Skip to contentSkip to conversation

sched: Clear ttwu_pending after enqueue_task

PATCH Superseded Tianchen Ding 5 participants 11 messages Nov 1, 2022 – Nov 16, 2022 Scheduler

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 sched: Clear ttwu_pending after enqueue_task

We found a long tail latency in schbench whem m*t is close to nr_cpus. (e.g., "schbench -m 2 -t 16" on a machine with 32 cpus.)

This is because when the wakee cpu is idle, rq->ttwu_pending is cleared too early, and idle_cpu() will return true until the wakee task enqueued. This will mislead the waker when selecting idle cpu, and wake multiple worker threads on the same wakee cpu. This situation is enlarged by commit f3dd3f674555 ("sched: Remove the limitation of WF_ON_CPU on wakelist if wakee cpu is idle") because it tends to use wakelist.

Here is the result of "schbench -m 2 -t 16" on a VM with 32vcpu (Intel(R) Xeon(R) Platinum 8369B).

Latency percentiles (usec):
base base+revert_f3dd3f674555 base+this_patch

50.0000th:         9                            13                 9
75.0000th:        12                            19                12
90.0000th:        15                            22                15
95.0000th:        18                            24                17
*99.0000th:       27                            31                24
99.5000th:      3364                            33                27
99.9000th:     12560                            36                30
---
 kernel/sched/core.c | 8 +-------
 1 file changed, 1 insertion(+), 7 deletions(-)
kernel/sched/core.c +1 -7
index 87c9cdf37a26..b07de1753be5 100644
@@ -3739,13 +3739,6 @@ void sched_ttwu_pending(void *arg)
 	if (!llist)
 		return;
 
-	/*
-	 * rq::ttwu_pending racy indication of out-standing wakeups.
-	 * Races such that false-negatives are possible, since they
-	 * are shorter lived that false-positives would be.
-	 */
-	WRITE_ONCE(rq->ttwu_pending, 0);
-
 	rq_lock_irqsave(rq, &rf);
 	update_rq_clock(rq);
 
@@ -3760,6 +3753,7 @@ void sched_ttwu_pending(void *arg)
 	}
 
 	rq_unlock_irqrestore(rq, &rf);
+	WRITE_ONCE(rq->ttwu_pending, 0);
 }
 
 void send_call_function_single_ipi(int cpu)
Signature · 1 line
2.27.0
maintainer
#1 lore raw
Quoted 15 lines · Tianchen Ding

We found a long tail latency in schbench whem m*t is close to nr_cpus. (e.g., "schbench -m 2 -t 16" on a machine with 32 cpus.)

This is because when the wakee cpu is idle, rq->ttwu_pending is cleared too early, and idle_cpu() will return true until the wakee task enqueued. This will mislead the waker when selecting idle cpu, and wake multiple worker threads on the same wakee cpu. This situation is enlarged by commit f3dd3f674555 ("sched: Remove the limitation of WF_ON_CPU on wakelist if wakee cpu is idle") because it tends to use wakelist.

Here is the result of "schbench -m 2 -t 16" on a VM with 32vcpu (Intel(R) Xeon(R) Platinum 8369B).

Latency percentiles (usec):
base base+revert_f3dd3f674555 base+this_patch

Quoted 7 lines
50.0000th:         9                            13                 9
75.0000th:        12                            19                12
90.0000th:        15                            22                15
95.0000th:        18                            24                17
*99.0000th:       27                            31                24
99.5000th:      3364                            33                27
99.9000th:     12560                            36                30

Nice; but have you also ran other benchmarks and confirmed it doesn't negatively affect those?

If so; mentioning that is very helpful. If not; best go do so :-)

Quoted 13 lines
---
 kernel/sched/core.c | 8 +-------
 1 file changed, 1 insertion(+), 7 deletions(-)
