下载掌阅APP，畅读海量书库
立即打开
链表之所以被称作链表，是因为它的弹性不动属性。它可以把离散时间到达的数据结构串起来，使其可以更容易地被索引，并且不需要移动之前的内容。内核哈希表是由链表群组成的，其每一个哈希桶（每一个哈希的值位置）都是一个链表。高性能的哈希表有很多种实现方法，例如DPDK里就有几种现成的，但是后来被DPDK所采用的用来处理哈希冲突的Cuckoo Hash算法，却只能保证哈希表使用率较低的情况下的高性能，换句话说是相对不可控的，这显然与Linux的需求不相符。内核中采用的是开链的哈希表，但是Linux内核中全部使用双向链表，而这个链表在应用到哈希表做开链哈希桶时要有针对性的优化。
双向链表很容易做成一个环，将起始的prev域设为最后一个数据，将最后一个数据的next设为起始数据。一般链表的设计思路是以链表节点为主体，一个双向链表节点的数据域一般包括prev、next与data。然而这样设计的一个明显缺点就是当一部分代码要处理链表的一部分数据时，其拿到的永远是链表的节点，要操作里面的数据代码需要通过节点索引到具体的数据位置。如果这种代码块很多，那么每次都要进行索引操作，这对于代码的“整洁性”就是败笔。
Linux采用了一个取巧的做法（include/linux/list.h），即双向链表的节点不包含实际的数据域，而是数据结构中包含链表的节点。理论上链表功能是数据结构功能的一部分。当一段代码拿到一个数据结构的实例后，就可以通过访问其中的链表域来确定其链表情况，使用链表定位到某一个实例后就可以使用container_of宏定位到这个结构体本身。
container_of宏的作用是已知结构体某个域的指针，求出结构体实例的指针。原理是根据结构体定义得出已知指针的偏移，用已知指针减去这个偏移就是结构体的指针。代码如下。
因此这个container_of并不只用于链表节点到真实数据结构体的映射，其他域都可以使用。代码如下。
这个双向链表的核心是一个头部，其与用户端链表的显著不同是并没有数据域。
双向链表的缺点是如果有很多特别短的链表时（很可能只有一个节点），双向链表的next和prev的头部就非常占用空间。典型的是哈希表，我们知道哈希表使用哈希函数计算得到一个地址，然后直接访问该地址的机制实现快速访问，但是哈希算法不可避免地会有哈希冲突（多个输入产生了同一个地址输出），此时解决哈希冲突的方法就是使用哈希桶，一般在同一个计算地址的位置实现一个链表，该链表链出所有哈希结果为本地址的值。
通常情况下，哈希表大部分的域都是空白的，而哈希表所需要的大小却要提前分配，只有每个哈希桶的链表才可以动态分配。一个双向链表的头部有两个指针的大小，如果这两个指针全部放入哈希表要提前分配空间，就会比单链表消耗多一倍的内存空间。所以内核专门设计了hlist，拥有只有一个指针大小的头部的双向链表。如图3-1所示。
图3-1
哈希链表本质上也是双向链表，但是组织方式与双向链表并不完全一样。代码如下。
Linux双向链表是环形的，而hlist有特定的头部结构。其头部只有一个first域，用来指向第一个节点（一个头部只有一个整数大小）。而第一个节点和后续的节点的结构都是一样的，只是第一个节点的next和pprev都是指向头部的first域。后续节点的next指向的是下个节点的next域（就是下一个节点的地址），而pprev指向的是上一个节点的next域。在整个链表的设计中，与双向链表的不同有两处，即头部和pprev。而pprev本质上又和双向链表的prev是一样的，都是指向上一个链表数据结构的地址。代码如下。
这么做其实是为了适应头部设计而引入的带“副作用”的解决方法。我们前面讨论过之所以要设计头部为一个整数大小的原因（哈希桶的空间利用率），而这个头部的引入，导致了第一个节点和后面节点的不同。为此所有相关的操作（添加、删除、遍历等）理论上都得特别照顾第一个节点（多一个特殊情况判断）。如果能从数据结构设计上将这种特殊情况去掉无疑是最好的，hlist的设计做到了这一点。其pprev（对应于双向链表的prev）并不是指向上一个节点的数据结构，而是指向上一个节点的next域。这对于头部节点来说，hlist_head结构体的first域既是指向下一个节点的指针，也是下一个节点的上一个节点位置（通过pprev指向），如此就能让第一个节点和后续的节点对所有操作展现出几乎一样的接口。
该数据结构存在的原因是系统运行时会产生内存碎片，为了利用内存碎片传送大数据，在DMA支持分离的多块内存同时的传输下，对应产生的软件结构，其表示的是多块分离的块内存。
scatterlist的主要结构体如下。
这里的数据结构的命名与设计不容易理解，但是其组织很高效，核心在page_link域。page_link域指向数据的存储内存页，offset表示其指向的内存在本内存页内的偏移，length表示其指向的内存空间的大小（可以大于一个页）。scatterlist的数组称为scatterlist table。
Linux允许两个scatterlist被连接起来，构成一个更大的scatterlist（如果多次调用，就可以连接起很多个scatterlist）。级联可以使用该结构体的page_link域。page_link不论是指向一个page页地址、一个scatterlist结构体，还是指向存储的页地址，其最后两位因为对齐原因理论上都是0（可用的不止两位，但只用了两位）。所以就可以使用最后两位来区别前面的地址到底是页地址还是scatterlist地址：01表示地址指向的是scatterlist（级联情况）；10表示后面没有级联的节点了；00表示page_link指向的是存储的页地址。
当一个scatterlist结构体用作级联时，该结构体内的其他域都为0，表示该节点不指向任何可用的存储空间，而只是用来连接下一个scatterlist table的桥梁。代码如下。
sg_table是对scatter_list的总体概括，内含了scaterlist、一个map之前的块数目orig_nents，以及一个map之后的块数目nents。这里的map的意义是各个分离的内存有可能恰好相邻，并可以合并。
scatterlist table可以被拼接（chain），如果不同的scatterlist所指向的内存是相邻的还可以被合并，所以其遍历格外复杂。
llist的全称是Lock-less NULL terminated single linked list，意思是不需要加锁的list。在生产者-消费者模型下，如果有多个生产者和多个消费者，生产者意味着链表添加操作，消费者意味着链表删除操作。但有多个生产者或者多个消费者一起操作时就需要加锁，但加锁是高耗费的操作，内核现在流行无锁操作，为这个需求诞生的就是llist。
Linux中断有上半部分和下半部分。上半部分会关闭所有中断，使系统失去响应，为了减少这个时间，上半部分不能休眠，复杂的操作也得放到下半部分执行。也就是意味着上半部分的代码不能使用加锁操作，而中断重入是很容易发生的，这就又诞生了加锁的需求。提高上半部分使用list数据结构能力的最好的方式就是使用无锁llist。代码如下。
内核实现的方法是使用cmpxchg宏。这本来是一个Intel平台的汇编指令，Linux喜欢这个指令，但其他平台不一定有，所以就封装了一个宏，在其他平台重新实现，而Intel平台直接调用cmpxchg指令即可。这个指令是原子的，有3个参数，对比第一个和第二个参数，如果相等则写入第三个参数到第一个参数指向的地址。如果不相等则返回第三个参数。本意是将第三个参数写入第一个参数指向的地址，但是加上对比后在写入之前第一个参数指向的内存就不会被其他任何指令修改，这就确保了在写入操作之前和之后的一致性。具体到llist就是在添加链表节点到头部时，需要确保在修改head->first指针时，没有其他的并行操作也在修改，因为同时修改会造成并发的操作，产生无法预知的后果。所以cmpxchg先读出head->next，然后head->first作为第一个参数，刚读出的head->first作为第二个参数，要添加的新节点作为第三个参数。代码如下。
