// SPDX-License-Identifier: GPL-2.0+

/*

* Sleepable Read-Copy Update mechanism for mutual exclusion.

*

* Copyright (C) IBM Corporation, 2006

* Copyright (C) Fujitsu, 2012

*

* Authors: Paul McKenney <paulmck@linux.ibm.com>

* Lai Jiangshan <laijs@cn.fujitsu.com>

*

* For detailed explanation of Read-Copy Update mechanism see -

* Documentation/RCU/ *.txt

*

*/

#define pr_fmt(fmt) "rcu: " fmt

#include <linux/export.h>

#include <linux/mutex.h>

#include <linux/percpu.h>

#include <linux/preempt.h>

#include <linux/rcupdate_wait.h>

#include <linux/sched.h>

#include <linux/smp.h>

#include <linux/delay.h>

#include <linux/module.h>

#include <linux/slab.h>

#include <linux/srcu.h>

#include "rcu.h"

#include "rcu_segcblist.h"

/* Holdoff in nanoseconds for auto-expediting. */

#define DEFAULT_SRCU_EXP_HOLDOFF (25 * 1000)

static ulong exp_holdoff = DEFAULT_SRCU_EXP_HOLDOFF;

module_param(exp_holdoff, ulong, 0444);

/* Overflow-check frequency. N bits roughly says every 2**N grace periods. */

static ulong counter_wrap_check = (ULONG_MAX >> 2);

module_param(counter_wrap_check, ulong, 0444);

/*

* Control conversion to SRCU_SIZE_BIG:

* 0: Don't convert at all.

* 1: Convert at init_srcu_struct() time.

* 2: Convert when rcutorture invokes srcu_torture_stats_print().

* 3: Decide at boot time based on system shape (default).

* 0x1x: Convert when excessive contention encountered.

*/

#define SRCU_SIZING_NONE 0

#define SRCU_SIZING_INIT 1

#define SRCU_SIZING_TORTURE 2

#define SRCU_SIZING_AUTO 3

#define SRCU_SIZING_CONTEND 0x10

#define SRCU_SIZING_IS(x) ((convert_to_big & ~SRCU_SIZING_CONTEND) == x)

#define SRCU_SIZING_IS_NONE() (SRCU_SIZING_IS(SRCU_SIZING_NONE))

#define SRCU_SIZING_IS_INIT() (SRCU_SIZING_IS(SRCU_SIZING_INIT))

#define SRCU_SIZING_IS_TORTURE() (SRCU_SIZING_IS(SRCU_SIZING_TORTURE))

#define SRCU_SIZING_IS_CONTEND() (convert_to_big & SRCU_SIZING_CONTEND)

static int convert_to_big = SRCU_SIZING_AUTO;

module_param(convert_to_big, int, 0444);

/* Number of CPUs to trigger init_srcu_struct()-time transition to big. */

static int big_cpu_lim __read_mostly = 128;

module_param(big_cpu_lim, int, 0444);

/* Contention events per jiffy to initiate transition to big. */

static int small_contention_lim __read_mostly = 100;

module_param(small_contention_lim, int, 0444);

/* Early-boot callback-management, so early that no lock is required! */

static LIST_HEAD(srcu_boot_list);

static bool __read_mostly srcu_init_done;

static void srcu_invoke_callbacks(struct work_struct *work);

static void srcu_reschedule(struct srcu_struct *ssp, unsigned long delay);

static void process_srcu(struct work_struct *work);

static void srcu_delay_timer(struct timer_list *t);

/* Wrappers for lock acquisition and release, see raw_spin_lock_rcu_node(). */

#define spin_lock_rcu_node(p) \

do { \

spin_lock(&ACCESS_PRIVATE(p, lock)); \

smp_mb__after_unlock_lock(); \

} while (0)

#define spin_unlock_rcu_node(p) spin_unlock(&ACCESS_PRIVATE(p, lock))

#define spin_lock_irq_rcu_node(p) \

do { \

spin_lock_irq(&ACCESS_PRIVATE(p, lock)); \

smp_mb__after_unlock_lock(); \

} while (0)

#define spin_unlock_irq_rcu_node(p) \

spin_unlock_irq(&ACCESS_PRIVATE(p, lock))

#define spin_lock_irqsave_rcu_node(p, flags) \

do { \

spin_lock_irqsave(&ACCESS_PRIVATE(p, lock), flags); \

smp_mb__after_unlock_lock(); \

} while (0)

#define spin_trylock_irqsave_rcu_node(p, flags) \

({ \

bool ___locked = spin_trylock_irqsave(&ACCESS_PRIVATE(p, lock), flags); \

\

if (___locked) \

smp_mb__after_unlock_lock(); \

___locked; \

})

#define spin_unlock_irqrestore_rcu_node(p, flags) \

spin_unlock_irqrestore(&ACCESS_PRIVATE(p, lock), flags) \

/*

* Initialize SRCU per-CPU data. Note that statically allocated

* srcu_struct structures might already have srcu_read_lock() and

* srcu_read_unlock() running against them. So if the is_static

* parameter is set, don't initialize ->srcu_ctrs[].srcu_locks and

* ->srcu_ctrs[].srcu_unlocks.

*/

static void init_srcu_struct_data(struct srcu_struct *ssp)

