linux kernel 中双向链表详解(一)_list_first_entry

1.概览

  list_head 在kernel代码中非常的常见，其本身则是一个双向链表，在使用时只需要将其嵌入到任意结构体中，就可以实现栈/队列的数据结构。并且删除，添加的操作时间复杂度都是O(1)。

2.list_head之栈实现

 前面提到过，嵌入list_head可以实现的栈(stack)数据结构。下面的代码实现很简单，其功能则是在驱动的初始化函数中将数据入栈并显示当前栈信息，在驱动的卸载函数中出栈数据并释放内存。随意定义个苹果数据结构，并将head_list嵌入其中，定义如下

struct apple {
	struct list_head list;
	int id;
};
1
2
3
4

  id则是唯一的，代表一个苹果的编号。

2.1 初始化链表头–LIST_HEAD

  为了让队列显的有序，我们单独定义一个head_list作为链表头。
  kernel 中代码如下

static LIST_HEAD(apple_top);
1

  使用kernel的帮助宏申明一个名为 apple_top 的 list_head，添加static修饰为了限制其作用域为本文件内。对于 LIST_HEAD 的实现如下

//file:kernel/include/linux/list.h
#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \
	struct list_head name = LIST_HEAD_INIT(name)
        || 展开如下
        \/
struct list_head name = { &name/* next */, &name /* prev */}
1
2
3
4
5
6
7
8

  从上可知，使用LIST_HEAD申明的head_list为指向自己的空链表，示意图如下

2.2 入栈–list_add

 栈的主要特性就是先入后出，使用list_add添加的项则是符合这种特性的，下面是其实现

//file:kernel/include/linux/list.h
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;
	WRITE_ONCE(prev->next, new);
}

static inline void list_add(struct list_head *new, struct list_head *head)
{
	__list_add(new, head, head->next);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

  list_add的实现依赖于__list_add，而对于__list_add的功能描述在kernel中如下

Insert a new entry between two known consecutive entries.
1

  从实现和内核描述可知，__list_add的功能就是将 new 项添加到项preve和next之间，结合list_add的代码可知其含义为将new添加到 head和head->next之间，图示如下

  使用list_add添加两项项后的示例图则如下

  使用list_add添加多项后的示例图则如下

2.3 出栈

  出栈的功能则分为两个部分，其一是定位栈顶此处使用list_first_entry，其二是删除栈顶项此处使用list_del。

2.3.1 栈的遍历–list_first_entry

//file:kernel/include/linux/list.h
#define list_first_entry(ptr, type, member) \
	list_entry((ptr)->next, type, member)
        container_of(ptr, type, member)
1
2
3
4

  ptr:
    则是链表头的指针，此处对应 &apple_top
  type:
    则是链表中具体项所对应的结构体，此处对应 struct apple
  member:
    则是head_list内嵌于具体项的名字，此处对应由struct apple可知为list
  实现上也比较简单，最终使用container_of来返回链表头的next项的。
  下面是list_first_entry的使用示例，用于返回栈顶项指针

struct apple *it = list_first_entry(&apple_top, struct apple, list);
1

2.3.1 删除一项–list_del

  list_del实现也非常简单，就是去头去尾，接头尾的操作。下面给出简单的调用流程

//file:kernel/include/linux/list.h
list_del(struct list_head *entry)
	__list_del_entry(entry);
        __list_del(entry->prev, entry->next)
            next->prev = prev;
            WRITE_ONCE(prev->next, next);
	entry->next = LIST_POISON1;
	entry->prev = LIST_POISON2;
1
2
3
4
5
6
7
8

  配合上面提到的list_first_entry，也就实现了出栈的功能，代码如下

struct apple *it = list_first_entry(&apple_top, struct apple, list);
list_del(&it->list);
1
2

2.4 代码实现

2.4.1 基本代码实现

struct apple {
	struct list_head list;
	int id;
};
static LIST_HEAD(apple_top);
static int __init list_test_drv_init()
{
	struct apple *tmp_apple = NULL;
	int count = 0;

	for( count = 0 ; count < APPLE_STACK_MAX; ++count) {

		tmp_apple = kzalloc(sizeof(struct apple), GFP_KERNEL);
		if(tmp_apple != NULL) {
			tmp_apple->id = count;
			list_add(&tmp_apple->list, &apple_top);
			LIST_TEST_INFO("push:apple->id:%d", tmp_apple->id);
			tmp_apple = NULL;
		}
	}
	return 0;
}

static void __exit list_test_drv_exit()
{
	struct apple *it = NULL;

	while(!list_empty(&apple_top)) {
		it = list_first_entry(&apple_top, struct apple, list);
		if(it == NULL){
			LIST_TEST_INFO("it is NULL");
			continue;
		}
		LIST_TEST_INFO("pop:apple->id:%d", it->id);
		list_del(&it->list);
		kzfree(it);
		it = NULL;
	}
}
module_init(list_test_drv_init);
module_exit(list_test_drv_exit);
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
41

  代码实现基本逻辑，在模块加载的时候会申请APPLE_STACK_MAX个apple，并压入栈中。
在模块推出后，则循环出栈直到队列为空。

2.4.1 完整源码

https://gitee.com/solo-king/linux-kernel-base-usage/blob/master/flagstaff/listStackTest.c
1

2.5 执行结果

2.5.1 入栈信息

board:/ # insmod /data/listStackTest.ko
[20749.835310] listTest:list_test_drv_init,54:push:apple->id:1
[20749.835317] listTest:list_test_drv_init,54:push:apple->id:2
[20749.835324] listTest:list_test_drv_init,54:push:apple->id:3
[20749.835331] listTest:list_test_drv_init,54:push:apple->id:4
[20749.835337] listTest:list_test_drv_init,54:push:apple->id:5
[20749.835344] listTest:list_test_drv_init,54:push:apple->id:6
[20749.835351] listTest:list_test_drv_init,54:push:apple->id:7
[20749.835357] listTest:list_test_drv_init,54:push:apple->id:8
[20749.835367] listTest:list_test_drv_init,54:push:apple->id:9
1
2
3
4
5
6
7
8
9
10

  从log能看出，栈顶的apple id为9，栈低为0。

2.5.1 出栈信息

board:/ # rmmod listStackTest
[20773.041927] listTest:list_test_drv_exit,73:pop:apple->id:9
[20773.041957] listTest:list_test_drv_exit,73:pop:apple->id:8
[20773.041966] listTest:list_test_drv_exit,73:pop:apple->id:7
[20773.041978] listTest:list_test_drv_exit,73:pop:apple->id:6
[20773.041986] listTest:list_test_drv_exit,73:pop:apple->id:5
[20773.041994] listTest:list_test_drv_exit,73:pop:apple->id:4
[20773.042003] listTest:list_test_drv_exit,73:pop:apple->id:3
[20773.042012] listTest:list_test_drv_exit,73:pop:apple->id:2
[20773.042022] listTest:list_test_drv_exit,73:pop:apple->id:1
[20773.042030] listTest:list_test_drv_exit,73:pop:apple->id:0
1
2
3
4
5
6
7
8
9
10
11

  从log也是能看出，是符合栈数据结构的特性–先入后出的。

3.list_head之队列实现

  队列的实现和栈的实现，在list_head双向链表实现中唯一的不同就是入列使用 list_add_tail，压栈使用 list_add 仅此而已。那么只要分析下 list_add_tail和 list_add实现的不同点即可，下面是对应代码

//file:kernel/include/linux/list.h
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
	__list_add(new, head->prev, head);
}
1
2
3
4
5

  可见，list_add_tail则是将new放置在链表头的前一个项和链表头之间，和list_add的实现正好相反。

