当前位置:首页 > 嵌入式培训 > 嵌入式学习 > 讲师博文 > 内核链表

内核链表 时间:2018-09-26      来源:未知

在Linux内核中使用了大量的链表结构来组织数据,包括设备列表以及各种功能模块中的数据组织。这些链表大多采用在[include/linux/list.h]实现的一个相当精彩的链表数据结构。

很多linux下的源代码都会使用这个头文件,它里面定义了一个结构,以及定义了和其相关的一组函数,初学嵌入式的同学往往会对内核链表感到一头雾水, 本文详细分析了3.14 内核中链表结构的实现,并通过实例对链表操作接口进行了测试。

一、 链表数据结构简介

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。链表明显的好处就是,常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序,数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点,但是不允许随机存取。链表有很多种不同的类型:单向链表,双向链表以及循环链表。链表可以在多种编程语言中实现。像Lisp和Scheme这样的语言的内建数据类型中就包含了链表的存取和操作。程序语言或面向对象语言,如C,C++和Java依靠易变工具来生成链表。

通常链表数据结构至少应包含两个域:数据域和指针域,数据域用于存储数据,指针域用于建立与下一个节点的联系。

按照指针域的组织以及各个节点之间的联系形式,链表又可以分为单链表、双链表、循环链表等多种类型,下面分别给出这几类常见链表类型的示意图:

1. 单链表

图1 单链表

单链表是简单的一类链表,它的特点是仅有一个指针域指向后继节点(next),因此,对单链表的遍历只能从头至尾(通常是NULL空指针)顺序进行。

2. 双链表

图2 双链表

通过设计前驱和后继两个指针域,双链表可以从两个方向遍历,这是它区别 于单链表的地方。如果打乱前驱、后继的依赖关系,就可以构成"二叉树";如果再让首节点的前驱指向链表尾节点、尾节点的后继指向首节点(如图2中虚线部 分),就构成了循环链表;如果设计更多的指针域,就可以构成各种复杂的树状数据结构。

3. 循环链表

循环链表的特点是尾节点的后继指向首节点。前面已经给出了双循环链表的示意图,它的特点是从任意一个节点出发,沿两个方向的任何一个,都能找到链表中的任意一个数据。如果去掉前驱指针,就是单循环链表。

二、 Linux 3.14内核链表数据结构的实现

链表数据结构的定义很简单(定义文件在linux-3.14-fs4412\include\linux\Types.h中):

和第一节介绍的双链表结构模型不同,这里的list_head没有数据域。在Linux内核链表中,不是在链表结构中包含数据,而是在数据结构中包含链表节点。list_head结构包含两个指向list_head结构的指针prev和next,由此可见,内核的链表具备双链表功能,实际上,通常它都组织成双循环链表。

在数据结构课本中,链表的经典定义方式通常是这样的(以单链表为例):

struct list_node {

struct list_node *next;

ElemType data;

};

在Linux内核链表中,需要用链表组织起来的数据通常会包含一个 struct list_head成员,

struct list_node

{

struct list_head list;

ElemType data;

};

从下图中我们可以看到,这种通用的链表结构避免了为每个数据项类型定义自己的链表的麻烦。

图3 内核链表链表示意图

三、 链表操作接口

1. 声明和初始化

实际上Linux只定义了链表节点,并没有专门定义链表头,那么一个链表结构是如何建立起来的呢?让我们来看看LIST_HEAD(和LIST_HEAD_INIT这2个宏:

当我们用LIST_HEAD(my_list)声明一个名为t的链表头时,它的next、prev指针都初始化为指向自己,这样,我们就有了一个空链表.

Linux用头指针的next是否指向自己来判断链表是否为空:

2. 插入/删除/合并

a) 插入

对链表的插入操作有两种:在表头插入和在表尾插入。Linux为此提供了两个接口:

因为Linux链表是循环表,且表头的next、prev分别指向链表中的第一个和末一个节点,所以,list_add和list_add_tail的区别并不大,实际上,Linux分别用

__list_add(new, head, head->next);

__list_add(new, head->prev, head);

来实现两个接口,可见,在表头插入是插入在head之后,而在表尾插入是插入在head->prev之后。

__list_add的实现如下:

假设有一个新list_node

结构变量new_list_node需要添加到my_list链表头,我们应当这样操作:

