sched: change nohz idle load balancing logic to push model
Subsystems (2)
cover sched: change nohz idle load balancing logic to push model
This is an updated version of patchset which is posted earlier at
http://lkml.org/lkml/2009/12/10/470
Description:
Existing nohz idle load balance logic uses the pull model, with one idle load balancer CPU nominated on any partially idle system and that balancer CPU not going into nohz mode. With the periodic tick, the balancer does the idle balancing on behalf of all the CPUs in nohz mode.
This is not very optimal and has few issues:
* the balancer will continue to have periodic ticks and wakeup frequently (HZ rate), even though it may not have any rebalancing to do on behalf of any of the idle CPUs.
* On x86 and CPUs that have APIC timer stoppage on idle CPUs, this periodic wakeup can result in an additional interrupt on a CPU doing the timer broadcast.
The alternative is to have a push model, where all idle CPUs can enter nohz mode and any busy CPU kicks one of the idle CPUs to take care of idle balancing on behalf of a group of idle CPUs.
Following patches switches idle load balancer to this push approach.
Updates from the previous version:
* Busy CPU uses send_remote_softirq() for invoking SCHED_SOFTIRQ on the idle load balancing cpu, which does the load balancing on behalf of all the idle CPUs.
* Dropped the per NUMA node nohz load balancing as it doesn't detect certain imbalance scenarios. This will be addressed later.
PATCH 1/7 softirq: Add a no local fallback option to send_remote_softirq
From: Venkatesh Pallipadi <[email protected]>
Subject: softirq: Add a no local fallback option to send_remote_softirq send_remote_softirq and __send_remote_softirq fallback to triggering the softirq on local CPU when __try_remote_softirq fails. In certain circumstances (like the SCHED_SOFTIRQ usage in following patch), the softirq should only run on target CPUs if it runs. This new option helps such callers.
As there seem to be no current users of send_remote_softirq in tree today, added this option to current API instead of introducing a new API.
--- include/linux/interrupt.h | 5 +++-- kernel/softirq.c | 12 ++++++++---- 2 files changed, 11 insertions(+), 6 deletions(-)
include/linux/interrupt.h +3 -2
@@ -419,13 +419,14 @@ DECLARE_PER_CPU(struct list_head [NR_SOF/* Try to send a softirq to a remote cpu. If this cannot be done, the * work will be queued to the local cpu. */ -extern void send_remote_softirq (struct call_single_data *cp,int cpu,int softirq); +extern void send_remote_softirq (struct call_single_data *cp,int cpu, +int softirq,int fallback);/* Like send_remote_softirq(), but the caller must disable local cpu interrupts * and compute the current cpu, passed in as 'this_cpu'. */ extern void __send_remote_softirq (struct call_single_data *cp,int cpu, -int this_cpu,int softirq); +int this_cpu,int softirq,int fallback);/* Tasklets --- multithreaded analogue of BHs.
kernel/softirq.c +8 -4
@@ -610,9 +610,12 @@ static int __try_remote_softirq(struct c* * Interrupts must be disabled. */ -void __send_remote_softirq (struct call_single_data *cp,int cpu,int this_cpu,int softirq) +void __send_remote_softirq (struct call_single_data *cp,int cpu,int this_cpu, +int softirq,int fallback) { -if (cpu == this_cpu ||__try_remote_softirq (cp, cpu, softirq)) +if (cpu == this_cpu) +__local_trigger (cp, softirq); +else if (__try_remote_softirq (cp, cpu, softirq) && fallback)__local_trigger (cp, softirq); }EXPORT_SYMBOL (__send_remote_softirq);
@@ -626,14 +629,15 @@ EXPORT_SYMBOL(__send_remote_softirq);* Like __send_remote_softirq except that disabling interrupts and * computing the current cpu is done for the caller. */ -void send_remote_softirq (struct call_single_data *cp,int cpu,int softirq) +void send_remote_softirq (struct call_single_data *cp,int cpu,int softirq, +int fallback) {unsigned long flags;int this_cpu;local_irq_save (flags); this_cpu =smp_processor_id (); -__send_remote_softirq (cp, cpu, this_cpu, softirq); +__send_remote_softirq (cp, cpu, this_cpu, softirq, fallback);local_irq_restore (flags); }EXPORT_SYMBOL (send_remote_softirq);
PATCH 2/7 softirq: add init_remote_softirq_csd()
In reply to Suresh SiddhaCurrently send_remote_softirq() API's don't allow single call_single_data struct(like per cpu call_single_data) to be used with multiple send_remote_softirq() calls in parallel (as each of the send_remote_softirq() call reinitializes the call_single_data overwriting the inflight usage.
Add a new init_remote_softirq_csd() which will init the call_single_data. Second send_remote_softirq() from the same cpu will now wait on the csd_lock() if the prior send_remote_softirq() is not complete.
--- include/linux/interrupt.h | 8 ++++++-- kernel/softirq.c | 41 +++++++++++++++++++++++++++-------------- 2 files changed, 33 insertions(+), 16 deletions(-)
kernel/softirq.c +27 -14
@@ -578,24 +578,23 @@ static void remote_softirq_receive(void local_irq_restore(flags); } -static int __try_remote_softirq (struct call_single_data *cp,int cpu,int softirq) +static int __try_remote_softirq (struct call_single_data *cp,int cpu) {if (cpu_online (cpu)) { - cp->func = remote_softirq_receive; - cp->info = cp; - cp->flags =0 ; - cp->priv = softirq; -__smp_call_function_single (cpu, cp,0 );return 0 ; }return 1 ; }#else /* CONFIG_USE_GENERIC_SMP_HELPERS */ -static int __try_remote_softirq (struct call_single_data *cp,int cpu,int softirq) +static int __try_remote_softirq (struct call_single_data *cp,int cpu) {return 1 ; } +static void remote_softirq_receive (void *data) +{ +return ; +}#endif /**
@@ -611,12 +610,12 @@ static int __try_remote_softirq(struct c* Interrupts must be disabled. */ void __send_remote_softirq (struct call_single_data *cp,int cpu,int this_cpu, -int softirq,int fallback) +int fallback) {if (cpu == this_cpu) -__local_trigger (cp, softirq); -else if (__try_remote_softirq (cp, cpu, softirq) && fallback) -__local_trigger (cp, softirq); +__local_trigger (cp, cp->priv); +else if (__try_remote_softirq (cp, cpu) && fallback) +__local_trigger (cp, cp->priv); }EXPORT_SYMBOL (__send_remote_softirq);
@@ -629,19 +628,33 @@ EXPORT_SYMBOL(__send_remote_softirq);* Like __send_remote_softirq except that disabling interrupts and * computing the current cpu is done for the caller. */ -void send_remote_softirq (struct call_single_data *cp,int cpu,int softirq, -int fallback) +void send_remote_softirq (struct call_single_data *cp,int cpu,int fallback) {unsigned long flags;int this_cpu;local_irq_save (flags); this_cpu =smp_processor_id (); -__send_remote_softirq (cp, cpu, this_cpu, softirq, fallback); +__send_remote_softirq (cp, cpu, this_cpu, fallback);local_irq_restore (flags); }EXPORT_SYMBOL (send_remote_softirq); +/*** +* init_remote_softirq_csd - initialize the smp_call_function_single()'s +* call single data that will be later used by send_remote_softirq() +* @cp: private SMP call function data area to be initialized +* @softirq: the softirq to be used for the work +*/ +void init_remote_softirq_csd (struct call_single_data *cp,int softirq) +{ + cp->func = remote_softirq_receive; + cp->info = cp; + cp->flags =0 ; + cp->priv = softirq; +} +EXPORT_SYMBOL (init_remote_softirq_csd); +static int __cpuinit remote_softirq_cpu_notify (struct notifier_block *self,unsigned long action,void *hcpu) {
include/linux/interrupt.h +6 -2
@@ -420,13 +420,17 @@ DECLARE_PER_CPU(struct list_head [NR_SOF* work will be queued to the local cpu. */ extern void send_remote_softirq (struct call_single_data *cp,int cpu, -int softirq,int fallback); +int fallback);/* Like send_remote_softirq(), but the caller must disable local cpu interrupts * and compute the current cpu, passed in as 'this_cpu'. */ extern void __send_remote_softirq (struct call_single_data *cp,int cpu, -int this_cpu,int softirq,int fallback); +int this_cpu,int fallback); + +/* Initialize the call_single_data to be later used with send_remote_softirq(). +*/ +extern void init_remote_softirq_csd (struct call_single_data *cp,int softirq);/* Tasklets --- multithreaded analogue of BHs.
PATCH 3/7 softirq: avoid softirq_work_list for SCHED_SOFTIRQ when sent remotely
In reply to Suresh SiddhaThere is no need to add the SCHED_SOFTIRQ work to the softirq_work_list when sent remotely. This is because any pending work associated with SCHED_SOFTIRQ need not be migrated to a new cpu when the current cpu is going down etc.
Also I am not sure how this softirq_work_list works for other softirqs. I don't see anyone removing the list entries from the softirq_work_list after it is handled on a remote cpu.
For now, just skip it for SCHED_SOFTIRQ.
--- kernel/softirq.c | 5 +++++ 1 file changed, 5 insertions(+)
kernel/softirq.c +5 -0
@@ -557,6 +557,11 @@ static void __local_trigger(struct call_ {struct list_head *head = &__get_cpu_var (softirq_work_list[softirq]); +if (softirq ==SCHED_SOFTIRQ ) { +raise_softirq_irqoff (softirq); +return ; + } +list_add_tail (&cp->list, head);/* Trigger the softirq only if the list was previously empty. */
Peter Zijlstra
maintainerRe: [patch 3/7] softirq: avoid softirq_work_list for SCHED_SOFTIRQ when sent remotely
Quoted 10 lines · Suresh Siddha
plain text document attachment (fix_local_trigger_remote_softirq_for_sched.patch)
There is no need to add theSCHED_SOFTIRQwork to thesoftirq_work_listwhen sent remotely. This is because any pending work associated withSCHED_SOFTIRQneed not be migrated to a new cpu when the current cpu is going down etc.Also I am not sure how this
softirq_work_listworks for other softirqs. I don't see anyone removing the list entries from thesoftirq_work_listafter it is handled on a remote cpu.
Most odd all that, Dave, Jens, what happened to all that remote_softirq stuff?
Re: [patch 3/7] softirq: avoid softirq_work_list for SCHED_SOFTIRQ when sent remotely
From: Peter Zijlstra <[email protected]>
Date: Thu, 20 May 2010 10:12:39 +0200
Quoted 2 lines
Most odd all that, Dave, Jens, what happened to all that
remote_softirqstuff?
Nobody ended up using this remote softirq infrastructure, it can be completely deleted.
Re: [patch 3/7] softirq: avoid softirq_work_list for SCHED_SOFTIRQ when sent remotely
Quoted 8 lines · David Miller
From: Peter Zijlstra <[email protected]>
Date: Thu, 20 May 2010 10:12:39 +0200Quoted 2 lines
Most odd all that, Dave, Jens, what happened to all that
remote_softirqstuff?Nobody ended up using this remote softirq infrastructure, it can be completely deleted.
What parts of it? There has been reworks of parts of the code since I added it, the block layer only uses __smp_call_function_single() to trigger remote softirqs.
Signature · 1 line
Jens Axboe
Peter Zijlstra
maintainerRe: [patch 3/7] softirq: avoid softirq_work_list for SCHED_SOFTIRQ when sent remotely
Quoted 7 lines · Jens Axboe
Quoted 6 lines · David Miller
From: Peter Zijlstra <[email protected]>
Date: Thu, 20 May 2010 10:12:39 +0200Quoted 2 lines
Most odd all that, Dave, Jens, what happened to all that
remote_softirqstuff?
Quoted 6 lines
Quoted 2 lines
Nobody ended up using this remote softirq infrastructure, it can be completely deleted.
What parts of it? There has been reworks of parts of the code since I added it, the block layer only uses
__smp_call_function_single()to trigger remote softirqs.
Right, so __smp_call_function_single() is the normal remote ipi stuff from kernel/smp.c, send_remote_softirq() is the pile of code in kernel/softirq.c that uses that to tickle remote softirqs.
The 'problem' seems to be that the remote softirq code (not the ipi bits) doesn't have any users and is quite complex and apparently incomplete.
Suresh, would it make sense to do as Jens does and simply use __smp_call_function_single() or do you think it still makes sense to have a small wrapper and maybe share that with Jens?
Re: [patch 3/7] softirq: avoid softirq_work_list for SCHED_SOFTIRQ when sent remotely
In reply to Jens AxboeFrom: Jens Axboe <[email protected]>
Date: Thu, 20 May 2010 10:23:09 +0200
Quoted 7 lines · David Miller
Quoted 6 lines
From: Peter Zijlstra <[email protected]>
Date: Thu, 20 May 2010 10:12:39 +0200Quoted 2 lines
Most odd all that, Dave, Jens, what happened to all that
remote_softirqstuff?
Quoted 6 lines
Quoted 2 lines
Nobody ended up using this remote softirq infrastructure, it can be completely deleted.
What parts of it? There has been reworks of parts of the code since I added it, the block layer only uses
__smp_call_function_single()to trigger remote softirqs.
And that's what the networking is using for RPS/RFS too.
PATCH 4/7 sched: Change nohz ilb logic from pull to push model
In reply to Suresh SiddhaFrom: Venkatesh Pallipadi <[email protected]>
Subject: sched: Change nohz ilb logic from pull to push model
In the new push model, all idle CPUs indeed go into nohz mode. There is still the concept of idle load balancer. Busy CPU kicks the nohz balancer when any of the nohz CPUs need idle load balancing. The kickee CPU does the idle load balancing on behalf of all idle CPUs instead of the normal idle balance.
This addresses the below two problems with the current nohz ilb logic:
* the balancer will continue to have periodic ticks and wakeup frequently, even though it may not have any rebalancing to do on behalf of any of the idle CPUs.
* On x86 and CPUs that have APIC timer stoppage on idle CPUs, this periodic wakeup can result in an additional interrupt on a CPU doing the timer broadcast.
--- kernel/sched.c | 13 +- kernel/sched_fair.c | 283 ++++++++++++++++++++++++++++++---------------------- 2 files changed, 177 insertions(+), 119 deletions(-)
kernel/sched_fair.c +167 -116
@@ -3081,10 +3081,26 @@ out_unlock: }#ifdef CONFIG_NO_HZ + +static DEFINE_PER_CPU(struct call_single_data, remote_sched_softirq_cb); + +/* +* idle load balancing details +* - One of the idle CPUs nominates itself as idle load_balancer, while +* entering idle. +* - This idle load balancer CPU will also go into tickless mode when +* it is idle, just like all other idle CPUs +* - When one of the busy CPUs notice that there may be an idle rebalancing +* needed, they will kick the idle load balancer, which then does idle +* load balancing for all the idle CPUs. +*/ static struct {atomic_t load_balancer; -cpumask_var_t cpu_mask; -cpumask_var_t ilb_grp_nohz_mask; +atomic_t first_pick_cpu; +atomic_t second_pick_cpu; +cpumask_var_t idle_cpus_mask; +cpumask_var_t grp_idle_mask; +unsigned long next_balance;/* in jiffy units */ } nohz____cacheline_aligned = { .load_balancer =ATOMIC_INIT (-1 ), };
@@ -3141,17 +3157,17 @@ static inline struct sched_domain *lowes*/ static inline int is_semi_idle_group (struct sched_group *ilb_group) { -cpumask_and (nohz.ilb_grp_nohz_mask, nohz.cpu_mask, +cpumask_and (nohz.grp_idle_mask, nohz.idle_cpus_mask,sched_group_cpus (ilb_group));/* * A sched_group is semi-idle when it has atleast one busy cpu * and atleast one idle cpu. */ -if (cpumask_empty (nohz.ilb_grp_nohz_mask)) +if (cpumask_empty (nohz.grp_idle_mask))return 0 ; -if (cpumask_equal (nohz.ilb_grp_nohz_mask,sched_group_cpus (ilb_group))) +if (cpumask_equal (nohz.grp_idle_mask,sched_group_cpus (ilb_group)))return 0 ;return 1 ;
@@ -3184,7 +3200,7 @@ static int find_new_ilb(int cpu)* Optimize for the case when we have no idle CPUs or only one * idle CPU. Don't walk the sched_domain hierarchy in such cases */ -if (cpumask_weight (nohz.cpu_mask) <2 ) +if (cpumask_weight (nohz.idle_cpus_mask) <2 ) goto out_done;for_each_flag_domain (cpu, sd,SD_POWERSAVINGS_BALANCE ) {
@@ -3192,7 +3208,7 @@ static int find_new_ilb(int cpu) do { if (is_semi_idle_group(ilb_group)) - return cpumask_first(nohz.ilb_grp_nohz_mask); + return cpumask_first(nohz.grp_idle_mask); ilb_group = ilb_group->next;
@@ -3200,42 +3216,61 @@ static int find_new_ilb(int cpu) } out_done: -return cpumask_first (nohz.cpu_mask); +return nr_cpu_ids; }#else /* (CONFIG_SCHED_MC || CONFIG_SCHED_SMT) */ static inline int find_new_ilb (int call_cpu) { -return cpumask_first (nohz.cpu_mask); +return nr_cpu_ids; }#endif /* +* Kick a CPU to do the nohz balancing, if it is time for it. We pick the +* nohz_load_balancer CPU (if there is one) otherwise fallback to any idle +* CPU (if there is one). +*/ +static void nohz_balancer_kick (int cpu) +{ +int ilb_cpu; + + nohz.next_balance++; + + ilb_cpu =get_nohz_load_balancer (); +if (ilb_cpu <0 ) { + ilb_cpu =cpumask_first (nohz.idle_cpus_mask); +if (ilb_cpu >= nr_cpu_ids) +return ; + } + +if (!cpu_rq (ilb_cpu)->nohz_balance_kick) { +struct call_single_data *cp; + +cpu_rq (ilb_cpu)->nohz_balance_kick =1 ; + cp = &per_cpu (remote_sched_softirq_cb, cpu); +send_remote_softirq (cp, ilb_cpu,0 ); + } +return ; +} + +/* * This routine will try to nominate the ilb (idle load balancing) * owner among the cpus whose ticks are stopped. ilb owner will do the idle -* load balancing on behalf of all those cpus. If all the cpus in the system -* go into this tickless mode, then there will be no ilb owner (as there is -* no need for one) and all the cpus will sleep till the next wakeup event -* arrives... -* -* For the ilb owner, tick is not stopped. And this tick will be used -* for idle load balancing. ilb owner will still be part of -* nohz.cpu_mask.. +* load balancing on behalf of all those cpus. * -* While stopping the tick, this cpu will become the ilb owner if there -* is no other owner. And will be the owner till that cpu becomes busy -* or if all cpus in the system stop their ticks at which point -* there is no need for ilb owner. -* -* When the ilb owner becomes busy, it nominates another owner, during the -* next busy scheduler_tick() +* When the ilb owner becomes busy, we will not have new ilb owner until some +* idle CPU wakes up and goes back to idle or some busy CPU tries to kick +* idle load balancing by kicking one of the idle CPUs. +* +* Ticks are stopped for the ilb owner as well, with busy CPU kicking this +* ilb owner CPU in future (when there is a need for idle load balancing on +* behalf of all idle CPUs). */ int select_nohz_load_balancer (int stop_tick) {int cpu =smp_processor_id ();if (stop_tick) { -cpu_rq (cpu)->in_nohz_recently =1 ; -if (!cpu_active (cpu)) {if (atomic_read (&nohz.load_balancer) != cpu)return 0 ;
@@ -3250,25 +3285,20 @@ int select_nohz_load_balancer(int stop_treturn 0 ; } -cpumask_set_cpu (cpu, nohz.cpu_mask); +cpumask_set_cpu (cpu, nohz.idle_cpus_mask); -/* time for ilb owner also to sleep */ -if (cpumask_weight (nohz.cpu_mask) ==num_active_cpus ()) { -if (atomic_read (&nohz.load_balancer) == cpu) -atomic_set (&nohz.load_balancer,-1 ); -return 0 ; - } +if (atomic_read (&nohz.first_pick_cpu) == cpu) +atomic_cmpxchg (&nohz.first_pick_cpu, cpu, nr_cpu_ids); +if (atomic_read (&nohz.second_pick_cpu) == cpu) +atomic_cmpxchg (&nohz.second_pick_cpu, cpu, nr_cpu_ids);if (atomic_read (&nohz.load_balancer) ==-1 ) { -/* make me the ilb owner */ -if (atomic_cmpxchg (&nohz.load_balancer,-1 , cpu) ==-1 ) -return 1 ; - }else if (atomic_read (&nohz.load_balancer) == cpu) {int new_ilb; -if (!(sched_smt_power_savings || - sched_mc_power_savings)) -return 1 ; +/* make me the ilb owner */ +if (atomic_cmpxchg (&nohz.load_balancer,-1 , cpu) !=-1 ) +return 0 ; +/* * Check to see if there is a more power-efficient * ilb.
@@ -3279,13 +3309,13 @@ int select_nohz_load_balancer(int stop_tresched_cpu (new_ilb);return 0 ; } -return 1 ; +return 0 ; } }else { -if (!cpumask_test_cpu (cpu, nohz.cpu_mask)) +if (!cpumask_test_cpu (cpu, nohz.idle_cpus_mask))return 0 ; -cpumask_clear_cpu (cpu, nohz.cpu_mask); +cpumask_clear_cpu (cpu, nohz.idle_cpus_mask);if (atomic_read (&nohz.load_balancer) == cpu)if (atomic_cmpxchg (&nohz.load_balancer, cpu,-1 ) != cpu)
@@ -3373,11 +3403,97 @@ out: rq->next_balance = next_balance; } +#ifdef CONFIG_NO_HZ /* -* run_rebalance_domains is triggered when needed from the scheduler tick. -* In CONFIG_NO_HZ case, the idle load balance owner will do the +* In CONFIG_NO_HZ case, the idle balance kickee will do the * rebalancing for all the cpus for whom scheduler ticks are stopped. */ +static void nohz_idle_balance (int this_cpu,enum cpu_idle_type idle) +{ +struct rq *this_rq =cpu_rq (this_cpu); +struct rq *rq; +int balance_cpu; + +if (idle !=CPU_IDLE || !this_rq->nohz_balance_kick) +return ; + +for_each_cpu (balance_cpu, nohz.idle_cpus_mask) { +if (balance_cpu == this_cpu) +continue ; + +/* +* If this cpu gets work to do, stop the load balancing +* work being done for other cpus. Next load +* balancing owner will pick it up. +*/ +if (need_resched ()) { + this_rq->nohz_balance_kick =0 ; +break ; + } + +rebalance_domains (balance_cpu,CPU_IDLE ); + + rq =cpu_rq (balance_cpu); +if (time_after (this_rq->next_balance, rq->next_balance)) + this_rq->next_balance = rq->next_balance; + } + nohz.next_balance = this_rq->next_balance; + this_rq->nohz_balance_kick =0 ; +} + +/* +* Current heuristic for kicking the idle load balancer +* - first_pick_cpu is the one of the busy CPUs. It will kick +* idle load balancer when it has more than one process active. This +* eliminates the need for idle load balancing altogether when we have +* only one running process in the system (common case). +* - If there are more than one busy CPU, idle load balancer may have +* to run for active_load_balance to happen (i.e., two busy CPUs are +* SMT or core siblings and can run better if they move to different +* physical CPUs). So, second_pick_cpu is the second of the busy CPUs +* which will kick idle load balancer as soon as it has any load. +*/ +static inline int nohz_kick_needed (struct rq *rq,int cpu) +{ +unsigned long now = jiffies; +int ret; +int first_pick_cpu, second_pick_cpu; + +if (time_before (now, nohz.next_balance)) +return 0 ; + +if (!rq->nr_running) +return 0 ; + + first_pick_cpu =atomic_read (&nohz.first_pick_cpu); + second_pick_cpu =atomic_read (&nohz.second_pick_cpu); + +if (first_pick_cpu < nr_cpu_ids && first_pick_cpu != cpu && + second_pick_cpu < nr_cpu_ids && second_pick_cpu != cpu) +return 0 ; + + ret =atomic_cmpxchg (&nohz.first_pick_cpu, nr_cpu_ids, cpu); +if (ret == nr_cpu_ids || ret == cpu) { +atomic_cmpxchg (&nohz.second_pick_cpu, cpu, nr_cpu_ids); +if (rq->nr_running >1 ) +return 1 ; + }else { + ret =atomic_cmpxchg (&nohz.second_pick_cpu, nr_cpu_ids, cpu); +if (ret == nr_cpu_ids || ret == cpu) { +if (rq->nr_running) +return 1 ; + } + } +return 0 ; +} +#else +static void nohz_idle_balance (int this_cpu,enum cpu_idle_type idle) { } +#endif + +/* +* run_rebalance_domains is triggered when needed from the scheduler tick. +* Also triggered for nohz idle balancing (with nohz_balancing_kick set). +*/ static void run_rebalance_domains (struct softirq_action *h) {int this_cpu =smp_processor_id ();
@@ -3387,37 +3503,12 @@ static void run_rebalance_domains(structrebalance_domains (this_cpu, idle); -#ifdef CONFIG_NO_HZ /* -* If this cpu is the owner for idle load balancing, then do the +* If this cpu has a pending nohz_balance_kick, then do the * balancing on behalf of the other idle cpus whose ticks are * stopped. */ -if (this_rq->idle_at_tick && -atomic_read (&nohz.load_balancer) == this_cpu) { -struct rq *rq; -int balance_cpu; - -for_each_cpu (balance_cpu, nohz.cpu_mask) { -if (balance_cpu == this_cpu) -continue ; - -/* -* If this cpu gets work to do, stop the load balancing -* work being done for other cpus. Next load -* balancing owner will pick it up. -*/ -if (need_resched ()) -break ; - -rebalance_domains (balance_cpu,CPU_IDLE ); - - rq =cpu_rq (balance_cpu); -if (time_after (this_rq->next_balance, rq->next_balance)) - this_rq->next_balance = rq->next_balance; - } - } -#endif +nohz_idle_balance (this_cpu, idle); }static inline int on_null_domain (int cpu)
@@ -3427,57 +3518,17 @@ static inline int on_null_domain(int cpu/* * Trigger the SCHED_SOFTIRQ if it is time to do periodic load balancing. -* -* In case of CONFIG_NO_HZ, this is the place where we nominate a new -* idle load balancing owner or decide to stop the periodic load balancing, -* if the whole system is idle. */ static inline void trigger_load_balance (struct rq *rq,int cpu) { -#ifdef CONFIG_NO_HZ -/* -* If we were in the nohz mode recently and busy at the current -* scheduler tick, then check if we need to nominate new idle -* load balancer. -*/ -if (rq->in_nohz_recently && !rq->idle_at_tick) { - rq->in_nohz_recently =0 ; - -if (atomic_read (&nohz.load_balancer) == cpu) { -cpumask_clear_cpu (cpu, nohz.cpu_mask); -atomic_set (&nohz.load_balancer,-1 ); - } - -if (atomic_read (&nohz.load_balancer) ==-1 ) { -int ilb =find_new_ilb (cpu); - -if (ilb < nr_cpu_ids) -resched_cpu (ilb); - } - } - -/* -* If this cpu is idle and doing idle load balancing for all the -* cpus with ticks stopped, is it time for that to stop? -*/ -if (rq->idle_at_tick &&atomic_read (&nohz.load_balancer) == cpu && -cpumask_weight (nohz.cpu_mask) ==num_online_cpus ()) { -resched_cpu (cpu); -return ; - } - -/* -* If this cpu is idle and the idle load balancing is done by -* someone else, then no need raise the SCHED_SOFTIRQ -*/ -if (rq->idle_at_tick &&atomic_read (&nohz.load_balancer) != cpu && -cpumask_test_cpu (cpu, nohz.cpu_mask)) -return ; -#endif /* Don't need to rebalance while attached to NULL domain */ if (time_after_eq (jiffies, rq->next_balance) &&likely (!on_null_domain (cpu)))raise_softirq (SCHED_SOFTIRQ ); +#ifdef CONFIG_NO_HZ + else if (nohz_kick_needed(rq, cpu) && likely(!on_null_domain(cpu))) + nohz_balancer_kick(cpu); +#endif }static void rq_online_fair (struct rq *rq)
kernel/sched.c +10 -3
@@ -504,7 +504,7 @@ struct rq {unsigned long cpu_load[CPU_LOAD_IDX_MAX ];#ifdef CONFIG_NO_HZ u64 nohz_stamp; -unsigned char in_nohz_recently; +unsigned char nohz_balance_kick;#endif unsigned int skip_clock_update;
@@ -7605,6 +7605,11 @@ void __init sched_init(void) rq->idle_stamp =0 ; rq->avg_idle =2 *sysctl_sched_migration_cost;rq_attach_root (rq, &def_root_domain); +#ifdef CONFIG_NO_HZ + rq->nohz_balance_kick =0 ; +init_remote_softirq_csd (&per_cpu (remote_sched_softirq_cb, i), +SCHED_SOFTIRQ ); +#endif #endif init_rq_hrtick (rq);atomic_set (&rq->nr_iowait,0 );
@@ -7649,8 +7654,10 @@ void __init sched_init(void)zalloc_cpumask_var (&nohz_cpu_mask,GFP_NOWAIT );#ifdef CONFIG_SMP #ifdef CONFIG_NO_HZ -zalloc_cpumask_var (&nohz.cpu_mask,GFP_NOWAIT ); -alloc_cpumask_var (&nohz.ilb_grp_nohz_mask,GFP_NOWAIT ); +zalloc_cpumask_var (&nohz.idle_cpus_mask,GFP_NOWAIT ); +alloc_cpumask_var (&nohz.grp_idle_mask,GFP_NOWAIT ); +atomic_set (&nohz.first_pick_cpu, nr_cpu_ids); +atomic_set (&nohz.second_pick_cpu, nr_cpu_ids);#endif /* May be allocated at isolcpus cmdline parse time */ if (cpu_isolated_map ==NULL )
Re: [patch 4/7] sched: Change nohz ilb logic from pull to push model
Quoted 9 lines · Suresh Siddha
From: Venkatesh Pallipadi <[email protected]>
Subject: sched: Change nohz ilb logic from pull to push modelIn the new push model, all idle CPUs indeed go into nohz mode. There is still the concept of idle load balancer. Busy CPU kicks the nohz balancer when any of the nohz CPUs need idle load balancing. The kickee CPU does the idle load balancing on behalf of all idle CPUs instead of the normal idle balance.
Quoted 7 lines
This addresses the below two problems with the current nohz ilb logic:
* the balancer will continue to have periodic ticks and wakeup frequently, even though it may not have any rebalancing to do on behalf of any of the idle CPUs.
* On x86 and CPUs that have APIC timer stoppage on idle CPUs, this periodic wakeup can result in an additional interrupt on a CPU doing the timer broadcast.
How do we select the timer broadcast cpu today? Is it changes at all at run time? Maybe that CPU should be a good target for the timer migration so that additional CPU are not wokenup from idle states.
Quoted 290 lines
Signed-off-by Venkatesh Pallipadi <[email protected]>Signed-off-by Suresh Siddha <[email protected]>--- kernel/sched.c | 13 +- kernel/sched_fair.c | 283 ++++++++++++++++++++++++++++++---------------------- 2 files changed, 177 insertions(+), 119 deletions(-)Index:
tip/kernel/sched_fair.c
===================================================================kernel/sched_fair.c +142
-45@@ -3081,10 +3081,26 @@ out_unlock: }#ifdef CONFIG_NO_HZ + +static DEFINE_PER_CPU(struct call_single_data, remote_sched_softirq_cb); + +/* +* idle load balancing details +* - One of the idle CPUs nominates itself as idle load_balancer, while +* entering idle. +* - This idle load balancer CPU will also go into tickless mode when +* it is idle, just like all other idle CPUs +* - When one of the busy CPUs notice that there may be an idle rebalancing +* needed, they will kick the idle load balancer, which then does idle +* load balancing for all the idle CPUs. +*/ static struct {atomic_t load_balancer; -cpumask_var_t cpu_mask; -cpumask_var_t ilb_grp_nohz_mask; +atomic_t first_pick_cpu; +atomic_t second_pick_cpu; +cpumask_var_t idle_cpus_mask; +cpumask_var_t grp_idle_mask; +unsigned long next_balance;/* in jiffy units */ } nohz____cacheline_aligned = { .load_balancer =ATOMIC_INIT (-1 ), };@@ -3141,17 +3157,17 @@ static inline struct sched_domain *lowes*/ static inline int is_semi_idle_group (struct sched_group *ilb_group) { -cpumask_and (nohz.ilb_grp_nohz_mask, nohz.cpu_mask, +cpumask_and (nohz.grp_idle_mask, nohz.idle_cpus_mask,sched_group_cpus (ilb_group));/* * A sched_group is semi-idle when it has atleast one busy cpu * and atleast one idle cpu. */ -if (cpumask_empty (nohz.ilb_grp_nohz_mask)) +if (cpumask_empty (nohz.grp_idle_mask))return 0 ; -if (cpumask_equal (nohz.ilb_grp_nohz_mask,sched_group_cpus (ilb_group))) +if (cpumask_equal (nohz.grp_idle_mask,sched_group_cpus (ilb_group)))return 0 ;return 1 ;@@ -3184,7 +3200,7 @@ static int find_new_ilb(int cpu)* Optimize for the case when we have no idle CPUs or only one * idle CPU. Don't walk the sched_domain hierarchy in such cases */ -if (cpumask_weight (nohz.cpu_mask) <2 ) +if (cpumask_weight (nohz.idle_cpus_mask) <2 ) goto out_done;for_each_flag_domain (cpu, sd,SD_POWERSAVINGS_BALANCE ) {@@ -3192,7 +3208,7 @@ static int find_new_ilb(int cpu) do { if (is_semi_idle_group(ilb_group)) - return cpumask_first(nohz.ilb_grp_nohz_mask); + return cpumask_first(nohz.grp_idle_mask); ilb_group = ilb_group->next;@@ -3200,42 +3216,61 @@ static int find_new_ilb(int cpu) } out_done: -return cpumask_first (nohz.cpu_mask); +return nr_cpu_ids; }#else /* (CONFIG_SCHED_MC || CONFIG_SCHED_SMT) */ static inline int find_new_ilb (int call_cpu) { -return cpumask_first (nohz.cpu_mask); +return nr_cpu_ids; }#endif /* +* Kick a CPU to do the nohz balancing, if it is time for it. We pick the +* nohz_load_balancer CPU (if there is one) otherwise fallback to any idle +* CPU (if there is one). +*/ +static void nohz_balancer_kick (int cpu) +{ +int ilb_cpu; + + nohz.next_balance++; + + ilb_cpu =get_nohz_load_balancer (); +if (ilb_cpu <0 ) { + ilb_cpu =cpumask_first (nohz.idle_cpus_mask); +if (ilb_cpu >= nr_cpu_ids) +return ; + } + +if (!cpu_rq (ilb_cpu)->nohz_balance_kick) { +struct call_single_data *cp; + +cpu_rq (ilb_cpu)->nohz_balance_kick =1 ; + cp = &per_cpu (remote_sched_softirq_cb, cpu); +send_remote_softirq (cp, ilb_cpu,0 ); + } +return ; +} + +/* * This routine will try to nominate the ilb (idle load balancing) * owner among the cpus whose ticks are stopped. ilb owner will do the idle -* load balancing on behalf of all those cpus. If all the cpus in the system -* go into this tickless mode, then there will be no ilb owner (as there is -* no need for one) and all the cpus will sleep till the next wakeup event -* arrives... -* -* For the ilb owner, tick is not stopped. And this tick will be used -* for idle load balancing. ilb owner will still be part of -* nohz.cpu_mask.. +* load balancing on behalf of all those cpus. * -* While stopping the tick, this cpu will become the ilb owner if there -* is no other owner. And will be the owner till that cpu becomes busy -* or if all cpus in the system stop their ticks at which point -* there is no need for ilb owner. -* -* When the ilb owner becomes busy, it nominates another owner, during the -* next busy scheduler_tick() +* When the ilb owner becomes busy, we will not have new ilb owner until some +* idle CPU wakes up and goes back to idle or some busy CPU tries to kick +* idle load balancing by kicking one of the idle CPUs. +* +* Ticks are stopped for the ilb owner as well, with busy CPU kicking this +* ilb owner CPU in future (when there is a need for idle load balancing on +* behalf of all idle CPUs). */ int select_nohz_load_balancer (int stop_tick) {int cpu =smp_processor_id ();if (stop_tick) { -cpu_rq (cpu)->in_nohz_recently =1 ; -if (!cpu_active (cpu)) {if (atomic_read (&nohz.load_balancer) != cpu)return 0 ;@@ -3250,25 +3285,20 @@ int select_nohz_load_balancer(int stop_treturn 0 ; } -cpumask_set_cpu (cpu, nohz.cpu_mask); +cpumask_set_cpu (cpu, nohz.idle_cpus_mask); -/* time for ilb owner also to sleep */ -if (cpumask_weight (nohz.cpu_mask) ==num_active_cpus ()) { -if (atomic_read (&nohz.load_balancer) == cpu) -atomic_set (&nohz.load_balancer,-1 ); -return 0 ; - } +if (atomic_read (&nohz.first_pick_cpu) == cpu) +atomic_cmpxchg (&nohz.first_pick_cpu, cpu, nr_cpu_ids); +if (atomic_read (&nohz.second_pick_cpu) == cpu) +atomic_cmpxchg (&nohz.second_pick_cpu, cpu, nr_cpu_ids);if (atomic_read (&nohz.load_balancer) ==-1 ) { -/* make me the ilb owner */ -if (atomic_cmpxchg (&nohz.load_balancer,-1 , cpu) ==-1 ) -return 1 ; - }else if (atomic_read (&nohz.load_balancer) == cpu) {int new_ilb; -if (!(sched_smt_power_savings || - sched_mc_power_savings)) -return 1 ; +/* make me the ilb owner */ +if (atomic_cmpxchg (&nohz.load_balancer,-1 , cpu) !=-1 ) +return 0 ; +/* * Check to see if there is a more power-efficient * ilb. @@ -3279,13 +3309,13 @@ int select_nohz_load_balancer(int stop_tresched_cpu (new_ilb);return 0 ; } -return 1 ; +return 0 ; } }else { -if (!cpumask_test_cpu (cpu, nohz.cpu_mask)) +if (!cpumask_test_cpu (cpu, nohz.idle_cpus_mask))return 0 ; -cpumask_clear_cpu (cpu, nohz.cpu_mask); +cpumask_clear_cpu (cpu, nohz.idle_cpus_mask);if (atomic_read (&nohz.load_balancer) == cpu)if (atomic_cmpxchg (&nohz.load_balancer, cpu,-1 ) != cpu)@@ -3373,11 +3403,97 @@ out: rq->next_balance = next_balance; } +#ifdef CONFIG_NO_HZ /* -* run_rebalance_domains is triggered when needed from the scheduler tick. -* In CONFIG_NO_HZ case, the idle load balance owner will do the +* In CONFIG_NO_HZ case, the idle balance kickee will do the * rebalancing for all the cpus for whom scheduler ticks are stopped. */ +static void nohz_idle_balance (int this_cpu,enum cpu_idle_type idle) +{ +struct rq *this_rq =cpu_rq (this_cpu); +struct rq *rq; +int balance_cpu; + +if (idle !=CPU_IDLE || !this_rq->nohz_balance_kick) +return ; + +for_each_cpu (balance_cpu, nohz.idle_cpus_mask) { +if (balance_cpu == this_cpu) +continue ; + +/* +* If this cpu gets work to do, stop the load balancing +* work being done for other cpus. Next load +* balancing owner will pick it up. +*/ +if (need_resched ()) { + this_rq->nohz_balance_kick =0 ; +break ; + } + +rebalance_domains (balance_cpu,CPU_IDLE ); + + rq =cpu_rq (balance_cpu); +if (time_after (this_rq->next_balance, rq->next_balance)) + this_rq->next_balance = rq->next_balance; + } + nohz.next_balance = this_rq->next_balance; + this_rq->nohz_balance_kick =0 ; +} + +/* +* Current heuristic for kicking the idle load balancer +* - first_pick_cpu is the one of the busy CPUs. It will kick +* idle load balancer when it has more than one process active. This +* eliminates the need for idle load balancing altogether when we have +* only one running process in the system (common case). +* - If there are more than one busy CPU, idle load balancer may have +* to run for active_load_balance to happen (i.e., two busy CPUs are +* SMT or core siblings and can run better if they move to different +* physical CPUs). So, second_pick_cpu is the second of the busy CPUs +* which will kick idle load balancer as soon as it has any load. +*/ +static inline int nohz_kick_needed (struct rq *rq,int cpu) +{ +unsigned long now = jiffies; +int ret; +int first_pick_cpu, second_pick_cpu; + +if (time_before (now, nohz.next_balance)) +return 0 ; + +if (!rq->nr_running) +return 0 ; + + first_pick_cpu =atomic_read (&nohz.first_pick_cpu); + second_pick_cpu =atomic_read (&nohz.second_pick_cpu); + +if (first_pick_cpu < nr_cpu_ids && first_pick_cpu != cpu && + second_pick_cpu < nr_cpu_ids && second_pick_cpu != cpu) +return 0 ; + + ret =atomic_cmpxchg (&nohz.first_pick_cpu, nr_cpu_ids, cpu); +if (ret == nr_cpu_ids || ret == cpu) { +atomic_cmpxchg (&nohz.second_pick_cpu, cpu, nr_cpu_ids);
kernel/sched_fair.c out: · line 3487
Quoted 10 lines
kernel/sched_fair.c +10
-0+if (rq->nr_running >1 ) +return 1 ; + }else { + ret =atomic_cmpxchg (&nohz.second_pick_cpu, nr_cpu_ids, cpu); +if (ret == nr_cpu_ids || ret == cpu) { +if (rq->nr_running) +return 1 ; + } + } +return 0 ;
Hi Suresh,
Can you please give more explanation on how the combination of first_pick_cpu and second_pick_cpu works. We need to kick an idle CPU whenever our cpu or group becomes overloaded right. We will have to prefer cores of other packages when more tasks become ready to run. So a notion of group overload is needed to kick new cpus. Also new idle CPUs that are kicked should come form other cores and packages instead or nearest sibling.
As per the current implementation a sibling thread may be kicked but it will not pull the task as the load balancer will be run on behalf of all idle cores in the system and then a appropriate idle core will pull the new task... correct?
--Vaidy
[snip]
Re: [patch 4/7] sched: Change nohz ilb logic from pull to push model
Quoted 19 lines · Vaidyanathan Srinivasan
Quoted 9 lines · Suresh Siddha
From: Venkatesh Pallipadi <[email protected]>
Subject: sched: Change nohz ilb logic from pull to push modelIn the new push model, all idle CPUs indeed go into nohz mode. There is still the concept of idle load balancer. Busy CPU kicks the nohz balancer when any of the nohz CPUs need idle load balancing. The kickee CPU does the idle load balancing on behalf of all idle CPUs instead of the normal idle balance.
Quoted 7 lines
This addresses the below two problems with the current nohz ilb logic:
* the balancer will continue to have periodic ticks and wakeup frequently, even though it may not have any rebalancing to do on behalf of any of the idle CPUs.
* On x86 and CPUs that have APIC timer stoppage on idle CPUs, this periodic wakeup can result in an additional interrupt on a CPU doing the timer broadcast.
Quoted 3 lines
How do we select the timer broadcast cpu today? Is it changes at all at run time? Maybe that CPU should be a good target for the timer migration so that additional CPU are not wokenup from idle states.
It is based on who handles irq 0. Anyways, newer generation of cpu's doesn't have apic timer stoppage issue. If you want to do more intelligent timer migrations, then its better to address with a mechanism that works efficiently for all platforms.
Quoted 3 lines
Can you please give more explanation on how the combination of
first_pick_cpuandsecond_pick_cpuworks. We need to kick an idle CPU whenever our cpu or group becomes overloaded right.
With this change, the need for idle load balancing(/kicking an idle cpu to do idle load balancing on behalf of all idle cpus) is determined when there is only one cpu busy with more than 1 task or more than one cpu busy.
sched group is relevant only if we are balancing at a particular domain. Traversing all the groups and finding out the group load vs capacity from the busy cpu will add more overhead to the busy cpu.
We need more intelligence of when to do idle load balancing and when to stop it. Current proposal is a simple fix to address the idle core in a semi-idle laptop/netbooks to not have periodic ticks in idle.
Quoted 5 lines
We will have to
prefer cores of other packages when more tasks become ready to run. So a notion of group overload is needed to kick new cpus. Also new idle CPUs that are kicked should come form other cores and packages instead or nearest sibling.
Kicked cpu can be nearest idle core to the busy core. This can do idle load balancing and the actual load can move the far away core (for perf policy) or nearest core (for power-savings policy). Any intelligent heuristics to do this with minimal disturbance to busy cpu's are welcome.
Quoted 5 lines
As per the current implementation a sibling thread may be kicked but it will not pull the task as the load balancer will be run on behalf of all idle cores in the system and then a appropriate idle core will pull the new task... correct?
Yes.
thanks,
suresh
PATCH 5/7 sched: Change select_nohz_load_balancer to return void
In reply to Suresh SiddhaFrom: Venkatesh Pallipadi <[email protected]>
Subject: sched: Change select_nohz_load_balancer to return void
select_nohz_load_balancer used to return 1 when ticks are not to be stopped (idle_balancer), 0 otherwise. With change to nohz idle_balancer logic, all idle cpus can go to tickless mode and be woken up by a kick from one of the busy cpus, if and when idle balancing is required. As a result, select_nohz_load_balancer can return void.
--- include/linux/sched.h | 7 ++----- kernel/sched_fair.c | 16 ++++++++-------- kernel/time/tick-sched.c | 8 +------- 3 files changed, 11 insertions(+), 20 deletions(-)
kernel/sched_fair.c +8 -8
@@ -3266,14 +3266,14 @@ static void nohz_balancer_kick(int cpu)* ilb owner CPU in future (when there is a need for idle load balancing on * behalf of all idle CPUs). */ -int select_nohz_load_balancer (int stop_tick) +void select_nohz_load_balancer (int stop_tick) {int cpu =smp_processor_id ();if (stop_tick) {if (!cpu_active (cpu)) {if (atomic_read (&nohz.load_balancer) != cpu) -return 0 ; +return ;/* * If we are going offline and still the leader,
@@ -3282,7 +3282,7 @@ int select_nohz_load_balancer(int stop_tif (atomic_cmpxchg (&nohz.load_balancer, cpu,-1 ) != cpu)BUG (); -return 0 ; +return ; }cpumask_set_cpu (cpu, nohz.idle_cpus_mask);
@@ -3297,7 +3297,7 @@ int select_nohz_load_balancer(int stop_t/* make me the ilb owner */ if (atomic_cmpxchg (&nohz.load_balancer,-1 , cpu) !=-1 ) -return 0 ; +return ;/* * Check to see if there is a more power-efficient
@@ -3307,13 +3307,13 @@ int select_nohz_load_balancer(int stop_tif (new_ilb < nr_cpu_ids && new_ilb != cpu) {atomic_set (&nohz.load_balancer,-1 );resched_cpu (new_ilb); -return 0 ; +return ; } -return 0 ; +return ; } }else {if (!cpumask_test_cpu (cpu, nohz.idle_cpus_mask)) -return 0 ; +return ;cpumask_clear_cpu (cpu, nohz.idle_cpus_mask);
@@ -3321,7 +3321,7 @@ int select_nohz_load_balancer(int stop_tif (atomic_cmpxchg (&nohz.load_balancer, cpu,-1 ) != cpu) BUG(); } -return 0 ; +return ; }#endif
kernel/time/tick-sched.c +1 -7
@@ -408,13 +408,7 @@ void tick_nohz_stop_sched_tick(int inidl* the scheduler tick in nohz_restart_sched_tick. */ if (!ts->tick_stopped) { -if (select_nohz_load_balancer (1 )) { -/* -* sched tick not stopped! -*/ -cpumask_clear_cpu (cpu, nohz_cpu_mask); - goto out; - } +select_nohz_load_balancer (1 ); ts->idle_tick =hrtimer_get_expires (&ts->sched_timer); ts->tick_stopped =1 ;
include/linux/sched.h +2 -5
@@ -272,14 +272,11 @@ extern void task_rq_unlock_wait(struct textern cpumask_var_t nohz_cpu_mask;#if defined(CONFIG_SMP ) && defined(CONFIG_NO_HZ ) -extern int select_nohz_load_balancer (int cpu); +extern void select_nohz_load_balancer (int stop_tick);extern int get_nohz_load_balancer (void );extern int nohz_ratelimit (int cpu);#else -static inline int select_nohz_load_balancer (int cpu) -{ -return 0 ; -} +static inline void select_nohz_load_balancer (int stop_tick) { }static inline int nohz_ratelimit (int cpu) {
PATCH 6/7 sched: change nohz.load_balancer to be nr_cpu_ids based
In reply to Suresh SiddhaFrom: Venkatesh Pallipadi <[email protected]>
Subject: sched: change nohz.load_balancer to be nr_cpu_ids based
nohz.load_balancer was using -1 when it is not set to any cpu. Change it to nr_cpu_ids, making it similar to other such variables in this file.
--- kernel/hrtimer.c | 2 +- kernel/sched.c | 1 + kernel/sched_fair.c | 26 ++++++++++++++++---------- kernel/timer.c | 2 +- 4 files changed, 19 insertions(+), 12 deletions(-)
kernel/sched_fair.c +16 -10
@@ -3101,13 +3101,15 @@ static struct {cpumask_var_t idle_cpus_mask;cpumask_var_t grp_idle_mask;unsigned long next_balance;/* in jiffy units */ -} nohz ____cacheline_aligned = { - .load_balancer = ATOMIC_INIT(-1), -}; +} nohz____cacheline_aligned ;int get_nohz_load_balancer (void ) { -return atomic_read (&nohz.load_balancer); +int load_balancer =atomic_read (&nohz.load_balancer); +if (load_balancer >= nr_cpu_ids) +return nr_cpu_ids; + +return load_balancer; }#if defined(CONFIG_SCHED_MC ) || defined(CONFIG_SCHED_SMT )
@@ -3237,7 +3239,8 @@ static void nohz_balancer_kick(int cpu) nohz.next_balance++; ilb_cpu =get_nohz_load_balancer (); -if (ilb_cpu <0 ) { + +if (ilb_cpu >= nr_cpu_ids) { ilb_cpu =cpumask_first (nohz.idle_cpus_mask);if (ilb_cpu >= nr_cpu_ids)return ;
@@ -3279,7 +3282,8 @@ void select_nohz_load_balancer(int stop_* If we are going offline and still the leader, * give up! */ -if (atomic_cmpxchg (&nohz.load_balancer, cpu,-1 ) != cpu) +if (atomic_cmpxchg (&nohz.load_balancer, cpu, + nr_cpu_ids) != cpu)BUG ();return ;
@@ -3292,11 +3296,12 @@ void select_nohz_load_balancer(int stop_if (atomic_read (&nohz.second_pick_cpu) == cpu)atomic_cmpxchg (&nohz.second_pick_cpu, cpu, nr_cpu_ids); -if (atomic_read (&nohz.load_balancer) ==-1 ) { +if (atomic_read (&nohz.load_balancer) >= nr_cpu_ids) {int new_ilb;/* make me the ilb owner */ -if (atomic_cmpxchg (&nohz.load_balancer,-1 , cpu) !=-1 ) +if (atomic_cmpxchg (&nohz.load_balancer, nr_cpu_ids, + cpu) != nr_cpu_ids)return ;/*
@@ -3305,7 +3310,7 @@ void select_nohz_load_balancer(int stop_*/ new_ilb =find_new_ilb (cpu);if (new_ilb < nr_cpu_ids && new_ilb != cpu) { -atomic_set (&nohz.load_balancer,-1 ); +atomic_set (&nohz.load_balancer, nr_cpu_ids);resched_cpu (new_ilb);return ; }
@@ -3318,7 +3323,8 @@ void select_nohz_load_balancer(int stop_cpumask_clear_cpu (cpu, nohz.idle_cpus_mask);if (atomic_read (&nohz.load_balancer) == cpu) -if (atomic_cmpxchg (&nohz.load_balancer, cpu,-1 ) != cpu) +if (atomic_cmpxchg (&nohz.load_balancer, cpu, + nr_cpu_ids) != cpu)BUG (); }return ;
kernel/sched.c +1 -0
@@ -7656,6 +7656,7 @@ void __init sched_init(void)#ifdef CONFIG_NO_HZ zalloc_cpumask_var (&nohz.idle_cpus_mask,GFP_NOWAIT );alloc_cpumask_var (&nohz.grp_idle_mask,GFP_NOWAIT ); +atomic_set (&nohz.load_balancer, nr_cpu_ids);atomic_set (&nohz.first_pick_cpu, nr_cpu_ids);atomic_set (&nohz.second_pick_cpu, nr_cpu_ids);#endif
kernel/hrtimer.c +1 -1
@@ -147,7 +147,7 @@ static int hrtimer_get_target(int this_cif (!pinned &&get_sysctl_timer_migration () &&idle_cpu (this_cpu)) {int preferred_cpu =get_nohz_load_balancer (); -if (preferred_cpu >=0 ) +if (preferred_cpu < nr_cpu_ids)return preferred_cpu; }#endif
kernel/timer.c +1 -1
@@ -682,7 +682,7 @@ __mod_timer(struct timer_list *timer, unif (!pinned &&get_sysctl_timer_migration () &&idle_cpu (cpu)) {int preferred_cpu =get_nohz_load_balancer (); -if (preferred_cpu >=0 ) +if (preferred_cpu < nr_cpu_ids) cpu = preferred_cpu; }#endif
Peter Zijlstra
maintainerRe: [patch 6/7] sched: change nohz.load_balancer to be nr_cpu_ids based
kernel/sched_fair.c static struct { · line 3113
Quoted 9 lines · Suresh Siddha
int
get_nohz_load_balancer(void)
{kernel/sched_fair.c +5
-1-return atomic_read (&nohz.load_balancer); +int load_balancer =atomic_read (&nohz.load_balancer); +if (load_balancer >= nr_cpu_ids) +return nr_cpu_ids; + +return load_balancer; }
How could it ever be > nr_cpu_ids, and thus, do we need that conditional?
PATCH 7/7 timers: use nearest busy cpu for migrating timers from an idle cpu
In reply to Suresh SiddhaCurrently we are migrating the unpinned timers from an idle to the cpu doing idle load balancing (when all the cpus in the system are idle, there is no idle load balacncing cpu and timers get added to the same idle cpu where the request was made. So the current optimization works only on semi idle system).
And In semi idle system, we no longer have periodic ticks on the idle cpu doing the idle load balancing on behalf of all the cpu's. Using that cpu will add more delays to the timers than intended (as that cpu's timer base may not be uptodate wrt jiffies etc). This was causing mysterious slowdowns during boot etc.
For now, in the semi idle case, use the nearest busy cpu for migrating timers from an idle cpu. This is good for power-savings anyway.
--- include/linux/sched.h | 2 +- kernel/hrtimer.c | 8 ++------ kernel/sched.c | 13 +++++++++++++ kernel/timer.c | 8 ++------ 4 files changed, 18 insertions(+), 13 deletions(-)
kernel/hrtimer.c +2 -6
@@ -144,12 +144,8 @@ struct hrtimer_clock_base *lock_hrtimer_static int hrtimer_get_target (int this_cpu,int pinned) {#ifdef CONFIG_NO_HZ -if (!pinned &&get_sysctl_timer_migration () &&idle_cpu (this_cpu)) { -int preferred_cpu =get_nohz_load_balancer (); - -if (preferred_cpu < nr_cpu_ids) -return preferred_cpu; - } +if (!pinned &&get_sysctl_timer_migration () &&idle_cpu (this_cpu)) +return get_nohz_timer_target ();#endif return this_cpu; }
kernel/sched.c +13 -0
@@ -1201,6 +1201,19 @@ static void resched_cpu(int cpu) }#ifdef CONFIG_NO_HZ +int get_nohz_timer_target (void ) +{ +int cpu =smp_processor_id (); +int i; +struct sched_domain *sd; + +for_each_domain (cpu, sd) { +for_each_cpu (i,sched_domain_span (sd)) +if (!idle_cpu (i)) +return i; + } +return cpu; +}/* * When add_timer_on() enqueues a timer into the timer wheel of an * idle CPU then this timer might expire before the next timer event
kernel/timer.c +2 -6
@@ -679,12 +679,8 @@ __mod_timer(struct timer_list *timer, un cpu =smp_processor_id ();#if defined(CONFIG_NO_HZ ) && defined(CONFIG_SMP ) -if (!pinned &&get_sysctl_timer_migration () &&idle_cpu (cpu)) { -int preferred_cpu =get_nohz_load_balancer (); - -if (preferred_cpu < nr_cpu_ids) - cpu = preferred_cpu; - } +if (!pinned &&get_sysctl_timer_migration () &&idle_cpu (cpu)) + cpu =get_nohz_timer_target ();#endif new_base =per_cpu (tvec_bases, cpu);
include/linux/sched.h +1 -1
@@ -273,7 +273,7 @@ extern void task_rq_unlock_wait(struct textern cpumask_var_t nohz_cpu_mask;#if defined(CONFIG_SMP ) && defined(CONFIG_NO_HZ )extern void select_nohz_load_balancer (int stop_tick); -extern int get_nohz_load_balancer (void ); +extern int get_nohz_timer_target (void );extern int nohz_ratelimit (int cpu);#else static inline void select_nohz_load_balancer (int stop_tick) { }
Re: [patch 7/7] timers: use nearest busy cpu for migrating timers from an idle cpu
Quoted 11 lines · Suresh Siddha
Currently we are migrating the unpinned timers from an idle to the cpu doing idle load balancing (when all the cpus in the system are idle, there is no idle load balacncing cpu and timers get added to the same idle cpu where the request was made. So the current optimization works only on semi idle system).
And In semi idle system, we no longer have periodic ticks on the idle cpu doing the idle load balancing on behalf of all the cpu's. Using that cpu will add more delays to the timers than intended (as that cpu's timer base may not be uptodate wrt jiffies etc). This was causing mysterious slowdowns during boot etc.
Hi Suresh,
Can please give more info on why this caused delay in bootup or timer event. The jiffies should be updated even with the current push model right. We will still have some pinned timer on the idle cpu and the time base will have to be updated when the timer event happens.
Quoted 3 lines
For now, in the semi idle case, use the nearest busy cpu for migrating timers from an idle cpu. This is good for power-savings anyway.
Yes. This is good solution. But on a large system the only running cpu may accumulate too may timers that could affect the performance of the task running. We will need to test this out.
Quoted 38 lines
Signed-off-by Suresh Siddha <[email protected]>--- include/linux/sched.h | 2 +- kernel/hrtimer.c | 8 ++------ kernel/sched.c | 13 +++++++++++++ kernel/timer.c | 8 ++------ 4 files changed, 18 insertions(+), 13 deletions(-)Index:
tip/kernel/hrtimer.c
===================================================================kernel/hrtimer.c +2
-6@@ -144,12 +144,8 @@ struct hrtimer_clock_base *lock_hrtimer_static int hrtimer_get_target (int this_cpu,int pinned) {#ifdef CONFIG_NO_HZ -if (!pinned &&get_sysctl_timer_migration () &&idle_cpu (this_cpu)) { -int preferred_cpu =get_nohz_load_balancer (); - -if (preferred_cpu < nr_cpu_ids) -return preferred_cpu; - } +if (!pinned &&get_sysctl_timer_migration () &&idle_cpu (this_cpu)) +return get_nohz_timer_target ();#endif return this_cpu; }Index:
tip/kernel/sched.c
===================================================================kernel/sched.c +3
-0@@ -1201,6 +1201,19 @@ static void resched_cpu(int cpu) }#ifdef CONFIG_NO_HZ +int get_nohz_timer_target (void ) +{ +int cpu =smp_processor_id ();
kernel/sched.c static void resched_cpu(int cpu) · line 1216
Quoted 10 lines
kernel/sched.c +10
-0+int i; +struct sched_domain *sd; + +for_each_domain (cpu, sd) { +for_each_cpu (i,sched_domain_span (sd)) +if (!idle_cpu (i)) +return i; + } +return cpu; +}
We will need a better way of finding the right CPU since this code will take longer time on a larger system with one or two busy cpus.
We should perhaps pick the cpu from the compliment of the current nohz.grp_idle_mask or something derived from these masks instead of searching in the sched domain. Only advantage I see is that we will get the busy CPU nearest as in same node which is better.
--Vaidy
[snip]
Re: [patch 7/7] timers: use nearest busy cpu for migrating timers from an idle cpu
Quoted 14 lines · Vaidyanathan Srinivasan
Quoted 11 lines · Suresh Siddha
Currently we are migrating the unpinned timers from an idle to the cpu doing idle load balancing (when all the cpus in the system are idle, there is no idle load balacncing cpu and timers get added to the same idle cpu where the request was made. So the current optimization works only on semi idle system).
And In semi idle system, we no longer have periodic ticks on the idle cpu doing the idle load balancing on behalf of all the cpu's. Using that cpu will add more delays to the timers than intended (as that cpu's timer base may not be uptodate wrt jiffies etc). This was causing mysterious slowdowns during boot etc.
Quoted 6 lines
Hi Suresh,
Can please give more info on why this caused delay in bootup or timer event. The jiffies should be updated even with the current push model right. We will still have some pinned timer on the idle cpu and the time base will have to be updated when the timer event happens.
with these changes, idle load balancer doesn't have periodic ticks in idle. So for that cpu, timer_jiffies in timer base won't be uptodate when another idle cpu adds timer to this cpu. So, we will introduce more delays for the timers than expected.
Quoted 6 lines
Quoted 2 lines
For now, in the semi idle case, use the nearest busy cpu for migrating timers from an idle cpu. This is good for power-savings anyway.
Yes. This is good solution. But on a large system the only running cpu may accumulate too may timers that could affect the performance of the task running. We will need to test this out.
Yes. It will be good to have an impact of this on big systems. If we see any performance issues, we can migrate the timers only when power-savings tunable is selected.
Quoted 19 lines
Quoted 5 lines
#ifdef
CONFIG_NO_HZkernel/sched.c +3
-0+int get_nohz_timer_target (void ) +{ +int cpu =smp_processor_id ();kernel/sched.c static void resched_cpu(int cpu) · line 1216
Quoted 10 lines
kernel/sched.c +10
-0+int i; +struct sched_domain *sd; + +for_each_domain (cpu, sd) { +for_each_cpu (i,sched_domain_span (sd)) +if (!idle_cpu (i)) +return i; + } +return cpu; +}We will need a better way of finding the right CPU since this code will take longer time on a larger system with one or two busy cpus.
Quoted 4 lines
We should perhaps pick the cpu from the compliment of the current nohz.grp_idle_mask or something derived from these masks instead of searching in the sched domain. Only advantage I see is that we will get the busy CPU nearest as in same node which is better.
Yes I wanted to migrate the timers to the nearest busy cpu aswell as distribute the load among all the busy cpus (if there are multiple cpu's busy).
thanks,
suresh
Hi Suresh.
Quoted 29 lines · Suresh Siddha
This is an updated version of patchset which is posted earlier at
http://lkml.org/lkml/2009/12/10/470Description:
Existing nohz idle load balance logic uses the pull model, with one idle load balancer CPU nominated on any partially idle system and that balancer CPU not going into nohz mode. With the periodic tick, the balancer does the idle balancing on behalf of all the CPUs in nohz mode.This is not very optimal and has few issues:
* the balancer will continue to have periodic ticks and wakeup frequently (HZ rate), even though it may not have any rebalancing to do on behalf of any of the idle CPUs.
* On x86 and CPUs that have APIC timer stoppage on idle CPUs, this periodic wakeup can result in an additional interrupt on a CPU doing the timer broadcast.The alternative is to have a push model, where all idle CPUs can enter nohz mode and any busy CPU kicks one of the idle CPUs to take care of idle balancing on behalf of a group of idle CPUs.
Following patches switches idle load balancer to this push approach.
Updates from the previous version:
* Busy CPU uses
send_remote_softirq()for invokingSCHED_SOFTIRQon the idle load balancing cpu, which does the load balancing on behalf of all the idle CPUs.
Quoted 5 lines
* Dropped the per NUMA node nohz load balancing as it doesn't detect certain imbalance scenarios. This will be addressed later.
Signed-off-by Suresh Siddha<[email protected]>Signed-off-by Venkatesh Pallipadi<[email protected]>
Sounds great.
I'm in the middle of packing at the moment, but will try to find time to test the patches.
It might help to show the difference that the patch series makes (powertop output?)
Regards,
Nigel
Hey,
Quoted 29 lines · Suresh Siddha
This is an updated version of patchset which is posted earlier at
http://lkml.org/lkml/2009/12/10/470Description:
Existing nohz idle load balance logic uses the pull model, with one idle load balancer CPU nominated on any partially idle system and that balancer CPU not going into nohz mode. With the periodic tick, the balancer does the idle balancing on behalf of all the CPUs in nohz mode.This is not very optimal and has few issues:
* the balancer will continue to have periodic ticks and wakeup frequently (HZ rate), even though it may not have any rebalancing to do on behalf of any of the idle CPUs.
* On x86 and CPUs that have APIC timer stoppage on idle CPUs, this periodic wakeup can result in an additional interrupt on a CPU doing the timer broadcast.The alternative is to have a push model, where all idle CPUs can enter nohz mode and any busy CPU kicks one of the idle CPUs to take care of idle balancing on behalf of a group of idle CPUs.
Following patches switches idle load balancer to this push approach.
Updates from the previous version:
* Busy CPU uses
send_remote_softirq()for invokingSCHED_SOFTIRQon the idle load balancing cpu, which does the load balancing on behalf of all the idle CPUs.
Quoted 5 lines
* Dropped the per NUMA node nohz load balancing as it doesn't detect certain imbalance scenarios. This will be addressed later.
Signed-off-by Suresh Siddha <[email protected]>Signed-off-by Venkatesh Pallipadi <[email protected]>
This patchset works good on my notebook; the number of wakeups decreases from ~2.5 to ~1.6 when booting with init=/bin/bash, disabling cursor blinking and enabling USB autosuspend.
Thanks and best,
Dominik
Peter Zijlstra
maintainerQuoted 23 lines · Suresh Siddha
This is an updated version of patchset which is posted earlier at
http://lkml.org/lkml/2009/12/10/470Description:
Existing nohz idle load balance logic uses the pull model, with one idle load balancer CPU nominated on any partially idle system and that balancer CPU not going into nohz mode. With the periodic tick, the balancer does the idle balancing on behalf of all the CPUs in nohz mode.This is not very optimal and has few issues:
* the balancer will continue to have periodic ticks and wakeup frequently (HZ rate), even though it may not have any rebalancing to do on behalf of any of the idle CPUs.
* On x86 and CPUs that have APIC timer stoppage on idle CPUs, this periodic wakeup can result in an additional interrupt on a CPU doing the timer broadcast.The alternative is to have a push model, where all idle CPUs can enter nohz mode and any busy CPU kicks one of the idle CPUs to take care of idle balancing on behalf of a group of idle CPUs.
Following patches switches idle load balancer to this push approach.
Quoted 8 lines
Updates from the previous version:
* Busy CPU uses
send_remote_softirq()for invokingSCHED_SOFTIRQon the idle load balancing cpu, which does the load balancing on behalf of all the idle CPUs.* Dropped the per NUMA node nohz load balancing as it doesn't detect certain imbalance scenarios. This will be addressed later.
Looks good.
I think we want to keep init_remote_softirq_csd() and a function that directly triggers the relevant softirq and make the networking code and the block layer use that if possible -- and axe the rest of the send_remote_softirq() infrastructure.
Also, I think it makes sense to fold patches 4-6.
Quoted 6 lines · Peter Zijlstra
Looks good.
I think we want to keep
init_remote_softirq_csd()and a function that directly triggers the relevant softirq and make the networking code and the block layer use that if possible -- and axe the rest of thesend_remote_softirq()infrastructure.
For now, I ended up using __smp_call_function_single() and does away with all the remote softirq changes. If needed, we can remove the remote softirq infrastructure but it looks like the block remote softirq code looks similar to remote softirq code (like cpu notifiers for hotplug, and softirq triggering by adding the request to local queues etc). Both these things are not required for SCHED_SOFTIRQ and so I just ended up using simple __smp_call_function_single(). May be in future we can modify block and networking code to use remote softirq infrastructure.
Quoted 1 line
Also, I think it makes sense to fold patches 4-6.
Ok. I consolidated everything into this single patch(appended).
thanks,
suresh
---
From: Venkatesh Pallipadi <[email protected]>
Subject: sched: Change nohz ilb logic from pull to push model
In the new push model, all idle CPUs indeed go into nohz mode. There is still the concept of idle load balancer (performing the load balancing on behalf of all the idle cpu's in the system). Busy CPU kicks the nohz balancer when any of the nohz CPUs need idle load balancing. The kickee CPU does the idle load balancing on behalf of all idle CPUs instead of the normal idle balance.
This addresses the below two problems with the current nohz ilb logic:
* the idle load balancer continued to have periodic ticks during idle and wokeup frequently, even though it did not have any rebalancing to do on behalf of any of the idle CPUs.
* On x86 and CPUs that have APIC timer stoppage on idle CPUs, this periodic wakeup can result in a periodic additional interrupt on a CPU doing the timer broadcast.
Also currently we are migrating the unpinned timers from an idle to the cpu doing idle load balancing (when all the cpus in the system are idle, there is no idle load balancing cpu and timers get added to the same idle cpu where the request was made. So the existing optimization works only on semi idle system).
And In semi idle system, we no longer have periodic ticks on the idle load balancer CPU. Using that cpu will add more delays to the timers than intended (as that cpu's timer base may not be uptodate wrt jiffies etc). This was causing mysterious slowdowns during boot etc.
For now, in the semi idle case, use the nearest busy cpu for migrating timers from an idle cpu. This is good for power-savings anyway.
--- include/linux/sched.h | 9 - kernel/hrtimer.c | 8 - kernel/sched.c | 34 ++++ kernel/sched_fair.c | 322 ++++++++++++++++++++++++++++------------------- kernel/time/tick-sched.c | 8 - kernel/timer.c | 8 - 6 files changed, 233 insertions(+), 156 deletions(-)
kernel/sched_fair.c +194 -128
@@ -3081,13 +3081,40 @@ out_unlock: }#ifdef CONFIG_NO_HZ + +static DEFINE_PER_CPU(struct call_single_data, remote_sched_softirq_cb); + +static void trigger_sched_softirq (void *data) +{ +raise_softirq_irqoff (SCHED_SOFTIRQ ); +} + +static inline void init_sched_softirq_csd (struct call_single_data *csd) +{ + csd->func = trigger_sched_softirq; + csd->info =NULL ; + csd->flags =0 ; + csd->priv =0 ; +} + +/* +* idle load balancing details +* - One of the idle CPUs nominates itself as idle load_balancer, while +* entering idle. +* - This idle load balancer CPU will also go into tickless mode when +* it is idle, just like all other idle CPUs +* - When one of the busy CPUs notice that there may be an idle rebalancing +* needed, they will kick the idle load balancer, which then does idle +* load balancing for all the idle CPUs. +*/ static struct {atomic_t load_balancer; -cpumask_var_t cpu_mask; -cpumask_var_t ilb_grp_nohz_mask; -} nohz____cacheline_aligned = { - .load_balancer =ATOMIC_INIT (-1 ), -}; +atomic_t first_pick_cpu; +atomic_t second_pick_cpu; +cpumask_var_t idle_cpus_mask; +cpumask_var_t grp_idle_mask; +unsigned long next_balance;/* in jiffy units */ +} nohz____cacheline_aligned ;int get_nohz_load_balancer (void ) {
@@ -3141,17 +3168,17 @@ static inline struct sched_domain *lowes*/ static inline int is_semi_idle_group (struct sched_group *ilb_group) { -cpumask_and (nohz.ilb_grp_nohz_mask, nohz.cpu_mask, +cpumask_and (nohz.grp_idle_mask, nohz.idle_cpus_mask,sched_group_cpus (ilb_group));/* * A sched_group is semi-idle when it has atleast one busy cpu * and atleast one idle cpu. */ -if (cpumask_empty (nohz.ilb_grp_nohz_mask)) +if (cpumask_empty (nohz.grp_idle_mask))return 0 ; -if (cpumask_equal (nohz.ilb_grp_nohz_mask,sched_group_cpus (ilb_group))) +if (cpumask_equal (nohz.grp_idle_mask,sched_group_cpus (ilb_group)))return 0 ;return 1 ;
@@ -3184,7 +3211,7 @@ static int find_new_ilb(int cpu)* Optimize for the case when we have no idle CPUs or only one * idle CPU. Don't walk the sched_domain hierarchy in such cases */ -if (cpumask_weight (nohz.cpu_mask) <2 ) +if (cpumask_weight (nohz.idle_cpus_mask) <2 ) goto out_done;for_each_flag_domain (cpu, sd,SD_POWERSAVINGS_BALANCE ) {
@@ -3192,7 +3219,7 @@ static int find_new_ilb(int cpu) do { if (is_semi_idle_group(ilb_group)) - return cpumask_first(nohz.ilb_grp_nohz_mask); + return cpumask_first(nohz.grp_idle_mask); ilb_group = ilb_group->next;
@@ -3200,98 +3227,116 @@ static int find_new_ilb(int cpu) } out_done: -return cpumask_first (nohz.cpu_mask); +return nr_cpu_ids; }#else /* (CONFIG_SCHED_MC || CONFIG_SCHED_SMT) */ static inline int find_new_ilb (int call_cpu) { -return cpumask_first (nohz.cpu_mask); +return nr_cpu_ids; }#endif /* +* Kick a CPU to do the nohz balancing, if it is time for it. We pick the +* nohz_load_balancer CPU (if there is one) otherwise fallback to any idle +* CPU (if there is one). +*/ +static void nohz_balancer_kick (int cpu) +{ +int ilb_cpu; + + nohz.next_balance++; + + ilb_cpu =get_nohz_load_balancer (); + +if (ilb_cpu >= nr_cpu_ids) { + ilb_cpu =cpumask_first (nohz.idle_cpus_mask); +if (ilb_cpu >= nr_cpu_ids) +return ; + } + +if (!cpu_rq (ilb_cpu)->nohz_balance_kick) { +struct call_single_data *cp; + +cpu_rq (ilb_cpu)->nohz_balance_kick =1 ; + cp = &per_cpu (remote_sched_softirq_cb, cpu); +__smp_call_function_single (ilb_cpu, cp,0 ); + } +return ; +} + +/* * This routine will try to nominate the ilb (idle load balancing) * owner among the cpus whose ticks are stopped. ilb owner will do the idle -* load balancing on behalf of all those cpus. If all the cpus in the system -* go into this tickless mode, then there will be no ilb owner (as there is -* no need for one) and all the cpus will sleep till the next wakeup event -* arrives... +* load balancing on behalf of all those cpus. * -* For the ilb owner, tick is not stopped. And this tick will be used -* for idle load balancing. ilb owner will still be part of -* nohz.cpu_mask.. +* When the ilb owner becomes busy, we will not have new ilb owner until some +* idle CPU wakes up and goes back to idle or some busy CPU tries to kick +* idle load balancing by kicking one of the idle CPUs. * -* While stopping the tick, this cpu will become the ilb owner if there -* is no other owner. And will be the owner till that cpu becomes busy -* or if all cpus in the system stop their ticks at which point -* there is no need for ilb owner. -* -* When the ilb owner becomes busy, it nominates another owner, during the -* next busy scheduler_tick() +* Ticks are stopped for the ilb owner as well, with busy CPU kicking this +* ilb owner CPU in future (when there is a need for idle load balancing on +* behalf of all idle CPUs). */ -int select_nohz_load_balancer (int stop_tick) +void select_nohz_load_balancer (int stop_tick) {int cpu =smp_processor_id ();if (stop_tick) { -cpu_rq (cpu)->in_nohz_recently =1 ; -if (!cpu_active (cpu)) {if (atomic_read (&nohz.load_balancer) != cpu) -return 0 ; +return ;/* * If we are going offline and still the leader, * give up! */ -if (atomic_cmpxchg (&nohz.load_balancer, cpu,-1 ) != cpu) +if (atomic_cmpxchg (&nohz.load_balancer, cpu, + nr_cpu_ids) != cpu)BUG (); -return 0 ; +return ; } -cpumask_set_cpu (cpu, nohz.cpu_mask); +cpumask_set_cpu (cpu, nohz.idle_cpus_mask); -/* time for ilb owner also to sleep */ -if (cpumask_weight (nohz.cpu_mask) ==num_active_cpus ()) { -if (atomic_read (&nohz.load_balancer) == cpu) -atomic_set (&nohz.load_balancer,-1 ); -return 0 ; - } +if (atomic_read (&nohz.first_pick_cpu) == cpu) +atomic_cmpxchg (&nohz.first_pick_cpu, cpu, nr_cpu_ids); +if (atomic_read (&nohz.second_pick_cpu) == cpu) +atomic_cmpxchg (&nohz.second_pick_cpu, cpu, nr_cpu_ids); -if (atomic_read (&nohz.load_balancer) ==-1 ) { -/* make me the ilb owner */ -if (atomic_cmpxchg (&nohz.load_balancer,-1 , cpu) ==-1 ) -return 1 ; - }else if (atomic_read (&nohz.load_balancer) == cpu) { +if (atomic_read (&nohz.load_balancer) >= nr_cpu_ids) {int new_ilb; -if (!(sched_smt_power_savings || - sched_mc_power_savings)) -return 1 ; +/* make me the ilb owner */ +if (atomic_cmpxchg (&nohz.load_balancer, nr_cpu_ids, + cpu) != nr_cpu_ids) +return ; +/* * Check to see if there is a more power-efficient * ilb. */ new_ilb =find_new_ilb (cpu);if (new_ilb < nr_cpu_ids && new_ilb != cpu) { -atomic_set (&nohz.load_balancer,-1 ); +atomic_set (&nohz.load_balancer, nr_cpu_ids);resched_cpu (new_ilb); -return 0 ; +return ; } -return 1 ; +return ; } }else { -if (!cpumask_test_cpu (cpu, nohz.cpu_mask)) -return 0 ; +if (!cpumask_test_cpu (cpu, nohz.idle_cpus_mask)) +return ; -cpumask_clear_cpu (cpu, nohz.cpu_mask); +cpumask_clear_cpu (cpu, nohz.idle_cpus_mask);if (atomic_read (&nohz.load_balancer) == cpu) -if (atomic_cmpxchg (&nohz.load_balancer, cpu,-1 ) != cpu) +if (atomic_cmpxchg (&nohz.load_balancer, cpu, + nr_cpu_ids) != cpu)BUG (); } -return 0 ; +return ; }#endif
@@ -3373,11 +3418,97 @@ out: rq->next_balance = next_balance; } +#ifdef CONFIG_NO_HZ /* -* run_rebalance_domains is triggered when needed from the scheduler tick. -* In CONFIG_NO_HZ case, the idle load balance owner will do the +* In CONFIG_NO_HZ case, the idle balance kickee will do the * rebalancing for all the cpus for whom scheduler ticks are stopped. */ +static void nohz_idle_balance (int this_cpu,enum cpu_idle_type idle) +{ +struct rq *this_rq =cpu_rq (this_cpu); +struct rq *rq; +int balance_cpu; + +if (idle !=CPU_IDLE || !this_rq->nohz_balance_kick) +return ; + +for_each_cpu (balance_cpu, nohz.idle_cpus_mask) { +if (balance_cpu == this_cpu) +continue ; + +/* +* If this cpu gets work to do, stop the load balancing +* work being done for other cpus. Next load +* balancing owner will pick it up. +*/ +if (need_resched ()) { + this_rq->nohz_balance_kick =0 ; +break ; + } + +rebalance_domains (balance_cpu,CPU_IDLE ); + + rq =cpu_rq (balance_cpu); +if (time_after (this_rq->next_balance, rq->next_balance)) + this_rq->next_balance = rq->next_balance; + } + nohz.next_balance = this_rq->next_balance; + this_rq->nohz_balance_kick =0 ; +} + +/* +* Current heuristic for kicking the idle load balancer +* - first_pick_cpu is the one of the busy CPUs. It will kick +* idle load balancer when it has more than one process active. This +* eliminates the need for idle load balancing altogether when we have +* only one running process in the system (common case). +* - If there are more than one busy CPU, idle load balancer may have +* to run for active_load_balance to happen (i.e., two busy CPUs are +* SMT or core siblings and can run better if they move to different +* physical CPUs). So, second_pick_cpu is the second of the busy CPUs +* which will kick idle load balancer as soon as it has any load. +*/ +static inline int nohz_kick_needed (struct rq *rq,int cpu) +{ +unsigned long now = jiffies; +int ret; +int first_pick_cpu, second_pick_cpu; + +if (time_before (now, nohz.next_balance)) +return 0 ; + +if (!rq->nr_running) +return 0 ; + + first_pick_cpu =atomic_read (&nohz.first_pick_cpu); + second_pick_cpu =atomic_read (&nohz.second_pick_cpu); + +if (first_pick_cpu < nr_cpu_ids && first_pick_cpu != cpu && + second_pick_cpu < nr_cpu_ids && second_pick_cpu != cpu) +return 0 ; + + ret =atomic_cmpxchg (&nohz.first_pick_cpu, nr_cpu_ids, cpu); +if (ret == nr_cpu_ids || ret == cpu) { +atomic_cmpxchg (&nohz.second_pick_cpu, cpu, nr_cpu_ids); +if (rq->nr_running >1 ) +return 1 ; + }else { + ret =atomic_cmpxchg (&nohz.second_pick_cpu, nr_cpu_ids, cpu); +if (ret == nr_cpu_ids || ret == cpu) { +if (rq->nr_running) +return 1 ; + } + } +return 0 ; +} +#else +static void nohz_idle_balance (int this_cpu,enum cpu_idle_type idle) { } +#endif + +/* +* run_rebalance_domains is triggered when needed from the scheduler tick. +* Also triggered for nohz idle balancing (with nohz_balancing_kick set). +*/ static void run_rebalance_domains (struct softirq_action *h) {int this_cpu =smp_processor_id ();
@@ -3387,37 +3518,12 @@ static void run_rebalance_domains(structrebalance_domains (this_cpu, idle); -#ifdef CONFIG_NO_HZ /* -* If this cpu is the owner for idle load balancing, then do the +* If this cpu has a pending nohz_balance_kick, then do the * balancing on behalf of the other idle cpus whose ticks are * stopped. */ -if (this_rq->idle_at_tick && -atomic_read (&nohz.load_balancer) == this_cpu) { -struct rq *rq; -int balance_cpu; - -for_each_cpu (balance_cpu, nohz.cpu_mask) { -if (balance_cpu == this_cpu) -continue ; - -/* -* If this cpu gets work to do, stop the load balancing -* work being done for other cpus. Next load -* balancing owner will pick it up. -*/ -if (need_resched ()) -break ; - -rebalance_domains (balance_cpu,CPU_IDLE ); - - rq =cpu_rq (balance_cpu); -if (time_after (this_rq->next_balance, rq->next_balance)) - this_rq->next_balance = rq->next_balance; - } - } -#endif +nohz_idle_balance (this_cpu, idle); }static inline int on_null_domain (int cpu)
@@ -3427,57 +3533,17 @@ static inline int on_null_domain(int cpu/* * Trigger the SCHED_SOFTIRQ if it is time to do periodic load balancing. -* -* In case of CONFIG_NO_HZ, this is the place where we nominate a new -* idle load balancing owner or decide to stop the periodic load balancing, -* if the whole system is idle. */ static inline void trigger_load_balance (struct rq *rq,int cpu) { -#ifdef CONFIG_NO_HZ -/* -* If we were in the nohz mode recently and busy at the current -* scheduler tick, then check if we need to nominate new idle -* load balancer. -*/ -if (rq->in_nohz_recently && !rq->idle_at_tick) { - rq->in_nohz_recently =0 ; - -if (atomic_read (&nohz.load_balancer) == cpu) { -cpumask_clear_cpu (cpu, nohz.cpu_mask); -atomic_set (&nohz.load_balancer,-1 ); - } - -if (atomic_read (&nohz.load_balancer) ==-1 ) { -int ilb =find_new_ilb (cpu); - -if (ilb < nr_cpu_ids) -resched_cpu (ilb); - } - } - -/* -* If this cpu is idle and doing idle load balancing for all the -* cpus with ticks stopped, is it time for that to stop? -*/ -if (rq->idle_at_tick &&atomic_read (&nohz.load_balancer) == cpu && -cpumask_weight (nohz.cpu_mask) ==num_online_cpus ()) { -resched_cpu (cpu); -return ; - } - -/* -* If this cpu is idle and the idle load balancing is done by -* someone else, then no need raise the SCHED_SOFTIRQ -*/ -if (rq->idle_at_tick &&atomic_read (&nohz.load_balancer) != cpu && -cpumask_test_cpu (cpu, nohz.cpu_mask)) -return ; -#endif /* Don't need to rebalance while attached to NULL domain */ if (time_after_eq (jiffies, rq->next_balance) &&likely (!on_null_domain (cpu)))raise_softirq (SCHED_SOFTIRQ ); +#ifdef CONFIG_NO_HZ + else if (nohz_kick_needed(rq, cpu) && likely(!on_null_domain(cpu))) + nohz_balancer_kick(cpu); +#endif }static void rq_online_fair (struct rq *rq)
kernel/sched.c +31 -3
@@ -504,7 +504,7 @@ struct rq {unsigned long cpu_load[CPU_LOAD_IDX_MAX ];#ifdef CONFIG_NO_HZ u64 nohz_stamp; -unsigned char in_nohz_recently; +unsigned char nohz_balance_kick;#endif unsigned int skip_clock_update;
@@ -1202,6 +1202,27 @@ static void resched_cpu(int cpu)#ifdef CONFIG_NO_HZ /* +* In the semi idle case, use the nearest busy cpu for migrating timers +* from an idle cpu. This is good for power-savings. +* +* We don't do similar optimization for completely idle system, as +* selecting an idle cpu will add more delays to the timers than intended +* (as that cpu's timer base may not be uptodate wrt jiffies etc). +*/ +int get_nohz_timer_target (void ) +{ +int cpu =smp_processor_id (); +int i; +struct sched_domain *sd; + +for_each_domain (cpu, sd) { +for_each_cpu (i,sched_domain_span (sd)) +if (!idle_cpu (i)) +return i; + } +return cpu; +} +/* * When add_timer_on() enqueues a timer into the timer wheel of an * idle CPU then this timer might expire before the next timer event * which is scheduled to wake up that CPU. In case of a completely
@@ -7604,6 +7625,10 @@ void __init sched_init(void) rq->idle_stamp =0 ; rq->avg_idle =2 *sysctl_sched_migration_cost;rq_attach_root (rq, &def_root_domain); +#ifdef CONFIG_NO_HZ + rq->nohz_balance_kick =0 ; +init_sched_softirq_csd (&per_cpu (remote_sched_softirq_cb, i)); +#endif #endif init_rq_hrtick (rq);atomic_set (&rq->nr_iowait,0 );
@@ -7648,8 +7673,11 @@ void __init sched_init(void)zalloc_cpumask_var (&nohz_cpu_mask,GFP_NOWAIT );#ifdef CONFIG_SMP #ifdef CONFIG_NO_HZ -zalloc_cpumask_var (&nohz.cpu_mask,GFP_NOWAIT ); -alloc_cpumask_var (&nohz.ilb_grp_nohz_mask,GFP_NOWAIT ); +zalloc_cpumask_var (&nohz.idle_cpus_mask,GFP_NOWAIT ); +alloc_cpumask_var (&nohz.grp_idle_mask,GFP_NOWAIT ); +atomic_set (&nohz.load_balancer, nr_cpu_ids); +atomic_set (&nohz.first_pick_cpu, nr_cpu_ids); +atomic_set (&nohz.second_pick_cpu, nr_cpu_ids);#endif /* May be allocated at isolcpus cmdline parse time */ if (cpu_isolated_map ==NULL )
include/linux/sched.h +3 -6
@@ -272,14 +272,11 @@ extern void task_rq_unlock_wait(struct textern cpumask_var_t nohz_cpu_mask;#if defined(CONFIG_SMP ) && defined(CONFIG_NO_HZ ) -extern int select_nohz_load_balancer (int cpu); -extern int get_nohz_load_balancer (void ); +extern void select_nohz_load_balancer (int stop_tick); +extern int get_nohz_timer_target (void );extern int nohz_ratelimit (int cpu);#else -static inline int select_nohz_load_balancer (int cpu) -{ -return 0 ; -} +static inline void select_nohz_load_balancer (int stop_tick) { }static inline int nohz_ratelimit (int cpu) {
kernel/hrtimer.c +2 -6
@@ -144,12 +144,8 @@ struct hrtimer_clock_base *lock_hrtimer_static int hrtimer_get_target (int this_cpu,int pinned) {#ifdef CONFIG_NO_HZ -if (!pinned &&get_sysctl_timer_migration () &&idle_cpu (this_cpu)) { -int preferred_cpu =get_nohz_load_balancer (); - -if (preferred_cpu >=0 ) -return preferred_cpu; - } +if (!pinned &&get_sysctl_timer_migration () &&idle_cpu (this_cpu)) +return get_nohz_timer_target ();#endif return this_cpu; }
kernel/time/tick-sched.c +1 -7
@@ -408,13 +408,7 @@ void tick_nohz_stop_sched_tick(int inidl* the scheduler tick in nohz_restart_sched_tick. */ if (!ts->tick_stopped) { -if (select_nohz_load_balancer (1 )) { -/* -* sched tick not stopped! -*/ -cpumask_clear_cpu (cpu, nohz_cpu_mask); - goto out; - } +select_nohz_load_balancer (1 ); ts->idle_tick =hrtimer_get_expires (&ts->sched_timer); ts->tick_stopped =1 ;
kernel/timer.c +2 -6
@@ -679,12 +679,8 @@ __mod_timer(struct timer_list *timer, un cpu =smp_processor_id ();#if defined(CONFIG_NO_HZ ) && defined(CONFIG_SMP ) -if (!pinned &&get_sysctl_timer_migration () &&idle_cpu (cpu)) { -int preferred_cpu =get_nohz_load_balancer (); - -if (preferred_cpu >=0 ) - cpu = preferred_cpu; - } +if (!pinned &&get_sysctl_timer_migration () &&idle_cpu (cpu)) + cpu =get_nohz_timer_target ();#endif new_base =per_cpu (tvec_bases, cpu);
Peter Zijlstra
maintainerQuoted 29 lines · Suresh Siddha
From: Venkatesh Pallipadi <[email protected]>
Subject: sched: Change nohz ilb logic from pull to push modelIn the new push model, all idle CPUs indeed go into nohz mode. There is still the concept of idle load balancer (performing the load balancing on behalf of all the idle cpu's in the system). Busy CPU kicks the nohz balancer when any of the nohz CPUs need idle load balancing. The kickee CPU does the idle load balancing on behalf of all idle CPUs instead of the normal idle balance.
This addresses the below two problems with the current nohz ilb logic:
* the idle load balancer continued to have periodic ticks during idle and wokeup frequently, even though it did not have any rebalancing to do on behalf of any of the idle CPUs.
* On x86 and CPUs that have APIC timer stoppage on idle CPUs, this periodic wakeup can result in a periodic additional interrupt on a CPU doing the timer broadcast.Also currently we are migrating the unpinned timers from an idle to the cpu doing idle load balancing (when all the cpus in the system are idle, there is no idle load balancing cpu and timers get added to the same idle cpu where the request was made. So the existing optimization works only on semi idle system).
And In semi idle system, we no longer have periodic ticks on the idle load balancer CPU. Using that cpu will add more delays to the timers than intended (as that cpu's timer base may not be uptodate wrt jiffies etc). This was causing mysterious slowdowns during boot etc.
Quoted 6 lines
For now, in the semi idle case, use the nearest busy cpu for migrating timers from an idle cpu. This is good for power-savings anyway.
Signed-off-by Venkatesh Pallipadi <[email protected]>Signed-off-by Suresh Siddha <[email protected]>---
I sorted the conflict with Venki's update_cpu_load() patch as below.
Thanks!
---
kernel/sched_fair.c +5 -30
@@ -3446,6 +3446,9 @@ static void nohz_idle_balance(int this_cbreak ; } +raw_spin_lock_irq (&rq->lock); +update_cpu_load (rq); +raw_spin_unlock_irq (&rq->lock);rebalance_domains (balance_cpu,CPU_IDLE ); rq =cpu_rq (balance_cpu);
@@ -3518,40 +3521,12 @@ static void run_rebalance_domains(structrebalance_domains (this_cpu, idle); -#ifdef CONFIG_NO_HZ /* -* If this cpu is the owner for idle load balancing, then do the +* If this cpu has a pending nohz_balance_kick, then do the * balancing on behalf of the other idle cpus whose ticks are * stopped. */ -if (this_rq->idle_at_tick && -atomic_read (&nohz.load_balancer) == this_cpu) { -struct rq *rq; -int balance_cpu; - -for_each_cpu (balance_cpu, nohz.cpu_mask) { -if (balance_cpu == this_cpu) -continue ; - -/* -* If this cpu gets work to do, stop the load balancing -* work being done for other cpus. Next load -* balancing owner will pick it up. -*/ -if (need_resched ()) -break ; - - rq =cpu_rq (balance_cpu); -raw_spin_lock_irq (&rq->lock); -update_cpu_load (rq); -raw_spin_unlock_irq (&rq->lock); -rebalance_domains (balance_cpu,CPU_IDLE ); - -if (time_after (this_rq->next_balance, rq->next_balance)) - this_rq->next_balance = rq->next_balance; - } - } -#endif +nohz_idle_balance (this_cpu, idle); }static inline int on_null_domain (int cpu)
[tip:sched/core] sched: Change nohz idle load balancing logic to push model
In reply to Suresh SiddhaCommit-ID: 83cd4fe27ad8446619b2e030b171b858501de87d Gitweb: http://git.kernel.org/tip/83cd4fe27ad8446619b2e030b171b858501de87d Author: Venkatesh Pallipadi <[email protected]> AuthorDate: Fri, 21 May 2010 17:09:41 -0700 Committer: Ingo Molnar <[email protected]> CommitDate: Wed, 9 Jun 2010 10:34:52 +0200
sched: Change nohz idle load balancing logic to push model
In the new push model, all idle CPUs indeed go into nohz mode. There is still the concept of idle load balancer (performing the load balancing on behalf of all the idle cpu's in the system). Busy CPU kicks the nohz balancer when any of the nohz CPUs need idle load balancing. The kickee CPU does the idle load balancing on behalf of all idle CPUs instead of the normal idle balance.
This addresses the below two problems with the current nohz ilb logic:
* the idle load balancer continued to have periodic ticks during idle and wokeup frequently, even though it did not have any rebalancing to do on behalf of any of the idle CPUs.
* On x86 and CPUs that have APIC timer stoppage on idle CPUs, this periodic wakeup can result in a periodic additional interrupt on a CPU doing the timer broadcast.
Also currently we are migrating the unpinned timers from an idle to the cpu doing idle load balancing (when all the cpus in the system are idle, there is no idle load balancing cpu and timers get added to the same idle cpu where the request was made. So the existing optimization works only on semi idle system).
And In semi idle system, we no longer have periodic ticks on the idle load balancer CPU. Using that cpu will add more delays to the timers than intended (as that cpu's timer base may not be uptodate wrt jiffies etc). This was causing mysterious slowdowns during boot etc.
For now, in the semi idle case, use the nearest busy cpu for migrating timers from an idle cpu. This is good for power-savings anyway.
LKML-Reference: <[email protected]>
--- include/linux/sched.h | 9 +- kernel/hrtimer.c | 8 +- kernel/sched.c | 34 +++++- kernel/sched_fair.c | 329 ++++++++++++++++++++++++++++------------------ kernel/time/tick-sched.c | 8 +- kernel/timer.c | 8 +- 6 files changed, 237 insertions(+), 159 deletions(-)
include/linux/sched.h +3 -6
@@ -271,14 +271,11 @@ extern int runqueue_is_locked(int cpu);extern cpumask_var_t nohz_cpu_mask;#if defined(CONFIG_SMP ) && defined(CONFIG_NO_HZ ) -extern int select_nohz_load_balancer (int cpu); -extern int get_nohz_load_balancer (void ); +extern void select_nohz_load_balancer (int stop_tick); +extern int get_nohz_timer_target (void );extern int nohz_ratelimit (int cpu);#else -static inline int select_nohz_load_balancer (int cpu) -{ -return 0 ; -} +static inline void select_nohz_load_balancer (int stop_tick) { }static inline int nohz_ratelimit (int cpu) {
kernel/hrtimer.c +2 -6
@@ -144,12 +144,8 @@ struct hrtimer_clock_base *lock_hrtimer_base(const struct hrtimer *timer,static int hrtimer_get_target (int this_cpu,int pinned) {#ifdef CONFIG_NO_HZ -if (!pinned &&get_sysctl_timer_migration () &&idle_cpu (this_cpu)) { -int preferred_cpu =get_nohz_load_balancer (); - -if (preferred_cpu >=0 ) -return preferred_cpu; - } +if (!pinned &&get_sysctl_timer_migration () &&idle_cpu (this_cpu)) +return get_nohz_timer_target ();#endif return this_cpu; }
kernel/sched.c +31 -3
@@ -460,7 +460,7 @@ struct rq {unsigned long last_load_update_tick;#ifdef CONFIG_NO_HZ u64 nohz_stamp; -unsigned char in_nohz_recently; +unsigned char nohz_balance_kick;#endif unsigned int skip_clock_update;
@@ -1195,6 +1195,27 @@ static void resched_cpu(int cpu)#ifdef CONFIG_NO_HZ /* +* In the semi idle case, use the nearest busy cpu for migrating timers +* from an idle cpu. This is good for power-savings. +* +* We don't do similar optimization for completely idle system, as +* selecting an idle cpu will add more delays to the timers than intended +* (as that cpu's timer base may not be uptodate wrt jiffies etc). +*/ +int get_nohz_timer_target (void ) +{ +int cpu =smp_processor_id (); +int i; +struct sched_domain *sd; + +for_each_domain (cpu, sd) { +for_each_cpu (i,sched_domain_span (sd)) +if (!idle_cpu (i)) +return i; + } +return cpu; +} +/* * When add_timer_on() enqueues a timer into the timer wheel of an * idle CPU then this timer might expire before the next timer event * which is scheduled to wake up that CPU. In case of a completely
@@ -7791,6 +7812,10 @@ void __init sched_init(void) rq->idle_stamp =0 ; rq->avg_idle =2 *sysctl_sched_migration_cost;rq_attach_root (rq, &def_root_domain); +#ifdef CONFIG_NO_HZ + rq->nohz_balance_kick =0 ; +init_sched_softirq_csd (&per_cpu (remote_sched_softirq_cb, i)); +#endif #endif init_rq_hrtick (rq);atomic_set (&rq->nr_iowait,0 );
@@ -7835,8 +7860,11 @@ void __init sched_init(void)zalloc_cpumask_var (&nohz_cpu_mask,GFP_NOWAIT );#ifdef CONFIG_SMP #ifdef CONFIG_NO_HZ -zalloc_cpumask_var (&nohz.cpu_mask,GFP_NOWAIT ); -alloc_cpumask_var (&nohz.ilb_grp_nohz_mask,GFP_NOWAIT ); +zalloc_cpumask_var (&nohz.idle_cpus_mask,GFP_NOWAIT ); +alloc_cpumask_var (&nohz.grp_idle_mask,GFP_NOWAIT ); +atomic_set (&nohz.load_balancer, nr_cpu_ids); +atomic_set (&nohz.first_pick_cpu, nr_cpu_ids); +atomic_set (&nohz.second_pick_cpu, nr_cpu_ids);#endif /* May be allocated at isolcpus cmdline parse time */ if (cpu_isolated_map ==NULL )
kernel/sched_fair.c +198 -131
448 lines not on this page · raw message
kernel/time/tick-sched.c +1 -7
@@ -408,13 +408,7 @@ void tick_nohz_stop_sched_tick(int inidle)* the scheduler tick in nohz_restart_sched_tick. */ if (!ts->tick_stopped) { -if (select_nohz_load_balancer (1 )) { -/* -* sched tick not stopped! -*/ -cpumask_clear_cpu (cpu, nohz_cpu_mask); - goto out; - } +select_nohz_load_balancer (1 ); ts->idle_tick =hrtimer_get_expires (&ts->sched_timer); ts->tick_stopped =1 ;
kernel/timer.c +2 -6
@@ -679,12 +679,8 @@ __mod_timer(struct timer_list *timer, unsigned long expires, cpu =smp_processor_id ();#if defined(CONFIG_NO_HZ ) && defined(CONFIG_SMP ) -if (!pinned &&get_sysctl_timer_migration () &&idle_cpu (cpu)) { -int preferred_cpu =get_nohz_load_balancer (); - -if (preferred_cpu >=0 ) - cpu = preferred_cpu; - } +if (!pinned &&get_sysctl_timer_migration () &&idle_cpu (cpu)) + cpu =get_nohz_timer_target ();#endif new_base =per_cpu (tvec_bases, cpu);
Hi.
I finally found the time to give this patch series a try. Minor updates were required, but I'm now running it against 2.6.34.
"Load balancing tick" is still number one in my powertop list of top causes of wakeups (sitting at ~60 to 80 per second as I type this, with ~170 wakeups per second total). Comparing this to the numbers I posted earlier, we seem to have a win.
I do wonder, though, whether further work could still be done. If I take one core offline, for example, I'm still getting load balancing ticks. Intuitively, I'd expect there to be no need for them with only one core available. But maybe I'm just ignorant of what's going on.
Regards,
Nigel
Hey,
Quoted 9 lines · Nigel Cunningham
"Load balancing tick" is still number one in my powertop list of top causes of wakeups (sitting at ~60 to 80 per second as I type this, with ~170 wakeups per second total). Comparing this to the numbers I posted earlier, we seem to have a win.
I do wonder, though, whether further work could still be done. If I take one core offline, for example, I'm still getting load balancing ticks. Intuitively, I'd expect there to be no need for them with only one core available. But maybe I'm just ignorant of what's going on.
Are you using HZ=1000, and is the CPU active ~ 6-8 % ? If so, is it just the regular timer tick while the CPU is active, and so not a real "wakeup"? (Or possibly double the number if both CPUs are active)
Best,
Dominik
Hi.
Quoted 8 lines · Dominik Brodowski
Hey,
Quoted 5 lines · Nigel Cunningham
"Load balancing tick" is still number one in my powertop list of top causes of wakeups (sitting at ~60 to 80 per second as I type this, with ~170 wakeups per second total). Comparing this to the numbers I posted earlier, we seem to have a win.
Quoted 8 lines
Quoted 4 lines
I do wonder, though, whether further work could still be done. If I take one core offline, for example, I'm still getting load balancing ticks. Intuitively, I'd expect there to be no need for them with only one core available. But maybe I'm just ignorant of what's going on.
Are you using HZ=1000, and is the CPU active ~ 6-8 % ? If so, is it just the regular timer tick while the CPU is active, and so not a real "wakeup"? (Or possibly double the number if both CPUs are active)
HZ is 1000, and the CPU running percentage in Powertop is low (2% when I'm not typing).
Regards,
Nigel
Hey
Quoted 14 lines · Nigel Cunningham
Quoted 13 lines · Dominik Brodowski
Hey,
Quoted 9 lines · Nigel Cunningham
"Load balancing tick" is still number one in my powertop list of top causes of wakeups (sitting at ~60 to 80 per second as I type this, with ~170 wakeups per second total). Comparing this to the numbers I posted earlier, we seem to have a win.
I do wonder, though, whether further work could still be done. If I take one core offline, for example, I'm still getting load balancing ticks. Intuitively, I'd expect there to be no need for them with only one core available. But maybe I'm just ignorant of what's going on.
Quoted 6 lines
Quoted 3 lines
Are you using HZ=1000, and is the CPU active ~ 6-8 % ? If so, is it just the regular timer tick while the CPU is active, and so not a real "wakeup"? (Or possibly double the number if both CPUs are active)
HZ is 1000, and the CPU running percentage in Powertop is low (2% when I'm not typing).
Still, that'd count for up to 4 % of the reported ticks. On my system, this phenomenon accounts pretty much for the events powertop calls "load balancin ticks". I wonder whether user- or kernelspace should be more smart to not consider something a wakeup event if it wasn't a wakeup, i.e. to ignore timer events from timer_stat / powertop if the CPU wasn't actually idle...
Best,
Dominik