sched: fix nohz idle load balancer issues

While trying to test recently introduced cpu bandwidth control feature for non-realtime tasks, we noticed "more than expected" idle time, which reduced considerably when booted with nohz=off. This patch is an attempt to fix that discrepancy so that we see little variance in idle time between nohz=on and nohz=off.

Test setup:

Machine : 16-cpus (2 Quad-core w/ HT enabled)
Kernel : Latest code (HEAD at 6e8d0472ea63969e2df77c7e84741495fedf7d9b) found

	  at git://tesla.tglx.de/git/linux-2.6-tip

Cgroups :

5 in number (/L1/L2/C1 - /L1/L2/C5), each having {2, 2, 4, 8, 16} tasks respectively. /L1 and /L2 were added to the hierarchy to mimic cgroup hierarchy created by libvirt and otherwise do not contain any tasks. Each cgroup has cpu.shares proportional to # of tasks in it. For ex: /L1/L2/C1's cpu.shares = 2 * 1024 = 2048, C3's cpu.shares = 4096 etc. Further, each task is placed in its own (sub-)cgroup with default shares of 1024 and a capped usage of 50% CPU.

        /L1/L2/C1/C1_1/Task1  -> capped at 50% cpu usage
        /L1/L2/C1/C1_2/Task2  -> capped at 50% cpu usage
        /L1/L2/C2/C2_1/Task3  -> capped at 50% cpu usage
        /L1/L2/C2/C2_2/Task3  -> capped at 50% cpu usage
        /L1/L2/C3/C3_1/Task4  -> capped at 50% cpu usage
        /L1/L2/C3/C3_2/Task4  -> capped at 50% cpu usage
        /L1/L2/C3/C3_3/Task4  -> capped at 50% cpu usage
        /L1/L2/C3/C3_4/Task4  -> capped at 50% cpu usage
        ...
        /L1/L2/C5/C5_16/Task32 -> capped at 50% cpu usage

So we have 32 tasks, each capped at 50% CPU usage, run on a 16-CPU system, which one may expect to consume all CPU resource leaving no idle time. While that may be "insane" expectation, the goal is to minimize idle time in this situation as much as possible.

I am using a slightly modified script provided at
https://lkml.org/lkml/2011/6/7/352 for generating this test scenario - can make that available if required.

Idle time was sampled every second (using vmstat) over a window of 60 seconds and was found as below:

Idle time Average Std-deviation Min Max
============================================================

nohz=off 4% 0.5% 3% 5%
nohz=on 10% 2.4% 5% 18%
nohz=on + patch 5.3% 1.3% 3% 9%

The patch cuts down idle time significantly when kernel is booted with 'nohz=on' (which is good for saving power when idle).

What are the tasks doing which are running - are they plain burning CPU time? If the tasks do something more complex, do you also have a measure of how much work gets done by the workload, per second?

Percentual changes in that metric would be nice to include in an additional column - that way we can see that it's not only idle that has gone down, but workload performance has gone up too.

In fact even if there was only a CPU burning loop in the workload it would be nice to make that somewhat more sophisticated by letting it process some larger array that has a cache footprint. This mimics real workloads that don't just spin burning CPU time but do real data processing.

For any non-trivial workload it's possible to reduce idle time without much increase in work done and in fact it's possible to decrease idle time *and* work done - so we need to see more clearly here and make sure it's all an improvement.

Quoted 3 lines · Ingo Molnar

What are the tasks doing which are running - are they plain burning CPU time? If the tasks do something more complex, do you also have a measure of how much work gets done by the workload, per second?

They are simple cpu hogs at this time.

Quoted 3 lines

Percentual changes in that metric would be nice to include in an additional column - that way we can see that it's not only idle that has gone down, but workload performance has gone up too.

Ok, good point.

Quoted 10 lines

In fact even if there was only a CPU burning loop in the workload it would be nice to make that somewhat more sophisticated by letting it process some larger array that has a cache footprint. This mimics real workloads that don't just spin burning CPU time but do real data processing.

