ggaaooppeenngg

为什么计算机科学是无限的但生命是有限的

IP 的分片与重组

ip 分片的主体函数在 ip_fragment 当中,重组则在 ip_defrag 当中。第一个分片的标志 Offset 为 0,MF 为 1,之后的分片则是 Offset 非 0,MF 为 1,最后一个分片则是 Offset 非 0,但是 MF 为 0。以此来分别当前的 IP packet 是否是一个分片。从 IP 层向上层协议发送数据包的时候就会进行重组,比如在 ip_local_deliver 当中,调用了。说一句题外话, TCP 有 MSS ,保障 TCP message 不超过分片大小,这样是一种对底层协议有感知的行为。

1
2
3
4
if (ip_is_fragment(ip_hdr(skb))) {
if (ip_defrag(net, skb, IP_DEFRAG_LOCAL_DELIVER))
return 0;
}

IP 分片

ip_is_fragment 对应的条件就是 (iph->frag_off & htons(IP_MF | IP_OFFSET)) != 0;

ip_fragment 当中会碰到几种情况,一种是不需要分片的 IP packet,这种很好,省心,一种是需要分片的 IP packet,这种最操心,还有一种是已经按分片负载的长度分配好了 buffer 只要加个头就相当于分片完成了就也非常棒。要从头开始进行分配的情况属于慢速路径,而已经有 buffer 准好的,直接加个头就完事的属于快速路径,快速路径的内存拷贝代价更低。

ip_fragment 主要检查 IP 是否允许进行分片,不然的话就返回一个 ICMP 错误。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct iphdr *iph = ip_hdr(skb);

if ((iph->frag_off & htons(IP_DF)) == 0)
return ip_do_fragment(net, sk, skb, output);

if (unlikely(!skb->ignore_df ||
(IPCB(skb)->frag_max_size &&
IPCB(skb)->frag_max_size > mtu))) {
IP_INC_STATS(net, IPSTATS_MIB_FRAGFAILS);
icmp_send(skb, ICMP_DEST_UNREACH, ICMP_FRAG_NEEDED,
htonl(mtu));
kfree_skb(skb);
return -EMSGSIZE;
}

return ip_do_fragment(net, sk, skb, output);

然后进入到 ip_do_fragment 当中。我们先看一下慢速路径是如何处理。

首先知道 IP 头部的长度,已经负载 (left),然后当前的指针,已经链路层需要预留的长度。

1
2
3
4
5
6
7
8
slow_path:
iph = ip_hdr(skb);

left = skb->len - hlen; /* Space per frame */
ptr = hlen; /* Where to start from */

ll_rs = LL_RESERVED_SPACE(rt->dst.dev);

IP 的 offset,以及不是最后一个分片的标志位,这里是进行分片的,不知道为什么要获取一些重组时候需要的数据,TODO。

/*
 *    Fragment the datagram.
 */

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

调整要分配的 skb_buff 的长度,首先不能超过 mtu,然后最后一段要按 8 对齐。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
* Keep copying data until we run out.
*/

