Alan Cox:单向链表中prev指针的妙用

Alan Cox:单向链表中prev指针的妙用

Alan Cox
Alan Cox

(感谢网友 @我的上铺叫路遥 投稿)

之前发过一篇二级指针操作单向链表的例子,显示了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 Kernel Team

附注:

最新的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.”

(全文完)

(转载本站文章请注明作者和出处 酷 壳 – CoolShell ,请勿用于任何商业用途)

好烂啊有点差凑合看看还不错很精彩 (36 人打了分,平均分: 4.11 )
Loading...

Alan Cox:单向链表中prev指针的妙用》的相关评论

  1. 顺便说一下那张题图是耗子弄的,我觉得还是用一张戴帽子的比较好……

    附录Alan的google+也是耗子搜到的,Cox大叔出于家庭原因暂时性地离开了Linux(也离开了Intel)。八卦一下,Alan和Linus对Linux开发理念不合,他说Linus是一个good developer但也是一个terible engineer,原因Linus是个完美主义者,总是重视代码可维护性方面(maintainable code),而Alan着重代码稳定性(stability)。每次遇上设计问题时,Linus总是倾向于re-write it to a better design,而Alan认为应该do small horrible fixes,而且他对Linus每次修改内核安全性方面的bug却又不让别人知道的做法很不以为然。在一次忍受不了Linus邮件里对其斥责,Cox随后离开了Linux项目投奔了Intel。

    http://apolyton.net/showthread.php/130212-Linus-Torvalds-is-a-terrible-engineer-Alan-Cox

  2. 理解应该是把原始的那个skb也利用起来了,在存在回调func的情况下,避免了一次深拷贝(kmalloc + clone)和释放(kfree)

  3. 通俗讲就是最后那次匹配可以直接用原始skb而不用clone, 所谓拖延也就是想分辨出哪个是最后一次然后偷个懒.

  4. 看到这个想起我在写链表时,也常注意由于循环判断引起的开销问题,使用过类似的code。

  5. 有人问我622行的kfree对应的kmalloc在哪里?这里有必要说得详细一点,你需要搞清楚skb的来龙去脉。最初是从硬件接口(网卡)缓存中拷贝到内核缓存,这才是最初的kmalloc,是在ISR前半部中执行的,并且插入到backlog的链表尾部。直到后半部net_bh中取backlog头部skb做解析处理,如果匹配协议项,那么上传之后由协议项去处理并释放,如果不匹配,就当即在链路层释放掉,这就是622行kfree的由来。

  6. 细节真的很重要
    顺道想起一句Steve Yegge的关于google招聘的一句话“除非你和那些胡子长的令甘道夫都自惭形秽的牛人一样,否则还是好好准备面试吧”

  7. 我的理解是,首先是這個func()會free掉第一個參數,所以為什麽只有最后一次匹配才可以用skb直接作為第一個參數,然後就是有3種情況
    1,一個都不匹配,就會只執行
    else
    kfree_skb(skb, FREE_WRITE);
    2,只有一個匹配,只執行一次回調,沒有sb_clone
    if(pt_prev)
    pt_prev->func(skb, skb->dev, pt_prev);
    3,有N(N>=2)次匹配,則會走sb_clone N-1次,再走一次最後的直接使用skb的那兒。

  8. 要是598行再用for从当前位置开始循环,循环体就短了吧。
    外层的for只负责找一个,其他的内层处理。只是代码会显得重复。

  9. 是不是可以这么理解:
    通常的情况是在循环里分配资源,然后处理。
    但这里的情况是循环之前已经有一个资源了,而且循环空转的话最后得释放这个资源。

    要是多个资源的话,一个pt_prev应该不够用,不过那似乎就成了缓存了。

  10. 和上一篇类似吧,重点依然不是指针。主要是处理好循环开始就存在的资源。

  11. 这个技巧跟cow有点异曲同工,不过还是非常赞。

    alan cox 是个大牛,看看网络部分,基本上都有他的名字

  12. Pingback: Chicago Bulls
  13. 每次循序都要对原始数据进行拷贝后使用,使用prev指针可以把原始的数据也利用上,从而减少一次深拷贝和内存释放。

  14. 原始代码在至少有一次匹配的情况下不会去执行 kfree_skb(skb, FREE_WRITE);
    按照这个逻辑精简的代码还是有问题的,精简的代码无论在什么情况下都会去执行kfree_skb(skb, FREE_WRITE);

  15. linux-3.1.7/net/core/dev.c中的static void dev_queue_xmit_nit(struct sk_buff *skb, struct net_device *dev)函数好像和这段代码类似

  16. 就是如果整个链表上只有一项匹配了, 那么没必要创建额外的副本, 直接把原始的那个skb派发出去就行了. 怎么感觉大家说的那么复杂, 我去.

  17. 这段代码比较老了,我看2.6以后的代码已经没有clone的操作,具体都交给协议栈自己处理了。从现在的代码分析这样做的目的应该是少了一次引用计数的增加的操作。

  18. 就是为了减少一次copy,代价当然是增加了代码的复杂性还有多了那些判断分支什么的。
    这都是看权衡了,这一切都是有得有失的,看你看重哪方面。

  19. 内核代码绝对是深度思考后的精华,当然越牛的人思考出的作品的确会更加精致!

    这里把skb重拾起来利用的确很妙,但是这种用法需要保证skb不是一个“const”的东西。

  20. 貌似是当只有一个匹配元素时,就不需要clone 了, 直接用skb ,从这样的需求来理解,写出这样的代码貌似也正常,还有一点是, 无论匹配的有几个元素, 最后一个总会用skb,不需要clone N 次, 不过这样的需求改为二级指针的的方法应该也能实现, skb 先赋给第一个匹配的元素, 后面的链表用用二级指针遍历……

  21. 个人觉得作者是不想浪费掉skb这个缓冲区,所以这样做。是呀,明明有一个现成的skb为什么不用呢。(n-1)*skb2 + skb = n*skb2

  22. 其实我想问:
    pt_prev->func(skb2, skb->dev, pt_prev); 这个函数里,为什么会把 skb2给释放掉啊?

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注