kernel/sched/core.c +0 -0
index 87c9cdf37a26..b07de1753be5 100644
@@ -3739,13 +3739,6 @@ void sched_ttwu_pending(void *arg)
 	if (!llist)
 		return;
 

kernel/sched/core.c void sched_ttwu_pending(void *arg) · line 3744

Quoted 10 lines
kernel/sched/core.c +0 -7
-	/*
-	 * rq::ttwu_pending racy indication of out-standing wakeups.
-	 * Races such that false-negatives are possible, since they
-	 * are shorter lived that false-positives would be.
-	 */
-	WRITE_ONCE(rq->ttwu_pending, 0);
-
 	rq_lock_irqsave(rq, &rf);
 	update_rq_clock(rq);
 

Could you try the below instead? Also note the comment; since you did the work to figure out why -- best record that for posterity.

@@ -3737,6 +3730,13 @@ void sched_ttwu_pending(void *arg)
set_task_cpu(p, cpu_of(rq));

ttwu_do_activate(rq, p, p->sched_remote_wakeup ? WF_MIGRATED : 0, &rf);
+ /*
+ * Must be after enqueueing at least once task such that
+ * idle_cpu() does not observe a false-negative -- if it does,
+ * it is possible for select_idle_siblings() to stack a number
+ * of tasks on this CPU during that window.
+ */
+ WRITE_ONCE(rq->ttwu_pending, 0);
}

rq_unlock_irqrestore(rq, &rf);

#2 lore raw
Quoted 57 lines · Peter Zijlstra
Quoted 15 lines · Tianchen Ding

We found a long tail latency in schbench whem m*t is close to nr_cpus. (e.g., "schbench -m 2 -t 16" on a machine with 32 cpus.)

This is because when the wakee cpu is idle, rq->ttwu_pending is cleared too early, and idle_cpu() will return true until the wakee task enqueued. This will mislead the waker when selecting idle cpu, and wake multiple worker threads on the same wakee cpu. This situation is enlarged by commit f3dd3f674555 ("sched: Remove the limitation of WF_ON_CPU on wakelist if wakee cpu is idle") because it tends to use wakelist.

Here is the result of "schbench -m 2 -t 16" on a VM with 32vcpu (Intel(R) Xeon(R) Platinum 8369B).

Latency percentiles (usec):
base base+revert_f3dd3f674555 base+this_patch

Quoted 7 lines
50.0000th:         9                            13                 9
75.0000th:        12                            19                12
90.0000th:        15                            22                15
95.0000th:        18                            24                17
*99.0000th:       27                            31                24
99.5000th:      3364                            33                27
99.9000th:     12560                            36                30

Nice; but have you also ran other benchmarks and confirmed it doesn't negatively affect those?

If so; mentioning that is very helpful. If not; best go do so :-)

Quoted 13 lines
---
 kernel/sched/core.c | 8 +-------
 1 file changed, 1 insertion(+), 7 deletions(-)
kernel/sched/core.c +0 -0
index 87c9cdf37a26..b07de1753be5 100644
@@ -3739,13 +3739,6 @@ void sched_ttwu_pending(void *arg)
 	if (!llist)
 		return;
 

kernel/sched/core.c void sched_ttwu_pending(void *arg) · line 3744

Quoted 10 lines
kernel/sched/core.c +0 -7
-	/*
-	 * rq::ttwu_pending racy indication of out-standing wakeups.
-	 * Races such that false-negatives are possible, since they
-	 * are shorter lived that false-positives would be.
-	 */
-	WRITE_ONCE(rq->ttwu_pending, 0);
-
 	rq_lock_irqsave(rq, &rf);
 	update_rq_clock(rq);
 

Could you try the below instead? Also note the comment; since you did the work to figure out why -- best record that for posterity.

Review void sched_ttwu_pending(void *arg) · line 3739

