Changes
-------
This is v3 of the shared runqueue patchset. This patch set is based off
of commit 88c56cfeaec4 ("sched/fair: Block nohz tick_stop when cfs
bandwidth in use") on the sched/core branch of tip.git.
v1 (RFC): https://lore.kernel.org/lkml/[email protected]/
v2: https://lore.kernel.org/lkml/[email protected]/
v2 -> v3 changes:
- Don't leave stale tasks in the lists when the SHARED_RUNQ feature is
disabled (Abel Wu)
- Use raw spin lock instead of spinlock_t (Peter)
- Fix return value from shared_runq_pick_next_task() to match the
semantics expected by newidle_balance() (Gautham, Abel)
- Fold patch __enqueue_entity() / __dequeue_entity() into previous patch
(Peter)
- Skip <= LLC domains in newidle_balance() if SHARED_RUNQ is enabled
(Peter)
- Properly support hotplug and recreating sched domains (Peter)
- Avoid unnecessary task_rq_unlock() + raw_spin_rq_lock() when src_rq ==
target_rq in shared_runq_pick_next_task() (Abel)
- Only issue list_del_init() in shared_runq_dequeue_task() if the task
is still in the list after acquiring the lock (Aaron Lu)
- Slightly change shared_runq_shard_idx() to make it more likely to keep
SMT siblings on the same bucket (Peter)
v1 -> v2 changes:
- Change name from swqueue to shared_runq (Peter)
- Shard per-LLC shared runqueues to avoid contention on scheduler-heavy
workloads (Peter)
- Pull tasks from the shared_runq in newidle_balance() rather than in
pick_next_task_fair() (Peter and Vincent)
- Rename a few functions to reflect their actual purpose. For example,
shared_runq_dequeue_task() instead of swqueue_remove_task() (Peter)
- Expose move_queued_task() from core.c rather than migrate_task_to()
(Peter)
- Properly check is_cpu_allowed() when pulling a task from a shared_runq
to ensure it can actually be migrated (Peter and Gautham)
- Dropped RFC tag
Overview
========
The scheduler must constantly strike a balance between work
conservation, and avoiding costly migrations which harm performance due
to e.g. decreased cache locality. The matter is further complicated by
the topology of the system. Migrating a task between cores on the same
LLC may be more optimal than keeping a task local to the CPU, whereas
migrating a task between LLCs or NUMA nodes may tip the balance in the
other direction.
With that in mind, while CFS is by and large mostly a work conserving
scheduler, there are certain instances where the scheduler will choose
to keep a task local to a CPU, when it would have been more optimal to
migrate it to an idle core.
An example of such a workload is the HHVM / web workload at Meta. HHVM
is a VM that JITs Hack and PHP code in service of web requests. Like
other JIT / compilation workloads, it tends to be heavily CPU bound, and
exhibit generally poor cache locality. To try and address this, we set
several debugfs (/sys/kernel/debug/sched) knobs on our HHVM workloads:
- migration_cost_ns -> 0
- latency_ns -> 20000000
- min_granularity_ns -> 10000000
- wakeup_granularity_ns -> 12000000
These knobs are intended both to encourage the scheduler to be as work
conserving as possible (migration_cost_ns -> 0), and also to keep tasks
running for relatively long time slices so as to avoid the overhead of
context switching (the other knobs). Collectively, these knobs provide a
substantial performance win; resulting in roughly a 20% improvement in
throughput. Worth noting, however, is that this improvement is _not_ at
full machine saturation.
That said, even with these knobs, we noticed that CPUs were still going
idle even when the host was overcommitted. In response, we wrote the
"shared runqueue" (SHARED_RUNQ) feature proposed in this patch set. The
idea behind SHARED_RUNQ is simple: it enables the scheduler to be more
aggressively work conserving by placing a waking task into a sharded
per-LLC FIFO queue that can be pulled from by another core in the LLC
FIFO queue which can then be pulled from before it goes idle.
With this simple change, we were able to achieve a 1 - 1.6% improvement
in throughput, as well as a small, consistent improvement in p95 and p99
latencies, in HHVM. These performance improvements were in addition to
the wins from the debugfs knobs mentioned above, and to other benchmarks
outlined below in the Results section.
Design
======
Note that the design described here reflects sharding, which is the
implementation added in the final patch of the series (following the
initial unsharded implementation added in patch 6/7). The design is
described that way in this commit summary as the benchmarks described in
the results section below all reflect a sharded SHARED_RUNQ.
The design of SHARED_RUNQ is quite simple. A shared_runq is simply a
list of struct shared_runq_shard objects, which itself is simply a
struct list_head of tasks, and a spinlock:
struct shared_runq_shard {
struct list_head list;
raw_spinlock_t lock;
} ____cacheline_aligned;
struct shared_runq {
u32 num_shards;
struct shared_runq_shard shards[];
} ____cacheline_aligned;
We create a struct shared_runq per LLC, ensuring they're in their own
cachelines to avoid false sharing between CPUs on different LLCs, and we
create a number of struct shared_runq_shard objects that are housed
there.
When a task first wakes up, it enqueues itself in the shared_runq_shard
of its current LLC at the end of enqueue_task_fair(). Enqueues only
happen if the task was not manually migrated to the current core by
select_task_rq(), and is not pinned to a specific CPU.
A core will pull a task from the shards in its LLC's shared_runq at the
beginning of newidle_balance().
Difference between SHARED_RUNQ and SIS_NODE
===========================================
In [0] Peter proposed a patch that addresses Tejun's observations that
when workqueues are targeted towards a specific LLC on his Zen2 machine
with small CCXs, that there would be significant idle time due to
select_idle_sibling() not considering anything outside of the current
LLC.
This patch (SIS_NODE) is essentially the complement to the proposal
here. SID_NODE causes waking tasks to look for idle cores in neighboring
LLCs on the same die, whereas SHARED_RUNQ causes cores about to go idle
to look for enqueued tasks. That said, in its current form, the two
features at are a different scope as SIS_NODE searches for idle cores
between LLCs, while SHARED_RUNQ enqueues tasks within a single LLC.
The patch was since removed in [1], and we compared the results to
SHARED_RUNQ (previously called "swqueue") in [2]. SIS_NODE did not
outperform SHARED_RUNQ on any of the benchmarks, so we elect to not
compare against it again for this v2 patch set.
[0]: https://lore.kernel.org/all/[email protected]/
[1]: https://lore.kernel.org/all/[email protected]/
[2]: https://lore.kernel.org/lkml/[email protected]/
Worth noting as well is that pointed out in [3] that the logic behind
including SIS_NODE in the first place should apply to SHARED_RUNQ
(meaning that e.g. very small Zen2 CPUs with only 3/4 cores per LLC
should benefit from having a single shared_runq stretch across multiple
LLCs). I drafted a patch that implements this by having a minimum LLC
size for creating a shard, and stretches a shared_runq across multiple
LLCs if they're smaller than that size, and sent it to Tejun to test on
his Zen2. Tejun reported back that SIS_NODE did not seem to make a
difference:
[3]: https://lore.kernel.org/lkml/[email protected]/
o____________o__________o
| mean | Variance |
o------------o----------o
Vanilla: | 108.84s | 0.0057 |
NO_SHARED_RUNQ: | 108.82s | 0.119s |
SHARED_RUNQ: | 108.17s | 0.038s |
SHARED_RUNQ w/ SIS_NODE: | 108.87s | 0.111s |
o------------o----------o
I similarly tried running kcompile on SHARED_RUNQ with SIS_NODE on my
7950X Zen3, but didn't see any gain relative to plain SHARED_RUNQ (though
a gain was observed relative to NO_SHARED_RUNQ, as described below).
Results
=======
Note that the motivation for the shared runqueue feature was originally
arrived at using experiments in the sched_ext framework that's currently
being proposed upstream. The ~1 - 1.6% improvement in HHVM throughput
is similarly visible using work-conserving sched_ext schedulers (even
very simple ones like global FIFO).
In both single and multi socket / CCX hosts, this can measurably improve
performance. In addition to the performance gains observed on our
internal web workloads, we also observed an improvement in common
workloads such as kernel compile and hackbench, when running shared
runqueue.
On the other hand, some workloads suffer from SHARED_RUNQ. Workloads
that hammer the runqueue hard, such as netperf UDP_RR, or schbench -L
-m 52 -p 512 -r 10 -t 1. This can be mitigated somewhat by sharding the
shared datastructures within a CCX, but it doesn't seem to eliminate all
contention in every scenario. On the positive side, it seems that
sharding does not materially harm the benchmarks run for this patch
series; and in fact seems to improve some workloads such as kernel
compile.
Note that for the kernel compile workloads below, the compilation was
done by running make -j$(nproc) built-in.a on several different types of
hosts configured with make allyesconfig on commit a27648c74210 ("afs:
Fix setting of mtime when creating a file/dir/symlink") on Linus' tree
(boost and turbo were disabled on all of these hosts when the
experiments were performed).
Finally, note that these results were from the patch set built off of
commit ebb83d84e49b ("sched/core: Avoid multiple calling
update_rq_clock() in __cfsb_csd_unthrottle()") on the sched/core branch
of tip.git for easy comparison with the v2 patch set results. The
patches in their final form from this set were rebased onto commit
88c56cfeaec4 ("sched/fair: Block nohz tick_stop when cfs bandwidth in
use") on the sched/core branch of tip.git.
=== Single-socket | 16 core / 32 thread | 2-CCX | AMD 7950X Zen4 ===
CPU max MHz: 5879.8818
CPU min MHz: 3000.0000
Command: make -j$(nproc) built-in.a
o____________o__________o
| mean | Variance |
o------------o----------o
NO_SHARED_RUNQ: | 581.95s | 2.639s |
SHARED_RUNQ: | 577.02s | 0.084s |
o------------o----------o
Takeaway: SHARED_RUNQ results in a statistically significant ~.85%
improvement over NO_SHARED_RUNQ. This suggests that enqueuing tasks in
the shared runqueue on every enqueue improves work conservation, and
thanks to sharding, does not result in contention.
Command: hackbench --loops 10000
o____________o__________o
| mean | Variance |
o------------o----------o
NO_SHARED_RUNQ: | 2.2492s | .00001s |
SHARED_RUNQ: | 2.0217s | .00065s |
o------------o----------o
Takeaway: SHARED_RUNQ in both forms performs exceptionally well compared
to NO_SHARED_RUNQ here, beating it by over 10%. This was a surprising
result given that it seems advantageous to err on the side of avoiding
migration in hackbench given that tasks are short lived in sending only
10k bytes worth of messages, but the results of the benchmark would seem
to suggest that minimizing runqueue delays is preferable.
Command:
for i in `seq 128`; do
netperf -6 -t UDP_RR -c -C -l $runtime &
done
o_______________________o
| Throughput | Variance |
o-----------------------o
NO_SHARED_RUNQ: | 25037.45 | 2243.44 |
SHARED_RUNQ: | 24952.50 | 1268.06 |
o-----------------------o
Takeaway: No statistical significance, though it is worth noting that
there is no regression for shared runqueue on the 7950X, while there is
a small regression on the Skylake and Milan hosts for SHARED_RUNQ as
described below.
=== Single-socket | 18 core / 36 thread | 1-CCX | Intel Skylake ===
CPU max MHz: 1601.0000
CPU min MHz: 800.0000
Command: make -j$(nproc) built-in.a
o____________o__________o
| mean | Variance |
o------------o----------o
NO_SHARED_RUNQ: | 1517.44s | 2.8322s |
SHARED_RUNQ: | 1516.51s | 2.9450s |
o------------o----------o
Takeaway: There's on statistically significant gain here. I observed
what I claimed was a .23% win in v2, but it appears that this is not
actually statistically significant.
Command: hackbench --loops 10000
o____________o__________o
| mean | Variance |
o------------o----------o
NO_SHARED_RUNQ: | 5.3370s | .0012s |
SHARED_RUNQ: | 5.2668s | .0033s |
o------------o----------o
Takeaway: SHARED_RUNQ results in a ~1.3% improvement over
NO_SHARED_RUNQ. Also statistically significant, but smaller than the
10+% improvement observed on the 7950X.
Command: netperf -n $(nproc) -l 60 -t TCP_RR
for i in `seq 128`; do
netperf -6 -t UDP_RR -c -C -l $runtime &
done
o_______________________o
| Throughput | Variance |
o-----------------------o
NO_SHARED_RUNQ: | 15699.32 | 377.01 |
SHARED_RUNQ: | 14966.42 | 714.13 |
o-----------------------o
Takeaway: NO_SHARED_RUNQ beats SHARED_RUNQ by ~4.6%. This result makes
sense -- the workload is very heavy on the runqueue, so enqueuing tasks
in the shared runqueue in __enqueue_entity() would intuitively result in
increased contention on the shard lock.
=== Single-socket | 72-core | 6-CCX | AMD Milan Zen3 ===
CPU max MHz: 700.0000
CPU min MHz: 700.0000
Command: make -j$(nproc) built-in.a
o____________o__________o
| mean | Variance |
o------------o----------o
NO_SHARED_RUNQ: | 1568.55s | 0.1568s |
SHARED_RUNQ: | 1568.26s | 1.2168s |
o------------o----------o
Takeaway: No statistically significant difference here. It might be
worth experimenting with work stealing in a follow-on patch set.
Command: hackbench --loops 10000
o____________o__________o
| mean | Variance |
o------------o----------o
NO_SHARED_RUNQ: | 5.2716s | .00143s |
SHARED_RUNQ: | 5.1716s | .00289s |
o------------o----------o
Takeaway: SHARED_RUNQ again wins, by about 2%.
Command: netperf -n $(nproc) -l 60 -t TCP_RR
for i in `seq 128`; do
netperf -6 -t UDP_RR -c -C -l $runtime &
done
o_______________________o
| Throughput | Variance |
o-----------------------o
NO_SHARED_RUNQ: | 17482.03 | 4675.99 |
SHARED_RUNQ: | 16697.25 | 9812.23 |
o-----------------------o
Takeaway: Similar to the Skylake runs, NO_SHARED_RUNQ still beats
SHARED_RUNQ, this time by ~4.5%. It's worth noting that in v2, the
NO_SHARED_RUNQ was only ~1.8% faster. The variance is very high here, so
the results of this benchmark should be taken with a large grain of
salt (noting that we do consistently see NO_SHARED_RUNQ on top due to
not contending on the shard lock).
Finally, let's look at how sharding affects the following schbench
incantation suggested by Chris in [4]:
schbench -L -m 52 -p 512 -r 10 -t 1
[4]: https://lore.kernel.org/lkml/[email protected]/
The TL;DR is that sharding improves things a lot, but doesn't completely
fix the problem. Here are the results from running the schbench command
on the 18 core / 36 thread single CCX, single-socket Skylake:
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
class name con-bounces contentions waittime-min waittime-max waittime-total waittime-avg acq-bounces acquisitions holdtime-min holdtime-max holdtime-total holdtime-avg
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
&shard->lock: 31510503 31510711 0.08 19.98 168932319.64 5.36 31700383 31843851 0.03 17.50 10273968.33 0.32
------------
&shard->lock 15731657 [<0000000068c0fd75>] pick_next_task_fair+0x4dd/0x510
&shard->lock 15756516 [<000000001faf84f9>] enqueue_task_fair+0x459/0x530
&shard->lock 21766 [<00000000126ec6ab>] newidle_balance+0x45a/0x650
&shard->lock 772 [<000000002886c365>] dequeue_task_fair+0x4c9/0x540
------------
&shard->lock 23458 [<00000000126ec6ab>] newidle_balance+0x45a/0x650
&shard->lock 16505108 [<000000001faf84f9>] enqueue_task_fair+0x459/0x530
&shard->lock 14981310 [<0000000068c0fd75>] pick_next_task_fair+0x4dd/0x510
&shard->lock 835 [<000000002886c365>] dequeue_task_fair+0x4c9/0x540
These results are when we create only 3 shards (16 logical cores per
shard), so the contention may be a result of overly-coarse sharding. If
we run the schbench incantation with no sharding whatsoever, we see the
following significantly worse lock stats contention:
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
class name con-bounces contentions waittime-min waittime-max waittime-total waittime-avg acq-bounces acquisitions holdtime-min holdtime-max holdtime-total holdtime-avg
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
&shard->lock: 117868635 118361486 0.09 393.01 1250954097.25 10.57 119345882 119780601 0.05 343.35 38313419.51 0.32
------------
&shard->lock 59169196 [<0000000060507011>] __enqueue_entity+0xdc/0x110
&shard->lock 59084239 [<00000000f1c67316>] __dequeue_entity+0x78/0xa0
&shard->lock 108051 [<00000000084a6193>] newidle_balance+0x45a/0x650
------------
&shard->lock 60028355 [<0000000060507011>] __enqueue_entity+0xdc/0x110
&shard->lock 119882 [<00000000084a6193>] newidle_balance+0x45a/0x650
&shard->lock 58213249 [<00000000f1c67316>] __dequeue_entity+0x78/0xa0
The contention is ~3-4x worse if we don't shard at all. This roughly
matches the fact that we had 3 shards on the first workload run above.
If we make the shards even smaller, the contention is comparably much
lower:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
class name con-bounces contentions waittime-min waittime-max waittime-total waittime-avg acq-bounces acquisitions holdtime-min holdtime-max holdtime-total holdtime-avg
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
&shard->lock: 13839849 13877596 0.08 13.23 5389564.95 0.39 46910241 48069307 0.06 16.40 16534469.35 0.34
------------
&shard->lock 3559 [<00000000ea455dcc>] newidle_balance+0x45a/0x650
&shard->lock 6992418 [<000000002266f400>] __dequeue_entity+0x78/0xa0
&shard->lock 6881619 [<000000002a62f2e0>] __enqueue_entity+0xdc/0x110
------------
&shard->lock 6640140 [<000000002266f400>] __dequeue_entity+0x78/0xa0
&shard->lock 3523 [<00000000ea455dcc>] newidle_balance+0x45a/0x650
&shard->lock 7233933 [<000000002a62f2e0>] __enqueue_entity+0xdc/0x110
Interestingly, SHARED_RUNQ performs worse than NO_SHARED_RUNQ on the schbench
benchmark on Milan as well, but we contend more on the rq lock than the
shard lock:
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
class name con-bounces contentions waittime-min waittime-max waittime-total waittime-avg acq-bounces acquisitions holdtime-min holdtime-max holdtime-total holdtime-avg
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
&rq->__lock: 9617614 9656091 0.10 79.64 69665812.00 7.21 18092700 67652829 0.11 82.38 344524858.87 5.09
-----------
&rq->__lock 6301611 [<000000003e63bf26>] task_rq_lock+0x43/0xe0
&rq->__lock 2530807 [<00000000516703f0>] __schedule+0x72/0xaa0
&rq->__lock 109360 [<0000000011be1562>] raw_spin_rq_lock_nested+0xa/0x10
&rq->__lock 178218 [<00000000c38a30f9>] sched_ttwu_pending+0x3d/0x170
-----------
&rq->__lock 3245506 [<00000000516703f0>] __schedule+0x72/0xaa0
&rq->__lock 1294355 [<00000000c38a30f9>] sched_ttwu_pending+0x3d/0x170
&rq->__lock 2837804 [<000000003e63bf26>] task_rq_lock+0x43/0xe0
&rq->__lock 1627866 [<0000000011be1562>] raw_spin_rq_lock_nested+0xa/0x10
..................................................................................................................................................................................................
&shard->lock: 7338558 7343244 0.10 35.97 7173949.14 0.98 30200858 32679623 0.08 35.59 16270584.52 0.50
------------
&shard->lock 2004142 [<00000000f8aa2c91>] __dequeue_entity+0x78/0xa0
&shard->lock 2611264 [<00000000473978cc>] newidle_balance+0x45a/0x650
&shard->lock 2727838 [<0000000028f55bb5>] __enqueue_entity+0xdc/0x110
------------
&shard->lock 2737232 [<00000000473978cc>] newidle_balance+0x45a/0x650
&shard->lock 1693341 [<00000000f8aa2c91>] __dequeue_entity+0x78/0xa0
&shard->lock 2912671 [<0000000028f55bb5>] __enqueue_entity+0xdc/0x110
...................................................................................................................................................................................................
If we look at the lock stats with SHARED_RUNQ disabled, the rq lock still
contends the most, but it's significantly less than with it enabled:
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
class name con-bounces contentions waittime-min waittime-max waittime-total waittime-avg acq-bounces acquisitions holdtime-min holdtime-max holdtime-total holdtime-avg
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
&rq->__lock: 791277 791690 0.12 110.54 4889787.63 6.18 1575996 62390275 0.13 112.66 316262440.56 5.07
-----------
&rq->__lock 263343 [<00000000516703f0>] __schedule+0x72/0xaa0
&rq->__lock 19394 [<0000000011be1562>] raw_spin_rq_lock_nested+0xa/0x10
&rq->__lock 4143 [<000000003b542e83>] __task_rq_lock+0x51/0xf0
&rq->__lock 51094 [<00000000c38a30f9>] sched_ttwu_pending+0x3d/0x170
-----------
&rq->__lock 23756 [<0000000011be1562>] raw_spin_rq_lock_nested+0xa/0x10
&rq->__lock 379048 [<00000000516703f0>] __schedule+0x72/0xaa0
&rq->__lock 677 [<000000003b542e83>] __task_rq_lock+0x51/0xf0
Worth noting is that increasing the granularity of the shards in general
improves very runqueue-heavy workloads such as netperf UDP_RR and this
schbench command, but it doesn't necessarily make a big difference for
every workload, or for sufficiently small CCXs such as the 7950X. It may
make sense to eventually allow users to control this with a debugfs
knob, but for now we'll elect to choose a default that resulted in good
performance for the benchmarks run for this patch series.
Conclusion
==========
SHARED_RUNQ in this form provides statistically significant wins for
several types of workloads, and various CPU topologies. The reason for
this is roughly the same for all workloads: SHARED_RUNQ encourages work
conservation inside of a CCX by having a CPU do an O(# per-LLC shards)
iteration over the shared_runq shards in an LLC. We could similarly do
an O(n) iteration over all of the runqueues in the current LLC when a
core is going idle, but that's quite costly (especially for larger
LLCs), and sharded SHARED_RUNQ seems to provide a performant middle
ground between doing an O(n) walk, and doing an O(1) pull from a single
per-LLC shared runq.
For the workloads above, kernel compile and hackbench were clear winners
for SHARED_RUNQ (especially in __enqueue_entity()). The reason for the
improvement in kernel compile is of course that we have a heavily
CPU-bound workload where cache locality doesn't mean much; getting a CPU
is the #1 goal. As mentioned above, while I didn't expect to see an
improvement in hackbench, the results of the benchmark suggest that
minimizing runqueue delays is preferable to optimizing for L1/L2
locality.
Not all workloads benefit from SHARED_RUNQ, however. Workloads that
hammer the runqueue hard, such as netperf UDP_RR, or schbench -L -m 52
-p 512 -r 10 -t 1, tend to run into contention on the shard locks;
especially when enqueuing tasks in __enqueue_entity(). This can be
mitigated significantly by sharding the shared datastructures within a
CCX, but it doesn't eliminate all contention, as described above.
Worth noting as well is that Gautham Shenoy ran some interesting
experiments on a few more ideas in [5], such as walking the shared_runq
on the pop path until a task is found that can be migrated to the
calling CPU. I didn't run those experiments in this patch set, but it
might be worth doing so.
[5]: https://lore.kernel.org/lkml/[email protected]/
Gautham also ran some other benchmarks in [6], which we may want to
again try on this v3, but with boost disabled.
[6]: https://lore.kernel.org/lkml/[email protected]/
Finally, while SHARED_RUNQ in this form encourages work conservation, it
of course does not guarantee it given that we don't implement any kind
of work stealing between shared_runq's. In the future, we could
potentially push CPU utilization even higher by enabling work stealing
between shared_runq's, likely between CCXs on the same NUMA node.
Originally-by: Roman Gushchin <[email protected]>
Signed-off-by: David Vernet <[email protected]>
David Vernet (7):
sched: Expose move_queued_task() from core.c
sched: Move is_cpu_allowed() into sched.h
sched: Check cpu_active() earlier in newidle_balance()
sched: Enable sched_feat callbacks on enable/disable
sched/fair: Add SHARED_RUNQ sched feature and skeleton calls
sched: Implement shared runqueue in CFS
sched: Shard per-LLC shared runqueues
include/linux/sched.h | 2 +
kernel/sched/core.c | 52 ++----
kernel/sched/debug.c | 18 ++-
kernel/sched/fair.c | 340 +++++++++++++++++++++++++++++++++++++++-
kernel/sched/features.h | 1 +
kernel/sched/sched.h | 56 ++++++-
kernel/sched/topology.c | 4 +-
7 files changed, 420 insertions(+), 53 deletions(-)
--
2.41.0
is_cpu_allowed() exists as a static inline function in core.c. The
functionality offered by is_cpu_allowed() is useful to scheduling
policies as well, e.g. to determine whether a runnable task can be
migrated to another core that would otherwise go idle.
Let's move it to sched.h.
Signed-off-by: David Vernet <[email protected]>
---
kernel/sched/core.c | 31 -------------------------------
kernel/sched/sched.h | 31 +++++++++++++++++++++++++++++++
2 files changed, 31 insertions(+), 31 deletions(-)
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 394e216b9d37..dd6412a49263 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -48,7 +48,6 @@
#include <linux/kcov.h>
#include <linux/kprobes.h>
#include <linux/llist_api.h>
-#include <linux/mmu_context.h>
#include <linux/mmzone.h>
#include <linux/mutex_api.h>
#include <linux/nmi.h>
@@ -2470,36 +2469,6 @@ static inline bool rq_has_pinned_tasks(struct rq *rq)
return rq->nr_pinned;
}
-/*
- * Per-CPU kthreads are allowed to run on !active && online CPUs, see
- * __set_cpus_allowed_ptr() and select_fallback_rq().
- */
-static inline bool is_cpu_allowed(struct task_struct *p, int cpu)
-{
- /* When not in the task's cpumask, no point in looking further. */
- if (!cpumask_test_cpu(cpu, p->cpus_ptr))
- return false;
-
- /* migrate_disabled() must be allowed to finish. */
- if (is_migration_disabled(p))
- return cpu_online(cpu);
-
- /* Non kernel threads are not allowed during either online or offline. */
- if (!(p->flags & PF_KTHREAD))
- return cpu_active(cpu) && task_cpu_possible(cpu, p);
-
- /* KTHREAD_IS_PER_CPU is always allowed. */
- if (kthread_is_per_cpu(p))
- return cpu_online(cpu);
-
- /* Regular kernel threads don't get to stay during offline. */
- if (cpu_dying(cpu))
- return false;
-
- /* But are allowed during online. */
- return cpu_online(cpu);
-}
-
/*
* This is how migration works:
*
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 69b100267fd0..88cca7cc00cf 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -44,6 +44,7 @@
#include <linux/lockdep.h>
#include <linux/minmax.h>
#include <linux/mm.h>
+#include <linux/mmu_context.h>
#include <linux/module.h>
#include <linux/mutex_api.h>
#include <linux/plist.h>
@@ -1203,6 +1204,36 @@ static inline bool is_migration_disabled(struct task_struct *p)
#endif
}
+/*
+ * Per-CPU kthreads are allowed to run on !active && online CPUs, see
+ * __set_cpus_allowed_ptr() and select_fallback_rq().
+ */
+static inline bool is_cpu_allowed(struct task_struct *p, int cpu)
+{
+ /* When not in the task's cpumask, no point in looking further. */
+ if (!cpumask_test_cpu(cpu, p->cpus_ptr))
+ return false;
+
+ /* migrate_disabled() must be allowed to finish. */
+ if (is_migration_disabled(p))
+ return cpu_online(cpu);
+
+ /* Non kernel threads are not allowed during either online or offline. */
+ if (!(p->flags & PF_KTHREAD))
+ return cpu_active(cpu) && task_cpu_possible(cpu, p);
+
+ /* KTHREAD_IS_PER_CPU is always allowed. */
+ if (kthread_is_per_cpu(p))
+ return cpu_online(cpu);
+
+ /* Regular kernel threads don't get to stay during offline. */
+ if (cpu_dying(cpu))
+ return false;
+
+ /* But are allowed during online. */
+ return cpu_online(cpu);
+}
+
DECLARE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);
#define cpu_rq(cpu) (&per_cpu(runqueues, (cpu)))
--
2.41.0
When a scheduler feature is enabled or disabled, the sched_feat_enable()
and sched_feat_disable() functions are invoked respectively for that
feature. For features that don't require resetting any state, this works
fine. However, there will be an upcoming feature called shared_runq
which needs to drain all tasks from a set of global shared runqueues in
order to avoid stale tasks from staying in the queues after the feature
has been disabled.
This patch therefore defines a new SCHED_FEAT_CALLBACK macro which
allows scheduler features to specify a callback that should be invoked
when a feature is enabled or disabled respectively. The SCHED_FEAT macro
assumes a NULL callback.
Signed-off-by: David Vernet <[email protected]>
---
kernel/sched/core.c | 4 ++--
kernel/sched/debug.c | 18 ++++++++++++++----
kernel/sched/sched.h | 16 ++++++++++------
3 files changed, 26 insertions(+), 12 deletions(-)
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index dd6412a49263..385c565da87f 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -124,12 +124,12 @@ DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);
* sysctl_sched_features, defined in sched.h, to allow constants propagation
* at compile time and compiler optimization based on features default.
*/
-#define SCHED_FEAT(name, enabled) \
+#define SCHED_FEAT_CALLBACK(name, enabled, cb) \
(1UL << __SCHED_FEAT_##name) * enabled |
const_debug unsigned int sysctl_sched_features =
#include "features.h"
0;
-#undef SCHED_FEAT
+#undef SCHED_FEAT_CALLBACK
/*
* Print a warning if need_resched is set for the given duration (if
diff --git a/kernel/sched/debug.c b/kernel/sched/debug.c
index aeeba46a096b..803dff75c56f 100644
--- a/kernel/sched/debug.c
+++ b/kernel/sched/debug.c
@@ -44,14 +44,14 @@ static unsigned long nsec_low(unsigned long long nsec)
#define SPLIT_NS(x) nsec_high(x), nsec_low(x)
-#define SCHED_FEAT(name, enabled) \
+#define SCHED_FEAT_CALLBACK(name, enabled, cb) \
#name ,
static const char * const sched_feat_names[] = {
#include "features.h"
};
-#undef SCHED_FEAT
+#undef SCHED_FEAT_CALLBACK
static int sched_feat_show(struct seq_file *m, void *v)
{
@@ -72,22 +72,32 @@ static int sched_feat_show(struct seq_file *m, void *v)
#define jump_label_key__true STATIC_KEY_INIT_TRUE
#define jump_label_key__false STATIC_KEY_INIT_FALSE
-#define SCHED_FEAT(name, enabled) \
+#define SCHED_FEAT_CALLBACK(name, enabled, cb) \
jump_label_key__##enabled ,
struct static_key sched_feat_keys[__SCHED_FEAT_NR] = {
#include "features.h"
};
-#undef SCHED_FEAT
+#undef SCHED_FEAT_CALLBACK
+
+#define SCHED_FEAT_CALLBACK(name, enabled, cb) cb,
+static const sched_feat_change_f sched_feat_cbs[__SCHED_FEAT_NR] = {
+#include "features.h"
+};
+#undef SCHED_FEAT_CALLBACK
static void sched_feat_disable(int i)
{
+ if (sched_feat_cbs[i])
+ sched_feat_cbs[i](false);
static_key_disable_cpuslocked(&sched_feat_keys[i]);
}
static void sched_feat_enable(int i)
{
+ if (sched_feat_cbs[i])
+ sched_feat_cbs[i](true);
static_key_enable_cpuslocked(&sched_feat_keys[i]);
}
#else
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 88cca7cc00cf..2631da3c8a4d 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -2065,6 +2065,8 @@ static inline void __set_task_cpu(struct task_struct *p, unsigned int cpu)
#endif
}
+#define SCHED_FEAT(name, enabled) SCHED_FEAT_CALLBACK(name, enabled, NULL)
+
/*
* Tunables that become constants when CONFIG_SCHED_DEBUG is off:
*/
@@ -2074,7 +2076,7 @@ static inline void __set_task_cpu(struct task_struct *p, unsigned int cpu)
# define const_debug const
#endif
-#define SCHED_FEAT(name, enabled) \
+#define SCHED_FEAT_CALLBACK(name, enabled, cb) \
__SCHED_FEAT_##name ,
enum {
@@ -2082,7 +2084,7 @@ enum {
__SCHED_FEAT_NR,
};
-#undef SCHED_FEAT
+#undef SCHED_FEAT_CALLBACK
#ifdef CONFIG_SCHED_DEBUG
@@ -2093,14 +2095,14 @@ enum {
extern const_debug unsigned int sysctl_sched_features;
#ifdef CONFIG_JUMP_LABEL
-#define SCHED_FEAT(name, enabled) \
+#define SCHED_FEAT_CALLBACK(name, enabled, cb) \
static __always_inline bool static_branch_##name(struct static_key *key) \
{ \
return static_key_##enabled(key); \
}
#include "features.h"
-#undef SCHED_FEAT
+#undef SCHED_FEAT_CALLBACK
extern struct static_key sched_feat_keys[__SCHED_FEAT_NR];
#define sched_feat(x) (static_branch_##x(&sched_feat_keys[__SCHED_FEAT_##x]))
@@ -2118,17 +2120,19 @@ extern struct static_key sched_feat_keys[__SCHED_FEAT_NR];
* constants propagation at compile time and compiler optimization based on
* features default.
*/
-#define SCHED_FEAT(name, enabled) \
+#define SCHED_FEAT_CALLBACK(name, enabled, cb) \
(1UL << __SCHED_FEAT_##name) * enabled |
static const_debug __maybe_unused unsigned int sysctl_sched_features =
#include "features.h"
0;
-#undef SCHED_FEAT
+#undef SCHED_FEAT_CALLBACK
#define sched_feat(x) !!(sysctl_sched_features & (1UL << __SCHED_FEAT_##x))
#endif /* SCHED_DEBUG */
+typedef void (*sched_feat_change_f)(bool enabling);
+
extern struct static_key_false sched_numa_balancing;
extern struct static_key_false sched_schedstats;
--
2.41.0
Overview
========
The scheduler must constantly strike a balance between work
conservation, and avoiding costly migrations which harm performance due
to e.g. decreased cache locality. The matter is further complicated by
the topology of the system. Migrating a task between cores on the same
LLC may be more optimal than keeping a task local to the CPU, whereas
migrating a task between LLCs or NUMA nodes may tip the balance in the
other direction.
With that in mind, while CFS is by and large mostly a work conserving
scheduler, there are certain instances where the scheduler will choose
to keep a task local to a CPU, when it would have been more optimal to
migrate it to an idle core.
An example of such a workload is the HHVM / web workload at Meta. HHVM
is a VM that JITs Hack and PHP code in service of web requests. Like
other JIT / compilation workloads, it tends to be heavily CPU bound, and
exhibit generally poor cache locality. To try and address this, we set
several debugfs (/sys/kernel/debug/sched) knobs on our HHVM workloads:
- migration_cost_ns -> 0
- latency_ns -> 20000000
- min_granularity_ns -> 10000000
- wakeup_granularity_ns -> 12000000
These knobs are intended both to encourage the scheduler to be as work
conserving as possible (migration_cost_ns -> 0), and also to keep tasks
running for relatively long time slices so as to avoid the overhead of
context switching (the other knobs). Collectively, these knobs provide a
substantial performance win; resulting in roughly a 20% improvement in
throughput. Worth noting, however, is that this improvement is _not_ at
full machine saturation.
That said, even with these knobs, we noticed that CPUs were still going
idle even when the host was overcommitted. In response, we wrote the
"shared runqueue" (SHARED_RUNQ) feature proposed in this patch set. The
idea behind SHARED_RUNQ is simple: it enables the scheduler to be more
aggressively work conserving by placing a waking task into a sharded
per-LLC FIFO queue that can be pulled from by another core in the LLC
FIFO queue which can then be pulled from before it goes idle.
With this simple change, we were able to achieve a 1 - 1.6% improvement
in throughput, as well as a small, consistent improvement in p95 and p99
latencies, in HHVM. These performance improvements were in addition to
the wins from the debugfs knobs mentioned above, and to other benchmarks
outlined below in the Results section.
Design
======
Note that the design described here reflects sharding, which will be
added in a subsequent patch. The design is described that way in this
commit summary as the benchmarks described in the results section below
all include sharded SHARED_RUNQ. The patches are not combined into one
to ease the burden of review.
The design of SHARED_RUNQ is quite simple. A shared_runq is simply a
list of struct shared_runq_shard objects, which itself is simply a
struct list_head of tasks, and a spinlock:
struct shared_runq_shard {
struct list_head list;
raw_spinlock_t lock;
} ____cacheline_aligned;
struct shared_runq {
u32 num_shards;
struct shared_runq_shard shards[];
} ____cacheline_aligned;
We create a struct shared_runq per LLC, ensuring they're in their own
cachelines to avoid false sharing between CPUs on different LLCs, and we
create a number of struct shared_runq_shard objects that are housed
there.
When a task first wakes up, it enqueues itself in the shared_runq_shard
of its current LLC at the end of enqueue_task_fair(). Enqueues only
happen if the task was not manually migrated to the current core by
select_task_rq(), and is not pinned to a specific CPU.
A core will pull a task from the shards in its LLC's shared_runq at the
beginning of newidle_balance().
Difference between SHARED_RUNQ and SIS_NODE
===========================================
In [0] Peter proposed a patch that addresses Tejun's observations that
when workqueues are targeted towards a specific LLC on his Zen2 machine
with small CCXs, that there would be significant idle time due to
select_idle_sibling() not considering anything outside of the current
LLC.
This patch (SIS_NODE) is essentially the complement to the proposal
here. SID_NODE causes waking tasks to look for idle cores in neighboring
LLCs on the same die, whereas SHARED_RUNQ causes cores about to go idle
to look for enqueued tasks. That said, in its current form, the two
features at are a different scope as SIS_NODE searches for idle cores
between LLCs, while SHARED_RUNQ enqueues tasks within a single LLC.
The patch was since removed in [1], and we compared the results to
shared_Runq (previously called "swqueue") in [2]. SIS_NODE did not
outperform SHARED_RUNQ on any of the benchmarks, so we elect to not
compare against it again for this v2 patch set.
[0]: https://lore.kernel.org/all/[email protected]/
[1]: https://lore.kernel.org/all/[email protected]/
[2]: https://lore.kernel.org/lkml/[email protected]/
Worth noting as well is that pointed out in [3] that the logic behind
including SIS_NODE in the first place should apply to SHARED_RUNQ
(meaning that e.g. very small Zen2 CPUs with only 3/4 cores per LLC
should benefit from having a single shared_runq stretch across multiple
LLCs). I drafted a patch that implements this by having a minimum LLC
size for creating a shard, and stretches a shared_runq across multiple
LLCs if they're smaller than that size, and sent it to Tejun to test on
his Zen2. Tejun reported back that SIS_NODE did not seem to make a
difference:
[3]: https://lore.kernel.org/lkml/[email protected]/
o____________o__________o
| mean | Variance |
o------------o----------o
Vanilla: | 108.84s | 0.0057 |
NO_SHARED_RUNQ: | 108.82s | 0.119s |
SHARED_RUNQ: | 108.17s | 0.038s |
SHARED_RUNQ w/ SIS_NODE: | 108.87s | 0.111s |
o------------o----------o
I similarly tried running kcompile on SHARED_RUNQ with SIS_NODE on my
7950X Zen3, but didn't see any gain relative to plain SHARED_RUNQ (though
a gain was observed relative to NO_SHARED_RUNQ, as described below).
Results
=======
Note that the motivation for the shared runqueue feature was originally
arrived at using experiments in the sched_ext framework that's currently
being proposed upstream. The ~1 - 1.6% improvement in HHVM throughput
is similarly visible using work-conserving sched_ext schedulers (even
very simple ones like global FIFO).
In both single and multi socket / CCX hosts, this can measurably improve
performance. In addition to the performance gains observed on our
internal web workloads, we also observed an improvement in common
workloads such as kernel compile and hackbench, when running shared
runqueue.
On the other hand, some workloads suffer from SHARED_RUNQ. Workloads
that hammer the runqueue hard, such as netperf UDP_RR, or schbench -L
-m 52 -p 512 -r 10 -t 1. This can be mitigated somewhat by sharding the
shared datastructures within a CCX, but it doesn't seem to eliminate all
contention in every scenario. On the positive side, it seems that
sharding does not materially harm the benchmarks run for this patch
series; and in fact seems to improve some workloads such as kernel
compile.
Note that for the kernel compile workloads below, the compilation was
done by running make -j$(nproc) built-in.a on several different types of
hosts configured with make allyesconfig on commit a27648c74210 ("afs:
Fix setting of mtime when creating a file/dir/symlink") on Linus' tree
(boost and turbo were disabled on all of these hosts when the
experiments were performed).
Finally, note that these results were from the patch set built off of
commit ebb83d84e49b ("sched/core: Avoid multiple calling
update_rq_clock() in __cfsb_csd_unthrottle()") on the sched/core branch
of tip.git for easy comparison with the v2 patch set results. The
patches in their final form from this set were rebased onto commit
88c56cfeaec4 ("sched/fair: Block nohz tick_stop when cfs bandwidth in
use").
=== Single-socket | 16 core / 32 thread | 2-CCX | AMD 7950X Zen4 ===
CPU max MHz: 5879.8818
CPU min MHz: 3000.0000
Command: make -j$(nproc) built-in.a
o____________o__________o
| mean | Variance |
o------------o----------o
NO_SHARED_RUNQ: | 581.95s | 2.639s |
SHARED_RUNQ: | 577.02s | 0.084s |
o------------o----------o
Takeaway: SHARED_RUNQ results in a statistically significant ~.85%
improvement over NO_SHARED_RUNQ. This suggests that enqueuing tasks in
the shared runqueue on every enqueue improves work conservation, and
thanks to sharding, does not result in contention.
Command: hackbench --loops 10000
o____________o__________o
| mean | Variance |
o------------o----------o
NO_SHARED_RUNQ: | 2.2492s | .00001s |
SHARED_RUNQ: | 2.0217s | .00065s |
o------------o----------o
Takeaway: SHARED_RUNQ in both forms performs exceptionally well compared
to NO_SHARED_RUNQ here, beating it by over 10%. This was a surprising
result given that it seems advantageous to err on the side of avoiding
migration in hackbench given that tasks are short lived in sending only
10k bytes worth of messages, but the results of the benchmark would seem
to suggest that minimizing runqueue delays is preferable.
Command:
for i in `seq 128`; do
netperf -6 -t UDP_RR -c -C -l $runtime &
done
o_______________________o
| Throughput | Variance |
o-----------------------o
NO_SHARED_RUNQ: | 25037.45 | 2243.44 |
SHARED_RUNQ: | 24952.50 | 1268.06 |
o-----------------------o
Takeaway: No statistical significance, though it is worth noting that
there is no regression for shared runqueue on the 7950X, while there is
a small regression on the Skylake and Milan hosts for SHARED_RUNQ as
described below.
=== Single-socket | 18 core / 36 thread | 1-CCX | Intel Skylake ===
CPU max MHz: 1601.0000
CPU min MHz: 800.0000
Command: make -j$(nproc) built-in.a
o____________o__________o
| mean | Variance |
o------------o----------o
NO_SHARED_RUNQ: | 1517.44s | 2.8322s |
SHARED_RUNQ: | 1516.51s | 2.9450s |
o------------o----------o
Takeaway: There's on statistically significant gain here. I observed
what I claimed was a .23% win in v2, but it appears that this is not
actually statistically significant.
Command: hackbench --loops 10000
o____________o__________o
| mean | Variance |
o------------o----------o
NO_SHARED_RUNQ: | 5.3370s | .0012s |
SHARED_RUNQ: | 5.2668s | .0033s |
o------------o----------o
Takeaway: SHARED_RUNQ results in a ~1.3% improvement over
NO_SHARED_RUNQ. Also statistically significant, but smaller than the
10+% improvement observed on the 7950X.
Command: netperf -n $(nproc) -l 60 -t TCP_RR
for i in `seq 128`; do
netperf -6 -t UDP_RR -c -C -l $runtime &
done
o_______________________o
| Throughput | Variance |
o-----------------------o
NO_SHARED_RUNQ: | 15699.32 | 377.01 |
SHARED_RUNQ: | 14966.42 | 714.13 |
o-----------------------o
Takeaway: NO_SHARED_RUNQ beats SHARED_RUNQ by ~4.6%. This result makes
sense -- the workload is very heavy on the runqueue, so enqueuing tasks
in the shared runqueue in __enqueue_entity() would intuitively result in
increased contention on the shard lock.
=== Single-socket | 72-core | 6-CCX | AMD Milan Zen3 ===
CPU max MHz: 700.0000
CPU min MHz: 700.0000
Command: make -j$(nproc) built-in.a
o____________o__________o
| mean | Variance |
o------------o----------o
NO_SHARED_RUNQ: | 1568.55s | 0.1568s |
SHARED_RUNQ: | 1568.26s | 1.2168s |
o------------o----------o
Takeaway: No statistically significant difference here. It might be
worth experimenting with work stealing in a follow-on patch set.
Command: hackbench --loops 10000
o____________o__________o
| mean | Variance |
o------------o----------o
NO_SHARED_RUNQ: | 5.2716s | .00143s |
SHARED_RUNQ: | 5.1716s | .00289s |
o------------o----------o
Takeaway: SHARED_RUNQ again wins, by about 2%.
Command: netperf -n $(nproc) -l 60 -t TCP_RR
for i in `seq 128`; do
netperf -6 -t UDP_RR -c -C -l $runtime &
done
o_______________________o
| Throughput | Variance |
o-----------------------o
NO_SHARED_RUNQ: | 17482.03 | 4675.99 |
SHARED_RUNQ: | 16697.25 | 9812.23 |
o-----------------------o
Takeaway: Similar to the Skylake runs, NO_SHARED_RUNQ still beats
SHARED_RUNQ, this time by ~4.5%. It's worth noting that in v2, the
NO_SHARED_RUNQ was only ~1.8% faster. The variance is very high here, so
the results of this benchmark should be taken with a large grain of
salt (noting that we do consistently see NO_SHARED_RUNQ on top due to
not contending on the shard lock).
Finally, let's look at how sharding affects the following schbench
incantation suggested by Chris in [4]:
schbench -L -m 52 -p 512 -r 10 -t 1
[4]: https://lore.kernel.org/lkml/[email protected]/
The TL;DR is that sharding improves things a lot, but doesn't completely
fix the problem. Here are the results from running the schbench command
on the 18 core / 36 thread single CCX, single-socket Skylake:
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
class name con-bounces contentions waittime-min waittime-max waittime-total waittime-avg acq-bounces acquisitions holdtime-min holdtime-max holdtime-total holdtime-avg
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
&shard->lock: 31510503 31510711 0.08 19.98 168932319.64 5.36 31700383 31843851 0.03 17.50 10273968.33 0.32
------------
&shard->lock 15731657 [<0000000068c0fd75>] pick_next_task_fair+0x4dd/0x510
&shard->lock 15756516 [<000000001faf84f9>] enqueue_task_fair+0x459/0x530
&shard->lock 21766 [<00000000126ec6ab>] newidle_balance+0x45a/0x650
&shard->lock 772 [<000000002886c365>] dequeue_task_fair+0x4c9/0x540
------------
&shard->lock 23458 [<00000000126ec6ab>] newidle_balance+0x45a/0x650
&shard->lock 16505108 [<000000001faf84f9>] enqueue_task_fair+0x459/0x530
&shard->lock 14981310 [<0000000068c0fd75>] pick_next_task_fair+0x4dd/0x510
&shard->lock 835 [<000000002886c365>] dequeue_task_fair+0x4c9/0x540
These results are when we create only 3 shards (16 logical cores per
shard), so the contention may be a result of overly-coarse sharding. If
we run the schbench incantation with no sharding whatsoever, we see the
following significantly worse lock stats contention:
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
class name con-bounces contentions waittime-min waittime-max waittime-total waittime-avg acq-bounces acquisitions holdtime-min holdtime-max holdtime-total holdtime-avg
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
&shard->lock: 117868635 118361486 0.09 393.01 1250954097.25 10.57 119345882 119780601 0.05 343.35 38313419.51 0.32
------------
&shard->lock 59169196 [<0000000060507011>] __enqueue_entity+0xdc/0x110
&shard->lock 59084239 [<00000000f1c67316>] __dequeue_entity+0x78/0xa0
&shard->lock 108051 [<00000000084a6193>] newidle_balance+0x45a/0x650
------------
&shard->lock 60028355 [<0000000060507011>] __enqueue_entity+0xdc/0x110
&shard->lock 119882 [<00000000084a6193>] newidle_balance+0x45a/0x650
&shard->lock 58213249 [<00000000f1c67316>] __dequeue_entity+0x78/0xa0
The contention is ~3-4x worse if we don't shard at all. This roughly
matches the fact that we had 3 shards on the first workload run above.
If we make the shards even smaller, the contention is comparably much
lower:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
class name con-bounces contentions waittime-min waittime-max waittime-total waittime-avg acq-bounces acquisitions holdtime-min holdtime-max holdtime-total holdtime-avg
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
&shard->lock: 13839849 13877596 0.08 13.23 5389564.95 0.39 46910241 48069307 0.06 16.40 16534469.35 0.34
------------
&shard->lock 3559 [<00000000ea455dcc>] newidle_balance+0x45a/0x650
&shard->lock 6992418 [<000000002266f400>] __dequeue_entity+0x78/0xa0
&shard->lock 6881619 [<000000002a62f2e0>] __enqueue_entity+0xdc/0x110
------------
&shard->lock 6640140 [<000000002266f400>] __dequeue_entity+0x78/0xa0
&shard->lock 3523 [<00000000ea455dcc>] newidle_balance+0x45a/0x650
&shard->lock 7233933 [<000000002a62f2e0>] __enqueue_entity+0xdc/0x110
Interestingly, SHARED_RUNQ performs worse than NO_SHARED_RUNQ on the schbench
benchmark on Milan as well, but we contend more on the rq lock than the
shard lock:
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
class name con-bounces contentions waittime-min waittime-max waittime-total waittime-avg acq-bounces acquisitions holdtime-min holdtime-max holdtime-total holdtime-avg
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
&rq->__lock: 9617614 9656091 0.10 79.64 69665812.00 7.21 18092700 67652829 0.11 82.38 344524858.87 5.09
-----------
&rq->__lock 6301611 [<000000003e63bf26>] task_rq_lock+0x43/0xe0
&rq->__lock 2530807 [<00000000516703f0>] __schedule+0x72/0xaa0
&rq->__lock 109360 [<0000000011be1562>] raw_spin_rq_lock_nested+0xa/0x10
&rq->__lock 178218 [<00000000c38a30f9>] sched_ttwu_pending+0x3d/0x170
-----------
&rq->__lock 3245506 [<00000000516703f0>] __schedule+0x72/0xaa0
&rq->__lock 1294355 [<00000000c38a30f9>] sched_ttwu_pending+0x3d/0x170
&rq->__lock 2837804 [<000000003e63bf26>] task_rq_lock+0x43/0xe0
&rq->__lock 1627866 [<0000000011be1562>] raw_spin_rq_lock_nested+0xa/0x10
..................................................................................................................................................................................................
&shard->lock: 7338558 7343244 0.10 35.97 7173949.14 0.98 30200858 32679623 0.08 35.59 16270584.52 0.50
------------
&shard->lock 2004142 [<00000000f8aa2c91>] __dequeue_entity+0x78/0xa0
&shard->lock 2611264 [<00000000473978cc>] newidle_balance+0x45a/0x650
&shard->lock 2727838 [<0000000028f55bb5>] __enqueue_entity+0xdc/0x110
------------
&shard->lock 2737232 [<00000000473978cc>] newidle_balance+0x45a/0x650
&shard->lock 1693341 [<00000000f8aa2c91>] __dequeue_entity+0x78/0xa0
&shard->lock 2912671 [<0000000028f55bb5>] __enqueue_entity+0xdc/0x110
...................................................................................................................................................................................................
If we look at the lock stats with SHARED_RUNQ disabled, the rq lock still
contends the most, but it's significantly less than with it enabled:
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
class name con-bounces contentions waittime-min waittime-max waittime-total waittime-avg acq-bounces acquisitions holdtime-min holdtime-max holdtime-total holdtime-avg
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
&rq->__lock: 791277 791690 0.12 110.54 4889787.63 6.18 1575996 62390275 0.13 112.66 316262440.56 5.07
-----------
&rq->__lock 263343 [<00000000516703f0>] __schedule+0x72/0xaa0
&rq->__lock 19394 [<0000000011be1562>] raw_spin_rq_lock_nested+0xa/0x10
&rq->__lock 4143 [<000000003b542e83>] __task_rq_lock+0x51/0xf0
&rq->__lock 51094 [<00000000c38a30f9>] sched_ttwu_pending+0x3d/0x170
-----------
&rq->__lock 23756 [<0000000011be1562>] raw_spin_rq_lock_nested+0xa/0x10
&rq->__lock 379048 [<00000000516703f0>] __schedule+0x72/0xaa0
&rq->__lock 677 [<000000003b542e83>] __task_rq_lock+0x51/0xf0
Worth noting is that increasing the granularity of the shards in general
improves very runqueue-heavy workloads such as netperf UDP_RR and this
schbench command, but it doesn't necessarily make a big difference for
every workload, or for sufficiently small CCXs such as the 7950X. It may
make sense to eventually allow users to control this with a debugfs
knob, but for now we'll elect to choose a default that resulted in good
performance for the benchmarks run for this patch series.
Conclusion
==========
SHARED_RUNQ in this form provides statistically significant wins for
several types of workloads, and various CPU topologies. The reason for
this is roughly the same for all workloads: SHARED_RUNQ encourages work
conservation inside of a CCX by having a CPU do an O(# per-LLC shards)
iteration over the shared_runq shards in an LLC. We could similarly do
an O(n) iteration over all of the runqueues in the current LLC when a
core is going idle, but that's quite costly (especially for larger
LLCs), and sharded SHARED_RUNQ seems to provide a performant middle
ground between doing an O(n) walk, and doing an O(1) pull from a single
per-LLC shared runq.
For the workloads above, kernel compile and hackbench were clear winners
for SHARED_RUNQ (especially in __enqueue_entity()). The reason for the
improvement in kernel compile is of course that we have a heavily
CPU-bound workload where cache locality doesn't mean much; getting a CPU
is the #1 goal. As mentioned above, while I didn't expect to see an
improvement in hackbench, the results of the benchmark suggest that
minimizing runqueue delays is preferable to optimizing for L1/L2
locality.
Not all workloads benefit from SHARED_RUNQ, however. Workloads that
hammer the runqueue hard, such as netperf UDP_RR, or schbench -L -m 52
-p 512 -r 10 -t 1, tend to run into contention on the shard locks;
especially when enqueuing tasks in __enqueue_entity(). This can be
mitigated significantly by sharding the shared datastructures within a
CCX, but it doesn't eliminate all contention, as described above.
Finally, while SHARED_RUNQ in this form encourages work conservation, it
of course does not guarantee it given that we don't implement any kind
of work stealing between shared_runq's. In the future, we could
potentially push CPU utilization even higher by enabling work stealing
between shared_runq's, likely between CCXs on the same NUMA node.
Originally-by: Roman Gushchin <[email protected]>
Signed-off-by: David Vernet <[email protected]>
---
include/linux/sched.h | 2 +
kernel/sched/core.c | 13 +++
kernel/sched/fair.c | 238 +++++++++++++++++++++++++++++++++++++++-
kernel/sched/sched.h | 4 +
kernel/sched/topology.c | 4 +-
5 files changed, 256 insertions(+), 5 deletions(-)
diff --git a/include/linux/sched.h b/include/linux/sched.h
index 2aab7be46f7e..8238069fd852 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -769,6 +769,8 @@ struct task_struct {
unsigned long wakee_flip_decay_ts;
struct task_struct *last_wakee;
+ struct list_head shared_runq_node;
+
/*
* recent_used_cpu is initially set as the last CPU used by a task
* that wakes affine another task. Waker/wakee relationships can
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 385c565da87f..fb7e71d3dc0a 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -4529,6 +4529,7 @@ static void __sched_fork(unsigned long clone_flags, struct task_struct *p)
#ifdef CONFIG_SMP
p->wake_entry.u_flags = CSD_TYPE_TTWU;
p->migration_pending = NULL;
+ INIT_LIST_HEAD(&p->shared_runq_node);
#endif
init_sched_mm_cid(p);
}
@@ -9764,6 +9765,18 @@ int sched_cpu_deactivate(unsigned int cpu)
return 0;
}
+void sched_update_domains(void)
+{
+ const struct sched_class *class;
+
+ update_sched_domain_debugfs();
+
+ for_each_class(class) {
+ if (class->update_domains)
+ class->update_domains();
+ }
+}
+
static void sched_rq_cpu_starting(unsigned int cpu)
{
struct rq *rq = cpu_rq(cpu);
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 9c23e3b948fc..6e740f8da578 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -139,20 +139,235 @@ static int __init setup_sched_thermal_decay_shift(char *str)
}
__setup("sched_thermal_decay_shift=", setup_sched_thermal_decay_shift);
+/**
+ * struct shared_runq - Per-LLC queue structure for enqueuing and migrating
+ * runnable tasks within an LLC.
+ *
+ * WHAT
+ * ====
+ *
+ * This structure enables the scheduler to be more aggressively work
+ * conserving, by placing waking tasks on a per-LLC FIFO queue that can then be
+ * pulled from when another core in the LLC is going to go idle.
+ *
+ * struct rq stores a pointer to its LLC's shared_runq via struct cfs_rq.
+ * Waking tasks are enqueued in the calling CPU's struct shared_runq in
+ * __enqueue_entity(), and are opportunistically pulled from the shared_runq
+ * in newidle_balance(). Tasks enqueued in a shared_runq may be scheduled prior
+ * to being pulled from the shared_runq, in which case they're simply dequeued
+ * from the shared_runq in __dequeue_entity().
+ *
+ * There is currently no task-stealing between shared_runqs in different LLCs,
+ * which means that shared_runq is not fully work conserving. This could be
+ * added at a later time, with tasks likely only being stolen across
+ * shared_runqs on the same NUMA node to avoid violating NUMA affinities.
+ *
+ * HOW
+ * ===
+ *
+ * A shared_runq is comprised of a list, and a spinlock for synchronization.
+ * Given that the critical section for a shared_runq is typically a fast list
+ * operation, and that the shared_runq is localized to a single LLC, the
+ * spinlock will typically only be contended on workloads that do little else
+ * other than hammer the runqueue.
+ *
+ * WHY
+ * ===
+ *
+ * As mentioned above, the main benefit of shared_runq is that it enables more
+ * aggressive work conservation in the scheduler. This can benefit workloads
+ * that benefit more from CPU utilization than from L1/L2 cache locality.
+ *
+ * shared_runqs are segmented across LLCs both to avoid contention on the
+ * shared_runq spinlock by minimizing the number of CPUs that could contend on
+ * it, as well as to strike a balance between work conservation, and L3 cache
+ * locality.
+ */
+struct shared_runq {
+ struct list_head list;
+ raw_spinlock_t lock;
+} ____cacheline_aligned;
+
#ifdef CONFIG_SMP
+
+static DEFINE_PER_CPU(struct shared_runq, shared_runqs);
+
+static struct shared_runq *rq_shared_runq(struct rq *rq)
+{
+ return rq->cfs.shared_runq;
+}
+
+static void shared_runq_reassign_domains(void)
+{
+ int i;
+ struct shared_runq *shared_runq;
+ struct rq *rq;
+ struct rq_flags rf;
+
+ for_each_possible_cpu(i) {
+ rq = cpu_rq(i);
+ shared_runq = &per_cpu(shared_runqs, per_cpu(sd_llc_id, i));
+
+ rq_lock(rq, &rf);
+ rq->cfs.shared_runq = shared_runq;
+ rq_unlock(rq, &rf);
+ }
+}
+
+static void __shared_runq_drain(struct shared_runq *shared_runq)
+{
+ struct task_struct *p, *tmp;
+
+ raw_spin_lock(&shared_runq->lock);
+ list_for_each_entry_safe(p, tmp, &shared_runq->list, shared_runq_node)
+ list_del_init(&p->shared_runq_node);
+ raw_spin_unlock(&shared_runq->lock);
+}
+
+static void update_domains_fair(void)
+{
+ int i;
+ struct shared_runq *shared_runq;
+
+ /* Avoid racing with SHARED_RUNQ enable / disable. */
+ lockdep_assert_cpus_held();
+
+ shared_runq_reassign_domains();
+
+ /* Ensure every core sees its updated shared_runq pointers. */
+ synchronize_rcu();
+
+ /*
+ * Drain all tasks from all shared_runq's to ensure there are no stale
+ * tasks in any prior domain runq. This can cause us to drain live
+ * tasks that would otherwise have been safe to schedule, but this
+ * isn't a practical problem given how infrequently domains are
+ * rebuilt.
+ */
+ for_each_possible_cpu(i) {
+ shared_runq = &per_cpu(shared_runqs, i);
+ __shared_runq_drain(shared_runq);
+ }
+}
+
void shared_runq_toggle(bool enabling)
-{}
+{
+ int cpu;
+
+ if (enabling)
+ return;
+
+ /* Avoid racing with hotplug. */
+ lockdep_assert_cpus_held();
+
+ /* Ensure all cores have stopped enqueueing / dequeuing tasks. */
+ synchronize_rcu();
+
+ for_each_possible_cpu(cpu) {
+ int sd_id;
+
+ sd_id = per_cpu(sd_llc_id, cpu);
+ if (cpu == sd_id)
+ __shared_runq_drain(rq_shared_runq(cpu_rq(cpu)));
+ }
+}
+
+static struct task_struct *shared_runq_pop_task(struct rq *rq)
+{
+ struct task_struct *p;
+ struct shared_runq *shared_runq;
+
+ shared_runq = rq_shared_runq(rq);
+ if (list_empty(&shared_runq->list))
+ return NULL;
+
+ raw_spin_lock(&shared_runq->lock);
+ p = list_first_entry_or_null(&shared_runq->list, struct task_struct,
+ shared_runq_node);
+ if (p && is_cpu_allowed(p, cpu_of(rq)))
+ list_del_init(&p->shared_runq_node);
+ else
+ p = NULL;
+ raw_spin_unlock(&shared_runq->lock);
+
+ return p;
+}
+
+static void shared_runq_push_task(struct rq *rq, struct task_struct *p)
+{
+ struct shared_runq *shared_runq;
+
+ shared_runq = rq_shared_runq(rq);
+ raw_spin_lock(&shared_runq->lock);
+ list_add_tail(&p->shared_runq_node, &shared_runq->list);
+ raw_spin_unlock(&shared_runq->lock);
+}
static void shared_runq_enqueue_task(struct rq *rq, struct task_struct *p)
-{}
+{
+ /*
+ * Only enqueue the task in the shared runqueue if:
+ *
+ * - SHARED_RUNQ is enabled
+ * - The task isn't pinned to a specific CPU
+ */
+ if (p->nr_cpus_allowed == 1)
+ return;
+
+ shared_runq_push_task(rq, p);
+}
static int shared_runq_pick_next_task(struct rq *rq, struct rq_flags *rf)
{
- return 0;
+ struct task_struct *p = NULL;
+ struct rq *src_rq;
+ struct rq_flags src_rf;
+ int ret = -1;
+
+ p = shared_runq_pop_task(rq);
+ if (!p)
+ return 0;
+
+ rq_unpin_lock(rq, rf);
+ raw_spin_rq_unlock(rq);
+
+ src_rq = task_rq_lock(p, &src_rf);
+
+ if (task_on_rq_queued(p) && !task_on_cpu(src_rq, p)) {
+ update_rq_clock(src_rq);
+ src_rq = move_queued_task(src_rq, &src_rf, p, cpu_of(rq));
+ ret = 1;
+ }
+
+ if (src_rq != rq) {
+ task_rq_unlock(src_rq, p, &src_rf);
+ raw_spin_rq_lock(rq);
+ } else {
+ rq_unpin_lock(rq, &src_rf);
+ raw_spin_unlock_irqrestore(&p->pi_lock, src_rf.flags);
+ }
+ rq_repin_lock(rq, rf);
+
+ return ret;
}
static void shared_runq_dequeue_task(struct task_struct *p)
-{}
+{
+ struct shared_runq *shared_runq;
+
+ if (!list_empty(&p->shared_runq_node)) {
+ shared_runq = rq_shared_runq(task_rq(p));
+ raw_spin_lock(&shared_runq->lock);
+ /*
+ * Need to double-check for the list being empty to avoid
+ * racing with the list being drained on the domain recreation
+ * or SHARED_RUNQ feature enable / disable path.
+ */
+ if (likely(!list_empty(&p->shared_runq_node)))
+ list_del_init(&p->shared_runq_node);
+ raw_spin_unlock(&shared_runq->lock);
+ }
+}
/*
* For asym packing, by default the lower numbered CPU has higher priority.
@@ -12093,6 +12308,16 @@ static int newidle_balance(struct rq *this_rq, struct rq_flags *rf)
rcu_read_lock();
sd = rcu_dereference_check_sched_domain(this_rq->sd);
+ /*
+ * Skip <= LLC domains as they likely won't have any tasks if the
+ * shared runq is empty.
+ */
+ if (sched_feat(SHARED_RUNQ)) {
+ sd = rcu_dereference(*this_cpu_ptr(&sd_llc));
+ if (likely(sd))
+ sd = sd->parent;
+ }
+
if (!READ_ONCE(this_rq->rd->overload) ||
(sd && this_rq->avg_idle < sd->max_newidle_lb_cost)) {
@@ -12969,6 +13194,7 @@ DEFINE_SCHED_CLASS(fair) = {
.task_dead = task_dead_fair,
.set_cpus_allowed = set_cpus_allowed_common,
+ .update_domains = update_domains_fair,
#endif
.task_tick = task_tick_fair,
@@ -13035,6 +13261,7 @@ __init void init_sched_fair_class(void)
{
#ifdef CONFIG_SMP
int i;
+ struct shared_runq *shared_runq;
for_each_possible_cpu(i) {
zalloc_cpumask_var_node(&per_cpu(load_balance_mask, i), GFP_KERNEL, cpu_to_node(i));
@@ -13044,6 +13271,9 @@ __init void init_sched_fair_class(void)
INIT_CSD(&cpu_rq(i)->cfsb_csd, __cfsb_csd_unthrottle, cpu_rq(i));
INIT_LIST_HEAD(&cpu_rq(i)->cfsb_csd_list);
#endif
+ shared_runq = &per_cpu(shared_runqs, i);
+ INIT_LIST_HEAD(&shared_runq->list);
+ raw_spin_lock_init(&shared_runq->lock);
}
open_softirq(SCHED_SOFTIRQ, run_rebalance_domains);
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index a484bb527ee4..3665dd935649 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -487,9 +487,11 @@ extern int sched_group_set_idle(struct task_group *tg, long idle);
#ifdef CONFIG_SMP
extern void set_task_rq_fair(struct sched_entity *se,
struct cfs_rq *prev, struct cfs_rq *next);
+extern void sched_update_domains(void);
#else /* !CONFIG_SMP */
static inline void set_task_rq_fair(struct sched_entity *se,
struct cfs_rq *prev, struct cfs_rq *next) { }
+static inline void sched_update_domains(void) {}
#endif /* CONFIG_SMP */
#endif /* CONFIG_FAIR_GROUP_SCHED */
@@ -578,6 +580,7 @@ struct cfs_rq {
#endif
#ifdef CONFIG_SMP
+ struct shared_runq *shared_runq;
/*
* CFS load tracking
*/
@@ -2282,6 +2285,7 @@ struct sched_class {
void (*rq_offline)(struct rq *rq);
struct rq *(*find_lock_rq)(struct task_struct *p, struct rq *rq);
+ void (*update_domains)(void);
#endif
void (*task_tick)(struct rq *rq, struct task_struct *p, int queued);
diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c
index 05a5bc678c08..8aaf644d4f2c 100644
--- a/kernel/sched/topology.c
+++ b/kernel/sched/topology.c
@@ -2576,6 +2576,8 @@ int __init sched_init_domains(const struct cpumask *cpu_map)
doms_cur = &fallback_doms;
cpumask_and(doms_cur[0], cpu_map, housekeeping_cpumask(HK_TYPE_DOMAIN));
err = build_sched_domains(doms_cur[0], NULL);
+ if (!err)
+ sched_update_domains();
return err;
}
@@ -2741,7 +2743,7 @@ void partition_sched_domains_locked(int ndoms_new, cpumask_var_t doms_new[],
dattr_cur = dattr_new;
ndoms_cur = ndoms_new;
- update_sched_domain_debugfs();
+ sched_update_domains();
}
/*
--
2.41.0
The SHARED_RUNQ scheduler feature creates a FIFO queue per LLC that
tasks are put into on enqueue, and pulled from when a core in that LLC
would otherwise go idle. For CPUs with large LLCs, this can sometimes
cause significant contention, as illustrated in [0].
[0]: https://lore.kernel.org/all/[email protected]/
So as to try and mitigate this contention, we can instead shard the
per-LLC runqueue into multiple per-LLC shards.
While this doesn't outright prevent all contention, it does somewhat mitigate it.
For example, if we run the following schbench command which does almost
nothing other than pound the runqueue:
schbench -L -m 52 -p 512 -r 10 -t 1
we observe with lockstats that sharding significantly decreases
contention.
3 shards:
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
class name con-bounces contentions waittime-min waittime-max waittime-total waittime-avg acq-bounces acquisitions holdtime-min holdtime-max holdtime-total holdtime-avg
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
&shard->lock: 31510503 31510711 0.08 19.98 168932319.64 5.36 31700383 31843851 0.03 17.50 10273968.33 0.32
------------
&shard->lock 15731657 [<0000000068c0fd75>] pick_next_task_fair+0x4dd/0x510
&shard->lock 15756516 [<000000001faf84f9>] enqueue_task_fair+0x459/0x530
&shard->lock 21766 [<00000000126ec6ab>] newidle_balance+0x45a/0x650
&shard->lock 772 [<000000002886c365>] dequeue_task_fair+0x4c9/0x540
------------
&shard->lock 23458 [<00000000126ec6ab>] newidle_balance+0x45a/0x650
&shard->lock 16505108 [<000000001faf84f9>] enqueue_task_fair+0x459/0x530
&shard->lock 14981310 [<0000000068c0fd75>] pick_next_task_fair+0x4dd/0x510
&shard->lock 835 [<000000002886c365>] dequeue_task_fair+0x4c9/0x540
No sharding:
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
class name con-bounces contentions waittime-min waittime-max waittime-total waittime-avg acq-bounces acquisitions holdtime-min holdtime-max holdtime-total holdtime-avg
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
&shard->lock: 117868635 118361486 0.09 393.01 1250954097.25 10.57 119345882 119780601 0.05 343.35 38313419.51 0.32
------------
&shard->lock 59169196 [<0000000060507011>] __enqueue_entity+0xdc/0x110
&shard->lock 59084239 [<00000000f1c67316>] __dequeue_entity+0x78/0xa0
&shard->lock 108051 [<00000000084a6193>] newidle_balance+0x45a/0x650
------------
&shard->lock 60028355 [<0000000060507011>] __enqueue_entity+0xdc/0x110
&shard->lock 119882 [<00000000084a6193>] newidle_balance+0x45a/0x650
&shard->lock 58213249 [<00000000f1c67316>] __dequeue_entity+0x78/0xa0
The contention is ~3-4x worse if we don't shard at all. This roughly
matches the fact that we had 3 shards on the host where this was
collected. This could be addressed in future patch sets by adding a
debugfs knob to control the sharding granularity. If we make the shards
even smaller (what's in this patch, i.e. a size of 6), the contention
goes away almost entirely:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
class name con-bounces contentions waittime-min waittime-max waittime-total waittime-avg acq-bounces acquisitions holdtime-min holdtime-max holdtime-total holdtime-avg
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
&shard->lock: 13839849 13877596 0.08 13.23 5389564.95 0.39 46910241 48069307 0.06 16.40 16534469.35 0.34
------------
&shard->lock 3559 [<00000000ea455dcc>] newidle_balance+0x45a/0x650
&shard->lock 6992418 [<000000002266f400>] __dequeue_entity+0x78/0xa0
&shard->lock 6881619 [<000000002a62f2e0>] __enqueue_entity+0xdc/0x110
------------
&shard->lock 6640140 [<000000002266f400>] __dequeue_entity+0x78/0xa0
&shard->lock 3523 [<00000000ea455dcc>] newidle_balance+0x45a/0x650
&shard->lock 7233933 [<000000002a62f2e0>] __enqueue_entity+0xdc/0x110
Interestingly, SHARED_RUNQ performs worse than NO_SHARED_RUNQ on the schbench
benchmark on Milan, but we contend even more on the rq lock:
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
class name con-bounces contentions waittime-min waittime-max waittime-total waittime-avg acq-bounces acquisitions holdtime-min holdtime-max holdtime-total holdtime-avg
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
&rq->__lock: 9617614 9656091 0.10 79.64 69665812.00 7.21 18092700 67652829 0.11 82.38 344524858.87 5.09
-----------
&rq->__lock 6301611 [<000000003e63bf26>] task_rq_lock+0x43/0xe0
&rq->__lock 2530807 [<00000000516703f0>] __schedule+0x72/0xaa0
&rq->__lock 109360 [<0000000011be1562>] raw_spin_rq_lock_nested+0xa/0x10
&rq->__lock 178218 [<00000000c38a30f9>] sched_ttwu_pending+0x3d/0x170
-----------
&rq->__lock 3245506 [<00000000516703f0>] __schedule+0x72/0xaa0
&rq->__lock 1294355 [<00000000c38a30f9>] sched_ttwu_pending+0x3d/0x170
&rq->__lock 2837804 [<000000003e63bf26>] task_rq_lock+0x43/0xe0
&rq->__lock 1627866 [<0000000011be1562>] raw_spin_rq_lock_nested+0xa/0x10
..................................................................................................................................................................................................
&shard->lock: 7338558 7343244 0.10 35.97 7173949.14 0.98 30200858 32679623 0.08 35.59 16270584.52 0.50
------------
&shard->lock 2004142 [<00000000f8aa2c91>] __dequeue_entity+0x78/0xa0
&shard->lock 2611264 [<00000000473978cc>] newidle_balance+0x45a/0x650
&shard->lock 2727838 [<0000000028f55bb5>] __enqueue_entity+0xdc/0x110
------------
&shard->lock 2737232 [<00000000473978cc>] newidle_balance+0x45a/0x650
&shard->lock 1693341 [<00000000f8aa2c91>] __dequeue_entity+0x78/0xa0
&shard->lock 2912671 [<0000000028f55bb5>] __enqueue_entity+0xdc/0x110
...................................................................................................................................................................................................
If we look at the lock stats with SHARED_RUNQ disabled, the rq lock still
contends the most, but it's significantly less than with it enabled:
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
class name con-bounces contentions waittime-min waittime-max waittime-total waittime-avg acq-bounces acquisitions holdtime-min holdtime-max holdtime-total holdtime-avg
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
&rq->__lock: 791277 791690 0.12 110.54 4889787.63 6.18 1575996 62390275 0.13 112.66 316262440.56 5.07
-----------
&rq->__lock 263343 [<00000000516703f0>] __schedule+0x72/0xaa0
&rq->__lock 19394 [<0000000011be1562>] raw_spin_rq_lock_nested+0xa/0x10
&rq->__lock 4143 [<000000003b542e83>] __task_rq_lock+0x51/0xf0
&rq->__lock 51094 [<00000000c38a30f9>] sched_ttwu_pending+0x3d/0x170
-----------
&rq->__lock 23756 [<0000000011be1562>] raw_spin_rq_lock_nested+0xa/0x10
&rq->__lock 379048 [<00000000516703f0>] __schedule+0x72/0xaa0
&rq->__lock 677 [<000000003b542e83>] __task_rq_lock+0x51/0xf0
&rq->__lock 47962 [<00000000c38a30f9>] sched_ttwu_pending+0x3d/0x170
In general, the takeaway here is that sharding does help with
contention, but it's not necessarily one size fits all, and it's
workload dependent. For now, let's include sharding to try and avoid
contention, and because it doesn't seem to regress CPUs that don't need
it such as the AMD 7950X.
Suggested-by: Peter Zijlstra <[email protected]>
Signed-off-by: David Vernet <[email protected]>
---
kernel/sched/fair.c | 149 ++++++++++++++++++++++++++++++-------------
kernel/sched/sched.h | 3 +-
2 files changed, 108 insertions(+), 44 deletions(-)
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 6e740f8da578..d67d86d3bfdf 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -143,19 +143,27 @@ __setup("sched_thermal_decay_shift=", setup_sched_thermal_decay_shift);
* struct shared_runq - Per-LLC queue structure for enqueuing and migrating
* runnable tasks within an LLC.
*
+ * struct shared_runq_shard - A structure containing a task list and a spinlock
+ * for a subset of cores in a struct shared_runq.
+ *
* WHAT
* ====
*
* This structure enables the scheduler to be more aggressively work
- * conserving, by placing waking tasks on a per-LLC FIFO queue that can then be
- * pulled from when another core in the LLC is going to go idle.
+ * conserving, by placing waking tasks on a per-LLC FIFO queue shard that can
+ * then be pulled from when another core in the LLC is going to go idle.
+ *
+ * struct rq stores two pointers in its struct cfs_rq:
+ *
+ * 1. The per-LLC struct shared_runq which contains one or more shards of
+ * enqueued tasks.
*
- * struct rq stores a pointer to its LLC's shared_runq via struct cfs_rq.
- * Waking tasks are enqueued in the calling CPU's struct shared_runq in
- * __enqueue_entity(), and are opportunistically pulled from the shared_runq
- * in newidle_balance(). Tasks enqueued in a shared_runq may be scheduled prior
- * to being pulled from the shared_runq, in which case they're simply dequeued
- * from the shared_runq in __dequeue_entity().
+ * 2. The shard inside of the per-LLC struct shared_runq which contains the
+ * list of runnable tasks for that shard.
+ *
+ * Waking tasks are enqueued in the calling CPU's struct shared_runq_shard in
+ * __enqueue_entity(), and are opportunistically pulled from the shared_runq in
+ * newidle_balance(). Pulling from shards is an O(# shards) operation.
*
* There is currently no task-stealing between shared_runqs in different LLCs,
* which means that shared_runq is not fully work conserving. This could be
@@ -165,11 +173,12 @@ __setup("sched_thermal_decay_shift=", setup_sched_thermal_decay_shift);
* HOW
* ===
*
- * A shared_runq is comprised of a list, and a spinlock for synchronization.
- * Given that the critical section for a shared_runq is typically a fast list
- * operation, and that the shared_runq is localized to a single LLC, the
- * spinlock will typically only be contended on workloads that do little else
- * other than hammer the runqueue.
+ * A struct shared_runq_shard is comprised of a list, and a spinlock for
+ * synchronization. Given that the critical section for a shared_runq is
+ * typically a fast list operation, and that the shared_runq_shard is localized
+ * to a subset of cores on a single LLC (plus other cores in the LLC that pull
+ * from the shard in newidle_balance()), the spinlock will typically only be
+ * contended on workloads that do little else other than hammer the runqueue.
*
* WHY
* ===
@@ -183,11 +192,21 @@ __setup("sched_thermal_decay_shift=", setup_sched_thermal_decay_shift);
* it, as well as to strike a balance between work conservation, and L3 cache
* locality.
*/
-struct shared_runq {
+struct shared_runq_shard {
struct list_head list;
raw_spinlock_t lock;
} ____cacheline_aligned;
+/* This would likely work better as a configurable knob via debugfs */
+#define SHARED_RUNQ_SHARD_SZ 6
+#define SHARED_RUNQ_MAX_SHARDS \
+ ((NR_CPUS / SHARED_RUNQ_SHARD_SZ) + (NR_CPUS % SHARED_RUNQ_SHARD_SZ != 0))
+
+struct shared_runq {
+ unsigned int num_shards;
+ struct shared_runq_shard shards[SHARED_RUNQ_MAX_SHARDS];
+} ____cacheline_aligned;
+
#ifdef CONFIG_SMP
static DEFINE_PER_CPU(struct shared_runq, shared_runqs);
@@ -197,31 +216,61 @@ static struct shared_runq *rq_shared_runq(struct rq *rq)
return rq->cfs.shared_runq;
}
+static struct shared_runq_shard *rq_shared_runq_shard(struct rq *rq)
+{
+ return rq->cfs.shard;
+}
+
+static int shared_runq_shard_idx(const struct shared_runq *runq, int cpu)
+{
+ return (cpu >> 1) % runq->num_shards;
+}
+
static void shared_runq_reassign_domains(void)
{
int i;
struct shared_runq *shared_runq;
struct rq *rq;
struct rq_flags rf;
+ unsigned int num_shards, shard_idx;
+
+ for_each_possible_cpu(i) {
+ if (per_cpu(sd_llc_id, i) == i) {
+ shared_runq = &per_cpu(shared_runqs, per_cpu(sd_llc_id, i));
+
+ num_shards = per_cpu(sd_llc_size, i) / SHARED_RUNQ_SHARD_SZ;
+ if (per_cpu(sd_llc_size, i) % SHARED_RUNQ_SHARD_SZ)
+ num_shards++;
+ shared_runq->num_shards = num_shards;
+ }
+ }
for_each_possible_cpu(i) {
rq = cpu_rq(i);
shared_runq = &per_cpu(shared_runqs, per_cpu(sd_llc_id, i));
+ shard_idx = shared_runq_shard_idx(shared_runq, i);
rq_lock(rq, &rf);
rq->cfs.shared_runq = shared_runq;
+ rq->cfs.shard = &shared_runq->shards[shard_idx];
rq_unlock(rq, &rf);
}
}
static void __shared_runq_drain(struct shared_runq *shared_runq)
{
- struct task_struct *p, *tmp;
+ unsigned int i;
- raw_spin_lock(&shared_runq->lock);
- list_for_each_entry_safe(p, tmp, &shared_runq->list, shared_runq_node)
- list_del_init(&p->shared_runq_node);
- raw_spin_unlock(&shared_runq->lock);
+ for (i = 0; i < shared_runq->num_shards; i++) {
+ struct shared_runq_shard *shard;
+ struct task_struct *p, *tmp;
+
+ shard = &shared_runq->shards[i];
+ raw_spin_lock(&shard->lock);
+ list_for_each_entry_safe(p, tmp, &shard->list, shared_runq_node)
+ list_del_init(&p->shared_runq_node);
+ raw_spin_unlock(&shard->lock);
+ }
}
static void update_domains_fair(void)
@@ -272,35 +321,32 @@ void shared_runq_toggle(bool enabling)
}
}
-static struct task_struct *shared_runq_pop_task(struct rq *rq)
+static struct task_struct *
+shared_runq_pop_task(struct shared_runq_shard *shard, int target)
{
struct task_struct *p;
- struct shared_runq *shared_runq;
- shared_runq = rq_shared_runq(rq);
- if (list_empty(&shared_runq->list))
+ if (list_empty(&shard->list))
return NULL;
- raw_spin_lock(&shared_runq->lock);
- p = list_first_entry_or_null(&shared_runq->list, struct task_struct,
+ raw_spin_lock(&shard->lock);
+ p = list_first_entry_or_null(&shard->list, struct task_struct,
shared_runq_node);
- if (p && is_cpu_allowed(p, cpu_of(rq)))
+ if (p && is_cpu_allowed(p, target))
list_del_init(&p->shared_runq_node);
else
p = NULL;
- raw_spin_unlock(&shared_runq->lock);
+ raw_spin_unlock(&shard->lock);
return p;
}
-static void shared_runq_push_task(struct rq *rq, struct task_struct *p)
+static void shared_runq_push_task(struct shared_runq_shard *shard,
+ struct task_struct *p)
{
- struct shared_runq *shared_runq;
-
- shared_runq = rq_shared_runq(rq);
- raw_spin_lock(&shared_runq->lock);
- list_add_tail(&p->shared_runq_node, &shared_runq->list);
- raw_spin_unlock(&shared_runq->lock);
+ raw_spin_lock(&shard->lock);
+ list_add_tail(&p->shared_runq_node, &shard->list);
+ raw_spin_unlock(&shard->lock);
}
static void shared_runq_enqueue_task(struct rq *rq, struct task_struct *p)
@@ -314,7 +360,7 @@ static void shared_runq_enqueue_task(struct rq *rq, struct task_struct *p)
if (p->nr_cpus_allowed == 1)
return;
- shared_runq_push_task(rq, p);
+ shared_runq_push_task(rq_shared_runq_shard(rq), p);
}
static int shared_runq_pick_next_task(struct rq *rq, struct rq_flags *rf)
@@ -322,9 +368,22 @@ static int shared_runq_pick_next_task(struct rq *rq, struct rq_flags *rf)
struct task_struct *p = NULL;
struct rq *src_rq;
struct rq_flags src_rf;
+ struct shared_runq *shared_runq;
+ struct shared_runq_shard *shard;
+ u32 i, starting_idx, curr_idx, num_shards;
int ret = -1;
- p = shared_runq_pop_task(rq);
+ shared_runq = rq_shared_runq(rq);
+ num_shards = shared_runq->num_shards;
+ starting_idx = shared_runq_shard_idx(shared_runq, cpu_of(rq));
+ for (i = 0; i < num_shards; i++) {
+ curr_idx = (starting_idx + i) % num_shards;
+ shard = &shared_runq->shards[curr_idx];
+
+ p = shared_runq_pop_task(shard, cpu_of(rq));
+ if (p)
+ break;
+ }
if (!p)
return 0;
@@ -353,11 +412,11 @@ static int shared_runq_pick_next_task(struct rq *rq, struct rq_flags *rf)
static void shared_runq_dequeue_task(struct task_struct *p)
{
- struct shared_runq *shared_runq;
+ struct shared_runq_shard *shard;
if (!list_empty(&p->shared_runq_node)) {
- shared_runq = rq_shared_runq(task_rq(p));
- raw_spin_lock(&shared_runq->lock);
+ shard = rq_shared_runq_shard(task_rq(p));
+ raw_spin_lock(&shard->lock);
/*
* Need to double-check for the list being empty to avoid
* racing with the list being drained on the domain recreation
@@ -365,7 +424,7 @@ static void shared_runq_dequeue_task(struct task_struct *p)
*/
if (likely(!list_empty(&p->shared_runq_node)))
list_del_init(&p->shared_runq_node);
- raw_spin_unlock(&shared_runq->lock);
+ raw_spin_unlock(&shard->lock);
}
}
@@ -13260,8 +13319,9 @@ void show_numa_stats(struct task_struct *p, struct seq_file *m)
__init void init_sched_fair_class(void)
{
#ifdef CONFIG_SMP
- int i;
+ int i, j;
struct shared_runq *shared_runq;
+ struct shared_runq_shard *shard;
for_each_possible_cpu(i) {
zalloc_cpumask_var_node(&per_cpu(load_balance_mask, i), GFP_KERNEL, cpu_to_node(i));
@@ -13272,8 +13332,11 @@ __init void init_sched_fair_class(void)
INIT_LIST_HEAD(&cpu_rq(i)->cfsb_csd_list);
#endif
shared_runq = &per_cpu(shared_runqs, i);
- INIT_LIST_HEAD(&shared_runq->list);
- raw_spin_lock_init(&shared_runq->lock);
+ for (j = 0; j < SHARED_RUNQ_MAX_SHARDS; j++) {
+ shard = &shared_runq->shards[j];
+ INIT_LIST_HEAD(&shard->list);
+ raw_spin_lock_init(&shard->lock);
+ }
}
open_softirq(SCHED_SOFTIRQ, run_rebalance_domains);
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 3665dd935649..b504f8f4416b 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -580,7 +580,8 @@ struct cfs_rq {
#endif
#ifdef CONFIG_SMP
- struct shared_runq *shared_runq;
+ struct shared_runq *shared_runq;
+ struct shared_runq_shard *shard;
/*
* CFS load tracking
*/
--
2.41.0
For certain workloads in CFS, CPU utilization is of the upmost
importance. For example, at Meta, our main web workload benefits from a
1 - 1.5% improvement in RPS, and a 1 - 2% improvement in p99 latency,
when CPU utilization is pushed as high as possible.
This is likely something that would be useful for any workload with long
slices, or for which avoiding migration is unlikely to result in
improved cache locality.
We will soon be enabling more aggressive load balancing via a new
feature called shared_runq, which places tasks into a FIFO queue in the
__enqueue_entity(), wakeup path, and then opportunistically dequeues
them in newidle_balance(). We don't want to enable the feature by
default, so this patch defines and declares a new scheduler feature
called SHARED_RUNQ which is disabled by default.
A set of future patches will implement these functions, and enable
shared_runq for both single and multi socket / CCX architectures.
Originally-by: Roman Gushchin <[email protected]>
Signed-off-by: David Vernet <[email protected]>
---
kernel/sched/fair.c | 34 ++++++++++++++++++++++++++++++++++
kernel/sched/features.h | 2 ++
kernel/sched/sched.h | 1 +
3 files changed, 37 insertions(+)
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index eb15d6f46479..9c23e3b948fc 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -140,6 +140,20 @@ static int __init setup_sched_thermal_decay_shift(char *str)
__setup("sched_thermal_decay_shift=", setup_sched_thermal_decay_shift);
#ifdef CONFIG_SMP
+void shared_runq_toggle(bool enabling)
+{}
+
+static void shared_runq_enqueue_task(struct rq *rq, struct task_struct *p)
+{}
+
+static int shared_runq_pick_next_task(struct rq *rq, struct rq_flags *rf)
+{
+ return 0;
+}
+
+static void shared_runq_dequeue_task(struct task_struct *p)
+{}
+
/*
* For asym packing, by default the lower numbered CPU has higher priority.
*/
@@ -162,6 +176,15 @@ int __weak arch_asym_cpu_priority(int cpu)
* (default: ~5%)
*/
#define capacity_greater(cap1, cap2) ((cap1) * 1024 > (cap2) * 1078)
+#else
+void shared_runq_toggle(bool enabling)
+{}
+
+static void shared_runq_enqueue_task(struct rq *rq, struct task_struct *p)
+{}
+
+static void shared_runq_dequeue_task(struct task_struct *p)
+{}
#endif
#ifdef CONFIG_CFS_BANDWIDTH
@@ -642,11 +665,15 @@ static inline bool __entity_less(struct rb_node *a, const struct rb_node *b)
*/
static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
+ if (sched_feat(SHARED_RUNQ) && entity_is_task(se))
+ shared_runq_enqueue_task(rq_of(cfs_rq), task_of(se));
rb_add_cached(&se->run_node, &cfs_rq->tasks_timeline, __entity_less);
}
static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
+ if (sched_feat(SHARED_RUNQ) && entity_is_task(se))
+ shared_runq_dequeue_task(task_of(se));
rb_erase_cached(&se->run_node, &cfs_rq->tasks_timeline);
}
@@ -12043,6 +12070,12 @@ static int newidle_balance(struct rq *this_rq, struct rq_flags *rf)
if (!cpu_active(this_cpu))
return 0;
+ if (sched_feat(SHARED_RUNQ)) {
+ pulled_task = shared_runq_pick_next_task(this_rq, rf);
+ if (pulled_task)
+ return pulled_task;
+ }
+
/*
* We must set idle_stamp _before_ calling idle_balance(), such that we
* measure the duration of idle_balance() as idle time.
@@ -12543,6 +12576,7 @@ static void attach_task_cfs_rq(struct task_struct *p)
static void switched_from_fair(struct rq *rq, struct task_struct *p)
{
+ shared_runq_dequeue_task(p);
detach_task_cfs_rq(p);
}
diff --git a/kernel/sched/features.h b/kernel/sched/features.h
index e10074cb4be4..6d7c93fc1a8f 100644
--- a/kernel/sched/features.h
+++ b/kernel/sched/features.h
@@ -103,3 +103,5 @@ SCHED_FEAT(ALT_PERIOD, true)
SCHED_FEAT(BASE_SLICE, true)
SCHED_FEAT(HZ_BW, true)
+
+SCHED_FEAT_CALLBACK(SHARED_RUNQ, false, shared_runq_toggle)
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 2631da3c8a4d..a484bb527ee4 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -2132,6 +2132,7 @@ static const_debug __maybe_unused unsigned int sysctl_sched_features =
#endif /* SCHED_DEBUG */
typedef void (*sched_feat_change_f)(bool enabling);
+extern void shared_runq_toggle(bool enabling);
extern struct static_key_false sched_numa_balancing;
extern struct static_key_false sched_schedstats;
--
2.41.0
The migrate_task_to() function exposed from kernel/sched/core.c migrates
the current task, which is silently assumed to also be its first
argument, to the specified CPU. The function uses stop_one_cpu() to
migrate the task to the target CPU, which won't work if @p is not the
current task as the stop_one_cpu() callback isn't invoked on remote
CPUs.
While this operation is useful for task_numa_migrate() in fair.c, it
would be useful if move_queued_task() in core.c was given external
linkage, as it actually can be used to migrate any task to a CPU.
A follow-on patch will call move_queued_task() from fair.c when
migrating a task in a shared runqueue to a remote CPU.
Suggested-by: Peter Zijlstra <[email protected]>
Signed-off-by: David Vernet <[email protected]>
---
kernel/sched/core.c | 4 ++--
kernel/sched/sched.h | 3 +++
2 files changed, 5 insertions(+), 2 deletions(-)
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 614271a75525..394e216b9d37 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -2519,8 +2519,8 @@ static inline bool is_cpu_allowed(struct task_struct *p, int cpu)
*
* Returns (locked) new rq. Old rq's lock is released.
*/
-static struct rq *move_queued_task(struct rq *rq, struct rq_flags *rf,
- struct task_struct *p, int new_cpu)
+struct rq *move_queued_task(struct rq *rq, struct rq_flags *rf,
+ struct task_struct *p, int new_cpu)
{
lockdep_assert_rq_held(rq);
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 19af1766df2d..69b100267fd0 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -1763,6 +1763,9 @@ init_numa_balancing(unsigned long clone_flags, struct task_struct *p)
#ifdef CONFIG_SMP
+
+extern struct rq *move_queued_task(struct rq *rq, struct rq_flags *rf,
+ struct task_struct *p, int new_cpu);
static inline void
queue_balance_callback(struct rq *rq,
struct balance_callback *head,
--
2.41.0
In newidle_balance(), we check if the current CPU is inactive, and then
decline to pull any remote tasks to the core if so. Before this check,
however, we're currently updating rq->idle_stamp. If a core is offline,
setting its idle stamp is not useful. The core won't be chosen by any
task in select_task_rq_fair(), and setting the rq->idle_stamp is
misleading anyways given that the core being inactive should imply that
it should have a very cold cache.
Let's set rq->idle_stamp in newidle_balance() only if the cpu is active.
Signed-off-by: David Vernet <[email protected]>
---
kernel/sched/fair.c | 12 ++++++------
1 file changed, 6 insertions(+), 6 deletions(-)
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index c28206499a3d..eb15d6f46479 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -12037,18 +12037,18 @@ static int newidle_balance(struct rq *this_rq, struct rq_flags *rf)
if (this_rq->ttwu_pending)
return 0;
- /*
- * We must set idle_stamp _before_ calling idle_balance(), such that we
- * measure the duration of idle_balance() as idle time.
- */
- this_rq->idle_stamp = rq_clock(this_rq);
-
/*
* Do not pull tasks towards !active CPUs...
*/
if (!cpu_active(this_cpu))
return 0;
+ /*
+ * We must set idle_stamp _before_ calling idle_balance(), such that we
+ * measure the duration of idle_balance() as idle time.
+ */
+ this_rq->idle_stamp = rq_clock(this_rq);
+
/*
* This is OK, because current is on_cpu, which avoids it being picked
* for load-balance and preemption/IRQs are still disabled avoiding
--
2.41.0
Hi David,
kernel test robot noticed the following build warnings:
[auto build test WARNING on tip/sched/core]
[cannot apply to linus/master v6.5-rc5 next-20230809]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]
url: https://github.com/intel-lab-lkp/linux/commits/David-Vernet/sched-Expose-move_queued_task-from-core-c/20230810-061611
base: tip/sched/core
patch link: https://lore.kernel.org/r/20230809221218.163894-8-void%40manifault.com
patch subject: [PATCH v3 7/7] sched: Shard per-LLC shared runqueues
config: loongarch-allyesconfig (https://download.01.org/0day-ci/archive/20230810/[email protected]/config)
compiler: loongarch64-linux-gcc (GCC) 12.3.0
reproduce: (https://download.01.org/0day-ci/archive/20230810/[email protected]/reproduce)
If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <[email protected]>
| Closes: https://lore.kernel.org/oe-kbuild-all/[email protected]/
All warnings (new ones prefixed by >>):
>> kernel/sched/fair.c:198: warning: expecting prototype for struct shared_runq. Prototype was for struct shared_runq_shard instead
vim +198 kernel/sched/fair.c
05289b90c2e40a Thara Gopinath 2020-02-21 141
7cc7fb0f3200dd David Vernet 2023-08-09 142 /**
7cc7fb0f3200dd David Vernet 2023-08-09 143 * struct shared_runq - Per-LLC queue structure for enqueuing and migrating
7cc7fb0f3200dd David Vernet 2023-08-09 144 * runnable tasks within an LLC.
7cc7fb0f3200dd David Vernet 2023-08-09 145 *
54c971b941e0bd David Vernet 2023-08-09 146 * struct shared_runq_shard - A structure containing a task list and a spinlock
54c971b941e0bd David Vernet 2023-08-09 147 * for a subset of cores in a struct shared_runq.
54c971b941e0bd David Vernet 2023-08-09 148 *
7cc7fb0f3200dd David Vernet 2023-08-09 149 * WHAT
7cc7fb0f3200dd David Vernet 2023-08-09 150 * ====
7cc7fb0f3200dd David Vernet 2023-08-09 151 *
7cc7fb0f3200dd David Vernet 2023-08-09 152 * This structure enables the scheduler to be more aggressively work
54c971b941e0bd David Vernet 2023-08-09 153 * conserving, by placing waking tasks on a per-LLC FIFO queue shard that can
54c971b941e0bd David Vernet 2023-08-09 154 * then be pulled from when another core in the LLC is going to go idle.
54c971b941e0bd David Vernet 2023-08-09 155 *
54c971b941e0bd David Vernet 2023-08-09 156 * struct rq stores two pointers in its struct cfs_rq:
54c971b941e0bd David Vernet 2023-08-09 157 *
54c971b941e0bd David Vernet 2023-08-09 158 * 1. The per-LLC struct shared_runq which contains one or more shards of
54c971b941e0bd David Vernet 2023-08-09 159 * enqueued tasks.
7cc7fb0f3200dd David Vernet 2023-08-09 160 *
54c971b941e0bd David Vernet 2023-08-09 161 * 2. The shard inside of the per-LLC struct shared_runq which contains the
54c971b941e0bd David Vernet 2023-08-09 162 * list of runnable tasks for that shard.
54c971b941e0bd David Vernet 2023-08-09 163 *
54c971b941e0bd David Vernet 2023-08-09 164 * Waking tasks are enqueued in the calling CPU's struct shared_runq_shard in
54c971b941e0bd David Vernet 2023-08-09 165 * __enqueue_entity(), and are opportunistically pulled from the shared_runq in
54c971b941e0bd David Vernet 2023-08-09 166 * newidle_balance(). Pulling from shards is an O(# shards) operation.
7cc7fb0f3200dd David Vernet 2023-08-09 167 *
7cc7fb0f3200dd David Vernet 2023-08-09 168 * There is currently no task-stealing between shared_runqs in different LLCs,
7cc7fb0f3200dd David Vernet 2023-08-09 169 * which means that shared_runq is not fully work conserving. This could be
7cc7fb0f3200dd David Vernet 2023-08-09 170 * added at a later time, with tasks likely only being stolen across
7cc7fb0f3200dd David Vernet 2023-08-09 171 * shared_runqs on the same NUMA node to avoid violating NUMA affinities.
7cc7fb0f3200dd David Vernet 2023-08-09 172 *
7cc7fb0f3200dd David Vernet 2023-08-09 173 * HOW
7cc7fb0f3200dd David Vernet 2023-08-09 174 * ===
7cc7fb0f3200dd David Vernet 2023-08-09 175 *
54c971b941e0bd David Vernet 2023-08-09 176 * A struct shared_runq_shard is comprised of a list, and a spinlock for
54c971b941e0bd David Vernet 2023-08-09 177 * synchronization. Given that the critical section for a shared_runq is
54c971b941e0bd David Vernet 2023-08-09 178 * typically a fast list operation, and that the shared_runq_shard is localized
54c971b941e0bd David Vernet 2023-08-09 179 * to a subset of cores on a single LLC (plus other cores in the LLC that pull
54c971b941e0bd David Vernet 2023-08-09 180 * from the shard in newidle_balance()), the spinlock will typically only be
54c971b941e0bd David Vernet 2023-08-09 181 * contended on workloads that do little else other than hammer the runqueue.
7cc7fb0f3200dd David Vernet 2023-08-09 182 *
7cc7fb0f3200dd David Vernet 2023-08-09 183 * WHY
7cc7fb0f3200dd David Vernet 2023-08-09 184 * ===
7cc7fb0f3200dd David Vernet 2023-08-09 185 *
7cc7fb0f3200dd David Vernet 2023-08-09 186 * As mentioned above, the main benefit of shared_runq is that it enables more
7cc7fb0f3200dd David Vernet 2023-08-09 187 * aggressive work conservation in the scheduler. This can benefit workloads
7cc7fb0f3200dd David Vernet 2023-08-09 188 * that benefit more from CPU utilization than from L1/L2 cache locality.
7cc7fb0f3200dd David Vernet 2023-08-09 189 *
7cc7fb0f3200dd David Vernet 2023-08-09 190 * shared_runqs are segmented across LLCs both to avoid contention on the
7cc7fb0f3200dd David Vernet 2023-08-09 191 * shared_runq spinlock by minimizing the number of CPUs that could contend on
7cc7fb0f3200dd David Vernet 2023-08-09 192 * it, as well as to strike a balance between work conservation, and L3 cache
7cc7fb0f3200dd David Vernet 2023-08-09 193 * locality.
7cc7fb0f3200dd David Vernet 2023-08-09 194 */
54c971b941e0bd David Vernet 2023-08-09 195 struct shared_runq_shard {
7cc7fb0f3200dd David Vernet 2023-08-09 196 struct list_head list;
7cc7fb0f3200dd David Vernet 2023-08-09 197 raw_spinlock_t lock;
7cc7fb0f3200dd David Vernet 2023-08-09 @198 } ____cacheline_aligned;
7cc7fb0f3200dd David Vernet 2023-08-09 199
--
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki
On Thu, Aug 10, 2023 at 07:46:37AM +0800, kernel test robot wrote:
> Hi David,
>
> kernel test robot noticed the following build warnings:
>
> [auto build test WARNING on tip/sched/core]
> [cannot apply to linus/master v6.5-rc5 next-20230809]
> [If your patch is applied to the wrong git tree, kindly drop us a note.
> And when submitting patch, we suggest to use '--base' as documented in
> https://git-scm.com/docs/git-format-patch#_base_tree_information]
>
> url: https://github.com/intel-lab-lkp/linux/commits/David-Vernet/sched-Expose-move_queued_task-from-core-c/20230810-061611
> base: tip/sched/core
> patch link: https://lore.kernel.org/r/20230809221218.163894-8-void%40manifault.com
> patch subject: [PATCH v3 7/7] sched: Shard per-LLC shared runqueues
> config: loongarch-allyesconfig (https://download.01.org/0day-ci/archive/20230810/[email protected]/config)
> compiler: loongarch64-linux-gcc (GCC) 12.3.0
> reproduce: (https://download.01.org/0day-ci/archive/20230810/[email protected]/reproduce)
>
> If you fix the issue in a separate patch/commit (i.e. not just a new version of
> the same patch/commit), kindly add following tags
> | Reported-by: kernel test robot <[email protected]>
> | Closes: https://lore.kernel.org/oe-kbuild-all/[email protected]/
>
> All warnings (new ones prefixed by >>):
>
> >> kernel/sched/fair.c:198: warning: expecting prototype for struct shared_runq. Prototype was for struct shared_runq_shard instead
I'll split this comment up in v4.
Hi David,
kernel test robot noticed the following build errors:
[auto build test ERROR on tip/sched/core]
[cannot apply to linus/master v6.5-rc5 next-20230809]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]
url: https://github.com/intel-lab-lkp/linux/commits/David-Vernet/sched-Expose-move_queued_task-from-core-c/20230810-061611
base: tip/sched/core
patch link: https://lore.kernel.org/r/20230809221218.163894-7-void%40manifault.com
patch subject: [PATCH v3 6/7] sched: Implement shared runqueue in CFS
config: sparc-randconfig-r015-20230809 (https://download.01.org/0day-ci/archive/20230810/[email protected]/config)
compiler: sparc-linux-gcc (GCC) 12.3.0
reproduce: (https://download.01.org/0day-ci/archive/20230810/[email protected]/reproduce)
If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <[email protected]>
| Closes: https://lore.kernel.org/oe-kbuild-all/[email protected]/
All error/warnings (new ones prefixed by >>):
>> kernel/sched/core.c:9768:6: warning: no previous prototype for 'sched_update_domains' [-Wmissing-prototypes]
9768 | void sched_update_domains(void)
| ^~~~~~~~~~~~~~~~~~~~
--
In file included from kernel/sched/build_utility.c:89:
kernel/sched/topology.c: In function 'sched_init_domains':
>> kernel/sched/topology.c:2580:17: error: implicit declaration of function 'sched_update_domains'; did you mean 'sched_update_scaling'? [-Werror=implicit-function-declaration]
2580 | sched_update_domains();
| ^~~~~~~~~~~~~~~~~~~~
| sched_update_scaling
cc1: some warnings being treated as errors
vim +2580 kernel/sched/topology.c
2558
2559 /*
2560 * Set up scheduler domains and groups. For now this just excludes isolated
2561 * CPUs, but could be used to exclude other special cases in the future.
2562 */
2563 int __init sched_init_domains(const struct cpumask *cpu_map)
2564 {
2565 int err;
2566
2567 zalloc_cpumask_var(&sched_domains_tmpmask, GFP_KERNEL);
2568 zalloc_cpumask_var(&sched_domains_tmpmask2, GFP_KERNEL);
2569 zalloc_cpumask_var(&fallback_doms, GFP_KERNEL);
2570
2571 arch_update_cpu_topology();
2572 asym_cpu_capacity_scan();
2573 ndoms_cur = 1;
2574 doms_cur = alloc_sched_domains(ndoms_cur);
2575 if (!doms_cur)
2576 doms_cur = &fallback_doms;
2577 cpumask_and(doms_cur[0], cpu_map, housekeeping_cpumask(HK_TYPE_DOMAIN));
2578 err = build_sched_domains(doms_cur[0], NULL);
2579 if (!err)
> 2580 sched_update_domains();
2581
2582 return err;
2583 }
2584
--
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki
Hi David,
kernel test robot noticed the following build errors:
[auto build test ERROR on tip/sched/core]
[cannot apply to linus/master v6.5-rc5 next-20230809]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]
url: https://github.com/intel-lab-lkp/linux/commits/David-Vernet/sched-Expose-move_queued_task-from-core-c/20230810-061611
base: tip/sched/core
patch link: https://lore.kernel.org/r/20230809221218.163894-7-void%40manifault.com
patch subject: [PATCH v3 6/7] sched: Implement shared runqueue in CFS
config: hexagon-randconfig-r045-20230809 (https://download.01.org/0day-ci/archive/20230810/[email protected]/config)
compiler: clang version 17.0.0 (https://github.com/llvm/llvm-project.git 4a5ac14ee968ff0ad5d2cc1ffa0299048db4c88a)
reproduce: (https://download.01.org/0day-ci/archive/20230810/[email protected]/reproduce)
If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <[email protected]>
| Closes: https://lore.kernel.org/oe-kbuild-all/[email protected]/
All error/warnings (new ones prefixed by >>):
In file included from kernel/sched/core.c:9:
In file included from include/linux/highmem.h:12:
In file included from include/linux/hardirq.h:11:
In file included from ./arch/hexagon/include/generated/asm/hardirq.h:1:
In file included from include/asm-generic/hardirq.h:17:
In file included from include/linux/irq.h:20:
In file included from include/linux/io.h:13:
In file included from arch/hexagon/include/asm/io.h:334:
include/asm-generic/io.h:547:31: warning: performing pointer arithmetic on a null pointer has undefined behavior [-Wnull-pointer-arithmetic]
547 | val = __raw_readb(PCI_IOBASE + addr);
| ~~~~~~~~~~ ^
include/asm-generic/io.h:560:61: warning: performing pointer arithmetic on a null pointer has undefined behavior [-Wnull-pointer-arithmetic]
560 | val = __le16_to_cpu((__le16 __force)__raw_readw(PCI_IOBASE + addr));
| ~~~~~~~~~~ ^
include/uapi/linux/byteorder/little_endian.h:37:51: note: expanded from macro '__le16_to_cpu'
37 | #define __le16_to_cpu(x) ((__force __u16)(__le16)(x))
| ^
In file included from kernel/sched/core.c:9:
In file included from include/linux/highmem.h:12:
In file included from include/linux/hardirq.h:11:
In file included from ./arch/hexagon/include/generated/asm/hardirq.h:1:
In file included from include/asm-generic/hardirq.h:17:
In file included from include/linux/irq.h:20:
In file included from include/linux/io.h:13:
In file included from arch/hexagon/include/asm/io.h:334:
include/asm-generic/io.h:573:61: warning: performing pointer arithmetic on a null pointer has undefined behavior [-Wnull-pointer-arithmetic]
573 | val = __le32_to_cpu((__le32 __force)__raw_readl(PCI_IOBASE + addr));
| ~~~~~~~~~~ ^
include/uapi/linux/byteorder/little_endian.h:35:51: note: expanded from macro '__le32_to_cpu'
35 | #define __le32_to_cpu(x) ((__force __u32)(__le32)(x))
| ^
In file included from kernel/sched/core.c:9:
In file included from include/linux/highmem.h:12:
In file included from include/linux/hardirq.h:11:
In file included from ./arch/hexagon/include/generated/asm/hardirq.h:1:
In file included from include/asm-generic/hardirq.h:17:
In file included from include/linux/irq.h:20:
In file included from include/linux/io.h:13:
In file included from arch/hexagon/include/asm/io.h:334:
include/asm-generic/io.h:584:33: warning: performing pointer arithmetic on a null pointer has undefined behavior [-Wnull-pointer-arithmetic]
584 | __raw_writeb(value, PCI_IOBASE + addr);
| ~~~~~~~~~~ ^
include/asm-generic/io.h:594:59: warning: performing pointer arithmetic on a null pointer has undefined behavior [-Wnull-pointer-arithmetic]
594 | __raw_writew((u16 __force)cpu_to_le16(value), PCI_IOBASE + addr);
| ~~~~~~~~~~ ^
include/asm-generic/io.h:604:59: warning: performing pointer arithmetic on a null pointer has undefined behavior [-Wnull-pointer-arithmetic]
604 | __raw_writel((u32 __force)cpu_to_le32(value), PCI_IOBASE + addr);
| ~~~~~~~~~~ ^
>> kernel/sched/core.c:9768:6: warning: no previous prototype for function 'sched_update_domains' [-Wmissing-prototypes]
9768 | void sched_update_domains(void)
| ^
kernel/sched/core.c:9768:1: note: declare 'static' if the function is not intended to be used outside of this translation unit
9768 | void sched_update_domains(void)
| ^
| static
kernel/sched/core.c:2467:20: warning: unused function 'rq_has_pinned_tasks' [-Wunused-function]
2467 | static inline bool rq_has_pinned_tasks(struct rq *rq)
| ^
kernel/sched/core.c:5818:20: warning: unused function 'sched_tick_stop' [-Wunused-function]
5818 | static inline void sched_tick_stop(int cpu) { }
| ^
kernel/sched/core.c:6519:20: warning: unused function 'sched_core_cpu_deactivate' [-Wunused-function]
6519 | static inline void sched_core_cpu_deactivate(unsigned int cpu) {}
| ^
kernel/sched/core.c:6520:20: warning: unused function 'sched_core_cpu_dying' [-Wunused-function]
6520 | static inline void sched_core_cpu_dying(unsigned int cpu) {}
| ^
kernel/sched/core.c:9570:20: warning: unused function 'balance_hotplug_wait' [-Wunused-function]
9570 | static inline void balance_hotplug_wait(void)
| ^
12 warnings generated.
--
In file included from kernel/sched/build_utility.c:15:
In file included from include/linux/sched/isolation.h:6:
In file included from include/linux/tick.h:8:
In file included from include/linux/clockchips.h:14:
In file included from include/linux/clocksource.h:22:
In file included from arch/hexagon/include/asm/io.h:334:
include/asm-generic/io.h:547:31: warning: performing pointer arithmetic on a null pointer has undefined behavior [-Wnull-pointer-arithmetic]
547 | val = __raw_readb(PCI_IOBASE + addr);
| ~~~~~~~~~~ ^
include/asm-generic/io.h:560:61: warning: performing pointer arithmetic on a null pointer has undefined behavior [-Wnull-pointer-arithmetic]
560 | val = __le16_to_cpu((__le16 __force)__raw_readw(PCI_IOBASE + addr));
| ~~~~~~~~~~ ^
include/uapi/linux/byteorder/little_endian.h:37:51: note: expanded from macro '__le16_to_cpu'
37 | #define __le16_to_cpu(x) ((__force __u16)(__le16)(x))
| ^
In file included from kernel/sched/build_utility.c:15:
In file included from include/linux/sched/isolation.h:6:
In file included from include/linux/tick.h:8:
In file included from include/linux/clockchips.h:14:
In file included from include/linux/clocksource.h:22:
In file included from arch/hexagon/include/asm/io.h:334:
include/asm-generic/io.h:573:61: warning: performing pointer arithmetic on a null pointer has undefined behavior [-Wnull-pointer-arithmetic]
573 | val = __le32_to_cpu((__le32 __force)__raw_readl(PCI_IOBASE + addr));
| ~~~~~~~~~~ ^
include/uapi/linux/byteorder/little_endian.h:35:51: note: expanded from macro '__le32_to_cpu'
35 | #define __le32_to_cpu(x) ((__force __u32)(__le32)(x))
| ^
In file included from kernel/sched/build_utility.c:15:
In file included from include/linux/sched/isolation.h:6:
In file included from include/linux/tick.h:8:
In file included from include/linux/clockchips.h:14:
In file included from include/linux/clocksource.h:22:
In file included from arch/hexagon/include/asm/io.h:334:
include/asm-generic/io.h:584:33: warning: performing pointer arithmetic on a null pointer has undefined behavior [-Wnull-pointer-arithmetic]
584 | __raw_writeb(value, PCI_IOBASE + addr);
| ~~~~~~~~~~ ^
include/asm-generic/io.h:594:59: warning: performing pointer arithmetic on a null pointer has undefined behavior [-Wnull-pointer-arithmetic]
594 | __raw_writew((u16 __force)cpu_to_le16(value), PCI_IOBASE + addr);
| ~~~~~~~~~~ ^
include/asm-generic/io.h:604:59: warning: performing pointer arithmetic on a null pointer has undefined behavior [-Wnull-pointer-arithmetic]
604 | __raw_writel((u32 __force)cpu_to_le32(value), PCI_IOBASE + addr);
| ~~~~~~~~~~ ^
In file included from kernel/sched/build_utility.c:89:
>> kernel/sched/topology.c:2580:3: error: call to undeclared function 'sched_update_domains'; ISO C99 and later do not support implicit function declarations [-Wimplicit-function-declaration]
2580 | sched_update_domains();
| ^
kernel/sched/topology.c:2746:2: error: call to undeclared function 'sched_update_domains'; ISO C99 and later do not support implicit function declarations [-Wimplicit-function-declaration]
2746 | sched_update_domains();
| ^
6 warnings and 2 errors generated.
vim +/sched_update_domains +2580 kernel/sched/topology.c
2558
2559 /*
2560 * Set up scheduler domains and groups. For now this just excludes isolated
2561 * CPUs, but could be used to exclude other special cases in the future.
2562 */
2563 int __init sched_init_domains(const struct cpumask *cpu_map)
2564 {
2565 int err;
2566
2567 zalloc_cpumask_var(&sched_domains_tmpmask, GFP_KERNEL);
2568 zalloc_cpumask_var(&sched_domains_tmpmask2, GFP_KERNEL);
2569 zalloc_cpumask_var(&fallback_doms, GFP_KERNEL);
2570
2571 arch_update_cpu_topology();
2572 asym_cpu_capacity_scan();
2573 ndoms_cur = 1;
2574 doms_cur = alloc_sched_domains(ndoms_cur);
2575 if (!doms_cur)
2576 doms_cur = &fallback_doms;
2577 cpumask_and(doms_cur[0], cpu_map, housekeeping_cpumask(HK_TYPE_DOMAIN));
2578 err = build_sched_domains(doms_cur[0], NULL);
2579 if (!err)
> 2580 sched_update_domains();
2581
2582 return err;
2583 }
2584
--
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki
Hi David,
kernel test robot noticed the following build warnings:
[auto build test WARNING on tip/sched/core]
[cannot apply to linus/master v6.5-rc5 next-20230809]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]
url: https://github.com/intel-lab-lkp/linux/commits/David-Vernet/sched-Expose-move_queued_task-from-core-c/20230810-061611
base: tip/sched/core
patch link: https://lore.kernel.org/r/20230809221218.163894-8-void%40manifault.com
patch subject: [PATCH v3 7/7] sched: Shard per-LLC shared runqueues
config: hexagon-randconfig-r041-20230809 (https://download.01.org/0day-ci/archive/20230810/[email protected]/config)
compiler: clang version 17.0.0 (https://github.com/llvm/llvm-project.git 4a5ac14ee968ff0ad5d2cc1ffa0299048db4c88a)
reproduce: (https://download.01.org/0day-ci/archive/20230810/[email protected]/reproduce)
If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <[email protected]>
| Closes: https://lore.kernel.org/oe-kbuild-all/[email protected]/
All warnings (new ones prefixed by >>):
>> kernel/sched/fair.c:198: warning: expecting prototype for struct shared_runq. Prototype was for struct shared_runq_shard instead
vim +198 kernel/sched/fair.c
05289b90c2e40ae Thara Gopinath 2020-02-21 141
7cc7fb0f3200dd3 David Vernet 2023-08-09 142 /**
7cc7fb0f3200dd3 David Vernet 2023-08-09 143 * struct shared_runq - Per-LLC queue structure for enqueuing and migrating
7cc7fb0f3200dd3 David Vernet 2023-08-09 144 * runnable tasks within an LLC.
7cc7fb0f3200dd3 David Vernet 2023-08-09 145 *
54c971b941e0bd0 David Vernet 2023-08-09 146 * struct shared_runq_shard - A structure containing a task list and a spinlock
54c971b941e0bd0 David Vernet 2023-08-09 147 * for a subset of cores in a struct shared_runq.
54c971b941e0bd0 David Vernet 2023-08-09 148 *
7cc7fb0f3200dd3 David Vernet 2023-08-09 149 * WHAT
7cc7fb0f3200dd3 David Vernet 2023-08-09 150 * ====
7cc7fb0f3200dd3 David Vernet 2023-08-09 151 *
7cc7fb0f3200dd3 David Vernet 2023-08-09 152 * This structure enables the scheduler to be more aggressively work
54c971b941e0bd0 David Vernet 2023-08-09 153 * conserving, by placing waking tasks on a per-LLC FIFO queue shard that can
54c971b941e0bd0 David Vernet 2023-08-09 154 * then be pulled from when another core in the LLC is going to go idle.
54c971b941e0bd0 David Vernet 2023-08-09 155 *
54c971b941e0bd0 David Vernet 2023-08-09 156 * struct rq stores two pointers in its struct cfs_rq:
54c971b941e0bd0 David Vernet 2023-08-09 157 *
54c971b941e0bd0 David Vernet 2023-08-09 158 * 1. The per-LLC struct shared_runq which contains one or more shards of
54c971b941e0bd0 David Vernet 2023-08-09 159 * enqueued tasks.
7cc7fb0f3200dd3 David Vernet 2023-08-09 160 *
54c971b941e0bd0 David Vernet 2023-08-09 161 * 2. The shard inside of the per-LLC struct shared_runq which contains the
54c971b941e0bd0 David Vernet 2023-08-09 162 * list of runnable tasks for that shard.
54c971b941e0bd0 David Vernet 2023-08-09 163 *
54c971b941e0bd0 David Vernet 2023-08-09 164 * Waking tasks are enqueued in the calling CPU's struct shared_runq_shard in
54c971b941e0bd0 David Vernet 2023-08-09 165 * __enqueue_entity(), and are opportunistically pulled from the shared_runq in
54c971b941e0bd0 David Vernet 2023-08-09 166 * newidle_balance(). Pulling from shards is an O(# shards) operation.
7cc7fb0f3200dd3 David Vernet 2023-08-09 167 *
7cc7fb0f3200dd3 David Vernet 2023-08-09 168 * There is currently no task-stealing between shared_runqs in different LLCs,
7cc7fb0f3200dd3 David Vernet 2023-08-09 169 * which means that shared_runq is not fully work conserving. This could be
7cc7fb0f3200dd3 David Vernet 2023-08-09 170 * added at a later time, with tasks likely only being stolen across
7cc7fb0f3200dd3 David Vernet 2023-08-09 171 * shared_runqs on the same NUMA node to avoid violating NUMA affinities.
7cc7fb0f3200dd3 David Vernet 2023-08-09 172 *
7cc7fb0f3200dd3 David Vernet 2023-08-09 173 * HOW
7cc7fb0f3200dd3 David Vernet 2023-08-09 174 * ===
7cc7fb0f3200dd3 David Vernet 2023-08-09 175 *
54c971b941e0bd0 David Vernet 2023-08-09 176 * A struct shared_runq_shard is comprised of a list, and a spinlock for
54c971b941e0bd0 David Vernet 2023-08-09 177 * synchronization. Given that the critical section for a shared_runq is
54c971b941e0bd0 David Vernet 2023-08-09 178 * typically a fast list operation, and that the shared_runq_shard is localized
54c971b941e0bd0 David Vernet 2023-08-09 179 * to a subset of cores on a single LLC (plus other cores in the LLC that pull
54c971b941e0bd0 David Vernet 2023-08-09 180 * from the shard in newidle_balance()), the spinlock will typically only be
54c971b941e0bd0 David Vernet 2023-08-09 181 * contended on workloads that do little else other than hammer the runqueue.
7cc7fb0f3200dd3 David Vernet 2023-08-09 182 *
7cc7fb0f3200dd3 David Vernet 2023-08-09 183 * WHY
7cc7fb0f3200dd3 David Vernet 2023-08-09 184 * ===
7cc7fb0f3200dd3 David Vernet 2023-08-09 185 *
7cc7fb0f3200dd3 David Vernet 2023-08-09 186 * As mentioned above, the main benefit of shared_runq is that it enables more
7cc7fb0f3200dd3 David Vernet 2023-08-09 187 * aggressive work conservation in the scheduler. This can benefit workloads
7cc7fb0f3200dd3 David Vernet 2023-08-09 188 * that benefit more from CPU utilization than from L1/L2 cache locality.
7cc7fb0f3200dd3 David Vernet 2023-08-09 189 *
7cc7fb0f3200dd3 David Vernet 2023-08-09 190 * shared_runqs are segmented across LLCs both to avoid contention on the
7cc7fb0f3200dd3 David Vernet 2023-08-09 191 * shared_runq spinlock by minimizing the number of CPUs that could contend on
7cc7fb0f3200dd3 David Vernet 2023-08-09 192 * it, as well as to strike a balance between work conservation, and L3 cache
7cc7fb0f3200dd3 David Vernet 2023-08-09 193 * locality.
7cc7fb0f3200dd3 David Vernet 2023-08-09 194 */
54c971b941e0bd0 David Vernet 2023-08-09 195 struct shared_runq_shard {
7cc7fb0f3200dd3 David Vernet 2023-08-09 196 struct list_head list;
7cc7fb0f3200dd3 David Vernet 2023-08-09 197 raw_spinlock_t lock;
7cc7fb0f3200dd3 David Vernet 2023-08-09 @198 } ____cacheline_aligned;
7cc7fb0f3200dd3 David Vernet 2023-08-09 199
--
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki
On Wed, Aug 30, 2023 at 02:17:09PM +0800, Chen Yu wrote:
> Hi David,
Hi Chenyu,
Thank you for running these tests, and for your very in-depth analysis
and explanation of the performance you were observing.
> On 2023-08-09 at 17:12:18 -0500, David Vernet wrote:
> > The SHARED_RUNQ scheduler feature creates a FIFO queue per LLC that
> > tasks are put into on enqueue, and pulled from when a core in that LLC
> > would otherwise go idle. For CPUs with large LLCs, this can sometimes
> > cause significant contention, as illustrated in [0].
> >
> > [0]: https://lore.kernel.org/all/[email protected]/
> >
> > So as to try and mitigate this contention, we can instead shard the
> > per-LLC runqueue into multiple per-LLC shards.
> >
> > While this doesn't outright prevent all contention, it does somewhat mitigate it.
> >
>
> Thanks for this proposal to make idle load balance more efficient. As we
> dicussed previously, I launched hackbench on Intel Sapphire Rapids
> and I have some findings.
>
> This platform has 2 sockets, each socket has 56C/112T. To avoid the
> run-run variance, only 1 socket is online, the cpufreq govenor is set to
> performance, the turbo is disabled, and C-states deeper than C1 are disabled.
>
> hackbench
> =========
> case load baseline(std%) compare%( std%)
> process-pipe 1-groups 1.00 ( 1.09) +0.55 ( 0.20)
> process-pipe 2-groups 1.00 ( 0.60) +3.57 ( 0.28)
> process-pipe 4-groups 1.00 ( 0.30) +5.22 ( 0.26)
> process-pipe 8-groups 1.00 ( 0.10) +43.96 ( 0.26)
> process-sockets 1-groups 1.00 ( 0.18) -1.56 ( 0.34)
> process-sockets 2-groups 1.00 ( 1.06) -12.37 ( 0.11)
> process-sockets 4-groups 1.00 ( 0.29) +0.21 ( 0.19)
> process-sockets 8-groups 1.00 ( 0.06) +3.59 ( 0.39)
>
> The 8 groups pipe mode has an impressive improvement, while the 2 groups sockets
> mode did see some regressions.
>
> The possible reason to cause the regression is at the end of this reply, in
> case you want to see the conclusion directly : )
I read through everything, and it all made sense. I'll reply to your
conclusion below.
> To investigate the regression, I did slight hack on the hackbench, by renaming
> the workload to sender and receiver.
>
> When it is in 2 groups mode, there would be 2 groups of senders and receivers.
> Each group has 14 senders and 14 receivers. So there are totally 56 tasks running
> on 112 CPUs. In each group, sender_i sends package to receiver_j ( i, j belong to [1,14] )
>
>
> 1. Firstly use 'top' to monitor the CPU utilization:
>
> When shared_runqueue is disabled, many CPUs are 100%, while the other
> CPUs remain 0%.
> When shared_runqueue is enabled, most CPUs are busy and the utilization is
> in 40%~60%.
>
> This means that shared_runqueue works as expected.
>
> 2. Then the bpf wakeup latency is monitored:
>
> tracepoint:sched:sched_wakeup,
> tracepoint:sched:sched_wakeup_new
> {
> if (args->comm == "sender") {
> @qstime[args->pid] = nsecs;
> }
> if (args->comm == "receiver") {
> @qrtime[args->pid] = nsecs;
> }
> }
>
> tracepoint:sched:sched_switch
> {
> if (args->next_comm == "sender") {
> $ns = @qstime[args->next_pid];
> if ($ns) {
> @sender_wakeup_lat = hist((nsecs - $ns) / 1000);
> delete(@qstime[args->next_pid]);
> }
> }
> if (args->next_comm == "receiver") {
> $ns = @qrtime[args->next_pid];
> if ($ns) {
> @receiver_wakeup_lat = hist((nsecs - $ns) / 1000);
> delete(@qstime[args->next_pid]);
> }
> }
> }
>
>
> It shows that, the wakeup latency of the receiver has been increased a little
> bit. But consider that this symptom is the same when the hackbench is in pipe mode,
> and there is no regression in pipe mode, the wakeup latency overhead might not be
> the cause of the regression.
>
> 3. Then FlameGraph is used to compare the bottleneck.
> There is still no obvious difference noticed. One obvious bottleneck is the atomic
> write to a memory cgroup page count(and runqueue lock contention is not observed).
> The backtrace:
>
> obj_cgroup_charge_pages;obj_cgroup_charge;__kmem_cache_alloc_node;
> __kmalloc_node_track_caller;kmalloc_reserve;__alloc_skb;
> alloc_skb_with_frags;sock_alloc_send_pskb;unix_stream_sendmsg
>
> However there is no obvious ratio difference between with/without shared runqueue
> enabled. So this one might not be the cause.
>
> 4. Check the wakeup task migration count
>
> Borrow the script from Aaron:
> kretfunc:select_task_rq_fair
> {
> $p = (struct task_struct *)args->p;
> if ($p->comm == "sender") {
> if ($p->thread_info.cpu != retval) {
> @wakeup_migrate_sender = count();
> } else {
> @wakeup_prev_sender = count();
> }
> }
> if ($p->comm == "receiver") {
> if ($p->thread_info.cpu != retval) {
> @wakeup_migrate_receiver = count();
> } else {
> @wakeup_prev_receiver = count();
> }
> }
> }
>
> Without shared_runqueue enabled, the wakee task are mostly woken up on it
> previous running CPUs.
> With shared_runqueue disabled, the wakee task are mostly woken up on a
> completely different idle CPUs.
>
> This reminds me that, is it possible the regression was caused by the broken
> cache locallity?
>
>
> 5. Check the L2 cache miss rate.
> perf stat -e l2_rqsts.references,l2_request.miss sleep 10
> The results show that the L2 cache miss rate is nearly the same with/without
> shared_runqueue enabled.
As mentioned below, I expect it would be interesting to also collect
icache / iTLB numbers. In my experience, poor uop cache locality will
also result in poor icache locality, though of course that depends on a
lot of other factors like alignment, how many (un)conditional branches
you have within some byte window, etc. If alignment, etc were the issue
though, we'd likely observe this also without SHARED_RUNQ.
> I did not check the L3 miss rate, because:
> 3.1 there is only 1 socket of CPUs online
> 3.2 the working set the hackbench is 56 * 100 * 300000, which is nearly
> the same as LLC cache size.
>
> 6. As mentioned in step 3, the bottleneck is a atomic write to a global
> variable. Then use perf c2c to check if there is any false/true sharing.
>
> According to the result, the total number and average cycles of local HITM
> is low.So this might indicate that this is not a false sharing or true
> sharing issue.
>
>
> 7. Then use perf topdown to dig into the detail. The methodology is at
> https://perf.wiki.kernel.org/index.php/Top-Down_Analysis
>
>
> When shared runqueue is disabled:
>
> # 65.2 % tma_backend_bound
> # 2.9 % tma_bad_speculation
> # 13.1 % tma_frontend_bound
> # 18.7 % tma_retiring
>
>
>
> When shared runqueue is enabled:
>
> # 52.4 % tma_backend_bound
> # 3.3 % tma_bad_speculation
> # 20.5 % tma_frontend_bound
> # 23.8 % tma_retiring
>
>
> We can see that, the ratio of frontend_bound has increased from 13.1% to
> 20.5%. As a comparison, this ratio does not increase when the hackbench
> is in pipe mode.
>
> Then further dig into the deeper level of frontend_bound:
>
> When shared runqueue is disabled:
> # 6.9 % tma_fetch_latency ----> # 7.3 % tma_ms_switches
> |
> ----> # 7.1 % tma_dsb_switches
>
>
> When shared runqueue is enabled:
> # 11.6 % tma_fetch_latency ----> # 6.7 % tma_ms_switches
> |
> ----> # 7.8 % tma_dsb_switches
>
>
> 1. The DSB(Decode Stream Buffer) switches count increases
> from 13.1% * 6.9% * 7.1% to 20.5% * 11.6% * 7.8%
Indeed, these switches are quite costly from what I understand.
> 2. The MS(Microcode Sequencer) switches count increases
> from 13.1% * 6.9% * 7.3% to 20.5% * 11.6% * 6.7%
>
> DSB is the cached decoded uops, which is similar to L1 icache,
> except that icache has the original instructions, while DSB has the
> decoded one. DSB reflects the instruction footprint. The increase
> of DSB switches mean that, the cached buffer has been thrashed a lot.
>
> MS is to decode the complex instructions, the increase of MS switch counter
> usually means that the workload is running some complex instruction.
> that the workload is running complex instructions.
>
> In summary:
>
> So the scenario to cause this issue I'm thinking of is:
> Task migration increases the DSB switches count. With shared_runqueue enabled,
> the task could be migrated to different CPUs more offen. And it has to fill its
> new uops into the DSB, but that DSB has already been filled by the old task's
> uops. So DSB switches is triggered to decode the new macro ops. This is usually
> not a problem if the workload runs some simple instructions. However if
> this workload's instruction footprint increases, task migration might break
> the DSB uops locality, which is similar to L1/L2 cache locality.
Interesting. As mentioned above, I expect we also see an increase in
iTLB and icache misses?
This is something we deal with in HHVM. Like any other JIT engine /
compiler, it is heavily front-end CPU bound, and has very poor icache,
iTLB, and uop cache locality (also lots of branch resteers, etc).
SHARED_RUNQ actually helps this workload quite a lot, as explained in
the cover letter for the patch series. It makes sense that it would: uop
locality is really bad even without increasing CPU util. So we have no
reason not to migrate the task and hop on a CPU.
> I wonder, if SHARED_RUNQ can consider that, if a task is a long duration one,
> say, p->avg_runtime >= sysctl_migration_cost, maybe we should not put such task
> on the per-LLC shared runqueue? In this way it will not be migrated too offen
> so as to keep its locality(both in terms of L1/L2 cache and DSB).
I'm hesitant to apply such heuristics to the feature. As mentioned
above, SHARED_RUNQ works very well on HHVM, despite its potential hit to
icache / iTLB / DSB locality. Those hhvmworker tasks run for a very long
time, sometimes upwards of 20+ms. They also tend to have poor L1 cache
locality in general even when they're scheduled on the same core they
were on before they were descheduled, so we observe better performance
if the task is migrated to a fully idle core rather than e.g. its
hypertwin if it's available. That's not something we can guarantee with
SHARED_RUNQ, but it hopefully illustrates the point that it's an example
of a workload that would suffer with such a heuristic.
Another point to consider is that performance implications that are a
result of Intel micro architectural details don't necessarily apply to
everyone. I'm not as familiar with the instruction decode pipeline on
AMD chips like Zen4. I'm sure they have a uop cache, but the size of
that cache, alignment requirements, the way that cache interfaces with
e.g. their version of the MITE / decoder, etc, are all going to be quite
different.
In general, I think it's difficult for heuristics like this to suit all
possible workloads or situations (not that you're claiming it is). My
preference is to keep it as is so that it's easier for users to build a
mental model of what outcome they should expect if they use the feature.
Put another way: As a user of this feature, I'd be a lot more surprised
to see that I enabled it and CPU util stayed low, vs. enabling it and
seeing higher CPU util, but also degraded icache / iTLB locality.
Let me know what you think, and thanks again for investing your time
into this.
Thanks,
David
On Wed, Aug 30, 2023 at 12:16:17PM +0530, K Prateek Nayak wrote:
> Hello David,
Hello Prateek,
>
> On 8/10/2023 3:42 AM, David Vernet wrote:
> > [..snip..]
> > diff --git a/include/linux/sched.h b/include/linux/sched.h
> > index 2aab7be46f7e..8238069fd852 100644
> > --- a/include/linux/sched.h
> > +++ b/include/linux/sched.h
> > @@ -769,6 +769,8 @@ struct task_struct {
> > unsigned long wakee_flip_decay_ts;
> > struct task_struct *last_wakee;
> >
> > + struct list_head shared_runq_node;
> > +
> > /*
> > * recent_used_cpu is initially set as the last CPU used by a task
> > * that wakes affine another task. Waker/wakee relationships can
> > diff --git a/kernel/sched/core.c b/kernel/sched/core.c
> > index 385c565da87f..fb7e71d3dc0a 100644
> > --- a/kernel/sched/core.c
> > +++ b/kernel/sched/core.c
> > @@ -4529,6 +4529,7 @@ static void __sched_fork(unsigned long clone_flags, struct task_struct *p)
> > #ifdef CONFIG_SMP
> > p->wake_entry.u_flags = CSD_TYPE_TTWU;
> > p->migration_pending = NULL;
> > + INIT_LIST_HEAD(&p->shared_runq_node);
> > #endif
> > init_sched_mm_cid(p);
> > }
> > @@ -9764,6 +9765,18 @@ int sched_cpu_deactivate(unsigned int cpu)
> > return 0;
> > }
> >
> > +void sched_update_domains(void)
> > +{
> > + const struct sched_class *class;
> > +
> > + update_sched_domain_debugfs();
> > +
> > + for_each_class(class) {
> > + if (class->update_domains)
> > + class->update_domains();
> > + }
> > +}
> > +
> > static void sched_rq_cpu_starting(unsigned int cpu)
> > {
> > struct rq *rq = cpu_rq(cpu);
> > diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> > index 9c23e3b948fc..6e740f8da578 100644
> > --- a/kernel/sched/fair.c
> > +++ b/kernel/sched/fair.c
> > @@ -139,20 +139,235 @@ static int __init setup_sched_thermal_decay_shift(char *str)
> > }
> > __setup("sched_thermal_decay_shift=", setup_sched_thermal_decay_shift);
> >
> > +/**
> > + * struct shared_runq - Per-LLC queue structure for enqueuing and migrating
> > + * runnable tasks within an LLC.
> > + *
> > + * WHAT
> > + * ====
> > + *
> > + * This structure enables the scheduler to be more aggressively work
> > + * conserving, by placing waking tasks on a per-LLC FIFO queue that can then be
> > + * pulled from when another core in the LLC is going to go idle.
> > + *
> > + * struct rq stores a pointer to its LLC's shared_runq via struct cfs_rq.
> > + * Waking tasks are enqueued in the calling CPU's struct shared_runq in
> > + * __enqueue_entity(), and are opportunistically pulled from the shared_runq
> > + * in newidle_balance(). Tasks enqueued in a shared_runq may be scheduled prior
> > + * to being pulled from the shared_runq, in which case they're simply dequeued
> > + * from the shared_runq in __dequeue_entity().
> > + *
> > + * There is currently no task-stealing between shared_runqs in different LLCs,
> > + * which means that shared_runq is not fully work conserving. This could be
> > + * added at a later time, with tasks likely only being stolen across
> > + * shared_runqs on the same NUMA node to avoid violating NUMA affinities.
> > + *
> > + * HOW
> > + * ===
> > + *
> > + * A shared_runq is comprised of a list, and a spinlock for synchronization.
> > + * Given that the critical section for a shared_runq is typically a fast list
> > + * operation, and that the shared_runq is localized to a single LLC, the
> > + * spinlock will typically only be contended on workloads that do little else
> > + * other than hammer the runqueue.
> > + *
> > + * WHY
> > + * ===
> > + *
> > + * As mentioned above, the main benefit of shared_runq is that it enables more
> > + * aggressive work conservation in the scheduler. This can benefit workloads
> > + * that benefit more from CPU utilization than from L1/L2 cache locality.
> > + *
> > + * shared_runqs are segmented across LLCs both to avoid contention on the
> > + * shared_runq spinlock by minimizing the number of CPUs that could contend on
> > + * it, as well as to strike a balance between work conservation, and L3 cache
> > + * locality.
> > + */
> > +struct shared_runq {
> > + struct list_head list;
> > + raw_spinlock_t lock;
> > +} ____cacheline_aligned;
> > +
> > #ifdef CONFIG_SMP
> > +
> > +static DEFINE_PER_CPU(struct shared_runq, shared_runqs);
> > +
> > +static struct shared_runq *rq_shared_runq(struct rq *rq)
> > +{
> > + return rq->cfs.shared_runq;
> > +}
> > +
> > +static void shared_runq_reassign_domains(void)
> > +{
> > + int i;
> > + struct shared_runq *shared_runq;
> > + struct rq *rq;
> > + struct rq_flags rf;
> > +
> > + for_each_possible_cpu(i) {
> > + rq = cpu_rq(i);
> > + shared_runq = &per_cpu(shared_runqs, per_cpu(sd_llc_id, i));
> > +
> > + rq_lock(rq, &rf);
> > + rq->cfs.shared_runq = shared_runq;
> > + rq_unlock(rq, &rf);
> > + }
> > +}
> > +
> > +static void __shared_runq_drain(struct shared_runq *shared_runq)
> > +{
> > + struct task_struct *p, *tmp;
> > +
> > + raw_spin_lock(&shared_runq->lock);
> > + list_for_each_entry_safe(p, tmp, &shared_runq->list, shared_runq_node)
> > + list_del_init(&p->shared_runq_node);
> > + raw_spin_unlock(&shared_runq->lock);
> > +}
> > +
> > +static void update_domains_fair(void)
> > +{
> > + int i;
> > + struct shared_runq *shared_runq;
> > +
> > + /* Avoid racing with SHARED_RUNQ enable / disable. */
> > + lockdep_assert_cpus_held();
> > +
> > + shared_runq_reassign_domains();
> > +
> > + /* Ensure every core sees its updated shared_runq pointers. */
> > + synchronize_rcu();
> > +
> > + /*
> > + * Drain all tasks from all shared_runq's to ensure there are no stale
> > + * tasks in any prior domain runq. This can cause us to drain live
> > + * tasks that would otherwise have been safe to schedule, but this
> > + * isn't a practical problem given how infrequently domains are
> > + * rebuilt.
> > + */
> > + for_each_possible_cpu(i) {
> > + shared_runq = &per_cpu(shared_runqs, i);
> > + __shared_runq_drain(shared_runq);
> > + }
> > +}
> > +
> > void shared_runq_toggle(bool enabling)
> > -{}
> > +{
> > + int cpu;
> > +
> > + if (enabling)
> > + return;
> > +
> > + /* Avoid racing with hotplug. */
> > + lockdep_assert_cpus_held();
> > +
> > + /* Ensure all cores have stopped enqueueing / dequeuing tasks. */
> > + synchronize_rcu();
> > +
> > + for_each_possible_cpu(cpu) {
> > + int sd_id;
> > +
> > + sd_id = per_cpu(sd_llc_id, cpu);
> > + if (cpu == sd_id)
> > + __shared_runq_drain(rq_shared_runq(cpu_rq(cpu)));
> > + }
> > +}
> > +
> > +static struct task_struct *shared_runq_pop_task(struct rq *rq)
> > +{
> > + struct task_struct *p;
> > + struct shared_runq *shared_runq;
> > +
> > + shared_runq = rq_shared_runq(rq);
> > + if (list_empty(&shared_runq->list))
> > + return NULL;
> > +
> > + raw_spin_lock(&shared_runq->lock);
> > + p = list_first_entry_or_null(&shared_runq->list, struct task_struct,
> > + shared_runq_node);
> > + if (p && is_cpu_allowed(p, cpu_of(rq)))
> > + list_del_init(&p->shared_runq_node);
>
> I wonder if we should remove the task from the list if
> "is_cpu_allowed()" return false.
>
> Consider the following scenario: A task that does not sleep, is pinned
> to single CPU. Since this is now at the head of the list, and cannot be
> moved, we leave it there, but since the task also never sleeps, it'll
> stay there, thus preventing the queue from doing its job.
Hmm, sorry, I may not be understanding your suggestion. If a task was
pinned to a single CPU, it would be dequeued from the shared_runq before
being pinned (see __set_cpus_allowed_ptr_locked()), and then would not
be added back to the shard in shared_runq_enqueue_task() because of
p->nr_cpus_allowed == 1. The task would also be dequeued from the shard
before it started running (unless I'm misunderstanding what you mean by
"a task that does not sleep"). Please let me know if I'm missing
something.
> Further implication ...
>
> > + else
> > + p = NULL;
> > + raw_spin_unlock(&shared_runq->lock);
> > +
> > + return p;
> > +}
> > +
> > +static void shared_runq_push_task(struct rq *rq, struct task_struct *p)
> > +{
> > + struct shared_runq *shared_runq;
> > +
> > + shared_runq = rq_shared_runq(rq);
> > + raw_spin_lock(&shared_runq->lock);
> > + list_add_tail(&p->shared_runq_node, &shared_runq->list);
> > + raw_spin_unlock(&shared_runq->lock);
> > +}
> >
> > static void shared_runq_enqueue_task(struct rq *rq, struct task_struct *p)
> > -{}
> > +{
> > + /*
> > + * Only enqueue the task in the shared runqueue if:
> > + *
> > + * - SHARED_RUNQ is enabled
> > + * - The task isn't pinned to a specific CPU
> > + */
> > + if (p->nr_cpus_allowed == 1)
> > + return;
> > +
> > + shared_runq_push_task(rq, p);
> > +}
> >
> > static int shared_runq_pick_next_task(struct rq *rq, struct rq_flags *rf)
> > {
> > - return 0;
> > + struct task_struct *p = NULL;
> > + struct rq *src_rq;
> > + struct rq_flags src_rf;
> > + int ret = -1;
> > +
> > + p = shared_runq_pop_task(rq);
> > + if (!p)
> > + return 0;
>
> ...
>
> Since we return 0 here in such a scenario, we'll take the old
> newidle_balance() path but ...
>
> > +
> > + rq_unpin_lock(rq, rf);
> > + raw_spin_rq_unlock(rq);
> > +
> > + src_rq = task_rq_lock(p, &src_rf);
> > +
> > + if (task_on_rq_queued(p) && !task_on_cpu(src_rq, p)) {
> > + update_rq_clock(src_rq);
> > + src_rq = move_queued_task(src_rq, &src_rf, p, cpu_of(rq));
> > + ret = 1;
> > + }
> > +
> > + if (src_rq != rq) {
> > + task_rq_unlock(src_rq, p, &src_rf);
> > + raw_spin_rq_lock(rq);
> > + } else {
> > + rq_unpin_lock(rq, &src_rf);
> > + raw_spin_unlock_irqrestore(&p->pi_lock, src_rf.flags);
> > + }
> > + rq_repin_lock(rq, rf);
> > +
> > + return ret;
> > }
> >
> > static void shared_runq_dequeue_task(struct task_struct *p)
> > -{}
> > +{
> > + struct shared_runq *shared_runq;
> > +
> > + if (!list_empty(&p->shared_runq_node)) {
> > + shared_runq = rq_shared_runq(task_rq(p));
> > + raw_spin_lock(&shared_runq->lock);
> > + /*
> > + * Need to double-check for the list being empty to avoid
> > + * racing with the list being drained on the domain recreation
> > + * or SHARED_RUNQ feature enable / disable path.
> > + */
> > + if (likely(!list_empty(&p->shared_runq_node)))
> > + list_del_init(&p->shared_runq_node);
> > + raw_spin_unlock(&shared_runq->lock);
> > + }
> > +}
> >
> > /*
> > * For asym packing, by default the lower numbered CPU has higher priority.
> > @@ -12093,6 +12308,16 @@ static int newidle_balance(struct rq *this_rq, struct rq_flags *rf)
> > rcu_read_lock();
> > sd = rcu_dereference_check_sched_domain(this_rq->sd);
> >
> > + /*
> > + * Skip <= LLC domains as they likely won't have any tasks if the
> > + * shared runq is empty.
> > + */
>
> ... now we skip all the way ahead of MC domain, overlooking any
> imbalance that might still exist within the SMT and MC groups
> since shared runq is not exactly empty.
>
> Let me know if I've got something wrong!
Yep, I mentioned this to Gautham as well in [0].
[0]: https://lore.kernel.org/all/20230818050355.GA5718@maniforge/
I agree that I think we should remove this heuristic from v4. Either
that, or add logic to iterate over the shared_runq until a viable task
is found.
>
> > + if (sched_feat(SHARED_RUNQ)) {
> > + sd = rcu_dereference(*this_cpu_ptr(&sd_llc));
> > + if (likely(sd))
> > + sd = sd->parent;
> > + }
>
> Speaking of skipping ahead of MC domain, I don't think this actually
> works since the domain traversal uses the "for_each_domain" macro
> which is defined as:
*blinks*
Uhhh, yeah, wow. Good catch!
> #define for_each_domain(cpu, __sd) \
> for (__sd = rcu_dereference_check_sched_domain(cpu_rq(cpu)->sd); \
> __sd; __sd = __sd->parent)
>
> The traversal starts from rq->sd overwriting your initialized value
> here. This is why we see "load_balance count on cpu newly idle" in
> Gautham's first report
> (https://lore.kernel.org/lkml/[email protected]/)
> to be non-zero.
>
> One way to do this would be as follows:
>
> static int newidle_balance() {
>
> ...
> for_each_domain(this_cpu, sd) {
>
> ...
> /* Skip balancing until LLc domain */
> if (sched_feat(SHARED_RUNQ) &&
> (sd->flags & SD_SHARE_PKG_RESOURCES))
> continue;
>
> ...
> }
> ...
> }
Yep, I think this makes sense to do.
> With this I see the newidle balance count for SMT and MC domain
> to be zero:
And indeed, I think this was the intention. Thanks again for catching
this. I'm excited to try this out when running benchmarks for v4.
> < ---------------------------------------- Category: newidle (SMT) ---------------------------------------- >
> load_balance cnt on cpu newly idle : 0 $ 0.000 $ [ 0.00000 ]
> --
> < ---------------------------------------- Category: newidle (MC) ---------------------------------------- >
> load_balance cnt on cpu newly idle : 0 $ 0.000 $ [ 0.00000 ]
> --
> < ---------------------------------------- Category: newidle (DIE) ---------------------------------------- >
> load_balance cnt on cpu newly idle : 2170 $ 9.319 $ [ 17.42832 ]
> --
> < ---------------------------------------- Category: newidle (NUMA) ---------------------------------------- >
> load_balance cnt on cpu newly idle : 30 $ 674.067 $ [ 0.24094 ]
> --
>
> Let me know if I'm missing something here :)
No, I think you're correct, we should be doing this. Assuming we want to
keep this heuristic, I think the block above is also correct so that we
properly account sd->max_newidle_lb_cost and rq->next_balance. Does that
make sense to you too?
>
> Note: The lb counts for DIE and NUMA are down since I'm experimenting
> with the implementation currently. I'll update of any new findings on
> the thread.
Ack, thank you for doing that.
Just FYI, I'll be on vacation for about 1.5 weeks starting tomorrow
afternoon. If I'm slow to respond, that's why.
Thanks,
David
On Thu, Aug 31, 2023 at 06:45:11PM +0800, Chen Yu wrote:
> On 2023-08-30 at 19:01:47 -0500, David Vernet wrote:
> > On Wed, Aug 30, 2023 at 02:17:09PM +0800, Chen Yu wrote:
> > >
> > > 5. Check the L2 cache miss rate.
> > > perf stat -e l2_rqsts.references,l2_request.miss sleep 10
> > > The results show that the L2 cache miss rate is nearly the same with/without
> > > shared_runqueue enabled.
> >
> > As mentioned below, I expect it would be interesting to also collect
> > icache / iTLB numbers. In my experience, poor uop cache locality will
> > also result in poor icache locality, though of course that depends on a
> > lot of other factors like alignment, how many (un)conditional branches
> > you have within some byte window, etc. If alignment, etc were the issue
> > though, we'd likely observe this also without SHARED_RUNQ.
> >
>
> [snip...]
>
> >
> > Interesting. As mentioned above, I expect we also see an increase in
> > iTLB and icache misses?
> >
>
> This is a good point, according to the perf topdown:
>
> SHARED_RUNQ is disabled:
>
> 13.0 % tma_frontend_bound
> 6.7 % tma_fetch_latency
> 0.3 % tma_itlb_misses
> 0.7 % tma_icache_misses
>
> itlb miss ratio is 13.0% * 6.7% * 0.3%
> icache miss ratio is 13.0% * 6.7% * 0.7%
>
> SHARED_RUNQ is enabled:
> 20.0 % tma_frontend_bound
> 11.6 % tma_fetch_latency
> 0.9 % tma_itlb_misses
> 0.5 % tma_icache_misses
>
> itlb miss ratio is 20.0% * 11.6% * 0.9%
> icache miss ratio is 20.0% * 11.6% * 0.5%
>
> So both icache and itlb miss ratio increase, and itlb miss increases more,
> although the bottleneck is neither icache nor itlb.
> And as you mentioned below, it depends on other factors, including the hardware
> settings, icache size, tlb size, DSB size, eg.
Thanks for collecting these stats. Good to know that things are making
sense and the data we're collecting are telling a consistent story.
> > This is something we deal with in HHVM. Like any other JIT engine /
> > compiler, it is heavily front-end CPU bound, and has very poor icache,
> > iTLB, and uop cache locality (also lots of branch resteers, etc).
> > SHARED_RUNQ actually helps this workload quite a lot, as explained in
> > the cover letter for the patch series. It makes sense that it would: uop
> > locality is really bad even without increasing CPU util. So we have no
> > reason not to migrate the task and hop on a CPU.
> >
>
> I see, this makes sense.
>
> > > I wonder, if SHARED_RUNQ can consider that, if a task is a long duration one,
> > > say, p->avg_runtime >= sysctl_migration_cost, maybe we should not put such task
> > > on the per-LLC shared runqueue? In this way it will not be migrated too offen
> > > so as to keep its locality(both in terms of L1/L2 cache and DSB).
> >
> > I'm hesitant to apply such heuristics to the feature. As mentioned
> > above, SHARED_RUNQ works very well on HHVM, despite its potential hit to
> > icache / iTLB / DSB locality. Those hhvmworker tasks run for a very long
> > time, sometimes upwards of 20+ms. They also tend to have poor L1 cache
> > locality in general even when they're scheduled on the same core they
> > were on before they were descheduled, so we observe better performance
> > if the task is migrated to a fully idle core rather than e.g. its
> > hypertwin if it's available. That's not something we can guarantee with
> > SHARED_RUNQ, but it hopefully illustrates the point that it's an example
> > of a workload that would suffer with such a heuristic.
> >
>
> OK, the hackbench is just a microbenchmark to help us evaluate
> what the impact SHARED_RUNQ could bring. If such heuristic heals
> hackbench but hurts the real workload then we can consider
> other direction.
>
> > Another point to consider is that performance implications that are a
> > result of Intel micro architectural details don't necessarily apply to
> > everyone. I'm not as familiar with the instruction decode pipeline on
> > AMD chips like Zen4. I'm sure they have a uop cache, but the size of
> > that cache, alignment requirements, the way that cache interfaces with
> > e.g. their version of the MITE / decoder, etc, are all going to be quite
> > different.
> >
>
> Yes, this is true.
>
> > In general, I think it's difficult for heuristics like this to suit all
> > possible workloads or situations (not that you're claiming it is). My
> > preference is to keep it as is so that it's easier for users to build a
> > mental model of what outcome they should expect if they use the feature.
> > Put another way: As a user of this feature, I'd be a lot more surprised
> > to see that I enabled it and CPU util stayed low, vs. enabling it and
> > seeing higher CPU util, but also degraded icache / iTLB locality.
> >
>
> Understand.
>
> > Let me know what you think, and thanks again for investing your time
> > into this.
> >
>
> Let me run other benchmarks to see if others are sensitive to
> the resource locality.
Great, thank you Chenyu.
FYI, I'll be on vacation for over a week starting later today, so my
responses may be delayed.
Thanks in advance for working on this. Looking forward to seeing the
results when I'm back at work.
Thanks,
David
On 2023-08-31 at 14:14:44 -0500, David Vernet wrote:
> On Thu, Aug 31, 2023 at 06:45:11PM +0800, Chen Yu wrote:
> > On 2023-08-30 at 19:01:47 -0500, David Vernet wrote:
> > > On Wed, Aug 30, 2023 at 02:17:09PM +0800, Chen Yu wrote:
[snip...]
> >
> > Let me run other benchmarks to see if others are sensitive to
> > the resource locality.
>
> Great, thank you Chenyu.
>
> FYI, I'll be on vacation for over a week starting later today, so my
> responses may be delayed.
>
> Thanks in advance for working on this. Looking forward to seeing the
> results when I'm back at work.
Sorry for late result. I applied your latest patch set on top of upstream
6.6-rc2 Commit 27bbf45eae9c(I pulled the latest commit from upstream yesterday).
The good news is that, there is overall slight stable improvement on tbench,
and no obvious regression on other benchmarks is observed on Sapphire Rapids
with 224 CPUs:
tbench throughput
======
case load baseline(std%) compare%( std%)
loopback 56-threads 1.00 ( 0.85) +4.35 ( 0.23)
loopback 112-threads 1.00 ( 0.38) +0.91 ( 0.05)
loopback 168-threads 1.00 ( 0.03) +2.96 ( 0.06)
loopback 224-threads 1.00 ( 0.09) +2.95 ( 0.05)
loopback 280-threads 1.00 ( 0.12) +2.48 ( 0.25)
loopback 336-threads 1.00 ( 0.23) +2.54 ( 0.14)
loopback 392-threads 1.00 ( 0.53) +2.91 ( 0.04)
loopback 448-threads 1.00 ( 0.10) +2.76 ( 0.07)
schbench 99.0th tail latency
========
case load baseline(std%) compare%( std%)
normal 1-mthreads 1.00 ( 0.32) +0.68 ( 0.32)
normal 2-mthreads 1.00 ( 1.83) +4.48 ( 3.31)
normal 4-mthreads 1.00 ( 0.83) -0.59 ( 1.80)
normal 8-mthreads 1.00 ( 4.47) -1.07 ( 3.49)
netperf throughput
=======
case load baseline(std%) compare%( std%)
TCP_RR 56-threads 1.00 ( 1.01) +1.37 ( 1.41)
TCP_RR 112-threads 1.00 ( 2.44) -0.94 ( 2.63)
TCP_RR 168-threads 1.00 ( 2.94) +3.22 ( 4.63)
TCP_RR 224-threads 1.00 ( 2.38) +2.83 ( 3.62)
TCP_RR 280-threads 1.00 ( 66.07) -7.26 ( 78.95)
TCP_RR 336-threads 1.00 ( 21.92) -0.50 ( 21.48)
TCP_RR 392-threads 1.00 ( 34.31) -0.00 ( 33.08)
TCP_RR 448-threads 1.00 ( 43.33) -0.31 ( 43.82)
UDP_RR 56-threads 1.00 ( 8.78) +3.84 ( 9.38)
UDP_RR 112-threads 1.00 ( 14.15) +1.84 ( 8.35)
UDP_RR 168-threads 1.00 ( 5.10) +2.95 ( 8.85)
UDP_RR 224-threads 1.00 ( 15.13) +2.76 ( 14.11)
UDP_RR 280-threads 1.00 ( 15.14) +2.14 ( 16.75)
UDP_RR 336-threads 1.00 ( 25.85) +1.64 ( 27.42)
UDP_RR 392-threads 1.00 ( 34.34) +0.40 ( 34.20)
UDP_RR 448-threads 1.00 ( 41.87) +1.41 ( 41.22)
We can have a re-run after the latest one is released.
thanks,
Chenyu
On Wed, 2023-08-09 at 17:12 -0500, David Vernet wrote:
Hi David,
I have been benchmarking the patch-set on POWER9 machine to understand
its impact. However, I've run into a recurring hard-lockups in
newidle_balance, specifically when SHARED_RUNQ feature is enabled. It
doesn't happen all the time, but it's something worth noting. I wanted
to inform you about this, and I can provide more details if needed.
-----------------------------------------
Some inital information regarding the hard-lockup:
Base Kernel:
-----------
Base kernel is upto commit 88c56cfeaec4 ("sched/fair: Block nohz
tick_stop when cfs bandwidth in use").
Patched Kernel:
-------------
Base Kernel + v3 (shared runqueue patch-set)(
https://lore.kernel.org/all/[email protected]/
)
The hard-lockup moslty occurs when running the Apache2 benchmarks with
ab (Apache HTTP benchmarking tool) on the patched kernel. However, this
problem is not exclusive to the mentioned benchmark and only occurs
while the SHARED_RUNQ feature is enabled. Disabling SHARED_RUNQ feature
prevents the occurrence of the lockup.
ab (Apache HTTP benchmarking tool):
https://httpd.apache.org/docs/2.4/programs/ab.html
Hardlockup with Patched Kernel:
------------------------------
[ 3289.727912][ C123] rcu: INFO: rcu_sched detected stalls on CPUs/tasks:
[ 3289.727943][ C123] rcu: 124-...0: (1 GPs behind) idle=f174/1/0x4000000000000000 softirq=12283/12289 fqs=732
[ 3289.727976][ C123] rcu: (detected by 123, t=2103 jiffies, g=127061, q=5517 ncpus=128)
[ 3289.728008][ C123] Sending NMI from CPU 123 to CPUs 124:
[ 3295.182378][ C123] CPU 124 didn't respond to backtrace IPI, inspecting paca.
[ 3295.182403][ C123] irq_soft_mask: 0x01 in_mce: 0 in_nmi: 0 current: 15 (ksoftirqd/124)
[ 3295.182421][ C123] Back trace of paca->saved_r1 (0xc000000de13e79b0) (possibly stale):
[ 3295.182437][ C123] Call Trace:
[ 3295.182456][ C123] [c000000de13e79b0] [c000000de13e7a70] 0xc000000de13e7a70 (unreliable)
[ 3295.182477][ C123] [c000000de13e7ac0] [0000000000000008] 0x8
[ 3295.182500][ C123] [c000000de13e7b70] [c000000de13e7c98] 0xc000000de13e7c98
[ 3295.182519][ C123] [c000000de13e7ba0] [c0000000001da8bc] move_queued_task+0x14c/0x280
[ 3295.182557][ C123] [c000000de13e7c30] [c0000000001f22d8] newidle_balance+0x648/0x940
[ 3295.182602][ C123] [c000000de13e7d30] [c0000000001f26ac] pick_next_task_fair+0x7c/0x680
[ 3295.182647][ C123] [c000000de13e7dd0] [c0000000010f175c] __schedule+0x15c/0x1040
[ 3295.182675][ C123] [c000000de13e7ec0] [c0000000010f26b4] schedule+0x74/0x140
[ 3295.182694][ C123] [c000000de13e7f30] [c0000000001c4994] smpboot_thread_fn+0x244/0x250
[ 3295.182731][ C123] [c000000de13e7f90] [c0000000001bc6e8] kthread+0x138/0x140
[ 3295.182769][ C123] [c000000de13e7fe0] [c00000000000ded8] start_kernel_thread+0x14/0x18
[ 3295.182806][ C123] rcu: rcu_sched kthread starved for 544 jiffies! g127061 f0x0 RCU_GP_DOING_FQS(6) ->state=0x0 ->cpu=66
[ 3295.182845][ C123] rcu: Unless rcu_sched kthread gets sufficient CPU time, OOM is now expected behavior.
[ 3295.182878][ C123] rcu: RCU grace-period kthread stack dump:
-----------------------------------------
[ 3943.438625][ C112] watchdog: CPU 112 self-detected hard LOCKUP @ _raw_spin_lock_irqsave+0x4c/0xc0
[ 3943.438631][ C112] watchdog: CPU 112 TB:115060212303626, last heartbeat TB:115054309631589 (11528ms ago)
[ 3943.438673][ C112] CPU: 112 PID: 2090 Comm: kworker/112:2 Tainted: G W L 6.5.0-rc2-00028-g7475adccd76b #51
[ 3943.438676][ C112] Hardware name: 8335-GTW POWER9 (raw) 0x4e1203 opal:skiboot-v6.5.3-35-g1851b2a06 PowerNV
[ 3943.438678][ C112] Workqueue: 0x0 (events)
[ 3943.438682][ C112] NIP: c0000000010ff01c LR: c0000000001d1064 CTR: c0000000001e8580
[ 3943.438684][ C112] REGS: c000007fffb6bd60 TRAP: 0900 Tainted: G W L (6.5.0-rc2-00028-g7475adccd76b)
[ 3943.438686][ C112] MSR: 9000000000009033 <SF,HV,EE,ME,IR,DR,RI,LE> CR: 24082222 XER: 00000000
[ 3943.438693][ C112] CFAR: 0000000000000000 IRQMASK: 1
[ 3943.438693][ C112] GPR00: c0000000001d1064 c000000e16d1fb20 c0000000014e8200 c000000e092fed3c
[ 3943.438693][ C112] GPR04: c000000e16d1fc58 c000000e092fe3c8 00000000000000e1 fffffffffffe0000
[ 3943.438693][ C112] GPR08: 0000000000000000 00000000000000e1 0000000000000000 c00000000299ccd8
[ 3943.438693][ C112] GPR12: 0000000024088222 c000007ffffb8300 c0000000001bc5b8 c000000deb46f740
[ 3943.438693][ C112] GPR16: 0000000000000008 c000000e092fe280 0000000000000001 c000007ffedd7b00
[ 3943.438693][ C112] GPR20: 0000000000000001 c0000000029a1280 0000000000000000 0000000000000001
[ 3943.438693][ C112] GPR24: 0000000000000000 c000000e092fed3c c000000e16d1fdf0 c00000000299ccd8
[ 3943.438693][ C112] GPR28: c000000e16d1fc58 c0000000021fbf00 c000007ffee6bf00 0000000000000001
[ 3943.438722][ C112] NIP [c0000000010ff01c] _raw_spin_lock_irqsave+0x4c/0xc0
[ 3943.438725][ C112] LR [c0000000001d1064] task_rq_lock+0x64/0x1b0
[ 3943.438727][ C112] Call Trace:
[ 3943.438728][ C112] [c000000e16d1fb20] [c000000e16d1fb60] 0xc000000e16d1fb60 (unreliable)
[ 3943.438731][ C112] [c000000e16d1fb50] [c000000e16d1fbf0] 0xc000000e16d1fbf0
[ 3943.438733][ C112] [c000000e16d1fbf0] [c0000000001f214c] newidle_balance+0x4bc/0x940
[ 3943.438737][ C112] [c000000e16d1fcf0] [c0000000001f26ac] pick_next_task_fair+0x7c/0x680
[ 3943.438739][ C112] [c000000e16d1fd90] [c0000000010f175c] __schedule+0x15c/0x1040
[ 3943.438743][ C112] [c000000e16d1fe80] [c0000000010f26b4] schedule+0x74/0x140
[ 3943.438747][ C112] [c000000e16d1fef0] [c0000000001afd44] worker_thread+0x134/0x580
[ 3943.438749][ C112] [c000000e16d1ff90] [c0000000001bc6e8] kthread+0x138/0x140
[ 3943.438753][ C112] [c000000e16d1ffe0] [c00000000000ded8] start_kernel_thread+0x14/0x18
[ 3943.438756][ C112] Code: 63e90001 992d0932 a12d0008 3ce0fffe 5529083c 61290001 7d001
-----------------------------------------
System configuration:
--------------------
# lscpu
Architecture: ppc64le
Byte Order: Little Endian
CPU(s): 128
On-line CPU(s) list: 0-127
Thread(s) per core: 4
Core(s) per socket: 16
Socket(s): 2
NUMA node(s): 8
Model: 2.3 (pvr 004e 1203)
Model name: POWER9 (raw), altivec supported
Frequency boost: enabled
CPU max MHz: 3800.0000
CPU min MHz: 2300.0000
L1d cache: 1 MiB
L1i cache: 1 MiB
NUMA node0 CPU(s): 64-127
NUMA node8 CPU(s): 0-63
NUMA node250 CPU(s):
NUMA node251 CPU(s):
NUMA node252 CPU(s):
NUMA node253 CPU(s):
NUMA node254 CPU(s):
NUMA node255 CPU(s):
# uname -r
6.5.0-rc2-00028-g7475adccd76b
# cat /sys/kernel/debug/sched/features
GENTLE_FAIR_SLEEPERS START_DEBIT NO_NEXT_BUDDY LAST_BUDDY
CACHE_HOT_BUDDY WAKEUP_PREEMPTION NO_HRTICK NO_HRTICK_DL NO_DOUBLE_TICK
NONTASK_CAPACITY TTWU_QUEUE NO_SIS_PROP SIS_UTIL NO_WARN_DOUBLE_CLOCK
RT_PUSH_IPI NO_RT_RUNTIME_SHARE NO_LB_MIN ATTACH_AGE_LOAD WA_IDLE
WA_WEIGHT WA_BIAS UTIL_EST UTIL_EST_FASTUP NO_LATENCY_WARN ALT_PERIOD
BASE_SLICE HZ_BW SHARED_RUNQ
-----------------------------------------
Please let me know if I've missed anything here. I'll continue
investigating and share any additional information I find.
Thanks and Regards,
Aboorva
> Changes
> -------
>
> This is v3 of the shared runqueue patchset. This patch set is based
> off
> of commit 88c56cfeaec4 ("sched/fair: Block nohz tick_stop when cfs
> bandwidth in use") on the sched/core branch of tip.git.
>
> v1 (RFC):
> https://lore.kernel.org/lkml/[email protected]/
> v2:
> https://lore.kernel.org/lkml/[email protected]/
>
> v2 -> v3 changes:
> - Don't leave stale tasks in the lists when the SHARED_RUNQ feature
> is
> disabled (Abel Wu)
>
> - Use raw spin lock instead of spinlock_t (Peter)
>
> - Fix return value from shared_runq_pick_next_task() to match the
> semantics expected by newidle_balance() (Gautham, Abel)
>
> - Fold patch __enqueue_entity() / __dequeue_entity() into previous
> patch
> (Peter)
>
> - Skip <= LLC domains in newidle_balance() if SHARED_RUNQ is enabled
> (Peter)
>
> - Properly support hotplug and recreating sched domains (Peter)
>
> - Avoid unnecessary task_rq_unlock() + raw_spin_rq_lock() when src_rq
> ==
> target_rq in shared_runq_pick_next_task() (Abel)
>
> - Only issue list_del_init() in shared_runq_dequeue_task() if the
> task
> is still in the list after acquiring the lock (Aaron Lu)
>
> - Slightly change shared_runq_shard_idx() to make it more likely to
> keep
> SMT siblings on the same bucket (Peter)
>
> v1 -> v2 changes:
> - Change name from swqueue to shared_runq (Peter)
>
> - Shard per-LLC shared runqueues to avoid contention on scheduler-
> heavy
> workloads (Peter)
>
> - Pull tasks from the shared_runq in newidle_balance() rather than in
> pick_next_task_fair() (Peter and Vincent)
>
> - Rename a few functions to reflect their actual purpose. For
> example,
> shared_runq_dequeue_task() instead of swqueue_remove_task() (Peter)
>
> - Expose move_queued_task() from core.c rather than migrate_task_to()
> (Peter)
>
> - Properly check is_cpu_allowed() when pulling a task from a
> shared_runq
> to ensure it can actually be migrated (Peter and Gautham)
>
> - Dropped RFC tag
>
> Overview
> ========
>
> The scheduler must constantly strike a balance between work
> conservation, and avoiding costly migrations which harm performance
> due
> to e.g. decreased cache locality. The matter is further complicated
> by
> the topology of the system. Migrating a task between cores on the
> same
> LLC may be more optimal than keeping a task local to the CPU, whereas
> migrating a task between LLCs or NUMA nodes may tip the balance in
> the
> other direction.
>
> With that in mind, while CFS is by and large mostly a work conserving
> scheduler, there are certain instances where the scheduler will
> choose
> to keep a task local to a CPU, when it would have been more optimal
> to
> migrate it to an idle core.
>
> An example of such a workload is the HHVM / web workload at Meta.
> HHVM
> is a VM that JITs Hack and PHP code in service of web requests. Like
> other JIT / compilation workloads, it tends to be heavily CPU bound,
> and
> exhibit generally poor cache locality. To try and address this, we
> set
> several debugfs (/sys/kernel/debug/sched) knobs on our HHVM
> workloads:
>
> - migration_cost_ns -> 0
> - latency_ns -> 20000000
> - min_granularity_ns -> 10000000
> - wakeup_granularity_ns -> 12000000
>
> These knobs are intended both to encourage the scheduler to be as
> work
> conserving as possible (migration_cost_ns -> 0), and also to keep
> tasks
> running for relatively long time slices so as to avoid the overhead
> of
> context switching (the other knobs). Collectively, these knobs
> provide a
> substantial performance win; resulting in roughly a 20% improvement
> in
> throughput. Worth noting, however, is that this improvement is _not_
> at
> full machine saturation.
>
> That said, even with these knobs, we noticed that CPUs were still
> going
> idle even when the host was overcommitted. In response, we wrote the
> "shared runqueue" (SHARED_RUNQ) feature proposed in this patch set.
> The
> idea behind SHARED_RUNQ is simple: it enables the scheduler to be
> more
> aggressively work conserving by placing a waking task into a sharded
> per-LLC FIFO queue that can be pulled from by another core in the LLC
> FIFO queue which can then be pulled from before it goes idle.
>
> With this simple change, we were able to achieve a 1 - 1.6%
> improvement
> in throughput, as well as a small, consistent improvement in p95 and
> p99
> latencies, in HHVM. These performance improvements were in addition
> to
> the wins from the debugfs knobs mentioned above, and to other
> benchmarks
> outlined below in the Results section.
>
> Design
> ======
>
> Note that the design described here reflects sharding, which is the
> implementation added in the final patch of the series (following the
> initial unsharded implementation added in patch 6/7). The design is
> described that way in this commit summary as the benchmarks described
> in
> the results section below all reflect a sharded SHARED_RUNQ.
>
> The design of SHARED_RUNQ is quite simple. A shared_runq is simply a
> list of struct shared_runq_shard objects, which itself is simply a
> struct list_head of tasks, and a spinlock:
>
> struct shared_runq_shard {
> struct list_head list;
> raw_spinlock_t lock;
> } ____cacheline_aligned;
>
> struct shared_runq {
> u32 num_shards;
> struct shared_runq_shard shards[];
> } ____cacheline_aligned;
>
> We create a struct shared_runq per LLC, ensuring they're in their own
> cachelines to avoid false sharing between CPUs on different LLCs, and
> we
> create a number of struct shared_runq_shard objects that are housed
> there.
>
> When a task first wakes up, it enqueues itself in the
> shared_runq_shard
> of its current LLC at the end of enqueue_task_fair(). Enqueues only
> happen if the task was not manually migrated to the current core by
> select_task_rq(), and is not pinned to a specific CPU.
>
> A core will pull a task from the shards in its LLC's shared_runq at
> the
> beginning of newidle_balance().
>
> Difference between SHARED_RUNQ and SIS_NODE
> ===========================================
>
> In [0] Peter proposed a patch that addresses Tejun's observations
> that
> when workqueues are targeted towards a specific LLC on his Zen2
> machine
> with small CCXs, that there would be significant idle time due to
> select_idle_sibling() not considering anything outside of the current
> LLC.
>
> This patch (SIS_NODE) is essentially the complement to the proposal
> here. SID_NODE causes waking tasks to look for idle cores in
> neighboring
> LLCs on the same die, whereas SHARED_RUNQ causes cores about to go
> idle
> to look for enqueued tasks. That said, in its current form, the two
> features at are a different scope as SIS_NODE searches for idle cores
> between LLCs, while SHARED_RUNQ enqueues tasks within a single LLC.
>
> The patch was since removed in [1], and we compared the results to
> SHARED_RUNQ (previously called "swqueue") in [2]. SIS_NODE did not
> outperform SHARED_RUNQ on any of the benchmarks, so we elect to not
> compare against it again for this v2 patch set.
>
> [0]:
> https://lore.kernel.org/all/[email protected]/
> [1]:
> https://lore.kernel.org/all/[email protected]/
> [2]:
> https://lore.kernel.org/lkml/[email protected]/
>
> Worth noting as well is that pointed out in [3] that the logic behind
> including SIS_NODE in the first place should apply to SHARED_RUNQ
> (meaning that e.g. very small Zen2 CPUs with only 3/4 cores per LLC
> should benefit from having a single shared_runq stretch across
> multiple
> LLCs). I drafted a patch that implements this by having a minimum LLC
> size for creating a shard, and stretches a shared_runq across
> multiple
> LLCs if they're smaller than that size, and sent it to Tejun to test
> on
> his Zen2. Tejun reported back that SIS_NODE did not seem to make a
> difference:
>
> [3]:
> https://lore.kernel.org/lkml/[email protected]/
>
> o____________o__________o
> | mean | Variance |
> o------------o----------o
> Vanilla: | 108.84s | 0.0057 |
> NO_SHARED_RUNQ: | 108.82s | 0.119s |
> SHARED_RUNQ: | 108.17s | 0.038s |
> SHARED_RUNQ w/ SIS_NODE: | 108.87s | 0.111s |
> o------------o----------o
>
> I similarly tried running kcompile on SHARED_RUNQ with SIS_NODE on my
> 7950X Zen3, but didn't see any gain relative to plain SHARED_RUNQ
> (though
> a gain was observed relative to NO_SHARED_RUNQ, as described below).
>
> Results
> =======
>
> Note that the motivation for the shared runqueue feature was
> originally
> arrived at using experiments in the sched_ext framework that's
> currently
> being proposed upstream. The ~1 - 1.6% improvement in HHVM throughput
> is similarly visible using work-conserving sched_ext schedulers (even
> very simple ones like global FIFO).
>
> In both single and multi socket / CCX hosts, this can measurably
> improve
> performance. In addition to the performance gains observed on our
> internal web workloads, we also observed an improvement in common
> workloads such as kernel compile and hackbench, when running shared
> runqueue.
>
> On the other hand, some workloads suffer from SHARED_RUNQ. Workloads
> that hammer the runqueue hard, such as netperf UDP_RR, or schbench -L
> -m 52 -p 512 -r 10 -t 1. This can be mitigated somewhat by sharding
> the
> shared datastructures within a CCX, but it doesn't seem to eliminate
> all
> contention in every scenario. On the positive side, it seems that
> sharding does not materially harm the benchmarks run for this patch
> series; and in fact seems to improve some workloads such as kernel
> compile.
>
> Note that for the kernel compile workloads below, the compilation was
> done by running make -j$(nproc) built-in.a on several different types
> of
> hosts configured with make allyesconfig on commit a27648c74210 ("afs:
> Fix setting of mtime when creating a file/dir/symlink") on Linus'
> tree
> (boost and turbo were disabled on all of these hosts when the
> experiments were performed).
>
> Finally, note that these results were from the patch set built off of
> commit ebb83d84e49b ("sched/core: Avoid multiple calling
> update_rq_clock() in __cfsb_csd_unthrottle()") on the sched/core
> branch
> of tip.git for easy comparison with the v2 patch set results. The
> patches in their final form from this set were rebased onto commit
> 88c56cfeaec4 ("sched/fair: Block nohz tick_stop when cfs bandwidth in
> use") on the sched/core branch of tip.git.
>
> === Single-socket | 16 core / 32 thread | 2-CCX | AMD 7950X Zen4 ===
>
> CPU max MHz: 5879.8818
> CPU min MHz: 3000.0000
>
> Command: make -j$(nproc) built-in.a
> o____________o__________o
> | mean | Variance |
> o------------o----------o
> NO_SHARED_RUNQ: | 581.95s | 2.639s |
> SHARED_RUNQ: | 577.02s | 0.084s |
> o------------o----------o
>
> Takeaway: SHARED_RUNQ results in a statistically significant ~.85%
> improvement over NO_SHARED_RUNQ. This suggests that enqueuing tasks
> in
> the shared runqueue on every enqueue improves work conservation, and
> thanks to sharding, does not result in contention.
>
> Command: hackbench --loops 10000
> o____________o__________o
> | mean | Variance |
> o------------o----------o
> NO_SHARED_RUNQ: | 2.2492s | .00001s |
> SHARED_RUNQ: | 2.0217s | .00065s |
> o------------o----------o
>
> Takeaway: SHARED_RUNQ in both forms performs exceptionally well
> compared
> to NO_SHARED_RUNQ here, beating it by over 10%. This was a surprising
> result given that it seems advantageous to err on the side of
> avoiding
> migration in hackbench given that tasks are short lived in sending
> only
> 10k bytes worth of messages, but the results of the benchmark would
> seem
> to suggest that minimizing runqueue delays is preferable.
>
> Command:
> for i in `seq 128`; do
> netperf -6 -t UDP_RR -c -C -l $runtime &
> done
> o_______________________o
> | Throughput | Variance |
> o-----------------------o
> NO_SHARED_RUNQ: | 25037.45 | 2243.44 |
> SHARED_RUNQ: | 24952.50 | 1268.06 |
> o-----------------------o
>
> Takeaway: No statistical significance, though it is worth noting that
> there is no regression for shared runqueue on the 7950X, while there
> is
> a small regression on the Skylake and Milan hosts for SHARED_RUNQ as
> described below.
>
> === Single-socket | 18 core / 36 thread | 1-CCX | Intel Skylake ===
>
> CPU max MHz: 1601.0000
> CPU min MHz: 800.0000
>
> Command: make -j$(nproc) built-in.a
> o____________o__________o
> | mean | Variance |
> o------------o----------o
> NO_SHARED_RUNQ: | 1517.44s | 2.8322s |
> SHARED_RUNQ: | 1516.51s | 2.9450s |
> o------------o----------o
>
> Takeaway: There's on statistically significant gain here. I observed
> what I claimed was a .23% win in v2, but it appears that this is not
> actually statistically significant.
>
> Command: hackbench --loops 10000
> o____________o__________o
> | mean | Variance |
> o------------o----------o
> NO_SHARED_RUNQ: | 5.3370s | .0012s |
> SHARED_RUNQ: | 5.2668s | .0033s |
> o------------o----------o
>
> Takeaway: SHARED_RUNQ results in a ~1.3% improvement over
> NO_SHARED_RUNQ. Also statistically significant, but smaller than the
> 10+% improvement observed on the 7950X.
>
> Command: netperf -n $(nproc) -l 60 -t TCP_RR
> for i in `seq 128`; do
> netperf -6 -t UDP_RR -c -C -l $runtime &
> done
> o_______________________o
> | Throughput | Variance |
> o-----------------------o
> NO_SHARED_RUNQ: | 15699.32 | 377.01 |
> SHARED_RUNQ: | 14966.42 | 714.13 |
> o-----------------------o
>
> Takeaway: NO_SHARED_RUNQ beats SHARED_RUNQ by ~4.6%. This result
> makes
> sense -- the workload is very heavy on the runqueue, so enqueuing
> tasks
> in the shared runqueue in __enqueue_entity() would intuitively result
> in
> increased contention on the shard lock.
>
> === Single-socket | 72-core | 6-CCX | AMD Milan Zen3 ===
>
> CPU max MHz: 700.0000
> CPU min MHz: 700.0000
>
> Command: make -j$(nproc) built-in.a
> o____________o__________o
> | mean | Variance |
> o------------o----------o
> NO_SHARED_RUNQ: | 1568.55s | 0.1568s |
> SHARED_RUNQ: | 1568.26s | 1.2168s |
> o------------o----------o
>
> Takeaway: No statistically significant difference here. It might be
> worth experimenting with work stealing in a follow-on patch set.
>
> Command: hackbench --loops 10000
> o____________o__________o
> | mean | Variance |
> o------------o----------o
> NO_SHARED_RUNQ: | 5.2716s | .00143s |
> SHARED_RUNQ: | 5.1716s | .00289s |
> o------------o----------o
>
> Takeaway: SHARED_RUNQ again wins, by about 2%.
>
> Command: netperf -n $(nproc) -l 60 -t TCP_RR
> for i in `seq 128`; do
> netperf -6 -t UDP_RR -c -C -l $runtime &
> done
> o_______________________o
> | Throughput | Variance |
> o-----------------------o
> NO_SHARED_RUNQ: | 17482.03 | 4675.99 |
> SHARED_RUNQ: | 16697.25 | 9812.23 |
> o-----------------------o
>
> Takeaway: Similar to the Skylake runs, NO_SHARED_RUNQ still beats
> SHARED_RUNQ, this time by ~4.5%. It's worth noting that in v2, the
> NO_SHARED_RUNQ was only ~1.8% faster. The variance is very high here,
> so
> the results of this benchmark should be taken with a large grain of
> salt (noting that we do consistently see NO_SHARED_RUNQ on top due to
> not contending on the shard lock).
>
> Finally, let's look at how sharding affects the following schbench
> incantation suggested by Chris in [4]:
>
> schbench -L -m 52 -p 512 -r 10 -t 1
>
> [4]:
> https://lore.kernel.org/lkml/[email protected]/
>
> The TL;DR is that sharding improves things a lot, but doesn't
> completely
> fix the problem. Here are the results from running the schbench
> command
> on the 18 core / 36 thread single CCX, single-socket Skylake:
>
> -------------------------------------------------------------------
> -------------------------------------------------------------------
> -----------------------------------------------------------------
> class name con-bounces contentions waittime-
> min waittime-max waittime-total waittime-avg acq-
> bounces acquisitions holdtime-min holdtime-max holdtime-
> total holdtime-avg
> -------------------------------------------------------------------
> -------------------------------------------------------------------
> -----------------------------------------------------------------
>
> &shard-
> >lock: 31510503 31510711 0.08 19.98
> 168932319.64 5.36 31700383 31843851 0.0
> 3 17.50 10273968.33 0.32
> ------------
> &shard->lock 15731657 [<0000000068c0fd75>]
> pick_next_task_fair+0x4dd/0x510
> &shard->lock 15756516 [<000000001faf84f9>]
> enqueue_task_fair+0x459/0x530
> &shard->lock 21766 [<00000000126ec6ab>]
> newidle_balance+0x45a/0x650
> &shard->lock 772 [<000000002886c365>]
> dequeue_task_fair+0x4c9/0x540
> ------------
> &shard->lock 23458 [<00000000126ec6ab>]
> newidle_balance+0x45a/0x650
> &shard->lock 16505108 [<000000001faf84f9>]
> enqueue_task_fair+0x459/0x530
> &shard->lock 14981310 [<0000000068c0fd75>]
> pick_next_task_fair+0x4dd/0x510
> &shard->lock 835 [<000000002886c365>]
> dequeue_task_fair+0x4c9/0x540
>
> These results are when we create only 3 shards (16 logical cores per
> shard), so the contention may be a result of overly-coarse sharding.
> If
> we run the schbench incantation with no sharding whatsoever, we see
> the
> following significantly worse lock stats contention:
>
> -------------------------------------------------------------------
> -------------------------------------------------------------------
> -------------------------------------------------------------------
> ----
> class name con-bounces contentions waittime-
> min waittime-max waittime-total waittime-avg acq-
> bounces acquisitions holdtime-min holdtime-max holdtime-
> total holdtime-avg
> -------------------------------------------------------------------
> -------------------------------------------------------------------
> -------------------------------------------------------------------
> ----
>
> &shard-
> >lock: 117868635 118361486 0.09 393.01
> 1250954097.25 10.57 119345882 119780601
> 0.05 343.35 38313419.51 0.32
> ------------
> &shard->lock 59169196 [<0000000060507011>]
> __enqueue_entity+0xdc/0x110
> &shard->lock 59084239 [<00000000f1c67316>]
> __dequeue_entity+0x78/0xa0
> &shard->lock 108051 [<00000000084a6193>]
> newidle_balance+0x45a/0x650
> ------------
> &shard->lock 60028355 [<0000000060507011>]
> __enqueue_entity+0xdc/0x110
> &shard->lock 119882 [<00000000084a6193>]
> newidle_balance+0x45a/0x650
> &shard->lock 58213249 [<00000000f1c67316>]
> __dequeue_entity+0x78/0xa0
>
> The contention is ~3-4x worse if we don't shard at all. This roughly
> matches the fact that we had 3 shards on the first workload run
> above.
> If we make the shards even smaller, the contention is comparably much
> lower:
>
> -------------------------------------------------------------------
> -------------------------------------------------------------------
> ----------------------------------------------------------
> class name con-bounces contentions waittime-
> min waittime-max waittime-total waittime-avg acq-
> bounces acquisitions holdtime-min holdtime-max holdtime-
> total holdtime-avg
> -------------------------------------------------------------------
> -------------------------------------------------------------------
> ----------------------------------------------------------
>
> &shard-
> >lock: 13839849 13877596 0.08 13.23 5
> 389564.95 0.39 46910241 48069307 0.06
> 16.40 16534469.35 0.34
> ------------
> &shard->lock 3559 [<00000000ea455dcc>]
> newidle_balance+0x45a/0x650
> &shard->lock 6992418 [<000000002266f400>]
> __dequeue_entity+0x78/0xa0
> &shard->lock 6881619 [<000000002a62f2e0>]
> __enqueue_entity+0xdc/0x110
> ------------
> &shard->lock 6640140 [<000000002266f400>]
> __dequeue_entity+0x78/0xa0
> &shard->lock 3523 [<00000000ea455dcc>]
> newidle_balance+0x45a/0x650
> &shard->lock 7233933 [<000000002a62f2e0>]
> __enqueue_entity+0xdc/0x110
>
> Interestingly, SHARED_RUNQ performs worse than NO_SHARED_RUNQ on the
> schbench
> benchmark on Milan as well, but we contend more on the rq lock than
> the
> shard lock:
>
> -------------------------------------------------------------------
> -------------------------------------------------------------------
> -----------------------------------------------------------
> class name con-bounces contentions waittime-
> min waittime-max waittime-total waittime-avg acq-
> bounces acquisitions holdtime-min holdtime-max holdtime-
> total holdtime-avg
> -------------------------------------------------------------------
> -------------------------------------------------------------------
> -----------------------------------------------------------
>
> &rq-
> >__lock: 9617614 9656091 0.10 79.64
> 69665812.00 7.21 18092700 67652829 0.11
> 82.38 344524858.87 5.09
> -----------
> &rq->__lock 6301611 [<000000003e63bf26>]
> task_rq_lock+0x43/0xe0
> &rq->__lock 2530807 [<00000000516703f0>]
> __schedule+0x72/0xaa0
> &rq->__lock 109360 [<0000000011be1562>]
> raw_spin_rq_lock_nested+0xa/0x10
> &rq->__lock 178218 [<00000000c38a30f9>]
> sched_ttwu_pending+0x3d/0x170
> -----------
> &rq->__lock 3245506 [<00000000516703f0>]
> __schedule+0x72/0xaa0
> &rq->__lock 1294355 [<00000000c38a30f9>]
> sched_ttwu_pending+0x3d/0x170
> &rq->__lock 2837804 [<000000003e63bf26>]
> task_rq_lock+0x43/0xe0
> &rq->__lock 1627866 [<0000000011be1562>]
> raw_spin_rq_lock_nested+0xa/0x10
>
> .....................................................................
> .....................................................................
> ........................................................
>
> &shard-
> >lock: 7338558 7343244 0.10 35.97 7
> 173949.14 0.98 30200858 32679623 0.08
> 35.59 16270584.52 0.50
> ------------
> &shard->lock 2004142 [<00000000f8aa2c91>]
> __dequeue_entity+0x78/0xa0
> &shard->lock 2611264 [<00000000473978cc>]
> newidle_balance+0x45a/0x650
> &shard->lock 2727838 [<0000000028f55bb5>]
> __enqueue_entity+0xdc/0x110
> ------------
> &shard->lock 2737232 [<00000000473978cc>]
> newidle_balance+0x45a/0x650
> &shard->lock 1693341 [<00000000f8aa2c91>]
> __dequeue_entity+0x78/0xa0
> &shard->lock 2912671 [<0000000028f55bb5>]
> __enqueue_entity+0xdc/0x110
>
> .....................................................................
> .....................................................................
> .........................................................
>
> If we look at the lock stats with SHARED_RUNQ disabled, the rq lock
> still
> contends the most, but it's significantly less than with it enabled:
>
> -------------------------------------------------------------------
> -------------------------------------------------------------------
> --------------------------------------------------------------
> class name con-bounces contentions waittime-
> min waittime-max waittime-total waittime-avg acq-
> bounces acquisitions holdtime-min holdtime-max holdtime-
> total holdtime-avg
> -------------------------------------------------------------------
> -------------------------------------------------------------------
> --------------------------------------------------------------
>
> &rq-
> >__lock: 791277 791690 0.12 110.54
> 4889787.63 6.18 1575996 62390275 0.1
> 3 112.66 316262440.56 5.07
> -----------
> &rq->__lock 263343 [<00000000516703f0>]
> __schedule+0x72/0xaa0
> &rq->__lock 19394 [<0000000011be1562>]
> raw_spin_rq_lock_nested+0xa/0x10
> &rq->__lock 4143 [<000000003b542e83>]
> __task_rq_lock+0x51/0xf0
> &rq->__lock 51094 [<00000000c38a30f9>]
> sched_ttwu_pending+0x3d/0x170
> -----------
> &rq->__lock 23756 [<0000000011be1562>]
> raw_spin_rq_lock_nested+0xa/0x10
> &rq->__lock 379048 [<00000000516703f0>]
> __schedule+0x72/0xaa0
> &rq->__lock 677 [<000000003b542e83>]
> __task_rq_lock+0x51/0xf0
>
> Worth noting is that increasing the granularity of the shards in
> general
> improves very runqueue-heavy workloads such as netperf UDP_RR and
> this
> schbench command, but it doesn't necessarily make a big difference
> for
> every workload, or for sufficiently small CCXs such as the 7950X. It
> may
> make sense to eventually allow users to control this with a debugfs
> knob, but for now we'll elect to choose a default that resulted in
> good
> performance for the benchmarks run for this patch series.
>
> Conclusion
> ==========
>
> SHARED_RUNQ in this form provides statistically significant wins for
> several types of workloads, and various CPU topologies. The reason
> for
> this is roughly the same for all workloads: SHARED_RUNQ encourages
> work
> conservation inside of a CCX by having a CPU do an O(# per-LLC
> shards)
> iteration over the shared_runq shards in an LLC. We could similarly
> do
> an O(n) iteration over all of the runqueues in the current LLC when a
> core is going idle, but that's quite costly (especially for larger
> LLCs), and sharded SHARED_RUNQ seems to provide a performant middle
> ground between doing an O(n) walk, and doing an O(1) pull from a
> single
> per-LLC shared runq.
>
> For the workloads above, kernel compile and hackbench were clear
> winners
> for SHARED_RUNQ (especially in __enqueue_entity()). The reason for
> the
> improvement in kernel compile is of course that we have a heavily
> CPU-bound workload where cache locality doesn't mean much; getting a
> CPU
> is the #1 goal. As mentioned above, while I didn't expect to see an
> improvement in hackbench, the results of the benchmark suggest that
> minimizing runqueue delays is preferable to optimizing for L1/L2
> locality.
>
> Not all workloads benefit from SHARED_RUNQ, however. Workloads that
> hammer the runqueue hard, such as netperf UDP_RR, or schbench -L -m
> 52
> -p 512 -r 10 -t 1, tend to run into contention on the shard locks;
> especially when enqueuing tasks in __enqueue_entity(). This can be
> mitigated significantly by sharding the shared datastructures within
> a
> CCX, but it doesn't eliminate all contention, as described above.
>
> Worth noting as well is that Gautham Shenoy ran some interesting
> experiments on a few more ideas in [5], such as walking the
> shared_runq
> on the pop path until a task is found that can be migrated to the
> calling CPU. I didn't run those experiments in this patch set, but it
> might be worth doing so.
>
> [5]:
> https://lore.kernel.org/lkml/[email protected]/
>
> Gautham also ran some other benchmarks in [6], which we may want to
> again try on this v3, but with boost disabled.
>
> [6]:
> https://lore.kernel.org/lkml/[email protected]/
>
> Finally, while SHARED_RUNQ in this form encourages work conservation,
> it
> of course does not guarantee it given that we don't implement any
> kind
> of work stealing between shared_runq's. In the future, we could
> potentially push CPU utilization even higher by enabling work
> stealing
> between shared_runq's, likely between CCXs on the same NUMA node.
>
> Originally-by: Roman Gushchin <[email protected]>
> Signed-off-by: David Vernet <[email protected]>
>
> David Vernet (7):
> sched: Expose move_queued_task() from core.c
> sched: Move is_cpu_allowed() into sched.h
> sched: Check cpu_active() earlier in newidle_balance()
> sched: Enable sched_feat callbacks on enable/disable
> sched/fair: Add SHARED_RUNQ sched feature and skeleton calls
> sched: Implement shared runqueue in CFS
> sched: Shard per-LLC shared runqueues
>
> include/linux/sched.h | 2 +
> kernel/sched/core.c | 52 ++----
> kernel/sched/debug.c | 18 ++-
> kernel/sched/fair.c | 340
> +++++++++++++++++++++++++++++++++++++++-
> kernel/sched/features.h | 1 +
> kernel/sched/sched.h | 56 ++++++-
> kernel/sched/topology.c | 4 +-
> 7 files changed, 420 insertions(+), 53 deletions(-)
>
On Mon, Nov 27, 2023 at 01:58:34PM +0530, Aboorva Devarajan wrote:
> On Wed, 2023-08-09 at 17:12 -0500, David Vernet wrote:
>
> Hi David,
>
> I have been benchmarking the patch-set on POWER9 machine to understand
> its impact. However, I've run into a recurring hard-lockups in
> newidle_balance, specifically when SHARED_RUNQ feature is enabled. It
> doesn't happen all the time, but it's something worth noting. I wanted
> to inform you about this, and I can provide more details if needed.
Hello Aboorva,
Thank you for testing out this patch set and for the report. One issue
that v4 will correct is that the shared_runq list could become corrupted
if you enable and disable the feature, as a stale task could remain in
the list after the feature has been disabled. I'll be including a fix
for that in v4, which I'm currently benchmarking, but other stuff keeps
seeming to preempt it.
By any chance, did you run into this when you were enabling / disabling
the feature? Or did you just enable it once and then hit this issue
after some time, which would indicate a different issue? I'm trying to
repro using ab, but haven't been successful thus far. If you're able to
repro consistently, it might be useful to run with CONFIG_LIST_DEBUG=y.
Thanks,
David
> -----------------------------------------
>
> Some inital information regarding the hard-lockup:
>
> Base Kernel:
> -----------
>
> Base kernel is upto commit 88c56cfeaec4 ("sched/fair: Block nohz
> tick_stop when cfs bandwidth in use").
>
> Patched Kernel:
> -------------
>
> Base Kernel + v3 (shared runqueue patch-set)(
> https://lore.kernel.org/all/[email protected]/
> )
>
> The hard-lockup moslty occurs when running the Apache2 benchmarks with
> ab (Apache HTTP benchmarking tool) on the patched kernel. However, this
> problem is not exclusive to the mentioned benchmark and only occurs
> while the SHARED_RUNQ feature is enabled. Disabling SHARED_RUNQ feature
> prevents the occurrence of the lockup.
>
> ab (Apache HTTP benchmarking tool):
> https://httpd.apache.org/docs/2.4/programs/ab.html
>
> Hardlockup with Patched Kernel:
> ------------------------------
>
> [ 3289.727912][ C123] rcu: INFO: rcu_sched detected stalls on CPUs/tasks:
> [ 3289.727943][ C123] rcu: 124-...0: (1 GPs behind) idle=f174/1/0x4000000000000000 softirq=12283/12289 fqs=732
> [ 3289.727976][ C123] rcu: (detected by 123, t=2103 jiffies, g=127061, q=5517 ncpus=128)
> [ 3289.728008][ C123] Sending NMI from CPU 123 to CPUs 124:
> [ 3295.182378][ C123] CPU 124 didn't respond to backtrace IPI, inspecting paca.
> [ 3295.182403][ C123] irq_soft_mask: 0x01 in_mce: 0 in_nmi: 0 current: 15 (ksoftirqd/124)
> [ 3295.182421][ C123] Back trace of paca->saved_r1 (0xc000000de13e79b0) (possibly stale):
> [ 3295.182437][ C123] Call Trace:
> [ 3295.182456][ C123] [c000000de13e79b0] [c000000de13e7a70] 0xc000000de13e7a70 (unreliable)
> [ 3295.182477][ C123] [c000000de13e7ac0] [0000000000000008] 0x8
> [ 3295.182500][ C123] [c000000de13e7b70] [c000000de13e7c98] 0xc000000de13e7c98
> [ 3295.182519][ C123] [c000000de13e7ba0] [c0000000001da8bc] move_queued_task+0x14c/0x280
> [ 3295.182557][ C123] [c000000de13e7c30] [c0000000001f22d8] newidle_balance+0x648/0x940
> [ 3295.182602][ C123] [c000000de13e7d30] [c0000000001f26ac] pick_next_task_fair+0x7c/0x680
> [ 3295.182647][ C123] [c000000de13e7dd0] [c0000000010f175c] __schedule+0x15c/0x1040
> [ 3295.182675][ C123] [c000000de13e7ec0] [c0000000010f26b4] schedule+0x74/0x140
> [ 3295.182694][ C123] [c000000de13e7f30] [c0000000001c4994] smpboot_thread_fn+0x244/0x250
> [ 3295.182731][ C123] [c000000de13e7f90] [c0000000001bc6e8] kthread+0x138/0x140
> [ 3295.182769][ C123] [c000000de13e7fe0] [c00000000000ded8] start_kernel_thread+0x14/0x18
> [ 3295.182806][ C123] rcu: rcu_sched kthread starved for 544 jiffies! g127061 f0x0 RCU_GP_DOING_FQS(6) ->state=0x0 ->cpu=66
> [ 3295.182845][ C123] rcu: Unless rcu_sched kthread gets sufficient CPU time, OOM is now expected behavior.
> [ 3295.182878][ C123] rcu: RCU grace-period kthread stack dump:
>
> -----------------------------------------
>
> [ 3943.438625][ C112] watchdog: CPU 112 self-detected hard LOCKUP @ _raw_spin_lock_irqsave+0x4c/0xc0
> [ 3943.438631][ C112] watchdog: CPU 112 TB:115060212303626, last heartbeat TB:115054309631589 (11528ms ago)
> [ 3943.438673][ C112] CPU: 112 PID: 2090 Comm: kworker/112:2 Tainted: G W L 6.5.0-rc2-00028-g7475adccd76b #51
> [ 3943.438676][ C112] Hardware name: 8335-GTW POWER9 (raw) 0x4e1203 opal:skiboot-v6.5.3-35-g1851b2a06 PowerNV
> [ 3943.438678][ C112] Workqueue: 0x0 (events)
> [ 3943.438682][ C112] NIP: c0000000010ff01c LR: c0000000001d1064 CTR: c0000000001e8580
> [ 3943.438684][ C112] REGS: c000007fffb6bd60 TRAP: 0900 Tainted: G W L (6.5.0-rc2-00028-g7475adccd76b)
> [ 3943.438686][ C112] MSR: 9000000000009033 <SF,HV,EE,ME,IR,DR,RI,LE> CR: 24082222 XER: 00000000
> [ 3943.438693][ C112] CFAR: 0000000000000000 IRQMASK: 1
> [ 3943.438693][ C112] GPR00: c0000000001d1064 c000000e16d1fb20 c0000000014e8200 c000000e092fed3c
> [ 3943.438693][ C112] GPR04: c000000e16d1fc58 c000000e092fe3c8 00000000000000e1 fffffffffffe0000
> [ 3943.438693][ C112] GPR08: 0000000000000000 00000000000000e1 0000000000000000 c00000000299ccd8
> [ 3943.438693][ C112] GPR12: 0000000024088222 c000007ffffb8300 c0000000001bc5b8 c000000deb46f740
> [ 3943.438693][ C112] GPR16: 0000000000000008 c000000e092fe280 0000000000000001 c000007ffedd7b00
> [ 3943.438693][ C112] GPR20: 0000000000000001 c0000000029a1280 0000000000000000 0000000000000001
> [ 3943.438693][ C112] GPR24: 0000000000000000 c000000e092fed3c c000000e16d1fdf0 c00000000299ccd8
> [ 3943.438693][ C112] GPR28: c000000e16d1fc58 c0000000021fbf00 c000007ffee6bf00 0000000000000001
> [ 3943.438722][ C112] NIP [c0000000010ff01c] _raw_spin_lock_irqsave+0x4c/0xc0
> [ 3943.438725][ C112] LR [c0000000001d1064] task_rq_lock+0x64/0x1b0
> [ 3943.438727][ C112] Call Trace:
> [ 3943.438728][ C112] [c000000e16d1fb20] [c000000e16d1fb60] 0xc000000e16d1fb60 (unreliable)
> [ 3943.438731][ C112] [c000000e16d1fb50] [c000000e16d1fbf0] 0xc000000e16d1fbf0
> [ 3943.438733][ C112] [c000000e16d1fbf0] [c0000000001f214c] newidle_balance+0x4bc/0x940
> [ 3943.438737][ C112] [c000000e16d1fcf0] [c0000000001f26ac] pick_next_task_fair+0x7c/0x680
> [ 3943.438739][ C112] [c000000e16d1fd90] [c0000000010f175c] __schedule+0x15c/0x1040
> [ 3943.438743][ C112] [c000000e16d1fe80] [c0000000010f26b4] schedule+0x74/0x140
> [ 3943.438747][ C112] [c000000e16d1fef0] [c0000000001afd44] worker_thread+0x134/0x580
> [ 3943.438749][ C112] [c000000e16d1ff90] [c0000000001bc6e8] kthread+0x138/0x140
> [ 3943.438753][ C112] [c000000e16d1ffe0] [c00000000000ded8] start_kernel_thread+0x14/0x18
> [ 3943.438756][ C112] Code: 63e90001 992d0932 a12d0008 3ce0fffe 5529083c 61290001 7d001
>
> -----------------------------------------
>
> System configuration:
> --------------------
>
> # lscpu
> Architecture: ppc64le
> Byte Order: Little Endian
> CPU(s): 128
> On-line CPU(s) list: 0-127
> Thread(s) per core: 4
> Core(s) per socket: 16
> Socket(s): 2
> NUMA node(s): 8
> Model: 2.3 (pvr 004e 1203)
> Model name: POWER9 (raw), altivec supported
> Frequency boost: enabled
> CPU max MHz: 3800.0000
> CPU min MHz: 2300.0000
> L1d cache: 1 MiB
> L1i cache: 1 MiB
> NUMA node0 CPU(s): 64-127
> NUMA node8 CPU(s): 0-63
> NUMA node250 CPU(s):
> NUMA node251 CPU(s):
> NUMA node252 CPU(s):
> NUMA node253 CPU(s):
> NUMA node254 CPU(s):
> NUMA node255 CPU(s):
>
> # uname -r
> 6.5.0-rc2-00028-g7475adccd76b
>
> # cat /sys/kernel/debug/sched/features
> GENTLE_FAIR_SLEEPERS START_DEBIT NO_NEXT_BUDDY LAST_BUDDY
> CACHE_HOT_BUDDY WAKEUP_PREEMPTION NO_HRTICK NO_HRTICK_DL NO_DOUBLE_TICK
> NONTASK_CAPACITY TTWU_QUEUE NO_SIS_PROP SIS_UTIL NO_WARN_DOUBLE_CLOCK
> RT_PUSH_IPI NO_RT_RUNTIME_SHARE NO_LB_MIN ATTACH_AGE_LOAD WA_IDLE
> WA_WEIGHT WA_BIAS UTIL_EST UTIL_EST_FASTUP NO_LATENCY_WARN ALT_PERIOD
> BASE_SLICE HZ_BW SHARED_RUNQ
>
> -----------------------------------------
>
> Please let me know if I've missed anything here. I'll continue
> investigating and share any additional information I find.
>
> Thanks and Regards,
> Aboorva
>
>
> > Changes
> > -------
> >
> > This is v3 of the shared runqueue patchset. This patch set is based
> > off
> > of commit 88c56cfeaec4 ("sched/fair: Block nohz tick_stop when cfs
> > bandwidth in use") on the sched/core branch of tip.git.
> >
> > v1 (RFC):
> > https://lore.kernel.org/lkml/[email protected]/
> > v2:
> > https://lore.kernel.org/lkml/[email protected]/
> >
> > v2 -> v3 changes:
> > - Don't leave stale tasks in the lists when the SHARED_RUNQ feature
> > is
> > disabled (Abel Wu)
> >
> > - Use raw spin lock instead of spinlock_t (Peter)
> >
> > - Fix return value from shared_runq_pick_next_task() to match the
> > semantics expected by newidle_balance() (Gautham, Abel)
> >
> > - Fold patch __enqueue_entity() / __dequeue_entity() into previous
> > patch
> > (Peter)
> >
> > - Skip <= LLC domains in newidle_balance() if SHARED_RUNQ is enabled
> > (Peter)
> >
> > - Properly support hotplug and recreating sched domains (Peter)
> >
> > - Avoid unnecessary task_rq_unlock() + raw_spin_rq_lock() when src_rq
> > ==
> > target_rq in shared_runq_pick_next_task() (Abel)
> >
> > - Only issue list_del_init() in shared_runq_dequeue_task() if the
> > task
> > is still in the list after acquiring the lock (Aaron Lu)
> >
> > - Slightly change shared_runq_shard_idx() to make it more likely to
> > keep
> > SMT siblings on the same bucket (Peter)
> >
> > v1 -> v2 changes:
> > - Change name from swqueue to shared_runq (Peter)
> >
> > - Shard per-LLC shared runqueues to avoid contention on scheduler-
> > heavy
> > workloads (Peter)
> >
> > - Pull tasks from the shared_runq in newidle_balance() rather than in
> > pick_next_task_fair() (Peter and Vincent)
> >
> > - Rename a few functions to reflect their actual purpose. For
> > example,
> > shared_runq_dequeue_task() instead of swqueue_remove_task() (Peter)
> >
> > - Expose move_queued_task() from core.c rather than migrate_task_to()
> > (Peter)
> >
> > - Properly check is_cpu_allowed() when pulling a task from a
> > shared_runq
> > to ensure it can actually be migrated (Peter and Gautham)
> >
> > - Dropped RFC tag
> >
> > Overview
> > ========
> >
> > The scheduler must constantly strike a balance between work
> > conservation, and avoiding costly migrations which harm performance
> > due
> > to e.g. decreased cache locality. The matter is further complicated
> > by
> > the topology of the system. Migrating a task between cores on the
> > same
> > LLC may be more optimal than keeping a task local to the CPU, whereas
> > migrating a task between LLCs or NUMA nodes may tip the balance in
> > the
> > other direction.
> >
> > With that in mind, while CFS is by and large mostly a work conserving
> > scheduler, there are certain instances where the scheduler will
> > choose
> > to keep a task local to a CPU, when it would have been more optimal
> > to
> > migrate it to an idle core.
> >
> > An example of such a workload is the HHVM / web workload at Meta.
> > HHVM
> > is a VM that JITs Hack and PHP code in service of web requests. Like
> > other JIT / compilation workloads, it tends to be heavily CPU bound,
> > and
> > exhibit generally poor cache locality. To try and address this, we
> > set
> > several debugfs (/sys/kernel/debug/sched) knobs on our HHVM
> > workloads:
> >
> > - migration_cost_ns -> 0
> > - latency_ns -> 20000000
> > - min_granularity_ns -> 10000000
> > - wakeup_granularity_ns -> 12000000
> >
> > These knobs are intended both to encourage the scheduler to be as
> > work
> > conserving as possible (migration_cost_ns -> 0), and also to keep
> > tasks
> > running for relatively long time slices so as to avoid the overhead
> > of
> > context switching (the other knobs). Collectively, these knobs
> > provide a
> > substantial performance win; resulting in roughly a 20% improvement
> > in
> > throughput. Worth noting, however, is that this improvement is _not_
> > at
> > full machine saturation.
> >
> > That said, even with these knobs, we noticed that CPUs were still
> > going
> > idle even when the host was overcommitted. In response, we wrote the
> > "shared runqueue" (SHARED_RUNQ) feature proposed in this patch set.
> > The
> > idea behind SHARED_RUNQ is simple: it enables the scheduler to be
> > more
> > aggressively work conserving by placing a waking task into a sharded
> > per-LLC FIFO queue that can be pulled from by another core in the LLC
> > FIFO queue which can then be pulled from before it goes idle.
> >
> > With this simple change, we were able to achieve a 1 - 1.6%
> > improvement
> > in throughput, as well as a small, consistent improvement in p95 and
> > p99
> > latencies, in HHVM. These performance improvements were in addition
> > to
> > the wins from the debugfs knobs mentioned above, and to other
> > benchmarks
> > outlined below in the Results section.
> >
> > Design
> > ======
> >
> > Note that the design described here reflects sharding, which is the
> > implementation added in the final patch of the series (following the
> > initial unsharded implementation added in patch 6/7). The design is
> > described that way in this commit summary as the benchmarks described
> > in
> > the results section below all reflect a sharded SHARED_RUNQ.
> >
> > The design of SHARED_RUNQ is quite simple. A shared_runq is simply a
> > list of struct shared_runq_shard objects, which itself is simply a
> > struct list_head of tasks, and a spinlock:
> >
> > struct shared_runq_shard {
> > struct list_head list;
> > raw_spinlock_t lock;
> > } ____cacheline_aligned;
> >
> > struct shared_runq {
> > u32 num_shards;
> > struct shared_runq_shard shards[];
> > } ____cacheline_aligned;
> >
> > We create a struct shared_runq per LLC, ensuring they're in their own
> > cachelines to avoid false sharing between CPUs on different LLCs, and
> > we
> > create a number of struct shared_runq_shard objects that are housed
> > there.
> >
> > When a task first wakes up, it enqueues itself in the
> > shared_runq_shard
> > of its current LLC at the end of enqueue_task_fair(). Enqueues only
> > happen if the task was not manually migrated to the current core by
> > select_task_rq(), and is not pinned to a specific CPU.
> >
> > A core will pull a task from the shards in its LLC's shared_runq at
> > the
> > beginning of newidle_balance().
> >
> > Difference between SHARED_RUNQ and SIS_NODE
> > ===========================================
> >
> > In [0] Peter proposed a patch that addresses Tejun's observations
> > that
> > when workqueues are targeted towards a specific LLC on his Zen2
> > machine
> > with small CCXs, that there would be significant idle time due to
> > select_idle_sibling() not considering anything outside of the current
> > LLC.
> >
> > This patch (SIS_NODE) is essentially the complement to the proposal
> > here. SID_NODE causes waking tasks to look for idle cores in
> > neighboring
> > LLCs on the same die, whereas SHARED_RUNQ causes cores about to go
> > idle
> > to look for enqueued tasks. That said, in its current form, the two
> > features at are a different scope as SIS_NODE searches for idle cores
> > between LLCs, while SHARED_RUNQ enqueues tasks within a single LLC.
> >
> > The patch was since removed in [1], and we compared the results to
> > SHARED_RUNQ (previously called "swqueue") in [2]. SIS_NODE did not
> > outperform SHARED_RUNQ on any of the benchmarks, so we elect to not
> > compare against it again for this v2 patch set.
> >
> > [0]:
> > https://lore.kernel.org/all/[email protected]/
> > [1]:
> > https://lore.kernel.org/all/[email protected]/
> > [2]:
> > https://lore.kernel.org/lkml/[email protected]/
> >
> > Worth noting as well is that pointed out in [3] that the logic behind
> > including SIS_NODE in the first place should apply to SHARED_RUNQ
> > (meaning that e.g. very small Zen2 CPUs with only 3/4 cores per LLC
> > should benefit from having a single shared_runq stretch across
> > multiple
> > LLCs). I drafted a patch that implements this by having a minimum LLC
> > size for creating a shard, and stretches a shared_runq across
> > multiple
> > LLCs if they're smaller than that size, and sent it to Tejun to test
> > on
> > his Zen2. Tejun reported back that SIS_NODE did not seem to make a
> > difference:
> >
> > [3]:
> > https://lore.kernel.org/lkml/[email protected]/
> >
> > o____________o__________o
> > | mean | Variance |
> > o------------o----------o
> > Vanilla: | 108.84s | 0.0057 |
> > NO_SHARED_RUNQ: | 108.82s | 0.119s |
> > SHARED_RUNQ: | 108.17s | 0.038s |
> > SHARED_RUNQ w/ SIS_NODE: | 108.87s | 0.111s |
> > o------------o----------o
> >
> > I similarly tried running kcompile on SHARED_RUNQ with SIS_NODE on my
> > 7950X Zen3, but didn't see any gain relative to plain SHARED_RUNQ
> > (though
> > a gain was observed relative to NO_SHARED_RUNQ, as described below).
> >
> > Results
> > =======
> >
> > Note that the motivation for the shared runqueue feature was
> > originally
> > arrived at using experiments in the sched_ext framework that's
> > currently
> > being proposed upstream. The ~1 - 1.6% improvement in HHVM throughput
> > is similarly visible using work-conserving sched_ext schedulers (even
> > very simple ones like global FIFO).
> >
> > In both single and multi socket / CCX hosts, this can measurably
> > improve
> > performance. In addition to the performance gains observed on our
> > internal web workloads, we also observed an improvement in common
> > workloads such as kernel compile and hackbench, when running shared
> > runqueue.
> >
> > On the other hand, some workloads suffer from SHARED_RUNQ. Workloads
> > that hammer the runqueue hard, such as netperf UDP_RR, or schbench -L
> > -m 52 -p 512 -r 10 -t 1. This can be mitigated somewhat by sharding
> > the
> > shared datastructures within a CCX, but it doesn't seem to eliminate
> > all
> > contention in every scenario. On the positive side, it seems that
> > sharding does not materially harm the benchmarks run for this patch
> > series; and in fact seems to improve some workloads such as kernel
> > compile.
> >
> > Note that for the kernel compile workloads below, the compilation was
> > done by running make -j$(nproc) built-in.a on several different types
> > of
> > hosts configured with make allyesconfig on commit a27648c74210 ("afs:
> > Fix setting of mtime when creating a file/dir/symlink") on Linus'
> > tree
> > (boost and turbo were disabled on all of these hosts when the
> > experiments were performed).
> >
> > Finally, note that these results were from the patch set built off of
> > commit ebb83d84e49b ("sched/core: Avoid multiple calling
> > update_rq_clock() in __cfsb_csd_unthrottle()") on the sched/core
> > branch
> > of tip.git for easy comparison with the v2 patch set results. The
> > patches in their final form from this set were rebased onto commit
> > 88c56cfeaec4 ("sched/fair: Block nohz tick_stop when cfs bandwidth in
> > use") on the sched/core branch of tip.git.
> >
> > === Single-socket | 16 core / 32 thread | 2-CCX | AMD 7950X Zen4 ===
> >
> > CPU max MHz: 5879.8818
> > CPU min MHz: 3000.0000
> >
> > Command: make -j$(nproc) built-in.a
> > o____________o__________o
> > | mean | Variance |
> > o------------o----------o
> > NO_SHARED_RUNQ: | 581.95s | 2.639s |
> > SHARED_RUNQ: | 577.02s | 0.084s |
> > o------------o----------o
> >
> > Takeaway: SHARED_RUNQ results in a statistically significant ~.85%
> > improvement over NO_SHARED_RUNQ. This suggests that enqueuing tasks
> > in
> > the shared runqueue on every enqueue improves work conservation, and
> > thanks to sharding, does not result in contention.
> >
> > Command: hackbench --loops 10000
> > o____________o__________o
> > | mean | Variance |
> > o------------o----------o
> > NO_SHARED_RUNQ: | 2.2492s | .00001s |
> > SHARED_RUNQ: | 2.0217s | .00065s |
> > o------------o----------o
> >
> > Takeaway: SHARED_RUNQ in both forms performs exceptionally well
> > compared
> > to NO_SHARED_RUNQ here, beating it by over 10%. This was a surprising
> > result given that it seems advantageous to err on the side of
> > avoiding
> > migration in hackbench given that tasks are short lived in sending
> > only
> > 10k bytes worth of messages, but the results of the benchmark would
> > seem
> > to suggest that minimizing runqueue delays is preferable.
> >
> > Command:
> > for i in `seq 128`; do
> > netperf -6 -t UDP_RR -c -C -l $runtime &
> > done
> > o_______________________o
> > | Throughput | Variance |
> > o-----------------------o
> > NO_SHARED_RUNQ: | 25037.45 | 2243.44 |
> > SHARED_RUNQ: | 24952.50 | 1268.06 |
> > o-----------------------o
> >
> > Takeaway: No statistical significance, though it is worth noting that
> > there is no regression for shared runqueue on the 7950X, while there
> > is
> > a small regression on the Skylake and Milan hosts for SHARED_RUNQ as
> > described below.
> >
> > === Single-socket | 18 core / 36 thread | 1-CCX | Intel Skylake ===
> >
> > CPU max MHz: 1601.0000
> > CPU min MHz: 800.0000
> >
> > Command: make -j$(nproc) built-in.a
> > o____________o__________o
> > | mean | Variance |
> > o------------o----------o
> > NO_SHARED_RUNQ: | 1517.44s | 2.8322s |
> > SHARED_RUNQ: | 1516.51s | 2.9450s |
> > o------------o----------o
> >
> > Takeaway: There's on statistically significant gain here. I observed
> > what I claimed was a .23% win in v2, but it appears that this is not
> > actually statistically significant.
> >
> > Command: hackbench --loops 10000
> > o____________o__________o
> > | mean | Variance |
> > o------------o----------o
> > NO_SHARED_RUNQ: | 5.3370s | .0012s |
> > SHARED_RUNQ: | 5.2668s | .0033s |
> > o------------o----------o
> >
> > Takeaway: SHARED_RUNQ results in a ~1.3% improvement over
> > NO_SHARED_RUNQ. Also statistically significant, but smaller than the
> > 10+% improvement observed on the 7950X.
> >
> > Command: netperf -n $(nproc) -l 60 -t TCP_RR
> > for i in `seq 128`; do
> > netperf -6 -t UDP_RR -c -C -l $runtime &
> > done
> > o_______________________o
> > | Throughput | Variance |
> > o-----------------------o
> > NO_SHARED_RUNQ: | 15699.32 | 377.01 |
> > SHARED_RUNQ: | 14966.42 | 714.13 |
> > o-----------------------o
> >
> > Takeaway: NO_SHARED_RUNQ beats SHARED_RUNQ by ~4.6%. This result
> > makes
> > sense -- the workload is very heavy on the runqueue, so enqueuing
> > tasks
> > in the shared runqueue in __enqueue_entity() would intuitively result
> > in
> > increased contention on the shard lock.
> >
> > === Single-socket | 72-core | 6-CCX | AMD Milan Zen3 ===
> >
> > CPU max MHz: 700.0000
> > CPU min MHz: 700.0000
> >
> > Command: make -j$(nproc) built-in.a
> > o____________o__________o
> > | mean | Variance |
> > o------------o----------o
> > NO_SHARED_RUNQ: | 1568.55s | 0.1568s |
> > SHARED_RUNQ: | 1568.26s | 1.2168s |
> > o------------o----------o
> >
> > Takeaway: No statistically significant difference here. It might be
> > worth experimenting with work stealing in a follow-on patch set.
> >
> > Command: hackbench --loops 10000
> > o____________o__________o
> > | mean | Variance |
> > o------------o----------o
> > NO_SHARED_RUNQ: | 5.2716s | .00143s |
> > SHARED_RUNQ: | 5.1716s | .00289s |
> > o------------o----------o
> >
> > Takeaway: SHARED_RUNQ again wins, by about 2%.
> >
> > Command: netperf -n $(nproc) -l 60 -t TCP_RR
> > for i in `seq 128`; do
> > netperf -6 -t UDP_RR -c -C -l $runtime &
> > done
> > o_______________________o
> > | Throughput | Variance |
> > o-----------------------o
> > NO_SHARED_RUNQ: | 17482.03 | 4675.99 |
> > SHARED_RUNQ: | 16697.25 | 9812.23 |
> > o-----------------------o
> >
> > Takeaway: Similar to the Skylake runs, NO_SHARED_RUNQ still beats
> > SHARED_RUNQ, this time by ~4.5%. It's worth noting that in v2, the
> > NO_SHARED_RUNQ was only ~1.8% faster. The variance is very high here,
> > so
> > the results of this benchmark should be taken with a large grain of
> > salt (noting that we do consistently see NO_SHARED_RUNQ on top due to
> > not contending on the shard lock).
> >
> > Finally, let's look at how sharding affects the following schbench
> > incantation suggested by Chris in [4]:
> >
> > schbench -L -m 52 -p 512 -r 10 -t 1
> >
> > [4]:
> > https://lore.kernel.org/lkml/[email protected]/
> >
> > The TL;DR is that sharding improves things a lot, but doesn't
> > completely
> > fix the problem. Here are the results from running the schbench
> > command
> > on the 18 core / 36 thread single CCX, single-socket Skylake:
> >
> > -------------------------------------------------------------------
> > -------------------------------------------------------------------
> > -----------------------------------------------------------------
> > class name con-bounces contentions waittime-
> > min waittime-max waittime-total waittime-avg acq-
> > bounces acquisitions holdtime-min holdtime-max holdtime-
> > total holdtime-avg
> > -------------------------------------------------------------------
> > -------------------------------------------------------------------
> > -----------------------------------------------------------------
> >
> > &shard-
> > >lock: 31510503 31510711 0.08 19.98
> > 168932319.64 5.36 31700383 31843851 0.0
> > 3 17.50 10273968.33 0.32
> > ------------
> > &shard->lock 15731657 [<0000000068c0fd75>]
> > pick_next_task_fair+0x4dd/0x510
> > &shard->lock 15756516 [<000000001faf84f9>]
> > enqueue_task_fair+0x459/0x530
> > &shard->lock 21766 [<00000000126ec6ab>]
> > newidle_balance+0x45a/0x650
> > &shard->lock 772 [<000000002886c365>]
> > dequeue_task_fair+0x4c9/0x540
> > ------------
> > &shard->lock 23458 [<00000000126ec6ab>]
> > newidle_balance+0x45a/0x650
> > &shard->lock 16505108 [<000000001faf84f9>]
> > enqueue_task_fair+0x459/0x530
> > &shard->lock 14981310 [<0000000068c0fd75>]
> > pick_next_task_fair+0x4dd/0x510
> > &shard->lock 835 [<000000002886c365>]
> > dequeue_task_fair+0x4c9/0x540
> >
> > These results are when we create only 3 shards (16 logical cores per
> > shard), so the contention may be a result of overly-coarse sharding.
> > If
> > we run the schbench incantation with no sharding whatsoever, we see
> > the
> > following significantly worse lock stats contention:
> >
> > -------------------------------------------------------------------
> > -------------------------------------------------------------------
> > -------------------------------------------------------------------
> > ----
> > class name con-bounces contentions waittime-
> > min waittime-max waittime-total waittime-avg acq-
> > bounces acquisitions holdtime-min holdtime-max holdtime-
> > total holdtime-avg
> > -------------------------------------------------------------------
> > -------------------------------------------------------------------
> > -------------------------------------------------------------------
> > ----
> >
> > &shard-
> > >lock: 117868635 118361486 0.09 393.01
> > 1250954097.25 10.57 119345882 119780601
> > 0.05 343.35 38313419.51 0.32
> > ------------
> > &shard->lock 59169196 [<0000000060507011>]
> > __enqueue_entity+0xdc/0x110
> > &shard->lock 59084239 [<00000000f1c67316>]
> > __dequeue_entity+0x78/0xa0
> > &shard->lock 108051 [<00000000084a6193>]
> > newidle_balance+0x45a/0x650
> > ------------
> > &shard->lock 60028355 [<0000000060507011>]
> > __enqueue_entity+0xdc/0x110
> > &shard->lock 119882 [<00000000084a6193>]
> > newidle_balance+0x45a/0x650
> > &shard->lock 58213249 [<00000000f1c67316>]
> > __dequeue_entity+0x78/0xa0
> >
> > The contention is ~3-4x worse if we don't shard at all. This roughly
> > matches the fact that we had 3 shards on the first workload run
> > above.
> > If we make the shards even smaller, the contention is comparably much
> > lower:
> >
> > -------------------------------------------------------------------
> > -------------------------------------------------------------------
> > ----------------------------------------------------------
> > class name con-bounces contentions waittime-
> > min waittime-max waittime-total waittime-avg acq-
> > bounces acquisitions holdtime-min holdtime-max holdtime-
> > total holdtime-avg
> > -------------------------------------------------------------------
> > -------------------------------------------------------------------
> > ----------------------------------------------------------
> >
> > &shard-
> > >lock: 13839849 13877596 0.08 13.23 5
> > 389564.95 0.39 46910241 48069307 0.06
> > 16.40 16534469.35 0.34
> > ------------
> > &shard->lock 3559 [<00000000ea455dcc>]
> > newidle_balance+0x45a/0x650
> > &shard->lock 6992418 [<000000002266f400>]
> > __dequeue_entity+0x78/0xa0
> > &shard->lock 6881619 [<000000002a62f2e0>]
> > __enqueue_entity+0xdc/0x110
> > ------------
> > &shard->lock 6640140 [<000000002266f400>]
> > __dequeue_entity+0x78/0xa0
> > &shard->lock 3523 [<00000000ea455dcc>]
> > newidle_balance+0x45a/0x650
> > &shard->lock 7233933 [<000000002a62f2e0>]
> > __enqueue_entity+0xdc/0x110
> >
> > Interestingly, SHARED_RUNQ performs worse than NO_SHARED_RUNQ on the
> > schbench
> > benchmark on Milan as well, but we contend more on the rq lock than
> > the
> > shard lock:
> >
> > -------------------------------------------------------------------
> > -------------------------------------------------------------------
> > -----------------------------------------------------------
> > class name con-bounces contentions waittime-
> > min waittime-max waittime-total waittime-avg acq-
> > bounces acquisitions holdtime-min holdtime-max holdtime-
> > total holdtime-avg
> > -------------------------------------------------------------------
> > -------------------------------------------------------------------
> > -----------------------------------------------------------
> >
> > &rq-
> > >__lock: 9617614 9656091 0.10 79.64
> > 69665812.00 7.21 18092700 67652829 0.11
> > 82.38 344524858.87 5.09
> > -----------
> > &rq->__lock 6301611 [<000000003e63bf26>]
> > task_rq_lock+0x43/0xe0
> > &rq->__lock 2530807 [<00000000516703f0>]
> > __schedule+0x72/0xaa0
> > &rq->__lock 109360 [<0000000011be1562>]
> > raw_spin_rq_lock_nested+0xa/0x10
> > &rq->__lock 178218 [<00000000c38a30f9>]
> > sched_ttwu_pending+0x3d/0x170
> > -----------
> > &rq->__lock 3245506 [<00000000516703f0>]
> > __schedule+0x72/0xaa0
> > &rq->__lock 1294355 [<00000000c38a30f9>]
> > sched_ttwu_pending+0x3d/0x170
> > &rq->__lock 2837804 [<000000003e63bf26>]
> > task_rq_lock+0x43/0xe0
> > &rq->__lock 1627866 [<0000000011be1562>]
> > raw_spin_rq_lock_nested+0xa/0x10
> >
> > .....................................................................
> > .....................................................................
> > ........................................................
> >
> > &shard-
> > >lock: 7338558 7343244 0.10 35.97 7
> > 173949.14 0.98 30200858 32679623 0.08
> > 35.59 16270584.52 0.50
> > ------------
> > &shard->lock 2004142 [<00000000f8aa2c91>]
> > __dequeue_entity+0x78/0xa0
> > &shard->lock 2611264 [<00000000473978cc>]
> > newidle_balance+0x45a/0x650
> > &shard->lock 2727838 [<0000000028f55bb5>]
> > __enqueue_entity+0xdc/0x110
> > ------------
> > &shard->lock 2737232 [<00000000473978cc>]
> > newidle_balance+0x45a/0x650
> > &shard->lock 1693341 [<00000000f8aa2c91>]
> > __dequeue_entity+0x78/0xa0
> > &shard->lock 2912671 [<0000000028f55bb5>]
> > __enqueue_entity+0xdc/0x110
> >
> > .....................................................................
> > .....................................................................
> > .........................................................
> >
> > If we look at the lock stats with SHARED_RUNQ disabled, the rq lock
> > still
> > contends the most, but it's significantly less than with it enabled:
> >
> > -------------------------------------------------------------------
> > -------------------------------------------------------------------
> > --------------------------------------------------------------
> > class name con-bounces contentions waittime-
> > min waittime-max waittime-total waittime-avg acq-
> > bounces acquisitions holdtime-min holdtime-max holdtime-
> > total holdtime-avg
> > -------------------------------------------------------------------
> > -------------------------------------------------------------------
> > --------------------------------------------------------------
> >
> > &rq-
> > >__lock: 791277 791690 0.12 110.54
> > 4889787.63 6.18 1575996 62390275 0.1
> > 3 112.66 316262440.56 5.07
> > -----------
> > &rq->__lock 263343 [<00000000516703f0>]
> > __schedule+0x72/0xaa0
> > &rq->__lock 19394 [<0000000011be1562>]
> > raw_spin_rq_lock_nested+0xa/0x10
> > &rq->__lock 4143 [<000000003b542e83>]
> > __task_rq_lock+0x51/0xf0
> > &rq->__lock 51094 [<00000000c38a30f9>]
> > sched_ttwu_pending+0x3d/0x170
> > -----------
> > &rq->__lock 23756 [<0000000011be1562>]
> > raw_spin_rq_lock_nested+0xa/0x10
> > &rq->__lock 379048 [<00000000516703f0>]
> > __schedule+0x72/0xaa0
> > &rq->__lock 677 [<000000003b542e83>]
> > __task_rq_lock+0x51/0xf0
> >
> > Worth noting is that increasing the granularity of the shards in
> > general
> > improves very runqueue-heavy workloads such as netperf UDP_RR and
> > this
> > schbench command, but it doesn't necessarily make a big difference
> > for
> > every workload, or for sufficiently small CCXs such as the 7950X. It
> > may
> > make sense to eventually allow users to control this with a debugfs
> > knob, but for now we'll elect to choose a default that resulted in
> > good
> > performance for the benchmarks run for this patch series.
> >
> > Conclusion
> > ==========
> >
> > SHARED_RUNQ in this form provides statistically significant wins for
> > several types of workloads, and various CPU topologies. The reason
> > for
> > this is roughly the same for all workloads: SHARED_RUNQ encourages
> > work
> > conservation inside of a CCX by having a CPU do an O(# per-LLC
> > shards)
> > iteration over the shared_runq shards in an LLC. We could similarly
> > do
> > an O(n) iteration over all of the runqueues in the current LLC when a
> > core is going idle, but that's quite costly (especially for larger
> > LLCs), and sharded SHARED_RUNQ seems to provide a performant middle
> > ground between doing an O(n) walk, and doing an O(1) pull from a
> > single
> > per-LLC shared runq.
> >
> > For the workloads above, kernel compile and hackbench were clear
> > winners
> > for SHARED_RUNQ (especially in __enqueue_entity()). The reason for
> > the
> > improvement in kernel compile is of course that we have a heavily
> > CPU-bound workload where cache locality doesn't mean much; getting a
> > CPU
> > is the #1 goal. As mentioned above, while I didn't expect to see an
> > improvement in hackbench, the results of the benchmark suggest that
> > minimizing runqueue delays is preferable to optimizing for L1/L2
> > locality.
> >
> > Not all workloads benefit from SHARED_RUNQ, however. Workloads that
> > hammer the runqueue hard, such as netperf UDP_RR, or schbench -L -m
> > 52
> > -p 512 -r 10 -t 1, tend to run into contention on the shard locks;
> > especially when enqueuing tasks in __enqueue_entity(). This can be
> > mitigated significantly by sharding the shared datastructures within
> > a
> > CCX, but it doesn't eliminate all contention, as described above.
> >
> > Worth noting as well is that Gautham Shenoy ran some interesting
> > experiments on a few more ideas in [5], such as walking the
> > shared_runq
> > on the pop path until a task is found that can be migrated to the
> > calling CPU. I didn't run those experiments in this patch set, but it
> > might be worth doing so.
> >
> > [5]:
> > https://lore.kernel.org/lkml/[email protected]/
> >
> > Gautham also ran some other benchmarks in [6], which we may want to
> > again try on this v3, but with boost disabled.
> >
> > [6]:
> > https://lore.kernel.org/lkml/[email protected]/
> >
> > Finally, while SHARED_RUNQ in this form encourages work conservation,
> > it
> > of course does not guarantee it given that we don't implement any
> > kind
> > of work stealing between shared_runq's. In the future, we could
> > potentially push CPU utilization even higher by enabling work
> > stealing
> > between shared_runq's, likely between CCXs on the same NUMA node.
> >
> > Originally-by: Roman Gushchin <[email protected]>
> > Signed-off-by: David Vernet <[email protected]>
> >
> > David Vernet (7):
> > sched: Expose move_queued_task() from core.c
> > sched: Move is_cpu_allowed() into sched.h
> > sched: Check cpu_active() earlier in newidle_balance()
> > sched: Enable sched_feat callbacks on enable/disable
> > sched/fair: Add SHARED_RUNQ sched feature and skeleton calls
> > sched: Implement shared runqueue in CFS
> > sched: Shard per-LLC shared runqueues
> >
> > include/linux/sched.h | 2 +
> > kernel/sched/core.c | 52 ++----
> > kernel/sched/debug.c | 18 ++-
> > kernel/sched/fair.c | 340
> > +++++++++++++++++++++++++++++++++++++++-
> > kernel/sched/features.h | 1 +
> > kernel/sched/sched.h | 56 ++++++-
> > kernel/sched/topology.c | 4 +-
> > 7 files changed, 420 insertions(+), 53 deletions(-)
> >
>
On Wed, Aug 09, 2023 at 05:12:11PM -0500, David Vernet wrote:
> Changes
> -------
>
> This is v3 of the shared runqueue patchset. This patch set is based off
> of commit 88c56cfeaec4 ("sched/fair: Block nohz tick_stop when cfs
> bandwidth in use") on the sched/core branch of tip.git.
>
> v1 (RFC): https://lore.kernel.org/lkml/[email protected]/
> v2: https://lore.kernel.org/lkml/[email protected]/
Hello everyone,
I wanted to give an update on this, as I've been promising a v4 of the
patch set for quite some time. I ran more experiments over the last few
weeks, and EEVDF has changed the performance profile of the SHARED_RUNQ
feature quite a bit compared to what we were observing with CFS. We may
pick this back up again at a later point, but for now we're going to
take a step back and re-evaluate.
Thanks,
David
On Mon, 2023-11-27 at 13:49 -0600, David Vernet wrote:
> On Mon, Nov 27, 2023 at 01:58:34PM +0530, Aboorva Devarajan wrote:
> > On Wed, 2023-08-09 at 17:12 -0500, David Vernet wrote:
> >
> > Hi David,
> >
> > I have been benchmarking the patch-set on POWER9 machine to understand
> > its impact. However, I've run into a recurring hard-lockups in
> > newidle_balance, specifically when SHARED_RUNQ feature is enabled. It
> > doesn't happen all the time, but it's something worth noting. I wanted
> > to inform you about this, and I can provide more details if needed.
>
> Hello Aboorva,
>
> Thank you for testing out this patch set and for the report. One issue
> that v4 will correct is that the shared_runq list could become corrupted
> if you enable and disable the feature, as a stale task could remain in
> the list after the feature has been disabled. I'll be including a fix
> for that in v4, which I'm currently benchmarking, but other stuff keeps
> seeming to preempt it.
Hi David,
Thank you for your response. While testing, I did observe the
shared_runq list becoming corrupted when enabling and disabling the
feature.
Please find the logs below with CONFIG_DEBUG_LIST enabled:
------------------------------------------
[ 4952.270819] list_add corruption. prev->next should be next (c0000003fae87a80), but was c0000000ba027ec8. (prev=c0000000ba027ec8).
[ 4952.270926] ------------[ cut here ]------------
[ 4952.270935] kernel BUG at lib/list_debug.c:30!
[ 4952.270947] Oops: Exception in kernel mode, sig: 5 [#1]
[ 4952.270956] LE PAGE_SIZE=64K MMU=Radix SMP NR_CPUS=2048 NUMA pSeries
[ 4952.271029] CPU: 10 PID: 31426 Comm: cc1 Kdump: loaded Not tainted 6.5.0-rc2+ #1
[ 4952.271042] Hardware name: IBM,9080-HEX POWER10 (raw) 0x800200 0xf000006 of:IBM,FW1060.00 (NH1060_012) hv:phyp pSeries
[ 4952.271054] NIP: c000000000872f88 LR: c000000000872f84 CTR: 00000000006d1a1c
[ 4952.271070] REGS: c00000006e1b34e0 TRAP: 0700 Not tainted (6.5.0-rc2+)
[ 4952.271079] MSR: 8000000002029033 <SF,VEC,EE,ME,IR,DR,RI,LE> CR: 28048222 XER: 00000006
[ 4952.271102] CFAR: c0000000001ffa24 IRQMASK: 1
[ 4952.271102] GPR00: c000000000872f84 c00000006e1b3780 c0000000019a3b00 0000000000000075
[ 4952.271102] GPR04: c0000003faff2c08 c0000003fb077e80 c00000006e1b35c8 00000003f8e70000
[ 4952.271102] GPR08: 0000000000000027 c000000002185f30 00000003f8e70000 0000000000000001
[ 4952.271102] GPR12: 0000000000000000 c0000003fffe2c80 c000000068ecb100 0000000000000000
[ 4952.271102] GPR16: 0000000000000000 0000000000000000 0000000000000000 0000000000000000
[ 4952.271102] GPR20: 0000000000000000 0000000000000000 0000000000000041 c00000006e1b3bb0
[ 4952.271102] GPR24: c000000002c72058 00000003f8e70000 0000000000000001 c00000000e919948
[ 4952.271102] GPR28: c0000000ba027ec8 c0000003fae87a80 c000000080ce6c00 c00000000e919980
[ 4952.271212] NIP [c000000000872f88] __list_add_valid+0xb8/0x100
[ 4952.271236] LR [c000000000872f84] __list_add_valid+0xb4/0x100
[ 4952.271248] Call Trace:
[ 4952.271254] [c00000006e1b3780] [c000000000872f84] __list_add_valid+0xb4/0x100 (unreliable)
[ 4952.271270] [c00000006e1b37e0] [c0000000001b8f50] __enqueue_entity+0x110/0x1c0
[ 4952.271288] [c00000006e1b3830] [c0000000001bec9c] enqueue_entity+0x16c/0x690
[ 4952.271301] [c00000006e1b38e0] [c0000000001bf280] enqueue_task_fair+0xc0/0x490
[ 4952.271315] [c00000006e1b3980] [c0000000001ada0c] ttwu_do_activate+0xac/0x410
[ 4952.271328] [c00000006e1b3a10] [c0000000001ae59c] try_to_wake_up+0x5fc/0x8b0
[ 4952.271341] [c00000006e1b3ae0] [c0000000001df6dc] autoremove_wake_function+0x2c/0xc0
[ 4952.271359] [c00000006e1b3b20] [c0000000001e1018] __wake_up_common+0xc8/0x240
[ 4952.271372] [c00000006e1b3b90] [c0000000001e123c] __wake_up_common_lock+0xac/0x120
[ 4952.271385] [c00000006e1b3c20] [c0000000005bd4a4] pipe_write+0xd4/0x980
[ 4952.271401] [c00000006e1b3d00] [c0000000005ad720] vfs_write+0x350/0x4b0
[ 4952.271420] [c00000006e1b3dc0] [c0000000005adc24] ksys_write+0xf4/0x140
[ 4952.271433] [c00000006e1b3e10] [c000000000031108] system_call_exception+0x128/0x340
[ 4952.271449] [c00000006e1b3e50] [c00000000000cedc] system_call_vectored_common+0x15c/0x2ec
[ 4952.271470] --- interrupt: 3000 at 0x7fff8df3aa34
[ 4952.271482] NIP: 00007fff8df3aa34 LR: 0000000000000000 CTR: 0000000000000000
[ 4952.271492] REGS: c00000006e1b3e80 TRAP: 3000 Not tainted (6.5.0-rc2+)
[ 4952.271502] MSR: 800000000000f033 <SF,EE,PR,FP,ME,IR,DR,RI,LE> CR: 44002822 XER: 00000000
[ 4952.271526] IRQMASK: 0
[ 4952.271526] GPR00: 0000000000000004 00007fffea094d00 0000000112467a00 0000000000000001
[ 4952.271526] GPR04: 0000000132c6a810 0000000000002000 00000000000004e4 0000000000000036
[ 4952.271526] GPR08: 0000000132c6c810 0000000000000000 0000000000000000 0000000000000000
[ 4952.271526] GPR12: 0000000000000000 00007fff8e71cac0 0000000000000000 0000000000000000
[ 4952.271526] GPR16: 0000000000000000 0000000000000000 0000000000000000 0000000000000000
[ 4952.271526] GPR20: 00007fffea09c76f 00000001123b6898 0000000000000003 0000000132c6c820
[ 4952.271526] GPR24: 0000000112469d88 00000001124686b8 0000000132c6a810 0000000000002000
[ 4952.271526] GPR28: 0000000000002000 00007fff8e0418e0 0000000132c6a810 0000000000002000
[ 4952.271627] NIP [00007fff8df3aa34] 0x7fff8df3aa34
[ 4952.271635] LR [0000000000000000] 0x0
[ 4952.271642] --- interrupt: 3000
[ 4952.271648] Code: f8010070 4b98ca81 60000000 0fe00000 7c0802a6 3c62ffa6 7d064378 7d244b78 38637f68 f8010070 4b98ca5d 60000000 <0fe00000> 7c0802a6 3c62ffa6 7ca62b78
[ 4952.271685] ---[ end trace 0000000000000000 ]---
[ 4952.282562] pstore: backend (nvram) writing error (-1)
------------------------------------------
>
> By any chance, did you run into this when you were enabling / disabling
> the feature? Or did you just enable it once and then hit this issue
> after some time, which would indicate a different issue? I'm trying to
> repro using ab, but haven't been successful thus far. If you're able to
> repro consistently, it might be useful to run with CONFIG_LIST_DEBUG=y.
>
Additionally, I noticed a sporadic issue persisting even after enabling
the feature once, and the issue surfaced over time. However, it
occurred specifically on a particular system, and my attempts to
recreate it were unsuccessful. I will provide more details if I can
successfully reproduce the issue with debug enabled. But looks like the
primary issue revolves around the shared_runq list getting corrupted
when toggling the feature on and off repeatedly as you pointed out.
I will keep an eye out for v4 and test if it's available later.
Thanks,
Aboorva
> Thanks,
> David
>
> > -----------------------------------------
> >
> > Some inital information regarding the hard-lockup:
> >
> > Base Kernel:
> > -----------
> >
> > Base kernel is upto commit 88c56cfeaec4 ("sched/fair: Block nohz
> > tick_stop when cfs bandwidth in use").
> >
> > Patched Kernel:
> > -------------
> >
> > Base Kernel + v3 (shared runqueue patch-set)(
> > https://lore.kernel.org/all/[email protected]/
> > )
> >
> > The hard-lockup moslty occurs when running the Apache2 benchmarks
> > with
> > ab (Apache HTTP benchmarking tool) on the patched kernel. However,
> > this
> > problem is not exclusive to the mentioned benchmark and only occurs
> > while the SHARED_RUNQ feature is enabled. Disabling SHARED_RUNQ
> > feature
> > prevents the occurrence of the lockup.
> >
> > ab (Apache HTTP benchmarking tool):
> > https://httpd.apache.org/docs/2.4/programs/ab.html
> >
> > Hardlockup with Patched Kernel:
> > ------------------------------
> >
> > [ 3289.727912][ C123] rcu: INFO: rcu_sched detected stalls on CPUs/tasks:
> > [ 3289.727943][ C123] rcu: 124-...0: (1 GPs behind) idle=f174/1/0x4000000000000000 softirq=12283/12289 fqs=732
> > [ 3289.727976][ C123] rcu: (detected by 123, t=2103 jiffies, g=127061, q=5517 ncpus=128)
> > [ 3289.728008][ C123] Sending NMI from CPU 123 to CPUs 124:
> > [ 3295.182378][ C123] CPU 124 didn't respond to backtrace IPI, inspecting paca.
> > [ 3295.182403][ C123] irq_soft_mask: 0x01 in_mce: 0 in_nmi: 0 current: 15 (ksoftirqd/124)
> > [ 3295.182421][ C123] Back trace of paca->saved_r1 (0xc000000de13e79b0) (possibly stale):
> > [ 3295.182437][ C123] Call Trace:
> > [ 3295.182456][ C123] [c000000de13e79b0] [c000000de13e7a70] 0xc000000de13e7a70 (unreliable)
> > [ 3295.182477][ C123] [c000000de13e7ac0] [0000000000000008] 0x8
> > [ 3295.182500][ C123] [c000000de13e7b70] [c000000de13e7c98] 0xc000000de13e7c98
> > [ 3295.182519][ C123] [c000000de13e7ba0] [c0000000001da8bc] move_queued_task+0x14c/0x280
> > [ 3295.182557][ C123] [c000000de13e7c30] [c0000000001f22d8] newidle_balance+0x648/0x940
> > [ 3295.182602][ C123] [c000000de13e7d30] [c0000000001f26ac] pick_next_task_fair+0x7c/0x680
> > [ 3295.182647][ C123] [c000000de13e7dd0] [c0000000010f175c] __schedule+0x15c/0x1040
> > [ 3295.182675][ C123] [c000000de13e7ec0] [c0000000010f26b4] schedule+0x74/0x140
> > [ 3295.182694][ C123] [c000000de13e7f30] [c0000000001c4994] smpboot_thread_fn+0x244/0x250
> > [ 3295.182731][ C123] [c000000de13e7f90] [c0000000001bc6e8] kthread+0x138/0x140
> > [ 3295.182769][ C123] [c000000de13e7fe0] [c00000000000ded8] start_kernel_thread+0x14/0x18
> > [ 3295.182806][ C123] rcu: rcu_sched kthread starved for 544 jiffies! g127061 f0x0 RCU_GP_DOING_FQS(6) ->state=0x0 ->cpu=66
> > [ 3295.182845][ C123] rcu: Unless rcu_sched kthread gets sufficient CPU time, OOM is now expected behavior.
> > [ 3295.182878][ C123] rcu: RCU grace-period kthread stack dump:
> >
> > -----------------------------------------
> >
> > [ 3943.438625][ C112] watchdog: CPU 112 self-detected hard LOCKUP @ _raw_spin_lock_irqsave+0x4c/0xc0
> > [ 3943.438631][ C112] watchdog: CPU 112 TB:115060212303626, last heartbeat TB:115054309631589 (11528ms ago)
> > [ 3943.438673][ C112] CPU: 112 PID: 2090 Comm: kworker/112:2 Tainted: G W L 6.5.0-rc2-00028-g7475adccd76b #51
> > [ 3943.438676][ C112] Hardware name: 8335-GTW POWER9 (raw) 0x4e1203 opal:skiboot-v6.5.3-35-g1851b2a06 PowerNV
> > [ 3943.438678][ C112] Workqueue: 0x0 (events)
> > [ 3943.438682][ C112] NIP: c0000000010ff01c LR: c0000000001d1064 CTR: c0000000001e8580
> > [ 3943.438684][ C112] REGS: c000007fffb6bd60 TRAP: 0900 Tainted: G W L (6.5.0-rc2-00028-g7475adccd76b)
> > [ 3943.438686][ C112] MSR: 9000000000009033 <SF,HV,EE,ME,IR,DR,RI,LE> CR: 24082222 XER: 00000000
> > [ 3943.438693][ C112] CFAR: 0000000000000000 IRQMASK: 1
> > [ 3943.438693][ C112] GPR00: c0000000001d1064 c000000e16d1fb20 c0000000014e8200 c000000e092fed3c
> > [ 3943.438693][ C112] GPR04: c000000e16d1fc58 c000000e092fe3c8 00000000000000e1 fffffffffffe0000
> > [ 3943.438693][ C112] GPR08: 0000000000000000 00000000000000e1 0000000000000000 c00000000299ccd8
> > [ 3943.438693][ C112] GPR12: 0000000024088222 c000007ffffb8300 c0000000001bc5b8 c000000deb46f740
> > [ 3943.438693][ C112] GPR16: 0000000000000008 c000000e092fe280 0000000000000001 c000007ffedd7b00
> > [ 3943.438693][ C112] GPR20: 0000000000000001 c0000000029a1280 0000000000000000 0000000000000001
> > [ 3943.438693][ C112] GPR24: 0000000000000000 c000000e092fed3c c000000e16d1fdf0 c00000000299ccd8
> > [ 3943.438693][ C112] GPR28: c000000e16d1fc58 c0000000021fbf00 c000007ffee6bf00 0000000000000001
> > [ 3943.438722][ C112] NIP [c0000000010ff01c] _raw_spin_lock_irqsave+0x4c/0xc0
> > [ 3943.438725][ C112] LR [c0000000001d1064] task_rq_lock+0x64/0x1b0
> > [ 3943.438727][ C112] Call Trace:
> > [ 3943.438728][ C112] [c000000e16d1fb20] [c000000e16d1fb60] 0xc000000e16d1fb60 (unreliable)
> > [ 3943.438731][ C112] [c000000e16d1fb50] [c000000e16d1fbf0] 0xc000000e16d1fbf0
> > [ 3943.438733][ C112] [c000000e16d1fbf0] [c0000000001f214c] newidle_balance+0x4bc/0x940
> > [ 3943.438737][ C112] [c000000e16d1fcf0] [c0000000001f26ac] pick_next_task_fair+0x7c/0x680
> > [ 3943.438739][ C112] [c000000e16d1fd90] [c0000000010f175c] __schedule+0x15c/0x1040
> > [ 3943.438743][ C112] [c000000e16d1fe80] [c0000000010f26b4] schedule+0x74/0x140
> > [ 3943.438747][ C112] [c000000e16d1fef0] [c0000000001afd44] worker_thread+0x134/0x580
> > [ 3943.438749][ C112] [c000000e16d1ff90] [c0000000001bc6e8] kthread+0x138/0x140
> > [ 3943.438753][ C112] [c000000e16d1ffe0] [c00000000000ded8] start_kernel_thread+0x14/0x18
> > [ 3943.438756][ C112] Code: 63e90001 992d0932 a12d0008 3ce0fffe 5529083c 61290001 7d001
> >
> > -----------------------------------------
> >
> > System configuration:
> > --------------------
> >
> > # lscpu
> > Architecture: ppc64le
> > Byte Order: Little Endian
> > CPU(s): 128
> > On-line CPU(s) list: 0-127
> > Thread(s) per core: 4
> > Core(s) per socket: 16
> > Socket(s): 2
> > NUMA node(s): 8
> > Model: 2.3 (pvr 004e 1203)
> > Model name: POWER9 (raw), altivec supported
> > Frequency boost: enabled
> > CPU max MHz: 3800.0000
> > CPU min MHz: 2300.0000
> > L1d cache: 1 MiB
> > L1i cache: 1 MiB
> > NUMA node0 CPU(s): 64-127
> > NUMA node8 CPU(s): 0-63
> > NUMA node250 CPU(s):
> > NUMA node251 CPU(s):
> > NUMA node252 CPU(s):
> > NUMA node253 CPU(s):
> > NUMA node254 CPU(s):
> > NUMA node255 CPU(s):
> >
> > # uname -r
> > 6.5.0-rc2-00028-g7475adccd76b
> >
> > # cat /sys/kernel/debug/sched/features
> > GENTLE_FAIR_SLEEPERS START_DEBIT NO_NEXT_BUDDY LAST_BUDDY
> > CACHE_HOT_BUDDY WAKEUP_PREEMPTION NO_HRTICK NO_HRTICK_DL NO_DOUBLE_TICK
> > NONTASK_CAPACITY TTWU_QUEUE NO_SIS_PROP SIS_UTIL NO_WARN_DOUBLE_CLOCK
> > RT_PUSH_IPI NO_RT_RUNTIME_SHARE NO_LB_MIN ATTACH_AGE_LOAD WA_IDLE
> > WA_WEIGHT WA_BIAS UTIL_EST UTIL_EST_FASTUP NO_LATENCY_WARN ALT_PERIOD
> > BASE_SLICE HZ_BW SHARED_RUNQ
> >
> > -----------------------------------------
> >
> > Please let me know if I've missed anything here. I'll continue
> > investigating and share any additional information I find.
> >
> > Thanks and Regards,
> > Aboorva
> >