線(xiàn)速問(wèn)題

很多人對(duì)這個(gè)線(xiàn)速概念存在誤解。認(rèn)為所謂線(xiàn)速能力就是路由器/交換機(jī)就像一根網(wǎng)線(xiàn)一樣。而這，是不可能的。應(yīng)該考慮到的一個(gè)概念就是延遲。數(shù)據(jù)包進(jìn)入路由器或者交換機(jī)，存在一個(gè)核心延遲操作，這就是選路，對(duì)于路由器而言，就是路由查找，對(duì)于交換機(jī)而言，就是查詢(xún)MAC/端口映射表，這個(gè)延遲是無(wú)法避開(kāi)的，這個(gè)操作需要大量的計(jì)算機(jī)資源，所以不管是路由器還是交換機(jī)，數(shù)據(jù)包在內(nèi)部是不可能像在線(xiàn)纜上那樣近光速傳輸?shù)?。?lèi)比一下你經(jīng)過(guò)十字街頭的時(shí)候，是不是要左顧右盼呢？

那么，設(shè)備的線(xiàn)速能力怎么衡量呢？如果一個(gè)數(shù)據(jù)包經(jīng)過(guò)一個(gè)路由器，那么延遲必覽無(wú)疑，可是設(shè)備都是有隊(duì)列或者緩沖區(qū)的，那么試想一個(gè)數(shù)據(jù)包緊接一個(gè)數(shù)據(jù)包從輸入端口進(jìn)入設(shè)備，然后一個(gè)數(shù)據(jù)包緊接一個(gè)數(shù)據(jù)包從輸出端口發(fā)出，這是可以做到的，我們對(duì)數(shù)據(jù)包不予編號(hào)，因此你也就無(wú)法判斷出來(lái)的數(shù)據(jù)包是不是剛剛進(jìn)去的那個(gè)了，這就是線(xiàn)速。

我們可以用電容來(lái)理解轉(zhuǎn)發(fā)設(shè)備。有人可能會(huì)覺(jué)得電容具有通高頻阻低頻的功效，我說(shuō)的不是這個(gè)，所以咱不考慮低頻，僅以高頻為例，電容具有存儲(chǔ)電荷的功能，這就類(lèi)似存儲(chǔ)轉(zhuǎn)發(fā)，電容充電的過(guò)程類(lèi)似于數(shù)據(jù)包進(jìn)入輸入隊(duì)列緩沖區(qū)，電容放電的過(guò)程類(lèi)似于數(shù)據(jù)包從輸出緩沖區(qū)輸出，我們可以看到，在電流經(jīng)過(guò)電容的前后，其速度是不變的，然而針對(duì)具體的電荷而言，從電容放出的電荷絕不是剛剛在在另一側(cè)充電的那個(gè)電荷，電容的充電放電擁有固有延遲。

我們回到轉(zhuǎn)發(fā)設(shè)備。對(duì)于交換機(jī)和路由器而言，衡量標(biāo)準(zhǔn)是不同的。

對(duì)于交換機(jī)而言，線(xiàn)速能力是背板總帶寬，因?yàn)樗牟楸聿僮鲗?dǎo)致的延遲并不大，大量的操作都在數(shù)據(jù)包通過(guò)交換矩陣的過(guò)程，因此背板帶寬直接導(dǎo)致了轉(zhuǎn)發(fā)效率。而對(duì)于路由器，衡量標(biāo)準(zhǔn)則是一個(gè)端口每秒輸入輸出最小數(shù)據(jù)包的數(shù)量，假設(shè)數(shù)據(jù)包以每秒100個(gè)進(jìn)入，每秒100個(gè)流出，那么其線(xiàn)速就是100pps。

本文針對(duì)路由器而不針對(duì)交換機(jī)。路由器的核心延遲在路由查找，而這個(gè)查找不會(huì)受到數(shù)據(jù)包長(zhǎng)度的影響，因此決定路由器線(xiàn)速能力的核心就在數(shù)據(jù)包輸出的效率，注意，不是數(shù)據(jù)包輸入的效率，因?yàn)橹灰?duì)列足夠長(zhǎng)，緩存足夠大，輸入總是線(xiàn)速的。但是輸入操作就涉及到了如何調(diào)度的問(wèn)題。這也就說(shuō)明了為何很多路由器都支持輸出流量控制而不是輸入流量控制的原因，因?yàn)檩斎肓骺丶词雇昝劳瓿?，它也?huì)受到路由器輸出端口自身輸出效率的影響，流控結(jié)果將不再準(zhǔn)確。

在寫(xiě)這個(gè)方案的前晚，有一個(gè)故事。我最近聯(lián)系到了初中時(shí)一起玩搖滾玩音響的超級(jí)鐵的朋友，他現(xiàn)在搞舞臺(tái)設(shè)計(jì)，燈光音響之類(lèi)的。我問(wèn)他在大型舞臺(tái)上，音箱擺放的位置不同，距離后級(jí)，前置，音源也不同，怎么做到不同聲道或者相同聲道的聲音同步的，要知道，好的耳朵可以聽(tīng)出來(lái)毫秒級(jí)的音差...他告訴我要統(tǒng)一到達(dá)時(shí)間，即統(tǒng)一音頻流到達(dá)各個(gè)箱子的時(shí)間，而這要做的就是調(diào)延遲，要求不同位置的箱子路徑上要有不同的延遲。這對(duì)我的設(shè)計(jì)方案的幫助是多么地大啊。

然后，在第二天，我就開(kāi)始整理這個(gè)令人悲傷最終心碎的Linux轉(zhuǎn)發(fā)優(yōu)化方案。

聲明：本文只是一篇普通文章，記錄這個(gè)方案的點(diǎn)點(diǎn)滴滴，并不是一個(gè)完整的方案，請(qǐng)勿在格式上較真，內(nèi)容上也只是寫(xiě)了些我認(rèn)為重要且有意思的。完整的方案是不便于以博文的形式發(fā)出來(lái)的。見(jiàn)諒。

問(wèn)題綜述

Linux內(nèi)核協(xié)議棧作為一種軟路由運(yùn)行時(shí)，和其它通用操作系統(tǒng)自帶的協(xié)議棧相比，其效率并非如下文所說(shuō)的那樣非常低。然而基于工業(yè)路由器的評(píng)判標(biāo)準(zhǔn)，確實(shí)是低了。

市面上各種基于Linux內(nèi)核協(xié)議棧的路由器產(chǎn)品，甚至網(wǎng)上也有大量的此類(lèi)文章，比如什么將Linux變成路由器之類(lèi)的，無(wú)非就是打開(kāi)ip_forward，加幾條iptables規(guī)則，搞個(gè)配置起來(lái)比較方便的WEB界面...我想說(shuō)這些太低級(jí)了，甚至超級(jí)低級(jí)。我很想談一下關(guān)于專(zhuān)業(yè)路由器的我的觀點(diǎn)，但是今天是小小的生日，玩了一天，就不寫(xiě)了。只是把我的方案整理出來(lái)吧。

Linux的轉(zhuǎn)發(fā)效率到底低在哪兒？如何優(yōu)化？這是本文要解釋的問(wèn)題。依然如故，本文可以隨意轉(zhuǎn)載并基于這個(gè)思路實(shí)現(xiàn)編碼，但是一旦用于商業(yè)目的，不保證沒(méi)有個(gè)人或組織追責(zé)，因此文中我盡量采用盡可能模糊的方式闡述細(xì)節(jié)。

瓶頸分析概述

1.DMA和內(nèi)存操作

我們考慮一下一個(gè)數(shù)據(jù)包轉(zhuǎn)發(fā)流程中需要的內(nèi)存操作，暫時(shí)不考慮DMA。

*)數(shù)據(jù)包從網(wǎng)卡拷貝到內(nèi)存

*)CPU訪(fǎng)問(wèn)內(nèi)存讀取數(shù)據(jù)包元數(shù)據(jù)

*)三層報(bào)頭修改，如TTL

*)轉(zhuǎn)發(fā)到二層后封裝MAC頭

*)數(shù)據(jù)包從內(nèi)存拷貝到輸出網(wǎng)卡

這幾個(gè)典型的內(nèi)存操作為什么慢？為什么我們總是對(duì)內(nèi)存操作有這么大的意見(jiàn)？因?yàn)樵L(fǎng)問(wèn)內(nèi)存需要經(jīng)過(guò)總線(xiàn)，首先總線(xiàn)競(jìng)爭(zhēng)(特別在SMP和DMA下)就是一個(gè)打群架的過(guò)程，另外因?yàn)閮?nèi)存自身的速度和CPU相比差了幾個(gè)數(shù)量級(jí)，這么玩下去，肯定會(huì)慢??！所以一般都是盡可能地使用CPU的cache，而這需要一定的針對(duì)局部性的數(shù)據(jù)布局，對(duì)于數(shù)據(jù)包接收以及其它IO操作而言，由于數(shù)據(jù)來(lái)自外部，和進(jìn)程執(zhí)行時(shí)的局部性利用沒(méi)法比。所以必須采用類(lèi)似Intel I/OAT的技術(shù)才能改善。

1.1.Linux作為服務(wù)器時(shí)

