Skip to contentSkip to conversation

sched/fair: Reorder scheduling related structs to reduce cache misses

RFC PATCH New Zecheng Li 1 participant 4 messages Jun 2, 2025 Scheduler

lore
Share & tools
lore

Zecheng Li

author
#0 lore raw

v2 cover sched/fair: Reorder scheduling related structs to reduce cache misses

Reorder the fields within the struct cfs_rq and struct sched_entity to improve cache locality. The two structs are heavily accessed, and their layouts have not been optimized yet. This can reduce cache misses, improving performance in CFS scheduling-related operations, particularly for servers with hundreds of cores and ~1000 cgroups.

The reordering is based on kernel data-type profiling
(https://lwn.net/Articles/955709/) indicating hot fields and fields frequently accessed together on real workloads.

This reordering aims to optimize cache utilization and improve the performance of scheduling-related functions, particularly tg_throttle_down, tg_unthrottle_up,__update_load_avg_cfs_rq, and sched_balance_update_blocked_averages. The reordering mainly considers performance when CONFIG_FAIR_GROUP_SCHED is configured. When it is disabled, there is no CFS bandwidth control and only a single cfs_rq exists per CPU, thus its layout would not significantly impact performance.

We use a benchmark with multiple cgroup levels to simulate real server load. The benchmark constructs a tree structure hierarchy of cgroups, with “width” and “depth” parameters controlling the number of children per node and the depth of the tree. Each leaf cgroup runs a schbench workload and gets an 80% quota of the total CPU quota divided by number of leaf cgroups (in other words, the target CPU load is set to 80%) to exercise the throttling functions. Bandwidth control period is set to 10ms. We run the benchmark on Intel and AMD machines; each machine has hundreds of threads.

Kernel LLC load misses for 30 seconds. d3 w10 (wider tree) means a cgroup hierarchy of 3 levels, each level has 10 children, totaling 1000 leaf cgroups. d5 w4 represents a deeper tree with more hierarchies. Each benchmark is run 10 times. The table shows 95% confidence intervals of the kernel LLC misses in millions.

| Kernel LLC Misses | d3 w10            | d5 w4             |
+-------------------+-------------------+-------------------+
| AMD-orig          | [3025.5, 3344.1]M | [3382.4, 3607.8]M |
| AMD-opt           | [2410.7, 2556.9]M | [2565.4, 2931.2]M |
| Change            | -22.01%           | -21.37%           |
| Intel-orig        | [1157.2, 1249.0]M | [1343.7, 1630.7]M |
| Intel-opt         | [960.2, 1023.0]M  | [1092.7, 1350.7]M |
| Change            | -17.59%           | -17.86%           |

Since the benchmark limits CPU quota, the RPS results reported by schbench did not show statistically significant improvement as it does not reflect the kernel overhead reduction.

Perf data shows the reduction of LLC misses percentage within the kernel for the depth 5, width 4 workload. The symbols are taken from the union of top 10 symbols in both original and optimized profiles.

| Symbol                                | Intel-orig | Intel-opt |
+---------------------------------------+------------+-----------+
| worker_thread                         | 75.41%     | 78.95%    |
| tg_unthrottle_up                      | 3.21%      | 1.61%     |
| tg_throttle_down                      | 2.42%      | 1.77%     |
| __update_load_avg_cfs_rq              | 1.95%      | 1.60%     |
| walk_tg_tree_from                     | 1.23%      | 0.91%     |
| sched_balance_update_blocked_averages | 1.09%      | 1.13%     |
| sched_balance_rq                      | 1.03%      | 1.08%     |
| _raw_spin_lock                        | 1.01%      | 1.23%     |
| task_mm_cid_work                      | 0.87%      | 1.09%     |
| __update_load_avg_se                  | 0.78%      | 0.48%     |
| Symbol                                | AMD-orig | AMD-opt |
+---------------------------------------+----------+---------+
| worker_thread                         | 53.97%   | 61.49%  |
| sched_balance_update_blocked_averages | 3.94%    | 2.48%   |
| __update_load_avg_cfs_rq              | 3.52%    | 2.62%   |
| update_load_avg                       | 2.66%    | 2.19%   |
| tg_throttle_down                      | 1.99%    | 1.57%   |
| tg_unthrottle_up                      | 1.98%    | 1.34%   |
| __update_load_avg_se                  | 1.89%    | 1.32%   |
| walk_tg_tree_from                     | 1.79%    | 1.37%   |
| sched_clock_noinstr                   | 1.59%    | 1.01%   |
| sched_balance_rq                      | 1.53%    | 1.26%   |
| _raw_spin_lock                        | 1.47%    | 1.41%   |
| task_mm_cid_work                      | 1.34%    | 1.42%   |

The percentage of the LLC misses in the system is reduced.

Other benchmarks (without CPU share limits) show no regression. They ran in a cgroup hierarchy with depth 5, width 4 setting (1024 instances) for 10 runs. perf profiles confirm the targeted CFS functions have lower LLC misses after reordering cfs_rq and sched_entity.

For avg latency and time, lower is better; for record/s, higher is better. Ranges are 95% CI.

| base | opt | metric
-----------+----------------------+----------------------+-------------

 sysbench  | 45.05 [44.69, 45.42] | 44.51 [43.99, 45.04] | avg latency
 hackbench | 27.00 [26.39, 27.61] | 27.29 [26.38, 28.20] | time
 ebizzy    | 948.2 [848.1, 1048]  | 951.8 [840.8, 1063]  | record/s

LLC cache miss in kernel. The fluctuation is in the order of ±10%.

| base | opt
-----------+--------+--------

 sysbench  | 404M   | 351M
 hackbench | 3,294M | 3,169M
 ebizzy    | 2,149M | 1,956M

Although we see a noticable reduction in LLC misses, the application throughput improvement is negligible because the cycles spent accessing cfs_rq and sched_entity are around ~1% among these benchmarks. The improvement saves 20% of the cycles accessing them, which is a ~0.2% direct saving. However, this benefits most workloads with quite large cgroup hierarchies.

v2 updates:

- Add macros to conditionally align a cache group to avoid extra RAM paddings on architectures with cacheline sizes other than 64B.

- Add more benchmark results.

Zecheng Li (3):
cache: conditionally align cache groups
sched/fair: Reorder struct cfs_rq
sched/fair: Reorder struct sched_entity

 include/linux/cache.h | 28 +++++++++++++++
 include/linux/sched.h | 39 +++++++++++----------
 kernel/sched/core.c   | 81 ++++++++++++++++++++++++++++++++++++++++++-
 kernel/sched/sched.h  | 81 +++++++++++++++++++++++++++++--------------
 4 files changed, 184 insertions(+), 45 deletions(-)

base-commit: a5806cd506af5a7c19bcd596e4708b5c464bfd21

Signature · 1 line
2.49.0
author
#1 lore raw

RFC PATCH v2 1/3 cache: conditionally align cache groups

Introduces a pair of macros, __cacheline_group_begin_aligned_cond and __cacheline_group_end_aligned_cond, to provide conditional cacheline alignment for cache groups. The alignment behavior is as follows:

If the COND parameter is equal to SMP_CACHE_BYTES, the cache group will be aligned to SMP_CACHE_BYTES.

If COND is not equal to SMP_CACHE_BYTES, no specific additional cacheline alignment is enforced by using __aligned(1).

This mechanism allows for more precise control over cacheline alignment, ensuring that layout optimizations intended for one cache architecture do not inadvertently degrade efficiency or introduce holes on systems with different cache line sizes.

---
 include/linux/cache.h | 28 ++++++++++++++++++++++++++++
 1 file changed, 28 insertions(+)
include/linux/cache.h +28 -0
index e69768f50d53..8b5dadf1c487 100644
@@ -147,6 +147,34 @@
 	struct { } __cacheline_group_pad__##GROUP		\
 	__aligned((__VA_ARGS__ + 0) ? : SMP_CACHE_BYTES)
 
+/**
+ * __cacheline_group_begin_aligned_cond - conditionally align a cache group
+ * @GROUP: name of the group
+ * @COND: a size; if it equals SMP_CACHE_BYTES, the group will be aligned
+ * to SMP_CACHE_BYTES. Otherwise, no specific cacheline alignment
+ * is enforced.
+ *
+ */
+#define __cacheline_group_begin_aligned_cond(GROUP, COND)	\
+	__cacheline_group_begin(GROUP)				\
+	__aligned(((COND) == SMP_CACHE_BYTES) ? SMP_CACHE_BYTES : 1)
+
+/**
+ * __cacheline_group_end_aligned_cond - declare a conditionally aligned group end
+ * @GROUP: name of the group
+ * @COND: condition (size); if it equals SMP_CACHE_BYTES, padding will
+ * be aligned to SMP_CACHE_BYTES. Otherwise, no alignment.
+ *
+ * This complements __cacheline_group_begin_aligned_cond.
+ * The end marker itself is aligned to sizeof(long).
+ * The final padding to avoid the next field falling into this cacheline
+ * is applied conditionally based on COND.
+ */
+#define __cacheline_group_end_aligned_cond(GROUP, COND)                 \
+        __cacheline_group_end(GROUP) __aligned(sizeof(long));           \
+        struct { } __cacheline_group_pad__##GROUP                       \
+        __aligned(((COND) == SMP_CACHE_BYTES) ? SMP_CACHE_BYTES : 1)
+
 #ifndef CACHELINE_ASSERT_GROUP_MEMBER
 #define CACHELINE_ASSERT_GROUP_MEMBER(TYPE, GROUP, MEMBER) \
 	BUILD_BUG_ON(!(offsetof(TYPE, MEMBER) >= \
Signature · 1 line
2.49.0
author
#2 lore raw

RFC PATCH v2 2/3 sched/fair: Reorder struct cfs_rq

In reply to Zecheng Li

Hot fields are moved to the head of the struct, for a total of 128 bytes, which accounts for two cache lines in x86. With all related CONFIG enabled, it also moves fields originally located around the 4th and 5th cache line offsets to provide better locality when executing CFS bandwidth control functions. Due to the removal of holes in the struct, its size is observed to reduce by one cacheline in an x86 system.

The following changes are proposed:

- Move curr, rq, tg, throttle_count, and runtime_enabled to the first cache line as they are frequently accessed (and mostly read). They are pointers to the closely related structs (rq, tg) or checked as a condition (curr, throttle_count and runtime_enabled).

- propagate and idle, two frequently read fields, were placed in separate cache lines. Group them in cache line 2 with the remaining fields previously in cache line 1 to fill the hole.

- on_list is often accessed together with throttle_clock_* in tg_unthrottle_up and tg_throttle_down functions. Move runtime_remaining and throttled_pelt_idle, which are less frequently accessed, to the outside to allow grouping on_list and throttle-related fields together. This cache group aligns to 64 byte boundaries only when the target architecture utilizes a 64 byte cache line size.

- Use __cacheline_group_* macros to delineate logically grouped fields for cache alignment, with compile-time checks added in cfs_rq_struct_check.

---
 kernel/sched/core.c  | 61 ++++++++++++++++++++++++++++++++-
 kernel/sched/sched.h | 81 ++++++++++++++++++++++++++++++--------------
 2 files changed, 115 insertions(+), 27 deletions(-)
kernel/sched/core.c +60 -1
index c81cf642dba0..ba89cd4f2fac 100644
@@ -8524,6 +8524,8 @@ LIST_HEAD(task_groups);
 static struct kmem_cache *task_group_cache __ro_after_init;
 #endif
 
+static void __init cfs_rq_struct_check(void);
+
 void __init sched_init(void)
 {
 	unsigned long ptr = 0;
@@ -8540,7 +8542,7 @@ void __init sched_init(void)
 	BUG_ON(!sched_class_above(&fair_sched_class, &ext_sched_class));
 	BUG_ON(!sched_class_above(&ext_sched_class, &idle_sched_class));
 #endif
-
+	cfs_rq_struct_check();
 	wait_bit_init();
 
 #ifdef CONFIG_FAIR_GROUP_SCHED
@@ -10746,3 +10748,60 @@ void sched_enq_and_set_task(struct sched_enq_and_set_ctx *ctx)
 		set_next_task(rq, ctx->p);
 }
 #endif	/* CONFIG_SCHED_CLASS_EXT */
+
+static void __init cfs_rq_struct_check(void)
+{
+	/*
+	 * The first two cache lines are hot and mostly read
+	 * except load.inv_weight
+	 */
+	CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, hot, load);
+	CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, hot, nr_queued);
+	CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, hot, h_nr_queued);
+	CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, hot, h_nr_runnable);
+	CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, hot, h_nr_idle);
+	CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, hot, curr);
+
+#ifdef CONFIG_FAIR_GROUP_SCHED
+	CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, hot, rq);
+	CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, hot, tg);
+
+#ifdef CONFIG_CFS_BANDWIDTH
+	CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, hot, throttle_count);
+	CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, hot, runtime_enabled);
+#endif
+	CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, hot, idle);
+
+#ifdef CONFIG_SMP
+	CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, hot, propagate);
+#endif
+#endif
+	CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, hot, avg_vruntime);
+	CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, hot, avg_load);
+	CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, hot, min_vruntime);
+	CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, hot, tasks_timeline);
+	CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, hot, next);
+
+	/*
+	 * This cache line groups hot fields of the throttling functions.
+	 * This group is enabled when CFS_BANDWIDTH is configured.
+	 */
+#ifdef CONFIG_CFS_BANDWIDTH
+#ifdef CONFIG_FAIR_GROUP_SCHED
+	CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, throttle, throttled);
+	CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, throttle, on_list);
+	CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, throttle,
+				      leaf_cfs_rq_list);
+
+	CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, throttle, throttled_clock);
+	CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, throttle,
+				      throttled_clock_pelt);
+	CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, throttle,
+				      throttled_clock_pelt_time);
+	CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, throttle,
+				      throttled_clock_self);
+	CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, throttle,
+				      throttled_clock_self_time);
+#endif
+#endif
+}
kernel/sched/sched.h +55 -26

