Commit | Line | Data |
---|---|---|
387b1468 | 1 | ======================= |
f3f54ffa | 2 | Generic Mutex Subsystem |
387b1468 | 3 | ======================= |
f3f54ffa IM |
4 | |
5 | started by Ingo Molnar <mingo@redhat.com> | |
387b1468 | 6 | |
9161f540 | 7 | updated by Davidlohr Bueso <davidlohr@hp.com> |
f3f54ffa | 8 | |
9161f540 DB |
9 | What are mutexes? |
10 | ----------------- | |
f3f54ffa | 11 | |
9161f540 DB |
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). | |
f3f54ffa | 20 | |
9161f540 | 21 | [1] http://lwn.net/Articles/164802/ |
f3f54ffa | 22 | |
9161f540 DB |
23 | Implementation |
24 | -------------- | |
f3f54ffa | 25 | |
9161f540 | 26 | Mutexes are represented by 'struct mutex', defined in include/linux/mutex.h |
79e90238 JL |
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 | |
387b1468 | 29 | actually contains `struct task_struct *` to the current lock owner and it is |
79e90238 JL |
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). | |
f3f54ffa | 36 | |
9161f540 DB |
37 | When acquiring a mutex, there are three possible paths that can be |
38 | taken, depending on the state of the lock: | |
f3f54ffa | 39 | |
79e90238 JL |
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. | |
9161f540 DB |
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 | ---------- | |
387b1468 MCC |
107 | Statically define the mutex:: |
108 | ||
9161f540 DB |
109 | DEFINE_MUTEX(name); |
110 | ||
387b1468 MCC |
111 | Dynamically initialize the mutex:: |
112 | ||
9161f540 DB |
113 | mutex_init(mutex); |
114 | ||
387b1468 MCC |
115 | Acquire the mutex, uninterruptible:: |
116 | ||
9161f540 DB |
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 | ||
387b1468 MCC |
121 | Acquire the mutex, interruptible:: |
122 | ||
9161f540 DB |
123 | int mutex_lock_interruptible_nested(struct mutex *lock, |
124 | unsigned int subclass); | |
125 | int mutex_lock_interruptible(struct mutex *lock); | |
126 | ||
387b1468 MCC |
127 | Acquire the mutex, interruptible, if dec to 0:: |
128 | ||
9161f540 DB |
129 | int atomic_dec_and_mutex_lock(atomic_t *cnt, struct mutex *lock); |
130 | ||
387b1468 MCC |
131 | Unlock the mutex:: |
132 | ||
9161f540 DB |
133 | void mutex_unlock(struct mutex *lock); |
134 | ||
387b1468 MCC |
135 | Test if the mutex is taken:: |
136 | ||
9161f540 | 137 | int mutex_is_locked(struct mutex *lock); |
f3f54ffa IM |
138 | |
139 | Disadvantages | |
140 | ------------- | |
141 | ||
79e90238 JL |
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. | |
f3f54ffa | 146 | |
9161f540 DB |
147 | When to use mutexes |
148 | ------------------- | |
f3f54ffa | 149 | |
9161f540 DB |
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. |