Quoted 10 lines
(quoted diff) +7 -0
@@ -3737,6 +3730,13 @@ void sched_ttwu_pending(void *arg)
 			set_task_cpu(p, cpu_of(rq));
 
 		ttwu_do_activate(rq, p, p->sched_remote_wakeup ? WF_MIGRATED : 0, &rf);
+		/*
+		 * Must be after enqueueing at least once task such that
+		 * idle_cpu() does not observe a false-negative -- if it does,
+		 * it is possible for select_idle_siblings() to stack a number
+		 * of tasks on this CPU during that window.
+		 */
+		WRITE_ONCE(rq->ttwu_pending, 0);

Just curious why do we put above code inside llist_for_each_entry_safe loop? My understanding is that once 1 task is queued, select_idle_cpu() would not treat this rq as idle anymore because nr_running is not 0. But would this bring overhead to write the rq->ttwu_pending multiple times, do I miss something?

thanks,
Chenyu

Quoted 3 lines
kernel/sched/core.c +0 -0
 	}
 
 	rq_unlock_irqrestore(rq, &rf);
maintainer
#3 lore raw
Quoted 16 lines · Chen Yu
Quoted 4 lines

Could you try the below instead? Also note the comment; since you did the work to figure out why -- best record that for posterity.

Review void sched_ttwu_pending(void *arg) · line 3739

Quoted 10 lines
(quoted diff) +7 -0
@@ -3737,6 +3730,13 @@ void sched_ttwu_pending(void *arg)
 			set_task_cpu(p, cpu_of(rq));
 
 		ttwu_do_activate(rq, p, p->sched_remote_wakeup ? WF_MIGRATED : 0, &rf);
+		/*
+		 * Must be after enqueueing at least once task such that
+		 * idle_cpu() does not observe a false-negative -- if it does,
+		 * it is possible for select_idle_siblings() to stack a number
+		 * of tasks on this CPU during that window.
+		 */
+		WRITE_ONCE(rq->ttwu_pending, 0);

Just curious why do we put above code inside llist_for_each_entry_safe loop?

Quoted 3 lines

My understanding is that once 1 task is queued, select_idle_cpu() would not treat this rq as idle anymore because nr_running is not 0. But would this bring overhead to write the rq->ttwu_pending multiple times, do I miss something?

So the consideration is that by clearing it late, you might also clear a next set; consider something like:

	cpu0			cpu1			cpu2

	ttwu_queue()
	  ->ttwu_pending = 1;
	  llist_add()

				sched_ttwu_pending()
				  llist_del_all()
				  ... long ...
							ttwu_queue()
							  ->ttwu_pending = 1
							  llist_add()

				  ... time ...
				  ->ttwu_pending = 0

Which leaves you with a non-empty list but with ttwu_pending == 0.

But I suppose that's not actually better with my variant, since it keeps writing 0s. We can make it more complicated again, but perhaps it doesn't matter and your version is good enough.

But please update with a comment on why it needs to be after ttwu_do_activate().

#4 lore raw
Quoted 42 lines · Peter Zijlstra
Quoted 16 lines · Chen Yu
Quoted 4 lines

Could you try the below instead? Also note the comment; since you did the work to figure out why -- best record that for posterity.

Review void sched_ttwu_pending(void *arg) · line 3739

Quoted 10 lines
(quoted diff) +7 -0
@@ -3737,6 +3730,13 @@ void sched_ttwu_pending(void *arg)
 			set_task_cpu(p, cpu_of(rq));
 
 		ttwu_do_activate(rq, p, p->sched_remote_wakeup ? WF_MIGRATED : 0, &rf);
+		/*
+		 * Must be after enqueueing at least once task such that
+		 * idle_cpu() does not observe a false-negative -- if it does,
+		 * it is possible for select_idle_siblings() to stack a number
+		 * of tasks on this CPU during that window.
+		 */
+		WRITE_ONCE(rq->ttwu_pending, 0);

Just curious why do we put above code inside llist_for_each_entry_safe loop?

Quoted 3 lines

