Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1385383
  • 博文数量: 317
  • 博客积分: 1557
  • 博客等级: 上尉
  • 技术积分: 1208
  • 用 户 组: 普通用户
  • 注册时间: 2008-02-26 23:38
个人简介

如果想出发,就不要等到明天!

文章分类

全部博文(317)

文章存档

2016年(1)

2015年(41)

2014年(152)

2013年(114)

2012年(4)

2011年(1)

2009年(4)

分类: LINUX

2014-10-17 16:39:58

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

今天开始学习kernel中的路由表FIB的实现,kernel支持两种FIB的存储方式:一种是hash,另外一种是单词查找树trie。分别由编译选项CONFIG_IP_FIB_HASH和CONFIG_IP_FIB_TRIE决定。
(据说新版本的kernel已经去掉了hash的实现方式)

下面首先看一下FIB中的数据结构,大部分数据结构都在文件ip_fib.h中
  1. struct fib_config {
  2.     //目的地址的掩码
  3.     u8            fc_dst_len;
  4.     //TOS
  5.     u8            fc_tos;
  6.     //路由协议,其实更像是指该条路由是从何而来,参见RTPROT_STATIC等宏
  7.     //RTPROT_STATIC表示该route为管理员添加的静态路由,RTPROT_ZEBRA为由zebra添加的路由
  8.     u8            fc_protocol;
  9.     //参见rt_scope_t的定义
  10.     u8            fc_scope;
  11.     //类型如RTN_UNICAST:直连路由,参见类似的定义
  12.     u8            fc_type;
  13.     /* 3 bytes unused */
  14.     //指示哪个路由表,如RT6_TABLE_MAIN
  15.     u32            fc_table;
  16.     //目的地址
  17.     __be32            fc_dst;
  18.     //网关
  19.     __be32            fc_gw;
  20.     //出口的网卡
  21.     int            fc_oif;
  22.     //路由标志
  23.     u32            fc_flags;
  24.     //优先级
  25.     u32            fc_priority;
  26.     //prefer 源地址,暂不知道用途
  27.     __be32            fc_prefsrc;
  28.     
  29.     struct nlattr        *fc_mx;
  30.     struct rtnexthop    *fc_mp;
  31.     int            fc_mx_len;
  32.     int            fc_mp_len;
  33.     u32            fc_flow;
  34.     u32            fc_nlflags;
  35.     struct nl_info        fc_nlinfo;
  36.  };
struct fib_config主要用于将外部的route的配置/参数形式转为FIB的内部配置形式。如使用IP命令添加/删除route时,或者路由daemon向linux添加/删除时,都需要将其传入系统API的参数转为FIB的内部配置结构。

  1. /*
  2.  * This structure contains data shared by many of routes.
  3.  */

  4. struct fib_info {
  5.     struct hlist_node    fib_hash;
  6.     struct hlist_node    fib_lhash;
  7.     struct net        *fib_net;
  8.     int            fib_treeref;
  9.     atomic_t        fib_clntref;
  10.     int            fib_dead;
  11.     unsigned        fib_flags;
  12.     int            fib_protocol;
  13.     __be32            fib_prefsrc;
  14.     u32            fib_priority;
  15.     u32            fib_metrics[RTAX_MAX];
  16. #define fib_mtu fib_metrics[RTAX_MTU-1]
  17. #define fib_window fib_metrics[RTAX_WINDOW-1]
  18. #define fib_rtt fib_metrics[RTAX_RTT-1]
  19. #define fib_advmss fib_metrics[RTAX_ADVMSS-1]
  20.     int            fib_nhs;
  21. #ifdef CONFIG_IP_ROUTE_MULTIPATH
  22.     int            fib_power;
  23. #endif
  24.     struct fib_nh        fib_nh[0];
  25. #define fib_dev        fib_nh[0].nh_dev
  26. };
