code:
Runtime locking correctness validator
=====================================

started by Ingo Molnar <mingo@redhat.com>

additions by Arjan van de Ven <arjan@linux.intel.com>

Lock-class
----------

The basic object the validator operates upon is a 'class' of locks.

A class of locks is a group of locks that are logically the same with
respect to locking rules, even if the locks may have multiple (possibly
tens of thousands of) instantiations. For example a lock in the inode
struct is one class, while each inode has its own instantiation of that
lock class.

The validator tracks the 'usage state' of lock-classes, and it tracks
the dependencies between different lock-classes. Lock usage indicates
how a lock is used with regard to its IRQ contexts, while lock
dependency can be understood as lock order, where L1 -> L2 suggests that
a task is attempting to acquire L2 while holding L1. From lockdep's
perspective, the two locks (L1 and L2) are not necessarily related; that
dependency just means the order ever happened. The validator maintains a
continuing effort to prove lock usages and dependencies are correct or
the validator will shoot a splat if incorrect.

A lock-class's behavior is constructed by its instances collectively:
when the first instance of a lock-class is used after bootup the class
gets registered, then all (subsequent) instances will be mapped to the
class and hence their usages and dependecies will contribute to those of
the class. A lock-class does not go away when a lock instance does, but
it can be removed if the memory space of the lock class (static or
dynamic) is reclaimed, this happens for example when a module is
unloaded or a workqueue is destroyed.

State
-----

The validator tracks lock-class usage history and divides the usage into
(4 usages * n STATEs + 1) categories:

where the 4 usages can be:

- 'ever held in STATE context'
- 'ever held as readlock in STATE context'
- 'ever held with STATE enabled'
- 'ever held as readlock with STATE enabled'

where the n STATEs are coded in kernel/locking/lockdep_states.h and as of
now they include:

- hardirq
- softirq

where the last 1 category is:

- 'ever used'                                       [ == !unused        ]

When locking rules are violated, these usage bits are presented in the
locking error messages, inside curlies, with a total of 2 * n STATEs bits.
A contrived example::

   modprobe/2287 is trying to acquire lock:
    (&sio_locks[i].lock){-.-.}, at: [<c02867fd>] mutex_lock+0x21/0x24

   but task is already holding lock:
    (&sio_locks[i].lock){-.-.}, at: [<c02867fd>] mutex_lock+0x21/0x24

For a given lock, the bit positions from left to right indicate the usage
of the lock and readlock (if exists), for each of the n STATEs listed
above respectively, and the character displayed at each bit position
indicates:

   ===  ===================================================
   '.'  acquired while irqs disabled and not in irq context
   '-'  acquired in irq context
   '+'  acquired with irqs enabled
   '?'  acquired in irq context with irqs enabled.
   ===  ===================================================

The bits are illustrated with an example::

    (&sio_locks[i].lock){-.-.}, at: [<c02867fd>] mutex_lock+0x21/0x24
                         ||||
                         ||| \-> softirq disabled and not in softirq context
                         || \--> acquired in softirq context
                         | \---> hardirq disabled and not in hardirq context
                          \----> acquired in hardirq context

For a given STATE, whether the lock is ever acquired in that STATE
context and whether that STATE is enabled yields four possible cases as
shown in the table below. The bit character is able to indicate which
exact case is for the lock as of the reporting time.

  +--------------+-------------+--------------+
  |              | irq enabled | irq disabled |
  +--------------+-------------+--------------+
  | ever in irq  |     '?'     |      '-'     |
  +--------------+-------------+--------------+
  | never in irq |     '+'     |      '.'     |
  +--------------+-------------+--------------+

The character '-' suggests irq is disabled because if otherwise the
charactor '?' would have been shown instead. Similar deduction can be
applied for '+' too.

Unused locks (e.g., mutexes) cannot be part of the cause of an error.

Single-lock state rules:
------------------------

A lock is irq-safe means it was ever used in an irq context, while a lock
is irq-unsafe means it was ever acquired with irq enabled.

A softirq-unsafe lock-class is automatically hardirq-unsafe as well. The
following states must be exclusive: only one of them is allowed to be set
for any lock-class based on its usage::

 <hardirq-safe> or <hardirq-unsafe>
 <softirq-safe> or <softirq-unsafe>

This is because if a lock can be used in irq context (irq-safe) then it
cannot be ever acquired with irq enabled (irq-unsafe). Otherwise, a
deadlock may happen. For example, in the scenario that after this lock
was acquired but before released, if the context is interrupted this
lock will be attempted to acquire twice, which creates a deadlock,
referred to as lock recursion deadlock.

The validator detects and reports lock usage that violates these
single-lock state rules.

Multi-lock dependency rules:
----------------------------

The same lock-class must not be acquired twice, because this could lead
to lock recursion deadlocks.

Furthermore, two locks can not be taken in inverse order::

 <L1> -> <L2>
 <L2> -> <L1>

because this could lead to a deadlock - referred to as lock inversion
deadlock - as attempts to acquire the two locks form a circle which
could lead to the two contexts waiting for each other permanently. The
validator will find such dependency circle in arbitrary complexity,
i.e., there can be any other locking sequence between the acquire-lock
operations; the validator will still find whether these locks can be
acquired in a circular fashion.

Furthermore, the following usage based lock dependencies are not allowed
between any two lock-classes::

   <hardirq-safe>   ->  <hardirq-unsafe>
   <softirq-safe>   ->  <softirq-unsafe>

The first rule comes from the fact that a hardirq-safe lock could be
taken by a hardirq context, interrupting a hardirq-unsafe lock - and
thus could result in a lock inversion deadlock. Likewise, a softirq-safe
lock could be taken by an softirq context, interrupting a softirq-unsafe
lock.

The above rules are enforced for any locking sequence that occurs in the
kernel: when acquiring a new lock, the validator checks whether there is
any rule violation between the new lock and any of the held locks.

When a lock-class changes its state, the following aspects of the above
dependency rules are enforced:

- if a new hardirq-safe lock is discovered, we check whether it
  took any hardirq-unsafe lock in the past.

- if a new softirq-safe lock is discovered, we check whether it took
  any softirq-unsafe lock in the past.

- if a new hardirq-unsafe lock is discovered, we check whether any
  hardirq-safe lock took it in the past.

- if a new softirq-unsafe lock is discovered, we check whether any
  softirq-safe lock took it in the past.

(Again, we do these checks too on the basis that an interrupt context
could interrupt _any_ of the irq-unsafe or hardirq-unsafe locks, which
could lead to a lock inversion deadlock - even if that lock scenario did
not trigger in practice yet.)

Exception: Nested data dependencies leading to nested locking
-------------------------------------------------------------

There are a few cases where the Linux kernel acquires more than one
instance of the same lock-class. Such cases typically happen when there
is some sort of hierarchy within objects of the same type. In these
cases there is an inherent "natural" ordering between the two objects
(defined by the properties of the hierarchy), and the kernel grabs the
locks in this fixed order on each of the objects.

An example of such an object hierarchy that results in "nested locking"
is that of a "whole disk" block-dev object and a "partition" block-dev
object; the partition is "part of" the whole device and as long as one
always takes the whole disk lock as a higher lock than the partition
lock, the lock ordering is fully correct. The validator does not
automatically detect this natural ordering, as the locking rule behind
the ordering is not static.

In order to teach the validator about this correct usage model, new
versions of the various locking primitives were added that allow you to
specify a "nesting level". An example call, for the block device mutex,
looks like this::

  enum bdev_bd_mutex_lock_class
  {
       BD_MUTEX_NORMAL,
       BD_MUTEX_WHOLE,
       BD_MUTEX_PARTITION
  };

  mutex_lock_nested(&bdev->bd_contains->bd_mutex, BD_MUTEX_PARTITION);

In this case the locking is done on a bdev object that is known to be a
partition.

The validator treats a lock that is taken in such a nested fashion as a
separate (sub)class for the purposes of validation.

Note: When changing code to use the _nested() primitives, be careful and
check really thoroughly that the hierarchy is correctly mapped; otherwise
you can get false positives or false negatives.

Annotations
-----------

Two constructs can be used to annotate and check where and if certain locks
must be held: lockdep_assert_held*(&lock) and lockdep_*pin_lock(&lock).

As the name suggests, lockdep_assert_held* family of macros assert that a
particular lock is held at a certain time (and generate a WARN() otherwise).
This annotation is largely used all over the kernel, e.g. kernel/sched/
core.c::

  void update_rq_clock(struct rq *rq)
  {
	s64 delta;

	lockdep_assert_held(&rq->lock);
	[...]
  }

where holding rq->lock is required to safely update a rq's clock.

The other family of macros is lockdep_*pin_lock(), which is admittedly only
used for rq->lock ATM. Despite their limited adoption these annotations
generate a WARN() if the lock of interest is "accidentally" unlocked. This turns
out to be especially helpful to debug code with callbacks, where an upper
layer assumes a lock remains taken, but a lower layer thinks it can maybe drop
and reacquire the lock ("unwittingly" introducing races). lockdep_pin_lock()
returns a 'struct pin_cookie' that is then used by lockdep_unpin_lock() to check
that nobody tampered with the lock, e.g. kernel/sched/sched.h::

  static inline void rq_pin_lock(struct rq *rq, struct rq_flags *rf)
  {
	rf->cookie = lockdep_pin_lock(&rq->lock);
	[...]
  }

  static inline void rq_unpin_lock(struct rq *rq, struct rq_flags *rf)
  {
	[...]
	lockdep_unpin_lock(&rq->lock, rf->cookie);
  }

While comments about locking requirements might provide useful information,
the runtime checks performed by annotations are invaluable when debugging
locking problems and they carry the same level of details when inspecting
code.  Always prefer annotations when in doubt!

Proof of 100% correctness:
--------------------------

The validator achieves perfect, mathematical 'closure' (proof of locking
correctness) in the sense that for every simple, standalone single-task
locking sequence that occurred at least once during the lifetime of the
kernel, the validator proves it with a 100% certainty that no
combination and timing of these locking sequences can cause any class of
lock related deadlock. [1]_

