[PATCH]Fix BUG of ip_rt_send_redirect()

[PATCH]Fix BUG of ip_rt_send_redirect()

[Li Yewang]

[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-
>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 <lyw@nanjing-fnst.com>

--- linux-2.6.9/net/ipv4/route.c.org	2006-11-16 08:49:48.000000000 +0800
+++ linux-2.6.9/net/ipv4/route.c	2006-11-16 08:51:30.000000000 +0800
@@ -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;

Re: [PATCH]Fix BUG of ip_rt_send_redirect()

[Stephen Hemminger]

On Thu, 16 Nov 2006 23:57:50 -0500
Li Yewang <lyw@nanjing-fnst.com> 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-
> >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 <lyw@nanjing-fnst.com>
> 
> --- linux-2.6.9/net/ipv4/route.c.org	2006-11-16 08:49:48.000000000 +0800
> +++ linux-2.6.9/net/ipv4/route.c	2006-11-16 08:51:30.000000000 +0800
> @@ -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;
> 
>

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. 

Re: [PATCH]Fix BUG of ip_rt_send_redirect()

[Wei Yongjun]

On Friday, November 17, 2006 11:51 AM
Stephen Hemminger <shemminger@osdl.org> wrote:

> On Thu, 16 Nov 2006 23:57:50 -0500
> Li Yewang <lyw@nanjing-fnst.com> 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-
>> >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).
>
> 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 

Re: [PATCH]Fix BUG of ip_rt_send_redirect()

[Herbert Xu]

Wei Yongjun <yjwei@nanjing-fnst.com> wrote:
> 
> 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,
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH]Fix BUG of ip_rt_send_redirect()

[Li Yewang]

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.



Herbert Xu <herbert@gondor.apana.org.au> 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.
> 
> 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,
> -- 
> Visit Openswan at http://www.openswan.org/
> Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
> 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 majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>

Re: [PATCH]Fix BUG of ip_rt_send_redirect()

[Li Yewang]

Herbert Xu herbert@gondor.apana.org.au 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.
> 
> 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.
        

> Visit Openswan at http://www.openswan.org/
> Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
> 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 majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>

Re:[PATCH]Fix BUG of ip_rt_send_redirect()

[Li Yewang]

Herbert Xu <herbert@gondor.apana.org.au> 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.
> 
>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.


Mr Herbert Xu:

According to your advice, I have made another patch for the redirect
bug.

This patch does not think of the jiffies wraparound any more.
Because if the router sends a redirect packet for the first time,
the redirect route cache entry will be created in the route cache.
If this entry is used frequently(This should be extremely rare), 
the rate_last will be update to the current jiffies when it sends 
the redirect packet. So we don't concern about the jiffies wraparound.
If this entry does not be used for a long time, the GC will remove 
it from route cache. Next time if we want to use this entry, 
the redirect entry will be created in the route cache again, and the
rate_last will be initialized to 0. So we don't care of the jiffies
wraparound too.


Following is my patch:

Signed-off-by: Li Yewang <lyw@nanjing-fnst.com>

