linux内核中一些常用的数据结构和操作

SH表适用于不需要对整个空间元素进行排序，而是只需要能快速找到某个元素的场合，是一种以空间换时间的方法，本质也是线性表，但由一个大 的线性表拆分为了多个小线性表，由于只需要查找小表，因此搜索速度就会线性查整个大表提高很多，理想情况下，有多少个小线性表，搜索速度就提高了多少倍， 通常把小线性表的表头综合为一个数组，大小就是HASH表的数量。HASH表速度的关键是HASH函数的设计，HASH函数根据每个元素中固定的参数进行计算，算出一个不大于HASH表数量的索引值，表示该元 素需要放在该索引号对应的那个表中，对于固定的参数，计算结果始终是固定的，但对于不同的参数值，希望计算出来的结果能尽可能地平均到每个索引值， HASH函数计算得越平均，表示每个小表中元素的数量都会差不多，这样搜索性能将越好。HASH函数也要尽可能的简单，以减少计算时间，常用的算法是将参 数累加求模，在include/linux/jhash.h中已经定义了一些HASH计算函数，可直接使用。HASH表在路由cache表，状态连接表等处用得很多。举例，连接跟踪中根据tuple值计算HASH：// net/ipv4/netfilter/ip_conntrack_core.cu_int32_t

hash_conntrack(const struct ip_conntrack_tuple *tuple)

{

#if 0

dump_tuple(tuple);

#endif

return (jhash_3words(tuple->src.ip,

(tuple->dst.ip ^ tuple->dst.protonum),

(tuple->src.u.all | (tuple->dst.u.all  16)),

ip_conntrack_hash_rnd) % ip_conntrack_htable_size);

}// include/linux/jhash.h

static inline u32 jhash_3words(u32 a, u32 b, u32 c, u32 initval)

{

a += JHASH_GOLDEN_RATIO;

b += JHASH_GOLDEN_RATIO;

c += initval;__jhash_mix(a, b, c);return c;

}4. 定时器(timer)linux内核定时器由以下结构描述：/* include/linux/timer.h */

struct timer_list {

struct list_head list;

unsigned long expires;

unsigned long data;

void (*function)(unsigned long);

};list：timer链表

expires：到期时间

function：到期函数，时间到期时调用的函数

data：传给到期函数的数据，实际应用中通常是一个指针转化而来，该指针指向一个结构

timer的操作：增加timer，将timer挂接到系统的timer链表：

extern void add_timer(struct timer_list * timer);删除timer，将timer从系统timer链表中拆除：

extern int del_timer(struct timer_list * timer);

(del_timer()函数可能会失败，这是因为该timer本来已经不在系统timer链表中了，也就是已经删除过了)对于SMP系统，删除timer最好使用下面的函数来防止冲突：

extern int del_timer_sync(struct timer_list * timer);修改timer，修改timer的到期时间：

int mod_timer(struct timer_list *timer, unsigned long expires);通常用法：

struct timer_list通常作为数据结构中的一个参数，在初始化结构的时候初始化timer，表示到期时要进行的操作，实现定时动作，通常更多的是作为超时 处理的，timer函数作为超时时的资源释放函数。注意：如果超时了运行超时函数，此时系统是处在时钟中断的bottom half里的，不能进行很复杂的操作，如果要完成一些复杂操作，如到期后的数据发送，不能直接在到期函数中处理，而是应该在到期函数中发个信号给特定内核 线程转到top half进行处理。为判断时间的先后，内核中定义了以下宏来判断：#define time_after(a,b) ((long)(b) - (long)(a)  0)

#define time_before(a,b) time_after(b,a)#define time_after_eq(a,b) ((long)(a) - (long)(b) >= 0)

#define time_before_eq(a,b) time_after_eq(b,a)这里用到了一个技巧，由于linux中的时间是无符号数，这里先将其转换为有符号数后再判断，就能解决时间回绕问题，当然只是一次回绕，回绕两次当然是判断不出来的，具体可自己实验体会。5. 内核线程(kernel_thread)内核中新线程的建立可以用kernel_thread函数实现，该函数在kernel/fork.c中定义：long kernel_thread(int (*fn)(void *), void * arg, unsigned long flags)fn：内核线程主函数;

arg：线程主函数的参数;

flags：建立线程的标志;内核线程函数通常都调用daemonize()进行后台化作为一个独立的线程运行，然后设置线程的一些参数，如名称，信号处理等，这也不是必须 的，然后就进入一个死循环，这是线程的主体部分，这个循环不能一直在运行，否则系统就死在这了，或者是某种事件驱动的，在事件到来前是睡眠的，事件到来后 唤醒进行操作，操作完后继续睡眠;或者是定时睡眠，