• 详解linux内核链表list_head及其接口应用

    Linux内核中的链表通常都组织成双向循环链表，不同于一般意义上的链表，这里的链表节点只含有链表指针（next和prev），没有链表的数据。Linux内核中使用的链表源代码位于 include/linux/list.h中，下面详细叙述。

    1. 链表数据结构 list_head 的定义：

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

    • 1
    • 2
    • 3

    【注意】只有前后节点指针，没有数据 ！

    2. 链表的声明和初始化

    2.1静态方法——编译时

    #define LIST_HEAD_INIT(name) { &(name), &(name) } // 链表的pre和next指针都指向了节点自己的首地址 
#define LIST_HEAD(name) \
	struct list_head name = LIST_HEAD_INIT(name)  

    • 1
    • 2
    • 3

    2.2动态方法——运行时

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

    • 1
    • 2
    • 3
    • 4
    • 5

    图示：

    image-20220821203053778

    3. 插入/删除/合并

    3.1插入

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

    • 1
    • 2
    • 3
    • 4

    依次插入数据1、数据2、数据3

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

    • 1
    • 2
    • 3
    • 4

    依次插入数据1、数据2、数据3

    • 可以看到他们调用了相同的 __list_add 函数：
    //将链表节点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;  
} 

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    3.2 删除

    • 对链表的删除操作函数有两种：list_del函数和list_del_init函数：
    3.2.1 list_del
    static inline void list_del(struct list_head *entry) // entry：要删除的链表的首地址  
{  
	__list_del(entry->prev, entry->next); // 等价于__list_del_entry(entry)  
	entry->next = LIST_POISON1;  
	entry->prev = LIST_POISON2;  
} 

/* 下面是LIST_POISON1和LIST_POISON2的出处：*/
#ifdef CONFIG_ILLEGAL_POINTER_VALUE
# define POISON_POINTER_DELTA _AC(CONFIG_ILLEGAL_POINTER_VALUE, UL)
#else
# define POISON_POINTER_DELTA 0
#endif
/* 
 * 通常情况下，非空指针会导致页错误，用于验证没有初始化的list元素。
 * 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)

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    • 将链表节点entry从链表中删除后，list_del函数中又将entry的next和prev指针指向了LIST_POISON1和LIST_POISON2位置，使得以后若再对他们进行访问都将引起页故障，以确保不在链表中的节点项不可访问。

      image-20220821210440988

    3.2.2 list_del_init
    static inline void list_del_init(struct list_head *entry)  
{  
	__list_del_entry(entry);  
	INIT_LIST_HEAD(entry); 		// 运行中初始化链表节点  
} 

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 将链表节点entry从链表中删除后，list_del_init函数中又将entry重新初始化了（next和prev指针指向了自己）。在此不再画图，唯一的不同是把删除下来的图的next和prev指针指向了自己的首地址
    • 他们调用了相同的 __list_del 函数
    static inline void __list_del(struct list_head * prev, struct list_head * next)  
{  
	next->prev = prev;  
	prev->next = next;  
} 

    • 1
    • 2
    • 3
    • 4
    • 5

    3.3 替换

    对链表的替换操作有两个：list_replace函数和list_replace_init函数：

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


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    image-20220821210913534

    3.3.2 list_replace_init
    static inline void list_replace_init(struct list_head *old, struct list_head *new)  
{  
    list_replace(old, new);  
    INIT_LIST_HEAD(old);  
} 

    • 1
    • 2
    • 3
    • 4
    • 5

    list_replace_init函数的图形在此处也不再画，区别就是多了初始化换下来的old节点

    3.4 搬移

    搬移的含义是将原本属于一个链表的节点移动到另一个链表的操作，有两个函数：list_move函数和list_move_tail函数：

    3.4.1 list_move
    /*
 * list_move:把节点list从原先链表上搬移到另一个链表head的头部 
 * @list: 我们要移动的节点 
 * @head: 要移动到的另外的一个链表头 
 */  
static inline void list_move(struct list_head *list, struct list_head *head)  
{  
    __list_del_entry(list);  
    list_add(list, head);  
} 

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    3.4.2 list_move_tail
    /*
 * list_move_tail:把节点list从原先链表上搬移到另一个链表head的尾部 
 * @list: the entry to move 
 * @head: the head that will follow our entry 
 */  
