本文共 6189 字，大约阅读时间需要 20 分钟。
http://blog.csdn.net/jccz_zys/article/details/1509832
以下基于linux内核2.4.0源码(转载请注明出处)
松哥
网络通信过程中，服务器必然提供监听socket响应客户端连接请求，也必然提供连接socket与客户端进行交互。一台主机上有不止一个的socket服务器，如ftp、telnet服务器等，他们初始都处于监听状态，等待连接请求的到来。linux中为了管理这两类socket提供了两个哈希链表：tcp_listening_hash和tcp_ehash，下面主要分析下监听哈希表，顺带说下连接hash表。
一、链表定义
在include/net/tcp.h中定义了tcp_hashinfo结构,包含了tcp协议所涉及到的一些哈希表信息,这两个哈希表以tcp_hashinfo的成员形式出现,如下所示：
extern struct tcp_hashinfo {
/* 结构成员用于tcp状态迁移图中的相关状态:
* TCP_ESTABLISHED <= sk->state < TCP_CLOSE
* 前半部份用于非超时状态,后半部份仅用于超时状态
*/
struct tcp_ehash_bucket *__tcp_ehash;
/* tcp的绑定哈希表,用于快速bind/connect*/
struct tcp_bind_hashbucket *__tcp_bhash;
int __tcp_bhash_size;
int __tcp_ehash_size;
/* 所有在监听状态的socket都存放在下面的哈希表中，其中键key为本地监听端口*/
struct sock *__tcp_listening_hash[TCP_LHTABLE_SIZE];
/*下面的成员缓冲区对齐*/
rwlock_t __tcp_lhash_lock /*监听哈希表访问锁*/
__attribute__((__aligned__(SMP_CACHE_BYTES)));
atomic_t __tcp_lhash_users;
wait_queue_head_t __tcp_lhash_wait;
/*上述三个成员主要用于用户通过/proc/ne获取监听套接字(间接访问监听哈希表时)信息时异步处理*/
spinlock_t __tcp_portalloc_lock;
} tcp_hashinfo;
接下来定义了一些宏以简化引用：
#define tcp_ehash (tcp_hashinfo.__tcp_ehash) /*连接哈希链表*/
#define tcp_bhash (tcp_hashinfo.__tcp_bhash) /*地址bind哈希链表*/
#define tcp_ehash_size (tcp_hashinfo.__tcp_ehash_size) /*连接哈希链表长度*/
#define tcp_bhash_size (tcp_hashinfo.__tcp_bhash_size) /*bind哈希链表长度*/
#define tcp_listening_hash (tcp_hashinfo.__tcp_listening_hash) /*监听哈希链表*/
#define tcp_lhash_lock (tcp_hashinfo.__tcp_lhash_lock) /*监听哈希链表访问锁*/
#define tcp_lhash_users (tcp_hashinfo.__tcp_lhash_users) /*引用计数*/
#define tcp_lhash_wait (tcp_hashinfo.__tcp_lhash_wait) /*异步访问时的等待队列*/
#define tcp_portalloc_lock (tcp_hashinfo.__tcp_portalloc_lock) /*SMP用途??*/
二、链表的初始化
tcp_listening_hash和tcp_ehash的初始化在net/ipv4/tcp_ipv4.c中,其中定义了全局变量tcp_hashinfo
并赋初值，如下：
/*
* 所有的成员都要初始化,以防止gcc-2.7.2.3编译错误
*/
struct tcp_hashinfo __cacheline_aligned tcp_hashinfo = {
__tcp_ehash: NULL,
__tcp_bhash: NULL,
__tcp_bhash_size: 0, /*初始大小为0*/
__tcp_ehash_size: 0,
__tcp_listening_hash: { NULL, },
__tcp_lhash_lock: RW_LOCK_UNLOCKED, /*读写锁*/
__tcp_lhash_users: ATOMIC_INIT(0),
__tcp_lhash_wait:
__WAIT_QUEUE_HEAD_INITIALIZER(tcp_hashinfo.__tcp_lhash_wait), //初始化等待队列
__tcp_portalloc_lock: SPIN_LOCK_UNLOCKED
};
三、链表的元素增加
服务器监听的函数调用过程如下：
sys_listen-->inet_listen-->tcp_listen_start-->tcp_v4_hash-->__tcp_v4_hash
其中，在tcp_listen_start中，将监听socket的accept_queue队列以及内核sock结构的
tcp_opt成员tp_pinfo.af_tcp所指向的listen_opt初始化。
listen_opt为struct tcp_listen_opt类型，定义在include/net/tcp.h中：
struct tcp_listen_opt
{
u8 max_qlen_log; /* SYN包队列的最大长度 */
int qlen; /*当前实际长度*/
int qlen_young;
int clock_hand; /**/
/*syn_table用于tcp三次握手协议时保留SYN包请求,与SYN Cookie配合可用于防止SYN flood攻击*/
struct open_request *syn_table[TCP_SYNQ_HSIZE];
};
下面来看看__tcp_v4_hash函数,在net/ipv4/tcp_ipv4.c中
static __inline__ void __tcp_v4_hash(struct sock *sk)
{
struct sock **skp;/*指向哈希表表项地址，其中每个哈希表项为链表.即指向链首指针的地址*/
rwlock_t *lock;
BUG_TRAP(sk->pprev==NULL);
if(sk->state == TCP_LISTEN) {/*注意在tcp_listen_start函数中已经将sock状态置为TCP_LISTEN了*/
skp = &tcp_listening_hash[tcp_sk_listen_hashfn(sk)];/*注意:tcp_sk_listen_hashfn封装了tcp_lhashfn*/
lock = &tcp_lhash_lock;
tcp_listen_wlock();
} else {/*否则加入到连接哈希表，如果代码执行到这里,一般此时sock为TCP_ESTABLISHED*/
skp = &tcp_ehash[(sk->hashent = tcp_sk_hashfn(sk))].chain;
lock = &tcp_ehash[sk->hashent].lock;
write_lock(lock);
}
/*sk->next:每个socket的next都指向后一个有相同hash值(冲突)的sock结构
*每个socket的pprev都指向前一个有相同hash值的sock结构*/
if((sk->next = *skp) != NULL) /*注意此时skp是获得的链表头的地址，所以此处是"*skp"来引用*/
(*skp)->pprev = &sk->next; /*双向链表,pprev指向前一个sock结构(即刚加入的sock结构的next地址)*/
*skp = sk;/*将sk加入到链首*/
sk->pprev = skp;
sock_prot_inc_use(sk->prot);/*修改prot->stats[].inuse计数*/
write_unlock(lock);
if (sk->state == TCP_LISTEN)
wake_up(&tcp_lhash_wait); /*唤醒等待队列*/
}
四、哈希链表元素的删除
监听链表的元素的释放是在监听套接子关闭时处理。函数调用链如下：
close-->(参考《情景阅读》)...-->inet_release-->tcp_close-->tcp_set_state-->tcp_unhash
tcp_unhash代码在net/ipv4/tcp_ipv4.c中,如下：
void tcp_unhash(struct sock *sk)
{
rwlock_t *lock;
if (sk->state == TCP_LISTEN) { /*监听套接字*/
local_bh_disable(); //
tcp_listen_wlock(); /*循环调度直至外部改变tcp_lhash_users为0是才往下执行*/
lock = &tcp_lhash_lock;
} else { /*其他状况时脱离tcp连接哈希桶*/
struct tcp_ehash_bucket *head = &tcp_ehash[sk->hashent];
lock = &head->lock;
write_lock_bh(&head->lock);//加锁处理
}
if(sk->pprev) {
if(sk->next)
sk->next->pprev = sk->pprev; /*将sk脱链*/
*sk->pprev = sk->next;/*sk->pprev指向前一节点的next地址，所以此处是将前一节点的next指针指向sk节点的后一节点*/
sk->pprev = NULL;
sock_prot_dec_use(sk->prot);
}
...
}
五、哈希函数
代码在include/net/Tcp.h,如下：
static __inline__ int tcp_lhashfn(unsigned short num)
{
return num & (TCP_LHTABLE_SIZE - 1);
}
可见此哈希函数仅根据请求的端口来做哈希，监听哈希表的长度是TCP_LHTABLE_SIZE,为32,定义如下：
#define TCP_LHTABLE_SIZE 32 /* Yes, really, this is all you need. */
注意:tcp_sk_listen_hashfn封装了tcp_lhashfn
六、哈希表的作用
内核中，每建立一个监听套接字，就将套接字挂入监听哈希表的某个表项链表中。则在内核收到连接请求的SYN或ACK等包传到TCP层时，要根据请求包的请求连接地址与端口号到哈希表中查找对应的服务器监听套接字是否存在，代码在net/ipv4/tcp_ipv4.c中,如下：
int tcp_v4_rcv(struct sk_buff *skb, unsigned short len)
{
...
/*__tcp_v4_lookup函数就是在监听哈希表和连接哈希桶中查找请求的服务器套接字*/
sk = __tcp_v4_lookup(skb->nh.iph->saddr, th->source,
skb->nh.iph->daddr, ntohs(th->dest), tcp_v4_iif(skb));
...
}
__tcp_v4_lookup函数在同一文件下，代码如下：
static inline struct sock *__tcp_v4_lookup(u32 saddr, u16 sport,
u32 daddr, u16 hnum, int dif)
{
struct sock *sk;
/*先在连接哈希桶中找*/
sk = __tcp_v4_lookup_established(saddr, sport, daddr, hnum, dif);
if (sk) /*找到则返回*/
return sk;
/*否则在监听哈希表中找*/
return tcp_v4_lookup_listener(daddr, hnum, dif);
}
我们来看tcp_v4_lookup_listener函数,其中入参有目标地址、目标端口
__inline__ struct sock *tcp_v4_lookup_listener(u32 daddr, unsigned short hnum, int dif)
{
struct sock *sk;
read_lock(&tcp_lhash_lock);
sk = tcp_listening_hash[tcp_lhashfn(hnum)];/*根据目标端口找到哈希表项,为链表首节点指针*/
if (sk) { /*如果链首不空*/
if (sk->num == hnum && /*如果端口相等*/
sk->next == NULL && /*如果仅此节点*/
(!sk->rcv_saddr || sk->rcv_saddr == daddr) && /*套接字绑定了IPv4地址,且此地址为请求的连接地址*/
!sk->bound_dev_if) /*如果存在绑定的设备接口*/
goto sherry_cache; //则直接返回
sk = __tcp_v4_lookup_listener(sk, daddr, hnum, dif); /*否则遍历链表,按照地址、端口、设备接口索引查找*/
}
if (sk) {/*找到则直接返回,否则sk=NULL*/
sherry_cache:
sock_hold(sk);
}
read_unlock(&tcp_lhash_lock); //解锁
return sk;
}
关于连接的哈希桶的功能也大致如此，主要用于保存建立连接的套接字,用于在接受到网络包后，找到对应
的处理套接字。
七、结束语
内核中的很多地方都采用了这种简单的哈希表,其中冲突的解决方法就是表项采用链表方式。在tcp的实现中,还引入了其它哈希表,如bind哈希表tcp_bhash等等。通过这些哈希表,内核可以简洁、方便、快速地查询这些哈希表中的目标套接字是否存在。