13 files changed, 737 insertions, 150 deletions
diff --git a/Documentation/mutex-design.txt b/Documentation/mutex-design.txt
index 1dfe62c3641d..ee231ed09ec6 100644
--- a/Documentation/mutex-design.txt
+++ b/Documentation/mutex-design.txt
@@ -1,139 +1,157 @@
 Generic Mutex Subsystem
 started by Ingo Molnar <mingo@redhat.com>
+updated by Davidlohr Bueso <davidlohr@hp.com>
-  "Why on earth do we need a new mutex subsystem, and what's wrong
+What are mutexes?
-   with semaphores?"
+-----------------
-firstly, there's nothing wrong with semaphores. But if the simpler
+In the Linux kernel, mutexes refer to a particular locking primitive
-mutex semantics are sufficient for your code, then there are a couple
+that enforces serialization on shared memory systems, and not only to
-of advantages of mutexes:
+the generic term referring to 'mutual exclusion' found in academia
+or similar theoretical text books. Mutexes are sleeping locks which
+behave similarly to binary semaphores, and were introduced in 2006[1]
+as an alternative to these. This new data structure provided a number
+of advantages, including simpler interfaces, and at that time smaller
+code (see Disadvantages).
- - 'struct mutex' is smaller on most architectures: E.g. on x86,
+[1] http://lwn.net/Articles/164802/
-   'struct semaphore' is 20 bytes, 'struct mutex' is 16 bytes.
-   A smaller structure size means less RAM footprint, and better
-   CPU-cache utilization.
- - tighter code. On x86 i get the following .text sizes when
+Implementation
-   switching all mutex-alike semaphores in the kernel to the mutex
+--------------
-   subsystem:
-        text    data     bss     dec     hex filename
+Mutexes are represented by 'struct mutex', defined in include/linux/mutex.h
-     3280380  868188  396860 4545428  455b94 vmlinux-semaphore
+and implemented in kernel/locking/mutex.c. These locks use a three
-     3255329  865296  396732 4517357  44eded vmlinux-mutex
+state atomic counter (->count) to represent the different possible
+transitions that can occur during the lifetime of a lock:
-   that's 25051 bytes of code saved, or a 0.76% win - off the hottest
+          1: unlocked
-   codepaths of the kernel. (The .data savings are 2892 bytes, or 0.33%)
+          0: locked, no waiters
-   Smaller code means better icache footprint, which is one of the
+   negative: locked, with potential waiters
-   major optimization goals in the Linux kernel currently.
- - the mutex subsystem is slightly faster and has better scalability for
+In its most basic form it also includes a wait-queue and a spinlock
-   contended workloads. On an 8-way x86 system, running a mutex-based
+that serializes access to it. CONFIG_SMP systems can also include
-   kernel and testing creat+unlink+close (of separate, per-task files)
+a pointer to the lock task owner (->owner) as well as a spinner MCS
-   in /tmp with 16 parallel tasks, the average number of ops/sec is:
+lock (->osq), both described below in (ii).
-    Semaphores:                        Mutexes:
+When acquiring a mutex, there are three possible paths that can be
+taken, depending on the state of the lock:
-    $ ./test-mutex V 16 10             $ ./test-mutex V 16 10
+(i) fastpath: tries to atomically acquire the lock by decrementing the
-    8 CPUs, running 16 tasks.          8 CPUs, running 16 tasks.
+    counter. If it was already taken by another task it goes to the next
-    checking VFS performance.          checking VFS performance.
+    possible path. This logic is architecture specific. On x86-64, the
-    avg loops/sec:      34713          avg loops/sec:      84153
+    locking fastpath is 2 instructions:
-    CPU utilization:    63%            CPU utilization:    22%
-   i.e. in this workload, the mutex based kernel was 2.4 times faster
+    0000000000000e10 <mutex_lock>:
-   than the semaphore based kernel, _and_ it also had 2.8 times less CPU
+    e21:   f0 ff 0b                lock decl (%rbx)
-   utilization. (In terms of 'ops per CPU cycle', the semaphore kernel
+    e24:   79 08                   jns    e2e <mutex_lock+0x1e>
-   performed 551 ops/sec per 1% of CPU time used, while the mutex kernel
-   performed 3825 ops/sec per 1% of CPU time used - it was 6.9 times
-   more efficient.)
-   the scalability difference is visible even on a 2-way P4 HT box:
-    Semaphores:                        Mutexes:
-    $ ./test-mutex V 16 10             $ ./test-mutex V 16 10
-    4 CPUs, running 16 tasks.          8 CPUs, running 16 tasks.
-    checking VFS performance.          checking VFS performance.
-    avg loops/sec:      127659         avg loops/sec:      181082
-    CPU utilization:    100%           CPU utilization:    34%
-   (the straight performance advantage of mutexes is 41%, the per-cycle
-    efficiency of mutexes is 4.1 times better.)
- - there are no fastpath tradeoffs, the mutex fastpath is just as tight
-   as the semaphore fastpath. On x86, the locking fastpath is 2
-   instructions:
-    c0377ccb <mutex_lock>:
-    c0377ccb:       f0 ff 08                lock decl (%eax)
-    c0377cce:       78 0e                   js     c0377cde <.text..lock.mutex>
-    c0377cd0:       c3                      ret
   the unlocking fastpath is equally tight:
-    c0377cd1 <mutex_unlock>:
+    0000000000000bc0 <mutex_unlock>:
-    c0377cd1:       f0 ff 00                lock incl (%eax)
+    bc8:   f0 ff 07                lock incl (%rdi)
-    c0377cd4:       7e 0f                   jle    c0377ce5 <.text..lock.mutex+0x7>
+    bcb:   7f 0a                   jg     bd7 <mutex_unlock+0x17>
-    c0377cd6:       c3                      ret
- - 'struct mutex' semantics are well-defined and are enforced if
+(ii) midpath: aka optimistic spinning, tries to spin for acquisition
-   CONFIG_DEBUG_MUTEXES is turned on. Semaphores on the other hand have
+     while the lock owner is running and there are no other tasks ready
-   virtually no debugging code or instrumentation. The mutex subsystem
+     to run that have higher priority (need_resched). The rationale is
-   checks and enforces the following rules:
+     that if the lock owner is running, it is likely to release the lock
+     soon. The mutex spinners are queued up using MCS lock so that only
-   * - only one task can hold the mutex at a time
+     one spinner can compete for the mutex.
-   * - only the owner can unlock the mutex
-   * - multiple unlocks are not permitted
+     The MCS lock (proposed by Mellor-Crummey and Scott) is a simple spinlock
-   * - recursive locking is not permitted
+     with the desirable properties of being fair and with each cpu trying
-   * - a mutex object must be initialized via the API
+     to acquire the lock spinning on a local variable. It avoids expensive
-   * - a mutex object must not be initialized via memset or copying
+     cacheline bouncing that common test-and-set spinlock implementations
-   * - task may not exit with mutex held
+     incur. An MCS-like lock is specially tailored for optimistic spinning
-   * - memory areas where held locks reside must not be freed
+     for sleeping lock implementation. An important feature of the customized
-   * - held mutexes must not be reinitialized
+     MCS lock is that it has the extra property that spinners are able to exit
-   * - mutexes may not be used in hardware or software interrupt
+     the MCS spinlock queue when they need to reschedule. This further helps
-   *   contexts such as tasklets and timers
+     avoid situations where MCS spinners that need to reschedule would continue
+     waiting to spin on mutex owner, only to go directly to slowpath upon
-   furthermore, there are also convenience features in the debugging
+     obtaining the MCS lock.
-   code:
-   * - uses symbolic names of mutexes, whenever they are printed in debug output
+(iii) slowpath: last resort, if the lock is still unable to be acquired,
-   * - point-of-acquire tracking, symbolic lookup of function names
+      the task is added to the wait-queue and sleeps until woken up by the
-   * - list of all locks held in the system, printout of them
+      unlock path. Under normal circumstances it blocks as TASK_UNINTERRUPTIBLE.
-   * - owner tracking
-   * - detects self-recursing locks and prints out all relevant info
+While formally kernel mutexes are sleepable locks, it is path (ii) that
-   * - detects multi-task circular deadlocks and prints out all affected
+makes them more practically a hybrid type. By simply not interrupting a
-   *   locks and tasks (and only those tasks)
+task and busy-waiting for a few cycles instead of immediately sleeping,

