FreeBSD provides two tools that can be used to ensure correct usage of locks. The tools are lock assertions and a lock order verifier named witness. To demonstrate these tools, we'll provide code examples from a kernel module and then explain how the tools can be used. The module works by receiving events from a userland process via a sysctl. The event is then handed off to a kernel thread which performs the tasks associated with a specific event.
Both of these tools are only enabled if the kernel is compiled with support for them enabled. This allows a kernel tuned for performance to avoid the overhead of verifying the assertions while allowing for a debug kernel used in development to perform the extra checks. Currently both of these tools are enabled by default, but they will be disabled when the FreeBSD Project releases 5.0 for performance reasons. If either tool detects a fatal problem, then it will panic the kernel. If the kernel debugger is compiled in, then the panic will drop into the kernel debugger as well. For non-fatal problems, the tool may drop into the kernel debugger if the debugger is enabled and the tool is configured to do so.
Lock Assertions
Both mutexes and shared/exclusive locks provide macros to assert that a lock is held at any given point. For mutexes, one can assert that the current thread either owns the lock or does not own the lock. If the thread does own the lock, one can also assert that the lock is either recursed or not recursed. For shared/exclusive locks, one can assert that a lock is either locked in either fashion. If an assertion fails, then the kernel will panic and drop into the kernel debugger if the debugger is enabled.
For example, in the crash kernel module, events 14 and 15 trigger false lock assertions. Event 14 asserts that Giant is owned when it is not.
case 14:
mtx_assert(&Giant, MA_OWNED);
break;
When event 14 is triggered, the output on the kernel console is:
crash: assert that Giant is locked
panic: mutex Giant not owned at crash.c:202
cpuid = 3; lapic.id = 03000000
Debugger("panic")Stopped at Debugger+0x46: pushl %ebxdb>
Event 15 exclusively locks the sx lock foo and then asserts that it is share locked.
case 15:
sx_xlock(&foo);
sx_assert(&foo, SX_SLOCKED);
sx_xunlock(&foo);
When event 15 is triggered, the output on the kernel console is:
crash: assert that foo is slocked
while it is xlocked
panic: Lock (sx) foo exclusively locked@ crash.c:206.
cpuid = 1; lapic = 01000000Debugger("panic")Stopped at Debugger+0x46:
pushl %ebxdb>
Witness
Along with the mutex code and advice provided by BSDi came a lock order verifier called witness. A lock order verifier checks the order in which locks are acquired against a specified lock order. If locks are acquired out of order, than the code in question may deadlock against other code which acquires locks in the proper order. For the purposes of lock order, a lock A is said to be acquired before lock B, if lock B is acquired while holding lock A.
Witness does not use a static lock order, instead it dynamically builds a tree of lock order relationships. It starts with explicit lock orders hard-coded in the source code. Once the system is up and running, witness monitors lock acquires and releases to dynamically add new order relationships and report violations of previously established lock orders.
For example, if a thread acquires lock B while holding lock A, then witness will save the lock order relationship of A before B in its internal state. Later on if another thread attempts to acquire lock B while holding lock A, it will print a warning message on the console and optionally drop into the kernel debugger.
The BSD/OS implementation only worked with mutexes, but the FreeBSD Project has extended it to work with shared/exclusive locks as well. Locks are grouped into classes based on their names. Thus, witness will treat two different locks with the same name as the same. If two locks with the same name are acquired, witness will panic unless multiple acquires of locks of that name are explicitly allowed. This is because witness can not check the order in which locks of the same name are acquired. The only lock group that witness currently allows multiple acquires of member locks are process locks. This is safe because process locks follow a defined order of locking a child process before locking a parent process. The crash kernel module was originally written to test witness on sx locks, thus it contains events to violate lock orders to ensure that witness detects the reversals. Event 2 locks the sx lock foo followed by the the sx lock bar. Event 3 locks the sx lock bar followed by the sx lock foo.
case 2:
sx_slock(&foo);
sx_slock(&bar);
sx_sunlock(&foo);
sx_sunlock(&bar);
break;
case 3:
sx_slock(&bar);
sx_slock(&foo);
sx_sunlock(&foo);
sx_sunlock(&bar);
break;
When event 2 is triggered followed by event 3, the output on the kernel console is:
crash: foo then bar
crash: bar then foo
lock order reversal
1st 0xc335fce0 bar @ crash.c:142
2nd 0xc335fc80 foo @ crash.c:143
Debugger("witness_lock")
Stopped at Debugger+0x46: pushl %ebxdb<
Event 4 locks the sx lock bar, locks the sx lock foo, and then locks the sx lock bar2. The locks bar and bar2 both have the same name and thus belong to the same lock group.
case 4:
sx_slock(&bar);
sx_slock(&foo);
sx_slock(&bar2);
sx_sunlock(&bar2);
sx_sunlock(&foo);
sx_sunlock(&bar);
break;
When event 4 is triggered, the output on the kernel console is:
crash: bar then foo then bar
lock order reversal
1st 0xc3363ce0 bar @ crash.c:148
2nd 0xc3363c80 foo @ crash.c:149
3rd 0xc3363d40 bar @ crash.c:150
Debugger("witness_lock")Stopped at Debugger+0x46: pushl %ebxdb<
Note that if there are actually three locks involved in a reversal, all three are displayed. However, if two locks are merely reversing a previously established order, only the information about the two locks is displayed. In addition to performing checks, witness also adds a new command to the kernel debugger. The command show locks [pid] displays the locks held by a given thread. If a pid is not specified, then the locks held by the current thread are displayed. For example, after the panic in the previous example, the output is:
db< show locks
shared (sx) foo (0xc3363c80) locked@ crash.c:149
shared (sx) bar (0xc3363ce0) locked@ crash.c:148
Sleep mutexes and sx locks are displayed in the order they were acquired. If the thread is currently executing on a CPU, then any spin locks held by the current thread are displayed as well.
Source: http://www.usenix.org/events/bsdcon02/full_papers/baldwin/baldwin_html/node7.html
