Skip to contentSkip to conversation

Fix BUG of ip_rt_send_redirect()

PATCH In review Li Yewang 4 participants 6 messages Nov 17, 2006 – Nov 29, 2006

Subsystems (3)
Networking Network drivers IPv4/IPv6
lore
Share & tools
lore

Li Yewang

author
#0 lore raw

PATCH 1/1 Fix BUG of ip_rt_send_redirect()

[1]Summary of the problem:
On IA32 system, If jiffies - b > 0x7fffffff, router can not send redirect packet.unsigned long b = rt->u.dst.rate_last +(ip_rt_redirect_load << rt->u.dst.rate_tokens)

[2]Full description of the problem:
In linux kernel, if time_after(jiffies, (rt->u.dst.rate_last +(ip_rt_redirect_load << rt->u.dst.rate_tokens)) == false, router will not send redirect packet. Here define b = rt-

Quoted 1 line

u.dst.rate_last +(ip_rt_redirect_load << rt->u.dst.rate_tokens):

1. If (jiffies - b <= 0x7fffffff), time_after(jiffies, b) == true, router will send redirect packet.

2. If (jiffies - b > 0x7fffffff), time_after(jiffies, b) == false, router will not send redirect packet. For example: when I add a router after system boot, jiffies = (unsigned long)(-300000), rt->u.dst.rate_last = 0, rt->u.dst.rate_tokens = 0, b = 20, time_after((unsigned long)(-300000), 20) == false, send redirect packet can not be send even if router is used in the first time.

When router send a redirect packet in time b, and before jiffies increased to 0x7fffffff + b, router can send redirect packet. But if a redirect packet must be send in 0x80000000+ b, time_after(jiffies, b) == false, redirect packet will not be send also. So between time (0x80000000+ b) to time b, router do not send redirect packet. That is to say, in a circle of jiffies, router has 24.9 days can not send redirect packet (0x80000000/1000/60/60/24=24.9).

jiffies b

------|------------------------------|----------------------|---->time
 0x80000000+b                        b                0x7fffffff+b
      |<--jiffies - b < 0x7fffffff-->|

Following is my patch.

Signed-off-by Li Yewang <[email protected]>
net/ipv4/route.c renamed from net/ipv4/route.c.org +4 -2
@@ -1196,7 +1196,8 @@ void ip_rt_send_redirect(struct sk_buff 
 	/* No redirected packets during ip_rt_redirect_silence;
 	 * reset the algorithm.
 	 */
-	if (time_after(jiffies, rt->u.dst.rate_last + ip_rt_redirect_silence)
+	if (time_after(jiffies, rt->u.dst.rate_last + ip_rt_redirect_silence) ||
+	    time_after(rt->u.dst.rate_last, jiffies))
 		rt->u.dst.rate_tokens = 0;
 
 	/* Too many ignored redirects; do not send anything

@@ -1212,7 +1213,8 @@ void ip_rt_send_redirect(struct sk_buff 
 	 */
 	if (time_after(jiffies,
 		       (rt->u.dst.rate_last +
-			(ip_rt_redirect_load << rt->u.dst.rate_tokens)))) {
+			(ip_rt_redirect_load << rt->u.dst.rate_tokens))) ||
+	    time_after(rt->u.dst.rate_last, jiffies)) {
 		icmp_send(skb, ICMP_REDIRECT, ICMP_REDIR_HOST, rt->rt_gateway);
 		rt->u.dst.rate_last = jiffies;
 		++rt->u.dst.rate_tokens;
#1 lore raw
Quoted 54 lines · On Thu, 16 Nov 2006 23:57:50 -0500 Li Yewang <[email protected]> wrote:

[1]Summary of the problem:
On IA32 system, If jiffies - b > 0x7fffffff, router can not send redirect packet.unsigned long b = rt->u.dst.rate_last +(ip_rt_redirect_load << rt->u.dst.rate_tokens)

[2]Full description of the problem:
In linux kernel, if time_after(jiffies, (rt->u.dst.rate_last +(ip_rt_redirect_load << rt->u.dst.rate_tokens)) == false, router will not send redirect packet. Here define b = rt-

Quoted 1 line

u.dst.rate_last +(ip_rt_redirect_load << rt->u.dst.rate_tokens):

1. If (jiffies - b <= 0x7fffffff), time_after(jiffies, b) == true, router will send redirect packet.

2. If (jiffies - b > 0x7fffffff), time_after(jiffies, b) == false, router will not send redirect packet. For example: when I add a router after system boot, jiffies = (unsigned long)(-300000), rt->u.dst.rate_last = 0, rt->u.dst.rate_tokens = 0, b = 20, time_after((unsigned long)(-300000), 20) == false, send redirect packet can not be send even if router is used in the first time.

When router send a redirect packet in time b, and before jiffies increased to 0x7fffffff + b, router can send redirect packet. But if a redirect packet must be send in 0x80000000+ b, time_after(jiffies, b) == false, redirect packet will not be send also. So between time (0x80000000+ b) to time b, router do not send redirect packet. That is to say, in a circle of jiffies, router has 24.9 days can not send redirect packet (0x80000000/1000/60/60/24=24.9).

jiffies b

------|------------------------------|----------------------|---->time
 0x80000000+b                        b                0x7fffffff+b
      |<--jiffies - b < 0x7fffffff-->|

Following is my patch.

Signed-off-by Li Yewang <[email protected]>
net/ipv4/route.c renamed from net/ipv4/route.c.org +2 -1
@@ -1196,7 +1196,8 @@ void ip_rt_send_redirect(struct sk_buff 
 	/* No redirected packets during ip_rt_redirect_silence;
 	 * reset the algorithm.
 	 */
-	if (time_after(jiffies, rt->u.dst.rate_last + ip_rt_redirect_silence)
+	if (time_after(jiffies, rt->u.dst.rate_last + ip_rt_redirect_silence) ||
+	    time_after(rt->u.dst.rate_last, jiffies))
 		rt->u.dst.rate_tokens = 0;
 
 	/* Too many ignored redirects; do not send anything

net/ipv4/route.c void ip_rt_send_redirect(struct sk_buff · line 1220

Quoted 9 lines
net/ipv4/route.c renamed from net/ipv4/route.c.org +2 -1
@@ -1212,7 +1213,8 @@ void ip_rt_send_redirect(struct sk_buff 
 	 */
 	if (time_after(jiffies,
 		       (rt->u.dst.rate_last +
-			(ip_rt_redirect_load << rt->u.dst.rate_tokens)))) {
+			(ip_rt_redirect_load << rt->u.dst.rate_tokens))) ||
+	    time_after(rt->u.dst.rate_last, jiffies)) {
 		icmp_send(skb, ICMP_REDIRECT, ICMP_REDIR_HOST, rt->rt_gateway);
 		rt->u.dst.rate_last = jiffies;
 		++rt->u.dst.rate_tokens;

Wouldn't making ip_rt_redirect_load and other unsigned long instead of int fix the problem?

Remember time_after() works correctly for values that wraparound.

#2 lore raw
Quoted 32 lines · Stephen Hemminger
Quoted 21 lines · On Thu, 16 Nov 2006 23:57:50 -0500 Li Yewang <[email protected]> wrote:

[1]Summary of the problem:
On IA32 system, If jiffies - b > 0x7fffffff, router can not send redirect packet.unsigned long b = rt->u.dst.rate_last +(ip_rt_redirect_load << rt->u.dst.rate_tokens)

[2]Full description of the problem:
In linux kernel, if time_after(jiffies, (rt->u.dst.rate_last +(ip_rt_redirect_load << rt->u.dst.rate_tokens)) == false, router will not send redirect packet. Here define b = rt-

Quoted 1 line

u.dst.rate_last +(ip_rt_redirect_load << rt->u.dst.rate_tokens):

1. If (jiffies - b <= 0x7fffffff), time_after(jiffies, b) == true, router will send redirect packet.

2. If (jiffies - b > 0x7fffffff), time_after(jiffies, b) == false, router will not send redirect packet. For example: when I add a router after system boot, jiffies = (unsigned long)(-300000), rt->u.dst.rate_last = 0, rt->u.dst.rate_tokens = 0, b = 20, time_after((unsigned long)(-300000), 20) == false, send redirect packet can not be send even if router is used in the first time.

Quoted 7 lines

When router send a redirect packet in time b, and before jiffies increased to 0x7fffffff + b, router can send redirect packet. But if a redirect packet must be send in 0x80000000+ b, time_after(jiffies, b) == false, redirect packet will not be send also. So between time (0x80000000+ b) to time b, router do not send redirect packet. That is to say, in a circle of jiffies, router has 24.9 days can not send redirect packet (0x80000000/1000/60/60/24=24.9).

Quoted 3 lines

Wouldn't making ip_rt_redirect_load and other unsigned long instead of int fix the problem?

Remember time_after() works correctly for values that wraparound.

Yes, time_after() works correctly for values that wraparound. For examples: if time a = (unsigned long)(-1), and time b = 1; time_after(b, a) = true. But if a is increaseing, after a circle of jiffies, a' = a + (unsigned long)(-1) + 1 = (unsigned long)(-1) = a,
this time a' is after b, but time_after(b, a') still equal to true,because values that wraparound can not be making in time_after().

Regards

#3 lore raw
Quoted 7 lines · Wei Yongjun

Yes, time_after() works correctly for values that wraparound. For examples: if time a = (unsigned long)(-1), and time b = 1; time_after(b, a) = true. But if a is increaseing, after a circle of jiffies, a' = a + (unsigned long)(-1)
+ 1 = (unsigned long)(-1) = a,
this time a' is after b, but time_after(b, a') still equal to true,because values that wraparound can not be making in time_after().

I think there are two problems here:

1) The first time we hit the check rate_last is zero. We should simply proceed with the redirect rather than treating this as a jiffies value.

2) When a dst is so old that the jiffies have wrapped around. I'm not sure whether this is worth solving as it should be extremely rare unless your HZ is sufficiently large and you're on a 32-bit platform.

One solution would be to periodically reset the rate_last fields to their original states. Perhaps we can combine that with the GC.

Cheers,

Signature · 4 lines
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
author
#4 lore raw

Yes, the first time when router want to send redirect packet, We should send the redirect packet simply and do not regard the jiffies. But the kernel has bugs as follow:
1.The kernel can not send the redirect packet at the begin 5 minutes
when the system boot(32bit machine).

2.In a circle of jiffies, router has 24.9 days can not send redirect packet.

I think my patch can solve the bugs.

Quoted 23 lines · Herbert Xu

I think there are two problems here:

1) The first time we hit the check rate_last is zero. We should simply proceed with the redirect rather than treating this as a jiffies value.

