1 概述

在Linux内核中，对于数据的管理，提供了2种类型的双向链表：一种是使用list_head结构体构成的环形双向链表；另一种是使用hlist_head和hlist_node2个结构体构成的具有表头的链型双向链表。

list_head的结构体如下所示：

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

hlist_head和hlist_node的结构体如下所示：

struct hlist_head {
    struct hlist_node *first;
};
struct hlist_node {
    struct hlist_node *next, **pprev;
};

它们组成的链表结构如图所示：

注意图上的箭头指向，在（a）图中，next指向下一个list_head结构的地址，prev指向前一个list_head结构的地址。而在（b）图中，next类似，指向下一个hlist_node结构的地址，而pprev指向前一个hlist_node的next指针。这是为什么呢？我们将在第3章中讨论。

内核为什么设计这么2个双向链表呢？使用它们有什么好处？它们的使用场景分别是什么呢？让我们一一阐述：

设计目的

内核中大量使用数据表，为了更好的管理这些表，必须满足：
- 所有操作都是原子的，不能受到并发的影响。
- 必须是通用模型，这样可以节省空间，使用灵活，而且也避免浪费编程人员的精力。
- 访问时间尽可能短，提高内核查找匹配速度。
适用场景

list_head结构组成的列表适用于对遍历时间要求比较严格的地方，比如进程的管理。我们在看task_struct结构体中就有多个list_head类型的变量，用来管理task。

hlist_head和hlist_node主要用于散列表中，因为内核中存在大量的hash表，使用这种方式实现的散列表因为少一个指针，可以节省一半的空间。

2 list_head链表

图（a）是由list_head组成的双向链表。它和普通的双向链表非常相似，只是仅包含2个成员next和prev指针，分别指向下一个和前一个list_head结构体。

假设我们的内核中需要定义一个kernel_list的结构体，它除了2个list_head结构体类型成员list1和list2之外，还有1个void *类型成员item，那么它的结构体可以是：

struct kernel_list {
    struct list_head list1;
    struct list_head list2;
    void *item;
};

所以，list_head结构体组成的双向链表，具有一下特性：

list在你需要链接数据结构的里面；
可以把struct list_head放在该数据结构的任何地方；
可以吧struct list_head变量命名为任何名字。
可以有多个list在一个数据结构中。

2.1 初始化

链表初始化分为静态初始化和动态初始化：

动态

 #define LIST_HEAD_INIT(name) { &(name), &(name) }
 /* 或 */
 static inline void INIT_LIST_HEAD(struct list_head *list)
 {
         list->next = list;
         list->prev = list;
 }
 /* 例如 */
 struct list_head my_list = LIST_HEAD_INIT(my_list);
 struct list_head your_list;
 INIT_LIST_HEAD(&your_list);

静态 - 用于声明时

 #define LIST_HEAD(name) \
         struct list_head name = LIST_HEAD_INIT(name)

 /* 例如 */
 LIST_HEAD(rds_sock_list);  
 /* ==> */
 struct rds_sock_list = { &(rds_sock_list), &(rds_sock_list) };

2.2 插入

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之后 */
static inline void list_add(struct list_head *new, struct list_head *head)
{
    __list_add(new, head, head->next);
}
/* new 插入到head之前 */
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
    __list_add(new, head->prev, head);
}

2.3 删除

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

2.4 替换

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

static inline void list_replace_init(struct list_head *old, 
                                    struct list_head *new)
{
    list_replace(old, new);
    INIT_LIST_HEAD(old);
}

2.5 拼接

static inline void __list_splice(const struct list_head *list,
                                struct list_head *prev,
                                struct list_head *next)
{
    struct list_head *first = list->next;
    struct list_head *last = list->prev;
    first->prev = prev;
    prev->next = first;
    last->next = next;
    next->prev = last;
}
/* list 加到 head 前面 */
static inline void list_splice(const struct list_head *list,
                                struct list_head *head)
{
    if (!list_empty(list))
        __list_splice(list, head, head->next);
}
/* list 加到 head 后面 */
static inline void list_splice_tail(struct list_head *list,
                                    struct list_head *head)
{
    if (!list_empty(list))
        __list_splice(list, head->prev, head);
}