diff --git a/Documentation/mutex-design.txt b/Documentation/mutex-design.txt index 1dfe62c3641d..ee231ed09ec6 100644 --- a/Documentation/mutex-design.txt +++ b/Documentation/mutex-design.txt
@@ -1,139 +1,157 @@
1	Generic Mutex Subsystem	1	Generic Mutex Subsystem
2		2
3	started by Ingo Molnar <mingo@redhat.com>	3	started by Ingo Molnar <mingo@redhat.com>
		4	updated by Davidlohr Bueso <davidlohr@hp.com>
4		5
5	"Why on earth do we need a new mutex subsystem, and what's wrong	6	What are mutexes?
6	with semaphores?"	7	-----------------
7		8
8	firstly, there's nothing wrong with semaphores. But if the simpler	9	In the Linux kernel, mutexes refer to a particular locking primitive
9	mutex semantics are sufficient for your code, then there are a couple	10	that enforces serialization on shared memory systems, and not only to
10	of advantages of mutexes:	11	the generic term referring to 'mutual exclusion' found in academia
		12	or similar theoretical text books. Mutexes are sleeping locks which
		13	behave similarly to binary semaphores, and were introduced in 2006[1]
		14	as an alternative to these. This new data structure provided a number
		15	of advantages, including simpler interfaces, and at that time smaller
		16	code (see Disadvantages).
11		17
12	- 'struct mutex' is smaller on most architectures: E.g. on x86,	18	[1] http://lwn.net/Articles/164802/
13	'struct semaphore' is 20 bytes, 'struct mutex' is 16 bytes.
14	A smaller structure size means less RAM footprint, and better
15	CPU-cache utilization.
16		19
17	- tighter code. On x86 i get the following .text sizes when	20	Implementation
18	switching all mutex-alike semaphores in the kernel to the mutex	21	--------------
19	subsystem:
20		22
21	text data bss dec hex filename	23	Mutexes are represented by 'struct mutex', defined in include/linux/mutex.h
22	3280380 868188 396860 4545428 455b94 vmlinux-semaphore	24	and implemented in kernel/locking/mutex.c. These locks use a three
23	3255329 865296 396732 4517357 44eded vmlinux-mutex	25	state atomic counter (->count) to represent the different possible
		26	transitions that can occur during the lifetime of a lock:
24		27
25	that's 25051 bytes of code saved, or a 0.76% win - off the hottest	28	1: unlocked
26	codepaths of the kernel. (The .data savings are 2892 bytes, or 0.33%)	29	0: locked, no waiters
27	Smaller code means better icache footprint, which is one of the	30	negative: locked, with potential waiters
28	major optimization goals in the Linux kernel currently.
29		31
30	- the mutex subsystem is slightly faster and has better scalability for	32	In its most basic form it also includes a wait-queue and a spinlock
31	contended workloads. On an 8-way x86 system, running a mutex-based	33	that serializes access to it. CONFIG_SMP systems can also include
32	kernel and testing creat+unlink+close (of separate, per-task files)	34	a pointer to the lock task owner (->owner) as well as a spinner MCS
33	in /tmp with 16 parallel tasks, the average number of ops/sec is:	35	lock (->osq), both described below in (ii).
34		36
35	Semaphores: Mutexes:	37	When acquiring a mutex, there are three possible paths that can be
		38	taken, depending on the state of the lock:
36		39
37	$ ./test-mutex V 16 10 $ ./test-mutex V 16 10	40	(i) fastpath: tries to atomically acquire the lock by decrementing the
38	8 CPUs, running 16 tasks. 8 CPUs, running 16 tasks.	41	counter. If it was already taken by another task it goes to the next
39	checking VFS performance. checking VFS performance.	42	possible path. This logic is architecture specific. On x86-64, the
40	avg loops/sec: 34713 avg loops/sec: 84153	43	locking fastpath is 2 instructions:
41	CPU utilization: 63% CPU utilization: 22%
42		44
43	i.e. in this workload, the mutex based kernel was 2.4 times faster	45	0000000000000e10 <mutex_lock>:
44	than the semaphore based kernel, _and_ it also had 2.8 times less CPU	46	e21: f0 ff 0b lock decl (%rbx)
45	utilization. (In terms of 'ops per CPU cycle', the semaphore kernel	47	e24: 79 08 jns e2e <mutex_lock+0x1e>
46	performed 551 ops/sec per 1% of CPU time used, while the mutex kernel
47	performed 3825 ops/sec per 1% of CPU time used - it was 6.9 times
48	more efficient.)
49
50	the scalability difference is visible even on a 2-way P4 HT box:
51
52	Semaphores: Mutexes:
53
54	$ ./test-mutex V 16 10 $ ./test-mutex V 16 10
55	4 CPUs, running 16 tasks. 8 CPUs, running 16 tasks.
56	checking VFS performance. checking VFS performance.
57	avg loops/sec: 127659 avg loops/sec: 181082
58	CPU utilization: 100% CPU utilization: 34%
59
60	(the straight performance advantage of mutexes is 41%, the per-cycle
61	efficiency of mutexes is 4.1 times better.)
62
63	- there are no fastpath tradeoffs, the mutex fastpath is just as tight
64	as the semaphore fastpath. On x86, the locking fastpath is 2
65	instructions:
66
67	c0377ccb <mutex_lock>:
68	c0377ccb: f0 ff 08 lock decl (%eax)
69	c0377cce: 78 0e js c0377cde <.text..lock.mutex>
70	c0377cd0: c3 ret
71		48
72	the unlocking fastpath is equally tight:	49	the unlocking fastpath is equally tight:
73		50
74	c0377cd1 <mutex_unlock>:	51	0000000000000bc0 <mutex_unlock>:
75	c0377cd1: f0 ff 00 lock incl (%eax)	52	bc8: f0 ff 07 lock incl (%rdi)
76	c0377cd4: 7e 0f jle c0377ce5 <.text..lock.mutex+0x7>	53	bcb: 7f 0a jg bd7 <mutex_unlock+0x17>
77	c0377cd6: c3 ret	54
78		55
79	- 'struct mutex' semantics are well-defined and are enforced if	56	(ii) midpath: aka optimistic spinning, tries to spin for acquisition
80	CONFIG_DEBUG_MUTEXES is turned on. Semaphores on the other hand have	57	while the lock owner is running and there are no other tasks ready
81	virtually no debugging code or instrumentation. The mutex subsystem	58	to run that have higher priority (need_resched). The rationale is
82	checks and enforces the following rules:	59	that if the lock owner is running, it is likely to release the lock
83		60	soon. The mutex spinners are queued up using MCS lock so that only
84	* - only one task can hold the mutex at a time	61	one spinner can compete for the mutex.
85	* - only the owner can unlock the mutex	62
86	* - multiple unlocks are not permitted	63	The MCS lock (proposed by Mellor-Crummey and Scott) is a simple spinlock
87	* - recursive locking is not permitted	64	with the desirable properties of being fair and with each cpu trying
88	* - a mutex object must be initialized via the API	65	to acquire the lock spinning on a local variable. It avoids expensive
89	* - a mutex object must not be initialized via memset or copying	66	cacheline bouncing that common test-and-set spinlock implementations
90	* - task may not exit with mutex held	67	incur. An MCS-like lock is specially tailored for optimistic spinning
91	* - memory areas where held locks reside must not be freed	68	for sleeping lock implementation. An important feature of the customized
92	* - held mutexes must not be reinitialized	69	MCS lock is that it has the extra property that spinners are able to exit
93	* - mutexes may not be used in hardware or software interrupt	70	the MCS spinlock queue when they need to reschedule. This further helps
94	* contexts such as tasklets and timers	71	avoid situations where MCS spinners that need to reschedule would continue
95		72	waiting to spin on mutex owner, only to go directly to slowpath upon
96	furthermore, there are also convenience features in the debugging	73	obtaining the MCS lock.
97	code:	74
98		75
99	* - uses symbolic names of mutexes, whenever they are printed in debug output	76	(iii) slowpath: last resort, if the lock is still unable to be acquired,
100	* - point-of-acquire tracking, symbolic lookup of function names	77	the task is added to the wait-queue and sleeps until woken up by the
101	* - list of all locks held in the system, printout of them	78	unlock path. Under normal circumstances it blocks as TASK_UNINTERRUPTIBLE.
102	* - owner tracking	79
103	* - detects self-recursing locks and prints out all relevant info	80	While formally kernel mutexes are sleepable locks, it is path (ii) that
104	* - detects multi-task circular deadlocks and prints out all affected	81	makes them more practically a hybrid type. By simply not interrupting a
105	* locks and tasks (and only those tasks)	82	task and busy-waiting for a few cycles instead of immediately sleeping,