Linux转发性能评估与优化(转发瓶颈分析与解决方案)
时间：2021-12-09 15:44:59
手机看文章
扫描二维码
随时随地手机看文章
[导读]原文作者：dog250原文链接：https://blog.csdn.net/dog250/article/details/46666029线速问题很多人对这个线速概念存在误解。认为所谓线速能力就是路由器/交换机就像一根网线一样。而这，是不可能的。应该考虑到的一个概念就是延迟。数据...
原文作者：dog250原文链接：https://blog.csdn.net/dog250/article/details/46666029
线速问题
很多人对这个线速概念存在误解。认为所谓线速能力就是路由器/交换机就像一根网线一样。而这，是不可能的。应该考虑到的一个概念就是延迟。数据包进入路由器或者交换机，存在一个核心延迟操作，这就是选路，对于路由器而言，就是路由查找，对于交换机而言，就是查询MAC/端口映射表，这个延迟是无法避开的，这个操作需要大量的计算机资源，所以不管是路由器还是交换机，数据包在内部是不可能像在线缆上那样近光速传输的。类比一下你经过十字街头的时候，是不是要左顾右盼呢？
那么，设备的线速能力怎么衡量呢？如果一个数据包经过一个路由器，那么延迟必览无疑，可是设备都是有队列或者缓冲区的，那么试想一个数据包紧接一个数据包从输入端口进入设备，然后一个数据包紧接一个数据包从输出端口发出，这是可以做到的，我们对数据包不予编号，因此你也就无法判断出来的数据包是不是刚刚进去的那个了，这就是线速。
我们可以用电容来理解转发设备。有人可能会觉得电容具有通高频阻低频的功效，我说的不是这个，所以咱不考虑低频，仅以高频为例，电容具有存储电荷的功能，这就类似存储转发，电容充电的过程类似于数据包进入输入队列缓冲区，电容放电的过程类似于数据包从输出缓冲区输出，我们可以看到，在电流经过电容的前后，其速度是不变的，然而针对具体的电荷而言，从电容放出的电荷绝不是刚刚在在另一侧充电的那个电荷，电容的充电放电拥有固有延迟。
我们回到转发设备。对于交换机和路由器而言，衡量标准是不同的。
对于交换机而言，线速能力是背板总带宽，因为它的查表操作导致的延迟并不大，大量的操作都在数据包通过交换矩阵的过程，因此背板带宽直接导致了转发效率。而对于路由器，衡量标准则是一个端口每秒输入输出最小数据包的数量，假设数据包以每秒100个进入，每秒100个流出，那么其线速就是100pps。
本文针对路由器而不针对交换机。路由器的核心延迟在路由查找，而这个查找不会受到数据包长度的影响，因此决定路由器线速能力的核心就在数据包输出的效率，注意，不是数据包输入的效率，因为只要队列足够长，缓存足够大，输入总是线速的。但是输入操作就涉及到了如何调度的问题。这也就说明了为何很多路由器都支持输出流量控制而不是输入流量控制的原因，因为输入流控即使完美完成，它也会受到路由器输出端口自身输出效率的影响，流控结果将不再准确。
在写这个方案的前晚，有一个故事。我最近联系到了初中时一起玩摇滚玩音响的超级铁的朋友，他现在搞舞台设计，灯光音响之类的。我问他在大型舞台上，音箱摆放的位置不同，距离后级，前置，音源也不同，怎么做到不同声道或者相同声道的声音同步的，要知道，好的耳朵可以听出来毫秒级的音差...他告诉我要统一到达时间，即统一音频流到达各个箱子的时间，而这要做的就是调延迟，要求不同位置的箱子路径上要有不同的延迟。这对我的设计方案的帮助是多么地大啊。
然后，在第二天，我就开始整理这个令人悲伤最终心碎的Linux转发优化方案。
声明：本文只是一篇普通文章，记录这个方案的点点滴滴，并不是一个完整的方案，请勿在格式上较真，内容上也只是写了些我认为重要且有意思的。完整的方案是不便于以博文的形式发出来的。见谅。
问题综述
Linux内核协议栈作为一种软路由运行时，和其它通用操作系统自带的协议栈相比，其效率并非如下文所说的那样非常低。然而基于工业路由器的评判标准，确实是低了。 市面上各种基于Linux内核协议栈的路由器产品，甚至网上也有大量的此类文章，比如什么将Linux变成路由器之类的，无非就是打开ip_forward，加几条iptables规则，搞个配置起来比较方便的WEB界面...我想说这些太低级了，甚至超级低级。我很想谈一下关于专业路由器的我的观点，但是今天是小小的生日，玩了一天，就不写了。只是把我的方案整理出来吧。
Linux的转发效率到底低在哪儿？如何优化？这是本文要解释的问题。依然如故，本文可以随意转载并基于这个思路实现编码，但是一旦用于商业目的，不保证没有个人或组织追责，因此文中我尽量采用尽可能模糊的方式阐述细节。
瓶颈分析概述
1.DMA和内存操作我们考虑一下一个数据包转发流程中需要的内存操作，暂时不考虑DMA。*)数据包从网卡拷贝到内存*)CPU访问内存读取数据包元数据*)三层报头修改，如TTL*)转发到二层后封装MAC头*)数据包从内存拷贝到输出网卡这几个典型的内存操作为什么慢？为什么我们总是对内存操作有这么大的意见？因为访问内存需要经过总线，首先总线竞争(特别在SMP和DMA下)就是一个打群架的过程，另外因为内存自身的速度和CPU相比差了几个数量级，这么玩下去，肯定会慢啊！所以一般都是尽可能地使用CPU的cache，而这需要一定的针对局部性的数据布局，对于数据包接收以及其它IO操作而言，由于数据来自外部，和进程执行时的局部性利用没法比。所以必须采用类似Intel I/OAT的技术才能改善。
1.1.Linux作为服务器时采用标准零拷贝map技术完全胜任。这是因为，运行于Linux的服务器和线速转发相比就是个蜗牛，服务器在处理客户端请求时消耗的时间是一个硬性时间，无法优化，这是代偿原理。Linux服务唯一需要的就是能快速取到客户端的数据包，而这可以通过DMA快速做到。本文不再具体讨论作为服务器运行的零拷贝问题，自己百度吧。
1.2.Linux作为转发设备时需要采用DMA映射交换的技术才能实现零拷贝。这是Linux转发性能低下的根本。由于输入端口的输入队列和输出端口的输出队列互不相识，导致了不能更好的利用系统资源以及多端口数据路由到单端口输出队列时的队列锁开销过大，总线争抢太严重。DMA影射交换需要超级棒的数据包队列管理设施，它用来调度数据包从输入端口队列到输出端口队列，而Linux几乎没有这样的设施。虽然近年在路由器领域有人提出了输入队列管理，但是这项技术对于Linux而言就是另一个世界，而我，把它引入了Linux世界。
2.网卡对数据包队列Buff管理在Linux内核中，几乎对于所有数据结构，都是需要时alloc，完毕后free，即使是kmem_cache，效果也一般，特别是对于高速线速设备而言(skb内存拷贝，若不采用DMA，则会频繁拷贝，即便采用DMA，在很多情况下也不是零拷贝)。即使是高端网卡在skb的buffer管理方面，也没有使用完全意义上的预分配内存池，因此会由于频繁的内存分配，释放造成内存颠簸，众所周知，内存操作是问题的根本，因为它涉及到CPU Cache，总线争抢，原子锁等，实际上，内存管理才是根本中的根本，这里面道道太多，它直接影响CPU cache，后者又会影响总线...从哪里分配内存，分配多少，何时释放，何时可以重用，这就牵扯到了内存区域着色等技术。通过分析Intel千兆网卡驱动，在我看来，Linux并没有做好这一点。
3.路由查找以及其它查找操作Linux不区分对待路由表和转发表，每次都要最长前缀查找，虽然海量路由表时trie算法比hash算法好，但是在路由分布畸形的情况下依然会使trie结构退化，或者频繁回溯。路由cache效率不高（查询代价太大，不固定大小，仅有弱智的老化算法，导致海量地址访问时，路由cache冲突链过长），最终在内核协议栈中下课。如果没有一个好的转发表，那么Linux协议栈在海量路由存在时对于线速能力就是一个瓶颈，这是一个可扩展性问题。另外，很多的查询结果都是可以被在一个地方缓存的，但是Linux协议栈没有这种缓存。比如，路由查询结果就是下一跳，而下一跳和输出网卡关联，而输出网卡又和下一跳的MAC地址以及将要封装的源MAC地址关联，这些本应该被缓存在一个表项，即转发表项内，然而Linux协议栈没有这么做。
4.不合理的锁为何要加锁，因为SMP。然而Linux内核几乎是对称的加锁，也就是说，比如每次查路由表时都要加锁，为何？因为怕在查询的期间路由表改变了...然而你仔细想想，在高速转发情景下，查找操作和修改操作在单位时间的比率是多少呢？不要以为你用读写锁就好了，读写锁不也有关抢占的操作吗(虽然我们已经建议关闭了抢占)？起码也浪费了几个指令周期。这些时间几率不对称操作的加锁是不必要的。你只需要保证内核本身不会崩掉即可，至于说IP转发的错误，不管也罢，按照IP协议，它本身就是一个尽力而为的协议。
5.中断与软中断调度Linux的中断分为上半部和下半部，动态调度下半部，它可以在中断上下文中运行，也可以在独立的内核线程上下文中运行，因此对于实时需求的环境，在软中断中处理的协议栈处理的运行时机是不可预知的。Linux原生内核并没有实现Solaris，Windows那样的中断优先级化，在某些情况下，Linux靠着自己动态的且及其优秀的调度方案可以达到极高的性能，然而对于固定的任务，Linux的调度机制却明显不足。而我需要做的，就是让不固定的东西固定化。
6.通用操作系统内核协议栈的通病作为一个通用操作系统内核，Linux内核并非仅仅处理网络数据，它还有很多别的子系统，比如各种文件系统，各种IPC等，它能做的只是可用，简单，易扩展。Linux原生协议栈完全未经网络优化，且基本装机在硬件同样也未经优化的通用架构上，网卡接口在PCI-E总线上，如果DMA管理不善，总线的占用和争抢带来的性能开销将会抵消掉DMA本意带来的好处（事实上对于转发而言并没有带来什么好处，它仅仅对于作为服务器运行的Linux有好处，因为它只涉及到一块网卡）[ 注意，我认为内核处理路径并非瓶颈，这是分层协议栈决定的，瓶颈在各层中的某些操作，比如内存操作(固有开销)以及查表操作(算法不好导致的开销)]
综述：Linux转发效率受到以下几大因素影响
IO/输入输出的队列管理/内存修改拷贝 （重新设计类似crossbar的队列管理实现DMA ring交换）各种表查询操作，特别是最长前缀匹配，诸多本身唯一确定的查询操作之间的关联没有建立SMP下处理器同步（锁开销）（使用大读锁以及RCU锁）以及cache利用率中断以及软中断调度
Linux转发性能提升方案
概述此方案的思路来自基于crossbar的新一代硬件路由器。设计要点：
1.重新设计的DMA包管理队列（ 思路来自Linux O(1)调度器，crossbar阵列以及VOQ[虚拟输出队列]）2.重新设计的基于定位而非最长前缀查找的转发表3.长线程处理（中断线程化，处理流水线化，增加CPU亲和）4.数据结构无锁化（基于线程局部数据结构）5.实现方式5.1.驱动以及内核协议栈修改5.2.完全的用户态协议栈5.3.评估：用户态协议栈灵活，但是在某些平台要处理空间切换导致的cache/tlb/mmu表的flush问题
内核协议栈方案优化框架0.例行优化1).网卡多队列绑定特定CPU核心（利用RSS特性分别处理TX和RX）[ 可以参见《Effective Gigabit Ethernet Adapters-Intel千兆网卡8257X性能调优》]2).按照包大小统计动态开关积压延迟中断ThrottleRate以及中断Delay(对于Intel千兆卡而言)3).禁用内核抢占，减少时钟HZ，由中断粒度驱动（见上面）4).如果不准备优化Netfilter，编译内核时禁用Netfilter，节省指令5).编译选项去掉DEBUG和TRACE，节省指令周期6).开启网卡的硬件卸载开关（如果有的话）7).最小化用户态进程的数量，降低其优先级8).原生网络协议栈优化 由于不再作为通用OS，可以让除了RX softirq的task适当饥饿 *CPU分组(考虑Linux的cgroup机制)，划一组CPU为数据面CPU，每一个CPU绑定一个RX softirq或者 *增加rx softirq一次执行的netdev_budget以及time limit，或者 *只要有包即处理，每一个。控制面/管理面的task可以绑在别的CPU上。
宗旨：原生协议栈的最优化方案
1.优化I/O，DMA，减少内存管理操作1).减少PCI-E的bus争用,采用crossbar的全交叉超立方开关的方式[ Tips：16 lines 8 bits PCI-E总线拓扑(非crossbar！)的网络线速不到满载60% pps]2).减少争抢式DMA，减少锁总线[Tips：优化指令LOCK，最好采用RISC，方可调高内核HZ][ Tips：交换DMA映射，而不是在输入/输出buffer ring之间拷贝数据！现在，只有傻逼才会在DMA情况拷贝内存，正确的做法是DMA重映射，交换指针！]3).采用skb内存池，避免频繁内存分配/释放造成的内存管理框架内的抖动[ Tips：每线程负责一块网卡(甚至输入和输出由不同的线程负责会更好)，保持一个预分配可循环利用的ring buffer，映射DMA]
宗旨：减少cache刷新和tlb刷新，减少内核管理设施的工作(比如频繁的内存管理)
2.优化中断分发1).增加长路径支持，减少进程切换导致的TLB以及Cache刷新2).利用多队列网卡支持中断CPU亲和力利用或者模拟软多队列提高并行性3).牺牲用户态进程的调度机会，全部精力集中于内核协议栈的处理，多CPU多路并行的[ Tips：如果有超多的CPU，建议划分cgroup ]4).中断处理线程化，内核线程化，多核心并行执行长路经，避免切换抖动5).线程内部，按照IXA NP微模块思想采用模块化(方案未实现，待商榷)
宗旨：减少cache刷新和tlb刷新减少协议栈处理被中断过于频繁打断[ 要么使用IntRate，要么引入中断优先级]
3.优化路由查找算法1).分离路由表和转发表，路由表和转发表同步采用RCU机制2).尽量采用线程局部数据每个线程一张转发表（由路由表生成，OpenVPN多线程采用，但失败），采用定位而非最长前缀查找（DxR或者我设计的那个）。若不采用为每个线程复制一份转发表，则需要重新设计RW锁或者使用RCU机制。3).采用hash/trie方式以及DxR或者我设计的DxRPro定位结构
宗旨：采用定位而非查找结构采用局部表，避免锁操作
4.优化lock1).查询定位局部表，无锁（甚至RW锁都没有）不禁止中断2).临界区和内核线程关联，不禁中断，不禁抢占（其实内核编译时抢占已经关闭了）3).优先级锁队列替换争抢模型，维持cache热度4).采用Windows的自旋锁机制[ Tips：Linux的ticket spin lock由于采用探测全局lock的方式，会造成总线开销和CPU同步开销，Windows的spin lock采用了探测CPU局部变量的方式实现了真正的队列lock，我设计的输入输出队列管理结构(下面详述)思路部分来源于Windows的自旋锁设计]
宗旨：锁的粒度与且仅与临界区资源关联，粒度最小化
优化细节概览1.DMA与输入输出队列优化
1.1.问题出在哪儿如果你对Linux内核协议栈足够熟悉，那么就肯定知道，Linux内核协议栈正是由于软件工程里面的天天普及的“一件好事”造成了转发性能低效。这就是“解除紧密耦合”。Linux协议栈转发和Linux服务器之间的根本区别在于，后者的应用服务并不在乎数据包输入网卡是哪个，它也不必关心输出网卡是哪一个，然而对于Linux协议栈转发而言，输入网卡和输出网卡之间确实是有必要相互感知的。Linux转发效率低的根本原因不是路由表不够高效，而是它的队列管理以及I/O管理机制的低效，造成这种低效的原因不是技术实现上难以做到，而是Linux内核追求的是一种灵活可扩展的性能，这就必须解除出入网卡，驱动和协议栈之间关于数据包管理的紧密耦合。我们以Intel千兆网卡驱动e1000e来说明上述的问题。顺便说一句，Intel千兆驱动亦如此，其它的就更别说了，其根源在于通用的网卡驱动和协议栈设计并不是针对转发优化的。
初始化：创建RX ring：RXbuffinfo[MAX]创建TX ring：TXbuffinfo[MAX]
RX过程：i = 当前RX ring游历到的位置;while(RXbuffinfo中有可用skb) { skb = RXbufferinfo[i].skb; RXbuffinfo[i].skb = NULL; i ; DMA_unmap(RXbufferinfo[i].DMA); [Tips：至此，skb已经和驱动脱离，完全交给了Linux协议栈] [Tips：至此，skb内存已经不再由RX ring维护，Linux协议栈拽走了skb这块内存] OS_receive_skb(skb); [Tips：由Linux协议栈负责释放skb，调用kfree_skb之类的接口] if (RX ring中被Linux协议栈摘走的skb过多) { alloc_new_skb_from_kmem_cache_to_RXring_RXbufferinfo_0_to_MAX_if_possible; [Tips：从Linux核心内存中再次分配skb] }}
TX过程：skb = 来自Linux协议栈dev_hard_xmit接口的数据包;i = TX ring中可用的位置TXbufferinfo[i].skb = skb;DMA_map(TXbufferinfo[i].DMA);while(TXbufferinfo中有可用的skb) { DMA_transmit_skb(TXbufferinfo[i]);}[异步等待传输完成中断或者在NAPI poll中主动调用]i = 传输完成的TXbufferinfo索引while(TXbufferinfo中有已经传输完成的skb) { skb = TXbufferinfo[i]; DMA_unmap(TXbufferinfo[i].DMA); kfree(skb); i ;}以上的流程可以看出，在持续转发数据包的时候，会涉及大量的针对skb的alloc和free操作。如果你觉得上面的代码不是那么直观，那么下面给出一个图示：
频繁的会发生从Linux核心内存中alloc skb和free skb的操作，这不仅仅是不必要的，而且还会损害CPU cache的利用。不要寄希望于keme_cache，我们可以看到，所有的网卡和socket几乎是共享一块核心内存的，虽然可以通过dev和kmem cache来优化，但很遗憾，这个优化没有质的飞跃。
1.2.构建新的DMA ring buffer管理设施-VOQ，建立输入/输出网卡之间队列的关联。类比Linux O(1)调度器算法，每一个cpu全局维护一个唯一的队列，散到各个网卡，靠交换队列的DMA映射指针而不是拷贝数据的方式优化性能，达到零拷贝，这只是其一。关于交换DMA映射指针而不是拷贝数据这一点不多谈，因为几乎所有的支持DMA的网卡驱动都是这么做的，如果它们不是这么做的，那么肯定有人会将代码改成这么做的。如果类比高端路由器的crossbar交换阵列结构以及真实的VOQ实现，你会发现，在逻辑上，每一对可能的输入/输出网卡之间维护一条数据转发通路是避免队头阻塞以及竞争的好方法。这样排队操作只会影响单独的网卡，不需要再全局加锁。在软件实现上，我们同样可以做到这个。你要明白，Linux的网卡驱动维护的队列信息被内核协议栈给割裂，从此，输入/输出网卡之间彼此失联，导致最优的二分图算法无法实施。事实上，你可能觉得把网卡作为一个集合，把需要输出的数据包最为另一个集合，转发操作需要做的就是建立数据包和网卡之间的一条路径，这是一个典型的二分图匹配问题，然而如果把建立路径的操作与二分图问题分离，这就是不再是网卡和数据包之间的二分图匹配问题了。因为分离出来的路由模块导致了针对每一个要转发的数据包，其输出网卡是唯一确定的。这个问题变成了处理输出网卡输出操作的CPU集合和输出网卡之间的二分图匹配问题。这里有一个优化点，那就是如果你有多核CPU，那么就可以为每一块网卡的输出操作绑定一个唯一的CPU，二分图匹配问题迎刃而解，剩下的就是硬件总线的争用问题(对于高性能crossbar路由器而言，这也是一个二分图匹配问题，但对于总线结构的通用系统而言有点区别，后面我会谈到)了，作为我们而言，这一点除了使用性价比更高的总线，比如我们使用PCI-E 16Lines 8 bits，没有别的办法。作为一个完全的方案，我不能寄希望于底层存在一个多核CPU系统，如果只有一个CPU，那么我们能寄希望于Linux进程调度系统吗？还是那个观点，作为一个通用操作系统内核，Linux不会针对网络转发做优化，于是乎，进程调度系统是此方案的另一个优化点，这个我后面再谈。最后，给出我的数据包队列管理VOQ的设计方案草图。
在我的这个针对Linux协议栈的VOQ设计中，VOQ总要要配合良好的输出调度算法，才能发挥出最佳的性能。
2.分离路由表和转发表以及建立查找操作之间的关联Linux协议栈是不区分对待路由表和转发表的，而这在高端路由器上显然是必须的。诚然，我没有想将Linux协议栈打造成比肩专业路由器的协议栈，然而通过这个排名第二的核心优化，它的转发效率定会更上一层楼。在大约三个月前，我参照DxR结构以及借鉴MMU思想设计了一个用于转发的索引结构，可以实现3步定位，无需做最长前缀匹配过程，具体可以参见我的这篇文章 《以DxR算法思想为基准设计出的路由项定位结构图解》，我在此就不再深度引用了。需要注意的是，这个结构可以根据现行的Linux协议栈路由FIB生成，而且在路由项不规则的情况下可以在最差情况下动态回退到标准DxR，比如路由项不可汇聚，路由项在IPv4地址空间划分区间过多且分布不均。我将我设计的这个结构称作DxR Pro 。至于说查找操作之间的关联，这也是一个深度优化，底层构建高速查询流表实现协议栈短路（流表可参照conntrack设计），这个优化思想直接参照了Netfilter的conntrack以及SDN流表的设计。虽然IP网络是一个无状态网络，中间路由器的转发策略也应该是一个无状态的转发。然而这是形而上意义上的理念。如果谈到深度优化，就不得不牺牲一点纯洁性。设计一个流表，流的定义可以不必严格按照五元组，而是可以根据协议头的任意字段，每一个表项中保存的信息包括但不限于以下的元素：*流表缓存路由项*流表缓存neighbour*流表缓存NAT*流表缓存ACL规则 *流表缓存二层头信息这样可以在协议栈的底层保存一张可以高速查询的流表，协议栈收到skb后匹配这张表的某项，一旦成功，可以直接取出相关的数据(比如路由项)直接转发，理论上只有一个流的第一个数据包会走标准协议栈的慢速路径(事实上，经过DxR Pro 的优化，一经不慢了...)。在直接快速转发中，需要执行一个HOOK，执行标准的例行操作，比如校验和，TTL递减等。 关于以上的元素，特别要指出的是和neighbour与二层信息相关的。数据转发操作一向被认为瓶颈在发不在收，在数据发送过程，会涉及到以下耗时的操作：>添加输出网卡的MAC地址作为源-内存拷贝>添加next hop的MAC地址作为目标-内存拷贝又一次，我们遇到了内存操作，恼人的内存操作！如果我们把这些MAC地址保存在流表中，可以避免吗？貌似只是可以快速定位，而无法避免内存拷贝...再一次的，我们需要硬件的特性来帮忙，这就是分散聚集I/O(Scatter-gather IO)，原则上，Scatter-gather IO可以将不连续的内存当成连续的内存使用，进而直接映射DMA，因此我们只需要告诉控制器，一个将要发送的帧的MAC头的位置在哪里，DMA就可以直接传输，没有必要将MAC地址拷贝到帧头的内存区域。如下图所示：
特别要注意，上述的流表缓存项中的数据存在大量冗余，因为next hop的MAC地址，输出网卡的MAC地址，这些是可以由路由项唯一确定的。之所以保存冗余数据，其原则还是为了优化，而标准的通用Linux内核协议栈，它却是要避免冗余的...既然保存了冗余数据，那么慢速路径的数据项和快速路经的数据项之间的同步就是一个必须要解决的问题。我基于读写的不对称性，着手采用event的方式通知更新，比如慢速路径中的数据项(路由，MAC信息，NAT，ACL信息等)，一旦这些信息更改，内核会专门触发一个查询操作，将快速流表中与之相关的表项disable掉即可。值得注意的是，这个查询操作没必要太快，因为相比较快速转发而言，数据同步的频率要慢天文数字个数量级...类似Cisco的设备，可以创建几个内核线程定期刷新慢速路径表项，用来发现数据项的更改，从而触发event。
[Tips：可以高速查找的流表结构可用多级hash（采用TCAM的类似方案），也可以借鉴我的DxR Pro 结构以及nf-HiPac算法的多维区间匹配结构，我个人比较推崇nf-HiPac]
3.路由Cache优化虽说Linux的路由cache早已下课，但是它下课的原因并不是cache机制本身不好，而是Linux的路由cache设计得不好。因此以下几点可以作为优化点来尝试。*)限制路由软cache的大小，保证查找速度[实施精心设计的老化算法和替换算法][ 利用互联网访问的时间局部性以及空间局部性（需要利用计数统计）][ 自我PK：如果有了我的那个3步定位结构，难道还用的到路由cache吗]*)预制常用IP地址到路由cache，实现一步定位[ 所谓常用IP需要根据计数统计更新，也可以静态设置]
4.Softirq在不支持RSS多队列网卡时的NAPI调度优化*)将设备按照协议头hash值均匀放在不同CPU，远程唤醒softirq，模拟RSS软实现目前的网络接收软中断的处理机制是，哪个CPU被网卡中断了，哪个CPU就处理网卡接收软中断，在网卡只能中断固定CPU的情况下，这会影响并行性，比如只有两块网卡，却有16核CPU。如何将尽可能多的CPU核心调动起来呢？这需要修改网络接收软中断处理逻辑。我希望多个CPU轮流处理数据包，而不是固定被中断的数据包来处理。修改逻辑如下：
1.所有的rx softirq内核线程组成一个数组struct task_struct rx_irq_handler[NR_CPUS];
2.所有的poll list组成一个数组struct list_head polll[NR_CPUS];
3.引入一把保护上述数据的自旋锁spinlock_t rx_handler_lock;
4.修改NAPI的调度逻辑void __napi_schedule(struct napi_struct *n){ unsigned long flags;
static int curr = 0; unsigned int hash = curr %NR_CPUS; local_irq_save(flags); spin_lock(
线速问题
很多人对这个线速概念存在误解。认为所谓线速能力就是路由器/交换机就像一根网线一样。而这，是不可能的。应该考虑到的一个概念就是延迟。数据包进入路由器或者交换机，存在一个核心延迟操作，这就是选路，对于路由器而言，就是路由查找，对于交换机而言，就是查询MAC/端口映射表，这个延迟是无法避开的，这个操作需要大量的计算机资源，所以不管是路由器还是交换机，数据包在内部是不可能像在线缆上那样近光速传输的。类比一下你经过十字街头的时候，是不是要左顾右盼呢？
那么，设备的线速能力怎么衡量呢？如果一个数据包经过一个路由器，那么延迟必览无疑，可是设备都是有队列或者缓冲区的，那么试想一个数据包紧接一个数据包从输入端口进入设备，然后一个数据包紧接一个数据包从输出端口发出，这是可以做到的，我们对数据包不予编号，因此你也就无法判断出来的数据包是不是刚刚进去的那个了，这就是线速。
我们可以用电容来理解转发设备。有人可能会觉得电容具有通高频阻低频的功效，我说的不是这个，所以咱不考虑低频，仅以高频为例，电容具有存储电荷的功能，这就类似存储转发，电容充电的过程类似于数据包进入输入队列缓冲区，电容放电的过程类似于数据包从输出缓冲区输出，我们可以看到，在电流经过电容的前后，其速度是不变的，然而针对具体的电荷而言，从电容放出的电荷绝不是刚刚在在另一侧充电的那个电荷，电容的充电放电拥有固有延迟。
我们回到转发设备。对于交换机和路由器而言，衡量标准是不同的。
对于交换机而言，线速能力是背板总带宽，因为它的查表操作导致的延迟并不大，大量的操作都在数据包通过交换矩阵的过程，因此背板带宽直接导致了转发效率。而对于路由器，衡量标准则是一个端口每秒输入输出最小数据包的数量，假设数据包以每秒100个进入，每秒100个流出，那么其线速就是100pps。
本文针对路由器而不针对交换机。路由器的核心延迟在路由查找，而这个查找不会受到数据包长度的影响，因此决定路由器线速能力的核心就在数据包输出的效率，注意，不是数据包输入的效率，因为只要队列足够长，缓存足够大，输入总是线速的。但是输入操作就涉及到了如何调度的问题。这也就说明了为何很多路由器都支持输出流量控制而不是输入流量控制的原因，因为输入流控即使完美完成，它也会受到路由器输出端口自身输出效率的影响，流控结果将不再准确。
在写这个方案的前晚，有一个故事。我最近联系到了初中时一起玩摇滚玩音响的超级铁的朋友，他现在搞舞台设计，灯光音响之类的。我问他在大型舞台上，音箱摆放的位置不同，距离后级，前置，音源也不同，怎么做到不同声道或者相同声道的声音同步的，要知道，好的耳朵可以听出来毫秒级的音差...他告诉我要统一到达时间，即统一音频流到达各个箱子的时间，而这要做的就是调延迟，要求不同位置的箱子路径上要有不同的延迟。这对我的设计方案的帮助是多么地大啊。
然后，在第二天，我就开始整理这个令人悲伤最终心碎的Linux转发优化方案。
声明：本文只是一篇普通文章，记录这个方案的点点滴滴，并不是一个完整的方案，请勿在格式上较真，内容上也只是写了些我认为重要且有意思的。完整的方案是不便于以博文的形式发出来的。见谅。
问题综述
Linux内核协议栈作为一种软路由运行时，和其它通用操作系统自带的协议栈相比，其效率并非如下文所说的那样非常低。然而基于工业路由器的评判标准，确实是低了。 市面上各种基于Linux内核协议栈的路由器产品，甚至网上也有大量的此类文章，比如什么将Linux变成路由器之类的，无非就是打开ip_forward，加几条iptables规则，搞个配置起来比较方便的WEB界面...我想说这些太低级了，甚至超级低级。我很想谈一下关于专业路由器的我的观点，但是今天是小小的生日，玩了一天，就不写了。只是把我的方案整理出来吧。
Linux的转发效率到底低在哪儿？如何优化？这是本文要解释的问题。依然如故，本文可以随意转载并基于这个思路实现编码，但是一旦用于商业目的，不保证没有个人或组织追责，因此文中我尽量采用尽可能模糊的方式阐述细节。
瓶颈分析概述
1.DMA和内存操作我们考虑一下一个数据包转发流程中需要的内存操作，暂时不考虑DMA。*)数据包从网卡拷贝到内存*)CPU访问内存读取数据包元数据*)三层报头修改，如TTL*)转发到二层后封装MAC头*)数据包从内存拷贝到输出网卡这几个典型的内存操作为什么慢？为什么我们总是对内存操作有这么大的意见？因为访问内存需要经过总线，首先总线竞争(特别在SMP和DMA下)就是一个打群架的过程，另外因为内存自身的速度和CPU相比差了几个数量级，这么玩下去，肯定会慢啊！所以一般都是尽可能地使用CPU的cache，而这需要一定的针对局部性的数据布局，对于数据包接收以及其它IO操作而言，由于数据来自外部，和进程执行时的局部性利用没法比。所以必须采用类似Intel I/OAT的技术才能改善。
1.1.Linux作为服务器时采用标准零拷贝map技术完全胜任。这是因为，运行于Linux的服务器和线速转发相比就是个蜗牛，服务器在处理客户端请求时消耗的时间是一个硬性时间，无法优化，这是代偿原理。Linux服务唯一需要的就是能快速取到客户端的数据包，而这可以通过DMA快速做到。本文不再具体讨论作为服务器运行的零拷贝问题，自己百度吧。
1.2.Linux作为转发设备时需要采用DMA映射交换的技术才能实现零拷贝。这是Linux转发性能低下的根本。由于输入端口的输入队列和输出端口的输出队列互不相识，导致了不能更好的利用系统资源以及多端口数据路由到单端口输出队列时的队列锁开销过大，总线争抢太严重。DMA影射交换需要超级棒的数据包队列管理设施，它用来调度数据包从输入端口队列到输出端口队列，而Linux几乎没有这样的设施。虽然近年在路由器领域有人提出了输入队列管理，但是这项技术对于Linux而言就是另一个世界，而我，把它引入了Linux世界。
2.网卡对数据包队列Buff管理在Linux内核中，几乎对于所有数据结构，都是需要时alloc，完毕后free，即使是kmem_cache，效果也一般，特别是对于高速线速设备而言(skb内存拷贝，若不采用DMA，则会频繁拷贝，即便采用DMA，在很多情况下也不是零拷贝)。即使是高端网卡在skb的buffer管理方面，也没有使用完全意义上的预分配内存池，因此会由于频繁的内存分配，释放造成内存颠簸，众所周知，内存操作是问题的根本，因为它涉及到CPU Cache，总线争抢，原子锁等，实际上，内存管理才是根本中的根本，这里面道道太多，它直接影响CPU cache，后者又会影响总线...从哪里分配内存，分配多少，何时释放，何时可以重用，这就牵扯到了内存区域着色等技术。通过分析Intel千兆网卡驱动，在我看来，Linux并没有做好这一点。
3.路由查找以及其它查找操作Linux不区分对待路由表和转发表，每次都要最长前缀查找，虽然海量路由表时trie算法比hash算法好，但是在路由分布畸形的情况下依然会使trie结构退化，或者频繁回溯。路由cache效率不高（查询代价太大，不固定大小，仅有弱智的老化算法，导致海量地址访问时，路由cache冲突链过长），最终在内核协议栈中下课。如果没有一个好的转发表，那么Linux协议栈在海量路由存在时对于线速能力就是一个瓶颈，这是一个可扩展性问题。另外，很多的查询结果都是可以被在一个地方缓存的，但是Linux协议栈没有这种缓存。比如，路由查询结果就是下一跳，而下一跳和输出网卡关联，而输出网卡又和下一跳的MAC地址以及将要封装的源MAC地址关联，这些本应该被缓存在一个表项，即转发表项内，然而Linux协议栈没有这么做。
4.不合理的锁为何要加锁，因为SMP。然而Linux内核几乎是对称的加锁，也就是说，比如每次查路由表时都要加锁，为何？因为怕在查询的期间路由表改变了...然而你仔细想想，在高速转发情景下，查找操作和修改操作在单位时间的比率是多少呢？不要以为你用读写锁就好了，读写锁不也有关抢占的操作吗(虽然我们已经建议关闭了抢占)？起码也浪费了几个指令周期。这些时间几率不对称操作的加锁是不必要的。你只需要保证内核本身不会崩掉即可，至于说IP转发的错误，不管也罢，按照IP协议，它本身就是一个尽力而为的协议。
5.中断与软中断调度Linux的中断分为上半部和下半部，动态调度下半部，它可以在中断上下文中运行，也可以在独立的内核线程上下文中运行，因此对于实时需求的环境，在软中断中处理的协议栈处理的运行时机是不可预知的。Linux原生内核并没有实现Solaris，Windows那样的中断优先级化，在某些情况下，Linux靠着自己动态的且及其优秀的调度方案可以达到极高的性能，然而对于固定的任务，Linux的调度机制却明显不足。而我需要做的，就是让不固定的东西固定化。
6.通用操作系统内核协议栈的通病作为一个通用操作系统内核，Linux内核并非仅仅处理网络数据，它还有很多别的子系统，比如各种文件系统，各种IPC等，它能做的只是可用，简单，易扩展。Linux原生协议栈完全未经网络优化，且基本装机在硬件同样也未经优化的通用架构上，网卡接口在PCI-E总线上，如果DMA管理不善，总线的占用和争抢带来的性能开销将会抵消掉DMA本意带来的好处（事实上对于转发而言并没有带来什么好处，它仅仅对于作为服务器运行的Linux有好处，因为它只涉及到一块网卡）[ 注意，我认为内核处理路径并非瓶颈，这是分层协议栈决定的，瓶颈在各层中的某些操作，比如内存操作(固有开销)以及查表操作(算法不好导致的开销)]
综述：Linux转发效率受到以下几大因素影响
IO/输入输出的队列管理/内存修改拷贝 （重新设计类似crossbar的队列管理实现DMA ring交换）各种表查询操作，特别是最长前缀匹配，诸多本身唯一确定的查询操作之间的关联没有建立SMP下处理器同步（锁开销）（使用大读锁以及RCU锁）以及cache利用率中断以及软中断调度
Linux转发性能提升方案
概述此方案的思路来自基于crossbar的新一代硬件路由器。设计要点：
1.重新设计的DMA包管理队列（ 思路来自Linux O(1)调度器，crossbar阵列以及VOQ[虚拟输出队列]）2.重新设计的基于定位而非最长前缀查找的转发表3.长线程处理（中断线程化，处理流水线化，增加CPU亲和）4.数据结构无锁化（基于线程局部数据结构）5.实现方式5.1.驱动以及内核协议栈修改5.2.完全的用户态协议栈5.3.评估：用户态协议栈灵活，但是在某些平台要处理空间切换导致的cache/tlb/mmu表的flush问题
内核协议栈方案优化框架0.例行优化1).网卡多队列绑定特定CPU核心（利用RSS特性分别处理TX和RX）[ 可以参见《Effective Gigabit Ethernet Adapters-Intel千兆网卡8257X性能调优》]2).按照包大小统计动态开关积压延迟中断ThrottleRate以及中断Delay(对于Intel千兆卡而言)3).禁用内核抢占，减少时钟HZ，由中断粒度驱动（见上面）4).如果不准备优化Netfilter，编译内核时禁用Netfilter，节省指令5).编译选项去掉DEBUG和TRACE，节省指令周期6).开启网卡的硬件卸载开关（如果有的话）7).最小化用户态进程的数量，降低其优先级8).原生网络协议栈优化 由于不再作为通用OS，可以让除了RX softirq的task适当饥饿 *CPU分组(考虑Linux的cgroup机制)，划一组CPU为数据面CPU，每一个CPU绑定一个RX softirq或者 *增加rx softirq一次执行的netdev_budget以及time limit，或者 *只要有包即处理，每一个。控制面/管理面的task可以绑在别的CPU上。
宗旨：原生协议栈的最优化方案
1.优化I/O，DMA，减少内存管理操作1).减少PCI-E的bus争用,采用crossbar的全交叉超立方开关的方式[ Tips：16 lines 8 bits PCI-E总线拓扑(非crossbar！)的网络线速不到满载60% pps]2).减少争抢式DMA，减少锁总线[Tips：优化指令LOCK，最好采用RISC，方可调高内核HZ][ Tips：交换DMA映射，而不是在输入/输出buffer ring之间拷贝数据！现在，只有傻逼才会在DMA情况拷贝内存，正确的做法是DMA重映射，交换指针！]3).采用skb内存池，避免频繁内存分配/释放造成的内存管理框架内的抖动[ Tips：每线程负责一块网卡(甚至输入和输出由不同的线程负责会更好)，保持一个预分配可循环利用的ring buffer，映射DMA]
宗旨：减少cache刷新和tlb刷新，减少内核管理设施的工作(比如频繁的内存管理)
2.优化中断分发1).增加长路径支持，减少进程切换导致的TLB以及Cache刷新2).利用多队列网卡支持中断CPU亲和力利用或者模拟软多队列提高并行性3).牺牲用户态进程的调度机会，全部精力集中于内核协议栈的处理，多CPU多路并行的[ Tips：如果有超多的CPU，建议划分cgroup ]4).中断处理线程化，内核线程化，多核心并行执行长路经，避免切换抖动5).线程内部，按照IXA NP微模块思想采用模块化(方案未实现，待商榷)
宗旨：减少cache刷新和tlb刷新减少协议栈处理被中断过于频繁打断[ 要么使用IntRate，要么引入中断优先级]
3.优化路由查找算法1).分离路由表和转发表，路由表和转发表同步采用RCU机制2).尽量采用线程局部数据每个线程一张转发表（由路由表生成，OpenVPN多线程采用，但失败），采用定位而非最长前缀查找（DxR或者我设计的那个）。若不采用为每个线程复制一份转发表，则需要重新设计RW锁或者使用RCU机制。3).采用hash/trie方式以及DxR或者我设计的DxRPro定位结构
宗旨：采用定位而非查找结构采用局部表，避免锁操作
4.优化lock1).查询定位局部表，无锁（甚至RW锁都没有）不禁止中断2).临界区和内核线程关联，不禁中断，不禁抢占（其实内核编译时抢占已经关闭了）3).优先级锁队列替换争抢模型，维持cache热度4).采用Windows的自旋锁机制[ Tips：Linux的ticket spin lock由于采用探测全局lock的方式，会造成总线开销和CPU同步开销，Windows的spin lock采用了探测CPU局部变量的方式实现了真正的队列lock，我设计的输入输出队列管理结构(下面详述)思路部分来源于Windows的自旋锁设计]
宗旨：锁的粒度与且仅与临界区资源关联，粒度最小化
优化细节概览1.DMA与输入输出队列优化
1.1.问题出在哪儿如果你对Linux内核协议栈足够熟悉，那么就肯定知道，Linux内核协议栈正是由于软件工程里面的天天普及的“一件好事”造成了转发性能低效。这就是“解除紧密耦合”。Linux协议栈转发和Linux服务器之间的根本区别在于，后者的应用服务并不在乎数据包输入网卡是哪个，它也不必关心输出网卡是哪一个，然而对于Linux协议栈转发而言，输入网卡和输出网卡之间确实是有必要相互感知的。Linux转发效率低的根本原因不是路由表不够高效，而是它的队列管理以及I/O管理机制的低效，造成这种低效的原因不是技术实现上难以做到，而是Linux内核追求的是一种灵活可扩展的性能，这就必须解除出入网卡，驱动和协议栈之间关于数据包管理的紧密耦合。我们以Intel千兆网卡驱动e1000e来说明上述的问题。顺便说一句，Intel千兆驱动亦如此，其它的就更别说了，其根源在于通用的网卡驱动和协议栈设计并不是针对转发优化的。
初始化：创建RX ring：RXbuffinfo[MAX]创建TX ring：TXbuffinfo[MAX]
RX过程：i = 当前RX ring游历到的位置;while(RXbuffinfo中有可用skb) { skb = RXbufferinfo[i].skb; RXbuffinfo[i].skb = NULL; i ; DMA_unmap(RXbufferinfo[i].DMA); [Tips：至此，skb已经和驱动脱离，完全交给了Linux协议栈] [Tips：至此，skb内存已经不再由RX ring维护，Linux协议栈拽走了skb这块内存] OS_receive_skb(skb); [Tips：由Linux协议栈负责释放skb，调用kfree_skb之类的接口] if (RX ring中被Linux协议栈摘走的skb过多) { alloc_new_skb_from_kmem_cache_to_RXring_RXbufferinfo_0_to_MAX_if_possible; [Tips：从Linux核心内存中再次分配skb] }}
TX过程：skb = 来自Linux协议栈dev_hard_xmit接口的数据包;i = TX ring中可用的位置TXbufferinfo[i].skb = skb;DMA_map(TXbufferinfo[i].DMA);while(TXbufferinfo中有可用的skb) { DMA_transmit_skb(TXbufferinfo[i]);}[异步等待传输完成中断或者在NAPI poll中主动调用]i = 传输完成的TXbufferinfo索引while(TXbufferinfo中有已经传输完成的skb) { skb = TXbufferinfo[i]; DMA_unmap(TXbufferinfo[i].DMA); kfree(skb); i ;}以上的流程可以看出，在持续转发数据包的时候，会涉及大量的针对skb的alloc和free操作。如果你觉得上面的代码不是那么直观，那么下面给出一个图示：
频繁的会发生从Linux核心内存中alloc skb和free skb的操作，这不仅仅是不必要的，而且还会损害CPU cache的利用。不要寄希望于keme_cache，我们可以看到，所有的网卡和socket几乎是共享一块核心内存的，虽然可以通过dev和kmem cache来优化，但很遗憾，这个优化没有质的飞跃。
1.2.构建新的DMA ring buffer管理设施-VOQ，建立输入/输出网卡之间队列的关联。类比Linux O(1)调度器算法，每一个cpu全局维护一个唯一的队列，散到各个网卡，靠交换队列的DMA映射指针而不是拷贝数据的方式优化性能，达到零拷贝，这只是其一。关于交换DMA映射指针而不是拷贝数据这一点不多谈，因为几乎所有的支持DMA的网卡驱动都是这么做的，如果它们不是这么做的，那么肯定有人会将代码改成这么做的。如果类比高端路由器的crossbar交换阵列结构以及真实的VOQ实现，你会发现，在逻辑上，每一对可能的输入/输出网卡之间维护一条数据转发通路是避免队头阻塞以及竞争的好方法。这样排队操作只会影响单独的网卡，不需要再全局加锁。在软件实现上，我们同样可以做到这个。你要明白，Linux的网卡驱动维护的队列信息被内核协议栈给割裂，从此，输入/输出网卡之间彼此失联，导致最优的二分图算法无法实施。事实上，你可能觉得把网卡作为一个集合，把需要输出的数据包最为另一个集合，转发操作需要做的就是建立数据包和网卡之间的一条路径，这是一个典型的二分图匹配问题，然而如果把建立路径的操作与二分图问题分离，这就是不再是网卡和数据包之间的二分图匹配问题了。因为分离出来的路由模块导致了针对每一个要转发的数据包，其输出网卡是唯一确定的。这个问题变成了处理输出网卡输出操作的CPU集合和输出网卡之间的二分图匹配问题。这里有一个优化点，那就是如果你有多核CPU，那么就可以为每一块网卡的输出操作绑定一个唯一的CPU，二分图匹配问题迎刃而解，剩下的就是硬件总线的争用问题(对于高性能crossbar路由器而言，这也是一个二分图匹配问题，但对于总线结构的通用系统而言有点区别，后面我会谈到)了，作为我们而言，这一点除了使用性价比更高的总线，比如我们使用PCI-E 16Lines 8 bits，没有别的办法。作为一个完全的方案，我不能寄希望于底层存在一个多核CPU系统，如果只有一个CPU，那么我们能寄希望于Linux进程调度系统吗？还是那个观点，作为一个通用操作系统内核，Linux不会针对网络转发做优化，于是乎，进程调度系统是此方案的另一个优化点，这个我后面再谈。最后，给出我的数据包队列管理VOQ的设计方案草图。
在我的这个针对Linux协议栈的VOQ设计中，VOQ总要要配合良好的输出调度算法，才能发挥出最佳的性能。
2.分离路由表和转发表以及建立查找操作之间的关联Linux协议栈是不区分对待路由表和转发表的，而这在高端路由器上显然是必须的。诚然，我没有想将Linux协议栈打造成比肩专业路由器的协议栈，然而通过这个排名第二的核心优化，它的转发效率定会更上一层楼。在大约三个月前，我参照DxR结构以及借鉴MMU思想设计了一个用于转发的索引结构，可以实现3步定位，无需做最长前缀匹配过程，具体可以参见我的这篇文章 《以DxR算法思想为基准设计出的路由项定位结构图解》，我在此就不再深度引用了。需要注意的是，这个结构可以根据现行的Linux协议栈路由FIB生成，而且在路由项不规则的情况下可以在最差情况下动态回退到标准DxR，比如路由项不可汇聚，路由项在IPv4地址空间划分区间过多且分布不均。我将我设计的这个结构称作DxR Pro 。至于说查找操作之间的关联，这也是一个深度优化，底层构建高速查询流表实现协议栈短路（流表可参照conntrack设计），这个优化思想直接参照了Netfilter的conntrack以及SDN流表的设计。虽然IP网络是一个无状态网络，中间路由器的转发策略也应该是一个无状态的转发。然而这是形而上意义上的理念。如果谈到深度优化，就不得不牺牲一点纯洁性。设计一个流表，流的定义可以不必严格按照五元组，而是可以根据协议头的任意字段，每一个表项中保存的信息包括但不限于以下的元素：*流表缓存路由项*流表缓存neighbour*流表缓存NAT*流表缓存ACL规则 *流表缓存二层头信息这样可以在协议栈的底层保存一张可以高速查询的流表，协议栈收到skb后匹配这张表的某项，一旦成功，可以直接取出相关的数据(比如路由项)直接转发，理论上只有一个流的第一个数据包会走标准协议栈的慢速路径(事实上，经过DxR Pro 的优化，一经不慢了...)。在直接快速转发中，需要执行一个HOOK，执行标准的例行操作，比如校验和，TTL递减等。 关于以上的元素，特别要指出的是和neighbour与二层信息相关的。数据转发操作一向被认为瓶颈在发不在收，在数据发送过程，会涉及到以下耗时的操作：>添加输出网卡的MAC地址作为源-内存拷贝>添加next hop的MAC地址作为目标-内存拷贝又一次，我们遇到了内存操作，恼人的内存操作！如果我们把这些MAC地址保存在流表中，可以避免吗？貌似只是可以快速定位，而无法避免内存拷贝...再一次的，我们需要硬件的特性来帮忙，这就是分散聚集I/O(Scatter-gather IO)，原则上，Scatter-gather IO可以将不连续的内存当成连续的内存使用，进而直接映射DMA，因此我们只需要告诉控制器，一个将要发送的帧的MAC头的位置在哪里，DMA就可以直接传输，没有必要将MAC地址拷贝到帧头的内存区域。如下图所示：
特别要注意，上述的流表缓存项中的数据存在大量冗余，因为next hop的MAC地址，输出网卡的MAC地址，这些是可以由路由项唯一确定的。之所以保存冗余数据，其原则还是为了优化，而标准的通用Linux内核协议栈，它却是要避免冗余的...既然保存了冗余数据，那么慢速路径的数据项和快速路经的数据项之间的同步就是一个必须要解决的问题。我基于读写的不对称性，着手采用event的方式通知更新，比如慢速路径中的数据项(路由，MAC信息，NAT，ACL信息等)，一旦这些信息更改，内核会专门触发一个查询操作，将快速流表中与之相关的表项disable掉即可。值得注意的是，这个查询操作没必要太快，因为相比较快速转发而言，数据同步的频率要慢天文数字个数量级...类似Cisco的设备，可以创建几个内核线程定期刷新慢速路径表项，用来发现数据项的更改，从而触发event。
[Tips：可以高速查找的流表结构可用多级hash（采用TCAM的类似方案），也可以借鉴我的DxR Pro 结构以及nf-HiPac算法的多维区间匹配结构，我个人比较推崇nf-HiPac]
3.路由Cache优化虽说Linux的路由cache早已下课，但是它下课的原因并不是cache机制本身不好，而是Linux的路由cache设计得不好。因此以下几点可以作为优化点来尝试。*)限制路由软cache的大小，保证查找速度[实施精心设计的老化算法和替换算法][ 利用互联网访问的时间局部性以及空间局部性（需要利用计数统计）][ 自我PK：如果有了我的那个3步定位结构，难道还用的到路由cache吗]*)预制常用IP地址到路由cache，实现一步定位[ 所谓常用IP需要根据计数统计更新，也可以静态设置]
4.Softirq在不支持RSS多队列网卡时的NAPI调度优化*)将设备按照协议头hash值均匀放在不同CPU，远程唤醒softirq，模拟RSS软实现目前的网络接收软中断的处理机制是，哪个CPU被网卡中断了，哪个CPU就处理网卡接收软中断，在网卡只能中断固定CPU的情况下，这会影响并行性，比如只有两块网卡，却有16核CPU。如何将尽可能多的CPU核心调动起来呢？这需要修改网络接收软中断处理逻辑。我希望多个CPU轮流处理数据包，而不是固定被中断的数据包来处理。修改逻辑如下：
1.所有的rx softirq内核线程组成一个数组struct task_struct rx_irq_handler[NR_CPUS];
2.所有的poll list组成一个数组struct list_head polll[NR_CPUS];
3.引入一把保护上述数据的自旋锁spinlock_t rx_handler_lock;
4.修改NAPI的调度逻辑void __napi_schedule(struct napi_struct *n){ unsigned long flags;
static int curr = 0; unsigned int hash = curr %NR_CPUS; local_irq_save(flags); spin_lock(
下载文档
