started by Ingo Molnar <mingo@redhat.com>
updated by Davidlohr Bueso <davidlohr@hp.com>
What are mutexes?¶
In the Linux kernel, mutexes refer to a particular locking primitivethat enforces serialization on shared memory systems, and not only tothe generic term referring to ‘mutual exclusion’ found in academiaor similar theoretical text books. Mutexes are sleeping locks whichbehave similarly to binary semaphores, and were introduced in 2006[1]as an alternative to these. This new data structure provided a numberof advantages, including simpler interfaces, and at that time smallercode (see Disadvantages).
Implementation¶
Mutexes are represented by ‘struct mutex’, defined in include/linux/mutex.hand implemented in kernel/locking/mutex.c. These locks use an atomic variable(->owner) to keep track of the lock state during its lifetime. Field owneractually contains struct task_struct * to the current lock owner and it istherefore NULL if not currently owned. Since task_struct pointers are alignedat at least L1_CACHE_BYTES, low bits (3) are used to store extra state (e.g.,if waiter list is non-empty). In its most basic form it also includes await-queue and a spinlock that serializes access to it. Furthermore,CONFIG_MUTEX_SPIN_ON_OWNER=y systems use a spinner MCS lock (->osq), describedbelow in (ii).
When acquiring a mutex, there are three possible paths that can betaken, depending on the state of the lock:
fastpath: tries to atomically acquire the lock by cmpxchg()ing the owner withthe current task. This only works in the uncontended case (cmpxchg() checksagainst 0UL, so all 3 state bits above have to be 0). If the lock iscontended it goes to the next possible path.
midpath: aka optimistic spinning, tries to spin for acquisitionwhile the lock owner is running and there are no other tasks readyto run that have higher priority (need_resched). The rationale isthat if the lock owner is running, it is likely to release the locksoon. The mutex spinners are queued up using MCS lock so that onlyone spinner can compete for the mutex.
The MCS lock (proposed by Mellor-Crummey and Scott) is a simple spinlockwith the desirable properties of being fair and with each cpu tryingto acquire the lock spinning on a local variable. It avoids expensivecacheline bouncing that common test-and-set spinlock implementationsincur. An MCS-like lock is specially tailored for optimistic spinningfor sleeping lock implementation. An important feature of the customizedMCS lock is that it has the extra property that spinners are able to exitthe MCS spinlock queue when they need to reschedule. This further helpsavoid situations where MCS spinners that need to reschedule would continuewaiting to spin on mutex owner, only to go directly to slowpath uponobtaining the MCS lock.
slowpath: last resort, if the lock is still unable to be acquired,the task is added to the wait-queue and sleeps until woken up by theunlock path. Under normal circ*mstances it blocks as TASK_UNINTERRUPTIBLE.
While formally kernel mutexes are sleepable locks, it is path (ii) thatmakes them more practically a hybrid type. By simply not interrupting atask and busy-waiting for a few cycles instead of immediately sleeping,the performance of this lock has been seen to significantly improve anumber of workloads. Note that this technique is also used for rw-semaphores.
Semantics¶
The mutex subsystem checks and enforces the following rules:
- Only one task can hold the mutex at a time.
- Only the owner can unlock the mutex.
- Multiple unlocks are not permitted.
- Recursive locking/unlocking is not permitted.
- A mutex must only be initialized via the API (see below).
- A task may not exit with a mutex held.
- Memory areas where held locks reside must not be freed.
- Held mutexes must not be reinitialized.
- Mutexes may not be used in hardware or software interruptcontexts such as tasklets and timers.
These semantics are fully enforced when CONFIG DEBUG_MUTEXES is enabled.In addition, the mutex debugging code also implements a number of otherfeatures that make lock debugging easier and faster:
- Uses symbolic names of mutexes, whenever they are printedin debug output.
- Point-of-acquire tracking, symbolic lookup of function names,list of all locks held in the system, printout of them.
- Owner tracking.
- Detects self-recursing locks and prints out all relevant info.
- Detects multi-task circular deadlocks and prints out all affectedlocks and tasks (and only those tasks).
Interfaces¶
Statically define the mutex:
DEFINE_MUTEX(name);
Dynamically initialize the mutex:
mutex_init(mutex);
Acquire the mutex, uninterruptible:
void mutex_lock(struct mutex *lock);void mutex_lock_nested(struct mutex *lock, unsigned int subclass);int mutex_trylock(struct mutex *lock);
Acquire the mutex, interruptible:
int mutex_lock_interruptible_nested(struct mutex *lock, unsigned int subclass);int mutex_lock_interruptible(struct mutex *lock);
Acquire the mutex, interruptible, if dec to 0:
int atomic_dec_and_mutex_lock(atomic_t *cnt, struct mutex *lock);
Unlock the mutex:
void mutex_unlock(struct mutex *lock);
Test if the mutex is taken:
int mutex_is_locked(struct mutex *lock);
Disadvantages¶
Unlike its original design and purpose, ‘struct mutex’ is among the largestlocks in the kernel. E.g: on x86-64 it is 32 bytes, where ‘struct semaphore’is 24 bytes and rw_semaphore is 40 bytes. Larger structure sizes mean more CPUcache and memory footprint.
When to use mutexes¶
Unless the strict semantics of mutexes are unsuitable and/or the criticalregion prevents the lock from being shared, always prefer them to any otherlocking primitive.
