ip分片与linux实现(整理自网络)

IP报文格式：

    与分片有关的是'标志'字段，标志字段占3bit。目前只有前两个比特有意义。

       |R|DF|MF| 

       R：保留未用。　　

       DF：Don't Fragment，“不分片”位，如果将这一比特置1 ，IP层将不对数据报进行分片。　　

       MF：More Fragment，“更多的片”，除了最后一片外，其他每个组成数据报的片都要把该比特置1。

IP分片原因：

     链路层具有最大传输单元MTU这个特性，它限制了数据帧的最大长度，不同的网络类型都有一个上限值。以太网的MTU是1500，如果IP层有数据包要传，而且数据包的长度超过了MTU，那么IP层就要对数据包进行分片（fragmentation）操作，使每一片的长度都小于或等于MTU。什么情况，或者说什么协议会尝试发送这么长的数据？常见的有UDP和ICMP，需要特别注意的是，TCP一般不会。为什么TCP不会造成IP分片呢？原因是TCP自身支持分段：当TCP要传输长度超过MSS（Maxitum Segment Size）的数据时，会先对数据进行分段，正常情况下，MSS小于MTU，因此，TCP一般不会造成IP分片。

     而UDP和ICMP就不支持这种分段功能了，UDP和ICMP认为网络层可以传输无限长（实际上有65535的限制）的数据，当这两种协议发送数据时，它们不考虑数据长度，仅在其头部添加UDP或ICMP首部，然后直接交给网络层。接着网络层IP协议对这种“身长头短”的数据进行分片，不要指望IP能很“智能”地识别传给它的数据上层头部在哪里，载荷又在哪里，它会直接将整个的数据切成N个分片，这样做的结果是，只有第一个分片具有UDP或者ICMP首部，而其它分片则没有。

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

  分片可以发生在原始发送端主机上，也可以发生在中间路由器上。

  已经分片过的数据报有可能会再次进行分片（可能不止一次）。

  片偏移字段指的是该片偏移原始数据报开始处的位置

  当数据报被分片后，每个片的总长度值要改为该片的长度值。

  在分片时，除最后一片外，其他每一片中的数据部分（除IP首部外的其余部分）必须是8字节的整数倍。

  另外需要解释几个术语： IP数据报是指IP层端到端的传输单元（在分片之前和重新组装之后），分组是指在IP   层和链路层之间传送的数据单元。一个分组可以是一个完整的IP数据报，也可以是IP数据报的一个分片。

linux 内核中的ip碎片重组过程:

   Linux内核的防火墙netfilter就自动对IP碎片包进行了重组，通过查看相关部分的内核源代码，可对IP重组过程有一个详细的了解。

(1) 当内核接收到本地的IP包, 在传递给上层协议处理之前,先进行碎片重组。IP包片段之间的标识号(id)是相同的.当IP包片偏量(frag_off)第14位(IP_MF)为1时, 表示该IP包有后继片段。片偏量的低13位则为该片段在完整数据包中的偏移量, 以8字节为单位.。当IP_MF位为0时,表示IP包是最后一块碎片。

(2) 碎片重组由重组队列完成, 每一重组队列对应于(daddr,saddr,protocol,id)构成的键值,它们存在于ipq结构构成的散列链之中. 重组队列将IP包按照将片段偏移量的顺序进行排列,当所有的片段都到齐后, 就可以将队列中的包碎片按顺序拼合成一个完整的IP包.

(3) 如果30秒后重组队列内包未到齐, 则重组过程失败, 重组队列被释放,同时向发送方以ICMP协议通知失败信息.重组队列的内存消耗不得大于256k(sysctl_ipfrag_high_thresh),否则将会调用(ip_evictor)释放每支散列尾端的重组队列。

linux内核中与分片相关的数据结构： 

skb就不介绍了。

结构体ipq链表代表一个分片的信息。

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

struct ipq {

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

 struct list_head lru_list; /* lru list member */

 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;

 struct timeval stamp;

};

系统定义了一个大小为IPQ_HASHSZ=64的ipq_hash表，

static struct ipq *ipq_hash[IPQ_HASHSZ];

每个数组元素就是一个具有相同hash值的链表。每个链表上的节点就代表着同一个链接的IP的碎片， 将这些碎片重新组合即为IP碎片重组。每个IP包用如下四元组表示：（id,saddr,daddr,protocol）,四个值都相同的碎片散列到一个ipq链中，即可组装成一个完整的IP包,hash值的计算方法：

