深入分析 Linux 内核链表(总结)

在Linux内核中使用了大量的链表结构来组织数据，包括设备列表以及各种功能模块中的数据组织。这些链表大多采用在
linux/include/linux/list.h 定义。
链表结构：
struct list_head {
    struct list_head *next, *prev;
};
list_head结构包含两个指向list_head结构的指针prev和next，内核的链表具备双链表功能，实际上，通常它都组织成双循环链表。

但是list_head没有数据域。在Linux内核链表中，不是在链表结构中包含数据，而是在数据结构中包含链表节点。
如： 138struct kset {
    139        struct kobj_type        * ktype;
    140        struct list_head        list;
    141        spinlock_t              list_lock;
    142        struct kobject          kobj;
    143        struct kset_uevent_ops  * uevent_ops;
    144};
    只是用struct list_head嵌入到其他的数据结构建立双向链表。
    
list_del()删除节点，删除下来的prev、 next指针分别被设为LIST_POSITION2和LIST_POSITION1两个特殊值，这样设置是为了保证不在链表中的节点项不可访问。对 LIST_POSITION1和LIST_POSITION2的访问都将引起页故障。与之相同，list_del_init()函数将节点从链表中解下来之后，调用LIST_INIT_HEAD()将节点置为空链状态.但list_del_rcu()删除节点，只是prev 置为LIST_POISON2，但是并没有next指针设置为LIST_POISON1，因为该指针可能仍然在被读者用于遍历该链表。


 439/**
 440 * list_for_each        -       iterate over a list
 441 * @pos:        the &struct list_head to use as a loop cursor.
 442 * @head:       the head for your list.
 443 */
 444#define list_for_each(pos, head) \
 445        for (pos = (head)->next; prefetch(pos->next), pos != (head); \
 446                pos = pos->next)
它实际上是一个for循环，利用传入的pos作为循环变量，从表头head开始，逐项向后（next方向）移动pos，直至又回到head（prefetch()可以不考虑，用于预取以提高遍历速度）


 480/**
 481 * list_for_each_entry  -       iterate over list of given type
 482 * @pos:        the type * to use as a loop cursor.
 483 * @head:       the head for your list.
 484 * @member:     the name of the list_struct within the struct.
 485 */
 486#define list_for_each_entry(pos, head, member)                          \
 487        for (pos = list_entry((head)->next, typeof(*pos), member);      \
 488             prefetch(pos->member.next), &pos->member != (head);        \
 489             pos = list_entry(pos->member.next, typeof(*pos), member))

其中pos为该数据结构list_head结构特定的指针，member为head数据结构的list_head成员。
list_for_each_entry()与list_for_each不同之处在于塔遍历指定类型数据结构的链表。

 
 其中：list_entry((head)->next, typeof(*pos), member);
 419/**
 420 * list_entry - get the struct for this entry
 421 * @ptr:        the &struct list_head pointer.
 422 * @type:       the type of the struct this is embedded in.
 423 * @member:     the name of the list_struct within the struct.
 424 */
 425#define list_entry(ptr, type, member) \
 426        container_of(ptr, type, member)
 
 该函数取得type结构的地址，通过container_of()宏实现的。

  311/**
 312 * container_of - cast a member of a structure out to the containing structure
 313 * @ptr:        the pointer to the member.
 314 * @type:       the type of the container struct this is embedded in.
 315 * @member:     the name of the member within the struct.
 316 *
 317 */
 318#define container_of(ptr, type, member) ({                      \
 319        const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
 320        (type *)( (char *)__mptr - offsetof(type,member) );})


内核的双向链表是一种内核常用的组织有序数据的数据结构，它通过指针将一系列数据节点连接成一条数据链。相对于数组，链表具有更好的动态性，建立链表时无需预先知道数据总量，可以随机分配空间，可以高效地在链表中的任意位置实时插入或删除数据。链表的开销主要是访问的顺序性和组织链的空间损失。