rcu-tasks: Defer IRQ-disabled callback enqueue to irq_work
Subsystems (3)
PATCH 1/1 rcu-tasks: Defer IRQ-disabled callback enqueue to irq_work
From: Matt Fleming <[email protected]>
call_rcu_tasks_generic() can be invoked with IRQs disabled, and on older kernels this exposed an ABBA deadlock against the scheduler runqueue lock via sched_ext's task-storage teardown path:
CPU 0 CPU 1
----- -----sched_ext_free()
task_rq_lock()
raw_spin_lock(rq->lock)
rcu_tasks_one_gp()
raw_spin_lock(cbs_gbl_lock)
scx_exit_task()
bpf_task_storage_delete()
call_rcu_tasks_generic()
raw_spin_lock(cbs_gbl_lock)
<blocks>
_printk()
console_unlock()
try_to_wake_up()
raw_spin_lock(rq->lock)
<blocks>Tasks Trace has since moved to SRCU and no longer takes this path, but Tasks and Tasks Rude still go through call_rcu_tasks_generic() and remain exposed to lock-order inversions against any lock that may be held with IRQs disabled by a caller.
Split the enqueue based on the caller's IRQ state. When IRQs are disabled, push the callback onto a statically initialised per-CPU lockless llist and schedule a hard irq_work to drain it into the segmented callback list under the usual per-CPU lock outside the caller's lock context. The drain is also invoked from rcu_barrier_tasks_generic() and rcu_tasks_need_gpcb() so barriers and grace-period progress cannot miss in-transit callbacks. IRQ-enabled callers keep the existing direct-enqueue semantics.
---
I have a separately tested 6.18.y backport and will submit it once this change lands upstream.
--- kernel/rcu/tasks.h | 186 ++++++++++++++++++++++++++++++++++++--------- 1 file changed, 149 insertions(+), 37 deletions(-)
kernel/rcu/tasks.h +149 -37
@@ -30,6 +30,8 @@ typedef void (*postgp_func_t)(struct rcu_tasks *rtp);* @rtp_n_lock_retries: Rough lock-contention statistic. * @rtp_work: Work queue for invoking callbacks. * @rtp_irq_work: IRQ work queue for deferred wakeups. +* @rtp_irq_bypass_work: IRQ work queue for draining IRQ-bypassed callbacks. +* @rtp_irq_bypass_list: Lockless callback list for IRQ-disabled callers. * @barrier_q_head: RCU callback for barrier operation. * @rtp_blkd_tasks: List of tasks blocked as readers. * @rtp_exit_list: List of tasks in the latter portion of do_exit().
@@ -46,6 +48,8 @@ struct rcu_tasks_percpu {unsigned int urgent_gp;struct work_struct rtp_work;struct irq_work rtp_irq_work; +struct irq_work rtp_irq_bypass_work; +struct llist_head rtp_irq_bypass_list;struct rcu_head barrier_q_head;struct list_head rtp_blkd_tasks;struct list_head rtp_exit_list;
@@ -129,11 +133,15 @@ struct rcu_tasks { };static void call_rcu_tasks_iw_wakeup (struct irq_work *iwp); +static void call_rcu_tasks_iw_drain_irq_bypass (struct irq_work *iwp); +static void rcu_tasks_adjust_cbs (struct rcu_tasks *rtp);#define DEFINE_RCU_TASKS (rt_name, gp, call, n) \ static DEFINE_PER_CPU(struct rcu_tasks_percpu, rt_name ## __percpu) = { \ .lock = __RAW_SPIN_LOCK_UNLOCKED(rt_name ## __percpu.cbs_pcpu_lock), \ .rtp_irq_work = IRQ_WORK_INIT_HARD(call_rcu_tasks_iw_wakeup), \ + .rtp_irq_bypass_work = IRQ_WORK_INIT_HARD(call_rcu_tasks_iw_drain_irq_bypass), \ + .rtp_irq_bypass_list = LLIST_HEAD_INIT(rtp_irq_bypass_list), \ }; \ static struct rcu_tasks rt_name = \ { \
@@ -328,6 +336,103 @@ static void call_rcu_tasks_generic_timer(struct timer_list *tlp)rcuwait_wake_up (&rtp->cbs_wait); } +static bool call_rcu_tasks_enqueue_locked (struct rcu_head *rhp, +struct rcu_tasks *rtp, +struct rcu_tasks_percpu *rtpcp) +{ +bool havekthread; +bool needwake; + +// Queuing callbacks before initialization not yet supported. +if (WARN_ON_ONCE (!rcu_segcblist_is_enabled (&rtpcp->cblist))) +rcu_segcblist_init (&rtpcp->cblist); +/* Pairs with the kthread publication in rcu_tasks_kthread(). */ + havekthread =smp_load_acquire (&rtp->kthread_ptr); + needwake = (!havekthread &&rcu_segcblist_empty (&rtpcp->cblist)) || + (rhp->func == wakeme_after_rcu) || + (rcu_segcblist_n_cbs (&rtpcp->cblist) == rcu_task_lazy_lim); +if (havekthread && !needwake && !timer_pending (&rtpcp->lazy_timer)) { +if (rtp->lazy_jiffies) +mod_timer (&rtpcp->lazy_timer,rcu_tasks_lazy_time (rtp)); +else + needwake =rcu_segcblist_empty (&rtpcp->cblist); + } +if (needwake) + rtpcp->urgent_gp =3 ; +rcu_segcblist_enqueue (&rtpcp->cblist, rhp); +return needwake; +} + +/* Acquire the callback-list lock and report whether the acquisition contended. */ +static bool call_rcu_tasks_lock (struct rcu_tasks_percpu *rtpcp) +{ +if (raw_spin_trylock_rcu_node (rtpcp))// irqs already disabled. +return false; +raw_spin_lock_rcu_node (rtpcp);// irqs already disabled. +return true; +} + +/* Record one callback-queuing-time contention event. */ +static bool rcu_tasks_need_queue_adjust (struct rcu_tasks *rtp, +struct rcu_tasks_percpu *rtpcp) +{ +unsigned long j = jiffies; + +if (rtpcp->rtp_jiffies != j) { + rtpcp->rtp_jiffies = j; + rtpcp->rtp_n_lock_retries =0 ; + } + +return rcu_task_cb_adjust && + ++rtpcp->rtp_n_lock_retries > rcu_task_contend_lim && +READ_ONCE (rtp->percpu_enqueue_lim) != rcu_task_cpu_ids; +} + +static void rcu_tasks_drain_irq_bypass (struct rcu_tasks_percpu *rtpcp) +{ +bool contended; +bool needadjust = false; +bool needwake = false; +unsigned long flags; +struct llist_node *llnode; +struct llist_node *next; +struct rcu_head *rhp; +struct rcu_tasks *rtp = rtpcp->rtpp; + +local_irq_save (flags); +rcu_read_lock (); + contended =call_rcu_tasks_lock (rtpcp); + +/* +* Serialize the entire bypass-to-cblist transfer with barrier +* entrainment so that a barrier cannot pass callbacks in transit. +*/ + llnode =llist_del_all (&rtpcp->rtp_irq_bypass_list); +if (!llnode) { +raw_spin_unlock_irqrestore_rcu_node (rtpcp, flags); +rcu_read_unlock (); +return ; + } + +if (contended) + needadjust =rcu_tasks_need_queue_adjust (rtp, rtpcp); + + llnode =llist_reverse_order (llnode); +llist_for_each_safe (llnode, next, llnode) { + rhp = (struct rcu_head *)llnode; + needwake |=call_rcu_tasks_enqueue_locked (rhp, rtp, rtpcp); + } +raw_spin_unlock_irqrestore_rcu_node (rtpcp, flags); + +if (unlikely (needadjust)) +rcu_tasks_adjust_cbs (rtp); +rcu_read_unlock (); + +/* We can't create the thread unless interrupts are enabled. */ +if (needwake &&READ_ONCE (rtp->kthread_ptr)) +rcuwait_wake_up (&rtp->cbs_wait); +} +// IRQ-work handler that does deferred wakeup for call_rcu_tasks_generic(). static void call_rcu_tasks_iw_wakeup (struct irq_work *iwp) {
@@ -338,15 +443,40 @@ static void call_rcu_tasks_iw_wakeup(struct irq_work *iwp)rcuwait_wake_up (&rtp->cbs_wait); } +// IRQ-work handler that drains IRQ-bypassed callbacks. +static void call_rcu_tasks_iw_drain_irq_bypass (struct irq_work *iwp) +{ +struct rcu_tasks_percpu *rtpcp; + + rtpcp = container_of(iwp, struct rcu_tasks_percpu, rtp_irq_bypass_work); +rcu_tasks_drain_irq_bypass (rtpcp); +} + +static void rcu_tasks_adjust_cbs (struct rcu_tasks *rtp) +{ +unsigned long flags; +bool expanded = false; + +raw_spin_lock_irqsave (&rtp->cbs_gbl_lock, flags); +if (rtp->percpu_enqueue_lim != rcu_task_cpu_ids) { +WRITE_ONCE (rtp->percpu_enqueue_shift,0 ); +WRITE_ONCE (rtp->percpu_dequeue_lim, rcu_task_cpu_ids); +smp_store_release (&rtp->percpu_enqueue_lim, rcu_task_cpu_ids); + expanded = true; + } +raw_spin_unlock_irqrestore (&rtp->cbs_gbl_lock, flags); +if (expanded) +pr_info ("Switching %s to per-CPU callback queuing.\n" , rtp->name); +} +// Enqueue a callback for the specified flavor of Tasks RCU. static void call_rcu_tasks_generic (struct rcu_head *rhp,rcu_callback_t func,struct rcu_tasks *rtp) {int chosen_cpu;unsigned long flags; -bool havekthread =smp_load_acquire (&rtp->kthread_ptr);int ideal_cpu; -unsigned long j; +bool irqsoff =irqs_disabled ();bool needadjust = false;bool needwake;struct rcu_tasks_percpu *rtpcp;
@@ -359,44 +489,23 @@ static void call_rcu_tasks_generic(struct rcu_head *rhp, rcu_callback_t func, chosen_cpu =cpumask_next (ideal_cpu -1 , cpu_possible_mask);WARN_ON_ONCE (chosen_cpu >= rcu_task_cpu_ids); rtpcp =per_cpu_ptr (rtp->rtpcpu, chosen_cpu); -if (!raw_spin_trylock_rcu_node (rtpcp)) {// irqs already disabled. -raw_spin_lock_rcu_node (rtpcp);// irqs already disabled. - j = jiffies; -if (rtpcp->rtp_jiffies != j) { - rtpcp->rtp_jiffies = j; - rtpcp->rtp_n_lock_retries =0 ; - } -if (rcu_task_cb_adjust && ++rtpcp->rtp_n_lock_retries > rcu_task_contend_lim && -READ_ONCE (rtp->percpu_enqueue_lim) != rcu_task_cpu_ids) - needadjust = true;// Defer adjustment to avoid deadlock. - } -// Queuing callbacks before initialization not yet supported. -if (WARN_ON_ONCE (!rcu_segcblist_is_enabled (&rtpcp->cblist))) -rcu_segcblist_init (&rtpcp->cblist); - needwake = (!havekthread &&rcu_segcblist_empty (&rtpcp->cblist)) || - (func == wakeme_after_rcu) || - (rcu_segcblist_n_cbs (&rtpcp->cblist) == rcu_task_lazy_lim); -if (havekthread && !needwake && !timer_pending (&rtpcp->lazy_timer)) { -if (rtp->lazy_jiffies) -mod_timer (&rtpcp->lazy_timer,rcu_tasks_lazy_time (rtp)); -else - needwake =rcu_segcblist_empty (&rtpcp->cblist); +if (irqsoff) { +llist_add ((struct llist_node *)rhp, &rtpcp->rtp_irq_bypass_list); +rcu_read_unlock (); +local_irq_restore (flags); +irq_work_queue (&rtpcp->rtp_irq_bypass_work); +return ; } -if (needwake) - rtpcp->urgent_gp =3 ; -rcu_segcblist_enqueue (&rtpcp->cblist, rhp); + +if (call_rcu_tasks_lock (rtpcp)) + needadjust =rcu_tasks_need_queue_adjust (rtp, rtpcp); + + needwake =call_rcu_tasks_enqueue_locked (rhp, rtp, rtpcp);raw_spin_unlock_irqrestore_rcu_node (rtpcp, flags); -if (unlikely (needadjust)) { -raw_spin_lock_irqsave (&rtp->cbs_gbl_lock, flags); -if (rtp->percpu_enqueue_lim != rcu_task_cpu_ids) { -WRITE_ONCE (rtp->percpu_enqueue_shift,0 ); -WRITE_ONCE (rtp->percpu_dequeue_lim, rcu_task_cpu_ids); -smp_store_release (&rtp->percpu_enqueue_lim, rcu_task_cpu_ids); -pr_info ("Switching %s to per-CPU callback queuing.\n" , rtp->name); - } -raw_spin_unlock_irqrestore (&rtp->cbs_gbl_lock, flags); - } +if (unlikely (needadjust)) +rcu_tasks_adjust_cbs (rtp);rcu_read_unlock (); +/* We can't create the thread unless interrupts are enabled. */ if (needwake &&READ_ONCE (rtp->kthread_ptr))irq_work_queue (&rtpcp->rtp_irq_work);
@@ -438,6 +547,7 @@ static void __maybe_unused rcu_barrier_tasks_generic(struct rcu_tasks *rtp)if (cpu >=smp_load_acquire (&rtp->percpu_dequeue_lim))break ; rtpcp =per_cpu_ptr (rtp->rtpcpu, cpu); +rcu_tasks_drain_irq_bypass (rtpcp); rtpcp->barrier_q_head.func = rcu_barrier_tasks_generic_cb;raw_spin_lock_irqsave_rcu_node (rtpcp, flags);if (rcu_segcblist_entrain (&rtpcp->cblist, &rtpcp->barrier_q_head))
@@ -470,6 +580,8 @@ static int rcu_tasks_need_gpcb(struct rcu_tasks *rtp)continue ;struct rcu_tasks_percpu *rtpcp =per_cpu_ptr (rtp->rtpcpu, cpu); +rcu_tasks_drain_irq_bypass (rtpcp); +/* Advance and accelerate any new callbacks. */ if (!rcu_segcblist_n_cbs (&rtpcp->cblist))continue ;
Signature · 1 line
2.43.0
Quoted 10 lines · Matt Fleming
From: Matt Fleming <[email protected]>
call_rcu_tasks_generic()can be invoked with IRQs disabled, and on older kernels this exposed an ABBA deadlock against the scheduler runqueue lock via sched_ext's task-storage teardown path:CPU 0 CPU 1
----- -----sched_ext_free()
task_rq_lock()
Quoted 13 lines
raw_spin_lock(rq->lock)
rcu_tasks_one_gp()
raw_spin_lock(cbs_gbl_lock)
scx_exit_task()
bpf_task_storage_delete()
call_rcu_tasks_generic()
raw_spin_lock(cbs_gbl_lock)
<blocks>
_printk()
console_unlock()
try_to_wake_up()
raw_spin_lock(rq->lock)
<blocks>Hey Paul, it looks like this didn't get picked up and now won't apply cleanly to your tree. Should I submit a v2?
Thanks,
Matt
Paul E. McKenney
maintainerQuoted 25 lines · Matt Fleming
Quoted 10 lines · Matt Fleming
From: Matt Fleming <[email protected]>
call_rcu_tasks_generic()can be invoked with IRQs disabled, and on older kernels this exposed an ABBA deadlock against the scheduler runqueue lock via sched_ext's task-storage teardown path:CPU 0 CPU 1
----- -----sched_ext_free()
task_rq_lock()Quoted 13 lines
raw_spin_lock(rq->lock) rcu_tasks_one_gp() raw_spin_lock(cbs_gbl_lock) scx_exit_task() bpf_task_storage_delete() call_rcu_tasks_generic() raw_spin_lock(cbs_gbl_lock) <blocks> _printk() console_unlock() try_to_wake_up() raw_spin_lock(rq->lock) <blocks>
Quoted 2 lines
Hey Paul, it looks like this didn't get picked up and now won't apply cleanly to your tree. Should I submit a v2?
Apologies for the delay!!!
It turns out that there are "interesting" relationships to certain BPF programs and the CPU hotplugs being unearthed in the discussions of this patch's call_rcu() and call_srcu(). Which we *might* be getting to the bottom of.
And that these affect call_rcu_tasks() as well. And which are sadly off-list, otherwise, I would invite you to join in. :-(
If you would be willing to do a v2, one piece of feedback that does not depend on the discussions is that RCU Tasks can sometimes have multiple callback queues, and when that happens, rcu_barrier_tasks_generic() must drain all of them.
Alternatively, please do feel free to hold off until we get the public posting of the call_rcu() and call_srcu() deferral patch series. It will likely provide a helper function that you can use. To your credit, your initial definition of the irqsoff local variable within call_rcu_tasks_generic() is what we seem to be settling on. It should also clarify what needs to happen when a CPU goes offline with deferred callbacks.
Again, please accept my apologies for being slow!
Thanx, Paul
Quoted 2 lines · Paul E. McKenney
Apologies for the delay!!!
No worries :)
Quoted 7 lines
Alternatively, please do feel free to hold off until we get the public posting of the
call_rcu()andcall_srcu()deferral patch series. It will likely provide a helper function that you can use. To your credit, your initial definition of the irqsoff local variable withincall_rcu_tasks_generic()is what we seem to be settling on. It should also clarify what needs to happen when a CPU goes offline with deferred callbacks.
Sure, I saw the patch series and will piggyback on top of it.
Thanks,
Matt