vpp路由模塊分析

概述

vpp作為一款優秀的高性能數據包轉發框架，對於性能出眾的原因，大家往往了解到的是其採用矢量化的報文處理思路極大的提高對cache的友好性，實際上除了這一點，還有一個比較複雜但是對轉發效率有關鍵影響的模塊，那就是路由模塊。路由模塊設計比較複雜，深入學習、分析、填坑，一方面是能夠更好的掌控，另外一方面作為最核心的模塊，其蘊含著對於報文轉發過程本質的一些思考，分析、學習對NFV研發很有意義。

vpp 路由框架理論基礎

vpp的路由框架設計有一個理論支撐，那就是CEF(Cisco ExpressForwarding);參見：

https://www.cisco.com/c/dam/global/fr_ca/assets/presentations/MPLS/Router_Architecture_And_IOS_Internals.pdf

該連結的文章圖文並茂，通俗易懂，非常詳細的說明了思科的路由設計思路。筆者就是通過該篇文章入門vpp的路由模塊的。為了方便後續說明，結合筆者的理解對該篇文章的關鍵點通過問答方式總結如下：

報文轉發的本質是什麼？

報文轉發的本質是通過三層頭的目的ip查找二層封裝信息及其出接口；

如何快速的進行報文的路由查找轉發？

通常情況下，報文轉發的關鍵流程如下：

1）以目的ip為key，查找路由表，得到value為下一跳信息nexthop和出接口；

2）以nexthop為key，查找arp表，獲得nexthop的mac地址信息；CEF為了一般化，將其稱之為rewrite string。

3）經過上述兩步查找操作，轉發報文的必需條件已滿足，使用上述生成的二層信息（rewrite string）填充在原始3層報文的頭部將報文放進出接口的發送隊列，由網卡完成發送；

通過上述分析，為了快速的完成報文轉發，在第一步完成查找時，實際上可以緩存查找的結果，即直接記錄映射關係：目的ip <--> 下一跳mac地址，這樣當下一個報文進入轉發時，可以直接從緩存中查找，如果查到直接轉發；思科將這種方案稱之為 Fast Switching

CEF是否採用上述Fast Switching提高轉發性能的策略呢？

沒有；原因是，如果採用緩存策略，那麼必然涉及到緩存老化問題，如何設計老化策略是個難題；（此處文章中實際還列舉了其它的問題，例如：二層信息及其路由表更新要強制刷新緩存和等待cpu再次構建緩存等，但是筆者認為這不是主要原因，因為這些工作是無法避免的，即使提出的CEF方案也不例外）；

什麼是CEF？

CEF提出使用兩張表來組織路由， 第一：路由表(route table)；第二：轉發表(switching table);筆者認為，與Fast Switching方案相比，其實思路是一樣的，switching table也可以看做是轉發麵使用的一個緩存，與Fast Switching不同的是，CEF的路由表和轉發表是直接關聯的（即一個路由表有且僅只有一個轉發表對於對應，且轉發表記錄的是路由表迭代處理的最終結果）；此外，vpp處理非常細緻，一方面將路由按照來源進行分類，不同來源的路由條目有不同的優先級；另一方面也為路由賦予了類型的概念（後面小節將進行詳細說明），這就會引出一個問題，配置一條路由其實需要一定量的計算，讓轉發麵去處理這些工作顯然是不合適的，所以vpp在轉發麵採用Mtrie這種數據結構來記錄上述計算的最終結果，具體計算的過程呢，當然就是圍繞著路由表展開的。

一些概念說明

