linux Documentation

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

- Device operations.
 - Guarantees.

- Varieties of memory barrier.
 - What may not be assumed about memory barriers?
 - Address-dependency barriers (historical).
 - Control dependencies.
 - SMP barrier pairing.
 - Examples of memory barrier sequences.
 - Read memory barriers vs load speculation.
 - Multicopy atomicity.

- Compiler barrier.
 - CPU memory barriers.

- Lock acquisition functions.
 - Interrupt disabling functions.
 - Sleep and wake-up functions.
 - Miscellaneous functions.

- Acquires vs memory accesses.

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

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

- And then there's the Alpha.
 - Virtual Machine Guests.

- Circular buffers.

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

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

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

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

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 = READ_ONCE(P); D = READ_ONCE(*Q);

 the CPU will issue the following memory operations:

Q = LOAD P, D = LOAD *Q

 and always in that order.  However, on DEC Alpha, READ_ONCE() also
 emits a memory-barrier instruction, so that a DEC Alpha CPU will
 instead issue the following memory operations:

Q = LOAD P, MEMORY_BARRIER, D = LOAD *Q, MEMORY_BARRIER

 Whether on DEC Alpha or not, the READ_ONCE() also prevents compiler
 mischief.

a = READ_ONCE(*X); WRITE_ONCE(*X, b);

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

a = LOAD *X, STORE *X = b

 And for:

WRITE_ONCE(*X, c); d = READ_ONCE(*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; *(A + 4) = Y;

 we may get any of:

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

memory location
	either an object of scalar type, or a maximal sequence
	of adjacent bit-fields all having nonzero width

	NOTE 1: Two threads of execution can update and access
	separate memory locations without interfering with
	each other.

	NOTE 2: A bit-field and an adjacent non-bit-field member
	are in separate memory locations. The same applies
	to two bit-fields, if one is declared inside a nested
	structure declaration and the other is not, or if the two
	are separated by a zero-length bit-field declaration,
	or if they are separated by a non-bit-field member
	declaration. It is not safe to concurrently update two
	bit-fields in the same structure if all members declared
	between them are also bit-fields, no matter what the
	sizes of those intervening bit-fields happen to be.

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 _before_ all the stores after the write barrier.

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

An address-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), an address-dependency barrier would
 be required to make sure that the target of the second load is updated
 after the address obtained by the first load is accessed.

 An address-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.  An address-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 address-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 an _address_ 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 address-dependency barriers should normally be paired with
 write barriers; see the "SMP barrier pairing" subsection.

 [!] Kernel release v5.9 removed kernel APIs for explicit address-
 dependency barriers.  Nowadays, APIs for marking loads from shared
 variables such as READ_ONCE() and rcu_dereference() provide implicit
 address-dependency barriers.

A read barrier is an address-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 address-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 ACQUIRE operation will appear to happen after the
 ACQUIRE operation with respect to the other components of the system.
 ACQUIRE operations include LOCK operations and both smp_load_acquire()
 and smp_cond_load_acquire() operations.

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

 An ACQUIRE operation should almost always be paired with a RELEASE
 operation.

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

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

 The use of ACQUIRE and RELEASE operations generally precludes the need
 for other sorts of memory barrier.  In addition, a RELEASE+ACQUIRE pair is
 -not- guaranteed to act as a full memory barrier.  However, after an
 ACQUIRE on a given variable, all memory accesses preceding any prior
 RELEASE on that same variable are guaranteed to be visible.  In other
 words, within a given variable's critical section, all accesses of all
 previous critical sections for that variable are guaranteed to have
 completed.

 This means that ACQUIRE acts as a minimal "acquire" operation and
 RELEASE acts as a minimal "release" operation.

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

    Documentation/driver-api/pci/pci.rst
    Documentation/core-api/dma-api-howto.rst
    Documentation/core-api/dma-api.rst

