Skip to contentSkip to conversation

sched/rt: mitigate root_domain cache line contention

PATCH Superseded Pan Deng 5 participants 47 messages Jul 21, 2025 – May 12

Subsystems (4)

v2 of 3 Superseded Latest is v3 →

lore
Share & tools
lore

Pan Deng

author
#0 lore raw

v2 cover sched/rt: mitigate root_domain cache line contention

When running multi-instance FFmpeg workload in cloud environment, cache line contention is severe during the access to root_domain data structures, which significantly degrades performance.

The SUT is a 2-socket machine with 240 physical cores and 480 logical CPUs. 60 FFmpeg instances are launched, each pinned to 4 physical cores (8 logical CPUs) for transcoding tasks. Sub-threads use RT priority 99 with FIFO scheduling. FPS(frame per second) is used as score.

Profiling shows the kernel consumes ~20% of CPU cycles, which is excessive in this scenario. The overhead primarily comes from RT task scheduling functions like cpupri_set, cpupri_find_fitness, dequeue_pushable_task, enqueue_pushable_task, pull_rt_task, __find_first_and_bit, and __bitmap_and. This is due to read/write contention on root_domain cache lines.

The perf c2c report, sorted by contention severity, reveals:

root_domain cache line 3:
- cpupri->pri_to_cpu[0].count is heavily loaded/stored, since counts[0] is more frequently updated than others along with a rt task enqueues an empty runq or dequeues from a non-overloaded runq.
- rto_mask is heavily loaded
- rto_loop_next and rto_loop_start are frequently stored
- rto_push_work and rto_lock are lightly accessed
- cycles per load: ~10K to 59K.

root_domain cache line 1:
- rto_count is frequently loaded/stored
- overloaded is heavily loaded
- cycles per load: ~2.8K to 44K

cpumask (bitmap) cache line of cpupri_vec->mask:
- bits are loaded during cpupri_find
- bits are stored during cpupri_set
- cycles per load: ~2.2K to 8.7K

The end cache line of cpupri:
- cpupri_vec->count and mask contends. The transcoding threads use rt pri 99, so that the contention occurs in the end.
- cycles per load: ~1.5K to 10.5K

According to above, we propose 4 patches to mitigate the contention, each patch resolves part of above issues:
Patch 1: Reorganize cpupri_vec, separate count, mask fields,
reducing contention on root_domain cache line 3 and cpupri's last cache line. This patch has an alternative implementation, which is described in the patch commit message, welcome any comments.
Patch 2: Restructure root_domain structure to minimize contention of
root_domain cache line 1 and 3 by reordering fields.
Patch 3: Split root_domain->rto_count to per-NUMA-node counters,
reducing the contention on root_domain cache line 1.
Patch 4: Split cpupri_vec->cpumask to per-NUMA-node bitmaps, reducing
load/store contention on the cpumask bitmap cache line.

Evaluation:
The patches are tested non-cumulatively, I'm happly to provide additional data as needed.

FFmpeg benchmark:
Performance changes (FPS):

- Baseline:             100.0%
- Baseline + Patch 1:   111.0%
- Baseline + Patch 2:   105.0%
- Baseline + Patch 3:   104.0%
- Baseline + Patch 4:   103.8%

Kernel CPU cycle usage(lower is better):

- Baseline:              20.0%
- Baseline + Patch 1:    11.0%
- Baseline + Patch 2:    17.7%
- Baseline + Patch 3:    18.6%
- Baseline + Patch 4:    18.7%

Cycles per load reduction (by perf c2c report):
- Patch 1:

  - `root_domain` cache line 3:    10K–59K    ->  0.5K–8K
  - `cpupri` last cache line:      1.5K–10.5K ->  eliminated
- Patch 2:
  - `root_domain` cache line 1:    2.8K–44K   ->  2.1K–2.7K
  - `root_domain` cache line 3:    10K–59K    ->  eliminated

- Patch 3:
- root_domain cache line 1: 2.8K–44K -> eliminated
- Patch 4:
- cpupri_vec->mask cache line: 2.2K–8.7K -> 0.5K–2.2K

stress-ng rt cyclic benchmark:
Command:

stress-ng/stress-ng --cyclic $(nproc) --cyclic-policy fifo   \
                    --timeout 30 --minimize --metrics

Performance changes (bogo ops/s, real time):

- Baseline:             100.0%
- Baseline + Patch 1:   131.4%
- Baseline + Patch 2:   118.6%
- Baseline + Patch 3:   150.4%
- Baseline + Patch 4:   105.9%

rt-tests pi_stress benchmark:
Command:
rt-tests/pi_stress -D 30 -g $(($(nproc) / 2))

Performance changes (Total inversions performed):

- Baseline:             100.0%
- Baseline + Patch 1:   176.5%
- Baseline + Patch 2:   104.7%
- Baseline + Patch 3:   105.1%
- Baseline + Patch 4:   109.3%

Changes since v1:
- Patch 3: Fixed non CONFIG_SMP build issue.
- Patch 1-4: Added stress-ng/cyclic and rt-tests/pi_stress test result.

Comments are appreciated, I'm looking forward to hearing feedback making revisions, thanks a lot!

Pan Deng (4):
sched/rt: Optimize cpupri_vec layout to mitigate cache line contention sched/rt: Restructure root_domain to reduce cacheline contention sched/rt: Split root_domain->rto_count to per-NUMA-node counters sched/rt: Split cpupri_vec->cpumask to per NUMA node to reduce
contention

 kernel/sched/cpupri.c   | 200 ++++++++++++++++++++++++++++++++++++----
 kernel/sched/cpupri.h   |   6 +-
 kernel/sched/rt.c       |  56 ++++++++++-
 kernel/sched/sched.h    |  61 ++++++------
 kernel/sched/topology.c |   7 ++
 5 files changed, 282 insertions(+), 48 deletions(-)

--
2.43.5

author
#1 lore raw

PATCH v2 1/4 sched/rt: Optimize cpupri_vec layout to mitigate cache line contention

When running a multi-instance FFmpeg workload on an HCC system, significant cache line contention is observed around cpupri_vec->count and mask in struct root_domain.

The SUT is a 2-socket machine with 240 physical cores and 480 logical CPUs. 60 FFmpeg instances are launched, each pinned to 4 physical cores (8 logical CPUs) for transcoding tasks. Sub-threads use RT priority 99 with FIFO scheduling. FPS is used as score.

perf c2c tool reveals:
root_domain cache line 3:
- cpupri->pri_to_cpu[0].count (offset 0x38) is heavily loaded/stored and contends with other fields, since counts[0] is more frequently updated than others along with a rt task enqueues an empty runq or dequeues from a non-overloaded runq.
- cycles per load: ~10K to 59K

cpupri's last cache line:
- cpupri_vec->count and mask contends. The transcoding threads use rt pri 99, so that the contention occurs in the end.
- cycles per load: ~1.5K to 10.5K

This change mitigates cpupri_vec->count, mask related contentions by separating each count and mask into different cache lines.

As a result:
- FPS improves by ~11%
- Kernel cycles% drops from ~20% to ~11%
- count and mask related cache line contention is mitigated, perf c2c shows root_domain cache line 3 cycles per load drops from ~10K-59K to ~0.5K-8K, cpupri's last cache line no longer appears in the report.
- stress-ng cyclic benchmark is improved ~31.4%, command:

  stress-ng/stress-ng --cyclic $(nproc) --cyclic-policy fifo   \
                      --timeout 30 --minimize --metrics

- rt-tests/pi_stress is improved ~76.5%, command:
rt-tests/pi_stress -D 30 -g $(($(nproc) / 2))

Appendix:
1. Current layout of contended data structure:
struct root_domain {
...
struct irq_work rto_push_work; /* 120 32 */
/* --- cacheline 2 boundary (128 bytes) was 24 bytes ago --- */
raw_spinlock_t rto_lock; /* 152 4 */
int rto_loop; /* 156 4 */
int rto_cpu; /* 160 4 */
atomic_t rto_loop_next; /* 164 4 */
atomic_t rto_loop_start; /* 168 4 */
/* XXX 4 bytes hole, try to pack */
cpumask_var_t rto_mask; /* 176 8 */
/* --- cacheline 3 boundary (192 bytes) was 8 bytes hence --- */
struct cpupri cpupri; /* 184 1624 */
/* --- cacheline 28 boundary (1792 bytes) was 16 bytes ago --- */
struct perf_domain * pd; /* 1808 8 */
/* size: 1816, cachelines: 29, members: 21 */
/* sum members: 1802, holes: 3, sum holes: 14 */
/* forced alignments: 1 */
/* last cacheline: 24 bytes */
} __attribute__((__aligned__(8)));

2. Perf c2c report of root_domain cache line 3:

-------  -------  ------  ------  ------  ------  ------------------------
 Rmt      Lcl     Store   Data    Load    Total    Symbol
Hitm%    Hitm%   L1 Hit%  offset  cycles  records
-------  -------  ------  ------  ------  ------  ------------------------
 353       44       62    0xff14d42c400e3880
-------  -------  ------  ------  ------  ------  ------------------------
 0.00%    2.27%    0.00%  0x0     21683   6     __flush_smp_call_function_
 0.00%    2.27%    0.00%  0x0     22294   5     __flush_smp_call_function_
 0.28%    0.00%    0.00%  0x0     0       2     irq_work_queue_on
 0.28%    0.00%    0.00%  0x0     27824   4     irq_work_single
 0.00%    0.00%    1.61%  0x0     28151   6     irq_work_queue_on
 0.57%    0.00%    0.00%  0x18    21822   8     native_queued_spin_lock_sl
 0.28%    2.27%    0.00%  0x18    16101   10    native_queued_spin_lock_sl
 0.57%    0.00%    0.00%  0x18    33199   5     native_queued_spin_lock_sl
 0.00%    0.00%    1.61%  0x18    10908   32    _raw_spin_lock
 0.00%    0.00%    1.61%  0x18    59770   2     _raw_spin_lock
 0.00%    0.00%    1.61%  0x18    0       1     _raw_spin_unlock
 1.42%    0.00%    0.00%  0x20    12918   20    pull_rt_task
 0.85%    0.00%   25.81%  0x24    31123   199   pull_rt_task
 0.85%    0.00%    3.23%  0x24    38218   24    pull_rt_task
 0.57%    4.55%   19.35%  0x28    30558   207   pull_rt_task
 0.28%    0.00%    0.00%  0x28    55504   10    pull_rt_task
18.70%   18.18%    0.00%  0x30    26438   291   dequeue_pushable_task
17.28%   22.73%    0.00%  0x30    29347   281   enqueue_pushable_task
 1.70%    2.27%    0.00%  0x30    12819   31    enqueue_pushable_task
 0.28%    0.00%    0.00%  0x30    17726   18    dequeue_pushable_task
34.56%   29.55%    0.00%  0x38    25509   527   cpupri_find_fitness
13.88%   11.36%   24.19%  0x38    30654   342   cpupri_set
 3.12%    2.27%    0.00%  0x38    18093   39    cpupri_set
 1.70%    0.00%    0.00%  0x38    37661   52    cpupri_find_fitness
 1.42%    2.27%   19.35%  0x38    31110   211   cpupri_set
 1.42%    0.00%    1.61%  0x38    45035   31    cpupri_set

3. Perf c2c report of cpupri's last cache line

-------  -------  ------  ------  ------  ------  ------------------------
 Rmt      Lcl     Store   Data    Load    Total    Symbol
Hitm%    Hitm%   L1 Hit%  offset  cycles  records
-------  -------  ------  ------  ------  ------  ------------------------
 149       43       41    0xff14d42c400e3ec0
-------  -------  ------  ------  ------  ------  ------------------------
 8.72%   11.63%    0.00%  0x8     2001    165   cpupri_find_fitness
 1.34%    2.33%    0.00%  0x18    1456    151   cpupri_find_fitness
 8.72%    9.30%   58.54%  0x28    1744    263   cpupri_set
 2.01%    4.65%   41.46%  0x28    1958    301   cpupri_set
 1.34%    0.00%    0.00%  0x28    10580   6     cpupri_set
69.80%   67.44%    0.00%  0x30    1754    347   cpupri_set
 8.05%    4.65%    0.00%  0x30    2144    256   cpupri_set

---
Note: The side effect of this change is that struct cpupri size is increased from 26 cache lines to 203 cache lines.

An alternative implementation of this patch could be separating counts and masks into 2 vectors in cpupri_vec (counts[] and masks[]), and add two paddings:
1. Between counts[0] and counts[1], since counts[0] is more frequently updated than others.
2. Between the two vectors, since counts[] is read-write access while masks[] is read access when it stores pointers.

The alternative introduces the complexity of 31+/21- LoC changes, it achieves almost the same performance, at the same time, struct cpupri size is reduced from 26 cache lines to 21 cache lines.

---
 kernel/sched/cpupri.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/sched/cpupri.h +1 -1
