Beautiful Code [62]
So, Jeff and I discussed the details of our solution over coffee, and he returned to write the block comment explaining our deceptively simple code change. Frankly, given the arguable inelegance of our solution, I was expecting the comment to be something of a confessional, adorned with the usual adjectives used in such comments, like "gross," "disgusting," or "vile."[**] But Jeff surprised me with what I believe is the best comment in all of Solaris—if not all of software:
[**] Which brings up a good tip: search for these words—along with classic standbys such as "XXX" and "FIXME"—in any source base for which you're curious where the bodies are buried.
Code View: Scroll / Show All
/*
* The turnstile hash table is partitioned into two halves: the lower half
* is used for upimutextab[] locks, the upper half for everything else.
* The reason for the distinction is that SOBJ_USER_PI locks present a
* unique problem: the upimutextab[] lock passed to turnstile_block( )
* cannot be dropped until the calling thread has blocked on its
* SOBJ_USER_PI lock and willed its priority down the blocking chain.
* At that point, the caller's t_lockp will be one of the turnstile locks.
* If mutex_exit( ) discovers that the upimutextab[] lock has waiters, it
* must wake them, which forces a lock ordering on us: the turnstile lock
* for the upimutextab[] lock will be acquired in mutex_vector_exit( ),
* which will eventually call into turnstile_pi_waive( ), which will then
* acquire the caller's thread lock, which in this case is the turnstile
* lock for the SOBJ_USER_PI lock. In general, when two turnstile locks
* must be held at the same time, the lock order must be the address order.
* Therefore, to prevent deadlock in turnstile_pi_waive( ), we must ensure
* that upimutextab[] locks *always* hash to lower addresses than any
* other locks. You think this is cheesy? Let's see you do better.
*/
#define TURNSTILE_HASH_SIZE 128 /* must be power of 2 */
#define TURNSTILE_HASH_MASK (TURNSTILE_HASH_SIZE - 1)
#define TURNSTILE_SOBJ_HASH(sobj) \
((((ulong_t)sobj >> 2) + ((ulong_t)sobj >> 9)) & TURNSTILE_HASH_MASK)
#define TURNSTILE_SOBJ_BUCKET(sobj) \
((IS_UPI(sobj) ? 0 : TURNSTILE_HASH_SIZE) + TURNSTILE_SOBJ_HASH(sobj))
#define TURNSTILE_CHAIN(sobj) turnstile_table[TURNSTILE_SOBJ_BUCKET(sobj)]
typedef struct turnstile_chain {
turnstile_t *tc_first; /* first turnstile on hash chain */
disp_lock_t tc_lock; /* lock for this hash chain */
} turnstile_chain_t;
turnstile_chain_t turnstile_table[2 * TURNSTILE_HASH_SIZE];
The tone of Jeff's comment much more accurately conveyed our sentiment than the confessional that I was envisioning: we implemented this solution not because we were defeated, but because it was the only way to conquer one of the most challenging problems that either of us had ever faced. And some may think it cheesy, but in the seven years since this code has integrated, no one has done better—and as of this writing, it seems unlikely that anyone ever will. To me at least, that's about as beautiful as code can get—cheesy or not.
So, the story had a happy ending: we integrated the fixes, and shipped the product on time. But the experience served to remind us of several principles of good software engineering:
Implement early
None of the problems that we faced was foreseen by Jeff or me, despite the fact that we had both spent time thinking about the problem during its design and implementation. Indeed, even after we encountered the initial bugs and were thus revisiting the problem very closely, the deeper problem still didn't occur to us; we had to encounter it to understand it.
Pound on it
We would have encountered these issues much, much earlier if the original engineer had implemented stress tests instead