--- linux-2.6.19/net/ipv4/route.c.org 2006-12-05 10:47:02.402147160
+0800
+++ linux-2.6.19/net/ipv4/route.c 2006-12-05 10:48:26.339386760 +0800
@@ -1327,7 +1327,8 @@ void ip_rt_send_redirect(struct sk_buff 
  /* Check for load limit; set rate_last to the latest sent
   * redirect.
   */
- if (time_after(jiffies,
+ if (rt->u.dst.rate_last == 0 ||
+     time_after(jiffies,
          (rt->u.dst.rate_last +
    (ip_rt_redirect_load << rt->u.dst.rate_tokens)))) {
   icmp_send(skb, ICMP_REDIRECT, ICMP_REDIR_HOST, rt->rt_gateway);


To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH]Fix BUG of ip_rt_send_redirect()

[Herbert Xu]

On Wed, Nov 29, 2006 at 04:08:45PM +0800, Li Yewang wrote:
> 
> --- linux-2.6.19/net/ipv4/route.c.org 2006-12-05 10:47:02.402147160
> +0800
> +++ linux-2.6.19/net/ipv4/route.c 2006-12-05 10:48:26.339386760 +0800
> @@ -1327,7 +1327,8 @@ void ip_rt_send_redirect(struct sk_buff 
>   /* Check for load limit; set rate_last to the latest sent
>    * redirect.
>    */
> - if (time_after(jiffies,
> + if (rt->u.dst.rate_last == 0 ||
> +     time_after(jiffies,
>           (rt->u.dst.rate_last +
>     (ip_rt_redirect_load << rt->u.dst.rate_tokens)))) {
>    icmp_send(skb, ICMP_REDIRECT, ICMP_REDIR_HOST, rt->rt_gateway);

Since rate_last can also be zero if jiffies == 0 (OK that's
extremely unlikely but I'm feeling picky today :), how about
checking rate_tokens instead? The value of rate_last can only
be relevant if rate_tokens is non-zero.

BTW, please also check the other spots where rate_last/rate_token
is used.  They might need a similar fix.

Cheers,
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re:[PATCH]Fix BUG of ip_rt_send_redirect()

[Li Yewang]

Herbert Xu <herbert@gondor.apana.org.au> wrote:

> 
> Since rate_last can also be zero if jiffies == 0 (OK that's
> extremely unlikely but I'm feeling picky today :), how about
> checking rate_tokens instead? The value of rate_last can only
> be relevant if rate_tokens is non-zero.
> 
> BTW, please also check the other spots where rate_last/rate_token
> is used.  They might need a similar fix.
> 
> Cheers,

Mr Herbert Xu

According to your advice, I have made another patch for the redirect
bug.

I have also checked other spots where rate_last/rate_tokens is used.
Those places need not be fixed.

Following is my patch:

signed-off-by: Li Yewang<lyw@nanjing-fnst.com>

--- linux-2.6.19.1/net/ipv4/route.c     2006-12-12 03:32:54.000000000
+0800
+++ linux-2.6.19.1/net/ipv4/route.org.c 2006-11-29 16:14:34.592058480
+0800
@@ -1327,7 +1327,8 @@ void ip_rt_send_redirect(struct sk_buff
        /* Check for load limit; set rate_last to the latest sent
         * redirect.
         */
-       if (time_after(jiffies,
+       if (rt->u.dst.rate_tokens == 0 ||
+            time_after(jiffies,
                       (rt->u.dst.rate_last +
                        (ip_rt_redirect_load << rt-
>u.dst.rate_tokens)))) {
                icmp_send(skb, ICMP_REDIRECT, ICMP_REDIR_HOST, rt-
>rt_gateway);

Re: [PATCH]Fix BUG of ip_rt_send_redirect()

[Herbert Xu]

On Wed, Nov 29, 2006 at 04:51:31PM +0800, Li Yewang wrote:
> 
> I have also checked other spots where rate_last/rate_tokens is used.
> Those places need not be fixed.

Thanks.

> Following is my patch:
> 
> signed-off-by: Li Yewang<lyw@nanjing-fnst.com>

Looks good to me.  You should cc David Miller <davem@davemloft.net>
for patch submissions.  Please also include a full description each
time you submit the patch.

> --- linux-2.6.19.1/net/ipv4/route.c     2006-12-12 03:32:54.000000000
> +0800
> +++ linux-2.6.19.1/net/ipv4/route.org.c 2006-11-29 16:14:34.592058480
> +0800
> @@ -1327,7 +1327,8 @@ void ip_rt_send_redirect(struct sk_buff
>         /* Check for load limit; set rate_last to the latest sent
>          * redirect.
>          */
> -       if (time_after(jiffies,
> +       if (rt->u.dst.rate_tokens == 0 ||
> +            time_after(jiffies,
>                        (rt->u.dst.rate_last +
>                         (ip_rt_redirect_load << rt-
> >u.dst.rate_tokens)))) {
>                 icmp_send(skb, ICMP_REDIRECT, ICMP_REDIR_HOST, rt-
> >rt_gateway);

Cheers,
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re:[PATCH]Fix BUG of ip_rt_send_redirect()

[Li Yewang]

David Miller <davem@davemloft.net> wrote:

> Applied, but I had to fix many errors in your patch by hand.
> Please take care of these details next time.
> 
> Here, your email client wrapped the lines in the patch, corrupting it.
> 
> Please use real tab characters, when necessary, in the indentation of
> new code lines that you add, not just spaces.
> 
> Thank you.

Mr David Miller

I have made another patch file about the ip_rt_send_redirect().
This patch has not wrapped lines, and can be patched into the kernel.

Following is my patch:

signed-off-by: Li Yewang <lyw@nanjing-fnst.com>

--- a/net/ipv4/route.org.c	2006-12-19 09:22:16.260271000 +0800
+++ a/net/ipv4/route.c	2006-12-19 09:22:16.241273888 +0800
@@ -1327,7 +1327,8 @@ void ip_rt_send_redirect(struct sk_buff 
 	/* Check for load limit; set rate_last to the latest sent
 	 * redirect.
 	 */
-	if (time_after(jiffies,
+	if (rt->u.dst.rate_tokens == 0 ||
+	    time_after(jiffies,
 		       (rt->u.dst.rate_last +
 			(ip_rt_redirect_load << rt->u.dst.rate_tokens)))) {
 		icmp_send(skb, ICMP_REDIRECT, ICMP_REDIR_HOST, rt->rt_gateway);

Re: [PATCH]Fix BUG of ip_rt_send_redirect()

[David Miller]

From: Li Yewang <lyw@nanjing-fnst.com>
Date: Tue, 19 Dec 2006 09:45:25 +0800

> David Miller <davem@davemloft.net> wrote:
> 
> > Applied, but I had to fix many errors in your patch by hand.
> > Please take care of these details next time.
> > 
> > Here, your email client wrapped the lines in the patch, corrupting it.
> > 
> > Please use real tab characters, when necessary, in the indentation of
> > new code lines that you add, not just spaces.
> > 
> > Thank you.
> 
> Mr David Miller
> 
> I have made another patch file about the ip_rt_send_redirect().
> This patch has not wrapped lines, and can be patched into the kernel.
> 
> Following is my patch:
> 
> signed-off-by: Li Yewang <lyw@nanjing-fnst.com>

I said I already fixed the patch up for you when I applied
it, you didn't need to redo it.