radix.c

Details description of Free BSD network source code.Those documents have explained each line of code

/*
 */
#ifndef _RADIX_H_
#include <sys/param.h>
#ifdef	_KERNEL
#include <sys/lock.h>
#include <sys/mutex.h>
#include <sys/systm.h>
#include <sys/malloc.h>
#include <sys/domain.h>
#else
#include <stdlib.h>
#endif
#include <sys/syslog.h>
#include <net/radix.h>
#endif

static int	rn_walktree_from(struct radix_node_head *h, void *a, void *m,walktree_f_t *f, void *w);/*遍历路由树的函数*/
static int rn_walktree(struct radix_node_head *, walktree_f_t *, void *);/*遍历路由树的函数,和上面一样,只不过参数不同*/
static struct radix_node
	 *rn_insert(void *, struct radix_node_head *, int *,struct radix_node [2]),/*在路由树中插入一节点和一叶子*/
	 /*注:在路由树中插入一叶子时也必须同时插入一节点*/
	 *rn_newpair(void *, int, struct radix_node[2]),/*该函数是制作两个redix_node节点,该两个节点是左边的和另一个(有可能是*/
	 /*中间一个节点即初始化调用时,也有可能是右边的节点即rn_inset调用时),返回另一个节点的指针*/
	 *rn_search(void *, struct radix_node *),/*搜索匹配的叶子函数,其中void * 代表是一个sockaddr结构类型的指针*/
	 *rn_search_m(void *, struct radix_node *, void *);/*和上面差不多,只是参数不同,后一个参数是掩码的指针(也是sockaddr结构)*/

static int	max_keylen;/*所有协议中地址最长的长度*/
static struct radix_mask *rn_mkfreelist;/*空闲的掩码指针,如果有申请掩码结构长度的块,该指针不为空时,使用该指针,在MKGet宏中使用*/
static struct radix_node_head *mask_rnhead;/*掩码树的首指针*/
static char *addmask_key;/*临时存放掩码的地方*/
static char normal_chars[] = {0, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, -1};
static char *rn_zeros, *rn_ones;/*一个全0和一个全1的掩码的指针,他们的长度是max_keylen(上面的),在rn_inithead中初始化*/

#define rn_masktop (mask_rnhead->rnh_treetop)/*掩码树的第一个节点.*/
#undef Bcmp
#define Bcmp(a, b, l) \  
	/*比较a和b是否相等*/
	((l) == 0 ? 0 : bcmp((caddr_t)(a), (caddr_t)(b), (u_long)(l)))

static int	rn_lexobetter(void *m_arg, void *n_arg);
static struct radix_mask *rn_new_radix_mask(struct radix_node *tt,struct radix_mask *next);/*共享键(既重复键)中加一新的掩码*/
static int	rn_satisfies_leaf(char *trial, struct radix_node *leaf,int skip);/*用于确定是否trial和leaf是在同一子网*/

/*从head节点开始向下搜索一与sockaddr结构v_arg相匹配的叶子*/
static struct radix_node *      /*返回值是一叶子*/
rn_search(v_arg, head)			/*v_arg是一将被搜索的叶子,head是将开始的节点.*/
	void *v_arg;
	struct radix_node *head;
{
	register struct radix_node *x;/*放到CPU通用寄存器中加快速度*/
	register caddr_t v;

