[zz]inux Kernel Design Patterns - Part 1

作者：Neil Brown
原文发布日期：June 8, 2009
来源：
译者：王旭 ( , @gnawux )
翻译时间：2009年8月29-30日

内核社区中，始终受到关注的一个话题便是维持代码质量。显而易见，我们需要维护乃至提高内核的质量，不过，如何能更好的做到这一点却不那么显而易见。一个已经取得一定成果的普适方法便是提升内核的各个方面的可见性。这将让这些方面的质量更加透明，进而可以提高它们的质量。

可见性的提高以不同的形式发生：

    * checkpatch.pl 脚本会检查代码的各式风格，将不一致的风格高亮标出，这会帮助（还记得使用这个脚本的）人们来修正代码风格上的错误。这样，通过提高代码风格指南的可见性，我们统一了代码的外观，于是在某种意义上说，提高了质量。
    * 在打开“lockdep”系统时，它可以动态计算锁（以及相关状态，比如是否允许中断等）之间的依赖性。如果有什么东西看起来比较异常的话，它会进行报告。这些异常并非总意味着可能死锁或有类似问题，但很多时候确实如此，而且这种死锁可能性是可以被消除掉的。这样，通过提升锁依赖关系图的可见性，可以提高代码质量。
    * 内核还包含着其他的可见性改进，如对不用的内存空间进行“poisoning（下毒）”，这样非法访问将更为明显，或者通过在 stack trace 中直接使用符号名称替代十六进制地址，从而使得 bug 报告能更有意义。
    * 在更高层面上，用于跟踪内核变化的”git”版本管理系统让观察补丁提交的时间和补丁作者变得十分容易。它鼓励让每个补丁的提交者都附加一个说明，由此可以获知为什么代码应该是这样的。这个可见性可以帮助理解代码，并且由于更多开发者能更好地了解代码的含义，从而可以提高质量。

除此之外，还有很多种方法可以提高其他方面的可见性，从而提高代码质量。在本系列文章中，我们将探讨一个特定的领域，这让作者们可以感到可见性可以发生质的改变的方式改进。这个领域就是阐明内核特定的设计模式。

设计模式

“设计模式”这个概念最早见于建筑学，1994年出版的《设计模式：可重用面向对象软件元素》一书将这个概念引入到了计算机工程，特别是面向对象编程领域之中。Wikipedia上有关于此主题的更加深入的介绍。

简而言之，设计模式描述了一类特定的设计问题，并描述了已经被验证有效的解决这一类问题的方法细节。设计模式的一个特别的好处是，它将问题描述与解决方法的描述结合在一起并进行命名。一个模式具有一个简单好记的名称非常有好处。如果开发者和审阅者都知道一个模式的名字，那么重要的设计决策就可以用一两个词就做到有效沟通，决策问题也就变得非常具有可视性了。

在 Linux 内核代码中，很多设计模式都已经被证实是有效的了。不过，它们中的大多数都还从来没有被文档化过，对其他开发者来说也就不怎么可用了。我的希望就是显式地描述这些模式，让这些模式被更广泛地使用，进而开发者可以更快更有效的解决常见问题。

在本系列文章的后面的部分，我们将考察三个问题域，并从中发现适用范围和重要性迥然不同的各种设计模式。我们的目标不仅是描述这些模式，而且要介绍这些模式适用的范围和所具有的价值，这样，其他人也可以尝试来描述他们遇到的模式。

这个系列中将引用很多 Linux 内核中的例子，因为例子是解释模式的一个重要部分。如无特殊声明，这些例子都取自2.6.30-rc4。

1. 引用计数

使用引用计数来管理对象的生命周期的想法非常普遍。核心思想就是使用一个计数器，当有一个新引用的时候就加一，释放引用的时候就减一。当计数器到达0的时候，这个对象所占用的所有资源（如用于存储它本身的内存）就都可以释放了。

管理引用计数的机制看起来非常直接。不过，实际上有一些微妙之处会使得它非常容易出错。部分基于这个原因，Linux 内核（自从 2004 年）就有了一个“kref”类型和一组相关机制（参考 Documentation/kref.txt, , 和 lib/kref.c）。这些方法封装了一部分微妙之处，特别的，让一个计数器明确地作为引用计数被以一种特定的方式来使用。如上所述，设计模式的名称非常有价值，开发者只提供要使用的设计模式的名字对于审阅者非常有好处。

