Skip to contentSkip to conversation

net: sched: pie: fix 64-bit division

PATCH Applied Leslie Monis 4 participants 7 messages Feb 27, 2019 – Feb 28, 2019

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

PATCH 1/1 net: sched: pie: fix 64-bit division

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")
---
 net/sched/sch_pie.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
net/sched/sch_pie.c +1 -1
index 4c0670b6aec1..f93cfe034c72 100644
@@ -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;
Signature · 1 line
2.17.1
Tested-by on v1 1/1
#1 lore raw
Quoted 4 lines · 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")

Thanks.

[https://lore.kernel.org/lkml/[email protected]/]

Quoted 18 lines
---
 net/sched/sch_pie.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
net/sched/sch_pie.c +1 -1
index 4c0670b6aec1..f93cfe034c72 100644
@@ -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;
Signature · 1 line
~Randy
#3 lore raw
In reply to Leslie Monis

From: Leslie Monis

Quoted 14 lines

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")
---
 net/sched/sch_pie.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
net/sched/sch_pie.c +0 -0
index 4c0670b6aec1..f93cfe034c72 100644

net/sched/sch_pie.c static void calculate_probability(struct Qdisc *sch) · line 432

Quoted 5 lines
net/sched/sch_pie.c +1 -1
@@ -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)

#4 lore raw
Quoted 27 lines · David Laight

From: Leslie Monis

Quoted 14 lines

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")
---
 net/sched/sch_pie.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
net/sched/sch_pie.c +0 -0
index 4c0670b6aec1..f93cfe034c72 100644

net/sched/sch_pie.c static void calculate_probability(struct Qdisc *sch) · line 432

Quoted 5 lines
net/sched/sch_pie.c +1 -1
@@ -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.

Quoted 9 lines

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

#5 lore raw

From: Leslie Monis

Quoted 43 lines

Sent: 27 February 2019 16:12

Quoted 24 lines · David Laight

From: Leslie Monis

Quoted 14 lines

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")
---
 net/sched/sch_pie.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
net/sched/sch_pie.c +0 -0
index 4c0670b6aec1..f93cfe034c72 100644

net/sched/sch_pie.c static void calculate_probability(struct Qdisc *sch) · line 432

Quoted 5 lines
net/sched/sch_pie.c +1 -1
@@ -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:

Quoted 7 lines
		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.

Quoted 5 lines

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)

#6 lore raw
Quoted 52 lines · David Laight

From: Leslie Monis

Quoted 43 lines

Sent: 27 February 2019 16:12

Quoted 24 lines · David Laight

From: Leslie Monis

Quoted 14 lines

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")
---
 net/sched/sch_pie.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
net/sched/sch_pie.c +0 -0
index 4c0670b6aec1..f93cfe034c72 100644

net/sched/sch_pie.c static void calculate_probability(struct Qdisc *sch) · line 432

Quoted 5 lines
net/sched/sch_pie.c +1 -1
@@ -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:

Quoted 7 lines
		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.

Quoted 5 lines

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:

Quoted 9 lines
	/* 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