模擬MMU設計一個將IPv4地址索引化的路由表，不同于DxR

我不知道有沒有人這么玩過，也許有，也許沒有。
時間和空間永遠都在厚此薄彼，只因為設施不全，在資源匱乏的年代，只能取舍。但是如果資源豐盈，魚 與熊掌，完全可以兼得！對于路由查找而言，緊湊的數據結構占用了很小的空間，難道它就要為此付出時間的代價嗎？如果我們考慮MMU設施，就會發現，緊湊的 數據結構不但節省了空間，還提高了速度。
       我們長期受到的教育就是取義一定要舍身這樣的教育，如果不舍身，取到的不會是義，也可能會被訛詐，不怪自己被訛，只因自己沒死。其實仔細想想，即便在資源 不那么豐盈，甚至資源緊缺的年代，緊湊小巧的數據結構一定會帶來時間的浪費嗎？或者說，速度快高效率的算法就一定要浪費內存嗎？如果是這樣，那么MMU是 怎么會被設計出來的呢？如果真的是這樣，MMU會因其維護自身所消耗的時間和空間超過了它的目標帶來的收益而被無情pass掉。然而，我們都知道，它最終 被設計出來了。并且，得益于CPU Cache的高效利用，MMU退化成了一個Cache不命中時才會啟用的慢速路徑，而通過局部性我們知道，大多數時候，執行流走的是快速路經...看來， 思路該換一下了。
       我知道的是，DxR算法就是這么玩的，所以這不是我個人在胡扯。但是我的玩法和DxR稍微有一點不同...

將最長掩碼邏輯提前到插入的時刻

就 Linux等通用操作系統而言，路由表的查表開銷主要集中在“最長掩碼匹配”上，因為在數據包執行IP路由的過程中，輸入僅僅是一個IPv4地址，即IP 頭中提取的目標IP地址，而此時的IP路由模塊并不知道路由表中哪些條目和這個IPv4地址相關，需要進行一次查找才能確定，在查找的過程中執行“最長掩 碼匹配”邏輯，對于HASH組織算法而言，按照掩碼的長度組織hash表，匹配順序自32位掩碼依次向下，而對于TRIE組織算法而言，情況也差不多，詳 情參閱《Internet路由之路由表查找算法概述-哈希/LC-Trie樹/256-way-mtrie樹》。
       對于查找而言，特別是HASH算法，難免要進行比較，比較結果要么為0要么非0，如果去除了比較的成本，理論上會節省一半的時間，對于TRIE樹而言，算 上回溯，節省的成本更多。當然了，不管是HASH算法還是TRIE樹算法，都會圍繞數據結構本身以及地址的特點做很多的優化，但是遺憾的是，這些優化治標 不治本，無法從根本上將“查找”這個操作根除！好吧，消除查找/比較就是根本目標！
       將IPv4地址索引化，就是答案！IPv4地址空間總共有4G個地址，如果將每一個地址都作為一個索引，那么將會消耗巨量的內存，但是這不是本質問題，完 全可以學著頁表那樣組織成分級索引。本質問題是如何將路由項和索引進行多對一的對應！即根據一個IPv4地址，將其作為一個索引，然后索引直接指向所有路 由結果中最長掩碼的那一條結果！這個倒也不難，我姑且不引入多級索引，仍然用平坦的32位IPv4地址空間做一級索引。如下圖所示：
可 以看出，最關鍵的就是用路由前綴將IPv4地址空間劃分為多個區間，按照上圖所示，拿著目標IP地址當索引，向右走，碰到的第一個路由項就是結果。最長掩 碼的邏輯完全體現在插入/刪除過程中，即從左到右前綴依次變短，長前綴的路由項會蓋在短前綴的路由項的前面，這就是核心思想。其實在HiPac防火墻中， 也正是使用了這個思想，即區間優先級。只是合理巧妙的編排數據結構，將最長掩碼邏輯提前到插入/刪除的時刻，將IP地址索引化，這樣會讓匹配過程一步到 位。
       我們不能用前綴長的路由完全覆蓋后面的，因為當它被刪除掉的時候，后面的還是要暴露出來的。
       好了，總結一下。插入/刪除操作在執行的時候，保證了最長掩碼的那個路由項覆蓋在了它作用地址區間的最前面。