{

int cpu;

struct srcu_data *sdp;

/*

* Initialize the per-CPU srcu_data array, which feeds into the

* leaves of the srcu_node tree.

*/

for_each_possible_cpu(cpu) {

sdp = per_cpu_ptr(ssp->sda, cpu);

spin_lock_init(&ACCESS_PRIVATE(sdp, lock));

rcu_segcblist_init(&sdp->srcu_cblist);

sdp->srcu_cblist_invoking = false;

sdp->srcu_gp_seq_needed = ssp->srcu_sup->srcu_gp_seq;

sdp->srcu_gp_seq_needed_exp = ssp->srcu_sup->srcu_gp_seq;

sdp->srcu_barrier_head.next = &sdp->srcu_barrier_head;

sdp->mynode = NULL;

sdp->cpu = cpu;

INIT_WORK(&sdp->work, srcu_invoke_callbacks);

timer_setup(&sdp->delay_work, srcu_delay_timer, 0);

sdp->ssp = ssp;

}

}

/* Invalid seq state, used during snp node initialization */

#define SRCU_SNP_INIT_SEQ 0x2

/*

* Check whether sequence number corresponding to snp node,

* is invalid.

*/

static inline bool srcu_invl_snp_seq(unsigned long s)

{

return s == SRCU_SNP_INIT_SEQ;

}

/*

* Allocated and initialize SRCU combining tree. Returns @true if

* allocation succeeded and @false otherwise.

*/

static bool init_srcu_struct_nodes(struct srcu_struct *ssp, gfp_t gfp_flags)

{

int cpu;

int i;

int level = 0;

int levelspread[RCU_NUM_LVLS];

struct srcu_data *sdp;

struct srcu_node *snp;

struct srcu_node *snp_first;

/* Initialize geometry if it has not already been initialized. */

rcu_init_geometry();

ssp->srcu_sup->node = kzalloc_objs(*ssp->srcu_sup->node, rcu_num_nodes,

gfp_flags);

if (!ssp->srcu_sup->node)

return false;

/* Work out the overall tree geometry. */

ssp->srcu_sup->level[0] = &ssp->srcu_sup->node[0];

for (i = 1; i < rcu_num_lvls; i++)

ssp->srcu_sup->level[i] = ssp->srcu_sup->level[i - 1] + num_rcu_lvl[i - 1];

rcu_init_levelspread(levelspread, num_rcu_lvl);

/* Each pass through this loop initializes one srcu_node structure. */

srcu_for_each_node_breadth_first(ssp, snp) {

spin_lock_init(&ACCESS_PRIVATE(snp, lock));

BUILD_BUG_ON(ARRAY_SIZE(snp->srcu_have_cbs) !=

ARRAY_SIZE(snp->srcu_data_have_cbs));

for (i = 0; i < ARRAY_SIZE(snp->srcu_have_cbs); i++) {

snp->srcu_have_cbs[i] = SRCU_SNP_INIT_SEQ;

snp->srcu_data_have_cbs[i] = 0;

}

snp->srcu_gp_seq_needed_exp = SRCU_SNP_INIT_SEQ;

snp->grplo = -1;

snp->grphi = -1;

if (snp == &ssp->srcu_sup->node[0]) {

/* Root node, special case. */

snp->srcu_parent = NULL;

continue;

}

/* Non-root node. */

if (snp == ssp->srcu_sup->level[level + 1])

level++;

snp->srcu_parent = ssp->srcu_sup->level[level - 1] +

(snp - ssp->srcu_sup->level[level]) /

levelspread[level - 1];

}

/*

* Initialize the per-CPU srcu_data array, which feeds into the

* leaves of the srcu_node tree.

*/

level = rcu_num_lvls - 1;

snp_first = ssp->srcu_sup->level[level];

for_each_possible_cpu(cpu) {

sdp = per_cpu_ptr(ssp->sda, cpu);

sdp->mynode = &snp_first[cpu / levelspread[level]];

for (snp = sdp->mynode; snp != NULL; snp = snp->srcu_parent) {

if (snp->grplo < 0)

snp->grplo = cpu;

snp->grphi = cpu;

}

sdp->grpmask = 1UL << (cpu - sdp->mynode->grplo);

}

smp_store_release(&ssp->srcu_sup->srcu_size_state, SRCU_SIZE_WAIT_BARRIER);

return true;

}

/*

* Initialize non-compile-time initialized fields, including the

* associated srcu_node and srcu_data structures. The is_static parameter

* tells us that ->sda has already been wired up to srcu_data.

*/

static int init_srcu_struct_fields(struct srcu_struct *ssp, bool is_static)

