Unreliable Guide to Locking -by Rusty Russell-中文版

albcamus

第8章. 加锁速度


在考虑使用锁的代码的速度问题上，主要有三件事需要关注。首先是并发性：当锁被别人持有时，有多少事情是我们需要等待的。其次是，需要花多少时间来获取与释放一把无争议的锁。第三呢，是尽量使用更少的──或曰更灵活的──锁。当然，这里我已经假定锁的使用非常频繁，否则你都不用担心效率问题的。

并发性依赖于锁被持有多长时间：你持有锁的时间，就应该同确实需要持有它的时间一样长，不要更长。在上面那个关于cache的例子中，我们在创建对象时是不持有锁的，只有在已经准备好把它插入到链表中时才去获取锁。

获取锁的时间依赖于加锁操作对于管道线(pipeline stalls)做了多少破坏性工作，以及本CPU是最后一个试图获取该锁的CPU(亦即：对本CPU来说，锁是否为缓存密集的(cache-hot))的可能性有多大：在具有很多CPU的机器上，这种可能性迅速降低。考虑一个700MHz的Intel Pentium III处理器：一条指令大约花费0.7纳秒，一次原子增加操作大约花费58纳秒，一次缓存密集的的加锁操作大约花费160纳秒，而从其他CPU上的一次缓存行转换还要额外花费170到360纳秒。(这些数据来自于Paul McKenney的Linux Journal RCU article )

这两个目标会发生冲突：通过把锁分成不同的的部分，可以减少持有锁的时间(例如上面例子中“每个对象一把的锁”)，但是这增加了获取锁这一操作的数量，因而结果一般是比只有一把锁的情况要慢一些。这也是推崇加锁简洁性的一个理由。

第三个考虑点放到了下面：的确存在一些方法能够减少锁的使用。


8.1. 读/写锁变体


自旋锁与信号量都具有读/写变体：rwlock_t和struct rw_semaphore。它们把使用者分成了两类：读者和写者。如果你只需要读数据，你该获取读锁；但如果你需要写数据，你需要获取写锁。可以有很多使用者同时获取读锁，但写锁却只能有单个使用者持有。

如果你的代码可以简洁的划分出读和写的界限(就象我们上面的cache代码那样)，而且读者通常需要很长时间的持有读锁，使用读写锁会更好。它们要比普通的锁要稍微慢点儿，所以在实践中rwlock_t通常并不很值得使用。


8.2. 避免锁的使用：RCU


有一种特殊的读/写锁定方法叫做RCU(Read Copy Update)，读者可以完全避免使用锁：由于我们希望我们的cache被读取远比被更新来的频繁(否则的话，还引入cache干什么？)，使用RCU就是一个可选择的优化。

如何移除读锁呢？移除读锁意味着写者可能在存在读者的情况下更新链表。这很简单：要向链表中添加元素的代码足够小心，我们就可以在它添加的同时读取链表。例如，把new元素添加到list链表中：

1. 
   
2. 
   
3.         new->next = list->next;
   
4.         wmb();
   
5.         list->next = new;
   
6.    
   

复制代码

wmb()是一个写内存屏障。它保证了第一个操作（设置新元素的next指针）是完整的，而且立即为其它CPU所见，这发生在第二个操作（把新元素添加到链表中）之前。这是很重要的，因为现代CPU和编译器可能会改变指令的执行顺序，除非明确告诉它们不要这样：我们希望一个读者要么完全看不到新元素的插入，要么能够看到新元素插入之后的next指针正确指向了链表的剩余部分。

幸运的是，有一个函数专门添加标准的struct list_head链表：list_add_rcu() (include/linux/list.h)。

从链表中删除元素更简单：假设我们要删除的元素为A，我们让指向A的指针重新指向A的后继者，读者要么完全看到了它，要么完全忽略了它。


        list->next = old->next;   

有一个list_del_rcu()函数(include/linux/list.h)来做该工作（而普通版本的删除操作会毒害(poison)要移除的对象，这是我们不愿看到的）。

读者也一定要小心：有些CPU会观察next指针以便预取下一个元素，但这样的话，如果next指针恰恰在这时候发生了变化，那么这些CPU预取的(pre-fetched)内容就是错误的。还好，有一个list_fro_each_entry_rcu()函数(include/linux/list.h)可以帮助你。当然，写者可以只使用list_for_each_entry() （译者案：这里的“只使用”，是说不用但是是否需要一个XXX_rcu()这样的函数），因为不可能同时有两个写者。