I.e. complex multi-CPU and multi-task locking scenarios do not have to
occur in practice to prove a deadlock: only the simple 'component'
locking chains have to occur at least once (anytime, in any
task/context) for the validator to be able to prove correctness. (For
example, complex deadlocks that would normally need more than 3 CPUs and
a very unlikely constellation of tasks, irq-contexts and timings to
occur, can be detected on a plain, lightly loaded single-CPU system as
well!)

This radically decreases the complexity of locking related QA of the
kernel: what has to be done during QA is to trigger as many "simple"
single-task locking dependencies in the kernel as possible, at least
once, to prove locking correctness - instead of having to trigger every
possible combination of locking interaction between CPUs, combined with
every possible hardirq and softirq nesting scenario (which is impossible
to do in practice).

.. [1]

    assuming that the validator itself is 100% correct, and no other
    part of the system corrupts the state of the validator in any way.
    We also assume that all NMI/SMM paths [which could interrupt
    even hardirq-disabled codepaths] are correct and do not interfere
    with the validator. We also assume that the 64-bit 'chain hash'
    value is unique for every lock-chain in the system. Also, lock
    recursion must not be higher than 20.

Performance:
------------

The above rules require **massive** amounts of runtime checking. If we did
that for every lock taken and for every irqs-enable event, it would
render the system practically unusably slow. The complexity of checking
is O(N^2), so even with just a few hundred lock-classes we'd have to do
tens of thousands of checks for every event.

This problem is solved by checking any given 'locking scenario' (unique
sequence of locks taken after each other) only once. A simple stack of
held locks is maintained, and a lightweight 64-bit hash value is
calculated, which hash is unique for every lock chain. The hash value,
when the chain is validated for the first time, is then put into a hash
table, which hash-table can be checked in a lockfree manner. If the
locking chain occurs again later on, the hash table tells us that we
don't have to validate the chain again.

Troubleshooting:
----------------

The validator tracks a maximum of MAX_LOCKDEP_KEYS number of lock classes.
Exceeding this number will trigger the following lockdep warning::

	(DEBUG_LOCKS_WARN_ON(id >= MAX_LOCKDEP_KEYS))

By default, MAX_LOCKDEP_KEYS is currently set to 8191, and typical
desktop systems have less than 1,000 lock classes, so this warning
normally results from lock-class leakage or failure to properly
initialize locks.  These two problems are illustrated below:

1.	Repeated module loading and unloading while running the validator
	will result in lock-class leakage.  The issue here is that each
	load of the module will create a new set of lock classes for
	that module's locks, but module unloading does not remove old
	classes (see below discussion of reuse of lock classes for why).
	Therefore, if that module is loaded and unloaded repeatedly,
	the number of lock classes will eventually reach the maximum.

2.	Using structures such as arrays that have large numbers of
	locks that are not explicitly initialized.  For example,
	a hash table with 8192 buckets where each bucket has its own
	spinlock_t will consume 8192 lock classes -unless- each spinlock
	is explicitly initialized at runtime, for example, using the
	run-time spin_lock_init() as opposed to compile-time initializers
	such as __SPIN_LOCK_UNLOCKED().  Failure to properly initialize
	the per-bucket spinlocks would guarantee lock-class overflow.
	In contrast, a loop that called spin_lock_init() on each lock
	would place all 8192 locks into a single lock class.

	The moral of this story is that you should always explicitly
	initialize your locks.

One might argue that the validator should be modified to allow
lock classes to be reused.  However, if you are tempted to make this
argument, first review the code and think through the changes that would
be required, keeping in mind that the lock classes to be removed are
likely to be linked into the lock-dependency graph.  This turns out to
be harder to do than to say.

Of course, if you do run out of lock classes, the next thing to do is
to find the offending lock classes.  First, the following command gives
you the number of lock classes currently in use along with the maximum::

	grep "lock-classes" /proc/lockdep_stats

This command produces the following output on a modest system::

	lock-classes:                          748 [max: 8191]

If the number allocated (748 above) increases continually over time,
then there is likely a leak.  The following command can be used to
identify the leaking lock classes::

	grep "BD" /proc/lockdep

Run the command and save the output, then compare against the output from
a later run of this command to identify the leakers.  This same output
can also help you find situations where runtime lock initialization has
been omitted.

Recursive read locks:
---------------------
The whole of the rest document tries to prove a certain type of cycle is equivalent
to deadlock possibility.

There are three types of lockers: writers (i.e. exclusive lockers, like
spin_lock() or write_lock()), non-recursive readers (i.e. shared lockers, like
down_read()) and recursive readers (recursive shared lockers, like rcu_read_lock()).
And we use the following notations of those lockers in the rest of the document:

	W or E:	stands for writers (exclusive lockers).
	r:	stands for non-recursive readers.
	R:	stands for recursive readers.
	S:	stands for all readers (non-recursive + recursive), as both are shared lockers.
	N:	stands for writers and non-recursive readers, as both are not recursive.

Obviously, N is "r or W" and S is "r or R".

Recursive readers, as their name indicates, are the lockers allowed to acquire
even inside the critical section of another reader of the same lock instance,
in other words, allowing nested read-side critical sections of one lock instance.

While non-recursive readers will cause a self deadlock if trying to acquire inside
the critical section of another reader of the same lock instance.

The difference between recursive readers and non-recursive readers is because:
recursive readers get blocked only by a write lock *holder*, while non-recursive
readers could get blocked by a write lock *waiter*. Considering the follow
example::

	TASK A:			TASK B:

	read_lock(X);
				write_lock(X);
	read_lock_2(X);

Task A gets the reader (no matter whether recursive or non-recursive) on X via
read_lock() first. And when task B tries to acquire writer on X, it will block
and become a waiter for writer on X. Now if read_lock_2() is recursive readers,
task A will make progress, because writer waiters don't block recursive readers,
and there is no deadlock. However, if read_lock_2() is non-recursive readers,
it will get blocked by writer waiter B, and cause a self deadlock.

Block conditions on readers/writers of the same lock instance:
--------------------------------------------------------------
There are simply four block conditions:

1.	Writers block other writers.
2.	Readers block writers.
3.	Writers block both recursive readers and non-recursive readers.
4.	And readers (recursive or not) don't block other recursive readers but
	may block non-recursive readers (because of the potential co-existing
	writer waiters)

Block condition matrix, Y means the row blocks the column, and N means otherwise.

	+---+---+---+---+
	|   | W | r | R |
	+---+---+---+---+
	| W | Y | Y | Y |
	+---+---+---+---+
	| r | Y | Y | N |
	+---+---+---+---+
	| R | Y | Y | N |
	+---+---+---+---+

	(W: writers, r: non-recursive readers, R: recursive readers)

acquired recursively. Unlike non-recursive read locks, recursive read locks
only get blocked by current write lock *holders* other than write lock
*waiters*, for example::

	TASK A:			TASK B:

	read_lock(X);

				write_lock(X);

	read_lock(X);

is not a deadlock for recursive read locks, as while the task B is waiting for
the lock X, the second read_lock() doesn't need to wait because it's a recursive
read lock. However if the read_lock() is non-recursive read lock, then the above
case is a deadlock, because even if the write_lock() in TASK B cannot get the
lock, but it can block the second read_lock() in TASK A.

Note that a lock can be a write lock (exclusive lock), a non-recursive read
lock (non-recursive shared lock) or a recursive read lock (recursive shared
lock), depending on the lock operations used to acquire it (more specifically,
the value of the 'read' parameter for lock_acquire()). In other words, a single
lock instance has three types of acquisition depending on the acquisition
functions: exclusive, non-recursive read, and recursive read.

To be concise, we call that write locks and non-recursive read locks as
"non-recursive" locks and recursive read locks as "recursive" locks.

Recursive locks don't block each other, while non-recursive locks do (this is
even true for two non-recursive read locks). A non-recursive lock can block the
corresponding recursive lock, and vice versa.

A deadlock case with recursive locks involved is as follow::

	TASK A:			TASK B:

	read_lock(X);
				read_lock(Y);
	write_lock(Y);
				write_lock(X);

Task A is waiting for task B to read_unlock() Y and task B is waiting for task
A to read_unlock() X.

Dependency types and strong dependency paths:
---------------------------------------------
Lock dependencies record the orders of the acquisitions of a pair of locks, and
because there are 3 types for lockers, there are, in theory, 9 types of lock
dependencies, but we can show that 4 types of lock dependencies are enough for
deadlock detection.

For each lock dependency::

	L1 -> L2

, which means lockdep has seen L1 held before L2 held in the same context at runtime.
And in deadlock detection, we care whether we could get blocked on L2 with L1 held,
IOW, whether there is a locker L3 that L1 blocks L3 and L2 gets blocked by L3. So
we only care about 1) what L1 blocks and 2) what blocks L2. As a result, we can combine
recursive readers and non-recursive readers for L1 (as they block the same types) and
we can combine writers and non-recursive readers for L2 (as they get blocked by the
same types).

With the above combination for simplification, there are 4 types of dependency edges
in the lockdep graph:

1) -(ER)->:
	    exclusive writer to recursive reader dependency, "X -(ER)-> Y" means
	    X -> Y and X is a writer and Y is a recursive reader.

2) -(EN)->:
	    exclusive writer to non-recursive locker dependency, "X -(EN)-> Y" means
	    X -> Y and X is a writer and Y is either a writer or non-recursive reader.

3) -(SR)->:
	    shared reader to recursive reader dependency, "X -(SR)-> Y" means
	    X -> Y and X is a reader (recursive or not) and Y is a recursive reader.

4) -(SN)->:
	    shared reader to non-recursive locker dependency, "X -(SN)-> Y" means
	    X -> Y and X is a reader (recursive or not) and Y is either a writer or
	    non-recursive reader.

Note that given two locks, they may have multiple dependencies between them,
for example::

	TASK A:

	read_lock(X);
	write_lock(Y);
	...

	TASK B:

	write_lock(X);
	write_lock(Y);

, we have both X -(SN)-> Y and X -(EN)-> Y in the dependency graph.

We use -(xN)-> to represent edges that are either -(EN)-> or -(SN)->, the
similar for -(Ex)->, -(xR)-> and -(Sx)->

