From nobody Mon Nov 16 01:06:43 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 4jSV7j5vY2z70dDN; Mon, 16 Nov 2026 01:06:57 +0000 (UTC) (envelope-from kib@freebsd.org) Received: from kib.kiev.ua (kib.kiev.ua [IPv6:2001:470:d5e7:1::1]) (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 4jSV7f5vkqz4pxD; Mon, 16 Nov 2026 01:06:54 +0000 (UTC) (envelope-from kib@freebsd.org) Authentication-Results: mx1.freebsd.org; dkim=none; dmarc=fail reason="No valid SPF, No valid DKIM" header.from=freebsd.org (policy=none); spf=softfail (mx1.freebsd.org: 2001:470:d5e7:1::1 is neither permitted nor denied by domain of kib@freebsd.org) smtp.mailfrom=kib@freebsd.org Received: from tom.home (kib@localhost [127.0.0.1] (may be forged)) by kib.kiev.ua (8.18.1/8.18.1) with ESMTPS id 6AG16hgA086856 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NO); Mon, 16 Nov 2026 03:06:46 +0200 (EET) (envelope-from kib@freebsd.org) DKIM-Filter: OpenDKIM Filter v2.10.3 kib.kiev.ua 6AG16hgA086856 Received: (from kostik@localhost) by tom.home (8.18.1/8.18.1/Submit) id 6AG16hFI086854; Mon, 16 Nov 2026 03:06:43 +0200 (EET) (envelope-from kib@freebsd.org) X-Authentication-Warning: tom.home: kostik set sender to kib@freebsd.org using -f Date: Mon, 16 Nov 2026 03:06:43 +0200 From: Konstantin Belousov To: Olivier Certner Cc: src-committers@freebsd.org, dev-commits-src-all@freebsd.org, dev-commits-src-main@freebsd.org Subject: Re: git: 538c48bf6247 - main - sched_ule: Fix rare deadlock on stealing a migrated lock-blocked thread Message-ID: References: <6af88c7c.174f6.cd8bbc2@gitrepo.freebsd.org> 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=us-ascii Content-Disposition: inline In-Reply-To: <6af88c7c.174f6.cd8bbc2@gitrepo.freebsd.org> X-Spam-Status: No, score=-2.9 required=5.0 tests=ALL_TRUSTED,BAYES_00 autolearn=ham autolearn_force=no version=4.0.2 X-Spam-Checker-Version: SpamAssassin 4.0.2 (2025-08-27) on tom.home X-Rspamd-Queue-Id: 4jSV7f5vkqz4pxD X-Spamd-Bar: / X-Spamd-Result: default: False [0.00 / 15.00]; MIME_GOOD(-0.10)[text/plain]; DMARC_POLICY_SOFTFAIL(0.10)[freebsd.org : No valid SPF, No valid DKIM,none]; ARC_NA(0.00)[]; R_DKIM_NA(0.00)[]; HAS_XAW(0.00)[]; ASN(0.00)[asn:6939, ipnet:2001:470::/32, country:US]; MIME_TRACE(0.00)[0:+]; FREEFALL_USER(0.00)[kib]; TO_DN_SOME(0.00)[]; MISSING_XM_UA(0.00)[]; MLMMJ_DEST(0.00)[dev-commits-src-all@freebsd.org,dev-commits-src-main@freebsd.org]; RCVD_TLS_LAST(0.00)[]; FROM_EQ_ENVFROM(0.00)[]; FROM_HAS_DN(0.00)[]; DNSWL_BLOCKED(0.00)[2001:470:d5e7:1::1:from]; RCVD_COUNT_TWO(0.00)[2]; TO_MATCH_ENVRCPT_ALL(0.00)[]; R_SPF_SOFTFAIL(0.00)[~all]; RCPT_COUNT_THREE(0.00)[4] 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 > 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 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)); > }