diff options
| author | Olivier Certner <olce@FreeBSD.org> | 2026-11-11 21:41:45 +0000 |
|---|---|---|
| committer | Olivier Certner <olce@FreeBSD.org> | 2026-11-14 16:29:33 +0000 |
| commit | 538c48bf6247a2895b364c96f495be4cc7df1933 (patch) | |
| tree | 37e15679340a7015d0ff1bd29a0d32d5a7fd5c6c | |
| parent | 2210a2f8d4705eee0bf3d89a8e30f0babb40fed1 (diff) | |
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
| -rw-r--r-- | sys/kern/sched_ule.c | 53 |
1 files 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)); } |