A "path" is a series of conjunct dependency edges in the graph. And we define a
"strong" path, which indicates the strong dependency throughout each dependency
in the path, as the path that doesn't have two conjunct edges (dependencies) as
-(xR)-> and -(Sx)->. In other words, a "strong" path is a path from a lock
walking to another through the lock dependencies, and if X -> Y -> Z is in the
path (where X, Y, Z are locks), and the walk from X to Y is through a -(SR)-> or
-(ER)-> dependency, the walk from Y to Z must not be through a -(SN)-> or
-(SR)-> dependency.

We will see why the path is called "strong" in next section.

Recursive Read Deadlock Detection:
----------------------------------

We now prove two things:

Lemma 1:

If there is a closed strong path (i.e. a strong circle), then there is a
combination of locking sequences that causes deadlock. I.e. a strong circle is
sufficient for deadlock detection.

Lemma 2:

If there is no closed strong path (i.e. strong circle), then there is no
combination of locking sequences that could cause deadlock. I.e.  strong
circles are necessary for deadlock detection.

With these two Lemmas, we can easily say a closed strong path is both sufficient
and necessary for deadlocks, therefore a closed strong path is equivalent to
deadlock possibility. As a closed strong path stands for a dependency chain that
could cause deadlocks, so we call it "strong", considering there are dependency
circles that won't cause deadlocks.

Proof for sufficiency (Lemma 1):

Let's say we have a strong circle::

	L1 -> L2 ... -> Ln -> L1

, which means we have dependencies::

	L1 -> L2
	L2 -> L3
	...
	Ln-1 -> Ln
	Ln -> L1

We now can construct a combination of locking sequences that cause deadlock:

Firstly let's make one CPU/task get the L1 in L1 -> L2, and then another get
the L2 in L2 -> L3, and so on. After this, all of the Lx in Lx -> Lx+1 are
held by different CPU/tasks.

And then because we have L1 -> L2, so the holder of L1 is going to acquire L2
in L1 -> L2, however since L2 is already held by another CPU/task, plus L1 ->
L2 and L2 -> L3 are not -(xR)-> and -(Sx)-> (the definition of strong), which
means either L2 in L1 -> L2 is a non-recursive locker (blocked by anyone) or
the L2 in L2 -> L3, is writer (blocking anyone), therefore the holder of L1
cannot get L2, it has to wait L2's holder to release.

Moreover, we can have a similar conclusion for L2's holder: it has to wait L3's
holder to release, and so on. We now can prove that Lx's holder has to wait for
Lx+1's holder to release, and note that Ln+1 is L1, so we have a circular
waiting scenario and nobody can get progress, therefore a deadlock.

Proof for necessary (Lemma 2):

Lemma 2 is equivalent to: If there is a deadlock scenario, then there must be a
strong circle in the dependency graph.

According to Wikipedia[1], if there is a deadlock, then there must be a circular
waiting scenario, means there are N CPU/tasks, where CPU/task P1 is waiting for
a lock held by P2, and P2 is waiting for a lock held by P3, ... and Pn is waiting
for a lock held by P1. Let's name the lock Px is waiting as Lx, so since P1 is waiting
for L1 and holding Ln, so we will have Ln -> L1 in the dependency graph. Similarly,
we have L1 -> L2, L2 -> L3, ..., Ln-1 -> Ln in the dependency graph, which means we
have a circle::

	Ln -> L1 -> L2 -> ... -> Ln

, and now let's prove the circle is strong:

For a lock Lx, Px contributes the dependency Lx-1 -> Lx and Px+1 contributes
the dependency Lx -> Lx+1, and since Px is waiting for Px+1 to release Lx,
so it's impossible that Lx on Px+1 is a reader and Lx on Px is a recursive
reader, because readers (no matter recursive or not) don't block recursive
readers, therefore Lx-1 -> Lx and Lx -> Lx+1 cannot be a -(xR)-> -(Sx)-> pair,
and this is true for any lock in the circle, therefore, the circle is strong.

References:
-----------
[1]: https://en.wikipedia.org/wiki/Deadlock
[2]: Shibu, K. (2009). Intro To Embedded Systems (1st ed.). Tata McGraw-Hill


code:
===============
Lock Statistics
===============

What
====

As the name suggests, it provides statistics on locks.

Why
===

Because things like lock contention can severely impact performance.

How
===

Lockdep already has hooks in the lock functions and maps lock instances to
lock classes. We build on that (see Documentation/locking/lockdep-design.rst).
The graph below shows the relation between the lock functions and the various
hooks therein::

        __acquire
            |
           lock _____
            |        \
            |    __contended
            |         |
            |       <wait>
            | _______/
            |/
            |
       __acquired
            |
            .
          <hold>
            .
            |
       __release
            |
         unlock

  lock, unlock	- the regular lock functions
  __*		- the hooks
  <> 		- states

With these hooks we provide the following statistics:

 con-bounces
	- number of lock contention that involved x-cpu data
 contentions
	- number of lock acquisitions that had to wait
 wait time
     min
	- shortest (non-0) time we ever had to wait for a lock
     max
	- longest time we ever had to wait for a lock
     total
	- total time we spend waiting on this lock
     avg
	- average time spent waiting on this lock
 acq-bounces
	- number of lock acquisitions that involved x-cpu data
 acquisitions
	- number of times we took the lock
 hold time
     min
	- shortest (non-0) time we ever held the lock
     max
	- longest time we ever held the lock
     total
	- total time this lock was held
     avg
	- average time this lock was held

These numbers are gathered per lock class, per read/write state (when
applicable).

It also tracks 4 contention points per class. A contention point is a call site
that had to wait on lock acquisition.

Configuration
-------------

Lock statistics are enabled via CONFIG_LOCK_STAT.

Usage
-----

Enable collection of statistics::

	# echo 1 >/proc/sys/kernel/lock_stat

Disable collection of statistics::

	# echo 0 >/proc/sys/kernel/lock_stat

Look at the current lock statistics::

  ( line numbers not part of actual output, done for clarity in the explanation
    below )

  # less /proc/lock_stat

  01 lock_stat version 0.4
  02-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
  03                              class name    con-bounces    contentions   waittime-min   waittime-max waittime-total   waittime-avg    acq-bounces   acquisitions   holdtime-min   holdtime-max holdtime-total   holdtime-avg
  04-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
  05
  06                         &mm->mmap_sem-W:            46             84           0.26         939.10       16371.53         194.90          47291        2922365           0.16     2220301.69 17464026916.32        5975.99
  07                         &mm->mmap_sem-R:            37            100           1.31      299502.61      325629.52        3256.30         212344       34316685           0.10        7744.91    95016910.20           2.77
  08                         ---------------
  09                           &mm->mmap_sem              1          [<ffffffff811502a7>] khugepaged_scan_mm_slot+0x57/0x280
  10                           &mm->mmap_sem             96          [<ffffffff815351c4>] __do_page_fault+0x1d4/0x510
  11                           &mm->mmap_sem             34          [<ffffffff81113d77>] vm_mmap_pgoff+0x87/0xd0
  12                           &mm->mmap_sem             17          [<ffffffff81127e71>] vm_munmap+0x41/0x80
  13                         ---------------
  14                           &mm->mmap_sem              1          [<ffffffff81046fda>] dup_mmap+0x2a/0x3f0
  15                           &mm->mmap_sem             60          [<ffffffff81129e29>] SyS_mprotect+0xe9/0x250
  16                           &mm->mmap_sem             41          [<ffffffff815351c4>] __do_page_fault+0x1d4/0x510
  17                           &mm->mmap_sem             68          [<ffffffff81113d77>] vm_mmap_pgoff+0x87/0xd0
  18
  19.............................................................................................................................................................................................................................
  20
  21                         unix_table_lock:           110            112           0.21          49.24         163.91           1.46          21094          66312           0.12         624.42       31589.81           0.48
  22                         ---------------
  23                         unix_table_lock             45          [<ffffffff8150ad8e>] unix_create1+0x16e/0x1b0
  24                         unix_table_lock             47          [<ffffffff8150b111>] unix_release_sock+0x31/0x250
  25                         unix_table_lock             15          [<ffffffff8150ca37>] unix_find_other+0x117/0x230
  26                         unix_table_lock              5          [<ffffffff8150a09f>] unix_autobind+0x11f/0x1b0
  27                         ---------------
  28                         unix_table_lock             39          [<ffffffff8150b111>] unix_release_sock+0x31/0x250
  29                         unix_table_lock             49          [<ffffffff8150ad8e>] unix_create1+0x16e/0x1b0
  30                         unix_table_lock             20          [<ffffffff8150ca37>] unix_find_other+0x117/0x230
  31                         unix_table_lock              4          [<ffffffff8150a09f>] unix_autobind+0x11f/0x1b0

This excerpt shows the first two lock class statistics. Line 01 shows the
output version - each time the format changes this will be updated. Line 02-04
show the header with column descriptions. Lines 05-18 and 20-31 show the actual
statistics. These statistics come in two parts; the actual stats separated by a
short separator (line 08, 13) from the contention points.

Lines 09-12 show the first 4 recorded contention points (the code
which tries to get the lock) and lines 14-17 show the first 4 recorded
contended points (the lock holder). It is possible that the max
con-bounces point is missing in the statistics.

The first lock (05-18) is a read/write lock, and shows two lines above the
short separator. The contention points don't match the column descriptors,
they have two: contentions and [<IP>] symbol. The second set of contention
points are the points we're contending with.

The integer part of the time values is in us.

