Beautiful Code [52]
Of course, this is not to say that every bug is necessarily fatal—just that the possibility always exists that a single bug will reveal something much larger than its manifestations: a design flaw that calls into question the fundamental assumptions upon which the software was built. Such a flaw can shake software to its core and, in the worst case, invalidate it completely. That is, a single software bug can be the proverbial spoonful of sewage in the barrel of wine, turning what would otherwise be an enjoyable pleasure into a toxic stew.
For me personally, this fine line between wine and sewage was never so stark as in one incident in the development of a critical subsystem of the Solaris kernel in 1999. This problem—and its solution—are worth discussing at some length, for they reveal how profound design defects can manifest themselves as bugs, and how devilish the details can become when getting a complicated and important body of software to function perfectly.
A word of caution before we begin: this journey will take us deep into the core of the Solaris kernel, into some of the most fundamental and subtlest mechanism of the operating system. As such, the detail may seem crushing; like adventurous spelunkers, we will at times be wading through dark, cold water or squeezing through suffocatingly tight passages—but for those that make the trip, a hidden and beautiful underground cavern awaits. So if you're ready, don your headlamp, grab a water bottle, and let's descend into the Solaris kernel….
The subsystem that is the center of our story is the turnstile subsystem. A turnstile is the mechanism used to block and wake up threads in Solaris—it is the underpinning of synchronization primitives such as mutexes and reader/writer locks. Or, to let the code speak for itself:[*]
[*] This code is open source and is available at http://src.opensolaris.org/source/xref/onnv/onnv-gate/usr/src/uts/common/os/turnstile.c.
Code View: Scroll / Show All
/*
* Turnstiles provide blocking and wakeup support, including priority
* inheritance, for synchronization primitives (e.g. mutexes and rwlocks).
* Typical usage is as follows:
*
* To block on lock 'lp' for read access in foo_enter( ):
*
* ts = turnstile_lookup(lp);
* [ If the lock is still held, set the waiters bit
* turnstile_block(ts, TS_READER_Q, lp, &foo_sobj_ops);
*
* To wake threads waiting for write access to lock 'lp' in foo_exit( ):
*
* ts = turnstile_lookup(lp);
* [ Either drop the lock (change owner to NULL) or perform a direct
* [ handoff (change owner to one of the threads we're about to wake).
* [ If we're going to wake the last waiter, clear the waiters bit.
* turnstile_wakeup(ts, TS_WRITER_Q, nwaiters, new_owner or NULL);
*
* turnstile_lookup( ) returns holding the turnstile hash chain lock for lp.
* Both turnstile_block() and turnstile_wakeup( ) drop the turnstile lock.
* To abort a turnstile operation, the client must call turnstile_exit( ).
*
...
The turnstile abstraction thus allows synchronization primitives to focus on their own particular policy without worrying about the delicate mechanics of blocking and awakening. As the block comment mentions, turnstile_block() is the function called to actually block the current thread on a synchronization primitive, and it is in this function that our subterranean journey begins in earnest with this cryptic comment of mine:
/*
* Follow the blocking chain to its end, willing our priority to
* everyone who's in our way.
*/
while (t->t_sobj_ops != NULL &&
(owner = SOBJ_OWNER(t->t_sobj_ops, t->t_wchan)) != NULL) {
if (owner == curthread) {
if (SOBJ_TYPE(sobj_ops) != SOBJ_USER_PI) {
panic("Deadlock: cycle in blocking chain");
}
/*
* If the cycle we've encountered ends in mp,
* then we know it isn't a 'real' cycle because
* we're going to drop mp before we go