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

From: Konstantin Belousov <kib_at_freebsd.org>
Date: Mon, 16 Nov 2026 01:06:43 UTC
On Sat, Nov 14, 2026 at 04:29:48PM +0000, Olivier Certner wrote:
> 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
We cannot sleep (or block) there at all.
s/sleep/spin/

> +			 * (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
s/cpu_wait/cpu_switch/

> +	 * 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));
>  }