采用標(biāo)準(zhǔn)零拷貝map技術(shù)完全勝任。這是因?yàn)?，運(yùn)行于Linux的服務(wù)器和線(xiàn)速轉(zhuǎn)發(fā)相比就是個(gè)蝸牛，服務(wù)器在處理客戶(hù)端請(qǐng)求時(shí)消耗的時(shí)間是一個(gè)硬性時(shí)間，無(wú)法優(yōu)化，這是代償原理。Linux服務(wù)唯一需要的就是能快速取到客戶(hù)端的數(shù)據(jù)包，而這可以通過(guò)DMA快速做到。本文不再具體討論作為服務(wù)器運(yùn)行的零拷貝問(wèn)題，自己百度吧。

1.2.Linux作為轉(zhuǎn)發(fā)設(shè)備時(shí)

需要采用DMA映射交換的技術(shù)才能實(shí)現(xiàn)零拷貝。這是Linux轉(zhuǎn)發(fā)性能低下的根本。由于輸入端口的輸入隊(duì)列和輸出端口的輸出隊(duì)列互不相識(shí)，導(dǎo)致了不能更好的利用系統(tǒng)資源以及多端口數(shù)據(jù)路由到單端口輸出隊(duì)列時(shí)的隊(duì)列鎖開(kāi)銷(xiāo)過(guò)大，總線(xiàn)爭(zhēng)搶太嚴(yán)重。DMA影射交換需要超級(jí)棒的數(shù)據(jù)包隊(duì)列管理設(shè)施，它用來(lái)調(diào)度數(shù)據(jù)包從輸入端口隊(duì)列到輸出端口隊(duì)列，而Linux幾乎沒(méi)有這樣的設(shè)施。

雖然近年在路由器領(lǐng)域有人提出了輸入隊(duì)列管理，但是這項(xiàng)技術(shù)對(duì)于Linux而言就是另一個(gè)世界，而我，把它引入了Linux世界。

2.網(wǎng)卡對(duì)數(shù)據(jù)包隊(duì)列Buff管理

在Linux內(nèi)核中，幾乎對(duì)于所有數(shù)據(jù)結(jié)構(gòu)，都是需要時(shí)alloc，完畢后free，即使是kmem_cache，效果也一般，特別是對(duì)于高速線(xiàn)速設(shè)備而言(skb內(nèi)存拷貝，若不采用DMA，則會(huì)頻繁拷貝，即便采用DMA，在很多情況下也不是零拷貝)。

即使是高端網(wǎng)卡在skb的buffer管理方面，也沒(méi)有使用完全意義上的預(yù)分配內(nèi)存池，因此會(huì)由于頻繁的內(nèi)存分配，釋放造成內(nèi)存顛簸，眾所周知，內(nèi)存操作是問(wèn)題的根本，因?yàn)樗婕暗紺PU Cache，總線(xiàn)爭(zhēng)搶?zhuān)渔i等，實(shí)際上，內(nèi)存管理才是根本中的根本，這里面道道太多，它直接影響CPU cache，后者又會(huì)影響總線(xiàn)...從哪里分配內(nèi)存，分配多少，何時(shí)釋放，何時(shí)可以重用，這就牽扯到了內(nèi)存區(qū)域著色等技術(shù)。通過(guò)分析Intel千兆網(wǎng)卡驅(qū)動(dòng)，在我看來(lái)，Linux并沒(méi)有做好這一點(diǎn)。

3.路由查找以及其它查找操作

Linux不區(qū)分對(duì)待路由表和轉(zhuǎn)發(fā)表，每次都要最長(zhǎng)前綴查找，雖然海量路由表時(shí)trie算法比hash算法好，但是在路由分布畸形的情況下依然會(huì)使trie結(jié)構(gòu)退化，或者頻繁回溯。路由cache效率不高（查詢(xún)代價(jià)太大，不固定大小，僅有弱智的老化算法，導(dǎo)致海量地址訪(fǎng)問(wèn)時(shí)，路由cache沖突鏈過(guò)長(zhǎng)），最終在內(nèi)核協(xié)議棧中下課。

如果沒(méi)有一個(gè)好的轉(zhuǎn)發(fā)表，那么Linux協(xié)議棧在海量路由存在時(shí)對(duì)于線(xiàn)速能力就是一個(gè)瓶頸，這是一個(gè)可擴(kuò)展性問(wèn)題。

另外，很多的查詢(xún)結(jié)果都是可以被在一個(gè)地方緩存的，但是Linux協(xié)議棧沒(méi)有這種緩存。比如，路由查詢(xún)結(jié)果就是下一跳，而下一跳和輸出網(wǎng)卡關(guān)聯(lián)，而輸出網(wǎng)卡又和下一跳的MAC地址以及將要封裝的源MAC地址關(guān)聯(lián)，這些本應(yīng)該被緩存在一個(gè)表項(xiàng)，即轉(zhuǎn)發(fā)表項(xiàng)內(nèi)，然而Linux協(xié)議棧沒(méi)有這么做。

4.不合理的鎖

為何要加鎖，因?yàn)镾MP。然而Linux內(nèi)核幾乎是對(duì)稱(chēng)的加鎖，也就是說(shuō)，比如每次查路由表時(shí)都要加鎖，為何？因?yàn)榕略诓樵?xún)的期間路由表改變了...然而你仔細(xì)想想，在高速轉(zhuǎn)發(fā)情景下，查找操作和修改操作在單位時(shí)間的比率是多少呢？不要以為你用讀寫(xiě)鎖就好了，讀寫(xiě)鎖不也有關(guān)搶占的操作嗎(雖然我們已經(jīng)建議關(guān)閉了搶占)？起碼也浪費(fèi)了幾個(gè)指令周期。這些時(shí)間幾率不對(duì)稱(chēng)操作的加鎖是不必要的。

你只需要保證內(nèi)核本身不會(huì)崩掉即可，至于說(shuō)IP轉(zhuǎn)發(fā)的錯(cuò)誤，不管也罷，按照IP協(xié)議，它本身就是一個(gè)盡力而為的協(xié)議。

5.中斷與軟中斷調(diào)度

Linux的中斷分為上半部和下半部，動(dòng)態(tài)調(diào)度下半部，它可以在中斷上下文中運(yùn)行，也可以在獨(dú)立的內(nèi)核線(xiàn)程上下文中運(yùn)行，因此對(duì)于實(shí)時(shí)需求的環(huán)境，在軟中斷中處理的協(xié)議棧處理的運(yùn)行時(shí)機(jī)是不可預(yù)知的。Linux原生內(nèi)核并沒(méi)有實(shí)現(xiàn)Solaris，Windows那樣的中斷優(yōu)先級(jí)化，在某些情況下，Linux靠著自己動(dòng)態(tài)的且及其優(yōu)秀的調(diào)度方案可以達(dá)到極高的性能，然而對(duì)于固定的任務(wù)，Linux的調(diào)度機(jī)制卻明顯不足。

而我需要做的，就是讓不固定的東西固定化。

6.通用操作系統(tǒng)內(nèi)核協(xié)議棧的通病

作為一個(gè)通用操作系統(tǒng)內(nèi)核，Linux內(nèi)核并非僅僅處理網(wǎng)絡(luò)數(shù)據(jù)，它還有很多別的子系統(tǒng)，比如各種文件系統(tǒng)，各種IPC等，它能做的只是可用，簡(jiǎn)單，易擴(kuò)展。

Linux原生協(xié)議棧完全未經(jīng)網(wǎng)絡(luò)優(yōu)化，且基本裝機(jī)在硬件同樣也未經(jīng)優(yōu)化的通用架構(gòu)上，網(wǎng)卡接口在PCI-E總線(xiàn)上，如果DMA管理不善，總線(xiàn)的占用和爭(zhēng)搶帶來(lái)的性能開(kāi)銷(xiāo)將會(huì)抵消掉DMA本意帶來(lái)的好處（事實(shí)上對(duì)于轉(zhuǎn)發(fā)而言并沒(méi)有帶來(lái)什么好處，它僅僅對(duì)于作為服務(wù)器運(yùn)行的Linux有好處，因?yàn)樗簧婕暗揭粔K網(wǎng)卡）

[ 注意，我認(rèn)為內(nèi)核處理路徑并非瓶頸，這是分層協(xié)議棧決定的，瓶頸在各層中的某些操作，比如內(nèi)存操作(固有開(kāi)銷(xiāo))以及查表操作(算法不好導(dǎo)致的開(kāi)銷(xiāo))]

綜述：Linux轉(zhuǎn)發(fā)效率受到以下幾大因素影響

IO/輸入輸出的隊(duì)列管理/內(nèi)存修改拷貝 （重新設(shè)計(jì)類(lèi)似crossbar的隊(duì)列管理實(shí)現(xiàn)DMA ring交換）

各種表查詢(xún)操作，特別是最長(zhǎng)前綴匹配，諸多本身唯一確定的查詢(xún)操作之間的關(guān)聯(lián)沒(méi)有建立

SMP下處理器同步（鎖開(kāi)銷(xiāo)）（使用大讀鎖以及RCU鎖）以及cache利用率

中斷以及軟中斷調(diào)度

Linux轉(zhuǎn)發(fā)性能提升方案