For any non-trivial workload it's possible to reduce idle time without much increase in work done and in fact it's possible to decrease idle time *and* work done - so we need to see more clearly here and make sure it's all an improvement.

Ok - I will run a cpu intensive benchmark and get some numbers on how benchmark score varies with the patch applied. I can pick a simple matrix multiplication type benchmark, unless you have other suggestions!

While trying to test recently introduced cpu bandwidth control feature for non-realtime tasks, we noticed "more than expected" idle time, which reduced considerably when booted with nohz=off. This patch is an attempt to fix that discrepancy so that we see little variance in idle time between nohz=on and nohz=off.

Test setup:

Machine : 16-cpus (2 Quad-core w/ HT enabled)
Kernel  : Latest code (HEAD at 6e8d0472ea63969e2df77c7e84741495fedf7d9b) found at git://tesla.tglx.de/git/linux-2.6-tip

Cgroups :

5 in number (/L1/L2/C1 - /L1/L2/C5), each having {2, 2, 4, 8, 16} tasks respectively. /L1 and /L2 were added to the hierarchy to mimic cgroup hierarchy created by libvirt and otherwise do not contain any tasks. Each cgroup has cpu.shares proportional to # of tasks in it. For ex: /L1/L2/C1's cpu.shares = 2 * 1024 = 2048, C3's cpu.shares = 4096 etc. Further, each task is placed in its own (sub-)cgroup with default shares of 1024 and a capped usage of 50% CPU.

       /L1/L2/C1/C1_1/Task1  -> capped at 50% cpu usage /L1/L2/C1/C1_2/Task2  -> capped at 50% cpu usage /L1/L2/C2/C2_1/Task3  -> capped at 50% cpu usage /L1/L2/C2/C2_2/Task3  -> capped at 50% cpu usage /L1/L2/C3/C3_1/Task4  -> capped at 50% cpu usage /L1/L2/C3/C3_2/Task4  -> capped at 50% cpu usage /L1/L2/C3/C3_3/Task4  -> capped at 50% cpu usage /L1/L2/C3/C3_4/Task4  -> capped at 50% cpu usage
       ...
       /L1/L2/C5/C5_16/Task32 -> capped at 50% cpu usage

So we have 32 tasks, each capped at 50% CPU usage, run on a 16-CPU system, which one may expect to consume all CPU resource leaving no idle time. While that may be "insane" expectation, the goal is to minimize idle time in this situation as much as possible.

I am using a slightly modified script provided at
https://lkml.org/lkml/2011/6/7/352 for generating this test scenario - can make that available if required.

Idle time was sampled every second (using vmstat) over a window of 60 seconds and was found as below:

Idle time               Average  Std-deviation   Min    Max
============================================================

nohz=off                4%        0.5%           3%      5% nohz=on                 10%       2.4%           5%      18% nohz=on + patch         5.3%      1.3%           3%      9%

The patch cuts down idle time significantly when kernel is booted with 'nohz=on' (which is good for saving power when idle).

Description of the patch
========================

Reviewing idle load balancer code and testing it with some trace_printk(), I observed the following:

1. I had put a trace_printk() in nohz_idle_balance() as below:

       nohz_idle_balance()
       {

       if (idle != CPU_IDLE || !this_rq->nohz_balance_kick) return;

       ..

               trace_printk("Running rebalance for %d\n", balance_cpu);

               rebalance_domains(balance_cpu, CPU_IDLE); }

   I *never* got that printed during the test. Further investigation revealed that ilb_cpu was bailing out early because idle = CPU_NOT_IDLE i.e ilb_cpu was no longer idle_at_tick by the time it got around to handle the kick. As a result, no one was truly doing a load balance on behalf of sleeping idle cpus.

2. nohz.next_interval is supposed to reflect min(rq->next_balance) across all sleeping idle cpus. As new idle cpus go tickless, we don't update nohz.next_balance to reflect the fact that the idle cpu going tickless may have rq->next_balance earlier than nohz.next_balance. Putting some trace_printk() I noticed that difference (between nohz.next_interval and its desired new value) was between  30 - 1673 ticks (CONFIG_HZ=1000 in my case).