#define ipqhashfn(id, saddr, daddr, prot)      ((((id) >> 1) ^ (saddr) ^ (daddr) ^ (prot)) & (IPQ_HASHSZ - 1)) 

下图即为该结构的示意图：

在内核中实现IP碎片重组的几个关键函数有：

ip_defrag()   net/ipv4/ip_fragment.c

基本过程是建立碎片处理队列，队列中每个节点（struct ipq）是一个链表，这个链表保存同一个连接的碎片，当碎片都到达之后进行数据包重组，或者在一定时间(缺省30秒)内所有碎片包不能到达而释放掉。该函数接受分片的数据包(sk_buff)，并试图进行组合，当完整的包组合好时，将新的sk_buff返还，否则返回一个空指针。

ip_frag_queue()

把新到达的分片加入到属于同一链接的节点中。

ip_frag_reasm()函数

把属于同一个链接中的所有分片组成一个新的IP数据包。

ipq_put()函数

释放节点里的所有分片，然后释放自身节点。

ip_find()函数

在hash表中查找属于同一链接的节点，如果没有找到，则新建一个节点。

ip_frage_mem()

存储分片的内存，其初始化

相关代码及注释：

系统定义了一个大小为IPQ_HASHSZ=64的ipq_hash表，static struct ipq *ipq_hash[IPQ_HASHSZ];每个数组元素就是一个具有相同hash值的链表。每个链表上的节点就代表着同一个链接的IP的碎片。

ip_frage_mem 

存储分片的内存，其初始化

什么情况，或者说什么协议会尝试发送这么长的数据？常见的有UDP和ICMP，需要特别注意的是，TCP一般不会。

为什么TCP不会造成IP分片呢？原因是TCP自身支持分段：当TCP要传输长度超过MSS（Maxitum Segment Size）的数据时，会先对数据进行分段，正常情况下，MSS小于MTU，因此，TCP一般不会造成IP分片。

而UDP和ICMP就不支持这种分段功能了，UDP和ICMP认为网络层可以传输无限长（实际上有65535的限制）的数据，当这两种协议发送数据时，它们不考虑数据长度，仅在其头部添加UDP或ICMP首部，然后直接交给网络层就万事大吉了。接着网络层IP协议对这种“身长头短”的数据进行分片，不要指望IP能很“智能”地识别传给它的数据上层头部在哪里，载荷又在哪里，它会直接将整个的数据切成N个分片，这样做的结果是，只有第一个分片具有UDP或者ICMP首部，而其它分片则没有。

相关代码实现：

//处理一个传过来的IP数据报

struct sk_buff *ip_defrag(struct sk_buff *skb)

{

struct iphdr *iph = skb->nh.iph;

struct ipq *qp;

struct net_device *dev; 

IP_INC_STATS_BH(IpReasmReqds);

/* Start by cleaning up the memory. */

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

if (atomic_read(&ip_frag_mem) > sysctl_ipfrag_high_thresh)

ip_evictor();

        //指定IP包对应设备dev

dev = skb->dev;

/* Lookup (or create) queue header */

if ((qp = ip_find(iph)) != NULL) { //根据HASH值，定位该包在分片链中的位置：

struct sk_buff *ret = NULL;

spin_lock(&qp->lock);

         //将该分片插入到分片队列中：设置设备，增加meat分片总长度，如果偏移为0则说明是第一个包，置上            FIRST_IN标志。

ip_frag_queue(qp, skb);

         //检查该分片是否是最后一个分片（分片是否都到齐了，包长度）如果是则进行分片重组调用                    ip_frag_reasm函数

if (qp->last_in == (FIRST_IN|LAST_IN) && //首包与尾包已收到

   qp->meat == qp->len) //队列中字节数恰好等于队列尾部

    ret = ip_frag_reasm(qp, dev); //重组碎片

          spin_unlock(&qp->lock);

ipq_put(qp);

return ret;

}

IP_INC_STATS_BH(IpReasmFails);

kfree_skb(skb);

return NULL;

}

// 碎片的重组过程

static struct sk_buff *ip_frag_reasm(struct ipq *qp, struct net_device *dev)

