2012/3

perfbook 读书笔记:SLAB_DESTROY_BY_RCU

perfbook 书中第8.3.3.6节讲到了类型安全,提到了Linux内核中的 SLAB_DESTROY_BY_RCU。但是书中并没有更详细的介绍这个特性。这里更详细地说一下。

要理解 SLABDESTROYBY_RCU,最重要的是看 kmem_cache_destroy(),以 slub 为例,
[c]
void kmem_cache_destroy(struct kmem_cache *s)
{
down_write(&slub_lock);
s->refcount—;
if (!s->refcount) {
list_del(&s->list);
up_write(&slub_lock);
if (kmem_cache_close(s)) {
printk(KERN_ERR “SLUB %s: %s called for cache that “
“still has objects.n”, s->name, __func
);
dump_stack();
}
if (s->flags & SLAB_DESTROY_BY_RCU)
rcu_barrier();
sysfs_slab_remove(s);
} else
up_write(&slub_lock);
}
[/c]

看那两行就足够了,rcu_barrier(); 是用来等待所有的 call_rcu() 回调函数结束,那么,kmem_cache_destroy() 在 SLAB_DESTROY_BY_RCU 的情况很明显就是等待所有 kmem_cache_free() 完成。

和普通的用 kmem_cache_alloc() 分配出来的对象相比,这种内存分配方式提供了更弱的保证,普通的分配可以保证对象不会被释放回 cache 中,而这个仅仅保证它不会被彻底释放,但不保证它会被放回 cache 重新利用,也就是说类型是不变的,即所谓的类型安全。实际上,在此期间它很有可能已经被放回 cache 重新利用了。

正是因为这种保证更弱了,所以在 rcu_read_lock() 并发区内就要多一个检查,检查是否还是之前的那个对象,因为这是类型安全的,所以对它进行同类型的检查是完全合法的。一个很好的例子是 __lock_task_sighand():

[c]
struct sighand_struct __lock_task_sighand(struct task_struct tsk,
unsigned long flags)
{
struct sighand_struct
sighand;

    for (;;) {
            local_irq_save(*flags);
            rcu_read_lock();
            sighand = rcu_dereference(tsk->sighand);
            if (unlikely(sighand == NULL)) {
                    rcu_read_unlock();
                    local_irq_restore(*flags);
                    break;
            }

            spin_lock(&sighand->siglock);
            if (likely(sighand == tsk->sighand)) {
                    rcu_read_unlock();
                    break;
            }
            spin_unlock(&sighand->siglock);
            rcu_read_unlock();
            local_irq_restore(*flags);
    }

    return sighand;

}
[/c]

注意,->siglock 是在 ->ctor() 中初始化的,所以刚分配出来的 sighand 的 ->siglock 也是已初始化的。

在此基础上,Linux 内核中还衍生出一个新的哈希链表,hlist_nulls,具体可以参考 Documentation/RCU/rculist_nulls.txt。

perfbook 读书笔记:livelock

注:本文以及后面的文章中提到的 perfbook 均是指大牛 Paul E. McKenney 的书,《Is Parallel Programming Hard, And, If So, What Can You Do About It?》,书名太长,故简写之。

最近一直在读这本 perfbook,它算是少有的全面而专门介绍 locking 的书,值得每个系统程序员去读。在读的过程中发现有的地方它介绍的并不是很详细,所以就写几篇读书笔记也算是对它的小小补充。

书中 6.1.2 节讲到了 livelock,即所谓的“活锁”,相对于死锁(deadlock)而言。因为上过操作系统课的原因,我估计很多人对 deadlock 并不陌生,但是 livelock 相对不那么熟悉。livelock 无非是饥饿(starvation)的极端情况。饥饿是由竞争引起,所谓竞争(contention)是指尝试获取一个已经被锁住的锁,长时间竞争会导致这些得不到锁的进程饥饿,所以饥饿的极端情况就是多个进程一直在尝试获取某一(几)把锁,但一直都得不到满足。

书中给出的例子很简单,解决方法是给两个进程加上不同延迟,也同时增加了 overhead,所以这个例子并不是很好。我们看一个现实中的例子,Linux 内核中的一个 livelock 的 bug:

commit eaf5f9073533cde21c7121c136f1c3f072d9cf59
Author: Miklos Szeredi
Date: Tue Jan 10 18:22:25 2012 +0100

fix shrink_dcache_parent() livelock

发生 livelock 的地方是 shrink_dcache_parent(),看其定义:
[c]
void shrink_dcache_parent(struct dentry * parent)
{
LIST_HEAD(dispose);
int found;

    while ((found = select_parent(parent, &dispose)) != 0)
            shrink_dentry_list(&dispose);

}
[/c]

根据这个 commit 的描述,我们可以发现存在下面这种情况:

1. CPU0 上的进程调用 select_parent(P) 找到了 dentry C,并把它放入 dispose 链表中,返回1;

2. 与此同时,CPU1 上的另一个进程也调用了select_parent(P),获取了 dentry P 的 ->d_lock;

3. CPU0 上的进程继续调用 shrink_dentry_list(),获取了 dentry C 的 ->d_lock,然后又调用 try_prune_one_dentry(C),dentry_kill(C):

[c]

if (inode && !spin_trylock(&inode->i_lock)) {
relock:
spin_unlock(&dentry->d_lock);
cpu_relax();
return dentry; / try again with same dentry /
}
if (IS_ROOT(dentry))
parent = NULL;
else
parent = dentry->d_parent;
if (parent && !spin_trylock(&parent->d_lock)) {
if (inode)
spin_unlock(&inode->i_lock);
goto relock;
}
[/c]

因为另一个进程持有dentry P的->d_lock,所以 dentry_kill() 中 spin_trylock(&parent->d_lock) 失败,转而 spin_unlock(&dentry->d_lock) 并返回;

4. CPU1 上的进程此时仍在调用 select_parent(P),并找到了 dentry C,锁住了它的->d_lock,放入 dispose 链表并返回1(其实就是重复步骤(1));

5. CPU0 上的进程继续 shrink_dentry_list() 中的循环,发现 dispose 链表已经为空,退出循环并返回;

6. CPU1 的进程开始重复步骤(3);

7. CPU0 的进程开始重复步骤(2)。

Livelock 产生了!

这里问题的关键在于那个 dispose list,如果 dentry C被某个进程加入到 dispose list 中,另外的进程不应该再找到它,所以修复就是加一个标志位 DCACHE_SHRINK_LIST,来标示这个 dentry 有没有被加入。

用宏实现 alignof

我们知道在C2011标准中引入了 alignof 操作符,但是在 gcc 和 glibc 完全支持 C2011 之前,我们仍然不能使用它。其实我们可以自己用宏实现一个(出自c.l.c):

define AlignOf(type) (offsetof(struct { char c; type t; }, t))

它巧妙地把参数指定的类型放入一个结构体中,在此结构体的最前面镶入一个 char 类型,这样该成员在结构体中的偏移就是它对齐的位置。看例子:

[c]

include

include

include

define AlignOf(type) (offsetof(struct { char c; type t; }, t))

int main(void)
{
struct foo { char a; int b; long c; };
typedef struct foo bar[128];

printf("sizeof foo: %lun", sizeof(struct foo));
printf("AlignOf foo: %lun", AlignOf(struct foo));
printf("sizeof bar: %lun", sizeof(bar));
printf("AlignOf bar: %lun", AlignOf(bar));
return 0;

}
[/c]
输出:
sizeof foo: 16
AlignOf foo: 8
sizeof bar: 2048
AlignOf bar: 8

再见,大理!

从去年7月初开始,在大理待了半年多了。明天一早就要离开大理了,各种舍不得……这期间因为去新疆离开过一次,可这次不同,下次再回来不知道是何时。

大理是我在国内能找到的最适宜居住和生活的地方了,没有之一。我理想中的生活有两种:一种是在路上,四处漂泊浪迹天涯;另一种是像在大理这样,白天晒晒太阳,晚上和朋友喝喝茶,打打牌,聊聊天,日子就这么无忧无虑地过着……

希望以后你们哪一位去往大理转,路过人民路超人蔬菜馆,给鸟哥打声招呼;路过人民路养生粥,买碗粥,顺便给老板小月打声招呼;若住在叶榆路阿弟家客栈给老板杨姐问声好!

再见,大理!不知道下次再回来你会变成什么样子!就算是真变成了“失败者乐园,老少边穷文艺中青年扎堆,街上十个人九个神经病,五个飞叶子,三个修禅的,一个摆地摊的”也千万不要变成丽江那样搞一夜情的圣地!不要!

