Linux转发性能评估与优化(转发瓶颈分析与解决方案)

线速问题

很多人对这个线速概念存在误解。认为所谓线速能力就是路由器/交换机就像一根网线一样。而这，是不可能的。应该考虑到的一个概念就是延迟。数据包进入路由器或者交换机，存在一个核心延迟操作，这就是选路，对于路由器而言，就是路由查找，对于交换机而言，就是查询MAC/端口映射表，这个延迟是无法避开的，这个操作需要大量的计算机资源，所以不管是路由器还是交换机，数据包在内部是不可能像在线缆上那样近光速传输的。类比一下你经过十字街头的时候，是不是要左顾右盼呢？
声明：本文只是一篇普通文章，记录这个方案的点点滴滴，并不是一个完整的方案，请勿在格式上较真，内容上也只是写了些我认为重要且有意思的。完整的方案是不便于以博文的形式发出来的。见谅。
问题综述Linux内核协议栈作为一种软路由运行时，和其它通用操作系统自带的协议栈相比，其效率并非如下文所说的那样非常低。然而基于工业路由器的评判标准，确实是低了。
瓶颈分析概述
1.DMA和内存操作我们考虑一下一个数据包转发流程中需要的内存操作，暂时不考虑DMA。
1.1.Linux作为服务器时采用标准零拷贝map技术完全胜任。这是因为，运行于Linux的服务器和线速转发相比就是个蜗牛，服务器在处理客户端请求时消耗的时间是一个硬性时间，无法优化，这是代偿原理。Linux服务唯一需要的就是能快速取到客户端的数据包，而这可以通过DMA快速做到。本文不再具体讨论作为服务器运行的零拷贝问题，自己百度吧。
1.2.Linux作为转发设备时需要采用DMA映射交换的技术才能实现零拷贝。这是Linux转发性能低下的根本。由于输入端口的输入队列和输出端口的输出队列互不相识，导致了不能更好的利用系统资源以及多端口数据路由到单端口输出队列时的队列锁开销过大，总线争抢太严重。DMA影射交换需要超级棒的数据包队列管理设施，它用来调度数据包从输入端口队列到输出端口队列，而Linux几乎没有这样的设施。
2.网卡对数据包队列Buff管理在Linux内核中，几乎对于所有数据结构，都是需要时alloc，完毕后free，即使是kmem_cache，效果也一般，特别是对于高速线速设备而言(skb内存拷贝，若不采用DMA，则会频繁拷贝，即便采用DMA，在很多情况下也不是零拷贝)。
3.路由查找以及其它查找操作Linux不区分对待路由表和转发表，每次都要最长前缀查找，虽然海量路由表时trie算法比hash算法好，但是在路由分布畸形的情况下依然会使trie结构退化，或者频繁回溯。路由cache效率不高（查询代价太大，不固定大小，仅有弱智的老化算法，导致海量地址访问时，路由cache冲突链过长），最终在内核协议栈中下课。
4.不合理的锁为何要加锁，因为SMP。然而Linux内核几乎是对称的加锁，也就是说，比如每次查路由表时都要加锁，为何？因为怕在查询的期间路由表改变了...然而你仔细想想，在高速转发情景下，查找操作和修改操作在单位时间的比率是多少呢？不要以为你用读写锁就好了，读写锁不也有关抢占的操作吗(虽然我们已经建议关闭了抢占)？起码也浪费了几个指令周期。这些时间几率不对称操作的加锁是不必要的。
5.中断与软中断调度Linux的中断分为上半部和下半部，动态调度下半部，它可以在中断上下文中运行，也可以在独立的内核线程上下文中运行，因此对于实时需求的环境，在软中断中处理的协议栈处理的运行时机是不可预知的。Linux原生内核并没有实现Solaris，Windows那样的中断优先级化，在某些情况下，Linux靠着自己动态的且及其优秀的调度方案可以达到极高的性能，然而对于固定的任务，Linux的调度机制却明显不足。
6.通用操作系统内核协议栈的通病作为一个通用操作系统内核，Linux内核并非仅仅处理网络数据，它还有很多别的子系统，比如各种文件系统，各种IPC等，它能做的只是可用，简单，易扩展。
注意，我认为内核处理路径并非瓶颈，这是分层协议栈决定的，瓶颈在各层中的某些操作，比如内存操作(固有开销)以及查表操作(算法不好导致的开销)]
综述：Linux转发效率受到以下几大因素影响
Linux转发性能提升方案

