1. 首页
  2. 文章中心
  3. linux 内核

linux 内核中 hash 的使用Linux内核提供的哈希hlist各种操作宏内核中使用实例

118 阅读 0 评论
我是靠谱客的博主 舒适蜡烛，最近开发中收集的这篇文章主要介绍linux 内核中 hash 的使用Linux内核提供的哈希hlist各种操作宏内核中使用实例，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

目录

Linux内核提供的哈希hlist

各种操作宏

内核中使用实例

先定义需要的结构 

辅助函数

初始化表头

增加节点（支持增加多个）

查找单个节点

删除节点（多个节点）

销毁表

在neifilter中需要根据用户态发送的IPv4来进行匹配经过hook点的包，并做阻断，所以需要存储一系列ip,增删查操作。内核已有hash表数据结构定义和操作。

Linux内核提供的哈希hlist

struct hlist_head {
    struct hlist_node *first;
};

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

各种操作宏

#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)
static inline int hlist_unhashed(const struct hlist_node *h)
static inline int hlist_empty(const struct hlist_head *h)
static inline void __hlist_del(struct hlist_node *n)
static inline void hlist_del(struct hlist_node *n)
static inline void hlist_del_init(struct hlist_node *n)
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_behind(struct hlist_node *n,struct hlist_node *prev)
static inline void hlist_add_fake(struct hlist_node *n)
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_safe(pos, n, head) 
        for (pos = (head)->first; pos && ({ n = pos->next; 1; }); 
             pos = n)
#define hlist_entry_safe(ptr, type, member) 
        ({ typeof(ptr) ____ptr = (ptr); 
           ____ptr ? hlist_entry(____ptr, type, member) : NULL; 
        })
#define hlist_for_each_entry(pos, head, member)                         
        for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);
             pos;                                                       
             pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
#define hlist_for_each_entry_continue(pos, member)                      
        for (pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member);
             pos;                                                       
             pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