{

struct sk_buff *skb;

struct iphdr *iph;

struct sk_buff *fp, *head = qp->fragments;

int len;

int ihlen;

ipq_kill(qp); //重组前，先删除该分片队列。

BUG_TRAP(head != NULL);

BUG_TRAP(FRAG_CB(head)->offset == 0);

        

ihlen = head->nh.iph->ihl*4; //取队列头IP包头长度

len = ihlen + qp->len; //总长度

if(len > 65535)

goto out_oversize;

        //为新的包分配sk_buff结构，填入相应的值：设置新的IP总长度（不能超过65535字节）；帧头位置、IP头位置、选项数据

skb = dev_alloc_skb(len);

if (!skb)

goto out_nomem;

/* Fill in the basic details. */

skb->mac.raw = skb->data;

skb->nh.raw = skb->data;

FRAG_CB(skb)->h = FRAG_CB(head)->h; //复制IP选项信息

skb->ip_summed = head->ip_summed;

skb->csum = 0;

        //拷贝原始的IP头（分片队列的第一个分片中有记录）到新的skb结构

memcpy(skb_put(skb, ihlen), head->nh.iph, ihlen);

//循环拷贝：将分片链上的分片skb数据拷贝到新的skb结构中。

for (fp=head; fp; fp = fp->next) {

memcpy(skb_put(skb, fp->len), fp->data, fp->len);

        //增加校样值

if (skb->ip_summed != fp->ip_summed)

            skb->ip_summed = CHECKSUM_NONE;

else if (skb->ip_summed == CHECKSUM_HW)

skb->csum = csum_add(skb->csum, fp->csum);

}

        //设置目的地址（克隆）、包类型、协议、设备。

skb->dst = dst_clone(head->dst);

skb->pkt_type = head->pkt_type;

skb->protocol = head->protocol;

skb->dev = dev;

/*

*  Clearly bogus, because security markings of the individual

*  fragments should have been checked for consistency before

*  gluing, and intermediate coalescing of fragments may have

*  taken place in ip_defrag() before ip_glue() ever got called.

*  If we're not going to do the consistency checking, we might

*  as well take the value associated with the first fragment.

* --rct

*/

skb->security = head->security;

      //进行防火墙处理

#ifdef CONFIG_NETFILTER

/* Connection association is same as fragment (if any). */

skb->nfct = head->nfct;

nf_conntrack_get(skb->nfct);

#ifdef CONFIG_NETFILTER_DEBUG

skb->nf_debug = head->nf_debug;

#endif

#endif

/* Done with all fragments. Fixup the new IP header. */

        //重新设置IP头、将3位标志和13位偏移设置为0、计算总长度。

iph = skb->nh.iph;

iph->frag_off = 0;

iph->tot_len = htons(len);

IP_INC_STATS_BH(IpReasmOKs);

return skb;

out_nomem:

  NETDEBUG(printk(KERN_ERR 

"IP: queue_glue: no memory for gluing queue %p\n",

qp));

goto out_fail;

out_oversize:

if (net_ratelimit())

printk(KERN_INFO

"Oversized IP packet from %d.%d.%d.%d.\n",

NIPQUAD(qp->saddr));

out_fail:

IP_INC_STATS_BH(IpReasmFails);

return NULL;

}

/在队列中增加新的分片处理过程. */

static void ip_frag_queue(struct ipq *qp, struct sk_buff *skb)

