Messages in this thread Patch in this message | | | Date | Thu, 07 May 2015 17:31:25 +0200 | From | Daniel Lezcano <> | Subject | Re: [PATCH 3/3] sched: fair: Fix wrong idle timestamp usage |
| |
On 04/15/2015 06:02 PM, Peter Zijlstra wrote: > On Wed, Apr 15, 2015 at 05:43:17PM +0200, Daniel Lezcano wrote: >> On 04/15/2015 02:18 PM, Peter Zijlstra wrote: >>> On Wed, Apr 15, 2015 at 12:00:24PM +0200, Daniel Lezcano wrote: >>>> The find_idlest_cpu is assuming the rq->idle_stamp information reflects when >>>> the cpu entered the idle state. This is wrong as the cpu may exit and enter >>>> the idle state several times without the rq->idle_stamp being updated. >>> >>> Sure, but you forgot to tell us why it matters. >> >> Yes, right. Thanks for pointing this out. >> >> Assuming we are in the situation where there are several idle cpus in the >> same idle state. >> >> With the current code, the function find_idlest_cpu will choose a cpu with >> the shortest idle duration. This information is based on the rq->idle_stamp >> variable and is correct until one of the idle cpu is exiting the >> cpuidle_enter function and re-entering it again. As soon as this happen, the >> rq->idle_stamp value is no longer a reliable information. >> >> Example: >> >> * CPU0 and CPU1 are running >> * CPU2 and CPU3 are in the C3 state. >> * CPU2 entered idle at T2 >> * CPU3 entered idle at T3 >> * T2 < T3 >> >> The function find_idlest_cpu will choose CPU3 because it has a shorter idle >> duration. >> >> Then CPU3 is woken up by an interrupt, process it and re-enter idle C3. >> >> The information will still give the out to date information T2 < T3 and >> find_idlest_cpu will choose CPU2 instead of CPU3. >> >> Even if that shouldn't have a big impact on the performance and energy side, >> we are dealing with a wrong information preventing us to improve the energy >> side later (eg. prevent to wakeup a cpu which did not reach its target >> residency yet). > > Right, I figured as much; but no tangible results or behavioural fail > observed. > >>> Urgh, you made horrid code more horrible. >>> >>> And all without reason. >> >> Ok. What is horrible ? The 'if then else' blocks or the algorithm itself ? > > Yeah the amount and depth of branches. I briefly tried to see if it > could be fixed but came up empty. Maybe I should try harder :-)
Here's a try here (patch below based on top of this patchset).
There is a cpumask for the idle cpus being set / cleared when entering / exiting the idle loop.
The function find_idlest_cpu uses this mask to separate idle cpus from running cpus.
So the benefit of this approach is we don't lookup on all sched_group's cpus but just a subset.
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index b44f1ad..b6f671e 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -4686,67 +4686,89 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p, return idlest; }
-/* - * find_idlest_cpu - find the idlest cpu among the cpus in group. - */ -static int -find_idlest_cpu(struct sched_group *group, struct task_struct *p, int this_cpu) +struct cpumask idle_cpus_mask; + +static int find_shallowest_idle_cpu(struct cpumask *cpus) { - unsigned long load, min_load = ULONG_MAX; - unsigned int min_exit_latency = UINT_MAX; u64 latest_idle_timestamp = 0; - int least_loaded_cpu = this_cpu; - int shallowest_idle_cpu = -1; - int i; + unsigned min_exit_latency = UINT_MAX; + int i, cpu = -1;
- /* Traverse only the allowed CPUs */ - for_each_cpu_and(i, sched_group_cpus(group), tsk_cpus_allowed(p)) { - if (idle_cpu(i)) { - struct rq *rq = cpu_rq(i); - struct cpuidle_state *idle = idle_get_state(rq); - - if (idle) { - if (idle->exit_latency < min_exit_latency) { - /* - * We give priority to a CPU - * whose idle state has the - * smallest exit latency - * irrespective of any idle - * timestamp. - */ - min_exit_latency = idle->exit_latency; - latest_idle_timestamp = idle->idle_stamp; - shallowest_idle_cpu = i; - } else if (idle->exit_latency == min_exit_latency && - idle->idle_stamp > latest_idle_timestamp) { - /* - * If the CPU is in the same - * idle state, choose the more - * recent one as it might have - * a warmer cache - */ - latest_idle_timestamp = idle->idle_stamp; - shallowest_idle_cpu = i; - } - } else if (rq->idle_stamp > latest_idle_timestamp) { - /* - * If no active idle state, then the - * most recent idled CPU might have a - * warmer cache - */ + for_each_cpu(i, cpus) { + + struct rq *rq = cpu_rq(i); + struct cpuidle_state *state = idle_get_state(rq); + + if (!state) { + + if (rq->idle_stamp > latest_idle_timestamp) { latest_idle_timestamp = rq->idle_stamp; - shallowest_idle_cpu = i; - } - } else if (shallowest_idle_cpu == -1) { - load = weighted_cpuload(i); - if (load < min_load || (load == min_load && i == this_cpu)) { - min_load = load; - least_loaded_cpu = i; + cpu = i; } + + continue; + } + + if (state->exit_latency < min_exit_latency) { + /* + * We give priority to a CPU whose idle state + * has the smallest exit latency irrespective + * of any idle timestamp. + */ + min_exit_latency = state->exit_latency; + cpu = i; + + continue; + } + + if (state->exit_latency == min_exit_latency && + state->idle_stamp > latest_idle_timestamp) { + /* + * If the CPU is in the same idle state, + * choose the more recent one as it might have + * a warmer cache + */ + cpu = i; + } + } + + return cpu; +} + +static int find_least_loaded_cpu(struct cpumask *cpus) +{ + int i, cpu, this_cpu; + int min_load = ULONG_MAX, load = weighted_cpuload(cpu); + + cpu = this_cpu = smp_processor_id(); + + for_each_cpu(i, cpus) { + if (load < min_load || (load == min_load && i == this_cpu)) { + min_load = load; + cpu = i; } }
- return shallowest_idle_cpu != -1 ? shallowest_idle_cpu : least_loaded_cpu; + return cpu; +} + +/* + * find_idlest_cpu - find the idlest cpu among the cpus in group. + */ +static int +find_idlest_cpu(struct sched_group *group, struct task_struct *p) +{ + struct cpumask tmp, idle_cpus, running_cpus; + + cpumask_and(&tmp, sched_group_cpus(group), tsk_cpus_allowed(p)); + + cpumask_and(&idle_cpus, &idle_cpus_mask, &tmp); + + cpumask_andnot(&running_cpus, &idle_cpus_mask, &tmp); + + return !cpumask_empty(&idle_cpus) ? + find_shallowest_idle_cpu(&idle_cpus) : + find_least_loaded_cpu(&running_cpus); }
/* @@ -4887,7 +4909,7 @@ select_task_rq_fair(struct task_struct *p, int prev_cpu, int sd_flag, int wake_f continue; }
- new_cpu = find_idlest_cpu(group, p, cpu); + new_cpu = find_idlest_cpu(group, p); if (new_cpu == -1 || new_cpu == cpu) { /* Now try balancing at a lower domain level of cpu */ sd = sd->child; diff --git a/kernel/sched/idle.c b/kernel/sched/idle.c index 80014a1..b2aa008 100644 --- a/kernel/sched/idle.c +++ b/kernel/sched/idle.c @@ -217,6 +217,8 @@ use_default: */ static void cpu_idle_loop(void) { + int cpu = smp_processor_id(); + while (1) { /* * If the arch has a polling bit, we maintain an invariant: @@ -230,6 +232,8 @@ static void cpu_idle_loop(void) __current_set_polling(); tick_nohz_idle_enter();
+ cpumask_set_cpu(cpu, &idle_cpus_mask); + while (!need_resched()) { check_pgt_cache(); rmb(); @@ -257,6 +261,8 @@ static void cpu_idle_loop(void) arch_cpu_idle_exit(); }
+ cpumask_clear_cpu(cpu, &idle_cpus_mask); + /* * Since we fell out of the loop above, we know * TIF_NEED_RESCHED must be set, propagate it into diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h index e0e1299..a14d833 100644 --- a/kernel/sched/sched.h +++ b/kernel/sched/sched.h @@ -544,6 +544,8 @@ struct root_domain {
extern struct root_domain def_root_domain;
+extern struct cpumask idle_cpus_mask; + #endif /* CONFIG_SMP */
/*
-- <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
| |