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.
281 	       &rsclp->head != READ_ONCE(rsclp->tails[RCU_DONE_TAIL]);  in rcu_segcblist_ready_cbs()
301 		return rsclp->head;  in rcu_segcblist_first_cb()
308  * callback -- if that callback is the first pending callback, then
315 		return *rsclp->tails[RCU_DONE_TAIL];  in rcu_segcblist_first_pend_cb()
321  * return true and store the nearest waited-upon grace period into *lp.
327 	*lp = rsclp->gp_seq[RCU_WAIT_TAIL];  in rcu_segcblist_nextgp()
333  * structure, updating accounting as needed.  Note that the ->len
335  * The ->len field is used by rcu_barrier() and friends to determine
345 	rhp->next = NULL;  in rcu_segcblist_enqueue()
346 	WRITE_ONCE(*rsclp->tails[RCU_NEXT_TAIL], rhp);  in rcu_segcblist_enqueue()
347 	WRITE_ONCE(rsclp->tails[RCU_NEXT_TAIL], &rhp->next);  in rcu_segcblist_enqueue()
352  * the end of the last non-empty segment.  If the entire rcu_segcblist
353  * is empty, make no change, but return false.
355  * This is intended for use by rcu_barrier()-like primitives, -not-
356  * for normal grace-period use.  IMPORTANT:  The callback you enqueue
369 	rhp->next = NULL;  in rcu_segcblist_entrain()
370 	for (i = RCU_NEXT_TAIL; i > RCU_DONE_TAIL; i--)  in rcu_segcblist_entrain()
371 		if (rsclp->tails[i] != rsclp->tails[i - 1])  in rcu_segcblist_entrain()
374 	WRITE_ONCE(*rsclp->tails[i], rhp);  in rcu_segcblist_entrain()
376 		WRITE_ONCE(rsclp->tails[i], &rhp->next);  in rcu_segcblist_entrain()
392 	rclp->len = rcu_segcblist_get_seglen(rsclp, RCU_DONE_TAIL);  in rcu_segcblist_extract_done_cbs()
393 	*rclp->tail = rsclp->head;  in rcu_segcblist_extract_done_cbs()
394 	WRITE_ONCE(rsclp->head, *rsclp->tails[RCU_DONE_TAIL]);  in rcu_segcblist_extract_done_cbs()
395 	WRITE_ONCE(*rsclp->tails[RCU_DONE_TAIL], NULL);  in rcu_segcblist_extract_done_cbs()
396 	rclp->tail = rsclp->tails[RCU_DONE_TAIL];  in rcu_segcblist_extract_done_cbs()
397 	for (i = RCU_CBLIST_NSEGS - 1; i >= RCU_DONE_TAIL; i--)  in rcu_segcblist_extract_done_cbs()
398 		if (rsclp->tails[i] == rsclp->tails[RCU_DONE_TAIL])  in rcu_segcblist_extract_done_cbs()
399 			WRITE_ONCE(rsclp->tails[i], &rsclp->head);  in rcu_segcblist_extract_done_cbs()
417 	rclp->len = 0;  in rcu_segcblist_extract_pend_cbs()
418 	*rclp->tail = *rsclp->tails[RCU_DONE_TAIL];  in rcu_segcblist_extract_pend_cbs()
419 	rclp->tail = rsclp->tails[RCU_NEXT_TAIL];  in rcu_segcblist_extract_pend_cbs()
420 	WRITE_ONCE(*rsclp->tails[RCU_DONE_TAIL], NULL);  in rcu_segcblist_extract_pend_cbs()
422 		rclp->len += rcu_segcblist_get_seglen(rsclp, i);  in rcu_segcblist_extract_pend_cbs()
423 		WRITE_ONCE(rsclp->tails[i], rsclp->tails[RCU_DONE_TAIL]);  in rcu_segcblist_extract_pend_cbs()
435 	rcu_segcblist_add_len(rsclp, rclp->len);  in rcu_segcblist_insert_count()
440  * done-callbacks segment of the specified rcu_segcblist.
447 	if (!rclp->head)  in rcu_segcblist_insert_done_cbs()
449 	rcu_segcblist_add_seglen(rsclp, RCU_DONE_TAIL, rclp->len);  in rcu_segcblist_insert_done_cbs()
450 	*rclp->tail = rsclp->head;  in rcu_segcblist_insert_done_cbs()
451 	WRITE_ONCE(rsclp->head, rclp->head);  in rcu_segcblist_insert_done_cbs()
453 		if (&rsclp->head == rsclp->tails[i])  in rcu_segcblist_insert_done_cbs()
454 			WRITE_ONCE(rsclp->tails[i], rclp->tail);  in rcu_segcblist_insert_done_cbs()
457 	rclp->head = NULL;  in rcu_segcblist_insert_done_cbs()
458 	rclp->tail = &rclp->head;  in rcu_segcblist_insert_done_cbs()
463  * new-callbacks segment of the specified rcu_segcblist.
468 	if (!rclp->head)  in rcu_segcblist_insert_pend_cbs()
471 	rcu_segcblist_add_seglen(rsclp, RCU_NEXT_TAIL, rclp->len);  in rcu_segcblist_insert_pend_cbs()
472 	WRITE_ONCE(*rsclp->tails[RCU_NEXT_TAIL], rclp->head);  in rcu_segcblist_insert_pend_cbs()
473 	WRITE_ONCE(rsclp->tails[RCU_NEXT_TAIL], rclp->tail);  in rcu_segcblist_insert_pend_cbs()
478  * on the current value passed in for the grace-period counter.
489 	 * Find all callbacks whose ->gp_seq numbers indicate that they  in rcu_segcblist_advance()
493 		if (ULONG_CMP_LT(seq, rsclp->gp_seq[i]))  in rcu_segcblist_advance()
495 		WRITE_ONCE(rsclp->tails[RCU_DONE_TAIL], rsclp->tails[i]);  in rcu_segcblist_advance()
505 		WRITE_ONCE(rsclp->tails[j], rsclp->tails[RCU_DONE_TAIL]);  in rcu_segcblist_advance()
508 	 * Callbacks moved, so there might be an empty RCU_WAIT_TAIL  in rcu_segcblist_advance()
509 	 * and a non-empty RCU_NEXT_READY_TAIL.  If so, copy the  in rcu_segcblist_advance()
511 	 * created by the now-ready-to-invoke segments.  in rcu_segcblist_advance()
514 		if (rsclp->tails[j] == rsclp->tails[RCU_NEXT_TAIL])  in rcu_segcblist_advance()
516 		WRITE_ONCE(rsclp->tails[j], rsclp->tails[i]);  in rcu_segcblist_advance()
518 		rsclp->gp_seq[j] = rsclp->gp_seq[i];  in rcu_segcblist_advance()
523  * "Accelerate" callbacks based on more-accurate grace-period information.
528  * scalability.  When more accurate grace-period information becomes
533  * grace-period sequence number seq at which new callbacks would become
547 	 * whose ->gp_seq[] completion is at or after that passed in via  in rcu_segcblist_accelerate()
548 	 * "seq", skipping any empty segments.  This oldest segment, along  in rcu_segcblist_accelerate()
551 	 * as their ->gp_seq[] grace-period completion sequence number.  in rcu_segcblist_accelerate()
553 	for (i = RCU_NEXT_READY_TAIL; i > RCU_DONE_TAIL; i--)  in rcu_segcblist_accelerate()
554 		if (rsclp->tails[i] != rsclp->tails[i - 1] &&  in rcu_segcblist_accelerate()
555 		    ULONG_CMP_LT(rsclp->gp_seq[i], seq))  in rcu_segcblist_accelerate()
560 	 * earlier grace-period sequence numbers than "seq", leave.  in rcu_segcblist_accelerate()
563 	 * the non-done segments contain callbacks that really are  in rcu_segcblist_accelerate()
568 	 * ->gp_seq[] completion is at or after that passed in via "seq",  in rcu_segcblist_accelerate()
569 	 * skipping any empty segments.  in rcu_segcblist_accelerate()
571 	 * Note that segment "i" (and any lower-numbered segments  in rcu_segcblist_accelerate()
573 	 * grace-period numbers remain unchanged.  For example, if i ==  in rcu_segcblist_accelerate()
576 	 * NEXT_READY_TAIL and the grace-period number of NEXT_READY_TAIL  in rcu_segcblist_accelerate()
577 	 * would be updated.  NEXT_TAIL would then be empty.  in rcu_segcblist_accelerate()
588 	 * into the segment located by the for-loop above.  Assign "seq"  in rcu_segcblist_accelerate()
589 	 * as the ->gp_seq[] value in order to correctly handle the case  in rcu_segcblist_accelerate()
594 		WRITE_ONCE(rsclp->tails[i], rsclp->tails[RCU_NEXT_TAIL]);  in rcu_segcblist_accelerate()
595 		rsclp->gp_seq[i] = seq;  in rcu_segcblist_accelerate()