概述

此方案的思路來(lái)自基于crossbar的新一代硬件路由器。設(shè)計(jì)要點(diǎn)：

1.重新設(shè)計(jì)的DMA包管理隊(duì)列（ 思路來(lái)自L(fǎng)inux O(1)調(diào)度器，crossbar陣列以及VOQ[虛擬輸出隊(duì)列]）

2.重新設(shè)計(jì)的基于定位而非最長(zhǎng)前綴查找的轉(zhuǎn)發(fā)表

3.長(zhǎng)線(xiàn)程處理（中斷線(xiàn)程化，處理流水線(xiàn)化，增加CPU親和）

4.數(shù)據(jù)結(jié)構(gòu)無(wú)鎖化（基于線(xiàn)程局部數(shù)據(jù)結(jié)構(gòu)）

5.實(shí)現(xiàn)方式

5.1.驅(qū)動(dòng)以及內(nèi)核協(xié)議棧修改

5.2.完全的用戶(hù)態(tài)協(xié)議棧

5.3.評(píng)估：用戶(hù)態(tài)協(xié)議棧靈活，但是在某些平臺(tái)要處理空間切換導(dǎo)致的cache/tlb/mmu表的flush問(wèn)題

內(nèi)核協(xié)議棧方案

優(yōu)化框架

0.例行優(yōu)化

1).網(wǎng)卡多隊(duì)列綁定特定CPU核心（利用RSS特性分別處理TX和RX）

[ 可以參見(jiàn)《Effective Gigabit Ethernet Adapters-Intel千兆網(wǎng)卡8257X性能調(diào)優(yōu)》]

2).按照包大小統(tǒng)計(jì)動(dòng)態(tài)開(kāi)關(guān)積壓延遲中斷ThrottleRate以及中斷Delay(對(duì)于Intel千兆卡而言)

3).禁用內(nèi)核搶占，減少時(shí)鐘HZ，由中斷粒度驅(qū)動(dòng)（見(jiàn)上面）

4).如果不準(zhǔn)備優(yōu)化Netfilter，編譯內(nèi)核時(shí)禁用Netfilter，節(jié)省指令

5).編譯選項(xiàng)去掉DEBUG和TRACE，節(jié)省指令周期

6).開(kāi)啟網(wǎng)卡的硬件卸載開(kāi)關(guān)（如果有的話(huà)）

7).最小化用戶(hù)態(tài)進(jìn)程的數(shù)量，降低其優(yōu)先級(jí)

8).原生網(wǎng)絡(luò)協(xié)議棧優(yōu)化

由于不再作為通用OS，可以讓除了RX softirq的task適當(dāng)饑餓

*CPU分組(考慮Linux的cgroup機(jī)制)，劃一組CPU為數(shù)據(jù)面CPU，每一個(gè)CPU綁定一個(gè)RX softirq或者

*增加rx softirq一次執(zhí)行的netdev_budget以及time limit，或者

*只要有包即處理，每一個(gè)?？刂泼?管理面的task可以綁在別的CPU上。

宗旨：

原生協(xié)議棧的最優(yōu)化方案

1.優(yōu)化I/O，DMA，減少內(nèi)存管理操作

1).減少PCI-E的bus爭(zhēng)用,采用crossbar的全交叉超立方開(kāi)關(guān)的方式

[ Tips：16 lines 8 bits PCI-E總線(xiàn)拓?fù)?非crossbar！)的網(wǎng)絡(luò)線(xiàn)速不到滿(mǎn)載60% pps]

2).減少爭(zhēng)搶式DMA，減少鎖總線(xiàn)[Tips：優(yōu)化指令LOCK，最好采用RISC，方可調(diào)高內(nèi)核HZ]

[ Tips：交換DMA映射，而不是在輸入/輸出buffer ring之間拷貝數(shù)據(jù)！現(xiàn)在，只有傻逼才會(huì)在DMA情況拷貝內(nèi)存，正確的做法是DMA重映射，交換指針！]

3).采用skb內(nèi)存池，避免頻繁內(nèi)存分配/釋放造成的內(nèi)存管理框架內(nèi)的抖動(dòng)

[ Tips：每線(xiàn)程負(fù)責(zé)一塊網(wǎng)卡(甚至輸入和輸出由不同的線(xiàn)程負(fù)責(zé)會(huì)更好)，保持一個(gè)預(yù)分配可循環(huán)利用的ring buffer，映射DMA]

宗旨：

減少cache刷新和tlb刷新，減少內(nèi)核管理設(shè)施的工作(比如頻繁的內(nèi)存管理)

2.優(yōu)化中斷分發(fā)

1).增加長(zhǎng)路徑支持，減少進(jìn)程切換導(dǎo)致的TLB以及Cache刷新

2).利用多隊(duì)列網(wǎng)卡支持中斷CPU親和力利用或者模擬軟多隊(duì)列提高并行性

3).犧牲用戶(hù)態(tài)進(jìn)程的調(diào)度機(jī)會(huì)，全部精力集中于內(nèi)核協(xié)議棧的處理，多CPU多路并行的

[ Tips：如果有超多的CPU，建議劃分cgroup ]

4).中斷處理線(xiàn)程化，內(nèi)核線(xiàn)程化，多核心并行執(zhí)行長(zhǎng)路經(jīng)，避免切換抖動(dòng)

5).線(xiàn)程內(nèi)部，按照IXA NP微模塊思想采用模塊化(方案未實(shí)現(xiàn)，待商榷)

宗旨：

減少cache刷新和tlb刷新

減少協(xié)議棧處理被中斷過(guò)于頻繁打斷[ 要么使用IntRate，要么引入中斷優(yōu)先級(jí)]

3.優(yōu)化路由查找算法

1).分離路由表和轉(zhuǎn)發(fā)表，路由表和轉(zhuǎn)發(fā)表同步采用RCU機(jī)制

2).盡量采用線(xiàn)程局部數(shù)據(jù)

每個(gè)線(xiàn)程一張轉(zhuǎn)發(fā)表（由路由表生成，OpenVPN多線(xiàn)程采用，但失?。?，采用定位而非最長(zhǎng)前綴查找（DxR或者我設(shè)計(jì)的那個(gè)）。若不采用為每個(gè)線(xiàn)程復(fù)制一份轉(zhuǎn)發(fā)表，則需要重新設(shè)計(jì)RW鎖或者使用RCU機(jī)制。

3).采用hash/trie方式以及DxR或者我設(shè)計(jì)的DxRPro定位結(jié)構(gòu)

宗旨：

采用定位而非查找結(jié)構(gòu)

采用局部表，避免鎖操作

4.優(yōu)化lock

1).查詢(xún)定位局部表，無(wú)鎖（甚至RW鎖都沒(méi)有）不禁止中斷

2).臨界區(qū)和內(nèi)核線(xiàn)程關(guān)聯(lián)，不禁中斷，不禁搶占（其實(shí)內(nèi)核編譯時(shí)搶占已經(jīng)關(guān)閉了）

3).優(yōu)先級(jí)鎖隊(duì)列替換爭(zhēng)搶模型，維持cache熱度

4).采用Windows的自旋鎖機(jī)制

[ Tips：Linux的ticket spin lock由于采用探測(cè)全局lock的方式，會(huì)造成總線(xiàn)開(kāi)銷(xiāo)和CPU同步開(kāi)銷(xiāo)，Windows的spin lock采用了探測(cè)CPU局部變量的方式實(shí)現(xiàn)了真正的隊(duì)列l(wèi)ock，我設(shè)計(jì)的輸入輸出隊(duì)列管理結(jié)構(gòu)(下面詳述)思路部分來(lái)源于Windows的自旋鎖設(shè)計(jì)]

宗旨：鎖的粒度與且僅與臨界區(qū)資源關(guān)聯(lián)，粒度最小化

優(yōu)化細(xì)節(jié)概覽

1.DMA與輸入輸出隊(duì)列優(yōu)化

1.1.問(wèn)題出在哪兒

如果你對(duì)Linux內(nèi)核協(xié)議棧足夠熟悉，那么就肯定知道，Linux內(nèi)核協(xié)議棧正是由于軟件工程里面的天天普及的“一件好事”造成了轉(zhuǎn)發(fā)性能低效。這就是“解除緊密耦合”。

Linux協(xié)議棧轉(zhuǎn)發(fā)和Linux服務(wù)器之間的根本區(qū)別在于，后者的應(yīng)用服務(wù)并不在乎數(shù)據(jù)包輸入網(wǎng)卡是哪個(gè)，它也不必關(guān)心輸出網(wǎng)卡是哪一個(gè)，然而對(duì)于Linux協(xié)議棧轉(zhuǎn)發(fā)而言，輸入網(wǎng)卡和輸出網(wǎng)卡之間確實(shí)是有必要相互感知的。Linux轉(zhuǎn)發(fā)效率低的根本原因不是路由表不夠高效，而是它的隊(duì)列管理以及I/O管理機(jī)制的低效，造成這種低效的原因不是技術(shù)實(shí)現(xiàn)上難以做到，而是Linux內(nèi)核追求的是一種靈活可擴(kuò)展的性能，這就必須解除出入網(wǎng)卡，驅(qū)動(dòng)和協(xié)議棧之間關(guān)于數(shù)據(jù)包管理的緊密耦合。

