Linux内核中的链表、红黑树和KFIFO

lLinux内核代码中广泛使用了链表、红黑树和KFIFO。

一、链表

linux内核代码大量使用了链表这种数据结构。链表是在解决数组不能动态扩展这个缺陷而产生的一种数据结构。链表所包含的元素可以动态创建并插入和删除。链表的每个元素都是离散存放的，因此不需要占用连续的内存。链表通常由若干节点组成，每个节点的结构都是一样的，由有效数据区和指针区两部分组成。有效数据区用来存储有效数据信息，而指针区用来指向链表的前继节点或者后继节点。因此，链表就是利用指针将各个节点串联起来的一种存储结构。
l链表在 linux 内核中的使用无处不在，可谓是基础中的基础。在很多的数据结构中都会嵌入struct list_head结构体变量，它可以使结构体加入到一个双向链表中。链表的初始化，增加，删除等操作的接口在nclude\linux\list.h里面，Kernel 中的文件、kobject、设备、驱动等等，都是依赖链表连接起来的。

1.1、链表结构体定义

l链表结构体定义内容如下，定义在 include\linux\types.h 中

struct list_head {struct list_head *next, *prev;
};

l其成员就是两个指向list_head的指针，next指向后一个链表节点、prev指向前一个链表节点。链表单独使用并没有太大意义，一般都是嵌入到“宿主结构体”中。代码逻辑不关注list本身，而是利用list，将“宿主结构体”串联起来。链表API在源码中的路径是：include\linux\list.h

1.2、初始化

在文件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;
}

l把next和prev指针都初始化并指向自己，这样便初始化了一个带头节点的空链表。

1.3、增删节点

l插入一个新节点的操作很简单，就是把原有的链表从插入点断开，再把新节点连接上去

/** Insert a new entry between two known consecutive entries.** This is only for internal list manipulation where we know* the prev/next entries already!*/
#ifndef CONFIG_DEBUG_LIST
static inline void __list_add(struct list_head *new,struct list_head *prev,struct list_head *next)
{next->prev = new;new->next = next;new->prev = prev;prev->next = new;
}
#else
extern void __list_add(struct list_head *new,struct list_head *prev,struct list_head *next);
#endif/*** list_add - add a new entry* @new: new entry to be added* @head: list head to add it after** Insert a new entry after the specified head.* This is good for implementing stacks.*/
static inline void list_add(struct list_head *new, struct list_head *head)
{__list_add(new, head, head->next);
}
/*** list_add_tail - add a new entry* @new: new entry to be added* @head: list head to add it before** Insert a new entry before the specified head.* This is useful for implementing queues.*/
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{__list_add(new, head->prev, head);
}

l插入前：head <–> next
l插入后：head <–> new <–> next
l删除节点同理，也是重新更改前后节点的指针内容来实现：

static inline void __list_del_entry(struct list_head *entry)
{__list_del(entry->prev, entry->next);
}static inline void list_del(struct list_head *entry)
{__list_del(entry->prev, entry->next);entry->next = LIST_POISON1;entry->prev = LIST_POISON2;
}

l删除后节点的前后指针，都被指向一个特殊的地址，用于识别出这个链表指针不能使用：

/** These are non-NULL pointers that will result in page faults* under normal circumstances, used to verify that nobody uses* non-initialized list entries.*/
#define LIST_POISON1  ((void *) 0x00100100 + POISON_POINTER_DELTA)
#define LIST_POISON2  ((void *) 0x00200200 + POISON_POINTER_DELTA)

l从增删节点的代码可以看出，list内是无锁的。如果存在线程安全问题，需要调用者自行加锁。

1.4、遍历链表

/*** list_for_each	-	iterate over a list* @pos:	the &struct list_head to use as a loop cursor.* @head:	the head for your list.*/
#define list_for_each(pos, head) \for (pos = (head)->next; pos != (head); pos = pos->next)/*** list_for_each_prev	-	iterate over a list backwards* @pos:	the &struct list_head to use as a loop cursor.* @head:	the head for your list.*/
#define list_for_each_prev(pos, head) \for (pos = (head)->prev; pos != (head); pos = pos->prev)/*** list_for_each_safe - iterate over a list safe against removal of list entry* @pos:	the &struct list_head to use as a loop cursor.* @n:		another &struct list_head to use as temporary storage* @head:	the head for your list.*/
#define list_for_each_safe(pos, n, head) \for (pos = (head)->next, n = pos->next; pos != (head); \pos = n, n = pos->next)/*** list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry* @pos:	the &struct list_head to use as a loop cursor.* @n:		another &struct list_head to use as temporary storage* @head:	the head for your list.*/
#define list_for_each_prev_safe(pos, n, head) \for (pos = (head)->prev, n = pos->prev; \pos != (head); \pos = n, n = pos->prev)/*** list_for_each_entry	-	iterate over list of given type* @pos:	the type * to use as a loop cursor.* @head:	the head for your list.* @member:	the name of the list_head within the struct.*/
#define list_for_each_entry(pos, head, member)				\for (pos = list_first_entry(head, typeof(*pos), member);	\&pos->member != (head);					\pos = list_next_entry(pos, member))

llist_for_each函数是按照从前往后的顺序遍历链表，通过不断指向元素的next元素，直到元素的指针和链表头指针地址相同，则表示链表遍历完成。
llist_for_each_prev函数则是从链表的尾部元素向前遍历。
llist_for_each_safe函数引入了指针n，用于存储pos的下一个元素的地址。引入指针n可以方便在遍历链表的时候删除pos指向的元素，而不影响遍历。list_for_each无法做到这一点。
llist_for_each_prev_safe函数和list_for_each_safe函数的区别是从后往前遍历。
llist_for_each_entry函数是list_for_each和list_entry的结合，有pos，head，member三个参数，pos是一个中间变量，指向当前访问的链表元素，head指链表头，member指pos指向的结构体中链表成员变量的名称，

1.5、查找链表元素

/*** list_entry - get the struct for this entry* @ptr:	the &struct list_head pointer.* @type:	the type of the struct this is embedded in.* @member:	the name of the list_head within the struct.*/
#define list_entry(ptr, type, member) \container_of(ptr, type, member)

list_entry宏有三个参数ptr，type，member。ptr是指数据结构中struct list_head变量成员的地址，type是指数据结构的类型，member是指数据结构中struct list_head的变量名。list_entry宏的结果是ptr指向的type类型的数据结构的变量地址。

1.6、使用示例

#include <linux/kernel.h>  
#include <linux/module.h>  
#include <linux/init.h>  
#include <linux/slab.h>  
#include <linux/list.h>    
//实际数据结构
struct student  
{  char name[100];  int num;  struct list_head list;  
};  
//链表的头结点, (无数据)  
struct list_head student_list;  
static int mylist_init(void)  
{  int i = 0;  printk( "###############################\n");      INIT_LIST_HEAD(&student_list);              //链表头结点student_list前驱和后继都指向自身  struct student *pstudent;pstudent= kmalloc(sizeof(struct student)*5,GFP_KERNEL);  //申请了5个结点的内存，内存地址是pstudent  ，而且这5个内存块是连续的。memset(pstudent,0,sizeof(struct student)*5);printk(KERN_INFO "************list_add_tail************\n");//1. 向链表添加结点for(i=0;i<5;i++)  {  sprintf(pstudent[i].name,"Student%d",i+1);  pstudent[i].num= i+1;  list_add_tail(&(pstudent[i].list), &student_list);      //尾插法, 添加到链表的末尾//list_add_tail(&(pstudent[i].list), &student_list);    //头插法printk("<0>---student%d name: %s\n",pstudent[i].num,pstudent[i].name);}printk(KERN_INFO "************list_for_each************\n");//2. 从头依次遍历节点  方法一struct student *tmp_student;struct list_head *pos;list_for_each(pos,&student_list)  {  //pos 是 每个节点中list 成员的地址tmp_student= list_entry(pos,struct student,list);  //根据pos获取每个节点的地址并赋值给tmp_studentprintk("<1>---student%d name: %s\n",tmp_student->num,tmp_student->name);  }printk(KERN_INFO "************list_for_each_entry************\n");//3. 从头依次遍历节点   方法二:  方法一的简化版struct student *tmp_student2;list_for_each_entry(tmp_student2,&student_list, list)  {  printk("<2>---student%d name: %s\n",tmp_student2->num,tmp_student2->name);  }for(i=0;i<5;i++)  {  list_del(&(pstudent[i].list));      }  kfree(pstudent);  printk( "###############################\n");return 0;  
}   
static void mylist_exit(void)  
{        
}    
module_init(mylist_init);  
module_exit(mylist_exit);
MODULE_LICENSE("GPL");

将代码在ubuntu的虚拟机里面测试，makefile文件如下：

KERNELDIR :=/usr/src/linux-headers-5.4.0-149-generic
CURRENT_PATH := $(shell pwd)
#禁用签名
CONFIG_MODULE_SIG=nobj-m := list.obuild: kernel_moduleskernel_modules:$(MAKE) -C $(KERNELDIR) M=$(CURRENT_PATH) modulesclean:$(MAKE) -C $(KERNELDIR) M=$(CURRENT_PATH) clean

运行结果如下图所示：
在这里插入图片描述

二、红黑树

红黑树（Red Black Tree）被广泛应用在内核的内存管理和进程调度中，用于将排序的元素组织到树中。红黑树被广泛应用在计算机科学的各个领域中，它在速度和实现复杂度之间提供一个很好的平衡。
红黑树是具有以下特征的二叉树。
每个节点或红或黑。
每个叶节点是黑色的。
如果结点都是红色，那么两个子结点都是黑色。
从一个内部结点到叶结点的简单路径上，对所有叶节点来说，黑色结点的数目都是相同的。
红黑树的一个优点是，所有重要的操作（例如插入、删除、搜索）都可以在O(log n)时间内完成，n为树中元素的数目。这里只是列出一个内核中使用红黑树的例子。这个例子可以在内核代码的documentation/Rbtree.txt文件中找到。

#include <linux/init.h>
#include <linux/list.h>
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/slab.h>
#include <linux/mm.h>
#include <linux/rbtree.h>struct mytype { struct rb_node node;int key; 
};/*红黑树根节点*/struct rb_root mytree = RB_ROOT;
/*根据key来查找节点*/
struct mytype *my_search(struct rb_root *root, int new){struct rb_node *node = root->rb_node;while (node) {struct mytype *data = container_of(node, struct mytype, node);if (data->key > new)node = node->rb_left;else if (data->key < new)node = node->rb_right;elsereturn data;}return NULL;}/*插入一个元素到红黑树中*/int my_insert(struct rb_root *root, struct mytype *data){struct rb_node **new = &(root->rb_node), *parent=NULL;/* 寻找可以添加新节点的地方 */while (*new) {struct mytype *this = container_of(*new, struct mytype, node);parent = *new;if (this->key > data->key)new = &((*new)->rb_left);else if (this->key < data->key) {new = &((*new)->rb_right);} elsereturn -1;}/* 添加一个新节点 */rb_link_node(&data->node, parent, new);rb_insert_color(&data->node, root);return 0;}static int __init my_init(void)
{int i;struct mytype *data;struct rb_node *node;/*插入元素*/for (i =0; i < 20; i+=2) {data = kmalloc(sizeof(struct mytype), GFP_KERNEL);data->key = i;my_insert(&mytree, data);}/*遍历红黑树，打印所有节点的key值*/for (node = rb_first(&mytree); node; node = rb_next(node)) printk("key=%d\n", rb_entry(node, struct mytype, node)->key);return 0;
}static void __exit my_exit(void)
{struct mytype *data;struct rb_node *node;for (node = rb_first(&mytree); node; node = rb_next(node)) {data = rb_entry(node, struct mytype, node);if (data) {rb_erase(&data->node, &mytree);kfree(data);}}
}
module_init(my_init);
module_exit(my_exit);
MODULE_LICENSE("GPL");

mytree是红黑树的根节点，my_insert()实现插入一个元素到红黑树中，my_search()根据key来查找节点。内核大量使用红黑树，如虚拟地址空间VMA的管理。
关于红黑树可以参考：
Linux内核中红黑树的使用方法
Linux内核中红黑树节点的插入原理分析
Linux内核中红黑树节点的删除原理分析

三、无锁环形缓冲区kfifo

3.1、kfifo介绍

3.1.1、kfifo作用

生产者和消费者模型是计算机编程中最常见的一种模型。生产者产生数据，而消费者消耗数据，如一个网络设备，硬件设备接收网络包，然后应用程序读取网络包。环形缓冲区是实现生产者和消费者模型的经典算法。环形缓冲区通常有一个读指针和一个写指针。读指针指向环形缓冲区中可读的数据，写指针指向环形缓冲区可写的数据。通过移动读指针和写指针实现缓冲区数据的读取和写入。FIFO主要用于缓冲速度不匹配的通信。
在Linux内核中，KFIFO是采用无锁环形缓冲区的实现。FIFO的全称是“First In First Out”，即先进先出的数据结构，它采用环形缓冲区的方法来实现，并提供一个无边界的字节流服务。采用环形缓冲区的好处是，当一个数据元素被消耗之后，其余数据元素不需要移动其存储位置，从而减少复制，提高效率。

3.1.2、kfifo原理

kfifo是linux内核的对队列功能的实现。在内核中，它被称为无锁环形队列。所谓无锁，就是当只有一个生产者和只有一个消费者时，操作fifo不需要加锁。这是因为kfifo出队和入队时，不会改动到相同的变量。
kfifo使用了in和out两个变量分别作为入队和出队的索引：

入队n个数据时，in变量就+n
出队k个数据时，out变量就+k
out不允许大于in（out等于in时表示fifo为空）
in不允许比out大超过fifo空间
如果in和out大于fifo空间了，这两个索引会一直往前加，不轻易回头，为出入队操作省下了几个指令周期。
那入队和出队的数据从哪里开始存储/读取呢，我们第一时间会想到，把 in/out 用“%”对fifo大小取余就行了，是吧？不，取余这种耗费资源的运算，内核开发者怎会轻易采用呢，kfifo的办法是，把 in/out 与上fifo->mask。这个mask等于fifo的空间大小减一（其要求fifo的空间必须是2的次方大小）。这个“与”操作可比取余操作快得多了。
由此，kfifo就实现了“无锁”“环形”队列。
了解了上述原理，我们就能意识到，这个无锁只是针对“单生产者-单消费者”而言的。“多生产者”时，则需要对入队操作进行加锁；同样的，“多消费者”时需要对出队操作进行加锁。

3.2、linux中kfifo的实现

kfifo的源码在linux内核的include/linux/kfifo.h文件中

3.2.1、结构体

kfifo的结构体如下：

struct __kfifo {unsigned int	in;//入队unsigned int	out;//出队unsigned int	mask;//大小掩码unsigned int	esize;大小void		*data;队列缓存指针
};

3.2.2、初始化并内存申请

在使用KFIFO之前需要进行初始化，有静态初始化和动态初始化两种方式。
1）、动态申请
动态初始化为kfifo_alloc在文件内include/linux/kfifo.h：

/*** kfifo_alloc - dynamically allocates a new fifo buffer* @fifo: pointer to the fifo* @size: the number of elements in the fifo, this must be a power of 2* @gfp_mask: get_free_pages mask, passed to kmalloc()** This macro dynamically allocates a new fifo buffer.** The numer of elements will be rounded-up to a power of 2.* The fifo will be release with kfifo_free().* Return 0 if no error, otherwise an error code.*/
#define kfifo_alloc(fifo, size, gfp_mask) \
__kfifo_int_must_check_helper( \
({ \typeof((fifo) + 1) __tmp = (fifo); \struct __kfifo *__kfifo = &__tmp->kfifo; \__is_kfifo_ptr(__tmp) ? \__kfifo_alloc(__kfifo, size, sizeof(*__tmp->type), gfp_mask) : \-EINVAL; \
}) \
)

该函数创建并分配一个大小为size的KFIFO环形缓冲区。第一个参数fifo是指向该环形缓冲区的struct kfifo数据结构；第二个参数size是指定缓冲区元素的数量；第三个参数gfp_mask表示分配KFIFO元素使用的分配掩码。
其中__kfifo_alloc函数在\lib\kfifo.c文件内：

int __kfifo_alloc(struct __kfifo *fifo, unsigned int size,size_t esize, gfp_t gfp_mask)
{/** round down to the next power of 2, since our 'let the indices* wrap' technique works only in this case.*/size = roundup_pow_of_two(size);fifo->in = 0;fifo->out = 0;fifo->esize = esize;if (size < 2) {fifo->data = NULL;fifo->mask = 0;return -EINVAL;}fifo->data = kmalloc(size * esize, gfp_mask);if (!fifo->data) {fifo->mask = 0;return -ENOMEM;}fifo->mask = size - 1;return 0;
}

通过代码可以看到kfifo最终申请的内存空间，是调用者要求空间的向上取2的次方。比如想申请7字节，最终是申请8字节；想申请9字节，最终是申请16字节。这样才能实现用mask大小掩码“与”上in/out索引，实现队列回环（避免取余计算）。
如果不了解这个规则，则可能会踩坑。比如某个程序想申请100字节（使用kfifo_alloc的动态方式或element大小为1），但实际申请到的是128字节而不自知。假设这个程序每次入队和出队都是10字节，当fifo存满后，最后一次入队的10字节实际上只保存了8字节，此后每次还是按10字节出队的话，则会永远错位2字节。
2）、静态申请
静态分配可以使用如下的宏。

#define DEFINE_KFIFO(fifo, type, size)
#define INIT_KFIFO(fifo)

定义在include/linux/kfifo.h文件内

/*** DEFINE_KFIFO - macro to define and initialize a fifo* @fifo: name of the declared fifo datatype* @type: type of the fifo elements* @size: the number of elements in the fifo, this must be a power of 2** Note: the macro can be used for global and local fifo data type variables.*/
#define DEFINE_KFIFO(fifo, type, size) \DECLARE_KFIFO(fifo, type, size) = \(typeof(fifo)) { \{ \{ \.in	= 0, \.out	= 0, \.mask	= __is_kfifo_ptr(&(fifo)) ? \0 : \ARRAY_SIZE((fifo).buf) - 1, \.esize	= sizeof(*(fifo).buf), \.data	= __is_kfifo_ptr(&(fifo)) ? \NULL : \(fifo).buf, \} \} \}

/*** INIT_KFIFO - Initialize a fifo declared by DECLARE_KFIFO* @fifo: name of the declared fifo datatype*/
#define INIT_KFIFO(fifo) \
(void)({ \typeof(&(fifo)) __tmp = &(fifo); \struct __kfifo *__kfifo = &__tmp->kfifo; \__kfifo->in = 0; \__kfifo->out = 0; \__kfifo->mask = __is_kfifo_ptr(__tmp) ? 0 : ARRAY_SIZE(__tmp->buf) - 1;\__kfifo->esize = sizeof(*__tmp->buf); \__kfifo->data = __is_kfifo_ptr(__tmp) ?  NULL : __tmp->buf; \
})

3.2.3、入队操作

把数据写入KFIFO环形缓冲区可以使用kfifo_in()函数接口。

int kfifo_in(fifo, buf, n)

该函数把buf指针指向的n个数据复制到KFIFO环形缓冲区中。第一个参数fifo指的是KFIFO环形缓冲区；第二个参数buf指向要复制的数据的buffer；第三个数据是要复制数据元素的数量。
kfifo_in()函数定义在include/linux/kfifo.h文件内

/*** kfifo_in - put data into the fifo* @fifo: address of the fifo to be used* @buf: the data to be added* @n: number of elements to be added** This macro copies the given buffer into the fifo and returns the* number of copied elements.** Note that with only one concurrent reader and one concurrent* writer, you don't need extra locking to use these macro.*/
#define	kfifo_in(fifo, buf, n) \
({ \typeof((fifo) + 1) __tmp = (fifo); \typeof(__tmp->ptr_const) __buf = (buf); \unsigned long __n = (n); \const size_t __recsize = sizeof(*__tmp->rectype); \struct __kfifo *__kfifo = &__tmp->kfifo; \(__recsize) ?\__kfifo_in_r(__kfifo, __buf, __n, __recsize) : \__kfifo_in(__kfifo, __buf, __n); \
})

其中__kfifo_in（）函数定义在\lib\kfifo.c文件内