概述

此方案的思路来自基于crossbar的新一代硬件路由器。设计要点：
思路来自Linux O(1)调度器，crossbar阵列以及VOQ[虚拟输出队列]）
内核协议栈方案

优化框架

0.例行优化

1).网卡多队列绑定特定CPU核心（利用RSS特性分别处理TX和RX）
可以参见《Effective Gigabit Ethernet Adapters-Intel千兆网卡8257X性能调优》]
1.优化I/O，DMA，减少内存管理操作 1).减少PCI-E的bus争用,采用crossbar的全交叉超立方开关的方式
Tips：16 lines 8 bits PCI-E总线拓扑(非crossbar！)的网络线速不到满载60% pps]
Tips：交换DMA映射，而不是在输入/输出buffer ring之间拷贝数据！现在，只有傻逼才会在DMA情况拷贝内存，正确的做法是DMA重映射，交换指针！]
Tips：每线程负责一块网卡(甚至输入和输出由不同的线程负责会更好)，保持一个预分配可循环利用的ring buffer，映射DMA]
2.优化中断分发1).增加长路径支持，减少进程切换导致的TLB以及Cache刷新
[Tips：如果有超多的CPU，建议划分cgroup]
要么使用IntRate，要么引入中断优先级]
3.优化路由查找算法1).分离路由表和转发表，路由表和转发表同步采用RCU机制
4.优化lock1).查询定位局部表，无锁（甚至RW锁都没有）不禁止中断
Tips：Linux的ticket spin lock由于采用探测全局lock的方式，会造成总线开销和CPU同步开销，Windows的spin lock采用了探测CPU局部变量的方式实现了真正的队列lock，我设计的输入输出队列管理结构(下面详述)思路部分来源于Windows的自旋锁设计]
宗旨：锁的粒度与且仅与临界区资源关联，粒度最小化

优化细节概览

1.DMA与输入输出队列优化

1.1.问题出在哪儿如果你对Linux内核协议栈足够熟悉，那么就肯定知道，Linux内核协议栈正是由于软件工程里面的天天普及的“一件好事”造成了转发性能低效。这就是“解除紧密耦合”。
创建RX ring：RXbuffinfo[MAX]

i = 当前RX ring游历到的位置;

