git: 538c48bf6247 - main - sched_ule: Fix rare deadlock on stealing a migrated lock-blocked thread

From: Olivier Certner <olce_at_FreeBSD.org>
Date: Sat, 14 Nov 2026 16:29:48 UTC
The branch main has been updated by olce:

URL: https://cgit.FreeBSD.org/src/commit/?id=538c48bf6247a2895b364c96f495be4cc7df1933

commit 538c48bf6247a2895b364c96f495be4cc7df1933
Author:     Olivier Certner <olce@FreeBSD.org>
AuthorDate: 2026-11-11 21:41:45 +0000
Commit:     Olivier Certner <olce@FreeBSD.org>
CommitDate: 2026-11-14 16:29:33 +0000

    sched_ule: Fix rare deadlock on stealing a migrated lock-blocked thread
    
    Thread stealing ultimately happens in tdq_move() which, while holding
    the locks of the source and destination runqueues, has to wait for the
    stolen thread to be lock-unblocked.  If it is indeed lock-blocked, the
    corresponding sched_switch_migrate() needs to re-acquire the lock of the
    runqueue of the CPU it is running on before being able to lock-unblock
    it.  This amounts to adding a "hidden" and variable additional
    lock-ordering dependency between the 'struct tdq' locks held by
    tdq_move() and that of an arbitray third 'struct tdq', possibly
    violating the ordering established by tdq_lock_pair().  In that case,
    other steals occurring in parallel and involving the same queues can
    deadlock the scheduler.
    
    Fix that by having sched_switch_migrate() hold its current CPU's
    runqueue's lock in addition to the remote CPU's before the migrated
    thread can appear on the remote runqueue, so that it does not have to
    re-acquire the former, removing the "hidden" lock-ordering dependency.
    
    Thanks to avg@ who reported such a currently extremely rare
    (explanations below) deadlock occurrence and analyzed it pretty
    thoroughly from the crash dump, as well as doing some code archeology
    (see the thread "ULE: run queue lock deadlock in sched_switch_migrate()
    + tdq_move()" in the FreeBSD-current mailing list).  For another,
    similar occurrence described in concise steps, please see commit
    435068aab79b ("Fix sched_switch_migrate(): (...)").
    
    Below is a thorough explanation of the deadlocks that could occur, an
    history of such deadlocks, a description and explanation of avg@'s
    occurrence, details on the fix's implementation and why that fix was
    chosen.
    
    ******
    
    Threads are ultimately stolen via tdq_move(), which finds the highest
    priority thread that can be migrated to the destination CPU.  tdq_move()
    waits for the stolen thread to become lock-unblocked before assigning it
    to the destination CPU's runqueue, because that action requires changing
    the thread's lock to the destination runqueue's lock (the blocked lock
    is a temporary placeholder for later replacement by the source CPU's
    runqueue's lock).  It does so with both the source and destination CPUs'
    runqueues locked.
    
    Consider the situation where a CPU steals a thread that is indeed
    lock-blocked.  This implies that some sched_switch() is executing on
    another CPU, evicting the stolen thread (as a thread lock-blocked by
    sched_add()/sched_pickcpu() or sched_throw() cannot be seen on
    a runqueue).  That CPU must be at a point where the stolen thread's
    runqueue just before the concurrent steal (=source runqueue) was
    unlocked, and there are two distinct such cases.  The first is that the
    evicted thread gets added to sched_switch()'s current runqueue/CPU, and
    we are past sched_switch()'s tdq_unlock(), but before cpu_switch() which
    lock-unblocks the thread.  In that case, the cpu_switch() thread does
    not block and eventually will execute cpu_switch().  The second case is
    that the evicted thread gets migrated to a remote CPU which is
    necessarily tdq_move()'s source CPU of the steal with our assumptions.
    We are then in sched_switch_migrate() after the thread got added to the
    remote CPU's runqueue, the remote CPU possibly signaled (according to
    priorities) and after its runqueue was unlocked.  We may however be
    before re-locking the current CPU's runqueue.  Then, sched_switch()
    depends on that re-locking to happen to finally lock-unblock the thread.
    As we have seen above, tdq_move() itself depends on observing the
    lock-unblock before it will release the source and destination
    runqueues.
    
    The problem is that there exists cases where sched_switch()'s re-locking
    of the current runqueue depends on the steal releasing its runqueues,
    creating a deadlock.  For example, the steal could happen between the
    same CPUs involved in sched_switch() with source and destination
    inverted, if sched_switch() migrates the thread prompted by the
    long-term load-balancer but the load imbalance suddenly changes and the
    latter makes the reverse decision.  In the current long-term
    load-balancer, this precise case cannot arise, but it could some years
    ago (see below).
    
    The practical case reported by avg@, which prompted this analysis and
    commit, is more involved.  There, sched_switch() initiates a migration
    as requested by the long-term load-balancer (TDF_PICKCPU is set on the
    thread and it is pre-empted, leading to sched_switch() being called).
    In parallel, some idle CPU wants to steal a thread from sched_switch()'s
    remote CPU, and we end up with a situation as described in the previous
    paragraphs.  Finally, the long-term load balancer locks the
    sched_switch()'s current CPU's runqueue (before sched_switch() can grab
    it again), wanting to migrate a thread from there to the steal's
    destination CPU (which was idle) (that runqueue is locked first because
    the corresponding CPU's 'struct tdq''s address happens to be smaller
    numerically, see tdq_lock_pair()).  That establishes a dependency from
    locking the steal's destination CPU to releasing the sched_switch()'s
    current CPU, closing a loop in the dependency graph, i.e., a deadlock.
    
    As avg@ points out, the same kind of deadlocks had been reported and
    fixed in 2009, as indicated by commit 435068aab79b ("Fix
    sched_switch_migrate(): (...)"), but the deadlock was re-introduced by
    commit 686bcb5c14ab ("schedlock 4/4") in 2019.  However, it appeared to
    be much more frequent back then.  That is most probably because the
    long-term load balancer was more aggressive, allowing thread ping-pong,
    whereas it now will only try to steal once from a given CPU per run,
    giving ample time between two runs for a migrated thread to become
    lock-unblocked before the next migration.  avg@ experienced the problem
    on a VM with 24 vCPUs "only once in many years on a fleet of thousands
    of systems", and we are not aware of any other report of such
    a deadlock, including on physical machines.  It probably occurred there
    because of an overloaded machine/hypervisor that for some reason would
    not execute some vCPU for an unusually long period of time at a bad
    moment.
    
    The fix is similar in spirit to what was done in commit 435068aab79b
    ("Fix sched_switch_migrate(): (...)").  It consists in
    sched_switch_migrate() locking both the current and remote runqueues
    before migrating the thread.  That way, sched_switch() never needs to
    reacquire any locks in order to finally unblock the migrated thread, so
    the migrated thread is eventually unlocked, as well as the runqueues
    lock by tdq_move().
    
    Contrary to the situation of 2009's fix, however, sched_switch_migrate()
    is now called with the current runqueue locked.  So we augment
    tdq_lock_pair() with a boolean to indicate that the first queue is
    already locked, and optimize it for that property: It will directly lock
    the second lock if that follows the (arbitrarily) established lock
    order, else it first tries to lock the second one opportunistically, and
    if that fails, unlocks the first before locking both in order (second
    then first).
    
    Our initial solution consisted in simply not considering a thread that
    is still lock-blocked when stealing, so that tdq_move() does not have to
    wait for it to become unblocked, which removes the lock dependency
    mentioned in the first paragraph.  It is marginally more efficient in
    the sense that it does not need to lock both runqueues in
    sched_switch_migrate(), which sometimes requires dropping the current
    runqueue's lock and then re-acquiring it, and allows to steal another
    thread more quickly (no need to wait for the stolen one to unblock), but
    it risked proving noticeably pessimistic in the case of a single thread
    to steal that is lock-blocked (a context switch has just occurred, and
    another thread is now run), as tdq_idled() and tdq_trysteal() are not
    prepare to handle this case, causing a missed steal opportunity and
    leaving two threads sharing the sched_switch()'s core even if other
    cores are free, until the next time the load balancer kicks in.
    Ideally, stealing should not require to lock two runqueues at the same
    time for increased steal parallelism, but such a change is much more
    involved so will be considered at a later time.
    
    Reported by:    avg
    Reviewed by:    mchoo, avg (before last tdq_lock_pair() optimization)
    MFC after:      2 weeks
    Sponsored by:   The FreeBSD Foundation
    Differential Revision:  https://reviews.freebsd.org/D61448
---
 sys/kern/sched_ule.c | 53 +++++++++++++++++++++++++++++++++++++++++++---------
 1 file changed, 44 insertions(+), 9 deletions(-)

diff --git a/sys/kern/sched_ule.c b/sys/kern/sched_ule.c
index 563baa5f06e2..f9fd54285743 100644
--- a/sys/kern/sched_ule.c
+++ b/sys/kern/sched_ule.c
@@ -1010,14 +1010,34 @@ sched_balance(void)
 
 /*
  * Lock two thread queues using their address to maintain lock order.
+ *
+ * 'one_locked' specifies if 'one' is already locked.  In this case, 'one' may
+ * first need to be unlocked, leaving both locks unlocked before they can be
+ * re-acquired.
  */
 static void
-tdq_lock_pair(struct tdq *one, struct tdq *two)
+tdq_lock_pair(struct tdq *one, bool one_locked, struct tdq *two)
 {
 	if (one < two) {
-		TDQ_LOCK(one);
+		if (!one_locked)
+			TDQ_LOCK(one);
 		TDQ_LOCK_FLAGS(two, MTX_DUPOK);
 	} else {
+		if (one_locked) {
+			/*
+			 * If we can acquire the second lock right away (without
+			 * blocking)...
+			 */
+			if (TDQ_TRYLOCK_FLAGS(two, MTX_DUPOK))
+				/* ...then we are done! */
+				return;
+			/*
+			 * That did not work. Release 'one' to acquire both
+			 * locks in the proper order as we may need to sleep
+			 * (most probably, as 'two' has just been seen locked).
+			 */
+			TDQ_UNLOCK(one);
+		}
 		TDQ_LOCK(two);
 		TDQ_LOCK_FLAGS(one, MTX_DUPOK);
 	}
@@ -1044,7 +1064,7 @@ sched_balance_pair(struct tdq *high, struct tdq *low)
 	bool ret;
 
 	ret = false;
-	tdq_lock_pair(high, low);
+	tdq_lock_pair(high, false, low);
 
 	/*
 	 * Transfer a thread from high to low.
@@ -2297,16 +2317,31 @@ sched_switch_migrate(struct tdq *tdq, struct thread *td, int flags)
 #ifdef SMP
 	tdq_load_rem(tdq, td);
 	/*
-	 * Do the lock dance required to avoid LOR.  We have an 
-	 * extra spinlock nesting from sched_switch() which will
-	 * prevent preemption while we're holding neither run-queue lock.
+	 * We have an extra spinlock nesting from sched_switch() which will
+	 * prevent preemption while we're holding neither run-queue lock, which
+	 * can happen in tdq_lock_pair() if tdq's lock has to be dropped and
+	 * re-acquired.
+	 *
+	 * In order to avoid deadlocks, we lock both the current and remote
+	 * runqueues before the thread, which is still lock-blocked, can appear
+	 * on the remote runqueue.  Indeed, a steal (tdq_move()) locks both the
+	 * source and destination runqueues, but needs to wait for the stolen
+	 * thread to be lock-unblocked (see there why).  If we dropped the
+	 * current runqueue lock, we would have to re-acquire it after putting
+	 * the thread into our remote CPU's runqueue (i.e., the source CPU for
+	 * the steal) before finally reaching cpu_wait() which lock-unblocks the
+	 * thread.  This would create a "hidden" and arbitrary additional
+	 * lock-ordering dependency between the source and destination locks of
+	 * tdq_move() on one hand, and our current runqueue's lock on the other
+	 * hand, sometimes violating the lock ordering established by
+	 * tdq_lock_pair().  Parallel steal attempts involving one of the
+	 * runqueue locks held by tdq_move() and our current runqueue's could
+	 * then cause a deadlock.
 	 */
-	TDQ_UNLOCK(tdq);
-	TDQ_LOCK(tdn);
+	tdq_lock_pair(tdq, true, tdn);
 	lowpri = tdq_add(tdn, td, flags);
 	tdq_notify(tdn, lowpri);
 	TDQ_UNLOCK(tdn);
-	TDQ_LOCK(tdq);
 #endif
 	return (TDQ_LOCKPTR(tdn));
 }