之前發過一篇二級指針操作單向鏈表的例子，顯示了C語言指針的靈活性，這次再探討一個指針操作鏈表的例子，而且是一種完全不同的用法。
這個例子是linux-1.2.13網絡協議棧裡的，關於鏈表遍歷&數據拷貝的一處實現。源文件是/net/inet/dev.c，你可以從kernel.org官網上下載。
從最早的0.96c版本開始，linux網絡部分一直采取TCP/IP協議族實現，這是最為廣泛應用的網絡協議，整個架構就是經典的OSI七層模型的描述，其中dev.c是屬於鏈路層實現。從功能上看，其位於網絡設備驅動程序和網絡層協議實現模塊之間，作為二者之間的數據包傳輸通道，一種接口模塊而存在——對驅動層的接口函數netif_rx, 以及對網絡層的接口函數net_bh。前者提供給驅動模塊的中斷例程調用，用於鏈路數據幀的封裝；後者作為驅動中斷例程底半部(buttom half)，用於對數據幀的解析處理並向上層傳送。
為了便於理解，這裡補充一下網絡通信原理和linux驅動中斷機制的背景知識。從最底層的物理層說起，當主機和路由器相互之間進行通信的時候，在物理介質上同軸、光纖等）以電平信號進行傳輸。主機或路由器的硬件接口網卡）負責收發這些信號，當信號發送到接口，再由內置的調制解調器(modem)將數字信號轉換成二進制碼，這樣才能駐留在主機的硬件緩存中。這時接口網卡）設備驅動程序將通過硬中斷來獲取硬件緩存中的數據，驅動程序是操作系統中負責直接同硬件設備打交道的模塊，硬中斷的觸發是初始化時通過設置控制寄存器實現的，用於通知驅動程序硬件緩存中有新的數據到來。linux卡設備驅動就是在中斷處理例程(ISR)中將硬件緩存數據拷貝到內核緩存中，打包成數據鏈路幀進行解析處理，再向上分發到各種協議層。由於ISR上下文是原子性的、中斷屏蔽的，整個步驟又較為繁瑣，因此全部放在ISR中處理會影響到其它中斷響應實時性，於是linux有實現一種bottom half的軟中斷處理機制，將整個ISR一分為二，前半部上下文屏蔽所有中斷，專門處理緊急的、實時性強的事務，如拷貝硬件緩存並打包封裝，後半部上下文沒有屏蔽中斷但代碼不可重入），用於處理比較耗時且非緊急事務，包括數據幀的解析處理和分發。下面要講的net_bh就屬於後半部。
我們主要關心的是將鏈路幀分發到協議層那一段邏輯，下面摘自net_bh函數中的一段代碼：
- 526 void net_bh(void *tmp)
- 527 {
- ...
- 577
- 578 /*
- 579 * We got a packet ID. Now loop over the "known protocols"
- 580 * table (which is actually a linked list, but this will
- 581 * change soon if I get my way- FvK), and forward the packet
- 582 * to anyone who wants it.
- 583 *
- 584 * [FvK didn't get his way but he is right this ought to be
- 585 * hashed so we typically get a single hit. The speed cost
- 586 * here is minimal but no doubt adds up at the 4,000+ pkts/second
- 587 * rate we can hit flat out]
- 588 */
- 589 pt_prev = NULL;
- 590 for (ptype = ptype_base; ptype != NULL; ptype = ptype->next)
- 591 {
- 592 if ((ptype->type == type || ptype->type == htons(ETH_P_ALL)) && (!ptype->dev || ptype->dev==skb->dev))
- 593 {
- 594 /*
- 595 * We already have a match queued. Deliver
- 596 * to it and then remember the new match
- 597 */
- 598 if(pt_prev)
- 599 {
- 600 struct sk_buff *skb2;
- 601 skb2=skb_clone(skb, GFP_ATOMIC);
- 602 /*
- 603 * Kick the protocol handler. This should be fast
- 604 * and efficient code.
- 605 */
- 606 if(skb2)
- 607 pt_prev->func(skb2, skb->dev, pt_prev);
- 608 }
- 609 /* Remember the current last to do */
- 610 pt_prev=ptype;
- 611 }
- 612 } /* End of protocol list loop */
- 613 /*
- 614 * Is there a last item to send to ?
- 615 */
- 616 if(pt_prev)
- 617 pt_prev->func(skb, skb->dev, pt_prev);
- 618 /*
- 619 * Has an unknown packet has been received ?
- 620 */
- 621 else
- 622 kfree_skb(skb, FREE_WRITE);
- 623
- ...
- 640 }
在此稍稍解說一下數據結構，skb就是內核緩存中sock數據封裝，協議棧裡從鏈路層到傳輸層都會用到，只不過封裝格式不同，主要是對協議首部(header)的由下而上層層剝離反之由上而下是層層創建），在此你只需理解為一個鏈路數據幀即可。這段代碼的邏輯是解析skb中的協議字段，從協議類型鏈表由 ptype_base維護）中查詢對應的協議節點進行函數指針func回調，以便將數據幀分發到相應的協議層如ARP、IP、8022、8023等）。
第一眼看上去是不是有點奇怪？這段代碼竟然用一個pt_prev指針去維護ptype鏈表中前一個節點，從而產生了額外的條件分支判斷，咋一看是否多了很多“余”了？回顧一下那篇二級指針操作單向鏈表的博文，簡直完全是反其道而行之的。如果把pt_prev去掉，代碼可以精簡為：
- for (ptype = ptype_base; ptype != NULL; ptype = ptype->next)
- {
- if ((ptype->type == type || ptype->type == htons(ETH_P_ALL)) && (!ptype->dev || ptype->dev==skb->dev))
- {
- /*
- * We already have a match queued. Deliver
- * to it and then remember the new match
- */
- struct sk_buff *skb2;
- skb2=skb_clone(skb, GFP_ATOMIC);
- /*
- * Kick the protocol handler. This should be fast
- * and efficient code.
- */
- if(skb2)
- pt_prev->func(skb2, skb->dev, pt_prev);
- }
- } /* End of protocol list loop */
- kfree_skb(skb, FREE_WRITE);
咋看一下“干淨”了很多，不是嗎？但我們要記住一點，凡是網上發布的linux內核源代碼，都是都是經過眾多黑客高手們重重檢視並驗證過的，人家這麼寫肯定有十分充足的理由，所以不要太過於相信自己的直覺了，讓我們再好好review一下代碼吧！看看這段循環裡做了什麼事情？特別是第592~611 行。
由於從網絡上拷貝過來skb是唯一的，而分發的協議對象可能是多個，所以在回調之前要做一次clone動作注意這裡是深度拷貝，相當於一次 kmalloc）。分發之後還需要調用kfree_skb釋放掉原始skb數據塊，它的歷史使命到此完成了，沒有保留的必要第622行）。注意，這兩個動作都是存在內核開銷的。
然而這裡為啥要pt_prev維護一個後向節點呢？這是有深意的，它的作用就是將當前匹配協議項的回調操作延時了。舉個例子，如果鏈表遍歷中找到某個匹配項，當前循環僅僅用pt_prev去記錄這個匹配項，除此之外不做任何事情，待到下一次匹配項找到時，才去做上一個匹配項pt_prev的回調操作，直到循環結束，才會去做最後的匹配項的回調當然pt_prev==NULL表示沒有一次匹配，直接釋放掉），所以這是一種拖延戰術。有什麼好處呢？就是比原先節省了很多不必要的操作。那麼哪些操作是不必要的呢？這裡我們逆向思考一下，我們看到clone是在協議字段匹配並且 pt_prev!=NULL的前提條件下執行的，而kfree是在pt_prev==NULL的前提條件下執行的。在此可以假設一下，如果ptype鏈表中存在N項協議與之匹配，那麼這段代碼只會執行N-1次clone，而沒有pt_prev時將會執行N次clone和1次kfree，再如果ptype鏈表中有且僅有一項協議與之匹配，那麼整個循環既不會執行到第601行的clone，也不會執行到第622行的kfree。
也就是說，當整個鏈表至少有一項匹配的一般情況下，pt_prev存在比沒有時減少了一次clone和一次kfree的開銷；只有全部不匹配的最差情況下，兩者都只做一次kfree動作，持平。這就是延遲策略產生的效益。
熟悉TCP/IP協議族的開發人員應該知道MTU最大傳輸單元）這個概念，遵循不同協議的MTU值是不同的。比如以太網幀MTU是1500個字節，802.3幀MTU是1492字節，PPP鏈路幀MTU是269字節，而超通道MTU理論上是65535字節。要知道在一個高速吞吐量通信網絡環境下，在大塊數據分片傳輸線路裡，在內核級別代碼中，減少一處系統開銷意味著什麼？
其實我們完全可以拋開一切網絡協議相關知識，這不過是一段極其普通的單向鏈表操作而已，邏輯並不復雜。但是看看人家頂級黑客是怎麼思考和 coding的，對比一下自己寫過的代碼，多少次數據處理是用一個簡單的for循環匆匆敷衍了事而沒有進一步思考其中的粗陋和不合理之處？面對真正的編程高手這種“心計”與“城府”，你是不是有種莫名不安感？你會懷疑你真的了解怎麼去使用和操作C語言中基本的鏈表數據結構麼？如果答案是肯定的，那就開始顫抖吧哈，別誤會，其實上面這段話不過是筆者的自我告解罷了）~~~
最後，讓我們感謝尊敬的Alan Cox大大對Linux社區卓越精細、無與倫比的貢獻！Alan是圖中中部戴紅帽子的那位）
附注：
最新的Linux-2.6.x版本中協議棧實現部分變動很大，但/net/core/dev.c的netif_receive_skb函數裡仍然保留了pt_prev這種用法，目的是一樣的，都是為了減少一次系統開銷的優化操作。
關於Alan，他在斯旺西大學工作時，在學校服務器上安裝了一個早期的linux版本，供學校使用。他修正了許多的問題，重寫了網絡系統中的許多部份。隨後成為linux內核開發小組中的重要成員。Alan Cox負責維持2.2版，在2.4版上擁有自己的分支在版本號上會冠上ac，如 2.4.13-ac1）。他的分支版本非常穩定，修正許多錯誤，許多廠商都使用他的版本。在他去進修工商管理碩士之前，涉入許多linux內核開發的事務，在社群中有很高的地位，有時會被視為是Linus之下的第二號領導者。
不過，今年1月28日的時候，Alan因為家庭原因宣布退出Linux項目了，下面是他Google+的聲明：
“I’m leaving the Linux world and Intel for a bit for family reasons, I’m aware that ‘family reasons’ is usually management speak for ‘I think the boss is an asshole’ but I’d like to assure everyone that while I frequently think Linus is an asshole (and therefore very good as kernel dictator) I am departing quite genuinely for family reasons and not because I’ve fallen out with Linus or Intel or anyone else. Far from it I’ve had great fun working there.”
原文鏈接：http://coolshell.cn/articles/9859.html
