bug in qavg calculation in include/net/red.h (resending as plain-text email)

(Resending as plain text)

Dear Alexey,

The code (see below) for computing the queue average for RED implementation in Linux kernel has a bug. The return line should be "return p->qavg + ((backlog - p->qavg) >> p->Wlog);". 

qavg = qavg*(1-W) + backlog*W

     = qavg + (backlog-qavg)*W

The current buggy code applies right shift to only the previous qavg, where as it should be applied to (backlog - qavg). Hope you can get this bug corrected.

Thanks,
Praveen Yalagandula
Senior Researcher, HP Labs, Palo Alto, CA

-------------------------------------

static inline unsigned long red_calc_qavg_no_idle_time(struct red_parms *p, unsigned int backlog)
{
     /*
     * NOTE: p->qavg is fixed point number with point at Wlog.
     * The formula below is equvalent to floating point
     * version:
     *
     *   qavg = qavg*(1-W) + backlog*W;
     *
     * --ANK (980924)
     */
     return p->qavg + (backlog - (p->qavg >> p->Wlog));
}

Le jeudi 05 janvier 2012 à 19:30 +0000, Yalagandula, Praveen a écrit :

(Resending as plain text)

Dear Alexey,

The code (see below) for computing the queue average for RED
implementation in Linux kernel has a bug. The return line should be
"return p->qavg + ((backlog - p->qavg) >> p->Wlog);". 

qavg = qavg*(1-W) + backlog*W

     = qavg + (backlog-qavg)*W

The current buggy code applies right shift to only the previous qavg,
where as it should be applied to (backlog - qavg). Hope you can get
this bug corrected.

Code is correct.

Please read the comment, it really explains the thing.

Thanks

Le jeudi 05 janvier 2012 à 21:13 +0100, Eric Dumazet a écrit :

Le jeudi 05 janvier 2012 à 19:30 +0000, Yalagandula, Praveen a écrit :

quoted

(Resending as plain text)

Dear Alexey,

The code (see below) for computing the queue average for RED
implementation in Linux kernel has a bug. The return line should be
"return p->qavg + ((backlog - p->qavg) >> p->Wlog);". 

qavg = qavg*(1-W) + backlog*W

     = qavg + (backlog-qavg)*W

The current buggy code applies right shift to only the previous qavg,
where as it should be applied to (backlog - qavg). Hope you can get
this bug corrected.

Code is correct.

Please read the comment, it really explains the thing.

I have more time to explain what's going on :

On input, "unsigned int backlog" is not yet scaled.
But qavg _is_ scaled by p->Wlog.

So we should first scale "backlog" by Wlog bits to the left :

backlog_scaled = backlog << p->Wlog;

Then we do our computation as you stated :

return p->qavg + ((backlog_scaled - p->qavg) >> p->Wlog);

Its equivalent to current code, but using a single shift to the right.

return p->qavg + (backlog - (p->qavg >> p->Wlog));


Hope this helps.

Thanks for the prompt response. I understand it better now.

Cheers,
Praveen

-----Original Message-----
From: Eric Dumazet [mailto:eric.dumazet@gmail.com]
Sent: Thursday, January 05, 2012 1:20 PM
To: Yalagandula, Praveen
Cc: Alexey Kuznetsov; netdev@vger.kernel.org
Subject: Re: bug in qavg calculation in include/net/red.h (resending as
plain-text email)

Le jeudi 05 janvier 2012 à 21:13 +0100, Eric Dumazet a écrit :

quoted

Le jeudi 05 janvier 2012 à 19:30 +0000, Yalagandula, Praveen a écrit

:

quoted

quoted

(Resending as plain text)

Dear Alexey,

The code (see below) for computing the queue average for RED
implementation in Linux kernel has a bug. The return line should be
"return p->qavg + ((backlog - p->qavg) >> p->Wlog);".

qavg = qavg*(1-W) + backlog*W

     = qavg + (backlog-qavg)*W

The current buggy code applies right shift to only the previous

qavg,

quoted

quoted

where as it should be applied to (backlog - qavg). Hope you can get
this bug corrected.

Code is correct.

Please read the comment, it really explains the thing.

I have more time to explain what's going on :

On input, "unsigned int backlog" is not yet scaled.
But qavg _is_ scaled by p->Wlog.

So we should first scale "backlog" by Wlog bits to the left :

backlog_scaled = backlog << p->Wlog;

Then we do our computation as you stated :

return p->qavg + ((backlog_scaled - p->qavg) >> p->Wlog);

Its equivalent to current code, but using a single shift to the right.

return p->qavg + (backlog - (p->qavg >> p->Wlog));


Hope this helps.