CPU 1		      CPU 2
===============	      ===============
{ A == 1, B == 2, C == 3, P == &A, Q == &C }
B = 4;
<write barrier>
WRITE_ONCE(P, &B);
		      Q = READ_ONCE_OLD(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>
WRITE_ONCE(P, &B);
		      Q = READ_ONCE(P);
		      
		      D = *Q;

CPU 1		      CPU 2
===============	      ===============
{ A == 1, B == 2, C = 3, P == &A, Q == &C }
B = 4;
<write barrier>
WRITE_ONCE(P, &B);
		      Q = READ_ONCE_OLD(P);
		      WRITE_ONCE(*Q, 5);

(Q == &B) && (B == 4)

q = READ_ONCE(a);

if (q) {
	/* BUG: No address dependency!!! */
	p = READ_ONCE(b);
}

q = READ_ONCE(a);
if (q) {
	<read barrier>
	p = READ_ONCE(b);
}

q = READ_ONCE(a);
if (q) {
	WRITE_ONCE(b, 1);
}

q = a;
b = 1;  /* BUG: Compiler and CPU can both reorder!!! */

q = READ_ONCE(a);
if (q) {
	barrier();
	WRITE_ONCE(b, 1);
	do_something();
} else {
	barrier();
	WRITE_ONCE(b, 1);
	do_something_else();
}

q = READ_ONCE(a);
barrier();
WRITE_ONCE(b, 1);  /* BUG: No ordering vs. load from a!!! */
if (q) {
	/* WRITE_ONCE(b, 1); -- moved up, BUG!!! */
	do_something();
} else {
	/* WRITE_ONCE(b, 1); -- moved up, BUG!!! */
	do_something_else();
}

q = READ_ONCE(a);
if (q) {
	smp_store_release(&b, 1);
	do_something();
} else {
	smp_store_release(&b, 1);
	do_something_else();
}

q = READ_ONCE(a);
if (q) {
	WRITE_ONCE(b, 1);
	do_something();
} else {
	WRITE_ONCE(b, 2);
	do_something_else();
}

q = READ_ONCE(a);
if (q % MAX) {
	WRITE_ONCE(b, 1);
	do_something();
} else {
	WRITE_ONCE(b, 2);
	do_something_else();
}

q = READ_ONCE(a);
WRITE_ONCE(b, 2);
do_something_else();

q = READ_ONCE(a);
BUILD_BUG_ON(MAX <= 1); /* Order load from a with store to b. */
if (q % MAX) {
	WRITE_ONCE(b, 1);
	do_something();
} else {
	WRITE_ONCE(b, 2);
	do_something_else();
}

q = READ_ONCE(a);
if (q || 1 > 0)
	WRITE_ONCE(b, 1);

q = READ_ONCE(a);
WRITE_ONCE(b, 1);

q = READ_ONCE(a);
if (q) {
	WRITE_ONCE(b, 1);
} else {
	WRITE_ONCE(b, 2);
}
WRITE_ONCE(c, 1);  /* BUG: No ordering against the read from 'a'. */

ld r1,a
cmp r1,$0
cmov,ne r4,$1
cmov,eq r4,$2
st r4,b
st $1,c

CPU 1		      CPU 2
===============	      ===============
WRITE_ONCE(a, 1);
<write barrier>
WRITE_ONCE(b, 2);     x = READ_ONCE(b);
		      <read barrier>
		      y = READ_ONCE(a);

CPU 1		      CPU 2
===============	      ===============================
a = 1;
<write barrier>
WRITE_ONCE(b, &a);    x = READ_ONCE(b);
		      
		      y = *x;

CPU 1		      CPU 2
===============	      ===============================
r1 = READ_ONCE(y);
<general barrier>
WRITE_ONCE(x, 1);     if (r2 = READ_ONCE(x)) {
		         
		         WRITE_ONCE(y, 1);
		      }

assert(r1 == 0 || r2 == 0);

CPU 1                               CPU 2
===================                 ===================
WRITE_ONCE(a, 1);    }----   --->{  v = READ_ONCE(c);
WRITE_ONCE(b, 2);    }    \ /    {  w = READ_ONCE(d);
<write barrier>            \        <read barrier>
WRITE_ONCE(c, 3);    }    / \    {  x = READ_ONCE(a);
WRITE_ONCE(d, 4);    }----   --->{  y = READ_ONCE(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)
			<address-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 --->   \   aaaaaaaaaaaaaaaaa   |       |
  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		r1=LOAD X (reads 1)	LOAD Y (reads 1)
			<general barrier>	<read barrier>
			STORE Y=r1		LOAD X

CPU 1			CPU 2			CPU 3
=======================	=======================	=======================
	{ X = 0, Y = 0 }
STORE X=1		r1=LOAD X (reads 1)	LOAD Y (reads 1)
			<data dependency>	<read barrier>
			STORE Y=r1		LOAD X (reads 0)

int u, v, x, y, z;

void cpu0(void)
{
	r0 = smp_load_acquire(&x);
	WRITE_ONCE(u, 1);
	smp_store_release(&y, 1);
}

void cpu1(void)
{
	r1 = smp_load_acquire(&y);
	r4 = READ_ONCE(v);
	r5 = READ_ONCE(u);
	smp_store_release(&z, 1);
}

void cpu2(void)
{
	r2 = smp_load_acquire(&z);
	smp_store_release(&x, 1);
}

void cpu3(void)
{
	WRITE_ONCE(v, 1);
	smp_mb();
	r3 = READ_ONCE(u);
}

r0 == 1 && r1 == 1 && r2 == 1

r1 == 1 && r5 == 0

r0 == 0 && r1 == 1 && r2 == 1 && r3 == 0 && r4 == 0

r0 == 0 && r1 == 1 && r2 == 1 && r3 == 0 && r4 == 0 && r5 == 1

r0 == 0 && r1 == 0 && r2 == 0 && r5 == 0

barrier();

a[0] = x;
a[1] = x;

 Might result in an older value of x stored in a[1] than in a[0].
 Prevent both the compiler and the CPU from doing this as follows:

a[0] = READ_ONCE(x);
a[1] = READ_ONCE(x);

 In short, READ_ONCE() and WRITE_ONCE() provide cache coherence for
 accesses from multiple CPUs to a single variable.

while (tmp = a)
	do_something_with(tmp);

 into the following code, which, although in some sense legitimate
 for single-threaded code, is almost certainly not what the developer
 intended:

if (tmp = a)
	for (;;)
		do_something_with(tmp);

 Use READ_ONCE() to prevent the compiler from doing this to you:

while (tmp = READ_ONCE(a))
	do_something_with(tmp);

while (tmp = a)
	do_something_with(tmp);

 This could result in the following code, which is perfectly safe in
 single-threaded code, but can be fatal in concurrent code:

while (a)
	do_something_with(a);

 For example, the optimized version of this code could result in
 passing a zero to do_something_with() in the case where the variable
 a was modified by some other CPU between the "while" statement and
 the call to do_something_with().

 Again, use READ_ONCE() to prevent the compiler from doing this:

while (tmp = READ_ONCE(a))
	do_something_with(tmp);

 Note that if the compiler runs short of registers, it might save
 tmp onto the stack.  The overhead of this saving and later restoring
 is why compilers reload variables.  Doing so is perfectly safe for
 single-threaded code, so you need to tell the compiler about cases
 where it is not safe.

while (tmp = a)
	do_something_with(tmp);

 Into this:

do { } while (0);

 This transformation is a win for single-threaded code because it
 gets rid of a load and a branch.  The problem is that the compiler
 will carry out its proof assuming that the current CPU is the only
 one updating variable 'a'.  If variable 'a' is shared, then the
 compiler's proof will be erroneous.  Use READ_ONCE() to tell the
 compiler that it doesn't know as much as it thinks it does:

while (tmp = READ_ONCE(a))
	do_something_with(tmp);

 But please note that the compiler is also closely watching what you
 do with the value after the READ_ONCE().  For example, suppose you
 do the following and MAX is a preprocessor macro with the value 1:

while ((tmp = READ_ONCE(a)) % MAX)
	do_something_with(tmp);

 Then the compiler knows that the result of the "%" operator applied
 to MAX will always be zero, again allowing the compiler to optimize
 the code into near-nonexistence.  (It will still load from the
 variable 'a'.)

a = 0;
... Code that does not store to variable a ...
a = 0;

 The compiler sees that the value of variable 'a' is already zero, so
 it might well omit the second store.  This would come as a fatal
 surprise if some other CPU might have stored to variable 'a' in the
 meantime.

 Use WRITE_ONCE() to prevent the compiler from making this sort of
 wrong guess:

WRITE_ONCE(a, 0);
... Code that does not store to variable a ...
WRITE_ONCE(a, 0);

void process_level(void)
{
	msg = get_message();
	flag = true;
}

void interrupt_handler(void)
{
	if (flag)
		process_message(msg);
}

 There is nothing to prevent the compiler from transforming
 process_level() to the following, in fact, this might well be a
 win for single-threaded code:

void process_level(void)
{
	flag = true;
	msg = get_message();
}

 If the interrupt occurs between these two statement, then
 interrupt_handler() might be passed a garbled msg.  Use WRITE_ONCE()
 to prevent this as follows:

void process_level(void)
{
	WRITE_ONCE(msg, get_message());
	WRITE_ONCE(flag, true);
}

void interrupt_handler(void)
{
	if (READ_ONCE(flag))
		process_message(READ_ONCE(msg));
}

 Note that the READ_ONCE() and WRITE_ONCE() wrappers in
 interrupt_handler() are needed if this interrupt handler can itself
 be interrupted by something that also accesses 'flag' and 'msg',
 for example, a nested interrupt or an NMI.  Otherwise, READ_ONCE()
 and WRITE_ONCE() are not needed in interrupt_handler() other than
 for documentation purposes.  (Note also that nested interrupts
 do not typically occur in modern Linux kernels, in fact, if an
 interrupt handler returns with interrupts enabled, you will get a
 WARN_ONCE() splat.)

 You should assume that the compiler can move READ_ONCE() and
 WRITE_ONCE() past code not containing READ_ONCE(), WRITE_ONCE(),
 barrier(), or similar primitives.

 This effect could also be achieved using barrier(), but READ_ONCE()
 and WRITE_ONCE() are more selective:  With READ_ONCE() and
 WRITE_ONCE(), the compiler need only forget the contents of the
 indicated memory locations, while with barrier() the compiler must
 discard the value of all memory locations that it has currently
 cached in any machine registers.  Of course, the compiler must also
 respect the order in which the READ_ONCE()s and WRITE_ONCE()s occur,
 though the CPU of course need not do so.

if (a)
	b = a;
else
	b = 42;

 The compiler might save a branch by optimizing this as follows:

b = 42;
if (a)
	b = a;

 In single-threaded code, this is not only safe, but also saves
 a branch.  Unfortunately, in concurrent code, this optimization
 could cause some other CPU to see a spurious value of 42 -- even
 if variable 'a' was never zero -- when loading variable 'b'.
 Use WRITE_ONCE() to prevent this as follows:

if (a)
	WRITE_ONCE(b, a);
else
	WRITE_ONCE(b, 42);

 The compiler can also invent loads.  These are usually less
 damaging, but they can result in cache-line bouncing and thus in
 poor performance and scalability.  Use READ_ONCE() to prevent
 invented loads.

p = 0x00010002;

 Please note that GCC really does use this sort of optimization,
 which is not surprising given that it would likely take more
 than two instructions to build the constant and then store it.
 This optimization can therefore be a win in single-threaded code.
 In fact, a recent bug (since fixed) caused GCC to incorrectly use
 this optimization in a volatile store.  In the absence of such bugs,
 use of WRITE_ONCE() prevents store tearing in the following example:

WRITE_ONCE(p, 0x00010002);

 Use of packed structures can also result in load and store tearing,
 as in this example:

struct __attribute__((__packed__)) foo {
	short a;
	int b;
	short c;
};
struct foo foo1, foo2;
...

foo2.a = foo1.a;
foo2.b = foo1.b;
foo2.c = foo1.c;

 Because there are no READ_ONCE() or WRITE_ONCE() wrappers and no
 volatile markings, the compiler would be well within its rights to
 implement these three assignment statements as a pair of 32-bit
 loads followed by a pair of 32-bit stores.  This would result in
 load tearing on 'foo1.b' and store tearing on 'foo2.b'.  READ_ONCE()
 and WRITE_ONCE() again prevent tearing in this example:

foo2.a = foo1.a;
WRITE_ONCE(foo2.b, READ_ONCE(foo1.b));
foo2.c = foo1.c;

TYPE			MANDATORY	SMP CONDITIONAL
=======================	===============	===============
GENERAL			mb()		smp_mb()
WRITE			wmb()		smp_wmb()
READ			rmb()		smp_rmb()
ADDRESS DEPENDENCY			READ_ONCE()

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

These are for use with atomic RMW functions that do not imply memory
 barriers, but where the code needs a memory barrier. Examples for atomic
 RMW functions that do not imply a memory barrier are e.g. add,
 subtract, (failed) conditional operations, _relaxed functions,
 but not atomic_read or atomic_set. A common example where a memory
 barrier may be required is when atomic ops are used for reference
 counting.

 These are also used for atomic RMW bitop functions that do not imply a
 memory barrier (such as set_bit and clear_bit).

 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();
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_{t,bitops}.txt for more information.

These are for use with consistent memory to guarantee the ordering
 of writes or reads of shared memory accessible to both the CPU and a
 DMA capable device. See Documentation/core-api/dma-api.rst file for more
 information about consistent memory.

 For example, consider a device driver that shares memory with a device
 and uses a descriptor status value to indicate if the descriptor belongs
 to the device or the CPU, and a doorbell to notify it when new
 descriptors are available:

if (desc->status != DEVICE_OWN) {
	/* do not read data until we own descriptor */
	dma_rmb();

	/* read/modify data */
	read_data = desc->data;
	desc->data = write_data;

	/* flush modifications before status update */
	dma_wmb();

	/* assign ownership */
	desc->status = DEVICE_OWN;

	/* Make descriptor status visible to the device followed by
	 * notify device of new descriptor
	 */
	writel(DESC_NOTIFY, doorbell);
}

 The dma_rmb() allows us to guarantee that the device has released ownership
 before we read the data from the descriptor, and the dma_wmb() allows
 us to guarantee the data is written to the descriptor before the device
 can see it now has ownership.  The dma_mb() implies both a dma_rmb() and
 a dma_wmb().

 Note that the dma_*() barriers do not provide any ordering guarantees for
 accesses to MMIO regions.  See the later "KERNEL I/O BARRIER EFFECTS"
 subsection for more information about I/O accessors and MMIO ordering.

This is for use with persistent memory to ensure that stores for which
 modifications are written to persistent storage reached a platform
 durability domain.

 For example, after a non-temporal write to pmem region, we use pmem_wmb()
 to ensure that stores have reached a platform durability domain. This ensures
 that stores have updated persistent storage before any data access or
 data transfer caused by subsequent instructions is initiated. This is
 in addition to the ordering done by wmb().

 For load from persistent memory, existing read memory barriers are sufficient
 to ensure read ordering.

For memory accesses with write-combining attributes (e.g. those returned
 by ioremap_wc()), the CPU may wait for prior accesses to be merged with
 subsequent ones. io_stop_wc() can be used to prevent the merging of
 write-combining memory accesses before this macro with those after it when
 such wait has performance implications.

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

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

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

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

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

All ACQUIRE operations issued before a RELEASE operation will be
 completed before the RELEASE operation.

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

*A = a;
ACQUIRE M
RELEASE M
*B = b;

ACQUIRE M, STORE *B, STORE *A, RELEASE M

*A = a;
RELEASE M
ACQUIRE N
*B = b;

ACQUIRE N, STORE *B, STORE *A, RELEASE M

Why does this work?

One key point is that we are only talking about the CPU doing
the reordering, not the compiler.  If the compiler (or, for
that matter, the developer) switched the operations, deadlock
-could- occur.

But suppose the CPU reordered the operations.  In this case,
the unlock precedes the lock in the assembly code.  The CPU
simply elected to try executing the later lock operation first.
If there is a deadlock, this lock operation will simply spin (or
try to sleep, but more on that later).	The CPU will eventually
execute the unlock operation (which preceded the lock operation
in the assembly code), which will unravel the potential deadlock,
allowing the lock operation to succeed.

But what if the lock is a sleeplock?  In that case, the code will
try to enter the scheduler, where it will eventually encounter
a memory barrier, which will force the earlier unlock operation
to complete, again unraveling the deadlock.  There might be
a sleep-unlock race, but the locking primitive needs to resolve
such races properly in any case.

*A = a;
*B = b;
ACQUIRE
*C = c;
*D = d;
RELEASE
*E = e;
*F = f;

ACQUIRE, {*F,*A}, *E, {*C,*D}, *B, RELEASE

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

{*F,*A}, *B,	ACQUIRE, *C, *D,	RELEASE, *E
*A, *B, *C,	ACQUIRE, *D,		RELEASE, *E, *F
*A, *B,		ACQUIRE, *C,		RELEASE, *D, *E, *F
*B,		ACQUIRE, *C, *D,	RELEASE, {*F,*A}, *E

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

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

prepare_to_wait();
prepare_to_wait_exclusive();

wait_event();
wait_event_cmd();
wait_event_exclusive_cmd();
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 (Sleeper)			CPU 2 (Waker)
===============================	===============================
set_current_state();		STORE event_indicated
  smp_store_mb();		wake_up();
    STORE current->state	  ...
    <general barrier>		  <general barrier>
LOAD event_indicated		  if ((LOAD task->state) & TASK_NORMAL)
				    STORE task->state

CPU 1				CPU 2
===============================	===============================
X = 1;				Y = 1;
smp_mb();			wake_up();
LOAD Y				LOAD X

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
===============================	===============================
WRITE_ONCE(*A, a);		WRITE_ONCE(*E, e);
ACQUIRE M			ACQUIRE Q
WRITE_ONCE(*B, b);		WRITE_ONCE(*F, f);
WRITE_ONCE(*C, c);		WRITE_ONCE(*G, g);
RELEASE M			RELEASE Q
WRITE_ONCE(*D, d);		WRITE_ONCE(*H, h);

*E, ACQUIRE M, ACQUIRE Q, *G, *C, *F, *A, *B, RELEASE Q, *D, *H, RELEASE M

*B, *C or *D preceding ACQUIRE M
*A, *B or *C following RELEASE M
*F, *G or *H preceding ACQUIRE Q
*E, *F or *G following RELEASE 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

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

The readX() and writeX() MMIO accessors take a pointer to the
peripheral being accessed as an __iomem * parameter. For pointers
mapped with the default I/O attributes (e.g. those returned by
ioremap()), the ordering guarantees are as follows:

1. All readX() and writeX() accesses to the same peripheral are ordered
   with respect to each other. This ensures that MMIO register accesses
   by the same CPU thread to a particular device will arrive in program
   order.

2. A writeX() issued by a CPU thread holding a spinlock is ordered
   before a writeX() to the same peripheral from another CPU thread
   issued after a later acquisition of the same spinlock. This ensures
   that MMIO register writes to a particular device issued while holding
   a spinlock will arrive in an order consistent with acquisitions of
   the lock.

3. A writeX() by a CPU thread to the peripheral will first wait for the
   completion of all prior writes to memory either issued by, or
   propagated to, the same thread. This ensures that writes by the CPU
   to an outbound DMA buffer allocated by dma_alloc_coherent() will be
   visible to a DMA engine when the CPU writes to its MMIO control
   register to trigger the transfer.

4. A readX() by a CPU thread from the peripheral will complete before
   any subsequent reads from memory by the same thread can begin. This
   ensures that reads by the CPU from an incoming DMA buffer allocated
   by dma_alloc_coherent() will not see stale data after reading from
   the DMA engine's MMIO status register to establish that the DMA
   transfer has completed.

5. A readX() by a CPU thread from the peripheral will complete before
   any subsequent delay() loop can begin execution on the same thread.
   This ensures that two MMIO register writes by the CPU to a peripheral
   will arrive at least 1us apart if the first write is immediately read
   back with readX() and udelay(1) is called prior to the second
   writeX():

	writel(42, DEVICE_REGISTER_0); // Arrives at the device...
	readl(DEVICE_REGISTER_0);
	udelay(1);
	writel(42, DEVICE_REGISTER_1); // ...at least 1us before this.

The ordering properties of __iomem pointers obtained with non-default
attributes (e.g. those returned by ioremap_wc()) are specific to the
underlying architecture and therefore the guarantees listed above cannot
generally be relied upon for accesses to these types of mappings.

These are similar to readX() and writeX(), but provide weaker memory
ordering guarantees. Specifically, they do not guarantee ordering with
respect to locking, normal memory accesses or delay() loops (i.e.
bullets 2-5 above) but they are still guaranteed to be ordered with
respect to other accesses from the same CPU thread to the same
peripheral when operating on __iomem pointers mapped with the default
I/O attributes.

The readsX() and writesX() MMIO accessors are designed for accessing
register-based, memory-mapped FIFOs residing on peripherals that are not
capable of performing DMA. Consequently, they provide only the ordering
guarantees of readX_relaxed() and writeX_relaxed(), as documented above.

The inX() and outX() accessors are intended to access legacy port-mapped
I/O peripherals, which may require special instructions on some
architectures (notably x86). The port number of the peripheral being
accessed is passed as an argument.

Since many CPU architectures ultimately access these peripherals via an
internal virtual memory mapping, the portable ordering guarantees
provided by inX() and outX() are the same as those provided by readX()
and writeX() respectively when accessing a mapping with the default I/O
attributes.

Device drivers may expect outX() to emit a non-posted write transaction
that waits for a completion response from the I/O peripheral before
returning. This is not guaranteed by all architectures and is therefore
not part of the portable ordering semantics.

As above, the insX() and outsX() accessors provide the same ordering
guarantees as readsX() and writesX() respectively when accessing a
mapping with the default I/O attributes.

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  |  :   |        |    |           |    |        |
|        |    |        |  :   |        |    |           |    +--------+
+--------+    +--------+  :   +--------+    +-----------+
                          :
                          :

a = READ_ONCE(*A);
WRITE_ONCE(*B, b);
c = READ_ONCE(*C);
d = READ_ONCE(*D);
WRITE_ONCE(*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 = READ_ONCE(*A);
WRITE_ONCE(*A, V);
WRITE_ONCE(*A, W);
X = READ_ONCE(*A);
WRITE_ONCE(*A, Y);
Z = READ_ONCE(*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/core-api/circular-buffers.rst

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
Signaled 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 typically need to call pci_restore_state() after reset to
re-initialize the device's config space registers and thereby
bring it from D0\ :sub:`uninitialized` into D0\ :sub:`active` state
(PCIe r7.0 sec 5.3.1.1).  The PCI core invokes pci_save_state()
on enumeration after initializing config space to ensure that a
saved state is available for subsequent error recovery.
Drivers which modify config space on probe may need to invoke
pci_save_state() afterwards to record those changes for later
error recovery.  When going into system suspend, pci_save_state()
is called for every PCI device and that state will be restored
not only on resume, but also on any subsequent error recovery.
In the unlikely event that the saved state recorded on suspend
is unsuitable for error recovery, drivers should call
pci_save_state() on resume.

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

   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 choose 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.

The 'TLP Header' is the prefix/header of the TLP that caused the error
in raw hex format. To decode the TLP Header into human-readable form
one may use tlp-tool:

https://github.com/mmpg-x86/tlp-tool

Example usage::

  curl -L https://git.kernel.org/linus/2ca1c94ce0b6 | rtlp-tool --aer

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, u16 *tag);

The `type` argument is used to specify the memory type, either volatile
or persistent, of the target memory. The `cpu` 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 Fscking 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/.  For others, browsers
and search engines will usually find what you are looking for.

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 1987, Rashid et al. described lazy TLB-flush [RichardRashid87a].
At first glance, this has nothing to do with RCU, but nevertheless
this paper helped inspire the update-side batching used in the later
RCU implementation in DYNIX/ptx.  In 1988, Barbara Liskov published
a description of Argus that noted that use of out-of-date values can
be tolerated in some situations.  Thus, this paper provides some early
theoretical justification for use of stale data.

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
today.

At about this same time, Andrews [Andrews91textbook] 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 [HMassalinPhD].  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 is quite similar to RCU [Gamsa99].  These operating
systems made pervasive use of RCU in place of "existence locks", which
greatly simplifies locking hierarchies and helps avoid deadlocks.

The year 2000 saw an email exchange that would likely have
led to yet another independent invention of something like RCU
[RustyRussell2000a,RustyRussell2000b].  Instead, 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).  The corresponding journal article appeared
in 2004 [MagedMichael04a].  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.  The key advantage
of inside-out reference counts is that they can be stored in immortal
variables, thus allowing races between access and deletion to be avoided.

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] (following up on a suggestion by
Hugh Dickins [Dickins02a] and an implementation by Mingming Cao
[MingmingCao2002IPCRCU]), 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 resizable RCU-protected hash tables may now be on a path
to a solution [JoshTriplett2009RPHash].  A few academic researchers are now
using RCU to solve their parallel problems [HariKannan2009DynamicAnalysisRCU].

