路由表插入流程分析

1、路由表    在內(nèi)核中存在路由表fib_table_hash和路由緩存表rt_hash_table。路由緩存表主要是為了加速路由的查找，每次路由查詢都會(huì)先查找路由緩存，再查找路由表。這和cache是一個(gè)道理，緩存存儲(chǔ)最近使用過的路由項(xiàng)，容量小，查找快速；路由表存儲(chǔ)所有路由項(xiàng)，容量大，查找慢。首先，應(yīng)該先了解路由表的意義，下面是route命令查看到的路由表：DestinationNetmaskGatewayFlagsInterfaceMetric169.254.0.0255.255.0.0*Ueth01192.168.123.0255.255.255.0*Ueth0

2、1default0.0.0.0192.168.123.254UGeth01    一條路由其實(shí)就是告知主機(jī)要到達(dá)一個(gè)目的地址，下一跳應(yīng)該走哪里。比如發(fā)往192.168.22.3報(bào)文通過查路由表，會(huì)得到下一跳為192.168.123.254，再將其發(fā)送出去。在路由表項(xiàng)中，還有一個(gè)很重要的屬性-scope，它代表了到目的網(wǎng)絡(luò)的距離。    路由scope可取值：RT_SCOPE_UNIVERSE, RT_SCOPE_LINK, RT_SCOPE_HOST    在報(bào)文的轉(zhuǎn)發(fā)過程中，顯然是每次轉(zhuǎn)發(fā)都要使到達(dá)目的

3、網(wǎng)絡(luò)的距離要越來越小或不變，否則根本到達(dá)不了目的網(wǎng)絡(luò)。上面提到的scope很好的實(shí)現(xiàn)這個(gè)功能，在查找路由表中，表項(xiàng)的scope一定是更小或相等的scope(比如RT_SCOPE_LINK，則表項(xiàng)scope只能為RT_SCOPE_LINK或RT_SCOPE_HOST)。 路由緩存    路由緩存用于加速路由的查找，當(dāng)收到報(bào)文或發(fā)送報(bào)文時(shí)，首先會(huì)查詢路由緩存，在內(nèi)核中被組織成hash表，就是rt_hash_table。static struct rt_hash_bucket       &

4、#160;  *rt_hash_table _read_mostly;      netipv4route.c通過ip_route_input()進(jìn)行查詢，首先是緩存操作時(shí)，通過src_ip, dst_ip, iif,rt_genid計(jì)算出hash值hash = rt_hash(daddr, saddr, iif, rt_genid(net);此時(shí)rt_hash_tablehash.chain就是要操作的緩存表項(xiàng)的鏈表，比如遍歷該鏈表for (rth = rt_hash_tablehash.chain; rth;

5、rth = rth->u.dst.rt_next)因此，在緩存中查找一個(gè)表項(xiàng)，首先計(jì)算出hash值，取出這組表項(xiàng)，然后遍歷鏈表，找出指定的表項(xiàng)，這里需要完全匹配src_ip, dst_ip, iif, tos, mark, net，實(shí)際上struct rtable中有專門的屬性用于緩存的查找鍵值  struct flowi。/* Cache lookup keys */struct flowi               

6、0;fl;當(dāng)找到表項(xiàng)后會(huì)更新表項(xiàng)的最后訪問時(shí)間，并取出dstdst_use(&rth->u.dst, jiffies);skb_dst_set(skb, &rth->u.dst); 路由緩存的創(chuàng)建inet_init() -> ip_init() -> ip_rt_init()rt_hash_table = (struct rt_hash_bucket *)         alloc_large_system_hash("IP route cac

7、he",                                     sizeof(struct rt_hash_bucket),      

8、60;                              rhash_entries,                 &

9、#160;                   (totalram_pages >= 128 * 1024) ?                        &#

10、160;             15 : 17,                                   

11、  0,                                     &rt_hash_log,        

12、;                             &rt_hash_mask,                  

13、;                    rhash_entries ? 0 : 512 * 1024);其中rt_hash_mask表示表的大小，rt_hash_log = log(rt_hash_mask)，創(chuàng)建后的結(jié)構(gòu)如圖所示：  路由緩存插入條目函數(shù)rt_intern_hash()要插入的條目是rt，相應(yīng)散列值是hash，首先通過hash值找到對應(yīng)的bucketrthp

