linux内核数据结构---hash表

心已赠人 2022-02-13 15:01 509阅读 0赞

关于linux内核链表请参考“[linux内核数据结构---链表][linux_---]”。

[链表][Link 1]虽然是最常见的数据结构，但实际使用中，由于链表的检索能力较差，更多的是作为队列和栈结构使用，如果需要查询，比如通过pid查找进程，通过描述符查找inode，就需要用到检索更快的数据结构——**[Hash表][Hash]**。  
先来看Hash节点的定义：

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

其中 hlist\_head 为头结点，与链表不同的是还需要一个节点的概念 hlist\_node，他们之间的关系如图：

![hlist\_head][hlist_head]  
左侧是定长数组，每个节点是 hlist\_head ，其中first指向 hlist\_node 节点，hlist\_node又组成一列链表，hlist\_node的链表结构跟 list\_head不同之处在于 hlist\_node 的 pprev 指向了 前一个节点的指针地址。  
**Hash表**使用起来也非常简单，首先通过hash函数计算目标值，得到一个索引，在hlist\_head数组中找到相应位置，再插入链表。Hash的链表Linux也提供了多种操作方式：

#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
    static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h);
    static inline void hlist_add_before(struct hlist_node *n, 
    		struct hlist_node *next)
    static inline void hlist_add_after(struct hlist_node *n, 
    		struct hlist_node *next)
    static inline void hlist_move_list(struct hlist_head *old,
    		struct hlist_head *new);
    
    #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
    #define hlist_for_each(pos, head) \     
            for (pos = (head)->first; pos ; pos = pos->next)
    #define hlist_for_each_entry(tpos, pos, head, member)                    \
            for (pos = (head)->first;                                        \
                 pos &&                                                      \
                    ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
                 pos = pos->next)

INIT\_HLIST\_HEAD —— 初始化链表；  
hlist\_add\_head —— 在链表头插入节点；  
hlist\_add\_before —— 在一个节点之前插入；  
hlist\_add\_after —— 在一个节点之后插入；  
hlist\_entry —— 同list\_entry；  
hlist\_for\_each —— 相关的一系列函数进行链表的遍历，与普通双向链表操作相同。  
除了Hash表中链表的操作，还有一个重要的元素是Hash函数，Hash函数的好坏直接影响Hash表的性能，Hash函数一般来讲跟具体要实现的业务相关，include/linux/jhash.h下实现了几个不同用途的Hash函数，另外，Linux还给出一个简单的Hash函数：

static inline u32 hash_32(u32 val, unsigned int bits)
    {
            /* On some cpus multiply is faster, on others gcc will do shifts */
            u32 hash = val * GOLDEN_RATIO_PRIME_32;
    
            /* High bits are more random, so use them. */
            return hash >> (32 - bits);
    }

这个函数把32位整数Hash成bits位的整数，另外还有 hash\_64 等等Hash函数。  
最后再来通过一个简单的例子看一下Hash表的使用：

#include <linux/kernel.h>
    #include <linux/types.h>
    #include <linux/list.h>
    #include <linux/init.h>
    #include <linux/module.h>
    #include <linux/slab.h>
    #include <linux/hash.h>
    
    struct simple_hash
    {
        int data;
        struct hlist_node node;
    };
    
    struct hlist_head * phash = NULL;
    
    static int __init initialization(void)
    {
        int i,k;
        struct hlist_head * phead;
        struct hlist_node * pnode;
        struct simple_hash * p;
    
        printk(KERN_INFO " init simple start\n");
    
        phash = (struct hlist_head*)kmalloc(sizeof(struct hlist_head) * 0xFF, GFP_KERNEL);
        for (i = 0; i < 0xFF; i++) {
            INIT_HLIST_HEAD(&phash[i]);
        }
        for (i = 0; i < 10; i++) {
            p = (struct simple_hash*)kmalloc(sizeof(struct simple_hash), GFP_KERNEL);
            k = i * 13;
    
            p->data = k;
            INIT_HLIST_NODE(&p->node);
    
            printk(KERN_INFO "insert %d\n", k);
            phead = &phash[hash_32(k, 8)];
            hlist_add_head(&p->node, phead);
        }
        k = 3 * 13;
        phead = &phash[hash_32(k, 8)];
        printk(KERN_INFO "search %d\n", k);
        hlist_for_each_entry(p, pnode, phead, node) {
            if (p->data == k) {
                printk(KERN_INFO " find it\n");
            }
        }
    
        printk(KERN_INFO "init simple end\n");
        return 0;
    }
    
    static void __exit cleanup(void)
    {
        int i;
        struct hlist_head * phead = NULL;
        struct simple_hash * p = NULL;
        printk(KERN_INFO "cleanup simple\n");
    
        if (phash == NULL) {
            return;
        }
    
        for (i = 0; i < 0xFF; i++) {
            phead = &phash[i];
            while (!hlist_empty(phead)) {
                p = hlist_entry(phead->first, struct simple_hash, node);
                printk(KERN_INFO "delete %d", p->data);
                hlist_del(&p->node);
                kfree(p);
            }
        }
        kfree(phead);
    }
    
    module_init(initialization);
    module_exit(cleanup);
    
    MODULE_AUTHOR("cppbreak cppbreak@gmail.com");
    MODULE_DESCRIPTION("A simple linux kernel module");
    MODULE_VERSION("V0.1");
    MODULE_LICENSE("Dual BSD/GPL");

[linux_---]: http://blog.csdn.net/shanzhizi/article/details/8963296
[Link 1]: http://tech.fancymore.com/page/143.html
[Hash]: http://blog.csdn.net/shanzhizi/article/category/1173806
[hlist_head]: http://tech.fancymore.com/files/2012/07/hlist_head.png