sched/fair: fix calc_cfs_shares fixed point arithmetics

PATCH In review Samuel Thibault 5 participants 12 messages Dec 19, 2016 – Jan 14, 2017 Scheduler

lore

Share & tools

lore

Samuel Thibault

author

2016-12-19 22:40 UTC #0 lore raw

PATCH 1/1 sched/fair: fix calc_cfs_shares fixed point arithmetics

2159197d6677 ("sched/core: Enable increased load resolution on 64-bit kernels")

exposed yet another miscalculation in calc_cfs_shares: MIN_SHARES is unscaled, and must thus be scaled before being manipulated against "shares" amounts.

Signed-off-by Samuel Thibault <[email protected]>

Cc Peter Zijlstra <[email protected]>

Cc Thomas Gleixner <[email protected]>

Cc Ingo Molnar <[email protected]>

Cc [email protected]

Fixes 2159197d6677 ("sched/core: Enable increased load resolution on 64-bit kernels")

---
This should be backported to 4.7 and 4.8 to fix scheduling priorities miscalculations

kernel/sched/fair.c +2 -2

index 6559d19..be84f72 100644
@@ -2657,8 +2657,8 @@ static long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg)
 	if (tg_weight)
 		shares /= tg_weight;
 
-	if (shares < MIN_SHARES)
-		shares = MIN_SHARES;
+	if (shares < scale_load(MIN_SHARES))
+		shares = scale_load(MIN_SHARES);
 	if (shares > tg->shares)
 		shares = tg->shares;

Paul Turner

2016-12-19 22:45 UTC #1 lore raw

Quoted 4 lines · Samuel Thibault

2159197d6677 ("sched/core: Enable increased load resolution on 64-bit kernels")
exposed yet another miscalculation in calc_cfs_shares: MIN_SHARES is unscaled, and must thus be scaled before being manipulated against "shares" amounts.

It's actually intentional that MIN_SHARES is un-scaled here, this is necessary to support the goal of sub-partitioning groups with small shares.

E.g. A group with shares=2 and 5 threads will internally provide 2048 units of weight for the load-balancer to account for their distribution.

Quoted 27 lines

Signed-off-by Samuel Thibault <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc [email protected]
Fixes 2159197d6677 ("sched/core: Enable increased load resolution on 64-bit kernels")
---
This should be backported to 4.7 and 4.8 to fix scheduling priorities miscalculations
kernel/sched/fair.c +2 -2
index 6559d19..be84f72 100644
@@ -2657,8 +2657,8 @@ static long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg)
        if (tg_weight)
                shares /= tg_weight;
 
-       if (shares < MIN_SHARES)
-               shares = MIN_SHARES;
+       if (shares < scale_load(MIN_SHARES))
+               shares = scale_load(MIN_SHARES);
        if (shares > tg->shares)
                shares = tg->shares;
 

Samuel Thibault

author

2016-12-19 23:07 UTC #2 lore raw

Quoted 10 lines · Paul Turner, on Mon 19 Dec 2016 14:44:38 -0800, wrote:

Quoted 4 lines · Samuel Thibault
2159197d6677 ("sched/core: Enable increased load resolution on 64-bit kernels")
exposed yet another miscalculation in calc_cfs_shares: MIN_SHARES is unscaled, and must thus be scaled before being manipulated against "shares" amounts.
It's actually intentional that MIN_SHARES is un-scaled here, this is necessary to support the goal of sub-partitioning groups with small shares.

Uh? you mean it's normal that MIN_SHARES is here compared as such against "shares" while e.g. in sched_group_set_shares or effective_load it is scaled before comparing with "shares"?

Quoted 3 lines

E.g. A group with shares=2 and 5 threads will internally provide 2048 units of weight for the load-balancer to account for their distribution.

But here "shares" is already scaled, so

Quoted 2 lines

kernel/sched/fair.c +0 -2

-       if (shares < MIN_SHARES)
-               shares = MIN_SHARES;

...

Quoted 1 line

        return shares;

This will only make sure that the returned shares is 2, not 2048.

Samuel

Paul Turner

2016-12-19 23:26 UTC #3 lore raw

Quoted 8 lines · Samuel Thibault

Quoted 7 lines · Paul Turner, on Mon 19 Dec 2016 14:44:38 -0800, wrote:
Quoted 4 lines · Samuel Thibault
2159197d6677 ("sched/core: Enable increased load resolution on 64-bit kernels")
exposed yet another miscalculation in calc_cfs_shares: MIN_SHARES is unscaled, and must thus be scaled before being manipulated against "shares" amounts.

Quoted 7 lines

