1 // SPDX-License-Identifier: GPL-2.0+
20 	rclp->head = NULL;  in rcu_cblist_init()
21 	rclp->tail = &rclp->head;  in rcu_cblist_init()
22 	rclp->len = 0;  in rcu_cblist_init()
30 	*rclp->tail = rhp;  in rcu_cblist_enqueue()
31 	rclp->tail = &rhp->next;  in rcu_cblist_enqueue()
32 	WRITE_ONCE(rclp->len, rclp->len + 1);  in rcu_cblist_enqueue()
37  * any contents of the first.  If rhp is non-NULL, enqueue it as the sole
39  * rcu_cblist structure, if initially non-empty, always appears non-empty
41  * is instead initialized to empty.
47 	drclp->head = srclp->head;  in rcu_cblist_flush_enqueue()
48 	if (drclp->head)  in rcu_cblist_flush_enqueue()
49 		drclp->tail = srclp->tail;  in rcu_cblist_flush_enqueue()
51 		drclp->tail = &drclp->head;  in rcu_cblist_flush_enqueue()
52 	drclp->len = srclp->len;  in rcu_cblist_flush_enqueue()
56 		rhp->next = NULL;  in rcu_cblist_flush_enqueue()
57 		srclp->head = rhp;  in rcu_cblist_flush_enqueue()
58 		srclp->tail = &rhp->next;  in rcu_cblist_flush_enqueue()
59 		WRITE_ONCE(srclp->len, 1);  in rcu_cblist_flush_enqueue()
71 	rhp = rclp->head;  in rcu_cblist_dequeue()
74 	rclp->len--;  in rcu_cblist_dequeue()
75 	rclp->head = rhp->next;  in rcu_cblist_dequeue()
76 	if (!rclp->head)  in rcu_cblist_dequeue()
77 		rclp->tail = &rclp->head;  in rcu_cblist_dequeue()
85 	atomic_long_set(&rsclp->len, v);  in rcu_segcblist_set_len()
87 	WRITE_ONCE(rsclp->len, v);  in rcu_segcblist_set_len()
94 	return READ_ONCE(rsclp->seglen[seg]);  in rcu_segcblist_get_seglen()
112 	WRITE_ONCE(rsclp->seglen[seg], v);  in rcu_segcblist_set_seglen()
118 	WRITE_ONCE(rsclp->seglen[seg], rsclp->seglen[seg] + v);  in rcu_segcblist_add_seglen()
145  * specified amount, which can be negative.  This can cause the ->len
151  * the update to the ->len field???
153  * The reason is that rcu_barrier() locklessly samples each CPU's ->len
163  * Therefore, ->len transitions from 1->0 and 0->1 have to be carefully
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
177  *					rcu_barrier() sees ->len as 0.
178  * set ->len = 1.
183  * With the full barriers, any case where rcu_barrier() sees ->len as 0 will
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
199  * set ->len = 0 (reordered)
200  *					rcu_barrier() sees ->len as 0
205  * With the full barriers, any case where rcu_barrier() sees ->len as 0
214 	atomic_long_add(v, &rsclp->len);  in rcu_segcblist_add_len()
218 	WRITE_ONCE(rsclp->len, rsclp->len + v);  in rcu_segcblist_add_len()
225  * This can cause the ->len field to disagree with the actual number of
241 	BUILD_BUG_ON(RCU_NEXT_TAIL + 1 != ARRAY_SIZE(rsclp->gp_seq));  in rcu_segcblist_init()
242 	BUILD_BUG_ON(ARRAY_SIZE(rsclp->tails) != ARRAY_SIZE(rsclp->gp_seq));  in rcu_segcblist_init()
243 	rsclp->head = NULL;  in rcu_segcblist_init()
245 		rsclp->tails[i] = &rsclp->head;  in rcu_segcblist_init()
254  * no longer be posted to it.  This structure must be empty.
270 	       &rsclp->head != READ_ONCE(rsclp->tails[RCU_DONE_TAIL]);  in rcu_segcblist_ready_cbs()
290 		return rsclp->head;  in rcu_segcblist_first_cb()
297  * callback -- if that callback is the first pending callback, then
304 		return *rsclp->tails[RCU_DONE_TAIL];  in rcu_segcblist_first_pend_cb()
310  * return true and store the nearest waited-upon grace period into *lp.
316 	*lp = rsclp->gp_seq[RCU_WAIT_TAIL];  in rcu_segcblist_nextgp()
322  * structure, updating accounting as needed.  Note that the ->len
324  * The ->len field is used by rcu_barrier() and friends to determine
334 	rhp->next = NULL;  in rcu_segcblist_enqueue()
335 	WRITE_ONCE(*rsclp->tails[RCU_NEXT_TAIL], rhp);  in rcu_segcblist_enqueue()
336 	WRITE_ONCE(rsclp->tails[RCU_NEXT_TAIL], &rhp->next);  in rcu_segcblist_enqueue()
341  * the end of the last non-empty segment.  If the entire rcu_segcblist
342  * is empty, make no change, but return false.
344  * This is intended for use by rcu_barrier()-like primitives, -not-
345  * for normal grace-period use.  IMPORTANT:  The callback you enqueue
358 	rhp->next = NULL;  in rcu_segcblist_entrain()
359 	for (i = RCU_NEXT_TAIL; i > RCU_DONE_TAIL; i--)  in rcu_segcblist_entrain()
363 	WRITE_ONCE(*rsclp->tails[i], rhp);  in rcu_segcblist_entrain()
365 		WRITE_ONCE(rsclp->tails[i], &rhp->next);  in rcu_segcblist_entrain()
381 	rclp->len = rcu_segcblist_get_seglen(rsclp, RCU_DONE_TAIL);  in rcu_segcblist_extract_done_cbs()
382 	*rclp->tail = rsclp->head;  in rcu_segcblist_extract_done_cbs()
383 	WRITE_ONCE(rsclp->head, *rsclp->tails[RCU_DONE_TAIL]);  in rcu_segcblist_extract_done_cbs()
384 	WRITE_ONCE(*rsclp->tails[RCU_DONE_TAIL], NULL);  in rcu_segcblist_extract_done_cbs()
385 	rclp->tail = rsclp->tails[RCU_DONE_TAIL];  in rcu_segcblist_extract_done_cbs()
386 	for (i = RCU_CBLIST_NSEGS - 1; i >= RCU_DONE_TAIL; i--)  in rcu_segcblist_extract_done_cbs()
387 		if (rsclp->tails[i] == rsclp->tails[RCU_DONE_TAIL])  in rcu_segcblist_extract_done_cbs()
388 			WRITE_ONCE(rsclp->tails[i], &rsclp->head);  in rcu_segcblist_extract_done_cbs()
406 	rclp->len = 0;  in rcu_segcblist_extract_pend_cbs()
407 	*rclp->tail = *rsclp->tails[RCU_DONE_TAIL];  in rcu_segcblist_extract_pend_cbs()
408 	rclp->tail = rsclp->tails[RCU_NEXT_TAIL];  in rcu_segcblist_extract_pend_cbs()
409 	WRITE_ONCE(*rsclp->tails[RCU_DONE_TAIL], NULL);  in rcu_segcblist_extract_pend_cbs()
411 		rclp->len += rcu_segcblist_get_seglen(rsclp, i);  in rcu_segcblist_extract_pend_cbs()
412 		WRITE_ONCE(rsclp->tails[i], rsclp->tails[RCU_DONE_TAIL]);  in rcu_segcblist_extract_pend_cbs()
424 	rcu_segcblist_add_len(rsclp, rclp->len);  in rcu_segcblist_insert_count()
429  * done-callbacks segment of the specified rcu_segcblist.
436 	if (!rclp->head)  in rcu_segcblist_insert_done_cbs()
438 	rcu_segcblist_add_seglen(rsclp, RCU_DONE_TAIL, rclp->len);  in rcu_segcblist_insert_done_cbs()
439 	*rclp->tail = rsclp->head;  in rcu_segcblist_insert_done_cbs()
440 	WRITE_ONCE(rsclp->head, rclp->head);  in rcu_segcblist_insert_done_cbs()
442 		if (&rsclp->head == rsclp->tails[i])  in rcu_segcblist_insert_done_cbs()
443 			WRITE_ONCE(rsclp->tails[i], rclp->tail);  in rcu_segcblist_insert_done_cbs()
446 	rclp->head = NULL;  in rcu_segcblist_insert_done_cbs()
447 	rclp->tail = &rclp->head;  in rcu_segcblist_insert_done_cbs()
452  * new-callbacks segment of the specified rcu_segcblist.
457 	if (!rclp->head)  in rcu_segcblist_insert_pend_cbs()
460 	rcu_segcblist_add_seglen(rsclp, RCU_NEXT_TAIL, rclp->len);  in rcu_segcblist_insert_pend_cbs()
461 	WRITE_ONCE(*rsclp->tails[RCU_NEXT_TAIL], rclp->head);  in rcu_segcblist_insert_pend_cbs()
462 	WRITE_ONCE(rsclp->tails[RCU_NEXT_TAIL], rclp->tail);  in rcu_segcblist_insert_pend_cbs()
467  * on the current value passed in for the grace-period counter.
478 	 * Find all callbacks whose ->gp_seq numbers indicate that they  in rcu_segcblist_advance()
482 		if (ULONG_CMP_LT(seq, rsclp->gp_seq[i]))  in rcu_segcblist_advance()
484 		WRITE_ONCE(rsclp->tails[RCU_DONE_TAIL], rsclp->tails[i]);  in rcu_segcblist_advance()
494 		WRITE_ONCE(rsclp->tails[j], rsclp->tails[RCU_DONE_TAIL]);  in rcu_segcblist_advance()
497 	 * Callbacks moved, so there might be an empty RCU_WAIT_TAIL  in rcu_segcblist_advance()
498 	 * and a non-empty RCU_NEXT_READY_TAIL.  If so, copy the  in rcu_segcblist_advance()
500 	 * created by the now-ready-to-invoke segments.  in rcu_segcblist_advance()
503 		if (rsclp->tails[j] == rsclp->tails[RCU_NEXT_TAIL])  in rcu_segcblist_advance()
505 		WRITE_ONCE(rsclp->tails[j], rsclp->tails[i]);  in rcu_segcblist_advance()
507 		rsclp->gp_seq[j] = rsclp->gp_seq[i];  in rcu_segcblist_advance()
512  * "Accelerate" callbacks based on more-accurate grace-period information.
517  * scalability.  When more accurate grace-period information becomes
522  * grace-period sequence number seq at which new callbacks would become
536 	 * whose ->gp_seq[] completion is at or after that passed in via  in rcu_segcblist_accelerate()
537 	 * "seq", skipping any empty segments.  This oldest segment, along  in rcu_segcblist_accelerate()
540 	 * as their ->gp_seq[] grace-period completion sequence number.  in rcu_segcblist_accelerate()
542 	for (i = RCU_NEXT_READY_TAIL; i > RCU_DONE_TAIL; i--)  in rcu_segcblist_accelerate()
544 		    ULONG_CMP_LT(rsclp->gp_seq[i], seq))  in rcu_segcblist_accelerate()
549 	 * earlier grace-period sequence numbers than "seq", leave.  in rcu_segcblist_accelerate()
552 	 * the non-done segments contain callbacks that really are  in rcu_segcblist_accelerate()
557 	 * ->gp_seq[] completion is at or after that passed in via "seq",  in rcu_segcblist_accelerate()
558 	 * skipping any empty segments.  in rcu_segcblist_accelerate()
560 	 * Note that segment "i" (and any lower-numbered segments  in rcu_segcblist_accelerate()
562 	 * grace-period numbers remain unchanged.  For example, if i ==  in rcu_segcblist_accelerate()
565 	 * NEXT_READY_TAIL and the grace-period number of NEXT_READY_TAIL  in rcu_segcblist_accelerate()
566 	 * would be updated.  NEXT_TAIL would then be empty.  in rcu_segcblist_accelerate()
577 	 * into the segment located by the for-loop above.  Assign "seq"  in rcu_segcblist_accelerate()
578 	 * as the ->gp_seq[] value in order to correctly handle the case  in rcu_segcblist_accelerate()
583 		WRITE_ONCE(rsclp->tails[i], rsclp->tails[RCU_NEXT_TAIL]);  in rcu_segcblist_accelerate()
584 		rsclp->gp_seq[i] = seq;  in rcu_segcblist_accelerate()