index d6cba0020064..245b0fa626be 100644
@@ -9,7 +9,7 @@
 
 struct cpupri_vec {
 	atomic_t		count;
-	cpumask_var_t		mask;
+	cpumask_var_t		mask	____cacheline_aligned;
 };
 
 struct cpupri {
Signature · 1 line
2.43.5
author
#10 lore raw

PATCH v2 2/4 sched/rt: Restructure root_domain to reduce cacheline contention

In reply to Pan Deng

When running a multi-instance FFmpeg workload on HCC system, significant contention is observed in root_domain cacheline 1 and 3.

The SUT is a 2-socket machine with 240 physical cores and 480 logical CPUs. 60 FFmpeg instances are launched, each pinned to 4 physical cores (8 logical CPUs) for transcoding tasks. Sub-threads use RT priority 99 with FIFO scheduling. FPS is used as score.

perf c2c tool reveals (sorted by contention severity):
root_domain cache line 3:
- cpupri->pri_to_cpu[0].count (offset 0x38) is heavily loaded/stored, since counts[0] is more frequently updated than others along with a rt task enqueues an empty runq or dequeues from a non-overloaded runq.
- rto_mask (0x30) is heavily loaded
- rto_loop_next (0x24) and rto_loop_start (0x28) are frequently stored
- rto_push_work (0x0) and rto_lock (0x18) are lightly accessed
- cycles per load: ~10K to 59K

root_domain cache line 1:
- rto_count (0x4) is frequently loaded/stored
- overloaded (0x28) is heavily loaded
- cycles per load: ~2.8K to 44K:

This change adjusts the layout of root_domain to isolate these contended fields across separate cache lines:
1. rto_count remains in the 1st cache line; overloaded and overutilized are moved to the last cache line
2. rto_push_work is placed in the 2nd cache line
3. rto_loop_start, rto_loop_next, and rto_lock remain in the 3rd cache line; rto_mask is moved near pd in the penultimate cache line
4. cpupri starts at the 4th cache line to prevent pri_to_cpu[0].count contending with fields in cache line 3.

With this change:
- FPS improves by ~5%
- Kernel cycles% drops from ~20% to ~17.7%
- root_domain cache line 3 no longer appears in perf-c2c report
- cycles per load of root_domain cache line 1 is reduced to from ~2.8K-44K to ~2.1K-2.7K
- stress-ng cyclic benchmark is improved ~18.6%, command:

  stress-ng/stress-ng --cyclic $(nproc) --cyclic-policy fifo   \
                      --timeout 30 --minimize --metrics

- rt-tests/pi_stress is improved ~4.7%, command:
rt-tests/pi_stress -D 30 -g $(($(nproc) / 2))

According to the nature of the change, to my understanding, it doesn`t introduce any negative impact in other scenario.

Note: This change increases the size of root_domain from 29 to 31 cache lines, it's considered acceptable since root_domain is a single global object.

Appendix:
1. Current layout of contended data structure:
struct root_domain {

    atomic_t                   refcount;             /*     0     4 */
    atomic_t                   rto_count;            /*     4     4 */

struct callback_head rcu __attribute__((__aligned__(8)));/*8 16 */
cpumask_var_t span; /* 24 8 */
cpumask_var_t online; /* 32 8 */
bool overloaded; /* 40 1 */
bool overutilized; /* 41 1 */
/* XXX 6 bytes hole, try to pack */
cpumask_var_t dlo_mask; /* 48 8 */
atomic_t dlo_count; /* 56 4 */
/* XXX 4 bytes hole, try to pack */

/* --- cacheline 1 boundary (64 bytes) --- */
struct dl_bw dl_bw; /* 64 24 */
struct cpudl cpudl; /* 88 24 */
u64 visit_gen; /* 112 8 */
struct irq_work rto_push_work; /* 120 32 */

/* --- cacheline 2 boundary (128 bytes) was 24 bytes ago --- */
raw_spinlock_t rto_lock; /* 152 4 */
int rto_loop; /* 156 4 */
int rto_cpu; /* 160 4 */
atomic_t rto_loop_next; /* 164 4 */
atomic_t rto_loop_start; /* 168 4 */
/* XXX 4 bytes hole, try to pack */
cpumask_var_t rto_mask; /* 176 8 */

/* --- cacheline 3 boundary (192 bytes) was 8 bytes hence --- */
struct cpupri cpupri; /* 184 1624 */
...
} __attribute__((__aligned__(8)));

2. Perf c2c report of root_domain cache line 3:

-------  -------  ------  ------  ------  ------  ------------------------
 Rmt      Lcl     Store   Data    Load    Total    Symbol
Hitm%    Hitm%   L1 Hit%  offset  cycles  records
-------  -------  ------  ------  ------  ------  ------------------------
 353       44       62    0xff14d42c400e3880
-------  -------  ------  ------  ------  ------  ------------------------
 0.00%    2.27%    0.00%  0x0     21683   6     __flush_smp_call_function_
 0.00%    2.27%    0.00%  0x0     22294   5     __flush_smp_call_function_
 0.28%    0.00%    0.00%  0x0     0       2     irq_work_queue_on
 0.28%    0.00%    0.00%  0x0     27824   4     irq_work_single
 0.00%    0.00%    1.61%  0x0     28151   6     irq_work_queue_on
 0.57%    0.00%    0.00%  0x18    21822   8     native_queued_spin_lock_sl
 0.28%    2.27%    0.00%  0x18    16101   10    native_queued_spin_lock_sl
 0.57%    0.00%    0.00%  0x18    33199   5     native_queued_spin_lock_sl
 0.00%    0.00%    1.61%  0x18    10908   32    _raw_spin_lock
 0.00%    0.00%    1.61%  0x18    59770   2     _raw_spin_lock
 0.00%    0.00%    1.61%  0x18    0       1     _raw_spin_unlock
 1.42%    0.00%    0.00%  0x20    12918   20    pull_rt_task
 0.85%    0.00%   25.81%  0x24    31123   199   pull_rt_task
 0.85%    0.00%    3.23%  0x24    38218   24    pull_rt_task
 0.57%    4.55%   19.35%  0x28    30558   207   pull_rt_task
 0.28%    0.00%    0.00%  0x28    55504   10    pull_rt_task
18.70%   18.18%    0.00%  0x30    26438   291   dequeue_pushable_task
17.28%   22.73%    0.00%  0x30    29347   281   enqueue_pushable_task
 1.70%    2.27%    0.00%  0x30    12819   31    enqueue_pushable_task
 0.28%    0.00%    0.00%  0x30    17726   18    dequeue_pushable_task
34.56%   29.55%    0.00%  0x38    25509   527   cpupri_find_fitness
13.88%   11.36%   24.19%  0x38    30654   342   cpupri_set
 3.12%    2.27%    0.00%  0x38    18093   39    cpupri_set
 1.70%    0.00%    0.00%  0x38    37661   52    cpupri_find_fitness
 1.42%    2.27%   19.35%  0x38    31110   211   cpupri_set
 1.42%    0.00%    1.61%  0x38    45035   31    cpupri_set

3. Perf c2c report of root_domain cache line 1:

-------  -------  ------  ------  ------  ------  ------------------------
 Rmt      Lcl     Store   Data    Load    Total    Symbol
Hitm%    Hitm%   L1 Hit%  offset  cycles  records
-------  -------  ------  ------  ------  ------  ------------------------
 231       43       48    0xff14d42c400e3800
-------  -------  ------  ------  ------  ------  ------------------------
22.51%   18.60%    0.00%  0x4     5041    247   pull_rt_task
 5.63%    2.33%   45.83%  0x4     6995    315   dequeue_pushable_task
 3.90%    4.65%   54.17%  0x4     6587    370   enqueue_pushable_task
 0.43%    0.00%    0.00%  0x4     17111   4     enqueue_pushable_task
 0.43%    0.00%    0.00%  0x4     44062   4     dequeue_pushable_task
32.03%   27.91%    0.00%  0x28    6393    285   enqueue_task_rt
16.45%   27.91%    0.00%  0x28    5534    139   sched_balance_newidle
14.72%   18.60%    0.00%  0x28    5287    110   dequeue_task_rt
 3.46%    0.00%    0.00%  0x28    2820    25    enqueue_task_fair
 0.43%    0.00%    0.00%  0x28    220     3     enqueue_task_stop
---
 kernel/sched/sched.h | 52 +++++++++++++++++++++++---------------------
 1 file changed, 27 insertions(+), 25 deletions(-)
kernel/sched/sched.h +27 -25
index 83e3aa917142..bc67806911f2 100644
@@ -968,24 +968,29 @@ struct root_domain {
 	cpumask_var_t		span;
 	cpumask_var_t		online;
 
+	atomic_t		dlo_count;
+	struct dl_bw		dl_bw;
+	struct cpudl		cpudl;
+
+#ifdef HAVE_RT_PUSH_IPI
 	/*
-	 * Indicate pullable load on at least one CPU, e.g:
-	 * - More than one runnable task
-	 * - Running task is misfit
+	 * For IPI pull requests, loop across the rto_mask.
 	 */
-	bool			overloaded;
-
-	/* Indicate one or more CPUs over-utilized (tipping point) */
-	bool			overutilized;
+	struct irq_work		rto_push_work;
+	raw_spinlock_t		rto_lock;
+	/* These are only updated and read within rto_lock */
+	int			rto_loop;
+	int			rto_cpu;
+	/* These atomics are updated outside of a lock */
+	atomic_t		rto_loop_next;
+	atomic_t		rto_loop_start;
+#endif
 
 	/*
 	 * The bit corresponding to a CPU gets set here if such CPU has more
 	 * than one runnable -deadline task (as it is below for RT tasks).
 	 */
 	cpumask_var_t		dlo_mask;
-	atomic_t		dlo_count;
-	struct dl_bw		dl_bw;
-	struct cpudl		cpudl;
 
 	/*
 	 * Indicate whether a root_domain's dl_bw has been checked or
@@ -995,32 +1000,29 @@ struct root_domain {
 	 * that u64 is 'big enough'. So that shouldn't be a concern.
 	 */
 	u64 visit_cookie;
+	struct cpupri		cpupri	____cacheline_aligned;
 
-#ifdef HAVE_RT_PUSH_IPI
 	/*
-	 * For IPI pull requests, loop across the rto_mask.
+	 * NULL-terminated list of performance domains intersecting with the
+	 * CPUs of the rd. Protected by RCU.
 	 */
-	struct irq_work		rto_push_work;
-	raw_spinlock_t		rto_lock;
-	/* These are only updated and read within rto_lock */
-	int			rto_loop;
-	int			rto_cpu;
-	/* These atomics are updated outside of a lock */
-	atomic_t		rto_loop_next;
-	atomic_t		rto_loop_start;
-#endif
+	struct perf_domain __rcu *pd	____cacheline_aligned;
+
 	/*
 	 * The "RT overload" flag: it gets set if a CPU has more than
 	 * one runnable RT task.
 	 */
 	cpumask_var_t		rto_mask;
-	struct cpupri		cpupri;
 
 	/*
-	 * NULL-terminated list of performance domains intersecting with the
-	 * CPUs of the rd. Protected by RCU.
+	 * Indicate pullable load on at least one CPU, e.g:
+	 * - More than one runnable task
+	 * - Running task is misfit
 	 */
-	struct perf_domain __rcu *pd;
+	bool			overloaded	____cacheline_aligned;
+
+	/* Indicate one or more CPUs over-utilized (tipping point) */
+	bool			overutilized;
 };
 
 extern void init_defrootdomain(void);
Signature · 1 line
2.43.5
author
#12 lore raw

PATCH v2 3/4 sched/rt: Split root_domain->rto_count to per-NUMA-node counters

In reply to Pan Deng

When running a multi-instance FFmpeg workload on HCC system, significant contention is observed on root_domain rto_count and overloaded fields.

The SUT is a 2-socket machine with 240 physical cores and 480 logical CPUs. 60 FFmpeg instances are launched, each pinned to 4 physical cores (8 logical CPUs) for transcoding tasks. Sub-threads use RT priority 99 with FIFO scheduling. FPS is used as score.

perf c2c tool reveals:
root_domain cache line 1:
- rto_count (0x4) is frequently loaded/stored
- overloaded (0x28) is heavily loaded
- cycles per load: ~2.8K to 44K:

A separate patch rearranges root_domain to place overloaded on a different cache line, but this alone is insufficient to resolve the contention on rto_count. As a complementary, this patch splits rto_count into per-numa-node counters to reduce the contention.

With this change:
- FPS improves by ~4%
- Kernel cycles% drops from ~20% to ~18.6%
- The cache line no longer appears in perf-c2c report
- stress-ng cyclic benchmark is improved ~50.4%, command:

  stress-ng/stress-ng --cyclic $(nproc) --cyclic-policy fifo   \
                      --timeout 30 --minimize --metrics

- rt-tests/pi_stress is improved ~5.1%, command:
rt-tests/pi_stress -D 30 -g $(($(nproc) / 2))

Appendix:
1. Perf c2c report of root_domain cache line 1:

-------  -------  ------  ------  ------  ------  ------------------------
 Rmt      Lcl     Store   Data    Load    Total    Symbol
Hitm%    Hitm%   L1 Hit%  offset  cycles  records
-------  -------  ------  ------  ------  ------  ------------------------
 231       43       48    0xff14d42c400e3800
-------  -------  ------  ------  ------  ------  ------------------------
22.51%   18.60%    0.00%  0x4     5041    247   pull_rt_task
 5.63%    2.33%   45.83%  0x4     6995    315   dequeue_pushable_task
 3.90%    4.65%   54.17%  0x4     6587    370   enqueue_pushable_task
 0.43%    0.00%    0.00%  0x4     17111   4     enqueue_pushable_task
 0.43%    0.00%    0.00%  0x4     44062   4     dequeue_pushable_task
32.03%   27.91%    0.00%  0x28    6393    285   enqueue_task_rt
16.45%   27.91%    0.00%  0x28    5534    139   sched_balance_newidle
14.72%   18.60%    0.00%  0x28    5287    110   dequeue_task_rt
 3.46%    0.00%    0.00%  0x28    2820    25    enqueue_task_fair
 0.43%    0.00%    0.00%  0x28    220     3     enqueue_task_stop

---
V1 -> V2: Fixed non CONFIG_SMP build issue

---
 kernel/sched/rt.c       | 56 ++++++++++++++++++++++++++++++++++++++---
 kernel/sched/sched.h    |  9 ++++++-
 kernel/sched/topology.c |  7 ++++++
 3 files changed, 68 insertions(+), 4 deletions(-)
kernel/sched/rt.c +53 -3
index e40422c37033..cbcfd3aa3439 100644
@@ -337,9 +337,58 @@ static inline bool need_pull_rt_task(struct rq *rq, struct task_struct *prev)
 	return rq->online && rq->rt.highest_prio.curr > prev->prio;
 }
 
+int rto_counts_init(atomic_tp **rto_counts)
+{
+	int i;
+	atomic_tp *counts = kzalloc(nr_node_ids * sizeof(atomic_tp), GFP_KERNEL);
+
+	if (!counts)
+		return -ENOMEM;
+
+	for (i = 0; i < nr_node_ids; i++) {
+		counts[i] = kzalloc_node(sizeof(atomic_t), GFP_KERNEL, i);
+
+		if (!counts[i])
+			goto cleanup;
+	}
+
+	*rto_counts = counts;
+	return 0;
+
+cleanup:
+	while (i--)
+		kfree(counts[i]);
+
+	kfree(counts);
+	return -ENOMEM;
+}
+
+void rto_counts_cleanup(atomic_tp *rto_counts)
+{
+	for (int i = 0; i < nr_node_ids; i++)
+		kfree(rto_counts[i]);
+
+	kfree(rto_counts);
+}
+
 static inline int rt_overloaded(struct rq *rq)
 {
-	return atomic_read(&rq->rd->rto_count);
+	int count = 0;
+	int cur_node, nid;
+
+	cur_node = numa_node_id();
+
+	for (int i = 0; i < nr_node_ids; i++) {
+		nid = (cur_node + i) % nr_node_ids;
+		count += atomic_read(rq->rd->rto_counts[nid]);
+
+		// The caller only checks if it is 0
+		// or 1, so that return once > 1
+		if (count > 1)
+			return count;
+	}
+
+	return count;
 }
 
 static inline void rt_set_overload(struct rq *rq)
@@ -358,7 +407,7 @@ static inline void rt_set_overload(struct rq *rq)
 	 * Matched by the barrier in pull_rt_task().
 	 */
 	smp_wmb();
-	atomic_inc(&rq->rd->rto_count);
+	atomic_inc(rq->rd->rto_counts[cpu_to_node(rq->cpu)]);
 }
 
 static inline void rt_clear_overload(struct rq *rq)
@@ -367,7 +416,7 @@ static inline void rt_clear_overload(struct rq *rq)
 		return;
 
 	/* the order here really doesn't matter */
-	atomic_dec(&rq->rd->rto_count);
+	atomic_dec(rq->rd->rto_counts[cpu_to_node(rq->cpu)]);
 	cpumask_clear_cpu(rq->cpu, rq->rd->rto_mask);
 }
 
@@ -443,6 +492,7 @@ static inline void dequeue_pushable_task(struct rq *rq, struct task_struct *p)
 static inline void rt_queue_push_tasks(struct rq *rq)
 {
 }
+
 #endif /* CONFIG_SMP */
 
 static void enqueue_top_rt_rq(struct rt_rq *rt_rq);
kernel/sched/sched.h +8 -1
index bc67806911f2..13fc3ac3381b 100644
@@ -953,6 +953,8 @@ struct perf_domain {
 	struct rcu_head rcu;
 };
 
+typedef atomic_t *atomic_tp;
+
 /*
  * We add the notion of a root-domain which will be used to define per-domain
  * variables. Each exclusive cpuset essentially defines an island domain by
@@ -963,12 +965,15 @@ struct perf_domain {
  */
 struct root_domain {
 	atomic_t		refcount;
-	atomic_t		rto_count;
 	struct rcu_head		rcu;
 	cpumask_var_t		span;
 	cpumask_var_t		online;
 
 	atomic_t		dlo_count;
+
+	/* rto_count per node */
+	atomic_tp		*rto_counts;
+
 	struct dl_bw		dl_bw;
 	struct cpudl		cpudl;
 
@@ -1030,6 +1035,8 @@ extern int sched_init_domains(const struct cpumask *cpu_map);
 extern void rq_attach_root(struct rq *rq, struct root_domain *rd);
 extern void sched_get_rd(struct root_domain *rd);
 extern void sched_put_rd(struct root_domain *rd);
+extern int rto_counts_init(atomic_tp **rto_counts);
+extern void rto_counts_cleanup(atomic_tp *rto_counts);
 
 static inline int get_rd_overloaded(struct root_domain *rd)
 {
kernel/sched/topology.c +7 -0
index b958fe48e020..166dc8177a44 100644
@@ -457,6 +457,7 @@ static void free_rootdomain(struct rcu_head *rcu)
 {
 	struct root_domain *rd = container_of(rcu, struct root_domain, rcu);
 
+	rto_counts_cleanup(rd->rto_counts);
 	cpupri_cleanup(&rd->cpupri);
 	cpudl_cleanup(&rd->cpudl);
 	free_cpumask_var(rd->dlo_mask);
@@ -549,8 +550,14 @@ static int init_rootdomain(struct root_domain *rd)
 
 	if (cpupri_init(&rd->cpupri) != 0)
 		goto free_cpudl;
+
+	if (rto_counts_init(&rd->rto_counts) != 0)
+		goto free_cpupri;
+
 	return 0;
 
+free_cpupri:
+	cpupri_cleanup(&rd->cpupri);
 free_cpudl:
 	cpudl_cleanup(&rd->cpudl);
 free_rto_mask:
Signature · 1 line
2.43.5
author
#17 lore raw

PATCH v2 4/4 sched/rt: Split cpupri_vec->cpumask to per NUMA node to reduce contention

In reply to Pan Deng

When running a multi-instance FFmpeg workload on HCC system, significant contention is observed on bitmap of cpupri_vec->cpumask.

The SUT is a 2-socket machine with 240 physical cores and 480 logical CPUs. 60 FFmpeg instances are launched, each pinned to 4 physical cores (8 logical CPUs) for transcoding tasks. Sub-threads use RT priority 99 with FIFO scheduling. FPS is used as score.

perf c2c tool reveals:
cpumask (bitmap) cache line of cpupri_vec->mask:
- bits are loaded during cpupri_find
- bits are stored during cpupri_set
- cycles per load: ~2.2K to 8.7K

This change splits cpupri_vec->cpumask into per-NUMA-node data to mitigate false sharing.

As a result:
- FPS improves by ~3.8%
- Kernel cycles% drops from ~20% to ~18.7%
- Cache line contention is mitigated, perf-c2c shows cycles per load drops from ~2.2K-8.7K to ~0.5K-2.2K
- stress-ng cyclic benchmark is improved ~5.9%, command:

  stress-ng/stress-ng --cyclic $(nproc) --cyclic-policy fifo   \
                      --timeout 30 --minimize --metrics

- rt-tests/pi_stress is improved ~9.3%, command:
rt-tests/pi_stress -D 30 -g $(($(nproc) / 2))

Note: CONFIG_CPUMASK_OFFSTACK=n remains unchanged.

Appendix:
1. Perf c2c report of cpupri_vec->mask bitmap cache line:

-------  -------  ------  ------  ------  ------  ------------------------
 Rmt      Lcl     Store   Data    Load    Total    Symbol
Hitm%    Hitm%   L1 Hit%  offset  cycles  records
-------  -------  ------  ------  ------  ------  ------------------------
 155       39       39    0xff14d52c4682d800
-------  -------  ------  ------  ------  ------  ------------------------
43.23%   43.59%    0.00%  0x0     3489    415   _find_first_and_bit
 3.23%    5.13%    0.00%  0x0     3478    107   __bitmap_and
 3.23%    0.00%    0.00%  0x0     2712    33    _find_first_and_bit
 1.94%    0.00%    7.69%  0x0     5992    33    cpupri_set
 0.00%    0.00%    5.13%  0x0     3733    19    cpupri_set
12.90%   12.82%    0.00%  0x8     3452    297   _find_first_and_bit
 1.29%    2.56%    0.00%  0x8     3007    117   __bitmap_and
 0.00%    5.13%    0.00%  0x8     3041    20    _find_first_and_bit
 0.00%    2.56%    2.56%  0x8     2374    22    cpupri_set
 0.00%    0.00%    7.69%  0x8     4194    38    cpupri_set
 8.39%    2.56%    0.00%  0x10    3336    264   _find_first_and_bit
 3.23%    0.00%    0.00%  0x10    3023    46    _find_first_and_bit
 2.58%    0.00%    0.00%  0x10    3040    130   __bitmap_and
 1.29%    0.00%   12.82%  0x10    4075    34    cpupri_set
 0.00%    0.00%    2.56%  0x10    2197    19    cpupri_set
 0.00%    2.56%    7.69%  0x18    4085    27    cpupri_set
 0.00%    2.56%    0.00%  0x18    3128    220   _find_first_and_bit
 0.00%    0.00%    5.13%  0x18    3028    20    cpupri_set
 2.58%    2.56%    0.00%  0x20    3089    198   _find_first_and_bit
 1.29%    0.00%    5.13%  0x20    5114    29    cpupri_set
 0.65%    2.56%    0.00%  0x20    3224    96    __bitmap_and
 0.65%    0.00%    7.69%  0x20    4392    31    cpupri_set
 2.58%    0.00%    0.00%  0x28    3327    214   _find_first_and_bit
 0.65%    2.56%    5.13%  0x28    5252    31    cpupri_set
 0.65%    0.00%    7.69%  0x28    8755    25    cpupri_set
 0.65%    0.00%    0.00%  0x28    4414    14    _find_first_and_bit
 1.29%    2.56%    0.00%  0x30    3139    171   _find_first_and_bit
 0.65%    0.00%    7.69%  0x30    2185    18    cpupri_set
 0.65%    0.00%    0.00%  0x30    3404    108   __bitmap_and
 0.00%    0.00%    2.56%  0x30    5542    21    cpupri_set
 3.23%    5.13%    0.00%  0x38    3493    190   _find_first_and_bit
 3.23%    2.56%    0.00%  0x38    3171    108   __bitmap_and
 0.00%    2.56%    7.69%  0x38    3285    14    cpupri_set
 0.00%    0.00%    5.13%  0x38    4035    27    cpupri_set
---
 kernel/sched/cpupri.c | 200 ++++++++++++++++++++++++++++++++++++++----
 kernel/sched/cpupri.h |   4 +
 2 files changed, 186 insertions(+), 18 deletions(-)
kernel/sched/cpupri.c +182 -18
index 42c40cfdf836..306b6baff4cd 100644
@@ -64,6 +64,143 @@ static int convert_prio(int prio)
 	return cpupri;
 }
 
+#ifdef	CONFIG_CPUMASK_OFFSTACK
+static inline int alloc_vec_masks(struct cpupri_vec *vec)
+{
+	int i;
+
+	for (i = 0; i < nr_node_ids; i++) {
+		if (!zalloc_cpumask_var_node(&vec->masks[i], GFP_KERNEL, i))
+			goto cleanup;
+
+		// Clear masks of cur node, set others
+		bitmap_complement(cpumask_bits(vec->masks[i]),
+			cpumask_bits(cpumask_of_node(i)), small_cpumask_bits);
+	}
+	return 0;
+
+cleanup:
+	while (i--)
+		free_cpumask_var(vec->masks[i]);
+	return -ENOMEM;
+}
+
+static inline void free_vec_masks(struct cpupri_vec *vec)
+{
+	for (int i = 0; i < nr_node_ids; i++)
+		free_cpumask_var(vec->masks[i]);
+}
+
+static inline int setup_vec_mask_var_ts(struct cpupri *cp)
+{
+	int i;
+
+	for (i = 0; i < CPUPRI_NR_PRIORITIES; i++) {
+		struct cpupri_vec *vec = &cp->pri_to_cpu[i];
+
+		vec->masks = kcalloc(nr_node_ids, sizeof(cpumask_var_t), GFP_KERNEL);
+		if (!vec->masks)
+			goto cleanup;
+	}
+	return 0;
+
+cleanup:
+	/* Free any already allocated masks */
+	while (i--) {
+		kfree(cp->pri_to_cpu[i].masks);
+		cp->pri_to_cpu[i].masks = NULL;
+	}
+
+	return -ENOMEM;
+}
+
+static inline void free_vec_mask_var_ts(struct cpupri *cp)
+{
+	for (int i = 0; i < CPUPRI_NR_PRIORITIES; i++) {
+		kfree(cp->pri_to_cpu[i].masks);
+		cp->pri_to_cpu[i].masks = NULL;
+	}
+}
+
+static inline int
+available_cpu_in_nodes(struct task_struct *p, struct cpupri_vec *vec)
+{
+	int cur_node = numa_node_id();
+
+	for (int i = 0; i < nr_node_ids; i++) {
+		int nid = (cur_node + i) % nr_node_ids;
+
+		if (cpumask_first_and_and(&p->cpus_mask, vec->masks[nid],
+					cpumask_of_node(nid)) < nr_cpu_ids)
+			return 1;
+	}
+
+	return 0;
+}
+
+#define available_cpu_in_vec available_cpu_in_nodes
+
+#else /* !CONFIG_CPUMASK_OFFSTACK */
+
+static inline int alloc_vec_masks(struct cpupri_vec *vec)
+{
+	if (!zalloc_cpumask_var(&vec->mask, GFP_KERNEL))
+		return -ENOMEM;
+
+	return 0;
+}
+
+static inline void free_vec_masks(struct cpupri_vec *vec)
+{
+	free_cpumask_var(vec->mask);
+}
+
+static inline int setup_vec_mask_var_ts(struct cpupri *cp)
+{
+	return 0;
+}
+
+static inline void free_vec_mask_var_ts(struct cpupri *cp)
+{
+}
+
+static inline int
+available_cpu_in_vec(struct task_struct *p, struct cpupri_vec *vec)
+{
+	if (cpumask_any_and(&p->cpus_mask, vec->mask) >= nr_cpu_ids)
+		return 0;
+
+	return 1;
+}
+#endif
+
+static inline int alloc_all_masks(struct cpupri *cp)
+{
+	int i;
+
+	for (i = 0; i < CPUPRI_NR_PRIORITIES; i++) {
+		if (alloc_vec_masks(&cp->pri_to_cpu[i]))
+			goto cleanup;
+	}
+
+	return 0;
+
+cleanup:
+	while (i--)
+		free_vec_masks(&cp->pri_to_cpu[i]);
+
+	return -ENOMEM;
+}
+
+static inline void setup_vec_counts(struct cpupri *cp)
+{
+	for (int i = 0; i < CPUPRI_NR_PRIORITIES; i++) {
+		struct cpupri_vec *vec = &cp->pri_to_cpu[i];
+
+		atomic_set(&vec->count, 0);
+	}
+}
+
 static inline int __cpupri_find(struct cpupri *cp, struct task_struct *p,
 				struct cpumask *lowest_mask, int idx)
 {
@@ -96,11 +233,24 @@ static inline int __cpupri_find(struct cpupri *cp, struct task_struct *p,
 	if (skip)
 		return 0;
 
-	if (cpumask_any_and(&p->cpus_mask, vec->mask) >= nr_cpu_ids)
+	if (!available_cpu_in_vec(p, vec))
 		return 0;
 
+#ifdef	CONFIG_CPUMASK_OFFSTACK
+	struct cpumask *cpupri_mask = lowest_mask;
+
+	// available && lowest_mask
+	if (lowest_mask) {
+		cpumask_copy(cpupri_mask, vec->masks[0]);
+		for (int nid = 1; nid < nr_node_ids; nid++)
+			cpumask_and(cpupri_mask, cpupri_mask, vec->masks[nid]);
+	}
+#else
+	struct cpumask *cpupri_mask = vec->mask;
+#endif
+
 	if (lowest_mask) {
-		cpumask_and(lowest_mask, &p->cpus_mask, vec->mask);
+		cpumask_and(lowest_mask, &p->cpus_mask, cpupri_mask);
 		cpumask_and(lowest_mask, lowest_mask, cpu_active_mask);
 
 		/*
@@ -229,7 +379,11 @@ void cpupri_set(struct cpupri *cp, int cpu, int newpri)
 	if (likely(newpri != CPUPRI_INVALID)) {
 		struct cpupri_vec *vec = &cp->pri_to_cpu[newpri];
 
+#ifdef	CONFIG_CPUMASK_OFFSTACK
+		cpumask_set_cpu(cpu, vec->masks[cpu_to_node(cpu)]);
+#else
 		cpumask_set_cpu(cpu, vec->mask);
+#endif
 		/*
 		 * When adding a new vector, we update the mask first,
 		 * do a write memory barrier, and then update the count, to
@@ -263,7 +417,11 @@ void cpupri_set(struct cpupri *cp, int cpu, int newpri)
 		 */
 		atomic_dec(&(vec)->count);
 		smp_mb__after_atomic();
+#ifdef	CONFIG_CPUMASK_OFFSTACK
+		cpumask_clear_cpu(cpu, vec->masks[cpu_to_node(cpu)]);
+#else
 		cpumask_clear_cpu(cpu, vec->mask);
+#endif
 	}
 
 	*currpri = newpri;
@@ -279,26 +437,31 @@ int cpupri_init(struct cpupri *cp)
 {
 	int i;
 
-	for (i = 0; i < CPUPRI_NR_PRIORITIES; i++) {
-		struct cpupri_vec *vec = &cp->pri_to_cpu[i];
-
-		atomic_set(&vec->count, 0);
-		if (!zalloc_cpumask_var(&vec->mask, GFP_KERNEL))
-			goto cleanup;
-	}
-
+	/* Allocate the cpu_to_pri array */
 	cp->cpu_to_pri = kcalloc(nr_cpu_ids, sizeof(int), GFP_KERNEL);
 	if (!cp->cpu_to_pri)
-		goto cleanup;
+		return -ENOMEM;
 
+	/* Initialize all CPUs to invalid priority */
 	for_each_possible_cpu(i)
 		cp->cpu_to_pri[i] = CPUPRI_INVALID;
 
+	/* Setup priority vectors */
+	setup_vec_counts(cp);
+	if (setup_vec_mask_var_ts(cp))
+		goto fail_setup_vectors;
+
+	/* Allocate masks for each priority vector */
+	if (alloc_all_masks(cp))
+		goto fail_alloc_masks;
+
 	return 0;
 
-cleanup:
-	for (i--; i >= 0; i--)
-		free_cpumask_var(cp->pri_to_cpu[i].mask);
+fail_alloc_masks:
+	free_vec_mask_var_ts(cp);
+
+fail_setup_vectors:
+	kfree(cp->cpu_to_pri);
 	return -ENOMEM;
 }
 
@@ -308,9 +471,10 @@ int cpupri_init(struct cpupri *cp)
  */
 void cpupri_cleanup(struct cpupri *cp)
 {
-	int i;
-
 	kfree(cp->cpu_to_pri);
-	for (i = 0; i < CPUPRI_NR_PRIORITIES; i++)
-		free_cpumask_var(cp->pri_to_cpu[i].mask);
+
+	for (int i = 0; i < CPUPRI_NR_PRIORITIES; i++)
+		free_vec_masks(&cp->pri_to_cpu[i]);
+
+	free_vec_mask_var_ts(cp);
 }
kernel/sched/cpupri.h +4 -0
index 245b0fa626be..c53f1f4dad86 100644
@@ -9,7 +9,11 @@
 
 struct cpupri_vec {
 	atomic_t		count;
+#ifdef CONFIG_CPUMASK_OFFSTACK
+	cpumask_var_t		*masks	____cacheline_aligned;
+#else
 	cpumask_var_t		mask	____cacheline_aligned;
+#endif
 };
 
 struct cpupri {
Signature · 1 line
2.43.5
maintainer
#45 lore raw
In reply to Pan Deng
Quoted 5 lines · Pan Deng

When running multi-instance FFmpeg workload in cloud environment, cache line contention is severe during the access to root_domain data structures, which significantly degrades performance.

The SUT is a 2-socket machine with 240 physical cores and 480 logical

What's a SUT?

Quoted 3 lines

CPUs. 60 FFmpeg instances are launched, each pinned to 4 physical cores (8 logical CPUs) for transcoding tasks. Sub-threads use RT priority 99 with FIFO scheduling. FPS(frame per second) is used as score.

So I think we can do some of this, but that workload is hilariously poorly configured.

You're pinning things but not partitioning, why? If you would have created 60 partitions, one for each FFmpeg thingy, then you wouldn't have needed any of this.

You're running at FIFO99 (IOW prio-0) and then claiming prio-0 is used more heavily than others... will d0h. What priority assignment scheme led to this? Is there a sensible reason these must be 99?

maintainer
#2 lore raw

Re: [PATCH v2 1/4] sched/rt: Optimize cpupri_vec layout to mitigate cache line contention

In reply to Pan Deng
Quoted 17 lines · Pan Deng

When running a multi-instance FFmpeg workload on an HCC system, significant cache line contention is observed around cpupri_vec->count and mask in struct root_domain.

The SUT is a 2-socket machine with 240 physical cores and 480 logical CPUs. 60 FFmpeg instances are launched, each pinned to 4 physical cores (8 logical CPUs) for transcoding tasks. Sub-threads use RT priority 99 with FIFO scheduling. FPS is used as score.

perf c2c tool reveals:
root_domain cache line 3:
- cpupri->pri_to_cpu[0].count (offset 0x38) is heavily loaded/stored and contends with other fields, since counts[0] is more frequently updated than others along with a rt task enqueues an empty runq or dequeues from a non-overloaded runq.
- cycles per load: ~10K to 59K

Quoted 7 lines

cpupri's last cache line:
- cpupri_vec->count and mask contends. The transcoding threads use rt pri 99, so that the contention occurs in the end.
- cycles per load: ~1.5K to 10.5K

This change mitigates cpupri_vec->count, mask related contentions by separating each count and mask into different cache lines.

Right.

Quoted 2 lines

Note: The side effect of this change is that struct cpupri size is increased from 26 cache lines to 203 cache lines.

That is pretty horrible, but probably unavoidable.

Quoted 5 lines

An alternative implementation of this patch could be separating counts and masks into 2 vectors in cpupri_vec (counts[] and masks[]), and add two paddings:
1. Between counts[0] and counts[1], since counts[0] is more frequently updated than others.

That is completely workload specific; it is a direct consequence of your (probably busted) priority assignment scheme.

Quoted 6 lines

2. Between the two vectors, since counts[] is read-write access while masks[] is read access when it stores pointers.

The alternative introduces the complexity of 31+/21- LoC changes, it achieves almost the same performance, at the same time, struct cpupri size is reduced from 26 cache lines to 21 cache lines.

That is not an alternative, since it very specifically only deals with fifo-99 contention.

Quoted 9 lines
---
 kernel/sched/cpupri.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/sched/cpupri.h +0 -0
index d6cba0020064..245b0fa626be 100644

kernel/sched/cpupri.h line 13

Quoted 6 lines
kernel/sched/cpupri.h +1 -1
@@ -9,7 +9,7 @@
 
 struct cpupri_vec {
 	atomic_t		count;
-	cpumask_var_t		mask;
+	cpumask_var_t		mask	____cacheline_aligned;
 };

At the very least this needs a comment, explaining the what and how of it.

maintainer
#11 lore raw

Re: [PATCH v2 2/4] sched/rt: Restructure root_domain to reduce cacheline contention

In reply to Pan Deng
Quoted 2 lines · Pan Deng

When running a multi-instance FFmpeg workload on HCC system, significant contention is observed in root_domain cacheline 1 and 3.

What's a HCC? Hobby Computer Club? Google is telling me it is the most prevalent form of liver cancer, but I somehow doubt that is what you're on about.

Quoted 1 line

The SUT is a 2-socket machine with 240 physical cores and 480 logical

Satellite User Terminal? Subsea Umbilical Termination? Small Unit Transceiver? Single Unit Test?

Quoted 3 lines

CPUs. 60 FFmpeg instances are launched, each pinned to 4 physical cores (8 logical CPUs) for transcoding tasks. Sub-threads use RT priority 99 with FIFO scheduling. FPS is used as score.

Yes yes, poorly configured systems hurt.

Quoted 37 lines

perf c2c tool reveals (sorted by contention severity):
root_domain cache line 3:
- cpupri->pri_to_cpu[0].count (offset 0x38) is heavily loaded/stored, since counts[0] is more frequently updated than others along with a rt task enqueues an empty runq or dequeues from a non-overloaded runq.
- rto_mask (0x30) is heavily loaded
- rto_loop_next (0x24) and rto_loop_start (0x28) are frequently stored
- rto_push_work (0x0) and rto_lock (0x18) are lightly accessed
- cycles per load: ~10K to 59K

root_domain cache line 1:
- rto_count (0x4) is frequently loaded/stored
- overloaded (0x28) is heavily loaded
- cycles per load: ~2.8K to 44K:

This change adjusts the layout of root_domain to isolate these contended fields across separate cache lines:
1. rto_count remains in the 1st cache line; overloaded and overutilized are moved to the last cache line
2. rto_push_work is placed in the 2nd cache line
3. rto_loop_start, rto_loop_next, and rto_lock remain in the 3rd cache line; rto_mask is moved near pd in the penultimate cache line
4. cpupri starts at the 4th cache line to prevent pri_to_cpu[0].count contending with fields in cache line 3.

With this change:
- FPS improves by ~5%
- Kernel cycles% drops from ~20% to ~17.7%
- root_domain cache line 3 no longer appears in perf-c2c report
- cycles per load of root_domain cache line 1 is reduced to from ~2.8K-44K to ~2.1K-2.7K
- stress-ng cyclic benchmark is improved ~18.6%, command:

  stress-ng/stress-ng --cyclic $(nproc) --cyclic-policy fifo   \
                      --timeout 30 --minimize --metrics

- rt-tests/pi_stress is improved ~4.7%, command:
rt-tests/pi_stress -D 30 -g $(($(nproc) / 2))

Quoted 6 lines

According to the nature of the change, to my understanding, it doesn`t introduce any negative impact in other scenario.

Note: This change increases the size of root_domain from 29 to 31 cache lines, it's considered acceptable since root_domain is a single global object.

Uhm, what? We're at 207 cachelines due to that previous patch, remember? A few more don't matter at this point I would guess.

It doesn't actually apply anymore, but it needs the very same that previous patch did -- more comments.

maintainer
#13 lore raw

Re: [PATCH v2 3/4] sched/rt: Split root_domain->rto_count to per-NUMA-node counters

In reply to Pan Deng
Quoted 2 lines · Pan Deng

As a complementary, this patch splits
rto_count into per-numa-node counters to reduce the contention.

Right... so Tim, didn't we have similar patches for task_group::load_avg or something like that? Whatever did happen there? Can we share common infra?

Also since Tim is sitting on this LLC infrastructure, can you compare per-node and per-llc for this stuff? Somehow I'm thinking that a 2 socket 480 CPU system only has like 2 nodes and while splitting this will help some, that might not be excellent.

Please test on both Intel and AMD systems, since AMD has more of these LLC things on.

maintainer
#18 lore raw

Re: [PATCH v2 4/4] sched/rt: Split cpupri_vec->cpumask to per NUMA node to reduce contention

In reply to Pan Deng
Quoted 2 lines · Pan Deng

This change splits cpupri_vec->cpumask into per-NUMA-node data to mitigate false sharing.

So I really do think we need something here. We're running into the whole cpumask contention thing on a semi regular basis.

But somehow I doubt this is it.

I would suggest building a radix tree like structure based on ACPIID -- which is inherently suitable for this given that is exactly how CPUID-0b/1f are specified.

This of course makes it very much x86 specific, but perhaps other architectures can provide similarly structured id spaces suitable for this.

If you make it so that it reduces to a single large level (equivalent to the normal bitmaps) when no intermediate masks are specific, it should work for all, and then architectures can opt-in by providing a suitable id space and masks.

maintainer
#46 lore raw
In reply to Peter Zijlstra
Quoted 16 lines · Peter Zijlstra
Quoted 5 lines · Pan Deng

When running multi-instance FFmpeg workload in cloud environment, cache line contention is severe during the access to root_domain data structures, which significantly degrades performance.

The SUT is a 2-socket machine with 240 physical cores and 480 logical

What's a SUT?

Quoted 3 lines

CPUs. 60 FFmpeg instances are launched, each pinned to 4 physical cores (8 logical CPUs) for transcoding tasks. Sub-threads use RT priority 99 with FIFO scheduling. FPS(frame per second) is used as score.

So I think we can do some of this, but that workload is hilariously poorly configured.

Quoted 8 lines

You're pinning things but not partitioning, why? If you would have created 60 partitions, one for each FFmpeg thingy, then you wouldn't have needed any of this.

You're running at FIFO99 (IOW prio-0) and then claiming prio-0 is used more heavily than others... will d0h. What priority assignment scheme led to this? Is there a sensible reason these must be 99?

Also, you failed the most basic of tasks, Cc all the relevant people. I would've hoped at least some of the 'reviewer' you had would've told you about that.

Notably, Steve is the one that often looks after this RT stuff.

#14 lore raw

Re: [PATCH v2 3/4] sched/rt: Split root_domain->rto_count to per-NUMA-node counters

In reply to Peter Zijlstra
Quoted 7 lines · Peter Zijlstra
Quoted 2 lines · Pan Deng

As a complementary, this patch splits
rto_count into per-numa-node counters to reduce the contention.

Right... so Tim, didn't we have similar patches for task_group::load_avg or something like that? Whatever did happen there? Can we share common infra?

We did talk about introducing per NUMA counter for load_avg. We went with limiting the update rate of load_avg to not more than once per msec in commit 1528c661c24b4 to control the cache bounce.

Quoted 5 lines

Also since Tim is sitting on this LLC infrastructure, can you compare per-node and per-llc for this stuff? Somehow I'm thinking that a 2 socket 480 CPU system only has like 2 nodes and while splitting this will help some, that might not be excellent.

You mean enhancing the per NUMA counter to per LLC? I think that makes sense to reduce the LLC cache bounce if there are multiple LLCs per NUMA node.

Tim

Quoted 5 lines

Please test on both Intel and AMD systems, since AMD has more of these LLC things on.

#19 lore raw

Re: [PATCH v2 4/4] sched/rt: Split cpupri_vec->cpumask to per NUMA node to reduce contention

In reply to Peter Zijlstra
Quoted 5 lines · Peter Zijlstra
Quoted 2 lines · Pan Deng

This change splits cpupri_vec->cpumask into per-NUMA-node data to mitigate false sharing.

Quoted 9 lines

So I really do think we need something here. We're running into the whole cpumask contention thing on a semi regular basis.

But somehow I doubt this is it.

I would suggest building a radix tree like structure based on ACPIID -- which is inherently suitable for this given that is exactly how CPUID-0b/1f are specified.

Are you thinking about replacing cpumask in cpupri_vec with something like xarray? And a question on using ACPIID for the CPU as index instead of CPUID. Is it because you want to even out access in the tree?

Tim

Quoted 8 lines

This of course makes it very much x86 specific, but perhaps other architectures can provide similarly structured id spaces suitable for this.

If you make it so that it reduces to a single large level (equivalent to the normal bitmaps) when no intermediate masks are specific, it should work for all, and then architectures can opt-in by providing a suitable id space and masks.

author
#3 lore raw

RE: [PATCH v2 1/4] sched/rt: Optimize cpupri_vec layout to mitigate cache line contention

In reply to Peter Zijlstra
Quoted 63 lines · Pan Deng
Quoted 1 line

When running a multi-instance FFmpeg workload on an HCC system,

significant

Quoted 16 lines

cache line contention is observed around cpupri_vec->count and mask in struct root_domain.

The SUT is a 2-socket machine with 240 physical cores and 480 logical CPUs. 60 FFmpeg instances are launched, each pinned to 4 physical cores (8 logical CPUs) for transcoding tasks. Sub-threads use RT priority 99 with FIFO scheduling. FPS is used as score.

perf c2c tool reveals:
root_domain cache line 3:
- cpupri->pri_to_cpu[0].count (offset 0x38) is heavily loaded/stored and contends with other fields, since counts[0] is more frequently updated than others along with a rt task enqueues an empty runq or dequeues from a non-overloaded runq.
- cycles per load: ~10K to 59K

Quoted 7 lines

cpupri's last cache line:
- cpupri_vec->count and mask contends. The transcoding threads use rt pri 99, so that the contention occurs in the end.
- cycles per load: ~1.5K to 10.5K

This change mitigates cpupri_vec->count, mask related contentions by separating each count and mask into different cache lines.

Right.

Quoted 2 lines

Note: The side effect of this change is that struct cpupri size is increased from 26 cache lines to 203 cache lines.

That is pretty horrible, but probably unavoidable.

Quoted 5 lines

An alternative implementation of this patch could be separating counts and masks into 2 vectors in cpupri_vec (counts[] and masks[]), and add two paddings:
1. Between counts[0] and counts[1], since counts[0] is more frequently updated than others.

That is completely workload specific; it is a direct consequence of your (probably busted) priority assignment scheme.

Quoted 6 lines

2. Between the two vectors, since counts[] is read-write access while masks[] is read access when it stores pointers.

The alternative introduces the complexity of 31+/21- LoC changes, it achieves almost the same performance, at the same time, struct cpupri size is reduced from 26 cache lines to 21 cache lines.

That is not an alternative, since it very specifically only deals with fifo-99 contention.

Quoted 10 lines
---
 kernel/sched/cpupri.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/sched/cpupri.h +0 -0
index d6cba0020064..245b0fa626be 100644
@@ -9,7 +9,7 @@
 
Quoted 8 lines

kernel/sched/cpupri.h line 13

Quoted 5 lines
kernel/sched/cpupri.h +1 -1
 struct cpupri_vec {
 	atomic_t		count;
-	cpumask_var_t		mask;
+	cpumask_var_t		mask	____cacheline_aligned;
 };

At the very least this needs a comment, explaining the what and how of it.

Hi Peter,

Thank you very much for helping look at this patch series. Before digging into the details, please let me briefly describe the structure of this patch set.
Each patch builds incrementally on the previous ones, with patch 1 improving performance by 11%, patch 1+2 improving by 12%, patch 1+2+3 improving by 13%, and patch 1+2+3+4 by 16%.
Since patch 1 gives the most benefit and is simple enough, we are planning to address the first issue in patch 1 and try to push this patch first, then address your comments in remained patches. We'll investigate a more generic method to solve the global contention issue as you proposed in patch 3 and patch 4, and we are planning to do that on multi-LLC system as well(Intel and AMD).
Regarding this patch, yes, using cacheline aligned could increase potential memory usage.
After internal discussion, we are thinking of an alternative method to mitigate the waste of memory usage, that is, using kmalloc() to allocate count in a different memory space rather than placing the count and cpumask together in this structure. The rationale is that, writing to address pointed by the counter and reading the address from cpumask is isolated in different memory space which could reduce the ratio of cache false sharing, besides, kmalloc() based on slub/slab could place the objects in different cache lines to reduce the cache contention. The drawback of dynamic allocation counter is that, we have to maintain the life cycle of the counters.
Could you please advise if sticking with current cache_align attribute method or using kmalloc() is preferred?

maintainer
#20 lore raw

Re: [PATCH v2 4/4] sched/rt: Split cpupri_vec->cpumask to per NUMA node to reduce contention

In reply to Tim Chen
Quoted 11 lines · Tim Chen
Quoted 10 lines · Peter Zijlstra
Quoted 2 lines · Pan Deng

This change splits cpupri_vec->cpumask into per-NUMA-node data to mitigate false sharing.

So I really do think we need something here. We're running into the whole cpumask contention thing on a semi regular basis.

But somehow I doubt this is it.

Quoted 8 lines
Quoted 4 lines

I would suggest building a radix tree like structure based on ACPIID -- which is inherently suitable for this given that is exactly how CPUID-0b/1f are specified.

Are you thinking about replacing cpumask in cpupri_vec with something like xarray? And a question on using ACPIID for the CPU as index instead of CPUID. Is it because you want to even out access in the tree?

Sorry, s/ACPI/APIC/, I keep cursing the sadist that put those two acronyms together.

No, because I want it sorted by topology. Per virtue of CPUID-b/1f the APIC-ID is in topology order.

Perhaps a little something like this. It will obviously only build on x86, and then only boot for those that have <=64 CPUs in their DIE domain.

This needs ARCH_HAS_SBM and a cpumask based fallback implementation of sbm at the very least.

Now, I was hoping AMD EPYC would have their CCD things as a topology level, but going by the MADT/CPUID dump I got from Boris, this is not the case. So we need to manually insert that level and hope the APIC-ID range is nicely setup for that, or they need to do worse things still.

I think that for things like DMR DIE DTRT, but I've not yet seem one upclose :/

Also, I really wish all the SNC capable chips would have the SNC domains enumerated, even if SNC is not in use. This x86 topology enumeration stuff is such a shit show :-(

Anyway, random hackery below, it basically does a 2 level structure where the leaf is a whole cacheline (double check the kzalloc_obj() stuff respects alignment) and we make sure the CPUs for that leaf are actually from the same cache domain. At least, that's the theory, see above ranting on the glories of topology enumeration.

It boots in qemu with --cpus 16,sockets=2,dies=2 and appears to 'work'. YMMV

This code is very much a PoC, treat it as such.

---

arch/x86/include/asm/apic.h +1 -0
index 9cd493d467d4..24012a91ac1e 100644
@@ -54,6 +54,7 @@ static inline void x86_32_probe_apic(void) { }
 #endif
 
 extern u32 cpuid_to_apicid[];
+extern u32 apicid_to_cpuid[];
 
 #define CPU_ACPIID_INVALID	U32_MAX
 
arch/x86/include/asm/sbm.h new file +12 -0
new file mode 100644
index 000000000000..9a4d283347d1
@@ -0,0 +1,12 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#include <asm/apic.h>
+
+static __always_inline u32 arch_sbm_cpu_to_idx(unsigned int cpu)
+{
+	return cpuid_to_apicid[cpu];
+}
+
+static __always_inline u32 arch_sbm_idx_to_cpu(unsigned int idx)
+{
+	return apicid_to_cpuid[idx];
+}
arch/x86/kernel/cpu/topology.c +21 -1
index eafcb1fc185a..6f3d18288600 100644
@@ -48,6 +48,12 @@ DECLARE_BITMAP(phys_cpu_present_map, MAX_LOCAL_APIC) __read_mostly;
 
 /* Used for CPU number allocation and parallel CPU bringup */
 u32 cpuid_to_apicid[] __ro_after_init = { [0 ... NR_CPUS - 1] = BAD_APICID, };
+u32 apicid_to_cpuid[MAX_LOCAL_APIC] = { 0 };
+
+u32 arch_sbm_leafs	__ro_after_init;
+u32 arch_sbm_shift	__ro_after_init;
+u32 arch_sbm_mask	__ro_after_init;
+u32 arch_sbm_bits	__ro_after_init;
 
 /* Bitmaps to mark registered APICs at each topology domain */
 static struct { DECLARE_BITMAP(map, MAX_LOCAL_APIC); } apic_maps[TOPO_MAX_DOMAIN] __ro_after_init;
@@ -234,6 +240,7 @@ static __init void topo_register_apic(u32 apic_id, u32 acpi_id, bool present)
 			cpu = topo_get_cpunr(apic_id);
 
 		cpuid_to_apicid[cpu] = apic_id;
+		apicid_to_cpuid[apic_id] = cpu;
 		topo_set_cpuids(cpu, apic_id, acpi_id);
 	} else {
 		topo_info.nr_disabled_cpus++;
@@ -537,7 +544,9 @@ void __init topology_init_possible_cpus(void)
 					      MAX_LOCAL_APIC, apicid);
 		if (apicid >= MAX_LOCAL_APIC)
 			break;
-		cpuid_to_apicid[topo_info.nr_assigned_cpus++] = apicid;
+		cpu = topo_info.nr_assigned_cpus++;
+		cpuid_to_apicid[cpu] = apicid;
+		apicid_to_cpuid[apicid] = cpu;
 	}
 
 	for (cpu = 0; cpu < allowed; cpu++) {
@@ -551,6 +560,17 @@ void __init topology_init_possible_cpus(void)
 		cpu_mark_primary_thread(cpu, apicid);
 		set_cpu_present(cpu, test_bit(apicid, phys_cpu_present_map));
 	}