Quoted 3 lines
It's actually intentional that MIN_SHARES is un-scaled here, this is necessary to support the goal of sub-partitioning groups with small shares.
Uh? you mean it's normal that MIN_SHARES is here compared as such against "shares" while e.g. in sched_group_set_shares or effective_load it is scaled before comparing with "shares"?

Yes.

sched_group_set_shares() controls the amount allocated to the group.

Both calc_cfs_shares() and effective_load() are subdividing this total. Which is why it is scaled up from the external value of 2.

Quoted 5 lines

Quoted 4 lines
E.g. A group with shares=2 and 5 threads will internally provide 2048 units of weight for the load-balancer to account for their distribution.

Quoted 8 lines

But here "shares" is already scaled, so
Quoted 2 lines
Quoted 2 lines
kernel/sched/fair.c +0 -2
-       if (shares < MIN_SHARES)
-               shares = MIN_SHARES;
...
Quoted 1 line
Quoted 1 line
        return shares;
This will only make sure that the returned shares is 2, not 2048.

This is intentional. The MIN_SHARES you are seeing here is overloaded. Every "1" unit of share is "SCHED_LOAD_RESOLUTION" bits internally. We express a minimum of "2" in terms of the unit weight due to larger numerical errors in the "1" case.
In the unscaled case this needs to be MIN_SHARES, and in the scaled case, the subdivision of the scaled values must still be >=2.

To make this concrete:
In this case we can then internally say that there are (internally) ~410 units of weight for each of these 5 threads.
Thus, if one cpu has 4 threads and another 1, we see that as a 1640/410 imbalance, not a 2048/2048 balance.

Quoted 2 lines

Samuel

Samuel Thibault

author

2016-12-19 23:29 UTC #4 lore raw

Quoted 9 lines · Paul Turner, on Mon 19 Dec 2016 15:26:19 -0800, wrote:

Quoted 6 lines
Quoted 2 lines
Quoted 2 lines
kernel/sched/fair.c +0 -2
-       if (shares < MIN_SHARES)
-               shares = MIN_SHARES;
...
Quoted 1 line
Quoted 1 line
        return shares;
This will only make sure that the returned shares is 2, not 2048.
This is intentional. The MIN_SHARES you are seeing here is overloaded. Every "1" unit of share is "SCHED_LOAD_RESOLUTION" bits internally.

I'm not talking about the SCHED_LOAD_RESOLUTION scaling, but about the SCHED_FIXEDPOINT_SHIFT scaling, which is what
2159197d6677 ("sched/core: Enable increased load resolution on 64-bit kernels") modified on 64bit platforms.

Samuel

Paul Turner

2016-12-19 23:32 UTC #5 lore raw

Quoted 8 lines · Samuel Thibault

Quoted 7 lines · Paul Turner, on Mon 19 Dec 2016 15:26:19 -0800, wrote:
Quoted 6 lines
Quoted 2 lines
Quoted 2 lines
kernel/sched/fair.c +0 -2
-       if (shares < MIN_SHARES)
-               shares = MIN_SHARES;
...
Quoted 1 line
Quoted 1 line
        return shares;
This will only make sure that the returned shares is 2, not 2048.

Quoted 7 lines

Quoted 2 lines
This is intentional. The MIN_SHARES you are seeing here is overloaded. Every "1" unit of share is "SCHED_LOAD_RESOLUTION" bits internally.
I'm not talking about the SCHED_LOAD_RESOLUTION scaling, but about the SCHED_FIXEDPOINT_SHIFT scaling, which is what
2159197d6677 ("sched/core: Enable increased load resolution on 64-bit kernels") modified on 64bit platforms.

.... From that commit:

"""
-#if 0 /* BITS_PER_LONG > 32 -- currently broken: it increases power usage under light load */
+#ifdef CONFIG_64BIT

 # define SCHED_LOAD_RESOLUTION 10
 # define scale_load(w)         ((w) << SCHED_LOAD_RESOLUTION)
 # define scale_load_down(w)    ((w) >> SCHED_LOAD_RESOLUTION)
"""

Please take a deeper look at the scale_load() interactions.

Samuel Thibault

author

2016-12-19 23:45 UTC #6 lore raw

Quoted 20 lines · Paul Turner, on Mon 19 Dec 2016 15:32:15 -0800, wrote:

Quoted 8 lines · Samuel Thibault
Quoted 7 lines · Paul Turner, on Mon 19 Dec 2016 15:26:19 -0800, wrote:
Quoted 6 lines
Quoted 2 lines
Quoted 2 lines
kernel/sched/fair.c +0 -2
-       if (shares < MIN_SHARES)
-               shares = MIN_SHARES;
...
Quoted 1 line
Quoted 1 line
        return shares;