14、 = &rt_hash_tablehash.chain;然后對bucket進(jìn)行一遍查詢，這次查詢的目的有兩個(gè)：如果是超時(shí)的條目，則直接刪除；如果是與rt相同鍵值的條目，則刪除并將rt插入頭部返回。while (rth = *rthp) != NULL)          if (rt_is_expired(rth)      / 超時(shí)的條目        &#

15、160;          *rthp = rth->u.dst.rt_next;                   rt_free(rth);             &

16、#160;     continue;                  if (compare_keys(&rth->fl, &rt->fl) && compare_netns(rth, rt) /重復(fù)的條目         

17、0;         *rthp = rth->u.dst.rt_next;                   rcu_assign_pointer(rth->u.dst.rt_next, rt_hash_tablehash.chain);     

18、60;             rcu_assign_pointer(rt_hash_tablehash.chain, rth);                            &#

19、160;                 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鄰居表進(jìn)行綁定Hint：緩存的每個(gè)bucket

20、是沒有頭結(jié)點(diǎn)的，單向鏈表，它所使用的插入和刪除操作是值得學(xué)習(xí)的，簡單實(shí)用。 路由緩存刪除條目rt_del()要?jiǎng)h除的條目是rt，相應(yīng)散列值是hash，首先通過hash值找到對應(yīng)的bucket，然后遍歷，如果條目超時(shí)，或找到rt，則刪除它。rthp = &rt_hash_tablehash.chain;spin_lock_bh(rt_hash_lock_addr(hash);ip_rt_put(rt);while (aux = *rthp) != NULL)          if (au

21、x = rt | rt_is_expired(aux)                    *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(has

23、h);路由表的創(chuàng)建inet_init() -> ip_init() -> ip_fib_init() -> fib_net_init() -> ip_fib_net_init()netipv4fib_frontend.c首先為路由表分配空間，這里的每個(gè)表項(xiàng)hlist_head實(shí)際都會(huì)鏈接一個(gè)單獨(dú)的路由表，F(xiàn)IB_TABLE_HASHSZ表示了分配多少個(gè)路由表，一般情況下至少有兩個(gè) LOCAL和MAIN。注意這里僅僅是表頭的空間分配，還沒有真正分配路由表空間。net->ipv4.fib_table_hash = kzalloc(  &#

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

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

26、#160;          &net->ipv4.fib_table_hashTABLE_MAIN_INDEX); 最終生成結(jié)構(gòu)如圖，LOCAL表位于fib_table_hash0，MAIN表位于fib_table_hash1；兩張表通過結(jié)構(gòu)tb_hlist鏈入鏈表，而tb_id則標(biāo)識了功能，255是LOCAL表，254是MAIN表。 關(guān)于這里的struct fn_hash，它表示了不同子網(wǎng)掩碼長度的hash表即fn_zone，對于ipv4，從032共33個(gè)。

27、而fn_hash的實(shí)現(xiàn)則是fib_table的最后一個(gè)參數(shù)unsigned char tb_data0。  注意到這里fn_zone還只是空指針，我們還只完成了路由表初始化的一部分。在啟動(dòng)階段還會(huì)調(diào)用inet_rtm_newroute() -> fib_table_insert() -> fn_new_zone() fib_hash.c來創(chuàng)建fn_zone結(jié)構(gòu)，前面已經(jīng)講過，fn_zone一共有33個(gè)，其中掩碼長度為0/0表示為默認(rèn)路由，fn_zone可以理解為相同掩碼的地址集合。首先為fn_zone分配空間struct fn_zone *fz = kzallo

28、c(sizeof(struct fn_zone), GFP_KERNEL);傳入?yún)?shù)z代表掩碼長度， z = 0的掩碼用于默認(rèn)路由，一般只有一個(gè)，所以fz_divisor只需設(shè)為1；其它設(shè)為16；這里要提到fz_divisor的作用，fz->fz_hash并不是個(gè)單鏈表，而是一個(gè)哈希表，而哈希表的大小就是fz_divisor。if (z)          fz->fz_divisor = 16; else       &#