2.6 列表其它操作

static inline int list_is_last(const struct list_head *list,
                                const struct list_head *head)
{
    return list->next == head;
}
static inline int list_empty(const struct list_head *head)
{
    return head->next == head;
}
/* list_empty_careful - tests whether a list is empty and not being modified */
static inline int list_empty_careful(const struct list_head *head)
{
    struct list_head *next = head->next;
    return (next == head) && (next == head->prev);
}
static inline int list_is_singular(const struct list_head *head)
{
    return !list_empty(head) && (head->next == head->prev);
}

2.7 链表入口点获取

一般通过struct list_head维护链表，那么有一个指向struct list_head*的指针ptr ,如何获取它所在结构体的指针，然后访问它的成员呢？

/*
 * @ptr:        &struct list_head 指针。
 * @type:       ptr所在结构体的类型。
 * @member:     list_head在type结构体中的名字。
 */
#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)

/* list_first_entry中的ptr是指表头的指针。不是第一个节点的指针，如上图所示 */ 
#define list_first_entry(ptr, type, member) \
        list_entry((ptr)->next, type, member)

这段代码的核心就是container_of宏，它通过巧妙使用0指针，它的成员地址就是就是该成员在实际结构中的偏移，所以通过这种巧妙的转变取得了type类型的结构体的指针。有了这个指针，我们就可以访问其任何成员了。

2.8 遍历链表

list_for_each遍历一个链表。

 // @pos：struct list_head类型的指针，用于指向我们遍历的链表节点；
 // @head：我们要遍历链表的头节点；
 #define list_for_each(pos, head) \      
         for (pos = (head)->next; pos != (head); pos = pos->next)

__list_for_each与list_for_each完全一样，遍历一个链表，同时也不做预取。

 #define __list_for_each(pos, head) \
         for (pos = (head)->next; pos != (head); pos = pos->next)

__list_for_each_prev用于从后向前反向遍历。

 #define list_for_each_prev(pos, head) \
         for (pos = (head)->prev; pos != (head); pos = pos->prev)

list_for_each_safe安全的遍历一个链表，其机制是我们多传入一个struct list_head的指针n，用于指向pos的下一个节点，以保证我们在删除pos指向的节点时，仍能继续遍历链表的剩余节点。
```
 #define list_for_each_safe(pos, n, head) \
         for (pos = (head)->next, n = pos->next; pos != (head); \
                 pos = n, n = pos->next)
```

list_for_each_prev_safe反向遍历，安全查找。

 #define list_for_each_prev_safe(pos, n, head) \
         for (pos = (head)->prev, n = pos->prev; \
              pos != (head); \
              pos = n, n = pos->prev)

前面5项在遍历链表时返回的是struct list_head指针的地址。当我们使用struct list_head型变量将一个节点挂到一个链表时，我们不是为了仅仅操纵这个光凸凸的节点，而是将struct list_head变量放到一个结构体内，根据对链表上struct list_head的遍历来得出strcut list_head所在结构体的首地址，list_for_each_entry正是为了完成这一功能而实现。
```
 #define list_for_each_entry(pos, head, member)                          \
         for (pos = list_entry((head)->next, typeof(*pos), member);      \
              &pos->member != (head);    \
              pos = list_entry(pos->member.next, typeof(*pos), member))
```

我们将所求结构体类型的指针变量pos、链表的头head和所求结构体内struct list_head的变量名member传到list_for_each_entry之后， list_entry的第一个参数用head->next指向下一个节点，此节点的地址也就是在所属结构体内的struct list_head成员变量的地址，第二个参数用typeof(*pos)求得pos的结构体类型，第三个参数为所求结构体内struct list_head的变量名。

2.9 list_head示例代码

从当前module节点,遍历系统所有module.

#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/init.h>
#include <linux/version.h>
#include <linux/list.h>

