sched: steer waking task to empty cfs_rq for better latencies

During my investigation of a performance issue, I found that we can do a better job of reducing latencies for a waking task by steering it towards a cpu where it will get better sleeper credits.

Consider a system with two nodes: N0-N1, each with 4 cpus and a cgroup /a which is of highest priority. Further all 4 cpus in a node are in the same llc (MC) domain.

		  	N0		   N1
			(0,1,2,3)	(4,5,6,7)

rq.nr_run -> 2 1 1 1 2 2 1 1
/a cfs_rq.nr_run -> 0 0 0 0 0 0 0 1

Consider a task of "/a" waking up after a short (< sysctl_sched_latency) sleep. Its prev_cpu was 7. select_idle_sibling(), failing to find a idle core, simply wakes up the task on CPU7, where it may be unable to preempt the currently running task (as its new vruntime is not sufficiently behind currently running tasks vruntime - owing to the short sleep it incurred). As a result, the task woken up is unable to run immediately and thus incurs some latency.

A better choice would be to find a cpu in cpu7's MC domain where its cgroup has 0 tasks (thus allowing the waking task to get better sleeper credits).

Patch below implements this idea. Some results with various benchmarks is enclosed.

Machine : 2 Quad-core Intel X5570 CPU w/ H/T enabled (16 cpus) Kernel : tip (HEAD at 2adb096)
guest VM : 2.6.18 linux kernel based enterprise guest

Benchmarks are run in two scenarios:

1. BM -> Bare Metal. Benchmark is run on bare metal in root cgroup
2. VM -> Benchmark is run inside a guest VM. Several cpu hogs (in various cgroups) are run on host. Cgroup setup is as below:

/libvirt/qemu/VM (cpu.shares = 8192. guest VM w/ 8 vcpus) /libvirt/qemu/hoga[bcd] (cpu.shares = 1024. hosts 4 cpu hogs each)

Mean and std. dev. (in brackets) for both tip and tip+patch cases provided below:

BM scenario:
tip tip+patch Remarks
mean(std. dev) mean (std. dev)

volano 1 (6.5%) 0.97 (4.7%) 3% loss
sysbench [n1] 1 (0.6%) 1.004 (0.7%) 0.4% win
tbench 1 [n2] 1 (2%) 1.024 (1.6%) 2.4% win
pipe bench [n3] 1 (5.5%) 1.009 (2.5%) 0.9% win

VM scenario

sysbench [n4] 1 (1.2%) 2.21 (1.3%) 121% win
httperf [n5] 1 (5.7%) 1.522 (6%) 52.2% win
tbench 8 [n6] 1 (3.1%) 1.91 (6.4%) 91% win
volano 1 (4.3%) 1.06 (2.8%) 6% win
Trade 1 1.94 94% win

Notes:

n1. sysbench was run with 16 threads.
n2. tbench was run on localhost with 1 client
n3. ops/sec metric from pipe bench captured. pipe bench run as:
perf stat --repeat 10 --null perf bench sched pipe
n4. sysbench was run (inside VM) with 8 threads.
n5. httperf was run as with burst-length of 100 and wsess of 100,500,0.
Webserver was running inside VM while benchmark was run on a physically different host.
n6. tbench was run over network with 8 clients

This is an improved version of the patch previously published that minimizes/avoids regressions seen earlier:

	https://lkml.org/lkml/2012/3/22/220 

Comments/flames wellcome!

--

Steer a waking task towards a cpu where its cgroup has zero tasks (in order to provide it better sleeper credits and hence reduce its wakeup latency).

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

Index: current/kernel/sched/fair.c
===================================================================
@@ -2459,6 +2459,32 @@ static long effective_load(struct task_g
 
 	return wl;
 }
+
+/*
+ * Look for a CPU within @target's MC domain where the task's cgroup has
+ * zero tasks in its cfs_rq.
+ */
+static __always_inline int
+select_idle_cfs_rq(struct task_struct *p, int target)
+{
+	struct cpumask tmpmask;
+	struct task_group *tg = task_group(p);
+	struct sched_domain *sd;
+	int i;
+
+	if (tg == &root_task_group)
+		return target;
+
+	sd = rcu_dereference(per_cpu(sd_llc, target));
+	cpumask_and(&tmpmask, sched_domain_span(sd), tsk_cpus_allowed(p));
+	for_each_cpu(i, &tmpmask) {
+		if (!tg->cfs_rq[i]->nr_running)
+			return i;
+	}
+
+	return target;
+}
+
 #else
 
 static inline unsigned long effective_load(struct task_group *tg, int cpu,

@@ -2467,6 +2493,12 @@ static inline unsigned long effective_lo
 	return wl;
 }
 