skb = 来自Linux协议栈dev_hard_xmit接口的数据包;
以上的流程可以看出，在持续转发数据包的时候，会涉及大量的针对skb的alloc和free操作。如果你觉得上面的代码不是那么直观，那么下面给出一个图示：
vcq908W7r9DUxNyjrLTvtb3B47+9sbSjrNXi1rvKx8bk0ruho7nY09q9u7u7RE1B07PJ5Na41eu2+LK7yse/vbG0yv2+3dXi0ru147K7tuDMuKOs0vLOqry4uvXL+dPQtcTWp7PWRE1BtcTN+L+ox/22r7a8ysfV4sO01/a1xKOsyOe5+8v8w8eyu8rH1eLDtNf2tcSjrMTHw7S/z7ao09DIy7vhvau0+sLruMSzydXiw7TX9rXEoaM8YnIgLyZndDs8YnIgLyZndDsgICAgICAgyOe5+8Dgsci437bLwrfTycb3tcRjcm9zc2Jhcr27u7vV88HQveG5udLUvLDV5sq1tcRWT1HKtc/Wo6zE47vht6LP1qOs1NrC37ytyc+jrMO/0ru21L/JxNy1xMrkyOsvyuSz9s34v6jWrrzkzqy7pNK7zPXK/b7d16q3os2owrfKx7Hcw+K208231+jI+9LUvLC+utX5tcS6w7e9t6iho9Xi0fnFxbbTstnX99a7u+HTsM/staW2wLXEzfi/qKOssrvQ6NKq1NnIq77WvNPL+KGj1NrI7bz+yrXP1snPo6zO0sPHzazR+b/J0tTX9rW91eK49qGjxOPSqsP3sNejrExpbnV4tcTN+L+ox/22r86su6S1xLbTwdDQxc+isbvE2rrL0K3S6dW7uPi47sHRo6y007TLo6zK5MjrL8rks/bN+L+o1q685LHLtMvKp8Gqo6y1vNbC1+7TxbXEtv631s28y+O3qM7et6jKtcqpoaM8YnIgLyZndDs8YnIgLyZndDsgICAgICAgysLKtcnPo6zE47/JxNy+9bXDsNHN+L+o1/fOqtK7uPa8r7rPo6yw0dDo0qrK5LP2tcTK/b7dsPzX7s6qwe3Su7j2vK+6z6Os16q3orLZ1/fQ6NKq1/a1xL7Nyse9qMGiyv2+3bD8us3N+L+o1q685LXE0rvM9cK3vrajrNXiysfSu7j2teTQzbXEtv631s28xqXF5M7KzOKjrMi7tvjI57n7sNG9qMGiwre+trXEstnX99Prtv631s28zsrM4rfWwOujrNXivs3Kx7K71NnKx834v6i6zcr9vt2w/NauvOS1xLb+t9bNvMalxeTOysziwcuho9Lyzqq31sDrs/bAtLXEwrfTycSjv+m1vNbCwcvV67bUw7/Su7j20qrXqreitcTK/b7dsPyjrMbkyuSz9s34v6jKx86o0rvIt7aotcSho9XiuPbOysziseSzycHLtKbA7crks/bN+L+oyuSz9rLZ1/e1xENQVbyvus+6zcrks/bN+L+o1q685LXEtv631s28xqXF5M7KzOKhozxiciAvJmd0OzxiciAvJmd0OyAgICAgICDV4sDv09DSu7j208W7r7Xjo6zEx77NysfI57n7xOPT0LbgustDUFWjrMTHw7S+zb/J0tTOqsO/0ru/6c34v6i1xMrks/ay2df3sPO2qNK7uPbOqNK7tcRDUFWjrLb+t9bNvMalxeTOyszi063I0Lb4veKjrMqjz8K1xL7NysfTsrz+19zP37XE1fnTw87KzOIottTT2rjf0NTE3GNyb3NzYmFywrfTycb3tvjR1KOs1eLSssrH0ru49rb+t9bNvMalxeTOyszio6y1q7bU09rX3M/fveG5ubXEzajTw8+1zbO2+NHU09C148f4sfCjrLrzw+bO0rvhzLi1vSnBy6Os1/fOqs7Sw8e2+NHUo6zV4tK7teOz/cHLyrnTw9DUvNuxyLj8uN+1xNfcz9+jrLHIyOfO0sPHyrnTw1BDSS1FIDE2TGluZXMgOCBiaXRzo6zDu9PQsfC1xLDst6iho9f3zqrSu7j2zerIq7XEt72wuKOsztKyu8TcvMTPo83709q117LjtObU2tK7uPa24LrLQ1BVz7XNs6OsyOe5+9a709DSu7j2Q1BVo6zEx8O0ztLDx8TcvMTPo83709pMaW51eL34s8y197bIz7XNs8Lwo7+7ucrHxMe49rnbteOjrNf3zqrSu7j2zajTw7LZ1/fPtc2zxNq6y6OsTGludXiyu7vh1eu21M34wufXqrei1/bTxbuvo6zT2srHuvWjrL34s8y197bIz7XNs8rHtMu3vbC4tcTB7dK7uPbTxbuvteOjrNXiuPbO0rrzw+bU2cy4oaM8YnIgLyZndDs8YnIgLyZndDsgICAgICAg1+6686OsuPiz9s7StcTK/b7dsPy208HQudzA7VZPUbXEyei8xre9sLiy3c28oaM8YnIgLyZndDs8YnIgLyZndDs8aW1nIHNyYz0="http://img.blog.csdn.net/20150628002027364?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvZG9nMjUw/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="\" />
2.分离路由表和转发表以及建立查找操作之间的关联Linux协议栈是不区分对待路由表和转发表的，而这在高端路由器上显然是必须的。诚然，我没有想将Linux协议栈打造成比肩专业路由器的协议栈，然而通过这个排名第二的核心优化，它的转发效率定会更上一层楼。
《以DxR算法思想为基准设计出的路由项定位结构图解》，我在此就不再深度引用了。需要注意的是，这个结构可以根据现行的Linux协议栈路由FIB生成，而且在路由项不规则的情况下可以在最差情况下动态回退到标准DxR，比如路由项不可汇聚，路由项在IPv4地址空间划分区间过多且分布不均。我将我设计的这个结构称作DxR Pro++。
*流表缓存路由项

