Skip to contentSkip to conversation

rcu: Reduce rnp->lock contention with per-CPU blocked task lists

RFC PATCH In review Joel Fernandes 5 participants 34 messages Jan 3 – Jan 10

Subsystems (4)
lore
Share & tools
lore

Joel Fernandes

author maintainer
#0 lore raw

cover rcu: Reduce rnp->lock contention with per-CPU blocked task lists

When a task is preempted while holding an RCU read-side lock, the kernel must track it on the rcu_node's blocked task list. This requires acquiring rnp->lock shared by all CPUs in that node's subtree.

Posting this as RFC for early feedback. There could be bugs lurking, especially related to expedited GPs which I have not yet taken a close look at. Several TODOs are added. It passed light TREE03 rcutorture testing.

On systems with 16 or fewer CPUs, the RCU hierarchy often has just a single rcu_node, making rnp->lock effectively a global lock for all blocked task operations. Every context switch where a task holds an RCU read-side lock contends on this single lock.

Enter Virtualization
--------------------
In virtualized environments, the problem becomes dramatically worse due to vCPU preemption. Research from USENIX ATC'17 ("The RCU-Reader Preemption Problem in VMs" by Gopinath and Paul McKenney) [1] explores the issue that RCU reader preemption in VMs causes multi-second latency spikes and huge increases in grace period duration.

When a vCPU is preempted by the hypervisor while holding rnp->lock, other vCPUs spin waiting for a lock holder that isn't even running. In testing with host RT preemptors to inject vCPU preemption, lock hold times extended from ~4us to over 4000us - a 1000x increase.

The Solution
------------
This series introduces per-CPU lists for tracking blocked RCU readers. The key insight is that when no grace period is active, blocked tasks complete their critical sections before really requiring any rnp locking.

1. Fast path: At context switch, Add the task only to the per-CPU list - no rnp->lock needed.

2. Promotion on demand: When a grace period starts, promote tasks from per-CPU lists to the rcu_node list.

3. Normal path: If a grace period is already waiting, tasks go directly to the rcu_node list as before.

Results
-------
Testing with 64 reader threads under vCPU preemption from 32 host SCHED_FIFO preemptors), 100 runs each. Throughput measured of read lock/unlock iterations per second.

                        Baseline        Optimized
Mean throughput         66,980 iter/s   97,719 iter/s   (+46%)
Lock hold time (mean)   1,069 us        ~0 us

The optimized version maintains stable performance with essentially close to zero rnp->lock overhead.

rcutorture Testing
------------------
TREE03 Testing with rcutorture without RCU or hotplug errors. More testing is in progress.

Note: I have added a CONFIG_RCU_PER_CPU_BLOCKED_LISTS to guard the feature but the plan is to eventually turn this on all the time.

[1] https://www.usenix.org/conference/atc17/technical-sessions/presentation/prasad

Joel Fernandes (14):
rcu: Add WARN_ON_ONCE for blocked flag invariant in exit_rcu()
rcu: Add per-CPU blocked task lists for PREEMPT_RCU
rcu: Early return during unlock for tasks only on per-CPU blocked list
rcu: Promote blocked tasks from per-CPU to rnp lists
rcu: Promote blocked tasks for expedited GPs
rcu: Promote per-CPU blocked tasks before checking for blocked readers
rcu: Promote late-arriving blocked tasks before reporting QS
rcu: Promote blocked tasks before QS report in force_qs_rnp()
rcu: Promote blocked tasks before QS report in
rcutree_report_cpu_dead()
rcu: Promote blocked tasks before QS report in rcu_gp_init()
rcu: Add per-CPU blocked list check in exit_rcu()
rcu: Skip per-CPU list addition when GP already started
rcu: Skip rnp addition when no grace period waiting
rcu: Remove checking of per-cpu blocked list against the node list

 include/linux/sched.h    |   4 +
 kernel/fork.c            |   4 +
 kernel/rcu/Kconfig       |  12 +++
 kernel/rcu/tree.c        |  60 +++++++++--
 kernel/rcu/tree.h        |  11 +-
 kernel/rcu/tree_exp.h    |   5 +
 kernel/rcu/tree_plugin.h | 211 +++++++++++++++++++++++++++++++++++----
 kernel/rcu/tree_stall.h  |   4 +-
 8 files changed, 279 insertions(+), 32 deletions(-)

base-commit: f8f9c1f4d0c7a64600e2ca312dec824a0bc2f1da --
2.34.1

author maintainer
#1 lore raw

RFC PATCH 1/14 rcu: Add WARN_ON_ONCE for blocked flag invariant in exit_rcu()

