Linux内核hash链表的理解和使用

一. hash链表的介绍

二. hash链表操作原理及使用

1. hash链表的结构介绍

        先给出hash链表的示意结构，对hash链表有一个整体的认识，如下图所示：

如图可知：

        1. 每个hash链表以first作为链表的头，hash链表是由多个以first作为头的链表组成，如上图的数组arr[n]中n，n表示链表数量。

        2. 每个hlist_node的next成员保存的是下一个hlist_node的地址，hlist_node的pprev成员保存的是前一个hlist_node的next成员的地址，如果是链表第一个元素，保存的是first的地址。

        3. 最后一个hlist_node的next成员的内容是NULL，也就是指向NULL。

为什么不把hash链表的每条链设计成内核普通链表的形态呢？

        1. 节省空间。因为struct list_head *next，struct list_head *prev，加起来是8个字节，struct hlist_node *first只需要4个字节，每个头部可以省略4字节，整个hash链表就可以省略4*n个字节，所以链表头设计为只有4字节。

        2. 不需要前向遍历。hash链表只需要后向遍历就可以，所以不需要升级成普通链表形式。

        3. 对于节点的操作可以使用统一的接口。例如在删除节点时，删除头节点和普通节点都可以使用__hlist_del函数来删除，下面会分析到。 

2. 基本数据结构

1.  
   struct hlist_head {
2.  
   struct hlist_node *first;
3.  
   };
4.  
    
5.  
   struct hlist_node {
6.  
   struct hlist_node *next, **pprev;
7.  
   };

        hash链表由链表头和链表节点组成，分别对应不同的结构体。链表头是由一个struct hlist类型的first指针组成，链表节点则是由struct hlist类型的next指针和二级指针pprev组成。

3. hash链表的初始化

1.  
   // 初始化struct hlist_head变量, 例如struct hlist_head head = HLIST_HEAD_INIT;
2.  
   #define HLIST_HEAD_INIT { .first = NULL }
3.  
    
4.  
   // 定义struct hlist_head变量并初始化, 例如HLIST_HEAD(objects)
5.  
   #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
6.  
    
7.  
   // 初始化ptr指向的struct hlist_head变量, 例如INIT_HLIST_HEAD(&object->area_list)
8.  
   #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)

        hash链表的初始化是把链表头的first成员置位NULL，各个宏的区别见上面代码上方的注释。

4. hash链表元素的删除

1.  
   static inline void __hlist_del(struct hlist_node *n)
2.  
   {
3.  
   struct hlist_node *next = n->next;
4.  
   struct hlist_node **pprev = n->pprev;
5.  
   *pprev = next;
6.  
   if (next)
7.  
   next->pprev = pprev;
8.  
   }

        __hlist_del函数的作用是从hash链表中删除节点n，有两种情况，一种是删除头结点，一种是删除普通节点。示意图如下所示：

删除头结点：

 分析：

1. struct hlist_node *next = n->next

        n->next保存的是node a的地址，next = n->next，所以next保存的是node a的地址，next指向node a。

2. struct hlist_node **pprev = n->pprev

        n->pprev保存的是first的地址，pprev = n->pprev，所以pprev保存的是first的地址

3. *pprev = next

        pprev表示first的地址值，*pprev表示取first地址的值，*pprev = next表示将next的地址赋值给first。

4. if (next) next->pprev = pprev

        如果next为空，也就是node a不存在，则不继续操作，如果next不为NULL，则node a的pprev成员指向first。

删除普通节点：

 分析：

1. struct hlist_node *next = n->next

        n->next保存的是node b的地址，next = n->next，所以next保存的是node b的地址，next指向node b。

2. struct hlist_node **pprev = n->pprev

        n->pprev保存的是node a的next成员的地址，pprev = n->pprev，所以pprev保存的是node a的next成员的地址

3. *pprev = next

        pprev表示first的地址值，*pprev表示取first地址的值，*pprev = next表示将next的地址赋值给first。

4. if (next) next->pprev = pprev

        如果next为空，也就是node b不存在，则不继续操作，如果next不为NULL，则node b的pprev成员指向first。

小结：        

        从删除头结点和普通节点的示意图来看，__list_del函数是同时适用于两种情况的删除的。

5. hash链表元素添加

1.  
   static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
2.  
   {
3.  
   struct hlist_node *first = h->first;
4.  
   n->next = first;
5.  
   if (first)
6.  
   first->pprev = &n->next;
7.  
   h->first = n;
8.  
   n->pprev = &h->first;
9.  
   }
