linux内核list解析

ゝ一纸荒年。 2022-08-20 12:05 183阅读 0赞

在linux内核里又有一个非常重要的数据结构，他就是双向循环链表list，定义在linux/list.h，这个数据结构可以说是linux内核中使用最广泛的数据结构了，list的理解对于我们阅读和理解内核有重大的意义，接下来我们一起看一下list.h，看一下这个神奇的数据结构吧。  
首先看一下这个数据结构的定义

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

里面定义了两个成员，都是指向list\_head结构体的指针，一个是指向掐你一个结构体的指针，另一个是指向后一个结构体的指针。

#define LIST_HEAD_INIT(name) { &(name), &(name) }

这个宏的作用是返回一个初始化list\_head结构体，传入的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;
    }

这个内敛函数和上一个宏的作用基本一致，就是穿入一个要初始化的链表，把他的成员指针都指向他自己。

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;
    }

这个函数的作用是插入一个链表节点到一个位置，传入的参数分别是新插入的节点，插入位置的前边的节点，插入位置的后边的节点。首先让后边的节点的prev成员指向new节点，然后new的next成员指向next，这样新插入的节点和后边节点的联系就算建立完成了，然后new的prev成员指向prev节点，然后prev节点的next成员指向new，至此插入就算结束了。

static inline void list_add(struct list_head *new, struct list_head *head)
    {
    	__list_add(new, head, head->next);
    }

这个函数调用上边我们解释过的函数，只是参数穿入了一个head指针，就是插入到head的后边，也就是链表的头部后边那一个位置。

static inline void list_add_tail(struct list_head *new, struct list_head *head)
    {
    	__list_add(new, head->prev, head);
    }

这个函数的作用是把一个new节点插入到head的最后一个点的位置，由于list\_head是双向链表，所以head->prev就是最后一个节点，直接传参，调用\_\_list\_add就ok了。

static inline void __list_del(struct list_head * prev, struct list_head * next)
    {
    	next->prev = prev;
    	prev->next = next;
    }

这个函数是linux内核内建的函数，也就是不允许其他使用者在其他的文件使用的（一般\_\_开头的都是），传入参数是要删除节点的前边和后边节点，删除其实很简单，只需要把前边的next指向后边，后边节点的prev指向前边即可。

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

链表删除函数，传入参数是要删除的节点，调用上一个我们解释过的函数，晚上删除，删除后的节点的指针赋值为LIST\_POISON1和LIST\_POISON2宏，完成删除。LIST\_POISON1和LIST\_POISON2定义在 include/linux/list.h文件

/*
     * 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)
    #define LIST_POISON2  ((void *) 0x00200200)

意思就是说这个宏代表防止被使用，估计linux内核对这个值有特殊的保护，可以不被意外访问到吧。

#define list_entry(ptr, type, member) \
    	container_of(ptr, type, member)

list\_entry这个宏的作用是传入这个list\_head的指针，还有list\_head所在结构体的类型，和list\_head的成员变量名字，就可以返回list\_head所在结构体的指针。

#define list_for_each(pos, head) \
    	for (pos = (head)->next; prefetch(pos->next), pos != (head); \
            	pos = pos->next)

这个宏的作用是遍历list，pos是一个list\_head指针，head就是链表的头指针，看定义也可以看出，就是一个简单的遍历for循环，当pos->next值为空的时候退出循环。