{

if (!is_static)

ssp->srcu_sup = kzalloc_obj(*ssp->srcu_sup);

if (!ssp->srcu_sup)

return -ENOMEM;

if (!is_static)

spin_lock_init(&ACCESS_PRIVATE(ssp->srcu_sup, lock));

ssp->srcu_sup->srcu_size_state = SRCU_SIZE_SMALL;

ssp->srcu_sup->node = NULL;

mutex_init(&ssp->srcu_sup->srcu_cb_mutex);

mutex_init(&ssp->srcu_sup->srcu_gp_mutex);

ssp->srcu_sup->srcu_gp_seq = SRCU_GP_SEQ_INITIAL_VAL;

ssp->srcu_sup->srcu_barrier_seq = 0;

mutex_init(&ssp->srcu_sup->srcu_barrier_mutex);

atomic_set(&ssp->srcu_sup->srcu_barrier_cpu_cnt, 0);

INIT_DELAYED_WORK(&ssp->srcu_sup->work, process_srcu);

ssp->srcu_sup->sda_is_static = is_static;

if (!is_static) {

ssp->sda = alloc_percpu(struct srcu_data);

ssp->srcu_ctrp = &ssp->sda->srcu_ctrs[0];

}

if (!ssp->sda)

goto err_free_sup;

init_srcu_struct_data(ssp);

ssp->srcu_sup->srcu_gp_seq_needed_exp = SRCU_GP_SEQ_INITIAL_VAL;

ssp->srcu_sup->srcu_last_gp_end = ktime_get_mono_fast_ns();

if (READ_ONCE(ssp->srcu_sup->srcu_size_state) == SRCU_SIZE_SMALL && SRCU_SIZING_IS_INIT()) {

if (!init_srcu_struct_nodes(ssp, is_static ? GFP_ATOMIC : GFP_KERNEL))

goto err_free_sda;

WRITE_ONCE(ssp->srcu_sup->srcu_size_state, SRCU_SIZE_BIG);

}

ssp->srcu_sup->srcu_ssp = ssp;

smp_store_release(&ssp->srcu_sup->srcu_gp_seq_needed,

SRCU_GP_SEQ_INITIAL_VAL); /* Init done. */

return 0;

err_free_sda:

if (!is_static) {

free_percpu(ssp->sda);

ssp->sda = NULL;

}

err_free_sup:

if (!is_static) {

kfree(ssp->srcu_sup);

ssp->srcu_sup = NULL;

}

return -ENOMEM;

}

#ifdef CONFIG_DEBUG_LOCK_ALLOC

static int

__init_srcu_struct_common(struct srcu_struct *ssp, const char *name, struct lock_class_key *key)

{

/* Don't re-initialize a lock while it is held. */

debug_check_no_locks_freed((void *)ssp, sizeof(*ssp));

lockdep_init_map(&ssp->dep_map, name, key, 0);

return init_srcu_struct_fields(ssp, false);

}

int __init_srcu_struct(struct srcu_struct *ssp, const char *name, struct lock_class_key *key)

{

ssp->srcu_reader_flavor = 0;

return __init_srcu_struct_common(ssp, name, key);

}

EXPORT_SYMBOL_GPL(__init_srcu_struct);

int __init_srcu_struct_fast(struct srcu_struct *ssp, const char *name, struct lock_class_key *key)

{

ssp->srcu_reader_flavor = SRCU_READ_FLAVOR_FAST;

return __init_srcu_struct_common(ssp, name, key);

}

EXPORT_SYMBOL_GPL(__init_srcu_struct_fast);

int __init_srcu_struct_fast_updown(struct srcu_struct *ssp, const char *name,

struct lock_class_key *key)

{

ssp->srcu_reader_flavor = SRCU_READ_FLAVOR_FAST_UPDOWN;

return __init_srcu_struct_common(ssp, name, key);

}

EXPORT_SYMBOL_GPL(__init_srcu_struct_fast_updown);

#else /* #ifdef CONFIG_DEBUG_LOCK_ALLOC */

/**

* init_srcu_struct - initialize a sleep-RCU structure

* @ssp: structure to initialize.

*

* Use this in place of DEFINE_SRCU() and DEFINE_STATIC_SRCU()

* for non-static srcu_struct structures that are to be passed to

* srcu_read_lock(), srcu_read_lock_nmisafe(), and friends. It is necessary

* to invoke this on a given srcu_struct before passing that srcu_struct

* to any other function. Each srcu_struct represents a separate domain

* of SRCU protection.

*/

int init_srcu_struct(struct srcu_struct *ssp)

{

ssp->srcu_reader_flavor = 0;

return init_srcu_struct_fields(ssp, false);

}

EXPORT_SYMBOL_GPL(init_srcu_struct);

/**

* init_srcu_struct_fast - initialize a fast-reader sleep-RCU structure

* @ssp: structure to initialize.

*

* Use this in place of DEFINE_SRCU_FAST() and DEFINE_STATIC_SRCU_FAST()

* for non-static srcu_struct structures that are to be passed to

* srcu_read_lock_fast() and friends. It is necessary to invoke this on a

* given srcu_struct before passing that srcu_struct to any other function.

* Each srcu_struct represents a separate domain of SRCU protection.

*/

int init_srcu_struct_fast(struct srcu_struct *ssp)

{

ssp->srcu_reader_flavor = SRCU_READ_FLAVOR_FAST;

return init_srcu_struct_fields(ssp, false);

}

EXPORT_SYMBOL_GPL(init_srcu_struct_fast);

/**

* init_srcu_struct_fast_updown - initialize a fast-reader up/down sleep-RCU structure

* @ssp: structure to initialize.

*

* Use this function in place of DEFINE_SRCU_FAST_UPDOWN() and

* DEFINE_STATIC_SRCU_FAST_UPDOWN() for non-static srcu_struct

* structures that are to be passed to srcu_read_lock_fast_updown(),

* srcu_down_read_fast(), and friends. It is necessary to invoke this on a

* given srcu_struct before passing that srcu_struct to any other function.

* Each srcu_struct represents a separate domain of SRCU protection.

*/

int init_srcu_struct_fast_updown(struct srcu_struct *ssp)

{

ssp->srcu_reader_flavor = SRCU_READ_FLAVOR_FAST_UPDOWN;

return init_srcu_struct_fields(ssp, false);

}

EXPORT_SYMBOL_GPL(init_srcu_struct_fast_updown);

#endif /* #else #ifdef CONFIG_DEBUG_LOCK_ALLOC */

/*

* Initiate a transition to SRCU_SIZE_BIG with lock held.

*/

static void __srcu_transition_to_big(struct srcu_struct *ssp)

