模擬MMU設(shè)計(jì)一個(gè)將IPv4地址索引化的路由表，不同于DxR

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

將最長(zhǎng)掩碼邏輯提前到插入的時(shí)刻

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

路由還是交換

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

設(shè)想中的實(shí)現(xiàn)-將“查找”變成“訪問”

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

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

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

和MMU的區(qū)別帶來的插曲

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

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

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

現(xiàn)實(shí)的實(shí)現(xiàn)-用起來

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

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

因?yàn)榈刂房臻g中有數(shù)據(jù)也有指令，每一個(gè)指令，即進(jìn)程本身的指令都會(huì)占據(jù)一個(gè)虛擬地址，這個(gè)地址便不能作為IPv4地址了...程序庫封裝了大量的指令，因此不能用。

2.你甚至不能使用內(nèi)核

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