[Problem Statement]
For a workload that is doing frequent context switches, the throughput
scales well until the number of instances reaches a peak point. After
that peak point, the throughput drops significantly if the number of
instances continues to increase.

The will-it-scale context_switch1 test case exposes the issue. The
test platform has 112 CPUs per LLC domain. The will-it-scale launches
1, 8, 16 ... 112 instances respectively. Each instance is composed
of 2 tasks, and each pair of tasks would do ping-pong scheduling via
pipe_read() and pipe_write(). No task is bound to any CPU.
It is found that, once the number of instances is higher than
56(112 tasks in total, every CPU has 1 task), the throughput
drops accordingly if the instance number continues to increase:

          ^
throughput|
          |                 X
          |               X   X X
          |             X         X X
          |           X               X
          |         X                   X
          |       X
          |     X
          |   X
          | X
          |
          +-----------------.------------------->
                            56
                                 number of instances

[Symptom analysis]

The performance downgrading was caused by a high system idle
percentage(around 20% ~ 30%). The CPUs waste a lot of time in
idle and do nothing. As a comparison, if set CPU affinity to
these workloads and stops them from migrating among CPUs,
the idle percentage drops to nearly 0%, and the throughput
increases a lot. This indicates room for optimization.

The cause is the race condition between select_task_rq() and
the task enqueue.

Suppose there are nr_cpus pairs of ping-pong scheduling
tasks. For example, p0' and p0 are ping-pong scheduling,
so do p1' <=> p1, and p2'<=> p2. None of these tasks are
bound to any CPUs. The problem can be summarized as:
more than 1 wakers are stacked on 1 CPU, which slows down
waking up their wakees:

CPU0					CPU1				CPU2

p0'					p1' => idle			p2'

try_to_wake_up(p0)							try_to_wake_up(p2);
CPU1 = select_task_rq(p0);						CPU1 = select_task_rq(p2);
ttwu_queue(p0, CPU1);							ttwu_queue(p2, CPU1);
  __ttwu_queue_wakelist(p0, CPU1);
    WRITE_ONCE(CPU1->ttwu_pending, 1);
    __smp_call_single_queue(CPU1, p0);	=> ttwu_list->p0
					quiting cpuidle_idle_call()

									  __ttwu_queue_wakelist(p2, CPU1);
									    WRITE_ONCE(CPU1->ttwu_pending, 1);
					ttwu_list->p2->p0	<=	    __smp_call_single_queue(CPU1, p2);

p0' => idle
					sched_ttwu_pending()
					  enqueue_task(p2 and p0)

					idle => p2

					...
					p2 time slice expires
					...
									!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
								<===	!!! p2 delays the wake up of p0' !!!
									!!! causes long idle on CPU0     !!!
					p2 => p0			!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
					p0 wakes up p0'

idle => p0'

Since there are many waker/wakee pairs in the system, the chain reaction
causes many CPUs to be victims. These idle CPUs wait for their waker to
be scheduled.

Tiancheng has mentioned the above issue here[1].

[Proposal]
The root cause is that there is no strict synchronization of
select_task_rq() and the set of ttwu_pending flag among several CPUs.
And this might be by design because the scheduler prefers parallel
wakeup.

Avoid this problem indirectly. If a system is busy, and if the waker
and wakee are both short duration tasks, wake up the wakee on current CPU.

The reason is that, if the waker is a short-duration task, it might
relinquish the CPU soon, and the wakee has the chance to be scheduled.
On the other hand, if the wakee is a short duration task, putting it on
non-idle CPU would bring minimal impact to the running task. No idle
core in the system indicates that this mechanism should not inhibit
spreading the tasks if the system is not busy.

This wake up strategy can be viewed as dynamic WF_SYNC. Except that
WF_SYNC does not treat non-idle CPU as candidate CPU.

[Benchmark results]
The baseline is v6.2-rc1 tip:sched/core, on top of
Commit be06c7d02443a ("cpuidle: Fix poll_idle() noinstr annotation").
The test platform has 2 x 56C/112T and 224 CPUs in total. C-states
deeper than C1E are disabled. Turbo is disabled. CPU frequency governor
is performance.

will-it-scale
=============
case			load		baseline	compare%
context_switch1		224 groups	1.00		+1262.06%

There is a huge improvement in fast context switch test case, especially
when the number of groups equals the CPUs.

netperf
=======
case            	load    	baseline(std%)	compare%( std%)
TCP_RR          	56-threads	 1.00 (  0.86)	 -0.16 (  0.98)
TCP_RR          	112-threads	 1.00 (  0.65)	 +0.24 (  0.50)
TCP_RR          	168-threads	 1.00 (  5.87)	 +4.99 (  4.81)
TCP_RR          	224-threads	 1.00 (  4.63)	+687.45 (  3.77)
TCP_RR          	280-threads	 1.00 (  9.91)	 +0.39 ( 13.05)
TCP_RR          	336-threads	 1.00 ( 21.27)	 +0.08 ( 15.32)
TCP_RR          	392-threads	 1.00 ( 40.60)	+20.30 ( 30.95)
TCP_RR          	448-threads	 1.00 ( 29.85)	 +0.05 ( 33.18)
UDP_RR          	56-threads	 1.00 (  2.46)	 -0.19 (  2.50)
UDP_RR          	112-threads	 1.00 ( 12.59)	 +0.00 ( 12.31)
UDP_RR          	168-threads	 1.00 ( 18.55)	 +6.33 ( 62.39)
UDP_RR          	224-threads	 1.00 ( 13.31)	+131.74 ( 22.13)
UDP_RR          	280-threads	 1.00 ( 32.69)	 -0.54 ( 23.84)
UDP_RR          	336-threads	 1.00 ( 28.52)	 +0.14 ( 26.45)
UDP_RR          	392-threads	 1.00 ( 26.80)	 +0.23 ( 32.52)
UDP_RR          	448-threads	 1.00 ( 41.65)	 -0.20 ( 42.97)

