kvm: Improving directed yield in PLE handler

From: Raghavendra K T<[email protected]>

virt/kvm/kvm_main.c +3 -0

+bool kvm_vcpu_eligible_for_directed_yield(struct kvm_vcpu *vcpu)
+{
+	bool eligible;

Currently Pause Loop Exit (PLE) handler is doing directed yield to a random vcpu on pl-exit. We already have filtering while choosing the candidate to yield_to. This change adds more checks while choosing a candidate to yield_to.

On a large vcpu guests, there is a high probability of yielding to the same vcpu who had recently done a pause-loop exit. Such a yield can lead to the vcpu spinning again.

The patchset keeps track of the pause loop exit and gives chance to a vcpu which has:

(a) Not done pause loop exit at all (probably he is preempted lock-holder)

(b) vcpu skipped in last iteration because it did pause loop exit, and probably has become eligible now (next eligible lock holder)

This concept also helps in cpu relax interception cases which use same handler.

Changes since V4:
- Naming Change (Avi):
struct ple ==> struct spin_loop
cpu_relax_intercepted ==> in_spin_loop vcpu_check_and_update_eligible ==> vcpu_eligible_for_directed_yield
- mark vcpu in spinloop as not eligible to avoid influence of previous exit

Changes since V3:
- arch specific fix/changes (Christian)

Changes since v2:
- Move ple structure to common code (Avi)
- rename pause_loop_exited to cpu_relax_intercepted (Avi)
- add config HAVE_KVM_CPU_RELAX_INTERCEPT (Avi)
- Drop superfluous curly braces (Ingo)

Changes since v1:
- Add more documentation for structure and algorithm and Rename plo ==> ple (Rik).
- change dy_eligible initial value to false. (otherwise very first directed yield will not be skipped. (Nikunj)
- fixup signoff/from issue

Future enhancements:
(1) Currently we have a boolean to decide on eligibility of vcpu. It would be nice if I get feedback on guest (>32 vcpu) whether we can improve better with integer counter. (with counter = say f(log n )).

(2) We have not considered system load during iteration of vcpu. With that information we can limit the scan and also decide whether schedule() is better. [ I am able to use #kicked vcpus to decide on this But may be there are better ideas like information from global loadavg.]

(3) We can exploit this further with PV patches since it also knows about next eligible lock-holder.

Summary: There is a very good improvement for kvm based guest on PLE machine. The V5 has huge improvement for kbench.

+-----------+-----------+-----------+------------+-----------+
   base_rik    stdev       patched      stdev       %improve
+-----------+-----------+-----------+------------+-----------+
              kernbench (time in sec lesser is better)
+-----------+-----------+-----------+------------+-----------+
 1x    49.2300     1.0171    22.6842     0.3073    117.0233 %
 2x    91.9358     1.7768    53.9608     1.0154    70.37516 %
+-----------+-----------+-----------+------------+-----------+

+-----------+-----------+-----------+------------+-----------+
ebizzy (records/sec more is better)

+-----------+-----------+-----------+------------+-----------+
 1x  1129.2500    28.6793    2125.6250    32.8239    88.23334 %
 2x  1892.3750    75.1112    2377.1250   181.6822    25.61596 %
+-----------+-----------+-----------+------------+-----------+

Note: The patches are tested on x86.

Links
V4: https://lkml.org/lkml/2012/7/16/80
V3: https://lkml.org/lkml/2012/7/12/437
V2: https://lkml.org/lkml/2012/7/10/392
V1: https://lkml.org/lkml/2012/7/9/32

Raghavendra K T (3):
config: Add config to support ple or cpu relax optimzation kvm : Note down when cpu relax intercepted or pause loop exited kvm : Choose a better candidate for directed yield

---
 arch/s390/kvm/Kconfig    |    1 +
 arch/x86/kvm/Kconfig     |    1 +
 include/linux/kvm_host.h |   39 +++++++++++++++++++++++++++++++++++++++
 virt/kvm/Kconfig         |    3 +++
 virt/kvm/kvm_main.c      |   41 +++++++++++++++++++++++++++++++++++++++++
 5 files changed, 85 insertions(+), 0 deletions(-)

Quoted 87 lines · Raghavendra K T

Currently Pause Loop Exit (PLE) handler is doing directed yield to a random vcpu on pl-exit. We already have filtering while choosing the candidate to yield_to. This change adds more checks while choosing a candidate to yield_to.

On a large vcpu guests, there is a high probability of yielding to the same vcpu who had recently done a pause-loop exit. Such a yield can lead to the vcpu spinning again.

The patchset keeps track of the pause loop exit and gives chance to a vcpu which has:

(a) Not done pause loop exit at all (probably he is preempted lock-holder)

(b) vcpu skipped in last iteration because it did pause loop exit, and probably has become eligible now (next eligible lock holder)

This concept also helps in cpu relax interception cases which use same handler.

Changes since V4:
- Naming Change (Avi):

   struct ple ==>  struct spin_loop
   cpu_relax_intercepted ==>  in_spin_loop
   vcpu_check_and_update_eligible ==>  vcpu_eligible_for_directed_yield

- mark vcpu in spinloop as not eligible to avoid influence of previous exit

Changes since V3:
- arch specific fix/changes (Christian)

Changes since v2:
- Move ple structure to common code (Avi)
- rename pause_loop_exited to cpu_relax_intercepted (Avi)
- add config HAVE_KVM_CPU_RELAX_INTERCEPT (Avi)
- Drop superfluous curly braces (Ingo)

Changes since v1:
- Add more documentation for structure and algorithm and Rename

    plo ==>  ple (Rik).

- change dy_eligible initial value to false. (otherwise very first directed yield will not be skipped. (Nikunj)
- fixup signoff/from issue

Future enhancements:
(1) Currently we have a boolean to decide on eligibility of vcpu. It would be nice if I get feedback on guest (>32 vcpu) whether we can improve better with integer counter. (with counter = say f(log n )).

(2) We have not considered system load during iteration of vcpu. With that information we can limit the scan and also decide whether schedule() is better. [ I am able to use #kicked vcpus to decide on this But may be there are better ideas like information from global loadavg.]

(3) We can exploit this further with PV patches since it also knows about next eligible lock-holder.

Summary: There is a very good improvement for kvm based guest on PLE machine. The V5 has huge improvement for kbench.

+-----------+-----------+-----------+------------+-----------+
    base_rik    stdev       patched      stdev       %improve
+-----------+-----------+-----------+------------+-----------+
               kernbench (time in sec lesser is better)
+-----------+-----------+-----------+------------+-----------+
  1x    49.2300     1.0171    22.6842     0.3073    117.0233 %
  2x    91.9358     1.7768    53.9608     1.0154    70.37516 %
+-----------+-----------+-----------+------------+-----------+

+-----------+-----------+-----------+------------+-----------+
ebizzy (records/sec more is better)

+-----------+-----------+-----------+------------+-----------+
  1x  1129.2500    28.6793    2125.6250    32.8239    88.23334 %
  2x  1892.3750    75.1112    2377.1250   181.6822    25.61596 %
+-----------+-----------+-----------+------------+-----------+

Note: The patches are tested on x86.

Links
V4: https://lkml.org/lkml/2012/7/16/80
V3: https://lkml.org/lkml/2012/7/12/437
V2: https://lkml.org/lkml/2012/7/10/392
V1: https://lkml.org/lkml/2012/7/9/32

Raghavendra K T (3):
config: Add config to support ple or cpu relax optimzation kvm : Note down when cpu relax intercepted or pause loop exited kvm : Choose a better candidate for directed yield

Quoted 7 lines

---
  arch/s390/kvm/Kconfig    |    1 +
  arch/x86/kvm/Kconfig     |    1 +
  include/linux/kvm_host.h |   39 +++++++++++++++++++++++++++++++++++++++
  virt/kvm/Kconfig         |    3 +++
  virt/kvm/kvm_main.c      |   41 +++++++++++++++++++++++++++++++++++++++++
  5 files changed, 85 insertions(+), 0 deletions(-)

Reviewed-by Marcelo Tosatti<[email protected]>

Thanks Marcelo for the review. Avi, Rik, Christian, please let me know if this series looks good now.

Quoted 4 lines · Raghavendra K T

Thanks Marcelo for the review. Avi, Rik, Christian, please let me know if this series looks good now.

It looks fine to me. Christian, is this okay for s390?

Quoted 103 lines · Marcelo Tosatti

Quoted 101 lines · Raghavendra K T

Currently Pause Loop Exit (PLE) handler is doing directed yield to a random vcpu on pl-exit. We already have filtering while choosing the candidate to yield_to. This change adds more checks while choosing a candidate to yield_to.

On a large vcpu guests, there is a high probability of yielding to the same vcpu who had recently done a pause-loop exit. Such a yield can lead to the vcpu spinning again.

The patchset keeps track of the pause loop exit and gives chance to a vcpu which has:

(a) Not done pause loop exit at all (probably he is preempted lock-holder)

(b) vcpu skipped in last iteration because it did pause loop exit, and probably has become eligible now (next eligible lock holder)

This concept also helps in cpu relax interception cases which use same handler.

Changes since V4:
- Naming Change (Avi):
struct ple ==> struct spin_loop
cpu_relax_intercepted ==> in_spin_loop vcpu_check_and_update_eligible ==> vcpu_eligible_for_directed_yield
- mark vcpu in spinloop as not eligible to avoid influence of previous exit

Changes since V3:
- arch specific fix/changes (Christian)

Changes since v2:
- Move ple structure to common code (Avi)
- rename pause_loop_exited to cpu_relax_intercepted (Avi)
- add config HAVE_KVM_CPU_RELAX_INTERCEPT (Avi)
- Drop superfluous curly braces (Ingo)

Changes since v1:
- Add more documentation for structure and algorithm and Rename plo ==> ple (Rik).
- change dy_eligible initial value to false. (otherwise very first directed
yield will not be skipped. (Nikunj)
- fixup signoff/from issue

Future enhancements:
(1) Currently we have a boolean to decide on eligibility of vcpu. It would be nice if I get feedback on guest (>32 vcpu) whether we can improve better with integer counter. (with counter = say f(log n )).

(2) We have not considered system load during iteration of vcpu. With that information we can limit the scan and also decide whether schedule()
is better. [ I am able to use #kicked vcpus to decide on this But may be there are better ideas like information from global loadavg.]

(3) We can exploit this further with PV patches since it also knows about
next eligible lock-holder.

Summary: There is a very good improvement for kvm based guest on PLE machine.
The V5 has huge improvement for kbench.

+-----------+-----------+-----------+------------+-----------+
base_rik stdev patched stdev %improve
+-----------+-----------+-----------+------------+-----------+
kernbench (time in sec lesser is better)
+-----------+-----------+-----------+------------+-----------+
1x 49.2300 1.0171 22.6842 0.3073 117.0233 %
2x 91.9358 1.7768 53.9608 1.0154 70.37516 %
+-----------+-----------+-----------+------------+-----------+

+-----------+-----------+-----------+------------+-----------+
ebizzy (records/sec more is better)
+-----------+-----------+-----------+------------+-----------+
1x 1129.2500 28.6793 2125.6250 32.8239 88.23334 % 2x 1892.3750 75.1112 2377.1250 181.6822 25.61596 %
+-----------+-----------+-----------+------------+-----------+

Note: The patches are tested on x86.

Links
V4: https://lkml.org/lkml/2012/7/16/80
V3: https://lkml.org/lkml/2012/7/12/437
V2: https://lkml.org/lkml/2012/7/10/392
V1: https://lkml.org/lkml/2012/7/9/32

Raghavendra K T (3):
config: Add config to support ple or cpu relax optimzation kvm : Note down when cpu relax intercepted or pause loop exited kvm : Choose a better candidate for directed yield
---
arch/s390/kvm/Kconfig | 1 +
arch/x86/kvm/Kconfig | 1 +
include/linux/kvm_host.h | 39 +++++++++++++++++++++++++++++++++++++++ virt/kvm/Kconfig | 3 +++
virt/kvm/kvm_main.c | 41 +++++++++++++++++++++++++++++++++++++++++

5 files changed, 85 insertions(+), 0 deletions(-)

Quoted 2 lines

Reviewed-by Marcelo Tosatti<[email protected]>

Thanks Marcelo for the review. Avi, Rik, Christian, please let me know if this series looks good now.

Currently Pause Loop Exit (PLE) handler is doing directed yield to a random vcpu on pl-exit. We already have filtering while choosing the candidate to yield_to. This change adds more checks while choosing a candidate to yield_to.

On a large vcpu guests, there is a high probability of yielding to the same vcpu who had recently done a pause-loop exit. Such a yield can lead to the vcpu spinning again.

The patchset keeps track of the pause loop exit and gives chance to a vcpu which has:

(a) Not done pause loop exit at all (probably he is preempted lock-holder)

(b) vcpu skipped in last iteration because it did pause loop exit, and probably has become eligible now (next eligible lock holder)

This concept also helps in cpu relax interception cases which use same handler.

I have noticed recently that PLE/yield_to() is still not that scalable for really large guests, sometimes even with no CPU over-commit. I have a small change that make a very big difference.

First, let me explain what I saw:

Time to boot a 3.6-rc kernel in an 80-way VM on a 4 socket, 40 core, 80 thread Westmere-EX system: 645 seconds!

Host cpu: ~98% in kernel, nearly all of it in spin_lock from double runqueue lock for yield_to()

So, I added some schedstats to yield_to(), one to count when we failed this test in yield_to()

     if (task_running(p_rq, p) || p->state)

and one when we pass all the conditions and get to actually yield:

      yielded = curr->sched_class->yield_to_task(rq, p, preempt);

And during boot up of this guest, I saw:

failed yield_to() because task is running: 8368810426 successful yield_to(): 13077658
0.156022% of yield_to calls 1 out of 640 yield_to calls

Obviously, we have a problem. Every exit causes a loop over 80 vcpus, each one trying to get two locks. This is happening on all [but one] vcpus at around the same time. Not going to work well.

So, since the check for a running task is nearly always true, I moved that -before- the double runqueue lock, so 99.84% of the attempts do not take the locks. Now, I do not know is this [not getting the locks] is a problem. However, I'd rather have a little inaccurate test for a running vcpu than burning 98% of CPU in host kernel. With the change the VM boot time went to: 100 seconds, an 85% reduction in time.

I also wanted to check to see this did not affect truly over-committed situations, so I first started with smaller VMs at 2x cpu over-commit:

16 VMs, 8-way each, all running dbench (2x cpu over-commmit)
throughput +/- stddev
----- -----

ple off:        2281 +/- 7.32%  (really bad as expected)
ple on:        19796 +/- 1.36%
ple on: w/fix: 19796 +/- 1.37%  (no degrade at all)

In this case the VMs are small enough, that we do not loop through enough vcpus to trigger the problem. host CPU is very low (3-4% range) for both default ple and with yield_to() fix.

So I went on to a bigger VM:

10 VMs, 16-way each, all running dbench (2x cpu over-commit)
throughput +/- stddev
----- -----
ple on: 2552 +/- .70%
ple on: w/fix: 4621 +/- 2.12% (81% improvement!)

This is where we start seeing a major difference. Without the fix, host cpu was around 70%, mostly in spin_lock. That was reduced to 60% (and guest went from 30 to 40%). I believe this is on the right track to reduce the spin lock contention, still get proper directed yield, and therefore improve the guest CPU available and its performance.

However, we still have lock contention, and I think we can reduce it even more. We have eliminated some attempts at double runqueue lock acquire because the check for the target vcpu is running is now before the lock. However, even if the target-to-yield-to vcpu [for the same guest upon we PLE exited] is not running, the physical processor/runqueue that target-to-yield-to vcpu is located on could be running a different VM's vcpu -and- going through a directed yield, therefore that run queue lock may already acquired. We do not want to just spin and wait, we want to move to the next candidate vcpu. We need a check to see if the smp processor/runqueue is already in a directed yield. Or, perhaps we just check if that cpu is not in guest mode, and if so, we skip that yield attempt for that vcpu and move to the next candidate vcpu. So, my question is: given a runqueue, what's the best way to check if that corresponding phys cpu is not in guest mode?

Here's the changes so far (schedstat changes not included here):

Signed-off-by Andrew Theurer<[email protected]>

kernel/sched/core.c +3 -0

index fbf1fd0..f8eff8c 100644
@@ -4844,6 +4844,9 @@ bool __sched yield_to(struct task_struct *p, bool
 preempt)
 
  again:
  	p_rq = task_rq(p);
+	if (task_running(p_rq, p) || p->state) {
+		goto out_no_unlock;
+	}
  	double_rq_lock(rq, p_rq);
  	while (task_rq(p) != p_rq) {

  		double_rq_unlock(rq, p_rq);

kernel/sched/core.c +1 -2

@@ -4856,8 +4859,6 @@ again:
  	if (curr->sched_class != p->sched_class)
  		goto out;
 
-	if (task_running(p_rq, p) || p->state)
-		goto out;
 
  	yielded = curr->sched_class->yield_to_task(rq, p, preempt);
  	if (yielded) {

@@ -4879,6 +4880,7 @@ again:
 
  out:
  	double_rq_unlock(rq, p_rq);
+out_no_unlock:
  	local_irq_restore(flags);
 
  	if (yielded)

CCing PeterZ also.

Quoted 25 lines · Andrew Theurer

I have noticed recently that PLE/yield_to() is still not that scalable for really large guests, sometimes even with no CPU over-commit. I have a small change that make a very big difference.

First, let me explain what I saw:

Time to boot a 3.6-rc kernel in an 80-way VM on a 4 socket, 40 core, 80 thread Westmere-EX system: 645 seconds!

Host cpu: ~98% in kernel, nearly all of it in spin_lock from double runqueue lock for yield_to()

So, I added some schedstats to yield_to(), one to count when we failed this test in yield_to()

     if (task_running(p_rq, p) || p->state)

and one when we pass all the conditions and get to actually yield:

      yielded = curr->sched_class->yield_to_task(rq, p, preempt);

And during boot up of this guest, I saw:

Quoted 9 lines

failed yield_to() because task is running: 8368810426 successful yield_to(): 13077658
0.156022% of yield_to calls 1 out of 640 yield_to calls

Obviously, we have a problem. Every exit causes a loop over 80 vcpus, each one trying to get two locks. This is happening on all [but one] vcpus at around the same time. Not going to work well.

True and interesting. I had once thought of reducing overall O(n^2) iteration to O(n log(n)) iterations by reducing number of candidates to search to O(log(n)) instead of current O(n). May be I have to get back to my experiment modes.

Quoted 35 lines

So, since the check for a running task is nearly always true, I moved that -before- the double runqueue lock, so 99.84% of the attempts do not take the locks. Now, I do not know is this [not getting the locks] is a problem. However, I'd rather have a little inaccurate test for a running vcpu than burning 98% of CPU in host kernel. With the change the VM boot time went to: 100 seconds, an 85% reduction in time.

I also wanted to check to see this did not affect truly over-committed situations, so I first started with smaller VMs at 2x cpu over-commit:

16 VMs, 8-way each, all running dbench (2x cpu over-commmit)
throughput +/- stddev
----- -----

ple off:        2281 +/- 7.32%  (really bad as expected)
ple on:        19796 +/- 1.36%
ple on: w/fix: 19796 +/- 1.37%  (no degrade at all)

In this case the VMs are small enough, that we do not loop through enough vcpus to trigger the problem. host CPU is very low (3-4% range) for both default ple and with yield_to() fix.

So I went on to a bigger VM:

10 VMs, 16-way each, all running dbench (2x cpu over-commit)
throughput +/- stddev
----- -----
ple on: 2552 +/- .70%
ple on: w/fix: 4621 +/- 2.12% (81% improvement!)

This is where we start seeing a major difference. Without the fix, host cpu was around 70%, mostly in spin_lock. That was reduced to 60% (and guest went from 30 to 40%). I believe this is on the right track to reduce the spin lock contention, still get proper directed yield, and therefore improve the guest CPU available and its performance.

Quoted 15 lines

However, we still have lock contention, and I think we can reduce it even more. We have eliminated some attempts at double runqueue lock acquire because the check for the target vcpu is running is now before the lock. However, even if the target-to-yield-to vcpu [for the same guest upon we PLE exited] is not running, the physical processor/runqueue that target-to-yield-to vcpu is located on could be running a different VM's vcpu -and- going through a directed yield, therefore that run queue lock may already acquired. We do not want to just spin and wait, we want to move to the next candidate vcpu. We need a check to see if the smp processor/runqueue is already in a directed yield. Or, perhaps we just check if that cpu is not in guest mode, and if so, we skip that yield attempt for that vcpu and move to the next candidate vcpu. So, my question is: given a runqueue, what's the best way to check if that corresponding phys cpu is not in guest mode?

We are indeed avoiding CPUS in guest mode when we check task->flags & PF_VCPU in vcpu_on_spin path. Doesn't that suffice?

    28.60%     264266  qemu-system-x86  [kernel.kallsyms]        [k] _raw_spin_lock
     9.21%      85109  qemu-system-x86  [kernel.kallsyms]        [k] __schedule
     4.98%      46035  qemu-system-x86  [kernel.kallsyms]        [k] _raw_spin_lock_irq
     4.12%      38066  qemu-system-x86  [kernel.kallsyms]        [k] yield_to
     4.01%      37114  qemu-system-x86  [kvm]                    [k] kvm_vcpu_on_spin
     3.52%      32507  qemu-system-x86  [kernel.kallsyms]        [k] get_pid_task

     3.37%      31141  qemu-system-x86  [kernel.kallsyms]        [k] native_load_tr_desc
     3.26%      30121  qemu-system-x86  [kvm]                    [k] __vcpu_run
     3.01%      27844  qemu-system-x86  [kvm_intel]              [k] vmx_vcpu_run
     2.98%      27592  qemu-system-x86  [kernel.kallsyms]        [k] resched_task
     2.72%      25108  qemu-system-x86  [kernel.kallsyms]        [k] __srcu_read_lock
     2.25%      20758  qemu-system-x86  [kernel.kallsyms]        [k] native_write_msr_safe
     2.01%      18522  qemu-system-x86  [kvm]                    [k] kvm_vcpu_yield_to
     1.89%      17508  qemu-system-x86  [kvm]                    [k] vcpu_enter_guest

    10.12%      83285  qemu-system-x86  [kernel.kallsyms]        [k] __schedule
     9.74%      80106  qemu-system-x86  [kernel.kallsyms]        [k] yield_to
     7.38%      60686  qemu-system-x86  [kernel.kallsyms]        [k] get_pid_task
     6.28%      51695  qemu-system-x86  [kernel.kallsyms]        [k] _raw_spin_lock

     5.24%      43128  qemu-system-x86  [kvm]                    [k] kvm_vcpu_on_spin
     5.04%      41517  qemu-system-x86  [kernel.kallsyms]        [k] __srcu_read_lock
     4.11%      33823  qemu-system-x86  [kvm_intel]              [k] vmx_vcpu_run
     3.62%      29827  qemu-system-x86  [kernel.kallsyms]        [k] native_load_tr_desc
     3.57%      29413  qemu-system-x86  [kvm]                    [k] kvm_vcpu_yield_to
     3.44%      28297  qemu-system-x86  [kvm]                    [k] __vcpu_run
     2.93%      24116  qemu-system-x86  [kvm]                    [k] vcpu_enter_guest
     2.60%      21379  qemu-system-x86  [kernel.kallsyms]        [k] resched_task

Signed-off-by Andrew Theurer <[email protected]>

kernel/sched/core.c +3 -0

index fbf1fd0..c767915 100644
@@ -4844,6 +4844,9 @@ bool __sched yield_to(struct task_struct *p, bool
 preempt)
 
 again:
 	p_rq = task_rq(p);
+	if (task_running(p_rq, p) || p->state || !(p_rq->curr->flags &
 PF_VCPU)) {
+		goto out_no_unlock;
+	}
 	double_rq_lock(rq, p_rq);

kernel/sched/core.c +0 -0

 	while (task_rq(p) != p_rq) {
 		double_rq_unlock(rq, p_rq);

kernel/sched/core.c +1 -0

 	yielded = curr->sched_class->yield_to_task(rq, p, preempt);
 	if (yielded) {

@@ -4879,6 +4880,7 @@ again:
 
 out:
 	double_rq_unlock(rq, p_rq);
+out_no_unlock:
 	local_irq_restore(flags);
 
 	if (yielded)

Quoted 23 lines

Signed-off-by Andrew Theurer <[email protected]>

kernel/sched/core.c +3 -0

index fbf1fd0..c767915 100644
@@ -4844,6 +4844,9 @@ bool __sched yield_to(struct task_struct *p, bool
 preempt)
 
 again:
 	p_rq = task_rq(p);
+	if (task_running(p_rq, p) || p->state || !(p_rq->curr->flags &
 PF_VCPU)) {
+		goto out_no_unlock;
+	}
 	double_rq_lock(rq, p_rq);

kernel/sched/core.c +0 -0

 	while (task_rq(p) != p_rq) {
 		double_rq_unlock(rq, p_rq);

@@ -4856,8 +4859,6 @@ again:
 	if (curr->sched_class != p->sched_class)
 		goto out;
 

kernel/sched/core.c again: · line 4860

Quoted 2 lines

kernel/sched/core.c +0 -2

-	if (task_running(p_rq, p) || p->state)
-		goto out;

Is it possible that by this time the current thread takes double rq lock, thread p could actually be running? i.e is there merit to keep this check around even with your similar check above?

Quoted 6 lines

kernel/sched/core.c +0 -0

 	yielded = curr->sched_class->yield_to_task(rq, p, preempt);
 	if (yielded) {

@@ -4879,6 +4880,7 @@ again:
 

kernel/sched/core.c again: · line 4886

Quoted 8 lines

kernel/sched/core.c +1 -0

 out:
 	double_rq_unlock(rq, p_rq);
+out_no_unlock:
 	local_irq_restore(flags);
 
 	if (yielded)

Quoted 4 lines

Quoted 4 lines

(quoted diff) +0 -0

@@ -4856,8 +4859,6 @@ again:
    if (curr->sched_class != p->sched_class)
            goto out;
 

Quoted 6 lines

Review again: · line 4860

Quoted 2 lines

(quoted diff) +0 -2

-   if (task_running(p_rq, p) || p->state)
-           goto out;

Is it possible that by this time the current thread takes double rq lock, thread p could actually be running? i.e is there merit to keep this check around even with your similar check above?

I think that's a good idea. I'll add that back in.

Quoted 4 lines · Andrew Theurer

Quoted 4 lines

Quoted 4 lines

(quoted diff) +0 -0

@@ -4856,8 +4859,6 @@ again:
    if (curr->sched_class != p->sched_class)
            goto out;
 

Quoted 8 lines

Quoted 6 lines

kernel/sched/core.c bool __sched yield_to(struct task_struct *p, bool preempt) · line 4340

Quoted 2 lines

kernel/sched/core.c +0 -2

-   if (task_running(p_rq, p) || p->state)
-           goto out;

Is it possible that by this time the current thread takes double rq lock, thread p could actually be running? i.e is there merit to keep this check around even with your similar check above?

I think that's a good idea. I'll add that back in.

Right, it needs to still be there, the test before acquiring p_rq is an optimistic test to avoid work, but you have to still test it once you acquire p_rq since the rest of the code relies on this not being so.

How about something like this instead.. ?

---
 kernel/sched/core.c | 35 ++++++++++++++++++++++++++---------
 1 file changed, 26 insertions(+), 9 deletions(-)

kernel/sched/core.c +0 -0

index c46a011..c9ecab2 100644
@@ -4300,6 +4300,23 @@ void __sched yield(void)
 }
 EXPORT_SYMBOL(yield);
 

kernel/sched/core.c +16 -9

+
+	if (task_running(p_rq, p) || p->state)
+		return false;
+
+	return true;
+}
+
 /**
  * yield_to - yield the current processor to another thread in
  * your thread group, or accelerate that thread toward the

@@ -4323,6 +4340,10 @@ bool __sched yield_to(struct task_struct *p, bool preempt)
 	rq = this_rq();
 
 again:
+	/* optimistic test to avoid taking locks */
+	if (!__yield_to_candidate(curr, p))
+		goto out_irq;
+
 	p_rq = task_rq(p);
 	double_rq_lock(rq, p_rq);
 	while (task_rq(p) != p_rq) {

@@ -4330,14 +4351,9 @@ bool __sched yield_to(struct task_struct *p, bool preempt)
 		goto again;
 	}
 
-	if (!curr->sched_class->yield_to_task)
-		goto out;
-
-	if (curr->sched_class != p->sched_class)
-		goto out;
-
-	if (task_running(p_rq, p) || p->state)
-		goto out;
+	/* validate state, holding p_rq ensures p's state cannot change */
+	if (!__yield_to_candidate(curr, p))
+		goto out_unlock;
 
 	yielded = curr->sched_class->yield_to_task(rq, p, preempt);
 	if (yielded) {

@@ -4350,8 +4366,9 @@ bool __sched yield_to(struct task_struct *p, bool preempt)
 			resched_task(p_rq->curr);
 	}
 
-out:
+out_unlock:
 	double_rq_unlock(rq, p_rq);
+out_irq:
 	local_irq_restore(flags);
 
 	if (yielded)

kernel/sched/core.c void __sched yield(void) · line 4312

Quoted 7 lines

kernel/sched/core.c +7 -0

+static bool __yield_to_candidate(struct task_struct *curr, struct task_struct *p)
+{
+     if (!curr->sched_class->yield_to_task)
+             return false;
+
+     if (curr->sched_class != p->sched_class)
+             return false;

Peter,

Should we also add a check if the runq has a skip buddy (as pointed out by Raghu) and return if the skip buddy is already set.

Quoted 6 lines

kernel/sched/core.c +5 -0

+     if (task_running(p_rq, p) || p->state)
+             return false;
+
+     return true;
+} 

Review bool __sched yield_to(struct task_struct *p,

Quoted 1 line

(quoted diff) +0 -0

@@ -4323,6 +4340,10 @@ bool __sched yield_to(struct task_struct *p,

bool preempt)

Quoted 7 lines

kernel/sched/core.c +4 -0

      rq = this_rq();
 
 again:
+     /* optimistic test to avoid taking locks */
+     if (!__yield_to_candidate(curr, p))
+             goto out_irq;
+

kernel/sched/core.c bool __sched yield_to(struct task_struct *p, bool preempt) · line 4348

Quoted 4 lines

kernel/sched/core.c +0 -0

      p_rq = task_rq(p);
      double_rq_lock(rq, p_rq);

Quoted 11 lines · Srikar Dronamraju

kernel/sched/core.c void __sched yield(void) · line 4312

Quoted 7 lines

kernel/sched/core.c +7 -0

+static bool __yield_to_candidate(struct task_struct *curr, struct task_struct *p)
+{
+     if (!curr->sched_class->yield_to_task)
+             return false;
+
+     if (curr->sched_class != p->sched_class)
+             return false;

Peter,

Quoted 2 lines

Should we also add a check if the runq has a skip buddy (as pointed out by Raghu) and return if the skip buddy is already set.

Oh right, I missed that suggestion.. the performance improvement went from 81% to 139% using this, right?

It might make more sense to keep that separate, outside of this function, since its not a strict prerequisite.

Quoted 8 lines

Quoted 6 lines

kernel/sched/core.c +5 -0

+     if (task_running(p_rq, p) || p->state)
+             return false;
+
+     return true;
+}

Quoted 9 lines

Review bool __sched yield_to(struct task_struct *p,

Quoted 1 line

(quoted diff) +0 -0

@@ -4323,6 +4340,10 @@ bool __sched yield_to(struct task_struct *p,

bool preempt)

Quoted 7 lines

kernel/sched/core.c +4 -0

       rq = this_rq();
 
  again:
+     /* optimistic test to avoid taking locks */
+     if (!__yield_to_candidate(curr, p))
+             goto out_irq;
+

So add something like:

	/* Optimistic, if we 'raced' with another yield_to(), don't bother */
	if (p_rq->cfs_rq->skip)
		goto out_irq;

Quoted 6 lines

kernel/sched/core.c bool __sched yield_to(struct task_struct *p, bool preempt) · line 4348

Quoted 4 lines

kernel/sched/core.c +0 -0

       p_rq = task_rq(p);
       double_rq_lock(rq, p_rq);

But I do have a question on this optimization though,.. Why do we check p_rq->cfs_rq->skip and not rq->cfs_rq->skip ?

That is, I'd like to see this thing explained a little better.

Does it go something like: p_rq is the runqueue of the task we'd like to yield to, rq is our own, they might be the same. If we have a ->skip, there's nothing we can do about it, OTOH p_rq having a ->skip and failing the yield_to() simply means us picking the next VCPU thread, which might be running on an entirely different cpu (rq) and could succeed?

Quoted 11 lines · Srikar Dronamraju

Review

Quoted 7 lines

(quoted diff) +7 -0

+static bool __yield_to_candidate(struct task_struct *curr, struct task_struct *p)
+{
+     if (!curr->sched_class->yield_to_task)
+             return false;
+
+     if (curr->sched_class != p->sched_class)
+             return false;

Peter,

Quoted 2 lines

Should we also add a check if the runq has a skip buddy (as pointed out by Raghu) and return if the skip buddy is already set.

Oh right, I missed that suggestion.. the performance improvement went from 81% to 139% using this, right?

It might make more sense to keep that separate, outside of this function, since its not a strict prerequisite.

Quoted 8 lines

Quoted 6 lines

(quoted diff) +5 -0

+     if (task_running(p_rq, p) || p->state)
+             return false;
+
+     return true;
+} 

Quoted 9 lines

Review bool __sched yield_to(struct task_struct *p,

Quoted 1 line

(quoted diff) +0 -0

@@ -4323,6 +4340,10 @@ bool __sched yield_to(struct task_struct *p,

bool preempt)

Quoted 7 lines

(quoted diff) +4 -0

      rq = this_rq();
 
 again:
+     /* optimistic test to avoid taking locks */
+     if (!__yield_to_candidate(curr, p))
+             goto out_irq;
+

So add something like:

	/* Optimistic, if we 'raced' with another yield_to(), don't bother */
	if (p_rq->cfs_rq->skip)
		goto out_irq;

Quoted 6 lines

Review bool __sched yield_to(struct task_struct *p, · line 4348

Quoted 4 lines

(quoted diff) +0 -0

      p_rq = task_rq(p);
      double_rq_lock(rq, p_rq);

But I do have a question on this optimization though,.. Why do we check p_rq->cfs_rq->skip and not rq->cfs_rq->skip ?

That is, I'd like to see this thing explained a little better.

Does it go something like: p_rq is the runqueue of the task we'd like to yield to, rq is our own, they might be the same. If we have a ->skip, there's nothing we can do about it, OTOH p_rq having a ->skip and failing the yield_to() simply means us picking the next VCPU thread, which might be running on an entirely different cpu (rq) and could succeed?

ple on: 2552 +/- .70%
ple on: w/fixv1: 4621 +/- 2.12% (81% improvement)
ple on: w/fixv2: 6115 (139% improvement)

kernel/sched/core.c bool __sched yield_to(struct task_struct *p, bool preempt) · line 4874

Quoted 6 lines · Andrew Theurer

kernel/sched/core.c +6 -0

+       /*
+        * if the target task is not running, then only yield if the
+        * current task is in guest mode
+        */
+       if (!(p_rq->curr->flags & PF_VCPU))
+               goto out_irq;

This would make yield_to() only ever work on KVM, not that I mind this too much, its a horrid thing and making it less useful for (ab)use is a good thing, still this probably wants mention somewhere :-)

Quoted 53 lines · Peter Zijlstra

Quoted 11 lines · Srikar Dronamraju

kernel/sched/core.c void __sched yield(void) · line 4832

Quoted 7 lines

kernel/sched/core.c +7 -0

+static bool __yield_to_candidate(struct task_struct *curr, struct task_struct *p)
+{
+     if (!curr->sched_class->yield_to_task)
+             return false;
+
+     if (curr->sched_class != p->sched_class)
+             return false;

Peter,

Quoted 2 lines

Should we also add a check if the runq has a skip buddy (as pointed out by Raghu) and return if the skip buddy is already set.

Oh right, I missed that suggestion.. the performance improvement went from 81% to 139% using this, right?

It might make more sense to keep that separate, outside of this function, since its not a strict prerequisite.

Quoted 8 lines

Quoted 6 lines

kernel/sched/core.c +5 -0

+     if (task_running(p_rq, p) || p->state)
+             return false;
+
+     return true;
+}

Quoted 9 lines

Review bool __sched yield_to(struct task_struct *p,

Quoted 1 line

(quoted diff) +0 -0

@@ -4323,6 +4340,10 @@ bool __sched yield_to(struct task_struct *p,

bool preempt)

Quoted 7 lines

kernel/sched/core.c +4 -0

       rq = this_rq();
 
  again:
+     /* optimistic test to avoid taking locks */
+     if (!__yield_to_candidate(curr, p))
+             goto out_irq;
+

So add something like:

	/* Optimistic, if we 'raced' with another yield_to(), don't bother */
	if (p_rq->cfs_rq->skip)
		goto out_irq;

Quoted 6 lines

Review bool __sched yield_to(struct task_struct *p, · line 4348

Quoted 4 lines

(quoted diff) +0 -0

       p_rq = task_rq(p);
       double_rq_lock(rq, p_rq);

But I do have a question on this optimization though,.. Why do we check p_rq->cfs_rq->skip and not rq->cfs_rq->skip ?

Quoted 8 lines

That is, I'd like to see this thing explained a little better.

Does it go something like: p_rq is the runqueue of the task we'd like to yield to, rq is our own, they might be the same. If we have a ->skip, there's nothing we can do about it, OTOH p_rq having a ->skip and failing the yield_to() simply means us picking the next VCPU thread, which might be running on an entirely different cpu (rq) and could succeed?

Here's two new versions, both include a __yield_to_candidate(): "v3" uses the check for p_rq->curr in guest mode, and "v4" uses the cfs_rq skip check. Raghu, I am not sure if this is exactly what you want implemented in v4.

Quoted 63 lines · Andrew Theurer

Quoted 53 lines · Peter Zijlstra

Quoted 11 lines · Srikar Dronamraju

kernel/sched/core.c void __sched yield(void) · line 4832

Quoted 7 lines

kernel/sched/core.c +7 -0

+static bool __yield_to_candidate(struct task_struct *curr, struct task_struct *p)
+{
+     if (!curr->sched_class->yield_to_task)
+             return false;
+
+     if (curr->sched_class != p->sched_class)
+             return false;

Peter,

Quoted 2 lines

Should we also add a check if the runq has a skip buddy (as pointed out by Raghu) and return if the skip buddy is already set.

Oh right, I missed that suggestion.. the performance improvement went from 81% to 139% using this, right?

It might make more sense to keep that separate, outside of this function, since its not a strict prerequisite.

Quoted 8 lines

Quoted 6 lines

kernel/sched/core.c +5 -0

+     if (task_running(p_rq, p) || p->state)
+             return false;
+
+     return true;
+}

Quoted 9 lines

Review bool __sched yield_to(struct task_struct *p,

Quoted 1 line

(quoted diff) +0 -0

@@ -4323,6 +4340,10 @@ bool __sched yield_to(struct task_struct *p,

bool preempt)

Quoted 7 lines

kernel/sched/core.c +4 -0

       rq = this_rq();
 
  again:
+     /* optimistic test to avoid taking locks */
+     if (!__yield_to_candidate(curr, p))
+             goto out_irq;
+

So add something like:

	/* Optimistic, if we 'raced' with another yield_to(), don't bother */
	if (p_rq->cfs_rq->skip)
		goto out_irq;

Quoted 6 lines

Review bool __sched yield_to(struct task_struct *p, · line 4348

Quoted 4 lines

(quoted diff) +0 -0

       p_rq = task_rq(p);
       double_rq_lock(rq, p_rq);

But I do have a question on this optimization though,.. Why do we check p_rq->cfs_rq->skip and not rq->cfs_rq->skip ?

Quoted 8 lines

That is, I'd like to see this thing explained a little better.

Does it go something like: p_rq is the runqueue of the task we'd like to yield to, rq is our own, they might be the same. If we have a ->skip, there's nothing we can do about it, OTOH p_rq having a ->skip and failing the yield_to() simply means us picking the next VCPU thread, which might be running on an entirely different cpu (rq) and could succeed?

Quoted 5 lines

Here's two new versions, both include a __yield_to_candidate(): "v3" uses the check for p_rq->curr in guest mode, and "v4" uses the cfs_rq skip check. Raghu, I am not sure if this is exactly what you want implemented in v4.

Andrew, Yes that is what I had. I think there was a mis-understanding. My intention was to if there is a directed_yield happened in runqueue (say rqA), do not bother to directed yield to that. But unfortunately as PeterZ pointed that would have resulted in setting next buddy of a different run queue than rqA.
So we can drop this "skip" idea. Pondering more over what to do? can we use next buddy itself ... thinking..

Quoted 63 lines · Andrew Theurer

Quoted 53 lines · Peter Zijlstra

Quoted 11 lines · Srikar Dronamraju

kernel/sched/core.c void __sched yield(void) · line 4832

Quoted 7 lines

kernel/sched/core.c +7 -0

+static bool __yield_to_candidate(struct task_struct *curr, struct task_struct *p)
+{
+     if (!curr->sched_class->yield_to_task)
+             return false;
+
+     if (curr->sched_class != p->sched_class)
+             return false;

Peter,

Quoted 2 lines

Should we also add a check if the runq has a skip buddy (as pointed out by Raghu) and return if the skip buddy is already set.

Oh right, I missed that suggestion.. the performance improvement went from 81% to 139% using this, right?

It might make more sense to keep that separate, outside of this function, since its not a strict prerequisite.

Quoted 8 lines

Quoted 6 lines

kernel/sched/core.c +5 -0

+     if (task_running(p_rq, p) || p->state)
+             return false;
+
+     return true;
+}

Quoted 9 lines

Review bool __sched yield_to(struct task_struct *p,

Quoted 1 line

(quoted diff) +0 -0

@@ -4323,6 +4340,10 @@ bool __sched yield_to(struct task_struct *p,

bool preempt)

Quoted 7 lines

kernel/sched/core.c +4 -0

       rq = this_rq();
 
  again:
+     /* optimistic test to avoid taking locks */
+     if (!__yield_to_candidate(curr, p))
+             goto out_irq;
+

So add something like:

	/* Optimistic, if we 'raced' with another yield_to(), don't bother */
	if (p_rq->cfs_rq->skip)
		goto out_irq;

Quoted 6 lines

Review bool __sched yield_to(struct task_struct *p, · line 4348

Quoted 4 lines

(quoted diff) +0 -0

       p_rq = task_rq(p);
       double_rq_lock(rq, p_rq);

But I do have a question on this optimization though,.. Why do we check p_rq->cfs_rq->skip and not rq->cfs_rq->skip ?

Quoted 8 lines

That is, I'd like to see this thing explained a little better.

Does it go something like: p_rq is the runqueue of the task we'd like to yield to, rq is our own, they might be the same. If we have a ->skip, there's nothing we can do about it, OTOH p_rq having a ->skip and failing the yield_to() simply means us picking the next VCPU thread, which might be running on an entirely different cpu (rq) and could succeed?

Quoted 5 lines

Here's two new versions, both include a __yield_to_candidate(): "v3" uses the check for p_rq->curr in guest mode, and "v4" uses the cfs_rq skip check. Raghu, I am not sure if this is exactly what you want implemented in v4.

Andrew, Yes that is what I had. I think there was a mis-understanding. My intention was to if there is a directed_yield happened in runqueue (say rqA), do not bother to directed yield to that. But unfortunately as PeterZ pointed that would have resulted in setting next buddy of a different run queue than rqA.
So we can drop this "skip" idea. Pondering more over what to do? can we use next buddy itself ... thinking..

Quoted 70 lines · Raghavendra K T

Quoted 63 lines · Andrew Theurer

Quoted 53 lines · Peter Zijlstra

Quoted 11 lines · Srikar Dronamraju

Review

Quoted 7 lines

(quoted diff) +7 -0

+static bool __yield_to_candidate(struct task_struct *curr, struct task_struct *p)
+{
+     if (!curr->sched_class->yield_to_task)
+             return false;
+
+     if (curr->sched_class != p->sched_class)
+             return false;

Peter,

Quoted 2 lines

Should we also add a check if the runq has a skip buddy (as pointed out by Raghu) and return if the skip buddy is already set.

Oh right, I missed that suggestion.. the performance improvement went from 81% to 139% using this, right?

It might make more sense to keep that separate, outside of this function, since its not a strict prerequisite.

Quoted 8 lines

Quoted 6 lines

(quoted diff) +5 -0

+     if (task_running(p_rq, p) || p->state)
+             return false;
+
+     return true;
+}

Quoted 9 lines

Review bool __sched yield_to(struct task_struct *p,

Quoted 1 line

(quoted diff) +0 -0

@@ -4323,6 +4340,10 @@ bool __sched yield_to(struct task_struct *p,

bool preempt)

Quoted 7 lines

(quoted diff) +4 -0

       rq = this_rq();
 
  again:
+     /* optimistic test to avoid taking locks */
+     if (!__yield_to_candidate(curr, p))
+             goto out_irq;
+

So add something like:

	/* Optimistic, if we 'raced' with another yield_to(), don't bother */
	if (p_rq->cfs_rq->skip)
		goto out_irq;

Quoted 6 lines

Review bool __sched yield_to(struct task_struct *p, · line 4348

Quoted 4 lines

(quoted diff) +0 -0

       p_rq = task_rq(p);
       double_rq_lock(rq, p_rq);

But I do have a question on this optimization though,.. Why do we check p_rq->cfs_rq->skip and not rq->cfs_rq->skip ?

Quoted 8 lines

That is, I'd like to see this thing explained a little better.

Does it go something like: p_rq is the runqueue of the task we'd like to yield to, rq is our own, they might be the same. If we have a ->skip, there's nothing we can do about it, OTOH p_rq having a ->skip and failing the yield_to() simply means us picking the next VCPU thread, which might be running on an entirely different cpu (rq) and could succeed?

Quoted 5 lines

Here's two new versions, both include a __yield_to_candidate(): "v3" uses the check for p_rq->curr in guest mode, and "v4" uses the cfs_rq skip check. Raghu, I am not sure if this is exactly what you want implemented in v4.

Quoted 7 lines

Andrew, Yes that is what I had. I think there was a mis-understanding. My intention was to if there is a directed_yield happened in runqueue (say rqA), do not bother to directed yield to that. But unfortunately as PeterZ pointed that would have resulted in setting next buddy of a different run queue than rqA.
So we can drop this "skip" idea. Pondering more over what to do? can we use next buddy itself ... thinking..

As I mentioned earlier today, I did not have your changes from kvm.git tree when I tested my changes. Here are your changes and my changes compared:

throughput in MB/sec

kvm_vcpu_on_spin changes: 4636 +/- 15.74%
yield_to changes: 4515 +/- 12.73%

I would be inclined to stick with your changes which are kept in kvm code. I did try both combined, and did not get good results:

both changes: 4074 +/- 19.12%

So, having both is probably not a good idea. However, I feel like there's more work to be done. With no over-commit (10 VMs), total throughput is 23427 +/- 2.76%. A 2x over-commit will no doubt have some overhead, but a reduction to ~4500 is still terrible. By contrast, 8-way VMs with 2x over-commit have a total throughput roughly 10% less than 8-way VMs with no overcommit (20 vs 10 8-way VMs on 80 cpu-thread host). We still have what appears to be scalability problems, but now it's not so much in runqueue locks for yield_to(), but now get_pid_task():

Quoted 93 lines · Andrew Theurer

Quoted 70 lines · Raghavendra K T

Quoted 63 lines · Andrew Theurer

Quoted 53 lines · Peter Zijlstra

Quoted 11 lines · Srikar Dronamraju

kernel/sched/core.c void __sched yield(void) · line 4833

Quoted 7 lines

kernel/sched/core.c +7 -0

+static bool __yield_to_candidate(struct task_struct *curr, struct task_struct *p)
+{
+     if (!curr->sched_class->yield_to_task)
+             return false;
+
+     if (curr->sched_class != p->sched_class)
+             return false;

Peter,

Quoted 2 lines

Should we also add a check if the runq has a skip buddy (as pointed out by Raghu) and return if the skip buddy is already set.

Oh right, I missed that suggestion.. the performance improvement went from 81% to 139% using this, right?

It might make more sense to keep that separate, outside of this function, since its not a strict prerequisite.

Quoted 8 lines

Quoted 6 lines

kernel/sched/core.c +5 -0

+     if (task_running(p_rq, p) || p->state)
+             return false;
+
+     return true;
+}

Quoted 9 lines

Review bool __sched yield_to(struct task_struct *p,

Quoted 1 line

(quoted diff) +0 -0

@@ -4323,6 +4340,10 @@ bool __sched yield_to(struct task_struct *p,

bool preempt)

Quoted 7 lines

kernel/sched/core.c +4 -0

       rq = this_rq();
 
  again:
+     /* optimistic test to avoid taking locks */
+     if (!__yield_to_candidate(curr, p))
+             goto out_irq;
+

So add something like:

	/* Optimistic, if we 'raced' with another yield_to(), don't bother */
	if (p_rq->cfs_rq->skip)
		goto out_irq;

Quoted 6 lines

kernel/sched/core.c bool __sched yield_to(struct task_struct *p, bool preempt) · line 4874

Quoted 4 lines

kernel/sched/core.c +0 -0

       p_rq = task_rq(p);
       double_rq_lock(rq, p_rq);

But I do have a question on this optimization though,.. Why do we check p_rq->cfs_rq->skip and not rq->cfs_rq->skip ?

Quoted 8 lines

That is, I'd like to see this thing explained a little better.

Does it go something like: p_rq is the runqueue of the task we'd like to yield to, rq is our own, they might be the same. If we have a ->skip, there's nothing we can do about it, OTOH p_rq having a ->skip and failing the yield_to() simply means us picking the next VCPU thread, which might be running on an entirely different cpu (rq) and could succeed?

Quoted 5 lines

Here's two new versions, both include a __yield_to_candidate(): "v3" uses the check for p_rq->curr in guest mode, and "v4" uses the cfs_rq skip check. Raghu, I am not sure if this is exactly what you want implemented in v4.

Quoted 7 lines

Andrew, Yes that is what I had. I think there was a mis-understanding. My intention was to if there is a directed_yield happened in runqueue (say rqA), do not bother to directed yield to that. But unfortunately as PeterZ pointed that would have resulted in setting next buddy of a different run queue than rqA.
So we can drop this "skip" idea. Pondering more over what to do? can we use next buddy itself ... thinking..

As I mentioned earlier today, I did not have your changes from kvm.git tree when I tested my changes. Here are your changes and my changes compared:

throughput in MB/sec

kvm_vcpu_on_spin changes: 4636 +/- 15.74%
yield_to changes: 4515 +/- 12.73%

I would be inclined to stick with your changes which are kept in kvm code. I did try both combined, and did not get good results:

both changes: 4074 +/- 19.12%

Quoted 10 lines

So, having both is probably not a good idea. However, I feel like there's more work to be done. With no over-commit (10 VMs), total throughput is 23427 +/- 2.76%. A 2x over-commit will no doubt have some overhead, but a reduction to ~4500 is still terrible. By contrast, 8-way VMs with 2x over-commit have a total throughput roughly 10% less than 8-way VMs with no overcommit (20 vs 10 8-way VMs on 80 cpu-thread host). We still have what appears to be scalability problems, but now it's not so much in runqueue locks for yield_to(), but now get_pid_task():

Hi Andrew,
IMHO, reducing the double runqueue lock overhead is a good idea, and may be we see the benefits when we increase the overcommit further.

The explaination for not seeing good benefit on top of PLE handler optimization patch is because we filter the yield_to candidates, and hence resulting in less contention for double runqueue lock. and extra code overhead during genuine yield_to might have resulted in some degradation in the case you tested.

However, did you use cfs.next also?. I hope it helps, when we combine.

Here is the result that is showing positive benefit.
I experimented on a 32 core (no HT) PLE machine with 32 vcpu guest(s).

+-----------+-----------+-----------+------------+-----------+
kernbench time in sec, lower is better

+-----------+-----------+-----------+------------+-----------+
       base      stddev     patched     stddev      %improve
+-----------+-----------+-----------+------------+-----------+
1x    44.3880     1.8699    40.8180     1.9173	   8.04271
2x    96.7580     4.2787    93.4188     3.5150	   3.45108
+-----------+-----------+-----------+------------+-----------+

+-----------+-----------+-----------+------------+-----------+
ebizzy record/sec higher is better

+-----------+-----------+-----------+------------+-----------+
       base      stddev     patched     stddev      %improve
+-----------+-----------+-----------+------------+-----------+
1x  2374.1250    50.9718   3816.2500    54.0681	  60.74343
2x  2536.2500    93.0403   2789.3750   204.7897	   9.98029
+-----------+-----------+-----------+------------+-----------+

Below is the patch which combine suggestions of peterZ on your original approach with cfs.next (already posted by Srikar in the other thread)

----8<----

kernel/sched/core.c +32 -9

index fbf1fd0..8551f57 100644
@@ -4820,6 +4820,24 @@ void __sched yield(void)
 }
 EXPORT_SYMBOL(yield);
 
+/*
+ * Tests preconditions required for sched_class::yield_to().
+ */
+static bool __yield_to_candidate(struct task_struct *curr, struct task_struct *p,
+					 struct rq *p_rq)
+{
+	if (!curr->sched_class->yield_to_task)
+		return false;
+
+	if (curr->sched_class != p->sched_class)
+		return false;
+
+	if (task_running(p_rq, p) || p->state)
+		return false;
+
+	return true;
+}
+
 /**
  * yield_to - yield the current processor to another thread in
  * your thread group, or accelerate that thread toward the

@@ -4844,20 +4862,24 @@ bool __sched yield_to(struct task_struct *p, bool preempt)
 
 again:
 	p_rq = task_rq(p);
+
+	/* optimistic test to avoid taking locks */
+	if (!__yield_to_candidate(curr, p, p_rq))
+		goto out_irq;
+
+	/* if next buddy is set, assume yield is in progress */
+	if (p_rq->cfs.next)
+		goto out_irq;
+
 	double_rq_lock(rq, p_rq);
 	while (task_rq(p) != p_rq) {
 		double_rq_unlock(rq, p_rq);
 		goto again;
 	}
 
-	if (!curr->sched_class->yield_to_task)
-		goto out;
-
-	if (curr->sched_class != p->sched_class)
-		goto out;
-
-	if (task_running(p_rq, p) || p->state)
-		goto out;
+	/* validate state, holding p_rq ensures p's state cannot change */
+	if (!__yield_to_candidate(curr, p, p_rq))
+		goto out_unlock;
 
 	yielded = curr->sched_class->yield_to_task(rq, p, preempt);
 	if (yielded) {

@@ -4877,8 +4899,9 @@ again:
 		rq->skip_clock_update = 0;
 	}
 
-out:
+out_unlock:
 	double_rq_unlock(rq, p_rq);
+out_irq:
 	local_irq_restore(flags);
 
 	if (yielded)

Quoted 141 lines · Raghavendra K T

Quoted 93 lines · Andrew Theurer

Quoted 70 lines · Raghavendra K T

Quoted 63 lines · Andrew Theurer

Quoted 53 lines · Peter Zijlstra

Quoted 11 lines · Srikar Dronamraju

Review

Quoted 7 lines

(quoted diff) +7 -0

+static bool __yield_to_candidate(struct task_struct *curr, struct task_struct *p)
+{
+     if (!curr->sched_class->yield_to_task)
+             return false;
+
+     if (curr->sched_class != p->sched_class)
+             return false;

Peter,

Quoted 2 lines

Should we also add a check if the runq has a skip buddy (as pointed out by Raghu) and return if the skip buddy is already set.

Oh right, I missed that suggestion.. the performance improvement went from 81% to 139% using this, right?

It might make more sense to keep that separate, outside of this function, since its not a strict prerequisite.

Quoted 8 lines

Quoted 6 lines

(quoted diff) +5 -0

+     if (task_running(p_rq, p) || p->state)
+             return false;
+
+     return true;
+}

Quoted 9 lines

Review bool __sched yield_to(struct task_struct *p,

Quoted 1 line

(quoted diff) +0 -0

@@ -4323,6 +4340,10 @@ bool __sched yield_to(struct task_struct *p,

bool preempt)

Quoted 7 lines

(quoted diff) +4 -0

       rq = this_rq();
 
  again:
+     /* optimistic test to avoid taking locks */
+     if (!__yield_to_candidate(curr, p))
+             goto out_irq;
+

So add something like:

	/* Optimistic, if we 'raced' with another yield_to(), don't bother */
	if (p_rq->cfs_rq->skip)
		goto out_irq;

Quoted 6 lines

Review bool __sched yield_to(struct task_struct *p, · line 4348

Quoted 4 lines

(quoted diff) +0 -0

       p_rq = task_rq(p);
       double_rq_lock(rq, p_rq);

But I do have a question on this optimization though,.. Why do we check p_rq->cfs_rq->skip and not rq->cfs_rq->skip ?

Quoted 8 lines

That is, I'd like to see this thing explained a little better.

Does it go something like: p_rq is the runqueue of the task we'd like to yield to, rq is our own, they might be the same. If we have a ->skip, there's nothing we can do about it, OTOH p_rq having a ->skip and failing the yield_to() simply means us picking the next VCPU thread, which might be running on an entirely different cpu (rq) and could succeed?

Quoted 5 lines

Here's two new versions, both include a __yield_to_candidate(): "v3" uses the check for p_rq->curr in guest mode, and "v4" uses the cfs_rq skip check. Raghu, I am not sure if this is exactly what you want implemented in v4.

Quoted 7 lines

Andrew, Yes that is what I had. I think there was a mis-understanding. My intention was to if there is a directed_yield happened in runqueue (say rqA), do not bother to directed yield to that. But unfortunately as PeterZ pointed that would have resulted in setting next buddy of a different run queue than rqA.
So we can drop this "skip" idea. Pondering more over what to do? can we use next buddy itself ... thinking..

As I mentioned earlier today, I did not have your changes from kvm.git tree when I tested my changes. Here are your changes and my changes compared:

throughput in MB/sec

kvm_vcpu_on_spin changes: 4636 +/- 15.74%
yield_to changes: 4515 +/- 12.73%

I would be inclined to stick with your changes which are kept in kvm code. I did try both combined, and did not get good results:

both changes: 4074 +/- 19.12%

Quoted 10 lines

So, having both is probably not a good idea. However, I feel like there's more work to be done. With no over-commit (10 VMs), total throughput is 23427 +/- 2.76%. A 2x over-commit will no doubt have some overhead, but a reduction to ~4500 is still terrible. By contrast, 8-way VMs with 2x over-commit have a total throughput roughly 10% less than 8-way VMs with no overcommit (20 vs 10 8-way VMs on 80 cpu-thread host). We still have what appears to be scalability problems, but now it's not so much in runqueue locks for yield_to(), but now get_pid_task():

Hi Andrew,
IMHO, reducing the double runqueue lock overhead is a good idea, and may be we see the benefits when we increase the overcommit further.

The explaination for not seeing good benefit on top of PLE handler optimization patch is because we filter the yield_to candidates, and hence resulting in less contention for double runqueue lock. and extra code overhead during genuine yield_to might have resulted in some degradation in the case you tested.

However, did you use cfs.next also?. I hope it helps, when we combine.

Here is the result that is showing positive benefit.
I experimented on a 32 core (no HT) PLE machine with 32 vcpu guest(s).

+-----------+-----------+-----------+------------+-----------+
kernbench time in sec, lower is better

+-----------+-----------+-----------+------------+-----------+
       base      stddev     patched     stddev      %improve
+-----------+-----------+-----------+------------+-----------+
1x    44.3880     1.8699    40.8180     1.9173	   8.04271
2x    96.7580     4.2787    93.4188     3.5150	   3.45108
+-----------+-----------+-----------+------------+-----------+

+-----------+-----------+-----------+------------+-----------+
ebizzy record/sec higher is better

+-----------+-----------+-----------+------------+-----------+
       base      stddev     patched     stddev      %improve
+-----------+-----------+-----------+------------+-----------+
1x  2374.1250    50.9718   3816.2500    54.0681	  60.74343
2x  2536.2500    93.0403   2789.3750   204.7897	   9.98029
+-----------+-----------+-----------+------------+-----------+

Quoted 3 lines

Below is the patch which combine suggestions of peterZ on your original approach with cfs.next (already posted by Srikar in the other thread)

I did get a chance to run with the below patch and your changes in kvm.git, but the results were not too different:

Dbench, 10 x 16-way VMs on 80-way host:

kvm_vcpu_on_spin changes: 4636 +/- 15.74%
yield_to changes: 4515 +/- 12.73%
both changes from above: 4074 +/- 19.12%
...plus cfs.next check: 4418 +/- 16.97%

Still hovering around 4500 MB/sec

The concern I have is that even though we have gone through changes to help reduce the candidate vcpus we yield to, we still have a very poor idea of which vcpu really needs to run. The result is high cpu usage in the get_pid_task and still some contention in the double runqueue lock. To make this scalable, we either need to significantly reduce the occurrence of the lock-holder preemption, or do a much better job of knowing which vcpu needs to run (and not unnecessarily yielding to vcpus which do not need to run).

On reducing the occurrence: The worst case for lock-holder preemption is having vcpus of same VM on the same runqueue. This guarantees the situation of 1 vcpu running while another [of the same VM] is not. To prove the point, I ran the same test, but with vcpus restricted to a range of host cpus, such that any single VM's vcpus can never be on the same runqueue. In this case, all 10 VMs' vcpu-0's are on host cpus 0-4, vcpu-1's are on host cpus 5-9, and so on. Here is the result:

kvm_cpu_spin, and all
yield_to changes, plus
restricted vcpu placement: 8823 +/- 3.20% much, much better

On picking a better vcpu to yield to: I really hesitate to rely on paravirt hint [telling us which vcpu is holding a lock], but I am not sure how else to reduce the candidate vcpus to yield to. I suspect we are yielding to way more vcpus than are prempted lock-holders, and that IMO is just work accomplishing nothing. Trying to think of way to further reduce candidate vcpus....

Quoted 66 lines

----8<----

kernel/sched/core.c +30 -8

index fbf1fd0..8551f57 100644
@@ -4820,6 +4820,24 @@ void __sched yield(void)
 }
 EXPORT_SYMBOL(yield);
 
+/*
+ * Tests preconditions required for sched_class::yield_to().
+ */
+static bool __yield_to_candidate(struct task_struct *curr, struct task_struct *p,
+					 struct rq *p_rq)
+{
+	if (!curr->sched_class->yield_to_task)
+		return false;
+
+	if (curr->sched_class != p->sched_class)
+		return false;
+
+	if (task_running(p_rq, p) || p->state)
+		return false;
+
+	return true;
+}
+
 /**
  * yield_to - yield the current processor to another thread in
  * your thread group, or accelerate that thread toward the

@@ -4844,20 +4862,24 @@ bool __sched yield_to(struct task_struct *p, bool preempt)
 
 again:
 	p_rq = task_rq(p);
+
+	/* optimistic test to avoid taking locks */
+	if (!__yield_to_candidate(curr, p, p_rq))
+		goto out_irq;
+
+	/* if next buddy is set, assume yield is in progress */
+	if (p_rq->cfs.next)
+		goto out_irq;
+
 	double_rq_lock(rq, p_rq);
 	while (task_rq(p) != p_rq) {
 		double_rq_unlock(rq, p_rq);
 		goto again;
 	}
 
-	if (!curr->sched_class->yield_to_task)
-		goto out;
-
-	if (curr->sched_class != p->sched_class)
-		goto out;
-
-	if (task_running(p_rq, p) || p->state)
-		goto out;
+	/* validate state, holding p_rq ensures p's state cannot change */
+	if (!__yield_to_candidate(curr, p, p_rq))
+		goto out_unlock;
 
 	yielded = curr->sched_class->yield_to_task(rq, p, preempt);
 	if (yielded) {

kernel/sched/core.c again: · line 4907

Quoted 10 lines

kernel/sched/core.c +2 -1

@@ -4877,8 +4899,9 @@ again:
 		rq->skip_clock_update = 0;
 	}
 
-out:
+out_unlock:
 	double_rq_unlock(rq, p_rq);
+out_irq:
 	local_irq_restore(flags);
 
 	if (yielded)

--
To unsubscribe from this list: send the line "unsubscribe kvm" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

Quoted 3 lines · Andrew Theurer

Quoted 2 lines · Raghavendra K T

* Andrew Theurer<[email protected]> [2012-09-11 13:27:41]:

Quoted 8 lines

On picking a better vcpu to yield to: I really hesitate to rely on paravirt hint [telling us which vcpu is holding a lock], but I am not sure how else to reduce the candidate vcpus to yield to. I suspect we are yielding to way more vcpus than are prempted lock-holders, and that IMO is just work accomplishing nothing. Trying to think of way to further reduce candidate vcpus....

wrt to yielding to vcpus for the same cpu, I recently noticed that there's a bug in yield_to_task_fair. yield_task_fair() calls clear_buddies(), so if we're yielding to a task that has been running on the same cpu that we're currently running on, and thus is also on the current cfs runqueue, then our 'who to pick next' hint is getting cleared right after we set it.

I had hoped that the patch below would show a general improvement in the vpu overcommit performance, however the results were variable - no worse, no better. Based on your results above showing good improvement from interleaving vcpus across the cpus, then that means there was a decent percent of these types of yields going on. So since the patch didn't change much that indicates that the next hinting isn't generally taken too seriously by the scheduler. Anyway, the patch should correct the code per its design, and testing shows that it didn't make anything worse, so I'll post it soon. Also, in order to try and improve how far set-next can jump ahead in the queue, I tested a kernel with group scheduling compiled out (libvirt uses cgroups and I'm not sure autogroups may affect things). I did get slight improvement with that, but nothing to write home to mom about.

kernel/sched/fair.c +1 -0

index c219bf8..7d8a21d 100644
@@ -3037,11 +3037,12 @@ static bool yield_to_task_fair(struct rq *rq, struct task_struct *p, bool preemp
  	if (!se->on_rq || throttled_hierarchy(cfs_rq_of(se)))
  		return false;
 
+	/* We're yielding, so tell the scheduler we don't want to be picked */

Quoted 4 lines · Andrew Jones

Quoted 3 lines · Andrew Theurer

Quoted 2 lines · Raghavendra K T

* Andrew Theurer<[email protected]> [2012-09-11 13:27:41]:

[...]

Quoted 44 lines

Quoted 8 lines

On picking a better vcpu to yield to: I really hesitate to rely on paravirt hint [telling us which vcpu is holding a lock], but I am not sure how else to reduce the candidate vcpus to yield to. I suspect we are yielding to way more vcpus than are prempted lock-holders, and that IMO is just work accomplishing nothing. Trying to think of way to further reduce candidate vcpus....

wrt to yielding to vcpus for the same cpu, I recently noticed that there's a bug in yield_to_task_fair. yield_task_fair() calls clear_buddies(), so if we're yielding to a task that has been running on the same cpu that we're currently running on, and thus is also on the current cfs runqueue, then our 'who to pick next' hint is getting cleared right after we set it.

I had hoped that the patch below would show a general improvement in the vpu overcommit performance, however the results were variable - no worse, no better. Based on your results above showing good improvement from interleaving vcpus across the cpus, then that means there was a decent percent of these types of yields going on. So since the patch didn't change much that indicates that the next hinting isn't generally taken too seriously by the scheduler. Anyway, the patch should correct the code per its design, and testing shows that it didn't make anything worse, so I'll post it soon. Also, in order to try and improve how far set-next can jump ahead in the queue, I tested a kernel with group scheduling compiled out (libvirt uses cgroups and I'm not sure autogroups may affect things). I did get slight improvement with that, but nothing to write home to mom about.

kernel/sched/fair.c +3 -0

index c219bf8..7d8a21d 100644
@@ -3037,11 +3037,12 @@ static bool yield_to_task_fair(struct rq *rq, struct task_struct *p, bool preemp
 	if (!se->on_rq || throttled_hierarchy(cfs_rq_of(se)))
 		return false;
 
+	/* We're yielding, so tell the scheduler we don't want to be picked */
+	yield_task_fair(rq);
+
 	/* Tell the scheduler that we'd really like pse to run next. */
 	set_next_buddy(se);
 

kernel/sched/fair.c static bool yield_to_task_fair(struct rq *rq, struct task_struct *p, bool preemp · line 3048

Quoted 5 lines

kernel/sched/fair.c +0 -2

-	yield_task_fair(rq);
-
 	return true;
 }
 

Hi Drew, Agree with your fix and tested the patch too.. results are pretty much same. puzzled why so.

thinking ... may be we hit this when #vcpu (of a VM) > #pcpu? (pigeonhole principle ;)).

The concern I have is that even though we have gone through changes to help reduce the candidate vcpus we yield to, we still have a very poor idea of which vcpu really needs to run. The result is high cpu usage in the get_pid_task and still some contention in the double runqueue lock. To make this scalable, we either need to significantly reduce the occurrence of the lock-holder preemption, or do a much better job of knowing which vcpu needs to run (and not unnecessarily yielding to vcpus which do not need to run).

On reducing the occurrence: The worst case for lock-holder preemption is having vcpus of same VM on the same runqueue. This guarantees the situation of 1 vcpu running while another [of the same VM] is not. To prove the point, I ran the same test, but with vcpus restricted to a range of host cpus, such that any single VM's vcpus can never be on the same runqueue. In this case, all 10 VMs' vcpu-0's are on host cpus 0-4, vcpu-1's are on host cpus 5-9, and so on. Here is the result:

kvm_cpu_spin, and all
yield_to changes, plus
restricted vcpu placement: 8823 +/- 3.20% much, much better

On picking a better vcpu to yield to: I really hesitate to rely on paravirt hint [telling us which vcpu is holding a lock], but I am not sure how else to reduce the candidate vcpus to yield to. I suspect we are yielding to way more vcpus than are prempted lock-holders, and that IMO is just work accomplishing nothing. Trying to think of way to further reduce candidate vcpus....

Quoted 8 lines

The concern I have is that even though we have gone through changes to help reduce the candidate vcpus we yield to, we still have a very poor idea of which vcpu really needs to run. The result is high cpu usage in the get_pid_task and still some contention in the double runqueue lock. To make this scalable, we either need to significantly reduce the occurrence of the lock-holder preemption, or do a much better job of knowing which vcpu needs to run (and not unnecessarily yielding to vcpus which do not need to run).

The patches that Raghavendra has been posting do accomplish that.

Quoted 13 lines

On reducing the occurrence: The worst case for lock-holder preemption is having vcpus of same VM on the same runqueue. This guarantees the situation of 1 vcpu running while another [of the same VM] is not. To prove the point, I ran the same test, but with vcpus restricted to a range of host cpus, such that any single VM's vcpus can never be on the same runqueue. In this case, all 10 VMs' vcpu-0's are on host cpus 0-4, vcpu-1's are on host cpus 5-9, and so on. Here is the result:

kvm_cpu_spin, and all
yield_to changes, plus
restricted vcpu placement: 8823 +/- 3.20% much, much better

Quoted 6 lines

On picking a better vcpu to yield to: I really hesitate to rely on paravirt hint [telling us which vcpu is holding a lock], but I am not sure how else to reduce the candidate vcpus to yield to. I suspect we are yielding to way more vcpus than are prempted lock-holders, and that IMO is just work accomplishing nothing. Trying to think of way to further reduce candidate vcpus....

... the patches are posted - you could try them out?

The concern I have is that even though we have gone through changes to help reduce the candidate vcpus we yield to, we still have a very poor idea of which vcpu really needs to run. The result is high cpu usage in the get_pid_task and still some contention in the double runqueue lock. To make this scalable, we either need to significantly reduce the occurrence of the lock-holder preemption, or do a much better job of knowing which vcpu needs to run (and not unnecessarily yielding to vcpus which do not need to run).

On reducing the occurrence: The worst case for lock-holder preemption is having vcpus of same VM on the same runqueue. This guarantees the situation of 1 vcpu running while another [of the same VM] is not. To prove the point, I ran the same test, but with vcpus restricted to a range of host cpus, such that any single VM's vcpus can never be on the same runqueue. In this case, all 10 VMs' vcpu-0's are on host cpus 0-4, vcpu-1's are on host cpus 5-9, and so on. Here is the result:

kvm_cpu_spin, and all
yield_to changes, plus
restricted vcpu placement: 8823 +/- 3.20% much, much better

On picking a better vcpu to yield to: I really hesitate to rely on paravirt hint [telling us which vcpu is holding a lock], but I am not sure how else to reduce the candidate vcpus to yield to. I suspect we are yielding to way more vcpus than are prempted lock-holders, and that IMO is just work accomplishing nothing. Trying to think of way to further reduce candidate vcpus....

Quoted 21 lines · Andrew Theurer

The concern I have is that even though we have gone through changes to help reduce the candidate vcpus we yield to, we still have a very poor idea of which vcpu really needs to run. The result is high cpu usage in the get_pid_task and still some contention in the double runqueue lock. To make this scalable, we either need to significantly reduce the occurrence of the lock-holder preemption, or do a much better job of knowing which vcpu needs to run (and not unnecessarily yielding to vcpus which do not need to run).

On reducing the occurrence: The worst case for lock-holder preemption is having vcpus of same VM on the same runqueue. This guarantees the situation of 1 vcpu running while another [of the same VM] is not. To prove the point, I ran the same test, but with vcpus restricted to a range of host cpus, such that any single VM's vcpus can never be on the same runqueue. In this case, all 10 VMs' vcpu-0's are on host cpus 0-4, vcpu-1's are on host cpus 5-9, and so on. Here is the result:

kvm_cpu_spin, and all
yield_to changes, plus
restricted vcpu placement: 8823 +/- 3.20% much, much better

Quoted 6 lines

On picking a better vcpu to yield to: I really hesitate to rely on paravirt hint [telling us which vcpu is holding a lock], but I am not sure how else to reduce the candidate vcpus to yield to. I suspect we are yielding to way more vcpus than are prempted lock-holders, and that IMO is just work accomplishing nothing. Trying to think of way to further reduce candidate vcpus....

I wouldn't say that yielding to the "wrong" vcpu accomplishes nothing. That other vcpu gets work done (unless it is in pause loop itself) and the yielding vcpu gets put to sleep for a while, so it doesn't spend cycles spinning. While we haven't fixed the problem at least the guest is accomplishing work, and meanwhile the real lock holder may get naturally scheduled and clear the lock.

The main problem with this theory is that the experiments don't seem to bear it out. So maybe one of the assumptions is wrong - the yielding vcpu gets scheduled early. That could be the case if the two vcpus are on different runqueues - you could be changing the relative priority of vcpus on the target runqueue, but still remain on top yourself. Is this possible with the current code?

Maybe we should prefer vcpus on the same runqueue as yield_to targets, and only fall back to remote vcpus when we see it didn't help.

Let's examine a few cases:

1. spinner on cpu 0, lock holder on cpu 0

win!

2. spinner on cpu 0, random vcpu(s) (or normal processes) on cpu 0

Spinner gets put to sleep, random vcpus get to work, low lock contention (no double_rq_lock), by the time spinner gets scheduled we might have won

3. spinner on cpu 0, another spinner on cpu 0

Worst case, we'll just spin some more. Need to detect this case and migrate something in.

4. spinner on cpu 0, alone

Similar

It seems we need to tie in to the load balancer.

Would changing the priority of the task while it is spinning help the load balancer?

Signature · 5 lines

error compiling committee.c: too many arguments to function
--
To unsubscribe from this list: send the line "unsubscribe kvm" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Quoted 21 lines · Andrew Theurer

The concern I have is that even though we have gone through changes to help reduce the candidate vcpus we yield to, we still have a very poor idea of which vcpu really needs to run. The result is high cpu usage in the get_pid_task and still some contention in the double runqueue lock. To make this scalable, we either need to significantly reduce the occurrence of the lock-holder preemption, or do a much better job of knowing which vcpu needs to run (and not unnecessarily yielding to vcpus which do not need to run).

On reducing the occurrence: The worst case for lock-holder preemption is having vcpus of same VM on the same runqueue. This guarantees the situation of 1 vcpu running while another [of the same VM] is not. To prove the point, I ran the same test, but with vcpus restricted to a range of host cpus, such that any single VM's vcpus can never be on the same runqueue. In this case, all 10 VMs' vcpu-0's are on host cpus 0-4, vcpu-1's are on host cpus 5-9, and so on. Here is the result:

kvm_cpu_spin, and all
yield_to changes, plus
restricted vcpu placement: 8823 +/- 3.20% much, much better

Quoted 6 lines

On picking a better vcpu to yield to: I really hesitate to rely on paravirt hint [telling us which vcpu is holding a lock], but I am not sure how else to reduce the candidate vcpus to yield to. I suspect we are yielding to way more vcpus than are prempted lock-holders, and that IMO is just work accomplishing nothing. Trying to think of way to further reduce candidate vcpus....

I wouldn't say that yielding to the "wrong" vcpu accomplishes nothing. That other vcpu gets work done (unless it is in pause loop itself) and the yielding vcpu gets put to sleep for a while, so it doesn't spend cycles spinning. While we haven't fixed the problem at least the guest is accomplishing work, and meanwhile the real lock holder may get naturally scheduled and clear the lock.

The main problem with this theory is that the experiments don't seem to bear it out.

So maybe one of the assumptions is wrong - the yielding
vcpu gets scheduled early. That could be the case if the two vcpus are on different runqueues - you could be changing the relative priority of vcpus on the target runqueue, but still remain on top yourself. Is this possible with the current code?

Maybe we should prefer vcpus on the same runqueue as yield_to targets, and only fall back to remote vcpus when we see it didn't help.

Let's examine a few cases:

1. spinner on cpu 0, lock holder on cpu 0

win!

2. spinner on cpu 0, random vcpu(s) (or normal processes) on cpu 0

Spinner gets put to sleep, random vcpus get to work, low lock contention (no double_rq_lock), by the time spinner gets scheduled we might have won

3. spinner on cpu 0, another spinner on cpu 0

Worst case, we'll just spin some more. Need to detect this case and migrate something in.

4. spinner on cpu 0, alone

Similar

It seems we need to tie in to the load balancer.

Would changing the priority of the task while it is spinning help the load balancer?

Quoted 30 lines · Avi Kivity

Quoted 21 lines · Andrew Theurer

The concern I have is that even though we have gone through changes to help reduce the candidate vcpus we yield to, we still have a very poor idea of which vcpu really needs to run. The result is high cpu usage in the get_pid_task and still some contention in the double runqueue lock. To make this scalable, we either need to significantly reduce the occurrence of the lock-holder preemption, or do a much better job of knowing which vcpu needs to run (and not unnecessarily yielding to vcpus which do not need to run).

On reducing the occurrence: The worst case for lock-holder preemption is having vcpus of same VM on the same runqueue. This guarantees the situation of 1 vcpu running while another [of the same VM] is not. To prove the point, I ran the same test, but with vcpus restricted to a range of host cpus, such that any single VM's vcpus can never be on the same runqueue. In this case, all 10 VMs' vcpu-0's are on host cpus 0-4, vcpu-1's are on host cpus 5-9, and so on. Here is the result:

kvm_cpu_spin, and all
yield_to changes, plus
restricted vcpu placement: 8823 +/- 3.20% much, much better

Quoted 6 lines

On picking a better vcpu to yield to: I really hesitate to rely on paravirt hint [telling us which vcpu is holding a lock], but I am not sure how else to reduce the candidate vcpus to yield to. I suspect we are yielding to way more vcpus than are prempted lock-holders, and that IMO is just work accomplishing nothing. Trying to think of way to further reduce candidate vcpus....

Quoted 6 lines

I wouldn't say that yielding to the "wrong" vcpu accomplishes nothing. That other vcpu gets work done (unless it is in pause loop itself) and the yielding vcpu gets put to sleep for a while, so it doesn't spend cycles spinning. While we haven't fixed the problem at least the guest is accomplishing work, and meanwhile the real lock holder may get naturally scheduled and clear the lock.

OK, yes, if the other thread gets useful work done, then it is not wasteful. I was thinking of the worst case scenario, where any other vcpu would likely spin as well, and the host side cpu-time for switching vcpu threads was not all that productive. Well, I suppose it does help eliminate potential lock holding vcpus; it just seems to be not that efficient or fast enough.

Quoted 3 lines

The main problem with this theory is that the experiments don't seem to bear it out.

Granted, my test case is quite brutal. It's nothing but over-committed VMs which always have some spin lock activity. However, we really should try to fix the worst case scenario.

Quoted 18 lines

So maybe one of the assumptions is wrong - the yielding
vcpu gets scheduled early. That could be the case if the two vcpus are on different runqueues - you could be changing the relative priority of vcpus on the target runqueue, but still remain on top yourself. Is this possible with the current code?

Maybe we should prefer vcpus on the same runqueue as yield_to targets, and only fall back to remote vcpus when we see it didn't help.

Let's examine a few cases:

1. spinner on cpu 0, lock holder on cpu 0

win!

2. spinner on cpu 0, random vcpu(s) (or normal processes) on cpu 0

Quoted 7 lines

Spinner gets put to sleep, random vcpus get to work, low lock contention (no double_rq_lock), by the time spinner gets scheduled we might have won

3. spinner on cpu 0, another spinner on cpu 0

Worst case, we'll just spin some more. Need to detect this case and migrate something in.

Well, we can certainly experiment and see what we get.

IMO, the key to getting this working really well on the large VMs is finding the lock-holding cpu -quickly-. What I think is happening is that we go through a relatively long process to get to that one right vcpu. I guess I need to find a faster way to get there.

So, having both is probably not a good idea. However, I feel like there's more work to be done. With no over-commit (10 VMs), total throughput is 23427 +/- 2.76%. A 2x over-commit will no doubt have some overhead, but a reduction to ~4500 is still terrible. By contrast, 8-way VMs with 2x over-commit have a total throughput roughly 10% less than 8-way VMs with no overcommit (20 vs 10 8-way VMs on 80 cpu-thread host). We still have what appears to be scalability problems, but now it's not so much in runqueue locks for yield_to(), but now get_pid_task():

perf on host:

32.10% 320131 qemu-system-x86 [kernel.kallsyms] [k] get_pid_task 11.60% 115686 qemu-system-x86 [kernel.kallsyms] [k] _raw_spin_lock 10.28% 102522 qemu-system-x86 [kernel.kallsyms] [k] yield_to

 9.17%  91507 qemu-system-x86 [kvm]             [k] kvm_vcpu_on_spin
 7.74%  77257 qemu-system-x86 [kvm]             [k] kvm_vcpu_yield_to
 3.56%  35476 qemu-system-x86 [kernel.kallsyms] [k] __srcu_read_lock
 3.00%  29951 qemu-system-x86 [kvm]             [k] __vcpu_run
 2.93%  29268 qemu-system-x86 [kvm_intel]       [k] vmx_vcpu_run
 2.88%  28783 qemu-system-x86 [kvm]             [k] vcpu_enter_guest
 2.59%  25827 qemu-system-x86 [kernel.kallsyms] [k] __schedule
 1.40%  13976 qemu-system-x86 [kernel.kallsyms] [k] _raw_spin_lock_irq
 1.28%  12823 qemu-system-x86 [kernel.kallsyms] [k] resched_task
 1.14%  11376 qemu-system-x86 [kvm_intel]       [k] vmcs_writel
 0.85%   8502 qemu-system-x86 [kernel.kallsyms] [k] pick_next_task_fair
 0.53%   5315 qemu-system-x86 [kernel.kallsyms] [k] native_write_msr_safe
 0.46%   4553 qemu-system-x86 [kernel.kallsyms] [k] native_load_tr_desc

get_pid_task() uses some rcu fucntions, wondering how scalable this is.... I tend to think of rcu as -not- having issues like this... is there a rcu stat/tracing tool which would help identify potential problems?

Quoted 9 lines

Review bool __sched yield_to(struct task_struct *p,

Quoted 1 line

(quoted diff) +0 -0

@@ -4323,6 +4340,10 @@ bool __sched yield_to(struct task_struct *p,

bool preempt)

Quoted 7 lines

kernel/sched/core.c +4 -0

      rq = this_rq();
 
 again:
+     /* optimistic test to avoid taking locks */
+     if (!__yield_to_candidate(curr, p))
+             goto out_irq;
+

So add something like:

	/* Optimistic, if we 'raced' with another yield_to(), don't bother */
	if (p_rq->cfs_rq->skip)
		goto out_irq;

Quoted 6 lines

kernel/sched/core.c bool __sched yield_to(struct task_struct *p, bool preempt) · line 4348

Quoted 4 lines

kernel/sched/core.c +0 -0

      p_rq = task_rq(p);
      double_rq_lock(rq, p_rq);

But I do have a question on this optimization though,.. Why do we check p_rq->cfs_rq->skip and not rq->cfs_rq->skip ?

That is, I'd like to see this thing explained a little better.

Does it go something like: p_rq is the runqueue of the task we'd like to yield to, rq is our own, they might be the same. If we have a ->skip, there's nothing we can do about it, OTOH p_rq having a ->skip and failing the yield_to() simply means us picking the next VCPU thread, which might be running on an entirely different cpu (rq) and could succeed?

Quoted 6 lines · Raghavendra K T

CCing PeterZ also.

Quoted 3 lines · Andrew Theurer

I have noticed recently that PLE/yield_to() is still not that scalable for really large guests, sometimes even with no CPU over-commit. I have a small change that make a very big difference.

Quoted 2 lines

We are indeed avoiding CPUS in guest mode when we check task->flags& PF_VCPU in vcpu_on_spin path. Doesn't that suffice?

My understanding is that it checks if the candidate vcpu task is in guest mode (let's call this vcpu g1vcpuN), and that vcpu will not be a target to yield to if it is already in guest mode. I am concerned about a different vcpu, possibly from a different VM (let's call it g2vcpuN), but it also located on the same runqueue as g1vcpuN -and- running. That vcpu, g2vcpuN, may also be doing a directed yield, and it may already be holding the rq lock. Or it could be in guest mode. If it is in guest mode, then let's still target this rq, and try to yield to g1vcpuN. However, if g2vcpuN is not in guest mode, then don't bother trying.

Patch include below.

Here's the new, v2 result with the previous two:

10 VMs, 16-way each, all running dbench (2x cpu over-commit)
throughput +/- stddev
----- -----
ple on: 2552 +/- .70%
ple on: w/fixv1: 4621 +/- 2.12% (81% improvement)
ple on: w/fixv2: 6115* (139% improvement)

[*] I do not have stdev yet because all 10 runs are not complete

for v1 to v2, host CPU dropped from 60% to 50%. Time in spin_lock() is also dropping:

So this seems to be working. However I wonder just how far we can take this. Ideally we need to be in<3-4% in host for PLE work, like I observe for the 8-way VMs. We are still way off.

-Andrew

Signed-off-by Andrew Theurer<[email protected]>

kernel/sched/core.c +0 -0

index fbf1fd0..c767915 100644