/* * Sleepable Read-Copy Update mechanism for mutual exclusion. * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, you can access it online at * http://www.gnu.org/licenses/gpl-2.0.html. * * Copyright (C) IBM Corporation, 2006 * Copyright (C) Fujitsu, 2012 * * Author: Paul McKenney <paulmck@us.ibm.com> * Lai Jiangshan <laijs@cn.fujitsu.com> * * For detailed explanation of Read-Copy Update mechanism see - * Documentation/RCU/ *.txt * */ #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/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); static void srcu_invoke_callbacks(struct work_struct *work);static void srcu_reschedule(struct srcu_struct *sp, unsigned long delay); /* * Initialize SRCU combining tree. 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_nodes(struct srcu_struct *sp, bool is_static){ 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; /* Work out the overall tree geometry. */ sp->level[0] = &sp->node[0]; for (i = 1; i < rcu_num_lvls; i++) sp->level[i] = sp->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. */ rcu_for_each_node_breadth_first(sp, snp) { raw_spin_lock_init(&ACCESS_PRIVATE(snp, lock)); WARN_ON_ONCE(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] = 0; snp->srcu_data_have_cbs[i] = 0; } snp->srcu_gp_seq_needed_exp = 0; snp->grplo = -1; snp->grphi = -1; if (snp == &sp->node[0]) { /* Root node, special case. */ snp->srcu_parent = NULL; continue; } /* Non-root node. */ if (snp == sp->level[level + 1]) level++; snp->srcu_parent = sp->level[level - 1] + (snp - sp->level[level]) / levelspread[level - 1]; } /* * Initialize the per-CPU srcu_data array, which feeds into the * leaves of the srcu_node tree. */ WARN_ON_ONCE(ARRAY_SIZE(sdp->srcu_lock_count) != ARRAY_SIZE(sdp->srcu_unlock_count)); level = rcu_num_lvls - 1; snp_first = sp->level[level]; for_each_possible_cpu(cpu) { sdp = per_cpu_ptr(sp->sda, cpu); raw_spin_lock_init(&ACCESS_PRIVATE(sdp, lock)); rcu_segcblist_init(&sdp->srcu_cblist); sdp->srcu_cblist_invoking = false; sdp->srcu_gp_seq_needed = sp->srcu_gp_seq; sdp->srcu_gp_seq_needed_exp = sp->srcu_gp_seq; 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->cpu = cpu; INIT_DELAYED_WORK(&sdp->work, srcu_invoke_callbacks); sdp->sp = sp; sdp->grpmask = 1 << (cpu - sdp->mynode->grplo); if (is_static) continue; /* Dynamically allocated, better be no srcu_read_locks()! */ for (i = 0; i < ARRAY_SIZE(sdp->srcu_lock_count); i++) { sdp->srcu_lock_count[i] = 0; sdp->srcu_unlock_count[i] = 0; } }} /* * Initialize non-compile-time initialized fields, including the * associated srcu_node and srcu_data structures. The is_static * parameter is passed through to init_srcu_struct_nodes(), and * also tells us that ->sda has already been wired up to srcu_data. */static int init_srcu_struct_fields(struct srcu_struct *sp, bool is_static){ mutex_init(&sp->srcu_cb_mutex); mutex_init(&sp->srcu_gp_mutex); sp->srcu_idx = 0; sp->srcu_gp_seq = 0; sp->srcu_barrier_seq = 0; mutex_init(&sp->srcu_barrier_mutex); atomic_set(&sp->srcu_barrier_cpu_cnt, 0); INIT_DELAYED_WORK(&sp->work, process_srcu); if (!is_static) sp->sda = alloc_percpu(struct srcu_data); init_srcu_struct_nodes(sp, is_static); sp->srcu_gp_seq_needed_exp = 0; sp->srcu_last_gp_end = ktime_get_mono_fast_ns(); smp_store_release(&sp->srcu_gp_seq_needed, 0); /* Init done. */ return sp->sda ? 0 : -ENOMEM;} #ifdef CONFIG_DEBUG_LOCK_ALLOC int __init_srcu_struct(struct srcu_struct *sp, const char *name, struct lock_class_key *key){ /* Don't re-initialize a lock while it is held. */ debug_check_no_locks_freed((void *)sp, sizeof(*sp)); lockdep_init_map(&sp->dep_map, name, key, 0); raw_spin_lock_init(&ACCESS_PRIVATE(sp, lock)); return init_srcu_struct_fields(sp, false);}EXPORT_SYMBOL_GPL(__init_srcu_struct); #else /* #ifdef CONFIG_DEBUG_LOCK_ALLOC */ /** * init_srcu_struct - initialize a sleep-RCU structure * @sp: 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 *sp){ raw_spin_lock_init(&ACCESS_PRIVATE(sp, lock)); return init_srcu_struct_fields(sp, false);}EXPORT_SYMBOL_GPL(init_srcu_struct); #endif /* #else #ifdef CONFIG_DEBUG_LOCK_ALLOC */ /* * 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 sp->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 *sp){ unsigned long flags; WARN_ON_ONCE(rcu_scheduler_active == RCU_SCHEDULER_INIT); /* The smp_load_acquire() pairs with the smp_store_release(). */ if (!rcu_seq_state(smp_load_acquire(&sp->srcu_gp_seq_needed))) /*^^^*/ return; /* Already initialized. */ raw_spin_lock_irqsave_rcu_node(sp, flags); if (!rcu_seq_state(sp->srcu_gp_seq_needed)) { raw_spin_unlock_irqrestore_rcu_node(sp, flags); return; } init_srcu_struct_fields(sp, true); raw_spin_unlock_irqrestore_rcu_node(sp, flags);} /* * Returns approximate total of the readers' ->srcu_lock_count[] values * for the rank of per-CPU counters specified by idx. */static unsigned long srcu_readers_lock_idx(struct srcu_struct *sp, int idx){ int cpu; unsigned long sum = 0; for_each_possible_cpu(cpu) { struct srcu_data *cpuc = per_cpu_ptr(sp->sda, cpu); sum += READ_ONCE(cpuc->srcu_lock_count[idx]); } return sum;} /* * 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 *sp, int idx){ int cpu; unsigned long sum = 0; for_each_possible_cpu(cpu) { struct srcu_data *cpuc = per_cpu_ptr(sp->sda, cpu); sum += READ_ONCE(cpuc->srcu_unlock_count[idx]); } 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 *sp, int idx){ unsigned long unlocks; unlocks = srcu_readers_unlock_idx(sp, idx); /* * 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 act like the store buffering pattern. * * This smp_mb() also pairs with smp_mb() C to prevent accesses * after the synchronize_srcu() from being executed before the * grace period ends. */ smp_mb(); /* A */ /* * If the locks are the same as the unlocks, then there must have * been no readers on this index at some time in between. This does * not mean that there are no more readers, as one could have read * the current index but not have incremented the lock counter yet. * * So suppose that the updater is preempted here for so long * that more than ULONG_MAX non-nested readers come and go in * the meantime. It turns out that this cannot result in overflow * because if a reader modifies its unlock count after we read it * above, then that reader's next load of ->srcu_idx is guaranteed * to get the new value, which will cause it to operate on the * other bank of counters, where it cannot contribute to the * overflow of these counters. This means that there is a maximum * of 2*NR_CPUS increments, which cannot overflow given current * systems, especially not on 64-bit systems. * * OK, how about nesting? This does impose a limit on nesting * of floor(ULONG_MAX/NR_CPUS/2), which should be sufficient, * especially on 64-bit systems. */ return srcu_readers_lock_idx(sp, idx) == unlocks;} /** * srcu_readers_active - returns true if there are readers. and false * otherwise * @sp: 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 *sp){ int cpu; unsigned long sum = 0; for_each_possible_cpu(cpu) { struct srcu_data *cpuc = per_cpu_ptr(sp->sda, cpu); sum += READ_ONCE(cpuc->srcu_lock_count[0]); sum += READ_ONCE(cpuc->srcu_lock_count[1]); sum -= READ_ONCE(cpuc->srcu_unlock_count[0]); sum -= READ_ONCE(cpuc->srcu_unlock_count[1]); } return sum;} #define SRCU_INTERVAL 1 /* * Return grace-period delay, zero if there are expedited grace * periods pending, SRCU_INTERVAL otherwise. */static unsigned long srcu_get_delay(struct srcu_struct *sp){ if (ULONG_CMP_LT(READ_ONCE(sp->srcu_gp_seq), READ_ONCE(sp->srcu_gp_seq_needed_exp))) return 0; return SRCU_INTERVAL;} /** * cleanup_srcu_struct - deconstruct a sleep-RCU structure * @sp: 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 *sp){ int cpu; if (WARN_ON(!srcu_get_delay(sp))) return; /* Leakage unless caller handles error. */ if (WARN_ON(srcu_readers_active(sp))) return; /* Leakage unless caller handles error. */ flush_delayed_work(&sp->work); for_each_possible_cpu(cpu) flush_delayed_work(&per_cpu_ptr(sp->sda, cpu)->work); if (WARN_ON(rcu_seq_state(READ_ONCE(sp->srcu_gp_seq)) != SRCU_STATE_IDLE) || WARN_ON(srcu_readers_active(sp))) { pr_info("cleanup_srcu_struct: Active srcu_struct %p state: %d\n", sp, rcu_seq_state(READ_ONCE(sp->srcu_gp_seq))); return; /* Caller forgot to stop doing call_srcu()? */ } free_percpu(sp->sda); sp->sda = NULL;}EXPORT_SYMBOL_GPL(cleanup_srcu_struct); /* * Counts the new reader in the appropriate per-CPU element of the * srcu_struct. * Returns an index that must be passed to the matching srcu_read_unlock(). */int __srcu_read_lock(struct srcu_struct *sp){ int idx; idx = READ_ONCE(sp->srcu_idx) & 0x1; this_cpu_inc(sp->sda->srcu_lock_count[idx]); smp_mb(); /* B */ /* Avoid leaking the critical section. */ return idx;}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 *sp, int idx){ smp_mb(); /* C */ /* Avoid leaking the critical section. */ this_cpu_inc(sp->sda->srcu_unlock_count[idx]);}EXPORT_SYMBOL_GPL(__srcu_read_unlock); /* * We use an adaptive strategy for synchronize_srcu() and especially for * synchronize_srcu_expedited(). We spin for a fixed time period * (defined below) to allow SRCU readers to exit their read-side critical * sections. If there are still some readers after a few microseconds, * we repeatedly block for 1-millisecond time periods. */#define SRCU_RETRY_CHECK_DELAY 5 /* * Start an SRCU grace period. */static void srcu_gp_start(struct srcu_struct *sp){ struct srcu_data *sdp = this_cpu_ptr(sp->sda); int state; lockdep_assert_held(&sp->lock); WARN_ON_ONCE(ULONG_CMP_GE(sp->srcu_gp_seq, sp->srcu_gp_seq_needed)); rcu_segcblist_advance(&sdp->srcu_cblist, rcu_seq_current(&sp->srcu_gp_seq)); (void)rcu_segcblist_accelerate(&sdp->srcu_cblist, rcu_seq_snap(&sp->srcu_gp_seq)); smp_mb(); /* Order prior store to ->srcu_gp_seq_needed vs. GP start. */ rcu_seq_start(&sp->srcu_gp_seq); state = rcu_seq_state(READ_ONCE(sp->srcu_gp_seq)); WARN_ON_ONCE(state != SRCU_STATE_SCAN1);} /* * Track online CPUs to guide callback workqueue placement. */DEFINE_PER_CPU(bool, srcu_online); void srcu_online_cpu(unsigned int cpu){ WRITE_ONCE(per_cpu(srcu_online, cpu), true);} void srcu_offline_cpu(unsigned int cpu){ WRITE_ONCE(per_cpu(srcu_online, cpu), false);} /* * Place the workqueue handler on the specified CPU if online, otherwise * just run it whereever. This is useful for placing workqueue handlers * that are to invoke the specified CPU's callbacks. */static bool srcu_queue_delayed_work_on(int cpu, struct workqueue_struct *wq, struct delayed_work *dwork, unsigned long delay){ bool ret; preempt_disable(); if (READ_ONCE(per_cpu(srcu_online, cpu))) ret = queue_delayed_work_on(cpu, wq, dwork, delay); else ret = queue_delayed_work(wq, dwork, delay); preempt_enable(); return ret;} /* * 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->cpu, system_power_efficient_wq, &sdp->work, 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 *sp, struct srcu_node *snp, unsigned long mask, unsigned long delay){ int cpu; for (cpu = snp->grplo; cpu <= snp->grphi; cpu++) { if (!(mask & (1 << (cpu - snp->grplo)))) continue; srcu_schedule_cbs_sdp(per_cpu_ptr(sp->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 *sp){ unsigned long cbdelay;Lines 1–500 of 1227. Load more
/* * Sleepable Read-Copy Update mechanism for mutual exclusion. * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, you can access it online at * http://www.gnu.org/licenses/gpl-2.0.html. * * Copyright (C) IBM Corporation, 2006 * Copyright (C) Fujitsu, 2012 * * Author: Paul McKenney <paulmck@us.ibm.com> * Lai Jiangshan <laijs@cn.fujitsu.com> * * For detailed explanation of Read-Copy Update mechanism see - * Documentation/RCU/ *.txt * */ #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/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); static void srcu_invoke_callbacks(struct work_struct *work); static void srcu_reschedule(struct srcu_struct *sp, unsigned long delay); /* * Initialize SRCU combining tree. 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_nodes(struct srcu_struct *sp, bool is_static) { 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; /* Work out the overall tree geometry. */ sp->level[0] = &sp->node[0]; for (i = 1; i < rcu_num_lvls; i++) sp->level[i] = sp->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. */ rcu_for_each_node_breadth_first(sp, snp) { raw_spin_lock_init(&ACCESS_PRIVATE(snp, lock)); WARN_ON_ONCE(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] = 0; snp->srcu_data_have_cbs[i] = 0; } snp->srcu_gp_seq_needed_exp = 0; snp->grplo = -1; snp->grphi = -1; if (snp == &sp->node[0]) { /* Root node, special case. */ snp->srcu_parent = NULL; continue; } /* Non-root node. */ if (snp == sp->level[level + 1]) level++; snp->srcu_parent = sp->level[level - 1] + (snp - sp->level[level]) / levelspread[level - 1]; } /* * Initialize the per-CPU srcu_data array, which feeds into the * leaves of the srcu_node tree. */ WARN_ON_ONCE(ARRAY_SIZE(sdp->srcu_lock_count) != ARRAY_SIZE(sdp->srcu_unlock_count)); level = rcu_num_lvls - 1; snp_first = sp->level[level]; for_each_possible_cpu(cpu) { sdp = per_cpu_ptr(sp->sda, cpu); raw_spin_lock_init(&ACCESS_PRIVATE(sdp, lock)); rcu_segcblist_init(&sdp->srcu_cblist); sdp->srcu_cblist_invoking = false; sdp->srcu_gp_seq_needed = sp->srcu_gp_seq; sdp->srcu_gp_seq_needed_exp = sp->srcu_gp_seq; 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->cpu = cpu; INIT_DELAYED_WORK(&sdp->work, srcu_invoke_callbacks); sdp->sp = sp; sdp->grpmask = 1 << (cpu - sdp->mynode->grplo); if (is_static) continue; /* Dynamically allocated, better be no srcu_read_locks()! */ for (i = 0; i < ARRAY_SIZE(sdp->srcu_lock_count); i++) { sdp->srcu_lock_count[i] = 0; sdp->srcu_unlock_count[i] = 0; } } } /* * Initialize non-compile-time initialized fields, including the * associated srcu_node and srcu_data structures. The is_static * parameter is passed through to init_srcu_struct_nodes(), and * also tells us that ->sda has already been wired up to srcu_data. */ static int init_srcu_struct_fields(struct srcu_struct *sp, bool is_static) { mutex_init(&sp->srcu_cb_mutex); mutex_init(&sp->srcu_gp_mutex); sp->srcu_idx = 0; sp->srcu_gp_seq = 0; sp->srcu_barrier_seq = 0; mutex_init(&sp->srcu_barrier_mutex); atomic_set(&sp->srcu_barrier_cpu_cnt, 0); INIT_DELAYED_WORK(&sp->work, process_srcu); if (!is_static) sp->sda = alloc_percpu(struct srcu_data); init_srcu_struct_nodes(sp, is_static); sp->srcu_gp_seq_needed_exp = 0; sp->srcu_last_gp_end = ktime_get_mono_fast_ns(); smp_store_release(&sp->srcu_gp_seq_needed, 0); /* Init done. */ return sp->sda ? 0 : -ENOMEM; } #ifdef CONFIG_DEBUG_LOCK_ALLOC int __init_srcu_struct(struct srcu_struct *sp, const char *name, struct lock_class_key *key) { /* Don't re-initialize a lock while it is held. */ debug_check_no_locks_freed((void *)sp, sizeof(*sp)); lockdep_init_map(&sp->dep_map, name, key, 0); raw_spin_lock_init(&ACCESS_PRIVATE(sp, lock)); return init_srcu_struct_fields(sp, false); } EXPORT_SYMBOL_GPL(__init_srcu_struct); #else /* #ifdef CONFIG_DEBUG_LOCK_ALLOC */ /** * init_srcu_struct - initialize a sleep-RCU structure * @sp: 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 *sp) { raw_spin_lock_init(&ACCESS_PRIVATE(sp, lock)); return init_srcu_struct_fields(sp, false); } EXPORT_SYMBOL_GPL(init_srcu_struct); #endif /* #else #ifdef CONFIG_DEBUG_LOCK_ALLOC */ /* * 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 sp->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 *sp) { unsigned long flags; WARN_ON_ONCE(rcu_scheduler_active == RCU_SCHEDULER_INIT); /* The smp_load_acquire() pairs with the smp_store_release(). */ if (!rcu_seq_state(smp_load_acquire(&sp->srcu_gp_seq_needed))) /*^^^*/ return; /* Already initialized. */ raw_spin_lock_irqsave_rcu_node(sp, flags); if (!rcu_seq_state(sp->srcu_gp_seq_needed)) { raw_spin_unlock_irqrestore_rcu_node(sp, flags); return; } init_srcu_struct_fields(sp, true); raw_spin_unlock_irqrestore_rcu_node(sp, flags); } /* * Returns approximate total of the readers' ->srcu_lock_count[] values * for the rank of per-CPU counters specified by idx. */ static unsigned long srcu_readers_lock_idx(struct srcu_struct *sp, int idx) { int cpu; unsigned long sum = 0; for_each_possible_cpu(cpu) { struct srcu_data *cpuc = per_cpu_ptr(sp->sda, cpu); sum += READ_ONCE(cpuc->srcu_lock_count[idx]); } return sum; } /* * 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 *sp, int idx) { int cpu; unsigned long sum = 0; for_each_possible_cpu(cpu) { struct srcu_data *cpuc = per_cpu_ptr(sp->sda, cpu); sum += READ_ONCE(cpuc->srcu_unlock_count[idx]); } 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 *sp, int idx) { unsigned long unlocks; unlocks = srcu_readers_unlock_idx(sp, idx); /* * 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 act like the store buffering pattern. * * This smp_mb() also pairs with smp_mb() C to prevent accesses * after the synchronize_srcu() from being executed before the * grace period ends. */ smp_mb(); /* A */ /* * If the locks are the same as the unlocks, then there must have * been no readers on this index at some time in between. This does * not mean that there are no more readers, as one could have read * the current index but not have incremented the lock counter yet. * * So suppose that the updater is preempted here for so long * that more than ULONG_MAX non-nested readers come and go in * the meantime. It turns out that this cannot result in overflow * because if a reader modifies its unlock count after we read it * above, then that reader's next load of ->srcu_idx is guaranteed * to get the new value, which will cause it to operate on the * other bank of counters, where it cannot contribute to the * overflow of these counters. This means that there is a maximum * of 2*NR_CPUS increments, which cannot overflow given current * systems, especially not on 64-bit systems. * * OK, how about nesting? This does impose a limit on nesting * of floor(ULONG_MAX/NR_CPUS/2), which should be sufficient, * especially on 64-bit systems. */ return srcu_readers_lock_idx(sp, idx) == unlocks; } /** * srcu_readers_active - returns true if there are readers. and false * otherwise * @sp: 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 *sp) { int cpu; unsigned long sum = 0; for_each_possible_cpu(cpu) { struct srcu_data *cpuc = per_cpu_ptr(sp->sda, cpu); sum += READ_ONCE(cpuc->srcu_lock_count[0]); sum += READ_ONCE(cpuc->srcu_lock_count[1]); sum -= READ_ONCE(cpuc->srcu_unlock_count[0]); sum -= READ_ONCE(cpuc->srcu_unlock_count[1]); } return sum; } #define SRCU_INTERVAL 1 /* * Return grace-period delay, zero if there are expedited grace * periods pending, SRCU_INTERVAL otherwise. */ static unsigned long srcu_get_delay(struct srcu_struct *sp) { if (ULONG_CMP_LT(READ_ONCE(sp->srcu_gp_seq), READ_ONCE(sp->srcu_gp_seq_needed_exp))) return 0; return SRCU_INTERVAL; } /** * cleanup_srcu_struct - deconstruct a sleep-RCU structure * @sp: 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 *sp) { int cpu; if (WARN_ON(!srcu_get_delay(sp))) return; /* Leakage unless caller handles error. */ if (WARN_ON(srcu_readers_active(sp))) return; /* Leakage unless caller handles error. */ flush_delayed_work(&sp->work); for_each_possible_cpu(cpu) flush_delayed_work(&per_cpu_ptr(sp->sda, cpu)->work); if (WARN_ON(rcu_seq_state(READ_ONCE(sp->srcu_gp_seq)) != SRCU_STATE_IDLE) || WARN_ON(srcu_readers_active(sp))) { pr_info("cleanup_srcu_struct: Active srcu_struct %p state: %d\n", sp, rcu_seq_state(READ_ONCE(sp->srcu_gp_seq))); return; /* Caller forgot to stop doing call_srcu()? */ } free_percpu(sp->sda); sp->sda = NULL; } EXPORT_SYMBOL_GPL(cleanup_srcu_struct); /* * Counts the new reader in the appropriate per-CPU element of the * srcu_struct. * Returns an index that must be passed to the matching srcu_read_unlock(). */ int __srcu_read_lock(struct srcu_struct *sp) { int idx; idx = READ_ONCE(sp->srcu_idx) & 0x1; this_cpu_inc(sp->sda->srcu_lock_count[idx]); smp_mb(); /* B */ /* Avoid leaking the critical section. */ return idx; } 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 *sp, int idx) { smp_mb(); /* C */ /* Avoid leaking the critical section. */ this_cpu_inc(sp->sda->srcu_unlock_count[idx]); } EXPORT_SYMBOL_GPL(__srcu_read_unlock); /* * We use an adaptive strategy for synchronize_srcu() and especially for * synchronize_srcu_expedited(). We spin for a fixed time period * (defined below) to allow SRCU readers to exit their read-side critical * sections. If there are still some readers after a few microseconds, * we repeatedly block for 1-millisecond time periods. */ #define SRCU_RETRY_CHECK_DELAY 5 /* * Start an SRCU grace period. */ static void srcu_gp_start(struct srcu_struct *sp) { struct srcu_data *sdp = this_cpu_ptr(sp->sda); int state; lockdep_assert_held(&sp->lock); WARN_ON_ONCE(ULONG_CMP_GE(sp->srcu_gp_seq, sp->srcu_gp_seq_needed)); rcu_segcblist_advance(&sdp->srcu_cblist, rcu_seq_current(&sp->srcu_gp_seq)); (void)rcu_segcblist_accelerate(&sdp->srcu_cblist, rcu_seq_snap(&sp->srcu_gp_seq)); smp_mb(); /* Order prior store to ->srcu_gp_seq_needed vs. GP start. */ rcu_seq_start(&sp->srcu_gp_seq); state = rcu_seq_state(READ_ONCE(sp->srcu_gp_seq)); WARN_ON_ONCE(state != SRCU_STATE_SCAN1); } /* * Track online CPUs to guide callback workqueue placement. */ DEFINE_PER_CPU(bool, srcu_online); void srcu_online_cpu(unsigned int cpu) { WRITE_ONCE(per_cpu(srcu_online, cpu), true); } void srcu_offline_cpu(unsigned int cpu) { WRITE_ONCE(per_cpu(srcu_online, cpu), false); } /* * Place the workqueue handler on the specified CPU if online, otherwise * just run it whereever. This is useful for placing workqueue handlers * that are to invoke the specified CPU's callbacks. */ static bool srcu_queue_delayed_work_on(int cpu, struct workqueue_struct *wq, struct delayed_work *dwork, unsigned long delay) { bool ret; preempt_disable(); if (READ_ONCE(per_cpu(srcu_online, cpu))) ret = queue_delayed_work_on(cpu, wq, dwork, delay); else ret = queue_delayed_work(wq, dwork, delay); preempt_enable(); return ret; } /* * 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->cpu, system_power_efficient_wq, &sdp->work, 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 *sp, struct srcu_node *snp, unsigned long mask, unsigned long delay) { int cpu; for (cpu = snp->grplo; cpu <= snp->grphi; cpu++) { if (!(mask & (1 << (cpu - snp->grplo)))) continue; srcu_schedule_cbs_sdp(per_cpu_ptr(sp->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 *sp) { unsigned long cbdelay;