Dealing with nested locks, subclasses may appear::

  32...........................................................................................................................................................................................................................
  33
  34                               &rq->lock:       13128          13128           0.43         190.53      103881.26           7.91          97454        3453404           0.00         401.11    13224683.11           3.82
  35                               ---------
  36                               &rq->lock          645          [<ffffffff8103bfc4>] task_rq_lock+0x43/0x75
  37                               &rq->lock          297          [<ffffffff8104ba65>] try_to_wake_up+0x127/0x25a
  38                               &rq->lock          360          [<ffffffff8103c4c5>] select_task_rq_fair+0x1f0/0x74a
  39                               &rq->lock          428          [<ffffffff81045f98>] scheduler_tick+0x46/0x1fb
  40                               ---------
  41                               &rq->lock           77          [<ffffffff8103bfc4>] task_rq_lock+0x43/0x75
  42                               &rq->lock          174          [<ffffffff8104ba65>] try_to_wake_up+0x127/0x25a
  43                               &rq->lock         4715          [<ffffffff8103ed4b>] double_rq_lock+0x42/0x54
  44                               &rq->lock          893          [<ffffffff81340524>] schedule+0x157/0x7b8
  45
  46...........................................................................................................................................................................................................................
  47
  48                             &rq->lock/1:        1526          11488           0.33         388.73      136294.31          11.86          21461          38404           0.00          37.93      109388.53           2.84
  49                             -----------
  50                             &rq->lock/1        11526          [<ffffffff8103ed58>] double_rq_lock+0x4f/0x54
  51                             -----------
  52                             &rq->lock/1         5645          [<ffffffff8103ed4b>] double_rq_lock+0x42/0x54
  53                             &rq->lock/1         1224          [<ffffffff81340524>] schedule+0x157/0x7b8
  54                             &rq->lock/1         4336          [<ffffffff8103ed58>] double_rq_lock+0x4f/0x54
  55                             &rq->lock/1          181          [<ffffffff8104ba65>] try_to_wake_up+0x127/0x25a

Line 48 shows statistics for the second subclass (/1) of &rq->lock class
(subclass starts from 0), since in this case, as line 50 suggests,
double_rq_lock actually acquires a nested lock of two spinlocks.

View the top contending locks::

  # grep : /proc/lock_stat | head
			clockevents_lock:       2926159        2947636           0.15       46882.81  1784540466.34         605.41        3381345        3879161           0.00        2260.97    53178395.68          13.71
		     tick_broadcast_lock:        346460         346717           0.18        2257.43    39364622.71         113.54        3642919        4242696           0.00        2263.79    49173646.60          11.59
		  &mapping->i_mmap_mutex:        203896         203899           3.36      645530.05 31767507988.39      155800.21        3361776        8893984           0.17        2254.15    14110121.02           1.59
			       &rq->lock:        135014         136909           0.18         606.09      842160.68           6.15        1540728       10436146           0.00         728.72    17606683.41           1.69
	       &(&zone->lru_lock)->rlock:         93000          94934           0.16          59.18      188253.78           1.98        1199912        3809894           0.15         391.40     3559518.81           0.93
			 tasklist_lock-W:         40667          41130           0.23        1189.42      428980.51          10.43         270278         510106           0.16         653.51     3939674.91           7.72
			 tasklist_lock-R:         21298          21305           0.20        1310.05      215511.12          10.12         186204         241258           0.14        1162.33     1179779.23           4.89
			      rcu_node_1:         47656          49022           0.16         635.41      193616.41           3.95         844888        1865423           0.00         764.26     1656226.96           0.89
       &(&dentry->d_lockref.lock)->rlock:         39791          40179           0.15        1302.08       88851.96           2.21        2790851       12527025           0.10        1910.75     3379714.27           0.27
			      rcu_node_0:         29203          30064           0.16         786.55     1555573.00          51.74          88963         244254           0.00         398.87      428872.51           1.76

Clear the statistics::

  # echo 0 > /proc/lock_stat

repo_name: angery/linux


code:
==================================
Kernel Lock Torture Test Operation
==================================

CONFIG_LOCK_TORTURE_TEST
========================

The CONFIG LOCK_TORTURE_TEST config option provides a kernel module
that runs torture tests on core kernel locking primitives. The kernel
module, 'locktorture', may be built after the fact on the running
kernel to be tested, if desired. The tests periodically output status
messages via printk(), which can be examined via the dmesg (perhaps
grepping for "torture").  The test is started when the module is loaded,
and stops when the module is unloaded. This program is based on how RCU
is tortured, via rcutorture.

This torture test consists of creating a number of kernel threads which
acquire the lock and hold it for specific amount of time, thus simulating
different critical region behaviors. The amount of contention on the lock
can be simulated by either enlarging this critical region hold time and/or
creating more kthreads.

Module Parameters
=================

This module has the following parameters:

Locktorture-specific
--------------------

nwriters_stress
		  Number of kernel threads that will stress exclusive lock
		  ownership (writers). The default value is twice the number
		  of online CPUs.

nreaders_stress
		  Number of kernel threads that will stress shared lock
		  ownership (readers). The default is the same amount of writer
		  locks. If the user did not specify nwriters_stress, then
		  both readers and writers be the amount of online CPUs.

torture_type
		  Type of lock to torture. By default, only spinlocks will
		  be tortured. This module can torture the following locks,
		  with string values as follows:

		     - "lock_busted":
				Simulates a buggy lock implementation.

		     - "spin_lock":
				spin_lock() and spin_unlock() pairs.

		     - "spin_lock_irq":
				spin_lock_irq() and spin_unlock_irq() pairs.

		     - "rw_lock":
				read/write lock() and unlock() rwlock pairs.

		     - "rw_lock_irq":
				read/write lock_irq() and unlock_irq()
				rwlock pairs.

		     - "mutex_lock":
				mutex_lock() and mutex_unlock() pairs.

		     - "rtmutex_lock":
				rtmutex_lock() and rtmutex_unlock() pairs.
				Kernel must have CONFIG_RT_MUTEX=y.

		     - "rwsem_lock":
				read/write down() and up() semaphore pairs.

Torture-framework (RCU + locking)
---------------------------------

shutdown_secs
		  The number of seconds to run the test before terminating
		  the test and powering off the system.  The default is
		  zero, which disables test termination and system shutdown.
		  This capability is useful for automated testing.

onoff_interval
		  The number of seconds between each attempt to execute a
		  randomly selected CPU-hotplug operation.  Defaults
		  to zero, which disables CPU hotplugging.  In
		  CONFIG_HOTPLUG_CPU=n kernels, locktorture will silently
		  refuse to do any CPU-hotplug operations regardless of
		  what value is specified for onoff_interval.

onoff_holdoff
		  The number of seconds to wait until starting CPU-hotplug
		  operations.  This would normally only be used when
		  locktorture was built into the kernel and started
		  automatically at boot time, in which case it is useful
		  in order to avoid confusing boot-time code with CPUs
		  coming and going. This parameter is only useful if
		  CONFIG_HOTPLUG_CPU is enabled.

stat_interval
		  Number of seconds between statistics-related printk()s.
		  By default, locktorture will report stats every 60 seconds.
		  Setting the interval to zero causes the statistics to
		  be printed -only- when the module is unloaded.

stutter
		  The length of time to run the test before pausing for this
		  same period of time.  Defaults to "stutter=5", so as
		  to run and pause for (roughly) five-second intervals.
		  Specifying "stutter=0" causes the test to run continuously
		  without pausing.

shuffle_interval
		  The number of seconds to keep the test threads affinitied
		  to a particular subset of the CPUs, defaults to 3 seconds.
		  Used in conjunction with test_no_idle_hz.

verbose
		  Enable verbose debugging printing, via printk(). Enabled
		  by default. This extra information is mostly related to
		  high-level errors and reports from the main 'torture'
		  framework.

Statistics
==========

Statistics are printed in the following format::

  spin_lock-torture: Writes:  Total: 93746064  Max/Min: 0/0   Fail: 0
     (A)		    (B)		   (C)		  (D)	       (E)

  (A): Lock type that is being tortured -- torture_type parameter.

  (B): Number of writer lock acquisitions. If dealing with a read/write
       primitive a second "Reads" statistics line is printed.

  (C): Number of times the lock was acquired.

  (D): Min and max number of times threads failed to acquire the lock.

  (E): true/false values if there were errors acquiring the lock. This should
       -only- be positive if there is a bug in the locking primitive's
       implementation. Otherwise a lock should never fail (i.e., spin_lock()).
       Of course, the same applies for (C), above. A dummy example of this is
       the "lock_busted" type.

Usage
=====

The following script may be used to torture locks::

	#!/bin/sh

	modprobe locktorture
	sleep 3600
	rmmod locktorture
	dmesg | grep torture:

The output can be manually inspected for the error flag of "!!!".
One could of course create a more elaborate script that automatically
checked for such errors.  The "rmmod" command forces a "SUCCESS",
"FAILURE", or "RCU_HOTPLUG" indication to be printk()ed.  The first
two are self-explanatory, while the last indicates that while there
were no locking failures, CPU-hotplug problems were detected.

Also see: Documentation/RCU/torture.rst


code:
.. SPDX-License-Identifier: GPL-2.0

.. _kernel_hacking_locktypes:

==========================
Lock types and their rules
==========================

Introduction
============

The kernel provides a variety of locking primitives which can be divided
into three categories:

 - Sleeping locks
 - CPU local locks
 - Spinning locks

This document conceptually describes these lock types and provides rules
for their nesting, including the rules for use under PREEMPT_RT.

Lock categories
===============

Sleeping locks
--------------

Sleeping locks can only be acquired in preemptible task context.

Although implementations allow try_lock() from other contexts, it is
necessary to carefully evaluate the safety of unlock() as well as of
try_lock().  Furthermore, it is also necessary to evaluate the debugging
versions of these primitives.  In short, don't acquire sleeping locks from
other contexts unless there is no other option.

Sleeping lock types:

 - mutex
 - rt_mutex
 - semaphore
 - rw_semaphore
 - ww_mutex
 - percpu_rw_semaphore

On PREEMPT_RT kernels, these lock types are converted to sleeping locks:

 - local_lock
 - spinlock_t
 - rwlock_t

CPU local locks
---------------

 - local_lock

On non-PREEMPT_RT kernels, local_lock functions are wrappers around
preemption and interrupt disabling primitives. Contrary to other locking
mechanisms, disabling preemption or interrupts are pure CPU local
concurrency control mechanisms and not suited for inter-CPU concurrency
control.

Spinning locks
--------------

 - raw_spinlock_t
 - bit spinlocks

On non-PREEMPT_RT kernels, these lock types are also spinning locks:

 - spinlock_t
 - rwlock_t

Spinning locks implicitly disable preemption and the lock / unlock functions
can have suffixes which apply further protections:

 ===================  ====================================================
 _bh()                Disable / enable bottom halves (soft interrupts)
 _irq()               Disable / enable interrupts
 _irqsave/restore()   Save and disable / restore interrupt disabled state
 ===================  ====================================================

Owner semantics
===============

The aforementioned lock types except semaphores have strict owner
semantics:

  The context (task) that acquired the lock must release it.

