[PATCH-2.4] Fix divide by 0 in vegas_cong_avoid()

[PATCH-2.4] Fix divide by 0 in vegas_cong_avoid()

[Lior Dotan]

Hi,

I had a divide by zero on kernel 2.4.33 running with Vegas enabled.
The KDB back trace is:
kdb> bt
Stack traceback for pid 0
0x403a6000        0        0  1    0   R  0x403a6370 *swapper
EBP        EIP        Function (args)
0x403a7d48 0x4026ae51 vegas_cong_avoid+0x111 (0x5f3bb638, 0x73c92cbb, 0xffffffff
, 0x73c92cbb, 0xf28d0275)
                               kernel .text 0x40100000 0x4026ad40 0x4026aef0
0x403a7d8c 0x4026bb67 tcp_ack+0x307 (0x5f3bb560, 0x581985c0, 0x18e, 0x4023e765,
0x5c369044)
                               kernel .text 0x40100000 0x4026b860 0x4026be20
0x403a7ddc 0x4026e771 tcp_rcv_established+0x461 (0x5f3bb560, 0x581985c0, 0x5c369
044, 0x2c, 0x5f3bb638)
                               kernel .text 0x40100000 0x4026e310 0x4026ed80
0x403a7e00 0x40277c2f tcp_v4_do_rcv+0x14f (0x5f3bb560, 0x581985c0, 0x0, 0x403a7e
50, 0x4024bb42)
                               kernel .text 0x40100000 0x40277ae0 0x40277c40
<Rest was cut for readability>
What happens is that vegas_rtt_calc() gets rtt as -1, so when it adds
1 the rtt is set to zero.
It seems that the -1 came from tcp_clean_rtx_queue() so I made this
small patch to fix the problem. I think it is also relevant to 2.6.


Don't perform congestion avoidance on packets that we didn't calculate
there RTT, as this may result in a divide by zero later on.

Signed-off-by: Lior Dotan <liodot@gmail.com>
---

diff -up net/ipv4/tcp_input.c.orig net/ipv4/tcp_input.c
--- net/ipv4/tcp_input.c.orig   2007-05-29 11:43:37.000000000 +0300
+++ net/ipv4/tcp_input.c        2007-05-29 11:20:21.000000000 +0300
@@ -2425,6 +2424,7 @@ static int tcp_clean_rtx_queue(struct so
                                        tp->retrans_out--;
                                acked |= FLAG_RETRANS_DATA_ACKED;
                                seq_rtt = -1;
+                               acked &= ~FLAG_DATA_ACKED;
                        } else if (seq_rtt < 0)
                                seq_rtt = now - scb->when;
                        if(sacked & TCPCB_SACKED_ACKED)

Re: [PATCH-2.4] Fix divide by 0 in vegas_cong_avoid()

[Stephen Hemminger]

On Tue, 29 May 2007 12:18:19 +0300
"Lior Dotan" <liodot@gmail.com> wrote:

> Hi,
> 
> I had a divide by zero on kernel 2.4.33 running with Vegas enabled.
> The KDB back trace is:
> kdb> bt
> Stack traceback for pid 0
> 0x403a6000        0        0  1    0   R  0x403a6370 *swapper
> EBP        EIP        Function (args)
> 0x403a7d48 0x4026ae51 vegas_cong_avoid+0x111 (0x5f3bb638, 0x73c92cbb, 0xffffffff
> , 0x73c92cbb, 0xf28d0275)
>                                kernel .text 0x40100000 0x4026ad40 0x4026aef0
> 0x403a7d8c 0x4026bb67 tcp_ack+0x307 (0x5f3bb560, 0x581985c0, 0x18e, 0x4023e765,
> 0x5c369044)
>                                kernel .text 0x40100000 0x4026b860 0x4026be20
> 0x403a7ddc 0x4026e771 tcp_rcv_established+0x461 (0x5f3bb560, 0x581985c0, 0x5c369
> 044, 0x2c, 0x5f3bb638)
>                                kernel .text 0x40100000 0x4026e310 0x4026ed80
> 0x403a7e00 0x40277c2f tcp_v4_do_rcv+0x14f (0x5f3bb560, 0x581985c0, 0x0, 0x403a7e
> 50, 0x4024bb42)
>                                kernel .text 0x40100000 0x40277ae0 0x40277c40
> <Rest was cut for readability>
> What happens is that vegas_rtt_calc() gets rtt as -1, so when it adds
> 1 the rtt is set to zero.
> It seems that the -1 came from tcp_clean_rtx_queue() so I made this
> small patch to fix the problem. I think it is also relevant to 2.6.


