linux内核哈希表一例v1.0

技术2025-04-04 31

作者：clusterlee

题记：毕业课题需要，再内核环境下写了个哈希表，和使用C# 、Java 、C++的hash_map相比考虑的东西多了许多，受益匪浅。

要点：

1.内存的分配和回收

2.临界区的互斥、并发控制

代码结构:

hash_example/hash_example.c /*内核模块，使用示例*/

hash_example/hash_table.h /* 结构类型定义、宏以及接口定义*/

hash_example/hash_table.c /* 接口实现*/

hash_example/Makefile

* 以下代码在2.6.23 下调试通过

//---------------------------------------hash_table.h-----------------------------------------------

#define EXAMPLE_TAB_BITS 16#define EXAMPLE_TAB_SIZE (1<<EXAMPLE_TAB_BITS)#define EXAMPLE_TAB_MASK (EXAMPLE_TAB_SIZE-1)#define EXAMPLE_F_HASHED 0x0001

struct example{ struct list_head node; char *s; /*主体 */ spinlock_t lock; /*自旋锁 */ atomic_t refcnt; /*引用计数*/ volatile __u16 flags; /*辅助标记 */ };

extern int example_init(void); /* 内存空间初始化*/

extern void example_cleanup(void); /* 内存清理回收*/

extern int example_hash(struct example *cp);

extern int example_unhash(struct example *cp);

extern struct example *example_get(char *s); /*查找*/

extern struct example* example_new(char *p); /*构造新项，并加入哈希表 */

extern int example_destroy(struct example *cp); /* 销毁一个哈希表中的项*/

extern inline void example_put(struct example *cp); /*引用计数减一*/

//--------------------------------------hash_example.c---------------------------------------------------

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

#include "hash_table.h"

static int __init hash_init(void){ int ret; struct example *cp=NULL; printk(KERN_ALERT "hash mod insert............../n"); ret=example_init(); if(ret<0) { printk(KERN_INFO "can't setup conrol./n."); } example_new("My girl_1"); example_new("My girl_2"); cp=example_get("My girl_2"); if(NULL!=cp) printk(KERN_ALERT "cp->s:%s/n",cp->s); example_put(cp); example_destroy(cp); cp=example_get("My girl_2"); if(NULL==cp) printk(KERN_ALERT "break with girl_2!/n"); return 0;}static void __exit hash_exit(void){ printk(KERN_ALERT "hash mod remove............../n"); example_cleanup();}module_init(hash_init);module_exit(hash_exit);

//--------------------------------------hash_table.c---------------------------------------------------

#include <linux/module.h>

#include <linux/kernel.h>#include <linux/init.h>

#include <linux/vmalloc.h>#include <linux/jhash.h>#include <linux/random.h>#include <linux/seq_file.h>#include <linux/sched.h>

#include "hash_table.h"

/* SLAB 分配器 */static struct kmem_cache *example_cachep;/* hash table */static struct list_head *example_tab;/* 记录 struct example 总数目，以便回收内存空间 */static atomic_t example_count=ATOMIC_INIT(0);/* hash函数使用的随机值 */static unsigned int example_rnd;

/** 一套锁*/#define CT_LOCKARRAY_BITS 4#define CT_LOCKARRAY_SIZE (1<<CT_LOCKARRAY_BITS)#define CT_LOCKARRAY_MASK (CT_LOCKARRAY_SIZE-1)

struct tcp_shift_aligned_lock{ rwlock_t l;}__attribute__((__aligned__(SMP_CACHE_BYTES)));

struct tcp_shift_aligned_lock __example_conntbl_lock_array[CT_LOCKARRAY_SIZE] __cacheline_aligned;

static inline voidct_read_lock(unsigned key){ read_lock(&__example_conntbl_lock_array[key&CT_LOCKARRAY_MASK].l);}static inline voidct_read_unlock(unsigned key){ read_unlock(&__example_conntbl_lock_array[key&CT_LOCKARRAY_MASK].l);}static inline voidct_write_lock(unsigned key){ write_lock(&__example_conntbl_lock_array[key&CT_LOCKARRAY_MASK].l);}static inline voidct_write_unlock(unsigned key){ write_unlock(&__example_conntbl_lock_array[key&CT_LOCKARRAY_MASK].l);}static inline voidct_read_lock_bh(unsigned key){ read_lock_bh(&__example_conntbl_lock_array[key&CT_LOCKARRAY_MASK].l);}static inline voidct_read_unlock_bh(unsigned key){ read_unlock_bh(&__example_conntbl_lock_array[key&CT_LOCKARRAY_MASK].l);}static inline voidct_write_lock_bh(unsigned key){ write_lock_bh(&__example_conntbl_lock_array[key&CT_LOCKARRAY_MASK].l);}static inline voidct_write_unlock_bh(unsigned key){ write_unlock_bh(&__example_conntbl_lock_array[key&CT_LOCKARRAY_MASK].l);}

