Linux下IP――分片与重组――详解

2. 原理介绍

1. 2. 为一个数据包片再次分片

    为数据包分片和为数据包片再次分片之间的细微差别就在于网关处理MF比特的不同。但一个网关为原来为分片的数据包分片时，除了末尾的数据包片，它将其余所有分片上的MF比特都置为一，最后一片为0。然而，当网关为一个非末尾的数据包片再次分片时，它会把生成的所有子分片中的MF比特全部设置为1，因为所有这些子分片都不可能是整个数据包的末尾的数据包片。

    对于分片，需要拷贝IP首部和选项，以及数据。而选项的拷贝要注意：根据协议标准，某些选项只应当出现在的一个数据包片中，而其他一些则必须出现在所有的数据包中。

1. 3. 数据包重组

1. 1. 2. 数据结构

    为了使数据包的重组效率更高，用于保存数据包的数据结构必须能够做到：

• 为构成某一个特定数据包的一组数据包片快速定位；
• 在一组数据包片中快速插入新的数据包片；
• 有效地判断一个完整的数据包是否已经全部抵达；
• 具有数据包片超时机制（ip_expire），并且，如果在重组完成之前定时器溢出，则删除数据包片。

1. 1. 3. 互斥操作

    重组程序代码使用了一个互斥信号量。Ipfrag_lock

1. 1. 4. 在链表中加入一个数据包片

    查找方式：链表的线性查找

1. 1. 5. 溢出时的丢弃

    分片列表空间以全满的情况下：丢弃对应的数据包的所有分片。Ip_evictor

1. 4. 测试是否组成一个完整的数据包ip_frag_queue

    判断IP_MF位是否为0！

1. 1. 2. 将数据包片组装成完整的数据包LAST_IN，ip_frag_reasm

1. 5. 数据包片链表的维护管理

• 为了使丢失数据包片的数据包不再浪费存储资源　，并防止因为标示符字段的重新使用而给IP带来混乱，但已经不可能再受到剩余数据包片时，IP必须定期检查数据包片列表。

• Ipq_unlink

• Ipq_put

• Ipq_kill

• Ipqhashfn

3. Linux下的实现

1. 2. IP分片

如何提高分片处理的效率

1. 1. 2. ip_fragment（非UDP使用）

1. 1. 1. 2. 典型调用者

    ip_sendà ip_fragment(skb, ip_finish_output);一般从转发来

    ip_queue_xmit2à ip_fragment(skb, skb->dst->output)一般从TCP来

    因为IP报太大而将其分片以适合于一个帧的传输。

1. 1. 1. 3. 处理过程

    获取外出设备（由skb决定）

          dev = rt->u.dst.dev;    出口路由设备

    ！！！skb->dst=rt=rt->u.dstàdst_entry

    取IP包头

          raw = skb->nh.raw;

          iph = (struct iphdr*)raw;   取IP头

    设定开始值

          hlen=IP头长

          left = ntohs(iph->tot_len) - hlen; 包总长度减去IP头长度――需要分片的数据长度

          mtu = rt->u.dst.pmtu - hlen;  物理MTU减去IP头长度――除去IP头的分片长度

          ptr = raw + hlen;    取数据区指针

    将数据包分片

• 分片算法很简单，但由于对sk_buff结构和链的操作时的实现非常复杂。
• 如果DF比特禁止分片，则ip_output丢弃分组并返回错误消息。
• 如果该数据包是在本地生成的，则传输层协议把该错误传回该进程
• 如果分组是被转发的，则ip_forward生成一个ICMP目的不可达差错报文，并指出不分片就我发转发该分组。
• 路径发现机制？该算法用来搜索到目的主机的路径，并发现所有中间网络支持的最大传送单元MTU。
• 新的分片包含：IP首部、某些原始分组中的选项以及最多len的长度的数据。
• Linux下没有分片队列，分一个片就发一个分片包。

          offset = (ntohs(iph->frag_off) & IP_OFFSET) << 3;

• • • • •     取出偏移位（13位），并乘8算出总字节数――算该包的偏移字节数

          not_last_frag = iph->frag_off & htons(IP_MF);

