[PATCH v3] sched: reorder some fields in struct rq

[PATCH v3] sched: reorder some fields in struct rq

[Blake Jones]

This colocates some hot fields in "struct rq" to be on the same cache line
as others that are often accessed at the same time or in similar ways.

Using data from a Google-internal fleet-scale profiler, I found three
distinct groups of hot fields in struct rq:

- (1) The runqueue lock: __lock.

- (2) Those accessed from hot code in pick_next_task_fair():
      nr_running, nr_numa_running, nr_preferred_running,
      ttwu_pending, cpu_capacity, curr, idle.

- (3) Those accessed from some other hot codepaths, e.g.
      update_curr(), update_rq_clock(), and scheduler_tick():
      clock_task, clock_pelt, clock, lost_idle_time,
      clock_update_flags, clock_pelt_idle, clock_idle.

The cycles spent on accessing these different groups of fields broke down
roughly as follows:

- 50% on group (1) (the runqueue lock, always read-write)
- 39% on group (2) (load:store ratio around 38:1)
-  8% on group (3) (load:store ratio around 5:1)
-  3% on all the other fields

Most of the fields in group (3) are already in a cache line grouping; this
patch just adds "clock" and "clock_update_flags" to that group. The fields
in group (2) are scattered across several cache lines; the main effect of
this patch is to group them together, on a single line at the beginning of
the structure. A few other less performance-critical fields (nr_switches,
numa_migrate_on, has_blocked_load, nohz_csd, last_blocked_load_update_tick)
were also reordered to reduce holes in the data structure.

Since the runqueue lock is acquired from so many different contexts, and is
basically always accessed using an atomic operation, putting it on either
of the cache lines for groups (2) or (3) would slow down accesses to those
fields dramatically, since those groups are read-mostly accesses.

This patch does not change the size of "struct rq" on machines with 64-byte
cache lines. The additional "____cacheline_aligned" to put the runqueue
lock on the next cache line will add an additional 64 bytes of padding on
machines with 128-byte cache lines; although this is unfortunate, it seemed
more likely to lead to stably good performance than e.g. by just putting
the runqueue lock somewhere in the middle of the structure and hoping it
wasn't on an otherwise busy cache line.

Signed-off-by: Blake Jones <blakejones@google.com>
Reviewed-by: Madadi Vineeth Reddy <vineethr@linux.ibm.com>
Tested-by: Madadi Vineeth Reddy <vineethr@linux.ibm.com>
---
 kernel/sched/sched.h | 75 +++++++++++++++++++++++++++-----------------
 1 file changed, 46 insertions(+), 29 deletions(-)

v2 -> v3 changes:
- Resynced and retested. Results are consistent with v2.
  Link to v2: https://lore.kernel.org/lkml/CAP_z_Cg1Yvyq1qEkYXcyL-=zqTxqMxpV3Ap7ggzd4Q8f+=Zd9A@mail.gmail.com/T/
  v2 received a Reviewed-By and Tested-By two months ago, but didn't get
  any response to multiple followup pings.

v1 -> v2 changes:
- Resynced to tip/sched/core tree, which has removed CONFIG_SMP.
  Link to v1: https://lore.kernel.org/lkml/20250722201339.1198239-1-blakejones@google.com/T/#u

I ran "hackbench" to test this change, but it didn't show very conclusive
results.  Looking at a profile of the hackbench run, it was spending 95% of
its cycles inside __alloc_skb(), __kfree_skb(), or kmem_cache_free() -
almost all of which was spent updating memcg counters or contending on the
list_lock in kmem_cache_node. In contrast, it spent less than 0.5% of its
cycles inside either schedule() or try_to_wake_up(). So it's not surprising
that it didn't show useful results here.

Instead, to test this, I wrote a focused load test that would put load on
the pick_next_task_fair() path. A parent process would fork many child
processes, and each child would nanosleep() for 1 msec many times in a
loop. The load test was monitored with "perf", and I looked at the amount
of cycles that were spent with sched_balance_rq() on the stack. The test
reliably showed ~5% of all cycles were spent there. I ran it 100 times on
a pair of 2-socket Intel Haswell machines (72 vCPUs per machine) - one
running the tip of sched/core, the other running this change - using 360
child processes and 8192 1-msec sleeps per child.  The mean cycle count
dropped from 5.14B to 4.91B, or a 4.6% decrease.

