linux Documentation

https://www.kernel.org/doc/html/latest/

t = LL.acq *y (0)
		t++;
		*x = 1;

- Device operations.
 - Guarantees.

- Varieties of memory barrier.
 - What may not be assumed about memory barriers?
 - Data dependency barriers.
 - Control dependencies.
 - SMP barrier pairing.
 - Examples of memory barrier sequences.
 - Read memory barriers vs load speculation.
 - Transitivity

- Compiler barrier.
 - CPU memory barriers.
 - MMIO write barrier.

- Locking functions.
 - Interrupt disabling functions.
 - Sleep and wake-up functions.
 - Miscellaneous functions.

- Locks vs memory accesses.
 - Locks vs I/O accesses.

- Interprocessor interaction.
 - Atomic operations.
 - Accessing devices.
 - Interrupts.

- Cache coherency.
 - Cache coherency vs DMA.
 - Cache coherency vs MMIO.

- And then there's the Alpha.

- Circular buffers.

:                :
	            :                :
	            :                :
	+-------+   :   +--------+   :   +-------+
	|       |   :   |        |   :   |       |
	|       |   :   |        |   :   |       |
	| CPU 1 |<----->| Memory |<----->| CPU 2 |
	|       |   :   |        |   :   |       |
	|       |   :   |        |   :   |       |
	+-------+   :   +--------+   :   +-------+
	    ^       :       ^        :       ^
	    |       :       |        :       |
	    |       :       |        :       |
	    |       :       v        :       |
	    |       :   +--------+   :       |
	    |       :   |        |   :       |
	    |       :   |        |   :       |
	    +---------->| Device |<----------+
	            :   |        |   :
	            :   |        |   :
	            :   +--------+   :
	            :                :

CPU 1		CPU 2
===============	===============
{ A == 1; B == 2 }
A = 3;		x = A;
B = 4;		y = B;

STORE A=3,	STORE B=4,	x=LOAD A->3,	y=LOAD B->4
STORE A=3,	STORE B=4,	y=LOAD B->4,	x=LOAD A->3
STORE A=3,	x=LOAD A->3,	STORE B=4,	y=LOAD B->4
STORE A=3,	x=LOAD A->3,	y=LOAD B->2,	STORE B=4
STORE A=3,	y=LOAD B->2,	STORE B=4,	x=LOAD A->3
STORE A=3,	y=LOAD B->2,	x=LOAD A->3,	STORE B=4
STORE B=4,	STORE A=3,	x=LOAD A->3,	y=LOAD B->4
STORE B=4, ...
...

x == 1, y == 2
x == 1, y == 4
x == 3, y == 2
x == 3, y == 4

CPU 1		CPU 2
===============	===============
{ A == 1, B == 2, C = 3, P == &A, Q == &C }
B = 4;		Q = P;
P = &B		D = *Q;

(Q == &A) and (D == 1)
(Q == &B) and (D == 2)
(Q == &B) and (D == 4)

*A = 5;
x = *D;

STORE *A = 5, x = LOAD *D
x = LOAD *D, STORE *A = 5

Q = P; D = *Q;

 the CPU will issue the following memory operations:

Q = LOAD P, D = LOAD *Q

 and always in that order.

a = *X; *X = b;

 the CPU will only issue the following sequence of memory operations:

a = LOAD *X, STORE *X = b

 And for:

*X = c; d = *X;

 the CPU will only issue:

STORE *X = c, d = LOAD *X

 (Loads and stores overlap if they are targeted at overlapping pieces of
 memory).

X = *A; Y = *B; *D = Z;

 we may get any of the following sequences:

X = LOAD *A,  Y = LOAD *B,  STORE *D = Z
X = LOAD *A,  STORE *D = Z, Y = LOAD *B
Y = LOAD *B,  X = LOAD *A,  STORE *D = Z
Y = LOAD *B,  STORE *D = Z, X = LOAD *A
STORE *D = Z, X = LOAD *A,  Y = LOAD *B
STORE *D = Z, Y = LOAD *B,  X = LOAD *A

X = *A; Y = *(A + 4);

 we may get any one of the following sequences:

X = LOAD *A; Y = LOAD *(A + 4);
Y = LOAD *(A + 4); X = LOAD *A;
{X, Y} = LOAD {*A, *(A + 4) };

 And for:

*A = X; Y = *A;

 we may get either of:

STORE *A = X; Y = LOAD *A;
STORE *A = Y = X;

A write memory barrier gives a guarantee that all the STORE operations
 specified before the barrier will appear to happen before all the STORE
 operations specified after the barrier with respect to the other
 components of the system.

 A write barrier is a partial ordering on stores only; it is not required
 to have any effect on loads.

 A CPU can be viewed as committing a sequence of store operations to the
 memory system as time progresses.  All stores before a write barrier will
 occur in the sequence _before_ all the stores after the write barrier.

 [!] Note that write barriers should normally be paired with read or data
 dependency barriers; see the "SMP barrier pairing" subsection.

A data dependency barrier is a weaker form of read barrier.  In the case
 where two loads are performed such that the second depends on the result
 of the first (eg: the first load retrieves the address to which the second
 load will be directed), a data dependency barrier would be required to
 make sure that the target of the second load is updated before the address
 obtained by the first load is accessed.

 A data dependency barrier is a partial ordering on interdependent loads
 only; it is not required to have any effect on stores, independent loads
 or overlapping loads.

 As mentioned in (1), the other CPUs in the system can be viewed as
 committing sequences of stores to the memory system that the CPU being
 considered can then perceive.  A data dependency barrier issued by the CPU
 under consideration guarantees that for any load preceding it, if that
 load touches one of a sequence of stores from another CPU, then by the
 time the barrier completes, the effects of all the stores prior to that
 touched by the load will be perceptible to any loads issued after the data
 dependency barrier.

 See the "Examples of memory barrier sequences" subsection for diagrams
 showing the ordering constraints.

 [!] Note that the first load really has to have a _data_ dependency and
 not a control dependency.  If the address for the second load is dependent
 on the first load, but the dependency is through a conditional rather than
 actually loading the address itself, then it's a _control_ dependency and
 a full read barrier or better is required.  See the "Control dependencies"
 subsection for more information.

 [!] Note that data dependency barriers should normally be paired with
 write barriers; see the "SMP barrier pairing" subsection.

A read barrier is a data dependency barrier plus a guarantee that all the
 LOAD operations specified before the barrier will appear to happen before
 all the LOAD operations specified after the barrier with respect to the
 other components of the system.

 A read barrier is a partial ordering on loads only; it is not required to
 have any effect on stores.

 Read memory barriers imply data dependency barriers, and so can substitute
 for them.

 [!] Note that read barriers should normally be paired with write barriers;
 see the "SMP barrier pairing" subsection.

A general memory barrier gives a guarantee that all the LOAD and STORE
 operations specified before the barrier will appear to happen before all
 the LOAD and STORE operations specified after the barrier with respect to
 the other components of the system.

 A general memory barrier is a partial ordering over both loads and stores.

 General memory barriers imply both read and write memory barriers, and so
 can substitute for either.

This acts as a one-way permeable barrier.  It guarantees that all memory
 operations after the LOCK operation will appear to happen after the LOCK
 operation with respect to the other components of the system.

 Memory operations that occur before a LOCK operation may appear to happen
 after it completes.

 A LOCK operation should almost always be paired with an UNLOCK operation.

This also acts as a one-way permeable barrier.  It guarantees that all
 memory operations before the UNLOCK operation will appear to happen before
 the UNLOCK operation with respect to the other components of the system.

 Memory operations that occur after an UNLOCK operation may appear to
 happen before it completes.

 LOCK and UNLOCK operations are guaranteed to appear with respect to each
 other strictly in the order specified.

 The use of LOCK and UNLOCK operations generally precludes the need for
 other sorts of memory barrier (but note the exceptions mentioned in the
 subsection "MMIO write barrier").

[*] For information on bus mastering DMA and coherency please read:

    Documentation/PCI/pci.txt
    Documentation/DMA-API-HOWTO.txt
    Documentation/DMA-API.txt

CPU 1		CPU 2
===============	===============
{ A == 1, B == 2, C = 3, P == &A, Q == &C }
B = 4;
<write barrier>
P = &B
		Q = P;
		D = *Q;

(Q == &A) implies (D == 1)
(Q == &B) implies (D == 4)

(Q == &B) and (D == 2) ????

CPU 1		CPU 2
===============	===============
{ A == 1, B == 2, C = 3, P == &A, Q == &C }
B = 4;
<write barrier>
P = &B
		Q = P;
		<data dependency barrier>
		D = *Q;

CPU 1		CPU 2
===============	===============
{ M[0] == 1, M[1] == 2, M[3] = 3, P == 0, Q == 3 }
M[1] = 4;
<write barrier>
P = 1
		Q = P;
		<data dependency barrier>
		D = M[Q];

q = &a;
if (p)
	q = &b;
<data dependency barrier>
x = *q;

q = &a;
if (p)
	q = &b;
<read barrier>
x = *q;

CPU 1		CPU 2
===============	===============
a = 1;
<write barrier>
b = 2;		x = b;
		<read barrier>
		y = a;

CPU 1		CPU 2
===============	===============================
a = 1;
<write barrier>
b = &a;		x = b;
		<data dependency barrier>
		y = *x;

CPU 1                           CPU 2
===============                 ===============
a = 1;           }----   --->{  v = c
b = 2;           }    \ /    {  w = d
<write barrier>        \        <read barrier>
c = 3;           }    / \    {  x = a;
d = 4;           }----   --->{  y = b;

CPU 1
=======================
STORE A = 1
STORE B = 2
STORE C = 3
<write barrier>
STORE D = 4
STORE E = 5

+-------+       :      :
|       |       +------+
|       |------>| C=3  |     }     /\
|       |  :    +------+     }-----  \  -----> Events perceptible to
|       |  :    | A=1  |     }        \/       the rest of the system
|       |  :    +------+     }
| CPU 1 |  :    | B=2  |     }
|       |       +------+     }
|       |   wwwwwwwwwwwwwwww }   <--- At this point the write barrier
|       |       +------+     }        requires all stores prior to the
|       |  :    | E=5  |     }        barrier to be committed before
|       |  :    +------+     }        further stores may take place
|       |------>| D=4  |     }
|       |       +------+
+-------+       :      :
                   |
                   | Sequence in which stores are committed to the
                   | memory system by CPU 1
                   V

CPU 1			CPU 2
=======================	=======================
	{ B = 7; X = 9; Y = 8; C = &Y }
STORE A = 1
STORE B = 2
<write barrier>
STORE C = &B		LOAD X
STORE D = 4		LOAD C (gets &B)
			LOAD *C (reads B)

+-------+       :      :                :       :
|       |       +------+                +-------+  | Sequence of update
|       |------>| B=2  |-----       --->| Y->8  |  | of perception on
|       |  :    +------+     \          +-------+  | CPU 2
| CPU 1 |  :    | A=1  |      \     --->| C->&Y |  V
|       |       +------+       |        +-------+
|       |   wwwwwwwwwwwwwwww   |        :       :
|       |       +------+       |        :       :
|       |  :    | C=&B |---    |        :       :       +-------+
|       |  :    +------+   \   |        +-------+       |       |
|       |------>| D=4  |    ----------->| C->&B |------>|       |
|       |       +------+       |        +-------+       |       |
+-------+       :      :       |        :       :       |       |
                               |        :       :       |       |
                               |        :       :       | CPU 2 |
                               |        +-------+       |       |
    Apparently incorrect --->  |        | B->7  |------>|       |
    perception of B (!)        |        +-------+       |       |
                               |        :       :       |       |
                               |        +-------+       |       |
    The load of X holds --->    \       | X->9  |------>|       |
    up the maintenance           \      +-------+       |       |
    of coherence of B             ----->| B->2  |       +-------+
                                        +-------+
                                        :       :

CPU 1			CPU 2
=======================	=======================
	{ B = 7; X = 9; Y = 8; C = &Y }
STORE A = 1
STORE B = 2
<write barrier>
STORE C = &B		LOAD X
STORE D = 4		LOAD C (gets &B)
			<data dependency barrier>
			LOAD *C (reads B)

+-------+       :      :                :       :
|       |       +------+                +-------+
|       |------>| B=2  |-----       --->| Y->8  |
|       |  :    +------+     \          +-------+
| CPU 1 |  :    | A=1  |      \     --->| C->&Y |
|       |       +------+       |        +-------+
|       |   wwwwwwwwwwwwwwww   |        :       :
|       |       +------+       |        :       :
|       |  :    | C=&B |---    |        :       :       +-------+
|       |  :    +------+   \   |        +-------+       |       |
|       |------>| D=4  |    ----------->| C->&B |------>|       |
|       |       +------+       |        +-------+       |       |
+-------+       :      :       |        :       :       |       |
                               |        :       :       |       |
                               |        :       :       | CPU 2 |
                               |        +-------+       |       |
                               |        | X->9  |------>|       |
                               |        +-------+       |       |
  Makes sure all effects --->   \   ddddddddddddddddd   |       |
  prior to the store of C        \      +-------+       |       |
  are perceptible to              ----->| B->2  |------>|       |
  subsequent loads                      +-------+       |       |
                                        :       :       +-------+

CPU 1			CPU 2
=======================	=======================
	{ A = 0, B = 9 }
STORE A=1
<write barrier>
STORE B=2
			LOAD B
			LOAD A

+-------+       :      :                :       :
|       |       +------+                +-------+
|       |------>| A=1  |------      --->| A->0  |
|       |       +------+      \         +-------+
| CPU 1 |   wwwwwwwwwwwwwwww   \    --->| B->9  |
|       |       +------+        |       +-------+
|       |------>| B=2  |---     |       :       :
|       |       +------+   \    |       :       :       +-------+
+-------+       :      :    \   |       +-------+       |       |
                             ---------->| B->2  |------>|       |
                                |       +-------+       | CPU 2 |
                                |       | A->0  |------>|       |
                                |       +-------+       |       |
                                |       :       :       +-------+
                                 \      :       :
                                  \     +-------+
                                   ---->| A->1  |
                                        +-------+
                                        :       :

CPU 1			CPU 2
=======================	=======================
	{ A = 0, B = 9 }
STORE A=1
<write barrier>
STORE B=2
			LOAD B
			<read barrier>
			LOAD A

+-------+       :      :                :       :
|       |       +------+                +-------+
|       |------>| A=1  |------      --->| A->0  |
|       |       +------+      \         +-------+
| CPU 1 |   wwwwwwwwwwwwwwww   \    --->| B->9  |
|       |       +------+        |       +-------+
|       |------>| B=2  |---     |       :       :
|       |       +------+   \    |       :       :       +-------+
+-------+       :      :    \   |       +-------+       |       |
                             ---------->| B->2  |------>|       |
                                |       +-------+       | CPU 2 |
                                |       :       :       |       |
                                |       :       :       |       |
  At this point the read ---->   \  rrrrrrrrrrrrrrrrr   |       |
  barrier causes all effects      \     +-------+       |       |
  prior to the storage of B        ---->| A->1  |------>|       |
  to be perceptible to CPU 2            +-------+       |       |
                                        :       :       +-------+

CPU 1			CPU 2
=======================	=======================
	{ A = 0, B = 9 }
STORE A=1
<write barrier>
STORE B=2
			LOAD B
			LOAD A [first load of A]
			<read barrier>
			LOAD A [second load of A]

+-------+       :      :                :       :
|       |       +------+                +-------+
|       |------>| A=1  |------      --->| A->0  |
|       |       +------+      \         +-------+
| CPU 1 |   wwwwwwwwwwwwwwww   \    --->| B->9  |
|       |       +------+        |       +-------+
|       |------>| B=2  |---     |       :       :
|       |       +------+   \    |       :       :       +-------+
+-------+       :      :    \   |       +-------+       |       |
                             ---------->| B->2  |------>|       |
                                |       +-------+       | CPU 2 |
                                |       :       :       |       |
                                |       :       :       |       |
                                |       +-------+       |       |
                                |       | A->0  |------>| 1st   |
                                |       +-------+       |       |
  At this point the read ---->   \  rrrrrrrrrrrrrrrrr   |       |
  barrier causes all effects      \     +-------+       |       |
  prior to the storage of B        ---->| A->1  |------>| 2nd   |
  to be perceptible to CPU 2            +-------+       |       |
                                        :       :       +-------+

+-------+       :      :                :       :
|       |       +------+                +-------+
|       |------>| A=1  |------      --->| A->0  |
|       |       +------+      \         +-------+
| CPU 1 |   wwwwwwwwwwwwwwww   \    --->| B->9  |
|       |       +------+        |       +-------+
|       |------>| B=2  |---     |       :       :
|       |       +------+   \    |       :       :       +-------+
+-------+       :      :    \   |       +-------+       |       |
                             ---------->| B->2  |------>|       |
                                |       +-------+       | CPU 2 |
                                |       :       :       |       |
                                 \      :       :       |       |
                                  \     +-------+       |       |
                                   ---->| A->1  |------>| 1st   |
                                        +-------+       |       |
                                    rrrrrrrrrrrrrrrrr   |       |
                                        +-------+       |       |
                                        | A->1  |------>| 2nd   |
                                        +-------+       |       |
                                        :       :       +-------+

CPU 1	   		CPU 2
=======================	=======================
 	   		LOAD B
 	   		DIVIDE		} Divide instructions generally
 	   		DIVIDE		} take a long time to perform
 	   		LOAD A

:       :       +-------+
                                        +-------+       |       |
                                    --->| B->2  |------>|       |
                                        +-------+       | CPU 2 |
                                        :       :DIVIDE |       |
                                        +-------+       |       |
The CPU being busy doing a --->     --->| A->0  |~~~~   |       |
division speculates on the              +-------+   ~   |       |
LOAD of A                               :       :   ~   |       |
                                        :       :DIVIDE |       |
                                        :       :   ~   |       |
Once the divisions are complete -->     :       :   ~-->|       |
the CPU can then perform the            :       :       |       |
LOAD with immediate effect              :       :       +-------+

CPU 1	   		CPU 2
=======================	=======================
 	   		LOAD B
 	   		DIVIDE
 	   		DIVIDE
			<read barrier>
 	   		LOAD A

:       :       +-------+
                                        +-------+       |       |
                                    --->| B->2  |------>|       |
                                        +-------+       | CPU 2 |
                                        :       :DIVIDE |       |
                                        +-------+       |       |
The CPU being busy doing a --->     --->| A->0  |~~~~   |       |
division speculates on the              +-------+   ~   |       |
LOAD of A                               :       :   ~   |       |
                                        :       :DIVIDE |       |
                                        :       :   ~   |       |
                                        :       :   ~   |       |
                                    rrrrrrrrrrrrrrrr~   |       |
                                        :       :   ~   |       |
                                        :       :   ~-->|       |
                                        :       :       |       |
                                        :       :       +-------+

:       :       +-------+
                                        +-------+       |       |
                                    --->| B->2  |------>|       |
                                        +-------+       | CPU 2 |
                                        :       :DIVIDE |       |
                                        +-------+       |       |
The CPU being busy doing a --->     --->| A->0  |~~~~   |       |
division speculates on the              +-------+   ~   |       |
LOAD of A                               :       :   ~   |       |
                                        :       :DIVIDE |       |
                                        :       :   ~   |       |
                                        :       :   ~   |       |
                                    rrrrrrrrrrrrrrrrr   |       |
                                        +-------+       |       |
The speculation is discarded --->   --->| A->1  |------>|       |
and an updated value is                 +-------+       |       |
retrieved                               :       :       +-------+

CPU 1			CPU 2			CPU 3
=======================	=======================	=======================
	{ X = 0, Y = 0 }
STORE X=1		LOAD X			STORE Y=1
			<general barrier>	<general barrier>
			LOAD Y			LOAD X

CPU 1			CPU 2			CPU 3
=======================	=======================	=======================
	{ X = 0, Y = 0 }
STORE X=1		LOAD X			STORE Y=1
			<read barrier>		<general barrier>
			LOAD Y			LOAD X

barrier();

TYPE		MANDATORY		SMP CONDITIONAL
===============	=======================	===========================
GENERAL		mb()			smp_mb()
WRITE		wmb()			smp_wmb()
READ		rmb()			smp_rmb()
DATA DEPENDENCY	read_barrier_depends()	smp_read_barrier_depends()

This assigns the value to the variable and then inserts a full memory
 barrier after it, depending on the function.  It isn't guaranteed to
 insert anything more than a compiler barrier in a UP compilation.

These are for use with atomic add, subtract, increment and decrement
 functions that don't return a value, especially when used for reference
 counting.  These functions do not imply memory barriers.

 As an example, consider a piece of code that marks an object as being dead
 and then decrements the object's reference count:

obj->dead = 1;
smp_mb__before_atomic_dec();
atomic_dec(&obj->ref_count);

 This makes sure that the death mark on the object is perceived to be set
 *before* the reference counter is decremented.

 See Documentation/atomic_ops.txt for more information.  See the "Atomic
 operations" subsection for information on where to use these.

These are for use similar to the atomic inc/dec barriers.  These are
 typically used for bitwise unlocking operations, so care must be taken as
 there are no implicit memory barriers here either.

 Consider implementing an unlock operation of some nature by clearing a
 locking bit.  The clear_bit() would then need to be barriered like this:

smp_mb__before_clear_bit();
clear_bit( ... );

 This prevents memory operations before the clear leaking to after it.  See
 the subsection on "Locking Functions" with reference to UNLOCK operation
 implications.

 See Documentation/atomic_ops.txt for more information.  See the "Atomic
 operations" subsection for information on where to use these.

mmiowb();

Memory operations issued after the LOCK will be completed after the LOCK
 operation has completed.

 Memory operations issued before the LOCK may be completed after the LOCK
 operation has completed.

Memory operations issued before the UNLOCK will be completed before the
 UNLOCK operation has completed.

 Memory operations issued after the UNLOCK may be completed before the
 UNLOCK operation has completed.

All LOCK operations issued before another LOCK operation will be completed
 before that LOCK operation.

All LOCK operations issued before an UNLOCK operation will be completed
 before the UNLOCK operation.

 All UNLOCK operations issued before a LOCK operation will be completed
 before the LOCK operation.

Certain variants of the LOCK operation may fail, either due to being
 unable to get the lock immediately, or due to receiving an unblocked
 signal whilst asleep waiting for the lock to become available.  Failed
 locks do not imply any sort of barrier.

*A = a;
LOCK
UNLOCK
*B = b;

LOCK, STORE *B, STORE *A, UNLOCK

*A = a;
*B = b;
LOCK
*C = c;
*D = d;
UNLOCK
*E = e;
*F = f;

LOCK, {*F,*A}, *E, {*C,*D}, *B, UNLOCK

[+] Note that {*F,*A} indicates a combined access.

{*F,*A}, *B,	LOCK, *C, *D,	UNLOCK, *E
*A, *B, *C,	LOCK, *D,	UNLOCK, *E, *F
*A, *B,		LOCK, *C,	UNLOCK, *D, *E, *F
*B,		LOCK, *C, *D,	UNLOCK, {*F,*A}, *E

for (;;) {
	set_current_state(TASK_UNINTERRUPTIBLE);
	if (event_indicated)
		break;
	schedule();
}

CPU 1
===============================
set_current_state();
  set_mb();
    STORE current->state
    <general barrier>
LOAD event_indicated

prepare_to_wait();
prepare_to_wait_exclusive();

wait_event();
wait_event_interruptible();
wait_event_interruptible_exclusive();
wait_event_interruptible_timeout();
wait_event_killable();
wait_event_timeout();
wait_on_bit();
wait_on_bit_lock();

event_indicated = 1;
wake_up(&event_wait_queue);

event_indicated = 1;
wake_up_process(event_daemon);

CPU 1				CPU 2
===============================	===============================
set_current_state();		STORE event_indicated
  set_mb();			wake_up();
    STORE current->state	  <write barrier>
    <general barrier>		  STORE current->state
LOAD event_indicated

complete();
wake_up();
wake_up_all();
wake_up_bit();
wake_up_interruptible();
wake_up_interruptible_all();
wake_up_interruptible_nr();
wake_up_interruptible_poll();
wake_up_interruptible_sync();
wake_up_interruptible_sync_poll();
wake_up_locked();
wake_up_locked_poll();
wake_up_nr();
wake_up_poll();
wake_up_process();

set_current_state(TASK_INTERRUPTIBLE);
if (event_indicated)
	break;
__set_current_state(TASK_RUNNING);
do_something(my_data);

my_data = value;
event_indicated = 1;
wake_up(&event_wait_queue);

set_current_state(TASK_INTERRUPTIBLE);
if (event_indicated) {
	smp_rmb();
	do_something(my_data);
}

my_data = value;
smp_wmb();
event_indicated = 1;
wake_up(&event_wait_queue);

CPU 1				CPU 2
===============================	===============================
*A = a;				*E = e;
LOCK M				LOCK Q
*B = b;				*F = f;
*C = c;				*G = g;
UNLOCK M			UNLOCK Q
*D = d;				*H = h;

*E, LOCK M, LOCK Q, *G, *C, *F, *A, *B, UNLOCK Q, *D, *H, UNLOCK M

*B, *C or *D preceding LOCK M
*A, *B or *C following UNLOCK M
*F, *G or *H preceding LOCK Q
*E, *F or *G following UNLOCK Q

CPU 1				CPU 2
===============================	===============================
*A = a;
LOCK M		[1]
*B = b;
*C = c;
UNLOCK M	[1]
*D = d;				*E = e;
				LOCK M		[2]
				*F = f;
				*G = g;
				UNLOCK M	[2]
				*H = h;

*E, LOCK M [1], *C, *B, *A, UNLOCK M [1],
	LOCK M [2], *H, *F, *G, UNLOCK M [2], *D

*B, *C, *D, *F, *G or *H preceding LOCK M [1]
*A, *B or *C following UNLOCK M [1]
*F, *G or *H preceding LOCK M [2]
*A, *B, *C, *E, *F or *G following UNLOCK M [2]

CPU 1				CPU 2
===============================	===============================
spin_lock(Q)
writel(0, ADDR)
writel(1, DATA);
spin_unlock(Q);
				spin_lock(Q);
				writel(4, ADDR);
				writel(5, DATA);
				spin_unlock(Q);

STORE *ADDR = 0, STORE *ADDR = 4, STORE *DATA = 1, STORE *DATA = 5

CPU 1				CPU 2
===============================	===============================
spin_lock(Q)
writel(0, ADDR)
writel(1, DATA);
mmiowb();
spin_unlock(Q);
				spin_lock(Q);
				writel(4, ADDR);
				writel(5, DATA);
				mmiowb();
				spin_unlock(Q);

CPU 1				CPU 2
===============================	===============================
spin_lock(Q)
writel(0, ADDR)
a = readl(DATA);
spin_unlock(Q);
				spin_lock(Q);
				writel(4, ADDR);
				b = readl(DATA);
				spin_unlock(Q);

struct rw_semaphore {
	...
	spinlock_t lock;
	struct list_head waiters;
};

struct rwsem_waiter {
	struct list_head list;
	struct task_struct *task;
};

LOAD waiter->list.next;
LOAD waiter->task;
STORE waiter->task;
CALL wakeup
RELEASE task

CPU 1				CPU 2
===============================	===============================
				down_xxx()
				Queue waiter
				Sleep
up_yyy()
LOAD waiter->task;
STORE waiter->task;
				Woken up by other event
<preempt>
				Resume processing
				down_xxx() returns
				call foo()
				foo() clobbers *waiter
</preempt>
LOAD waiter->list.next;
--- OOPS ---

LOAD waiter->list.next;
LOAD waiter->task;
smp_mb();
STORE waiter->task;
CALL wakeup
RELEASE task

xchg();
cmpxchg();
atomic_cmpxchg();
atomic_inc_return();
atomic_dec_return();
atomic_add_return();
atomic_sub_return();
atomic_inc_and_test();
atomic_dec_and_test();
atomic_sub_and_test();
atomic_add_negative();
atomic_add_unless();	/* when succeeds (returns 1) */
test_and_set_bit();
test_and_clear_bit();
test_and_change_bit();

atomic_set();
set_bit();
clear_bit();
change_bit();

atomic_add();
atomic_sub();
atomic_inc();
atomic_dec();

test_and_set_bit_lock();
clear_bit_unlock();
__clear_bit_unlock();

LOCAL IRQ DISABLE
writew(ADDR, 3);
writew(DATA, y);
LOCAL IRQ ENABLE
<interrupt>
writew(ADDR, 4);
q = readw(DATA);
</interrupt>

STORE *ADDR = 3, STORE *ADDR = 4, STORE *DATA = y, q = LOAD *DATA

These are intended to talk to I/O space rather than memory space, but
 that's primarily a CPU-specific concept. The i386 and x86_64 processors do
 indeed have special I/O space access cycles and instructions, but many
 CPUs don't have such a concept.

 The PCI bus, amongst others, defines an I/O space concept which - on such
 CPUs as i386 and x86_64 - readily maps to the CPU's concept of I/O
 space.  However, it may also be mapped as a virtual I/O space in the CPU's
 memory map, particularly on those CPUs that don't support alternate I/O
 spaces.

 Accesses to this space may be fully synchronous (as on i386), but
 intermediary bridges (such as the PCI host bridge) may not fully honour
 that.

 They are guaranteed to be fully ordered with respect to each other.

 They are not guaranteed to be fully ordered with respect to other types of
 memory and I/O operation.

Whether these are guaranteed to be fully ordered and uncombined with
 respect to each other on the issuing CPU depends on the characteristics
 defined for the memory window through which they're accessing. On later
 i386 architecture machines, for example, this is controlled by way of the
 MTRR registers.

 Ordinarily, these will be guaranteed to be fully ordered and uncombined,
 provided they're not accessing a prefetchable device.

 However, intermediary hardware (such as a PCI bridge) may indulge in
 deferral if it so wishes; to flush a store, a load from the same location
 is preferred[*], but a load from the same device or from configuration
 space should suffice for PCI.

 [*] NOTE! attempting to load from the same location as was written to may
 	 cause a malfunction - consider the 16550 Rx/Tx serial registers for
 	 example.

 Used with prefetchable I/O memory, an mmiowb() barrier may be required to
 force stores to be ordered.

 Please refer to the PCI specification for more information on interactions
 between PCI transactions.

These are similar to readX(), but are not guaranteed to be ordered in any
 way. Be aware that there is no I/O read barrier available.

These will perform appropriately for the type of access they're actually
 doing, be it inX()/outX() or readX()/writeX().

<--- CPU --->         :       <----------- Memory ----------->
                          :
+--------+    +--------+  :   +--------+    +-----------+
|        |    |        |  :   |        |    |           |    +--------+
|  CPU   |    | Memory |  :   | CPU    |    |           |    |	      |
|  Core  |--->| Access |----->| Cache  |<-->|           |    |	      |
|        |    | Queue  |  :   |        |    |           |--->| Memory |
|        |    |        |  :   |        |    |           |    |	      |
+--------+    +--------+  :   +--------+    |           |    | 	      |
                          :                 | Cache     |    +--------+
                          :                 | Coherency |
                          :                 | Mechanism |    +--------+
+--------+    +--------+  :   +--------+    |           |    |	      |
|        |    |        |  :   |        |    |           |    |        |
|  CPU   |    | Memory |  :   | CPU    |    |           |--->| Device |
|  Core  |--->| Access |----->| Cache  |<-->|           |    | 	      |
|        |    | Queue  |  :   |        |    |           |    | 	      |
|        |    |        |  :   |        |    |           |    +--------+
+--------+    +--------+  :   +--------+    +-----------+
                          :
                          :

:
            :                          +--------+
            :      +---------+         |        |
+--------+  : +--->| Cache A |<------->|        |
|        |  : |    +---------+         |        |
|  CPU 1 |<---+                        |        |
|        |  : |    +---------+         |        |
+--------+  : +--->| Cache B |<------->|        |
            :      +---------+         |        |
            :                          | Memory |
            :      +---------+         | System |
+--------+  : +--->| Cache C |<------->|        |
|        |  : |    +---------+         |        |
|  CPU 2 |<---+                        |        |
|        |  : |    +---------+         |        |
+--------+  : +--->| Cache D |<------->|        |
            :      +---------+         |        |
            :                          +--------+
            :

CPU 1		CPU 2		COMMENT
===============	===============	=======================================
				u == 0, v == 1 and p == &u, q == &u
v = 2;
smp_wmb();			Make sure change to v is visible before
				 change to p
<A:modify v=2>			v is now in cache A exclusively
p = &v;
<B:modify p=&v>			p is now in cache B exclusively

CPU 1		CPU 2		COMMENT
===============	===============	=======================================
...
		q = p;
		x = *q;

CPU 1		CPU 2		COMMENT
===============	===============	=======================================
				u == 0, v == 1 and p == &u, q == &u
v = 2;
smp_wmb();
<A:modify v=2>	<C:busy>
		<C:queue v=2>
p = &v;		q = p;
		<D:request p>
<B:modify p=&v>	<D:commit p=&v>
	  	<D:read p>
		x = *q;
		<C:read *q>	Reads from v before v updated in cache
		<C:unbusy>
		<C:commit v=2>

CPU 1		CPU 2		COMMENT
===============	===============	=======================================
				u == 0, v == 1 and p == &u, q == &u
v = 2;
smp_wmb();
<A:modify v=2>	<C:busy>
		<C:queue v=2>
p = &v;		q = p;
		<D:request p>
<B:modify p=&v>	<D:commit p=&v>
	  	<D:read p>
		smp_read_barrier_depends()
		<C:unbusy>
		<C:commit v=2>
		x = *q;
		<C:read *q>	Reads from v after v updated in cache

a = *A;
*B = b;
c = *C;
d = *D;
*E = e;

LOAD *A, STORE *B, LOAD *C, LOAD *D, STORE *E.

LOAD *A, ..., LOAD {*C,*D}, STORE *E, STORE *B

(Where "LOAD {*C,*D}" is a combined load)

U = *A;
*A = V;
*A = W;
X = *A;
*A = Y;
Z = *A;

U == the original value of *A
X == W
Z == Y
*A == Y

U=LOAD *A, STORE *A=V, STORE *A=W, X=LOAD *A, STORE *A=Y, Z=LOAD *A

*A = V;
*A = W;

*A = W;

*A = Y;
Z = *A;

*A = Y;
Z = Y;

Documentation/circular-buffers.txt

Each device enumerated by ACPI includes ACPI-defined objects in the
ACPI Namespace that report the hardware resources the device could
occupy [_PRS], an object that reports the resources that are currently
used by the device [_CRS], and objects for configuring those resources
[_SRS].  The information is used by the Plug and Play OS (OSPM) to
configure the devices.

When OSPM enumerates a device, it calls _PRS to determine the resource
requirements of the device.  It may also call _CRS to find the current
resource settings for the device.  Using this information, the Plug and
Play system determines what resources the device should consume and
sets those resources by calling the device’s _SRS control method.

In ACPI, devices can consume resources (for example, legacy keyboards),
provide resources (for example, a proprietary PCI bridge), or do both.
Unless otherwise specified, resources for a device are assumed to be
taken from the nearest matching resource above the device in the device
hierarchy.

Extended Address Space Descriptor (.4)
  General Flags: Bit [0] Consumer/Producer:

    * 1 – This device consumes this resource
    * 0 – This device produces and consumes this resource

The MCFG table is only used to communicate the base addresses
corresponding to the PCI Segment Groups available to the system at
boot.

This control method appears under a host bridge object. When the _CBA
method appears under an active host bridge object, the operating system
evaluates this structure to identify the memory mapped configuration
base address corresponding to the PCI Segment Group for the bus number
range specified in _CRS method. An ACPI name space object that contains
the _CBA method must also contain a corresponding _SEG method.

==  ===========================
  0   Boot interrupt is enabled.
  1   Boot interrupt is disabled.
  ==  ===========================

