Commit | Line | Data |
---|---|---|
eb7935e4 | 1 | // SPDX-License-Identifier: GPL-2.0+ |
98059b98 PM |
2 | /* |
3 | * RCU segmented callback lists, function definitions | |
4 | * | |
98059b98 PM |
5 | * Copyright IBM Corporation, 2017 |
6 | * | |
eb7935e4 | 7 | * Authors: Paul E. McKenney <paulmck@linux.ibm.com> |
98059b98 PM |
8 | */ |
9 | ||
10 | #include <linux/types.h> | |
11 | #include <linux/kernel.h> | |
12 | #include <linux/interrupt.h> | |
56628a7f | 13 | #include <linux/rcupdate.h> |
98059b98 PM |
14 | |
15 | #include "rcu_segcblist.h" | |
16 | ||
17 | /* Initialize simple callback list. */ | |
18 | void rcu_cblist_init(struct rcu_cblist *rclp) | |
19 | { | |
20 | rclp->head = NULL; | |
21 | rclp->tail = &rclp->head; | |
22 | rclp->len = 0; | |
23 | rclp->len_lazy = 0; | |
24 | } | |
25 | ||
98059b98 PM |
26 | /* |
27 | * Dequeue the oldest rcu_head structure from the specified callback | |
28 | * list. This function assumes that the callback is non-lazy, but | |
29 | * the caller can later invoke rcu_cblist_dequeued_lazy() if it | |
30 | * finds otherwise (and if it cares about laziness). This allows | |
31 | * different users to have different ways of determining laziness. | |
32 | */ | |
33 | struct rcu_head *rcu_cblist_dequeue(struct rcu_cblist *rclp) | |
34 | { | |
35 | struct rcu_head *rhp; | |
36 | ||
37 | rhp = rclp->head; | |
38 | if (!rhp) | |
39 | return NULL; | |
40 | rclp->len--; | |
41 | rclp->head = rhp->next; | |
42 | if (!rclp->head) | |
43 | rclp->tail = &rclp->head; | |
44 | return rhp; | |
45 | } | |
46 | ||
47 | /* | |
48 | * Initialize an rcu_segcblist structure. | |
49 | */ | |
50 | void rcu_segcblist_init(struct rcu_segcblist *rsclp) | |
51 | { | |
52 | int i; | |
53 | ||
54 | BUILD_BUG_ON(RCU_NEXT_TAIL + 1 != ARRAY_SIZE(rsclp->gp_seq)); | |
55 | BUILD_BUG_ON(ARRAY_SIZE(rsclp->tails) != ARRAY_SIZE(rsclp->gp_seq)); | |
56 | rsclp->head = NULL; | |
57 | for (i = 0; i < RCU_CBLIST_NSEGS; i++) | |
58 | rsclp->tails[i] = &rsclp->head; | |
59 | rsclp->len = 0; | |
60 | rsclp->len_lazy = 0; | |
61 | } | |
62 | ||
63 | /* | |
64 | * Disable the specified rcu_segcblist structure, so that callbacks can | |
65 | * no longer be posted to it. This structure must be empty. | |
66 | */ | |
67 | void rcu_segcblist_disable(struct rcu_segcblist *rsclp) | |
68 | { | |
69 | WARN_ON_ONCE(!rcu_segcblist_empty(rsclp)); | |
70 | WARN_ON_ONCE(rcu_segcblist_n_cbs(rsclp)); | |
71 | WARN_ON_ONCE(rcu_segcblist_n_lazy_cbs(rsclp)); | |
72 | rsclp->tails[RCU_NEXT_TAIL] = NULL; | |
73 | } | |
74 | ||
98059b98 PM |
75 | /* |
76 | * Does the specified rcu_segcblist structure contain callbacks that | |
77 | * are ready to be invoked? | |
78 | */ | |
79 | bool rcu_segcblist_ready_cbs(struct rcu_segcblist *rsclp) | |
80 | { | |
81 | return rcu_segcblist_is_enabled(rsclp) && | |
82 | &rsclp->head != rsclp->tails[RCU_DONE_TAIL]; | |
83 | } | |
84 | ||
85 | /* | |
86 | * Does the specified rcu_segcblist structure contain callbacks that | |
87 | * are still pending, that is, not yet ready to be invoked? | |
88 | */ | |
89 | bool rcu_segcblist_pend_cbs(struct rcu_segcblist *rsclp) | |
90 | { | |
91 | return rcu_segcblist_is_enabled(rsclp) && | |
92 | !rcu_segcblist_restempty(rsclp, RCU_DONE_TAIL); | |
93 | } | |
94 | ||
98059b98 PM |
95 | /* |
96 | * Return a pointer to the first callback in the specified rcu_segcblist | |
97 | * structure. This is useful for diagnostics. | |
98 | */ | |
99 | struct rcu_head *rcu_segcblist_first_cb(struct rcu_segcblist *rsclp) | |
100 | { | |
101 | if (rcu_segcblist_is_enabled(rsclp)) | |
102 | return rsclp->head; | |
103 | return NULL; | |
104 | } | |
105 | ||
106 | /* | |
107 | * Return a pointer to the first pending callback in the specified | |
108 | * rcu_segcblist structure. This is useful just after posting a given | |
109 | * callback -- if that callback is the first pending callback, then | |
110 | * you cannot rely on someone else having already started up the required | |
111 | * grace period. | |
112 | */ | |
113 | struct rcu_head *rcu_segcblist_first_pend_cb(struct rcu_segcblist *rsclp) | |
114 | { | |
115 | if (rcu_segcblist_is_enabled(rsclp)) | |
116 | return *rsclp->tails[RCU_DONE_TAIL]; | |
117 | return NULL; | |
118 | } | |
119 | ||
98059b98 PM |
120 | /* |
121 | * Enqueue the specified callback onto the specified rcu_segcblist | |
122 | * structure, updating accounting as needed. Note that the ->len | |
123 | * field may be accessed locklessly, hence the WRITE_ONCE(). | |
124 | * The ->len field is used by rcu_barrier() and friends to determine | |
125 | * if it must post a callback on this structure, and it is OK | |
126 | * for rcu_barrier() to sometimes post callbacks needlessly, but | |
127 | * absolutely not OK for it to ever miss posting a callback. | |
128 | */ | |
129 | void rcu_segcblist_enqueue(struct rcu_segcblist *rsclp, | |
130 | struct rcu_head *rhp, bool lazy) | |
131 | { | |
132 | WRITE_ONCE(rsclp->len, rsclp->len + 1); /* ->len sampled locklessly. */ | |
133 | if (lazy) | |
134 | rsclp->len_lazy++; | |
135 | smp_mb(); /* Ensure counts are updated before callback is enqueued. */ | |
136 | rhp->next = NULL; | |
137 | *rsclp->tails[RCU_NEXT_TAIL] = rhp; | |
138 | rsclp->tails[RCU_NEXT_TAIL] = &rhp->next; | |
139 | } | |
140 | ||
141 | /* | |
142 | * Entrain the specified callback onto the specified rcu_segcblist at | |
143 | * the end of the last non-empty segment. If the entire rcu_segcblist | |
144 | * is empty, make no change, but return false. | |
145 | * | |
146 | * This is intended for use by rcu_barrier()-like primitives, -not- | |
147 | * for normal grace-period use. IMPORTANT: The callback you enqueue | |
148 | * will wait for all prior callbacks, NOT necessarily for a grace | |
149 | * period. You have been warned. | |
150 | */ | |
151 | bool rcu_segcblist_entrain(struct rcu_segcblist *rsclp, | |
152 | struct rcu_head *rhp, bool lazy) | |
153 | { | |
154 | int i; | |
155 | ||
156 | if (rcu_segcblist_n_cbs(rsclp) == 0) | |
157 | return false; | |
158 | WRITE_ONCE(rsclp->len, rsclp->len + 1); | |
159 | if (lazy) | |
160 | rsclp->len_lazy++; | |
161 | smp_mb(); /* Ensure counts are updated before callback is entrained. */ | |
162 | rhp->next = NULL; | |
163 | for (i = RCU_NEXT_TAIL; i > RCU_DONE_TAIL; i--) | |
164 | if (rsclp->tails[i] != rsclp->tails[i - 1]) | |
165 | break; | |
166 | *rsclp->tails[i] = rhp; | |
167 | for (; i <= RCU_NEXT_TAIL; i++) | |
168 | rsclp->tails[i] = &rhp->next; | |
169 | return true; | |
170 | } | |
171 | ||
172 | /* | |
173 | * Extract only the counts from the specified rcu_segcblist structure, | |
174 | * and place them in the specified rcu_cblist structure. This function | |
175 | * supports both callback orphaning and invocation, hence the separation | |
176 | * of counts and callbacks. (Callbacks ready for invocation must be | |
177 | * orphaned and adopted separately from pending callbacks, but counts | |
178 | * apply to all callbacks. Locking must be used to make sure that | |
179 | * both orphaned-callbacks lists are consistent.) | |
180 | */ | |
181 | void rcu_segcblist_extract_count(struct rcu_segcblist *rsclp, | |
182 | struct rcu_cblist *rclp) | |
183 | { | |
184 | rclp->len_lazy += rsclp->len_lazy; | |
185 | rclp->len += rsclp->len; | |
186 | rsclp->len_lazy = 0; | |
187 | WRITE_ONCE(rsclp->len, 0); /* ->len sampled locklessly. */ | |
188 | } | |
189 | ||
190 | /* | |
191 | * Extract only those callbacks ready to be invoked from the specified | |
192 | * rcu_segcblist structure and place them in the specified rcu_cblist | |
193 | * structure. | |
194 | */ | |
195 | void rcu_segcblist_extract_done_cbs(struct rcu_segcblist *rsclp, | |
196 | struct rcu_cblist *rclp) | |
197 | { | |
198 | int i; | |
199 | ||
200 | if (!rcu_segcblist_ready_cbs(rsclp)) | |
201 | return; /* Nothing to do. */ | |
202 | *rclp->tail = rsclp->head; | |
203 | rsclp->head = *rsclp->tails[RCU_DONE_TAIL]; | |
204 | *rsclp->tails[RCU_DONE_TAIL] = NULL; | |
205 | rclp->tail = rsclp->tails[RCU_DONE_TAIL]; | |
206 | for (i = RCU_CBLIST_NSEGS - 1; i >= RCU_DONE_TAIL; i--) | |
207 | if (rsclp->tails[i] == rsclp->tails[RCU_DONE_TAIL]) | |
208 | rsclp->tails[i] = &rsclp->head; | |
209 | } | |
210 | ||
211 | /* | |
212 | * Extract only those callbacks still pending (not yet ready to be | |
213 | * invoked) from the specified rcu_segcblist structure and place them in | |
214 | * the specified rcu_cblist structure. Note that this loses information | |
215 | * about any callbacks that might have been partway done waiting for | |
216 | * their grace period. Too bad! They will have to start over. | |
217 | */ | |
218 | void rcu_segcblist_extract_pend_cbs(struct rcu_segcblist *rsclp, | |
219 | struct rcu_cblist *rclp) | |
220 | { | |
221 | int i; | |
222 | ||
223 | if (!rcu_segcblist_pend_cbs(rsclp)) | |
224 | return; /* Nothing to do. */ | |
225 | *rclp->tail = *rsclp->tails[RCU_DONE_TAIL]; | |
226 | rclp->tail = rsclp->tails[RCU_NEXT_TAIL]; | |
227 | *rsclp->tails[RCU_DONE_TAIL] = NULL; | |
228 | for (i = RCU_DONE_TAIL + 1; i < RCU_CBLIST_NSEGS; i++) | |
229 | rsclp->tails[i] = rsclp->tails[RCU_DONE_TAIL]; | |
230 | } | |
231 | ||
232 | /* | |
233 | * Insert counts from the specified rcu_cblist structure in the | |
234 | * specified rcu_segcblist structure. | |
235 | */ | |
236 | void rcu_segcblist_insert_count(struct rcu_segcblist *rsclp, | |
237 | struct rcu_cblist *rclp) | |
238 | { | |
239 | rsclp->len_lazy += rclp->len_lazy; | |
240 | /* ->len sampled locklessly. */ | |
241 | WRITE_ONCE(rsclp->len, rsclp->len + rclp->len); | |
242 | rclp->len_lazy = 0; | |
243 | rclp->len = 0; | |
244 | } | |
245 | ||
246 | /* | |
247 | * Move callbacks from the specified rcu_cblist to the beginning of the | |
248 | * done-callbacks segment of the specified rcu_segcblist. | |
249 | */ | |
250 | void rcu_segcblist_insert_done_cbs(struct rcu_segcblist *rsclp, | |
251 | struct rcu_cblist *rclp) | |
252 | { | |
253 | int i; | |
254 | ||
255 | if (!rclp->head) | |
256 | return; /* No callbacks to move. */ | |
257 | *rclp->tail = rsclp->head; | |
258 | rsclp->head = rclp->head; | |
259 | for (i = RCU_DONE_TAIL; i < RCU_CBLIST_NSEGS; i++) | |
260 | if (&rsclp->head == rsclp->tails[i]) | |
261 | rsclp->tails[i] = rclp->tail; | |
262 | else | |
263 | break; | |
264 | rclp->head = NULL; | |
265 | rclp->tail = &rclp->head; | |
266 | } | |
267 | ||
268 | /* | |
269 | * Move callbacks from the specified rcu_cblist to the end of the | |
270 | * new-callbacks segment of the specified rcu_segcblist. | |
271 | */ | |
272 | void rcu_segcblist_insert_pend_cbs(struct rcu_segcblist *rsclp, | |
273 | struct rcu_cblist *rclp) | |
274 | { | |
275 | if (!rclp->head) | |
276 | return; /* Nothing to do. */ | |
277 | *rsclp->tails[RCU_NEXT_TAIL] = rclp->head; | |
278 | rsclp->tails[RCU_NEXT_TAIL] = rclp->tail; | |
279 | rclp->head = NULL; | |
280 | rclp->tail = &rclp->head; | |
281 | } | |
282 | ||
283 | /* | |
284 | * Advance the callbacks in the specified rcu_segcblist structure based | |
285 | * on the current value passed in for the grace-period counter. | |
286 | */ | |
287 | void rcu_segcblist_advance(struct rcu_segcblist *rsclp, unsigned long seq) | |
288 | { | |
289 | int i, j; | |
290 | ||
291 | WARN_ON_ONCE(!rcu_segcblist_is_enabled(rsclp)); | |
292 | if (rcu_segcblist_restempty(rsclp, RCU_DONE_TAIL)) | |
293 | return; | |
294 | ||
295 | /* | |
296 | * Find all callbacks whose ->gp_seq numbers indicate that they | |
297 | * are ready to invoke, and put them into the RCU_DONE_TAIL segment. | |
298 | */ | |
299 | for (i = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++) { | |
300 | if (ULONG_CMP_LT(seq, rsclp->gp_seq[i])) | |
301 | break; | |
302 | rsclp->tails[RCU_DONE_TAIL] = rsclp->tails[i]; | |
303 | } | |
304 | ||
305 | /* If no callbacks moved, nothing more need be done. */ | |
306 | if (i == RCU_WAIT_TAIL) | |
307 | return; | |
308 | ||
309 | /* Clean up tail pointers that might have been misordered above. */ | |
310 | for (j = RCU_WAIT_TAIL; j < i; j++) | |
311 | rsclp->tails[j] = rsclp->tails[RCU_DONE_TAIL]; | |
312 | ||
313 | /* | |
314 | * Callbacks moved, so clean up the misordered ->tails[] pointers | |
315 | * that now point into the middle of the list of ready-to-invoke | |
316 | * callbacks. The overall effect is to copy down the later pointers | |
317 | * into the gap that was created by the now-ready segments. | |
318 | */ | |
319 | for (j = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++, j++) { | |
320 | if (rsclp->tails[j] == rsclp->tails[RCU_NEXT_TAIL]) | |
321 | break; /* No more callbacks. */ | |
322 | rsclp->tails[j] = rsclp->tails[i]; | |
323 | rsclp->gp_seq[j] = rsclp->gp_seq[i]; | |
324 | } | |
325 | } | |
326 | ||
327 | /* | |
328 | * "Accelerate" callbacks based on more-accurate grace-period information. | |
329 | * The reason for this is that RCU does not synchronize the beginnings and | |
330 | * ends of grace periods, and that callbacks are posted locally. This in | |
331 | * turn means that the callbacks must be labelled conservatively early | |
332 | * on, as getting exact information would degrade both performance and | |
333 | * scalability. When more accurate grace-period information becomes | |
334 | * available, previously posted callbacks can be "accelerated", marking | |
335 | * them to complete at the end of the earlier grace period. | |
336 | * | |
337 | * This function operates on an rcu_segcblist structure, and also the | |
338 | * grace-period sequence number seq at which new callbacks would become | |
339 | * ready to invoke. Returns true if there are callbacks that won't be | |
340 | * ready to invoke until seq, false otherwise. | |
341 | */ | |
342 | bool rcu_segcblist_accelerate(struct rcu_segcblist *rsclp, unsigned long seq) | |
343 | { | |
344 | int i; | |
345 | ||
346 | WARN_ON_ONCE(!rcu_segcblist_is_enabled(rsclp)); | |
347 | if (rcu_segcblist_restempty(rsclp, RCU_DONE_TAIL)) | |
348 | return false; | |
349 | ||
350 | /* | |
351 | * Find the segment preceding the oldest segment of callbacks | |
352 | * whose ->gp_seq[] completion is at or after that passed in via | |
353 | * "seq", skipping any empty segments. This oldest segment, along | |
354 | * with any later segments, can be merged in with any newly arrived | |
355 | * callbacks in the RCU_NEXT_TAIL segment, and assigned "seq" | |
356 | * as their ->gp_seq[] grace-period completion sequence number. | |
357 | */ | |
358 | for (i = RCU_NEXT_READY_TAIL; i > RCU_DONE_TAIL; i--) | |
359 | if (rsclp->tails[i] != rsclp->tails[i - 1] && | |
360 | ULONG_CMP_LT(rsclp->gp_seq[i], seq)) | |
361 | break; | |
362 | ||
363 | /* | |
364 | * If all the segments contain callbacks that correspond to | |
365 | * earlier grace-period sequence numbers than "seq", leave. | |
366 | * Assuming that the rcu_segcblist structure has enough | |
367 | * segments in its arrays, this can only happen if some of | |
368 | * the non-done segments contain callbacks that really are | |
369 | * ready to invoke. This situation will get straightened | |
370 | * out by the next call to rcu_segcblist_advance(). | |
371 | * | |
372 | * Also advance to the oldest segment of callbacks whose | |
373 | * ->gp_seq[] completion is at or after that passed in via "seq", | |
374 | * skipping any empty segments. | |
375 | */ | |
376 | if (++i >= RCU_NEXT_TAIL) | |
377 | return false; | |
378 | ||
379 | /* | |
380 | * Merge all later callbacks, including newly arrived callbacks, | |
381 | * into the segment located by the for-loop above. Assign "seq" | |
382 | * as the ->gp_seq[] value in order to correctly handle the case | |
383 | * where there were no pending callbacks in the rcu_segcblist | |
384 | * structure other than in the RCU_NEXT_TAIL segment. | |
385 | */ | |
386 | for (; i < RCU_NEXT_TAIL; i++) { | |
387 | rsclp->tails[i] = rsclp->tails[RCU_NEXT_TAIL]; | |
388 | rsclp->gp_seq[i] = seq; | |
389 | } | |
390 | return true; | |
391 | } | |
392 | ||
f2dbe4a5 PM |
393 | /* |
394 | * Merge the source rcu_segcblist structure into the destination | |
395 | * rcu_segcblist structure, then initialize the source. Any pending | |
396 | * callbacks from the source get to start over. It is best to | |
397 | * advance and accelerate both the destination and the source | |
398 | * before merging. | |
399 | */ | |
400 | void rcu_segcblist_merge(struct rcu_segcblist *dst_rsclp, | |
401 | struct rcu_segcblist *src_rsclp) | |
402 | { | |
403 | struct rcu_cblist donecbs; | |
404 | struct rcu_cblist pendcbs; | |
405 | ||
406 | rcu_cblist_init(&donecbs); | |
407 | rcu_cblist_init(&pendcbs); | |
408 | rcu_segcblist_extract_count(src_rsclp, &donecbs); | |
409 | rcu_segcblist_extract_done_cbs(src_rsclp, &donecbs); | |
410 | rcu_segcblist_extract_pend_cbs(src_rsclp, &pendcbs); | |
411 | rcu_segcblist_insert_count(dst_rsclp, &donecbs); | |
412 | rcu_segcblist_insert_done_cbs(dst_rsclp, &donecbs); | |
413 | rcu_segcblist_insert_pend_cbs(dst_rsclp, &pendcbs); | |
414 | rcu_segcblist_init(src_rsclp); | |
415 | } |