[PATCH] [PKT_SCHED] RED: Fix overflow in calculation of queue average

[PATCH] [PKT_SCHED] RED: Fix overflow in calculation of queue average

[Ilpo Järvinen]

Overflow can occur very easily with 32 bits, e.g., with 1 second
us_idle is approx. 2^20, which leaves only 11-Wlog bits for queue
length. Since the EWMA exponent is typically around 9, queue
lengths larger than 2^2 cause overflow. Whether the affected
branch is taken when us_idle is as high as 1 second, depends on
Scell_log, but with rather reasonable configuration Scell_log is
large enough to cause p->Stab to have zero index, which always
results zero shift (typically also few other small indices result
in zero shift).

Signed-off-by: Ilpo Järvinen <ilpo.jarvinen@helsinki.fi>
---
 include/net/red.h |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/include/net/red.h b/include/net/red.h
index 5ccdbb3..1fc32e1 100644
--- a/include/net/red.h
+++ b/include/net/red.h
@@ -212,7 +212,7 @@ static inline unsigned long red_calc_qav
 		 * Seems, it is the best solution to
 		 * problem of too coarse exponent tabulation.
 		 */
-		us_idle = (p->qavg * us_idle) >> p->Scell_log;
+		us_idle = (p->qavg * (long long)us_idle) >> p->Scell_log;
 
 		if (us_idle < (p->qavg >> 1))
 			return p->qavg - us_idle;
-- 
1.4.1

Re: [PATCH] [PKT_SCHED] RED: Fix overflow in calculation of queue average

[Stephen Hemminger]

On Fri, 04 Aug 2006 00:33:32 +0300
Ilpo  Järvinen <ilpo.jarvinen@helsinki.fi> wrote:

> Overflow can occur very easily with 32 bits, e.g., with 1 second
> us_idle is approx. 2^20, which leaves only 11-Wlog bits for queue
> length. Since the EWMA exponent is typically around 9, queue
> lengths larger than 2^2 cause overflow. Whether the affected
> branch is taken when us_idle is as high as 1 second, depends on
> Scell_log, but with rather reasonable configuration Scell_log is
> large enough to cause p->Stab to have zero index, which always
> results zero shift (typically also few other small indices result
> in zero shift).
> 
> Signed-off-by: Ilpo Järvinen <ilpo.jarvinen@helsinki.fi>
> ---
>  include/net/red.h |    2 +-
>  1 files changed, 1 insertions(+), 1 deletions(-)
> 
> diff --git a/include/net/red.h b/include/net/red.h
> index 5ccdbb3..1fc32e1 100644
> --- a/include/net/red.h
> +++ b/include/net/red.h
> @@ -212,7 +212,7 @@ static inline unsigned long red_calc_qav
>  		 * Seems, it is the best solution to
>  		 * problem of too coarse exponent tabulation.
>  		 */
> -		us_idle = (p->qavg * us_idle) >> p->Scell_log;
> +		us_idle = (p->qavg * (long long)us_idle) >> p->Scell_log;
>  
>  		if (us_idle < (p->qavg >> 1))
>  			return p->qavg - us_idle;

Use u64 instead of long long. 

-- 
If one would give me six lines written by the hand of the most honest
man, I would find something in them to have him hanged. -- Cardinal Richlieu

[PATCH v2] [PKT_SCHED] RED: Fix overflow in calculation of queue average

[Ilpo Järvinen]

Overflow can occur very easily with 32 bits, e.g., with 1 second
us_idle is approx. 2^20, which leaves only 11-Wlog bits for queue
length. Since the EWMA exponent is typically around 9, queue
lengths larger than 2^2 cause overflow. Whether the affected
branch is taken when us_idle is as high as 1 second, depends on
Scell_log, but with rather reasonable configuration Scell_log is
large enough to cause p->Stab to have zero index, which always
results zero shift (typically also few other small indices result
in zero shift).

Signed-off-by: Ilpo Järvinen <ilpo.jarvinen@helsinki.fi>
---
 include/net/red.h |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/include/net/red.h b/include/net/red.h
index 2ed4358..cfc2625 100644
--- a/include/net/red.h
+++ b/include/net/red.h
@@ -213,7 +213,7 @@ static inline unsigned long red_calc_qav
 		 * Seems, it is the best solution to
 		 * problem of too coarse exponent tabulation.
 		 */
-		us_idle = (p->qavg * us_idle) >> p->Scell_log;
+		us_idle = (p->qavg * (u64)us_idle) >> p->Scell_log;
 
 		if (us_idle < (p->qavg >> 1))
 			return p->qavg - us_idle;
-- 
1.4.0

Re: [PATCH v2] [PKT_SCHED] RED: Fix overflow in calculation of queue average

[David Miller]

From: "Ilpo Järvinen" <ilpo.jarvinen@helsinki.fi>
Date: Fri, 4 Aug 2006 18:44:20 +0300 (EEST)

> Overflow can occur very easily with 32 bits, e.g., with 1 second
> us_idle is approx. 2^20, which leaves only 11-Wlog bits for queue
> length. Since the EWMA exponent is typically around 9, queue
> lengths larger than 2^2 cause overflow. Whether the affected
> branch is taken when us_idle is as high as 1 second, depends on
> Scell_log, but with rather reasonable configuration Scell_log is
> large enough to cause p->Stab to have zero index, which always
> results zero shift (typically also few other small indices result
> in zero shift).
> 
> Signed-off-by: Ilpo Järvinen <ilpo.jarvinen@helsinki.fi>

Applied, thanks.