Seems like fixing the -1 would be better.  Perhaps NTP reset
the clock?

> 
> Don't perform congestion avoidance on packets that we didn't calculate
> there RTT, as this may result in a divide by zero later on.
> 
> Signed-off-by: Lior Dotan <liodot@gmail.com>
> ---
> 
> diff -up net/ipv4/tcp_input.c.orig net/ipv4/tcp_input.c
> --- net/ipv4/tcp_input.c.orig   2007-05-29 11:43:37.000000000 +0300
> +++ net/ipv4/tcp_input.c        2007-05-29 11:20:21.000000000 +0300
> @@ -2425,6 +2424,7 @@ static int tcp_clean_rtx_queue(struct so
>                                         tp->retrans_out--;
>                                 acked |= FLAG_RETRANS_DATA_ACKED;
>                                 seq_rtt = -1;
> +                               acked &= ~FLAG_DATA_ACKED;
>                         } else if (seq_rtt < 0)
>                                 seq_rtt = now - scb->when;
>                         if(sacked & TCPCB_SACKED_ACKED)
> -
> 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


-- 
Stephen Hemminger <shemminger@linux-foundation.org>

Re: [PATCH-2.4] Fix divide by 0 in vegas_cong_avoid()

[Lior Dotan]

NTP was not running. I'm not sure what do you mean by fixing the -1.
The trace shows that vegas_cong_avoid() is called with -1, and the
only way it can happen is from tcp_clean_rtx_queue() and the patch
should eliminate this. Another way of solving this is by checking
vegas_rtt_calc() and see if it gets -1 and handle it there.
Another thing that I don't understand is that some places like
tcp_ack() declare seq_rtt as signed and some vegas_cong_avoid()
declare it as unsigned. Shouldn't it be declared always as signed?

On 5/29/07, Stephen Hemminger <shemminger@linux-foundation.org> wrote:
> On Tue, 29 May 2007 12:18:19 +0300
> "Lior Dotan" <liodot@gmail.com> wrote:
>
> > Hi,
> >
> > I had a divide by zero on kernel 2.4.33 running with Vegas enabled.
> > The KDB back trace is:
> > kdb> bt
> > Stack traceback for pid 0
> > 0x403a6000        0        0  1    0   R  0x403a6370 *swapper
> > EBP        EIP        Function (args)
> > 0x403a7d48 0x4026ae51 vegas_cong_avoid+0x111 (0x5f3bb638, 0x73c92cbb, 0xffffffff
> > , 0x73c92cbb, 0xf28d0275)
> >                                kernel .text 0x40100000 0x4026ad40 0x4026aef0
> > 0x403a7d8c 0x4026bb67 tcp_ack+0x307 (0x5f3bb560, 0x581985c0, 0x18e, 0x4023e765,
> > 0x5c369044)
> >                                kernel .text 0x40100000 0x4026b860 0x4026be20
>
>
> Seems like fixing the -1 would be better.  Perhaps NTP reset
> the clock?
>
>
>
> --
> Stephen Hemminger <shemminger@linux-foundation.org>
>

Re: [PATCH-2.4] Fix divide by 0 in vegas_cong_avoid()

[Stephen Hemminger]

On Tue, 29 May 2007 12:18:19 +0300
"Lior Dotan" <liodot@gmail.com> wrote:

> Hi,
> 
> I had a divide by zero on kernel 2.4.33 running with Vegas enabled.
> The KDB back trace is:
> kdb> bt
> Stack traceback for pid 0
> 0x403a6000        0        0  1    0   R  0x403a6370 *swapper
> EBP        EIP        Function (args)
> 0x403a7d48 0x4026ae51 vegas_cong_avoid+0x111 (0x5f3bb638, 0x73c92cbb, 0xffffffff
> , 0x73c92cbb, 0xf28d0275)
>                                kernel .text 0x40100000 0x4026ad40 0x4026aef0
> 0x403a7d8c 0x4026bb67 tcp_ack+0x307 (0x5f3bb560, 0x581985c0, 0x18e, 0x4023e765,
> 0x5c369044)
>                                kernel .text 0x40100000 0x4026b860 0x4026be20
> 0x403a7ddc 0x4026e771 tcp_rcv_established+0x461 (0x5f3bb560, 0x581985c0, 0x5c369
> 044, 0x2c, 0x5f3bb638)
>                                kernel .text 0x40100000 0x4026e310 0x4026ed80
> 0x403a7e00 0x40277c2f tcp_v4_do_rcv+0x14f (0x5f3bb560, 0x581985c0, 0x0, 0x403a7e
> 50, 0x4024bb42)
>                                kernel .text 0x40100000 0x40277ae0 0x40277c40
> <Rest was cut for readability>
> What happens is that vegas_rtt_calc() gets rtt as -1, so when it adds
> 1 the rtt is set to zero.
> It seems that the -1 came from tcp_clean_rtx_queue() so I made this
> small patch to fix the problem. I think it is also relevant to 2.6.
> 
> 
> Don't perform congestion avoidance on packets that we didn't calculate
> there RTT, as this may result in a divide by zero later on.
> 
> Signed-off-by: Lior Dotan <liodot@gmail.com>
> ---
> 
> diff -up net/ipv4/tcp_input.c.orig net/ipv4/tcp_input.c
> --- net/ipv4/tcp_input.c.orig   2007-05-29 11:43:37.000000000 +0300
> +++ net/ipv4/tcp_input.c        2007-05-29 11:20:21.000000000 +0300
> @@ -2425,6 +2424,7 @@ static int tcp_clean_rtx_queue(struct so
>                                         tp->retrans_out--;
>                                 acked |= FLAG_RETRANS_DATA_ACKED;
>                                 seq_rtt = -1;
> +                               acked &= ~FLAG_DATA_ACKED;
>                         } else if (seq_rtt < 0)
>                                 seq_rtt = now - scb->when;
>                         if(sacked & TCPCB_SACKED_ACKED)
> -

The proposed fix for TSO and packets acked callback will fix this as well.
Your fix makes sense for kernels < 2.6.22, but with 2.6.22 this would
fix it:
	http://article.gmane.org/gmane.linux.network/63101

-- 
Stephen Hemminger <shemminger@linux-foundation.org>

Re: [PATCH-2.4] Fix divide by 0 in vegas_cong_avoid()

[Stephen Hemminger]

On Tue, 29 May 2007 20:23:45 +0200
"Lior Dotan" <liodot@gmail.com> wrote:

> NTP was not running. I'm not sure what do you mean by fixing the -1.
> The trace shows that vegas_cong_avoid() is called with -1, and the
> only way it can happen is from tcp_clean_rtx_queue() and the patch
> should eliminate this. Another way of solving this is by checking
> vegas_rtt_calc() and see if it gets -1 and handle it there.
> Another thing that I don't understand is that some places like
> tcp_ack() declare seq_rtt as signed and some vegas_cong_avoid()
> declare it as unsigned. Shouldn't it be declared always as signed?
> 
> On 5/29/07, Stephen Hemminger <shemminger@linux-foundation.org> wrote:
> > On Tue, 29 May 2007 12:18:19 +0300
> > "Lior Dotan" <liodot@gmail.com> wrote:
> >
> > > Hi,
> > >
> > > I had a divide by zero on kernel 2.4.33 running with Vegas enabled.

I don't think anyone has backported the other vegas fixes from 2.6.21
to 2.4.

