内核路由模块分析.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_data[0];
};
fib_table 结构只是一个路由表结构中最上层的一个结构，它下面还很多的层次，下面这张图描绘了整个路由表的数据结构：
第一个层次是 fib_table 和 fn_hash 结构。实际上， fnhash 结构即是 fib_table 的 tb_data 域。这一层主要是包括一个路由表所对应的标识符 (tb_id) ，操作函数指针 (tb_looup 等 ) ，以及对所有路由项的一个总索引 (fn_hash 结构 ) 。最为重要的就是这个索引，一个路由表把它所有的路由项划分成 33 个区域，划分的原则即是子网掩码的长度（从 0 到 32 ），这 33 个区域分别对应着 fn_hash 结构中的 fz_zone[0] 到 fz_zone[32] 。之所以这么划分的原因就因为，路由的表的查找要从最精确到最不精确，也就是说要从掩码最长的路由项查起。
第二个层次是 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_hashlookup 查找特定的路由表。函数有两个参数， key 是查找的关键字，它与路由缓存查找时的 key 是一致的。 res 是输出参数，函数返回后如果成功则在 res 存入查找结果。函数的返回值用来指示错误。
static int　fn_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_table[hash]。
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_lookup
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可以由用户显式指定或者由内核配置为默认值; 而下一跳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 < RT_SCOPE_UNIVERSE;
A要发送报文给A, A到A路由的scope是RT_SCOPE_HOST, 下一条为空, scope是RT_SCOPE_NOWHERE;
路由结束条件是路由查找的结果返回RT_SCOPE_HOST或者RT_SCOPE_LINK; RT_SCOPE_HOST表示目的地址是本机; RT_SCOPE_LINK表示目的地址与本机直连, 可以通过L2协议进行发送;

2.2 路由缓存
因 此，在缓存中查找一个表项，首先计算出hash值，取出这组表项，然后遍历链表，找出指定的表项，这里需要完全匹配[src_ip, dst_ip, iif, tos, mark, net]，实际上struct rtable中有专门的属性用于缓存的查找键值– struct flowi。

当找到表项后会更新表项的最后访问时间，并取出dst
dst_use(&rth->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_hash[TABLE_LOCAL_INDEX]);
hlist_add_head_rcu(&main_table->tb_hlist,
                  &net->ipv4.fib_table_hash[TABLE_MAIN_INDEX]);
最终生成结构如图，LOCAL表位于fib_table_hash[0]，MAIN表位于fib_table_hash[1]；两张表通过结构tb_hlist链入链表，而tb_id则标识了功能，255是LOCAL表，254是MAIN表。
关于这里的struct fn_hash，它表示了不同子网掩码长度的hash表[即fn_zone]，对于ipv4，从0~32共33个。而fn_hash的实现则是fib_table的最后一个参数unsigned char tb_data[0]。

传 入参数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_zones[i]，将新创建的fz设成fn_zones[i].next；然后将fz根 据掩码长度添加到fn_zones[]中相应位置；fn_zone_list始终指向掩码长度最长的fn_zone。

？？？？？？

路由表的查找效率是第一位的，因此内核在实现时使用了多级索引来进行加速：
第一级：fn_zone，按不同掩码长度分类(如/5和/24)；
第二级：fib_node，按不同网络地址分类(如124.44.33.0/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 int fib_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_lookup
static int
fn_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_hash[fn_hash(k, fz)];            
//fnhash(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 <= 0)
                    goto out;
          }
     }
     err = 1;
out:
     read_unlock(&fib_hash_lock);
     return err;
}

int fib_semantic_match(struct list_head *head, const struct flowi *flp,
          struct fib_result *res, int prefixlen) //这里head是f->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 < flp->fl4_scope)         //比较路由范围 scope
               continue;

          fa->fa_state |= FA_S_ACCESSED;

          err = fib_props[fa->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 < fi->fib_nhs) {
                         nh_sel = nhsel;
                         goto out_fill_res;
                    }
#else
                    if (nhsel < 1) {       //非多径路由转发地址编号必须小于1
                         goto out_fill_res;             跳转
                    }
#endif
                    endfor_nexthops(fi);
                    continue;

               default:
                    printk(KERN_WARNING "fib_semantic_match bad type %#x\n",
                         fa->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_info

printk扩展函数功能,打印内核ipv4地址32位网络字节序整形按点分...

printk（打印级别宏"%pI4",ip->saddr）;
附件：
Linux网络编程IPv4和IPv6的inet_addr、inet_aton、inet_pton等函数小结
知识背景：
210.25.132.181属于IP地址的ASCII表示法，也就是字符串形式。英语叫做IPv4 numbers-and-dots notation。
如果把210.25.132.181转换为整数形式，是3524887733，这个就是整数形式的IP地址。英语叫做binary data。（其实binary是二进制的意思）
详细介绍，请参考： 网络字节序与主机字节序的转换 

（一）问题所在：
如何在字符串形式的IP和整数形式的IP之间转换呢？
转换函数：
int inet_aton(const char *cp, struct in_addr *inp); //in_aton
in_addr_t inet_addr(const char *cp);
in_addr_t inetnetwork(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. int main()  
10. {  
11.     char ip[] = "192.168.0.74";  
12.     long r1, r2, r3;  //long   
13.     struct in_addr addr;  
14.   
15.     r1 = inet_addr(ip); //返回网络字节序   
16.     if(-1 == r1){  
17.         printf("inet_addr return -1/n");  
18.     }else{  
19.         printf("inet_addr ip: %ld/n", r1);  
20.     }  
21.       
22.     r2 = inet_network(ip);    //返回主机字节序   
23.     if(-1 == r2){  
24.         printf("inet_addr return -1/n");  
25.     }else{  
26.         printf("inet_network ip: %ld/n", r2);   
27.         printf("inet_network ip: %ld/n", ntohl(r2));   //ntohl: 主机字节序 ——> 网络字节序   
28.     }  
29.       
30.     r3 = inet_aton(ip, &addr);  //返回网络字节序   
31.     if(0 == r3){  
32.         printf("inet_aton return -1/n");  
33.     }else{  
34.         printf("inet_aton ip: %ld/n", addr.s_addr);  
35.     }  
36.   
37. /*****  批量注释的一种方法  *****/  
38. #if 0     
39.     r3 = inet_aton(ip, addr);  
40.     if(0 == r3){  
41.         printf("inet_aton return -1/n");  
42.     }else{  
43.         printf("inet_aton ip: %ld/n", ntohl(addr.s_addr));  
44.     }  
45. #endif   
46.   
47.     return 0;  
48. }  

运行结果：
[work@db-testing-com06- net]$ gcc -W -o inet_addr inet_addr.c
[work@db-testing-com06- net]$ ./inet_addr                    
inet_addr ip: 1241557184
inet_network ip: -1062731702
inet_network ip: 1241557184
inet_aton ip: 1241557184 

--------------------------------------------------------------------------

IP字符串 《——》 网络字节流
inet_addr、inet_aton、inet_ntoa

 程序代码：
[cpp] view plaincopyprint?
1. #include    
2. #include    
3. #include    
4. #include    
5. #include    
6. int main(int argc