From nobody Sat Nov 14 16:29:48 2026 X-Original-To: dev-commits-src-all@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 4jRfjS6Dpsz71Mbr for ; Sat, 14 Nov 2026 16:29:48 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange x25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by mx1.freebsd.org (Postfix) with ESMTPS id 4jRfjS50jqz4g23 for ; Sat, 14 Nov 2026 16:29:48 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1794673788; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=H49AV7jhVHcO4/vz8laUBa/U2mnSWZVKfByPyVgHm4Q=; b=WRBtrMgoXeBaB5LggbOlOvkRZ+3Cl0KlYJp8wYHAy0ZgMjBiXvMWNR9SiKEsSkgRVgJLni 2ORK/brVCT+J4PYT6pPbGI/OccdZc02wDUvE6PWcSQgxkA2NH+upfGs4+ap7g5IPgXj2ne EIzjOiHean4PF6JovwHfGPWLGGwVaxpTy8sOdilPFic32cTlFJotbXHGwbvokENMOH45t0 uvFxwyM7/YX3x0bklcOSRQC3icRZIULIlR9xyVCBjwXlS84rZ5DknDzofcxms6i5AsVwdW yNITxdYn1P/IEq/AOikRLmUmKk41cOQj8Oz4mxZ9q0NhCKkX5GiwwD4hcnzOGQ== ARC-Seal: i=1; a=rsa-sha256; d=freebsd.org; s=dkim; cv=none; t=1794673788; b=dVTen6Bb7VKqLsiFvOLk7ZK6Cda2oOxOeyDAEQ0kk6aj3z1Ccf4Rxi2wvuSIaszcO38nxm g1pr8Tns2lBvbRYaiUDEVvboShdSG0G0q25nXC7LY4Nt6xzXExZZC3BtvkGPJk/TOnxovO UFuXdjDh4ObeDU/5pFAhGS3iqKk+oXXAidY4bjM0WLYYHaNXKoALvF12GNCjUgtw/NNJdh rAaTWYNKt3aDnXpt8oggbeOG4FnITI46PmHLEVUmYpzW7f7ZIsQwm6GTUlJECpK3pIcxvw LieckvKnXOkjKo6XLQSAg4rsqvcIz3QfmCotI9S7/bUMA6XRV1ichFT9y/FyAg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1794673788; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=H49AV7jhVHcO4/vz8laUBa/U2mnSWZVKfByPyVgHm4Q=; b=id2bo3HHdbrC1LgJggIb3xX5eFD4P1nHhtpUcKanxPAdifmGNOayipoIXFwryoAf3995bo mLa0UEqW38RsVCRvrRvrY+wgBhmlbai5WhyNV6mS3RA3tRt3YsCeKgz0vNjmXl/EJpp+Ig 6HiT8JDsSmQItHpInP1RGdIE/2U7Z+Ng0+o45g4W91WCuCAuy5cG/6Ht0ZFay6y7F6Pmud WdY5tIoiBzkQkwPLiwHnKfu5lPszkOc+z49lxTQa4RGGqFXZFhXpWObMSteoH0sdL1ZV0r 2hZ6ZpE6rNAljcGKjwHC36GGbjL3zH7FbRb0P1Vyn0S5RlO5BHHLBwffhZ27/g== ARC-Authentication-Results: i=1; mx1.freebsd.org; none Received: from gitrepo.freebsd.org (gitrepo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:5]) by mxrelay.nyi.freebsd.org (Postfix) with ESMTP id 4jRfjS4fN0zRmt for ; Sat, 14 Nov 2026 16:29:48 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from git (uid 1279) (envelope-from git@FreeBSD.org) id 174f6 by gitrepo.freebsd.org (DragonFly Mail Agent v0.13+ on gitrepo.freebsd.org); Sat, 14 Nov 2026 16:29:48 +0000 To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org From: Olivier Certner Subject: git: 538c48bf6247 - main - sched_ule: Fix rare deadlock on stealing a migrated lock-blocked thread List-Archive: https://lists.freebsd.org/archives/dev-commits-src-all X-BeenThere: dev-commits-src-all@freebsd.org List-Id: Commit messages for all branches of the src repository List-Post: List-Help: List-Subscribe: List-Unsubscribe: List-Owner: Precedence: list MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: olce X-Git-Repository: src X-Git-Refname: refs/heads/main X-Git-Reftype: branch X-Git-Commit: 538c48bf6247a2895b364c96f495be4cc7df1933 Auto-Submitted: auto-generated Date: Sat, 14 Nov 2026 16:29:48 +0000 Message-Id: <6af88c7c.174f6.cd8bbc2@gitrepo.freebsd.org> The branch main has been updated by olce: URL: https://cgit.FreeBSD.org/src/commit/?id=538c48bf6247a2895b364c96f495be4cc7df1933 commit 538c48bf6247a2895b364c96f495be4cc7df1933 Author: Olivier Certner AuthorDate: 2026-11-11 21:41:45 +0000 Commit: Olivier Certner 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 + * (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)); }