Linux 内核结构体之 list & hlist
Linux 内核中提供了链表的实现，这其中包括了双向链表和用于哈希表的 hash list（hlist）。双向链表的实现采用侵入式的方式，链表节点不保存任何数据内容，而是将链表结构作为具体数据结构的成员；hlist 虽然有 pprev 和 next 成员，但它并不是双向链表，因为 pprev 指向的是前一个节点的 next 指针。
Linked List
此种链表只需一种结构体，即：
struct list_head {
struct list_head *next, *prev;
};
常用的函数和宏列举如下：
#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;
}
// 在链表头后增加一个元素，即将新增元素插入到链表第一个位置，可用于实现栈结构
static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
// 在链表头前插入一个元素，即将新元素插入到链表最末，可用于实现队列结构
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
}
// 获取包含链表节点 ptr 的 type 结构体指针，member 为 list_head 在 type 结构重的定义
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
// 获取链表的第一个结构体，ptr 为链表头
#define list_first_entry(ptr, type, member) \
list_entry((ptr)->next, type, member)
// 获取链表的最后一个结构体，ptr 为链表头
#define list_last_entry(ptr, type, member) \
list_entry((ptr)->prev, type, member)
// 遍历链表
#define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
关于双向链表如果非要说一点需要注意的地方的话，那就是双向链表的头不存储真实数据，它通常作为链表遍历的入口存在于系统的全局变量。一个完整的使用例子见：Linux Kernel Programming–Linked List。
Hash List
Hash List 是为 Hash Table 设计的一种链表，其实上述的双向链表也能实现哈希表，但由于双向链表的头跟其它节点一样，都有两个指针，因此当 bucket 很大的时候，会浪费内存。hlist 实现为以下两种结构体：
struct hlist_head {
struct hlist_node *first;
};
struct hlist_node {
struct hlist_node *next, **pprev;
};
可以看出，相对于 list_head 的两个指针，hlist_head 仅需保存一个指针。hlist_node 的 next 指向下一个节点，但 pprev（指针的指针） 并不指向上一个节点，而是指向上一个节点的 next 指针，这样设计的好处是当要删除的节点是第一个节点，也可以通过 *pprev = next 直接修改指针的指向（参见2）。
hlist 常见的函数及宏列举如下：
#define HLIST_HEAD_INIT { .first = NULL }
// 初始化链表头
#define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
static inline void INIT_HLIST_NODE(struct hlist_node *h)
{
h->next = NULL;
h->pprev = NULL;
}
// 在节点头之后添加节点 n，即操作后 n 为链表的第一个节点
static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
struct hlist_node *first = h->first;
n->next = first;
if (first)
first->pprev = &n->next;
WRITE_ONCE(h->first, n);
n->pprev = &h->first;
}
// 在节点 next 之前添加节点 n
/* next must be != NULL */
static inline void hlist_add_before(struct hlist_node *n,
struct hlist_node *next)
{
n->pprev = next->pprev;
n->next = next;
next->pprev = &n->next;
WRITE_ONCE(*(n->pprev), n);
}
// 在节点 prev 之后增加节点 n
static inline void hlist_add_behind(struct hlist_node *n,
struct hlist_node *prev)
{
n->next = prev->next;
WRITE_ONCE(prev->next, n);
n->pprev = &prev->next;
if (n->next)
n->next->pprev = &n->next;
}
// 同 list_entry
#define hlist_entry(ptr, type, member) container_of(ptr,type,member)
// 遍历 Hash List
#define hlist_for_each(pos, head) \
for (pos = (head)->first; pos ; pos = pos->next)
由于 hlist 的这种设计，导致它不能在 O(1) 时间获取到尾节点，也不能进行反向遍历。这可能就是计算机中常见的 Trade Off 吧。
Hash List with bit lock
hlist_bl 是 hlist 一个特殊版本。一般在使用 hlist 用作 hashtable 的时候，会给每个 hlist 定义一个 spinlock，而为了减少这种内存开销，hlist_bl 利用 hlist_bl_head->first 的地址最后一位来代替 spinlock，这种方式可行的原因是因为指针通常为4字节8字节对齐，最后一位一定为0。
其关键函数如下：
static inline struct hlist_bl_node *hlist_bl_first(struct hlist_bl_head *h)
{
return (struct hlist_bl_node *)
((unsigned long)h->first & ~LIST_BL_LOCKMASK);
}
static inline void hlist_bl_set_first(struct hlist_bl_head *h,
struct hlist_bl_node *n)
{
LIST_BL_BUG_ON((unsigned long)n & LIST_BL_LOCKMASK);
LIST_BL_BUG_ON(((unsigned long)h->first & LIST_BL_LOCKMASK) !=
LIST_BL_LOCKMASK);
h->first = (struct hlist_bl_node *)((unsigned long)n | LIST_BL_LOCKMASK);
}
static inline bool hlist_bl_empty(const struct hlist_bl_head *h)
{
return !((unsigned long)READ_ONCE(h->first) & ~LIST_BL_LOCKMASK);
}
static inline void hlist_bl_lock(struct hlist_bl_head *b)
{
bit_spin_lock(0, (unsigned long *)b);
}
static inline void hlist_bl_unlock(struct hlist_bl_head *b)
{
__bit_spin_unlock(0, (unsigned long *)b);
}
static inline bool hlist_bl_is_locked(struct hlist_bl_head *b)
{
return bit_spin_is_locked(0, (unsigned long *)b);
}