// 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_lock_count[] and ->srcu_unlock_count[]. */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. */ BUILD_BUG_ON(ARRAY_SIZE(sdp->srcu_lock_count) != ARRAY_SIZE(sdp->srcu_unlock_count)); 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 = kcalloc(rcu_num_nodes, sizeof(*ssp->srcu_sup->node), 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(sizeof(*ssp->srcu_sup), GFP_KERNEL); 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_idx = 0; 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); 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, GFP_ATOMIC)) 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 int __init_srcu_struct(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);}EXPORT_SYMBOL_GPL(__init_srcu_struct); #else /* #ifdef CONFIG_DEBUG_LOCK_ALLOC */ /** * init_srcu_struct - initialize a sleep-RCU structure * @ssp: structure to initialize. * * Must 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){ return init_srcu_struct_fields(ssp, false);}EXPORT_SYMBOL_GPL(init_srcu_struct); #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_lock_count[] 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_lock_count[idx]); 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_LITE && !gp) return false; return sum == unlocks;} /* * Returns approximate total of the readers' ->srcu_unlock_count[] 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 = 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_unlock_count[idx]); 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_LITE); /* * 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 beingLines 1–500 of 2061. Load more
// 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_lock_count[] and ->srcu_unlock_count[]. */ 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. */ BUILD_BUG_ON(ARRAY_SIZE(sdp->srcu_lock_count) != ARRAY_SIZE(sdp->srcu_unlock_count)); 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 = kcalloc(rcu_num_nodes, sizeof(*ssp->srcu_sup->node), 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(sizeof(*ssp->srcu_sup), GFP_KERNEL); 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_idx = 0; 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); 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, GFP_ATOMIC)) 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 int __init_srcu_struct(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); } EXPORT_SYMBOL_GPL(__init_srcu_struct); #else /* #ifdef CONFIG_DEBUG_LOCK_ALLOC */ /** * init_srcu_struct - initialize a sleep-RCU structure * @ssp: structure to initialize. * * Must 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) { return init_srcu_struct_fields(ssp, false); } EXPORT_SYMBOL_GPL(init_srcu_struct); #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_lock_count[] 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_lock_count[idx]); 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_LITE && !gp) return false; return sum == unlocks; } /* * Returns approximate total of the readers' ->srcu_unlock_count[] 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 = 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_unlock_count[idx]); 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_LITE); /* * 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