netfilter数据结构设计的艺术

netfilter较以前的ipchains提升了一个层次，在ipchains的东西中抽象出来共性的东 西然后形成了一个框架，从ipchains到netfilter的发展展现了软件发展的数据不断抽象的过程，也正是《重构》一书中讲的精髓。 netfilter不再为具体的过滤服务，而是提供了一个过滤模板，用户不再需要重新设计具体的过滤过程，而只需要填充这个模板就可以了，也就是说 netfilter只提供了机制，而策略需要用户空间的iptables程序来设置，然后在netfilter的框架机制上运行，这十分符合linux的 设计哲学，这个意义上，ipchains注定要被赶出去的，正如khttpd注定出局一样。netfilter框架中从低到高有几个概念：表 （table），链（chain），规则--匹配（match）/目标（target），一个表有若干条链，一条链有若干个规则，其中table和 chain作为底层的支撑提供运行机制，而规则（match/target）就是用户的策略，要iptables实用程序设置。因为框架主要提供过滤机制，因此这个框架就叫做netfilter，而这个框架最底层的是table，所以它的策略程序就叫做iptables，下面就开始扯netfilter 的更深层的意义。
如果第一次看netfilter，那么肯定很多人都会被它的数据结构搞晕，因为在整个内核中，它几乎就是一个另类，c语言明明提供了struct和很多的 数据类型，而且linux的内核内存管理框架也提供了很多的机制，比如slab等等，但是netfilter似乎对这些并不感冒，它竟然自己实现了自己数 据结构的独特管理方式，包括数据结构设计，字段生成，数据定位以及修改。很容易迷惑的地方就是table，match，target的组织形式，这个和 linux路由表的组织类似但是更复杂，不是数据结构更复杂，而是数据结构的组织方式更复杂，如果在用户空间，那么你可以随意设计很多的数据结构，完全按照自己的设计意愿做出各种数据结构，然后用指针将它们按照自己的设计意愿组合在一起，因为用户空间的程序不必过于考虑效率问题和别的什么问题，那些都是标 准库或者操作系统的事，用户程序只要考虑应用本身就可以了，但是到了内核就不可以了，内核是机制的实现，很多用户或者库可以推掉的事情必须由内核来承担，比如用户程序可以不考虑内存的管理甚至不用管内存泄露，但是库必须要为用户程序擦屁股，如果库也不管，那么内核必须提供这样功能，起码要提供一个好的动态 内存管理接口以便库甚至应用程序自己可以更容易的实现一个，也就是说，底层的尽量惯着上层的，包括为之提供好的机制，为之实现错误检测，实在超越了自己的设计边界，那才由应用程序自己承担，这是一个强大的操作系统必须做到的。对于性能，这是操作系统必须要考虑的，因为绝对不允许在操作系统内核内部浪费哪怕 几个时钟周期，因为内核只是一个服务者，这个要求就好比饭店的服务员尽量不要比客户多一样。正是因为如此，netfilter的设计即体现用户应用策略但 是却又在内核实现才显得与众不同。
     netfilter本质上是一个线性的结构，它自己管理着一大块内存，然后在这块内存上开始表演，它不用内核的机制而是自己管理它，在外界看来，这块内存就是一块普通的内存，外界只会将之看作一个整体一团混沌而不能看到内部，但是对于netfilter自己，它看到的却是一片奇妙的世界，它可以看到自己亲手切开的美味的蛋糕，我们现在就尝尝这块蛋糕：