+static __always_inline int
+select_idle_cfs_rq(struct task_struct *p, int target)
+{
+	return target;
+}
+
 #endif
 
 static int wake_affine(struct sched_domain *sd, struct task_struct *p, int sync)

@@ -2677,6 +2709,13 @@ next:
 			sg = sg->next;
 		} while (sg != sd->groups);
 	}
+
+	/*
+	 * Look for the next best possibility - a cpu where this task gets
+	 * (better) sleeper credits.
+	 */
+	target = select_idle_cfs_rq(p, target);
+
 done:
 	return target;
 }

That's just vile.. pjt could you post your global vruntime stuff so vatsa can have a go at that?

The workload I am up against does experience tons of wakeup (after very short (microsecond range) bursts of sleeps) and so am skeptical how the global vruntime would keep up with this kind of workload. I'd be happy to test patches and give feedback!

- vatsa

Thing is, global vruntime might fix that flaw/property you're exploiting to get that preemption.

Am curious to see how global vruntime influences task placement (esp. on wakeup). Going back to the previous example:

                        N0                 N1
                        (0,1,2,3)	(4,5,6,7)

rq.nr_run ->            2 1 1 1         2 2 1 1
/a cfs_rq.nr_run ->     0 0 0 0         0 0 0 1

CPU7 is running a task A0 belonging to "/a". Another task A1 belonging to "/a" is waking up and its prev_cpu was 7. Currently we let it wake on cpu7 itself and wait behind A0. With global vruntime, are you saying that we let A1 wake on cpu7 and it would preempt A0? That would still not be nice as A0 now incurs some additional latencies?

- vatsa

IIUC, global vruntime don't influence task placement, perhaps it'll do something related task's priority, as if wakeup task gets picked up by scheduler quickly. I'm also curious to see how global vruntime influences task placement. :-)

Thanks,
Rakib

That is, you're playing a deficiency we should fix, not exploit.

Also, you do a second loop over all those cpus right after we've already iterated them..

furthermore, that 100%+ gain is still way insane, what else is broken? Did you try those paravirt tlb-flush patches and other such weirdness?

The first loop doesn't necessarily iterate thr' all cpus (as its looking for a core that is fully idle - and hence breaks once it finds a busy sibling).

?

I have tried most benchmarks that were recommended for this kind of change. Let me know if you suggest any other benchmark ..

I will try that next. But IMHO the benefit of reduced wakeup latencies should be over and above any benefit we get from paravirtualization.

- vatsa

I got around to try pv-tlb-flush patches and it showed >100% improvement for sysbench (without the balance-on-wake patch on host). This was what readprofile showed (when pv-tlb-flush patches were absent in guest):

1135704 total                                   0.3265
636737 native_cpuid                             18192.4857
283201 __bitmap_empty                           2832.0100
137853 flush_tlb_others_ipi                     569.6405

I will try out how much they help Trade workload (which got me started on this originally) and report back (part of the problem in trying out is that pv-tlb-flush platches are throwing wierd problems - which Nikunj is helping investigate).

In any case, we can't expect users to be able to easily upgrade their guest VM kernels and so I am still looking for a solution that works for older guest VM kernels. Paul, hope I can get the global vruntime patches from you soon to test how much it helps!

- vatsa

A bug, the below patch should cure it. kvm_mmu_flush_tlb will queue the request, but we have already passed the phase of checking that. I will fold this in my next version.

index 6c42056..b114411 100644
@@ -1550,7 +1550,7 @@ static void kvm_set_vcpu_state(struct kvm_vcpu *vcpu)
 
        vs->state = 1;
        if (vs->flush_on_enter) {
-               kvm_mmu_flush_tlb(vcpu);
+               kvm_x86_ops->tlb_flush(vcpu);
                vs->flush_on_enter = 0;
        }