Skip to contentSkip to conversation

Fragment ID wrap workaround (read-only, untested).

PATCH Rusty Russell (IBM) 5 participants 9 messages Jul 15, 2004 – Jul 27, 2004

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

Hi all,

I spoke about this today, thought I'd send the code out. Useful only
for reading, as it's entirely untested and some is tricky and needs careful thinking.

Name: Fragment ID Wrap Workaround
Status: Untested

There's at least one old IBM Bugzilla bug, in which fragement IDs wrapped, causing NFS data corruption on UDP stresstesting.

Solution presented here is twofold:

1) Move the offset of the fragments every time the ID wraps (usually the packet doesn't fit exactly into the MTU, so we have some slack), and

2) Check overlapping fragments that the contents match: if not, drop the whole thing.

Note that I also implemented skb_iter functions, so I could compare the fragment overlap efficiently: really should be a separate patch. DaveM points out (FIXME) that doing the double walk means we need to guarantee two kmaps for the networking code.

Also applies to IPv6. Simpler implementation would just drop all fragments on any overlap as a "doesn't happen IRL" case (it needs someone to duplicate a packet, then send each one by a different MTU path).

include/linux/ip.h +1 -1
diff -urpN --exclude TAGS -X /home/rusty/devel/kernel/kernel-patches/current-dontdiff --minimal .4882-linux-2.6.7-bk20/include/linux/ip.h .4882-linux-2.6.7-bk20.updated/include/linux/ip.h
@@ -118,12 +118,12 @@ struct inet_opt {
 	int			tos;		/* TOS */
 	unsigned	   	cmsg_flags;
 	struct ip_options	*opt;
+	__u32			id;		/* ID counter for DF pkts */
 	__u16			sport;		/* Source port */
 	unsigned char		hdrincl;	/* Include headers ? */
 	__u8			mc_ttl;		/* Multicasting TTL */
 	__u8			mc_loop;	/* Loopback */
 	__u8			pmtudisc;
-	__u16			id;		/* ID counter for DF pkts */
 	unsigned		recverr : 1,
 				freebind : 1;
 	int			mc_index;	/* Multicast device index */
include/linux/skbuff.h +17 -0
diff -urpN --exclude TAGS -X /home/rusty/devel/kernel/kernel-patches/current-dontdiff --minimal .4882-linux-2.6.7-bk20/include/linux/skbuff.h .4882-linux-2.6.7-bk20.updated/include/linux/skbuff.h
@@ -1108,6 +1108,23 @@ extern void	       skb_split(struct sk_b
 extern void skb_init(void);
 extern void skb_add_mtu(int mtu);
 
+struct skb_iter
+{
+	/* Iteration functions set these */
+	unsigned char *data;
+	unsigned int len;
+
+	/* Private to iteration */
+	unsigned int nextfrag;
+	struct sk_buff *fraglist;
+};
+
+/* Keep iterating until skb_iter_next returns false. */
+extern void skb_iter_first(const struct sk_buff *skb, struct skb_iter *i);
+extern int skb_iter_next(const struct sk_buff *skb, struct skb_iter *i);
+/* Call this if aborting loop before !skb_iter_next */
+extern void skb_iter_abort(const struct sk_buff *skb, struct skb_iter *i);
+
 #ifdef CONFIG_NETFILTER
 static inline void nf_conntrack_put(struct nf_ct_info *nfct)
 {
net/core/skbuff.c +64 -0

70 lines not on this page · raw message

net/ipv4/ip_fragment.c +95 -9

137 lines not on this page · raw message

net/ipv4/ip_output.c +32 -9

58 lines not on this page · raw message

#1 lore raw

Rusty,
Those ideas should work if both sides are Linux, but not
when mixing with something else. A non-Linux receiver won't detect wrap and drop the packet, generally, even if the fragments overlap and don't match, and a non-Linux sender will send (typically) same-sized fragments that aren't offset. Doesn't hurt anything for those cases, so maybe in addition:

My idea for solving this problem is to create an estimator for the reassembly timer. The fundamental problem as I see it is that the reassembly timer is fixed, and about 6000 times too long on a fast network (and worse the faster networks get).

In the typical case, you'll receive lots of successfully reassembled packets from the same destination and, from those, you can build a good time estimate for how long it takes you to receive all the fragments, when you're going to. The reassembly timeout ought to be a little longer than that estimator, which might be a fraction of a millisecond on a local link, and maybe tens of seconds going across the Internet. Then you can time out and release the frags based on the expected behavior, rather than waiting so long the other side has time to wrap while you still have a valid frag queue.

It also has the advantage that, on a faster link, a higher loss rate doesn't have you wasting memory holding fragments that aren't ever going to be reassembled successfully, anyway.

The estimator could be very much like the TCP rtt estimator, and could go in the routing table (not so good for asymmetric paths), the fib, or its own little cache w/ timeout maintained by the reassembly code.

There are some problems with this scheme, too, but I think it fixes most bad behavior on the receiver side with unmodified senders.

Comments?

                                        +-DLS
#2 lore raw
Quoted 4 lines · David Stevens

My idea for solving this problem is to create an estimator for the reassembly timer. The fundamental problem as I see it is that the reassembly timer is fixed, and about 6000 times too long on a fast network (and worse the faster networks get).

Won't that make the worst case behaviour on a congested link much worse?

e.g. consider a very congested link with variable RTTs. Or a link that works relatively smoothly and suddenly the RTT increases.

Yes, running fragmentation over those is not a good idea, but still it should not be made worse.

Your variable timer even with a smoothing algorithm in the RTT estimator will expire far too early and very likely drop a lot more fragments in this scenario than before.

In general handling a link where the RTT increases would seem tricky with your scheme. Unlike TCP there is no retransmit to save the day.

-Andi

#3 lore raw

Andi Kleen <[email protected]> wrote on 07/15/2004 02:27:17 AM:

Quoted 4 lines

Won't that make the worst case behaviour on a congested link much worse?

e.g. consider a very congested link with variable RTTs. Or a link that works relatively smoothly and suddenly the RTT increases.

I know what you mean here, but just to be precise, this isn't an RTT estimator, but an estimator for the time to receive a complete set of fragments. And, of course, it'd need to be scaled to a (potential) max-sized packet, since the number of fragments isn't known in advance, and could be larger. Better multiple the time-out for a 4K reassembly by 16, in case you get a 64K datagram next.

Quoted 2 lines

Yes, running fragmentation over those is not a good idea, but still it should not be made worse.

Delivery to the user of incorrect data is the problem, and, no, it doesn't make that worse. :-) The scenario, to make it clear for everyone, is a small loss rate on a fast network leads to reassembling packets with the same IP ID that are not the same packet when the ID wraps before the frag queue timer has expired. If you're blasting away on a gigabit network (or faster) and you drop one fragment (or more) from a packet you've received, that frag queue will be there 65536 packets later when you reuse the same ID
for a different packet. I think that works out to be 7 secs or so at full rate-- well within the 1-4 minute typical frag queue timer on most systems.
When the second packet arrives, if it's big enough that the missing frag offsets can fulfill reassembly, it'll use them. So, 100% of the time when sending same-sized packets, like NFS mostly does, and you lose 1 fragment, you'll reassemble garbage when the IP ID wraps (well before the frag queue expires). And the checksum will pass anyway on average about 1/64K of the time. If you send at full rate and drop, say, 100 frags a second, it doesn't take too long to get a Frankenpacket-- reassembled from parts of others. :-)

That's the problem the timer idea is trying to solve, and a higher loss rate here is acceptable-- the checksum only fails to catch the problem 1/64K of the time, so you probably have a relatively high loss rate to start with when it's occurring.

Quoted 3 lines

Your variable timer even with a smoothing algorithm in the RTT estimator will expire far too early and very likely drop a lot more fragments in this scenario than before.

Not necessarily, because it doesn't at all have to be a "near" estimate, the way TCP is trying to make it. It can solve the problem by taking a close estimate to the actual time and then using a frag timeout that's 10 times bigger. As long as the frag timeout isn't thousands of times too large (as it is now), IP ID wrap can't happen before you dump the frag queue-- the whole point.

Quoted 3 lines

In general handling a link where the RTT increases would seem tricky with your scheme. Unlike TCP there is no retransmit to save the day.

In the particular case (NFS over UDP), there is both a retransmit (done by RPC) and significant loss rate to start with. As long as the time-out is conservative, I don't think this has to affect other cases significantly.

                                                +-DLS
#5 lore raw
In reply to David Stevens
Quoted 6 lines · On Thu, 15 Jul 2004 07:49:13 -0700 David Stevens <[email protected]> wrote:
Quoted 3 lines

Yes, running fragmentation over those is not a good idea, but still it should not be made worse.

Delivery to the user of incorrect data is the problem, and, no, it doesn't make that worse. :-) The scenario, to make it clear for everyone, is a]

The data corruption problem only starts to become a real issue at Gigabit Speeds and faster. Normally such congested links are much slower

Quoted 9 lines

small loss rate on a fast network leads to reassembling packets with the same IP ID that are not the same packet when the ID wraps before the frag queue timer has expired. If you're blasting away on a gigabit network (or faster) and you drop one fragment (or more) from a packet you've received, that frag queue will be there 65536 packets later when you reuse the same ID
for a different packet. I think that works out to be 7 secs or so at full rate-- well within the 1-4 minute typical frag queue timer on most systems.

[...]

I'm well aware of the Gigabit+ NFS problem. My standard suggestion to solve it is to just get rid of NFS over UDP - it always was a bad idea.

My point was just that you're concentrating on that one only, but you're potentially causing more problems for slow links. The stack has to work well both for slow and fast links though.

Quoted 9 lines
Quoted 4 lines

In general handling a link where the RTT increases would seem tricky with your scheme. Unlike TCP there is no retransmit to save the day.

In the particular case (NFS over UDP), there is both a retransmit (done by RPC) and significant loss rate to start with. As long as the time-out is conservative, I don't think this has to affect other cases significantly.

NFS over UDP is just a bad idea. Don't do it. NFS over TCP works fine these days and should be the prefered choice for everybody.

I don't really see the point of risking problems with slower links just to fix a fundamentally flawed protocol.

And you cannot rely on all UDP based protocols doing this as well.

-Andi

#6 lore raw

Andi Kleen wrote on 07/15/2004 09:27:35 AM:

Quoted 1 line

I'm well aware of the Gigabit+ NFS problem. My standard suggestion to

solve

Quoted 1 line

it is to just get rid of NFS over UDP - it always was a bad idea.

No disagreement here.

Quoted 3 lines

My point was just that you're concentrating on that one only, but you're potentially causing more problems for slow links. The stack has to work well both for slow and fast links though.

That's the problem it's intended to solve, but of course any actual solution would have to behave well for all links, and that's in fact the whole reason to have a dynamic frag queue timeout instead of a fixed one for all links. As long as the timeout is conservative without being so enormously so that it allows IP ID wrap, it shouldn't affect any existing use at all.

If the timeout were scaled to be only 10 (or 100!) times any reasonable expectation of success rather than thousands or tens of thousands of times too large, the problem wouldn't exist on fast links, and slow links would behave exactly as they do now.

I agree that NFS over UDP should be dead as soon as possible, and fragmentation in general not far behind it. They aren't quite dead yet; until they are, why not make them better behaved? And if your argument is that it isn't worth fixing because it isn't used, then of course the argument that it'll break slow links to change it doesn't fly. Sites obviously have fast links where this can break, and done correctly, this shouldn't affect slow links at all. People who don't use NFS over UDP aren't affected by it either way, right? :-)

                                                        +-DLS
#7 lore raw
Quoted 4 lines · On Thu, 15 Jul 2004 09:54:53 -0700 David Stevens <[email protected]> wrote:

I agree that NFS over UDP should be dead as soon as possible, and fragmentation in general not far behind it. They aren't quite dead yet; until they are, why not make them better behaved? And if your argument is that it isn't worth fixing because it isn't

I wouldn't go that far, just make extremly sure that any solution works on slow links too. The problem I see is that if you make the delay factor long enough to make the extremly variable links not regress you risk making the wrap on very fast links likely again.

-Andi

#8 lore raw
In reply to David Stevens
Quoted 5 lines

you'll reassemble garbage when the IP ID wraps (well before the frag queue expires). And the checksum will pass anyway on average about 1/64K of the time. If you send at full rate and drop, say, 100 frags a second, it doesn't take too long to get a Frankenpacket-- reassembled from parts of others. :-)