我們以Intel千兆網(wǎng)卡驅(qū)動(dòng)e1000e來(lái)說(shuō)明上述的問(wèn)題。順便說(shuō)一句，Intel千兆驅(qū)動(dòng)亦如此，其它的就更別說(shuō)了，其根源在于通用的網(wǎng)卡驅(qū)動(dòng)和協(xié)議棧設(shè)計(jì)并不是針對(duì)轉(zhuǎn)發(fā)優(yōu)化的。

初始化：

創(chuàng)建RX ring：RXbuffinfo[MAX]

創(chuàng)建TX ring：TXbuffinfo[MAX]

RX過(guò)程：

i = 當(dāng)前RX ring游歷到的位置;

while(RXbuffinfo中有可用skb) {

skb = RXbufferinfo[i].skb;

RXbuffinfo[i].skb = NULL;

i++;

DMA_unmap(RXbufferinfo[i].DMA);

[Tips：至此，skb已經(jīng)和驅(qū)動(dòng)脫離，完全交給了Linux協(xié)議棧]

[Tips：至此，skb內(nèi)存已經(jīng)不再由RX ring維護(hù)，Linux協(xié)議棧拽走了skb這塊內(nèi)存]

OS_receive_skb(skb);

[Tips：由Linux協(xié)議棧負(fù)責(zé)釋放skb，調(diào)用kfree_skb之類(lèi)的接口]

if (RX ring中被Linux協(xié)議棧摘走的skb過(guò)多) {

alloc_new_skb_from_kmem_cache_to_RXring_RXbufferinfo_0_to_MAX_if_possible;

[Tips：從Linux核心內(nèi)存中再次分配skb]

}

}

TX過(guò)程：

skb = 來(lái)自L(fǎng)inux協(xié)議棧dev_hard_xmit接口的數(shù)據(jù)包;

i = TX ring中可用的位置

TXbufferinfo[i].skb = skb;

DMA_map(TXbufferinfo[i].DMA);

while(TXbufferinfo中有可用的skb) {

DMA_transmit_skb(TXbufferinfo[i]);

}

[異步等待傳輸完成中斷或者在NAPI poll中主動(dòng)調(diào)用]

i = 傳輸完成的TXbufferinfo索引

while(TXbufferinfo中有已經(jīng)傳輸完成的skb) {

skb = TXbufferinfo[i];

DMA_unmap(TXbufferinfo[i].DMA);

kfree(skb);

i++;

}

以上的流程可以看出，在持續(xù)轉(zhuǎn)發(fā)數(shù)據(jù)包的時(shí)候，會(huì)涉及大量的針對(duì)skb的alloc和free操作。如果你覺(jué)得上面的代碼不是那么直觀，那么下面給出一個(gè)圖示：

頻繁的會(huì)發(fā)生從Linux核心內(nèi)存中alloc skb和free skb的操作，這不僅僅是不必要的，而且還會(huì)損害CPU cache的利用。不要寄希望于keme_cache，我們可以看到，所有的網(wǎng)卡和socket幾乎是共享一塊核心內(nèi)存的，雖然可以通過(guò)dev和kmem cache來(lái)優(yōu)化，但很遺憾，這個(gè)優(yōu)化沒(méi)有質(zhì)的飛躍。

1.2.構(gòu)建新的DMA ring buffer管理設(shè)施-VOQ，建立輸入/輸出網(wǎng)卡之間隊(duì)列的關(guān)聯(lián)。

類(lèi)比Linux O(1)調(diào)度器算法，每一個(gè)cpu全局維護(hù)一個(gè)唯一的隊(duì)列，散到各個(gè)網(wǎng)卡，靠交換隊(duì)列的DMA映射指針而不是拷貝數(shù)據(jù)的方式優(yōu)化性能，達(dá)到零拷貝，這只是其一。關(guān)于交換DMA映射指針而不是拷貝數(shù)據(jù)這一點(diǎn)不多談，因?yàn)閹缀跛械闹С諨MA的網(wǎng)卡驅(qū)動(dòng)都是這么做的，如果它們不是這么做的，那么肯定有人會(huì)將代碼改成這么做的。

如果類(lèi)比高端路由器的crossbar交換陣列結(jié)構(gòu)以及真實(shí)的VOQ實(shí)現(xiàn)，你會(huì)發(fā)現(xiàn)，在邏輯上，每一對(duì)可能的輸入/輸出網(wǎng)卡之間維護(hù)一條數(shù)據(jù)轉(zhuǎn)發(fā)通路是避免隊(duì)頭阻塞以及競(jìng)爭(zhēng)的好方法。這樣排隊(duì)操作只會(huì)影響單獨(dú)的網(wǎng)卡，不需要再全局加鎖。在軟件實(shí)現(xiàn)上，我們同樣可以做到這個(gè)。你要明白，Linux的網(wǎng)卡驅(qū)動(dòng)維護(hù)的隊(duì)列信息被內(nèi)核協(xié)議棧給割裂，從此，輸入/輸出網(wǎng)卡之間彼此失聯(lián)，導(dǎo)致最優(yōu)的二分圖算法無(wú)法實(shí)施。

事實(shí)上，你可能覺(jué)得把網(wǎng)卡作為一個(gè)集合，把需要輸出的數(shù)據(jù)包最為另一個(gè)集合，轉(zhuǎn)發(fā)操作需要做的就是建立數(shù)據(jù)包和網(wǎng)卡之間的一條路徑，這是一個(gè)典型的二分圖匹配問(wèn)題，然而如果把建立路徑的操作與二分圖問(wèn)題分離，這就是不再是網(wǎng)卡和數(shù)據(jù)包之間的二分圖匹配問(wèn)題了。因?yàn)榉蛛x出來(lái)的路由模塊導(dǎo)致了針對(duì)每一個(gè)要轉(zhuǎn)發(fā)的數(shù)據(jù)包，其輸出網(wǎng)卡是唯一確定的。這個(gè)問(wèn)題變成了處理輸出網(wǎng)卡輸出操作的CPU集合和輸出網(wǎng)卡之間的二分圖匹配問(wèn)題。

這里有一個(gè)優(yōu)化點(diǎn)，那就是如果你有多核CPU，那么就可以為每一塊網(wǎng)卡的輸出操作綁定一個(gè)唯一的CPU，二分圖匹配問(wèn)題迎刃而解，剩下的就是硬件總線(xiàn)的爭(zhēng)用問(wèn)題(對(duì)于高性能crossbar路由器而言，這也是一個(gè)二分圖匹配問(wèn)題，但對(duì)于總線(xiàn)結(jié)構(gòu)的通用系統(tǒng)而言有點(diǎn)區(qū)別，后面我會(huì)談到)了，作為我們而言，這一點(diǎn)除了使用性?xún)r(jià)比更高的總線(xiàn)，比如我們使用PCI-E 16Lines 8 bits，沒(méi)有別的辦法。作為一個(gè)完全的方案，我不能寄希望于底層存在一個(gè)多核CPU系統(tǒng)，如果只有一個(gè)CPU，那么我們能寄希望于Linux進(jìn)程調(diào)度系統(tǒng)嗎？還是那個(gè)觀點(diǎn)，作為一個(gè)通用操作系統(tǒng)內(nèi)核，Linux不會(huì)針對(duì)網(wǎng)絡(luò)轉(zhuǎn)發(fā)做優(yōu)化，于是乎，進(jìn)程調(diào)度系統(tǒng)是此方案的另一個(gè)優(yōu)化點(diǎn)，這個(gè)我后面再談。

最后，給出我的數(shù)據(jù)包隊(duì)列管理VOQ的設(shè)計(jì)方案草圖。

在我的這個(gè)針對(duì)Linux協(xié)議棧的VOQ設(shè)計(jì)中，VOQ總要要配合良好的輸出調(diào)度算法，才能發(fā)揮出最佳的性能。

2.分離路由表和轉(zhuǎn)發(fā)表以及建立查找操作之間的關(guān)聯(lián)

Linux協(xié)議棧是不區(qū)分對(duì)待路由表和轉(zhuǎn)發(fā)表的，而這在高端路由器上顯然是必須的。誠(chéng)然，我沒(méi)有想將Linux協(xié)議棧打造成比肩專(zhuān)業(yè)路由器的協(xié)議棧，然而通過(guò)這個(gè)排名第二的核心優(yōu)化，它的轉(zhuǎn)發(fā)效率定會(huì)更上一層樓。

在大約三個(gè)月前，我參照DxR結(jié)構(gòu)以及借鑒MMU思想設(shè)計(jì)了一個(gè)用于轉(zhuǎn)發(fā)的索引結(jié)構(gòu)，可以實(shí)現(xiàn)3步定位，無(wú)需做最長(zhǎng)前綴匹配過(guò)程，具體可以參見(jiàn)我的這篇文章 《以DxR算法思想為基準(zhǔn)設(shè)計(jì)出的路由項(xiàng)定位結(jié)構(gòu)圖解》，我在此就不再深度引用了。需要注意的是，這個(gè)結(jié)構(gòu)可以根據(jù)現(xiàn)行的Linux協(xié)議棧路由FIB生成，而且在路由項(xiàng)不規(guī)則的情況下可以在最差情況下動(dòng)態(tài)回退到標(biāo)準(zhǔn)DxR，比如路由項(xiàng)不可匯聚，路由項(xiàng)在IPv4地址空間劃分區(qū)間過(guò)多且分布不均。我將我設(shè)計(jì)的這個(gè)結(jié)構(gòu)稱(chēng)作DxR Pro++。