My understanding is that once 1 task is queued, select_idle_cpu() would not treat this rq as idle anymore because nr_running is not 0. But would this bring overhead to write the rq->ttwu_pending multiple times, do I miss something?

So the consideration is that by clearing it late, you might also clear a next set; consider something like:

	cpu0			cpu1			cpu2

	ttwu_queue()
	  ->ttwu_pending = 1;
	  llist_add()

				sched_ttwu_pending()
				  llist_del_all()
				  ... long ...
							ttwu_queue()
							  ->ttwu_pending = 1
							  llist_add()

				  ... time ...
				  ->ttwu_pending = 0
Quoted 2 lines

Which leaves you with a non-empty list but with ttwu_pending == 0.

Thanks for the explaination, in theory the race windows could be shrinked but could not be closed due to ttwu_pending is not protected by lock in ttwu_queue() -> __ttwu_queue_wakelist() I suppose.

Quoted 3 lines

But I suppose that's not actually better with my variant, since it keeps writing 0s. We can make it more complicated again, but perhaps it doesn't matter and your version is good enough.

I see, although I'm not the author of this patch :)

thanks,
Chenyu

Quoted 4 lines

But please update with a comment on why it needs to be after ttwu_do_activate().

#6 lore raw
In reply to Peter Zijlstra
Quoted 24 lines · Peter Zijlstra
Quoted 15 lines · Tianchen Ding

We found a long tail latency in schbench whem m*t is close to nr_cpus. (e.g., "schbench -m 2 -t 16" on a machine with 32 cpus.)

This is because when the wakee cpu is idle, rq->ttwu_pending is cleared too early, and idle_cpu() will return true until the wakee task enqueued. This will mislead the waker when selecting idle cpu, and wake multiple worker threads on the same wakee cpu. This situation is enlarged by commit f3dd3f674555 ("sched: Remove the limitation of WF_ON_CPU on wakelist if wakee cpu is idle") because it tends to use wakelist.

Here is the result of "schbench -m 2 -t 16" on a VM with 32vcpu (Intel(R) Xeon(R) Platinum 8369B).

Latency percentiles (usec):
base base+revert_f3dd3f674555 base+this_patch

Quoted 7 lines
50.0000th:         9                            13                 9
75.0000th:        12                            19                12
90.0000th:        15                            22                15
95.0000th:        18                            24                17
*99.0000th:       27                            31                24
99.5000th:      3364                            33                27
99.9000th:     12560                            36                30
Quoted 5 lines

Nice; but have you also ran other benchmarks and confirmed it doesn't negatively affect those?

If so; mentioning that is very helpful. If not; best go do so :-)

Thanks for the review.

We've tested with unixbench and hackbench (they show the average scores), and the performance result seems no difference.
We don't mention here because what we found is a specific case in schbench (where m*t==nr_cpus). It only affect long tail latency, so the problem and the fix should also take effects on only this case, not the average scores.

Quoted 13 lines
Quoted 13 lines
---
  kernel/sched/core.c | 8 +-------
  1 file changed, 1 insertion(+), 7 deletions(-)
kernel/sched/core.c +0 -0
index 87c9cdf37a26..b07de1753be5 100644
@@ -3739,13 +3739,6 @@ void sched_ttwu_pending(void *arg)
  	if (!llist)
  		return;
 
Quoted 14 lines

kernel/sched/core.c void sched_ttwu_pending(void *arg) · line 3744

Quoted 10 lines
kernel/sched/core.c +0 -7
-	/*
-	 * rq::ttwu_pending racy indication of out-standing wakeups.
-	 * Races such that false-negatives are possible, since they
-	 * are shorter lived that false-positives would be.
-	 */
-	WRITE_ONCE(rq->ttwu_pending, 0);
-
  	rq_lock_irqsave(rq, &rf);
  	update_rq_clock(rq);
 

Could you try the below instead? Also note the comment; since you did the work to figure out why -- best record that for posterity.

