上一节较为详细的讨论了 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 内核还定义了一些其他比较方便操作链表的宏和方法,限于篇幅,下一节再说了。