Documentation/locking/mutex-design.rst - linux - Git at Google

 =======================
 Generic Mutex Subsystem
 =======================

 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 primitive
 that enforces serialization on shared memory systems, and not only to
 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).

 [1] https://lwn.net/Articles/164802/

 Implementation
 --------------

 Mutexes are represented by 'struct mutex', defined in include/linux/mutex.h
 and implemented in kernel/locking/mutex.c. These locks use an atomic variable
 (->owner) to keep track of the lock state during its lifetime.  Field owner
 actually contains `struct task_struct *` to the current lock owner and it is
 therefore NULL if not currently owned. Since task_struct pointers are aligned
 to 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 a
 wait-queue and a spinlock that serializes access to it. Furthermore,
 CONFIG_MUTEX_SPIN_ON_OWNER=y systems use a spinner MCS lock (->osq), described
 below in (ii).

 When acquiring a mutex, there are three possible paths that can be
 taken, depending on the state of the lock:

 (i) fastpath: tries to atomically acquire the lock by cmpxchg()ing the owner with
     the current task. This only works in the uncontended case (cmpxchg() checks
     against 0UL, so all 3 state bits above have to be 0). If the lock is
     contended it goes to the next possible path.

 (ii) midpath: aka optimistic spinning, tries to spin for acquisition
      while the lock owner is running and there are no other tasks ready
      to run that have higher priority (need_resched). The rationale is
      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
      one spinner can compete for the mutex.

      The MCS lock (proposed by Mellor-Crummey and Scott) is a simple spinlock
      with the desirable properties of being fair and with each cpu trying
      to acquire the lock spinning on a local variable. It avoids expensive
      cacheline bouncing that common test-and-set spinlock implementations
      incur. An MCS-like lock is specially tailored for optimistic spinning
      for sleeping lock implementation. An important feature of the customized
      MCS lock is that it has the extra property that spinners are able to exit
      the MCS spinlock queue when they need to reschedule. This further helps
      avoid situations where MCS spinners that need to reschedule would continue
      waiting to spin on mutex owner, only to go directly to slowpath upon
      obtaining the MCS lock.


 (iii) 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 the
       unlock path. Under normal circumstances it blocks as TASK_UNINTERRUPTIBLE.

 While formally kernel mutexes are sleepable locks, it is path (ii) that
 makes them more practically a hybrid type. By simply not interrupting a
 task and busy-waiting for a few cycles instead of immediately sleeping,
 the performance of this lock has been seen to significantly improve a
 number 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 interrupt
       contexts 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 other
 features that make lock debugging easier and faster:

     - Uses symbolic names of mutexes, whenever they are printed
       in 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 affected
       locks and tasks (and only those tasks).

 Mutexes - and most other sleeping locks like rwsems - do not provide an
 implicit reference for the memory they occupy, which reference is released
 with mutex_unlock().

 [ This is in contrast with spin_unlock() [or completion_done()], which
   APIs can be used to guarantee that the memory is not touched by the
   lock implementation after spin_unlock()/completion_done() releases
   the lock. ]

 mutex_unlock() may access the mutex structure even after it has internally
 released the lock already - so it's not safe for another context to
 acquire the mutex and assume that the mutex_unlock() context is not using
 the structure anymore.

 The mutex user must ensure that the mutex is not destroyed while a
 release operation is still in progress - in other words, callers of
 mutex_unlock() must ensure that the mutex stays alive until mutex_unlock()
 has returned.

 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 largest
 locks 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 CPU
 cache and memory footprint.

 When to use mutexes
 -------------------

 Unless the strict semantics of mutexes are unsuitable and/or the critical
 region prevents the lock from being shared, always prefer them to any other
 locking primitive.
	=======================
	Generic Mutex Subsystem
	=======================

	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 primitive
	that enforces serialization on shared memory systems, and not only to
	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).

	[1] https://lwn.net/Articles/164802/

	Implementation
	--------------

	Mutexes are represented by 'struct mutex', defined in include/linux/mutex.h
	and implemented in kernel/locking/mutex.c. These locks use an atomic variable
	(->owner) to keep track of the lock state during its lifetime. Field owner
	actually contains `struct task_struct *` to the current lock owner and it is
	therefore NULL if not currently owned. Since task_struct pointers are aligned
	to 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 a
	wait-queue and a spinlock that serializes access to it. Furthermore,
	CONFIG_MUTEX_SPIN_ON_OWNER=y systems use a spinner MCS lock (->osq), described
	below in (ii).

	When acquiring a mutex, there are three possible paths that can be
	taken, depending on the state of the lock:

	(i) fastpath: tries to atomically acquire the lock by cmpxchg()ing the owner with
	the current task. This only works in the uncontended case (cmpxchg() checks
	against 0UL, so all 3 state bits above have to be 0). If the lock is
	contended it goes to the next possible path.

	(ii) midpath: aka optimistic spinning, tries to spin for acquisition
	while the lock owner is running and there are no other tasks ready
	to run that have higher priority (need_resched). The rationale is
	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
	one spinner can compete for the mutex.

	The MCS lock (proposed by Mellor-Crummey and Scott) is a simple spinlock
	with the desirable properties of being fair and with each cpu trying
	to acquire the lock spinning on a local variable. It avoids expensive
	cacheline bouncing that common test-and-set spinlock implementations
	incur. An MCS-like lock is specially tailored for optimistic spinning
	for sleeping lock implementation. An important feature of the customized
	MCS lock is that it has the extra property that spinners are able to exit
	the MCS spinlock queue when they need to reschedule. This further helps
	avoid situations where MCS spinners that need to reschedule would continue
	waiting to spin on mutex owner, only to go directly to slowpath upon
	obtaining the MCS lock.


	(iii) 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 the
	unlock path. Under normal circumstances it blocks as TASK_UNINTERRUPTIBLE.

	While formally kernel mutexes are sleepable locks, it is path (ii) that
	makes them more practically a hybrid type. By simply not interrupting a
	task and busy-waiting for a few cycles instead of immediately sleeping,
	the performance of this lock has been seen to significantly improve a
	number 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 interrupt
	contexts 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 other
	features that make lock debugging easier and faster:

	- Uses symbolic names of mutexes, whenever they are printed
	in 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 affected
	locks and tasks (and only those tasks).

	Mutexes - and most other sleeping locks like rwsems - do not provide an
	implicit reference for the memory they occupy, which reference is released
	with mutex_unlock().

	[ This is in contrast with spin_unlock() [or completion_done()], which
	APIs can be used to guarantee that the memory is not touched by the
	lock implementation after spin_unlock()/completion_done() releases
	the lock. ]

	mutex_unlock() may access the mutex structure even after it has internally
	released the lock already - so it's not safe for another context to
	acquire the mutex and assume that the mutex_unlock() context is not using
	the structure anymore.

	The mutex user must ensure that the mutex is not destroyed while a
	release operation is still in progress - in other words, callers of
	mutex_unlock() must ensure that the mutex stays alive until mutex_unlock()
	has returned.

	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 largest
	locks 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 CPU
	cache and memory footprint.

	When to use mutexes
	-------------------

	Unless the strict semantics of mutexes are unsuitable and/or the critical
	region prevents the lock from being shared, always prefer them to any other
	locking primitive.