Linux3.5核心以後的路由下一跳快取

在Linux3.5版本(包括)之前，存在一個路由cache，這個路由cache的初衷是美好的，但是現實往往是令人遺憾的。以下是陳列得出的兩個問題：
1.面臨針對hash演算法的ddos問題(描述該問題的文章已經汗牛充棟，不再贅述)；
2.快取出口裝置是p2p裝置的路由項會降低效能。
這些問題本質上是由於路由cache的查詢方式和路由表的查詢方式互不相容引起的。路由cache必須是精確的元組匹配，因此它必須設計成一維的hash 表，而路由表查詢演算法是最前字首匹配，因此它可以是多維的。路由查詢最終會找到路由項，在不考慮策略路由的前提下，我們來看一下把出口裝置為p2p裝置的路由項塞進路由cache是多麼的沒有意義。

p2p裝置的鄰居集合裡只有一個下一跳，那就是它的對端，因此對於p2p裝置，甚至都不需要進行鄰居系結的過程！然而如果將這類路由塞進路由cache的話，將會佔據巨量的記憶體，試想如果有10w個IP地址需要通訊，源IP集合中同樣有10w個IP地址，將有可能會建立100w條路由cache項，極端一點，如果此時系統中只有不多的幾條路由表項的話，查詢路由表的開銷可能會反而低於查詢路由cache的開銷，特別地，如果路由結果是p2p裝置，事實上只要想辦法cache這唯一的一個條目即可。這就是一和多的區別，這次，我們發現不光零到一有意義，一到多也同樣不可小覷。

如果系統中有一塊乙太網卡eth0，由於同一網段會有多個鄰居，不同的目標IP地址，其下一跳可能會有所不同，我們不得不cache每一個與eth0相關的路由項，然後針對每一個封包進行精確匹配，然而如果系統中有一塊p2p網絡卡，它的鄰居只有一個，對於對等裝置而言，其對端邏輯上只有一個裝置，它是唯一的且確定的，它是該對等裝置的鄰居集合中的唯一一個鄰居，因此事實上無需進行鄰居系結過程，只要從對等裝置將封包發出，該封包就一定會到達唯一的對端，在這種情況下，如果我們還cache每一個與該p2p網絡卡相關的路由項，意義就不大了，然而，對於Linux的路由cache機制而言，這是無法做的的，因為在查詢路由cache以及查詢路由表之前，我們無從知道這個封包就是最終要從一個p2p網絡卡傳送出去的。

一個解決方案是，如果查詢路由表的結果表明其出口裝置是p2p裝置，則設定一個NOCACHE標誌，表示不cache它，待到封包傳送完畢即釋放，我想這個實現是簡單而明瞭的，本來去年9月份想實現掉它，也是為了我們的一個閘道器產品可以提高效能，但是後面我離職了，此事也就不了了之，直到最近，我再次面臨了此問題。然而我有了更好的建議，那就是升級核心到3.6+，不過這是後話，事實上，如果你必須維護基於低版本核心的老產品的話，修改程式碼就是避不開的，幸運的是，不管是老公司，還是新公司，我與2.6.32版本的程式碼打交道已經6年了。

擴大點說，路由查詢這東西確實很尷尬，可以肯定，一台裝置上可能會有數十萬條的路由，然而與其相連的鄰居集合內的節點數卻可以用一個位元組來表示，而且大多數節點的鄰居可能只有不超過10個！我們消耗了大量的精力，什麼cache查詢，什麼最長字首匹配，最終就是為了在數十萬數量級的大海中撈出幾根針，所以說，這一直都是一個比較有挑戰性的領域，與TCP加速相比，這個領域更加閉環，它不受其它影響，只有演算法本身影響它！事實上，不光p2p裝置，就連 ethX裝置，結局也是悲哀的，設定幾十條路由，最終的下一跳可能只有五六個，p2p裝置只是更加極端一些罷了，對於p2p裝置，我們一般這麼寫路由即可：
route add -host/net a.b.c.d/e dev tunlX
然而對於ethX裝置而言，一般來說我們必須寫路由：
route add -host/net a.b.c.d/e gw A.B.C.D
也就是說，p2p裝置直接告知了封包從裝置發出去即可，然而對於ethX裝置(或者所有的廣播網路裝置以及NBMA裝置)，必須進行地址解析或者下一跳解析才會知道從哪裡發出去。不光如此，路由cache還會對鄰居子系統造成影響，簡單的說，就是路由項參照鄰居，路由項釋放之前，鄰居不能被釋放，即便 p2p裝置不需要鄰居解析，在程式碼層面也必須特殊處理，不幸的是，Linux核心中並沒有看到這種特殊處理，p2p裝置的路由項依然會塞進路由 cache。

