免费注册 查看新帖 |

ChinaUnix.net

  平台 论坛 博客 文库
12345下一页
最近访问板块 发新帖
查看: 20947 | 回复: 46

Unreliable Guide to Locking -by Rusty Russell-中文版 [复制链接]

论坛徽章:
0
发表于 2005-11-25 17:45 |显示全部楼层
Kernel Locking 中文版


Unreliable Guide To Locking
Rusty Russell

      <rusty@rustcorp.com.au>
翻译:

      albcamus <albcamus@163.com>


Copyright © 2003 Rusty Russell

This documentation is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA

For more details see the file COPYING in the source distribution of Linux.

论坛徽章:
0
发表于 2005-11-25 17:46 |显示全部楼层
第1章. 介绍


欢迎进入Rusty优秀的《Unreliable Guide to Kernel Locking》细节。本文档描述了Linux 2.6内核的锁系统。

随着Linux内核引入了超线程与 抢占 ,每一个Hacking内核的人都应该了解并发性与为SMP加锁的基础知识。

论坛徽章:
0
发表于 2005-11-25 17:46 |显示全部楼层
第2章. 并发带来的问题


(如果你已知道并发是什么,请略过本章).

在一个普通的程序里,你可以这样为一个计数器增加计数:


        very_important_count++;


下面是你期望的结果:
table21.png

论坛徽章:
0
发表于 2005-11-25 17:47 |显示全部楼层
事情还可能这样发生:

Table 2-2. 可能的结果
table22.png

论坛徽章:
0
发表于 2005-11-25 17:48 |显示全部楼层
2.1. 竞态条件与临界区


这种情况,结果依赖于多个任务的相对执行顺序,叫做竞态条件。包含并发问题的代码,叫做临界区。尤其是Linux开始支持SMP机器以来,竞态条件和临界区就成为内核设计与实现的主要问题。

抢占具有相同的影响,即使只有一个CPU也是这样的:抢占了正在临界区中执行的任务,我们就重现了上面描述的情况。在这种情况下,抢占了其他代码的线程必须在它的临界区独自运行(排斥其它线程)。

解决的方法是:认识到何时会发生同时访问,使用锁来保证在任意时刻只有一个实例能够进入临界区。在Linux内核中有很多友好的原语(primitives)来帮助你做到这点──也有不友好的原语,但我将当作它们并不存在。

论坛徽章:
0
发表于 2005-11-25 17:49 |显示全部楼层
第3章. 在Linux内核中加锁


我多么希望能给你一句忠告:不要与比你更不理性的人同眠;而如果是关于锁的忠告,我会这样给出:保持简单。

不要试图引入新类型的锁。


真是够奇怪的,最后一条竟然恰恰与我的忠告相反──因为这时你已经与不理性的人同眠了,你需要考虑弄只看门狗。(译者案:Watchdog是一种以NMI方式检查CPU死锁的机制)


3.1. 两种主要类型的锁:自旋锁与信号量


内核中主要有两种类型的锁。最基本的类型是自旋锁(include/asm/spinlock.h),它只允许一个持有者;如果你获取自旋锁时不成功,你将一直在自旋中尝试获得它,直到成功。自旋锁又小又快,可以在任何地方使用。

第二种类型是信号量(include/asm/spinlock.h),它可以在任何时刻被多个持有者同时持有(允许的持有者的数量是在信号量初试化时规定的),但是在通常情况下信号量只允许一个持有者(这时它也叫互斥锁,mutex)。如果你获取信号量时不成功,任务就会把自身放到一个队列中睡眠,一直到信号量被释放时才被唤醒。这意味着在你等待的时候,CPU将做其他的事情。但是,很多情况是不允许睡眠的(参考 第9章 ),这时你应该用自旋锁而不是信号量。

这两种锁的任何一种都是不允许递归的:参考 7.1小节.


3.2. 单CPU内核与锁


在单CPU机器上,对于编译时既没打开CONFIG_SMP、也没打开CONFIG_PREEMPT的内核来说,自旋锁根本不存在。这是一个出色的设计策略:既然没有别人能在同时刻执行,就没理由加锁。

(译案:感谢max2005兄的指正)

如果编译时同时打开了CONFIG_SMP和CONFIG_PREEMPT,自旋锁的作用就仅仅是禁止抢占,这就足以防止任何竞态了。多数情况下,我们可以把抢占等同于SMP来考虑其可能带来的竞态问题,不必单独对付它。

当测试加锁代码时,即使你没有SMP测试环境,总应该打开CONFIG_SMP和CONFIG_PREEMPT选项,因为这会重现关于锁的某些类型的BUG。

