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

From: Enji Cooper (yaneurabeya) <yaneurabeya_at_gmail.com>
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