MODULE_LICENSE("GPL");
struct module *m = &__this_module;
static void list_module_test(void)
{
    struct module *mod;
    list_for_each_entry(mod, m->list.prev, list)
        printk ("%s\n", mod->name);
}
static int list_module_init (void)
{
    list_module_test();
    return 0;
}

static void list_module_exit (void)
{
    printk ("unload listmodule.ko\n");
}

module_init(list_module_init);
module_exit(list_module_exit);

Makefile文件如下，可直接在linux主机上编译：

ifeq ($(KERNELRELEASE),)
    KERNELDIR ?= /lib/modules/$(shell uname -r)/build
    PWD := $(shell pwd)
modules:
        $(MAKE) -C $(KERNELDIR) M=$(PWD) modules

modules_install:
        $(MAKE) -C $(KERNELDIR) M=$(PWD) modules_install

clean:
        rm -rf *.o *~ core .depend .*.cmd *.ko *.mod.c .tmp_versions

.PHONY: modules modules_install clean
else
    obj-m := listmodule.o
endif

3 hlist_head和hlist_node链表

拥有一个指针链表头的双向链表.它被分为struct hlist_head头节点和struct hlist_node 元素节点。pprev指向前一个节点的next指针.

现在疑问来了:为什么pprev不是prev也就是一个指针,用于简单的指向list的前一个指针呢?这样即使对于first而言,它可以将prev指针指向list的尾结点.

主要是基于以下几个考虑:

hash列表中的list一般元素不多(如果太多了一般是设计出现了问题),即使遍历也不需要太大的代价,同时需要得到尾结点的需求也不多.
如果对于一般节点而言,prev指向的是前一个指针,而对于first也就是hash的第一个元素而言prev指向的是list的尾结点,那么在删除一个元素的时候还需要判断该节点是不是first节点进行处理.而在hlist提供的删除节点的API中,并没有带上hlist_head这个参数,因此做这个判断存在难度.
以上两点说明了为什么不使用prev,现在来说明为什么需要的是pprev。这样的话只需要修改pprev指针的指向就可以删除成员。

3.1 初始化

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

3.2 插入

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;
    h->first = n;
    n->pprev = &h->first;
}
/* 节点n插入到节点next之前 */
/* 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;
    *(n->pprev) = n;
}
/* 节点n插入到节点next之后 */
static inline void hlist_add_after(struct hlist_node *n,
                                        struct hlist_node *next)
{
    next->next = n->next;
    n->next = next;
    next->pprev = &n->next;

    if(next->next)
        next->next->pprev  = &next->next;
}

3.3 删除

static inline void __hlist_del(struct hlist_node *n)
{
        struct hlist_node *next = n->next;
        struct hlist_node **pprev = n->pprev;
        *pprev = next;
        if (next)
                next->pprev = pprev;
}

static inline void hlist_del(struct hlist_node *n)
{
        __hlist_del(n);
        n->next = LIST_POISON1;
        n->pprev = LIST_POISON2;
}

static inline void hlist_del_init(struct hlist_node *n)
{
        if (!hlist_unhashed(n)) {
                __hlist_del(n);
                INIT_HLIST_NODE(n);
        }
}

3.4 遍历

#define hlist_for_each(pos, head) \
        for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
             pos = pos->next)
#define hlist_for_each_safe(pos, n, head) \
        for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
             pos = n)
#define hlist_entry(ptr, type, member) container_of(ptr,type,member)
#define hlist_for_each_entry(tpos, pos, head, member)                    \
        for (pos = (head)->first;                                        \
             pos && ({ prefetch(pos->next); 1;}) &&                      \
                ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
             pos = pos->next)
#define hlist_for_each_entry_continue(tpos, pos, member)                 \
        for (pos = (pos)->next;                                          \
             pos && ({ prefetch(pos->next); 1;}) &&                      \
                ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
             pos = pos->next)
#define hlist_for_each_entry_from(tpos, pos, member)                     \
        for (; pos && ({ prefetch(pos->next); 1;}) &&                    \
                ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
             pos = pos->next)