This will only make sure that the returned shares is 2, not 2048.
Quoted 7 lines
Quoted 2 lines
This is intentional. The MIN_SHARES you are seeing here is overloaded. Every "1" unit of share is "SCHED_LOAD_RESOLUTION" bits internally.
I'm not talking about the SCHED_LOAD_RESOLUTION scaling, but about the SCHED_FIXEDPOINT_SHIFT scaling, which is what
2159197d6677 ("sched/core: Enable increased load resolution on 64-bit kernels") modified on 64bit platforms.
.... From that commit:

Quoted 7 lines

"""
-#if 0 /* BITS_PER_LONG > 32 -- currently broken: it increases power usage under light load */
+#ifdef CONFIG_64BIT
 # define SCHED_LOAD_RESOLUTION 10
 # define scale_load(w)         ((w) << SCHED_LOAD_RESOLUTION)
 # define scale_load_down(w)    ((w) >> SCHED_LOAD_RESOLUTION)

Errgl, sorry, I was referring to the old naming. This stuff has seen so much patching over and over in the past revisions... It though you were referring to SCHED_CAPACITY_SCALE. The code I was reading now uses SCHED_LOAD_RESOLUTION, so that's why I read your "SCHED_LOAD_RESOLUTION" as "the other scaling".

Quoted 3 lines

The MIN_SHARES you are seeing here is overloaded.
In the unscaled case this needs to be MIN_SHARES, and in the scaled case, the subdivision of the scaled values must still be >=2.

Ok, now I understand. I have to say this overloading is confusing.

Samuel

Dietmar Eggemann

reviewer

2016-12-20 13:04 UTC #7 lore raw

Hi Samuel,

Quoted 4 lines · Samuel Thibault

Quoted 3 lines · Paul Turner, on Mon 19 Dec 2016 15:32:15 -0800, wrote:
Quoted 1 line · Samuel Thibault
Paul Turner, on Mon 19 Dec 2016 15:26:19 -0800, wrote:

[...]

Quoted 7 lines

Quoted 3 lines
The MIN_SHARES you are seeing here is overloaded.
In the unscaled case this needs to be MIN_SHARES, and in the scaled case, the subdivision of the scaled values must still be >=2.
Ok, now I understand. I have to say this overloading is confusing.
Samuel

this had been already discussed back in August when I posted the original patch.

https://lkml.org/lkml/2016/8/22/351
https://lkml.org/lkml/2016/8/23/641

Peter Zijlstra

maintainer

2016-12-20 13:16 UTC #8 lore raw

Quoted 14 lines · Dietmar Eggemann

Hi Samuel,
Quoted 4 lines · Samuel Thibault
Quoted 3 lines · Paul Turner, on Mon 19 Dec 2016 15:32:15 -0800, wrote:
Quoted 1 line · Samuel Thibault
Paul Turner, on Mon 19 Dec 2016 15:26:19 -0800, wrote:
[...]
Quoted 4 lines
Quoted 3 lines
The MIN_SHARES you are seeing here is overloaded.
In the unscaled case this needs to be MIN_SHARES, and in the scaled case, the subdivision of the scaled values must still be >=2.

Quoted 6 lines

Quoted 3 lines
Ok, now I understand. I have to say this overloading is confusing.
Samuel
this had been already discussed back in August when I posted the original patch.

Maybe we should put a comment in to avoid getting more of these ;-)

Dietmar Eggemann

reviewer

2017-01-11 11:29 UTC #9 lore raw

Quoted 15 lines · Peter Zijlstra

Quoted 14 lines · Dietmar Eggemann
Hi Samuel,
Quoted 4 lines · Samuel Thibault
Quoted 3 lines · Paul Turner, on Mon 19 Dec 2016 15:32:15 -0800, wrote:
Quoted 1 line · Samuel Thibault
Paul Turner, on Mon 19 Dec 2016 15:26:19 -0800, wrote:
[...]
Quoted 4 lines
Quoted 3 lines
The MIN_SHARES you are seeing here is overloaded.
In the unscaled case this needs to be MIN_SHARES, and in the scaled case, the subdivision of the scaled values must still be >=2.

Quoted 9 lines

Quoted 6 lines
Quoted 3 lines
Ok, now I understand. I have to say this overloading is confusing.
Samuel
this had been already discussed back in August when I posted the original patch.
Maybe we should put a comment in to avoid getting more of these ;-)

Maybe something like this? Mainly what Paul taught us plus an example from a discussion I had with Vincent.

-- >8 --

Subject: [PATCH] sched/fair: Explain why MIN_SHARES isn't scaled in
calc_cfs_shares()

Signed-off-by Dietmar Eggemann <[email protected]>

---
 kernel/sched/fair.c | 12 ++++++++++++
 1 file changed, 12 insertions(+)

kernel/sched/fair.c +12 -0

index 6559d197e08a..a0ca9b11b1b3 100644
@@ -2657,6 +2657,18 @@ static long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg)
        if (tg_weight)
                shares /= tg_weight;
 
+       /*
+        * MIN_SHARES has to be unscaled here to support per-cpu partitioning
+        * of a group with small tg->shares value. It is a floor value which is
+        * assigned as a minimum load.weight to the sched_entity representing
+        * the group on a cpu.
+        *
+        * E.g. on 64-bit for a group with tg->shares of scale_load(15)=15*1024
+        * on an 8 core system with 8 tasks each runnable on one cpu shares has
+        * to be 15*1024*1/8=1920 instead of scale_load(MIN_SHARES)=2*1024. In
+        * case no task is runnable on a cpu MIN_SHARES=2 should be returned
+        * instead of 0.
+        */
        if (shares < MIN_SHARES)
                shares = MIN_SHARES;
        if (shares > tg->shares)

Signature · 1 line

2.11.0

tip-bot for Dietmar Eggemann

merge bot

2017-01-14 12:49 UTC #10 lore raw

[tip:sched/core] sched/fair: Explain why MIN_SHARES isn't scaled in calc_cfs_shares()

sched/fair: Explain why MIN_SHARES isn't scaled in calc_cfs_shares()

Commit-ID:  b8fd8423697b9ec729c5bb91737faad84ae19985
Gitweb:     http://git.kernel.org/tip/b8fd8423697b9ec729c5bb91737faad84ae19985
Author:     Dietmar Eggemann <[email protected]>
AuthorDate: Wed, 11 Jan 2017 11:29:47 +0000
Committer:  Ingo Molnar <[email protected]>
CommitDate: Sat, 14 Jan 2017 11:30:02 +0100

sched/fair: Explain why MIN_SHARES isn't scaled in calc_cfs_shares()

Signed-off-by Dietmar Eggemann <[email protected]>

Signed-off-by Peter Zijlstra (Intel) <[email protected]>

Cc Linus Torvalds <[email protected]>

Cc Mike Galbraith <[email protected]>

Cc Paul Turner <[email protected]>

Cc Peter Zijlstra <[email protected]>

Cc Samuel Thibault <[email protected]>

Cc Thomas Gleixner <[email protected]>

Link http://lkml.kernel.org/r/[email protected] open here

Signed-off-by Ingo Molnar <[email protected]>

---
 kernel/sched/fair.c | 12 ++++++++++++
 1 file changed, 12 insertions(+)

kernel/sched/fair.c +12 -0

index 2b866a2..274c747 100644
@@ -2657,6 +2657,18 @@ static long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg)
 	if (tg_weight)
 		shares /= tg_weight;
 
+	/*
+	 * MIN_SHARES has to be unscaled here to support per-CPU partitioning
+	 * of a group with small tg->shares value. It is a floor value which is
+	 * assigned as a minimum load.weight to the sched_entity representing
+	 * the group on a CPU.
+	 *
+	 * E.g. on 64-bit for a group with tg->shares of scale_load(15)=15*1024
+	 * on an 8-core system with 8 tasks each runnable on one CPU shares has
+	 * to be 15*1024*1/8=1920 instead of scale_load(MIN_SHARES)=2*1024. In
+	 * case no task is runnable on a CPU MIN_SHARES=2 should be returned
+	 * instead of 0.
+	 */
 	if (shares < MIN_SHARES)
 		shares = MIN_SHARES;
 	if (shares > tg->shares)

Samuel Thibault

author

2016-12-20 13:22 UTC #11 lore raw

In reply to Dietmar Eggemann

Quoted 12 lines · Dietmar Eggemann, on Tue 20 Dec 2016 14:04:34 +0100, wrote:

Quoted 4 lines · Samuel Thibault
Quoted 3 lines · Paul Turner, on Mon 19 Dec 2016 15:32:15 -0800, wrote:
Quoted 1 line · Samuel Thibault
Paul Turner, on Mon 19 Dec 2016 15:26:19 -0800, wrote:
[...]
Quoted 4 lines
Quoted 3 lines
The MIN_SHARES you are seeing here is overloaded.
In the unscaled case this needs to be MIN_SHARES, and in the scaled case, the subdivision of the scaled values must still be >=2.

Quoted 6 lines

Quoted 3 lines
Ok, now I understand. I have to say this overloading is confusing.
Samuel
this had been already discussed back in August when I posted the original patch.

But that doesn't show up in the source code or git history. One shouldn't have to dig mailing lists to get code comments :)

Samuel