Andrew Morton 语录：

    我更希望开发者们能这么说：“啊，这里用了kref。这样，我理解它用了 refcounting，我知道它被很好的 debug 了，并且知道它能处理一般的错误了。”这比下面这样强多了：“哦，这个东西实现了自己的refcounting --- 这样我就得在这里对常见错误进行审阅”。

Linux 内核中引入 kref  为其显式支持设计模式既打了一个勾也打了一个叉。勾就是 kref 就是具体实现了一个重要的设计模式，良好的文档化，并在使用的时候使得代码清晰可见。而这个叉则是因为 kref 仅仅封装了部分关于引用计数的内容。有些引用计数的应用并未被 kref 模型所惠及，稍后我们将看到。一个没有提供所需的方法的引用计数具有“blessed”机制实际可以导致错误，因为人们可能会在 kref 不该使用的地方使用它，在实际上它不能工作的地方认为它可以工作。

一种有用的了解引用计数的复杂性的步骤是要了解到，经常有两类截然不同的引用指向某个对象。事实上，可能会有三类甚至更多，但这并不常见，并且可以被理解成为更广义的两类的情况。我们将这两类引用称为“外部的”和“内部的”，虽然有的场合“强的”和“弱的”可能更合适一些。

“外部”引用是指我们最习惯于考虑到的引用。外部引用在“get”与“put”的时候被计数，被管理对象的子系统可被相去甚远的子系统所持有。一个对象的外部引用的存在代表着一个强烈而简单的含义：对象在使用中。

与之相对应的，“内部”引用常常不被计数，它仅在管理对象的系统内部（或与其密切相关的系统内）持有。不同的内部引用具有不同的含义，因此实现的含义也十分不同。

最常见的内部引用的例子是提供“按名称查询”服务的缓存。如果你知道了一个对象的名称，那么只要缓存中确实存在这个对象，就可以通过缓存来得到一个外部引用。这个缓存会在一个列表或一组链表中的一个链表，如一个哈希表中保存每个对象。这个列表中存在的对象实际是一个对对象的引用。但是它却不应该是一个被计数的引用。它不具有“对象在使用中”这样的语义，而仅仅是“当有人想用这个对象的时候，它是可用的”。在所有外部引用被释放之前，对象将一直不会从列表中删除，而且即使所有外部引用都被释放的时候，它也可能不会立刻从列表中删除。内部引用的存在和本意喻示着着引用计数的实现方式。

一个有用的对不同引用计数风格进行分类的方法是通过其所需要的“put”操作的实现来进行区分。“get”方法一般是一样的。它获取一个外部引用，并产生了另一个外部引用。它的实现差不多是这样的：

    assert(obj->refcount > 0) ; increment(obj->refcount);

或者如 Linux 内核中的 C 代码：

    BUG_ON(atomic_read(&obj->refcnt)) ; atomic_inc(&obj->refcnt);

注意，“get”不能被用于一个已经被释放了的对象，还需要一些其他的处理。

“put” 操作有三个变种。尽管在用例上还有一些重叠，但区分这三者对于保持代码的简洁是有好处的。这三种方式以 Linux C 的写法是这样的：

   1      atomic_dec(&obj->refcnt);

   2      if (atomic_dec_and_test(&obj->refcnt)) { ... do stuff ... }

   3      if (atomic_dec_and_lock(&obj->refcnt, &subsystem_lock)) {
                 ..... do stuff ....
         spin_unlock(&subsystem_lock);
      }

2. "kref" 风格

从中间一种方法开始，第2项是 kref 使用的风格。这个风格适用于对象没有其外部引用活得长的情况。当引用计数到达0的时候，对象需要被释放，否则就要进行处理，这就需要使用 atomic_dec_and_test() 来检查引用计数为为0的情况。

符合这一风格的对象通常都不需要顾虑内部引用，大部分 sysfs 中的对象就是这样，它们使用大量的 kref。但如果一个使用 kref 风格引用计数的对象有内部引用，那么它就不允许用一个内部引用来创建外部引用，除非能确定仍有其它的外部引用。如果有此必要，可以使用如下原语：

     atomic_inc_not_zero(&obj->refcnt);

 这样，在计数器不为零的情况下自加，返回值指示操作是否成功。在 linux 内核中，atomic_inc_not_zero() 是一个较新引入的操作，在2005年末作为不加锁的 page cache 的一部分引入。因而，这个原语的使用还不够广泛，一些本可以使用这个原语的代码使用了自旋锁。遗憾的是，kref 包也没使用它。

这样风格的引用有一个没用使用kref 的有意思的例子，甚至连 atomic_dec_and_test()  都没有用（虽然实际可以用并且确实应该用），这就是 struct super 里面的两个引用计数：s_count 和 s_active 。

