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 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
runqueues locked.
Consider the following situation. sched_switch() executes on a third
CPU and decides to migrate its current thread to the above-mentioned
source CPU. To do so, it blocks it and put it on the new CPU's
runqueue, temporarily dropping the current (=third) CPU's runqueue lock
while acquiring the new CPU's one (to prevent a possible LOR). Once the
thread is on the new runqueue, it drops that runqueue's lock and wants
to re-acquire the current (=third) CPU's runqueue lock.
If that thread is the highest priority one in the new runqueue (the
above-mentioned source CPU's one), it can be the one stolen by
a concurrent tdq_move() as mentioned in the first paragraph. Let's
consider the case where that happens just before sched_switch()
re-acquires its (third) CPU's runqueue lock.
Finally, imagine that the long-term load balancer concurrently runs in
order to transfer a thread from the third CPU to one of the source or
destination CPUs evoked above. This run can easily be triggered by
appropriate load values on the three CPUs (typically, if Destination <
Source < Third). The load balancer (ultimately in sched_balance_pair())
first locks the third CPU's runqueue (assuming it has a lower CPU ID).
Let's assume it does so just before sched_switch() can re-acquire it but
after tdq_move() executed.
In this situation, the scheduler is deadlocked. In order for the load
balancer to acquire either the source and destination CPU's runqueue's
locks, they have to be released by tdq_move(), which requires the stolen
thread to become unblocked first. This can only happen if
sched_switch() can proceed to cpu_switch(), but for that it must first
re-acquire the third CPU's runqueue lock, which the load balancer
already holds.
To solve this situation while preserving some amount of "try steal"
efficiency (on sched_switch() with no more threads to execute), ensure
that tdq_move() only steals threads that have been unblocked already, so
that tdq_move() never has to wait for it to unblock.
Reported by: avg