(相册:在大理的日子

关于 extern inline

(本文是《C语言编程艺术》的一部分,转载请注明出处,勿用于商业用途。)

大家一定对C语言 inline 关键字不陌生,甚至经常用到 static inline 的函数。可能感到陌生的是 extern inline。C11 标准在6.7.4 p7 中对此进行了描述,不过比较生涩难读。简单地讲,static line 和 extern inline 的区别,从名字上也能看得出来,就是编译单元之外可见性的问题。把一个普通函数给内联掉之后,一个显著的区别就是外部可见性没了,怎么能同时既能内联又能保留外部的可见性呢?为了解决这个问题就有了extern inline。

static inline 是说这个函数就这么一个,而且没有外部可见性,在所有的编译单元中大家必须共用这么一个定义,这也是为什么 static inline 通常要放到头文件中的原因;而 extern inline 就不一样了,它是说这个函数虽然只有一个定义,但是既有内联的版本,也有非内联的版本,如果你能看得到它的定义。即在同一个编译单元中,那么你就可以用它的内联版本;看不到的话,你就可以用非内联版本,即和其它普通函数一模一样。

而如果既不带 static 也不带 extern 的话,含义又不同了:前面的 extern inline 只需要定义一次,只是不同的地方看到的版本不同,有的地方看到的是内联的版本,而有的地方看到的只是个 external reference。而仅用 inline 的话,就变成了要定义两次,带 inline 关键字的这个定义就是内联版本,在这个编译单元中都用这个版本,而在外部,还是使用普通的非内联定义。换句话说,带 inline 的定义遮盖住了外部的定义。既然有两个不同的版本,那么也就需要保持这两个版本的定义相同,否则就会有问题。

以上是标准C的定义,而 GNU89 的定义就不同了,基本上是把”extern inline”和”inline”的含义给交换了,“static line” 的含义都是相同的。看下面的标准C的例子:

[c]
//a.c
//C99
extern inline int max(int a, int b)
{
return a > b ? a : b;
}

int a = 10;
int b = 20;
int foo(void)
{
return max(a, b);
}

extern int bar(void);

int main(void)
{
return foo() + bar();
}

//b.c
//C99
extern int max(int a, int b);

int bar(void)
{
int a = 10;
int b = 20;
return max(a, b);
}
[/c]

我们这么编译:
% gcc -std=c99 -O2 -Wall -W a.c b.c -o c

而我们如果把它编译成 GNU89 的话,就会报错:
% gcc -std=gnu89 -O2 -Wall -W a.c b.c -o c
/tmp/ccAJTzwY.o: In function bar': b.c:(.text+0xb): undefined reference tomax’
collect2: ld returned 1 exit status

很明显,因为 GNU89 中的 extern inline 需要两个定义,明显我们少了一个。修改后的代码如下:

[c]
//a.c
//GNU89
extern inline int max(int a, int b)
{
return a > b ? a : b;
}

int a = 10;
int b = 20;
int foo(void)
{
return max(a, b);
}

extern int bar(void);

int main(void)
{
return foo() + bar();
}

// b.c
//GNU89
int max(int a, int b)
{
return a > b ? a : b;
}

int bar(void)
{
int a = 10;
int b = 20;
return max(a, b);
}
[/c]

glibc 中就用到了 GNU89 的extern inline 特性,在 ctype.h 中,tolower()/toupper() 的定义是:
[c]

ifdef __USE_EXTERN_INLINES

extern_inline int NTH (tolower (int c))
{
return
c >= -128 && c = -128 && c = -128 && c = -128 && c < 256 ? __ctype_toupper[c] : c;
}
[/c]

顺便说一句,gcc 提供了-fgnu89-inline 和 -fno-gnu89-inline 选项可在编译时控制上述 inline 的行为。

Stackoverflow 上有人做了一个很好的总结,我翻译了一下:

GNU89:

"inline": 函数可能会被内联掉,非内联的版本总是会生成,而且外部可见,因此内联的定义在本编译单元中只能有一次,其它地方看到的是非内联版本。

"static inline":不会生成外部可见的非内联版本,可能会生成一个 static 的非内联版本。它当然可以被定义多次,因为外部看不到它。

"extern inline":不会生成一个非内联的版本,但是可以调用一个非内联版本(因此你必须在其它编译单元中定义它)。只能有一个定义的规则当然也适用,非内联版本和内联版本的代码必须是一样的。

C99 (or GNU99):

"inline":和 GNU89 的 "extern inline" 一样,没有外部可见的函数生成,但是外部可见的函数必须存在,因为有可能会用到它。

"extern inline":和 GNU89 的 "inline" 一样, 会生成外部可见的代码,最多一个编译单元可以使用它。

"static inline":和 GNU89 的 "static inline" 一样,这是唯一一个在 GNU89 和 C99之间可移植的。

最后,我们可以看大神 Linus Torvalds 如何描述 extern inline:

“static inline” means “we have to have this function, if you use it, but don’t inline it, then make a static version of it in this compilation unit”. “extern inline” means “I actually have an extern for this function, but if you want to inline it, here’s the inline-version”.

参考资料:
http://www.greenend.org.uk/rjk/tech/inline.html
http://gcc.gnu.org/ml/gcc/2006-11/msg00006.html
http://stackoverflow.com/questions/6312597/is-inline-without-static-or-extern-ever-useful-in-c99
http://www.cnblogs.com/cnmaizi/archive/2011/01/19/1939686.html

不同人眼中的我

在别人眼中我是

在我朋友眼中我是

在同行眼中我是

在我女朋友眼中我是

在我父母眼中我是

我以为我是

而实际上我是

终有一天我会是