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

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

[Leslie Monis]

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@gmail.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);
 
 	q->vars.qdelay = qdelay;
 	q->vars.qlen_old = qlen;
-- 
2.17.1

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

[Randy Dunlap]

On 2/26/19 5:00 PM, Leslie Monis wrote:
> 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@gmail.com>

Reported-by: Randy Dunlap <rdunlap@infradead.org>
Tested-by: Randy Dunlap <rdunlap@infradead.org>

Thanks.

[https://lore.kernel.org/lkml/6ecd1bde-c15b-0568-2b72-6e0796a87864@infradead.org/]

> ---
>  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);
>  
>  	q->vars.qdelay = qdelay;
>  	q->vars.qlen_old = qlen;
> 


-- 
~Randy

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

[David Miller]

From: Leslie Monis <lesliemonis@gmail.com>
Date: Wed, 27 Feb 2019 06:30:06 +0530

> 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@gmail.com>

Applied, thank you.

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

[David Laight]

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@gmail.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)

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

[Leslie Monis]

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@gmail.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

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

[David Laight]

From: Leslie Monis
> Sent: 27 February 2019 16:12
> 
> 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@gmail.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
> 
> 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?

I think I'd leave it as a division - the compiler should do the shift.
So:
	/* Scale by 98.4% */
	q-vars.prob -= q->vars.prob / 64u;

	David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)

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

[Leslie Monis]

On Thu, Feb 28, 2019 at 10:10:33AM +0000, David Laight wrote:
> From: Leslie Monis
> > Sent: 27 February 2019 16:12
> > 
> > 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@gmail.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
> > 
> > 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?
> 
> I think I'd leave it as a division - the compiler should do the shift.
> So:
> 	/* Scale by 98.4% */
> 	q-vars.prob -= q->vars.prob / 64u;
> 
> 	David
> 
> -
> Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
> Registration No: 1397386 (Wales)
> 

Alright, I'll prepare a patch for this. May I credit you
with a Suggested-by tag?

Thanks,
Leslie