浅析route_table是如何工作

1、理解route_table是如何工作指导人：郭巍松 作者：王岩广 时 i'可：2005-9-71 route_table结构很重要denos route.table这个数据结构非常重要，许多结构是通过它来实现，比如pim-sm中的 tib,注册状态 reg, nexthop cache 等都其实是一个 route_tableo route_table 是一个二叉树（每 一个节点除带有一个左儿子，一个右儿子，还有一个父指针）。一个完整的route_table,由 两种结构组成，一个route_table和若干个route_node<> struct route_table 这

2、个结构由一个 sluct route_node 指针和一个 lable 号红i成。struct route_node *top;u int32 t id;/table 号 stuctroute.node这个结构其实是一个二叉树。（应为三叉树），它的内容包括：struct route_node *link2;/两个儿子stuct prefix p;前缀信息struct route_table *table;/ 指向一个 route_tableja我们使用来看，它是冋指本 身所在的表stuct route_node *parcnt;/父节点 unt32_t lock;void *info;/这个节

3、点真正的信息所在。注 意是任意类型指针void * aggregate;/目前不解，聚类指针一 般用于ripng中一个table是由若干个route_node组成，每一个route_node除了有一个父节点和两个儿子节 点外，还可以指向另一个table。下图是一个route_table的例子。strurtsirua rente ui>ltsirud kukjniide*l()p tj>tj2j id一个route.table骨架（没有画出info指针）2 route_table表节点的插入一个route_table是通过函数一次或多次调用route_node_get(table,p

4、refix)來创建和查询，通过 route_node_lookup()来查询(不创建)。现在通过get函数来分析一个table是如何建立起来, 和如何查询的。get函数如下：1 struct route_node *2 route_node_get (struct route_table * table, struct prefix *p)34 struct route_node *new;5 struct route_node *node;6 struct route_node * match; 表示被匹配到的节点，如果没有匹配到为空7 match = null;8 node = table

5、->top;9 while (node && node->pprefixlen <= p->prefixlen &&10 prefix_match (&node->p? p) /如果 prefix_match(a,b),即 a 的 prefixlen 小于等于 b,并且a的prefix中的前prefixlen跟b相同,即我们一般所 说的最短匹配11 12 if (node->p.prefixlen = p->prefixlen)13 14 routeock_node (node);15 return node;/

6、查询作用16 17 match = node;18 node = node->linkcheck_bit(&p->uprefix, node->p.prefixlen);19 20 if (node = null)/创建笫一个(时间顺序上的第一个，但不一定是根节点)节点，或创建叶子节点21 22 new = route_node_set (table, p);23 if (match) /创建的是叶子节点24 set_link (match, new);25 else26 table->top = new; 第一个节点27 28 else/创建中间节点29 30

7、 new = route_node_create ();31 route_common (&node->p, p, &new->p);/new->p 尽暈长的 prefixlen,但要匹配/node->p32 new->p.family = p->family;33 new->table = table;34 set_link (new, node);35 if (match)36 set_link (match, new);37 else38 table->top = new;39 if (new->p.prefixlen

8、 != p->prefixlen)/创建兄弟节点40 41 match = new; /创建的这个new不会被return出去，也就是不会被赋值info指针42 new = route_node_set (table, p);43 setjink (match, new);44 45 46 route_lock_node (new);47 return new;48 )2.1建立第一个节点假设现在没有节点，即route_table->top为null,则第8行，node被赋值为null,则跳 过循环体（一个查询匹配过程），因为node为null,程序到22行,new=route_n

9、ode_set（table,p） 函数分配一个route_node大小内存，并把p中的内容内存拷贝到new,则节点创建好了，接 下来将这个节点接在table后，即让table->top=nevo （显然此处match为null）,此亥u表如 图1所示：(注意：图中table_node结构没有画全，省略了 lock, aggregateo为了易于理解，1表示加 入的顺序号)2.2插入子节点(叶子节点)程序第8彳亍,node被赋值为table->top的值,即上图中1号table_node的地址。子节点的 prefixlen 定耍大于等于父节点的prefixlen,并且要匹配父节点。p

10、refix_match (prefix *n, prefix *p) =true 函数的含义是：p-> prefixlen>=n->prefixlen,并且在 p->u.prefix 的 0 到 n->prefixlen-l位与n->u.prefix的相应位相同，一句话就是我们常说的匹配。其余情况返冋 falseo可以子节点的prefix 一定要匹配父节点的prefix,或者说父节点的prefix包含子节点 的 prefix o进入循坏体，12行到16行是查询功能，我们不管。17行将node赋值给match,即匹配到 node这个节点。node顺儿子指针被赋