while (left > 0) {
len = left;
/* IF: it doesn't fit, use 'mtu' - the data space left */
if (len > mtu)
len = mtu;
/* IF: we are not sending up to and including the packet end
then align the next start on an eight byte boundary */
if (len < left) {
len &= ~7;
}

/* Allocate buffer */
skb2 = alloc_skb(len + hlen + ll_rs, GFP_ATOMIC);
if (!skb2) {
err = -ENOMEM;
goto fail;
}

设置分片的元数据,ip_copy_metadata 会拷贝优先级,协议类型,等辅助信息。然后保留 L2 的头部空间,接着在保留 IP 层的长度,然后设置网络头部,接着设置传输层头部的位置,就是一些初始化的动作。

1
2
3
4
5
6
7
8
9
/*
* Set up data on packet
*/

ip_copy_metadata(skb2, skb);
skb_reserve(skb2, ll_rs);
skb_put(skb2, len + hlen);
skb_reset_network_header(skb2);
skb2->transport_header = skb2->network_header + hlen;

设置对应 sk 为 owner

1
2
3
4
5
6
7
/*
* Charge the memory for the fragment to any owner
* it might possess
*/

if (skb->sk)
skb_set_owner_w(skb2, skb->sk);

拷贝网络层的头部

1
2
3
4
5
/*
* Copy the packet header into the new buffer.
*/

skb_copy_from_linear_data(skb, skb_network_header(skb2), hlen);

然后拷贝真正的负载,这里没有直接用 memcpy 的原因是,对应的空间不一定是连续的,它可能含有 frag_list,甚至是之前检查没有通过的快速路径到达了这里。

1
2
3
4
5
6
/*
* Copy a block of the IP datagram.
*/
if (skb_copy_bits(skb, ptr, skb_transport_header(skb2), len))
BUG();
left -= len;

设置 IP 头的偏移和分片标志。

1
2
3
4
5
6
7
8
/*
* Fill in the new header fields.
*/
iph = ip_hdr(skb2);
iph->frag_off = htons((offset >> 3));

if (IPCB(skb)->flags & IPSKB_FRAG_PMTU)
iph->frag_off |= htons(IP_DF);

如果是第一个分片就尝试更新 IP options。

1
2
3
4
5
6
7
8
/* ANK: dirty, but effective trick. Upgrade options only if
* the segment to be fragmented was THE FIRST (otherwise,
* options are already fixed) and make it ONCE
* on the initial skb, so that all the following fragments
* will inherit fixed options.
*/
if (offset == 0)
ip_options_fragment(skb);

最后修改位移,更新标记位,计算 checksum,然后送到 output。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
* Added AC : If we are fragmenting a fragment that's not the
* last fragment then keep MF on each bit
*/
if (left > 0 || not_last_frag)
iph->frag_off |= htons(IP_MF);
ptr += len;
offset += len;

/*
* Put this fragment into the sending queue.
*/
iph->tot_len = htons(len + hlen);

ip_send_check(iph);

err = output(net, sk, skb2);
if (err)
goto fail;

IP_INC_STATS(net, IPSTATS_MIB_FRAGCREATES);

这个就是慢速路径的分片过程,快速路径的分片过程其实更简单,因为比较麻烦的事情已经在 ip_append_data 里面处理过了,在我上一篇文章里面有介绍这个过程,就是在上层调用 ip_append_data 的时候,会在主动的进行分段式的缓存,而不使用连续空间,每个分段式的换粗也会不超过分片的大小,这样每个缓存就可以直接用来做分片了。

现在再回头看快速路径,快速路径主要检查有没有 frag_list 也就是之前分配好的 buffer 列表。获取第一个 buffer (存在 frags 里面,不是 frag_list)的长度,如果比 mtu 大,或者不是 8 的倍数,或者已经是分段了,或者是一段 shared skb_buff (因为快速路径不会拷贝内存,慢速路径会会分配新的内存,不影响之前有人引用)都不行,要进入慢速路径。

1
2
3
4
5
6
7
8
9
10
if (skb_has_frag_list(skb)) {
struct sk_buff *frag, *frag2;
unsigned int first_len = skb_pagelen(skb);

if (first_len - hlen > mtu ||
((first_len - hlen) & 7) ||
ip_is_fragment(iph) ||
skb_cloned(skb))
goto slow_path;

首先保证每个 frag_list 里面 frag 不超过 mtu,然后不是最后一段需要是 8 的倍数,有足够的头部空间用来给新的 IP 分片用,然后 frag 的 buffer 也不能是 shared,最后绑定 sk 关系,减掉 skb 的 truesize。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
skb_walk_frags(skb, frag) {
/* Correct geometry. */
if (frag->len > mtu ||
((frag->len & 7) && frag->next) ||
skb_headroom(frag) < hlen)
goto slow_path_clean;

/* Partially cloned skb? */
if (skb_shared(frag))
goto slow_path_clean;

BUG_ON(frag->sk);
if (skb->sk) {
frag->sk = skb->sk;
frag->destructor = sock_wfree;
}
skb->truesize -= frag->truesize;
}

到这里就可以真的开始分片了,初始化头部信息,以及要用来分片的 frag。

1
2
3
4
5
6
7
8
9
err = 0;
offset = 0;
frag = skb_shinfo(skb)->frag_list;
skb_frag_list_init(skb);
skb->data_len = first_len - skb_headlen(skb);
skb->len = first_len;
iph->tot_len = htons(first_len);
iph->frag_off = htons(IP_MF);
ip_send_check(iph);

这个循环里面做的事情就更简单了,比起慢速路径来说,就是给每个原本没有头部的 buffer,加上头部变成真正的 fragment。保留空间,设置网络层头部,拷贝头部memcpy(skb_network_header(frag), iph, hlen);,拷贝原信息,如果是第一个分片更新 options,然后更新标记位,然后送到 output。直到 frag_list 被循环完,这就大功告成了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
for (;;) {
/* Prepare header of the next frame,
* before previous one went down. */
if (frag) {
frag->ip_summed = CHECKSUM_NONE;
skb_reset_transport_header(frag);
__skb_push(frag, hlen);
skb_reset_network_header(frag);
memcpy(skb_network_header(frag), iph, hlen);
iph = ip_hdr(frag);
iph->tot_len = htons(frag->len);
ip_copy_metadata(frag, skb);
if (offset == 0)
ip_options_fragment(frag);
offset += skb->len - hlen;
iph->frag_off = htons(offset>>3);
if (frag->next)
iph->frag_off |= htons(IP_MF);
/* Ready, complete checksum */
ip_send_check(iph);
}

err = output(net, sk, skb);

if (!err)
IP_INC_STATS(net, IPSTATS_MIB_FRAGCREATES);
if (err || !frag)
break;

skb = frag;
frag = skb->next;
skb->next = NULL;
}

IP 重组

重组一般发生在向上层协议栈传输的时候,不过有的路由器也有可能进行重组,可能要对整个 IP packet 进行校验等,一般情况下,转发不太会对 IP 进行重组。IP 重组讲起来也有些麻烦。

每个正在被重组的 IP packet 都会用一个 ipq 表示,这个 ipq 使用的是 hash table (inet_frags->hash) 的搜索结构,没有 ipq 由 源地址,目的地址,协议和 ID 确定,所以存在重复的可能。ip_defrag依赖两个函数一个是ip_find用于寻找 ipq 如果没有找到的话会自动创建一个,其次是用于入队的 ip_frag_queue ,进行重组的工作。sk_buff->cb 用于保存当前的 offset。对于分片的重组也会有超时机制,防止一个 ipq 停留太长的时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/* Process an incoming IP datagram fragment. */
int ip_defrag(struct net *net, struct sk_buff *skb, u32 user)
{
struct net_device *dev = skb->dev ? : skb_dst(skb)->dev;
int vif = l3mdev_master_ifindex_rcu(dev);
struct ipq *qp;

__IP_INC_STATS(net, IPSTATS_MIB_REASMREQDS);
skb_orphan(skb);

/* Lookup (or create) queue header */
qp = ip_find(net, ip_hdr(skb), user, vif);
if (qp) {
int ret;

spin_lock(&qp->q.lock);

ret = ip_frag_queue(qp, skb);

spin_unlock(&qp->q.lock);
ipq_put(qp);
return ret;
}

__IP_INC_STATS(net, IPSTATS_MIB_REASMFAILS);
kfree_skb(skb);
return -ENOMEM;
}

ip_find 主要两个功能,根据原信息计算 hash 值,从net->ipv4.frags 的 hash 表当中寻找到对应的 ipq

1
2
3
4
hash = ipqhashfn(iph->id, iph->saddr, iph->daddr, iph->protocol);

q = inet_frag_find(&net->ipv4.frags, &ip4_frags, &arg, hash);

然后进入到 ip_frag_queue 当中首先检查,如果出现错误,就把 ipq 标记为可以被之后的垃圾回收清扫。

1
2
3
4
5
6
7
8
9
10
if (qp->q.flags & INET_FRAG_COMPLETE)
goto err;

if (!(IPCB(skb)->flags & IPSKB_FRAG_COMPLETE) &&
unlikely(ip_frag_too_far(qp)) &&
unlikely(err = ip_frag_reinit(qp))) {
ipq_kill(qp);
goto err;
}

获取 offset,flags 和头部。

1
2
3
4
5
6
7
ecn = ip4_frag_ecn(ip_hdr(skb)->tos);
offset = ntohs(ip_hdr(skb)->frag_off);
flags = offset & ~IP_OFFSET;
offset &= IP_OFFSET;
offset <<= 3; /* offset is in 8-byte chunks */
ihl = ip_hdrlen(skb);

计算这个追加的 fragment 会拷贝的位置的末尾在哪。

1
2
3
4
/* Determine the position of this fragment. */
end = offset + skb->len - skb_network_offset(skb) - ihl;
err = -EINVAL;

如果是最后一个 fragment,那么不应该超过 q.len,或者已经有了最后一个了,但是 endq.len 不一致,所以有一些 corruption。如果检查没问题,就更新q.flasg 标记为最后一个和把 end 赋值给q.len

1
2
3
4
5
6
7
8
9
10
11
/* 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 corrupted.
*/
if (end < qp->q.len ||
((qp->q.flags & INET_FRAG_LAST_IN) && end != qp->q.len))
goto err;
qp->q.flags |= INET_FRAG_LAST_IN;
qp->q.len = end;

如果不是最后一个,长度要与 8 对齐,然后更新 q.len

1
2
3
4
5
6
7
8
9
10
11
12
13
} else {
if (end&7) {
end &= ~7;
if (skb->ip_summed != CHECKSUM_UNNECESSARY)
skb->ip_summed = CHECKSUM_NONE;
}
if (end > qp->q.len) {
/* Some bits beyond end -> corruption. */
if (qp->q.flags & INET_FRAG_LAST_IN)
goto err;
qp->q.len = end;
}

剩下的就是从链表 q.fragments 当中中根据offset 寻找到要插入的位置,会先看一下表尾,再进行遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
if (end == offset)
goto err;

err = -ENOMEM;
if (!pskb_pull(skb, skb_network_offset(skb) + ihl))
goto err;

err = pskb_trim_rcsum(skb, end - offset);
if (err)
goto err;

/* 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 = qp->q.fragments_tail;
if (!prev || FRAG_CB(prev)->offset < offset) {
next = NULL;
goto found;
}
prev = NULL;
for (next = qp->q.fragments; next != NULL; next = next->next) {
if (FRAG_CB(next)->offset >= offset)
break; /* bingo! */
prev = next;
}

如果和前面的分组有重叠,就把重叠的部分去掉,CHECKSUM_NONE 可以使当前的校验和失效。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
if (prev) {
int i = (FRAG_CB(prev)->offset + prev->len) - offset;

if (i > 0) {
offset += i;
err = -EINVAL;
if (end <= offset)
goto err;
err = -ENOMEM;
if (!pskb_pull(skb, i))
goto err;
if (skb->ip_summed != CHECKSUM_UNNECESSARY)
skb->ip_summed = CHECKSUM_NONE;
}
}

然后向后检查有没有重叠,并且把重叠的部分去掉,如果重叠的部分比 next 本身还要大,直接把 next 删掉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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.
*/
if (!pskb_pull(next, i))
goto err;
FRAG_CB(next)->offset += i;
qp->q.meat -= i;
if (next->ip_summed != CHECKSUM_UNNECESSARY)
next->ip_summed = CHECKSUM_NONE;
break;
} else {
struct sk_buff *free_it = next;

/* Old fragment is completely overridden with
* new one drop it.
*/
next = next->next;

if (prev)
prev->next = next;
else
qp->q.fragments = next;

qp->q.meat -= free_it->len;
sub_frag_mem_limit(qp->q.net, free_it->truesize);
kfree_skb(free_it);
}
}