{

lockdep_assert_held(&ACCESS_PRIVATE(ssp->srcu_sup, lock));

smp_store_release(&ssp->srcu_sup->srcu_size_state, SRCU_SIZE_ALLOC);

}

/*

* Initiate an idempotent transition to SRCU_SIZE_BIG.

*/

static void srcu_transition_to_big(struct srcu_struct *ssp)

{

unsigned long flags;

/* Double-checked locking on ->srcu_size-state. */

if (smp_load_acquire(&ssp->srcu_sup->srcu_size_state) != SRCU_SIZE_SMALL)

return;

spin_lock_irqsave_rcu_node(ssp->srcu_sup, flags);

if (smp_load_acquire(&ssp->srcu_sup->srcu_size_state) != SRCU_SIZE_SMALL) {

spin_unlock_irqrestore_rcu_node(ssp->srcu_sup, flags);

return;

}

__srcu_transition_to_big(ssp);

spin_unlock_irqrestore_rcu_node(ssp->srcu_sup, flags);

}

/*

* Check to see if the just-encountered contention event justifies

* a transition to SRCU_SIZE_BIG.

*/

static void spin_lock_irqsave_check_contention(struct srcu_struct *ssp)

{

unsigned long j;

if (!SRCU_SIZING_IS_CONTEND() || ssp->srcu_sup->srcu_size_state)

return;

j = jiffies;

if (ssp->srcu_sup->srcu_size_jiffies != j) {

ssp->srcu_sup->srcu_size_jiffies = j;

ssp->srcu_sup->srcu_n_lock_retries = 0;

}

if (++ssp->srcu_sup->srcu_n_lock_retries <= small_contention_lim)

return;

__srcu_transition_to_big(ssp);

}

/*

* Acquire the specified srcu_data structure's ->lock, but check for

* excessive contention, which results in initiation of a transition

* to SRCU_SIZE_BIG. But only if the srcutree.convert_to_big module

* parameter permits this.

*/

static void spin_lock_irqsave_sdp_contention(struct srcu_data *sdp, unsigned long *flags)

{

struct srcu_struct *ssp = sdp->ssp;

if (spin_trylock_irqsave_rcu_node(sdp, *flags))

return;

spin_lock_irqsave_rcu_node(ssp->srcu_sup, *flags);

spin_lock_irqsave_check_contention(ssp);

spin_unlock_irqrestore_rcu_node(ssp->srcu_sup, *flags);

spin_lock_irqsave_rcu_node(sdp, *flags);

}

/*

* Acquire the specified srcu_struct structure's ->lock, but check for

* excessive contention, which results in initiation of a transition

* to SRCU_SIZE_BIG. But only if the srcutree.convert_to_big module

* parameter permits this.

*/

static void spin_lock_irqsave_ssp_contention(struct srcu_struct *ssp, unsigned long *flags)

{

if (spin_trylock_irqsave_rcu_node(ssp->srcu_sup, *flags))

return;

spin_lock_irqsave_rcu_node(ssp->srcu_sup, *flags);

spin_lock_irqsave_check_contention(ssp);

}

/*

* First-use initialization of statically allocated srcu_struct

* structure. Wiring up the combining tree is more than can be

* done with compile-time initialization, so this check is added

* to each update-side SRCU primitive. Use ssp->lock, which -is-

* compile-time initialized, to resolve races involving multiple

* CPUs trying to garner first-use privileges.

*/

static void check_init_srcu_struct(struct srcu_struct *ssp)

{

unsigned long flags;

/* The smp_load_acquire() pairs with the smp_store_release(). */

if (!rcu_seq_state(smp_load_acquire(&ssp->srcu_sup->srcu_gp_seq_needed))) /*^^^*/

return; /* Already initialized. */

spin_lock_irqsave_rcu_node(ssp->srcu_sup, flags);

if (!rcu_seq_state(ssp->srcu_sup->srcu_gp_seq_needed)) {

spin_unlock_irqrestore_rcu_node(ssp->srcu_sup, flags);

return;

}

init_srcu_struct_fields(ssp, true);

spin_unlock_irqrestore_rcu_node(ssp->srcu_sup, flags);

}

/*

* Is the current or any upcoming grace period to be expedited?

*/

static bool srcu_gp_is_expedited(struct srcu_struct *ssp)

{

struct srcu_usage *sup = ssp->srcu_sup;

return ULONG_CMP_LT(READ_ONCE(sup->srcu_gp_seq), READ_ONCE(sup->srcu_gp_seq_needed_exp));

}

/*

* Computes approximate total of the readers' ->srcu_ctrs[].srcu_locks

* values for the rank of per-CPU counters specified by idx, and returns

* true if the caller did the proper barrier (gp), and if the count of

* the locks matches that of the unlocks passed in.

*/

static bool srcu_readers_lock_idx(struct srcu_struct *ssp, int idx, bool gp, unsigned long unlocks)

{

int cpu;

unsigned long mask = 0;

unsigned long sum = 0;

for_each_possible_cpu(cpu) {

struct srcu_data *sdp = per_cpu_ptr(ssp->sda, cpu);

sum += atomic_long_read(&sdp->srcu_ctrs[idx].srcu_locks);

if (IS_ENABLED(CONFIG_PROVE_RCU))

mask = mask | READ_ONCE(sdp->srcu_reader_flavor);

}

WARN_ONCE(IS_ENABLED(CONFIG_PROVE_RCU) && (mask & (mask - 1)),

"Mixed reader flavors for srcu_struct at %ps.\n", ssp);

if (mask & SRCU_READ_FLAVOR_SLOWGP && !gp)

return false;

return sum == unlocks;

}