3. AFAICS CPUs desigated as first_pick_cpu or second_pick_cpu can be idle for sometime before going tickless. When that happens, they stop kicking ilb_cpu. More importantly other busy cpus also don't kick ilb_cpu as they are neither first nor second pick_cpu. In this situation, ilb_cpu is not woken up in a timely manner to do idle load balance.

This patch is an attempt to solve above issues observed with idle load balancer.

- The patch causes a ilb_cpu (that was kicked) to kick another idle cpu in case it was found to be !idle_at_tick (so that another idle cpu can do load balance on behalf of idle cpus). This fixes issue #1

- The patch introduces a 'nohz.next_balance_lock' spinlock which is used to update nohz.next_balance, so that it stays as min(rq->next_balance). This fixes issue #2. I don't like a global spinlock so much, but don't see easy way out. Besides, this lock is taken in context of idle cpu.

- It allows any busy cpu to kick ilb_cpu if it has greater than 2 runnable tasks. This addresses issue #3

The patch is against latest tip code (HEAD at 6e8d0472ea63969e2df77c7e84741495fedf7d9b) found at
git://tesla.tglx.de/git/linux-2.6-tip

Another improvement that we may want to look at is to have second_pick_cpu avoid kicking in case there is no power/performance benefit (i.e its not a thread/core sibling of first_pick_cpu).

Comments/flames welcome!

Signed-off-by Srivatsa Vaddagiri <[email protected]>

---

Index: current/kernel/sched.c
===================================================================

kernel/sched.c +1 -0

@@ -8355,6 +8355,7 @@ void __init sched_init(void)
        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);
+       spin_lock_init(&nohz.next_balance_lock);
  #endif
        /* May be allocated at isolcpus cmdline parse time */
        if (cpu_isolated_map == NULL)

Index: current/kernel/sched_fair.c
===================================================================

kernel/sched_fair.c +0 -0

@@ -4302,6 +4302,7 @@ static struct {
        cpumask_var_t idle_cpus_mask;
        cpumask_var_t grp_idle_mask;

       unsigned long next_balance;     /* in jiffy units */
+       spinlock_t next_balance_lock;   /* Serialize update to 'next_balance' */ } nohz ____cacheline_aligned;

 int get_nohz_load_balancer(void)

kernel/sched_fair.c +30 -7

@@ -4443,8 +4444,12 @@ static void nohz_balancer_kick(int cpu)
 
        ilb_cpu = get_nohz_load_balancer();
 
-       if (ilb_cpu >= nr_cpu_ids) {
-               ilb_cpu = cpumask_first(nohz.idle_cpus_mask);
+       /*
+        * ilb_cpu itself can be attempting to kick another idle cpu. Pick
+        * another idle cpu in that case.
+        */
+       if (ilb_cpu >= nr_cpu_ids || ilb_cpu == cpu) {
+               ilb_cpu = cpumask_any_but(nohz.idle_cpus_mask, cpu);
                if (ilb_cpu >= nr_cpu_ids)
                        return;
        }

@@ -4459,6 +4464,18 @@ static void nohz_balancer_kick(int cpu)
        return;
  }
 