More importantly, given that this change reduces cache misses in a very hot
kernel codepath, there's likely to be additional application performance
improvement due to reduced cache conflicts from kernel data structures.

diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index e7718f12bc55..e9f71a09a5d8 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -1114,28 +1114,47 @@ DECLARE_STATIC_KEY_FALSE(sched_uclamp_used);
  * acquire operations must be ordered by ascending &runqueue.
  */
 struct rq {
-	/* runqueue lock: */
-	raw_spinlock_t		__lock;
-
-	/* Per class runqueue modification mask; bits in class order. */
-	unsigned int		queue_mask;
+	/*
+	 * The following members are loaded together from pick_next_task(),
+	 * and should be on an isolated cache line to avoid cache pollution.
+	 * They are loaded much more often than they are stored.
+	 */
 	unsigned int		nr_running;
 #ifdef CONFIG_NUMA_BALANCING
 	unsigned int		nr_numa_running;
 	unsigned int		nr_preferred_running;
-	unsigned int		numa_migrate_on;
 #endif
+	unsigned int		ttwu_pending;
+	unsigned long		cpu_capacity;
+#ifdef CONFIG_SCHED_PROXY_EXEC
+	struct task_struct __rcu	*donor;  /* Scheduling context */
+	struct task_struct __rcu	*curr;   /* Execution context */
+#else
+	union {
+		struct task_struct __rcu *donor; /* Scheduler context */
+		struct task_struct __rcu *curr;  /* Execution context */
+	};
+#endif
+	struct task_struct	*idle;
+	/* padding left here deliberately */
+
+	/*
+	 * The next cacheline holds the (hot) runqueue lock, as well as
+	 * some other less performance-critical fields.
+	 */
+	u64			nr_switches	____cacheline_aligned;
+
+	/* runqueue lock: */
+	raw_spinlock_t		__lock;
+
 #ifdef CONFIG_NO_HZ_COMMON
-	unsigned long		last_blocked_load_update_tick;
-	unsigned int		has_blocked_load;
-	call_single_data_t	nohz_csd;
 	unsigned int		nohz_tick_stopped;
 	atomic_t		nohz_flags;
+	unsigned int		has_blocked_load;
+	unsigned long		last_blocked_load_update_tick;
+	call_single_data_t	nohz_csd;
 #endif /* CONFIG_NO_HZ_COMMON */
 
-	unsigned int		ttwu_pending;
-	u64			nr_switches;
-
 #ifdef CONFIG_UCLAMP_TASK
 	/* Utilization clamp values based on CPU's RUNNABLE tasks */
 	struct uclamp_rq	uclamp[UCLAMP_CNT] ____cacheline_aligned;
@@ -1158,6 +1177,9 @@ struct rq {
 	struct list_head	*tmp_alone_branch;
 #endif /* CONFIG_FAIR_GROUP_SCHED */
 
+#ifdef CONFIG_NUMA_BALANCING
+	unsigned int		numa_migrate_on;
+#endif
 	/*
 	 * This is part of a global counter where only the total sum
 	 * over all CPUs matters. A task can increase this counter on
@@ -1166,36 +1188,33 @@ struct rq {
 	 */
 	unsigned long 		nr_uninterruptible;
 
-#ifdef CONFIG_SCHED_PROXY_EXEC
-	struct task_struct __rcu	*donor;  /* Scheduling context */
-	struct task_struct __rcu	*curr;   /* Execution context */
-#else
-	union {
-		struct task_struct __rcu *donor; /* Scheduler context */
-		struct task_struct __rcu *curr;  /* Execution context */
-	};
-#endif
 	struct sched_dl_entity	*dl_server;
-	struct task_struct	*idle;
 	struct task_struct	*stop;
 	unsigned long		next_balance;
 	struct mm_struct	*prev_mm;
 
-	unsigned int		clock_update_flags;
-	u64			clock;
-	/* Ensure that all clocks are in the same cache line */
+	/* Per class runqueue modification mask; bits in class order. */
+	unsigned int		queue_mask;
+
+	atomic_t		nr_iowait;
+
+	/*
+	 * The following fields of clock data are frequently referenced
+	 * and updated together, and should go on their own cache line.
+	 */
 	u64			clock_task ____cacheline_aligned;
 	u64			clock_pelt;
+	u64			clock;
 	unsigned long		lost_idle_time;
+	unsigned int		clock_update_flags;
 	u64			clock_pelt_idle;
 	u64			clock_idle;
+
 #ifndef CONFIG_64BIT
 	u64			clock_pelt_idle_copy;
 	u64			clock_idle_copy;
 #endif
 
-	atomic_t		nr_iowait;
-
 	u64 last_seen_need_resched_ns;
 	int ticks_without_resched;
 
@@ -1206,8 +1225,6 @@ struct rq {
 	struct root_domain		*rd;
 	struct sched_domain __rcu	*sd;
 
-	unsigned long		cpu_capacity;
-
 	struct balance_callback *balance_callback;
 
 	unsigned char		nohz_idle_balance;
-- 
2.51.1.838.g19442a804e-goog

Re: [PATCH v3] sched: reorder some fields in struct rq

[Peter Zijlstra]

On Tue, Oct 28, 2025 at 01:03:48AM -0700, Blake Jones wrote:

> diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
> index e7718f12bc55..e9f71a09a5d8 100644
> --- a/kernel/sched/sched.h
> +++ b/kernel/sched/sched.h
> @@ -1114,28 +1114,47 @@ DECLARE_STATIC_KEY_FALSE(sched_uclamp_used);
>   * acquire operations must be ordered by ascending &runqueue.
>   */
>  struct rq {
> -	/* runqueue lock: */
> -	raw_spinlock_t		__lock;
> -
> -	/* Per class runqueue modification mask; bits in class order. */
> -	unsigned int		queue_mask;

queue_mask is modified right along with nr_running -- every
enqueue/dequeue. It seems weird to move it away from nr_running.

> +	/*
> +	 * The following members are loaded together from pick_next_task(),
> +	 * and should be on an isolated cache line to avoid cache pollution.
> +	 * They are loaded much more often than they are stored.
> +	 */
>  	unsigned int		nr_running;
>  #ifdef CONFIG_NUMA_BALANCING
>  	unsigned int		nr_numa_running;
>  	unsigned int		nr_preferred_running;
> -	unsigned int		numa_migrate_on;
>  #endif
> +	unsigned int		ttwu_pending;
> +	unsigned long		cpu_capacity;
> +#ifdef CONFIG_SCHED_PROXY_EXEC
> +	struct task_struct __rcu	*donor;  /* Scheduling context */
> +	struct task_struct __rcu	*curr;   /* Execution context */
> +#else
> +	union {
> +		struct task_struct __rcu *donor; /* Scheduler context */
> +		struct task_struct __rcu *curr;  /* Execution context */
> +	};
> +#endif
> +	struct task_struct	*idle;
> +	/* padding left here deliberately */
> +
> +	/*
> +	 * The next cacheline holds the (hot) runqueue lock, as well as
> +	 * some other less performance-critical fields.
> +	 */
> +	u64			nr_switches	____cacheline_aligned;
> +
> +	/* runqueue lock: */
> +	raw_spinlock_t		__lock;

Does it not make more sense to put the lock in the same cacheline as the
clock fields?

> +
>  #ifdef CONFIG_NO_HZ_COMMON
> -	unsigned long		last_blocked_load_update_tick;
> -	unsigned int		has_blocked_load;
> -	call_single_data_t	nohz_csd;
>  	unsigned int		nohz_tick_stopped;
>  	atomic_t		nohz_flags;
> +	unsigned int		has_blocked_load;
> +	unsigned long		last_blocked_load_update_tick;
> +	call_single_data_t	nohz_csd;
>  #endif /* CONFIG_NO_HZ_COMMON */
>  
> -	unsigned int		ttwu_pending;
> -	u64			nr_switches;
> -
>  #ifdef CONFIG_UCLAMP_TASK
>  	/* Utilization clamp values based on CPU's RUNNABLE tasks */
>  	struct uclamp_rq	uclamp[UCLAMP_CNT] ____cacheline_aligned;
> @@ -1158,6 +1177,9 @@ struct rq {
>  	struct list_head	*tmp_alone_branch;
>  #endif /* CONFIG_FAIR_GROUP_SCHED */
>  
> +#ifdef CONFIG_NUMA_BALANCING
> +	unsigned int		numa_migrate_on;
> +#endif
>  	/*
>  	 * This is part of a global counter where only the total sum
>  	 * over all CPUs matters. A task can increase this counter on
> @@ -1166,36 +1188,33 @@ struct rq {
>  	 */
>  	unsigned long 		nr_uninterruptible;
>  
> -#ifdef CONFIG_SCHED_PROXY_EXEC
> -	struct task_struct __rcu	*donor;  /* Scheduling context */
> -	struct task_struct __rcu	*curr;   /* Execution context */
> -#else
> -	union {
> -		struct task_struct __rcu *donor; /* Scheduler context */
> -		struct task_struct __rcu *curr;  /* Execution context */
> -	};
> -#endif
>  	struct sched_dl_entity	*dl_server;
> -	struct task_struct	*idle;
>  	struct task_struct	*stop;
>  	unsigned long		next_balance;
>  	struct mm_struct	*prev_mm;
>  
> -	unsigned int		clock_update_flags;
> -	u64			clock;
> -	/* Ensure that all clocks are in the same cache line */
> +	/* Per class runqueue modification mask; bits in class order. */
> +	unsigned int		queue_mask;
> +
> +	atomic_t		nr_iowait;

nr_iowait has cross CPU updates and would be subject to false sharing.

> +
> +	/*
> +	 * The following fields of clock data are frequently referenced
> +	 * and updated together, and should go on their own cache line.
> +	 */
>  	u64			clock_task ____cacheline_aligned;
>  	u64			clock_pelt;
> +	u64			clock;
>  	unsigned long		lost_idle_time;
> +	unsigned int		clock_update_flags;
>  	u64			clock_pelt_idle;
>  	u64			clock_idle;
> +
>  #ifndef CONFIG_64BIT
>  	u64			clock_pelt_idle_copy;
>  	u64			clock_idle_copy;
>  #endif
>  
> -	atomic_t		nr_iowait;
> -
>  	u64 last_seen_need_resched_ns;
>  	int ticks_without_resched;

Does the thing want a __no_randomize_layout ?

Re: [PATCH v3] sched: reorder some fields in struct rq

[Blake Jones]

[I thought I'd turned off HTML on my reply just now, but apparently not.
Sorry about that. Re-sending so the list has context...]

Hi Peter,

Thanks for your questions. Here are my thoughts:

On Tue, Oct 28, 2025 at 4:29 AM Peter Zijlstra <peterz@infradead.org> wrote:
> queue_mask is modified right along with nr_running -- every
> enqueue/dequeue. It seems weird to move it away from nr_running.

My main goal with this change is to optimize the first line for read-mostly
usage - specifically, for the loop in update_sg_lb_stats(), which loads
data from many rq's without locking them. Data from some Google fleet
profilers showed about 38x as many loads as stores to these fields.

From what I could tell from your patch, queue_mask is write-mostly -
enqueue_task() and dequeue_task() update it, and sched_balance_newidle()
stores to it and loads it later. That's why I didn't put it in the first
line.

That said, the place where I relocated it to is somewhat arbitrary. I
mostly put it there because it had some open space on that line, though
its new neighbors prev_mm and next_balance are also updated somewhat
frequently. If you have another suggestion I'm quite open to it.

> Does it not make more sense to put the lock in the same cacheline as the
> clock fields?

Great question. When I was first playing around with this reordering, I did
some more substantial movement within struct rq. But for the versions I've
sent out, I decided to keep it focused on just a few areas where I could
tell there was clustered usage. I didn't want to over-fit the placement of
a whole lot of fields in struct rq, since the code inevitably changes.

So I'd be open to moving the lock to the same line as the clock fields if
you think it would be a perf win, but I don't personally have any perf
numbers that could demonstrate the merits of doing that. WDYT?

> nr_iowait has cross CPU updates and would be subject to false sharing.

Mmm, good point. I moved it back before the clock-related cache line to
balance out moving "clock" and "clock_update_flags" to that line, since
otherwise it was going to add an extra line to the structure. But also,
it had been on the same line as the various clock fields, so that false
sharing was already not doing us any favors.

The line that I've moved it to has your queue_mask, so that's probably not
the best place. How about if I move it to the end of the structure, next to
cfsb_csd and cfsb_csd_list, since those don't seem to get used very often?

> Does the thing want a __no_randomize_layout ?

Well, this is by far one of the hottest kernel data structures we see at
Google, and it's not an obvious thing for a security vuln to target. So I'd
be quite happy to add __no_randomize_layout; if you agree, I'll add it.

Blake

Re: [PATCH v3] sched: reorder some fields in struct rq

[Peter Zijlstra]

On Tue, Oct 28, 2025 at 03:15:27PM -0700, Blake Jones wrote:
> Hi Peter,
> 
> Thanks for your questions. Here are my thoughts:
> 
> On Tue, Oct 28, 2025 at 4:29 AM Peter Zijlstra <peterz@infradead.org> wrote:
> 
> > queue_mask is modified right along with nr_running -- every
> > enqueue/dequeue. It seems weird to move it away from nr_running.
> >
> 
> My main goal with this change is to optimize the first line for read-mostly
> usage - specifically, for the loop in update_sg_lb_stats(), which loads
> data from many rq's without locking them. Data from some Google fleet
> profilers showed about 38x as many loads as stores to these fields.
> 
> From what I could tell from your patch, queue_mask is write-mostly -
> enqueue_task() and dequeue_task() update it, and sched_balance_newidle()
> stores to it and loads it later. That's why I didn't put it in the first
> line.
> 
> That said, the place where I relocated it to is somewhat arbitrary. I
> mostly put it there because it had some open space on that line, though
> its new neighbors prev_mm and next_balance are also updated somewhat
> frequently. If you have another suggestion I'm quite open to it.

Right. I missed the read-heavy part. It still feels somewhat weird to
split variables you know are modified together, but alas.

Also, I might be reworking/removing queue_mask again soon, we'll see if
that pans out.

> > Does it not make more sense to put the lock in the same cacheline as the
> > clock fields?
> >
> 
> Great question. When I was first playing around with this reordering, I did
> some more substantial movement within struct rq. But for the versions I've
> sent out, I decided to keep it focused on just a few areas where I could
> tell there was clustered usage. I didn't want to over-fit the placement of
> a whole lot of fields in struct rq, since the code inevitably changes.
> 
> So I'd be open to moving the lock to the same line as the clock fields if
> you think it would be a perf win, but I don't personally have any perf
> numbers that could demonstrate the merits of doing that. WDYT?

Most places that take rq->lock also update rq->clock. So I was wondering
if it made sense to put them together. I don't have numbers either.

> > nr_iowait has cross CPU updates and would be subject to false sharing.
> >
> 
> Mmm, good point. I moved it back before the clock-related cache line to
> balance out moving "clock" and "clock_update_flags" to that line, since
> otherwise it was going to add an extra line to the structure. But also,
> it had been on the same line as the various clock fields, so that false
> sharing was already not doing us any favors.
> 
> The line that I've moved it to has your queue_mask, so that's probably not
> the best place. How about if I move it to the end of the structure, next to
> cfsb_csd and cfsb_csd_list, since those don't seem to get used very often?

Works for me.

> > Does the thing want a __no_randomize_layout ?
> >
> 
> Well, this is by far one of the hottest kernel data structures we see at
> Google, and it's not an obvious thing for a security vuln to target. So I'd
> be quite happy to add __no_randomize_layout; if you agree, I'll add it.

Lets make it so.

Thanks!

Re: [PATCH v3] sched: reorder some fields in struct rq

[Blake Jones]

On Wed, Oct 29, 2025 at 2:14 AM Peter Zijlstra <peterz@infradead.org> wrote:
> Most places that take rq->lock also update rq->clock. So I was wondering
> if it made sense to put them together. I don't have numbers either.

Makes sense. I think I'll leave it out of this patch since I don't
have numbers for it, but it's an compelling enough idea that I might
try to get some numbers and come back with a followup.

> > The line that I've moved it to has your queue_mask, so that's probably not
> > the best place. How about if I move it to the end of the structure, next to
> > cfsb_csd and cfsb_csd_list, since those don't seem to get used very often?
>
> Works for me.

Great.

> > Well, this is by far one of the hottest kernel data structures we see at
> > Google, and it's not an obvious thing for a security vuln to target. So I'd
> > be quite happy to add __no_randomize_layout; if you agree, I'll add it.
>
> Lets make it so.

Done.

I've made these changes and fleshed out the comment at the top of the
structure a bit more, and I sent the result out as v4:
https://lore.kernel.org/lkml/20251029185458.3040228-1-blakejones@google.com/T/#u

Thanks.

Blake