Re: git: 538c48bf6247 - main - sched_ule: Fix rare deadlock on stealing a migrated lock-blocked thread
- Reply: Enji Cooper (yaneurabeya): "Re: git: 538c48bf6247 - main - sched_ule: Fix rare deadlock on stealing a migrated lock-blocked thread"
- In reply to: Olivier Certner : "git: 538c48bf6247 - main - sched_ule: Fix rare deadlock on stealing a migrated lock-blocked thread"
- Go to: [ bottom of page ] [ top of archives ] [ this month ]
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));
> }