linux核心netfilter連接配接跟蹤的hash算法

linux核心netfilter連接配接跟蹤的hash算法

linux核心中的netfilter是一款強大的基于狀态的防火牆，具有連接配接跟蹤（conntrack）的實作。conntrack是netfilter的核心，許多增強的功能，例如，位址轉換（NAT），基于内容的業務識别（l7， layer-7 module）都是基于連接配接跟蹤。然而，netfilter的性能還有很多值得改進的地方。

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;

       } udp;

              u_int16_t id;

       } icmp;

       } 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. */

              union {

                     u_int32_t all[NF_CT_TUPLE_L3SIZE];

                     u_int32_t ip;

                     u_int32_t ip6[4];

              } u3;

                     /* Add other protocols here. */

                     u_int16_t all;

                     struct {

                            u_int16_t port;

                     } tcp;

                     } udp;

                            u_int8_t type, code;

                     } icmp;

                     } 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位數字。

上面的兩個宏這是lookup3.c的核心hash算法，hash的基礎。

hashword是通用的hash算法，用于計算任意cpu架構，任意長度的字元串的hash值。

不斷的把輸入的串k，每隔3位進行mix，直到完畢。傳回final。

對于ipv4的話，可以直接把源位址，目的位址，(源端口<< 16)|目的端口，這三個整數進行final，得到hash值。

對于ip位址和端口号的特點，這種複雜的算法是否真的有更好的hash效果，我持懷疑态度。