路由表插入流程分析

1、路由表    在内核中存在路由表fib_table_hash和路由缓存表rt_hash_table。路由缓存表主要是为了加速路由的查找，每次路由查询都会先查找路由缓存，再查找路由表。这和cache是一个道理，缓存存储最近使用过的路由项，容量小，查找快速；路由表存储所有路由项，容量大，查找慢。首先，应该先了解路由表的意义，下面是route命令查看到的路由表：DestinationNetmaskGatewayFlagsInterfaceMetric*Ueth01*Ueth01defaultUGeth01    一条路由其实就是告知主机要到

2、达一个目的地址，下一跳应该走哪里。比如发往报文通过查路由表，会得到下一跳为，再将其发送出去。在路由表项中，还有一个很重要的属性-scope，它代表了到目的网络的距离。    路由scope可取值：RT_SCOPE_UNIVERSE, RT_SCOPE_LINK, RT_SCOPE_HOST    在报文的转发过程中，显然是每次转发都要使到达目的网络的距离要越来越小或不变，否则根本到达不了目的网络。上面提到的scope很好的实现这个功能，在查找路由表中，表项的scope一定是更小或相等的scope(比如RT_SCOPE_LINK，则表项

3、scope只能为RT_SCOPE_LINK或RT_SCOPE_HOST)。 路由缓存    路由缓存用于加速路由的查找，当收到报文或发送报文时，首先会查询路由缓存，在内核中被组织成hash表，就是rt_hash_table。static struct rt_hash_bucket          *rt_hash_table _read_mostly;      netipv4route.c通过