- Intel® 6300ESB I/O Controller Hub (Document # 300641-004US)
5.7.3 Boot Interrupt
https://www.intel.com/content/dam/doc/datasheet/6300esb-io-controller-hub-datasheet.pdf

  - Intel® Xeon® Processor E5-1600/2400/2600/4600 v3 Product Families
Datasheet - Volume 2: Registers (Document # 330784-003)
6.6.41 cipintrc Coherent Interface Protocol Interrupt Control
https://www.intel.com/content/dam/www/public/us/en/documents/datasheets/xeon-e5-v3-datasheet-vol-2.pdf

- Intel® 6700PXH 64-bit PCI Hub (Document # 302628)
2.15.2 PCI Express Legacy INTx Support and Boot Interrupt
https://www.intel.com/content/dam/doc/datasheet/6700pxh-64-bit-pci-hub-datasheet.pdf

nvec = pci_alloc_irq_vectors(pdev, 1, nvec, PCI_IRQ_ALL_TYPES)
if (nvec < 0)
	goto out_err;

ret = pci_alloc_irq_vectors(pdev, nvec, nvec, PCI_IRQ_ALL_TYPES);
if (ret < 0)
	goto out_err;

ret = pci_alloc_irq_vectors(pdev, 1, 1, PCI_IRQ_ALL_TYPES);
if (ret < 0)
	goto out_err;

nvec = pci_alloc_irq_vectors(pdev, 1, nvec, PCI_IRQ_MSI | PCI_IRQ_MSIX);
if (nvec < 0)
	goto out_err;

Most device drivers have a per-device spinlock which is taken in the
interrupt handler.  With pin-based interrupts or a single MSI, it is not
necessary to disable interrupts (Linux guarantees the same interrupt will
not be re-entered).  If a device uses multiple interrupts, the driver
must disable interrupts while the lock is held.  If the device sends
a different interrupt, the driver will deadlock trying to recursively
acquire the spinlock.  Such deadlocks can be avoided by using
spin_lock_irqsave() or spin_lock_irq() which disable local interrupts
and acquire the lock (see Documentation/kernel-hacking/locking.rst).

How to tell whether MSI/MSI-X is enabled on a device
----------------------------------------------------

Using 'lspci -v' (as root) may show some devices with "MSI", "Message
Signalled Interrupts" or "MSI-X" capabilities.  Each of these capabilities
has an 'Enable' flag which is followed with either "+" (enabled)
or "-" (disabled).


MSI quirks
==========

Several PCI chipsets or devices are known not to support MSIs.
The PCI stack provides three ways to disable MSIs:

1. globally
2. on all devices behind a specific bridge
3. on a single device

Disabling MSIs globally
-----------------------

Some host chipsets simply don't support MSIs properly.  If we're
lucky, the manufacturer knows this and has indicated it in the ACPI
FADT table.  In this case, Linux automatically disables MSIs.
Some boards don't include this information in the table and so we have
to detect them ourselves.  The complete list of these is found near the
quirk_disable_all_msi() function in drivers/pci/quirks.c.

If you have a board which has problems with MSIs, you can pass pci=nomsi
on the kernel command line to disable MSIs on all devices.  It would be
in your best interests to report the problem to [email protected]
including a full 'lspci -v' so we can add the quirks to the kernel.

Disabling MSIs below a bridge
-----------------------------

Some PCI bridges are not able to route MSIs between buses properly.
In this case, MSIs must be disabled on all devices behind the bridge.

Some bridges allow you to enable MSIs by changing some bits in their
PCI configuration space (especially the Hypertransport chipsets such
as the nVidia nForce and Serverworks HT2000).  As with host chipsets,
Linux mostly knows about them and automatically enables MSIs if it can.
If you have a bridge unknown to Linux, you can enable
MSIs in configuration space using whatever method you know works, then
enable MSIs on that bridge by doing::

       echo 1 > /sys/bus/pci/devices/$bridge/msi_bus

where $bridge is the PCI address of the bridge you've enabled (eg
0000:00:0e.0).

To disable MSIs, echo 0 instead of 1.  Changing this value should be
done with caution as it could break interrupt handling for all devices
below this bridge.

Again, please notify [email protected] of any bridges that need
special handling.

Disabling MSIs on a single device
---------------------------------

Some devices are known to have faulty MSI implementations.  Usually this
is handled in the individual device driver, but occasionally it's necessary
to handle this with a quirk.  Some drivers have an option to disable use
of MSI.  While this is a convenient workaround for the driver author,
it is not good practice, and should not be emulated.

Finding why MSIs are disabled on a device
-----------------------------------------

From the above three sections, you can see that there are many reasons
why MSIs may not be enabled for a given device.  Your first step should
be to examine your dmesg carefully to determine whether MSIs are enabled
for your machine.  You should also check your .config to be sure you
have enabled CONFIG_PCI_MSI.

Then, 'lspci -t' gives the list of bridges above a device. Reading
`/sys/bus/pci/devices/*/msi_bus` will tell you whether MSIs are enabled (1)
or disabled (0).  If 0 is found in any of the msi_bus files belonging
to bridges between the PCI root and the device, MSIs are disabled.

It is also worth checking the device driver to see whether it supports MSIs.
For example, it may contain calls to pci_alloc_irq_vectors() with the
PCI_IRQ_MSI or PCI_IRQ_MSIX flags.


List of device drivers MSI(-X) APIs
===================================

The PCI/MSI subsystem has a dedicated C file for its exported device driver
APIs — `drivers/pci/msi/api.c`. The following functions are exported:

.. kernel-doc:: drivers/pci/msi/api.c
   :export:

---

### Documentation PCI Pci Error Recovery (`Documentation/PCI/pci-error-recovery.rst`)

.. SPDX-License-Identifier: GPL-2.0

==================
PCI Error Recovery
==================


:Authors: - Linas Vepstas <[email protected]>
          - Richard Lary <[email protected]>
          - Mike Mason <[email protected]>


Many PCI bus controllers are able to detect a variety of hardware
PCI errors on the bus, such as parity errors on the data and address
buses, as well as SERR and PERR errors.  Some of the more advanced
chipsets are able to deal with these errors; these include PCIe chipsets,
and the PCI-host bridges found on IBM Power4, Power5 and Power6-based
pSeries boxes. A typical action taken is to disconnect the affected device,
halting all I/O to it.  The goal of a disconnection is to avoid system
corruption; for example, to halt system memory corruption due to DMAs
to "wild" addresses. Typically, a reconnection mechanism is also
offered, so that the affected PCI device(s) are reset and put back
into working condition. The reset phase requires coordination
between the affected device drivers and the PCI controller chip.
This document describes a generic API for notifying device drivers
of a bus disconnection, and then performing error recovery.
This API is currently implemented in the 2.6.16 and later kernels.

Reporting and recovery is performed in several steps. First, when
a PCI hardware error has resulted in a bus disconnect, that event
is reported as soon as possible to all affected device drivers,
including multiple instances of a device driver on multi-function
cards. This allows device drivers to avoid deadlocking in spinloops,
waiting for some i/o-space register to change, when it never will.
It also gives the drivers a chance to defer incoming I/O as
needed.

Next, recovery is performed in several stages. Most of the complexity
is forced by the need to handle multi-function devices, that is,
devices that have multiple device drivers associated with them.
In the first stage, each driver is allowed to indicate what type
of reset it desires, the choices being a simple re-enabling of I/O
or requesting a slot reset.

If any driver requests a slot reset, that is what will be done.

After a reset and/or a re-enabling of I/O, all drivers are
again notified, so that they may then perform any device setup/config
that may be required.  After these have all completed, a final
"resume normal operations" event is sent out.

The biggest reason for choosing a kernel-based implementation rather
than a user-space implementation was the need to deal with bus
disconnects of PCI devices attached to storage media, and, in particular,
disconnects from devices holding the root file system.  If the root
file system is disconnected, a user-space mechanism would have to go
through a large number of contortions to complete recovery. Almost all
of the current Linux file systems are not tolerant of disconnection
from/reconnection to their underlying block device. By contrast,
bus errors are easy to manage in the device driver. Indeed, most
device drivers already handle very similar recovery procedures;
for example, the SCSI-generic layer already provides significant
mechanisms for dealing with SCSI bus errors and SCSI bus resets.


Detailed Design
===============

Design and implementation details below, based on a chain of
public email discussions with Ben Herrenschmidt, circa 5 April 2005.

The error recovery API support is exposed to the driver in the form of
a structure of function pointers pointed to by a new field in struct
pci_driver. A driver that fails to provide the structure is "non-aware",
and the actual recovery steps taken are platform dependent.  The
arch/powerpc implementation will simulate a PCI hotplug remove/add.

This structure has the form::

	struct pci_error_handlers
	{
		int (*error_detected)(struct pci_dev *dev, pci_channel_state_t);
		int (*mmio_enabled)(struct pci_dev *dev);
		int (*slot_reset)(struct pci_dev *dev);
		void (*resume)(struct pci_dev *dev);
		void (*cor_error_detected)(struct pci_dev *dev);
	};

The possible channel states are::

	typedef enum {
		pci_channel_io_normal,  /* I/O channel is in normal state */
		pci_channel_io_frozen,  /* I/O to channel is blocked */
		pci_channel_io_perm_failure, /* PCI card is dead */
	} pci_channel_state_t;

Possible return values are::

	enum pci_ers_result {
		PCI_ERS_RESULT_NONE,        /* no result/none/not supported in device driver */
		PCI_ERS_RESULT_CAN_RECOVER, /* Device driver can recover without slot reset */
		PCI_ERS_RESULT_NEED_RESET,  /* Device driver wants slot to be reset. */
		PCI_ERS_RESULT_DISCONNECT,  /* Device has completely failed, is unrecoverable */
		PCI_ERS_RESULT_RECOVERED,   /* Device driver is fully recovered and operational */
	};

A driver does not have to implement all of these callbacks; however,
if it implements any, it must implement error_detected(). If a callback
is not implemented, the corresponding feature is considered unsupported.
For example, if mmio_enabled() and resume() aren't there, then it
is assumed that the driver does not need these callbacks
for recovery.  Typically a driver will want to know about
a slot_reset().

The actual steps taken by a platform to recover from a PCI error
event will be platform-dependent, but will follow the general
sequence described below.

STEP 0: Error Event
-------------------
A PCI bus error is detected by the PCI hardware.  On powerpc, the slot
is isolated, in that all I/O is blocked: all reads return 0xffffffff,
all writes are ignored.

Similarly, on platforms supporting Downstream Port Containment
(PCIe r7.0 sec 6.2.11), the link to the sub-hierarchy with the
faulting device is disabled. Any device in the sub-hierarchy
becomes inaccessible.

STEP 1: Notification
--------------------
Platform calls the error_detected() callback on every instance of
every driver affected by the error.

At this point, the device might not be accessible anymore, depending on
the platform (the slot will be isolated on powerpc). The driver may
already have "noticed" the error because of a failing I/O, but this
is the proper "synchronization point", that is, it gives the driver
a chance to cleanup, waiting for pending stuff (timers, whatever, etc...)
to complete; it can take semaphores, schedule, etc... everything but
touch the device. Within this function and after it returns, the driver
shouldn't do any new IOs. Called in task context. This is sort of a
"quiesce" point. See note about interrupts at the end of this doc.

All drivers participating in this system must implement this call.
The driver must return one of the following result codes:

  - PCI_ERS_RESULT_RECOVERED
      Driver returns this if it thinks the device is usable despite
      the error and does not need further intervention.
  - PCI_ERS_RESULT_CAN_RECOVER
      Driver returns this if it thinks it might be able to recover
      the HW by just banging IOs or if it wants to be given
      a chance to extract some diagnostic information (see
      mmio_enable, below).
  - PCI_ERS_RESULT_NEED_RESET
      Driver returns this if it can't recover without a
      slot reset.
  - PCI_ERS_RESULT_DISCONNECT
      Driver returns this if it doesn't want to recover at all.

The next step taken will depend on the result codes returned by the
drivers.

If all drivers on the segment/slot return PCI_ERS_RESULT_CAN_RECOVER,
then the platform should re-enable IOs on the slot (or do nothing in
particular, if the platform doesn't isolate slots), and recovery
proceeds to STEP 2 (MMIO Enable).

If any driver requested a slot reset (by returning PCI_ERS_RESULT_NEED_RESET),
then recovery proceeds to STEP 4 (Slot Reset).

If the platform is unable to recover the slot, the next step
is STEP 6 (Permanent Failure).

.. note::

   The current powerpc implementation assumes that a device driver will
   *not* schedule or semaphore in this routine; the current powerpc
   implementation uses one kernel thread to notify all devices;
   thus, if one device sleeps/schedules, all devices are affected.
   Doing better requires complex multi-threaded logic in the error
   recovery implementation (e.g. waiting for all notification threads
   to "join" before proceeding with recovery.)  This seems excessively
   complex and not worth implementing.

   The current powerpc implementation doesn't much care if the device
   attempts I/O at this point, or not.  I/Os will fail, returning
   a value of 0xff on read, and writes will be dropped. If more than
   EEH_MAX_FAILS I/Os are attempted to a frozen adapter, EEH
   assumes that the device driver has gone into an infinite loop
   and prints an error to syslog.  A reboot is then required to
   get the device working again.

STEP 2: MMIO Enabled
--------------------
The platform re-enables MMIO to the device (but typically not the
DMA), and then calls the mmio_enabled() callback on all affected
device drivers.

This is the "early recovery" call. IOs are allowed again, but DMA is
not, with some restrictions. This is NOT a callback for the driver to
start operations again, only to peek/poke at the device, extract diagnostic
information, if any, and eventually do things like trigger a device local
reset or some such, but not restart operations. This callback is made if
all drivers on a segment agree that they can try to recover and if no automatic
link reset was performed by the HW. If the platform can't just re-enable IOs
without a slot reset or a link reset, it will not call this callback, and
instead will have gone directly to STEP 3 (Link Reset) or STEP 4 (Slot Reset).

.. note::

   On platforms supporting Advanced Error Reporting (PCIe r7.0 sec 6.2),
   the faulting device may already be accessible in STEP 1 (Notification).
   Drivers should nevertheless defer accesses to STEP 2 (MMIO Enabled)
   to be compatible with EEH on powerpc and with s390 (where devices are
   inaccessible until STEP 2).

   On platforms supporting Downstream Port Containment, the link to the
   sub-hierarchy with the faulting device is re-enabled in STEP 3 (Link
   Reset). Hence devices in the sub-hierarchy are inaccessible until
   STEP 4 (Slot Reset).

   For errors such as Surprise Down (PCIe r7.0 sec 6.2.7), the device
   may not even be accessible in STEP 4 (Slot Reset). Drivers can detect
   accessibility by checking whether reads from the device return all 1's
   (PCI_POSSIBLE_ERROR()).

.. note::

   The following is proposed; no platform implements this yet:
   Proposal: All I/Os should be done _synchronously_ from within
   this callback, errors triggered by them will be returned via
   the normal pci_check_whatever() API, no new error_detected()
   callback will be issued due to an error happening here. However,
   such an error might cause IOs to be re-blocked for the whole
   segment, and thus invalidate the recovery that other devices
   on the same segment might have done, forcing the whole segment
   into one of the next states, that is, link reset or slot reset.

The driver should return one of the following result codes:
  - PCI_ERS_RESULT_RECOVERED
      Driver returns this if it thinks the device is fully
      functional and thinks it is ready to start
      normal driver operations again. There is no
      guarantee that the driver will actually be
      allowed to proceed, as another driver on the
      same segment might have failed and thus triggered a
      slot reset on platforms that support it.

  - PCI_ERS_RESULT_NEED_RESET
      Driver returns this if it thinks the device is not
      recoverable in its current state and it needs a slot
      reset to proceed.

  - PCI_ERS_RESULT_DISCONNECT
      Same as above. Total failure, no recovery even after
      reset driver dead. (To be defined more precisely)

The next step taken depends on the results returned by the drivers.
If all drivers returned PCI_ERS_RESULT_RECOVERED, then the platform
proceeds to either STEP 3 (Link Reset) or to STEP 5 (Resume Operations).

If any driver returned PCI_ERS_RESULT_NEED_RESET, then the platform
proceeds to STEP 4 (Slot Reset)

STEP 3: Link Reset
------------------
The platform resets the link.  This is a PCIe specific step
and is done whenever a fatal error has been detected that can be
"solved" by resetting the link.

STEP 4: Slot Reset
------------------

In response to a return value of PCI_ERS_RESULT_NEED_RESET, the
platform will perform a slot reset on the requesting PCI device(s).
The actual steps taken by a platform to perform a slot reset
will be platform-dependent. Upon completion of slot reset, the
platform will call the device slot_reset() callback.

Powerpc platforms implement two levels of slot reset:
soft reset(default) and fundamental(optional) reset.

Powerpc soft reset consists of asserting the adapter #RST line and then
restoring the PCI BARs and PCI configuration header to a state
that is equivalent to what it would be after a fresh system
power-on followed by power-on BIOS/system firmware initialization.
Soft reset is also known as hot-reset.

Powerpc fundamental reset is supported by PCIe cards only
and results in device's state machines, hardware logic, port states and
configuration registers to initialize to their default conditions.

For most PCI devices, a soft reset will be sufficient for recovery.
Optional fundamental reset is provided to support a limited number
of PCIe devices for which a soft reset is not sufficient
for recovery.

If the platform supports PCI hotplug, then the reset might be
performed by toggling the slot electrical power off/on.

It is important for the platform to restore the PCI config space
to the "fresh poweron" state, rather than the "last state". After
a slot reset, the device driver will almost always use its standard
device initialization routines, and an unusual config space setup
may result in hung devices, kernel panics, or silent data corruption.

This call gives drivers the chance to re-initialize the hardware
(re-download firmware, etc.).  At this point, the driver may assume
that the card is in a fresh state and is fully functional. The slot
is unfrozen and the driver has full access to PCI config space,
memory mapped I/O space and DMA. Interrupts (Legacy, MSI, or MSI-X)
will also be available.

Drivers should not restart normal I/O processing operations
at this point.  If all device drivers report success on this
callback, the platform will call resume() to complete the sequence,
and let the driver restart normal I/O processing.

A driver can still return a critical failure for this function if
it can't get the device operational after reset.  If the platform
previously tried a soft reset, it might now try a hard reset (power
cycle) and then call slot_reset() again.  If the device still can't
be recovered, there is nothing more that can be done;  the platform
will typically report a "permanent failure" in such a case.  The
device will be considered "dead" in this case.

Drivers for multi-function cards will need to coordinate among
themselves as to which driver instance will perform any "one-shot"
or global device initialization. For example, the Symbios sym53cxx2
driver performs device init only from PCI function 0::

	+       if (PCI_FUNC(pdev->devfn) == 0)
	+               sym_reset_scsi_bus(np, 0);

Result codes:
	- PCI_ERS_RESULT_DISCONNECT
	  Same as above.

Drivers for PCIe cards that require a fundamental reset must
set the needs_freset bit in the pci_dev structure in their probe function.
For example, the QLogic qla2xxx driver sets the needs_freset bit for certain
PCI card types::

	+	/* Set EEH reset type to fundamental if required by hba  */
	+	if (IS_QLA24XX(ha) || IS_QLA25XX(ha) || IS_QLA81XX(ha))
	+		pdev->needs_freset = 1;
	+

Platform proceeds either to STEP 5 (Resume Operations) or STEP 6 (Permanent
Failure).

.. note::

   The current powerpc implementation does not try a power-cycle
   reset if the driver returned PCI_ERS_RESULT_DISCONNECT.
   However, it probably should.


STEP 5: Resume Operations
-------------------------
The platform will call the resume() callback on all affected device
drivers if all drivers on the segment have returned
PCI_ERS_RESULT_RECOVERED from one of the 3 previous callbacks.
The goal of this callback is to tell the driver to restart activity,
that everything is back and running. This callback does not return
a result code.

At this point, if a new error happens, the platform will restart
a new error recovery sequence.

STEP 6: Permanent Failure
-------------------------
A "permanent failure" has occurred, and the platform cannot recover
the device.  The platform will call error_detected() with a
pci_channel_state_t value of pci_channel_io_perm_failure.

The device driver should, at this point, assume the worst. It should
cancel all pending I/O, refuse all new I/O, returning -EIO to
higher layers. The device driver should then clean up all of its
memory and remove itself from kernel operations, much as it would
during system shutdown.

The platform will typically notify the system operator of the
permanent failure in some way.  If the device is hotplug-capable,
the operator will probably want to remove and replace the device.
Note, however, not all failures are truly "permanent". Some are
caused by over-heating, some by a poorly seated card. Many
PCI error events are caused by software bugs, e.g. DMAs to
wild addresses or bogus split transactions due to programming
errors. See the discussion in Documentation/arch/powerpc/eeh-pci-error-recovery.rst
for additional detail on real-life experience of the causes of
software errors.


Conclusion; General Remarks
---------------------------
The way the callbacks are called is platform policy. A platform with
no slot reset capability may want to just "ignore" drivers that can't
recover (disconnect them) and try to let other cards on the same segment
recover. Keep in mind that in most real life cases, though, there will
be only one driver per segment.

Now, a note about interrupts. If you get an interrupt and your
device is dead or has been isolated, there is a problem :)
The current policy is to turn this into a platform policy.
That is, the recovery API only requires that:

 - There is no guarantee that interrupt delivery can proceed from any
   device on the segment starting from the error detection and until the
   slot_reset callback is called, at which point interrupts are expected
   to be fully operational.

 - There is no guarantee that interrupt delivery is stopped, that is,
   a driver that gets an interrupt after detecting an error, or that detects
   an error within the interrupt handler such that it prevents proper
   ack'ing of the interrupt (and thus removal of the source) should just
   return IRQ_NOTHANDLED. It's up to the platform to deal with that
   condition, typically by masking the IRQ source during the duration of
   the error handling. It is expected that the platform "knows" which
   interrupts are routed to error-management capable slots and can deal
   with temporarily disabling that IRQ number during error processing (this
   isn't terribly complex). That means some IRQ latency for other devices
   sharing the interrupt, but there is simply no other way. High end
   platforms aren't supposed to share interrupts between many devices
   anyway :)

.. note::

   Implementation details for the powerpc platform are discussed in
   the file Documentation/arch/powerpc/eeh-pci-error-recovery.rst

   As of this writing, there is a growing list of device drivers with
   patches implementing error recovery. Not all of these patches are in
   mainline yet. These may be used as "examples":

   - drivers/scsi/ipr
   - drivers/scsi/sym53c8xx_2
   - drivers/scsi/qla2xxx
   - drivers/scsi/lpfc
   - drivers/next/bnx2.c
   - drivers/next/e100.c
   - drivers/net/e1000
   - drivers/net/e1000e
   - drivers/net/ixgbe
   - drivers/net/cxgb3
   - drivers/net/s2io.c

   The cor_error_detected() callback is invoked in handle_error_source() when
   the error severity is "correctable". The callback is optional and allows
   additional logging to be done if desired. See example:

   - drivers/cxl/pci.c

The End
-------

---

### Documentation PCI Pci Iov Howto (`Documentation/PCI/pci-iov-howto.rst`)

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

====================================
PCI Express I/O Virtualization Howto
====================================

:Copyright: |copy| 2009 Intel Corporation
:Authors: - Yu Zhao <[email protected]>
          - Donald Dutile <[email protected]>

Overview
========

What is SR-IOV
--------------

Single Root I/O Virtualization (SR-IOV) is a PCI Express Extended
capability which makes one physical device appear as multiple virtual
devices. The physical device is referred to as Physical Function (PF)
while the virtual devices are referred to as Virtual Functions (VF).
Allocation of the VF can be dynamically controlled by the PF via
registers encapsulated in the capability. By default, this feature is
not enabled and the PF behaves as traditional PCIe device. Once it's
turned on, each VF's PCI configuration space can be accessed by its own
Bus, Device and Function Number (Routing ID). And each VF also has PCI
Memory Space, which is used to map its register set. VF device driver
operates on the register set so it can be functional and appear as a
real existing PCI device.

User Guide
==========

How can I enable SR-IOV capability
----------------------------------

Multiple methods are available for SR-IOV enablement.
In the first method, the device driver (PF driver) will control the
enabling and disabling of the capability via API provided by SR-IOV core.
If the hardware has SR-IOV capability, loading its PF driver would
enable it and all VFs associated with the PF.  Some PF drivers require
a module parameter to be set to determine the number of VFs to enable.
In the second method, a write to the sysfs file sriov_numvfs will
enable and disable the VFs associated with a PCIe PF.  This method
enables per-PF, VF enable/disable values versus the first method,
which applies to all PFs of the same device.  Additionally, the
PCI SRIOV core support ensures that enable/disable operations are
valid to reduce duplication in multiple drivers for the same
checks, e.g., check numvfs == 0 if enabling VFs, ensure
numvfs <= totalvfs.
The second method is the recommended method for new/future VF devices.

How can I use the Virtual Functions
-----------------------------------

The VF is treated as hot-plugged PCI devices in the kernel, so they
should be able to work in the same way as real PCI devices. The VF
requires device driver that is same as a normal PCI device's.

Developer Guide
===============

SR-IOV API
----------

To enable SR-IOV capability:

(a) For the first method, in the driver::

	int pci_enable_sriov(struct pci_dev *dev, int nr_virtfn);

'nr_virtfn' is number of VFs to be enabled.

(b) For the second method, from sysfs::

	echo 'nr_virtfn' > \
        /sys/bus/pci/devices/<DOMAIN:BUS:DEVICE.FUNCTION>/sriov_numvfs

To disable SR-IOV capability:

(a) For the first method, in the driver::

	void pci_disable_sriov(struct pci_dev *dev);

(b) For the second method, from sysfs::

	echo  0 > \
        /sys/bus/pci/devices/<DOMAIN:BUS:DEVICE.FUNCTION>/sriov_numvfs

To enable auto probing VFs by a compatible driver on the host, run
command below before enabling SR-IOV capabilities. This is the
default behavior.
::

	echo 1 > \
        /sys/bus/pci/devices/<DOMAIN:BUS:DEVICE.FUNCTION>/sriov_drivers_autoprobe

To disable auto probing VFs by a compatible driver on the host, run
command below before enabling SR-IOV capabilities. Updating this
entry will not affect VFs which are already probed.
::

	echo  0 > \
        /sys/bus/pci/devices/<DOMAIN:BUS:DEVICE.FUNCTION>/sriov_drivers_autoprobe

Usage example
-------------

Following piece of code illustrates the usage of the SR-IOV API.
::

	static int dev_probe(struct pci_dev *dev, const struct pci_device_id *id)
	{
		pci_enable_sriov(dev, NR_VIRTFN);

		...

		return 0;
	}

	static void dev_remove(struct pci_dev *dev)
	{
		pci_disable_sriov(dev);

		...
	}

	static int dev_suspend(struct device *dev)
	{
		...

		return 0;
	}

	static int dev_resume(struct device *dev)
	{
		...

		return 0;
	}

	static void dev_shutdown(struct pci_dev *dev)
	{
		...
	}

	static int dev_sriov_configure(struct pci_dev *dev, int numvfs)
	{
		if (numvfs > 0) {
			...
			pci_enable_sriov(dev, numvfs);
			...
			return numvfs;
		}
		if (numvfs == 0) {
			....
			pci_disable_sriov(dev);
			...
			return 0;
		}
	}

	static struct pci_driver dev_driver = {
		.name =		"SR-IOV Physical Function driver",
		.id_table =	dev_id_table,
		.probe =	dev_probe,
		.remove =	dev_remove,
		.driver.pm =	&dev_pm_ops,
		.shutdown =	dev_shutdown,
		.sriov_configure = dev_sriov_configure,
	};

---

### Documentation PCI Pci (`Documentation/PCI/pci.rst`)

.. SPDX-License-Identifier: GPL-2.0

==============================
How To Write Linux PCI Drivers
==============================

:Authors: - Martin Mares <[email protected]>
          - Grant Grundler <[email protected]>

The world of PCI is vast and full of (mostly unpleasant) surprises.
Since each CPU architecture implements different chip-sets and PCI devices
have different requirements (erm, "features"), the result is the PCI support
in the Linux kernel is not as trivial as one would wish. This short paper
tries to introduce all potential driver authors to Linux APIs for
PCI device drivers.

A more complete resource is the third edition of "Linux Device Drivers"
by Jonathan Corbet, Alessandro Rubini, and Greg Kroah-Hartman.
LDD3 is available for free (under Creative Commons License) from:
https://lwn.net/Kernel/LDD3/.

However, keep in mind that all documents are subject to "bit rot".
Refer to the source code if things are not working as described here.

Please send questions/comments/patches about Linux PCI API to the
"Linux PCI" <[email protected]> mailing list.


Structure of PCI drivers
========================
PCI drivers "discover" PCI devices in a system via pci_register_driver().
Actually, it's the other way around. When the PCI generic code discovers
a new device, the driver with a matching "description" will be notified.
Details on this below.

pci_register_driver() leaves most of the probing for devices to
the PCI layer and supports online insertion/removal of devices [thus
supporting hot-pluggable PCI, CardBus, and Express-Card in a single driver].
pci_register_driver() call requires passing in a table of function
pointers and thus dictates the high level structure of a driver.

Once the driver knows about a PCI device and takes ownership, the
driver generally needs to perform the following initialization:

  - Enable the device
  - Request MMIO/IOP resources
  - Set the DMA mask size (for both coherent and streaming DMA)
  - Allocate and initialize shared control data (pci_allocate_coherent())
  - Access device configuration space (if needed)
  - Register IRQ handler (request_irq())
  - Initialize non-PCI (i.e. LAN/SCSI/etc parts of the chip)
  - Enable DMA/processing engines

When done using the device, and perhaps the module needs to be unloaded,
the driver needs to take the following steps:

  - Disable the device from generating IRQs
  - Release the IRQ (free_irq())
  - Stop all DMA activity
  - Release DMA buffers (both streaming and coherent)
  - Unregister from other subsystems (e.g. scsi or netdev)
  - Release MMIO/IOP resources
  - Disable the device

Most of these topics are covered in the following sections.
For the rest look at LDD3 or <linux/pci.h> .

If the PCI subsystem is not configured (CONFIG_PCI is not set), most of
the PCI functions described below are defined as inline functions either
completely empty or just returning an appropriate error codes to avoid
lots of ifdefs in the drivers.


pci_register_driver() call
==========================

PCI device drivers call ``pci_register_driver()`` during their
initialization with a pointer to a structure describing the driver
(``struct pci_driver``):

.. kernel-doc:: include/linux/pci.h
   :functions: pci_driver

The ID table is an array of ``struct pci_device_id`` entries ending with an
all-zero entry.  Definitions with static const are generally preferred.

.. kernel-doc:: include/linux/mod_devicetable.h
   :functions: pci_device_id

Most drivers only need ``PCI_DEVICE()`` or ``PCI_DEVICE_CLASS()`` to set up
a pci_device_id table.

New PCI IDs may be added to a device driver pci_ids table at runtime
as shown below::

  echo "vendor device subvendor subdevice class class_mask driver_data" > \
  /sys/bus/pci/drivers/{driver}/new_id

All fields are passed in as hexadecimal values (no leading 0x).
The vendor and device fields are mandatory, the others are optional. Users
need pass only as many optional fields as necessary:

  - subvendor and subdevice fields default to PCI_ANY_ID (FFFFFFFF)
  - class and classmask fields default to 0
  - driver_data defaults to 0UL.
  - override_only field defaults to 0.

Note that driver_data must match the value used by any of the pci_device_id
entries defined in the driver. This makes the driver_data field mandatory
if all the pci_device_id entries have a non-zero driver_data value.

Once added, the driver probe routine will be invoked for any unclaimed
PCI devices listed in its (newly updated) pci_ids list.

When the driver exits, it just calls pci_unregister_driver() and the PCI layer
automatically calls the remove hook for all devices handled by the driver.


"Attributes" for driver functions/data
--------------------------------------

Please mark the initialization and cleanup functions where appropriate
(the corresponding macros are defined in <linux/init.h>):

	======		=================================================
	__init		Initialization code. Thrown away after the driver
			initializes.
	__exit		Exit code. Ignored for non-modular drivers.
	======		=================================================

Tips on when/where to use the above attributes:
	- The module_init()/module_exit() functions (and all
	  initialization functions called _only_ from these)
	  should be marked __init/__exit.

	- Do not mark the struct pci_driver.

	- Do NOT mark a function if you are not sure which mark to use.
	  Better to not mark the function than mark the function wrong.


How to find PCI devices manually
================================

PCI drivers should have a really good reason for not using the
pci_register_driver() interface to search for PCI devices.
The main reason PCI devices are controlled by multiple drivers
is because one PCI device implements several different HW services.
E.g. combined serial/parallel port/floppy controller.

A manual search may be performed using the following constructs:

Searching by vendor and device ID::

	struct pci_dev *dev = NULL;
	while (dev = pci_get_device(VENDOR_ID, DEVICE_ID, dev))
		configure_device(dev);

Searching by class ID (iterate in a similar way)::

	pci_get_class(CLASS_ID, dev)

Searching by both vendor/device and subsystem vendor/device ID::

	pci_get_subsys(VENDOR_ID,DEVICE_ID, SUBSYS_VENDOR_ID, SUBSYS_DEVICE_ID, dev).

You can use the constant PCI_ANY_ID as a wildcard replacement for
VENDOR_ID or DEVICE_ID.  This allows searching for any device from a
specific vendor, for example.

These functions are hotplug-safe. They increment the reference count on
the pci_dev that they return. You must eventually (possibly at module unload)
decrement the reference count on these devices by calling pci_dev_put().


Device Initialization Steps
===========================

As noted in the introduction, most PCI drivers need the following steps
for device initialization:

  - Enable the device
  - Request MMIO/IOP resources
  - Set the DMA mask size (for both coherent and streaming DMA)
  - Allocate and initialize shared control data (pci_allocate_coherent())
  - Access device configuration space (if needed)
  - Register IRQ handler (request_irq())
  - Initialize non-PCI (i.e. LAN/SCSI/etc parts of the chip)
  - Enable DMA/processing engines.

The driver can access PCI config space registers at any time.
(Well, almost. When running BIST, config space can go away...but
that will just result in a PCI Bus Master Abort and config reads
will return garbage).


Enable the PCI device
---------------------
Before touching any device registers, the driver needs to enable
the PCI device by calling pci_enable_device(). This will:

  - wake up the device if it was in suspended state,
  - allocate I/O and memory regions of the device (if BIOS did not),
  - allocate an IRQ (if BIOS did not).

.. note::
   pci_enable_device() can fail! Check the return value.

.. warning::
   OS BUG: we don't check resource allocations before enabling those
   resources. The sequence would make more sense if we called
   pci_request_resources() before calling pci_enable_device().
   Currently, the device drivers can't detect the bug when two
   devices have been allocated the same range. This is not a common
   problem and unlikely to get fixed soon.

   This has been discussed before but not changed as of 2.6.19:
   https://lore.kernel.org/r/[email protected]/


pci_set_master() will enable DMA by setting the bus master bit
in the PCI_COMMAND register. It also fixes the latency timer value if
it's set to something bogus by the BIOS.  pci_clear_master() will
disable DMA by clearing the bus master bit.

If the PCI device can use the PCI Memory-Write-Invalidate transaction,
call pci_set_mwi().  This enables the PCI_COMMAND bit for Mem-Wr-Inval
and also ensures that the cache line size register is set correctly.
Check the return value of pci_set_mwi() as not all architectures
or chip-sets may support Memory-Write-Invalidate.  Alternatively,
if Mem-Wr-Inval would be nice to have but is not required, call
pci_try_set_mwi() to have the system do its best effort at enabling
Mem-Wr-Inval.


Request MMIO/IOP resources
--------------------------
Memory (MMIO), and I/O port addresses should NOT be read directly
from the PCI device config space. Use the values in the pci_dev structure
as the PCI "bus address" might have been remapped to a "host physical"
address by the arch/chip-set specific kernel support.

See Documentation/driver-api/io-mapping.rst for how to access device registers
or device memory.

The device driver needs to call pci_request_region() to verify
no other device is already using the same address resource.
Conversely, drivers should call pci_release_region() AFTER
calling pci_disable_device().
The idea is to prevent two devices colliding on the same address range.

.. tip::
   See OS BUG comment above. Currently (2.6.19), The driver can only
   determine MMIO and IO Port resource availability _after_ calling
   pci_enable_device().

Generic flavors of pci_request_region() are request_mem_region()
(for MMIO ranges) and request_region() (for IO Port ranges).
Use these for address resources that are not described by "normal" PCI
BARs.

Also see pci_request_selected_regions() below.


Set the DMA mask size
---------------------
.. note::
   If anything below doesn't make sense, please refer to
   Documentation/core-api/dma-api.rst. This section is just a reminder that
   drivers need to indicate DMA capabilities of the device and is not
   an authoritative source for DMA interfaces.

While all drivers should explicitly indicate the DMA capability
(e.g. 32 or 64 bit) of the PCI bus master, devices with more than
32-bit bus master capability for streaming data need the driver
to "register" this capability by calling dma_set_mask() with
appropriate parameters.  In general this allows more efficient DMA
on systems where System RAM exists above 4G _physical_ address.

Drivers for all PCI-X and PCIe compliant devices must call
dma_set_mask() as they are 64-bit DMA devices.

Similarly, drivers must also "register" this capability if the device
can directly address "coherent memory" in System RAM above 4G physical
address by calling dma_set_coherent_mask().
Again, this includes drivers for all PCI-X and PCIe compliant devices.
Many 64-bit "PCI" devices (before PCI-X) and some PCI-X devices are
64-bit DMA capable for payload ("streaming") data but not control
("coherent") data.


Setup shared control data
-------------------------
Once the DMA masks are set, the driver can allocate "coherent" (a.k.a. shared)
memory.  See Documentation/core-api/dma-api.rst for a full description of
the DMA APIs. This section is just a reminder that it needs to be done
before enabling DMA on the device.


Initialize device registers
---------------------------
Some drivers will need specific "capability" fields programmed
or other "vendor specific" register initialized or reset.
E.g. clearing pending interrupts.


Register IRQ handler
--------------------
While calling request_irq() is the last step described here,
this is often just another intermediate step to initialize a device.
This step can often be deferred until the device is opened for use.

All interrupt handlers for IRQ lines should be registered with IRQF_SHARED
and use the devid to map IRQs to devices (remember that all PCI IRQ lines
can be shared).

request_irq() will associate an interrupt handler and device handle
with an interrupt number. Historically interrupt numbers represent
IRQ lines which run from the PCI device to the Interrupt controller.
With MSI and MSI-X (more below) the interrupt number is a CPU "vector".

request_irq() also enables the interrupt. Make sure the device is
quiesced and does not have any interrupts pending before registering
the interrupt handler.

MSI and MSI-X are PCI capabilities. Both are "Message Signaled Interrupts"
which deliver interrupts to the CPU via a DMA write to a Local APIC.
The fundamental difference between MSI and MSI-X is how multiple
"vectors" get allocated. MSI requires contiguous blocks of vectors
while MSI-X can allocate several individual ones.

MSI capability can be enabled by calling pci_alloc_irq_vectors() with the
PCI_IRQ_MSI and/or PCI_IRQ_MSIX flags before calling request_irq(). This
causes the PCI support to program CPU vector data into the PCI device
capability registers. Many architectures, chip-sets, or BIOSes do NOT
support MSI or MSI-X and a call to pci_alloc_irq_vectors with just
the PCI_IRQ_MSI and PCI_IRQ_MSIX flags will fail, so try to always
specify PCI_IRQ_INTX as well.

Drivers that have different interrupt handlers for MSI/MSI-X and
legacy INTx should chose the right one based on the msi_enabled
and msix_enabled flags in the pci_dev structure after calling
pci_alloc_irq_vectors.

There are (at least) two really good reasons for using MSI:

1) MSI is an exclusive interrupt vector by definition.
   This means the interrupt handler doesn't have to verify
   its device caused the interrupt.

2) MSI avoids DMA/IRQ race conditions. DMA to host memory is guaranteed
   to be visible to the host CPU(s) when the MSI is delivered. This
   is important for both data coherency and avoiding stale control data.
   This guarantee allows the driver to omit MMIO reads to flush
   the DMA stream.

See drivers/infiniband/hw/mthca/ or drivers/net/tg3.c for examples
of MSI/MSI-X usage.


PCI device shutdown
===================

When a PCI device driver is being unloaded, most of the following
steps need to be performed:

  - Disable the device from generating IRQs
  - Release the IRQ (free_irq())
  - Stop all DMA activity
  - Release DMA buffers (both streaming and coherent)
  - Unregister from other subsystems (e.g. scsi or netdev)
  - Disable device from responding to MMIO/IO Port addresses
  - Release MMIO/IO Port resource(s)


Stop IRQs on the device
-----------------------
How to do this is chip/device specific. If it's not done, it opens
the possibility of a "screaming interrupt" if (and only if)
the IRQ is shared with another device.

When the shared IRQ handler is "unhooked", the remaining devices
using the same IRQ line will still need the IRQ enabled. Thus if the
"unhooked" device asserts IRQ line, the system will respond assuming
it was one of the remaining devices asserted the IRQ line. Since none
of the other devices will handle the IRQ, the system will "hang" until
it decides the IRQ isn't going to get handled and masks the IRQ (100,000
iterations later). Once the shared IRQ is masked, the remaining devices
will stop functioning properly. Not a nice situation.

This is another reason to use MSI or MSI-X if it's available.
MSI and MSI-X are defined to be exclusive interrupts and thus
are not susceptible to the "screaming interrupt" problem.


Release the IRQ
---------------
Once the device is quiesced (no more IRQs), one can call free_irq().
This function will return control once any pending IRQs are handled,
"unhook" the drivers IRQ handler from that IRQ, and finally release
the IRQ if no one else is using it.


Stop all DMA activity
---------------------
It's extremely important to stop all DMA operations BEFORE attempting
to deallocate DMA control data. Failure to do so can result in memory
corruption, hangs, and on some chip-sets a hard crash.

Stopping DMA after stopping the IRQs can avoid races where the
IRQ handler might restart DMA engines.

While this step sounds obvious and trivial, several "mature" drivers
didn't get this step right in the past.


Release DMA buffers
-------------------
Once DMA is stopped, clean up streaming DMA first.
I.e. unmap data buffers and return buffers to "upstream"
owners if there is one.

Then clean up "coherent" buffers which contain the control data.

See Documentation/core-api/dma-api.rst for details on unmapping interfaces.


