1 /* SPDX-License-Identifier: GPL-2.0+ */
2 /*
3  * RCU segmented callback lists
4  *
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.
8  *
9  * Copyright IBM Corporation, 2017
10  *
11  * Authors: Paul E. McKenney <paulmck@linux.net.ibm.com>
12  */
13 
14 #ifndef __INCLUDE_LINUX_RCU_SEGCBLIST_H
15 #define __INCLUDE_LINUX_RCU_SEGCBLIST_H
16 
17 #include <linux/types.h>
18 #include <linux/atomic.h>
19 
20 /* Simple unsegmented callback lists. */
21 struct rcu_cblist {
22 	struct rcu_head *head;
23 	struct rcu_head **tail;
24 	long len;
25 };
26 
27 #define RCU_CBLIST_INITIALIZER(n) { .head = NULL, .tail = &n.head }
28 
29 /* Complicated segmented callback lists.  ;-) */
30 
31 /*
32  * Index values for segments in rcu_segcblist structure.
33  *
34  * The segments are as follows:
35  *
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.
49  *
50  * Note that RCU_WAIT_TAIL cannot be empty unless RCU_NEXT_READY_TAIL is also
51  * empty.
52  *
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).
59  */
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
65 
66 
67 /*
68  *                     ==NOCB Offloading state machine==
69  *
70  *
71  *  ----------------------------------------------------------------------------
72  *  |                              SEGCBLIST_RCU_CORE                          |
73  *  |                                                                          |
74  *  |  Callbacks processed by rcu_core() from softirqs or local                |
75  *  |  rcuc kthread, without holding nocb_lock.                                |
76  *  ----------------------------------------------------------------------------
77  *                                         |
78  *                                         v
79  *  ----------------------------------------------------------------------------
80  *  |       SEGCBLIST_RCU_CORE | SEGCBLIST_LOCKING | SEGCBLIST_OFFLOADED       |
81  *  |                                                                          |
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  *  ----------------------------------------------------------------------------
86  *                                         |
87  *                                         v
88  *                        -----------------------------------
89  *                        |                                 |
90  *                        v                                 v
91  *  ---------------------------------------  ----------------------------------|
92  *  |        SEGCBLIST_RCU_CORE   |       |  |     SEGCBLIST_RCU_CORE   |      |
93  *  |        SEGCBLIST_LOCKING    |       |  |     SEGCBLIST_LOCKING    |      |
94  *  |        SEGCBLIST_OFFLOADED  |       |  |     SEGCBLIST_OFFLOADED  |      |
95  *  |        SEGCBLIST_KTHREAD_CB         |  |     SEGCBLIST_KTHREAD_GP        |
96  *  |                                     |  |                                 |
97  *  |                                     |  |                                 |
98  *  | CB kthread woke up and              |  | GP kthread woke up and          |
99  *  | acknowledged SEGCBLIST_OFFLOADED.   |  | acknowledged SEGCBLIST_OFFLOADED|
100  *  | Processes callbacks concurrently    |  |                                 |
101  *  | with rcu_core(), holding            |  |                                 |
102  *  | nocb_lock.                          |  |                                 |
103  *  ---------------------------------------  -----------------------------------
104  *                        |                                 |
105  *                        -----------------------------------
106  *                                         |
107  *                                         v
108  *  |--------------------------------------------------------------------------|
109  *  |                           SEGCBLIST_LOCKING    |                         |
110  *  |                           SEGCBLIST_OFFLOADED  |                         |
111  *  |                           SEGCBLIST_KTHREAD_GP |                         |
112  *  |                           SEGCBLIST_KTHREAD_CB                           |
113  *  |                                                                          |
114  *  |   Kthreads handle callbacks holding nocb_lock, local rcu_core() stops    |
115  *  |   handling callbacks. Enable bypass queueing.                            |
116  *  ----------------------------------------------------------------------------
117  */
118 
119 
120 
121 /*
122  *                       ==NOCB De-Offloading state machine==
123  *
124  *
125  *  |--------------------------------------------------------------------------|
126  *  |                           SEGCBLIST_LOCKING    |                         |
127  *  |                           SEGCBLIST_OFFLOADED  |                         |
128  *  |                           SEGCBLIST_KTHREAD_CB |                         |
129  *  |                           SEGCBLIST_KTHREAD_GP                           |
130  *  |                                                                          |
131  *  |   CB/GP kthreads handle callbacks holding nocb_lock, local rcu_core()    |
132  *  |   ignores callbacks. Bypass enqueue is enabled.                          |
133  *  ----------------------------------------------------------------------------
134  *                                      |
135  *                                      v
136  *  |--------------------------------------------------------------------------|
137  *  |                           SEGCBLIST_RCU_CORE   |                         |
138  *  |                           SEGCBLIST_LOCKING    |                         |
139  *  |                           SEGCBLIST_OFFLOADED  |                         |
140  *  |                           SEGCBLIST_KTHREAD_CB |                         |
141  *  |                           SEGCBLIST_KTHREAD_GP                           |
142  *  |                                                                          |
143  *  |   CB/GP kthreads handle callbacks holding nocb_lock, local rcu_core()    |
144  *  |   handles callbacks concurrently. Bypass enqueue is enabled.             |
145  *  |   Invoke RCU core so we make sure not to preempt it in the middle with   |
146  *  |   leaving some urgent work unattended within a jiffy.                    |
147  *  ----------------------------------------------------------------------------
148  *                                      |
149  *                                      v
150  *  |--------------------------------------------------------------------------|
151  *  |                           SEGCBLIST_RCU_CORE   |                         |
152  *  |                           SEGCBLIST_LOCKING    |                         |
153  *  |                           SEGCBLIST_KTHREAD_CB |                         |
154  *  |                           SEGCBLIST_KTHREAD_GP                           |
155  *  |                                                                          |
156  *  |   CB/GP kthreads and local rcu_core() handle callbacks concurrently      |
157  *  |   holding nocb_lock. Wake up CB and GP kthreads if necessary. Disable    |
158  *  |   bypass enqueue.                                                        |
159  *  ----------------------------------------------------------------------------
160  *                                      |
161  *                                      v
162  *                     -----------------------------------
163  *                     |                                 |
164  *                     v                                 v
165  *  ---------------------------------------------------------------------------|
166  *  |                                     |                                    |
167  *  |        SEGCBLIST_RCU_CORE |         |       SEGCBLIST_RCU_CORE |         |
168  *  |        SEGCBLIST_LOCKING  |         |       SEGCBLIST_LOCKING  |         |
169  *  |        SEGCBLIST_KTHREAD_CB         |       SEGCBLIST_KTHREAD_GP         |
170  *  |                                     |                                    |
171  *  | GP kthread woke up and              |   CB kthread woke up and           |
172  *  | acknowledged the fact that          |   acknowledged the fact that       |
173  *  | SEGCBLIST_OFFLOADED got cleared.    |   SEGCBLIST_OFFLOADED got cleared. |
174  *  |                                     |   The CB kthread goes to sleep     |
175  *  | The callbacks from the target CPU   |   until it ever gets re-offloaded. |
176  *  | will be ignored from the GP kthread |                                    |
177  *  | loop.                               |                                    |
178  *  ----------------------------------------------------------------------------
179  *                      |                                 |
180  *                      -----------------------------------
181  *                                      |
182  *                                      v
183  *  ----------------------------------------------------------------------------
184  *  |                SEGCBLIST_RCU_CORE | SEGCBLIST_LOCKING                    |
185  *  |                                                                          |
186  *  | Callbacks processed by rcu_core() from softirqs or local                 |
187  *  | rcuc kthread, while holding nocb_lock. Forbid nocb_timer to be armed.    |
188  *  | Flush pending nocb_timer. Flush nocb bypass callbacks.                   |
189  *  ----------------------------------------------------------------------------
190  *                                      |
191  *                                      v
192  *  ----------------------------------------------------------------------------
193  *  |                         SEGCBLIST_RCU_CORE                               |
194  *  |                                                                          |
195  *  |  Callbacks processed by rcu_core() from softirqs or local                |
196  *  |  rcuc kthread, without holding nocb_lock.                                |
197  *  ----------------------------------------------------------------------------
198  */
199 #define SEGCBLIST_ENABLED	BIT(0)
200 #define SEGCBLIST_RCU_CORE	BIT(1)
201 #define SEGCBLIST_LOCKING	BIT(2)
202 #define SEGCBLIST_KTHREAD_CB	BIT(3)
203 #define SEGCBLIST_KTHREAD_GP	BIT(4)
204 #define SEGCBLIST_OFFLOADED	BIT(5)
205 
206 struct rcu_segcblist {
207 	struct rcu_head *head;
208 	struct rcu_head **tails[RCU_CBLIST_NSEGS];
209 	unsigned long gp_seq[RCU_CBLIST_NSEGS];
210 #ifdef CONFIG_RCU_NOCB_CPU
211 	atomic_long_t len;
212 #else
213 	long len;
214 #endif
215 	long seglen[RCU_CBLIST_NSEGS];
216 	u8 flags;
217 };
218 
219 #define RCU_SEGCBLIST_INITIALIZER(n) \
220 { \
221 	.head = NULL, \
222 	.tails[RCU_DONE_TAIL] = &n.head, \
223 	.tails[RCU_WAIT_TAIL] = &n.head, \
224 	.tails[RCU_NEXT_READY_TAIL] = &n.head, \
225 	.tails[RCU_NEXT_TAIL] = &n.head, \
226 }
227 
228 #endif /* __INCLUDE_LINUX_RCU_SEGCBLIST_H */
229