+/* Update nohz.next_balance with a new minimum value */
+static inline void set_nohz_next_balance(unsigned long next_balance)
+{
+       if (time_after(next_balance, nohz.next_balance))
+               return;
+
+       spin_lock(&nohz.next_balance_lock);
+       if (time_before(next_balance, nohz.next_balance))
+               nohz.next_balance = next_balance;
+       spin_unlock(&nohz.next_balance_lock);
+}
+
  /*
  * 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

@@ -4517,8 +4534,10 @@ void select_nohz_load_balancer(int stop_
                                resched_cpu(new_ilb);
                                return;
                        }
+                       set_nohz_next_balance(cpu_rq(cpu)->next_balance);
                        return;
                }
+               set_nohz_next_balance(cpu_rq(cpu)->next_balance);
        } else {
                if (!cpumask_test_cpu(cpu, nohz.idle_cpus_mask))
                        return;

@@ -4634,9 +4653,16 @@ static void nohz_idle_balance(int this_c
        struct rq *rq;
        int balance_cpu;
 
-       if (idle != CPU_IDLE || !this_rq->nohz_balance_kick)
+       if (!this_rq->nohz_balance_kick)
                return;
 
+       /* Wakeup another idle cpu to do idle load balance if we got busy */
+       if (idle != CPU_IDLE) {
+               nohz_balancer_kick(this_cpu);
+               this_rq->nohz_balance_kick = 0;
+               return;
+       }
+
        for_each_cpu(balance_cpu, nohz.idle_cpus_mask) {
                if (balance_cpu == this_cpu)
                        continue;

@@ -4646,10 +4672,8 @@ static void nohz_idle_balance(int this_c
                 * work being done for other cpus. Next load
                 * balancing owner will pick it up.
                 */
-               if (need_resched()) {
-                       this_rq->nohz_balance_kick = 0;
+               if (need_resched())
                        break;
-               }
 
                raw_spin_lock_irq(&this_rq->lock);
                update_rq_clock(this_rq);

@@ -4663,7 +4687,7 @@ static void nohz_idle_balance(int this_c
                if (time_after(this_rq->next_balance, rq->next_balance))
                        this_rq->next_balance = rq->next_balance;
        }
-       nohz.next_balance = this_rq->next_balance;
+       set_nohz_next_balance(this_rq->next_balance);
        this_rq->nohz_balance_kick = 0;
  }
 

@@ -4695,8 +4719,11 @@ static inline int nohz_kick_needed(struc
        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)
+           second_pick_cpu < nr_cpu_ids && second_pick_cpu != cpu) {
+               if (rq->nr_running > 1)
+                       return 1;
               return 0;
+       }

       ret = atomic_cmpxchg(&nohz.first_pick_cpu, nr_cpu_ids, cpu); if (ret == nr_cpu_ids || ret == cpu) {

kernel/sched_fair.c +1 -1

@@ -4752,7 +4779,7 @@ static inline void trigger_load_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)))
+       if (nohz_kick_needed(rq, cpu) && likely(!on_null_domain(cpu)))
                nohz_balancer_kick(cpu);
  #endif
  }

Quoted 16 lines · Srivatsa Vaddagiri

Reviewing idle load balancer code and testing it with some trace_printk(), I observed the following:

1. I had put a trace_printk() in nohz_idle_balance() as below:

       nohz_idle_balance()
       {

       if (idle != CPU_IDLE || !this_rq->nohz_balance_kick)
               return;

       ..

               trace_printk("Running rebalance for %d\n", balance_cpu);

Quoted 8 lines

               rebalance_domains(balance_cpu, CPU_IDLE);
       }

I *never* got that printed during the test. Further investigation revealed that ilb_cpu was bailing out early because idle = CPU_NOT_IDLE i.e ilb_cpu was no longer idle_at_tick by the time it got around to handle the kick. As a result, no one was truly doing a load balance on behalf of sleeping idle cpus.

Quoted 6 lines

This patch is an attempt to solve above issues observed with idle load balancer.

- The patch causes a ilb_cpu (that was kicked) to kick another idle cpu in case it was found to be !idle_at_tick (so that another idle cpu can do load balance on behalf of idle cpus). This fixes issue #1

Some comments:

Another potential change here is to
- either reverse the order of rebalance_domains() and nohz_idle_balance() in run_rebalance_domains()
- or to kick another idle CPU in case of need_resched() in nohz_idle_balance. This should help with idle balance of tickless CPUs when ilb CPU gets a new task through load balance and hence aborts ilb.

One of the reasons why we saw lib_cpu not idle is probably because that info was stale.

Consider this scenario.

a. got a tick when the cpu was busy, so idle_at_tick was not set b. cpu went idle
c. same cpu got the kick IPI from other busy cpu
d. and as it has idle_at_tick not set, it couldn't proceed with the nohz idle balance.

I think we are mostly likely seeing the above mentioned scenario.

Also Vatsa, there is a deadlock associated by using __smp_call_funciton_single() in the nohz_balancer_kick(). So I am planning to remove the IPI that is used to kick the nohz balancer and instead use the resched_cpu logic to kick the nohz balancer.