	for (x = head, v = v_arg; x->rn_bit >= 0;) {/*到遇到一叶子时停止*/
		if (x->rn_bmask & v[x->rn_offset])/*按位进行与操作,rn_bmask是位掩码*/
			x = x->rn_right;/*说明树的右下面的节点将是下一个循环被检测的节点.*/
		else
			x = x->rn_left;/*说明树的左下面的节点将是下一个循环被检测的节点.*/
	}
	return (x);/*出来时x->rn_bit<0,即x指向一叶子,且该叶子与被查询的叶子(v_arg)最为接近.*/
}
/*由rn_match函数调用,返回值是叶子*/
static struct radix_node *
rn_search_m(v_arg, head, m_arg)
	struct radix_node *head;
	void *v_arg, *m_arg;
{
	register struct radix_node *x;
	register caddr_t v = v_arg, m = m_arg;
/*使用该函数的目的在于提高性能，其实用上面的函数也能达到目的，采用该函数的情况是调用函数是在回朔*/
/*其间调用，而回朔时已经判断了如果上一层的节点无掩码，就再回朔到上一层*/
	for (x = head; x->rn_bit >= 0;) {/*循环的入口是一节点，当遇到一叶子时退出循环。*/
		if ((x->rn_bmask & m[x->rn_offset]) &&
		    (x->rn_bmask & v[x->rn_offset]))/*当节点的该位置位（为1），并且该节点的掩码该位也为1*/
			x = x->rn_right;/*上面条件成立则下一循环使用该节点右下方的节点*/
		else
			x = x->rn_left;/*否则使用该节点左下方的节点*/
	}
	return x;/*循环的出口是指向一匹配的叶子*/
}

int
rn_refines(m_arg, n_arg)
	void *m_arg, *n_arg;
{
	register caddr_t m = m_arg, n = n_arg;/*sockaddr结构类型指针,该结构第一字节是整个结构的长度*/
	register caddr_t lim, lim2 = lim = n + *(u_char *)n;/*lim,lim2都指向n的尾部+1的地方,*(u_char *)n是n指向的第一个字节的内容,即n结构的长度*/
	int longer = (*(u_char *)n++) - (int)(*(u_char *)m++);/*看看n结构比m结构长多少*/
	int masks_are_equal = 1;
/*  目前的情况:lim2,lim,n
    <------------16-------------->
    |-----|----------------------|
    ^ 16  <---------15----------->
    n  ^
	  *(u_char *)n=16            ^
	                           lim,lim2
	执行int longer=...以后,n的指针发生了改变
	      ^
		  n  从这比较比较合理,因为前面一个字节是表示整个结构的长度,所以第一个字节不能比较.
	
*/
	if (longer > 0)/*即n的结构>m的结构(就那IP协议来说,IP地址的结构比IP地址掩码的结构就要长)*/
		lim -= longer;
/* 我们来看看上面的这种情况,如图所示:这是longer大于0的情况
	<---------8-------->
    |-----|------------|
    ^  8  <---7-------->
    m  ^
	  *(u_char *)n=8             ^
	                           lim2	
						<-longer->
					   ^
					  lim=lim-longer  即lim为要比较的尾部指针
	执行int longer=...以后,n的指针发生了改变
	      ^
		  m  从这比较比较合理,因为前面一个字节是表示整个结构的长度,所以第一个字节不能比较.

*/
	while (n < lim) {/*如果m和n都是*/
		if (*n & ~(*m))
			return 0;
		if (*n++ != *m++)
			masks_are_equal = 0;
	}
	while (n < lim2)
		if (*n++)
			return 0;
	if (masks_are_equal && (longer < 0))
		for (lim2 = m - longer; m < lim2; )
			if (*m++)
				return 1;
	return (!masks_are_equal);
}

struct radix_node *
rn_lookup(v_arg, m_arg, head)
	void *v_arg, *m_arg;
	struct radix_node_head *head;
{
	register struct radix_node *x;
	caddr_t netmask = 0;

	if (m_arg) {
		x = rn_addmask(m_arg, 1, head->rnh_treetop->rn_offset);
		if (x == 0)
			return (0);
		netmask = x->rn_key;
	}
	x = rn_match(v_arg, head);
	if (x && netmask) {
		while (x && x->rn_mask != netmask)
			x = x->rn_dupedkey;
	}
	return x;
}