我们的困难最终是：什么时候我们可以真正的删除元素？记住，一个读者可能正在访问要被删除的元素：如果我们释放掉这个元素，而让next指针指向新元素，读者将立即访问到垃圾内存并崩溃。我们必须等待到所有正在遍历链表的读者都结束了遍历，才能真正释放掉元素。我们用call_rcu()函数注册一个回调函数，当所有读者结束遍历时，它会真正销毁对象。

但是，RCU如何得知什么时候读者结束遍历了呢？首先，读者总是在rcu_read_lock()/rcu_read_unlock()之间执行遍历：这会禁止抢占（而且只是禁止抢占，其它什么都不做），因此读者在遍历链表期间不会睡眠。

RCU一直等待到其他的CPU至少睡眠了一次：因为读者不会在读取过程中睡眠，此时我们就知道我们等待其结束的那些读者终于都结束了。于是回调函数被调用。真实的RCU代码要比这里讲述的更优化些，但这里讲的是它的基础。

1. 
   
2. --- cache.c.perobjectlock 2003-12-11 17:15:03.000000000 +1100
   
3. +++ cache.c.rcupdate    2003-12-11 17:55:14.000000000 +1100
   
4. @@ -1,15 +1,18 @@
   
5. #include <linux/list.h>
   
6. #include <linux/slab.h>
   
7. #include <linux/string.h>
   
8. +#include <linux/rcupdate.h>
   
9. #include <asm/semaphore.h>
   
10. #include <asm/errno.h>
    
11. 
    
12. struct object
    
