作者在 2011-04-26 14:44:38 发布以下内容
Linux 2.6内核链表数据结构
1 链表设计原理
这里使用2.6内核，但实际上2.4内核中的链表结构和2.6并没有什么区别。不同之处在于2.6
扩充了两种链表数据结构：链表的读拷贝更新（rcu）和HASH链表（hlist）。这两种扩展都
是基于最基本的list结构，因此，本文主要介绍基本链表结构，然后再简要介绍一下rcu和
hlist。
链表数据结构的定义很简单（节选自[include/linux/list.h]，以下所有代码，除非加以说
明，其余均取自该文件）：
struct list_head
{
struct list_head *next, *prev;
};
{
struct list_head *next, *prev;
};
list_head结构包含两个指向list_head结构的指针prev和next，由此可见，内核的链表具备
双链表功能，实际上，通常它都组织成双循环链表。这里的list_head没有数据域。在Linux
内核链表中，不是在链表结构中包含数据，而是在数据结构中包含链表节点。
在数据结构课本中，链表的经典定义方式通常是这样的（以单链表为例）：
struct list_node
{
struct list_node *next;
ElemType data;
};
{
struct list_node *next;
ElemType data;
};
因为ElemType的缘故，对每一种数据项类型都需要定义各自的链表结构。有经验的C++程序员
应该知道，标准模板库中的<list>采用的是C++ Template，利用模板抽象出和数据项类型无
关的链表操作接口。
在Linux内核链表中，需要用链表组织起来的数据通常会包含一个struct list_head成员，真
实代码中使用的链表几乎是不变地由几个结构类型组成, 每一个描述一个链表中的入口项.
为在你的代码中使用 Linux 列表, 你只需要嵌入一个 list_head 在构成这个链表的结构里
面. 它的声明可能看起来象这样:
struct nf_sockopts
{
/* 数据 */
struct list_head list;
/* 数据 */
};
{
/* 数据 */
struct list_head list;
/* 数据 */
};
这种通用的链表结构避免了为每个数据项类型定义自己的链表的麻烦。Linux的简捷实用、
不求完美和标准的风格，在这里体现得相当充分。
列表的头常常是一个独立的 list_head 结构. 下图显示了这个简单的 struct
list_head 是如何用来维护一个数据结构的列表的.
-----------
( 链表头 )
-----------
+----+----+ ----------- ----------- -----------
+-----+ | +--+ ( nf_sockopts ) ( nf_sockopts ) ( nf_sockopts )
| +----+----+ | ----------- ----------- -----------
| list_head | +-----------+ +-----------+ +-----------+
| | | | | | | |
| | | data | | data | | data |
| | | | | | | |
| | +-----+-----+ +-----+-----+ +-----+-----+
| +----+ | +-------+ | +------+ | +----+
| +-----------+ +-----------+ +-----------+ |
| | | | | | | |
| | data | | data | | data | |
| | | | | | | |
| +-----+-----+ +-----+-----+ +-----+-----+ |
| |
| |
+--------------------------------------------------------------------------------
-----------------
( linux链表 )
-----------------
( 链表头 )
-----------
+----+----+ ----------- ----------- -----------
+-----+ | +--+ ( nf_sockopts ) ( nf_sockopts ) ( nf_sockopts )
| +----+----+ | ----------- ----------- -----------
| list_head | +-----------+ +-----------+ +-----------+
| | | | | | | |
| | | data | | data | | data |
| | | | | | | |
| | +-----+-----+ +-----+-----+ +-----+-----+
| +----+ | +-------+ | +------+ | +----+
| +-----------+ +-----------+ +-----------+ |
| | | | | | | |
| | data | | data | | data | |
| | | | | | | |
| +-----+-----+ +-----+-----+ +-----+-----+ |
| |
| |
+--------------------------------------------------------------------------------
-----------------
( linux链表 )
-----------------
2 由链表节点到数据项变量list_entry
我们知道，Linux链表中仅保存了数据项结构中list_head成员变量的地址，那么我们如何通
过这个list_head成员访问到作为它的所有者的节点数据呢？Linux为此提供了一个
list_entry(ptr,type,member)宏，其中ptr是指向该数据中list_head成员的指针，也就是存
储在链表中的地址值，type是数据项的类型，member则是数据项类型定义中list_head成员的
变量名，例如，我们要访问nf_sockopts链表地址，则如此调用：
list_entry(ptr, struct nf_sockopts, list);
这里"list"正是nf_sockopts结构中定义的用于链表操作的节点成员。
list_entry的使用相当简单，相比之下，它的实现则有一些难懂：
#define list_entry(ptr, type, member) container_of(ptr, type, member)
// container_of宏定义在[include/linux/kernel.h]中：
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
// offsetof宏定义在[include/linux/stddef.h]中：
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
// container_of宏定义在[include/linux/kernel.h]中：
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
// offsetof宏定义在[include/linux/stddef.h]中：
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
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成员相对于结构变量的偏移量。
3 声明和初始化
Linux用头指针的next是否指向自己来判断链表是否为空：
static inline int list_empty(const struct list_head *head)
{
return head->next == head;
}
{
return head->next == head;
}
Linux提供了一个INIT_LIST_HEAD宏用于运行时初始化链表：
#define INIT_LIST_HEAD(ptr) do { \
(ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)
(ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)
在阐述下面的实现前，先定义可初始化一个具体链表，后面的例子都是根据
这个具体链表展开说明的。
// 声明
struct nf_sockopts
{
/* 数据 */
struct list_head list;
/* 数据 */
};
// 实例
struct nf_sockopts sockopt;
// 初始化
INIT_LIST_HEAD((&sockopt)->list);
struct nf_sockopts
{
/* 数据 */
struct list_head list;
/* 数据 */
};
// 实例
struct nf_sockopts sockopt;
// 初始化
INIT_LIST_HEAD((&sockopt)->list);