In the scenarios we were looking at, packet loss rate was fairly low. What compounded the problem was that the NFS payload wasn't very varied, so the UDP checksum distribution was far from even.

When we looked into the problem, we considered implementing a per-route parameter where the admin can set lower reassembly timeouts. I think this is a solution that both addresses the problem, and does not interfere with WAN traffic. The user space tools could even select reasonable defaults based on the hardware type when setting up the device.

(We did not implement this because we decided to go for NFS over TCP by default instead).

Quoted 8 lines
Quoted 3 lines

In general handling a link where the RTT increases would seem tricky with your scheme. Unlike TCP there is no retransmit to save the day.

In the particular case (NFS over UDP), there is both a retransmit (done by RPC) and significant loss rate to start with. As long as the time-out is conservative, I don't think this has to affect other cases significantly.

NFS isn't the only application making heavy use of UDP. Video and audio do so too, and these don't have retransmits. Granted, these should choose a paket size that is below the path MTU, but not all applications always do.

IMO an estimator such as you describe would need to be very sensitive to jitter in fragment latencies, and it may be fairly hard to find a solution that works from 802.11 up to 10GE. A per-route reassembly timeout is probably a lot less of a headache.

Olaf

Signature · 3 lines
Olaf Kirch     |  The Hardware Gods hate me.
[email protected]   |
---------------+