aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorIngo Molnar <mingo@kernel.org>2017-05-03 02:00:14 -0400
committerIngo Molnar <mingo@kernel.org>2017-05-03 02:00:14 -0400
commit20652ed6e44f4963281b65209b917be86ac6765b (patch)
treeb9a71f3445203169c7deda78e8ea971f4cba01c0
parentb5fe223a4bd0217a657ff084e48752c367a8a55f (diff)
parent933dfbd7c437bbbf65caae785dfa105fbfaa8485 (diff)
Merge branch 'for-mingo' of git://git.kernel.org/pub/scm/linux/kernel/git/paulmck/linux-rcu into core/rcu
Pull RCU fixes from Paul E. McKenney: "This series adds a pair of commits that move function definitions from include/linux/rcu_segcblist.h to new kernel/rcu/rcu_segcblist.h and kernel/rcu/rcu_segcblist.c files, thus greatly decreasing the size of the externally visible include/linux/rcu_segcblist.h file." Signed-off-by: Ingo Molnar <mingo@kernel.org>
-rw-r--r--include/linux/rcu_segcblist.h628
-rw-r--r--init/Kconfig3
-rw-r--r--kernel/rcu/Makefile1
-rw-r--r--kernel/rcu/rcu_segcblist.c505
-rw-r--r--kernel/rcu/rcu_segcblist.h164
-rw-r--r--kernel/rcu/srcutiny.c1
-rw-r--r--kernel/rcu/srcutree.c1
-rw-r--r--kernel/rcu/tree.c18
-rw-r--r--kernel/rcu/tree.h3
-rw-r--r--kernel/rcu/tree_plugin.h8
-rw-r--r--kernel/rcu/tree_trace.c4
11 files changed, 694 insertions, 642 deletions
diff --git a/include/linux/rcu_segcblist.h b/include/linux/rcu_segcblist.h
index ced8f313fd05..ba4d2621d9ca 100644
--- a/include/linux/rcu_segcblist.h
+++ b/include/linux/rcu_segcblist.h
@@ -20,8 +20,8 @@
20 * Authors: Paul E. McKenney <paulmck@linux.vnet.ibm.com> 20 * Authors: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
21 */ 21 */
22 22
23#ifndef __KERNEL_RCU_SEGCBLIST_H 23#ifndef __INCLUDE_LINUX_RCU_SEGCBLIST_H
24#define __KERNEL_RCU_SEGCBLIST_H 24#define __INCLUDE_LINUX_RCU_SEGCBLIST_H
25 25
26/* Simple unsegmented callback lists. */ 26/* Simple unsegmented callback lists. */
27struct rcu_cblist { 27struct rcu_cblist {
@@ -33,102 +33,6 @@ struct rcu_cblist {
33 33
34#define RCU_CBLIST_INITIALIZER(n) { .head = NULL, .tail = &n.head } 34#define RCU_CBLIST_INITIALIZER(n) { .head = NULL, .tail = &n.head }
35 35
36/* Initialize simple callback list. */
37static inline void rcu_cblist_init(struct rcu_cblist *rclp)
38{
39 rclp->head = NULL;
40 rclp->tail = &rclp->head;
41 rclp->len = 0;
42 rclp->len_lazy = 0;
43}
44
45/* Is simple callback list empty? */
46static inline bool rcu_cblist_empty(struct rcu_cblist *rclp)
47{
48 return !rclp->head;
49}
50
51/* Return number of callbacks in simple callback list. */
52static inline long rcu_cblist_n_cbs(struct rcu_cblist *rclp)
53{
54 return rclp->len;
55}
56
57/* Return number of lazy callbacks in simple callback list. */
58static inline long rcu_cblist_n_lazy_cbs(struct rcu_cblist *rclp)
59{
60 return rclp->len_lazy;
61}
62
63/*
64 * Debug function to actually count the number of callbacks.
65 * If the number exceeds the limit specified, return -1.
66 */
67static inline long rcu_cblist_count_cbs(struct rcu_cblist *rclp, long lim)
68{
69 int cnt = 0;
70 struct rcu_head **rhpp = &rclp->head;
71
72 for (;;) {
73 if (!*rhpp)
74 return cnt;
75 if (++cnt > lim)
76 return -1;
77 rhpp = &(*rhpp)->next;
78 }
79}
80
81/*
82 * Dequeue the oldest rcu_head structure from the specified callback
83 * list. This function assumes that the callback is non-lazy, but
84 * the caller can later invoke rcu_cblist_dequeued_lazy() if it
85 * finds otherwise (and if it cares about laziness). This allows
86 * different users to have different ways of determining laziness.
87 */
88static inline struct rcu_head *rcu_cblist_dequeue(struct rcu_cblist *rclp)
89{
90 struct rcu_head *rhp;
91
92 rhp = rclp->head;
93 if (!rhp)
94 return NULL;
95 rclp->len--;
96 rclp->head = rhp->next;
97 if (!rclp->head)
98 rclp->tail = &rclp->head;
99 return rhp;
100}
101
102/*
103 * Account for the fact that a previously dequeued callback turned out
104 * to be marked as lazy.
105 */
106static inline void rcu_cblist_dequeued_lazy(struct rcu_cblist *rclp)
107{
108 rclp->len_lazy--;
109}
110
111/*
112 * Interim function to return rcu_cblist head pointer. Longer term, the
113 * rcu_cblist will be used more pervasively, removing the need for this
114 * function.
115 */
116static inline struct rcu_head *rcu_cblist_head(struct rcu_cblist *rclp)
117{
118 return rclp->head;
119}
120
121/*
122 * Interim function to return rcu_cblist head pointer. Longer term, the
123 * rcu_cblist will be used more pervasively, removing the need for this
124 * function.
125 */
126static inline struct rcu_head **rcu_cblist_tail(struct rcu_cblist *rclp)
127{
128 WARN_ON_ONCE(rcu_cblist_empty(rclp));
129 return rclp->tail;
130}
131
132/* Complicated segmented callback lists. ;-) */ 36/* Complicated segmented callback lists. ;-) */
133 37
134/* 38/*
@@ -183,530 +87,4 @@ struct rcu_segcblist {
183 .tails[RCU_NEXT_TAIL] = &n.head, \ 87 .tails[RCU_NEXT_TAIL] = &n.head, \
184} 88}
185 89
186/* 90#endif /* __INCLUDE_LINUX_RCU_SEGCBLIST_H */
187 * Initialize an rcu_segcblist structure.
188 */
189static inline void rcu_segcblist_init(struct rcu_segcblist *rsclp)
190{
191 int i;
192
193 BUILD_BUG_ON(RCU_NEXT_TAIL + 1 != ARRAY_SIZE(rsclp->gp_seq));
194 BUILD_BUG_ON(ARRAY_SIZE(rsclp->tails) != ARRAY_SIZE(rsclp->gp_seq));
195 rsclp->head = NULL;
196 for (i = 0; i < RCU_CBLIST_NSEGS; i++)
197 rsclp->tails[i] = &rsclp->head;
198 rsclp->len = 0;
199 rsclp->len_lazy = 0;
200}
201
202/*
203 * Is the specified rcu_segcblist structure empty?
204 *
205 * But careful! The fact that the ->head field is NULL does not
206 * necessarily imply that there are no callbacks associated with
207 * this structure. When callbacks are being invoked, they are
208 * removed as a group. If callback invocation must be preempted,
209 * the remaining callbacks will be added back to the list. Either
210 * way, the counts are updated later.
211 *
212 * So it is often the case that rcu_segcblist_n_cbs() should be used
213 * instead.
214 */
215static inline bool rcu_segcblist_empty(struct rcu_segcblist *rsclp)
216{
217 return !rsclp->head;
218}
219
220/* Return number of callbacks in segmented callback list. */
221static inline long rcu_segcblist_n_cbs(struct rcu_segcblist *rsclp)
222{
223 return READ_ONCE(rsclp->len);
224}
225
226/* Return number of lazy callbacks in segmented callback list. */
227static inline long rcu_segcblist_n_lazy_cbs(struct rcu_segcblist *rsclp)
228{
229 return rsclp->len_lazy;
230}
231
232/* Return number of lazy callbacks in segmented callback list. */
233static inline long rcu_segcblist_n_nonlazy_cbs(struct rcu_segcblist *rsclp)
234{
235 return rsclp->len - rsclp->len_lazy;
236}
237
238/*
239 * Is the specified rcu_segcblist enabled, for example, not corresponding
240 * to an offline or callback-offloaded CPU?
241 */
242static inline bool rcu_segcblist_is_enabled(struct rcu_segcblist *rsclp)
243{
244 return !!rsclp->tails[RCU_NEXT_TAIL];
245}
246
247/*
248 * Disable the specified rcu_segcblist structure, so that callbacks can
249 * no longer be posted to it. This structure must be empty.
250 */
251static inline void rcu_segcblist_disable(struct rcu_segcblist *rsclp)
252{
253 WARN_ON_ONCE(!rcu_segcblist_empty(rsclp));
254 WARN_ON_ONCE(rcu_segcblist_n_cbs(rsclp));
255 WARN_ON_ONCE(rcu_segcblist_n_lazy_cbs(rsclp));
256 rsclp->tails[RCU_NEXT_TAIL] = NULL;
257}
258
259/*
260 * Is the specified segment of the specified rcu_segcblist structure
261 * empty of callbacks?
262 */
263static inline bool rcu_segcblist_segempty(struct rcu_segcblist *rsclp, int seg)
264{
265 if (seg == RCU_DONE_TAIL)
266 return &rsclp->head == rsclp->tails[RCU_DONE_TAIL];
267 return rsclp->tails[seg - 1] == rsclp->tails[seg];
268}
269
270/*
271 * Are all segments following the specified segment of the specified
272 * rcu_segcblist structure empty of callbacks? (The specified
273 * segment might well contain callbacks.)
274 */
275static inline bool rcu_segcblist_restempty(struct rcu_segcblist *rsclp, int seg)
276{
277 return !*rsclp->tails[seg];
278}
279
280/*
281 * Does the specified rcu_segcblist structure contain callbacks that
282 * are ready to be invoked?
283 */
284static inline bool rcu_segcblist_ready_cbs(struct rcu_segcblist *rsclp)
285{
286 return rcu_segcblist_is_enabled(rsclp) &&
287 &rsclp->head != rsclp->tails[RCU_DONE_TAIL];
288}
289
290/*
291 * Does the specified rcu_segcblist structure contain callbacks that
292 * are still pending, that is, not yet ready to be invoked?
293 */
294static inline bool rcu_segcblist_pend_cbs(struct rcu_segcblist *rsclp)
295{
296 return rcu_segcblist_is_enabled(rsclp) &&
297 !rcu_segcblist_restempty(rsclp, RCU_DONE_TAIL);
298}
299
300/*
301 * Dequeue and return the first ready-to-invoke callback. If there
302 * are no ready-to-invoke callbacks, return NULL. Disables interrupts
303 * to avoid interference. Does not protect from interference from other
304 * CPUs or tasks.
305 */
306static inline struct rcu_head *
307rcu_segcblist_dequeue(struct rcu_segcblist *rsclp)
308{
309 unsigned long flags;
310 int i;
311 struct rcu_head *rhp;
312
313 local_irq_save(flags);
314 if (!rcu_segcblist_ready_cbs(rsclp)) {
315 local_irq_restore(flags);
316 return NULL;
317 }
318 rhp = rsclp->head;
319 BUG_ON(!rhp);
320 rsclp->head = rhp->next;
321 for (i = RCU_DONE_TAIL; i < RCU_CBLIST_NSEGS; i++) {
322 if (rsclp->tails[i] != &rhp->next)
323 break;
324 rsclp->tails[i] = &rsclp->head;
325 }
326 smp_mb(); /* Dequeue before decrement for rcu_barrier(). */
327 WRITE_ONCE(rsclp->len, rsclp->len - 1);
328 local_irq_restore(flags);
329 return rhp;
330}
331
332/*
333 * Account for the fact that a previously dequeued callback turned out
334 * to be marked as lazy.
335 */
336static inline void rcu_segcblist_dequeued_lazy(struct rcu_segcblist *rsclp)
337{
338 unsigned long flags;
339
340 local_irq_save(flags);
341 rsclp->len_lazy--;
342 local_irq_restore(flags);
343}
344
345/*
346 * Return a pointer to the first callback in the specified rcu_segcblist
347 * structure. This is useful for diagnostics.
348 */
349static inline struct rcu_head *
350rcu_segcblist_first_cb(struct rcu_segcblist *rsclp)
351{
352 if (rcu_segcblist_is_enabled(rsclp))
353 return rsclp->head;
354 return NULL;
355}
356
357/*
358 * Return a pointer to the first pending callback in the specified
359 * rcu_segcblist structure. This is useful just after posting a given
360 * callback -- if that callback is the first pending callback, then
361 * you cannot rely on someone else having already started up the required
362 * grace period.
363 */
364static inline struct rcu_head *
365rcu_segcblist_first_pend_cb(struct rcu_segcblist *rsclp)
366{
367 if (rcu_segcblist_is_enabled(rsclp))
368 return *rsclp->tails[RCU_DONE_TAIL];
369 return NULL;
370}
371
372/*
373 * Does the specified rcu_segcblist structure contain callbacks that
374 * have not yet been processed beyond having been posted, that is,
375 * does it contain callbacks in its last segment?
376 */
377static inline bool rcu_segcblist_new_cbs(struct rcu_segcblist *rsclp)
378{
379 return rcu_segcblist_is_enabled(rsclp) &&
380 !rcu_segcblist_restempty(rsclp, RCU_NEXT_READY_TAIL);
381}
382
383/*
384 * Enqueue the specified callback onto the specified rcu_segcblist
385 * structure, updating accounting as needed. Note that the ->len
386 * field may be accessed locklessly, hence the WRITE_ONCE().
387 * The ->len field is used by rcu_barrier() and friends to determine
388 * if it must post a callback on this structure, and it is OK
389 * for rcu_barrier() to sometimes post callbacks needlessly, but
390 * absolutely not OK for it to ever miss posting a callback.
391 */
392static inline void rcu_segcblist_enqueue(struct rcu_segcblist *rsclp,
393 struct rcu_head *rhp, bool lazy)
394{
395 WRITE_ONCE(rsclp->len, rsclp->len + 1); /* ->len sampled locklessly. */
396 if (lazy)
397 rsclp->len_lazy++;
398 smp_mb(); /* Ensure counts are updated before callback is enqueued. */
399 rhp->next = NULL;
400 *rsclp->tails[RCU_NEXT_TAIL] = rhp;
401 rsclp->tails[RCU_NEXT_TAIL] = &rhp->next;
402}
403
404/*
405 * Entrain the specified callback onto the specified rcu_segcblist at
406 * the end of the last non-empty segment. If the entire rcu_segcblist
407 * is empty, make no change, but return false.
408 *
409 * This is intended for use by rcu_barrier()-like primitives, -not-
410 * for normal grace-period use. IMPORTANT: The callback you enqueue
411 * will wait for all prior callbacks, NOT necessarily for a grace
412 * period. You have been warned.
413 */
414static inline bool rcu_segcblist_entrain(struct rcu_segcblist *rsclp,
415 struct rcu_head *rhp, bool lazy)
416{
417 int i;
418
419 if (rcu_segcblist_n_cbs(rsclp) == 0)
420 return false;
421 WRITE_ONCE(rsclp->len, rsclp->len + 1);
422 if (lazy)
423 rsclp->len_lazy++;
424 smp_mb(); /* Ensure counts are updated before callback is entrained. */
425 rhp->next = NULL;
426 for (i = RCU_NEXT_TAIL; i > RCU_DONE_TAIL; i--)
427 if (rsclp->tails[i] != rsclp->tails[i - 1])
428 break;
429 *rsclp->tails[i] = rhp;
430 for (; i <= RCU_NEXT_TAIL; i++)
431 rsclp->tails[i] = &rhp->next;
432 return true;
433}
434
435/*
436 * Extract only the counts from the specified rcu_segcblist structure,
437 * and place them in the specified rcu_cblist structure. This function
438 * supports both callback orphaning and invocation, hence the separation
439 * of counts and callbacks. (Callbacks ready for invocation must be
440 * orphaned and adopted separately from pending callbacks, but counts
441 * apply to all callbacks. Locking must be used to make sure that
442 * both orphaned-callbacks lists are consistent.)
443 */
444static inline void rcu_segcblist_extract_count(struct rcu_segcblist *rsclp,
445 struct rcu_cblist *rclp)
446{
447 rclp->len_lazy += rsclp->len_lazy;
448 rclp->len += rsclp->len;
449 rsclp->len_lazy = 0;
450 WRITE_ONCE(rsclp->len, 0); /* ->len sampled locklessly. */
451}
452
453/*
454 * Extract only those callbacks ready to be invoked from the specified
455 * rcu_segcblist structure and place them in the specified rcu_cblist
456 * structure.
457 */
458static inline void rcu_segcblist_extract_done_cbs(struct rcu_segcblist *rsclp,
459 struct rcu_cblist *rclp)
460{
461 int i;
462
463 if (!rcu_segcblist_ready_cbs(rsclp))
464 return; /* Nothing to do. */
465 *rclp->tail = rsclp->head;
466 rsclp->head = *rsclp->tails[RCU_DONE_TAIL];
467 *rsclp->tails[RCU_DONE_TAIL] = NULL;
468 rclp->tail = rsclp->tails[RCU_DONE_TAIL];
469 for (i = RCU_CBLIST_NSEGS - 1; i >= RCU_DONE_TAIL; i--)
470 if (rsclp->tails[i] == rsclp->tails[RCU_DONE_TAIL])
471 rsclp->tails[i] = &rsclp->head;
472}
473
474/*
475 * Extract only those callbacks still pending (not yet ready to be
476 * invoked) from the specified rcu_segcblist structure and place them in
477 * the specified rcu_cblist structure. Note that this loses information
478 * about any callbacks that might have been partway done waiting for
479 * their grace period. Too bad! They will have to start over.
480 */
481static inline void
482rcu_segcblist_extract_pend_cbs(struct rcu_segcblist *rsclp,
483 struct rcu_cblist *rclp)
484{
485 int i;
486
487 if (!rcu_segcblist_pend_cbs(rsclp))
488 return; /* Nothing to do. */
489 *rclp->tail = *rsclp->tails[RCU_DONE_TAIL];
490 rclp->tail = rsclp->tails[RCU_NEXT_TAIL];
491 *rsclp->tails[RCU_DONE_TAIL] = NULL;
492 for (i = RCU_DONE_TAIL + 1; i < RCU_CBLIST_NSEGS; i++)
493 rsclp->tails[i] = rsclp->tails[RCU_DONE_TAIL];
494}
495
496/*
497 * Move the entire contents of the specified rcu_segcblist structure,
498 * counts, callbacks, and all, to the specified rcu_cblist structure.
499 * @@@ Why do we need this??? Moving early-boot CBs to NOCB lists?
500 * @@@ Memory barrier needed? (Not if only used at boot time...)
501 */
502static inline void rcu_segcblist_extract_all(struct rcu_segcblist *rsclp,
503 struct rcu_cblist *rclp)
504{
505 rcu_segcblist_extract_done_cbs(rsclp, rclp);
506 rcu_segcblist_extract_pend_cbs(rsclp, rclp);
507 rcu_segcblist_extract_count(rsclp, rclp);
508}
509
510/*
511 * Insert counts from the specified rcu_cblist structure in the
512 * specified rcu_segcblist structure.
513 */
514static inline void rcu_segcblist_insert_count(struct rcu_segcblist *rsclp,
515 struct rcu_cblist *rclp)
516{
517 rsclp->len_lazy += rclp->len_lazy;
518 /* ->len sampled locklessly. */
519 WRITE_ONCE(rsclp->len, rsclp->len + rclp->len);
520 rclp->len_lazy = 0;
521 rclp->len = 0;
522}
523
524/*
525 * Move callbacks from the specified rcu_cblist to the beginning of the
526 * done-callbacks segment of the specified rcu_segcblist.
527 */
528static inline void rcu_segcblist_insert_done_cbs(struct rcu_segcblist *rsclp,
529 struct rcu_cblist *rclp)
530{
531 int i;
532
533 if (!rclp->head)
534 return; /* No callbacks to move. */
535 *rclp->tail = rsclp->head;
536 rsclp->head = rclp->head;
537 for (i = RCU_DONE_TAIL; i < RCU_CBLIST_NSEGS; i++)
538 if (&rsclp->head == rsclp->tails[i])
539 rsclp->tails[i] = rclp->tail;
540 else
541 break;
542 rclp->head = NULL;
543 rclp->tail = &rclp->head;
544}
545
546/*
547 * Move callbacks from the specified rcu_cblist to the end of the
548 * new-callbacks segment of the specified rcu_segcblist.
549 */
550static inline void rcu_segcblist_insert_pend_cbs(struct rcu_segcblist *rsclp,
551 struct rcu_cblist *rclp)
552{
553 if (!rclp->head)
554 return; /* Nothing to do. */
555 *rsclp->tails[RCU_NEXT_TAIL] = rclp->head;
556 rsclp->tails[RCU_NEXT_TAIL] = rclp->tail;
557 rclp->head = NULL;
558 rclp->tail = &rclp->head;
559}
560
561/*
562 * Advance the callbacks in the specified rcu_segcblist structure based
563 * on the current value passed in for the grace-period counter.
564 */
565static inline void rcu_segcblist_advance(struct rcu_segcblist *rsclp,
566 unsigned long seq)
567{
568 int i, j;
569
570 WARN_ON_ONCE(!rcu_segcblist_is_enabled(rsclp));
571 if (rcu_segcblist_restempty(rsclp, RCU_DONE_TAIL))
572 return;
573
574 /*
575 * Find all callbacks whose ->gp_seq numbers indicate that they
576 * are ready to invoke, and put them into the RCU_DONE_TAIL segment.
577 */
578 for (i = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++) {
579 if (ULONG_CMP_LT(seq, rsclp->gp_seq[i]))
580 break;
581 rsclp->tails[RCU_DONE_TAIL] = rsclp->tails[i];
582 }
583
584 /* If no callbacks moved, nothing more need be done. */
585 if (i == RCU_WAIT_TAIL)
586 return;
587
588 /* Clean up tail pointers that might have been misordered above. */
589 for (j = RCU_WAIT_TAIL; j < i; j++)
590 rsclp->tails[j] = rsclp->tails[RCU_DONE_TAIL];
591
592 /*
593 * Callbacks moved, so clean up the misordered ->tails[] pointers
594 * that now point into the middle of the list of ready-to-invoke
595 * callbacks. The overall effect is to copy down the later pointers
596 * into the gap that was created by the now-ready segments.
597 */
598 for (j = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++, j++) {
599 if (rsclp->tails[j] == rsclp->tails[RCU_NEXT_TAIL])
600 break; /* No more callbacks. */
601 rsclp->tails[j] = rsclp->tails[i];
602 rsclp->gp_seq[j] = rsclp->gp_seq[i];
603 }
604}
605
606/*
607 * "Accelerate" callbacks based on more-accurate grace-period information.
608 * The reason for this is that RCU does not synchronize the beginnings and
609 * ends of grace periods, and that callbacks are posted locally. This in
610 * turn means that the callbacks must be labelled conservatively early
611 * on, as getting exact information would degrade both performance and
612 * scalability. When more accurate grace-period information becomes
613 * available, previously posted callbacks can be "accelerated", marking
614 * them to complete at the end of the earlier grace period.
615 *
616 * This function operates on an rcu_segcblist structure, and also the
617 * grace-period sequence number seq at which new callbacks would become
618 * ready to invoke. Returns true if there are callbacks that won't be
619 * ready to invoke until seq, false otherwise.
620 */
621static inline bool rcu_segcblist_accelerate(struct rcu_segcblist *rsclp,
622 unsigned long seq)
623{
624 int i;
625
626 WARN_ON_ONCE(!rcu_segcblist_is_enabled(rsclp));
627 if (rcu_segcblist_restempty(rsclp, RCU_DONE_TAIL))
628 return false;
629
630 /*
631 * Find the segment preceding the oldest segment of callbacks
632 * whose ->gp_seq[] completion is at or after that passed in via
633 * "seq", skipping any empty segments. This oldest segment, along
634 * with any later segments, can be merged in with any newly arrived
635 * callbacks in the RCU_NEXT_TAIL segment, and assigned "seq"
636 * as their ->gp_seq[] grace-period completion sequence number.
637 */
638 for (i = RCU_NEXT_READY_TAIL; i > RCU_DONE_TAIL; i--)
639 if (rsclp->tails[i] != rsclp->tails[i - 1] &&
640 ULONG_CMP_LT(rsclp->gp_seq[i], seq))
641 break;
642
643 /*
644 * If all the segments contain callbacks that correspond to
645 * earlier grace-period sequence numbers than "seq", leave.
646 * Assuming that the rcu_segcblist structure has enough
647 * segments in its arrays, this can only happen if some of
648 * the non-done segments contain callbacks that really are
649 * ready to invoke. This situation will get straightened
650 * out by the next call to rcu_segcblist_advance().
651 *
652 * Also advance to the oldest segment of callbacks whose
653 * ->gp_seq[] completion is at or after that passed in via "seq",
654 * skipping any empty segments.
655 */
656 if (++i >= RCU_NEXT_TAIL)
657 return false;
658
659 /*
660 * Merge all later callbacks, including newly arrived callbacks,
661 * into the segment located by the for-loop above. Assign "seq"
662 * as the ->gp_seq[] value in order to correctly handle the case
663 * where there were no pending callbacks in the rcu_segcblist
664 * structure other than in the RCU_NEXT_TAIL segment.
665 */
666 for (; i < RCU_NEXT_TAIL; i++) {
667 rsclp->tails[i] = rsclp->tails[RCU_NEXT_TAIL];
668 rsclp->gp_seq[i] = seq;
669 }
670 return true;
671}
672
673/*
674 * Scan the specified rcu_segcblist structure for callbacks that need
675 * a grace period later than the one specified by "seq". We don't look
676 * at the RCU_DONE_TAIL or RCU_NEXT_TAIL segments because they don't
677 * have a grace-period sequence number.
678 */
679static inline bool rcu_segcblist_future_gp_needed(struct rcu_segcblist *rsclp,
680 unsigned long seq)
681{
682 int i;
683
684 for (i = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++)
685 if (rsclp->tails[i - 1] != rsclp->tails[i] &&
686 ULONG_CMP_LT(seq, rsclp->gp_seq[i]))
687 return true;
688 return false;
689}
690
691/*
692 * Interim function to return rcu_segcblist head pointer. Longer term, the
693 * rcu_segcblist will be used more pervasively, removing the need for this
694 * function.
695 */
696static inline struct rcu_head *rcu_segcblist_head(struct rcu_segcblist *rsclp)
697{
698 return rsclp->head;
699}
700
701/*
702 * Interim function to return rcu_segcblist head pointer. Longer term, the
703 * rcu_segcblist will be used more pervasively, removing the need for this
704 * function.
705 */
706static inline struct rcu_head **rcu_segcblist_tail(struct rcu_segcblist *rsclp)
707{
708 WARN_ON_ONCE(rcu_segcblist_empty(rsclp));
709 return rsclp->tails[RCU_NEXT_TAIL];
710}
711
712#endif /* __KERNEL_RCU_SEGCBLIST_H */
diff --git a/init/Kconfig b/init/Kconfig
index 42a346b0df43..1d3475fc9496 100644
--- a/init/Kconfig
+++ b/init/Kconfig
@@ -573,6 +573,9 @@ config RCU_STALL_COMMON
573 the tiny variants to disable RCU CPU stall warnings, while 573 the tiny variants to disable RCU CPU stall warnings, while
574 making these warnings mandatory for the tree variants. 574 making these warnings mandatory for the tree variants.
575 575
576config RCU_NEED_SEGCBLIST
577 def_bool ( TREE_RCU || PREEMPT_RCU || TINY_SRCU || TREE_SRCU )
578
576config CONTEXT_TRACKING 579config CONTEXT_TRACKING
577 bool 580 bool
578 581
diff --git a/kernel/rcu/Makefile b/kernel/rcu/Makefile
index 158e6593d58c..23803c7d5180 100644
--- a/kernel/rcu/Makefile
+++ b/kernel/rcu/Makefile
@@ -12,3 +12,4 @@ obj-$(CONFIG_TREE_RCU) += tree.o
12obj-$(CONFIG_PREEMPT_RCU) += tree.o 12obj-$(CONFIG_PREEMPT_RCU) += tree.o
13obj-$(CONFIG_TREE_RCU_TRACE) += tree_trace.o 13obj-$(CONFIG_TREE_RCU_TRACE) += tree_trace.o
14obj-$(CONFIG_TINY_RCU) += tiny.o 14obj-$(CONFIG_TINY_RCU) += tiny.o
15obj-$(CONFIG_RCU_NEED_SEGCBLIST) += rcu_segcblist.o
diff --git a/kernel/rcu/rcu_segcblist.c b/kernel/rcu/rcu_segcblist.c
new file mode 100644
index 000000000000..2b62a38b080f
--- /dev/null
+++ b/kernel/rcu/rcu_segcblist.c
@@ -0,0 +1,505 @@
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. */
30void 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 */
42long 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 */
63struct 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 */
80void 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 */
97void 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 */
109bool 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 */
120bool 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 */
130bool 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 */
142struct 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 */
171void 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 */
184struct 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 */
198struct 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 */
210bool 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 */
225void 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 */
247bool 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 */
277void 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 */
291void 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 */
314void 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 */
332void 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 */
346void 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 */
368void 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 */
383void 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 */
438bool 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 */
495bool 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}
diff --git a/kernel/rcu/rcu_segcblist.h b/kernel/rcu/rcu_segcblist.h
new file mode 100644
index 000000000000..6e36e36478cd
--- /dev/null
+++ b/kernel/rcu/rcu_segcblist.h
@@ -0,0 +1,164 @@
1/*
2 * RCU segmented callback lists, internal-to-rcu header file
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/rcu_segcblist.h>
24
25/*
26 * Account for the fact that a previously dequeued callback turned out
27 * to be marked as lazy.
28 */
29static inline void rcu_cblist_dequeued_lazy(struct rcu_cblist *rclp)
30{
31 rclp->len_lazy--;
32}
33
34/*
35 * Interim function to return rcu_cblist head pointer. Longer term, the
36 * rcu_cblist will be used more pervasively, removing the need for this
37 * function.
38 */
39static inline struct rcu_head *rcu_cblist_head(struct rcu_cblist *rclp)
40{
41 return rclp->head;
42}
43
44/*
45 * Interim function to return rcu_cblist head pointer. Longer term, the
46 * rcu_cblist will be used more pervasively, removing the need for this
47 * function.
48 */
49static inline struct rcu_head **rcu_cblist_tail(struct rcu_cblist *rclp)
50{
51 WARN_ON_ONCE(!rclp->head);
52 return rclp->tail;
53}
54
55void rcu_cblist_init(struct rcu_cblist *rclp);
56long rcu_cblist_count_cbs(struct rcu_cblist *rclp, long lim);
57struct rcu_head *rcu_cblist_dequeue(struct rcu_cblist *rclp);
58
59/*
60 * Is the specified rcu_segcblist structure empty?
61 *
62 * But careful! The fact that the ->head field is NULL does not
63 * necessarily imply that there are no callbacks associated with
64 * this structure. When callbacks are being invoked, they are
65 * removed as a group. If callback invocation must be preempted,
66 * the remaining callbacks will be added back to the list. Either
67 * way, the counts are updated later.
68 *
69 * So it is often the case that rcu_segcblist_n_cbs() should be used
70 * instead.
71 */
72static inline bool rcu_segcblist_empty(struct rcu_segcblist *rsclp)
73{
74 return !rsclp->head;
75}
76
77/* Return number of callbacks in segmented callback list. */
78static inline long rcu_segcblist_n_cbs(struct rcu_segcblist *rsclp)
79{
80 return READ_ONCE(rsclp->len);
81}
82
83/* Return number of lazy callbacks in segmented callback list. */
84static inline long rcu_segcblist_n_lazy_cbs(struct rcu_segcblist *rsclp)
85{
86 return rsclp->len_lazy;
87}
88
89/* Return number of lazy callbacks in segmented callback list. */
90static inline long rcu_segcblist_n_nonlazy_cbs(struct rcu_segcblist *rsclp)
91{
92 return rsclp->len - rsclp->len_lazy;
93}
94
95/*
96 * Is the specified rcu_segcblist enabled, for example, not corresponding
97 * to an offline or callback-offloaded CPU?
98 */
99static inline bool rcu_segcblist_is_enabled(struct rcu_segcblist *rsclp)
100{
101 return !!rsclp->tails[RCU_NEXT_TAIL];
102}
103
104/*
105 * Are all segments following the specified segment of the specified
106 * rcu_segcblist structure empty of callbacks? (The specified
107 * segment might well contain callbacks.)
108 */
109static inline bool rcu_segcblist_restempty(struct rcu_segcblist *rsclp, int seg)
110{
111 return !*rsclp->tails[seg];
112}
113
114/*
115 * Interim function to return rcu_segcblist head pointer. Longer term, the
116 * rcu_segcblist will be used more pervasively, removing the need for this
117 * function.
118 */
119static inline struct rcu_head *rcu_segcblist_head(struct rcu_segcblist *rsclp)
120{
121 return rsclp->head;
122}
123
124/*
125 * Interim function to return rcu_segcblist head pointer. Longer term, the
126 * rcu_segcblist will be used more pervasively, removing the need for this
127 * function.
128 */
129static inline struct rcu_head **rcu_segcblist_tail(struct rcu_segcblist *rsclp)
130{
131 WARN_ON_ONCE(rcu_segcblist_empty(rsclp));
132 return rsclp->tails[RCU_NEXT_TAIL];
133}
134
135void rcu_segcblist_init(struct rcu_segcblist *rsclp);
136void rcu_segcblist_disable(struct rcu_segcblist *rsclp);
137bool rcu_segcblist_segempty(struct rcu_segcblist *rsclp, int seg);
138bool rcu_segcblist_ready_cbs(struct rcu_segcblist *rsclp);
139bool rcu_segcblist_pend_cbs(struct rcu_segcblist *rsclp);
140struct rcu_head *rcu_segcblist_dequeue(struct rcu_segcblist *rsclp);
141void rcu_segcblist_dequeued_lazy(struct rcu_segcblist *rsclp);
142struct rcu_head *rcu_segcblist_first_cb(struct rcu_segcblist *rsclp);
143struct rcu_head *rcu_segcblist_first_pend_cb(struct rcu_segcblist *rsclp);
144bool rcu_segcblist_new_cbs(struct rcu_segcblist *rsclp);
145void rcu_segcblist_enqueue(struct rcu_segcblist *rsclp,
146 struct rcu_head *rhp, bool lazy);
147bool rcu_segcblist_entrain(struct rcu_segcblist *rsclp,
148 struct rcu_head *rhp, bool lazy);
149void rcu_segcblist_extract_count(struct rcu_segcblist *rsclp,
150 struct rcu_cblist *rclp);
151void rcu_segcblist_extract_done_cbs(struct rcu_segcblist *rsclp,
152 struct rcu_cblist *rclp);
153void rcu_segcblist_extract_pend_cbs(struct rcu_segcblist *rsclp,
154 struct rcu_cblist *rclp);
155void rcu_segcblist_insert_count(struct rcu_segcblist *rsclp,
156 struct rcu_cblist *rclp);
157void rcu_segcblist_insert_done_cbs(struct rcu_segcblist *rsclp,
158 struct rcu_cblist *rclp);
159void rcu_segcblist_insert_pend_cbs(struct rcu_segcblist *rsclp,
160 struct rcu_cblist *rclp);
161void rcu_segcblist_advance(struct rcu_segcblist *rsclp, unsigned long seq);
162bool rcu_segcblist_accelerate(struct rcu_segcblist *rsclp, unsigned long seq);
163bool rcu_segcblist_future_gp_needed(struct rcu_segcblist *rsclp,
164 unsigned long seq);
diff --git a/kernel/rcu/srcutiny.c b/kernel/rcu/srcutiny.c
index b8293527ee18..36e1f82faed1 100644
--- a/kernel/rcu/srcutiny.c
+++ b/kernel/rcu/srcutiny.c
@@ -30,6 +30,7 @@
30#include <linux/srcu.h> 30#include <linux/srcu.h>
31 31
32#include <linux/rcu_node_tree.h> 32#include <linux/rcu_node_tree.h>
33#include "rcu_segcblist.h"
33#include "rcu.h" 34#include "rcu.h"
34 35
35static int init_srcu_struct_fields(struct srcu_struct *sp) 36static int init_srcu_struct_fields(struct srcu_struct *sp)
diff --git a/kernel/rcu/srcutree.c b/kernel/rcu/srcutree.c
index 87b070de6371..3ae8474557df 100644
--- a/kernel/rcu/srcutree.c
+++ b/kernel/rcu/srcutree.c
@@ -38,6 +38,7 @@
38#include <linux/srcu.h> 38#include <linux/srcu.h>
39 39
40#include "rcu.h" 40#include "rcu.h"
41#include "rcu_segcblist.h"
41 42
42ulong exp_holdoff = 25 * 1000; /* Holdoff (ns) for auto-expediting. */ 43ulong exp_holdoff = 25 * 1000; /* Holdoff (ns) for auto-expediting. */
43module_param(exp_holdoff, ulong, 0444); 44module_param(exp_holdoff, ulong, 0444);
diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
index 91fff49d5869..1205c8ad138a 100644
--- a/kernel/rcu/tree.c
+++ b/kernel/rcu/tree.c
@@ -2633,9 +2633,8 @@ static void rcu_adopt_orphan_cbs(struct rcu_state *rsp, unsigned long flags)
2633 return; 2633 return;
2634 2634
2635 /* Do the accounting first. */ 2635 /* Do the accounting first. */
2636 rdp->n_cbs_adopted += rcu_cblist_n_cbs(&rsp->orphan_done); 2636 rdp->n_cbs_adopted += rsp->orphan_done.len;
2637 if (rcu_cblist_n_lazy_cbs(&rsp->orphan_done) != 2637 if (rsp->orphan_done.len_lazy != rsp->orphan_done.len)
2638 rcu_cblist_n_cbs(&rsp->orphan_done))
2639 rcu_idle_count_callbacks_posted(); 2638 rcu_idle_count_callbacks_posted();
2640 rcu_segcblist_insert_count(&rdp->cblist, &rsp->orphan_done); 2639 rcu_segcblist_insert_count(&rdp->cblist, &rsp->orphan_done);
2641 2640
@@ -2647,9 +2646,9 @@ static void rcu_adopt_orphan_cbs(struct rcu_state *rsp, unsigned long flags)
2647 2646
2648 /* First adopt the ready-to-invoke callbacks, then the done ones. */ 2647 /* First adopt the ready-to-invoke callbacks, then the done ones. */
2649 rcu_segcblist_insert_done_cbs(&rdp->cblist, &rsp->orphan_done); 2648 rcu_segcblist_insert_done_cbs(&rdp->cblist, &rsp->orphan_done);
2650 WARN_ON_ONCE(!rcu_cblist_empty(&rsp->orphan_done)); 2649 WARN_ON_ONCE(rsp->orphan_done.head);
2651 rcu_segcblist_insert_pend_cbs(&rdp->cblist, &rsp->orphan_pend); 2650 rcu_segcblist_insert_pend_cbs(&rdp->cblist, &rsp->orphan_pend);
2652 WARN_ON_ONCE(!rcu_cblist_empty(&rsp->orphan_pend)); 2651 WARN_ON_ONCE(rsp->orphan_pend.head);
2653 WARN_ON_ONCE(rcu_segcblist_empty(&rdp->cblist) != 2652 WARN_ON_ONCE(rcu_segcblist_empty(&rdp->cblist) !=
2654 !rcu_segcblist_n_cbs(&rdp->cblist)); 2653 !rcu_segcblist_n_cbs(&rdp->cblist));
2655} 2654}
@@ -2792,17 +2791,16 @@ static void rcu_do_batch(struct rcu_state *rsp, struct rcu_data *rdp)
2792 * Stop only if limit reached and CPU has something to do. 2791 * Stop only if limit reached and CPU has something to do.
2793 * Note: The rcl structure counts down from zero. 2792 * Note: The rcl structure counts down from zero.
2794 */ 2793 */
2795 if (-rcu_cblist_n_cbs(&rcl) >= bl && 2794 if (-rcl.len >= bl &&
2796 (need_resched() || 2795 (need_resched() ||
2797 (!is_idle_task(current) && !rcu_is_callbacks_kthread()))) 2796 (!is_idle_task(current) && !rcu_is_callbacks_kthread())))
2798 break; 2797 break;
2799 } 2798 }
2800 2799
2801 local_irq_save(flags); 2800 local_irq_save(flags);
2802 count = -rcu_cblist_n_cbs(&rcl); 2801 count = -rcl.len;
2803 trace_rcu_batch_end(rsp->name, count, !rcu_cblist_empty(&rcl), 2802 trace_rcu_batch_end(rsp->name, count, !!rcl.head, need_resched(),
2804 need_resched(), is_idle_task(current), 2803 is_idle_task(current), rcu_is_callbacks_kthread());
2805 rcu_is_callbacks_kthread());
2806 2804
2807 /* Update counts and requeue any remaining callbacks. */ 2805 /* Update counts and requeue any remaining callbacks. */
2808 rcu_segcblist_insert_done_cbs(&rdp->cblist, &rcl); 2806 rcu_segcblist_insert_done_cbs(&rdp->cblist, &rcl);
diff --git a/kernel/rcu/tree.h b/kernel/rcu/tree.h
index 0e598ab08fea..ba38262c3554 100644
--- a/kernel/rcu/tree.h
+++ b/kernel/rcu/tree.h
@@ -30,9 +30,10 @@
30#include <linux/seqlock.h> 30#include <linux/seqlock.h>
31#include <linux/swait.h> 31#include <linux/swait.h>
32#include <linux/stop_machine.h> 32#include <linux/stop_machine.h>
33#include <linux/rcu_segcblist.h>
34#include <linux/rcu_node_tree.h> 33#include <linux/rcu_node_tree.h>
35 34
35#include "rcu_segcblist.h"
36
36/* 37/*
37 * Dynticks per-CPU state. 38 * Dynticks per-CPU state.
38 */ 39 */
diff --git a/kernel/rcu/tree_plugin.h b/kernel/rcu/tree_plugin.h
index 7f1d677a2a25..c9a48657512a 100644
--- a/kernel/rcu/tree_plugin.h
+++ b/kernel/rcu/tree_plugin.h
@@ -1934,20 +1934,20 @@ static bool __maybe_unused rcu_nocb_adopt_orphan_cbs(struct rcu_state *rsp,
1934 struct rcu_data *rdp, 1934 struct rcu_data *rdp,
1935 unsigned long flags) 1935 unsigned long flags)
1936{ 1936{
1937 long ql = rcu_cblist_n_cbs(&rsp->orphan_done); 1937 long ql = rsp->orphan_done.len;
1938 long qll = rcu_cblist_n_lazy_cbs(&rsp->orphan_done); 1938 long qll = rsp->orphan_done.len_lazy;
1939 1939
1940 /* If this is not a no-CBs CPU, tell the caller to do it the old way. */ 1940 /* If this is not a no-CBs CPU, tell the caller to do it the old way. */
1941 if (!rcu_is_nocb_cpu(smp_processor_id())) 1941 if (!rcu_is_nocb_cpu(smp_processor_id()))
1942 return false; 1942 return false;
1943 1943
1944 /* First, enqueue the donelist, if any. This preserves CB ordering. */ 1944 /* First, enqueue the donelist, if any. This preserves CB ordering. */
1945 if (!rcu_cblist_empty(&rsp->orphan_done)) { 1945 if (rsp->orphan_done.head) {
1946 __call_rcu_nocb_enqueue(rdp, rcu_cblist_head(&rsp->orphan_done), 1946 __call_rcu_nocb_enqueue(rdp, rcu_cblist_head(&rsp->orphan_done),
1947 rcu_cblist_tail(&rsp->orphan_done), 1947 rcu_cblist_tail(&rsp->orphan_done),
1948 ql, qll, flags); 1948 ql, qll, flags);
1949 } 1949 }
1950 if (!rcu_cblist_empty(&rsp->orphan_pend)) { 1950 if (rsp->orphan_pend.head) {
1951 __call_rcu_nocb_enqueue(rdp, rcu_cblist_head(&rsp->orphan_pend), 1951 __call_rcu_nocb_enqueue(rdp, rcu_cblist_head(&rsp->orphan_pend),
1952 rcu_cblist_tail(&rsp->orphan_pend), 1952 rcu_cblist_tail(&rsp->orphan_pend),
1953 ql, qll, flags); 1953 ql, qll, flags);
diff --git a/kernel/rcu/tree_trace.c b/kernel/rcu/tree_trace.c
index 30c5bf89ee58..6cea17a1ea30 100644
--- a/kernel/rcu/tree_trace.c
+++ b/kernel/rcu/tree_trace.c
@@ -277,8 +277,8 @@ static void print_one_rcu_state(struct seq_file *m, struct rcu_state *rsp)
277 rsp->n_force_qs, rsp->n_force_qs_ngp, 277 rsp->n_force_qs, rsp->n_force_qs_ngp,
278 rsp->n_force_qs - rsp->n_force_qs_ngp, 278 rsp->n_force_qs - rsp->n_force_qs_ngp,
279 READ_ONCE(rsp->n_force_qs_lh), 279 READ_ONCE(rsp->n_force_qs_lh),
280 rcu_cblist_n_lazy_cbs(&rsp->orphan_done), 280 rsp->orphan_done.len_lazy,
281 rcu_cblist_n_cbs(&rsp->orphan_done)); 281 rsp->orphan_done.len);
282 for (rnp = &rsp->node[0]; rnp - &rsp->node[0] < rcu_num_nodes; rnp++) { 282 for (rnp = &rsp->node[0]; rnp - &rsp->node[0] < rcu_num_nodes; rnp++) {
283 if (rnp->level != level) { 283 if (rnp->level != level) {
284 seq_puts(m, "\n"); 284 seq_puts(m, "\n");