It works well for me. But I have the same thought with Chen Yu, and will explain in detail in my next reply.

Thanks.

Quoted 14 lines
(quoted diff) +7 -0
@@ -3737,6 +3730,13 @@ void sched_ttwu_pending(void *arg)
  			set_task_cpu(p, cpu_of(rq));
 
  		ttwu_do_activate(rq, p, p->sched_remote_wakeup ? WF_MIGRATED : 0, &rf);
+		/*
+		 * Must be after enqueueing at least once task such that
+		 * idle_cpu() does not observe a false-negative -- if it does,
+		 * it is possible for select_idle_siblings() to stack a number
+		 * of tasks on this CPU during that window.
+		 */
+		WRITE_ONCE(rq->ttwu_pending, 0);
  	}
 
  	rq_unlock_irqrestore(rq, &rf);
#5 lore raw
In reply to Peter Zijlstra
Quoted 42 lines · Peter Zijlstra
Quoted 16 lines · Chen Yu
Quoted 4 lines

Could you try the below instead? Also note the comment; since you did the work to figure out why -- best record that for posterity.

Review void sched_ttwu_pending(void *arg) · line 3739

Quoted 10 lines
(quoted diff) +7 -0
@@ -3737,6 +3730,13 @@ void sched_ttwu_pending(void *arg)
  			set_task_cpu(p, cpu_of(rq));
 
  		ttwu_do_activate(rq, p, p->sched_remote_wakeup ? WF_MIGRATED : 0, &rf);
+		/*
+		 * Must be after enqueueing at least once task such that
+		 * idle_cpu() does not observe a false-negative -- if it does,
+		 * it is possible for select_idle_siblings() to stack a number
+		 * of tasks on this CPU during that window.
+		 */
+		WRITE_ONCE(rq->ttwu_pending, 0);

Just curious why do we put above code inside llist_for_each_entry_safe loop?

Quoted 3 lines

My understanding is that once 1 task is queued, select_idle_cpu() would not treat this rq as idle anymore because nr_running is not 0. But would this bring overhead to write the rq->ttwu_pending multiple times, do I miss something?

So the consideration is that by clearing it late, you might also clear a next set; consider something like:

	cpu0			cpu1			cpu2

	ttwu_queue()
	  ->ttwu_pending = 1;
	  llist_add()

				sched_ttwu_pending()
				  llist_del_all()
				  ... long ...
							ttwu_queue()
							  ->ttwu_pending = 1
							  llist_add()

				  ... time ...
				  ->ttwu_pending = 0
Quoted 6 lines

Which leaves you with a non-empty list but with ttwu_pending == 0.

But I suppose that's not actually better with my variant, since it keeps writing 0s. We can make it more complicated again, but perhaps it doesn't matter and your version is good enough.

Yeah. Since your version repeats writting 0 to ttwu_pending, it finally reaches the same effect with mine. Although the performance results in my tests seem to be no difference, it may still bring more overhead.

IMO, according to the latest linux-next code, all callers querying rq->ttwu_pending only take cares about whether the cpu is idle because they always combine with querying nr_running. Actually no one cares about whether wake_entry.llist is empty. So for the use of checking cpu idle state, move rq->ttwu_pending=0 after enqueuing task can help fully cover the whole state.

For your case, although ttwu_pending is set to 0 with some tasks really pending, at this time nr_running is sure to be >0, so callers who query both ttwu_pending and nr_running will know this cpu is not idle. (Now the callers querying these two values are lockless, so there may be race in a really small window? But this case is extremely rare, I think we should not make it more complicated.)

Quoted 2 lines

But please update with a comment on why it needs to be after ttwu_do_activate().

OK. Should I send v2 or you directly add the comment?

Thanks.

#7 lore raw

PATCH v2 1/1 sched: Clear ttwu_pending after enqueue_task

In reply to Tianchen Ding

