中华民族到了最坑爹的时候

April 25th, 2012 by 王 聪 No comments »

牛奶不能喝了!

奶粉不能吃了!

馒头不能吃了!

食用油不能用了!

胶囊不能吃了!

果冻酸奶不能吃了!

蜜饯不能吃了!

沙琪玛不能吃了!

牛肉拉面不能吃了!

砂锅粥不能吃了!

可乐不能喝了!

纯净水不能喝了!

果粒橙不能喝了!

雪碧不能喝了!

绿茶不能喝了!

……

起来!不愿做奴隶的人们!把我们的食物铸成我们新的生化武器!中华民族到了,最坑爹的时候!每个人被迫着发出最后的吼声!起来!起来!起来!我们东亚病夫,吃着最毒的食物,前进!吃着最毒的食物, 前进!前进!前进!进!

分享视频:从一维空间到十二维空间

April 20th, 2012 by 王 聪 7 comments »

刚看到一个很有趣的讲多维空间的科普视频:

后悔当年物理没有学好,看到四维后面就不懂了。

perfbook 读书笔记:ACCESS_ONCE()

April 3rd, 2012 by 王 聪 2 comments »

如果你看过 Linux 内核中的 RCU 的实现,你应该注意到了这个叫做 ACCESS_ONCE() 宏,但是并没有很多人真正理解它的含义。网上有的地方甚至对此有错误的解释,所以特写此文来澄清一下。

虽然我早在读 perfbook 之前就了解了 ACCESS_ONCE() 的含义(通过询问大牛 Paul),但这本书中正好也没有很详细地介绍这个宏,所以就当是此书的读书笔记了。

定义

它的定义很简单,在 include/linux/compiler.h 的底部:

C:
  1. #define ACCESS_ONCE(x) (*(volatile typeof(x) *)&(x))

仅从语法上讲,这似乎毫无意义,先取其地址,在通过指针取其值。而实际上不然,多了一个关键词 volatile,所以它的含义就是强制编译器每次使用 x 都从内存中获取。

原因
仅仅从定义来看基本上看不大出来为什么要引入这么一个东西。可以通过几个例子(均来自 Paul,我做了小的修改)看一下。

1. 循环中有每次都要读取的全局变量:

C:
  1. ...
  2. static int should_continue;
  3. static void do_something(void);
  4. ...
  5.                while (should_continue)
  6.                        do_something();

假设 do_something() 函数中并没有对变量 should_continue 做任何修改,那么,编译器完全有可能把它优化成:

C:
  1. ...
  2.                if (should_continue)
  3.                        for (;;)
  4.                                do_something();

这很好理解,不是吗?对于单线程的程序,这么做完全没问题,可是对于多线程,问题就出来了:如果这个线程在执行do_something() 的期间,另外一个线程改变了 should_continue 的值,那么上面的优化就是完全错误的了!更严重的问题是,编译器根本就没有办法知道这段代码是不是并发的,也就无从决定进行的优化是不是正确的!

这里有两种解决办法:1) 给 should_continue 加锁,毕竟多个进程访问和修改全局变量需要锁是很自然的;2) 禁止编译器做此优化。加锁的方法有些过了,毕竟 should_continue 只是一个布尔,而且退一步讲,就算每次读到的值不是最新的 should_continue 的值也可能是无所谓的,大不了多循环几次,所以禁止编译器做优化是一个更简单也更容易的解决办法。我们使用 ACCESS_ONCE() 来访问 should_continue:

C:
  1. ...
  2.      while (ACCESS_ONCE(should_continue))
  3.                        do_something();

2. 指针读取一次,但要dereference多次:

C:
  1. ...
  2.     p = global_ptr;
  3.     if (p && p->s && p->s->func)
  4.         p->s->func();

那么编译器也有可能把它编译成:

C:
  1. ...
  2.     if (global_ptr && global_ptr->s && global_ptr->s->func)
  3.         global_ptr->s->func();

你可以谴责编译器有些笨了,但事实上这是C标准允许的。这种情况下,另外的进程做了 global_ptr = NULL; 就会导致后一段代码 segfault,而前一段代码没问题。同上,所以这时候也要用 ACCESS_ONCE():

