Re: git: 538c48bf6247 - main - sched_ule: Fix rare deadlock on stealing a migrated lock-blocked thread
Date: Wed, 18 Nov 2026 07:34:26 UTC
> On Nov 15, 2026, at 5:06 PM, Konstantin Belousov <kib@FreeBSD.org> wrote:
>
> 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));
>> }
This probably caused https://bugs.freebsd.org/bugzilla/show_bug.cgi?id=300858 .
Cheers,
-Enji