{

struct iphdr *iph = skb->nh.iph;

struct sk_buff *prev, *next;

int flags, offset;

int ihl, end;

if (qp->last_in & COMPLETE)

goto err;

      //根据该包的标志位与偏移量：如果是最后一个分片包（但不一定分片完全到齐），设置分片队列长度为原         包的长度；如果是比当前分片靠后的包，改变分片队列的长度；如果是靠前的包。

offset = ntohs(iph->frag_off); //取片偏移量描述字

flags = offset & ~IP_OFFSET; //取片标志

offset &= IP_OFFSET; //求片偏移量

offset <<= 3; /* offset is in 8-byte chunks */

ihl = iph->ihl * 4;

/* Determine the position of this fragment. */

end = offset + (ntohs(iph->tot_len) - ihl); //求该片段尾部的数据偏移量

/* Is this the final fragment? */

if ((flags & IP_MF) == 0) { //最后一片段

/* If we already have some bits beyond end

* or have different end, the segment is corrrupted.

*/

if (end < qp->len || //最后一个片段的未尾小于队列内最大的未尾

   ((qp->last_in & LAST_IN) && end != qp->len))

goto err;

qp->last_in |= LAST_IN;

qp->len = end; //设取队列最大未尾

} else { //是中间某个片段

if (end&7) { //如果片段尾部不在8字节上对齐

end &= ~7; 

if (skb->ip_summed != CHECKSUM_UNNECESSARY)

skb->ip_summed = CHECKSUM_NONE; 不计算校验和

}

if (end > qp->len) { ///该片段比队列内其它成员位置要大

/* Some bits beyond end -> corruption. */

if (qp->last_in & LAST_IN)

goto err;

qp->len = end;

}

}

if (end == offset) //片段的数据区长度为零

goto err;

/* Point into the IP datagram 'data' part. */

skb_pull(skb, (skb->nh.raw+ihl) - skb->data); //删除IP包的头部

skb_trim(skb, end - offset); //去队尾部可能的衬垫

/* Find out which fragments are in front and at the back of us

* in the chain of fragments so far.  We must know where to put

* this fragment, right?

*/

prev = NULL; //扫描重组队列中的包片段,取偏移大于或等于当前包偏移的前一成员作为插入位置

for(next = qp->fragments; next != NULL; next = next->next) {

if (FRAG_CB(next)->offset >= offset)

break; /* bingo! */

prev = next; 

}

//当前偏移的包

/* We found where to put this one.  Check for overlap with

* preceding fragment, and, if needed, align things so that

* any overlaps are eliminated.

*/

      //如果该分片不是第一个分片（prev!=null），先消除与前一分片重叠：求prev尾部与当前偏移之差，（该偏移包，不一定就是紧接着的那一个包）；再消除与后一分片的重叠，求当前偏移与next重叠之差，如果当前包尾部小于后一包尾部，后一包起点后移，后一分片交叠部分清除，减少分片统计总长度meat；如果后一分片完全包含在此分片中，清除它next，减少分片统计总长度meat。

if (prev) {

int i = (FRAG_CB(prev)->offset + prev->len) - offset; //求prev尾部与当前偏移之差

if (i > 0) { //插入点成员尾部大于当前包开始, 说明当前包与前一包重叠

offset += i; //当前包起点后移

if (end <= offset)

goto err;

skb_pull(skb, i); //删除当前包前部i字节.

if (skb->ip_summed != CHECKSUM_UNNECESSARY)

skb->ip_summed = CHECKSUM_NONE;

}

}

// next是当前包的后一包

while (next && FRAG_CB(next)->offset < end) { //后一包与当前包有重叠

int i = end - FRAG_CB(next)->offset; /* overlap is 'i' bytes */

if (i < next->len) { //当前包尾部小于后一包尾部

/* Eat head of the next overlapped fragment

* and leave the loop. The next ones cannot overlap.

*/

FRAG_CB(next)->offset += i; //后一包起点后移

skb_pull(next, i); //删除后一包i字节

qp->meat -= i; //meat为队列已容纳的总字节数

if (next->ip_summed != CHECKSUM_UNNECESSARY)

next->ip_summed = CHECKSUM_NONE;

break;

} else { //当前包尾部大于或等于后一包尾部, 则删除后一包

struct sk_buff *free_it = next;

/* Old fragmnet is completely overridden with

* new one drop it.

*/

next = next->next;

if (prev)

    prev->next = next; 

else //说明next包是队列首包

          qp->fragments = next; 

           qp->meat -= free_it->len;

frag_kfree_skb(free_it);

}

}

FRAG_CB(skb)->offset = offset; //在skb的cb[]块上记录当前包代表的数据位移

/* Insert this fragment in the chain of fragments. */

       //将该分片插入到分片队列中：设置设备，增加meat分片总长度，如果偏移为0则说明是第一个包，置上FIRST_IN标志。

skb->next = next;

if (prev)

prev->next = skb;

else

qp->fragments = skb; //作为首包

if (skb->dev)

qp->iif = skb->dev->ifindex; //取包的输入设号号

skb->dev = NULL;

qp->meat += skb->len;

atomic_add(skb->truesize, &ip_frag_mem); //truesize为包描述结构与数据区总长

if (offset == 0) //首包

qp->last_in |= FIRST_IN; 

return;

err:

kfree_skb(skb);

}