[Tips：可以高速查找的流表结构可用多级hash（采用TCAM的类似方案），也可以借鉴我的DxR Pro++结构以及nf-HiPac算法的多维区间匹配结构，我个人比较推崇nf-HiPac]

3.路由Cache优化

虽说Linux的路由cache早已下课，但是它下课的原因并不是cache机制本身不好，而是Linux的路由cache设计得不好。因此以下几点可以作为优化点来尝试。
利用互联网访问的时间局部性以及空间局部性（需要利用计数统计）]
自我PK：如果有了我的那个3步定位结构，难道还用的到路由cache吗]
所谓常用IP需要根据计数统计更新，也可以静态设置]
4.Softirq在不支持RSS多队列网卡时的NAPI调度优化*)将设备按照协议头hash值均匀放在不同CPU，远程唤醒softirq，模拟RSS软实馅喎?http://www.Bkjia.com/kf/yidong/wp/" target="_blank" class="keylink">WPGJyIC8mZ3Q7xL/HsLXEzfjC573TytXI7dbQts+1xLSmwO27+tbGysejrMTEuPZDUFWxu834v6jW0LbPwcujrMTEuPZDUFW+zbSmwO3N+L+ovdPK1cjt1tC2z6Os1NrN+L+o1rvE3NbQts+5zLaoQ1BVtcTH6b/2z8KjrNXiu+HTsM/ssqLQ0NDUo6yxyMjn1rvT0MG9v+nN+L+oo6zItNPQMTa6y0NQVaGjyOe6zr2rvqG/ycTctuC1xENQVbrL0MS197avxvDAtMTYo7/V4tDo0qrQ3rjEzfjC573TytXI7dbQts+0psDtwt+8raGjztLPo837tuC49kNQVcLWwfe0psDtyv2+3bD8o6y2+LK7yse5zLaosbvW0LbPtcTK/b7dsPzAtLSmwO2ho9DeuMTC37ytyOfPwqO6PGJyIC8mZ3Q7PGJyIC8mZ3Q7PHN0cm9uZz4xLsv509C1xHJ4IHNvZnRpcnHE2rrLz9+zzNfps8nSu7j2yv3X6Twvc3Ryb25nPjxiciAvJmd0OzxwcmUgY2xhc3M9"brush:java;">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(&rx_handler_lock); list_add_tail(&n->poll_list, polll[hash]); local_softirq_pending(hash) |= NET_RX_SOFTIRQ; spin_unlock(&rx_handler_lock); local_irq_restore(flags); }
Tips：注意和DMA/DCA，CPU cache亲和的结合，如果连DMA都不支持，那他妈的还优化个毛]
*)延长net softirq的执行时间，有包就一直dispatch loop。管理/控制平面进程被划分到独立的cgroup/cpuset中。
5.Linux调度器相关的修改这个优化涉及到方案的完备性，毕竟我们不能保证CPU核心的数量一定大于网卡数量的2倍(输入处理和输出处理分离)，那么就必须考虑输出事件的调度问题。
//只要有skb排队，无条件setbit setbit(outcart, incard); //只要有skb排队，则将与输出网卡关联的输出线程的虚拟时间减去一个值，该值由数据包长度与常量归一化计算所得。 outcard_tx_task_dec_vruntime(outcard, skb->len);
6.内置包分类和包过滤的情况这是一个关于Netfilter优化的话题，Netfilter的性能一直被人诟病，其很大程度上都是由于iptables造成的，一定要区分对待Netfilter和iptables。当然排除了这个误会，并不表明Netfilter就完全无罪。Netfilter是一个框架，它本身在我们已经关闭了抢占的情况下是没有锁开销的，关键的在它内部的HOOK遍历执行中，作为一些callback，内部的逻辑是不受控制的，像iptables，conntrack(本来数据结构粒度就很粗-同一张hash存储两个方向的元组，又使用大量的大粒度锁，内存不紧张时我们可以多用几把锁，空间换自由，再说，一把锁能占多大空间啊)，都是吃性能的大户，而nf-HiPac就好很多。因此这部分的优化不好说。
*)预处理ACL或者NAT的ruleset（采用nf-hipac方案替换非预处理的逐条匹配）
]
*)包调度算法（CFS队列，RB树存储包到达时间*h(x)，h为包长的函数）
7.作为容器的skbskb作为一个数据包的容器存在，它要和真正的数据包区分开来，事实上，它仅仅作为一个数据包的载体，像一辆卡车运载数据包。它是不应该被释放的，永远不该被释放。每一块网卡都应该拥有自己的卡车车队，如果我们把网卡看作是航空港，Linux路由器看作是陆地，那么卡车从空港装载货物(数据包)，要么把它运输到某个目的地(Linux作为服务器)，要么把它运输到另一个空港(Linux作为转发路由器)，其间这辆卡车运送个来回即可，这辆卡车一直属于货物到达的那个空港，将货物运到另一个空港后空车返回即可。卡车的使用不必中心调度，更无需用完后销毁，用的时候再造一辆(Linux的转发瓶颈即在此！！！)。
用户态协议栈方案

