本文的copyleft归gfree.wind@gmail.com所有,使用GPL发布,可以自由拷贝,转载。但转载请保持文档的完整性,注明原作者及原链接,严禁用于任何商业用途。
作者:gfree.wind@gmail.com
博客:linuxfocus.blog.chinaunix.net
昨天学习了路由表hash实现的查询以及相关的一些数据结构。为了更清楚的说明路由表hash的实现方式,今天主要写一下使用hash时的路由表的数据组织结构。
第一层的数据结构是struct fib_table。
- struct fib_table {
-
struct hlist_node tb_hlist;
-
u32 tb_id;
-
int tb_default;
-
unsigned char tb_data[0];
-
};
其中最重要的是tb_data,它是真正的hash方式存储的数据,对于hash实现的路由表,其数据结构为struct fn_hash
- struct fn_hash {
-
struct fn_zone *fn_zones[33];
-
struct fn_zone *fn_zone_list;
-
};
fn_zones为大小33的数组,其索引值正好对应掩码长度。即fn_zones[0]对应掩码为0的路由(默认路由),fn_zones[1]对应掩码为1的路由,一直到fn_zones[32]对应掩码为32的路由。那么fn_zone_list是做什么用的呢?fn_zone_list是为了最佳匹配的路由查找。
比如当前有且只有3条路由,
1) ip route add 0.0.0.0/0 via 10.1.1.1
2) ip route add 192.168.3.0/24 via 10.1.1.2
3) ip route add 192.168.3.155/32 via 10.1.1.3
路由1存储在fn_zones[0]中,路由2存储在fn_zones[24],路由3存储在fn_zones[32]中。
那么此时的fn_zone_list指向的是fn_zones[32],完整的链表为
fn_zone_list(即fn_zones[32]).next->fn_zones[24]->fn_zones[0]。
这样按照前文学习的fib_table_lookup代码,顺序遍历fn_zone_list,也就实现了对路由的最佳匹配。
那么继续看struct fn_zone
- struct fn_zone {
-
struct fn_zone *fz_next; /* Next not empty zone */
-
struct hlist_head *fz_hash; /* Hash table pointer */
-
int fz_nent; /* Number of entries */
-
-
int fz_divisor; /* Hash divisor */
-
u32 fz_hashmask; /* (fz_divisor - 1) */
-
#define FZ_HASHMASK(fz) ((fz)->fz_hashmask)
-
-
int fz_order; /* Zone order */
-
__be32 fz_mask;
-
#define FZ_MASK(fz) ((fz)->fz_mask)
-
};
到了这层,就是一个hash的实现,fz_hash相当于hash中的桶。当查找路由时,通过hash函数得到hash值假设为h,则对应的桶为fz_hash[h]。
而桶中数据的组织结构为hlist,通过遍历该hlist,即得到每一个路由节点struct fib_node。
- struct fib_node {
-
struct hlist_node fn_hash;
-
struct list_head fn_alias;
-
__be32 fn_key;
-
struct fib_alias fn_embedded_alias;
-
};
本想画一个图的。。但是发现自己不太会玩UML画图工具呵。
估计上面的文字描述已经把路由表hash的实现方式清晰的描述出来了,就不上图了。
而且刚刚下了最新的stable kernel代码2.39.3,路由表已经不支持hash方式的实现了,只剩下trie方式。所以我也就不在这个hash的实现上耽误时间了——那个UML工具,已经浪费了我半个小时的时间了。
下次开始研究路由表trie的实现方式了
阅读(560) | 评论(0) | 转发(0) |