1 /* SPDX-License-Identifier: GPL-2.0+ */
3 * RCU segmented callback lists
5 * This seemingly RCU-private file must be available to SRCU users
6 * because the size of the TREE SRCU srcu_struct structure depends
7 * on these definitions.
9 * Copyright IBM Corporation, 2017
11 * Authors: Paul E. McKenney <paulmck@linux.net.ibm.com>
14 #ifndef __INCLUDE_LINUX_RCU_SEGCBLIST_H
15 #define __INCLUDE_LINUX_RCU_SEGCBLIST_H
17 #include <linux/types.h>
18 #include <linux/atomic.h>
20 /* Simple unsegmented callback lists. */
22 struct rcu_head *head;
23 struct rcu_head **tail;
27 #define RCU_CBLIST_INITIALIZER(n) { .head = NULL, .tail = &n.head }
29 /* Complicated segmented callback lists. ;-) */
32 * Index values for segments in rcu_segcblist structure.
34 * The segments are as follows:
36 * [head, *tails[RCU_DONE_TAIL]):
37 * Callbacks whose grace period has elapsed, and thus can be invoked.
38 * [*tails[RCU_DONE_TAIL], *tails[RCU_WAIT_TAIL]):
39 * Callbacks waiting for the current GP from the current CPU's viewpoint.
40 * [*tails[RCU_WAIT_TAIL], *tails[RCU_NEXT_READY_TAIL]):
41 * Callbacks that arrived before the next GP started, again from
42 * the current CPU's viewpoint. These can be handled by the next GP.
43 * [*tails[RCU_NEXT_READY_TAIL], *tails[RCU_NEXT_TAIL]):
44 * Callbacks that might have arrived after the next GP started.
45 * There is some uncertainty as to when a given GP starts and
46 * ends, but a CPU knows the exact times if it is the one starting
47 * or ending the GP. Other CPUs know that the previous GP ends
48 * before the next one starts.
50 * Note that RCU_WAIT_TAIL cannot be empty unless RCU_NEXT_READY_TAIL is also
53 * The ->gp_seq[] array contains the grace-period number at which the
54 * corresponding segment of callbacks will be ready to invoke. A given
55 * element of this array is meaningful only when the corresponding segment
56 * is non-empty, and it is never valid for RCU_DONE_TAIL (whose callbacks
57 * are already ready to invoke) or for RCU_NEXT_TAIL (whose callbacks have
58 * not yet been assigned a grace-period number).
60 #define RCU_DONE_TAIL 0 /* Also RCU_WAIT head. */
61 #define RCU_WAIT_TAIL 1 /* Also RCU_NEXT_READY head. */
62 #define RCU_NEXT_READY_TAIL 2 /* Also RCU_NEXT head. */
63 #define RCU_NEXT_TAIL 3
64 #define RCU_CBLIST_NSEGS 4
68 * ==NOCB Offloading state machine==
71 * ----------------------------------------------------------------------------
72 * | SEGCBLIST_SOFTIRQ_ONLY |
74 * | Callbacks processed by rcu_core() from softirqs or local |
75 * | rcuc kthread, without holding nocb_lock. |
76 * ----------------------------------------------------------------------------
79 * ----------------------------------------------------------------------------
80 * | SEGCBLIST_OFFLOADED |
82 * | Callbacks processed by rcu_core() from softirqs or local |
83 * | rcuc kthread, while holding nocb_lock. Waking up CB and GP kthreads, |
84 * | allowing nocb_timer to be armed. |
85 * ----------------------------------------------------------------------------
88 * -----------------------------------
91 * --------------------------------------- ----------------------------------|
92 * | SEGCBLIST_OFFLOADED | | | SEGCBLIST_OFFLOADED | |
93 * | SEGCBLIST_KTHREAD_CB | | SEGCBLIST_KTHREAD_GP |
96 * | CB kthread woke up and | | GP kthread woke up and |
97 * | acknowledged SEGCBLIST_OFFLOADED. | | acknowledged SEGCBLIST_OFFLOADED|
98 * | Processes callbacks concurrently | | |
99 * | with rcu_core(), holding | | |
101 * --------------------------------------- -----------------------------------
103 * -----------------------------------
106 * |--------------------------------------------------------------------------|
107 * | SEGCBLIST_OFFLOADED | |
108 * | SEGCBLIST_KTHREAD_CB | |
109 * | SEGCBLIST_KTHREAD_GP |
111 * | Kthreads handle callbacks holding nocb_lock, local rcu_core() stops |
112 * | handling callbacks. |
113 * ----------------------------------------------------------------------------
119 * ==NOCB De-Offloading state machine==
122 * |--------------------------------------------------------------------------|
123 * | SEGCBLIST_OFFLOADED | |
124 * | SEGCBLIST_KTHREAD_CB | |
125 * | SEGCBLIST_KTHREAD_GP |
127 * | CB/GP kthreads handle callbacks holding nocb_lock, local rcu_core() |
128 * | ignores callbacks. |
129 * ----------------------------------------------------------------------------
132 * |--------------------------------------------------------------------------|
133 * | SEGCBLIST_KTHREAD_CB | |
134 * | SEGCBLIST_KTHREAD_GP |
136 * | CB/GP kthreads and local rcu_core() handle callbacks concurrently |
137 * | holding nocb_lock. Wake up CB and GP kthreads if necessary. |
138 * ----------------------------------------------------------------------------
141 * -----------------------------------
144 * ---------------------------------------------------------------------------|
146 * | SEGCBLIST_KTHREAD_CB | SEGCBLIST_KTHREAD_GP |
148 * | GP kthread woke up and | CB kthread woke up and |
149 * | acknowledged the fact that | acknowledged the fact that |
150 * | SEGCBLIST_OFFLOADED got cleared. | SEGCBLIST_OFFLOADED got cleared. |
151 * | | The CB kthread goes to sleep |
152 * | The callbacks from the target CPU | until it ever gets re-offloaded. |
153 * | will be ignored from the GP kthread | |
155 * ----------------------------------------------------------------------------
157 * -----------------------------------
160 * ----------------------------------------------------------------------------
163 * | Callbacks processed by rcu_core() from softirqs or local |
164 * | rcuc kthread, while holding nocb_lock. Forbid nocb_timer to be armed. |
165 * | Flush pending nocb_timer. Flush nocb bypass callbacks. |
166 * ----------------------------------------------------------------------------
169 * ----------------------------------------------------------------------------
170 * | SEGCBLIST_SOFTIRQ_ONLY |
172 * | Callbacks processed by rcu_core() from softirqs or local |
173 * | rcuc kthread, without holding nocb_lock. |
174 * ----------------------------------------------------------------------------
176 #define SEGCBLIST_ENABLED BIT(0)
177 #define SEGCBLIST_SOFTIRQ_ONLY BIT(1)
178 #define SEGCBLIST_KTHREAD_CB BIT(2)
179 #define SEGCBLIST_KTHREAD_GP BIT(3)
180 #define SEGCBLIST_OFFLOADED BIT(4)
182 struct rcu_segcblist {
183 struct rcu_head *head;
184 struct rcu_head **tails[RCU_CBLIST_NSEGS];
185 unsigned long gp_seq[RCU_CBLIST_NSEGS];
186 #ifdef CONFIG_RCU_NOCB_CPU
191 long seglen[RCU_CBLIST_NSEGS];
195 #define RCU_SEGCBLIST_INITIALIZER(n) \
198 .tails[RCU_DONE_TAIL] = &n.head, \
199 .tails[RCU_WAIT_TAIL] = &n.head, \
200 .tails[RCU_NEXT_READY_TAIL] = &n.head, \
201 .tails[RCU_NEXT_TAIL] = &n.head, \
204 #endif /* __INCLUDE_LINUX_RCU_SEGCBLIST_H */