> > > The KDB back trace is:
> > > kdb> bt
> > > Stack traceback for pid 0
> > > 0x403a6000        0        0  1    0   R  0x403a6370 *swapper
> > > EBP        EIP        Function (args)
> > > 0x403a7d48 0x4026ae51 vegas_cong_avoid+0x111 (0x5f3bb638, 0x73c92cbb, 0xffffffff
> > > , 0x73c92cbb, 0xf28d0275)
> > >                                kernel .text 0x40100000 0x4026ad40 0x4026aef0
> > > 0x403a7d8c 0x4026bb67 tcp_ack+0x307 (0x5f3bb560, 0x581985c0, 0x18e, 0x4023e765,
> > > 0x5c369044)
> > >                                kernel .text 0x40100000 0x4026b860 0x4026be20
> >
> >
> > Seems like fixing the -1 would be better.  Perhaps NTP reset
> > the clock?
> >
> >
> >
> > --
> > Stephen Hemminger <shemminger@linux-foundation.org>
> >

For 2.6.22, rtt_calc doesn't exist, instead pkts_acked is called. The following
should be added to avoid getting bogus timestamp values from retransmits.

--- a/net/ipv4/tcp_vegas.c	2007-05-02 12:26:35.000000000 -0700
+++ b/net/ipv4/tcp_vegas.c	2007-05-29 14:06:26.000000000 -0700
@@ -117,6 +117,10 @@ void tcp_vegas_pkts_acked(struct sock *s
 	struct vegas *vegas = inet_csk_ca(sk);
 	u32 vrtt;
 
+	/* Ignore retransmits */
+	if (unlikely(cnt == 0))
+		return;
+
 	/* Never allow zero rtt or baseRTT */
 	vrtt = ktime_to_us(net_timedelta(last)) + 1;
 


-- 
Stephen Hemminger <shemminger@linux-foundation.org>

Re: [PATCH-2.4] Fix divide by 0 in vegas_cong_avoid()

[Ilpo Järvinen]

On Tue, 29 May 2007, Stephen Hemminger wrote:

> On Tue, 29 May 2007 20:23:45 +0200
> "Lior Dotan" <liodot@gmail.com> wrote:
> 
> > NTP was not running. I'm not sure what do you mean by fixing the -1.
> > The trace shows that vegas_cong_avoid() is called with -1, and the
> > only way it can happen is from tcp_clean_rtx_queue() and the patch
> > should eliminate this. Another way of solving this is by checking
> > vegas_rtt_calc() and see if it gets -1 and handle it there.
> > Another thing that I don't understand is that some places like
> > tcp_ack() declare seq_rtt as signed and some vegas_cong_avoid()
> > declare it as unsigned. Shouldn't it be declared always as signed?
> > 
> > On 5/29/07, Stephen Hemminger <shemminger@linux-foundation.org> wrote:
> > > On Tue, 29 May 2007 12:18:19 +0300
> > > "Lior Dotan" <liodot@gmail.com> wrote:
> > >
> > > > Hi,
> > > >
> > > > I had a divide by zero on kernel 2.4.33 running with Vegas enabled.
> 
> I don't think anyone has backported the other vegas fixes from 2.6.21
> to 2.4.
> 
> 
> For 2.6.22, rtt_calc doesn't exist, instead pkts_acked is called.

I tried to figure this one out yesterday, and it seems to me that divide 
by zero should not occur with 2.6.22 (nor with 2.6.21 code), no matter
how I try to approach vegas...

> The following should be added to avoid getting bogus timestamp values 
> from retransmits.

...but this is unreliable timestamps problem is a real one that originates 
from API merge commit 164891aadf1721fca4dce473bb0e0998181537c6 of yours 
(see some though about it below). I suppose there are now similar concerns 
about timestamp validity in other cc modules than vegas too.

> --- a/net/ipv4/tcp_vegas.c	2007-05-02 12:26:35.000000000 -0700
> +++ b/net/ipv4/tcp_vegas.c	2007-05-29 14:06:26.000000000 -0700
> @@ -117,6 +117,10 @@ void tcp_vegas_pkts_acked(struct sock *s
>  	struct vegas *vegas = inet_csk_ca(sk);
>  	u32 vrtt;
>  
> +	/* Ignore retransmits */
> +	if (unlikely(cnt == 0))
> +		return;
> +
>  	/* Never allow zero rtt or baseRTT */
>  	vrtt = ktime_to_us(net_timedelta(last)) + 1;

...I don't think this works, because cnt won't be zero ever because to 
make the call some skbs were cleaned from the queue (isn't that what 
pkts_acked stands for?). There is as if (acked&FLAG_ACKED) guard before 
making the pkts_acked call to cc modules, thus delta in packets_out will 
always be greater than 0. Hmm, now that I realize this, I would say that
checks for > 0 in pkts_acked are entirely bogus (in the current code), 
hmm, that means I have more things to cleanup in tcp-2.6, at least, bic, 
cubic and westwood do them... :-).

I think the code did a right thing before your api merge, since it called 
rtt callback only if FLAG_RETRANS_DATA_ACKED was not set (and pkts_acked 
always), i.e., when TCP cannot know if it was the rexmission that 
triggered the cumulative ACK or any original transmission, no new RTT 
measurement should be made. Consider also the fact that, there might be a 
non rexmitted skb after rexmitted one, which Lior's patch doesn't do 
right way at all since the FLAG_DATA_ACKED would again get set (no 
div-by-zero would have occured then but an unreliable timestamp would
have been givento vegas in 2.4).

The number of packets that got cumulatively acked is never a right metric 
to measure whether the cumulative ACK originated from rexmitted skbs or 
not. ...Perhaps the FLAG_RETRANS_DATA_ACKED flag needs to be passed 
somehow to cc modules?


-- 
 i.

Re: [PATCH-2.4] Fix divide by 0 in vegas_cong_avoid()

[Stephen Hemminger]

On Wed, 30 May 2007 10:49:54 +0300 (EEST)
"Ilpo Järvinen" <ilpo.jarvinen@helsinki.fi> wrote:

> On Tue, 29 May 2007, Stephen Hemminger wrote:
> 
> > On Tue, 29 May 2007 20:23:45 +0200
> > "Lior Dotan" <liodot@gmail.com> wrote:
> > 
> > > NTP was not running. I'm not sure what do you mean by fixing the -1.
> > > The trace shows that vegas_cong_avoid() is called with -1, and the
> > > only way it can happen is from tcp_clean_rtx_queue() and the patch
> > > should eliminate this. Another way of solving this is by checking
> > > vegas_rtt_calc() and see if it gets -1 and handle it there.
> > > Another thing that I don't understand is that some places like
> > > tcp_ack() declare seq_rtt as signed and some vegas_cong_avoid()
> > > declare it as unsigned. Shouldn't it be declared always as signed?
> > > 
> > > On 5/29/07, Stephen Hemminger <shemminger@linux-foundation.org> wrote:
> > > > On Tue, 29 May 2007 12:18:19 +0300
> > > > "Lior Dotan" <liodot@gmail.com> wrote:
> > > >
> > > > > Hi,
> > > > >
> > > > > I had a divide by zero on kernel 2.4.33 running with Vegas enabled.
> > 
> > I don't think anyone has backported the other vegas fixes from 2.6.21
> > to 2.4.
> > 
> > 
> > For 2.6.22, rtt_calc doesn't exist, instead pkts_acked is called.
> 
> I tried to figure this one out yesterday, and it seems to me that divide 
> by zero should not occur with 2.6.22 (nor with 2.6.21 code), no matter
> how I try to approach vegas...
> 
> > The following should be added to avoid getting bogus timestamp values 
> > from retransmits.
> 
> ...but this is unreliable timestamps problem is a real one that originates 
> from API merge commit 164891aadf1721fca4dce473bb0e0998181537c6 of yours 
> (see some though about it below). I suppose there are now similar concerns 
> about timestamp validity in other cc modules than vegas too.
> 
> > --- a/net/ipv4/tcp_vegas.c	2007-05-02 12:26:35.000000000 -0700
> > +++ b/net/ipv4/tcp_vegas.c	2007-05-29 14:06:26.000000000 -0700
> > @@ -117,6 +117,10 @@ void tcp_vegas_pkts_acked(struct sock *s
> >  	struct vegas *vegas = inet_csk_ca(sk);
> >  	u32 vrtt;
> >  
> > +	/* Ignore retransmits */
> > +	if (unlikely(cnt == 0))
> > +		return;
> > +
> >  	/* Never allow zero rtt or baseRTT */
> >  	vrtt = ktime_to_us(net_timedelta(last)) + 1;
> 
> ...I don't think this works, because cnt won't be zero ever because to 
> make the call some skbs were cleaned from the queue (isn't that what 
> pkts_acked stands for?). There is as if (acked&FLAG_ACKED) guard before 
> making the pkts_acked call to cc modules, thus delta in packets_out will 
> always be greater than 0. Hmm, now that I realize this, I would say that
> checks for > 0 in pkts_acked are entirely bogus (in the current code), 
> hmm, that means I have more things to cleanup in tcp-2.6, at least, bic, 
> cubic and westwood do them... :-).
> 
> I think the code did a right thing before your api merge, since it called 
> rtt callback only if FLAG_RETRANS_DATA_ACKED was not set (and pkts_acked 
> always), i.e., when TCP cannot know if it was the rexmission that 
> triggered the cumulative ACK or any original transmission, no new RTT 
> measurement should be made. Consider also the fact that, there might be a 
> non rexmitted skb after rexmitted one, which Lior's patch doesn't do 
> right way at all since the FLAG_DATA_ACKED would again get set (no 
> div-by-zero would have occured then but an unreliable timestamp would
> have been givento vegas in 2.4).
> 
> The number of packets that got cumulatively acked is never a right metric 
> to measure whether the cumulative ACK originated from rexmitted skbs or 
> not. ...Perhaps the FLAG_RETRANS_DATA_ACKED flag needs to be passed 
> somehow to cc modules?
> 
> 

What about the mixed case where some retransmitted data and new
data was covered by one ack.  I would rather keep the merge, but think
about the cases more carefully.

-- 
Stephen Hemminger <shemminger@linux-foundation.org>

Re: [PATCH-2.4] Fix divide by 0 in vegas_cong_avoid()

[Ilpo Järvinen]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 2442 bytes --]

