文章来源：
曾经的代码，今年还在用(conntrack-tools-1.0.0):
C语言:
#ifndef _LINUX_JHASH_H
#define _LINUX_JHASH_H
#define u32 unsigned int
#define u8 char
/* jhash.h: Jenkins hash support.
*
* Copyright (C) 1996 Bob Jenkins (bob_jenkins@burtleburtle.net)
*
*
*
* These are the credits from Bob's sources:
*
* lookup2.c, by Bob Jenkins, December 1996, Public Domain.
* hash(), hash2(), hash3, and mix() are externally useful functions.
* Routines to test the hash are included if SELF_TEST is defined.
* You can use this free for any purpose. It has no warranty.
*
* Copyright (C) 2003 David S. Miller (davem@redhat.com)
*
* I've modified Bob's hash to be useful in the Linux kernel, and
* any bugs present are surely my fault. -DaveM
*/
/* NOTE: Arguments are modified. */
#define __jhash_mix(a, b, c) \
{ \
a -= b; a -= c; a ^= (c>>13); \
b -= c; b -= a; b ^= (a<<8); \
c -= a; c -= b; c ^= (b>>13); \
a -= b; a -= c; a ^= (c>>12); \
b -= c; b -= a; b ^= (a<<16); \
c -= a; c -= b; c ^= (b>>5); \
a -= b; a -= c; a ^= (c>>3); \
b -= c; b -= a; b ^= (a<<10); \
c -= a; c -= b; c ^= (b>>15); \
}
/* The golden ration: an arbitrary value */
#define JHASH_GOLDEN_RATIO 0x9e3779b9
/* The most generic version, hashes an arbitrary sequence
* of bytes. No alignment or length assumptions are made about
* the input key.
*/
static inline u32 jhash(const void *key, u32 length, u32 initval)
{
u32 a, b, c, len;
const u8 *k = key;
len = length;
a = b = JHASH_GOLDEN_RATIO;
c = initval;
while (len >= 12) {
a += (k[0] +((u32)k[1]<<8) +((u32)k[2]<<16) +((u32)k[3]<<24));
b += (k[4] +((u32)k[5]<<8) +((u32)k[6]<<16) +((u32)k[7]<<24));
c += (k[8] +((u32)k[9]<<8) +((u32)k[10]<<16)+((u32)k[11]<<24));
__jhash_mix(a,b,c);
k += 12;
len -= 12;
}
c += length;
switch (len) {
case 11: c += ((u32)k[10]<<24);
case 10: c += ((u32)k[9]<<16);
case 9 : c += ((u32)k[8]<<8);
case 8 : b += ((u32)k[7]<<24);
case 7 : b += ((u32)k[6]<<16);
case 6 : b += ((u32)k[5]<<8);
case 5 : b += k[4];
case 4 : a += ((u32)k[3]<<24);
case 3 : a += ((u32)k[2]<<16);
case 2 : a += ((u32)k[1]<<8);
case 1 : a += k[0];
};
__jhash_mix(a,b,c);
return c;
}
/* A special optimized version that handles 1 or more of u32s.
* The length parameter here is the number of u32s in the key.
*/
static inline u32 jhash2(const u32 *k, u32 length, u32 initval)
{
u32 a, b, c, len;
a = b = JHASH_GOLDEN_RATIO;
c = initval;
len = length;
while (len >= 3) {
a += k[0];
b += k[1];
c += k[2];
__jhash_mix(a, b, c);
k += 3; len -= 3;
}
c += length * 4;
switch (len) {
case 2 : b += k[1];
case 1 : a += k[0];
};
__jhash_mix(a,b,c);
return c;
}
/* A special ultra-optimized versions that knows they are hashing exactly
* 3, 2 or 1 word(s).
*
* NOTE: In partilar the "c += length; __jhash_mix(a,b,c);" normally
* done at the end is not done here.
*/
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;
}
static inline u32 jhash_2words(u32 a, u32 b, u32 initval)
{
return jhash_3words(a, b, 0, initval);
}
static inline u32 jhash_1word(u32 a, u32 initval)
{
return jhash_3words(a, 0, 0, initval);
}
#endif /* _LINUX_JHASH_H */
linux内核中的netfilter是一款强大的基于状态的防火墙，具有连接跟踪（conntrack）的实现。conntrack是netfilter的核心，许多增强的功能，例如，地址转换（NAT），基于内容的业务识别（l7， layer-7 module）都是基于连接跟踪。然而，netfilter的性能还有很多值得改进的地方。
netfilter的连接跟踪的hash算法是在Bob Jenkins的lookup2.c基础上的改进实现，Bob Jenkins已经推出lookup3.c的实现，见地址：和
netfilter中的hash求值的代码如下：
static u_int32_t __hash_conntrack(const struct nf_conntrack_tuple *tuple,
unsigned int size, unsigned int rnd)
{
unsigned int a, b;
a = jhash((void *)tuple->src.u3.all, sizeof(tuple->src.u3.all),
((tuple->src.l3num) << 16) | tuple->dst.protonum);
b = jhash((void *)tuple->dst.u3.all, sizeof(tuple->dst.u3.all),
(tuple->src.u.all << 16) | tuple->dst.u.all);
return jhash_2words(a, b, rnd) % size;
}
static inline u_int32_t hash_conntrack(const struct nf_conntrack_tuple *tuple)
{
return __hash_conntrack(tuple, nf_conntrack_htable_size,
nf_conntrack_hash_rnd);
}
这是一个对于ipv6和ipv4的hash求值的通用实现。struct nf_conntrack_tuple是一个通用的连接的四元组，同时用于ipv4和ipv6，tcp，udp，sctp，icmp协议，所以，其定义比较复杂。可以把它理解为源地址，源端口，目的地址，目的端口。
#define NF_CT_TUPLE_L3SIZE 4
union nf_conntrack_man_l3proto {
u_int32_t all[NF_CT_TUPLE_L3SIZE];
u_int32_t ip;
u_int32_t ip6[4];
};
其实这就是ip地址。
union nf_conntrack_man_proto
{
/* Add other protocols here. */
u_int16_t all;
struct {
u_int16_t port;
} tcp;
struct {
u_int16_t port;
} udp;
struct {
u_int16_t id;
} icmp;
struct {
u_int16_t port;
} sctp;
};
这就是端口。
struct nf_conntrack_man
{
union nf_conntrack_man_l3proto u3;
union nf_conntrack_man_proto u;
/* Layer 3 protocol */
u_int16_t l3num;
};
目的地址和端口，l3num不知道是什么东西？
struct nf_conntrack_tuple
{
struct nf_conntrack_man src;
/* These are the parts of the tuple which are fixed. */
struct {
union {
u_int32_t all[NF_CT_TUPLE_L3SIZE];
u_int32_t ip;
u_int32_t ip6[4];
} u3;
union {
/* Add other protocols here. */
u_int16_t all;
struct {
u_int16_t port;
} tcp;
struct {
u_int16_t port;
} udp;
struct {
u_int8_t type, code;
} icmp;
struct {
u_int16_t port;
} sctp;
} u;
/* The protocol. */
u_int8_t protonum;
/* The direction (for tuplehash) */
u_int8_t dir;
} dst;
};
有些混乱，就是源地址和目的地址，protonum和dir不知道为什么这么定义？
上面的hash算法在仅用于ipv4时，可以进行优化。jhash函数是通用的hash函数，上面的目的是把ipv6的长串字符hash为一个32位整数，而ipv4的情况下，可以不用。
最后，使用％运算，这是非常低效的，Bob Jenkins专门指出了这一点。由于table的大小都为2的次方，所以，可以使用&的算法。
另外，我认为Bob Jenkins的算法是对于通用的数字的hash算法，对于tcp连接这样比较特殊的数字的hash，使用这么复杂的算法，是否有意义？简单的加法运算是否更有效率？
lookup3.c与lookup2.c有很大的不同。lookup3.c中，使用了final宏，和mix宏分开。而lookup2.c中没有使用final宏。
linux下的修改过的hash函数：
static inline u32 jhash(const void *key, u32 length, u32 initval)
通用的hash函数，对任意长度的key字符串进行hash运算，得到一个32位数字。
static inline u32 jhash2(u32 *k, u32 length, u32 initval)
优化的版本，对任意长度的32位整数进行hash运算，得到一个32位数字。
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;
}
优化的版本，对3个32位整数进行hash运算，得到一个32位数字。
static inline u32 jhash_2words(u32 a, u32 b, u32 initval)
{
return jhash_3words(a, b, 0, initval);
}
对2个32位整数进行hash运算，得到一个32位数字。
static inline u32 jhash_1word(u32 a, u32 initval)
{
return jhash_3words(a, 0, 0, initval);
}
对1个32位整数进行hash运算，得到一个32位数字。
- #define mix(a,b,c) \
-
{ \
-
a -= c; a ^= rot(c, 4); c += b; \
-
b -= a; b ^= rot(a, 6); a += c; \
-
c -= b; c ^= rot(b, 8); b += a; \
-
a -= c; a ^= rot(c,16); c += b; \
-
b -= a; b ^= rot(a,19); a += c; \
-
c -= b; c ^= rot(b, 4); b += a; \
-
}
-
-
#define final(a,b,c) \
-
{ \
-
c ^= b; c -= rot(b,14); \
-
a ^= c; a -= rot(c,11); \
-
b ^= a; b -= rot(a,25); \
-
c ^= b; c -= rot(b,16); \
-
a ^= c; a -= rot(c,4); \
-
b ^= a; b -= rot(a,14); \
-
c ^= b; c -= rot(b,24); \
-
}
上面的两个宏这是lookup3.c的核心hash算法，hash的基础。
- uint32_t hashword(
-
const uint32_t * k, /* the key, an array of uint32_t values */
-
size_t length, /* the length of the key, in uint32_ts */
-
uint32_t initval) /* the previous hash, or an arbitrary value */
-
{
-
uint32_t a , b, c;
-
/* Set up the internal state */
-
a = b = c = 0xdeadbeef + (((uint32_t) length) << 2) + initval;
-
-
/*----------------------------------- handle most of the key */
-
while (length > 3)
-
{
-
a += k[0];
-
b += k[1];
-
c += k[2];
-
mix(a, b, c);
-
length -= 3;
-
k += 3;
-
}
-
-
/*------------------------ handle the last 3 uint32_t's */
-
switch (length) /* all the case statements fall through */
-
{
-
case 3:
-
c += k[2];
-
case 2:
-
b += k[1];
-
case 1:
-
a += k[0];
-
final(a, b, c);
-
case 0: /* case 0: nothing left to add */
-
break;
-
}
-
/*------------------------------------- report the result */
-
return c;
-
}
hashword是通用的hash算法，用于计算任意cpu架构，任意长度的字符串的hash值。
不断的把输入的串k，每隔3位进行mix，直到完毕。返回final。
对于ipv4的话，可以直接把源地址，目的地址，(源端口<< 16)|目的端口，这三个整数进行final，得到hash值。
对于ip地址和端口号的特点，这种复杂的算法是否真的有更好的hash效果，我持怀疑态度。