list_add(&new_list_node.list, &my_list);

从这里我们看出,my_list链表中记录的并不是new_list_node的地址,而是其中的list元素的地址。如何通过链表访问到new_list_node呢?下面会有详细介绍。

b) 删除

当我们需要删除my_list链表中添加的new_sockopt项时,我们这么操作:

list_del(&new_list_node.list);

被剔除下来的new_list_node.list,prev、next指

针分别被设为LIST_POSITION2和LIST_POSITION1两个特殊值,这样设置是为了保证不在链表中的节点项不可访问--对

LIST_POSITION1和LIST_POSITION2的访问都将引起页故障。与之相对应,list_del_init()函数将节点从链表中解下

来之后,调用LIST_INIT_HEAD()将节点置为空链状态。

c) 搬移

Linux提供了将原本属于一个链表的节点移动到另一个链表的操作,并根据插入到新链表的位置分为两类:

例如list_move(&new_list_node.list,&my_list)会把new_list_node从它所在的链表上删除,并将其再链入my_list的表头。

d) 合并

除了针对节点的插入、删除操作,Linux链表还提供了整个链表的插入功能:

假设当前有两个链表,表头分别是list1和list2(都是 struct list_head变量),当调用list_splice(&list1,&list2)时,只要list1非空,list1链表的内容 将被挂接在list2链表上,位于list2和list2.next(原list2表的第一个节点)之间。新list2链表将以原list1表的第一个节 点为首节点,而尾节点不变。

当list1被挂接到list2之后,作为原表头指针的list1的next、prev仍然指向原来的节点,为了避免引起混乱,Linux提供了一个list_splice_init()函数:

static inline void list_splice_init(struct list_head *list, struct list_head *head);

该函数在将list合并到head链表的基础上,调用INIT_LIST_HEAD(list)将list设置为空链。

3. 遍历

遍历是链表经常的操作之一,为了方便核心应用遍历链表,Linux链表将遍历操作抽象成几个宏。在介绍遍历宏之前,我们先看看如何从链表中访问到我们真正需要的数据项。

a) 由链表节点到数据项变量

我们知道,Linux链表中仅保存了数据项结构中list_head成 员变量的地址,那么我们如何通过这个list_head成员访问到作为它的所有者的节点数据呢?Linux为此提供了一个 list_entry(ptr,type,member)宏,其中ptr是指向该数据中list_head成员的指针,也就是存储在链表中的地址值,type是数据项的类型,member则是数据项类型定义中list_head成员的变量名,例如,我们要访问my_list链表中首个 list_node变量,则如此调用:

list_entry(my_list->next, struct list_node, list);

这里"list"正是nf_sockopt_ops结构中定义的用于链表操作的节点成员变量名。

list_entry的使用相当简单,相比之下,它的实现则有一些难懂:

container_of宏定义在[include/linux/kernel.h]中

offsetof宏定义在[include/linux/stddef.h]中:

size_t终定义为unsigned int(i386)。

这里使用的是一个利用编译器技术的小技巧,即先求得结构成员在与结构中的偏移量,然后根据成员变量的地址反过来得出属主结构变量的地址。

container_of()和offsetof()并不仅用于链表操 作,这里有趣的地方是((type *)0)->member,它将0地址强制"转换"为type结构的指针,再访问到type结构中的member成员。在container_of 宏中,它用来给typeof()提供参数(typeof()是gcc的扩展,和sizeof()类似),以获得member成员的数据类型;在 offsetof()中,这个member成员的地址实际上就是type数据结构中member成员相对于结构变量的偏移量。

b) 遍历宏

以下是一个遍历内核链表节点的实例

……

struct list_head *i;

……

list_for_each(i, &nf_sockopts) {

struct nf_sockopt_ops *ops = (struct nf_sockopt_ops *)i;

……

}

……

函数首先定义一个(struct list_head *)指针变量i,然后调用list_for_each(i,&my_list)进行遍历。在[include/linux/list.h]中,list_for_each()宏是这么定义的:

它实际上是一个for循环,利用传入的pos作为循环变量,从表头head开始,逐项向后(next方向)移动pos,直至又回到head(prefetch()可以不考虑,用于预取以提高遍历速度)。