static int
rn_satisfies_leaf(trial, leaf, skip)/*参数skip是地址要跳过的部分(因为前面相同而不需要比较)*/
	char *trial;/*要查询的地址指针*/
	register struct radix_node *leaf;/*要被比较的叶子*/
	int skip;
{
	register char *cp = trial, *cp2 = leaf->rn_key, *cp3 = leaf->rn_mask;
	/*cp是要查询的协议地址指针,cp2是被比较的叶子中包含的协议地址指针,cp3是被比较的叶子的掩码指针,该指针用*/
	/*来确定cp所指示的地址是否是在该叶子的子网内*/
	char *cplim;/*是地址结束地方的指针,比较的时候用来判断是否到了地址尾部.*/
	int length = min(*(u_char *)cp, *(u_char *)cp2);/*取最小值用来作为比较的长度*/

	if (cp3 == 0)/*如果叶子的掩码为空的话,那么意味着他是一个主机路由,主机路由有一个全1的掩码*/
		cp3 = rn_ones;/*rn_ones是一个全1的掩码,在rn_inithead函数中初始化(该函数在最后的第二个函数)*/
	else
		length = min(length, *(u_char *)cp3);/*同上面一样*/
	cplim = cp + length; cp3 += skip; cp2 += skip;/*cplim就指向了要比较的最尾端,cp3指向掩码要开始比*/
	/*较的地方(skip之前是相同的,不需要比),cp2指向叶子中包含的协议地址指针要比较的开始的地方.*/
	for (cp += skip; cp < cplim; cp++, cp2++, cp3++)/*逐个字节的比较*/
		if ((*cp ^ *cp2) & *cp3)/*实际上是(*cp & *cp3) ^ (*cp2 & *cp3) 即地址cp和掩码cp3相与后看看是否和*/
								/*地址cp2与掩码cp3相与后的结果一样,一样的话就是在同一个子网,即找到了网络地址*/
			return 0;/*为真就是两个地址不在同一个子网络上*/
	return 1;/*到这的话就代表是在同一个子网*/
}
/*查询是否有节点和v_arg匹配*/
struct radix_node *
rn_match(v_arg, head)
	void *v_arg;/*要查询的匹配节点指针,sockaddr结构指针,(IP协议为sockaddr_in结构)*/
	struct radix_node_head *head;/*协议的radix树节点顶部*/
{
	caddr_t v = v_arg;
	register struct radix_node *t = head->rnh_treetop, *x; /*t为该协议的radix树的顶部三radix_node节点中间的一个*/
	register caddr_t cp = v, cp2;/*cp是指针v的备份*/
	caddr_t cplim;
	struct radix_node *saved_t, *top = t;/*top是radix_node结构指针t的备份*/
	int off = t->rn_offset, vlen = *(u_char *)cp, matched_off;/*C语言要熟悉哦,*(u_char *)cp代表取指针cp指向的第一个字节,*/
	register int test, b, rn_bit;                             /*在此处cp是一sockaddr结构的指针,该结构第一个u_char是结构长度*/
	/*变量off(上面定义的)代表在sockaddr结构中要测试的位的偏移量*/
	for (; t->rn_bit >= 0; ) {/*测试是否是节点,>=0是节点,该循环的意思是每一级的测试位与sockaddr协议地址的相应位测试,从而找到最相近的节点.*/
		if (t->rn_bmask & cp[t->rn_offset])
			t = t->rn_right;
		else
			t = t->rn_left;
	}/*最终出循环的时候是到了一个叶子上(t->rn_bit<0).*/
	/*其实路由的精华就在这个循环内,要理解并不容易.*/
	/* 以下是源代码中的解释:
	 * 经过该循环,我们完全匹配了目的主机的地址或匹配了前面的多少位
	 */
	if (t->rn_mask)/*叶子有掩码吗?*/
		vlen = *(u_char *)t->rn_mask;/*有,取指针指向的第一个字节(是该掩码的长度)*/
	cp += off; cp2 = t->rn_key + off; cplim = v + vlen;
	/*cp指向了协议地址,cp2指向了查找到的radix树中的协议地址,cplim是地址结束的指针*/
	for (; cp < cplim; cp++, cp2++)/*开始比较协议地址*/
		if (*cp != *cp2)
			goto on1;/*找到的radix树中的地址和要查找的地址不完全匹配*/
	if (t->rn_flags & RNF_ROOT)/*RNF_ROOT是顶部的树,是默认路由.*/
		t = t->rn_dupedkey;
	return t;/*找到了该radix_node*/
on1:/*在不匹配的情况下要做的工作*/
	test = (*cp ^ *cp2) & 0xff; /* 看看到底在协议地址的第几位上开始不同(此时的cp和cp2经过上面的for循环已经到了不相同的哪个字节) */
	for (b = 7; (test >>= 1) > 0;)/*测试一下,到底是第几位上不同呢?*/
		b--;
	/*最终得出在第b位上开始不同.*/
	matched_off = cp - v;/*不同的位置-协议地址开始的位置=两个地址相同部分的长度*/
	b += matched_off << 3;/*matched_off<<3代表字节换算成位以后的长度.b=以位为单位的开始不相同长度*/
	rn_bit = -1 - b;/*好,记录此位到rn_bit中.*/
	if ((saved_t = t)->rn_mask == 0)/*如果掩码为空,则代表隐含的全为1的主机路由.在查询重复键前先保存.*/
		t = t->rn_dupedkey;/*首先看看有无重复键*/
	for (; t; t = t->rn_dupedkey)/*当然无重复键就不会进入此循环*/
		if (t->rn_flags & RNF_NORMAL) {/*是正常路由吗?是就代表是一叶子*/
			if (rn_bit <= t->rn_bit)/*新的算法,在老的NET/3中没有,指当被解释地址的掩码第一个出现0的位置比被对比的叶子的掩码第一个出现0的位置更靠前的时候就认为找到了.*/
				return t;
		} else if (rn_satisfies_leaf(v, t, matched_off))/*matched_off代表两个地址相同的部分(即不需要比较,可跳过的部分)*/
				return t;/*上面的函数主要是查看是否是和该叶子在同一子网内.为真则在同一子网内,并返回该叶子.*/
	t = saved_t;/*既然上面已经判断即不在重复键中,也不在同一子网内,那么准备向上一层回朔.*/
	/* 在树中进行回朔 */
	do {
		register struct radix_mask *m;/*掩码节点指针,因为频繁使用,所以放到CPU的通用寄存器中以加快速度*/
		t = t->rn_parent;/*回朔到父节点*/
		m = t->rn_mklist;/*m指向父节点的掩码列表指针*/
		/*如果存在掩码列表指针,那么每个掩码都要搜索 */
		while (m) {
			if (m->rm_flags & RNF_NORMAL) {/*是正常路由吗?是就代表是一叶子*/
				if (rn_bit <= m->rm_bit)/*新的算法,在老的NET/3中没有,指当被解释地址的掩码第一个出现0的位置比被对比的叶子的掩码第一个出现0的位置更靠前的时候就认为找到了.*/
					return (m->rm_leaf);/*返回该掩码指向的叶子.*/
			} else {
				off = min(t->rn_offset, matched_off);/*matched_off是两个地址相同部分的长度,rn_offset是比较的位置*/
				x = rn_search_m(v, t, m->rm_mask);/*该函数在上面,从新的位置开始搜索*/
				while (x && x->rn_mask != m->rm_mask)
					x = x->rn_dupedkey;/*搜索重复键,直到x->rn_mask == m->rm_mask*/
				if (x && rn_satisfies_leaf(v, x, off))/*查看是否属于该叶子的子网*/
					return x;
			}
			m = m->rm_mklist;/*下一个掩码*/
		}
	} while (t != top);/*没有到树顶就继续循环*/
	return 0;/*没找到*/
}