/*

* Returns approximate total of the readers' ->srcu_ctrs[].srcu_unlocks

* values for the rank of per-CPU counters specified by idx.

*/

static unsigned long srcu_readers_unlock_idx(struct srcu_struct *ssp, int idx, unsigned long *rdm)

{

int cpu;

unsigned long mask = ssp->srcu_reader_flavor;

unsigned long sum = 0;

for_each_possible_cpu(cpu) {

struct srcu_data *sdp = per_cpu_ptr(ssp->sda, cpu);

sum += atomic_long_read(&sdp->srcu_ctrs[idx].srcu_unlocks);

mask = mask | READ_ONCE(sdp->srcu_reader_flavor);

}

WARN_ONCE(IS_ENABLED(CONFIG_PROVE_RCU) && (mask & (mask - 1)),

"Mixed reader flavors for srcu_struct at %ps.\n", ssp);

*rdm = mask;

return sum;

}

/*

* Return true if the number of pre-existing readers is determined to

* be zero.

*/

static bool srcu_readers_active_idx_check(struct srcu_struct *ssp, int idx)

{

bool did_gp;

unsigned long rdm;

unsigned long unlocks;

unlocks = srcu_readers_unlock_idx(ssp, idx, &rdm);

did_gp = !!(rdm & SRCU_READ_FLAVOR_SLOWGP);

/*

* Make sure that a lock is always counted if the corresponding

* unlock is counted. Needs to be a smp_mb() as the read side may

* contain a read from a variable that is written to before the

* synchronize_srcu() in the write side. In this case smp_mb()s

* A and B (or X and Y) act like the store buffering pattern.

*

* This smp_mb() also pairs with smp_mb() C (or, in the case of X,

* Z) to prevent accesses after the synchronize_srcu() from being

* executed before the grace period ends.

*/

if (!did_gp)

smp_mb(); /* A */

else if (srcu_gp_is_expedited(ssp))

synchronize_rcu_expedited(); /* X */

else

synchronize_rcu(); /* X */

/*

* If the locks are the same as the unlocks, then there must have

* been no readers on this index at some point in this function.

* But there might be more readers, as a task might have read

* the current ->srcu_ctrp but not yet have incremented its CPU's

* ->srcu_ctrs[idx].srcu_locks counter. In fact, it is possible

* that most of the tasks have been preempted between fetching

* ->srcu_ctrp and incrementing ->srcu_ctrs[idx].srcu_locks. And

* there could be almost (ULONG_MAX / sizeof(struct task_struct))

* tasks in a system whose address space was fully populated

* with memory. Call this quantity Nt.

*

* So suppose that the updater is preempted at this

* point in the code for a long time. That now-preempted

* updater has already flipped ->srcu_ctrp (possibly during

* the preceding grace period), done an smp_mb() (again,

* possibly during the preceding grace period), and summed up

* the ->srcu_ctrs[idx].srcu_unlocks counters. How many times

* can a given one of the aforementioned Nt tasks increment the

* old ->srcu_ctrp value's ->srcu_ctrs[idx].srcu_locks counter,

* in the absence of nesting?

*

* It can clearly do so once, given that it has already fetched

* the old value of ->srcu_ctrp and is just about to use that

* value to index its increment of ->srcu_ctrs[idx].srcu_locks.

* But as soon as it leaves that SRCU read-side critical section,

* it will increment ->srcu_ctrs[idx].srcu_unlocks, which must

* follow the updater's above read from that same value. Thus,

as soon the reading task does an smp_mb() and a later fetch from

* ->srcu_ctrp, that task will be guaranteed to get the new index.

* Except that the increment of ->srcu_ctrs[idx].srcu_unlocks

* in __srcu_read_unlock() is after the smp_mb(), and the fetch

* from ->srcu_ctrp in __srcu_read_lock() is before the smp_mb().

* Thus, that task might not see the new value of ->srcu_ctrp until

* the -second- __srcu_read_lock(), which in turn means that this

* task might well increment ->srcu_ctrs[idx].srcu_locks for the

* old value of ->srcu_ctrp twice, not just once.

*

* However, it is important to note that a given smp_mb() takes

* effect not just for the task executing it, but also for any

* later task running on that same CPU.

*

* That is, there can be almost Nt + Nc further increments

* of ->srcu_ctrs[idx].srcu_locks for the old index, where Nc

* is the number of CPUs. But this is OK because the size of

* the task_struct structure limits the value of Nt and current

* systems limit Nc to a few thousand.

*

* OK, but what about nesting? This does impose a limit on

* nesting of half of the size of the task_struct structure

* (measured in bytes), which should be sufficient. A late 2022

* TREE01 rcutorture run reported this size to be no less than

* 9408 bytes, allowing up to 4704 levels of nesting, which is

* comfortably beyond excessive. Especially on 64-bit systems,

* which are unlikely to be configured with an address space fully

* populated with memory, at least not anytime soon.

*/

return srcu_readers_lock_idx(ssp, idx, did_gp, unlocks);

}

/**

* srcu_readers_active - returns true if there are readers. and false

* otherwise

* @ssp: which srcu_struct to count active readers (holding srcu_read_lock).

*

* Note that this is not an atomic primitive, and can therefore suffer

* severe errors when invoked on an active srcu_struct. That said, it

* can be useful as an error check at cleanup time.

*/

static bool srcu_readers_active(struct srcu_struct *ssp)