路由還是交換

IP 互聯網被設計成基于路由的而非基于交換的，這背后有一個哲學意義上理由。然而如今，人們逐漸在IP路由上加入了交換的特征，從而設計出了很多基于硬件的快 速轉發裝置或者依靠路由表生成交換轉發表實現快速轉發，比如三層交換機。但是到底什么是交換？什么又是路由？簡單來講，路由是一種比較軟的叫法，其執行方 式為“取出協議頭的字段，然后和路由表的內容做‘最長前綴匹配’，其間經歷大量的訪存，比較操作”，而交換則是比較硬一些的說法，其執行方式為“從協議頭 中取出一個‘索引字段’，直接索引交換表，然后根據索引指向的結果直接轉發”。看看吧，我的玩法和DxR是不是變路由為交換了，也許你覺得這無非雕蟲小 技，但是生活難道不應該為這種小事情而樂呵樂呵么...

設想中的實現-將“查找”變成“訪問”

眾所周知，現代操作系統是基于虛擬內存的，更好地實現了進程之間的隔離與訪問控制，但是本文不談這些，本文要說的是基于這個原則的“一種利用”。
       事實上，在運行著現代操作系統的計算機的運行過程中，每訪問一個地址都要經歷一番“查找”，這個查找過程是如此地快以至于大多數用戶甚至程序員(系統程序 員除外)都會視而不見，甚至很多人都不知道存在這么一個查找過程，這個查找過程就是MMU的虛擬/物理地址的轉換過程。
       如果我用IPv4路由前綴作為虛擬內存地址，將其對應的下一跳等路由結果信息作為物理頁面的內容并按照此對應關系建立頁表映射，那么我只需要訪問一下從 IP頭中抽取的目標IPv4地址，就可以獲取對應的物理頁面的內容，內容是什么？西服嗎？NO！內容就是路由的結果。我將第一節的示意圖加以簡化再稍微變 換一下，變成了下面的樣子：
看出來什么了嗎？這不就是頁表么？是的，IPv4地址作為索引，而路由 項結果作為物理頁面，最長掩碼匹配過程體現在了構建映射的過程中。但是，這有問題！占用空間太大了！是的，MMU的解決辦法就是構建多級映射，路由表也可 以采用這個原則。將上面的圖折彎一下，就變成了一個類MMU設施的路由匹配表：
好了，現在完全將路由匹配表套在了MMU設施中，IPv4地址完全索引化！直接像訪問內存地址那樣“訪問IPv4”地址，比如IPv4地址為0x01020304，那么為了獲取它的路由項結果，只需要如下的訪問：

char *addr = 0x01020304;
struct fib_res *res = (struct fib_res *)*addr;

如果發生缺頁，就說明沒有匹配的路由，即Network is unreachable，如果有默認路由，所有沒有指定映射的虛擬地址都會落在“默認路由頁面”上。

和MMU的區別帶來的插曲

