- 论坛徽章:
- 0
|
是啊，还是有很多东西要考虑，尤其对我这种没有接触过内核开发的人来说，想看看conntrack的hash实现，没看明白，下面是在网上找的一个例子，基本能看清楚，不知道存不存在问题，Godbach帮忙看看：
- /*
- * 以下代码 在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 void
- ct_read_lock(unsigned key)
- {
- read_lock(&__example_conntbl_lock_array[key&CT_LOCKARRAY_MASK].l);
- }
- static inline void
- ct_read_unlock(unsigned key)
- {
- read_unlock(&__example_conntbl_lock_array[key&CT_LOCKARRAY_MASK].l);
- }
- static inline void
- ct_write_lock(unsigned key)
- {
- write_lock(&__example_conntbl_lock_array[key&CT_LOCKARRAY_MASK].l);
- }
- static inline void
- ct_write_unlock(unsigned key)
- {
- write_unlock(&__example_conntbl_lock_array[key&CT_LOCKARRAY_MASK].l);
- }
- static inline void
- ct_read_lock_bh(unsigned key)
- {
- read_lock_bh(&__example_conntbl_lock_array[key&CT_LOCKARRAY_MASK].l);
- }
- static inline void
- ct_read_unlock_bh(unsigned key)
- {
- read_unlock_bh(&__example_conntbl_lock_array[key&CT_LOCKARRAY_MASK].l);
- }
- static inline void
- ct_write_lock_bh(unsigned key)
- {
- write_lock_bh(&__example_conntbl_lock_array[key&CT_LOCKARRAY_MASK].l);
- }
- static inline void
- ct_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);
-
- }
|
|
免费注册
发表于 2010-12-17 17:34
发表于 2010-12-17 17:53