{

int cpu;

unsigned long sum = 0;

for_each_possible_cpu(cpu) {

struct srcu_data *sdp = per_cpu_ptr(ssp->sda, cpu);

sum += atomic_long_read(&sdp->srcu_ctrs[0].srcu_locks);

sum += atomic_long_read(&sdp->srcu_ctrs[1].srcu_locks);

sum -= atomic_long_read(&sdp->srcu_ctrs[0].srcu_unlocks);

sum -= atomic_long_read(&sdp->srcu_ctrs[1].srcu_unlocks);

}

return sum;

}

/*

* We use an adaptive strategy for synchronize_srcu() and especially for

* synchronize_srcu_expedited(). We spin for a fixed time period

* (defined below, boot time configurable) to allow SRCU readers to exit

* their read-side critical sections. If there are still some readers

* after one jiffy, we repeatedly block for one jiffy time periods.

* The blocking time is increased as the grace-period age increases,

* with max blocking time capped at 10 jiffies.

*/

#define SRCU_DEFAULT_RETRY_CHECK_DELAY 5

static ulong srcu_retry_check_delay = SRCU_DEFAULT_RETRY_CHECK_DELAY;

module_param(srcu_retry_check_delay, ulong, 0444);

#define SRCU_INTERVAL 1 // Base delay if no expedited GPs pending.

#define SRCU_MAX_INTERVAL 10 // Maximum incremental delay from slow readers.

#define SRCU_DEFAULT_MAX_NODELAY_PHASE_LO 3UL // Lowmark on default per-GP-phase

// no-delay instances.

#define SRCU_DEFAULT_MAX_NODELAY_PHASE_HI 1000UL // Highmark on default per-GP-phase

// no-delay instances.

#define SRCU_UL_CLAMP_LO(val, low) ((val) > (low) ? (val) : (low))

#define SRCU_UL_CLAMP_HI(val, high) ((val) < (high) ? (val) : (high))

#define SRCU_UL_CLAMP(val, low, high) SRCU_UL_CLAMP_HI(SRCU_UL_CLAMP_LO((val), (low)), (high))

// per-GP-phase no-delay instances adjusted to allow non-sleeping poll upto

// one jiffies time duration. Mult by 2 is done to factor in the srcu_get_delay()

// called from process_srcu().

#define SRCU_DEFAULT_MAX_NODELAY_PHASE_ADJUSTED \

(2UL * USEC_PER_SEC / HZ / SRCU_DEFAULT_RETRY_CHECK_DELAY)

// Maximum per-GP-phase consecutive no-delay instances.

#define SRCU_DEFAULT_MAX_NODELAY_PHASE \

SRCU_UL_CLAMP(SRCU_DEFAULT_MAX_NODELAY_PHASE_ADJUSTED, \

SRCU_DEFAULT_MAX_NODELAY_PHASE_LO, \

SRCU_DEFAULT_MAX_NODELAY_PHASE_HI)

static ulong srcu_max_nodelay_phase = SRCU_DEFAULT_MAX_NODELAY_PHASE;

module_param(srcu_max_nodelay_phase, ulong, 0444);

// Maximum consecutive no-delay instances.

#define SRCU_DEFAULT_MAX_NODELAY (SRCU_DEFAULT_MAX_NODELAY_PHASE > 100 ? \

SRCU_DEFAULT_MAX_NODELAY_PHASE : 100)

static ulong srcu_max_nodelay = SRCU_DEFAULT_MAX_NODELAY;

module_param(srcu_max_nodelay, ulong, 0444);

/*

* Return grace-period delay, zero if there are expedited grace

* periods pending, SRCU_INTERVAL otherwise.

*/

static unsigned long srcu_get_delay(struct srcu_struct *ssp)

{

unsigned long gpstart;

unsigned long j;

unsigned long jbase = SRCU_INTERVAL;

struct srcu_usage *sup = ssp->srcu_sup;

lockdep_assert_held(&ACCESS_PRIVATE(ssp->srcu_sup, lock));

if (srcu_gp_is_expedited(ssp))

jbase = 0;

if (rcu_seq_state(READ_ONCE(sup->srcu_gp_seq))) {

j = jiffies - 1;

gpstart = READ_ONCE(sup->srcu_gp_start);

if (time_after(j, gpstart))

jbase += j - gpstart;

if (!jbase) {

ASSERT_EXCLUSIVE_WRITER(sup->srcu_n_exp_nodelay);

WRITE_ONCE(sup->srcu_n_exp_nodelay, READ_ONCE(sup->srcu_n_exp_nodelay) + 1);

if (READ_ONCE(sup->srcu_n_exp_nodelay) > srcu_max_nodelay_phase)

jbase = 1;

}

}

return jbase > SRCU_MAX_INTERVAL ? SRCU_MAX_INTERVAL : jbase;

}

/**

* cleanup_srcu_struct - deconstruct a sleep-RCU structure

* @ssp: structure to clean up.

*

* Must invoke this after you are finished using a given srcu_struct that

* was initialized via init_srcu_struct(), else you leak memory.

*/

void cleanup_srcu_struct(struct srcu_struct *ssp)