至于說(shuō)查找操作之間的關(guān)聯(lián)，這也是一個(gè)深度優(yōu)化，底層構(gòu)建高速查詢(xún)流表實(shí)現(xiàn)協(xié)議棧短路（流表可參照conntrack設(shè)計(jì)），這個(gè)優(yōu)化思想直接參照了Netfilter的conntrack以及SDN流表的設(shè)計(jì)。雖然IP網(wǎng)絡(luò)是一個(gè)無(wú)狀態(tài)網(wǎng)絡(luò)，中間路由器的轉(zhuǎn)發(fā)策略也應(yīng)該是一個(gè)無(wú)狀態(tài)的轉(zhuǎn)發(fā)。然而這是形而上意義上的理念。如果談到深度優(yōu)化，就不得不犧牲一點(diǎn)純潔性。

設(shè)計(jì)一個(gè)流表，流的定義可以不必嚴(yán)格按照五元組，而是可以根據(jù)協(xié)議頭的任意字段，每一個(gè)表項(xiàng)中保存的信息包括但不限于以下的元素：

*流表緩存路由項(xiàng)

*流表緩存neighbour

*流表緩存NAT

*流表緩存ACL規(guī)則

*流表緩存二層頭信息

這樣可以在協(xié)議棧的底層保存一張可以高速查詢(xún)的流表，協(xié)議棧收到skb后匹配這張表的某項(xiàng)，一旦成功，可以直接取出相關(guān)的數(shù)據(jù)(比如路由項(xiàng))直接轉(zhuǎn)發(fā)，理論上只有一個(gè)流的第一個(gè)數(shù)據(jù)包會(huì)走標(biāo)準(zhǔn)協(xié)議棧的慢速路徑(事實(shí)上，經(jīng)過(guò)DxR Pro++的優(yōu)化，一經(jīng)不慢了...)。在直接快速轉(zhuǎn)發(fā)中，需要執(zhí)行一個(gè)HOOK，執(zhí)行標(biāo)準(zhǔn)的例行操作，比如校驗(yàn)和，TTL遞減等。

關(guān)于以上的元素，特別要指出的是和neighbour與二層信息相關(guān)的。數(shù)據(jù)轉(zhuǎn)發(fā)操作一向被認(rèn)為瓶頸在發(fā)不在收，在數(shù)據(jù)發(fā)送過(guò)程，會(huì)涉及到以下耗時(shí)的操作：>添加輸出網(wǎng)卡的MAC地址作為源-內(nèi)存拷貝>添加next hop的MAC地址作為目標(biāo)-內(nèi)存拷貝又一次，我們遇到了內(nèi)存操作，惱人的內(nèi)存操作！如果我們把這些MAC地址保存在流表中，可以避免嗎？貌似只是可以快速定位，而無(wú)法避免內(nèi)存拷貝...再一次的，我們需要硬件的特性來(lái)幫忙，這就是分散聚集I/O(Scatter-gather IO)，原則上，Scatter-gather IO可以將不連續(xù)的內(nèi)存當(dāng)成連續(xù)的內(nèi)存使用，進(jìn)而直接映射DMA，因此我們只需要告訴控制器，一個(gè)將要發(fā)送的幀的MAC頭的位置在哪里，DMA就可以直接傳輸，沒(méi)有必要將MAC地址拷貝到幀頭的內(nèi)存區(qū)域。如下圖所示：

特別要注意，上述的流表緩存項(xiàng)中的數(shù)據(jù)存在大量冗余，因?yàn)閚ext hop的MAC地址，輸出網(wǎng)卡的MAC地址，這些是可以由路由項(xiàng)唯一確定的。之所以保存冗余數(shù)據(jù)，其原則還是為了優(yōu)化，而標(biāo)準(zhǔn)的通用Linux內(nèi)核協(xié)議棧，它卻是要避免冗余的...既然保存了冗余數(shù)據(jù)，那么慢速路徑的數(shù)據(jù)項(xiàng)和快速路經(jīng)的數(shù)據(jù)項(xiàng)之間的同步就是一個(gè)必須要解決的問(wèn)題。我基于讀寫(xiě)的不對(duì)稱(chēng)性，著手采用event的方式通知更新，比如慢速路徑中的數(shù)據(jù)項(xiàng)(路由，MAC信息，NAT，ACL信息等)，一旦這些信息更改，內(nèi)核會(huì)專(zhuān)門(mén)觸發(fā)一個(gè)查詢(xún)操作，將快速流表中與之相關(guān)的表項(xiàng)disable掉即可。值得注意的是，這個(gè)查詢(xún)操作沒(méi)必要太快，因?yàn)橄啾容^快速轉(zhuǎn)發(fā)而言，數(shù)據(jù)同步的頻率要慢天文數(shù)字個(gè)數(shù)量級(jí)...類(lèi)似Cisco的設(shè)備，可以創(chuàng)建幾個(gè)內(nèi)核線(xiàn)程定期刷新慢速路徑表項(xiàng)，用來(lái)發(fā)現(xiàn)數(shù)據(jù)項(xiàng)的更改，從而觸發(fā)event。

[Tips：可以高速查找的流表結(jié)構(gòu)可用多級(jí)hash（采用TCAM的類(lèi)似方案），也可以借鑒我的DxR Pro++結(jié)構(gòu)以及nf-HiPac算法的多維區(qū)間匹配結(jié)構(gòu)，我個(gè)人比較推崇nf-HiPac]

3.路由Cache優(yōu)化

雖說(shuō)Linux的路由cache早已下課，但是它下課的原因并不是cache機(jī)制本身不好，而是Linux的路由cache設(shè)計(jì)得不好。因此以下幾點(diǎn)可以作為優(yōu)化點(diǎn)來(lái)嘗試。

*)限制路由軟cache的大小，保證查找速度[實(shí)施精心設(shè)計(jì)的老化算法和替換算法]

[ 利用互聯(lián)網(wǎng)訪(fǎng)問(wèn)的時(shí)間局部性以及空間局部性（需要利用計(jì)數(shù)統(tǒng)計(jì)）]

[ 自我PK：如果有了我的那個(gè)3步定位結(jié)構(gòu)，難道還用的到路由cache嗎]

*)預(yù)制常用IP地址到路由cache，實(shí)現(xiàn)一步定位

[ 所謂常用IP需要根據(jù)計(jì)數(shù)統(tǒng)計(jì)更新，也可以靜態(tài)設(shè)置]

4.Softirq在不支持RSS多隊(duì)列網(wǎng)卡時(shí)的NAPI調(diào)度優(yōu)化

*)將設(shè)備按照協(xié)議頭hash值均勻放在不同CPU，遠(yuǎn)程喚醒softirq，模擬RSS軟實(shí)現(xiàn)

目前的網(wǎng)絡(luò)接收軟中斷的處理機(jī)制是，哪個(gè)CPU被網(wǎng)卡中斷了，哪個(gè)CPU就處理網(wǎng)卡接收軟中斷，在網(wǎng)卡只能中斷固定CPU的情況下，這會(huì)影響并行性，比如只有兩塊網(wǎng)卡，卻有16核CPU。如何將盡可能多的CPU核心調(diào)動(dòng)起來(lái)呢？這需要修改網(wǎng)絡(luò)接收軟中斷處理邏輯。我希望多個(gè)CPU輪流處理數(shù)據(jù)包，而不是固定被中斷的數(shù)據(jù)包來(lái)處理。修改邏輯如下：

1.所有的rx softirq內(nèi)核線(xiàn)程組成一個(gè)數(shù)組

struct task_struct rx_irq_handler[NR_CPUS];

2.所有的poll list組成一個(gè)數(shù)組

struct list_head polll[NR_CPUS];

3.引入一把保護(hù)上述數(shù)據(jù)的自旋鎖

spinlock_t rx_handler_lock;

4.修改NAPI的調(diào)度邏輯

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親和的結(jié)合，如果連DMA都不支持，那還優(yōu)化個(gè)毛]

理論上一定要做基于傳輸層以及傳輸層以下的元組做hash，不能隨機(jī)分派，在計(jì)算hash的時(shí)候也不能引入任何每包可變的字段。由于某些高層協(xié)議比如TCP以及絕大多數(shù)的基于非TCP的應(yīng)用協(xié)議是高度按序的，中間節(jié)點(diǎn)的完全基于數(shù)據(jù)包處理的并行化會(huì)引起數(shù)據(jù)包在端節(jié)點(diǎn)的亂序到達(dá)，從而引發(fā)重組和重傳開(kāi)銷(xiāo)。自己為了提高線(xiàn)速能力貌似爽了一把，卻給端主機(jī)帶來(lái)了麻煩。然而我目前沒(méi)有考慮這個(gè)，我只是基于輪轉(zhuǎn)調(diào)度的方式來(lái)分發(fā)poll過(guò)程到不同的CPU來(lái)處理，這顯然會(huì)導(dǎo)致上述的亂序問(wèn)題。

