Linux kernal鬼斧神工，博大精深，让人叹为观止，拍手叫绝。然匠心独运的设计并非扑朔迷离、盘根错节，真正的匠心独运乃辞简理博、化繁为简，在简洁中昭显优雅和智慧，kfifo就是这样一种数据结构，它就是这样简约高效，匠心独运，妙不可言，下面就跟大家一起探讨学习。
在外界看来，Linux内核的内部似乎变化很少，尤其是像内存管理子系统（memory-management subsystem）这样的子系统。然而，开发人员时常需要更换内部接口来解决某些长期存在的问题。比如，其中一个问题就是用来保护内存管理里的重要结构的锁的竞争问题，这些重要结构是指页表（page table）和虚拟内存区域（VMA, virtual memory area）等。Liam Howlett 和Matthew Wilcox 一直在开发一种新的数据结构，称为 "maple tree"，希望能取代目前用于 VMA 管理的数据结构。这个改动可能对内核内部结构造成巨大变化，作者已经公布了一个改动很大的 patch set 来召唤 review。
Linux 是一个虚拟内存(virtual-memory)系统。每个进程的地址空间中包含多个虚拟内存区域（VMA），都是由 vm_area_struct 结构表示。每个 vma 都代表一块连续的地址空间，并且这部分区域都是属于相同的内存类型，也就是可以是 anonymous memory（匿名内存，内容并不与某个文件对应）、memory-mapped file（内存映射文件），甚至是 device memory（设备内存）。从进程的角度来看，一个 VMA 区域都是连续的，而实际上底层的物理内存区域可能并不连续。此外，整个地址空间在各个 VMA 之间是有空洞的，当内核需要映射产生一个新的区域时（例如在加载一个库文件或者响应 mmap()调用时），内核就会从这些空洞分配出虚拟空间从而利用起来（当然还是会预留一些未映射的 "guard" page，有利于减少缓冲区溢出的危害）。
我们的系统中几乎所有工作都涉及到内存，所以对这些表示 VMA 的结构的操作必须要快。这些操作包括 lookup（查找，也就是找出哪个 VMA 是对应某个虚拟地址的、确认内存是否被 map 过，或者寻找一个空闲区域用于分配新的 VMA），以及修改（例如，增大堆栈空间）。
VMA 目前是通过一个红黑树（rbtree，red-black tree）的变种来管理的，针对红黑树来说增加了一个额外的双向链表，用来让内核遍历某个进程地址空间中的所有 VMA。内核开发者对这种数据结构的不满已经有一段时间了，原因有很多：rbtree 不能很好地支持范围（ranges），难以用 lockless（不需要获取锁）的方式来进行操作（rbtree 需要进行 balance 操作，这会同时影响多个 item），而且 rbtree 遍历的效率很低，这也是为什么需要一个额外的双向链表。
对 VMA 的操作会使用一个 lock 来保护（具体来说是一个 reader/writer semaphore），这个 lock 位于 struct mm_struct 中，此前名为 mmap_sem，2020 年 6 月的 5.8 版本将其改名为 mmap_lock。改名是为了能将对这个 lock 的操作都用 API 包装起来，希望将来替换的时候方便。
用户经常会碰到争抢这个 lock 的情况，尤其是那些在大型系统中使用多线程应用的用户。内核开发者已经多次讨论过这个问题，在 2019 年的 Linux Storage, Filesystem, and Memory-Management Summit (LFSMM) 峰会上至少有三次讨论过这个问题。问题的核心是，许多操作都需要获取 lock，这包括几乎全部的涉及 page table 和 VMA 的操作。还有其他一些相关的结构事实上也被 mmap_lock 地保护起来（麻烦的是相关文档也是缺失的）。开发者们在做的事情除了将不相关的结构从 mmap_lock 保护下拆分出来之外，还在考虑使用一个结构能允许 VMA 的访问变成 lockless 模式，或者使用某种类型的 range lock。当时有人提出了 maple tree 结构作为解决方案之一，但当时 maple tree 还处于早期开发状态，代码还没有完成。
Linux内核实现了常用的通用数据结构：
- 链表
- 队列
- 映射
- 二叉树
内核开发者应尽可能使用这些数据结构，不要造轮子重复开发。
一、链表
Linux内核代码大量使用了链表这种数据结构。链表是在解决数组不能动态扩展这个缺陷而产生的一种数据结构。链表所包含的元素可以动态创建并插入和删除。链表的每个元素都是离散存放的，因此不需要占用连续的内存。链表通常由若干节点组成，每个节点的结构都是一样的，由有效数据区和指针区两部分组成。有效数据区用来存储有效数据信息，而指针区用来指向链表的前继节点或者后继节点。因此，链表就是利用指针将各个节点串联起来的一种存储结构。
（1）单向链表
单向链表的指针区只包含一个指向下一个节点的指针，因此会形成一个单一方向的链表，如下代码所示。
struct list { int data; /*有效数据*/ struct list *next; /*指向下一个元素的指针*/ struct list *prev; /*指向上一个元素的指针*/ };
（2）双向链表
如图所示，双向链表和单向链表的区别是指针区包含了两个指针，一个指向前继节点，另一个指向后继节点，如下代码所示。
struct list { int data; /*有效数据*/ struct list *next; /*指向下一个元素的指针*/ struct list *prev; /*指向上一个元素的指针*/ };
（3）Linux内核链表实现
单向链表和双向链表在实际使用中有一些局限性，如数据区必须是固定数据，而实际需求是多种多样的。这种方法无法构建一套通用的链表，因为每个不同的数据区需要一套链表。为此，Linux内核把所有链表操作方法的共同部分提取出来，把不同的部分留给代码编程者自己去处理。Linux内核实现了一套纯链表的封装，链表节点数据结构只有指针区而没有数据区，另外还封装了各种操作函数，如创建节点函数、插入节点函数、删除节点函数、遍历节点函数等。
Linux内核链表使用struct list_head数据结构来描述：
<include/linux/types.h> struct list_head { struct list_head *next, *prev; };
struct list_head数据结构不包含链表节点的数据区，通常是嵌入其他数据结构，如struct page数据结构中嵌入了一个lru链表节点，通常是把page数据结构挂入LRU链表。
<include/linux/mm_types.h> struct page { ... struct list_head lru; ... }
链表头的初始化有两种方法，一种是静态初始化，另一种动态初始化。把next和prev指针都初始化并指向自己，这样便初始化了一个带头节点的空链表。
<include/linux/list.h> /*静态初始化*/ #define LIST_HEAD_INIT(name) { &(name), &(name) } #define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name) /*动态初始化*/ static inline void INIT_LIST_HEAD(struct list_head *list) { list->next = list; list->prev = list; }
添加节点到一个链表中，内核提供了几个接口函数，如list_add()是把一个节点添加到表头，list_add_tail()是插入表尾。
<include/linux/list.h> void list_add(struct list_head *new, struct list_head *head) list_add_tail(struct list_head *new, struct list_head *head)
遍历节点的接口函数。
#define list_for_each(pos, head) for (pos = (head)->next; pos != (head); pos = pos->next)
这个宏只是遍历一个一个节点的当前位置，那么如何获取节点本身的数据结构呢？这里还需要使用list_entry()宏。
#define list_entry(ptr, type, member) container_of(ptr, type, member) container_of()宏的定义在kernel.h头文件中。 #define container_of(ptr, type, member) ({ const typeof( ((type *)0)->member ) *__mptr = (ptr); (type *)( (char *)__mptr - offsetof(type,member) );}) #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
其中offsetof()宏是通过把0地址转换为type类型的指针，然后去获取该结构体中member成员的指针，也就是获取了member在type结构体中的偏移量。最后用指针ptr减去offset，就得到type结构体的真实地址了。
下面是遍历链表的一个例子：
<drivers/block/osdblk.c> static ssize_t class_osdblk_list(struct class *c, struct class_attribute *attr, char *data) { int n = 0; struct list_head *tmp; list_for_each(tmp, &osdblkdev_list) { struct osdblk_device *osdev; osdev = list_entry(tmp, struct osdblk_device, node); n += sprintf(data+n, "%d %d %llu %llu %sn", osdev->id, osdev->major, osdev->obj.partition, osdev->obj.id, osdev->osd_path); } return n; }
二、队列
Linux内核通用队列实现称为kfifo。
kfifo是一种"First In First Out “数据结构，它采用了前面提到的环形缓冲区来实现，提供一个无边界的字节流服务。采用环形缓冲区的好处为，当一个数据元素被用掉后，其余数据元素不需要移动其存储位置，从而减少拷贝提高效率。更重要的是，kfifo采用了并行无锁技术，kfifo实现的单生产/单消费模式的共享队列是不需要加锁同步的。
struct kfifo { unsigned char *buffer; /* the buffer holding the data */ unsigned int size; /* the size of the allocated buffer */ unsigned int in; /* data is added at offset (in % size) */ unsigned int out; /* data is extracted from off. (out % size) */ spinlock_t *lock; /* protects concurrent modifications */ };
它的结构如图：
这看起来与普通的环形缓冲区没有什么差别，但是让人叹为观止的地方就是它巧妙的用 in 和 out 的关系和特性，处理各种操作，下面我们来详细分析。
2.1kfifo内存分配和初始化
首先，看一个很有趣的函数，判断一个数是否为2的次幂，按照一般的思路，求一个数n是否为2的次幂的方法为看 n % 2 是否等于0， 我们知道“取模运算”的效率并没有 “位运算” 的效率高，有兴趣的同学可以自己做下实验。下面再验证一下这样取2的模的正确性，若n为2的次幂，则n和n-1的二进制各个位肯定不同 (如8(1000)和7(0111))，&出来的结果肯定是0；如果n不为2的次幂，则各个位肯定有相同的 (如7(0111) 和6(0110))，&出来结果肯定为0。是不是很巧妙？
bool is_power_of_2(unsigned long n) { return (n != 0 && ((n & (n - 1)) == 0)); }
再看下kfifo内存分配和初始化的代码，前面提到kfifo总是对size进行2次幂的圆整，这样的好处不言而喻，可以将kfifo->size取模运算可以转化为与运算，如下： kfifo->in % kfifo->size 可以转化为 kfifo->in & (kfifo->size – 1)“取模运算”的效率并没有 “位运算” 的效率高还记得不，不放过任何一点可以提高效率的地方。
struct kfifo *kfifo_alloc(unsigned int size, gfp_t gfp_mask, spinlock_t *lock) { unsigned char *buffer; struct kfifo *ret; /* * round up to the next power of 2, since our 'let the indices * wrap' technique works only in this case. */ if (!is_power_of_2(size)) { BUG_ON(size > 0x80000000); ` size = roundup_pow_of_two(size); } buffer = kmalloc(size, gfp_mask); if (!buffer) return ERR_PTR(-ENOMEM); ret = kfifo_init(buffer, size, gfp_mask, lock); if (IS_ERR(ret)) kfree(buffer); return ret; }
2.2kfifo并发无锁奥秘---内存屏障
为什么kfifo实现的单生产/单消费模式的共享队列是不需要加锁同步的呢？天底下没有免费的午餐的道理人人都懂，下面我们就来看看kfifo实现并发无锁的奥秘。
我们知道 编译器编译源代码时，会将源代码进行优化，将源代码的指令进行重排序，以适合于CPU的并行执行。然而，内核同步必须避免指令重新排序，优化屏障（Optimization barrier）避免编译器的重排序优化操作，保证编译程序时在优化屏障之前的指令不会在优化屏障之后执行。
举个例子，如果多核CPU执行以下程序：
a = 1; b = a + 1; assert(b == 2);
假设初始时a和b的值都是0，a处于CPU1-cache中，b处于CPU0-cache中。如果按照下面流程执行这段代码：
1 CPU0执行a=1; 2 因为a在CPU1-cache中，所以CPU0发送一个read invalidate消息来占有数据 3 CPU0将a存入store buffer 4 CPU1接收到read invalidate消息，于是它传递cache-line，并从自己的cache中移出该cache-line 5 CPU0开始执行b=a+1; 6 CPU0接收到了CPU1传递来的cache-line，即“a=0” 7 CPU0从cache中读取a的值，即“0” 8 CPU0更新cache-line，将store buffer中的数据写入，即“a=1” 9 CPU0使用读取到的a的值“0”，执行加1操作，并将结果“1”写入b（b在CPU0-cache中，所以直接进行） 10 CPU0执行assert(b == 2); 失败
软件可通过读写屏障强制内存访问次序。读写屏障像一堵墙，所有在设置读写屏障之前发起的内存访问，必须先于在设置屏障之后发起的内存访问之前完成，确保内存访问按程序的顺序完成。Linux内核提供的内存屏障API函数说明如下表。内存屏障可用于多处理器和单处理器系统，如果仅用于多处理器系统，就使用smp_xxx函数，在单处理器系统上，它们什么都不要。
如果对上述代码加上内存屏障,就能保证在CPU0取a时，一定已经设置好了a = 1:
void foo(void) { a = 1; smp_wmb(); b = a + 1; }
这里只是简单介绍了内存屏障的概念，如果想对内存屏障有进一步理解,请参考我的译文《为什么需要内存屏障》。
2.3kfifo的入队__kfifo_put和出队__kfifo_get操作
__kfifo_put是入队操作，它先将数据放入buffer中，然后移动in的位置，其源代码如下：
unsigned int __kfifo_put(struct kfifo *fifo, const unsigned char *buffer, unsigned int len) { unsigned int l; len = min(len, fifo->size - fifo->in + fifo->out); /* * Ensure that we sample the fifo->out index -before- we * start putting bytes into the kfifo. */ smp_mb(); /* first put the data starting from fifo->in to buffer end */ l = min(len, fifo->size - (fifo->in & (fifo->size - 1))); memcpy(fifo->buffer + (fifo->in & (fifo->size - 1)), buffer, l); /* then put the rest (if any) at the beginning of the buffer */ memcpy(fifo->buffer, buffer + l, len - l); /* * Ensure that we add the bytes to the kfifo -before- * we update the fifo->in index. */ smp_wmb(); fifo->in += len; return len; }
6行，环形缓冲区的剩余容量为fifo->size - fifo->in + fifo->out，让写入的长度取len和剩余容量中较小的，避免写越界；
13行，加内存屏障，保证在开始放入数据之前，fifo->out取到正确的值（另一个CPU可能正在改写out值）
16行，前面讲到fifo->size已经2的次幂圆整，而且kfifo->in % kfifo->size 可以转化为 kfifo->in & (kfifo->size – 1)，所以fifo->size - (fifo->in & (fifo->size - 1)) 即位 fifo->in 到 buffer末尾所剩余的长度，l取len和剩余长度的最小值，即为需要拷贝l 字节到fifo->buffer + fifo->in的位置上。
17行，拷贝l 字节到fifo->buffer + fifo->in的位置上，如果l = len，则已拷贝完成，第20行len – l 为0，将不执行，如果l = fifo->size - (fifo->in & (fifo->size - 1)) ，则第20行还需要把剩下的 len – l 长度拷贝到buffer的头部。
27行，加写内存屏障，保证in 加之前，memcpy的字节已经全部写入buffer，如果不加内存屏障，可能数据还没写完，另一个CPU就来读数据，读到的缓冲区内的数据不完全，因为读数据是通过 in – out 来判断的。
29行，注意这里 只是用了 fifo->in += len而未取模，这就是kfifo的设计精妙之处，这里用到了unsigned int的溢出性质，当in 持续增加到溢出时又会被置为0，这样就节省了每次in向前增加都要取模的性能，锱铢必较，精益求精，让人不得不佩服。
__kfifo_get是出队操作，它从buffer中取出数据，然后移动out的位置，其源代码如下：
unsigned int __kfifo_get(struct kfifo *fifo, unsigned char *buffer, unsigned int len) { unsigned int l; len = min(len, fifo->in - fifo->out); /* * Ensure that we sample the fifo->in index -before- we * start removing bytes from the kfifo. */ smp_rmb(); /* first get the data from fifo->out until the end of the buffer */ l = min(len, fifo->size - (fifo->out & (fifo->size - 1))); memcpy(buffer, fifo->buffer + (fifo->out & (fifo->size - 1)), l); /* then get the rest (if any) from the beginning of the buffer */ memcpy(buffer + l, fifo->buffer, len - l); /* * Ensure that we remove the bytes from the kfifo -before- * we update the fifo->out index. */ smp_mb(); fifo->out += len; return len; }
6行，可去读的长度为fifo->in – fifo->out，让读的长度取len和剩余容量中较小的，避免读越界；
13行，加读内存屏障，保证在开始取数据之前，fifo->in取到正确的值（另一个CPU可能正在改写in值）
16行，前面讲到fifo->size已经2的次幂圆整，而且kfifo->out % kfifo->size 可以转化为 kfifo->out & (kfifo->size – 1)，所以fifo->size - (fifo->out & (fifo->size - 1)) 即位 fifo->out 到 buffer末尾所剩余的长度，l取len和剩余长度的最小值，即为从fifo->buffer + fifo->in到末尾所要去读的长度。
17行，从fifo->buffer + fifo->out的位置开始读取l长度，如果l = len，则已读取完成，第20行len – l 为0，将不执行，如果l =fifo->size - (fifo->out & (fifo->size - 1)) ，则第20行还需从buffer头部读取 len – l 长。
27行，加内存屏障，保证在修改out前，已经从buffer中取走了数据，如果不加屏障，可能先执行了增加out的操作，数据还没取完，令一个CPU可能已经往buffer写数据，将数据破坏，因为写数据是通过fifo->size - (fifo->in & (fifo->size - 1))来判断的 。
29行，注意这里 只是用了 fifo->out += len 也未取模，同样unsigned int的溢出性质，当out 持续增加到溢出时又会被置为0，如果in先溢出，出现 in < out 的情况，那么 in – out 为负数（又将溢出），in – out 的值还是为buffer中数据的长度。
这里图解一下 in 先溢出的情况，size = 64， 写入前 in = 4294967291， out = 4294967279 ，数据 in – out = 12;
写入 数据16个字节，则 in + 16 = 4294967307，溢出为 11，此时 in – out = –4294967268，溢出为28，数据长度仍然正确，由此可见，在这种特殊情况下，这种计算仍然正确，是不是让人叹为观止，妙不可言？
