blob: 7f181c9675f761bd8fbc81294a665da0dd0ecb85 [file] [log] [blame]
Paul E. McKenneyeb7935e2019-01-17 10:13:19 -08001// SPDX-License-Identifier: GPL-2.0+
Paul E. McKenney98059b92017-05-02 06:30:12 -07002/*
3 * RCU segmented callback lists, function definitions
4 *
Paul E. McKenney98059b92017-05-02 06:30:12 -07005 * Copyright IBM Corporation, 2017
6 *
Paul E. McKenneyeb7935e2019-01-17 10:13:19 -08007 * Authors: Paul E. McKenney <paulmck@linux.ibm.com>
Paul E. McKenney98059b92017-05-02 06:30:12 -07008 */
9
Joel Fernandes (Google)ae5c2342020-09-23 11:22:09 -040010#include <linux/cpu.h>
Paul E. McKenney98059b92017-05-02 06:30:12 -070011#include <linux/interrupt.h>
Joel Fernandes (Google)ae5c2342020-09-23 11:22:09 -040012#include <linux/kernel.h>
13#include <linux/types.h>
Paul E. McKenney98059b92017-05-02 06:30:12 -070014
15#include "rcu_segcblist.h"
16
17/* Initialize simple callback list. */
18void rcu_cblist_init(struct rcu_cblist *rclp)
19{
20 rclp->head = NULL;
21 rclp->tail = &rclp->head;
22 rclp->len = 0;
Paul E. McKenney98059b92017-05-02 06:30:12 -070023}
24
25/*
Paul E. McKenneyeda669a2019-07-01 17:36:53 -070026 * Enqueue an rcu_head structure onto the specified callback list.
Paul E. McKenneyeda669a2019-07-01 17:36:53 -070027 */
28void rcu_cblist_enqueue(struct rcu_cblist *rclp, struct rcu_head *rhp)
29{
30 *rclp->tail = rhp;
31 rclp->tail = &rhp->next;
32 WRITE_ONCE(rclp->len, rclp->len + 1);
33}
34
35/*
Paul E. McKenneyd1b222c2019-07-02 16:03:33 -070036 * Flush the second rcu_cblist structure onto the first one, obliterating
37 * any contents of the first. If rhp is non-NULL, enqueue it as the sole
38 * element of the second rcu_cblist structure, but ensuring that the second
39 * rcu_cblist structure, if initially non-empty, always appears non-empty
40 * throughout the process. If rdp is NULL, the second rcu_cblist structure
41 * is instead initialized to empty.
42 */
43void rcu_cblist_flush_enqueue(struct rcu_cblist *drclp,
44 struct rcu_cblist *srclp,
45 struct rcu_head *rhp)
46{
47 drclp->head = srclp->head;
48 if (drclp->head)
49 drclp->tail = srclp->tail;
50 else
51 drclp->tail = &drclp->head;
52 drclp->len = srclp->len;
Paul E. McKenneyd1b222c2019-07-02 16:03:33 -070053 if (!rhp) {
54 rcu_cblist_init(srclp);
55 } else {
56 rhp->next = NULL;
57 srclp->head = rhp;
58 srclp->tail = &rhp->next;
59 WRITE_ONCE(srclp->len, 1);
Paul E. McKenneyd1b222c2019-07-02 16:03:33 -070060 }
61}
62
63/*
Paul E. McKenney98059b92017-05-02 06:30:12 -070064 * Dequeue the oldest rcu_head structure from the specified callback
Joel Fernandes (Google)77a40f92019-08-30 12:36:32 -040065 * list.
Paul E. McKenney98059b92017-05-02 06:30:12 -070066 */
67struct rcu_head *rcu_cblist_dequeue(struct rcu_cblist *rclp)
68{
69 struct rcu_head *rhp;
70
71 rhp = rclp->head;
72 if (!rhp)
73 return NULL;
74 rclp->len--;
75 rclp->head = rhp->next;
76 if (!rclp->head)
77 rclp->tail = &rclp->head;
78 return rhp;
79}
80
Paul E. McKenneyeda669a2019-07-01 17:36:53 -070081/* Set the length of an rcu_segcblist structure. */
kbuild test robot1d24dd42019-08-08 10:32:58 +080082static void rcu_segcblist_set_len(struct rcu_segcblist *rsclp, long v)
Paul E. McKenneyeda669a2019-07-01 17:36:53 -070083{
84#ifdef CONFIG_RCU_NOCB_CPU
85 atomic_long_set(&rsclp->len, v);
86#else
87 WRITE_ONCE(rsclp->len, v);
88#endif
89}
90
Joel Fernandes (Google)ae5c2342020-09-23 11:22:09 -040091/* Get the length of a segment of the rcu_segcblist structure. */
92static long rcu_segcblist_get_seglen(struct rcu_segcblist *rsclp, int seg)
93{
94 return READ_ONCE(rsclp->seglen[seg]);
95}
96
Joel Fernandes (Google)b4e60392020-11-18 11:15:41 -050097/* Return number of callbacks in segmented callback list by summing seglen. */
98long rcu_segcblist_n_segment_cbs(struct rcu_segcblist *rsclp)
99{
100 long len = 0;
101 int i;
102
103 for (i = RCU_DONE_TAIL; i < RCU_CBLIST_NSEGS; i++)
104 len += rcu_segcblist_get_seglen(rsclp, i);
105
106 return len;
107}
108
Joel Fernandes (Google)ae5c2342020-09-23 11:22:09 -0400109/* Set the length of a segment of the rcu_segcblist structure. */
110static void rcu_segcblist_set_seglen(struct rcu_segcblist *rsclp, int seg, long v)
111{
112 WRITE_ONCE(rsclp->seglen[seg], v);
113}
114
115/* Increase the numeric length of a segment by a specified amount. */
116static void rcu_segcblist_add_seglen(struct rcu_segcblist *rsclp, int seg, long v)
117{
118 WRITE_ONCE(rsclp->seglen[seg], rsclp->seglen[seg] + v);
119}
120
121/* Move from's segment length to to's segment. */
122static void rcu_segcblist_move_seglen(struct rcu_segcblist *rsclp, int from, int to)
123{
124 long len;
125
126 if (from == to)
127 return;
128
129 len = rcu_segcblist_get_seglen(rsclp, from);
130 if (!len)
131 return;
132
133 rcu_segcblist_add_seglen(rsclp, to, len);
134 rcu_segcblist_set_seglen(rsclp, from, 0);
135}
136
137/* Increment segment's length. */
138static void rcu_segcblist_inc_seglen(struct rcu_segcblist *rsclp, int seg)
139{
140 rcu_segcblist_add_seglen(rsclp, seg, 1);
141}
142
Paul E. McKenneyeda669a2019-07-01 17:36:53 -0700143/*
144 * Increase the numeric length of an rcu_segcblist structure by the
145 * specified amount, which can be negative. This can cause the ->len
146 * field to disagree with the actual number of callbacks on the structure.
147 * This increase is fully ordered with respect to the callers accesses
148 * both before and after.
Joel Fernandes (Google)c2e13112020-11-03 09:26:03 -0500149 *
150 * So why on earth is a memory barrier required both before and after
151 * the update to the ->len field???
152 *
153 * The reason is that rcu_barrier() locklessly samples each CPU's ->len
154 * field, and if a given CPU's field is zero, avoids IPIing that CPU.
155 * This can of course race with both queuing and invoking of callbacks.
156 * Failing to correctly handle either of these races could result in
157 * rcu_barrier() failing to IPI a CPU that actually had callbacks queued
158 * which rcu_barrier() was obligated to wait on. And if rcu_barrier()
159 * failed to wait on such a callback, unloading certain kernel modules
160 * would result in calls to functions whose code was no longer present in
161 * the kernel, for but one example.
162 *
163 * Therefore, ->len transitions from 1->0 and 0->1 have to be carefully
164 * ordered with respect with both list modifications and the rcu_barrier().
165 *
166 * The queuing case is CASE 1 and the invoking case is CASE 2.
167 *
168 * CASE 1: Suppose that CPU 0 has no callbacks queued, but invokes
169 * call_rcu() just as CPU 1 invokes rcu_barrier(). CPU 0's ->len field
170 * will transition from 0->1, which is one of the transitions that must
171 * be handled carefully. Without the full memory barriers after the ->len
172 * update and at the beginning of rcu_barrier(), the following could happen:
173 *
174 * CPU 0 CPU 1
175 *
176 * call_rcu().
177 * rcu_barrier() sees ->len as 0.
178 * set ->len = 1.
179 * rcu_barrier() does nothing.
180 * module is unloaded.
181 * callback invokes unloaded function!
182 *
183 * With the full barriers, any case where rcu_barrier() sees ->len as 0 will
184 * have unambiguously preceded the return from the racing call_rcu(), which
185 * means that this call_rcu() invocation is OK to not wait on. After all,
186 * you are supposed to make sure that any problematic call_rcu() invocations
187 * happen before the rcu_barrier().
188 *
189 *
190 * CASE 2: Suppose that CPU 0 is invoking its last callback just as
191 * CPU 1 invokes rcu_barrier(). CPU 0's ->len field will transition from
192 * 1->0, which is one of the transitions that must be handled carefully.
193 * Without the full memory barriers before the ->len update and at the
194 * end of rcu_barrier(), the following could happen:
195 *
196 * CPU 0 CPU 1
197 *
198 * start invoking last callback
199 * set ->len = 0 (reordered)
200 * rcu_barrier() sees ->len as 0
201 * rcu_barrier() does nothing.
202 * module is unloaded
203 * callback executing after unloaded!
204 *
205 * With the full barriers, any case where rcu_barrier() sees ->len as 0
206 * will be fully ordered after the completion of the callback function,
207 * so that the module unloading operation is completely safe.
208 *
Paul E. McKenneyeda669a2019-07-01 17:36:53 -0700209 */
Joel Fernandes (Google)6bc33582020-11-03 09:25:57 -0500210void rcu_segcblist_add_len(struct rcu_segcblist *rsclp, long v)
Paul E. McKenneyeda669a2019-07-01 17:36:53 -0700211{
212#ifdef CONFIG_RCU_NOCB_CPU
Joel Fernandes (Google)c2e13112020-11-03 09:26:03 -0500213 smp_mb__before_atomic(); // Read header comment above.
Paul E. McKenneyeda669a2019-07-01 17:36:53 -0700214 atomic_long_add(v, &rsclp->len);
Joel Fernandes (Google)c2e13112020-11-03 09:26:03 -0500215 smp_mb__after_atomic(); // Read header comment above.
Paul E. McKenneyeda669a2019-07-01 17:36:53 -0700216#else
Joel Fernandes (Google)c2e13112020-11-03 09:26:03 -0500217 smp_mb(); // Read header comment above.
Paul E. McKenneyeda669a2019-07-01 17:36:53 -0700218 WRITE_ONCE(rsclp->len, rsclp->len + v);
Joel Fernandes (Google)c2e13112020-11-03 09:26:03 -0500219 smp_mb(); // Read header comment above.
Paul E. McKenneyeda669a2019-07-01 17:36:53 -0700220#endif
221}
222
223/*
224 * Increase the numeric length of an rcu_segcblist structure by one.
225 * This can cause the ->len field to disagree with the actual number of
226 * callbacks on the structure. This increase is fully ordered with respect
227 * to the callers accesses both before and after.
228 */
229void rcu_segcblist_inc_len(struct rcu_segcblist *rsclp)
230{
231 rcu_segcblist_add_len(rsclp, 1);
232}
233
234/*
Paul E. McKenney98059b92017-05-02 06:30:12 -0700235 * Initialize an rcu_segcblist structure.
236 */
237void rcu_segcblist_init(struct rcu_segcblist *rsclp)
238{
239 int i;
240
241 BUILD_BUG_ON(RCU_NEXT_TAIL + 1 != ARRAY_SIZE(rsclp->gp_seq));
242 BUILD_BUG_ON(ARRAY_SIZE(rsclp->tails) != ARRAY_SIZE(rsclp->gp_seq));
243 rsclp->head = NULL;
Joel Fernandes (Google)ae5c2342020-09-23 11:22:09 -0400244 for (i = 0; i < RCU_CBLIST_NSEGS; i++) {
Paul E. McKenney98059b92017-05-02 06:30:12 -0700245 rsclp->tails[i] = &rsclp->head;
Joel Fernandes (Google)ae5c2342020-09-23 11:22:09 -0400246 rcu_segcblist_set_seglen(rsclp, i, 0);
247 }
Paul E. McKenneyeda669a2019-07-01 17:36:53 -0700248 rcu_segcblist_set_len(rsclp, 0);
Frederic Weisbecker65e56032020-11-13 13:13:16 +0100249 rcu_segcblist_set_flags(rsclp, SEGCBLIST_ENABLED);
Paul E. McKenney98059b92017-05-02 06:30:12 -0700250}
251
252/*
253 * Disable the specified rcu_segcblist structure, so that callbacks can
254 * no longer be posted to it. This structure must be empty.
255 */
256void rcu_segcblist_disable(struct rcu_segcblist *rsclp)
257{
258 WARN_ON_ONCE(!rcu_segcblist_empty(rsclp));
259 WARN_ON_ONCE(rcu_segcblist_n_cbs(rsclp));
Frederic Weisbecker65e56032020-11-13 13:13:16 +0100260 rcu_segcblist_clear_flags(rsclp, SEGCBLIST_ENABLED);
Paul E. McKenney98059b92017-05-02 06:30:12 -0700261}
262
263/*
Paul E. McKenneyce5215c2019-04-12 15:58:34 -0700264 * Mark the specified rcu_segcblist structure as offloaded. This
265 * structure must be empty.
266 */
Frederic Weisbeckerd97b0782020-11-13 13:13:19 +0100267void rcu_segcblist_offload(struct rcu_segcblist *rsclp, bool offload)
Paul E. McKenneyce5215c2019-04-12 15:58:34 -0700268{
Frederic Weisbeckerd97b0782020-11-13 13:13:19 +0100269 if (offload) {
270 rcu_segcblist_clear_flags(rsclp, SEGCBLIST_SOFTIRQ_ONLY);
271 rcu_segcblist_set_flags(rsclp, SEGCBLIST_OFFLOADED);
272 } else {
273 rcu_segcblist_clear_flags(rsclp, SEGCBLIST_OFFLOADED);
274 }
Paul E. McKenneyce5215c2019-04-12 15:58:34 -0700275}
276
277/*
Paul E. McKenney98059b92017-05-02 06:30:12 -0700278 * Does the specified rcu_segcblist structure contain callbacks that
279 * are ready to be invoked?
280 */
281bool rcu_segcblist_ready_cbs(struct rcu_segcblist *rsclp)
282{
283 return rcu_segcblist_is_enabled(rsclp) &&
Paul E. McKenneybfeebe22020-01-03 16:14:08 -0800284 &rsclp->head != READ_ONCE(rsclp->tails[RCU_DONE_TAIL]);
Paul E. McKenney98059b92017-05-02 06:30:12 -0700285}
286
287/*
288 * Does the specified rcu_segcblist structure contain callbacks that
289 * are still pending, that is, not yet ready to be invoked?
290 */
291bool rcu_segcblist_pend_cbs(struct rcu_segcblist *rsclp)
292{
293 return rcu_segcblist_is_enabled(rsclp) &&
294 !rcu_segcblist_restempty(rsclp, RCU_DONE_TAIL);
295}
296
297/*
Paul E. McKenney98059b92017-05-02 06:30:12 -0700298 * Return a pointer to the first callback in the specified rcu_segcblist
299 * structure. This is useful for diagnostics.
300 */
301struct rcu_head *rcu_segcblist_first_cb(struct rcu_segcblist *rsclp)
302{
303 if (rcu_segcblist_is_enabled(rsclp))
304 return rsclp->head;
305 return NULL;
306}
307
308/*
309 * Return a pointer to the first pending callback in the specified
310 * rcu_segcblist structure. This is useful just after posting a given
311 * callback -- if that callback is the first pending callback, then
312 * you cannot rely on someone else having already started up the required
313 * grace period.
314 */
315struct rcu_head *rcu_segcblist_first_pend_cb(struct rcu_segcblist *rsclp)
316{
317 if (rcu_segcblist_is_enabled(rsclp))
318 return *rsclp->tails[RCU_DONE_TAIL];
319 return NULL;
320}
321
322/*
Paul E. McKenney5d6742b2019-05-15 09:56:40 -0700323 * Return false if there are no CBs awaiting grace periods, otherwise,
324 * return true and store the nearest waited-upon grace period into *lp.
325 */
326bool rcu_segcblist_nextgp(struct rcu_segcblist *rsclp, unsigned long *lp)
327{
328 if (!rcu_segcblist_pend_cbs(rsclp))
329 return false;
330 *lp = rsclp->gp_seq[RCU_WAIT_TAIL];
331 return true;
332}
333
334/*
Paul E. McKenney98059b92017-05-02 06:30:12 -0700335 * Enqueue the specified callback onto the specified rcu_segcblist
336 * structure, updating accounting as needed. Note that the ->len
337 * field may be accessed locklessly, hence the WRITE_ONCE().
338 * The ->len field is used by rcu_barrier() and friends to determine
339 * if it must post a callback on this structure, and it is OK
340 * for rcu_barrier() to sometimes post callbacks needlessly, but
341 * absolutely not OK for it to ever miss posting a callback.
342 */
343void rcu_segcblist_enqueue(struct rcu_segcblist *rsclp,
Joel Fernandes (Google)77a40f92019-08-30 12:36:32 -0400344 struct rcu_head *rhp)
Paul E. McKenney98059b92017-05-02 06:30:12 -0700345{
Paul E. McKenneyeda669a2019-07-01 17:36:53 -0700346 rcu_segcblist_inc_len(rsclp);
Joel Fernandes (Google)ae5c2342020-09-23 11:22:09 -0400347 rcu_segcblist_inc_seglen(rsclp, RCU_NEXT_TAIL);
Paul E. McKenney98059b92017-05-02 06:30:12 -0700348 rhp->next = NULL;
Paul E. McKenney76c69272019-05-13 14:36:11 -0700349 WRITE_ONCE(*rsclp->tails[RCU_NEXT_TAIL], rhp);
350 WRITE_ONCE(rsclp->tails[RCU_NEXT_TAIL], &rhp->next);
Paul E. McKenney98059b92017-05-02 06:30:12 -0700351}
352
353/*
354 * Entrain the specified callback onto the specified rcu_segcblist at
355 * the end of the last non-empty segment. If the entire rcu_segcblist
356 * is empty, make no change, but return false.
357 *
358 * This is intended for use by rcu_barrier()-like primitives, -not-
359 * for normal grace-period use. IMPORTANT: The callback you enqueue
360 * will wait for all prior callbacks, NOT necessarily for a grace
361 * period. You have been warned.
362 */
363bool rcu_segcblist_entrain(struct rcu_segcblist *rsclp,
Joel Fernandes (Google)77a40f92019-08-30 12:36:32 -0400364 struct rcu_head *rhp)
Paul E. McKenney98059b92017-05-02 06:30:12 -0700365{
366 int i;
367
368 if (rcu_segcblist_n_cbs(rsclp) == 0)
369 return false;
Paul E. McKenneyeda669a2019-07-01 17:36:53 -0700370 rcu_segcblist_inc_len(rsclp);
Paul E. McKenney98059b92017-05-02 06:30:12 -0700371 smp_mb(); /* Ensure counts are updated before callback is entrained. */
372 rhp->next = NULL;
373 for (i = RCU_NEXT_TAIL; i > RCU_DONE_TAIL; i--)
374 if (rsclp->tails[i] != rsclp->tails[i - 1])
375 break;
Joel Fernandes (Google)ae5c2342020-09-23 11:22:09 -0400376 rcu_segcblist_inc_seglen(rsclp, i);
Paul E. McKenney76c69272019-05-13 14:36:11 -0700377 WRITE_ONCE(*rsclp->tails[i], rhp);
Paul E. McKenney98059b92017-05-02 06:30:12 -0700378 for (; i <= RCU_NEXT_TAIL; i++)
Paul E. McKenney76c69272019-05-13 14:36:11 -0700379 WRITE_ONCE(rsclp->tails[i], &rhp->next);
Paul E. McKenney98059b92017-05-02 06:30:12 -0700380 return true;
381}
382
383/*
Paul E. McKenney98059b92017-05-02 06:30:12 -0700384 * Extract only those callbacks ready to be invoked from the specified
385 * rcu_segcblist structure and place them in the specified rcu_cblist
386 * structure.
387 */
388void rcu_segcblist_extract_done_cbs(struct rcu_segcblist *rsclp,
389 struct rcu_cblist *rclp)
390{
391 int i;
392
393 if (!rcu_segcblist_ready_cbs(rsclp))
394 return; /* Nothing to do. */
Joel Fernandes (Google)ae5c2342020-09-23 11:22:09 -0400395 rclp->len = rcu_segcblist_get_seglen(rsclp, RCU_DONE_TAIL);
Paul E. McKenney98059b92017-05-02 06:30:12 -0700396 *rclp->tail = rsclp->head;
Paul E. McKenneye6060b42019-05-13 15:57:50 -0700397 WRITE_ONCE(rsclp->head, *rsclp->tails[RCU_DONE_TAIL]);
Paul E. McKenney76c69272019-05-13 14:36:11 -0700398 WRITE_ONCE(*rsclp->tails[RCU_DONE_TAIL], NULL);
Paul E. McKenney98059b92017-05-02 06:30:12 -0700399 rclp->tail = rsclp->tails[RCU_DONE_TAIL];
400 for (i = RCU_CBLIST_NSEGS - 1; i >= RCU_DONE_TAIL; i--)
401 if (rsclp->tails[i] == rsclp->tails[RCU_DONE_TAIL])
Paul E. McKenney76c69272019-05-13 14:36:11 -0700402 WRITE_ONCE(rsclp->tails[i], &rsclp->head);
Joel Fernandes (Google)ae5c2342020-09-23 11:22:09 -0400403 rcu_segcblist_set_seglen(rsclp, RCU_DONE_TAIL, 0);
Paul E. McKenney98059b92017-05-02 06:30:12 -0700404}
405
406/*
407 * Extract only those callbacks still pending (not yet ready to be
408 * invoked) from the specified rcu_segcblist structure and place them in
409 * the specified rcu_cblist structure. Note that this loses information
410 * about any callbacks that might have been partway done waiting for
411 * their grace period. Too bad! They will have to start over.
412 */
413void rcu_segcblist_extract_pend_cbs(struct rcu_segcblist *rsclp,
414 struct rcu_cblist *rclp)
415{
416 int i;
417
418 if (!rcu_segcblist_pend_cbs(rsclp))
419 return; /* Nothing to do. */
Joel Fernandes (Google)ae5c2342020-09-23 11:22:09 -0400420 rclp->len = 0;
Paul E. McKenney98059b92017-05-02 06:30:12 -0700421 *rclp->tail = *rsclp->tails[RCU_DONE_TAIL];
422 rclp->tail = rsclp->tails[RCU_NEXT_TAIL];
Paul E. McKenney76c69272019-05-13 14:36:11 -0700423 WRITE_ONCE(*rsclp->tails[RCU_DONE_TAIL], NULL);
Joel Fernandes (Google)ae5c2342020-09-23 11:22:09 -0400424 for (i = RCU_DONE_TAIL + 1; i < RCU_CBLIST_NSEGS; i++) {
425 rclp->len += rcu_segcblist_get_seglen(rsclp, i);
Paul E. McKenney76c69272019-05-13 14:36:11 -0700426 WRITE_ONCE(rsclp->tails[i], rsclp->tails[RCU_DONE_TAIL]);
Joel Fernandes (Google)ae5c2342020-09-23 11:22:09 -0400427 rcu_segcblist_set_seglen(rsclp, i, 0);
428 }
Paul E. McKenney98059b92017-05-02 06:30:12 -0700429}
430
431/*
432 * Insert counts from the specified rcu_cblist structure in the
433 * specified rcu_segcblist structure.
434 */
435void rcu_segcblist_insert_count(struct rcu_segcblist *rsclp,
436 struct rcu_cblist *rclp)
437{
Paul E. McKenneyeda669a2019-07-01 17:36:53 -0700438 rcu_segcblist_add_len(rsclp, rclp->len);
Paul E. McKenney98059b92017-05-02 06:30:12 -0700439}
440
441/*
442 * Move callbacks from the specified rcu_cblist to the beginning of the
443 * done-callbacks segment of the specified rcu_segcblist.
444 */
445void rcu_segcblist_insert_done_cbs(struct rcu_segcblist *rsclp,
446 struct rcu_cblist *rclp)
447{
448 int i;
449
450 if (!rclp->head)
451 return; /* No callbacks to move. */
Joel Fernandes (Google)ae5c2342020-09-23 11:22:09 -0400452 rcu_segcblist_add_seglen(rsclp, RCU_DONE_TAIL, rclp->len);
Paul E. McKenney98059b92017-05-02 06:30:12 -0700453 *rclp->tail = rsclp->head;
Paul E. McKenneye6060b42019-05-13 15:57:50 -0700454 WRITE_ONCE(rsclp->head, rclp->head);
Paul E. McKenney98059b92017-05-02 06:30:12 -0700455 for (i = RCU_DONE_TAIL; i < RCU_CBLIST_NSEGS; i++)
456 if (&rsclp->head == rsclp->tails[i])
Paul E. McKenney76c69272019-05-13 14:36:11 -0700457 WRITE_ONCE(rsclp->tails[i], rclp->tail);
Paul E. McKenney98059b92017-05-02 06:30:12 -0700458 else
459 break;
460 rclp->head = NULL;
461 rclp->tail = &rclp->head;
462}
463
464/*
465 * Move callbacks from the specified rcu_cblist to the end of the
466 * new-callbacks segment of the specified rcu_segcblist.
467 */
468void rcu_segcblist_insert_pend_cbs(struct rcu_segcblist *rsclp,
469 struct rcu_cblist *rclp)
470{
471 if (!rclp->head)
472 return; /* Nothing to do. */
Joel Fernandes (Google)ae5c2342020-09-23 11:22:09 -0400473
474 rcu_segcblist_add_seglen(rsclp, RCU_NEXT_TAIL, rclp->len);
Paul E. McKenney76c69272019-05-13 14:36:11 -0700475 WRITE_ONCE(*rsclp->tails[RCU_NEXT_TAIL], rclp->head);
476 WRITE_ONCE(rsclp->tails[RCU_NEXT_TAIL], rclp->tail);
Paul E. McKenney98059b92017-05-02 06:30:12 -0700477}
478
479/*
480 * Advance the callbacks in the specified rcu_segcblist structure based
481 * on the current value passed in for the grace-period counter.
482 */
483void rcu_segcblist_advance(struct rcu_segcblist *rsclp, unsigned long seq)
484{
485 int i, j;
486
487 WARN_ON_ONCE(!rcu_segcblist_is_enabled(rsclp));
488 if (rcu_segcblist_restempty(rsclp, RCU_DONE_TAIL))
489 return;
490
491 /*
492 * Find all callbacks whose ->gp_seq numbers indicate that they
493 * are ready to invoke, and put them into the RCU_DONE_TAIL segment.
494 */
495 for (i = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++) {
496 if (ULONG_CMP_LT(seq, rsclp->gp_seq[i]))
497 break;
Paul E. McKenney76c69272019-05-13 14:36:11 -0700498 WRITE_ONCE(rsclp->tails[RCU_DONE_TAIL], rsclp->tails[i]);
Joel Fernandes (Google)ae5c2342020-09-23 11:22:09 -0400499 rcu_segcblist_move_seglen(rsclp, i, RCU_DONE_TAIL);
Paul E. McKenney98059b92017-05-02 06:30:12 -0700500 }
501
502 /* If no callbacks moved, nothing more need be done. */
503 if (i == RCU_WAIT_TAIL)
504 return;
505
506 /* Clean up tail pointers that might have been misordered above. */
507 for (j = RCU_WAIT_TAIL; j < i; j++)
Paul E. McKenney76c69272019-05-13 14:36:11 -0700508 WRITE_ONCE(rsclp->tails[j], rsclp->tails[RCU_DONE_TAIL]);
Paul E. McKenney98059b92017-05-02 06:30:12 -0700509
510 /*
511 * Callbacks moved, so clean up the misordered ->tails[] pointers
512 * that now point into the middle of the list of ready-to-invoke
513 * callbacks. The overall effect is to copy down the later pointers
514 * into the gap that was created by the now-ready segments.
515 */
516 for (j = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++, j++) {
517 if (rsclp->tails[j] == rsclp->tails[RCU_NEXT_TAIL])
518 break; /* No more callbacks. */
Paul E. McKenney76c69272019-05-13 14:36:11 -0700519 WRITE_ONCE(rsclp->tails[j], rsclp->tails[i]);
Joel Fernandes (Google)ae5c2342020-09-23 11:22:09 -0400520 rcu_segcblist_move_seglen(rsclp, i, j);
Paul E. McKenney98059b92017-05-02 06:30:12 -0700521 rsclp->gp_seq[j] = rsclp->gp_seq[i];
522 }
523}
524
525/*
526 * "Accelerate" callbacks based on more-accurate grace-period information.
527 * The reason for this is that RCU does not synchronize the beginnings and
528 * ends of grace periods, and that callbacks are posted locally. This in
529 * turn means that the callbacks must be labelled conservatively early
530 * on, as getting exact information would degrade both performance and
531 * scalability. When more accurate grace-period information becomes
532 * available, previously posted callbacks can be "accelerated", marking
533 * them to complete at the end of the earlier grace period.
534 *
535 * This function operates on an rcu_segcblist structure, and also the
536 * grace-period sequence number seq at which new callbacks would become
537 * ready to invoke. Returns true if there are callbacks that won't be
538 * ready to invoke until seq, false otherwise.
539 */
540bool rcu_segcblist_accelerate(struct rcu_segcblist *rsclp, unsigned long seq)
541{
Joel Fernandes (Google)ae5c2342020-09-23 11:22:09 -0400542 int i, j;
Paul E. McKenney98059b92017-05-02 06:30:12 -0700543
544 WARN_ON_ONCE(!rcu_segcblist_is_enabled(rsclp));
545 if (rcu_segcblist_restempty(rsclp, RCU_DONE_TAIL))
546 return false;
547
548 /*
549 * Find the segment preceding the oldest segment of callbacks
550 * whose ->gp_seq[] completion is at or after that passed in via
551 * "seq", skipping any empty segments. This oldest segment, along
552 * with any later segments, can be merged in with any newly arrived
553 * callbacks in the RCU_NEXT_TAIL segment, and assigned "seq"
554 * as their ->gp_seq[] grace-period completion sequence number.
555 */
556 for (i = RCU_NEXT_READY_TAIL; i > RCU_DONE_TAIL; i--)
557 if (rsclp->tails[i] != rsclp->tails[i - 1] &&
558 ULONG_CMP_LT(rsclp->gp_seq[i], seq))
559 break;
560
561 /*
562 * If all the segments contain callbacks that correspond to
563 * earlier grace-period sequence numbers than "seq", leave.
564 * Assuming that the rcu_segcblist structure has enough
565 * segments in its arrays, this can only happen if some of
566 * the non-done segments contain callbacks that really are
567 * ready to invoke. This situation will get straightened
568 * out by the next call to rcu_segcblist_advance().
569 *
570 * Also advance to the oldest segment of callbacks whose
571 * ->gp_seq[] completion is at or after that passed in via "seq",
572 * skipping any empty segments.
Joel Fernandes (Google)53922272020-06-18 16:29:49 -0400573 *
574 * Note that segment "i" (and any lower-numbered segments
575 * containing older callbacks) will be unaffected, and their
576 * grace-period numbers remain unchanged. For example, if i ==
577 * WAIT_TAIL, then neither WAIT_TAIL nor DONE_TAIL will be touched.
578 * Instead, the CBs in NEXT_TAIL will be merged with those in
579 * NEXT_READY_TAIL and the grace-period number of NEXT_READY_TAIL
580 * would be updated. NEXT_TAIL would then be empty.
Paul E. McKenney98059b92017-05-02 06:30:12 -0700581 */
Joel Fernandes (Google)53922272020-06-18 16:29:49 -0400582 if (rcu_segcblist_restempty(rsclp, i) || ++i >= RCU_NEXT_TAIL)
Paul E. McKenney98059b92017-05-02 06:30:12 -0700583 return false;
584
Joel Fernandes (Google)ae5c2342020-09-23 11:22:09 -0400585 /* Accounting: everything below i is about to get merged into i. */
586 for (j = i + 1; j <= RCU_NEXT_TAIL; j++)
587 rcu_segcblist_move_seglen(rsclp, j, i);
588
Paul E. McKenney98059b92017-05-02 06:30:12 -0700589 /*
590 * Merge all later callbacks, including newly arrived callbacks,
591 * into the segment located by the for-loop above. Assign "seq"
592 * as the ->gp_seq[] value in order to correctly handle the case
593 * where there were no pending callbacks in the rcu_segcblist
594 * structure other than in the RCU_NEXT_TAIL segment.
595 */
596 for (; i < RCU_NEXT_TAIL; i++) {
Paul E. McKenney76c69272019-05-13 14:36:11 -0700597 WRITE_ONCE(rsclp->tails[i], rsclp->tails[RCU_NEXT_TAIL]);
Paul E. McKenney98059b92017-05-02 06:30:12 -0700598 rsclp->gp_seq[i] = seq;
599 }
600 return true;
601}
602
603/*
Paul E. McKenneyf2dbe4a2017-06-27 07:44:06 -0700604 * Merge the source rcu_segcblist structure into the destination
605 * rcu_segcblist structure, then initialize the source. Any pending
606 * callbacks from the source get to start over. It is best to
607 * advance and accelerate both the destination and the source
608 * before merging.
609 */
610void rcu_segcblist_merge(struct rcu_segcblist *dst_rsclp,
611 struct rcu_segcblist *src_rsclp)
612{
613 struct rcu_cblist donecbs;
614 struct rcu_cblist pendcbs;
615
Joel Fernandes (Google)ae5c2342020-09-23 11:22:09 -0400616 lockdep_assert_cpus_held();
617
Paul E. McKenneyf2dbe4a2017-06-27 07:44:06 -0700618 rcu_cblist_init(&donecbs);
619 rcu_cblist_init(&pendcbs);
Joel Fernandes (Google)ae5c2342020-09-23 11:22:09 -0400620
Paul E. McKenneyf2dbe4a2017-06-27 07:44:06 -0700621 rcu_segcblist_extract_done_cbs(src_rsclp, &donecbs);
622 rcu_segcblist_extract_pend_cbs(src_rsclp, &pendcbs);
Joel Fernandes (Google)ae5c2342020-09-23 11:22:09 -0400623
624 /*
625 * No need smp_mb() before setting length to 0, because CPU hotplug
626 * lock excludes rcu_barrier.
627 */
628 rcu_segcblist_set_len(src_rsclp, 0);
629
Paul E. McKenneyf2dbe4a2017-06-27 07:44:06 -0700630 rcu_segcblist_insert_count(dst_rsclp, &donecbs);
Joel Fernandes (Google)ae5c2342020-09-23 11:22:09 -0400631 rcu_segcblist_insert_count(dst_rsclp, &pendcbs);
Paul E. McKenneyf2dbe4a2017-06-27 07:44:06 -0700632 rcu_segcblist_insert_done_cbs(dst_rsclp, &donecbs);
633 rcu_segcblist_insert_pend_cbs(dst_rsclp, &pendcbs);
Joel Fernandes (Google)ae5c2342020-09-23 11:22:09 -0400634
Paul E. McKenneyf2dbe4a2017-06-27 07:44:06 -0700635 rcu_segcblist_init(src_rsclp);
636}