We found a long tail latency in schbench whem m*t is close to nr_cpus. (e.g., "schbench -m 2 -t 16" on a machine with 32 cpus.)

This is because when the wakee cpu is idle, rq->ttwu_pending is cleared too early, and idle_cpu() will return true until the wakee task enqueued. This will mislead the waker when selecting idle cpu, and wake multiple worker threads on the same wakee cpu. This situation is enlarged by commit f3dd3f674555 ("sched: Remove the limitation of WF_ON_CPU on wakelist if wakee cpu is idle") because it tends to use wakelist.

Here is the result of "schbench -m 2 -t 16" on a VM with 32vcpu (Intel(R) Xeon(R) Platinum 8369B).

Latency percentiles (usec):
base base+revert_f3dd3f674555 base+this_patch

50.0000th:         9                            13                 9
75.0000th:        12                            19                12
90.0000th:        15                            22                15
95.0000th:        18                            24                17
*99.0000th:       27                            31                24
99.5000th:      3364                            33                27
99.9000th:     12560                            36                30

We also tested on unixbench and hackbench, and saw no performance change.

---
v2:
Update commit log about other benchmarks.
Add comment in code.
Move the code before rq_unlock. This can make ttwu_pending updated a bit earlier than v1 so that it can reflect the real condition more timely, maybe.

v1: https://lore.kernel.org/all/[email protected]/

---
 kernel/sched/core.c | 18 +++++++++++-------
 1 file changed, 11 insertions(+), 7 deletions(-)
kernel/sched/core.c +11 -7
index 87c9cdf37a26..7a04b5565389 100644
@@ -3739,13 +3739,6 @@ void sched_ttwu_pending(void *arg)
 	if (!llist)
 		return;
 
-	/*
-	 * rq::ttwu_pending racy indication of out-standing wakeups.
-	 * Races such that false-negatives are possible, since they
-	 * are shorter lived that false-positives would be.
-	 */
-	WRITE_ONCE(rq->ttwu_pending, 0);
-
 	rq_lock_irqsave(rq, &rf);
 	update_rq_clock(rq);
 
@@ -3759,6 +3752,17 @@ void sched_ttwu_pending(void *arg)
 		ttwu_do_activate(rq, p, p->sched_remote_wakeup ? WF_MIGRATED : 0, &rf);
 	}
 
+	/*
+	 * Must be after enqueueing at least once task such that
+	 * idle_cpu() does not observe a false-negative -- if it does,
+	 * it is possible for select_idle_siblings() to stack a number
+	 * of tasks on this CPU during that window.
+	 *
+	 * It is ok to clear ttwu_pending when another task pending.
+	 * We will receive IPI after local irq enabled and then enqueue it.
+	 * Since now nr_running > 0, idle_cpu() will always get correct result.
+	 */
+	WRITE_ONCE(rq->ttwu_pending, 0);
 	rq_unlock_irqrestore(rq, &rf);
 }
 
Signature · 1 line
2.27.0
Reviewed-by on v2 1/1
#8 lore raw
Quoted 66 lines · Tianchen Ding

We found a long tail latency in schbench whem m*t is close to nr_cpus. (e.g., "schbench -m 2 -t 16" on a machine with 32 cpus.)

This is because when the wakee cpu is idle, rq->ttwu_pending is cleared too early, and idle_cpu() will return true until the wakee task enqueued. This will mislead the waker when selecting idle cpu, and wake multiple worker threads on the same wakee cpu. This situation is enlarged by commit f3dd3f674555 ("sched: Remove the limitation of WF_ON_CPU on wakelist if wakee cpu is idle") because it tends to use wakelist.

Here is the result of "schbench -m 2 -t 16" on a VM with 32vcpu (Intel(R) Xeon(R) Platinum 8369B).

Latency percentiles (usec):
base base+revert_f3dd3f674555 base+this_patch