{

int cpu;

unsigned long delay;

struct srcu_usage *sup = ssp->srcu_sup;

spin_lock_irq_rcu_node(ssp->srcu_sup);

delay = srcu_get_delay(ssp);

spin_unlock_irq_rcu_node(ssp->srcu_sup);

if (WARN_ON(!delay))

return; /* Just leak it! */

if (WARN_ON(srcu_readers_active(ssp)))

return; /* Just leak it! */

flush_delayed_work(&sup->work);

for_each_possible_cpu(cpu) {

struct srcu_data *sdp = per_cpu_ptr(ssp->sda, cpu);

timer_delete_sync(&sdp->delay_work);

flush_work(&sdp->work);

if (WARN_ON(rcu_segcblist_n_cbs(&sdp->srcu_cblist)))

return; /* Forgot srcu_barrier(), so just leak it! */

}

if (WARN_ON(rcu_seq_state(READ_ONCE(sup->srcu_gp_seq)) != SRCU_STATE_IDLE) ||

WARN_ON(rcu_seq_current(&sup->srcu_gp_seq) != sup->srcu_gp_seq_needed) ||

WARN_ON(srcu_readers_active(ssp))) {

pr_info("%s: Active srcu_struct %p read state: %d gp state: %lu/%lu\n",

__func__, ssp, rcu_seq_state(READ_ONCE(sup->srcu_gp_seq)),

rcu_seq_current(&sup->srcu_gp_seq), sup->srcu_gp_seq_needed);

return; // Caller forgot to stop doing call_srcu()?

// Or caller invoked start_poll_synchronize_srcu()

// and then cleanup_srcu_struct() before that grace

// period ended?

}

kfree(sup->node);

sup->node = NULL;

sup->srcu_size_state = SRCU_SIZE_SMALL;

if (!sup->sda_is_static) {

free_percpu(ssp->sda);

ssp->sda = NULL;

kfree(sup);

ssp->srcu_sup = NULL;

}

}

EXPORT_SYMBOL_GPL(cleanup_srcu_struct);

/*

* Check for consistent reader flavor.

*/

void __srcu_check_read_flavor(struct srcu_struct *ssp, int read_flavor)

{

int old_read_flavor;

struct srcu_data *sdp;

/* NMI-unsafe use in NMI is a bad sign, as is multi-bit read_flavor values. */

WARN_ON_ONCE(read_flavor != SRCU_READ_FLAVOR_NMI &&

read_flavor != SRCU_READ_FLAVOR_FAST && in_nmi());

WARN_ON_ONCE(read_flavor & (read_flavor - 1));

sdp = raw_cpu_ptr(ssp->sda);

old_read_flavor = READ_ONCE(sdp->srcu_reader_flavor);

WARN_ON_ONCE(ssp->srcu_reader_flavor && read_flavor != ssp->srcu_reader_flavor);

WARN_ON_ONCE(old_read_flavor && ssp->srcu_reader_flavor &&

old_read_flavor != ssp->srcu_reader_flavor);

WARN_ON_ONCE(read_flavor == SRCU_READ_FLAVOR_FAST && !ssp->srcu_reader_flavor);

if (!old_read_flavor) {

old_read_flavor = cmpxchg(&sdp->srcu_reader_flavor, 0, read_flavor);

if (!old_read_flavor)

return;

}

WARN_ONCE(old_read_flavor != read_flavor, "CPU %d old state %d new state %d\n", sdp->cpu, old_read_flavor, read_flavor);

}

EXPORT_SYMBOL_GPL(__srcu_check_read_flavor);

/*

* Counts the new reader in the appropriate per-CPU element of the

* srcu_struct.

* Returns a guaranteed non-negative index that must be passed to the

* matching __srcu_read_unlock().

*/

int __srcu_read_lock(struct srcu_struct *ssp)

{

struct srcu_ctr __percpu *scp = READ_ONCE(ssp->srcu_ctrp);

this_cpu_inc(scp->srcu_locks.counter);

smp_mb(); /* B */ /* Avoid leaking the critical section. */

return __srcu_ptr_to_ctr(ssp, scp);

}

EXPORT_SYMBOL_GPL(__srcu_read_lock);

/*

* Removes the count for the old reader from the appropriate per-CPU

* element of the srcu_struct. Note that this may well be a different

* CPU than that which was incremented by the corresponding srcu_read_lock().

*/

void __srcu_read_unlock(struct srcu_struct *ssp, int idx)

{

smp_mb(); /* C */ /* Avoid leaking the critical section. */

this_cpu_inc(__srcu_ctr_to_ptr(ssp, idx)->srcu_unlocks.counter);

}

EXPORT_SYMBOL_GPL(__srcu_read_unlock);

#ifdef CONFIG_NEED_SRCU_NMI_SAFE

/*

* Counts the new reader in the appropriate per-CPU element of the

* srcu_struct, but in an NMI-safe manner using RMW atomics.

* Returns an index that must be passed to the matching srcu_read_unlock().

*/

int __srcu_read_lock_nmisafe(struct srcu_struct *ssp)

{

struct srcu_ctr __percpu *scpp = READ_ONCE(ssp->srcu_ctrp);

struct srcu_ctr *scp = raw_cpu_ptr(scpp);

atomic_long_inc(&scp->srcu_locks);

smp_mb__after_atomic(); /* B */ /* Avoid leaking the critical section. */

return __srcu_ptr_to_ctr(ssp, scpp);

}

EXPORT_SYMBOL_GPL(__srcu_read_lock_nmisafe);

/*

* Removes the count for the old reader from the appropriate per-CPU

* element of the srcu_struct. Note that this may well be a different

* CPU than that which was incremented by the corresponding srcu_read_lock().

*/

void __srcu_read_unlock_nmisafe(struct srcu_struct *ssp, int idx)

{

smp_mb__before_atomic(); /* C */ /* Avoid leaking the critical section. */

atomic_long_inc(&raw_cpu_ptr(__srcu_ctr_to_ptr(ssp, idx))->srcu_unlocks);

}

EXPORT_SYMBOL_GPL(__srcu_read_unlock_nmisafe);

