xref: /openbmc/linux/kernel/rcu/rcu_segcblist.c (revision 9a87ffc99ec8eb8d35eed7c4f816d75f5cc9662e)
1eb7935e4SPaul E. McKenney // SPDX-License-Identifier: GPL-2.0+
298059b98SPaul E. McKenney /*
398059b98SPaul E. McKenney  * RCU segmented callback lists, function definitions
498059b98SPaul E. McKenney  *
598059b98SPaul E. McKenney  * Copyright IBM Corporation, 2017
698059b98SPaul E. McKenney  *
7eb7935e4SPaul E. McKenney  * Authors: Paul E. McKenney <paulmck@linux.ibm.com>
898059b98SPaul E. McKenney  */
998059b98SPaul E. McKenney 
10ae5c2341SJoel Fernandes (Google) #include <linux/cpu.h>
1198059b98SPaul E. McKenney #include <linux/interrupt.h>
12ae5c2341SJoel Fernandes (Google) #include <linux/kernel.h>
13ae5c2341SJoel Fernandes (Google) #include <linux/types.h>
1498059b98SPaul E. McKenney 
1598059b98SPaul E. McKenney #include "rcu_segcblist.h"
1698059b98SPaul E. McKenney 
1798059b98SPaul E. McKenney /* Initialize simple callback list. */
rcu_cblist_init(struct rcu_cblist * rclp)1898059b98SPaul E. McKenney void rcu_cblist_init(struct rcu_cblist *rclp)
1998059b98SPaul E. McKenney {
2098059b98SPaul E. McKenney 	rclp->head = NULL;
2198059b98SPaul E. McKenney 	rclp->tail = &rclp->head;
2298059b98SPaul E. McKenney 	rclp->len = 0;
2398059b98SPaul E. McKenney }
2498059b98SPaul E. McKenney 
2598059b98SPaul E. McKenney /*
26eda669a6SPaul E. McKenney  * Enqueue an rcu_head structure onto the specified callback list.
27eda669a6SPaul E. McKenney  */
rcu_cblist_enqueue(struct rcu_cblist * rclp,struct rcu_head * rhp)28eda669a6SPaul E. McKenney void rcu_cblist_enqueue(struct rcu_cblist *rclp, struct rcu_head *rhp)
29eda669a6SPaul E. McKenney {
30eda669a6SPaul E. McKenney 	*rclp->tail = rhp;
31eda669a6SPaul E. McKenney 	rclp->tail = &rhp->next;
32eda669a6SPaul E. McKenney 	WRITE_ONCE(rclp->len, rclp->len + 1);
33eda669a6SPaul E. McKenney }
34eda669a6SPaul E. McKenney 
35eda669a6SPaul E. McKenney /*
36d1b222c6SPaul E. McKenney  * Flush the second rcu_cblist structure onto the first one, obliterating
37d1b222c6SPaul E. McKenney  * any contents of the first.  If rhp is non-NULL, enqueue it as the sole
38d1b222c6SPaul E. McKenney  * element of the second rcu_cblist structure, but ensuring that the second
39d1b222c6SPaul E. McKenney  * rcu_cblist structure, if initially non-empty, always appears non-empty
40d1b222c6SPaul E. McKenney  * throughout the process.  If rdp is NULL, the second rcu_cblist structure
41d1b222c6SPaul E. McKenney  * is instead initialized to empty.
42d1b222c6SPaul E. McKenney  */
rcu_cblist_flush_enqueue(struct rcu_cblist * drclp,struct rcu_cblist * srclp,struct rcu_head * rhp)43d1b222c6SPaul E. McKenney void rcu_cblist_flush_enqueue(struct rcu_cblist *drclp,
44d1b222c6SPaul E. McKenney 			      struct rcu_cblist *srclp,
45d1b222c6SPaul E. McKenney 			      struct rcu_head *rhp)
46d1b222c6SPaul E. McKenney {
47d1b222c6SPaul E. McKenney 	drclp->head = srclp->head;
48d1b222c6SPaul E. McKenney 	if (drclp->head)
49d1b222c6SPaul E. McKenney 		drclp->tail = srclp->tail;
50d1b222c6SPaul E. McKenney 	else
51d1b222c6SPaul E. McKenney 		drclp->tail = &drclp->head;
52d1b222c6SPaul E. McKenney 	drclp->len = srclp->len;
53d1b222c6SPaul E. McKenney 	if (!rhp) {
54d1b222c6SPaul E. McKenney 		rcu_cblist_init(srclp);
55d1b222c6SPaul E. McKenney 	} else {
56d1b222c6SPaul E. McKenney 		rhp->next = NULL;
57d1b222c6SPaul E. McKenney 		srclp->head = rhp;
58d1b222c6SPaul E. McKenney 		srclp->tail = &rhp->next;
59d1b222c6SPaul E. McKenney 		WRITE_ONCE(srclp->len, 1);
60d1b222c6SPaul E. McKenney 	}
61d1b222c6SPaul E. McKenney }
62d1b222c6SPaul E. McKenney 
63d1b222c6SPaul E. McKenney /*
6498059b98SPaul E. McKenney  * Dequeue the oldest rcu_head structure from the specified callback
6577a40f97SJoel Fernandes (Google)  * list.
6698059b98SPaul E. McKenney  */
rcu_cblist_dequeue(struct rcu_cblist * rclp)6798059b98SPaul E. McKenney struct rcu_head *rcu_cblist_dequeue(struct rcu_cblist *rclp)
6898059b98SPaul E. McKenney {
6998059b98SPaul E. McKenney 	struct rcu_head *rhp;
7098059b98SPaul E. McKenney 
7198059b98SPaul E. McKenney 	rhp = rclp->head;
7298059b98SPaul E. McKenney 	if (!rhp)
7398059b98SPaul E. McKenney 		return NULL;
7498059b98SPaul E. McKenney 	rclp->len--;
7598059b98SPaul E. McKenney 	rclp->head = rhp->next;
7698059b98SPaul E. McKenney 	if (!rclp->head)
7798059b98SPaul E. McKenney 		rclp->tail = &rclp->head;
7898059b98SPaul E. McKenney 	return rhp;
7998059b98SPaul E. McKenney }
8098059b98SPaul E. McKenney 
81eda669a6SPaul E. McKenney /* Set the length of an rcu_segcblist structure. */
rcu_segcblist_set_len(struct rcu_segcblist * rsclp,long v)821d24dd4eSkbuild test robot static void rcu_segcblist_set_len(struct rcu_segcblist *rsclp, long v)
83eda669a6SPaul E. McKenney {
84eda669a6SPaul E. McKenney #ifdef CONFIG_RCU_NOCB_CPU
85eda669a6SPaul E. McKenney 	atomic_long_set(&rsclp->len, v);
86eda669a6SPaul E. McKenney #else
87eda669a6SPaul E. McKenney 	WRITE_ONCE(rsclp->len, v);
88eda669a6SPaul E. McKenney #endif
89eda669a6SPaul E. McKenney }
90eda669a6SPaul E. McKenney 
91ae5c2341SJoel Fernandes (Google) /* Get the length of a segment of the rcu_segcblist structure. */
rcu_segcblist_get_seglen(struct rcu_segcblist * rsclp,int seg)92*253cbbffSPaul E. McKenney long rcu_segcblist_get_seglen(struct rcu_segcblist *rsclp, int seg)
93ae5c2341SJoel Fernandes (Google) {
94ae5c2341SJoel Fernandes (Google) 	return READ_ONCE(rsclp->seglen[seg]);
95ae5c2341SJoel Fernandes (Google) }
96ae5c2341SJoel Fernandes (Google) 
97b4e6039eSJoel Fernandes (Google) /* Return number of callbacks in segmented callback list by summing seglen. */
rcu_segcblist_n_segment_cbs(struct rcu_segcblist * rsclp)98b4e6039eSJoel Fernandes (Google) long rcu_segcblist_n_segment_cbs(struct rcu_segcblist *rsclp)
99b4e6039eSJoel Fernandes (Google) {
100b4e6039eSJoel Fernandes (Google) 	long len = 0;
101b4e6039eSJoel Fernandes (Google) 	int i;
102b4e6039eSJoel Fernandes (Google) 
103b4e6039eSJoel Fernandes (Google) 	for (i = RCU_DONE_TAIL; i < RCU_CBLIST_NSEGS; i++)
104b4e6039eSJoel Fernandes (Google) 		len += rcu_segcblist_get_seglen(rsclp, i);
105b4e6039eSJoel Fernandes (Google) 
106b4e6039eSJoel Fernandes (Google) 	return len;
107b4e6039eSJoel Fernandes (Google) }
108b4e6039eSJoel Fernandes (Google) 
109ae5c2341SJoel Fernandes (Google) /* Set the length of a segment of the rcu_segcblist structure. */
rcu_segcblist_set_seglen(struct rcu_segcblist * rsclp,int seg,long v)110ae5c2341SJoel Fernandes (Google) static void rcu_segcblist_set_seglen(struct rcu_segcblist *rsclp, int seg, long v)
111ae5c2341SJoel Fernandes (Google) {
112ae5c2341SJoel Fernandes (Google) 	WRITE_ONCE(rsclp->seglen[seg], v);
113ae5c2341SJoel Fernandes (Google) }
114ae5c2341SJoel Fernandes (Google) 
115ae5c2341SJoel Fernandes (Google) /* Increase the numeric length of a segment by a specified amount. */
rcu_segcblist_add_seglen(struct rcu_segcblist * rsclp,int seg,long v)116ae5c2341SJoel Fernandes (Google) static void rcu_segcblist_add_seglen(struct rcu_segcblist *rsclp, int seg, long v)
117ae5c2341SJoel Fernandes (Google) {
118ae5c2341SJoel Fernandes (Google) 	WRITE_ONCE(rsclp->seglen[seg], rsclp->seglen[seg] + v);
119ae5c2341SJoel Fernandes (Google) }
120ae5c2341SJoel Fernandes (Google) 
121ae5c2341SJoel Fernandes (Google) /* Move from's segment length to to's segment. */
rcu_segcblist_move_seglen(struct rcu_segcblist * rsclp,int from,int to)122ae5c2341SJoel Fernandes (Google) static void rcu_segcblist_move_seglen(struct rcu_segcblist *rsclp, int from, int to)
123ae5c2341SJoel Fernandes (Google) {
124ae5c2341SJoel Fernandes (Google) 	long len;
125ae5c2341SJoel Fernandes (Google) 
126ae5c2341SJoel Fernandes (Google) 	if (from == to)
127ae5c2341SJoel Fernandes (Google) 		return;
128ae5c2341SJoel Fernandes (Google) 
129ae5c2341SJoel Fernandes (Google) 	len = rcu_segcblist_get_seglen(rsclp, from);
130ae5c2341SJoel Fernandes (Google) 	if (!len)
131ae5c2341SJoel Fernandes (Google) 		return;
132ae5c2341SJoel Fernandes (Google) 
133ae5c2341SJoel Fernandes (Google) 	rcu_segcblist_add_seglen(rsclp, to, len);
134ae5c2341SJoel Fernandes (Google) 	rcu_segcblist_set_seglen(rsclp, from, 0);
135ae5c2341SJoel Fernandes (Google) }
136ae5c2341SJoel Fernandes (Google) 
137ae5c2341SJoel Fernandes (Google) /* Increment segment's length. */
rcu_segcblist_inc_seglen(struct rcu_segcblist * rsclp,int seg)138ae5c2341SJoel Fernandes (Google) static void rcu_segcblist_inc_seglen(struct rcu_segcblist *rsclp, int seg)
139ae5c2341SJoel Fernandes (Google) {
140ae5c2341SJoel Fernandes (Google) 	rcu_segcblist_add_seglen(rsclp, seg, 1);
141ae5c2341SJoel Fernandes (Google) }
142ae5c2341SJoel Fernandes (Google) 
143eda669a6SPaul E. McKenney /*
144eda669a6SPaul E. McKenney  * Increase the numeric length of an rcu_segcblist structure by the
145eda669a6SPaul E. McKenney  * specified amount, which can be negative.  This can cause the ->len
146eda669a6SPaul E. McKenney  * field to disagree with the actual number of callbacks on the structure.
147eda669a6SPaul E. McKenney  * This increase is fully ordered with respect to the callers accesses
148eda669a6SPaul E. McKenney  * both before and after.
149c2e13112SJoel Fernandes (Google)  *
150c2e13112SJoel Fernandes (Google)  * So why on earth is a memory barrier required both before and after
151c2e13112SJoel Fernandes (Google)  * the update to the ->len field???
152c2e13112SJoel Fernandes (Google)  *
153c2e13112SJoel Fernandes (Google)  * The reason is that rcu_barrier() locklessly samples each CPU's ->len
154c2e13112SJoel Fernandes (Google)  * field, and if a given CPU's field is zero, avoids IPIing that CPU.
155c2e13112SJoel Fernandes (Google)  * This can of course race with both queuing and invoking of callbacks.
156c2e13112SJoel Fernandes (Google)  * Failing to correctly handle either of these races could result in
157c2e13112SJoel Fernandes (Google)  * rcu_barrier() failing to IPI a CPU that actually had callbacks queued
158c2e13112SJoel Fernandes (Google)  * which rcu_barrier() was obligated to wait on.  And if rcu_barrier()
159c2e13112SJoel Fernandes (Google)  * failed to wait on such a callback, unloading certain kernel modules
160c2e13112SJoel Fernandes (Google)  * would result in calls to functions whose code was no longer present in
161c2e13112SJoel Fernandes (Google)  * the kernel, for but one example.
162c2e13112SJoel Fernandes (Google)  *
163c2e13112SJoel Fernandes (Google)  * Therefore, ->len transitions from 1->0 and 0->1 have to be carefully
164c2e13112SJoel Fernandes (Google)  * ordered with respect with both list modifications and the rcu_barrier().
165c2e13112SJoel Fernandes (Google)  *
166c2e13112SJoel Fernandes (Google)  * The queuing case is CASE 1 and the invoking case is CASE 2.
167c2e13112SJoel Fernandes (Google)  *
168c2e13112SJoel Fernandes (Google)  * CASE 1: Suppose that CPU 0 has no callbacks queued, but invokes
169c2e13112SJoel Fernandes (Google)  * call_rcu() just as CPU 1 invokes rcu_barrier().  CPU 0's ->len field
170c2e13112SJoel Fernandes (Google)  * will transition from 0->1, which is one of the transitions that must
171c2e13112SJoel Fernandes (Google)  * be handled carefully.  Without the full memory barriers after the ->len
172c2e13112SJoel Fernandes (Google)  * update and at the beginning of rcu_barrier(), the following could happen:
173c2e13112SJoel Fernandes (Google)  *
174c2e13112SJoel Fernandes (Google)  * CPU 0				CPU 1
175c2e13112SJoel Fernandes (Google)  *
176c2e13112SJoel Fernandes (Google)  * call_rcu().
177c2e13112SJoel Fernandes (Google)  *					rcu_barrier() sees ->len as 0.
178c2e13112SJoel Fernandes (Google)  * set ->len = 1.
179c2e13112SJoel Fernandes (Google)  *					rcu_barrier() does nothing.
180c2e13112SJoel Fernandes (Google)  *					module is unloaded.
181c2e13112SJoel Fernandes (Google)  * callback invokes unloaded function!
182c2e13112SJoel Fernandes (Google)  *
183c2e13112SJoel Fernandes (Google)  * With the full barriers, any case where rcu_barrier() sees ->len as 0 will
184c2e13112SJoel Fernandes (Google)  * have unambiguously preceded the return from the racing call_rcu(), which
185c2e13112SJoel Fernandes (Google)  * means that this call_rcu() invocation is OK to not wait on.  After all,
186c2e13112SJoel Fernandes (Google)  * you are supposed to make sure that any problematic call_rcu() invocations
187c2e13112SJoel Fernandes (Google)  * happen before the rcu_barrier().
188c2e13112SJoel Fernandes (Google)  *
189c2e13112SJoel Fernandes (Google)  *
190c2e13112SJoel Fernandes (Google)  * CASE 2: Suppose that CPU 0 is invoking its last callback just as
191c2e13112SJoel Fernandes (Google)  * CPU 1 invokes rcu_barrier().  CPU 0's ->len field will transition from
192c2e13112SJoel Fernandes (Google)  * 1->0, which is one of the transitions that must be handled carefully.
193c2e13112SJoel Fernandes (Google)  * Without the full memory barriers before the ->len update and at the
194c2e13112SJoel Fernandes (Google)  * end of rcu_barrier(), the following could happen:
195c2e13112SJoel Fernandes (Google)  *
196c2e13112SJoel Fernandes (Google)  * CPU 0				CPU 1
197c2e13112SJoel Fernandes (Google)  *
198c2e13112SJoel Fernandes (Google)  * start invoking last callback
199c2e13112SJoel Fernandes (Google)  * set ->len = 0 (reordered)
200c2e13112SJoel Fernandes (Google)  *					rcu_barrier() sees ->len as 0
201c2e13112SJoel Fernandes (Google)  *					rcu_barrier() does nothing.
202c2e13112SJoel Fernandes (Google)  *					module is unloaded
203c2e13112SJoel Fernandes (Google)  * callback executing after unloaded!
204c2e13112SJoel Fernandes (Google)  *
205c2e13112SJoel Fernandes (Google)  * With the full barriers, any case where rcu_barrier() sees ->len as 0
206c2e13112SJoel Fernandes (Google)  * will be fully ordered after the completion of the callback function,
207c2e13112SJoel Fernandes (Google)  * so that the module unloading operation is completely safe.
208c2e13112SJoel Fernandes (Google)  *
209eda669a6SPaul E. McKenney  */
rcu_segcblist_add_len(struct rcu_segcblist * rsclp,long v)2106bc33582SJoel Fernandes (Google) void rcu_segcblist_add_len(struct rcu_segcblist *rsclp, long v)
211eda669a6SPaul E. McKenney {
212eda669a6SPaul E. McKenney #ifdef CONFIG_RCU_NOCB_CPU
213c2e13112SJoel Fernandes (Google) 	smp_mb__before_atomic(); // Read header comment above.
214eda669a6SPaul E. McKenney 	atomic_long_add(v, &rsclp->len);
215c2e13112SJoel Fernandes (Google) 	smp_mb__after_atomic();  // Read header comment above.
216eda669a6SPaul E. McKenney #else
217c2e13112SJoel Fernandes (Google) 	smp_mb(); // Read header comment above.
218eda669a6SPaul E. McKenney 	WRITE_ONCE(rsclp->len, rsclp->len + v);
219c2e13112SJoel Fernandes (Google) 	smp_mb(); // Read header comment above.
220eda669a6SPaul E. McKenney #endif
221eda669a6SPaul E. McKenney }
222eda669a6SPaul E. McKenney 
223eda669a6SPaul E. McKenney /*
224eda669a6SPaul E. McKenney  * Increase the numeric length of an rcu_segcblist structure by one.
225eda669a6SPaul E. McKenney  * This can cause the ->len field to disagree with the actual number of
226eda669a6SPaul E. McKenney  * callbacks on the structure.  This increase is fully ordered with respect
227eda669a6SPaul E. McKenney  * to the callers accesses both before and after.
228eda669a6SPaul E. McKenney  */
rcu_segcblist_inc_len(struct rcu_segcblist * rsclp)229eda669a6SPaul E. McKenney void rcu_segcblist_inc_len(struct rcu_segcblist *rsclp)
230eda669a6SPaul E. McKenney {
231eda669a6SPaul E. McKenney 	rcu_segcblist_add_len(rsclp, 1);
232eda669a6SPaul E. McKenney }
233eda669a6SPaul E. McKenney 
234eda669a6SPaul E. McKenney /*
23598059b98SPaul E. McKenney  * Initialize an rcu_segcblist structure.
23698059b98SPaul E. McKenney  */
rcu_segcblist_init(struct rcu_segcblist * rsclp)23798059b98SPaul E. McKenney void rcu_segcblist_init(struct rcu_segcblist *rsclp)
23898059b98SPaul E. McKenney {
23998059b98SPaul E. McKenney 	int i;
24098059b98SPaul E. McKenney 
24198059b98SPaul E. McKenney 	BUILD_BUG_ON(RCU_NEXT_TAIL + 1 != ARRAY_SIZE(rsclp->gp_seq));
24298059b98SPaul E. McKenney 	BUILD_BUG_ON(ARRAY_SIZE(rsclp->tails) != ARRAY_SIZE(rsclp->gp_seq));
24398059b98SPaul E. McKenney 	rsclp->head = NULL;
244ae5c2341SJoel Fernandes (Google) 	for (i = 0; i < RCU_CBLIST_NSEGS; i++) {
24598059b98SPaul E. McKenney 		rsclp->tails[i] = &rsclp->head;
246ae5c2341SJoel Fernandes (Google) 		rcu_segcblist_set_seglen(rsclp, i, 0);
247ae5c2341SJoel Fernandes (Google) 	}
248eda669a6SPaul E. McKenney 	rcu_segcblist_set_len(rsclp, 0);
24965e56032SFrederic Weisbecker 	rcu_segcblist_set_flags(rsclp, SEGCBLIST_ENABLED);
25098059b98SPaul E. McKenney }
25198059b98SPaul E. McKenney 
25298059b98SPaul E. McKenney /*
25398059b98SPaul E. McKenney  * Disable the specified rcu_segcblist structure, so that callbacks can
25498059b98SPaul E. McKenney  * no longer be posted to it.  This structure must be empty.
25598059b98SPaul E. McKenney  */
rcu_segcblist_disable(struct rcu_segcblist * rsclp)25698059b98SPaul E. McKenney void rcu_segcblist_disable(struct rcu_segcblist *rsclp)
25798059b98SPaul E. McKenney {
25898059b98SPaul E. McKenney 	WARN_ON_ONCE(!rcu_segcblist_empty(rsclp));
25998059b98SPaul E. McKenney 	WARN_ON_ONCE(rcu_segcblist_n_cbs(rsclp));
26065e56032SFrederic Weisbecker 	rcu_segcblist_clear_flags(rsclp, SEGCBLIST_ENABLED);
26198059b98SPaul E. McKenney }
26298059b98SPaul E. McKenney 
26398059b98SPaul E. McKenney /*
264213d56bfSFrederic Weisbecker  * Mark the specified rcu_segcblist structure as offloaded (or not)
265ce5215c1SPaul E. McKenney  */
rcu_segcblist_offload(struct rcu_segcblist * rsclp,bool offload)266d97b0781SFrederic Weisbecker void rcu_segcblist_offload(struct rcu_segcblist *rsclp, bool offload)
267ce5215c1SPaul E. McKenney {
268fbb94cbdSFrederic Weisbecker 	if (offload)
269213d56bfSFrederic Weisbecker 		rcu_segcblist_set_flags(rsclp, SEGCBLIST_LOCKING | SEGCBLIST_OFFLOADED);
270fbb94cbdSFrederic Weisbecker 	else
271d97b0781SFrederic Weisbecker 		rcu_segcblist_clear_flags(rsclp, SEGCBLIST_OFFLOADED);
272d97b0781SFrederic Weisbecker }
273ce5215c1SPaul E. McKenney 
274ce5215c1SPaul E. McKenney /*
27598059b98SPaul E. McKenney  * Does the specified rcu_segcblist structure contain callbacks that
27698059b98SPaul E. McKenney  * are ready to be invoked?
27798059b98SPaul E. McKenney  */
rcu_segcblist_ready_cbs(struct rcu_segcblist * rsclp)27898059b98SPaul E. McKenney bool rcu_segcblist_ready_cbs(struct rcu_segcblist *rsclp)
27998059b98SPaul E. McKenney {
28098059b98SPaul E. McKenney 	return rcu_segcblist_is_enabled(rsclp) &&
281bfeebe24SPaul E. McKenney 	       &rsclp->head != READ_ONCE(rsclp->tails[RCU_DONE_TAIL]);
28298059b98SPaul E. McKenney }
28398059b98SPaul E. McKenney 
28498059b98SPaul E. McKenney /*
28598059b98SPaul E. McKenney  * Does the specified rcu_segcblist structure contain callbacks that
28698059b98SPaul E. McKenney  * are still pending, that is, not yet ready to be invoked?
28798059b98SPaul E. McKenney  */
rcu_segcblist_pend_cbs(struct rcu_segcblist * rsclp)28898059b98SPaul E. McKenney bool rcu_segcblist_pend_cbs(struct rcu_segcblist *rsclp)
28998059b98SPaul E. McKenney {
29098059b98SPaul E. McKenney 	return rcu_segcblist_is_enabled(rsclp) &&
29198059b98SPaul E. McKenney 	       !rcu_segcblist_restempty(rsclp, RCU_DONE_TAIL);
29298059b98SPaul E. McKenney }
29398059b98SPaul E. McKenney 
29498059b98SPaul E. McKenney /*
29598059b98SPaul E. McKenney  * Return a pointer to the first callback in the specified rcu_segcblist
29698059b98SPaul E. McKenney  * structure.  This is useful for diagnostics.
29798059b98SPaul E. McKenney  */
rcu_segcblist_first_cb(struct rcu_segcblist * rsclp)29898059b98SPaul E. McKenney struct rcu_head *rcu_segcblist_first_cb(struct rcu_segcblist *rsclp)
29998059b98SPaul E. McKenney {
30098059b98SPaul E. McKenney 	if (rcu_segcblist_is_enabled(rsclp))
30198059b98SPaul E. McKenney 		return rsclp->head;
30298059b98SPaul E. McKenney 	return NULL;
30398059b98SPaul E. McKenney }
30498059b98SPaul E. McKenney 
30598059b98SPaul E. McKenney /*
30698059b98SPaul E. McKenney  * Return a pointer to the first pending callback in the specified
30798059b98SPaul E. McKenney  * rcu_segcblist structure.  This is useful just after posting a given
30898059b98SPaul E. McKenney  * callback -- if that callback is the first pending callback, then
30998059b98SPaul E. McKenney  * you cannot rely on someone else having already started up the required
31098059b98SPaul E. McKenney  * grace period.
31198059b98SPaul E. McKenney  */
rcu_segcblist_first_pend_cb(struct rcu_segcblist * rsclp)31298059b98SPaul E. McKenney struct rcu_head *rcu_segcblist_first_pend_cb(struct rcu_segcblist *rsclp)
31398059b98SPaul E. McKenney {
31498059b98SPaul E. McKenney 	if (rcu_segcblist_is_enabled(rsclp))
31598059b98SPaul E. McKenney 		return *rsclp->tails[RCU_DONE_TAIL];
31698059b98SPaul E. McKenney 	return NULL;
31798059b98SPaul E. McKenney }
31898059b98SPaul E. McKenney 
31998059b98SPaul E. McKenney /*
3205d6742b3SPaul E. McKenney  * Return false if there are no CBs awaiting grace periods, otherwise,
3215d6742b3SPaul E. McKenney  * return true and store the nearest waited-upon grace period into *lp.
3225d6742b3SPaul E. McKenney  */
rcu_segcblist_nextgp(struct rcu_segcblist * rsclp,unsigned long * lp)3235d6742b3SPaul E. McKenney bool rcu_segcblist_nextgp(struct rcu_segcblist *rsclp, unsigned long *lp)
3245d6742b3SPaul E. McKenney {
3255d6742b3SPaul E. McKenney 	if (!rcu_segcblist_pend_cbs(rsclp))
3265d6742b3SPaul E. McKenney 		return false;
3275d6742b3SPaul E. McKenney 	*lp = rsclp->gp_seq[RCU_WAIT_TAIL];
3285d6742b3SPaul E. McKenney 	return true;
3295d6742b3SPaul E. McKenney }
3305d6742b3SPaul E. McKenney 
3315d6742b3SPaul E. McKenney /*
33298059b98SPaul E. McKenney  * Enqueue the specified callback onto the specified rcu_segcblist
33398059b98SPaul E. McKenney  * structure, updating accounting as needed.  Note that the ->len
33498059b98SPaul E. McKenney  * field may be accessed locklessly, hence the WRITE_ONCE().
33598059b98SPaul E. McKenney  * The ->len field is used by rcu_barrier() and friends to determine
33698059b98SPaul E. McKenney  * if it must post a callback on this structure, and it is OK
33798059b98SPaul E. McKenney  * for rcu_barrier() to sometimes post callbacks needlessly, but
33898059b98SPaul E. McKenney  * absolutely not OK for it to ever miss posting a callback.
33998059b98SPaul E. McKenney  */
rcu_segcblist_enqueue(struct rcu_segcblist * rsclp,struct rcu_head * rhp)34098059b98SPaul E. McKenney void rcu_segcblist_enqueue(struct rcu_segcblist *rsclp,
34177a40f97SJoel Fernandes (Google) 			   struct rcu_head *rhp)
34298059b98SPaul E. McKenney {
343eda669a6SPaul E. McKenney 	rcu_segcblist_inc_len(rsclp);
344ae5c2341SJoel Fernandes (Google) 	rcu_segcblist_inc_seglen(rsclp, RCU_NEXT_TAIL);
34598059b98SPaul E. McKenney 	rhp->next = NULL;
34676c6927cSPaul E. McKenney 	WRITE_ONCE(*rsclp->tails[RCU_NEXT_TAIL], rhp);
34776c6927cSPaul E. McKenney 	WRITE_ONCE(rsclp->tails[RCU_NEXT_TAIL], &rhp->next);
34898059b98SPaul E. McKenney }
34998059b98SPaul E. McKenney 
35098059b98SPaul E. McKenney /*
35198059b98SPaul E. McKenney  * Entrain the specified callback onto the specified rcu_segcblist at
35298059b98SPaul E. McKenney  * the end of the last non-empty segment.  If the entire rcu_segcblist
35398059b98SPaul E. McKenney  * is empty, make no change, but return false.
35498059b98SPaul E. McKenney  *
35598059b98SPaul E. McKenney  * This is intended for use by rcu_barrier()-like primitives, -not-
35698059b98SPaul E. McKenney  * for normal grace-period use.  IMPORTANT:  The callback you enqueue
35798059b98SPaul E. McKenney  * will wait for all prior callbacks, NOT necessarily for a grace
35898059b98SPaul E. McKenney  * period.  You have been warned.
35998059b98SPaul E. McKenney  */
rcu_segcblist_entrain(struct rcu_segcblist * rsclp,struct rcu_head * rhp)36098059b98SPaul E. McKenney bool rcu_segcblist_entrain(struct rcu_segcblist *rsclp,
36177a40f97SJoel Fernandes (Google) 			   struct rcu_head *rhp)
36298059b98SPaul E. McKenney {
36398059b98SPaul E. McKenney 	int i;
36498059b98SPaul E. McKenney 
36598059b98SPaul E. McKenney 	if (rcu_segcblist_n_cbs(rsclp) == 0)
36698059b98SPaul E. McKenney 		return false;
367eda669a6SPaul E. McKenney 	rcu_segcblist_inc_len(rsclp);
36898059b98SPaul E. McKenney 	smp_mb(); /* Ensure counts are updated before callback is entrained. */
36998059b98SPaul E. McKenney 	rhp->next = NULL;
37098059b98SPaul E. McKenney 	for (i = RCU_NEXT_TAIL; i > RCU_DONE_TAIL; i--)
37198059b98SPaul E. McKenney 		if (rsclp->tails[i] != rsclp->tails[i - 1])
37298059b98SPaul E. McKenney 			break;
373ae5c2341SJoel Fernandes (Google) 	rcu_segcblist_inc_seglen(rsclp, i);
37476c6927cSPaul E. McKenney 	WRITE_ONCE(*rsclp->tails[i], rhp);
37598059b98SPaul E. McKenney 	for (; i <= RCU_NEXT_TAIL; i++)
37676c6927cSPaul E. McKenney 		WRITE_ONCE(rsclp->tails[i], &rhp->next);
37798059b98SPaul E. McKenney 	return true;
37898059b98SPaul E. McKenney }
37998059b98SPaul E. McKenney 
38098059b98SPaul E. McKenney /*
38198059b98SPaul E. McKenney  * Extract only those callbacks ready to be invoked from the specified
38298059b98SPaul E. McKenney  * rcu_segcblist structure and place them in the specified rcu_cblist
38398059b98SPaul E. McKenney  * structure.
38498059b98SPaul E. McKenney  */
rcu_segcblist_extract_done_cbs(struct rcu_segcblist * rsclp,struct rcu_cblist * rclp)38598059b98SPaul E. McKenney void rcu_segcblist_extract_done_cbs(struct rcu_segcblist *rsclp,
38698059b98SPaul E. McKenney 				    struct rcu_cblist *rclp)
38798059b98SPaul E. McKenney {
38898059b98SPaul E. McKenney 	int i;
38998059b98SPaul E. McKenney 
39098059b98SPaul E. McKenney 	if (!rcu_segcblist_ready_cbs(rsclp))
39198059b98SPaul E. McKenney 		return; /* Nothing to do. */
392ae5c2341SJoel Fernandes (Google) 	rclp->len = rcu_segcblist_get_seglen(rsclp, RCU_DONE_TAIL);
39398059b98SPaul E. McKenney 	*rclp->tail = rsclp->head;
394e6060b41SPaul E. McKenney 	WRITE_ONCE(rsclp->head, *rsclp->tails[RCU_DONE_TAIL]);
39576c6927cSPaul E. McKenney 	WRITE_ONCE(*rsclp->tails[RCU_DONE_TAIL], NULL);
39698059b98SPaul E. McKenney 	rclp->tail = rsclp->tails[RCU_DONE_TAIL];
39798059b98SPaul E. McKenney 	for (i = RCU_CBLIST_NSEGS - 1; i >= RCU_DONE_TAIL; i--)
39898059b98SPaul E. McKenney 		if (rsclp->tails[i] == rsclp->tails[RCU_DONE_TAIL])
39976c6927cSPaul E. McKenney 			WRITE_ONCE(rsclp->tails[i], &rsclp->head);
400ae5c2341SJoel Fernandes (Google) 	rcu_segcblist_set_seglen(rsclp, RCU_DONE_TAIL, 0);
40198059b98SPaul E. McKenney }
40298059b98SPaul E. McKenney 
40398059b98SPaul E. McKenney /*
40498059b98SPaul E. McKenney  * Extract only those callbacks still pending (not yet ready to be
40598059b98SPaul E. McKenney  * invoked) from the specified rcu_segcblist structure and place them in
40698059b98SPaul E. McKenney  * the specified rcu_cblist structure.  Note that this loses information
40798059b98SPaul E. McKenney  * about any callbacks that might have been partway done waiting for
40898059b98SPaul E. McKenney  * their grace period.  Too bad!  They will have to start over.
40998059b98SPaul E. McKenney  */
rcu_segcblist_extract_pend_cbs(struct rcu_segcblist * rsclp,struct rcu_cblist * rclp)41098059b98SPaul E. McKenney void rcu_segcblist_extract_pend_cbs(struct rcu_segcblist *rsclp,
41198059b98SPaul E. McKenney 				    struct rcu_cblist *rclp)
41298059b98SPaul E. McKenney {
41398059b98SPaul E. McKenney 	int i;
41498059b98SPaul E. McKenney 
41598059b98SPaul E. McKenney 	if (!rcu_segcblist_pend_cbs(rsclp))
41698059b98SPaul E. McKenney 		return; /* Nothing to do. */
417ae5c2341SJoel Fernandes (Google) 	rclp->len = 0;
41898059b98SPaul E. McKenney 	*rclp->tail = *rsclp->tails[RCU_DONE_TAIL];
41998059b98SPaul E. McKenney 	rclp->tail = rsclp->tails[RCU_NEXT_TAIL];
42076c6927cSPaul E. McKenney 	WRITE_ONCE(*rsclp->tails[RCU_DONE_TAIL], NULL);
421ae5c2341SJoel Fernandes (Google) 	for (i = RCU_DONE_TAIL + 1; i < RCU_CBLIST_NSEGS; i++) {
422ae5c2341SJoel Fernandes (Google) 		rclp->len += rcu_segcblist_get_seglen(rsclp, i);
42376c6927cSPaul E. McKenney 		WRITE_ONCE(rsclp->tails[i], rsclp->tails[RCU_DONE_TAIL]);
424ae5c2341SJoel Fernandes (Google) 		rcu_segcblist_set_seglen(rsclp, i, 0);
425ae5c2341SJoel Fernandes (Google) 	}
42698059b98SPaul E. McKenney }
42798059b98SPaul E. McKenney 
42898059b98SPaul E. McKenney /*
42998059b98SPaul E. McKenney  * Insert counts from the specified rcu_cblist structure in the
43098059b98SPaul E. McKenney  * specified rcu_segcblist structure.
43198059b98SPaul E. McKenney  */
rcu_segcblist_insert_count(struct rcu_segcblist * rsclp,struct rcu_cblist * rclp)43298059b98SPaul E. McKenney void rcu_segcblist_insert_count(struct rcu_segcblist *rsclp,
43398059b98SPaul E. McKenney 				struct rcu_cblist *rclp)
43498059b98SPaul E. McKenney {
435eda669a6SPaul E. McKenney 	rcu_segcblist_add_len(rsclp, rclp->len);
43698059b98SPaul E. McKenney }
43798059b98SPaul E. McKenney 
43898059b98SPaul E. McKenney /*
43998059b98SPaul E. McKenney  * Move callbacks from the specified rcu_cblist to the beginning of the
44098059b98SPaul E. McKenney  * done-callbacks segment of the specified rcu_segcblist.
44198059b98SPaul E. McKenney  */
rcu_segcblist_insert_done_cbs(struct rcu_segcblist * rsclp,struct rcu_cblist * rclp)44298059b98SPaul E. McKenney void rcu_segcblist_insert_done_cbs(struct rcu_segcblist *rsclp,
44398059b98SPaul E. McKenney 				   struct rcu_cblist *rclp)
44498059b98SPaul E. McKenney {
44598059b98SPaul E. McKenney 	int i;
44698059b98SPaul E. McKenney 
44798059b98SPaul E. McKenney 	if (!rclp->head)
44898059b98SPaul E. McKenney 		return; /* No callbacks to move. */
449ae5c2341SJoel Fernandes (Google) 	rcu_segcblist_add_seglen(rsclp, RCU_DONE_TAIL, rclp->len);
45098059b98SPaul E. McKenney 	*rclp->tail = rsclp->head;
451e6060b41SPaul E. McKenney 	WRITE_ONCE(rsclp->head, rclp->head);
45298059b98SPaul E. McKenney 	for (i = RCU_DONE_TAIL; i < RCU_CBLIST_NSEGS; i++)
45398059b98SPaul E. McKenney 		if (&rsclp->head == rsclp->tails[i])
45476c6927cSPaul E. McKenney 			WRITE_ONCE(rsclp->tails[i], rclp->tail);
45598059b98SPaul E. McKenney 		else
45698059b98SPaul E. McKenney 			break;
45798059b98SPaul E. McKenney 	rclp->head = NULL;
45898059b98SPaul E. McKenney 	rclp->tail = &rclp->head;
45998059b98SPaul E. McKenney }
46098059b98SPaul E. McKenney 
46198059b98SPaul E. McKenney /*
46298059b98SPaul E. McKenney  * Move callbacks from the specified rcu_cblist to the end of the
46398059b98SPaul E. McKenney  * new-callbacks segment of the specified rcu_segcblist.
46498059b98SPaul E. McKenney  */
rcu_segcblist_insert_pend_cbs(struct rcu_segcblist * rsclp,struct rcu_cblist * rclp)46598059b98SPaul E. McKenney void rcu_segcblist_insert_pend_cbs(struct rcu_segcblist *rsclp,
46698059b98SPaul E. McKenney 				   struct rcu_cblist *rclp)
46798059b98SPaul E. McKenney {
46898059b98SPaul E. McKenney 	if (!rclp->head)
46998059b98SPaul E. McKenney 		return; /* Nothing to do. */
470ae5c2341SJoel Fernandes (Google) 
471ae5c2341SJoel Fernandes (Google) 	rcu_segcblist_add_seglen(rsclp, RCU_NEXT_TAIL, rclp->len);
47276c6927cSPaul E. McKenney 	WRITE_ONCE(*rsclp->tails[RCU_NEXT_TAIL], rclp->head);
47376c6927cSPaul E. McKenney 	WRITE_ONCE(rsclp->tails[RCU_NEXT_TAIL], rclp->tail);
47498059b98SPaul E. McKenney }
47598059b98SPaul E. McKenney 
47698059b98SPaul E. McKenney /*
47798059b98SPaul E. McKenney  * Advance the callbacks in the specified rcu_segcblist structure based
47898059b98SPaul E. McKenney  * on the current value passed in for the grace-period counter.
47998059b98SPaul E. McKenney  */
rcu_segcblist_advance(struct rcu_segcblist * rsclp,unsigned long seq)48098059b98SPaul E. McKenney void rcu_segcblist_advance(struct rcu_segcblist *rsclp, unsigned long seq)
48198059b98SPaul E. McKenney {
48298059b98SPaul E. McKenney 	int i, j;
48398059b98SPaul E. McKenney 
48498059b98SPaul E. McKenney 	WARN_ON_ONCE(!rcu_segcblist_is_enabled(rsclp));
48598059b98SPaul E. McKenney 	if (rcu_segcblist_restempty(rsclp, RCU_DONE_TAIL))
48698059b98SPaul E. McKenney 		return;
48798059b98SPaul E. McKenney 
48898059b98SPaul E. McKenney 	/*
48998059b98SPaul E. McKenney 	 * Find all callbacks whose ->gp_seq numbers indicate that they
49098059b98SPaul E. McKenney 	 * are ready to invoke, and put them into the RCU_DONE_TAIL segment.
49198059b98SPaul E. McKenney 	 */
49298059b98SPaul E. McKenney 	for (i = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++) {
49398059b98SPaul E. McKenney 		if (ULONG_CMP_LT(seq, rsclp->gp_seq[i]))
49498059b98SPaul E. McKenney 			break;
49576c6927cSPaul E. McKenney 		WRITE_ONCE(rsclp->tails[RCU_DONE_TAIL], rsclp->tails[i]);
496ae5c2341SJoel Fernandes (Google) 		rcu_segcblist_move_seglen(rsclp, i, RCU_DONE_TAIL);
49798059b98SPaul E. McKenney 	}
49898059b98SPaul E. McKenney 
49998059b98SPaul E. McKenney 	/* If no callbacks moved, nothing more need be done. */
50098059b98SPaul E. McKenney 	if (i == RCU_WAIT_TAIL)
50198059b98SPaul E. McKenney 		return;
50298059b98SPaul E. McKenney 
50398059b98SPaul E. McKenney 	/* Clean up tail pointers that might have been misordered above. */
50498059b98SPaul E. McKenney 	for (j = RCU_WAIT_TAIL; j < i; j++)
50576c6927cSPaul E. McKenney 		WRITE_ONCE(rsclp->tails[j], rsclp->tails[RCU_DONE_TAIL]);
50698059b98SPaul E. McKenney 
50798059b98SPaul E. McKenney 	/*
508d22959aaSPaul E. McKenney 	 * Callbacks moved, so there might be an empty RCU_WAIT_TAIL
509d22959aaSPaul E. McKenney 	 * and a non-empty RCU_NEXT_READY_TAIL.  If so, copy the
510d22959aaSPaul E. McKenney 	 * RCU_NEXT_READY_TAIL segment to fill the RCU_WAIT_TAIL gap
511d22959aaSPaul E. McKenney 	 * created by the now-ready-to-invoke segments.
51298059b98SPaul E. McKenney 	 */
51398059b98SPaul E. McKenney 	for (j = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++, j++) {
51498059b98SPaul E. McKenney 		if (rsclp->tails[j] == rsclp->tails[RCU_NEXT_TAIL])
51598059b98SPaul E. McKenney 			break;  /* No more callbacks. */
51676c6927cSPaul E. McKenney 		WRITE_ONCE(rsclp->tails[j], rsclp->tails[i]);
517ae5c2341SJoel Fernandes (Google) 		rcu_segcblist_move_seglen(rsclp, i, j);
51898059b98SPaul E. McKenney 		rsclp->gp_seq[j] = rsclp->gp_seq[i];
51998059b98SPaul E. McKenney 	}
52098059b98SPaul E. McKenney }
52198059b98SPaul E. McKenney 
52298059b98SPaul E. McKenney /*
52398059b98SPaul E. McKenney  * "Accelerate" callbacks based on more-accurate grace-period information.
52498059b98SPaul E. McKenney  * The reason for this is that RCU does not synchronize the beginnings and
52598059b98SPaul E. McKenney  * ends of grace periods, and that callbacks are posted locally.  This in
52698059b98SPaul E. McKenney  * turn means that the callbacks must be labelled conservatively early
52798059b98SPaul E. McKenney  * on, as getting exact information would degrade both performance and
52898059b98SPaul E. McKenney  * scalability.  When more accurate grace-period information becomes
52998059b98SPaul E. McKenney  * available, previously posted callbacks can be "accelerated", marking
53098059b98SPaul E. McKenney  * them to complete at the end of the earlier grace period.
53198059b98SPaul E. McKenney  *
53298059b98SPaul E. McKenney  * This function operates on an rcu_segcblist structure, and also the
53398059b98SPaul E. McKenney  * grace-period sequence number seq at which new callbacks would become
53498059b98SPaul E. McKenney  * ready to invoke.  Returns true if there are callbacks that won't be
53598059b98SPaul E. McKenney  * ready to invoke until seq, false otherwise.
53698059b98SPaul E. McKenney  */
rcu_segcblist_accelerate(struct rcu_segcblist * rsclp,unsigned long seq)53798059b98SPaul E. McKenney bool rcu_segcblist_accelerate(struct rcu_segcblist *rsclp, unsigned long seq)
53898059b98SPaul E. McKenney {
539ae5c2341SJoel Fernandes (Google) 	int i, j;
54098059b98SPaul E. McKenney 
54198059b98SPaul E. McKenney 	WARN_ON_ONCE(!rcu_segcblist_is_enabled(rsclp));
54298059b98SPaul E. McKenney 	if (rcu_segcblist_restempty(rsclp, RCU_DONE_TAIL))
54398059b98SPaul E. McKenney 		return false;
54498059b98SPaul E. McKenney 
54598059b98SPaul E. McKenney 	/*
54698059b98SPaul E. McKenney 	 * Find the segment preceding the oldest segment of callbacks
54798059b98SPaul E. McKenney 	 * whose ->gp_seq[] completion is at or after that passed in via
54898059b98SPaul E. McKenney 	 * "seq", skipping any empty segments.  This oldest segment, along
54998059b98SPaul E. McKenney 	 * with any later segments, can be merged in with any newly arrived
55098059b98SPaul E. McKenney 	 * callbacks in the RCU_NEXT_TAIL segment, and assigned "seq"
55198059b98SPaul E. McKenney 	 * as their ->gp_seq[] grace-period completion sequence number.
55298059b98SPaul E. McKenney 	 */
55398059b98SPaul E. McKenney 	for (i = RCU_NEXT_READY_TAIL; i > RCU_DONE_TAIL; i--)
55498059b98SPaul E. McKenney 		if (rsclp->tails[i] != rsclp->tails[i - 1] &&
55598059b98SPaul E. McKenney 		    ULONG_CMP_LT(rsclp->gp_seq[i], seq))
55698059b98SPaul E. McKenney 			break;
55798059b98SPaul E. McKenney 
55898059b98SPaul E. McKenney 	/*
55998059b98SPaul E. McKenney 	 * If all the segments contain callbacks that correspond to
56098059b98SPaul E. McKenney 	 * earlier grace-period sequence numbers than "seq", leave.
56198059b98SPaul E. McKenney 	 * Assuming that the rcu_segcblist structure has enough
56298059b98SPaul E. McKenney 	 * segments in its arrays, this can only happen if some of
56398059b98SPaul E. McKenney 	 * the non-done segments contain callbacks that really are
56498059b98SPaul E. McKenney 	 * ready to invoke.  This situation will get straightened
56598059b98SPaul E. McKenney 	 * out by the next call to rcu_segcblist_advance().
56698059b98SPaul E. McKenney 	 *
56798059b98SPaul E. McKenney 	 * Also advance to the oldest segment of callbacks whose
56898059b98SPaul E. McKenney 	 * ->gp_seq[] completion is at or after that passed in via "seq",
56998059b98SPaul E. McKenney 	 * skipping any empty segments.
57053922270SJoel Fernandes (Google) 	 *
57153922270SJoel Fernandes (Google) 	 * Note that segment "i" (and any lower-numbered segments
57253922270SJoel Fernandes (Google) 	 * containing older callbacks) will be unaffected, and their
57353922270SJoel Fernandes (Google) 	 * grace-period numbers remain unchanged.  For example, if i ==
57453922270SJoel Fernandes (Google) 	 * WAIT_TAIL, then neither WAIT_TAIL nor DONE_TAIL will be touched.
57553922270SJoel Fernandes (Google) 	 * Instead, the CBs in NEXT_TAIL will be merged with those in
57653922270SJoel Fernandes (Google) 	 * NEXT_READY_TAIL and the grace-period number of NEXT_READY_TAIL
57753922270SJoel Fernandes (Google) 	 * would be updated.  NEXT_TAIL would then be empty.
57898059b98SPaul E. McKenney 	 */
57953922270SJoel Fernandes (Google) 	if (rcu_segcblist_restempty(rsclp, i) || ++i >= RCU_NEXT_TAIL)
58098059b98SPaul E. McKenney 		return false;
58198059b98SPaul E. McKenney 
582ae5c2341SJoel Fernandes (Google) 	/* Accounting: everything below i is about to get merged into i. */
583ae5c2341SJoel Fernandes (Google) 	for (j = i + 1; j <= RCU_NEXT_TAIL; j++)
584ae5c2341SJoel Fernandes (Google) 		rcu_segcblist_move_seglen(rsclp, j, i);
585ae5c2341SJoel Fernandes (Google) 
58698059b98SPaul E. McKenney 	/*
58798059b98SPaul E. McKenney 	 * Merge all later callbacks, including newly arrived callbacks,
58898059b98SPaul E. McKenney 	 * into the segment located by the for-loop above.  Assign "seq"
58998059b98SPaul E. McKenney 	 * as the ->gp_seq[] value in order to correctly handle the case
59098059b98SPaul E. McKenney 	 * where there were no pending callbacks in the rcu_segcblist
59198059b98SPaul E. McKenney 	 * structure other than in the RCU_NEXT_TAIL segment.
59298059b98SPaul E. McKenney 	 */
59398059b98SPaul E. McKenney 	for (; i < RCU_NEXT_TAIL; i++) {
59476c6927cSPaul E. McKenney 		WRITE_ONCE(rsclp->tails[i], rsclp->tails[RCU_NEXT_TAIL]);
59598059b98SPaul E. McKenney 		rsclp->gp_seq[i] = seq;
59698059b98SPaul E. McKenney 	}
59798059b98SPaul E. McKenney 	return true;
59898059b98SPaul E. McKenney }
59998059b98SPaul E. McKenney 
60098059b98SPaul E. McKenney /*
601f2dbe4a5SPaul E. McKenney  * Merge the source rcu_segcblist structure into the destination
602f2dbe4a5SPaul E. McKenney  * rcu_segcblist structure, then initialize the source.  Any pending
603f2dbe4a5SPaul E. McKenney  * callbacks from the source get to start over.  It is best to
604f2dbe4a5SPaul E. McKenney  * advance and accelerate both the destination and the source
605f2dbe4a5SPaul E. McKenney  * before merging.
606f2dbe4a5SPaul E. McKenney  */
rcu_segcblist_merge(struct rcu_segcblist * dst_rsclp,struct rcu_segcblist * src_rsclp)607f2dbe4a5SPaul E. McKenney void rcu_segcblist_merge(struct rcu_segcblist *dst_rsclp,
608f2dbe4a5SPaul E. McKenney 			 struct rcu_segcblist *src_rsclp)
609f2dbe4a5SPaul E. McKenney {
610f2dbe4a5SPaul E. McKenney 	struct rcu_cblist donecbs;
611f2dbe4a5SPaul E. McKenney 	struct rcu_cblist pendcbs;
612f2dbe4a5SPaul E. McKenney 
613ae5c2341SJoel Fernandes (Google) 	lockdep_assert_cpus_held();
614ae5c2341SJoel Fernandes (Google) 
615f2dbe4a5SPaul E. McKenney 	rcu_cblist_init(&donecbs);
616f2dbe4a5SPaul E. McKenney 	rcu_cblist_init(&pendcbs);
617ae5c2341SJoel Fernandes (Google) 
618f2dbe4a5SPaul E. McKenney 	rcu_segcblist_extract_done_cbs(src_rsclp, &donecbs);
619f2dbe4a5SPaul E. McKenney 	rcu_segcblist_extract_pend_cbs(src_rsclp, &pendcbs);
620ae5c2341SJoel Fernandes (Google) 
621ae5c2341SJoel Fernandes (Google) 	/*
622ae5c2341SJoel Fernandes (Google) 	 * No need smp_mb() before setting length to 0, because CPU hotplug
623ae5c2341SJoel Fernandes (Google) 	 * lock excludes rcu_barrier.
624ae5c2341SJoel Fernandes (Google) 	 */
625ae5c2341SJoel Fernandes (Google) 	rcu_segcblist_set_len(src_rsclp, 0);
626ae5c2341SJoel Fernandes (Google) 
627f2dbe4a5SPaul E. McKenney 	rcu_segcblist_insert_count(dst_rsclp, &donecbs);
628ae5c2341SJoel Fernandes (Google) 	rcu_segcblist_insert_count(dst_rsclp, &pendcbs);
629f2dbe4a5SPaul E. McKenney 	rcu_segcblist_insert_done_cbs(dst_rsclp, &donecbs);
630f2dbe4a5SPaul E. McKenney 	rcu_segcblist_insert_pend_cbs(dst_rsclp, &pendcbs);
631ae5c2341SJoel Fernandes (Google) 
632f2dbe4a5SPaul E. McKenney 	rcu_segcblist_init(src_rsclp);
633f2dbe4a5SPaul E. McKenney }
634