50.0000th:         9                            13                 9
75.0000th:        12                            19                12
90.0000th:        15                            22                15
95.0000th:        18                            24                17
*99.0000th:       27                            31                24
99.5000th:      3364                            33                27
99.9000th:     12560                            36                30

We also tested on unixbench and hackbench, and saw no performance change.

---
v2:
Update commit log about other benchmarks.
Add comment in code.
Move the code before rq_unlock. This can make ttwu_pending updated a bit earlier than v1 so that it can reflect the real condition more timely, maybe.

v1: https://lore.kernel.org/all/[email protected]/

---
 kernel/sched/core.c | 18 +++++++++++-------
 1 file changed, 11 insertions(+), 7 deletions(-)
kernel/sched/core.c +4 -7
index 87c9cdf37a26..7a04b5565389 100644
@@ -3739,13 +3739,6 @@ void sched_ttwu_pending(void *arg)
 	if (!llist)
 		return;
 
-	/*
-	 * rq::ttwu_pending racy indication of out-standing wakeups.
-	 * Races such that false-negatives are possible, since they
-	 * are shorter lived that false-positives would be.
-	 */
-	WRITE_ONCE(rq->ttwu_pending, 0);
-
 	rq_lock_irqsave(rq, &rf);
 	update_rq_clock(rq);
 
@@ -3759,6 +3752,17 @@ void sched_ttwu_pending(void *arg)
 		ttwu_do_activate(rq, p, p->sched_remote_wakeup ? WF_MIGRATED : 0, &rf);
 	}
 
+	/*
+	 * Must be after enqueueing at least once task such that
+	 * idle_cpu() does not observe a false-negative -- if it does,
+	 * it is possible for select_idle_siblings() to stack a number

kernel/sched/core.c void sched_ttwu_pending(void *arg) · line 3768

Quoted 10 lines
kernel/sched/core.c +7 -0
+	 * of tasks on this CPU during that window.
+	 *
+	 * It is ok to clear ttwu_pending when another task pending.
+	 * We will receive IPI after local irq enabled and then enqueue it.
+	 * Since now nr_running > 0, idle_cpu() will always get correct result.
+	 */
+	WRITE_ONCE(rq->ttwu_pending, 0);
 	rq_unlock_irqrestore(rq, &rf);
 }
 

thanks,
Chenyu

reviewer Acked-by on v2 1/1
#9 lore raw
In reply to Tianchen Ding
Quoted 23 lines · Tianchen Ding

We found a long tail latency in schbench whem m*t is close to nr_cpus. (e.g., "schbench -m 2 -t 16" on a machine with 32 cpus.)

This is because when the wakee cpu is idle, rq->ttwu_pending is cleared too early, and idle_cpu() will return true until the wakee task enqueued. This will mislead the waker when selecting idle cpu, and wake multiple worker threads on the same wakee cpu. This situation is enlarged by commit f3dd3f674555 ("sched: Remove the limitation of WF_ON_CPU on wakelist if wakee cpu is idle") because it tends to use wakelist.

Here is the result of "schbench -m 2 -t 16" on a VM with 32vcpu (Intel(R) Xeon(R) Platinum 8369B).

Latency percentiles (usec):
base base+revert_f3dd3f674555 base+this_patch

50.0000th:         9                            13                 9
75.0000th:        12                            19                12
90.0000th:        15                            22                15
95.0000th:        18                            24                17
*99.0000th:       27                            31                24
99.5000th:      3364                            33                27
99.9000th:     12560                            36                30
Quoted 4 lines

We also tested on unixbench and hackbench, and saw no performance change.

I tested this on bare metal across a range of machines. The impact of the patch is nowhere near as obvious as it is on a VM but even then, schbench generally benefits (not by as much and not always at all percentiles). The only workload that appeared to suffer was specjbb2015 but *only* on NUMA machines, on UMA it was fine and the benchmark can be a little flaky for getting stable results anyway. In the few cases where it showed a problem, the NUMA balancing behaviour was also different so I think it can be ignored.