s_active 非常符合 kref 的风格。超级块的生命周期开始时 s_active 为1（alloc_super() 中设置），并且，当 s_active 变成零之后，就无法再获取外部引用了。这个规则位于 grab_super()，虽然超级块没有立刻被清除。当前的代码（由于历史原因）在 s_active 非零时给加上一个很大的数（S_BIAS），而 grab_super()  去检查 s_count 是否超过 S_BIAS 而不是 s_active 是否为零。后面这次检查实际上可以直接使用 atomic_inc_not_zero()，从而避免使用自旋锁。

s_count 提供了另一类不同类型的引用，既是内部引用，又是外部引用。它的内部。从语义远弱于 s_active 方面说，它是内部引用计数。s_count 引用计数的意思仅在于“超级块还不能立刻被释放”，而不检查它是否真的处于 active 状态。而它却又非常类似 kref 那样，从 1 开始生命周期（实际是 1*S_BIAS），当它到 0 的时候（在 __put_super() 中）超级块就被销毁了，从这个意义上讲又是外部引用计数。

只要进行如下操作，这两个引用计数就可以用两个 kref 所代替：

    * S_BIAS 置为 1
    * grab_super() 使用 atomic_inc_not_zero() 原语，而不是和 S_BIAS 进行比较

这样，很多自旋锁都可以不用了。具体细节可以作为练习留给各位读者了。

3. "kcref" 风格

Linux 内核并没有 “kcref” 对象，但这个名字似乎适用于接下来的这种引用计数风格。“c”是指的“缓存（cached）”，这种风格经常用于缓存之中。所以可以称为 Kernel Cached REFerence。

kcref 引用计数如上面第三种情况使用 atomic_dec_and_lock() 。这是因为，最后一次 put 的时候，需要释放掉资源或检验是否需要其他特定的处理。这需要进行一次加锁来保证当前状态被重新求值期间不会再产生新的引用。

一个简单的例子是 struct inode 中的 i_count 引用计数。iput() 中的主要部分是这样的：

    if (atomic_dec_and_lock(&inode->i_count, &inode_lock))
    iput_final(inode);

其中 iput_final() 检验 inode 的状态，并决定它是否可以被销毁，或是还要留在缓存中，以备稍后重用。

特别的，inode_lock 会阻止从 inode 哈希表中的内部引用建立外部引用。由于这个原因，仅有持有 inode_lock 的时候才能将内部引用转化为外部引用。支持这个操作的函数称为 iget_locked() （或 iget5_locked()）。

略有一点复杂的例子是 struct dentry，这里的 d_count 是用的类似 kcref 的方式管理的。它更复杂一些的原因在于在我们获得引用之前，需要先获取两个锁—— dcache_lock 和 de->d_lock。这要求我们必须先获得一个锁，然后再用 atomic_dec_and_lock() 来获取另一个（如 prune_one_dentry  之中），或者先用 atomic_dec_and_lock() 然后请求另一个锁并重新检查引用计数，如 dput() 中的操作。这是一个很好的例子，它说明了你永远不能肯定你已经封装了所有的可能的引用计数风格。需要两个锁的情况很难被预见到。

一个更复杂的例子是 struct vfsmount 中的 mnt_count。这里的复杂性源于两个引用计数的相互影响：mnt_count 是一个典型的外部引用计数，而 mnt_pinned 是进程审计模块的内部引用计数。特别地，它统计文件系统中打开的审计文件的数量（实际应该使用个更贴切的名字）。复杂性来自于当只有内部引用存在的时候，它们将全被转化为外部引用。关于这个例子的细节同样留作练习，留给感兴趣的读者。

4. "plain"风格

最后一种引用计数涉及到的风格就是直接对引用计数进行减值操作（atomic_dec()）而不做其他任何事情。这个风格在内核中并不常见，必须有充分的理由才会使用。毕竟随意放着一个躺着的对象不是个好主意。

这个风格的一个例子出现在 struct buffer_head 中，位于 fs/buffer.c 和 。非常简单 的put_bh()函数：

    static inline void put_bh(struct buffer_head *bh)
    {
        smp_mb__before_atomic_dec();
        atomic_dec(&bh->b_count);
    }

这样做没什么问题，因为 buffer_heads 有它们自己的生命周期管理规则，他们是紧密和页相关的。一个页面中会分配出一个或多个 buffer_heads，以分成小片（buffer）。它们会被保存着，直到页面本身被释放，这时，所有的 buffer_heads 都会被清除（通过 try_to_free_buffers() 调用 drop_buffers()）。

