Chinaunix首页 | 论坛 | 博客
  • 博客访问: 8019408
  • 博文数量: 159
  • 博客积分: 10424
  • 博客等级: 少将
  • 技术积分: 14615
  • 用 户 组: 普通用户
  • 注册时间: 2010-07-14 12:45
个人简介

啦啦啦~~~

文章分类
文章存档

2015年(5)

2014年(1)

2013年(5)

2012年(10)

2011年(116)

2010年(22)

分类: LINUX

2011-07-20 22:08:18

本文的copyleft归gfree.wind@gmail.com所有,使用GPL发布,可以自由拷贝,转载。但转载请保持文档的完整性,注明原作者及原链接,严禁用于任何商业用途。
作者:gfree.wind@gmail.com
博客:linuxfocus.blog.chinaunix.net
   

昨天学习了路由表hash实现的查询以及相关的一些数据结构。为了更清楚的说明路由表hash的实现方式,今天主要写一下使用hash时的路由表的数据组织结构。

第一层的数据结构是struct fib_table。
  1. struct fib_table {
  2.     struct hlist_node tb_hlist;
  3.     u32        tb_id;
  4.     int        tb_default;
  5.     unsigned char    tb_data[0];
  6. };
其中最重要的是tb_data,它是真正的hash方式存储的数据,对于hash实现的路由表,其数据结构为struct fn_hash
  1. struct fn_hash {
  2.     struct fn_zone    *fn_zones[33];
  3.     struct fn_zone    *fn_zone_list;
  4. };
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
  1. struct fn_zone {
  2.     struct fn_zone        *fz_next;    /* Next not empty zone    */
  3.     struct hlist_head    *fz_hash;    /* Hash table pointer    */
  4.     int            fz_nent;    /* Number of entries    */

  5.     int            fz_divisor;    /* Hash divisor        */
  6.     u32            fz_hashmask;    /* (fz_divisor - 1)    */
  7. #define FZ_HASHMASK(fz)        ((fz)->fz_hashmask)

  8.     int            fz_order;    /* Zone order        */
  9.     __be32            fz_mask;
  10. #define FZ_MASK(fz)        ((fz)->fz_mask)
  11. };
到了这层,就是一个hash的实现,fz_hash相当于hash中的桶。当查找路由时,通过hash函数得到hash值假设为h,则对应的桶为fz_hash[h]。

而桶中数据的组织结构为hlist,通过遍历该hlist,即得到每一个路由节点struct fib_node。
  1. struct fib_node {
  2.     struct hlist_node    fn_hash;
  3.     struct list_head    fn_alias;
  4.     __be32            fn_key;
  5.     struct fib_alias fn_embedded_alias;
  6. };

本想画一个图的。。但是发现自己不太会玩UML画图工具呵。
估计上面的文字描述已经把路由表hash的实现方式清晰的描述出来了,就不上图了。

而且刚刚下了最新的stable kernel代码2.39.3,路由表已经不支持hash方式的实现了,只剩下trie方式。所以我也就不在这个hash的实现上耽误时间了——那个UML工具,已经浪费了我半个小时的时间了。

下次开始研究路由表trie的实现方式了

阅读(7186) | 评论(0) | 转发(14) |
给主人留下些什么吧!~~