#endif // CONFIG_NEED_SRCU_NMI_SAFE

/*

* Start an SRCU grace period.

*/

static void srcu_gp_start(struct srcu_struct *ssp)

{

int state;

lockdep_assert_held(&ACCESS_PRIVATE(ssp->srcu_sup, lock));

WARN_ON_ONCE(ULONG_CMP_GE(ssp->srcu_sup->srcu_gp_seq, ssp->srcu_sup->srcu_gp_seq_needed));

WRITE_ONCE(ssp->srcu_sup->srcu_gp_start, jiffies);

WRITE_ONCE(ssp->srcu_sup->srcu_n_exp_nodelay, 0);

smp_mb(); /* Order prior store to ->srcu_gp_seq_needed vs. GP start. */

rcu_seq_start(&ssp->srcu_sup->srcu_gp_seq);

state = rcu_seq_state(ssp->srcu_sup->srcu_gp_seq);

WARN_ON_ONCE(state != SRCU_STATE_SCAN1);

}

static void srcu_delay_timer(struct timer_list *t)

{

struct srcu_data *sdp = container_of(t, struct srcu_data, delay_work);

queue_work_on(sdp->cpu, rcu_gp_wq, &sdp->work);

}

static void srcu_queue_delayed_work_on(struct srcu_data *sdp,

unsigned long delay)

{

if (!delay) {

queue_work_on(sdp->cpu, rcu_gp_wq, &sdp->work);

return;

}

timer_reduce(&sdp->delay_work, jiffies + delay);

}

/*

* Schedule callback invocation for the specified srcu_data structure,

* if possible, on the corresponding CPU.

*/

static void srcu_schedule_cbs_sdp(struct srcu_data *sdp, unsigned long delay)

{

srcu_queue_delayed_work_on(sdp, delay);

}

/*

* Schedule callback invocation for all srcu_data structures associated

* with the specified srcu_node structure that have callbacks for the

* just-completed grace period, the one corresponding to idx. If possible,

* schedule this invocation on the corresponding CPUs.

*/

static void srcu_schedule_cbs_snp(struct srcu_struct *ssp, struct srcu_node *snp,

unsigned long mask, unsigned long delay)

{

int cpu;

for (cpu = snp->grplo; cpu <= snp->grphi; cpu++) {

if (!(mask & (1UL << (cpu - snp->grplo))))

continue;

srcu_schedule_cbs_sdp(per_cpu_ptr(ssp->sda, cpu), delay);

}

}

/*

* Note the end of an SRCU grace period. Initiates callback invocation

* and starts a new grace period if needed.

*

* The ->srcu_cb_mutex acquisition does not protect any data, but

* instead prevents more than one grace period from starting while we

* are initiating callback invocation. This allows the ->srcu_have_cbs[]

* array to have a finite number of elements.

*/

static void srcu_gp_end(struct srcu_struct *ssp)

{

unsigned long cbdelay = 1;

bool cbs;

bool last_lvl;

int cpu;

unsigned long gpseq;

int idx;

unsigned long mask;

struct srcu_data *sdp;

unsigned long sgsne;

struct srcu_node *snp;

int ss_state;

struct srcu_usage *sup = ssp->srcu_sup;

/* Prevent more than one additional grace period. */

mutex_lock(&sup->srcu_cb_mutex);

/* End the current grace period. */

spin_lock_irq_rcu_node(sup);

idx = rcu_seq_state(sup->srcu_gp_seq);

WARN_ON_ONCE(idx != SRCU_STATE_SCAN2);

if (srcu_gp_is_expedited(ssp))

cbdelay = 0;

WRITE_ONCE(sup->srcu_last_gp_end, ktime_get_mono_fast_ns());

rcu_seq_end(&sup->srcu_gp_seq);

gpseq = rcu_seq_current(&sup->srcu_gp_seq);

if (ULONG_CMP_LT(sup->srcu_gp_seq_needed_exp, gpseq))

WRITE_ONCE(sup->srcu_gp_seq_needed_exp, gpseq);

spin_unlock_irq_rcu_node(sup);

mutex_unlock(&sup->srcu_gp_mutex);

/* A new grace period can start at this point. But only one. */

/* Initiate callback invocation as needed. */

ss_state = smp_load_acquire(&sup->srcu_size_state);

if (ss_state < SRCU_SIZE_WAIT_BARRIER) {

srcu_schedule_cbs_sdp(per_cpu_ptr(ssp->sda, get_boot_cpu_id()),

cbdelay);

} else {

idx = rcu_seq_ctr(gpseq) % ARRAY_SIZE(snp->srcu_have_cbs);

srcu_for_each_node_breadth_first(ssp, snp) {

spin_lock_irq_rcu_node(snp);

cbs = false;

last_lvl = snp >= sup->level[rcu_num_lvls - 1];

if (last_lvl)

cbs = ss_state < SRCU_SIZE_BIG || snp->srcu_have_cbs[idx] == gpseq;

snp->srcu_have_cbs[idx] = gpseq;

rcu_seq_set_state(&snp->srcu_have_cbs[idx], 1);

sgsne = snp->srcu_gp_seq_needed_exp;

if (srcu_invl_snp_seq(sgsne) || ULONG_CMP_LT(sgsne, gpseq))

WRITE_ONCE(snp->srcu_gp_seq_needed_exp, gpseq);

if (ss_state < SRCU_SIZE_BIG)

mask = ~0;

else

mask = snp->srcu_data_have_cbs[idx];

snp->srcu_data_have_cbs[idx] = 0;