内核中Radix Tree的疑问

Cyberman.Wu

首先我的理解是这样的：
1. 在/usr/src/sys/net/radix.c中有一些全局变量如rn_zeros、rn_ones，并且有人全局的树mask_rnhead，这些都在route_init()->rn_init()时初始化。然后在route_init()中调用各domain的dom_rtattach函数最终调用rn_inithead初始化自己的Tree。
2. 其它使用Radix tree的模块如ipfw直接调用rn_inithead初始化自己的Tree。Radix Tree的机制没有完全搞清楚，这里不明白的是，全局的Tree在其它Tree被操作时只要使用了mask都可能被操作到，为什么会这样？

另外看代码好像可以支持不在内核态使用似的：

void rn_init() {     char *cp, *cplim; #ifdef _KERNEL     struct domain *dom;     for (dom = domains; dom; dom = dom->dom_next)         if (dom->dom_maxrtkey > max_keylen)             max_keylen = dom->dom_maxrtkey; #endif     if (max_keylen == 0) {         log(LOG_ERR,             "rn_init: radix functions require max_keylen be setn");         return;     }     R_Malloc(rn_zeros, char *, 3 * max_keylen);     if (rn_zeros == NULL)         panic("rn_init");     bzero(rn_zeros, 3 * max_keylen);     rn_ones = cp = rn_zeros + max_keylen;     addmask_key = cplim = rn_ones + max_keylen;     while (cp < cplim)         *cp++ = -1;     if (rn_inithead((void **)(void *)&mask_rnhead, 0) == 0)         panic("rn_init 2"); }

但实际上如果不定义_KERNEL的话，静态全局变量max_keylen只能是0，所以总是返回失败，不明白为啥代码做成这样的。

[ 本帖最后由 Cyberman.Wu 于 2009-9-14 11:38 编辑 ]

ppabc

看不懂

wander8848

路由是路由，算法是算法，两者分的还是很清楚的。
我想详解二对radix树在路由里的使用方法已经说的很清楚了，还有有个牛人也写了篇文档介绍radix树。

mingyanguo

原帖由 Cyberman.Wu 于 2009-9-13 19:36 发表
首先我的理解是这样的：
1. 在/usr/src/sys/net/radix.c中有一些全局变量如rn_zeros、rn_ones，并且有人全局的树mask_rnhead，这些都在route_init()->rn_init()时初始化。然后在route_init()中调用各domain的d ...

不定义KERNEL自己在那里确定一下max_keylen就是了，加这个宏估计是方便测试。可以直接CC一下测试算法。

lllaaa

写代码的时候不是在内核里调试的。这种算法类的代码完全可以在userland来写和调试。