下载掌阅APP，畅读海量书库
立即打开
内核数据结构与用户端的数据结构并没有理论上的不同，但是内核数据结构通常比用户端的数据结构更加注重性能和内核业务场景。
链表既有弹性，又能在弹性伸缩的过程中保持已有的内容不变。链表可以把在离散时间到达的数据结构串起来，使其更容易被索引，并且不需要移动之前的内容，但缺陷是数据在内存中是离散的，不利于CPU cache加速和批量管理。
内核哈希表是由链表群组成的，每一个哈希桶（即每一个哈希的值位置）都是一个链表。哈希表有很多种实现方法，不同实现方法的主要区别就在于处理哈希冲突的方式。在内核中采用的是开链的哈希表，主要使用双向链表，而这个链表在做开链哈希桶时要有针对性地优化：使头部节点只占一个指针的大小。
总体来说，哈希表是一个大数组，数组的索引就是哈希的结果，但是这样可能会出现多个值对应同一个索引值的问题，所以所有的哈希表都需要解决哈希（值）冲突的问题。针对解决哈希冲突的方法可以将哈希表分为三种：开链哈希表、多级哈希表和布谷鸟（Cuckoo）哈希表，下面对这三种哈希表进行详细介绍。
（1）开链哈希表，使用链表来解决冲突，这是在Linux内核中采用的方法，也是在实际使用中最常见的方法。由于哈希表具有稀疏的特征，所以并不是所有的哈希桶（bucket）都存在内容，但不存在内容时根本不需要哈希表的存在。bucket的值可以直接设置为NULL，这就要求所使用的链表的头部尽可能只占一个指针的位置，这就是hlist的概念，是一个头部只占一个指针大小的特殊双向哈希表。
（2）多级哈希表，一般用在性能非常敏感的场所，例如，华为方舟编译器的vtable的实现就采用了二级哈希表，一级哈希表是32个slot的数组，若对索引到同一个bucket的不同值进行一次再哈希，则在数组前面的31个slot中使用二次哈希的值作为索引来存放内容。如果发现经过二次哈希的结果仍然发生冲突，就在最后一个slot的位置进行特殊标记，然后重新生成一个二级哈希，在二级哈希中解决冲突，但二级哈希会发生冲突的概率很小，所以二级哈希一般使用链表即可。这样做的好处是，在大部分情况下，一级哈希不需要遍历链表，而是一个直接的索引，性能非常好。
（3）布谷鸟哈希表，这种哈希表曾经在DPDK中被广泛应用，它的原理是每个bucket都是一个数组，索引的结果在数组中进行再哈希，只是当二级哈希出现冲突的时候，布谷鸟哈希表不进行额外的内存申请，而是到其他的bucket中寻找是否存在可用的空的位置。布谷鸟哈希表的特点是需要的内存大小是固定的，在使用文件作为哈希表的存储介质时，可以直接映射文件到内存以加载哈希表。
在这三种哈希表中，性能最好的且可以最大程度实现无锁的是多级哈希表，跨进程共享首选布谷鸟哈希表，最节省内存的是开链哈希表。
双向链表很容易做成一个环，即将起始的prev域设为最后一个数据，将最后一个数据的next设为起始数据。在include/linux/list.h中实现的双向链表的节点不包含实际的数据域，而在具体的数据结构中包含链表的节点。
理论上链表功能是数据结构功能的一部分。当一段代码拿到一个数据结构的实例后，就可以通过访问其中的链表域来确定其链表情况。在使用链表定位到某一个实例后，就可以使用container_of宏定位到这个结构体本身。container_of宏的作用是在已知结构体某个域的指针的情况下，求出结构体实例的指针，其原理是根据结构体定义得出已知指针的偏移，用已知指针减去这个偏移就是结构体的指针，代码如下。
container_of宏并不只用于链表节点到真实数据结构体的映射，也可以在其他域使用。双向链表的节点定义如下。
这个双向链表的核心是一个头部，其与用户端链表的显著不同是没有数据域。
在时钟源管理中（kernel/time/clocksource.c），也是通过链表对所有的可用时钟进行管理的。一个list_head是两个指针的大小，对链表的初始化定义如下。
相当于定义了：
也就是定义并初始化了clocksource_list这个双向链表。添加一个时钟源到链表，代码如下。
首先，遍历这个链表，由于链表本身只是struct list_head类型，其中的节点也是struct list_head类型，因此在遍历的时候使用list_for_each_entry，通过第一个参数传入struct clocksource *，就可以让每个遍历得到的entry的类型都转换为struct clocksource *，在遍历的逻辑中就可以直接使用struct clocksource *类型的变量来进行处理。然后，通过对tmp->rating与cs->rating进行大小对比，找到第一个比cs->rating小的时钟源，跳出遍历循环，在第一个比cs->rating的值小的位置进行插入，从而就实现了一个以rating的大小为维度的排序链表。
也就是说，clocksource_list是一个struct clocksource *类型的双向排序链表，却只使用了一个简单的struct list_head为基本单位组织的双向链表结构。以struct list_head为基本单位的双向链表结构就是Linux内核提供给其他组件的基础双向链表数据结构，以下代码是list遍历的定义。
list_for_each_entry的实现过程就是，遍历通用类型的链表，对每一个元素都使用container_of宏进行类型转换。整个过程的核心是向container_of宏传入链表在外部结构体中的偏移，也就是第三个参数member在第一个参数ptr中的偏移。对于clocksource_list，使用了list_for_each_entry（tmp，＆clocksource_list，list），也就是传入了list这个域在struct clocksource中的偏移，所以在struct clocksource中必然存在一个叫作list的域，定义方式是struct list_head list，否则就无法从链表得到外部的struct clocksource指针。