struct xt_table            //一个总体上的表，建立间架结构
{
         struct list_head list;                 //内核中所有的netfilter表连接成一个链表，这是它与外界的不多的几个接口之一，内核通过此链表对netfilter进行管理
         const char name[XT_TABLE_MAXNAMELEN];  //唯一的名字，用作识别
         unsigned int valid_hooks;              //感兴趣的钩子
         rwlock_t lock;
         void *private;    //填充物，void *类型易于扩展。这个是最重要的，其实就是xt_table_info，鉴于层次分离与扩展原则，这里用void*
...
         u_int8_t af;            //协议族
};
struct xt_table_info  //数据结构组织上和上面的的xt_table分离，描述本表的静态数据
{
         unsigned int size;
         unsigned int number;
         unsigned int initial_entries;
         unsigned int hook_entry[NF_INET_NUMHOOKS];  //本table作用的钩子
         unsigned int underflow[NF_INET_NUMHOOKS];
         char *entries[1];   //每个cpu一个的ipt_entry，但是每个表的ipt_entry可由其next_offset连接成串
};
struct ipt_entry  //数据结构组织上和上面的的xt_table_info分离，描述本表的动态行为，真正开始工作的策略在这里体现
{
         struct ipt_ip ip;
         unsigned int nfcache;
         u_int16_t target_offset;   //本ipt_entry中target的偏移，系统将迭代所有的match，找到一个匹配上，然后调用target
         u_int16_t next_offset;     //本xt_table_info中下一个ipt_entry的偏移
         unsigned int comefrom;
         struct xt_counters counters;
         unsigned char elems[0];    //0个或者多个match以及一个target顺序排列（c语言技巧）
};
struct xt_entry_match
{
          union {
                 struct {
                         u_int16_t match_size;
                         char name[XT_FUNCTION_MAXNAMELEN-1];
                         u_int8_t revision;
                 } user;    //用户结构
                 struct {
                         u_int16_t match_size;
                         struct xt_match *match;//内核的匹配结构，内部有匹配函数
                 } kernel;  //内核结构
                 u_int16_t match_size;
         } u;
         unsigned char data[0];
};
struct xt_entry_target
{
         union {
                 struct {
                         u_int16_t target_size;
                         char name[XT_FUNCTION_MAXNAMELEN-1];
                         u_int8_t revision;
                 } user;
                 struct {
                         u_int16_t target_size;
                         struct xt_target *target; //内核的target函数
                 } kernel;
                 u_int16_t target_size;
         } u;
         unsigned char data[0];
};
由 上述的结构可以看出，从ipt_entry开始，所有的结构体都连接成串，整体在物理上是一个线性结构，这一点从一系列的offset指针可以看出来，但 是这些结构在逻辑上却是一个立体结构，和关系数据库很像，而且最重要的也是我感觉最妙的是，netfilter并没有用指针指来指去来引用数据结构，而是 直接用这种线性式的手工分割数据的方式来进行，看看上面的数据结构，到处都是void *类型的或者char *类型的指针，这不但分离了类型相关的数据结构之间的耦合，而且手工分割虽然没有类型信息，但是却可以使执行更加有效率。因为netfilter涉及到很 多迭代过程，当然说到迭代不能不想到的就是链表，很多时候就是list_head，虽然这个结构很小很强大，不会带来多少开销，但是netfilter的 设计者还是避开了它，这样带来了时间和空间上效率的提升，在空间上，我们可以看到，除了总体的间架结构，其它的都没有链表指针，如果不看代码实现和注释，只看那些数据结构，你肯定为它们是如何组织成一个立体结构的原因而发蒙，少了链表指针或者嵌入式链表就可以少一个字段从而节省了小部分空间，再从时间上考 虑，如果使用嵌入式链表，那么必然在还原原始数据结构的时候要用container_of类似的宏：
#define container_of(ptr, type, member) ({                      /
    const typeof( ((type *)0)->member ) *__mptr = (ptr);    /
    (type *)( (char *)__mptr - offsetof(type,member) );})
