Check out the new USENIX Web site. next up previous
Next: Diagnostic Tools Up: Locking in the Multithreaded Previous: Synchronization Primitives



Simply knowing how a lock functions or what API it uses is not sufficient to understand how a lock should be used. To help guide kernel developers in using locks properly, several guidelines have been crafted. Some of these guidelines were provided by the BSD/OS developers while others are the results of the experiences of FreeBSD developers.

Special Rules About Giant

The Giant sleep mutex is a temporary mutex used to protect data structures in the kernel that are not fully protected by another lock during the SMPng transition. Giant has to not interfere with other locks that are added. Thus, Giant has some unique properties.

First, no lock is allowed to be held while acquiring Giant. This ensures that other locks can always be safely acquired whether or not Giant is held. This in turn allows subsystems that have their own locks to be called directly without Giant being held, and to be called by other subsystems that still require Giant.

Second, the Giant mutex is automatically released by the sleep and condition variable wait function families before blocking and reacquired when a thread resumes. Since the Giant mutex is reacquired before the interlock lock and no other mutexes may be held while blocked, this does not result in any lock order reversals due to the first property. There are lock order reversals between the Giant mutex and locks held while a thread is blocked when the thread is resumed, but these reversals are not problematic since the Giant mutex is dropped when blocking on such locks.

Avoid Recursing on Exclusive Locks

A lock acquire is recursive if the thread trying to acquire the lock already holds the lock. If the lock is recursive, then the acquire will succeed. A recursed lock must be released by the owning thread the same number of times it has been acquired before it is fully released.

When an exclusive lock is acquired, the holder usually assumes that it has exclusive access to the object the lock protects. Unfortunately, recursive locks can break this assumption in some cases. Suppose we have a function F1 that uses a recursive lock L to protect object O. If function F2 acquires lock L, modifies object O so that is in an inconsistent state, and calls F1, F1 will recursively acquire L1 and falsely assume that O is in a consistent state.

One way of preventing this bug from going undetected is to use a non-recursive lock. Lock assertions can be placed in internal functions to ensure that calling functions obtain the necessary locks. This allows one to develop a locking protocol whereby callers of certain functions must obtain locks before calling the functions This must be balanced, however, with a desire to not require users of a public interface to acquire locks private to the subsystem.

For example, suppose a certain subsystem has a function G that is a public function called from other functions outside of this subsystem. Suppose that G is also called by other functions within the subsystem. Now there is a tradeoff involved. If you use assertions to require a lock to be held when G is called, then functions from other subsystems have to be aware of the lock in question. If, on the other hand, you allow recursion to make the interface to the subsystem cleaner, you can potentially allow the problem described above.

A compromise is to use a recursive lock, but to limit the places where recursion is allowed. This can be done by asserting that an acquired lock is not recursed just after acquiring it in places where recursion is not needed. However, if a lock is widely used, then it may be difficult to ensure that all places that acquire the lock make the proper assertions and that all places that the lock may be recursively acquired are safe.

An example of the first method is used with the psignal function. This function posts a signal to a process. The process has to be locked by the per-process lock during this operation. Since psignal is called from several places even including a few device drivers, it was desirable to acquire the lock in psignal itself. However, in other places such as signaling a parent process with SIGCHLD during process exit, several operations need to be performed while holding the process lock. This resulted in recursing on the process lock. Due to the wide use of the process lock, it was determined that the lock should remain non-recursive. Thus, psignal asserts that a process being signaled is locked, and callers are required to lock the process explicitly.

Currently in FreeBSD, mutexes are not recursive by default. A mutex can be made recursive by passing a flag to mtx_init. Exclusive sx locks never allow recursion, but shared sx locks always allow recursion. If a thread attempts to recursively lock a non-recursive lock, the kernel will panic reporting the file and line number of the offending lock operation.

Avoid Holding Exclusive Locks for Long Periods of Time

