aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-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));
}