雖然上面畫出的那幅圖看上去真的狠像MMU設施，但是你注意到它們的區別了嗎？
       MMU映射的物理頁面大小是固定的，然而路由表中被各條路由覆蓋的地址區間范圍卻不是固定的，但是這又有什么關系呢？折騰了大半天準備寫個模擬實現，覺得 很興奮，然后去沖個澡，沒辦法，我喜歡冷，但是家里實在太冷了，也許，沖個熱水澡可以帶來點思路，然而不但沒有帶來什么思路，反而發現一個嚴重的問題，就 是路由項和物理頁面無法完全類比，因為它的大小并不固定，如果按照類似4096大小頁面來切分IPv4地址空間，最終在二級“路由頁表”中索引到的是一個 覆蓋4096個IPv4地址的范圍，難道它們必須使用同一個路由項嗎？我感覺自己那個時候好傻！把自己的思路向下推進一步問題就解決了，而這根本就不是一 個問題，我在上面最后一個圖里畫得一清二楚！我使用了全部的32位IPv4地址做索引，而不是像4096大小頁表那樣空出低12位！我實際上構建的是一個 地址表而不是地址塊表。復雜性全部在插入以及對下一跳的編碼上。我想，是絕對不能在最終的路由"頁面"存儲指針的，因為對于32位系統，指針要4字 節，64位的話更多，為了應付一個IPv4地址一條路由這種極端情況，每一個目標IPv4作為索引最終定位到的那個所謂的“項”，只能有一個字節可以使 用！！
       一個字節怎么使用？如果我有1萬個表項怎么辦？哈哈！反過來想，最終我們要得到什么？得到一個下一跳而已！總共會有多少下一跳？256個夠嗎？我覺得是夠 了！你可能會有1萬個路由表項，但是它們會復用少得多的“下一跳”。你見過哪個路由器開花一樣接200多根線纜出去的嗎？交換機吧！因此我可能會如下的編 碼：將所有的下一跳連續放在一塊連續的內存中，每個項大小固定，然后用最終的路由頁表加偏移指向的那一個字節索引這些下一跳們(如果下一跳們的數量超過了 256，那還有辦法，就是從為了對齊而空余不用的byte中借位，對齊不但有利于快速內存尋址，也利用cacheline的映射)。
       以上的圖示是我事后畫的，洗澡的時候我沒有照著這個思路走下去，反而在思考D16R(以16bit作為直接索引的DxR實例)的合理性，難道我也要被引到 DxR的思想中去嗎？想到這里，我又興奮又沮喪，興奮是由于我原創性質地自行設計出了DxR，沮喪在于我實在不想學它，我想設計一個完全索引化的多級索引 表，不加入任何所謂的“算法”，所以我要避開各種樹，各種諸如二分查找之類的，甚至避開哈希和遍歷。因此在用起來之前，我要記錄一下我要避開這種算法的理 由，下面的一節本應該加密，萬一被看到了，不喜勿噴，這不是吐嘈，這是愛好。

避開各種樹，hash以及精妙算法的理由

O(1)一定很快嗎？O(n)和O(lgn)呢？大O當自強！
       首先，在設計和實現一個體系的時候，不要被算法書上的理論捆住了手腳。大O旨在擴展性方面提供一個考量，簡單說，如果算法不隨著元素個數的增加而增加計算 延時，那么它就是O(1)，如果元素個數和時間的增加是log關系，那么它就是O(lgn)。具體n是多少，曲線到多少才會"大拐"？也許你會說，這種基 于MMU的路由表不適合IPv6，那樣它會占據大多的空間，因此就不具備可擴展性，但是我也沒說要用于IPv6啊，對于IPv4路由而言，它難道不和32 位虛擬地址一樣么？MMU的設計怎么就沒有考慮可擴展性呢？答案是當MMU應用在64位系統上的時候，它可以有更多的選擇，比如反向hash表等，但是對 于32位系統，完全索引化的MMU絕對比各種樹各種hash要好，另外，它更適合硬件實現 ，因為它“無邏輯”，簡單！舉一個不恰當的例子。如果一個O(1)算法，它的執行時間是100年，哪怕n到了10000000000...每趟下來都是 100年，絕對一個O(1)算法，另外有一個O(n2)算法，它在n等于100的時候執行時間為1ns，而赫拉克勒斯知道，在特定的環境中，n不會大于 500，你會選擇哪個算法呢？
       在IPv4的環境下，或者在不差錢買內存的IPv6環境下，或者在任意的可控的有限環境下(可別扯無限！在計算機中沒有無限！你看OpenSSL中算個 big number多費勁啊)，多級索引表無疑是最快的數據結構，最好用的當然是hash，但它絕對沒有索引快。索引化保證了速度，多級保證了空間占用不會太 大，其中級數就是算法執行操作的數量，別的都是浮云。
       算法的大O法適合算法分析，但如果用于真實系統，必須考慮很多別的約束。大O在數據訪問上忽略了訪存尋址的開銷，平滑了各級cache帶來的效率差異(它 們可是數量級的差異啊)，在指令執行上平滑了各種操作的指令時間差異，忽略了cache，忽略了MMU，然而這些在實際的實現中都不能忽略。算法分析甚至 都不能算是軟件性能的分析，這不是它的缺陷，因為人家就不是干這個的。軟件和硬件的改造都可以將同一個算法改良，硬件布線的不同可造成實際開銷的差異，比 如換一條總線，挪一個位置...因此最終的性能應該是算法本身，軟件實現，硬件實現三者的函數，權值偏重還不一樣。人們往往十分在乎算法本身，其次在乎軟 件實現，對于硬件，基本是仰望，沒錢怎么都不行，不像前兩者，換個算法，換個實現就可以搞定的。