Exclusive locks reduce concurrency and should be held for as short a time as possible. Since a thread can block for an indeterminate amount of time, it follows that exclusive locks should not be held by a blocked thread when possible. Locks that should be held by a blocked thread are protecting data structures already protected in the pre-SMPng kernel. Thus, only locks present prior to SMPng should be held by a blocked thread, but new locks should not be held while blocked. The existing locks should be sufficient to cover the cases when an object needs to be locked by a blocked thread. An example of this type of lock would be a lock associated with a file's contents.

Functions that block such as the sleep and cv_wait families of functions should not be called with any locks held. Exceptions to this rule are the Giant lock, the optional interlock lock passed to the function, and locks that can be held by a blocked thread. Since these functions only release the interlock once, they should not be called with the interlock recursively acquired.

Note that it is better to hold a lock for a short period of time when it is not needed than to drop the lock only to reacquire it. Otherwise, the thread may have to block when it tries to reacquire the lock. For example, suppose lock L protects two lists A and B and that the objects on the lists do not need locks since they only have one reference at a time. Then, a section of code may want to remove an object from list A, set a flag in the object, and store the object on list B. The operation of setting the flag does not require a lock due to the nature of the object, thus the code could drop the lock around that operation. However, since the operations to drop and acquire the lock are more expensive than the operation to set a flag, it is better to lock L, remove an object from list A, set the flag in the object, put the object on list B, and then release the lock.

Use Sleep Mutexes Rather Than Spin Mutexes

As described earlier, spin mutexes block interrupts while they are held. Thus, holding spin mutexes can increase interrupt latency and should be avoided when possible. Sleep mutexes require a context in case they block, however, so sleep mutexes may not be used in interrupt handlers that do not run in a thread context. Instead, these handlers must use spin mutexes. Spin mutexes may also need to be used in non-interrupt contexts or in threaded interrupt handlers to protect data structures shared with non-threaded interrupt handlers. All other mutexes should be sleep mutexes to avoid increasing interrupt latency. Also note that since locking a sleep mutex may potentially block, a sleep mutex may not be acquired while holding a spin mutex. Unlocking a contested sleep mutex may result in switching to a higher priority thread that was waiting on the mutex. Since we cannot switch while holding a spin mutex, this potential switch must be disabled by passing the MTX_NOSWITCH flag when releasing a sleep mutex while holding a spin mutex.

Lock Both Reads and Writes

Data objects protected by locks must be protected for both reads and writes. Specifically, if a data object needs to be locked when writing to the object, it also needs to be locked when reading from the object. However, a read lock does not have to be as strong as a write lock. A read lock simply needs to ensure that the data it is reading is coherent and up to date. Memory barriers within the locks guarantee that the data is not stale. All that remains for a read lock is that the lock block all writers until it is released. A write lock, on the other hand, must block all readers in addition to meeting the requirements of a read lock. Note that a write lock is always sufficient protection for reading.

Read locks and write locks can be implemented in several ways. If an object is protected by a mutex, then the mutex must be held for read and write locks. If an object is protected by an sx lock, then a shared lock is sufficient for reading, but an exclusive lock is required for writing. If an object is protected by multiple locks, then a read lock of at least one of the locks is sufficient for reading, but a write lock of all locks is required for writing.

An example of this method is the pointer to the parent process within a process structure. This pointer is protected by both the proctree_lock sx lock and the per-process mutex. Thus, to read the parent process pointer, one only needs to either grab a shared or exclusive lock of the proctree_lock or lock the process structure itself. However, to set the parent process pointer, both locks must be locked exclusively. Thus, the inferior function asserts that the proctree_lock is locked while it walks up the process tree seeing if a specified process is a child of the current process, while psignal simply needs to lock the child process to read the parent process pointer while posting SIGCHLD to the parent. However, when re-parenting a process, both the child process and the process tree must be exclusively locked.

next up previous
Next: Diagnostic Tools Up: Locking in the Multithreaded Previous: Synchronization Primitives