* Global ordering of mutexes in the garbage collector

For a program to deadlock with mutexes, there must be a cycle in the
directed graph whose nodes are threads and which has an edge from
thread A to thread B whenever A is waiting for a mutex locked by B.
In other words, there must be some A waiting for some B, who is
waiting for some C, ... who is waiting for A.  If this were not the
case, then every chain of waiting threads ends with a thread that's
not waiting for anyone else.  Since that thread's runnable, it's not a
mutex deadlock.

The standard way to prevent deadlocks is to declare a partial ordering
among all the mutexes threads might contend for.  By definition,
partial orderings are acyclic, so there is no cycle of mutexes such
that X < Y < Z < ... < X.  Then, we write the code so that threads
never try to lock a new mutex Y while holding a mutex X unless X < Y.

Following this rule, deadlock cycles cannot form.  Each thread in such
a cycle would be holding some mutex X while waiting to acquire some
other mutex Y.  This wouldn't be permitted unless X < Y.  But then
walking the deadlock cycle would yield a cycle of mutexes X < Y < Z <
... < X.  Which we know can't happen, since < is a partial order.

Partial orderings are transitive, so if we've written that A < B and B
< C, then you may assume that A < C.



So, here is our global ordering for mutexes in Minor.

If A and B are mutexes, a thread will never try to lock a mutex B
while holding a mutex A unless A < B in this ordering.  If you do find
you need to hold two locks A and B simultaneously, but ! (A < B),
there are two possibilities:

- If B < A, then you can back out of what you're doing, acquire B, and
  then re-acquire A.

- If neither A < B nor B < A, then you are not permitted to hold those
  two locks simultaneously at all.  You'll need to add some entry to
  the table below, while ensuring that it is still a valid partial
  order.  There will usually be one direction that makes more sense
  than the other.

The order in which resources appear here to the left of the "<"
respects the overall partial ordering of resources.

incoherent_mutex < global_ref_group_mutex
incoherent_mutex < symbol_hash_mutex
incoherent_mutex < allocation_mutex
symbol_hash_mutex < allocation_mutex

One catch to all this is that the proof of freedom from deadlock only
reassures you if the entire program respects the partial ordering ---
the user's code as well as Minor.  So it's not sufficient for the
Minor library to be well-behaved by itself: in general, we would need
to include the mutex partial ordering as part of Minor's public
interface, explain how and when each Minor entry point uses the
mutexes, and so on.  But that's really hairy.

Fortunately, we can finesse things.  If Minor always releases all its
mutexes before control leaves Minor code (in addition to respecting
the rules described above), then the program will never try to acquire
any non-Minor mutexes while holding any Minor mutexes.  Minor mutexes
cannot participate in a deadlock cycle.  But note that this means more
than just releasing your mutexes before you return: invoking a
callback function provided by the user counts as "control leaving
Minor code", as does making any system call that could block.


;;; Local Variables:
;;; dabbrev-friend-buffer-function: jimb-c-mode-p
;;; End: