Linux内核中的链表

淡淡的烟草味﹌ 2022-05-17 12:48 214阅读 0赞

1 链表简述

在讲Linux内核中的链表之前，我们先来看一下平时所见的链表：

/*平时所见的单向链表*/
    struct entry{
    	int data;
    	char * desc;
    	struct entry *next;
    }
    
    /*平时所见的双向链表*/
    struct entry{
    	int data;
    	char * desc;
    	struct entry *prev;
    	struct entry *next;
    }

用图片表示如下：

![70][]

下面来看一下Linux内核中关于双向链表的实现：

![70 1][]

内核中双向链表的结构体：[源代码网址][Link 1]

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

先来说一下Linux内核中的链表为什么要这样设计？

对于每一个链表，都需要实现一组操作：初始化链表，插入和删除元素，对链表进行遍历等等。试想，如果我们采用普通链表那样的方式，每一次我们建立一个链表结构体，我们都需要重新实现初始化、插入、删除、遍历元素等，这可能浪费开发人员的精力，也因为对每个不同的链表都要重复相同的原语操作（这里原语操作指的是对链表的建立与增、删、遍历等操作）而造成存储空间的浪费。

2 内核链表实现

Linux内核中有关链表操作的源代码如下：[源代码网址][Link 2]

/*对双向链表进行初始化操作*/
    #define LIST_HEAD_INIT(name) { &(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;
    }
    
    /*向链表中插入一个元素，准确来说是将new元素插在prev和next元素的中间*/
    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;
    }
    
    /*向链表头部插入元素，新插入的元素将成为第一个元素。准确来说是将new元素插入到链表第一个元素之前，也就是head之后*/
    static inline void list_add(struct list_head *new, struct list_head *head)
    {
    	__list_add(new, head, head->next);
    }
    
    /*向链表尾部插入元素，新插入的元素将成为链表中最后一个元素，也就是head的prev指向的元素*/
    static inline void list_add_tail(struct list_head *new, struct list_head *head)
    {
    	__list_add(new, head->prev, head);
    }
    
    /*替换链表中的某个元素，其中old为要替换的元素，new表示用于替换old的元素
    如果old元素为空，它将会被覆盖（If @old was empty, it will be overwritten.）。
    也就是说，如果old是链表中唯一一个元素，那么这个链表就会被替换*/
    static inline void list_replace(struct list_head *old,
    				struct list_head *new)
    {
    	new->next = old->next;
    	new->next->prev = new;
    	new->prev = old->prev;
    	new->prev->next = new;
    }
    
    /*判断list元素是否为链表中的最后一个元素*/
    static inline int list_is_last(const struct list_head *list,
    				const struct list_head *head)
    {
    	return list->next == head;
    }
    
    /*判断链表是否为空*/
    static inline int list_empty(const struct list_head *head)
    {
    	return head->next == head;
    }
    
    /*判断一个链表中是否只有一个元素*/
    static inline int list_is_singular(const struct list_head *head)
    {
    	return !list_empty(head) && (head->next == head->prev);
    }
    
    /*遍历链表，head表示要遍历的链表，pos表示遍历使用的游标*/
    #define list_for_each(pos, head) \
    	for (pos = (head)->next; pos != (head); pos = pos->next)
    
    /*逆序遍历一个链表，head表示要遍历的链表，pos表示遍历使用的游标*/
    #define list_for_each_prev(pos, head) \
    	for (pos = (head)->prev; pos != (head); pos = pos->prev)
    
    /*安全的遍历一个链表，head表示要遍历的链表，pos表示要遍历的链表的游标，n用来临时存储链表节点
    实际上，在遍历链表的时候，可能会发生正在遍历的元素被移除，为此，可以临时保存下一个要遍历的链表节点
    */
    #define list_for_each_safe(pos, n, head) \
    	for (pos = (head)->next, n = pos->next; pos != (head); \
    		pos = n, n = pos->next)
    
    /*安全的逆序遍历一个链表节点，head表示要遍历的链表，pos表示遍历使用的游标，n用来临时存放链表节点*/
    #define list_for_each_prev_safe(pos, n, head) \
    	for (pos = (head)->prev, n = pos->prev; \
    	     pos != (head); \
    	     pos = n, n = pos->prev)

上面是链表的一些基本的方法，关于这些方法的一些简单说明都已经写在注释中了，这些方法也很容易明白。简单画了一张插入节点的图，对应\_\_list\_add方法：

![70 2][]

下面重点说一下list\_del这个方法，这个方法的定义如下：[源代码网址][Link 3]

/*从链表中删除一个元素*/
    static inline void __list_del(struct list_head * prev, struct list_head * next)
    {
    	next->prev = prev;
    	prev->next = next;
    }
    
    #ifndef CONFIG_DEBUG_LIST
    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;
    }
    #else
    extern void __list_del_entry(struct list_head *entry);
    extern void list_del(struct list_head *entry);
    #endif

从上面的代码中不难看出list\_del(entry)其实就是entry元素从链表中删除，但是下面的两行代码需要解释一下：

entry->next = LIST_POISON1;
    entry->prev = LIST_POISON2;

关于LIST\_POISON1和LIST\_POISON2的宏定义如下：

