Documentation/locking/mutex-design.rst

Source file repositories/reference/linux-study-clean/Documentation/locking/mutex-design.rst

File Facts

System
Linux kernel
Corpus path
Documentation/locking/mutex-design.rst
Extension
.rst
Size
7019 bytes
Lines
171
Domain
Support Tooling And Documentation
Bucket
Documentation
Inferred role
Support Tooling And Documentation: documentation
Status
atlas-only

Why This File Exists

Repository support layer: documentation, build tooling, samples, user-space helper tools, generated initramfs support, licenses, and validation utilities.

Dependency Surface

Detected Declarations

Annotated Snippet

=======================
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

Annotation

Implementation Notes