linux学习17,内核中链表的设计与实现

上一节较为详细的讨论了 linux 中的系统调用,接下来几节将学习 linux 内核中的基本数据结构的设计和实现。本节先来看看 linux 内核中的链表。

链表和数组有些相似

链表是基于 C语言指针的,看了我《C语言入门》系列文章的朋友应该记得这张图:

指针 p2 指向一块内存,可以通过 p2 修改该内存里保存的数值。链表其实也是类似的,只不过链表是一个挨一个“串起来”的:

这种形式的数据结构和静态数组有些相似,不过链表包含的元素都是动态创建插入的,编译的时候并不需要知道要创建多少元素,而且链表的每个元素创建时间可能差异比较大,所以各个链表元素在内存中往往也不是连续的。

也正是因为链表的各个元素在内存中不像数组元素那样连续,所以链表才需要额外的“连接方式”将这些元素连接起来,指针正是一种非常合适的“连接方式”。

定义链表

如果使用基本数据类型定义链表,例如:

int* a;
int* b;
int* c;
a = b;
b = c;


这样的确定义了一个链表,但是却没有任何意义,因为它真的只是一个链表,无法存储任何额外的信息。所以,链表一般都是用复合数据类型定义,常用的是结构体数据类型,这样一来,一个基本的链表可以如下定义:

struct node{
    void* data;
    struct node* next;
};

这样就很好用了,next 成员负责连接下一个(数据结构一模一样的)节点,data 成员则负责存储数据,如果 data 成员不方便存储所有数据,还可以随时增加数据成员。这样的数据结构简图如下:

在某些链表中,每个节点还可以指向前一个节点:

struct node{
    void* data;
    struct node* prev;
    struct node* next;
};

它的数据结构简图如下:

因为这种链表可以同时向前和向后连接,所有常被称作“双向链表”。

上面介绍的两种链表,两端的节点常常是指向 NULL 的,表示链表的起点和终点。但是有的链表两端节点并不指向 NULL,而是分别指向首尾,这样就形成了“环形链表”,请看下图:

linux 内核常使用的标准链表就是环形双向链表,这主要是因为环形双向链表有最大的灵活性。

访问链表元素

访问数组元素时既可以线性访问,也可以随机访问。这是因为数组的各个元素在内存中是紧密排列的,只需知道其中一个元素的地址,其他元素的地址都可以简单的推算出来。

而链表的各个元素在内存中并不连续,所以只能通过 next 或者 prev 指针线性访问。例如先访问节点 1,然后利用节点 1 的next 指针访问节点 2,再利用节点 2 的next 指针访问节点 3。

当然了,访问链表也可以从任意指定的节点开始。如果链表是环形链表,则从任意一个节点都能够遍历所有链表元素。如果是双向链表,则从某个节点出发,既可以向前访问,也可以向后访问。

这是一种最简单的沿着链表访问元素的方法,也是最适合访问链表的方法。如果需要随机访问数据,则就不应该使用链表的数据类型了。链表最适合使用在需要遍历所有元素,以及需要动态插入删除数据的场景。

linux 内核中的链表的设计和实现

一般情况下,定义链表时都是通过在数据内部添加 prev 和 next 指针实现的,请看:

struct fox{
    int tail_len;
    int weight;
    struct fox* prev;
    struct fox* next;
};

上面的 C语言代码使用 prev 和 next 指针定义了一个双向链表,然后又插入了尾巴长度和体重两个成员,用于描述 fox(狐狸) ,这就相当于“把数据结构”塞入链表。

linux 内核使用链表的方式与众不同,它不是将数据结构塞入链表,而是把链表塞入数据结构。linux 内核的链表相关C语言代码在 <linux/list.h> 中声明:

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

可以看出,这是相当简单的双向链表,next 指针指向下一个节点,prev 指向前一个。list_head 并没有存储其他数据的地方,那怎样使用呢?按照上面的说法,linux 内核“将链表塞入数据结构”,请看C语言代码:

struct fox{
    int tail_len;
    int weight;
    struct list_head list;
};

这样链表就能存储其他数据了,访问下一个节点可以使用 fox 中的 list.next,访问前一个节点可以使用 list.prev。为了操作更方便,linux 内核还定义了一些链表操作函数,例如 list_add() 可以方便的将新节点加入链表,INIT_LIST_HEAD() 初始化链表等待:

不过 linux 内核提供的这些方法接收的参数都是 struct list_head 型的,而链表中的 next、prev 只是我们想使用的结构体中的成员而已,要是只知道 next、prev 的地址,怎样访问结构体的其他成员呢?这就要借助于 container_of() 宏了,它的 C 语言代码如下,请看:

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


通过 container_of 宏,linux 内核可以很方便的访问结构体的其他成员。这是因为在 C语言中,给定结构体中的变量偏移在编译时地址就被 ABI 固定下来了。

下面分析一下 container_of 宏,以 struct fox 为例:

struct fox{
    int tail_len;
    int weight;
    struct list_head list;
};
struct fox f;

已知 list 的地址,如何求 f 的地址呢?其实很简单,将 list 的地址减去 list 在 struct fox 中的偏移就可以了。

container_of 宏就是这样的思路:

const typeof( ((type *)0)->member ) *__mptr = (ptr);

这一句定义了一个和 member 同类型的指针

__mptr
,并将 ptr 的地址传递给它。

 (type *)( (char *)__mptr - offsetof(type,member) );})

这一句的目的就是将

__mptr
减去 member 在 type 中的偏移,执行完毕之后就得到了 f 的地址,这时再访问其他成员就不难了。

offsetof 的宏定义如下,也是非常简单的:

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

到这里,我们就清楚了linux 内核常用的标准链表的定义和基本使用方法。事实上,linux 内核还定义了一些其他比较方便操作链表的宏和方法,限于篇幅,下一节再说了。

阅读更多:   Linux笔记
添加新评论

icon_redface.gificon_idea.gificon_cool.gif2016kuk.gificon_mrgreen.gif2016shuai.gif2016tp.gif2016db.gif2016ch.gificon_razz.gif2016zj.gificon_sad.gificon_cry.gif2016zhh.gificon_question.gif2016jk.gif2016bs.gificon_lol.gif2016qiao.gificon_surprised.gif2016fendou.gif2016ll.gif