Documentation/locking/mutex-design.rst

   1 =======================
   2 Generic Mutex Subsystem
   3 =======================
   4
   5 started by Ingo Molnar <mingo@redhat.com>
   6
   7 updated by Davidlohr Bueso <davidlohr@hp.com>
   8
   9 What are mutexes?
  10 -----------------
  11
  12 In the Linux kernel, mutexes refer to a particular locking primitive
  13 that enforces serialization on shared memory systems, and not only to
  14 the generic term referring to 'mutual exclusion' found in academia
  15 or similar theoretical text books. Mutexes are sleeping locks which
  16 behave similarly to binary semaphores, and were introduced in 2006[1]
  17 as an alternative to these. This new data structure provided a number
  18 of advantages, including simpler interfaces, and at that time smaller
  19 code (see Disadvantages).
  20
  21 [1] http://lwn.net/Articles/164802/
  22
  23 Implementation
  24 --------------
  25
  26 Mutexes are represented by 'struct mutex', defined in include/linux/mutex.h
  27 and implemented in kernel/locking/mutex.c. These locks use an atomic variable
  28 (->owner) to keep track of the lock state during its lifetime.  Field owner
  29 actually contains `struct task_struct *` to the current lock owner and it is
  30 therefore NULL if not currently owned. Since task_struct pointers are aligned
  31 at at least L1_CACHE_BYTES, low bits (3) are used to store extra state (e.g.,
  32 if waiter list is non-empty).  In its most basic form it also includes a
  33 wait-queue and a spinlock that serializes access to it. Furthermore,
  34 CONFIG_MUTEX_SPIN_ON_OWNER=y systems use a spinner MCS lock (->osq), described
  35 below in (ii).
  36
  37 When acquiring a mutex, there are three possible paths that can be
  38 taken, depending on the state of the lock:
  39
  40 (i) fastpath: tries to atomically acquire the lock by cmpxchg()ing the owner with
  41     the current task. This only works in the uncontended case (cmpxchg() checks
  42     against 0UL, so all 3 state bits above have to be 0). If the lock is
  43     contended it goes to the next possible path.
  44
  45 (ii) midpath: aka optimistic spinning, tries to spin for acquisition
  46      while the lock owner is running and there are no other tasks ready
  47      to run that have higher priority (need_resched). The rationale is
  48      that if the lock owner is running, it is likely to release the lock
  49      soon. The mutex spinners are queued up using MCS lock so that only
  50      one spinner can compete for the mutex.
  51
  52      The MCS lock (proposed by Mellor-Crummey and Scott) is a simple spinlock
  53      with the desirable properties of being fair and with each cpu trying
  54      to acquire the lock spinning on a local variable. It avoids expensive
  55      cacheline bouncing that common test-and-set spinlock implementations
  56      incur. An MCS-like lock is specially tailored for optimistic spinning
  57      for sleeping lock implementation. An important feature of the customized
  58      MCS lock is that it has the extra property that spinners are able to exit
  59      the MCS spinlock queue when they need to reschedule. This further helps
  60      avoid situations where MCS spinners that need to reschedule would continue
  61      waiting to spin on mutex owner, only to go directly to slowpath upon
  62      obtaining the MCS lock.
  63
  64
  65 (iii) slowpath: last resort, if the lock is still unable to be acquired,
  66       the task is added to the wait-queue and sleeps until woken up by the
  67       unlock path. Under normal circumstances it blocks as TASK_UNINTERRUPTIBLE.
  68
  69 While formally kernel mutexes are sleepable locks, it is path (ii) that
  70 makes them more practically a hybrid type. By simply not interrupting a
  71 task and busy-waiting for a few cycles instead of immediately sleeping,
  72 the performance of this lock has been seen to significantly improve a
  73 number of workloads. Note that this technique is also used for rw-semaphores.
  74
  75 Semantics
  76 ---------
  77
  78 The mutex subsystem checks and enforces the following rules:
  79
  80     - Only one task can hold the mutex at a time.
  81     - Only the owner can unlock the mutex.
  82     - Multiple unlocks are not permitted.
  83     - Recursive locking/unlocking is not permitted.
  84     - A mutex must only be initialized via the API (see below).
  85     - A task may not exit with a mutex held.
  86     - Memory areas where held locks reside must not be freed.
  87     - Held mutexes must not be reinitialized.
  88     - Mutexes may not be used in hardware or software interrupt
  89       contexts such as tasklets and timers.
  90
  91 These semantics are fully enforced when CONFIG DEBUG_MUTEXES is enabled.
  92 In addition, the mutex debugging code also implements a number of other
  93 features that make lock debugging easier and faster:
  94
  95     - Uses symbolic names of mutexes, whenever they are printed
  96       in debug output.
  97     - Point-of-acquire tracking, symbolic lookup of function names,
  98       list of all locks held in the system, printout of them.
  99     - Owner tracking.
 100     - Detects self-recursing locks and prints out all relevant info.
 101     - Detects multi-task circular deadlocks and prints out all affected
 102       locks and tasks (and only those tasks).
 103
 104
 105 Interfaces
 106 ----------
 107 Statically define the mutex::
 108
 109    DEFINE_MUTEX(name);
 110
 111 Dynamically initialize the mutex::
 112
 113    mutex_init(mutex);
 114
 115 Acquire the mutex, uninterruptible::
 116
 117    void mutex_lock(struct mutex *lock);
 118    void mutex_lock_nested(struct mutex *lock, unsigned int subclass);
 119    int  mutex_trylock(struct mutex *lock);
 120
 121 Acquire the mutex, interruptible::
 122
 123    int mutex_lock_interruptible_nested(struct mutex *lock,
 124                                        unsigned int subclass);
 125    int mutex_lock_interruptible(struct mutex *lock);
 126
 127 Acquire the mutex, interruptible, if dec to 0::
 128
 129    int atomic_dec_and_mutex_lock(atomic_t *cnt, struct mutex *lock);
 130
 131 Unlock the mutex::
 132
 133    void mutex_unlock(struct mutex *lock);
 134
 135 Test if the mutex is taken::
 136
 137    int mutex_is_locked(struct mutex *lock);
 138
 139 Disadvantages
 140 -------------
 141
 142 Unlike its original design and purpose, 'struct mutex' is among the largest
 143 locks in the kernel. E.g: on x86-64 it is 32 bytes, where 'struct semaphore'
 144 is 24 bytes and rw_semaphore is 40 bytes. Larger structure sizes mean more CPU
 145 cache and memory footprint.
 146
 147 When to use mutexes
 148 -------------------
 149
 150 Unless the strict semantics of mutexes are unsuitable and/or the critical
 151 region prevents the lock from being shared, always prefer them to any other
 152 locking primitive.