#ifdef RN_DEBUG
int	rn_nodenum;
struct	radix_node *rn_clist;
int	rn_saveinfo;
int	rn_debug =  1;
#endif
/*该函数是制作两个redix_node节点,该两个节点是左边的和中间的,返回中间节点的指针.初始化和insert时调用*/
static struct radix_node *
rn_newpair(v, b, nodes)
	void *v;
	int b;
	struct radix_node nodes[2];/*nodes是两个节点的指针*/
{
	register struct radix_node *tt = nodes, *t = tt + 1;/*tt是左边节点,t是中间节点*/
	t->rn_bit = b;/*b>=0代表是节点,否则是叶子,并且是叶子中掩码第一个开始为0的位置,以位为单位,不是以字节*/
	t->rn_bmask = 0x80 >> (b & 7);/*7=0111(二进制),计算位掩码.如b=3的话,结果就应该为二进制00100000*/
	t->rn_left = tt;/*tt在t节点的左边*/
	t->rn_offset = b >> 3;/*因为b是代表偏移的位,转化为字节要除以8,既>>3*/
	tt->rn_bit = -1;/*小于0,是叶子.*/
	tt->rn_key = (caddr_t)v;/*IP中实际上是sockaddr_in结构的地址*/
	tt->rn_parent = t;/*父节点是中间的节点.*/
	tt->rn_flags = t->rn_flags = RNF_ACTIVE;/*加上活动标志*/
	tt->rn_mklist = t->rn_mklist = 0;/*掩码列表暂时为空.*/
#ifdef RN_DEBUG /*关于调试的代码,我就不具体分析了,因为他和原理没有很大的关系*/
	tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++;
	tt->rn_twin = t;
	tt->rn_ybro = rn_clist;
	rn_clist = tt;
#endif
	return t;/*返回中间节点*/
}
/*插入一叶子*/
static struct radix_node *
rn_insert(v_arg, head, dupentry, nodes)
	void *v_arg;/*要插入叶子的sockaddr结构的指针*/
	struct radix_node_head *head;/*指插入的树,如:IPX或IP的路由树*/
	int *dupentry;/*用于返回时的函数判断,为1代表成功*/
	struct radix_node nodes[2];
{
	caddr_t v = v_arg;/*转换为地址结构指针*/
	struct radix_node *top = head->rnh_treetop;/*指向该协议的路由树顶部*/
	int head_off = top->rn_offset, vlen = (int)*((u_char *)v);/*head_off是开始测试的位置,vlen是要插入的叶子的sockaddr结构的长度*/
	register struct radix_node *t = rn_search(v_arg, top);/*从top节点开始向下搜索一与sockaddr结构v_arg相匹配的叶子*/
	register caddr_t cp = v + head_off;/*指向开始测试的位置*/
	register int b;
	struct radix_node *tt;
 