#define hlist_for_each_entry_safe(tpos, pos, n, head, member)            \
        for (pos = (head)->first;                                        \
             pos && ({ n = pos->next; 1; }) &&                           \
                ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
             pos = n)

3.5 其它

static inline int hlist_unhashed(const struct hlist_node *h)
{
    return !h->pprev;
}

static inline int hlist_empty(const struct hlist_head *h)
{
    return !h->first;
}

3.6 hlish_head示例

#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/init.h>
#include <linux/version.h>
#include <linux/list.h>
#include <linux/slab.h>

MODULE_LICENSE("GPL");

#define init_name_hash()                0
#define IFNAMSIZ 16

#define NETDEV_HASHBITS 8
#define NETDEV_HASHENTRIES (1 << NETDEV_HASHBITS)

/* 
 * partial_hash_update函数。假设每个字符占用4位 
 */
static inline unsigned long
partial_name_hash(unsigned long c, unsigned long prevhash)
{
  return (prevhash + (c << 4) + (c >> 4)) * 11;
}

/*
 * long型->int型
 */
static inline unsigned long end_name_hash(unsigned long hash)
{
  return (unsigned int) hash;
}

/* 
 * 为一个字符串计算哈希值 
 */
static inline unsigned int
full_name_hash(const unsigned char *name, unsigned int len)
{
    unsigned long hash = init_name_hash();
    while (len--)
        hash = partial_name_hash(*name++, hash);
    return end_name_hash(hash);
}

/*
 * 定义hash表头
 */
struct net {
    struct hlist_head       *dev_name_head;
};

static inline struct hlist_head *dev_name_hash(struct net *net,
                                               const char *name)
{
    unsigned hash = full_name_hash(name, strnlen(name, IFNAMSIZ));
    return &net->dev_name_head[hash & ((1 << NETDEV_HASHBITS) - 1)];
}  

static struct hlist_head *netdev_create_hash(void)
{
    int i;
    struct hlist_head *hash;

    hash = kmalloc(sizeof(*hash) * NETDEV_HASHENTRIES, GFP_KERNEL);
    if (hash != NULL)
        for (i = 0; i < NETDEV_HASHENTRIES; i++)
            INIT_HLIST_HEAD(&hash[i]);

    return hash;
}

struct net_device {
    char    name[IFNAMSIZ];
    struct  hlist_node name_hlist;
    int     net_num;
};

struct net_device *dev_get_by_name(struct net *net, const char *name)
{
    struct hlist_node *p;
    hlist_for_each(p, dev_name_hash(net, name)) {
    struct net_device *dev = hlist_entry(p, struct net_device, name_hlist);
    if (!strncmp(dev->name, name, IFNAMSIZ))
        return dev;
    }
    return NULL;
}

static struct net net_space;
static struct net_device *devices;
static int hlist_module_init(void) 
{
    const   int dev_num = 10;
            int i;
    
    net_space.dev_name_head = netdev_create_hash();
    if (net_space.dev_name_head == NULL) {
        goto err_name;
    }
    devices = kmalloc(sizeof(struct net_device) * dev_num, GFP_KERNEL);
    if (devices == NULL) {
        goto err_dev;
    }
    for (i = 0; i < dev_num; ++i) {
        snprintf(devices[i].name, IFNAMSIZ, "eth%d", i); 
        devices[i].net_num = i;
        hlist_add_head(&devices[i].name_hlist,
                dev_name_hash(&net_space, devices[i].name));
    }
    struct net_device *dev;
    dev = dev_get_by_name(&net_space, "eth1");
    if (dev) {
        printk("%s, %d\n", dev->name, dev->net_num);
    }
    return 0;
err_dev:
    kfree(net_space.dev_name_head);
err_name:
    return -ENOMEM;
}

static void hlist_module_exit(void) {
    kfree(devices);
    kfree(net_space.dev_name_head);
}

module_init(hlist_module_init);
module_exit(hlist_module_exit);

Linux内核10-list_head和hlist_head的理解

对linux内核中使用的链表结构做一个深入的研究