之前發(fā)過一篇二級指針操作單向鏈表的例子，顯示了C語言指針的靈活性，這次再探討一個指針操作鏈表的例子，而且是一種完全不同的用法。

這個例子是linux-1.2.13網(wǎng)絡(luò)協(xié)議棧里的，關(guān)于鏈表遍歷&數(shù)據(jù)拷貝的一處實現(xiàn)。源文件是/net/inet/dev.c，你可以從kernel.org官網(wǎng)上下載。

從最早的0.96c版本開始，linux網(wǎng)絡(luò)部分一直采取TCP/IP協(xié)議族實現(xiàn)，這是最為廣泛應(yīng)用的網(wǎng)絡(luò)協(xié)議，整個架構(gòu)就是經(jīng)典的OSI七層模型的描述，其中dev.c是屬于鏈路層實現(xiàn)。從功能上看，其位于網(wǎng)絡(luò)設(shè)備驅(qū)動程序和網(wǎng)絡(luò)層協(xié)議實現(xiàn)模塊之間，作為二者之間的數(shù)據(jù)包傳輸通道，一種接口模塊而存在——對驅(qū)動層的接口函數(shù)netif_rx, 以及對網(wǎng)絡(luò)層的接口函數(shù)net_bh。前者提供給驅(qū)動模塊的中斷例程調(diào)用，用于鏈路數(shù)據(jù)幀的封裝；后者作為驅(qū)動中斷例程底半部(buttom half)，用于對數(shù)據(jù)幀的解析處理并向上層傳送。

為了便于理解，這里補充一下網(wǎng)絡(luò)通信原理和linux驅(qū)動中斷機制的背景知識。從***層的物理層說起，當(dāng)主機和路由器相互之間進(jìn)行通信的時候，在物理介質(zhì)上（同軸、光纖等）以電平信號進(jìn)行傳輸。主機或路由器的硬件接口（網(wǎng)卡）負(fù)責(zé)收發(fā)這些信號，當(dāng)信號發(fā)送到接口，再由內(nèi)置的調(diào)制解調(diào)器(modem)將數(shù)字信號轉(zhuǎn)換成二進(jìn)制碼，這樣才能駐留在主機的硬件緩存中。這時接口（網(wǎng)卡）設(shè)備驅(qū)動程序?qū)⑼ㄟ^硬中斷來獲取硬件緩存中的數(shù)據(jù)，驅(qū)動程序是操作系統(tǒng)中負(fù)責(zé)直接同硬件設(shè)備打交道的模塊，硬中斷的觸發(fā)是初始化時通過設(shè)置控制寄存器實現(xiàn)的，用于通知驅(qū)動程序硬件緩存中有新的數(shù)據(jù)到來。linux卡設(shè)備驅(qū)動就是在中斷處理例程(ISR)中將硬件緩存數(shù)據(jù)拷貝到內(nèi)核緩存中，打包成數(shù)據(jù)鏈路幀進(jìn)行解析處理，再向上分發(fā)到各種協(xié)議層。由于ISR上下文是原子性的、中斷屏蔽的，整個步驟又較為繁瑣，因此全部放在ISR中處理會影響到其它中斷響應(yīng)實時性，于是linux有實現(xiàn)一種bottom half的軟中斷處理機制，將整個ISR一分為二，前半部上下文屏蔽所有中斷，專門處理緊急的、實時性強的事務(wù)，如拷貝硬件緩存并打包封裝，后半部上下文沒有屏蔽中斷（但代碼不可重入），用于處理比較耗時且非緊急事務(wù)，包括數(shù)據(jù)幀的解析處理和分發(fā)。下面要講的net_bh就屬于后半部。

我們主要關(guān)心的是將鏈路幀分發(fā)到協(xié)議層那一段邏輯，下面摘自net_bh函數(shù)中的一段代碼：

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 } 

在此稍稍解說一下數(shù)據(jù)結(jié)構(gòu)，skb就是內(nèi)核緩存中sock數(shù)據(jù)封裝，協(xié)議棧里從鏈路層到傳輸層都會用到，只不過封裝格式不同，主要是對協(xié)議首部(header)的由下而上層層剝離（反之由上而下是層層創(chuàng)建），在此你只需理解為一個鏈路數(shù)據(jù)幀即可。這段代碼的邏輯是解析skb中的協(xié)議字段，從協(xié)議類型鏈表（由 ptype_base維護(hù)）中查詢對應(yīng)的協(xié)議節(jié)點進(jìn)行函數(shù)指針func回調(diào)，以便將數(shù)據(jù)幀分發(fā)到相應(yīng)的協(xié)議層（如ARP、IP、8022、8023等）。

***眼看上去是不是有點奇怪？這段代碼竟然用一個pt_prev指針去維護(hù)ptype鏈表中前一個節(jié)點，從而產(chǎn)生了額外的條件分支判斷，咋一看是否多了很多“余”了？回顧一下那篇二級指針操作單向鏈表的博文，簡直完全是反其道而行之的。如果把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); 

咋看一下“干凈”了很多，不是嗎？但我們要記住一點，凡是網(wǎng)上發(fā)布的linux內(nèi)核源代碼，都是都是經(jīng)過眾多黑客高手們重重檢視并驗證過的，人家這么寫肯定有十分充足的理由，所以不要太過于相信自己的直覺了，讓我們再好好review一下代碼吧！看看這段循環(huán)里做了什么事情？特別是第592~611 行。

由于從網(wǎng)絡(luò)上拷貝過來skb是唯一的，而分發(fā)的協(xié)議對象可能是多個，所以在回調(diào)之前要做一次clone動作（注意這里是深度拷貝，相當(dāng)于一次 kmalloc）。分發(fā)之后還需要調(diào)用kfree_skb釋放掉原始skb數(shù)據(jù)塊，它的歷史使命到此完成了，沒有保留的必要（第622行）。注意，這兩個動作都是存在內(nèi)核開銷的。

然而這里為啥要pt_prev維護(hù)一個后向節(jié)點呢？這是有深意的，它的作用就是將當(dāng)前匹配協(xié)議項的回調(diào)操作延時了。舉個例子，如果鏈表遍歷中找到某個匹配項，當(dāng)前循環(huán)僅僅用pt_prev去記錄這個匹配項，除此之外不做任何事情，待到下一次匹配項找到時，才去做上一個匹配項pt_prev的回調(diào)操作，直到循環(huán)結(jié)束，才會去做***的匹配項的回調(diào)（當(dāng)然pt_prev==NULL表示沒有一次匹配，直接釋放掉），所以這是一種拖延戰(zhàn)術(shù)。有什么好處呢？就是比原先節(jié)省了很多不必要的操作。那么哪些操作是不必要的呢？這里我們逆向思考一下，我們看到clone是在協(xié)議字段匹配并且 pt_prev!=NULL的前提條件下執(zhí)行的，而kfree是在pt_prev==NULL的前提條件下執(zhí)行的。在此可以假設(shè)一下，如果ptype鏈表中存在N項協(xié)議與之匹配，那么這段代碼只會執(zhí)行N-1次clone，而沒有pt_prev時將會執(zhí)行N次clone和1次kfree，再如果ptype鏈表中有且僅有一項協(xié)議與之匹配，那么整個循環(huán)既不會執(zhí)行到第601行的clone，也不會執(zhí)行到第622行的kfree。

也就是說，當(dāng)整個鏈表至少有一項匹配的一般情況下，pt_prev存在比沒有時減少了一次clone和一次kfree的開銷；只有全部不匹配的最差情況下，兩者都只做一次kfree動作，持平。這就是延遲策略產(chǎn)生的效益。

熟悉TCP/IP協(xié)議族的開發(fā)人員應(yīng)該知道MTU（***傳輸單元）這個概念，遵循不同協(xié)議的MTU值是不同的。比如以太網(wǎng)幀MTU是1500個字節(jié)，802.3幀MTU是1492字節(jié)，PPP鏈路幀MTU是269字節(jié)，而超通道MTU理論上是65535字節(jié)。要知道在一個高速吞吐量通信網(wǎng)絡(luò)環(huán)境下，在大塊數(shù)據(jù)分片傳輸線路里，在內(nèi)核級別代碼中，減少一處系統(tǒng)開銷意味著什么？

其實我們完全可以拋開一切網(wǎng)絡(luò)協(xié)議相關(guān)知識，這不過是一段極其普通的單向鏈表操作而已，邏輯并不復(fù)雜。但是看看人家***黑客是怎么思考和 coding的，對比一下自己寫過的代碼，多少次數(shù)據(jù)處理是用一個簡單的for循環(huán)匆匆敷衍了事而沒有進(jìn)一步思考其中的粗陋和不合理之處？面對真正的編程高手這種“心計”與“城府”，你是不是有種莫名不安感？你會懷疑你真的了解怎么去使用和操作C語言中基本的鏈表數(shù)據(jù)結(jié)構(gòu)么？如果答案是肯定的，那就開始顫抖吧（哈，別誤會，其實上面這段話不過是筆者的自我告解罷了）~~~

***，讓我們感謝尊敬的Alan Cox大大對Linux社區(qū)卓越精細(xì)、***的貢獻(xiàn)?。ˋlan是圖中中部戴紅帽子的那位）

[[76314]]

附注：

***的Linux-2.6.x版本中協(xié)議棧實現(xiàn)部分變動很大，但/net/core/dev.c的netif_receive_skb函數(shù)里仍然保留了pt_prev這種用法，目的是一樣的，都是為了減少一次系統(tǒng)開銷的優(yōu)化操作。

關(guān)于Alan，他在斯旺西大學(xué)工作時，在學(xué)校服務(wù)器上安裝了一個早期的linux版本，供學(xué)校使用。他修正了許多的問題，重寫了網(wǎng)絡(luò)系統(tǒng)中的許多部份。隨后成為linux內(nèi)核開發(fā)小組中的重要成員。Alan Cox負(fù)責(zé)維持2.2版，在2.4版上擁有自己的分支（在版本號上會冠上ac，如 2.4.13-ac1）。他的分支版本非常穩(wěn)定，修正許多錯誤，許多廠商都使用他的版本。在他去進(jìn)修工商管理碩士之前，涉入許多l(xiāng)inux內(nèi)核開發(fā)的事務(wù)，在社群中有很高的地位，有時會被視為是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