There is significant 600+% improvement for TCP_RR and 100+% for UDP_RR
when the number of threads equals the CPUs.

tbench
======
case            	load    	baseline(std%)	compare%( std%)
loopback        	56-threads	 1.00 (  1.05)	 +0.56 (  0.48)
loopback        	112-threads	 1.00 (  1.04)	 +0.83 (  0.65)
loopback        	168-threads	 1.00 ( 29.60)	+37.37 ( 33.77)
loopback        	224-threads	 1.00 (  0.22)	 +0.11 (  0.02)
loopback        	280-threads	 1.00 (  0.04)	 -0.11 (  0.06)
loopback        	336-threads	 1.00 (  0.10)	 -0.11 (  0.11)
loopback        	392-threads	 1.00 (  0.42)	 -0.06 (  0.05)
loopback        	448-threads	 1.00 (  0.08)	 +0.19 (  0.07)

There is no noticeable impact on tbench. And there is run-to-run variance
in 168 threads case, with or without this patch applied. It might be
another issue and need to be investigated later.

hackbench
=========
case            	load    	baseline(std%)	compare%( std%)
process-pipe    	1-groups	 1.00 ( 11.63)	+10.24 ( 17.85)
process-sockets 	1-groups	 1.00 ( 15.36)	-17.58 ( 20.96)
threads-pipe    	1-groups	 1.00 (  2.78)	 +2.86 (  4.14)
threads-sockets 	1-groups	 1.00 (  1.44)	 -0.57 (  1.09)
process-pipe    	2-groups	 1.00 (  4.93)	 -3.48 (  8.04)
process-sockets 	2-groups	 1.00 (  2.44)	 -3.76 (  2.34)
threads-pipe    	2-groups	 1.00 (  2.26)	 +4.36 (  1.77)
threads-sockets 	2-groups	 1.00 (  2.50)	 +1.86 (  4.46)
process-pipe    	4-groups	 1.00 (  1.97)	+13.06 (  7.60)
process-sockets 	4-groups	 1.00 (  0.11)	 -0.57 (  0.66)
threads-pipe    	4-groups	 1.00 (  2.48)	 +1.90 (  3.81)
threads-sockets 	4-groups	 1.00 (  2.41)	 +0.28 (  1.78)
process-pipe    	8-groups	 1.00 (  1.45)	 +1.62 (  0.13)
process-sockets 	8-groups	 1.00 (  0.21)	 +0.05 (  0.33)
threads-pipe    	8-groups	 1.00 (  0.36)	 -1.19 (  0.85)
threads-sockets 	8-groups	 1.00 (  0.39)	 +1.03 (  0.33)

Overall there is no noticeable impact on hackbench. There is a large
run-to-run variance when the load is low, with or without this patch
applied. Similar to tbench, this issue needs to be investigated too.

schbench
========
case            	load    	baseline(std%)	compare%( std%)
normal          	1-mthreads	 1.00 (  0.53)	 -0.22 (  1.33)
normal          	2-mthreads	 1.00 (  3.04)	 -3.53 (  4.88)
normal          	4-mthreads	 1.00 (  2.28)	 +1.73 (  1.66)
normal          	8-mthreads	 1.00 (  2.18)	 -1.75 (  1.42)

There should be no impact on schbench in theory, because the default task
duration of schbench is 30 ms, which is much longer than the short task
threshold.

[Limitations/Miscellaneous]

[a]
Peter has suggested[2] comparing task duration with the cost of searching
for an idle CPU. If the latter is higher, then give up the scan, to
achieve better task affine. However, this method does not fit in the case
encountered in this patch. Because there are plenty of (fast)idle CPUs in
the system, it will not take too long to find an idle CPU. The bottleneck is
caused by the race condition mentioned above.

[b]
The short task threshold is sysctl_sched_min_granularity / 8.
According to get_update_sysctl_factor(), the sysctl_sched_min_granularity
could be 0.75 msec * 4 for SCHED_TUNABLESCALING_LOG,
or 0.75 msec * ncpus for SCHED_TUNABLESCALING_LINEAR.
Choosing 8 as the divisor is a trade-off. Thanks Honglei for pointing
this out.

[c]
SIS_SHORT leverages SIS_PROP to do better task placement. If the scan
number suggested by SIS_PROP is smaller than 60% of llc_weight, it
indicates that the util_avg% of the LLC domain is higher than 50%.
The 50% util_avg indicates a half-busy LLC domain, which makes a double
confirm with !has_idle_core, to not stack tasks if the system has idle
CPUs. System busier than this could lower its bar to choose a
compromised "idle" CPU.

[1] https://lore.kernel.org/lkml/9ed75cad-3718-356f-21ca-1b8ec601f335@linux.alibaba.com/
[2] https://lore.kernel.org/lkml/Y2O8a%2FOhk1i1l8ao@hirez.programming.kicks-ass.net/

