netdev - Re: [PATCH net-next] net: sched: pie: fix 64-bit division

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:   Wed, 27 Feb 2019 21:42:28 +0530
From:   Leslie Monis <lesliemonis@...il.com>
To:     David Laight <David.Laight@...LAB.COM>
Cc:     netdev@...r.kernel.org
Subject: Re: [PATCH net-next] net: sched: pie: fix 64-bit division

On Wed, Feb 27, 2019 at 10:11:14AM +0000, David Laight wrote:
> From: Leslie Monis
> > Sent: 27 February 2019 01:00
> > Use div_u64() to resolve build failures on 32-bit platforms.
> > 
> > Fixes: 3f7ae5f3dc52 ("net: sched: pie: add more cases to auto-tune alpha and beta")
> > Signed-off-by: Leslie Monis <lesliemonis@...il.com>
> > ---
> >  net/sched/sch_pie.c | 2 +-
> >  1 file changed, 1 insertion(+), 1 deletion(-)
> > 
> > diff --git a/net/sched/sch_pie.c b/net/sched/sch_pie.c
> > index 4c0670b6aec1..f93cfe034c72 100644
> > --- a/net/sched/sch_pie.c
> > +++ b/net/sched/sch_pie.c
> > @@ -429,7 +429,7 @@ static void calculate_probability(struct Qdisc *sch)
> >  	 */
> > 
> >  	if (qdelay == 0 && qdelay_old == 0 && update_prob)
> > -		q->vars.prob = (q->vars.prob * 98) / 100;
> > +		q->vars.prob = 98 * div_u64(q->vars.prob, 100);
> 
> This has significantly different rounding after the change.
> The result for small values is very different.
> The alterative:
> 		q->vars.prob -= div_u64(q->vars.prob, 50);
> is much nearer to the original - but never goes to zero.
> 
> If the 98% decay factor isn't critical then you could remove
> 1/64th or 1/32nd + 1/16th to avoid the slow division.
> 
> 	David
> 
> -
> Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
> Registration No: 1397386 (Wales)
> 

Hi David,

You're right, the change does make the result for small
values different. I made it anyway as the probability
value is scaled by u64. It is safe to say that q->vars.prob
holds relatively large values (in its scaled form) in all
cases where it isn't 0.

But, I think we can avoid the slow division here. RFC 8033
does say that using (1 - 1/64) should be sufficient. This
will give us:
	q-vars.prob -= q->vars.prob >> 6;
which I feel would be much better. What do you reckon?

Thanks a lot for the feedback.

Cheers,
Leslie