剩下的就是插入链表,并且更新 ipq 的信息了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
skb->next = next;
if (!next)
qp->q.fragments_tail = skb;
if (prev)
prev->next = skb;
else
qp->q.fragments = skb;

dev = skb->dev;
if (dev) {
qp->iif = dev->ifindex;
skb->dev = NULL;
}
qp->q.stamp = skb->tstamp;
qp->q.meat += skb->len;
qp->ecn |= ecn;
add_frag_mem_limit(qp->q.net, skb->truesize);
if (offset == 0)
qp->q.flags |= INET_FRAG_FIRST_IN;

fragsize = skb->len + ihl;

if (fragsize > qp->q.max_size)
qp->q.max_size = fragsize;

if (ip_hdr(skb)->frag_off & htons(IP_DF) &&
fragsize > qp->max_df_size)
qp->max_df_size = fragsize;

然后如果,第一个包和最后一个包都收齐了的话,就尝试进行重组。

1
2
3
4
5
6
7
8
9
if (qp->q.flags == (INET_FRAG_FIRST_IN | INET_FRAG_LAST_IN) &&
qp->q.meat == qp->q.len) {
unsigned long orefdst = skb->_skb_refdst;

skb->_skb_refdst = 0UL;
err = ip_frag_reasm(qp, prev, dev);
skb->_skb_refdst = orefdst;
return err;
}

另外垃圾回收的过程,就是在内存超过阈值的时候,把超时的 ipq 从 hash 表当中剔除。内存阈值通过 ip_frag_mem获取。

1
2
3
4
int ip_frag_mem(struct net *net)
{
return sum_frag_mem_limit(&net->ipv4.frags);
}

总结

IP 分片与重组的整体流程大致如此,IP 面临的覆盖的现象,是由于不同的 packet 但是 hash 元素一样导致的。另一方面重叠处理一个是防止出现重叠包攻击导致内存溢出。还有就是具体的校验过程会丢给上层的协议来控制。