Defragment IP packets

The defragmenting code is enabled by CONFIG_IP_DEFRAG. The code is useful for TFTP transfers, so the static reassembly buffer is sized based on CONFIG_TFTP_MAXBLOCK (default is 16kB).

The packet buffer is used as an array of "hole" structures, acting as a double-linked list. Each new fragment can split a hole in two, reduce a hole or fill a hole. No support is there for a fragment overlapping two diffrent holes (i.e., thre new fragment is across an already-received fragment).

The code includes a number of suggestions by Robin Getz.

Signed-off-by Alessandro Rubini <[email protected]>

---
 net/net.c |  172
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--
 1 files changed, 167 insertions(+), 5 deletions(-)

net/net.c +0 -0

index 641c37c..be382dd 100644
@@ -1117,6 +1117,164 @@ static void CDPStart(void)
 }

net/net.c +8 -0

+#endif
+#define IP_PAYLOAD (CONFIG_TFTP_MAXBLOCK + 4)
+#define IP_PKTSIZE (IP_PAYLOAD + IP_HDR_SIZE_NO_UDP)
+
+/*
+ * this is the packet being assembled, either data or frag control.
+ * Fragments go by 8 bytes, so this union must be 8 bytes long
+ */

net/net.c +18 -0

+	static uchar pkt_buff[IP_PKTSIZE] __attribute__((aligned(PKTALIGN)));
+	static u16 first_hole, total_len;
+	struct hole *payload, *thisfrag, *h, *newh;
+	IP_t *localip = (IP_t *)pkt_buff;
+	uchar *indata = (uchar *)ip;
+	int offset8, start, len, done = 0;
+	u16 ip_off = ntohs(ip->ip_off);
+
+	/* payload starts after IP header, this fragment is in there */
+	payload = (struct hole *)(pkt_buff + IP_HDR_SIZE_NO_UDP);
+	offset8 =  (ip_off & IP_OFFS);
+	thisfrag = payload + offset8;
+	start = offset8 * 8;
+	len = ntohs(ip->ip_len) - IP_HDR_SIZE_NO_UDP;
+
+	if (start + len > IP_PAYLOAD) /* fragment extends too far */
+		return NULL;
+

net/net.c +93 -0

