Lock Options

D Implementation

To make my deadlock-prevention scheme practical, I need to automate code generation. In D, code can be generated from strings using mixins. Strings can be manipulated during compile time to produce the desired code. Moreover, in D, you don't have to learn a separate language to evaluate things at compile time. A sizable subset of D can be executed at compile time. Because compile-time functions can also be called at runtime, testing and debugging is a breeze.

I start with the task of creating some global declarations. I need to:

• Declare a global array of mutexes.
• Generate code that will initialize it at startup.
• Declare the hierarchy of interfaces that encapsulate lock options.
• Generate some helper functions for type parsing.

The input, known at compile time, is the list of lock names. Here, I name my locks "A", "B", and "C" (normally, one would use more meaningful names). In client's code, all this is accomplished in one top-level statement:

mixin(declareAllLocks   (["A", "B", "C"])); 

The order in which lock names are specified doesn't matter—they will be sorted alphabetically at compile time.

Particular lock options are generated using a compile-time function, Options, which again takes a list of lock names. The result of Options, a string, is converted to a proper type at compile time using a template ToType. For instance, to generate the type that encapsulates the option to take locks "A" and "B", the client writes:

ToType!(Options(["A", "B"])) 

D's template syntax uses the exclamation mark to introduce template parameters (equivalent to angle brackets in C++ and lookalikes). Here, the template ToType is parametrized by a compile-time string returned by Options.

Below is the declaration of a function with the option to take locks "A" and "B":

void takeAB(ToType!(Options(["A",     "B"])) lockOptions); 

Notice that the lock option variable must be named lockOptions for another mixin, LOCK, to work. This mixin combines the taking of a named lock with the declaration of a new local variable, lockOptions, as described earlier. Here, lock "A" is taken for the duration of its scope:

mixin(LOCK("A")); 

Listing Two shows the example of user code. The complete implementation is available online at www.ddj.com/code/).

Conclusion

The deadlock-prevention scheme described here has a lot of limitations. It doesn't work with fine-grain locking, where the number of dynamically created objects with their own locks is unpredictable. It doesn't deal with more general reentrancy, where a thread can retake any of the locks it already holds. On the other hand, lock-taking is encoded in the type system, so once the program compiles, it is guaranteed not to deadlock (at least not on the locks that take part in the scheme). That's a much stronger guarantee than even the most comprehensive runtime testing can provide.

Acknowledgments

I'm grateful to Scott Meyers for making an early version of his paper available to me, and to Andrei Alexandrescu and Walter Bright for valuable comments.

interface NoLock {} 
interface A: NoLock {} 
interface B: NoLock {} 
interface C: NoLock {} 
interface A_B: B,A {} 
interface A_C: C,A {} 
interface B_C: C,B {} 
interface A_B_C: B_C,A_C,A_B {} 

mixin(declareAllLocks(["A", "B", "C"])); 
void takeC(ToType!(Options(["C"])) lockOptions) { 
  { 
    mixin(LOCK("C")); 
  } 
} 
void takeBC(ToType!(Options(["B", "C"])) lockOptions) { 
  { 
    mixin(LOCK("B")); 
    takeC(lockOptions); 
  } 
} 
void main() { 
  ToType!(Options(["C", "B", "A"])) lockOptions; 
  takeBC(lockOptions); 
}