思想
标准IP路由查找的过程为我们提供了一个极好的“匹配-动作”的例程。即匹配到一个路由项，然后将数据包发给该路由项指示的下一跳。如果我们把上面对IP路由查找的过程向上抽象一个层次，就会发现，其实它还可以有别的用。抽象后的表述为：以数据包的源地址或者目标地址为键值去查询一张表，查到结果项以后执行结果项指示的一个动作。一个结果项为：
struct result_node {
uint32 network;
uint32 netmask;
void *action;
};
以上这个思想多亏了路由查找中的“最长前缀匹配”原则，该原则是隐式的，但是该原则保证了最精确的匹配。
需求
在我的特殊场景中，我希望一个网络段(一个大的网络，一个小一点的网络，一台主机)发出的数据流和一个字符串描述关联起来，该字符串可以是描述，可以是用户名，它甚至可以是别的任意什么东西...以往这种情况会被认为是不符合UNIX哲学的，并且在以往，内存使用方式太小气，内存太奢侈。但是现如今，不需要吝啬内存了，我们便可以在内核里面塞入任何可以塞入的东西，只要设计得当，让它符合UNIX哲学精神即可。总的来讲，我希望从一个到达的数据包上取出一个事先配置好的字符串。
为何Linux没有实现
实际上我的想法一开始就是错误的。正确性在于我知道我是错的。为何一直以来我一直在“修补”Linux内核协议栈以及Netfilter扩展的各种不良或者不完备的实现呢，比如“立即生效NAT”，比如双向静态NAT，比如不完备的conntrack confirm机制，不一而足。这些缺陷难道Linux内核以及Netfilter社区的那帮大牛们意识不到吗？绝对不是这样，因为他们遵循的是Worse is better原则，该原则的核心就是简单主宰一切，为了简单可以舍弃该舍弃的一切。而我的做法，即实现很多协议栈不包含的东西，看起来就是违背的就是Worse is better原则，我用Completeness(完备性)原则替换了Simplicity(简单性)原则，而这两个的原则的正确表述应该是：
- Simplicity
- The design must be simple, both in implementation and interface. It is more important for the implementation to be simple than the interface. Simplicity is the most important consideration in a design.
- Completeness
- The design must cover as many important situations as is practical. All reasonably expected cases should be covered. Completeness can be sacrificed in favor of any other quality. In fact, completeness must be sacrificed whenever implementation simplicity is jeopardized. Consistency can be sacrificed to achieve completeness if simplicity is retained; especially worthless is consistency of interface.
- 所以，Linux的社区开发人员严格遵循了该原则，没有引入“复杂且不常用”的机制。而我为何非要实现它们呢？我的想法是一切为了满足我的需求，依照Simplicity优先原则，我不得不这么做，因为我这么做是为了不引入更复杂的机制。
分析
既然是给数据流绑定一个字符串，很显然，扩展nf_conntrack是绝佳的选择，如何扩展它我在前文已经做了详述。接下来需要考虑的是如何设置规则，很显然，写一个INFO iptables模块是一个选择：iptables -t ...-A .... -j INFO --set-info "aaaaaaaaaaaa"
INFO模块的思想是：从skb取出conntrack结构体，进而取出acct扩展(我总是喜欢拿account扩展开刀)，然后把set-info参数指示的信息拷贝到acct扩展中。
但是，如果有10000个info信息需要设置，我就要建立10000条规则，每一个数据包都要在内核中顺序的遍历以上所有的规则，iptables规则太多(超过5000条)的话，确实会严重影响网络性能。当然你可以灵活安排规则的顺序以便使数据包快速结束一个链的匹配过程，比如以下这样：
iptables ... -m state --state ESTABLISHED -j ACCEPT (设置在第一条，因为只有针对一个流的第一个NEW状态的数据包才会有set-info的必要)
.... -j INFO --set-info aaaaa
.... -j INFO --set-info bbbbb
.... -j INFO --set-info ccccc
这确实是一种技巧，玩过iptables的都知道，但是由于存在以下4个问题导致我不得不寻找其它的方案：
1.当INFO和INFO之外的其它target并不一致同意通过以上的方式跳出规则匹配链的时候，就需要安排另一条自定义链来解决。
2.由于上述第1点的频繁操作，最终会演变成针对iptables的编程，规则集本身会越来越复杂，像写得不好的C++代码那样，调整一条规则的顺序都将是极其困难的。
3.退一万步说话，对一个NEW状态的包，它真的就需要遍历规则(注意，iptables是遍历)匹配，我需要一种比O(n)高效的算法(nf-HiPAC在5000+条规则情况下会好很多)。
4.Netflter的nf-HiPAC项目可能是个创举，但是我没有时间详细研究它。
UNIX思想教导我们要将问题拆成互相独立的小问题，然后让它们相互配合去解决最终的大问题，但是相互配合本身有时会成为新的问题，需要付出巨大的管理成本。并不是每一类问题都可以拆成cat file|grep key那样的方式的。
当我发现IP路由的查找过程其实就是一个“匹配-动作”的模式之后，我便改了“动作”的解释，将“发往下一跳”改为“取出info信息”，注意，只是取出info信息，并没有设置它到conntrack，为何不把这两件事一起做呢？因为这两件事之间的关系和cat file|grep key之间的关系很像。上一小节的4个问题，我是这么回答的：
1.使用路由查找模块是完全独立于iptables，和iptables没有半毛钱关系；
2.使用路由查找模块不需要和任何其它模块接口，你只需要调用以下接口：
int nf_route_table_search(const u_int32_t src, char *info, int len);
如果src找到，则将和该地址所在的最长前缀匹配的网络关联的info信息取出来，如果没有与之关联的，则返回非0
3.效率更不用说，完全就是Linux内核的hash路由查找算法，用了十几年了，跑在各种环境下。
4.虽然我没有时间去研究nf-HiPAC项目，但是我对路由查找算法却早已精通，一个思想是：永远使用自己最熟悉的技术。
再次扩展
话说可以使用路由查找模块快速匹配到一个数据包关联的一个“路由项”，那么该路由项里面仅仅存一个字符串信息是不是太浪费了呢？能不能把路由项携带的信息也搞成可扩展的呢？答案无疑是肯定的，因为我已经将“下一跳”修改成了字符串信息，接下来就是取消这个类型定义就可以了，在路由项里面加一个void *指针无疑是可取的，但是为了使内存更紧凑，加入一个0长度数组是更好的选择。在内核中，struct fib_node指示一个路由项，为了和标准的区分，我加了一个nf_前缀表明它是和Netfilter关联并由nf_conntrack使用的“路由项”，同时去掉携带数据类型的定义：
/*
* 以下结构体指示一个“路由节点”，它可以携带一个extra_data
* 你可以任意定义它，比如可以如下定义：
* struct my_extra {
* char info[INFO_SIZE];
* int policy; // NF_ACCEPT,NF_DROP或者其它？
* // .... extra of extra ？？
* };
* 它带来了无限的扩展性，你可以使用这个“路由”节点存储任何数据。
*/
struct nf_fib_node {
struct hlist_node nf_fn_hash;
u_int32_t fn_key;
int len;
// extra_len指示你传入的extra data的长度
int extra_len;
// 0长度数组，你可以任意定义它
char extra[0];
};
PS： 《JAVA编程思想》第15章，15.16小节一开始：介绍过这样的思想，即要编写能够尽可能广泛地应用的代码。为了实现这一点，我们需要各种途径来放松对我们的代码将要作用的类型所作的限制，同时不丢失静态类型检查的好处。
进一步扩展
ACL的全称为访问控制列表，注意“列表”这个词，表明它的结构是一维线性。在很多的系统上，ACL对数据包的具体匹配行为依赖管理员的规则配置顺序。注意以上说的是ACL的用户配置接口，当然对于这一点，Linux的iptables以及Cisco的ACL是一致的，但是对于内部的实现，各家系统就有所区别了。以Linux的iptables为例，考虑以下的规则序列：i=1;
# 添加巨量的iptables规则
for ((; i < 255; i++)); do
j=1;
for ((; j < 255; j++)); do
iptables -A FORWARD -s 192.168.$i.$j -j DROP;
done
done
此时来了一个源地址是172.16.0.0/24网段的数据包，它是否要经过6万多条规则呢？当然了，你可以将一条针对非192.168.0.0/16段的ACCEPT规则放在第一条，但是这里的重点却是在实现层面而非配置层面的：在数据包匹配的过程中，如何迅速躲开那些明显不匹配的规则。这也是nf-HiPAC项目的目的之一。这种思想完全颠倒了以往以规则中的地址来匹配数据包的匹配主导权，变成了按数据包的源/目标IP去匹配规则。使用路由查找的思想无疑是很方便的！
按照上一小节我对struct nf_fib_node的扩展，在这个意义上，它的extra的定义已经相当明确：
struct my_extra {
// 替换iptables中的matches
struct list_head matches_list;
// 替换iptables的target
int policy; // NF_ACCEPT,NF_DROP或者其它？
};
表述出来就是，用数据包的源IP地址或者目标IP地址去“查一张路由表”，如果查找到，则取出它的extra数据，指示数据包如何被处理。
实现
上述的“进一步扩展”一节中说明的思想仅仅指出了一种可行性，我还没有想出把它放在哪个位置好。写下本文的目的最初是为了实现一个叫做conntrack_table的工具，针对nf_conntrack来做操作，比如：1.在conntrack里面绑定两个方向的路由，实现仅仅针对conntrack进行查找，不再针对每一个数据包都去查路由表；
2.用最长前缀匹配的IP路由查找机制而不是用iptables匹配机制来将一个conntrack的第一个数据包匹配到一个路由项，然后从该路由项中取出信息设置到conntrack结构体中；
由于周末的时间有限，平时回家又太晚，因此该版本的实现仅仅包含了使用路由机制保存网段的字符串信息，然后将其设置在conntrack结构体中。
内核机制实现思路
内核态一共需要实现两个部分，第一个部分是将标准的路由查找算法复制移植一份到nf_conntrack_ipv4模块中，第二部分就是在nf_conntrack被confirm的地方查询这个路由表，取出结果路由项中保存的info信息存储在conntrack中，这个操作仅仅针对一个流的第一个数据包。后续的数据包不再查询这个路由表。内核的路由查找模块的移植代码一会儿我再给出，现在先给出针对confirm的修改，修改的仅有ipv4_confirm函数，它是挂接于INET IPv4协议族的一个HOOK函数，这样我便不必考虑其它的协议了，从而省略了协议判断：static unsigned int ipv4_confirm(unsigned int hooknum,
struct sk_buff *skb,
const struct net_device *in,
const struct net_device *out,
int (*okfn)(struct sk_buff *))
{
...
out:
/* We've seen it coming out the other side: confirm it */
ret = nf_conntrack_confirm(skb);
if (ret == NF_ACCEPT) {
#include "nf_conntrack_info.h"
#define MAX_LEN 128
struct nf_conn_priv {
struct nf_conn_counter ncc[IP_CT_DIR_MAX];
char *info;
};
struct nf_conn_priv *ncp;
struct nf_conn_counter *acct;
acct = nf_conn_acct_find(ct);
if (acct) {
char buf[MAX_LEN] = {0};
int len = MAX_LEN;
struct iphdr *iph = ip_hdr(skb);
// 查询“路由表”，获取结果
int rv = nf_route_table_search(iph->saddr, buf, &len);
if (!rv) {
ncp = (struct nf_conn_priv *)acct;
if (ncp->info == NULL) {
ncp->info = (char *)kcalloc(1, len+1, GFP_ATOMIC);
}
// 拷贝获取的结果到conntrack
memcpy(ncp->info, buf, len);
}
}
}
return ret;
}
注意，这个ipv4_confirm里面的这个位置是我精心挑选的，一个好的插入点将会减少大量的if语句，不管是古老的语言还是OO语言，if语句都是在不得不用的时候才要用的。程序执行到一个位置，它本身应该知道自己的上下文信息，who am i这样的问题不该问。
好了，现在该把对Linux路由查找算法的移植展示出来了，我想hash算法已经经得住了这么多年的性能考验，也就没有移植trie树算法，同时我裁减掉了rehash机制。这个移植很简单，基本就是net/ipv4/fib_hash.c的修改操作，去除了fib_node的类型化定义，也就是说将其提升到了“泛型”的层次。代码如下：
头文件：nf_conntrack_rtable.h
#include <linux/types.h>
#include <linux/list.h>
#define SIZE 128
struct nf_fn_zone {
struct nf_fn_zone *fz_next; /* Next not empty zone */
struct hlist_head *fz_hash; /* Hash table pointer */
int fz_nent; /* Number of entries */
int fz_divisor; /* Hash divisor */
u32 fz_hashmask; /* (fz_divisor - 1) */
#define FZ_HASHMASK(fz) ((fz)->fz_hashmask)
int fz_order; /* Zone order */
u_int32_t fz_mask;
#define FZ_MASK(fz) ((fz)->fz_mask)
};
struct nf_fn_hash {
struct nf_fn_zone *nf_fn_zones[33];
struct nf_fn_zone *nf_fn_zone_list;
};
/*
* 以下结构体指示一个“路由节点”，它可以携带一个extra_data
* 你可以任意定义它，比如可以如下定义：
* struct my_extra {
* char info[128];
* int policy; // NF_ACCEPT,NF_DROP或者其它？
* // .... extra of extra ？？
* };
* 它带来了无限的扩展性，你可以使用这个“路由”节点存储任何数据。
*/
struct nf_fib_node {
struct hlist_node nf_fn_hash;
u_int32_t fn_key;
int len;
// extra_len指示你传入的extra data的长度
int extra_len;
// 0长度数组，你可以任意定义它
char extra[0];
};
// 查找接口
int nf_route_table_search(const u_int32_t dst, void *res, int *res_len);
// 添加接口
int nf_route_table_add( u_int32_t network, u_int32_t netmask, void *extra, int extra_len);
// 节点删除接口
int nf_route_table_delete(u_int32_t network, u_int32_t mask);
// 清除接口
void nf_route_table_clear(void);
C文件：nf_conntrack_rtable.c
#include <linux/types.h>
#include <linux/inetdevice.h>
#include <linux/slab.h>
#include <linux/kernel.h>
#include "nf_conntrack_info.h"
#ifndef NULL
#define NULL 0
#endif
// 使用lock总是安全的。内核编程两要素：1.安全；2.高效
static DEFINE_RWLOCK(nf_hash_lock);
struct nf_fn_hash *route_table = NULL;
static inline u_int32_t nf_fz_key(u_int32_t dst, struct nf_fn_zone *fz)
{
return dst & FZ_MASK(fz);
}
static inline u32 nf_fn_hash(u_int32_t key, struct nf_fn_zone *fz)
{
u32 h = key>>(32 - fz->fz_order);
h ^= (h>>20);
h ^= (h>>10);
h ^= (h>>5);
h &= FZ_HASHMASK(fz);
return h;
}
static struct hlist_head *fz_hash_alloc(int divisor)
{
unsigned long size = divisor * sizeof(struct hlist_head);
return kcalloc(1, size, GFP_ATOMIC);
}
static struct nf_fn_zone * fn_new_zone(struct nf_fn_hash *table, int z)
{
int i;
struct nf_fn_zone *fz = kcalloc(1, sizeof(struct nf_fn_zone), GFP_ATOMIC);
if (!fz)
return NULL;
if (z) {
fz->fz_divisor = 16;
} else {
fz->fz_divisor = 1;
}
fz->fz_hashmask = (fz->fz_divisor - 1);
fz->fz_hash = fz_hash_alloc(fz->fz_divisor);
if (!fz->fz_hash) {
kfree(fz);
return NULL;
}
fz->fz_order = z;
fz->fz_mask = inet_make_mask(z);
/* Find the first not empty zone with more specific mask */
for (i=z+1; i<=32; i++)
if (table->nf_fn_zones[i])
break;
write_lock_bh(&nf_hash_lock);
if (i>32) {
/* No more specific masks, we are the first. */
fz->fz_next = table->nf_fn_zone_list;
table->nf_fn_zone_list = fz;
} else {
fz->fz_next = table->nf_fn_zones[i]->fz_next;
table->nf_fn_zones[i]->fz_next = fz;
}
table->nf_fn_zones[z] = fz;
write_unlock_bh(&nf_hash_lock);
return fz;
}
// 路由表操作接口：1.查找；2.删除。参数过于多，类似Win32 API，风格不好，但使用方便
int nf_route_table_opt(const u_int32_t dst, const u_int32_t mask, int del_option, void *res, int *res_len)
{
int rv = 1;
struct nf_fn_zone *fz;
struct nf_fib_node *del_node = NULL;
if (NULL == route_table) {
printk("");
return 1;
}
read_lock(&nf_hash_lock);
for (fz = route_table->nf_fn_zone_list; fz; fz = fz->fz_next) {
struct hlist_head *head;
struct hlist_node *node;
struct nf_fib_node *f;
u_int32_t k = nf_fz_key(dst, fz);
head = &fz->fz_hash[nf_fn_hash(k, fz)];
hlist_for_each_entry(f, node, head, nf_fn_hash) {
if (f->fn_key == k){
if ( 1 == del_option && mask == FZ_MASK(fz)){
del_node = f;
} else if (0 == del_option){
// 将用户传入的extra数据拷贝给调用者。
memcpy(res, (const void *)(f->extra), f->extra_len);
*res_len = f->extra_len;
}
rv=0;
goto out;
}
}
}
rv = 1;
out:
read_lock(&nf_hash_lock);
if (del_node) {
write_lock_bh(&nf_hash_lock);
__hlist_del(&del_node->nf_fn_hash);
kfree(del_node);
write_unlock_bh(&nf_hash_lock);
}
return rv;
}
static inline void fib_insert_node(struct nf_fn_zone *fz, struct nf_fib_node *f)
{
struct hlist_head *head = &fz->fz_hash[nf_fn_hash(f->fn_key, fz)];
hlist_add_head(&f->nf_fn_hash, head);
}
int nf_route_table_search(u_int32_t dst, void *res, int *res_len)
{
return nf_route_table_opt(dst, 32, 0, res, res_len);
}
int nf_route_table_delete(u_int32_t network, u_int32_t mask)
{
return nf_route_table_opt(network, mask, 1, NULL, NULL);
}
int nf_route_table_add(u_int32_t network, u_int32_t netmask, void *extra, int extra_len)
{
struct nf_fib_node *new_f;
struct nf_fn_zone *fz;
new_f = kcalloc(1, sizeof(struct nf_fib_node) + extra_len, GFP_ATOMIC);
new_f->len = inet_mask_len(netmask);
new_f->extra_len = extra_len;
new_f->fn_key = network;
memcpy(new_f->extra, extra, extra_len);
if (new_f->len > 32) {
return -1;
}
INIT_HLIST_NODE(&new_f->nf_fn_hash);
if ( NULL == route_table){
route_table = kcalloc(1, sizeof(struct nf_fn_hash), GFP_ATOMIC);
fz = fn_new_zone(route_table,new_f->len);
} else {
fz = route_table->nf_fn_zones[new_f->len];
}
if (!fz && !(fz = fn_new_zone(route_table,new_f->len))) {
return -1;
}
fib_insert_node(fz, new_f);
return 0;
}
void nf_route_table_clear( void )
{
struct nf_fn_zone *fz,*old;
if (NULL == route_table) {
printk("");
return;
}
write_lock_bh(&nf_hash_lock);
for (fz = route_table->nf_fn_zone_list; fz; ) {
if (fz != NULL){
kfree(fz->fz_hash);
fz->fz_hash=NULL;
old = fz;
fz = fz->fz_next;
kfree(old);
old=NULL;
}
}
kfree(route_table);
route_table=NULL;
write_unlock_bh(&nf_hash_lock);
return;
}
编译相关我将上述代码放入net/ipv4/netfilter目录下，修改Makefile，加入nf_conntrack_rtable.o：
nf_conntrack_ipv4-objs := nf_conntrack_l3proto_ipv4.o nf_conntrack_proto_icmp.o nf_conntrack_info.o然后编译即可，出来的nf_conntrack_ipv4.ko就已经加入自己的扩展了。
用户接口
在抛弃iptables之后，我选择了procfs作为用户接口，因为它使用标准的文件IO接口，可以方便的在各种脚本中操作。这里还有三个思想。第一个思想是，如果已经有了现成的可以完成要求的机制，就不要编写C代码。内容越来越多，代码越来越少！
另外一个思想就是要使用事务型的操作，而不是自己封装事务序列。同样对于写文件，如果用C或者JAVA来写，那么你就必须完成open-readinfo-write-write-write...write end-close这样的序列，你操纵的不是文件，更多的是在玩弄编程语言本身，如果使用bash脚本，一个echo即可，echo程序内部封装了一个完整的序列(strace echo sth >./a便知)，你又何必自己重复实现一个类似的呢？当然这又引出了第三个思想。
使用文本而不是二进制来做配置。只要不是纯机器操作，就不要使用二进制，二进制是机器的世界，只要涉及到人的因素，文本是最好的信息交换方式。
因此，我选择了procfs作为和内核机制通信的方式，以它来配置策略，或者说添加/删除“扩展路由”。
效果
当我执行以下的操作：
echo +192.168.10.0 255.255.255.0 1234abcd >/proc/nfrtable
此时有来自192.168.10.30的数据包过来，你就会在/proc/net/nf_conntrack中看到和该数据流关联的1234abcd信息，反之如果有来自192.168.20.0/24网段的数据包，将不会有这个信息。此外，当你执行iptables-save的时候，再也看不到关于info的设置了，事实上，INFO模块根本就不需要了。
关于算法的重用
Linux内核是不拘一格的，其算法是公开的，因此也就没有什么Copy right一说，所以任何人都可以使用。关键的一点是，移植它的算法需要付出一点代价，正如Linus所说的那句经典的RTFS，Linux源码不提供任何的可移植性接口供用户使用，一切都需要你自己来做！比如，你不能在编译内核的时候将一些可重用的模块编译成一个Library，如果你需要，你必须自己来修改Makefile。关于Linux内核API
Linux内核API是多变的，这种运动给它带来的最大好处在于灵活，还是那句话，RTFS。源码就在你眼前，看到有需要的自己拿去，不过内核社区不提供任何搬运支持。正如一座金矿，管理者只是在管理它，任何淘金者都可以挖走自己需要的金子，但是管理者不提供任何车辆负责搬运，即使你有钱想租也没有，要知道，金子是很重的哦！Linux金矿还有另一项规则，即任何人都可以在里面加入自己的代码，工具以及任何其它东西。因此就引出一个问题，那就是Linux内核API的不稳定性。你别指望有一个品管团队来检查你的代码实现以及接口定义，社区在乎的是，只要它解决了实际问题，就会被采纳。如果你在使用2.6.18内核，然后你觉得不好，然后你修改了它的一部分接口，确实没有被Linus骂，那么这些接口将成为2.6.18-x或者2.6.19的标准接口。然而Linux提供了LKM机制，而LKM需要调用的正是内核接口，因此LKM的版本号必须和其宿主的内核版本号绝对一致，因为内核接口随时都是可以变化的。
Linux的风格决定了它的灵活性，代价就是诸多的关于LKM的限制。Windows正好相反，它提供最大限度的兼容性接口，不管是内核驱动还是用户应用都是如此，当然也有代价，那就是Windows内核和拥护库的日益臃肿，因为需要大量的适配器来兼容新老接口。微软的系统的API也是不断变化的，只是它向用户隐藏了这种变化而已，实施这种隐藏的正是微软的在职人员...
本文转自 dog250 51CTO博客，原文链接:http://blog.51cto.com/dog250/1398418