+	/*
+	 * What follows is the reassembly algorithm. We use the payload
+	 * array as a linked list of hole descriptors, as each hole starts
+	 * at a multiple of 8 bytes. However, last byte can be whaever value,
+	 * so it is represented as byte count, not as 8-byte blocks.
+	 */
+
+	h = payload + first_hole;
+	while (h->last_byte < start) {
+		if (!h->next_hole) {
+			/* no hole that far away */
+			return NULL;
+		}
+		h = payload + h->next_hole;
+	}
+
+	if (offset8 + (len / 8) <= h - payload) {
+		/* no overlap with holes (dup fragment?) */
+		return NULL;
+	}
+
+	if (!(ip_off & IP_FLAGS_MFRAG)) {
+		/* no more fragmentss: truncate this (last) hole */
+		total_len = start + len;
+		h->last_byte = start + len;
+	}
+
+	/*
+	 * There is some overlap: fix the hole list. This code doesn't
+	 * deal with a fragment that overlaps with two different holes
+	 * (thus being a superset of a previously-received fragment).
+	 */
+
+	if ( (h >= thisfrag) && (h->last_byte <= start + len) ) {
+		/* complete overlap with hole: remove hole */
+		if (!h->prev_hole && !h->next_hole) {
+			/* last remaining hole */
+			done = 1;
+		} else if (!h->prev_hole) {
+			/* first hole */
+			first_hole = h->next_hole;
+			payload[h->next_hole].prev_hole = 0;
+		} else if (!h->next_hole) {
+			/* last hole */
+			payload[h->prev_hole].next_hole = 0;
+		} else {
+			/* in the middle of the list */
+			payload[h->next_hole].prev_hole = h->prev_hole;
+			payload[h->prev_hole].next_hole = h->next_hole;
+		}
+
+	} else if (h->last_byte <= start + len) {
+		/* overlaps with final part of the hole: shorten this hole */
+		h->last_byte = start;
+
+	} else if (h >= thisfrag) {
+		/* overlaps with initial part of the hole: move this hole */
+		newh = thisfrag + (len / 8);
+		*newh = *h;
+		h = newh;
+		if (h->next_hole)
+			payload[h->next_hole].prev_hole = (h - payload);
+		if (h->prev_hole)
+			payload[h->prev_hole].next_hole = (h - payload);
+		else
+			first_hole = (h - payload);
+
+	} else {
+		/* fragment sits in the middle: split the hole */
+		newh = thisfrag + (len / 8);
+		*newh = *h;
+		h->last_byte = start;
+		h->next_hole = (newh - payload);
+		newh->prev_hole = (h - payload);
+		if (newh->next_hole)
+			payload[newh->next_hole].prev_hole = (newh - payload);
+	}
+
+	/* finally copy this fragment and possibly return whole packet */
+	memcpy((uchar *)thisfrag, indata + IP_HDR_SIZE_NO_UDP, len);
+	if (!done)
+		return NULL;
+
+	localip->ip_len = htons(total_len);
+	*lenp = total_len + IP_HDR_SIZE_NO_UDP;
+	return localip;
+}
+
+static inline IP_t *NetDefragment(IP_t *ip, int *lenp)
+{
+	u16 ip_off = ntohs(ip->ip_off);
+	if (!(ip_off & (IP_OFFS | IP_FLAGS_MFRAG)))
+		return ip; /* not a fragment */

net/net.c +2 -0

 void
 NetReceive(volatile uchar * inpkt, int len)

@@ -1363,10 +1521,12 @@ NetReceive(volatile uchar * inpkt, int len)
 #ifdef ET_DEBUG
 		puts ("Got IP\n");
 #endif
+		/* Before we start poking the header, make sure it is there */
 		if (len < IP_HDR_SIZE) {
 			debug ("len bad %d < %lu\n", len, (ulong)IP_HDR_SIZE);
 			return;
 		}
+		/* Check the packet length */
 		if (len < ntohs(ip->ip_len)) {
 			printf("len bad %d < %d\n", len,
 ntohs(ip->ip_len));

net/net.c +4 -5

 			return;

@@ -1375,21 +1535,20 @@ NetReceive(volatile uchar * inpkt, int len)
 #ifdef ET_DEBUG
 		printf("len=%d, v=%02x\n", len, ip->ip_hl_v & 0xff);
 #endif
+		/* Can't deal with anything except IPv4 */
 		if ((ip->ip_hl_v & 0xf0) != 0x40) {
 			return;
 		}
-		/* Can't deal with fragments */
-		if (ip->ip_off & htons(IP_OFFS | IP_FLAGS_MFRAG)) {
-			return;
-		}
-		/* can't deal with headers > 20 bytes */
+		/* Can't deal with IP options (headers != 20 bytes) */
 		if ((ip->ip_hl_v & 0x0f) > 0x05) {
 			return;
 		}
+		/* Check the Checksum of the header */
 		if (!NetCksumOk((uchar *)ip, IP_HDR_SIZE_NO_UDP / 2)) {
 			puts ("checksum bad\n");
 			return;
 		}
+		/* If it is not for us, ignore it */
 		tmp = NetReadIP(&ip->ip_dst);
 		if (NetOurIP && tmp != NetOurIP && tmp != 0xFFFFFFFF) {
 #ifdef CONFIG_MCAST_TFTP

net/net.c +0 -0

 		/*
 		 * watch for ICMP host redirects
 		 *

Review

Quoted 2 lines

(quoted diff) +2 -0

+#ifndef CONFIG_TFTP_MAXBLOCK
+#define CONFIG_TFTP_MAXBLOCK 16384

It is more than tftp - nfs could also use the same.

How about CONFIG_NET_MAXDEFRAG instead?

Review

Quoted 2 lines

(quoted diff) +2 -0

+static IP_t *__NetDefragment(IP_t *ip, int *lenp)
+{

I don't understand the purpose of the lenp.

The calling function doesn't use the len var, except for ICMP_ECHO_REQUEST, which are not allowed to be fragmented.

I eliminated it - and suffered no side effects.

Quoted 5 lines

(quoted diff) +5 -0

+	if (!total_len || localip->ip_id != ip->ip_id) {
+		/* new (or different) packet, reset structs */
+		total_len = 0xffff;
+		payload[0].last_byte = ~0;
+		payload[0].next_hole = 0;

Review

Quoted 5 lines

(quoted diff) +5 -0

+		payload[0].prev_hole = 0;
+		first_hole = 0;
+		/* any IP header will work, copy the first we received */
+		memcpy(localip, ip, IP_HDR_SIZE_NO_UDP);
+	}

I'm not sure the reset if we loose a packet, or get a bad one - start over is a great idea.

For some reason - why I'm ping flooding when tftping a large file (with large tftp block size) - things hang. If I set the block size to under the MTU - it works fine. Do you get the same?

Review

Quoted 7 lines

(quoted diff) +7 -0

+#else /* !CONFIG_IP_DEFRAG */
+
+static inline IP_t *NetDefragment(IP_t *ip, int *lenp)
+{
+	return ip;
+}
+#endif

This needs to have the same logic (ip_off & (IP_OFFS | IP_FLAGS_MFRAG)) as the above function. See comment below.

Quoted 3 lines

For some reason - why I'm ping flooding when tftping a large file (with large tftp block size) - things hang. If I set the block size to under the MTU - it works fine. Do you get the same?

Didn't try, and I can't do that today. I suspect either your ping is over-mtu, so each new fragment triggers the above code,

or simply your
ether+uboot can't keep up with the data rate.

As eaplained in the cover letter <[email protected]> some fragments can be lost in high traffic, as polling mode doesn't allow to enqueue packets. So I think you just loose some fragments, as target CPU time is eaten by the ping packets, and you don't get the complete reassembled packet any more.

I'm pretty sure it's like this.

On the other hand, I found a minor issue in this situation:
- start a tftp transfer
- ctrl-C it
- start another

Server retransmissions for the first transfer go into the defrag engine e that reset-defrag-data code is triggered, so a packet may be lost, and I get a sporadic T in the receiving u-boot. I think it's not a real problem, though --- or, now that I rethink about it, it can be the same issue as above: my ether can't enqueue 8k of stuff so a fragment is lost in that case.

Quoted 2 lines

or simply your
ether+uboot can't keep up with the data rate.

That doesn't explain, why does it work, when there is no fragmentation???

Quoted 1 line

I'm pretty sure it's like this.

I'm not convinced yet - but need to do some further poking on a different network...

What is missing in the reassembly code (that is described in RFC815) is the timer. (quote from the RFC):
--------------
The final part of the algorithm is some sort of timer based mechanism which decrements the time to live field of each partially reassembled datagram, so that incomplete datagrams which have outlived their usefulness can be detected and deleted.
--------------

Quoted 4 lines

Quoted 2 lines

or simply your
ether+uboot can't keep up with the data rate.

That doesn't explain, why does it work, when there is no fragmentation???

Well, with no fragmentation there is less traffic. Each tftp packet is one patch, instead of a burst of packets (intermixed with pings).

Is the target replying to all pings?

Or is it loosing some?

If it looses say 30%, I expect one fragment in 3 to be lost as well. If your big-tftp is 4 fragments, 20% passes it loss is equally spread

but I fear much less as the burst saturates the incoming queue.

Quoted 4 lines

Quoted 1 line

I'm pretty sure it's like this.

I'm not convinced yet - but need to do some further poking on a different network...

Thanks for these tests, mine is just guessing.

Quoted 8 lines

What is missing in the reassembly code (that is described in RFC815) is the timer. (quote from the RFC):
--------------
The final part of the algorithm is some sort of timer based mechanism which decrements the time to live field of each partially reassembled datagram, so that incomplete datagrams which have outlived their usefulness can be detected and deleted.
--------------

But I reassemble one packet only, so I don't need to timeout partly-filled packets to recover memory.

A soon as I have a fragment for a new packet, the old packet is discarded (while unfragmented stuff flies intermixed).

Quoted 1 line

Is the target replying to all pings?

Yes. And I can see the same in wireshark.

Quoted 9 lines

Quoted 8 lines

What is missing in the reassembly code (that is described in RFC815) is the timer. (quote from the RFC):
--------------
The final part of the algorithm is some sort of timer based mechanism which decrements the time to live field of each partially reassembled datagram, so that incomplete datagrams which have outlived their usefulness can be detected and deleted.
--------------

Quoted 2 lines

But I reassemble one packet only, so I don't need to timeout partly-filled packets to recover memory.

But it is for the state that you described - the user cntr-C a current transfer, and the reassembly algorithm doesn't know to throw away a partially accepted packet, when things are cancelled...

Quoted 3 lines

Quoted 1 line

Is the target replying to all pings?

Yes. And I can see the same in wireshark.

Ah. I see. Strange...

Quoted 9 lines

Quoted 9 lines

Quoted 8 lines

What is missing in the reassembly code (that is described in RFC815) is the timer. (quote from the RFC):
--------------
The final part of the algorithm is some sort of timer based mechanism which decrements the time to live field of each partially reassembled datagram, so that incomplete datagrams which have outlived their usefulness can be detected and deleted.
--------------

Quoted 6 lines

Quoted 2 lines

But I reassemble one packet only, so I don't need to timeout partly-filled packets to recover memory.

But it is for the state that you described - the user cntr-C a current transfer, and the reassembly algorithm doesn't know to throw away a partially accepted packet, when things are cancelled...

No, it's not like that.

The old instance of the TFTP server resends the last packet of the aborted xfer,

while the new server sends the new
packet. Both packets are new, they just come as intermixed fragments. And none survives as there is only one reassembly buffer.

Or something
like that, but both are fresh fragmented packets, no timeout would solve this sporadic problem.

It seems to me that if we want a secure defagment system (one that can be use to net-boot production systems in hostile networks), it's going to be too complex. It could work well, however, as a faster tool for the interactive developer.

What I'm talking about is:
- start a tftp file transfer.
- CNTR-C it, causing a partial reassembly to done.
- start a new transfer.

All I did was add this to the start of NetLoop() to ensure that things are OK.

#ifdef CONFIG_IP_DEFRAG
memset(pkt_buff, 0, IP_HDR_SIZE_NO_UDP);
#endif

Quoted 2 lines

The old instance of the TFTP server resends the last packet of the aborted xfer,

As a minimal test - since we are only talking about tftp and nfs (so far) - if we did not attempt to assemble packets which are not coming from the serverip, that might be an OK thing to do...

if (NetReadIP(&ip->ip_src) != NetServerIP)

All I'm asking for is something robust... :)

Quoted 3 lines

For some reason - why I'm ping flooding when tftping a large file (with large tftp block size) - things hang. If I set the block size to under the MTU - it works fine. Do you get the same?

Didn't try, and I can't do that today. I suspect either your ping is over-mtu, so each new fragment triggers the above code, or simply your ether+uboot can't keep up with the data rate.

Thanks for your comments.

Quoted 4 lines

Review

Quoted 2 lines

(quoted diff) +2 -0

+#ifndef CONFIG_TFTP_MAXBLOCK
+#define CONFIG_TFTP_MAXBLOCK 16384

It is more than tftp - nfs could also use the same.

Yes, I know. But most users are tftp ones. And if you want an even number (like 16k) as a tftp packet you need to add the headers and the sequence count. And I prefer to have the useful number in the config. So I used "TFTP" in the name in order for NFS users to know they must make some calculation.

Quoted 1 line

How about CONFIG_NET_MAXDEFRAG instead?

We could have MAXPAYLOAD if we count in NFS overhead as well (I don't know how much it is, currently. Hope you see my point.

Quoted 5 lines

Review

Quoted 2 lines

(quoted diff) +2 -0

+static IP_t *__NetDefragment(IP_t *ip, int *lenp)
+{

I don't understand the purpose of the lenp.

Quoted 4 lines

The calling function doesn't use the len var, except for ICMP_ECHO_REQUEST, which are not allowed to be fragmented.

I eliminated it - and suffered no side effects.

Well, since the caller has this "len" variable, I didn't want to leave it corrupted. But if it's actually unused after this point, we can well discard it.

Quoted 10 lines

Review

Quoted 7 lines

(quoted diff) +7 -0

+#else /* !CONFIG_IP_DEFRAG */
+
+static inline IP_t *NetDefragment(IP_t *ip, int *lenp)
+{
+	return ip;
+}
+#endif

This needs to have the same logic (ip_off & (IP_OFFS | IP_FLAGS_MFRAG)) as the above function. See comment below.

Yes, correct. Thanks.

Were you going to send an update for Ben?

Quoted 2 lines

Were you going to send an update for Ben?

Yes, but I was waiting for your confirmation. Will do tomorrow.

/alessandro
_______________________________________________
U-Boot mailing list
U-Boot at lists.denx.de
http://lists.denx.de/mailman/listinfo/u-boot