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

Signed-off-by: Tianchen Ding <dtcccc@linux.alibaba.com>
---
 kernel/sched/core.c | 8 +-------
 1 file changed, 1 insertion(+), 7 deletions(-)
  

On Tue, Nov 01, 2022 at 03:36:30PM +0800, Tianchen Ding wrote:
> 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

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 :-)

> Signed-off-by: Tianchen Ding <dtcccc@linux.alibaba.com>
> ---
>  kernel/sched/core.c | 8 +-------
>  1 file changed, 1 insertion(+), 7 deletions(-)
> 
> diff --git a/kernel/sched/core.c b/kernel/sched/core.c
> index 87c9cdf37a26..b07de1753be5 100644
> --- a/kernel/sched/core.c
> +++ b/kernel/sched/core.c
> @@ -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);
>  

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);
  

On 2022-11-01 at 11:34:04 +0100, Peter Zijlstra wrote:
> On Tue, Nov 01, 2022 at 03:36:30PM +0800, Tianchen Ding wrote:
> > 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
> 
> 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 :-)
> 
> > Signed-off-by: Tianchen Ding <dtcccc@linux.alibaba.com>
> > ---
> >  kernel/sched/core.c | 8 +-------
> >  1 file changed, 1 insertion(+), 7 deletions(-)
> > 
> > diff --git a/kernel/sched/core.c b/kernel/sched/core.c
> > index 87c9cdf37a26..b07de1753be5 100644
> > --- a/kernel/sched/core.c
> > +++ b/kernel/sched/core.c
> > @@ -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);
> >  
> 
> 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);
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
>  	}
>  
>  	rq_unlock_irqrestore(rq, &rf);
  

On Tue, Nov 01, 2022 at 09:51:25PM +0800, Chen Yu wrote:

> > 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);
> 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?

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().
  

On 2022-11-01 at 15:59:25 +0100, Peter Zijlstra wrote:
> On Tue, Nov 01, 2022 at 09:51:25PM +0800, Chen Yu wrote:
> 
> > > 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);
> > 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?
> 
> 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.
>
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.
> 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
> 
> But please update with a comment on why it needs to be after
> ttwu_do_activate().
>
  

On 2022/11/1 18:34, Peter Zijlstra wrote:
> On Tue, Nov 01, 2022 at 03:36:30PM +0800, Tianchen Ding wrote:
>> 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
> 
> 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.

>> Signed-off-by: Tianchen Ding <dtcccc@linux.alibaba.com>
>> ---
>>   kernel/sched/core.c | 8 +-------
>>   1 file changed, 1 insertion(+), 7 deletions(-)
>>
>> diff --git a/kernel/sched/core.c b/kernel/sched/core.c
>> index 87c9cdf37a26..b07de1753be5 100644
>> --- a/kernel/sched/core.c
>> +++ b/kernel/sched/core.c
>> @@ -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);
>>   
> 
> 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.

> @@ -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);
  

On 2022/11/1 22:59, Peter Zijlstra wrote:
> On Tue, Nov 01, 2022 at 09:51:25PM +0800, Chen Yu wrote:
> 
>>> 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);
>> 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?
> 
> 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.
> 

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.)

> 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.