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