從CEF理論可知，報文轉發的本質是切換二層頭信息（mac地址），所以路由解析的實質就是如果將待轉發報文的目的ip映射到二層目的mac，及其出接口，目的mac確保報文可以到達下一跳設備，出接口一方面指明了報文從哪個接口發出，另一方面也知道了如何填充源mac；上述是站在報文的解析與封裝的角度看，那麼vpp裡面如何將上述過程運轉起來呢？vpp裡面承載報文轉發的對象是node圖，這個node圖可以是靜態註冊的，也可以是在運行時動態構建的，路由解析的結果最終會反應到node之間的連接關係上，如下圖(路由解析)圖中，ip4-lookup節點執行路由查找動作，ip4-rewrite節點執行填充二層頭信息的動作，error_drop節點執行報文丟棄動作。從圖中可以看出，若路由成功解析，那麼在ip4-lookup節點將報文遞交給ip4-rewrite節點， 若路由解析失敗, 那麼會直接將報文遞交給error_drop節點將報文直接丟棄；此外，可以想到，ip4-rewrite節點填充的二層信息包含在ip4-lookup執行的結果裡面，vpp裡面將在這個結構抽象為：ip_adjacency_t。

一條路由配置主要包括三部分：1）prefix；2）表項所在的路由表；3）路徑；對於路徑部分，vpp也做了分類：attached/attached-nexthop/rr。這幾個概念從英文看比較抽象，對比說明如下：

路由若成功解析，最終必然得到兩個最重要的信息，第一是dstmac，第二是出接口，一定程度出接口應該比dstmac更加重要，因為沒有出接口，設備是無法知道究竟從那個埠送出報文；那麼在配置路由時是否可以直接為prefix指定出接口信息呢？當然可以，而且路由如果這麼配置的話，那麼這條路徑就是attached，如下：

ip route add 1.1.1.0/24 table 0 via gre0                                                                                                                                  
上面這條命令為prefix 1.1.1.0/24配置了一條路徑(vpp中稱之為fib_path_t)：via gre0, 即命中1.1.1.0/24的流量通過gre0這條隧道轉發即可（出接口為隧道接口的場景後面會詳細說明）；
那麼什麼是attached-nexthop呢？看這條命令：
ip route add 1.1.1.0/24 table 0 via 172.168.0.2 via xeth0                                                                                                                     
注意：via 172.168.0.2 via xeth0 這是一條path，這條path中指定了nexthop（172.168.0.2），這種path稱之為attached-nexthop。
為什麼有attached和attached-nexthop的分類呢？attached實際上是指約束了prefix和xeth0接口上的ip在一個子網內，即要到達prefix，直接使用報文的dstip構建arp-request報文通過xeth0發出後就能學到dstip的mac地址；attached-nexthop是指prefix和xeth0接口上的ip不在一個子網內，那麼到達prefix需要增加一跳nexthop，當然nexthop和xeth0的ip在一個二層域內。
此外，一般情況下（vpp目前的實現），如果接口是三層接口（例如gre0，即報文從該接口發出時不需要填充二層信息），這種情況下，配置路由路徑時可以直接配置出接口為三層接口；如果接口是二層接口，那麼這種情況下，一般要配置nexthop，除非prefix和xeth0連接的對端在同一個2層域內；
還有一個path類型：route recursive簡稱rr，還是用例子說明：
ip route add 1.1.1.0/24 table 0 via 2.2.2.2 ip route add 0.0.0.0/0 table 0 via 172.168.0.2 xeth0                                                                                                                           
如上面：path：via 2.2.2.2 沒有顯式指定出接口，到prefix1.1.1.0/24 的流量需要通過2.2.2.2轉發，那麼2.2.2.2又如何到達呢，這就需要迭代計算了，已經配置了默認路由，那麼通過默認路由可以得知如何到達2.2.2.2， 那麼就間接的學習到了到達prefix 1.1.1.0/24的路徑。想想前面提到過的一點，路由查找的本質，第一獲得出接口，第二獲取nexthop的mac，而且第一條甚至比第二條更加重要，因為不知道出接口如何學習到nexthop的mac呢。再來看rr類型的路由的本質：那就是在配置路由時沒有指定出接口，這時這條路由需要進一步計算一下得到出接口信息，那麼這種類型的路由就稱之為rr類型路由。這是vpp裡面處理較為複雜的地方。
上述這幾種路由path的類型都有與之對應的路由類型，即這條路由的path是attached， 那麼就說這個路由表表項是attached。
此外代碼裡面還有一個名詞：connected路由類型，這個是用來描述路由表項的類型的，並沒有與之對應的connected類型的path存在。如何配置connected類型的路由呢？我們知道，當在接口上配置ip地址時，需要在接口綁定的路由表中導出路由，vpp將這種路由標識為connected類型。為什麼這麼定義，可以暫且不用追究，因為源碼中真正用到這個含義的地方很少，只知道這麼用並不影響整體的理解。
路由源是指進入路由表的表項從何而來。通常我們關心的來源有如下：
配置一條靜態attached/attached-nexthop路由
靜態或者動態配置一條arp
這種情況下會將配置的ip作為32位的精細路由添加進路由表。
接口上配置ip地址
例如：接口上配置一個ip：192.168.1.10/24；會在路由表中添加兩條關鍵路由：192.168.1.10/32；192.168.1.0/24；
創建隧道接口或者配置rr類型的路由
vpp裡面創建隧道接口時會指定隧道的srcip和dstip，會添加一條到dstip的精細路由；
路由有不同的來源，那麼若不同的源在配置路由時設置相同的prefix但是路徑不一樣，那麼流量在轉發時應該採用哪個源的path呢？這就涉及到優先級了。vpp的處理方式是對上述的路由來源做了明確的區分和管理（fib_entry_src_t)，對不同來源的路由設置了靜態的優先級。
這個概念也是雖比較抽象，但是實際還是容易理解的，看下面的prefix：
   prefix1: 0.0.0.0/0   prefix2: 1.1.0.0/16                                                                                                                                                                 prefix3: 1.1.1.0/24   prefix4: 1.1.1.1/32
