请教Netfilter hash算法

独孤九贱

Netfilter的连接跟踪表，是通过一个hash表来维护的，其首先把一个数据包根据来源/端口/协议转换成一个"tuple"，然后根据这个"tuple"来计算hash值：

1. static u_int32_t
   
2. hash_conntrack(const struct ip_conntrack_tuple *tuple)
   
3. {
   
4. #if 0
   
5.         dump_tuple(tuple);
   
6. #endif
   
7.         return (jhash_3words(tuple->src.ip,
   
8.                              (tuple->dst.ip ^ tuple->dst.protonum),
   
9.                              (tuple->src.u.all | (tuple->dst.u.all << 16)),
   
10.                              ip_conntrack_hash_rnd) % ip_conntrack_htable_size);
    
11. }

复制代码

其中ip_conntrack_hash_rnd是一个通过get_random_bytes函数产生的四字节的随机数，ip_conntrack_htable_size是hash表的大小。

1. static inline u32 jhash_3words(u32 a, u32 b, u32 c, u32 initval)
   
2. {
   
3.         a += JHASH_GOLDEN_RATIO;
   
4.         b += JHASH_GOLDEN_RATIO;
   
5.         c += initval;
   
6. 
   
7.         __jhash_mix(a, b, c);
   
8. 
   
9.         return c;
   
10. }

复制代码

__jhash_mix宏定义如下：

1. /* NOTE: Arguments are modified. */
   
2. #define __jhash_mix(a, b, c) \
   
3. { \
   
4.   a -= b; a -= c; a ^= (c>>13); \
   
5.   b -= c; b -= a; b ^= (a<<8); \
   
6.   c -= a; c -= b; c ^= (b>>13); \
   
7.   a -= b; a -= c; a ^= (c>>12);  \
   
8.   b -= c; b -= a; b ^= (a<<16); \
   
9.   c -= a; c -= b; c ^= (b>>5); \
   
10.   a -= b; a -= c; a ^= (c>>3);  \
    
11.   b -= c; b -= a; b ^= (a<<10); \
    
12.   c -= a; c -= b; c ^= (b>>15); \
    
13. }

复制代码

宏JHASH_GOLDEN_RATIO 定义如下：

1. /* The golden ration: an arbitrary value */
   
2. #define JHASH_GOLDEN_RATIO        0x9e3779b9

复制代码

这个hash算法看了个半懂，请哪位大哥分析一下这个算法，说说这样设计的好处，呵呵！！

liubinbj

这个算法基于Bob Jenkins早期的一篇论文，代码原封不动照搬。
为什么这么写，是有数学道理的，不是两句讲的清。
去年作者又发现了一个据他说更快的算法，是这样的：

1. 
   
2. #define rot(x,k) (((x)<<(k)) ^ ((x)>>(32-(k))))
   
3. 
   
4. #define hash_mix(a,b,c) \
   
5. { \
   
6.   c ^= b; c -= rot(b,14); \
   
7.   a ^= c; a -= rot(c,11); \
   
8.   b ^= a; b -= rot(a,25); \
   
9.   c ^= b; c -= rot(b,16); \
   
10.   a ^= c; a -= rot(c,4);  \
    
11.   b ^= a; b -= rot(a,14); \
    
12.   c ^= b; c -= rot(b,24); \
    
13. }
    

复制代码

也许过一段时间核心就会改成这个代码了。