信号量依然存在,因为它们之所以被引入,乃是为了同步用户上下文。我们将马上看到这一点。


3.3. 只在用户上下文加锁


如果你的数据结构只可能被用户上下文访问,你可以用信号量(linux/asm/semaphore.h)来保护它。这是最简单的情况了:把信号量初试化为可用资源的数量(通常是1),就可以调用down_interruptible()来获取信号量,调用up()来释放它。还有一个down()函数,但应该避免使用它,因为如果有信号到来它不会返回。

例如:linux/net/core/netfilter.c允许用nf_register_sockopt()注册新的setsockopt()和getsockopt()调用。注册和注销只有在模块加载与卸载时才会发生(是在引导时执行的,没有并发问题),注册了的链表只有setsockopt()或getsockopt()系统调用才会查阅。因此,nf_sockopt_mutex 就可以完美的保护住这些,这是因为setsockopt和getsockopt允许睡眠。


3.4. 在用户上下文与Softirqs之间加锁


如果一个softirq与用户上下文共享数据,就有两个问题:首先,当前的用户上下文可能被softirq中断;其次,临界区可能会在别的CPU进入。这时spin_lock_bh() (include/linux/spinlock.h)就有了用武之地。它会在那个CPU上禁止softirqs,然后获取锁。spin_unlock_bh()做相反的工作。(由于历史原因,后缀‘bh’成为对各种下半部的通称,后者是software interrupts的旧称。其实spin_lock_bh本应叫作spin_lock_softirq才贴切)

注意这里你也可以用spin_lock_irq()或者spin_lock_irqsave(),这样不单会禁止softirqs,还会禁止硬件中断:参考第4章。

这在UP 上也能很好地工作:自旋锁消失了,该宏变成了只是local_bh_disable() (include/linux/interrupt.h),它会禁止softirqs运行。


3.5. 在用户上下文与Tasklets之间加锁


这种情况与上面的情况(译者案,上面“在用户上下文与softirqs之间加锁”的情况)完全一致,因为tasklets本来就是作为一种softirq运行的。


3.6. 在用户上下文与Timers之间加锁


这种情况也和上面情况完全一致,因为timers本来就是一种softirq(译者案:Timer是时钟中断的下半部)。从加锁观点来看,tasklets和timers的地位是等同的。


3.7. 在Tasklets/Timers之间加锁


有时一个tasklet或timer会与另一个tasklet或timer共享数据。


3.7.1. 同一个Tasklet/Timer


由于同一时刻,一个tasklet决不会在两个CPU上执行,即使在SMP机器上,你也不必担心你的tasklet会发生重入问题(同时运行了两个实例)


3.7.2. 不同的Tasklets/Timers


如果你的tasklet或timer想要同另一个tasklet或timer共享数据,你需要对它们二者都使用spin_lock()和spin_unlock()。没必要使用spin_lock_bh(),因为你已经处在tasklet中了,而同一个CPU不会同时再执行其他的tasklet。


3.8. 在Softirqs之间加锁


一个softirq经常需要与自己或其它的tasklet/timer共享数据。


3.8.1. 同一个Softirq


同一个softirq可能在别的CPU上执行:你可以使用per-CPU数据(参考 8.3小节)以获得更好的性能。如果你打算这样使用softirq,通常是为了获得可伸缩的高性能而带来额外的复杂性。

你需要用spin_lock()和spin_unlock()保护共享数据。


3.8.2. 不同的 Softirqs


你需要使用spin_lock()和spin_unlock()保护共享数据,不管是timer,tasklet,还是不同的/同一个/另一个的softirq:它们中的任何一个都可以在另一个CPU上运行。

[ 本帖最后由 albcamus 于 2006-10-12 11:36 编辑 ]

论坛徽章:
0
发表于 2005-11-25 17:50 |显示全部楼层
第4章. 硬中断上下文


硬中断通常与一个tasklet或softirq通信。这通常涉及到把一个任务放到某个队列中,再由softirq取出来。


4.1. 在硬中断与Softirqs/Tasklets之间加锁


如果一个硬件中断服务例程与一个softirq共享数据,就有两点需要考虑。第一,softirq的执行过程可能会被硬件中断打断;第二,临界区可能会被另一个CPU上的硬件中断进入。这正是spin_lock_irq()派上用场的地方。它在那个CPU上禁止中断,然后获取锁。spin_unlock_irq()做相反的工作。