2010 produced a simpler preemptible-RCU implementation
based on TREE_RCU [PaulEMcKenney2010SimpleOptRCU], lockdep-RCU
[PaulEMcKenney2010LockdepRCU], another resizable RCU-protected hash
table [HerbertXu2010RCUResizeHash] (this one consuming more memory,
but allowing arbitrary changes in hash function, as required for DoS
avoidance in the networking code), realization of the 2009 RCU-protected
hash table with atomic node move [JoshTriplett2010RPHash], an update on
the RCU API [PaulEMcKenney2010RCUAPI].

2011 marked the inclusion of Nick Piggin's fully lockless dentry search
[LinusTorvalds2011Linux2:6:38:rc1:NPigginVFS], an RCU-protected red-black
tree using software transactional memory to protect concurrent updates
(strange, but true!) [PhilHoward2011RCUTMRBTree], yet another variant of
RCU-protected resizable hash tables [Triplett:2011:RPHash], the 3.0 RCU
trainwreck [PaulEMcKenney2011RCU3.0trainwreck], and Neil Brown's "Meet the
Lockers" LWN article [NeilBrown2011MeetTheLockers].  Some academic
work looked at debugging uses of RCU [Seyster:2011:RFA:2075416.2075425].

In 2012, Josh Triplett received his Ph.D. with his dissertation
covering RCU-protected resizable hash tables and the relationship
between memory barriers and read-side traversal order:  If the updater
is making changes in the opposite direction from the read-side traversal
order, the updater need only execute a memory-barrier instruction,
but if in the same direction, the updater needs to wait for a grace
period between the individual updates [JoshTriplettPhD].  Also in 2012,
after seventeen years of attempts, an RCU paper made it into a top-flight
academic journal, IEEE Transactions on Parallel and Distributed Systems
[MathieuDesnoyers2012URCU].  A group of researchers in Spain applied
user-level RCU to crowd simulation [GuillermoVigueras2012RCUCrowd], and
another group of researchers in Europe produced a formal description of
RCU based on separation logic [AlexeyGotsman2012VerifyGraceExtended],
which was published in the 2013 European Symposium on Programming
[AlexeyGotsman2013ESOPRCU].



Bibtex Entries

@article{Kung80
,author="H. T. Kung and Q. Lehman"
,title="Concurrent Manipulation of Binary Search Trees"
,Year="1980"
,Month="September"
,journal="ACM Transactions on Database Systems"
,volume="5"
,number="3"
,pages="354-382"
,annotation={
	Use garbage collector to clean up data after everyone is done with it.
	.
	Oldest use of something vaguely resembling RCU that I have found.
	http://portal.acm.org/citation.cfm?id=320619&dl=GUIDE,
	[Viewed December 3, 2007]
}
}

@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"
,annotation={
	.
	Superseded by Manber84.
	.
	Describes concurrent AVL tree implementation.  Uses a
	garbage-collection mechanism to handle concurrent use and deletion
	of nodes in the tree, but lacks the summary-of-execution-history
	concept of read-copy locking.
	.
	Keeps full list of processes that were active when a given
	node was to be deleted, and waits until all such processes have
	-terminated- before allowing this node to be reused.  This is
	not described in great detail -- one could imagine using process
	IDs for this if the ID space was large enough that overlapping
	never occurred.
	.
	This restriction makes this algorithm unsuitable for use in
	systems comprised of long-lived processes.  It also produces
	completely unacceptable overhead in systems with large numbers
	of processes.  Finally, it is specific to AVL trees.
	.
	Cites Kung80, so not an independent invention, but the first
	RCU-like usage that does not rely on an automatic garbage
	collector.
}
}

@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"
,annotation={
	Describes concurrent AVL tree implementation.  Uses a
	garbage-collection mechanism to handle concurrent use and deletion
	of nodes in the tree, but lacks the summary-of-execution-history
	concept of read-copy locking.
	.
	Keeps full list of processes that were active when a given
	node was to be deleted, and waits until all such processes have
	-terminated- before allowing this node to be reused.  This is
	not described in great detail -- one could imagine using process
	IDs for this if the ID space was large enough that overlapping
	never occurred.
	.
	This restriction makes this algorithm unsuitable for use in
	systems comprised of long-lived processes.  It also produces
	completely unacceptable overhead in systems with large numbers
	of processes.  Finally, it is specific to AVL trees.
}
}

@Conference{RichardRashid87a
,Author="Richard Rashid and Avadis Tevanian and Michael Young and
David Golub and Robert Baron and David Black and William Bolosky and
Jonathan Chew"
,Title="Machine-Independent Virtual Memory Management for Paged
Uniprocessor and Multiprocessor Architectures"
,Booktitle="{2\textsuperscript{nd} Symposium on Architectural Support
for Programming Languages and Operating Systems}"
,Publisher="Association for Computing Machinery"
,Month="October"
,Year="1987"
,pages="31-39"
,Address="Palo Alto, CA"
,note="Available:
\url{http://www.cse.ucsc.edu/~randal/221/rashid-machvm.pdf}
[Viewed February 17, 2005]"
,annotation={
	Describes lazy TLB flush, where one waits for each CPU to pass
	through a scheduling-clock interrupt before reusing a given range
	of virtual address.  Does not describe how one determines that
	all CPUs have in fact taken such an interrupt, though there are
	no shortage of straightforward methods for accomplishing this.
	.
	Note that it does not make sense to just wait a fixed amount of
	time, since a given CPU might have interrupts disabled for an
	extended amount of time.
}
}

@article{BarbaraLiskov1988ArgusCACM
,author = {Barbara Liskov}
,title = {Distributed programming in {Argus}}
,journal = {Commun. ACM}
,volume = {31}
,number = {3}
,year = {1988}
,issn = {0001-0782}
,pages = {300--312}
,doi = {http://doi.acm.org/10.1145/42392.42399}
,publisher = {ACM}
,address = {New York, NY, USA}
,annotation={
	At the top of page 307: "Conflicts with deposits and withdrawals
	are necessary if the reported total is to be up to date.  They
	could be avoided by having total return a sum that is slightly
	out of date."  Relies on semantics -- approximate numerical
	values sometimes OK.
}
}

@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"
,annotation={
	Concurrent access to skip lists.  Has both weak and strong search.
	Uses concept of ``garbage queue'', but has no real way of cleaning
	the garbage efficiently.
	.
	Appears to be an independent invention of an RCU-like mechanism.
}
}

# Was Adams91, see also syncrefs.bib.
@Book{Andrews91textbook
,Author="Gregory R. Andrews"
,title="Concurrent Programming, Principles, and Practices"
,Publisher="Benjamin Cummins"
,Year="1991"
,annotation={
	Has a few paragraphs describing ``chaotic relaxation'', a
	numerical analysis technique that allows multiprocessors to
	avoid synchronization overhead by using possibly-stale data.
	.
	Seems like this is descended from yet another independent
	invention of RCU-like function -- but this is restricted
	in that reclamation is not necessary.
}
}

@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.  See page 90
		(PDF page 106), Section 5.4, fourth bullet point.
}
}

@unpublished{Jacobson93
,author="Van Jacobson"
,title="Avoid Read-Side Locking Via Delayed Free"
,year="1993"
,month="September"
,note="private communication"
,annotation={
	Use fixed time delay to approximate grace period.  Very simple,
	but subject to random memory corruption under heavy load.
	.
	Independent invention of RCU-like mechanism.
}
}

@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"
,note="Available:
\url{https://www.usenix.org/publications/library/proceedings/neworl/full_papers/john.a}
[Viewed October 1, 2010]"
,annotation={
	Age vnodes out of the cache, and have a fixed time set by a kernel
	parameter.  Not clear that all races were in fact correctly handled.
	Used a 20-minute time by default, which would most definitely not
	be suitable during DoS attacks or virus scans.
	.
	Apparently independent invention of RCU-like mechanism.
}
}