Unregister from other subsystems
--------------------------------
Most low level PCI device drivers support some other subsystem
like USB, ALSA, SCSI, NetDev, Infiniband, etc. Make sure your
driver isn't losing resources from that other subsystem.
If this happens, typically the symptom is an Oops (panic) when
the subsystem attempts to call into a driver that has been unloaded.


Disable Device from responding to MMIO/IO Port addresses
--------------------------------------------------------
io_unmap() MMIO or IO Port resources and then call pci_disable_device().
This is the symmetric opposite of pci_enable_device().
Do not access device registers after calling pci_disable_device().


Release MMIO/IO Port Resource(s)
--------------------------------
Call pci_release_region() to mark the MMIO or IO Port range as available.
Failure to do so usually results in the inability to reload the driver.


How to access PCI config space
==============================

You can use `pci_(read|write)_config_(byte|word|dword)` to access the config
space of a device represented by `struct pci_dev *`. All these functions return
0 when successful or an error code (`PCIBIOS_...`) which can be translated to a
text string by pcibios_strerror. Most drivers expect that accesses to valid PCI
devices don't fail.

If you don't have a struct pci_dev available, you can call
`pci_bus_(read|write)_config_(byte|word|dword)` to access a given device
and function on that bus.

If you access fields in the standard portion of the config header, please
use symbolic names of locations and bits declared in <linux/pci.h>.

If you need to access Extended PCI Capability registers, just call
pci_find_capability() for the particular capability and it will find the
corresponding register block for you.


Other interesting functions
===========================

=============================	================================================
pci_get_domain_bus_and_slot()	Find pci_dev corresponding to given domain,
				bus and slot and number. If the device is
				found, its reference count is increased.
pci_set_power_state()		Set PCI Power Management state (0=D0 ... 3=D3)
pci_find_capability()		Find specified capability in device's capability
				list.
pci_resource_start()		Returns bus start address for a given PCI region
pci_resource_end()		Returns bus end address for a given PCI region
pci_resource_len()		Returns the byte length of a PCI region
pci_set_drvdata()		Set private driver data pointer for a pci_dev
pci_get_drvdata()		Return private driver data pointer for a pci_dev
pci_set_mwi()			Enable Memory-Write-Invalidate transactions.
pci_clear_mwi()			Disable Memory-Write-Invalidate transactions.
=============================	================================================


Miscellaneous hints
===================

When displaying PCI device names to the user (for example when a driver wants
to tell the user what card has it found), please use pci_name(pci_dev).

Always refer to the PCI devices by a pointer to the pci_dev structure.
All PCI layer functions use this identification and it's the only
reasonable one. Don't use bus/slot/function numbers except for very
special purposes -- on systems with multiple primary buses their semantics
can be pretty complex.

Don't try to turn on Fast Back to Back writes in your driver.  All devices
on the bus need to be capable of doing it, so this is something which needs
to be handled by platform and generic code, not individual drivers.


Vendor and device identifications
=================================

Do not add new device or vendor IDs to include/linux/pci_ids.h unless they
are shared across multiple drivers.  You can add private definitions in
your driver if they're helpful, or just use plain hex constants.

The device IDs are arbitrary hex numbers (vendor controlled) and normally used
only in a single location, the pci_device_id table.

Please DO submit new vendor/device IDs to https://pci-ids.ucw.cz/.
There's a mirror of the pci.ids file at https://github.com/pciutils/pciids.


Obsolete functions
==================

There are several functions which you might come across when trying to
port an old driver to the new PCI interface.  They are no longer present
in the kernel as they aren't compatible with hotplug or PCI domains or
having sane locking.

=================	===========================================
pci_find_device()	Superseded by pci_get_device()
pci_find_subsys()	Superseded by pci_get_subsys()
pci_find_slot()		Superseded by pci_get_domain_bus_and_slot()
pci_get_slot()		Superseded by pci_get_domain_bus_and_slot()
=================	===========================================

The alternative is the traditional PCI device driver that walks PCI
device lists. This is still possible but discouraged.


MMIO Space and "Write Posting"
==============================

Converting a driver from using I/O Port space to using MMIO space
often requires some additional changes. Specifically, "write posting"
needs to be handled. Many drivers (e.g. tg3, acenic, sym53c8xx_2)
already do this. I/O Port space guarantees write transactions reach the PCI
device before the CPU can continue. Writes to MMIO space allow the CPU
to continue before the transaction reaches the PCI device. HW weenies
call this "Write Posting" because the write completion is "posted" to
the CPU before the transaction has reached its destination.

Thus, timing sensitive code should add readl() where the CPU is
expected to wait before doing other work.  The classic "bit banging"
sequence works fine for I/O Port space::

       for (i = 8; --i; val >>= 1) {
               outb(val & 1, ioport_reg);      /* write bit */
               udelay(10);
       }

The same sequence for MMIO space should be::

       for (i = 8; --i; val >>= 1) {
               writeb(val & 1, mmio_reg);      /* write bit */
               readb(safe_mmio_reg);           /* flush posted write */
               udelay(10);
       }

It is important that "safe_mmio_reg" not have any side effects that
interferes with the correct operation of the device.

Another case to watch out for is when resetting a PCI device. Use PCI
Configuration space reads to flush the writel(). This will gracefully
handle the PCI master abort on all platforms if the PCI device is
expected to not respond to a readl().  Most x86 platforms will allow
MMIO reads to master abort (a.k.a. "Soft Fail") and return garbage
(e.g. ~0). But many RISC platforms will crash (a.k.a."Hard Fail").

---

### Documentation PCI Pcieaer Howto (`Documentation/PCI/pcieaer-howto.rst`)

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

===========================================================
The PCI Express Advanced Error Reporting Driver Guide HOWTO
===========================================================

:Authors: - T. Long Nguyen <[email protected]>
          - Yanmin Zhang <[email protected]>

:Copyright: |copy| 2006 Intel Corporation

Overview
===========

About this guide
----------------

This guide describes the basics of the PCI Express (PCIe) Advanced Error
Reporting (AER) driver and provides information on how to use it, as
well as how to enable the drivers of Endpoint devices to conform with
the PCIe AER driver.


What is the PCIe AER Driver?
----------------------------

PCIe error signaling can occur on the PCIe link itself
or on behalf of transactions initiated on the link. PCIe
defines two error reporting paradigms: the baseline capability and
the Advanced Error Reporting capability. The baseline capability is
required of all PCIe components providing a minimum defined
set of error reporting requirements. Advanced Error Reporting
capability is implemented with a PCIe Advanced Error Reporting
extended capability structure providing more robust error reporting.

The PCIe AER driver provides the infrastructure to support PCIe Advanced
Error Reporting capability. The PCIe AER driver provides three basic
functions:

  - Gathers the comprehensive error information if errors occurred.
  - Reports error to the users.
  - Performs error recovery actions.

The AER driver only attaches to Root Ports and RCECs that support the PCIe
AER capability.


User Guide
==========

Include the PCIe AER Root Driver into the Linux Kernel
------------------------------------------------------

The PCIe AER driver is a Root Port service driver attached
via the PCIe Port Bus driver. If a user wants to use it, the driver
must be compiled. It is enabled with CONFIG_PCIEAER, which
depends on CONFIG_PCIEPORTBUS.

Load PCIe AER Root Driver
-------------------------

Some systems have AER support in firmware. Enabling Linux AER support at
the same time the firmware handles AER would result in unpredictable
behavior. Therefore, Linux does not handle AER events unless the firmware
grants AER control to the OS via the ACPI _OSC method. See the PCI Firmware
Specification for details regarding _OSC usage.

AER error output
----------------

When a PCIe AER error is captured, an error message will be output to
console. If it's a correctable error, it is output as a warning message.
Otherwise, it is printed as an error. So users could choose different
log level to filter out correctable error messages.

Below shows an example::

  0000:50:00.0: PCIe Bus Error: severity=Uncorrectable (Fatal), type=Transaction Layer, (Requester ID)
  0000:50:00.0:   device [8086:0329] error status/mask=00100000/00000000
  0000:50:00.0:    [20] UnsupReq               (First)
  0000:50:00.0:   TLP Header: 0x04000001 0x00200a03 0x05010000 0x00050100

In the example, 'Requester ID' means the ID of the device that sent
the error message to the Root Port. Please refer to PCIe specs for other
fields.

AER Ratelimits
--------------

Since error messages can be generated for each transaction, we may see
large volumes of errors reported. To prevent spammy devices from flooding
the console/stalling execution, messages are throttled by device and error
type (correctable vs. non-fatal uncorrectable).  Fatal errors, including
DPC errors, are not ratelimited.

AER uses the default ratelimit of DEFAULT_RATELIMIT_BURST (10 events) over
DEFAULT_RATELIMIT_INTERVAL (5 seconds).

Ratelimits are exposed in the form of sysfs attributes and configurable.
See Documentation/ABI/testing/sysfs-bus-pci-devices-aer.

AER Statistics / Counters
-------------------------

When PCIe AER errors are captured, the counters / statistics are also exposed
in the form of sysfs attributes which are documented at
Documentation/ABI/testing/sysfs-bus-pci-devices-aer.

Developer Guide
===============

To enable error recovery, a software driver must provide callbacks.

To support AER better, developers need to understand how AER works.

PCIe errors are classified into two types: correctable errors
and uncorrectable errors. This classification is based on the impact
of those errors, which may result in degraded performance or function
failure.

Correctable errors pose no impacts on the functionality of the
interface. The PCIe protocol can recover without any software
intervention or any loss of data. These errors are detected and
corrected by hardware.

Unlike correctable errors, uncorrectable
errors impact functionality of the interface. Uncorrectable errors
can cause a particular transaction or a particular PCIe link
to be unreliable. Depending on those error conditions, uncorrectable
errors are further classified into non-fatal errors and fatal errors.
Non-fatal errors cause the particular transaction to be unreliable,
but the PCIe link itself is fully functional. Fatal errors, on
the other hand, cause the link to be unreliable.

When PCIe error reporting is enabled, a device will automatically send an
error message to the Root Port above it when it captures
an error. The Root Port, upon receiving an error reporting message,
internally processes and logs the error message in its AER
Capability structure. Error information being logged includes storing
the error reporting agent's Requester ID into the Error Source
Identification Registers and setting the error bits of the Root Error
Status Register accordingly. If AER error reporting is enabled in the Root
Error Command Register, the Root Port generates an interrupt when an
error is detected.

Note that the errors as described above are related to the PCIe
hierarchy and links. These errors do not include any device specific
errors because device specific errors will still get sent directly to
the device driver.

Provide callbacks
-----------------

PCI error-recovery callbacks

Correctable errors pose no impacts on the functionality of
the interface. The PCIe protocol can recover without any
software intervention or any loss of data. These errors do not
require any recovery actions. The AER driver clears the device's
correctable error status register accordingly and logs these errors.

Uncorrectable (non-fatal and fatal) errors

https://github.com/intel/aer-inject.git

::

  int pcie_port_service_register(struct pcie_port_service_driver *new)

This API replaces the Linux Driver Model's pci_register_driver API. A
service driver should always calls pcie_port_service_register at
module init. Note that after service driver being loaded, calls
such as pci_enable_device(dev) and pci_set_master(dev) are no longer
necessary since these calls are executed by the PCI Port Bus driver.

pcie_port_service_unregister

Below is sample service driver code to initialize the port service
driver data structure.
::

  static struct pcie_port_service_id service_id[] = { {
    .vendor = PCI_ANY_ID,
    .device = PCI_ANY_ID,
    .port_type = PCIE_RC_PORT,
    .service_type = PCIE_PORT_SERVICE_AER,
    }, { /* end: all zeroes */ }
  };

  static struct pcie_port_service_driver root_aerdrv = {
    .name		= (char *)device_name,
    .id_table	= service_id,

    .probe		= aerdrv_load,
    .remove		= aerdrv_unload,

    .suspend	= aerdrv_suspend,
    .resume		= aerdrv_resume,
  };

Below is a sample code for registering/unregistering a service
driver.
::

  static int __init aerdrv_service_init(void)
  {
    int retval = 0;

    retval = pcie_port_service_register(&root_aerdrv);
    if (!retval) {
      /*
      * FIX ME
      */
    }
    return retval;
  }

  static void __exit aerdrv_service_exit(void)
  {
    pcie_port_service_unregister(&root_aerdrv);
  }

  module_init(aerdrv_service_init);
  module_exit(aerdrv_service_exit);

Possible Resource Conflicts
===========================

Since all service drivers of a PCI-PCI Bridge Port device are
allowed to run simultaneously, below lists a few of possible resource
conflicts with proposed solutions.

MSI and MSI-X Vector Resource
-----------------------------

Once MSI or MSI-X interrupts are enabled on a device, it stays in this
mode until they are disabled again.  Since service drivers of the same
PCI-PCI Bridge port share the same physical device, if an individual
service driver enables or disables MSI/MSI-X mode it may result
unpredictable behavior.

To avoid this situation all service drivers are not permitted to
switch interrupt mode on its device. The PCI Express Port Bus driver
is responsible for determining the interrupt mode and this should be
transparent to service drivers. Service drivers need to know only
the vector IRQ assigned to the field irq of struct pcie_device, which
is passed in when the PCI Express Port Bus driver probes each service
driver. Service drivers should use (struct pcie_device*)dev->irq to
call request_irq/free_irq. In addition, the interrupt mode is stored
in the field interrupt_mode of struct pcie_device.

PCI Memory/IO Mapped Regions
----------------------------

Service drivers for PCI Express Power Management (PME), Advanced
Error Reporting (AER), Hot-Plug (HP) and Virtual Channel (VC) access
PCI configuration space on the PCI Express port. In all cases the
registers accessed are independent of each other. This patch assumes
that all service drivers will be well behaved and not overwrite
other service driver's configuration settings.

PCI Config Registers
--------------------

Each service driver runs its PCI config operations on its own
capability structure except the PCI Express capability structure,
that is shared between many drivers including the service drivers.
RMW Capability accessors (pcie_capability_clear_and_set_word(),
pcie_capability_set_word(), and pcie_capability_clear_word()) protect
a selected set of PCI Express Capability Registers:

* Link Control Register
* Root Control Register
* Link Control 2 Register

Any change to those registers should be performed using RMW accessors to
avoid problems due to concurrent updates. For the up-to-date list of
protected registers, see pcie_capability_clear_and_set_word().

---

### Documentation PCI Sysfs Pci (`Documentation/PCI/sysfs-pci.rst`)

.. SPDX-License-Identifier: GPL-2.0

============================================
Accessing PCI device resources through sysfs
============================================

sysfs, usually mounted at /sys, provides access to PCI resources on platforms
that support it.  For example, a given bus might look like this::

     /sys/devices/pci0000:17
     |-- 0000:17:00.0
     |   |-- class
     |   |-- config
     |   |-- device
     |   |-- enable
     |   |-- irq
     |   |-- local_cpus
     |   |-- remove
     |   |-- resource
     |   |-- resource0
     |   |-- resource1
     |   |-- resource2
     |   |-- revision
     |   |-- rom
     |   |-- subsystem_device
     |   |-- subsystem_vendor
     |   `-- vendor
     `-- ...

The topmost element describes the PCI domain and bus number.  In this case,
the domain number is 0000 and the bus number is 17 (both values are in hex).
This bus contains a single function device in slot 0.  The domain and bus
numbers are reproduced for convenience.  Under the device directory are several
files, each with their own function.

       =================== =====================================================
       file		   function
       =================== =====================================================
       class		   PCI class (ascii, ro)
       config		   PCI config space (binary, rw)
       device		   PCI device (ascii, ro)
       enable	           Whether the device is enabled (ascii, rw)
       irq		   IRQ number (ascii, ro)
       local_cpus	   nearby CPU mask (cpumask, ro)
       remove		   remove device from kernel's list (ascii, wo)
       resource		   PCI resource host addresses (ascii, ro)
       resource0..N	   PCI resource N, if present (binary, mmap, rw\ [1]_)
       resource0_wc..N_wc  PCI WC map resource N, if prefetchable (binary, mmap)
       revision		   PCI revision (ascii, ro)
       rom		   PCI ROM resource, if present (binary, ro)
       subsystem_device	   PCI subsystem device (ascii, ro)
       subsystem_vendor	   PCI subsystem vendor (ascii, ro)
       vendor		   PCI vendor (ascii, ro)
       =================== =====================================================

::

  ro - read only file
  rw - file is readable and writable
  wo - write only file
  mmap - file is mmapable
  ascii - file contains ascii text
  binary - file contains binary data
  cpumask - file contains a cpumask type

.. [1] rw for IORESOURCE_IO (I/O port) regions only

The read only files are informational, writes to them will be ignored, with
the exception of the 'rom' file.  Writable files can be used to perform
actions on the device (e.g. changing config space, detaching a device).
mmapable files are available via an mmap of the file at offset 0 and can be
used to do actual device programming from userspace.  Note that some platforms
don't support mmapping of certain resources, so be sure to check the return
value from any attempted mmap.  The most notable of these are I/O port
resources, which also provide read/write access.

The 'enable' file provides a counter that indicates how many times the device
has been enabled.  If the 'enable' file currently returns '4', and a '1' is
echoed into it, it will then return '5'.  Echoing a '0' into it will decrease
the count.  Even when it returns to 0, though, some of the initialisation
may not be reversed.

The 'rom' file is special in that it provides read-only access to the device's
ROM file, if available.  It's disabled by default, however, so applications
should write the string "1" to the file to enable it before attempting a read
call, and disable it following the access by writing "0" to the file.  Note
that the device must be enabled for a rom read to return data successfully.
In the event a driver is not bound to the device, it can be enabled using the
'enable' file, documented above.

The 'remove' file is used to remove the PCI device, by writing a non-zero
integer to the file.  This does not involve any kind of hot-plug functionality,
e.g. powering off the device.  The device is removed from the kernel's list of
PCI devices, the sysfs directory for it is removed, and the device will be
removed from any drivers attached to it. Removal of PCI root buses is
disallowed.

Accessing legacy resources through sysfs
----------------------------------------

Legacy I/O port and ISA memory resources are also provided in sysfs if the
underlying platform supports them.  They're located in the PCI class hierarchy,
e.g.::

	/sys/class/pci_bus/0000:17/
	|-- bridge -> ../../../devices/pci0000:17
	|-- cpuaffinity
	|-- legacy_io
	`-- legacy_mem

The legacy_io file is a read/write file that can be used by applications to
do legacy port I/O.  The application should open the file, seek to the desired
port (e.g. 0x3e8) and do a read or a write of 1, 2 or 4 bytes.  The legacy_mem
file should be mmapped with an offset corresponding to the memory offset
desired, e.g. 0xa0000 for the VGA frame buffer.  The application can then
simply dereference the returned pointer (after checking for errors of course)
to access legacy memory space.

Supporting PCI access on new platforms
--------------------------------------

In order to support PCI resource mapping as described above, Linux platform
code should ideally define ARCH_GENERIC_PCI_MMAP_RESOURCE and use the generic
implementation of that functionality. To support the historical interface of
mmap() through files in /proc/bus/pci, platforms may also set HAVE_PCI_MMAP.

Alternatively, platforms which set HAVE_PCI_MMAP may provide their own
implementation of pci_mmap_resource_range() instead of defining
ARCH_GENERIC_PCI_MMAP_RESOURCE.

Platforms which support write-combining maps of PCI resources must define
arch_can_pci_mmap_wc() which shall evaluate to non-zero at runtime when
write-combining is permitted. Platforms which support maps of I/O resources
define arch_can_pci_mmap_io() similarly.

Legacy resources are protected by the HAVE_PCI_LEGACY define.  Platforms
wishing to support legacy functionality should define it and provide
pci_legacy_read, pci_legacy_write and pci_mmap_legacy_page_range functions.

---

### Documentation PCI Tph (`Documentation/PCI/tph.rst`)

.. SPDX-License-Identifier: GPL-2.0


===========
TPH Support
===========

:Copyright: 2024 Advanced Micro Devices, Inc.
:Authors: - Eric van Tassell <[email protected]>
          - Wei Huang <[email protected]>


Overview
========

TPH (TLP Processing Hints) is a PCIe feature that allows endpoint devices
to provide optimization hints for requests that target memory space.
These hints, in a format called Steering Tags (STs), are embedded in the
requester's TLP headers, enabling the system hardware, such as the Root
Complex, to better manage platform resources for these requests.

For example, on platforms with TPH-based direct data cache injection
support, an endpoint device can include appropriate STs in its DMA
traffic to specify which cache the data should be written to. This allows
the CPU core to have a higher probability of getting data from cache,
potentially improving performance and reducing latency in data
processing.


How to Use TPH
==============

TPH is presented as an optional extended capability in PCIe. The Linux
kernel handles TPH discovery during boot, but it is up to the device
driver to request TPH enablement if it is to be utilized. Once enabled,
the driver uses the provided API to obtain the Steering Tag for the
target memory and to program the ST into the device's ST table.

Enable TPH support in Linux
---------------------------

To support TPH, the kernel must be built with the CONFIG_PCIE_TPH option
enabled.

Manage TPH
----------

To enable TPH for a device, use the following function::

  int pcie_enable_tph(struct pci_dev *pdev, int mode);

This function enables TPH support for device with a specific ST mode.
Current supported modes include:

  * PCI_TPH_ST_NS_MODE - NO ST Mode
  * PCI_TPH_ST_IV_MODE - Interrupt Vector Mode
  * PCI_TPH_ST_DS_MODE - Device Specific Mode

`pcie_enable_tph()` checks whether the requested mode is actually
supported by the device before enabling. The device driver can figure out
which TPH mode is supported and can be properly enabled based on the
return value of `pcie_enable_tph()`.

To disable TPH, use the following function::

  void pcie_disable_tph(struct pci_dev *pdev);

Manage ST
---------

Steering Tags are platform specific. PCIe spec does not specify where STs
are from. Instead PCI Firmware Specification defines an ACPI _DSM method
(see the `Revised _DSM for Cache Locality TPH Features ECN
<https://members.pcisig.com/wg/PCI-SIG/document/15470>`_) for retrieving
STs for a target memory of various properties. This method is what is
supported in this implementation.

To retrieve a Steering Tag for a target memory associated with a specific
CPU, use the following function::

  int pcie_tph_get_cpu_st(struct pci_dev *pdev, enum tph_mem_type type,
                          unsigned int cpu_uid, u16 *tag);

The `type` argument is used to specify the memory type, either volatile
or persistent, of the target memory. The `cpu_uid` argument specifies the
CPU where the memory is associated to.

After the ST value is retrieved, the device driver can use the following
function to write the ST into the device::

  int pcie_tph_set_st_entry(struct pci_dev *pdev, unsigned int index,
                            u16 tag);

The `index` argument is the ST table entry index the ST tag will be
written into. `pcie_tph_set_st_entry()` will figure out the proper
location of ST table, either in the MSI-X table or in the TPH Extended
Capability space, and write the Steering Tag into the ST entry pointed by
the `index` argument.

It is completely up to the driver to decide how to use these TPH
functions. For example a network device driver can use the TPH APIs above
to update the Steering Tag when interrupt affinity of a RX/TX queue has
been changed. Here is a sample code for IRQ affinity notifier:

.. code-block:: c

    static void irq_affinity_notified(struct irq_affinity_notify *notify,
                                      const cpumask_t *mask)
    {
         struct drv_irq *irq;
         unsigned int cpu_id;
         u16 tag;

         irq = container_of(notify, struct drv_irq, affinity_notify);
         cpumask_copy(irq->cpu_mask, mask);

         /* Pick a right CPU as the target - here is just an example */
         cpu_id = cpumask_first(irq->cpu_mask);

         if (pcie_tph_get_cpu_st(irq->pdev, TPH_MEM_TYPE_VM, cpu_id,
                                 &tag))
             return;

         if (pcie_tph_set_st_entry(irq->pdev, irq->msix_nr, tag))
             return;
    }

Disable TPH system-wide
-----------------------

There is a kernel command line option available to control TPH feature:
    * "notph": TPH will be disabled for all endpoint devices.

---

### Documentation RCU NMI RCU (`Documentation/RCU/NMI-RCU.rst`)

.. _NMI_rcu_doc:

Using RCU to Protect Dynamic NMI Handlers
=========================================


Although RCU is usually used to protect read-mostly data structures,
it is possible to use RCU to provide dynamic non-maskable interrupt
handlers, as well as dynamic irq handlers.  This document describes
how to do this, drawing loosely from Zwane Mwaikambo's NMI-timer
work in an old version of "arch/x86/kernel/traps.c".

The relevant pieces of code are listed below, each followed by a
brief explanation::

	static int dummy_nmi_callback(struct pt_regs *regs, int cpu)
	{
		return 0;
	}

The dummy_nmi_callback() function is a "dummy" NMI handler that does
nothing, but returns zero, thus saying that it did nothing, allowing
the NMI handler to take the default machine-specific action::

	static nmi_callback_t nmi_callback = dummy_nmi_callback;

This nmi_callback variable is a global function pointer to the current
NMI handler::

	void do_nmi(struct pt_regs * regs, long error_code)
	{
		int cpu;

		nmi_enter();

		cpu = smp_processor_id();
		++nmi_count(cpu);

		if (!rcu_dereference_sched(nmi_callback)(regs, cpu))
			default_do_nmi(regs);

		nmi_exit();
	}

The do_nmi() function processes each NMI.  It first disables preemption
in the same way that a hardware irq would, then increments the per-CPU
count of NMIs.  It then invokes the NMI handler stored in the nmi_callback
function pointer.  If this handler returns zero, do_nmi() invokes the
default_do_nmi() function to handle a machine-specific NMI.  Finally,
preemption is restored.

In theory, rcu_dereference_sched() is not needed, since this code runs
only on i386, which in theory does not need rcu_dereference_sched()
anyway.  However, in practice it is a good documentation aid, particularly
for anyone attempting to do something similar on Alpha or on systems
with aggressive optimizing compilers.

Quick Quiz:
		Why might the rcu_dereference_sched() be necessary on Alpha, given that the code referenced by the pointer is read-only?

:ref:`Answer to Quick Quiz <answer_quick_quiz_NMI>`

Back to the discussion of NMI and RCU::

	void set_nmi_callback(nmi_callback_t callback)
	{
		rcu_assign_pointer(nmi_callback, callback);
	}

The set_nmi_callback() function registers an NMI handler.  Note that any
data that is to be used by the callback must be initialized up -before-
the call to set_nmi_callback().  On architectures that do not order
writes, the rcu_assign_pointer() ensures that the NMI handler sees the
initialized values::

	void unset_nmi_callback(void)
	{
		rcu_assign_pointer(nmi_callback, dummy_nmi_callback);
	}

This function unregisters an NMI handler, restoring the original
dummy_nmi_handler().  However, there may well be an NMI handler
currently executing on some other CPU.  We therefore cannot free
up any data structures used by the old NMI handler until execution
of it completes on all other CPUs.

One way to accomplish this is via synchronize_rcu(), perhaps as
follows::

	unset_nmi_callback();
	synchronize_rcu();
	kfree(my_nmi_data);

This works because (as of v4.20) synchronize_rcu() blocks until all
CPUs complete any preemption-disabled segments of code that they were
executing.
Since NMI handlers disable preemption, synchronize_rcu() is guaranteed
not to return until all ongoing NMI handlers exit.  It is therefore safe
to free up the handler's data as soon as synchronize_rcu() returns.

Important note: for this to work, the architecture in question must
invoke nmi_enter() and nmi_exit() on NMI entry and exit, respectively.

.. _answer_quick_quiz_NMI:

Answer to Quick Quiz:
	Why might the rcu_dereference_sched() be necessary on Alpha, given that the code referenced by the pointer is read-only?

	The caller to set_nmi_callback() might well have
	initialized some data that is to be used by the new NMI
	handler.  In this case, the rcu_dereference_sched() would
	be needed, because otherwise a CPU that received an NMI
	just after the new handler was set might see the pointer
	to the new NMI handler, but the old pre-initialized
	version of the handler's data.

	This same sad story can happen on other CPUs when using
	a compiler with aggressive pointer-value speculation
	optimizations.  (But please don't!)

	More important, the rcu_dereference_sched() makes it
	clear to someone reading the code that the pointer is
	being protected by RCU-sched.

---

### Documentation RCU RTFP (`Documentation/RCU/RTFP.txt`)

Read the F-ing Papers!


This document describes RCU-related publications, and is followed by
the corresponding bibtex entries.  A number of the publications may
be found at http://www.rdrop.com/users/paulmck/RCU/.

The first thing resembling RCU was published in 1980, when Kung and Lehman
[Kung80] recommended use of a garbage collector to defer destruction
of nodes in a parallel binary search tree in order to simplify its
implementation.  This works well in environments that have garbage
collectors, but most production garbage collectors incur significant
overhead.

In 1982, Manber and Ladner [Manber82,Manber84] recommended deferring
destruction until all threads running at that time have terminated, again
for a parallel binary search tree.  This approach works well in systems
with short-lived threads, such as the K42 research operating system.
However, Linux has long-lived tasks, so more is needed.

In 1986, Hennessy, Osisek, and Seigh [Hennessy89] introduced passive
serialization, which is an RCU-like mechanism that relies on the presence
of "quiescent states" in the VM/XA hypervisor that are guaranteed not
to be referencing the data structure.  However, this mechanism was not
optimized for modern computer systems, which is not surprising given
that these overheads were not so expensive in the mid-80s.  Nonetheless,
passive serialization appears to be the first deferred-destruction
mechanism to be used in production.  Furthermore, the relevant patent
has lapsed, so this approach may be used in non-GPL software, if desired.
(In contrast, implementation of RCU is permitted only in software licensed
under either GPL or LGPL.  Sorry!!!)

In 1990, Pugh [Pugh90] noted that explicitly tracking which threads
were reading a given data structure permitted deferred free to operate
in the presence of non-terminating threads.  However, this explicit
tracking imposes significant read-side overhead, which is undesirable
in read-mostly situations.  This algorithm does take pains to avoid
write-side contention and parallelize the other write-side overheads by
providing a fine-grained locking design, however, it would be interesting
to see how much of the performance advantage reported in 1990 remains
in 2004.

At about this same time, Adams [Adams91] described ``chaotic relaxation'',
where the normal barriers between successive iterations of convergent
numerical algorithms are relaxed, so that iteration $n$ might use
data from iteration $n-1$ or even $n-2$.  This introduces error,
which typically slows convergence and thus increases the number of
iterations required.  However, this increase is sometimes more than made
up for by a reduction in the number of expensive barrier operations,
which are otherwise required to synchronize the threads at the end
of each iteration.  Unfortunately, chaotic relaxation requires highly
structured data, such as the matrices used in scientific programs, and
is thus inapplicable to most data structures in operating-system kernels.

In 1992, Henry (now Alexia) Massalin completed a dissertation advising
parallel programmers to defer processing when feasible to simplify
synchronization.  RCU makes extremely heavy use of this advice.

In 1993, Jacobson [Jacobson93] verbally described what is perhaps the
simplest deferred-free technique: simply waiting a fixed amount of time
before freeing blocks awaiting deferred free.  Jacobson did not describe
any write-side changes he might have made in this work using SGI's Irix
kernel.  Aju John published a similar technique in 1995 [AjuJohn95].
This works well if there is a well-defined upper bound on the length of
time that reading threads can hold references, as there might well be in
hard real-time systems.  However, if this time is exceeded, perhaps due
to preemption, excessive interrupts, or larger-than-anticipated load,
memory corruption can ensue, with no reasonable means of diagnosis.
Jacobson's technique is therefore inappropriate for use in production
operating-system kernels, except when such kernels can provide hard
real-time response guarantees for all operations.

Also in 1995, Pu et al. [Pu95a] applied a technique similar to that of Pugh's
read-side-tracking to permit replugging of algorithms within a commercial
Unix operating system.  However, this replugging permitted only a single
reader at a time.  The following year, this same group of researchers
extended their technique to allow for multiple readers [Cowan96a].
Their approach requires memory barriers (and thus pipeline stalls),
but reduces memory latency, contention, and locking overheads.

1995 also saw the first publication of DYNIX/ptx's RCU mechanism
[Slingwine95], which was optimized for modern CPU architectures,
and was successfully applied to a number of situations within the
DYNIX/ptx kernel.  The corresponding conference paper appeared in 1998
[McKenney98].

In 1999, the Tornado and K42 groups described their "generations"
mechanism, which quite similar to RCU [Gamsa99].  These operating systems
made pervasive use of RCU in place of "existence locks", which greatly
simplifies locking hierarchies.

2001 saw the first RCU presentation involving Linux [McKenney01a]
at OLS.  The resulting abundance of RCU patches was presented the
following year [McKenney02a], and use of RCU in dcache was first
described that same year [Linder02a].

Also in 2002, Michael [Michael02b,Michael02a] presented "hazard-pointer"
techniques that defer the destruction of data structures to simplify
non-blocking synchronization (wait-free synchronization, lock-free
synchronization, and obstruction-free synchronization are all examples of
non-blocking synchronization).  In particular, this technique eliminates
locking, reduces contention, reduces memory latency for readers, and
parallelizes pipeline stalls and memory latency for writers.  However,
these techniques still impose significant read-side overhead in the
form of memory barriers.  Researchers at Sun worked along similar lines
in the same timeframe [HerlihyLM02].  These techniques can be thought
of as inside-out reference counts, where the count is represented by the
number of hazard pointers referencing a given data structure (rather than
the more conventional counter field within the data structure itself).

By the same token, RCU can be thought of as a "bulk reference count",
where some form of reference counter covers all reference by a given CPU
or thread during a set timeframe.  This timeframe is related to, but
not necessarily exactly the same as, an RCU grace period.  In classic
RCU, the reference counter is the per-CPU bit in the "bitmask" field,
and each such bit covers all references that might have been made by
the corresponding CPU during the prior grace period.  Of course, RCU
can be thought of in other terms as well.

In 2003, the K42 group described how RCU could be used to create
hot-pluggable implementations of operating-system functions [Appavoo03a].
Later that year saw a paper describing an RCU implementation of System
V IPC [Arcangeli03], and an introduction to RCU in Linux Journal
[McKenney03a].

2004 has seen a Linux-Journal article on use of RCU in dcache
[McKenney04a], a performance comparison of locking to RCU on several
different CPUs [McKenney04b], a dissertation describing use of RCU in a
number of operating-system kernels [PaulEdwardMcKenneyPhD], a paper
describing how to make RCU safe for soft-realtime applications [Sarma04c],
and a paper describing SELinux performance with RCU [JamesMorris04b].

2005 brought further adaptation of RCU to realtime use, permitting
preemption of RCU realtime critical sections [PaulMcKenney05a,
PaulMcKenney05b].

2006 saw the first best-paper award for an RCU paper [ThomasEHart2006a],
as well as further work on efficient implementations of preemptible
RCU [PaulEMcKenney2006b], but priority-boosting of RCU read-side critical
sections proved elusive.  An RCU implementation permitting general
blocking in read-side critical sections appeared [PaulEMcKenney2006c],
Robert Olsson described an RCU-protected trie-hash combination
[RobertOlsson2006a].

2007 saw the journal version of the award-winning RCU paper from 2006
[ThomasEHart2007a], as well as a paper demonstrating use of Promela
and Spin to mechanically verify an optimization to Oleg Nesterov's
QRCU [PaulEMcKenney2007QRCUspin], a design document describing
preemptible RCU [PaulEMcKenney2007PreemptibleRCU], and the three-part
LWN "What is RCU?" series [PaulEMcKenney2007WhatIsRCUFundamentally,
PaulEMcKenney2008WhatIsRCUUsage, and PaulEMcKenney2008WhatIsRCUAPI].

2008 saw a journal paper on real-time RCU [DinakarGuniguntala2008IBMSysJ],
a history of how Linux changed RCU more than RCU changed Linux
[PaulEMcKenney2008RCUOSR], and a design overview of hierarchical RCU
[PaulEMcKenney2008HierarchicalRCU].

2009 introduced user-level RCU algorithms [PaulEMcKenney2009MaliciousURCU],
which Mathieu Desnoyers is now maintaining [MathieuDesnoyers2009URCU]
[MathieuDesnoyersPhD].  TINY_RCU [PaulEMcKenney2009BloatWatchRCU] made
its appearance, as did expedited RCU [PaulEMcKenney2009expeditedRCU].
The problem of resizeable RCU-protected hash tables may now be on a path
to a solution [JoshTriplett2009RPHash].

Bibtex Entries

@article{Kung80
,author="H. T. Kung and Q. Lehman"
,title="Concurrent Maintenance of Binary Search Trees"
,Year="1980"
,Month="September"
,journal="ACM Transactions on Database Systems"
,volume="5"
,number="3"
,pages="354-382"
}

@techreport{Manber82
,author="Udi Manber and Richard E. Ladner"
,title="Concurrency Control in a Dynamic Search Structure"
,institution="Department of Computer Science, University of Washington"
,address="Seattle, Washington"
,year="1982"
,number="82-01-01"
,month="January"
,pages="28"
}

@article{Manber84
,author="Udi Manber and Richard E. Ladner"
,title="Concurrency Control in a Dynamic Search Structure"
,Year="1984"
,Month="September"
,journal="ACM Transactions on Database Systems"
,volume="9"
,number="3"
,pages="439-455"
}

@techreport{Hennessy89
,author="James P. Hennessy and Damian L. Osisek and Joseph W. {Seigh II}"
,title="Passive Serialization in a Multitasking Environment"
,institution="US Patent and Trademark Office"
,address="Washington, DC"
,year="1989"
,number="US Patent 4,809,168 (lapsed)"
,month="February"
,pages="11"
}

@techreport{Pugh90
,author="William Pugh"
,title="Concurrent Maintenance of Skip Lists"
,institution="Institute of Advanced Computer Science Studies, Department of Computer Science, University of Maryland"
,address="College Park, Maryland"
,year="1990"
,number="CS-TR-2222.1"
,month="June"
}

@Book{Adams91
,Author="Gregory R. Adams"
,title="Concurrent Programming, Principles, and Practices"
,Publisher="Benjamin Cummins"
,Year="1991"
}

@phdthesis{HMassalinPhD
,author="H. Massalin"
,title="Synthesis: An Efficient Implementation of Fundamental Operating
System Services"
,school="Columbia University"
,address="New York, NY"
,year="1992"
,annotation="
	Mondo optimizing compiler.
	Wait-free stuff.
	Good advice: defer work to avoid synchronization.
"
}

@unpublished{Jacobson93
,author="Van Jacobson"
,title="Avoid Read-Side Locking Via Delayed Free"
,year="1993"
,month="September"
,note="Verbal discussion"
}

@Conference{AjuJohn95
,Author="Aju John"
,Title="Dynamic vnodes -- Design and Implementation"
,Booktitle="{USENIX Winter 1995}"
,Publisher="USENIX Association"
,Month="January"
,Year="1995"
,pages="11-23"
,Address="New Orleans, LA"
}

@conference{Pu95a,
Author = "Calton Pu and Tito Autrey and Andrew Black and Charles Consel and
Crispin Cowan and Jon Inouye and Lakshmi Kethana and Jonathan Walpole and
Ke Zhang",
Title = "Optimistic Incremental Specialization: Streamlining a Commercial
Operating System",
Booktitle = "15\textsuperscript{th} ACM Symposium on
Operating Systems Principles (SOSP'95)",
address = "Copper Mountain, CO",
month="December",
year="1995",
pages="314-321",
annotation="
	Uses a replugger, but with a flag to signal when people are
	using the resource at hand.  Only one reader at a time.
"
}

@conference{Cowan96a,
Author = "Crispin Cowan and Tito Autrey and Charles Krasic and
Calton Pu and Jonathan Walpole",
Title = "Fast Concurrent Dynamic Linking for an Adaptive Operating System",
Booktitle = "International Conference on Configurable Distributed Systems
(ICCDS'96)",
address = "Annapolis, MD",
month="May",
year="1996",
pages="108",
isbn="0-8186-7395-8",
annotation="
	Uses a replugger, but with a counter to signal when people are
	using the resource at hand.  Allows multiple readers.
"
}

@techreport{Slingwine95
,author="John D. Slingwine and Paul E. McKenney"
,title="Apparatus and Method for Achieving Reduced Overhead Mutual
Exclusion and Maintaining Coherency in a Multiprocessor System
Utilizing Execution History and Thread Monitoring"
,institution="US Patent and Trademark Office"
,address="Washington, DC"
,year="1995"
,number="US Patent 5,442,758 (contributed under GPL)"
,month="August"
}

@techreport{Slingwine97
,author="John D. Slingwine and Paul E. McKenney"
,title="Method for maintaining data coherency using thread
activity summaries in a multicomputer system"
,institution="US Patent and Trademark Office"
,address="Washington, DC"
,year="1997"
,number="US Patent 5,608,893 (contributed under GPL)"
,month="March"
}

@techreport{Slingwine98
,author="John D. Slingwine and Paul E. McKenney"
,title="Apparatus and method for achieving reduced overhead
mutual exclusion and maintaining coherency in a multiprocessor
system utilizing execution history and thread monitoring"
,institution="US Patent and Trademark Office"
,address="Washington, DC"
,year="1998"
,number="US Patent 5,727,209 (contributed under GPL)"
,month="March"
}

@Conference{McKenney98
,Author="Paul E. McKenney and John D. Slingwine"
,Title="Read-Copy Update: Using Execution History to Solve Concurrency
Problems"
,Booktitle="{Parallel and Distributed Computing and Systems}"
,Month="October"
,Year="1998"
,pages="509-518"
,Address="Las Vegas, NV"
}

@Conference{Gamsa99
,Author="Ben Gamsa and Orran Krieger and Jonathan Appavoo and Michael Stumm"
,Title="Tornado: Maximizing Locality and Concurrency in a Shared Memory
Multiprocessor Operating System"
,Booktitle="{Proceedings of the 3\textsuperscript{rd} Symposium on
Operating System Design and Implementation}"
,Month="February"
,Year="1999"
,pages="87-100"
,Address="New Orleans, LA"
}

@techreport{Slingwine01
,author="John D. Slingwine and Paul E. McKenney"
,title="Apparatus and method for achieving reduced overhead
mutual exclusion and maintaining coherency in a multiprocessor
system utilizing execution history and thread monitoring"
,institution="US Patent and Trademark Office"
,address="Washington, DC"
,year="2001"
,number="US Patent 5,219,690 (contributed under GPL)"
,month="April"
}

@Conference{McKenney01a
,Author="Paul E. McKenney and Jonathan Appavoo and Andi Kleen and
Orran Krieger and Rusty Russell and Dipankar Sarma and Maneesh Soni"
,Title="Read-Copy Update"
,Booktitle="{Ottawa Linux Symposium}"
,Month="July"
,Year="2001"
,note="Available:
\url{http://www.linuxsymposium.org/2001/abstracts/readcopy.php}
\url{http://www.rdrop.com/users/paulmck/rclock/rclock_OLS.2001.05.01c.pdf}
[Viewed June 23, 2004]"
annotation="
Described RCU, and presented some patches implementing and using it in
the Linux kernel.
"
}

@Conference{Linder02a
,Author="Hanna Linder and Dipankar Sarma and Maneesh Soni"
,Title="Scalability of the Directory Entry Cache"
,Booktitle="{Ottawa Linux Symposium}"
,Month="June"
,Year="2002"
,pages="289-300"
}

@Conference{McKenney02a
,Author="Paul E. McKenney and Dipankar Sarma and
Andrea Arcangeli and Andi Kleen and Orran Krieger and Rusty Russell"
,Title="Read-Copy Update"
,Booktitle="{Ottawa Linux Symposium}"
,Month="June"
,Year="2002"
,pages="338-367"
,note="Available:
\url{http://www.linux.org.uk/~ajh/ols2002_proceedings.pdf.gz}
[Viewed June 23, 2004]"
}

@conference{Michael02a
,author="Maged M. Michael"
,title="Safe Memory Reclamation for Dynamic Lock-Free Objects Using Atomic
Reads and Writes"
,Year="2002"
,Month="August"
,booktitle="{Proceedings of the 21\textsuperscript{st} Annual ACM
Symposium on Principles of Distributed Computing}"
,pages="21-30"
,annotation="
	Each thread keeps an array of pointers to items that it is
	currently referencing.	Sort of an inside-out garbage collection
	mechanism, but one that requires the accessing code to explicitly
	state its needs.  Also requires read-side memory barriers on
	most architectures.
"
}

@conference{Michael02b
,author="Maged M. Michael"
,title="High Performance Dynamic Lock-Free Hash Tables and List-Based Sets"
,Year="2002"
,Month="August"
,booktitle="{Proceedings of the 14\textsuperscript{th} Annual ACM
Symposium on Parallel
Algorithms and Architecture}"
,pages="73-82"
,annotation="
	Like the title says...
"
}

@InProceedings{HerlihyLM02
,author={Maurice Herlihy and Victor Luchangco and Mark Moir}
,title="The Repeat Offender Problem: A Mechanism for Supporting Dynamic-Sized,
Lock-Free Data Structures"
,booktitle={Proceedings of 16\textsuperscript{th} International
Symposium on Distributed Computing}
,year=2002
,month="October"
,pages="339-353"
}

@article{Appavoo03a
,author="J. Appavoo and K. Hui and C. A. N. Soules and R. W. Wisniewski and
D. M. {Da Silva} and O. Krieger and M. A. Auslander and D. J. Edelsohn and
B. Gamsa and G. R. Ganger and P. McKenney and M. Ostrowski and
B. Rosenburg and M. Stumm and J. Xenidis"
,title="Enabling Autonomic Behavior in Systems Software With Hot Swapping"
,Year="2003"
,Month="January"
,journal="IBM Systems Journal"
,volume="42"
,number="1"
,pages="60-76"
}

@Conference{Arcangeli03
,Author="Andrea Arcangeli and Mingming Cao and Paul E. McKenney and
Dipankar Sarma"
,Title="Using Read-Copy Update Techniques for {System V IPC} in the
{Linux} 2.5 Kernel"
,Booktitle="Proceedings of the 2003 USENIX Annual Technical Conference
(FREENIX Track)"
,Publisher="USENIX Association"
,year="2003"
,month="June"
,pages="297-310"
}

@article{McKenney03a
,author="Paul E. McKenney"
,title="Using {RCU} in the {Linux} 2.5 Kernel"
,Year="2003"
,Month="October"
,journal="Linux Journal"
,volume="1"
,number="114"
,pages="18-26"
}

@techreport{Friedberg03a
,author="Stuart A. Friedberg"
,title="Lock-Free Wild Card Search Data Structure and Method"
,institution="US Patent and Trademark Office"
,address="Washington, DC"
,year="2003"
,number="US Patent 6,662,184 (contributed under GPL)"
,month="December"
,pages="112"
}

@article{McKenney04a
,author="Paul E. McKenney and Dipankar Sarma and Maneesh Soni"
,title="Scaling dcache with {RCU}"
,Year="2004"
,Month="January"
,journal="Linux Journal"
,volume="1"
,number="118"
,pages="38-46"
}

@Conference{McKenney04b
,Author="Paul E. McKenney"
,Title="{RCU} vs. Locking Performance on Different {CPUs}"
,Booktitle="{linux.conf.au}"
,Month="January"
,Year="2004"
,Address="Adelaide, Australia"
,note="Available:
\url{http://www.linux.org.au/conf/2004/abstracts.html#90}
\url{http://www.rdrop.com/users/paulmck/rclock/lockperf.2004.01.17a.pdf}
[Viewed June 23, 2004]"
}

@phdthesis{PaulEdwardMcKenneyPhD
,author="Paul E. McKenney"
,title="Exploiting Deferred Destruction:
An Analysis of Read-Copy-Update Techniques
in Operating System Kernels"
,school="OGI School of Science and Engineering at
Oregon Health and Sciences University"
,year="2004"
,note="Available:
\url{http://www.rdrop.com/users/paulmck/RCU/RCUdissertation.2004.07.14e1.pdf}
[Viewed October 15, 2004]"
}

@Conference{Sarma04c
,Author="Dipankar Sarma and Paul E. McKenney"
,Title="Making RCU Safe for Deep Sub-Millisecond Response Realtime Applications"
,Booktitle="Proceedings of the 2004 USENIX Annual Technical Conference
(FREENIX Track)"
,Publisher="USENIX Association"
,year="2004"
,month="June"
,pages="182-191"
}

@unpublished{JamesMorris04b
,Author="James Morris"
,Title="Recent Developments in {SELinux} Kernel Performance"
,month="December"
,year="2004"
,note="Available:
\url{http://www.livejournal.com/users/james_morris/2153.html}
[Viewed December 10, 2004]"
}

@unpublished{PaulMcKenney05a
,Author="Paul E. McKenney"
,Title="{[RFC]} {RCU} and {CONFIG\_PREEMPT\_RT} progress"
,month="May"
,year="2005"
,note="Available:
\url{http://lkml.org/lkml/2005/5/9/185}
[Viewed May 13, 2005]"
,annotation="
	First publication of working lock-based deferred free patches
	for the CONFIG_PREEMPT_RT environment.
"
}

@conference{PaulMcKenney05b
,Author="Paul E. McKenney and Dipankar Sarma"
,Title="Towards Hard Realtime Response from the Linux Kernel on SMP Hardware"
,Booktitle="linux.conf.au 2005"
,month="April"
,year="2005"
,address="Canberra, Australia"
,note="Available:
\url{http://www.rdrop.com/users/paulmck/RCU/realtimeRCU.2005.04.23a.pdf}
[Viewed May 13, 2005]"
,annotation="
	Realtime turns into making RCU yet more realtime friendly.
"
}

@conference{ThomasEHart2006a
,Author="Thomas E. Hart and Paul E. McKenney and Angela Demke Brown"
,Title="Making Lockless Synchronization Fast: Performance Implications
of Memory Reclamation"
,Booktitle="20\textsuperscript{th} {IEEE} International Parallel and
Distributed Processing Symposium"
,month="April"
,year="2006"
,day="25-29"
,address="Rhodes, Greece"
,annotation="
	Compares QSBR (AKA "classic RCU"), HPBR, EBR, and lock-free
	reference counting.
"
}

@Conference{PaulEMcKenney2006b
,Author="Paul E. McKenney and Dipankar Sarma and Ingo Molnar and
Suparna Bhattacharya"
,Title="Extending RCU for Realtime and Embedded Workloads"
,Booktitle="{Ottawa Linux Symposium}"
,Month="July"
,Year="2006"
,pages="v2 123-138"
,note="Available:
\url{http://www.linuxsymposium.org/2006/index_2006.php}
\url{http://www.rdrop.com/users/paulmck/RCU/OLSrtRCU.2006.08.11a.pdf}
[Viewed January 1, 2007]"
,annotation="
	Described how to improve the -rt implementation of realtime RCU.
"
}

@unpublished{PaulEMcKenney2006c
,Author="Paul E. McKenney"
,Title="Sleepable {RCU}"
,month="October"
,day="9"
,year="2006"
,note="Available:
\url{http://lwn.net/Articles/202847/}
Revised:
\url{http://www.rdrop.com/users/paulmck/RCU/srcu.2007.01.14a.pdf}
[Viewed August 21, 2006]"
,annotation="
	LWN article introducing SRCU.
"
}

@unpublished{RobertOlsson2006a
,Author="Robert Olsson and Stefan Nilsson"
,Title="{TRASH}: A dynamic {LC}-trie and hash data structure"
,month="August"
,day="18"
,year="2006"
,note="Available:
\url{http://www.nada.kth.se/~snilsson/public/papers/trash/trash.pdf}
[Viewed February 24, 2007]"
,annotation="
	RCU-protected dynamic trie-hash combination.
"
}

@unpublished{ThomasEHart2007a
,Author="Thomas E. Hart and Paul E. McKenney and Angela Demke Brown and Jonathan Walpole"
,Title="Performance of memory reclamation for lockless synchronization"
,journal="J. Parallel Distrib. Comput."
,year="2007"
,note="To appear in J. Parallel Distrib. Comput.
       \url{doi=10.1016/j.jpdc.2007.04.010}"
,annotation={
	Compares QSBR (AKA "classic RCU"), HPBR, EBR, and lock-free
	reference counting.  Journal version of ThomasEHart2006a.
}
}

@unpublished{PaulEMcKenney2007QRCUspin
,Author="Paul E. McKenney"
,Title="Using Promela and Spin to verify parallel algorithms"
,month="August"
,day="1"
,year="2007"
,note="Available:
\url{http://lwn.net/Articles/243851/}
[Viewed September 8, 2007]"
,annotation="
	LWN article describing Promela and spin, and also using Oleg
	Nesterov's QRCU as an example (with Paul McKenney's fastpath).
"
}

@unpublished{PaulEMcKenney2007PreemptibleRCU
,Author="Paul E. McKenney"
,Title="The design of preemptible read-copy-update"
,month="October"
,day="8"
,year="2007"
,note="Available:
\url{http://lwn.net/Articles/253651/}
[Viewed October 25, 2007]"
,annotation="
	LWN article describing the design of preemptible RCU.
"
}

########################################################################
#
#	"What is RCU?" LWN series.
#

@unpublished{PaulEMcKenney2007WhatIsRCUFundamentally
,Author="Paul E. McKenney and Jonathan Walpole"
,Title="What is {RCU}, Fundamentally?"
,month="December"
,day="17"
,year="2007"
,note="Available:
\url{http://lwn.net/Articles/262464/}
[Viewed December 27, 2007]"
,annotation="
	Lays out the three basic components of RCU: (1) publish-subscribe,
	(2) wait for pre-existing readers to complete, and (2) maintain
	multiple versions.
"
}

@unpublished{PaulEMcKenney2008WhatIsRCUUsage
,Author="Paul E. McKenney"
,Title="What is {RCU}? Part 2: Usage"
,month="January"
,day="4"
,year="2008"
,note="Available:
\url{http://lwn.net/Articles/263130/}
[Viewed January 4, 2008]"
,annotation="
	Lays out six uses of RCU:
	1. RCU is a Reader-Writer Lock Replacement
	2. RCU is a Restricted Reference-Counting Mechanism
	3. RCU is a Bulk Reference-Counting Mechanism
	4. RCU is a Poor Man's Garbage Collector
	5. RCU is a Way of Providing Existence Guarantees
	6. RCU is a Way of Waiting for Things to Finish 
"
}

@unpublished{PaulEMcKenney2008WhatIsRCUAPI
,Author="Paul E. McKenney"
,Title="{RCU} part 3: the {RCU} {API}"
,month="January"
,day="17"
,year="2008"
,note="Available:
\url{http://lwn.net/Articles/264090/}
[Viewed January 10, 2008]"
,annotation="
	Gives an overview of the Linux-kernel RCU API and a brief annotated RCU
	bibliography.
"
}

#
#	"What is RCU?" LWN series.
#
########################################################################

@article{DinakarGuniguntala2008IBMSysJ
,author="D. Guniguntala and P. E. McKenney and J. Triplett and J. Walpole"
,title="The read-copy-update mechanism for supporting real-time applications on shared-memory multiprocessor systems with {Linux}"
,Year="2008"
,Month="April"
,journal="IBM Systems Journal"
,volume="47"
,number="2"
,pages="@@-@@"
,annotation="
	RCU, realtime RCU, sleepable RCU, performance.
"
}

@article{PaulEMcKenney2008RCUOSR
,author="Paul E. McKenney and Jonathan Walpole"
,title="Introducing technology into the {Linux} kernel: a case study"
,Year="2008"
,journal="SIGOPS Oper. Syst. Rev."
,volume="42"
,number="5"
,pages="4--17"
,issn="0163-5980"
,doi={http://doi.acm.org/10.1145/1400097.1400099}
,publisher="ACM"
,address="New York, NY, USA"
,annotation={
	Linux changed RCU to a far greater degree than RCU has changed Linux.
}
}

@unpublished{PaulEMcKenney2008HierarchicalRCU
,Author="Paul E. McKenney"
,Title="Hierarchical {RCU}"
,month="November"
,day="3"
,year="2008"
,note="Available:
\url{http://lwn.net/Articles/305782/}
[Viewed November 6, 2008]"
,annotation="
	RCU with combining-tree-based grace-period detection,
	permitting it to handle thousands of CPUs.
"
}

@conference{PaulEMcKenney2009MaliciousURCU
,Author="Paul E. McKenney"
,Title="Using a Malicious User-Level {RCU} to Torture {RCU}-Based Algorithms"
,Booktitle="linux.conf.au 2009"
,month="January"
,year="2009"
,address="Hobart, Australia"
,note="Available:
\url{http://www.rdrop.com/users/paulmck/RCU/urcutorture.2009.01.22a.pdf}
[Viewed February 2, 2009]"
,annotation="
	Realtime RCU and torture-testing RCU uses.
"
}

@unpublished{MathieuDesnoyers2009URCU
,Author="Mathieu Desnoyers"
,Title="[{RFC} git tree] Userspace {RCU} (urcu) for {Linux}"
,month="February"
,day="5"
,year="2009"
,note="Available:
\url{http://lkml.org/lkml/2009/2/5/572}
\url{git://lttng.org/userspace-rcu.git}
[Viewed February 20, 2009]"
,annotation="
	Mathieu Desnoyers's user-space RCU implementation.
	git://lttng.org/userspace-rcu.git
"
}

@unpublished{PaulEMcKenney2009BloatWatchRCU
,Author="Paul E. McKenney"
,Title="{RCU}: The {Bloatwatch} Edition"
,month="March"
,day="17"
,year="2009"
,note="Available:
\url{http://lwn.net/Articles/323929/}
[Viewed March 20, 2009]"
,annotation="
	Uniprocessor assumptions allow simplified RCU implementation.
"
}

@unpublished{PaulEMcKenney2009expeditedRCU
,Author="Paul E. McKenney"
,Title="[{PATCH} -tip 0/3] expedited 'big hammer' {RCU} grace periods"
,month="June"
,day="25"
,year="2009"
,note="Available:
\url{http://lkml.org/lkml/2009/6/25/306}
[Viewed August 16, 2009]"
,annotation="
	First posting of expedited RCU to be accepted into -tip.
"
}

@unpublished{JoshTriplett2009RPHash
,Author="Josh Triplett"
,Title="Scalable concurrent hash tables via relativistic programming"
,month="September"
,year="2009"
,note="Linux Plumbers Conference presentation"
,annotation="
	RP fun with hash tables.
"
}

@phdthesis{MathieuDesnoyersPhD
, title  = "Low-Impact Operating System Tracing"
, author = "Mathieu Desnoyers"
, school = "Ecole Polytechnique de Montr\'{e}al"
, month  = "December"
, year   = 2009
,note="Available:
\url{http://www.lttng.org/pub/thesis/desnoyers-dissertation-2009-12.pdf}
[Viewed December 9, 2009]"
}

---

### Documentation RCU UP (`Documentation/RCU/UP.rst`)

.. _up_doc:

RCU on Uniprocessor Systems
===========================

A common misconception is that, on UP systems, the call_rcu() primitive
may immediately invoke its function.  The basis of this misconception
is that since there is only one CPU, it should not be necessary to
wait for anything else to get done, since there are no other CPUs for
anything else to be happening on.  Although this approach will *sort of*
work a surprising amount of the time, it is a very bad idea in general.
This document presents three examples that demonstrate exactly how bad
an idea this is.

Example 1: softirq Suicide
--------------------------

Suppose that an RCU-based algorithm scans a linked list containing
elements A, B, and C in process context, and can delete elements from
this same list in softirq context.  Suppose that the process-context scan
is referencing element B when it is interrupted by softirq processing,
which deletes element B, and then invokes call_rcu() to free element B
after a grace period.

Now, if call_rcu() were to directly invoke its arguments, then upon return
from softirq, the list scan would find itself referencing a newly freed
element B.  This situation can greatly decrease the life expectancy of
your kernel.

This same problem can occur if call_rcu() is invoked from a hardware
interrupt handler.

Example 2: Function-Call Fatality
---------------------------------

Of course, one could avert the suicide described in the preceding example
by having call_rcu() directly invoke its arguments only if it was called
from process context.  However, this can fail in a similar manner.

Suppose that an RCU-based algorithm again scans a linked list containing
elements A, B, and C in process context, but that it invokes a function
on each element as it is scanned.  Suppose further that this function
deletes element B from the list, then passes it to call_rcu() for deferred
freeing.  This may be a bit unconventional, but it is perfectly legal
RCU usage, since call_rcu() must wait for a grace period to elapse.
Therefore, in this case, allowing call_rcu() to immediately invoke
its arguments would cause it to fail to make the fundamental guarantee
underlying RCU, namely that call_rcu() defers invoking its arguments until
all RCU read-side critical sections currently executing have completed.

Quick Quiz #1:
	Why is it *not* legal to invoke synchronize_rcu() in this case?

:ref:`Answers to Quick Quiz <answer_quick_quiz_up>`

Example 3: Death by Deadlock
----------------------------

Suppose that call_rcu() is invoked while holding a lock, and that the
callback function must acquire this same lock.  In this case, if
call_rcu() were to directly invoke the callback, the result would
be self-deadlock *even if* this invocation occurred from a later
call_rcu() invocation a full grace period later.

In some cases, it would possible to restructure to code so that
the call_rcu() is delayed until after the lock is released.  However,
there are cases where this can be quite ugly:

1.	If a number of items need to be passed to call_rcu() within
	the same critical section, then the code would need to create
	a list of them, then traverse the list once the lock was
	released.

2.	In some cases, the lock will be held across some kernel API,
	so that delaying the call_rcu() until the lock is released
	requires that the data item be passed up via a common API.
	It is far better to guarantee that callbacks are invoked
	with no locks held than to have to modify such APIs to allow
	arbitrary data items to be passed back up through them.

If call_rcu() directly invokes the callback, painful locking restrictions
or API changes would be required.

Quick Quiz #2:
	What locking restriction must RCU callbacks respect?

:ref:`Answers to Quick Quiz <answer_quick_quiz_up>`

It is important to note that userspace RCU implementations *do*
permit call_rcu() to directly invoke callbacks, but only if a full
grace period has elapsed since those callbacks were queued.  This is
the case because some userspace environments are extremely constrained.
Nevertheless, people writing userspace RCU implementations are strongly
encouraged to avoid invoking callbacks from call_rcu(), thus obtaining
the deadlock-avoidance benefits called out above.

Summary
-------

Permitting call_rcu() to immediately invoke its arguments breaks RCU,
even on a UP system.  So do not do it!  Even on a UP system, the RCU
infrastructure *must* respect grace periods, and *must* invoke callbacks
from a known environment in which no locks are held.

Note that it *is* safe for synchronize_rcu() to return immediately on
UP systems, including PREEMPT SMP builds running on UP systems.

Quick Quiz #3:
	Why can't synchronize_rcu() return immediately on UP systems running
	preemptible RCU?

.. _answer_quick_quiz_up:

Answer to Quick Quiz #1:
	Why is it *not* legal to invoke synchronize_rcu() in this case?

	Because the calling function is scanning an RCU-protected linked
	list, and is therefore within an RCU read-side critical section.
	Therefore, the called function has been invoked within an RCU
	read-side critical section, and is not permitted to block.

Answer to Quick Quiz #2:
	What locking restriction must RCU callbacks respect?

	Any lock that is acquired within an RCU callback must be acquired
	elsewhere using an _bh variant of the spinlock primitive.
	For example, if "mylock" is acquired by an RCU callback, then
	a process-context acquisition of this lock must use something
	like spin_lock_bh() to acquire the lock.  Please note that
	it is also OK to use _irq variants of spinlocks, for example,
	spin_lock_irqsave().

	If the process-context code were to simply use spin_lock(),
	then, since RCU callbacks can be invoked from softirq context,
	the callback might be called from a softirq that interrupted
	the process-context critical section.  This would result in
	self-deadlock.

	This restriction might seem gratuitous, since very few RCU
	callbacks acquire locks directly.  However, a great many RCU
	callbacks do acquire locks *indirectly*, for example, via
	the kfree() primitive.

Answer to Quick Quiz #3:
	Why can't synchronize_rcu() return immediately on UP systems
	running preemptible RCU?

	Because some other task might have been preempted in the middle
	of an RCU read-side critical section.  If synchronize_rcu()
	simply immediately returned, it would prematurely signal the
	end of the grace period, which would come as a nasty shock to
	that other thread when it started running again.

---

### Documentation RCU Checklist (`Documentation/RCU/checklist.rst`)

.. SPDX-License-Identifier: GPL-2.0

================================
Review Checklist for RCU Patches
================================


This document contains a checklist for producing and reviewing patches
that make use of RCU.  Violating any of the rules listed below will
result in the same sorts of problems that leaving out a locking primitive
would cause.  This list is based on experiences reviewing such patches
over a rather long period of time, but improvements are always welcome!

0.	Is RCU being applied to a read-mostly situation?  If the data
	structure is updated more than about 10% of the time, then you
	should strongly consider some other approach, unless detailed
	performance measurements show that RCU is nonetheless the right
	tool for the job.  Yes, RCU does reduce read-side overhead by
	increasing write-side overhead, which is exactly why normal uses
	of RCU will do much more reading than updating.

	Another exception is where performance is not an issue, and RCU
	provides a simpler implementation.  An example of this situation
	is the dynamic NMI code in the Linux 2.6 kernel, at least on
	architectures where NMIs are rare.

	Yet another exception is where the low real-time latency of RCU's
	read-side primitives is critically important.

	One final exception is where RCU readers are used to prevent
	the ABA problem (https://en.wikipedia.org/wiki/ABA_problem)
	for lockless updates.  This does result in the mildly
	counter-intuitive situation where rcu_read_lock() and
	rcu_read_unlock() are used to protect updates, however, this
	approach can provide the same simplifications to certain types
	of lockless algorithms that garbage collectors do.

1.	Does the update code have proper mutual exclusion?

	RCU does allow *readers* to run (almost) naked, but *writers* must
	still use some sort of mutual exclusion, such as:

	a.	locking,
	b.	atomic operations, or
	c.	restricting updates to a single task.

	If you choose #b, be prepared to describe how you have handled
	memory barriers on weakly ordered machines (pretty much all of
	them -- even x86 allows later loads to be reordered to precede
	earlier stores), and be prepared to explain why this added
	complexity is worthwhile.  If you choose #c, be prepared to
	explain how this single task does not become a major bottleneck
	on large systems (for example, if the task is updating information
	relating to itself that other tasks can read, there by definition
	can be no bottleneck).	Note that the definition of "large" has
	changed significantly:	Eight CPUs was "large" in the year 2000,
	but a hundred CPUs was unremarkable in 2017.

2.	Do the RCU read-side critical sections make proper use of
	rcu_read_lock() and friends?  These primitives are needed
	to prevent grace periods from ending prematurely, which
	could result in data being unceremoniously freed out from
	under your read-side code, which can greatly increase the
	actuarial risk of your kernel.

	As a rough rule of thumb, any dereference of an RCU-protected
	pointer must be covered by rcu_read_lock(), rcu_read_lock_bh(),
	rcu_read_lock_sched(), or by the appropriate update-side lock.
	Explicit disabling of preemption (preempt_disable(), for example)
	can serve as rcu_read_lock_sched(), but is less readable and
	prevents lockdep from detecting locking issues.  Acquiring a
	raw spinlock also enters an RCU read-side critical section.

	The guard(rcu)() and scoped_guard(rcu) primitives designate
	the remainder of the current scope or the next statement,
	respectively, as the RCU read-side critical section.  Use of
	these guards can be less error-prone than rcu_read_lock(),
	rcu_read_unlock(), and friends.

	Please note that you *cannot* rely on code known to be built
	only in non-preemptible kernels.  Such code can and will break,
	especially in kernels built with CONFIG_PREEMPT_COUNT=y.

	Letting RCU-protected pointers "leak" out of an RCU read-side
	critical section is every bit as bad as letting them leak out
	from under a lock.  Unless, of course, you have arranged some
	other means of protection, such as a lock or a reference count
	*before* letting them out of the RCU read-side critical section.

3.	Does the update code tolerate concurrent accesses?

	The whole point of RCU is to permit readers to run without
	any locks or atomic operations.  This means that readers will
	be running while updates are in progress.  There are a number
	of ways to handle this concurrency, depending on the situation:

	a.	Use the RCU variants of the list and hlist update
		primitives to add, remove, and replace elements on
		an RCU-protected list.	Alternatively, use the other
		RCU-protected data structures that have been added to
		the Linux kernel.

		This is almost always the best approach.

	b.	Proceed as in (a) above, but also maintain per-element
		locks (that are acquired by both readers and writers)
		that guard per-element state.  Fields that the readers
		refrain from accessing can be guarded by some other lock
		acquired only by updaters, if desired.

		This also works quite well.

	c.	Make updates appear atomic to readers.	For example,
		pointer updates to properly aligned fields will
		appear atomic, as will individual atomic primitives.
		Sequences of operations performed under a lock will *not*
		appear to be atomic to RCU readers, nor will sequences
		of multiple atomic primitives.	One alternative is to
		move multiple individual fields to a separate structure,
		thus solving the multiple-field problem by imposing an
		additional level of indirection.

		This can work, but is starting to get a bit tricky.

	d.	Carefully order the updates and the reads so that readers
		see valid data at all phases of the update.  This is often
		more difficult than it sounds, especially given modern
		CPUs' tendency to reorder memory references.  One must
		usually liberally sprinkle memory-ordering operations
		through the code, making it difficult to understand and
		to test.  Where it works, it is better to use things
		like smp_store_release() and smp_load_acquire(), but in
		some cases the smp_mb() full memory barrier is required.

		As noted earlier, it is usually better to group the
		changing data into a separate structure, so that the
		change may be made to appear atomic by updating a pointer
		to reference a new structure containing updated values.

4.	Weakly ordered CPUs pose special challenges.  Almost all CPUs
	are weakly ordered -- even x86 CPUs allow later loads to be
	reordered to precede earlier stores.  RCU code must take all of
	the following measures to prevent memory-corruption problems:

	a.	Readers must maintain proper ordering of their memory
		accesses.  The rcu_dereference() primitive ensures that
		the CPU picks up the pointer before it picks up the data
		that the pointer points to.  This really is necessary
		on Alpha CPUs.

		The rcu_dereference() primitive is also an excellent
		documentation aid, letting the person reading the
		code know exactly which pointers are protected by RCU.
		Please note that compilers can also reorder code, and
		they are becoming increasingly aggressive about doing
		just that.  The rcu_dereference() primitive therefore also
		prevents destructive compiler optimizations.  However,
		with a bit of devious creativity, it is possible to
		mishandle the return value from rcu_dereference().
		Please see rcu_dereference.rst for more information.

		The rcu_dereference() primitive is used by the
		various "_rcu()" list-traversal primitives, such
		as the list_for_each_entry_rcu().  Note that it is
		perfectly legal (if redundant) for update-side code to
		use rcu_dereference() and the "_rcu()" list-traversal
		primitives.  This is particularly useful in code that
		is common to readers and updaters.  However, lockdep
		will complain if you access rcu_dereference() outside
		of an RCU read-side critical section.  See lockdep.rst
		to learn what to do about this.

		Of course, neither rcu_dereference() nor the "_rcu()"
		list-traversal primitives can substitute for a good
		concurrency design coordinating among multiple updaters.

	b.	If the list macros are being used, the list_add_tail_rcu()
		and list_add_rcu() primitives must be used in order
		to prevent weakly ordered machines from misordering
		structure initialization and pointer planting.
		Similarly, if the hlist macros are being used, the
		hlist_add_head_rcu() primitive is required.

	c.	If the list macros are being used, the list_del_rcu()
		primitive must be used to keep list_del()'s pointer
		poisoning from inflicting toxic effects on concurrent
		readers.  Similarly, if the hlist macros are being used,
		the hlist_del_rcu() primitive is required.

		The list_replace_rcu() and hlist_replace_rcu() primitives
		may be used to replace an old structure with a new one
		in their respective types of RCU-protected lists.

	d.	Rules similar to (4b) and (4c) apply to the "hlist_nulls"
		type of RCU-protected linked lists.

	e.	Updates must ensure that initialization of a given
		structure happens before pointers to that structure are
		publicized.  Use the rcu_assign_pointer() primitive
		when publicizing a pointer to a structure that can
		be traversed by an RCU read-side critical section.

5.	If any of call_rcu(), call_srcu(), call_rcu_tasks(), or
	call_rcu_tasks_trace() is used, the callback function may be
	invoked from softirq context, and in any case with bottom halves
	disabled.  In particular, this callback function cannot block.
	If you need the callback to block, run that code in a workqueue
	handler scheduled from the callback.  The queue_rcu_work()
	function does this for you in the case of call_rcu().

6.	Since synchronize_rcu() can block, it cannot be called
	from any sort of irq context.  The same rule applies
	for synchronize_srcu(), synchronize_rcu_expedited(),
	synchronize_srcu_expedited(), synchronize_rcu_tasks(),
	synchronize_rcu_tasks_rude(), and synchronize_rcu_tasks_trace().

	The expedited forms of these primitives have the same semantics
	as the non-expedited forms, but expediting is more CPU intensive.
	Use of the expedited primitives should be restricted to rare
	configuration-change operations that would not normally be
	undertaken while a real-time workload is running.  Note that
	IPI-sensitive real-time workloads can use the rcupdate.rcu_normal
	kernel boot parameter to completely disable expedited grace
	periods, though this might have performance implications.

	In particular, if you find yourself invoking one of the expedited
	primitives repeatedly in a loop, please do everyone a favor:
	Restructure your code so that it batches the updates, allowing
	a single non-expedited primitive to cover the entire batch.
	This will very likely be faster than the loop containing the
	expedited primitive, and will be much much easier on the rest
	of the system, especially to real-time workloads running on the
	rest of the system.  Alternatively, instead use asynchronous
	primitives such as call_rcu().

7.	As of v4.20, a given kernel implements only one RCU flavor, which
	is RCU-sched for PREEMPTION=n and RCU-preempt for PREEMPTION=y.
	If the updater uses call_rcu() or synchronize_rcu(), then
	the corresponding readers may use:  (1) rcu_read_lock() and
	rcu_read_unlock(), (2) any pair of primitives that disables
	and re-enables softirq, for example, rcu_read_lock_bh() and
	rcu_read_unlock_bh(), or (3) any pair of primitives that disables
	and re-enables preemption, for example, rcu_read_lock_sched() and
	rcu_read_unlock_sched().  If the updater uses synchronize_srcu()
	or call_srcu(), then the corresponding readers must use
	srcu_read_lock() and srcu_read_unlock(), and with the same
	srcu_struct.  The rules for the expedited RCU grace-period-wait
	primitives are the same as for their non-expedited counterparts.

	Similarly, it is necessary to correctly use the RCU Tasks flavors:

	a.	If the updater uses synchronize_rcu_tasks() or
		call_rcu_tasks(), then the readers must refrain from
		executing voluntary context switches, that is, from
		blocking.

	b.	If the updater uses call_rcu_tasks_trace()
		or synchronize_rcu_tasks_trace(), then the
		corresponding readers must use rcu_read_lock_trace()
		and rcu_read_unlock_trace().

	c.	If an updater uses synchronize_rcu_tasks_rude(),
		then the corresponding readers must use anything that
		disables preemption, for example, preempt_disable()
		and preempt_enable().

	Mixing things up will result in confusion and broken kernels, and
	has even resulted in an exploitable security issue.  Therefore,
	when using non-obvious pairs of primitives, commenting is
	of course a must.  One example of non-obvious pairing is
	the XDP feature in networking, which calls BPF programs from
	network-driver NAPI (softirq) context.	BPF relies heavily on RCU
	protection for its data structures, but because the BPF program
	invocation happens entirely within a single local_bh_disable()
	section in a NAPI poll cycle, this usage is safe.  The reason
	that this usage is safe is that readers can use anything that
	disables BH when updaters use call_rcu() or synchronize_rcu().

8.	Although synchronize_rcu() is slower than is call_rcu(),
	it usually results in simpler code.  So, unless update
	performance is critically important, the updaters cannot block,
	or the latency of synchronize_rcu() is visible from userspace,
	synchronize_rcu() should be used in preference to call_rcu().
	Furthermore, kfree_rcu() and kvfree_rcu() usually result
	in even simpler code than does synchronize_rcu() without
	synchronize_rcu()'s multi-millisecond latency.	So please take
	advantage of kfree_rcu()'s and kvfree_rcu()'s "fire and forget"
	memory-freeing capabilities where it applies.

	An especially important property of the synchronize_rcu()
	primitive is that it automatically self-limits: if grace periods
	are delayed for whatever reason, then the synchronize_rcu()
	primitive will correspondingly delay updates.  In contrast,
	code using call_rcu() should explicitly limit update rate in
	cases where grace periods are delayed, as failing to do so can
	result in excessive realtime latencies or even OOM conditions.

	Ways of gaining this self-limiting property when using call_rcu(),
	kfree_rcu(), or kvfree_rcu() include:

	a.	Keeping a count of the number of data-structure elements
		used by the RCU-protected data structure, including
		those waiting for a grace period to elapse.  Enforce a
		limit on this number, stalling updates as needed to allow
		previously deferred frees to complete.	Alternatively,
		limit only the number awaiting deferred free rather than
		the total number of elements.

		One way to stall the updates is to acquire the update-side
		mutex.	(Don't try this with a spinlock -- other CPUs
		spinning on the lock could prevent the grace period
		from ever ending.)  Another way to stall the updates
		is for the updates to use a wrapper function around
		the memory allocator, so that this wrapper function
		simulates OOM when there is too much memory awaiting an
		RCU grace period.  There are of course many other
		variations on this theme.

	b.	Limiting update rate.  For example, if updates occur only
		once per hour, then no explicit rate limiting is
		required, unless your system is already badly broken.
		Older versions of the dcache subsystem take this approach,
		guarding updates with a global lock, limiting their rate.

	c.	Trusted update -- if updates can only be done manually by
		superuser or some other trusted user, then it might not
		be necessary to automatically limit them.  The theory
		here is that superuser already has lots of ways to crash
		the machine.

	d.	Periodically invoke rcu_barrier(), permitting a limited
		number of updates per grace period.

	The same cautions apply to call_srcu(), call_rcu_tasks(), and
	call_rcu_tasks_trace().  This is why there is an srcu_barrier(),
	rcu_barrier_tasks(), and rcu_barrier_tasks_trace(), respectively.

	Note that although these primitives do take action to avoid
	memory exhaustion when any given CPU has too many callbacks,
	a determined user or administrator can still exhaust memory.
	This is especially the case if a system with a large number of
	CPUs has been configured to offload all of its RCU callbacks onto
	a single CPU, or if the system has relatively little free memory.

9.	All RCU list-traversal primitives, which include
	rcu_dereference(), list_for_each_entry_rcu(), and
	list_for_each_safe_rcu(), must be either within an RCU read-side
	critical section or must be protected by appropriate update-side
	locks.	RCU read-side critical sections are delimited by
	rcu_read_lock() and rcu_read_unlock(), or by similar primitives
	such as rcu_read_lock_bh() and rcu_read_unlock_bh(), in which
	case the matching rcu_dereference() primitive must be used in
	order to keep lockdep happy, in this case, rcu_dereference_bh().

	The reason that it is permissible to use RCU list-traversal
	primitives when the update-side lock is held is that doing so
	can be quite helpful in reducing code bloat when common code is
	shared between readers and updaters.  Additional primitives
	are provided for this case, as discussed in lockdep.rst.

	One exception to this rule is when data is only ever added to
	the linked data structure, and is never removed during any
	time that readers might be accessing that structure.  In such
	cases, READ_ONCE() may be used in place of rcu_dereference()
	and the read-side markers (rcu_read_lock() and rcu_read_unlock(),
	for example) may be omitted.

10.	Conversely, if you are in an RCU read-side critical section,
	and you don't hold the appropriate update-side lock, you *must*
	use the "_rcu()" variants of the list macros.  Failing to do so
	will break Alpha, cause aggressive compilers to generate bad code,
	and confuse people trying to understand your code.

11.	Any lock acquired by an RCU callback must be acquired elsewhere
	with softirq disabled, e.g., via spin_lock_bh().  Failing to
	disable softirq on a given acquisition of that lock will result
	in deadlock as soon as the RCU softirq handler happens to run
	your RCU callback while interrupting that acquisition's critical
	section.

12.	RCU callbacks can be and are executed in parallel.  In many cases,
	the callback code simply wrappers around kfree(), so that this
	is not an issue (or, more accurately, to the extent that it is
	an issue, the memory-allocator locking handles it).  However,
	if the callbacks do manipulate a shared data structure, they
	must use whatever locking or other synchronization is required
	to safely access and/or modify that data structure.

	Do not assume that RCU callbacks will be executed on the same
	CPU that executed the corresponding call_rcu(), call_srcu(),
	call_rcu_tasks(), or call_rcu_tasks_trace().  For example, if
	a given CPU goes offline while having an RCU callback pending,
	then that RCU callback will execute on some surviving CPU.
	(If this was not the case, a self-spawning RCU callback would
	prevent the victim CPU from ever going offline.)  Furthermore,
	CPUs designated by rcu_nocbs= might well *always* have their
	RCU callbacks executed on some other CPUs, in fact, for some
	real-time workloads, this is the whole point of using the
	rcu_nocbs= kernel boot parameter.

	In addition, do not assume that callbacks queued in a given order
	will be invoked in that order, even if they all are queued on the
	same CPU.  Furthermore, do not assume that same-CPU callbacks will
	be invoked serially.  For example, in recent kernels, CPUs can be
	switched between offloaded and de-offloaded callback invocation,
	and while a given CPU is undergoing such a switch, its callbacks
	might be concurrently invoked by that CPU's softirq handler and
	that CPU's rcuo kthread.  At such times, that CPU's callbacks
	might be executed both concurrently and out of order.

13.	Unlike most flavors of RCU, it *is* permissible to block in an
	SRCU read-side critical section (demarked by srcu_read_lock()
	and srcu_read_unlock()), hence the "SRCU": "sleepable RCU".
	As with RCU, guard(srcu)() and scoped_guard(srcu) forms are
	available, and often provide greater ease of use.  Please note
	that if you don't need to sleep in read-side critical sections,
	you should be using RCU rather than SRCU, because RCU is almost
	always faster and easier to use than is SRCU.

	Also unlike other forms of RCU, explicit initialization and
	cleanup is required either at build time via DEFINE_SRCU()
	or DEFINE_STATIC_SRCU() or at runtime via init_srcu_struct()
	and cleanup_srcu_struct().  These last two are passed a
	"struct srcu_struct" that defines the scope of a given
	SRCU domain.  Once initialized, the srcu_struct is passed
	to srcu_read_lock(), srcu_read_unlock() synchronize_srcu(),
	synchronize_srcu_expedited(), and call_srcu().	A given
	synchronize_srcu() waits only for SRCU read-side critical
	sections governed by srcu_read_lock() and srcu_read_unlock()
	calls that have been passed the same srcu_struct.  This property
	is what makes sleeping read-side critical sections tolerable --
	a given subsystem delays only its own updates, not those of other
	subsystems using SRCU.	Therefore, SRCU is less prone to OOM the
	system than RCU would be if RCU's read-side critical sections
	were permitted to sleep.

	The ability to sleep in read-side critical sections does not
	come for free.	First, corresponding srcu_read_lock() and
	srcu_read_unlock() calls must be passed the same srcu_struct.
	Second, grace-period-detection overhead is amortized only
	over those updates sharing a given srcu_struct, rather than
	being globally amortized as they are for other forms of RCU.
	Therefore, SRCU should be used in preference to rw_semaphore
	only in extremely read-intensive situations, or in situations
	requiring SRCU's read-side deadlock immunity or low read-side
	realtime latency.  You should also consider percpu_rw_semaphore
	when you need lightweight readers.

	SRCU's expedited primitive (synchronize_srcu_expedited())
	never sends IPIs to other CPUs, so it is easier on
	real-time workloads than is synchronize_rcu_expedited().

	It is also permissible to sleep in RCU Tasks Trace read-side
	critical section, which are delimited by rcu_read_lock_trace()
	and rcu_read_unlock_trace().  However, this is a specialized
	flavor of RCU, and you should not use it without first checking
	with its current users.  In most cases, you should instead
	use SRCU.  As with RCU and SRCU, guard(rcu_tasks_trace)() and
	scoped_guard(rcu_tasks_trace) are available, and often provide
	greater ease of use.

	Note that rcu_assign_pointer() relates to SRCU just as it does to
	other forms of RCU, but instead of rcu_dereference() you should
	use srcu_dereference() in order to avoid lockdep splats.

14.	The whole point of call_rcu(), synchronize_rcu(), and friends
	is to wait until all pre-existing readers have finished before
	carrying out some otherwise-destructive operation.  It is
	therefore critically important to *first* remove any path
	that readers can follow that could be affected by the
	destructive operation, and *only then* invoke call_rcu(),
	synchronize_rcu(), or friends.

	Because these primitives only wait for pre-existing readers, it
	is the caller's responsibility to guarantee that any subsequent
	readers will execute safely.

15.	The various RCU read-side primitives do *not* necessarily contain
	memory barriers.  You should therefore plan for the CPU
	and the compiler to freely reorder code into and out of RCU
	read-side critical sections.  It is the responsibility of the
	RCU update-side primitives to deal with this.

	For SRCU readers, you can use smp_mb__after_srcu_read_unlock()
	immediately after an srcu_read_unlock() to get a full barrier.

16.	Use CONFIG_PROVE_LOCKING, CONFIG_DEBUG_OBJECTS_RCU_HEAD, and the
	__rcu sparse checks to validate your RCU code.	These can help
	find problems as follows:

	CONFIG_PROVE_LOCKING:
		check that accesses to RCU-protected data structures
		are carried out under the proper RCU read-side critical
		section, while holding the right combination of locks,
		or whatever other conditions are appropriate.

	CONFIG_DEBUG_OBJECTS_RCU_HEAD:
		check that you don't pass the same object to call_rcu()
		(or friends) before an RCU grace period has elapsed
		since the last time that you passed that same object to
		call_rcu() (or friends).

	CONFIG_RCU_STRICT_GRACE_PERIOD:
		combine with KASAN to check for pointers leaked out
		of RCU read-side critical sections.  This Kconfig
		option is tough on both performance and scalability,
		and so is limited to four-CPU systems.

	__rcu sparse checks:
		tag the pointer to the RCU-protected data structure
		with __rcu, and sparse will warn you if you access that
		pointer without the services of one of the variants
		of rcu_dereference().

	These debugging aids can help you find problems that are
	otherwise extremely difficult to spot.

17.	If you pass a callback function defined within a module
	to one of call_rcu(), call_srcu(), call_rcu_tasks(), or
	call_rcu_tasks_trace(), then it is necessary to wait for all
	pending callbacks to be invoked before unloading that module.
	Note that it is absolutely *not* sufficient to wait for a grace
	period!  For example, synchronize_rcu() implementation is *not*
	guaranteed to wait for callbacks registered on other CPUs via
	call_rcu().  Or even on the current CPU if that CPU recently
	went offline and came back online.

	You instead need to use one of the barrier functions:

	-	call_rcu() -> rcu_barrier()
	-	call_srcu() -> srcu_barrier()
	-	call_rcu_tasks() -> rcu_barrier_tasks()
	-	call_rcu_tasks_trace() -> rcu_barrier_tasks_trace()

	However, these barrier functions are absolutely *not* guaranteed
	to wait for a grace period.  For example, if there are no
	call_rcu() callbacks queued anywhere in the system, rcu_barrier()
	can and will return immediately.

	So if you need to wait for both a grace period and for all
	pre-existing callbacks, you will need to invoke both functions,
	with the pair depending on the flavor of RCU:

	-	Either synchronize_rcu() or synchronize_rcu_expedited(),
		together with rcu_barrier()
	-	Either synchronize_srcu() or synchronize_srcu_expedited(),
		together with and srcu_barrier()
	-	synchronize_rcu_tasks() and rcu_barrier_tasks()
	-	synchronize_tasks_trace() and rcu_barrier_tasks_trace()

	If necessary, you can use something like workqueues to execute
	the requisite pair of functions concurrently.

	See rcubarrier.rst for more information.

---

### Documentation RCU Index (`Documentation/RCU/index.rst`)

.. SPDX-License-Identifier: GPL-2.0

.. _rcu_handbook:

============
RCU Handbook
============

.. toctree::
   :maxdepth: 2

   checklist
   lockdep
   lockdep-splat
   rcubarrier
   rcu_dereference
   whatisRCU
   rcu
   rculist_nulls
   rcuref
   torture
   stallwarn
   listRCU
   NMI-RCU
   UP

   Design/Memory-Ordering/Tree-RCU-Memory-Ordering
   Design/Expedited-Grace-Periods/Expedited-Grace-Periods
   Design/Requirements/Requirements
   Design/Data-Structures/Data-Structures

.. only:: subproject and html

   Indices
   =======

   * :ref:`genindex`

---

### Documentation RCU ListRCU (`Documentation/RCU/listRCU.rst`)

.. _list_rcu_doc:

Using RCU to Protect Read-Mostly Linked Lists
=============================================

One of the most common uses of RCU is protecting read-mostly linked lists
(``struct list_head`` in list.h).  One big advantage of this approach is
that all of the required memory ordering is provided by the list macros.
This document describes several list-based RCU use cases.

When iterating a list while holding the rcu_read_lock(), writers may
modify the list.  The reader is guaranteed to see all of the elements
which were added to the list before they acquired the rcu_read_lock()
and are still on the list when they drop the rcu_read_unlock().
Elements which are added to, or removed from the list may or may not
be seen.  If the writer calls list_replace_rcu(), the reader may see
either the old element or the new element; they will not see both,
nor will they see neither.


Example 1: Read-mostly list: Deferred Destruction
-------------------------------------------------

A widely used usecase for RCU lists in the kernel is lockless iteration over
all processes in the system. ``task_struct::tasks`` represents the list node that
links all the processes. The list can be traversed in parallel to any list
additions or removals.

The traversal of the list is done using ``for_each_process()`` which is defined
by the 2 macros::

	#define next_task(p) \
		list_entry_rcu((p)->tasks.next, struct task_struct, tasks)

	#define for_each_process(p) \
		for (p = &init_task ; (p = next_task(p)) != &init_task ; )

The code traversing the list of all processes typically looks like::

	rcu_read_lock();
	for_each_process(p) {
		/* Do something with p */
	}
	rcu_read_unlock();

The simplified and heavily inlined code for removing a process from a
task list is::

	void release_task(struct task_struct *p)
	{
		write_lock(&tasklist_lock);
		list_del_rcu(&p->tasks);
		write_unlock(&tasklist_lock);
		call_rcu(&p->rcu, delayed_put_task_struct);
	}

When a process exits, ``release_task()`` calls ``list_del_rcu(&p->tasks)``
via __exit_signal() and __unhash_process() under ``tasklist_lock``
writer lock protection.  The list_del_rcu() invocation removes
the task from the list of all tasks. The ``tasklist_lock``
prevents concurrent list additions/removals from corrupting the
list. Readers using ``for_each_process()`` are not protected with the
``tasklist_lock``. To prevent readers from noticing changes in the list
pointers, the ``task_struct`` object is freed only after one or more
grace periods elapse, with the help of call_rcu(), which is invoked via
put_task_struct_rcu_user(). This deferring of destruction ensures that
any readers traversing the list will see valid ``p->tasks.next`` pointers
and deletion/freeing can happen in parallel with traversal of the list.
This pattern is also called an **existence lock**, since RCU refrains
from invoking the delayed_put_task_struct() callback function until
all existing readers finish, which guarantees that the ``task_struct``
object in question will remain in existence until after the completion
of all RCU readers that might possibly have a reference to that object.


Example 2: Read-Side Action Taken Outside of Lock: No In-Place Updates
----------------------------------------------------------------------

Some reader-writer locking use cases compute a value while holding
the read-side lock, but continue to use that value after that lock is
released.  These use cases are often good candidates for conversion
to RCU.  One prominent example involves network packet routing.
Because the packet-routing data tracks the state of equipment outside
of the computer, it will at times contain stale data.  Therefore, once
the route has been computed, there is no need to hold the routing table
static during transmission of the packet.  After all, you can hold the
routing table static all you want, but that won't keep the external
Internet from changing, and it is the state of the external Internet
that really matters.  In addition, routing entries are typically added
or deleted, rather than being modified in place.  This is a rare example
of the finite speed of light and the non-zero size of atoms actually
helping make synchronization be lighter weight.

A straightforward example of this type of RCU use case may be found in
the system-call auditing support.  For example, a reader-writer locked
implementation of ``audit_filter_task()`` might be as follows::

	static enum audit_state audit_filter_task(struct task_struct *tsk, char **key)
	{
		struct audit_entry *e;
		enum audit_state   state;

		read_lock(&auditsc_lock);
		/* Note: audit_filter_mutex held by caller. */
		list_for_each_entry(e, &audit_tsklist, list) {
			if (audit_filter_rules(tsk, &e->rule, NULL, &state)) {
				if (state == AUDIT_STATE_RECORD)
					*key = kstrdup(e->rule.filterkey, GFP_ATOMIC);
				read_unlock(&auditsc_lock);
				return state;
			}
		}
		read_unlock(&auditsc_lock);
		return AUDIT_BUILD_CONTEXT;
	}

Here the list is searched under the lock, but the lock is dropped before
the corresponding value is returned.  By the time that this value is acted
on, the list may well have been modified.  This makes sense, since if
you are turning auditing off, it is OK to audit a few extra system calls.

This means that RCU can be easily applied to the read side, as follows::

	static enum audit_state audit_filter_task(struct task_struct *tsk, char **key)
	{
		struct audit_entry *e;
		enum audit_state   state;

		rcu_read_lock();
		/* Note: audit_filter_mutex held by caller. */
		list_for_each_entry_rcu(e, &audit_tsklist, list) {
			if (audit_filter_rules(tsk, &e->rule, NULL, &state)) {
				if (state == AUDIT_STATE_RECORD)
					*key = kstrdup(e->rule.filterkey, GFP_ATOMIC);
				rcu_read_unlock();
				return state;
			}
		}
		rcu_read_unlock();
		return AUDIT_BUILD_CONTEXT;
	}

The read_lock() and read_unlock() calls have become rcu_read_lock()
and rcu_read_unlock(), respectively, and the list_for_each_entry()
has become list_for_each_entry_rcu().  The **_rcu()** list-traversal
primitives add READ_ONCE() and diagnostic checks for incorrect use
outside of an RCU read-side critical section.

The changes to the update side are also straightforward. A reader-writer lock
might be used as follows for deletion and insertion in these simplified
versions of audit_del_rule() and audit_add_rule()::

	static inline int audit_del_rule(struct audit_rule *rule,
					 struct list_head *list)
	{
		struct audit_entry *e;

		write_lock(&auditsc_lock);
		list_for_each_entry(e, list, list) {
			if (!audit_compare_rule(rule, &e->rule)) {
				list_del(&e->list);
				write_unlock(&auditsc_lock);
				return 0;
			}
		}
		write_unlock(&auditsc_lock);
		return -EFAULT;		/* No matching rule */
	}

	static inline int audit_add_rule(struct audit_entry *entry,
					 struct list_head *list)
	{
		write_lock(&auditsc_lock);
		if (entry->rule.flags & AUDIT_PREPEND) {
			entry->rule.flags &= ~AUDIT_PREPEND;
			list_add(&entry->list, list);
		} else {
			list_add_tail(&entry->list, list);
		}
		write_unlock(&auditsc_lock);
		return 0;
	}

Following are the RCU equivalents for these two functions::

	static inline int audit_del_rule(struct audit_rule *rule,
					 struct list_head *list)
	{
		struct audit_entry *e;

		/* No need to use the _rcu iterator here, since this is the only
		 * deletion routine. */
		list_for_each_entry(e, list, list) {
			if (!audit_compare_rule(rule, &e->rule)) {
				list_del_rcu(&e->list);
				call_rcu(&e->rcu, audit_free_rule);
				return 0;
			}
		}
		return -EFAULT;		/* No matching rule */
	}

	static inline int audit_add_rule(struct audit_entry *entry,
					 struct list_head *list)
	{
		if (entry->rule.flags & AUDIT_PREPEND) {
			entry->rule.flags &= ~AUDIT_PREPEND;
			list_add_rcu(&entry->list, list);
		} else {
			list_add_tail_rcu(&entry->list, list);
		}
		return 0;
	}

Normally, the write_lock() and write_unlock() would be replaced by a
spin_lock() and a spin_unlock(). But in this case, all callers hold
``audit_filter_mutex``, so no additional locking is required. The
auditsc_lock can therefore be eliminated, since use of RCU eliminates the
need for writers to exclude readers.

The list_del(), list_add(), and list_add_tail() primitives have been
replaced by list_del_rcu(), list_add_rcu(), and list_add_tail_rcu().
The **_rcu()** list-manipulation primitives add memory barriers that are
needed on weakly ordered CPUs.  The list_del_rcu() primitive omits the
pointer poisoning debug-assist code that would otherwise cause concurrent
readers to fail spectacularly.

So, when readers can tolerate stale data and when entries are either added or
deleted, without in-place modification, it is very easy to use RCU!


Example 3: Handling In-Place Updates
------------------------------------

The system-call auditing code does not update auditing rules in place.  However,
if it did, the reader-writer-locked code to do so might look as follows
(assuming only ``field_count`` is updated, otherwise, the added fields would
need to be filled in)::

	static inline int audit_upd_rule(struct audit_rule *rule,
					 struct list_head *list,
					 __u32 newaction,
					 __u32 newfield_count)
	{
		struct audit_entry *e;
		struct audit_entry *ne;

		write_lock(&auditsc_lock);
		/* Note: audit_filter_mutex held by caller. */
		list_for_each_entry(e, list, list) {
			if (!audit_compare_rule(rule, &e->rule)) {
				e->rule.action = newaction;
				e->rule.field_count = newfield_count;
				write_unlock(&auditsc_lock);
				return 0;
			}
		}
		write_unlock(&auditsc_lock);
		return -EFAULT;		/* No matching rule */
	}

The RCU version creates a copy, updates the copy, then replaces the old
entry with the newly updated entry.  This sequence of actions, allowing
concurrent reads while making a copy to perform an update, is what gives
RCU (*read-copy update*) its name.

The RCU version of audit_upd_rule() is as follows::

	static inline int audit_upd_rule(struct audit_rule *rule,
					 struct list_head *list,
					 __u32 newaction,
					 __u32 newfield_count)
	{
		struct audit_entry *e;
		struct audit_entry *ne;

		list_for_each_entry(e, list, list) {
			if (!audit_compare_rule(rule, &e->rule)) {
				ne = kmalloc(sizeof(*entry), GFP_ATOMIC);
				if (ne == NULL)
					return -ENOMEM;
				audit_copy_rule(&ne->rule, &e->rule);
				ne->rule.action = newaction;
				ne->rule.field_count = newfield_count;
				list_replace_rcu(&e->list, &ne->list);
				call_rcu(&e->rcu, audit_free_rule);
				return 0;
			}
		}
		return -EFAULT;		/* No matching rule */
	}

Again, this assumes that the caller holds ``audit_filter_mutex``.  Normally, the
writer lock would become a spinlock in this sort of code.

The update_lsm_rule() does something very similar, for those who would
prefer to look at real Linux-kernel code.

Another use of this pattern can be found in the openswitch driver's *connection
tracking table* code in ``ct_limit_set()``.  The table holds connection tracking
entries and has a limit on the maximum entries.  There is one such table
per-zone and hence one *limit* per zone.  The zones are mapped to their limits
through a hashtable using an RCU-managed hlist for the hash chains. When a new
limit is set, a new limit object is allocated and ``ct_limit_set()`` is called
to replace the old limit object with the new one using list_replace_rcu().
The old limit object is then freed after a grace period using kfree_rcu().


Example 4: Eliminating Stale Data
---------------------------------

The auditing example above tolerates stale data, as do most algorithms
that are tracking external state.  After all, given there is a delay
from the time the external state changes before Linux becomes aware
of the change, and so as noted earlier, a small quantity of additional
RCU-induced staleness is generally not a problem.

However, there are many examples where stale data cannot be tolerated.
One example in the Linux kernel is the System V IPC (see the shm_lock()
function in ipc/shm.c).  This code checks a *deleted* flag under a
per-entry spinlock, and, if the *deleted* flag is set, pretends that the
entry does not exist.  For this to be helpful, the search function must
return holding the per-entry spinlock, as shm_lock() does in fact do.

.. _quick_quiz:

Quick Quiz:
	For the deleted-flag technique to be helpful, why is it necessary
	to hold the per-entry lock while returning from the search function?

:ref:`Answer to Quick Quiz <quick_quiz_answer>`

If the system-call audit module were to ever need to reject stale data, one way
to accomplish this would be to add a ``deleted`` flag and a ``lock`` spinlock to the
``audit_entry`` structure, and modify audit_filter_task() as follows::

	static struct audit_entry *audit_filter_task(struct task_struct *tsk, char **key)
	{
		struct audit_entry *e;
		enum audit_state   state;

		rcu_read_lock();
		list_for_each_entry_rcu(e, &audit_tsklist, list) {
			if (audit_filter_rules(tsk, &e->rule, NULL, &state)) {
				spin_lock(&e->lock);
				if (e->deleted) {
					spin_unlock(&e->lock);
					rcu_read_unlock();
					return NULL;
				}
				rcu_read_unlock();
				if (state == AUDIT_STATE_RECORD)
					*key = kstrdup(e->rule.filterkey, GFP_ATOMIC);
				/* As long as e->lock is held, e is valid and
				 * its value is not stale */
				return e;
			}
		}
		rcu_read_unlock();
		return NULL;
	}

The ``audit_del_rule()`` function would need to set the ``deleted`` flag under the
spinlock as follows::

	static inline int audit_del_rule(struct audit_rule *rule,
					 struct list_head *list)
	{
		struct audit_entry *e;

		/* No need to use the _rcu iterator here, since this
		 * is the only deletion routine. */
		list_for_each_entry(e, list, list) {
			if (!audit_compare_rule(rule, &e->rule)) {
				spin_lock(&e->lock);
				list_del_rcu(&e->list);
				e->deleted = 1;
				spin_unlock(&e->lock);
				call_rcu(&e->rcu, audit_free_rule);
				return 0;
			}
		}
		return -EFAULT;		/* No matching rule */
	}

This too assumes that the caller holds ``audit_filter_mutex``.

Note that this example assumes that entries are only added and deleted.
Additional mechanism is required to deal correctly with the update-in-place
performed by audit_upd_rule().  For one thing, audit_upd_rule() would
need to hold the locks of both the old ``audit_entry`` and its replacement
while executing the list_replace_rcu().


Example 5: Skipping Stale Objects
---------------------------------

For some use cases, reader performance can be improved by skipping
stale objects during read-side list traversal, where stale objects
are those that will be removed and destroyed after one or more grace
periods. One such example can be found in the timerfd subsystem. When a
``CLOCK_REALTIME`` clock is reprogrammed (for example due to setting
of the system time) then all programmed ``timerfds`` that depend on
this clock get triggered and processes waiting on them are awakened in
advance of their scheduled expiry. To facilitate this, all such timers
are added to an RCU-managed ``cancel_list`` when they are setup in
``timerfd_setup_cancel()``::

	static void timerfd_setup_cancel(struct timerfd_ctx *ctx, int flags)
	{
		spin_lock(&ctx->cancel_lock);
		if ((ctx->clockid == CLOCK_REALTIME ||
		     ctx->clockid == CLOCK_REALTIME_ALARM) &&
		    (flags & TFD_TIMER_ABSTIME) && (flags & TFD_TIMER_CANCEL_ON_SET)) {
			if (!ctx->might_cancel) {
				ctx->might_cancel = true;
				spin_lock(&cancel_lock);
				list_add_rcu(&ctx->clist, &cancel_list);
				spin_unlock(&cancel_lock);
			}
		} else {
			__timerfd_remove_cancel(ctx);
		}
		spin_unlock(&ctx->cancel_lock);
	}

When a timerfd is freed (fd is closed), then the ``might_cancel``
flag of the timerfd object is cleared, the object removed from the
``cancel_list`` and destroyed, as shown in this simplified and inlined
version of timerfd_release()::

	int timerfd_release(struct inode *inode, struct file *file)
	{
		struct timerfd_ctx *ctx = file->private_data;

		spin_lock(&ctx->cancel_lock);
		if (ctx->might_cancel) {
			ctx->might_cancel = false;
			spin_lock(&cancel_lock);
			list_del_rcu(&ctx->clist);
			spin_unlock(&cancel_lock);
		}
		spin_unlock(&ctx->cancel_lock);

		if (isalarm(ctx))
			alarm_cancel(&ctx->t.alarm);
		else
			hrtimer_cancel(&ctx->t.tmr);
		kfree_rcu(ctx, rcu);
		return 0;
	}

If the ``CLOCK_REALTIME`` clock is set, for example by a time server, the
hrtimer framework calls ``timerfd_clock_was_set()`` which walks the
``cancel_list`` and wakes up processes waiting on the timerfd. While iterating
the ``cancel_list``, the ``might_cancel`` flag is consulted to skip stale
objects::

	void timerfd_clock_was_set(void)
	{
		ktime_t moffs = ktime_mono_to_real(0);
		struct timerfd_ctx *ctx;
		unsigned long flags;

		rcu_read_lock();
		list_for_each_entry_rcu(ctx, &cancel_list, clist) {
			if (!ctx->might_cancel)
				continue;
			spin_lock_irqsave(&ctx->wqh.lock, flags);
			if (ctx->moffs != moffs) {
				ctx->moffs = KTIME_MAX;
				ctx->ticks++;
				wake_up_locked_poll(&ctx->wqh, EPOLLIN);
			}
			spin_unlock_irqrestore(&ctx->wqh.lock, flags);
		}
		rcu_read_unlock();
	}

The key point is that because RCU-protected traversal of the
``cancel_list`` happens concurrently with object addition and removal,
sometimes the traversal can access an object that has been removed from
the list. In this example, a flag is used to skip such objects.


Summary
-------

Read-mostly list-based data structures that can tolerate stale data are
the most amenable to use of RCU.  The simplest case is where entries are
either added or deleted from the data structure (or atomically modified
in place), but non-atomic in-place modifications can be handled by making
a copy, updating the copy, then replacing the original with the copy.
If stale data cannot be tolerated, then a *deleted* flag may be used
in conjunction with a per-entry spinlock in order to allow the search
function to reject newly deleted data.

.. _quick_quiz_answer:

Answer to Quick Quiz:
	For the deleted-flag technique to be helpful, why is it necessary
	to hold the per-entry lock while returning from the search function?

	If the search function drops the per-entry lock before returning,
	then the caller will be processing stale data in any case.  If it
	is really OK to be processing stale data, then you don't need a
	*deleted* flag.  If processing stale data really is a problem,
	then you need to hold the per-entry lock across all of the code
	that uses the value that was returned.

:ref:`Back to Quick Quiz <quick_quiz>`

---

### Documentation RCU Lockdep Splat (`Documentation/RCU/lockdep-splat.rst`)

.. SPDX-License-Identifier: GPL-2.0

=================
Lockdep-RCU Splat
=================

Lockdep-RCU was added to the Linux kernel in early 2010
(http://lwn.net/Articles/371986/).  This facility checks for some common
misuses of the RCU API, most notably using one of the rcu_dereference()
family to access an RCU-protected pointer without the proper protection.
When such misuse is detected, an lockdep-RCU splat is emitted.

The usual cause of a lockdep-RCU splat is someone accessing an
RCU-protected data structure without either (1) being in the right kind of
RCU read-side critical section or (2) holding the right update-side lock.
This problem can therefore be serious: it might result in random memory
overwriting or worse.  There can of course be false positives, this
being the real world and all that.

So let's look at an example RCU lockdep splat from 3.0-rc5, one that
has long since been fixed::

    =============================
    WARNING: suspicious RCU usage
    -----------------------------
    block/cfq-iosched.c:2776 suspicious rcu_dereference_protected() usage!

other info that might help us debug this::

    rcu_scheduler_active = 1, debug_locks = 0
    3 locks held by scsi_scan_6/1552:
    #0:  (&shost->scan_mutex){+.+.}, at: [<ffffffff8145efca>]
    scsi_scan_host_selected+0x5a/0x150
    #1:  (&eq->sysfs_lock){+.+.}, at: [<ffffffff812a5032>]
    elevator_exit+0x22/0x60
    #2:  (&(&q->__queue_lock)->rlock){-.-.}, at: [<ffffffff812b6233>]
    cfq_exit_queue+0x43/0x190

    stack backtrace:
    Pid: 1552, comm: scsi_scan_6 Not tainted 3.0.0-rc5 #17
    Call Trace:
    [<ffffffff810abb9b>] lockdep_rcu_dereference+0xbb/0xc0
    [<ffffffff812b6139>] __cfq_exit_single_io_context+0xe9/0x120
    [<ffffffff812b626c>] cfq_exit_queue+0x7c/0x190
    [<ffffffff812a5046>] elevator_exit+0x36/0x60
    [<ffffffff812a802a>] blk_cleanup_queue+0x4a/0x60
    [<ffffffff8145cc09>] scsi_free_queue+0x9/0x10
    [<ffffffff81460944>] __scsi_remove_device+0x84/0xd0
    [<ffffffff8145dca3>] scsi_probe_and_add_lun+0x353/0xb10
    [<ffffffff817da069>] ? error_exit+0x29/0xb0
    [<ffffffff817d98ed>] ? _raw_spin_unlock_irqrestore+0x3d/0x80
    [<ffffffff8145e722>] __scsi_scan_target+0x112/0x680
    [<ffffffff812c690d>] ? trace_hardirqs_off_thunk+0x3a/0x3c
    [<ffffffff817da069>] ? error_exit+0x29/0xb0
    [<ffffffff812bcc60>] ? kobject_del+0x40/0x40
    [<ffffffff8145ed16>] scsi_scan_channel+0x86/0xb0
    [<ffffffff8145f0b0>] scsi_scan_host_selected+0x140/0x150
    [<ffffffff8145f149>] do_scsi_scan_host+0x89/0x90
    [<ffffffff8145f170>] do_scan_async+0x20/0x160
    [<ffffffff8145f150>] ? do_scsi_scan_host+0x90/0x90
    [<ffffffff810975b6>] kthread+0xa6/0xb0
    [<ffffffff817db154>] kernel_thread_helper+0x4/0x10
    [<ffffffff81066430>] ? finish_task_switch+0x80/0x110
    [<ffffffff817d9c04>] ? retint_restore_args+0xe/0xe
    [<ffffffff81097510>] ? __kthread_init_worker+0x70/0x70
    [<ffffffff817db150>] ? gs_change+0xb/0xb

Line 2776 of block/cfq-iosched.c in v3.0-rc5 is as follows::

	if (rcu_dereference(ioc->ioc_data) == cic) {

This form says that it must be in a plain vanilla RCU read-side critical
section, but the "other info" list above shows that this is not the
case.  Instead, we hold three locks, one of which might be RCU related.
And maybe that lock really does protect this reference.  If so, the fix
is to inform RCU, perhaps by changing __cfq_exit_single_io_context() to
take the struct request_queue "q" from cfq_exit_queue() as an argument,
which would permit us to invoke rcu_dereference_protected as follows::

	if (rcu_dereference_protected(ioc->ioc_data,
				      lockdep_is_held(&q->queue_lock)) == cic) {

With this change, there would be no lockdep-RCU splat emitted if this
code was invoked either from within an RCU read-side critical section
or with the ->queue_lock held.  In particular, this would have suppressed
the above lockdep-RCU splat because ->queue_lock is held (see #2 in the
list above).

On the other hand, perhaps we really do need an RCU read-side critical
section.  In this case, the critical section must span the use of the
return value from rcu_dereference(), or at least until there is some
reference count incremented or some such.  One way to handle this is to
add rcu_read_lock() and rcu_read_unlock() as follows::

	rcu_read_lock();
	if (rcu_dereference(ioc->ioc_data) == cic) {
		spin_lock(&ioc->lock);
		rcu_assign_pointer(ioc->ioc_data, NULL);
		spin_unlock(&ioc->lock);
	}
	rcu_read_unlock();

With this change, the rcu_dereference() is always within an RCU
read-side critical section, which again would have suppressed the
above lockdep-RCU splat.

But in this particular case, we don't actually dereference the pointer
returned from rcu_dereference().  Instead, that pointer is just compared
to the cic pointer, which means that the rcu_dereference() can be replaced
by rcu_access_pointer() as follows::

	if (rcu_access_pointer(ioc->ioc_data) == cic) {

Because it is legal to invoke rcu_access_pointer() without protection,
this change would also suppress the above lockdep-RCU splat.

---

### Documentation RCU Lockdep (`Documentation/RCU/lockdep.rst`)

.. SPDX-License-Identifier: GPL-2.0

========================
RCU and lockdep checking
========================

All flavors of RCU have lockdep checking available, so that lockdep is
aware of when each task enters and leaves any flavor of RCU read-side
critical section.  Each flavor of RCU is tracked separately (but note
that this is not the case in 2.6.32 and earlier).  This allows lockdep's
tracking to include RCU state, which can sometimes help when debugging
deadlocks and the like.

In addition, RCU provides the following primitives that check lockdep's
state::

	rcu_read_lock_held() for normal RCU.
	rcu_read_lock_bh_held() for RCU-bh.
	rcu_read_lock_sched_held() for RCU-sched.
	rcu_read_lock_any_held() for any of normal RCU, RCU-bh, and RCU-sched.
	srcu_read_lock_held() for SRCU.
	rcu_read_lock_trace_held() for RCU Tasks Trace.

These functions are conservative, and will therefore return 1 if they
aren't certain (for example, if CONFIG_DEBUG_LOCK_ALLOC is not set).
This prevents things like WARN_ON(!rcu_read_lock_held()) from giving false
positives when lockdep is disabled.

In addition, a separate kernel config parameter CONFIG_PROVE_RCU enables
checking of rcu_dereference() primitives:

	rcu_dereference(p):
		Check for RCU read-side critical section.
	rcu_dereference_bh(p):
		Check for RCU-bh read-side critical section.
	rcu_dereference_sched(p):
		Check for RCU-sched read-side critical section.
	srcu_dereference(p, sp):
		Check for SRCU read-side critical section.
	rcu_dereference_check(p, c):
		Use explicit check expression "c" along with
		rcu_read_lock_held().  This is useful in code that is
		invoked by both RCU readers and updaters.
	rcu_dereference_bh_check(p, c):
		Use explicit check expression "c" along with
		rcu_read_lock_bh_held().  This is useful in code that
		is invoked by both RCU-bh readers and updaters.
	rcu_dereference_sched_check(p, c):
		Use explicit check expression "c" along with
		rcu_read_lock_sched_held().  This is useful in code that
		is invoked by both RCU-sched readers and updaters.
	srcu_dereference_check(p, c):
		Use explicit check expression "c" along with
		srcu_read_lock_held().  This is useful in code that
		is invoked by both SRCU readers and updaters.
	rcu_dereference_raw(p):
		Don't check.  (Use sparingly, if at all.)
	rcu_dereference_raw_check(p):
		Don't do lockdep at all.  (Use sparingly, if at all.)
	rcu_dereference_protected(p, c):
		Use explicit check expression "c", and omit all barriers
		and compiler constraints.  This is useful when the data
		structure cannot change, for example, in code that is
		invoked only by updaters.
	rcu_access_pointer(p):
		Return the value of the pointer and omit all barriers,
		but retain the compiler constraints that prevent duplicating
		or coalescing.  This is useful when testing the
		value of the pointer itself, for example, against NULL.

The rcu_dereference_check() check expression can be any boolean
expression, but would normally include a lockdep expression.  For a
moderately ornate example, consider the following::

	file = rcu_dereference_check(fdt->fd[fd],
				     lockdep_is_held(&files->file_lock) ||
				     atomic_read(&files->count) == 1);

This expression picks up the pointer "fdt->fd[fd]" in an RCU-safe manner,
and, if CONFIG_PROVE_RCU is configured, verifies that this expression
is used in:

1.	An RCU read-side critical section (implicit), or
2.	with files->file_lock held, or
3.	on an unshared files_struct.

In case (1), the pointer is picked up in an RCU-safe manner for vanilla
RCU read-side critical sections, in case (2) the ->file_lock prevents
any change from taking place, and finally, in case (3) the current task
is the only task accessing the file_struct, again preventing any change
from taking place.  If the above statement was invoked only from updater
code, it could instead be written as follows::

	file = rcu_dereference_protected(fdt->fd[fd],
					 lockdep_is_held(&files->file_lock) ||
					 atomic_read(&files->count) == 1);

This would verify cases #2 and #3 above, and furthermore lockdep would
complain even if this was used in an RCU read-side critical section unless
one of these two cases held.  Because rcu_dereference_protected() omits
all barriers and compiler constraints, it generates better code than do
the other flavors of rcu_dereference().  On the other hand, it is illegal
to use rcu_dereference_protected() if either the RCU-protected pointer
or the RCU-protected data that it points to can change concurrently.

Like rcu_dereference(), when lockdep is enabled, RCU list and hlist
traversal primitives check for being called from within an RCU read-side
critical section.  However, a lockdep expression can be passed to them
as an additional optional argument.  With this lockdep expression, these
traversal primitives will complain only if the lockdep expression is
false and they are called from outside any RCU read-side critical section.

For example, the workqueue for_each_pwq() macro is intended to be used
either within an RCU read-side critical section or with wq->mutex held.
It is thus implemented as follows::

	#define for_each_pwq(pwq, wq)
		list_for_each_entry_rcu((pwq), &(wq)->pwqs, pwqs_node,
					lock_is_held(&(wq->mutex).dep_map))

---

### Documentation RCU Rcu (`Documentation/RCU/rcu.rst`)

.. _rcu_doc:

RCU Concepts
============

The basic idea behind RCU (read-copy update) is to split destructive
operations into two parts, one that prevents anyone from seeing the data
item being destroyed, and one that actually carries out the destruction.
A "grace period" must elapse between the two parts, and this grace period
must be long enough that any readers accessing the item being deleted have
since dropped their references.  For example, an RCU-protected deletion
from a linked list would first remove the item from the list, wait for
a grace period to elapse, then free the element.  See listRCU.rst for more
information on using RCU with linked lists.

Frequently Asked Questions
--------------------------

- Why would anyone want to use RCU?

  The advantage of RCU's two-part approach is that RCU readers need
  not acquire any locks, perform any atomic instructions, write to
  shared memory, or (on CPUs other than Alpha) execute any memory
  barriers.  The fact that these operations are quite expensive
  on modern CPUs is what gives RCU its performance advantages
  in read-mostly situations.  The fact that RCU readers need not
  acquire locks can also greatly simplify deadlock-avoidance code.

- How can the updater tell when a grace period has completed
  if the RCU readers give no indication when they are done?

  Just as with spinlocks, RCU readers are not permitted to
  block, switch to user-mode execution, or enter the idle loop.
  Therefore, as soon as a CPU is seen passing through any of these
  three states, we know that that CPU has exited any previous RCU
  read-side critical sections.  So, if we remove an item from a
  linked list, and then wait until all CPUs have switched context,
  executed in user mode, or executed in the idle loop, we can
  safely free up that item.

  Preemptible variants of RCU (CONFIG_PREEMPT_RCU) get the
  same effect, but require that the readers manipulate CPU-local
  counters.  These counters allow limited types of blocking within
  RCU read-side critical sections.  SRCU also uses CPU-local
  counters, and permits general blocking within RCU read-side
  critical sections.  These variants of RCU detect grace periods
  by sampling these counters.

- If I am running on a uniprocessor kernel, which can only do one
  thing at a time, why should I wait for a grace period?

  See UP.rst for more information.

- How can I see where RCU is currently used in the Linux kernel?

  Search for "rcu_read_lock", "rcu_read_unlock", "call_rcu",
  "rcu_read_lock_bh", "rcu_read_unlock_bh", "srcu_read_lock",
  "srcu_read_unlock", "synchronize_rcu", "synchronize_net",
  "synchronize_srcu", and the other RCU primitives.  Or grab one
  of the cscope databases from:

  (http://www.rdrop.com/users/paulmck/RCU/linuxusage/rculocktab.html).

- What guidelines should I follow when writing code that uses RCU?

  See checklist.rst.

- Why the name "RCU"?

  "RCU" stands for "read-copy update".
  listRCU.rst has more information on where this name came from, search
  for "read-copy update" to find it.

- I hear that RCU is patented?  What is with that?

  Yes, it is.  There are several known patents related to RCU,
  search for the string "Patent" in Documentation/RCU/RTFP.txt to find them.
  Of these, one was allowed to lapse by the assignee, and the
  others have been contributed to the Linux kernel under GPL.
  Many (but not all) have long since expired.
  There are now also LGPL implementations of user-level RCU
  available (https://liburcu.org/).

- I hear that RCU needs work in order to support realtime kernels?

  Realtime-friendly RCU are enabled via the CONFIG_PREEMPTION
  kernel configuration parameter.

- Where can I find more information on RCU?

  See the Documentation/RCU/RTFP.txt file.
  Or point your browser at (https://docs.google.com/document/d/1X0lThx8OK0ZgLMqVoXiR4ZrGURHrXK6NyLRbeXe3Xac/edit)
  or (https://docs.google.com/document/d/1GCdQC8SDbb54W1shjEXqGZ0Rq8a6kIeYutdSIajfpLA/edit?usp=sharing).

---

### Documentation RCU Rcu Dereference (`Documentation/RCU/rcu_dereference.rst`)

.. _rcu_dereference_doc:

PROPER CARE AND FEEDING OF RETURN VALUES FROM rcu_dereference()
===============================================================

Proper care and feeding of address and data dependencies is critically
important to correct use of things like RCU.  To this end, the pointers
returned from the rcu_dereference() family of primitives carry address and
data dependencies.  These dependencies extend from the rcu_dereference()
macro's load of the pointer to the later use of that pointer to compute
either the address of a later memory access (representing an address
dependency) or the value written by a later memory access (representing
a data dependency).

Most of the time, these dependencies are preserved, permitting you to
freely use values from rcu_dereference().  For example, dereferencing
(prefix "*"), field selection ("->"), assignment ("="), address-of
("&"), casts, and addition or subtraction of constants all work quite
naturally and safely.  However, because current compilers do not take
either address or data dependencies into account it is still possible
to get into trouble.

Follow these rules to preserve the address and data dependencies emanating
from your calls to rcu_dereference() and friends, thus keeping your RCU
readers working properly:

-	You must use one of the rcu_dereference() family of primitives
	to load an RCU-protected pointer, otherwise CONFIG_PROVE_RCU
	will complain.  Worse yet, your code can see random memory-corruption
	bugs due to games that compilers and DEC Alpha can play.
	Without one of the rcu_dereference() primitives, compilers
	can reload the value, and won't your code have fun with two
	different values for a single pointer!  Without rcu_dereference(),
	DEC Alpha can load a pointer, dereference that pointer, and
	return data preceding initialization that preceded the store
	of the pointer.  (As noted later, in recent kernels READ_ONCE()
	also prevents DEC Alpha from playing these tricks.)

	In addition, the volatile cast in rcu_dereference() prevents the
	compiler from deducing the resulting pointer value.  Please see
	the section entitled "EXAMPLE WHERE THE COMPILER KNOWS TOO MUCH"
	for an example where the compiler can in fact deduce the exact
	value of the pointer, and thus cause misordering.

-	In the special case where data is added but is never removed
	while readers are accessing the structure, READ_ONCE() may be used
	instead of rcu_dereference().  In this case, use of READ_ONCE()
	takes on the role of the lockless_dereference() primitive that
	was removed in v4.15.

-	You are only permitted to use rcu_dereference() on pointer values.
	The compiler simply knows too much about integral values to
	trust it to carry dependencies through integer operations.
	There are a very few exceptions, namely that you can temporarily
	cast the pointer to uintptr_t in order to:

	-	Set bits and clear bits down in the must-be-zero low-order
		bits of that pointer.  This clearly means that the pointer
		must have alignment constraints, for example, this does
		*not* work in general for char* pointers.

	-	XOR bits to translate pointers, as is done in some
		classic buddy-allocator algorithms.

	It is important to cast the value back to pointer before
	doing much of anything else with it.

-	Avoid cancellation when using the "+" and "-" infix arithmetic
	operators.  For example, for a given variable "x", avoid
	"(x-(uintptr_t)x)" for char* pointers.	The compiler is within its
	rights to substitute zero for this sort of expression, so that
	subsequent accesses no longer depend on the rcu_dereference(),
	again possibly resulting in bugs due to misordering.

	Of course, if "p" is a pointer from rcu_dereference(), and "a"
	and "b" are integers that happen to be equal, the expression
	"p+a-b" is safe because its value still necessarily depends on
	the rcu_dereference(), thus maintaining proper ordering.

-	If you are using RCU to protect JITed functions, so that the
	"()" function-invocation operator is applied to a value obtained
	(directly or indirectly) from rcu_dereference(), you may need to
	interact directly with the hardware to flush instruction caches.
	This issue arises on some systems when a newly JITed function is
	using the same memory that was used by an earlier JITed function.

-	Do not use the results from relational operators ("==", "!=",
	">", ">=", "<", or "<=") when dereferencing.  For example,
	the following (quite strange) code is buggy::

		int *p;
		int *q;

		...

		p = rcu_dereference(gp)
		q = &global_q;
		q += p > &oom_p;
		r1 = *q;  /* BUGGY!!! */

	As before, the reason this is buggy is that relational operators
	are often compiled using branches.  And as before, although
	weak-memory machines such as ARM or PowerPC do order stores
	after such branches, but can speculate loads, which can again
	result in misordering bugs.

-	Be very careful about comparing pointers obtained from
	rcu_dereference() against non-NULL values.  As Linus Torvalds
	explained, if the two pointers are equal, the compiler could
	substitute the pointer you are comparing against for the pointer
	obtained from rcu_dereference().  For example::

		p = rcu_dereference(gp);
		if (p == &default_struct)
			do_default(p->a);

	Because the compiler now knows that the value of "p" is exactly
	the address of the variable "default_struct", it is free to
	transform this code into the following::

		p = rcu_dereference(gp);
		if (p == &default_struct)
			do_default(default_struct.a);

	On ARM and Power hardware, the load from "default_struct.a"
	can now be speculated, such that it might happen before the
	rcu_dereference().  This could result in bugs due to misordering.

	However, comparisons are OK in the following cases:

	-	The comparison was against the NULL pointer.  If the
		compiler knows that the pointer is NULL, you had better
		not be dereferencing it anyway.  If the comparison is
		non-equal, the compiler is none the wiser.  Therefore,
		it is safe to compare pointers from rcu_dereference()
		against NULL pointers.

	-	The pointer is never dereferenced after being compared.
		Since there are no subsequent dereferences, the compiler
		cannot use anything it learned from the comparison
		to reorder the non-existent subsequent dereferences.
		This sort of comparison occurs frequently when scanning
		RCU-protected circular linked lists.

		Note that if the pointer comparison is done outside
		of an RCU read-side critical section, and the pointer
		is never dereferenced, rcu_access_pointer() should be
		used in place of rcu_dereference().  In most cases,
		it is best to avoid accidental dereferences by testing
		the rcu_access_pointer() return value directly, without
		assigning it to a variable.

		Within an RCU read-side critical section, there is little
		reason to use rcu_access_pointer().

	-	The comparison is against a pointer that references memory
		that was initialized "a long time ago."  The reason
		this is safe is that even if misordering occurs, the
		misordering will not affect the accesses that follow
		the comparison.  So exactly how long ago is "a long
		time ago"?  Here are some possibilities:

		-	Compile time.

		-	Boot time.

		-	Module-init time for module code.

		-	Prior to kthread creation for kthread code.

		-	During some prior acquisition of the lock that
			we now hold.

		-	Before mod_timer() time for a timer handler.

		There are many other possibilities involving the Linux
		kernel's wide array of primitives that cause code to
		be invoked at a later time.

	-	The pointer being compared against also came from
		rcu_dereference().  In this case, both pointers depend
		on one rcu_dereference() or another, so you get proper
		ordering either way.

		That said, this situation can make certain RCU usage
		bugs more likely to happen.  Which can be a good thing,
		at least if they happen during testing.  An example
		of such an RCU usage bug is shown in the section titled
		"EXAMPLE OF AMPLIFIED RCU-USAGE BUG".

	-	All of the accesses following the comparison are stores,
		so that a control dependency preserves the needed ordering.
		That said, it is easy to get control dependencies wrong.
		Please see the "CONTROL DEPENDENCIES" section of
		Documentation/memory-barriers.txt for more details.

	-	The pointers are not equal *and* the compiler does
		not have enough information to deduce the value of the
		pointer.  Note that the volatile cast in rcu_dereference()
		will normally prevent the compiler from knowing too much.

		However, please note that if the compiler knows that the
		pointer takes on only one of two values, a not-equal
		comparison will provide exactly the information that the
		compiler needs to deduce the value of the pointer.

-	Disable any value-speculation optimizations that your compiler
	might provide, especially if you are making use of feedback-based
	optimizations that take data collected from prior runs.  Such
	value-speculation optimizations reorder operations by design.

	There is one exception to this rule:  Value-speculation
	optimizations that leverage the branch-prediction hardware are
	safe on strongly ordered systems (such as x86), but not on weakly
	ordered systems (such as ARM or Power).  Choose your compiler
	command-line options wisely!


EXAMPLE OF AMPLIFIED RCU-USAGE BUG
----------------------------------

Because updaters can run concurrently with RCU readers, RCU readers can
see stale and/or inconsistent values.  If RCU readers need fresh or
consistent values, which they sometimes do, they need to take proper
precautions.  To see this, consider the following code fragment::

	struct foo {
		int a;
		int b;
		int c;
	};
	struct foo *gp1;
	struct foo *gp2;

	void updater(void)
	{
		struct foo *p;

		p = kmalloc(...);
		if (p == NULL)
			deal_with_it();
		p->a = 42;  /* Each field in its own cache line. */
		p->b = 43;
		p->c = 44;
		rcu_assign_pointer(gp1, p);
		p->b = 143;
		p->c = 144;
		rcu_assign_pointer(gp2, p);
	}

	void reader(void)
	{
		struct foo *p;
		struct foo *q;
		int r1, r2;

		rcu_read_lock();
		p = rcu_dereference(gp2);
		if (p == NULL)
			return;
		r1 = p->b;  /* Guaranteed to get 143. */
		q = rcu_dereference(gp1);  /* Guaranteed non-NULL. */
		if (p == q) {
			/* The compiler decides that q->c is same as p->c. */
			r2 = p->c; /* Could get 44 on weakly order system. */
		} else {
			r2 = p->c - r1; /* Unconditional access to p->c. */
		}
		rcu_read_unlock();
		do_something_with(r1, r2);
	}

You might be surprised that the outcome (r1 == 143 && r2 == 44) is possible,
but you should not be.  After all, the updater might have been invoked
a second time between the time reader() loaded into "r1" and the time
that it loaded into "r2".  The fact that this same result can occur due
to some reordering from the compiler and CPUs is beside the point.

But suppose that the reader needs a consistent view?

Then one approach is to use locking, for example, as follows::

	struct foo {
		int a;
		int b;
		int c;
		spinlock_t lock;
	};
	struct foo *gp1;
	struct foo *gp2;

	void updater(void)
	{
		struct foo *p;

		p = kmalloc(...);
		if (p == NULL)
			deal_with_it();
		spin_lock(&p->lock);
		p->a = 42;  /* Each field in its own cache line. */
		p->b = 43;
		p->c = 44;
		spin_unlock(&p->lock);
		rcu_assign_pointer(gp1, p);
		spin_lock(&p->lock);
		p->b = 143;
		p->c = 144;
		spin_unlock(&p->lock);
		rcu_assign_pointer(gp2, p);
	}

	void reader(void)
	{
		struct foo *p;
		struct foo *q;
		int r1, r2;

		rcu_read_lock();
		p = rcu_dereference(gp2);
		if (p == NULL)
			return;
		spin_lock(&p->lock);
		r1 = p->b;  /* Guaranteed to get 143. */
		q = rcu_dereference(gp1);  /* Guaranteed non-NULL. */
		if (p == q) {
			/* The compiler decides that q->c is same as p->c. */
			r2 = p->c; /* Locking guarantees r2 == 144. */
		} else {
			spin_lock(&q->lock);
			r2 = q->c - r1;
			spin_unlock(&q->lock);
		}
		rcu_read_unlock();
		spin_unlock(&p->lock);
		do_something_with(r1, r2);
	}

As always, use the right tool for the job!


EXAMPLE WHERE THE COMPILER KNOWS TOO MUCH
-----------------------------------------

If a pointer obtained from rcu_dereference() compares not-equal to some
other pointer, the compiler normally has no clue what the value of the
first pointer might be.  This lack of knowledge prevents the compiler
from carrying out optimizations that otherwise might destroy the ordering
guarantees that RCU depends on.  And the volatile cast in rcu_dereference()
should prevent the compiler from guessing the value.

But without rcu_dereference(), the compiler knows more than you might
expect.  Consider the following code fragment::

	struct foo {
		int a;
		int b;
	};
	static struct foo variable1;
	static struct foo variable2;
	static struct foo *gp = &variable1;

	void updater(void)
	{
		initialize_foo(&variable2);
		rcu_assign_pointer(gp, &variable2);
		/*
		 * The above is the only store to gp in this translation unit,
		 * and the address of gp is not exported in any way.
		 */
	}

	int reader(void)
	{
		struct foo *p;

		p = gp;
		barrier();
		if (p == &variable1)
			return p->a; /* Must be variable1.a. */
		else
			return p->b; /* Must be variable2.b. */
	}

Because the compiler can see all stores to "gp", it knows that the only
possible values of "gp" are "variable1" on the one hand and "variable2"
on the other.  The comparison in reader() therefore tells the compiler
the exact value of "p" even in the not-equals case.  This allows the
compiler to make the return values independent of the load from "gp",
in turn destroying the ordering between this load and the loads of the
return values.  This can result in "p->b" returning pre-initialization
garbage values on weakly ordered systems.

In short, rcu_dereference() is *not* optional when you are going to
dereference the resulting pointer.


WHICH MEMBER OF THE rcu_dereference() FAMILY SHOULD YOU USE?
------------------------------------------------------------

First, please avoid using rcu_dereference_raw() and also please avoid
using rcu_dereference_check() and rcu_dereference_protected() with a
second argument with a constant value of 1 (or true, for that matter).
With that caution out of the way, here is some guidance for which
member of the rcu_dereference() to use in various situations:

1.	If the access needs to be within an RCU read-side critical
	section, use rcu_dereference().  With the new consolidated
	RCU flavors, an RCU read-side critical section is entered
	using rcu_read_lock(), anything that disables bottom halves,
	anything that disables interrupts, or anything that disables
	preemption.  Please note that spinlock critical sections
	are also implied RCU read-side critical sections, even when
	they are preemptible, as they are in kernels built with
	CONFIG_PREEMPT_RT=y.

2.	If the access might be within an RCU read-side critical section
	on the one hand, or protected by (say) my_lock on the other,
	use rcu_dereference_check(), for example::

		p1 = rcu_dereference_check(p->rcu_protected_pointer,
					   lockdep_is_held(&my_lock));


3.	If the access might be within an RCU read-side critical section
	on the one hand, or protected by either my_lock or your_lock on
	the other, again use rcu_dereference_check(), for example::

		p1 = rcu_dereference_check(p->rcu_protected_pointer,
					   lockdep_is_held(&my_lock) ||
					   lockdep_is_held(&your_lock));

4.	If the access is on the update side, so that it is always protected
	by my_lock, use rcu_dereference_protected()::

		p1 = rcu_dereference_protected(p->rcu_protected_pointer,
					       lockdep_is_held(&my_lock));

	This can be extended to handle multiple locks as in #3 above,
	and both can be extended to check other conditions as well.

5.	If the protection is supplied by the caller, and is thus unknown
	to this code, that is the rare case when rcu_dereference_raw()
	is appropriate.  In addition, rcu_dereference_raw() might be
	appropriate when the lockdep expression would be excessively
	complex, except that a better approach in that case might be to
	take a long hard look at your synchronization design.  Still,
	there are data-locking cases where any one of a very large number
	of locks or reference counters suffices to protect the pointer,
	so rcu_dereference_raw() does have its place.

	However, its place is probably quite a bit smaller than one
	might expect given the number of uses in the current kernel.
	Ditto for its synonym, rcu_dereference_check( ... , 1), and
	its close relative, rcu_dereference_protected(... , 1).


SPARSE CHECKING OF RCU-PROTECTED POINTERS
-----------------------------------------

The sparse static-analysis tool checks for non-RCU access to RCU-protected
pointers, which can result in "interesting" bugs due to compiler
optimizations involving invented loads and perhaps also load tearing.
For example, suppose someone mistakenly does something like this::

	p = q->rcu_protected_pointer;
	do_something_with(p->a);
	do_something_else_with(p->b);

If register pressure is high, the compiler might optimize "p" out
of existence, transforming the code to something like this::

	do_something_with(q->rcu_protected_pointer->a);
	do_something_else_with(q->rcu_protected_pointer->b);

This could fatally disappoint your code if q->rcu_protected_pointer
changed in the meantime.  Nor is this a theoretical problem:  Exactly
this sort of bug cost Paul E. McKenney (and several of his innocent
colleagues) a three-day weekend back in the early 1990s.

Load tearing could of course result in dereferencing a mashup of a pair
of pointers, which also might fatally disappoint your code.

These problems could have been avoided simply by making the code instead
read as follows::

	p = rcu_dereference(q->rcu_protected_pointer);
	do_something_with(p->a);
	do_something_else_with(p->b);

Unfortunately, these sorts of bugs can be extremely hard to spot during
review.  This is where the sparse tool comes into play, along with the
"__rcu" marker.  If you mark a pointer declaration, whether in a structure
or as a formal parameter, with "__rcu", which tells sparse to complain if
this pointer is accessed directly.  It will also cause sparse to complain
if a pointer not marked with "__rcu" is accessed using rcu_dereference()
and friends.  For example, ->rcu_protected_pointer might be declared as
follows::

	struct foo __rcu *rcu_protected_pointer;

Use of "__rcu" is opt-in.  If you choose not to use it, then you should
ignore the sparse warnings.

---

### Documentation RCU Rcubarrier (`Documentation/RCU/rcubarrier.rst`)

.. _rcu_barrier:

RCU and Unloadable Modules
==========================

[Originally published in LWN Jan. 14, 2007: http://lwn.net/Articles/217484/]

RCU updaters sometimes use call_rcu() to initiate an asynchronous wait for
a grace period to elapse.  This primitive takes a pointer to an rcu_head
struct placed within the RCU-protected data structure and another pointer
to a function that may be invoked later to free that structure. Code to
delete an element p from the linked list from IRQ context might then be
as follows::

	list_del_rcu(p);
	call_rcu(&p->rcu, p_callback);

Since call_rcu() never blocks, this code can safely be used from within
IRQ context. The function p_callback() might be defined as follows::

	static void p_callback(struct rcu_head *rp)
	{
		struct pstruct *p = container_of(rp, struct pstruct, rcu);

		kfree(p);
	}


Unloading Modules That Use call_rcu()
-------------------------------------

But what if the p_callback() function is defined in an unloadable module?

If we unload the module while some RCU callbacks are pending,
the CPUs executing these callbacks are going to be severely
disappointed when they are later invoked, as fancifully depicted at
http://lwn.net/images/ns/kernel/rcu-drop.jpg.

We could try placing a synchronize_rcu() in the module-exit code path,
but this is not sufficient. Although synchronize_rcu() does wait for a
grace period to elapse, it does not wait for the callbacks to complete.

One might be tempted to try several back-to-back synchronize_rcu()
calls, but this is still not guaranteed to work. If there is a very
heavy RCU-callback load, then some of the callbacks might be deferred in
order to allow other processing to proceed. For but one example, such
deferral is required in realtime kernels in order to avoid excessive
scheduling latencies.


rcu_barrier()
-------------

This situation can be handled by the rcu_barrier() primitive.  Rather
than waiting for a grace period to elapse, rcu_barrier() waits for all
outstanding RCU callbacks to complete.  Please note that rcu_barrier()
does **not** imply synchronize_rcu(), in particular, if there are no RCU
callbacks queued anywhere, rcu_barrier() is within its rights to return
immediately, without waiting for anything, let alone a grace period.

Pseudo-code using rcu_barrier() is as follows:

   1. Prevent any new RCU callbacks from being posted.
   2. Execute rcu_barrier().
   3. Allow the module to be unloaded.

There is also an srcu_barrier() function for SRCU, and you of course
must match the flavor of srcu_barrier() with that of call_srcu().
If your module uses multiple srcu_struct structures, then it must also
use multiple invocations of srcu_barrier() when unloading that module.
For example, if it uses call_rcu(), call_srcu() on srcu_struct_1, and
call_srcu() on srcu_struct_2, then the following three lines of code
will be required when unloading::

  1  rcu_barrier();
  2  srcu_barrier(&srcu_struct_1);
  3  srcu_barrier(&srcu_struct_2);

If latency is of the essence, workqueues could be used to run these
three functions concurrently.

An ancient version of the rcutorture module makes use of rcu_barrier()
in its exit function as follows::

  1  static void
  2  rcu_torture_cleanup(void)
  3  {
  4    int i;
  5
  6    fullstop = 1;
  7    if (shuffler_task != NULL) {
  8      VERBOSE_PRINTK_STRING("Stopping rcu_torture_shuffle task");
  9      kthread_stop(shuffler_task);
 10    }
 11    shuffler_task = NULL;
 12
 13    if (writer_task != NULL) {
 14      VERBOSE_PRINTK_STRING("Stopping rcu_torture_writer task");
 15      kthread_stop(writer_task);
 16    }
 17    writer_task = NULL;
 18
 19    if (reader_tasks != NULL) {
 20      for (i = 0; i < nrealreaders; i++) {
 21        if (reader_tasks[i] != NULL) {
 22          VERBOSE_PRINTK_STRING(
 23            "Stopping rcu_torture_reader task");
 24          kthread_stop(reader_tasks[i]);
 25        }
 26        reader_tasks[i] = NULL;
 27      }
 28      kfree(reader_tasks);
 29      reader_tasks = NULL;
 30    }
 31    rcu_torture_current = NULL;
 32
 33    if (fakewriter_tasks != NULL) {
 34      for (i = 0; i < nfakewriters; i++) {
 35        if (fakewriter_tasks[i] != NULL) {
 36          VERBOSE_PRINTK_STRING(
 37            "Stopping rcu_torture_fakewriter task");
 38          kthread_stop(fakewriter_tasks[i]);
 39        }
 40        fakewriter_tasks[i] = NULL;
 41      }
 42      kfree(fakewriter_tasks);
 43      fakewriter_tasks = NULL;
 44    }
 45
 46    if (stats_task != NULL) {
 47      VERBOSE_PRINTK_STRING("Stopping rcu_torture_stats task");
 48      kthread_stop(stats_task);
 49    }
 50    stats_task = NULL;
 51
 52    /* Wait for all RCU callbacks to fire. */
 53    rcu_barrier();
 54
 55    rcu_torture_stats_print(); /* -After- the stats thread is stopped! */
 56
 57    if (cur_ops->cleanup != NULL)
 58      cur_ops->cleanup();
 59    if (atomic_read(&n_rcu_torture_error))
 60      rcu_torture_print_module_parms("End of test: FAILURE");
 61    else
 62      rcu_torture_print_module_parms("End of test: SUCCESS");
 63  }

Line 6 sets a global variable that prevents any RCU callbacks from
re-posting themselves. This will not be necessary in most cases, since
RCU callbacks rarely include calls to call_rcu(). However, the rcutorture
module is an exception to this rule, and therefore needs to set this
global variable.

Lines 7-50 stop all the kernel tasks associated with the rcutorture
module. Therefore, once execution reaches line 53, no more rcutorture
RCU callbacks will be posted. The rcu_barrier() call on line 53 waits
for any pre-existing callbacks to complete.

Then lines 55-62 print status and do operation-specific cleanup, and
then return, permitting the module-unload operation to be completed.

.. _rcubarrier_quiz_1:

Quick Quiz #1:
	Is there any other situation where rcu_barrier() might
	be required?

:ref:`Answer to Quick Quiz #1 <answer_rcubarrier_quiz_1>`

Your module might have additional complications. For example, if your
module invokes call_rcu() from timers, you will need to first refrain
from posting new timers, cancel (or wait for) all the already-posted
timers, and only then invoke rcu_barrier() to wait for any remaining
RCU callbacks to complete.

Of course, if your module uses call_rcu(), you will need to invoke
rcu_barrier() before unloading.  Similarly, if your module uses
call_srcu(), you will need to invoke srcu_barrier() before unloading,
and on the same srcu_struct structure.  If your module uses call_rcu()
**and** call_srcu(), then (as noted above) you will need to invoke
rcu_barrier() **and** srcu_barrier().


Implementing rcu_barrier()
--------------------------

Dipankar Sarma's implementation of rcu_barrier() makes use of the fact
that RCU callbacks are never reordered once queued on one of the per-CPU
queues. His implementation queues an RCU callback on each of the per-CPU
callback queues, and then waits until they have all started executing, at
which point, all earlier RCU callbacks are guaranteed to have completed.

The original code for rcu_barrier() was roughly as follows::

  1  void rcu_barrier(void)
  2  {
  3    BUG_ON(in_interrupt());
  4    /* Take cpucontrol mutex to protect against CPU hotplug */
  5    mutex_lock(&rcu_barrier_mutex);
  6    init_completion(&rcu_barrier_completion);
  7    atomic_set(&rcu_barrier_cpu_count, 1);
  8    on_each_cpu(rcu_barrier_func, NULL, 0, 1);
  9    if (atomic_dec_and_test(&rcu_barrier_cpu_count))
 10      complete(&rcu_barrier_completion);
 11    wait_for_completion(&rcu_barrier_completion);
 12    mutex_unlock(&rcu_barrier_mutex);
 13  }

Line 3 verifies that the caller is in process context, and lines 5 and 12
use rcu_barrier_mutex to ensure that only one rcu_barrier() is using the
global completion and counters at a time, which are initialized on lines
6 and 7. Line 8 causes each CPU to invoke rcu_barrier_func(), which is
shown below. Note that the final "1" in on_each_cpu()'s argument list
ensures that all the calls to rcu_barrier_func() will have completed
before on_each_cpu() returns. Line 9 removes the initial count from
rcu_barrier_cpu_count, and if this count is now zero, line 10 finalizes
the completion, which prevents line 11 from blocking.  Either way,
line 11 then waits (if needed) for the completion.

.. _rcubarrier_quiz_2:

Quick Quiz #2:
	Why doesn't line 8 initialize rcu_barrier_cpu_count to zero,
	thereby avoiding the need for lines 9 and 10?

:ref:`Answer to Quick Quiz #2 <answer_rcubarrier_quiz_2>`

This code was rewritten in 2008 and several times thereafter, but this
still gives the general idea.

The rcu_barrier_func() runs on each CPU, where it invokes call_rcu()
to post an RCU callback, as follows::

  1  static void rcu_barrier_func(void *notused)
  2  {
  3    int cpu = smp_processor_id();
  4    struct rcu_data *rdp = &per_cpu(rcu_data, cpu);
  5    struct rcu_head *head;
  6
  7    head = &rdp->barrier;
  8    atomic_inc(&rcu_barrier_cpu_count);
  9    call_rcu(head, rcu_barrier_callback);
 10  }

Lines 3 and 4 locate RCU's internal per-CPU rcu_data structure,
which contains the struct rcu_head that needed for the later call to
call_rcu(). Line 7 picks up a pointer to this struct rcu_head, and line
8 increments the global counter. This counter will later be decremented
by the callback. Line 9 then registers the rcu_barrier_callback() on
the current CPU's queue.

The rcu_barrier_callback() function simply atomically decrements the
rcu_barrier_cpu_count variable and finalizes the completion when it
reaches zero, as follows::

  1  static void rcu_barrier_callback(struct rcu_head *notused)
  2  {
  3    if (atomic_dec_and_test(&rcu_barrier_cpu_count))
  4      complete(&rcu_barrier_completion);
  5  }

.. _rcubarrier_quiz_3:

Quick Quiz #3:
	What happens if CPU 0's rcu_barrier_func() executes
	immediately (thus incrementing rcu_barrier_cpu_count to the
	value one), but the other CPU's rcu_barrier_func() invocations
	are delayed for a full grace period? Couldn't this result in
	rcu_barrier() returning prematurely?

:ref:`Answer to Quick Quiz #3 <answer_rcubarrier_quiz_3>`

The current rcu_barrier() implementation is more complex, due to the need
to avoid disturbing idle CPUs (especially on battery-powered systems)
and the need to minimally disturb non-idle CPUs in real-time systems.
In addition, a great many optimizations have been applied.  However,
the code above illustrates the concepts.


rcu_barrier() Summary
---------------------

The rcu_barrier() primitive is used relatively infrequently, since most
code using RCU is in the core kernel rather than in modules. However, if
you are using RCU from an unloadable module, you need to use rcu_barrier()
so that your module may be safely unloaded.


Answers to Quick Quizzes
------------------------

.. _answer_rcubarrier_quiz_1:

Quick Quiz #1:
	Is there any other situation where rcu_barrier() might
	be required?

Answer:
	Interestingly enough, rcu_barrier() was not originally
	implemented for module unloading. Nikita Danilov was using
	RCU in a filesystem, which resulted in a similar situation at
	filesystem-unmount time. Dipankar Sarma coded up rcu_barrier()
	in response, so that Nikita could invoke it during the
	filesystem-unmount process.

	Much later, yours truly hit the RCU module-unload problem when
	implementing rcutorture, and found that rcu_barrier() solves
	this problem as well.

:ref:`Back to Quick Quiz #1 <rcubarrier_quiz_1>`

.. _answer_rcubarrier_quiz_2:

Quick Quiz #2:
	Why doesn't line 8 initialize rcu_barrier_cpu_count to zero,
	thereby avoiding the need for lines 9 and 10?

Answer:
	Suppose that the on_each_cpu() function shown on line 8 was
	delayed, so that CPU 0's rcu_barrier_func() executed and
	the corresponding grace period elapsed, all before CPU 1's
	rcu_barrier_func() started executing.  This would result in
	rcu_barrier_cpu_count being decremented to zero, so that line
	11's wait_for_completion() would return immediately, failing to
	wait for CPU 1's callbacks to be invoked.

	Note that this was not a problem when the rcu_barrier() code
	was first added back in 2005.  This is because on_each_cpu()
	disables preemption, which acted as an RCU read-side critical
	section, thus preventing CPU 0's grace period from completing
	until on_each_cpu() had dealt with all of the CPUs.

	However, with the RCU flavor consolidation around v4.20, this
	possibility was once again ruled out, because the consolidated
	RCU once again waits on nonpreemptible regions of code.

	Nevertheless, that extra count might still be a good idea.
	Relying on these sort of accidents of implementation can result
	in later surprise bugs when the implementation changes.

:ref:`Back to Quick Quiz #2 <rcubarrier_quiz_2>`

.. _answer_rcubarrier_quiz_3:

Quick Quiz #3:
	What happens if CPU 0's rcu_barrier_func() executes
	immediately (thus incrementing rcu_barrier_cpu_count to the
	value one), but the other CPU's rcu_barrier_func() invocations
	are delayed for a full grace period? Couldn't this result in
	rcu_barrier() returning prematurely?

Answer:
	This cannot happen. The reason is that on_each_cpu() has its last
	argument, the wait flag, set to "1". This flag is passed through
	to smp_call_function() and further to smp_call_function_on_cpu(),
	causing this latter to spin until the cross-CPU invocation of
	rcu_barrier_func() has completed. This by itself would prevent
	a grace period from completing on non-CONFIG_PREEMPTION kernels,
	since each CPU must undergo a context switch (or other quiescent
	state) before the grace period can complete. However, this is
	of no use in CONFIG_PREEMPTION kernels.

	Therefore, on_each_cpu() disables preemption across its call
	to smp_call_function() and also across the local call to
	rcu_barrier_func(). Because recent RCU implementations treat
	preemption-disabled regions of code as RCU read-side critical
	sections, this prevents grace periods from completing. This
	means that all CPUs have executed rcu_barrier_func() before
	the first rcu_barrier_callback() can possibly execute, in turn
	preventing rcu_barrier_cpu_count from prematurely reaching zero.

	But if on_each_cpu() ever decides to forgo disabling preemption,
	as might well happen due to real-time latency considerations,
	initializing rcu_barrier_cpu_count to one will save the day.

:ref:`Back to Quick Quiz #3 <rcubarrier_quiz_3>`

---

### Documentation RCU Rculist Nulls (`Documentation/RCU/rculist_nulls.rst`)

.. SPDX-License-Identifier: GPL-2.0

=================================================
Using RCU hlist_nulls to protect list and objects
=================================================

This section describes how to use hlist_nulls to
protect read-mostly linked lists and
objects using SLAB_TYPESAFE_BY_RCU allocations.

Please read the basics in listRCU.rst.

Using 'nulls'
=============

Using special makers (called 'nulls') is a convenient way
to solve following problem.

Without 'nulls', a typical RCU linked list managing objects which are
allocated with SLAB_TYPESAFE_BY_RCU kmem_cache can use the following
algorithms.  Following examples assume 'obj' is a pointer to such
objects, which is having below type.

::

  struct object {
    struct hlist_node obj_node;
    atomic_t refcnt;
    unsigned int key;
  };

1) Lookup algorithm
-------------------

::

  begin:
  rcu_read_lock();
  obj = lockless_lookup(key);
  if (obj) {
    if (!try_get_ref(obj)) { // might fail for free objects
      rcu_read_unlock();
      goto begin;
    }
    /*
    * Because a writer could delete object, and a writer could
    * reuse these object before the RCU grace period, we
    * must check key after getting the reference on object
    */
    if (obj->key != key) { // not the object we expected
      put_ref(obj);
      rcu_read_unlock();
      goto begin;
    }
  }
  rcu_read_unlock();

Beware that lockless_lookup(key) cannot use traditional hlist_for_each_entry_rcu()
but a version with an additional memory barrier (smp_rmb())

::

  lockless_lookup(key)
  {
    struct hlist_node *node, *next;
    for (pos = rcu_dereference((head)->first);
         pos && ({ next = pos->next; smp_rmb(); prefetch(next); 1; }) &&
         ({ obj = hlist_entry(pos, typeof(*obj), obj_node); 1; });
         pos = rcu_dereference(next))
      if (obj->key == key)
        return obj;
    return NULL;
  }

And note the traditional hlist_for_each_entry_rcu() misses this smp_rmb()::

  struct hlist_node *node;
  for (pos = rcu_dereference((head)->first);
       pos && ({ prefetch(pos->next); 1; }) &&
       ({ obj = hlist_entry(pos, typeof(*obj), obj_node); 1; });
       pos = rcu_dereference(pos->next))
    if (obj->key == key)
      return obj;
  return NULL;

Quoting Corey Minyard::

  "If the object is moved from one list to another list in-between the
  time the hash is calculated and the next field is accessed, and the
  object has moved to the end of a new list, the traversal will not
  complete properly on the list it should have, since the object will
  be on the end of the new list and there's not a way to tell it's on a
  new list and restart the list traversal. I think that this can be
  solved by pre-fetching the "next" field (with proper barriers) before
  checking the key."

2) Insertion algorithm
----------------------

We need to make sure a reader cannot read the new 'obj->obj_node.next' value
and previous value of 'obj->key'. Otherwise, an item could be deleted
from a chain, and inserted into another chain. If new chain was empty
before the move, 'next' pointer is NULL, and lockless reader can not
detect the fact that it missed following items in original chain.

::

  /*
   * Please note that new inserts are done at the head of list,
   * not in the middle or end.
   */
  obj = kmem_cache_alloc(...);
  lock_chain(); // typically a spin_lock()
  obj->key = key;
  atomic_set_release(&obj->refcnt, 1); // key before refcnt
  hlist_add_head_rcu(&obj->obj_node, list);
  unlock_chain(); // typically a spin_unlock()


3) Removal algorithm
--------------------

Nothing special here, we can use a standard RCU hlist deletion.
But thanks to SLAB_TYPESAFE_BY_RCU, beware a deleted object can be reused
very very fast (before the end of RCU grace period)

::

  if (put_last_reference_on(obj) {
    lock_chain(); // typically a spin_lock()
    hlist_del_init_rcu(&obj->obj_node);
    unlock_chain(); // typically a spin_unlock()
    kmem_cache_free(cachep, obj);
  }



--------------------------------------------------------------------------

Avoiding extra smp_rmb()
========================

With hlist_nulls we can avoid extra smp_rmb() in lockless_lookup().

For example, if we choose to store the slot number as the 'nulls'
end-of-list marker for each slot of the hash table, we can detect
a race (some writer did a delete and/or a move of an object
to another chain) checking the final 'nulls' value if
the lookup met the end of chain. If final 'nulls' value
is not the slot number, then we must restart the lookup at
the beginning. If the object was moved to the same chain,
then the reader doesn't care: It might occasionally
scan the list again without harm.

Note that using hlist_nulls means the type of 'obj_node' field of
'struct object' becomes 'struct hlist_nulls_node'.


1) lookup algorithm
-------------------

::

  head = &table[slot];
  begin:
  rcu_read_lock();
  hlist_nulls_for_each_entry_rcu(obj, node, head, obj_node) {
    if (obj->key == key) {
      if (!try_get_ref(obj)) { // might fail for free objects
	rcu_read_unlock();
        goto begin;
      }
      if (obj->key != key) { // not the object we expected
        put_ref(obj);
	rcu_read_unlock();
        goto begin;
      }
      goto out;
    }
  }

  // If the nulls value we got at the end of this lookup is
  // not the expected one, we must restart lookup.
  // We probably met an item that was moved to another chain.
  if (get_nulls_value(node) != slot) {
    put_ref(obj);
    rcu_read_unlock();
    goto begin;
  }
  obj = NULL;

  out:
  rcu_read_unlock();

2) Insert algorithm
-------------------

Same to the above one, but uses hlist_nulls_add_head_rcu() instead of
hlist_add_head_rcu().

::

  /*
   * Please note that new inserts are done at the head of list,
   * not in the middle or end.
   */
  obj = kmem_cache_alloc(cachep);
  lock_chain(); // typically a spin_lock()
  obj->key = key;
  atomic_set_release(&obj->refcnt, 1); // key before refcnt
  /*
   * insert obj in RCU way (readers might be traversing chain)
   */
  hlist_nulls_add_head_rcu(&obj->obj_node, list);
  unlock_chain(); // typically a spin_unlock()

---

### Documentation RCU Rcuref (`Documentation/RCU/rcuref.rst`)

.. SPDX-License-Identifier: GPL-2.0

====================================================================
Reference-count design for elements of lists/arrays protected by RCU
====================================================================


Please note that the percpu-ref feature is likely your first
stop if you need to combine reference counts and RCU.  Please see
include/linux/percpu-refcount.h for more information.  However, in
those unusual cases where percpu-ref would consume too much memory,
please read on.

------------------------------------------------------------------------

Reference counting on elements of lists which are protected by traditional
reader/writer spinlocks or semaphores are straightforward:

CODE LISTING A::

    1.					    2.
    add()				    search_and_reference()
    {					    {
	alloc_object				read_lock(&list_lock);
	...					search_for_element
	atomic_set(&el->rc, 1);			atomic_inc(&el->rc);
	write_lock(&list_lock);			 ...
	add_element				read_unlock(&list_lock);
	...					...
	write_unlock(&list_lock);	   }
    }

    3.					    4.
    release_referenced()		    delete()
    {					    {
	...					write_lock(&list_lock);
	if(atomic_dec_and_test(&el->rc))	...
	    kfree(el);
	...					remove_element
    }						write_unlock(&list_lock);
						...
						if (atomic_dec_and_test(&el->rc))
						    kfree(el);
						...
					    }

If this list/array is made lock free using RCU as in changing the
write_lock() in add() and delete() to spin_lock() and changing read_lock()
in search_and_reference() to rcu_read_lock(), the atomic_inc() in
search_and_reference() could potentially hold reference to an element which
has already been deleted from the list/array.  Use atomic_inc_not_zero()
in this scenario as follows:

CODE LISTING B::

    1.					    2.
    add()				    search_and_reference()
    {					    {
	alloc_object				rcu_read_lock();
	...					search_for_element
	atomic_set(&el->rc, 1);			if (!atomic_inc_not_zero(&el->rc)) {
	spin_lock(&list_lock);			    rcu_read_unlock();
						    return FAIL;
	add_element				}
	...					...
	spin_unlock(&list_lock);		rcu_read_unlock();
    }					    }
    3.					    4.
    release_referenced()		    delete()
    {					    {
	...					spin_lock(&list_lock);
	if (atomic_dec_and_test(&el->rc))	...
	    call_rcu(&el->head, el_free);	remove_element
	...					spin_unlock(&list_lock);
    }						...
						if (atomic_dec_and_test(&el->rc))
						    call_rcu(&el->head, el_free);
						...
					    }

Sometimes, a reference to the element needs to be obtained in the
update (write) stream.	In such cases, atomic_inc_not_zero() might be
overkill, since we hold the update-side spinlock.  One might instead
use atomic_inc() in such cases.

It is not always convenient to deal with "FAIL" in the
search_and_reference() code path.  In such cases, the
atomic_dec_and_test() may be moved from delete() to el_free()
as follows:

CODE LISTING C::

    1.					    2.
    add()				    search_and_reference()
    {					    {
	alloc_object				rcu_read_lock();
	...					search_for_element
	atomic_set(&el->rc, 1);			atomic_inc(&el->rc);
	spin_lock(&list_lock);			...

	add_element				rcu_read_unlock();
	...				    }
	spin_unlock(&list_lock);	    4.
    }					    delete()
    3.					    {
    release_referenced()			spin_lock(&list_lock);
    {						...
	...					remove_element
	if (atomic_dec_and_test(&el->rc))	spin_unlock(&list_lock);
	    kfree(el);				...
	...					call_rcu(&el->head, el_free);
    }						...
    5.					    }
    void el_free(struct rcu_head *rhp)
    {
	release_referenced();
    }

The key point is that the initial reference added by add() is not removed
until after a grace period has elapsed following removal.  This means that
search_and_reference() cannot find this element, which means that the value
of el->rc cannot increase.  Thus, once it reaches zero, there are no
readers that can or ever will be able to reference the element.	 The
element can therefore safely be freed.	This in turn guarantees that if
any reader finds the element, that reader may safely acquire a reference
without checking the value of the reference counter.

A clear advantage of the RCU-based pattern in listing C over the one
in listing B is that any call to search_and_reference() that locates
a given object will succeed in obtaining a reference to that object,
even given a concurrent invocation of delete() for that same object.
Similarly, a clear advantage of both listings B and C over listing A is
that a call to delete() is not delayed even if there are an arbitrarily
large number of calls to search_and_reference() searching for the same
object that delete() was invoked on.  Instead, all that is delayed is
the eventual invocation of kfree(), which is usually not a problem on
modern computer systems, even the small ones.

In cases where delete() can sleep, synchronize_rcu() can be called from
delete(), so that el_free() can be subsumed into delete as follows::

    4.
    delete()
    {
	spin_lock(&list_lock);
	...
	remove_element
	spin_unlock(&list_lock);
	...
	synchronize_rcu();
	if (atomic_dec_and_test(&el->rc))
	    kfree(el);
	...
    }

As additional examples in the kernel, the pattern in listing C is used by
reference counting of struct pid, while the pattern in listing B is used by
struct posix_acl.

---

### Documentation RCU Stallwarn (`Documentation/RCU/stallwarn.rst`)

.. SPDX-License-Identifier: GPL-2.0

==============================
Using RCU's CPU Stall Detector
==============================

This document first discusses what sorts of issues RCU's CPU stall
detector can locate, and then discusses kernel parameters and Kconfig
options that can be used to fine-tune the detector's operation.  Finally,
this document explains the stall detector's "splat" format.


What Causes RCU CPU Stall Warnings?
===================================

So your kernel printed an RCU CPU stall warning.  The next question is
"What caused it?"  The following problems can result in RCU CPU stall
warnings:

-	A CPU looping in an RCU read-side critical section.

-	A CPU looping with interrupts disabled.

-	A CPU looping with preemption disabled.

-	A CPU looping with bottom halves disabled.

-	For !CONFIG_PREEMPTION kernels, a CPU looping anywhere in the
	kernel without potentially invoking schedule().  If the looping
	in the kernel is really expected and desirable behavior, you
	might need to add some calls to cond_resched().

-	Booting Linux using a console connection that is too slow to
	keep up with the boot-time console-message rate.  For example,
	a 115Kbaud serial console can be *way* too slow to keep up
	with boot-time message rates, and will frequently result in
	RCU CPU stall warning messages.  Especially if you have added
	debug printk()s.

-	Anything that prevents RCU's grace-period kthreads from running.
	This can result in the "All QSes seen" console-log message.
	This message will include information on when the kthread last
	ran and how often it should be expected to run.  It can also
	result in the ``rcu_.*kthread starved for`` console-log message,
	which will include additional debugging information.

-	A CPU-bound real-time task in a CONFIG_PREEMPTION kernel, which might
	happen to preempt a low-priority task in the middle of an RCU
	read-side critical section.   This is especially damaging if
	that low-priority task is not permitted to run on any other CPU,
	in which case the next RCU grace period can never complete, which
	will eventually cause the system to run out of memory and hang.
	While the system is in the process of running itself out of
	memory, you might see stall-warning messages.

-	A CPU-bound real-time task in a CONFIG_PREEMPT_RT kernel that
	is running at a higher priority than the RCU softirq threads.
	This will prevent RCU callbacks from ever being invoked,
	and in a CONFIG_PREEMPT_RCU kernel will further prevent
	RCU grace periods from ever completing.  Either way, the
	system will eventually run out of memory and hang.  In the
	CONFIG_PREEMPT_RCU case, you might see stall-warning
	messages.

	You can use the rcutree.kthread_prio kernel boot parameter to
	increase the scheduling priority of RCU's kthreads, which can
	help avoid this problem.  However, please note that doing this
	can increase your system's context-switch rate and thus degrade
	performance.

-	A periodic interrupt whose handler takes longer than the time
	interval between successive pairs of interrupts.  This can
	prevent RCU's kthreads and softirq handlers from running.
	Note that certain high-overhead debugging options, for example
	the function_graph tracer, can result in interrupt handler taking
	considerably longer than normal, which can in turn result in
	RCU CPU stall warnings.

-	Testing a workload on a fast system, tuning the stall-warning
	timeout down to just barely avoid RCU CPU stall warnings, and then
	running the same workload with the same stall-warning timeout on a
	slow system.  Note that thermal throttling and on-demand governors
	can cause a single system to be sometimes fast and sometimes slow!

-	A hardware or software issue shuts off the scheduler-clock
	interrupt on a CPU that is not in dyntick-idle mode.  This
	problem really has happened, and seems to be most likely to
	result in RCU CPU stall warnings for CONFIG_NO_HZ_COMMON=n kernels.

-	A hardware or software issue that prevents time-based wakeups
	from occurring.  These issues can range from misconfigured or
	buggy timer hardware through bugs in the interrupt or exception
	path (whether hardware, firmware, or software) through bugs
	in Linux's timer subsystem through bugs in the scheduler, and,
	yes, even including bugs in RCU itself.  It can also result in
	the ``rcu_.*timer wakeup didn't happen for`` console-log message,
	which will include additional debugging information.

-	A timer issue causes time to appear to jump forward, so that RCU
	believes that the RCU CPU stall-warning timeout has been exceeded
	when in fact much less time has passed.  This could be due to
	timer hardware bugs, timer driver bugs, or even corruption of
	the "jiffies" global variable.	These sorts of timer hardware
	and driver bugs are not uncommon when testing new hardware.

-	A low-level kernel issue that either fails to invoke one of the
	variants of rcu_eqs_enter(true), rcu_eqs_exit(true), ct_idle_enter(),
	ct_idle_exit(), ct_irq_enter(), or ct_irq_exit() on the one
	hand, or that invokes one of them too many times on the other.
	Historically, the most frequent issue has been an omission
	of either irq_enter() or irq_exit(), which in turn invoke
	ct_irq_enter() or ct_irq_exit(), respectively.  Building your
	kernel with CONFIG_RCU_EQS_DEBUG=y can help track down these types
	of issues, which sometimes arise in architecture-specific code.

-	A bug in the RCU implementation.

-	A hardware failure.  This is quite unlikely, but is not at all
	uncommon in large datacenter.  In one memorable case some decades
	back, a CPU failed in a running system, becoming unresponsive,
	but not causing an immediate crash.  This resulted in a series
	of RCU CPU stall warnings, eventually leading to the realization
	that the CPU had failed.

The RCU, RCU-sched, RCU-tasks, and RCU-tasks-trace implementations have
CPU stall warning.  Note that SRCU does *not* have CPU stall warnings.
Please note that RCU only detects CPU stalls when there is a grace period
in progress.  No grace period, no CPU stall warnings.

To diagnose the cause of the stall, inspect the stack traces.
The offending function will usually be near the top of the stack.
If you have a series of stall warnings from a single extended stall,
comparing the stack traces can often help determine where the stall
is occurring, which will usually be in the function nearest the top of
that portion of the stack which remains the same from trace to trace.
If you can reliably trigger the stall, ftrace can be quite helpful.

RCU bugs can often be debugged with the help of CONFIG_RCU_TRACE
and with RCU's event tracing.  For information on RCU's event tracing,
see include/trace/events/rcu.h.


Fine-Tuning the RCU CPU Stall Detector
======================================

The rcuupdate.rcu_cpu_stall_suppress module parameter disables RCU's
CPU stall detector, which detects conditions that unduly delay RCU grace
periods.  This module parameter enables CPU stall detection by default,
but may be overridden via boot-time parameter or at runtime via sysfs.
The stall detector's idea of what constitutes "unduly delayed" is
controlled by a set of kernel configuration variables and cpp macros:

CONFIG_RCU_CPU_STALL_TIMEOUT
----------------------------

	This kernel configuration parameter defines the period of time
	that RCU will wait from the beginning of a grace period until it
	issues an RCU CPU stall warning.  This time period is normally
	21 seconds.

	This configuration parameter may be changed at runtime via the
	/sys/module/rcupdate/parameters/rcu_cpu_stall_timeout, however
	this parameter is checked only at the beginning of a cycle.
	So if you are 10 seconds into a 40-second stall, setting this
	sysfs parameter to (say) five will shorten the timeout for the
	*next* stall, or the following warning for the current stall
	(assuming the stall lasts long enough).  It will not affect the
	timing of the next warning for the current stall.

	Stall-warning messages may be enabled and disabled completely via
	/sys/module/rcupdate/parameters/rcu_cpu_stall_suppress.

CONFIG_RCU_EXP_CPU_STALL_TIMEOUT
--------------------------------

	Same as the CONFIG_RCU_CPU_STALL_TIMEOUT parameter but only for
	the expedited grace period. This parameter defines the period
	of time that RCU will wait from the beginning of an expedited
	grace period until it issues an RCU CPU stall warning. This time
	period is normally 20 milliseconds on Android devices.	A zero
	value causes the CONFIG_RCU_CPU_STALL_TIMEOUT value to be used,
	after conversion to milliseconds.

	This configuration parameter may be changed at runtime via the
	/sys/module/rcupdate/parameters/rcu_exp_cpu_stall_timeout, however
	this parameter is checked only at the beginning of a cycle. If you
	are in a current stall cycle, setting it to a new value will change
	the timeout for the -next- stall.

	Stall-warning messages may be enabled and disabled completely via
	/sys/module/rcupdate/parameters/rcu_cpu_stall_suppress.

RCU_STALL_DELAY_DELTA
---------------------

	Although the lockdep facility is extremely useful, it does add
	some overhead.  Therefore, under CONFIG_PROVE_RCU, the
	RCU_STALL_DELAY_DELTA macro allows five extra seconds before
	giving an RCU CPU stall warning message.  (This is a cpp
	macro, not a kernel configuration parameter.)

RCU_STALL_RAT_DELAY
-------------------

	The CPU stall detector tries to make the offending CPU print its
	own warnings, as this often gives better-quality stack traces.
	However, if the offending CPU does not detect its own stall in
	the number of jiffies specified by RCU_STALL_RAT_DELAY, then
	some other CPU will complain.  This delay is normally set to
	two jiffies.  (This is a cpp macro, not a kernel configuration
	parameter.)

rcupdate.rcu_task_stall_timeout
-------------------------------

	This boot/sysfs parameter controls the RCU-tasks and
	RCU-tasks-trace stall warning intervals.  A value of zero or less
	suppresses RCU-tasks stall warnings.  A positive value sets the
	stall-warning interval in seconds.  An RCU-tasks stall warning
	starts with the line:

		INFO: rcu_tasks detected stalls on tasks:

	And continues with the output of sched_show_task() for each
	task stalling the current RCU-tasks grace period.

	An RCU-tasks-trace stall warning starts (and continues) similarly:

		INFO: rcu_tasks_trace detected stalls on tasks


Interpreting RCU's CPU Stall-Detector "Splats"
==============================================

For non-RCU-tasks flavors of RCU, when a CPU detects that some other
CPU is stalling, it will print a message similar to the following::

	INFO: rcu_sched detected stalls on CPUs/tasks:
	2-...: (3 GPs behind) idle=06c/0/0 softirq=1453/1455 fqs=0
	16-...: (0 ticks this GP) idle=81c/0/0 softirq=764/764 fqs=0
	(detected by 32, t=2603 jiffies, g=7075, q=625)

This message indicates that CPU 32 detected that CPUs 2 and 16 were both
causing stalls, and that the stall was affecting RCU-sched.  This message
will normally be followed by stack dumps for each CPU.  Please note that
PREEMPT_RCU builds can be stalled by tasks as well as by CPUs, and that
the tasks will be indicated by PID, for example, "P3421".  It is even
possible for an rcu_state stall to be caused by both CPUs *and* tasks,
in which case the offending CPUs and tasks will all be called out in the list.
In some cases, CPUs will detect themselves stalling, which will result
in a self-detected stall.

CPU 2's "(3 GPs behind)" indicates that this CPU has not interacted with
the RCU core for the past three grace periods.  In contrast, CPU 16's "(0
ticks this GP)" indicates that this CPU has not taken any scheduling-clock
interrupts during the current stalled grace period.

The "idle=" portion of the message prints the dyntick-idle state.
The hex number before the first "/" is the low-order 16 bits of the
dynticks counter, which will have an even-numbered value if the CPU
is in dyntick-idle mode and an odd-numbered value otherwise.  The hex
number between the two "/"s is the value of the nesting, which will be
a small non-negative number if in the idle loop (as shown above) and a
very large positive number otherwise.  The number following the final
"/" is the NMI nesting, which will be a small non-negative number.

The "softirq=" portion of the message tracks the number of RCU softirq
handlers that the stalled CPU has executed.  The number before the "/"
is the number that had executed since boot at the time that this CPU
last noted the beginning of a grace period, which might be the current
(stalled) grace period, or it might be some earlier grace period (for
example, if the CPU might have been in dyntick-idle mode for an extended
time period).  The number after the "/" is the number that have executed
since boot until the current time.  If this latter number stays constant
across repeated stall-warning messages, it is possible that RCU's softirq
handlers are no longer able to execute on this CPU.  This can happen if
the stalled CPU is spinning with interrupts are disabled, or, in -rt
kernels, if a high-priority process is starving RCU's softirq handler.

The "fqs=" shows the number of force-quiescent-state idle/offline
detection passes that the grace-period kthread has made across this
CPU since the last time that this CPU noted the beginning of a grace
period.

The "detected by" line indicates which CPU detected the stall (in this
case, CPU 32), how many jiffies have elapsed since the start of the grace
period (in this case 2603), the grace-period sequence number (7075), and
an estimate of the total number of RCU callbacks queued across all CPUs
(625 in this case).

If the grace period ends just as the stall warning starts printing,
there will be a spurious stall-warning message, which will include
the following::

	INFO: Stall ended before state dump start

This is rare, but does happen from time to time in real life.  It is also
possible for a zero-jiffy stall to be flagged in this case, depending
on how the stall warning and the grace-period initialization happen to
interact.  Please note that it is not possible to entirely eliminate this
sort of false positive without resorting to things like stop_machine(),
which is overkill for this sort of problem.

If all CPUs and tasks have passed through quiescent states, but the
grace period has nevertheless failed to end, the stall-warning splat
will include something like the following::

	All QSes seen, last rcu_preempt kthread activity 23807 (4297905177-4297881370), jiffies_till_next_fqs=3, root ->qsmask 0x0

The "23807" indicates that it has been more than 23 thousand jiffies
since the grace-period kthread ran.  The "jiffies_till_next_fqs"
indicates how frequently that kthread should run, giving the number
of jiffies between force-quiescent-state scans, in this case three,
which is way less than 23807.  Finally, the root rcu_node structure's
->qsmask field is printed, which will normally be zero.

If the relevant grace-period kthread has been unable to run prior to
the stall warning, as was the case in the "All QSes seen" line above,
the following additional line is printed::

	rcu_sched kthread starved for 23807 jiffies! g7075 f0x0 RCU_GP_WAIT_FQS(3) ->state=0x1 ->cpu=5
	Unless rcu_sched kthread gets sufficient CPU time, OOM is now expected behavior.

Starving the grace-period kthreads of CPU time can of course result
in RCU CPU stall warnings even when all CPUs and tasks have passed
through the required quiescent states.  The "g" number shows the current
grace-period sequence number, the "f" precedes the ->gp_flags command
to the grace-period kthread, the "RCU_GP_WAIT_FQS" indicates that the
kthread is waiting for a short timeout, the "state" precedes value of the
task_struct ->state field, and the "cpu" indicates that the grace-period
kthread last ran on CPU 5.

If the relevant grace-period kthread does not wake from FQS wait in a
reasonable time, then the following additional line is printed::

	kthread timer wakeup didn't happen for 23804 jiffies! g7076 f0x0 RCU_GP_WAIT_FQS(5) ->state=0x402

The "23804" indicates that kthread's timer expired more than 23 thousand
jiffies ago.  The rest of the line has meaning similar to the kthread
starvation case.

Additionally, the following line is printed::

	Possible timer handling issue on cpu=4 timer-softirq=11142

Here "cpu" indicates that the grace-period kthread last ran on CPU 4,
where it queued the fqs timer.  The number following the "timer-softirq"
is the current ``TIMER_SOFTIRQ`` count on cpu 4.  If this value does not
change on successive RCU CPU stall warnings, there is further reason to
suspect a timer problem.

These messages are usually followed by stack dumps of the CPUs and tasks
involved in the stall.  These stack traces can help you locate the cause
of the stall, keeping in mind that the CPU detecting the stall will have
an interrupt frame that is mainly devoted to detecting the stall.


Multiple Warnings From One Stall
================================

If a stall lasts long enough, multiple stall-warning messages will
be printed for it.  The second and subsequent messages are printed at
longer intervals, so that the time between (say) the first and second
message will be about three times the interval between the beginning
of the stall and the first message.  It can be helpful to compare the
stack dumps for the different messages for the same stalled grace period.


Stall Warnings for Expedited Grace Periods
==========================================

If an expedited grace period detects a stall, it will place a message
like the following in dmesg::

	INFO: rcu_sched detected expedited stalls on CPUs/tasks: { 7-... } 21119 jiffies s: 73 root: 0x2/.

This indicates that CPU 7 has failed to respond to a reschedule IPI.
The three periods (".") following the CPU number indicate that the CPU
is online (otherwise the first period would instead have been "O"),
that the CPU was online at the beginning of the expedited grace period
(otherwise the second period would have instead been "o"), and that
the CPU has been online at least once since boot (otherwise, the third
period would instead have been "N").  The number before the "jiffies"
indicates that the expedited grace period has been going on for 21,119
jiffies.  The number following the "s:" indicates that the expedited
grace-period sequence counter is 73.  The fact that this last value is
odd indicates that an expedited grace period is in flight.  The number
following "root:" is a bitmask that indicates which children of the root
rcu_node structure correspond to CPUs and/or tasks that are blocking the
current expedited grace period.  If the tree had more than one level,
additional hex numbers would be printed for the states of the other
rcu_node structures in the tree.

As with normal grace periods, PREEMPT_RCU builds can be stalled by
tasks as well as by CPUs, and that the tasks will be indicated by PID,
for example, "P3421".

It is entirely possible to see stall warnings from normal and from
expedited grace periods at about the same time during the same run.

RCU_CPU_STALL_CPUTIME
=====================

In kernels built with CONFIG_RCU_CPU_STALL_CPUTIME=y or booted with
rcupdate.rcu_cpu_stall_cputime=1, the following additional information
is supplied with each RCU CPU stall warning::

  rcu:          hardirqs   softirqs   csw/system
  rcu:  number:      624         45            0
  rcu: cputime:       69          1         2425   ==> 2500(ms)

These statistics are collected during the sampling period. The values
in row "number:" are the number of hard interrupts, number of soft
interrupts, and number of context switches on the stalled CPU. The
first three values in row "cputime:" indicate the CPU time in
milliseconds consumed by hard interrupts, soft interrupts, and tasks
on the stalled CPU.  The last number is the measurement interval, again
in milliseconds.  Because user-mode tasks normally do not cause RCU CPU
stalls, these tasks are typically kernel tasks, which is why only the
system CPU time are considered.

The sampling period is shown as follows::

  |<------------first timeout---------->|<-----second timeout----->|
  |<--half timeout-->|<--half timeout-->|                          |
  |                  |<--first period-->|                          |
  |                  |<-----------second sampling period---------->|
  |                  |                  |                          |
             snapshot time point    1st-stall                  2nd-stall

The following describes four typical scenarios:

1. A CPU looping with interrupts disabled.

   ::

     rcu:          hardirqs   softirqs   csw/system
     rcu:  number:        0          0            0
     rcu: cputime:        0          0            0   ==> 2500(ms)

   Because interrupts have been disabled throughout the measurement
   interval, there are no interrupts and no context switches.
   Furthermore, because CPU time consumption was measured using interrupt
   handlers, the system CPU consumption is misleadingly measured as zero.
   This scenario will normally also have "(0 ticks this GP)" printed on
   this CPU's summary line.

2. A CPU looping with bottom halves disabled.

   This is similar to the previous example, but with non-zero number of
   and CPU time consumed by hard interrupts, along with non-zero CPU
   time consumed by in-kernel execution::

     rcu:          hardirqs   softirqs   csw/system
     rcu:  number:      624          0            0
     rcu: cputime:       49          0         2446   ==> 2500(ms)

   The fact that there are zero softirqs gives a hint that these were
   disabled, perhaps via local_bh_disable().  It is of course possible
   that there were no softirqs, perhaps because all events that would
   result in softirq execution are confined to other CPUs.  In this case,
   the diagnosis should continue as shown in the next example.

3. A CPU looping with preemption disabled.

   Here, only the number of context switches is zero::

     rcu:          hardirqs   softirqs   csw/system
     rcu:  number:      624         45            0
     rcu: cputime:       69          1         2425   ==> 2500(ms)

   This situation hints that the stalled CPU was looping with preemption
   disabled.

4. No looping, but massive hard and soft interrupts.

   ::

     rcu:          hardirqs   softirqs   csw/system
     rcu:  number:       xx         xx            0
     rcu: cputime:       xx         xx            0   ==> 2500(ms)

   Here, the number and CPU time of hard interrupts are all non-zero,
   but the number of context switches and the in-kernel CPU time consumed
   are zero. The number and cputime of soft interrupts will usually be
   non-zero, but could be zero, for example, if the CPU was spinning
   within a single hard interrupt handler.

   If this type of RCU CPU stall warning can be reproduced, you can
   narrow it down by looking at /proc/interrupts or by writing code to
   trace each interrupt, for example, by referring to show_interrupts().

---

### Documentation RCU Torture (`Documentation/RCU/torture.rst`)

.. SPDX-License-Identifier: GPL-2.0

==========================
RCU Torture Test Operation
==========================


CONFIG_RCU_TORTURE_TEST
=======================

The CONFIG_RCU_TORTURE_TEST config option is available for all RCU
implementations.  It creates an rcutorture kernel module that can
be loaded to run a torture test.  The test periodically outputs
status messages via printk(), which can be examined via the dmesg
command (perhaps grepping for "torture").  The test is started
when the module is loaded, and stops when the module is unloaded.

Module parameters are prefixed by "rcutorture." in
Documentation/admin-guide/kernel-parameters.txt.

Output
======

The statistics output is as follows::

	rcu-torture:--- Start of test: nreaders=16 nfakewriters=4 stat_interval=30 verbose=0 test_no_idle_hz=1 shuffle_interval=3 stutter=5 irqreader=1 fqs_duration=0 fqs_holdoff=0 fqs_stutter=3 test_boost=1/0 test_boost_interval=7 test_boost_duration=4
	rcu-torture: rtc:           (null) ver: 155441 tfle: 0 rta: 155441 rtaf: 8884 rtf: 155440 rtmbe: 0 rtbe: 0 rtbke: 0 rtbre: 0 rtbf: 0 rtb: 0 nt: 3055767
	rcu-torture: Reader Pipe:  727860534 34213 0 0 0 0 0 0 0 0 0
	rcu-torture: Reader Batch:  727877838 17003 0 0 0 0 0 0 0 0 0
	rcu-torture: Free-Block Circulation:  155440 155440 155440 155440 155440 155440 155440 155440 155440 155440 0
	rcu-torture:--- End of test: SUCCESS: nreaders=16 nfakewriters=4 stat_interval=30 verbose=0 test_no_idle_hz=1 shuffle_interval=3 stutter=5 irqreader=1 fqs_duration=0 fqs_holdoff=0 fqs_stutter=3 test_boost=1/0 test_boost_interval=7 test_boost_duration=4

The command "dmesg | grep torture:" will extract this information on
most systems.  On more esoteric configurations, it may be necessary to
use other commands to access the output of the printk()s used by
the RCU torture test.  The printk()s use KERN_ALERT, so they should
be evident.  ;-)

The first and last lines show the rcutorture module parameters, and the
last line shows either "SUCCESS" or "FAILURE", based on rcutorture's
automatic determination as to whether RCU operated correctly.

The entries are as follows:

*	"rtc": The hexadecimal address of the structure currently visible
	to readers.

*	"ver": The number of times since boot that the RCU writer task
	has changed the structure visible to readers.

*	"tfle": If non-zero, indicates that the "torture freelist"
	containing structures to be placed into the "rtc" area is empty.
	This condition is important, since it can fool you into thinking
	that RCU is working when it is not.  :-/

*	"rta": Number of structures allocated from the torture freelist.

*	"rtaf": Number of allocations from the torture freelist that have
	failed due to the list being empty.  It is not unusual for this
	to be non-zero, but it is bad for it to be a large fraction of
	the value indicated by "rta".

*	"rtf": Number of frees into the torture freelist.

*	"rtmbe": A non-zero value indicates that rcutorture believes that
	rcu_assign_pointer() and rcu_dereference() are not working
	correctly.  This value should be zero.

*	"rtbe": A non-zero value indicates that one of the rcu_barrier()
	family of functions is not working correctly.

*	"rtbke": rcutorture was unable to create the real-time kthreads
	used to force RCU priority inversion.  This value should be zero.

*	"rtbre": Although rcutorture successfully created the kthreads
	used to force RCU priority inversion, it was unable to set them
	to the real-time priority level of 1.  This value should be zero.

*	"rtbf": The number of times that RCU priority boosting failed
	to resolve RCU priority inversion.

*	"rtb": The number of times that rcutorture attempted to force
	an RCU priority inversion condition.  If you are testing RCU
	priority boosting via the "test_boost" module parameter, this
	value should be non-zero.

*	"nt": The number of times rcutorture ran RCU read-side code from
	within a timer handler.  This value should be non-zero only
	if you specified the "irqreader" module parameter.

*	"Reader Pipe": Histogram of "ages" of structures seen by readers.
	If any entries past the first two are non-zero, RCU is broken.
	And rcutorture prints the error flag string "!!!" to make sure
	you notice.  The age of a newly allocated structure is zero,
	it becomes one when removed from reader visibility, and is
	incremented once per grace period subsequently -- and is freed
	after passing through (RCU_TORTURE_PIPE_LEN-2) grace periods.

	The output displayed above was taken from a correctly working
	RCU.  If you want to see what it looks like when broken, break
	it yourself.  ;-)

*	"Reader Batch": Another histogram of "ages" of structures seen
	by readers, but in terms of counter flips (or batches) rather
	than in terms of grace periods.  The legal number of non-zero
	entries is again two.  The reason for this separate view is that
	it is sometimes easier to get the third entry to show up in the
	"Reader Batch" list than in the "Reader Pipe" list.

*	"Free-Block Circulation": Shows the number of torture structures
	that have reached a given point in the pipeline.  The first element
	should closely correspond to the number of structures allocated,
	the second to the number that have been removed from reader view,
	and all but the last remaining to the corresponding number of
	passes through a grace period.  The last entry should be zero,
	as it is only incremented if a torture structure's counter
	somehow gets incremented farther than it should.

Different implementations of RCU can provide implementation-specific
additional information.  For example, Tree SRCU provides the following
additional line::

	srcud-torture: Tree SRCU per-CPU(idx=0): 0(35,-21) 1(-4,24) 2(1,1) 3(-26,20) 4(28,-47) 5(-9,4) 6(-10,14) 7(-14,11) T(1,6)

This line shows the per-CPU counter state, in this case for Tree SRCU
using a dynamically allocated srcu_struct (hence "srcud-" rather than
"srcu-").  The numbers in parentheses are the values of the "old" and
"current" counters for the corresponding CPU.  The "idx" value maps the
"old" and "current" values to the underlying array, and is useful for
debugging.  The final "T" entry contains the totals of the counters.

Usage on Specific Kernel Builds
===============================

It is sometimes desirable to torture RCU on a specific kernel build,
for example, when preparing to put that kernel build into production.
In that case, the kernel should be built with CONFIG_RCU_TORTURE_TEST=m
so that the test can be started using modprobe and terminated using rmmod.

For example, the following script may be used to torture RCU::

	#!/bin/sh

	modprobe rcutorture
	sleep 3600
	rmmod rcutorture
	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 RCU failures, CPU-hotplug problems were detected.


Usage on Mainline Kernels
=========================

When using rcutorture to test changes to RCU itself, it is often
necessary to build a number of kernels in order to test that change
across a broad range of combinations of the relevant Kconfig options
and of the relevant kernel boot parameters.  In this situation, use
of modprobe and rmmod can be quite time-consuming and error-prone.

Therefore, the tools/testing/selftests/rcutorture/bin/kvm.sh
script is available for mainline testing for x86, arm64, and
powerpc.  By default, it will run the series of tests specified by
tools/testing/selftests/rcutorture/configs/rcu/CFLIST, with each test
running for 30 minutes within a guest OS using a minimal userspace
supplied by an automatically generated initrd.  After the tests are
complete, the resulting build products and console output are analyzed
for errors and the results of the runs are summarized.

On larger systems, rcutorture testing can be accelerated by passing the
--cpus argument to kvm.sh.  For example, on a 64-CPU system, "--cpus 43"
would use up to 43 CPUs to run tests concurrently, which as of v5.4 would
complete all the scenarios in two batches, reducing the time to complete
from about eight hours to about one hour (not counting the time to build
the sixteen kernels).  The "--dryrun sched" argument will not run tests,
but rather tell you how the tests would be scheduled into batches.  This
can be useful when working out how many CPUs to specify in the --cpus
argument.

Not all changes require that all scenarios be run.  For example, a change
to Tree SRCU might run only the SRCU-N and SRCU-P scenarios using the
--configs argument to kvm.sh as follows:  "--configs 'SRCU-N SRCU-P'".
Large systems can run multiple copies of the full set of scenarios,
for example, a system with 448 hardware threads can run five instances
of the full set concurrently.  To make this happen::

	kvm.sh --cpus 448 --configs '5*CFLIST'

Alternatively, such a system can run 56 concurrent instances of a single
eight-CPU scenario::

	kvm.sh --cpus 448 --configs '56*TREE04'

Or 28 concurrent instances of each of two eight-CPU scenarios::

	kvm.sh --cpus 448 --configs '28*TREE03 28*TREE04'

Of course, each concurrent instance will use memory, which can be
limited using the --memory argument, which defaults to 512M.  Small
values for memory may require disabling the callback-flooding tests
using the --bootargs parameter discussed below.

Sometimes additional debugging is useful, and in such cases the --kconfig
parameter to kvm.sh may be used, for example, ``--kconfig 'CONFIG_RCU_EQS_DEBUG=y'``.
In addition, there are the --gdb, --kasan, and --kcsan parameters.
Note that --gdb limits you to one scenario per kvm.sh run and requires
that you have another window open from which to run ``gdb`` as instructed
by the script.

Kernel boot arguments can also be supplied, for example, to control
rcutorture's module parameters.  For example, to test a change to RCU's
CPU stall-warning code, use "--bootargs 'rcutorture.stall_cpu=30'".
This will of course result in the scripting reporting a failure, namely
the resulting RCU CPU stall warning.  As noted above, reducing memory may
require disabling rcutorture's callback-flooding tests::

	kvm.sh --cpus 448 --configs '56*TREE04' --memory 128M \
		--bootargs 'rcutorture.fwd_progress=0'

Sometimes all that is needed is a full set of kernel builds.  This is
what the --buildonly parameter does.

The --duration parameter can override the default run time of 30 minutes.
For example, ``--duration 2d`` would run for two days, ``--duration 3h``
would run for three hours, ``--duration 5m`` would run for five minutes,
and ``--duration 45s`` would run for 45 seconds.  This last can be useful
for tracking down rare boot-time failures.

Finally, the --trust-make parameter allows each kernel build to reuse what
it can from the previous kernel build.  Please note that without the
--trust-make parameter, your tags files may be demolished.

There are additional more arcane arguments that are documented in the
source code of the kvm.sh script.

If a run contains failures, the number of buildtime and runtime failures
is listed at the end of the kvm.sh output, which you really should redirect
to a file.  The build products and console output of each run is kept in
tools/testing/selftests/rcutorture/res in timestamped directories.  A
given directory can be supplied to kvm-find-errors.sh in order to have
it cycle you through summaries of errors and full error logs.  For example::

	tools/testing/selftests/rcutorture/bin/kvm-find-errors.sh \
		tools/testing/selftests/rcutorture/res/2020.01.20-15.54.23

However, it is often more convenient to access the files directly.
Files pertaining to all scenarios in a run reside in the top-level
directory (2020.01.20-15.54.23 in the example above), while per-scenario
files reside in a subdirectory named after the scenario (for example,
"TREE04").  If a given scenario ran more than once (as in "--configs
'56*TREE04'" above), the directories corresponding to the second and
subsequent runs of that scenario include a sequence number, for example,
"TREE04.2", "TREE04.3", and so on.

The most frequently used file in the top-level directory is testid.txt.
If the test ran in a git repository, then this file contains the commit
that was tested and any uncommitted changes in diff format.

The most frequently used files in each per-scenario-run directory are:

.config:
	This file contains the Kconfig options.

Make.out:
	This contains build output for a specific scenario.

console.log:
	This contains the console output for a specific scenario.
	This file may be examined once the kernel has booted, but
	it might not exist if the build failed.

vmlinux:
	This contains the kernel, which can be useful with tools like
	objdump and gdb.

A number of additional files are available, but are less frequently used.
Many are intended for debugging of rcutorture itself or of its scripting.

As of v5.4, a successful run with the default set of scenarios produces
the following summary at the end of the run on a 12-CPU system::

    SRCU-N ------- 804233 GPs (148.932/s) [srcu: g10008272 f0x0 ]
    SRCU-P ------- 202320 GPs (37.4667/s) [srcud: g1809476 f0x0 ]
    SRCU-t ------- 1122086 GPs (207.794/s) [srcu: g0 f0x0 ]
    SRCU-u ------- 1111285 GPs (205.794/s) [srcud: g1 f0x0 ]
    TASKS01 ------- 19666 GPs (3.64185/s) [tasks: g0 f0x0 ]
    TASKS02 ------- 20541 GPs (3.80389/s) [tasks: g0 f0x0 ]
    TASKS03 ------- 19416 GPs (3.59556/s) [tasks: g0 f0x0 ]
    TINY01 ------- 836134 GPs (154.84/s) [rcu: g0 f0x0 ] n_max_cbs: 34198
    TINY02 ------- 850371 GPs (157.476/s) [rcu: g0 f0x0 ] n_max_cbs: 2631
    TREE01 ------- 162625 GPs (30.1157/s) [rcu: g1124169 f0x0 ]
    TREE02 ------- 333003 GPs (61.6672/s) [rcu: g2647753 f0x0 ] n_max_cbs: 35844
    TREE03 ------- 306623 GPs (56.782/s) [rcu: g2975325 f0x0 ] n_max_cbs: 1496497
    CPU count limited from 16 to 12
    TREE04 ------- 246149 GPs (45.5831/s) [rcu: g1695737 f0x0 ] n_max_cbs: 434961
    TREE05 ------- 314603 GPs (58.2598/s) [rcu: g2257741 f0x2 ] n_max_cbs: 193997
    TREE07 ------- 167347 GPs (30.9902/s) [rcu: g1079021 f0x0 ] n_max_cbs: 478732
    CPU count limited from 16 to 12
    TREE09 ------- 752238 GPs (139.303/s) [rcu: g13075057 f0x0 ] n_max_cbs: 99011


Repeated Runs
=============

Suppose that you are chasing down a rare boot-time failure.  Although you
could use kvm.sh, doing so will rebuild the kernel on each run.  If you
need (say) 1,000 runs to have confidence that you have fixed the bug,
these pointless rebuilds can become extremely annoying.

This is why kvm-again.sh exists.

Suppose that a previous kvm.sh run left its output in this directory::

	tools/testing/selftests/rcutorture/res/2022.11.03-11.26.28

Then this run can be re-run without rebuilding as follow::

	kvm-again.sh tools/testing/selftests/rcutorture/res/2022.11.03-11.26.28

A few of the original run's kvm.sh parameters may be overridden, perhaps
most notably --duration and --bootargs.  For example::

	kvm-again.sh tools/testing/selftests/rcutorture/res/2022.11.03-11.26.28 \
		--duration 45s

would re-run the previous test, but for only 45 seconds, thus facilitating
tracking down the aforementioned rare boot-time failure.


Distributed Runs
================

Although kvm.sh is quite useful, its testing is confined to a single
system.  It is not all that hard to use your favorite framework to cause
(say) 5 instances of kvm.sh to run on your 5 systems, but this will very
likely unnecessarily rebuild kernels.  In addition, manually distributing
the desired rcutorture scenarios across the available systems can be
painstaking and error-prone.

And this is why the kvm-remote.sh script exists.

If the following command works::

	ssh system0 date

and if it also works for system1, system2, system3, system4, and system5,
and all of these systems have 64 CPUs, you can type::

	kvm-remote.sh "system0 system1 system2 system3 system4 system5" \
		--cpus 64 --duration 8h --configs "5*CFLIST"

This will build each default scenario's kernel on the local system, then
spread each of five instances of each scenario over the systems listed,
running each scenario for eight hours.  At the end of the runs, the
results will be gathered, recorded, and printed.  Most of the parameters
that kvm.sh will accept can be passed to kvm-remote.sh, but the list of
systems must come first.

The kvm.sh ``--dryrun scenarios`` argument is useful for working out
how many scenarios may be run in one batch across a group of systems.

You can also re-run a previous remote run in a manner similar to kvm.sh::

	kvm-remote.sh "system0 system1 system2 system3 system4 system5" \
		tools/testing/selftests/rcutorture/res/2022.11.03-11.26.28-remote \
		--duration 24h

In this case, most of the kvm-again.sh parameters may be supplied following
the pathname of the old run-results directory.

---

### Documentation RCU WhatisRCU (`Documentation/RCU/whatisRCU.rst`)

.. _whatisrcu_doc:

What is RCU?  --  "Read, Copy, Update"
======================================

Please note that the "What is RCU?" LWN series is an excellent place
to start learning about RCU:

| 1.	What is RCU, Fundamentally?  https://lwn.net/Articles/262464/
| 2.	What is RCU? Part 2: Usage   https://lwn.net/Articles/263130/
| 3.	RCU part 3: the RCU API      https://lwn.net/Articles/264090/
| 4.	The RCU API, 2010 Edition    https://lwn.net/Articles/418853/
| 	2010 Big API Table           https://lwn.net/Articles/419086/
| 5.	The RCU API, 2014 Edition    https://lwn.net/Articles/609904/
|	2014 Big API Table           https://lwn.net/Articles/609973/
| 6.	The RCU API, 2019 Edition    https://lwn.net/Articles/777036/
|	2019 Big API Table           https://lwn.net/Articles/777165/
| 7.	The RCU API, 2024 Edition    https://lwn.net/Articles/988638/
|       2024 Background Information  https://lwn.net/Articles/988641/
|	2024 Big API Table           https://lwn.net/Articles/988666/

For those preferring video:

| 1.	Unraveling RCU Mysteries: Fundamentals          https://www.linuxfoundation.org/webinars/unraveling-rcu-usage-mysteries
| 2.	Unraveling RCU Mysteries: Additional Use Cases  https://www.linuxfoundation.org/webinars/unraveling-rcu-usage-mysteries-additional-use-cases


What is RCU?

RCU is a synchronization mechanism that was added to the Linux kernel
during the 2.5 development effort that is optimized for read-mostly
situations.  Although RCU is actually quite simple, making effective use
of it requires you to think differently about your code.  Another part
of the problem is the mistaken assumption that there is "one true way" to
describe and to use RCU.  Instead, the experience has been that different
people must take different paths to arrive at an understanding of RCU,
depending on their experiences and use cases.  This document provides
several different paths, as follows:

:ref:`1.	RCU OVERVIEW <1_whatisRCU>`

:ref:`2.	WHAT IS RCU'S CORE API? <2_whatisRCU>`

:ref:`3.	WHAT ARE SOME EXAMPLE USES OF CORE RCU API? <3_whatisRCU>`

:ref:`4.	WHAT IF MY UPDATING THREAD CANNOT BLOCK? <4_whatisRCU>`

:ref:`5.	WHAT ARE SOME SIMPLE IMPLEMENTATIONS OF RCU? <5_whatisRCU>`

:ref:`6.	ANALOGY WITH READER-WRITER LOCKING <6_whatisRCU>`

:ref:`7.	ANALOGY WITH REFERENCE COUNTING <7_whatisRCU>`

:ref:`8.	FULL LIST OF RCU APIs <8_whatisRCU>`

:ref:`9.	ANSWERS TO QUICK QUIZZES <9_whatisRCU>`

People who prefer starting with a conceptual overview should focus on
Section 1, though most readers will profit by reading this section at
some point.  People who prefer to start with an API that they can then
experiment with should focus on Section 2.  People who prefer to start
with example uses should focus on Sections 3 and 4.  People who need to
understand the RCU implementation should focus on Section 5, then dive
into the kernel source code.  People who reason best by analogy should
focus on Section 6 and 7.  Section 8 serves as an index to the docbook
API documentation, and Section 9 is the traditional answer key.

So, start with the section that makes the most sense to you and your
preferred method of learning.  If you need to know everything about
everything, feel free to read the whole thing -- but if you are really
that type of person, you have perused the source code and will therefore
never need this document anyway.  ;-)

.. _1_whatisRCU:

1.  RCU OVERVIEW
----------------

The basic idea behind RCU is to split updates into "removal" and
"reclamation" phases.  The removal phase removes references to data items
within a data structure (possibly by replacing them with references to
new versions of these data items), and can run concurrently with readers.
The reason that it is safe to run the removal phase concurrently with
readers is the semantics of modern CPUs guarantee that readers will see
either the old or the new version of the data structure rather than a
partially updated reference.  The reclamation phase does the work of reclaiming
(e.g., freeing) the data items removed from the data structure during the
removal phase.  Because reclaiming data items can disrupt any readers
concurrently referencing those data items, the reclamation phase must
not start until readers no longer hold references to those data items.

Splitting the update into removal and reclamation phases permits the
updater to perform the removal phase immediately, and to defer the
reclamation phase until all readers active during the removal phase have
completed, either by blocking until they finish or by registering a
callback that is invoked after they finish.  Only readers that are active
during the removal phase need be considered, because any reader starting
after the removal phase will be unable to gain a reference to the removed
data items, and therefore cannot be disrupted by the reclamation phase.

So the typical RCU update sequence goes something like the following:

a.	Remove pointers to a data structure, so that subsequent
	readers cannot gain a reference to it.

b.	Wait for all previous readers to complete their RCU read-side
	critical sections.

c.	At this point, there cannot be any readers who hold references
	to the data structure, so it now may safely be reclaimed
	(e.g., kfree()d).

Step (b) above is the key idea underlying RCU's deferred destruction.
The ability to wait until all readers are done allows RCU readers to
use much lighter-weight synchronization, in some cases, absolutely no
synchronization at all.  In contrast, in more conventional lock-based
schemes, readers must use heavy-weight synchronization in order to
prevent an updater from deleting the data structure out from under them.
This is because lock-based updaters typically update data items in place,
and must therefore exclude readers.  In contrast, RCU-based updaters
typically take advantage of the fact that writes to single aligned
pointers are atomic on modern CPUs, allowing atomic insertion, removal,
and replacement of data items in a linked structure without disrupting
readers.  Concurrent RCU readers can then continue accessing the old
versions, and can dispense with the atomic operations, memory barriers,
and communications cache misses that are so expensive on present-day
SMP computer systems, even in absence of lock contention.

In the three-step procedure shown above, the updater is performing both
the removal and the reclamation step, but it is often helpful for an
entirely different thread to do the reclamation, as is in fact the case
in the Linux kernel's directory-entry cache (dcache).  Even if the same
thread performs both the update step (step (a) above) and the reclamation
step (step (c) above), it is often helpful to think of them separately.
For example, RCU readers and updaters need not communicate at all,
but RCU provides implicit low-overhead communication between readers
and reclaimers, namely, in step (b) above.

So how the heck can a reclaimer tell when a reader is done, given
that readers are not doing any sort of synchronization operations???
Read on to learn about how RCU's API makes this easy.

.. _2_whatisRCU:

2.  WHAT IS RCU'S CORE API?
---------------------------

The core RCU API is quite small:

a.	rcu_read_lock()
b.	rcu_read_unlock()
c.	synchronize_rcu() / call_rcu()
d.	rcu_assign_pointer()
e.	rcu_dereference()

There are many other members of the RCU API, but the rest can be
expressed in terms of these five, though most implementations instead
express synchronize_rcu() in terms of the call_rcu() callback API.

The five core RCU APIs are described below, the other 18 will be enumerated
later.  See the kernel docbook documentation for more info, or look directly
at the function header comments.

rcu_read_lock()
^^^^^^^^^^^^^^^
	void rcu_read_lock(void);

	This temporal primitive is used by a reader to inform the
	reclaimer that the reader is entering an RCU read-side critical
	section.  It is illegal to block while in an RCU read-side
	critical section, though kernels built with CONFIG_PREEMPT_RCU
	can preempt RCU read-side critical sections.  Any RCU-protected
	data structure accessed during an RCU read-side critical section
	is guaranteed to remain unreclaimed for the full duration of that
	critical section.  Reference counts may be used in conjunction
	with RCU to maintain longer-term references to data structures.

	Note that anything that disables bottom halves, preemption,
	or interrupts also enters an RCU read-side critical section.
	Acquiring a spinlock also enters an RCU read-side critical
	sections, even for spinlocks that do not disable preemption,
	as is the case in kernels built with CONFIG_PREEMPT_RT=y.
	Sleeplocks do *not* enter RCU read-side critical sections.

rcu_read_unlock()
^^^^^^^^^^^^^^^^^
	void rcu_read_unlock(void);

	This temporal primitives is used by a reader to inform the
	reclaimer that the reader is exiting an RCU read-side critical
	section.  Anything that enables bottom halves, preemption,
	or interrupts also exits an RCU read-side critical section.
	Releasing a spinlock also exits an RCU read-side critical section.

	Note that RCU read-side critical sections may be nested and/or
	overlapping.

synchronize_rcu()
^^^^^^^^^^^^^^^^^
	void synchronize_rcu(void);

	This temporal primitive marks the end of updater code and the
	beginning of reclaimer code.  It does this by blocking until
	all pre-existing RCU read-side critical sections on all CPUs
	have completed.  Note that synchronize_rcu() will **not**
	necessarily wait for any subsequent RCU read-side critical
	sections to complete.  For example, consider the following
	sequence of events::

	         CPU 0                  CPU 1                 CPU 2
	     ----------------- ------------------------- ---------------
	 1.  rcu_read_lock()
	 2.                    enters synchronize_rcu()
	 3.                                               rcu_read_lock()
	 4.  rcu_read_unlock()
	 5.                     exits synchronize_rcu()
	 6.                                              rcu_read_unlock()

	To reiterate, synchronize_rcu() waits only for ongoing RCU
	read-side critical sections to complete, not necessarily for
	any that begin after synchronize_rcu() is invoked.

	Of course, synchronize_rcu() does not necessarily return
	**immediately** after the last pre-existing RCU read-side critical
	section completes.  For one thing, there might well be scheduling
	delays.  For another thing, many RCU implementations process
	requests in batches in order to improve efficiencies, which can
	further delay synchronize_rcu().

	Since synchronize_rcu() is the API that must figure out when
	readers are done, its implementation is key to RCU.  For RCU
	to be useful in all but the most read-intensive situations,
	synchronize_rcu()'s overhead must also be quite small.

	The call_rcu() API is an asynchronous callback form of
	synchronize_rcu(), and is described in more detail in a later
	section.  Instead of blocking, it registers a function and
	argument which are invoked after all ongoing RCU read-side
	critical sections have completed.  This callback variant is
	particularly useful in situations where it is illegal to block
	or where update-side performance is critically important.

	However, the call_rcu() API should not be used lightly, as use
	of the synchronize_rcu() API generally results in simpler code.
	In addition, the synchronize_rcu() API has the nice property
	of automatically limiting update rate should grace periods
	be delayed.  This property results in system resilience in face
	of denial-of-service attacks.  Code using call_rcu() should limit
	update rate in order to gain this same sort of resilience.  See
	checklist.rst for some approaches to limiting the update rate.

rcu_assign_pointer()
^^^^^^^^^^^^^^^^^^^^
	void rcu_assign_pointer(p, typeof(p) v);

	Yes, rcu_assign_pointer() **is** implemented as a macro, though
	it would be cool to be able to declare a function in this manner.
	(And there has been some discussion of adding overloaded functions
	to the C language, so who knows?)

	The updater uses this spatial macro to assign a new value to an
	RCU-protected pointer, in order to safely communicate the change
	in value from the updater to the reader.  This is a spatial (as
	opposed to temporal) macro.  It does not evaluate to an rvalue,
	but it does provide any compiler directives and memory-barrier
	instructions required for a given compile or CPU architecture.
	Its ordering properties are that of a store-release operation,
	that is, any prior loads and stores required to initialize the
	structure are ordered before the store that publishes the pointer
	to that structure.

	Perhaps just as important, rcu_assign_pointer() serves to document
	(1) which pointers are protected by RCU and (2) the point at which
	a given structure becomes accessible to other CPUs.  That said,
	rcu_assign_pointer() is most frequently used indirectly, via
	the _rcu list-manipulation primitives such as list_add_rcu().

rcu_dereference()
^^^^^^^^^^^^^^^^^
	typeof(p) rcu_dereference(p);

	Like rcu_assign_pointer(), rcu_dereference() must be implemented
	as a macro.

	The reader uses the spatial rcu_dereference() macro to fetch
	an RCU-protected pointer, which returns a value that may
	then be safely dereferenced.  Note that rcu_dereference()
	does not actually dereference the pointer, instead, it
	protects the pointer for later dereferencing.  It also
	executes any needed memory-barrier instructions for a given
	CPU architecture.  Currently, only Alpha needs memory barriers
	within rcu_dereference() -- on other CPUs, it compiles to a
	volatile load.	However, no mainstream C compilers respect
	address dependencies, so rcu_dereference() uses volatile casts,
	which, in combination with the coding guidelines listed in
	rcu_dereference.rst, prevent current compilers from breaking
	these dependencies.

	Common coding practice uses rcu_dereference() to copy an
	RCU-protected pointer to a local variable, then dereferences
	this local variable, for example as follows::

		p = rcu_dereference(head.next);
		return p->data;

	However, in this case, one could just as easily combine these
	into one statement::

		return rcu_dereference(head.next)->data;

	If you are going to be fetching multiple fields from the
	RCU-protected structure, using the local variable is of
	course preferred.  Repeated rcu_dereference() calls look
	ugly, do not guarantee that the same pointer will be returned
	if an update happened while in the critical section, and incur
	unnecessary overhead on Alpha CPUs.

	Note that the value returned by rcu_dereference() is valid
	only within the enclosing RCU read-side critical section [1]_.
	For example, the following is **not** legal::

		rcu_read_lock();
		p = rcu_dereference(head.next);
		rcu_read_unlock();
		x = p->address;	/* BUG!!! */
		rcu_read_lock();
		y = p->data;	/* BUG!!! */
		rcu_read_unlock();

	Holding a reference from one RCU read-side critical section
	to another is just as illegal as holding a reference from
	one lock-based critical section to another!  Similarly,
	using a reference outside of the critical section in which
	it was acquired is just as illegal as doing so with normal
	locking.

	As with rcu_assign_pointer(), an important function of
	rcu_dereference() is to document which pointers are protected by
	RCU, in particular, flagging a pointer that is subject to changing
	at any time, including immediately after the rcu_dereference().
	And, again like rcu_assign_pointer(), rcu_dereference() is
	typically used indirectly, via the _rcu list-manipulation
	primitives, such as list_for_each_entry_rcu() [2]_.

.. 	[1] The variant rcu_dereference_protected() can be used outside
	of an RCU read-side critical section as long as the usage is
	protected by locks acquired by the update-side code.  This variant
	avoids the lockdep warning that would happen when using (for
	example) rcu_dereference() without rcu_read_lock() protection.
	Using rcu_dereference_protected() also has the advantage
	of permitting compiler optimizations that rcu_dereference()
	must prohibit.	The rcu_dereference_protected() variant takes
	a lockdep expression to indicate which locks must be acquired
	by the caller. If the indicated protection is not provided,
	a lockdep splat is emitted.  See Design/Requirements/Requirements.rst
	and the API's code comments for more details and example usage.

.. 	[2] If the list_for_each_entry_rcu() instance might be used by
	update-side code as well as by RCU readers, then an additional
	lockdep expression can be added to its list of arguments.
	For example, given an additional "lock_is_held(&mylock)" argument,
	the RCU lockdep code would complain only if this instance was
	invoked outside of an RCU read-side critical section and without
	the protection of mylock.

The following diagram shows how each API communicates among the
reader, updater, and reclaimer.
::


	    rcu_assign_pointer()
	                            +--------+
	    +---------------------->| reader |---------+
	    |                       +--------+         |
	    |                           |              |
	    |                           |              | Protect:
	    |                           |              | rcu_read_lock()
	    |                           |              | rcu_read_unlock()
	    |        rcu_dereference()  |              |
	    +---------+                 |              |
	    | updater |<----------------+              |
	    +---------+                                V
	    |                                    +-----------+
	    +----------------------------------->| reclaimer |
	                                         +-----------+
	      Defer:
	      synchronize_rcu() & call_rcu()


The RCU infrastructure observes the temporal sequence of rcu_read_lock(),
rcu_read_unlock(), synchronize_rcu(), and call_rcu() invocations in
order to determine when (1) synchronize_rcu() invocations may return
to their callers and (2) call_rcu() callbacks may be invoked.  Efficient
implementations of the RCU infrastructure make heavy use of batching in
order to amortize their overhead over many uses of the corresponding APIs.
The rcu_assign_pointer() and rcu_dereference() invocations communicate
spatial changes via stores to and loads from the RCU-protected pointer in
question.

There are at least three flavors of RCU usage in the Linux kernel. The diagram
above shows the most common one. On the updater side, the rcu_assign_pointer(),
synchronize_rcu() and call_rcu() primitives used are the same for all three
flavors. However for protection (on the reader side), the primitives used vary
depending on the flavor:

a.	rcu_read_lock() / rcu_read_unlock()
	rcu_dereference()

b.	rcu_read_lock_bh() / rcu_read_unlock_bh()
	local_bh_disable() / local_bh_enable()
	rcu_dereference_bh()

c.	rcu_read_lock_sched() / rcu_read_unlock_sched()
	preempt_disable() / preempt_enable()
	local_irq_save() / local_irq_restore()
	hardirq enter / hardirq exit
	NMI enter / NMI exit
	rcu_dereference_sched()

These three flavors are used as follows:

a.	RCU applied to normal data structures.

b.	RCU applied to networking data structures that may be subjected
	to remote denial-of-service attacks.

c.	RCU applied to scheduler and interrupt/NMI-handler tasks.

Again, most uses will be of (a).  The (b) and (c) cases are important
for specialized uses, but are relatively uncommon.  The SRCU, RCU-Tasks,
RCU-Tasks-Rude, and RCU-Tasks-Trace have similar relationships among
their assorted primitives.

.. _3_whatisRCU:

3.  WHAT ARE SOME EXAMPLE USES OF CORE RCU API?
-----------------------------------------------

This section shows a simple use of the core RCU API to protect a
global pointer to a dynamically allocated structure.  More-typical
uses of RCU may be found in listRCU.rst and NMI-RCU.rst.
::

	struct foo {
		int a;
		char b;
		long c;
	};
	DEFINE_SPINLOCK(foo_mutex);

	struct foo __rcu *gbl_foo;

	/*
	 * Create a new struct foo that is the same as the one currently
	 * pointed to by gbl_foo, except that field "a" is replaced
	 * with "new_a".  Points gbl_foo to the new structure, and
	 * frees up the old structure after a grace period.
	 *
	 * Uses rcu_assign_pointer() to ensure that concurrent readers
	 * see the initialized version of the new structure.
	 *
	 * Uses synchronize_rcu() to ensure that any readers that might
	 * have references to the old structure complete before freeing
	 * the old structure.
	 */
	void foo_update_a(int new_a)
	{
		struct foo *new_fp;
		struct foo *old_fp;

		new_fp = kmalloc(sizeof(*new_fp), GFP_KERNEL);
		spin_lock(&foo_mutex);
		old_fp = rcu_dereference_protected(gbl_foo, lockdep_is_held(&foo_mutex));
		*new_fp = *old_fp;
		new_fp->a = new_a;
		rcu_assign_pointer(gbl_foo, new_fp);
		spin_unlock(&foo_mutex);
		synchronize_rcu();
		kfree(old_fp);
	}

	/*
	 * Return the value of field "a" of the current gbl_foo
	 * structure.  Use rcu_read_lock() and rcu_read_unlock()
	 * to ensure that the structure does not get deleted out
	 * from under us, and use rcu_dereference() to ensure that
	 * we see the initialized version of the structure (important
	 * for DEC Alpha and for people reading the code).
	 */
	int foo_get_a(void)
	{
		int retval;

		rcu_read_lock();
		retval = rcu_dereference(gbl_foo)->a;
		rcu_read_unlock();
		return retval;
	}

So, to sum up:

-	Use rcu_read_lock() and rcu_read_unlock() to guard RCU
	read-side critical sections.

-	Within an RCU read-side critical section, use rcu_dereference()
	to dereference RCU-protected pointers.

-	Use some solid design (such as locks or semaphores) to
	keep concurrent updates from interfering with each other.

-	Use rcu_assign_pointer() to update an RCU-protected pointer.
	This primitive protects concurrent readers from the updater,
	**not** concurrent updates from each other!  You therefore still
	need to use locking (or something similar) to keep concurrent
	rcu_assign_pointer() primitives from interfering with each other.

-	Use synchronize_rcu() **after** removing a data element from an
	RCU-protected data structure, but **before** reclaiming/freeing
	the data element, in order to wait for the completion of all
	RCU read-side critical sections that might be referencing that
	data item.

See checklist.rst for additional rules to follow when using RCU.
And again, more-typical uses of RCU may be found in listRCU.rst
and NMI-RCU.rst.

.. _4_whatisRCU:

4.  WHAT IF MY UPDATING THREAD CANNOT BLOCK?
--------------------------------------------

In the example above, foo_update_a() blocks until a grace period elapses.
This is quite simple, but in some cases one cannot afford to wait so
long -- there might be other high-priority work to be done.

In such cases, one uses call_rcu() rather than synchronize_rcu().
The call_rcu() API is as follows::

	void call_rcu(struct rcu_head *head, rcu_callback_t func);

This function invokes func(head) after a grace period has elapsed.
This invocation might happen from either softirq or process context,
so the function is not permitted to block.  The foo struct needs to
have an rcu_head structure added, perhaps as follows::

	struct foo {
		int a;
		char b;
		long c;
		struct rcu_head rcu;
	};

The foo_update_a() function might then be written as follows::

	/*
	 * Create a new struct foo that is the same as the one currently
	 * pointed to by gbl_foo, except that field "a" is replaced
	 * with "new_a".  Points gbl_foo to the new structure, and
	 * frees up the old structure after a grace period.
	 *
	 * Uses rcu_assign_pointer() to ensure that concurrent readers
	 * see the initialized version of the new structure.
	 *
	 * Uses call_rcu() to ensure that any readers that might have
	 * references to the old structure complete before freeing the
	 * old structure.
	 */
	void foo_update_a(int new_a)
	{
		struct foo *new_fp;
		struct foo *old_fp;

		new_fp = kmalloc(sizeof(*new_fp), GFP_KERNEL);
		spin_lock(&foo_mutex);
		old_fp = rcu_dereference_protected(gbl_foo, lockdep_is_held(&foo_mutex));
		*new_fp = *old_fp;
		new_fp->a = new_a;
		rcu_assign_pointer(gbl_foo, new_fp);
		spin_unlock(&foo_mutex);
		call_rcu(&old_fp->rcu, foo_reclaim);
	}

The foo_reclaim() function might appear as follows::

	void foo_reclaim(struct rcu_head *rp)
	{
		struct foo *fp = container_of(rp, struct foo, rcu);

		foo_cleanup(fp->a);

		kfree(fp);
	}

The container_of() primitive is a macro that, given a pointer into a
struct, the type of the struct, and the pointed-to field within the
struct, returns a pointer to the beginning of the struct.

The use of call_rcu() permits the caller of foo_update_a() to
immediately regain control, without needing to worry further about the
old version of the newly updated element.  It also clearly shows the
RCU distinction between updater, namely foo_update_a(), and reclaimer,
namely foo_reclaim().

The summary of advice is the same as for the previous section, except
that we are now using call_rcu() rather than synchronize_rcu():

-	Use call_rcu() **after** removing a data element from an
	RCU-protected data structure in order to register a callback
	function that will be invoked after the completion of all RCU
	read-side critical sections that might be referencing that
	data item.

If the callback for call_rcu() is not doing anything more than calling
kfree() on the structure, you can use kfree_rcu() instead of call_rcu()
to avoid having to write your own callback::

	kfree_rcu(old_fp, rcu);

If the occasional sleep is permitted, the single-argument form may
be used, omitting the rcu_head structure from struct foo.

	kfree_rcu_mightsleep(old_fp);

This variant almost never blocks, but might do so by invoking
synchronize_rcu() in response to memory-allocation failure.

Again, see checklist.rst for additional rules governing the use of RCU.

.. _5_whatisRCU:

5.  WHAT ARE SOME SIMPLE IMPLEMENTATIONS OF RCU?
------------------------------------------------

One of the nice things about RCU is that it has extremely simple "toy"
implementations that are a good first step towards understanding the
production-quality implementations in the Linux kernel.  This section
presents two such "toy" implementations of RCU, one that is implemented
in terms of familiar locking primitives, and another that more closely
resembles "classic" RCU.  Both are way too simple for real-world use,
lacking both functionality and performance.  However, they are useful
in getting a feel for how RCU works.  See kernel/rcu/update.c for a
production-quality implementation, and see:

	https://docs.google.com/document/d/1X0lThx8OK0ZgLMqVoXiR4ZrGURHrXK6NyLRbeXe3Xac/edit

for papers describing the Linux kernel RCU implementation.  The OLS'01
and OLS'02 papers are a good introduction, and the dissertation provides
more details on the current implementation as of early 2004.


5A.  "TOY" IMPLEMENTATION #1: LOCKING
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
This section presents a "toy" RCU implementation that is based on
familiar locking primitives.  Its overhead makes it a non-starter for
real-life use, as does its lack of scalability.  It is also unsuitable
for realtime use, since it allows scheduling latency to "bleed" from
one read-side critical section to another.  It also assumes recursive
reader-writer locks:  If you try this with non-recursive locks, and
you allow nested rcu_read_lock() calls, you can deadlock.

However, it is probably the easiest implementation to relate to, so is
a good starting point.

It is extremely simple::

	static DEFINE_RWLOCK(rcu_gp_mutex);

	void rcu_read_lock(void)
	{
		read_lock(&rcu_gp_mutex);
	}

	void rcu_read_unlock(void)
	{
		read_unlock(&rcu_gp_mutex);
	}

	void synchronize_rcu(void)
	{
		write_lock(&rcu_gp_mutex);
		smp_mb__after_spinlock();
		write_unlock(&rcu_gp_mutex);
	}

[You can ignore rcu_assign_pointer() and rcu_dereference() without missing
much.  But here are simplified versions anyway.  And whatever you do,
don't forget about them when submitting patches making use of RCU!]::

	#define rcu_assign_pointer(p, v) \
	({ \
		smp_store_release(&(p), (v)); \
	})

	#define rcu_dereference(p) \
	({ \
		typeof(p) _________p1 = READ_ONCE(p); \
		(_________p1); \
	})


The rcu_read_lock() and rcu_read_unlock() primitive read-acquire
and release a global reader-writer lock.  The synchronize_rcu()
primitive write-acquires this same lock, then releases it.  This means
that once synchronize_rcu() exits, all RCU read-side critical sections
that were in progress before synchronize_rcu() was called are guaranteed
to have completed -- there is no way that synchronize_rcu() would have
been able to write-acquire the lock otherwise.  The smp_mb__after_spinlock()
promotes synchronize_rcu() to a full memory barrier in compliance with
the "Memory-Barrier Guarantees" listed in:

	Design/Requirements/Requirements.rst

It is possible to nest rcu_read_lock(), since reader-writer locks may
be recursively acquired.  Note also that rcu_read_lock() is immune
from deadlock (an important property of RCU).  The reason for this is
that the only thing that can block rcu_read_lock() is a synchronize_rcu().
But synchronize_rcu() does not acquire any locks while holding rcu_gp_mutex,
so there can be no deadlock cycle.

.. _quiz_1:

Quick Quiz #1:
		Why is this argument naive?  How could a deadlock
		occur when using this algorithm in a real-world Linux
		kernel?  How could this deadlock be avoided?

:ref:`Answers to Quick Quiz <9_whatisRCU>`

5B.  "TOY" EXAMPLE #2: CLASSIC RCU
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
This section presents a "toy" RCU implementation that is based on
"classic RCU".  It is also short on performance (but only for updates) and
on features such as hotplug CPU and the ability to run in CONFIG_PREEMPTION
kernels.  The definitions of rcu_dereference() and rcu_assign_pointer()
are the same as those shown in the preceding section, so they are omitted.
::

	void rcu_read_lock(void) { }

	void rcu_read_unlock(void) { }

	void synchronize_rcu(void)
	{
		int cpu;

		for_each_possible_cpu(cpu)
			run_on(cpu);
	}

Note that rcu_read_lock() and rcu_read_unlock() do absolutely nothing.
This is the great strength of classic RCU in a non-preemptive kernel:
read-side overhead is precisely zero, at least on non-Alpha CPUs.
And there is absolutely no way that rcu_read_lock() can possibly
participate in a deadlock cycle!

The implementation of synchronize_rcu() simply schedules itself on each
CPU in turn.  The run_on() primitive can be implemented straightforwardly
in terms of the sched_setaffinity() primitive.  Of course, a somewhat less
"toy" implementation would restore the affinity upon completion rather
than just leaving all tasks running on the last CPU, but when I said
"toy", I meant **toy**!

So how the heck is this supposed to work???

Remember that it is illegal to block while in an RCU read-side critical
section.  Therefore, if a given CPU executes a context switch, we know
that it must have completed all preceding RCU read-side critical sections.
Once **all** CPUs have executed a context switch, then **all** preceding
RCU read-side critical sections will have completed.

So, suppose that we remove a data item from its structure and then invoke
synchronize_rcu().  Once synchronize_rcu() returns, we are guaranteed
that there are no RCU read-side critical sections holding a reference
to that data item, so we can safely reclaim it.

.. _quiz_2:

Quick Quiz #2:
		Give an example where Classic RCU's read-side
		overhead is **negative**.

:ref:`Answers to Quick Quiz <9_whatisRCU>`

.. _quiz_3:

Quick Quiz #3:
		If it is illegal to block in an RCU read-side
		critical section, what the heck do you do in
		CONFIG_PREEMPT_RT, where normal spinlocks can block???

:ref:`Answers to Quick Quiz <9_whatisRCU>`

.. _6_whatisRCU:

6.  ANALOGY WITH READER-WRITER LOCKING
--------------------------------------

Although RCU can be used in many different ways, a very common use of
RCU is analogous to reader-writer locking.  The following unified
diff shows how closely related RCU and reader-writer locking can be.
::

	@@ -5,5 +5,5 @@ struct el {
	 	int data;
	 	/* Other data fields */
	 };
	-rwlock_t listmutex;
	+spinlock_t listmutex;
	 struct el head;

	@@ -13,15 +14,15 @@
		struct list_head *lp;
		struct el *p;

	-	read_lock(&listmutex);
	-	list_for_each_entry(p, head, lp) {
	+	rcu_read_lock();
	+	list_for_each_entry_rcu(p, head, lp) {
			if (p->key == key) {
				*result = p->data;
	-			read_unlock(&listmutex);
	+			rcu_read_unlock();
				return 1;
			}
		}
	-	read_unlock(&listmutex);
	+	rcu_read_unlock();
		return 0;
	 }

	@@ -29,15 +30,16 @@
	 {
		struct el *p;

	-	write_lock(&listmutex);
	+	spin_lock(&listmutex);
		list_for_each_entry(p, head, lp) {
			if (p->key == key) {
	-			list_del(&p->list);
	-			write_unlock(&listmutex);
	+			list_del_rcu(&p->list);
	+			spin_unlock(&listmutex);
	+			synchronize_rcu();
				kfree(p);
				return 1;
			}
		}
	-	write_unlock(&listmutex);
	+	spin_unlock(&listmutex);
		return 0;
	 }

Or, for those who prefer a side-by-side listing::

 1 struct el {                          1 struct el {
 2   struct list_head list;             2   struct list_head list;
 3   long key;                          3   long key;
 4   spinlock_t mutex;                  4   spinlock_t mutex;
 5   int data;                          5   int data;
 6   /* Other data fields */            6   /* Other data fields */
 7 };                                   7 };
 8 rwlock_t listmutex;                  8 spinlock_t listmutex;
 9 struct el head;                      9 struct el head;

::

  1 int search(long key, int *result)    1 int search(long key, int *result)
  2 {                                    2 {
  3   struct list_head *lp;              3   struct list_head *lp;
  4   struct el *p;                      4   struct el *p;
  5                                      5
  6   read_lock(&listmutex);             6   rcu_read_lock();
  7   list_for_each_entry(p, head, lp) { 7   list_for_each_entry_rcu(p, head, lp) {
  8     if (p->key == key) {             8     if (p->key == key) {
  9       *result = p->data;             9       *result = p->data;
 10       read_unlock(&listmutex);      10       rcu_read_unlock();
 11       return 1;                     11       return 1;
 12     }                               12     }
 13   }                                 13   }
 14   read_unlock(&listmutex);          14   rcu_read_unlock();
 15   return 0;                         15   return 0;
 16 }                                   16 }

::

  1 int delete(long key)                 1 int delete(long key)
  2 {                                    2 {
  3   struct el *p;                      3   struct el *p;
  4                                      4
  5   write_lock(&listmutex);            5   spin_lock(&listmutex);
  6   list_for_each_entry(p, head, lp) { 6   list_for_each_entry(p, head, lp) {
  7     if (p->key == key) {             7     if (p->key == key) {
  8       list_del(&p->list);            8       list_del_rcu(&p->list);
  9       write_unlock(&listmutex);      9       spin_unlock(&listmutex);
                                        10       synchronize_rcu();
 10       kfree(p);                     11       kfree(p);
 11       return 1;                     12       return 1;
 12     }                               13     }
 13   }                                 14   }
 14   write_unlock(&listmutex);         15   spin_unlock(&listmutex);
 15   return 0;                         16   return 0;
 16 }                                   17 }

Either way, the differences are quite small.  Read-side locking moves
to rcu_read_lock() and rcu_read_unlock, update-side locking moves from
a reader-writer lock to a simple spinlock, and a synchronize_rcu()
precedes the kfree().

However, there is one potential catch: the read-side and update-side
critical sections can now run concurrently.  In many cases, this will
not be a problem, but it is necessary to check carefully regardless.
For example, if multiple independent list updates must be seen as
a single atomic update, converting to RCU will require special care.

Also, the presence of synchronize_rcu() means that the RCU version of
delete() can now block.  If this is a problem, there is a callback-based
mechanism that never blocks, namely call_rcu() or kfree_rcu(), that can
be used in place of synchronize_rcu().

.. _7_whatisRCU:

7.  ANALOGY WITH REFERENCE COUNTING
-----------------------------------

The reader-writer analogy (illustrated by the previous section) is not
always the best way to think about using RCU.  Another helpful analogy
considers RCU an effective reference count on everything which is
protected by RCU.

A reference count typically does not prevent the referenced object's
values from changing, but does prevent changes to type -- particularly the
gross change of type that happens when that object's memory is freed and
re-allocated for some other purpose.  Once a type-safe reference to the
object is obtained, some other mechanism is needed to ensure consistent
access to the data in the object.  This could involve taking a spinlock,
but with RCU the typical approach is to perform reads with SMP-aware
operations such as smp_load_acquire(), to perform updates with atomic
read-modify-write operations, and to provide the necessary ordering.
RCU provides a number of support functions that embed the requi