rcu: Reduce rnp->lock contention with per-CPU blocked task lists
Subsystems (4)
Joel Fernandes
maintainercover 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
Joel Fernandes
maintainerRFC 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
@@ -846,6 +846,7 @@ void exit_rcu(void)if (unlikely (!list_empty (¤t->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
Steven Rostedt
reviewerRe: [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_ONCEto 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.Signed-off-by Joel Fernandes <[email protected]>--- kernel/rcu/tree_plugin.h | 1 + 1 file changed, 1 insertion(+)kernel/rcu/tree_plugin.h +0
-0
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 (¤t->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 );
Joel Fernandes
maintainerRe: [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_ONCEto 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.Signed-off-by Joel Fernandes <[email protected]>--- 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@@ -846,6 +846,7 @@ void exit_rcu(void)if (unlikely (!list_empty (¤t->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
Joel Fernandes
maintainerRFC PATCH 2/14 rcu: Add per-CPU blocked task lists for PREEMPT_RCU
In reply to Joel FernandesAdd 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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
Steven Rostedt
reviewerRe: [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
-0depends on TREE_RCUkernel/rcu/tree.c +17
-0@@ -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@@ -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
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));
Joel Fernandes
maintainerRFC PATCH 3/14 rcu: Early return during unlock for tasks only on per-CPU blocked list
In reply to Joel FernandesAdd 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
@@ -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
Joel Fernandes
maintainerRFC PATCH 4/14 rcu: Promote blocked tasks from per-CPU to rnp lists
In reply to Joel FernandesAdd 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
@@ -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
Steven Rostedt
reviewerRe: [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? +*/
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 whenPREEMPT_RTis 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
Joel Fernandes
maintainerRFC PATCH 5/14 rcu: Promote blocked tasks for expedited GPs
In reply to Joel FernandesAdd 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
@@ -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
@@ -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
@@ -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
Joel Fernandes
maintainerRFC PATCH 6/14 rcu: Promote per-CPU blocked tasks before checking for blocked readers
In reply to Joel FernandesWhen 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
@@ -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
@@ -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
@@ -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
@@ -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
Joel Fernandes
maintainerRFC PATCH 7/14 rcu: Promote late-arriving blocked tasks before reporting QS
In reply to Joel FernandesBlocked 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
@@ -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
@@ -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
Joel Fernandes
maintainerRFC PATCH 8/14 rcu: Promote blocked tasks before QS report in force_qs_rnp()
In reply to Joel FernandesWhen 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
@@ -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
Joel Fernandes
maintainerRFC PATCH 9/14 rcu: Promote blocked tasks before QS report in rcutree_report_cpu_dead()
In reply to Joel FernandesWhen 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
@@ -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
Joel Fernandes
maintainerRFC PATCH 10/14 rcu: Promote blocked tasks before QS report in rcu_gp_init()
In reply to Joel FernandesDuring 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
@@ -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
Joel Fernandes
maintainerRFC PATCH 11/14 rcu: Add per-CPU blocked list check in exit_rcu()
In reply to Joel FernandesWith 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
@@ -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 (¤t->rcu_node_entry))) { +/* Check if task is on any blocked list (rnp or per-CPU). */ + on_list = !list_empty (¤t->rcu_node_entry); +#ifdef CONFIG_RCU_PER_CPU_BLOCKED_LISTS + on_list = on_list || !list_empty (¤t->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
Joel Fernandes
maintainerRFC PATCH 12/14 rcu: Skip per-CPU list addition when GP already started
In reply to Joel FernandesWhen 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
@@ -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
Joel Fernandes
maintainerRFC PATCH 13/14 rcu: Skip rnp addition when no grace period waiting
In reply to Joel FernandesThis 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
@@ -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
Joel Fernandes
maintainerRFC PATCH 14/14 rcu: Remove checking of per-cpu blocked list against the node list
In reply to Joel FernandesNow 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
@@ -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
kernel test robot
build botRe: [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
Paul E. McKenney
maintainerQuoted 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->lockshared 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, makingrnp->lockeffectively 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->lockneeded.2. Promotion on demand: When a grace period starts, promote tasks from per-CPU lists to the
rcu_nodelist.3. Normal path: If a grace period is already waiting, tasks go directly to the
rcu_nodelist as before.Results
-------
Testing with 64 reader threads under vCPU preemption from 32 hostSCHED_FIFOpreemptors), 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->lockoverhead.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_LISTSto 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
@@ -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: AddWARN_ON_ONCEfor blocked flag invariant inexit_rcu()
rcu: Add per-CPU blocked task lists forPREEMPT_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 inforce_qs_rnp()
rcu: Promote blocked tasks before QS report in
rcutree_report_cpu_dead()
rcu: Promote blocked tasks before QS report inrcu_gp_init()
rcu: Add per-CPU blocked list check inexit_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 listinclude/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
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->lockshared 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, makingrnp->lockeffectively 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->lockneeded.2. Promotion on demand: When a grace period starts, promote tasks from per-CPU lists to the
rcu_nodelist.3. Normal path: If a grace period is already waiting, tasks go directly to the
rcu_nodelist as before.Results
-------
Testing with 64 reader threads under vCPU preemption from 32 hostSCHED_FIFOpreemptors), 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 usExcellent 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->lockoverhead.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_LISTSto 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@@ -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
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@@ -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_LEAFto 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
Paul E. McKenney
maintainerQuoted 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@@ -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_LEAFto 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
Joel Fernandes
maintainerQuoted 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@@ -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_LEAFto 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.
Paul E. McKenney
maintainerQuoted 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@@ -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_LEAFto 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
Paul E. McKenney
maintainerQuoted 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->lockshared 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, makingrnp->lockeffectively 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->lockneeded.2. Promotion on demand: When a grace period starts, promote tasks from per-CPU lists to the
rcu_nodelist.3. Normal path: If a grace period is already waiting, tasks go directly to the
rcu_nodelist as before.Results
-------
Testing with 64 reader threads under vCPU preemption from 32 hostSCHED_FIFOpreemptors), 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 usExcellent 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->lockoverhead.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_LISTSto 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@@ -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_LEAFto 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
Steven Rostedt
reviewerQuoted 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
Paul E. McKenney
maintainerQuoted 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
Joel Fernandes
maintainerQuoted 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
Paul E. McKenney
maintainerQuoted 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
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->lockoverhead.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_LISTSto 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_LEAFfurther 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@@ -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_LEAFto 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
Paul E. McKenney
maintainerQuoted 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->lockoverhead.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_LISTSto 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_LEAFfurther 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@@ -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_LEAFto 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