/* hash 函数 */static inline unsigned example_hash_key(char *p){ int n; /*简单示例*/ n=strlen(p); return jhash_2words(n,p[0],example_rnd)&EXAMPLE_TAB_MASK;}

inline void example_put(struct example* cp){ atomic_dec(&cp->refcnt);}int example_hash(struct example *cp){ unsigned hash; int ret; hash=example_hash_key(cp->s); ct_write_lock(hash); if(!(cp->flags&EXAMPLE_F_HASHED)) { list_add(&cp->node,&example_tab[hash]); cp->flags|=EXAMPLE_F_HASHED; atomic_add(1,&cp->refcnt); ret=1; } else { ret=0; } ct_write_unlock(hash); return ret;}

int example_unhash(struct example *cp){ unsigned hash; int ret; hash=example_hash_key(cp->s); ct_write_lock(hash); if(cp->flags&EXAMPLE_F_HASHED) { list_del(&cp->node); cp->flags &=~EXAMPLE_F_HASHED; atomic_sub(1,&cp->refcnt); ret=1; } else { ret=0; } ct_write_unlock(hash); return ret;}struct example *example_get(char *s){ struct example *cp; unsigned hash; hash=example_hash_key(s); ct_read_lock(hash); list_for_each_entry(cp,&example_tab[hash],node) { spin_lock(&cp->lock); if(strncmp(cp->s,s,strlen(cp->s))==0) { spin_unlock(&cp->lock); atomic_inc(&cp->refcnt); ct_read_unlock(hash); return cp; } spin_unlock(&cp->lock); } ct_read_unlock(hash); return NULL; }struct example* example_new(char *p){ struct example *cp=NULL; int n; cp=kmem_cache_alloc(example_cachep,GFP_ATOMIC); if(cp==NULL) { return NULL; } memset(cp,0,sizeof(*cp)); INIT_LIST_HEAD(&cp->node); spin_lock_init(&cp->lock); n=strlen(p); cp->s=(char*)kmalloc(((n+1)*sizeof(char)),GFP_ATOMIC); memcpy(cp->s,p,(n+1)*sizeof(char)); (cp->s)[n]='/0'; atomic_inc(&example_count); atomic_set(&cp->refcnt,0); example_hash(cp); return cp;}int example_destroy( struct example* cp){ if (cp==NULL) return 0; atomic_inc(&cp->refcnt);

if(! example_unhash(cp)) { example_put(cp); return 0; } if(likely((atomic_read(&cp->refcnt))==1)) { spin_lock(&cp->lock); if(cp->s) kfree(cp->s); spin_unlock(&cp->lock); atomic_dec(&example_count); kmem_cache_free(example_cachep,cp); return 1; } example_hash(cp); //还有人使用此项，hash back! example_put(cp) ; return 0;}

int example_init(void){ int idx; /* allocte hash table*/ if(!(example_tab=vmalloc(EXAMPLE_TAB_SIZE*sizeof(struct list_head)))) return -ENOMEM; example_cachep=kmem_cache_create("example", sizeof(struct example),0, SLAB_HWCACHE_ALIGN,NULL); if(!example_cachep) { vfree(example_tab); return -ENOMEM; } /*init hash tab*/ for(idx=0;idx<EXAMPLE_TAB_SIZE;idx++) { INIT_LIST_HEAD(&example_tab[idx]); } /*init locking tab*/ for(idx=0;idx<CT_LOCKARRAY_SIZE;idx++) { rwlock_init(&__example_conntbl_lock_array[idx].l); } /* generate random*/ get_random_bytes(&example_rnd,sizeof(example_rnd)); return 0; }

static void example_flush(void){ int idx; struct list_head *list=NULL; struct example *cp=NULL; flush_again: for(idx=0;idx<EXAMPLE_TAB_SIZE;idx++) { ct_write_lock(idx); list=&example_tab[idx]; while(!list_empty(list)) { cp=list_entry(list->next,struct example,node); ct_write_unlock(idx); // example_destroy 有可能使用了相同的锁，所以先解锁

if(!example_destroy(cp)) { ct_write_lock(idx); break; } ct_write_lock(idx); } ct_write_unlock(idx); } if(atomic_read(&example_count)!=0) { schedule(); //有些example项，可能正在被使用不能一下被destroy，所以等待下次回收空间 goto flush_again; } }

void example_cleanup(void){ example_flush(); kmem_cache_destroy(example_cachep); vfree(example_tab); }

后记：。。。。。辛苦。。。。

最新回复(0)