内核路由模块分析.doc

（一） 概述路由策略数据库（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 oif ) 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 这个策略对应的路由表，它是路由表索引表 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 unsigned 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 char tb_data0; ; fib_table 结构只是一个路由表结构中最上层的一个结构，它下面还很多的层次，下面这张图描绘了整个路由表的数据结构：第一个层次是 fib_table 和 fn_hash 结构。实际上， fn_hash 结构即是 fib_table 的 tb_data 域。这一层主要是包括一个路由表所对应的标识符 (tb_id) ，操作函数指针 (tb_looup 等 ) ，以及对所有路由项的一个总索引 (fn_hash 结构 ) 。最为重要的就是这个索引，一个路由表把它所有的路由项划分成 33 个区域，划分的原则即是子网掩码的长度（从 0 到 32 ），这 33 个区域分别对应着 fn_hash 结构中的 fz_zone0 到 fz_zone32 。之所以这么划分的原因就因为，路由的表的查找要从最精确到最不精确，也就是说要从掩码最长的路由项查起。 第二个层次是 fn_zone 结构。每个 fn_zone 代表了一个区域，由于并不是 33 个区域都会同时存在，一般往往只有常用到的掩码长度（如 0,16,24,32 位）对应的区域才存在，所以所有存在的区域按从大到小的顺序被链成一个 list ，从而提高查找的效率。这人 fn_zone 结构中最重要的就是 fz_hash 域了，它指向了一个 hash table ，这个 hash table 组织了这个区域下的所有路由项。第三个层次是代表路由项的 fn_node 结构。它是 hash table 的结点，其中 fn_key 域即是 hash 查找的关键字，它实际上就是路由项的目标网络号。这个结构的提供了路由查找的结果信息， fn_type 这个域指示了这个路由项的含义：单播转发，本地，丢弃， NAT 等等。对于大多数情况，路由项都是单播转发类型的，这时关于下一跳的信息就入在 fn_info 中了，它指向一个 fib_info 结构。第四个层次即是 fib_info 结构。因为很多的路由项具有相同的下一跳信息，即 fn_node 与 fib_info 结构是多对一的关系。所以 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 rt_key * key , struct fib_result * res ) 这个函数的工作就是对整个路由策略数据库进行查找，它会在需要的时候调用 fn_hash_lookup 查找特定的路由表。函数有两个参数， key 是查找的关键字，它与路由缓存查找时的 key 是一致的。 res 是输出参数，函数返回后如果成功则在 res 存入查找结果。函数的返回值用来指示错误。 static intfn_hash_lookup (struct fib_table * tb , const struct rt_key * key , struct fib_result * res ) 3、前底端接口部分主要是给用户提供的一些对路由策略数据库增删改的操作函数这一部分主要实现以下几个功能： 1 对路由表，策略表进行增加项，删除项，创建表，表空路由缓存等操作。 2 为路由策略数据库，路由缓存提供 /proc 接口。 3 设置定时器，以定时对路由缓存进行清理工作。（二） 路由表与路由缓存2.1 路由表在内核中存在路由表fib_table_hash和路由缓存表rt_hash_tablehash。RT_SCOPE_UNIVERSE=0, /任意的地址路由 RT_SCOPE_SITE=200, /用户自定义 RT_SCOPE_LINK=253, /本地直连的路由 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_lookupfib_hash.c 269插入路由到路由表fn_hash_insertfib_hash.c 341删除路由表的路由fn_hash_deletefn_hash_dumpfib_hash.c 433fib_hash.c 614更新路由表的路由fn_hash_flushfib_hash.c 729显示路由表的路由信息fn_hash_get_infofib_hash.c 750选择默认路由 fn_hash_select_defaultfib_hash.c 842路由的scope和本地配置地址的scope可以由用户显式指定或者由内核配置为默认值; 而下一跳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, &rth-u.dst);2.3 路由缓存的创建inet_init() - 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实际都会链接一个单独的路由表，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_table(RT_TABLE_MAIN);然后将local和main表链入之前的fib_table_hash中hlist_add_head_rcu(&local_table-tb_hlist, &net-ipv4.fib_table_hashTABLE_LOCAL_INDEX);hlist_add_head_rcu(&main_table-tb_hlist, &net-ipv4.fib_table_hashTABLE_MAIN_INDEX);最终生成结构如图，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个。而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_hashmask就得出了在哈希表的位置；而fz_hash就是下一层的哈希表了，前面已经提过路由表被多组分层了，这里fz_hash就是根据 fz_divisor大小来创建的；fz_order就是子网掩码长度；fz_mask就是子网掩码。fz-fz_hashmask = (fz-fz_divisor - 1);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。？路由表的查找效率是第一位的，因此内核在实现时使用了多级索引来进行加速：第一级：fn_zone，按不同掩码长度分类(如/5和/24)；第二级：fib_node，按不同网络地址分类(如/24)；第三级：fib_info，按下一跳路由信息。当然，我们创建路由表也要按照这个顺序。（三） Linux路由功能实现3.1 数据包流程如图4-1所示，ip_rcv是IPv4数据包的基本接收函数，由下层调用。这个函数完成一系列的校验、协议处理等等，然后进入第一个HOOK点，这是在本机路由前的点。在ip_rcv_finish函数中，会调用ip_route_input函数来进行本机路由，判断是发送给本机的，还是需要转发的，由此来知道下一处理函数是ip_local_deliver，还是ip_forward。至于ip_route_input是如何进行路由的，将在下一节进行讲解。ip_local_deliver以上，是本机数据包流程，这与路由无关，这里不做赘述。ip_forward进行一些路由的处理，比如设置网关、MTU，TTL减1等等。然后进入ip_forward_finish，根据之前设置的skb-dst-output函数来确定去处。这个output也是在之前的路由过程中确定的，具体是单播、多播、还是广播等等，视之前的路由和协议而定。3.2 数据包路由过程ip_route_input函数中，首先去路由缓存rt_ hash_table中查找，如果找到则直接返回。如果没有找到，则调用ip_route_input_slow来查找路由表。ip_route_input_slow函数中调用fib_lookup来查找。fib_lookup有两种定义，根据不同的功能编译开关。一种是只查找main表和local表，这是低级路由。另一种则会遍历rule表，先匹配应该查找哪一张路由表（可能是高级路由配置的），然后再对该表进行查询。如果查询结果是本机的数据包，则会在ip_route_input_slow函数的后面部分进行数据包路由信息的更改，最重要的是入口函数改成ip_local_deliver。然后调用rt_intern_hash函数来更新路由缓存。如果结果是需要转发的，则调用ip_mkroute_input-_mkroute_input来做进一步的处理（ip_mkroute_input中有一个分支，多路路由，这里不作介绍）。也就是把查找到的路由信息加入路由缓存，并把路由结果传递给数据包。3.3相关代码分析（四） 路由接口主要函数分析4.1 路由转发表的检索过程(fib_lookup)static inline intfib_lookup(struct net *net, const struct flowi *flp, struct fib_result *res) struct fib_table *table; table =fib_get_table(net,RT_TABLE_LOCAL); /先查LOCAL if (!table-tb_lookup(table, flp, res) return 0; table =fib_get_table(net,RT_TABLE_MAIN); /再查MAIN if (!table-tb_lookup(table, flp, res) return 0; return -ENETUNREACH;!table-tb_lookup(table, flp, res) 即fn_hash_lookupstatic intfn_hash_lookup(struct fib_table *tb, const struct flowi *flp, struct fib_result *res) int err; struct fn_zone *fz; struct fn_hash *t = (struct fn_hash *)tb-tb_data; /获得路由区队列 read_lock(&fib_hash_lock); for (fz =t-fn_zone_list; fz; fz = fz-fz_next) /扫描网络区 struct hlist_head *head; struct hlist_node *node; struct fib_node *f; _be32 k = fz_key(flp-fl4_dst, fz); /取目标地址在该网络区的网络号 fl4_det&(fz)-fz_mask) head = &fz-fz_hashfn_hash(k, fz); /fn_hash(k, fz)得到hash关键字,获得hash链头 hlist_for_each_entry(f, node, head, fn_hash) if (f-fn_key != k) /通过fn_key找到匹配的fib node节点 continue;err = fib_semantic_match(&f-fn_alias, /进入fib semantic查找 flp, res, fz-fz_order); if (err fn_alias结构 struct fib_alias *fa; int nh_sel = 0; list_for_each_entry_rcu(fa, head, fa_list) int err; if (fa-fa_tos & fa-fa_tos != flp-fl4_tos) /比较TOS continue; if (fa-fa_scope fl4_scope) /比较路由范围 scope continue; fa-fa_state |= FA_S_ACCESSED; err = fib_propsfa-fa_type.error; /取转发类型错误码,根据错误码进行特定处理 if (err = 0) /允许的转发类型 struct fib_info *fi = fa-fa_info; if (fi-fib_flags & RTNH_F_DEAD) /如果该转发节点不通 continue; switch (fa-fa_type) case RTN_UNICAST: /单目转发 case RTN_LOCAL: /本地转发 case RTN_BROADCAST: /广播转发 case RTN_ANYCAST: /任意转发 case RTN_MULTICAST: /多目转发 for_nexthops(fi) /对于转发信息中的每一个转发地址,取每个fib_nh结构 if (nh-nh_flags&RTNH_F_DEAD) continue; if (!flp-oif | flp-oif = nh-nh_oif) break; #ifdef CONFIG_IP_ROUTE_MULTIPATH /多径路由 if (nhsel fib_nhs) nh_sel = nhsel; goto out_fill_res; #else if (nhsel fa_type); return -EINVAL; return err; return 1;out_fill_res: res-prefixlen = prefixlen;/填充查询结果到了这里算是从fib中找到了路由信息 res-nh_sel = nh_sel; res-type = fa-fa_type; res-scope = fa-fa_scope; res-fi = fa-fa_info; atomic_inc(&res-fi-fib_clntref); return 0; 成功返回4.2 路由转发表的插入过程(fn_hash_insert)4.3 路由fib_create_infoprintk扩展函数功能,打印内核ipv4地址32位网络字节序整形按点分.printk（打印级别宏%pI4,ip-saddr）;附件：Linux网络编程IPv4和IPv6的inet_addr、inet_aton、inet_pton等函数小结知识背景：81属于IP地址的ASCII表示法，也就是字符串形式。英语叫做IPv4 numbers-and-dots notation。如果把81转换为整数形式，是3524887733，这个就是整数形式的IP地址。英语叫做binary data。（其实binary是二进制的意思）详细介绍，请参考：网络字节序与主机字节序的转换（一）问题所在：如何在字符串形式的IP和整数形式的IP之间转换呢？转换函数：int inet_aton(const char *cp, struct in_addr *inp); /in_atonin_addr_t inet_addr(const char *cp);in_addr_t inet_network(const char *cp);int inet_pton(int af, const char *src, void *dst);const char *inet_ntop(int af, const void *src, char *dst, socklen_t cnt);参考：http:/beej.us/guide/bgnet/output/html/multipage/inet_ntopman.html=IPv4：IP字符串 网络字节流inet_addr、inet_network、inet_aton程序代码：cpp view plaincopyprint?1. #include 2. #include 3. #include 4. #include 5. #include 6. #include 7. #include 8. 9. intmain()10. 11. charip=4;12. longr1,r2,r3;/long 13. structin_addraddr;14. 15. r1=inet_addr(ip);/返回网络字节序 16. if(-1=r1)17. printf(inet_addrreturn-1/n);18. else19. printf(inet_addrip:%ld/n,r1);20. 21. 22. r2=inet_network(ip);/返回主机字节序 23. if(-1=r2)24. printf(inet_addrreturn-1/n);25. else26. printf(inet_networkip:%ld/n,r2);27. printf(inet_networkip:%ld/n,ntohl(r2);/ntohl:主机字节序网络字节序 28. 29. 30. r3=inet_aton(ip,&addr);/返回网络字节序 31. if(0=r3)32. printf(inet_atonreturn-1/n);33. else34. printf(inet_atonip:%ld/n,addr.s_addr);35. 36. 37. /*批量注释的一种方法*/38. #if0 39. r3=inet_aton(ip,addr);40. if(0=r3)41. printf(inet_atonreturn-1/n);42. else43. printf(inet_atonip:%ld/n,ntohl(addr.s_addr);44. 45. #endif 46. 47. return0;48. 运行结果： net$ gcc -W -o inet_addr inet_addr.c net$ ./inet_addr inet_addr ip: 1241557184inet_network ip: -1062731702inet_network ip: 1241557184inet_aton ip: 1241557184-IP字符串 网络字节流inet_addr、inet_aton、inet_ntoa程序代码：cpp view plaincopyprint?1. #include 2. #include 3. #include 4. #include 5. #include 6. intmain(intargc,char*argv)7. 8. charip1=4;9. charip2=79;10. structin_addraddr1,addr2;11. longl1,l2;12. l1=inet_addr(ip1);/IP字符串网络字节 13. l2=inet_addr(ip2);14. printf(IP1:%s/nIP2:%s/n,ip1,ip2);15. printf(Addr1:%ld/nAddr2:%ld/n,l1,l2);16. 17. memcpy(&addr1,&l1,4);/复制4个字节大小 18. memcpy(&addr2,&l2,4);19. printf(%s%s/n,inet_ntoa(addr1),inet_ntoa(addr2);/注意：printf函数自右向左求值、覆盖 20. printf(%s/n,inet_ntoa(addr1);/网络字节IP字符串 21. printf(%s/n,inet_ntoa(addr2);22. return0;23. 运行结果： net$ gcc -W -o inet_ntoa inet_ net$ ./inet_ntoa IP1: 4IP2: 79Addr1: 1241557184Addr2: 30045237314 4479=IPv6：IPv4 字符串 网络字节流inet_pton、inet_ntop程序代码：cpp view plaincopyprint?1. #include 2. #include 3. #include 4. #include 5. 6. intmain()7. 8. charip=4;9. structin_addraddr;10. 11. intret=inet_pton(AF_INET,ip,(void*)&addr);/IP字符串网络字节流 12. if(0=ret)13. printf(inet_ptonerror,return0/n);14. return-1;15. else16. printf(inet_ptonip:%ld/n,addr.s_addr);17. printf(inet_ptonip:0x%x/n,addr.s_addr);18. 19. 20. constchar*pstr=inet_ntop(AF_INET,(void*)&addr,ip,128);/网络字节流IP字符串 21. if(NULL=pstr)22. printf(inet_ntoperror,returnNULL/n);23. return-1;24. else25. printf(i