10.  
     
11.  
    /* next must be != NULL */
12.  
    static inline void hlist_add_before(struct hlist_node *n,
13.  
    struct hlist_node *next)
14.  
    {
15.  
    n->pprev = next->pprev;
16.  
    n->next = next;
17.  
    next->pprev = &n->next;
18.  
    *(n->pprev) = n;
19.  
    }
20.  
     
21.  
    static inline void hlist_add_behind(struct hlist_node *n,
22.  
    struct hlist_node *prev)
23.  
    {
24.  
    n->next = prev->next;
25.  
    prev->next = n;
26.  
    n->pprev = &prev->next;
27.  
     
28.  
    if (n->next)
29.  
    n->next->pprev = &n->next;
30.  
    }

        hlist_add_head函数用于添加链表头结点，示意图如下：

 分析：

1. struct hlist_node *first = h->first

        保存第一个节点（node h）的地址为first指针的值。

2. n->next = first

        node n的next指针的值被赋值为node h的地址。

3. if (first)
        first->pprev = &n->next

        如果node h存在，则node h的pprev指针的值被赋值为node n的next指针的地址

4. h->first = n

        h->first指针的值被赋值为node n指针的值。

5. n->pprev = &h->first

        node n的pprev指针的值h->first指针的地址。

        hlist_add_before函数有hlist_node n和hlist_node next两个参数，表示在node next前添加node n，示意图如下：

分析：

1. n->pprev = next->pprev

        next->pprev表示是node b的next指针的地址，n->pprev = next->pprev表示n->pprev指针的值保存的是node b的next指针的地址。

2. n->next = next

        node n的next指针的值被赋值为node next的地址。

3. next->pprev = &n->next

        node next的pprev指针的值被赋值为node n的next指针的地址。

4. *(n->pprev) = n

        node next的pprev指针的值是node b的next指针的地址，所以*(n->pprev)是node b的next指针的内容被赋值为node n的地址

        hlist_add_behind函数有hlist_node n和hlist_node prev两个参数，表示在node prev后添加node n，示意图如下：

 分析：

1. n->next = prev->next

        prev->next表示是node b的地址，n->next = prev->next表示node n的next指针的值被赋值为node b的地址。

2. prev->next = n

        node prev的next指针的值是node n的地址。

3. n->pprev = &prev->next

        node prev的next指针的地址赋值为node n的pprev指针的值。

4. if (n->next)
        n->next->pprev  = &n->next

        if (n->next)表示如果node b存在，n->next是node b的地址，n->next->pprev是node b的pprev指针的值被赋值为node n的next指针的地址。

6. hash链表元素遍历

1.  
   #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
2.  
    
3.  
   #define hlist_for_each(pos, head) \
4.  
   for (pos = (head)->first; pos ; pos = pos->next)
5.  
    
6.  
   #define hlist_for_each_safe(pos, n, head) \
7.  
   for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
8.  
   pos = n)
9.  
    
10.  
    #define hlist_entry_safe(ptr, type, member) \
11.  
    ({ typeof(ptr) ____ptr = (ptr); \
12.  
    ____ptr ? hlist_entry(____ptr, type, member) : NULL; \
13.  
    })

        hlist_entry宏与Linux内核链表理解与使用解析的list_entry一样，都是封装了container_of函数，此处不再分析。

        hlist_for_each宏用于遍历hash链表，分别有pos和head参数，pos指向head的first成员，通过next指针遍历整个链表。

        hlist_for_each_safe宏分别有pos和head参数，和list_for_each_safe宏的作用类似，当在遍历链表的时候，删除pos指向的节点，不会影响遍历后面的链表节点。

         hlist_entry_safe则会对ptr的类型做一个检查。

        

三. 总结

        最后以一个hash链表的示例结尾吧，这段代码是引用一个别的博客的，我觉得例子很好，链接list and hlist in kernel，代码粘贴如下

1.  
   #include <linux/module.h>
2.  
   #include <linux/kernel.h>
3.  
   #include <linux/init.h>
4.  
   #include <linux/version.h>
5.  
   #include <linux/list.h>
6.  
   #include <linux/slab.h>
7.  
    
8.  
   MODULE_LICENSE("GPL");
9.  
    
10.  
    #define init_name_hash() 0
11.  
    #define IFNAMSIZ 16
12.  
     
13.  
    #define NETDEV_HASHBITS 8