以上就是路由查詢的困境。困境在於多對一或者多對少的對映過程，這種情況下，營造一個精確匹配的cache可能使結局更加悲哀，因此，用一種統一的方式進行調優可能更加符合人之常情。Linux3.6以後，去除了路由cache的支援，所有的封包要想傳送出去，必須查詢路由表！如今的過程可能會變成以下的邏輯：

dst=lookup_fib_table(skb);
dst_nexthop=alloc_entry(dst);
neigh=bind_neigh(dst_nexthop);
neigh.output(skb);
release_entry(dst_nexthop);這是一個完美的過程，然而在協定棧的實現層面，出現了新的問題，即 alloc/release會帶來巨大的記憶體抖動，我們知道，記憶體分配與釋放是一個必須要在CPU外部完成的事務，它的開銷是巨大的，雖然在Linux中有slab cache，但是我們同樣也知道，cache是分層的。事實上，Linux在3.6以後，實現了新的路由cache，不再快取一個路由項，因為那需要 skb的元組精確匹配，而是快取下一跳，找到這個cache必須經過lookup_fib_table這個例程。

這是個創舉，因為快取的東西是唯一的，除非發生一些例外！這就破解了解決多對一以及多對少的問題，在找到快取之前，你必須先查詢路由表，而查詢完畢之後，理論上你已經知道了下一跳，除非一些例外(再次重申！)這個新的下一跳快取只是為了避免記憶體的分配/釋放！虛擬碼如下：

dst=lookup_fib_table(skb);
dst_nexthop=lookup_nh_cache(dst);
if dst_nexthop == NULL;
then
    dst_nexthop=alloc_entry(dst);
    if dst_nexthop.cache == true;
    then
        insert_into_nh_cache(dst_nexthop);
    endif
endif
neigh=bind_neigh(dst_nexthop);
neigh.output(skb);
if dst_nexthop.cache == false
then
    release_entry(dst_nexthop);
endif就這樣，路由cache不再快取整個路由項，而是快取路由表查詢結果的下一跳。

        鑑於一般而言，一個路由項只有一個下一跳，因此這個快取是極其有意義的。這意味著，在大多數時候，當路由查詢的結果是一個確定的dst時，其下一跳快取會命中，此時便不再需要重新分配新的dst_nexthop結構體，而是直接使用快取中的即可，如果很不幸，沒有命中，那麼重新分配一個 dst_nexthop，將其盡可能地插入到下一跳快取，如果再次很不幸，沒有成功插入，那麼設定NOCACHE標誌，這意味著該dst_nexthop 使用完畢後將會被直接釋放。

        上述段落說明的是下一跳快取命中的情況，那麼在什麼情況下會不命中呢，這很簡單，無非就是在上述的lookup_nh_cache例程中返回NULL的時候，有不多的幾種情況會導致其發生，比如某種原因將既有的路由項刪除或者更新等。這個我隨後會通過一個p2p虛擬網絡卡mtu問題給予說明，在此之前，我還要闡述另外一種常見的情形，那就是重定向路由。

        所謂的重定向路由，它會更新本節點路由表的一個路由項條目，要注意的是，這個更新並不是永久的，而是臨時的，所以Linux的做法並不是直接修改路由表，而是修改下一跳快取！這個過程是非同步的，虛擬碼如下：

# IP_OUT例程執行IP傳送邏輯，它首先會查詢標準路由表，然後在下一跳快取中查詢下一跳dst_nexthop，以決定是否重新分配一個新的dst_nexthop，除非你一開始指定NOCACHE標誌，否則幾乎都會在查詢下一跳快取失敗進而建立新的dst_nexthop之後將其插入到下一跳快取，以留給後續的封包傳送時使用，這樣就避免了每次重新分配/釋放新的記憶體空間。
func IP_OUT：
    dst=lookup_fib_table(skb);
    dst_nexthop = loopup_redirect_nh(skb.daddr, dst);
    if dst_nexthop == NULL;
    then
        dst_nexthop=lookup_nh_cache(dst);
    endif
    if dst_nexthop == NULL;
    then
        dst_nexthop=alloc_entry(dst);
        if dst_nexthop.cache == true;
        then
            insert_into_nh_cache(dst_nexthop);
        endif
    endif
    neigh=bind_neigh(dst_nexthop);
    neigh.output(skb);
    if dst_nexthop.cache == false
    then
        release_entry(dst_nexthop);
    endif
endfunc

# IP_ROUTE_REDIRECT例程將建立或者更新一個dst_nexthop，並將其插入到一個連結串列中，該連結串列由封包的目標地址作為查詢鍵。
func IP_ROUTE_REDIRECT:
    dst=lookup_fib_table(icmp.redirect.daddr);
    dst_nexthop = new_dst_nexthop(dst, icmp.redirect.newnexthop);
    insert_into_redirect_nh(dst_nexthop);
