Linux 内核设计模式（二）
上周我们讨论了说明内核设计模式的重要性，并且观察了围绕参考计数器的设计模式。这周我们会着眼于关于编码的一个非常不同的方面，看看为什么内核有特殊需求以及这些需求是怎样通过成功的方法实现的。今天在“显微镜”下的话题是复杂数据结构。
说到“复杂数据结构”，我们的意思是那些由不同数量简单对象组成的对象，可能是一个同构的集合，也可能一个异构的集合。总体来说，对象可以加到这个结构中来，也可以从中移除，也可以在其中找到。当我们在编程入门课程中研究这些结构时，处理这样数据结构的首选方式是使用抽象数据类型。
抽象数据类型背后的想法是封装整个数据结构的实现，并且只是提供一个定义良好的接口来让别人进行操作。这种方法的好处在于它提供了一个干净的分离，数据结构在实现时可以不知道哪个应用程序最终用到它，应用程序在实现时也可以不知道数据类型的实现细节。两方面都只是基于接口编程，接口就像一个合同，它明确地阐述需要什么和可以期望实现什么。
另一方面，这种方法的代价之一与接口的抽象本性密切相连。抽象一个接口的意义就是移除不必要的细节，这对于入门的计算机学生来讲很好，但是对于内核程序员来说很糟糕。在内核编程中，性能非常重要，其重要性紧随正确性和可维护性，有时还会排在可维护性之前。在内核中，不是所有的代码路径性能都很重要，但是许多是重要的，在性能重要和不太重要的路径中都使用相同的数据结构，开发过程可以从中受益。所以，数据类型不是过分抽象是至关重要的，但是实现的所有细节都是可见的，那么程序员在使用它们的时候就可以做出最优选择。
所以，内核中数据结构的首要原则就是不要隐藏细节，要想了解这是怎么应用的，以及从中发现更深入的原则来提取模式，我们将会在Linux内核中探讨几个更加成功的数据类型。
开门见山，我们探讨的第一个数据类型是双向链表，这些链表在一个单独include文件<linux/list.h>中实现。任何支持程序的库的文件都没有“.c”分隔。使用内联函数，所有处理链表的代码都实现得足够简单。因此，在任何其他(GPLv2-licensed)项目中使用该实现都很容易。
“list.h”表中有两个方面值得注意，因为它们都指向可能的模式。第一个是struct list_head，它不仅仅是表头，也是表中项的锚点，你的作者已经观察了其他链表的实现，这些实现要求：在任何数据结构中，第一个和第二个元素要存储为表的“后一个”和“前一个”指针，所以通用的表代码可以在各种各样不同的数据结构中使用。Linux内核表不受上述限制，list_head结构可以在数据结构的任何位置嵌入，而且来自那个结构的大量实例的list_head可以链接到一起。使用list_entry()宏，其中包含的结构可以从->next 或者 ->prev指针中找到。
这种方法至少有两个好处。其中之一是程序员仍然完全掌握结构域的位置，以防他们需要把重要的域紧密放到一起来促进缓存利用。另一个是只是通过设定多个struct list_head域，结构很容易位于两个或多个非常独立的表上。
在Linux内核中，这种把一个结构嵌入另一个的实践和使用container_of()（这是list_entry()的通用形式）从child结构中得到parent是很常见的，而且有点让人想起面向对象编程。容器就像是嵌入结构的子类型。
其他list.h的值得注意的方面是“for_each”宏的扩散——该宏让遍历列表再反过来看每一项变得容易。这种宏一共有二十个（rculist.h中的四个没算在内，为了简洁，我选择了忽略）。
我们有时想要反向遍历列表（跟随“prev”链接），有五个宏向后走，有十五个宏向前走。
我们有时想要在列表中间开始，在从该位置“继续”，所以我们有四个“继续”宏和三个“来自”宏，“来自”宏在用程序解释起始点方面稍有不同。
我们有时想要用到目标数据结构中嵌入的struct list_head，但是我们真的经常想要使用list_entry()来得到封闭结构；我们发现，如果“for_each”宏为我们做这件事是最简单的，它提供了“for_each”宏的“进入”版本，一共有十三个版本（占整个二十个的一半以上）。
至于更微妙的原因，我们有时想要能够删除“当前”项，同时无需担忧遍历整个列表，这要求提供“this”入口之前就获取到“next”指针的一个副本，指针要在入口处进行操作，因此会产生八个“safe”宏。链表的“ADT”风格实现很有可能只提供了“safe”版本，以便隐藏这些细节。但是，内核程序员不想为额外步骤浪费存储空间或者精力，在常见案例中，是不需要上述步骤的。
那么实际上我们确实有两种稍微不同的链表，常规链表用struct list_head作为链表头，这种结构包括一个指向起始位置的指针和一个指向末尾的指针。在一些用例中，无需找到列表的末尾就能够将列表头尺寸减半是非常有价值的，其中一种典型用例就是哈希表，其中所有这些头都需要进入一个数组中。为了满足上述要求，我们有一个hlist，它与常规列表非常相似，不同之处在于struct hlist_head中只需要一个指针。这可以解释六种不同的“for_each”宏。
如果我们有以下的每种可能的组合：正向或反向，继续或者停止，进入或退出，安全或不安全，常规或hlist，我们就会有三十二种不同的宏。实际上，只需要其中的十九种，而且只有这十九种已经被编码了。我们当然可以编码剩下的十一个，但是写从来都不会用到的代码还是让人头疼，这种事还从未发生过。
善于观察的读者可能已经注意到上面一些数字中存在小矛盾。在二十个宏中，有一个不符合上述模式，它最初是说明内核程序员评价性能的。这个最终“for_each”宏是__list_for_each()。其他所有宏都用“prefetch”函数来表明CPU在每次迭代开始时开始传递->next指针，所以当下一次迭代开始时指针在缓存中已经是可用的了（尽管“safe”宏实际上是fetch而不是prefetch）。尽管这通常会提升性能，但在一些情况下它也会使运行变慢。当遍历列表几乎总是中止非常早时——通常只是考虑第一项——prefetch通常会成为浪费的部分。在这些情况下（目前全是在网络代码中），__list_for_each()宏是可用的，它不会prefetch任何内容。所以有非常严格性能要求的人可用有更好的机会来获取到他们想要的性能。
嵌入锚: 在一个数据结构中包含通用对象的好方法是在其中嵌入一个锚，之后围绕锚点建立数据结构，使用container_of()可以从锚中找到对象。
宽泛接口: 不要沉迷于考虑“万全之策”的陷阱，有二十个或者更多的宏做同一件事是很不常见的事，它可能是找到最优解的处理复杂性的一种非常合适的方法。尝试把所有可能性都挤到一个接口中的做法效率很低，而且选择不为接口提供所有可能性会起到反作用。拥有所有可用的排列可以鼓励开发者为工作使用正确的工具，而不是选择妥协。在2.6.30-rc4中，list_for_each_entry()有近三千种用法，list_for_each_entry_safe()有大约一千种用法，list_for_each()有近五百种用法，剩余的加起来不到一千种。但事实是那些很少使用的方法一点也没有因此降低其重要性。
我们下一个数据结构是红黑树，这是一个半平衡的二叉查找树，通常查找、插入和删除操作的时间复杂度是“log(n)”。它在<linux/rbtree.h>和lib/rbtree.c中有实现，它与list.h表有很强的相似性，因为它在每个数据结构中都嵌入了一个锚点(struct rb_node)而且由这些锚点建立树。
关于红黑树的需要注意的有趣点是：不存在搜索函数。搜索一个红黑树是非常简单的操作，而且几行代码就可以实现，如顶端rbtree.h中的例子所示。一个搜索函数肯定是可写的，但是开发者选择不写，主要的原因是性能，这可能也不会太令人惊讶。为了写一个搜索函数，你需要把“compare”函数传递到搜索函数中，要在C中做这件事，你需要传递一个函数指针。因为比较函数通常非常简单，下方函数指针和函数调用的代价通常会淹没做比较本身的代价。结果是：把整个搜索操作编译为一个函数会产生更高效的代码，相同的性能也可以通过使用内联函数或者宏实现，但是假如搜索函数本身太短了，这样做看起来不怎么值得。
注意，红黑树实际上也不提供插入函数。开发者需要编写搜索操作；如果搜索失败了，新的节点必须插在没找到它的那个地方，而且树必须重新平衡。对于这种最终插入和重平衡有现成函数，这些函数确实足够复杂，值得把它们分隔开成几个函数。
通过给开发者提供搜索和一些插入的职责，红黑树库实际上给出了很多有价值的自由。“搜索一个入口，如果没找到就插入个新的”模式非常常见，但是在“搜索”和“添加”阶段间发生事情的细节不总是相同的，所以没有什么内容是可以很容易编入库中的。通过提供基础工具，把细节留到特定情况，红黑树的用户就会发现他们解脱束缚了，而不是努力与一个几乎不会做他们期望事情的库抗争。
所以这个红黑树的例子重新加强了“嵌入锚”的模式，并且显示了一种模式，这种模式提供的工具有时比提供整个解决方案还要有用。在这个案例中，提供了插入、移除和重平衡所需的基本数据结构和工具，但是整个解决方案始终需要调整来适应每个案例。
这种模式也描述了针对哈希表的内核方法，这些是非常常见的数据结构，但是这与最后的实现看起来不那么一样。hlist和数组的基本建造块和一些用于计算哈希(<linux/hash.h>)的通用函数都是可用的，将这些联系到一起来来满足给定的目标是取决于开发者的。
因此，我们有了另一种模式：
工具箱: 有时不为通用服务提供完整解决方案是最好的选择，而不是提供一整套能用于建立自定义解决方案的工具。
我们最后一种数据结构是基数树。Linux内核实际上有两种基数树实现。其中一种在<linux/idr.h> 和 lib/idr.c中，另外一种在<linux/radix-tree.h> 和 lib/radix-tree.c中。两者都提供了数（unsigned long）到任意指针（void *）的映射，尽管基数树也允许两个“tag”和每个入口一起存储。为了这篇文章的目标，我们将只会着眼于其中一种实现（你们的作者最熟悉的那种）——基数树实现。
基数树遵照我们在list.h中看到的模式，这种模式有多个接口，而不是试着把大量需求打包到一个接口中。list.h有二十个“for_each”宏；基数树有六个“lookup”函数，取决于我们是只想要一项还是一个范围（gang lookup），或者取决于我们是否想要标签来限制搜索（tag lookup），也取决于我们是否想要找到指针存储的位置，而不是存在那的指针（页缓存微妙的锁定策略需要）。
但是基数树没有遵照之前数据结构的嵌入锚模式，那就是这有趣的原因。对于列表和红黑树，处理数据结构所需的存储实际上是与数据结构中项的数量成一比一比例的，所以在那些项中保留存储效果非常好。对于一个基数树，所需的存储是一些小数组，每个数组参照一些项。所以在每一项中嵌入这些数组不会有效果，这意味着：与list.h和红黑树不同，基数树有时需要分配一些内存，目的是为了能够在数据结构中添加项，这有一些有趣的结果。
在之前的数据结构中（列表和红黑树），我们没有提到锁。如果需要上锁，那么数据结构的用户很有可能了解详细需求，所以所有的锁的细节都留给了调用者（我们称之为“调用者锁定”，与“被调用者锁定”相反，调用者锁定更常见而且普遍更受欢迎）。这对于列表和红黑树来说很好，因为它们在内部做的事没有特别受锁影响的。
如果需要内存分配，那就不是这种情况了。如果一个进程需要分配内存，很有可能它需要在内存管理子系统向存储区写数据的时候休眠，为的是让内存可用。有各种各样的锁（如自旋锁）可能不会在进程休眠时保留，所以在内部为基数树代码分配内存的需求和在外部为基数树代码保留锁之间，有可能有重要的交互。
对于这种问题明显的及方案（一旦已经理解了这个问题）是在接管锁之前预分配内存需要的最大数量。这是通过基数树内部的radix_tree_preload()函数实现的，它管理可用红黑树节点的每个CPU池，并且确保池子是满的而且不会被任何其他基数树操作使用。因此，把radix_tree_insert()和radix_tree_preload()以及radix_tree_preload_end()的调用括在一起可用确保radix_tree_insert()调用不会由于缺少内存而失败（尽管radix_tree_preload()可能会失败），这样一来在锁定方面就不会有不愉快的交互了。
那么我们现在可以总结我们已经发现的设计模式列表了，这些设计模式在内核中与数据结构（和其他部分）搭配的效果很好，为了完整性，那些已经详细说明的部分也在该表中简要说明了。
嵌入的锚。
这对于列表非常有用，如果你探究了对象，锚也可以被泛化并且可见（留给读者的练习）。
宽泛接口。
这提醒我们：尝试把大量用例挤到一个函数调用中是不必要的——应该就提供大量函数调用（这些调用应该有有用的、（希望是）一致的名字）。
工具箱。
有时最好不要为通用服务提供完整解决方案，而是应该提供一系列工具，这些工具可以用于建立自定义解决方案。
调用者锁。
当有任何怀疑时，选择让调用者管理锁而不是被调用者，这会把更多的控制权给予函数的用户。
预分配外部锁。
这在某种程度上非常明显，但是它在内核中用得非常广泛，所以详细阐述它是个好主意。
下周我们会完成我们对于内核设计模式的探究，主要通过看得更高，并且着眼于一些与整个子系统设计相关的模式。
对于那些想要进一步探索这些思想的人，这里有一些出发点。
通过探究所有“container_of”宏的用户，为所有已经被嵌入的数据结构列个表。在这些表中，将都在相同结构中嵌入的对儿列个表（建模多个继承），评论这是如何影响多个继承的一般用途。
写一个的实现，它对于内置内核使用很适合。考虑文章中讨论的每个模式的应用性，利用list.h列表有额外奖励。
Linux包括一个mempool库，基数树选择不使用这个库，它更细化自己的简单池（在radix_tree_preload中）。检验改变基数树的结果来使用mempool，在基数树或者模式中恢复这个设计选择，进而解释这个设计选择。
比较基数树和idr的实现来观察是否一个人可以无需牺牲正确性、可维护性或者性能来选择其他方式实现，提供为什么它们应该分隔开的解释，或者提供一个补丁来用一个替换另一个。
【版权声明】
原文作者未做权利声明，视为共享知识产权进入公共领域，自动获得授权；
近期热文