rw_semaphores have a special interface which allows non-owner release for
readers.

rtmutex
=======

RT-mutexes are mutexes with support for priority inheritance (PI).

PI has limitations on non-PREEMPT_RT kernels due to preemption and
interrupt disabled sections.

PI clearly cannot preempt preemption-disabled or interrupt-disabled
regions of code, even on PREEMPT_RT kernels.  Instead, PREEMPT_RT kernels
execute most such regions of code in preemptible task context, especially
interrupt handlers and soft interrupts.  This conversion allows spinlock_t
and rwlock_t to be implemented via RT-mutexes.

semaphore
=========

semaphore is a counting semaphore implementation.

Semaphores are often used for both serialization and waiting, but new use
cases should instead use separate serialization and wait mechanisms, such
as mutexes and completions.

semaphores and PREEMPT_RT
----------------------------

PREEMPT_RT does not change the semaphore implementation because counting
semaphores have no concept of owners, thus preventing PREEMPT_RT from
providing priority inheritance for semaphores.  After all, an unknown
owner cannot be boosted. As a consequence, blocking on semaphores can
result in priority inversion.

rw_semaphore
============

rw_semaphore is a multiple readers and single writer lock mechanism.

On non-PREEMPT_RT kernels the implementation is fair, thus preventing
writer starvation.

rw_semaphore complies by default with the strict owner semantics, but there
exist special-purpose interfaces that allow non-owner release for readers.
These interfaces work independent of the kernel configuration.

rw_semaphore and PREEMPT_RT
---------------------------

PREEMPT_RT kernels map rw_semaphore to a separate rt_mutex-based
implementation, thus changing the fairness:

 Because an rw_semaphore writer cannot grant its priority to multiple
 readers, a preempted low-priority reader will continue holding its lock,
 thus starving even high-priority writers.  In contrast, because readers
 can grant their priority to a writer, a preempted low-priority writer will
 have its priority boosted until it releases the lock, thus preventing that
 writer from starving readers.

local_lock
==========

local_lock provides a named scope to critical sections which are protected
by disabling preemption or interrupts.

On non-PREEMPT_RT kernels local_lock operations map to the preemption and
interrupt disabling and enabling primitives:

 ===============================  ======================
 local_lock(&llock)               preempt_disable()
 local_unlock(&llock)             preempt_enable()
 local_lock_irq(&llock)           local_irq_disable()
 local_unlock_irq(&llock)         local_irq_enable()
 local_lock_irqsave(&llock)       local_irq_save()
 local_unlock_irqrestore(&llock)  local_irq_restore()
 ===============================  ======================

The named scope of local_lock has two advantages over the regular
primitives:

  - The lock name allows static analysis and is also a clear documentation
    of the protection scope while the regular primitives are scopeless and
    opaque.

  - If lockdep is enabled the local_lock gains a lockmap which allows to
    validate the correctness of the protection. This can detect cases where
    e.g. a function using preempt_disable() as protection mechanism is
    invoked from interrupt or soft-interrupt context. Aside of that
    lockdep_assert_held(&llock) works as with any other locking primitive.

local_lock and PREEMPT_RT
-------------------------

PREEMPT_RT kernels map local_lock to a per-CPU spinlock_t, thus changing
semantics:

  - All spinlock_t changes also apply to local_lock.

local_lock usage
----------------

local_lock should be used in situations where disabling preemption or
interrupts is the appropriate form of concurrency control to protect
per-CPU data structures on a non PREEMPT_RT kernel.

local_lock is not suitable to protect against preemption or interrupts on a
PREEMPT_RT kernel due to the PREEMPT_RT specific spinlock_t semantics.

raw_spinlock_t and spinlock_t
=============================

raw_spinlock_t
--------------

raw_spinlock_t is a strict spinning lock implementation in all kernels,
including PREEMPT_RT kernels.  Use raw_spinlock_t only in real critical
core code, low-level interrupt handling and places where disabling
preemption or interrupts is required, for example, to safely access
hardware state.  raw_spinlock_t can sometimes also be used when the
critical section is tiny, thus avoiding RT-mutex overhead.

spinlock_t
----------

The semantics of spinlock_t change with the state of PREEMPT_RT.

On a non-PREEMPT_RT kernel spinlock_t is mapped to raw_spinlock_t and has
exactly the same semantics.

spinlock_t and PREEMPT_RT
-------------------------

On a PREEMPT_RT kernel spinlock_t is mapped to a separate implementation
based on rt_mutex which changes the semantics:

 - Preemption is not disabled.

 - The hard interrupt related suffixes for spin_lock / spin_unlock
   operations (_irq, _irqsave / _irqrestore) do not affect the CPU's
   interrupt disabled state.

 - The soft interrupt related suffix (_bh()) still disables softirq
   handlers.

   Non-PREEMPT_RT kernels disable preemption to get this effect.

   PREEMPT_RT kernels use a per-CPU lock for serialization which keeps
   preemption enabled. The lock disables softirq handlers and also
   prevents reentrancy due to task preemption.

PREEMPT_RT kernels preserve all other spinlock_t semantics:

 - Tasks holding a spinlock_t do not migrate.  Non-PREEMPT_RT kernels
   avoid migration by disabling preemption.  PREEMPT_RT kernels instead
   disable migration, which ensures that pointers to per-CPU variables
   remain valid even if the task is preempted.

 - Task state is preserved across spinlock acquisition, ensuring that the
   task-state rules apply to all kernel configurations.  Non-PREEMPT_RT
   kernels leave task state untouched.  However, PREEMPT_RT must change
   task state if the task blocks during acquisition.  Therefore, it saves
   the current task state before blocking and the corresponding lock wakeup
   restores it, as shown below::

    task->state = TASK_INTERRUPTIBLE
     lock()
       block()
         task->saved_state = task->state
	 task->state = TASK_UNINTERRUPTIBLE
	 schedule()
					lock wakeup
					  task->state = task->saved_state

   Other types of wakeups would normally unconditionally set the task state
   to RUNNING, but that does not work here because the task must remain
   blocked until the lock becomes available.  Therefore, when a non-lock
   wakeup attempts to awaken a task blocked waiting for a spinlock, it
   instead sets the saved state to RUNNING.  Then, when the lock
   acquisition completes, the lock wakeup sets the task state to the saved
   state, in this case setting it to RUNNING::

    task->state = TASK_INTERRUPTIBLE
     lock()
       block()
         task->saved_state = task->state
	 task->state = TASK_UNINTERRUPTIBLE
	 schedule()
					non lock wakeup
					  task->saved_state = TASK_RUNNING

					lock wakeup
					  task->state = task->saved_state

   This ensures that the real wakeup cannot be lost.

rwlock_t
========

rwlock_t is a multiple readers and single writer lock mechanism.

Non-PREEMPT_RT kernels implement rwlock_t as a spinning lock and the
suffix rules of spinlock_t apply accordingly. The implementation is fair,
thus preventing writer starvation.

rwlock_t and PREEMPT_RT
-----------------------

PREEMPT_RT kernels map rwlock_t to a separate rt_mutex-based
implementation, thus changing semantics:

 - All the spinlock_t changes also apply to rwlock_t.

 - Because an rwlock_t writer cannot grant its priority to multiple
   readers, a preempted low-priority reader will continue holding its lock,
   thus starving even high-priority writers.  In contrast, because readers
   can grant their priority to a writer, a preempted low-priority writer
   will have its priority boosted until it releases the lock, thus
   preventing that writer from starving readers.

PREEMPT_RT caveats
==================

local_lock on RT
----------------

The mapping of local_lock to spinlock_t on PREEMPT_RT kernels has a few
implications. For example, on a non-PREEMPT_RT kernel the following code
sequence works as expected::

  local_lock_irq(&local_lock);
  raw_spin_lock(&lock);

and is fully equivalent to::

   raw_spin_lock_irq(&lock);

On a PREEMPT_RT kernel this code sequence breaks because local_lock_irq()
is mapped to a per-CPU spinlock_t which neither disables interrupts nor
preemption. The following code sequence works perfectly correct on both
PREEMPT_RT and non-PREEMPT_RT kernels::

  local_lock_irq(&local_lock);
  spin_lock(&lock);

Another caveat with local locks is that each local_lock has a specific
protection scope. So the following substitution is wrong::

  func1()
  {
    local_irq_save(flags);    -> local_lock_irqsave(&local_lock_1, flags);
    func3();
    local_irq_restore(flags); -> local_unlock_irqrestore(&local_lock_1, flags);
  }

  func2()
  {
    local_irq_save(flags);    -> local_lock_irqsave(&local_lock_2, flags);
    func3();
    local_irq_restore(flags); -> local_unlock_irqrestore(&local_lock_2, flags);
  }

  func3()
  {
    lockdep_assert_irqs_disabled();
    access_protected_data();
  }

On a non-PREEMPT_RT kernel this works correctly, but on a PREEMPT_RT kernel
local_lock_1 and local_lock_2 are distinct and cannot serialize the callers
of func3(). Also the lockdep assert will trigger on a PREEMPT_RT kernel
because local_lock_irqsave() does not disable interrupts due to the
PREEMPT_RT-specific semantics of spinlock_t. The correct substitution is::

  func1()
  {
    local_irq_save(flags);    -> local_lock_irqsave(&local_lock, flags);
    func3();
    local_irq_restore(flags); -> local_unlock_irqrestore(&local_lock, flags);
  }

  func2()
  {
    local_irq_save(flags);    -> local_lock_irqsave(&local_lock, flags);
    func3();
    local_irq_restore(flags); -> local_unlock_irqrestore(&local_lock, flags);
  }

  func3()
  {
    lockdep_assert_held(&local_lock);
    access_protected_data();
  }

spinlock_t and rwlock_t
-----------------------

The changes in spinlock_t and rwlock_t semantics on PREEMPT_RT kernels
have a few implications.  For example, on a non-PREEMPT_RT kernel the
following code sequence works as expected::

   local_irq_disable();
   spin_lock(&lock);

and is fully equivalent to::

   spin_lock_irq(&lock);

Same applies to rwlock_t and the _irqsave() suffix variants.