可以看到：prefix1~4，這幾個prefix依次更加精細，那麼我們可以說：
prefix1 cover prefix2  或者：prefix2 is been covered by prefix1
prefix2 cover prefix3  或者：prefix3 is been covered by prefix2
...
想像一下，當沒有配置到1.1.1.1/32的精細路由或者原來配置的path被刪除時，1.1.1.1/32可以繼承其cover 1.1.1.0/24的path，使用1.1.1.0/24的path完成流量轉發，若1.1.1.0/24被刪除了，那麼可以使用次精細的路由1.1.1.0/16 ...
vpp為了實現上述的功能，維護路由表項之間的cover與covered關係。當前vpp的實現中，要完全支持上述的功能的，需要在配置路由entry時，設置上FIB_ENTRY_SRC_FLAG_INHERITED
或者
FIB_ENTRY_FLAG_COVERED_INHERIT。
針對NFV的場景，是不需要做到如此複雜的關聯的。
但是，類似1.1.1.1/32這種精細prefix是需要建立cover關係的；
例如：在創建一個隧道接口時，會隱式創建一條到dstip的精細路由，這條路由是RR類型的，即需要迭代計算的，在這個過程中會找到次精細路由的path並繼承，這樣完成精細路由的解析，當次精細路由刪除時，可以通過cover-track機制找到次次精細（或最後迭代到默認路由0.0.0.0/0）。
這個是另個一個vpp引入的比較抽象和複雜的概念，為了說明這個概念，首先要了解vpp裡面路由表和接口的關係。
接口的概念在vpp裡面是非常重的，接口作為流量流入流出的關鍵驛站，vpp的很多功能都是基於接口這個抽象來完成的，比如feature。接口可以是隧道接口（gre/vxlan)，vlan子接口, 物理網卡，loopback。所有的接口都可以綁定一張路由表，且只可以綁定一張路由表。為什麼要綁定路由表呢，可以想到，如果不綁定路由表，當在接口上配置一個ip地址時，導出的路由表項應該添加到哪個路由表裡面呢？此外，若流量從接口流入，那麼應該查找哪個路由表完成轉發呢？所以只有綁定了路由表，接口上配置ip導出的路由表項才有棲身之地，流入接口的流量才有轉發策略。解釋清楚接口和路由表的關聯關係後，我們再看什麼是import/export, 考慮如下的配置：
1. set interface ip table xeth0 10             2. ip route add 1.1.0.0/16 table 10 via xeth0                                                                                                           3. ip route add 2.2.2.0/24 table 10 via 1.1.1.1                                                                                                             4. ip route add 1.1.0.0/16 table 11 via xeth0                                                                                                   
第1命令為xeth0接口綁定了路由表10；
第2,3條命令在路由表10中添加了一條路由，但是注意第3條命令還會隱式的增加一條RR類型的路由1.1.1.1/32, 而且這條路由會被1.1.0.0/16個fib_entry cover；
第4條命令在路由表11中添加了一條路由，但是需要注意的是，這條路由的路徑和第2條路由的路徑是一樣的，都為"via xeth0"，就是說xeth0上本來綁定的路由表為10，但是現在路由表11也引用了xeth0這個接口，那麼針對第4條路由配置，vpp會進行如下處理：
首先在路由表11中創建prefix 為 1.1.0.0/16的fib_entry, 然後解析path並安裝;
因為xeth0綁定的接口為10，與當前的路由表11不同，所以設置該路由entry的標誌位: FIB_ENTRY_FLAG_IMPORT；
使用prefix 1.1.0.0/16查找路由表10，獲得一個路由表項1.1.0.0/16，然後導入路由表10中被該路由表項覆蓋的其它路由表項，此處為：1.1.1.1/32.
從上述過程可以推測出這麼操作的理由，雖然在接口xeth0上綁定了table10路由表，但是並不代表xeth0隻能做為table10這張路由表中路由條目的path，xeth0還可以做為其它路由表（例如此處的table11）中表項的path，一旦這麼做了（例如第4條命令），我們可以想像既然table11中到達prefix 1.1.0.0/16的path為xeth0，那麼更進一步，我們何不在table10中去查一下看prefix 1.1.0.0/16的路由是否已經存在，如果存在且還有一堆被其cover的小弟，那麼乾脆把這一對小弟也import進來吧，這樣省的在table11中再次增加了。
從上述流程也可以看出，這個處理過程是很複雜的。但是在SDN場景實際是不需要的，因為SDN最重要的一點就是要做到路由隔離，vpp裡面沒有構建由多個路由表組成一個VRF這種模型，那麼如果簡單的將路由表作為VRF隔離不同租戶的流量的話，顯然是不需要上述這種跨VRF進行路由的導入和導出，否則就達不到隔離的目的了。
路由關鍵數據結構梳理
上述說明了vpp路由模塊相關的一些概念，下面進一步具體化，考察路由模塊具體的實現。分析實現，先看骨架，即關鍵數據結構的組織。
備註：下面的分析基於的vpp的開源版本為：19.01
根據CEF理論，首先看路由表和轉發表，vpp組織如下圖：
路由表和轉發表
如上圖，對於路由表，vpp將路由表項按照prefix長度（0-32）進行劃分，每
一種prefix長度創建一張hash表，當配置路由時，將按照prefix的長度，存儲到相應的hash表中。這張路由表由fib_entry_by_dst_addresss這個欄位引用。
對於轉發表，如圖中的ip4_fib_mtrie_t這個欄位，轉發表組織為mtrie結構，32bit的ip地址可以切片為8-8-8-8或者16-8-8，上面圖示的是8-8-8-8的情況，這個查找過程非常類似mmu頁表查找過程。
此外，配置路由時，路由表項先進入路由表，然後在路由表中完成路由解析，然後將結果安裝在轉發表中，這個過程由上述的紅色虛線示意。
上述說明了路由表和轉發表的組織，下面再看路由表中的路由表項是如何組織的。如下圖：
如上圖，以一條配置為入口，圖示了配置條目中的關鍵欄位是如何被vpp組織和管理的。此外，需要注意上述數據結構中都嵌入一個fib_node_t這個結構，這個結構是一個連接端子，靠這個連接端子，vpp可以將相同或不同類型的數據結構連接起來，形成一個複雜的關聯網絡，這樣方便實現通知機制（一個結構狀態變化要通知到與其關聯的其他結構）。
圖中數據結構解釋如下：
fib_entry_t
該結構是路由表表項的抽象，根據前面提出，vpp裡面對路由來源做了區分，所以在該表項中還要記錄是那個源貢獻這個表項，這個記錄欄位就體現在fe_srcs這個數組中，這個數組裡面每一項就代表一個源，目前主要關心的源如下：
1) API:  指通過vpp提供的vapi創建的路由；
2) CLI：指通過vpp提供的命令行接口創建的路由；
3) interface：指在接口上配置ip地址引入的路由；
4) adj：指配置靜態或動態arp表項引入的路由；
5) rr：指因沒有配置出接口，需要進一步迭代解析的路由；
此外上圖中還示意了fe_delegates這個數組，想想前面提到的路由cover/covered/import/export的概念，這個欄位就是用來管理上述的關聯關係的。
fib_entry_src_t
該結構是對路由源的抽象，如圖中所示，不同的源有一些特定的源信息，這個體現在數據結構中的union欄位中。這個源貢獻的路徑保存在哪？就是圖中fes_pl這個欄位。
fib_path_t
該結構是對一條路徑的抽象，前面提到過，路徑也是分類型的，所以如上圖，這個結構中也有union結構，包括了不同類型路徑包含的信息。
fib_path_list_t
該結構是fib_path_t的一個集合，因為要支持路由多路徑，所以該結構是一個鍊表，每個元素類型為fib_path_t，表示到達該prefix的一條路徑；
fib_path_list_db
該結構是fib_path_list_t的一個資料庫（採用hash表實現）。因為不同的prefix的路徑可能是相同的，所以路徑實際上是所有prefix共享的，這樣一方面節省了存儲空間（不需要為每個prefix存儲其路徑信息）；另一方面，當路徑信息更新時也可以反向通知到所有與該條路徑關聯的路由表項；
上述說明了一個路由表項涉及到的結構，本節說明路由表項之間的關聯關係涉及到的數據結構。
如上圖，fib_entry_t結構中的fe_delegates數組是用來記錄與該路由表項相關聯的數據結構，這個數組也保存了好幾種類型的關聯關係：
cover/covered關聯：fib_entry_delegate_t結構裡面的fd_list是一個fib_entry_t數據結構的鍊表頭，該鍊表記錄了被此fib_entry_t cover的所有的路由表項；
import/export關聯：這個關聯關係相對比較複雜，如前文所述，如果在創建路由時設置了FIB_ENTRY_FLAG_IMPORT標誌，且該條路由path指定的出口庫綁定的路由表和當前要添加進的路由表不一致，那麼就是執行import這個動作，執行import後的效果如上圖。圖中，import fib_entry創建完成後，會去從另外一張路由表中import被當前prefix cover的其它路由表項，import fib_entry中的fib_ae_import_t這個數據結構記錄了所有import的路由表項；同時在export fib_entry中也創建了一個數據結構fib_ae_export_t，這個結構記錄了n個fib_ae_import_t結構，表示那些fib_entry從自己這導入了路由。這樣整個cover/covered/import/export的關聯關係就建立起來了。
上述了主要說明了路由表現在被解析前的數據結構，下面說明路由表項解析完成後與轉發麵的數據結構的關聯。同樣圖示如下：
路由安裝
前文路由解析小節已經說明路由解析成功與否對於vpp轉發麵來說意味著node之間的連接狀態（ip4-lookup -> ip4-rewrite或者error-drop），那麼這個連結是如何體現的呢？vpp裡面有另一個關鍵數據結構dpo，這個數據結構承上啟下，起著連接兩個node作用，同時通過這個結構還可以查到轉發報文所需的所有信息（比如：nexthop的mac地址等）那麼可以猜到，路由解析就是構建一個這樣的數據結構，並與mtrie關聯起來，這樣流量轉發的路徑就鋪設完畢了。
具體數據結構關聯如上圖所示，路徑fib_path_t解析的結果為一個ip_adjacency_t，將其封裝成一個dpo後存儲在欄位fp_dpo中，考慮到可能存在多個路徑，所以每一條路徑都會對應一個dpo。當所有的path都完成解析後，將path的dpo搜集在一起，存儲在一個叫load_balance_t的數據結構中（具體如圖，該數據結構有一個bucket數組，將dpo依次放入這個數組）。此外，在fib_entry_t的fe_lb記錄load_balance_t數據結構的索引（註：此處說索引，這是vpp的一個編程範式，可以簡單理解為只要通過這個索引就可以找到這個數據結構），這樣fib_entry_t與轉發麵的關聯也建立起來了。