現實的實現-用起來

這么美妙的一個類比，成全了一個完美的查找結構，是時候用起來了！
       簡單來講，只需要建立一個“地址空間”，然后用路由表內容來填充MMU就可以了。但是沒有這么簡單，比如在Linux中會面臨下面的問題：

1.你不能使用C庫或者以及任何別的庫

因為地址空間中有數據也有指令，每一個指令，即進程本身的指令都會占據一個虛擬地址，這個地址便不能作為IPv4地址了...程序庫封裝了大量的指令，因此不能用。

2.你甚至不能使用內核

這可沒得玩了，內核本身為所有的地址空間共享，內核作為一個管理機構，其代碼本身也映射在了任何地址空間中，比如0xC0000000以上的很多地址都是和物理內存一一映射的，不多說了吧。
由于代碼指令的映射，整個虛擬地址空間不能全部為IPv4地址所用，那么解決辦法是什么呢？
       既然已經學會了思想，干嘛非要完完全全照搬呢？直接使用MMU設施？這個想法太瘋狂，也印證了思想者太懶惰！誠然，你可以使用帶有虛擬化支持的虛擬MMU中的一套設施，但這只能說明你對硬件本身比較精通。為何不自己構建一套軟的MMU呢？
       DxR路由表的構建無疑是緊湊而精妙的，它并沒有指望使用現成的MMU，反而在其中加入了二分法，這便是一個很好的折中模擬，我也可以這么做。我并不指望 這個模擬MMU的匹配算法本身能有多快，而是要學習一下DxR的思想，即使用緊湊的數據結構來提高CPU Cache的利用率，盡可能將結果Cache到CPU而不是將請求發射到總線！即便完全使用系統的硬件MMU，又能如何呢？能利用它的TLB嗎？如果不 能，還有什么意義呢？你知道TLB命中意味著什么嗎？你知道大部分的MMU尋址操作都不是直接去查頁表而基本都是在TLB中命中的嗎？TLB是一種 Cache！因此，模擬MMU并不是根本目的，利用Cache才是王道！
       我們知道，CPU Cache(包括TLB)之所以可以被以可觀的頻率命中，是因為內存尋址的局部性！對于IP地址而言，這種局部性存在嗎？想象一下屬于一個數據流的多個數 據包會持續經過，不同數據流的數據包錯峰經過，就會知道局部性原則是一個普適的原則。核心路徑上的流量工程都是基于路徑的，而QoS是基于應用的，這種分 類原則會促進局部性而不是抵消它！畢竟，分類，what is 分類？這是一個哲學問題，柏拉圖以來，兩千年了，人們還在持續論爭，分類到底是為了聚合，還是為了散列...
       這是羊年春節期間的一個收獲，類比了MMU，模擬了了MMU，另外的收獲是，讀了很多歷史方面的書，看了幾部電影，其中一部還算可以的恐怖片《怨靈》，在紹興蘭亭講歷史...