浅析route_table是如何工作

理解Route_table是如何工作指导人：郭巍松作者：王岩广时间：2005-9-71Route_table结构很重要Dcnos中route_table这个数据结构非常重要，许多结构是通过它来实现，比如PIM-SM中的TIB，注册状态reg，nexthopcache等都其实是一个route_table。Route_table是一个二叉树（每一个节点除带有一个左儿子，一个右儿子，还有一个父指针）。一个完整的route_table，由两种结构组成，一个route_table和若干个route_node。Structroute_table这个结构由一个Stuctroute_node指针和一个table号组成。Structroute_node*top;U_int32_tid;//table号Stuctroute_node这个结构其实是一个二叉树。（应为三叉树），它的内容包括：Structroute_node*link[2];//两个儿子Stuctprefixp;//前缀信息Structroute_table*table;//指向一个route_table,从我们使用来看，它是回指本身所在的表Stuctroute_node*parent;//父节点U_int32_tlock;Void*info;//这个节点真正的信息所在。注意是任意类型指针Void*aggregate;//目前不解，聚类指针一般用于ripng中一个Table是由若干个route_node组成，每一个route_node除了有一个父节点和两个儿子节点外，还可以指向另一个table。下图是一个route_table的例子。Structroute_tableStructroute_nodeStructroute_node*topU_int32_tId一个route_table骨架（没有画出info指针）2Route_table表节点的插入一个route_table是通过函数一次或多次调用route_node_get(table,prefix)来创建和查询，通过route_node_lookup()来查询（不创建）。现在通过get函数来分析一个table是如何建立起来，和如何查询的。Get函数如下：1structroute_node*2route_node_get(structroute_table*table,structprefix*p)3{4structroute_node*new;5structroute_node*node;6structroute_node*match;//表示被匹配到的节点，如果没有匹配到为空7match=NULL;8node=table-top;9while(node&&node-p.prefixlen=p-prefixlen&&10prefix_match(&node-p,p))//如果prefix_match(a,b),即a的prefixlen小于等于b，并//且a的prefix中的前prefixlen跟b相同，即我们一般所//说的最短匹配11{12if(node-p.prefixlen==p-prefixlen)13{14route_lock_node(node);15returnnode;//查询作用16}17match=node;18node=node-link[check_bit(&p-u.prefix,node-p.prefixlen)];19}20if(node==NULL)//创建第一个（时间顺序上的第一个，但不一定是根节点）节点，或//创建叶子节点21{22new=route_node_set(table,p);23if(match)//创建的是叶子节点24set_link(match,new);25else26table-top=new;//第一个节点27}28else//创建中间节点29{30new=route_node_create();31route_common(&node-p,p,&new-p);//new-p尽量长的prefixlen，但要匹配//node-p32new-p.family=p-family;33new-table=table;34set_link(new,node);35if(match)36set_link(match,new);37else38table-top=new;39if(new-p.prefixlen!=p-prefixlen)//创建兄弟节点40{41match=new;//创建的这个new不会被return出去，也就是不会被赋值info指针42new=route_node_set(table,p);43set_link(match,new);44}45}46route_lock_node(new);47returnnew;48}2.1建立第一个节点假设现在没有节点，即route_table-top为NULL，则第8行，node被赋值为NULL，则跳过循环体（一个查询匹配过程），因为node为NULL，程序到22行，new=route_node_set(table,p)函数分配一个route_node大小内存，并把p中的内容内存拷贝到new，则节点创建好了，接下来将这个节点接在table后，即让table-top=new。（显然此处match为NULL），此刻表如图1所示：（注意：图中table_node结构没有画全，省略了lock，aggregate。为了易于理解，1表示加入的顺序号）图1第一个节点2.2插入子节点（叶子节点）程序第8行，node被赋值为table-top的值，即上图中1号table_node的地址。子节点的prefixlen一定要大于等于父节点的prefixlen，并且要匹配父节点。Prefix_match（prefix*n，prefix*p）==true函数的含义是：p-prefixlen=n-prefixlen，并且在p-u.prefix的0到n-prefixlen-1位与n-u.prefix的相应位相同，一句话就是我们常说的匹配。其余情况返回false。可以子节点的prefix一定要匹配父节点的prefix，或者说父节点的prefix包含子节点的prefix。进入循环体，12行到16行是查询功能，我们不管。17行将node赋值给match，即匹配到node这个节点。Node顺儿子指针被赋值为下一个，此处无论赋值左儿子还是右儿子都是空。（究竟如何确定被赋值为左还是右，下面会详细说到）。Node被赋值为空，于是推出循环体，并到达22行。此处，我们发现回到了上一小节“建立第一个节点”相同的内容。的确是一样，他们都是要重新分配table_node空间，并赋值prefix，但接下来就不同了。此处match不为NULL，我们此处是已经匹配到节点1的，所以执行24行set_link(match,new)。这个函数是将刚创建并赋好值得new插入到match之后，作他的儿子节点。具体怎么插入，我们来看：staticvoidset_link(structroute_node*father,structroute_node*son){intbit;bit=check_bit(&son-p.u.prefix,father-p.prefixlen);pal_assert(bit==0||bit==1);father-link[bit]=son;son-parent=father;}可以看出，要想做father的儿子，首先决定确左儿子还是右儿子，通过函数check_bit来确定。因为儿子跟父子在父子的prefixlen范围内完全一样，这个函数其实就是检测prefix之后第一位，如果是零，则为左儿子，否则就是右儿子。father-link[bit]=son，son-parent=father即是赋值动作。图二为加了之后的二叉树：图二加入叶子节点2.3插入父节点或兄弟节点如果待加入的prefix，prefixlen比树第一个节点还要短，或者比树中某一个节点的prefixlen短，再或者跟树中某一个节点prefixlen一样长，但并不匹配它，即从循环体跳出，但node并不为空。此时程序到30行，函数route_node_create（）只是分配table_node大小的内存，并不给new赋值。31行，函数route_common(structprefix*n,structprefix*p,structprefix*new)其实是给new赋值的过程，如何赋值呢？如果在p-prefixlen之内，从最左边（最高位）开始n-u.prefix跟p-u.prefix连续相同的bit位，赋值给new-u.prefix的相应位，同时这个位数作为new-prefixlen，其他位赋值0。举例n-u.prefix11000000111000010010000100000001prefixlen=24p-u.prefix11000100110000010010000100000001prefixlen=18new-u.prefix11000000000000000000000000000000prefixlen=5可以看出：如果new-prefixlen等于p-prefixlen，则表示在p-prefixlen范围内p的值跟n-u.prefix完全相等，同时p-prefixlen又小于等于n-prefixlen，进一步说p包含了n，则p应为n的父节点。如果new-prefixlen小于p-prefixlen，则表示p-u.prefix从new-prefixlen之后开始不同于n-u.prefix，即n和p都应该是new的儿子，且因为第new-prefixlen个bit不同而分为左儿子和又儿子。代码30-38插入父节点new，代码39-44，即为如果new-prefixlen小于p-prefixlen，插入兄弟节点。下图是几种插入后的可能情况：图3-1插入成为根节点（虚线表示可能需要插入为兄弟节点）图3-2插入中间结点（虚线表示可能插入为兄弟节点）最后，通过插入过程我们可以看出如下几个特征：子节点一定匹配父节点，父节点一定包含子节点（即子的掩码长度=父的，且最短匹配）子节点的prefix中在父节点的prefixlen之后的第一位为0，则为左节点，否则为右节点左节点和右节点的prefixlen不一定相等每一次调用route_node_get函数不一定在table创建一个节点，有可能先创建一个节点，再创建一个此节点的子节点返回，这就意味着一个route_table中有可能有info指针为空的节点。3树中节点的查询3.1route_node_lookup此函数输入table的地址，以及prefix*p，就是遍历树（根据p-u.prefix的内容决定左枝还是右枝），当node-p.prefixlen==p-prefixlen时返回（前提是prefix_match()==true了）。Route_node_get，也是首先查询（方法相同，查不到时创建），lookup只查询不创建。此接口不会返回info指针为空的节点。3.2route_next和route_next_until用这个函数遍历二叉树for（rn=table-top;rn;rn=route_next(rn)）{if(m-info==NULL)continue;…}或for（rn=table-top;rn;rn=route_next_util(rn,limit)）{if(m-info==NULL)continue;…}就是先根遍历二叉树算法或者部分遍历。但是因为其中可能有虚节点（即info指针为空的节点）返回，所以对于每一个节点作检查。4节点的lock、unlock与删除树中每一个节点都一个lock