+
+	apicid = 0;
+	for_each_possible_cpu(cpu)
+		apicid = max(apicid, cpuid_to_apicid[cpu]);
+
+	arch_sbm_shift = x86_topo_system.dom_shifts[TOPO_DIE_DOMAIN] - 1;
+	arch_sbm_leafs = 1 + (apicid >> arch_sbm_shift);
+	arch_sbm_mask = (1 << arch_sbm_shift) - 1;
+	arch_sbm_bits = arch_sbm_shift;
+
+	pr_info("SBM: shift(%d) leafs(%d) APIC(%x)\n", arch_sbm_shift, arch_sbm_leafs, apicid);
 }
 
 /*
include/linux/sbm.h new file +83 -0

83 lines not on this page · raw message

kernel/sched/fair.c +14 -35

117 lines not on this page · raw message

lib/Makefile +1 -1
index 1b9ee167517f..8d1f6b5327d5 100644
@@ -40,7 +40,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \
 	 is_single_threaded.o plist.o decompress.o kobject_uevent.o \
 	 earlycpio.o seq_buf.o siphash.o dec_and_lock.o \
 	 nmi_backtrace.o win_minmax.o memcat_p.o \
-	 buildid.o objpool.o iomem_copy.o sys_info.o
+	 buildid.o objpool.o iomem_copy.o sys_info.o sbm.o
 
 lib-$(CONFIG_UNION_FIND) += union_find.o
 lib-$(CONFIG_PRINTK) += dump_stack.o
lib/sbm.c new file +57 -0

57 lines not on this page · raw message

maintainer
#4 lore raw

Re: [PATCH v2 1/4] sched/rt: Optimize cpupri_vec layout to mitigate cache line contention

In reply to Deng, Pan
Quoted 6 lines · Pan

Regarding this patch, yes, using cacheline aligned could increase potential memory usage.
After internal discussion, we are thinking of an alternative method to mitigate the waste of memory usage, that is, using kmalloc() to allocate count in a different memory space rather than placing the count and cpumask together in this structure. The rationale is that, writing to

Quoted 8 lines

address pointed by the counter and reading the address from cpumask is isolated in different memory space which could reduce the ratio of cache false sharing, besides, kmalloc() based on slub/slab could place the objects in different cache lines to reduce the cache contention. The drawback of dynamic allocation counter is that, we have to maintain the life cycle of the counters.
Could you please advise if sticking with current cache_align attribute method or using kmalloc() is preferred?

Well, you'd have to allocate a full cacheline anyway. If you allocate N 4 byte (counter) objects, there's a fair chance they end up in the same cacheline (its a SLAB after all) and then you're back to having a ton of false sharing.

Anyway, for you specific workload, why isn't partitioning a viable solution? It would not need any kernel modifications and would get rid of the contention entirely.

maintainer
#15 lore raw

Re: [PATCH v2 3/4] sched/rt: Split root_domain->rto_count to per-NUMA-node counters

In reply to Tim Chen
Quoted 14 lines · Tim Chen
Quoted 7 lines · Peter Zijlstra
Quoted 2 lines · Pan Deng

As a complementary, this patch splits
rto_count into per-numa-node counters to reduce the contention.

Right... so Tim, didn't we have similar patches for task_group::load_avg or something like that? Whatever did happen there? Can we share common infra?

We did talk about introducing per NUMA counter for load_avg. We went with limiting the update rate of load_avg to not more than once per msec in commit 1528c661c24b4 to control the cache bounce.

Quoted 1 line
Quoted 8 lines
Quoted 4 lines

Also since Tim is sitting on this LLC infrastructure, can you compare per-node and per-llc for this stuff? Somehow I'm thinking that a 2 socket 480 CPU system only has like 2 nodes and while splitting this will help some, that might not be excellent.

You mean enhancing the per NUMA counter to per LLC? I think that makes sense to reduce the LLC cache bounce if there are multiple LLCs per NUMA node.

Does that system have multiple LLCs? Realistically, it would probably improve things if we could split these giant stupid LLCs along the same lines SNC does.

I still have the below terrible hack that I've been using to diagnose and test all these multi-llc patches/regressions etc. Funnily enough its been good enough to actually show some of the issues.

---
Subject: x86/topology: Add paramter to split LLC
From: Peter Zijlstra <[email protected]>
Date: Thu Feb 19 12:11:16 CET 2026

Add a (debug) option to virtually split the LLC, no CAT involved, just fake topology. Used to test code that depends (either in behaviour or directly) on there being multiple LLC domains in a node.

---
 Documentation/admin-guide/kernel-parameters.txt |   12 ++++++++++++
 arch/x86/include/asm/processor.h                |    5 +++++
 arch/x86/kernel/smpboot.c                       |   20 ++++++++++++++++++++
 3 files changed, 37 insertions(+)
Documentation/admin-guide/kernel-parameters.txt +12 -0
@@ -7241,6 +7241,18 @@ Kernel parameters
 			Not specifying this option is equivalent to
 			spec_store_bypass_disable=auto.
 
+	split_llc=
+			[X86,EARLY] Split the LLC N-ways
+
+			When set, the LLC is split this many ways by matching
+			'core_id % n'. This is setup before SMP bringup and
+			used during SMP bringup before it knows the full
+			topology. If your core count doesn't nicely divide by
+			the number given, you get to keep the pieces.
+
+			This is mostly a debug feature to emulate multiple LLCs
+			on hardware that only have a single LLC.
+
 	split_lock_detect=
 			[X86] Enable split lock detection or bus lock detection
 
arch/x86/include/asm/processor.h +5 -0
@@ -699,6 +699,11 @@ static inline u32 per_cpu_l2c_id(unsigne
 	return per_cpu(cpu_info.topo.l2c_id, cpu);
 }
 
+static inline u32 per_cpu_core_id(unsigned int cpu)
+{
+	return per_cpu(cpu_info.topo.core_id, cpu);
+}
+
 #ifdef CONFIG_CPU_SUP_AMD
 /*
  * Issue a DIV 0/1 insn to clear any division data from previous DIV
arch/x86/kernel/smpboot.c +20 -0
@@ -424,6 +424,21 @@ static const struct x86_cpu_id intel_cod
 	{}
 };
 
+/*
+ * Allows splitting the LLC by matching 'core_id % split_llc'.
+ *
+ * This is mostly a debug hack to emulate systems with multiple LLCs per node
+ * on systems that do not naturally have this.
+ */
+static unsigned int split_llc = 0;
+
+static int __init split_llc_setup(char *str)
+{
+	get_option(&str, &split_llc);
+	return 0;
+}
+early_param("split_llc", split_llc_setup);
+
 static bool match_llc(struct cpuinfo_x86 *c, struct cpuinfo_x86 *o)
 {
 	const struct x86_cpu_id *id = x86_match_cpu(intel_cod_cpu);
@@ -438,6 +453,11 @@ static bool match_llc(struct cpuinfo_x86
 	if (per_cpu_llc_id(cpu1) != per_cpu_llc_id(cpu2))
 		return false;
 
+	if (split_llc &&
+	    (per_cpu_core_id(cpu1) % split_llc) !=
+	    (per_cpu_core_id(cpu2) % split_llc))
+		return false;
+
 	/*
 	 * Allow the SNC topology without warning. Return of false
 	 * means 'c' does not share the LLC of 'o'. This will be
#16 lore raw

Re: [PATCH v2 3/4] sched/rt: Split root_domain->rto_count to per-NUMA-node counters

Quoted 20 lines · Peter Zijlstra
Quoted 19 lines · Tim Chen
Quoted 7 lines · Peter Zijlstra
Quoted 2 lines · Pan Deng

As a complementary, this patch splits
rto_count into per-numa-node counters to reduce the contention.

Right... so Tim, didn't we have similar patches for task_group::load_avg or something like that? Whatever did happen there? Can we share common infra?

We did talk about introducing per NUMA counter for load_avg. We went with limiting the update rate of load_avg to not more than once per msec in commit 1528c661c24b4 to control the cache bounce.

Quoted 5 lines

Also since Tim is sitting on this LLC infrastructure, can you compare per-node and per-llc for this stuff? Somehow I'm thinking that a 2 socket 480 CPU system only has like 2 nodes and while splitting this will help some, that might not be excellent.

Quoted 7 lines
Quoted 3 lines

You mean enhancing the per NUMA counter to per LLC? I think that makes sense to reduce the LLC cache bounce if there are multiple LLCs per NUMA node.

Does that system have multiple LLCs? Realistically, it would probably improve things if we could split these giant stupid LLCs along the same lines SNC does.

The system that Pan tested does not have multiple LLCs per node. But future Intel systems and current AMD systems do. So it make sense to start thinking about having a per LLC count infrastructure.

We could create a per LLC counter library, kind of like the percpu counter
we already have. We can leverage compact LLC id assignment in the cache aware scheduling patches to allocate arrays indexed by LLC id. The caveat is if such LLC
count is used during early boot before LLCs are enumerated in the topology code, we may need to put do accounting in a global count, till the per LLC count gets enumerated
and we know the right size of the LLC array. And we'll also need to
check if new LLC come online or offline and handle things accordingly.

That sounds reasonable?

Tim

Quoted 94 lines

I still have the below terrible hack that I've been using to diagnose and test all these multi-llc patches/regressions etc. Funnily enough its been good enough to actually show some of the issues.

---
Subject: x86/topology: Add paramter to split LLC
From: Peter Zijlstra <[email protected]>
Date: Thu Feb 19 12:11:16 CET 2026

Add a (debug) option to virtually split the LLC, no CAT involved, just fake topology. Used to test code that depends (either in behaviour or directly) on there being multiple LLC domains in a node.

---
 Documentation/admin-guide/kernel-parameters.txt |   12 ++++++++++++
 arch/x86/include/asm/processor.h                |    5 +++++
 arch/x86/kernel/smpboot.c                       |   20 ++++++++++++++++++++
 3 files changed, 37 insertions(+)
Documentation/admin-guide/kernel-parameters.txt +12 -0
@@ -7241,6 +7241,18 @@ Kernel parameters
 			Not specifying this option is equivalent to
 			spec_store_bypass_disable=auto.
 
+	split_llc=
+			[X86,EARLY] Split the LLC N-ways
+
+			When set, the LLC is split this many ways by matching
+			'core_id % n'. This is setup before SMP bringup and
+			used during SMP bringup before it knows the full
+			topology. If your core count doesn't nicely divide by
+			the number given, you get to keep the pieces.
+
+			This is mostly a debug feature to emulate multiple LLCs
+			on hardware that only have a single LLC.
+
 	split_lock_detect=
 			[X86] Enable split lock detection or bus lock detection
 
arch/x86/include/asm/processor.h +5 -0
@@ -699,6 +699,11 @@ static inline u32 per_cpu_l2c_id(unsigne
 	return per_cpu(cpu_info.topo.l2c_id, cpu);
 }
 
+static inline u32 per_cpu_core_id(unsigned int cpu)
+{
+	return per_cpu(cpu_info.topo.core_id, cpu);
+}
+
 #ifdef CONFIG_CPU_SUP_AMD
 /*
  * Issue a DIV 0/1 insn to clear any division data from previous DIV
arch/x86/kernel/smpboot.c +20 -0
@@ -424,6 +424,21 @@ static const struct x86_cpu_id intel_cod
 	{}
 };
 
+/*
+ * Allows splitting the LLC by matching 'core_id % split_llc'.
+ *
+ * This is mostly a debug hack to emulate systems with multiple LLCs per node
+ * on systems that do not naturally have this.
+ */
+static unsigned int split_llc = 0;
+
+static int __init split_llc_setup(char *str)
+{
+	get_option(&str, &split_llc);
+	return 0;
+}
+early_param("split_llc", split_llc_setup);
+
 static bool match_llc(struct cpuinfo_x86 *c, struct cpuinfo_x86 *o)
 {
 	const struct x86_cpu_id *id = x86_match_cpu(intel_cod_cpu);
@@ -438,6 +453,11 @@ static bool match_llc(struct cpuinfo_x86
 	if (per_cpu_llc_id(cpu1) != per_cpu_llc_id(cpu2))
 		return false;
 
+	if (split_llc &&
+	    (per_cpu_core_id(cpu1) % split_llc) !=
+	    (per_cpu_core_id(cpu2) % split_llc))
+		return false;
+
 	/*
 	 * Allow the SNC topology without warning. Return of false
 	 * means 'c' does not share the LLC of 'o'. This will be
author
#5 lore raw

RE: [PATCH v2 1/4] sched/rt: Optimize cpupri_vec layout to mitigate cache line contention

In reply to Peter Zijlstra
Quoted 18 lines · Pan
Quoted 15 lines

Regarding this patch, yes, using cacheline aligned could increase potential memory usage.
After internal discussion, we are thinking of an alternative method to mitigate the waste of memory usage, that is, using kmalloc() to allocate count in a different memory space rather than placing the count and cpumask together in this structure. The rationale is that, writing to address pointed by the counter and reading the address from cpumask is isolated in different memory space which could reduce the ratio of cache false sharing, besides, kmalloc() based on slub/slab could place the objects in different cache lines to reduce the cache contention. The drawback of dynamic allocation counter is that, we have to maintain the life cycle of the counters.
Could you please advise if sticking with current cache_align attribute method or using kmalloc() is preferred?

Quoted 8 lines

Well, you'd have to allocate a full cacheline anyway. If you allocate N 4 byte (counter) objects, there's a fair chance they end up in the same cacheline (its a SLAB after all) and then you're back to having a ton of false sharing.

Anyway, for you specific workload, why isn't partitioning a viable solution? It would not need any kernel modifications and would get rid of the contention entirely.

Thank you very much for pointing this out.

We understand cpuset partitioning would eliminate the contention. However, in managed container platforms (e.g., Kubernetes), users can obtain RT capabilities for their workloads via CAP_SYS_NICE, but they don't have host-level privileges to create cpuset partitions.

Besides the cache line align approach, regarding both the contention and memory overhead, would it be possible to consider the alternative approach as follow:

1. Use {counts[], masks[]} instead of vec[{count, mask}]

2. Separate counts[0] (CPUPRI_NORMAL), who experiences both heavy write and read traffic.
Writes: RT task lifecycle operations (enqueue on empty runqueue, dequeue from non-overloaded runqueue) frequently update the normal priority count.
Reads: RT tasks searching for available CPUs scan from low to high priority, with counts[0] being checked at the start of every search iteration.
So that even if workloads used lower RT priorities (e.g., RT pri 49 instead of 99), counts[0] contention would still be heavy, not specific to the pri-99 workload configuration.

3. Separate masks from counts to ensure no contention between them.

With the change struct cpupri size can be reduced from 26 cache lines to 21 cache lines, which saves more memory in cpuset partitioning scenarios.

code change looks like this:
---

kernel/sched/cpupri.c +39 -23
index 42c40cfdf836..1e333e6edb1e 100644
@@ -64,16 +64,38 @@ static int convert_prio(int prio)
 	return cpupri;
 }
 
+/*
+ * Get pointer to count for given priority index.
+ *
+ * Skip padding after counts[0] for idx > 0 to access the correct location.
+ */
+static inline atomic_t *cpupri_count(struct cpupri *cp, int idx)
+{
+	if (idx > 0)
+		idx += CPUPRI_COUNT0_PADDING;
+
+	return &cp->pri_to_cpu.counts[idx];
+}
+
+/*
+ * Get pointer to mask for given priority index.
+ */
+static inline cpumask_var_t cpupri_mask(struct cpupri *cp, int idx)
+{
+	return cp->pri_to_cpu.masks[idx];
+}
+
 static inline int __cpupri_find(struct cpupri *cp, struct task_struct *p,
 				struct cpumask *lowest_mask, int idx)
 {
-	struct cpupri_vec *vec  = &cp->pri_to_cpu[idx];
+	cpumask_var_t cpu_mask = cpupri_mask(cp, idx);
+
 	int skip = 0;
 
-	if (!atomic_read(&(vec)->count))
+	if (!atomic_read(cpupri_count(cp, idx)))
 		skip = 1;
 	/*
-	 * When looking at the vector, we need to read the counter,
+	 * When looking at the vector, we need to read the count,
 	 * do a memory barrier, then read the mask.
 	 *
 	 * Note: This is still all racy, but we can deal with it.
@@ -96,18 +118,18 @@ static inline int __cpupri_find(struct cpupri *cp, struct task_struct *p,
 	if (skip)
 		return 0;
 
-	if (cpumask_any_and(&p->cpus_mask, vec->mask) >= nr_cpu_ids)
+	if (cpumask_any_and(&p->cpus_mask, cpu_mask) >= nr_cpu_ids)
 		return 0;
 
 	if (lowest_mask) {
-		cpumask_and(lowest_mask, &p->cpus_mask, vec->mask);
+		cpumask_and(lowest_mask, &p->cpus_mask, cpu_mask);
 		cpumask_and(lowest_mask, lowest_mask, cpu_active_mask);
 
 		/*
 		 * We have to ensure that we have at least one bit
 		 * still set in the array, since the map could have
 		 * been concurrently emptied between the first and
-		 * second reads of vec->mask.  If we hit this
+		 * second reads of cpu_mask.  If we hit this
 		 * condition, simply act as though we never hit this
 		 * priority level and continue on.
 		 */
@@ -227,23 +249,19 @@ void cpupri_set(struct cpupri *cp, int cpu, int newpri)
 	 * cpu being missed by the priority loop in cpupri_find.
 	 */
 	if (likely(newpri != CPUPRI_INVALID)) {
-		struct cpupri_vec *vec = &cp->pri_to_cpu[newpri];
-
-		cpumask_set_cpu(cpu, vec->mask);
+		cpumask_set_cpu(cpu, cpupri_mask(cp, newpri));
 		/*
 		 * When adding a new vector, we update the mask first,
 		 * do a write memory barrier, and then update the count, to
 		 * make sure the vector is visible when count is set.
 		 */
 		smp_mb__before_atomic();
-		atomic_inc(&(vec)->count);
+		atomic_inc(cpupri_count(cp, newpri));
 		do_mb = 1;
 	}
 	if (likely(oldpri != CPUPRI_INVALID)) {
-		struct cpupri_vec *vec  = &cp->pri_to_cpu[oldpri];
-
 		/*
-		 * Because the order of modification of the vec->count
+		 * Because the order of modification of the cpu count
 		 * is important, we must make sure that the update
 		 * of the new prio is seen before we decrement the
 		 * old prio. This makes sure that the loop sees
@@ -252,18 +270,18 @@ void cpupri_set(struct cpupri *cp, int cpu, int newpri)
 		 * priority, as that will trigger an rt pull anyway.
 		 *
 		 * We only need to do a memory barrier if we updated
-		 * the new priority vec.
+		 * cpu count or mask of the new priority.
 		 */
 		if (do_mb)
 			smp_mb__after_atomic();
 
 		/*
-		 * When removing from the vector, we decrement the counter first
+		 * When removing from the vector, we decrement the count first
 		 * do a memory barrier and then clear the mask.
 		 */
-		atomic_dec(&(vec)->count);
+		atomic_dec(cpupri_count(cp, oldpri));
 		smp_mb__after_atomic();
-		cpumask_clear_cpu(cpu, vec->mask);
+		cpumask_clear_cpu(cpu, cpupri_mask(cp, oldpri));
 	}
 
 	*currpri = newpri;
@@ -280,10 +298,8 @@ int cpupri_init(struct cpupri *cp)
 	int i;
 
 	for (i = 0; i < CPUPRI_NR_PRIORITIES; i++) {
-		struct cpupri_vec *vec = &cp->pri_to_cpu[i];
-
-		atomic_set(&vec->count, 0);
-		if (!zalloc_cpumask_var(&vec->mask, GFP_KERNEL))
+		atomic_set(cpupri_count(cp, i), 0);
+		if (!zalloc_cpumask_var(&cp->pri_to_cpu.masks[i], GFP_KERNEL))
 			goto cleanup;
 	}
 
@@ -298,7 +314,7 @@ int cpupri_init(struct cpupri *cp)
 
 cleanup:
 	for (i--; i >= 0; i--)
-		free_cpumask_var(cp->pri_to_cpu[i].mask);
+		free_cpumask_var(cpupri_mask(cp, i));
 	return -ENOMEM;
 }
 
@@ -312,5 +328,5 @@ void cpupri_cleanup(struct cpupri *cp)
 
 	kfree(cp->cpu_to_pri);
 	for (i = 0; i < CPUPRI_NR_PRIORITIES; i++)
-		free_cpumask_var(cp->pri_to_cpu[i].mask);
+		free_cpumask_var(cpupri_mask(cp, i));
 }
kernel/sched/cpupri.h +65 -3

83 lines not on this page · raw message

kernel/sched/sched.h +1 -1
index 475bb5998295..2263237cdeb0 100644
@@ -1014,7 +1014,7 @@ struct root_domain {
 	 * one runnable RT task.
 	 */
 	cpumask_var_t		rto_mask;
-	struct cpupri		cpupri;
+	struct cpupri		cpupri	____cacheline_aligned;
 
 	/*
 	 * NULL-terminated list of performance domains intersecting with the
#21 lore raw

Re: [PATCH v2 4/4] sched/rt: Split cpupri_vec->cpumask to per NUMA node to reduce contention

In reply to Peter Zijlstra
Quoted 10 lines · Peter Zijlstra
Quoted 9 lines · Tim Chen
Quoted 8 lines · Peter Zijlstra
Quoted 2 lines · Pan Deng

This change splits cpupri_vec->cpumask into per-NUMA-node data to mitigate false sharing.

So I really do think we need something here. We're running into the whole cpumask contention thing on a semi regular basis.

[ ... ]

Quoted 4 lines
lib/sbm.c new file +4 -0
+
+unsigned int sbm_find_next_bit(struct sbm *sbm, int start)
+{
+	struct sbm_leaf *leaf = (void *)sbm;

lib/sbm.c line 49

Quoted 10 lines
lib/sbm.c new file +10 -0
+	struct sbm_root *root = (void *)sbm;
+	int nr = start >> arch_sbm_shift;
+	int bit = start & arch_sbm_mask;
+	unsigned long tmp, mask = (~0UL) << bit;
+	if (sbm->type == st_root) {
+		for (; nr < arch_sbm_leafs; nr++, mask = ~0UL) {
+			leaf = root->leafs[nr];
+			tmp = leaf->bitmap & mask;
+			if (!tmp)
+				continue;

I suppose this should be

	if (tmp)
		break;
otherwise
[   40.071616] watchdog: BUG: soft lockup - CPU#0 stuck for 30s! [swapper/0:0]
[   40.071616] Modules linked in:
[   40.071616] CPU: 0 UID: 0 PID: 0 Comm: swapper/0 Not tainted 7.0.0-rc5-sbm-+ #16 PREEMPT(full)
[   40.071616] RIP: 0010:sbm_find_next_bit+0x2a/0xa0

lib/sbm.c line 57

Quoted 8 lines
lib/sbm.c new file +8 -0
+		}
+	} else {
+		tmp = leaf->bitmap & mask;
+	}
+	if (!tmp)
+		return -1;
+	return (nr << arch_sbm_shift) | __ffs(tmp);
+}

update of the test:
With above change, I did a simple hackbench test on a system with multiple LLCs within 1 node, so the benefit is significant(+12%~+30%) when system is under-loaded, while some regression when overloaded(-10%)(need to figure out)

thanks,
Chenyu

#22 lore raw

Re: [PATCH v2 4/4] sched/rt: Split cpupri_vec->cpumask to per NUMA node to reduce contention

Hello Chenyu,

Quoted 5 lines · Yu C

update of the test:
With above change, I did a simple hackbench test on a system with multiple LLCs within 1 node, so the benefit is significant(+12%~+30%) when system is under-loaded, while some regression when overloaded(-10%)(need to figure out)

Could it be because of how we are traversing the CPUs now for idle load balancing? Since we use the first set bit for ilb_cpu and also staring balancing from that very CPu, we might just stop after a successful balance on the ilb_cpu.

Would something like below on top of Peter's suggestion + your fix help?

(lightly tested; Has survived sched messaging on baremetal)

include/linux/sbm.h +37 -0
index 8beade6c0585..98c4c1866534 100644
@@ -76,8 +76,45 @@ static inline bool sbm_cpu_test(struct sbm *sbm, int cpu)
 	return __sbm_op(sbm, test_bit);
 }
 
+static __always_inline
+unsigned int sbm_find_next_bit_wrap(struct sbm *sbm, int start)
+{
+	int bit = sbm_find_next_bit(sbm, start);
+
+	if (bit >= 0 || start == 0)
+		return bit;
+
+	bit = sbm_find_next_bit(sbm, 0);
+	return bit < start ? bit : -1;
+}
+
+static __always_inline
+unsigned int __sbm_for_each_wrap(struct sbm *sbm, int start, int n)
+{
+	int bit;
+
+	/* If not wrapped around */
+	if (n > start) {
+		/* and have a bit, just return it. */
+		bit = sbm_find_next_bit(sbm, n);
+		if (bit >= 0)
+			return bit;
+
+		/* Otherwise, wrap around and ... */
+		n = 0;
+	}
+
+	/* Search the other part. */
+	bit = sbm_find_next_bit(sbm, n);
+	return bit < start ? bit : -1;
+}
+
 #define sbm_for_each_set_bit(sbm, idx) \
 	for (int idx = sbm_find_next_bit(sbm, 0); \
 	     idx >= 0; idx = sbm_find_next_bit(sbm, idx+1))
 
+#define sbm_for_each_set_bit_wrap(sbm, idx, start) \
+	for (int idx = sbm_find_next_bit_wrap(sbm, start); \
+	     idx >= 0; idx = __sbm_for_each_wrap(sbm, start, idx+1))
+
 #endif /* _LINUX_SBM_H */
kernel/sched/fair.c +3 -1
index a3a423c4706e..f485afb6286d 100644
@@ -12916,6 +12916,7 @@ static void _nohz_idle_balance(struct rq *this_rq, unsigned int flags)
 	int this_cpu = this_rq->cpu;
 	int balance_cpu;
 	struct rq *rq;
+	u32 start;
 
 	WARN_ON_ONCE((flags & NOHZ_KICK_MASK) == NOHZ_BALANCE_KICK);
 
@@ -12944,7 +12945,8 @@ static void _nohz_idle_balance(struct rq *this_rq, unsigned int flags)
 	 * Start with the next CPU after this_cpu so we will end with this_cpu and let a
 	 * chance for other idle cpu to pull load.
 	 */
-	sbm_for_each_set_bit(nohz.sbm, idx) {
+	start = arch_sbm_cpu_to_idx((this_cpu + 1) % nr_cpu_ids);
+	sbm_for_each_set_bit_wrap(nohz.sbm, idx, start) {
 		balance_cpu = arch_sbm_idx_to_cpu(idx);
 
 		if (!idle_cpu(balance_cpu))

---

This is pretty much giving me similar performance as tip for sched messaging runs under heavy load but your mileage may vary :-)

Signature · 2 lines
Thanks and Regards,
Prateek
#23 lore raw

Re: [PATCH v2 4/4] sched/rt: Split cpupri_vec->cpumask to per NUMA node to reduce contention

Hello Prateek,

Quoted 92 lines · K Prateek Nayak

Hello Chenyu,

Quoted 5 lines · Yu C

update of the test:
With above change, I did a simple hackbench test on a system with multiple LLCs within 1 node, so the benefit is significant(+12%~+30%) when system is under-loaded, while some regression when overloaded(-10%)(need to figure out)

Could it be because of how we are traversing the CPUs now for idle load balancing? Since we use the first set bit for ilb_cpu and also staring balancing from that very CPu, we might just stop after a successful balance on the ilb_cpu.

Would something like below on top of Peter's suggestion + your fix help?

(lightly tested; Has survived sched messaging on baremetal)

include/linux/sbm.h +37 -0
index 8beade6c0585..98c4c1866534 100644
@@ -76,8 +76,45 @@ static inline bool sbm_cpu_test(struct sbm *sbm, int cpu)
  	return __sbm_op(sbm, test_bit);
  }
 
+static __always_inline
+unsigned int sbm_find_next_bit_wrap(struct sbm *sbm, int start)
+{
+	int bit = sbm_find_next_bit(sbm, start);
+
+	if (bit >= 0 || start == 0)
+		return bit;
+
+	bit = sbm_find_next_bit(sbm, 0);
+	return bit < start ? bit : -1;
+}
+
+static __always_inline
+unsigned int __sbm_for_each_wrap(struct sbm *sbm, int start, int n)
+{
+	int bit;
+
+	/* If not wrapped around */
+	if (n > start) {
+		/* and have a bit, just return it. */
+		bit = sbm_find_next_bit(sbm, n);
+		if (bit >= 0)
+			return bit;
+
+		/* Otherwise, wrap around and ... */
+		n = 0;
+	}
+
+	/* Search the other part. */
+	bit = sbm_find_next_bit(sbm, n);
+	return bit < start ? bit : -1;
+}
+
  #define sbm_for_each_set_bit(sbm, idx) \
  	for (int idx = sbm_find_next_bit(sbm, 0); \
  	     idx >= 0; idx = sbm_find_next_bit(sbm, idx+1))
 
+#define sbm_for_each_set_bit_wrap(sbm, idx, start) \
+	for (int idx = sbm_find_next_bit_wrap(sbm, start); \
+	     idx >= 0; idx = __sbm_for_each_wrap(sbm, start, idx+1))
+
  #endif /* _LINUX_SBM_H */
kernel/sched/fair.c +3 -2
index a3a423c4706e..f485afb6286d 100644
@@ -12916,6 +12916,7 @@ static void _nohz_idle_balance(struct rq *this_rq, unsigned int flags)
  	int this_cpu = this_rq->cpu;
  	int balance_cpu;
  	struct rq *rq;
+	u32 start;
 
  	WARN_ON_ONCE((flags & NOHZ_KICK_MASK) == NOHZ_BALANCE_KICK);
 
@@ -12944,7 +12945,8 @@ static void _nohz_idle_balance(struct rq *this_rq, unsigned int flags)
  	 * Start with the next CPU after this_cpu so we will end with this_cpu and let a
  	 * chance for other idle cpu to pull load.
  	 */
-	sbm_for_each_set_bit(nohz.sbm, idx) {
+	start = arch_sbm_cpu_to_idx((this_cpu + 1) % nr_cpu_ids);
+	sbm_for_each_set_bit_wrap(nohz.sbm, idx, start) {
  		balance_cpu = arch_sbm_idx_to_cpu(idx);
 
  		if (!idle_cpu(balance_cpu))
---
Quoted 3 lines

This is pretty much giving me similar performance as tip for sched messaging runs under heavy load but your mileage may vary :-)

Thanks very much for providing this optimization. It should help more nohz idle CPUs-beyond just the currently selected ilb_cpu to assist in offloading work. When I applied this patch and reran the test, it appeared to introduce some regressions (underload and overload) compared to the baseline without Peter’s sbm applied.

One suspicion is that with sbm enabled(without your patch), more tasks are "aggregated" onto the first CPU(or maybe the front part) in nohz.sbm, because sbm_for_each_set_bit() always picks the first idle CPU to pull work. As we already know, hackbench on our platform strongly prefers being aggregated rather than being spread across different LLCs. So with the spreading fix, the hackbench might be put to different CPUs. Anyway, I'll run more rounds of testing to check whether this is consistent or merely due to run-to-run variance. And I'll try other workloads besides hackbench. Or do you have suggestion on what workload we can try, which is sensitive to nohz cpumask access(I chose hackbench because I found Shrikanth was using hackbench for nohz evaluation in commit 5d86d542f6)

thanks,
Chenyu

CPUs

#24 lore raw

Re: [PATCH v2 4/4] sched/rt: Split cpupri_vec->cpumask to per NUMA node to reduce contention

Hello Chenyu,

Thank you for testing the changes! Much appreciated.

Quoted 7 lines · Yu C

One suspicion is that with sbm enabled(without your patch), more tasks are "aggregated" onto the first CPU(or maybe the front part) in nohz.sbm, because sbm_for_each_set_bit() always picks the first idle CPU to pull work. As we already know, hackbench on our platform strongly prefers being aggregated rather than being spread across different LLCs. So with the spreading fix, the hackbench might be put to different CPUs.

Ack! But I cannot seem to come up with a theory on why it would be any worse than original.

P.S. what does your SBM log in the dmesg look like? On my 3rd Generation EPYC machine (2 x 64C/128T) it looks like:

CPU topo: SBM: shift(6) leafs(4) APIC(ff)

Now, I suppose I get 4 leaves because I have 128CPUs per socket (2 x u64 per socket) but it is not super how it is achieved from doing:

    arch_sbm_shift = x86_topo_system.dom_shifts[TOPO_DIE_DOMAIN] - 1;

that divides TOPO_DIE_DOMAIN into two but that should only be okay until 128CPUs per DIE.

It is still not super clear to me how the logic deals with more than 128CPUs in a DIE domain because that'll need more than the u64 but sbm_find_next_bit() simply does:

    tmp = leaf->bitmap & mask; /* All are u64 */

expecting just the u64 bitmap to represent all the CPUs in the leaf.

If we have, say 256 CPUs per DIE, we get shift(7) and arch_sbm_mask as 7f (127) which allows a leaf to more than 64 CPUs but we are using the "u64 bitmap" directly and not:

find_next_bit(bitmap, arch_sbm_mask)

Am I missing something here?

AMD got the 0x80000026 for defining TOPO_DIE_DOMAIN as soon as we crossed 256CPUs per socket in 4th Generation EPYC so it'll have per CCD (up to 2LLCs) smb leaves but if I'm not mistaken, some of the SPR systems still advertised one large TILE / DIE domain.

I'm curious if your test system exposed multiple DIE per PKG since 280 logical CPUs per socket based on the cover letter would still go beyond needing 64 bits if it is advertised as a single DIE.

Quoted 7 lines

Anyway, I'll run more
rounds of testing to check whether this is consistent or merely due to run-to-run variance. And I'll try other workloads besides hackbench. Or do you have suggestion on what workload we can try, which is sensitive to nohz cpumask access(I chose hackbench because I found Shrikanth was using hackbench for nohz evaluation in commit 5d86d542f6)

Most sensitive is schbench's tail latency when system is fully loaded (#workers = #CPUs) but that data point also has large run to run variation - I generally look for crazy jumps like the tail latency turning 5-8x consistently across multiple runs before actually concluding it is a regression.

hackbench (/ sched-messaging) should be good enough from a throughput standpoint.

Signature · 2 lines
Thanks and Regards,
Prateek
author
#6 lore raw

RE: [PATCH v2 1/4] sched/rt: Optimize cpupri_vec layout to mitigate cache line contention

In reply to Deng, Pan
Quoted 39 lines
kernel/sched/cpupri.h +27 -1
+	atomic_t		counts[CPUPRI_COUNT_ARRAY_SIZE];
+
+	/*
+	 * Padding to separate count and mask vectors.
+	 *
+	 * Prevents false sharing between:
+	 * - counts[] (read-write, hot path in cpupri_set)
+	 * - masks[] (read-mostly, accessed in cpupri_find)
+	 */
+	char			padding[CPUPRI_VEC_PADDING];
+
+	/*
+	 * CPU mask vector.
+	 *
+	 * Either stores:
+	 * - Pointers to dynamically allocated cpumasks (read-mostly after init)
+	 * - Inline cpumasks (if !CPUMASK_OFFSTACK)
+	 */
+	cpumask_var_t		masks[CPUPRI_NR_PRIORITIES];
 };
 
 struct cpupri {
-	struct cpupri_vec	pri_to_cpu[CPUPRI_NR_PRIORITIES];
+	/*
+	 * Priority-to-CPU mapping.
+	 *
+	 * Single cpupri_vec structure containing all counts and masks,
+	 * rather than 101 separate cpupri_vec elements. This reduces
+	 * memory overhead from ~26 to ~21 cachelines.
+	 */
+	struct cpupri_vec       pri_to_cpu;
 	int			*cpu_to_pri;
 };
kernel/sched/sched.h +0 -0
index 475bb5998295..2263237cdeb0 100644

kernel/sched/sched.h struct root_domain { · line 1020

Quoted 8 lines
kernel/sched/sched.h +1 -1
@@ -1014,7 +1014,7 @@ struct root_domain {
 	 * one runnable RT task.
 	 */
 	cpumask_var_t		rto_mask;
-	struct cpupri		cpupri;
+	struct cpupri		cpupri	____cacheline_aligned;
 
 	/*
 	 * NULL-terminated list of performance domains intersecting with the

Peter and Steven,

Here we consider two approaches:
The cache-line alignment approach is simple to implement but increases memory usage.
The alternative approach (separating counts and masks, with padding after counts[0]) reduces memory footprint at the cost of slightly higher complexity. What is your opinion? thanks a lot!

maintainer
#7 lore raw

Re: [PATCH v2 1/4] sched/rt: Optimize cpupri_vec layout to mitigate cache line contention

In reply to Deng, Pan
Quoted 27 lines · Pan
Quoted 18 lines · Pan
Quoted 15 lines

Regarding this patch, yes, using cacheline aligned could increase potential memory usage.
After internal discussion, we are thinking of an alternative method to mitigate the waste of memory usage, that is, using kmalloc() to allocate count in a different memory space rather than placing the count and cpumask together in this structure. The rationale is that, writing to address pointed by the counter and reading the address from cpumask is isolated in different memory space which could reduce the ratio of cache false sharing, besides, kmalloc() based on slub/slab could place the objects in different cache lines to reduce the cache contention. The drawback of dynamic allocation counter is that, we have to maintain the life cycle of the counters.
Could you please advise if sticking with current cache_align attribute method or using kmalloc() is preferred?

Quoted 8 lines

Well, you'd have to allocate a full cacheline anyway. If you allocate N 4 byte (counter) objects, there's a fair chance they end up in the same cacheline (its a SLAB after all) and then you're back to having a ton of false sharing.

Anyway, for you specific workload, why isn't partitioning a viable solution? It would not need any kernel modifications and would get rid of the contention entirely.

Quoted 6 lines

Thank you very much for pointing this out.

We understand cpuset partitioning would eliminate the contention. However, in managed container platforms (e.g., Kubernetes), users can obtain RT capabilities for their workloads via CAP_SYS_NICE, but they don't have host-level privileges to create cpuset partitions.

So because Kubernetes is shit, you're going to patch the kernel? Isn't that backwards? Should you not instead try and fix this kubernetes thing?

maintainer
#25 lore raw

Re: [PATCH v2 4/4] sched/rt: Split cpupri_vec->cpumask to per NUMA node to reduce contention

In reply to K Prateek Nayak
Quoted 8 lines · K Prateek Nayak

It is still not super clear to me how the logic deals with more than 128CPUs in a DIE domain because that'll need more than the u64 but sbm_find_next_bit() simply does:

    tmp = leaf->bitmap & mask; /* All are u64 */

expecting just the u64 bitmap to represent all the CPUs in the leaf.

Quoted 7 lines

If we have, say 256 CPUs per DIE, we get shift(7) and arch_sbm_mask as 7f (127) which allows a leaf to more than 64 CPUs but we are using the "u64 bitmap" directly and not:

find_next_bit(bitmap, arch_sbm_mask)

Am I missing something here?

Nope. That logic just isn't there, that was left as an exercise to the reader :-)

For AMD in particular it would be good to have one leaf per CCD, but since CCD are not enumerated in your topology (they really should be), I didn't do that.

Now, I seem to remember we had this discussion in the past some time, and you had some hacks available.

Anyway, the whole premise was to have one leaf/cacheline per cache, such that high frequency atomic ops set/clear bit, don't bounce the line around.

I took the nohz bitmap, because it was relatively simple and is known to suffer from contention under certain workloads.

#26 lore raw

Re: [PATCH v2 4/4] sched/rt: Split cpupri_vec->cpumask to per NUMA node to reduce contention

Hello Peter,

Quoted 14 lines · Peter Zijlstra
Quoted 12 lines · K Prateek Nayak

It is still not super clear to me how the logic deals with more than 128CPUs in a DIE domain because that'll need more than the u64 but sbm_find_next_bit() simply does:

    tmp = leaf->bitmap & mask; /* All are u64 */

expecting just the u64 bitmap to represent all the CPUs in the leaf.

If we have, say 256 CPUs per DIE, we get shift(7) and arch_sbm_mask as 7f (127) which allows a leaf to more than 64 CPUs but we are using the "u64 bitmap" directly and not:

Quoted 6 lines
Quoted 3 lines

find_next_bit(bitmap, arch_sbm_mask)

Am I missing something here?

Nope. That logic just isn't there, that was left as an exercise to the reader :-)

Ack! Let me go fiddle with that.

Quoted 4 lines

For AMD in particular it would be good to have one leaf per CCD, but since CCD are not enumerated in your topology (they really should be), I didn't do that.

We got the extended topology leaf 0x80000026 since 4th Generation EPYC and we (well Thomas) added the parser support in v6.10 [1] so we can discover the CCD boundary using that now ;-)

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

Quoted 3 lines

Now, I seem to remember we had this discussion in the past some time, and you had some hacks available.

That, I believe, was for the NPS boundaries that we don't expose in NPS1 but CCX should be good enough.

Quoted 7 lines

Anyway, the whole premise was to have one leaf/cacheline per cache, such that high frequency atomic ops set/clear bit, don't bounce the line around.

I took the nohz bitmap, because it was relatively simple and is known to suffer from contention under certain workloads.

Ack! It would be better to tie it to the TOPO_TILE_DOMAIN then which maps to the "CCX" on AMD and is the LLC boundary. CCD is just a cluster of CCX that is nearby - mostly the dense core offerings enumerate 2CCX per CCD.

Signature · 2 lines
Thanks and Regards,
Prateek
#27 lore raw

Re: [PATCH v2 4/4] sched/rt: Split cpupri_vec->cpumask to per NUMA node to reduce contention

Quoted 17 lines · K Prateek Nayak

Hello Peter,

Quoted 14 lines · Peter Zijlstra
Quoted 12 lines · K Prateek Nayak

It is still not super clear to me how the logic deals with more than 128CPUs in a DIE domain because that'll need more than the u64 but sbm_find_next_bit() simply does:

     tmp = leaf->bitmap & mask; /* All are u64 */

expecting just the u64 bitmap to represent all the CPUs in the leaf.

If we have, say 256 CPUs per DIE, we get shift(7) and arch_sbm_mask as 7f (127) which allows a leaf to more than 64 CPUs but we are using the "u64 bitmap" directly and not:

Quoted 9 lines
Quoted 6 lines
Quoted 3 lines

find_next_bit(bitmap, arch_sbm_mask)

Am I missing something here?

Nope. That logic just isn't there, that was left as an exercise to the reader :-)

Ack! Let me go fiddle with that.

Nice catch. I hadn't noticed this since we have fewer than 64 CPUs per die. Please feel free to send patches to me when they're available.

And regarding your other question about the calculation of arch_sbm_shift, I'm trying to understand why there is a subtraction of 1, should it be:
- arch_sbm_shift = x86_topo_system.dom_shifts[TOPO_DIE_DOMAIN] - 1;
+ arch_sbm_shift = x86_topo_system.dom_shifts[TOPO_DIE_DOMAIN - 1];
?
Are we trying to filer the raw global unique die id? - similar to topo_apicid() which mask the lower x86_topo_system.dom_shifts[dom - 1]).

With above change I can get a correct value of leaves (4) rather than (2) in the original version.

thanks,
Chenyu

#28 lore raw

Re: [PATCH v2 4/4] sched/rt: Split cpupri_vec->cpumask to per NUMA node to reduce contention

Hello Chenyu,

Quoted 40 lines · Yu C
Quoted 17 lines · K Prateek Nayak

Hello Peter,

Quoted 14 lines · Peter Zijlstra
Quoted 12 lines · K Prateek Nayak

It is still not super clear to me how the logic deals with more than 128CPUs in a DIE domain because that'll need more than the u64 but sbm_find_next_bit() simply does:

     tmp = leaf->bitmap & mask; /* All are u64 */

expecting just the u64 bitmap to represent all the CPUs in the leaf.

If we have, say 256 CPUs per DIE, we get shift(7) and arch_sbm_mask as 7f (127) which allows a leaf to more than 64 CPUs but we are using the "u64 bitmap" directly and not:

Quoted 9 lines
Quoted 6 lines
Quoted 3 lines

     find_next_bit(bitmap, arch_sbm_mask)

Am I missing something here?

Nope. That logic just isn't there, that was left as an exercise to the reader :-)

Ack! Let me go fiddle with that.

Nice catch. I hadn't noticed this since we have fewer than 64 CPUs per die. Please feel free to send patches to me when they're available.

And regarding your other question about the calculation of arch_sbm_shift, I'm trying to understand why there is a subtraction of 1, should it be:
-       arch_sbm_shift = x86_topo_system.dom_shifts[TOPO_DIE_DOMAIN] - 1; +       arch_sbm_shift = x86_topo_system.dom_shifts[TOPO_DIE_DOMAIN - 1]; ?
Are we trying to filer the raw global unique die id? - similar to topo_apicid() which mask the lower x86_topo_system.dom_shifts[dom - 1]).

Quoted 2 lines

With above change I can get a correct value of leaves (4) rather than (2) in the original version.

Thanks for confirming. I guess that would just be TOPO_TILE_DOMAIN then and would work well on AMD too since that is where the CCX is mapped. I'll get hold of a SPR / use a VM to confirm with 0x1f behavior.

I'll post the patches next week since I have to check with Andrea on how the ARM systems have decided to number their SMT threads and whether they requires separate plumbing for arch_sbm_idx_to_cpu(), arch_sbm_cpu_to_idx() or not.

Signature · 2 lines
Thanks and Regards,
Prateek
#29 lore raw

Re: [PATCH v2 4/4] sched/rt: Split cpupri_vec->cpumask to per NUMA node to reduce contention

In reply to Chen, Yu C
Quoted 34 lines · Yu C
Quoted 17 lines · K Prateek Nayak

Hello Peter,

Quoted 14 lines · Peter Zijlstra
Quoted 12 lines · K Prateek Nayak

It is still not super clear to me how the logic deals with more than 128CPUs in a DIE domain because that'll need more than the u64 but sbm_find_next_bit() simply does:

     tmp = leaf->bitmap & mask; /* All are u64 */

expecting just the u64 bitmap to represent all the CPUs in the leaf.

If we have, say 256 CPUs per DIE, we get shift(7) and arch_sbm_mask as 7f (127) which allows a leaf to more than 64 CPUs but we are using the "u64 bitmap" directly and not:

Quoted 9 lines
Quoted 6 lines
Quoted 3 lines

find_next_bit(bitmap, arch_sbm_mask)

Am I missing something here?

Nope. That logic just isn't there, that was left as an exercise to the reader :-)

Ack! Let me go fiddle with that.

Nice catch. I hadn't noticed this since we have fewer than 64 CPUs per die. Please feel free to send patches to me when they're available.

And regarding your other question about the calculation of arch_sbm_shift, I'm trying to understand why there is a subtraction of 1, should it be:

Review

Quoted 2 lines
(quoted diff) +1 -1
-       arch_sbm_shift = x86_topo_system.dom_shifts[TOPO_DIE_DOMAIN] - 1;
+       arch_sbm_shift = x86_topo_system.dom_shifts[TOPO_DIE_DOMAIN - 1];

Perhaps something like

	arch_sbm_shift = min(sizeof(unsigned long),
			     topology_get_domain_shift(TOPO_TILE_DOMAIN));

to take care of both AMD system and the 64 bit leaf bitmask limit?

Tim

Quoted 12 lines

?
Are we trying to filer the raw global unique die id? - similar to topo_apicid()
which mask the lower x86_topo_system.dom_shifts[dom - 1]).

With above change I can get a correct value of leaves (4) rather than (2) in the original version.

thanks,
Chenyu

#30 lore raw

Re: [PATCH v2 4/4] sched/rt: Split cpupri_vec->cpumask to per NUMA node to reduce contention

Hello Tim,

Quoted 11 lines · Tim Chen

Review

Quoted 4 lines

And regarding your other question about the calculation of arch_sbm_shift, I'm trying to understand why there is a subtraction of 1, should it be:

(quoted diff) +1 -1
-       arch_sbm_shift = x86_topo_system.dom_shifts[TOPO_DIE_DOMAIN] - 1;
+       arch_sbm_shift = x86_topo_system.dom_shifts[TOPO_DIE_DOMAIN - 1];

Perhaps something like

	arch_sbm_shift = min(sizeof(unsigned long),
			     topology_get_domain_shift(TOPO_TILE_DOMAIN));

to take care of both AMD system and the 64 bit leaf bitmask limit?

Ack! But do we want to separate CPUs on same LLC domain across different cachelines in 64 CPU chunks or should we use the rest of the padding to represent them?

I'm collecting some performance numbers to see if makes any difference under high contention but have you seen benefits of sharding the mask further when there are hundreds of CPU on the same LLC?

Signature · 2 lines
Thanks and Regards,
Prateek
#43 lore raw

Re: [PATCH v2 4/4] sched/rt: Split cpupri_vec->cpumask to per NUMA node to reduce contention

In reply to Tim Chen
Quoted 38 lines · Tim Chen
Quoted 34 lines · Yu C
Quoted 17 lines · K Prateek Nayak

Hello Peter,

Quoted 14 lines · Peter Zijlstra
Quoted 12 lines · K Prateek Nayak

It is still not super clear to me how the logic deals with more than 128CPUs in a DIE domain because that'll need more than the u64 but sbm_find_next_bit() simply does:

      tmp = leaf->bitmap & mask; /* All are u64 */

expecting just the u64 bitmap to represent all the CPUs in the leaf.

If we have, say 256 CPUs per DIE, we get shift(7) and arch_sbm_mask as 7f (127) which allows a leaf to more than 64 CPUs but we are using the "u64 bitmap" directly and not:

Quoted 9 lines
Quoted 6 lines
Quoted 3 lines

find_next_bit(bitmap, arch_sbm_mask)

Am I missing something here?

Nope. That logic just isn't there, that was left as an exercise to the reader :-)

Ack! Let me go fiddle with that.

Nice catch. I hadn't noticed this since we have fewer than 64 CPUs per die. Please feel free to send patches to me when they're available.

And regarding your other question about the calculation of arch_sbm_shift, I'm trying to understand why there is a subtraction of 1, should it be:

Review

Quoted 2 lines
(quoted diff) +1 -1
-       arch_sbm_shift = x86_topo_system.dom_shifts[TOPO_DIE_DOMAIN] - 1;
+       arch_sbm_shift = x86_topo_system.dom_shifts[TOPO_DIE_DOMAIN - 1];
Quoted 7 lines

Perhaps something like

	arch_sbm_shift = min(sizeof(unsigned long),
			     topology_get_domain_shift(TOPO_TILE_DOMAIN));

to take care of both AMD system and the 64 bit leaf bitmask limit?

Yes, this should be doable (Prateek has mentioned using TOPO_TILE_DOMAIN). The only drawback I can think of is that if there are more than 64 CPUs within a die, it is possible CPUs in different dies (LLCs) be indexed in the same leaf and access the same mask, which would still lead to cache contention. Maybe we should allocate the leaf cpumask according to the actual size of a die?

thanks,
Chenyu

#8 lore raw

Re: [PATCH v2 1/4] sched/rt: Optimize cpupri_vec layout to mitigate cache line contention

In reply to Pan Deng
Quoted 9 lines · Pan Deng

When running a multi-instance FFmpeg workload on an HCC system, significant cache line contention is observed around cpupri_vec->count and mask in struct root_domain.

The SUT is a 2-socket machine with 240 physical cores and 480 logical CPUs. 60 FFmpeg instances are launched, each pinned to 4 physical cores (8 logical CPUs) for transcoding tasks. Sub-threads use RT priority 99 with FIFO scheduling. FPS is used as score.

[ ... ]

Quoted 7 lines

As a result:
- FPS improves by ~11%
- Kernel cycles% drops from ~20% to ~11%
- count and mask related cache line contention is mitigated, perf c2c shows root_domain cache line 3 cycles per load drops from ~10K-59K to ~0.5K-8K, cpupri's last cache line no longer appears in the report.
- stress-ng cyclic benchmark is improved ~31.4%, command:

Quoted 5 lines
   stress-ng/stress-ng --cyclic $(nproc) --cyclic-policy fifo   \
                       --timeout 30 --minimize --metrics
- rt-tests/pi_stress is improved ~76.5%, command:
   rt-tests/pi_stress -D 30 -g $(($(nproc) / 2))

According to your test results above, this original proposal seems simple enough. It provides a general benefit, not only for FFmpeg workloads with "unusual" CPU affinity settings, but also for other common workloads that do not use CPU affinity or partitioning.
I still prefer this proposal. Later we can rebase patch 4 on top of sbm to see if it brings further improvements. patch 1 and patch 4 could form a patch series IMHO.

thanks,
Chenyu

Quoted 13 lines
kernel/sched/cpupri.h +1 -1
index d6cba0020064..245b0fa626be 100644
@@ -9,7 +9,7 @@
 
  struct cpupri_vec {
  	atomic_t		count;
-	cpumask_var_t		mask;
+	cpumask_var_t		mask	____cacheline_aligned;
  };
 
  struct cpupri {
#31 lore raw

Re: [PATCH v2 4/4] sched/rt: Split cpupri_vec->cpumask to per NUMA node to reduce contention

In reply to K Prateek Nayak

Hello Prateek,

Quoted 10 lines · K Prateek Nayak

Hello Tim,

Quoted 7 lines · Tim Chen

Review

Quoted 4 lines

And regarding your other question about the calculation of arch_sbm_shift, I'm trying to understand why there is a subtraction of 1, should it be:

(quoted diff) +1 -1
-       arch_sbm_shift = x86_topo_system.dom_shifts[TOPO_DIE_DOMAIN] - 1;
+       arch_sbm_shift = x86_topo_system.dom_shifts[TOPO_DIE_DOMAIN - 1];

Perhaps something like

Quoted 9 lines
Quoted 4 lines
	arch_sbm_shift = min(sizeof(unsigned long),
			     topology_get_domain_shift(TOPO_TILE_DOMAIN));

to take care of both AMD system and the 64 bit leaf bitmask limit?

Ack! But do we want to separate CPUs on same LLC domain across different cachelines in 64 CPU chunks or should we use the rest of the padding to represent them?

I just saw your email and I had the same question.

Quoted 5 lines

I'm collecting some performance numbers to see if makes any difference under high contention but have you seen benefits of sharding the mask further when there are hundreds of CPU on the same LLC?

We haven't tried breaking it down further. One possible approach is to partition it at L2 scope, the benefit of which may depend on the workload.

thanks,
Chenyu

#32 lore raw

Re: [PATCH v2 4/4] sched/rt: Split cpupri_vec->cpumask to per NUMA node to reduce contention

Hello Chenyu,

Quoted 3 lines · Yu C

We haven't tried breaking it down further. One possible approach is to partition it at L2 scope, the benefit of which may depend on the workload.

I fear at that point we'll have too many cachelines and too much cache pollution when the CPU starts reading this at tick to schedule a newidle balance.

A 128 core system would bring in 128 * 64B = 8kB worth of data to traverse the mask and at that point it becomes a trade off between how fast you want reads vs writes and does it even speed up writes after a certain point?

Sorry I got distracted by some other stuff today but I'll share the results from my experiments tomorrow.

Signature · 2 lines
Thanks and Regards,
Prateek
#44 lore raw

Re: [PATCH v2 4/4] sched/rt: Split cpupri_vec->cpumask to per NUMA node to reduce contention

In reply to Chen, Yu C
Quoted 44 lines · Yu C
Quoted 43 lines · Tim Chen
Quoted 34 lines · Yu C
Quoted 17 lines · K Prateek Nayak

Hello Peter,

Quoted 14 lines · Peter Zijlstra
Quoted 12 lines · K Prateek Nayak

It is still not super clear to me how the logic deals with more than 128CPUs in a DIE domain because that'll need more than the u64 but sbm_find_next_bit() simply does:

      tmp = leaf->bitmap & mask; /* All are u64 */

expecting just the u64 bitmap to represent all the CPUs in the leaf.

If we have, say 256 CPUs per DIE, we get shift(7) and arch_sbm_mask as 7f (127) which allows a leaf to more than 64 CPUs but we are using the "u64 bitmap" directly and not:

Quoted 9 lines
Quoted 6 lines
Quoted 3 lines

find_next_bit(bitmap, arch_sbm_mask)

Am I missing something here?

Nope. That logic just isn't there, that was left as an exercise to the reader :-)

Ack! Let me go fiddle with that.

Nice catch. I hadn't noticed this since we have fewer than 64 CPUs per die. Please feel free to send patches to me when they're available.

And regarding your other question about the calculation of arch_sbm_shift, I'm trying to understand why there is a subtraction of 1, should it be:

Review

Quoted 2 lines
(quoted diff) +1 -1
-       arch_sbm_shift = x86_topo_system.dom_shifts[TOPO_DIE_DOMAIN] - 1;
+       arch_sbm_shift = x86_topo_system.dom_shifts[TOPO_DIE_DOMAIN - 1];

Perhaps something like

	arch_sbm_shift = min(sizeof(unsigned long),
			     topology_get_domain_shift(TOPO_TILE_DOMAIN));
Quoted 8 lines
Quoted 2 lines

to take care of both AMD system and the 64 bit leaf bitmask limit?

Yes, this should be doable (Prateek has mentioned using TOPO_TILE_DOMAIN). The only drawback I can think of is that if there are more than 64 CPUs within a die, it is possible CPUs in different dies (LLCs) be indexed in the same leaf and access the same mask,

First, I think I should have used

	arch_sbm_shift = min(BITS_PER_LONG,
			     topology_get_domain_shift(TOPO_TILE_DOMAIN));

I am assuming that we should choose TOPO_DIE_DOMAIN for Intel CPUs and TOPO_TILE_DOMAIN for AMD CPUs. And the assumption is that such domain choice will span one L3 (I think that's the case).

Then leaf domains smaller than the
domain size will also only span one L3 by definition. So for the 128 CPUs example you gave, both leaves with CPU
0-63 and 64-127 will span the same LLC and we should not have cache
bounce.

Tim

Quoted 8 lines

which would still lead to cache
contention. Maybe we should allocate the leaf cpumask according to the actual size of a die?

thanks,
Chenyu

#33 lore raw

Re: [PATCH v2 4/4] sched/rt: Split cpupri_vec->cpumask to per NUMA node to reduce contention

In reply to K Prateek Nayak

Hello Chenyu, Tim,

Quoted 11 lines · K Prateek Nayak

Hello Chenyu,

Quoted 3 lines · Yu C

We haven't tried breaking it down further. One possible approach is to partition it at L2 scope, the benefit of which may depend on the workload.

I fear at that point we'll have too many cachelines and too much cache pollution when the CPU starts reading this at tick to schedule a newidle balance.

Quoted 7 lines

A 128 core system would bring in 128 * 64B = 8kB worth of data to traverse the mask and at that point it becomes a trade off between how fast you want reads vs writes and does it even speed up writes after a certain point?

Sorry I got distracted by some other stuff today but I'll share the results from my experiments tomorrow.

Here is some data from an experiments I ran on a 3rd Generation EPYC system (2 socket x 64C/128T (8LLCs per socket)):

Experiment: Two threads pinned per-CPU on all CPUs yielding to each other and are operating on some cpumask - one setting the current CPU on the mask and other clearing the current CPU: Just an estimate of worst case scenario is we have to do one modification per sched-switch.

I'm measuring total cycles taken for cpumask operations with following variants:

%cycles vs global mask operation

global mask                                     : 100.0000%  (var: 3.28%)
per-NUMA mask                                   :  32.9209%  (var: 7.77%)
per-LLC mask                                    :   1.2977%  (var: 4.85%)
per-LLC mask (u8 operation; no LOCK prefix)     :   0.4930%  (var: 0.83%)

per-NUMA split is 3X faster, per-LLC on this 16LLC machine is 77x faster and since there is enough space in the cacheline we can use a u8 to set and clear the CPu atomically without LOCK prefix and then do a >> 3 to get the CPU index from set bit which is 202x faster.

If we use the u8 operations, we can only read 8CPUs per 8-byte load on 64-bit system but with per-LLC mask, we can scan all 16CPUs on the LLC with one 8-byte read and and per-NUMA one requires two 8-byte reads to scan the 128CPUs per socket.

I think per-LLC mask (or, as Tim suggested, 64CPUs per cacheline) is a good tradeoff between the speedup vs amount of loads required to piece together the full cpumask. Thoughts?

Signature · 2 lines
Thanks and Regards,
Prateek
author
#9 lore raw

RE: [PATCH v2 1/4] sched/rt: Optimize cpupri_vec layout to mitigate cache line contention

In reply to Chen, Yu C
Quoted 4 lines

According to your test results above, this original proposal seems simple enough. It provides a general benefit, not only for FFmpeg workloads with "unusual" CPU affinity settings, but also for other common workloads that do not use CPU affinity or partitioning.

Yes, exactly. FFmpeg and K8s are just example scenarios - the optimization benefits any workload with RT thread contention. For instance, running cyclictest on a 2-socket, 384-logical-core system:

"cyclictest -t -i200 -h 32 -m -p 95 -q"

This patch reduces both mean and max latency by at least 40%.

Quoted 3 lines

I still prefer this proposal. Later we can rebase patch 4 on top of sbm to see if it brings further improvements. patch 1 and patch 4 could form a patch series IMHO.

Thank you for the feedback. I agree that patch 1 and patch 4 work well together. Regarding the sbm discussion: we've observed promising results in our sbm experiments, and I believe rebasing patch 4 on top of sbm would likely show further improvements beyond the per-NUMA implementation. I'll try this once the sbm implementation stabilizes.

Per Peter's previous request, I'm planning to add comments like this:
/*
* Separate mask to a different cacheline to mitigate contention
* between count (read-write) and mask (read-mostly when storing
* pointers). This alignment increases root_domain size by ~11KB,
* but eliminates cache line bouncing between cpupri_set() writers
* and cpupri_find_fitness() readers under heavy RT workloads. *
* Memory overhead considerations:
* - Systems with cpuset partitions: each partition's root_domain is
* dynamically allocated (kalloc). The ~11KB overhead per partition
* scales with partition count, acceptable on servers using partitions.
* - Systems without partitions: only the static def_root_domain incurs
* the overhead, which is manageable for typical use.
*
* Additionally, this cacheline alignment ensures cpupri starts at a
* cacheline boundary, eliminating false sharing with root_domain's
* preceding fields (rto_mask, rto_loop_next, rto_loop_start). */
cpumask_var_t mask ____cacheline_aligned_in_smp;

Since this optimization is independent of the sbm work, would it be possible to review this patch first? That would allow the sbm-related improvements (patch 4) to build on top of this foundation once they're ready.

Best Regards
Pan

#34 lore raw

Re: [PATCH v2 4/4] sched/rt: Split cpupri_vec->cpumask to per NUMA node to reduce contention

In reply to K Prateek Nayak
Quoted 45 lines · K Prateek Nayak

Hello Chenyu, Tim,

Quoted 11 lines · K Prateek Nayak

Hello Chenyu,

Quoted 3 lines · Yu C

We haven't tried breaking it down further. One possible approach is to partition it at L2 scope, the benefit of which may depend on the workload.

I fear at that point we'll have too many cachelines and too much cache pollution when the CPU starts reading this at tick to schedule a newidle balance.

Quoted 7 lines

A 128 core system would bring in 128 * 64B = 8kB worth of data to traverse the mask and at that point it becomes a trade off between how fast you want reads vs writes and does it even speed up writes after a certain point?

Sorry I got distracted by some other stuff today but I'll share the results from my experiments tomorrow.

Here is some data from an experiments I ran on a 3rd Generation EPYC system (2 socket x 64C/128T (8LLCs per socket)):

Experiment: Two threads pinned per-CPU on all CPUs yielding to each other and are operating on some cpumask - one setting the current CPU on the mask and other clearing the current CPU: Just an estimate of worst case scenario is we have to do one modification per sched-switch.

I'm measuring total cycles taken for cpumask operations with following variants:

%cycles vs global mask operation

global mask                                     : 100.0000%  (var: 3.28%)
per-NUMA mask                                   :  32.9209%  (var: 7.77%)
per-LLC mask                                    :   1.2977%  (var: 4.85%)
per-LLC mask (u8 operation; no LOCK prefix)     :   0.4930%  (var: 0.83%)

per-NUMA split is 3X faster, per-LLC on this 16LLC machine is 77x faster and since there is enough space in the cacheline we can use a u8 to set and clear the CPu atomically without LOCK prefix and then do a >> 3 to get the CPU index from set bit which is 202x faster.

Quoted 8 lines

If we use the u8 operations, we can only read 8CPUs per 8-byte load on 64-bit system but with per-LLC mask, we can scan all 16CPUs on the LLC with one 8-byte read and and per-NUMA one requires two 8-byte reads to scan the 128CPUs per socket.

I think per-LLC mask (or, as Tim suggested, 64CPUs per cacheline) is a good tradeoff between the speedup vs amount of loads required to piece together the full cpumask. Thoughts?

I agree that per-LLC mask is a good compromise between minimizing loads and offer good speed ups. I think we should get the LLC APICID
mask from 0x4 leaf (L1, L2, L3) instead of inferring from 0x1f leaf (Tile, Die ...etc) for Intel. And the cache leaf I think is 0x8000_001D leaf for AMD. Those are parsed in cacheinfo code and we can get it from there.

Tim

#35 lore raw

Re: [PATCH v2 4/4] sched/rt: Split cpupri_vec->cpumask to per NUMA node to reduce contention

Hi Prateek, Tim,

Quoted 46 lines · Tim Chen
Quoted 45 lines · K Prateek Nayak

Hello Chenyu, Tim,

Quoted 11 lines · K Prateek Nayak

Hello Chenyu,

Quoted 3 lines · Yu C

We haven't tried breaking it down further. One possible approach is to partition it at L2 scope, the benefit of which may depend on the workload.

I fear at that point we'll have too many cachelines and too much cache pollution when the CPU starts reading this at tick to schedule a newidle balance.

Quoted 7 lines

A 128 core system would bring in 128 * 64B = 8kB worth of data to traverse the mask and at that point it becomes a trade off between how fast you want reads vs writes and does it even speed up writes after a certain point?

Sorry I got distracted by some other stuff today but I'll share the results from my experiments tomorrow.

Here is some data from an experiments I ran on a 3rd Generation EPYC system (2 socket x 64C/128T (8LLCs per socket)):

Experiment: Two threads pinned per-CPU on all CPUs yielding to each other and are operating on some cpumask - one setting the current CPU on the mask and other clearing the current CPU: Just an estimate of worst case scenario is we have to do one modification per sched-switch.

I'm measuring total cycles taken for cpumask operations with following variants:

%cycles vs global mask operation

global mask                                     : 100.0000%  (var: 3.28%)
per-NUMA mask                                   :  32.9209%  (var: 7.77%)
per-LLC mask                                    :   1.2977%  (var: 4.85%)
per-LLC mask (u8 operation; no LOCK prefix)     :   0.4930%  (var: 0.83%)

per-NUMA split is 3X faster, per-LLC on this 16LLC machine is 77x faster and since there is enough space in the cacheline we can use a u8 to set and clear the CPu atomically without LOCK prefix and then do a >> 3 to get the CPU index from set bit which is 202x faster.

Quoted 8 lines
Quoted 8 lines

If we use the u8 operations, we can only read 8CPUs per 8-byte load on 64-bit system but with per-LLC mask, we can scan all 16CPUs on the LLC with one 8-byte read and and per-NUMA one requires two 8-byte reads to scan the 128CPUs per socket.

I think per-LLC mask (or, as Tim suggested, 64CPUs per cacheline) is a good tradeoff between the speedup vs amount of loads required to piece together the full cpumask. Thoughts?

Yes, making it per LLC should work well enough (for balancing) to achieve optimal benefit. Let me run some similar tests to yours,plus hackbench/schbench, to see what the results are.
BTW, on AMD systems, does the TILE domain always match the CCX where L3 is shared? On Intel the DIE is not always mapped to a domain where L3 is shared.

Quoted 7 lines

I agree that per-LLC mask is a good compromise between minimizing loads and offer good speed ups. I think we should get the LLC APICID
mask from 0x4 leaf (L1, L2, L3) instead of inferring from 0x1f leaf (Tile, Die ...etc) for Intel. And the cache leaf I think is 0x8000_001D leaf for AMD. Those are parsed in cacheinfo code and we can get it from there.

Yes, let me check how we can leverage the l3 id for that.

thanks,
Chenyu

#36 lore raw

Re: [PATCH v2 4/4] sched/rt: Split cpupri_vec->cpumask to per NUMA node to reduce contention

Hello Chenyu, Tim,

Quoted 10 lines · Yu C
Quoted 3 lines
Quoted 3 lines

I think per-LLC mask (or, as Tim suggested, 64CPUs per cacheline) is a good tradeoff between the speedup vs amount of loads required to piece together the full cpumask. Thoughts?

Yes, making it per LLC should work well enough (for balancing) to achieve optimal benefit. Let me run some similar tests to yours,plus hackbench/schbench, to see what the results are.
BTW, on AMD systems, does the TILE domain always match the CCX where L3 is shared? On Intel the DIE is not always mapped to a domain where L3 is shared.

On AMD platforms that support the extended leaf 0x80000026, CCX is always mapped to L3 and matched the data on 0x8000001D cache property leaf for L3.

Quoted 10 lines
Quoted 8 lines

I agree that per-LLC mask is a good compromise between minimizing loads and offer good speed ups.  I think we should get the LLC APICID
mask from 0x4 leaf (L1, L2, L3) instead of inferring from 0x1f leaf (Tile, Die ...etc) for Intel.  And the cache leaf I think is 0x8000_001D leaf for AMD. Those are parsed in cacheinfo code and we can get it from there.

Yes, let me check how we can leverage the l3 id for that.

Ack! I think the cacheinfo is better for all this and is also compatible with older systems that may nit have the extend topology enumeration leaf. AMD only got it two generations ago and until that only cache property leaf was used for marking the LLC (CCX) boundary.

Signature · 2 lines
Thanks and Regards,
Prateek
#37 lore raw

Re: [PATCH v2 1/4] sched/rt: Optimize cpupri_vec layout to mitigate cache line contention

Quoted 24 lines · K Prateek Nayak

Hello Chenyu, Tim,

Quoted 10 lines · Yu C
Quoted 3 lines
Quoted 3 lines

I think per-LLC mask (or, as Tim suggested, 64CPUs per cacheline) is a good tradeoff between the speedup vs amount of loads required to piece together the full cpumask. Thoughts?

Yes, making it per LLC should work well enough (for balancing) to achieve optimal benefit. Let me run some similar tests to yours,plus hackbench/schbench, to see what the results are.
BTW, on AMD systems, does the TILE domain always match the CCX where L3 is shared? On Intel the DIE is not always mapped to a domain where L3 is shared.

On AMD platforms that support the extended leaf 0x80000026, CCX is always mapped to L3 and matched the data on 0x8000001D cache property leaf for L3.

Quoted 6 lines
Quoted 5 lines
Quoted 5 lines

I agree that per-LLC mask is a good compromise between minimizing loads and offer good speed ups. I think we should get the LLC APICID
mask from 0x4 leaf (L1, L2, L3) instead of inferring from 0x1f leaf (Tile, Die ...etc) for Intel. And the cache leaf I think is 0x8000_001D leaf for AMD. Those are parsed in cacheinfo code and we can get it from there.

Quoted 6 lines
Quoted 1 line

Yes, let me check how we can leverage the l3 id for that.

Ack! I think the cacheinfo is better for all this and is also compatible with older systems that may nit have the extend topology enumeration leaf. AMD only got it two generations ago and until that only cache property leaf was used for marking the LLC (CCX) boundary.

Sorry for the delay. Here are the changes that create sbm leafs based on cacheinfo. This can be applied on top of Peter's original patches and Prateek's search optimization. We have not tested it yet, but it aims to provide an evaluation prototype that prepares for next steps:
nohz idle mask evaluation, converting cpupri_vec->cpumask to per-LLC granularity, etc. We will start testing nohz mask(if no objection on this prototype) and share the results later.

thanks,
Chenyu

#38 lore raw

PATCH 1/3 x86/sbm: Fix domain shift calculation and sbm_find_next_bit()

---
 arch/x86/kernel/cpu/topology.c | 2 +-
 include/linux/sbm.h            | 2 +-
 lib/sbm.c                      | 6 +++---
 3 files changed, 5 insertions(+), 5 deletions(-)
arch/x86/kernel/cpu/topology.c +1 -1
index 6f3d18288600..751b7517f2d5 100644
@@ -565,7 +565,7 @@ void __init topology_init_possible_cpus(void)
 	for_each_possible_cpu(cpu)
 		apicid = max(apicid, cpuid_to_apicid[cpu]);
 
-	arch_sbm_shift = x86_topo_system.dom_shifts[TOPO_DIE_DOMAIN] - 1;
+	arch_sbm_shift = x86_topo_system.dom_shifts[TOPO_DIE_DOMAIN - 1];
 	arch_sbm_leafs = 1 + (apicid >> arch_sbm_shift);
 	arch_sbm_mask = (1 << arch_sbm_shift) - 1;
 	arch_sbm_bits = arch_sbm_shift;
include/linux/sbm.h +1 -1
index 8beade6c0585..a25a96366694 100644
@@ -36,7 +36,7 @@ struct sbm {
 };
 
 extern struct sbm *sbm_alloc(void);
-extern unsigned int sbm_find_next_bit(struct sbm *sbm, int start);
+extern int sbm_find_next_bit(struct sbm *sbm, int start);
 
 #define __sbm_op(sbm, func)				\
 ({							\
lib/sbm.c +3 -3
index 167cf857cd32..8006f9b04b62 100644
@@ -34,7 +34,7 @@ struct sbm *sbm_alloc(void)
 	return NULL;
 }
 
-unsigned int sbm_find_next_bit(struct sbm *sbm, int start)
+int sbm_find_next_bit(struct sbm *sbm, int start)
 {
 	struct sbm_leaf *leaf = (void *)sbm;
 	struct sbm_root *root = (void *)sbm;
@@ -45,8 +45,8 @@ unsigned int sbm_find_next_bit(struct sbm *sbm, int start)
 		for (; nr < arch_sbm_leafs; nr++, mask = ~0UL) {
 			leaf = root->leafs[nr];
 			tmp = leaf->bitmap & mask;
-			if (!tmp)
-				continue;
+			if (tmp)
+				break;
 		}
 	} else {
 		tmp = leaf->bitmap & mask;
Signature · 1 line
2.25.1
#39 lore raw

PATCH 2/3 lib/sbm: Use dynamically sized bitmap in sbm_leaf

In reply to Chen Yu

The original sbm_leaf uses a single unsigned long (u64) as its bitmap, which limits each leaf to representing at most 64 CPUs. When a LLC domain contains more than 64 logical CPUs, the within-leaf bit position (computed as apicid & arch_sbm_mask) can exceed 63.

Since set_bit(nr, addr) treats addr as an arbitrarily long bitmap array, set_bit(65, &leaf->bitmap) would write to (&leaf->bitmap)[1], memory beyond the single unsigned long field. While ____cacheline_aligned padding may prevent corrupting adjacent leaves, the bits written into the padding are never read back by sbm_find_next_bit(), silently making those CPUs invisible.

Fix this by converting the fixed u64 bitmap to a flexible array member (unsigned long bitmap[]) whose size is determined at allocation time from the number of CPUs that of the TILE domain(1 << arch_sbm_shift). A subsequent patch will switch to use the number CPUs shared LLC rather than TILE domain.

---
 include/linux/sbm.h |  5 +++--
 lib/sbm.c           | 28 +++++++++++++++++-----------
 2 files changed, 20 insertions(+), 13 deletions(-)
include/linux/sbm.h +3 -2
index a25a96366694..8d60f4bc7004 100644
@@ -28,7 +28,8 @@ struct sbm_root {
 
 struct sbm_leaf {
 	enum sbm_type	type;
-	unsigned long	bitmap;
+	unsigned int	nbits;
+	unsigned long	bitmap[];
 } ____cacheline_aligned;
 
 struct sbm {
@@ -48,7 +49,7 @@ extern int sbm_find_next_bit(struct sbm *sbm, int start);
 		leaf = root->leafs[nr];			\
 	}						\
 	int bit = idx & arch_sbm_mask;			\
-	func(bit, &leaf->bitmap);			\
+	func(bit, leaf->bitmap);			\
 })
 
 static inline void sbm_cpu_set(struct sbm *sbm, int cpu)
lib/sbm.c +17 -11
index 8006f9b04b62..76670ce14291 100644
@@ -4,6 +4,8 @@
 struct sbm *sbm_alloc(void)
 {
 	unsigned int nr = arch_sbm_leafs;
+	unsigned int nbits = 1U << arch_sbm_shift;
+	unsigned int nlongs = BITS_TO_LONGS(nbits);
 	struct sbm_root *root = kzalloc_flex(*root, leafs, nr);
 	struct sbm_leaf *leaf;
 	if (!root)
@@ -12,10 +14,12 @@ struct sbm *sbm_alloc(void)
 	root->type = st_root;
 
 	for (int i = 0; i < nr; i++) {
-		leaf = kzalloc_obj(*leaf);
+		leaf = kzalloc(struct_size(leaf, bitmap, nlongs),
+			       GFP_KERNEL);
 		if (!leaf)
 			goto fail;
 		leaf->type = st_leaf;
+		leaf->nbits = nbits;
 		root->leafs[i] = leaf;
 	}
 
@@ -40,18 +44,20 @@ int sbm_find_next_bit(struct sbm *sbm, int start)
 	struct sbm_root *root = (void *)sbm;
 	int nr = start >> arch_sbm_shift;
 	int bit = start & arch_sbm_mask;
-	unsigned long tmp, mask = (~0UL) << bit;
+	unsigned int found;
+
 	if (sbm->type == st_root) {
-		for (; nr < arch_sbm_leafs; nr++, mask = ~0UL) {
+		do {
 			leaf = root->leafs[nr];
-			tmp = leaf->bitmap & mask;
-			if (tmp)
-				break;
-		}
+			found = find_next_bit(leaf->bitmap, leaf->nbits, bit);
+			if (found < leaf->nbits)
+				return (nr << arch_sbm_shift) | found;
+			bit = 0;
+		} while (++nr < arch_sbm_leafs);
 	} else {
-		tmp = leaf->bitmap & mask;
+		found = find_next_bit(leaf->bitmap, leaf->nbits, bit);
+		if (found < leaf->nbits)
+			return found;
 	}
-	if (!tmp)
-		return -1;
-	return (nr << arch_sbm_shift) | __ffs(tmp);
+	return -1;
 }
Signature · 1 line
2.25.1
#40 lore raw

PATCH 3/3 x86/sbm: Derive leaf granularity from LLC cacheinfo instead of topology domain

In reply to Chen Yu

From: Tim Chen <[email protected]>

Instead of using topology domain shifts (TOPO_TILE_DOMAIN) which may not align with the actual LLC boundary, derive SBM parameters from the authoritative LLC cache identification that the kernel already performs during boot CPU identification.

- intel_cacheinfo_0x4(): iterates CPUID 0x04 leaves, identifies L2/L3
- cacheinfo_amd_init_llc_id(): identifies LLC for AMD/Hygon CPUs

Besides, if sbm is not defined for an architecture, define a default implementation for it similar to cpumask. Rename arch_sbm_max_apicid to sbm_max_apicid and put it in x86 file as it is specific for x86.

---
 arch/x86/include/asm/apic.h     |  1 +
 arch/x86/include/asm/sbm.h      | 13 ++++---------
 arch/x86/kernel/cpu/cacheinfo.c | 20 +++++++++++++++++++-
 arch/x86/kernel/cpu/common.c    |  8 ++++++++
 arch/x86/kernel/cpu/topology.c  | 12 ++----------
 include/linux/sbm.h             |  9 +++++++--
 kernel/sched/core.c             |  2 ++
 kernel/sched/fair.c             |  6 ++++++
 kernel/sched/sched.h            |  1 +
 kernel/sched/topology.c         |  6 ++++++
 lib/sbm.c                       | 28 ++++++++++++++++++++++++----
 11 files changed, 80 insertions(+), 26 deletions(-)
arch/x86/include/asm/apic.h +1 -0
index 24012a91ac1e..90406d8d6af1 100644
@@ -55,6 +55,7 @@ static inline void x86_32_probe_apic(void) { }
 
 extern u32 cpuid_to_apicid[];
 extern u32 apicid_to_cpuid[];
+extern unsigned int sbm_max_apicid;
 
 #define CPU_ACPIID_INVALID	U32_MAX
 
arch/x86/include/asm/sbm.h +4 -9
index 9a4d283347d1..f48d3a985972 100644
@@ -1,12 +1,7 @@
 /* SPDX-License-Identifier: GPL-2.0 */
 #include <asm/apic.h>
 
-static __always_inline u32 arch_sbm_cpu_to_idx(unsigned int cpu)
-{
-	return cpuid_to_apicid[cpu];
-}
-
-static __always_inline u32 arch_sbm_idx_to_cpu(unsigned int idx)
-{
-	return apicid_to_cpuid[idx];
-}
+#define arch_sbm_cpu_to_idx(cpu) \
+    ((u32)(cpuid_to_apicid[(cpu)]))
+#define arch_sbm_idx_to_cpu(idx) \
+    ((u32)(apicid_to_cpuid[(idx)]))
arch/x86/kernel/cpu/cacheinfo.c +19 -1
index 51a95b07831f..fa59fa6828a6 100644
@@ -21,6 +21,8 @@
 #include <asm/smp.h>
 #include <asm/tlbflush.h>
 
+#include <linux/sbm.h>
+
 #include "cpu.h"
 
 /* Shared last level cache maps */
@@ -317,12 +319,16 @@ void cacheinfo_amd_init_llc_id(struct cpuinfo_x86 *c, u16 die_id)
 	if (c->x86 < 0x17) {
 		/* Pre-Zen: LLC is at the node level */
 		c->topo.llc_id = die_id;
+		if (c == &boot_cpu_data)
+			arch_sbm_shift = topology_get_domain_shift(TOPO_DIE_DOMAIN);
 	} else if (c->x86 == 0x17 && c->x86_model <= 0x1F) {
 		/*
 		 * Family 17h up to 1F models: LLC is at the core
 		 * complex level.  Core complex ID is ApicId[3].
 		 */
 		c->topo.llc_id = c->topo.apicid >> 3;
+		if (c == &boot_cpu_data)
+			arch_sbm_shift = 3;
 	} else {
 		/*
 		 * Newer families: LLC ID is calculated from the number
@@ -331,8 +337,11 @@ void cacheinfo_amd_init_llc_id(struct cpuinfo_x86 *c, u16 die_id)
 		u32 llc_index = find_num_cache_leaves(c) - 1;
 		struct _cpuid4_info id4 = {};
 
-		if (!amd_fill_cpuid4_info(llc_index, &id4))
+		if (!amd_fill_cpuid4_info(llc_index, &id4)) {
 			c->topo.llc_id = get_cache_id(c->topo.apicid, &id4);
+			if (c == &boot_cpu_data)
+				arch_sbm_shift = get_count_order(1 + id4.eax.split.num_threads_sharing);
+		}
 	}
 }
 
@@ -346,6 +355,8 @@ void cacheinfo_hygon_init_llc_id(struct cpuinfo_x86 *c)
 	 * at the core complex level.  Core complex ID is ApicId[3].
 	 */
 	c->topo.llc_id = c->topo.apicid >> 3;
+	if (c == &boot_cpu_data)
+		arch_sbm_shift = 3;
 }
 
 void init_amd_cacheinfo(struct cpuinfo_x86 *c)
@@ -425,6 +436,7 @@ static bool intel_cacheinfo_0x4(struct cpuinfo_x86 *c)
 	struct cpu_cacheinfo *ci = get_cpu_cacheinfo(c->cpu_index);
 	unsigned int l2_id = BAD_APICID, l3_id = BAD_APICID;
 	unsigned int l1d = 0, l1i = 0, l2 = 0, l3 = 0;
+	unsigned int llc_nthreads = 0;
 
 	if (c->cpuid_level < 4)
 		return false;
@@ -461,6 +473,7 @@ static bool intel_cacheinfo_0x4(struct cpuinfo_x86 *c)
 		case 3:
 			l3 = id4.size / 1024;
 			l3_id = calc_cache_topo_id(c, &id4);
+			llc_nthreads = 1 + id4.eax.split.num_threads_sharing;
 			break;
 		default:
 			break;
@@ -469,6 +482,11 @@ static bool intel_cacheinfo_0x4(struct cpuinfo_x86 *c)
 
 	c->topo.l2c_id = l2_id;
 	c->topo.llc_id = (l3_id == BAD_APICID) ? l2_id : l3_id;
+
+	/* Save LLC shift for SBM (boot CPU only) */
+	if (c == &boot_cpu_data && llc_nthreads)
+		arch_sbm_shift = get_count_order(llc_nthreads);
+
 	intel_cacheinfo_done(c, l3, l2, l1i, l1d);
 	return true;
 }
arch/x86/kernel/cpu/common.c +8 -0
index a8ff4376c286..5c590d8a3e78 100644
@@ -28,6 +28,7 @@
 #include <linux/stackprotector.h>
 #include <linux/utsname.h>
 #include <linux/efi.h>
+#include <linux/sbm.h>
 
 #include <asm/alternative.h>
 #include <asm/cmdline.h>
@@ -70,6 +71,7 @@
 #include <asm/set_memory.h>
 #include <asm/traps.h>
 #include <asm/sev.h>
+#include <asm/apic.h>
 #include <asm/tdx.h>
 #include <asm/posted_intr.h>
 #include <asm/runtime-const.h>
@@ -2561,6 +2563,12 @@ void __init arch_cpu_finalize_init(void)
 
 	identify_boot_cpu();
 
+	arch_sbm_leafs = 1 + (sbm_max_apicid >> arch_sbm_shift);
+	arch_sbm_mask  = (1 << arch_sbm_shift) - 1;
+	arch_sbm_bits  = arch_sbm_shift;
+	pr_info("SBM: shift(%d) leafs(%d) APIC(%x)\n",
+		arch_sbm_shift, arch_sbm_leafs, sbm_max_apicid);
+
 	select_idle_routine();
 
 	/*
arch/x86/kernel/cpu/topology.c +2 -10
index 751b7517f2d5..9245456791b0 100644
@@ -50,10 +50,7 @@ DECLARE_BITMAP(phys_cpu_present_map, MAX_LOCAL_APIC) __read_mostly;
 u32 cpuid_to_apicid[] __ro_after_init = { [0 ... NR_CPUS - 1] = BAD_APICID, };
 u32 apicid_to_cpuid[MAX_LOCAL_APIC] = { 0 };
 
-u32 arch_sbm_leafs	__ro_after_init;
-u32 arch_sbm_shift	__ro_after_init;
-u32 arch_sbm_mask	__ro_after_init;
-u32 arch_sbm_bits	__ro_after_init;
+u32 sbm_max_apicid	__ro_after_init;
 
 /* Bitmaps to mark registered APICs at each topology domain */
 static struct { DECLARE_BITMAP(map, MAX_LOCAL_APIC); } apic_maps[TOPO_MAX_DOMAIN] __ro_after_init;
@@ -565,12 +562,7 @@ void __init topology_init_possible_cpus(void)
 	for_each_possible_cpu(cpu)
 		apicid = max(apicid, cpuid_to_apicid[cpu]);
 
-	arch_sbm_shift = x86_topo_system.dom_shifts[TOPO_DIE_DOMAIN - 1];
-	arch_sbm_leafs = 1 + (apicid >> arch_sbm_shift);
-	arch_sbm_mask = (1 << arch_sbm_shift) - 1;
-	arch_sbm_bits = arch_sbm_shift;
-
-	pr_info("SBM: shift(%d) leafs(%d) APIC(%x)\n", arch_sbm_shift, arch_sbm_leafs, apicid);
+	sbm_max_apicid = apicid;
 }
 
 /*
include/linux/sbm.h +7 -2
index 8d60f4bc7004..be940bcf1ae9 100644
@@ -12,8 +12,13 @@ extern unsigned int arch_sbm_shift;
 extern unsigned int arch_sbm_mask;
 extern unsigned int arch_sbm_bits;
 
-extern unsigned int arch_sbm_cpu_to_idx(unsigned int cpu);
-extern unsigned int arch_sbm_idx_to_cpu(unsigned int idx);
+#ifndef arch_sbm_cpu_to_idx
+#define arch_sbm_cpu_to_idx(cpu) (cpu)
+#endif
+
+#ifndef arch_sbm_idx_to_cpu
+#define arch_sbm_idx_to_(idx) (idx)
+#endif
 
 enum sbm_type {
 	st_root = 0,
kernel/sched/core.c +2 -0
index 496dff740dca..2be95fa3c002 100644
@@ -8567,6 +8567,8 @@ void __init sched_init_smp(void)
 
 	sched_init_dl_servers();
 
+	init_sched_fair_class_smp();
+
 	sched_smp_initialized = true;
 }
 
kernel/sched/fair.c +6 -0
index 474ee0362998..ae95610721b4 100644
@@ -14033,6 +14033,12 @@ __init void init_sched_fair_class(void)
 #ifdef CONFIG_NO_HZ_COMMON
 	nohz.next_balance = jiffies;
 	nohz.next_blocked = jiffies;
+#endif
+}
+
+void __init init_sched_fair_class_smp(void)
+{
+#ifdef CONFIG_NO_HZ_COMMON
 	nohz.sbm = sbm_alloc();
 #endif
 }
kernel/sched/sched.h +1 -0
index 43bbf0693cca..9e45396a1512 100644
@@ -2878,6 +2878,7 @@ extern void update_max_interval(void);
 extern void init_sched_dl_class(void);
 extern void init_sched_rt_class(void);
 extern void init_sched_fair_class(void);
+extern void init_sched_fair_class_smp(void);
 
 extern void resched_curr(struct rq *rq);
 extern void resched_curr_lazy(struct rq *rq);
kernel/sched/topology.c +6 -0
index 32dcddaead82..f62a10c869fa 100644
@@ -5,6 +5,7 @@
 
 #include <linux/sched/isolation.h>
 #include <linux/bsearch.h>
+#include <linux/sbm.h>
 #include "sched.h"
 
 DEFINE_MUTEX(sched_domains_mutex);
@@ -21,6 +22,11 @@ void sched_domains_mutex_unlock(void)
 static cpumask_var_t sched_domains_tmpmask;
 static cpumask_var_t sched_domains_tmpmask2;
 
+u32 arch_sbm_leafs     __ro_after_init;
+u32 arch_sbm_shift     __ro_after_init;
+u32 arch_sbm_mask      __ro_after_init;
+u32 arch_sbm_bits      __ro_after_init;
+
 static int __init sched_debug_setup(char *str)
 {
 	sched_debug_verbose = true;
lib/sbm.c +24 -4
index 76670ce14291..45003e7b5621 100644
@@ -1,13 +1,33 @@
 /* SPDX-License-Identifier: GPL-2.0 */
 #include <linux/sbm.h>
+#include <linux/cpumask.h>
 
 struct sbm *sbm_alloc(void)
 {
-	unsigned int nr = arch_sbm_leafs;
-	unsigned int nbits = 1U << arch_sbm_shift;
-	unsigned int nlongs = BITS_TO_LONGS(nbits);
-	struct sbm_root *root = kzalloc_flex(*root, leafs, nr);
+	unsigned int nr;
+	unsigned int nbits;
+	unsigned int nlongs;
+	struct sbm_root *root;
 	struct sbm_leaf *leaf;
+
+	if (!arch_sbm_shift) {
+		unsigned int max_idx = num_possible_cpus();
+
+		/*
+		 * unsigned long is the base unit for bitmap in sbm_leaf.
+		 * Use that for default bitmap size for compact bitmap
+		 * without unused bits.
+		 */
+		arch_sbm_shift = BYTES_TO_BITS(sizeof(unsigned long));
+		arch_sbm_leafs = 1 + (max_idx >> arch_sbm_shift);
+		arch_sbm_mask = (1 << arch_sbm_shift) - 1;
+		arch_sbm_bits = arch_sbm_shift;
+	}
+
+	nr = arch_sbm_leafs;
+	nbits = 1U << arch_sbm_shift;
+	nlongs = BITS_TO_LONGS(nbits);
+	root = kzalloc_flex(*root, leafs, nr);
 	if (!root)
 		return NULL;
 
Signature · 1 line
2.25.1
#41 lore raw

Re: [PATCH 3/3] x86/sbm: Derive leaf granularity from LLC cacheinfo instead of topology domain

Hello Chenyu, Tim,

Thank you for working on it!

I got distracted seeing if there was a way to make the sbitmap work here with minimal overhead but that data structure is too over engineered for block layer specific use cases (separate cacheline to track clearing with delayed clearing, alloc_hints, and other fancy bells and whistles) and it took me a while to get something going with that.

Perhaps keeping the minimal sbm functionality out separate is a good way forward.

Quoted 18 lines · Chen Yu
arch/x86/kernel/cpu/cacheinfo.c +4 -0
@@ -317,12 +319,16 @@ void cacheinfo_amd_init_llc_id(struct cpuinfo_x86 *c, u16 die_id)
 	if (c->x86 < 0x17) {
 		/* Pre-Zen: LLC is at the node level */
 		c->topo.llc_id = die_id;
+		if (c == &boot_cpu_data)
+			arch_sbm_shift = topology_get_domain_shift(TOPO_DIE_DOMAIN);
 	} else if (c->x86 == 0x17 && c->x86_model <= 0x1F) {
 		/*
 		 * Family 17h up to 1F models: LLC is at the core
 		 * complex level.  Core complex ID is ApicId[3].
 		 */
 		c->topo.llc_id = c->topo.apicid >> 3;
+		if (c == &boot_cpu_data)
+			arch_sbm_shift = 3;
 	} else {
 		/*
 		 * Newer families: LLC ID is calculated from the number

arch/x86/kernel/cpu/cacheinfo.c void cacheinfo_amd_init_llc_id(struct cpuinfo_x86 *c, u16 die_id) · line 344

Quoted 9 lines
arch/x86/kernel/cpu/cacheinfo.c +4 -1
@@ -331,8 +337,11 @@ void cacheinfo_amd_init_llc_id(struct cpuinfo_x86 *c, u16 die_id)
 		u32 llc_index = find_num_cache_leaves(c) - 1;
 		struct _cpuid4_info id4 = {};
 
-		if (!amd_fill_cpuid4_info(llc_index, &id4))
+		if (!amd_fill_cpuid4_info(llc_index, &id4)) {
 			c->topo.llc_id = get_cache_id(c->topo.apicid, &id4);
+			if (c == &boot_cpu_data)
+				arch_sbm_shift = get_count_order(1 + id4.eax.split.num_threads_sharing);
+		}

So I'm slightly skeptical on AMD's heterogenous processors based systems getting this right but I have to get my hands on one to confirm.

Either ways, it seems like an AMD specific problem that I'll chase down if it exists but this should be fine from testing perspective on your system.

Quoted 14 lines
lib/sbm.c +7 -4
 struct sbm *sbm_alloc(void)
 {
-	unsigned int nr = arch_sbm_leafs;
-	unsigned int nbits = 1U << arch_sbm_shift;
-	unsigned int nlongs = BITS_TO_LONGS(nbits);
-	struct sbm_root *root = kzalloc_flex(*root, leafs, nr);
+	unsigned int nr;
+	unsigned int nbits;
+	unsigned int nlongs;
+	struct sbm_root *root;
 	struct sbm_leaf *leaf;
+
+	if (!arch_sbm_shift) {
+		unsigned int max_idx = num_possible_cpus();

lib/sbm.c line 24

Quoted 10 lines
lib/sbm.c +10 -0
+
+		/*
+		 * unsigned long is the base unit for bitmap in sbm_leaf.
+		 * Use that for default bitmap size for compact bitmap
+		 * without unused bits.
+		 */
+		arch_sbm_shift = BYTES_TO_BITS(sizeof(unsigned long));
+		arch_sbm_leafs = 1 + (max_idx >> arch_sbm_shift);
+		arch_sbm_mask = (1 << arch_sbm_shift) - 1;
+		arch_sbm_bits = arch_sbm_shift;

Side note:

So while chasing sbitmap, I realized there are some users of sbitmap out there that are essentially using its minimal functionality that smb provides and can be converted over to save an extra cacheline worth of overhead.

Does it make sense to keep the arch_sbm_* stuff specific to the scheduler and allow wider use of sbm for any sparse bitmap usage?

lib/sbm.c line 32

Quoted 9 lines
lib/sbm.c +6 -0
+	}
+
+	nr = arch_sbm_leafs;
+	nbits = 1U << arch_sbm_shift;
+	nlongs = BITS_TO_LONGS(nbits);
+	root = kzalloc_flex(*root, leafs, nr);
 	if (!root)
 		return NULL;

My QEMU has suddenly refused to boot after the conversion to cache properties leaf changes so I'll try to see why that is the case.

Signature · 2 lines
Thanks and Regards,
Prateek
#42 lore raw

Re: [PATCH 3/3] x86/sbm: Derive leaf granularity from LLC cacheinfo instead of topology domain

Hi Prateek,

Quoted 10 lines · K Prateek Nayak

arch/x86/kernel/cpu/cacheinfo.c void cacheinfo_amd_init_llc_id(struct cpuinfo_x86 *c, u16 die_id) · line 344

Quoted 6 lines
arch/x86/kernel/cpu/cacheinfo.c +4 -1
-		if (!amd_fill_cpuid4_info(llc_index, &id4))
+		if (!amd_fill_cpuid4_info(llc_index, &id4)) {
  			c->topo.llc_id = get_cache_id(c->topo.apicid, &id4);
+			if (c == &boot_cpu_data)
+				arch_sbm_shift = get_count_order(1 + id4.eax.split.num_threads_sharing);
+		}

So I'm slightly skeptical on AMD's heterogenous processors based systems getting this right but I have to get my hands on one to confirm.

Quoted 4 lines

Either ways, it seems like an AMD specific problem that I'll chase down if it exists but this should be fine from testing perspective on your system.

Right, this reminds me that Intel's heterogeneous (hybrid) processors might also need to be accounted for if the platform has multiple LLCs.

Quoted 27 lines
Quoted 14 lines
  struct sbm *sbm_alloc(void)
  {
lib/sbm.c +7 -4
-	unsigned int nr = arch_sbm_leafs;
-	unsigned int nbits = 1U << arch_sbm_shift;
-	unsigned int nlongs = BITS_TO_LONGS(nbits);
-	struct sbm_root *root = kzalloc_flex(*root, leafs, nr);
+	unsigned int nr;
+	unsigned int nbits;
+	unsigned int nlongs;
+	struct sbm_root *root;
  	struct sbm_leaf *leaf;
+
+	if (!arch_sbm_shift) {
+		unsigned int max_idx = num_possible_cpus();

lib/sbm.c line 24

Quoted 10 lines
lib/sbm.c +10 -0
+
+		/*
+		 * unsigned long is the base unit for bitmap in sbm_leaf.
+		 * Use that for default bitmap size for compact bitmap
+		 * without unused bits.
+		 */
+		arch_sbm_shift = BYTES_TO_BITS(sizeof(unsigned long));
+		arch_sbm_leafs = 1 + (max_idx >> arch_sbm_shift);
+		arch_sbm_mask = (1 << arch_sbm_shift) - 1;
+		arch_sbm_bits = arch_sbm_shift;

Side note:

Quoted 1 line

So while chasing sbitmap, I realized there are some users of sbitmap out

Thanks for pointing it out. I took a look at sbitmap; it seems to provide cache-friendly bit allocation strategy for different CPUs. This seems to be a bit different usage model from sbm, which aims to provide a 1:1 mapping between a CPU and its corresponding bit in a mask in a cache-friendly manner. That said, the allocation logic could be reused between sbitmap and sbm IMO.

Quoted 7 lines

there that are essentially using its minimal functionality that smb provides and can be converted over to save an extra cacheline worth of overhead.

Does it make sense to keep the arch_sbm_* stuff specific to the scheduler and allow wider use of sbm for any sparse bitmap usage?

Yes, I think this is feasible. We can introduce
struct sbm *sbm_alloc(unsigned int max_idx, unsigned int leaf_bits) to allow reuse by other non-scheduler components.

Quoted 4 lines
Quoted 4 lines
lib/sbm.c +4 -0
+	}
+
+	nr = arch_sbm_leafs;
+	nbits = 1U << arch_sbm_shift;
Quoted 9 lines

lib/sbm.c line 32

Quoted 5 lines
lib/sbm.c +2 -0
+	nlongs = BITS_TO_LONGS(nbits);
+	root = kzalloc_flex(*root, leafs, nr);
  	if (!root)
  		return NULL;

My QEMU has suddenly refused to boot after the conversion to cache properties leaf changes so I'll try to see why that is the case.

Thanks, I haven't tested on VM yet, let me take a look.

thanks,
Chenyu