1、（一） 概述 路由策略数据库（ RPDB） 路由部分结构 整个路由系统可以分成三部分： IP 层调用接口，路由策略数据库，和前后端接口 1、 IP 层调用接口主要是提供一组调用接口给 IP 层代码： 这一部分主要提供了两个供 IP 层调用的入口函数： int ip_route_input ( struct sk_buff * skb, u32 dst, u32 src , u8 tos, struct net_device *dev ); int ip_route_output ( struct rtable *rp, u32 daddr, u32 saddr, u32 tos, int oi
2、f ) ip_route_input_slow ：当 ip_route_input 查 cache 不命中时调用此函数，此函数进而调用路由策略数据库的查询接口进行查询，然后更新路由 cache 。 ip_route_output_slow ：当 ip_route_output 查 cahe 不命中是调用此函数，此函数进而调用路由策略数据库的查询接口进行查询， 然后更新路由 cache 。 2、路由策略数据库部分主要包括一个策略库和多张路由表： 策略表 fib_rule 每个策略是一个 fib_rule 结构。这个结构有几个重要的域： r_preference 这个策略的优先级。 r_table
3、 这个策略对应的路由表，它是路由表索引表 fib_tables 的一个索引值。 r_action 策略的动作，如单播，丢弃， NAT 等。 r_src,r_srcmask,r_dst,r_dstmask,r_tos 等 策略的选择器，即描述什么样的 IP 包匹配这条策略。 路由表 fib_table 定义如下： struct fib_table * local_table ; struct fib_table * main_table ; struct fib_table * fib_tables RT_TABLE_MAX +1; 它的数据结构是： struct fib_table unsig
4、ned char tb_id; unsigned tb_stamp; int (*tb_lookup)(struct fib_table * tb , const struct rt_key * key , struct fib_result * res ); int (*tb_insert)( ); int (*tb_delete)( ); int (*tb_dump)( ); int (*tb_flush)(struct fib_table * table ); int (*tb_get_info)( ); void (*tb_select_default)( ); unsigned ch
5、ar tb_data0; ; fib_table 结构只是一个路由表结构中最上层的一个结构，它下面还很多的层次，下面这张图描绘了整个路由表的数据结构： 第一个层次是 fib_table 和 fn_hash 结构。实际上， fn_hash 结构即是 fib_table 的 tb_data 域。 这一层主要是包括一个 路由表所对应的标识符 (tb_id) ，操作函数指针 (tb_looup 等 ) ，以及对所有路由项的一个总索引 (fn_hash 结构 ) 。最为重要的就是这个索引，一个路由表把它所有的路由项划分成 33 个区域 ，划分的原则即是子网掩码的长度（从 0 到 32 ），这 33 个区
6、域分别对应着 fn_hash 结构中的 fz_zone0 到 fz_zone32 。之所以这么划分的原因就因为，路由的表的查找要从最精确到最不精确，也就是说要从掩码最长的路由项查起。 第二个层次是 fn_zone 结构。 每个 fn_zone 代表了一个区域 ，由于并不是 33 个区域都会同时存在，一般往往只有常用到的掩码长度（如 0,16,24,32 位）对应的区域才存在，所以所有存在的区域按从大到小的顺序被链成一个 list ，从而提高查找的效率。这人 fn_zone 结构中最重要的就是 fz_hash 域了，它指向了一个 hash table ，这个 hash table 组织了这个区域
7、下的所有路由项 。 第三个层次是代表 路由项 的 fn_node 结构 。它是 hash table 的结点，其中 fn_key 域即是 hash 查找的关键字，它实际上就是路由项的目标网络号。这个结构的提供了路由查找的结果信息， fn_type 这个域指示了这个路由项的含义：单播转发，本地，丢弃， NAT 等等。对于大多数情况，路由项都是单播转发类型的，这时关于 下一跳的信息就入在 fn_info 中了，它指向一个 fib_info 结构。 第四个层次即是 fib_info 结构 。因为很多的路由项具有相同的 下一跳信息 ，即 fn_node 与 fib_info 结构是多对一的关系。所以
8、fn_node 中只存放一个指向 fib_info 的指针 fn_info 。所有 fib_info 结构被单独管理，它们被组织成一个双向链表，表头为 fib_info_list 。关于下一跳的具体信息由 fib_nh 数组指示，它是一个数组意味着一个下一跳决策可以对应着多个物理的下一跳，这是 linux 支持的一个 MULITPATH 功能。 处理函数 这部分的处理函数中最为重要的就是 对路由策略数据库的查找函数 fib_lookup ，以及对单个路由表进行查找的 fn_hash_lookup 函数。 fib_lookup 的定义 : int fib_lookup (const struct
9、 rt_key * key , struct fib_result * res ) 这个函数的工作就是对整个路由策略数据库进行查找，它会在需要的时候调用 fn_hash_lookup 查找特定的路由表。函数有两个参数， key 是查找的关键字，它与路由缓存查找时的 key 是一致的。 res 是输出参数，函数返回后如果成功则在 res 存入查找结果。函数的返回值用来指示错误。 static int fn_hash_lookup (struct fib_table * tb , const struct rt_key * key , struct fib_result * res ) 3、前底端
10、接口部分主要是给用户提供的一些对路由策略数据库增删改的操作函数 这一部分主要实现以下几个功能： 1 对路由表，策略表进行增加项，删除项，创建表，表空路由缓存等操作。 2 为路由策略数据库，路由缓存提供 /proc 接口。 3 设置定时器，以定时对路由缓存进行清理工作。 （二） 路由表 与路由缓存 2.1 路由表 在 内 核 中 存 在 路 由 表 fib_table_hash 和 路由缓存表rt_hash_tablehash。 RT_SCOPE_UNIVERSE=0, /任意的地址路由 RT_SCOPE_SITE=200, /用户自定义 RT_SCOPE_LINK=253, /本地直连的路由
11、RT_SCOPE_HOST=254, /主机路由 RT_SCOPE_NOWHERE=255 /不存在的路由 RT_SCOPE_NOWHERE 表示该路由无法到达任意主机 , 也就是说到该目的地址没有路由 RT_SCOPE_HOST 表示该路由目的为本机接口 , 此类型路由为 fib_add_ifaddr 自动添加 RT_SCOPE_LINK 表示 路由目的为本地网络 RT_SCOPE_UNIVERSE 表示路由目的为其他非直连网络 , 也就是需要至少一个下一条网关 ; 路由表的物理操作主要包括如下这些函数： 路由标操作 实现函数 位置 新建路由表 删除路由表 搜索路由 fn_hash_look
12、up fib_hash.c 269 插入路由到路由表 fn_hash_insert fib_hash.c 341 删除路由表的路由 fn_hash_delete fn_hash_dump fib_hash.c 433 fib_hash.c 614 更新路由表的路由 fn_hash_flush fib_hash.c 729 显示路由表的路由信息 fn_hash_get_info fib_hash.c 750 选择默认路由 fn_hash_select_default fib_hash.c 842 路由的 scope和本地配置地址的 scope可以由用户显式指定或者由内核配置为默认值 ; 而下一跳
13、 fib_nh 的 scope 只能由 fib_check_nh 指定 ; 给定路由和它的下一跳 , 下一跳 fib_nh的 scope是用于到达该下一跳路由的 scope; 当主机转发一条报文都会使该报文跟接近最终目的 ; 因此 , 路由的 scope 必须大等于该到达下一跳路由 scope; A要发送报文给 C, A 到 C 路由的 scope 是 RT_SCOPE_UNIVERSE, 下一跳是 RT; 而 A 到 RT路由的 scope 是 RT_SCOPE_LINK u.dst, jiffies); skb_dst_set(skb, 2.3 路由缓存的创建 inet_init() -
14、ip_init() - ip_rt_init() 2.4 路由缓存插入条目 函 数 rt_intern_hash()如果新插入 rt 满足一定条件，还要与 ARP 邻居表进行绑定 Hint：缓存的每个 bucket 是没有头结点的，单向链表，它所使用的插入和删除操作是值得学习的，简单实用 。 2.5 路由缓存删除条目 rt_del() 2.6 路由表的创建 inet_init() - ip_init() - ip_fib_init() - fib_net_init() - ip_fib_net_init() 首先为路由表分配空间，这里 的每个表项 hlist_head 实际都会链 接一个单独的
15、路由表，FIB_TABLE_HASHSZ 表示了分配多少个路由表 ，一般情况下至少有两个 LOCAL 和 MAIN。注意这里仅仅是表头的空间分配，还没有真正分配路由表空间。 net-ipv4.fib_table_hash = kzalloc( sizeof(struct hlist_head)*FIB_TABLE_HASHSZ, GFP_KERNEL); ip_fib_net_init() - fib4_rules_init()，这里真正分配了路由表空间 local_table = fib_hash_table(RT_TABLE_LOCAL); main_table = fib_hash_ta
16、ble(RT_TABLE_MAIN); 然后将 local 和 main 表链入之前的 fib_table_hash 中 hlist_add_head_rcu( hlist_add_head_rcu( 最终生成结构如图， LOCAL 表位于 fib_table_hash0， MAIN 表位于 fib_table_hash1；两张表通过结构 tb_hlist 链入链表，而 tb_id 则标识了功能， 255 是 LOCAL 表， 254 是 MAIN表。 关于这里的 struct fn_hash，它表示了不同子网掩码长度的 hash 表 即 fn_zone，对于 ipv4，从 032 共 33
17、个。而 fn_hash 的实现则是 fib_table 的最后一个参数 unsigned char tb_data0。 传 入参数 z 代表掩码长度， z = 0 的掩码用于默认路由，一般只有一个，所以 fz_divisor只需设为 1；其它设为 16；这里要提到 fz_divisor 的作 用， fz-fz_hash 并不是个单链表，而是一个哈希表，而哈希表的大小就是 fz_divisor。 if (z) fz-fz_divisor = 16; else fz-fz_divisor = 1; fz_hashmask 实际是用于求余数的，当算出 hash 值，再 hash fz-fz_hash = fz_hash_alloc(fz-fz_divisor); fz-fz_order = z; fz-fz_mask = inet_make_mask(z); 从 子网长度大于新添加 fz 的 fn_zone 中挑选一个不为空的 fn_zonesi，将新创建的 fz 设成 fn_zonesi.next；然后将 fz 根 据掩码长度添加到 fn_zones中相应位置； fn_zone_list始终指向掩码长度最长的 fn_zone。