硬件中断服务例程中不需要使用spin_lock_irq(),因为当它在执行的时候softirq是不可能执行的:它可以使用spin_lock(),这个会更快一些。唯一的例外是另一个硬件中断服务例程使用了相同的锁:spin_lock_irq()会禁止那个硬件中断。

这在UP机器上也能很好的工作:自旋锁消失了,spin_lock_irq()变成了仅仅是local_irq_disable() (include/asm/smp.h),这将会禁止sofirq/tasklet/BH的运行。

spin_lock_irqsave()(include/linux/spinlock.h)是spin_lock_irq()的变体,它把当前的中断开启与否的状态保存在一个状态字中,用以将来传递给spin_unlock_restore()。这意味着同样的代码既可以在硬件中断服务例程中(这时中断已关闭)使用,也可以在softirqs中(这时需要主动禁止中断)使用。

注意,softirqs(包括tasklets和timers)是在硬件中断返回时得到运行的,因此spin_lock_irq()同样也会禁止掉它们。从这个意义上说,spin_lock_irqsave()是最通用和最强大的加锁函数。


4.2. 在两个硬中断服务例程之间加锁


很少有两个硬件中断服务例程共享数据的情况。如果你真的需要这样做,可以使用spin_lock_irqsave() :在进入中断服务时是否自动关闭中断,这件事是体系结构相关的。

论坛徽章:
0
发表于 2005-11-25 17:50 |显示全部楼层
第5章. 关于锁的使用的图表


Pete Zaitcev 提供了这样的总结:

    *

      如果你处在进程上下文(任何系统调用),想把其他进程排挤出临界区,使用信号量。你可以获得信号量之后去睡眠(例如调用copy_from_user或kmalloc(x, GFP_KERNEL)之类的函数)。
    *

      否则(亦即:数据可能被中断访问),使用spin_lock_irqsave()和spin_lock_irqrestore()。
    *

      避免任何持有自旋锁超过5行代码的情况,避免任何跨越函数调用的只有自旋锁的情况。(有种情况例外,比方象readb这样的原子访问)

5.1. 加锁最低要求表


下面的表列出了在不同上下文中加锁时的最低要求。在一些情况下,同一个上下文在给定时刻只能在一个CPU上执行,因此不需要锁(例如,某个线程在给定时刻只可能在一个CPU上运行,但如果它需要跟另一个线程共享数据,就需要锁了)

记住上面的建议:你可以总是只用spin_lock_irqsave(),它是其它加锁原语的超集。


表 5-1. 加锁的要求
table51.png

论坛徽章:
0
发表于 2005-11-25 17:53 |显示全部楼层
第6章. 常见的例子


让我们一步步看一下一个简单的例子:一个对映射号的缓存(译者案:原文“a cache of number to name mappings”,虚存子系统不熟,恐怕翻译不确)。该缓存保存了对象的使用有多频繁这个数据,当它满了,抛出最少使用的那个。


6.1. 都在用户上下文


在第一个例子中,我们假定所有的操作都发生在用户上下文(也就是,都在系统调用中),所以允许睡眠。这意味着我们可以使用信号量来保护cache和其中的所有对象。下面是代码:


  1. #include <linux/list.h>
  2. #include <linux/slab.h>
  3. #include <linux/string.h>
  4. #include <asm/semaphore.h>
  5. #include <asm/errno.h>

  6. struct object
  7. {
  8.         struct list_head list;
  9.         int id;
  10.         char name[32];
  11.         int popularity;
  12. };


  13. /* 保护缓存、缓存号和其中的对象 */
  14. static DECLARE_MUTEX(cache_lock);
  15. static LIST_HEAD(cache);
  16. static unsigned int cache_num = 0;
  17. #define MAX_CACHE_SIZE 10

  18. /* 必须持有cache_lock信号量 */
  19. static struct object *__cache_find(int id)
  20. {
  21.         struct object *i;

  22.         list_for_each_entry(i, &cache, list)
  23.                 if (i->id == id) {
  24.                         i->popularity++;
  25.                         return i;
  26.                 }
  27.         return NULL;
  28. }

  29. /* 必须持有cache_lock信号量 */
  30. static void __cache_delete(struct object *obj)
  31. {
  32.         BUG_ON(!obj);
  33.         list_del(&obj->list);
  34.         kfree(obj);
  35.         cache_num--;
  36. }


  37. /* 必须持有cache_lock信号量 */
  38. static void __cache_add(struct object *obj)
  39. {
  40.         list_add(&obj->list, &cache);
  41.         if (++cache_num > MAX_CACHE_SIZE) {
  42.                 struct object *i, *outcast = NULL;
  43.                 list_for_each_entry(i, &cache, list) {
  44.                         if (!outcast || i->popularity < outcast->popularity)
  45.                                 outcast = i;
  46.                 }
  47.                 __cache_delete(outcast);
  48.         }
  49. }

  50. /* 对上面函数的调用,这才是信号量发挥作用的地方──译注 */
  51. int cache_add(int id, const char *name)
  52. {
  53.         struct object *obj;

  54.         if ((obj = kmalloc(sizeof(*obj), GFP_KERNEL)) == NULL)
  55.                 return -ENOMEM;

  56.         strlcpy(obj->name, name, sizeof(obj->name));
  57.         obj->id = id;
  58.         obj->popularity = 0;

  59.         down(&cache_lock);
  60.         __cache_add(obj);
  61.         up(&cache_lock);
  62.         return 0;
  63. }

  64. void cache_delete(int id)
  65. {
  66.         down(&cache_lock);
  67.         __cache_delete(__cache_find(id));
  68.         up(&cache_lock);
  69. }

  70. int cache_find(int id, char *name)
  71. {
  72.         struct object *obj;
  73.         int ret = -ENOENT;

  74.         down(&cache_lock);
  75.         obj = __cache_find(id);
  76.         if (obj) {
  77.                 ret = 0;
  78.                 strcpy(name, obj->name);
  79.         }
  80.         up(&cache_lock);

  81. return ret;

  82. }