On PREEMPT_RT kernel this code sequence breaks because RT-mutex requires a
fully preemptible context.  Instead, use spin_lock_irq() or
spin_lock_irqsave() and their unlock counterparts.  In cases where the
interrupt disabling and locking must remain separate, PREEMPT_RT offers a
local_lock mechanism.  Acquiring the local_lock pins the task to a CPU,
allowing things like per-CPU interrupt disabled locks to be acquired.
However, this approach should be used only where absolutely necessary.

A typical scenario is protection of per-CPU variables in thread context::

  struct foo *p = get_cpu_ptr(&var1);

  spin_lock(&p->lock);
  p->count += this_cpu_read(var2);

This is correct code on a non-PREEMPT_RT kernel, but on a PREEMPT_RT kernel
this breaks. The PREEMPT_RT-specific change of spinlock_t semantics does
not allow to acquire p->lock because get_cpu_ptr() implicitly disables
preemption. The following substitution works on both kernels::

  struct foo *p;

  migrate_disable();
  p = this_cpu_ptr(&var1);
  spin_lock(&p->lock);
  p->count += this_cpu_read(var2);

migrate_disable() ensures that the task is pinned on the current CPU which
in turn guarantees that the per-CPU access to var1 and var2 are staying on
the same CPU while the task remains preemptible.

The migrate_disable() substitution is not valid for the following
scenario::

  func()
  {
    struct foo *p;

    migrate_disable();
    p = this_cpu_ptr(&var1);
    p->val = func2();

This breaks because migrate_disable() does not protect against reentrancy from
a preempting task. A correct substitution for this case is::

  func()
  {
    struct foo *p;

    local_lock(&foo_lock);
    p = this_cpu_ptr(&var1);
    p->val = func2();

On a non-PREEMPT_RT kernel this protects against reentrancy by disabling
preemption. On a PREEMPT_RT kernel this is achieved by acquiring the
underlying per-CPU spinlock.

raw_spinlock_t on RT
--------------------

Acquiring a raw_spinlock_t disables preemption and possibly also
interrupts, so the critical section must avoid acquiring a regular
spinlock_t or rwlock_t, for example, the critical section must avoid
allocating memory.  Thus, on a non-PREEMPT_RT kernel the following code
works perfectly::

  raw_spin_lock(&lock);
  p = kmalloc(sizeof(*p), GFP_ATOMIC);

But this code fails on PREEMPT_RT kernels because the memory allocator is
fully preemptible and therefore cannot be invoked from truly atomic
contexts.  However, it is perfectly fine to invoke the memory allocator
while holding normal non-raw spinlocks because they do not disable
preemption on PREEMPT_RT kernels::

  spin_lock(&lock);
  p = kmalloc(sizeof(*p), GFP_ATOMIC);

bit spinlocks
-------------

PREEMPT_RT cannot substitute bit spinlocks because a single bit is too
small to accommodate an RT-mutex.  Therefore, the semantics of bit
spinlocks are preserved on PREEMPT_RT kernels, so that the raw_spinlock_t
caveats also apply to bit spinlocks.

Some bit spinlocks are replaced with regular spinlock_t for PREEMPT_RT
using conditional (#ifdef'ed) code changes at the usage site.  In contrast,
usage-site changes are not needed for the spinlock_t substitution.
Instead, conditionals in header files and the core locking implemementation
enable the compiler to do the substitution transparently.

Lock type nesting rules
=======================

The most basic rules are:

  - Lock types of the same lock category (sleeping, CPU local, spinning)
    can nest arbitrarily as long as they respect the general lock ordering
    rules to prevent deadlocks.

  - Sleeping lock types cannot nest inside CPU local and spinning lock types.

  - CPU local and spinning lock types can nest inside sleeping lock types.

  - Spinning lock types can nest inside all lock types

These constraints apply both in PREEMPT_RT and otherwise.

The fact that PREEMPT_RT changes the lock category of spinlock_t and
rwlock_t from spinning to sleeping and substitutes local_lock with a
per-CPU spinlock_t means that they cannot be acquired while holding a raw
spinlock.  This results in the following nesting ordering:

  1) Sleeping locks
  2) spinlock_t, rwlock_t, local_lock
  3) raw_spinlock_t and bit spinlocks

Lockdep will complain if these constraints are violated, both in
PREEMPT_RT and otherwise.


code:
=======================
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).

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.


code:
====================
Percpu rw semaphores
====================

Percpu rw semaphores is a new read-write semaphore design that is
optimized for locking for reading.

The problem with traditional read-write semaphores is that when multiple
cores take the lock for reading, the cache line containing the semaphore
is bouncing between L1 caches of the cores, causing performance
degradation.

Locking for reading is very fast, it uses RCU and it avoids any atomic
instruction in the lock and unlock path. On the other hand, locking for
writing is very expensive, it calls synchronize_rcu() that can take
hundreds of milliseconds.

The lock is declared with "struct percpu_rw_semaphore" type.
The lock is initialized percpu_init_rwsem, it returns 0 on success and
-ENOMEM on allocation failure.
The lock must be freed with percpu_free_rwsem to avoid memory leak.

The lock is locked for read with percpu_down_read, percpu_up_read and
for write with percpu_down_write, percpu_up_write.

The idea of using RCU for optimized rw-lock was introduced by
Eric Dumazet <eric.dumazet@gmail.com>.
The code was written by Mikulas Patocka <mpatocka@redhat.com>


code:
======================
Lightweight PI-futexes
======================

We are calling them lightweight for 3 reasons:

 - in the user-space fastpath a PI-enabled futex involves no kernel work
   (or any other PI complexity) at all. No registration, no extra kernel
   calls - just pure fast atomic ops in userspace.

 - even in the slowpath, the system call and scheduling pattern is very
   similar to normal futexes.

 - the in-kernel PI implementation is streamlined around the mutex
   abstraction, with strict rules that keep the implementation
   relatively simple: only a single owner may own a lock (i.e. no
   read-write lock support), only the owner may unlock a lock, no
   recursive locking, etc.

Priority Inheritance - why?
---------------------------

The short reply: user-space PI helps achieving/improving determinism for
user-space applications. In the best-case, it can help achieve
determinism and well-bound latencies. Even in the worst-case, PI will
improve the statistical distribution of locking related application
delays.

The longer reply
----------------

Firstly, sharing locks between multiple tasks is a common programming
technique that often cannot be replaced with lockless algorithms. As we
can see it in the kernel [which is a quite complex program in itself],
lockless structures are rather the exception than the norm - the current
ratio of lockless vs. locky code for shared data structures is somewhere
between 1:10 and 1:100. Lockless is hard, and the complexity of lockless
algorithms often endangers to ability to do robust reviews of said code.
I.e. critical RT apps often choose lock structures to protect critical
data structures, instead of lockless algorithms. Furthermore, there are
cases (like shared hardware, or other resource limits) where lockless
access is mathematically impossible.

Media players (such as Jack) are an example of reasonable application
design with multiple tasks (with multiple priority levels) sharing
short-held locks: for example, a highprio audio playback thread is
combined with medium-prio construct-audio-data threads and low-prio
display-colory-stuff threads. Add video and decoding to the mix and
we've got even more priority levels.

So once we accept that synchronization objects (locks) are an
unavoidable fact of life, and once we accept that multi-task userspace
apps have a very fair expectation of being able to use locks, we've got
to think about how to offer the option of a deterministic locking
implementation to user-space.

Most of the technical counter-arguments against doing priority
inheritance only apply to kernel-space locks. But user-space locks are
different, there we cannot disable interrupts or make the task
non-preemptible in a critical section, so the 'use spinlocks' argument
does not apply (user-space spinlocks have the same priority inversion
problems as other user-space locking constructs). Fact is, pretty much
the only technique that currently enables good determinism for userspace
locks (such as futex-based pthread mutexes) is priority inheritance:

Currently (without PI), if a high-prio and a low-prio task shares a lock
[this is a quite common scenario for most non-trivial RT applications],
even if all critical sections are coded carefully to be deterministic
(i.e. all critical sections are short in duration and only execute a
limited number of instructions), the kernel cannot guarantee any
deterministic execution of the high-prio task: any medium-priority task
could preempt the low-prio task while it holds the shared lock and
executes the critical section, and could delay it indefinitely.

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

As mentioned before, the userspace fastpath of PI-enabled pthread
mutexes involves no kernel work at all - they behave quite similarly to
normal futex-based locks: a 0 value means unlocked, and a value==TID
means locked. (This is the same method as used by list-based robust
futexes.) Userspace uses atomic ops to lock/unlock these mutexes without
entering the kernel.

To handle the slowpath, we have added two new futex ops:

  - FUTEX_LOCK_PI
  - FUTEX_UNLOCK_PI

If the lock-acquire fastpath fails, [i.e. an atomic transition from 0 to
TID fails], then FUTEX_LOCK_PI is called. The kernel does all the
remaining work: if there is no futex-queue attached to the futex address
yet then the code looks up the task that owns the futex [it has put its
own TID into the futex value], and attaches a 'PI state' structure to
the futex-queue. The pi_state includes an rt-mutex, which is a PI-aware,
kernel-based synchronization object. The 'other' task is made the owner
of the rt-mutex, and the FUTEX_WAITERS bit is atomically set in the
futex value. Then this task tries to lock the rt-mutex, on which it
blocks. Once it returns, it has the mutex acquired, and it sets the
futex value to its own TID and returns. Userspace has no other work to
perform - it now owns the lock, and futex value contains
FUTEX_WAITERS|TID.

If the unlock side fastpath succeeds, [i.e. userspace manages to do a
TID -> 0 atomic transition of the futex value], then no kernel work is
triggered.

If the unlock fastpath fails (because the FUTEX_WAITERS bit is set),
then FUTEX_UNLOCK_PI is called, and the kernel unlocks the futex on the
behalf of userspace - and it also unlocks the attached
pi_state->rt_mutex and thus wakes up any potential waiters.

Note that under this approach, contrary to previous PI-futex approaches,
there is no prior 'registration' of a PI-futex. [which is not quite
possible anyway, due to existing ABI properties of pthread mutexes.]

Also, under this scheme, 'robustness' and 'PI' are two orthogonal
properties of futexes, and all four combinations are possible: futex,
robust-futex, PI-futex, robust+PI-futex.

