aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorOlivier Certner <olce@FreeBSD.org>2026-11-11 21:41:45 +0000
committerOlivier Certner <olce@FreeBSD.org>2026-11-14 16:29:33 +0000
commit538c48bf6247a2895b364c96f495be4cc7df1933 (patch)
tree37e15679340a7015d0ff1bd29a0d32d5a7fd5c6c
parent2210a2f8d4705eee0bf3d89a8e30f0babb40fed1 (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.c53
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));
}