static inline void list_move_tail(struct list_head *list, struct list_head *head)  
{  
	__list_del_entry(list);  
	list_add_tail(list, head);  
} 

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    3.5 合并

    合并在这里的意思就是合并了，是将两个独立的链表合并成为一个链表，合并的时候根据合并的位置的不同可以分为：

    • 合并到头部的 list_splice函数
    • 合并到尾部的 list_splice_tail函数
    3.5.1 list_splice
    /* 
 * list_splice: join two lists, this is designed for stacks 
 * @list: the new list to add. 
 * @head: the place to add it in the first list. 
 */  
static inline void list_splice(const struct list_head *list, struct list_head *head) {  
	if (!list_empty(list))  
		__list_splice(list, head, head->next);  
}  

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    image-20220821214130319

    • 假设当前有两个链表，表头分别是list1和list2（都是struct list_head变量），当调用list_splice(&list1,&list2)时，只要list1非空，list1链表的内容将被挂接在list2链表上，位于list2和list2.next（原list2表的第一个节点）之间。新list2链表将以原list1表的第一个节点为首节点，而尾节点不变。
    3.5.2 list_splice_tail
    /* 
 * list_splice_tail - join two lists, each list being a queue 
 * @list: the new list to add. 
 * @head: the place to add it in the first list. 
 */  
static inline void list_splice_tail(struct list_head *list, struct list_head *head) 
{  
    if (!list_empty(list))  
        __list_splice(list, head->prev, head);  
} 

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 假设当前有两个链表，表头分别是list1和list2（都是struct list_head变量），当调用list_splice_tail(&list1,&list2)时，只要list1非空，list1链表的内容将被挂接在list2链表上，位于list2尾节点和list2（原list2头）之间。新list2链表将以原list1表的最后一个节点为尾节点，而头节点不变。
    3.5.3 list_splice_init
    static inline void list_splice_init(struct list_head *list, struct list_head *head) 
{  
	if (!list_empty(list)) {  
		__list_splice(list, head, head->next);  
		INIT_LIST_HEAD(list);             <--- 跟list_splice唯一的不同  
	}  
} 

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    3.5.4 list_splice_tail_init
    static inline void list_splice_tail_init(struct list_head *list, struct list_head *head)  
{  
	if (!list_empty(list)) {  
		__list_splice(list, head->prev, head);  
		INIT_LIST_HEAD(list);     		<--- 跟list_splice_tail唯一的不同  
	}  
} 

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 共同的函数__list_splice和list_empty
    //将链表list插入到另一个链表的prev和next节点之间
static inline void __list_splice(const struct list_head *list, struct list_head *prev, struct list_head *next)  
{
    struct list_head *first = list->next;  
	struct list_head *last = list->prev;  

	first->prev = prev;  
	prev->next = first;  

	last->next = next;  
	next->prev = last;  
}  

//判断链表head是否为空
static inline int list_empty(const struct list_head *head)  
{  
    return head->next == head;  
} 

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    4. 找到链表中的数据

    前边提到的函数都是操作的链表节点的入口，但是对于我们真正有意义的是节点上的数据，链表的头上没有数据，其他的节点上都是带有数据的。如何从一个链表节点的入口得到节点的数据呢？要用到以下的函数

    list_entry函数：

    /*
 * list_entry - 通过链表地址获得包含该链表的结构体的地址 
 * @ptr:    member的首地址 
 * @type:   容器的类型 
 * @member: 要得到他的容器的某个成员 
 */  
#define list_entry(ptr, type, member) \
	container_of(ptr, type, member)  

#define container_of(ptr, type, member) ({ \
	const typeof( ((type *)0)->member ) *__mptr = (ptr); \ 
		(type *)( (char *)__mptr - offsetof(type,member) );})  

// 将数据结构体放到0地址处，天然的结构体中成员的首地址就是成员在结构体中的偏移量(字节)
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER) 

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    举例：

    main.c

    #include   
#include 

LIST_HEAD(device_list);  