More details about priority inheritance can be found in
Documentation/locking/rt-mutex.rst.


code:
===========================================================================
Proper Locking Under a Preemptible Kernel: Keeping Kernel Code Preempt-Safe
===========================================================================

:Author: Robert Love <rml@tech9.net>

Introduction
============

A preemptible kernel creates new locking issues.  The issues are the same as
those under SMP: concurrency and reentrancy.  Thankfully, the Linux preemptible
kernel model leverages existing SMP locking mechanisms.  Thus, the kernel
requires explicit additional locking for very few additional situations.

This document is for all kernel hackers.  Developing code in the kernel
requires protecting these situations.

RULE #1: Per-CPU data structures need explicit protection
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Two similar problems arise. An example code snippet::

	struct this_needs_locking tux[NR_CPUS];
	tux[smp_processor_id()] = some_value;
	/* task is preempted here... */
	something = tux[smp_processor_id()];

First, since the data is per-CPU, it may not have explicit SMP locking, but
require it otherwise.  Second, when a preempted task is finally rescheduled,
the previous value of smp_processor_id may not equal the current.  You must
protect these situations by disabling preemption around them.

You can also use put_cpu() and get_cpu(), which will disable preemption.

RULE #2: CPU state must be protected.
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Under preemption, the state of the CPU must be protected.  This is arch-
dependent, but includes CPU structures and state not preserved over a context
switch.  For example, on x86, entering and exiting FPU mode is now a critical
section that must occur while preemption is disabled.  Think what would happen
if the kernel is executing a floating-point instruction and is then preempted.
Remember, the kernel does not save FPU state except for user tasks.  Therefore,
upon preemption, the FPU registers will be sold to the lowest bidder.  Thus,
preemption must be disabled around such regions.

Note, some FPU functions are already explicitly preempt safe.  For example,
kernel_fpu_begin and kernel_fpu_end will disable and enable preemption.

RULE #3: Lock acquire and release must be performed by same task
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

A lock acquired in one task must be released by the same task.  This
means you can't do oddball things like acquire a lock and go off to
play while another task releases it.  If you want to do something
like this, acquire and release the task in the same code path and
have the caller wait on an event by the other task.

Solution
========

Data protection under preemption is achieved by disabling preemption for the
duration of the critical region.

::

  preempt_enable()		decrement the preempt counter
  preempt_disable()		increment the preempt counter
  preempt_enable_no_resched()	decrement, but do not immediately preempt
  preempt_check_resched()	if needed, reschedule
  preempt_count()		return the preempt counter

The functions are nestable.  In other words, you can call preempt_disable
n-times in a code path, and preemption will not be reenabled until the n-th
call to preempt_enable.  The preempt statements define to nothing if
preemption is not enabled.

Note that you do not need to explicitly prevent preemption if you are holding
any locks or interrupts are disabled, since preemption is implicitly disabled
in those cases.

But keep in mind that 'irqs disabled' is a fundamentally unsafe way of
disabling preemption - any cond_resched() or cond_resched_lock() might trigger
a reschedule if the preempt count is 0. A simple printk() might trigger a
reschedule. So use this implicit preemption-disabling property only if you
know that the affected codepath does not do any of this. Best policy is to use
this only for small, atomic code that you wrote and which calls no complex
functions.

Example::

	cpucache_t *cc; /* this is per-CPU */
	preempt_disable();
	cc = cc_data(searchp);
	if (cc && cc->avail) {
		__free_block(searchp, cc_entry(cc), cc->avail);
		cc->avail = 0;
	}
	preempt_enable();
	return 0;

Notice how the preemption statements must encompass every reference of the
critical variables.  Another example::

	int buf[NR_CPUS];
	set_cpu_val(buf);
	if (buf[smp_processor_id()] == -1) printf(KERN_INFO "wee!\n");
	spin_lock(&buf_lock);
	/* ... */

This code is not preempt-safe, but see how easily we can fix it by simply
moving the spin_lock up two lines.

Preventing preemption using interrupt disabling
===============================================

It is possible to prevent a preemption event using local_irq_disable and
local_irq_save.  Note, when doing so, you must be very careful to not cause
an event that would set need_resched and result in a preemption check.  When
in doubt, rely on locking or explicit preemption disabling.

Note in 2.5 interrupt disabling is now only per-CPU (e.g. local).

An additional concern is proper usage of local_irq_disable and local_irq_save.
These may be used to protect from preemption, however, on exit, if preemption
may be enabled, a test to see if preemption is required should be done.  If
these are called from the spin_lock and read/write lock macros, the right thing
is done.  They may also be called within a spin-lock protected region, however,
if they are ever called outside of this context, a test for preemption should
be made. Do note that calls from interrupt context or bottom half/ tasklets
are also protected by preemption locks and so may use the versions which do
not check preemption.


code:
====================
The robust futex ABI
====================

:Author: Started by Paul Jackson <pj@sgi.com>

Robust_futexes provide a mechanism that is used in addition to normal
futexes, for kernel assist of cleanup of held locks on task exit.

The interesting data as to what futexes a thread is holding is kept on a
linked list in user space, where it can be updated efficiently as locks
are taken and dropped, without kernel intervention.  The only additional
kernel intervention required for robust_futexes above and beyond what is
required for futexes is:

 1) a one time call, per thread, to tell the kernel where its list of
    held robust_futexes begins, and
 2) internal kernel code at exit, to handle any listed locks held
    by the exiting thread.

The existing normal futexes already provide a "Fast Userspace Locking"
mechanism, which handles uncontested locking without needing a system
call, and handles contested locking by maintaining a list of waiting
threads in the kernel.  Options on the sys_futex(2) system call support
waiting on a particular futex, and waking up the next waiter on a
particular futex.

For robust_futexes to work, the user code (typically in a library such
as glibc linked with the application) has to manage and place the
necessary list elements exactly as the kernel expects them.  If it fails
to do so, then improperly listed locks will not be cleaned up on exit,
probably causing deadlock or other such failure of the other threads
waiting on the same locks.

A thread that anticipates possibly using robust_futexes should first
issue the system call::

    asmlinkage long
    sys_set_robust_list(struct robust_list_head __user *head, size_t len);

The pointer 'head' points to a structure in the threads address space
consisting of three words.  Each word is 32 bits on 32 bit arch's, or 64
bits on 64 bit arch's, and local byte order.  Each thread should have
its own thread private 'head'.

If a thread is running in 32 bit compatibility mode on a 64 native arch
kernel, then it can actually have two such structures - one using 32 bit
words for 32 bit compatibility mode, and one using 64 bit words for 64
bit native mode.  The kernel, if it is a 64 bit kernel supporting 32 bit
compatibility mode, will attempt to process both lists on each task
exit, if the corresponding sys_set_robust_list() call has been made to
setup that list.

  The first word in the memory structure at 'head' contains a
  pointer to a single linked list of 'lock entries', one per lock,
  as described below.  If the list is empty, the pointer will point
  to itself, 'head'.  The last 'lock entry' points back to the 'head'.

  The second word, called 'offset', specifies the offset from the
  address of the associated 'lock entry', plus or minus, of what will
  be called the 'lock word', from that 'lock entry'.  The 'lock word'
  is always a 32 bit word, unlike the other words above.  The 'lock
  word' holds 2 flag bits in the upper 2 bits, and the thread id (TID)
  of the thread holding the lock in the bottom 30 bits.  See further
  below for a description of the flag bits.

  The third word, called 'list_op_pending', contains transient copy of
  the address of the 'lock entry', during list insertion and removal,
  and is needed to correctly resolve races should a thread exit while
  in the middle of a locking or unlocking operation.

Each 'lock entry' on the single linked list starting at 'head' consists
of just a single word, pointing to the next 'lock entry', or back to
'head' if there are no more entries.  In addition, nearby to each 'lock
entry', at an offset from the 'lock entry' specified by the 'offset'
word, is one 'lock word'.

The 'lock word' is always 32 bits, and is intended to be the same 32 bit
lock variable used by the futex mechanism, in conjunction with
robust_futexes.  The kernel will only be able to wakeup the next thread
waiting for a lock on a threads exit if that next thread used the futex
mechanism to register the address of that 'lock word' with the kernel.

For each futex lock currently held by a thread, if it wants this
robust_futex support for exit cleanup of that lock, it should have one
'lock entry' on this list, with its associated 'lock word' at the
specified 'offset'.  Should a thread die while holding any such locks,
the kernel will walk this list, mark any such locks with a bit
indicating their holder died, and wakeup the next thread waiting for
that lock using the futex mechanism.

When a thread has invoked the above system call to indicate it
anticipates using robust_futexes, the kernel stores the passed in 'head'
pointer for that task.  The task may retrieve that value later on by
using the system call::

    asmlinkage long
    sys_get_robust_list(int pid, struct robust_list_head __user **head_ptr,
                        size_t __user *len_ptr);

It is anticipated that threads will use robust_futexes embedded in
larger, user level locking structures, one per lock.  The kernel
robust_futex mechanism doesn't care what else is in that structure, so
long as the 'offset' to the 'lock word' is the same for all
robust_futexes used by that thread.  The thread should link those locks
it currently holds using the 'lock entry' pointers.  It may also have
other links between the locks, such as the reverse side of a double
linked list, but that doesn't matter to the kernel.

By keeping its locks linked this way, on a list starting with a 'head'
pointer known to the kernel, the kernel can provide to a thread the
essential service available for robust_futexes, which is to help clean
up locks held at the time of (a perhaps unexpectedly) exit.

Actual locking and unlocking, during normal operations, is handled
entirely by user level code in the contending threads, and by the
existing futex mechanism to wait for, and wakeup, locks.  The kernels
only essential involvement in robust_futexes is to remember where the
list 'head' is, and to walk the list on thread exit, handling locks
still held by the departing thread, as described below.

There may exist thousands of futex lock structures in a threads shared
memory, on various data structures, at a given point in time. Only those
lock structures for locks currently held by that thread should be on
that thread's robust_futex linked lock list a given time.

A given futex lock structure in a user shared memory region may be held
at different times by any of the threads with access to that region. The
thread currently holding such a lock, if any, is marked with the threads
TID in the lower 30 bits of the 'lock word'.