struct fib_info用于存储路由条目的一些共用的参数。

  1. struct fib_table {
  2.     /* 负载成员,用于将所有的fib_table链接起来 */
  3.     struct hlist_node tb_hlist;
  4.     u32        tb_id;
  5.     int        tb_default;
  6.     /* 路由表数据:因为有hash和trie两种方式,所以使用零长数组 */
  7.     unsigned char    tb_data[0];
  8. };

恩,下面开始学习代码,对于路由来说,最重要的就是路由的查询:
  1. static inline int fib_lookup(struct net *net, const struct flowi *flp,
  2.              struct fib_result *res)
  3. {
  4.     struct fib_table *table;
     /* 
     先查询本地地址路由表
     本地路由表保存本地地址,多播等,属于需要发送到本机的地址信息。
     */
  1.     table = fib_get_table(net, RT_TABLE_LOCAL);
  2.     if (!fib_table_lookup(table, flp, res))
  3.         return 0;
     /*
     再查询main路由表,这个是咱们设置路由或路由daemon设置的路由表 
     */
  1.     table = fib_get_table(net, RT_TABLE_MAIN);
  2.     if (!fib_table_lookup(table, flp, res))
  3.         return 0;
  4.     return -ENETUNREACH;
  5. }
fib_get_table比较简单,就是通过id,从net->ipv4.fib_table_hash中取出对应的路由表——对于IPv4来说。

那么查找路由的核心函数就为fib_table_lookup,这个函数的实现依赖于编译选项,共有两种实现方式,hash和trie。其中hash的实现比较简单,今天先学习hash的实现方式。
  1. int fib_table_lookup(struct fib_table *tb,
  2.          const struct flowi *flp, struct fib_result *res)
  3. {
  4.     int err;
  5.     struct fn_zone *fz;
  6.     /* 得到真正的route hash表 */
  7.     struct fn_hash *t = (struct fn_hash *)tb->tb_data;

  8.     read_lock(&fib_hash_lock);
  9.     /* 按顺序从fn_zone中查找路由,详细解释见后文 */
  10.     for (fz = t->fn_zone_list; fz; fz = fz->fz_next) {
  11.         struct hlist_head *head;
  12.         struct hlist_node *node;
  13.         struct fib_node *f;
  14. /* 计算key,实际就是dst的网络部分 */
  15.         __be32 k = fz_key(flp->fl4_dst, fz);
         /* 计算hash */
  1.         head = &fz->fz_hash[fn_hash(k, fz)];
 /* 在桶中遍历所有路由条目 */
  1.         hlist_for_each_entry(f, node, head, fn_hash) {
  2.             /* 地址网络部分的值不同,该路由肯定不符,跳过 */
  3.             if (f->fn_key != k)
  4.                 continue;
             /* 对路由进行其它的比较,如tos等 */
  1.             err = fib_semantic_match(&f->fn_alias,
  2.                          flp, res,
  3.                          fz->fz_order);
  4.             if (err <= 0)
  5.                 goto out;
  6.         }
  7.     }
  8.     err = 1;
  9. out:
  10.     read_unlock(&fib_hash_lock);
  11.     return err;
  12. }
从上面看,路由表的hash查找是比较简单的。唯一的疑惑就是这个struct fn_zone。
下面是路由hash表的数据结构
  1. struct fn_hash {
  2.     struct fn_zone    *fn_zones[33];
  3.     struct fn_zone    *fn_zone_list;
  4. };
路由hash表将路由条目按照掩码长度分到不同的33个fn_zones中,掩码长度为0即对应fn_zones[0],掩码长度为1即fn_zones[1],一直到掩码长度为32,则对应fn_zones[32]。而fn_zone_list指向的是最长的有路由条目的fn_zones。这样查找路由的时候,通过fn_zone_list顺序查找,从而实现了路由的最佳匹配。

今天基本上学习了kernel的路由表的hash实现方式。下面有可能将hash实现的完整的路由数据组织结构写出来,或者转到路由表trie的实现方式。


阅读(301) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册