29、160;  fz->fz_divisor = 1;fz_hashmask實(shí)際是用于求余數(shù)的，當(dāng)算出hash值，再hash & fz_hashmask就得出了在哈希表的位置；而fz_hash就是下一層的哈希表了，前面已經(jīng)提過路由表被多組分層了，這里fz_hash就是根據(jù)fz_divisor大小來創(chuàng)建的；fz_order就是子網(wǎng)掩碼長度；fz_mask就是子網(wǎng)掩碼。fz->fz_hashmask = (fz->fz_divisor - 1);fz->fz_hash = fz_hash_alloc(fz->fz_divisor);fz->

30、;fz_order = z;fz->fz_mask = inet_make_mask(z); 從子網(wǎng)長度大于新添加fz的fn_zone中挑選一個(gè)不為空的fn_zonesi，將新創(chuàng)建的fz設(shè)成fn_zonesi.next；然后將fz根據(jù)掩碼長度添加到fn_zones中相應(yīng)位置；fn_zone_list始終指向掩碼長度最長的fn_zone。for (i=z+1; i<=32; i+)         if (table->fn_zonesi)   &#

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

32、;        fz->fz_next = table->fn_zonesi->fz_next;         table->fn_zonesi->fz_next = fz;table->fn_zonesz = fz;這里的fn_hash是數(shù)組與鏈表的結(jié)合體，看下fn_hash定義struct fn_hash       

33、60;  struct fn_zone *fn_zones33;         struct fn_zone *fn_zone_list;fn_hash包含33數(shù)組元素，每個(gè)元素存放一定掩碼長度的fn_zone，其中fn_zonei存儲(chǔ)掩碼長度為i。而fn_zone通過內(nèi)部屬性fz_next又彼此串連起來，形成單向鏈表，其中fn_zone_list可以看作鏈表頭，而這里鏈表的組織順序是倒序的，即從掩碼長到短。  到這里，fz_hash所分配的哈

