内核中hash表（以net_device为例）

佚名 6年前 (2019-04-18) 随笔 435人围观抢沙发百度已收录

　　下边函数实现将新的 net_device 设备插入到内核链表中

/* * Device list insertion */ static void list_netdevice(struct net_device *dev) { struct net *net = dev_net(dev); ASSERT_RTNL(); write_lock_bh(&dev_base_lock); list_add_tail_rcu(&dev->dev_list, &net->dev_base_head); hlist_add_head_rcu(&dev->name_hlist, dev_name_hash(net, dev->name)); hlist_add_head_rcu(&dev->index_hlist, dev_index_hash(net, dev->ifindex)); write_unlock_bh(&dev_base_lock); dev_base_seq_inc(net); }

　　如上所示，一共有一个链表，两个hash表，其中一个是name hash，另一个是ifindex hash。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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

static struct hlist_head * __net_init 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;
}

　　如上所示，一共有(1<<8 = 256) 个hash entry， key值为 8 bits。

　　获取hash entry代码如下：先计算出一个unsigned int(32bits)的hash，然后稍微操作一下，取高8字节作为 key 值。

static inline struct hlist_head *dev_name_hash(struct net *net, const char *name)
{   
    unsigned int hash = full_name_hash(name, strnlen(name, IFNAMSIZ));

    return &net->dev_name_head[hash_32(hash, NETDEV_HASHBITS)];
}

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

　　访问hash表代码如下：先获取所在的entry，然后遍历该entry。

struct net_device *dev_get_by_name_rcu(struct net *net, const char *name)
{
    struct net_device *dev;   
    struct hlist_head *head = dev_name_hash(net, name);

    hlist_for_each_entry_rcu(dev, head, name_hlist)
        if (!strncmp(dev->name, name, IFNAMSIZ))
            return dev;       

    return NULL;                                                                                                                                        
}