13. {
    
14. -        /* 下面两个域由cache_lock保护 */
    
15. +        /* 下面由RCU保护 */
    
16.          struct list_head list;
    
17.          int popularity;
    
18. 
    
19. +        struct rcu_head rcu;
    
20. +
    
21.          atomic_t refcnt;
    
22. 
    
23.          /* 一旦创建就不要更改. */
    
24. @@ -40,7 +43,7 @@
    
25. {
    
26.          struct object *i;
    
27. 
    
28. -        list_for_each_entry(i, &cache, list) {
    
29. +        list_for_each_entry_rcu(i, &cache, list) {
    
30.                  if (i->id == id) {
    
31.                          i->popularity++;
    
32.                          return i;
    
33. @@ -49,19 +52,25 @@
    
34.          return NULL;
    
35. }
    
36. 
    
37. +/* 一旦我们知道没有读者了，立即最终丢弃对象. */
    
38. +static void cache_delete_rcu(void *arg)
    
39. +{
    
40. +        object_put(arg);
    
41. +}
    
42. +
    
43. /* 必须在持有cache_lock的情况下调用 */
    
44. static void __cache_delete(struct object *obj)
    
45. {
    
46.          BUG_ON(!obj);
    
47. -        list_del(&obj->list);
    
48. -        object_put(obj);
    
49. +        list_del_rcu(&obj->list);
    
50.          cache_num--;
    
51. +        call_rcu(&obj->rcu, cache_delete_rcu, obj);
    
52. }
    
53. 
    
54. /* 必须在持有cache_lock的情况下调用 */
    
55. static void __cache_add(struct object *obj)
    
56. {
    
57. -        list_add(&obj->list, &cache);
    
58. +        list_add_rcu(&obj->list, &cache);
    
59.          if (++cache_num > MAX_CACHE_SIZE) {
    
60.                  struct object *i, *outcast = NULL;
    
61.                  list_for_each_entry(i, &cache, list) {
    
62. @@ -85,6 +94,7 @@
    
63.          obj->popularity = 0;
    
64.          atomic_set(&obj->refcnt, 1); /* cache本身占一个引用计数 */
    
65.          spin_lock_init(&obj->lock);
    
66. +        INIT_RCU_HEAD(&obj->rcu);
    
67. 
    
68.          spin_lock_irqsave(&cache_lock, flags);
    
69.          __cache_add(obj);
    
70. @@ -104,12 +114,11 @@
    
71. struct object *cache_find(int id)
    
72. {
    
73.          struct object *obj;
    
74. -        unsigned long flags;
    
75. 
    
76. -        spin_lock_irqsave(&cache_lock, flags);
    
77. +        rcu_read_lock();
    
78.          obj = __cache_find(id);
    
79.          if (obj)
    
80.                  object_get(obj);
    
81. -        spin_unlock_irqrestore(&cache_lock, flags);
    
82. +        rcu_read_unlock();
    
83.          return obj;
    
84. }

复制代码

注意读者会在__cache_find()中改变popularity域的值，但是没有使用锁。我们的方案应该把它变成atomic_t类型的，但是对本例来说我们不会导致竞态条件：近似的结果就已经不错了，所以我没做改变。

结果是，cache_find()函数并不需要与其它函数同步，因此它在SMP上几乎跟在UP上一样快。

此处还存在一个更纵深的可能的优化：想一想我们最初的cache代码，那时没有引用计数，无论何时调用者想访问对象，就要持有锁。这仍然是可能的：如果你持有锁，就没人能够删掉对象，因此你就不必读取并写回引用计数了。

由于RCU中的“读锁”会禁止抢占（而且只是禁止抢占，其它什么都不做），调用者如果调用cache_find()或object_put()之前已经禁止抢占了，就并不需要读取并写回引用计数：我们可以把__cache_find()变成非static的从而暴露给其它文件，这时候调用者就可以直接调用这些函数了。

此处的优势是：引用计数并不被写入，对象并不被更改，这在SMP机器上会非常快──由于CPU的caching的原因。


8.3. Per-CPU数据


另一种使用相当广泛的避免锁的技术是，为每个CPU使用数据的一份拷贝。例如，如果你想为一个普通的条件保持一个计数，你可能会使用自旋锁和一个计数器，这简单而漂亮。

如果它表现的太慢了(通常不会，但是如果你的确测试到这种情况发生了)，你就该改变一下策略：为每个CPU保持一个计数器，这样，没有一个计数器需要互斥的锁来保护。参考DEFINE_PER_CPU()，get_cpu_var()和put_cpu_var() (include/linux/percpu.h)。

Per-CPU计数器的另一个用场是local_t数据类型，和cpu_local_inc()以及其它的相关函数。这在某些体系结构上是比简单的加锁代码更高效的。(include/asm/local.h)

注意，对计数器来说，根本不存在简单而可靠的方法可以精确的得到它的值而不需要引入锁。只不过某些情况下这不是问题罢了。


8.4. 中断服务例程通常使用哪些数据


如果数据只是在中断服务例程内部访问，你根本不需要锁：内核本身已经保证了中断服务例程不会同时在多个CPU上运行。

Manfred Spraul指出，即使数据会偶尔被用户上下文或softirqs/tasklets访问，你仍然可以这样。中断服务例程自身不需要锁，其它所有的访问者这样做：

1. 
   
2.         spin_lock(&lock);
   
3.         disable_irq(irq);
   
4.         ...
   
5.         enable_irq(irq);s
   
6.         spin_unlock(&lock);
   

复制代码

disable_irq()禁止了中断服务例程的运行(如果此刻已经在别的CPU上运行了，那就等待它的结束)。自旋锁禁止了同时刻其它任何可能的访问。自然，这比单个spin_lock_irq()调用要慢些，所以只有这种访问很少发生时这种用法才是合理的。

albcamus

第9章. 中断里调用哪些函数是安全的？


内核中许多函数会导致睡眠(亦即，直接或间接地调用了scheduler())：当持有锁或禁止了抢占时，你不可以调用它们。这同样意味着只有在用户上下文才可以调用：在中断里调用它们是非法的。


9.1. 一些可能睡眠的函数


下面列出了最常见的几个，但通常来讲，你需要阅读代码来判断其它的函数是否可以在中断里安全的调用。如果每一个人都是在可睡眠环境下调用某个函数的，那么多半你也要保证可睡眠的环境(译者案：原文是“If everyone else who calls it can sleep, you probably need to be able to sleep, too.”) 特别地，注册与注销函数通常需要在用户上下文中调用，它们可能睡眠。

    *

      访问用户空间:
          o

            copy_from_user()
          o

            copy_to_user()
          o

            get_user()
          o

            put_user()
    *

      kmalloc(GFP_KERNEL)
    *

      down_interruptible() 和 down()

      有一个down_trylock()函数，它可以在中断上下文中调用，不会睡眠。Up()决不会导致睡眠。

9.2. 一些不会睡眠的函数


有些函数可以在任何上下文中调用，可以持有任何的锁。

    *

      printk()
    *

      kfree()
    *

      add_timer() 和 del_timer()

albcamus

第10章. 进一步阅读


    *

      Documentation/spinlock.txt: 这是Linus Torvalds的内核源代码中的自旋锁教程
    *

      Unix Systems for Modern Architectures: Symmetric Multiprocessing and Caching for Kernel Programmers.

      Curt Schimmel的一部对内核级加锁的极好的著作(不是为Linux写的，但几乎都适用)。书可能贵了些，但对于理解SMP加锁来说，它值这个价钱。[ISBN:0201633388]

      （译者案：中文译本《现代体系结构上的Unix系统：内核程序员的SMP和Caching技术》，人民邮电出版社2003年4月出版，定价￥39,共289页，翻译非常不错，是本值得阅读的好书。）

第11章. 致谢


感谢Telsa Gwynne在DocBook化文档上的帮助，整理与添加风格。

感谢Martin Pool，Phlipp Rumpf，Stephen rothwell，Paul Mackerras，Ruedi Aschwanden，Alan Cox，Manfred Spraul，Time Waugh，Pete Zaitcev，James Morris，Robert Love，Paul McKennney，John Ashby，感谢他们的校对、勘误、争论和评注。

感谢小团体(译者案：原词cabal，原意是阴谋团体，似乎具有反讽意味，讽刺有些人把Linux内核开发团队称为cabal的FUD行为)没有影响该文档。

albcamus

术语

（译者案：为了方便理解，本页所有术语条目一律保留其英文）


抢占，preemption
    在2.5内核之前，或编译时CONFIG_PREEMPT未打开，内核中用户上下文的进程不会彼此抢占（亦即：只要你占有CPU，你就一直占有，直到自己放弃或者发生硬件中断）。在2.5.4以后且打开了CONFIG_PREEMPT，事情改变了：在用户上下文，更高优先级的任务可以抢占当前任务：自旋锁为此改写，以添加禁止抢占的效果，即使在UP上也是如此。

bh
    下半部：由于历史原因，带有'_bh'后缀的函数现在通常指所有的软中断。例如spin_lock_bh()将阻止任何软中断在本CPU上的运行。原来的BH是不该继续使用的，它终将被tasklets取代。在任一给定时刻，一个下半部只可能有一个实例在运行。
    (译者注：Linux内核的各种下半部的命名混乱不堪，例如上面这句其实就不太严谨。tasklet/timer诚然是“任何时刻只可能有一个实例在运行”，但是一个softirq就有可能同时在多个CPU上运行。推荐阅读Robert Love的Linux Kernel Development 一书来理清个中关系)

硬件中断/硬中断，Hardware Interrupt/Hardware IRQ
    硬件中断请求。在硬件中断处理函数中，in_irq()宏返回true。

中断上下文，Interrupt Context
    非用户上下文：正在处理一个硬件中断或软中断。这种情况下，in_interrupt()宏返回true。

对称多处理器，SMP
    对称多处理器：为多CPU机器编译的内核。（CONFIG_SMP=y）.

软中断/softirq，Software Interrupt/softirq
    软中断处理程序。in_irq()返回false；in_softirq()返回true。Tasklets和softirqs都属于软中断。
    严格来讲，一个softirq是一个最多能有32个枚举类型的软中断，它可以同时运行在多个CPU上。有时softirq一词也用来指谓tasklets(也就是说，指谓所有的软中断)。

tasklet
    一种可动态注册的软中断，保证了同一时刻只能有一个CPU在运行它。

定时器，timer
    一种可动态注册的软中断，它在给定时刻(或接近给定时刻)运行。当运行时，它就象tasklet一样(事实上它们是作为TIMER_SOFTIRQ被调用的)。

单处理器，UP
    单处理器：非SMP。（CONFIG_SMP=n）

用户上下文，User Context
    内核代表某个进程(亦即，一次系统调用或陷阱)或内核线程在运行。你可以用current宏得知究竟是哪个进程。注意不要与“用户空间”一词搞混。它可以被硬件或软中断打断执行。

用户空间，Userspace
    进程在内核之外执行自己的代码。

翻译后记

    由于本人水平所限，加上没有SMP环境试验一些理解正确与否，文档误译之处肯定不少（有些不会翻译的干脆就保留原文了，如您所见）。 无论您有什么观点，请与albcamus@163.com联系，欢迎批评指正，我会尽量跟踪改进本文档的翻译。如果您英文可以的话，还是看原版吧，作者的行文并不难懂。
    在翻译过程中，alert7前辈为我提供了他的译稿做参考，并指正了很多问题，在此向他表示感谢！──当然，误译之处只由我自己负责。
    趁十一熬夜，05年10月05日凌晨6点

albcamus

HTML排版真是糟糕，论坛上更加无法整理。
制作了一个PDF文件，里面的超链接暂时不可用，等我改好了再另外上传一份吧

albcamus

传上来3天了，一点回应没有，没有人对互斥感兴趣？
写内核态代码，一不注意就会崩溃，没人需要这个？

bingosek

不懂也是要支持一下啦

不然论坛里就只剩下“急急急，我的linux上不了网”之流的帖子啦

fdrtnos

感谢，感谢，最近正在看互斥的一些东西！！！！

albcamus

这个帖子加个精华，方便别人查找──大家没意见吧?

zalem

呵呵，老早就拜读过了，不过只看了描述部分,涉及到linux的实现就全部略过了，以后再慢慢看...锁真让人头痛...搞通了的人，都是机器人...