复制代码


注意我们总是保证在持有cache_lock信号量的情况下对缓存添加、删除和查找操作:缓存结构自身与其中的对象都被该信号量保护起来。这种情况很简单,因为我们为用户拷贝数据,而不允许用户直接访问对象。

这里有一个轻量(而且很常见)的优化:在cache_add中,我们先设置对象的各个域,然后再获取锁。这是安全的,因为没有人能够在我们把对象加入到cache之前就访问它。


6.2. 从中断上下文中访问


现在我们来考虑一下cache_find会在中断上下文中被调用的情况:这个“中断上下文”或者是硬件中断,或者是softirq。我们使用一个timer来从cache中删除对象。

改写了的代码在下面,用标准的补丁形式给出:以-开始的行是被删除了的,以+开始的行是新添加了的。


  1. --- cache.c.usercontext 2003-12-09 13:58:54.000000000 +1100
  2. +++ cache.c.interrupt   2003-12-09 14:07:49.000000000 +1100
  3. @@ -12,7 +12,7 @@
  4.          int popularity;
  5. };

  6. -static DECLARE_MUTEX(cache_lock);
  7. +static spinlock_t cache_lock = SPIN_LOCK_UNLOCKED;
  8. static LIST_HEAD(cache);
  9. static unsigned int cache_num = 0;
  10. #define MAX_CACHE_SIZE 10
  11. @@ -55,6 +55,7 @@
  12. int cache_add(int id, const char *name)
  13. {
  14.          struct object *obj;
  15. +        unsigned long flags;

  16.          if ((obj = kmalloc(sizeof(*obj), GFP_KERNEL)) == NULL)
  17.                  return -ENOMEM;
  18. @@ -63,30 +64,33 @@
  19.          obj->id = id;
  20.          obj->popularity = 0;

  21. -        down(&cache_lock);
  22. +        spin_lock_irqsave(&cache_lock, flags);
  23.          __cache_add(obj);
  24. -        up(&cache_lock);
  25. +        spin_unlock_irqrestore(&cache_lock, flags);
  26.          return 0;
  27. }

  28. void cache_delete(int id)
  29. {
  30. -        down(&cache_lock);
  31. +        unsigned long flags;
  32. +
  33. +        spin_lock_irqsave(&cache_lock, flags);
  34.          __cache_delete(__cache_find(id));
  35. -        up(&cache_lock);
  36. +        spin_unlock_irqrestore(&cache_lock, flags);
  37. }

  38. int cache_find(int id, char *name)
  39. {
  40.          struct object *obj;
  41.          int ret = -ENOENT;
  42. +        unsigned long flags;

  43. -        down(&cache_lock);
  44. +        spin_lock_irqsave(&cache_lock, flags);
  45.          obj = __cache_find(id);
  46.          if (obj) {
  47.                  ret = 0;
  48.                  strcpy(name, obj->name);
  49.          }
  50. -        up(&cache_lock);
  51. +        spin_unlock_irqrestore(&cache_lock, flags);
  52.          return ret;
  53. }
复制代码


注意一下,如果中断原来是开启着的,spin_lock_irqsave会关掉它们;否则(我们已经处在中断服务例程中)就什么也不做。这些函数可以安全地在任何上下文中调用。

