linux内核netfilter连接跟踪的hash算法

linux内核netfilter连接跟踪的hash算法

 

linux内核中的netfilter是一款强大的基于状态的防火墙,具有连接跟踪(conntrack)的实现。conntrack是netfilter的核心,许多增强的功能,例如,地址转换(NAT),基于内容的业务识别(l7, layer-7 module)都是基于连接跟踪。然而,netfilter的性能还有很多值得改进的地方。

netfilter的连接跟踪的hash算法是在Bob Jenkins的lookup2.c基础上的改进实现,Bob Jenkins已经推出lookup3.c的实现,见地址:http://burtleburtle.net/bob/hash/http://burtleburtle.net/bob/c/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效果,我持怀疑态度。

时间: 2024-10-23 17:36:07

linux内核netfilter连接跟踪的hash算法的相关文章

conntrack-tools 1.2.0发布 Linux用户空间连接跟踪工具

conntrack-tools 是一套Linux用户空间连接跟踪工具,用于http://www.aliyun.com/zixun/aggregation/13879.html">系统管理员进行交互连接跟踪系统,该模块提供了iptables的状态数据包检查.它包括了用户空间的守护进程conntrackd和命令行界面conntrack. conntrack-tools 1.2.0该版本支持NAT期望,期望类的同步,助手的名字.现在允许标记筛选.已加入Q.931和H.245的配置示例. 软件信息

linux内核中的C语言常规算法(前提:你的编译器要支持typeof和type)

学过C语言的伙伴都知道,曾经比较两个数,输出最大或最小的一个,或者是比较三个数,输出最大或者最小的那个,又或是两个数交换,又或是绝对值等等,其实这些算法在linux内核中通通都有实现,以下的代码是我从linux内核源码的kernel.c中抠出来的代码,我们来看看: 我们直接上代码: #include <stdio.h> #include <stdlib.h> /* * min()/max() macros that also do * strict type-checking..

Linux内核中的有关Page的算法

static inline int get_order(unsigned long size) { int order; size = (size-1) >> (PAGE_SHIFT-1); order = -1; do { size >>= 1; order++; } while (size); return order; } 上面这个算法是从内核源代码摘抄下来的,其中PAGE_SHIFT是一个宏,定义的大小为12,这段代码的含义是 返回关联在当前平台的大小的分配级别, 根据 P

戴文的Linux内核专题:27 配置内核 (23)

戴文的Linux内核专题:27 配置内核 (23) 欢迎来到内核配置的下一章!本篇中我们会配置密码API,虚拟化和运行库.密码学指的是在需要的计算机之间加密和安全通信的科学.用户可能加密数据以保证是收件人而不是黑客收到数据. Linux内核需要在内核中启用"Cryptographic algorithm manager"(密码算法管理器).这个特性提供了操作内核的加密特性所需的软件. 当启用这个它,用户空间提供了配置加密特性(Userspace cryptographic algori

libnetfilter_cttimeout 1.0.0发布 连接跟踪超时接口

libnetfilter_cttimeout 是一个Netfilter连接跟踪超时的接口.它提供了一个用户空间库,包括一个编程接口到细粒度的连接跟踪超时基础设施.通过该库可以创建.更新和删除超时,且连接到流量. libnetfilter_cttimeout主要功能: • 创建超时对象• 检索超时对象• 删除超时对象 libnetfilter_cttimeout 1.0.0这是首次发布的版本. 软件信息:http://netfilter.org/projects/libnetfilter_ctti

基本数据结构和算法在Linux内核中使用

基本数据结构和算法在Linux内核中使用 gaufunga day ago 搬运工 Linux内核(源代码的链接在github). 1.链表.双向链表.无锁链表. 2.B+ 树,这是一些你无法在教科书上找到的说明. 一个相对简单的B+树的实现.我把它作为一个学习练习来帮助理解B+树是如何工作的.这同样也被证明是有用的. ... 一个在教科书中并不常见的技巧.最小的值在右侧而不是在左侧.所有在一个节点里用到的槽都在左侧,所有没有用到的槽包含了空值(NUL).大多数操作只简单地遍历所有的槽一次并在第

C语言之linux内核实现最大公约数算法

最大公约数算法,又称欧几里德算法,至今已有几千年的历史了.在我们开始学习C语言的时候最常用的算法就是辗转相除法,其实在linux内核中,内核也是使用这样的方法实现两数最大公约数的计算.      两个整数的最大公约数是能够同时整除它们的最大的正整数.辗转相除法基于如下原理:两个整数的最大公约数等于其中较小的数和两数的相除余数的最大公约数.       例如,252和105的最大公约数是21(252 = 21 × 12:105 = 21 × 5);       算法原理: 设两数为a.b(b<a)

linux内核-关于Linux内核中通过hash表将pid转化为task_struct地址的计算

问题描述 关于Linux内核中通过hash表将pid转化为task_struct地址的计算 内核中通过hash表把pid快速转化为task_struct的地址,Linux内核中有4张hash表,在初始化期间会为4张hash表动态分配地址.但转化的计算问题中,<深入理解Linux内核>中提出,对于一个有512MB RAM系统,每张表就存储在4个页框中,每张表可以有2048个表项,不知道这个是如何计算而来的.

深度剖析linux内核万能--双向链表,Hash链表模版

我们都知道,链表是数据结构中用得最广泛的一种数据结构,对于数据结构,有顺序存储,数组就是一种.有链式存储,链表算一种.当然还有索引式的,散列式的,各种风格的说法,叫法层出不穷,但是万变不离其中,只要知道什么场合用什么样的数据结构,那就行了. 那么,标题说的内核万能链表,其实就是内核链表,它到底和我们平常大学学的数据结构的链表有什么不同呢??内核链表,是在linux内核里的一种普遍存在的数据结构,比如内核调度算法中有这样的结构,摄像头驱动程序,wifi模块,G_sensor等等,用到链表的东西实在