    {
	register caddr_t cp2 = t->rn_key + head_off;
	register int cmp_res;
	caddr_t cplim = v + vlen;

	while (cp < cplim)
		if (*cp2++ != *cp++)
			goto on1;
	*dupentry = 1;
	return t;
on1:
	*dupentry = 0;
	cmp_res = (cp[-1] ^ cp2[-1]) & 0xff;
	for (b = (cp - v) << 3; cmp_res; b--)
		cmp_res >>= 1;
    }
    {
	register struct radix_node *p, *x = top;
	cp = v;
	do {
		p = x;
		if (cp[x->rn_offset] & x->rn_bmask)
			x = x->rn_right;
		else
			x = x->rn_left;
	} while (b > (unsigned) x->rn_bit);
				/* x->rn_bit < b && x->rn_bit >= 0 */
#ifdef RN_DEBUG/*调试时打印一些信息*/
	if (rn_debug)
		log(LOG_DEBUG, "rn_insert: Going In:\n"), traverse(p);
#endif
	t = rn_newpair(v_arg, b, nodes); /*看上面的函数说明,该函数是制作两个redix_node节点,该两个节点是左边的和另一个(有可能是*/
									/*中间一个节点即初始化调用时,也有可能是右边的节点即rn_inset调用时),返回另一个节点的指针*/
	tt = t->rn_left;/*进行树的连结*/
	if ((cp[p->rn_offset] & p->rn_bmask) == 0)