C:
  1. ...
  2.     p = ACCESS_ONCE(global_ptr);
  3.     if (p && p->s && p->s->func)
  4.         p->s->func();

3. watchdog 中的变量:

C:
  1. for (;;) {
  2.                        still_working = 1;
  3.                        do_something();
  4.                }

假设 do_something() 定义是可见的,而且没有修改 still_working 的值,那么,编译器可能会把它优化成:

C:
  1. still_working = 1;
  2.                for (;;) {
  3.                        do_something();
  4.                }

如果其它进程同时执行了:

C:
  1. for (;;) {
  2.                        still_working = 0;
  3.                        sleep(10);
  4.                        if (!still_working)
  5.                                panic();
  6.                }

通过 still_working 变量来检测 wathcdog 是否停止了,并且等待10秒后,它确实停止了,panic()!经过编译器优化后,就算它没有停止也会 panic!!所以也应该加上 ACCESS_ONCE():

C:
  1. for (;;) {
  2.                        ACCESS_ONCE(still_working) = 1;
  3.                        do_something();
  4.                }

综上,我们不难看出,需要使用 ACCESS_ONCE() 的两个条件是:

1. 在无锁的情况下访问全局变量;
2. 对该变量的访问可能被编译器优化成合并成一次(上面第1、3个例子)或者拆分成多次(上面第2个例子)。

例子

Linus 在邮件中给出的另外一个例子是:

编译器有可能把下面的代码:

C:
  1. if (a> MEMORY) {
  2.         do1;
  3.         do2;
  4.         do3;
  5.     } else {
  6.         do2;
  7.     }

优化成:

C:
  1. if (a> MEMORY)
  2.         do1;
  3.     do2;
  4.     if (a> MEMORY)
  5.         do3;

这里完全符合上面我总结出来的两个条件,所以也应该使用 ACCESS_ONCE()。正如 Linus 所说,不是编译器一定会这么优化,而是你无法证明它不会做这样的优化。

So the rule is: if you access unlocked values, you use ACCESS_ONCE(). You
don't say "but it can't matter". Because you simply don't know.

再看实际中的例子:

commit 0ad92ad03aa444b312bd318b0341011a8be09d13
Author: Eric Dumazet
Date:   Tue Nov 1 12:56:59 2011 +0000

    udp: fix a race in encap_rcv handling

    udp_queue_rcv_skb() has a possible race in encap_rcv handling, since
    this pointer can be changed anytime.

    We should use ACCESS_ONCE() to close the race.