不幸的是,cache_add调用了带有GFP_KERNEL标志的kmalloc,这只是在用户上下文才是合法的。我假定cache_add仍然只会在用户上下文中被调用,否则就应该给cache_add添加参数了。(译注:我觉得作者的意思是说,如果打算让cache_add能在中断和用户两种上下文中使用,应该添加一个参数来表达究竟是在哪种上下文中调用的。FIXME)


6.3. 把对象暴露在文件之外


如果对象包含更多的信息,仅仅提供拷贝函数是不够的:其它代码可能会需要保持一个指向对象的指针,例如,不想每次访问它都要先查找。这就产生了两个问题。

第一个问题是,我们采用cache_lock来保护对象,我们必须把这些函数定义为非static的,这样其它文件中的代码才能使用。这使得锁的使用更加技巧化,再也不是在同一地方了。

第二个问题是生命期问题。如果其它结构保留了一个指向我们的对象的指针,它多半期望该指针总是有效的。很不幸,这只在你持有锁时才会得到保证,否则其它人可能调用cache_delete来删除对象──还可能更糟糕,在删除之后又添加了另一个对象,还在原来的地址上。

但是由于只有一把锁,你也不能总持有它,否则其它人就完全无法工作了。

该问题的解决是使用引用计数:每个持有指向对象的指针的人,在他们第一次获得该指针时,递增一次引用计数;当他们使用完毕,递减一次引用计数。谁把引用计数减到了零,就知道可以删除了,于是执行删除操作。