• • • • • 取出MF位（第14位）

    循环进行分片：

          while(left > 0) {

                 len = left;

                 /* IF: it doesn't fit, use 'mtu' - the data space left */

                 if (len > mtu)    如果剩下的数据left还比MTU大，则以MTU为分片的数据长度；否则，就用left作为数据长度（对于最后一片）

                        len = mtu;   

                 /* IF: we are not sending upto and including the packet end

                    then align the next start on an eight byte boundary下一个开始出是八字节的边界对齐 */

                 if (len < left) {   当len<mtu时，即最后一个分片长度小于MTU，则不需要再取8字节的整数倍

                        len &= ~7;   取8字节的整数倍

                 }

    分配缓冲区新的分片包的sk_buff，大小：硬件帧长＋分片长＋IP头长

    填充分片

• 包类型：本机、广播、多播、其他主机、外出、回环、快速路由
• 包优先级
• 留出帧头的空间
• 指定IP和TCP的原始指针raw

                 /*

                  * Charge the memory for the fragment to any owner

                  * it might possess

                  */

• 如果该包有sock，在包的sock注册该分片的所有者。
• 拷贝目的地址，增加引用计数。
• 拷贝出口设备。
• 拷贝IP头
• 拷贝IP报块（只有分片长度MTU大小），并减小总的包长度left-len，以便下次分片。Left记录了剩余数据量。

    装填新的IP头

• 定位新分片包的IP头
• 设置分片的偏移值（对于第一个分片该值就是原IP包的偏移值）――offset记录了分片的偏移量。此时标志位为空。iph->frag_off = htons((offset >> 3));

 

    如果偏移为0――表明该包第一次被分片

                 if (offset == 0)                      

    表明该IP包是第一次分片要在第一片中填入一些不允许在其他分片中出现的选项，为了提高效率（选项一般放在分片的第一个包中。

                        ip_options_fragment(skb); 

    对于多充分片（not_last_frag=1表示该包就是一个分片包）――对分片包再次分片时，需要保持MF为1

                 if (left > 0 || not_last_frag)

                        iph->frag_off |= htons(IP_MF);          设置MF位1

    移动原IP包的数据指针ptr

    移动分片偏移指针offset

                 ptr += len;        移动IP包数据指针

                 offset += len;        移动分片指针

    如果配置了防火墙，则进行防火墙值的设置。

    发送该分片

• 计算总包长
• 为分片包重新产生校样和
• 发送分片ip_finish_output

    ｝循环直到数据分片结束（left=0）

1. 1. 3. UDP的分片（待续）

1. 3. IP重组

1. 1. 2. ip_defrag

    众所周知，网络数据报在linux的网络堆栈中是以sk_buff的结构传送的，ip_defrag()的功能就是接受分片的数据包(sk_buff)，并试图进行组合，当完整的包组合好时，将新的sk_buff返还，否则返回一个空指针。

1. 1. 1. 2. 典型调用者

    if (iph->frag_off & htons(IP_MF|IP_OFFSET))判断是否是分片

•     ip_local_deliveràip_defrag(skb)；

1. 1. 1. 3. 关键数据结构（2.4系列）

1. 1. 1. 1. 2. ipq

    这些分片形成一个双向链表（在linux内核中，若需要使用链表，除非有特殊需要，否则推荐双向链表，见document/CodingStyle）,表示一个未组装完的分片队列（属于一个ip包）。这个链表的头指针要放在ipq结构中：

    /* Describe an entry in the "incomplete datagrams" queue. */

    struct ipq {

          struct ipq *next;  /* linked list pointers   */

          u32  saddr;

          u32  daddr;

          u16  id;

          u8  protocol;

          u8  last_in;

    #define COMPLETE  4

    #define FIRST_IN  2

    #define LAST_IN   1 

          struct sk_buff *fragments; /* linked list of received fragments */

          int  len;  /* total length of original datagram */

          int  meat;  保留现有的分片长度的累加值

          spinlock_t lock;

          atomic_t refcnt;

          struct timer_list timer; /* when will this queue expire?  */

          struct ipq **pprev;

          int  iif;  /* Device index - for icmp replies */

    };

    注意每个ipq保留了一个定时器（即struct timer_list timer;）。 

    Ipq利用一个HASH表来构建分片链。

    hash表：

    #define IPQ_HASHSZ   64

    struct ipq *ipq_hash[IPQ_HASHSZ];

    #define ipqhashfn(id, saddr, daddr, prot) /标识、源地址、目的地址、协议

        ((((id) >> 1) ^ (saddr) ^ (daddr) ^ (prot)) & (IPQ_HASHSZ - 1)) 
 

    每个IP包用如下四元组表示：（id,saddr,daddr,protocol）,四个值都相同的碎片散列到一个IPQ链中，即可组装成一个完整的IP包。

1. 1. 1. 1. 3. FRAG_CB

    #define FRAG_CB(skb) ((struct ipfrag_skb_cb*)((skb)->cb))

    cb是一块控制缓冲区。它提供给每一层存放私有的数据。如果你需要将它们保持到其他层，则必须进行克隆skb_clone。

          char  cb[48]; 

1. 1. 1. 1. 4. ipfrag_skb_cb

    struct ipfrag_skb_cb

    {

          struct inet_skb_parm h;

          int   offset;

    };

1. 1. 1. 1. 5. inet_skb_parm

    struct inet_skb_parm

    {

          struct ip_options opt;  /* Compiled IP options  */

          unsigned char  flags; 

    #define IPSKB_MASQUERADED 1

    #define IPSKB_TRANSLATED 2

    #define IPSKB_FORWARDED  4

    };

1. 1. 1. 4. 函数说明

• 当内核接收到本地的IP包, 在传递给上层协议处理之前, 先进行碎片重组.IP包分片之间的标识号(id)是相同的. 当IP包片偏量(frag_off)第14位(IP_MF)为1时, 表示该IP包有后继分片. 片偏移量的低13位则为该分片在完整数据包中的偏移量, 以8字节为单位. 当IP_MF位为0时, 表示IP包是最后一块碎片.
• 如果60－120秒后（IP_FRAG_TIME常量指定。（30＊HZ））重组队列内包未到齐, 则重组过程失败, 重组队列被释放, 同时向发送方以ICMP协议通知失败信息. 重组队列的内存消耗不得大于256k(sysctl_ipfrag_high_thresh), 否则将会调用(ip_evictor)释放每支散列尾端的重组队列.
• 所有IP实现必须能给重装最多576字节的数据报。
• 可能会有分片重叠。分片重叠的处理。
• 为了防止因保留分片而造成内存消耗过大，linux设置了界限来防止这种情况，如果超过了内存使用的上限，则清空内存中最老的队列（ipq）.所用内存的大小保存在变量ip_frag_mem中，当然，对它的读写都应是“原子”操作（atomic_sub，atomic_add，atomic_read，etc）。其定义在文件ip_fragment.c前部
• 2.4的分片组装代码的流程与2.2系列基本相同，不同的是将函数的分工变化了。由于原ipfrag结构保留的结构均可在skbuff中得到，在2.4中将此结构取消了，并对ipq结构做了一些修改。其他主要变化有：

•     1）ip_defrag分成了ip_defrag和ip_frag_queue两部分。

•     2）ip_glue换名成ip_frag_reasm,流程基本未动。

• 3）现在ipq中用meat保留现有的分片长度的累加值（已经解决重叠），如果此值到达总长度，则意味着所有的分片到达，因此取消了ip_done函数，不必每次遍历一次链表，因此在效率上有了较大的提高，抗小碎片攻击的能力得到加强。 
  

    ip_findàip_frag_createàip_frag-internà IP_FRAG_TIME

1. 1. 1. 5. 流程

    struct sk_buff *ip_defrag(struct sk_buff *skb)

    {

    如果用于分片处理的内存空间大于系统规定的最大值256k，那么要进行清洗ip_evictor 

    指定IP包对应设备dev

    根据HASH值，定位该包在分片链中的位置：

• • 如果有分片链，说明已有其他分片到达，？？？如果非正常顺序到达呢？

•     将该分片插入到对应的分片队列中，

• • 根据该包的标志位与偏移量：如果是最后一个分片包（但不一定分片完全到齐），设置分片队列长度为原包的长度；如果是比当前分片靠后的包，改变分片队列的长度；如果是靠前的包。
  • 调整分片包的skb指针：使skb->data指向ip载荷（数据区），skb->tail指向ip载荷尾。即：skb->data-skb->tail＝ip载荷区。如此以便将该sk_buff加入该分片链，并在重组时很容易拼接分片。
  • 扫描重组队列中的包片段，找到分片链中该分片的前一个分片：利用偏移量找offset
  • 如果该分片不是第一个分片（prev!=null），先消除与前一分片重叠：求prev尾部与当前偏移之差，（该偏移包，不一定就是紧接着的那一个包）；再消除与后一分片的重叠，求当前偏移与next重叠之差，如果当前包尾部小于后一包尾部，后一包起点后移，后一分片交叠部分清除，减少分片统计总长度meat；如果后一分片完全包含在此分片中，清除它next，减少分片统计总长度meat。
  • 将该分片插入到分片队列中：设置设备，增加meat分片总长度，如果偏移为0则说明是第一个包，置上FIRST_IN标志。
  • 检查该分片是否是最后一个分片（分片是否都到齐了，包长度），是：进行分片重组ip_frag_reasm
  • 重组前，先删除该分片队列。
  • 为新的包分配sk_buff结构，填入相应的值：设置新的IP总长度（不能超过65535字节）；帧头位置、IP头位置、选项数据
  • 拷贝原始的IP头（分片队列的第一个分片中有记录）到新的skb结构
  • 循环拷贝：将分片链上的分片skb数据拷贝到新的skb结构中。
  • 增加校样值。
  • 设置目的地址（克隆）、包类型、协议、设备。
  • 进行防火墙处理。
  • 重新设置IP头、将3位标志和13位偏移设置为0、计算总长度。
  • 返回新的IP包。
  • 如果是第一个分片（找不到），就创建新的入口项插到分片队列头ip_frag_create

1. 1. 1. 6. ip_evictor

    当分片所用的内存超过一定的上限时(sysctl_ipfrag_high_thresh)会调用ip_evicator以释放内存。

    ip_evicator会找寻可清空的IPQ，并将其清空，直到到达到可用的下限（sysctl_ipfrag_low_thresh）。 

    这个值在ip_fragment.c中按如下定义：

    int sysctl_ipfrag_high_thresh = 256*1024;

    int sysctl_ipfrag_low_thresh = 192*1024; 

    同样，用sysctl -a可可看到这两参数，同时可以动态修改。

    ＃sysctl -a

    ......

    net.ipv4.ipfrag_low_thresh = 196608

    net.ipv4.ipfrag_high_thresh = 262144

    ......

    理论上ip_evicator应该采用LRU算法，将最古老的IPQ清除。但目前linux(包括2.4.0)没有实现此功能，只是将hash表按次序清空，这样的好处是简单易行。 

    Memory limiting on fragments.  Evictor trashes(丢弃) the oldest * fragment queue until we are back under the low threshold.

    Ip_evictor函数遍历分片队列，同时丢弃到目前为止已经收集到的分片，直到所使用的总的内存量小于规定的限制时为止。只要占用的内存大于对他的内存限制值，这个函数就调用Ip_free函数。当分片队列为空并且内存阀值也超过时，Ip_evictor函数可以引起内核的恐慌。

    LRU算法，全局变量ipq_hash[64]链表，越靠近链尾越老引用计数越大越不容易被洗掉

    两重循环每次洗掉时间最老引用计数最少的分片，直到总占用内存降到sysctl_ipfrag_low_thresh＝192＊1024

1. 1. 1. 7. ip_frag_create

    初始化一个IP分片队列，包括了定时器，处理函数为IP_expire。用ip_frag_intern建立链表头和插入时间链。

1. 1. 1. 8. ip_frag_intern

    ip_frag_nqueues++