// SPDX-License-Identifier: GPL-2.0+
/*
* RCU segmented callback lists, function definitions
*
* Copyright IBM Corporation, 2017
*
* Authors: Paul E. McKenney <[email protected]>
*/
#include <linux/cpu.h>
#include <linux/interrupt.h>
#include <linux/kernel.h>
#include <linux/types.h>
#include "rcu_segcblist.h"
/* Initialize simple callback list. */
void rcu_cblist_init(struct rcu_cblist *rclp)
{
rclp->head = NULL;
rclp->tail = &rclp->head;
rclp->len = 0;
}
/*
* Enqueue an rcu_head structure onto the specified callback list.
*/
void rcu_cblist_enqueue(struct rcu_cblist *rclp, struct rcu_head *rhp)
{
*rclp->tail = rhp;
rclp->tail = &rhp->next;
WRITE_ONCE(rclp->len, rclp->len + 1);
}
/*
* Flush the second rcu_cblist structure onto the first one, obliterating
* any contents of the first. If rhp is non-NULL, enqueue it as the sole
* element of the second rcu_cblist structure, but ensuring that the second
* rcu_cblist structure, if initially non-empty, always appears non-empty
* throughout the process. If rdp is NULL, the second rcu_cblist structure
* is instead initialized to empty.
*/
void rcu_cblist_flush_enqueue(struct rcu_cblist *drclp,
struct rcu_cblist *srclp,
struct rcu_head *rhp)
{
drclp->head = srclp->head;
if (drclp->head)
drclp->tail = srclp->tail;
else
drclp->tail = &drclp->head;
drclp->len = srclp->len;
if (!rhp) {
rcu_cblist_init(srclp);
} else {
rhp->next = NULL;
srclp->head = rhp;
srclp->tail = &rhp->next;
WRITE_ONCE(srclp->len, 1);
}
}
/*
* Dequeue the oldest rcu_head structure from the specified callback
* list.
*/
struct rcu_head *rcu_cblist_dequeue(struct rcu_cblist *rclp)
{
struct rcu_head *rhp;
rhp = rclp->head;
if (!rhp)
return NULL;
rclp->len--;
rclp->head = rhp->next;
if (!rclp->head)
rclp->tail = &rclp->head;
return rhp;
}
/* Set the length of an rcu_segcblist structure. */
static void rcu_segcblist_set_len(struct rcu_segcblist *rsclp, long v)
{
#ifdef CONFIG_RCU_NOCB_CPU
atomic_long_set(&rsclp->len, v);
#else
WRITE_ONCE(rsclp->len, v);
#endif
}
/* Get the length of a segment of the rcu_segcblist structure. */
long rcu_segcblist_get_seglen(struct rcu_segcblist *rsclp, int seg)
{
return READ_ONCE(rsclp->seglen[seg]);
}
/* Return number of callbacks in segmented callback list by summing seglen. */
long rcu_segcblist_n_segment_cbs(struct rcu_segcblist *rsclp)
{
long len = 0;
int i;
for (i = RCU_DONE_TAIL; i < RCU_CBLIST_NSEGS; i++)
len += rcu_segcblist_get_seglen(rsclp, i);
return len;
}
/* Set the length of a segment of the rcu_segcblist structure. */
static void rcu_segcblist_set_seglen(struct rcu_segcblist *rsclp, int seg, long v)
{
WRITE_ONCE(rsclp->seglen[seg], v);
}
/* Increase the numeric length of a segment by a specified amount. */
static void rcu_segcblist_add_seglen(struct rcu_segcblist *rsclp, int seg, long v)
{
WRITE_ONCE(rsclp->seglen[seg], rsclp->seglen[seg] + v);
}
/* Move from's segment length to to's segment. */
static void rcu_segcblist_move_seglen(struct rcu_segcblist *rsclp, int from, int to)
{
long len;
if (from == to)
return;
len = rcu_segcblist_get_seglen(rsclp, from);
if (!len)
return;
rcu_segcblist_add_seglen(rsclp, to, len);
rcu_segcblist_set_seglen(rsclp, from, 0);
}
/* Increment segment's length. */
static void rcu_segcblist_inc_seglen(struct rcu_segcblist *rsclp, int seg)
{
rcu_segcblist_add_seglen(rsclp, seg, 1);
}
/*
* Increase the numeric length of an rcu_segcblist structure by the
* specified amount, which can be negative. This can cause the ->len
* field to disagree with the actual number of callbacks on the structure.
* This increase is fully ordered with respect to the callers accesses
* both before and after.
*
* So why on earth is a memory barrier required both before and after
* the update to the ->len field???
*
* The reason is that rcu_barrier() locklessly samples each CPU's ->len
* field, and if a given CPU's field is zero, avoids IPIing that CPU.
* This can of course race with both queuing and invoking of callbacks.
* Failing to correctly handle either of these races could result in
* rcu_barrier() failing to IPI a CPU that actually had callbacks queued
* which rcu_barrier() was obligated to wait on. And if rcu_barrier()
* failed to wait on such a callback, unloading certain kernel modules
* would result in calls to functions whose code was no longer present in
* the kernel, for but one example.
*
* Therefore, ->len transitions from 1->0 and 0->1 have to be carefully
* ordered with respect with both list modifications and the rcu_barrier().
*
* The queuing case is CASE 1 and the invoking case is CASE 2.
*
* CASE 1: Suppose that CPU 0 has no callbacks queued, but invokes
* call_rcu() just as CPU 1 invokes rcu_barrier(). CPU 0's ->len field
* will transition from 0->1, which is one of the transitions that must
* be handled carefully. Without the full memory barriers after the ->len
* update and at the beginning of rcu_barrier(), the following could happen:
*
* CPU 0 CPU 1
*
* call_rcu().
* rcu_barrier() sees ->len as 0.
* set ->len = 1.
* rcu_barrier() does nothing.
* module is unloaded.
* callback invokes unloaded function!
*
* With the full barriers, any case where rcu_barrier() sees ->len as 0 will
* have unambiguously preceded the return from the racing call_rcu(), which
* means that this call_rcu() invocation is OK to not wait on. After all,
* you are supposed to make sure that any problematic call_rcu() invocations
* happen before the rcu_barrier().
*
*
* CASE 2: Suppose that CPU 0 is invoking its last callback just as
* CPU 1 invokes rcu_barrier(). CPU 0's ->len field will transition from
* 1->0, which is one of the transitions that must be handled carefully.
* Without the full memory barriers before the ->len update and at the
* end of rcu_barrier(), the following could happen:
*
* CPU 0 CPU 1
*
* start invoking last callback
* set ->len = 0 (reordered)
* rcu_barrier() sees ->len as 0
* rcu_barrier() does nothing.
* module is unloaded
* callback executing after unloaded!
*
* With the full barriers, any case where rcu_barrier() sees ->len as 0
* will be fully ordered after the completion of the callback function,
* so that the module unloading operation is completely safe.
*
*/
void rcu_segcblist_add_len(struct rcu_segcblist *rsclp, long v)
{
#ifdef CONFIG_RCU_NOCB_CPU
smp_mb__before_atomic(); // Read header comment above.
atomic_long_add(v, &rsclp->len);
smp_mb__after_atomic(); // Read header comment above.
#else
smp_mb(); // Read header comment above.
WRITE_ONCE(rsclp->len, rsclp->len + v);
smp_mb(); // Read header comment above.
#endif
}
/*
* Increase the numeric length of an rcu_segcblist structure by one.
* This can cause the ->len field to disagree with the actual number of
* callbacks on the structure. This increase is fully ordered with respect
* to the callers accesses both before and after.
*/
void rcu_segcblist_inc_len(struct rcu_segcblist *rsclp)
{
rcu_segcblist_add_len(rsclp, 1);
}
/*
* Initialize an rcu_segcblist structure.
*/
void rcu_segcblist_init(struct rcu_segcblist *rsclp)
{
int i;
BUILD_BUG_ON(RCU_NEXT_TAIL + 1 != ARRAY_SIZE(rsclp->gp_seq));
BUILD_BUG_ON(ARRAY_SIZE(rsclp->tails) != ARRAY_SIZE(rsclp->gp_seq));
rsclp->head = NULL;
for (i = 0; i < RCU_CBLIST_NSEGS; i++) {
rsclp->tails[i] = &rsclp->head;
rcu_segcblist_set_seglen(rsclp, i, 0);
}
rcu_segcblist_set_len(rsclp, 0);
rcu_segcblist_set_flags(rsclp, SEGCBLIST_ENABLED);
}
/*
* Disable the specified rcu_segcblist structure, so that callbacks can
* no longer be posted to it. This structure must be empty.
*/
void rcu_segcblist_disable(struct rcu_segcblist *rsclp)
{
WARN_ON_ONCE(!rcu_segcblist_empty(rsclp));
WARN_ON_ONCE(rcu_segcblist_n_cbs(rsclp));
rcu_segcblist_clear_flags(rsclp, SEGCBLIST_ENABLED);
}
/*
* Does the specified rcu_segcblist structure contain callbacks that
* are ready to be invoked?
*/
bool rcu_segcblist_ready_cbs(struct rcu_segcblist *rsclp)
{
return rcu_segcblist_is_enabled(rsclp) &&
&rsclp->head != READ_ONCE(rsclp->tails[RCU_DONE_TAIL]);
}
/*
* Does the specified rcu_segcblist structure contain callbacks that
* are still pending, that is, not yet ready to be invoked?
*/
bool rcu_segcblist_pend_cbs(struct rcu_segcblist *rsclp)
{
return rcu_segcblist_is_enabled(rsclp) &&
!rcu_segcblist_restempty(rsclp, RCU_DONE_TAIL);
}
/*
* Return a pointer to the first callback in the specified rcu_segcblist
* structure. This is useful for diagnostics.
*/
struct rcu_head *rcu_segcblist_first_cb(struct rcu_segcblist *rsclp)
{
if (rcu_segcblist_is_enabled(rsclp))
return rsclp->head;
return NULL;
}
/*
* Return a pointer to the first pending callback in the specified
* rcu_segcblist structure. This is useful just after posting a given
* callback -- if that callback is the first pending callback, then
* you cannot rely on someone else having already started up the required
* grace period.
*/
struct rcu_head *rcu_segcblist_first_pend_cb(struct rcu_segcblist *rsclp)
{
if (rcu_segcblist_is_enabled(rsclp))
return *rsclp->tails[RCU_DONE_TAIL];
return NULL;
}
/*
* Return false if there are no CBs awaiting grace periods, otherwise,
* return true and store the nearest waited-upon grace period into *lp.
*/
bool rcu_segcblist_nextgp(struct rcu_segcblist *rsclp, unsigned long *lp)
{
if (!rcu_segcblist_pend_cbs(rsclp))
return false;
*lp = rsclp->gp_seq[RCU_WAIT_TAIL];
return true;
}
/*
* Enqueue the specified callback onto the specified rcu_segcblist
* structure, updating accounting as needed. Note that the ->len
* field may be accessed locklessly, hence the WRITE_ONCE().
* The ->len field is used by rcu_barrier() and friends to determine
* if it must post a callback on this structure, and it is OK
* for rcu_barrier() to sometimes post callbacks needlessly, but
* absolutely not OK for it to ever miss posting a callback.
*/
void rcu_segcblist_enqueue(struct rcu_segcblist *rsclp,
struct rcu_head *rhp)
{
rcu_segcblist_inc_len(rsclp);
rcu_segcblist_inc_seglen(rsclp, RCU_NEXT_TAIL);
rhp->next = NULL;
WRITE_ONCE(*rsclp->tails[RCU_NEXT_TAIL], rhp);
WRITE_ONCE(rsclp->tails[RCU_NEXT_TAIL], &rhp->next);
}
/*
* Entrain the specified callback onto the specified rcu_segcblist at
* the end of the last non-empty segment. If the entire rcu_segcblist
* is empty, make no change, but return false.
*
* This is intended for use by rcu_barrier()-like primitives, -not-
* for normal grace-period use. IMPORTANT: The callback you enqueue
* will wait for all prior callbacks, NOT necessarily for a grace
* period. You have been warned.
*/
bool rcu_segcblist_entrain(struct rcu_segcblist *rsclp,
struct rcu_head *rhp)
{
int i;
if (rcu_segcblist_n_cbs(rsclp) == 0)
return false;
rcu_segcblist_inc_len(rsclp);
smp_mb(); /* Ensure counts are updated before callback is entrained. */
rhp->next = NULL;
for (i = RCU_NEXT_TAIL; i > RCU_DONE_TAIL; i--)
if (!rcu_segcblist_segempty(rsclp, i))
break;
rcu_segcblist_inc_seglen(rsclp, i);
WRITE_ONCE(*rsclp->tails[i], rhp);
for (; i <= RCU_NEXT_TAIL; i++)
WRITE_ONCE(rsclp->tails[i], &rhp->next);
return true;
}
/*
* Extract only those callbacks ready to be invoked from the specified
* rcu_segcblist structure and place them in the specified rcu_cblist
* structure.
*/
void rcu_segcblist_extract_done_cbs(struct rcu_segcblist *rsclp,
struct rcu_cblist *rclp)
{
int i;
if (!rcu_segcblist_ready_cbs(rsclp))
return; /* Nothing to do. */
rclp->len = rcu_segcblist_get_seglen(rsclp, RCU_DONE_TAIL);
*rclp->tail = rsclp->head;
WRITE_ONCE(rsclp->head, *rsclp->tails[RCU_DONE_TAIL]);
WRITE_ONCE(*rsclp->tails[RCU_DONE_TAIL], NULL);
rclp->tail = rsclp->tails[RCU_DONE_TAIL];
for (i = RCU_CBLIST_NSEGS - 1; i >= RCU_DONE_TAIL; i--)
if (rsclp->tails[i] == rsclp->tails[RCU_DONE_TAIL])
WRITE_ONCE(rsclp->tails[i], &rsclp->head);
rcu_segcblist_set_seglen(rsclp, RCU_DONE_TAIL, 0);
}
/*
* Extract only those callbacks still pending (not yet ready to be
* invoked) from the specified rcu_segcblist structure and place them in
* the specified rcu_cblist structure. Note that this loses information
* about any callbacks that might have been partway done waiting for
* their grace period. Too bad! They will have to start over.
*/
void rcu_segcblist_extract_pend_cbs(struct rcu_segcblist *rsclp,
struct rcu_cblist *rclp)
{
int i;
if (!rcu_segcblist_pend_cbs(rsclp))
return; /* Nothing to do. */
rclp->len = 0;
*rclp->tail = *rsclp->tails[RCU_DONE_TAIL];
rclp->tail = rsclp->tails[RCU_NEXT_TAIL];
WRITE_ONCE(*rsclp->tails[RCU_DONE_TAIL], NULL);
for (i = RCU_DONE_TAIL + 1; i < RCU_CBLIST_NSEGS; i++) {
rclp->len += rcu_segcblist_get_seglen(rsclp, i);
WRITE_ONCE(rsclp->tails[i], rsclp->tails[RCU_DONE_TAIL]);
rcu_segcblist_set_seglen(rsclp, i, 0);
}
}
/*
* Insert counts from the specified rcu_cblist structure in the
* specified rcu_segcblist structure.
*/
void rcu_segcblist_insert_count(struct rcu_segcblist *rsclp,
struct rcu_cblist *rclp)
{
rcu_segcblist_add_len(rsclp, rclp->len);
}
/*
* Move callbacks from the specified rcu_cblist to the beginning of the
* done-callbacks segment of the specified rcu_segcblist.
*/
void rcu_segcblist_insert_done_cbs(struct rcu_segcblist *rsclp,
struct rcu_cblist *rclp)
{
int i;
if (!rclp->head)
return; /* No callbacks to move. */
rcu_segcblist_add_seglen(rsclp, RCU_DONE_TAIL, rclp->len);
*rclp->tail = rsclp->head;
WRITE_ONCE(rsclp->head, rclp->head);
for (i = RCU_DONE_TAIL; i < RCU_CBLIST_NSEGS; i++)
if (&rsclp->head == rsclp->tails[i])
WRITE_ONCE(rsclp->tails[i], rclp->tail);
else
break;
rclp->head = NULL;
rclp->tail = &rclp->head;
}
/*
* Move callbacks from the specified rcu_cblist to the end of the
* new-callbacks segment of the specified rcu_segcblist.
*/
void rcu_segcblist_insert_pend_cbs(struct rcu_segcblist *rsclp,
struct rcu_cblist *rclp)
{
if (!rclp->head)
return; /* Nothing to do. */
rcu_segcblist_add_seglen(rsclp, RCU_NEXT_TAIL, rclp->len);
WRITE_ONCE(*rsclp->tails[RCU_NEXT_TAIL], rclp->head);
WRITE_ONCE(rsclp->tails[RCU_NEXT_TAIL], rclp->tail);
}
/*
* Advance the callbacks in the specified rcu_segcblist structure based
* on the current value passed in for the grace-period counter.
*/
void rcu_segcblist_advance(struct rcu_segcblist *rsclp, unsigned long seq)
{
int i, j;
WARN_ON_ONCE(!rcu_segcblist_is_enabled(rsclp));
if (rcu_segcblist_restempty(rsclp, RCU_DONE_TAIL))
return;
/*
* Find all callbacks whose ->gp_seq numbers indicate that they
* are ready to invoke, and put them into the RCU_DONE_TAIL segment.
*/
for (i = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++) {
if (ULONG_CMP_LT(seq, rsclp->gp_seq[i]))
break;
WRITE_ONCE(rsclp->tails[RCU_DONE_TAIL], rsclp->tails[i]);
rcu_segcblist_move_seglen(rsclp, i, RCU_DONE_TAIL);
}
/* If no callbacks moved, nothing more need be done. */
if (i == RCU_WAIT_TAIL)
return;
/* Clean up tail pointers that might have been misordered above. */
for (j = RCU_WAIT_TAIL; j < i; j++)
WRITE_ONCE(rsclp->tails[j], rsclp->tails[RCU_DONE_TAIL]);
/*
* Callbacks moved, so there might be an empty RCU_WAIT_TAIL
* and a non-empty RCU_NEXT_READY_TAIL. If so, copy the
* RCU_NEXT_READY_TAIL segment to fill the RCU_WAIT_TAIL gap
* created by the now-ready-to-invoke segments.
*/
for (j = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++, j++) {
if (rsclp->tails[j] == rsclp->tails[RCU_NEXT_TAIL])
break; /* No more callbacks. */
WRITE_ONCE(rsclp->tails[j], rsclp->tails[i]);
rcu_segcblist_move_seglen(rsclp, i, j);
rsclp->gp_seq[j] = rsclp->gp_seq[i];
}
}
/*
* "Accelerate" callbacks based on more-accurate grace-period information.
* The reason for this is that RCU does not synchronize the beginnings and
* ends of grace periods, and that callbacks are posted locally. This in
* turn means that the callbacks must be labelled conservatively early
* on, as getting exact information would degrade both performance and
* scalability. When more accurate grace-period information becomes
* available, previously posted callbacks can be "accelerated", marking
* them to complete at the end of the earlier grace period.
*
* This function operates on an rcu_segcblist structure, and also the
* grace-period sequence number seq at which new callbacks would become
* ready to invoke. Returns true if there are callbacks that won't be
* ready to invoke until seq, false otherwise.
*/
bool rcu_segcblist_accelerate(struct rcu_segcblist *rsclp, unsigned long seq)
{
int i, j;
WARN_ON_ONCE(!rcu_segcblist_is_enabled(rsclp));
if (rcu_segcblist_restempty(rsclp, RCU_DONE_TAIL))
return false;
/*
* Find the segment preceding the oldest segment of callbacks
* whose ->gp_seq[] completion is at or after that passed in via
* "seq", skipping any empty segments. This oldest segment, along
* with any later segments, can be merged in with any newly arrived
* callbacks in the RCU_NEXT_TAIL segment, and assigned "seq"
* as their ->gp_seq[] grace-period completion sequence number.
*/
for (i = RCU_NEXT_READY_TAIL; i > RCU_DONE_TAIL; i--)
if (!rcu_segcblist_segempty(rsclp, i) &&
ULONG_CMP_LT(rsclp->gp_seq[i], seq))
break;
/*
* If all the segments contain callbacks that correspond to
* earlier grace-period sequence numbers than "seq", leave.
* Assuming that the rcu_segcblist structure has enough
* segments in its arrays, this can only happen if some of
* the non-done segments contain callbacks that really are
* ready to invoke. This situation will get straightened
* out by the next call to rcu_segcblist_advance().
*
* Also advance to the oldest segment of callbacks whose
* ->gp_seq[] completion is at or after that passed in via "seq",
* skipping any empty segments.
*
* Note that segment "i" (and any lower-numbered segments
* containing older callbacks) will be unaffected, and their
* grace-period numbers remain unchanged. For example, if i ==
* WAIT_TAIL, then neither WAIT_TAIL nor DONE_TAIL will be touched.
* Instead, the CBs in NEXT_TAIL will be merged with those in
* NEXT_READY_TAIL and the grace-period number of NEXT_READY_TAIL
* would be updated. NEXT_TAIL would then be empty.
*/
if (rcu_segcblist_restempty(rsclp, i) || ++i >= RCU_NEXT_TAIL)
return false;
/* Accounting: everything below i is about to get merged into i. */
for (j = i + 1; j <= RCU_NEXT_TAIL; j++)
rcu_segcblist_move_seglen(rsclp, j, i);
/*
* Merge all later callbacks, including newly arrived callbacks,
* into the segment located by the for-loop above. Assign "seq"
* as the ->gp_seq[] value in order to correctly handle the case
* where there were no pending callbacks in the rcu_segcblist
* structure other than in the RCU_NEXT_TAIL segment.
*/
for (; i < RCU_NEXT_TAIL; i++) {
WRITE_ONCE(rsclp->tails[i], rsclp->tails[RCU_NEXT_TAIL]);
rsclp->gp_seq[i] = seq;
}
return true;
}
/*
* Merge the source rcu_segcblist structure into the destination
* rcu_segcblist structure, then initialize the source. Any pending
* callbacks from the source get to start over. It is best to
* advance and accelerate both the destination and the source
* before merging.
*/
void rcu_segcblist_merge(struct rcu_segcblist *dst_rsclp,
struct rcu_segcblist *src_rsclp)
{
struct rcu_cblist donecbs;
struct rcu_cblist pendcbs;
lockdep_assert_cpus_held();
rcu_cblist_init(&donecbs);
rcu_cblist_init(&pendcbs);
rcu_segcblist_extract_done_cbs(src_rsclp, &donecbs);
rcu_segcblist_extract_pend_cbs(src_rsclp, &pendcbs);
/*
* No need smp_mb() before setting length to 0, because CPU hotplug
* lock excludes rcu_barrier.
*/
rcu_segcblist_set_len(src_rsclp, 0);
rcu_segcblist_insert_count(dst_rsclp, &donecbs);
rcu_segcblist_insert_count(dst_rsclp, &pendcbs);
rcu_segcblist_insert_done_cbs(dst_rsclp, &donecbs);
rcu_segcblist_insert_pend_cbs(dst_rsclp, &pendcbs);
rcu_segcblist_init(src_rsclp);
}
Codebase Browser
linux