2) When a dst is so old that the jiffies have wrapped around. I'm not sure whether this is worth solving as it should be extremely rare unless your HZ is sufficiently large and you're on a 32-bit platform.

One solution would be to periodically reset the rate_last fields to their original states. Perhaps we can combine that with the GC.

Cheers,

Signature · 8 lines
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
-
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
author
#5 lore raw
In reply to Herbert Xu
Quoted 5 lines · Herbert Xu [email protected] wrote:

I think there are two problems here:

1) The first time we hit the check rate_last is zero. We should simply proceed with the redirect rather than treating this as a jiffies value.

Quoted 8 lines

2) When a dst is so old that the jiffies have wrapped around. I'm not sure whether this is worth solving as it should be extremely rare unless your HZ is sufficiently large and you're on a 32-bit platform.

One solution would be to periodically reset the rate_last fields to their original states. Perhaps we can combine that with the GC.

Cheers,

Mr Herbert Xu

Sorry for later reply

I have some questions about your advice:
1) If the first time when we send the redirect packets, but the time_after(jiffies, b)==false. So the redirect packets can not be sended.
This situation happens when the system of 32-bit boot on less than 5 minutes. This must be the kernel bug.

2) If the router used frequently, the garbage collect function can not free this dst. Next time when we want this router to send redirect packets, and if the jiffies wraparound and time_after(jiffies,b)==false, the redirect packets can not be sended. So we must consider this situation and solve this problem.

Quoted 9 lines

Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]> Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
-
To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html