通常，”plain”风格适用于那些内部引用会一直存在，对象不会丢的情况，这个内部引用的所在的进程会最终找到并释放对象。

5. 反模式（Anti-patterns）

现在要回顾一下这个引用计数来作为设计模式的介绍，我们将要讨论反模式的相关概念。设计模式都是已经经过检验可以工作的方法，并应该鼓励使用，而反模式则是那些已经证明不能良好工作，并应被慎用的。

作者建议把在引用计数中使用”偏置（bias）“作为一个反模式的例子。偏置是一个大数，在引用计数中进行加减，它被用于保存一些信息。我们已经在超级块的 s_count 中见过这种方式了。在这个例子中，偏置的存在表示 s_active  是非零值，这很容易直接检验。所以偏置实际没有任何价值，只是使得代码的真实用意更不清楚了。

另一个使用偏置的例子是 fs/sysfs/sysfs.h 和 fs/sysfs/dir.c 中的 struct sysfs_dirent 。十分有趣，struct sysfs_dirent 和超级块一样，有两个以用，也是叫做 s_count 和 s_active。这里，当选项被去激活时，s_active 有一个大的负数偏置。同样信息可以被有效并更清晰地存储在一个标志字 s_flags 中。在标识中存放一些信息比用偏置的方法存放在计数器中更为易懂，也更应该被推荐。

总之，使用偏置不能增加清晰度，不是一个常用模式。它不能比一个单独的标志位提供更多的信息，极端缺少内存、无法发现其它可用内存的情况下使用偏置来存放信息的情况非常罕见。因此，引用计数中，偏置应该被视为反模式并尽力避免使用。

6. 总结

到时候结束我们对各种引用计数相关的设计模式的介绍了。简单列出如”kref”与”kcref”，”外部“与”内部“引用这样的术语是非常有帮助的。像我们一样找到 kref 和可以用 kcref 的代码，并在所有可用的地方使用它们，这对开发者和审阅者都有好处，开发者可以在一开始就找到正确的方法，而审阅者也更容易知道代码的用意。

我们本文中涉及的设计模式包括

    * kref: 当对象的生命周期仅仅延续到最后一次释放外部引用的时候，kref 是恰当的设计模式。如果对象有内部引用，那么它们只有使用 atomic_inc_not_zero() 才能变成外部引用。例子：struct super_block 中的s_active 和 s_count 。
    * kcref: 如果对象的生命周期超出最后一次释放外部引用，那么应该使用 atomic_dec_and_lock() 和 kcref。内部引用只有在获得了子系统锁的时候才能转化为外部引用。例如：i_count 中的 i_count。
    * plain: 当对象的生命周期挂靠在其他对象之上的时候，应该采用plain 引用模式。对象的非零引用计数必须被看作是对父对象的内部引用，内部引用转化为外部引用必须遵循和父对象相同的规则。例子：struct buffer_head 中的 b_count。
    * biased-reference: 当你想要在引用计数中使用一个大的偏移值来表征一些特殊状态的时候，停下，别这么干。使用个别的标志位吧，这是反模式。

下个星期我们将换一个领域看其中 Linux 内核已经证明了的成功的设计模式，并看一些复杂的数据结构略多的地方。

7. 练习

作者在准备这个系列的时候就被提醒到，没有比直接研究代码更能让人理解这些问题了。所以也给感兴趣的读者留了一些练习。

   1. 使用 kref 在 struct super 中替换 s_active，抛弃 S_BIAS。比较使用 trifecta 进行正确性、可维护性和性能检查的结果 。
   2. 为 mnt_pinned 和处理它的相关函数选择一个更贴切的名字。
   3. 给 kref 库添加一个使用 atomic_inc_not_zero() 的函数，并使用它（或相反的操作）去掉 net/sunrpc/svcauth.c 中使用的atomic_dec_and_lock() ，这里它破坏了 kref 的抽象。
   4. 检查 struct page （如 mm_types.h 中） 的 _count 引用计数，观察它的行为更像 kref 还是 kcref （提示：肯定不是 plain）。这应该包括标记所有的内部引用和相关的锁定规则。指明为什么 page cache (struct address_space.page_tree) 有一个引用计数或为什么不应该有。这将包括理解 page_freeze_refs() 和它在 __remove_mapping() 中的使用，以及 page_cache_{get,add}_speculative()。

补充：一个系列的最小的自包含的补丁来实现上述这些研究结果的改变被证实是有用的。