131 lines not on this page · raw message

Signature · 1 line
2.49.0
author
#3 lore raw

RFC PATCH v2 3/3 sched/fair: Reorder struct sched_entity

In reply to Zecheng Li

Groups the mostly read fields in struct sched_entity to the head of the struct when CONFIG_FAIR_GROUP_SCHED is set. The additional fields from CONFIG_FAIR_GROUP_SCHED are related to CFS cgroup scheduling and were placed far away from the hot fields load, on_rq and vruntime. They are moved together to the head of the struct to exploit locality. Although depth is not as hot as other fields, we keep it here to avoid breaking the #ifdef boundaries. Adds enforced alignment of struct sched_entity to ensure the cache group works as intended.

Also adds a compile time check when CONFIG_FAIR_GROUP_SCHED is set to check the placement of the hot fields.

---
 include/linux/sched.h | 39 +++++++++++++++++++++------------------
 kernel/sched/core.c   | 20 ++++++++++++++++++++
 2 files changed, 41 insertions(+), 18 deletions(-)
include/linux/sched.h +21 -18
index f96ac1982893..b20b2d590cf6 100644
@@ -567,40 +567,43 @@ struct sched_statistics {
 } ____cacheline_aligned;
 
 struct sched_entity {
+#ifdef CONFIG_FAIR_GROUP_SCHED
+	/* Group the read most hot fields in sched_entity */
+	__cacheline_group_begin(hot);
+	struct sched_entity		*parent;
+	/* rq on which this entity is (to be) queued: */
+	struct cfs_rq			*cfs_rq;
+	/* rq "owned" by this entity/group: */
+	struct cfs_rq			*my_q;
+	/* cached value of my_q->h_nr_running */
+	unsigned long			runnable_weight;
+	int				depth;
+#endif
+	unsigned char			on_rq;
+	unsigned char			sched_delayed;
+	unsigned char			rel_deadline;
+	unsigned char			custom_slice;
 	/* For load-balancing: */
 	struct load_weight		load;
+	u64				vruntime;
+#ifdef CONFIG_FAIR_GROUP_SCHED
+	__cacheline_group_end(hot);
+#endif
 	struct rb_node			run_node;
 	u64				deadline;
 	u64				min_vruntime;
 	u64				min_slice;
 
 	struct list_head		group_node;
-	unsigned char			on_rq;
-	unsigned char			sched_delayed;
-	unsigned char			rel_deadline;
-	unsigned char			custom_slice;
-					/* hole */
 
 	u64				exec_start;
 	u64				sum_exec_runtime;
 	u64				prev_sum_exec_runtime;
-	u64				vruntime;
 	s64				vlag;
 	u64				slice;
 
 	u64				nr_migrations;
 
-#ifdef CONFIG_FAIR_GROUP_SCHED
-	int				depth;
-	struct sched_entity		*parent;
-	/* rq on which this entity is (to be) queued: */
-	struct cfs_rq			*cfs_rq;
-	/* rq "owned" by this entity/group: */
-	struct cfs_rq			*my_q;
-	/* cached value of my_q->h_nr_running */
-	unsigned long			runnable_weight;
-#endif
-
 #ifdef CONFIG_SMP
 	/*
 	 * Per entity load average tracking.
@@ -610,7 +613,7 @@ struct sched_entity {
 	 */
 	struct sched_avg		avg;
 #endif
-};
+} ____cacheline_aligned;
 
 struct sched_rt_entity {
 	struct list_head		run_list;
kernel/sched/core.c +20 -0
index ba89cd4f2fac..dcc50df9e8ca 100644
@@ -8525,6 +8525,7 @@ static struct kmem_cache *task_group_cache __ro_after_init;
 #endif
 
 static void __init cfs_rq_struct_check(void);
+static void __init sched_entity_struct_check(void);
 
 void __init sched_init(void)
 {
@@ -8543,6 +8544,7 @@ void __init sched_init(void)
 	BUG_ON(!sched_class_above(&ext_sched_class, &idle_sched_class));
 #endif
 	cfs_rq_struct_check();
+	sched_entity_struct_check();
 	wait_bit_init();
 
 #ifdef CONFIG_FAIR_GROUP_SCHED
@@ -10805,3 +10807,21 @@ static void __init cfs_rq_struct_check(void)
 #endif
 #endif
 }
+
+static void __init sched_entity_struct_check(void)
+{
+	/*
+	 * The compile time check is only enabled with CONFIG_FAIR_GROUP_SCHED.
+	 * We care about the placement of six hottest fields below.
+	 */
+#ifdef CONFIG_FAIR_GROUP_SCHED
+	CACHELINE_ASSERT_GROUP_MEMBER(struct sched_entity, hot, parent);
+	CACHELINE_ASSERT_GROUP_MEMBER(struct sched_entity, hot, cfs_rq);
+	CACHELINE_ASSERT_GROUP_MEMBER(struct sched_entity, hot, my_q);
+	CACHELINE_ASSERT_GROUP_MEMBER(struct sched_entity, hot,
+				      runnable_weight);
+	CACHELINE_ASSERT_GROUP_MEMBER(struct sched_entity, hot, on_rq);
+	CACHELINE_ASSERT_GROUP_MEMBER(struct sched_entity, hot, load);
+	CACHELINE_ASSERT_GROUP_MEMBER(struct sched_entity, hot, vruntime);
+#endif
+}
Signature · 1 line
2.49.0