[PATCH 1/25]: Fix bug in the calculation of very low sending rates

[PATCH 1/25]: Fix bug in the calculation of very low sending rates

[Gerrit Renker]

[CCID 3]: Fix bug in the calculation of very low sending rates

This fixes an error in the calculation of t_ipi when X converges towards
very low sending rates (between 1 and 64 bytes per second).

Although this case may not sound likely, it can be reproduced by connecting,
hitting enter (1 byte sent) and waiting for some time, during which the
nofeedback timer halves the sending rate until finally it reaches the region
1..64 bytes/sec. Computing X is handled correctly (tested separately); but by
dividing X _before_ entering the calculation of t_ipi, X becomes zero as
a result.  This in turn triggers a BUG condition caught in scaled_div().

Fixed by replacing with equivalent statement and explicit typecast for good
measure.

Calculation verified and effect of patch tested - reduced never below 1 byte
per 64 seconds afterwards, i.e. not allowing divide-by-zero.

Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
---
 net/dccp/ccids/ccid3.c |    4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

--- a/net/dccp/ccids/ccid3.c
+++ b/net/dccp/ccids/ccid3.c
@@ -102,8 +102,8 @@ static inline u64 rfc3390_initial_rate(s
 static inline void ccid3_update_send_interval(struct ccid3_hc_tx_sock *hctx)
 {
 	/* Calculate new t_ipi = s / X_inst (X_inst is in 64 * bytes/second) */
-	hctx->ccid3hctx_t_ipi = scaled_div(hctx->ccid3hctx_s,
-					   hctx->ccid3hctx_x >> 6);
+	hctx->ccid3hctx_t_ipi = scaled_div32(((u64)hctx->ccid3hctx_s) << 6,
+					     hctx->ccid3hctx_x);
 
 	/* Calculate new delta by delta = min(t_ipi / 2, t_gran / 2) */
 	hctx->ccid3hctx_delta = min_t(u32, hctx->ccid3hctx_t_ipi / 2,

Re: [PATCH 1/25]: Fix bug in the calculation of very low sending rates

[Ian McDonald]

On 3/22/07, Gerrit Renker <gerrit@erg.abdn.ac.uk> wrote:
> [CCID 3]: Fix bug in the calculation of very low sending rates
>
Acked-by: Ian McDonald <ian.mcdonald@jandi.co.nz>
-- 
Web: http://wand.net.nz/~iam4
Blog: http://iansblog.jandi.co.nz
WAND Network Research Group

Re: [PATCH 1/25]: Fix bug in the calculation of very low sending

[Eddie Kohler]

I'm surprised that this case occurs:

Gerrit Renker wrote:
> [CCID 3]: Fix bug in the calculation of very low sending rates
> 
> This fixes an error in the calculation of t_ipi when X converges towards
> very low sending rates (between 1 and 64 bytes per second).
> 
> Although this case may not sound likely, it can be reproduced by connecting,
> hitting enter (1 byte sent) and waiting for some time, during which the
> nofeedback timer halves the sending rate until finally it reaches the region
> 1..64 bytes/sec. Computing X is handled correctly (tested separately); but by
> dividing X _before_ entering the calculation of t_ipi, X becomes zero as
> a result.  This in turn triggers a BUG condition caught in scaled_div().

According to RFC 4342, the allowed sending rate should never be reduced 
below the TCP initial sending rate of two or four packets per RTT, 
depending on the packet size, as the result of an idle or slow period.

Hitting enter and then waiting is an idle period.

Since X is the allowed transmit rate, it seems Linux implementation is 
not following this at the moment; but perhaps there is code elsewhere 
handling this case?

Eddie


> Fixed by replacing with equivalent statement and explicit typecast for good
> measure.
> 
> Calculation verified and effect of patch tested - reduced never below 1 byte
> per 64 seconds afterwards, i.e. not allowing divide-by-zero.
> 
> Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
> ---
>  net/dccp/ccids/ccid3.c |    4 ++--
>  1 file changed, 2 insertions(+), 2 deletions(-)
> 
> --- a/net/dccp/ccids/ccid3.c
> +++ b/net/dccp/ccids/ccid3.c
> @@ -102,8 +102,8 @@ static inline u64 rfc3390_initial_rate(s
>  static inline void ccid3_update_send_interval(struct ccid3_hc_tx_sock *hctx)
>  {
>  	/* Calculate new t_ipi = s / X_inst (X_inst is in 64 * bytes/second) */
> -	hctx->ccid3hctx_t_ipi = scaled_div(hctx->ccid3hctx_s,
> -					   hctx->ccid3hctx_x >> 6);
> +	hctx->ccid3hctx_t_ipi = scaled_div32(((u64)hctx->ccid3hctx_s) << 6,
> +					     hctx->ccid3hctx_x);
>  
>  	/* Calculate new delta by delta = min(t_ipi / 2, t_gran / 2) */
>  	hctx->ccid3hctx_delta = min_t(u32, hctx->ccid3hctx_t_ipi / 2,
> -
> To unsubscribe from this list: send the line "unsubscribe dccp" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH 1/25]: Fix bug in the calculation of very low sending rates

[Gerrit Renker]

Quoting Eddie Kohler:
|  I'm surprised that this case occurs:
|  
|  Gerrit Renker wrote:
|  > [CCID 3]: Fix bug in the calculation of very low sending rates
|  > 
|  > This fixes an error in the calculation of t_ipi when X converges towards
|  > very low sending rates (between 1 and 64 bytes per second).
|  > 
|  > Although this case may not sound likely, it can be reproduced by connecting,
|  > hitting enter (1 byte sent) and waiting for some time, during which the
|  > nofeedback timer halves the sending rate until finally it reaches the region
|  > 1..64 bytes/sec. Computing X is handled correctly (tested separately); but by
|  > dividing X _before_ entering the calculation of t_ipi, X becomes zero as
|  > a result.  This in turn triggers a BUG condition caught in scaled_div().
|  
|  According to RFC 4342, the allowed sending rate should never be reduced 
|  below the TCP initial sending rate of two or four packets per RTT, 
|  depending on the packet size, as the result of an idle or slow period.
|  
|  Hitting enter and then waiting is an idle period.
|  
|  Since X is the allowed transmit rate, it seems Linux implementation is 
|  not following this at the moment; but perhaps there is code elsewhere 
|  handling this case?
|  
Respecting the TCP initial sending rate is handled by rfc3390_initial_rate(), but this
patch is in a different section of the code; the nofeedback timer reducing X.
This patch is not affected by and does not affect the TCP initial rate. 

It is a bona-fide bug fix and only concerned with rounding errors. The present code is 
wrong and will cause a BUG condition under the described conditions.
|  >  static inline void ccid3_update_send_interval(struct ccid3_hc_tx_sock *hctx)
|  >  {
|  >  	/* Calculate new t_ipi = s / X_inst (X_inst is in 64 * bytes/second) */
|  > -	hctx->ccid3hctx_t_ipi = scaled_div(hctx->ccid3hctx_s,
|  > -					   hctx->ccid3hctx_x >> 6);
|  > +	hctx->ccid3hctx_t_ipi = scaled_div32(((u64)hctx->ccid3hctx_s) << 6,
|  > +					     hctx->ccid3hctx_x);
The bug here is in scaled_div(hctx->ccid3hctx_s, hctx->ccid3hctx_x >> 6): the right-shift
is done before the division operation is evaluated. Thus sending rates in the range 
1/64 bytes/sec ... 1 byte/sec will appear as 0, and consequently trigger "divide-by-zero"
BUG condition in scaled_div. And this case is perfectly possible, due to the definition
of s/t_mbi and s/(2*t_mbi) in RFC 3448, 4.3 - both values would with the above show as 0
when s is very small.

It may be that due to the TCP initial rate this case is rare, but it still represents a
bug condition and must not be allowed to occur.