If a task is on the rcu_node_entry list, its blocked flag should already be set (it's set before adding to any list in rcu_note_context_switch()). The current code silently re-sets it, which could mask bugs.

Add a WARN_ON_ONCE to detect this invariant violation. If this warning ever fires, it indicates a bug where a task was added to a blocked list without properly setting the blocked flag first.

---
 kernel/rcu/tree_plugin.h | 1 +
 1 file changed, 1 insertion(+)
kernel/rcu/tree_plugin.h +1 -0
index dbe2d02be824..73ba5f4a968d 100644
@@ -846,6 +846,7 @@ void exit_rcu(void)
 	if (unlikely(!list_empty(&current->rcu_node_entry))) {
 		rcu_preempt_depth_set(1);
 		barrier();
+		WARN_ON_ONCE(!t->rcu_read_unlock_special.b.blocked);
 		WRITE_ONCE(t->rcu_read_unlock_special.b.blocked, true);
 	} else if (unlikely(rcu_preempt_depth())) {
 		rcu_preempt_depth_set(1);
Signature · 1 line
2.34.1
#2 lore raw

Re: [PATCH RFC 01/14] rcu: Add WARN_ON_ONCE for blocked flag invariant in exit_rcu()

Quoted 14 lines · On Fri, 2 Jan 2026 19:23:30 -0500 Joel Fernandes <[email protected]> wrote:

Add a WARN_ON_ONCE to detect this invariant violation. If this warning ever fires, it indicates a bug where a task was added to a blocked list without properly setting the blocked flag first.

---
 kernel/rcu/tree_plugin.h | 1 +
 1 file changed, 1 insertion(+)
kernel/rcu/tree_plugin.h +0 -0
index dbe2d02be824..73ba5f4a968d 100644

kernel/rcu/tree_plugin.h void exit_rcu(void) · line 850

Quoted 5 lines
kernel/rcu/tree_plugin.h +1 -0
@@ -846,6 +846,7 @@ void exit_rcu(void)
 	if (unlikely(!list_empty(&current->rcu_node_entry))) {
 		rcu_preempt_depth_set(1);
 		barrier();
+		WARN_ON_ONCE(!t->rcu_read_unlock_special.b.blocked);
 		WRITE_ONCE(t->rcu_read_unlock_special.b.blocked, true);

If we warn when it is not set, could we just remove setting it? Or do:

		if (WARN_ON_ONCE(!t->rcu_read_unlock_special.b.blocked))
	 		WRITE_ONCE(t->rcu_read_unlock_special.b.blocked, true);

-- Steve

Quoted 3 lines
kernel/rcu/tree_plugin.h +0 -0
 	} else if (unlikely(rcu_preempt_depth())) {
 		rcu_preempt_depth_set(1);
author maintainer
#3 lore raw

Re: [PATCH RFC 01/14] rcu: Add WARN_ON_ONCE for blocked flag invariant in exit_rcu()

Quoted 12 lines · Steven Rostedt
Quoted 9 lines · On Fri, 2 Jan 2026 19:23:30 -0500 Joel Fernandes <[email protected]> wrote:

Add a WARN_ON_ONCE to detect this invariant violation. If this warning ever fires, it indicates a bug where a task was added to a blocked list without properly setting the blocked flag first.

---
 kernel/rcu/tree_plugin.h | 1 +
 1 file changed, 1 insertion(+)
Quoted 10 lines

kernel/rcu/tree_plugin.h void exit_rcu(void) · line 850

Quoted 10 lines
kernel/rcu/tree_plugin.h +1 -0
index dbe2d02be824..73ba5f4a968d 100644
@@ -846,6 +846,7 @@ void exit_rcu(void)
 	if (unlikely(!list_empty(&current->rcu_node_entry))) {
 		rcu_preempt_depth_set(1);
 		barrier();
+		WARN_ON_ONCE(!t->rcu_read_unlock_special.b.blocked);
 		WRITE_ONCE(t->rcu_read_unlock_special.b.blocked, true);

Right, so it is ever not set then we are trying to "right" a "wrong", so..

Quoted 6 lines

If we warn when it is not set, could we just remove setting it? Or do:

		if (WARN_ON_ONCE(!t->rcu_read_unlock_special.b.blocked))
	 		WRITE_ONCE(t->rcu_read_unlock_special.b.blocked, true);

.. we could just do this. I'll apply the suggestion, thanks!

- Joel

author maintainer
#4 lore raw

RFC PATCH 2/14 rcu: Add per-CPU blocked task lists for PREEMPT_RCU

In reply to Joel Fernandes

Add per-CPU tracking of tasks blocked in RCU read-side critical sections. Each rcu_data gets a blkd_list protected by blkd_lock, mirroring the rcu_node blkd_tasks list at per-CPU granularity.

Tasks are added on preemption and removed on rcu_read_unlock. A WARN_ON_ONCE in rcu_gp_init verifies list consistency.

---
 include/linux/sched.h    |  4 ++++
 kernel/fork.c            |  4 ++++
 kernel/rcu/Kconfig       | 12 ++++++++++++
 kernel/rcu/tree.c        | 32 ++++++++++++++++++++++++++++++++
 kernel/rcu/tree.h        |  6 ++++++
 kernel/rcu/tree_plugin.h | 21 +++++++++++++++++++++
 6 files changed, 79 insertions(+)
include/linux/sched.h +4 -0
index d395f2810fac..90ce501a568e 100644
@@ -931,6 +931,10 @@ struct task_struct {
 	union rcu_special		rcu_read_unlock_special;
 	struct list_head		rcu_node_entry;
 	struct rcu_node			*rcu_blocked_node;
+#ifdef CONFIG_RCU_PER_CPU_BLOCKED_LISTS
+	struct list_head		rcu_rdp_entry;
+	int				rcu_blocked_cpu;
+#endif
 #endif /* #ifdef CONFIG_PREEMPT_RCU */
 
 #ifdef CONFIG_TASKS_RCU
kernel/fork.c +4 -0
index b1f3915d5f8e..7a5ba2d2c1b5 100644
@@ -1819,6 +1819,10 @@ static inline void rcu_copy_process(struct task_struct *p)
 	p->rcu_read_unlock_special.s = 0;
 	p->rcu_blocked_node = NULL;
 	INIT_LIST_HEAD(&p->rcu_node_entry);
+#ifdef CONFIG_RCU_PER_CPU_BLOCKED_LISTS
+	INIT_LIST_HEAD(&p->rcu_rdp_entry);
+	p->rcu_blocked_cpu = -1;
+#endif
 #endif /* #ifdef CONFIG_PREEMPT_RCU */
 #ifdef CONFIG_TASKS_RCU
 	p->rcu_tasks_holdout = false;
kernel/rcu/Kconfig +12 -0
index 4d9b21f69eaa..4bb12f1fed09 100644
@@ -248,6 +248,18 @@ config RCU_EXP_KTHREAD
 
 	  Accept the default if unsure.
 
+config RCU_PER_CPU_BLOCKED_LISTS
+	bool "Use per-CPU blocked task lists in PREEMPT_RCU"
+	depends on PREEMPT_RCU
+	default n
+	help
+	  Enable per-CPU tracking of tasks blocked in RCU read-side
+	  critical sections. This allows to quickly toggle the feature.
+	  Eventually the config will be removed, in favor of always keeping
+	  the optimization enabled.
+
+	  Accept the default if unsure.
+
 config RCU_NOCB_CPU
 	bool "Offload RCU callback processing from boot-selected CPUs"
 	depends on TREE_RCU
kernel/rcu/tree.c +32 -0
index 293bbd9ac3f4..e2b6a4579086 100644
@@ -1809,6 +1809,14 @@ static noinline_for_stack bool rcu_gp_init(void)
 	struct rcu_node *rnp = rcu_get_root();
 	bool start_new_poll;
 	unsigned long old_gp_seq;
+#ifdef CONFIG_RCU_PER_CPU_BLOCKED_LISTS
+	struct task_struct *t_verify;
+	int cpu_verify;
+	int rnp_count;
+	int rdp_total;
+	struct rcu_data *rdp_cpu;
+	struct task_struct *t_rdp;
+#endif
 
 	WRITE_ONCE(rcu_state.gp_activity, jiffies);
 	raw_spin_lock_irq_rcu_node(rnp);
@@ -1891,6 +1899,26 @@ static noinline_for_stack bool rcu_gp_init(void)
 		 */
 		arch_spin_lock(&rcu_state.ofl_lock);
 		raw_spin_lock_rcu_node(rnp);
+#ifdef CONFIG_RCU_PER_CPU_BLOCKED_LISTS
+		/*
+		 * Verify rdp lists consistent with rnp list. Since the unlock
+		 * path removes from rdp before rnp, we can have tasks that are
+		 * on rnp but not on rdp (in the middle of being removed).
+		 * Therefore rnp_count >= rdp_total is the expected invariant.
+		 */
+		rnp_count = 0;
+		rdp_total = 0;
+		list_for_each_entry(t_verify, &rnp->blkd_tasks, rcu_node_entry)
+			rnp_count++;
+		for (cpu_verify = rnp->grplo; cpu_verify <= rnp->grphi; cpu_verify++) {
+			rdp_cpu = per_cpu_ptr(&rcu_data, cpu_verify);
+			raw_spin_lock(&rdp_cpu->blkd_lock);
+			list_for_each_entry(t_rdp, &rdp_cpu->blkd_list, rcu_rdp_entry)
+				rdp_total++;
+			raw_spin_unlock(&rdp_cpu->blkd_lock);
+		}
+		WARN_ON_ONCE(rnp_count < rdp_total);
+#endif
 		if (rnp->qsmaskinit == rnp->qsmaskinitnext &&
 		    !rnp->wait_blkd_tasks) {
 			/* Nothing to do on this leaf rcu_node structure. */
@@ -4143,6 +4171,10 @@ rcu_boot_init_percpu_data(int cpu)
 	rdp->rcu_onl_gp_state = RCU_GP_CLEANED;
 	rdp->last_sched_clock = jiffies;
 	rdp->cpu = cpu;
+#ifdef CONFIG_RCU_PER_CPU_BLOCKED_LISTS
+	raw_spin_lock_init(&rdp->blkd_lock);
+	INIT_LIST_HEAD(&rdp->blkd_list);
+#endif
 	rcu_boot_init_nocb_percpu_data(rdp);
 }
 
kernel/rcu/tree.h +6 -0
index b8bbe7960cda..13d5649a80fb 100644
@@ -294,6 +294,12 @@ struct rcu_data {
 
 	long lazy_len;			/* Length of buffered lazy callbacks. */
 	int cpu;
+
+#ifdef CONFIG_RCU_PER_CPU_BLOCKED_LISTS
+	/* 8) Per-CPU blocked task tracking. */
+	raw_spinlock_t blkd_lock;	/* Protects blkd_list. */
+	struct list_head blkd_list;	/* Tasks blocked on this CPU. */
+#endif
 };
 
 /* Values for nocb_defer_wakeup field in struct rcu_data. */
kernel/rcu/tree_plugin.h +21 -0
index 73ba5f4a968d..5d2bde19131a 100644
@@ -338,6 +338,12 @@ void rcu_note_context_switch(bool preempt)
 		raw_spin_lock_rcu_node(rnp);
 		t->rcu_read_unlock_special.b.blocked = true;
 		t->rcu_blocked_node = rnp;
+#ifdef CONFIG_RCU_PER_CPU_BLOCKED_LISTS
+		t->rcu_blocked_cpu = rdp->cpu;
+		raw_spin_lock(&rdp->blkd_lock);
+		list_add(&t->rcu_rdp_entry, &rdp->blkd_list);
+		raw_spin_unlock(&rdp->blkd_lock);
+#endif
 
 		/*
 		 * Verify the CPU's sanity, trace the preemption, and
@@ -485,6 +491,10 @@ rcu_preempt_deferred_qs_irqrestore(struct task_struct *t, unsigned long flags)
 	struct rcu_data *rdp;
 	struct rcu_node *rnp;
 	union rcu_special special;
+#ifdef CONFIG_RCU_PER_CPU_BLOCKED_LISTS
+	int blocked_cpu;
+	struct rcu_data *blocked_rdp;
+#endif
 
 	rdp = this_cpu_ptr(&rcu_data);
 	if (rdp->defer_qs_iw_pending == DEFER_QS_PENDING)
@@ -530,6 +540,17 @@ rcu_preempt_deferred_qs_irqrestore(struct task_struct *t, unsigned long flags)
 		 * to loop.  Retain a WARN_ON_ONCE() out of sheer paranoia.
 		 */
 		rnp = t->rcu_blocked_node;
+#ifdef CONFIG_RCU_PER_CPU_BLOCKED_LISTS
+		/* Remove from per-CPU list if task was added to it. */
+		blocked_cpu = t->rcu_blocked_cpu;
+		if (blocked_cpu != -1) {
+			blocked_rdp = per_cpu_ptr(&rcu_data, blocked_cpu);
+			raw_spin_lock(&blocked_rdp->blkd_lock);
+			list_del_init(&t->rcu_rdp_entry);
+			t->rcu_blocked_cpu = -1;
+			raw_spin_unlock(&blocked_rdp->blkd_lock);
+		}
+#endif
 		raw_spin_lock_rcu_node(rnp); /* irqs already disabled. */
 		WARN_ON_ONCE(rnp != t->rcu_blocked_node);
 		WARN_ON_ONCE(!rcu_is_leaf_node(rnp));
Signature · 1 line
2.34.1
#5 lore raw

Re: [PATCH RFC 02/14] rcu: Add per-CPU blocked task lists for PREEMPT_RCU

kernel/rcu/Kconfig config RCU_EXP_KTHREAD · line 255

Quoted 11 lines · On Fri, 2 Jan 2026 19:23:31 -0500 Joel Fernandes <[email protected]> wrote:
kernel/rcu/Kconfig +4 -0
@@ -248,6 +248,18 @@ config RCU_EXP_KTHREAD
 
 	  Accept the default if unsure.
 
+config RCU_PER_CPU_BLOCKED_LISTS
+	bool "Use per-CPU blocked task lists in PREEMPT_RCU"
+	depends on PREEMPT_RCU
 
+	default n

nit, you don't need "default n". The default for options without defining a default setting is "n".

kernel/rcu/Kconfig config RCU_EXP_KTHREAD · line 261

Quoted 7 lines
kernel/rcu/Kconfig +7 -0
+	help
+	  Enable per-CPU tracking of tasks blocked in RCU read-side
+	  critical sections. This allows to quickly toggle the feature.
+	  Eventually the config will be removed, in favor of always keeping
+	  the optimization enabled.
+
+	  Accept the default if unsure.

Hmm, RCU is the only place that says "Accept the default". That would usually be for non boolean values (for numbers). But it should say either "Say N if unsure" or "Say Y if unsure".

Quoted 36 lines
kernel/rcu/Kconfig +1 -0
+
 config RCU_NOCB_CPU
 	bool "Offload RCU callback processing from boot-selected CPUs"
kernel/rcu/Kconfig +0 -0
 	depends on TREE_RCU
kernel/rcu/tree.c +17 -0
index 293bbd9ac3f4..e2b6a4579086 100644
@@ -1809,6 +1809,14 @@ static noinline_for_stack bool rcu_gp_init(void)
 	struct rcu_node *rnp = rcu_get_root();
 	bool start_new_poll;
 	unsigned long old_gp_seq;
+#ifdef CONFIG_RCU_PER_CPU_BLOCKED_LISTS
+	struct task_struct *t_verify;
+	int cpu_verify;
+	int rnp_count;
+	int rdp_total;
+	struct rcu_data *rdp_cpu;
+	struct task_struct *t_rdp;
+#endif
 
 	WRITE_ONCE(rcu_state.gp_activity, jiffies);
 	raw_spin_lock_irq_rcu_node(rnp);
@@ -1891,6 +1899,26 @@ static noinline_for_stack bool rcu_gp_init(void)
 		 */
 		arch_spin_lock(&rcu_state.ofl_lock);
 		raw_spin_lock_rcu_node(rnp);
+#ifdef CONFIG_RCU_PER_CPU_BLOCKED_LISTS
+		/*
+		 * Verify rdp lists consistent with rnp list. Since the unlock
+		 * path removes from rdp before rnp, we can have tasks that are
+		 * on rnp but not on rdp (in the middle of being removed).
+		 * Therefore rnp_count >= rdp_total is the expected invariant.
+		 */
+		rnp_count = 0;
+		rdp_total = 0;

kernel/rcu/tree.c static noinline_for_stack bool rcu_gp_init(void) · line 1920

Quoted 10 lines
kernel/rcu/tree.c +10 -0
+		list_for_each_entry(t_verify, &rnp->blkd_tasks, rcu_node_entry)
+			rnp_count++;
+		for (cpu_verify = rnp->grplo; cpu_verify <= rnp->grphi; cpu_verify++) {
+			rdp_cpu = per_cpu_ptr(&rcu_data, cpu_verify);
+			raw_spin_lock(&rdp_cpu->blkd_lock);
+			list_for_each_entry(t_rdp, &rdp_cpu->blkd_list, rcu_rdp_entry)
+				rdp_total++;
+			raw_spin_unlock(&rdp_cpu->blkd_lock);
+		}
+		WARN_ON_ONCE(rnp_count < rdp_total);

This only happens at boot right? This isn't something that executes at normal run time right? Otherwise I would be worried about loops like this under raw spin locks that could affect RT.

Quoted 37 lines
kernel/rcu/tree.c +5 -0
+#endif
 		if (rnp->qsmaskinit == rnp->qsmaskinitnext &&
 		    !rnp->wait_blkd_tasks) {
 			/* Nothing to do on this leaf rcu_node structure. */
@@ -4143,6 +4171,10 @@ rcu_boot_init_percpu_data(int cpu)
 	rdp->rcu_onl_gp_state = RCU_GP_CLEANED;
 	rdp->last_sched_clock = jiffies;
 	rdp->cpu = cpu;
+#ifdef CONFIG_RCU_PER_CPU_BLOCKED_LISTS
+	raw_spin_lock_init(&rdp->blkd_lock);
+	INIT_LIST_HEAD(&rdp->blkd_list);
+#endif
 	rcu_boot_init_nocb_percpu_data(rdp);
 }
 
kernel/rcu/tree.h +6 -0
index b8bbe7960cda..13d5649a80fb 100644
@@ -294,6 +294,12 @@ struct rcu_data {
 
 	long lazy_len;			/* Length of buffered lazy callbacks. */
 	int cpu;
+
+#ifdef CONFIG_RCU_PER_CPU_BLOCKED_LISTS
+	/* 8) Per-CPU blocked task tracking. */
+	raw_spinlock_t blkd_lock;	/* Protects blkd_list. */
+	struct list_head blkd_list;	/* Tasks blocked on this CPU. */
+#endif
 };
 
 /* Values for nocb_defer_wakeup field in struct rcu_data. */
kernel/rcu/tree_plugin.h +0 -0
index 73ba5f4a968d..5d2bde19131a 100644

kernel/rcu/tree_plugin.h void rcu_note_context_switch(bool preempt) · line 345

Quoted 8 lines
kernel/rcu/tree_plugin.h +5 -0
@@ -338,6 +338,12 @@ void rcu_note_context_switch(bool preempt)
 		raw_spin_lock_rcu_node(rnp);
 		t->rcu_read_unlock_special.b.blocked = true;
 		t->rcu_blocked_node = rnp;
+#ifdef CONFIG_RCU_PER_CPU_BLOCKED_LISTS
+		t->rcu_blocked_cpu = rdp->cpu;
+		raw_spin_lock(&rdp->blkd_lock);
+		list_add(&t->rcu_rdp_entry, &rdp->blkd_list);
+		raw_spin_unlock(&rdp->blkd_lock);

Should we use scoped_guard?

		scoped_guard(raw_spinlock, &rdp->blkd_lock) {
			list_add(&t->rcu_rdp_entry, &rdp->blkd_list);
		}
Quoted 16 lines
kernel/rcu/tree_plugin.h +5 -0
+#endif
 
 		/*
 		 * Verify the CPU's sanity, trace the preemption, and
@@ -485,6 +491,10 @@ rcu_preempt_deferred_qs_irqrestore(struct task_struct *t, unsigned long flags)
 	struct rcu_data *rdp;
 	struct rcu_node *rnp;
 	union rcu_special special;
+#ifdef CONFIG_RCU_PER_CPU_BLOCKED_LISTS
+	int blocked_cpu;
+	struct rcu_data *blocked_rdp;
+#endif
 
 	rdp = this_cpu_ptr(&rcu_data);
 	if (rdp->defer_qs_iw_pending == DEFER_QS_PENDING)

kernel/rcu/tree_plugin.h rcu_preempt_deferred_qs_irqrestore(struct task_struct *t, unsigned long flags) · line 545

Quoted 6 lines
kernel/rcu/tree_plugin.h +3 -0
@@ -530,6 +540,17 @@ rcu_preempt_deferred_qs_irqrestore(struct task_struct *t, unsigned long flags)
 		 * to loop.  Retain a WARN_ON_ONCE() out of sheer paranoia.
 		 */
 		rnp = t->rcu_blocked_node;
+#ifdef CONFIG_RCU_PER_CPU_BLOCKED_LISTS
+		/* Remove from per-CPU list if task was added to it. */
+		blocked_cpu = t->rcu_blocked_cpu;

And use guard here?

		if (blocked_cpu != -1) {
			blocked_rdp = per_cpu_ptr(&rcu_data, blocked_cpu);
			guard(raw_spin_lock)(&blocked_rdp->blkd_lock);
			list_del_init(&t->rcu_rdp_entry);
			t->rcu_blocked_cpu = -1;
		}

-- Steve

Quoted 5 lines
kernel/rcu/tree_plugin.h +2 -0
+		}
+#endif
 		raw_spin_lock_rcu_node(rnp); /* irqs already disabled. */
 		WARN_ON_ONCE(rnp != t->rcu_blocked_node);
 		WARN_ON_ONCE(!rcu_is_leaf_node(rnp));
author maintainer
#6 lore raw

RFC PATCH 3/14 rcu: Early return during unlock for tasks only on per-CPU blocked list

In reply to Joel Fernandes

Add a check for t->rcu_blocked_node being NULL after removing the task from the per-CPU blocked list. If NULL, the task was only on the per-CPU list and not on the rcu_node's blkd_tasks list, so we can skip all the rnp lock acquisition and quiescent state reporting.

Currently this path is not taken since tasks are always added to both lists. This prepares for a future optimization where tasks will initially be added only to the per-CPU list and promoted to the rnp list only when a grace period needs to wait for them.

---
 kernel/rcu/tree_plugin.h | 16 ++++++++++++++++
 1 file changed, 16 insertions(+)
kernel/rcu/tree_plugin.h +16 -0
index 5d2bde19131a..ee26e87c72f8 100644
@@ -549,6 +549,22 @@ rcu_preempt_deferred_qs_irqrestore(struct task_struct *t, unsigned long flags)
 			list_del_init(&t->rcu_rdp_entry);
 			t->rcu_blocked_cpu = -1;
 			raw_spin_unlock(&blocked_rdp->blkd_lock);
+			/*
+			 * TODO: This should just be "WARN_ON_ONCE(rnp); return;" since after
+			 * the last patches, the task can only be in either the rdp or the rnp
+			 * list, not both. Since blocked_cpu != -1, it is clearly not in the rnp
+			 * so we activate the benefits of this patchset by removing the task
+			 * from the rdp blocked list and early returning.
+			 */
+			if (!rnp) {
+				/*
+				 * Task was only on per-CPU list, not on rnp list.
+				 * This can happen in future when tasks are added
+				 * only to rdp initially and promoted to rnp later.
+				 */
+				local_irq_restore(flags);
+				return;
+			}
 		}
 #endif
 		raw_spin_lock_rcu_node(rnp); /* irqs already disabled. */
Signature · 1 line
2.34.1
author maintainer
#7 lore raw

RFC PATCH 4/14 rcu: Promote blocked tasks from per-CPU to rnp lists

In reply to Joel Fernandes

Add rcu_promote_blocked_tasks() helper that moves blocked tasks from per-CPU rdp->blkd_list to the rcu_node's blkd_tasks list during grace period initialization. This is a prerequisite for deferring rnp list addition until gp_init.

---
 kernel/rcu/tree.c        |  2 +
 kernel/rcu/tree_plugin.h | 80 ++++++++++++++++++++++++++++++++++++++++
 2 files changed, 82 insertions(+)
kernel/rcu/tree.c +2 -0
index e2b6a4579086..5837e9923642 100644
@@ -1899,6 +1899,7 @@ static noinline_for_stack bool rcu_gp_init(void)
 		 */
 		arch_spin_lock(&rcu_state.ofl_lock);
 		raw_spin_lock_rcu_node(rnp);
+		rcu_promote_blocked_tasks(rnp);
 #ifdef CONFIG_RCU_PER_CPU_BLOCKED_LISTS
 		/*
 		 * Verify rdp lists consistent with rnp list. Since the unlock
@@ -1982,6 +1983,7 @@ static noinline_for_stack bool rcu_gp_init(void)
 		rcu_gp_slow(gp_init_delay);
 		raw_spin_lock_irqsave_rcu_node(rnp, flags);
 		rdp = this_cpu_ptr(&rcu_data);
+		rcu_promote_blocked_tasks(rnp);
 		rcu_preempt_check_blocked_tasks(rnp);
 		rnp->qsmask = rnp->qsmaskinit;
 		WRITE_ONCE(rnp->gp_seq, rcu_state.gp_seq);
kernel/rcu/tree_plugin.h +80 -0

92 lines not on this page · raw message

Signature · 1 line
2.34.1
#8 lore raw

Re: [PATCH RFC 04/14] rcu: Promote blocked tasks from per-CPU to rnp lists

Quoted 9 lines · On Fri, 2 Jan 2026 19:23:33 -0500 Joel Fernandes <[email protected]> wrote:
kernel/rcu/tree_plugin.h +9 -0
+#ifdef CONFIG_RCU_PER_CPU_BLOCKED_LISTS
+/*
+ * Promote blocked tasks from a single CPU's per-CPU list to the rnp list.
+ *
+ * If there are no tracked blockers (gp_tasks NULL) and this CPU
+ * is still blocking the corresponding GP (bit set in qsmask), set
+ * the pointer to ensure the GP machinery knows about the blocking task.
+ * This handles late promotion during QS reporting, where tasks may have
+ * blocked after rcu_gp_init() or sync_exp_reset_tree() ran their scans.

kernel/rcu/tree_plugin.h static void rcu_read_unlock_special(struct task_struct *t) · line 827

Quoted 10 lines
kernel/rcu/tree_plugin.h +10 -0
+ */
+static void rcu_promote_blocked_tasks_rdp(struct rcu_data *rdp,
+					  struct rcu_node *rnp)
+{
+	struct task_struct *t, *tmp;
+
+	raw_lockdep_assert_held_rcu_node(rnp);
+
+	raw_spin_lock(&rdp->blkd_lock);
+	list_for_each_entry_safe(t, tmp, &rdp->blkd_list, rcu_rdp_entry) {

How big can this list be? This would be considered an unbounded latency for PREEMPT_RT. If this is needed, then we need to disable this when PREEMPT_RT is enabled.

-- Steve

Quoted 6 lines
kernel/rcu/tree_plugin.h +6 -0
+		/*
+		 * Skip tasks already on rnp list. A non-NULL
+		 * rcu_blocked_node indicates the task was already
+		 * promoted or added directly during blocking.
+		 * TODO: Should be WARN_ON_ONCE() after the last patch?
+		 */
#9 lore raw

Re: [PATCH RFC 04/14] rcu: Promote blocked tasks from per-CPU to rnp lists

Quoted 18 lines · Steven Rostedt
Quoted 15 lines · On Fri, 2 Jan 2026 19:23:33 -0500 Joel Fernandes <[email protected]> wrote:
kernel/rcu/tree_plugin.h +15 -0
+#ifdef CONFIG_RCU_PER_CPU_BLOCKED_LISTS
+/*
+ * Promote blocked tasks from a single CPU's per-CPU list to the rnp list.
+ *
+ * If there are no tracked blockers (gp_tasks NULL) and this CPU
+ * is still blocking the corresponding GP (bit set in qsmask), set
+ * the pointer to ensure the GP machinery knows about the blocking task.
+ * This handles late promotion during QS reporting, where tasks may have
+ * blocked after rcu_gp_init() or sync_exp_reset_tree() ran their scans.
+ */
+static void rcu_promote_blocked_tasks_rdp(struct rcu_data *rdp,
+					  struct rcu_node *rnp)
+{
+	struct task_struct *t, *tmp;
+
Quoted 8 lines

kernel/rcu/tree_plugin.h static void rcu_read_unlock_special(struct task_struct *t) · line 827

Quoted 4 lines
kernel/rcu/tree_plugin.h +4 -0
+	raw_lockdep_assert_held_rcu_node(rnp);
+
+	raw_spin_lock(&rdp->blkd_lock);
+	list_for_each_entry_safe(t, tmp, &rdp->blkd_list, rcu_rdp_entry) {

How big can this list be? This would be considered an unbounded latency for PREEMPT_RT. If this is needed, then we need to disable this when PREEMPT_RT is enabled.

Steve, thanks. This is still quite a bit in the experimental/RFC phase, but if we ever were to do this, we could splice the list of tasks into O(1) instead of O(N) I am doing here. Great point.

Thanks for the suggestions about the guards as well on the other patch, I shall use that where possible in any of my new code.

thanks,

- Joel

author maintainer
#10 lore raw

RFC PATCH 5/14 rcu: Promote blocked tasks for expedited GPs

In reply to Joel Fernandes

Add a call to rcu_promote_blocked_tasks() in sync_exp_reset_tree() before checking for blocked tasks. This ensures that expedited grace periods properly wait for tasks that were blocked on per-CPU lists before the expedited GP was initiated.

---
 kernel/rcu/tree.h        | 1 +
 kernel/rcu/tree_exp.h    | 5 +++++
 kernel/rcu/tree_plugin.h | 8 +++++---
 3 files changed, 11 insertions(+), 3 deletions(-)
kernel/rcu/tree.h +1 -0
index 13d5649a80fb..b71c6c1de8d3 100644
@@ -501,6 +501,7 @@ static bool rcu_is_callbacks_kthread(struct rcu_data *rdp);
 static void rcu_cpu_kthread_setup(unsigned int cpu);
 static void rcu_spawn_one_boost_kthread(struct rcu_node *rnp);
 static bool rcu_preempt_has_tasks(struct rcu_node *rnp);
+static void rcu_promote_blocked_tasks(struct rcu_node *rnp);
 static bool rcu_preempt_need_deferred_qs(struct task_struct *t);
 static void zero_cpu_stall_ticks(struct rcu_data *rdp);
 static struct swait_queue_head *rcu_nocb_gp_get(struct rcu_node *rnp);
kernel/rcu/tree_exp.h +5 -0
index 96c49c56fc14..f6cb0e3147c4 100644
@@ -141,6 +141,11 @@ static void __maybe_unused sync_exp_reset_tree(void)
 		raw_spin_lock_irqsave_rcu_node(rnp, flags);
 		WARN_ON_ONCE(rnp->expmask);
 		WRITE_ONCE(rnp->expmask, rnp->expmaskinit);
+		/*
+		 * Promote tasks from per-CPU lists before checking blkd_tasks.
+		 * This ensures expedited GPs see tasks blocked.
+		 */
+		rcu_promote_blocked_tasks(rnp);
 		/*
 		 * Need to wait for any blocked tasks as well.	Note that
 		 * additional blocking tasks will also block the expedited GP
kernel/rcu/tree_plugin.h +5 -3
index 6810f1b72d2a..ad33fdd0efe8 100644
@@ -810,8 +810,8 @@ static void rcu_read_unlock_special(struct task_struct *t)
 /*
  * Promote blocked tasks from a single CPU's per-CPU list to the rnp list.
  *
- * If there are no tracked blockers (gp_tasks NULL) and this CPU
- * is still blocking the corresponding GP (bit set in qsmask), set
+ * If there are no tracked blockers (gp_tasks/exp_tasks NULL) and this CPU
+ * is still blocking the corresponding GP (bit set in qsmask/expmask), set
  * the pointer to ensure the GP machinery knows about the blocking task.
  * This handles late promotion during QS reporting, where tasks may have
  * blocked after rcu_gp_init() or sync_exp_reset_tree() ran their scans.
@@ -844,11 +844,13 @@ static void rcu_promote_blocked_tasks_rdp(struct rcu_data *rdp,
 		t->rcu_blocked_cpu = -1;
 
 		/*
-		 * Set gp_tasks if this is the first blocker and
+		 * Set gp_tasks/exp_tasks if this is the first blocker and
 		 * this CPU is still blocking the corresponding GP.
 		 */
 		if (!rnp->gp_tasks && (rnp->qsmask & rdp->grpmask))
 			WRITE_ONCE(rnp->gp_tasks, &t->rcu_node_entry);
+		if (!rnp->exp_tasks && (rnp->expmask & rdp->grpmask))
+			WRITE_ONCE(rnp->exp_tasks, &t->rcu_node_entry);
 	}
 	raw_spin_unlock(&rdp->blkd_lock);
 }
Signature · 1 line
2.34.1
author maintainer
#11 lore raw

RFC PATCH 6/14 rcu: Promote per-CPU blocked tasks before checking for blocked readers

In reply to Joel Fernandes

When CONFIG_RCU_PER_CPU_BLOCKED_LISTS is enabled, tasks that block in RCU read-side critical sections may be placed on per-CPU lists rather than directly on the rcu_node's blkd_tasks list. It is possible that a task can block just after rcu_gp_init()'s promotion scan completes, leaving it only on the per-CPU list while a GP is active.

The RCU priority boosting mechanism only looks at rnp->gp_tasks and rnp->exp_tasks, which point into rnp->blkd_tasks. Tasks on per-CPU lists are invisible to the boost kthread and cannot be boosted.

Address this by adding a "promote" parameter to rcu_preempt_blocked_readers_cgp(). When promote is true and the caller the function first promotes any tasks from per-CPU blocked lists to the rcu_node's blkd_tasks list before checking if there are blocked readers. This ensures that late-arriving tasks are visible for priority boosting and other operations.

Callers that hold the rnp lock pass promote=true to get an accurate answer including late arrivals. Lockless callers (GP loop, FQS check) pass promote=false for an approximate snapshot (TODO: need to check if we can always just set "promote" to true and remove the parameter).

---
 kernel/rcu/tree.c        | 14 +++++++-------
 kernel/rcu/tree.h        |  2 +-
 kernel/rcu/tree_plugin.h | 34 ++++++++++++++++++++++++++++------
 kernel/rcu/tree_stall.h  |  4 ++--
 4 files changed, 38 insertions(+), 16 deletions(-)
kernel/rcu/tree.c +7 -7
index 5837e9923642..f8f43f94adbb 100644
@@ -2034,7 +2034,7 @@ static bool rcu_gp_fqs_check_wake(int *gfp)
 		return true;
 
 	// The current grace period has completed.
-	if (!READ_ONCE(rnp->qsmask) && !rcu_preempt_blocked_readers_cgp(rnp))
+	if (!READ_ONCE(rnp->qsmask) && !rcu_preempt_blocked_readers_cgp(rnp, false))
 		return true;
 
 	return false;
@@ -2125,7 +2125,7 @@ static noinline_for_stack void rcu_gp_fqs_loop(void)
 		 * the corresponding leaf nodes have passed through their quiescent state.
 		 */
 		if (!READ_ONCE(rnp->qsmask) &&
-		    !rcu_preempt_blocked_readers_cgp(rnp))
+		    !rcu_preempt_blocked_readers_cgp(rnp, false))
 			break;
 		/* If time for quiescent-state forcing, do it. */
 		if (!time_after(rcu_state.jiffies_force_qs, jiffies) ||
@@ -2207,7 +2207,7 @@ static noinline void rcu_gp_cleanup(void)
 	rcu_seq_end(&new_gp_seq);
 	rcu_for_each_node_breadth_first(rnp) {
 		raw_spin_lock_irq_rcu_node(rnp);
-		if (WARN_ON_ONCE(rcu_preempt_blocked_readers_cgp(rnp)))
+		if (WARN_ON_ONCE(rcu_preempt_blocked_readers_cgp(rnp, true)))
 			dump_blkd_tasks(rnp, 10);
 		WARN_ON_ONCE(rnp->qsmask);
 		WRITE_ONCE(rnp->gp_seq, new_gp_seq);
@@ -2376,13 +2376,13 @@ static void rcu_report_qs_rnp(unsigned long mask, struct rcu_node *rnp,
 		}
 		WARN_ON_ONCE(oldmask); /* Any child must be all zeroed! */
 		WARN_ON_ONCE(!rcu_is_leaf_node(rnp) &&
-			     rcu_preempt_blocked_readers_cgp(rnp));
+			     rcu_preempt_blocked_readers_cgp(rnp, true));
 		WRITE_ONCE(rnp->qsmask, rnp->qsmask & ~mask);
 		trace_rcu_quiescent_state_report(rcu_state.name, rnp->gp_seq,
 						 mask, rnp->qsmask, rnp->level,
 						 rnp->grplo, rnp->grphi,
 						 !!rnp->gp_tasks);
-		if (rnp->qsmask != 0 || rcu_preempt_blocked_readers_cgp(rnp)) {
+		if (rnp->qsmask != 0 || rcu_preempt_blocked_readers_cgp(rnp, true)) {
 
 			/* Other bits still set at this level, so done. */
 			raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
@@ -2428,7 +2428,7 @@ rcu_report_unblock_qs_rnp(struct rcu_node *rnp, unsigned long flags)
 
 	raw_lockdep_assert_held_rcu_node(rnp);
 	if (WARN_ON_ONCE(!IS_ENABLED(CONFIG_PREEMPT_RCU)) ||
-	    WARN_ON_ONCE(rcu_preempt_blocked_readers_cgp(rnp)) ||
+	    WARN_ON_ONCE(rcu_preempt_blocked_readers_cgp(rnp, true)) ||
 	    rnp->qsmask != 0) {
 		raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
 		return;  /* Still need more quiescent states! */
@@ -2763,7 +2763,7 @@ static void force_qs_rnp(int (*f)(struct rcu_data *rdp))
 		raw_spin_lock_irqsave_rcu_node(rnp, flags);
 		rcu_state.cbovldnext |= !!rnp->cbovldmask;
 		if (rnp->qsmask == 0) {
-			if (rcu_preempt_blocked_readers_cgp(rnp)) {
+			if (rcu_preempt_blocked_readers_cgp(rnp, true)) {
 				/*
 				 * No point in scanning bits because they
 				 * are all zero.  But we might need to
kernel/rcu/tree.h +1 -1
index b71c6c1de8d3..25eb9200e6ef 100644
@@ -486,7 +486,7 @@ static const char *tp_rcu_varname __used __tracepoint_string = rcu_name;
 /* Forward declarations for tree_plugin.h */
 static void rcu_bootup_announce(void);
 static void rcu_qs(void);
-static int rcu_preempt_blocked_readers_cgp(struct rcu_node *rnp);
+static int rcu_preempt_blocked_readers_cgp(struct rcu_node *rnp, bool promote);
 #ifdef CONFIG_HOTPLUG_CPU
 static bool rcu_preempt_has_tasks(struct rcu_node *rnp);
 #endif /* #ifdef CONFIG_HOTPLUG_CPU */
kernel/rcu/tree_plugin.h +28 -6
index ad33fdd0efe8..6ed3815bb912 100644
@@ -383,9 +383,28 @@ EXPORT_SYMBOL_GPL(rcu_note_context_switch);
  * Check for preempted RCU readers blocking the current grace period
  * for the specified rcu_node structure.  If the caller needs a reliable
  * answer, it must hold the rcu_node's ->lock.
+ *
+ * If @promote is true and CONFIG_RCU_PER_CPU_BLOCKED_LISTS is enabled,
+ * this function first promotes any tasks from per-CPU blocked lists to
+ * the rcu_node's blkd_tasks list before checking.  This ensures that
+ * late-arriving tasks (blocked after GP init's promotion scan) are
+ * visible for priority boosting and other operations.  When promoting,
+ * the caller must hold rnp->lock.
  */
-static int rcu_preempt_blocked_readers_cgp(struct rcu_node *rnp)
+static int rcu_preempt_blocked_readers_cgp(struct rcu_node *rnp, bool promote)
 {
+#ifdef CONFIG_RCU_PER_CPU_BLOCKED_LISTS
+	if (promote && rcu_is_leaf_node(rnp)) {
+		int cpu;
+		struct rcu_data *rdp;
+
+		raw_lockdep_assert_held_rcu_node(rnp);
+		for (cpu = rnp->grplo; cpu <= rnp->grphi; cpu++) {
+			rdp = per_cpu_ptr(&rcu_data, cpu);
+			rcu_promote_blocked_tasks_rdp(rdp, rnp);
+		}
+	}
+#endif
 	return READ_ONCE(rnp->gp_tasks) != NULL;
 }
 
@@ -570,7 +589,7 @@ rcu_preempt_deferred_qs_irqrestore(struct task_struct *t, unsigned long flags)
 		raw_spin_lock_rcu_node(rnp); /* irqs already disabled. */
 		WARN_ON_ONCE(rnp != t->rcu_blocked_node);
 		WARN_ON_ONCE(!rcu_is_leaf_node(rnp));
-		empty_norm = !rcu_preempt_blocked_readers_cgp(rnp);
+		empty_norm = !rcu_preempt_blocked_readers_cgp(rnp, true);
 		WARN_ON_ONCE(rnp->completedqs == rnp->gp_seq &&
 			     (!empty_norm || rnp->qsmask));
 		empty_exp = sync_rcu_exp_done(rnp);
@@ -597,7 +616,7 @@ rcu_preempt_deferred_qs_irqrestore(struct task_struct *t, unsigned long flags)
 		 * so we must take a snapshot of the expedited state.
 		 */
 		empty_exp_now = sync_rcu_exp_done(rnp);
-		if (!empty_norm && !rcu_preempt_blocked_readers_cgp(rnp)) {
+		if (!empty_norm && !rcu_preempt_blocked_readers_cgp(rnp, true)) {
 			trace_rcu_quiescent_state_report(TPS("preempt_rcu"),
 							 rnp->gp_seq,
 							 0, rnp->qsmask,
@@ -901,7 +920,7 @@ static void rcu_preempt_check_blocked_tasks(struct rcu_node *rnp)
 
 	RCU_LOCKDEP_WARN(preemptible(), "rcu_preempt_check_blocked_tasks() invoked with preemption enabled!!!\n");
 	raw_lockdep_assert_held_rcu_node(rnp);
-	if (WARN_ON_ONCE(rcu_preempt_blocked_readers_cgp(rnp)))
+	if (WARN_ON_ONCE(rcu_preempt_blocked_readers_cgp(rnp, true)))
 		dump_blkd_tasks(rnp, 10);
 	if (rcu_preempt_has_tasks(rnp) &&
 	    (rnp->qsmaskinit || rnp->wait_blkd_tasks)) {
@@ -1127,7 +1146,7 @@ EXPORT_SYMBOL_GPL(rcu_note_context_switch);
  * Because preemptible RCU does not exist, there are never any preempted
  * RCU readers.
  */
-static int rcu_preempt_blocked_readers_cgp(struct rcu_node *rnp)
+static int rcu_preempt_blocked_readers_cgp(struct rcu_node *rnp, bool promote)
 {
 	return 0;
 }
@@ -1221,6 +1240,9 @@ static void rcu_preempt_deferred_qs_init(struct rcu_data *rdp) { }
 
 static void rcu_promote_blocked_tasks(struct rcu_node *rnp) { }
 
+static void rcu_promote_blocked_tasks_rdp(struct rcu_data *rdp,
+					  struct rcu_node *rnp) { }
+
 #endif /* #else #ifdef CONFIG_PREEMPT_RCU */
 
 /*
@@ -1378,7 +1400,7 @@ static void rcu_initiate_boost(struct rcu_node *rnp, unsigned long flags)
 {
 	raw_lockdep_assert_held_rcu_node(rnp);
 	if (!rnp->boost_kthread_task ||
-	    (!rcu_preempt_blocked_readers_cgp(rnp) && !rnp->exp_tasks)) {
+	    (!rcu_preempt_blocked_readers_cgp(rnp, true) && !rnp->exp_tasks)) {
 		raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
 		return;
 	}
kernel/rcu/tree_stall.h +2 -2
index b67532cb8770..5aa65130ab5c 100644
@@ -277,7 +277,7 @@ static void rcu_print_detail_task_stall_rnp(struct rcu_node *rnp)
 	struct task_struct *t;
 
 	raw_spin_lock_irqsave_rcu_node(rnp, flags);
-	if (!rcu_preempt_blocked_readers_cgp(rnp)) {
+	if (!rcu_preempt_blocked_readers_cgp(rnp, true)) {
 		raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
 		return;
 	}
@@ -331,7 +331,7 @@ static int rcu_print_task_stall(struct rcu_node *rnp, unsigned long flags)
 	struct task_struct *ts[8];
 
 	lockdep_assert_irqs_disabled();
-	if (!rcu_preempt_blocked_readers_cgp(rnp)) {
+	if (!rcu_preempt_blocked_readers_cgp(rnp, true)) {
 		raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
 		return 0;
 	}
Signature · 1 line
2.34.1
author maintainer
#12 lore raw

RFC PATCH 7/14 rcu: Promote late-arriving blocked tasks before reporting QS

In reply to Joel Fernandes

Blocked tasks need to be promoted before rdp QS reporting, so that the QS reporting infrastructure considers this and does not prematurely end the GP.

Therefore, this patch adds support for the same.

---
 kernel/rcu/tree.c | 7 +++++++
 kernel/rcu/tree.h | 2 ++
 2 files changed, 9 insertions(+)
kernel/rcu/tree.c +7 -0
index f8f43f94adbb..2a20b1a8c5d3 100644
@@ -2500,6 +2500,13 @@ rcu_report_qs_rdp(struct rcu_data *rdp)
 			WARN_ON_ONCE(rcu_accelerate_cbs(rnp, rdp));
 		}
 
+		/*
+		 * Promote any late-arriving blocked tasks before reporting QS.
+		 * This handles the case where a task blocks just as a GP is
+		 * starting, missing the initial promotion in rcu_gp_init().
+		 */
+		rcu_promote_blocked_tasks_rdp(rdp, rnp);
+
 		rcu_disable_urgency_upon_qs(rdp);
 		rcu_report_qs_rnp(mask, rnp, rnp->gp_seq, flags);
 		/* ^^^ Released rnp->lock */
kernel/rcu/tree.h +2 -0
index 25eb9200e6ef..809aa77f57f8 100644
@@ -502,6 +502,8 @@ static void rcu_cpu_kthread_setup(unsigned int cpu);
 static void rcu_spawn_one_boost_kthread(struct rcu_node *rnp);
 static bool rcu_preempt_has_tasks(struct rcu_node *rnp);
 static void rcu_promote_blocked_tasks(struct rcu_node *rnp);
+static void rcu_promote_blocked_tasks_rdp(struct rcu_data *rdp,
+					  struct rcu_node *rnp);
 static bool rcu_preempt_need_deferred_qs(struct task_struct *t);
 static void zero_cpu_stall_ticks(struct rcu_data *rdp);
 static struct swait_queue_head *rcu_nocb_gp_get(struct rcu_node *rnp);
Signature · 1 line
2.34.1
author maintainer
#13 lore raw

RFC PATCH 8/14 rcu: Promote blocked tasks before QS report in force_qs_rnp()

In reply to Joel Fernandes

When force_qs_rnp() forces quiescent states for idle or offline CPUs, any tasks blocked on those CPUs' per-CPU blocked lists must first be promoted to the rcu_node's blkd_tasks list.

Without this promotion, blocked tasks on per-CPU lists won't have gp_tasks point to them, so the GP machinery won't wait for them. This can cause "Wrong-GP reads" errors where a GP completes while readers are still in their critical sections.

Therefore, call rcu_promote_blocked_tasks_rdp() before reporting QS.

---
 kernel/rcu/tree.c | 5 +++++
 1 file changed, 5 insertions(+)
kernel/rcu/tree.c +5 -0
index 2a20b1a8c5d3..19fd13c1e6be 100644
@@ -2790,6 +2790,11 @@ static void force_qs_rnp(int (*f)(struct rcu_data *rdp))
 			rdp = per_cpu_ptr(&rcu_data, cpu);
 			ret = f(rdp);
 			if (ret > 0) {
+				/*
+				 * Promote blocked tasks before reporting QS.
+				 * Otherwise tasks on per-CPU list aren't tracked.
+				 */
+				rcu_promote_blocked_tasks_rdp(rdp, rnp);
 				mask |= rdp->grpmask;
 				rcu_disable_urgency_upon_qs(rdp);
 			}
Signature · 1 line
2.34.1
author maintainer
#14 lore raw

RFC PATCH 9/14 rcu: Promote blocked tasks before QS report in rcutree_report_cpu_dead()

In reply to Joel Fernandes

When a CPU dies and reports QS via rcutree_report_cpu_dead(), any tasks blocked on that CPU's per-CPU blocked list must first be promoted to the rcu_node's blkd_tasks list.

Without this promotion, blocked tasks on the dying CPU's per-CPU list won't have gp_tasks point to them, so the GP machinery won't wait for them. This can cause "Wrong-GP reads" errors where a GP completes while readers are still in their critical sections.

Therefore, call rcu_promote_blocked_tasks_rdp() before reporting QS.

---
 kernel/rcu/tree.c | 5 +++++
 1 file changed, 5 insertions(+)
kernel/rcu/tree.c +5 -0
index 19fd13c1e6be..5e73ebb260e3 100644
@@ -4460,6 +4460,11 @@ void rcutree_report_cpu_dead(void)
 	rdp->rcu_ofl_gp_seq = READ_ONCE(rcu_state.gp_seq);
 	rdp->rcu_ofl_gp_state = READ_ONCE(rcu_state.gp_state);
 	if (rnp->qsmask & mask) { /* RCU waiting on outgoing CPU? */
+		/*
+		 * Promote blocked tasks from dying CPU's per-CPU list before
+		 * reporting QS. Otherwise those tasks won't block the GP.
+		 */
+		rcu_promote_blocked_tasks_rdp(rdp, rnp);
 		/* Report quiescent state -before- changing ->qsmaskinitnext! */
 		rcu_disable_urgency_upon_qs(rdp);
 		rcu_report_qs_rnp(mask, rnp, rnp->gp_seq, flags);
Signature · 1 line
2.34.1
author maintainer
#15 lore raw

RFC PATCH 10/14 rcu: Promote blocked tasks before QS report in rcu_gp_init()

In reply to Joel Fernandes

During grace period initialization, when rcu_gp_init() reports QS for offline CPUs, any tasks blocked on those CPUs' per-CPU blocked lists must first be promoted to the rcu_node's blkd_tasks list.

Without this promotion, blocked tasks on offline CPUs' per-CPU lists won't have gp_tasks point to them, so the GP machinery won't wait for them. This can cause "Wrong-GP reads" errors where a GP completes while readers are still in their critical sections.

Therefore, call call rcu_promote_blocked_tasks_rdp() for each offline CPU before reporting QS for them.

---
 kernel/rcu/tree.c | 15 ++++++++++++++-
 1 file changed, 14 insertions(+), 1 deletion(-)
kernel/rcu/tree.c +14 -1
index 5e73ebb260e3..468388970c98 100644
@@ -2001,8 +2001,21 @@ static noinline_for_stack bool rcu_gp_init(void)
 		 */
 		mask = rnp->qsmask & ~rnp->qsmaskinitnext;
 		rnp->rcu_gp_init_mask = mask;
-		if ((mask || rnp->wait_blkd_tasks) && rcu_is_leaf_node(rnp))
+		if ((mask || rnp->wait_blkd_tasks) && rcu_is_leaf_node(rnp)) {
+			int cpu;
+
+			/*
+			 * Promote blocked tasks from offline CPUs before
+			 * reporting QS, so they properly block the GP.
+			 */
+			for_each_leaf_node_cpu_mask(rnp, cpu, mask) {
+				struct rcu_data *rdp_cpu;
+
+				rdp_cpu = per_cpu_ptr(&rcu_data, cpu);
+				rcu_promote_blocked_tasks_rdp(rdp_cpu, rnp);
+			}
 			rcu_report_qs_rnp(mask, rnp, rnp->gp_seq, flags);
+		}
 		else
 			raw_spin_unlock_irq_rcu_node(rnp);
 		cond_resched_tasks_rcu_qs();
Signature · 1 line
2.34.1
author maintainer
#16 lore raw

RFC PATCH 11/14 rcu: Add per-CPU blocked list check in exit_rcu()

In reply to Joel Fernandes

With per-CPU blocked lists, a task can be on either the rcu_node's blkd_tasks list or on the per-CPU blocked list.

Therefore, extend exit_rcu() to check both lists. This ensures that if a task exits while on any blocked list, the cleanup path will properly handle it.

---
 kernel/rcu/tree_plugin.h | 9 ++++++++-
 1 file changed, 8 insertions(+), 1 deletion(-)
kernel/rcu/tree_plugin.h +8 -1
index 6ed3815bb912..8622e79660ed 100644
@@ -978,8 +978,15 @@ static void rcu_flavor_sched_clock_irq(int user)
 void exit_rcu(void)
 {
 	struct task_struct *t = current;
+	bool on_list;
 
-	if (unlikely(!list_empty(&current->rcu_node_entry))) {
+	/* Check if task is on any blocked list (rnp or per-CPU). */
+	on_list = !list_empty(&current->rcu_node_entry);
+#ifdef CONFIG_RCU_PER_CPU_BLOCKED_LISTS
+	on_list = on_list || !list_empty(&current->rcu_rdp_entry);
+#endif
+
+	if (unlikely(on_list)) {
 		rcu_preempt_depth_set(1);
 		barrier();
 		WARN_ON_ONCE(!t->rcu_read_unlock_special.b.blocked);
Signature · 1 line
2.34.1
author maintainer
#17 lore raw

RFC PATCH 12/14 rcu: Skip per-CPU list addition when GP already started

In reply to Joel Fernandes

When a grace period is already started or waiting on this CPU, skip adding the blocked task to the per-CPU rdp->blkd_list. The task goes directly to rnp->blkd_tasks via rcu_preempt_ctxt_queue(), which is the same behavior as before per-CPU lists were added.

When no GP is waiting, add the task to BOTH lists as before this patch. This maintains the existing behavior while preparing for the next patch which will skip rnp blocked list addition when no GP is waiting.

Because the rnp->blkd_tasks handling remains unchanged (tasks still go through rcu_preempt_ctxt_queue() in all cases), this work same as before this patch.

---
 kernel/rcu/tree_plugin.h | 16 ++++++++++++----
 1 file changed, 12 insertions(+), 4 deletions(-)
kernel/rcu/tree_plugin.h +12 -4
index 8622e79660ed..d43dd153c152 100644
@@ -339,10 +339,18 @@ void rcu_note_context_switch(bool preempt)
 		t->rcu_read_unlock_special.b.blocked = true;
 		t->rcu_blocked_node = rnp;
 #ifdef CONFIG_RCU_PER_CPU_BLOCKED_LISTS
-		t->rcu_blocked_cpu = rdp->cpu;
-		raw_spin_lock(&rdp->blkd_lock);
-		list_add(&t->rcu_rdp_entry, &rdp->blkd_list);
-		raw_spin_unlock(&rdp->blkd_lock);
+		/*
+		 * If no GP is waiting on this CPU, add to per-CPU list as well
+		 * so promotion can find it if a GP starts later. If GP waiting,
+		 * skip per-CPU list - task goes only to rnp->blkd_tasks (same
+		 * behavior as before per-CPU lists were added).
+		 */
+		if (!rcu_gp_in_progress() && !rdp->cpu_no_qs.b.norm && !rdp->cpu_no_qs.b.exp) {
+			t->rcu_blocked_cpu = rdp->cpu;
+			raw_spin_lock(&rdp->blkd_lock);
+			list_add(&t->rcu_rdp_entry, &rdp->blkd_list);
+			raw_spin_unlock(&rdp->blkd_lock);
+		}
 #endif
 
 		/*
Signature · 1 line
2.34.1
author maintainer
#18 lore raw

RFC PATCH 13/14 rcu: Skip rnp addition when no grace period waiting

In reply to Joel Fernandes

This is the key optimization commit that triggers the per-CPU blocked task list promotion mechanism.

When a GP is waiting, add directly to rnp->blkd_tasks via rcu_preempt_ctxt_queue(), but NOT to the per-CPU list.

However, when no GP is waiting on this CPU, skip adding to rnp->blkd_tasks entirely. This completely avoids rnp->lock acquisition in this path triggering the optimization.

---
 kernel/rcu/tree_plugin.h | 64 ++++++++++++++++++++++++----------------
 1 file changed, 38 insertions(+), 26 deletions(-)
kernel/rcu/tree_plugin.h +38 -26
index d43dd153c152..a0cd50f1e6c5 100644
@@ -335,37 +335,43 @@ void rcu_note_context_switch(bool preempt)
 
 		/* Possibly blocking in an RCU read-side critical section. */
 		rnp = rdp->mynode;
-		raw_spin_lock_rcu_node(rnp);
 		t->rcu_read_unlock_special.b.blocked = true;
-		t->rcu_blocked_node = rnp;
 #ifdef CONFIG_RCU_PER_CPU_BLOCKED_LISTS
 		/*
-		 * If no GP is waiting on this CPU, add to per-CPU list as well
-		 * so promotion can find it if a GP starts later. If GP waiting,
-		 * skip per-CPU list - task goes only to rnp->blkd_tasks (same
-		 * behavior as before per-CPU lists were added).
+		 * Check if a GP is in progress.
 		 */
 		if (!rcu_gp_in_progress() && !rdp->cpu_no_qs.b.norm && !rdp->cpu_no_qs.b.exp) {
+			/*
+			 * No GP waiting on this CPU. Add to per-CPU list only,
+			 * skipping rnp->lock for better scalability.
+			 */
+			t->rcu_blocked_node = NULL;
 			t->rcu_blocked_cpu = rdp->cpu;
 			raw_spin_lock(&rdp->blkd_lock);
 			list_add(&t->rcu_rdp_entry, &rdp->blkd_list);
 			raw_spin_unlock(&rdp->blkd_lock);
-		}
+			trace_rcu_preempt_task(rcu_state.name, t->pid,
+					       rcu_seq_snap(&rnp->gp_seq));
+		} else
 #endif
+		/* GP waiting (or per-CPU lists disabled) - add to rnp. */
+		{
+			raw_spin_lock_rcu_node(rnp);
+			t->rcu_blocked_node = rnp;
 
-		/*
-		 * Verify the CPU's sanity, trace the preemption, and
-		 * then queue the task as required based on the states
-		 * of any ongoing and expedited grace periods.
-		 */
-		WARN_ON_ONCE(!rcu_rdp_cpu_online(rdp));
-		WARN_ON_ONCE(!list_empty(&t->rcu_node_entry));
-		trace_rcu_preempt_task(rcu_state.name,
-				       t->pid,
-				       (rnp->qsmask & rdp->grpmask)
-				       ? rnp->gp_seq
-				       : rcu_seq_snap(&rnp->gp_seq));
-		rcu_preempt_ctxt_queue(rnp, rdp);
+			/*
+			 * Verify the CPU's sanity, trace the preemption, and
+			 * then queue the task as required based on the states
+			 * of any ongoing and expedited grace periods.
+			 */
+			WARN_ON_ONCE(!rcu_rdp_cpu_online(rdp));
+			WARN_ON_ONCE(!list_empty(&t->rcu_node_entry));
+			trace_rcu_preempt_task(rcu_state.name, t->pid,
+					       (rnp->qsmask & rdp->grpmask)
+					       ? rnp->gp_seq
+					       : rcu_seq_snap(&rnp->gp_seq));
+			rcu_preempt_ctxt_queue(rnp, rdp);
+		}
 	} else {
 		rcu_preempt_deferred_qs(t);
 	}
@@ -568,13 +574,22 @@ rcu_preempt_deferred_qs_irqrestore(struct task_struct *t, unsigned long flags)
 		 */
 		rnp = t->rcu_blocked_node;
 #ifdef CONFIG_RCU_PER_CPU_BLOCKED_LISTS
-		/* Remove from per-CPU list if task was added to it. */
 		blocked_cpu = t->rcu_blocked_cpu;
 		if (blocked_cpu != -1) {
+			/*
+			 * Task is on per-CPU list. Remove it and check if
+			 * it was promoted to rnp->blkd_tasks.
+			 */
 			blocked_rdp = per_cpu_ptr(&rcu_data, blocked_cpu);
 			raw_spin_lock(&blocked_rdp->blkd_lock);
 			list_del_init(&t->rcu_rdp_entry);
 			t->rcu_blocked_cpu = -1;
+
+			/*
+			 * Read rcu_blocked_node while holding blkd_lock to
+			 * serialize with rcu_promote_blocked_tasks().
+			 */
+			rnp = t->rcu_blocked_node;
 			raw_spin_unlock(&blocked_rdp->blkd_lock);
 			/*
 			 * TODO: This should just be "WARN_ON_ONCE(rnp); return;" since after
@@ -584,15 +599,12 @@ rcu_preempt_deferred_qs_irqrestore(struct task_struct *t, unsigned long flags)
 			 * from the rdp blocked list and early returning.
 			 */
 			if (!rnp) {
-				/*
-				 * Task was only on per-CPU list, not on rnp list.
-				 * This can happen in future when tasks are added
-				 * only to rdp initially and promoted to rnp later.
-				 */
+				/* Not promoted - no GP waiting for this task. */
 				local_irq_restore(flags);
 				return;
 			}
 		}
+		/* else: Task went directly to rnp->blkd_tasks. */
 #endif
 		raw_spin_lock_rcu_node(rnp); /* irqs already disabled. */
 		WARN_ON_ONCE(rnp != t->rcu_blocked_node);
Signature · 1 line
2.34.1
author maintainer
#19 lore raw

RFC PATCH 14/14 rcu: Remove checking of per-cpu blocked list against the node list

In reply to Joel Fernandes

Now that the verification check consistently is verified, remove it. It is still kept in the patch series for illustration/testing purposes.

---
 kernel/rcu/tree.c | 20 --------------------
 1 file changed, 20 deletions(-)
kernel/rcu/tree.c +0 -20
index 468388970c98..9d9d7c5ff3fc 100644
@@ -1900,26 +1900,6 @@ static noinline_for_stack bool rcu_gp_init(void)
 		arch_spin_lock(&rcu_state.ofl_lock);
 		raw_spin_lock_rcu_node(rnp);
 		rcu_promote_blocked_tasks(rnp);
-#ifdef CONFIG_RCU_PER_CPU_BLOCKED_LISTS
-		/*
-		 * Verify rdp lists consistent with rnp list. Since the unlock
-		 * path removes from rdp before rnp, we can have tasks that are
-		 * on rnp but not on rdp (in the middle of being removed).
-		 * Therefore rnp_count >= rdp_total is the expected invariant.
-		 */
-		rnp_count = 0;
-		rdp_total = 0;
-		list_for_each_entry(t_verify, &rnp->blkd_tasks, rcu_node_entry)
-			rnp_count++;
-		for (cpu_verify = rnp->grplo; cpu_verify <= rnp->grphi; cpu_verify++) {
-			rdp_cpu = per_cpu_ptr(&rcu_data, cpu_verify);
-			raw_spin_lock(&rdp_cpu->blkd_lock);
-			list_for_each_entry(t_rdp, &rdp_cpu->blkd_list, rcu_rdp_entry)
-				rdp_total++;
-			raw_spin_unlock(&rdp_cpu->blkd_lock);
-		}
-		WARN_ON_ONCE(rnp_count < rdp_total);
-#endif
 		if (rnp->qsmaskinit == rnp->qsmaskinitnext &&
 		    !rnp->wait_blkd_tasks) {
 			/* Nothing to do on this leaf rcu_node structure. */
Signature · 1 line
2.34.1
#20 lore raw

Re: [PATCH RFC 14/14] rcu: Remove checking of per-cpu blocked list against the node list

kernel test robot noticed the following build warnings:

Hi Joel,

[This is a private test report for your RFC patch.] kernel test robot noticed the following build warnings:

[auto build test WARNING on f8f9c1f4d0c7a64600e2ca312dec824a0bc2f1da]

url:    https://github.com/intel-lab-lkp/linux/commits/Joel-Fernandes/rcu-Add-WARN_ON_ONCE-for-blocked-flag-invariant-in-exit_rcu/20260103-083616
base:   f8f9c1f4d0c7a64600e2ca312dec824a0bc2f1da
patch link:    https://lore.kernel.org/r/20260103002343.6599-15-joelagnelf%40nvidia.com
patch subject: [PATCH RFC 14/14] rcu: Remove checking of per-cpu blocked list against the node list
config: s390-allmodconfig (https://download.01.org/0day-ci/archive/20260110/[email protected]/config)
compiler: clang version 18.1.8 (https://github.com/llvm/llvm-project 3b5b5c1ec4a3095ab096dd780e84d7ab81f3d7ff)
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20260110/[email protected]/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <[email protected]>
| Closes: https://lore.kernel.org/oe-kbuild-all/[email protected]/

All warnings (new ones prefixed by >>):

>> kernel/rcu/tree.c:1813:22: warning: unused variable 't_verify' [-Wunused-variable]
    1813 |         struct task_struct *t_verify;
         |                             ^~~~~~~~
>> kernel/rcu/tree.c:1814:6: warning: unused variable 'cpu_verify' [-Wunused-variable]
    1814 |         int cpu_verify;
         |             ^~~~~~~~~~
>> kernel/rcu/tree.c:1815:6: warning: unused variable 'rnp_count' [-Wunused-variable]
    1815 |         int rnp_count;
         |             ^~~~~~~~~
>> kernel/rcu/tree.c:1816:6: warning: unused variable 'rdp_total' [-Wunused-variable]
    1816 |         int rdp_total;
         |             ^~~~~~~~~
>> kernel/rcu/tree.c:1817:19: warning: unused variable 'rdp_cpu' [-Wunused-variable]
    1817 |         struct rcu_data *rdp_cpu;
         |                          ^~~~~~~
>> kernel/rcu/tree.c:1818:22: warning: unused variable 't_rdp' [-Wunused-variable]
    1818 |         struct task_struct *t_rdp;
         |                             ^~~~~

6 warnings generated.

vim +/t_verify +1813 kernel/rcu/tree.c

988f569ae041cc kernel/rcu/tree.c Uladzislau Rezki (Sony  2024-03-08  1799) 
64db4cfff99c04 kernel/rcutree.c  Paul E. McKenney        2008-12-18  1800  /*
45fed3e7cfb400 kernel/rcu/tree.c Paul E. McKenney        2015-11-07  1801   * Initialize a new grace period.  Return false if no grace period required.
64db4cfff99c04 kernel/rcutree.c  Paul E. McKenney        2008-12-18  1802   */
f74126dcbcbffe kernel/rcu/tree.c Paul E. McKenney        2021-06-07  1803  static noinline_for_stack bool rcu_gp_init(void)
64db4cfff99c04 kernel/rcutree.c  Paul E. McKenney        2008-12-18  1804  {
ec2c29765a4ab1 kernel/rcu/tree.c Paul E. McKenney        2018-05-07  1805  	unsigned long flags;
0aa04b055e71bd kernel/rcu/tree.c Paul E. McKenney        2015-01-23  1806  	unsigned long oldmask;
ec2c29765a4ab1 kernel/rcu/tree.c Paul E. McKenney        2018-05-07  1807  	unsigned long mask;
b3dbec76e5334f kernel/rcutree.c  Paul E. McKenney        2012-06-18  1808  	struct rcu_data *rdp;
336a4f6c451e48 kernel/rcu/tree.c Paul E. McKenney        2018-07-03  1809  	struct rcu_node *rnp = rcu_get_root();
988f569ae041cc kernel/rcu/tree.c Uladzislau Rezki (Sony  2024-03-08  1810) 	bool start_new_poll;
4aa6e94cf90c0d kernel/rcu/tree.c Joel Fernandes          2025-03-24  1811  	unsigned long old_gp_seq;
4babf56e07e6c2 kernel/rcu/tree.c Joel Fernandes          2026-01-02  1812  #ifdef CONFIG_RCU_PER_CPU_BLOCKED_LISTS
4babf56e07e6c2 kernel/rcu/tree.c Joel Fernandes          2026-01-02 @1813  	struct task_struct *t_verify;
4babf56e07e6c2 kernel/rcu/tree.c Joel Fernandes          2026-01-02 @1814  	int cpu_verify;
4babf56e07e6c2 kernel/rcu/tree.c Joel Fernandes          2026-01-02 @1815  	int rnp_count;
4babf56e07e6c2 kernel/rcu/tree.c Joel Fernandes          2026-01-02 @1816  	int rdp_total;
4babf56e07e6c2 kernel/rcu/tree.c Joel Fernandes          2026-01-02 @1817  	struct rcu_data *rdp_cpu;
4babf56e07e6c2 kernel/rcu/tree.c Joel Fernandes          2026-01-02 @1818  	struct task_struct *t_rdp;
4babf56e07e6c2 kernel/rcu/tree.c Joel Fernandes          2026-01-02  1819  #endif
b3dbec76e5334f kernel/rcutree.c  Paul E. McKenney        2012-06-18  1820  
9cbc5b97029bff kernel/rcu/tree.c Paul E. McKenney        2018-07-05  1821  	WRITE_ONCE(rcu_state.gp_activity, jiffies);
2a67e741bbbc02 kernel/rcu/tree.c Peter Zijlstra          2015-10-08  1822  	raw_spin_lock_irq_rcu_node(rnp);
62bb24c4b022b9 kernel/rcu/tree.c Paul E. McKenney        2024-03-07  1823  	if (!rcu_state.gp_flags) {
f7be82093952ee kernel/rcutree.c  Paul E. McKenney        2013-08-08  1824  		/* Spurious wakeup, tell caller to go back to sleep.  */
67c583a7de3433 kernel/rcu/tree.c Boqun Feng              2015-12-29  1825  		raw_spin_unlock_irq_rcu_node(rnp);
45fed3e7cfb400 kernel/rcu/tree.c Paul E. McKenney        2015-11-07  1826  		return false;
f7be82093952ee kernel/rcutree.c  Paul E. McKenney        2013-08-08  1827  	}
9cbc5b97029bff kernel/rcu/tree.c Paul E. McKenney        2018-07-05  1828  	WRITE_ONCE(rcu_state.gp_flags, 0); /* Clear all flags: New GP. */
b3dbec76e5334f kernel/rcutree.c  Paul E. McKenney        2012-06-18  1829  
de8e87305a1ae8 kernel/rcu/tree.c Paul E. McKenney        2018-07-03  1830  	if (WARN_ON_ONCE(rcu_gp_in_progress())) {
f7be82093952ee kernel/rcutree.c  Paul E. McKenney        2013-08-08  1831  		/*
f7be82093952ee kernel/rcutree.c  Paul E. McKenney        2013-08-08  1832  		 * Grace period already in progress, don't start another.
f7be82093952ee kernel/rcutree.c  Paul E. McKenney        2013-08-08  1833  		 * Not supposed to be able to happen.
f7be82093952ee kernel/rcutree.c  Paul E. McKenney        2013-08-08  1834  		 */
67c583a7de3433 kernel/rcu/tree.c Boqun Feng              2015-12-29  1835  		raw_spin_unlock_irq_rcu_node(rnp);
45fed3e7cfb400 kernel/rcu/tree.c Paul E. McKenney        2015-11-07  1836  		return false;
64db4cfff99c04 kernel/rcutree.c  Paul E. McKenney        2008-12-18  1837  	}
b32e9eb6ad2957 kernel/rcutree.c  Paul E. McKenney        2009-11-12  1838  
64db4cfff99c04 kernel/rcutree.c  Paul E. McKenney        2008-12-18  1839  	/* Advance to a new grace period and initialize state. */
ad3832e974eba3 kernel/rcu/tree.c Paul E. McKenney        2018-07-03  1840  	record_gp_stall_check_time();
85aad7cc417877 kernel/rcu/tree.c Paul E. McKenney        2024-12-12  1841  	/*
85aad7cc417877 kernel/rcu/tree.c Paul E. McKenney        2024-12-12  1842  	 * A new wait segment must be started before gp_seq advanced, so
85aad7cc417877 kernel/rcu/tree.c Paul E. McKenney        2024-12-12  1843  	 * that previous gp waiters won't observe the new gp_seq.
85aad7cc417877 kernel/rcu/tree.c Paul E. McKenney        2024-12-12  1844  	 */
85aad7cc417877 kernel/rcu/tree.c Paul E. McKenney        2024-12-12  1845  	start_new_poll = rcu_sr_normal_gp_init();
ff3bb6f4d06247 kernel/rcu/tree.c Paul E. McKenney        2018-05-01  1846  	/* Record GP times before starting GP, hence rcu_seq_start(). */
4aa6e94cf90c0d kernel/rcu/tree.c Joel Fernandes          2025-03-24  1847  	old_gp_seq = rcu_state.gp_seq;
30a7806adab5f6 kernel/rcu/tree.c Joel Fernandes          2025-07-15  1848  	/*
30a7806adab5f6 kernel/rcu/tree.c Joel Fernandes          2025-07-15  1849  	 * Critical ordering: rcu_seq_start() must happen BEFORE the CPU hotplug
30a7806adab5f6 kernel/rcu/tree.c Joel Fernandes          2025-07-15  1850  	 * scan below. Otherwise we risk a race where a newly onlining CPU could
30a7806adab5f6 kernel/rcu/tree.c Joel Fernandes          2025-07-15  1851  	 * be missed by the current grace period, potentially leading to
30a7806adab5f6 kernel/rcu/tree.c Joel Fernandes          2025-07-15  1852  	 * use-after-free errors. For a detailed explanation of this race, see
30a7806adab5f6 kernel/rcu/tree.c Joel Fernandes          2025-07-15  1853  	 * Documentation/RCU/Design/Requirements/Requirements.rst in the
30a7806adab5f6 kernel/rcu/tree.c Joel Fernandes          2025-07-15  1854  	 * "Hotplug CPU" section.
186779c0364680 kernel/rcu/tree.c Joel Fernandes          2025-07-15  1855  	 *
186779c0364680 kernel/rcu/tree.c Joel Fernandes          2025-07-15  1856  	 * Also note that the root rnp's gp_seq is kept separate from, and lags,
186779c0364680 kernel/rcu/tree.c Joel Fernandes          2025-07-15  1857  	 * the rcu_state's gp_seq, for a reason. See the Quick-Quiz on
186779c0364680 kernel/rcu/tree.c Joel Fernandes          2025-07-15  1858  	 * Single-node systems for more details (in Data-Structures.rst).
30a7806adab5f6 kernel/rcu/tree.c Joel Fernandes          2025-07-15  1859  	 */
9cbc5b97029bff kernel/rcu/tree.c Paul E. McKenney        2018-07-05  1860  	rcu_seq_start(&rcu_state.gp_seq);
4aa6e94cf90c0d kernel/rcu/tree.c Joel Fernandes          2025-03-24  1861  	/* Ensure that rcu_seq_done_exact() guardband doesn't give false positives. */
4aa6e94cf90c0d kernel/rcu/tree.c Joel Fernandes          2025-03-24  1862  	WARN_ON_ONCE(IS_ENABLED(CONFIG_PROVE_RCU) &&
4aa6e94cf90c0d kernel/rcu/tree.c Joel Fernandes          2025-03-24  1863  		     rcu_seq_done_exact(&old_gp_seq, rcu_seq_snap(&rcu_state.gp_seq)));
4aa6e94cf90c0d kernel/rcu/tree.c Joel Fernandes          2025-03-24  1864  
62ae19511f1efb kernel/rcu/tree.c Paul E. McKenney        2020-03-21  1865  	ASSERT_EXCLUSIVE_WRITER(rcu_state.gp_seq);
9cbc5b97029bff kernel/rcu/tree.c Paul E. McKenney        2018-07-05  1866  	trace_rcu_grace_period(rcu_state.name, rcu_state.gp_seq, TPS("start"));
bf95b2bc3e42f1 kernel/rcu/tree.c Paul E. McKenney        2022-04-13  1867  	rcu_poll_gp_seq_start(&rcu_state.gp_seq_polled_snap);
67c583a7de3433 kernel/rcu/tree.c Boqun Feng              2015-12-29  1868  	raw_spin_unlock_irq_rcu_node(rnp);
64db4cfff99c04 kernel/rcutree.c  Paul E. McKenney        2008-12-18  1869  
988f569ae041cc kernel/rcu/tree.c Uladzislau Rezki (Sony  2024-03-08  1870) 	/*
988f569ae041cc kernel/rcu/tree.c Uladzislau Rezki (Sony  2024-03-08  1871) 	 * The "start_new_poll" is set to true, only when this GP is not able
988f569ae041cc kernel/rcu/tree.c Uladzislau Rezki (Sony  2024-03-08  1872) 	 * to handle anything and there are outstanding users. It happens when
988f569ae041cc kernel/rcu/tree.c Uladzislau Rezki (Sony  2024-03-08  1873) 	 * the rcu_sr_normal_gp_init() function was not able to insert a dummy
988f569ae041cc kernel/rcu/tree.c Uladzislau Rezki (Sony  2024-03-08  1874) 	 * separator to the llist, because there were no left any dummy-nodes.
988f569ae041cc kernel/rcu/tree.c Uladzislau Rezki (Sony  2024-03-08  1875) 	 *
988f569ae041cc kernel/rcu/tree.c Uladzislau Rezki (Sony  2024-03-08  1876) 	 * Number of dummy-nodes is fixed, it could be that we are run out of
988f569ae041cc kernel/rcu/tree.c Uladzislau Rezki (Sony  2024-03-08  1877) 	 * them, if so we start a new pool request to repeat a try. It is rare
988f569ae041cc kernel/rcu/tree.c Uladzislau Rezki (Sony  2024-03-08  1878) 	 * and it means that a system is doing a slow processing of callbacks.
988f569ae041cc kernel/rcu/tree.c Uladzislau Rezki (Sony  2024-03-08  1879) 	 */
988f569ae041cc kernel/rcu/tree.c Uladzislau Rezki (Sony  2024-03-08  1880) 	if (start_new_poll)
988f569ae041cc kernel/rcu/tree.c Uladzislau Rezki (Sony  2024-03-08  1881) 		(void) start_poll_synchronize_rcu();
988f569ae041cc kernel/rcu/tree.c Uladzislau Rezki (Sony  2024-03-08  1882) 
0aa04b055e71bd kernel/rcu/tree.c Paul E. McKenney        2015-01-23  1883  	/*
f37599e6f06da4 kernel/rcu/tree.c Joel Fernandes (Google  2020-08-07  1884) 	 * Apply per-leaf buffered online and offline operations to
f37599e6f06da4 kernel/rcu/tree.c Joel Fernandes (Google  2020-08-07  1885) 	 * the rcu_node tree. Note that this new grace period need not
f37599e6f06da4 kernel/rcu/tree.c Joel Fernandes (Google  2020-08-07  1886) 	 * wait for subsequent online CPUs, and that RCU hooks in the CPU
f37599e6f06da4 kernel/rcu/tree.c Joel Fernandes (Google  2020-08-07  1887) 	 * offlining path, when combined with checks in this function,
f37599e6f06da4 kernel/rcu/tree.c Joel Fernandes (Google  2020-08-07  1888) 	 * will handle CPUs that are currently going offline or that will
f37599e6f06da4 kernel/rcu/tree.c Joel Fernandes (Google  2020-08-07  1889) 	 * go offline later.  Please also refer to "Hotplug CPU" section
f37599e6f06da4 kernel/rcu/tree.c Joel Fernandes (Google  2020-08-07  1890) 	 * of RCU's Requirements documentation.
0aa04b055e71bd kernel/rcu/tree.c Paul E. McKenney        2015-01-23  1891  	 */
683954e55c9814 kernel/rcu/tree.c Neeraj Upadhyay         2020-11-16  1892  	WRITE_ONCE(rcu_state.gp_state, RCU_GP_ONOFF);
82980b1622d970 kernel/rcu/tree.c David Woodhouse         2021-02-16  1893  	/* Exclude CPU hotplug operations. */
aedf4ba984168a kernel/rcu/tree.c Paul E. McKenney        2018-07-04  1894  	rcu_for_each_leaf_node(rnp) {
51cace13729f89 kernel/rcu/tree.c Paul E. McKenney        2024-05-08  1895  		local_irq_disable();
5d71c2b53f1790 kernel/rcu/tree.c Joel Fernandes          2025-07-15  1896  		/*
5d71c2b53f1790 kernel/rcu/tree.c Joel Fernandes          2025-07-15  1897  		 * Serialize with CPU offline. See Requirements.rst > Hotplug CPU >
5d71c2b53f1790 kernel/rcu/tree.c Joel Fernandes          2025-07-15  1898  		 * Concurrent Quiescent State Reporting for Offline CPUs.
5d71c2b53f1790 kernel/rcu/tree.c Joel Fernandes          2025-07-15  1899  		 */
82980b1622d970 kernel/rcu/tree.c David Woodhouse         2021-02-16  1900  		arch_spin_lock(&rcu_state.ofl_lock);
82980b1622d970 kernel/rcu/tree.c David Woodhouse         2021-02-16  1901  		raw_spin_lock_rcu_node(rnp);
899b2d63bf635c kernel/rcu/tree.c Joel Fernandes          2026-01-02  1902  		rcu_promote_blocked_tasks(rnp);
0aa04b055e71bd kernel/rcu/tree.c Paul E. McKenney        2015-01-23  1903  		if (rnp->qsmaskinit == rnp->qsmaskinitnext &&
0aa04b055e71bd kernel/rcu/tree.c Paul E. McKenney        2015-01-23  1904  		    !rnp->wait_blkd_tasks) {
0aa04b055e71bd kernel/rcu/tree.c Paul E. McKenney        2015-01-23  1905  			/* Nothing to do on this leaf rcu_node structure. */
82980b1622d970 kernel/rcu/tree.c David Woodhouse         2021-02-16  1906  			raw_spin_unlock_rcu_node(rnp);
82980b1622d970 kernel/rcu/tree.c David Woodhouse         2021-02-16  1907  			arch_spin_unlock(&rcu_state.ofl_lock);
51cace13729f89 kernel/rcu/tree.c Paul E. McKenney        2024-05-08  1908  			local_irq_enable();
0aa04b055e71bd kernel/rcu/tree.c Paul E. McKenney        2015-01-23  1909  			continue;
0aa04b055e71bd kernel/rcu/tree.c Paul E. McKenney        2015-01-23  1910  		}
0aa04b055e71bd kernel/rcu/tree.c Paul E. McKenney        2015-01-23  1911  
0aa04b055e71bd kernel/rcu/tree.c Paul E. McKenney        2015-01-23  1912  		/* Record old state, apply changes to ->qsmaskinit field. */
0aa04b055e71bd kernel/rcu/tree.c Paul E. McKenney        2015-01-23  1913  		oldmask = rnp->qsmaskinit;
0aa04b055e71bd kernel/rcu/tree.c Paul E. McKenney        2015-01-23  1914  		rnp->qsmaskinit = rnp->qsmaskinitnext;
0aa04b055e71bd kernel/rcu/tree.c Paul E. McKenney        2015-01-23  1915  
0aa04b055e71bd kernel/rcu/tree.c Paul E. McKenney        2015-01-23  1916  		/* If zero-ness of ->qsmaskinit changed, propagate up tree. */
0aa04b055e71bd kernel/rcu/tree.c Paul E. McKenney        2015-01-23  1917  		if (!oldmask != !rnp->qsmaskinit) {
962aff03c315b5 kernel/rcu/tree.c Paul E. McKenney        2018-05-02  1918  			if (!oldmask) { /* First online CPU for rcu_node. */
962aff03c315b5 kernel/rcu/tree.c Paul E. McKenney        2018-05-02  1919  				if (!rnp->wait_blkd_tasks) /* Ever offline? */
0aa04b055e71bd kernel/rcu/tree.c Paul E. McKenney        2015-01-23  1920  					rcu_init_new_rnp(rnp);
962aff03c315b5 kernel/rcu/tree.c Paul E. McKenney        2018-05-02  1921  			} else if (rcu_preempt_has_tasks(rnp)) {
962aff03c315b5 kernel/rcu/tree.c Paul E. McKenney        2018-05-02  1922  				rnp->wait_blkd_tasks = true; /* blocked tasks */
962aff03c315b5 kernel/rcu/tree.c Paul E. McKenney        2018-05-02  1923  			} else { /* Last offline CPU and can propagate. */
0aa04b055e71bd kernel/rcu/tree.c Paul E. McKenney        2015-01-23  1924  				rcu_cleanup_dead_rnp(rnp);
0aa04b055e71bd kernel/rcu/tree.c Paul E. McKenney        2015-01-23  1925  			}
962aff03c315b5 kernel/rcu/tree.c Paul E. McKenney        2018-05-02  1926  		}
0aa04b055e71bd kernel/rcu/tree.c Paul E. McKenney        2015-01-23  1927  
0aa04b055e71bd kernel/rcu/tree.c Paul E. McKenney        2015-01-23  1928  		/*
0aa04b055e71bd kernel/rcu/tree.c Paul E. McKenney        2015-01-23  1929  		 * If all waited-on tasks from prior grace period are
0aa04b055e71bd kernel/rcu/tree.c Paul E. McKenney        2015-01-23  1930  		 * done, and if all this rcu_node structure's CPUs are
0aa04b055e71bd kernel/rcu/tree.c Paul E. McKenney        2015-01-23  1931  		 * still offline, propagate up the rcu_node tree and
0aa04b055e71bd kernel/rcu/tree.c Paul E. McKenney        2015-01-23  1932  		 * clear ->wait_blkd_tasks.  Otherwise, if one of this
0aa04b055e71bd kernel/rcu/tree.c Paul E. McKenney        2015-01-23  1933  		 * rcu_node structure's CPUs has since come back online,
962aff03c315b5 kernel/rcu/tree.c Paul E. McKenney        2018-05-02  1934  		 * simply clear ->wait_blkd_tasks.
0aa04b055e71bd kernel/rcu/tree.c Paul E. McKenney        2015-01-23  1935  		 */
0aa04b055e71bd kernel/rcu/tree.c Paul E. McKenney        2015-01-23  1936  		if (rnp->wait_blkd_tasks &&
962aff03c315b5 kernel/rcu/tree.c Paul E. McKenney        2018-05-02  1937  		    (!rcu_preempt_has_tasks(rnp) || rnp->qsmaskinit)) {
0aa04b055e71bd kernel/rcu/tree.c Paul E. McKenney        2015-01-23  1938  			rnp->wait_blkd_tasks = false;
962aff03c315b5 kernel/rcu/tree.c Paul E. McKenney        2018-05-02  1939  			if (!rnp->qsmaskinit)
0aa04b055e71bd kernel/rcu/tree.c Paul E. McKenney        2015-01-23  1940  				rcu_cleanup_dead_rnp(rnp);
0aa04b055e71bd kernel/rcu/tree.c Paul E. McKenney        2015-01-23  1941  		}
0aa04b055e71bd kernel/rcu/tree.c Paul E. McKenney        2015-01-23  1942  
82980b1622d970 kernel/rcu/tree.c David Woodhouse         2021-02-16  1943  		raw_spin_unlock_rcu_node(rnp);
82980b1622d970 kernel/rcu/tree.c David Woodhouse         2021-02-16  1944  		arch_spin_unlock(&rcu_state.ofl_lock);
51cace13729f89 kernel/rcu/tree.c Paul E. McKenney        2024-05-08  1945  		local_irq_enable();
0aa04b055e71bd kernel/rcu/tree.c Paul E. McKenney        2015-01-23  1946  	}
22212332c1f37d kernel/rcu/tree.c Paul E. McKenney        2018-07-03  1947  	rcu_gp_slow(gp_preinit_delay); /* Races with CPU hotplug. */
64db4cfff99c04 kernel/rcutree.c  Paul E. McKenney        2008-12-18  1948  
64db4cfff99c04 kernel/rcutree.c  Paul E. McKenney        2008-12-18  1949  	/*
b835db1f9cadaf kernel/rcutree.c  Paul E. McKenney        2009-09-08  1950  	 * Set the quiescent-state-needed bits in all the rcu_node
9cbc5b97029bff kernel/rcu/tree.c Paul E. McKenney        2018-07-05  1951  	 * structures for all currently online CPUs in breadth-first
9cbc5b97029bff kernel/rcu/tree.c Paul E. McKenney        2018-07-05  1952  	 * order, starting from the root rcu_node structure, relying on the
9cbc5b97029bff kernel/rcu/tree.c Paul E. McKenney        2018-07-05  1953  	 * layout of the tree within the rcu_state.node[] array.  Note that
9cbc5b97029bff kernel/rcu/tree.c Paul E. McKenney        2018-07-05  1954  	 * other CPUs will access only the leaves of the hierarchy, thus
9cbc5b97029bff kernel/rcu/tree.c Paul E. McKenney        2018-07-05  1955  	 * seeing that no grace period is in progress, at least until the
9cbc5b97029bff kernel/rcu/tree.c Paul E. McKenney        2018-07-05  1956  	 * corresponding leaf node has been initialized.
7fdefc10e1d730 kernel/rcutree.c  Paul E. McKenney        2012-06-22  1957  	 *
7fdefc10e1d730 kernel/rcutree.c  Paul E. McKenney        2012-06-22  1958  	 * The grace period cannot complete until the initialization
7fdefc10e1d730 kernel/rcutree.c  Paul E. McKenney        2012-06-22  1959  	 * process finishes, because this kthread handles both.
64db4cfff99c04 kernel/rcutree.c  Paul E. McKenney        2008-12-18  1960  	 */
683954e55c9814 kernel/rcu/tree.c Neeraj Upadhyay         2020-11-16  1961  	WRITE_ONCE(rcu_state.gp_state, RCU_GP_INIT);
aedf4ba984168a kernel/rcu/tree.c Paul E. McKenney        2018-07-04  1962  	rcu_for_each_node_breadth_first(rnp) {
22212332c1f37d kernel/rcu/tree.c Paul E. McKenney        2018-07-03  1963  		rcu_gp_slow(gp_init_delay);
ec2c29765a4ab1 kernel/rcu/tree.c Paul E. McKenney        2018-05-07  1964  		raw_spin_lock_irqsave_rcu_node(rnp, flags);
da1df50d16171f kernel/rcu/tree.c Paul E. McKenney        2018-07-03  1965  		rdp = this_cpu_ptr(&rcu_data);
899b2d63bf635c kernel/rcu/tree.c Joel Fernandes          2026-01-02  1966  		rcu_promote_blocked_tasks(rnp);
81ab59a3ad8656 kernel/rcu/tree.c Paul E. McKenney        2018-07-03  1967  		rcu_preempt_check_blocked_tasks(rnp);
49e291266d0920 kernel/rcutree.c  Paul E. McKenney        2009-09-18  1968  		rnp->qsmask = rnp->qsmaskinit;
9cbc5b97029bff kernel/rcu/tree.c Paul E. McKenney        2018-07-05  1969  		WRITE_ONCE(rnp->gp_seq, rcu_state.gp_seq);
d09b62dfa33644 kernel/rcutree.c  Paul E. McKenney        2009-11-02  1970  		if (rnp == rdp->mynode)
c7e48f7ba38201 kernel/rcu/tree.c Paul E. McKenney        2018-07-03  1971  			(void)__note_gp_changes(rnp, rdp);
27f4d28057adf9 kernel/rcutree.c  Paul E. McKenney        2011-02-07  1972  		rcu_preempt_boost_start_gp(rnp);
9cbc5b97029bff kernel/rcu/tree.c Paul E. McKenney        2018-07-05  1973  		trace_rcu_grace_period_init(rcu_state.name, rnp->gp_seq,
d4c08f2ac311a3 kernel/rcutree.c  Paul E. McKenney        2011-06-25  1974  					    rnp->level, rnp->grplo,
d4c08f2ac311a3 kernel/rcutree.c  Paul E. McKenney        2011-06-25  1975  					    rnp->grphi, rnp->qsmask);
5d71c2b53f1790 kernel/rcu/tree.c Joel Fernandes          2025-07-15  1976  		/*
5d71c2b53f1790 kernel/rcu/tree.c Joel Fernandes          2025-07-15  1977  		 * Quiescent states for tasks on any now-offline CPUs. Since we
5d71c2b53f1790 kernel/rcu/tree.c Joel Fernandes          2025-07-15  1978  		 * released the ofl and rnp lock before this loop, CPUs might
5d71c2b53f1790 kernel/rcu/tree.c Joel Fernandes          2025-07-15  1979  		 * have gone offline and we have to report QS on their behalf.
5d71c2b53f1790 kernel/rcu/tree.c Joel Fernandes          2025-07-15  1980  		 * See Requirements.rst > Hotplug CPU > Concurrent QS Reporting.
5d71c2b53f1790 kernel/rcu/tree.c Joel Fernandes          2025-07-15  1981  		 */
ec2c29765a4ab1 kernel/rcu/tree.c Paul E. McKenney        2018-05-07  1982  		mask = rnp->qsmask & ~rnp->qsmaskinitnext;
f2e2df59786d7b kernel/rcu/tree.c Paul E. McKenney        2018-05-15  1983  		rnp->rcu_gp_init_mask = mask;
f378d76282efe0 kernel/rcu/tree.c Joel Fernandes          2026-01-02  1984  		if ((mask || rnp->wait_blkd_tasks) && rcu_is_leaf_node(rnp)) {
f378d76282efe0 kernel/rcu/tree.c Joel Fernandes          2026-01-02  1985  			int cpu;
f378d76282efe0 kernel/rcu/tree.c Joel Fernandes          2026-01-02  1986  
f378d76282efe0 kernel/rcu/tree.c Joel Fernandes          2026-01-02  1987  			/*
f378d76282efe0 kernel/rcu/tree.c Joel Fernandes          2026-01-02  1988  			 * Promote blocked tasks from offline CPUs before
f378d76282efe0 kernel/rcu/tree.c Joel Fernandes          2026-01-02  1989  			 * reporting QS, so they properly block the GP.
f378d76282efe0 kernel/rcu/tree.c Joel Fernandes          2026-01-02  1990  			 */
f378d76282efe0 kernel/rcu/tree.c Joel Fernandes          2026-01-02  1991  			for_each_leaf_node_cpu_mask(rnp, cpu, mask) {
f378d76282efe0 kernel/rcu/tree.c Joel Fernandes          2026-01-02  1992  				struct rcu_data *rdp_cpu;
f378d76282efe0 kernel/rcu/tree.c Joel Fernandes          2026-01-02  1993  
f378d76282efe0 kernel/rcu/tree.c Joel Fernandes          2026-01-02  1994  				rdp_cpu = per_cpu_ptr(&rcu_data, cpu);
f378d76282efe0 kernel/rcu/tree.c Joel Fernandes          2026-01-02  1995  				rcu_promote_blocked_tasks_rdp(rdp_cpu, rnp);
f378d76282efe0 kernel/rcu/tree.c Joel Fernandes          2026-01-02  1996  			}
b50912d0b5e03f kernel/rcu/tree.c Paul E. McKenney        2018-07-03  1997  			rcu_report_qs_rnp(mask, rnp, rnp->gp_seq, flags);
f378d76282efe0 kernel/rcu/tree.c Joel Fernandes          2026-01-02  1998  		}
ec2c29765a4ab1 kernel/rcu/tree.c Paul E. McKenney        2018-05-07  1999  		else
67c583a7de3433 kernel/rcu/tree.c Boqun Feng              2015-12-29  2000  			raw_spin_unlock_irq_rcu_node(rnp);
cee43939893337 kernel/rcu/tree.c Paul E. McKenney        2018-03-02  2001  		cond_resched_tasks_rcu_qs();
9cbc5b97029bff kernel/rcu/tree.c Paul E. McKenney        2018-07-05  2002  		WRITE_ONCE(rcu_state.gp_activity, jiffies);
64db4cfff99c04 kernel/rcutree.c  Paul E. McKenney        2008-12-18  2003  	}
64db4cfff99c04 kernel/rcutree.c  Paul E. McKenney        2008-12-18  2004  
933ada2c3310aa kernel/rcu/tree.c Paul E. McKenney        2020-08-06  2005  	// If strict, make all CPUs aware of new grace period.
933ada2c3310aa kernel/rcu/tree.c Paul E. McKenney        2020-08-06  2006  	if (IS_ENABLED(CONFIG_RCU_STRICT_GRACE_PERIOD))
933ada2c3310aa kernel/rcu/tree.c Paul E. McKenney        2020-08-06  2007  		on_each_cpu(rcu_strict_gp_boundary, NULL, 0);
933ada2c3310aa kernel/rcu/tree.c Paul E. McKenney        2020-08-06  2008  
45fed3e7cfb400 kernel/rcu/tree.c Paul E. McKenney        2015-11-07  2009  	return true;
cabc49c1ff51ba kernel/rcutree.c  Paul E. McKenney        2012-06-20  2010  }
cabc49c1ff51ba kernel/rcutree.c  Paul E. McKenney        2012-06-20  2011  
Signature · 2 lines
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki
maintainer
#21 lore raw
In reply to Joel Fernandes
Quoted 48 lines · Joel Fernandes

When a task is preempted while holding an RCU read-side lock, the kernel must track it on the rcu_node's blocked task list. This requires acquiring rnp->lock shared by all CPUs in that node's subtree.

Posting this as RFC for early feedback. There could be bugs lurking, especially related to expedited GPs which I have not yet taken a close look at. Several TODOs are added. It passed light TREE03 rcutorture testing.

On systems with 16 or fewer CPUs, the RCU hierarchy often has just a single rcu_node, making rnp->lock effectively a global lock for all blocked task operations. Every context switch where a task holds an RCU read-side lock contends on this single lock.

Enter Virtualization
--------------------
In virtualized environments, the problem becomes dramatically worse due to vCPU preemption. Research from USENIX ATC'17 ("The RCU-Reader Preemption Problem in VMs" by Gopinath and Paul McKenney) [1] explores the issue that RCU reader preemption in VMs causes multi-second latency spikes and huge increases in grace period duration.

When a vCPU is preempted by the hypervisor while holding rnp->lock, other vCPUs spin waiting for a lock holder that isn't even running. In testing with host RT preemptors to inject vCPU preemption, lock hold times extended from ~4us to over 4000us - a 1000x increase.

The Solution
------------
This series introduces per-CPU lists for tracking blocked RCU readers. The key insight is that when no grace period is active, blocked tasks complete their critical sections before really requiring any rnp locking.

1. Fast path: At context switch, Add the task only to the per-CPU list - no rnp->lock needed.

2. Promotion on demand: When a grace period starts, promote tasks from per-CPU lists to the rcu_node list.

3. Normal path: If a grace period is already waiting, tasks go directly to the rcu_node list as before.

Results
-------
Testing with 64 reader threads under vCPU preemption from 32 host SCHED_FIFO preemptors), 100 runs each. Throughput measured of read lock/unlock iterations per second.

Quoted 3 lines
                        Baseline        Optimized
Mean throughput         66,980 iter/s   97,719 iter/s   (+46%)
Lock hold time (mean)   1,069 us        ~0 us

Excellent performance improvement!

It would be good to simplify the management of the blocked-tasks lists, and to make it more exact, as in never unnecessarily priority-boost a task. But it is not like people have been complaining, at least not to me. And earlier attempts in that direction added more mess than simplification. :-(

Quoted 10 lines

The optimized version maintains stable performance with essentially close to zero rnp->lock overhead.

rcutorture Testing
------------------
TREE03 Testing with rcutorture without RCU or hotplug errors. More testing is in progress.

Note: I have added a CONFIG_RCU_PER_CPU_BLOCKED_LISTS to guard the feature but the plan is to eventually turn this on all the time.

Yes, Aravinda, Gopinath, and I did publish that paper back in the day (with Aravinda having done almost all the work), but it was an artificial workload. Which is OK given that it was an academic effort. It has also provided some entertainment, for example, an audience member asking me if I was aware of this work in a linguistic-kill-shot manner. ;-)

So are we finally seeing this effect in the wild?

The main point of this patch series is to avoid lock contention due to vCPU preemption, correct? If so, will we need similar work on the other locks in the Linux kernel, both within RCU and elsewhere? I vaguely recall your doing some work along those lines a few years back, and maybe Thomas Gleixner's deferred-preemption work could help with this. Or not, who knows? Keeping the hypervisor informed of lock state is not necessarily free.

Also if so, would the following rather simpler patch do the same trick, if accompanied by CONFIG_RCU_FANOUT_LEAF=1?

------------------------------------------------------------------------

kernel/rcu/Kconfig +3 -3
index 6a319e2926589..04dbee983b37d 100644
@@ -198,9 +198,9 @@ config RCU_FANOUT
 
 config RCU_FANOUT_LEAF
 	int "Tree-based hierarchical RCU leaf-level fanout value"
-	range 2 64 if 64BIT && !RCU_STRICT_GRACE_PERIOD
-	range 2 32 if !64BIT && !RCU_STRICT_GRACE_PERIOD
-	range 2 3 if RCU_STRICT_GRACE_PERIOD
+	range 1 64 if 64BIT && !RCU_STRICT_GRACE_PERIOD
+	range 1 32 if !64BIT && !RCU_STRICT_GRACE_PERIOD
+	range 1 3 if RCU_STRICT_GRACE_PERIOD
 	depends on TREE_RCU && RCU_EXPERT
 	default 16 if !RCU_STRICT_GRACE_PERIOD
 	default 2 if RCU_STRICT_GRACE_PERIOD

------------------------------------------------------------------------

This passes a quick 20-minute rcutorture smoke test. Does it provide similar performance benefits?

Thanx, Paul

Quoted 34 lines

[1] https://www.usenix.org/conference/atc17/technical-sessions/presentation/prasad

Joel Fernandes (14):
rcu: Add WARN_ON_ONCE for blocked flag invariant in exit_rcu()
rcu: Add per-CPU blocked task lists for PREEMPT_RCU
rcu: Early return during unlock for tasks only on per-CPU blocked list
rcu: Promote blocked tasks from per-CPU to rnp lists
rcu: Promote blocked tasks for expedited GPs
rcu: Promote per-CPU blocked tasks before checking for blocked readers
rcu: Promote late-arriving blocked tasks before reporting QS
rcu: Promote blocked tasks before QS report in force_qs_rnp()
rcu: Promote blocked tasks before QS report in
rcutree_report_cpu_dead()
rcu: Promote blocked tasks before QS report in rcu_gp_init()
rcu: Add per-CPU blocked list check in exit_rcu()
rcu: Skip per-CPU list addition when GP already started
rcu: Skip rnp addition when no grace period waiting
rcu: Remove checking of per-cpu blocked list against the node list

 include/linux/sched.h    |   4 +
 kernel/fork.c            |   4 +
 kernel/rcu/Kconfig       |  12 +++
 kernel/rcu/tree.c        |  60 +++++++++--
 kernel/rcu/tree.h        |  11 +-
 kernel/rcu/tree_exp.h    |   5 +
 kernel/rcu/tree_plugin.h | 211 +++++++++++++++++++++++++++++++++++----
 kernel/rcu/tree_stall.h  |   4 +-
 8 files changed, 279 insertions(+), 32 deletions(-)

base-commit: f8f9c1f4d0c7a64600e2ca312dec824a0bc2f1da --
2.34.1

#22 lore raw

Hi Paul,

Quoted 49 lines · Paul E. McKenney
Quoted 48 lines · Joel Fernandes

When a task is preempted while holding an RCU read-side lock, the kernel must track it on the rcu_node's blocked task list. This requires acquiring rnp->lock shared by all CPUs in that node's subtree.

Posting this as RFC for early feedback. There could be bugs lurking, especially related to expedited GPs which I have not yet taken a close look at. Several TODOs are added. It passed light TREE03 rcutorture testing.

On systems with 16 or fewer CPUs, the RCU hierarchy often has just a single rcu_node, making rnp->lock effectively a global lock for all blocked task operations. Every context switch where a task holds an RCU read-side lock contends on this single lock.

Enter Virtualization
--------------------
In virtualized environments, the problem becomes dramatically worse due to vCPU preemption. Research from USENIX ATC'17 ("The RCU-Reader Preemption Problem in VMs" by Gopinath and Paul McKenney) [1] explores the issue that RCU reader preemption in VMs causes multi-second latency spikes and huge increases in grace period duration.

When a vCPU is preempted by the hypervisor while holding rnp->lock, other vCPUs spin waiting for a lock holder that isn't even running. In testing with host RT preemptors to inject vCPU preemption, lock hold times extended from ~4us to over 4000us - a 1000x increase.

The Solution
------------
This series introduces per-CPU lists for tracking blocked RCU readers. The key insight is that when no grace period is active, blocked tasks complete their critical sections before really requiring any rnp locking.

1. Fast path: At context switch, Add the task only to the per-CPU list - no rnp->lock needed.

2. Promotion on demand: When a grace period starts, promote tasks from per-CPU lists to the rcu_node list.

3. Normal path: If a grace period is already waiting, tasks go directly to the rcu_node list as before.

Results
-------
Testing with 64 reader threads under vCPU preemption from 32 host SCHED_FIFO preemptors), 100 runs each. Throughput measured of read lock/unlock iterations per second.

Quoted 5 lines
Quoted 3 lines
                        Baseline        Optimized
Mean throughput         66,980 iter/s   97,719 iter/s   (+46%)
Lock hold time (mean)   1,069 us        ~0 us

Excellent performance improvement!

Thanks. :)

Quoted 5 lines

It would be good to simplify the management of the blocked-tasks lists, and to make it more exact, as in never unnecessarily priority-boost a task. But it is not like people have been complaining, at least not to me. And earlier attempts in that direction added more mess than simplification. :-(

Interesting. I might look into the boosting logic to see whether we can avoid boosting certain tasks depending on whether they help the grace period complete or not. Thank you for the suggestion.

Quoted 11 lines
Quoted 10 lines

The optimized version maintains stable performance with essentially close to zero rnp->lock overhead.

rcutorture Testing
------------------
TREE03 Testing with rcutorture without RCU or hotplug errors. More testing is in progress.

Note: I have added a CONFIG_RCU_PER_CPU_BLOCKED_LISTS to guard the feature but the plan is to eventually turn this on all the time.

Quoted 7 lines

Yes, Aravinda, Gopinath, and I did publish that paper back in the day (with Aravinda having done almost all the work), but it was an artificial workload. Which is OK given that it was an academic effort. It has also provided some entertainment, for example, an audience member asking me if I was aware of this work in a linguistic-kill-shot manner. ;-)

So are we finally seeing this effect in the wild?

This patch set is also targeting a synthetic test I wrote to see if I could reproduce a preemption problem. I know several instances over the years where my teams (mainly at Google) were trying to resolve spin lock preemption inside virtual machines by boosting vCPU threads. In the spirit of RCU performance and VMs, we should probably optimize node locking IMO, but I do see your point of view about optimizing real-world use cases as well.

What bothers me about the current state of affairs is that even without any grace period in progress, any task blocking in an RCU Read Side critical section will take a (almost-)global lock that is shared by other CPUs who might also be preempting/blocking RCU readers. Further, if this happens to be a vCPU that was preempted while holding the node lock, then every other vCPU thread that blocks in an RCU critical section will also block and end up slowing preemption down in the vCPU. My preference would be to keep the readers fast while moving the overhead to the slow path (the overhead being promoting tasks at the right time that were blocked). In fact, in these patches, I'm directly going to the node list if there is a grace period in progress.

Quoted 7 lines

The main point of this patch series is to avoid lock contention due to vCPU preemption, correct? If so, will we need similar work on the other locks in the Linux kernel, both within RCU and elsewhere? I vaguely recall your doing some work along those lines a few years back, and maybe Thomas Gleixner's deferred-preemption work could help with this. Or not, who knows? Keeping the hypervisor informed of lock state is not necessarily free.

Yes, I did some work on this at Google, but it turned out to be a very fragmented effort in terms of where (which subsystem - KVM, scheduler etc) should we do the priority boosting of vCPU threads. In the end, we just ended up with an internal prototype that was not upstreamable but worked pretty well and only had time for production (a lesson I learned there is we should probably work on upstream solutions first, but life is not that easy sometimes).

About the deferred-preemption, I believe Steven Rostedt at one point was looking at that for VMs, but that effort stalled as Peter is concerned about doing that would mess up the scheduler. The idea (AFAIU) is to use the rseq page to communicate locking information between vCPU threads and the host and then let the host avoid vCPU preemption - but the scheduler needs to do something with that information. Otherwise, it's no use.

Quoted 24 lines

Also if so, would the following rather simpler patch do the same trick, if accompanied by CONFIG_RCU_FANOUT_LEAF=1?

------------------------------------------------------------------------

kernel/rcu/Kconfig +3 -4
index 6a319e2926589..04dbee983b37d 100644
@@ -198,9 +198,9 @@ config RCU_FANOUT
 
 config RCU_FANOUT_LEAF
 	int "Tree-based hierarchical RCU leaf-level fanout value"
-	range 2 64 if 64BIT && !RCU_STRICT_GRACE_PERIOD
-	range 2 32 if !64BIT && !RCU_STRICT_GRACE_PERIOD
-	range 2 3 if RCU_STRICT_GRACE_PERIOD
+	range 1 64 if 64BIT && !RCU_STRICT_GRACE_PERIOD
+	range 1 32 if !64BIT && !RCU_STRICT_GRACE_PERIOD
+	range 1 3 if RCU_STRICT_GRACE_PERIOD
 	depends on TREE_RCU && RCU_EXPERT>  	default 16 if !RCU_STRICT_GRACE_PERIOD
 	default 2 if RCU_STRICT_GRACE_PERIOD
 
------------------------------------------------------------------------
Quoted 2 lines

This passes a quick 20-minute rcutorture smoke test. Does it provide similar performance benefits?

I tried this out, and it also brings down the contention and solves the problem I saw (in testing so far).

Would this work also if the test had grace periods init/cleanup racing with preempted RCU read-side critical sections? I'm doing longer tests now to see how this performs under GP-stress, versus my solution. I am also seeing that with just the node lists, not per-cpu list, I see a dramatic throughput drop after some amount of time, but I can't explain it. And I do not see this with the per-cpu list solution (I'm currently testing if I see the same throughput drop with the fan-out solution you proposed).

I'm also wondering whether relying on the user to set FANOUT_LEAF to 1 is reasonable, considering this is not a default. Are you suggesting defaulting to this for small systems? If not, then I guess the optimization will not be enabled by default. Eventually, with this patch set, if we are moving forward with this approach, I will remove the config option for per-CPU block list altogether so that it is enabled by default. That's kind of my plan if we agreed on this, but it is just an RFC stage :).

thanks,

- Joel

#23 lore raw
Quoted 38 lines · Joel Fernandes
Quoted 24 lines

Also if so, would the following rather simpler patch do the same trick, if accompanied by CONFIG_RCU_FANOUT_LEAF=1?

------------------------------------------------------------------------

kernel/rcu/Kconfig +3 -4
index 6a319e2926589..04dbee983b37d 100644
@@ -198,9 +198,9 @@ config RCU_FANOUT
 
 config RCU_FANOUT_LEAF
 	int "Tree-based hierarchical RCU leaf-level fanout value"
-	range 2 64 if 64BIT && !RCU_STRICT_GRACE_PERIOD
-	range 2 32 if !64BIT && !RCU_STRICT_GRACE_PERIOD
-	range 2 3 if RCU_STRICT_GRACE_PERIOD
+	range 1 64 if 64BIT && !RCU_STRICT_GRACE_PERIOD
+	range 1 32 if !64BIT && !RCU_STRICT_GRACE_PERIOD
+	range 1 3 if RCU_STRICT_GRACE_PERIOD
 	depends on TREE_RCU && RCU_EXPERT>  	default 16 if !RCU_STRICT_GRACE_PERIOD
 	default 2 if RCU_STRICT_GRACE_PERIOD
 
------------------------------------------------------------------------
Quoted 2 lines

This passes a quick 20-minute rcutorture smoke test. Does it provide similar performance benefits?

I tried this out, and it also brings down the contention and solves the problem I saw (in testing so far).

Would this work also if the test had grace periods init/cleanup racing with preempted RCU read-side critical sections? I'm doing longer tests now to see how this performs under GP-stress, versus my solution. I am also seeing that with just the node lists, not per-cpu list, I see a dramatic throughput drop after some amount of time, but I can't explain it. And I do not see this with the per-cpu list solution (I'm currently testing if I see the same throughput drop with the fan-out solution you proposed).

Quoted 7 lines

I'm also wondering whether relying on the user to set FANOUT_LEAF to 1 is reasonable, considering this is not a default. Are you suggesting defaulting to this for small systems? If not, then I guess the optimization will not be enabled by default. Eventually, with this patch set, if we are moving forward with this approach, I will remove the config option for per-CPU block list altogether so that it is enabled by default. That's kind of my plan if we agreed on this, but it is just an RFC stage 🙂.

So the fanout solution works great when there are grace periods in progress. I see no throughput drop, and consistent performance with read site critical sections. However, if we switch to having no grace periods continuously happening in progress, I can see the throughput dropping quite a bit here (-30%). I can't explain that, but I do not see that issue with per-CPU lists.

With the per-cpu list scheme, blocking does not involve the node at all, as long as there is no grace period in progress. So, in that sense, per-CPU blocked list is completely detached from RCU - it is a bit like lazy RCU in the sense instead of a callback, it is the blocking task in a per-cpu list, relieving RCU of the burden.

Maybe the extra layer of the node tree (with fanout == 1) somehow adds unnecessary overhead that does not exist with Per CPU lists? Even though there is this throughput drop, it still does better than baseline with a common RCU node.

Based on this, I would say per-cpu blocked list is still worth doing. Thoughts?

- Joel

maintainer
#24 lore raw
Quoted 49 lines · Joel Fernandes
Quoted 38 lines · Joel Fernandes
Quoted 24 lines

Also if so, would the following rather simpler patch do the same trick, if accompanied by CONFIG_RCU_FANOUT_LEAF=1?

------------------------------------------------------------------------

kernel/rcu/Kconfig +3 -4
index 6a319e2926589..04dbee983b37d 100644
@@ -198,9 +198,9 @@ config RCU_FANOUT
 
 config RCU_FANOUT_LEAF
 	int "Tree-based hierarchical RCU leaf-level fanout value"
-	range 2 64 if 64BIT && !RCU_STRICT_GRACE_PERIOD
-	range 2 32 if !64BIT && !RCU_STRICT_GRACE_PERIOD
-	range 2 3 if RCU_STRICT_GRACE_PERIOD
+	range 1 64 if 64BIT && !RCU_STRICT_GRACE_PERIOD
+	range 1 32 if !64BIT && !RCU_STRICT_GRACE_PERIOD
+	range 1 3 if RCU_STRICT_GRACE_PERIOD
 	depends on TREE_RCU && RCU_EXPERT>  	default 16 if !RCU_STRICT_GRACE_PERIOD
 	default 2 if RCU_STRICT_GRACE_PERIOD
 
------------------------------------------------------------------------
Quoted 2 lines

This passes a quick 20-minute rcutorture smoke test. Does it provide similar performance benefits?

I tried this out, and it also brings down the contention and solves the problem I saw (in testing so far).

Would this work also if the test had grace periods init/cleanup racing with preempted RCU read-side critical sections? I'm doing longer tests now to see how this performs under GP-stress, versus my solution. I am also seeing that with just the node lists, not per-cpu list, I see a dramatic throughput drop after some amount of time, but I can't explain it. And I do not see this with the per-cpu list solution (I'm currently testing if I see the same throughput drop with the fan-out solution you proposed).

Quoted 7 lines

I'm also wondering whether relying on the user to set FANOUT_LEAF to 1 is reasonable, considering this is not a default. Are you suggesting defaulting to this for small systems? If not, then I guess the optimization will not be enabled by default. Eventually, with this patch set, if we are moving forward with this approach, I will remove the config option for per-CPU block list altogether so that it is enabled by default. That's kind of my plan if we agreed on this, but it is just an RFC stage 🙂.

Quoted 5 lines

So the fanout solution works great when there are grace periods in progress. I see no throughput drop, and consistent performance with read site critical sections. However, if we switch to having no grace periods continuously happening in progress, I can see the throughput dropping quite a bit here (-30%). I can't explain that, but I do not see that issue with per-CPU lists.

Might this be due to the change in number of tasks? Not having the thread that continuously runs grace periods might be affecting scheduling decisions, and with CPU overcommit, those scheduling decisions can cause large changes in throughput. Plus there are other spinlocks that might be subject to vCPU preemption, including the various scheduler spinlocks.

Quoted 5 lines

With the per-cpu list scheme, blocking does not involve the node at all, as long as there is no grace period in progress. So, in that sense, per-CPU blocked list is completely detached from RCU - it is a bit like lazy RCU in the sense instead of a callback, it is the blocking task in a per-cpu list, relieving RCU of the burden.

Unless I am seriously misreading your patch, the grace-period kthread still acquires your per-CPU locks. Also, reducing the number of grace periods should *reduce* contention on the rcu_node ->lock.

Quoted 5 lines

Maybe the extra layer of the node tree (with fanout == 1) somehow adds unnecessary overhead that does not exist with Per CPU lists? Even though there is this throughput drop, it still does better than baseline with a common RCU node.

Based on this, I would say per-cpu blocked list is still worth doing. Thoughts?

I think that we need to understand the differences before jumping to conclusions. There are a lot of possible reasons for changes in throughput, especially given the CPU overload. After all, queuing theory suggests high variance in that case, possibly even on exactly the same setup.

Thanx, Paul

author maintainer
#25 lore raw
Quoted 56 lines · Paul E. McKenney
Quoted 49 lines · Joel Fernandes
Quoted 38 lines · Joel Fernandes
Quoted 24 lines

Also if so, would the following rather simpler patch do the same trick, if accompanied by CONFIG_RCU_FANOUT_LEAF=1?

------------------------------------------------------------------------

kernel/rcu/Kconfig +3 -4
index 6a319e2926589..04dbee983b37d 100644
@@ -198,9 +198,9 @@ config RCU_FANOUT
 
 config RCU_FANOUT_LEAF
 	int "Tree-based hierarchical RCU leaf-level fanout value"
-	range 2 64 if 64BIT && !RCU_STRICT_GRACE_PERIOD
-	range 2 32 if !64BIT && !RCU_STRICT_GRACE_PERIOD
-	range 2 3 if RCU_STRICT_GRACE_PERIOD
+	range 1 64 if 64BIT && !RCU_STRICT_GRACE_PERIOD
+	range 1 32 if !64BIT && !RCU_STRICT_GRACE_PERIOD
+	range 1 3 if RCU_STRICT_GRACE_PERIOD
 	depends on TREE_RCU && RCU_EXPERT>  	default 16 if !RCU_STRICT_GRACE_PERIOD
 	default 2 if RCU_STRICT_GRACE_PERIOD
 
------------------------------------------------------------------------
Quoted 2 lines

This passes a quick 20-minute rcutorture smoke test. Does it provide similar performance benefits?

I tried this out, and it also brings down the contention and solves the problem I saw (in testing so far).

Would this work also if the test had grace periods init/cleanup racing with preempted RCU read-side critical sections? I'm doing longer tests now to see how this performs under GP-stress, versus my solution. I am also seeing that with just the node lists, not per-cpu list, I see a dramatic throughput drop after some amount of time, but I can't explain it. And I do not see this with the per-cpu list solution (I'm currently testing if I see the same throughput drop with the fan-out solution you proposed).

Quoted 7 lines

I'm also wondering whether relying on the user to set FANOUT_LEAF to 1 is reasonable, considering this is not a default. Are you suggesting defaulting to this for small systems? If not, then I guess the optimization will not be enabled by default. Eventually, with this patch set, if we are moving forward with this approach, I will remove the config option for per-CPU block list altogether so that it is enabled by default. That's kind of my plan if we agreed on this, but it is just an RFC stage 🙂.

Quoted 5 lines

So the fanout solution works great when there are grace periods in progress. I see no throughput drop, and consistent performance with read site critical sections. However, if we switch to having no grace periods continuously happening in progress, I can see the throughput dropping quite a bit here (-30%). I can't explain that, but I do not see that issue with per-CPU lists.

Quoted 5 lines

Might this be due to the change in number of tasks? Not having the thread that continuously runs grace periods might be affecting scheduling decisions, and with CPU overcommit, those scheduling decisions can cause large changes in throughput. Plus there are other spinlocks that might be subject to vCPU preemption, including the various scheduler spinlocks.

Yeah these are all possible, currently studying it more :)

Quoted 8 lines
Quoted 5 lines

With the per-cpu list scheme, blocking does not involve the node at all, as long as there is no grace period in progress. So, in that sense, per-CPU blocked list is completely detached from RCU - it is a bit like lazy RCU in the sense instead of a callback, it is the blocking task in a per-cpu list, relieving RCU of the burden.

Unless I am seriously misreading your patch, the grace-period kthread still acquires your per-CPU locks.

Yes, but I am not triggering grace periods (in the tests where I am expecting an improvement). It is in those tests that I am seeing the throughput drop with FANOUT, but let me confirm that again. I did run it 200 times and notice this. I'm not sure what else a fanout of one for leaves does, but this is my chance to learn about it :).

I am saying when there is no GPs active (that is when the optimization in these patches is active). In one of the patches, if grace period is in progress or already started, I do not trigger the optimization. The optimization is only when grace periods are not active. This is similar to lazy RCU, where, if we have active grace periods in progress, we don't really make new RCU callbacks lazy since it is pointless.

Quoted 1 line

Also, reducing the number of grace periods> should *reduce* contention on the

rcu_node ->lock.

Quoted 5 lines
Quoted 5 lines

Maybe the extra layer of the node tree (with fanout == 1) somehow adds unnecessary overhead that does not exist with Per CPU lists? Even though there is this throughput drop, it still does better than baseline with a common RCU node.

Quoted 7 lines
Quoted 1 line

Based on this, I would say per-cpu blocked list is still worth doing. Thoughts?

I think that we need to understand the differences before jumping to conclusions. There are a lot of possible reasons for changes in throughput, especially given the CPU overload. After all, queuing theory suggests high variance in that case, possibly even on exactly the same setup.

Sure, that's why I'm doing hundreds of runs to get repetitive results and cut back on the outliers. But it is quite challenging to study all possibilities given the time constraints. I'm trying to collect traces as much as I can and study them. The synchronize RCU latency that I just improved, for instance, came from one of such exercises.

Thanks.

maintainer
#26 lore raw
Quoted 59 lines · Joel Fernandes
Quoted 56 lines · Paul E. McKenney
Quoted 54 lines · Joel Fernandes
Quoted 38 lines · Joel Fernandes
Quoted 24 lines

Also if so, would the following rather simpler patch do the same trick, if accompanied by CONFIG_RCU_FANOUT_LEAF=1?

------------------------------------------------------------------------

kernel/rcu/Kconfig +3 -4
index 6a319e2926589..04dbee983b37d 100644
@@ -198,9 +198,9 @@ config RCU_FANOUT
 
 config RCU_FANOUT_LEAF
 	int "Tree-based hierarchical RCU leaf-level fanout value"
-	range 2 64 if 64BIT && !RCU_STRICT_GRACE_PERIOD
-	range 2 32 if !64BIT && !RCU_STRICT_GRACE_PERIOD
-	range 2 3 if RCU_STRICT_GRACE_PERIOD
+	range 1 64 if 64BIT && !RCU_STRICT_GRACE_PERIOD
+	range 1 32 if !64BIT && !RCU_STRICT_GRACE_PERIOD
+	range 1 3 if RCU_STRICT_GRACE_PERIOD
 	depends on TREE_RCU && RCU_EXPERT>  	default 16 if !RCU_STRICT_GRACE_PERIOD
 	default 2 if RCU_STRICT_GRACE_PERIOD
 
------------------------------------------------------------------------
Quoted 2 lines

This passes a quick 20-minute rcutorture smoke test. Does it provide similar performance benefits?

I tried this out, and it also brings down the contention and solves the problem I saw (in testing so far).

Would this work also if the test had grace periods init/cleanup racing with preempted RCU read-side critical sections? I'm doing longer tests now to see how this performs under GP-stress, versus my solution. I am also seeing that with just the node lists, not per-cpu list, I see a dramatic throughput drop after some amount of time, but I can't explain it. And I do not see this with the per-cpu list solution (I'm currently testing if I see the same throughput drop with the fan-out solution you proposed).

Quoted 7 lines

I'm also wondering whether relying on the user to set FANOUT_LEAF to 1 is reasonable, considering this is not a default. Are you suggesting defaulting to this for small systems? If not, then I guess the optimization will not be enabled by default. Eventually, with this patch set, if we are moving forward with this approach, I will remove the config option for per-CPU block list altogether so that it is enabled by default. That's kind of my plan if we agreed on this, but it is just an RFC stage 🙂.

So the fanout solution works great when there are grace periods in progress. I see no throughput drop, and consistent performance with read site critical sections. However, if we switch to having no grace periods continuously happening in progress, I can see the throughput dropping quite a bit here (-30%). I can't explain that, but I do not see that issue with per-CPU lists.

Quoted 7 lines
Quoted 5 lines

Might this be due to the change in number of tasks? Not having the thread that continuously runs grace periods might be affecting scheduling decisions, and with CPU overcommit, those scheduling decisions can cause large changes in throughput. Plus there are other spinlocks that might be subject to vCPU preemption, including the various scheduler spinlocks.

Yeah these are all possible, currently studying it more :)

Looking forward to seeing what you find!

Quoted 6 lines
Quoted 6 lines
Quoted 5 lines

With the per-cpu list scheme, blocking does not involve the node at all, as long as there is no grace period in progress. So, in that sense, per-CPU blocked list is completely detached from RCU - it is a bit like lazy RCU in the sense instead of a callback, it is the blocking task in a per-cpu list, relieving RCU of the burden.

Quoted 8 lines
Quoted 2 lines

Unless I am seriously misreading your patch, the grace-period kthread still acquires your per-CPU locks.

Yes, but I am not triggering grace periods (in the tests where I am expecting an improvement). It is in those tests that I am seeing the throughput drop with FANOUT, but let me confirm that again. I did run it 200 times and notice this. I'm not sure what else a fanout of one for leaves does, but this is my chance to learn about it :).

Well, TREE09 has tested at least one aspect of this configuration quite thoroughly over the years. ;-)

Quoted 6 lines

I am saying when there is no GPs active (that is when the optimization in these patches is active). In one of the patches, if grace period is in progress or already started, I do not trigger the optimization. The optimization is only when grace periods are not active. This is similar to lazy RCU, where, if we have active grace periods in progress, we don't really make new RCU callbacks lazy since it is pointless.

Interesting. When there is no grace period is also when it is least harmful to acquire the rcu_node structure's ->lock.

Quoted 15 lines
Quoted 1 line

Also, reducing the number of grace periods> should *reduce* contention on the

rcu_node ->lock.

Quoted 5 lines
Quoted 5 lines

Maybe the extra layer of the node tree (with fanout == 1) somehow adds unnecessary overhead that does not exist with Per CPU lists? Even though there is this throughput drop, it still does better than baseline with a common RCU node.

Quoted 7 lines
Quoted 1 line

Based on this, I would say per-cpu blocked list is still worth doing. Thoughts?

I think that we need to understand the differences before jumping to conclusions. There are a lot of possible reasons for changes in throughput, especially given the CPU overload. After all, queuing theory suggests high variance in that case, possibly even on exactly the same setup.

Quoted 5 lines

Sure, that's why I'm doing hundreds of runs to get repetitive results and cut back on the outliers. But it is quite challenging to study all possibilities given the time constraints. I'm trying to collect traces as much as I can and study them. The synchronize RCU latency that I just improved, for instance, came from one of such exercises.

There is absolutely nothing wrong with experiments!

Thanx, Paul

maintainer
#27 lore raw
In reply to Joel Fernandes
Quoted 65 lines · Joel Fernandes

Hi Paul,

Quoted 49 lines · Paul E. McKenney
Quoted 48 lines · Joel Fernandes

When a task is preempted while holding an RCU read-side lock, the kernel must track it on the rcu_node's blocked task list. This requires acquiring rnp->lock shared by all CPUs in that node's subtree.

Posting this as RFC for early feedback. There could be bugs lurking, especially related to expedited GPs which I have not yet taken a close look at. Several TODOs are added. It passed light TREE03 rcutorture testing.

On systems with 16 or fewer CPUs, the RCU hierarchy often has just a single rcu_node, making rnp->lock effectively a global lock for all blocked task operations. Every context switch where a task holds an RCU read-side lock contends on this single lock.

Enter Virtualization
--------------------
In virtualized environments, the problem becomes dramatically worse due to vCPU preemption. Research from USENIX ATC'17 ("The RCU-Reader Preemption Problem in VMs" by Gopinath and Paul McKenney) [1] explores the issue that RCU reader preemption in VMs causes multi-second latency spikes and huge increases in grace period duration.

When a vCPU is preempted by the hypervisor while holding rnp->lock, other vCPUs spin waiting for a lock holder that isn't even running. In testing with host RT preemptors to inject vCPU preemption, lock hold times extended from ~4us to over 4000us - a 1000x increase.

The Solution
------------
This series introduces per-CPU lists for tracking blocked RCU readers. The key insight is that when no grace period is active, blocked tasks complete their critical sections before really requiring any rnp locking.

1. Fast path: At context switch, Add the task only to the per-CPU list - no rnp->lock needed.

2. Promotion on demand: When a grace period starts, promote tasks from per-CPU lists to the rcu_node list.

3. Normal path: If a grace period is already waiting, tasks go directly to the rcu_node list as before.

Results
-------
Testing with 64 reader threads under vCPU preemption from 32 host SCHED_FIFO preemptors), 100 runs each. Throughput measured of read lock/unlock iterations per second.

Quoted 5 lines
Quoted 3 lines
                        Baseline        Optimized
Mean throughput         66,980 iter/s   97,719 iter/s   (+46%)
Lock hold time (mean)   1,069 us        ~0 us

Excellent performance improvement!

Thanks. :)

Quoted 5 lines

It would be good to simplify the management of the blocked-tasks lists, and to make it more exact, as in never unnecessarily priority-boost a task. But it is not like people have been complaining, at least not to me. And earlier attempts in that direction added more mess than simplification. :-(

Quoted 3 lines

Interesting. I might look into the boosting logic to see whether we can avoid boosting certain tasks depending on whether they help the grace period complete or not. Thank you for the suggestion.

Just so you know, all of my simplification efforts thus far have instead made it more complex, but who knows what I might have been missing?

Quoted 17 lines
Quoted 17 lines
Quoted 10 lines

The optimized version maintains stable performance with essentially close to zero rnp->lock overhead.

rcutorture Testing
------------------
TREE03 Testing with rcutorture without RCU or hotplug errors. More testing is in progress.

Note: I have added a CONFIG_RCU_PER_CPU_BLOCKED_LISTS to guard the feature but the plan is to eventually turn this on all the time.

Yes, Aravinda, Gopinath, and I did publish that paper back in the day (with Aravinda having done almost all the work), but it was an artificial workload. Which is OK given that it was an academic effort. It has also provided some entertainment, for example, an audience member asking me if I was aware of this work in a linguistic-kill-shot manner. ;-)

Quoted 8 lines
Quoted 1 line

So are we finally seeing this effect in the wild?

This patch set is also targeting a synthetic test I wrote to see if I could reproduce a preemption problem. I know several instances over the years where my teams (mainly at Google) were trying to resolve spin lock preemption inside virtual machines by boosting vCPU threads. In the spirit of RCU performance and VMs, we should probably optimize node locking IMO, but I do see your point of view about optimizing real-world use cases as well.

Also taking care of all spinlocks instead of doing large numbers of per-spinlock workarounds would be good. There are a *lot* of spinlocks in the Linux kernel!

Quoted 10 lines

What bothers me about the current state of affairs is that even without any grace period in progress, any task blocking in an RCU Read Side critical section will take a (almost-)global lock that is shared by other CPUs who might also be preempting/blocking RCU readers. Further, if this happens to be a vCPU that was preempted while holding the node lock, then every other vCPU thread that blocks in an RCU critical section will also block and end up slowing preemption down in the vCPU. My preference would be to keep the readers fast while moving the overhead to the slow path (the overhead being promoting tasks at the right time that were blocked). In fact, in these patches, I'm directly going to the node list if there is a grace period in progress.

Not "(almost-)global"!

That lock replicates itself automatically with increasing numbers of CPUs. That 16 used to be the full (at the time) 32-bit cpumask, but we decreased it to 16 based on performance feedback from Andi Kleen back in the day. If we are seeing real-world contention on that lock in real-world workloads on real-world systems, further adjustments could be made, either reducing CONFIG_RCU_FANOUT_LEAF further or offloading the lock, where your series is one example of the latter.

I could easily believe that the vCPU preemption problem needs to be addressed, but doing so on a per-spinlock basis would lead to greatly increased complexity throughout the kernel, not just RCU.

Quoted 8 lines
Quoted 7 lines

The main point of this patch series is to avoid lock contention due to vCPU preemption, correct? If so, will we need similar work on the other locks in the Linux kernel, both within RCU and elsewhere? I vaguely recall your doing some work along those lines a few years back, and maybe Thomas Gleixner's deferred-preemption work could help with this. Or not, who knows? Keeping the hypervisor informed of lock state is not necessarily free.

Quoted 6 lines

Yes, I did some work on this at Google, but it turned out to be a very fragmented effort in terms of where (which subsystem - KVM, scheduler etc) should we do the priority boosting of vCPU threads. In the end, we just ended up with an internal prototype that was not upstreamable but worked pretty well and only had time for production (a lesson I learned there is we should probably work on upstream solutions first, but life is not that easy sometimes).

Which is one reason deferred preemption would be attractive.

Quoted 6 lines

About the deferred-preemption, I believe Steven Rostedt at one point was looking at that for VMs, but that effort stalled as Peter is concerned about doing that would mess up the scheduler. The idea (AFAIU) is to use the rseq page to communicate locking information between vCPU threads and the host and then let the host avoid vCPU preemption - but the scheduler needs to do something with that information. Otherwise, it's no use.

Has deferred preemption for userspace locking also stalled? If not, then the scheduler's support for userspace should apply directly to guest OSes, right?

Quoted 30 lines
Quoted 24 lines

Also if so, would the following rather simpler patch do the same trick, if accompanied by CONFIG_RCU_FANOUT_LEAF=1?

------------------------------------------------------------------------

kernel/rcu/Kconfig +3 -4
index 6a319e2926589..04dbee983b37d 100644
@@ -198,9 +198,9 @@ config RCU_FANOUT
 
 config RCU_FANOUT_LEAF
 	int "Tree-based hierarchical RCU leaf-level fanout value"
-	range 2 64 if 64BIT && !RCU_STRICT_GRACE_PERIOD
-	range 2 32 if !64BIT && !RCU_STRICT_GRACE_PERIOD
-	range 2 3 if RCU_STRICT_GRACE_PERIOD
+	range 1 64 if 64BIT && !RCU_STRICT_GRACE_PERIOD
+	range 1 32 if !64BIT && !RCU_STRICT_GRACE_PERIOD
+	range 1 3 if RCU_STRICT_GRACE_PERIOD
 	depends on TREE_RCU && RCU_EXPERT>  	default 16 if !RCU_STRICT_GRACE_PERIOD
 	default 2 if RCU_STRICT_GRACE_PERIOD
 
------------------------------------------------------------------------
Quoted 2 lines

This passes a quick 20-minute rcutorture smoke test. Does it provide similar performance benefits?

I tried this out, and it also brings down the contention and solves the problem I saw (in testing so far).

Quoted 7 lines

Would this work also if the test had grace periods init/cleanup racing with preempted RCU read-side critical sections? I'm doing longer tests now to see how this performs under GP-stress, versus my solution. I am also seeing that with just the node lists, not per-cpu list, I see a dramatic throughput drop after some amount of time, but I can't explain it. And I do not see this with the per-cpu list solution (I'm currently testing if I see the same throughput drop with the fan-out solution you proposed).

Might the throughput drop be due to increased load on the host? Another possibility is that tasks/vCPUs got shuffled so as to increase the probability of preemption.

Also, doesn't your patch also cause the grace-period kthread to acquire that per-CPU lock, thus also possibly resulting in contention, vCPU preemption, and so on?

Quoted 7 lines

I'm also wondering whether relying on the user to set FANOUT_LEAF to 1 is reasonable, considering this is not a default. Are you suggesting defaulting to this for small systems? If not, then I guess the optimization will not be enabled by default. Eventually, with this patch set, if we are moving forward with this approach, I will remove the config option for per-CPU block list altogether so that it is enabled by default. That's kind of my plan if we agreed on this, but it is just an RFC stage :).

Right now, we are experimenting, so the usability issue is less pressing. Once we find out what is really going on for real-world systems, we can make adjustments if and as appropriate, said adjustments including usability.

Thanx, Paul

#28 lore raw
Quoted 6 lines · On Tue, 6 Jan 2026 11:17:19 -0800 "Paul E. McKenney" <[email protected]> wrote:
Quoted 3 lines

Interesting. I might look into the boosting logic to see whether we can avoid boosting certain tasks depending on whether they help the grace period complete or not. Thank you for the suggestion.

Just so you know, all of my simplification efforts thus far have instead made it more complex, but who knows what I might have been missing?

Maybe you are too smart to make it simple? ;-)

Quoted 3 lines

I could easily believe that the vCPU preemption problem needs to be addressed, but doing so on a per-spinlock basis would lead to greatly increased complexity throughout the kernel, not just RCU.

Agreed.

Quoted 9 lines
Quoted 9 lines
Quoted 8 lines

The main point of this patch series is to avoid lock contention due to vCPU preemption, correct? If so, will we need similar work on the other locks in the Linux kernel, both within RCU and elsewhere? I vaguely recall your doing some work along those lines a few years back, and maybe Thomas Gleixner's deferred-preemption work could help with this. Or not, who knows? Keeping the hypervisor informed of lock state is not necessarily free.

Quoted 8 lines
Quoted 6 lines

Yes, I did some work on this at Google, but it turned out to be a very fragmented effort in terms of where (which subsystem - KVM, scheduler etc) should we do the priority boosting of vCPU threads. In the end, we just ended up with an internal prototype that was not upstreamable but worked pretty well and only had time for production (a lesson I learned there is we should probably work on upstream solutions first, but life is not that easy sometimes).

Which is one reason deferred preemption would be attractive.

Yes. That's why I've been pushing it.

Quoted 11 lines
Quoted 7 lines

About the deferred-preemption, I believe Steven Rostedt at one point was looking at that for VMs, but that effort stalled as Peter is concerned about doing that would mess up the scheduler. The idea (AFAIU) is to use the rseq page to communicate locking information between vCPU threads and the host and then let the host avoid vCPU preemption - but the scheduler needs to do something with that information. Otherwise, it's no use.

Has deferred preemption for userspace locking also stalled? If not, then the scheduler's support for userspace should apply directly to guest OSes, right?

No, the user space deferred preemption is still moving along nicely (I believe Thomas has completed most of it). The issue here is that the deferred happens before going back to user space. That's a different location than going back to the guest. The logic needs to be in that path too.

One thing that Peter Zijlstra pushed was the limited amount of time that deferred wait may happen. He says user space spinlocks are a bad design, but it has been proven for that they are currently the most efficient when coming to very short critical sections. That is, where the critical section is shorter than the cost of a system call. Thus, he forces the deferred scheduling to be at most 50us max (he's also suggested less than that).

But when it comes to the guest, where kernel spinlocks are user space spinlocks, and can be held for more than 50us, I would like a way to have the guests defer the scheduling for even longer than user space spin locks.

-- Steve

maintainer
#29 lore raw
Quoted 11 lines · Steven Rostedt
Quoted 6 lines · On Tue, 6 Jan 2026 11:17:19 -0800 "Paul E. McKenney" <[email protected]> wrote:
Quoted 3 lines

Interesting. I might look into the boosting logic to see whether we can avoid boosting certain tasks depending on whether they help the grace period complete or not. Thank you for the suggestion.

Just so you know, all of my simplification efforts thus far have instead made it more complex, but who knows what I might have been missing?

Maybe you are too smart to make it simple? ;-)

There is the old adage that the complexity of any software artifact grows to just barely exceed the capabilities of those working on it. ;-)

But all that aside, getting fresh eyes on it would be a good thing.

Quoted 21 lines
Quoted 3 lines

I could easily believe that the vCPU preemption problem needs to be addressed, but doing so on a per-spinlock basis would lead to greatly increased complexity throughout the kernel, not just RCU.

Agreed.

Quoted 15 lines
Quoted 14 lines
Quoted 7 lines

The main point of this patch series is to avoid lock contention due to vCPU preemption, correct? If so, will we need similar work on the other locks in the Linux kernel, both within RCU and elsewhere? I vaguely recall your doing some work along those lines a few years back, and maybe Thomas Gleixner's deferred-preemption work could help with this. Or not, who knows? Keeping the hypervisor informed of lock state is not necessarily free.

Yes, I did some work on this at Google, but it turned out to be a very fragmented effort in terms of where (which subsystem - KVM, scheduler etc) should we do the priority boosting of vCPU threads. In the end, we just ended up with an internal prototype that was not upstreamable but worked pretty well and only had time for production (a lesson I learned there is we should probably work on upstream solutions first, but life is not that easy sometimes).

Quoted 3 lines
Quoted 1 line

Which is one reason deferred preemption would be attractive.

Yes. That's why I've been pushing it.

Very good to hear!

Quoted 11 lines
Quoted 10 lines
Quoted 6 lines

About the deferred-preemption, I believe Steven Rostedt at one point was looking at that for VMs, but that effort stalled as Peter is concerned about doing that would mess up the scheduler. The idea (AFAIU) is to use the rseq page to communicate locking information between vCPU threads and the host and then let the host avoid vCPU preemption - but the scheduler needs to do something with that information. Otherwise, it's no use.

Has deferred preemption for userspace locking also stalled? If not, then the scheduler's support for userspace should apply directly to guest OSes, right?

Quoted 5 lines

No, the user space deferred preemption is still moving along nicely (I believe Thomas has completed most of it). The issue here is that the deferred happens before going back to user space. That's a different location than going back to the guest. The logic needs to be in that path too.

OK, got it, thank you!

Quoted 10 lines

One thing that Peter Zijlstra pushed was the limited amount of time that deferred wait may happen. He says user space spinlocks are a bad design, but it has been proven for that they are currently the most efficient when coming to very short critical sections. That is, where the critical section is shorter than the cost of a system call. Thus, he forces the deferred scheduling to be at most 50us max (he's also suggested less than that).

But when it comes to the guest, where kernel spinlocks are user space spinlocks, and can be held for more than 50us, I would like a way to have the guests defer the scheduling for even longer than user space spin locks.

I would *hope* that the rcu_node ->lock instances are held for less than 50us! At least in the absence of SMIs, NMIs, or vCPU preemption on systems with at least 100MHz core CPU clock frequency. Besides, SMIs, NMIs, vCPU preemption affect userspace locks, as do IRQs and softirqs.

Of course, hope springs eternal...

Thanx, Paul

author maintainer
#30 lore raw
Quoted 9 lines · Paul E. McKenney
Quoted 9 lines
Quoted 9 lines
Quoted 6 lines

About the deferred-preemption, I believe Steven Rostedt at one point was looking at that for VMs, but that effort stalled as Peter is concerned about doing that would mess up the scheduler. The idea (AFAIU) is to use the rseq page to communicate locking information between vCPU threads and the host and then let the host avoid vCPU preemption - but the scheduler needs to do something with that information. Otherwise, it's no use.

Has deferred preemption for userspace locking also stalled? If not, then the scheduler's support for userspace should apply directly to guest OSes, right?

Quoted 7 lines
Quoted 5 lines

No, the user space deferred preemption is still moving along nicely (I believe Thomas has completed most of it). The issue here is that the deferred happens before going back to user space. That's a different location than going back to the guest. The logic needs to be in that path too.

OK, got it, thank you!

There's also the challenge of sharing the locking information with the guest even when there is *no contention*. KVM being unaware of lock critical sections in the VM-exit path. Then after that wiring it up with the deffered preemption infra and moving beyond the 50 micro second limits. If we VM exited and then made a decision, I think we are easily going to blow past 50 micro seconds anyway.

But again to clarify, I didn't mean to use vCPU preemption as the driving usecase for this.. but I ran into it when I wrote a benchmark to see how RCU behaves in a VM.

- Joel

maintainer
#31 lore raw
Quoted 18 lines · Joel Fernandes
Quoted 15 lines · Paul E. McKenney
Quoted 14 lines
Quoted 9 lines
Quoted 6 lines

About the deferred-preemption, I believe Steven Rostedt at one point was looking at that for VMs, but that effort stalled as Peter is concerned about doing that would mess up the scheduler. The idea (AFAIU) is to use the rseq page to communicate locking information between vCPU threads and the host and then let the host avoid vCPU preemption - but the scheduler needs to do something with that information. Otherwise, it's no use.

Has deferred preemption for userspace locking also stalled? If not, then the scheduler's support for userspace should apply directly to guest OSes, right?

No, the user space deferred preemption is still moving along nicely (I believe Thomas has completed most of it). The issue here is that the deferred happens before going back to user space. That's a different location than going back to the guest. The logic needs to be in that path too.

Quoted 7 lines
Quoted 1 line

OK, got it, thank you!

There's also the challenge of sharing the locking information with the guest even when there is *no contention*. KVM being unaware of lock critical sections in the VM-exit path. Then after that wiring it up with the deffered preemption infra and moving beyond the 50 micro second limits. If we VM exited and then made a decision, I think we are easily going to blow past 50 micro seconds anyway.

Yes, the VM-exit path would need to do its part. Could the 50 microseconds be measured up to but not including the VM exit?

Quoted 3 lines

But again to clarify, I didn't mean to use vCPU preemption as the driving usecase for this.. but I ran into it when I wrote a benchmark to see how RCU behaves in a VM.

Me, I am just trying to keep the complexity down to a dull roar. So please do not take my pushback personally. "Just doing my job."

Thanx, Paul

#32 lore raw
In reply to Paul E. McKenney
Quoted 1 line · Paul E. McKenney

On Mon, Jan 05, 2026 at 07:55:18PM -0500, Joel Fernandes wrote:

[..]

Quoted 26 lines
Quoted 17 lines
Quoted 17 lines
Quoted 10 lines

The optimized version maintains stable performance with essentially close to zero rnp->lock overhead.

rcutorture Testing
------------------
TREE03 Testing with rcutorture without RCU or hotplug errors. More testing is in progress.

Note: I have added a CONFIG_RCU_PER_CPU_BLOCKED_LISTS to guard the feature but the plan is to eventually turn this on all the time.

Yes, Aravinda, Gopinath, and I did publish that paper back in the day (with Aravinda having done almost all the work), but it was an artificial workload. Which is OK given that it was an academic effort. It has also provided some entertainment, for example, an audience member asking me if I was aware of this work in a linguistic-kill-shot manner. ;-)

Quoted 8 lines
Quoted 1 line

So are we finally seeing this effect in the wild?

This patch set is also targeting a synthetic test I wrote to see if I could reproduce a preemption problem. I know several instances over the years where my teams (mainly at Google) were trying to resolve spin lock preemption inside virtual machines by boosting vCPU threads. In the spirit of RCU performance and VMs, we should probably optimize node locking IMO, but I do see your point of view about optimizing real-world use cases as well.

Quoted 3 lines

Also taking care of all spinlocks instead of doing large numbers of per-spinlock workarounds would be good. There are a *lot* of spinlocks in the Linux kernel!

I wouldn't call it a workaround yet. Avoiding lock contention by using per CPU list is an optimization we have done before right? (Example the synthetic RCU callback-flooding use case where we used a per-cpu list). We can call it defensive programming, if you will. ;-) Especially in the scheduler hot path where we are blocking/preempting. Again, I'm not saying we should do it for this case since we are still studying the issue, but just on the fact that we are optimizing a spin lock we acquire *a lot* shouldn't be categorized as a workaround in my opinion.

This blocking is even more likely on preempt RT in read-side critical sections. Again, I'm not saying that we should do this optimization, but I don't think we can ignore it. At least not based on the data I have so far.

Quoted 13 lines
Quoted 10 lines

What bothers me about the current state of affairs is that even without any grace period in progress, any task blocking in an RCU Read Side critical section will take a (almost-)global lock that is shared by other CPUs who might also be preempting/blocking RCU readers. Further, if this happens to be a vCPU that was preempted while holding the node lock, then every other vCPU thread that blocks in an RCU critical section will also block and end up slowing preemption down in the vCPU. My preference would be to keep the readers fast while moving the overhead to the slow path (the overhead being promoting tasks at the right time that were blocked). In fact, in these patches, I'm directly going to the node list if there is a grace period in progress.

Not "(almost-)global"!

Quoted 7 lines

That lock replicates itself automatically with increasing numbers of CPUs. That 16 used to be the full (at the time) 32-bit cpumask, but we decreased it to 16 based on performance feedback from Andi Kleen back in the day. If we are seeing real-world contention on that lock in real-world workloads on real-world systems, further adjustments could be made, either reducing CONFIG_RCU_FANOUT_LEAF further or offloading the lock, where your series is one example of the latter.

I meant it is global or almost global depending on the number of CPUs. So for example on an 8 CPU system with the default fanout, it is a global lock, correct?

Quoted 3 lines

I could easily believe that the vCPU preemption problem needs to be addressed, but doing so on a per-spinlock basis would lead to greatly increased complexity throughout the kernel, not just RCU.

I agree with this. I was not intending to solve this for the entire kernel, at first at least.

Quoted 10 lines
Quoted 6 lines

About the deferred-preemption, I believe Steven Rostedt at one point was looking at that for VMs, but that effort stalled as Peter is concerned about doing that would mess up the scheduler. The idea (AFAIU) is to use the rseq page to communicate locking information between vCPU threads and the host and then let the host avoid vCPU preemption - but the scheduler needs to do something with that information. Otherwise, it's no use.

Has deferred preemption for userspace locking also stalled? If not, then the scheduler's support for userspace should apply directly to guest OSes, right?

I don't think there have been any user space locking optimizations for preemption that has made it upstream (AFAIK). I know there were efforts, but I could be out of date there. I think the devil is in the details as well because user space optimizations cannot always be applied to guests in my experience. The VM exit path and the syscall entry/exit paths are quite different, including the API boundary.

Quoted 38 lines
Quoted 30 lines
Quoted 24 lines

Also if so, would the following rather simpler patch do the same trick, if accompanied by CONFIG_RCU_FANOUT_LEAF=1?

------------------------------------------------------------------------

kernel/rcu/Kconfig +3 -4
index 6a319e2926589..04dbee983b37d 100644
@@ -198,9 +198,9 @@ config RCU_FANOUT
 
 config RCU_FANOUT_LEAF
 	int "Tree-based hierarchical RCU leaf-level fanout value"
-	range 2 64 if 64BIT && !RCU_STRICT_GRACE_PERIOD
-	range 2 32 if !64BIT && !RCU_STRICT_GRACE_PERIOD
-	range 2 3 if RCU_STRICT_GRACE_PERIOD
+	range 1 64 if 64BIT && !RCU_STRICT_GRACE_PERIOD
+	range 1 32 if !64BIT && !RCU_STRICT_GRACE_PERIOD
+	range 1 3 if RCU_STRICT_GRACE_PERIOD
 	depends on TREE_RCU && RCU_EXPERT>  	default 16 if !RCU_STRICT_GRACE_PERIOD
 	default 2 if RCU_STRICT_GRACE_PERIOD
 
------------------------------------------------------------------------
Quoted 2 lines

This passes a quick 20-minute rcutorture smoke test. Does it provide similar performance benefits?

I tried this out, and it also brings down the contention and solves the problem I saw (in testing so far).

Quoted 7 lines

Would this work also if the test had grace periods init/cleanup racing with preempted RCU read-side critical sections? I'm doing longer tests now to see how this performs under GP-stress, versus my solution. I am also seeing that with just the node lists, not per-cpu list, I see a dramatic throughput drop after some amount of time, but I can't explain it. And I do not see this with the per-cpu list solution (I'm currently testing if I see the same throughput drop with the fan-out solution you proposed).

Quoted 1 line

Might the throughput drop be due to increased load on the host?

The load is constant with the benchmark, and the data is repeatable and consistent. So random load on the host is unlikely.

Quoted 6 lines

Another possibility is that tasks/vCPUs got shuffled so as to increase the probability of preemption.

Also, doesn't your patch also cause the grace-period kthread to acquire that per-CPU lock, thus also possibly resulting in contention, vCPU preemption, and so on?

Yes, I'm tracing it more. Even with baseline (without these patches), I see this throughput drop so it is worth investigating. I think it's something possibly like a lock convoy forming, but the fact that if I don't use RNP locking, the lock convoy disappears, and the throughput is completely stable. That tells me that that has something to do with that or something related. I also measured the exact RNP lock time and counted the number of contentions, so I am not really guessing here. The RNP lock is contended consistently. I think it's a great idea for me to extend this lock contention measurement to the run queue locks as well, for me to measure how they are doing (or even extending it to all locks, as you mentioned) - at least for me to confirm the theory that the same test severely contends other locks as well.

Quoted 8 lines
Quoted 7 lines

I'm also wondering whether relying on the user to set FANOUT_LEAF to 1 is reasonable, considering this is not a default. Are you suggesting defaulting to this for small systems? If not, then I guess the optimization will not be enabled by default. Eventually, with this patch set, if we are moving forward with this approach, I will remove the config option for per-CPU block list altogether so that it is enabled by default. That's kind of my plan if we agreed on this, but it is just an RFC stage :).

Quoted 4 lines

Right now, we are experimenting, so the usability issue is less pressing. Once we find out what is really going on for real-world systems, we can make adjustments if and as appropriate, said adjustments including usability.

Sure, thanks.

- Joel

maintainer
#33 lore raw
Quoted 42 lines · Joel Fernandes
Quoted 1 line · Paul E. McKenney

On Mon, Jan 05, 2026 at 07:55:18PM -0500, Joel Fernandes wrote:

[..]

Quoted 26 lines
Quoted 17 lines
Quoted 17 lines
Quoted 10 lines

The optimized version maintains stable performance with essentially close to zero rnp->lock overhead.

rcutorture Testing
------------------
TREE03 Testing with rcutorture without RCU or hotplug errors. More testing is in progress.

Note: I have added a CONFIG_RCU_PER_CPU_BLOCKED_LISTS to guard the feature but the plan is to eventually turn this on all the time.

Yes, Aravinda, Gopinath, and I did publish that paper back in the day (with Aravinda having done almost all the work), but it was an artificial workload. Which is OK given that it was an academic effort. It has also provided some entertainment, for example, an audience member asking me if I was aware of this work in a linguistic-kill-shot manner. ;-)

Quoted 8 lines
Quoted 1 line

So are we finally seeing this effect in the wild?

This patch set is also targeting a synthetic test I wrote to see if I could reproduce a preemption problem. I know several instances over the years where my teams (mainly at Google) were trying to resolve spin lock preemption inside virtual machines by boosting vCPU threads. In the spirit of RCU performance and VMs, we should probably optimize node locking IMO, but I do see your point of view about optimizing real-world use cases as well.

Quoted 3 lines

Also taking care of all spinlocks instead of doing large numbers of per-spinlock workarounds would be good. There are a *lot* of spinlocks in the Linux kernel!

I wouldn't call it a workaround yet. Avoiding lock contention by using per CPU list is an optimization we have done before right? (Example the synthetic RCU callback-flooding use case where we used a per-cpu list). We can call it defensive programming, if you will. ;-) Especially in the scheduler hot path where we are blocking/preempting. Again, I'm not saying we should do it for this case since we are still studying the issue, but just on the fact that we are optimizing a spin lock we acquire *a lot* shouldn't be categorized as a workaround in my opinion.

Quoted 3 lines

This blocking is even more likely on preempt RT in read-side critical sections. Again, I'm not saying that we should do this optimization, but I don't think we can ignore it. At least not based on the data I have so far.

If the main motivation is vCPU preemption, I consider this to be a workaround for the lack of awareness of guest-OS locks by the host OS. If there is some other reasonable way of generating contention on this lock, then per-CPU locking is one specific way of addressing that contention. As is reducing the value of CONFIG_RCU_FANOUT_LEAF and who knows what all else.

Quoted 21 lines
Quoted 13 lines
Quoted 10 lines

What bothers me about the current state of affairs is that even without any grace period in progress, any task blocking in an RCU Read Side critical section will take a (almost-)global lock that is shared by other CPUs who might also be preempting/blocking RCU readers. Further, if this happens to be a vCPU that was preempted while holding the node lock, then every other vCPU thread that blocks in an RCU critical section will also block and end up slowing preemption down in the vCPU. My preference would be to keep the readers fast while moving the overhead to the slow path (the overhead being promoting tasks at the right time that were blocked). In fact, in these patches, I'm directly going to the node list if there is a grace period in progress.

Not "(almost-)global"!

Quoted 7 lines

That lock replicates itself automatically with increasing numbers of CPUs. That 16 used to be the full (at the time) 32-bit cpumask, but we decreased it to 16 based on performance feedback from Andi Kleen back in the day. If we are seeing real-world contention on that lock in real-world workloads on real-world systems, further adjustments could be made, either reducing CONFIG_RCU_FANOUT_LEAF further or offloading the lock, where your series is one example of the latter.

Quoted 2 lines

I meant it is global or almost global depending on the number of CPUs. So for example on an 8 CPU system with the default fanout, it is a global lock, correct?

Yes, but only assuming the default CONFIG_RCU_FANOUT_LEAF value of 16, or some other value of 8 or larger. But in that case, there are only 8 CPUs contending for that lock, so is there really a problem? (In the absence of vCPU contention, that is.) And the default value can be changed if needed.

Quoted 6 lines
Quoted 3 lines

I could easily believe that the vCPU preemption problem needs to be addressed, but doing so on a per-spinlock basis would lead to greatly increased complexity throughout the kernel, not just RCU.

I agree with this. I was not intending to solve this for the entire kernel, at first at least.

If addressing vCPU contention is the goal, how many locks are individually adjusted before solving it for the whole kernel becomes easier and less complex?

Quoted 11 lines
Quoted 10 lines
Quoted 6 lines

About the deferred-preemption, I believe Steven Rostedt at one point was looking at that for VMs, but that effort stalled as Peter is concerned about doing that would mess up the scheduler. The idea (AFAIU) is to use the rseq page to communicate locking information between vCPU threads and the host and then let the host avoid vCPU preemption - but the scheduler needs to do something with that information. Otherwise, it's no use.

Has deferred preemption for userspace locking also stalled? If not, then the scheduler's support for userspace should apply directly to guest OSes, right?

Quoted 6 lines

I don't think there have been any user space locking optimizations for preemption that has made it upstream (AFAIK). I know there were efforts, but I could be out of date there. I think the devil is in the details as well because user space optimizations cannot always be applied to guests in my experience. The VM exit path and the syscall entry/exit paths are quite different, including the API boundary.

Thomas and Steve are having another go at the userspace portion of this problem. Should that make it in, the guest-OS portion might not be that big an ask.

Quoted 38 lines
Quoted 38 lines
Quoted 37 lines
Quoted 24 lines

Also if so, would the following rather simpler patch do the same trick, if accompanied by CONFIG_RCU_FANOUT_LEAF=1?

------------------------------------------------------------------------

kernel/rcu/Kconfig +3 -4
index 6a319e2926589..04dbee983b37d 100644
@@ -198,9 +198,9 @@ config RCU_FANOUT
 
 config RCU_FANOUT_LEAF
 	int "Tree-based hierarchical RCU leaf-level fanout value"
-	range 2 64 if 64BIT && !RCU_STRICT_GRACE_PERIOD
-	range 2 32 if !64BIT && !RCU_STRICT_GRACE_PERIOD
-	range 2 3 if RCU_STRICT_GRACE_PERIOD
+	range 1 64 if 64BIT && !RCU_STRICT_GRACE_PERIOD
+	range 1 32 if !64BIT && !RCU_STRICT_GRACE_PERIOD
+	range 1 3 if RCU_STRICT_GRACE_PERIOD
 	depends on TREE_RCU && RCU_EXPERT>  	default 16 if !RCU_STRICT_GRACE_PERIOD
 	default 2 if RCU_STRICT_GRACE_PERIOD
 
------------------------------------------------------------------------
Quoted 2 lines

This passes a quick 20-minute rcutorture smoke test. Does it provide similar performance benefits?

I tried this out, and it also brings down the contention and solves the problem I saw (in testing so far).

Would this work also if the test had grace periods init/cleanup racing with preempted RCU read-side critical sections? I'm doing longer tests now to see how this performs under GP-stress, versus my solution. I am also seeing that with just the node lists, not per-cpu list, I see a dramatic throughput drop after some amount of time, but I can't explain it. And I do not see this with the per-cpu list solution (I'm currently testing if I see the same throughput drop with the fan-out solution you proposed).

Quoted 4 lines
Quoted 1 line

Might the throughput drop be due to increased load on the host?

The load is constant with the benchmark, and the data is repeatable and consistent. So random load on the host is unlikely.

So you have a system with the various background threads corralled or disabled?

Quoted 7 lines
Quoted 6 lines

Another possibility is that tasks/vCPUs got shuffled so as to increase the probability of preemption.

Also, doesn't your patch also cause the grace-period kthread to acquire that per-CPU lock, thus also possibly resulting in contention, vCPU preemption, and so on?

Quoted 11 lines

Yes, I'm tracing it more. Even with baseline (without these patches), I see this throughput drop so it is worth investigating. I think it's something possibly like a lock convoy forming, but the fact that if I don't use RNP locking, the lock convoy disappears, and the throughput is completely stable. That tells me that that has something to do with that or something related. I also measured the exact RNP lock time and counted the number of contentions, so I am not really guessing here. The RNP lock is contended consistently. I think it's a great idea for me to extend this lock contention measurement to the run queue locks as well, for me to measure how they are doing (or even extending it to all locks, as you mentioned) - at least for me to confirm the theory that the same test severely contends other locks as well.

Is the RNP lock contended under non-overload conditions? If I remember correctly, you were running 2x CPU overload. Is the RNP lock contended in bare-metal kernels?

Thanx, Paul

Quoted 17 lines
Quoted 8 lines
Quoted 7 lines

I'm also wondering whether relying on the user to set FANOUT_LEAF to 1 is reasonable, considering this is not a default. Are you suggesting defaulting to this for small systems? If not, then I guess the optimization will not be enabled by default. Eventually, with this patch set, if we are moving forward with this approach, I will remove the config option for per-CPU block list altogether so that it is enabled by default. That's kind of my plan if we agreed on this, but it is just an RFC stage :).

Quoted 4 lines

Right now, we are experimenting, so the usability issue is less pressing. Once we find out what is really going on for real-world systems, we can make adjustments if and as appropriate, said adjustments including usability.

Sure, thanks.

- Joel