路由配置流程分析
前面一節解釋了路由模塊的關鍵數據結構，這是靜態的，本節介紹路由的創建流程，即路由模塊的動態處理流程。如下使用api配置一條路由：
ip route add 192.168.0.0/24 table 0 via 192.168.10.1 xeth1
vpp路由模塊源碼中已經包含了調試信息，我們抓取上述路由配置時路由模塊的debug信息，從裡面可以看出路由配置的步驟，當了解了一個大致的配置流程後，再對比閱讀源碼，應該就可以更加清晰的理解配置流程。
配置一條路由debug輸出的信息要遠多於上圖中顯示的，此處為了抓住主要流程，已經刪除了一些不太重要的信息。
圖中用紅色框圈住的欄位表示vpp主要的處理動作，例如alloc/create...
標號將日誌按照塊進行了分類，每一個塊實現了一個階段的配置，下面依次按照標號進行說明：
1.  按照上述的配置命令，創建該條路由對應的path機器路由entry
1.1 分配path_list（index為23）並進行解析（注意此時的解析完成實現的狀態是：將ip4-lookup節點與arp-ipv4節點連接起來），將path_list結構插入DB中。
1.2 激活這個源並安裝到轉發麵中；
2.  上述的配置命令是一條attached-nexthop類型的路徑，這其實隱含一條到nexthop的精細路由，所以此處也要添加進路由表
2.1 同樣的流程，創建這條精細路由的path_list（index為21），注意這個地方path雖然與步驟1中的path是一致的，但是vpp還是分配了同樣的結構進行了保存，為什麼不復用上述步驟1中的path_list呢？原因是，一般情況下當增加一條精細路由時，vpp會按照special的方式去對待，其path是不會採用shared方式去生成，而是創建一個私有的保存起來。
2.2 執行cover-trace計算，因為此處創建一條精細路由，所以該精細路由可能會被子網路由cover，所以此處進行關聯計算，圖中計算的結果為被接口源（接口上配置了24位掩碼ip地址，導出了一個子網路由）子網路由（index為17）覆蓋；
2.3 激活並安裝在轉發麵中；
3.  該步驟對node節點連接關係進行更新；
在說明該步驟之前，需要說明一下背景。上述增加的路由表項已經完成了resolved，但是注意這個resovled實現的節點的連接關係是ip4-lookup到arp-ipv4，就是說最終轉發報文所需的信息（nexthop mac地址）還沒有，此處連接好的節點只是表明一旦有流量經過，那麼會觸發mac地址學習這個動作。此外在步驟1中，解析path時，vpp會發送一條arp-request，期望能儘快學習到mac地址，一旦學習到，那麼步驟3就開始行動起來了。可以猜到，當學習到mac地址後，最終的路由解析完成了，那麼轉發麵的node連接關係（ip4-lookup->arp-ipv4）也要發生變化了(ip4-lookup->ip4-rewrite）；vpp採用一個walk的術語實現這一個功能，還記得前面在數據結構梳理一節中的fib_node_t這個連接端子嗎？因為有這個連結端子，同時vpp在創建路由、path時已經建立好了關聯關係（如下圖），所以此處可以按圖索驥，計算和更新路由表及其轉發麵的節點拓撲。
步驟3的處理流程：
3.1 ip_adjency_t狀態發生了變化，通知fib_path_list_t(23)進行更新，進一步更新192.168.0.0/24 fib_entry，最終更新轉發麵dpo；
3.2 ip_adjency_t狀態發生了變化，通知fib_path_list_t(21)進行更新，進一步更新192.168.10.1/32 fib_entry，最終更新轉發麵dpo；