大多数情况下,遍历链表的时候都需要获得链表节点数据项,也就是说list_for_each()和list_entry()总是同时使用。对此Linux给出了一个list_for_each_entry()宏:

#define list_for_each_entry(pos, head, member)

与list_for_each()不同,这里的pos是数据项结构指针类型,而不是(struct list_head *)。

某些应用需要反向遍历链表,Linux提供了 list_for_each_prev()和list_for_each_entry_reverse()来完成这一操作,使用方法和上面介绍的 list_for_each()、list_for_each_entry()完全相同。

如果遍历不是从链表头开始,而是从已知的某个节点pos开始,则可以使 用list_for_each_entry_continue(pos,head,member)。有时还会出现这种需求,即经过一系列计算后,如果 pos有值,则从pos开始遍历,如果没有,则从链表头开始,为此,Linux专门提供了一个 list_prepare_entry(pos,head,member)宏,将它的返回值作为 list_for_each_entry_continue()的pos参数,就可以满足这一要求。

4. 安全性考虑

在并发执行的环境下,链表操作通常都应该考虑同步安全性问题,为了方便,Linux将这一操作留给应用自己处理。Linux链表自己考虑的安全性主要有两个方面:

a) list_empty()判断

基本的list_empty()仅以头指针的next是否指向自己来判 断链表是否为空,Linux链表另行提供了一个list_empty_careful()宏,它同时判断头指针的next和prev,仅当两者都指向自己 时才返回真。这主要是为了应付另一个cpu正在处理同一个链表而造成next、prev不一致的情况。但代码注释也承认,这一安全保障能力有限:除非其他 cpu的链表操作只有list_del_init(),否则仍然不能保证安全,也就是说,还是需要加锁保护。

b) 遍历时节点删除

前面介绍了用于链表遍历的几个宏,它们都是通过移动pos指针来达到遍 历的目的。但如果遍历的操作中包含删除pos指针所指向的节点,pos指针的移动就会被中断,因为list_del(pos)将把pos的next、 prev置成LIST_POSITION2和LIST_POSITION1的特殊值。

当然,调用者完全可以自己缓存next指针使遍历操作能够连贯起来,但 为了编程的一致性,Linux链表仍然提供了两个对应于基本遍历操作的"_safe"接口:list_for_each_safe(pos, n, head)、list_for_each_entry_safe(pos, n, head, member),它们要求调用者另外提供一个与pos同类型的指针n,在for循环中暂存pos下一个节点的地址,避免因pos节点被释放而造成的断链。

四、实例

以下实例为方便应用程序测试,直接将内核的list.h文件拷贝出来,将要测试的宏拷贝出来,删除不必要的信息。

//list.h

#ifndef __LIST_H

#define __LIST_H

#if defined(WIN32)

#define INLINE __inline

#else

#define INLINE inline

#endif

/* This file is from Linux Kernel (include/linux/list.h)

* and modified by simply removing hardware prefetching of list items.

* Here by copyright, credits attributed to where ever they belong.

* Get from //isis.poly.edu/kulesh/stuff/src/klist/

*/

/*

* Simple doubly linked list implementation.

*

* Some of the internal functions ("__xxx") are useful when

* manipulating whole lists rather than single entries, as

* sometimes we already know the next/prev entries and we can

* generate better code by using them directly rather than

* using the generic single-entry routines.

*/

struct list_head{

struct list_head*next, *prev;

};

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

#define LIST_HEAD(name) \

struct list_head name = LIST_HEAD_INIT(name)

#define INIT_LIST_HEAD(ptr) do { \

(ptr)->next = (ptr); (ptr)->prev = (ptr); \

} while (0)

/*

* Insert a new entry between two known consecutive entries.

*

* This is only for internal list manipulation where we know

* the prev/next entries already!

*/

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;

}

/**

* 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);

}

/*

* Delete a list entry by making the prev/next entries

* point to each other.

*

* This is only for internal list manipulation where we know

* the prev/next entries already!

*/

static INLINE void __list_del(struct list_head*prev,struct list_head*next)

{

next->prev= prev;

prev->next= next;

}

/**

* list_del - deletes entry from list.

* @entry: the element to delete from the list.

* Note: list_empty on entry does not return true after this, the entry is in an undefined state.

*/

static INLINE void list_del(struct list_head*entry)

