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

這是1個失敗的嘗試

我不知道有無人這么玩過，或許有，或許沒有。但不能不先說1下本文的條件，本文中所述的設計是1個不可行的設計，它是不可能實現的！緣由在于我在思考的進程中沒有全盤應對。但是，雖然是1個失敗的設計，也要把這個進程記錄下來，由于期間的思考進程是值得保存的，即使是沒有帶來預期的結果。
       另外，這是我在幫1個朋友的項目中所做工作的1部份，假期在旅游的間隙，酒店里做的，沒有拿錢，純潔幫忙，也沒有占用工作時間，固然也沒有占用旅游的時間，所以我只是記錄1下而已。

空間換時間

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

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

就Linux等通用操作系統而言，路由表的查表開消主要集中在“最長掩碼匹配”上，由于在數據包履行IP路由的進程中，輸入僅僅是1個IPv4地址，即IP頭中提取的目標IP地址，而此時的IP路由模塊其實不知道路由表中哪些條目和這個IPv4地址相干，需要進行1次查找才能肯定，在查找的進程中履行“最長掩碼匹配”邏輯，對HASH組織算法而言，依照掩碼的長度組織hash表，匹配順序自32位掩碼順次向下，而對TRIE組織算法而言，情況也差不多，詳情參閱《Internet路由之路由表查找算法概述-哈希/LC-Trie樹/256-way-mtrie樹》。
       對查找而言，特別是HASH算法，難免要進行比較，比較結果要末為0要末非0，如果去除比較的本錢，理論上會節省1半的時間，對TRIE樹而言，算上回溯，節省的本錢更多。固然了，不論是HASH算法還是TRIE樹算法，都會圍繞數據結構本身和地址的特點做很多的優化，但是遺憾的是，這些優化治標不治本，沒法從根本上將“查找”這個操作根除！好吧，消除查找/比較就是根本目標！
       將IPv4地址索引化，就是答案！IPv4地址空間總共有4G個地址，如果將每個地址都作為1個索引，那末將會消耗巨量的內存，但是這不是本質問題，完全可以學著頁表那樣組織成份級索引。本質問題是如何將路由項和索引進行多對1的對應！即根據1個IPv4地址，將其作為1個索引，然后索引直接指向所有路由結果中最長掩碼的那1條結果！這個倒也不難，我姑且不引入多級索引，依然用平坦的32位IPv4地址空間做1級索引。以下圖所示：

可以看出，最關鍵的就是用路由前綴將IPv4地址空間劃分為多個區間，依照上圖所示，拿著目標IP地址當索引，向右走，碰到的第1個路由項就是結果。最長掩碼的邏輯完全部現在插入/刪除進程中，即從左到右前綴順次變短，長前綴的路由項會蓋在短前綴的路由項的前面，這就是核心思想。其實在HiPac防火墻中，也正是使用了這個思想，即區間優先級。只是公道奇妙的編排數據結構，將最長掩碼邏輯提早到插入/刪除的時刻，將IP地址索引化，這樣會讓匹配進程1步到位。
       我們不能用前綴長的路由完全覆蓋后面的，由于當它被刪除掉的時候，后面的還是要暴露出來的。
       好了，總結1下。插入/刪除操作在履行的時候，保證了最長掩碼的那個路由項覆蓋在了它作用地址區間的最前面。

路由還是交換

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

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

盡人皆知，現代操作系統是基于虛擬內存的，更好地實現了進程之間的隔離與訪問控制，但是本文不談這些，本文要說的是基于這個原則的“1種利用”。
       事實上，在運行著現代操作系統的計算機的運行進程中，每訪問1個地址都要經歷1番“查找”，這個查找進程是如此地快以致于大多數用戶乃至程序員(系統程序員除外)都會視而不見，乃至很多人都不知道存在這么1個查找進程，這個查找進程就是MMU的虛擬/物理地址的轉換進程。
       如果我用IPv4路由前綴作為虛擬內存地址，將其對應的下1跳等路由結果信息作為物理頁面的內容并依照此對應關系建立頁表映照，那末我只需要訪問1下從IP頭中抽取的目標IPv4地址，就能夠獲得對應的物理頁面的內容，內容是甚么？西服嗎？NO！內容就是路由的結果。我將第1節的示意圖加以簡化再略微變換1下，變成了下面的模樣：

看出來甚么了嗎？這不就是頁表么？是的，IPv4地址作為索引，而路由項結果作為物理頁面，最長掩碼匹配進程體現在了構建映照的進程中。但是，這有問題！占用空間太大了！是的，MMU的解決辦法就是構建多級映照，路由表也能夠采取這個原則。將上面的圖折彎1下，就變成了1個類MMU設施的路由匹配表：

好了，現在完全將路由匹配表套在了MMU設施中，IPv4地址完全索引化！直接像訪問內存地址那樣“訪問IPv4”地址，比如IPv4地址為0x01020304，那末為了獲得它的路由項結果，只需要以下的訪問：

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

和MMU的區分帶來的插曲

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

       以上的圖示是我事后畫的，洗澡的時候我沒有照著這個思路走下去，反而在思考D16R(以16bit作為直接索引的DxR實例)的公道性，難道我也要被引到DxR的思想中去嗎？想到這里，我又興奮又懊喪，興奮是由于我原創性質地自行設計出了DxR，懊喪在于我實在不想學它，我想設計1個完全索引化的多級索引表，不加入任何所謂的“算法”，所以我要避開各種樹，各種諸如2分查找之類的，乃至避開哈希和遍歷。因此在用起來之前，我要記錄1下我要避開這類算法的理由，下面的1節本應當加密，萬1被看到了，不喜勿噴，這不是吐嘈，這是愛好-雖然終究證明我是錯的。

避開各種樹，hash和精巧算法的理由

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

現實的實現-希望用起來

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

1.你不能使用C庫或和任何別的庫

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

2.你乃至不能使用內核

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

為何失敗

只有在實際寫代碼的時候，才會發現這個設計是多么地不可行！除非你具有4G多的內存可用，否則永久別希望這個算法能有多快！雖然我采取分級索引的方式建立了IPv4地址到下1跳索引的映照，但是斟酌1下1共會有多少個這樣的映照？所有的IPv4地址，那末就是4G個映照，算上映照表，下1跳表，總共需要4G以上的內存可用...這難道不還是空間換時間嗎？多級的映照表并沒有節省空間-相反它平增了管理開消，它僅僅是適應了稀疏索引而已，而我們知道，路由時的目標IPv4地址其實不是1個稀疏的索引！只能暫時擱筆，容我想一想，然后先退回到DxR算法。
       這是羊年春節期間的1個收獲，類比了MMU，摹擬了了MMU，另外的收獲是，讀了很多歷史方面的書，看了幾部電影，其中1部還算可以的恐怖片《怨靈》，在紹興蘭亭講歷史...