11、值为下一个，此处无论赋值左儿子还是右儿子都是空。(究竟如何确定被赋值为左还是右，下面会详细说到)。node被赋值为空，于是推出循环体，并到达22行。此处，我们发现回到了上一小节“建立 笫一个节点”相同的内容。的确是一样，他们都是要重新分配table_node空间，并赋值prefix, 但接下來就不同了。此处match不为null,我们此处是己经匹配到节点1的，所以执行 24行set_link (match, new)o这个函数是将刚创建并赋好值得new插入到match之后，作他 的儿子节点。具体怎么插入，我们来看：static voidset_li nk (struct route_ node

12、 * father, struct route_node *son)int bit;bit = check_bit (&son->p.u.prefix, falher->p.prefixlen);pal_assert (bit = 0 | bit = 1);father->linkbit = son;son->parent = father;可以看出，要想做father的儿子，首先决定确左儿子还是右儿子，通过函数check_bit来确 定。因为儿子跟父子在父子的prefixlen范围内完全一样，这个函数其实就是检测prefix之后 笫一位,如果是零，则为左儿子，

13、否则就是右儿子。father->linkbit = son, son->parent = father即是赋值动作。图二为加了之后的二叉树：图二加入叶子节点2.3插入父节点或兄弟节点如果待加入的prefix, prefixlen比树第一个节点还要短，或者比树中某一个节点的prefixlen 短，再或者跟树中某一个节点prefixlen 样长，但并不匹配它，即从循环体跳出，但node 并不为空。此时程序到30行，函数route_node_create ()只是分配table_node大小的内存，并不给new赋值。n->u.prefix p> u.pre fix new&g

14、t;u.prefix 可以看出：31 行，函数 route_common (struct prefix *n, struct prefix *p, struct prefix *new)其实是给 new 赋值的过程,如何赋值呢?如果在p>prefixlen之内,从最左边(最高位)开始n->u.prefix 跟p->u.prefix连续相同的bit位，赋值给new->u.prefix的相应位，同时这个位数作为 new->prefixlen,其他位赋值0。举例prefixlen=24prefixlen= 18prefixlen=51100 0000 1110 0001

15、 0010 0001 0000 00011100 0100 1100 0001 0010 0001 0000 00011100 0000 0000 0000 0000 0000 0000 0000 如果 new->prefixlen 等于 p->prefixlen,则表示在 p->prefixlen 范围内 p 的值跟 n->u.prefix 完全相等，同时p->prefixlen又小于等于n->prefixlen,进一步说p包含了 n,则p应为 n的父节点。 如果 new->prefixlen 小于 p->prefixlen,则表示 p->

16、;u.prefix 从 new->prefixlen z后开始不 同于n->u.prefix,即n和p都应该是new的儿子，且因为第new->prefixlen个bit不同 而分为左儿子和又儿子。代码30-38插入父节点new,代码39-44,即为如果new->prefixlen小于p->prefixlen,插入 兄弟节点。下图是儿种插入后的可能情况:图31插入成为根节点（虚线表示可能碍要插入为兄弟节点）图32插入中间结点（虚线表示可能插入为兄弟节点）最后，通过插入过程我们可以看出如下几个特征： 子节点一定匹配父节点，父节点一定包含子节点（即子的掩码长度二父的，且

17、最短匹 配） 子节点的prefix中在父节点的prefixlen之后的第一位为0,则为左节点，否则为右节点 左节点和右节点的prefixlen不一定相等 每一次调用route_node_get函数不一定在table创建一个节点，有可能先创建一个节点, 再创建一个此节点的子节点返回，这就意味着一个route_table中有可能有info指针为 空的节点。3树中节点的查询3.1 route_node_lookup此函数输入table的地址，以及prefix 就是遍历树(根据p->u.prefix的内容决定左枝还 是右枝)，当 node->p.prefixlen = p->pref

18、ixlen 时返冋(前提是 prefix_match()=true 了)。 route_node_get,也是首先查询(方法相同，查不到时创建),lookup只查询不创建。此接 口不会返回info指针为空的节点。3.2 route_next 禾口 route_next_until用这个函数遍历二叉树for (rn=table->top;rn;rn=route_next(rn)if(m >info = null)continue; 或for (rn=table->top;rn;m=route_next_util(rn, limit)if(m->info = null)continue;就是先根遍历二叉树算法或者部分遍历。但是因为其屮可能有虚节点（即imo指针为空的 节点）返回，所以对于每一个节点作检查。4节点的lock、unlock与删除树中每一个节点都一个lock属性，其实就是一个引用计数。一个节点被初建时lock为1。 每一次访问该节点之前都应该调用route_iock_node,访问结束时调用route_unlock_node0但是注意对同一个节点的lock, unlock有时是在不同的函数中完成。比如当你lookup 一个 节点时，lookup函数通常会在返冋你要找的节点之前将之lock,那么你在使用完此节点后要 记得unloc