diff --git a/net/ipv4/udp.c b/net/ipv4/udp.c
index 131d8a7..ab0966d 100644
--- a/net/ipv4/udp.c
+++ b/net/ipv4/udp.c
@@ -1397,6 +1397,8 @@ int udp_queue_rcv_skb(struct sock *sk, struct sk_buff *skb)
 	nf_reset(skb);

 	if (up->encap_type) {
+		int (*encap_rcv)(struct sock *sk, struct sk_buff *skb);
+
 		/*
 		 * This is an encapsulation socket so pass the skb to
 		 * the socket's udp_encap_rcv() hook. Otherwise, just
@@ -1409,11 +1411,11 @@ int udp_queue_rcv_skb(struct sock *sk, struct sk_buff *skb)
 		 */

 		/* if we're overly short, let UDP handle it */
-		if (skb->len > sizeof(struct udphdr) &&
-		    up->encap_rcv != NULL) {
+		encap_rcv = ACCESS_ONCE(up->encap_rcv);
+		if (skb->len > sizeof(struct udphdr) && encap_rcv != NULL) {
 			int ret;

-			ret = (*up->encap_rcv)(sk, skb);
+			ret = encap_rcv(sk, skb);
 			if (ret <= 0) {
 				UDP_INC_STATS_BH(sock_net(sk),
 						 UDP_MIB_INDATAGRAMS,

更多

或许看了上面的会让你有一种错觉,volatile 可以解决同步的问题,其实不然,它只解决其中一个方面。而且上面所有的例子有一个共同的特点:所有的写操作都是简单的赋值(相对于大于CPU字宽的结构体赋值),简单赋值操作在所有平台上都是原子性的,而如果是做加法操作,原子性未必可以保证,更不用说需要 memory barrier 的时候了。所以,不要滥用 volatile。

perfbook 读书笔记:SLAB_DESTROY_BY_RCU

March 29th, 2012 by 王 聪 No comments »

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

要理解 SLAB_DESTROY_BY_RCU,最重要的是看 kmem_cache_destroy(),以 slub 为例,

C:
  1. void kmem_cache_destroy(struct kmem_cache *s)
  2. {
  3.         down_write(&slub_lock);
  4.         s->refcount--;
  5.         if (!s->refcount) {
  6.                 list_del(&s->list);
  7.                 up_write(&slub_lock);
  8.                 if (kmem_cache_close(s)) {
  9.                         printk(KERN_ERR "SLUB %s: %s called for cache that "
  10.                                 "still has objects.\n", s->name, __func__);
  11.                         dump_stack();
  12.                 }
  13.                 if (s->flags & SLAB_DESTROY_BY_RCU)
  14.                         rcu_barrier();
  15.                 sysfs_slab_remove(s);
  16.         } else
  17.                 up_write(&slub_lock);
  18. }

看那两行就足够了,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:
  1. struct sighand_struct *__lock_task_sighand(struct task_struct *tsk,
  2.                                            unsigned long *flags)
  3. {              
  4.         struct sighand_struct *sighand;
  5.  
  6.         for (;;) {
  7.                 local_irq_save(*flags);
  8.                 rcu_read_lock();
  9.                 sighand = rcu_dereference(tsk->sighand);
  10.                 if (unlikely(sighand == NULL)) {
  11.                         rcu_read_unlock();
  12.                         local_irq_restore(*flags);
  13.                         break;
  14.                 }
  15.  
  16.                 spin_lock(&sighand->siglock);
  17.                 if (likely(sighand == tsk->sighand)) {
  18.                         rcu_read_unlock();
  19.                         break;
  20.                 }
  21.                 spin_unlock(&sighand->siglock);
  22.                 rcu_read_unlock();
  23.                 local_irq_restore(*flags);
  24.         }
  25.  
  26.         return sighand;
  27. }

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

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

perfbook 读书笔记:livelock

March 24th, 2012 by 王 聪 No comments »

注:本文以及后面的文章中提到的 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:
  1. void shrink_dcache_parent(struct dentry * parent)
  2. {
  3.         LIST_HEAD(dispose);
  4.         int found;
  5.  
  6.         while ((found = select_parent(parent, &dispose)) != 0)
  7.                 shrink_dentry_list(&dispose);
  8. }

根据这个 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:
  1. ...
  2.         if (inode && !spin_trylock(&inode->i_lock)) {
  3. relock:
  4.                 spin_unlock(&dentry->d_lock);
  5.                 cpu_relax();
  6.                 return dentry; /* try again with same dentry */
  7.         }
  8.         if (IS_ROOT(dentry))
  9.                 parent = NULL;
  10.         else
  11.                 parent = dentry->d_parent;
  12.         if (parent && !spin_trylock(&parent->d_lock)) {
  13.                 if (inode)
  14.                         spin_unlock(&inode->i_lock);
  15.                 goto relock;
  16.         }

因为另一个进程持有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

March 20th, 2012 by 王 聪 No comments »

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

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

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

C:
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <stddef.h>
  4.  
  5. #define AlignOf(type_) (offsetof(struct { char c; type_ t; }, t))
  6. int main(void)
  7. {
  8.     struct foo { char a; int b; long c; };
  9.     typedef struct foo bar[128];
  10.  
  11.     printf("sizeof foo: %lu\n", sizeof(struct foo));
  12.     printf("AlignOf foo: %lu\n", AlignOf(struct foo));
  13.     printf("sizeof bar: %lu\n", sizeof(bar));
  14.     printf("AlignOf bar: %lu\n", AlignOf(bar));
  15.     return 0;
  16. }

输出:
sizeof foo: 16
AlignOf foo: 8
sizeof bar: 2048
AlignOf bar: 8

知识共享许可协议
本作品采用知识共享署名-非商业性使用-相同方式共享 2.5 中国大陆许可协议进行许可。
葡驻京办ICP备07006283号