Loading...
Note: File does not exist in v4.6.
1// SPDX-License-Identifier: GPL-2.0+
2/*
3 * Sleepable Read-Copy Update mechanism for mutual exclusion.
4 *
5 * Copyright (C) IBM Corporation, 2006
6 * Copyright (C) Fujitsu, 2012
7 *
8 * Authors: Paul McKenney <paulmck@linux.ibm.com>
9 * Lai Jiangshan <laijs@cn.fujitsu.com>
10 *
11 * For detailed explanation of Read-Copy Update mechanism see -
12 * Documentation/RCU/ *.txt
13 *
14 */
15
16#define pr_fmt(fmt) "rcu: " fmt
17
18#include <linux/export.h>
19#include <linux/mutex.h>
20#include <linux/percpu.h>
21#include <linux/preempt.h>
22#include <linux/rcupdate_wait.h>
23#include <linux/sched.h>
24#include <linux/smp.h>
25#include <linux/delay.h>
26#include <linux/module.h>
27#include <linux/slab.h>
28#include <linux/srcu.h>
29
30#include "rcu.h"
31#include "rcu_segcblist.h"
32
33/* Holdoff in nanoseconds for auto-expediting. */
34#define DEFAULT_SRCU_EXP_HOLDOFF (25 * 1000)
35static ulong exp_holdoff = DEFAULT_SRCU_EXP_HOLDOFF;
36module_param(exp_holdoff, ulong, 0444);
37
38/* Overflow-check frequency. N bits roughly says every 2**N grace periods. */
39static ulong counter_wrap_check = (ULONG_MAX >> 2);
40module_param(counter_wrap_check, ulong, 0444);
41
42/*
43 * Control conversion to SRCU_SIZE_BIG:
44 * 0: Don't convert at all.
45 * 1: Convert at init_srcu_struct() time.
46 * 2: Convert when rcutorture invokes srcu_torture_stats_print().
47 * 3: Decide at boot time based on system shape (default).
48 * 0x1x: Convert when excessive contention encountered.
49 */
50#define SRCU_SIZING_NONE 0
51#define SRCU_SIZING_INIT 1
52#define SRCU_SIZING_TORTURE 2
53#define SRCU_SIZING_AUTO 3
54#define SRCU_SIZING_CONTEND 0x10
55#define SRCU_SIZING_IS(x) ((convert_to_big & ~SRCU_SIZING_CONTEND) == x)
56#define SRCU_SIZING_IS_NONE() (SRCU_SIZING_IS(SRCU_SIZING_NONE))
57#define SRCU_SIZING_IS_INIT() (SRCU_SIZING_IS(SRCU_SIZING_INIT))
58#define SRCU_SIZING_IS_TORTURE() (SRCU_SIZING_IS(SRCU_SIZING_TORTURE))
59#define SRCU_SIZING_IS_CONTEND() (convert_to_big & SRCU_SIZING_CONTEND)
60static int convert_to_big = SRCU_SIZING_AUTO;
61module_param(convert_to_big, int, 0444);
62
63/* Number of CPUs to trigger init_srcu_struct()-time transition to big. */
64static int big_cpu_lim __read_mostly = 128;
65module_param(big_cpu_lim, int, 0444);
66
67/* Contention events per jiffy to initiate transition to big. */
68static int small_contention_lim __read_mostly = 100;
69module_param(small_contention_lim, int, 0444);
70
71/* Early-boot callback-management, so early that no lock is required! */
72static LIST_HEAD(srcu_boot_list);
73static bool __read_mostly srcu_init_done;
74
75static void srcu_invoke_callbacks(struct work_struct *work);
76static void srcu_reschedule(struct srcu_struct *ssp, unsigned long delay);
77static void process_srcu(struct work_struct *work);
78static void srcu_delay_timer(struct timer_list *t);
79
80/* Wrappers for lock acquisition and release, see raw_spin_lock_rcu_node(). */
81#define spin_lock_rcu_node(p) \
82do { \
83 spin_lock(&ACCESS_PRIVATE(p, lock)); \
84 smp_mb__after_unlock_lock(); \
85} while (0)
86
87#define spin_unlock_rcu_node(p) spin_unlock(&ACCESS_PRIVATE(p, lock))
88
89#define spin_lock_irq_rcu_node(p) \
90do { \
91 spin_lock_irq(&ACCESS_PRIVATE(p, lock)); \
92 smp_mb__after_unlock_lock(); \
93} while (0)
94
95#define spin_unlock_irq_rcu_node(p) \
96 spin_unlock_irq(&ACCESS_PRIVATE(p, lock))
97
98#define spin_lock_irqsave_rcu_node(p, flags) \
99do { \
100 spin_lock_irqsave(&ACCESS_PRIVATE(p, lock), flags); \
101 smp_mb__after_unlock_lock(); \
102} while (0)
103
104#define spin_trylock_irqsave_rcu_node(p, flags) \
105({ \
106 bool ___locked = spin_trylock_irqsave(&ACCESS_PRIVATE(p, lock), flags); \
107 \
108 if (___locked) \
109 smp_mb__after_unlock_lock(); \
110 ___locked; \
111})
112
113#define spin_unlock_irqrestore_rcu_node(p, flags) \
114 spin_unlock_irqrestore(&ACCESS_PRIVATE(p, lock), flags) \
115
116/*
117 * Initialize SRCU per-CPU data. Note that statically allocated
118 * srcu_struct structures might already have srcu_read_lock() and
119 * srcu_read_unlock() running against them. So if the is_static parameter
120 * is set, don't initialize ->srcu_lock_count[] and ->srcu_unlock_count[].
121 */
122static void init_srcu_struct_data(struct srcu_struct *ssp)
123{
124 int cpu;
125 struct srcu_data *sdp;
126
127 /*
128 * Initialize the per-CPU srcu_data array, which feeds into the
129 * leaves of the srcu_node tree.
130 */
131 WARN_ON_ONCE(ARRAY_SIZE(sdp->srcu_lock_count) !=
132 ARRAY_SIZE(sdp->srcu_unlock_count));
133 for_each_possible_cpu(cpu) {
134 sdp = per_cpu_ptr(ssp->sda, cpu);
135 spin_lock_init(&ACCESS_PRIVATE(sdp, lock));
136 rcu_segcblist_init(&sdp->srcu_cblist);
137 sdp->srcu_cblist_invoking = false;
138 sdp->srcu_gp_seq_needed = ssp->srcu_sup->srcu_gp_seq;
139 sdp->srcu_gp_seq_needed_exp = ssp->srcu_sup->srcu_gp_seq;
140 sdp->mynode = NULL;
141 sdp->cpu = cpu;
142 INIT_WORK(&sdp->work, srcu_invoke_callbacks);
143 timer_setup(&sdp->delay_work, srcu_delay_timer, 0);
144 sdp->ssp = ssp;
145 }
146}
147
148/* Invalid seq state, used during snp node initialization */
149#define SRCU_SNP_INIT_SEQ 0x2
150
151/*
152 * Check whether sequence number corresponding to snp node,
153 * is invalid.
154 */
155static inline bool srcu_invl_snp_seq(unsigned long s)
156{
157 return s == SRCU_SNP_INIT_SEQ;
158}
159
160/*
161 * Allocated and initialize SRCU combining tree. Returns @true if
162 * allocation succeeded and @false otherwise.
163 */
164static bool init_srcu_struct_nodes(struct srcu_struct *ssp, gfp_t gfp_flags)
165{
166 int cpu;
167 int i;
168 int level = 0;
169 int levelspread[RCU_NUM_LVLS];
170 struct srcu_data *sdp;
171 struct srcu_node *snp;
172 struct srcu_node *snp_first;
173
174 /* Initialize geometry if it has not already been initialized. */
175 rcu_init_geometry();
176 ssp->srcu_sup->node = kcalloc(rcu_num_nodes, sizeof(*ssp->srcu_sup->node), gfp_flags);
177 if (!ssp->srcu_sup->node)
178 return false;
179
180 /* Work out the overall tree geometry. */
181 ssp->srcu_sup->level[0] = &ssp->srcu_sup->node[0];
182 for (i = 1; i < rcu_num_lvls; i++)
183 ssp->srcu_sup->level[i] = ssp->srcu_sup->level[i - 1] + num_rcu_lvl[i - 1];
184 rcu_init_levelspread(levelspread, num_rcu_lvl);
185
186 /* Each pass through this loop initializes one srcu_node structure. */
187 srcu_for_each_node_breadth_first(ssp, snp) {
188 spin_lock_init(&ACCESS_PRIVATE(snp, lock));
189 WARN_ON_ONCE(ARRAY_SIZE(snp->srcu_have_cbs) !=
190 ARRAY_SIZE(snp->srcu_data_have_cbs));
191 for (i = 0; i < ARRAY_SIZE(snp->srcu_have_cbs); i++) {
192 snp->srcu_have_cbs[i] = SRCU_SNP_INIT_SEQ;
193 snp->srcu_data_have_cbs[i] = 0;
194 }
195 snp->srcu_gp_seq_needed_exp = SRCU_SNP_INIT_SEQ;
196 snp->grplo = -1;
197 snp->grphi = -1;
198 if (snp == &ssp->srcu_sup->node[0]) {
199 /* Root node, special case. */
200 snp->srcu_parent = NULL;
201 continue;
202 }
203
204 /* Non-root node. */
205 if (snp == ssp->srcu_sup->level[level + 1])
206 level++;
207 snp->srcu_parent = ssp->srcu_sup->level[level - 1] +
208 (snp - ssp->srcu_sup->level[level]) /
209 levelspread[level - 1];
210 }
211
212 /*
213 * Initialize the per-CPU srcu_data array, which feeds into the
214 * leaves of the srcu_node tree.
215 */
216 level = rcu_num_lvls - 1;
217 snp_first = ssp->srcu_sup->level[level];
218 for_each_possible_cpu(cpu) {
219 sdp = per_cpu_ptr(ssp->sda, cpu);
220 sdp->mynode = &snp_first[cpu / levelspread[level]];
221 for (snp = sdp->mynode; snp != NULL; snp = snp->srcu_parent) {
222 if (snp->grplo < 0)
223 snp->grplo = cpu;
224 snp->grphi = cpu;
225 }
226 sdp->grpmask = 1UL << (cpu - sdp->mynode->grplo);
227 }
228 smp_store_release(&ssp->srcu_sup->srcu_size_state, SRCU_SIZE_WAIT_BARRIER);
229 return true;
230}
231
232/*
233 * Initialize non-compile-time initialized fields, including the
234 * associated srcu_node and srcu_data structures. The is_static parameter
235 * tells us that ->sda has already been wired up to srcu_data.
236 */
237static int init_srcu_struct_fields(struct srcu_struct *ssp, bool is_static)
238{
239 if (!is_static)
240 ssp->srcu_sup = kzalloc(sizeof(*ssp->srcu_sup), GFP_KERNEL);
241 if (!ssp->srcu_sup)
242 return -ENOMEM;
243 if (!is_static)
244 spin_lock_init(&ACCESS_PRIVATE(ssp->srcu_sup, lock));
245 ssp->srcu_sup->srcu_size_state = SRCU_SIZE_SMALL;
246 ssp->srcu_sup->node = NULL;
247 mutex_init(&ssp->srcu_sup->srcu_cb_mutex);
248 mutex_init(&ssp->srcu_sup->srcu_gp_mutex);
249 ssp->srcu_idx = 0;
250 ssp->srcu_sup->srcu_gp_seq = 0;
251 ssp->srcu_sup->srcu_barrier_seq = 0;
252 mutex_init(&ssp->srcu_sup->srcu_barrier_mutex);
253 atomic_set(&ssp->srcu_sup->srcu_barrier_cpu_cnt, 0);
254 INIT_DELAYED_WORK(&ssp->srcu_sup->work, process_srcu);
255 ssp->srcu_sup->sda_is_static = is_static;
256 if (!is_static)
257 ssp->sda = alloc_percpu(struct srcu_data);
258 if (!ssp->sda)
259 goto err_free_sup;
260 init_srcu_struct_data(ssp);
261 ssp->srcu_sup->srcu_gp_seq_needed_exp = 0;
262 ssp->srcu_sup->srcu_last_gp_end = ktime_get_mono_fast_ns();
263 if (READ_ONCE(ssp->srcu_sup->srcu_size_state) == SRCU_SIZE_SMALL && SRCU_SIZING_IS_INIT()) {
264 if (!init_srcu_struct_nodes(ssp, GFP_ATOMIC))
265 goto err_free_sda;
266 WRITE_ONCE(ssp->srcu_sup->srcu_size_state, SRCU_SIZE_BIG);
267 }
268 ssp->srcu_sup->srcu_ssp = ssp;
269 smp_store_release(&ssp->srcu_sup->srcu_gp_seq_needed, 0); /* Init done. */
270 return 0;
271
272err_free_sda:
273 if (!is_static) {
274 free_percpu(ssp->sda);
275 ssp->sda = NULL;
276 }
277err_free_sup:
278 if (!is_static) {
279 kfree(ssp->srcu_sup);
280 ssp->srcu_sup = NULL;
281 }
282 return -ENOMEM;
283}
284
285#ifdef CONFIG_DEBUG_LOCK_ALLOC
286
287int __init_srcu_struct(struct srcu_struct *ssp, const char *name,
288 struct lock_class_key *key)
289{
290 /* Don't re-initialize a lock while it is held. */
291 debug_check_no_locks_freed((void *)ssp, sizeof(*ssp));
292 lockdep_init_map(&ssp->dep_map, name, key, 0);
293 return init_srcu_struct_fields(ssp, false);
294}
295EXPORT_SYMBOL_GPL(__init_srcu_struct);
296
297#else /* #ifdef CONFIG_DEBUG_LOCK_ALLOC */
298
299/**
300 * init_srcu_struct - initialize a sleep-RCU structure
301 * @ssp: structure to initialize.
302 *
303 * Must invoke this on a given srcu_struct before passing that srcu_struct
304 * to any other function. Each srcu_struct represents a separate domain
305 * of SRCU protection.
306 */
307int init_srcu_struct(struct srcu_struct *ssp)
308{
309 return init_srcu_struct_fields(ssp, false);
310}
311EXPORT_SYMBOL_GPL(init_srcu_struct);
312
313#endif /* #else #ifdef CONFIG_DEBUG_LOCK_ALLOC */
314
315/*
316 * Initiate a transition to SRCU_SIZE_BIG with lock held.
317 */
318static void __srcu_transition_to_big(struct srcu_struct *ssp)
319{
320 lockdep_assert_held(&ACCESS_PRIVATE(ssp->srcu_sup, lock));
321 smp_store_release(&ssp->srcu_sup->srcu_size_state, SRCU_SIZE_ALLOC);
322}
323
324/*
325 * Initiate an idempotent transition to SRCU_SIZE_BIG.
326 */
327static void srcu_transition_to_big(struct srcu_struct *ssp)
328{
329 unsigned long flags;
330
331 /* Double-checked locking on ->srcu_size-state. */
332 if (smp_load_acquire(&ssp->srcu_sup->srcu_size_state) != SRCU_SIZE_SMALL)
333 return;
334 spin_lock_irqsave_rcu_node(ssp->srcu_sup, flags);
335 if (smp_load_acquire(&ssp->srcu_sup->srcu_size_state) != SRCU_SIZE_SMALL) {
336 spin_unlock_irqrestore_rcu_node(ssp->srcu_sup, flags);
337 return;
338 }
339 __srcu_transition_to_big(ssp);
340 spin_unlock_irqrestore_rcu_node(ssp->srcu_sup, flags);
341}
342
343/*
344 * Check to see if the just-encountered contention event justifies
345 * a transition to SRCU_SIZE_BIG.
346 */
347static void spin_lock_irqsave_check_contention(struct srcu_struct *ssp)
348{
349 unsigned long j;
350
351 if (!SRCU_SIZING_IS_CONTEND() || ssp->srcu_sup->srcu_size_state)
352 return;
353 j = jiffies;
354 if (ssp->srcu_sup->srcu_size_jiffies != j) {
355 ssp->srcu_sup->srcu_size_jiffies = j;
356 ssp->srcu_sup->srcu_n_lock_retries = 0;
357 }
358 if (++ssp->srcu_sup->srcu_n_lock_retries <= small_contention_lim)
359 return;
360 __srcu_transition_to_big(ssp);
361}
362
363/*
364 * Acquire the specified srcu_data structure's ->lock, but check for
365 * excessive contention, which results in initiation of a transition
366 * to SRCU_SIZE_BIG. But only if the srcutree.convert_to_big module
367 * parameter permits this.
368 */
369static void spin_lock_irqsave_sdp_contention(struct srcu_data *sdp, unsigned long *flags)
370{
371 struct srcu_struct *ssp = sdp->ssp;
372
373 if (spin_trylock_irqsave_rcu_node(sdp, *flags))
374 return;
375 spin_lock_irqsave_rcu_node(ssp->srcu_sup, *flags);
376 spin_lock_irqsave_check_contention(ssp);
377 spin_unlock_irqrestore_rcu_node(ssp->srcu_sup, *flags);
378 spin_lock_irqsave_rcu_node(sdp, *flags);
379}
380
381/*
382 * Acquire the specified srcu_struct structure's ->lock, but check for
383 * excessive contention, which results in initiation of a transition
384 * to SRCU_SIZE_BIG. But only if the srcutree.convert_to_big module
385 * parameter permits this.
386 */
387static void spin_lock_irqsave_ssp_contention(struct srcu_struct *ssp, unsigned long *flags)
388{
389 if (spin_trylock_irqsave_rcu_node(ssp->srcu_sup, *flags))
390 return;
391 spin_lock_irqsave_rcu_node(ssp->srcu_sup, *flags);
392 spin_lock_irqsave_check_contention(ssp);
393}
394
395/*
396 * First-use initialization of statically allocated srcu_struct
397 * structure. Wiring up the combining tree is more than can be
398 * done with compile-time initialization, so this check is added
399 * to each update-side SRCU primitive. Use ssp->lock, which -is-
400 * compile-time initialized, to resolve races involving multiple
401 * CPUs trying to garner first-use privileges.
402 */
403static void check_init_srcu_struct(struct srcu_struct *ssp)
404{
405 unsigned long flags;
406
407 /* The smp_load_acquire() pairs with the smp_store_release(). */
408 if (!rcu_seq_state(smp_load_acquire(&ssp->srcu_sup->srcu_gp_seq_needed))) /*^^^*/
409 return; /* Already initialized. */
410 spin_lock_irqsave_rcu_node(ssp->srcu_sup, flags);
411 if (!rcu_seq_state(ssp->srcu_sup->srcu_gp_seq_needed)) {
412 spin_unlock_irqrestore_rcu_node(ssp->srcu_sup, flags);
413 return;
414 }
415 init_srcu_struct_fields(ssp, true);
416 spin_unlock_irqrestore_rcu_node(ssp->srcu_sup, flags);
417}
418
419/*
420 * Returns approximate total of the readers' ->srcu_lock_count[] values
421 * for the rank of per-CPU counters specified by idx.
422 */
423static unsigned long srcu_readers_lock_idx(struct srcu_struct *ssp, int idx)
424{
425 int cpu;
426 unsigned long sum = 0;
427
428 for_each_possible_cpu(cpu) {
429 struct srcu_data *cpuc = per_cpu_ptr(ssp->sda, cpu);
430
431 sum += atomic_long_read(&cpuc->srcu_lock_count[idx]);
432 }
433 return sum;
434}
435
436/*
437 * Returns approximate total of the readers' ->srcu_unlock_count[] values
438 * for the rank of per-CPU counters specified by idx.
439 */
440static unsigned long srcu_readers_unlock_idx(struct srcu_struct *ssp, int idx)
441{
442 int cpu;
443 unsigned long mask = 0;
444 unsigned long sum = 0;
445
446 for_each_possible_cpu(cpu) {
447 struct srcu_data *cpuc = per_cpu_ptr(ssp->sda, cpu);
448
449 sum += atomic_long_read(&cpuc->srcu_unlock_count[idx]);
450 if (IS_ENABLED(CONFIG_PROVE_RCU))
451 mask = mask | READ_ONCE(cpuc->srcu_nmi_safety);
452 }
453 WARN_ONCE(IS_ENABLED(CONFIG_PROVE_RCU) && (mask & (mask >> 1)),
454 "Mixed NMI-safe readers for srcu_struct at %ps.\n", ssp);
455 return sum;
456}
457
458/*
459 * Return true if the number of pre-existing readers is determined to
460 * be zero.
461 */
462static bool srcu_readers_active_idx_check(struct srcu_struct *ssp, int idx)
463{
464 unsigned long unlocks;
465
466 unlocks = srcu_readers_unlock_idx(ssp, idx);
467
468 /*
469 * Make sure that a lock is always counted if the corresponding
470 * unlock is counted. Needs to be a smp_mb() as the read side may
471 * contain a read from a variable that is written to before the
472 * synchronize_srcu() in the write side. In this case smp_mb()s
473 * A and B act like the store buffering pattern.
474 *
475 * This smp_mb() also pairs with smp_mb() C to prevent accesses
476 * after the synchronize_srcu() from being executed before the
477 * grace period ends.
478 */
479 smp_mb(); /* A */
480
481 /*
482 * If the locks are the same as the unlocks, then there must have
483 * been no readers on this index at some point in this function.
484 * But there might be more readers, as a task might have read
485 * the current ->srcu_idx but not yet have incremented its CPU's
486 * ->srcu_lock_count[idx] counter. In fact, it is possible
487 * that most of the tasks have been preempted between fetching
488 * ->srcu_idx and incrementing ->srcu_lock_count[idx]. And there
489 * could be almost (ULONG_MAX / sizeof(struct task_struct)) tasks
490 * in a system whose address space was fully populated with memory.
491 * Call this quantity Nt.
492 *
493 * So suppose that the updater is preempted at this point in the
494 * code for a long time. That now-preempted updater has already
495 * flipped ->srcu_idx (possibly during the preceding grace period),
496 * done an smp_mb() (again, possibly during the preceding grace
497 * period), and summed up the ->srcu_unlock_count[idx] counters.
498 * How many times can a given one of the aforementioned Nt tasks
499 * increment the old ->srcu_idx value's ->srcu_lock_count[idx]
500 * counter, in the absence of nesting?
501 *
502 * It can clearly do so once, given that it has already fetched
503 * the old value of ->srcu_idx and is just about to use that value
504 * to index its increment of ->srcu_lock_count[idx]. But as soon as
505 * it leaves that SRCU read-side critical section, it will increment
506 * ->srcu_unlock_count[idx], which must follow the updater's above
507 * read from that same value. Thus, as soon the reading task does
508 * an smp_mb() and a later fetch from ->srcu_idx, that task will be
509 * guaranteed to get the new index. Except that the increment of
510 * ->srcu_unlock_count[idx] in __srcu_read_unlock() is after the
511 * smp_mb(), and the fetch from ->srcu_idx in __srcu_read_lock()
512 * is before the smp_mb(). Thus, that task might not see the new
513 * value of ->srcu_idx until the -second- __srcu_read_lock(),
514 * which in turn means that this task might well increment
515 * ->srcu_lock_count[idx] for the old value of ->srcu_idx twice,
516 * not just once.
517 *
518 * However, it is important to note that a given smp_mb() takes
519 * effect not just for the task executing it, but also for any
520 * later task running on that same CPU.
521 *
522 * That is, there can be almost Nt + Nc further increments of
523 * ->srcu_lock_count[idx] for the old index, where Nc is the number
524 * of CPUs. But this is OK because the size of the task_struct
525 * structure limits the value of Nt and current systems limit Nc
526 * to a few thousand.
527 *
528 * OK, but what about nesting? This does impose a limit on
529 * nesting of half of the size of the task_struct structure
530 * (measured in bytes), which should be sufficient. A late 2022
531 * TREE01 rcutorture run reported this size to be no less than
532 * 9408 bytes, allowing up to 4704 levels of nesting, which is
533 * comfortably beyond excessive. Especially on 64-bit systems,
534 * which are unlikely to be configured with an address space fully
535 * populated with memory, at least not anytime soon.
536 */
537 return srcu_readers_lock_idx(ssp, idx) == unlocks;
538}
539
540/**
541 * srcu_readers_active - returns true if there are readers. and false
542 * otherwise
543 * @ssp: which srcu_struct to count active readers (holding srcu_read_lock).
544 *
545 * Note that this is not an atomic primitive, and can therefore suffer
546 * severe errors when invoked on an active srcu_struct. That said, it
547 * can be useful as an error check at cleanup time.
548 */
549static bool srcu_readers_active(struct srcu_struct *ssp)
550{
551 int cpu;
552 unsigned long sum = 0;
553
554 for_each_possible_cpu(cpu) {
555 struct srcu_data *cpuc = per_cpu_ptr(ssp->sda, cpu);
556
557 sum += atomic_long_read(&cpuc->srcu_lock_count[0]);
558 sum += atomic_long_read(&cpuc->srcu_lock_count[1]);
559 sum -= atomic_long_read(&cpuc->srcu_unlock_count[0]);
560 sum -= atomic_long_read(&cpuc->srcu_unlock_count[1]);
561 }
562 return sum;
563}
564
565/*
566 * We use an adaptive strategy for synchronize_srcu() and especially for
567 * synchronize_srcu_expedited(). We spin for a fixed time period
568 * (defined below, boot time configurable) to allow SRCU readers to exit
569 * their read-side critical sections. If there are still some readers
570 * after one jiffy, we repeatedly block for one jiffy time periods.
571 * The blocking time is increased as the grace-period age increases,
572 * with max blocking time capped at 10 jiffies.
573 */
574#define SRCU_DEFAULT_RETRY_CHECK_DELAY 5
575
576static ulong srcu_retry_check_delay = SRCU_DEFAULT_RETRY_CHECK_DELAY;
577module_param(srcu_retry_check_delay, ulong, 0444);
578
579#define SRCU_INTERVAL 1 // Base delay if no expedited GPs pending.
580#define SRCU_MAX_INTERVAL 10 // Maximum incremental delay from slow readers.
581
582#define SRCU_DEFAULT_MAX_NODELAY_PHASE_LO 3UL // Lowmark on default per-GP-phase
583 // no-delay instances.
584#define SRCU_DEFAULT_MAX_NODELAY_PHASE_HI 1000UL // Highmark on default per-GP-phase
585 // no-delay instances.
586
587#define SRCU_UL_CLAMP_LO(val, low) ((val) > (low) ? (val) : (low))
588#define SRCU_UL_CLAMP_HI(val, high) ((val) < (high) ? (val) : (high))
589#define SRCU_UL_CLAMP(val, low, high) SRCU_UL_CLAMP_HI(SRCU_UL_CLAMP_LO((val), (low)), (high))
590// per-GP-phase no-delay instances adjusted to allow non-sleeping poll upto
591// one jiffies time duration. Mult by 2 is done to factor in the srcu_get_delay()
592// called from process_srcu().
593#define SRCU_DEFAULT_MAX_NODELAY_PHASE_ADJUSTED \
594 (2UL * USEC_PER_SEC / HZ / SRCU_DEFAULT_RETRY_CHECK_DELAY)
595
596// Maximum per-GP-phase consecutive no-delay instances.
597#define SRCU_DEFAULT_MAX_NODELAY_PHASE \
598 SRCU_UL_CLAMP(SRCU_DEFAULT_MAX_NODELAY_PHASE_ADJUSTED, \
599 SRCU_DEFAULT_MAX_NODELAY_PHASE_LO, \
600 SRCU_DEFAULT_MAX_NODELAY_PHASE_HI)
601
602static ulong srcu_max_nodelay_phase = SRCU_DEFAULT_MAX_NODELAY_PHASE;
603module_param(srcu_max_nodelay_phase, ulong, 0444);
604
605// Maximum consecutive no-delay instances.
606#define SRCU_DEFAULT_MAX_NODELAY (SRCU_DEFAULT_MAX_NODELAY_PHASE > 100 ? \
607 SRCU_DEFAULT_MAX_NODELAY_PHASE : 100)
608
609static ulong srcu_max_nodelay = SRCU_DEFAULT_MAX_NODELAY;
610module_param(srcu_max_nodelay, ulong, 0444);
611
612/*
613 * Return grace-period delay, zero if there are expedited grace
614 * periods pending, SRCU_INTERVAL otherwise.
615 */
616static unsigned long srcu_get_delay(struct srcu_struct *ssp)
617{
618 unsigned long gpstart;
619 unsigned long j;
620 unsigned long jbase = SRCU_INTERVAL;
621 struct srcu_usage *sup = ssp->srcu_sup;
622
623 if (ULONG_CMP_LT(READ_ONCE(sup->srcu_gp_seq), READ_ONCE(sup->srcu_gp_seq_needed_exp)))
624 jbase = 0;
625 if (rcu_seq_state(READ_ONCE(sup->srcu_gp_seq))) {
626 j = jiffies - 1;
627 gpstart = READ_ONCE(sup->srcu_gp_start);
628 if (time_after(j, gpstart))
629 jbase += j - gpstart;
630 if (!jbase) {
631 WRITE_ONCE(sup->srcu_n_exp_nodelay, READ_ONCE(sup->srcu_n_exp_nodelay) + 1);
632 if (READ_ONCE(sup->srcu_n_exp_nodelay) > srcu_max_nodelay_phase)
633 jbase = 1;
634 }
635 }
636 return jbase > SRCU_MAX_INTERVAL ? SRCU_MAX_INTERVAL : jbase;
637}
638
639/**
640 * cleanup_srcu_struct - deconstruct a sleep-RCU structure
641 * @ssp: structure to clean up.
642 *
643 * Must invoke this after you are finished using a given srcu_struct that
644 * was initialized via init_srcu_struct(), else you leak memory.
645 */
646void cleanup_srcu_struct(struct srcu_struct *ssp)
647{
648 int cpu;
649 struct srcu_usage *sup = ssp->srcu_sup;
650
651 if (WARN_ON(!srcu_get_delay(ssp)))
652 return; /* Just leak it! */
653 if (WARN_ON(srcu_readers_active(ssp)))
654 return; /* Just leak it! */
655 flush_delayed_work(&sup->work);
656 for_each_possible_cpu(cpu) {
657 struct srcu_data *sdp = per_cpu_ptr(ssp->sda, cpu);
658
659 del_timer_sync(&sdp->delay_work);
660 flush_work(&sdp->work);
661 if (WARN_ON(rcu_segcblist_n_cbs(&sdp->srcu_cblist)))
662 return; /* Forgot srcu_barrier(), so just leak it! */
663 }
664 if (WARN_ON(rcu_seq_state(READ_ONCE(sup->srcu_gp_seq)) != SRCU_STATE_IDLE) ||
665 WARN_ON(rcu_seq_current(&sup->srcu_gp_seq) != sup->srcu_gp_seq_needed) ||
666 WARN_ON(srcu_readers_active(ssp))) {
667 pr_info("%s: Active srcu_struct %p read state: %d gp state: %lu/%lu\n",
668 __func__, ssp, rcu_seq_state(READ_ONCE(sup->srcu_gp_seq)),
669 rcu_seq_current(&sup->srcu_gp_seq), sup->srcu_gp_seq_needed);
670 return; /* Caller forgot to stop doing call_srcu()? */
671 }
672 kfree(sup->node);
673 sup->node = NULL;
674 sup->srcu_size_state = SRCU_SIZE_SMALL;
675 if (!sup->sda_is_static) {
676 free_percpu(ssp->sda);
677 ssp->sda = NULL;
678 kfree(sup);
679 ssp->srcu_sup = NULL;
680 }
681}
682EXPORT_SYMBOL_GPL(cleanup_srcu_struct);
683
684#ifdef CONFIG_PROVE_RCU
685/*
686 * Check for consistent NMI safety.
687 */
688void srcu_check_nmi_safety(struct srcu_struct *ssp, bool nmi_safe)
689{
690 int nmi_safe_mask = 1 << nmi_safe;
691 int old_nmi_safe_mask;
692 struct srcu_data *sdp;
693
694 /* NMI-unsafe use in NMI is a bad sign */
695 WARN_ON_ONCE(!nmi_safe && in_nmi());
696 sdp = raw_cpu_ptr(ssp->sda);
697 old_nmi_safe_mask = READ_ONCE(sdp->srcu_nmi_safety);
698 if (!old_nmi_safe_mask) {
699 WRITE_ONCE(sdp->srcu_nmi_safety, nmi_safe_mask);
700 return;
701 }
702 WARN_ONCE(old_nmi_safe_mask != nmi_safe_mask, "CPU %d old state %d new state %d\n", sdp->cpu, old_nmi_safe_mask, nmi_safe_mask);
703}
704EXPORT_SYMBOL_GPL(srcu_check_nmi_safety);
705#endif /* CONFIG_PROVE_RCU */
706
707/*
708 * Counts the new reader in the appropriate per-CPU element of the
709 * srcu_struct.
710 * Returns an index that must be passed to the matching srcu_read_unlock().
711 */
712int __srcu_read_lock(struct srcu_struct *ssp)
713{
714 int idx;
715
716 idx = READ_ONCE(ssp->srcu_idx) & 0x1;
717 this_cpu_inc(ssp->sda->srcu_lock_count[idx].counter);
718 smp_mb(); /* B */ /* Avoid leaking the critical section. */
719 return idx;
720}
721EXPORT_SYMBOL_GPL(__srcu_read_lock);
722
723/*
724 * Removes the count for the old reader from the appropriate per-CPU
725 * element of the srcu_struct. Note that this may well be a different
726 * CPU than that which was incremented by the corresponding srcu_read_lock().
727 */
728void __srcu_read_unlock(struct srcu_struct *ssp, int idx)
729{
730 smp_mb(); /* C */ /* Avoid leaking the critical section. */
731 this_cpu_inc(ssp->sda->srcu_unlock_count[idx].counter);
732}
733EXPORT_SYMBOL_GPL(__srcu_read_unlock);
734
735#ifdef CONFIG_NEED_SRCU_NMI_SAFE
736
737/*
738 * Counts the new reader in the appropriate per-CPU element of the
739 * srcu_struct, but in an NMI-safe manner using RMW atomics.
740 * Returns an index that must be passed to the matching srcu_read_unlock().
741 */
742int __srcu_read_lock_nmisafe(struct srcu_struct *ssp)
743{
744 int idx;
745 struct srcu_data *sdp = raw_cpu_ptr(ssp->sda);
746
747 idx = READ_ONCE(ssp->srcu_idx) & 0x1;
748 atomic_long_inc(&sdp->srcu_lock_count[idx]);
749 smp_mb__after_atomic(); /* B */ /* Avoid leaking the critical section. */
750 return idx;
751}
752EXPORT_SYMBOL_GPL(__srcu_read_lock_nmisafe);
753
754/*
755 * Removes the count for the old reader from the appropriate per-CPU
756 * element of the srcu_struct. Note that this may well be a different
757 * CPU than that which was incremented by the corresponding srcu_read_lock().
758 */
759void __srcu_read_unlock_nmisafe(struct srcu_struct *ssp, int idx)
760{
761 struct srcu_data *sdp = raw_cpu_ptr(ssp->sda);
762
763 smp_mb__before_atomic(); /* C */ /* Avoid leaking the critical section. */
764 atomic_long_inc(&sdp->srcu_unlock_count[idx]);
765}
766EXPORT_SYMBOL_GPL(__srcu_read_unlock_nmisafe);
767
768#endif // CONFIG_NEED_SRCU_NMI_SAFE
769
770/*
771 * Start an SRCU grace period.
772 */
773static void srcu_gp_start(struct srcu_struct *ssp)
774{
775 int state;
776
777 lockdep_assert_held(&ACCESS_PRIVATE(ssp->srcu_sup, lock));
778 WARN_ON_ONCE(ULONG_CMP_GE(ssp->srcu_sup->srcu_gp_seq, ssp->srcu_sup->srcu_gp_seq_needed));
779 WRITE_ONCE(ssp->srcu_sup->srcu_gp_start, jiffies);
780 WRITE_ONCE(ssp->srcu_sup->srcu_n_exp_nodelay, 0);
781 smp_mb(); /* Order prior store to ->srcu_gp_seq_needed vs. GP start. */
782 rcu_seq_start(&ssp->srcu_sup->srcu_gp_seq);
783 state = rcu_seq_state(ssp->srcu_sup->srcu_gp_seq);
784 WARN_ON_ONCE(state != SRCU_STATE_SCAN1);
785}
786
787
788static void srcu_delay_timer(struct timer_list *t)
789{
790 struct srcu_data *sdp = container_of(t, struct srcu_data, delay_work);
791
792 queue_work_on(sdp->cpu, rcu_gp_wq, &sdp->work);
793}
794
795static void srcu_queue_delayed_work_on(struct srcu_data *sdp,
796 unsigned long delay)
797{
798 if (!delay) {
799 queue_work_on(sdp->cpu, rcu_gp_wq, &sdp->work);
800 return;
801 }
802
803 timer_reduce(&sdp->delay_work, jiffies + delay);
804}
805
806/*
807 * Schedule callback invocation for the specified srcu_data structure,
808 * if possible, on the corresponding CPU.
809 */
810static void srcu_schedule_cbs_sdp(struct srcu_data *sdp, unsigned long delay)
811{
812 srcu_queue_delayed_work_on(sdp, delay);
813}
814
815/*
816 * Schedule callback invocation for all srcu_data structures associated
817 * with the specified srcu_node structure that have callbacks for the
818 * just-completed grace period, the one corresponding to idx. If possible,
819 * schedule this invocation on the corresponding CPUs.
820 */
821static void srcu_schedule_cbs_snp(struct srcu_struct *ssp, struct srcu_node *snp,
822 unsigned long mask, unsigned long delay)
823{
824 int cpu;
825
826 for (cpu = snp->grplo; cpu <= snp->grphi; cpu++) {
827 if (!(mask & (1UL << (cpu - snp->grplo))))
828 continue;
829 srcu_schedule_cbs_sdp(per_cpu_ptr(ssp->sda, cpu), delay);
830 }
831}
832
833/*
834 * Note the end of an SRCU grace period. Initiates callback invocation
835 * and starts a new grace period if needed.
836 *
837 * The ->srcu_cb_mutex acquisition does not protect any data, but
838 * instead prevents more than one grace period from starting while we
839 * are initiating callback invocation. This allows the ->srcu_have_cbs[]
840 * array to have a finite number of elements.
841 */
842static void srcu_gp_end(struct srcu_struct *ssp)
843{
844 unsigned long cbdelay = 1;
845 bool cbs;
846 bool last_lvl;
847 int cpu;
848 unsigned long flags;
849 unsigned long gpseq;
850 int idx;
851 unsigned long mask;
852 struct srcu_data *sdp;
853 unsigned long sgsne;
854 struct srcu_node *snp;
855 int ss_state;
856 struct srcu_usage *sup = ssp->srcu_sup;
857
858 /* Prevent more than one additional grace period. */
859 mutex_lock(&sup->srcu_cb_mutex);
860
861 /* End the current grace period. */
862 spin_lock_irq_rcu_node(sup);
863 idx = rcu_seq_state(sup->srcu_gp_seq);
864 WARN_ON_ONCE(idx != SRCU_STATE_SCAN2);
865 if (ULONG_CMP_LT(READ_ONCE(sup->srcu_gp_seq), READ_ONCE(sup->srcu_gp_seq_needed_exp)))
866 cbdelay = 0;
867
868 WRITE_ONCE(sup->srcu_last_gp_end, ktime_get_mono_fast_ns());
869 rcu_seq_end(&sup->srcu_gp_seq);
870 gpseq = rcu_seq_current(&sup->srcu_gp_seq);
871 if (ULONG_CMP_LT(sup->srcu_gp_seq_needed_exp, gpseq))
872 WRITE_ONCE(sup->srcu_gp_seq_needed_exp, gpseq);
873 spin_unlock_irq_rcu_node(sup);
874 mutex_unlock(&sup->srcu_gp_mutex);
875 /* A new grace period can start at this point. But only one. */
876
877 /* Initiate callback invocation as needed. */
878 ss_state = smp_load_acquire(&sup->srcu_size_state);
879 if (ss_state < SRCU_SIZE_WAIT_BARRIER) {
880 srcu_schedule_cbs_sdp(per_cpu_ptr(ssp->sda, get_boot_cpu_id()),
881 cbdelay);
882 } else {
883 idx = rcu_seq_ctr(gpseq) % ARRAY_SIZE(snp->srcu_have_cbs);
884 srcu_for_each_node_breadth_first(ssp, snp) {
885 spin_lock_irq_rcu_node(snp);
886 cbs = false;
887 last_lvl = snp >= sup->level[rcu_num_lvls - 1];
888 if (last_lvl)
889 cbs = ss_state < SRCU_SIZE_BIG || snp->srcu_have_cbs[idx] == gpseq;
890 snp->srcu_have_cbs[idx] = gpseq;
891 rcu_seq_set_state(&snp->srcu_have_cbs[idx], 1);
892 sgsne = snp->srcu_gp_seq_needed_exp;
893 if (srcu_invl_snp_seq(sgsne) || ULONG_CMP_LT(sgsne, gpseq))
894 WRITE_ONCE(snp->srcu_gp_seq_needed_exp, gpseq);
895 if (ss_state < SRCU_SIZE_BIG)
896 mask = ~0;
897 else
898 mask = snp->srcu_data_have_cbs[idx];
899 snp->srcu_data_have_cbs[idx] = 0;
900 spin_unlock_irq_rcu_node(snp);
901 if (cbs)
902 srcu_schedule_cbs_snp(ssp, snp, mask, cbdelay);
903 }
904 }
905
906 /* Occasionally prevent srcu_data counter wrap. */
907 if (!(gpseq & counter_wrap_check))
908 for_each_possible_cpu(cpu) {
909 sdp = per_cpu_ptr(ssp->sda, cpu);
910 spin_lock_irqsave_rcu_node(sdp, flags);
911 if (ULONG_CMP_GE(gpseq, sdp->srcu_gp_seq_needed + 100))
912 sdp->srcu_gp_seq_needed = gpseq;
913 if (ULONG_CMP_GE(gpseq, sdp->srcu_gp_seq_needed_exp + 100))
914 sdp->srcu_gp_seq_needed_exp = gpseq;
915 spin_unlock_irqrestore_rcu_node(sdp, flags);
916 }
917
918 /* Callback initiation done, allow grace periods after next. */
919 mutex_unlock(&sup->srcu_cb_mutex);
920
921 /* Start a new grace period if needed. */
922 spin_lock_irq_rcu_node(sup);
923 gpseq = rcu_seq_current(&sup->srcu_gp_seq);
924 if (!rcu_seq_state(gpseq) &&
925 ULONG_CMP_LT(gpseq, sup->srcu_gp_seq_needed)) {
926 srcu_gp_start(ssp);
927 spin_unlock_irq_rcu_node(sup);
928 srcu_reschedule(ssp, 0);
929 } else {
930 spin_unlock_irq_rcu_node(sup);
931 }
932
933 /* Transition to big if needed. */
934 if (ss_state != SRCU_SIZE_SMALL && ss_state != SRCU_SIZE_BIG) {
935 if (ss_state == SRCU_SIZE_ALLOC)
936 init_srcu_struct_nodes(ssp, GFP_KERNEL);
937 else
938 smp_store_release(&sup->srcu_size_state, ss_state + 1);
939 }
940}
941
942/*
943 * Funnel-locking scheme to scalably mediate many concurrent expedited
944 * grace-period requests. This function is invoked for the first known
945 * expedited request for a grace period that has already been requested,
946 * but without expediting. To start a completely new grace period,
947 * whether expedited or not, use srcu_funnel_gp_start() instead.
948 */
949static void srcu_funnel_exp_start(struct srcu_struct *ssp, struct srcu_node *snp,
950 unsigned long s)
951{
952 unsigned long flags;
953 unsigned long sgsne;
954
955 if (snp)
956 for (; snp != NULL; snp = snp->srcu_parent) {
957 sgsne = READ_ONCE(snp->srcu_gp_seq_needed_exp);
958 if (WARN_ON_ONCE(rcu_seq_done(&ssp->srcu_sup->srcu_gp_seq, s)) ||
959 (!srcu_invl_snp_seq(sgsne) && ULONG_CMP_GE(sgsne, s)))
960 return;
961 spin_lock_irqsave_rcu_node(snp, flags);
962 sgsne = snp->srcu_gp_seq_needed_exp;
963 if (!srcu_invl_snp_seq(sgsne) && ULONG_CMP_GE(sgsne, s)) {
964 spin_unlock_irqrestore_rcu_node(snp, flags);
965 return;
966 }
967 WRITE_ONCE(snp->srcu_gp_seq_needed_exp, s);
968 spin_unlock_irqrestore_rcu_node(snp, flags);
969 }
970 spin_lock_irqsave_ssp_contention(ssp, &flags);
971 if (ULONG_CMP_LT(ssp->srcu_sup->srcu_gp_seq_needed_exp, s))
972 WRITE_ONCE(ssp->srcu_sup->srcu_gp_seq_needed_exp, s);
973 spin_unlock_irqrestore_rcu_node(ssp->srcu_sup, flags);
974}
975
976/*
977 * Funnel-locking scheme to scalably mediate many concurrent grace-period
978 * requests. The winner has to do the work of actually starting grace
979 * period s. Losers must either ensure that their desired grace-period
980 * number is recorded on at least their leaf srcu_node structure, or they
981 * must take steps to invoke their own callbacks.
982 *
983 * Note that this function also does the work of srcu_funnel_exp_start(),
984 * in some cases by directly invoking it.
985 *
986 * The srcu read lock should be hold around this function. And s is a seq snap
987 * after holding that lock.
988 */
989static void srcu_funnel_gp_start(struct srcu_struct *ssp, struct srcu_data *sdp,
990 unsigned long s, bool do_norm)
991{
992 unsigned long flags;
993 int idx = rcu_seq_ctr(s) % ARRAY_SIZE(sdp->mynode->srcu_have_cbs);
994 unsigned long sgsne;
995 struct srcu_node *snp;
996 struct srcu_node *snp_leaf;
997 unsigned long snp_seq;
998 struct srcu_usage *sup = ssp->srcu_sup;
999
1000 /* Ensure that snp node tree is fully initialized before traversing it */
1001 if (smp_load_acquire(&sup->srcu_size_state) < SRCU_SIZE_WAIT_BARRIER)
1002 snp_leaf = NULL;
1003 else
1004 snp_leaf = sdp->mynode;
1005
1006 if (snp_leaf)
1007 /* Each pass through the loop does one level of the srcu_node tree. */
1008 for (snp = snp_leaf; snp != NULL; snp = snp->srcu_parent) {
1009 if (WARN_ON_ONCE(rcu_seq_done(&sup->srcu_gp_seq, s)) && snp != snp_leaf)
1010 return; /* GP already done and CBs recorded. */
1011 spin_lock_irqsave_rcu_node(snp, flags);
1012 snp_seq = snp->srcu_have_cbs[idx];
1013 if (!srcu_invl_snp_seq(snp_seq) && ULONG_CMP_GE(snp_seq, s)) {
1014 if (snp == snp_leaf && snp_seq == s)
1015 snp->srcu_data_have_cbs[idx] |= sdp->grpmask;
1016 spin_unlock_irqrestore_rcu_node(snp, flags);
1017 if (snp == snp_leaf && snp_seq != s) {
1018 srcu_schedule_cbs_sdp(sdp, do_norm ? SRCU_INTERVAL : 0);
1019 return;
1020 }
1021 if (!do_norm)
1022 srcu_funnel_exp_start(ssp, snp, s);
1023 return;
1024 }
1025 snp->srcu_have_cbs[idx] = s;
1026 if (snp == snp_leaf)
1027 snp->srcu_data_have_cbs[idx] |= sdp->grpmask;
1028 sgsne = snp->srcu_gp_seq_needed_exp;
1029 if (!do_norm && (srcu_invl_snp_seq(sgsne) || ULONG_CMP_LT(sgsne, s)))
1030 WRITE_ONCE(snp->srcu_gp_seq_needed_exp, s);
1031 spin_unlock_irqrestore_rcu_node(snp, flags);
1032 }
1033
1034 /* Top of tree, must ensure the grace period will be started. */
1035 spin_lock_irqsave_ssp_contention(ssp, &flags);
1036 if (ULONG_CMP_LT(sup->srcu_gp_seq_needed, s)) {
1037 /*
1038 * Record need for grace period s. Pair with load
1039 * acquire setting up for initialization.
1040 */
1041 smp_store_release(&sup->srcu_gp_seq_needed, s); /*^^^*/
1042 }
1043 if (!do_norm && ULONG_CMP_LT(sup->srcu_gp_seq_needed_exp, s))
1044 WRITE_ONCE(sup->srcu_gp_seq_needed_exp, s);
1045
1046 /* If grace period not already in progress, start it. */
1047 if (!WARN_ON_ONCE(rcu_seq_done(&sup->srcu_gp_seq, s)) &&
1048 rcu_seq_state(sup->srcu_gp_seq) == SRCU_STATE_IDLE) {
1049 WARN_ON_ONCE(ULONG_CMP_GE(sup->srcu_gp_seq, sup->srcu_gp_seq_needed));
1050 srcu_gp_start(ssp);
1051
1052 // And how can that list_add() in the "else" clause
1053 // possibly be safe for concurrent execution? Well,
1054 // it isn't. And it does not have to be. After all, it
1055 // can only be executed during early boot when there is only
1056 // the one boot CPU running with interrupts still disabled.
1057 if (likely(srcu_init_done))
1058 queue_delayed_work(rcu_gp_wq, &sup->work,
1059 !!srcu_get_delay(ssp));
1060 else if (list_empty(&sup->work.work.entry))
1061 list_add(&sup->work.work.entry, &srcu_boot_list);
1062 }
1063 spin_unlock_irqrestore_rcu_node(sup, flags);
1064}
1065
1066/*
1067 * Wait until all readers counted by array index idx complete, but
1068 * loop an additional time if there is an expedited grace period pending.
1069 * The caller must ensure that ->srcu_idx is not changed while checking.
1070 */
1071static bool try_check_zero(struct srcu_struct *ssp, int idx, int trycount)
1072{
1073 unsigned long curdelay;
1074
1075 curdelay = !srcu_get_delay(ssp);
1076
1077 for (;;) {
1078 if (srcu_readers_active_idx_check(ssp, idx))
1079 return true;
1080 if ((--trycount + curdelay) <= 0)
1081 return false;
1082 udelay(srcu_retry_check_delay);
1083 }
1084}
1085
1086/*
1087 * Increment the ->srcu_idx counter so that future SRCU readers will
1088 * use the other rank of the ->srcu_(un)lock_count[] arrays. This allows
1089 * us to wait for pre-existing readers in a starvation-free manner.
1090 */
1091static void srcu_flip(struct srcu_struct *ssp)
1092{
1093 /*
1094 * Because the flip of ->srcu_idx is executed only if the
1095 * preceding call to srcu_readers_active_idx_check() found that
1096 * the ->srcu_unlock_count[] and ->srcu_lock_count[] sums matched
1097 * and because that summing uses atomic_long_read(), there is
1098 * ordering due to a control dependency between that summing and
1099 * the WRITE_ONCE() in this call to srcu_flip(). This ordering
1100 * ensures that if this updater saw a given reader's increment from
1101 * __srcu_read_lock(), that reader was using a value of ->srcu_idx
1102 * from before the previous call to srcu_flip(), which should be
1103 * quite rare. This ordering thus helps forward progress because
1104 * the grace period could otherwise be delayed by additional
1105 * calls to __srcu_read_lock() using that old (soon to be new)
1106 * value of ->srcu_idx.
1107 *
1108 * This sum-equality check and ordering also ensures that if
1109 * a given call to __srcu_read_lock() uses the new value of
1110 * ->srcu_idx, this updater's earlier scans cannot have seen
1111 * that reader's increments, which is all to the good, because
1112 * this grace period need not wait on that reader. After all,
1113 * if those earlier scans had seen that reader, there would have
1114 * been a sum mismatch and this code would not be reached.
1115 *
1116 * This means that the following smp_mb() is redundant, but
1117 * it stays until either (1) Compilers learn about this sort of
1118 * control dependency or (2) Some production workload running on
1119 * a production system is unduly delayed by this slowpath smp_mb().
1120 */
1121 smp_mb(); /* E */ /* Pairs with B and C. */
1122
1123 WRITE_ONCE(ssp->srcu_idx, ssp->srcu_idx + 1); // Flip the counter.
1124
1125 /*
1126 * Ensure that if the updater misses an __srcu_read_unlock()
1127 * increment, that task's __srcu_read_lock() following its next
1128 * __srcu_read_lock() or __srcu_read_unlock() will see the above
1129 * counter update. Note that both this memory barrier and the
1130 * one in srcu_readers_active_idx_check() provide the guarantee
1131 * for __srcu_read_lock().
1132 */
1133 smp_mb(); /* D */ /* Pairs with C. */
1134}
1135
1136/*
1137 * If SRCU is likely idle, return true, otherwise return false.
1138 *
1139 * Note that it is OK for several current from-idle requests for a new
1140 * grace period from idle to specify expediting because they will all end
1141 * up requesting the same grace period anyhow. So no loss.
1142 *
1143 * Note also that if any CPU (including the current one) is still invoking
1144 * callbacks, this function will nevertheless say "idle". This is not
1145 * ideal, but the overhead of checking all CPUs' callback lists is even
1146 * less ideal, especially on large systems. Furthermore, the wakeup
1147 * can happen before the callback is fully removed, so we have no choice
1148 * but to accept this type of error.
1149 *
1150 * This function is also subject to counter-wrap errors, but let's face
1151 * it, if this function was preempted for enough time for the counters
1152 * to wrap, it really doesn't matter whether or not we expedite the grace
1153 * period. The extra overhead of a needlessly expedited grace period is
1154 * negligible when amortized over that time period, and the extra latency
1155 * of a needlessly non-expedited grace period is similarly negligible.
1156 */
1157static bool srcu_might_be_idle(struct srcu_struct *ssp)
1158{
1159 unsigned long curseq;
1160 unsigned long flags;
1161 struct srcu_data *sdp;
1162 unsigned long t;
1163 unsigned long tlast;
1164
1165 check_init_srcu_struct(ssp);
1166 /* If the local srcu_data structure has callbacks, not idle. */
1167 sdp = raw_cpu_ptr(ssp->sda);
1168 spin_lock_irqsave_rcu_node(sdp, flags);
1169 if (rcu_segcblist_pend_cbs(&sdp->srcu_cblist)) {
1170 spin_unlock_irqrestore_rcu_node(sdp, flags);
1171 return false; /* Callbacks already present, so not idle. */
1172 }
1173 spin_unlock_irqrestore_rcu_node(sdp, flags);
1174
1175 /*
1176 * No local callbacks, so probabilistically probe global state.
1177 * Exact information would require acquiring locks, which would
1178 * kill scalability, hence the probabilistic nature of the probe.
1179 */
1180
1181 /* First, see if enough time has passed since the last GP. */
1182 t = ktime_get_mono_fast_ns();
1183 tlast = READ_ONCE(ssp->srcu_sup->srcu_last_gp_end);
1184 if (exp_holdoff == 0 ||
1185 time_in_range_open(t, tlast, tlast + exp_holdoff))
1186 return false; /* Too soon after last GP. */
1187
1188 /* Next, check for probable idleness. */
1189 curseq = rcu_seq_current(&ssp->srcu_sup->srcu_gp_seq);
1190 smp_mb(); /* Order ->srcu_gp_seq with ->srcu_gp_seq_needed. */
1191 if (ULONG_CMP_LT(curseq, READ_ONCE(ssp->srcu_sup->srcu_gp_seq_needed)))
1192 return false; /* Grace period in progress, so not idle. */
1193 smp_mb(); /* Order ->srcu_gp_seq with prior access. */
1194 if (curseq != rcu_seq_current(&ssp->srcu_sup->srcu_gp_seq))
1195 return false; /* GP # changed, so not idle. */
1196 return true; /* With reasonable probability, idle! */
1197}
1198
1199/*
1200 * SRCU callback function to leak a callback.
1201 */
1202static void srcu_leak_callback(struct rcu_head *rhp)
1203{
1204}
1205
1206/*
1207 * Start an SRCU grace period, and also queue the callback if non-NULL.
1208 */
1209static unsigned long srcu_gp_start_if_needed(struct srcu_struct *ssp,
1210 struct rcu_head *rhp, bool do_norm)
1211{
1212 unsigned long flags;
1213 int idx;
1214 bool needexp = false;
1215 bool needgp = false;
1216 unsigned long s;
1217 struct srcu_data *sdp;
1218 struct srcu_node *sdp_mynode;
1219 int ss_state;
1220
1221 check_init_srcu_struct(ssp);
1222 /*
1223 * While starting a new grace period, make sure we are in an
1224 * SRCU read-side critical section so that the grace-period
1225 * sequence number cannot wrap around in the meantime.
1226 */
1227 idx = __srcu_read_lock_nmisafe(ssp);
1228 ss_state = smp_load_acquire(&ssp->srcu_sup->srcu_size_state);
1229 if (ss_state < SRCU_SIZE_WAIT_CALL)
1230 sdp = per_cpu_ptr(ssp->sda, get_boot_cpu_id());
1231 else
1232 sdp = raw_cpu_ptr(ssp->sda);
1233 spin_lock_irqsave_sdp_contention(sdp, &flags);
1234 if (rhp)
1235 rcu_segcblist_enqueue(&sdp->srcu_cblist, rhp);
1236 /*
1237 * The snapshot for acceleration must be taken _before_ the read of the
1238 * current gp sequence used for advancing, otherwise advancing may fail
1239 * and acceleration may then fail too.
1240 *
1241 * This could happen if:
1242 *
1243 * 1) The RCU_WAIT_TAIL segment has callbacks (gp_num = X + 4) and the
1244 * RCU_NEXT_READY_TAIL also has callbacks (gp_num = X + 8).
1245 *
1246 * 2) The grace period for RCU_WAIT_TAIL is seen as started but not
1247 * completed so rcu_seq_current() returns X + SRCU_STATE_SCAN1.
1248 *
1249 * 3) This value is passed to rcu_segcblist_advance() which can't move
1250 * any segment forward and fails.
1251 *
1252 * 4) srcu_gp_start_if_needed() still proceeds with callback acceleration.
1253 * But then the call to rcu_seq_snap() observes the grace period for the
1254 * RCU_WAIT_TAIL segment as completed and the subsequent one for the
1255 * RCU_NEXT_READY_TAIL segment as started (ie: X + 4 + SRCU_STATE_SCAN1)
1256 * so it returns a snapshot of the next grace period, which is X + 12.
1257 *
1258 * 5) The value of X + 12 is passed to rcu_segcblist_accelerate() but the
1259 * freshly enqueued callback in RCU_NEXT_TAIL can't move to
1260 * RCU_NEXT_READY_TAIL which already has callbacks for a previous grace
1261 * period (gp_num = X + 8). So acceleration fails.
1262 */
1263 s = rcu_seq_snap(&ssp->srcu_sup->srcu_gp_seq);
1264 if (rhp) {
1265 rcu_segcblist_advance(&sdp->srcu_cblist,
1266 rcu_seq_current(&ssp->srcu_sup->srcu_gp_seq));
1267 WARN_ON_ONCE(!rcu_segcblist_accelerate(&sdp->srcu_cblist, s));
1268 }
1269 if (ULONG_CMP_LT(sdp->srcu_gp_seq_needed, s)) {
1270 sdp->srcu_gp_seq_needed = s;
1271 needgp = true;
1272 }
1273 if (!do_norm && ULONG_CMP_LT(sdp->srcu_gp_seq_needed_exp, s)) {
1274 sdp->srcu_gp_seq_needed_exp = s;
1275 needexp = true;
1276 }
1277 spin_unlock_irqrestore_rcu_node(sdp, flags);
1278
1279 /* Ensure that snp node tree is fully initialized before traversing it */
1280 if (ss_state < SRCU_SIZE_WAIT_BARRIER)
1281 sdp_mynode = NULL;
1282 else
1283 sdp_mynode = sdp->mynode;
1284
1285 if (needgp)
1286 srcu_funnel_gp_start(ssp, sdp, s, do_norm);
1287 else if (needexp)
1288 srcu_funnel_exp_start(ssp, sdp_mynode, s);
1289 __srcu_read_unlock_nmisafe(ssp, idx);
1290 return s;
1291}
1292
1293/*
1294 * Enqueue an SRCU callback on the srcu_data structure associated with
1295 * the current CPU and the specified srcu_struct structure, initiating
1296 * grace-period processing if it is not already running.
1297 *
1298 * Note that all CPUs must agree that the grace period extended beyond
1299 * all pre-existing SRCU read-side critical section. On systems with
1300 * more than one CPU, this means that when "func()" is invoked, each CPU
1301 * is guaranteed to have executed a full memory barrier since the end of
1302 * its last corresponding SRCU read-side critical section whose beginning
1303 * preceded the call to call_srcu(). It also means that each CPU executing
1304 * an SRCU read-side critical section that continues beyond the start of
1305 * "func()" must have executed a memory barrier after the call_srcu()
1306 * but before the beginning of that SRCU read-side critical section.
1307 * Note that these guarantees include CPUs that are offline, idle, or
1308 * executing in user mode, as well as CPUs that are executing in the kernel.
1309 *
1310 * Furthermore, if CPU A invoked call_srcu() and CPU B invoked the
1311 * resulting SRCU callback function "func()", then both CPU A and CPU
1312 * B are guaranteed to execute a full memory barrier during the time
1313 * interval between the call to call_srcu() and the invocation of "func()".
1314 * This guarantee applies even if CPU A and CPU B are the same CPU (but
1315 * again only if the system has more than one CPU).
1316 *
1317 * Of course, these guarantees apply only for invocations of call_srcu(),
1318 * srcu_read_lock(), and srcu_read_unlock() that are all passed the same
1319 * srcu_struct structure.
1320 */
1321static void __call_srcu(struct srcu_struct *ssp, struct rcu_head *rhp,
1322 rcu_callback_t func, bool do_norm)
1323{
1324 if (debug_rcu_head_queue(rhp)) {
1325 /* Probable double call_srcu(), so leak the callback. */
1326 WRITE_ONCE(rhp->func, srcu_leak_callback);
1327 WARN_ONCE(1, "call_srcu(): Leaked duplicate callback\n");
1328 return;
1329 }
1330 rhp->func = func;
1331 (void)srcu_gp_start_if_needed(ssp, rhp, do_norm);
1332}
1333
1334/**
1335 * call_srcu() - Queue a callback for invocation after an SRCU grace period
1336 * @ssp: srcu_struct in queue the callback
1337 * @rhp: structure to be used for queueing the SRCU callback.
1338 * @func: function to be invoked after the SRCU grace period
1339 *
1340 * The callback function will be invoked some time after a full SRCU
1341 * grace period elapses, in other words after all pre-existing SRCU
1342 * read-side critical sections have completed. However, the callback
1343 * function might well execute concurrently with other SRCU read-side
1344 * critical sections that started after call_srcu() was invoked. SRCU
1345 * read-side critical sections are delimited by srcu_read_lock() and
1346 * srcu_read_unlock(), and may be nested.
1347 *
1348 * The callback will be invoked from process context, but must nevertheless
1349 * be fast and must not block.
1350 */
1351void call_srcu(struct srcu_struct *ssp, struct rcu_head *rhp,
1352 rcu_callback_t func)
1353{
1354 __call_srcu(ssp, rhp, func, true);
1355}
1356EXPORT_SYMBOL_GPL(call_srcu);
1357
1358/*
1359 * Helper function for synchronize_srcu() and synchronize_srcu_expedited().
1360 */
1361static void __synchronize_srcu(struct srcu_struct *ssp, bool do_norm)
1362{
1363 struct rcu_synchronize rcu;
1364
1365 srcu_lock_sync(&ssp->dep_map);
1366
1367 RCU_LOCKDEP_WARN(lockdep_is_held(ssp) ||
1368 lock_is_held(&rcu_bh_lock_map) ||
1369 lock_is_held(&rcu_lock_map) ||
1370 lock_is_held(&rcu_sched_lock_map),
1371 "Illegal synchronize_srcu() in same-type SRCU (or in RCU) read-side critical section");
1372
1373 if (rcu_scheduler_active == RCU_SCHEDULER_INACTIVE)
1374 return;
1375 might_sleep();
1376 check_init_srcu_struct(ssp);
1377 init_completion(&rcu.completion);
1378 init_rcu_head_on_stack(&rcu.head);
1379 __call_srcu(ssp, &rcu.head, wakeme_after_rcu, do_norm);
1380 wait_for_completion(&rcu.completion);
1381 destroy_rcu_head_on_stack(&rcu.head);
1382
1383 /*
1384 * Make sure that later code is ordered after the SRCU grace
1385 * period. This pairs with the spin_lock_irq_rcu_node()
1386 * in srcu_invoke_callbacks(). Unlike Tree RCU, this is needed
1387 * because the current CPU might have been totally uninvolved with
1388 * (and thus unordered against) that grace period.
1389 */
1390 smp_mb();
1391}
1392
1393/**
1394 * synchronize_srcu_expedited - Brute-force SRCU grace period
1395 * @ssp: srcu_struct with which to synchronize.
1396 *
1397 * Wait for an SRCU grace period to elapse, but be more aggressive about
1398 * spinning rather than blocking when waiting.
1399 *
1400 * Note that synchronize_srcu_expedited() has the same deadlock and
1401 * memory-ordering properties as does synchronize_srcu().
1402 */
1403void synchronize_srcu_expedited(struct srcu_struct *ssp)
1404{
1405 __synchronize_srcu(ssp, rcu_gp_is_normal());
1406}
1407EXPORT_SYMBOL_GPL(synchronize_srcu_expedited);
1408
1409/**
1410 * synchronize_srcu - wait for prior SRCU read-side critical-section completion
1411 * @ssp: srcu_struct with which to synchronize.
1412 *
1413 * Wait for the count to drain to zero of both indexes. To avoid the
1414 * possible starvation of synchronize_srcu(), it waits for the count of
1415 * the index=((->srcu_idx & 1) ^ 1) to drain to zero at first,
1416 * and then flip the srcu_idx and wait for the count of the other index.
1417 *
1418 * Can block; must be called from process context.
1419 *
1420 * Note that it is illegal to call synchronize_srcu() from the corresponding
1421 * SRCU read-side critical section; doing so will result in deadlock.
1422 * However, it is perfectly legal to call synchronize_srcu() on one
1423 * srcu_struct from some other srcu_struct's read-side critical section,
1424 * as long as the resulting graph of srcu_structs is acyclic.
1425 *
1426 * There are memory-ordering constraints implied by synchronize_srcu().
1427 * On systems with more than one CPU, when synchronize_srcu() returns,
1428 * each CPU is guaranteed to have executed a full memory barrier since
1429 * the end of its last corresponding SRCU read-side critical section
1430 * whose beginning preceded the call to synchronize_srcu(). In addition,
1431 * each CPU having an SRCU read-side critical section that extends beyond
1432 * the return from synchronize_srcu() is guaranteed to have executed a
1433 * full memory barrier after the beginning of synchronize_srcu() and before
1434 * the beginning of that SRCU read-side critical section. Note that these
1435 * guarantees include CPUs that are offline, idle, or executing in user mode,
1436 * as well as CPUs that are executing in the kernel.
1437 *
1438 * Furthermore, if CPU A invoked synchronize_srcu(), which returned
1439 * to its caller on CPU B, then both CPU A and CPU B are guaranteed
1440 * to have executed a full memory barrier during the execution of
1441 * synchronize_srcu(). This guarantee applies even if CPU A and CPU B
1442 * are the same CPU, but again only if the system has more than one CPU.
1443 *
1444 * Of course, these memory-ordering guarantees apply only when
1445 * synchronize_srcu(), srcu_read_lock(), and srcu_read_unlock() are
1446 * passed the same srcu_struct structure.
1447 *
1448 * Implementation of these memory-ordering guarantees is similar to
1449 * that of synchronize_rcu().
1450 *
1451 * If SRCU is likely idle, expedite the first request. This semantic
1452 * was provided by Classic SRCU, and is relied upon by its users, so TREE
1453 * SRCU must also provide it. Note that detecting idleness is heuristic
1454 * and subject to both false positives and negatives.
1455 */
1456void synchronize_srcu(struct srcu_struct *ssp)
1457{
1458 if (srcu_might_be_idle(ssp) || rcu_gp_is_expedited())
1459 synchronize_srcu_expedited(ssp);
1460 else
1461 __synchronize_srcu(ssp, true);
1462}
1463EXPORT_SYMBOL_GPL(synchronize_srcu);
1464
1465/**
1466 * get_state_synchronize_srcu - Provide an end-of-grace-period cookie
1467 * @ssp: srcu_struct to provide cookie for.
1468 *
1469 * This function returns a cookie that can be passed to
1470 * poll_state_synchronize_srcu(), which will return true if a full grace
1471 * period has elapsed in the meantime. It is the caller's responsibility
1472 * to make sure that grace period happens, for example, by invoking
1473 * call_srcu() after return from get_state_synchronize_srcu().
1474 */
1475unsigned long get_state_synchronize_srcu(struct srcu_struct *ssp)
1476{
1477 // Any prior manipulation of SRCU-protected data must happen
1478 // before the load from ->srcu_gp_seq.
1479 smp_mb();
1480 return rcu_seq_snap(&ssp->srcu_sup->srcu_gp_seq);
1481}
1482EXPORT_SYMBOL_GPL(get_state_synchronize_srcu);
1483
1484/**
1485 * start_poll_synchronize_srcu - Provide cookie and start grace period
1486 * @ssp: srcu_struct to provide cookie for.
1487 *
1488 * This function returns a cookie that can be passed to
1489 * poll_state_synchronize_srcu(), which will return true if a full grace
1490 * period has elapsed in the meantime. Unlike get_state_synchronize_srcu(),
1491 * this function also ensures that any needed SRCU grace period will be
1492 * started. This convenience does come at a cost in terms of CPU overhead.
1493 */
1494unsigned long start_poll_synchronize_srcu(struct srcu_struct *ssp)
1495{
1496 return srcu_gp_start_if_needed(ssp, NULL, true);
1497}
1498EXPORT_SYMBOL_GPL(start_poll_synchronize_srcu);
1499
1500/**
1501 * poll_state_synchronize_srcu - Has cookie's grace period ended?
1502 * @ssp: srcu_struct to provide cookie for.
1503 * @cookie: Return value from get_state_synchronize_srcu() or start_poll_synchronize_srcu().
1504 *
1505 * This function takes the cookie that was returned from either
1506 * get_state_synchronize_srcu() or start_poll_synchronize_srcu(), and
1507 * returns @true if an SRCU grace period elapsed since the time that the
1508 * cookie was created.
1509 *
1510 * Because cookies are finite in size, wrapping/overflow is possible.
1511 * This is more pronounced on 32-bit systems where cookies are 32 bits,
1512 * where in theory wrapping could happen in about 14 hours assuming
1513 * 25-microsecond expedited SRCU grace periods. However, a more likely
1514 * overflow lower bound is on the order of 24 days in the case of
1515 * one-millisecond SRCU grace periods. Of course, wrapping in a 64-bit
1516 * system requires geologic timespans, as in more than seven million years
1517 * even for expedited SRCU grace periods.
1518 *
1519 * Wrapping/overflow is much more of an issue for CONFIG_SMP=n systems
1520 * that also have CONFIG_PREEMPTION=n, which selects Tiny SRCU. This uses
1521 * a 16-bit cookie, which rcutorture routinely wraps in a matter of a
1522 * few minutes. If this proves to be a problem, this counter will be
1523 * expanded to the same size as for Tree SRCU.
1524 */
1525bool poll_state_synchronize_srcu(struct srcu_struct *ssp, unsigned long cookie)
1526{
1527 if (!rcu_seq_done(&ssp->srcu_sup->srcu_gp_seq, cookie))
1528 return false;
1529 // Ensure that the end of the SRCU grace period happens before
1530 // any subsequent code that the caller might execute.
1531 smp_mb(); // ^^^
1532 return true;
1533}
1534EXPORT_SYMBOL_GPL(poll_state_synchronize_srcu);
1535
1536/*
1537 * Callback function for srcu_barrier() use.
1538 */
1539static void srcu_barrier_cb(struct rcu_head *rhp)
1540{
1541 struct srcu_data *sdp;
1542 struct srcu_struct *ssp;
1543
1544 sdp = container_of(rhp, struct srcu_data, srcu_barrier_head);
1545 ssp = sdp->ssp;
1546 if (atomic_dec_and_test(&ssp->srcu_sup->srcu_barrier_cpu_cnt))
1547 complete(&ssp->srcu_sup->srcu_barrier_completion);
1548}
1549
1550/*
1551 * Enqueue an srcu_barrier() callback on the specified srcu_data
1552 * structure's ->cblist. but only if that ->cblist already has at least one
1553 * callback enqueued. Note that if a CPU already has callbacks enqueue,
1554 * it must have already registered the need for a future grace period,
1555 * so all we need do is enqueue a callback that will use the same grace
1556 * period as the last callback already in the queue.
1557 */
1558static void srcu_barrier_one_cpu(struct srcu_struct *ssp, struct srcu_data *sdp)
1559{
1560 spin_lock_irq_rcu_node(sdp);
1561 atomic_inc(&ssp->srcu_sup->srcu_barrier_cpu_cnt);
1562 sdp->srcu_barrier_head.func = srcu_barrier_cb;
1563 debug_rcu_head_queue(&sdp->srcu_barrier_head);
1564 if (!rcu_segcblist_entrain(&sdp->srcu_cblist,
1565 &sdp->srcu_barrier_head)) {
1566 debug_rcu_head_unqueue(&sdp->srcu_barrier_head);
1567 atomic_dec(&ssp->srcu_sup->srcu_barrier_cpu_cnt);
1568 }
1569 spin_unlock_irq_rcu_node(sdp);
1570}
1571
1572/**
1573 * srcu_barrier - Wait until all in-flight call_srcu() callbacks complete.
1574 * @ssp: srcu_struct on which to wait for in-flight callbacks.
1575 */
1576void srcu_barrier(struct srcu_struct *ssp)
1577{
1578 int cpu;
1579 int idx;
1580 unsigned long s = rcu_seq_snap(&ssp->srcu_sup->srcu_barrier_seq);
1581
1582 check_init_srcu_struct(ssp);
1583 mutex_lock(&ssp->srcu_sup->srcu_barrier_mutex);
1584 if (rcu_seq_done(&ssp->srcu_sup->srcu_barrier_seq, s)) {
1585 smp_mb(); /* Force ordering following return. */
1586 mutex_unlock(&ssp->srcu_sup->srcu_barrier_mutex);
1587 return; /* Someone else did our work for us. */
1588 }
1589 rcu_seq_start(&ssp->srcu_sup->srcu_barrier_seq);
1590 init_completion(&ssp->srcu_sup->srcu_barrier_completion);
1591
1592 /* Initial count prevents reaching zero until all CBs are posted. */
1593 atomic_set(&ssp->srcu_sup->srcu_barrier_cpu_cnt, 1);
1594
1595 idx = __srcu_read_lock_nmisafe(ssp);
1596 if (smp_load_acquire(&ssp->srcu_sup->srcu_size_state) < SRCU_SIZE_WAIT_BARRIER)
1597 srcu_barrier_one_cpu(ssp, per_cpu_ptr(ssp->sda, get_boot_cpu_id()));
1598 else
1599 for_each_possible_cpu(cpu)
1600 srcu_barrier_one_cpu(ssp, per_cpu_ptr(ssp->sda, cpu));
1601 __srcu_read_unlock_nmisafe(ssp, idx);
1602
1603 /* Remove the initial count, at which point reaching zero can happen. */
1604 if (atomic_dec_and_test(&ssp->srcu_sup->srcu_barrier_cpu_cnt))
1605 complete(&ssp->srcu_sup->srcu_barrier_completion);
1606 wait_for_completion(&ssp->srcu_sup->srcu_barrier_completion);
1607
1608 rcu_seq_end(&ssp->srcu_sup->srcu_barrier_seq);
1609 mutex_unlock(&ssp->srcu_sup->srcu_barrier_mutex);
1610}
1611EXPORT_SYMBOL_GPL(srcu_barrier);
1612
1613/**
1614 * srcu_batches_completed - return batches completed.
1615 * @ssp: srcu_struct on which to report batch completion.
1616 *
1617 * Report the number of batches, correlated with, but not necessarily
1618 * precisely the same as, the number of grace periods that have elapsed.
1619 */
1620unsigned long srcu_batches_completed(struct srcu_struct *ssp)
1621{
1622 return READ_ONCE(ssp->srcu_idx);
1623}
1624EXPORT_SYMBOL_GPL(srcu_batches_completed);
1625
1626/*
1627 * Core SRCU state machine. Push state bits of ->srcu_gp_seq
1628 * to SRCU_STATE_SCAN2, and invoke srcu_gp_end() when scan has
1629 * completed in that state.
1630 */
1631static void srcu_advance_state(struct srcu_struct *ssp)
1632{
1633 int idx;
1634
1635 mutex_lock(&ssp->srcu_sup->srcu_gp_mutex);
1636
1637 /*
1638 * Because readers might be delayed for an extended period after
1639 * fetching ->srcu_idx for their index, at any point in time there
1640 * might well be readers using both idx=0 and idx=1. We therefore
1641 * need to wait for readers to clear from both index values before
1642 * invoking a callback.
1643 *
1644 * The load-acquire ensures that we see the accesses performed
1645 * by the prior grace period.
1646 */
1647 idx = rcu_seq_state(smp_load_acquire(&ssp->srcu_sup->srcu_gp_seq)); /* ^^^ */
1648 if (idx == SRCU_STATE_IDLE) {
1649 spin_lock_irq_rcu_node(ssp->srcu_sup);
1650 if (ULONG_CMP_GE(ssp->srcu_sup->srcu_gp_seq, ssp->srcu_sup->srcu_gp_seq_needed)) {
1651 WARN_ON_ONCE(rcu_seq_state(ssp->srcu_sup->srcu_gp_seq));
1652 spin_unlock_irq_rcu_node(ssp->srcu_sup);
1653 mutex_unlock(&ssp->srcu_sup->srcu_gp_mutex);
1654 return;
1655 }
1656 idx = rcu_seq_state(READ_ONCE(ssp->srcu_sup->srcu_gp_seq));
1657 if (idx == SRCU_STATE_IDLE)
1658 srcu_gp_start(ssp);
1659 spin_unlock_irq_rcu_node(ssp->srcu_sup);
1660 if (idx != SRCU_STATE_IDLE) {
1661 mutex_unlock(&ssp->srcu_sup->srcu_gp_mutex);
1662 return; /* Someone else started the grace period. */
1663 }
1664 }
1665
1666 if (rcu_seq_state(READ_ONCE(ssp->srcu_sup->srcu_gp_seq)) == SRCU_STATE_SCAN1) {
1667 idx = 1 ^ (ssp->srcu_idx & 1);
1668 if (!try_check_zero(ssp, idx, 1)) {
1669 mutex_unlock(&ssp->srcu_sup->srcu_gp_mutex);
1670 return; /* readers present, retry later. */
1671 }
1672 srcu_flip(ssp);
1673 spin_lock_irq_rcu_node(ssp->srcu_sup);
1674 rcu_seq_set_state(&ssp->srcu_sup->srcu_gp_seq, SRCU_STATE_SCAN2);
1675 ssp->srcu_sup->srcu_n_exp_nodelay = 0;
1676 spin_unlock_irq_rcu_node(ssp->srcu_sup);
1677 }
1678
1679 if (rcu_seq_state(READ_ONCE(ssp->srcu_sup->srcu_gp_seq)) == SRCU_STATE_SCAN2) {
1680
1681 /*
1682 * SRCU read-side critical sections are normally short,
1683 * so check at least twice in quick succession after a flip.
1684 */
1685 idx = 1 ^ (ssp->srcu_idx & 1);
1686 if (!try_check_zero(ssp, idx, 2)) {
1687 mutex_unlock(&ssp->srcu_sup->srcu_gp_mutex);
1688 return; /* readers present, retry later. */
1689 }
1690 ssp->srcu_sup->srcu_n_exp_nodelay = 0;
1691 srcu_gp_end(ssp); /* Releases ->srcu_gp_mutex. */
1692 }
1693}
1694
1695/*
1696 * Invoke a limited number of SRCU callbacks that have passed through
1697 * their grace period. If there are more to do, SRCU will reschedule
1698 * the workqueue. Note that needed memory barriers have been executed
1699 * in this task's context by srcu_readers_active_idx_check().
1700 */
1701static void srcu_invoke_callbacks(struct work_struct *work)
1702{
1703 long len;
1704 bool more;
1705 struct rcu_cblist ready_cbs;
1706 struct rcu_head *rhp;
1707 struct srcu_data *sdp;
1708 struct srcu_struct *ssp;
1709
1710 sdp = container_of(work, struct srcu_data, work);
1711
1712 ssp = sdp->ssp;
1713 rcu_cblist_init(&ready_cbs);
1714 spin_lock_irq_rcu_node(sdp);
1715 WARN_ON_ONCE(!rcu_segcblist_segempty(&sdp->srcu_cblist, RCU_NEXT_TAIL));
1716 rcu_segcblist_advance(&sdp->srcu_cblist,
1717 rcu_seq_current(&ssp->srcu_sup->srcu_gp_seq));
1718 /*
1719 * Although this function is theoretically re-entrant, concurrent
1720 * callbacks invocation is disallowed to avoid executing an SRCU barrier
1721 * too early.
1722 */
1723 if (sdp->srcu_cblist_invoking ||
1724 !rcu_segcblist_ready_cbs(&sdp->srcu_cblist)) {
1725 spin_unlock_irq_rcu_node(sdp);
1726 return; /* Someone else on the job or nothing to do. */
1727 }
1728
1729 /* We are on the job! Extract and invoke ready callbacks. */
1730 sdp->srcu_cblist_invoking = true;
1731 rcu_segcblist_extract_done_cbs(&sdp->srcu_cblist, &ready_cbs);
1732 len = ready_cbs.len;
1733 spin_unlock_irq_rcu_node(sdp);
1734 rhp = rcu_cblist_dequeue(&ready_cbs);
1735 for (; rhp != NULL; rhp = rcu_cblist_dequeue(&ready_cbs)) {
1736 debug_rcu_head_unqueue(rhp);
1737 debug_rcu_head_callback(rhp);
1738 local_bh_disable();
1739 rhp->func(rhp);
1740 local_bh_enable();
1741 }
1742 WARN_ON_ONCE(ready_cbs.len);
1743
1744 /*
1745 * Update counts, accelerate new callbacks, and if needed,
1746 * schedule another round of callback invocation.
1747 */
1748 spin_lock_irq_rcu_node(sdp);
1749 rcu_segcblist_add_len(&sdp->srcu_cblist, -len);
1750 sdp->srcu_cblist_invoking = false;
1751 more = rcu_segcblist_ready_cbs(&sdp->srcu_cblist);
1752 spin_unlock_irq_rcu_node(sdp);
1753 /* An SRCU barrier or callbacks from previous nesting work pending */
1754 if (more)
1755 srcu_schedule_cbs_sdp(sdp, 0);
1756}
1757
1758/*
1759 * Finished one round of SRCU grace period. Start another if there are
1760 * more SRCU callbacks queued, otherwise put SRCU into not-running state.
1761 */
1762static void srcu_reschedule(struct srcu_struct *ssp, unsigned long delay)
1763{
1764 bool pushgp = true;
1765
1766 spin_lock_irq_rcu_node(ssp->srcu_sup);
1767 if (ULONG_CMP_GE(ssp->srcu_sup->srcu_gp_seq, ssp->srcu_sup->srcu_gp_seq_needed)) {
1768 if (!WARN_ON_ONCE(rcu_seq_state(ssp->srcu_sup->srcu_gp_seq))) {
1769 /* All requests fulfilled, time to go idle. */
1770 pushgp = false;
1771 }
1772 } else if (!rcu_seq_state(ssp->srcu_sup->srcu_gp_seq)) {
1773 /* Outstanding request and no GP. Start one. */
1774 srcu_gp_start(ssp);
1775 }
1776 spin_unlock_irq_rcu_node(ssp->srcu_sup);
1777
1778 if (pushgp)
1779 queue_delayed_work(rcu_gp_wq, &ssp->srcu_sup->work, delay);
1780}
1781
1782/*
1783 * This is the work-queue function that handles SRCU grace periods.
1784 */
1785static void process_srcu(struct work_struct *work)
1786{
1787 unsigned long curdelay;
1788 unsigned long j;
1789 struct srcu_struct *ssp;
1790 struct srcu_usage *sup;
1791
1792 sup = container_of(work, struct srcu_usage, work.work);
1793 ssp = sup->srcu_ssp;
1794
1795 srcu_advance_state(ssp);
1796 curdelay = srcu_get_delay(ssp);
1797 if (curdelay) {
1798 WRITE_ONCE(sup->reschedule_count, 0);
1799 } else {
1800 j = jiffies;
1801 if (READ_ONCE(sup->reschedule_jiffies) == j) {
1802 WRITE_ONCE(sup->reschedule_count, READ_ONCE(sup->reschedule_count) + 1);
1803 if (READ_ONCE(sup->reschedule_count) > srcu_max_nodelay)
1804 curdelay = 1;
1805 } else {
1806 WRITE_ONCE(sup->reschedule_count, 1);
1807 WRITE_ONCE(sup->reschedule_jiffies, j);
1808 }
1809 }
1810 srcu_reschedule(ssp, curdelay);
1811}
1812
1813void srcutorture_get_gp_data(enum rcutorture_type test_type,
1814 struct srcu_struct *ssp, int *flags,
1815 unsigned long *gp_seq)
1816{
1817 if (test_type != SRCU_FLAVOR)
1818 return;
1819 *flags = 0;
1820 *gp_seq = rcu_seq_current(&ssp->srcu_sup->srcu_gp_seq);
1821}
1822EXPORT_SYMBOL_GPL(srcutorture_get_gp_data);
1823
1824static const char * const srcu_size_state_name[] = {
1825 "SRCU_SIZE_SMALL",
1826 "SRCU_SIZE_ALLOC",
1827 "SRCU_SIZE_WAIT_BARRIER",
1828 "SRCU_SIZE_WAIT_CALL",
1829 "SRCU_SIZE_WAIT_CBS1",
1830 "SRCU_SIZE_WAIT_CBS2",
1831 "SRCU_SIZE_WAIT_CBS3",
1832 "SRCU_SIZE_WAIT_CBS4",
1833 "SRCU_SIZE_BIG",
1834 "SRCU_SIZE_???",
1835};
1836
1837void srcu_torture_stats_print(struct srcu_struct *ssp, char *tt, char *tf)
1838{
1839 int cpu;
1840 int idx;
1841 unsigned long s0 = 0, s1 = 0;
1842 int ss_state = READ_ONCE(ssp->srcu_sup->srcu_size_state);
1843 int ss_state_idx = ss_state;
1844
1845 idx = ssp->srcu_idx & 0x1;
1846 if (ss_state < 0 || ss_state >= ARRAY_SIZE(srcu_size_state_name))
1847 ss_state_idx = ARRAY_SIZE(srcu_size_state_name) - 1;
1848 pr_alert("%s%s Tree SRCU g%ld state %d (%s)",
1849 tt, tf, rcu_seq_current(&ssp->srcu_sup->srcu_gp_seq), ss_state,
1850 srcu_size_state_name[ss_state_idx]);
1851 if (!ssp->sda) {
1852 // Called after cleanup_srcu_struct(), perhaps.
1853 pr_cont(" No per-CPU srcu_data structures (->sda == NULL).\n");
1854 } else {
1855 pr_cont(" per-CPU(idx=%d):", idx);
1856 for_each_possible_cpu(cpu) {
1857 unsigned long l0, l1;
1858 unsigned long u0, u1;
1859 long c0, c1;
1860 struct srcu_data *sdp;
1861
1862 sdp = per_cpu_ptr(ssp->sda, cpu);
1863 u0 = data_race(atomic_long_read(&sdp->srcu_unlock_count[!idx]));
1864 u1 = data_race(atomic_long_read(&sdp->srcu_unlock_count[idx]));
1865
1866 /*
1867 * Make sure that a lock is always counted if the corresponding
1868 * unlock is counted.
1869 */
1870 smp_rmb();
1871
1872 l0 = data_race(atomic_long_read(&sdp->srcu_lock_count[!idx]));
1873 l1 = data_race(atomic_long_read(&sdp->srcu_lock_count[idx]));
1874
1875 c0 = l0 - u0;
1876 c1 = l1 - u1;
1877 pr_cont(" %d(%ld,%ld %c)",
1878 cpu, c0, c1,
1879 "C."[rcu_segcblist_empty(&sdp->srcu_cblist)]);
1880 s0 += c0;
1881 s1 += c1;
1882 }
1883 pr_cont(" T(%ld,%ld)\n", s0, s1);
1884 }
1885 if (SRCU_SIZING_IS_TORTURE())
1886 srcu_transition_to_big(ssp);
1887}
1888EXPORT_SYMBOL_GPL(srcu_torture_stats_print);
1889
1890static int __init srcu_bootup_announce(void)
1891{
1892 pr_info("Hierarchical SRCU implementation.\n");
1893 if (exp_holdoff != DEFAULT_SRCU_EXP_HOLDOFF)
1894 pr_info("\tNon-default auto-expedite holdoff of %lu ns.\n", exp_holdoff);
1895 if (srcu_retry_check_delay != SRCU_DEFAULT_RETRY_CHECK_DELAY)
1896 pr_info("\tNon-default retry check delay of %lu us.\n", srcu_retry_check_delay);
1897 if (srcu_max_nodelay != SRCU_DEFAULT_MAX_NODELAY)
1898 pr_info("\tNon-default max no-delay of %lu.\n", srcu_max_nodelay);
1899 pr_info("\tMax phase no-delay instances is %lu.\n", srcu_max_nodelay_phase);
1900 return 0;
1901}
1902early_initcall(srcu_bootup_announce);
1903
1904void __init srcu_init(void)
1905{
1906 struct srcu_usage *sup;
1907
1908 /* Decide on srcu_struct-size strategy. */
1909 if (SRCU_SIZING_IS(SRCU_SIZING_AUTO)) {
1910 if (nr_cpu_ids >= big_cpu_lim) {
1911 convert_to_big = SRCU_SIZING_INIT; // Don't bother waiting for contention.
1912 pr_info("%s: Setting srcu_struct sizes to big.\n", __func__);
1913 } else {
1914 convert_to_big = SRCU_SIZING_NONE | SRCU_SIZING_CONTEND;
1915 pr_info("%s: Setting srcu_struct sizes based on contention.\n", __func__);
1916 }
1917 }
1918
1919 /*
1920 * Once that is set, call_srcu() can follow the normal path and
1921 * queue delayed work. This must follow RCU workqueues creation
1922 * and timers initialization.
1923 */
1924 srcu_init_done = true;
1925 while (!list_empty(&srcu_boot_list)) {
1926 sup = list_first_entry(&srcu_boot_list, struct srcu_usage,
1927 work.work.entry);
1928 list_del_init(&sup->work.work.entry);
1929 if (SRCU_SIZING_IS(SRCU_SIZING_INIT) &&
1930 sup->srcu_size_state == SRCU_SIZE_SMALL)
1931 sup->srcu_size_state = SRCU_SIZE_ALLOC;
1932 queue_work(rcu_gp_wq, &sup->work.work);
1933 }
1934}
1935
1936#ifdef CONFIG_MODULES
1937
1938/* Initialize any global-scope srcu_struct structures used by this module. */
1939static int srcu_module_coming(struct module *mod)
1940{
1941 int i;
1942 struct srcu_struct *ssp;
1943 struct srcu_struct **sspp = mod->srcu_struct_ptrs;
1944
1945 for (i = 0; i < mod->num_srcu_structs; i++) {
1946 ssp = *(sspp++);
1947 ssp->sda = alloc_percpu(struct srcu_data);
1948 if (WARN_ON_ONCE(!ssp->sda))
1949 return -ENOMEM;
1950 }
1951 return 0;
1952}
1953
1954/* Clean up any global-scope srcu_struct structures used by this module. */
1955static void srcu_module_going(struct module *mod)
1956{
1957 int i;
1958 struct srcu_struct *ssp;
1959 struct srcu_struct **sspp = mod->srcu_struct_ptrs;
1960
1961 for (i = 0; i < mod->num_srcu_structs; i++) {
1962 ssp = *(sspp++);
1963 if (!rcu_seq_state(smp_load_acquire(&ssp->srcu_sup->srcu_gp_seq_needed)) &&
1964 !WARN_ON_ONCE(!ssp->srcu_sup->sda_is_static))
1965 cleanup_srcu_struct(ssp);
1966 if (!WARN_ON(srcu_readers_active(ssp)))
1967 free_percpu(ssp->sda);
1968 }
1969}
1970
1971/* Handle one module, either coming or going. */
1972static int srcu_module_notify(struct notifier_block *self,
1973 unsigned long val, void *data)
1974{
1975 struct module *mod = data;
1976 int ret = 0;
1977
1978 switch (val) {
1979 case MODULE_STATE_COMING:
1980 ret = srcu_module_coming(mod);
1981 break;
1982 case MODULE_STATE_GOING:
1983 srcu_module_going(mod);
1984 break;
1985 default:
1986 break;
1987 }
1988 return ret;
1989}
1990
1991static struct notifier_block srcu_module_nb = {
1992 .notifier_call = srcu_module_notify,
1993 .priority = 0,
1994};
1995
1996static __init int init_srcu_module_notifier(void)
1997{
1998 int ret;
1999
2000 ret = register_module_notifier(&srcu_module_nb);
2001 if (ret)
2002 pr_warn("Failed to register srcu module notifier\n");
2003 return ret;
2004}
2005late_initcall(init_srcu_module_notifier);
2006
2007#endif /* #ifdef CONFIG_MODULES */