若想完美解決上述問(wèn)題，需要增加一個(gè)調(diào)度層，將RX softirq再次分為上下兩半部RX softirq1和RX softirq2，上半部RX softirq1僅僅是不斷取出skb并分派到特定CPU核心，下半部才是協(xié)議棧處理，修改NAPI的poll邏輯，每當(dāng)poll出來(lái)一個(gè)skb，就計(jì)算這個(gè)skb的hash值，然后將其再次分派到特定的CPU的隊(duì)列中，最后喚醒有skb需要處理的CPU上的RX softirq2，這期間需要引入一個(gè)位圖來(lái)記錄有無(wú)情況。

但是有一個(gè)需要權(quán)衡的邏輯，是不是真的值得將RX softirq做再次分割，將其分為上下半部，這期間的調(diào)度開(kāi)銷(xiāo)和切換開(kāi)銷(xiāo)到底是多少，需要基準(zhǔn)測(cè)試來(lái)評(píng)估。

*)延長(zhǎng)net softirq的執(zhí)行時(shí)間，有包就一直dispatch loop。管理/控制平面進(jìn)程被劃分到獨(dú)立的cgroup/cpuset中。

5.Linux調(diào)度器相關(guān)的修改

這個(gè)優(yōu)化涉及到方案的完備性，畢竟我們不能保證CPU核心的數(shù)量一定大于網(wǎng)卡數(shù)量的2倍(輸入處理和輸出處理分離)，那么就必須考慮輸出事件的調(diào)度問(wèn)題。

依照數(shù)據(jù)包隊(duì)列管理的設(shè)計(jì)方案，考慮單CPU核心，如果有多塊網(wǎng)卡的輸出位圖中有bit被置位，那么到底調(diào)度哪一個(gè)網(wǎng)卡進(jìn)行輸出呢？這是一個(gè)明確的task調(diào)度問(wèn)題。你放心把這個(gè)工作交給Linux內(nèi)核的調(diào)度器去做嗎？我不會(huì)。

因?yàn)槲抑?，雖然有好幾個(gè)網(wǎng)卡可能都有數(shù)據(jù)包等待發(fā)送，但是它們的任務(wù)量并不同，這又是一個(gè)二分圖問(wèn)題。我需要三個(gè)指標(biāo)加權(quán)來(lái)權(quán)衡讓哪個(gè)網(wǎng)卡先發(fā)送，這三個(gè)指標(biāo)是，隊(duì)頭等待時(shí)間，隊(duì)列數(shù)據(jù)包長(zhǎng)度總和以及數(shù)據(jù)包數(shù)量。由此可以算出一個(gè)優(yōu)先級(jí)prio，總的來(lái)講就是虛擬輸出隊(duì)列中等待越久，數(shù)據(jù)包越多，長(zhǎng)度越長(zhǎng)的那個(gè)網(wǎng)卡最值得發(fā)送數(shù)據(jù)。計(jì)算隊(duì)列總長(zhǎng)勢(shì)必會(huì)引發(fā)非局部訪(fǎng)問(wèn)，比如訪(fǎng)問(wèn)其它網(wǎng)卡的虛擬輸出隊(duì)列，這就會(huì)引發(fā)鎖的問(wèn)題，因此考慮簡(jiǎn)單情形，僅僅使用一個(gè)指標(biāo)，即數(shù)據(jù)包長(zhǎng)度。在Linux當(dāng)前的CFS調(diào)度器情形下，需要將排隊(duì)虛擬輸出隊(duì)列的數(shù)據(jù)包長(zhǎng)度與task的虛擬時(shí)間，即vruntime關(guān)聯(lián)，具體來(lái)講就是，在輸入網(wǎng)卡對(duì)輸出網(wǎng)卡的輸出位圖置位的時(shí)候，有下列序列：

//只要有skb排隊(duì)，無(wú)條件setbit

setbit(outcart, incard);

//只要有skb排隊(duì)，則將與輸出網(wǎng)卡關(guān)聯(lián)的輸出線(xiàn)程的虛擬時(shí)間減去一個(gè)值，該值由數(shù)據(jù)包長(zhǎng)度與常量歸一化計(jì)算所得。

outcard_tx_task_dec_vruntime(outcard, skb->len);

對(duì)Linux CFS調(diào)度不熟悉的，可以自行g(shù)oogle。事實(shí)上，一旦某個(gè)輸出網(wǎng)卡的輸出task開(kāi)始運(yùn)行，它也是按照這種基于虛擬時(shí)間流逝的CFS方式來(lái)調(diào)度數(shù)據(jù)包的，即摘下一個(gè)最值得發(fā)送的數(shù)據(jù)包隊(duì)列描述符放入TX ring。

最后有一個(gè)思考，如果不采用CFS而采用RT調(diào)度類(lèi)是不是更好？單獨(dú)網(wǎng)卡輸出的實(shí)時(shí)性和多塊網(wǎng)卡輸出之間的公平性如何權(quán)衡？另外，采用RT調(diào)度類(lèi)就一定帶有實(shí)時(shí)性嗎？

6.內(nèi)置包分類(lèi)和包過(guò)濾的情況

這是一個(gè)關(guān)于Netfilter優(yōu)化的話(huà)題，Netfilter的性能一直被人詬病，其很大程度上都是由于iptables造成的，一定要區(qū)分對(duì)待Netfilter和iptables。當(dāng)然排除了這個(gè)誤會(huì)，并不表明Netfilter就完全無(wú)罪。Netfilter是一個(gè)框架，它本身在我們已經(jīng)關(guān)閉了搶占的情況下是沒(méi)有鎖開(kāi)銷(xiāo)的，關(guān)鍵的在它內(nèi)部的HOOK遍歷執(zhí)行中，作為一些callback，內(nèi)部的邏輯是不受控制的，像iptables，conntrack(本來(lái)數(shù)據(jù)結(jié)構(gòu)粒度就很粗-同一張hash存儲(chǔ)兩個(gè)方向的元組，又使用大量的大粒度鎖，內(nèi)存不緊張時(shí)我們可以多用幾把鎖，空間換自由，再說(shuō)，一把鎖能占多大空間啊)，都是吃性能的大戶(hù)，而nf-HiPac就好很多。因此這部分的優(yōu)化不好說(shuō)。

不過(guò)建議還是有的，為一段臨界區(qū)加鎖的時(shí)候千萬(wàn)不要盲目，如果一個(gè)數(shù)據(jù)結(jié)構(gòu)被讀的頻率比被寫(xiě)的頻率高很多，以至于后者可以被忽略的地步，那么勸各位不要鎖定它，即使RW鎖，RCU鎖都不要，而是采用復(fù)制的形式，拷貝出一個(gè)副本，然后讀副本，寫(xiě)原本，寫(xiě)入原本后采用原子事件的方式通知副本失效。比如上面提到的關(guān)于快速流表的同步問(wèn)題，一旦路由發(fā)生變化，就觸發(fā)一個(gè)原子事件，查詢(xún)快速流表中與之相關(guān)的項(xiàng)，失效掉它。查詢(xún)可以很慢，因?yàn)槁酚筛碌念l率很低。

本節(jié)不多談，建議如下：

*)預(yù)處理ACL或者NAT的ruleset（采用nf-hipac方案替換非預(yù)處理的逐條匹配）

[Hipac算法類(lèi)似于一種針對(duì)規(guī)則的預(yù)處理，將matches進(jìn)行了拆分，采用多維區(qū)間匹配算法]

*)包調(diào)度算法（CFS隊(duì)列，RB樹(shù)存儲(chǔ)包到達(dá)時(shí)間*h(x)，h為包長(zhǎng)的函數(shù)）

7.作為容器的skb

skb作為一個(gè)數(shù)據(jù)包的容器存在，它要和真正的數(shù)據(jù)包區(qū)分開(kāi)來(lái)，事實(shí)上，它僅僅作為一個(gè)數(shù)據(jù)包的載體，像一輛卡車(chē)運(yùn)載數(shù)據(jù)包。它是不應(yīng)該被釋放的，永遠(yuǎn)不該被釋放。每一塊網(wǎng)卡都應(yīng)該擁有自己的卡車(chē)車(chē)隊(duì)，如果我們把網(wǎng)卡看作是航空港，Linux路由器看作是陸地，那么卡車(chē)從空港裝載貨物(數(shù)據(jù)包)，要么把它運(yùn)輸?shù)侥硞€(gè)目的地(Linux作為服務(wù)器)，要么把它運(yùn)輸?shù)搅硪粋€(gè)空港(Linux作為轉(zhuǎn)發(fā)路由器)，其間這輛卡車(chē)運(yùn)送個(gè)來(lái)回即可，這輛卡車(chē)一直屬于貨物到達(dá)的那個(gè)空港，將貨物運(yùn)到另一個(gè)空港后空車(chē)返回即可?？ㄜ?chē)的使用不必中心調(diào)度，更無(wú)需用完后銷(xiāo)毀，用的時(shí)候再造一輛(Linux的轉(zhuǎn)發(fā)瓶頸即在此！??！)。

