linux内核中链表的实现

linux内核中链表的实现

linux内核中链表的实现是相当的出色的，《linux内核设计与实现》（附录A）中说“linux内核使用了一种独一无二的方法遍历链表”、“为了这种巧妙设计，内核骇客们还是颇有点自豪的”。

-----------------------------------------------------------------------------------------------------------------------------------

1、链表结构体

struct list_head {
struct list_head *next, *prev;
};
很显然，这是一个双向链表。不过，令人疑惑的是这个链表结构中竟然没有存储节点数据的字段，这是因为
它不是单独使用的，而是需要加入到表示具体数据结构的结构体中，与表示具体数据结构的结构体组合一起
使用，才能显示出它的用途和价值。
《……设计与实现》上说“一个list_head结构体本身没有什么意义，通常需要把它嵌入到自己的结构
体中”。

例如 struct my_struct{
struct list_head list;
unsigned long dog;
void *cat;
}
这样表示具体数据结构的my_struct结构体就和list_head联系起来了。就可以把my_struct的对象通过
list成员链接起来，形成一个链表。
struct my_struct *p1,*p2,*p3......

p1->list->next=p2->list;
p2->list->pre=p1->list;
p2->list->next=p3->list;
p3->list->pre=p2->list;
p3->list->next=p1->list;
p1->list->pre=p3->list;

这样就通过list_head成员把my_struct的对象链接起来。
可以通过list_entry(p1->list,struct my_struct,list)来返回指向p1的my_struct指针，也就是
通过list_entry可以实现由list域访问其所属的结构体对象的功能。

2、链表操作函数
内核中很巧妙实现了链表的操作，大都非常简洁、精炼，通过宏或者内联函数实现，其中
list_entry的实现很有意思。

··初始化链表：
static inline void INIT_LIST_HEAD(struct list_head *list)
{
list->next = list;
list->prev = list;
}
可以看出初始化时链表前项节点和后向节点都指向了其本身。

··添加操作（此处仅列出一个）：

static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}


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;
}

new是新添加项，添加到结点head所在的链表中，并且是加到head之后第一个结点。

··删除操作（仅列出一个）：

static inline void list_del(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
}

static inline void __list_del(struct list_head * prev, struct list_head * next)
{
next->prev = prev;
prev->next = next;
}

从链表中删除entry，并使其指向安全的位置LIST_POISON1和LIST_POISON2，关于这两个常量的解释和定义在
linux/poison.h（22行）
/*
* These are non-NULL pointers that will result in page faults
* under normal circumstances, used to verify that nobody uses
* non-initialized list entries.
*/
#define LIST_POISON1 ((void *) 0x00100100 + POISON_POINTER_DELTA)
#define LIST_POISON2 ((void *) 0x00200200 + POISON_POINTER_DELTA)

··遍历链表：

遍历链表list_for_each是一个宏，展开了就是一个for循环

#define list_for_each(pos, head) \
for (pos = (head)->next; prefetch(pos->next), pos != (head); \
pos = pos->next)
其中prefech(pos->next)是处理器预取pos->next，通过处理器的预取功能，对for循环进行了优化。

··访问数据操作：

#define list_entry(ptr, type, member) \
container_of(ptr, type, member)

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

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

container_of是一个有点复杂的宏,使用了C扩展关键字typeof，还有不好理解的求结构体成员
变量偏移.....
·((type *)0)是将0强制转化为type *，也就是指向type类型的指针

·((type *)0)->member是访问type结构中的member成员

·const typeof( ((type *)0)->member ) *__mptr 定义一个与((type *)0)->member同种类型的
指针变量（const变量）

·const typeof( ((type *)0)->member ) *__mptr=(ptr)对常量指针变量__mptr赋值
__mptr=ptr

·((size_t) &((TYPE *)0)->MEMBER得到member在type结构体中的偏移量，
offsetof(type,member)的展开效果

·(char *)__mptr - offsetof(type,member) 将__mptr强制转化为char类型指针，也就是__mptr
的地址，然后减去member在结构体中的偏移量，的到的自然就是结构体起始地址（偏移量求的很巧妙，
又很巧妙的获得结构体起始地址）。

·(type *)( (char *)__mptr - offsetof(type,member) )最后再强制转化为(type *)类型，
得到ptr所在的结构体对象（大功告成）。
到此成功的通过结构体对象的一个域的字段，获取了结构体对象本身，即访问list_head关联的结构对象
成功。
----------------------------------------------------------------------------------
取得结构体一个字段的偏移地址的方法 offsetof(type,member) 宏，设置的十分巧妙，
取得偏移后，具体对象的member地址-偏移地址，得到type对象的起始地址，设计相当的妙。

评论

2 楼 grzrt 2012-07-25  

jinnianshilongnian 写道

整这个了？

没有 看看 了解一下

1 楼 jinnianshilongnian 2012-07-24  

整这个了？