BSDradix树路由表的设计原理
写这篇文章的时候使用的是FreeBSD5.1的代码，举例用的是IPv6地址。BSD路由表使用的是radix树，这种树的设计思想来自Donald R.Morrison于1968年提出的Patricia树（Practical Algorithm To Retrieve Information Coded In Alphanumeric）。这是一种基于以二进制表示的键值的查找树，尤其适合于处理非常长的、可变长度的键值。Partricia的基本思想是构建一个二叉树，在每个节点中都存储有进行下一次的bit测试之前需要跳过的bit数目，以此来避免单路分支（即避免二叉树的某一段呈现只往左或者只往右生长的趋势）。因此，一般意义上的Patricia树由内部节点和外部节点组成，内部节点用于指示需要进行bit测试的位置，并依据bit测试结果决定查找操作的前进方向，而外部节点则用于存储键值，查找操作将于外部节点处终止。
BSD正是借用了Partricia树的思想来组织路由表，但考虑到路由表的特殊性，即需要存储掩码并实现最长匹配路由查找，于是对Partricia树进行了改造，形成了BSD的radix树。在BSD的radix树中的路由查找操作将分为三个步骤，第一个步骤即是Partricia查找，终结于某个叶子节点，判断该叶子节点是否与查找键相同。第二个步骤，如果找到的叶子节点与查找键无法匹配，则在这个叶子节点的重复键链表中寻找网络匹配的可能。第三个步骤，如果找到的叶子节点及其重复键与查找键不满足网络匹配条件，则向树顶回溯，继续寻找网络匹配的可能。
1 BSD路由表的表头
BSD路由表的头指针存放在rt_tables[]数组中，这是一个radix_node_head结构体类型的指针数组。在BSD的协议栈中，所有协议的路由表都是用radix树进行组织的，而这些radix树的头指针就都存放在rt_tables[]数组中，IPv6路由表的头指针只是其中之一，即下标为AF_INET6的数组元素。
radix_node_head结构体的内存布局如图1所示。rnh_treetop是指向路由表顶部节点的指针。在这个结构体中还定义了8个函数指针，分别指向路由表提供的8个操作函数。在这个结构体的尾部还有三个radix_node结构体，这就是radix树的初始三节点，它们的rn_flags字段将被设置成RNF_ROOT，表示这是radix树的根节点。这三个节点是在路由表跏蓟?鄙?傻摹?
路由表初始化完成后，这三个根节点的链接关系如图3所示。从这个图中我们可以看出，在三个根节点组成的数组rnh_nodes[3]中，第二个根节点作为路由表的顶部节点，由rnh_treetop指针指向，它将是对路由表的所有操作的开始处。此外，第一个根节点被初始化为顶部节点的左孩子，第三个根节点被初始化为顶部节点的右孩子，而这三个初始根节点的父指针都指向了中间的那个顶部节点。这实际上已经搭起了一个radix树的基本框架。如图2所示。
在图2中，我们将中间的作为路由树顶的根节点用圆圈表示，因为它属于内部节点。而另外的两个根节点我们用方框表示，它们属于叶子节点。在本文档中将始终按照这一约定来图示内部节点和叶子节点。
2 BSD路由表的节点
BSD路由表的radix树实际上就是由一系列的内部节点和叶子节点组成的。内部节点位于树的中间位置，每个内部节点都会指定一个bit测试位置，即当从树的顶端开始向下查找，遇到这个内部节点时需要判断是0还是1的bit位置，接下来的查找将根据bit测试的结果来决定是向左走还是向右走。叶子节点位于树的边缘，用于存储路由表键值，即IP地址。
2.1 内部节点
前已述及，内部节点在radix树中用于表示一个bit测试位置。
内部节点和叶子节点使用的都是radix_node结构体，只是少数字段的定义有所不同。我们首先通过内部节点来查看一下radix_node结构体中的各个字段。在radix树中的3个根节点中，位于中间的那个顶端节点就是内部节点，因此我们的描述就以图3为例。
rn_mklist:这个指针指向的是一个radix_mask结构体链表。对于内部节点来说这个链表上的掩码都取自它的子树中的叶子节点所对应的掩码，但只有那些在做逻辑AND运算时能够把这个内部节点的测试bit变成0的掩码才能够加入到这个链表中，这类掩码的作用将在路由查找时的回溯过程中体现出来。对于叶子节点，如果它的掩码满足上述条件而被选入它的某一级父节点的掩码链表的话，那么它的rn_mklist指针就会指向这个掩码链表中对应于它自己的掩码的那个节点。
rn_parent:这是节点的父指针，从叶子节点一直向上指到树的顶端节点，而树的顶端节点的父指针是指向它自己的。路由查找时的回溯过程将沿父指针进行。
rn_bit:对于内部节点，这个值大于等于0，用于指示在这个内部节点处需要进行测试的bit位置。这个位置是从用于存储IP地址的socket地址结构体的起始位置开始计算的。对于叶子节点，这个值是一个负数，具体数值就是-1减去这个叶子节点所对应的掩码的索引值。而所谓掩码的索引值就是指这个掩码中第一次出现0的bit位置，这个位置也是从socket地址结构体的起始位置开始计算的。
rn_bmask:这是一个1字节的掩码，其中只有一个bit为1。在实际的路由查找中，为了加快查找速度，就是使用这个字段直接对指定的字节进行bit测试，而不是指定bit进行测试。对于叶子节点，这个字段为0。
rn_flags:这个字段的可能取值一共有3个，RNF_NORMAL，表示这是一个含有常规路由的叶子节点；RNF_ROOT，表示这是一个位于radix_node_head结构体中的节点，即路由表中的三个根节点；RNF_ACTIVE，表示这条路由的状态是好的。
rn_Off:这是内部节点独有的字段，表示一个从socket地址结构体的起始位置开始计算的字节偏移量，用于指定在这个内部节点处需用rn_bmask进行单字节比较的字节偏移量。
rn_L:这是内部节点独有的字段，指向这个内部节点的左孩子。
rn_R:这是内部节点独有的字段，指向这个内部节点的右孩子。
2.2 叶子节点
叶子节点和内部节点的大部分字段都是一样的，只是最后三个字段的定义不一样。相同字段的定义已在前面的内部节点部分进行了描述，最后三个字段的定义如下。
rn_Key:这个字段就内存位置而言相当于内部节点中的rn_Off字段。这个字段用于指向存储着叶子节点键值（即IP地址）的socket地址结构体。
rn_Pfxlen: 这个字段就内存位置而言相当于内部节点中的rn_L字段。这个字段用于存储前缀长度。
rn_Dupedkey: 这个字段就内存位置而言相当于内部节点中的rn_R字段。当路由表中有重复键情况出现的时候，即有多个叶子节点的键值（IP地址）相同，这些叶子节点是以链表的形式挂接在树中的某个叶子节点下的，rn_Dupedkey即指向重复键链表中的下一个叶子节点。
在radix树中，左右两个根节点即属于叶子节点。
2.3 根节点
radix树中的根节点即是在图2和图3中给出的3个节点。这三个节点都被设置了RNF_ROOT标志，以表示它们是根节点。
中间的那个根节点是radix树的顶部节点，所有的路由查找操作都是从它开始的。我们可以看到，这个根节点的bit测试位置是64，也就是说，对于存储在socket地址结构体中的BSD地址而言，实际的BSD地址开始的第一个bit在结构体中的偏移量是64，整个radix树的bit比较算法就是从这第64 bit开始。前已述及，为了加快查找速度，实际的查找操作中使用的是字节偏移和字节掩码。因此，第64 bit对应的字节偏移就是8，而字节掩码就是二进制的1000 0000。
另外的两个根节点分列于树的最左端和最右端。我们可以看到，它们的rn_bit字段都小于0，表明这两个根节点属于叶子节点。事实上，它们一个对应的是全0键值，一个对应的是全1键值。
在路由查找操作中，任何时刻都不能返回根节点本身。如果查找操作定位到了根节点，将代之以返回空指针。
2.4 重复键节点
BSD路由表中的重复键节点是指路由树中键值（IP地址）完全相同的叶子节点。
这些重复键节点由各自的rn_Dupedkey指针串成一个链表，通过位于链表头部的叶子节点挂在路由树中。位于链表中的重复键节点是按照掩码的精确程度从高到低排列的，即位于链表头部的叶子节点的掩码最精确，对于掩码连续的情况而言也就是它的掩码最长。这样在路由查找的时候如果找到了这串重复键节点，就可以保证掩码最长的路由最先匹配。
3 BSD路由表的路由条目
如前所述，BSD路由表是由一系列的内部节点和叶子节点组织起来的，这是BSD路由表的逻辑结构。如果从内存布局来讲，BSD路由表中的路由条目则是通过rtentry结构体来存放的，我们前面提到的内部节点和外部节点实际上都是存放在这个结构体中的。rtentry结构体的组成如图4所示。
我们可以看到，在rtentry结构体的头部就是由两个radix_node结构体组成的数组rt_nodes[2]。在这个数组中，第一个元素是叶子节点，负责存储路由表键值，即IP地址，第二个元素是内部节点，负责完成树的连接。因此，就一般情况而言，每当往路由树中添加一条路由的时候，我们实际上添加的是两个节点，一个叶子节点和一个内部节点，只不过这两个节点的存储空间是我们事先用rtentry结构体分配好了的。虽然这两个节点在物理上是紧挨着的，但是由于后续路由条目的加入，它们之间就可能会插入一系列的内部节点，而这些内部节点又分别属于各自的rtentry结构体，并对应着各自的叶子节