1.争议

在某些平台上，如果不解决user/kernel切换时的cache，tlb刷新开销，这种方案并不是我主推的，这些平台上不管是写直通还是写回，访问cache都是不经MMU的，也不cache mmu权限，且cache直接使用虚地址。
2.争议解决方案可以采用Intel I/OAT的DCA技术，避免上下文切换导致的cache抖动
3.采用PF_RING的方式修改驱动，直接与DMA buffer ring关联（参见内核方案的DMA优化）。
4.借鉴Tilera的RISC超多核心方案并行流水线处理每一层，流水级数为同时处理的包的数量，CPU核心数+2，流水数量为处理模块的数量。
流水线倒立]
稳定性

对于非专业非大型路由器，稳定性问题可以不考虑，因为无需7*24，故障了大不了重启一下而已，无伤大雅。但是就技术而言，还是有几点要说的。在高速总线情形下，并行总线容易窜扰，内存也容易故障，一个位的错误，一个电平的不稳定都会引发不可预知的后果，所以PCI-E这种高速总线都采用串行的方式传输数据，对于硬盘而言，SATA也是一样的道理。

在多网卡DMA情况下，对于通过的基于PCI-E的设备而言，总线上的群殴是很激烈的，这是总线这种拓扑结构所决定的，和总线类型无关，再考虑到系统总线和多CPU核心，这种群殴会更加激烈，因为CPU们也会参与进来。群殴的时候，打翻桌椅而不是扳倒对方是很常有的事，只要考虑一下这种情况，我就想为三年前我与客户的一次争吵而向他道歉。

2012年，我做一个VPN项目，客户说我的设备可能下一秒就会宕机，因为不确定性。我说if(true) {printf("cao ni ma!\n")(当然当时我不敢这么说);确定会执行吗？他说不一定。我就上火了...可是现在看来，他是对的。
VOQ设计后良好的副作用-QoSVOQ是本方案的一个亮点，本文几乎是围绕VOQ展开的，关于另一个亮点DxR Pro，在其它的文章中已经有所阐述，本文只是加以引用而已。临近末了，我再次提到了VOQ，这次是从一个宏观的角度，而不是细节的角度来加以说明。
VOQ设计后良好的副作用-队头拥塞以及加速比问题
总线拓扑和Crossbar
系统。因此，期待直接使用高效的kmem_cache并不是一个好的主意。
最后的声明本文仅仅是针对Linux做的转发调优方案，如果需要更加优化的方案， 请参考ASIC以及NP等硬件方案，不要使用总线拓扑，而是使用交叉阵列拓扑。