@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"
,month="August"
,annotation={
	Describes the parallel RCU infrastructure.  Includes NUMA aspect
	(structure of bitmap can reflect bus structure of computer system).
	.
	Another independent invention of an RCU-like mechanism, but the
	"real" RCU this time!
}
}

@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"
,month="March"
,pages="19"
,annotation={
	Describes use of RCU to synchronize data between a pair of
	SMP/NUMA computer systems.
}
}

@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"
,month="March"
,annotation={
	Describes doing an atomic update by copying the data item and
	then substituting it into the data structure.
}
}

@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"
,annotation={
	Describes and analyzes RCU mechanism in DYNIX/ptx.  Describes
	application to linked list update and log-buffer flushing.
	Defines 'quiescent state'.  Includes both measured and analytic
	evaluation.
	http://www.rdrop.com/users/paulmck/RCU/rclockpdcsproof.pdf
	[Viewed December 3, 2007]
}
}

@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"
,annotation={
	Use of RCU-like facility in K42/Tornado.  Another independent
	invention of RCU.
	See especially pages 7-9 (Section 5).
	http://www.usenix.org/events/osdi99/full_papers/gamsa/gamsa.pdf
	[Viewed August 30, 2006]
}
}

@unpublished{RustyRussell2000a
,Author="Rusty Russell"
,Title="Re: modular net drivers"
,month="June"
,year="2000"
,day="23"
,note="Available:
\url{http://oss.sgi.com/projects/netdev/archive/2000-06/msg00250.html}
[Viewed April 10, 2006]"
,annotation={
	Proto-RCU proposal from Phil Rumpf and Rusty Russell.
	Yet another independent invention of RCU.
	Outline of algorithm to unload modules...
	.
	Appeared on net-dev mailing list.
}
}

@unpublished{RustyRussell2000b
,Author="Rusty Russell"
,Title="Re: modular net drivers"
,month="June"
,year="2000"
,day="24"
,note="Available:
\url{http://oss.sgi.com/projects/netdev/archive/2000-06/msg00254.html}
[Viewed April 10, 2006]"
,annotation={
	Proto-RCU proposal from Phil Rumpf and Rusty Russell.
	.
	Appeared on net-dev mailing list.
}
}

@unpublished{McKenney01b
,Author="Paul E. McKenney and Dipankar Sarma"
,Title="Read-Copy Update Mutual Exclusion in {Linux}"
,month="February"
,year="2001"
,note="Available:
\url{http://lse.sourceforge.net/locking/rcu/rcupdate_doc.html}
[Viewed October 18, 2004]"
,annotation={
	Prototypical Linux documentation for RCU.
}
}

@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 6,219,690"
,month="April"
,annotation={
	'Change in mode' aspect of RCU.  Can be thought of as a lazy barrier.
}
}

@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{https://kernel.org/doc/ols/2001/read-copy.pdf}
\url{http://www.rdrop.com/users/paulmck/RCU/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.
}
}

@unpublished{McKenney01f
,Author="Paul E. McKenney"
,Title="{RFC:} patch to allow lock-free traversal of lists with insertion"
,month="October"
,year="2001"
,note="Available:
\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=100259266316456&w=2}
[Viewed June 23, 2004]"
,annotation={
	Memory-barrier and Alpha thread.  100 messages, not too bad...
}
}

@unpublished{Spraul01
,Author="Manfred Spraul"
,Title="Re: {RFC:} patch to allow lock-free traversal of lists with insertion"
,month="October"
,year="2001"
,note="Available:
\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=100264675012867&w=2}
[Viewed June 23, 2004]"
,annotation={
	Suggested burying memory barriers in Linux's list-manipulation
	primitives.
}
}

@unpublished{LinusTorvalds2001a
,Author="Linus Torvalds"
,Title="{Re:} {[Lse-tech]} {Re:} {RFC:} patch to allow lock-free traversal of lists with insertion"
,month="October"
,year="2001"
,note="Available:
\url{https://lore.kernel.org/r/[email protected]}
[Viewed August 21, 2004]"
,annotation={
}
}

@unpublished{Blanchard02a
,Author="Anton Blanchard"
,Title="some RCU dcache and ratcache results"
,month="March"
,year="2002"
,note="Available:
\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=101637107412972&w=2}
[Viewed October 18, 2004]"
}

@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...
}
}

@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"
,annotation={
	Measured scalability of Linux 2.4 kernel's directory-entry cache
	(dcache), and measured some scalability enhancements.
}
}

@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]"
,annotation={
	Presented and compared a number of RCU implementations for the
	Linux kernel.
}
}

@unpublished{Sarma02a
,Author="Dipankar Sarma"
,Title="specweb99: dcache scalability results"
,month="July"
,year="2002"
,note="Available:
\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=102645767914212&w=2}
[Viewed June 23, 2004]"
,annotation={
	Compare fastwalk and RCU for dcache.  RCU won.
}
}

@unpublished{Barbieri02
,Author="Luca Barbieri"
,Title="Re: {[PATCH]} Initial support for struct {vfs\_cred}"
,month="August"
,year="2002"
,note="Available:
\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=103082050621241&w=2}
[Viewed: June 23, 2004]"
,annotation={
	Suggested RCU for vfs\_shared\_cred.
}
}

@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.
}
}

@unpublished{Dickins02a
,author="Hugh Dickins"
,title="Use RCU for System-V IPC"
,year="2002"
,month="October"
,note="private communication"
}

@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"
}

@unpublished{Sarma02b
,Author="Dipankar Sarma"
,Title="Some dcache\_rcu benchmark numbers"
,month="October"
,year="2002"
,note="Available:
\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=103462075416638&w=2}
[Viewed June 23, 2004]"
,annotation={
	Performance of dcache RCU on kernbench for 16x NUMA-Q and 1x,
	2x, and 4x systems.  RCU does no harm, and helps on 16x.
}
}

@unpublished{MingmingCao2002IPCRCU
,Author="Mingming Cao"
,Title="[PATCH]updated ipc lock patch"
,month="October"
,year="2002"
,note="Available:
\url{https://lore.kernel.org/r/[email protected]}
[Viewed February 15, 2014]"
,annotation={
	Mingming Cao's patch to introduce RCU to SysV IPC.
}
}

@unpublished{LinusTorvalds2003a
,Author="Linus Torvalds"
,Title="Re: {[PATCH]} small fixes in brlock.h"
,month="March"
,year="2003"
,note="Available:
\url{https://lore.kernel.org/r/[email protected]}
[Viewed March 13, 2006]"
,annotation={
	Linus suggests replacing brlock with RCU and/or seqlocks:
	.
	'It's entirely possible that the current user could be replaced
	by RCU and/or seqlocks, and we could get rid of brlocks entirely.'
	.
	Stephen Hemminger responds by replacing them with RCU.
}
}

@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"
,annotation={
	Use of RCU to enable hot-swapping for autonomic behavior in K42.
}
}

@unpublished{Seigh03
,author="Joseph W. {Seigh II}"
,title="Read Copy Update"
,Year="2003"
,Month="March"
,note="email correspondence"
,annotation={
	Described the relationship of the VM/XA passive serialization to RCU.
}
}

@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"
,annotation={
	Compared updated RCU implementations for the Linux kernel, and
	described System V IPC use of RCU, including order-of-magnitude
	performance improvements.
	http://www.rdrop.com/users/paulmck/RCU/rcu.FREENIX.2003.06.14.pdf
}
}

@Conference{Soules03a
,Author="Craig A. N. Soules and Jonathan Appavoo and Kevin Hui and
Dilma {Da Silva} and Gregory R. Ganger and Orran Krieger and
Michael Stumm and Robert W. Wisniewski and Marc Auslander and
Michal Ostrowski and Bryan Rosenburg and Jimi Xenidis"
,Title="System Support for Online Reconfiguration"
,Booktitle="Proceedings of the 2003 USENIX Annual Technical Conference"
,Publisher="USENIX Association"
,year="2003"
,month="June"
,pages="141-154"
}

@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"
,note="Available:
\url{http://www.linuxjournal.com/article/6993}
[Viewed November 14, 2007]"
,annotation={
	Reader-friendly intro to RCU, with the infamous old-man-and-brat
	cartoon.
}
}

@unpublished{Sarma03a
,Author="Dipankar Sarma"
,Title="RCU low latency patches"
,month="December"
,year="2003"
,note="Message ID: [email protected]"
,annotation={
	dipankar/ct.2004.03.27/RCUll.2003.12.22.patch
}
}

@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"
,month="December"
,pages="112"
,annotation={
	Applies RCU to a wildcard-search Patricia tree in order to permit
	synchronization-free lookup.  RCU is used to retain removed nodes
	for a grace period before freeing them.
}
}

@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"
,annotation={
	Reader friendly intro to dcache and RCU.
	http://www.linuxjournal.com/node/7124
	[Viewed December 26, 2010]
}
}

@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/RCU/lockperf.2004.01.17a.pdf}
[Viewed June 23, 2004]"
,annotation={
	Compares performance of RCU to that of other locking primitives
	over a number of CPUs (x86, Opteron, Itanium, and PPC).
}
}

@unpublished{Sarma04a
,Author="Dipankar Sarma"
,Title="{[PATCH]} {RCU} for low latency (experimental)"
,month="March"
,year="2004"
,note="\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=108003746402892&w=2}"
,annotation={
	Head of thread: dipankar/2004.03.23/rcu-low-lat.1.patch
}
}

@unpublished{Sarma04b
,Author="Dipankar Sarma"
,Title="Re: {[PATCH]} {RCU} for low latency (experimental)"
,month="March"
,year="2004"
,note="\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=108016474829546&w=2}"
,annotation={
	dipankar/rcuth.2004.03.24/rcu-throttle.patch
}
}

@unpublished{Spraul04a
,Author="Manfred Spraul"
,Title="[RFC] 0/5 rcu lock update"
,month="May"
,year="2004"
,note="Available:
\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=108546407726602&w=2}
[Viewed June 23, 2004]"
,annotation={
	Hierarchical-bitmap patch for RCU infrastructure.
}
}

@unpublished{Steiner04a
,Author="Jack Steiner"
,Title="Re: [Lse-tech] [RFC, PATCH] 1/5 rcu lock update:
Add per-cpu batch counter"
,month="May"
,year="2004"
,note="Available:
\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=108551764515332&w=2}
[Viewed June 23, 2004]"
,annotation={
	RCU runs reasonably on a 512-CPU SGI using Manfred Spraul's patches,
	which may be found at:
	https://lore.kernel.org/r/[email protected] (split vars into cachelines)
	https://lore.kernel.org/r/[email protected] (cpu_quiet() patch)
	https://lore.kernel.org/r/[email protected] (0/5)
	https://lore.kernel.org/r/[email protected] (1/5)
		https://lore.kernel.org/r/[email protected] (works for Jack)
	https://lore.kernel.org/r/[email protected] (2/5)
	https://lore.kernel.org/r/[email protected] (3/5)
	https://lore.kernel.org/r/[email protected] (4/5)
	https://lore.kernel.org/r/[email protected] (5/5)
}
}

@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"
,annotation={
	Describes and compares a number of modifications to the Linux RCU
	implementation that make it friendly to realtime applications.
	https://www.usenix.org/conference/2004-usenix-annual-technical-conference/making-rcu-safe-deep-sub-millisecond-response
	[Viewed July 26, 2012]
}
}

@article{MagedMichael04a
,author="Maged M. Michael"
,title="Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects"
,Year="2004"
,Month="June"
,journal="IEEE Transactions on Parallel and Distributed Systems"
,volume="15"
,number="6"
,pages="491-504"
,url="Available:
\url{http://www.research.ibm.com/people/m/michael/ieeetpds-2004.pdf}
[Viewed March 1, 2005]"
,annotation={
	New canonical hazard-pointer citation.
}
}

@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"
,annotation={
	Describes RCU implementations and presents design patterns
	corresponding to common uses of RCU in several operating-system
	kernels.
	http://www.rdrop.com/users/paulmck/RCU/RCUdissertation.2004.07.14e1.pdf
	[Viewed October 15, 2004]
}
}