In most cases it was better than vanilla and better than a revert or at least made marginal differences that were borderline noise. However, avoiding stacking tasks due to false positives is also important because even though that can help performance in some cases (strictly sync wakeups), it's not necessarily a good idea. So while it's not a universal win, it wins more than it loses and it appears to be more clearly a win on VMs so on that basis

Signature · 2 lines
Mel Gorman
SUSE Labs
merge bot Applied
#10 lore raw

[tip: sched/core] sched: Clear ttwu_pending after enqueue_task()

In reply to Tianchen Ding
The following commit has been merged into the sched/core branch of tip:

The following commit has been merged into the sched/core branch of tip:

Commit-ID:     d6962c4fe8f96f7d384d6489b6b5ab5bf3e35991
Gitweb:        https://git.kernel.org/tip/d6962c4fe8f96f7d384d6489b6b5ab5bf3e35991
Author:        Tianchen Ding <[email protected]>
AuthorDate:    Fri, 04 Nov 2022 10:36:01 +08:00
Committer:     Peter Zijlstra <[email protected]>
CommitterDate: Wed, 16 Nov 2022 10:13:05 +01:00

sched: Clear ttwu_pending after enqueue_task()

We found a long tail latency in schbench whem m*t is close to nr_cpus. (e.g., "schbench -m 2 -t 16" on a machine with 32 cpus.)

This is because when the wakee cpu is idle, rq->ttwu_pending is cleared too early, and idle_cpu() will return true until the wakee task enqueued. This will mislead the waker when selecting idle cpu, and wake multiple worker threads on the same wakee cpu. This situation is enlarged by commit f3dd3f674555 ("sched: Remove the limitation of WF_ON_CPU on wakelist if wakee cpu is idle") because it tends to use wakelist.

Here is the result of "schbench -m 2 -t 16" on a VM with 32vcpu (Intel(R) Xeon(R) Platinum 8369B).

Latency percentiles (usec):
base base+revert_f3dd3f674555 base+this_patch

50.0000th:         9                            13                 9
75.0000th:        12                            19                12
90.0000th:        15                            22                15
95.0000th:        18                            24                17
*99.0000th:       27                            31                24
99.5000th:      3364                            33                27
99.9000th:     12560                            36                30

We also tested on unixbench and hackbench, and saw no performance change.

---
 kernel/sched/core.c | 18 +++++++++++-------
 1 file changed, 11 insertions(+), 7 deletions(-)
kernel/sched/core.c +11 -7
index 07ac08c..314c2c0 100644
@@ -3739,13 +3739,6 @@ void sched_ttwu_pending(void *arg)
 	if (!llist)
 		return;
 
-	/*
-	 * rq::ttwu_pending racy indication of out-standing wakeups.
-	 * Races such that false-negatives are possible, since they
-	 * are shorter lived that false-positives would be.
-	 */
-	WRITE_ONCE(rq->ttwu_pending, 0);
-
 	rq_lock_irqsave(rq, &rf);
 	update_rq_clock(rq);
 
@@ -3759,6 +3752,17 @@ void sched_ttwu_pending(void *arg)
 		ttwu_do_activate(rq, p, p->sched_remote_wakeup ? WF_MIGRATED : 0, &rf);
 	}
 
+	/*
+	 * Must be after enqueueing at least once task such that
+	 * idle_cpu() does not observe a false-negative -- if it does,
+	 * it is possible for select_idle_siblings() to stack a number
+	 * of tasks on this CPU during that window.
+	 *
+	 * It is ok to clear ttwu_pending when another task pending.
+	 * We will receive IPI after local irq enabled and then enqueue it.
+	 * Since now nr_running > 0, idle_cpu() will always get correct result.
+	 */
+	WRITE_ONCE(rq->ttwu_pending, 0);
 	rq_unlock_irqrestore(rq, &rf);
 }