projects/linux·blob master · refs

2184 lines · 76.6 KiB

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