34、希表還沒有插入內(nèi)容，這部分為fib_insert_node()完成。inet_rtm_newroute() -> fib_table_insert() -> fib_insert_node() netipv4fib_hash.c這里f是fib_node，可以理解為具有相同網(wǎng)絡(luò)地址的路由項(xiàng)集合。根據(jù)fn_key(網(wǎng)絡(luò)地址)和fz(掩碼長度)來計(jì)算hash值，決定將f插入fz_hash的哪個(gè)項(xiàng)。struct hlist_head *head = &fz->fz_hashfn_hash(f->fn_key, fz);hlist_add_head(&f->

35、fn_hash, head); 如何fib_node還不存在，則會(huì)創(chuàng)建它，這里的kmem_cache_zalloc()其實(shí)就是內(nèi)存分配new_f = kmem_cache_zalloc(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

36、 = key;f = new_f; 路由表最后一層是fib_info，具體的路由信息都存儲(chǔ)在此，它由fib_create_info()創(chuàng)建。首先為fib_info分配空間，由于fib_info的最后一個(gè)屬性是struct fib_nh fib_nh0，因此大小是fib_info + nhs * fib_nh，這里的fib_nh代表了下一跳(next hop)的信息，nhs代表了下一跳的數(shù)目，一般情況下nhs=1，除非配置了支持多路徑。fi = kzalloc(sizeof(*fi)+nhs*sizeof(struct fib_nh), GFP_KERNEL);設(shè)置fi的相關(guān)屬性fi-

37、>fib_net = hold_net(net);fi->fib_protocol = cfg->fc_protocol;fi->fib_flags = cfg->fc_flags;fi->fib_priority = cfg->fc_priority;fi->fib_prefsrc = cfg->fc_prefsrc;fi->fib_nhs = nhs;使fi后面所有的nh->nh_parent指向fi，設(shè)置后如圖所示change_nexthops(fi)       

38、;   nexthop_nh->nh_parent = fi; endfor_nexthops(fi)  設(shè)置fib_nh的屬性，這里僅展示了單一路徑的情況：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;然后，再根據(jù)cfg->fc_scope值來設(shè)置nh的其余屬性。如果scope是RT_SCOPE_HOST，則設(shè)置下一跳sc

39、ope為RT_SCOPE_NOWHEREif (cfg->fc_scope = RT_SCOPE_HOST)          struct fib_nh *nh = fi->fib_nh;         nh->nh_scope = RT_SCOPE_NOWHERE;         nh->nh_d

40、ev = dev_get_by_index(net, fi->fib_nh->nh_oif);如果scope是RT_SCOPE_LINK或RT_SCOPE_UNIVERSE，則設(shè)置下跳change_nexthops(fi)          if (err = fib_check_nh(cfg, fi, nexthop_nh) != 0)             &

41、#160;     goto failure; endfor_nexthops(fi)最后，將fi鏈入鏈表中，這里要注意的是所有的fib_info(只要?jiǎng)?chuàng)建了的)都會(huì)加入fib_info_hash中，如果路由項(xiàng)使用了優(yōu)先地址屬性，還會(huì)加入fib_info_laddrhash中。hlist_add_head(&fi->fib_hash,                

42、0;        &fib_info_hashfib_info_hashfn(fi);if (fi->fib_prefsrc)          struct hlist_head *head;         head = &fib_info_laddrhashfib_laddr_hashfn(fi->fi

43、b_prefsrc);         hlist_add_head(&fi->fib_lhash, head);無論fib_info在路由表中位于哪個(gè)掩碼、哪個(gè)網(wǎng)段結(jié)構(gòu)下，都與fib_info_hash和fib_info_laddrhash無關(guān)，這兩個(gè)哈希表與路由表獨(dú)立，主要是用于加速路由信息fib_info的查找。哈希表的大小為fib_hash_size，當(dāng)超過這個(gè)限制時(shí)，fib_hash_size * 2(如果哈希函數(shù)夠好，每個(gè)bucket都有一個(gè)fib_info)。fib_info在

44、哈希表的圖示如下：  由于路由表信息也可能要以設(shè)備dev為鍵值搜索，因此還存在fib_info_devhash哈希表，用于存儲(chǔ)nh的設(shè)置dev->ifindex。change_nexthops(fi)          hash = fib_devindex_hashfn(nexthop_nh->nh_dev->ifindex);         head = &fib_

45、info_devhashhash;         hlist_add_head(&nexthop_nh->nh_hash, head); endfor_nexthops(fi)   上面講過了路由表各個(gè)部分的創(chuàng)建，現(xiàn)在來看下它們是如何一起工作的，在fib_table_insert()netipv4fib_hash.c完成整個(gè)的路由表創(chuàng)建過程。下面來看下fib_table_insert()函數(shù)：從fn_zones中取出掩碼長度為fc_dst_len的項(xiàng)，如果該項(xiàng)

46、不存在，則創(chuàng)建它fn_zone的創(chuàng)建前面已經(jīng)講過。fz = table->fn_zonescfg->fc_dst_len;if (!fz && !(fz = fn_new_zone(table, cfg->fc_dst_len)         return -ENOBUFS;然后創(chuàng)建fib_info結(jié)構(gòu)，前面已經(jīng)講過fi = fib_create_info(cfg);然后在掩碼長度相同項(xiàng)里查找指定網(wǎng)絡(luò)地址key(如145.222.33.0/24)，查找的結(jié)果如圖所示f

47、= fib_find_node(fz, key);  如果不存在該網(wǎng)絡(luò)地址項(xiàng)，則創(chuàng)建相應(yīng)的fib_node，并加入到鏈表fz_hash中if (!f)          new_f = kmem_cache_zalloc(fn_hash_kmem, GFP_KERNEL);         if (new_f = NULL)                  goto out;          INIT_HLI