其實(shí)還有更加高效的做法，那就是卡車(chē)將貨物運(yùn)輸?shù)搅硪粋€(gè)港口或者運(yùn)輸?shù)疥懙啬康牡睾?，不必空?chē)返回，而是直接排入目的港口或者目的地的出港隊(duì)列，等待運(yùn)輸貨物滿(mǎn)載返回所屬的港口。但是對(duì)于Linux而言，由于需要路由查找后才知道卡車(chē)返回哪里，因此在出發(fā)的時(shí)候，卡車(chē)并不能確定它一定會(huì)返回它所屬的港口...因此需要對(duì)包管理隊(duì)列做一定的修正，即解除網(wǎng)卡的RX ring和skb的永久綁定關(guān)系。為了統(tǒng)一起見(jiàn)，新的設(shè)計(jì)將路由到本機(jī)的數(shù)據(jù)包也作為轉(zhuǎn)發(fā)處理，只是輸出網(wǎng)卡變成了一個(gè)BSD socket，新的設(shè)計(jì)如下圖所示：

其實(shí)，類(lèi)比火車(chē)和出租車(chē)我們就能看到這個(gè)區(qū)別。對(duì)于火車(chē)而言，它的線(xiàn)路是固定的，比如哈爾濱到漢口的火車(chē)，它屬于哈爾濱鐵路局，滿(mǎn)客到達(dá)漢口后，下客，然后漢口空車(chē)重新上客，它一定返回哈爾濱。然而對(duì)于出租車(chē)，就不是這樣，嘉定的滬C牌的出租車(chē)?yán)碚撋蠈儆诩味ǎ痪茌d情況下，一個(gè)人打車(chē)到松江，司機(jī)到松江后，雖然期待有人打他的車(chē)回嘉定，但是乘客上車(chē)后(路由查找)，告訴司機(jī)，他要到閔行，到達(dá)后，又一人上車(chē)，說(shuō)要到嘉興...越走越遠(yuǎn)，但事實(shí)就是這樣，因?yàn)槌丝蜕宪?chē)前，司機(jī)是不能確定他要去哪里的。

用戶(hù)態(tài)協(xié)議棧方案

1.爭(zhēng)議

在某些平臺(tái)上，如果不解決user/kernel切換時(shí)的cache，tlb刷新開(kāi)銷(xiāo)，這種方案并不是我主推的，這些平臺(tái)上不管是寫(xiě)直通還是寫(xiě)回，訪(fǎng)問(wèn)cache都是不經(jīng)MMU的，也不cache mmu權(quán)限，且cache直接使用虛地址。

2.爭(zhēng)議解決方案

可以采用Intel I/OAT的DCA技術(shù)，避免上下文切換導(dǎo)致的cache抖動(dòng)

3.采用PF_RING的方式

修改驅(qū)動(dòng)，直接與DMA buffer ring關(guān)聯(lián)（參見(jiàn)內(nèi)核方案的DMA優(yōu)化）。

4.借鑒Tilera的RISC超多核心方案

并行流水線(xiàn)處理每一層，流水級(jí)數(shù)為同時(shí)處理的包的數(shù)量，CPU核心數(shù)+2，流水?dāng)?shù)量為處理模塊的數(shù)量。

[ 流水線(xiàn)倒立]

本質(zhì)上來(lái)講，用戶(hù)態(tài)協(xié)議棧和內(nèi)核協(xié)議棧的方案是雷同的，無(wú)外乎還是那幾種思想。用戶(hù)態(tài)協(xié)議棧實(shí)現(xiàn)起來(lái)限制更少，更靈活，同時(shí)也更穩(wěn)定，但是并不是一味的都是好處。需要注意的是，大量存在的爭(zhēng)議都是形而上的，仁者見(jiàn)仁，智者見(jiàn)智。

穩(wěn)定性

對(duì)于非專(zhuān)業(yè)非大型路由器，穩(wěn)定性問(wèn)題可以不考慮，因?yàn)闊o(wú)需7*24，故障了大不了重啟一下而已，無(wú)傷大雅。但是就技術(shù)而言，還是有幾點(diǎn)要說(shuō)的。在高速總線(xiàn)情形下，并行總線(xiàn)容易竄擾，內(nèi)存也容易故障，一個(gè)位的錯(cuò)誤，一個(gè)電平的不穩(wěn)定都會(huì)引發(fā)不可預(yù)知的后果，所以PCI-E這種高速總線(xiàn)都采用串行的方式傳輸數(shù)據(jù)，對(duì)于硬盤(pán)而言，SATA也是一樣的道理。

在多網(wǎng)卡DMA情況下，對(duì)于通過(guò)的基于PCI-E的設(shè)備而言，總線(xiàn)上的群毆是很激烈的，這是總線(xiàn)這種拓?fù)浣Y(jié)構(gòu)所決定的，和總線(xiàn)類(lèi)型無(wú)關(guān)，再考慮到系統(tǒng)總線(xiàn)和多CPU核心，這種群毆會(huì)更加激烈，因?yàn)镃PU們也會(huì)參與進(jìn)來(lái)。群毆的時(shí)候，打翻桌椅而不是扳倒對(duì)方是很常有的事，只要考慮一下這種情況，我就想為三年前我與客戶(hù)的一次爭(zhēng)吵而向他道歉。

2012年，我做一個(gè)VPN項(xiàng)目，客戶(hù)說(shuō)我的設(shè)備可能下一秒就會(huì)宕機(jī)，因?yàn)椴淮_定性。我說(shuō)if(true) {printf("cao ni ma! ")(當(dāng)然當(dāng)時(shí)我不敢這么說(shuō));確定會(huì)執(zhí)行嗎？他說(shuō)不一定。我就上火了...可是現(xiàn)在看來(lái)，他是對(duì)的。

VOQ設(shè)計(jì)后良好的副作用-QoS

VOQ是本方案的一個(gè)亮點(diǎn)，本文幾乎是圍繞VOQ展開(kāi)的，關(guān)于另一個(gè)亮點(diǎn)DxR Pro，在其它的文章中已經(jīng)有所闡述，本文只是加以引用而已。臨近末了，我再次提到了VOQ，這次是從一個(gè)宏觀的角度，而不是細(xì)節(jié)的角度來(lái)加以說(shuō)明。

只要輸入緩沖區(qū)隊(duì)列足夠大，數(shù)據(jù)包接收幾乎就是線(xiàn)速的，然而對(duì)于輸出，卻受到了調(diào)度算法，隊(duì)頭擁塞等問(wèn)題的影響，即輸入對(duì)于系統(tǒng)來(lái)講是被動(dòng)的，中斷觸發(fā)的，而輸出對(duì)于系統(tǒng)來(lái)講則是主動(dòng)的，受制于系統(tǒng)的設(shè)計(jì)。因此對(duì)于轉(zhuǎn)發(fā)而言“收易發(fā)難”就是一個(gè)真理。因此對(duì)于QoS的位置，大多數(shù)系統(tǒng)都選擇在了輸出隊(duì)列上，因?yàn)檩斎腙?duì)列上即便對(duì)流量進(jìn)行了干預(yù)，流量在輸出的時(shí)候還是會(huì)受到二次無(wú)辜的干預(yù)，而這會(huì)影響輸入隊(duì)列上的QoS干預(yù)效果。我記得曾經(jīng)研究過(guò)Linux上的IMQ輸入隊(duì)列流控，當(dāng)時(shí)只是關(guān)注了實(shí)現(xiàn)細(xì)節(jié)，并沒(méi)有進(jìn)行形而上的思考，現(xiàn)在不了。

有了VOQ以后，配合設(shè)計(jì)良好的調(diào)度算法，幾乎解決了所有問(wèn)題，這是令人興奮的。上文中我提到輸出操作的時(shí)候，輸出線(xiàn)程采用基于數(shù)據(jù)包長(zhǎng)度以及虛擬時(shí)間的加權(quán)公平調(diào)度算法進(jìn)行輸出調(diào)度，但是這個(gè)算法的效果只是全速發(fā)送數(shù)據(jù)包。如果這個(gè)調(diào)度算法策略化，做成一個(gè)可插拔的，或者說(shuō)把Linux的TC模塊中的框架和算法移植進(jìn)來(lái)，是不是會(huì)更好呢？

唉，如果你百度“路由器 線(xiàn)速”，它搜出來(lái)的幾乎都是“路由器 限速”，這真是一個(gè)玩笑。其實(shí)對(duì)于轉(zhuǎn)發(fā)而言，你根本不用添加任何TC規(guī)則就能達(dá)到限速的效果，Linux盒子在網(wǎng)上上一串，馬上就被自動(dòng)限速了，難道不是這樣嗎？而加上VOQ以后，你確實(shí)需要限速了。就像在擁擠的中國(guó)城市中區(qū)，主干道上寫(xiě)著限速60，這不是開(kāi)玩笑嗎？哪個(gè)市中心的熙熙攘攘的街道能跑到60....但是一旦上了高速，限速100/120，就是必須的了。

VOQ設(shè)計(jì)后良好的副作用-隊(duì)頭擁塞以及加速比問(wèn)題