4、ip_route_input()进行查询，首先是缓存操作时，通过src_ip, dst_ip, iif,rt_genid计算出hash值hash = rt_hash(daddr, saddr, iif, rt_genid(net);此时rt_hash_tablehash.chain就是要操作的缓存表项的链表，比如遍历该链表for (rth = rt_hash_tablehash.chain; rth; rth = rth->u.dst.rt_next)因此，在缓存中查找一个表项，首先计算出hash值，取出这组表项，然后遍历链表，找出指定的表项，这里需要完全匹配src_ip, dst_ip

5、, iif, tos, mark, net，实际上struct rtable中有专门的属性用于缓存的查找键值  struct flowi。/* Cache lookup keys */struct flowi                fl;当找到表项后会更新表项的最后访问时间，并取出dstdst_use(&rth->u.dst, jiffies);skb_dst_set(skb, &rth->

6、u.dst); 路由缓存的创建inet_init() -> ip_init() -> ip_rt_init()rt_hash_table = (struct rt_hash_bucket *)         alloc_large_system_hash("IP route cache",              

7、0;                      sizeof(struct rt_hash_bucket),                      

8、0;              rhash_entries,                                 &#

9、160;   (totalram_pages >= 128 * 1024) ?                                      15 : 17, &

10、#160;                                   0,              

11、;                       &rt_hash_log,                        

12、             &rt_hash_mask,                                  

13、    rhash_entries ? 0 : 512 * 1024);其中rt_hash_mask表示表的大小，rt_hash_log = log(rt_hash_mask)，创建后的结构如图所示：  路由缓存插入条目函数rt_intern_hash()要插入的条目是rt，相应散列值是hash，首先通过hash值找到对应的bucketrthp = &rt_hash_tablehash.chain;然后对bucket进行一遍查询，这次查询的目的有两个：如果是超时的条目，则直接删除；如果是与rt相同键值的条目，则删除并将rt插入

14、头部返回。while (rth = *rthp) != NULL)          if (rt_is_expired(rth)      / 超时的条目                   *rthp = rth->u.dst.rt_next;

15、60;                  rt_free(rth);                   continue;         

16、;         if (compare_keys(&rth->fl, &rt->fl) && compare_netns(rth, rt) /重复的条目                   *rthp = rth->u.dst.rt_next;  

17、;                 rcu_assign_pointer(rth->u.dst.rt_next, rt_hash_tablehash.chain);                   rcu_assign_point

18、er(rt_hash_tablehash.chain, rth);                                            

19、60; rthp = &rth->u.dst.rt_next;在扫描一遍后，如rt还未存在，则将其插入头部rt->u.dst.rt_next = rt_hash_tablehash.chain;rcu_assign_pointer(rt_hash_tablehash.chain, rt);如果新插入rt满足一定条件，还要与ARP邻居表进行绑定Hint：缓存的每个bucket是没有头结点的，单向链表，它所使用的插入和删除操作是值得学习的，简单实用。 路由缓存删除条目rt_del()要删除的条目是rt，相应散列值是hash，首先通过hash值找到对应的buc

20、ket，然后遍历，如果条目超时，或找到rt，则删除它。rthp = &rt_hash_tablehash.chain;spin_lock_bh(rt_hash_lock_addr(hash);ip_rt_put(rt);while (aux = *rthp) != NULL)          if (aux = rt | rt_is_expired(aux)            

21、60;       *rthp = aux->u.dst.rt_next;                   rt_free(aux);                &#

22、160;  continue;                  rthp = &aux->u.dst.rt_next;spin_unlock_bh(rt_hash_lock_addr(hash);路由表的创建inet_init() -> ip_init() -> ip_fib_init() -> fib_net_init() -> ip_fib_net_in

23、it()netipv4fib_frontend.c首先为路由表分配空间，这里的每个表项hlist_head实际都会链接一个单独的路由表，FIB_TABLE_HASHSZ表示了分配多少个路由表，一般情况下至少有两个 LOCAL和MAIN。注意这里仅仅是表头的空间分配，还没有真正分配路由表空间。net->ipv4.fib_table_hash = kzalloc(         sizeof(struct hlist_head)*FIB_TABLE_HASHSZ, GFP_KERNEL);&

24、#160;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,          

25、;         &net->ipv4.fib_table_hashTABLE_LOCAL_INDEX);hlist_add_head_rcu(&main_table->tb_hlist,                   &net->ipv4.fib_table_hash

26、TABLE_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。  注意到这里fn_zone还只是空指针，我们还只完成了路由表初始化的

27、一部分。在启动阶段还会调用inet_rtm_newroute() -> fib_table_insert() -> fn_new_zone() fib_hash.c来创建fn_zone结构，前面已经讲过，fn_zone一共有33个，其中掩码长度为0/0表示为默认路由，fn_zone可以理解为相同掩码的地址集合。首先为fn_zone分配空间struct fn_zone *fz = kzalloc(sizeof(struct fn_zone), GFP_KERNEL);传入参数z代表掩码长度， z = 0的掩码用于默认路由，一般只有一个，所以fz_divisor只需设为1；其

28、它设为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就得出了在哈

29、希表的位置；而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，将新创

30、建的fz设成fn_zonesi.next；然后将fz根据掩码长度添加到fn_zones中相应位置；fn_zone_list始终指向掩码长度最长的fn_zone。for (i=z+1; i<=32; i+)         if (table->fn_zonesi)                   bre

31、ak;if (i>32)          fz->fz_next = table->fn_zone_list;         table->fn_zone_list = fz; else          fz->fz_next = table->fn_zonesi->fz_next

32、;         table->fn_zonesi->fz_next = fz;table->fn_zonesz = fz;这里的fn_hash是数组与链表的结合体，看下fn_hash定义struct fn_hash          struct fn_zone *fn_zones33;        &#

33、160;struct fn_zone *fn_zone_list;fn_hash包含33数组元素，每个元素存放一定掩码长度的fn_zone，其中fn_zonei存储掩码长度为i。而fn_zone通过内部属性fz_next又彼此串连起来，形成单向链表，其中fn_zone_list可以看作链表头，而这里链表的组织顺序是倒序的，即从掩码长到短。  到这里，fz_hash所分配的哈希表还没有插入内容，这部分为fib_insert_node()完成。inet_rtm_newroute() -> fib_table_insert() -> fib_insert_n

34、ode() netipv4fib_hash.c这里f是fib_node，可以理解为具有相同网络地址的路由项集合。根据fn_key(网络地址)和fz(掩码长度)来计算hash值，决定将f插入fz_hash的哪个项。struct hlist_head *head = &fz->fz_hashfn_hash(f->fn_key, fz);hlist_add_head(&f->fn_hash, head); 如何fib_node还不存在，则会创建它，这里的kmem_cache_zalloc()其实就是内存分配new_f = kmem_cache_zalloc

35、(fn_hash_kmem, GFP_KERNEL);if (new_f = NULL)         goto out;INIT_HLIST_NODE(&new_f->fn_hash);INIT_LIST_HEAD(&new_f->fn_alias);new_f->fn_key = key;f = new_f; 路由表最后一层是fib_info，具体的路由信息都存储在此，它由fib_create_info()创建。首先为fib_info分配空间，由于fib_

36、info的最后一个属性是struct fib_nh fib_nh0，因此大小是fib_info + nhs * fib_nh，这里的fib_nh代表了下一跳(next hop)的信息，nhs代表了下一跳的数目，一般情况下nhs=1，除非配置了支持多路径。fi = kzalloc(sizeof(*fi)+nhs*sizeof(struct fib_nh), GFP_KERNEL);设置fi的相关属性fi->fib_net = hold_net(net);fi->fib_protocol = cfg->fc_protocol;fi->fib_flags = cfg->

37、fc_flags;fi->fib_priority = cfg->fc_priority;fi->fib_prefsrc = cfg->fc_prefsrc;fi->fib_nhs = nhs;使fi后面所有的nh->nh_parent指向fi，设置后如图所示change_nexthops(fi)          nexthop_nh->nh_parent = fi; endfor_nexthops(fi)  设置fib_nh的属性，这里仅展

38、示了单一路径的情况：struct fib_nh *nh = fi->fib_nh;nh->nh_oif = cfg->fc_oif;nh->nh_gw = cfg->fc_gw;nh->nh_flags = cfg->fc_flags;然后，再根据cfg->fc_scope值来设置nh的其余属性。如果scope是RT_SCOPE_HOST，则设置下一跳scope为RT_SCOPE_NOWHEREif (cfg->fc_scope = RT_SCOPE_HOST)       

39、60;  struct fib_nh *nh = fi->fib_nh;         nh->nh_scope = RT_SCOPE_NOWHERE;         nh->nh_dev = dev_get_by_index(net, fi->fib_nh->nh_oif);如果scope是RT_SCOPE_LINK或RT_SCOPE_UNIVERSE，则设置下

40、跳change_nexthops(fi)          if (err = fib_check_nh(cfg, fi, nexthop_nh) != 0)                   goto failure; endfor_nexthops(fi)最后，将fi链入链表中，这里要注意的是所有的fib_inf

41、o(只要创建了的)都会加入fib_info_hash中，如果路由项使用了优先地址属性，还会加入fib_info_laddrhash中。hlist_add_head(&fi->fib_hash,                         &fib_info_hashfib_info_hashfn(fi);if (fi-&g

42、t;fib_prefsrc)          struct hlist_head *head;         head = &fib_info_laddrhashfib_laddr_hashfn(fi->fib_prefsrc);         hlist_add_head(&fi->fib_l

43、hash, head);无论fib_info在路由表中位于哪个掩码、哪个网段结构下，都与fib_info_hash和fib_info_laddrhash无关，这两个哈希表与路由表独立，主要是用于加速路由信息fib_info的查找。哈希表的大小为fib_hash_size，当超过这个限制时，fib_hash_size * 2(如果哈希函数够好，每个bucket都有一个fib_info)。fib_info在哈希表的图示如下：  由于路由表信息也可能要以设备dev为键值搜索，因此还存在fib_info_devhash哈希表，用于存储nh的设置dev->ifindex。cha

44、nge_nexthops(fi)          hash = fib_devindex_hashfn(nexthop_nh->nh_dev->ifindex);         head = &fib_info_devhashhash;         hlist_add_head(&nextho

45、p_nh->nh_hash, head); endfor_nexthops(fi)   上面讲过了路由表各个部分的创建，现在来看下它们是如何一起工作的，在fib_table_insert()netipv4fib_hash.c完成整个的路由表创建过程。下面来看下fib_table_insert()函数：从fn_zones中取出掩码长度为fc_dst_len的项，如果该项不存在，则创建它fn_zone的创建前面已经讲过。fz = table->fn_zonescfg->fc_dst_len;if (!fz && !(fz = fn_n

46、ew_zone(table, cfg->fc_dst_len)         return -ENOBUFS;然后创建fib_info结构，前面已经讲过fi = fib_create_info(cfg);然后在掩码长度相同项里查找指定网络地址key(如145.222.33.0/24)，查找的结果如图所示f = fib_find_node(fz, key);  如果不存在该网络地址项，则创建相应的fib_node，并加入到链表fz_hash中if (!f)   

47、;       new_f = kmem_cache_zalloc(fn_hash_kmem, GFP_KERNEL);         if (new_f = NULL)                  goto out;          INIT_HLIST_NODE(&a