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 :

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.