sched: fair: Use the earliest break even
PATCH 1/1 sched: fair: Use the earliest break even
In the idle CPU selection process occuring in the slow path via the find_idlest_group_cpu() function, we pick up in priority an idle CPU with the shallowest idle state otherwise we fall back to the least loaded CPU.
In order to be more energy efficient but without impacting the performances, let's use another criteria: the break even deadline.
At idle time, when we store the idle state the CPU is entering in, we compute the next deadline where the CPU could be woken up without spending more energy to sleep.
At the selection process, we use the shallowest CPU but in addition we choose the one with the minimal break even deadline instead of relying on the idle_timestamp. When the CPU is idle, the timestamp has less meaning because the CPU could have wake up and sleep again several times without exiting the idle loop. In this case the break even deadline is more relevant as it increases the probability of choosing a CPU which reached its break even.
Tested on a synquacer 24 cores, 6 sched domains:
sched/perf and messaging does not show a performance regression. Ran 10 times schbench and adrestia.
with break-even deadline:
-------------------------
schbench *99.0th : 14844.8 adrestia / periodic : 57.95 adrestia / single : 49.3
Without break-even deadline:
----------------------------
schbench / *99.0th : 15017.6 adrestia / periodic : 57 adrestia / single : 55.4
--- kernel/sched/fair.c | 18 ++++++++++++++++-- kernel/sched/idle.c | 9 ++++++++- kernel/sched/sched.h | 20 ++++++++++++++++++++ 3 files changed, 44 insertions(+), 3 deletions(-)
kernel/sched/fair.c +16 -2
@@ -5793,6 +5793,7 @@ find_idlest_group_cpu(struct sched_group *group, struct task_struct *p, int this {unsigned long load, min_load =ULONG_MAX ;unsigned int min_exit_latency =UINT_MAX ; +s64 min_break_even =S64_MAX ;u64 latest_idle_timestamp =0 ;int least_loaded_cpu = this_cpu;int shallowest_idle_cpu =-1 ;
@@ -5810,6 +5811,8 @@ find_idlest_group_cpu(struct sched_group *group, struct task_struct *p, int thisif (available_idle_cpu (i)) {struct rq *rq =cpu_rq (i);struct cpuidle_state *idle =idle_get_state (rq); +s64 break_even =idle_get_break_even (rq); +if (idle && idle->exit_latency < min_exit_latency) {/* * We give priority to a CPU whose idle state
@@ -5817,10 +5820,21 @@ find_idlest_group_cpu(struct sched_group *group, struct task_struct *p, int this* of any idle timestamp. */ min_exit_latency = idle->exit_latency; + min_break_even = break_even; latest_idle_timestamp = rq->idle_stamp; shallowest_idle_cpu = i; - }else if ((!idle || idle->exit_latency == min_exit_latency) && - rq->idle_stamp > latest_idle_timestamp) { + }else if ((idle && idle->exit_latency == min_exit_latency) && + break_even < min_break_even) { +/* +* We give priority to the shallowest +* idle states with the minimal break +* even deadline to decrease the +* probability to choose a CPU which +* did not reach its break even yet +*/ + min_break_even = break_even; + shallowest_idle_cpu = i; + }else if (!idle && rq->idle_stamp > latest_idle_timestamp) {/* * If equal or no active idle state, then * the most recently idled CPU might have
kernel/sched/idle.c +8 -1
@@ -19,7 +19,14 @@ extern char __cpuidle_text_start[], __cpuidle_text_end[];*/ void sched_idle_set_state (struct cpuidle_state *idle_state) { -idle_set_state (this_rq (), idle_state); +struct rq *rq =this_rq (); +ktime_t kt; + +if (likely (idle_state)) { + kt =ktime_add_ns (ktime_get (), idle_state->exit_latency_ns); +idle_set_state (rq, idle_state); +idle_set_break_even (rq,ktime_to_ns (kt)); + } }static int __read_mostly cpu_idle_force_poll;
kernel/sched/sched.h +20 -0
@@ -1015,6 +1015,7 @@ struct rq {#ifdef CONFIG_CPU_IDLE /* Must be inspected within a rcu lock section */ struct cpuidle_state *idle_state; +s64 break_even;#endif };
@@ -1850,6 +1851,16 @@ static inline struct cpuidle_state *idle_get_state(struct rq *rq) return rq->idle_state; } + +static inline void idle_set_break_even (struct rq *rq,s64 break_even) +{ + rq->break_even = break_even; +} + +static inline s64 idle_get_break_even (struct rq *rq) +{ +return rq->break_even; +}#else static inline void idle_set_state (struct rq *rq,struct cpuidle_state *idle_state)
@@ -1860,6 +1871,15 @@ static inline struct cpuidle_state *idle_get_state(struct rq *rq) {return NULL ; } + +static inline void idle_set_break_even (struct rq *rq,s64 break_even) +{ +} + +static inline s64 idle_get_break_even (struct rq *rq) +{ +return 0 ; +}#endif extern void schedule_idle (void );
Signature · 1 line
2.17.1
Hi Daniel
Adding Rafael to CC as I think he might be interested in this too.
Quoted 7 lines · Daniel Lezcano
In the idle CPU selection process occuring in the slow path via the
find_idlest_group_cpu()function, we pick up in priority an idle CPU with the shallowest idle state otherwise we fall back to the least loaded CPU.In order to be more energy efficient but without impacting the performances, let's use another criteria: the break even deadline.
What is the break even deadline?
Quoted 4 lines
At idle time, when we store the idle state the CPU is entering in, we compute the next deadline where the CPU could be woken up without spending more energy to sleep.
I think that's its definition, but could do with more explanation.
So the break even deadline is the time window during which we can abort the CPU while entering its shallowest idle state?
So if we have 2 cpus entering the shallowest idle state, we pick the one that has a faster abort? And the energy saving comes from the fact we avoided unnecessary sleep-just-to-wakeup-immediately cycle?
Quoted 20 lines
At the selection process, we use the shallowest CPU but in addition we choose the one with the minimal break even deadline instead of relying on the
idle_timestamp. When the CPU is idle, the timestamp has less meaning because the CPU could have wake up and sleep again several times without exiting the idle loop. In this case the break even deadline is more relevant as it increases the probability of choosing a CPU which reached its break even.Tested on a synquacer 24 cores, 6 sched domains:
sched/perf and messaging does not show a performance regression. Ran 10 times schbench and adrestia.
with break-even deadline:
-------------------------schbench *99.0th : 14844.8 adrestia / periodic : 57.95 adrestia / single : 49.3
Quoted 5 lines
Without break-even deadline:
----------------------------schbench / *99.0th : 15017.6 adrestia / periodic : 57 adrestia / single : 55.4
Lower is better or worse? The numbers might be popular and maybe I should have known them, but adding some explanation will always help.
Do you have any energy measurement on the impact of this patch?
Quoted 40 lines
Signed-off-by Daniel Lezcano <[email protected]>--- kernel/sched/fair.c | 18 ++++++++++++++++-- kernel/sched/idle.c | 9 ++++++++- kernel/sched/sched.h | 20 ++++++++++++++++++++ 3 files changed, 44 insertions(+), 3 deletions(-)kernel/sched/fair.c +6
-2@@ -5793,6 +5793,7 @@ find_idlest_group_cpu(struct sched_group *group, struct task_struct *p, int this {unsigned long load, min_load =ULONG_MAX ;unsigned int min_exit_latency =UINT_MAX ; +s64 min_break_even =S64_MAX ;u64 latest_idle_timestamp =0 ;int least_loaded_cpu = this_cpu;int shallowest_idle_cpu =-1 ;@@ -5810,6 +5811,8 @@ find_idlest_group_cpu(struct sched_group *group, struct task_struct *p, int thisif (available_idle_cpu (i)) {struct rq *rq =cpu_rq (i);struct cpuidle_state *idle =idle_get_state (rq); +s64 break_even =idle_get_break_even (rq); +if (idle && idle->exit_latency < min_exit_latency) {/* * We give priority to a CPU whose idle state @@ -5817,10 +5820,21 @@ find_idlest_group_cpu(struct sched_group *group, struct task_struct *p, int this* of any idle timestamp. */ min_exit_latency = idle->exit_latency; + min_break_even = break_even; latest_idle_timestamp = rq->idle_stamp; shallowest_idle_cpu = i; - }else if ((!idle || idle->exit_latency == min_exit_latency) && - rq->idle_stamp > latest_idle_timestamp) { + }else if ((idle && idle->exit_latency == min_exit_latency) && + break_even < min_break_even) {
kernel/sched/fair.c find_idlest_group_cpu(struct sched_group *group, struct task_struct *p, int this · line 5837
Quoted 10 lines
kernel/sched/fair.c +10
-0+/* +* We give priority to the shallowest +* idle states with the minimal break +* even deadline to decrease the +* probability to choose a CPU which +* did not reach its break even yet +*/ + min_break_even = break_even; + shallowest_idle_cpu = i; + }else if (!idle && rq->idle_stamp > latest_idle_timestamp) {
Shouldn't you retain the original if condition here? You omitted the 2nd part of this check compared to the original condition
(!idle || >>>idle->exit_latency == min_exit_latency<<<)
Quoted 8 lines
kernel/sched/fair.c +0
-0/* * If equal or no active idle state, then * the most recently idled CPU might have kernel/sched/idle.c +0
-0
kernel/sched/idle.c extern char __cpuidle_text_start[], __cpuidle_text_end[]; · line 27
Quoted 10 lines
kernel/sched/idle.c +6
-1@@ -19,7 +19,14 @@ extern char __cpuidle_text_start[], __cpuidle_text_end[];*/ void sched_idle_set_state (struct cpuidle_state *idle_state) { -idle_set_state (this_rq (), idle_state); +struct rq *rq =this_rq (); +ktime_t kt; + +if (likely (idle_state)) { + kt =ktime_add_ns (ktime_get (), idle_state->exit_latency_ns); +idle_set_state (rq, idle_state);
This changes the behavior of the function.
There's a call to sched_idle_set_state(NULL), so with this it'd be a NOP.
Is this intentional?
Don't you need to reset the break_even value if idle_state is NULL too?
Thanks
--
Qais Yousef
Quoted 53 lines
kernel/sched/idle.c +2
-0+idle_set_break_even (rq,ktime_to_ns (kt)); + } }static int __read_mostly cpu_idle_force_poll;kernel/sched/sched.h +20
-0@@ -1015,6 +1015,7 @@ struct rq {#ifdef CONFIG_CPU_IDLE /* Must be inspected within a rcu lock section */ struct cpuidle_state *idle_state; +s64 break_even;#endif };@@ -1850,6 +1851,16 @@ static inline struct cpuidle_state *idle_get_state(struct rq *rq) return rq->idle_state; } + +static inline void idle_set_break_even (struct rq *rq,s64 break_even) +{ + rq->break_even = break_even; +} + +static inline s64 idle_get_break_even (struct rq *rq) +{ +return rq->break_even; +}#else static inline void idle_set_state (struct rq *rq,struct cpuidle_state *idle_state)@@ -1860,6 +1871,15 @@ static inline struct cpuidle_state *idle_get_state(struct rq *rq) {return NULL ; } + +static inline void idle_set_break_even (struct rq *rq,s64 break_even) +{ +} + +static inline s64 idle_get_break_even (struct rq *rq) +{ +return 0 ; +}#endif extern void schedule_idle (void );Signature · 1 line
2.17.1
Hi Qais,
Quoted 15 lines · Qais Yousef
Hi Daniel
Adding Rafael to CC as I think he might be interested in this too.
Quoted 7 lines · Daniel Lezcano
In the idle CPU selection process occuring in the slow path via the
find_idlest_group_cpu()function, we pick up in priority an idle CPU with the shallowest idle state otherwise we fall back to the least loaded CPU.In order to be more energy efficient but without impacting the performances, let's use another criteria: the break even deadline.
What is the break even deadline?
Quoted 8 lines
Quoted 3 lines
At idle time, when we store the idle state the CPU is entering in, we compute the next deadline where the CPU could be woken up without spending more energy to sleep.
I think that's its definition, but could do with more explanation.
So the break even deadline is the time window during which we can abort the CPU while entering its shallowest idle state?
No, it is the moment in absolute time when the min residency is reached.
From Documentation/devicetree/bindings/arm/idle-states.yaml
"
min-residency is defined for a given idle state as the minimum expected residency time for a state (inclusive of preparation and entry) after which choosing that state become the most energy efficient option. A good way to visualise this, is by taking the same graph above and comparing some states energy consumptions plots.
"
Quoted 3 lines
So if we have 2 cpus entering the shallowest idle state, we pick the one that has a faster abort? And the energy saving comes from the fact we avoided unnecessary sleep-just-to-wakeup-immediately cycle?
No, actually it is about to choose a CPU where it has a better chance to have reach its min residency. Basically, when the CPU enters an idle state, that has a cost (cache flush / refill, context saving/restore etc ...), so there is a peak of energy and the CPU has to save energy long enough to compensate this extra consumption.
If the scheduler is constantly waking up an idle CPU before it slept long enough, we lose energy and performance.
Example 1, the CPUs are in a state:
- CPU0 (power down)
- CPU1 (power down)
- CPU2 (WFI)
- CPU3 (power down)
The routine choose CPU2 because it is the shallowest state.
Example 2, the CPUs are in a state:
- CPU0 (power down) (bedl = 1234)
- CPU1 (power down) (bedl = 4321)
- CPU2 (power down) (bedl = 9876)
- CPU3 (power down) (bedl = 3421)
* bedl = break even deadline
The routine choose CPU1 because the bedl is the smallest.
Quoted 19 lines
Quoted 19 lines
At the selection process, we use the shallowest CPU but in addition we choose the one with the minimal break even deadline instead of relying on the
idle_timestamp. When the CPU is idle, the timestamp has less meaning because the CPU could have wake up and sleep again several times without exiting the idle loop. In this case the break even deadline is more relevant as it increases the probability of choosing a CPU which reached its break even.Tested on a synquacer 24 cores, 6 sched domains:
sched/perf and messaging does not show a performance regression. Ran 10 times schbench and adrestia.
with break-even deadline:
-------------------------schbench *99.0th : 14844.8 adrestia / periodic : 57.95 adrestia / single : 49.3
Quoted 8 lines
Quoted 5 lines
Without break-even deadline:
----------------------------schbench / *99.0th : 15017.6 adrestia / periodic : 57 adrestia / single : 55.4Lower is better or worse? The numbers might be popular and maybe I should have known them, but adding some explanation will always help.
* lesser is better
Quoted 1 line
Do you have any energy measurement on the impact of this patch?
No, I don't have any platform allowing that. I've an instrumented big.Little but this patch is not relevant as the EAS takes over.
The only platform I have in my hands now is the synquacer 24 cores which makes sense for this slow path selection.
Quoted 53 lines
Quoted 39 lines
Signed-off-by Daniel Lezcano <[email protected]>--- kernel/sched/fair.c | 18 ++++++++++++++++-- kernel/sched/idle.c | 9 ++++++++- kernel/sched/sched.h | 20 ++++++++++++++++++++ 3 files changed, 44 insertions(+), 3 deletions(-)kernel/sched/fair.c +6
-2@@ -5793,6 +5793,7 @@ find_idlest_group_cpu(struct sched_group *group, struct task_struct *p, int this {unsigned long load, min_load =ULONG_MAX ;unsigned int min_exit_latency =UINT_MAX ; +s64 min_break_even =S64_MAX ;u64 latest_idle_timestamp =0 ;int least_loaded_cpu = this_cpu;int shallowest_idle_cpu =-1 ;@@ -5810,6 +5811,8 @@ find_idlest_group_cpu(struct sched_group *group, struct task_struct *p, int thisif (available_idle_cpu (i)) {struct rq *rq =cpu_rq (i);struct cpuidle_state *idle =idle_get_state (rq); +s64 break_even =idle_get_break_even (rq); +if (idle && idle->exit_latency < min_exit_latency) {/* * We give priority to a CPU whose idle state @@ -5817,10 +5820,21 @@ find_idlest_group_cpu(struct sched_group *group, struct task_struct *p, int this* of any idle timestamp. */ min_exit_latency = idle->exit_latency; + min_break_even = break_even; latest_idle_timestamp = rq->idle_stamp; shallowest_idle_cpu = i; - }else if ((!idle || idle->exit_latency == min_exit_latency) && - rq->idle_stamp > latest_idle_timestamp) { + }else if ((idle && idle->exit_latency == min_exit_latency) && + break_even < min_break_even) {kernel/sched/fair.c find_idlest_group_cpu(struct sched_group *group, struct task_struct *p, int this · line 5837
Quoted 10 lines
kernel/sched/fair.c +10
-0+/* +* We give priority to the shallowest +* idle states with the minimal break +* even deadline to decrease the +* probability to choose a CPU which +* did not reach its break even yet +*/ + min_break_even = break_even; + shallowest_idle_cpu = i; + }else if (!idle && rq->idle_stamp > latest_idle_timestamp) {Shouldn't you retain the original if condition here? You omitted the 2nd part of this check compared to the original condition
Quoted 1 line
(!idle || >>>idle->exit_latency == min_exit_latency<<<)
It is done on purpose because of the condition right before.
Quoted 21 lines
Quoted 8 lines
kernel/sched/fair.c +0
-0/* * If equal or no active idle state, then * the most recently idled CPU might have kernel/sched/idle.c +0
-0kernel/sched/idle.c extern char __cpuidle_text_start[], __cpuidle_text_end[]; · line 27
Quoted 10 lines
kernel/sched/idle.c +6
-1@@ -19,7 +19,14 @@ extern char __cpuidle_text_start[], __cpuidle_text_end[];*/ void sched_idle_set_state (struct cpuidle_state *idle_state) { -idle_set_state (this_rq (), idle_state); +struct rq *rq =this_rq (); +ktime_t kt; + +if (likely (idle_state)) { + kt =ktime_add_ns (ktime_get (), idle_state->exit_latency_ns); +idle_set_state (rq, idle_state);This changes the behavior of the function.
Quoted 3 lines
There's a call to
sched_idle_set_state(NULL), so with this it'd be a NOP.Is this intentional?
Nope, thanks for spotting it. It should be:
void sched_idle_set_state(struct cpuidle_state *idle_state) {
- idle_set_state(this_rq(), idle_state); + struct rq *rq = this_rq(); + idle_set_state(rq, idle_state);
+
+ if (likely(idle_state)) {
+ ktime_t kt = ktime_add_ns(ktime_get(),
+ idle_state->exit_latency_ns);
+ idle_set_break_even(rq, ktime_to_ns(kt));
+ }
}
Quoted 1 line
Don't you need to reset the
break_evenvalue ifidle_stateis NULL too?
If the idle_state is NULL, the routine won't use the break_even.
Signature · 5 lines
<http://www.linaro.org/> Linaro.org │ Open source software for ARM SoCs Follow Linaro: <http://www.facebook.com/pages/Linaro> Facebook | <http://twitter.com/#!/linaroorg> Twitter | <http://www.linaro.org/linaro-blog/> Blog
Quoted 67 lines · Daniel Lezcano
Hi Qais,
Quoted 15 lines · Qais Yousef
Hi Daniel
Adding Rafael to CC as I think he might be interested in this too.
Quoted 7 lines · Daniel Lezcano
In the idle CPU selection process occuring in the slow path via the
find_idlest_group_cpu()function, we pick up in priority an idle CPU with the shallowest idle state otherwise we fall back to the least loaded CPU.In order to be more energy efficient but without impacting the performances, let's use another criteria: the break even deadline.
What is the break even deadline?
Quoted 8 lines
Quoted 3 lines
At idle time, when we store the idle state the CPU is entering in, we compute the next deadline where the CPU could be woken up without spending more energy to sleep.
I think that's its definition, but could do with more explanation.
So the break even deadline is the time window during which we can abort the CPU while entering its shallowest idle state?
No, it is the moment in absolute time when the min residency is reached.
From
Documentation/devicetree/bindings/arm/idle-states.yaml"
min-residency is defined for a given idle state as the minimum expected residency time for a state (inclusive of preparation and entry) after which choosing that state become the most energy efficient option. A good way to visualise this, is by taking the same graph above and comparing some states energy consumptions plots.
"Quoted 3 lines
So if we have 2 cpus entering the shallowest idle state, we pick the one that has a faster abort? And the energy saving comes from the fact we avoided unnecessary sleep-just-to-wakeup-immediately cycle?
No, actually it is about to choose a CPU where it has a better chance to have reach its min residency. Basically, when the CPU enters an idle state, that has a cost (cache flush / refill, context saving/restore etc ...), so there is a peak of energy and the CPU has to save energy long enough to compensate this extra consumption.
If the scheduler is constantly waking up an idle CPU before it slept long enough, we lose energy and performance.
Example 1, the CPUs are in a state:
- CPU0 (power down)
- CPU1 (power down)
- CPU2 (WFI)
- CPU3 (power down)The routine choose CPU2 because it is the shallowest state.
Example 2, the CPUs are in a state:
- CPU0 (power down) (bedl = 1234)
- CPU1 (power down) (bedl = 4321)
- CPU2 (power down) (bedl = 9876)
- CPU3 (power down) (bedl = 3421)
Quoted 3 lines
* bedl = break even deadline
The routine choose CPU1 because the bedl is the smallest.
Thanks for the explanation and the reference. The idle-state.yaml has a nice diagram. I won't insist, but I think including the definition of break even will help a lot to make the patch more understandable.
[...]
Quoted 6 lines
Quoted 4 lines
Shouldn't you retain the original if condition here? You omitted the 2nd part of this check compared to the original condition
(!idle || >>>idle->exit_latency == min_exit_latency<<<)It is done on purpose because of the condition right before.
I see it now. If denote the condition as B. If it was false then the OR will reduce to !idle. But if it was True, then which path you take will depend only on state of idle too, which you check in both paths.
[...]
Quoted 17 lines
Nope, thanks for spotting it. It should be:
void
sched_idle_set_state(struct cpuidle_state *idle_state){kernel/sched/idle.c +8
-1-idle_set_state (this_rq (), idle_state); +struct rq *rq =this_rq (); +idle_set_state (rq, idle_state); + +if (likely (idle_state)) { +ktime_t kt =ktime_add_ns (ktime_get (), + idle_state->exit_latency_ns); +idle_set_break_even (rq,ktime_to_ns (kt)); + } }
Quoted 3 lines
Quoted 1 line
Don't you need to reset the
break_evenvalue ifidle_stateis NULL too?If the
idle_stateis NULL, the routine won't use thebreak_even.
+1
Thanks
--
Qais Yousef
Quoted 12 lines · Daniel Lezcano
In the idle CPU selection process occuring in the slow path via the
find_idlest_group_cpu()function, we pick up in priority an idle CPU with the shallowest idle state otherwise we fall back to the least loaded CPU.In order to be more energy efficient but without impacting the performances, let's use another criteria: the break even deadline.
At idle time, when we store the idle state the CPU is entering in, we compute the next deadline where the CPU could be woken up without spending more energy to sleep.
Quoted 8 lines
At the selection process, we use the shallowest CPU but in addition we choose the one with the minimal break even deadline instead of relying on the
idle_timestamp. When the CPU is idle, the timestamp has less meaning because the CPU could have wake up and sleep again several times without exiting the idle loop. In this case the break even deadline is more relevant as it increases the probability of choosing a CPU which reached its break even.
Ok so we still favour smallest exit latency, but if we have to pick among several CPUs with the same exit latency, we can use the break even. I'll want to test this on stuff, but I like the overall idea.
Quoted 13 lines
kernel/sched/fair.c +1
-0@@ -5793,6 +5793,7 @@ find_idlest_group_cpu(struct sched_group *group, struct task_struct *p, int this {unsigned long load, min_load =ULONG_MAX ;unsigned int min_exit_latency =UINT_MAX ; +s64 min_break_even =S64_MAX ;u64 latest_idle_timestamp =0 ;int least_loaded_cpu = this_cpu;int shallowest_idle_cpu =-1 ;
kernel/sched/fair.c find_idlest_group_cpu(struct sched_group *group, struct task_struct *p, int this · line 5815
Quoted 5 lines
kernel/sched/fair.c +2
-0@@ -5810,6 +5811,8 @@ find_idlest_group_cpu(struct sched_group *group, struct task_struct *p, int thisif (available_idle_cpu (i)) {struct rq *rq =cpu_rq (i);struct cpuidle_state *idle =idle_get_state (rq); +s64 break_even =idle_get_break_even (rq); +
Nit: there's tabs in that line break.
Quoted 17 lines
kernel/sched/fair.c +6
-2if (idle && idle->exit_latency < min_exit_latency) {/* * We give priority to a CPU whose idle state @@ -5817,10 +5820,21 @@ find_idlest_group_cpu(struct sched_group *group, struct task_struct *p, int this* of any idle timestamp. */ min_exit_latency = idle->exit_latency; + min_break_even = break_even; latest_idle_timestamp = rq->idle_stamp; shallowest_idle_cpu = i; - }else if ((!idle || idle->exit_latency == min_exit_latency) && - rq->idle_stamp > latest_idle_timestamp) { + }else if ((idle && idle->exit_latency == min_exit_latency) && + break_even < min_break_even) { +/* +* We give priority to the shallowest +* idle states with the minimal break
kernel/sched/fair.c find_idlest_group_cpu(struct sched_group *group, struct task_struct *p, int this · line 5840
Quoted 10 lines
kernel/sched/fair.c +7
-0+* even deadline to decrease the +* probability to choose a CPU which +* did not reach its break even yet +*/ + min_break_even = break_even; + shallowest_idle_cpu = i; + }else if (!idle && rq->idle_stamp > latest_idle_timestamp) {/* * If equal or no active idle state, then * the most recently idled CPU might have
That comment will need to be changed as well, that condition now only catters to the !idle case.
With that said, that comment actually raises a valid point: picking recently idled CPUs might give us warmer cache. So by using the break even stat, we can end up picking CPUs with colder caches (have been idling for longer) than the current logic would. I suppose more testing will tell us where we stand.
kernel/sched/idle.c extern char __cpuidle_text_start[], __cpuidle_text_end[]; · line 25
Quoted 13 lines
kernel/sched/idle.c +4
-1@@ -19,7 +19,14 @@ extern char __cpuidle_text_start[], __cpuidle_text_end[];*/ void sched_idle_set_state (struct cpuidle_state *idle_state) { -idle_set_state (this_rq (), idle_state); +struct rq *rq =this_rq (); +ktime_t kt; + +if (likely (idle_state)) {
Doesn't this break things? e.g. calling this with NULL?
kernel/sched/idle.c extern char __cpuidle_text_start[], __cpuidle_text_end[]; · line 26
Quoted 1 line
kernel/sched/idle.c +1
-0+ kt =ktime_add_ns (ktime_get (), idle_state->exit_latency_ns);
ISTR there were objections to using ktime stuff in the scheduler, but I can't remember anything specific. If we only call into it when actually entering an idle state (and not when we're exiting one), I suppose that would be fine?
Quoted 11 lines
kernel/sched/idle.c +3
-0+idle_set_state (rq, idle_state); +idle_set_break_even (rq,ktime_to_ns (kt)); + } }static int __read_mostly cpu_idle_force_poll;kernel/sched/sched.h +0
-0
kernel/sched/sched.h struct rq { · line 1018
Quoted 4 lines
kernel/sched/sched.h +1
-0@@ -1015,6 +1015,7 @@ struct rq {#ifdef CONFIG_CPU_IDLE /* Must be inspected within a rcu lock section */ struct cpuidle_state *idle_state; +s64 break_even;
Why signed? This should be purely positive, right?
Quoted 7 lines
kernel/sched/sched.h +0
-0#endif };@@ -1850,6 +1851,16 @@ static inline struct cpuidle_state *idle_get_state(struct rq *rq)return rq->idle_state; }
kernel/sched/sched.h static inline struct cpuidle_state *idle_get_state(struct rq *rq) · line 1863
Quoted 10 lines
kernel/sched/sched.h +10
-0+ +static inline void idle_set_break_even (struct rq *rq,s64 break_even) +{ + rq->break_even = break_even; +} + +static inline s64 idle_get_break_even (struct rq *rq) +{ +return rq->break_even; +}
I'm not super familiar with the callsites for setting idle states, what's the locking situation there? Do we have any rq lock?
In find_idlest_group_cpu() we're in a read-side RCU section, so the idle_state is protected (speaking of which, why isn't idle_get_state() using rcu_dereference()?), but that's doesn't cover the break even.
IIUC at the very least we may want to give them the READ/WRITE_ONCE() treatment.
Quoted 70 lines · Valentin Schneider
Quoted 12 lines · Daniel Lezcano
In the idle CPU selection process occuring in the slow path via the
find_idlest_group_cpu()function, we pick up in priority an idle CPU with the shallowest idle state otherwise we fall back to the least loaded CPU.In order to be more energy efficient but without impacting the performances, let's use another criteria: the break even deadline.
At idle time, when we store the idle state the CPU is entering in, we compute the next deadline where the CPU could be woken up without spending more energy to sleep.
Quoted 8 lines
At the selection process, we use the shallowest CPU but in addition we choose the one with the minimal break even deadline instead of relying on the
idle_timestamp. When the CPU is idle, the timestamp has less meaning because the CPU could have wake up and sleep again several times without exiting the idle loop. In this case the break even deadline is more relevant as it increases the probability of choosing a CPU which reached its break even.Ok so we still favour smallest exit latency, but if we have to pick among several CPUs with the same exit latency, we can use the break even. I'll want to test this on stuff, but I like the overall idea.
Quoted 13 lines
kernel/sched/fair.c +1
-0@@ -5793,6 +5793,7 @@ find_idlest_group_cpu(struct sched_group *group, struct task_struct *p, int this {unsigned long load, min_load =ULONG_MAX ;unsigned int min_exit_latency =UINT_MAX ; +s64 min_break_even =S64_MAX ;u64 latest_idle_timestamp =0 ;int least_loaded_cpu = this_cpu;int shallowest_idle_cpu =-1 ;kernel/sched/fair.c find_idlest_group_cpu(struct sched_group *group, struct task_struct *p, int this · line 5815
Quoted 5 lines
kernel/sched/fair.c +2
-0@@ -5810,6 +5811,8 @@ find_idlest_group_cpu(struct sched_group *group, struct task_struct *p, int thisif (available_idle_cpu (i)) {struct rq *rq =cpu_rq (i);struct cpuidle_state *idle =idle_get_state (rq); +s64 break_even =idle_get_break_even (rq); +Nit: there's tabs in that line break.
Quoted 22 lines
kernel/sched/fair.c +11
-2if (idle && idle->exit_latency < min_exit_latency) {/* * We give priority to a CPU whose idle state @@ -5817,10 +5820,21 @@ find_idlest_group_cpu(struct sched_group *group, struct task_struct *p, int this* of any idle timestamp. */ min_exit_latency = idle->exit_latency; + min_break_even = break_even; latest_idle_timestamp = rq->idle_stamp; shallowest_idle_cpu = i; - }else if ((!idle || idle->exit_latency == min_exit_latency) && - rq->idle_stamp > latest_idle_timestamp) { + }else if ((idle && idle->exit_latency == min_exit_latency) && + break_even < min_break_even) { +/* +* We give priority to the shallowest +* idle states with the minimal break +* even deadline to decrease the +* probability to choose a CPU which +* did not reach its break even yet +*/ + min_break_even = break_even;
Quoted 8 lines
kernel/sched/fair.c find_idlest_group_cpu(struct sched_group *group, struct task_struct *p, int this · line 5840
Quoted 5 lines
kernel/sched/fair.c +2
-0+ shallowest_idle_cpu = i; + }else if (!idle && rq->idle_stamp > latest_idle_timestamp) {/* * If equal or no active idle state, then * the most recently idled CPU might have That comment will need to be changed as well, that condition now only catters to the !idle case.
Right.
Quoted 5 lines
With that said, that comment actually raises a valid point: picking recently idled CPUs might give us warmer cache. So by using the break even stat, we can end up picking CPUs with colder caches (have been idling for longer) than the current logic would. I suppose more testing will tell us where we stand.
Actually I'm not sure this comment still applies. If the CPU is powered down, the cache is flushed or we can be picking up CPU with their cache totally trashed by interrupt processing.
Quoted 7 lines
Quoted 7 lines
kernel/sched/idle.c +0
-0@@ -19,7 +19,14 @@ extern char __cpuidle_text_start[], __cpuidle_text_end[];*/ void sched_idle_set_state (struct cpuidle_state *idle_state)
Quoted 8 lines
kernel/sched/idle.c extern char __cpuidle_text_start[], __cpuidle_text_end[]; · line 25
Quoted 6 lines
kernel/sched/idle.c +4
-1{ -idle_set_state (this_rq (), idle_state); +struct rq *rq =this_rq (); +ktime_t kt; + +if (likely (idle_state)) {Doesn't this break things? e.g. calling this with NULL?
Yes, Qais spotted it.
Quoted 6 lines
kernel/sched/idle.c extern char __cpuidle_text_start[], __cpuidle_text_end[]; · line 26
Quoted 1 line
kernel/sched/idle.c +1
-0+ kt =ktime_add_ns (ktime_get (), idle_state->exit_latency_ns);ISTR there were objections to using ktime stuff in the scheduler, but I can't remember anything specific. If we only call into it when actually entering an idle state (and not when we're exiting one), I suppose that would be fine?
In this slow path it is fine. In the fast path, it is unacceptable.
Quoted 5 lines
Quoted 5 lines
kernel/sched/idle.c +3
-0+idle_set_state (rq, idle_state); +idle_set_break_even (rq,ktime_to_ns (kt)); + } }
Quoted 12 lines
kernel/sched/sched.h struct rq { · line 1018
Quoted 10 lines
kernel/sched/idle.c +0
-0static int __read_mostly cpu_idle_force_poll;kernel/sched/sched.h +1
-0@@ -1015,6 +1015,7 @@ struct rq {#ifdef CONFIG_CPU_IDLE /* Must be inspected within a rcu lock section */ struct cpuidle_state *idle_state; +s64 break_even;Why signed? This should be purely positive, right?
It should be, but s64 complies with the functions ktime_to_ns signature.
static inline s64 ktime_to_ns(const ktime_t kt)
Quoted 5 lines
Quoted 5 lines
kernel/sched/sched.h +0
-0#endif };@@ -1850,6 +1851,16 @@ static inline struct cpuidle_state *idle_get_state(struct rq *rq)
Quoted 15 lines
kernel/sched/sched.h static inline struct cpuidle_state *idle_get_state(struct rq *rq) · line 1863
Quoted 12 lines
kernel/sched/sched.h +10
-0return rq->idle_state; } + +static inline void idle_set_break_even (struct rq *rq,s64 break_even) +{ + rq->break_even = break_even; +} + +static inline s64 idle_get_break_even (struct rq *rq) +{ +return rq->break_even; +}I'm not super familiar with the callsites for setting idle states, what's the locking situation there? Do we have any rq lock?
It is safe, we are under rcu, this section was discussed several years ago when introducing the idle_set_state():
https://lkml.org/lkml/2014/9/19/332
Quoted 7 lines
In
find_idlest_group_cpu()we're in a read-side RCU section, so theidle_stateis protected (speaking of which, why isn'tidle_get_state()usingrcu_dereference()?), but that's doesn't cover the break even.IIUC at the very least we may want to give them the READ/WRITE_ONCE() treatment.
Signature · 5 lines
<http://www.linaro.org/> Linaro.org │ Open source software for ARM SoCs Follow Linaro: <http://www.facebook.com/pages/Linaro> Facebook | <http://twitter.com/#!/linaroorg> Twitter | <http://www.linaro.org/linaro-blog/> Blog
Quoted 19 lines · Daniel Lezcano
Quoted 5 lines
With that said, that comment actually raises a valid point: picking recently idled CPUs might give us warmer cache. So by using the break even stat, we can end up picking CPUs with colder caches (have been idling for longer) than the current logic would. I suppose more testing will tell us where we stand.
Actually I'm not sure this comment still applies. If the CPU is powered down, the cache is flushed or we can be picking up CPU with their cache totally trashed by interrupt processing.
Quoted 8 lines
kernel/sched/sched.h struct rq { · line 1018
Quoted 6 lines
+++
b/kernel/sched/sched.hkernel/sched/sched.h +1
-0@@ -1015,6 +1015,7 @@ struct rq {#ifdef CONFIG_CPU_IDLE /* Must be inspected within a rcu lock section */ struct cpuidle_state *idle_state; +s64 break_even;Why signed? This should be purely positive, right?
Quoted 4 lines
It should be, but s64 complies with the functions
ktime_to_nssignature.static inline s64
ktime_to_ns(const ktime_t kt)
Would there be harm then in simply storing:
ktime_get_ns() + idle_state->exit_latency_ns
(which is u64)?
Quoted 21 lines
Quoted 5 lines
Quoted 5 lines
(quoted diff) +0
-0#endif };@@ -1850,6 +1851,16 @@ static inline struct cpuidle_state *idle_get_state(struct rq *rq)Quoted 15 lines
kernel/sched/sched.h static inline struct cpuidle_state *idle_get_state(struct rq *rq) · line 1863
Quoted 12 lines
kernel/sched/sched.h +10
-0return rq->idle_state; } + +static inline void idle_set_break_even (struct rq *rq,s64 break_even) +{ + rq->break_even = break_even; +} + +static inline s64 idle_get_break_even (struct rq *rq) +{ +return rq->break_even; +}I'm not super familiar with the callsites for setting idle states, what's the locking situation there? Do we have any rq lock?
Quoted 5 lines
It is safe, we are under rcu, this section was discussed several years ago when introducing the
idle_set_state():
Thanks for the link!
So while we (should) have the relevant barriers, there can still be concurrent writing (from the CPU entering/leaving idle) and reading (from the CPU gathering stats).
rcu_dereference() gives you READ_ONCE(), and the rcu_assign_pointer() should give you an smp_store_release(). What I'm thinking here is, if we have reasons not to use the RCU primitives, we should at least slap some READ/WRITE_ONCE() to the accesses. Also, can RCU even do anything about scalar values like the break even you're storing?
Quoted 7 lines
Quoted 7 lines
In
find_idlest_group_cpu()we're in a read-side RCU section, so theidle_stateis protected (speaking of which, why isn'tidle_get_state()usingrcu_dereference()?), but that's doesn't cover the break even.IIUC at the very least we may want to give them the READ/WRITE_ONCE() treatment.
Hi Valentin,
[cc'ing Thomas Gleixner]
Quoted 23 lines · Valentin Schneider
Quoted 21 lines · Daniel Lezcano
Quoted 5 lines
With that said, that comment actually raises a valid point: picking recently idled CPUs might give us warmer cache. So by using the break even stat, we can end up picking CPUs with colder caches (have been idling for longer) than the current logic would. I suppose more testing will tell us where we stand.
Actually I'm not sure this comment still applies. If the CPU is powered down, the cache is flushed or we can be picking up CPU with their cache totally trashed by interrupt processing.
Quoted 8 lines
kernel/sched/sched.h struct rq { · line 1018
Quoted 6 lines
+++
b/kernel/sched/sched.hkernel/sched/sched.h +1
-0@@ -1015,6 +1015,7 @@ struct rq {#ifdef CONFIG_CPU_IDLE /* Must be inspected within a rcu lock section */ struct cpuidle_state *idle_state; +s64 break_even;Why signed? This should be purely positive, right?
It should be, but s64 complies with the functions
ktime_to_nssignature.
Quoted 8 lines
Quoted 2 lines
static inline s64
ktime_to_ns(const ktime_t kt)Would there be harm then in simply storing:
ktime_get_ns()+idle_state->exit_latency_ns(which is u64)?
Actually I'm not sure, ktime_get_ns() is correct, it returns an u64 but it is actually returning:
return ktime_to_ns(ktime_get());
where ktime_to_ns is returning a s64.
There are the following functions:
static inline u64 ktime_get_coarse_ns(void) static inline u64 ktime_get_coarse_real_ns(void) static inline u64 ktime_get_coarse_boottime_ns(void) static inline u64 ktime_get_coarse_clocktai_ns(void) static inline u64 ktime_get_ns(void)
static inline u64 ktime_get_real_ns(void) static inline u64 ktime_get_boottime_ns(void) static inline u64 ktime_get_clocktai_ns(void) static inline u64 ktime_get_raw_ns(void)
extern u64 ktime_get_mono_fast_ns(void); extern u64 ktime_get_raw_fast_ns(void); extern u64 ktime_get_boot_fast_ns(void); extern u64 ktime_get_real_fast_ns(void);
They are all based on ktime_get_ns() which returns a s64.
Not sure this type mismatch was done on purpose or not.
Thomas?
Signature · 5 lines
<http://www.linaro.org/> Linaro.org │ Open source software for ARM SoCs Follow Linaro: <http://www.facebook.com/pages/Linaro> Facebook | <http://twitter.com/#!/linaroorg> Twitter | <http://www.linaro.org/linaro-blog/> Blog