可 以看到，这要所少次指针引用，浪费多少个时钟周期。于是netfilter的设计者就想出了直接用偏移引用的直线式的一维数据结构，然后通过其逻辑意义组织成关系结构。我们可以看一下match的迭代过程，没有任何别的结构字段指示特定结构的地址（指针），而是全部靠原始的char *或者void *来指示，这样就可以指示任意类型的数据结构了，而且位置用偏移来表示，这样就可以将一个线性连续的数据区，类似于堆区的内存块分割成一个个有意义的数据结构，具体是什么意义，在初始化的时候指定，然后在运行时应用，注意，这样做的缺点就是阅读起来不甚明了，不过清晰性和性能本来就是鱼与熊掌，不可兼得， 另外，在你应用你自己手工分割的数据结构时，你必须保证其已经经过完全的初始化，因为在运行时应用的时候没有类型信息在里面，无法进行检测。还是看一下这个迭代过程吧：
#define XT_MATCH_ITERATE(type, e, fn, args...)          /
({                                                      /
         unsigned int __i;                              /
         int __ret = 0;                                 /
         struct xt_entry_match *__m;                    /                                           
         for (__i = sizeof(type);                       /
              __i < (e)->target_offset;                 /    //结束条件
              __i += __m->u.match_size) {               /    //__m-u.match_size是前一个match的大小，注意，所有的match是线性顺序排列的，而且大小不是确定的，因此通过将一个 match加上这个size来找到下一个match
                 __m = (void *)e + __i;   /                                                             
                 __ret = fn(__m , ## args);             /  //调用函数，这个函数是个功能函数，指示了这次迭代一个ipt_entry的所有match需要干什么事情。比如在迭代ipt_entry时的 do_match和在初始化match时的find_check_match
                 if (__ret != 0)                        /
                         break;                         /
         }                                              /
         __ret;                                         /
})
整个netfilter的执行过程中，一共有过三次也就是三个层次的迭代，一次是hook的迭代，hook强调一种钩子，包括钩子的位置以及行为，netfilter在不同的hook上尝试，这也是最高层的迭代：
list_for_each_continue_rcu(*i, head) {
                 struct nf_hook_ops *elem = (struct nf_hook_ops *)*i;
...
                 verdict = elem->hook(hook, skb, indev, outdev, okfn);
在 每一个hook上调用hook函数，如果该hook上挂载有netfilter的表，那么就开始了第二次迭代也就是更低一级别的迭代就是该表 xt_table_info的所有的ipt_entry的迭代，比如在ipt_do_table中就有体现，这其中就是通过ipt_entry中的 next_offset字段进行的，基本调用形式就是像下面这样朴素的形式：
struct ipt_entry *next = (void *)e + e->next_offset;
接 下来对于每个ipt_entry，如果有match的话，那么就要进行更低一级别的第三次迭代，就是上面所说的matchs迭代进行数据包匹配，一旦找到 一个匹配，那么就要调用target进行最后的裁决，这个target顺序排在所有match的后面，通过ipt_entry的 target_offset可以找到。这个netfilter中到处都是这种方式的代码，很拗但是仔细研究却很艺术，因为netfilter用这种方式解决了用户策略的多样化的难题，要知道内核只提供机制而不管策略，但是像netfilter这样和用户策略结合这么紧密的模块该怎么设计，这就是一个问题了，比如该把数据结构定位为多大，表的数量以及类型如何关联和协作，和用户紧密相关导致数据结构要有很多灵活的字段，并且这一点就会导致数据结构的不定长 特性，再者数据结构可能会随意组合，鉴于此要用分层次的设计方法，但是层次之间怎么结合又是问题，可选字段的存在导致数据结构定义的复杂度增加，用联合会使代码可维护性降低，因此就选择了这种线性排列的靠偏移分割的整体数据结构，更加有创意的是，很多数据结构都是无类型的，只是一个指针，然后通过偏移来定 位不同的数据结构，这样就解决了用户策略设置的数据结构不一致以及可选字段存在的问题。
     GNU编译器支持一种特殊的写法，就是结构内部零长度数组，这个特性特别适合可选字段或者不定长字段，因为即使为了支持不定长数据不用定长的数组而在这里设置一个指针类型的数据，那么如果本结构没有可选字段，就会白白浪费4个字节的空间，因此这个特性非常巧妙。举例：
struct zero_array
{
    char* strVersion;
    int   iLength;
    char  real_data[0];
};

这 个结构中，并不知道zero_array数据结构是否携带数据以及携带多少，这些数据信息都会在iLength上体现，应用这个结构的程序察看该结构的 iLength字段得知是否有以及有多少实际数据，上述写法可以将real_data在逻辑上在虚拟地址空间置于zero_array之后，这是编译器的 特性而不是语言的规范，而且这种方式虽然可以灵活分配数据，但是不能在栈上分配这样的数据结构。再看看上述的结构，是否非常像网络协议的格式，将不定长的数据结构中定长的部分剖出来作为结构体本身的定义作为消息头，然后将不定长的所有的消息数据用零长度数组表示。