I will post this patch mostly tomorrow. That patch will not use the idle_at_tick check in the nohz_idle_balance(). So that should address your issue in some cases if not most.

Quoted 3 lines · Suresh Siddha

I will post this patch mostly tomorrow. That patch will not use the idle_at_tick check in the nohz_idle_balance(). So that should address your issue in some cases if not most.

Ok ..would be glad to test your change ..

Anyways, this appended patch is just for your quick experiment. I will think a bit more tomorrow morning before sending the patch with complete changelog. Thanks.

So ended up with using kick_process() and the scheduler_ipi() context to trigger the SCHED_SOFTIRQ instead of using smp call function vector sequence (which has a deadlock scenario in the context of heavy interrupts which I can explain in detail when I send the complete changelog). And also I am explicitly requesting for idle balance to address the stale idle_at_tick condition.

I'd be interested in hearing more about that deadlock, because when allocating your own csd and not waiting for the result __smp_call_function_single() should be deadlock free.

Quoted 4 lines

kernel/sched.c +0 -0

@@ -2733,6 +2733,11 @@ void scheduler_ipi(void)
        struct rq *rq = this_rq();
        struct task_struct *list = xchg(&rq->wake_list, NULL);
 

kernel/sched.c void scheduler_ipi(void) · line 2739

Quoted 4 lines

kernel/sched.c +4 -0

+       if (unlikely((rq->idle == current) && rq->nohz_balance_kick)) {
+               rq->idle_balance = 1;
+               raise_softirq_irqoff(SCHED_SOFTIRQ);
+       } 

This can end up being outside of irq_enter()/irq_exit(), which is probably not what you want. See the somewhat large comment right below here.

Some comments:

Another potential change here is to
- either reverse the order of rebalance_domains() and nohz_idle_balance() in run_rebalance_domains()

- or to kick another idle CPU in case of need_resched() in nohz_idle_balance. This should help with idle balance of tickless CPUs when ilb CPU gets a new task through load balance and hence aborts ilb.

Quoted 5 lines

- The patch introduces a 'nohz.next_balance_lock' spinlock which is used to update nohz.next_balance, so that it stays as min(rq->next_balance). This fixes issue #2. I don't like a global spinlock so much, but don't see easy way out. Besides, this lock is taken in context of idle cpu.

The problem I see with this is that there is no way to reset next_balance when a previously idle CPU goes busy. This probably will result in frequent ilb than needed and potential power and performance(due to SMT or freq timer interrupts) impact.

Quoted 2 lines

- It allows any busy cpu to kick ilb_cpu if it has greater than 2 runnable tasks. This addresses issue #3

This again may have power impact with frequent kicking.

Especially with higher number of logical CPUs. Likely cleaner way is to clear first_pick, second_pick on idle instead of clearing on tickless.

Would be interesting to see some tests power impact (or number of interrupts, resched IPIs etc) of this change. Both with netbook kind of systems and on servers with partially idle configuration.

unless we want to go for more sophisticated like a sorted list of rq->next_balance in a rb-tree

Quoted 2 lines · Srivatsa Vaddagiri

unless we want to go for more sophisticated like a sorted list of rq->next_balance in a rb-tree

Given that this list will need to be global (and not per-cpu) and it will need to be updated reqularly (even when cpus are busy and as they update their rq->next_balance), that will probably not fly!

Quoted 2 lines

Especially with higher number of logical CPUs. Likely cleaner way is to clear first_pick, second_pick on idle instead of clearing on tickless.

I think I tried that (cleared first/second_pick_cpu in nohz_kick_needed() upon idle) but didn't get the best results. Let me try that again and post idle time numbers.

Quoted 5 lines · Srivatsa Vaddagiri

Quoted 2 lines

Especially with higher number of logical CPUs. Likely cleaner way is to clear first_pick, second_pick on idle instead of clearing on tickless.

I think I tried that (cleared first/second_pick_cpu in nohz_kick_needed() upon idle) but didn't get the best results.