When adding or removing a lock from its list of held locks, in order for
the kernel to correctly handle lock cleanup regardless of when the task
exits (perhaps it gets an unexpected signal 9 in the middle of
manipulating this list), the user code must observe the following
protocol on 'lock entry' insertion and removal:

On insertion:

 1) set the 'list_op_pending' word to the address of the 'lock entry'
    to be inserted,
 2) acquire the futex lock,
 3) add the lock entry, with its thread id (TID) in the bottom 30 bits
    of the 'lock word', to the linked list starting at 'head', and
 4) clear the 'list_op_pending' word.

On removal:

 1) set the 'list_op_pending' word to the address of the 'lock entry'
    to be removed,
 2) remove the lock entry for this lock from the 'head' list,
 3) release the futex lock, and
 4) clear the 'lock_op_pending' word.

On exit, the kernel will consider the address stored in
'list_op_pending' and the address of each 'lock word' found by walking
the list starting at 'head'.  For each such address, if the bottom 30
bits of the 'lock word' at offset 'offset' from that address equals the
exiting threads TID, then the kernel will do two things:

 1) if bit 31 (0x80000000) is set in that word, then attempt a futex
    wakeup on that address, which will waken the next thread that has
    used to the futex mechanism to wait on that address, and
 2) atomically set  bit 30 (0x40000000) in the 'lock word'.

In the above, bit 31 was set by futex waiters on that lock to indicate
they were waiting, and bit 30 is set by the kernel to indicate that the
lock owner died holding the lock.

The kernel exit code will silently stop scanning the list further if at
any point:

 1) the 'head' pointer or an subsequent linked list pointer
    is not a valid address of a user space word
 2) the calculated location of the 'lock word' (address plus
    'offset') is not the valid address of a 32 bit user space
    word
 3) if the list contains more than 1 million (subject to
    future kernel configuration changes) elements.

When the kernel sees a list entry whose 'lock word' doesn't have the
current threads TID in the lower 30 bits, it does nothing with that
entry, and goes on to the next entry.


code:
========================================
A description of what robust futexes are
========================================

:Started by: Ingo Molnar <mingo@redhat.com>

Background
----------

what are robust futexes? To answer that, we first need to understand
what futexes are: normal futexes are special types of locks that in the
noncontended case can be acquired/released from userspace without having
to enter the kernel.

A futex is in essence a user-space address, e.g. a 32-bit lock variable
field. If userspace notices contention (the lock is already owned and
someone else wants to grab it too) then the lock is marked with a value
that says "there's a waiter pending", and the sys_futex(FUTEX_WAIT)
syscall is used to wait for the other guy to release it. The kernel
creates a 'futex queue' internally, so that it can later on match up the
waiter with the waker - without them having to know about each other.
When the owner thread releases the futex, it notices (via the variable
value) that there were waiter(s) pending, and does the
sys_futex(FUTEX_WAKE) syscall to wake them up.  Once all waiters have
taken and released the lock, the futex is again back to 'uncontended'
state, and there's no in-kernel state associated with it. The kernel
completely forgets that there ever was a futex at that address. This
method makes futexes very lightweight and scalable.

"Robustness" is about dealing with crashes while holding a lock: if a
process exits prematurely while holding a pthread_mutex_t lock that is
also shared with some other process (e.g. yum segfaults while holding a
pthread_mutex_t, or yum is kill -9-ed), then waiters for that lock need
to be notified that the last owner of the lock exited in some irregular
way.

To solve such types of problems, "robust mutex" userspace APIs were
created: pthread_mutex_lock() returns an error value if the owner exits
prematurely - and the new owner can decide whether the data protected by
the lock can be recovered safely.

There is a big conceptual problem with futex based mutexes though: it is
the kernel that destroys the owner task (e.g. due to a SEGFAULT), but
the kernel cannot help with the cleanup: if there is no 'futex queue'
(and in most cases there is none, futexes being fast lightweight locks)
then the kernel has no information to clean up after the held lock!
Userspace has no chance to clean up after the lock either - userspace is
the one that crashes, so it has no opportunity to clean up. Catch-22.

In practice, when e.g. yum is kill -9-ed (or segfaults), a system reboot
is needed to release that futex based lock. This is one of the leading
bugreports against yum.

To solve this problem, the traditional approach was to extend the vma
(virtual memory area descriptor) concept to have a notion of 'pending
robust futexes attached to this area'. This approach requires 3 new
syscall variants to sys_futex(): FUTEX_REGISTER, FUTEX_DEREGISTER and
FUTEX_RECOVER. At do_exit() time, all vmas are searched to see whether
they have a robust_head set. This approach has two fundamental problems
left:

 - it has quite complex locking and race scenarios. The vma-based
   approach had been pending for years, but they are still not completely
   reliable.

 - they have to scan _every_ vma at sys_exit() time, per thread!

The second disadvantage is a real killer: pthread_exit() takes around 1
microsecond on Linux, but with thousands (or tens of thousands) of vmas
every pthread_exit() takes a millisecond or more, also totally
destroying the CPU's L1 and L2 caches!

This is very much noticeable even for normal process sys_exit_group()
calls: the kernel has to do the vma scanning unconditionally! (this is
because the kernel has no knowledge about how many robust futexes there
are to be cleaned up, because a robust futex might have been registered
in another task, and the futex variable might have been simply mmap()-ed
into this process's address space).

This huge overhead forced the creation of CONFIG_FUTEX_ROBUST so that
normal kernels can turn it off, but worse than that: the overhead makes
robust futexes impractical for any type of generic Linux distribution.

So something had to be done.

New approach to robust futexes
------------------------------

At the heart of this new approach there is a per-thread private list of
robust locks that userspace is holding (maintained by glibc) - which
userspace list is registered with the kernel via a new syscall [this
registration happens at most once per thread lifetime]. At do_exit()
time, the kernel checks this user-space list: are there any robust futex
locks to be cleaned up?

In the common case, at do_exit() time, there is no list registered, so
the cost of robust futexes is just a simple current->robust_list != NULL
comparison. If the thread has registered a list, then normally the list
is empty. If the thread/process crashed or terminated in some incorrect
way then the list might be non-empty: in this case the kernel carefully
walks the list [not trusting it], and marks all locks that are owned by
this thread with the FUTEX_OWNER_DIED bit, and wakes up one waiter (if
any).

The list is guaranteed to be private and per-thread at do_exit() time,
so it can be accessed by the kernel in a lockless way.

There is one race possible though: since adding to and removing from the
list is done after the futex is acquired by glibc, there is a few
instructions window for the thread (or process) to die there, leaving
the futex hung. To protect against this possibility, userspace (glibc)
also maintains a simple per-thread 'list_op_pending' field, to allow the
kernel to clean up if the thread dies after acquiring the lock, but just
before it could have added itself to the list. Glibc sets this
list_op_pending field before it tries to acquire the futex, and clears
it after the list-add (or list-remove) has finished.

That's all that is needed - all the rest of robust-futex cleanup is done
in userspace [just like with the previous patches].

Ulrich Drepper has implemented the necessary glibc support for this new
mechanism, which fully enables robust mutexes.

Key differences of this userspace-list based approach, compared to the
vma based method:

 - it's much, much faster: at thread exit time, there's no need to loop
   over every vma (!), which the VM-based method has to do. Only a very
   simple 'is the list empty' op is done.

 - no VM changes are needed - 'struct address_space' is left alone.

 - no registration of individual locks is needed: robust mutexes don't
   need any extra per-lock syscalls. Robust mutexes thus become a very
   lightweight primitive - so they don't force the application designer
   to do a hard choice between performance and robustness - robust
   mutexes are just as fast.

 - no per-lock kernel allocation happens.

 - no resource limits are needed.

 - no kernel-space recovery call (FUTEX_RECOVER) is needed.

 - the implementation and the locking is "obvious", and there are no
   interactions with the VM.

Performance
-----------

I have benchmarked the time needed for the kernel to process a list of 1
million (!) held locks, using the new method [on a 2GHz CPU]:

 - with FUTEX_WAIT set [contended mutex]: 130 msecs
 - without FUTEX_WAIT set [uncontended mutex]: 30 msecs

I have also measured an approach where glibc does the lock notification
[which it currently does for !pshared robust mutexes], and that took 256
msecs - clearly slower, due to the 1 million FUTEX_WAKE syscalls
userspace had to do.

(1 million held locks are unheard of - we expect at most a handful of
locks to be held at a time. Nevertheless it's nice to know that this
approach scales nicely.)

Implementation details
----------------------

The patch adds two new syscalls: one to register the userspace list, and
one to query the registered list pointer::

 asmlinkage long
 sys_set_robust_list(struct robust_list_head __user *head,
                     size_t len);

 asmlinkage long
 sys_get_robust_list(int pid, struct robust_list_head __user **head_ptr,
                     size_t __user *len_ptr);

List registration is very fast: the pointer is simply stored in
current->robust_list. [Note that in the future, if robust futexes become
widespread, we could extend sys_clone() to register a robust-list head
for new threads, without the need of another syscall.]

So there is virtually zero overhead for tasks not using robust futexes,
and even for robust futex users, there is only one extra syscall per
thread lifetime, and the cleanup operation, if it happens, is fast and
straightforward. The kernel doesn't have any internal distinction between
robust and normal futexes.

If a futex is found to be held at exit time, the kernel sets the
following bit of the futex word::

	#define FUTEX_OWNER_DIED        0x40000000

and wakes up the next futex waiter (if any). User-space does the rest of
the cleanup.

Otherwise, robust futexes are acquired by glibc by putting the TID into
the futex field atomically. Waiters set the FUTEX_WAITERS bit::

	#define FUTEX_WAITERS           0x80000000

and the remaining bits are for the TID.

Testing, architecture support
-----------------------------

I've tested the new syscalls on x86 and x86_64, and have made sure the
parsing of the userspace list is robust [ ;-) ] even if the list is
deliberately corrupted.

i386 and x86_64 syscalls are wired up at the moment, and Ulrich has
tested the new glibc code (on x86_64 and i386), and it works for his
robust-mutex testcases.

All other architectures should build just fine too - but they won't have
the new syscalls yet.

Architectures need to implement the new futex_atomic_cmpxchg_inatomic()
inline function before writing up the syscalls.