Suggested-by: Tim Chen <tim.c.chen@intel.com>
Suggested-by: K Prateek Nayak <kprateek.nayak@amd.com>
Tested-by: kernel test robot <yujie.liu@intel.com>
Signed-off-by: Chen Yu <yu.c.chen@intel.com>
---
 kernel/sched/fair.c     | 26 ++++++++++++++++++++++++++
 kernel/sched/features.h |  1 +
 2 files changed, 27 insertions(+)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index aa16611c7263..d50097e5fcc1 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -6489,6 +6489,20 @@ static int wake_wide(struct task_struct *p)
 	return 1;
 }
 
+/*
+ * If a task switches in and then voluntarily relinquishes the
+ * CPU quickly, it is regarded as a short duration task.
+ *
+ * SIS_SHORT tries to wake up the short wakee on current CPU. This
+ * aims to avoid race condition among CPUs due to frequent context
+ * switch.
+ */
+static inline int is_short_task(struct task_struct *p)
+{
+	return sched_feat(SIS_SHORT) && p->se.dur_avg &&
+	       ((p->se.dur_avg * 8) < sysctl_sched_min_granularity);
+}
+
 /*
  * The purpose of wake_affine() is to quickly determine on which CPU we can run
  * soonest. For the purpose of speed we only consider the waking and previous
@@ -6525,6 +6539,11 @@ wake_affine_idle(int this_cpu, int prev_cpu, int sync)
 	if (available_idle_cpu(prev_cpu))
 		return prev_cpu;
 
+	/* The only running task is a short duration one. */
+	if (cpu_rq(this_cpu)->nr_running == 1 &&
+	    is_short_task(rcu_dereference(cpu_curr(this_cpu))))
+		return this_cpu;
+
 	return nr_cpumask_bits;
 }
 
@@ -6899,6 +6918,13 @@ static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, bool
 			/* overloaded LLC is unlikely to have idle cpu/core */
 			if (nr == 1)
 				return -1;
+
+			if (!has_idle_core && this == target &&
+			    (5 * nr < 3 * sd->span_weight) &&
+			    cpu_rq(target)->nr_running <= 1 &&
+			    is_short_task(p) &&
+			    is_short_task(rcu_dereference(cpu_curr(target))))
+				return target;
 		}
 	}
 
diff --git a/kernel/sched/features.h b/kernel/sched/features.h
index ee7f23c76bd3..efdc29c42161 100644
--- a/kernel/sched/features.h
+++ b/kernel/sched/features.h
@@ -62,6 +62,7 @@ SCHED_FEAT(TTWU_QUEUE, true)
  */
 SCHED_FEAT(SIS_PROP, false)
 SCHED_FEAT(SIS_UTIL, true)
+SCHED_FEAT(SIS_SHORT, true)
 
 /*
  * Issue a WARN when we do multiple update_rq_clock() calls
-- 
2.25.1

Hi Chen,

I've tested this patchset (with modification) on our Redis proxy
servers, and the results seems promising.

On 2/3/23 1:18 PM, Chen Yu wrote:
> ...
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index aa16611c7263..d50097e5fcc1 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -6489,6 +6489,20 @@ static int wake_wide(struct task_struct *p)
>   	return 1;
>   }
>   
> +/*
> + * If a task switches in and then voluntarily relinquishes the
> + * CPU quickly, it is regarded as a short duration task.
> + *
> + * SIS_SHORT tries to wake up the short wakee on current CPU. This
> + * aims to avoid race condition among CPUs due to frequent context
> + * switch.
> + */
> +static inline int is_short_task(struct task_struct *p)
> +{
> +	return sched_feat(SIS_SHORT) && p->se.dur_avg &&
> +	       ((p->se.dur_avg * 8) < sysctl_sched_min_granularity);
> +}

I changed the factor to fit into the shape of tasks in question.

	static inline int is_short_task(struct task_struct *p)
	{
		u64 dur = sysctl_sched_min_granularity / 8;

		if (!sched_feat(SIS_SHORT) || !p->se.dur_avg)
			return false;

		/*
		 * Bare tracepoint to allow dynamically changing
		 * the threshold.
		 */
		trace_sched_short_task_tp(p, &dur);

		return p->se.dur_avg < dur;
	}

I'm not sure it is the right way to provide such flexibility, but
definition of 'short' can be workload specific.

> +
>   /*
>    * The purpose of wake_affine() is to quickly determine on which CPU we can run
>    * soonest. For the purpose of speed we only consider the waking and previous
> @@ -6525,6 +6539,11 @@ wake_affine_idle(int this_cpu, int prev_cpu, int sync)
>   	if (available_idle_cpu(prev_cpu))
>   		return prev_cpu;
>   
> +	/* The only running task is a short duration one. */
> +	if (cpu_rq(this_cpu)->nr_running == 1 &&
> +	    is_short_task(rcu_dereference(cpu_curr(this_cpu))))
> +		return this_cpu;

Since proxy server handles simple data delivery, the tasks are
generally short running ones and hate task stacking which may
introduce scheduling latency (even there are only 2 short tasks
competing each other). So this part brings slight regression on
the proxy case. But I still think this is good for most cases.