/*
     * 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 *) 0x100 + POISON_POINTER_DELTA)
    #define LIST_POISON2  ((void *) 0x200 + POISON_POINTER_DELTA)

这里为什么不将entry->next=NULL;entry->prev=NULL;而是将它们置成LIST\_POISON1和LIST\_POISON2呢？我们先看一下关于LIST\_POISON1和LIST\_POISON2的注释，翻译过来就是：

这些非空指针在正常情况下会导致页面错误，用于验证没有人使用非初始化链表项。

页面错误这的就是缺页中断，使用entry->next=LIST\_POISON1;entry->LIST\_POISON2;应该是在删除链表元素的时候，如果该链表节点已经被删除，那么就可以进行提示了。也就是说，在普通环境中，用来验证所有的链表节点都已经被初始化。

看到上面关于Linux内核链表的介绍，你可能会突然意识到一个问题：

一个链表节点中只有prev和next域，我们的数据放到哪里呢？其实Linux内核中的链表的使用是有技巧的。比如我们定义一个普通的entry元素，元素中包含data和desc连个属性，如果使用linux内核链表，我们该怎么做呢？答案如下：

struct entry{
        int data;
        char *desc;
        list_head list;
    }

关于上面定义的链表，就是我们一开始提出来的Linux内核链表的使用，也就是下面的图。

![70 1][]

考虑一个问题，我们现在要对上面的这个链表进行遍历，并且在遍历的时候读取data和desc的值，该怎么做呢？

看一个例子：

/**
     * container_of - cast a member of a structure out to the containing structure
     * @ptr:	the pointer to the member.
     * @type:	the type of the container struct this is embedded in.
     * @member:	the name of the member within the struct.
     *
     */
    #define container_of(ptr, type, member) ({			\
    	const typeof( ((type *)0)->member ) *__mptr = (ptr);	\
    	(type *)( (char *)__mptr - offsetof(type,member) );})
    /**
     * 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_struct within the struct.
     */
    #define list_entry(ptr, type, member) \
    	container_of(ptr, type, member)
    
    #define list_for_each_safe(pos, n, head) \
    	for (pos = (head)->next, n = pos->next; pos != (head); \
    		pos = n, n = pos->next)
    
    struct entry{
    	int data;
    	char *desc;
    	list_head list;
    }
    
    struct entry my_entry;
    struct entry *ep;
    struct list_head *this, *next;
    
    list_for_each_safe(this, next, &my_entry) {
    	ep = list_entry(this, struct entry, list);
            //在这里已经获取到当前遍历的元素，并且是struct entry类型，也就是ep
            //所以这里可以通过ep->data，ep->desc来获取到data、desc的值
            //to do ......
    }

其实上面操作的重点是container\_of宏定义，下面我们结合上面的代码重点来看一下这个宏定义：

我们将ptr=this,type=struct entry,member=list带入上面的container\_of(ptr,type,member)宏定义，得到结果如下：

container_of(this, struct entry, list) ({			\
    	const typeof( ((struct entry *)0)->list ) *__mptr = (this);	\
    	(struct entry *)( (char *)__mptr - offsetof(struct entry,list) );})

下面我们来一行一行的分析一下这个展开后的宏，首先看展开后的宏的第一个分号前的那一句：

const typeof(      ((struct entry *)0)->list    )    * __mptr = (this);

为了便于观察，我将括号做了一下切分，接下来一点一点的分析，typeof里面的内容不难理解，就是将0地址强制转换成struct entry类型，这种做法你获取不太清楚，举个常见的例子：  ((struct entry \*)&my\_entry)这样获取容易理解一下，&my\_entry其实就是个地址，说白了就是一个数字，只不过上面((struct entry \*)0)中是直接将0当做地址了。typeof在内核中很常见，它的作用就是根据变量来获取变量的类型，所以const typeof(  ((struct entry \*)0)->list )这一句的结果就是list\_head类型，也就是struct entry结构体中list元素的类型。所以const typeof( ((struct entry \*)0)->list )  \* \_\_mptr = (this);这一句就相当于list\_head \*\_\_mptr=this;而这个this，我们之前的定义就是list\_head \*this;这一句不难理解。接下来看下面一句：

(struct entry *)( (char *)__mptr - offsetof(struct entry,list) );

其中offsetof函数是获取member在type中的偏移量，在这里就是获取list在struct entry结构体中的偏移量，这里为什么要将\_\_mptr再转换成char \*类型呢？其实为了在做地址加减是时候保证不会出错，不转其实是会出问题的，想一想为什么？所以(char \*)\_\_mptr - offsetof(struct entry,list)就获取到了整个entry元素所在的地址。所以container\_of这个宏定义在上面的例子中的功能很简单：就是根据struct entry元素中list的地址来获取整个entry的地址，获取到整个entry的地址之后，我们就可以访问entry元素中的其他属性了，在上面的例子中就是访问entry元素中的data、desc属性。

好了，关于Linux内核链表的介绍就写到这里。

本人能力有限，文中如有错误，请您批评指正，邮箱：ieyaolulu@163.com，谢谢！

[70]: /images/20220517/5c2b0b90a7e5437a8ad3caa9bfbde0a3.png
[70 1]: /images/20220517/8f5301d435814fcaaa871e2819ace4de.png
[Link 1]: https://elixir.bootlin.com/linux/v3.14.69/source/include/linux/types.h#L185
[Link 2]: https://elixir.bootlin.com/linux/v3.14.69/source/include/linux/list.h#L60
[70 2]: /images/20220517/976fd63009e24fa8aa3a46dc2d0b2751.png
[Link 3]: https://elixir.bootlin.com/linux/v3.14.69/source/include/linux/list.h#L104