When creating and destroying DSQs concurrently, a potential deadlock can
occur due to a circular locking dependency between the locks involved in
the operations:

 - create_dsq():

  rhashtable_bucket --> rq->lock --> dsq->lock

 - destroy_dsq():

  dsq->lock -> rhashtable_bucket

This circular dependency is also shown by the following lockdep splat:

[   85.874899] ======================================================
[   85.881304] WARNING: possible circular locking dependency detected
[   85.887710] 6.13.0-rc7-00043-g619f0b6fad52 #3 Not tainted
[   85.893298] ------------------------------------------------------
[   85.899699] sched_ext_ops_h/2060 is trying to acquire lock:
[   85.905467] ffff000080029838 (rhashtable_bucket){....}-{0:0}, at: destroy_dsq+0x1b4/0x7f8
[   85.913960]
               but task is already holding lock:
[   85.919996] ffff0000a126fed8 (&dsq->lock){-.-.}-{2:2}, at: destroy_dsq+0x6c/0x7f8
[   85.927753]
               which lock already depends on the new lock.
...
               other info that might help us debug this:

[   86.494385] Chain exists of:
                 rhashtable_bucket --> &rq->__lock --> &dsq->lock

[   86.510168]  Possible unsafe locking scenario:

[   86.519784]        CPU0                    CPU1
[   86.526184]        ----                    ----
[   86.532560]   lock(&dsq->lock);
[   86.537487]                                lock(&rq->__lock);
[   86.545154]                                lock(&dsq->lock);
[   86.552680]   lock(rhashtable_bucket);
[   86.558244]
                *** DEADLOCK ***

Fix by avoiding the acquisition of the rhashtable lock while dsq->lock
is held in destroy_dsq().

Fixes: f0e1a0643a59 ("sched_ext: Implement BPF extensible scheduler class")
Signed-off-by: Andrea Righi <arighi@nvidia.com>
---
 kernel/sched/ext.c | 16 +++++++++++++---
 1 file changed, 13 insertions(+), 3 deletions(-)

diff --git a/kernel/sched/ext.c b/kernel/sched/ext.c
index 8535b46fa4c3..f1bc7639e730 100644
--- a/kernel/sched/ext.c
+++ b/kernel/sched/ext.c
@@ -4521,9 +4521,6 @@ static void destroy_dsq(u64 dsq_id)
 		goto out_unlock_dsq;
 	}
 
-	if (rhashtable_remove_fast(&dsq_hash, &dsq->hash_node, dsq_hash_params))
-		goto out_unlock_dsq;
-
 	/*
 	 * Mark dead by invalidating ->id to prevent dispatch_enqueue() from
 	 * queueing more tasks. As this function can be called from anywhere,
@@ -4531,6 +4528,19 @@ static void destroy_dsq(u64 dsq_id)
 	 * operations inside scheduler locks.
 	 */
 	dsq->id = SCX_DSQ_INVALID;
+
+	raw_spin_unlock_irqrestore(&dsq->lock, flags);
+
+	/*
+	 * If removing the DSQ from the rhashtable fails, it means that a
+	 * concurrent destroy_dsq() has already removed it. In this case,
+	 * avoid triggering the free via the irq work.
+	 */
+	if (rhashtable_remove_fast(&dsq_hash, &dsq->hash_node, dsq_hash_params))
+		goto out_unlock_rcu;
+
+	raw_spin_lock_irqsave(&dsq->lock, flags);
+
 	llist_add(&dsq->free_node, &dsqs_to_free);
 	irq_work_queue(&free_dsq_irq_work);
 
-- 
2.48.0

On Thu, Jan 16, 2025 at 12:51:01PM +0100, Andrea Righi wrote:
> When creating and destroying DSQs concurrently, a potential deadlock can
> occur due to a circular locking dependency between the locks involved in
> the operations:
> 
>  - create_dsq():
> 
>   rhashtable_bucket --> rq->lock --> dsq->lock

Hmm... this is probably the same thing that Breno tried to fix with
rhashtable update. Breno, what's the current state of that patch? I saw bug
reports and fix patch flying by but didn't track them closely.

Thanks.

-- 
tejun

Hello Tejun,

On Thu, Jan 16, 2025 at 04:06:26PM -1000, Tejun Heo wrote:
> On Thu, Jan 16, 2025 at 12:51:01PM +0100, Andrea Righi wrote:
> > When creating and destroying DSQs concurrently, a potential deadlock can
> > occur due to a circular locking dependency between the locks involved in
> > the operations:
> > 
> >  - create_dsq():
> > 
> >   rhashtable_bucket --> rq->lock --> dsq->lock
> 
> Hmm... this is probably the same thing that Breno tried to fix with
> rhashtable update. Breno, what's the current state of that patch? I saw bug
> reports and fix patch flying by but didn't track them closely.

Right, that seems exactly the problem I fixed. This is the current state
of the issue.

The fix is already in linux-next, but not on linus' tree:

	e1d3422c95f00  Breno Leitao        : rhashtable: Fix potential deadlock by moving schedule_work outside lock

That fixes caused a regression[1], and Herbert got a patch, which is not
committed in linux-next AFAIK.

This is Herbert's fix:

	https://lore.kernel.org/all/Z4XWx5X0doetOJni@gondor.apana.org.au/

[1] Link: https://lore.kernel.org/all/Z4DoFYQ3ytB-wS3-@gondor.apana.org.au/

--breno

Hi Breno,

On Fri, Jan 17, 2025 at 01:46:12AM -0800, Breno Leitao wrote:
...
> > Hmm... this is probably the same thing that Breno tried to fix with
> > rhashtable update. Breno, what's the current state of that patch? I saw bug
> > reports and fix patch flying by but didn't track them closely.
> 
> Right, that seems exactly the problem I fixed. This is the current state
> of the issue.
> 
> The fix is already in linux-next, but not on linus' tree:
> 
> 	e1d3422c95f00  Breno Leitao        : rhashtable: Fix potential deadlock by moving schedule_work outside lock

Oh I totally missed your fix.

> 
> That fixes caused a regression[1], and Herbert got a patch, which is not
> committed in linux-next AFAIK.
> 
> This is Herbert's fix:
> 
> 	https://lore.kernel.org/all/Z4XWx5X0doetOJni@gondor.apana.org.au/

If there's something in progress already, feel free to ignore my patch.
I'll do a test on my side later with these fixes applied.

Thanks,
-Andrea

> 
> [1] Link: https://lore.kernel.org/all/Z4DoFYQ3ytB-wS3-@gondor.apana.org.au/
> 
> --breno