模拟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部还算可以的恐怖片《怨灵》，在绍兴兰亭讲历史...