内核链表是一个doubly linked list，是一个双向循环链表。Linux使用链表时，将链表放入数据结构中。头文件：<linux/list.h>
链表头定义在<linux/types.h>
1 2 3 | struct list_head { struct list_head *next, *prev;}; |
所有的链表操作，均是操作list_head结构体，而不操作包含它的数据结构。
链表的每一个项都是上述数据结构，但是Linux的设计是有一个专门的头，其不包含数据，仅用于维护链表，其它的链表项则包含数据。
如上述，如果知道A狐狸的list成员，是可以遍历整个链表，但是不知道哪个是头，哪个是包含数据的链表项。因此我们始终需要知道head。
1 获取链表头的父结构体
使用list_entry()宏：
1 2 3 4 5 6 | #define list_entry(ptr, type, member) \ container_of(ptr, type, member)// examplestruct list_head *list = &A.list;list_entry(list, struct fox, list); |
list_first_entry(ptr, type, member)
获取第一个节点，ptr通常是链表头。
2 定义和初始化头
链表头初始化时，next和prev均指向它自己。
有3种方式，其实现代码如下：
1 2 3 4 5 6 7 8 9 10 | #define LIST_HEAD_INIT(name) { &(name), &(name) }#define LIST_HEAD(name) \ struct list_head name = LIST_HEAD_INIT(name) static inline void INIT_LIST_HEAD(struct list_head *list){ WRITE_ONCE(list->next, list); list->prev = list;} |
如果头是静态或全局变量则：
1 | static LIST_HEAD(fox_head); |
如果头是结构体的成员，并动态初始化：
1 | INIT_LIST_HEAD(inode->inotify_watches); |
如果头是结构体成员，并编译期间静态初始化：
1 2 3 4 | struct inode inode = { .inotify_watches = LIST_HEAD_INIT(inode.inotify_watches),}; |
3 链表操作函数
所有这些函数，均为内联函数，实现在linux/list.h头文件中。
内核链表还有一个重要的特点是，它的prev和next绝不为Null，这极大的优化了链表维护的代码。
所有的链表操作函数内部都没有锁保护，需要根据上下文，自己添加锁保护。
3.1 list_add()
将一个节点添加到head之后，该节点为第一个节点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | 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;}static inline void list_add(struct list_head *new, struct list_head *head){ __list_add(new, head, head->next);} |
3.2 list_add_tail()
将一个节点添加到head之前，该节点成为最后一个节点。
1 2 3 4 | static inline void list_add_tail(struct list_head *new, struct list_head *head){ __list_add(new, head->prev, head);} |
3.3 list_del()
删除一个节点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | static inline void __list_del(struct list_head * prev, struct list_head * next){ next->prev = prev; WRITE_ONCE(prev->next, next);}static inline void __list_del_entry(struct list_head *entry){ if (!__list_del_entry_valid(entry)) return; __list_del(entry->prev, entry->next);}static inline void list_del(struct list_head *entry){ __list_del_entry(entry); entry->next = LIST_POISON1; entry->prev = LIST_POISON2;} |
删除节点后，next和prev被赋予一个特殊的值，而不是NULL，这是出于调试目的。
3.4 list_del_init()
删除之后，再进行头初始化。
3.5 list_replace()
替换节点
1 2 3 4 5 6 7 8 | static inline void list_replace(struct list_head *old, struct list_head *new){ new->next = old->next; new->next->prev = new; new->prev = old->prev; new->prev->next = new;} |
3.6 list_replace_init()
替换后，在进行头初始化。
3.7 其它操作
将list从现链表删除，然后插入到head链表
void list_move(struct list_head *list, struct list_head *head)
将list从现链表删除，然后插入到head链表尾
void list_move_tail(struct list_head *list,
struct list_head *head)
链表是否是最后一个节点（判断next是否为头）
int list_is_last(const struct list_head *list,
const struct list_head *head)
链表是否为空（判断next是否为头自己）
int list_empty(const struct list_head *head)
判断链表是否只有一个节点
int list_is_singular(const struct list_head *head)
将下一个节点移动为上一个节点
void list_rotate_left(struct list_head *head)
将head之后的节点直到entry，移动到空链表list
void list_cut_position(struct list_head *list,
struct list_head *head, struct list_head *entry)
将list链表合并到head之后：
void list_splice(const struct list_head *list,
struct list_head *head)
list_splice_tail()
list_splice_init()
list_splice_tail_init()
带tail的合并到head之前，带init的合并后，对list进行头初始化。
3.8 遍历链表
遍历链表需要提供一个变量存储当前cursor。对于safe类接口，还需要一个变量存储下一个节点。
1 2 3 4 5 6 7 8 9 10 11 | #define list_for_each(pos, head) \ for (pos = (head)->next; pos != (head); pos = pos->next)#define list_for_each_prev(pos, head) \ for (pos = (head)->prev; pos != (head); pos = pos->prev)#define list_for_each_safe(pos, n, head) \ for (pos = (head)->next, n = pos->next; pos != (head); \ pos = n, n = pos->next)#define list_for_each_prev_safe(pos, n, head) \ for (pos = (head)->prev, n = pos->prev; \ pos != (head); \ pos = n, n = pos->prev) |
prev类是反向遍历。如果需要删除遍历出的当前节点，需要使用safe类接口，它将当前节点的下一个遍历节点存储起来，这样删除了当前节点，也可以继续遍历。
上述4个接口，获取的是list_head的指针，通常获取其父结构的指针更为便利，有对应的接口：
1 2 3 4 | list_for_each_entry(pos, head, member) list_for_each_entry_reverse(pos, head, member) list_for_each_entry_safe(pos, n, head, member) list_for_each_entry_safe_reverse(pos, n, head, member) |
从一个特定节点之后开始搜索：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | #define list_prepare_entry(pos, head, member) \ ((pos) ? : list_entry(head, typeof(*pos), member))#define list_for_each_entry_continue(pos, head, member) \ for (pos = list_entry(pos->member.next, typeof(*pos), member); \ &pos->member != (head); \ pos = list_entry(pos->member.next, typeof(*pos), member))#define list_for_each_entry_continue_reverse(pos, head, member) \ for (pos = list_entry(pos->member.prev, typeof(*pos), member); \ &pos->member != (head); \ pos = list_entry(pos->member.prev, typeof(*pos), member))#define list_for_each_entry_from(pos, head, member) \ for (; &pos->member != (head); \ pos = list_entry(pos->member.next, typeof(*pos), member))#define list_for_each_entry_safe_continue(pos, n, head, member) \ for (pos = list_entry(pos->member.next, typeof(*pos), member), \ n = list_entry(pos->member.next, typeof(*pos), member); \ &pos->member != (head); \ pos = n, n = list_entry(n->member.next, typeof(*n), member))#define list_for_each_entry_safe_from(pos, n, head, member) \ for (n = list_entry(pos->member.next, typeof(*pos), member); \ &pos->member != (head); \ pos = n, n = list_entry(n->member.next, typeof(*n), member)) |
list_prepare_entry()，如果pos为空，则head的父结构，否则为pos。注意：如果head不是放在父结构中的，这里也没关系，假设有一个父结构，可以安全的使用list_for_each_entry_continue()，它从下一个节点开始遍历，使用一个假的父结构指针也是可以获取下一个节点的，但是不能使用list_for_each_entry_from()。
list_for_each_entry_continue()，从pos的下一个节点开始遍历
list_for_each_entry_continue_reverse，从pos的上一个节点开始反向遍历
list_for_each_entry_from()，从pos本身开始遍历
list_for_each_entry_safe_continue()，safe版本
list_for_each_entry_safe_from()，safe版本
重置next为pos的next
1 2 | #define list_safe_reset_next(pos, n, member) \ n = list_entry(pos->member.next, typeof(*pos), member) |
参考：
Robert Love. Linux Kernel Development. Third Edition