On Wed, 30 May 2007, Stephen Hemminger wrote:

> On Wed, 30 May 2007 10:49:54 +0300 (EEST)
> "Ilpo Järvinen" <ilpo.jarvinen@helsinki.fi> wrote:
> 
> > I think the code did a right thing before your api merge, since it called 
> > rtt callback only if FLAG_RETRANS_DATA_ACKED was not set (and pkts_acked 
> > always), i.e., when TCP cannot know if it was the rexmission that 
> > triggered the cumulative ACK or any original transmission, no new RTT 
> > measurement should be made. Consider also the fact that, there might be a 
> > non rexmitted skb after rexmitted one, which Lior's patch doesn't do 
> > right way at all since the FLAG_DATA_ACKED would again get set (no 
> > div-by-zero would have occured then but an unreliable timestamp would
> > have been givento vegas in 2.4).
> > 
> > The number of packets that got cumulatively acked is never a right metric 
> > to measure whether the cumulative ACK originated from rexmitted skbs or 
> > not. ...Perhaps the FLAG_RETRANS_DATA_ACKED flag needs to be passed 
> > somehow to cc modules?
> 
> What about the mixed case where some retransmitted data and new
> data was covered by one ack. 

Without timestamps TCP cannot do anything better than consider a
cumulative ACK that includes any ever retransmitted segment as
inaccurate timestamp. Like in tcp_ack_no_tstamp:

        if (flag & FLAG_RETRANS_DATA_ACKED)
                return;

...I think this same applies to cc modules as well. With timestamps 
things are another beast.

> I would rather keep the merge, but think about the cases more
> carefully.

IMHO there's no problem with keeping the merge, you just need to add 
another parameter to pkts_acked (or by some other means indicate it) to 
distinguish RTT measurement with accurate timestamp from inaccurate ones. 
Maybe the first step (to 2.6.22 to avoid new bugs etc.) should be just to 
give the flag (for some funny reason, it's called "acked" in 
tcp_clean_rtx_queue) or use a single arg with 0/1 value fo depending on 
FLAG_RETRANS_DATA_ACKED and check that in the merged pkts_acked in the 
cases that were using the old rtt callback. It would allow retaining the 
previous (correct) functionality as it was before the API merge. That 
would prevent potential regressions in cc modules due to this merge. 

...Then perhaps come up with a solution that takes advantage of timestamps 
more aggressively to 2.6.23 like the core rtt estimator already does. 


-- 
 i.