用硬件路由器的術(shù)語(yǔ)，如果采用將數(shù)據(jù)包路由后排隊(duì)到輸出網(wǎng)卡隊(duì)列的方案，那么就會(huì)有多塊網(wǎng)卡同時(shí)往一塊網(wǎng)卡排隊(duì)數(shù)據(jù)包的情況，這對(duì)于輸出網(wǎng)卡而言是被動(dòng)的，這又是一個(gè)令人悲傷的群毆過(guò)程，為了讓多個(gè)包都能同時(shí)到達(dá)，輸出帶寬一定要是各個(gè)輸入帶寬的加和，這就是N倍加速問(wèn)題，我們希望的是一個(gè)輸出網(wǎng)卡主動(dòng)對(duì)數(shù)據(jù)包進(jìn)行調(diào)度的過(guò)程，有序必然高效。這就是VOQ設(shè)計(jì)的精髓。

對(duì)于Linux而言，由于它的輸出隊(duì)列是軟件的，因此N加速比問(wèn)題變成了隊(duì)列鎖定問(wèn)題，總之，還是一個(gè)令人遺憾的群毆過(guò)程，因此應(yīng)對(duì)方案的思想是一致的。因此在Linux中我就模擬了一個(gè)VOQ。從這里我們可以看出VOQ和輸出排隊(duì)的區(qū)別，VOQ對(duì)于輸出過(guò)程而言是主動(dòng)調(diào)度的過(guò)程，顯然更加高效，而輸出排隊(duì)對(duì)于輸出過(guò)程而言則是一個(gè)被動(dòng)被爭(zhēng)搶的過(guò)程，顯然這是令人感到無(wú)望的。

需要說(shuō)明的是，VOQ只是一個(gè)邏輯上的概念，類(lèi)比了硬件路由器的概念。如果依然堅(jiān)持使用輸出排隊(duì)而不是VOQ，那么設(shè)計(jì)多個(gè)輸出隊(duì)列，每一個(gè)網(wǎng)卡一個(gè)隊(duì)列也是合理的，它甚至更加簡(jiǎn)化，壓縮掉了一個(gè)網(wǎng)卡分派過(guò)程，簡(jiǎn)化了調(diào)度。于是我們得到了Linux VOQ設(shè)計(jì)的第三版：將虛擬輸出隊(duì)列VOQ關(guān)聯(lián)到輸出網(wǎng)卡而不是輸入網(wǎng)卡(下面一小節(jié)我將分析原因)。

總線(xiàn)拓?fù)浜虲rossbar

真正的硬件路由器，比如Cisco，華為的設(shè)備，路由轉(zhuǎn)發(fā)全由線(xiàn)卡硬件執(zhí)行，數(shù)據(jù)包在此期間是靜止在那里的，查詢(xún)轉(zhuǎn)發(fā)表的速度是如此之快，以至于相對(duì)將數(shù)據(jù)包挪到輸出網(wǎng)卡隊(duì)列的開(kāi)銷(xiāo)，查表開(kāi)銷(xiāo)可以忽略。因此在真正的硬件路由器上，如何構(gòu)建一個(gè)高性能交換網(wǎng)絡(luò)就是重中之重。

不但如此，硬件路由器還需要考慮的是，數(shù)據(jù)包在路由查詢(xún)過(guò)后是由輸入處理邏輯直接通過(guò)交換網(wǎng)絡(luò)PUSH到輸出網(wǎng)卡隊(duì)列呢，還是原地不動(dòng)，然后等待輸出邏輯通過(guò)交換網(wǎng)絡(luò)把數(shù)據(jù)包PULL到那里。這個(gè)不同會(huì)影響到交換網(wǎng)絡(luò)仲裁器的設(shè)計(jì)。如果有多個(gè)網(wǎng)卡同時(shí)往一個(gè)網(wǎng)卡輸出數(shù)據(jù)包，PUSH方式可能會(huì)產(chǎn)生沖突，因?yàn)樵贑rossbar的一條路徑上，它相當(dāng)于一條總線(xiàn)，而且沖突一般會(huì)發(fā)生在交換網(wǎng)絡(luò)內(nèi)部，因此這種PUSH的情況下，一般會(huì)在交換網(wǎng)絡(luò)內(nèi)部的開(kāi)關(guān)節(jié)點(diǎn)上攜帶cache，用來(lái)暫存沖突仲裁失敗的數(shù)據(jù)包。反之，如果是PULL方式，情況就有所不同。因此把輸出隊(duì)列放在交換網(wǎng)絡(luò)的哪一側(cè)帶來(lái)的效果是不同的。

但是對(duì)于通用系統(tǒng)架構(gòu)，一般都是采用PCI-E總線(xiàn)連接各個(gè)網(wǎng)卡，這是一種典型的總線(xiàn)結(jié)構(gòu)，根本就沒(méi)有所謂的交換網(wǎng)絡(luò)。因此所謂的仲裁就是總線(xiàn)仲裁，這并不是我關(guān)注的重點(diǎn)，誰(shuí)讓我手上只有一個(gè)通用架構(gòu)的設(shè)備呢？！我的優(yōu)化不包括總線(xiàn)仲裁器的設(shè)計(jì)，因?yàn)槲也欢@個(gè)。

因此，對(duì)于通用架構(gòu)總線(xiàn)拓?fù)涞腖inux協(xié)議棧轉(zhuǎn)發(fā)優(yōu)化而言，虛擬輸出隊(duì)列VOQ關(guān)聯(lián)在輸入網(wǎng)卡還是輸出網(wǎng)卡，影響不會(huì)太大。但是考慮到連續(xù)內(nèi)存訪(fǎng)問(wèn)帶來(lái)的局部性?xún)?yōu)化，我還是傾向?qū)OQ關(guān)聯(lián)到輸出網(wǎng)卡。如果VOQ關(guān)聯(lián)到輸入網(wǎng)卡，那么在進(jìn)行輸出調(diào)度的時(shí)候，輸出網(wǎng)卡的輸出線(xiàn)程就要從輸出位圖指示的每一個(gè)待發(fā)送數(shù)據(jù)的輸入網(wǎng)卡VOQ中與自己關(guān)聯(lián)的隊(duì)列調(diào)度數(shù)據(jù)包，無(wú)疑，這些隊(duì)列在內(nèi)存中是不連續(xù)的，如果關(guān)聯(lián)到輸出網(wǎng)卡，對(duì)于每一個(gè)輸出網(wǎng)卡而言，VOQ是連續(xù)的。如下圖所示：

實(shí)現(xiàn)相關(guān)

前面我們提到skb只是作為容器(卡車(chē))存在。因此skb是不必釋放的。理想情況下，在Linux內(nèi)核啟動(dòng)，網(wǎng)絡(luò)協(xié)議棧初始化的時(shí)候，根據(jù)自身的硬件性能和網(wǎng)卡參數(shù)做一次自測(cè)，然后分配MAX個(gè)skb，這些skb可以先均勻分配到各個(gè)網(wǎng)卡，同時(shí)預(yù)留一個(gè)socket skb池，供用戶(hù)socket取。后面的事情就是skb運(yùn)輸行為了，卡車(chē)開(kāi)到哪里算哪里，運(yùn)輸過(guò)程不空載。

可能你會(huì)覺(jué)得這個(gè)沒(méi)有必要，因?yàn)閟kb本身甚至整個(gè)Linux內(nèi)核中絕大部分內(nèi)存分配都是被預(yù)先分配并cache的，slab就是做這個(gè)的，不是有kmem_cache機(jī)制嗎？是這樣的，我承認(rèn)Linux內(nèi)核在這方面做得很不錯(cuò)。但是kmem_cache是一個(gè)通用的框架，為何不針對(duì)skb再提高一個(gè)層次呢？每一次調(diào)用alloc_skb，都會(huì)觸發(fā)到kmem_cache框架內(nèi)的管理機(jī)制做很多工作，更新數(shù)據(jù)結(jié)構(gòu)，維護(hù)鏈表等，甚至可能會(huì)觸及到更加底層的伙伴系統(tǒng)。因此，期待直接使用高效的kmem_cache并不是一個(gè)好的主意。

你可能會(huì)反駁說(shuō)萬(wàn)一系統(tǒng)內(nèi)存吃緊也不釋放嗎？萬(wàn)事并不絕對(duì)，但這并不是本文的范疇，這涉及到很多方面，比如cgroup等。

針對(duì)skb的修改，我添加了一個(gè)字段，指示它的所屬地(某個(gè)網(wǎng)卡？socket池？...)，當(dāng)前所屬地，這些信息可以維護(hù)skb不會(huì)被free到kmem_cache，同時(shí)也可以最優(yōu)化cache利用率。這部分修改已經(jīng)實(shí)現(xiàn)，目前正在針對(duì)Intel千兆卡的驅(qū)動(dòng)做進(jìn)一步修改。關(guān)于DxR Pro的性能，我在用戶(hù)態(tài)已經(jīng)經(jīng)過(guò)測(cè)試，目前還沒(méi)有移植到內(nèi)核。

關(guān)于快速查找表的實(shí)現(xiàn)，目前的思路是優(yōu)化nf_conntrack，做多級(jí)hash查找。

審核編輯：湯梓紅