unsigned int __kfifo_in(struct __kfifo *fifo,const void *buf, unsigned int len)
{unsigned int l;l = kfifo_unused(fifo);if (len > l)len = l;kfifo_copy_in(fifo, buf, len, fifo->in);fifo->in += len;return len;
}

入队共3个步骤：
查询剩余空间（确认最大可入队的长度）
拷贝数据进内存
in索引更新
已用空间就是in-out，总空间是mask+1：

3.2.4、出队操作

从KFIFO环形缓冲区中列出或者摘取数据可以使用kfifo_out()函数接口。

#define    kfifo_out(fifo, buf, n)

该函数是从fifo指向的环形缓冲区中复制n个数据元素到buf指向的缓冲区中。如果KFIFO环形缓冲区的数据元素小于n个，那么复制出去的数据元素小于n个。
kfifo_out()函数定义在include/linux/kfifo.h文件内


/*** kfifo_out - get data from the fifo* @fifo: address of the fifo to be used* @buf: pointer to the storage buffer* @n: max. number of elements to get** This macro get some data from the fifo and return the numbers of elements* copied.** Note that with only one concurrent reader and one concurrent* writer, you don't need extra locking to use these macro.*/
#define	kfifo_out(fifo, buf, n) \
__kfifo_uint_must_check_helper( \
({ \typeof((fifo) + 1) __tmp = (fifo); \typeof(__tmp->ptr) __buf = (buf); \unsigned long __n = (n); \const size_t __recsize = sizeof(*__tmp->rectype); \struct __kfifo *__kfifo = &__tmp->kfifo; \(__recsize) ?\__kfifo_out_r(__kfifo, __buf, __n, __recsize) : \__kfifo_out(__kfifo, __buf, __n); \
}) \
)

出队操作和入队类似，其中__kfifo_out()函数定义在\lib\kfifo.c文件内

3.3、kfifo的使用示例

#include <linux/init.h>
#include <linux/module.h>
#include <linux/proc_fs.h>
#include <linux/mutex.h>
#include <linux/kfifo.h>
struct kfifo Kfifo_Test;
//定义fifo最大保存的元素个数
#define DM_FIFO_ELEMENT_MAX     1024
static int mykfifo_init(void)
{char buf[100];int i = 0;int ret = 0;printk(KERN_INFO "###############################\n");//申请fifo内存空间，一般在模块初始化时调用printk(KERN_INFO "************kfifo_alloc************\n");ret = kfifo_alloc(&Kfifo_Test, DM_FIFO_ELEMENT_MAX, GFP_KERNEL);if (ret) {printk(KERN_ERR "kfifo_alloc fail ret=%d\n", ret);return 1;}printk(KERN_INFO "************kfifo_in************\n");for ( i = 0; i < 10; i++) {memset(buf, 0x00, 100);memset(buf, 'a' + i, i + 1);kfifo_in(&Kfifo_Test, buf, i + 1);printk(KERN_ERR "kfifo_in:%s\n", buf);}printk(KERN_INFO "************kfifo_out************\n");while (!kfifo_is_empty(&Kfifo_Test)) {memset(buf, 0x00, 100);ret = kfifo_out(&Kfifo_Test, buf, sizeof(buf));printk(KERN_INFO "kfifo_out: %s\n",buf);}printk(KERN_INFO "************kfifo_free************\n");//释放内存空间，一般在模块退出时调用kfifo_free(&Kfifo_Test);printk(KERN_INFO "###############################\n");
return 0;
}
static void mykfifo_exit(void)  
{        
}   
module_init(mykfifo_init);  
module_exit(mykfifo_exit);
MODULE_LICENSE("GPL");

将代码在ubuntu的虚拟机里面测试，makefile文件如下：

KERNELDIR :=/usr/src/linux-headers-5.4.0-149-generic
CURRENT_PATH := $(shell pwd)
#禁用签名
CONFIG_MODULE_SIG=nobj-m := kfifo.obuild: kernel_moduleskernel_modules:$(MAKE) -C $(KERNELDIR) M=$(CURRENT_PATH) modulesclean:$(MAKE) -C $(KERNELDIR) M=$(CURRENT_PATH) clean