下面是代码:


  1. --- cache.c.interrupt   2003-12-09 14:25:43.000000000 +1100
  2. +++ cache.c.refcnt      2003-12-09 14:33:05.000000000 +1100
  3. @@ -7,6 +7,7 @@
  4. struct object
  5. {
  6.          struct list_head list;
  7. +        unsigned int refcnt;
  8.          int id;
  9.          char name[32];
  10.          int popularity;
  11. @@ -17,6 +18,35 @@
  12. static unsigned int cache_num = 0;
  13. #define MAX_CACHE_SIZE 10

  14. +static void __object_put(struct object *obj)
  15. +{
  16. +        if (--obj->refcnt == 0)
  17. +                kfree(obj);
  18. +}
  19. +
  20. +static void __object_get(struct object *obj)
  21. +{
  22. +        obj->refcnt++;
  23. +}
  24. +
  25. +void object_put(struct object *obj)
  26. +{
  27. +        unsigned long flags;
  28. +
  29. +        spin_lock_irqsave(&cache_lock, flags);
  30. +        __object_put(obj);
  31. +        spin_unlock_irqrestore(&cache_lock, flags);
  32. +}
  33. +
  34. +void object_get(struct object *obj)
  35. +{
  36. +        unsigned long flags;
  37. +
  38. +        spin_lock_irqsave(&cache_lock, flags);
  39. +        __object_get(obj);
  40. +        spin_unlock_irqrestore(&cache_lock, flags);
  41. +}
  42. +
  43. /* Must be holding cache_lock */
  44. static struct object *__cache_find(int id)
  45. {
  46. @@ -35,6 +65,7 @@
  47. {
  48.          BUG_ON(!obj);
  49.          list_del(&obj->list);
  50. +        __object_put(obj);
  51.          cache_num--;
  52. }

  53. @@ -63,6 +94,7 @@
  54.          strlcpy(obj->name, name, sizeof(obj->name));
  55.          obj->id = id;
  56.          obj->popularity = 0;
  57. +        obj->refcnt = 1; /* The cache holds a reference */

  58.          spin_lock_irqsave(&cache_lock, flags);
  59.          __cache_add(obj);
  60. @@ -79,18 +111,15 @@
  61.          spin_unlock_irqrestore(&cache_lock, flags);
  62. }

  63. -int cache_find(int id, char *name)
  64. +struct object *cache_find(int id)
  65. {
  66.          struct object *obj;
  67. -        int ret = -ENOENT;
  68.          unsigned long flags;

  69.          spin_lock_irqsave(&cache_lock, flags);
  70.          obj = __cache_find(id);
  71. -        if (obj) {
  72. -                ret = 0;
  73. -                strcpy(name, obj->name);
  74. -        }
  75. +        if (obj)
  76. +                __object_get(obj);
  77.          spin_unlock_irqrestore(&cache_lock, flags);
  78. -        return ret;
  79. +        return obj;
  80. }
复制代码


我们把引用计数操作封装进标准的‘get’和‘put’函数中。现在我们可以用cache_find返回对象的指针了,它具有引用计数功能。这样,持有对象指针的用户就可以睡眠了(例如,调用copy_to_user把名字拷贝到用户空间。)(译注:最后一句的意思是说,持有对象指针的用户不必象以前那样为了保证指针的合法性就一直持有锁了。引用计数本身跟锁以及是否可以睡眠一点关系都没有)

另一点要注意的是,我说“每个指向对象的指针都应该有一个引用计数”──因此当对象刚被插入到cache中时,其引用计数应当为1。有些不同版本的实现并不使用引用计数,但它们更加复杂。


6.3.1. 为引用计数使用原子操作


实践中,refcnt的类型应该是atomic_t。在include/asm/atomic.h中定义了几个原子操作:这些操作保证了从系统的所有CPU的角度看,都是原子的。因此不需要锁。这种情况下,原子操作要比自旋锁简单的多,尽管复杂情况下使用自旋锁要来得清晰。使用atomic_inc和atomic_dec_and_test来取代标准的加减操作符,再也不用为引用计数上锁了。


  1. --- cache.c.refcnt      2003-12-09 15:00:35.000000000 +1100
  2. +++ cache.c.refcnt-atomic       2003-12-11 15:49:42.000000000 +1100
  3. @@ -7,7 +7,7 @@
  4. struct object
  5. {
  6.          struct list_head list;
  7. -        unsigned int refcnt;
  8. +        atomic_t refcnt;
  9.          int id;
  10.          char name[32];
  11.          int popularity;
  12. @@ -18,33 +18,15 @@
  13. static unsigned int cache_num = 0;
  14. #define MAX_CACHE_SIZE 10

  15. -static void __object_put(struct object *obj)
  16. -{
  17. -        if (--obj->refcnt == 0)
  18. -                kfree(obj);
  19. -}
  20. -
  21. -static void __object_get(struct object *obj)
  22. -{
  23. -        obj->refcnt++;
  24. -}
  25. -
  26. void object_put(struct object *obj)
  27. {
  28. -        unsigned long flags;
  29. -
  30. -        spin_lock_irqsave(&cache_lock, flags);
  31. -        __object_put(obj);
  32. -        spin_unlock_irqrestore(&cache_lock, flags);
  33. +        if (atomic_dec_and_test(&obj->refcnt))
  34. +                kfree(obj);
  35. }

  36. void object_get(struct object *obj)
  37. {
  38. -        unsigned long flags;
  39. -
  40. -        spin_lock_irqsave(&cache_lock, flags);
  41. -        __object_get(obj);
  42. -        spin_unlock_irqrestore(&cache_lock, flags);
  43. +        atomic_inc(&obj->refcnt);
  44. }

  45. /* Must be holding cache_lock */
  46. @@ -65,7 +47,7 @@
  47. {
  48.          BUG_ON(!obj);
  49.          list_del(&obj->list);
  50. -        __object_put(obj);
  51. +        object_put(obj);
  52.          cache_num--;
  53. }

  54. @@ -94,7 +76,7 @@
  55.          strlcpy(obj->name, name, sizeof(obj->name));
  56.          obj->id = id;
  57.          obj->popularity = 0;
  58. -        obj->refcnt = 1; /* The cache holds a reference */
  59. +        atomic_set(&obj->refcnt, 1); /* The cache holds a reference */

  60.          spin_lock_irqsave(&cache_lock, flags);
  61.          __cache_add(obj);
  62. @@ -119,7 +101,7 @@
  63.          spin_lock_irqsave(&cache_lock, flags);
  64.          obj = __cache_find(id);
  65.          if (obj)
  66. -                __object_get(obj);
  67. +                object_get(obj);
  68.          spin_unlock_irqrestore(&cache_lock, flags);
  69.          return obj;
  70. }
复制代码


6.4. 保护对象自身


在上面的例子中,我们都假定对象(除了引用计数)自从创建之后就不会被更改。如果我们希望允许改变name(译者案,指struct object中的name域),有三种可能:

    *

      你可以把cache_lock变成非static的,告诉人们改变name之前先获得锁。
    *

      你也可以提供一个cache_obj_rename函数,该函数先获得锁,然后为调用者改变name。你需要告诉每一个需要改变name的人使用这个函数。
    *

      你也可以用cache_lock只保护cache自身,而使用另一把锁来保护name域。

理论上,你可以把锁的使用细粒度化(fine-grained)到这样的程度:为每个域维持一把锁。实践中,最通用的变体是:

    *

      一把用来保护基础设施(infrastructure.本例中是cache链表)和所有对象的锁。至今为止我们在示例中看到的便是这种情况。
    *

      一把用来保护基础设施(包括对象结构中的链表指针)的锁,另一把放在对象内部,用来保护对象的其它域.
    *

      多把锁来保护基础设施(例如,Hash表的每一个链都用一把锁保护),可能配合使用每个对象一把的锁。


下面是“每个对象一把的锁”的实现:


  1. --- cache.c.refcnt-atomic       2003-12-11 15:50:54.000000000 +1100
  2. +++ cache.c.perobjectlock       2003-12-11 17:15:03.000000000 +1100
  3. @@ -6,11 +6,17 @@

  4. struct object
  5. {
  6. +         /* 下面两个域,由cache_lock来保护 */
  7.          struct list_head list;
  8. +        int popularity;
  9. +
  10.          atomic_t refcnt;
  11. +
  12. +        /* Doesn't change once created. */
  13.          int id;
  14. +
  15. +        spinlock_t lock; /* Protects the name */
  16.          char name[32];
  17. -        int popularity;
  18. };

  19. static spinlock_t cache_lock = SPIN_LOCK_UNLOCKED;
  20. @@ -77,6 +84,7 @@
  21.          obj->id = id;
  22.          obj->popularity = 0;
  23.          atomic_set(&obj->refcnt, 1); /* cache本身占一个引用计数 */
  24. +        spin_lock_init(&obj->lock);

  25.          spin_lock_irqsave(&cache_lock, flags);
  26.          __cache_add(obj);
复制代码

注意我的策略是popularity域由cache_lock来保护,而不是每个对象一把的锁。这是因为它(就象对象内部的struct list_head域一样)在逻辑上是属于基础设施的一部分的。这样,当在__cache_add查找最少使用的对象时,我就不必去获取每个对象一把的锁了。

这个策略还有一处要注意:id域是不可更改的,这样我就不必在__cache_find()时去获取每个对象一把的锁来保护它。每个对象一把的锁,在这里,只是被调用者使用来保护name域的读和写。

另外,注意我在注释里说明了哪些数据由哪些锁来保护。这是非常重要的,因为它描述了代码运行时的行为,(倘若不加注释)仅仅靠阅读代码是很难获得认识的。这正如Alan Cox所说,“锁是用来保护数据的,而非代码。”

论坛徽章:
0
发表于 2005-11-25 17:55 |显示全部楼层
第7章. 常见问题


7.1. 死锁: 简单与高级


当一段代码试图两次获取同一把自旋锁时,就出现了BUG:它将永远自旋,等待着锁被释放(自旋锁、读写自旋锁和信号量在linux中皆是非递归的)。这很容易诊断:它并非是一个类似“呆上五夜来谈清楚毛绒绒的兔子身上有多少根毛的编码问题”(译者案:原文是stay-up-five-nights-talk-to-fluffy-code-bunnies ,没法翻译啊)之类的问题。

试想一个稍微复杂一点的情况,假设你有一个softirq和用户上下文共享一片区域。如果你使用了spin_lock()来保护它,很可能用户上下文持有锁时被这个softirq打断,然后softirq尝试获得该锁──但它永远也不会成功。

这些情形称为死锁。如同上面展示的那样,它甚至会在单CPU机器上发生(尽管不会在编译时没选上SMP的机器上发生。因为如果编译时CONFIG_SMP=n,自旋锁就消失了。这种情况下你会造成数据腐败)。

这种死锁容易诊断:在SMP机器上,看门狗(watchdog)timer或者编译时加入DEBUG_SPINLOCKS (include/linux/spinlock.h)会在发生死锁时立即显示它。

更复杂的问题是一种叫做“致命拥抱”的死锁,它涉及到两把或更多的锁。比方你有一个Hash表:表中的每一个项是一个自旋锁和一个对象链表。在softirq处理函数中,你可能会想更改某个对象在Hash表中的位置,从某个位置到另一个:你获得了旧的Hash链表的自旋锁和新的链表的自旋锁,然后从旧的链表中删除对象,插入到新的链表中。

这里有两个问题。第一,如果你的代码试图把对象移动到相同的链表中,它就会因两次尝试获取同一把锁而死锁;第二,如果在别的CPU上运行的同一个softirq试图把另一个对象从你的目的链表移动到你的源链表中,下面的事情就发生了:


Table 7-1. 顺序

CPU 1
       

CPU 2

获取锁 A -> OK
       

获取锁 B -> OK

试图获取 B -> spin
       

试图获取 A -> spin

这两个CPU将永远自旋,等待着对方释放自旋锁。它会使系统看起来象崩溃了一样。


7.2. 防备死锁


教科书告诉你说:总是以相同的顺序获取锁,你就不会造成死锁了。而实践则会告诉你,这种方法不具有扩展性:当我创建一把锁的时候,我对内核的理解还真不足以计算出在5000种锁的层次中,哪一种合适。

最好的锁是被封装了的:它们不会暴露在头文件中,不会被它所在文件之外的函数持有。你可以读一下这种代码,来看看为什么它永远不会死锁。因为它持有一把锁时,是决不会试图去获取另一把的。使用你的代码的人甚至不需要知道你曾经使用了锁。

一个经典问题是当你提供了回调函数或钩子函数:如果你在持有锁的情况下调用它们,你将冒死锁的危险:简单死锁或致命拥抱(谁能预知回调函数将会干些什么?)。记住,别的程序员是极度想得到你的(原文:the other programmers are out to get you,实在不懂如何翻译才好;-( ),所以不要这样做。


7.2.1. 对死锁的防备过当


死锁诚然会带来问题,然而不如数据腐败(data corruption)之甚。试想这样的一段代码,它获取一把读锁,搜索一个链表,如果没找到想要的数据,就释放掉读锁,然后获取一把写锁,把对象插入到链表:这样的代码存在竞态问题。

如果你看不出为什么,那就请离我的代码他妈的远点儿。


7.3. 竞态Timers: 一次内核游戏


Timers会造成它们独有的竞态条件。考虑一个对象集合(链表,Hash表等),每个对象都有一个timer,该timer负责销毁它所属的对象。

如果你打算销毁整个对象集合(例如模块卸载的时候),你可能会这样做:


  1.         /* 这段代码太太太太太糟糕了:如果想更糟糕的话,你还可以使用“匈牙利命名法”
  2.          */
  3.         spin_lock_bh(&list_lock);

  4.         while (list) {
  5.                 struct foo *next = list->next;
  6.                 del_timer(&list->timer);
  7.                 kfree(list);
  8.                 list = next;
  9.         }

  10.         spin_unlock_bh(&list_lock);
复制代码

在SMP机器上,这段代码早晚要导致崩溃。因为一个timer可能在spin_lock_bh()之前已经gone off了,它将只有在我们调用spin_unlock_bh()之后才成功的获取锁,然后试图去释放掉响应的元素(而元素已经释放掉了!)

这个问题可以通过检查del_timer()的返回值来预防:如果返回1,说明timer已经被删除了;如果返回0,说明(在这个例子中)它正在运行。所以我们应当这样:


  1.         retry:  
  2.                 spin_lock_bh(&list_lock);

  3.                 while (list) {
  4.                         struct foo *next = list->next;
  5.                         if (!del_timer(&list->timer)) {
  6.                                 /* Give timer a chance to delete this */
  7.                                 spin_unlock_bh(&list_lock);
  8.                                 goto retry;
  9.                         }
  10.                         kfree(list);
  11.                         list = next;
  12.                 }

  13.                 spin_unlock_bh(&list_lock);
  14.    
复制代码

另一个常见问题是那些自启动的(通过在timer的函数的最后调用add_timer()就会实现定时器的自启动 )timers的删除操作。这是一个很常见的易导致竞态的情形,你该使用del_timer_sync() (include/linux/timer.h)来处理这种情况。该函数的返回值是:我们要删除的timer最终被停止自启动之前,删除动作应该执行的次数。


7.4. 混乱的Sparc处理器


Alan Cox说:“在sparc机器上,中断的禁止/激活动作处在寄存器窗口中”。Andi Kleen说“当你从另一个函数用标志(译注:flag, 指如spin_lock_irqsave时的第二个参数)恢复寄存器状态时,就会弄乱所有的寄存器窗口”

所以永远不要把由spin_lock_irqsave()保存的标志传递给另一个函数(除非它被声明为inline的)。通常没人会这么干,但你能记住这点最好。David Miller在直接方式下无法做任何事情。(我敢这么说,是因为我有印象他和一位PowverPC维护者在对待折衷点问题上态度是什么样子的。)
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

基于案例的 SQL 优化实战训练营

讲师:中电福富特级专家梁敬彬,参与本次课程培训,你将收获:
1. 能编写出较为高效的 SQL;
2. 能解决70%以上的数据库常见优化问题;
3. 能得到老师提供的高效的相关工具和解决方案;
4. 能举一反三,收获不仅仅是 SQL 优化。
现在购票享受8.8折优惠!
----------------------------------------
优惠时间:2019年3月20日前

大会官网>>
  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP