Linux内核中的list_head结构

在 Linux 内核链表中，需要用链表组织起来的数据通常会包含一个struct list_head 成员。这种通用的链表结构避免了为每个数据项类型定义自己的链表的麻烦。

include/linux/list.h

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

在该头文件海定义了list_head的若干常用操作：

• 初始化：宏INIT_LIST_HEAD；
• 链表的插入删除合并操作：函数list_add()，list_add_tail()，list_del()，list_move()，list_move_tail()，list_empty()，list_splice()；
• 遍历链表用的迭代器：宏list_for_each等等；

这些操作的具体实现我就不多说了，这是任何一本数据结构的书中最基础的内容。值得注意的是list_head的使用方式。在Linux内核里有相当多的队列，其操作都是通过list_head进行的，但是list_head只是个连接件，如果通过该连接件找到其宿主结构呢？以struct page为例：

include/linux/mm.h

typedef struct page {
    struct list_head list;        /* ->mapping has some page lists. */
    ….
    struct list_head lru;        /* Pageout list, eg. active_list;
                                           protected by pagemap_lru_lock !! */
     ….
} mem_map_t;

此时，struct page是list_head结构体的变量list和lru的宿主结构。我们直接看看代码是如何解决寻找宿主结构这个问题的，在mm/page_alloc.c定义的函数rmqueue()中有如下的代码：

page = list_entry(curr, struct page, list);

而list_entry定义在文件include/linux/list.h中：

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

用C语言宏替换的规则，可知上面page = list_entry(…)将会被替换为：

page = ((struct page*)((char*)(curr) - (unsigned long)(&((struct page*)0)->list)));

这里的curr是一个page结构内部的成分list的地址，而我们需要的是那个page结构本身的地址，所以要从地址curr减去一个位移量，即成分list在page内部的位移量，才能达到要求。这里使用了一个很巧妙的方法：&((struct page*)0)->list就表示当结构page正好在地址0上时其成分list的地址，这刚好等于位移。

更详细的解读请参考《Linux内核情景分析》。