typedef struct device_struct  
{  
    unsigned char *devname;  
    struct list_head entry;  
} device_struct_s;  

int main(int argc, const char *argv[])  
{  
    device_struct_s led;  
    device_struct_s *ledp;  
    led.devname = "led";  

    /* 添加到链表的前边 */  
    list_add(&led.entry, &device_list);  

    /* 得到含有链表节点的数据结构体的首地址 */  
    ledp = list_entry(device_list.next, device_struct_s, entry);  
    printf("led.devname = %s\n", ledp->devname);  
    return 0;  
}  

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    5. 遍历链表

    对linux内核的遍历可以分为遍历链表和遍历链表中的结构体：

    从头开始遍历链表，list_for_each宏;

    从头开始遍历链表中的结构体，list_for_each_entry宏;

    5.1 遍历list_head链表

    /*
 * list_for_each - 迭代/遍历 链表 
 * @cursor: list_head链表指针. 
 * @head:   要遍历的list_head链表的头
 */  
#define list_for_each(cursor, head) \ 
	for (cursor = (head)->next; cursor != (head); cursor = cursor->next)   

/*
 *next: 指向当前crusor指向的结构体的下一个结构体
 */
#define list_for_each_safe(cursor, next, head) \ 
	for (cursor = (head)->next,next = cursor->next;\
         cursor != (head);\
         cursor = next,next = cursor->next)  

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 注意：当我们采用list__for_each()函数遍历list时，如果我们删除元素（即执行list_del(cursor);），就会导致cursor指向的元素的prev=LIST_POISON1，next=LIST_POISON2，当执行到cursor=cursor->next时，就会出现错误。
      • 但是当我们使用list_for_each_safe()函数遍历list时，如果我们也删除元素后，会执行cursor=next，而next=cursor->next（注意：next=cursor->next中的cursor是删除的那个元素），所以虽然删除了元素cursor，但是执行了cursor=next后，cursor指向了正确的遍历位置，所以使用list_for_each_safe()函数遍历list时并不会出现错误。
      • list_for_each_safe()在遍历时之所以不会出现错误，是因为我们使用了next暂时保存了cursor（被删除元素所指向的下一个元素），所以用这个宏定义，不会出现遍历时删除元素的错误。

    5.2 遍历“含有list_head项的结构体‘链表

    /*
 * list_for_each_entry  - 遍历含链表节点入口的结构体 
 * @cursor: 指向“含list_head结构的结构体”的指针. 
 * @head:   要遍历的结构体链表的头节点中的list_head项的指针
 * @member: 结构体中list_head项的名字 
 */  
#define list_for_each_entry(cursor, head, member) \
	for (cursor = list_entry((head)->next, typeof(*cursor), member);\
		&cursor->member != (head);\  
		cursor = list_entry(cursor->member.next, typeof(*cursor), member)) 
/*
 *next: 指向当前crusor指向的结构体的下一个结构体;
 */
#define list_for_each_entry_safe(cursor, next, head, member) \
	for (cursor = list_entry((head)->next, typeof(*cursor), member),\
		next = list_entry(cursor->member.next, typeof(*cursor), member);\
		&cursor->member != (head);\  
		cursor = next, next = list_entry(next->member.next, typeof(*cursor), member)) 

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    • 相比于list_for_each_entry，list_for_each_entry_safe用指针next对链表的下一个数据结构进行了临时存储，所以同理，如果在遍历链表的时候需要做删除链表中的当前项操作时，用list_for_each_entry_safe可以安全的删除，而不会影响接下来的遍历过程（用next指针可以继续完成接下来的遍历， 而list_for_each_entry则无法继续遍历，删除后会导致无法继续遍历）。

    • 举例

    #include   
#include 

LIST_HEAD(device_list);  //定义并初始化了一个list_head类型的变量device_list

typedef struct device_struct  
{  
	unsigned char *devname;  
	struct list_head entry;  
} device_struct_s;  

