The kernel lock validator

Posted May 31, 2006 3:28 UTC (Wed) by walken (subscriber, #7089)
Parent article: The kernel lock validator

This may be a dumb question, but why not assign an explicit rank to every lock type ?

That way, the lock ranks double as documentation of the lock ordering.

(I'm using this quite successfully at work for a kernel-type project, though not related to linux).

to post comments

The kernel lock validator

Posted May 31, 2006 6:22 UTC (Wed) by dlang (guest, #313) [Link] (1 responses)

the list of locks is not static.

remember basic and line numbers? no matter how you started your numbering scheme you eventually ran into trouble.

David Lang

The kernel lock validator

Posted Jun 9, 2006 4:13 UTC (Fri) by slamb (guest, #1070) [Link]

The list of lock keys is static, and that's what would get assigned ranks. I quote from the article:

Locks which are allocated dynamically (as most locks embedded within structures are) [...] should be mapped to a single key. [...] Thus, for each lock initialization, this code creates a static variable (__key) and uses its address as the key identifying the type of the lock. Since any particular type of lock tends to be initialized in a single place, this trick associates the same key with every lock of the same type.

I also work in a project which assigns ranks manually.

Disadvantage: especially given the number of locks in the Linux kernel, it'd be a large initial effort to go through and create a ranking consistent with all the approved locking orders. (On the other hand, not doing it probably means struggling with this list over and over without it actually being written down anywhere.)

Advantage: you wouldn't even need to run through two code paths to know that they can deadlock - just the one you've defined as wrong.

Advantage: it'd remove all the heaviness of the lock validator. There's no need for the "before" and "after" lists; the rank defines them. The stack could be just a bit array - small enough that it's probably practical to preallocate its full extent on thread creation. Thus, the lock validator would not add potential out of memory failures, and it'd run quickly. There'd be no reason not to always have it on.

(Actually, I'm not sure how strict the same-key locking stuff (spin_lock_nested and such) is. To track those, a fancier stack might still be necessary.)