3.1 入列第一项

  下图是入列了第一个项目后链表的示意图

3.2 入列第二项

  下图是入列了第二个项目后链表的示意图

3.3 入列多项

  下图是入列了多项目后链表的示意图

  所以配合上 list_first_entry接口，每次返回的都是head_list.next项目，所以其访问序列和队列的特性是符合的，即先进先出。

3.4 执行结果

3.4.1 入列信息

board:/ # insmod  /data/listQueueTest.ko
[29592.571532] listTest:list_test_drv_init,39:enqueue:apple->id:0
[29592.571539] listTest:list_test_drv_init,39:enqueue:apple->id:1
[29592.571543] listTest:list_test_drv_init,39:enqueue:apple->id:2
[29592.571549] listTest:list_test_drv_init,39:enqueue:apple->id:3
[29592.571555] listTest:list_test_drv_init,39:enqueue:apple->id:4
[29592.571560] listTest:list_test_drv_init,39:enqueue:apple->id:5
[29592.571564] listTest:list_test_drv_init,39:enqueue:apple->id:6
[29592.571570] listTest:list_test_drv_init,39:enqueue:apple->id:7
[29592.571575] listTest:list_test_drv_init,39:enqueue:apple->id:8
[29592.571579] listTest:list_test_drv_init,39:enqueue:apple->id:9
1
2
3
4
5
6
7
8
9
10
11

3.4.2 出列信息

board:/ # rmmod listQueueTest
[29598.406872] listTest:list_test_drv_exit,56:dequeue:apple->id:0
[29598.406898] listTest:list_test_drv_exit,56:dequeue:apple->id:1
[29598.406907] listTest:list_test_drv_exit,56:dequeue:apple->id:2
[29598.406915] listTest:list_test_drv_exit,56:dequeue:apple->id:3
[29598.406925] listTest:list_test_drv_exit,56:dequeue:apple->id:4
[29598.406934] listTest:list_test_drv_exit,56:dequeue:apple->id:5
[29598.406943] listTest:list_test_drv_exit,56:dequeue:apple->id:6
[29598.406952] listTest:list_test_drv_exit,56:dequeue:apple->id:7
[29598.406959] listTest:list_test_drv_exit,56:dequeue:apple->id:8
[29598.406967] listTest:list_test_drv_exit,56:dequeue:apple->id:9
1
2
3
4
5
6
7
8
9
10
11

3.5 完整源码

https://gitee.com/solo-king/linux-kernel-base-usage/blob/master/flagstaff/listQueueTest.c
1