int main(int argc, const char *argv[])  
{  
	device_struct_s led, gpio, beep, *tmp;  

    led.devname = "led";  
    gpio.devname = "gpio";  
    beep.devname = "beep";  

    /* 一个一个往链表的头部添加 */  
    list_add(&led.entry, &device_list);  // device_list——>led.entry
    list_add(&gpio.entry, &device_list); // device_list——>gpio.entry——>led.entry 
    list_add(&beep.entry, &device_list); // device_list——>beep.entry——>gpio.entry——>led.entry 

    /* 1. 遍历链表 */  
    struct list_head *cursor;  
    list_for_each(cursor, &device_list)  
    {  
        tmp = list_entry(cursor, device_struct_s, entry);  
        printf("tmp.devname = %s\n", tmp->devname);  
    }  

    /* 2. 遍历含链表的结构体 */  
    device_struct_s *cursor2;  
    list_for_each_entry(cursor2, &device_list, entry)  
    {  
        printf("cursor2.devname = %s\n", cursor2->devname);  
    }  
        return 0;  
}  

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40

    • 输出结果

      tmp.devname = beep  
tmp.devname = gpio  
tmp.devname = led  
j.devname = beep  
j.devname = gpio  
j.devname = led

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6

    另外：

    1. linux内核的链表中提供了反向遍历链表的宏list_for_each_prev和list_for_each_entry_reverse，他们分别是list_for_each和list_for_each_entry的反方向的实现，使用方法完全一样。
    2. 如果遍历不是从链表头开始，而是从已知的某个节点pos开始，则要使用list_for_each_entry_continue宏（使用方法同list_for_each_entry宏）。
    3. 如果想实现如果pos有值则从pos开始遍历，如果没有则从链表的头开始遍历，为此，Linux专门提供了一个list_prepare_entry(pos,head,member)宏，将它的返回值作为list_for_each_entry_continue()的pos参数，就可以满足这一要求。
    • 我们将list_for_each_prev和list_for_each_entry_reverse的代码和执行结果也写下来：
    /* 3. 反向遍历链表的入口的首地值 */  
printf("list_for_each_prev()\n");  
struct list_head *cursor3;  
list_for_each_prev(cursor3, &device_list)  
{  
    tmp = list_entry(cursor3, device_struct_s, entry);  
    printf("tmp.devname = %s\n", tmp->devname);  
}  


/* 4. 反向遍历含链表的入口的结构体的首地值 */ 
printf("list_for_each_reverse()\n");  
device_struct_s *cursor4;  
list_for_each_entry_reverse(cursor4, &device_list, entry)  
{  
	printf("cursor4.devname = %s\n", g->evname);  
}  

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    结合上边代码的执行结果如下：

    list_for_each_prev()   <--- 可以看到遍历结果是从尾部遍历到头部  
tmp.devname = led  
tmp.devname = gpio  
tmp.devname = beep  
list_for_each_reverse()   <--- 可以看到遍历结果是从尾部遍历到头部  
cursor4.devname = led  
cursor4.devname = gpio  
cursor4.devname = beep  

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    ;
    }

    /* 4. 反向遍历含链表的入口的结构体的首地值 */
    printf(“list_for_each_reverse()\n”);
    device_struct_s *cursor4;
    list_for_each_entry_reverse(cursor4, &device_list, entry)
    {
    printf(“cursor4.devname = %s\n”, g->evname);
    }

    
结合上边代码的执行结果如下：

```bash
list_for_each_prev()   <--- 可以看到遍历结果是从尾部遍历到头部  
tmp.devname = led  
tmp.devname = gpio  
tmp.devname = beep  
list_for_each_reverse()   <--- 可以看到遍历结果是从尾部遍历到头部  
cursor4.devname = led  
cursor4.devname = gpio  
cursor4.devname = beep  

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    参考文章：【内核数据结构】 内核链表分析_沧海一笑的技术博客_51CTO博客

  • 相关阅读:
    络达开发---UI定义+自定义按钮事件
    一种计算整数位1个数的新方法
    go 指针
    python数据管理和分析
    Redis在计数器和人员记录的事务操作应用
    视频去LOGO的方法，AI自动完美地去除视频LOGO
    Python编程：正则表达式详解
    一行代码修复100vh bug | 京东云技术团队
    向毕业妥协系列之机器学习笔记:高级学习算法-神经网络（一）
    JSON
  • 原文地址：https://blog.csdn.net/liangzc1124/article/details/126862414