Speaking of task stacking, I found wake_affine_weight() can be
much more dangerous. It chooses the less loaded one between the
prev & this cpu as a candidate, so 'small' tasks can be easily
stacked on this cpu when wake up several tasks at one time if
this cpu is unloaded. This really hurts if the 'small' tasks are
latency-sensitive, although wake_affine_weight() does the right
thing from the point of view of 'load'.

The following change greatly reduced the p99lat of Redis service
from 150ms to 0.9ms, at exactly the same throughput (QPS).

@@ -5763,6 +5787,9 @@ wake_affine_weight(struct sched_domain *sd, struct 
task_struct *p,
	s64 this_eff_load, prev_eff_load;
	unsigned long task_load;

+	if (is_short_task(p))
+		return nr_cpumask_bits;
+
	this_eff_load = cpu_load(cpu_rq(this_cpu));

	if (sync) {

I know that 'short' tasks are not necessarily 'small' tasks, e.g.
sleeping duration is small or have large weights, but this works
really well for this case. This is partly because delivering data
is memory bandwidth intensive hence prefer cache hot cpus. And I
think this is also applicable to the general purposes: do NOT let
the short running tasks suffering from cache misses caused by
migration.

Best regards,
	Abel

On 2023/2/16 20:55, Abel Wu wrote:
> Hi Chen,
> 
> I've tested this patchset (with modification) on our Redis proxy
> servers, and the results seems promising.
> 
> On 2/3/23 1:18 PM, Chen Yu wrote:
>> ...
>> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
>> index aa16611c7263..d50097e5fcc1 100644
>> --- a/kernel/sched/fair.c
>> +++ b/kernel/sched/fair.c
>> @@ -6489,6 +6489,20 @@ static int wake_wide(struct task_struct *p)
>>       return 1;
>>   }
>> +/*
>> + * If a task switches in and then voluntarily relinquishes the
>> + * CPU quickly, it is regarded as a short duration task.
>> + *
>> + * SIS_SHORT tries to wake up the short wakee on current CPU. This
>> + * aims to avoid race condition among CPUs due to frequent context
>> + * switch.
>> + */
>> +static inline int is_short_task(struct task_struct *p)
>> +{
>> +    return sched_feat(SIS_SHORT) && p->se.dur_avg &&
>> +           ((p->se.dur_avg * 8) < sysctl_sched_min_granularity);
>> +}
> 
> I changed the factor to fit into the shape of tasks in question.
> 
>      static inline int is_short_task(struct task_struct *p)
>      {
>          u64 dur = sysctl_sched_min_granularity / 8;
> 
>          if (!sched_feat(SIS_SHORT) || !p->se.dur_avg)
>              return false;
> 
>          /*
>           * Bare tracepoint to allow dynamically changing
>           * the threshold.
>           */
>          trace_sched_short_task_tp(p, &dur);
> 
>          return p->se.dur_avg < dur;
>      }
> 
> I'm not sure it is the right way to provide such flexibility, but
> definition of 'short' can be workload specific.
> 
>> +
>>   /*
>>    * The purpose of wake_affine() is to quickly determine on which CPU 
>> we can run
>>    * soonest. For the purpose of speed we only consider the waking and 
>> previous
>> @@ -6525,6 +6539,11 @@ wake_affine_idle(int this_cpu, int prev_cpu, 
>> int sync)
>>       if (available_idle_cpu(prev_cpu))
>>           return prev_cpu;
>> +    /* The only running task is a short duration one. */
>> +    if (cpu_rq(this_cpu)->nr_running == 1 &&
>> +        is_short_task(rcu_dereference(cpu_curr(this_cpu))))
>> +        return this_cpu;
> 
> Since proxy server handles simple data delivery, the tasks are
> generally short running ones and hate task stacking which may
> introduce scheduling latency (even there are only 2 short tasks
> competing each other). So this part brings slight regression on
> the proxy case. But I still think this is good for most cases.
> 
> Speaking of task stacking, I found wake_affine_weight() can be
> much more dangerous. It chooses the less loaded one between the
> prev & this cpu as a candidate, so 'small' tasks can be easily
> stacked on this cpu when wake up several tasks at one time if
> this cpu is unloaded. This really hurts if the 'small' tasks are
> latency-sensitive, although wake_affine_weight() does the right
> thing from the point of view of 'load'.
> 
> The following change greatly reduced the p99lat of Redis service
> from 150ms to 0.9ms, at exactly the same throughput (QPS).
> 
> @@ -5763,6 +5787,9 @@ wake_affine_weight(struct sched_domain *sd, struct 
> task_struct *p,
>      s64 this_eff_load, prev_eff_load;
>      unsigned long task_load;
> 
> +    if (is_short_task(p))
> +        return nr_cpumask_bits;
> +
>      this_eff_load = cpu_load(cpu_rq(this_cpu));
> 
>      if (sync) {
> 
> I know that 'short' tasks are not necessarily 'small' tasks, e.g.
> sleeping duration is small or have large weights, but this works
> really well for this case. This is partly because delivering data
> is memory bandwidth intensive hence prefer cache hot cpus. And I
> think this is also applicable to the general purposes: do NOT let
> the short running tasks suffering from cache misses caused by
> migration.
> 

Redis is a bit special. It runs quick and really sensitive on schedule 
latency. The purpose of this 'short task' feature from Yu is to mitigate 
the migration and tend to place the waking task on local cpu, this is 
somehow on the opposite side of workload such as Redis. The changes you 
did remind me of the latency-prio stuff. Maybe we can do something base 
on both the 'short task' and 'latency-prio' to make your changes more 
general. thoughts?

Thanks,
Honglei

> Best regards,
>      Abel

On 2023-02-17 at 16:35:24 +0800, Honglei Wang wrote:
> 
> 
> On 2023/2/16 20:55, Abel Wu wrote:
> > Hi Chen,
> > 
> > I've tested this patchset (with modification) on our Redis proxy
> > servers, and the results seems promising.
> > 
> > On 2/3/23 1:18 PM, Chen Yu wrote:
> > > ...
> > > diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> > > index aa16611c7263..d50097e5fcc1 100644
> > > --- a/kernel/sched/fair.c
> > > +++ b/kernel/sched/fair.c
> > > @@ -6489,6 +6489,20 @@ static int wake_wide(struct task_struct *p)
> > >       return 1;
> > >   }
> > > +/*
> > > + * If a task switches in and then voluntarily relinquishes the
> > > + * CPU quickly, it is regarded as a short duration task.
> > > + *
> > > + * SIS_SHORT tries to wake up the short wakee on current CPU. This
> > > + * aims to avoid race condition among CPUs due to frequent context
> > > + * switch.
> > > + */
> > > +static inline int is_short_task(struct task_struct *p)
> > > +{
> > > +    return sched_feat(SIS_SHORT) && p->se.dur_avg &&
> > > +           ((p->se.dur_avg * 8) < sysctl_sched_min_granularity);
> > > +}
> > 
> > I changed the factor to fit into the shape of tasks in question.
> > 
> >      static inline int is_short_task(struct task_struct *p)
> >      {
> >          u64 dur = sysctl_sched_min_granularity / 8;
> > 
> >          if (!sched_feat(SIS_SHORT) || !p->se.dur_avg)
> >              return false;
> > 
> >          /*
> >           * Bare tracepoint to allow dynamically changing
> >           * the threshold.
> >           */
> >          trace_sched_short_task_tp(p, &dur);
> > 
> >          return p->se.dur_avg < dur;
> >      }
> > 
> > I'm not sure it is the right way to provide such flexibility, but
> > definition of 'short' can be workload specific.
> > 
> > > +
> > >   /*
> > >    * The purpose of wake_affine() is to quickly determine on which
> > > CPU we can run
> > >    * soonest. For the purpose of speed we only consider the waking
> > > and previous
> > > @@ -6525,6 +6539,11 @@ wake_affine_idle(int this_cpu, int prev_cpu,
> > > int sync)
> > >       if (available_idle_cpu(prev_cpu))
> > >           return prev_cpu;
> > > +    /* The only running task is a short duration one. */
> > > +    if (cpu_rq(this_cpu)->nr_running == 1 &&
> > > +        is_short_task(rcu_dereference(cpu_curr(this_cpu))))
> > > +        return this_cpu;
> > 
> > Since proxy server handles simple data delivery, the tasks are
> > generally short running ones and hate task stacking which may
> > introduce scheduling latency (even there are only 2 short tasks
> > competing each other). So this part brings slight regression on
> > the proxy case. But I still think this is good for most cases.
> > 
> > Speaking of task stacking, I found wake_affine_weight() can be
> > much more dangerous. It chooses the less loaded one between the
> > prev & this cpu as a candidate, so 'small' tasks can be easily
> > stacked on this cpu when wake up several tasks at one time if
> > this cpu is unloaded. This really hurts if the 'small' tasks are
> > latency-sensitive, although wake_affine_weight() does the right
> > thing from the point of view of 'load'.
> > 
> > The following change greatly reduced the p99lat of Redis service
> > from 150ms to 0.9ms, at exactly the same throughput (QPS).
> > 
> > @@ -5763,6 +5787,9 @@ wake_affine_weight(struct sched_domain *sd, struct
> > task_struct *p,
> >      s64 this_eff_load, prev_eff_load;
> >      unsigned long task_load;
> > 
> > +    if (is_short_task(p))
> > +        return nr_cpumask_bits;
> > +
> >      this_eff_load = cpu_load(cpu_rq(this_cpu));
> > 
> >      if (sync) {
> > 
> > I know that 'short' tasks are not necessarily 'small' tasks, e.g.
> > sleeping duration is small or have large weights, but this works
> > really well for this case. This is partly because delivering data
> > is memory bandwidth intensive hence prefer cache hot cpus. And I
> > think this is also applicable to the general purposes: do NOT let
> > the short running tasks suffering from cache misses caused by
> > migration.
> > 
> 
> Redis is a bit special. It runs quick and really sensitive on schedule
> latency. The purpose of this 'short task' feature from Yu is to mitigate the
> migration and tend to place the waking task on local cpu, this is somehow on
> the opposite side of workload such as Redis. The changes you did remind me
> of the latency-prio stuff. Maybe we can do something base on both the 'short
> task' and 'latency-prio' to make your changes more general. thoughts?
>
Looks reasonable, I suppose you were refering to 'latency nice' proposed by
Vincent. For now I'd like to keep this patch simple enough, later we can
extend it.

thanks,
Chenyu 
> Thanks,
> Honglei
> 
> > Best regards,
> >      Abel

On 2023/2/20 12:58, Chen Yu wrote:
> On 2023-02-17 at 16:35:24 +0800, Honglei Wang wrote:
>>
>>
>> On 2023/2/16 20:55, Abel Wu wrote:
>>> Hi Chen,
>>>
>>> I've tested this patchset (with modification) on our Redis proxy
>>> servers, and the results seems promising.
>>>
>>> On 2/3/23 1:18 PM, Chen Yu wrote:
>>>> ...
>>>> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
>>>> index aa16611c7263..d50097e5fcc1 100644
>>>> --- a/kernel/sched/fair.c
>>>> +++ b/kernel/sched/fair.c
>>>> @@ -6489,6 +6489,20 @@ static int wake_wide(struct task_struct *p)
>>>>        return 1;
>>>>    }
>>>> +/*
>>>> + * If a task switches in and then voluntarily relinquishes the
>>>> + * CPU quickly, it is regarded as a short duration task.
>>>> + *
>>>> + * SIS_SHORT tries to wake up the short wakee on current CPU. This
>>>> + * aims to avoid race condition among CPUs due to frequent context
>>>> + * switch.
>>>> + */
>>>> +static inline int is_short_task(struct task_struct *p)
>>>> +{
>>>> +    return sched_feat(SIS_SHORT) && p->se.dur_avg &&
>>>> +           ((p->se.dur_avg * 8) < sysctl_sched_min_granularity);
>>>> +}
>>>
>>> I changed the factor to fit into the shape of tasks in question.
>>>
>>>       static inline int is_short_task(struct task_struct *p)
>>>       {
>>>           u64 dur = sysctl_sched_min_granularity / 8;
>>>
>>>           if (!sched_feat(SIS_SHORT) || !p->se.dur_avg)
>>>               return false;
>>>
>>>           /*
>>>            * Bare tracepoint to allow dynamically changing
>>>            * the threshold.
>>>            */
>>>           trace_sched_short_task_tp(p, &dur);
>>>
>>>           return p->se.dur_avg < dur;
>>>       }
>>>
>>> I'm not sure it is the right way to provide such flexibility, but
>>> definition of 'short' can be workload specific.
>>>
>>>> +
>>>>    /*
>>>>     * The purpose of wake_affine() is to quickly determine on which
>>>> CPU we can run
>>>>     * soonest. For the purpose of speed we only consider the waking
>>>> and previous
>>>> @@ -6525,6 +6539,11 @@ wake_affine_idle(int this_cpu, int prev_cpu,
>>>> int sync)
>>>>        if (available_idle_cpu(prev_cpu))
>>>>            return prev_cpu;
>>>> +    /* The only running task is a short duration one. */
>>>> +    if (cpu_rq(this_cpu)->nr_running == 1 &&
>>>> +        is_short_task(rcu_dereference(cpu_curr(this_cpu))))
>>>> +        return this_cpu;
>>>
>>> Since proxy server handles simple data delivery, the tasks are
>>> generally short running ones and hate task stacking which may
>>> introduce scheduling latency (even there are only 2 short tasks
>>> competing each other). So this part brings slight regression on
>>> the proxy case. But I still think this is good for most cases.
>>>
>>> Speaking of task stacking, I found wake_affine_weight() can be
>>> much more dangerous. It chooses the less loaded one between the
>>> prev & this cpu as a candidate, so 'small' tasks can be easily
>>> stacked on this cpu when wake up several tasks at one time if
>>> this cpu is unloaded. This really hurts if the 'small' tasks are
>>> latency-sensitive, although wake_affine_weight() does the right
>>> thing from the point of view of 'load'.
>>>
>>> The following change greatly reduced the p99lat of Redis service
>>> from 150ms to 0.9ms, at exactly the same throughput (QPS).
>>>
>>> @@ -5763,6 +5787,9 @@ wake_affine_weight(struct sched_domain *sd, struct
>>> task_struct *p,
>>>       s64 this_eff_load, prev_eff_load;
>>>       unsigned long task_load;
>>>
>>> +    if (is_short_task(p))
>>> +        return nr_cpumask_bits;
>>> +
>>>       this_eff_load = cpu_load(cpu_rq(this_cpu));
>>>
>>>       if (sync) {
>>>
>>> I know that 'short' tasks are not necessarily 'small' tasks, e.g.
>>> sleeping duration is small or have large weights, but this works
>>> really well for this case. This is partly because delivering data
>>> is memory bandwidth intensive hence prefer cache hot cpus. And I
>>> think this is also applicable to the general purposes: do NOT let
>>> the short running tasks suffering from cache misses caused by
>>> migration.
>>>
>>
>> Redis is a bit special. It runs quick and really sensitive on schedule
>> latency. The purpose of this 'short task' feature from Yu is to mitigate the
>> migration and tend to place the waking task on local cpu, this is somehow on
>> the opposite side of workload such as Redis. The changes you did remind me
>> of the latency-prio stuff. Maybe we can do something base on both the 'short
>> task' and 'latency-prio' to make your changes more general. thoughts?
>>
> Looks reasonable, I suppose you were refering to 'latency nice' proposed by
> Vincent. For now I'd like to keep this patch simple enough, later we can
> extend it.
> 

Yep, agree to keep this patch as is for now.

Thanks,
Honglei

> thanks,
> Chenyu

Hi Honglei,

On 2/17/23 4:35 PM, Honglei Wang wrote:
>> The following change greatly reduced the p99lat of Redis service
>> from 150ms to 0.9ms, at exactly the same throughput (QPS).
>>
>> @@ -5763,6 +5787,9 @@ wake_affine_weight(struct sched_domain *sd, 
>> struct task_struct *p,
>>      s64 this_eff_load, prev_eff_load;
>>      unsigned long task_load;
>>
>> +    if (is_short_task(p))
>> +        return nr_cpumask_bits;
>> +
>>      this_eff_load = cpu_load(cpu_rq(this_cpu));
>>
>>      if (sync) {
>>
>> I know that 'short' tasks are not necessarily 'small' tasks, e.g.
>> sleeping duration is small or have large weights, but this works
>> really well for this case. This is partly because delivering data
>> is memory bandwidth intensive hence prefer cache hot cpus. And I
>> think this is also applicable to the general purposes: do NOT let
>> the short running tasks suffering from cache misses caused by
>> migration.
>>
> 
> Redis is a bit special. It runs quick and really sensitive on schedule 
> latency. The purpose of this 'short task' feature from Yu is to mitigate 
> the migration and tend to place the waking task on local cpu, this is 
> somehow on the opposite side of workload such as Redis. The changes you 
> did remind me of the latency-prio stuff. Maybe we can do something base 
> on both the 'short task' and 'latency-prio' to make your changes more 
> general. thoughts?

I think it is more like an enhance rather than conflict. Chen Yu's patch
treats the cpus with only one short task as idle, to make idle cpu scan
more efficient. So if this cpu is such 'idle' cpu, just choose it. While
what I suggested is to ignore this cpu if it is not idle.

But as you pointed out that Redis is a bit special in the manner of
sensitive on scheduling latency, the change in wake_affine_weight() may
be inappropriate as 'weight' implies more on throughput than latency.

Best Regards,
	Abel

Hi Abel,
On 2023-02-16 at 20:55:29 +0800, Abel Wu wrote:
> Hi Chen,
> 
> I've tested this patchset (with modification) on our Redis proxy
> servers, and the results seems promising.
> 
> On 2/3/23 1:18 PM, Chen Yu wrote:
> > ...
> > diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> > index aa16611c7263..d50097e5fcc1 100644
> > --- a/kernel/sched/fair.c
> > +++ b/kernel/sched/fair.c
> > @@ -6489,6 +6489,20 @@ static int wake_wide(struct task_struct *p)
> >   	return 1;
> >   }
> > +/*
> > + * If a task switches in and then voluntarily relinquishes the
> > + * CPU quickly, it is regarded as a short duration task.
> > + *
> > + * SIS_SHORT tries to wake up the short wakee on current CPU. This
> > + * aims to avoid race condition among CPUs due to frequent context
> > + * switch.
> > + */
> > +static inline int is_short_task(struct task_struct *p)
> > +{
> > +	return sched_feat(SIS_SHORT) && p->se.dur_avg &&
> > +	       ((p->se.dur_avg * 8) < sysctl_sched_min_granularity);
> > +}
> 
> I changed the factor to fit into the shape of tasks in question.
> 
> 	static inline int is_short_task(struct task_struct *p)
> 	{
> 		u64 dur = sysctl_sched_min_granularity / 8;
> 
> 		if (!sched_feat(SIS_SHORT) || !p->se.dur_avg)
> 			return false;
> 
> 		/*
> 		 * Bare tracepoint to allow dynamically changing
> 		 * the threshold.
> 		 */
> 		trace_sched_short_task_tp(p, &dur);
> 
> 		return p->se.dur_avg < dur;
> 	}
> 
> I'm not sure it is the right way to provide such flexibility, but
> definition of 'short' can be workload specific.
> 
I'm not sure neither.
> > +
> >   /*
> >    * The purpose of wake_affine() is to quickly determine on which CPU we can run
> >    * soonest. For the purpose of speed we only consider the waking and previous
> > @@ -6525,6 +6539,11 @@ wake_affine_idle(int this_cpu, int prev_cpu, int sync)
> >   	if (available_idle_cpu(prev_cpu))
> >   		return prev_cpu;
> > +	/* The only running task is a short duration one. */
> > +	if (cpu_rq(this_cpu)->nr_running == 1 &&
> > +	    is_short_task(rcu_dereference(cpu_curr(this_cpu))))
> > +		return this_cpu;
> 
> Since proxy server handles simple data delivery, the tasks are
> generally short running ones and hate task stacking which may
> introduce scheduling latency (even there are only 2 short tasks
> competing each other). So this part brings slight regression on
> the proxy case. But I still think this is good for most cases.
> 
> Speaking of task stacking, I found wake_affine_weight() can be
> much more dangerous. It chooses the less loaded one between the
> prev & this cpu as a candidate, so 'small' tasks can be easily
> stacked on this cpu when wake up several tasks at one time if
> this cpu is unloaded. This really hurts if the 'small' tasks are
> latency-sensitive, although wake_affine_weight() does the right
> thing from the point of view of 'load'.
> 
> The following change greatly reduced the p99lat of Redis service
> from 150ms to 0.9ms, at exactly the same throughput (QPS).
> 
> @@ -5763,6 +5787,9 @@ wake_affine_weight(struct sched_domain *sd, struct
> task_struct *p,
> 	s64 this_eff_load, prev_eff_load;
> 	unsigned long task_load;
> 
> +	if (is_short_task(p))
> +		return nr_cpumask_bits;
> +
So above change wants to wake up the short task on its previous
CPU if I understand correctly.
> 	this_eff_load = cpu_load(cpu_rq(this_cpu));
> 
> 	if (sync) {
> 
> I know that 'short' tasks are not necessarily 'small' tasks, e.g.
> sleeping duration is small or have large weights, but this works
> really well for this case. This is partly because delivering data
> is memory bandwidth intensive hence prefer cache hot cpus. And I
> think this is also applicable to the general purposes: do NOT let
> the short running tasks suffering from cache misses caused by
> migration.
> 
I see. My original thought was to mitigate short task migration
as much as possible. Either waking up the task on current CPU or previous
CPU should both achieve the goal in theory. Could you please describe
a little more about how Redis proxy server was tested? Was it tested
locally or using multiple machines? I asked this because for network
benchmarks, it might be better to wake the task close to the waker(maybe
the NIC interrupt) due to hot network buffer. Anyway I will test
your change slightly changed to see the impact, and also Redis. But it
would be even better if you could provide some simple test steps I can
try locally : )

thanks,
Chenyu 
> Best regards,
> 	Abel

On 2/16/23 11:24 PM, Chen Yu wrote:
>> The following change greatly reduced the p99lat of Redis service
>> from 150ms to 0.9ms, at exactly the same throughput (QPS).
>>
>> @@ -5763,6 +5787,9 @@ wake_affine_weight(struct sched_domain *sd, struct
>> task_struct *p,
>> 	s64 this_eff_load, prev_eff_load;
>> 	unsigned long task_load;
>>
>> +	if (is_short_task(p))
>> +		return nr_cpumask_bits;
>> +
> So above change wants to wake up the short task on its previous
> CPU if I understand correctly.

Yes.

>> 	this_eff_load = cpu_load(cpu_rq(this_cpu));
>>
>> 	if (sync) {
>>
>> I know that 'short' tasks are not necessarily 'small' tasks, e.g.
>> sleeping duration is small or have large weights, but this works
>> really well for this case. This is partly because delivering data
>> is memory bandwidth intensive hence prefer cache hot cpus. And I
>> think this is also applicable to the general purposes: do NOT let
>> the short running tasks suffering from cache misses caused by
>> migration.
>>
> I see. My original thought was to mitigate short task migration
> as much as possible. Either waking up the task on current CPU or previous
> CPU should both achieve the goal in theory. Could you please describe
> a little more about how Redis proxy server was tested? Was it tested
> locally or using multiple machines? I asked this because for network
> benchmarks, it might be better to wake the task close to the waker(maybe
> the NIC interrupt) due to hot network buffer. Anyway I will test
> your change slightly changed to see the impact, and also Redis. But it
> would be even better if you could provide some simple test steps I can
> try locally : )

Sorry for missing the info. The test was done in production environment,
and what I have done is only updating the kernel in several machines
which are highly loaded, that is over 85% cpu util observed by mpstat.
Please let me know if you want any specific info.

Best,
	Abel

On 2023-02-17 at 10:44:51 +0800, Abel Wu wrote:
> On 2/16/23 11:24 PM, Chen Yu wrote:
> > > The following change greatly reduced the p99lat of Redis service
> > > from 150ms to 0.9ms, at exactly the same throughput (QPS).
> > > 
> > > @@ -5763,6 +5787,9 @@ wake_affine_weight(struct sched_domain *sd, struct
> > > task_struct *p,
> > > 	s64 this_eff_load, prev_eff_load;
> > > 	unsigned long task_load;
> > > 
> > > +	if (is_short_task(p))
> > > +		return nr_cpumask_bits;
> > > +
> > So above change wants to wake up the short task on its previous
> > CPU if I understand correctly.
> 
> Yes.
> 
> > > 	this_eff_load = cpu_load(cpu_rq(this_cpu));
> > > 
> > > 	if (sync) {
> > > 
> > > I know that 'short' tasks are not necessarily 'small' tasks, e.g.
> > > sleeping duration is small or have large weights, but this works
> > > really well for this case. This is partly because delivering data
> > > is memory bandwidth intensive hence prefer cache hot cpus. And I
> > > think this is also applicable to the general purposes: do NOT let
> > > the short running tasks suffering from cache misses caused by
> > > migration.
> > > 
> > I see. My original thought was to mitigate short task migration
> > as much as possible. Either waking up the task on current CPU or previous
> > CPU should both achieve the goal in theory. Could you please describe
> > a little more about how Redis proxy server was tested? Was it tested
> > locally or using multiple machines? I asked this because for network
> > benchmarks, it might be better to wake the task close to the waker(maybe
> > the NIC interrupt) due to hot network buffer. Anyway I will test
> > your change slightly changed to see the impact, and also Redis. But it
> > would be even better if you could provide some simple test steps I can
> > try locally : )
> 
> Sorry for missing the info. The test was done in production environment,
> and what I have done is only updating the kernel in several machines
> which are highly loaded, that is over 85% cpu util observed by mpstat.
> Please let me know if you want any specific info.
>
I've modified the code a little bit, which was inpired by your statement
"'small' tasks can be easily stacked on this cpu when wake up several tasks
at one time if this cpu is unloaded". I added extra check on wakee_flips, so
that tasks waking up too many different tasks will not be treated as 'small'
ones. That is to say, only tasks waking up each other exclusively will be
put together. So far this change has verified to keep the improvement for
netperf/will-it-scale, and I just launched the redis test to see what will
happen.

thanks,
Chenyu