中华国学，用英文讲的，稀里糊涂听了个大概，不得不佩服西方人的缜密的逻辑思维，竟然把玄之又玄的道家思想说的跟牛顿定律一般，佩服。归家，又收到了邮件，还是关于nf-hipac的，不知不觉就想彻底整理一篇文章说个明白，可是哪有个够啊哪有个够。
匆匆吃完晚饭，碗也没刷，餐桌狼藉，家人都在看电视，玩手机，小小依然捧着iPad...我的摊子如下：
<a href="http://s3.51cto.com/wyfs02/M02/53/A2/wKioL1RsnlyjhmL3AAixJkRpu6A685.jpg" target="_blank"></a>
如果说理论分析不足以镇住人，或者说一上来就讲理论可能把人吓跑，还是先来点感官上的体验吧。
执行下面的命令：
系统中添加了将近20000条的iptables规则，iperf的测试结果如下：
<a href="http://s3.51cto.com/wyfs02/M00/53/A2/wKioL1Rsns-D4uvwAAGLWa1hPL0344.jpg" target="_blank"></a>
下面我来试一下nf-hipac，由于nf-hipac的命令语法和iptables基本兼容，因此按照下面的命令执行：
如此一来，系统中添加了将近2000条nf-hipac规则，iperf的测试结果如下：
<a href="http://s3.51cto.com/wyfs02/M01/53/A4/wKiom1RsnoLwRtzaAAGTsPcsNug716.jpg" target="_blank"></a>
二者的对比相当明显，最后我们来看一下既没有iptables又没有nf-hipac规则的时候，iperf的结果：
<a href="http://s3.51cto.com/wyfs02/M02/53/A2/wKioL1RsnxvzUjKIAAGBSxb_808366.jpg" target="_blank"></a>
显而易见，nf-hipac加载20000个条目的结果和裸奔的结果是几乎一致的，这是多么令人兴奋的一件事啊！
幸运的是，我已经决定将其做成一个可以加载的内核模块了，并且支持2.6.32以及以上的内核。今晚开始了移植工作，基本分为几块的工作量：
a.适配match/target内核API
b.适配netlink内核API
在 还没有完成模块化之前，只能在2.6.13上打patch了。能我相当信心的是，nf-hipac的内核补丁事实上是在net/ipv4 /netfilter目录下的一个子目录nf-hipac，所有的文件全部在里面，并未对任何内核关键的数据结构打补丁，因此nf-hipac完全可以作 为一个模块进行编译。
解压缩nf-hipac-0.9.1.tar.bz2，进入user目录，执行make install PREFIX=/usr/local IPT_LIB_DIR=/usr/local/lib/iptables，很容易就编译成功了。
进入新下载的2.6.13内核的根目录：
为内核打上patch：
配置.config文件，我使用了Debian GNU/Linux 3.1的config文件：
然后make menuconfig：
加入一个版本后缀
General setup ---> (hipac) Local version - append to kernel release
选中nf-HiPAC
Networking ---> Networking options --->
[*] Network packet filtering (replaces ipchains) --->
IP: Netfilter Configuration --->
<M> nf-HiPAC support (High Performance Packet Classification)
[*] Single path optimization
保存.config
直接编译：
修改/boot/grub/menu.lst，使用新的vmlinuz-2.6.13hipac启动系统
系统启动完成
除 了iptables换成nf-hipac之外没有任何别的区别，但是要注意，所有的iptables的match都被nf-hipac支持，但是并不意味 着iptables的match可以内置到nf-hipac的dimtree中实现高效匹配，只有nf-hipac内置的match才可以实现高效 dimtree匹配，这些match的共同特点就是它们的值域可以“区间化”。下面是一个nf-hipac支持的列表：
Options:
--proto -p [!] proto protocol: by number or name, eg. `tcp'
--source -s [!] address[/mask] or
address[:address]
source(s) specification
--destination -d [!] address[/mask] or
destination(s) specification
--in-interface -i [!] devname
network interface name
--jump -j target
target for rule
--numeric -n numeric output of addresses and ports
--out-interface -o [!] devname
--verbose -v verbose mode
--line-numbers print line numbers when listing
[!] --fragment -f match second or further fragments only
--version -V print package version.
----------
TCP options:
--syn match when only SYN flag set
--not-syn match when not only SYN flag set
--source-port [!] port[:port]
--sport ...
match source port(s)
--destination-port [!] port[:port]
--dport ...
match destination port(s)
UDP options:
ICMP options:
--icmp-type typename match icmp type
(or numeric type or type/code)
see also: nf-hipac -h icmp
STATE options:
--state [!] [INVALID|ESTABLISHED|NEW|RELATED|UNTRACKED|ESTABLISHED,RELATED]
State to match
TTL options:
--ttl value[:value] match time to live value(s)
如 果nf-hipac命令中出现了iptables的match，比如从/lib/iptables目录加载的libipt_set.so中的ipset match以及任何iptables的match模块，最终都要排在dimtree的叶子节点进行独立的iptables匹配过程。代码里面已经很清晰的 表明了这一点。nf-hipac的HOOK函数是hipac_match，该函数首先进行例行的高效的HiPAC算法匹配，然后找到一个叶子节点，该叶子 节点可能体现出两种行为：
a.它就是纯粹的nf-hipac的rule，此时叶子指示一个target：
b.它在nf-hipac规则中夹杂了iptables的match(这些match从/lib/iptables/目录下加载)，此时需要进行iptables的例行匹配，这种匹配不是按照HiPAC算法高效执行的，而是使用iptables的算法慢速遍历的：
nf-hipac模块加载了之后，会在procfs的net目录***册自己，其中的/proc/net/nf-hipac下的info文件中有下面一行：
nf-hipac is invoked before iptables
如果你想让iptables首先进行匹配，那么请执行：
其/proc/net/nf-hipac/statistics目录下有关于hipac规则树的一些统计信息，目前只有3个链被支持。
nf-hipac相比较iptables，性能那叫一个帅！相比ipset则不相上下，然而nf-hipac在综合效果上则是介于iptables和ipset之间的一个being。它是怎么做到的。
iptables的规则在内存中是线性排列的，内核的HOOK通过遍历这些规则链进行逐一匹配，这个逐一匹配的顺序内含了优先级的概念，首先加入的 rule首先被匹配到。但是除了这个顺序的排列之外，规则之间再也没有了别的关联，因此很难将它们作为一个整体来进行优化。
ipset将ip地址，端口等统一进行管理，但是同一个集合中的元素只能采取统一的动作，即target，虽然在ip地址的匹配中极端高效，但是使用起来 很不灵活，很难做到比如同在set中的ip1和ip2执行不同的-j target动作。ipset是将单一的match统一管理进行优化的，和多条iptables规则没有必然的关系，即它没有将多条iptables规则 关联起来。
除了傻傻的线性排列，除了单一match的hash/tree统一管理，iptables和match，target之间还能有别的关系吗？即它们之间还 能有别的排列方式吗？当然有，这就是nf-hipac的方式。nf-hipac采用了另一种排列方式，即将固定的match进行排序，也就是说将每一条规 则拆开来，这就就可以化不确定为确定。确定的是match的总的种类，不确定的是规则的数量，最终确定的match的数量决定了树的高度，而这个不确定的 规则数量影响的仅仅是树的广度，仅此而已。
下面的一幅图非常复杂，是我听完嘉定中华国学后在我的餐桌上画的，已经很晚了，无所事事，睡不着，也没喝酒，所以就兴奋了。图示如下：
<a href="http://s3.51cto.com/wyfs02/M02/53/A4/wKiom1RsnfvSy4UlAA5CEMq2ELI635.jpg" target="_blank"></a>
拆 散了一条条的rule之后，剩下的就是将match和target组成一棵树了，事实上rule并没有被拆散，所谓的rule就是若干的match和一个 target，在右边这棵树中体现的就是每一个树节点的match层次，最下层的优先级最高，这就体现了rule的配置顺序，rule的配置顺序体现的就 是优先级。
nf-hipac不更新了，没人维护了，难道是作者因此找到好的工作了，难道是作者结婚了，难道是作者生孩子了...这种判断也太中国化了，反正就是不更 新了...单单谈效率，ipset完全可以让nf-hipac下课，但是谈点别的之后，nf-hipac的优势就显现出来了。
有破有立，方可不败。
如果我们结合上面的图仔细分析为何添加了20000条左右的nf-hipac，性能依然不受任何影响，就会发现，nf-hipac的匹配过程最多经过n层 的树深度，而n是match的数量，在这20000条规则中，match的数量只有1个！！注意了，这就是关键，1个！如果使用iptables，那么匹 配的过程最多经过m个rule。也就是说，nf-hipac将m个rule拆散了之后，将其中所有的match压缩成了n层的树，每一层拥有m个层的区间 交集匹配，这些交集仅仅决定其下层树节点的rule交集。照此说来，很多的数据包从第一个match集合(所有rule的第一个match组成的集合)树 根开始匹配，一旦rule的match交集变成空，就可以直接下决断“没有匹配的rule”了，所以即便是少数种类的match集合节点，一个数据包也不 一定能从树根匹配到最后一个match集合。这就是nf-hipac超猛的根本原因。
对于nf-hipac树的查找，需要注意的是，如果不是叶子节点，执行流只会碰触到最先配置的那条rule，即最下面的那条，其余的rule被隐藏在该最 下面rule的上面，它们的作用仅仅是告诉执行流，该区间的下面的分支树节点是所有这些rule的交集，仅此而已。
从iptables到nf-hipac的变化是：从遍历m*n次(m为rule的数量，n为每一个rule的match的数量)简化为了遍历n次(n为所 有rule中最多match的那一条rule的match的数量)。之所以如此就是因为nf-hipac将所有的rule作为一个整体来优化。那么代价是 什么？代价就是插入rule，删除rule的开销。插入一条rule，首先需要将其所有的match拆分开来，然后找出每一个树节点的位置，即rule的 插入位置，然后准备将这些match分别插入到那些位置中，是否插入取决于那个位置有没有对应rule的match交集，如果没有，则不予插入，删除的过 程类似，也需要进行比较复杂的计算。
那么有没有什么办法让nf-hipac变得低效呢？很显然，当你了解了nf-hipac的dimtree的构造之后，你就会明白，n的数量越大，效率越 低，n是什么？n是match的种类的数量。整个tree的深度就是n，如果自己构造20000种左右的match，那么试试看，仅仅配置一条nf- hipac规则，整个tree的构造将变成深度为2000的倒立的链表...我之所以仅仅设置一条nf-hipac规则是因为如果设置了多条，反而可能由 于中途rule的match交集为空而提前退出遍历树。但是幸运的是，对于一个数据包那么多种的match是不必要的。
本文转自 dog250 51CTO博客，原文链接:http://blog.51cto.com/dog250/1579804
![查找算法之二分查找查找算法之二分查找[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)