@unpublished{PaulEMcKenney2004rcu:dereference
,Author="Dipankar Sarma"
,Title="{Re: RCU : Abstracted RCU dereferencing [5/5]}"
,month="August"
,year="2004"
,note="Available:
\url{https://lore.kernel.org/r/[email protected]}
[Viewed June 8, 2010]"
,annotation={
	Introduce rcu_dereference().
}
}

@unpublished{JimHouston04a
,Author="Jim Houston"
,Title="{[RFC\&PATCH] Alternative {RCU} implementation}"
,month="August"
,year="2004"
,note="Available:
\url{https://lore.kernel.org/r/[email protected]}
[Viewed February 17, 2005]"
,annotation={
	Uses active code in rcu_read_lock() and rcu_read_unlock() to
	make RCU happen, allowing RCU to function on CPUs that do not
	receive a scheduling-clock interrupt.
}
}

@unpublished{TomHart04a
,Author="Thomas E. Hart"
,Title="Master's Thesis: Applying Lock-free Techniques to the {Linux} Kernel"
,month="October"
,year="2004"
,note="Available:
\url{http://www.cs.toronto.edu/~tomhart/masters_thesis.html}
[Viewed October 15, 2004]"
,annotation={
	Proposes comparing RCU to lock-free methods for the Linux kernel.
}
}

@unpublished{Vaddagiri04a
,Author="Srivatsa Vaddagiri"
,Title="Subject: [RFC] Use RCU for tcp\_ehash lookup"
,month="October"
,year="2004"
,note="Available:
\url{http://marc.theaimsgroup.com/?t=109395731700004&r=1&w=2}
[Viewed October 18, 2004]"
,annotation={
	Srivatsa's RCU patch for tcp_ehash lookup.
}
}

@unpublished{Thirumalai04a
,Author="Ravikiran Thirumalai"
,Title="Subject: [patchset] Lockfree fd lookup 0 of 5"
,month="October"
,year="2004"
,note="Available:
\url{http://marc.theaimsgroup.com/?t=109144217400003&r=1&w=2}
[Viewed October 18, 2004]"
,annotation={
	Ravikiran's lockfree FD patch.
}
}

@unpublished{Thirumalai04b
,Author="Ravikiran Thirumalai"
,Title="Subject: Re: [patchset] Lockfree fd lookup 0 of 5"
,month="October"
,year="2004"
,note="Available:
\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=109152521410459&w=2}
[Viewed October 18, 2004]"
,annotation={
	Ravikiran's lockfree FD patch.
}
}

@unpublished{PaulEMcKenney2004rcu:assign:pointer
,Author="Paul E. McKenney"
,Title="{[PATCH 1/3] RCU: \url{rcu_assign_pointer()} removal of memory barriers}"
,month="October"
,year="2004"
,note="Available:
\url{https://lore.kernel.org/r/[email protected]}
[Viewed June 8, 2010]"
,annotation={
	Introduce rcu_assign_pointer().
}
}

@unpublished{JamesMorris04a
,Author="James Morris"
,Title="{[PATCH 2/3] SELinux} scalability - convert {AVC} to {RCU}"
,day="15"
,month="November"
,year="2004"
,note="\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=110054979416004&w=2}"
,annotation={
	James Morris posts Kaigai Kohei's patch to LKML.
	[Viewed December 10, 2004]
	Kaigai's patch is at https://lore.kernel.org/r/[email protected]
}
}

@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]"
,annotation={
	RCU helps SELinux performance.  ;-)  Made LWN.
}
}

@unpublished{PaulMcKenney2005RCUSemantics
,Author="Paul E. McKenney and Jonathan Walpole"
,Title="{RCU} Semantics: A First Attempt"
,month="January"
,year="2005"
,day="30"
,note="Available:
\url{http://www.rdrop.com/users/paulmck/RCU/rcu-semantics.2005.01.30a.pdf}
[Viewed December 6, 2009]"
,annotation={
	Early derivation of RCU semantics.
}
}

@unpublished{PaulMcKenney2005e
,Author="Paul E. McKenney"
,Title="Real-Time Preemption and {RCU}"
,month="March"
,year="2005"
,day="17"
,note="Available:
\url{https://lore.kernel.org/r/[email protected]}
[Viewed September 5, 2005]"
,annotation={
	First posting showing how RCU can be safely adapted for
	preemptible RCU read side critical sections.
}
}

@unpublished{EsbenNeilsen2005a
,Author="Esben Neilsen"
,Title="Re: Real-Time Preemption and {RCU}"
,month="March"
,year="2005"
,day="18"
,note="Available:
\url{https://lore.kernel.org/r/[email protected]}
[Viewed March 30, 2006]"
,annotation={
	Esben Neilsen suggests read-side suppression of grace-period
	processing for crude-but-workable realtime RCU.  The downside
	is indefinite grace periods...  But this is OK for experimentation
	and testing.
}
}

@unpublished{TomHart05a
,Author="Thomas E. Hart and Paul E. McKenney and Angela Demke Brown"
,Title="Efficient Memory Reclamation is Necessary for Fast Lock-Free
Data Structures"
,month="March"
,year="2005"
,note="Available:
\url{ftp://ftp.cs.toronto.edu/csrg-technical-reports/515/}
[Viewed March 4, 2005]"
,annotation={
	Comparison of RCU, QBSR, and EBSR.  RCU wins for read-mostly
	workloads.  ;-)
}
}

@unpublished{JonCorbet2005DeprecateSyncKernel
,Author="Jonathan Corbet"
,Title="API change: synchronize_kernel() deprecated"
,month="May"
,day="3"
,year="2005"
,note="Available:
\url{http://lwn.net/Articles/134484/}
[Viewed May 3, 2005]"
,annotation={
	Jon Corbet describes deprecation of synchronize_kernel()
	in favor of synchronize_rcu() and synchronize_sched().
}
}

@unpublished{PaulMcKenney05a
,Author="Paul E. McKenney"
,Title="{[RFC]} {RCU} and {CONFIG\_PREEMPT\_RT} progress"
,month="May"
,year="2005"
,note="Available:
\url{https://lore.kernel.org/r/[email protected]}
[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.
	http://lca2005.linux.org.au/Papers/Paul%20McKenney/Towards%20Hard%20Realtime%20Response%20from%20the%20Linux%20Kernel/LKS.2005.04.22a.pdf
}
}

@unpublished{PaulEMcKenneyHomePage
,Author="Paul E. McKenney"
,Title="{Paul} {E.} {McKenney}"
,month="May"
,year="2005"
,note="Available:
\url{http://www.rdrop.com/users/paulmck/}
[Viewed May 25, 2005]"
,annotation={
	Paul McKenney's home page.
}
}

@unpublished{PaulEMcKenneyRCUPage
,Author="Paul E. McKenney"
,Title="Read-Copy Update {(RCU)}"
,month="May"
,year="2005"
,note="Available:
\url{http://www.rdrop.com/users/paulmck/RCU}
[Viewed May 25, 2005]"
,annotation={
	Paul McKenney's RCU page.
}
}

@unpublished{JosephSeigh2005a
,Author="Joseph Seigh"
,Title="{RCU}+{SMR} (hazard pointers)"
,month="July"
,year="2005"
,note="Personal communication"
,annotation={
	Joe Seigh announcing his atomic-ptr-plus project.
	http://sourceforge.net/projects/atomic-ptr-plus/
}
}

@unpublished{JosephSeigh2005b
,Author="Joseph Seigh"
,Title="Lock-free synchronization primitives"
,month="July"
,day="6"
,year="2005"
,note="Available:
\url{http://sourceforge.net/projects/atomic-ptr-plus/}
[Viewed August 8, 2005]"
,annotation={
	Joe Seigh's atomic-ptr-plus project.
}
}

@unpublished{PaulMcKenney2005c
,Author="Paul E.McKenney"
,Title="{[RFC,PATCH] RCU} and {CONFIG\_PREEMPT\_RT} sane patch"
,month="August"
,day="1"
,year="2005"
,note="Available:
\url{https://lore.kernel.org/r/[email protected]}
[Viewed March 14, 2006]"
,annotation={
	First operating counter-based realtime RCU patch posted to LKML.
}
}

@unpublished{PaulMcKenney2005d
,Author="Paul E. McKenney"
,Title="Re: [Fwd: Re: [patch] Real-Time Preemption, -RT-2.6.13-rc4-V0.7.52-01]"
,month="August"
,day="8"
,year="2005"
,note="Available:
\url{https://lore.kernel.org/r/[email protected]}
[Viewed March 14, 2006]"
,annotation={
	First operating counter-based realtime RCU patch posted to LKML,
	but fixed so that various unusual combinations of configuration
	parameters all function properly.
}
}

@unpublished{PaulMcKenney2005rcutorture
,Author="Paul E. McKenney"
,Title="{[PATCH]} {RCU} torture testing"
,month="October"
,day="1"
,year="2005"
,note="Available:
\url{https://lore.kernel.org/r/[email protected]}
[Viewed March 14, 2006]"
,annotation={
	First rcutorture patch.
}
}

@unpublished{DavidSMiller2006HashedLocking
,Author="David S. Miller"
,Title="Re: [{PATCH}, {RFC}] {RCU} : {OOM} avoidance and lower latency"
,month="January"
,day="6"
,year="2006"
,note="Available:
\url{https://lore.kernel.org/r/[email protected]}
[Viewed February 29, 2012]"
,annotation={
	David Miller's view on hashed arrays of locks: used to really
	like it, but time he saw an opportunity for this technique,
	something else always proved superior.  Partitioning or RCU.  ;-)
}
}

@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"
,note="Available:
\url{http://www.rdrop.com/users/paulmck/RCU/hart_ipdps06.pdf}
[Viewed April 28, 2008]"
,annotation={
	Compares QSBR, HPBR, EBR, and lock-free reference counting.
	http://www.cs.toronto.edu/~tomhart/perflab/ipdps06.tgz
}
}

@unpublished{NickPiggin2006radixtree
,Author="Nick Piggin"
,Title="[patch 3/3] radix-tree: {RCU} lockless readside"
,month="June"
,day="20"
,year="2006"
,note="Available:
\url{https://lore.kernel.org/r/[email protected]}
[Viewed March 25, 2008]"
,annotation={
	RCU-protected radix tree.
}
}

@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{https://kernel.org/doc/ols/2006/ols2006v2-pages-131-146.pdf}
\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{WikipediaRCU
,Author="Paul E. McKenney and Chris Purcell and Algae and Ben Schumin and
Gaius Cornelius and Qwertyus and Neil Conway and Sbw and Blainster and
Canis Rufus and Zoicon5 and Anome and Hal Eisen"
,Title="Read-Copy Update"
,month="July"
,day="8"
,year="2006"
,note="\url{https://en.wikipedia.org/wiki/Read-copy-update}"
,annotation={
	Wikipedia RCU page as of July 8 2006.
	[Viewed August 21, 2006]
}
}

@Conference{NickPiggin2006LocklessPageCache
,Author="Nick Piggin"
,Title="A Lockless Pagecache in Linux---Introduction, Progress, Performance"
,Booktitle="{Ottawa Linux Symposium}"
,Month="July"
,Year="2006"
,pages="v2 249-254"
,note="Available:
\url{https://kernel.org/doc/ols/2006/ols2006v2-pages-249-262.pdf}
[Viewed January 11, 2009]"
,annotation={
	Uses RCU-protected radix tree for a lockless page cache.
}
}

@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="\url{http://www.nada.kth.se/~snilsson/publications/TRASH/trash.pdf}"
,annotation={
	RCU-protected dynamic trie-hash combination.
	[Viewed March 4, 2011]
}
}

@unpublished{ChristophHellwig2006RCU2SRCU
,Author="Christoph Hellwig"
,Title="Re: {[-mm PATCH 1/4]} {RCU}: split classic rcu"
,month="September"
,day="28"
,year="2006"
,note="Available:
\url{https://lore.kernel.org/r/[email protected]}
[Viewed March 27, 2008]"
}

@unpublished{PaulEMcKenneyRCUusagePage
,Author="Paul E. McKenney"
,Title="{RCU} {Linux} Usage"
,month="October"
,year="2006"
,note="Available:
\url{http://www.rdrop.com/users/paulmck/RCU/linuxusage.html}
[Viewed January 14, 2007]"
,annotation={
	Paul McKenney's RCU page showing graphs plotting Linux-kernel
	usage of RCU.
}
}

@unpublished{PaulEMcKenneyRCUusageRawDataPage
,Author="Paul E. McKenney"
,Title="Read-Copy Update {(RCU)} Usage in {Linux} Kernel"
,month="October"
,year="2006"
,note="Available:
\url{http://www.rdrop.com/users/paulmck/RCU/linuxusage/rculocktab.html}
[Viewed January 14, 2007]"
,annotation={
	Paul McKenney's RCU page showing Linux usage of RCU in tabular
	form, with links to corresponding cscope databases.
}
}

@unpublished{GauthamShenoy2006RCUrwlock
,Author="Gautham R. Shenoy"
,Title="[PATCH 4/5] lock\_cpu\_hotplug: Redesign - Lightweight implementation of lock\_cpu\_hotplug"
,month="October"
,year="2006"
,day=26
,note="Available:
\url{https://lore.kernel.org/r/[email protected]}
[Viewed January 26, 2009]"
,annotation={
	RCU-based reader-writer lock that allows readers to proceed with
	no memory barriers or atomic instruction in absence of writers.
	If writer do show up, readers must of course wait as required by
	the semantics of reader-writer locking.  This is a recursive
	lock.
}
}

@unpublished{JensAxboe2006SlowSRCU
,Author="Jens Axboe"
,Title="Re: [patch] cpufreq: mark \url{cpufreq_tsc()} as
\url{core_initcall_sync}"
,month="November"
,year="2006"
,day=17
,note="Available:
\url{https://lore.kernel.org/r/[email protected]}
[Viewed May 28, 2007]"
,annotation={
	SRCU's grace periods are too slow for Jens, even after a
	factor-of-three speedup.
	Sped-up version of SRCU at https://lore.kernel.org/r/[email protected].
}
}

@unpublished{OlegNesterov2006QRCU
,Author="Oleg Nesterov"
,Title="Re: [patch] cpufreq: mark {\tt cpufreq\_tsc()} as
{\tt core\_initcall\_sync}"
,month="November"
,year="2006"
,day=19
,note="Available:
\url{https://lore.kernel.org/r/20061119190027.GA3676@oleg}
[Viewed May 28, 2007]"
,annotation={
	First cut of QRCU.  Expanded/corrected versions followed.
	Used to be OlegNesterov2007QRCU, now time-corrected.
}
}

@unpublished{OlegNesterov2006aQRCU
,Author="Oleg Nesterov"
,Title="Re: [RFC, PATCH 1/2] qrcu: {"quick"} srcu implementation"
,month="November"
,year="2006"
,day=30
,note="Available:
\url{https://lore.kernel.org/r/20061130015714.GC1350@oleg}
[Viewed November 26, 2008]"
,annotation={
	Expanded/corrected version of QRCU.
	Used to be OlegNesterov2007aQRCU, now time-corrected.
}
}

@unpublished{EvgeniyPolyakov2006RCUslowdown
,Author="Evgeniy Polyakov"
,Title="Badness in postponing work"
,month="December"
,year="2006"
,day=05
,note="Available:
\url{http://www.ioremap.net/node/41}
[Viewed October 28, 2008]"
,annotation={
	Using RCU as a pure delay leads to a 2.5x slowdown in skbs in
	the Linux kernel.
}
}

@inproceedings{ChrisMatthews2006ClusteredObjectsRCU
,author = {Matthews, Chris and Coady, Yvonne and Appavoo, Jonathan}
,title = {Portability events: a programming model for scalable system infrastructures}
,booktitle = {PLOS '06: Proceedings of the 3rd workshop on Programming languages and operating systems}
,year = {2006}
,isbn = {1-59593-577-0}
,pages = {11}
,location = {San Jose, California}
,doi = {http://doi.acm.org/10.1145/1215995.1216006}
,publisher = {ACM}
,address = {New York, NY, USA}
,annotation={
	Uses K42's RCU-like functionality to manage clustered-object
	lifetimes.
}
}

@article{DilmaDaSilva2006K42
,author = {Silva, Dilma Da and Krieger, Orran and Wisniewski, Robert W. and Waterland, Amos and Tam, David and Baumann, Andrew}
,title = {K42: an infrastructure for operating system research}
,journal = {SIGOPS Oper. Syst. Rev.}
,volume = {40}
,number = {2}
,year = {2006}
,issn = {0163-5980}
,pages = {34--42}
,doi = {http://doi.acm.org/10.1145/1131322.1131333}
,publisher = {ACM}
,address = {New York, NY, USA}
,annotation={
	Describes relationship of K42 generations to RCU.
}
}

# CoreyMinyard2007list_splice_rcu
@unpublished{CoreyMinyard2007list:splice:rcu
,Author="Corey Minyard and Paul E. McKenney"
,Title="{[PATCH]} add an {RCU} version of list splicing"
,month="January"
,year="2007"
,day=3
,note="Available:
\url{https://lore.kernel.org/r/20070103152738.GA16063@localdomain}
[Viewed May 28, 2007]"
,annotation={
	Patch for list_splice_rcu().
}
}

@unpublished{PaulEMcKenney2007rcubarrier
,Author="Paul E. McKenney"
,Title="{RCU} and Unloadable Modules"
,month="January"
,day="14"
,year="2007"
,note="Available:
\url{http://lwn.net/Articles/217484/}
[Viewed November 22, 2007]"
,annotation={
	LWN article introducing the rcu_barrier() primitive.
}
}

@unpublished{PeterZijlstra2007SyncBarrier
,Author="Peter Zijlstra and Ingo Molnar"
,Title="{[PATCH 3/7]} barrier: a scalable synchonisation barrier"
,month="January"
,year="2007"
,day=28
,note="Available:
\url{https://lore.kernel.org/r/[email protected]}
[Viewed March 27, 2008]"
,annotation={
	RCU-like implementation for frequent updaters and rare readers(!).
	Subsumed into QRCU.  Maybe...
}
}

@unpublished{PaulEMcKenney2007BoostRCU
,Author="Paul E. McKenney"
,Title="Priority-Boosting {RCU} Read-Side Critical Sections"
,month="February"
,day="5"
,year="2007"
,note="\url{http://lwn.net/Articles/220677/}"
,annotation={
	LWN article introducing RCU priority boosting.
	Revised:
	http://www.rdrop.com/users/paulmck/RCU/RCUbooststate.2007.04.16a.pdf
	[Viewed September 7, 2007]
}
}

@unpublished{PaulMcKenney2007QRCUpatch
,Author="Paul E. McKenney"
,Title="{[PATCH]} {QRCU} with lockless fastpath"
,month="February"
,year="2007"
,day=24
,note="Available:
\url{https://lore.kernel.org/r/[email protected]}
[Viewed March 27, 2008]"
,annotation={
	Patch for QRCU supplying lock-free fast path.
}
}

@article{JonathanAppavoo2007K42RCU
,author = {Appavoo, Jonathan and Silva, Dilma Da and Krieger, Orran and Auslander, Marc and Ostrowski, Michal and Rosenburg, Bryan and Waterland, Amos and Wisniewski, Robert W. and Xenidis, Jimi and Stumm, Michael and Soares, Livio}
,title = {Experience distributing objects in an SMMP OS}
,journal = {ACM Trans. Comput. Syst.}
,volume = {25}
,number = {3}
,year = {2007}
,issn = {0734-2071}
,pages = {6/1--6/52}
,doi = {http://doi.acm.org/10.1145/1275517.1275518}
,publisher = {ACM}
,address = {New York, NY, USA}
,annotation={
	Role of RCU in K42.
}
}

@conference{RobertOlsson2007Trash
,Author="Robert Olsson and Stefan Nilsson"
,Title="{TRASH}: A dynamic {LC}-trie and hash data structure"
,booktitle="Workshop on High Performance Switching and Routing (HPSR'07)"
,month="May"
,year="2007"
,note="Available:
\url{http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4281239}
[Viewed October 1, 2010]"
,annotation={
	RCU-protected dynamic trie-hash combination.
}
}

@conference{PeterZijlstra2007ConcurrentPagecacheRCU
,Author="Peter Zijlstra"
,Title="Concurrent Pagecache"
,Booktitle="Linux Symposium"
,month="June"
,year="2007"
,address="Ottawa, Canada"
,note="Available:
\url{http://ols.108.redhat.com/2007/Reprints/zijlstra-Reprint.pdf}
[Viewed April 14, 2008]"
,annotation={
	Page-cache modifications permitting RCU readers and concurrent
	updates.
}
}

@unpublished{PaulEMcKenney2007whatisRCU
,Author="Paul E. McKenney"
,Title="What is {RCU}?"
,year="2007"
,month="07"
,note="Available:
\url{http://www.rdrop.com/users/paulmck/RCU/whatisRCU.html}
[Viewed July 6, 2007]"
,annotation={
	Describes RCU in Linux kernel.
}
}

@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).
	Merged patch at: https://lore.kernel.org/r/[email protected]
}
}

@unpublished{PaulEMcKenney2007WG21DDOatomics
,Author="Paul E. McKenney and Hans-J. Boehm and Lawrence Crowl"
,Title="C++ Data-Dependency Ordering: Atomics and Memory Model"
,month="August"
,day="3"
,year="2007"
,note="Available:
\url{http://open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2664.htm}
[Viewed December 7, 2009]"
,annotation={
	RCU for C++, parts 1 and 2.
}
}

@unpublished{PaulEMcKenney2007WG21DDOannotation
,Author="Paul E. McKenney and Lawrence Crowl"
,Title="C++ Data-Dependency Ordering: Function Annotation"
,month="September"
,day="18"
,year="2008"
,note="Available:
\url{http://open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2782.htm}
[Viewed December 7, 2009]"
,annotation={
	RCU for C++, part 2, updated many times.
}
}

@unpublished{PaulEMcKenney2007PreemptibleRCUPatch
,Author="Paul E. McKenney"
,Title="[PATCH RFC 0/9] {RCU}: Preemptible {RCU}"
,month="September"
,day="10"
,year="2007"
,note="Available:
\url{https://lore.kernel.org/r/[email protected]}
[Viewed October 25, 2007]"
,annotation={
	Final patch for preemptible RCU to -rt.  (Later patches were
	to mainline, eventually incorporated.)
}
}

@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.
}
}

@article{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."
,volume={67}
,number="12"
,year="2007"
,issn="0743-7315"
,pages="1270--1285"
,doi="http://dx.doi.org/10.1016/j.jpdc.2007.04.010"
,publisher="Academic Press, Inc."
,address="Orlando, FL, USA"
,annotation={
	Compares QSBR, HPBR, EBR, and lock-free reference counting.
	Journal version of ThomasEHart2006a.
}
}

# MathieuDesnoyers2007call_rcu_schedNeeded
@unpublished{MathieuDesnoyers2007call:rcu:schedNeeded
,Author="Mathieu Desnoyers"
,Title="Re: [patch 1/2] {Linux} Kernel Markers - Support Multiple Probes"
,month="December"
,day="20"
,year="2007"
,note="Available:
\url{https://lore.kernel.org/r/20071220142540.GB22523@Krystal}
[Viewed March 27, 2008]"
,annotation={
	Request for call_rcu_sched() and rcu_barrier_sched().
}
}


########################################################################
#
#	"What is RCU?" LWN series.
#
#	http://lwn.net/Articles/262464/ (What is RCU, Fundamentally?)
#	http://lwn.net/Articles/263130/ (What is RCU's Usage?)
#	http://lwn.net/Articles/264090/ (What is RCU's API?)

@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.
#
########################################################################


@unpublished{SteveRostedt2008dyntickRCUpatch
,Author="Steven Rostedt and Paul E. McKenney"
,Title="{[PATCH]} add support for dynamic ticks and preempt rcu"
,month="January"
,day="29"
,year="2008"
,note="Available:
\url{https://lore.kernel.org/r/[email protected]}
[Viewed March 27, 2008]"
,annotation={
	Patch that prevents preemptible RCU from unnecessarily waking
	up dynticks-idle CPUs.
}
}

@unpublished{PaulEMcKenney2008LKMLDependencyOrdering
,Author="Paul E. McKenney"
,Title="Re: [PATCH 02/22 -v7] Add basic support for gcc profiler instrumentation"
,month="February"
,day="1"
,year="2008"
,note="Available:
\url{https://lore.kernel.org/r/[email protected]}
[Viewed October 18, 2008]"
,annotation={
	Explanation of compilers violating dependency ordering.
}
}

@Conference{PaulEMcKenney2008Beijing
,Author="Paul E. McKenney"
,Title="Introducing Technology Into {Linux} Or:
Introducing your technology Into {Linux} will require introducing a
lot of {Linux} into your technology!!!"
,Booktitle="2008 Linux Developer Symposium - China"
,Publisher="OSS China"
,Month="February"
,Year="2008"
,Address="Beijing, China"
,note="Available:
\url{http://www.rdrop.com/users/paulmck/RCU/TechIntroLinux.2008.02.19a.pdf}
[Viewed August 12, 2008]"
}

@unpublished{PaulEMcKenney2008dynticksRCU
,Author="Paul E. McKenney and Steven Rostedt"
,Title="Integrating and Validating dynticks and Preemptable RCU"
,month="April"
,day="24"
,year="2008"
,note="Available:
\url{http://lwn.net/Articles/279077/}
[Viewed April 24, 2008]"
,annotation={
	Describes use of Promela and Spin to validate (and fix!) the
	dynticks/RCU interface.
}
}

@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="May"
,journal="IBM Systems Journal"
,volume="47"
,number="2"
,pages="221-236"
,annotation={
	RCU, realtime RCU, sleepable RCU, performance.
	http://www.research.ibm.com/journal/sj/472/guniguntala.pdf
	[Viewed April 24, 2008]
}
}

@unpublished{LaiJiangshan2008NewClassicAlgorithm
,Author="Lai Jiangshan"
,Title="[{RFC}][{PATCH}] rcu classic: new algorithm for callbacks-processing"
,month="June"
,day="3"
,year="2008"
,note="Available:
\url{https://lore.kernel.org/r/[email protected]}
[Viewed December 10, 2008]"
,annotation={
	Updated RCU classic algorithm.  Introduced multi-tailed list
	for RCU callbacks and also pulling common code into
	__call_rcu().
}
}

@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.
	http://portal.acm.org/citation.cfm?doid=1400097.1400099
}
}

@unpublished{ManfredSpraul2008StateMachineRCU
,Author="Manfred Spraul"
,Title="[{RFC}, {PATCH}] state machine based rcu"
,month="August"
,day="21"
,year="2008"
,note="Available:
\url{https://lore.kernel.org/r/[email protected]}
[Viewed December 8, 2008]"
,annotation={
	State-based RCU.  One key thing that this patch does is to
	separate the dynticks handling of NMIs and IRQs.
}
}

@unpublished{ManfredSpraul2008dyntickIRQNMI
,Author="Manfred Spraul"
,Title="Re: [{RFC}, {PATCH}] v4 scalable classic {RCU} implementation"
,month="September"
,day="6"
,year="2008"
,note="Available:
\url{https://lore.kernel.org/r/[email protected]}
[Viewed December 8, 2008]"
,annotation={
	Manfred notes a fix required to my attempt to separate irq
	and NMI processing for hierarchical RCU's dynticks interface.
}
}

# Was PaulEMcKenney2011cyclicRCU
@techreport{PaulEMcKenney2008cyclicRCU
,author="Paul E. McKenney"
,title="Efficient Support of Consistent Cyclic Search With Read-Copy Update"
,institution="US Patent and Trademark Office"
,address="Washington, DC"
,year="2008"
,number="US Patent 7,426,511"
,month="September"
,pages="23"
,annotation={
	Maintains an additional level of indirection to allow
	readers to confine themselves to the desired snapshot of the
	data structure.  Only permits one update at a time.
}
}

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

@unpublished{PaulEMcKenney2009BloatwatchRCU
,Author="Paul E. McKenney"
,Title="Re: [PATCH fyi] RCU: the bloatwatch edition"
,month="January"
,day="14"
,year="2009"
,note="Available:
\url{https://lore.kernel.org/r/[email protected]}
[Viewed January 15, 2009]"
,annotation={
	Small-footprint implementation of RCU for uniprocessor
	embedded applications -- and also for exposition purposes.
}
}

@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="\url{http://lttng.org/urcu}"
,annotation={
	Mathieu Desnoyers's user-space RCU implementation.
	git://lttng.org/userspace-rcu.git
	http://lttng.org/cgi-bin/gitweb.cgi?p=userspace-rcu.git
	http://lttng.org/urcu
	https://lore.kernel.org/r/20090206030543.GB8560@Krystal
}
}

@unpublished{PaulEMcKenney2009LWNBloatWatchRCU
,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{EvgeniyPolyakov2009EllipticsNetwork
,Author="Evgeniy Polyakov"
,Title="The Elliptics Network"
,month="April"
,day="17"
,year="2009"
,note="Available:
\url{http://www.ioremap.net/projects/elliptics}
[Viewed April 30, 2009]"
,annotation={
	Distributed hash table with transactions, using elliptic
	hash functions to distribute data.
}
}

@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{https://lore.kernel.org/r/[email protected]}
[Viewed August 16, 2009]"
,annotation={
	First posting of expedited RCU to be accepted into -tip.
}
}

@unpublished{PaulEMcKenney2009fastRTRCU
,Author="Paul E. McKenney"
,Title="[{PATCH} {RFC} -tip 0/4] {RCU} cleanups and simplified preemptable {RCU}"
,month="July"
,day="23"
,year="2009"
,note="Available:
\url{https://lore.kernel.org/r/[email protected]}
[Viewed August 15, 2009]"
,annotation={
	First posting of simple and fast preemptible RCU.
}
}

@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.
	Superseded by JoshTriplett2010RPHash
}
}

@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]"
,annotation={
	Chapter 6 (page 97) covers user-level RCU.
}
}

@unpublished{RelativisticProgrammingWiki
,Author="Josh Triplett and Paul E. McKenney and Jonathan Walpole"
,Title="Relativistic Programming"
,month="September"
,year="2009"
,note="Available:
\url{http://wiki.cs.pdx.edu/rp/}
[Viewed December 9, 2009]"
,annotation={
	Main Relativistic Programming Wiki.
}
}

@conference{PaulEMcKenney2009DeterministicRCU
,Author="Paul E. McKenney"
,Title="Deterministic Synchronization in Multicore Systems: the Role of {RCU}"
,Booktitle="Eleventh Real Time Linux Workshop"
,month="September"
,year="2009"
,address="Dresden, Germany"
,note="Available:
\url{http://www.rdrop.com/users/paulmck/realtime/paper/DetSyncRCU.2009.08.18a.pdf}
[Viewed January 14, 2009]"
}

@unpublished{PaulEMcKenney2009HuntingHeisenbugs
,Author="Paul E. McKenney"
,Title="Hunting Heisenbugs"
,month="November"
,year="2009"
,day="1"
,note="Available:
\url{http://paulmck.livejournal.com/14639.html}
[Viewed June 4, 2010]"
,annotation={
	Day-one bug in Tree RCU that took forever to track down.
}
}

@unpublished{MathieuDesnoyers2009defer:rcu
,Author="Mathieu Desnoyers"
,Title="Kernel RCU: shrink the size of the struct rcu\_head"
,month="December"
,year="2009"
,note="Available:
\url{https://lore.kernel.org/r/20091018232918.GA7385@Krystal}
[Viewed December 29, 2009]"
,annotation={
	Mathieu proposed defer_rcu() with fixed-size per-thread pool
	of RCU callbacks.
}
}

@unpublished{MathieuDesnoyers2009VerifPrePub
,Author="Mathieu Desnoyers and Paul E. McKenney and Michel R. Dagenais"
,Title="Multi-Core Systems Modeling for Formal Verification of Parallel Algorithms"
,month="December"
,year="2009"
,note="Submitted to IEEE TPDS"
,annotation={
	OOMem model for Mathieu's user-level RCU mechanical proof of
	correctness.
}
}

@unpublished{MathieuDesnoyers2009URCUPrePub
,Author="Mathieu Desnoyers and Paul E. McKenney and Alan Stern and Michel R. Dagenais and Jonathan Walpole"
,Title="User-Level Implementations of Read-Copy Update"
,month="December"
,year="2010"
,url={\url{http://www.computer.org/csdl/trans/td/2012/02/ttd2012020375-abs.html}}
,annotation={
	RCU overview, desiderata, semi-formal semantics, user-level RCU
	usage scenarios, three classes of RCU implementation, wait-free
	RCU updates, RCU grace-period batching, update overhead,
	http://www.rdrop.com/users/paulmck/RCU/urcu-main-accepted.2011.08.30a.pdf
	http://www.rdrop.com/users/paulmck/RCU/urcu-supp-accepted.2011.08.30a.pdf
	Superseded by MathieuDesnoyers2012URCU.
}
}

@inproceedings{HariKannan2009DynamicAnalysisRCU
,author = {Kannan, Hari}
,title = {Ordering decoupled metadata accesses in multiprocessors}
,booktitle = {MICRO 42: Proceedings of the 42nd Annual IEEE/ACM International Symposium on Microarchitecture}
,year = {2009}
,isbn = {978-1-60558-798-1}
,pages = {381--390}
,location = {New York, New York}
,doi = {http://doi.acm.org/10.1145/1669112.1669161}
,publisher = {ACM}
,address = {New York, NY, USA}
,annotation={
	Uses RCU to protect metadata used in dynamic analysis.
}
}

@conference{PaulEMcKenney2010SimpleOptRCU
,Author="Paul E. McKenney"
,Title="Simplicity Through Optimization"
,Booktitle="linux.conf.au 2010"
,month="January"
,year="2010"
,address="Wellington, New Zealand"
,note="Available:
\url{http://www.rdrop.com/users/paulmck/RCU/SimplicityThruOptimization.2010.01.21f.pdf}
[Viewed October 10, 2010]"
,annotation={
	TREE_PREEMPT_RCU optimizations greatly simplified the old
	PREEMPT_RCU implementation.
}
}

@unpublished{PaulEMcKenney2010LockdepRCU
,Author="Paul E. McKenney"
,Title="Lockdep-{RCU}"
,month="February"
,year="2010"
,day="1"
,note="\url{https://lwn.net/Articles/371986/}"
,annotation={
	CONFIG_PROVE_RCU, or at least an early version.
	[Viewed June 4, 2010]
}
}

@unpublished{AviKivity2010KVM2RCU
,Author="Avi Kivity"
,Title="[{PATCH} 37/40] {KVM}: Bump maximum vcpu count to 64"
,month="February"
,year="2010"
,note="Available:
\url{http://www.mail-archive.com/[email protected]/msg28640.html}
[Viewed March 20, 2010]"
,annotation={
	Use of RCU permits KVM to increase the size of guest OSes from
	16 CPUs to 64 CPUs.
}
}

@unpublished{HerbertXu2010RCUResizeHash
,Author="Herbert Xu"
,Title="bridge: Add core IGMP snooping support"
,month="February"
,year="2010"
,note="Available:
\url{http://thread.gmane.org/gmane.linux.network/153338}
[Viewed June 9, 2014]"
,annotation={
	Use a pair of list_head structures to support RCU-protected
	resizable hash tables.
}
}

@mastersthesis{AbhinavDuggal2010Masters
,author="Abhinav Duggal"
,title="Stopping Data Races Using Redflag"
,school="Stony Brook University"
,year="2010"
,annotation={
	Data-race detector incorporating RCU.
	http://www.filesystems.org/docs/abhinav-thesis/abhinav_thesis.pdf
}
}

@article{JoshTriplett2010RPHash
,author="Josh Triplett and Paul E. McKenney and Jonathan Walpole"
,title="Scalable Concurrent Hash Tables via Relativistic Programming"
,journal="ACM Operating Systems Review"
,year=2010
,volume=44
,number=3
,month="July"
,annotation={
	RP fun with hash tables.
	http://portal.acm.org/citation.cfm?id=1842733.1842750
}
}

@unpublished{PaulEMcKenney2010RCUAPI
,Author="Paul E. McKenney"
,Title="The {RCU} {API}, 2010 Edition"
,month="December"
,day="8"
,year="2010"
,note="\url{http://lwn.net/Articles/418853/}"
,annotation={
	Includes updated software-engineering features.
	[Viewed December 8, 2010]
}
}

@mastersthesis{AndrejPodzimek2010masters
,author="Andrej Podzimek"
,title="Read-Copy-Update for OpenSolaris"
,school="Charles University in Prague"
,year="2010"
,note="Available:
\url{https://andrej.podzimek.org/thesis.pdf}
[Viewed January 31, 2011]"
,annotation={
	Reviews RCU implementations and creates a few for OpenSolaris.
	Drives quiescent-state detection from RCU read-side primitives,
	in a manner roughly similar to that of Jim Houston.
}
}

@unpublished{LinusTorvalds2011Linux2:6:38:rc1:NPigginVFS
,Author="Linus Torvalds"
,Title="Linux 2.6.38-rc1"
,month="January"
,year="2011"
,note="Available:
\url{https://lore.kernel.org/r/[email protected]}
[Viewed March 4, 2011]"
,annotation={
	"The RCU-based name lookup is at the other end of the spectrum - the
	absolute anti-gimmick. It's some seriously good stuff, and gets rid of
	the last main global lock that really tends to hurt some kernel loads.
	The dentry lock is no longer a big serializing issue. What's really
	nice about it is that it actually improves performance a lot even for
	single-threaded loads (on an SMP kernel), because it gets rid of some
	of the most expensive parts of path component lookup, which was the
	d_lock on every component lookup. So I'm seeing improvements of 30-50%
	on some seriously pathname-lookup intensive loads."
}
}

@techreport{JoshTriplett2011RPScalableCorrectOrdering
,author = {Josh Triplett and Philip W. Howard and Paul E. McKenney and Jonathan Walpole}
,title = {Scalable Correct Memory Ordering via Relativistic Programming}
,year = {2011}
,number = {11-03}
,institution = {Portland State University}
,note = {\url{http://www.cs.pdx.edu/pdfs/tr1103.pdf}}
}

@inproceedings{PhilHoward2011RCUTMRBTree
,author = {Philip W. Howard and Jonathan Walpole}
,title = {A Relativistic Enhancement to Software Transactional Memory}
,booktitle = {Proceedings of the 3rd USENIX conference on Hot topics in parallelism}
,series = {HotPar'11}
,year = {2011}
,location = {Berkeley, CA}
,pages = {1--6}
,numpages = {6}
,url = {http://www.usenix.org/event/hotpar11/tech/final_files/Howard.pdf}
,publisher = {USENIX Association}
,address = {Berkeley, CA, USA}
}

@techreport{PaulEMcKenney2011cyclicparallelRCU
,author="Paul E. McKenney and Jonathan Walpole"
,title="Efficient Support of Consistent Cyclic Search With Read-Copy Update and Parallel Updates"
,institution="US Patent and Trademark Office"
,address="Washington, DC"
,year="2011"
,number="US Patent 7,953,778"
,month="May"
,pages="34"
,annotation={
	Maintains an array of generation numbers to track in-flight
	updates and keeps an additional level of indirection to allow
	readers to confine themselves to the desired snapshot of the
	data structure.
}
}

@inproceedings{Triplett:2011:RPHash
,author = {Triplett, Josh and McKenney, Paul E. and Walpole, Jonathan}
,title = {Resizable, Scalable, Concurrent Hash Tables via Relativistic Programming}
,booktitle = {Proceedings of the 2011 USENIX Annual Technical Conference}
,month = {June}
,year = {2011}
,pages = {145--158}
,numpages = {14}
,url={http://www.usenix.org/event/atc11/tech/final_files/Triplett.pdf}
,publisher = {The USENIX Association}
,address = {Portland, OR USA}
}

@unpublished{PaulEMcKenney2011RCU3.0trainwreck
,Author="Paul E. McKenney"
,Title="3.0 and {RCU:} what went wrong"
,month="July"
,day="27"
,year="2011"
,note="\url{http://lwn.net/Articles/453002/}"
,annotation={
	Analysis of the RCU trainwreck in Linux kernel 3.0.
	[Viewed July 27, 2011]
}
}

@unpublished{NeilBrown2011MeetTheLockers
,Author="Neil Brown"
,Title="Meet the {Lockers}"
,month="August"
,day="3"
,year="2011"
,note="Available:
\url{http://lwn.net/Articles/453685/}
[Viewed September 2, 2011]"
,annotation={
	The Locker family as an analogy for locking, reference counting,
	RCU, and seqlock.
}
}

@inproceedings{Seyster:2011:RFA:2075416.2075425
,author = {Seyster, Justin and Radhakrishnan, Prabakar and Katoch, Samriti and Duggal, Abhinav and Stoller, Scott D. and Zadok, Erez}
,title = {Redflag: a framework for analysis of Kernel-level concurrency}
,booktitle = {Proceedings of the 11th international conference on Algorithms and architectures for parallel processing - Volume Part I}
,series = {ICA3PP'11}
,year = {2011}
,isbn = {978-3-642-24649-4}
,location = {Melbourne, Australia}
,pages = {66--79}
,numpages = {14}
,url = {http://dl.acm.org/citation.cfm?id=2075416.2075425}
,acmid = {2075425}
,publisher = {Springer-Verlag}
,address = {Berlin, Heidelberg}
}

@phdthesis{JoshTriplettPhD
,author="Josh Triplett"
,title="Relativistic Causal Ordering: A Memory Model for Scalable Concurrent Data Structures"
,school="Portland State University"
,year="2012"
,annotation={
	RCU-protected hash tables, barriers vs. read-side traversal order.
	.
	If the updater is making changes in the opposite direction from
	the read-side traversal order, the updater need only execute a
	memory-barrier instruction, but if in the same direction, the
	updater needs to wait for a grace period between the individual
	updates.
}
}

@article{MathieuDesnoyers2012URCU
,Author="Mathieu Desnoyers and Paul E. McKenney and Alan Stern and Michel R. Dagenais and Jonathan Walpole"
,Title="User-Level Implementations of Read-Copy Update"
,journal="IEEE Transactions on Parallel and Distributed Systems"
,volume={23}
,year="2012"
,issn="1045-9219"
,pages="375-382"
,doi="http://doi.ieeecomputersociety.org/10.1109/TPDS.2011.159"
,publisher="IEEE Computer Society"
,address="Los Alamitos, CA, USA"
,annotation={
	RCU overview, desiderata, semi-formal semantics, user-level RCU
	usage scenarios, three classes of RCU implementation, wait-free
	RCU updates, RCU grace-period batching, update overhead,
	http://www.rdrop.com/users/paulmck/RCU/urcu-main-accepted.2011.08.30a.pdf
	http://www.rdrop.com/users/paulmck/RCU/urcu-supp-accepted.2011.08.30a.pdf
	http://www.computer.org/cms/Computer.org/dl/trans/td/2012/02/extras/ttd2012020375s.pdf
}
}

@inproceedings{AustinClements2012RCULinux:mmapsem
,author = {Austin Clements and Frans Kaashoek and Nickolai Zeldovich}
,title = {Scalable Address Spaces Using {RCU} Balanced Trees}
,booktitle = {Architectural Support for Programming Languages and Operating Systems (ASPLOS 2012)}
,month = {March}
,year = {2012}
,pages = {199--210}
,numpages = {12}
,publisher = {ACM}
,address = {London, UK}
,url="http://people.csail.mit.edu/nickolai/papers/clements-bonsai.pdf"
}

@unpublished{PaulEMcKenney2012ELCbattery
,Author="Paul E. McKenney"
,Title="Making {RCU} Safe For Battery-Powered Devices"
,month="February"
,day="15"
,year="2012"
,note="Available:
\url{http://www.rdrop.com/users/paulmck/RCU/RCUdynticks.2012.02.15b.pdf}
[Viewed March 1, 2012]"
,annotation={
	RCU_FAST_NO_HZ, round 2.
}
}

@article{GuillermoVigueras2012RCUCrowd
,author = {Vigueras, Guillermo and Ordu\~{n}a, Juan M. and Lozano, Miguel}
,day = {25}
,doi = {10.1007/s11227-012-0766-x}
,issn = {0920-8542}
,journal = {The Journal of Supercomputing}
,keywords = {linux, simulation}
,month = apr
,posted-at = {2012-05-03 09:12:04}
,priority = {2}
,title = {{A Read-Copy Update based parallel server for distributed crowd simulations}}
,url = {http://dx.doi.org/10.1007/s11227-012-0766-x}
,year = {2012}
}


@unpublished{JonCorbet2012ACCESS:ONCE
,Author="Jon Corbet"
,Title="{ACCESS\_ONCE()}"
,month="August"
,day="1"
,year="2012"
,note="\url{http://lwn.net/Articles/508991/}"
,annotation={
	A couple of simple specific compiler optimizations that motivate
	ACCESS_ONCE().
}
}

@unpublished{AlexeyGotsman2012VerifyGraceExtended
,Author="Alexey Gotsman and Noam Rinetzky and Hongseok Yang"
,Title="Verifying Highly Concurrent Algorithms with Grace (extended version)"
,month="July"
,day="10"
,year="2012"
,note="\url{http://software.imdea.org/~gotsman/papers/recycling-esop13-ext.pdf}"
,annotation={
	Separation-logic formulation of RCU uses.
}
}

@unpublished{PaulMcKenney2012RCUUsage
,Author="Paul E. McKenney and Silas Boyd-Wickizer and Jonathan Walpole"
,Title="{RCU} Usage In the Linux Kernel: One Decade Later"
,month="September"
,day="17"
,year="2012"
,url=http://rdrop.com/users/paulmck/techreports/survey.2012.09.17a.pdf
,note="Technical report paulmck.2012.09.17"
,annotation={
	Overview of the first variant of no-CBs CPUs for RCU.
}
}

@unpublished{JonCorbet2012NOCB
,Author="Jon Corbet"
,Title="Relocating RCU callbacks"
,month="October"
,day="31"
,year="2012"
,note="\url{http://lwn.net/Articles/522262/}"
,annotation={
	Overview of the first variant of no-CBs CPUs for RCU.
}
}

@phdthesis{JustinSeyster2012PhD
,author="Justin Seyster"
,title="Runtime Verification of Kernel-Level Concurrency Using Compiler-Based Instrumentation"
,school="Stony Brook University"
,year="2012"
,annotation={
	Looking for data races, including those involving RCU.
	Proposal:
	http://www.fsl.cs.sunysb.edu/docs/jseyster-proposal/redflag.pdf
	Dissertation:
	http://www.fsl.cs.sunysb.edu/docs/jseyster-dissertation/redflag.pdf
}
}

@unpublished{PaulEMcKenney2013RCUUsage
,Author="Paul E. McKenney and Silas Boyd-Wickizer and Jonathan Walpole"
,Title="{RCU} Usage in the {Linux} Kernel: One Decade Later"
,month="February"
,day="24"
,year="2013"
,note="\url{http://rdrop.com/users/paulmck/techreports/RCUUsage.2013.02.24a.pdf}"
,annotation={
	Usage of RCU within the Linux kernel.
}
}

@inproceedings{AlexeyGotsman2013ESOPRCU
,author = {Alexey Gotsman and Noam Rinetzky and Hongseok Yang}
,title = {Verifying concurrent memory reclamation algorithms with grace}
,booktitle = {ESOP'13: European Symposium on Programming}
,year = {2013}
,pages = {249--269}
,publisher = {Springer}
,address = {Rome, Italy}
,annotation={
	http://software.imdea.org/~gotsman/papers/recycling-esop13.pdf
}
}

@unpublished{PaulEMcKenney2013NoTinyPreempt
,Author="Paul E. McKenney"
,Title="Simplifying RCU"
,month="March"
,day="6"
,year="2013"
,note="\url{http://lwn.net/Articles/541037/}"
,annotation={
	Getting rid of TINY_PREEMPT_RCU.
}
}

---

### 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(), DEFINE_STATIC_SRCU(), DEFINE_SRCU_FAST(),
	or DEFINE_STATIC_SRCU_FAST() or at runtime via either
	init_srcu_struct() or init_srcu_struct_fast() and
	cleanup_srcu_struct().	These last three 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

---

### 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_obj(*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_obj(*p);
		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_obj(*p);
		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(); pr