14.  
    #define NETDEV_HASHENTRIES (1 << NETDEV_HASHBITS)
15.  
    /* partial hash update function. Assume roughly 4 bits per character */
16.  
    static inline unsigned long
17.  
    partial_name_hash(unsigned long c, unsigned long prevhash)
18.  
    {
19.  
    return (prevhash (c << 4) (c >> 4)) * 11;
20.  
    }
21.  
    /*
22.  
    * Finally: cut down the number of bits to a int value (and try to avoid
23.  
    * losing bits)
24.  
    */
25.  
    static inline unsigned long end_name_hash(unsigned long hash)
26.  
    {
27.  
    return (unsigned int) hash;
28.  
    }
29.  
    /* Compute the hash for a name string. */
30.  
    static inline unsigned int
31.  
    full_name_hash(const unsigned char *name, unsigned int len)
32.  
    {
33.  
    unsigned long hash = init_name_hash();
34.  
    while (len--)
35.  
    hash = partial_name_hash(*name , hash);
36.  
    return end_name_hash(hash);
37.  
    }
38.  
     
39.  
    struct net {
40.  
    struct hlist_head *dev_name_head;
41.  
    };
42.  
     
43.  
    static inline struct hlist_head *dev_name_hash(struct net *net,
44.  
    const char *name)
45.  
    {
46.  
    unsigned hash = full_name_hash(name, strnlen(name, IFNAMSIZ));
47.  
    return &net->dev_name_head[hash & ((1 << NETDEV_HASHBITS) - 1)];
48.  
    }
49.  
     
50.  
     
51.  
    static struct hlist_head *netdev_create_hash(void)
52.  
    {
53.  
    int i;
54.  
    struct hlist_head *hash;
55.  
     
56.  
    hash = kmalloc(sizeof(*hash) * NETDEV_HASHENTRIES, GFP_KERNEL);
57.  
    if (hash != NULL)
58.  
    for (i = 0; i < NETDEV_HASHENTRIES; i )
59.  
    INIT_HLIST_HEAD(&hash[i]);
60.  
     
61.  
    return hash;
62.  
    }
63.  
     
64.  
    struct net_device {
65.  
    char name[IFNAMSIZ];
66.  
    struct hlist_node name_hlist;
67.  
    int net_num;
68.  
    };
69.  
     
70.  
    struct net_device *dev_get_by_name(struct net *net, const char *name) {
71.  
    struct hlist_node *p;
72.  
    hlist_for_each(p, dev_name_hash(net, name)) {
73.  
    struct net_device *dev
74.  
    = hlist_entry(p, struct net_device, name_hlist);
75.  
    if (!strncmp(dev->name, name, IFNAMSIZ))
76.  
    return dev;
77.  
    }
78.  
    return NULL;
79.  
    }
80.  
     
81.  
    static struct net net_space;
82.  
    static struct net_device *devices;
83.  
    static int hlist_module_init(void) {
84.  
    const int dev_num = 10;
85.  
    int i;
86.  
    net_space.dev_name_head = netdev_create_hash();
87.  
    if (net_space.dev_name_head == NULL) {
88.  
    goto err_name;
89.  
    }
90.  
    devices = kmalloc(sizeof(struct net_device) * dev_num, GFP_KERNEL);
91.  
    if (devices == NULL) {
92.  
    goto err_dev;
93.  
    }
94.  
    for (i = 0; i < dev_num; i) {
95.  
    snprintf(devices[i].name, IFNAMSIZ, "eth%d", i);
96.  
    devices[i].net_num = i;
97.  
    hlist_add_head(&devices[i].name_hlist,
98.  
    dev_name_hash(&net_space, devices[i].name));
99.  
    }
100.  
     struct net_device *dev;
101.  
     dev = dev_get_by_name(&net_space, "eth1");
102.  
     if (dev) {
103.  
     printk("%s, %d\n", dev->name, dev->net_num);
104.  
     }
105.  
     return 0;
106.  
      
107.  
     err_dev:
108.  
     kfree(net_space.dev_name_head);
109.  
     err_name:
110.  
     return -ENOMEM;
111.  
     }
112.  
      
113.  
      
114.  
     static void hlist_module_exit(void) {
115.  
     kfree(devices);
116.  
     kfree(net_space.dev_name_head);
117.  
     }
118.  
      
119.  
     module_init(hlist_module_init);
120.  
     module_exit(hlist_module_exit);

这篇好文章是转载于：学新通技术网