#define hlist_for_each_entry_from(pos, member)                          
        for (; pos;                                                     
             pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
#define hlist_for_each_entry_safe(pos, n, head, member)                 
        for (pos = hlist_entry_safe((head)->first, typeof(*pos), member);
             pos && ({ n = pos->member.next; 1; });                     
             pos = hlist_entry_safe(n, typeof(*pos), member))

内核中使用实例

内核中分配内存和释放内存用到的接口为kmalloc/kfree, 需要分配bucket数组和每个节点。

先定义需要的结构 

这里是需要存储ipv4， 即一个uint32_t 的数字

//比如需要存储Ipv4
//定义一个存储Ipv4 的节点结构体
struct SNodeIpv4
{
    struct hlist_node hnode;
    uint32_t ipv4;
};

#define HASH_COUNT 9973 //指定hash bucket的数量
static struct hlist_head *ipv4_hash = NULL; //head

辅助函数

自定义结构计算hash值的函数和相等判断函数，这里的自定义结构是一个Ipv4数字

//计算hash值
struct hlist_head *call_hash_ipv4(const uint32_t *ipv4)
{
    uint32_t val = 0;
    if (NULL == ipv4_hash || NULL == ipv4)
    {
        return NULL;
    }
    val = *ipv4 % HASH_COUNT;
    return &ipv4_hash[val];
}

//相等判断
int eq_ipv4(const uint32_t *_left, const uint32_t *_right)
{
    if (NULL == _left || NULL == _right)
    {
        return 0;
    }

    if (*_left ^ *_right)
    {
        return 0;
    }
    return 1;
}

初始化表头

int InitHashIpv4(void)
{
    int i = 0;
    int retCode = 0;

    do
    {
        ipv4_hash = (struct hlist_head *)kmalloc(sizeof(struct hlist_head) * HASH_COUNT, GFP_ATOMIC);
        if (NULL == ipv4_hash)
        {
            printk(KERN_ERR "%s:%i ipv4_hash alloc errorn", __FILE__, __LINE__);
            retCode = -1;
            break;
        }
        //初始化hash表头
        for (i = 0; i < HASH_COUNT; i++)
        {
            INIT_HLIST_HEAD(&ipv4_hash[i]);
        }
        printk(KERN_DEBUG "%s:%i InitHashIpv4 succ.n", __FILE__, __LINE__);
    }while(false);

    return retCode;
}

增加节点（支持增加多个）

int AddIpv4(const uint32_t *_ipv4, uint32_t count)
{
    int i = 0;
    const uint32_t *node_ipv4 = _ipv4;
    struct hlist_head *hash_bucket = NULL;
    struct SNodeIpv4 *pNode = NULL;
    struct hlist_node *next = NULL;
    int retCode = 0;
    if (NULL == node_ipv4 || count < 1)
    {
        return -1;
    }

    for(i = 0; i < count; ++i)
    {
        //找到bucket
        node_ipv4 = _ipv4 + i;
        hash_bucket = call_hash_ipv4(node_ipv4);
        if (NULL == hash_bucket)
        {
            retCode = -1;
            break;
        }

        hlist_for_each_entry_safe(pNode, next, hash_bucket, hnode)
        {
            if (eq_ipv4(&pNode->ipv4, node_ipv4))
            {
                //已经存在
                continue;
            }
        }
        
        //分配一个node
        pNode = (struct SNodeIpv4 *)kmalloc(sizeof(struct SNodeIpv4), GFP_ATOMIC);
        if (pNode == NULL)
        {
            printk(KERN_ERR "%s:%i SNodeIpv4 alloc errorn", __FILE__, __LINE__);
            retCode = -1;
            break;
        }
        memset(pNode, 0, sizeof(struct SNodeIpv4));
        INIT_HLIST_NODE(&pNode->hnode);
        memcpy(&pNode->ipv4, node_ipv4, sizeof(pNode->ipv4));
        hlist_add_head(&pNode->hnode, hash_bucket);
        printk(KERN_DEBUG "%s:%i AddIpv4 [%u]n", __FILE__, __LINE__, *node_ipv4);
    }

    return retCode;
}

查找单个节点

int FindIpv4(const uint32_t *_ipv4)
{
    struct hlist_head *hash_bucket = NULL;
    struct SNodeIpv4 *pNode = NULL;
    struct hlist_node *next = NULL;
    int retCode = -1;

    if (NULL == _ipv4)
    {
        return -1;
    }

    do
    {
        hash_bucket = call_hash_ipv4(_ipv4);
        if (NULL == hash_bucket)
        {
            retCode = -1;
            break;
        }

        hlist_for_each_entry_safe(pNode, next, hash_bucket, hnode)
        {
            if (eq_ipv4(&pNode->ipv4, _ipv4))
            {
                retCode = 0;
                break;
            }
        }
    }while(false);

    return retCode;
}

删除节点（多个节点）

int DelIpv4(const uint32_t *_ipv4, uint32_t count)
{
    int i = 0;
    const uint32_t *node_ipv4 = _ipv4;
    struct hlist_head *hash_bucket = NULL;
    struct SNodeIpv4 *pNode = NULL;
    struct hlist_node *next = NULL;

    int retCode = 0;

    if (NULL == _ipv4 || count < 1)
    {
        return -1;
    }

    for(i = 0; i < count; ++i)
    {
        node_ipv4 = _ipv4 + i;
        hash_bucket = call_hash_ipv4(node_ipv4);
        if (NULL == hash_bucket)
        {
            retCode = -1;
            break;
        }

        hlist_for_each_entry_safe(pNode, next, hash_bucket, hnode)
        {
            if (eq_ipv4(&pNode->ipv4, node_ipv4))
            {
                hlist_del(&pNode->hnode);
                kfree(pNode);
            }
        }
    }

    return retCode;
}

销毁表

int DestoryHashIpv4(void)
{
    struct SNodeIpv4 *pNode = NULL;
    struct hlist_node *next = NULL;
    int i = 0;
    int retCode = 0;
    
    do
    {
        if (NULL == ipv4_hash)
        {
            printk(KERN_ERR "%s:%i ipv4_hash is NULLn", __FILE__, __LINE__);
            retCode = -1;
            break;
        }

        for (i = 0; i < HASH_COUNT; i++)
        {
            hlist_for_each_entry_safe(pNode, next, &ipv4_hash[i], hnode)
            {
                hlist_del(&pNode->hnode);
                kfree(pNode);
            }
        }

        kfree(ipv4_hash);
        ipv4_hash = NULL;
    } while (false);  

    return retCode;
}

凡是过往，即为序章

最后

以上就是舒适蜡烛为你收集整理的linux 内核中 hash 的使用Linux内核提供的哈希hlist各种操作宏内核中使用实例的全部内容，希望文章能够帮你解决linux 内核中 hash 的使用Linux内核提供的哈希hlist各种操作宏内核中使用实例所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(78)

相关文章

语义分割损失函数系列(1):交叉熵损失函数这里注意：
语义分割损失函数系列(1):交叉熵损失函数这里注意：
list_for_each与list_for_each_entry具体解释
list_for_each与list_for_each_entry具体解释
list_for_each_entry的理解
list_for_each_entry的理解
Linux链表操作
Linux链表操作
linux 内核中 hash 的使用Linux内核提供的哈希hlist各种操作宏内核中使用实例
linux 内核中 hash 的使用Linux内核提供的哈希hlist各种操作宏内核中使用实例
Linux内核 hlist_head/hlist_node结构解析
Linux内核 hlist_head/hlist_node结构解析
linux内核 hash表的基本使用
linux内核 hash表的基本使用
漫谈linux内核哈希表,linux内核中的哈希散列表
漫谈linux内核哈希表,linux内核中的哈希散列表

评论列表共有 0 条评论

立即
投稿
返回
顶部