开源世界中的算法与数据结构 2 -- Linux Skbuff实现
兼回忆贴,大概在03年开始接触Linux的协议栈代码,那个时候还找不到什么参考书,有些东西自己搞明白了但是也从来没想过在那个论坛发个帖子什么的,也没有现在的记录总结的习惯. 后来有一本08年版的《TCP/IP Architecture, Design and Implementation in Linux》其中解析了Linux2.4 协议栈的多数代码,其中第五章专门涉及skbuff的代码实现讲解,非常详细,这个小短文不翻译整个章节,各种网文很多,只是想根据关键部分说一下我理解的设计背后的原因。
- skbuff的形态1
上面是最基本的一个sk_buff了,一个TCP报文的skbuff示意图,这里隐含着一些内容:
报文分析的标准模式
skbuff采用的大块控制结构对象指向数据区是标准的实现模式,例如BSD这样的OS以及工程实现中都是这样的。
参数的集中
与其提供多个对象或者多个参数保存报文信息,不如将其集中起来存放,即便于功能扩展时保持接口稳定性,又减少了接口参数,更加容易理解和记忆。的时候仅仅是因为缩减参数长度这一简单理由,我们就搞一个XXContext的数据结构,收容各种变量,而不顾内聚耦合之类的编程标准。
skb_shared_info是个什么东东,为什么放在了数据报文的尾部?
代码中的注解是,这个部分数据是各个skbuff之间共享的。这个结构其实是控制结构,但是为什么放在数据区呢?我的理解是,因为其在多个克隆的skbuff之间共享,如果放在控制区则会造成克隆后的skbuff之中数据冗余。
- skbuff的形态2 - 带有Paged Data的skbuff
上图可见除了标准数据区的报文内容外,skb_shared_info会有多个frag部分指向离散存储的Page数据。所有Page数据和标准数据区的数据的总和是报文内容。我并未遇到过这种情况,根据【1】中的描述,在使用Scatter-gather DMA技术的时候可以利用Paged Data。http://bbs.ednchina.com/BLOG_ARTICLE_73287.HTM之中描述了Scatter-gather DMA技术。因为“连续的存储器地址在物理上不一定是连续的,所以DMA传输要分成多次完成。”,采用Scatter-gather技术的优点是,通过DMA传送多块离散数据之后产生一次中断,这样减少了中断次数。
上述数据结构设计就是我所说的因为系统对于数据结构的影响而引入的对于数据结构的修改,课堂不会遇到。
- skbuff的形态3 - IP Fragment
上图是fragment的组织图,同属一分片的报文会串接到第一个分片的frag_list上面。
由此可见虽然skb_shared_info之中的frag_list和frags名字差不多,容易混淆,实际二者的功能是完全不同的。
skbuff的形态4 - 混合完全版
上图是【1】之中的图5.5,skbuff之中既包括了fragment也有paged data。
下面是Linux2.4之中的sk_buff的定义,供参考。
struct sk_buff {
/* These two members must be first. */
struct sk_buff * next; /* Next buffer in list */
struct sk_buff * prev; /* Previous buffer in list */
struct sk_buff_head * list; /* List we are on */ 用于回指,便于引用next和prev所在的list。
struct sock *sk; /* Socket we are owned by */
struct timeval stamp; /* Time we arrived */
struct net_device *dev; /* Device we arrived on/are leaving by */
struct net_device *real_dev; /* For support of point to point protocols
(e.g. 802.3ad) over bonding, we must save the
physical device that got the packet before
replacing skb->dev with the virtual device. */
/* Transport layer header */ 指向四层头
union
{
struct tcphdr *th;
struct udphdr *uh;
struct icmphdr *icmph;
struct igmphdr *igmph;
struct iphdr *ipiph;
struct spxhdr *spxh;
unsigned char *raw;
} h;
/* Network layer header */ 指向三层头
union
{
struct iphdr *iph;
struct ipv6hdr *ipv6h;
struct arphdr *arph;
struct ipxhdr *ipxh;
unsigned char *raw;
} nh;
/* Link layer header */ 指向二层头
union
{
struct ethhdr *ethernet;
unsigned char *raw;
} mac;
struct dst_entry *dst;
/*
* This is the control buffer. It is free to use for every
* layer. Please put your private variables there. If you
* want to keep them across layers you have to do a skb_clone()
* first. This is owned by whoever has the skb queued ATM.
*/
char cb[48]; 这一段保存中间信息,例如IP处理的时候一些Option内容保存在这里
unsigned int len; /* Length of actual data */ SKB上挂接的网络报文的整体长度
unsigned int data_len; 第一片之外的分片报文的数据长度
unsigned int csum; /* Checksum */
unsigned char __unused, /* Dead field, may be reused */
cloned, /* head may be cloned (check refcnt to be sure). */ SKB是克隆还是原始的
pkt_type, /* Packet class */
ip_summed; /* Driver fed us an IP checksum */
__u32 priority; /* Packet queueing priority */
atomic_t users; /* User count - see datagram.c,tcp.c */
unsigned short protocol; /* Packet protocol from driver. */
unsigned short security; /* Security level of packet */
unsigned int truesize; /* Buffer size */ 包含skb控制块+数据块的整体内存大小
unsigned char *head; /* Head of buffer */
unsigned char *data; /* Data head pointer */ 报文解析到哪里,这个指针移动到哪里
unsigned char *tail; /* Tail pointer */
unsigned char *end; /* End pointer */
void (*destructor)(struct sk_buff *); /* Destruct function */
#ifdef CONFIG_NETFILTER
/* Can be used for communication between hooks. */
unsigned long nfmark;
/* Cache info */
__u32 nfcache;
/* Associated connection, if any */
struct nf_ct_info *nfct;
#ifdef CONFIG_NETFILTER_DEBUG
unsigned int nf_debug;
#endif
#endif /*CONFIG_NETFILTER*/
#if defined(CONFIG_HIPPI)
union{
__u32 ifield;
} private;
#endif
#ifdef CONFIG_NET_SCHED
__u32 tc_index; /* traffic control index */
#endif
};
References:
【1】.《TCP/IP Architecture, Design and Implementation in Linux》- charpter 5 - “sk_buff AND PROTOCOL HEADERS”
建议继续学习:
- 浅谈MySQL索引背后的数据结构及算法 (阅读:9886)
- 爱喝啤酒的程序员是如何学习数据结构的 (阅读:5070)
- 分布式系统的数据结构 (阅读:4956)
- stream.js :一个新的JavaScript数据结构 (阅读:4083)
- 开源世界中的算法与数据结构 3 -- Linux Kernel List 和GList (阅读:2901)
- 数据结构之treap (阅读:2688)
- 开源世界中的算法与数据结构 1 -- Linux FIB实现 (阅读:2384)
- 开源世界中的算法与数据结构 3 -- Linux IPv6 FIB表实现 (阅读:2327)
- 深入剖析 redis 数据结构 skiplist (阅读:2262)
- 深入剖析 redis 数据结构 ziplist (阅读:1591)
扫一扫订阅我的微信号:IT技术博客大学习
- 作者:appleleaf 来源: kernelchina blogs
- 标签: Skbuff 数据结构
- 发布时间:2012-02-05 23:17:33
- [54] IOS安全–浅谈关于IOS加固的几种方法
- [52] android 开发入门
- [52] 如何拿下简短的域名
- [51] 图书馆的世界纪录
- [49] Go Reflect 性能
- [49] Oracle MTS模式下 进程地址与会话信
- [47] 【社会化设计】自我(self)部分――欢迎区
- [46] 读书笔记-壹百度:百度十年千倍的29条法则
- [36] 程序员技术练级攻略
- [29] 视觉调整-设计师 vs. 逻辑