{

__list_del(entry->prev, entry->next);

entry->next= (void*)0;

entry->prev= (void*)0;

}

/**

* list_del_init - deletes entry from list and reinitialize it.

* @entry: the element to delete from the list.

*/

static INLINE void list_del_init(struct list_head*entry)

{

__list_del(entry->prev, entry->next);

INIT_LIST_HEAD(entry);

}

/**

* list_move - delete from one list and add as another's head

* @list: the entry to move

* @head: the head that will precede our entry

*/

static INLINE void list_move(struct list_head*list,struct list_head*head)

{

__list_del(list->prev, list->next);

list_add(list, head);

}

/**

* list_move_tail - delete from one list and add as another's tail

* @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(list->prev, list->next);

list_add_tail(list, head);

}

/**

* list_empty - tests whether a list is empty

* @head: the list to test.

*/

static INLINE int list_empty(struct list_head*head)

{

return head->next== head;

}

static INLINE void __list_splice(struct list_head*list,

struct list_head*head)

{

struct list_head*first= list->next;

struct list_head*last= list->prev;

struct list_head*at= head->next;

first->prev= head;

head->next= first;

last->next= at;

at->prev= last;

}

/**

* list_splice - join two lists

* @list: the new list to add.

* @head: the place to add it in the first list.

*/

static INLINE void list_splice(struct list_head*list,struct list_head*head)

{

if(!list_empty(list))

__list_splice(list, head);

}

/**

* list_splice_init - join two lists and reinitialise the emptied list.

* @list: the new list to add.

* @head: the place to add it in the first list.

*

* The list at @list is reinitialised

*/

static INLINE void list_splice_init(struct list_head*list,

struct list_head*head)

{

if(!list_empty(list)) {

__list_splice(list, head);

INIT_LIST_HEAD(list);

}

}

/**

* 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) \

((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

/**

* list_for_each - iterate over a list

* @pos: the &struct list_head to use as a loop counter.

* @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 counter.

* @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 counter.

* @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_entry - iterate over list of given type

* @pos: the type * to use as a loop counter.

* @head: the head for your list.

* @member: the name of the list_struct within the struct.

*/

#define list_for_each_entry(pos, head, member) \

for (pos = list_entry((head)->next, typeof(*pos), member); \

&pos->member != (head); \

pos = list_entry(pos->member.next, typeof(*pos), member))

/**

* list_for_each_entry_safe - iterate over list of given type safe against removal of list entry

* @pos: the type * to use as a loop counter.

* @n: another type * to use as temporary storage

* @head: the head for your list.

* @member: the name of the list_struct within the struct.

*/

#define list_for_each_entry_safe(pos, n, head, member) \

for (pos = list_entry((head)->next, typeof(*pos), member), \

n = list_entry(pos->member.next, typeof(*pos), member); \

&pos->member != (head); \

pos = n, n = list_entry(n->member.next, typeof(*n), member))

#endif

#include

#include "list.h"

typedef struct test_struct

{

int test_a;

char test_b;

struct list_head list;

}TEST_LIST;

int main(int argc, char *argv[])

{

int i;

TEST_LIST *p = NULL;

struct list_head *ptr = NULL;

LIST_HEAD(t);

for (i = 0; i < 10; i++) {

p = (TEST_LIST *)malloc(sizeof(TEST_LIST));

p->test_a = i;

p->test_b = i + 1;

list_add(&(p->list), &t);

}

list_for_each(ptr, &t) {

p = list_entry(ptr, TEST_LIST, list);

printf("%d %d/n", p->test_a, p->test_b);

}

return 0;

}

该实例我们实现了链表的初始化、节点插入、链表遍历等操作。

更多链表技术文章:

嵌入式linux内核数据结构之单向链表

嵌入式linux内核数据结构之双向链表

数据结构链表的基本操作

数据结构——链表的封装

上一篇:C语言实现类继承多态封装

下一篇:Android之NDK开发介绍及环境搭建

热点文章推荐
华清学员就业榜单
高薪学员经验分享
热点新闻推荐
前台专线:010-82525158 企业培训洽谈专线:010-82525379 院校合作洽谈专线:010-82525379 Copyright © 2004-2022 北京华清远见科技集团有限公司 版权所有 ,京ICP备16055225号-5京公海网安备11010802025203号

回到顶部