endfunc
以上就是3.6以後核心的下一跳快取邏輯，值得注意，它並沒有減少路由查詢的開銷，而是減少了記憶體分配/釋放的開銷！路由查詢是繞不過去的，但是路由查詢結果是路由項，它和下一跳結構體以及鄰居結構體之間還有層次關係，其關係如下：
路由項-下一跳結構體-鄰居項
一個封包在傳送過程中，必須在路由查詢結束後系結一個下一跳結構體，然後系結一個鄰居，路由表只是一個靜態表，資料通道沒有許可權修改它，它只是用來查詢，協定棧必須用查詢到的路由項資訊來構造一個下一跳結構體，這個時候就體現了快取下一跳的重要性，因為它減少了構造的開銷！

        最後，我們可以看一下效果，如果你只是看程式碼，那麼當你看到input或者output路徑中的rt_dst_alloc呼叫時，你可能會很灰心喪氣，但是如果你使用下面的命令看一下實際結果：
watch -d -n 1 “cat /proc/net/stat/rt_cache”
的時候，你就會發現，in_slow_tot和out_slow_tot兩個欄位的計數器增加十分緩慢，甚至停滯！這意味著絕大多數的封包在接收和傳送過程中都命中了下一跳cache！如果你發現了異常，也就是說不是這種情況，它們中的其一或者兩者增長的很快??那麼可能是兩方面的原因：
1.你的核心可能沒有升級到足夠高的版本
這意味著你的核心有bug，在3.10的最初版本中，RT_CACHE_STAT_INC(in_slow_tot);的呼叫是發生在下列程式碼之前的：

if (res.fi) {
    if (!itag) {
        rth = rcu_dereference(FIB_RES_NH(res).nh_rth_input);
        if (rt_cache_valid(rth)) {
            skb_dst_set_noref(skb, &rth->dst);
            err = 0;
            goto out;
        }
        do_cache = true;
    }
}

rth = rt_dst_alloc(net->loopback_dev,
          IN_DEV_CONF_GET(in_dev, NOPOLICY), false, do_cache);
...也就是說它遺留了路由cache存在的年代的程式碼，錯誤的將下一跳快取當成了路由cache！只需要將RT_CACHE_STAT_INC(in_slow_tot)移植到rt_dst_alloc之後即可。
2.你可能使用了p2p裝置，但是並沒有正確的設定MTU
我們知道ipip隧道裝置在Linux上是一個虛擬網絡卡裝置，封包要真正傳送出去要經過重新封裝一個IP頭部的過程，如果最終是經由ethX傳送資料，其 MTU預設是1500，如果ipip隧道裝置的MTU也是1500或者小於1500減去必要頭部開銷的話，就到導致重新更新MTU的操作，而一個下一跳快取中包含MTU資訊，如果MTU需要重新更新，就意味著下一跳快取需要更新。

在一般的物理裝置中，這不是問題，因為往往在IP層傳送資料前，MTU就是已經確知的，但是對於ipip隧道裝置而言，在資料傳送的時候，協定棧在實際往隧道傳送資料前並不知道最終封包需要再次封裝，因此也就對MTU過大導致資料無法傳送這件事不知情，特別是遇到gso，tso這種情況，事情會更加複雜。此時我們有兩個解決方案：
1).適當調低ipip隧道的MTU值，保證即使經過再次封裝，也不過長度過載。這樣就不會導致重新更新MTU進而釋放更新下一跳cache。
2).從程式碼入手！
根據程式碼的rt_cache_valid來看，不要讓下一跳快取的標誌變成DST_OBSOLETE_KILL即可，而這也是和MTU相關的，而在 __ip_rt_update_pmtu中，只要保證下一跳快取的初始mtu不為0即可，這可以加入一個判斷，在rt_dst_alloc之後，初始化 rth欄位的時候：

if (dev_out->flags&(IFF_LOOPBACK|IFF_POINTOPOINT))
    rth->mtu = dev_out->mtu;
else
    rth->mtu = 0;經過測試，效果良好！

BTW,和很多的安全協定一樣，路由表項以及下一跳快取也使用了版本號來管理其有效性，只有表項的ID和全域性ID一致的時候，才代表該表項有效，這簡化了重新整理操作，當重新整理發生的時候，只需要遞增全域性版本號ID即可。

現在，可以總結一下了。在Linux3.6以後，路由cache被去除了，取而代之的是下一跳快取，這裡面有很多的蹊蹺，比如有重定向路由的處理等... 這主要是有效減少了記憶體管理的開銷而不是查詢本身的開銷。在此要說一下記憶體的開銷和查詢的開銷。二者並不是一個層次的，記憶體的開銷主要跟記憶體管理資料結構以及體系結構有關，這是一個複雜的範疇，而查詢的開銷相對簡單，只是跟演算法的時間空間複雜度以及體系結構相關，然而為什麼用查詢的開銷換記憶體的開銷，這永遠是一個無解的哲學問題！

本文永久更新連結地址：http://www.linuxidc.com/Linux/2016-03/129014.htm