Linux轉(zhuǎn)發(fā)性能評(píng)估與優(yōu)化(轉(zhuǎn)發(fā)瓶頸分析與解決方案)
[導(dǎo)讀]原文作者：dog250原文鏈接：https://blog.csdn.net/dog250/article/details/46666029線速問(wèn)題很多人對(duì)這個(gè)線速概念存在誤解。認(rèn)為所謂線速能力就是路由器/交換機(jī)就像一根網(wǎng)線一樣。而這，是不可能的。應(yīng)該考慮到的一個(gè)概念就是延遲。數(shù)據(jù)...
原文作者：dog250原文鏈接：https://blog.csdn.net/dog250/article/details/46666029
線速問(wèn)題
很多人對(duì)這個(gè)線速概念存在誤解。認(rèn)為所謂線速能力就是路由器/交換機(jī)就像一根網(wǎng)線一樣。而這，是不可能的。應(yīng)該考慮到的一個(gè)概念就是延遲。數(shù)據(jù)包進(jìn)入路由器或者交換機(jī)，存在一個(gè)核心延遲操作，這就是選路，對(duì)于路由器而言，就是路由查找，對(duì)于交換機(jī)而言，就是查詢MAC/端口映射表，這個(gè)延遲是無(wú)法避開(kāi)的，這個(gè)操作需要大量的計(jì)算機(jī)資源，所以不管是路由器還是交換機(jī)，數(shù)據(jù)包在內(nèi)部是不可能像在線纜上那樣近光速傳輸?shù)?。類比一下你?jīng)過(guò)十字街頭的時(shí)候，是不是要左顧右盼呢？
那么，設(shè)備的線速能力怎么衡量呢？如果一個(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è)了，這就是線速。
我們可以用電容來(lái)理解轉(zhuǎn)發(fā)設(shè)備。有人可能會(huì)覺(jué)得電容具有通高頻阻低頻的功效，我說(shuō)的不是這個(gè)，所以咱不考慮低頻，僅以高頻為例，電容具有存儲(chǔ)電荷的功能，這就類似存儲(chǔ)轉(zhuǎn)發(fā)，電容充電的過(guò)程類似于數(shù)據(jù)包進(jìn)入輸入隊(duì)列緩沖區(qū)，電容放電的過(guò)程類似于數(shù)據(jù)包從輸出緩沖區(qū)輸出，我們可以看到，在電流經(jīng)過(guò)電容的前后，其速度是不變的，然而針對(duì)具體的電荷而言，從電容放出的電荷絕不是剛剛在在另一側(cè)充電的那個(gè)電荷，電容的充電放電擁有固有延遲。
我們回到轉(zhuǎn)發(fā)設(shè)備。對(duì)于交換機(jī)和路由器而言，衡量標(biāo)準(zhǔn)是不同的。
對(duì)于交換機(jī)而言，線速能力是背板總帶寬，因?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è)流出，那么其線速就是100pps。
本文針對(duì)路由器而不針對(duì)交換機(jī)。路由器的核心延遲在路由查找，而這個(gè)查找不會(huì)受到數(shù)據(jù)包長(zhǎng)度的影響，因此決定路由器線速能力的核心就在數(shù)據(jù)包輸出的效率，注意，不是數(shù)據(jù)包輸入的效率，因?yàn)橹灰?duì)列足夠長(zhǎng)，緩存足夠大，輸入總是線速的。但是輸入操作就涉及到了如何調(diào)度的問(wèn)題。這也就說(shuō)明了為何很多路由器都支持輸出流量控制而不是輸入流量控制的原因，因?yàn)檩斎肓骺丶词雇昝劳瓿?，它也?huì)受到路由器輸出端口自身輸出效率的影響，流控結(jié)果將不再準(zhǔn)確。
在寫這個(gè)方案的前晚，有一個(gè)故事。我最近聯(lián)系到了初中時(shí)一起玩搖滾玩音響的超級(jí)鐵的朋友，他現(xiàn)在搞舞臺(tái)設(shè)計(jì)，燈光音響之類的。我問(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)容上也只是寫了些我認(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)上也有大量的此類文章，比如什么將Linux變成路由器之類的，無(wú)非就是打開(kāi)ip_forward，加幾條iptables規(guī)則，搞個(gè)配置起來(lái)比較方便的WEB界面...我想說(shuō)這些太低級(jí)了，甚至超級(jí)低級(jí)。我很想談一下關(guān)于專業(yè)路由器的我的觀點(diǎn)，但是今天是小小的生日，玩了一天，就不寫了。只是把我的方案整理出來(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訪問(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問(wèn)內(nèi)存需要經(jīng)過(guò)總線，首先總線競(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)法比。所以必須采用類似Intel I/OAT的技術(shù)才能改善。
1.1.Linux作為服務(wù)器時(shí)采用標(biāo)準(zhǔn)零拷貝map技術(shù)完全勝任。這是因?yàn)?，運(yùn)行于Linux的服務(wù)器和線速轉(zhuǎn)發(fā)相比就是個(gè)蝸牛，服務(wù)器在處理客戶端請(qǐng)求時(shí)消耗的時(shí)間是一個(gè)硬性時(shí)間，無(wú)法優(yōu)化，這是代償原理。Linux服務(wù)唯一需要的就是能快速取到客戶端的數(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)銷過(guò)大，總線爭(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ì)于高速線速設(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，總線爭(zhēng)搶，原子鎖等，實(shí)際上，內(nèi)存管理才是根本中的根本，這里面道道太多，它直接影響CPU cache，后者又會(huì)影響總線...從哪里分配內(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效率不高（查詢代價(jià)太大，不固定大小，僅有弱智的老化算法，導(dǎo)致海量地址訪問(wèn)時(shí)，路由cache沖突鏈過(guò)長(zhǎng)），最終在內(nèi)核協(xié)議棧中下課。如果沒(méi)有一個(gè)好的轉(zhuǎn)發(fā)表，那么Linux協(xié)議棧在海量路由存在時(shí)對(duì)于線速能力就是一個(gè)瓶頸，這是一個(gè)可擴(kuò)展性問(wèn)題。另外，很多的查詢結(jié)果都是可以被在一個(gè)地方緩存的，但是Linux協(xié)議棧沒(méi)有這種緩存。比如，路由查詢結(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ì)稱的加鎖，也就是說(shuō)，比如每次查路由表時(shí)都要加鎖，為何？因?yàn)榕略诓樵兊钠陂g路由表改變了...然而你仔細(xì)想想，在高速轉(zhuǎn)發(fā)情景下，查找操作和修改操作在單位時(shí)間的比率是多少呢？不要以為你用讀寫鎖就好了，讀寫鎖不也有關(guān)搶占的操作嗎(雖然我們已經(jīng)建議關(guān)閉了搶占)？起碼也浪費(fèi)了幾個(gè)指令周期。這些時(shí)間幾率不對(duì)稱操作的加鎖是不必要的。你只需要保證內(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)核線程上下文中運(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總線上，如果DMA管理不善，總線的占用和爭(zhēng)搶帶來(lái)的性能開(kāi)銷將會(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)銷)以及查表操作(算法不好導(dǎo)致的開(kāi)銷)]
綜述：Linux轉(zhuǎn)發(fā)效率受到以下幾大因素影響
IO/輸入輸出的隊(duì)列管理/內(nèi)存修改拷貝 （重新設(shè)計(jì)類似crossbar的隊(duì)列管理實(shí)現(xiàn)DMA ring交換）各種表查詢操作，特別是最長(zhǎng)前綴匹配，諸多本身唯一確定的查詢操作之間的關(guān)聯(lián)沒(méi)有建立SMP下處理器同步（鎖開(kāi)銷）（使用大讀鎖以及RCU鎖）以及cache利用率中斷以及軟中斷調(diào)度
Linux轉(zhuǎn)發(fā)性能提升方案
概述此方案的思路來(lái)自基于crossbar的新一代硬件路由器。設(shè)計(jì)要點(diǎn)：
1.重新設(shè)計(jì)的DMA包管理隊(duì)列（ 思路來(lái)自Linux O(1)調(diào)度器，crossbar陣列以及VOQ[虛擬輸出隊(duì)列]）2.重新設(shè)計(jì)的基于定位而非最長(zhǎng)前綴查找的轉(zhuǎn)發(fā)表3.長(zhǎng)線程處理（中斷線程化，處理流水線化，增加CPU親和）4.數(shù)據(jù)結(jié)構(gòu)無(wú)鎖化（基于線程局部數(shù)據(jù)結(jié)構(gòu)）5.實(shí)現(xiàn)方式5.1.驅(qū)動(dòng)以及內(nèi)核協(xié)議棧修改5.2.完全的用戶態(tài)協(xié)議棧5.3.評(píng)估：用戶態(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)（如果有的話）7).最小化用戶態(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總線拓?fù)?非crossbar！)的網(wǎng)絡(luò)線速不到滿載60% pps]2).減少爭(zhēng)搶式DMA，減少鎖總線[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：每線程負(fù)責(zé)一塊網(wǎng)卡(甚至輸入和輸出由不同的線程負(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).犧牲用戶態(tài)進(jìn)程的調(diào)度機(jī)會(huì)，全部精力集中于內(nèi)核協(xié)議棧的處理，多CPU多路并行的[ Tips：如果有超多的CPU，建議劃分cgroup ]4).中斷處理線程化，內(nèi)核線程化，多核心并行執(zhí)行長(zhǎng)路經(jīng)，避免切換抖動(dòng)5).線程內(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).盡量采用線程局部數(shù)據(jù)每個(gè)線程一張轉(zhuǎn)發(fā)表（由路由表生成，OpenVPN多線程采用，但失?。?，采用定位而非最長(zhǎng)前綴查找（DxR或者我設(shè)計(jì)的那個(gè)）。若不采用為每個(gè)線程復(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)化lock1).查詢定位局部表，無(wú)鎖（甚至RW鎖都沒(méi)有）不禁止中斷2).臨界區(qū)和內(nèi)核線程關(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ì)造成總線開(kāi)銷和CPU同步開(kāi)銷，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之類的接口]? ? ? ? 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)自Linux協(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)。類比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ì)將代碼改成這么做的。如果類比高端路由器的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)題迎刃而解，剩下的就是硬件總線的爭(zhēng)用問(wèn)題(對(duì)于高性能crossbar路由器而言，這也是一個(gè)二分圖匹配問(wèn)題，但對(duì)于總線結(jié)構(gòu)的通用系統(tǒng)而言有點(diǎn)區(qū)別，后面我會(huì)談到)了，作為我們而言，這一點(diǎn)除了使用性價(jià)比更高的總線，比如我們使用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é)議棧打造成比肩專業(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)稱作DxR Pro 。至于說(shuō)查找操作之間的關(guān)聯(lián)，這也是一個(gè)深度優(yōu)化，底層構(gòu)建高速查詢流表實(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é)議棧的底層保存一張可以高速查詢的流表，協(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)題。我基于讀寫的不對(duì)稱性，著手采用event的方式通知更新，比如慢速路徑中的數(shù)據(jù)項(xiàng)(路由，MAC信息，NAT，ACL信息等)，一旦這些信息更改，內(nèi)核會(huì)專門觸發(fā)一個(gè)查詢操作，將快速流表中與之相關(guān)的表項(xiàng)disable掉即可。值得注意的是，這個(gè)查詢操作沒(méi)必要太快，因?yàn)橄啾容^快速轉(zhuǎn)發(fā)而言，數(shù)據(jù)同步的頻率要慢天文數(shù)字個(gè)數(shù)量級(jí)...類似Cisco的設(shè)備，可以創(chuàng)建幾個(gè)內(nèi)核線程定期刷新慢速路徑表項(xiàng)，用來(lái)發(fā)現(xiàn)數(shù)據(jù)項(xiàng)的更改，從而觸發(fā)event。
[Tips：可以高速查找的流表結(jié)構(gòu)可用多級(jí)hash（采用TCAM的類似方案），也可以借鑒我的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)訪問(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)核線程組成一個(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(
線速問(wèn)題
很多人對(duì)這個(gè)線速概念存在誤解。認(rèn)為所謂線速能力就是路由器/交換機(jī)就像一根網(wǎng)線一樣。而這，是不可能的。應(yīng)該考慮到的一個(gè)概念就是延遲。數(shù)據(jù)包進(jìn)入路由器或者交換機(jī)，存在一個(gè)核心延遲操作，這就是選路，對(duì)于路由器而言，就是路由查找，對(duì)于交換機(jī)而言，就是查詢MAC/端口映射表，這個(gè)延遲是無(wú)法避開(kāi)的，這個(gè)操作需要大量的計(jì)算機(jī)資源，所以不管是路由器還是交換機(jī)，數(shù)據(jù)包在內(nèi)部是不可能像在線纜上那樣近光速傳輸?shù)?。類比一下你?jīng)過(guò)十字街頭的時(shí)候，是不是要左顧右盼呢？
那么，設(shè)備的線速能力怎么衡量呢？如果一個(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è)了，這就是線速。
我們可以用電容來(lái)理解轉(zhuǎn)發(fā)設(shè)備。有人可能會(huì)覺(jué)得電容具有通高頻阻低頻的功效，我說(shuō)的不是這個(gè)，所以咱不考慮低頻，僅以高頻為例，電容具有存儲(chǔ)電荷的功能，這就類似存儲(chǔ)轉(zhuǎn)發(fā)，電容充電的過(guò)程類似于數(shù)據(jù)包進(jìn)入輸入隊(duì)列緩沖區(qū)，電容放電的過(guò)程類似于數(shù)據(jù)包從輸出緩沖區(qū)輸出，我們可以看到，在電流經(jīng)過(guò)電容的前后，其速度是不變的，然而針對(duì)具體的電荷而言，從電容放出的電荷絕不是剛剛在在另一側(cè)充電的那個(gè)電荷，電容的充電放電擁有固有延遲。
我們回到轉(zhuǎn)發(fā)設(shè)備。對(duì)于交換機(jī)和路由器而言，衡量標(biāo)準(zhǔn)是不同的。
對(duì)于交換機(jī)而言，線速能力是背板總帶寬，因?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è)流出，那么其線速就是100pps。
本文針對(duì)路由器而不針對(duì)交換機(jī)。路由器的核心延遲在路由查找，而這個(gè)查找不會(huì)受到數(shù)據(jù)包長(zhǎng)度的影響，因此決定路由器線速能力的核心就在數(shù)據(jù)包輸出的效率，注意，不是數(shù)據(jù)包輸入的效率，因?yàn)橹灰?duì)列足夠長(zhǎng)，緩存足夠大，輸入總是線速的。但是輸入操作就涉及到了如何調(diào)度的問(wèn)題。這也就說(shuō)明了為何很多路由器都支持輸出流量控制而不是輸入流量控制的原因，因?yàn)檩斎肓骺丶词雇昝劳瓿?，它也?huì)受到路由器輸出端口自身輸出效率的影響，流控結(jié)果將不再準(zhǔn)確。
在寫這個(gè)方案的前晚，有一個(gè)故事。我最近聯(lián)系到了初中時(shí)一起玩搖滾玩音響的超級(jí)鐵的朋友，他現(xiàn)在搞舞臺(tái)設(shè)計(jì)，燈光音響之類的。我問(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)容上也只是寫了些我認(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)上也有大量的此類文章，比如什么將Linux變成路由器之類的，無(wú)非就是打開(kāi)ip_forward，加幾條iptables規(guī)則，搞個(gè)配置起來(lái)比較方便的WEB界面...我想說(shuō)這些太低級(jí)了，甚至超級(jí)低級(jí)。我很想談一下關(guān)于專業(yè)路由器的我的觀點(diǎn)，但是今天是小小的生日，玩了一天，就不寫了。只是把我的方案整理出來(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訪問(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問(wèn)內(nèi)存需要經(jīng)過(guò)總線，首先總線競(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)法比。所以必須采用類似Intel I/OAT的技術(shù)才能改善。
1.1.Linux作為服務(wù)器時(shí)采用標(biāo)準(zhǔn)零拷貝map技術(shù)完全勝任。這是因?yàn)?，運(yùn)行于Linux的服務(wù)器和線速轉(zhuǎn)發(fā)相比就是個(gè)蝸牛，服務(wù)器在處理客戶端請(qǐng)求時(shí)消耗的時(shí)間是一個(gè)硬性時(shí)間，無(wú)法優(yōu)化，這是代償原理。Linux服務(wù)唯一需要的就是能快速取到客戶端的數(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)銷過(guò)大，總線爭(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ì)于高速線速設(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，總線爭(zhēng)搶，原子鎖等，實(shí)際上，內(nèi)存管理才是根本中的根本，這里面道道太多，它直接影響CPU cache，后者又會(huì)影響總線...從哪里分配內(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效率不高（查詢代價(jià)太大，不固定大小，僅有弱智的老化算法，導(dǎo)致海量地址訪問(wèn)時(shí)，路由cache沖突鏈過(guò)長(zhǎng)），最終在內(nèi)核協(xié)議棧中下課。如果沒(méi)有一個(gè)好的轉(zhuǎn)發(fā)表，那么Linux協(xié)議棧在海量路由存在時(shí)對(duì)于線速能力就是一個(gè)瓶頸，這是一個(gè)可擴(kuò)展性問(wèn)題。另外，很多的查詢結(jié)果都是可以被在一個(gè)地方緩存的，但是Linux協(xié)議棧沒(méi)有這種緩存。比如，路由查詢結(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ì)稱的加鎖，也就是說(shuō)，比如每次查路由表時(shí)都要加鎖，為何？因?yàn)榕略诓樵兊钠陂g路由表改變了...然而你仔細(xì)想想，在高速轉(zhuǎn)發(fā)情景下，查找操作和修改操作在單位時(shí)間的比率是多少呢？不要以為你用讀寫鎖就好了，讀寫鎖不也有關(guān)搶占的操作嗎(雖然我們已經(jīng)建議關(guān)閉了搶占)？起碼也浪費(fèi)了幾個(gè)指令周期。這些時(shí)間幾率不對(duì)稱操作的加鎖是不必要的。你只需要保證內(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)核線程上下文中運(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總線上，如果DMA管理不善，總線的占用和爭(zhēng)搶帶來(lái)的性能開(kāi)銷將會(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)銷)以及查表操作(算法不好導(dǎo)致的開(kāi)銷)]
綜述：Linux轉(zhuǎn)發(fā)效率受到以下幾大因素影響
IO/輸入輸出的隊(duì)列管理/內(nèi)存修改拷貝 （重新設(shè)計(jì)類似crossbar的隊(duì)列管理實(shí)現(xiàn)DMA ring交換）各種表查詢操作，特別是最長(zhǎng)前綴匹配，諸多本身唯一確定的查詢操作之間的關(guān)聯(lián)沒(méi)有建立SMP下處理器同步（鎖開(kāi)銷）（使用大讀鎖以及RCU鎖）以及cache利用率中斷以及軟中斷調(diào)度
Linux轉(zhuǎn)發(fā)性能提升方案
概述此方案的思路來(lái)自基于crossbar的新一代硬件路由器。設(shè)計(jì)要點(diǎn)：
1.重新設(shè)計(jì)的DMA包管理隊(duì)列（ 思路來(lái)自Linux O(1)調(diào)度器，crossbar陣列以及VOQ[虛擬輸出隊(duì)列]）2.重新設(shè)計(jì)的基于定位而非最長(zhǎng)前綴查找的轉(zhuǎn)發(fā)表3.長(zhǎng)線程處理（中斷線程化，處理流水線化，增加CPU親和）4.數(shù)據(jù)結(jié)構(gòu)無(wú)鎖化（基于線程局部數(shù)據(jù)結(jié)構(gòu)）5.實(shí)現(xiàn)方式5.1.驅(qū)動(dòng)以及內(nèi)核協(xié)議棧修改5.2.完全的用戶態(tài)協(xié)議棧5.3.評(píng)估：用戶態(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)（如果有的話）7).最小化用戶態(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總線拓?fù)?非crossbar！)的網(wǎng)絡(luò)線速不到滿載60% pps]2).減少爭(zhēng)搶式DMA，減少鎖總線[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：每線程負(fù)責(zé)一塊網(wǎng)卡(甚至輸入和輸出由不同的線程負(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).犧牲用戶態(tài)進(jìn)程的調(diào)度機(jī)會(huì)，全部精力集中于內(nèi)核協(xié)議棧的處理，多CPU多路并行的[ Tips：如果有超多的CPU，建議劃分cgroup ]4).中斷處理線程化，內(nèi)核線程化，多核心并行執(zhí)行長(zhǎng)路經(jīng)，避免切換抖動(dòng)5).線程內(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).盡量采用線程局部數(shù)據(jù)每個(gè)線程一張轉(zhuǎn)發(fā)表（由路由表生成，OpenVPN多線程采用，但失?。?，采用定位而非最長(zhǎng)前綴查找（DxR或者我設(shè)計(jì)的那個(gè)）。若不采用為每個(gè)線程復(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)化lock1).查詢定位局部表，無(wú)鎖（甚至RW鎖都沒(méi)有）不禁止中斷2).臨界區(qū)和內(nèi)核線程關(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ì)造成總線開(kāi)銷和CPU同步開(kāi)銷，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之類的接口]? ? ? ? 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)自Linux協(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)。類比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ì)將代碼改成這么做的。如果類比高端路由器的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)題迎刃而解，剩下的就是硬件總線的爭(zhēng)用問(wèn)題(對(duì)于高性能crossbar路由器而言，這也是一個(gè)二分圖匹配問(wèn)題，但對(duì)于總線結(jié)構(gòu)的通用系統(tǒng)而言有點(diǎn)區(qū)別，后面我會(huì)談到)了，作為我們而言，這一點(diǎn)除了使用性價(jià)比更高的總線，比如我們使用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é)議棧打造成比肩專業(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)稱作DxR Pro 。至于說(shuō)查找操作之間的關(guān)聯(lián)，這也是一個(gè)深度優(yōu)化，底層構(gòu)建高速查詢流表實(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é)議棧的底層保存一張可以高速查詢的流表，協(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)題。我基于讀寫的不對(duì)稱性，著手采用event的方式通知更新，比如慢速路徑中的數(shù)據(jù)項(xiàng)(路由，MAC信息，NAT，ACL信息等)，一旦這些信息更改，內(nèi)核會(huì)專門觸發(fā)一個(gè)查詢操作，將快速流表中與之相關(guān)的表項(xiàng)disable掉即可。值得注意的是，這個(gè)查詢操作沒(méi)必要太快，因?yàn)橄啾容^快速轉(zhuǎn)發(fā)而言，數(shù)據(jù)同步的頻率要慢天文數(shù)字個(gè)數(shù)量級(jí)...類似Cisco的設(shè)備，可以創(chuàng)建幾個(gè)內(nèi)核線程定期刷新慢速路徑表項(xiàng)，用來(lái)發(fā)現(xiàn)數(shù)據(jù)項(xiàng)的更改，從而觸發(fā)event。
[Tips：可以高速查找的流表結(jié)構(gòu)可用多級(jí)hash（采用TCAM的類似方案），也可以借鑒我的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)訪問(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)核線程組成一個(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(
下載文檔
