xref: /linux/kernel/rcu/tree.c (revision be602cde657ee43d23adbf309be6d700d0106dc9)
1 // SPDX-License-Identifier: GPL-2.0+
2 /*
3  * Read-Copy Update mechanism for mutual exclusion (tree-based version)
4  *
5  * Copyright IBM Corporation, 2008
6  *
7  * Authors: Dipankar Sarma <dipankar@in.ibm.com>
8  *	    Manfred Spraul <manfred@colorfullife.com>
9  *	    Paul E. McKenney <paulmck@linux.ibm.com>
10  *
11  * Based on the original work by Paul McKenney <paulmck@linux.ibm.com>
12  * and inputs from Rusty Russell, Andrea Arcangeli and Andi Kleen.
13  *
14  * For detailed explanation of Read-Copy Update mechanism see -
15  *	Documentation/RCU
16  */
17 
18 #define pr_fmt(fmt) "rcu: " fmt
19 
20 #include <linux/types.h>
21 #include <linux/kernel.h>
22 #include <linux/init.h>
23 #include <linux/spinlock.h>
24 #include <linux/smp.h>
25 #include <linux/rcupdate_wait.h>
26 #include <linux/interrupt.h>
27 #include <linux/sched.h>
28 #include <linux/sched/debug.h>
29 #include <linux/nmi.h>
30 #include <linux/atomic.h>
31 #include <linux/bitops.h>
32 #include <linux/export.h>
33 #include <linux/completion.h>
34 #include <linux/kmemleak.h>
35 #include <linux/moduleparam.h>
36 #include <linux/panic.h>
37 #include <linux/panic_notifier.h>
38 #include <linux/percpu.h>
39 #include <linux/notifier.h>
40 #include <linux/cpu.h>
41 #include <linux/mutex.h>
42 #include <linux/time.h>
43 #include <linux/kernel_stat.h>
44 #include <linux/wait.h>
45 #include <linux/kthread.h>
46 #include <uapi/linux/sched/types.h>
47 #include <linux/prefetch.h>
48 #include <linux/delay.h>
49 #include <linux/random.h>
50 #include <linux/trace_events.h>
51 #include <linux/suspend.h>
52 #include <linux/ftrace.h>
53 #include <linux/tick.h>
54 #include <linux/sysrq.h>
55 #include <linux/kprobes.h>
56 #include <linux/gfp.h>
57 #include <linux/oom.h>
58 #include <linux/smpboot.h>
59 #include <linux/jiffies.h>
60 #include <linux/slab.h>
61 #include <linux/sched/isolation.h>
62 #include <linux/sched/clock.h>
63 #include <linux/vmalloc.h>
64 #include <linux/mm.h>
65 #include <linux/kasan.h>
66 #include <linux/context_tracking.h>
67 #include "../time/tick-internal.h"
68 
69 #include "tree.h"
70 #include "rcu.h"
71 
72 #ifdef MODULE_PARAM_PREFIX
73 #undef MODULE_PARAM_PREFIX
74 #endif
75 #define MODULE_PARAM_PREFIX "rcutree."
76 
77 /* Data structures. */
78 static void rcu_sr_normal_gp_cleanup_work(struct work_struct *);
79 
80 static DEFINE_PER_CPU_SHARED_ALIGNED(struct rcu_data, rcu_data) = {
81 	.gpwrap = true,
82 };
83 static struct rcu_state rcu_state = {
84 	.level = { &rcu_state.node[0] },
85 	.gp_state = RCU_GP_IDLE,
86 	.gp_seq = (0UL - 300UL) << RCU_SEQ_CTR_SHIFT,
87 	.barrier_mutex = __MUTEX_INITIALIZER(rcu_state.barrier_mutex),
88 	.barrier_lock = __RAW_SPIN_LOCK_UNLOCKED(rcu_state.barrier_lock),
89 	.name = RCU_NAME,
90 	.abbr = RCU_ABBR,
91 	.exp_mutex = __MUTEX_INITIALIZER(rcu_state.exp_mutex),
92 	.exp_wake_mutex = __MUTEX_INITIALIZER(rcu_state.exp_wake_mutex),
93 	.ofl_lock = __ARCH_SPIN_LOCK_UNLOCKED,
94 	.srs_cleanup_work = __WORK_INITIALIZER(rcu_state.srs_cleanup_work,
95 		rcu_sr_normal_gp_cleanup_work),
96 	.srs_cleanups_pending = ATOMIC_INIT(0),
97 #ifdef CONFIG_RCU_NOCB_CPU
98 	.nocb_mutex = __MUTEX_INITIALIZER(rcu_state.nocb_mutex),
99 #endif
100 };
101 
102 /* Dump rcu_node combining tree at boot to verify correct setup. */
103 static bool dump_tree;
104 module_param(dump_tree, bool, 0444);
105 /* By default, use RCU_SOFTIRQ instead of rcuc kthreads. */
106 static bool use_softirq = !IS_ENABLED(CONFIG_PREEMPT_RT);
107 #ifndef CONFIG_PREEMPT_RT
108 module_param(use_softirq, bool, 0444);
109 #endif
110 /* Control rcu_node-tree auto-balancing at boot time. */
111 static bool rcu_fanout_exact;
112 module_param(rcu_fanout_exact, bool, 0444);
113 /* Increase (but not decrease) the RCU_FANOUT_LEAF at boot time. */
114 static int rcu_fanout_leaf = RCU_FANOUT_LEAF;
115 module_param(rcu_fanout_leaf, int, 0444);
116 int rcu_num_lvls __read_mostly = RCU_NUM_LVLS;
117 /* Number of rcu_nodes at specified level. */
118 int num_rcu_lvl[] = NUM_RCU_LVL_INIT;
119 int rcu_num_nodes __read_mostly = NUM_RCU_NODES; /* Total # rcu_nodes in use. */
120 
121 /*
122  * The rcu_scheduler_active variable is initialized to the value
123  * RCU_SCHEDULER_INACTIVE and transitions RCU_SCHEDULER_INIT just before the
124  * first task is spawned.  So when this variable is RCU_SCHEDULER_INACTIVE,
125  * RCU can assume that there is but one task, allowing RCU to (for example)
126  * optimize synchronize_rcu() to a simple barrier().  When this variable
127  * is RCU_SCHEDULER_INIT, RCU must actually do all the hard work required
128  * to detect real grace periods.  This variable is also used to suppress
129  * boot-time false positives from lockdep-RCU error checking.  Finally, it
130  * transitions from RCU_SCHEDULER_INIT to RCU_SCHEDULER_RUNNING after RCU
131  * is fully initialized, including all of its kthreads having been spawned.
132  */
133 int rcu_scheduler_active __read_mostly;
134 EXPORT_SYMBOL_GPL(rcu_scheduler_active);
135 
136 /*
137  * The rcu_scheduler_fully_active variable transitions from zero to one
138  * during the early_initcall() processing, which is after the scheduler
139  * is capable of creating new tasks.  So RCU processing (for example,
140  * creating tasks for RCU priority boosting) must be delayed until after
141  * rcu_scheduler_fully_active transitions from zero to one.  We also
142  * currently delay invocation of any RCU callbacks until after this point.
143  *
144  * It might later prove better for people registering RCU callbacks during
145  * early boot to take responsibility for these callbacks, but one step at
146  * a time.
147  */
148 static int rcu_scheduler_fully_active __read_mostly;
149 
150 static void rcu_report_qs_rnp(unsigned long mask, struct rcu_node *rnp,
151 			      unsigned long gps, unsigned long flags);
152 static struct task_struct *rcu_boost_task(struct rcu_node *rnp);
153 static void invoke_rcu_core(void);
154 static void rcu_report_exp_rdp(struct rcu_data *rdp);
155 static void sync_sched_exp_online_cleanup(int cpu);
156 static void check_cb_ovld_locked(struct rcu_data *rdp, struct rcu_node *rnp);
157 static bool rcu_rdp_is_offloaded(struct rcu_data *rdp);
158 static bool rcu_rdp_cpu_online(struct rcu_data *rdp);
159 static bool rcu_init_invoked(void);
160 static void rcu_cleanup_dead_rnp(struct rcu_node *rnp_leaf);
161 static void rcu_init_new_rnp(struct rcu_node *rnp_leaf);
162 
163 /*
164  * rcuc/rcub/rcuop kthread realtime priority. The "rcuop"
165  * real-time priority(enabling/disabling) is controlled by
166  * the extra CONFIG_RCU_NOCB_CPU_CB_BOOST configuration.
167  */
168 static int kthread_prio = IS_ENABLED(CONFIG_RCU_BOOST) ? 1 : 0;
169 module_param(kthread_prio, int, 0444);
170 
171 /* Delay in jiffies for grace-period initialization delays, debug only. */
172 
173 static int gp_preinit_delay;
174 module_param(gp_preinit_delay, int, 0444);
175 static int gp_init_delay;
176 module_param(gp_init_delay, int, 0444);
177 static int gp_cleanup_delay;
178 module_param(gp_cleanup_delay, int, 0444);
179 static int nohz_full_patience_delay;
180 module_param(nohz_full_patience_delay, int, 0444);
181 static int nohz_full_patience_delay_jiffies;
182 
183 // Add delay to rcu_read_unlock() for strict grace periods.
184 static int rcu_unlock_delay;
185 #ifdef CONFIG_RCU_STRICT_GRACE_PERIOD
186 module_param(rcu_unlock_delay, int, 0444);
187 #endif
188 
189 /*
190  * This rcu parameter is runtime-read-only. It reflects
191  * a minimum allowed number of objects which can be cached
192  * per-CPU. Object size is equal to one page. This value
193  * can be changed at boot time.
194  */
195 static int rcu_min_cached_objs = 5;
196 module_param(rcu_min_cached_objs, int, 0444);
197 
198 // A page shrinker can ask for pages to be freed to make them
199 // available for other parts of the system. This usually happens
200 // under low memory conditions, and in that case we should also
201 // defer page-cache filling for a short time period.
202 //
203 // The default value is 5 seconds, which is long enough to reduce
204 // interference with the shrinker while it asks other systems to
205 // drain their caches.
206 static int rcu_delay_page_cache_fill_msec = 5000;
207 module_param(rcu_delay_page_cache_fill_msec, int, 0444);
208 
209 /* Retrieve RCU kthreads priority for rcutorture */
210 int rcu_get_gp_kthreads_prio(void)
211 {
212 	return kthread_prio;
213 }
214 EXPORT_SYMBOL_GPL(rcu_get_gp_kthreads_prio);
215 
216 /*
217  * Number of grace periods between delays, normalized by the duration of
218  * the delay.  The longer the delay, the more the grace periods between
219  * each delay.  The reason for this normalization is that it means that,
220  * for non-zero delays, the overall slowdown of grace periods is constant
221  * regardless of the duration of the delay.  This arrangement balances
222  * the need for long delays to increase some race probabilities with the
223  * need for fast grace periods to increase other race probabilities.
224  */
225 #define PER_RCU_NODE_PERIOD 3	/* Number of grace periods between delays for debugging. */
226 
227 /*
228  * Return true if an RCU grace period is in progress.  The READ_ONCE()s
229  * permit this function to be invoked without holding the root rcu_node
230  * structure's ->lock, but of course results can be subject to change.
231  */
232 static int rcu_gp_in_progress(void)
233 {
234 	return rcu_seq_state(rcu_seq_current(&rcu_state.gp_seq));
235 }
236 
237 /*
238  * Return the number of callbacks queued on the specified CPU.
239  * Handles both the nocbs and normal cases.
240  */
241 static long rcu_get_n_cbs_cpu(int cpu)
242 {
243 	struct rcu_data *rdp = per_cpu_ptr(&rcu_data, cpu);
244 
245 	if (rcu_segcblist_is_enabled(&rdp->cblist))
246 		return rcu_segcblist_n_cbs(&rdp->cblist);
247 	return 0;
248 }
249 
250 /**
251  * rcu_softirq_qs - Provide a set of RCU quiescent states in softirq processing
252  *
253  * Mark a quiescent state for RCU, Tasks RCU, and Tasks Trace RCU.
254  * This is a special-purpose function to be used in the softirq
255  * infrastructure and perhaps the occasional long-running softirq
256  * handler.
257  *
258  * Note that from RCU's viewpoint, a call to rcu_softirq_qs() is
259  * equivalent to momentarily completely enabling preemption.  For
260  * example, given this code::
261  *
262  *	local_bh_disable();
263  *	do_something();
264  *	rcu_softirq_qs();  // A
265  *	do_something_else();
266  *	local_bh_enable();  // B
267  *
268  * A call to synchronize_rcu() that began concurrently with the
269  * call to do_something() would be guaranteed to wait only until
270  * execution reached statement A.  Without that rcu_softirq_qs(),
271  * that same synchronize_rcu() would instead be guaranteed to wait
272  * until execution reached statement B.
273  */
274 void rcu_softirq_qs(void)
275 {
276 	RCU_LOCKDEP_WARN(lock_is_held(&rcu_bh_lock_map) ||
277 			 lock_is_held(&rcu_lock_map) ||
278 			 lock_is_held(&rcu_sched_lock_map),
279 			 "Illegal rcu_softirq_qs() in RCU read-side critical section");
280 	rcu_qs();
281 	rcu_preempt_deferred_qs(current);
282 	rcu_tasks_qs(current, false);
283 }
284 
285 /*
286  * Reset the current CPU's RCU_WATCHING counter to indicate that the
287  * newly onlined CPU is no longer in an extended quiescent state.
288  * This will either leave the counter unchanged, or increment it
289  * to the next non-quiescent value.
290  *
291  * The non-atomic test/increment sequence works because the upper bits
292  * of the ->state variable are manipulated only by the corresponding CPU,
293  * or when the corresponding CPU is offline.
294  */
295 static void rcu_watching_online(void)
296 {
297 	if (ct_rcu_watching() & CT_RCU_WATCHING)
298 		return;
299 	ct_state_inc(CT_RCU_WATCHING);
300 }
301 
302 /*
303  * Return true if the snapshot returned from ct_rcu_watching()
304  * indicates that RCU is in an extended quiescent state.
305  */
306 static bool rcu_watching_snap_in_eqs(int snap)
307 {
308 	return !(snap & CT_RCU_WATCHING);
309 }
310 
311 /**
312  * rcu_watching_snap_stopped_since() - Has RCU stopped watching a given CPU
313  * since the specified @snap?
314  *
315  * @rdp: The rcu_data corresponding to the CPU for which to check EQS.
316  * @snap: rcu_watching snapshot taken when the CPU wasn't in an EQS.
317  *
318  * Returns true if the CPU corresponding to @rdp has spent some time in an
319  * extended quiescent state since @snap. Note that this doesn't check if it
320  * /still/ is in an EQS, just that it went through one since @snap.
321  *
322  * This is meant to be used in a loop waiting for a CPU to go through an EQS.
323  */
324 static bool rcu_watching_snap_stopped_since(struct rcu_data *rdp, int snap)
325 {
326 	/*
327 	 * The first failing snapshot is already ordered against the accesses
328 	 * performed by the remote CPU after it exits idle.
329 	 *
330 	 * The second snapshot therefore only needs to order against accesses
331 	 * performed by the remote CPU prior to entering idle and therefore can
332 	 * rely solely on acquire semantics.
333 	 */
334 	if (WARN_ON_ONCE(rcu_watching_snap_in_eqs(snap)))
335 		return true;
336 
337 	return snap != ct_rcu_watching_cpu_acquire(rdp->cpu);
338 }
339 
340 /*
341  * Return true if the referenced integer is zero while the specified
342  * CPU remains within a single extended quiescent state.
343  */
344 bool rcu_watching_zero_in_eqs(int cpu, int *vp)
345 {
346 	int snap;
347 
348 	// If not quiescent, force back to earlier extended quiescent state.
349 	snap = ct_rcu_watching_cpu(cpu) & ~CT_RCU_WATCHING;
350 	smp_rmb(); // Order CT state and *vp reads.
351 	if (READ_ONCE(*vp))
352 		return false;  // Non-zero, so report failure;
353 	smp_rmb(); // Order *vp read and CT state re-read.
354 
355 	// If still in the same extended quiescent state, we are good!
356 	return snap == ct_rcu_watching_cpu(cpu);
357 }
358 
359 /*
360  * Let the RCU core know that this CPU has gone through the scheduler,
361  * which is a quiescent state.  This is called when the need for a
362  * quiescent state is urgent, so we burn an atomic operation and full
363  * memory barriers to let the RCU core know about it, regardless of what
364  * this CPU might (or might not) do in the near future.
365  *
366  * We inform the RCU core by emulating a zero-duration dyntick-idle period.
367  *
368  * The caller must have disabled interrupts and must not be idle.
369  */
370 notrace void rcu_momentary_eqs(void)
371 {
372 	int seq;
373 
374 	raw_cpu_write(rcu_data.rcu_need_heavy_qs, false);
375 	seq = ct_state_inc(2 * CT_RCU_WATCHING);
376 	/* It is illegal to call this from idle state. */
377 	WARN_ON_ONCE(!(seq & CT_RCU_WATCHING));
378 	rcu_preempt_deferred_qs(current);
379 }
380 EXPORT_SYMBOL_GPL(rcu_momentary_eqs);
381 
382 /**
383  * rcu_is_cpu_rrupt_from_idle - see if 'interrupted' from idle
384  *
385  * If the current CPU is idle and running at a first-level (not nested)
386  * interrupt, or directly, from idle, return true.
387  *
388  * The caller must have at least disabled IRQs.
389  */
390 static int rcu_is_cpu_rrupt_from_idle(void)
391 {
392 	long nesting;
393 
394 	/*
395 	 * Usually called from the tick; but also used from smp_function_call()
396 	 * for expedited grace periods. This latter can result in running from
397 	 * the idle task, instead of an actual IPI.
398 	 */
399 	lockdep_assert_irqs_disabled();
400 
401 	/* Check for counter underflows */
402 	RCU_LOCKDEP_WARN(ct_nesting() < 0,
403 			 "RCU nesting counter underflow!");
404 	RCU_LOCKDEP_WARN(ct_nmi_nesting() <= 0,
405 			 "RCU nmi_nesting counter underflow/zero!");
406 
407 	/* Are we at first interrupt nesting level? */
408 	nesting = ct_nmi_nesting();
409 	if (nesting > 1)
410 		return false;
411 
412 	/*
413 	 * If we're not in an interrupt, we must be in the idle task!
414 	 */
415 	WARN_ON_ONCE(!nesting && !is_idle_task(current));
416 
417 	/* Does CPU appear to be idle from an RCU standpoint? */
418 	return ct_nesting() == 0;
419 }
420 
421 #define DEFAULT_RCU_BLIMIT (IS_ENABLED(CONFIG_RCU_STRICT_GRACE_PERIOD) ? 1000 : 10)
422 				// Maximum callbacks per rcu_do_batch ...
423 #define DEFAULT_MAX_RCU_BLIMIT 10000 // ... even during callback flood.
424 static long blimit = DEFAULT_RCU_BLIMIT;
425 #define DEFAULT_RCU_QHIMARK 10000 // If this many pending, ignore blimit.
426 static long qhimark = DEFAULT_RCU_QHIMARK;
427 #define DEFAULT_RCU_QLOMARK 100   // Once only this many pending, use blimit.
428 static long qlowmark = DEFAULT_RCU_QLOMARK;
429 #define DEFAULT_RCU_QOVLD_MULT 2
430 #define DEFAULT_RCU_QOVLD (DEFAULT_RCU_QOVLD_MULT * DEFAULT_RCU_QHIMARK)
431 static long qovld = DEFAULT_RCU_QOVLD; // If this many pending, hammer QS.
432 static long qovld_calc = -1;	  // No pre-initialization lock acquisitions!
433 
434 module_param(blimit, long, 0444);
435 module_param(qhimark, long, 0444);
436 module_param(qlowmark, long, 0444);
437 module_param(qovld, long, 0444);
438 
439 static ulong jiffies_till_first_fqs = IS_ENABLED(CONFIG_RCU_STRICT_GRACE_PERIOD) ? 0 : ULONG_MAX;
440 static ulong jiffies_till_next_fqs = ULONG_MAX;
441 static bool rcu_kick_kthreads;
442 static int rcu_divisor = 7;
443 module_param(rcu_divisor, int, 0644);
444 
445 /* Force an exit from rcu_do_batch() after 3 milliseconds. */
446 static long rcu_resched_ns = 3 * NSEC_PER_MSEC;
447 module_param(rcu_resched_ns, long, 0644);
448 
449 /*
450  * How long the grace period must be before we start recruiting
451  * quiescent-state help from rcu_note_context_switch().
452  */
453 static ulong jiffies_till_sched_qs = ULONG_MAX;
454 module_param(jiffies_till_sched_qs, ulong, 0444);
455 static ulong jiffies_to_sched_qs; /* See adjust_jiffies_till_sched_qs(). */
456 module_param(jiffies_to_sched_qs, ulong, 0444); /* Display only! */
457 
458 /*
459  * Make sure that we give the grace-period kthread time to detect any
460  * idle CPUs before taking active measures to force quiescent states.
461  * However, don't go below 100 milliseconds, adjusted upwards for really
462  * large systems.
463  */
464 static void adjust_jiffies_till_sched_qs(void)
465 {
466 	unsigned long j;
467 
468 	/* If jiffies_till_sched_qs was specified, respect the request. */
469 	if (jiffies_till_sched_qs != ULONG_MAX) {
470 		WRITE_ONCE(jiffies_to_sched_qs, jiffies_till_sched_qs);
471 		return;
472 	}
473 	/* Otherwise, set to third fqs scan, but bound below on large system. */
474 	j = READ_ONCE(jiffies_till_first_fqs) +
475 		      2 * READ_ONCE(jiffies_till_next_fqs);
476 	if (j < HZ / 10 + nr_cpu_ids / RCU_JIFFIES_FQS_DIV)
477 		j = HZ / 10 + nr_cpu_ids / RCU_JIFFIES_FQS_DIV;
478 	pr_info("RCU calculated value of scheduler-enlistment delay is %ld jiffies.\n", j);
479 	WRITE_ONCE(jiffies_to_sched_qs, j);
480 }
481 
482 static int param_set_first_fqs_jiffies(const char *val, const struct kernel_param *kp)
483 {
484 	ulong j;
485 	int ret = kstrtoul(val, 0, &j);
486 
487 	if (!ret) {
488 		WRITE_ONCE(*(ulong *)kp->arg, (j > HZ) ? HZ : j);
489 		adjust_jiffies_till_sched_qs();
490 	}
491 	return ret;
492 }
493 
494 static int param_set_next_fqs_jiffies(const char *val, const struct kernel_param *kp)
495 {
496 	ulong j;
497 	int ret = kstrtoul(val, 0, &j);
498 
499 	if (!ret) {
500 		WRITE_ONCE(*(ulong *)kp->arg, (j > HZ) ? HZ : (j ?: 1));
501 		adjust_jiffies_till_sched_qs();
502 	}
503 	return ret;
504 }
505 
506 static const struct kernel_param_ops first_fqs_jiffies_ops = {
507 	.set = param_set_first_fqs_jiffies,
508 	.get = param_get_ulong,
509 };
510 
511 static const struct kernel_param_ops next_fqs_jiffies_ops = {
512 	.set = param_set_next_fqs_jiffies,
513 	.get = param_get_ulong,
514 };
515 
516 module_param_cb(jiffies_till_first_fqs, &first_fqs_jiffies_ops, &jiffies_till_first_fqs, 0644);
517 module_param_cb(jiffies_till_next_fqs, &next_fqs_jiffies_ops, &jiffies_till_next_fqs, 0644);
518 module_param(rcu_kick_kthreads, bool, 0644);
519 
520 static void force_qs_rnp(int (*f)(struct rcu_data *rdp));
521 static int rcu_pending(int user);
522 
523 /*
524  * Return the number of RCU GPs completed thus far for debug & stats.
525  */
526 unsigned long rcu_get_gp_seq(void)
527 {
528 	return READ_ONCE(rcu_state.gp_seq);
529 }
530 EXPORT_SYMBOL_GPL(rcu_get_gp_seq);
531 
532 /*
533  * Return the number of RCU expedited batches completed thus far for
534  * debug & stats.  Odd numbers mean that a batch is in progress, even
535  * numbers mean idle.  The value returned will thus be roughly double
536  * the cumulative batches since boot.
537  */
538 unsigned long rcu_exp_batches_completed(void)
539 {
540 	return rcu_state.expedited_sequence;
541 }
542 EXPORT_SYMBOL_GPL(rcu_exp_batches_completed);
543 
544 /*
545  * Return the root node of the rcu_state structure.
546  */
547 static struct rcu_node *rcu_get_root(void)
548 {
549 	return &rcu_state.node[0];
550 }
551 
552 /*
553  * Send along grace-period-related data for rcutorture diagnostics.
554  */
555 void rcutorture_get_gp_data(int *flags, unsigned long *gp_seq)
556 {
557 	*flags = READ_ONCE(rcu_state.gp_flags);
558 	*gp_seq = rcu_seq_current(&rcu_state.gp_seq);
559 }
560 EXPORT_SYMBOL_GPL(rcutorture_get_gp_data);
561 
562 #if defined(CONFIG_NO_HZ_FULL) && (!defined(CONFIG_GENERIC_ENTRY) || !defined(CONFIG_KVM_XFER_TO_GUEST_WORK))
563 /*
564  * An empty function that will trigger a reschedule on
565  * IRQ tail once IRQs get re-enabled on userspace/guest resume.
566  */
567 static void late_wakeup_func(struct irq_work *work)
568 {
569 }
570 
571 static DEFINE_PER_CPU(struct irq_work, late_wakeup_work) =
572 	IRQ_WORK_INIT(late_wakeup_func);
573 
574 /*
575  * If either:
576  *
577  * 1) the task is about to enter in guest mode and $ARCH doesn't support KVM generic work
578  * 2) the task is about to enter in user mode and $ARCH doesn't support generic entry.
579  *
580  * In these cases the late RCU wake ups aren't supported in the resched loops and our
581  * last resort is to fire a local irq_work that will trigger a reschedule once IRQs
582  * get re-enabled again.
583  */
584 noinstr void rcu_irq_work_resched(void)
585 {
586 	struct rcu_data *rdp = this_cpu_ptr(&rcu_data);
587 
588 	if (IS_ENABLED(CONFIG_GENERIC_ENTRY) && !(current->flags & PF_VCPU))
589 		return;
590 
591 	if (IS_ENABLED(CONFIG_KVM_XFER_TO_GUEST_WORK) && (current->flags & PF_VCPU))
592 		return;
593 
594 	instrumentation_begin();
595 	if (do_nocb_deferred_wakeup(rdp) && need_resched()) {
596 		irq_work_queue(this_cpu_ptr(&late_wakeup_work));
597 	}
598 	instrumentation_end();
599 }
600 #endif /* #if defined(CONFIG_NO_HZ_FULL) && (!defined(CONFIG_GENERIC_ENTRY) || !defined(CONFIG_KVM_XFER_TO_GUEST_WORK)) */
601 
602 #ifdef CONFIG_PROVE_RCU
603 /**
604  * rcu_irq_exit_check_preempt - Validate that scheduling is possible
605  */
606 void rcu_irq_exit_check_preempt(void)
607 {
608 	lockdep_assert_irqs_disabled();
609 
610 	RCU_LOCKDEP_WARN(ct_nesting() <= 0,
611 			 "RCU nesting counter underflow/zero!");
612 	RCU_LOCKDEP_WARN(ct_nmi_nesting() !=
613 			 CT_NESTING_IRQ_NONIDLE,
614 			 "Bad RCU  nmi_nesting counter\n");
615 	RCU_LOCKDEP_WARN(!rcu_is_watching_curr_cpu(),
616 			 "RCU in extended quiescent state!");
617 }
618 #endif /* #ifdef CONFIG_PROVE_RCU */
619 
620 #ifdef CONFIG_NO_HZ_FULL
621 /**
622  * __rcu_irq_enter_check_tick - Enable scheduler tick on CPU if RCU needs it.
623  *
624  * The scheduler tick is not normally enabled when CPUs enter the kernel
625  * from nohz_full userspace execution.  After all, nohz_full userspace
626  * execution is an RCU quiescent state and the time executing in the kernel
627  * is quite short.  Except of course when it isn't.  And it is not hard to
628  * cause a large system to spend tens of seconds or even minutes looping
629  * in the kernel, which can cause a number of problems, include RCU CPU
630  * stall warnings.
631  *
632  * Therefore, if a nohz_full CPU fails to report a quiescent state
633  * in a timely manner, the RCU grace-period kthread sets that CPU's
634  * ->rcu_urgent_qs flag with the expectation that the next interrupt or
635  * exception will invoke this function, which will turn on the scheduler
636  * tick, which will enable RCU to detect that CPU's quiescent states,
637  * for example, due to cond_resched() calls in CONFIG_PREEMPT=n kernels.
638  * The tick will be disabled once a quiescent state is reported for
639  * this CPU.
640  *
641  * Of course, in carefully tuned systems, there might never be an
642  * interrupt or exception.  In that case, the RCU grace-period kthread
643  * will eventually cause one to happen.  However, in less carefully
644  * controlled environments, this function allows RCU to get what it
645  * needs without creating otherwise useless interruptions.
646  */
647 void __rcu_irq_enter_check_tick(void)
648 {
649 	struct rcu_data *rdp = this_cpu_ptr(&rcu_data);
650 
651 	// If we're here from NMI there's nothing to do.
652 	if (in_nmi())
653 		return;
654 
655 	RCU_LOCKDEP_WARN(!rcu_is_watching_curr_cpu(),
656 			 "Illegal rcu_irq_enter_check_tick() from extended quiescent state");
657 
658 	if (!tick_nohz_full_cpu(rdp->cpu) ||
659 	    !READ_ONCE(rdp->rcu_urgent_qs) ||
660 	    READ_ONCE(rdp->rcu_forced_tick)) {
661 		// RCU doesn't need nohz_full help from this CPU, or it is
662 		// already getting that help.
663 		return;
664 	}
665 
666 	// We get here only when not in an extended quiescent state and
667 	// from interrupts (as opposed to NMIs).  Therefore, (1) RCU is
668 	// already watching and (2) The fact that we are in an interrupt
669 	// handler and that the rcu_node lock is an irq-disabled lock
670 	// prevents self-deadlock.  So we can safely recheck under the lock.
671 	// Note that the nohz_full state currently cannot change.
672 	raw_spin_lock_rcu_node(rdp->mynode);
673 	if (READ_ONCE(rdp->rcu_urgent_qs) && !rdp->rcu_forced_tick) {
674 		// A nohz_full CPU is in the kernel and RCU needs a
675 		// quiescent state.  Turn on the tick!
676 		WRITE_ONCE(rdp->rcu_forced_tick, true);
677 		tick_dep_set_cpu(rdp->cpu, TICK_DEP_BIT_RCU);
678 	}
679 	raw_spin_unlock_rcu_node(rdp->mynode);
680 }
681 NOKPROBE_SYMBOL(__rcu_irq_enter_check_tick);
682 #endif /* CONFIG_NO_HZ_FULL */
683 
684 /*
685  * Check to see if any future non-offloaded RCU-related work will need
686  * to be done by the current CPU, even if none need be done immediately,
687  * returning 1 if so.  This function is part of the RCU implementation;
688  * it is -not- an exported member of the RCU API.  This is used by
689  * the idle-entry code to figure out whether it is safe to disable the
690  * scheduler-clock interrupt.
691  *
692  * Just check whether or not this CPU has non-offloaded RCU callbacks
693  * queued.
694  */
695 int rcu_needs_cpu(void)
696 {
697 	return !rcu_segcblist_empty(&this_cpu_ptr(&rcu_data)->cblist) &&
698 		!rcu_rdp_is_offloaded(this_cpu_ptr(&rcu_data));
699 }
700 
701 /*
702  * If any sort of urgency was applied to the current CPU (for example,
703  * the scheduler-clock interrupt was enabled on a nohz_full CPU) in order
704  * to get to a quiescent state, disable it.
705  */
706 static void rcu_disable_urgency_upon_qs(struct rcu_data *rdp)
707 {
708 	raw_lockdep_assert_held_rcu_node(rdp->mynode);
709 	WRITE_ONCE(rdp->rcu_urgent_qs, false);
710 	WRITE_ONCE(rdp->rcu_need_heavy_qs, false);
711 	if (tick_nohz_full_cpu(rdp->cpu) && rdp->rcu_forced_tick) {
712 		tick_dep_clear_cpu(rdp->cpu, TICK_DEP_BIT_RCU);
713 		WRITE_ONCE(rdp->rcu_forced_tick, false);
714 	}
715 }
716 
717 /**
718  * rcu_is_watching - RCU read-side critical sections permitted on current CPU?
719  *
720  * Return @true if RCU is watching the running CPU and @false otherwise.
721  * An @true return means that this CPU can safely enter RCU read-side
722  * critical sections.
723  *
724  * Although calls to rcu_is_watching() from most parts of the kernel
725  * will return @true, there are important exceptions.  For example, if the
726  * current CPU is deep within its idle loop, in kernel entry/exit code,
727  * or offline, rcu_is_watching() will return @false.
728  *
729  * Make notrace because it can be called by the internal functions of
730  * ftrace, and making this notrace removes unnecessary recursion calls.
731  */
732 notrace bool rcu_is_watching(void)
733 {
734 	bool ret;
735 
736 	preempt_disable_notrace();
737 	ret = rcu_is_watching_curr_cpu();
738 	preempt_enable_notrace();
739 	return ret;
740 }
741 EXPORT_SYMBOL_GPL(rcu_is_watching);
742 
743 /*
744  * If a holdout task is actually running, request an urgent quiescent
745  * state from its CPU.  This is unsynchronized, so migrations can cause
746  * the request to go to the wrong CPU.  Which is OK, all that will happen
747  * is that the CPU's next context switch will be a bit slower and next
748  * time around this task will generate another request.
749  */
750 void rcu_request_urgent_qs_task(struct task_struct *t)
751 {
752 	int cpu;
753 
754 	barrier();
755 	cpu = task_cpu(t);
756 	if (!task_curr(t))
757 		return; /* This task is not running on that CPU. */
758 	smp_store_release(per_cpu_ptr(&rcu_data.rcu_urgent_qs, cpu), true);
759 }
760 
761 /*
762  * When trying to report a quiescent state on behalf of some other CPU,
763  * it is our responsibility to check for and handle potential overflow
764  * of the rcu_node ->gp_seq counter with respect to the rcu_data counters.
765  * After all, the CPU might be in deep idle state, and thus executing no
766  * code whatsoever.
767  */
768 static void rcu_gpnum_ovf(struct rcu_node *rnp, struct rcu_data *rdp)
769 {
770 	raw_lockdep_assert_held_rcu_node(rnp);
771 	if (ULONG_CMP_LT(rcu_seq_current(&rdp->gp_seq) + ULONG_MAX / 4,
772 			 rnp->gp_seq))
773 		WRITE_ONCE(rdp->gpwrap, true);
774 	if (ULONG_CMP_LT(rdp->rcu_iw_gp_seq + ULONG_MAX / 4, rnp->gp_seq))
775 		rdp->rcu_iw_gp_seq = rnp->gp_seq + ULONG_MAX / 4;
776 }
777 
778 /*
779  * Snapshot the specified CPU's RCU_WATCHING counter so that we can later
780  * credit them with an implicit quiescent state.  Return 1 if this CPU
781  * is in dynticks idle mode, which is an extended quiescent state.
782  */
783 static int rcu_watching_snap_save(struct rcu_data *rdp)
784 {
785 	/*
786 	 * Full ordering between remote CPU's post idle accesses and updater's
787 	 * accesses prior to current GP (and also the started GP sequence number)
788 	 * is enforced by rcu_seq_start() implicit barrier and even further by
789 	 * smp_mb__after_unlock_lock() barriers chained all the way throughout the
790 	 * rnp locking tree since rcu_gp_init() and up to the current leaf rnp
791 	 * locking.
792 	 *
793 	 * Ordering between remote CPU's pre idle accesses and post grace period
794 	 * updater's accesses is enforced by the below acquire semantic.
795 	 */
796 	rdp->watching_snap = ct_rcu_watching_cpu_acquire(rdp->cpu);
797 	if (rcu_watching_snap_in_eqs(rdp->watching_snap)) {
798 		trace_rcu_fqs(rcu_state.name, rdp->gp_seq, rdp->cpu, TPS("dti"));
799 		rcu_gpnum_ovf(rdp->mynode, rdp);
800 		return 1;
801 	}
802 	return 0;
803 }
804 
805 /*
806  * Returns positive if the specified CPU has passed through a quiescent state
807  * by virtue of being in or having passed through an dynticks idle state since
808  * the last call to rcu_watching_snap_save() for this same CPU, or by
809  * virtue of having been offline.
810  *
811  * Returns negative if the specified CPU needs a force resched.
812  *
813  * Returns zero otherwise.
814  */
815 static int rcu_watching_snap_recheck(struct rcu_data *rdp)
816 {
817 	unsigned long jtsq;
818 	int ret = 0;
819 	struct rcu_node *rnp = rdp->mynode;
820 
821 	/*
822 	 * If the CPU passed through or entered a dynticks idle phase with
823 	 * no active irq/NMI handlers, then we can safely pretend that the CPU
824 	 * already acknowledged the request to pass through a quiescent
825 	 * state.  Either way, that CPU cannot possibly be in an RCU
826 	 * read-side critical section that started before the beginning
827 	 * of the current RCU grace period.
828 	 */
829 	if (rcu_watching_snap_stopped_since(rdp, rdp->watching_snap)) {
830 		trace_rcu_fqs(rcu_state.name, rdp->gp_seq, rdp->cpu, TPS("dti"));
831 		rcu_gpnum_ovf(rnp, rdp);
832 		return 1;
833 	}
834 
835 	/*
836 	 * Complain if a CPU that is considered to be offline from RCU's
837 	 * perspective has not yet reported a quiescent state.  After all,
838 	 * the offline CPU should have reported a quiescent state during
839 	 * the CPU-offline process, or, failing that, by rcu_gp_init()
840 	 * if it ran concurrently with either the CPU going offline or the
841 	 * last task on a leaf rcu_node structure exiting its RCU read-side
842 	 * critical section while all CPUs corresponding to that structure
843 	 * are offline.  This added warning detects bugs in any of these
844 	 * code paths.
845 	 *
846 	 * The rcu_node structure's ->lock is held here, which excludes
847 	 * the relevant portions the CPU-hotplug code, the grace-period
848 	 * initialization code, and the rcu_read_unlock() code paths.
849 	 *
850 	 * For more detail, please refer to the "Hotplug CPU" section
851 	 * of RCU's Requirements documentation.
852 	 */
853 	if (WARN_ON_ONCE(!rcu_rdp_cpu_online(rdp))) {
854 		struct rcu_node *rnp1;
855 
856 		pr_info("%s: grp: %d-%d level: %d ->gp_seq %ld ->completedqs %ld\n",
857 			__func__, rnp->grplo, rnp->grphi, rnp->level,
858 			(long)rnp->gp_seq, (long)rnp->completedqs);
859 		for (rnp1 = rnp; rnp1; rnp1 = rnp1->parent)
860 			pr_info("%s: %d:%d ->qsmask %#lx ->qsmaskinit %#lx ->qsmaskinitnext %#lx ->rcu_gp_init_mask %#lx\n",
861 				__func__, rnp1->grplo, rnp1->grphi, rnp1->qsmask, rnp1->qsmaskinit, rnp1->qsmaskinitnext, rnp1->rcu_gp_init_mask);
862 		pr_info("%s %d: %c online: %ld(%d) offline: %ld(%d)\n",
863 			__func__, rdp->cpu, ".o"[rcu_rdp_cpu_online(rdp)],
864 			(long)rdp->rcu_onl_gp_seq, rdp->rcu_onl_gp_state,
865 			(long)rdp->rcu_ofl_gp_seq, rdp->rcu_ofl_gp_state);
866 		return 1; /* Break things loose after complaining. */
867 	}
868 
869 	/*
870 	 * A CPU running for an extended time within the kernel can
871 	 * delay RCU grace periods: (1) At age jiffies_to_sched_qs,
872 	 * set .rcu_urgent_qs, (2) At age 2*jiffies_to_sched_qs, set
873 	 * both .rcu_need_heavy_qs and .rcu_urgent_qs.  Note that the
874 	 * unsynchronized assignments to the per-CPU rcu_need_heavy_qs
875 	 * variable are safe because the assignments are repeated if this
876 	 * CPU failed to pass through a quiescent state.  This code
877 	 * also checks .jiffies_resched in case jiffies_to_sched_qs
878 	 * is set way high.
879 	 */
880 	jtsq = READ_ONCE(jiffies_to_sched_qs);
881 	if (!READ_ONCE(rdp->rcu_need_heavy_qs) &&
882 	    (time_after(jiffies, rcu_state.gp_start + jtsq * 2) ||
883 	     time_after(jiffies, rcu_state.jiffies_resched) ||
884 	     rcu_state.cbovld)) {
885 		WRITE_ONCE(rdp->rcu_need_heavy_qs, true);
886 		/* Store rcu_need_heavy_qs before rcu_urgent_qs. */
887 		smp_store_release(&rdp->rcu_urgent_qs, true);
888 	} else if (time_after(jiffies, rcu_state.gp_start + jtsq)) {
889 		WRITE_ONCE(rdp->rcu_urgent_qs, true);
890 	}
891 
892 	/*
893 	 * NO_HZ_FULL CPUs can run in-kernel without rcu_sched_clock_irq!
894 	 * The above code handles this, but only for straight cond_resched().
895 	 * And some in-kernel loops check need_resched() before calling
896 	 * cond_resched(), which defeats the above code for CPUs that are
897 	 * running in-kernel with scheduling-clock interrupts disabled.
898 	 * So hit them over the head with the resched_cpu() hammer!
899 	 */
900 	if (tick_nohz_full_cpu(rdp->cpu) &&
901 	    (time_after(jiffies, READ_ONCE(rdp->last_fqs_resched) + jtsq * 3) ||
902 	     rcu_state.cbovld)) {
903 		WRITE_ONCE(rdp->rcu_urgent_qs, true);
904 		WRITE_ONCE(rdp->last_fqs_resched, jiffies);
905 		ret = -1;
906 	}
907 
908 	/*
909 	 * If more than halfway to RCU CPU stall-warning time, invoke
910 	 * resched_cpu() more frequently to try to loosen things up a bit.
911 	 * Also check to see if the CPU is getting hammered with interrupts,
912 	 * but only once per grace period, just to keep the IPIs down to
913 	 * a dull roar.
914 	 */
915 	if (time_after(jiffies, rcu_state.jiffies_resched)) {
916 		if (time_after(jiffies,
917 			       READ_ONCE(rdp->last_fqs_resched) + jtsq)) {
918 			WRITE_ONCE(rdp->last_fqs_resched, jiffies);
919 			ret = -1;
920 		}
921 		if (IS_ENABLED(CONFIG_IRQ_WORK) &&
922 		    !rdp->rcu_iw_pending && rdp->rcu_iw_gp_seq != rnp->gp_seq &&
923 		    (rnp->ffmask & rdp->grpmask)) {
924 			rdp->rcu_iw_pending = true;
925 			rdp->rcu_iw_gp_seq = rnp->gp_seq;
926 			irq_work_queue_on(&rdp->rcu_iw, rdp->cpu);
927 		}
928 
929 		if (rcu_cpu_stall_cputime && rdp->snap_record.gp_seq != rdp->gp_seq) {
930 			int cpu = rdp->cpu;
931 			struct rcu_snap_record *rsrp;
932 			struct kernel_cpustat *kcsp;
933 
934 			kcsp = &kcpustat_cpu(cpu);
935 
936 			rsrp = &rdp->snap_record;
937 			rsrp->cputime_irq     = kcpustat_field(kcsp, CPUTIME_IRQ, cpu);
938 			rsrp->cputime_softirq = kcpustat_field(kcsp, CPUTIME_SOFTIRQ, cpu);
939 			rsrp->cputime_system  = kcpustat_field(kcsp, CPUTIME_SYSTEM, cpu);
940 			rsrp->nr_hardirqs = kstat_cpu_irqs_sum(rdp->cpu);
941 			rsrp->nr_softirqs = kstat_cpu_softirqs_sum(rdp->cpu);
942 			rsrp->nr_csw = nr_context_switches_cpu(rdp->cpu);
943 			rsrp->jiffies = jiffies;
944 			rsrp->gp_seq = rdp->gp_seq;
945 		}
946 	}
947 
948 	return ret;
949 }
950 
951 /* Trace-event wrapper function for trace_rcu_future_grace_period.  */
952 static void trace_rcu_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
953 			      unsigned long gp_seq_req, const char *s)
954 {
955 	trace_rcu_future_grace_period(rcu_state.name, READ_ONCE(rnp->gp_seq),
956 				      gp_seq_req, rnp->level,
957 				      rnp->grplo, rnp->grphi, s);
958 }
959 
960 /*
961  * rcu_start_this_gp - Request the start of a particular grace period
962  * @rnp_start: The leaf node of the CPU from which to start.
963  * @rdp: The rcu_data corresponding to the CPU from which to start.
964  * @gp_seq_req: The gp_seq of the grace period to start.
965  *
966  * Start the specified grace period, as needed to handle newly arrived
967  * callbacks.  The required future grace periods are recorded in each
968  * rcu_node structure's ->gp_seq_needed field.  Returns true if there
969  * is reason to awaken the grace-period kthread.
970  *
971  * The caller must hold the specified rcu_node structure's ->lock, which
972  * is why the caller is responsible for waking the grace-period kthread.
973  *
974  * Returns true if the GP thread needs to be awakened else false.
975  */
976 static bool rcu_start_this_gp(struct rcu_node *rnp_start, struct rcu_data *rdp,
977 			      unsigned long gp_seq_req)
978 {
979 	bool ret = false;
980 	struct rcu_node *rnp;
981 
982 	/*
983 	 * Use funnel locking to either acquire the root rcu_node
984 	 * structure's lock or bail out if the need for this grace period
985 	 * has already been recorded -- or if that grace period has in
986 	 * fact already started.  If there is already a grace period in
987 	 * progress in a non-leaf node, no recording is needed because the
988 	 * end of the grace period will scan the leaf rcu_node structures.
989 	 * Note that rnp_start->lock must not be released.
990 	 */
991 	raw_lockdep_assert_held_rcu_node(rnp_start);
992 	trace_rcu_this_gp(rnp_start, rdp, gp_seq_req, TPS("Startleaf"));
993 	for (rnp = rnp_start; 1; rnp = rnp->parent) {
994 		if (rnp != rnp_start)
995 			raw_spin_lock_rcu_node(rnp);
996 		if (ULONG_CMP_GE(rnp->gp_seq_needed, gp_seq_req) ||
997 		    rcu_seq_started(&rnp->gp_seq, gp_seq_req) ||
998 		    (rnp != rnp_start &&
999 		     rcu_seq_state(rcu_seq_current(&rnp->gp_seq)))) {
1000 			trace_rcu_this_gp(rnp, rdp, gp_seq_req,
1001 					  TPS("Prestarted"));
1002 			goto unlock_out;
1003 		}
1004 		WRITE_ONCE(rnp->gp_seq_needed, gp_seq_req);
1005 		if (rcu_seq_state(rcu_seq_current(&rnp->gp_seq))) {
1006 			/*
1007 			 * We just marked the leaf or internal node, and a
1008 			 * grace period is in progress, which means that
1009 			 * rcu_gp_cleanup() will see the marking.  Bail to
1010 			 * reduce contention.
1011 			 */
1012 			trace_rcu_this_gp(rnp_start, rdp, gp_seq_req,
1013 					  TPS("Startedleaf"));
1014 			goto unlock_out;
1015 		}
1016 		if (rnp != rnp_start && rnp->parent != NULL)
1017 			raw_spin_unlock_rcu_node(rnp);
1018 		if (!rnp->parent)
1019 			break;  /* At root, and perhaps also leaf. */
1020 	}
1021 
1022 	/* If GP already in progress, just leave, otherwise start one. */
1023 	if (rcu_gp_in_progress()) {
1024 		trace_rcu_this_gp(rnp, rdp, gp_seq_req, TPS("Startedleafroot"));
1025 		goto unlock_out;
1026 	}
1027 	trace_rcu_this_gp(rnp, rdp, gp_seq_req, TPS("Startedroot"));
1028 	WRITE_ONCE(rcu_state.gp_flags, rcu_state.gp_flags | RCU_GP_FLAG_INIT);
1029 	WRITE_ONCE(rcu_state.gp_req_activity, jiffies);
1030 	if (!READ_ONCE(rcu_state.gp_kthread)) {
1031 		trace_rcu_this_gp(rnp, rdp, gp_seq_req, TPS("NoGPkthread"));
1032 		goto unlock_out;
1033 	}
1034 	trace_rcu_grace_period(rcu_state.name, data_race(rcu_state.gp_seq), TPS("newreq"));
1035 	ret = true;  /* Caller must wake GP kthread. */
1036 unlock_out:
1037 	/* Push furthest requested GP to leaf node and rcu_data structure. */
1038 	if (ULONG_CMP_LT(gp_seq_req, rnp->gp_seq_needed)) {
1039 		WRITE_ONCE(rnp_start->gp_seq_needed, rnp->gp_seq_needed);
1040 		WRITE_ONCE(rdp->gp_seq_needed, rnp->gp_seq_needed);
1041 	}
1042 	if (rnp != rnp_start)
1043 		raw_spin_unlock_rcu_node(rnp);
1044 	return ret;
1045 }
1046 
1047 /*
1048  * Clean up any old requests for the just-ended grace period.  Also return
1049  * whether any additional grace periods have been requested.
1050  */
1051 static bool rcu_future_gp_cleanup(struct rcu_node *rnp)
1052 {
1053 	bool needmore;
1054 	struct rcu_data *rdp = this_cpu_ptr(&rcu_data);
1055 
1056 	needmore = ULONG_CMP_LT(rnp->gp_seq, rnp->gp_seq_needed);
1057 	if (!needmore)
1058 		rnp->gp_seq_needed = rnp->gp_seq; /* Avoid counter wrap. */
1059 	trace_rcu_this_gp(rnp, rdp, rnp->gp_seq,
1060 			  needmore ? TPS("CleanupMore") : TPS("Cleanup"));
1061 	return needmore;
1062 }
1063 
1064 static void swake_up_one_online_ipi(void *arg)
1065 {
1066 	struct swait_queue_head *wqh = arg;
1067 
1068 	swake_up_one(wqh);
1069 }
1070 
1071 static void swake_up_one_online(struct swait_queue_head *wqh)
1072 {
1073 	int cpu = get_cpu();
1074 
1075 	/*
1076 	 * If called from rcutree_report_cpu_starting(), wake up
1077 	 * is dangerous that late in the CPU-down hotplug process. The
1078 	 * scheduler might queue an ignored hrtimer. Defer the wake up
1079 	 * to an online CPU instead.
1080 	 */
1081 	if (unlikely(cpu_is_offline(cpu))) {
1082 		int target;
1083 
1084 		target = cpumask_any_and(housekeeping_cpumask(HK_TYPE_RCU),
1085 					 cpu_online_mask);
1086 
1087 		smp_call_function_single(target, swake_up_one_online_ipi,
1088 					 wqh, 0);
1089 		put_cpu();
1090 	} else {
1091 		put_cpu();
1092 		swake_up_one(wqh);
1093 	}
1094 }
1095 
1096 /*
1097  * Awaken the grace-period kthread.  Don't do a self-awaken (unless in an
1098  * interrupt or softirq handler, in which case we just might immediately
1099  * sleep upon return, resulting in a grace-period hang), and don't bother
1100  * awakening when there is nothing for the grace-period kthread to do
1101  * (as in several CPUs raced to awaken, we lost), and finally don't try
1102  * to awaken a kthread that has not yet been created.  If all those checks
1103  * are passed, track some debug information and awaken.
1104  *
1105  * So why do the self-wakeup when in an interrupt or softirq handler
1106  * in the grace-period kthread's context?  Because the kthread might have
1107  * been interrupted just as it was going to sleep, and just after the final
1108  * pre-sleep check of the awaken condition.  In this case, a wakeup really
1109  * is required, and is therefore supplied.
1110  */
1111 static void rcu_gp_kthread_wake(void)
1112 {
1113 	struct task_struct *t = READ_ONCE(rcu_state.gp_kthread);
1114 
1115 	if ((current == t && !in_hardirq() && !in_serving_softirq()) ||
1116 	    !READ_ONCE(rcu_state.gp_flags) || !t)
1117 		return;
1118 	WRITE_ONCE(rcu_state.gp_wake_time, jiffies);
1119 	WRITE_ONCE(rcu_state.gp_wake_seq, READ_ONCE(rcu_state.gp_seq));
1120 	swake_up_one_online(&rcu_state.gp_wq);
1121 }
1122 
1123 /*
1124  * If there is room, assign a ->gp_seq number to any callbacks on this
1125  * CPU that have not already been assigned.  Also accelerate any callbacks
1126  * that were previously assigned a ->gp_seq number that has since proven
1127  * to be too conservative, which can happen if callbacks get assigned a
1128  * ->gp_seq number while RCU is idle, but with reference to a non-root
1129  * rcu_node structure.  This function is idempotent, so it does not hurt
1130  * to call it repeatedly.  Returns an flag saying that we should awaken
1131  * the RCU grace-period kthread.
1132  *
1133  * The caller must hold rnp->lock with interrupts disabled.
1134  */
1135 static bool rcu_accelerate_cbs(struct rcu_node *rnp, struct rcu_data *rdp)
1136 {
1137 	unsigned long gp_seq_req;
1138 	bool ret = false;
1139 
1140 	rcu_lockdep_assert_cblist_protected(rdp);
1141 	raw_lockdep_assert_held_rcu_node(rnp);
1142 
1143 	/* If no pending (not yet ready to invoke) callbacks, nothing to do. */
1144 	if (!rcu_segcblist_pend_cbs(&rdp->cblist))
1145 		return false;
1146 
1147 	trace_rcu_segcb_stats(&rdp->cblist, TPS("SegCbPreAcc"));
1148 
1149 	/*
1150 	 * Callbacks are often registered with incomplete grace-period
1151 	 * information.  Something about the fact that getting exact
1152 	 * information requires acquiring a global lock...  RCU therefore
1153 	 * makes a conservative estimate of the grace period number at which
1154 	 * a given callback will become ready to invoke.	The following
1155 	 * code checks this estimate and improves it when possible, thus
1156 	 * accelerating callback invocation to an earlier grace-period
1157 	 * number.
1158 	 */
1159 	gp_seq_req = rcu_seq_snap(&rcu_state.gp_seq);
1160 	if (rcu_segcblist_accelerate(&rdp->cblist, gp_seq_req))
1161 		ret = rcu_start_this_gp(rnp, rdp, gp_seq_req);
1162 
1163 	/* Trace depending on how much we were able to accelerate. */
1164 	if (rcu_segcblist_restempty(&rdp->cblist, RCU_WAIT_TAIL))
1165 		trace_rcu_grace_period(rcu_state.name, gp_seq_req, TPS("AccWaitCB"));
1166 	else
1167 		trace_rcu_grace_period(rcu_state.name, gp_seq_req, TPS("AccReadyCB"));
1168 
1169 	trace_rcu_segcb_stats(&rdp->cblist, TPS("SegCbPostAcc"));
1170 
1171 	return ret;
1172 }
1173 
1174 /*
1175  * Similar to rcu_accelerate_cbs(), but does not require that the leaf
1176  * rcu_node structure's ->lock be held.  It consults the cached value
1177  * of ->gp_seq_needed in the rcu_data structure, and if that indicates
1178  * that a new grace-period request be made, invokes rcu_accelerate_cbs()
1179  * while holding the leaf rcu_node structure's ->lock.
1180  */
1181 static void rcu_accelerate_cbs_unlocked(struct rcu_node *rnp,
1182 					struct rcu_data *rdp)
1183 {
1184 	unsigned long c;
1185 	bool needwake;
1186 
1187 	rcu_lockdep_assert_cblist_protected(rdp);
1188 	c = rcu_seq_snap(&rcu_state.gp_seq);
1189 	if (!READ_ONCE(rdp->gpwrap) && ULONG_CMP_GE(rdp->gp_seq_needed, c)) {
1190 		/* Old request still live, so mark recent callbacks. */
1191 		(void)rcu_segcblist_accelerate(&rdp->cblist, c);
1192 		return;
1193 	}
1194 	raw_spin_lock_rcu_node(rnp); /* irqs already disabled. */
1195 	needwake = rcu_accelerate_cbs(rnp, rdp);
1196 	raw_spin_unlock_rcu_node(rnp); /* irqs remain disabled. */
1197 	if (needwake)
1198 		rcu_gp_kthread_wake();
1199 }
1200 
1201 /*
1202  * Move any callbacks whose grace period has completed to the
1203  * RCU_DONE_TAIL sublist, then compact the remaining sublists and
1204  * assign ->gp_seq numbers to any callbacks in the RCU_NEXT_TAIL
1205  * sublist.  This function is idempotent, so it does not hurt to
1206  * invoke it repeatedly.  As long as it is not invoked -too- often...
1207  * Returns true if the RCU grace-period kthread needs to be awakened.
1208  *
1209  * The caller must hold rnp->lock with interrupts disabled.
1210  */
1211 static bool rcu_advance_cbs(struct rcu_node *rnp, struct rcu_data *rdp)
1212 {
1213 	rcu_lockdep_assert_cblist_protected(rdp);
1214 	raw_lockdep_assert_held_rcu_node(rnp);
1215 
1216 	/* If no pending (not yet ready to invoke) callbacks, nothing to do. */
1217 	if (!rcu_segcblist_pend_cbs(&rdp->cblist))
1218 		return false;
1219 
1220 	/*
1221 	 * Find all callbacks whose ->gp_seq numbers indicate that they
1222 	 * are ready to invoke, and put them into the RCU_DONE_TAIL sublist.
1223 	 */
1224 	rcu_segcblist_advance(&rdp->cblist, rnp->gp_seq);
1225 
1226 	/* Classify any remaining callbacks. */
1227 	return rcu_accelerate_cbs(rnp, rdp);
1228 }
1229 
1230 /*
1231  * Move and classify callbacks, but only if doing so won't require
1232  * that the RCU grace-period kthread be awakened.
1233  */
1234 static void __maybe_unused rcu_advance_cbs_nowake(struct rcu_node *rnp,
1235 						  struct rcu_data *rdp)
1236 {
1237 	rcu_lockdep_assert_cblist_protected(rdp);
1238 	if (!rcu_seq_state(rcu_seq_current(&rnp->gp_seq)) || !raw_spin_trylock_rcu_node(rnp))
1239 		return;
1240 	// The grace period cannot end while we hold the rcu_node lock.
1241 	if (rcu_seq_state(rcu_seq_current(&rnp->gp_seq)))
1242 		WARN_ON_ONCE(rcu_advance_cbs(rnp, rdp));
1243 	raw_spin_unlock_rcu_node(rnp);
1244 }
1245 
1246 /*
1247  * In CONFIG_RCU_STRICT_GRACE_PERIOD=y kernels, attempt to generate a
1248  * quiescent state.  This is intended to be invoked when the CPU notices
1249  * a new grace period.
1250  */
1251 static void rcu_strict_gp_check_qs(void)
1252 {
1253 	if (IS_ENABLED(CONFIG_RCU_STRICT_GRACE_PERIOD)) {
1254 		rcu_read_lock();
1255 		rcu_read_unlock();
1256 	}
1257 }
1258 
1259 /*
1260  * Update CPU-local rcu_data state to record the beginnings and ends of
1261  * grace periods.  The caller must hold the ->lock of the leaf rcu_node
1262  * structure corresponding to the current CPU, and must have irqs disabled.
1263  * Returns true if the grace-period kthread needs to be awakened.
1264  */
1265 static bool __note_gp_changes(struct rcu_node *rnp, struct rcu_data *rdp)
1266 {
1267 	bool ret = false;
1268 	bool need_qs;
1269 	const bool offloaded = rcu_rdp_is_offloaded(rdp);
1270 
1271 	raw_lockdep_assert_held_rcu_node(rnp);
1272 
1273 	if (rdp->gp_seq == rnp->gp_seq)
1274 		return false; /* Nothing to do. */
1275 
1276 	/* Handle the ends of any preceding grace periods first. */
1277 	if (rcu_seq_completed_gp(rdp->gp_seq, rnp->gp_seq) ||
1278 	    unlikely(READ_ONCE(rdp->gpwrap))) {
1279 		if (!offloaded)
1280 			ret = rcu_advance_cbs(rnp, rdp); /* Advance CBs. */
1281 		rdp->core_needs_qs = false;
1282 		trace_rcu_grace_period(rcu_state.name, rdp->gp_seq, TPS("cpuend"));
1283 	} else {
1284 		if (!offloaded)
1285 			ret = rcu_accelerate_cbs(rnp, rdp); /* Recent CBs. */
1286 		if (rdp->core_needs_qs)
1287 			rdp->core_needs_qs = !!(rnp->qsmask & rdp->grpmask);
1288 	}
1289 
1290 	/* Now handle the beginnings of any new-to-this-CPU grace periods. */
1291 	if (rcu_seq_new_gp(rdp->gp_seq, rnp->gp_seq) ||
1292 	    unlikely(READ_ONCE(rdp->gpwrap))) {
1293 		/*
1294 		 * If the current grace period is waiting for this CPU,
1295 		 * set up to detect a quiescent state, otherwise don't
1296 		 * go looking for one.
1297 		 */
1298 		trace_rcu_grace_period(rcu_state.name, rnp->gp_seq, TPS("cpustart"));
1299 		need_qs = !!(rnp->qsmask & rdp->grpmask);
1300 		rdp->cpu_no_qs.b.norm = need_qs;
1301 		rdp->core_needs_qs = need_qs;
1302 		zero_cpu_stall_ticks(rdp);
1303 	}
1304 	rdp->gp_seq = rnp->gp_seq;  /* Remember new grace-period state. */
1305 	if (ULONG_CMP_LT(rdp->gp_seq_needed, rnp->gp_seq_needed) || rdp->gpwrap)
1306 		WRITE_ONCE(rdp->gp_seq_needed, rnp->gp_seq_needed);
1307 	if (IS_ENABLED(CONFIG_PROVE_RCU) && READ_ONCE(rdp->gpwrap))
1308 		WRITE_ONCE(rdp->last_sched_clock, jiffies);
1309 	WRITE_ONCE(rdp->gpwrap, false);
1310 	rcu_gpnum_ovf(rnp, rdp);
1311 	return ret;
1312 }
1313 
1314 static void note_gp_changes(struct rcu_data *rdp)
1315 {
1316 	unsigned long flags;
1317 	bool needwake;
1318 	struct rcu_node *rnp;
1319 
1320 	local_irq_save(flags);
1321 	rnp = rdp->mynode;
1322 	if ((rdp->gp_seq == rcu_seq_current(&rnp->gp_seq) &&
1323 	     !unlikely(READ_ONCE(rdp->gpwrap))) || /* w/out lock. */
1324 	    !raw_spin_trylock_rcu_node(rnp)) { /* irqs already off, so later. */
1325 		local_irq_restore(flags);
1326 		return;
1327 	}
1328 	needwake = __note_gp_changes(rnp, rdp);
1329 	raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
1330 	rcu_strict_gp_check_qs();
1331 	if (needwake)
1332 		rcu_gp_kthread_wake();
1333 }
1334 
1335 static atomic_t *rcu_gp_slow_suppress;
1336 
1337 /* Register a counter to suppress debugging grace-period delays. */
1338 void rcu_gp_slow_register(atomic_t *rgssp)
1339 {
1340 	WARN_ON_ONCE(rcu_gp_slow_suppress);
1341 
1342 	WRITE_ONCE(rcu_gp_slow_suppress, rgssp);
1343 }
1344 EXPORT_SYMBOL_GPL(rcu_gp_slow_register);
1345 
1346 /* Unregister a counter, with NULL for not caring which. */
1347 void rcu_gp_slow_unregister(atomic_t *rgssp)
1348 {
1349 	WARN_ON_ONCE(rgssp && rgssp != rcu_gp_slow_suppress && rcu_gp_slow_suppress != NULL);
1350 
1351 	WRITE_ONCE(rcu_gp_slow_suppress, NULL);
1352 }
1353 EXPORT_SYMBOL_GPL(rcu_gp_slow_unregister);
1354 
1355 static bool rcu_gp_slow_is_suppressed(void)
1356 {
1357 	atomic_t *rgssp = READ_ONCE(rcu_gp_slow_suppress);
1358 
1359 	return rgssp && atomic_read(rgssp);
1360 }
1361 
1362 static void rcu_gp_slow(int delay)
1363 {
1364 	if (!rcu_gp_slow_is_suppressed() && delay > 0 &&
1365 	    !(rcu_seq_ctr(rcu_state.gp_seq) % (rcu_num_nodes * PER_RCU_NODE_PERIOD * delay)))
1366 		schedule_timeout_idle(delay);
1367 }
1368 
1369 static unsigned long sleep_duration;
1370 
1371 /* Allow rcutorture to stall the grace-period kthread. */
1372 void rcu_gp_set_torture_wait(int duration)
1373 {
1374 	if (IS_ENABLED(CONFIG_RCU_TORTURE_TEST) && duration > 0)
1375 		WRITE_ONCE(sleep_duration, duration);
1376 }
1377 EXPORT_SYMBOL_GPL(rcu_gp_set_torture_wait);
1378 
1379 /* Actually implement the aforementioned wait. */
1380 static void rcu_gp_torture_wait(void)
1381 {
1382 	unsigned long duration;
1383 
1384 	if (!IS_ENABLED(CONFIG_RCU_TORTURE_TEST))
1385 		return;
1386 	duration = xchg(&sleep_duration, 0UL);
1387 	if (duration > 0) {
1388 		pr_alert("%s: Waiting %lu jiffies\n", __func__, duration);
1389 		schedule_timeout_idle(duration);
1390 		pr_alert("%s: Wait complete\n", __func__);
1391 	}
1392 }
1393 
1394 /*
1395  * Handler for on_each_cpu() to invoke the target CPU's RCU core
1396  * processing.
1397  */
1398 static void rcu_strict_gp_boundary(void *unused)
1399 {
1400 	invoke_rcu_core();
1401 }
1402 
1403 // Make the polled API aware of the beginning of a grace period.
1404 static void rcu_poll_gp_seq_start(unsigned long *snap)
1405 {
1406 	struct rcu_node *rnp = rcu_get_root();
1407 
1408 	if (rcu_scheduler_active != RCU_SCHEDULER_INACTIVE)
1409 		raw_lockdep_assert_held_rcu_node(rnp);
1410 
1411 	// If RCU was idle, note beginning of GP.
1412 	if (!rcu_seq_state(rcu_state.gp_seq_polled))
1413 		rcu_seq_start(&rcu_state.gp_seq_polled);
1414 
1415 	// Either way, record current state.
1416 	*snap = rcu_state.gp_seq_polled;
1417 }
1418 
1419 // Make the polled API aware of the end of a grace period.
1420 static void rcu_poll_gp_seq_end(unsigned long *snap)
1421 {
1422 	struct rcu_node *rnp = rcu_get_root();
1423 
1424 	if (rcu_scheduler_active != RCU_SCHEDULER_INACTIVE)
1425 		raw_lockdep_assert_held_rcu_node(rnp);
1426 
1427 	// If the previously noted GP is still in effect, record the
1428 	// end of that GP.  Either way, zero counter to avoid counter-wrap
1429 	// problems.
1430 	if (*snap && *snap == rcu_state.gp_seq_polled) {
1431 		rcu_seq_end(&rcu_state.gp_seq_polled);
1432 		rcu_state.gp_seq_polled_snap = 0;
1433 		rcu_state.gp_seq_polled_exp_snap = 0;
1434 	} else {
1435 		*snap = 0;
1436 	}
1437 }
1438 
1439 // Make the polled API aware of the beginning of a grace period, but
1440 // where caller does not hold the root rcu_node structure's lock.
1441 static void rcu_poll_gp_seq_start_unlocked(unsigned long *snap)
1442 {
1443 	unsigned long flags;
1444 	struct rcu_node *rnp = rcu_get_root();
1445 
1446 	if (rcu_init_invoked()) {
1447 		if (rcu_scheduler_active != RCU_SCHEDULER_INACTIVE)
1448 			lockdep_assert_irqs_enabled();
1449 		raw_spin_lock_irqsave_rcu_node(rnp, flags);
1450 	}
1451 	rcu_poll_gp_seq_start(snap);
1452 	if (rcu_init_invoked())
1453 		raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
1454 }
1455 
1456 // Make the polled API aware of the end of a grace period, but where
1457 // caller does not hold the root rcu_node structure's lock.
1458 static void rcu_poll_gp_seq_end_unlocked(unsigned long *snap)
1459 {
1460 	unsigned long flags;
1461 	struct rcu_node *rnp = rcu_get_root();
1462 
1463 	if (rcu_init_invoked()) {
1464 		if (rcu_scheduler_active != RCU_SCHEDULER_INACTIVE)
1465 			lockdep_assert_irqs_enabled();
1466 		raw_spin_lock_irqsave_rcu_node(rnp, flags);
1467 	}
1468 	rcu_poll_gp_seq_end(snap);
1469 	if (rcu_init_invoked())
1470 		raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
1471 }
1472 
1473 /*
1474  * There is a single llist, which is used for handling
1475  * synchronize_rcu() users' enqueued rcu_synchronize nodes.
1476  * Within this llist, there are two tail pointers:
1477  *
1478  * wait tail: Tracks the set of nodes, which need to
1479  *            wait for the current GP to complete.
1480  * done tail: Tracks the set of nodes, for which grace
1481  *            period has elapsed. These nodes processing
1482  *            will be done as part of the cleanup work
1483  *            execution by a kworker.
1484  *
1485  * At every grace period init, a new wait node is added
1486  * to the llist. This wait node is used as wait tail
1487  * for this new grace period. Given that there are a fixed
1488  * number of wait nodes, if all wait nodes are in use
1489  * (which can happen when kworker callback processing
1490  * is delayed) and additional grace period is requested.
1491  * This means, a system is slow in processing callbacks.
1492  *
1493  * TODO: If a slow processing is detected, a first node
1494  * in the llist should be used as a wait-tail for this
1495  * grace period, therefore users which should wait due
1496  * to a slow process are handled by _this_ grace period
1497  * and not next.
1498  *
1499  * Below is an illustration of how the done and wait
1500  * tail pointers move from one set of rcu_synchronize nodes
1501  * to the other, as grace periods start and finish and
1502  * nodes are processed by kworker.
1503  *
1504  *
1505  * a. Initial llist callbacks list:
1506  *
1507  * +----------+           +--------+          +-------+
1508  * |          |           |        |          |       |
1509  * |   head   |---------> |   cb2  |--------->| cb1   |
1510  * |          |           |        |          |       |
1511  * +----------+           +--------+          +-------+
1512  *
1513  *
1514  *
1515  * b. New GP1 Start:
1516  *
1517  *                    WAIT TAIL
1518  *                      |
1519  *                      |
1520  *                      v
1521  * +----------+     +--------+      +--------+        +-------+
1522  * |          |     |        |      |        |        |       |
1523  * |   head   ------> wait   |------>   cb2  |------> |  cb1  |
1524  * |          |     | head1  |      |        |        |       |
1525  * +----------+     +--------+      +--------+        +-------+
1526  *
1527  *
1528  *
1529  * c. GP completion:
1530  *
1531  * WAIT_TAIL == DONE_TAIL
1532  *
1533  *                   DONE TAIL
1534  *                     |
1535  *                     |
1536  *                     v
1537  * +----------+     +--------+      +--------+        +-------+
1538  * |          |     |        |      |        |        |       |
1539  * |   head   ------> wait   |------>   cb2  |------> |  cb1  |
1540  * |          |     | head1  |      |        |        |       |
1541  * +----------+     +--------+      +--------+        +-------+
1542  *
1543  *
1544  *
1545  * d. New callbacks and GP2 start:
1546  *
1547  *                    WAIT TAIL                          DONE TAIL
1548  *                      |                                 |
1549  *                      |                                 |
1550  *                      v                                 v
1551  * +----------+     +------+    +------+    +------+    +-----+    +-----+    +-----+
1552  * |          |     |      |    |      |    |      |    |     |    |     |    |     |
1553  * |   head   ------> wait |--->|  cb4 |--->| cb3  |--->|wait |--->| cb2 |--->| cb1 |
1554  * |          |     | head2|    |      |    |      |    |head1|    |     |    |     |
1555  * +----------+     +------+    +------+    +------+    +-----+    +-----+    +-----+
1556  *
1557  *
1558  *
1559  * e. GP2 completion:
1560  *
1561  * WAIT_TAIL == DONE_TAIL
1562  *                   DONE TAIL
1563  *                      |
1564  *                      |
1565  *                      v
1566  * +----------+     +------+    +------+    +------+    +-----+    +-----+    +-----+
1567  * |          |     |      |    |      |    |      |    |     |    |     |    |     |
1568  * |   head   ------> wait |--->|  cb4 |--->| cb3  |--->|wait |--->| cb2 |--->| cb1 |
1569  * |          |     | head2|    |      |    |      |    |head1|    |     |    |     |
1570  * +----------+     +------+    +------+    +------+    +-----+    +-----+    +-----+
1571  *
1572  *
1573  * While the llist state transitions from d to e, a kworker
1574  * can start executing rcu_sr_normal_gp_cleanup_work() and
1575  * can observe either the old done tail (@c) or the new
1576  * done tail (@e). So, done tail updates and reads need
1577  * to use the rel-acq semantics. If the concurrent kworker
1578  * observes the old done tail, the newly queued work
1579  * execution will process the updated done tail. If the
1580  * concurrent kworker observes the new done tail, then
1581  * the newly queued work will skip processing the done
1582  * tail, as workqueue semantics guarantees that the new
1583  * work is executed only after the previous one completes.
1584  *
1585  * f. kworker callbacks processing complete:
1586  *
1587  *
1588  *                   DONE TAIL
1589  *                     |
1590  *                     |
1591  *                     v
1592  * +----------+     +--------+
1593  * |          |     |        |
1594  * |   head   ------> wait   |
1595  * |          |     | head2  |
1596  * +----------+     +--------+
1597  *
1598  */
1599 static bool rcu_sr_is_wait_head(struct llist_node *node)
1600 {
1601 	return &(rcu_state.srs_wait_nodes)[0].node <= node &&
1602 		node <= &(rcu_state.srs_wait_nodes)[SR_NORMAL_GP_WAIT_HEAD_MAX - 1].node;
1603 }
1604 
1605 static struct llist_node *rcu_sr_get_wait_head(void)
1606 {
1607 	struct sr_wait_node *sr_wn;
1608 	int i;
1609 
1610 	for (i = 0; i < SR_NORMAL_GP_WAIT_HEAD_MAX; i++) {
1611 		sr_wn = &(rcu_state.srs_wait_nodes)[i];
1612 
1613 		if (!atomic_cmpxchg_acquire(&sr_wn->inuse, 0, 1))
1614 			return &sr_wn->node;
1615 	}
1616 
1617 	return NULL;
1618 }
1619 
1620 static void rcu_sr_put_wait_head(struct llist_node *node)
1621 {
1622 	struct sr_wait_node *sr_wn = container_of(node, struct sr_wait_node, node);
1623 
1624 	atomic_set_release(&sr_wn->inuse, 0);
1625 }
1626 
1627 /* Disabled by default. */
1628 static int rcu_normal_wake_from_gp;
1629 module_param(rcu_normal_wake_from_gp, int, 0644);
1630 static struct workqueue_struct *sync_wq;
1631 
1632 static void rcu_sr_normal_complete(struct llist_node *node)
1633 {
1634 	struct rcu_synchronize *rs = container_of(
1635 		(struct rcu_head *) node, struct rcu_synchronize, head);
1636 	unsigned long oldstate = (unsigned long) rs->head.func;
1637 
1638 	WARN_ONCE(IS_ENABLED(CONFIG_PROVE_RCU) &&
1639 		!poll_state_synchronize_rcu(oldstate),
1640 		"A full grace period is not passed yet: %lu",
1641 		rcu_seq_diff(get_state_synchronize_rcu(), oldstate));
1642 
1643 	/* Finally. */
1644 	complete(&rs->completion);
1645 }
1646 
1647 static void rcu_sr_normal_gp_cleanup_work(struct work_struct *work)
1648 {
1649 	struct llist_node *done, *rcu, *next, *head;
1650 
1651 	/*
1652 	 * This work execution can potentially execute
1653 	 * while a new done tail is being updated by
1654 	 * grace period kthread in rcu_sr_normal_gp_cleanup().
1655 	 * So, read and updates of done tail need to
1656 	 * follow acq-rel semantics.
1657 	 *
1658 	 * Given that wq semantics guarantees that a single work
1659 	 * cannot execute concurrently by multiple kworkers,
1660 	 * the done tail list manipulations are protected here.
1661 	 */
1662 	done = smp_load_acquire(&rcu_state.srs_done_tail);
1663 	if (WARN_ON_ONCE(!done))
1664 		return;
1665 
1666 	WARN_ON_ONCE(!rcu_sr_is_wait_head(done));
1667 	head = done->next;
1668 	done->next = NULL;
1669 
1670 	/*
1671 	 * The dummy node, which is pointed to by the
1672 	 * done tail which is acq-read above is not removed
1673 	 * here.  This allows lockless additions of new
1674 	 * rcu_synchronize nodes in rcu_sr_normal_add_req(),
1675 	 * while the cleanup work executes. The dummy
1676 	 * nodes is removed, in next round of cleanup
1677 	 * work execution.
1678 	 */
1679 	llist_for_each_safe(rcu, next, head) {
1680 		if (!rcu_sr_is_wait_head(rcu)) {
1681 			rcu_sr_normal_complete(rcu);
1682 			continue;
1683 		}
1684 
1685 		rcu_sr_put_wait_head(rcu);
1686 	}
1687 
1688 	/* Order list manipulations with atomic access. */
1689 	atomic_dec_return_release(&rcu_state.srs_cleanups_pending);
1690 }
1691 
1692 /*
1693  * Helper function for rcu_gp_cleanup().
1694  */
1695 static void rcu_sr_normal_gp_cleanup(void)
1696 {
1697 	struct llist_node *wait_tail, *next = NULL, *rcu = NULL;
1698 	int done = 0;
1699 
1700 	wait_tail = rcu_state.srs_wait_tail;
1701 	if (wait_tail == NULL)
1702 		return;
1703 
1704 	rcu_state.srs_wait_tail = NULL;
1705 	ASSERT_EXCLUSIVE_WRITER(rcu_state.srs_wait_tail);
1706 	WARN_ON_ONCE(!rcu_sr_is_wait_head(wait_tail));
1707 
1708 	/*
1709 	 * Process (a) and (d) cases. See an illustration.
1710 	 */
1711 	llist_for_each_safe(rcu, next, wait_tail->next) {
1712 		if (rcu_sr_is_wait_head(rcu))
1713 			break;
1714 
1715 		rcu_sr_normal_complete(rcu);
1716 		// It can be last, update a next on this step.
1717 		wait_tail->next = next;
1718 
1719 		if (++done == SR_MAX_USERS_WAKE_FROM_GP)
1720 			break;
1721 	}
1722 
1723 	/*
1724 	 * Fast path, no more users to process except putting the second last
1725 	 * wait head if no inflight-workers. If there are in-flight workers,
1726 	 * they will remove the last wait head.
1727 	 *
1728 	 * Note that the ACQUIRE orders atomic access with list manipulation.
1729 	 */
1730 	if (wait_tail->next && wait_tail->next->next == NULL &&
1731 	    rcu_sr_is_wait_head(wait_tail->next) &&
1732 	    !atomic_read_acquire(&rcu_state.srs_cleanups_pending)) {
1733 		rcu_sr_put_wait_head(wait_tail->next);
1734 		wait_tail->next = NULL;
1735 	}
1736 
1737 	/* Concurrent sr_normal_gp_cleanup work might observe this update. */
1738 	ASSERT_EXCLUSIVE_WRITER(rcu_state.srs_done_tail);
1739 	smp_store_release(&rcu_state.srs_done_tail, wait_tail);
1740 
1741 	/*
1742 	 * We schedule a work in order to perform a final processing
1743 	 * of outstanding users(if still left) and releasing wait-heads
1744 	 * added by rcu_sr_normal_gp_init() call.
1745 	 */
1746 	if (wait_tail->next) {
1747 		atomic_inc(&rcu_state.srs_cleanups_pending);
1748 		if (!queue_work(sync_wq, &rcu_state.srs_cleanup_work))
1749 			atomic_dec(&rcu_state.srs_cleanups_pending);
1750 	}
1751 }
1752 
1753 /*
1754  * Helper function for rcu_gp_init().
1755  */
1756 static bool rcu_sr_normal_gp_init(void)
1757 {
1758 	struct llist_node *first;
1759 	struct llist_node *wait_head;
1760 	bool start_new_poll = false;
1761 
1762 	first = READ_ONCE(rcu_state.srs_next.first);
1763 	if (!first || rcu_sr_is_wait_head(first))
1764 		return start_new_poll;
1765 
1766 	wait_head = rcu_sr_get_wait_head();
1767 	if (!wait_head) {
1768 		// Kick another GP to retry.
1769 		start_new_poll = true;
1770 		return start_new_poll;
1771 	}
1772 
1773 	/* Inject a wait-dummy-node. */
1774 	llist_add(wait_head, &rcu_state.srs_next);
1775 
1776 	/*
1777 	 * A waiting list of rcu_synchronize nodes should be empty on
1778 	 * this step, since a GP-kthread, rcu_gp_init() -> gp_cleanup(),
1779 	 * rolls it over. If not, it is a BUG, warn a user.
1780 	 */
1781 	WARN_ON_ONCE(rcu_state.srs_wait_tail != NULL);
1782 	rcu_state.srs_wait_tail = wait_head;
1783 	ASSERT_EXCLUSIVE_WRITER(rcu_state.srs_wait_tail);
1784 
1785 	return start_new_poll;
1786 }
1787 
1788 static void rcu_sr_normal_add_req(struct rcu_synchronize *rs)
1789 {
1790 	llist_add((struct llist_node *) &rs->head, &rcu_state.srs_next);
1791 }
1792 
1793 /*
1794  * Initialize a new grace period.  Return false if no grace period required.
1795  */
1796 static noinline_for_stack bool rcu_gp_init(void)
1797 {
1798 	unsigned long flags;
1799 	unsigned long oldmask;
1800 	unsigned long mask;
1801 	struct rcu_data *rdp;
1802 	struct rcu_node *rnp = rcu_get_root();
1803 	bool start_new_poll;
1804 
1805 	WRITE_ONCE(rcu_state.gp_activity, jiffies);
1806 	raw_spin_lock_irq_rcu_node(rnp);
1807 	if (!rcu_state.gp_flags) {
1808 		/* Spurious wakeup, tell caller to go back to sleep.  */
1809 		raw_spin_unlock_irq_rcu_node(rnp);
1810 		return false;
1811 	}
1812 	WRITE_ONCE(rcu_state.gp_flags, 0); /* Clear all flags: New GP. */
1813 
1814 	if (WARN_ON_ONCE(rcu_gp_in_progress())) {
1815 		/*
1816 		 * Grace period already in progress, don't start another.
1817 		 * Not supposed to be able to happen.
1818 		 */
1819 		raw_spin_unlock_irq_rcu_node(rnp);
1820 		return false;
1821 	}
1822 
1823 	/* Advance to a new grace period and initialize state. */
1824 	record_gp_stall_check_time();
1825 	/* Record GP times before starting GP, hence rcu_seq_start(). */
1826 	rcu_seq_start(&rcu_state.gp_seq);
1827 	ASSERT_EXCLUSIVE_WRITER(rcu_state.gp_seq);
1828 	start_new_poll = rcu_sr_normal_gp_init();
1829 	trace_rcu_grace_period(rcu_state.name, rcu_state.gp_seq, TPS("start"));
1830 	rcu_poll_gp_seq_start(&rcu_state.gp_seq_polled_snap);
1831 	raw_spin_unlock_irq_rcu_node(rnp);
1832 
1833 	/*
1834 	 * The "start_new_poll" is set to true, only when this GP is not able
1835 	 * to handle anything and there are outstanding users. It happens when
1836 	 * the rcu_sr_normal_gp_init() function was not able to insert a dummy
1837 	 * separator to the llist, because there were no left any dummy-nodes.
1838 	 *
1839 	 * Number of dummy-nodes is fixed, it could be that we are run out of
1840 	 * them, if so we start a new pool request to repeat a try. It is rare
1841 	 * and it means that a system is doing a slow processing of callbacks.
1842 	 */
1843 	if (start_new_poll)
1844 		(void) start_poll_synchronize_rcu();
1845 
1846 	/*
1847 	 * Apply per-leaf buffered online and offline operations to
1848 	 * the rcu_node tree. Note that this new grace period need not
1849 	 * wait for subsequent online CPUs, and that RCU hooks in the CPU
1850 	 * offlining path, when combined with checks in this function,
1851 	 * will handle CPUs that are currently going offline or that will
1852 	 * go offline later.  Please also refer to "Hotplug CPU" section
1853 	 * of RCU's Requirements documentation.
1854 	 */
1855 	WRITE_ONCE(rcu_state.gp_state, RCU_GP_ONOFF);
1856 	/* Exclude CPU hotplug operations. */
1857 	rcu_for_each_leaf_node(rnp) {
1858 		local_irq_disable();
1859 		arch_spin_lock(&rcu_state.ofl_lock);
1860 		raw_spin_lock_rcu_node(rnp);
1861 		if (rnp->qsmaskinit == rnp->qsmaskinitnext &&
1862 		    !rnp->wait_blkd_tasks) {
1863 			/* Nothing to do on this leaf rcu_node structure. */
1864 			raw_spin_unlock_rcu_node(rnp);
1865 			arch_spin_unlock(&rcu_state.ofl_lock);
1866 			local_irq_enable();
1867 			continue;
1868 		}
1869 
1870 		/* Record old state, apply changes to ->qsmaskinit field. */
1871 		oldmask = rnp->qsmaskinit;
1872 		rnp->qsmaskinit = rnp->qsmaskinitnext;
1873 
1874 		/* If zero-ness of ->qsmaskinit changed, propagate up tree. */
1875 		if (!oldmask != !rnp->qsmaskinit) {
1876 			if (!oldmask) { /* First online CPU for rcu_node. */
1877 				if (!rnp->wait_blkd_tasks) /* Ever offline? */
1878 					rcu_init_new_rnp(rnp);
1879 			} else if (rcu_preempt_has_tasks(rnp)) {
1880 				rnp->wait_blkd_tasks = true; /* blocked tasks */
1881 			} else { /* Last offline CPU and can propagate. */
1882 				rcu_cleanup_dead_rnp(rnp);
1883 			}
1884 		}
1885 
1886 		/*
1887 		 * If all waited-on tasks from prior grace period are
1888 		 * done, and if all this rcu_node structure's CPUs are
1889 		 * still offline, propagate up the rcu_node tree and
1890 		 * clear ->wait_blkd_tasks.  Otherwise, if one of this
1891 		 * rcu_node structure's CPUs has since come back online,
1892 		 * simply clear ->wait_blkd_tasks.
1893 		 */
1894 		if (rnp->wait_blkd_tasks &&
1895 		    (!rcu_preempt_has_tasks(rnp) || rnp->qsmaskinit)) {
1896 			rnp->wait_blkd_tasks = false;
1897 			if (!rnp->qsmaskinit)
1898 				rcu_cleanup_dead_rnp(rnp);
1899 		}
1900 
1901 		raw_spin_unlock_rcu_node(rnp);
1902 		arch_spin_unlock(&rcu_state.ofl_lock);
1903 		local_irq_enable();
1904 	}
1905 	rcu_gp_slow(gp_preinit_delay); /* Races with CPU hotplug. */
1906 
1907 	/*
1908 	 * Set the quiescent-state-needed bits in all the rcu_node
1909 	 * structures for all currently online CPUs in breadth-first
1910 	 * order, starting from the root rcu_node structure, relying on the
1911 	 * layout of the tree within the rcu_state.node[] array.  Note that
1912 	 * other CPUs will access only the leaves of the hierarchy, thus
1913 	 * seeing that no grace period is in progress, at least until the
1914 	 * corresponding leaf node has been initialized.
1915 	 *
1916 	 * The grace period cannot complete until the initialization
1917 	 * process finishes, because this kthread handles both.
1918 	 */
1919 	WRITE_ONCE(rcu_state.gp_state, RCU_GP_INIT);
1920 	rcu_for_each_node_breadth_first(rnp) {
1921 		rcu_gp_slow(gp_init_delay);
1922 		raw_spin_lock_irqsave_rcu_node(rnp, flags);
1923 		rdp = this_cpu_ptr(&rcu_data);
1924 		rcu_preempt_check_blocked_tasks(rnp);
1925 		rnp->qsmask = rnp->qsmaskinit;
1926 		WRITE_ONCE(rnp->gp_seq, rcu_state.gp_seq);
1927 		if (rnp == rdp->mynode)
1928 			(void)__note_gp_changes(rnp, rdp);
1929 		rcu_preempt_boost_start_gp(rnp);
1930 		trace_rcu_grace_period_init(rcu_state.name, rnp->gp_seq,
1931 					    rnp->level, rnp->grplo,
1932 					    rnp->grphi, rnp->qsmask);
1933 		/* Quiescent states for tasks on any now-offline CPUs. */
1934 		mask = rnp->qsmask & ~rnp->qsmaskinitnext;
1935 		rnp->rcu_gp_init_mask = mask;
1936 		if ((mask || rnp->wait_blkd_tasks) && rcu_is_leaf_node(rnp))
1937 			rcu_report_qs_rnp(mask, rnp, rnp->gp_seq, flags);
1938 		else
1939 			raw_spin_unlock_irq_rcu_node(rnp);
1940 		cond_resched_tasks_rcu_qs();
1941 		WRITE_ONCE(rcu_state.gp_activity, jiffies);
1942 	}
1943 
1944 	// If strict, make all CPUs aware of new grace period.
1945 	if (IS_ENABLED(CONFIG_RCU_STRICT_GRACE_PERIOD))
1946 		on_each_cpu(rcu_strict_gp_boundary, NULL, 0);
1947 
1948 	return true;
1949 }
1950 
1951 /*
1952  * Helper function for swait_event_idle_exclusive() wakeup at force-quiescent-state
1953  * time.
1954  */
1955 static bool rcu_gp_fqs_check_wake(int *gfp)
1956 {
1957 	struct rcu_node *rnp = rcu_get_root();
1958 
1959 	// If under overload conditions, force an immediate FQS scan.
1960 	if (*gfp & RCU_GP_FLAG_OVLD)
1961 		return true;
1962 
1963 	// Someone like call_rcu() requested a force-quiescent-state scan.
1964 	*gfp = READ_ONCE(rcu_state.gp_flags);
1965 	if (*gfp & RCU_GP_FLAG_FQS)
1966 		return true;
1967 
1968 	// The current grace period has completed.
1969 	if (!READ_ONCE(rnp->qsmask) && !rcu_preempt_blocked_readers_cgp(rnp))
1970 		return true;
1971 
1972 	return false;
1973 }
1974 
1975 /*
1976  * Do one round of quiescent-state forcing.
1977  */
1978 static void rcu_gp_fqs(bool first_time)
1979 {
1980 	int nr_fqs = READ_ONCE(rcu_state.nr_fqs_jiffies_stall);
1981 	struct rcu_node *rnp = rcu_get_root();
1982 
1983 	WRITE_ONCE(rcu_state.gp_activity, jiffies);
1984 	WRITE_ONCE(rcu_state.n_force_qs, rcu_state.n_force_qs + 1);
1985 
1986 	WARN_ON_ONCE(nr_fqs > 3);
1987 	/* Only countdown nr_fqs for stall purposes if jiffies moves. */
1988 	if (nr_fqs) {
1989 		if (nr_fqs == 1) {
1990 			WRITE_ONCE(rcu_state.jiffies_stall,
1991 				   jiffies + rcu_jiffies_till_stall_check());
1992 		}
1993 		WRITE_ONCE(rcu_state.nr_fqs_jiffies_stall, --nr_fqs);
1994 	}
1995 
1996 	if (first_time) {
1997 		/* Collect dyntick-idle snapshots. */
1998 		force_qs_rnp(rcu_watching_snap_save);
1999 	} else {
2000 		/* Handle dyntick-idle and offline CPUs. */
2001 		force_qs_rnp(rcu_watching_snap_recheck);
2002 	}
2003 	/* Clear flag to prevent immediate re-entry. */
2004 	if (READ_ONCE(rcu_state.gp_flags) & RCU_GP_FLAG_FQS) {
2005 		raw_spin_lock_irq_rcu_node(rnp);
2006 		WRITE_ONCE(rcu_state.gp_flags, rcu_state.gp_flags & ~RCU_GP_FLAG_FQS);
2007 		raw_spin_unlock_irq_rcu_node(rnp);
2008 	}
2009 }
2010 
2011 /*
2012  * Loop doing repeated quiescent-state forcing until the grace period ends.
2013  */
2014 static noinline_for_stack void rcu_gp_fqs_loop(void)
2015 {
2016 	bool first_gp_fqs = true;
2017 	int gf = 0;
2018 	unsigned long j;
2019 	int ret;
2020 	struct rcu_node *rnp = rcu_get_root();
2021 
2022 	j = READ_ONCE(jiffies_till_first_fqs);
2023 	if (rcu_state.cbovld)
2024 		gf = RCU_GP_FLAG_OVLD;
2025 	ret = 0;
2026 	for (;;) {
2027 		if (rcu_state.cbovld) {
2028 			j = (j + 2) / 3;
2029 			if (j <= 0)
2030 				j = 1;
2031 		}
2032 		if (!ret || time_before(jiffies + j, rcu_state.jiffies_force_qs)) {
2033 			WRITE_ONCE(rcu_state.jiffies_force_qs, jiffies + j);
2034 			/*
2035 			 * jiffies_force_qs before RCU_GP_WAIT_FQS state
2036 			 * update; required for stall checks.
2037 			 */
2038 			smp_wmb();
2039 			WRITE_ONCE(rcu_state.jiffies_kick_kthreads,
2040 				   jiffies + (j ? 3 * j : 2));
2041 		}
2042 		trace_rcu_grace_period(rcu_state.name, rcu_state.gp_seq,
2043 				       TPS("fqswait"));
2044 		WRITE_ONCE(rcu_state.gp_state, RCU_GP_WAIT_FQS);
2045 		(void)swait_event_idle_timeout_exclusive(rcu_state.gp_wq,
2046 				 rcu_gp_fqs_check_wake(&gf), j);
2047 		rcu_gp_torture_wait();
2048 		WRITE_ONCE(rcu_state.gp_state, RCU_GP_DOING_FQS);
2049 		/* Locking provides needed memory barriers. */
2050 		/*
2051 		 * Exit the loop if the root rcu_node structure indicates that the grace period
2052 		 * has ended, leave the loop.  The rcu_preempt_blocked_readers_cgp(rnp) check
2053 		 * is required only for single-node rcu_node trees because readers blocking
2054 		 * the current grace period are queued only on leaf rcu_node structures.
2055 		 * For multi-node trees, checking the root node's ->qsmask suffices, because a
2056 		 * given root node's ->qsmask bit is cleared only when all CPUs and tasks from
2057 		 * the corresponding leaf nodes have passed through their quiescent state.
2058 		 */
2059 		if (!READ_ONCE(rnp->qsmask) &&
2060 		    !rcu_preempt_blocked_readers_cgp(rnp))
2061 			break;
2062 		/* If time for quiescent-state forcing, do it. */
2063 		if (!time_after(rcu_state.jiffies_force_qs, jiffies) ||
2064 		    (gf & (RCU_GP_FLAG_FQS | RCU_GP_FLAG_OVLD))) {
2065 			trace_rcu_grace_period(rcu_state.name, rcu_state.gp_seq,
2066 					       TPS("fqsstart"));
2067 			rcu_gp_fqs(first_gp_fqs);
2068 			gf = 0;
2069 			if (first_gp_fqs) {
2070 				first_gp_fqs = false;
2071 				gf = rcu_state.cbovld ? RCU_GP_FLAG_OVLD : 0;
2072 			}
2073 			trace_rcu_grace_period(rcu_state.name, rcu_state.gp_seq,
2074 					       TPS("fqsend"));
2075 			cond_resched_tasks_rcu_qs();
2076 			WRITE_ONCE(rcu_state.gp_activity, jiffies);
2077 			ret = 0; /* Force full wait till next FQS. */
2078 			j = READ_ONCE(jiffies_till_next_fqs);
2079 		} else {
2080 			/* Deal with stray signal. */
2081 			cond_resched_tasks_rcu_qs();
2082 			WRITE_ONCE(rcu_state.gp_activity, jiffies);
2083 			WARN_ON(signal_pending(current));
2084 			trace_rcu_grace_period(rcu_state.name, rcu_state.gp_seq,
2085 					       TPS("fqswaitsig"));
2086 			ret = 1; /* Keep old FQS timing. */
2087 			j = jiffies;
2088 			if (time_after(jiffies, rcu_state.jiffies_force_qs))
2089 				j = 1;
2090 			else
2091 				j = rcu_state.jiffies_force_qs - j;
2092 			gf = 0;
2093 		}
2094 	}
2095 }
2096 
2097 /*
2098  * Clean up after the old grace period.
2099  */
2100 static noinline void rcu_gp_cleanup(void)
2101 {
2102 	int cpu;
2103 	bool needgp = false;
2104 	unsigned long gp_duration;
2105 	unsigned long new_gp_seq;
2106 	bool offloaded;
2107 	struct rcu_data *rdp;
2108 	struct rcu_node *rnp = rcu_get_root();
2109 	struct swait_queue_head *sq;
2110 
2111 	WRITE_ONCE(rcu_state.gp_activity, jiffies);
2112 	raw_spin_lock_irq_rcu_node(rnp);
2113 	rcu_state.gp_end = jiffies;
2114 	gp_duration = rcu_state.gp_end - rcu_state.gp_start;
2115 	if (gp_duration > rcu_state.gp_max)
2116 		rcu_state.gp_max = gp_duration;
2117 
2118 	/*
2119 	 * We know the grace period is complete, but to everyone else
2120 	 * it appears to still be ongoing.  But it is also the case
2121 	 * that to everyone else it looks like there is nothing that
2122 	 * they can do to advance the grace period.  It is therefore
2123 	 * safe for us to drop the lock in order to mark the grace
2124 	 * period as completed in all of the rcu_node structures.
2125 	 */
2126 	rcu_poll_gp_seq_end(&rcu_state.gp_seq_polled_snap);
2127 	raw_spin_unlock_irq_rcu_node(rnp);
2128 
2129 	/*
2130 	 * Propagate new ->gp_seq value to rcu_node structures so that
2131 	 * other CPUs don't have to wait until the start of the next grace
2132 	 * period to process their callbacks.  This also avoids some nasty
2133 	 * RCU grace-period initialization races by forcing the end of
2134 	 * the current grace period to be completely recorded in all of
2135 	 * the rcu_node structures before the beginning of the next grace
2136 	 * period is recorded in any of the rcu_node structures.
2137 	 */
2138 	new_gp_seq = rcu_state.gp_seq;
2139 	rcu_seq_end(&new_gp_seq);
2140 	rcu_for_each_node_breadth_first(rnp) {
2141 		raw_spin_lock_irq_rcu_node(rnp);
2142 		if (WARN_ON_ONCE(rcu_preempt_blocked_readers_cgp(rnp)))
2143 			dump_blkd_tasks(rnp, 10);
2144 		WARN_ON_ONCE(rnp->qsmask);
2145 		WRITE_ONCE(rnp->gp_seq, new_gp_seq);
2146 		if (!rnp->parent)
2147 			smp_mb(); // Order against failing poll_state_synchronize_rcu_full().
2148 		rdp = this_cpu_ptr(&rcu_data);
2149 		if (rnp == rdp->mynode)
2150 			needgp = __note_gp_changes(rnp, rdp) || needgp;
2151 		/* smp_mb() provided by prior unlock-lock pair. */
2152 		needgp = rcu_future_gp_cleanup(rnp) || needgp;
2153 		// Reset overload indication for CPUs no longer overloaded
2154 		if (rcu_is_leaf_node(rnp))
2155 			for_each_leaf_node_cpu_mask(rnp, cpu, rnp->cbovldmask) {
2156 				rdp = per_cpu_ptr(&rcu_data, cpu);
2157 				check_cb_ovld_locked(rdp, rnp);
2158 			}
2159 		sq = rcu_nocb_gp_get(rnp);
2160 		raw_spin_unlock_irq_rcu_node(rnp);
2161 		rcu_nocb_gp_cleanup(sq);
2162 		cond_resched_tasks_rcu_qs();
2163 		WRITE_ONCE(rcu_state.gp_activity, jiffies);
2164 		rcu_gp_slow(gp_cleanup_delay);
2165 	}
2166 	rnp = rcu_get_root();
2167 	raw_spin_lock_irq_rcu_node(rnp); /* GP before ->gp_seq update. */
2168 
2169 	/* Declare grace period done, trace first to use old GP number. */
2170 	trace_rcu_grace_period(rcu_state.name, rcu_state.gp_seq, TPS("end"));
2171 	rcu_seq_end(&rcu_state.gp_seq);
2172 	ASSERT_EXCLUSIVE_WRITER(rcu_state.gp_seq);
2173 	WRITE_ONCE(rcu_state.gp_state, RCU_GP_IDLE);
2174 	/* Check for GP requests since above loop. */
2175 	rdp = this_cpu_ptr(&rcu_data);
2176 	if (!needgp && ULONG_CMP_LT(rnp->gp_seq, rnp->gp_seq_needed)) {
2177 		trace_rcu_this_gp(rnp, rdp, rnp->gp_seq_needed,
2178 				  TPS("CleanupMore"));
2179 		needgp = true;
2180 	}
2181 	/* Advance CBs to reduce false positives below. */
2182 	offloaded = rcu_rdp_is_offloaded(rdp);
2183 	if ((offloaded || !rcu_accelerate_cbs(rnp, rdp)) && needgp) {
2184 
2185 		// We get here if a grace period was needed (“needgp”)
2186 		// and the above call to rcu_accelerate_cbs() did not set
2187 		// the RCU_GP_FLAG_INIT bit in ->gp_state (which records
2188 		// the need for another grace period).  The purpose
2189 		// of the “offloaded” check is to avoid invoking
2190 		// rcu_accelerate_cbs() on an offloaded CPU because we do not
2191 		// hold the ->nocb_lock needed to safely access an offloaded
2192 		// ->cblist.  We do not want to acquire that lock because
2193 		// it can be heavily contended during callback floods.
2194 
2195 		WRITE_ONCE(rcu_state.gp_flags, RCU_GP_FLAG_INIT);
2196 		WRITE_ONCE(rcu_state.gp_req_activity, jiffies);
2197 		trace_rcu_grace_period(rcu_state.name, rcu_state.gp_seq, TPS("newreq"));
2198 	} else {
2199 
2200 		// We get here either if there is no need for an
2201 		// additional grace period or if rcu_accelerate_cbs() has
2202 		// already set the RCU_GP_FLAG_INIT bit in ->gp_flags. 
2203 		// So all we need to do is to clear all of the other
2204 		// ->gp_flags bits.
2205 
2206 		WRITE_ONCE(rcu_state.gp_flags, rcu_state.gp_flags & RCU_GP_FLAG_INIT);
2207 	}
2208 	raw_spin_unlock_irq_rcu_node(rnp);
2209 
2210 	// Make synchronize_rcu() users aware of the end of old grace period.
2211 	rcu_sr_normal_gp_cleanup();
2212 
2213 	// If strict, make all CPUs aware of the end of the old grace period.
2214 	if (IS_ENABLED(CONFIG_RCU_STRICT_GRACE_PERIOD))
2215 		on_each_cpu(rcu_strict_gp_boundary, NULL, 0);
2216 }
2217 
2218 /*
2219  * Body of kthread that handles grace periods.
2220  */
2221 static int __noreturn rcu_gp_kthread(void *unused)
2222 {
2223 	rcu_bind_gp_kthread();
2224 	for (;;) {
2225 
2226 		/* Handle grace-period start. */
2227 		for (;;) {
2228 			trace_rcu_grace_period(rcu_state.name, rcu_state.gp_seq,
2229 					       TPS("reqwait"));
2230 			WRITE_ONCE(rcu_state.gp_state, RCU_GP_WAIT_GPS);
2231 			swait_event_idle_exclusive(rcu_state.gp_wq,
2232 					 READ_ONCE(rcu_state.gp_flags) &
2233 					 RCU_GP_FLAG_INIT);
2234 			rcu_gp_torture_wait();
2235 			WRITE_ONCE(rcu_state.gp_state, RCU_GP_DONE_GPS);
2236 			/* Locking provides needed memory barrier. */
2237 			if (rcu_gp_init())
2238 				break;
2239 			cond_resched_tasks_rcu_qs();
2240 			WRITE_ONCE(rcu_state.gp_activity, jiffies);
2241 			WARN_ON(signal_pending(current));
2242 			trace_rcu_grace_period(rcu_state.name, rcu_state.gp_seq,
2243 					       TPS("reqwaitsig"));
2244 		}
2245 
2246 		/* Handle quiescent-state forcing. */
2247 		rcu_gp_fqs_loop();
2248 
2249 		/* Handle grace-period end. */
2250 		WRITE_ONCE(rcu_state.gp_state, RCU_GP_CLEANUP);
2251 		rcu_gp_cleanup();
2252 		WRITE_ONCE(rcu_state.gp_state, RCU_GP_CLEANED);
2253 	}
2254 }
2255 
2256 /*
2257  * Report a full set of quiescent states to the rcu_state data structure.
2258  * Invoke rcu_gp_kthread_wake() to awaken the grace-period kthread if
2259  * another grace period is required.  Whether we wake the grace-period
2260  * kthread or it awakens itself for the next round of quiescent-state
2261  * forcing, that kthread will clean up after the just-completed grace
2262  * period.  Note that the caller must hold rnp->lock, which is released
2263  * before return.
2264  */
2265 static void rcu_report_qs_rsp(unsigned long flags)
2266 	__releases(rcu_get_root()->lock)
2267 {
2268 	raw_lockdep_assert_held_rcu_node(rcu_get_root());
2269 	WARN_ON_ONCE(!rcu_gp_in_progress());
2270 	WRITE_ONCE(rcu_state.gp_flags, rcu_state.gp_flags | RCU_GP_FLAG_FQS);
2271 	raw_spin_unlock_irqrestore_rcu_node(rcu_get_root(), flags);
2272 	rcu_gp_kthread_wake();
2273 }
2274 
2275 /*
2276  * Similar to rcu_report_qs_rdp(), for which it is a helper function.
2277  * Allows quiescent states for a group of CPUs to be reported at one go
2278  * to the specified rcu_node structure, though all the CPUs in the group
2279  * must be represented by the same rcu_node structure (which need not be a
2280  * leaf rcu_node structure, though it often will be).  The gps parameter
2281  * is the grace-period snapshot, which means that the quiescent states
2282  * are valid only if rnp->gp_seq is equal to gps.  That structure's lock
2283  * must be held upon entry, and it is released before return.
2284  *
2285  * As a special case, if mask is zero, the bit-already-cleared check is
2286  * disabled.  This allows propagating quiescent state due to resumed tasks
2287  * during grace-period initialization.
2288  */
2289 static void rcu_report_qs_rnp(unsigned long mask, struct rcu_node *rnp,
2290 			      unsigned long gps, unsigned long flags)
2291 	__releases(rnp->lock)
2292 {
2293 	unsigned long oldmask = 0;
2294 	struct rcu_node *rnp_c;
2295 
2296 	raw_lockdep_assert_held_rcu_node(rnp);
2297 
2298 	/* Walk up the rcu_node hierarchy. */
2299 	for (;;) {
2300 		if ((!(rnp->qsmask & mask) && mask) || rnp->gp_seq != gps) {
2301 
2302 			/*
2303 			 * Our bit has already been cleared, or the
2304 			 * relevant grace period is already over, so done.
2305 			 */
2306 			raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
2307 			return;
2308 		}
2309 		WARN_ON_ONCE(oldmask); /* Any child must be all zeroed! */
2310 		WARN_ON_ONCE(!rcu_is_leaf_node(rnp) &&
2311 			     rcu_preempt_blocked_readers_cgp(rnp));
2312 		WRITE_ONCE(rnp->qsmask, rnp->qsmask & ~mask);
2313 		trace_rcu_quiescent_state_report(rcu_state.name, rnp->gp_seq,
2314 						 mask, rnp->qsmask, rnp->level,
2315 						 rnp->grplo, rnp->grphi,
2316 						 !!rnp->gp_tasks);
2317 		if (rnp->qsmask != 0 || rcu_preempt_blocked_readers_cgp(rnp)) {
2318 
2319 			/* Other bits still set at this level, so done. */
2320 			raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
2321 			return;
2322 		}
2323 		rnp->completedqs = rnp->gp_seq;
2324 		mask = rnp->grpmask;
2325 		if (rnp->parent == NULL) {
2326 
2327 			/* No more levels.  Exit loop holding root lock. */
2328 
2329 			break;
2330 		}
2331 		raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
2332 		rnp_c = rnp;
2333 		rnp = rnp->parent;
2334 		raw_spin_lock_irqsave_rcu_node(rnp, flags);
2335 		oldmask = READ_ONCE(rnp_c->qsmask);
2336 	}
2337 
2338 	/*
2339 	 * Get here if we are the last CPU to pass through a quiescent
2340 	 * state for this grace period.  Invoke rcu_report_qs_rsp()
2341 	 * to clean up and start the next grace period if one is needed.
2342 	 */
2343 	rcu_report_qs_rsp(flags); /* releases rnp->lock. */
2344 }
2345 
2346 /*
2347  * Record a quiescent state for all tasks that were previously queued
2348  * on the specified rcu_node structure and that were blocking the current
2349  * RCU grace period.  The caller must hold the corresponding rnp->lock with
2350  * irqs disabled, and this lock is released upon return, but irqs remain
2351  * disabled.
2352  */
2353 static void __maybe_unused
2354 rcu_report_unblock_qs_rnp(struct rcu_node *rnp, unsigned long flags)
2355 	__releases(rnp->lock)
2356 {
2357 	unsigned long gps;
2358 	unsigned long mask;
2359 	struct rcu_node *rnp_p;
2360 
2361 	raw_lockdep_assert_held_rcu_node(rnp);
2362 	if (WARN_ON_ONCE(!IS_ENABLED(CONFIG_PREEMPT_RCU)) ||
2363 	    WARN_ON_ONCE(rcu_preempt_blocked_readers_cgp(rnp)) ||
2364 	    rnp->qsmask != 0) {
2365 		raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
2366 		return;  /* Still need more quiescent states! */
2367 	}
2368 
2369 	rnp->completedqs = rnp->gp_seq;
2370 	rnp_p = rnp->parent;
2371 	if (rnp_p == NULL) {
2372 		/*
2373 		 * Only one rcu_node structure in the tree, so don't
2374 		 * try to report up to its nonexistent parent!
2375 		 */
2376 		rcu_report_qs_rsp(flags);
2377 		return;
2378 	}
2379 
2380 	/* Report up the rest of the hierarchy, tracking current ->gp_seq. */
2381 	gps = rnp->gp_seq;
2382 	mask = rnp->grpmask;
2383 	raw_spin_unlock_rcu_node(rnp);	/* irqs remain disabled. */
2384 	raw_spin_lock_rcu_node(rnp_p);	/* irqs already disabled. */
2385 	rcu_report_qs_rnp(mask, rnp_p, gps, flags);
2386 }
2387 
2388 /*
2389  * Record a quiescent state for the specified CPU to that CPU's rcu_data
2390  * structure.  This must be called from the specified CPU.
2391  */
2392 static void
2393 rcu_report_qs_rdp(struct rcu_data *rdp)
2394 {
2395 	unsigned long flags;
2396 	unsigned long mask;
2397 	struct rcu_node *rnp;
2398 
2399 	WARN_ON_ONCE(rdp->cpu != smp_processor_id());
2400 	rnp = rdp->mynode;
2401 	raw_spin_lock_irqsave_rcu_node(rnp, flags);
2402 	if (rdp->cpu_no_qs.b.norm || rdp->gp_seq != rnp->gp_seq ||
2403 	    rdp->gpwrap) {
2404 
2405 		/*
2406 		 * The grace period in which this quiescent state was
2407 		 * recorded has ended, so don't report it upwards.
2408 		 * We will instead need a new quiescent state that lies
2409 		 * within the current grace period.
2410 		 */
2411 		rdp->cpu_no_qs.b.norm = true;	/* need qs for new gp. */
2412 		raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
2413 		return;
2414 	}
2415 	mask = rdp->grpmask;
2416 	rdp->core_needs_qs = false;
2417 	if ((rnp->qsmask & mask) == 0) {
2418 		raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
2419 	} else {
2420 		/*
2421 		 * This GP can't end until cpu checks in, so all of our
2422 		 * callbacks can be processed during the next GP.
2423 		 *
2424 		 * NOCB kthreads have their own way to deal with that...
2425 		 */
2426 		if (!rcu_rdp_is_offloaded(rdp)) {
2427 			/*
2428 			 * The current GP has not yet ended, so it
2429 			 * should not be possible for rcu_accelerate_cbs()
2430 			 * to return true.  So complain, but don't awaken.
2431 			 */
2432 			WARN_ON_ONCE(rcu_accelerate_cbs(rnp, rdp));
2433 		}
2434 
2435 		rcu_disable_urgency_upon_qs(rdp);
2436 		rcu_report_qs_rnp(mask, rnp, rnp->gp_seq, flags);
2437 		/* ^^^ Released rnp->lock */
2438 	}
2439 }
2440 
2441 /*
2442  * Check to see if there is a new grace period of which this CPU
2443  * is not yet aware, and if so, set up local rcu_data state for it.
2444  * Otherwise, see if this CPU has just passed through its first
2445  * quiescent state for this grace period, and record that fact if so.
2446  */
2447 static void
2448 rcu_check_quiescent_state(struct rcu_data *rdp)
2449 {
2450 	/* Check for grace-period ends and beginnings. */
2451 	note_gp_changes(rdp);
2452 
2453 	/*
2454 	 * Does this CPU still need to do its part for current grace period?
2455 	 * If no, return and let the other CPUs do their part as well.
2456 	 */
2457 	if (!rdp->core_needs_qs)
2458 		return;
2459 
2460 	/*
2461 	 * Was there a quiescent state since the beginning of the grace
2462 	 * period? If no, then exit and wait for the next call.
2463 	 */
2464 	if (rdp->cpu_no_qs.b.norm)
2465 		return;
2466 
2467 	/*
2468 	 * Tell RCU we are done (but rcu_report_qs_rdp() will be the
2469 	 * judge of that).
2470 	 */
2471 	rcu_report_qs_rdp(rdp);
2472 }
2473 
2474 /* Return true if callback-invocation time limit exceeded. */
2475 static bool rcu_do_batch_check_time(long count, long tlimit,
2476 				    bool jlimit_check, unsigned long jlimit)
2477 {
2478 	// Invoke local_clock() only once per 32 consecutive callbacks.
2479 	return unlikely(tlimit) &&
2480 	       (!likely(count & 31) ||
2481 		(IS_ENABLED(CONFIG_RCU_DOUBLE_CHECK_CB_TIME) &&
2482 		 jlimit_check && time_after(jiffies, jlimit))) &&
2483 	       local_clock() >= tlimit;
2484 }
2485 
2486 /*
2487  * Invoke any RCU callbacks that have made it to the end of their grace
2488  * period.  Throttle as specified by rdp->blimit.
2489  */
2490 static void rcu_do_batch(struct rcu_data *rdp)
2491 {
2492 	long bl;
2493 	long count = 0;
2494 	int div;
2495 	bool __maybe_unused empty;
2496 	unsigned long flags;
2497 	unsigned long jlimit;
2498 	bool jlimit_check = false;
2499 	long pending;
2500 	struct rcu_cblist rcl = RCU_CBLIST_INITIALIZER(rcl);
2501 	struct rcu_head *rhp;
2502 	long tlimit = 0;
2503 
2504 	/* If no callbacks are ready, just return. */
2505 	if (!rcu_segcblist_ready_cbs(&rdp->cblist)) {
2506 		trace_rcu_batch_start(rcu_state.name,
2507 				      rcu_segcblist_n_cbs(&rdp->cblist), 0);
2508 		trace_rcu_batch_end(rcu_state.name, 0,
2509 				    !rcu_segcblist_empty(&rdp->cblist),
2510 				    need_resched(), is_idle_task(current),
2511 				    rcu_is_callbacks_kthread(rdp));
2512 		return;
2513 	}
2514 
2515 	/*
2516 	 * Extract the list of ready callbacks, disabling IRQs to prevent
2517 	 * races with call_rcu() from interrupt handlers.  Leave the
2518 	 * callback counts, as rcu_barrier() needs to be conservative.
2519 	 *
2520 	 * Callbacks execution is fully ordered against preceding grace period
2521 	 * completion (materialized by rnp->gp_seq update) thanks to the
2522 	 * smp_mb__after_unlock_lock() upon node locking required for callbacks
2523 	 * advancing. In NOCB mode this ordering is then further relayed through
2524 	 * the nocb locking that protects both callbacks advancing and extraction.
2525 	 */
2526 	rcu_nocb_lock_irqsave(rdp, flags);
2527 	WARN_ON_ONCE(cpu_is_offline(smp_processor_id()));
2528 	pending = rcu_segcblist_get_seglen(&rdp->cblist, RCU_DONE_TAIL);
2529 	div = READ_ONCE(rcu_divisor);
2530 	div = div < 0 ? 7 : div > sizeof(long) * 8 - 2 ? sizeof(long) * 8 - 2 : div;
2531 	bl = max(rdp->blimit, pending >> div);
2532 	if ((in_serving_softirq() || rdp->rcu_cpu_kthread_status == RCU_KTHREAD_RUNNING) &&
2533 	    (IS_ENABLED(CONFIG_RCU_DOUBLE_CHECK_CB_TIME) || unlikely(bl > 100))) {
2534 		const long npj = NSEC_PER_SEC / HZ;
2535 		long rrn = READ_ONCE(rcu_resched_ns);
2536 
2537 		rrn = rrn < NSEC_PER_MSEC ? NSEC_PER_MSEC : rrn > NSEC_PER_SEC ? NSEC_PER_SEC : rrn;
2538 		tlimit = local_clock() + rrn;
2539 		jlimit = jiffies + (rrn + npj + 1) / npj;
2540 		jlimit_check = true;
2541 	}
2542 	trace_rcu_batch_start(rcu_state.name,
2543 			      rcu_segcblist_n_cbs(&rdp->cblist), bl);
2544 	rcu_segcblist_extract_done_cbs(&rdp->cblist, &rcl);
2545 	if (rcu_rdp_is_offloaded(rdp))
2546 		rdp->qlen_last_fqs_check = rcu_segcblist_n_cbs(&rdp->cblist);
2547 
2548 	trace_rcu_segcb_stats(&rdp->cblist, TPS("SegCbDequeued"));
2549 	rcu_nocb_unlock_irqrestore(rdp, flags);
2550 
2551 	/* Invoke callbacks. */
2552 	tick_dep_set_task(current, TICK_DEP_BIT_RCU);
2553 	rhp = rcu_cblist_dequeue(&rcl);
2554 
2555 	for (; rhp; rhp = rcu_cblist_dequeue(&rcl)) {
2556 		rcu_callback_t f;
2557 
2558 		count++;
2559 		debug_rcu_head_unqueue(rhp);
2560 
2561 		rcu_lock_acquire(&rcu_callback_map);
2562 		trace_rcu_invoke_callback(rcu_state.name, rhp);
2563 
2564 		f = rhp->func;
2565 		debug_rcu_head_callback(rhp);
2566 		WRITE_ONCE(rhp->func, (rcu_callback_t)0L);
2567 		f(rhp);
2568 
2569 		rcu_lock_release(&rcu_callback_map);
2570 
2571 		/*
2572 		 * Stop only if limit reached and CPU has something to do.
2573 		 */
2574 		if (in_serving_softirq()) {
2575 			if (count >= bl && (need_resched() || !is_idle_task(current)))
2576 				break;
2577 			/*
2578 			 * Make sure we don't spend too much time here and deprive other
2579 			 * softirq vectors of CPU cycles.
2580 			 */
2581 			if (rcu_do_batch_check_time(count, tlimit, jlimit_check, jlimit))
2582 				break;
2583 		} else {
2584 			// In rcuc/rcuoc context, so no worries about
2585 			// depriving other softirq vectors of CPU cycles.
2586 			local_bh_enable();
2587 			lockdep_assert_irqs_enabled();
2588 			cond_resched_tasks_rcu_qs();
2589 			lockdep_assert_irqs_enabled();
2590 			local_bh_disable();
2591 			// But rcuc kthreads can delay quiescent-state
2592 			// reporting, so check time limits for them.
2593 			if (rdp->rcu_cpu_kthread_status == RCU_KTHREAD_RUNNING &&
2594 			    rcu_do_batch_check_time(count, tlimit, jlimit_check, jlimit)) {
2595 				rdp->rcu_cpu_has_work = 1;
2596 				break;
2597 			}
2598 		}
2599 	}
2600 
2601 	rcu_nocb_lock_irqsave(rdp, flags);
2602 	rdp->n_cbs_invoked += count;
2603 	trace_rcu_batch_end(rcu_state.name, count, !!rcl.head, need_resched(),
2604 			    is_idle_task(current), rcu_is_callbacks_kthread(rdp));
2605 
2606 	/* Update counts and requeue any remaining callbacks. */
2607 	rcu_segcblist_insert_done_cbs(&rdp->cblist, &rcl);
2608 	rcu_segcblist_add_len(&rdp->cblist, -count);
2609 
2610 	/* Reinstate batch limit if we have worked down the excess. */
2611 	count = rcu_segcblist_n_cbs(&rdp->cblist);
2612 	if (rdp->blimit >= DEFAULT_MAX_RCU_BLIMIT && count <= qlowmark)
2613 		rdp->blimit = blimit;
2614 
2615 	/* Reset ->qlen_last_fqs_check trigger if enough CBs have drained. */
2616 	if (count == 0 && rdp->qlen_last_fqs_check != 0) {
2617 		rdp->qlen_last_fqs_check = 0;
2618 		rdp->n_force_qs_snap = READ_ONCE(rcu_state.n_force_qs);
2619 	} else if (count < rdp->qlen_last_fqs_check - qhimark)
2620 		rdp->qlen_last_fqs_check = count;
2621 
2622 	/*
2623 	 * The following usually indicates a double call_rcu().  To track
2624 	 * this down, try building with CONFIG_DEBUG_OBJECTS_RCU_HEAD=y.
2625 	 */
2626 	empty = rcu_segcblist_empty(&rdp->cblist);
2627 	WARN_ON_ONCE(count == 0 && !empty);
2628 	WARN_ON_ONCE(!IS_ENABLED(CONFIG_RCU_NOCB_CPU) &&
2629 		     count != 0 && empty);
2630 	WARN_ON_ONCE(count == 0 && rcu_segcblist_n_segment_cbs(&rdp->cblist) != 0);
2631 	WARN_ON_ONCE(!empty && rcu_segcblist_n_segment_cbs(&rdp->cblist) == 0);
2632 
2633 	rcu_nocb_unlock_irqrestore(rdp, flags);
2634 
2635 	tick_dep_clear_task(current, TICK_DEP_BIT_RCU);
2636 }
2637 
2638 /*
2639  * This function is invoked from each scheduling-clock interrupt,
2640  * and checks to see if this CPU is in a non-context-switch quiescent
2641  * state, for example, user mode or idle loop.  It also schedules RCU
2642  * core processing.  If the current grace period has gone on too long,
2643  * it will ask the scheduler to manufacture a context switch for the sole
2644  * purpose of providing the needed quiescent state.
2645  */
2646 void rcu_sched_clock_irq(int user)
2647 {
2648 	unsigned long j;
2649 
2650 	if (IS_ENABLED(CONFIG_PROVE_RCU)) {
2651 		j = jiffies;
2652 		WARN_ON_ONCE(time_before(j, __this_cpu_read(rcu_data.last_sched_clock)));
2653 		__this_cpu_write(rcu_data.last_sched_clock, j);
2654 	}
2655 	trace_rcu_utilization(TPS("Start scheduler-tick"));
2656 	lockdep_assert_irqs_disabled();
2657 	raw_cpu_inc(rcu_data.ticks_this_gp);
2658 	/* The load-acquire pairs with the store-release setting to true. */
2659 	if (smp_load_acquire(this_cpu_ptr(&rcu_data.rcu_urgent_qs))) {
2660 		/* Idle and userspace execution already are quiescent states. */
2661 		if (!rcu_is_cpu_rrupt_from_idle() && !user) {
2662 			set_tsk_need_resched(current);
2663 			set_preempt_need_resched();
2664 		}
2665 		__this_cpu_write(rcu_data.rcu_urgent_qs, false);
2666 	}
2667 	rcu_flavor_sched_clock_irq(user);
2668 	if (rcu_pending(user))
2669 		invoke_rcu_core();
2670 	if (user || rcu_is_cpu_rrupt_from_idle())
2671 		rcu_note_voluntary_context_switch(current);
2672 	lockdep_assert_irqs_disabled();
2673 
2674 	trace_rcu_utilization(TPS("End scheduler-tick"));
2675 }
2676 
2677 /*
2678  * Scan the leaf rcu_node structures.  For each structure on which all
2679  * CPUs have reported a quiescent state and on which there are tasks
2680  * blocking the current grace period, initiate RCU priority boosting.
2681  * Otherwise, invoke the specified function to check dyntick state for
2682  * each CPU that has not yet reported a quiescent state.
2683  */
2684 static void force_qs_rnp(int (*f)(struct rcu_data *rdp))
2685 {
2686 	int cpu;
2687 	unsigned long flags;
2688 	struct rcu_node *rnp;
2689 
2690 	rcu_state.cbovld = rcu_state.cbovldnext;
2691 	rcu_state.cbovldnext = false;
2692 	rcu_for_each_leaf_node(rnp) {
2693 		unsigned long mask = 0;
2694 		unsigned long rsmask = 0;
2695 
2696 		cond_resched_tasks_rcu_qs();
2697 		raw_spin_lock_irqsave_rcu_node(rnp, flags);
2698 		rcu_state.cbovldnext |= !!rnp->cbovldmask;
2699 		if (rnp->qsmask == 0) {
2700 			if (rcu_preempt_blocked_readers_cgp(rnp)) {
2701 				/*
2702 				 * No point in scanning bits because they
2703 				 * are all zero.  But we might need to
2704 				 * priority-boost blocked readers.
2705 				 */
2706 				rcu_initiate_boost(rnp, flags);
2707 				/* rcu_initiate_boost() releases rnp->lock */
2708 				continue;
2709 			}
2710 			raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
2711 			continue;
2712 		}
2713 		for_each_leaf_node_cpu_mask(rnp, cpu, rnp->qsmask) {
2714 			struct rcu_data *rdp;
2715 			int ret;
2716 
2717 			rdp = per_cpu_ptr(&rcu_data, cpu);
2718 			ret = f(rdp);
2719 			if (ret > 0) {
2720 				mask |= rdp->grpmask;
2721 				rcu_disable_urgency_upon_qs(rdp);
2722 			}
2723 			if (ret < 0)
2724 				rsmask |= rdp->grpmask;
2725 		}
2726 		if (mask != 0) {
2727 			/* Idle/offline CPUs, report (releases rnp->lock). */
2728 			rcu_report_qs_rnp(mask, rnp, rnp->gp_seq, flags);
2729 		} else {
2730 			/* Nothing to do here, so just drop the lock. */
2731 			raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
2732 		}
2733 
2734 		for_each_leaf_node_cpu_mask(rnp, cpu, rsmask)
2735 			resched_cpu(cpu);
2736 	}
2737 }
2738 
2739 /*
2740  * Force quiescent states on reluctant CPUs, and also detect which
2741  * CPUs are in dyntick-idle mode.
2742  */
2743 void rcu_force_quiescent_state(void)
2744 {
2745 	unsigned long flags;
2746 	bool ret;
2747 	struct rcu_node *rnp;
2748 	struct rcu_node *rnp_old = NULL;
2749 
2750 	if (!rcu_gp_in_progress())
2751 		return;
2752 	/* Funnel through hierarchy to reduce memory contention. */
2753 	rnp = raw_cpu_read(rcu_data.mynode);
2754 	for (; rnp != NULL; rnp = rnp->parent) {
2755 		ret = (READ_ONCE(rcu_state.gp_flags) & RCU_GP_FLAG_FQS) ||
2756 		       !raw_spin_trylock(&rnp->fqslock);
2757 		if (rnp_old != NULL)
2758 			raw_spin_unlock(&rnp_old->fqslock);
2759 		if (ret)
2760 			return;
2761 		rnp_old = rnp;
2762 	}
2763 	/* rnp_old == rcu_get_root(), rnp == NULL. */
2764 
2765 	/* Reached the root of the rcu_node tree, acquire lock. */
2766 	raw_spin_lock_irqsave_rcu_node(rnp_old, flags);
2767 	raw_spin_unlock(&rnp_old->fqslock);
2768 	if (READ_ONCE(rcu_state.gp_flags) & RCU_GP_FLAG_FQS) {
2769 		raw_spin_unlock_irqrestore_rcu_node(rnp_old, flags);
2770 		return;  /* Someone beat us to it. */
2771 	}
2772 	WRITE_ONCE(rcu_state.gp_flags, rcu_state.gp_flags | RCU_GP_FLAG_FQS);
2773 	raw_spin_unlock_irqrestore_rcu_node(rnp_old, flags);
2774 	rcu_gp_kthread_wake();
2775 }
2776 EXPORT_SYMBOL_GPL(rcu_force_quiescent_state);
2777 
2778 // Workqueue handler for an RCU reader for kernels enforcing struct RCU
2779 // grace periods.
2780 static void strict_work_handler(struct work_struct *work)
2781 {
2782 	rcu_read_lock();
2783 	rcu_read_unlock();
2784 }
2785 
2786 /* Perform RCU core processing work for the current CPU.  */
2787 static __latent_entropy void rcu_core(void)
2788 {
2789 	unsigned long flags;
2790 	struct rcu_data *rdp = raw_cpu_ptr(&rcu_data);
2791 	struct rcu_node *rnp = rdp->mynode;
2792 
2793 	if (cpu_is_offline(smp_processor_id()))
2794 		return;
2795 	trace_rcu_utilization(TPS("Start RCU core"));
2796 	WARN_ON_ONCE(!rdp->beenonline);
2797 
2798 	/* Report any deferred quiescent states if preemption enabled. */
2799 	if (IS_ENABLED(CONFIG_PREEMPT_COUNT) && (!(preempt_count() & PREEMPT_MASK))) {
2800 		rcu_preempt_deferred_qs(current);
2801 	} else if (rcu_preempt_need_deferred_qs(current)) {
2802 		set_tsk_need_resched(current);
2803 		set_preempt_need_resched();
2804 	}
2805 
2806 	/* Update RCU state based on any recent quiescent states. */
2807 	rcu_check_quiescent_state(rdp);
2808 
2809 	/* No grace period and unregistered callbacks? */
2810 	if (!rcu_gp_in_progress() &&
2811 	    rcu_segcblist_is_enabled(&rdp->cblist) && !rcu_rdp_is_offloaded(rdp)) {
2812 		local_irq_save(flags);
2813 		if (!rcu_segcblist_restempty(&rdp->cblist, RCU_NEXT_READY_TAIL))
2814 			rcu_accelerate_cbs_unlocked(rnp, rdp);
2815 		local_irq_restore(flags);
2816 	}
2817 
2818 	rcu_check_gp_start_stall(rnp, rdp, rcu_jiffies_till_stall_check());
2819 
2820 	/* If there are callbacks ready, invoke them. */
2821 	if (!rcu_rdp_is_offloaded(rdp) && rcu_segcblist_ready_cbs(&rdp->cblist) &&
2822 	    likely(READ_ONCE(rcu_scheduler_fully_active))) {
2823 		rcu_do_batch(rdp);
2824 		/* Re-invoke RCU core processing if there are callbacks remaining. */
2825 		if (rcu_segcblist_ready_cbs(&rdp->cblist))
2826 			invoke_rcu_core();
2827 	}
2828 
2829 	/* Do any needed deferred wakeups of rcuo kthreads. */
2830 	do_nocb_deferred_wakeup(rdp);
2831 	trace_rcu_utilization(TPS("End RCU core"));
2832 
2833 	// If strict GPs, schedule an RCU reader in a clean environment.
2834 	if (IS_ENABLED(CONFIG_RCU_STRICT_GRACE_PERIOD))
2835 		queue_work_on(rdp->cpu, rcu_gp_wq, &rdp->strict_work);
2836 }
2837 
2838 static void rcu_core_si(void)
2839 {
2840 	rcu_core();
2841 }
2842 
2843 static void rcu_wake_cond(struct task_struct *t, int status)
2844 {
2845 	/*
2846 	 * If the thread is yielding, only wake it when this
2847 	 * is invoked from idle
2848 	 */
2849 	if (t && (status != RCU_KTHREAD_YIELDING || is_idle_task(current)))
2850 		wake_up_process(t);
2851 }
2852 
2853 static void invoke_rcu_core_kthread(void)
2854 {
2855 	struct task_struct *t;
2856 	unsigned long flags;
2857 
2858 	local_irq_save(flags);
2859 	__this_cpu_write(rcu_data.rcu_cpu_has_work, 1);
2860 	t = __this_cpu_read(rcu_data.rcu_cpu_kthread_task);
2861 	if (t != NULL && t != current)
2862 		rcu_wake_cond(t, __this_cpu_read(rcu_data.rcu_cpu_kthread_status));
2863 	local_irq_restore(flags);
2864 }
2865 
2866 /*
2867  * Wake up this CPU's rcuc kthread to do RCU core processing.
2868  */
2869 static void invoke_rcu_core(void)
2870 {
2871 	if (!cpu_online(smp_processor_id()))
2872 		return;
2873 	if (use_softirq)
2874 		raise_softirq(RCU_SOFTIRQ);
2875 	else
2876 		invoke_rcu_core_kthread();
2877 }
2878 
2879 static void rcu_cpu_kthread_park(unsigned int cpu)
2880 {
2881 	per_cpu(rcu_data.rcu_cpu_kthread_status, cpu) = RCU_KTHREAD_OFFCPU;
2882 }
2883 
2884 static int rcu_cpu_kthread_should_run(unsigned int cpu)
2885 {
2886 	return __this_cpu_read(rcu_data.rcu_cpu_has_work);
2887 }
2888 
2889 /*
2890  * Per-CPU kernel thread that invokes RCU callbacks.  This replaces
2891  * the RCU softirq used in configurations of RCU that do not support RCU
2892  * priority boosting.
2893  */
2894 static void rcu_cpu_kthread(unsigned int cpu)
2895 {
2896 	unsigned int *statusp = this_cpu_ptr(&rcu_data.rcu_cpu_kthread_status);
2897 	char work, *workp = this_cpu_ptr(&rcu_data.rcu_cpu_has_work);
2898 	unsigned long *j = this_cpu_ptr(&rcu_data.rcuc_activity);
2899 	int spincnt;
2900 
2901 	trace_rcu_utilization(TPS("Start CPU kthread@rcu_run"));
2902 	for (spincnt = 0; spincnt < 10; spincnt++) {
2903 		WRITE_ONCE(*j, jiffies);
2904 		local_bh_disable();
2905 		*statusp = RCU_KTHREAD_RUNNING;
2906 		local_irq_disable();
2907 		work = *workp;
2908 		WRITE_ONCE(*workp, 0);
2909 		local_irq_enable();
2910 		if (work)
2911 			rcu_core();
2912 		local_bh_enable();
2913 		if (!READ_ONCE(*workp)) {
2914 			trace_rcu_utilization(TPS("End CPU kthread@rcu_wait"));
2915 			*statusp = RCU_KTHREAD_WAITING;
2916 			return;
2917 		}
2918 	}
2919 	*statusp = RCU_KTHREAD_YIELDING;
2920 	trace_rcu_utilization(TPS("Start CPU kthread@rcu_yield"));
2921 	schedule_timeout_idle(2);
2922 	trace_rcu_utilization(TPS("End CPU kthread@rcu_yield"));
2923 	*statusp = RCU_KTHREAD_WAITING;
2924 	WRITE_ONCE(*j, jiffies);
2925 }
2926 
2927 static struct smp_hotplug_thread rcu_cpu_thread_spec = {
2928 	.store			= &rcu_data.rcu_cpu_kthread_task,
2929 	.thread_should_run	= rcu_cpu_kthread_should_run,
2930 	.thread_fn		= rcu_cpu_kthread,
2931 	.thread_comm		= "rcuc/%u",
2932 	.setup			= rcu_cpu_kthread_setup,
2933 	.park			= rcu_cpu_kthread_park,
2934 };
2935 
2936 /*
2937  * Spawn per-CPU RCU core processing kthreads.
2938  */
2939 static int __init rcu_spawn_core_kthreads(void)
2940 {
2941 	int cpu;
2942 
2943 	for_each_possible_cpu(cpu)
2944 		per_cpu(rcu_data.rcu_cpu_has_work, cpu) = 0;
2945 	if (use_softirq)
2946 		return 0;
2947 	WARN_ONCE(smpboot_register_percpu_thread(&rcu_cpu_thread_spec),
2948 		  "%s: Could not start rcuc kthread, OOM is now expected behavior\n", __func__);
2949 	return 0;
2950 }
2951 
2952 static void rcutree_enqueue(struct rcu_data *rdp, struct rcu_head *head, rcu_callback_t func)
2953 {
2954 	rcu_segcblist_enqueue(&rdp->cblist, head);
2955 	if (__is_kvfree_rcu_offset((unsigned long)func))
2956 		trace_rcu_kvfree_callback(rcu_state.name, head,
2957 					 (unsigned long)func,
2958 					 rcu_segcblist_n_cbs(&rdp->cblist));
2959 	else
2960 		trace_rcu_callback(rcu_state.name, head,
2961 				   rcu_segcblist_n_cbs(&rdp->cblist));
2962 	trace_rcu_segcb_stats(&rdp->cblist, TPS("SegCBQueued"));
2963 }
2964 
2965 /*
2966  * Handle any core-RCU processing required by a call_rcu() invocation.
2967  */
2968 static void call_rcu_core(struct rcu_data *rdp, struct rcu_head *head,
2969 			  rcu_callback_t func, unsigned long flags)
2970 {
2971 	rcutree_enqueue(rdp, head, func);
2972 	/*
2973 	 * If called from an extended quiescent state, invoke the RCU
2974 	 * core in order to force a re-evaluation of RCU's idleness.
2975 	 */
2976 	if (!rcu_is_watching())
2977 		invoke_rcu_core();
2978 
2979 	/* If interrupts were disabled or CPU offline, don't invoke RCU core. */
2980 	if (irqs_disabled_flags(flags) || cpu_is_offline(smp_processor_id()))
2981 		return;
2982 
2983 	/*
2984 	 * Force the grace period if too many callbacks or too long waiting.
2985 	 * Enforce hysteresis, and don't invoke rcu_force_quiescent_state()
2986 	 * if some other CPU has recently done so.  Also, don't bother
2987 	 * invoking rcu_force_quiescent_state() if the newly enqueued callback
2988 	 * is the only one waiting for a grace period to complete.
2989 	 */
2990 	if (unlikely(rcu_segcblist_n_cbs(&rdp->cblist) >
2991 		     rdp->qlen_last_fqs_check + qhimark)) {
2992 
2993 		/* Are we ignoring a completed grace period? */
2994 		note_gp_changes(rdp);
2995 
2996 		/* Start a new grace period if one not already started. */
2997 		if (!rcu_gp_in_progress()) {
2998 			rcu_accelerate_cbs_unlocked(rdp->mynode, rdp);
2999 		} else {
3000 			/* Give the grace period a kick. */
3001 			rdp->blimit = DEFAULT_MAX_RCU_BLIMIT;
3002 			if (READ_ONCE(rcu_state.n_force_qs) == rdp->n_force_qs_snap &&
3003 			    rcu_segcblist_first_pend_cb(&rdp->cblist) != head)
3004 				rcu_force_quiescent_state();
3005 			rdp->n_force_qs_snap = READ_ONCE(rcu_state.n_force_qs);
3006 			rdp->qlen_last_fqs_check = rcu_segcblist_n_cbs(&rdp->cblist);
3007 		}
3008 	}
3009 }
3010 
3011 /*
3012  * RCU callback function to leak a callback.
3013  */
3014 static void rcu_leak_callback(struct rcu_head *rhp)
3015 {
3016 }
3017 
3018 /*
3019  * Check and if necessary update the leaf rcu_node structure's
3020  * ->cbovldmask bit corresponding to the current CPU based on that CPU's
3021  * number of queued RCU callbacks.  The caller must hold the leaf rcu_node
3022  * structure's ->lock.
3023  */
3024 static void check_cb_ovld_locked(struct rcu_data *rdp, struct rcu_node *rnp)
3025 {
3026 	raw_lockdep_assert_held_rcu_node(rnp);
3027 	if (qovld_calc <= 0)
3028 		return; // Early boot and wildcard value set.
3029 	if (rcu_segcblist_n_cbs(&rdp->cblist) >= qovld_calc)
3030 		WRITE_ONCE(rnp->cbovldmask, rnp->cbovldmask | rdp->grpmask);
3031 	else
3032 		WRITE_ONCE(rnp->cbovldmask, rnp->cbovldmask & ~rdp->grpmask);
3033 }
3034 
3035 /*
3036  * Check and if necessary update the leaf rcu_node structure's
3037  * ->cbovldmask bit corresponding to the current CPU based on that CPU's
3038  * number of queued RCU callbacks.  No locks need be held, but the
3039  * caller must have disabled interrupts.
3040  *
3041  * Note that this function ignores the possibility that there are a lot
3042  * of callbacks all of which have already seen the end of their respective
3043  * grace periods.  This omission is due to the need for no-CBs CPUs to
3044  * be holding ->nocb_lock to do this check, which is too heavy for a
3045  * common-case operation.
3046  */
3047 static void check_cb_ovld(struct rcu_data *rdp)
3048 {
3049 	struct rcu_node *const rnp = rdp->mynode;
3050 
3051 	if (qovld_calc <= 0 ||
3052 	    ((rcu_segcblist_n_cbs(&rdp->cblist) >= qovld_calc) ==
3053 	     !!(READ_ONCE(rnp->cbovldmask) & rdp->grpmask)))
3054 		return; // Early boot wildcard value or already set correctly.
3055 	raw_spin_lock_rcu_node(rnp);
3056 	check_cb_ovld_locked(rdp, rnp);
3057 	raw_spin_unlock_rcu_node(rnp);
3058 }
3059 
3060 static void
3061 __call_rcu_common(struct rcu_head *head, rcu_callback_t func, bool lazy_in)
3062 {
3063 	static atomic_t doublefrees;
3064 	unsigned long flags;
3065 	bool lazy;
3066 	struct rcu_data *rdp;
3067 
3068 	/* Misaligned rcu_head! */
3069 	WARN_ON_ONCE((unsigned long)head & (sizeof(void *) - 1));
3070 
3071 	if (debug_rcu_head_queue(head)) {
3072 		/*
3073 		 * Probable double call_rcu(), so leak the callback.
3074 		 * Use rcu:rcu_callback trace event to find the previous
3075 		 * time callback was passed to call_rcu().
3076 		 */
3077 		if (atomic_inc_return(&doublefrees) < 4) {
3078 			pr_err("%s(): Double-freed CB %p->%pS()!!!  ", __func__, head, head->func);
3079 			mem_dump_obj(head);
3080 		}
3081 		WRITE_ONCE(head->func, rcu_leak_callback);
3082 		return;
3083 	}
3084 	head->func = func;
3085 	head->next = NULL;
3086 	kasan_record_aux_stack_noalloc(head);
3087 	local_irq_save(flags);
3088 	rdp = this_cpu_ptr(&rcu_data);
3089 	lazy = lazy_in && !rcu_async_should_hurry();
3090 
3091 	/* Add the callback to our list. */
3092 	if (unlikely(!rcu_segcblist_is_enabled(&rdp->cblist))) {
3093 		// This can trigger due to call_rcu() from offline CPU:
3094 		WARN_ON_ONCE(rcu_scheduler_active != RCU_SCHEDULER_INACTIVE);
3095 		WARN_ON_ONCE(!rcu_is_watching());
3096 		// Very early boot, before rcu_init().  Initialize if needed
3097 		// and then drop through to queue the callback.
3098 		if (rcu_segcblist_empty(&rdp->cblist))
3099 			rcu_segcblist_init(&rdp->cblist);
3100 	}
3101 
3102 	check_cb_ovld(rdp);
3103 
3104 	if (unlikely(rcu_rdp_is_offloaded(rdp)))
3105 		call_rcu_nocb(rdp, head, func, flags, lazy);
3106 	else
3107 		call_rcu_core(rdp, head, func, flags);
3108 	local_irq_restore(flags);
3109 }
3110 
3111 #ifdef CONFIG_RCU_LAZY
3112 static bool enable_rcu_lazy __read_mostly = !IS_ENABLED(CONFIG_RCU_LAZY_DEFAULT_OFF);
3113 module_param(enable_rcu_lazy, bool, 0444);
3114 
3115 /**
3116  * call_rcu_hurry() - Queue RCU callback for invocation after grace period, and
3117  * flush all lazy callbacks (including the new one) to the main ->cblist while
3118  * doing so.
3119  *
3120  * @head: structure to be used for queueing the RCU updates.
3121  * @func: actual callback function to be invoked after the grace period
3122  *
3123  * The callback function will be invoked some time after a full grace
3124  * period elapses, in other words after all pre-existing RCU read-side
3125  * critical sections have completed.
3126  *
3127  * Use this API instead of call_rcu() if you don't want the callback to be
3128  * invoked after very long periods of time, which can happen on systems without
3129  * memory pressure and on systems which are lightly loaded or mostly idle.
3130  * This function will cause callbacks to be invoked sooner than later at the
3131  * expense of extra power. Other than that, this function is identical to, and
3132  * reuses call_rcu()'s logic. Refer to call_rcu() for more details about memory
3133  * ordering and other functionality.
3134  */
3135 void call_rcu_hurry(struct rcu_head *head, rcu_callback_t func)
3136 {
3137 	__call_rcu_common(head, func, false);
3138 }
3139 EXPORT_SYMBOL_GPL(call_rcu_hurry);
3140 #else
3141 #define enable_rcu_lazy		false
3142 #endif
3143 
3144 /**
3145  * call_rcu() - Queue an RCU callback for invocation after a grace period.
3146  * By default the callbacks are 'lazy' and are kept hidden from the main
3147  * ->cblist to prevent starting of grace periods too soon.
3148  * If you desire grace periods to start very soon, use call_rcu_hurry().
3149  *
3150  * @head: structure to be used for queueing the RCU updates.
3151  * @func: actual callback function to be invoked after the grace period
3152  *
3153  * The callback function will be invoked some time after a full grace
3154  * period elapses, in other words after all pre-existing RCU read-side
3155  * critical sections have completed.  However, the callback function
3156  * might well execute concurrently with RCU read-side critical sections
3157  * that started after call_rcu() was invoked.
3158  *
3159  * RCU read-side critical sections are delimited by rcu_read_lock()
3160  * and rcu_read_unlock(), and may be nested.  In addition, but only in
3161  * v5.0 and later, regions of code across which interrupts, preemption,
3162  * or softirqs have been disabled also serve as RCU read-side critical
3163  * sections.  This includes hardware interrupt handlers, softirq handlers,
3164  * and NMI handlers.
3165  *
3166  * Note that all CPUs must agree that the grace period extended beyond
3167  * all pre-existing RCU read-side critical section.  On systems with more
3168  * than one CPU, this means that when "func()" is invoked, each CPU is
3169  * guaranteed to have executed a full memory barrier since the end of its
3170  * last RCU read-side critical section whose beginning preceded the call
3171  * to call_rcu().  It also means that each CPU executing an RCU read-side
3172  * critical section that continues beyond the start of "func()" must have
3173  * executed a memory barrier after the call_rcu() but before the beginning
3174  * of that RCU read-side critical section.  Note that these guarantees
3175  * include CPUs that are offline, idle, or executing in user mode, as
3176  * well as CPUs that are executing in the kernel.
3177  *
3178  * Furthermore, if CPU A invoked call_rcu() and CPU B invoked the
3179  * resulting RCU callback function "func()", then both CPU A and CPU B are
3180  * guaranteed to execute a full memory barrier during the time interval
3181  * between the call to call_rcu() and the invocation of "func()" -- even
3182  * if CPU A and CPU B are the same CPU (but again only if the system has
3183  * more than one CPU).
3184  *
3185  * Implementation of these memory-ordering guarantees is described here:
3186  * Documentation/RCU/Design/Memory-Ordering/Tree-RCU-Memory-Ordering.rst.
3187  */
3188 void call_rcu(struct rcu_head *head, rcu_callback_t func)
3189 {
3190 	__call_rcu_common(head, func, enable_rcu_lazy);
3191 }
3192 EXPORT_SYMBOL_GPL(call_rcu);
3193 
3194 /* Maximum number of jiffies to wait before draining a batch. */
3195 #define KFREE_DRAIN_JIFFIES (5 * HZ)
3196 #define KFREE_N_BATCHES 2
3197 #define FREE_N_CHANNELS 2
3198 
3199 /**
3200  * struct kvfree_rcu_bulk_data - single block to store kvfree_rcu() pointers
3201  * @list: List node. All blocks are linked between each other
3202  * @gp_snap: Snapshot of RCU state for objects placed to this bulk
3203  * @nr_records: Number of active pointers in the array
3204  * @records: Array of the kvfree_rcu() pointers
3205  */
3206 struct kvfree_rcu_bulk_data {
3207 	struct list_head list;
3208 	struct rcu_gp_oldstate gp_snap;
3209 	unsigned long nr_records;
3210 	void *records[] __counted_by(nr_records);
3211 };
3212 
3213 /*
3214  * This macro defines how many entries the "records" array
3215  * will contain. It is based on the fact that the size of
3216  * kvfree_rcu_bulk_data structure becomes exactly one page.
3217  */
3218 #define KVFREE_BULK_MAX_ENTR \
3219 	((PAGE_SIZE - sizeof(struct kvfree_rcu_bulk_data)) / sizeof(void *))
3220 
3221 /**
3222  * struct kfree_rcu_cpu_work - single batch of kfree_rcu() requests
3223  * @rcu_work: Let queue_rcu_work() invoke workqueue handler after grace period
3224  * @head_free: List of kfree_rcu() objects waiting for a grace period
3225  * @head_free_gp_snap: Grace-period snapshot to check for attempted premature frees.
3226  * @bulk_head_free: Bulk-List of kvfree_rcu() objects waiting for a grace period
3227  * @krcp: Pointer to @kfree_rcu_cpu structure
3228  */
3229 
3230 struct kfree_rcu_cpu_work {
3231 	struct rcu_work rcu_work;
3232 	struct rcu_head *head_free;
3233 	struct rcu_gp_oldstate head_free_gp_snap;
3234 	struct list_head bulk_head_free[FREE_N_CHANNELS];
3235 	struct kfree_rcu_cpu *krcp;
3236 };
3237 
3238 /**
3239  * struct kfree_rcu_cpu - batch up kfree_rcu() requests for RCU grace period
3240  * @head: List of kfree_rcu() objects not yet waiting for a grace period
3241  * @head_gp_snap: Snapshot of RCU state for objects placed to "@head"
3242  * @bulk_head: Bulk-List of kvfree_rcu() objects not yet waiting for a grace period
3243  * @krw_arr: Array of batches of kfree_rcu() objects waiting for a grace period
3244  * @lock: Synchronize access to this structure
3245  * @monitor_work: Promote @head to @head_free after KFREE_DRAIN_JIFFIES
3246  * @initialized: The @rcu_work fields have been initialized
3247  * @head_count: Number of objects in rcu_head singular list
3248  * @bulk_count: Number of objects in bulk-list
3249  * @bkvcache:
3250  *	A simple cache list that contains objects for reuse purpose.
3251  *	In order to save some per-cpu space the list is singular.
3252  *	Even though it is lockless an access has to be protected by the
3253  *	per-cpu lock.
3254  * @page_cache_work: A work to refill the cache when it is empty
3255  * @backoff_page_cache_fill: Delay cache refills
3256  * @work_in_progress: Indicates that page_cache_work is running
3257  * @hrtimer: A hrtimer for scheduling a page_cache_work
3258  * @nr_bkv_objs: number of allocated objects at @bkvcache.
3259  *
3260  * This is a per-CPU structure.  The reason that it is not included in
3261  * the rcu_data structure is to permit this code to be extracted from
3262  * the RCU files.  Such extraction could allow further optimization of
3263  * the interactions with the slab allocators.
3264  */
3265 struct kfree_rcu_cpu {
3266 	// Objects queued on a linked list
3267 	// through their rcu_head structures.
3268 	struct rcu_head *head;
3269 	unsigned long head_gp_snap;
3270 	atomic_t head_count;
3271 
3272 	// Objects queued on a bulk-list.
3273 	struct list_head bulk_head[FREE_N_CHANNELS];
3274 	atomic_t bulk_count[FREE_N_CHANNELS];
3275 
3276 	struct kfree_rcu_cpu_work krw_arr[KFREE_N_BATCHES];
3277 	raw_spinlock_t lock;
3278 	struct delayed_work monitor_work;
3279 	bool initialized;
3280 
3281 	struct delayed_work page_cache_work;
3282 	atomic_t backoff_page_cache_fill;
3283 	atomic_t work_in_progress;
3284 	struct hrtimer hrtimer;
3285 
3286 	struct llist_head bkvcache;
3287 	int nr_bkv_objs;
3288 };
3289 
3290 static DEFINE_PER_CPU(struct kfree_rcu_cpu, krc) = {
3291 	.lock = __RAW_SPIN_LOCK_UNLOCKED(krc.lock),
3292 };
3293 
3294 static __always_inline void
3295 debug_rcu_bhead_unqueue(struct kvfree_rcu_bulk_data *bhead)
3296 {
3297 #ifdef CONFIG_DEBUG_OBJECTS_RCU_HEAD
3298 	int i;
3299 
3300 	for (i = 0; i < bhead->nr_records; i++)
3301 		debug_rcu_head_unqueue((struct rcu_head *)(bhead->records[i]));
3302 #endif
3303 }
3304 
3305 static inline struct kfree_rcu_cpu *
3306 krc_this_cpu_lock(unsigned long *flags)
3307 {
3308 	struct kfree_rcu_cpu *krcp;
3309 
3310 	local_irq_save(*flags);	// For safely calling this_cpu_ptr().
3311 	krcp = this_cpu_ptr(&krc);
3312 	raw_spin_lock(&krcp->lock);
3313 
3314 	return krcp;
3315 }
3316 
3317 static inline void
3318 krc_this_cpu_unlock(struct kfree_rcu_cpu *krcp, unsigned long flags)
3319 {
3320 	raw_spin_unlock_irqrestore(&krcp->lock, flags);
3321 }
3322 
3323 static inline struct kvfree_rcu_bulk_data *
3324 get_cached_bnode(struct kfree_rcu_cpu *krcp)
3325 {
3326 	if (!krcp->nr_bkv_objs)
3327 		return NULL;
3328 
3329 	WRITE_ONCE(krcp->nr_bkv_objs, krcp->nr_bkv_objs - 1);
3330 	return (struct kvfree_rcu_bulk_data *)
3331 		llist_del_first(&krcp->bkvcache);
3332 }
3333 
3334 static inline bool
3335 put_cached_bnode(struct kfree_rcu_cpu *krcp,
3336 	struct kvfree_rcu_bulk_data *bnode)
3337 {
3338 	// Check the limit.
3339 	if (krcp->nr_bkv_objs >= rcu_min_cached_objs)
3340 		return false;
3341 
3342 	llist_add((struct llist_node *) bnode, &krcp->bkvcache);
3343 	WRITE_ONCE(krcp->nr_bkv_objs, krcp->nr_bkv_objs + 1);
3344 	return true;
3345 }
3346 
3347 static int
3348 drain_page_cache(struct kfree_rcu_cpu *krcp)
3349 {
3350 	unsigned long flags;
3351 	struct llist_node *page_list, *pos, *n;
3352 	int freed = 0;
3353 
3354 	if (!rcu_min_cached_objs)
3355 		return 0;
3356 
3357 	raw_spin_lock_irqsave(&krcp->lock, flags);
3358 	page_list = llist_del_all(&krcp->bkvcache);
3359 	WRITE_ONCE(krcp->nr_bkv_objs, 0);
3360 	raw_spin_unlock_irqrestore(&krcp->lock, flags);
3361 
3362 	llist_for_each_safe(pos, n, page_list) {
3363 		free_page((unsigned long)pos);
3364 		freed++;
3365 	}
3366 
3367 	return freed;
3368 }
3369 
3370 static void
3371 kvfree_rcu_bulk(struct kfree_rcu_cpu *krcp,
3372 	struct kvfree_rcu_bulk_data *bnode, int idx)
3373 {
3374 	unsigned long flags;
3375 	int i;
3376 
3377 	if (!WARN_ON_ONCE(!poll_state_synchronize_rcu_full(&bnode->gp_snap))) {
3378 		debug_rcu_bhead_unqueue(bnode);
3379 		rcu_lock_acquire(&rcu_callback_map);
3380 		if (idx == 0) { // kmalloc() / kfree().
3381 			trace_rcu_invoke_kfree_bulk_callback(
3382 				rcu_state.name, bnode->nr_records,
3383 				bnode->records);
3384 
3385 			kfree_bulk(bnode->nr_records, bnode->records);
3386 		} else { // vmalloc() / vfree().
3387 			for (i = 0; i < bnode->nr_records; i++) {
3388 				trace_rcu_invoke_kvfree_callback(
3389 					rcu_state.name, bnode->records[i], 0);
3390 
3391 				vfree(bnode->records[i]);
3392 			}
3393 		}
3394 		rcu_lock_release(&rcu_callback_map);
3395 	}
3396 
3397 	raw_spin_lock_irqsave(&krcp->lock, flags);
3398 	if (put_cached_bnode(krcp, bnode))
3399 		bnode = NULL;
3400 	raw_spin_unlock_irqrestore(&krcp->lock, flags);
3401 
3402 	if (bnode)
3403 		free_page((unsigned long) bnode);
3404 
3405 	cond_resched_tasks_rcu_qs();
3406 }
3407 
3408 static void
3409 kvfree_rcu_list(struct rcu_head *head)
3410 {
3411 	struct rcu_head *next;
3412 
3413 	for (; head; head = next) {
3414 		void *ptr = (void *) head->func;
3415 		unsigned long offset = (void *) head - ptr;
3416 
3417 		next = head->next;
3418 		debug_rcu_head_unqueue((struct rcu_head *)ptr);
3419 		rcu_lock_acquire(&rcu_callback_map);
3420 		trace_rcu_invoke_kvfree_callback(rcu_state.name, head, offset);
3421 
3422 		if (!WARN_ON_ONCE(!__is_kvfree_rcu_offset(offset)))
3423 			kvfree(ptr);
3424 
3425 		rcu_lock_release(&rcu_callback_map);
3426 		cond_resched_tasks_rcu_qs();
3427 	}
3428 }
3429 
3430 /*
3431  * This function is invoked in workqueue context after a grace period.
3432  * It frees all the objects queued on ->bulk_head_free or ->head_free.
3433  */
3434 static void kfree_rcu_work(struct work_struct *work)
3435 {
3436 	unsigned long flags;
3437 	struct kvfree_rcu_bulk_data *bnode, *n;
3438 	struct list_head bulk_head[FREE_N_CHANNELS];
3439 	struct rcu_head *head;
3440 	struct kfree_rcu_cpu *krcp;
3441 	struct kfree_rcu_cpu_work *krwp;
3442 	struct rcu_gp_oldstate head_gp_snap;
3443 	int i;
3444 
3445 	krwp = container_of(to_rcu_work(work),
3446 		struct kfree_rcu_cpu_work, rcu_work);
3447 	krcp = krwp->krcp;
3448 
3449 	raw_spin_lock_irqsave(&krcp->lock, flags);
3450 	// Channels 1 and 2.
3451 	for (i = 0; i < FREE_N_CHANNELS; i++)
3452 		list_replace_init(&krwp->bulk_head_free[i], &bulk_head[i]);
3453 
3454 	// Channel 3.
3455 	head = krwp->head_free;
3456 	krwp->head_free = NULL;
3457 	head_gp_snap = krwp->head_free_gp_snap;
3458 	raw_spin_unlock_irqrestore(&krcp->lock, flags);
3459 
3460 	// Handle the first two channels.
3461 	for (i = 0; i < FREE_N_CHANNELS; i++) {
3462 		// Start from the tail page, so a GP is likely passed for it.
3463 		list_for_each_entry_safe(bnode, n, &bulk_head[i], list)
3464 			kvfree_rcu_bulk(krcp, bnode, i);
3465 	}
3466 
3467 	/*
3468 	 * This is used when the "bulk" path can not be used for the
3469 	 * double-argument of kvfree_rcu().  This happens when the
3470 	 * page-cache is empty, which means that objects are instead
3471 	 * queued on a linked list through their rcu_head structures.
3472 	 * This list is named "Channel 3".
3473 	 */
3474 	if (head && !WARN_ON_ONCE(!poll_state_synchronize_rcu_full(&head_gp_snap)))
3475 		kvfree_rcu_list(head);
3476 }
3477 
3478 static bool
3479 need_offload_krc(struct kfree_rcu_cpu *krcp)
3480 {
3481 	int i;
3482 
3483 	for (i = 0; i < FREE_N_CHANNELS; i++)
3484 		if (!list_empty(&krcp->bulk_head[i]))
3485 			return true;
3486 
3487 	return !!READ_ONCE(krcp->head);
3488 }
3489 
3490 static bool
3491 need_wait_for_krwp_work(struct kfree_rcu_cpu_work *krwp)
3492 {
3493 	int i;
3494 
3495 	for (i = 0; i < FREE_N_CHANNELS; i++)
3496 		if (!list_empty(&krwp->bulk_head_free[i]))
3497 			return true;
3498 
3499 	return !!krwp->head_free;
3500 }
3501 
3502 static int krc_count(struct kfree_rcu_cpu *krcp)
3503 {
3504 	int sum = atomic_read(&krcp->head_count);
3505 	int i;
3506 
3507 	for (i = 0; i < FREE_N_CHANNELS; i++)
3508 		sum += atomic_read(&krcp->bulk_count[i]);
3509 
3510 	return sum;
3511 }
3512 
3513 static void
3514 schedule_delayed_monitor_work(struct kfree_rcu_cpu *krcp)
3515 {
3516 	long delay, delay_left;
3517 
3518 	delay = krc_count(krcp) >= KVFREE_BULK_MAX_ENTR ? 1:KFREE_DRAIN_JIFFIES;
3519 	if (delayed_work_pending(&krcp->monitor_work)) {
3520 		delay_left = krcp->monitor_work.timer.expires - jiffies;
3521 		if (delay < delay_left)
3522 			mod_delayed_work(system_unbound_wq, &krcp->monitor_work, delay);
3523 		return;
3524 	}
3525 	queue_delayed_work(system_unbound_wq, &krcp->monitor_work, delay);
3526 }
3527 
3528 static void
3529 kvfree_rcu_drain_ready(struct kfree_rcu_cpu *krcp)
3530 {
3531 	struct list_head bulk_ready[FREE_N_CHANNELS];
3532 	struct kvfree_rcu_bulk_data *bnode, *n;
3533 	struct rcu_head *head_ready = NULL;
3534 	unsigned long flags;
3535 	int i;
3536 
3537 	raw_spin_lock_irqsave(&krcp->lock, flags);
3538 	for (i = 0; i < FREE_N_CHANNELS; i++) {
3539 		INIT_LIST_HEAD(&bulk_ready[i]);
3540 
3541 		list_for_each_entry_safe_reverse(bnode, n, &krcp->bulk_head[i], list) {
3542 			if (!poll_state_synchronize_rcu_full(&bnode->gp_snap))
3543 				break;
3544 
3545 			atomic_sub(bnode->nr_records, &krcp->bulk_count[i]);
3546 			list_move(&bnode->list, &bulk_ready[i]);
3547 		}
3548 	}
3549 
3550 	if (krcp->head && poll_state_synchronize_rcu(krcp->head_gp_snap)) {
3551 		head_ready = krcp->head;
3552 		atomic_set(&krcp->head_count, 0);
3553 		WRITE_ONCE(krcp->head, NULL);
3554 	}
3555 	raw_spin_unlock_irqrestore(&krcp->lock, flags);
3556 
3557 	for (i = 0; i < FREE_N_CHANNELS; i++) {
3558 		list_for_each_entry_safe(bnode, n, &bulk_ready[i], list)
3559 			kvfree_rcu_bulk(krcp, bnode, i);
3560 	}
3561 
3562 	if (head_ready)
3563 		kvfree_rcu_list(head_ready);
3564 }
3565 
3566 /*
3567  * Return: %true if a work is queued, %false otherwise.
3568  */
3569 static bool
3570 kvfree_rcu_queue_batch(struct kfree_rcu_cpu *krcp)
3571 {
3572 	unsigned long flags;
3573 	bool queued = false;
3574 	int i, j;
3575 
3576 	raw_spin_lock_irqsave(&krcp->lock, flags);
3577 
3578 	// Attempt to start a new batch.
3579 	for (i = 0; i < KFREE_N_BATCHES; i++) {
3580 		struct kfree_rcu_cpu_work *krwp = &(krcp->krw_arr[i]);
3581 
3582 		// Try to detach bulk_head or head and attach it, only when
3583 		// all channels are free.  Any channel is not free means at krwp
3584 		// there is on-going rcu work to handle krwp's free business.
3585 		if (need_wait_for_krwp_work(krwp))
3586 			continue;
3587 
3588 		// kvfree_rcu_drain_ready() might handle this krcp, if so give up.
3589 		if (need_offload_krc(krcp)) {
3590 			// Channel 1 corresponds to the SLAB-pointer bulk path.
3591 			// Channel 2 corresponds to vmalloc-pointer bulk path.
3592 			for (j = 0; j < FREE_N_CHANNELS; j++) {
3593 				if (list_empty(&krwp->bulk_head_free[j])) {
3594 					atomic_set(&krcp->bulk_count[j], 0);
3595 					list_replace_init(&krcp->bulk_head[j],
3596 						&krwp->bulk_head_free[j]);
3597 				}
3598 			}
3599 
3600 			// Channel 3 corresponds to both SLAB and vmalloc
3601 			// objects queued on the linked list.
3602 			if (!krwp->head_free) {
3603 				krwp->head_free = krcp->head;
3604 				get_state_synchronize_rcu_full(&krwp->head_free_gp_snap);
3605 				atomic_set(&krcp->head_count, 0);
3606 				WRITE_ONCE(krcp->head, NULL);
3607 			}
3608 
3609 			// One work is per one batch, so there are three
3610 			// "free channels", the batch can handle. Break
3611 			// the loop since it is done with this CPU thus
3612 			// queuing an RCU work is _always_ success here.
3613 			queued = queue_rcu_work(system_unbound_wq, &krwp->rcu_work);
3614 			WARN_ON_ONCE(!queued);
3615 			break;
3616 		}
3617 	}
3618 
3619 	raw_spin_unlock_irqrestore(&krcp->lock, flags);
3620 	return queued;
3621 }
3622 
3623 /*
3624  * This function is invoked after the KFREE_DRAIN_JIFFIES timeout.
3625  */
3626 static void kfree_rcu_monitor(struct work_struct *work)
3627 {
3628 	struct kfree_rcu_cpu *krcp = container_of(work,
3629 		struct kfree_rcu_cpu, monitor_work.work);
3630 
3631 	// Drain ready for reclaim.
3632 	kvfree_rcu_drain_ready(krcp);
3633 
3634 	// Queue a batch for a rest.
3635 	kvfree_rcu_queue_batch(krcp);
3636 
3637 	// If there is nothing to detach, it means that our job is
3638 	// successfully done here. In case of having at least one
3639 	// of the channels that is still busy we should rearm the
3640 	// work to repeat an attempt. Because previous batches are
3641 	// still in progress.
3642 	if (need_offload_krc(krcp))
3643 		schedule_delayed_monitor_work(krcp);
3644 }
3645 
3646 static enum hrtimer_restart
3647 schedule_page_work_fn(struct hrtimer *t)
3648 {
3649 	struct kfree_rcu_cpu *krcp =
3650 		container_of(t, struct kfree_rcu_cpu, hrtimer);
3651 
3652 	queue_delayed_work(system_highpri_wq, &krcp->page_cache_work, 0);
3653 	return HRTIMER_NORESTART;
3654 }
3655 
3656 static void fill_page_cache_func(struct work_struct *work)
3657 {
3658 	struct kvfree_rcu_bulk_data *bnode;
3659 	struct kfree_rcu_cpu *krcp =
3660 		container_of(work, struct kfree_rcu_cpu,
3661 			page_cache_work.work);
3662 	unsigned long flags;
3663 	int nr_pages;
3664 	bool pushed;
3665 	int i;
3666 
3667 	nr_pages = atomic_read(&krcp->backoff_page_cache_fill) ?
3668 		1 : rcu_min_cached_objs;
3669 
3670 	for (i = READ_ONCE(krcp->nr_bkv_objs); i < nr_pages; i++) {
3671 		bnode = (struct kvfree_rcu_bulk_data *)
3672 			__get_free_page(GFP_KERNEL | __GFP_NORETRY | __GFP_NOMEMALLOC | __GFP_NOWARN);
3673 
3674 		if (!bnode)
3675 			break;
3676 
3677 		raw_spin_lock_irqsave(&krcp->lock, flags);
3678 		pushed = put_cached_bnode(krcp, bnode);
3679 		raw_spin_unlock_irqrestore(&krcp->lock, flags);
3680 
3681 		if (!pushed) {
3682 			free_page((unsigned long) bnode);
3683 			break;
3684 		}
3685 	}
3686 
3687 	atomic_set(&krcp->work_in_progress, 0);
3688 	atomic_set(&krcp->backoff_page_cache_fill, 0);
3689 }
3690 
3691 static void
3692 run_page_cache_worker(struct kfree_rcu_cpu *krcp)
3693 {
3694 	// If cache disabled, bail out.
3695 	if (!rcu_min_cached_objs)
3696 		return;
3697 
3698 	if (rcu_scheduler_active == RCU_SCHEDULER_RUNNING &&
3699 			!atomic_xchg(&krcp->work_in_progress, 1)) {
3700 		if (atomic_read(&krcp->backoff_page_cache_fill)) {
3701 			queue_delayed_work(system_unbound_wq,
3702 				&krcp->page_cache_work,
3703 					msecs_to_jiffies(rcu_delay_page_cache_fill_msec));
3704 		} else {
3705 			hrtimer_init(&krcp->hrtimer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
3706 			krcp->hrtimer.function = schedule_page_work_fn;
3707 			hrtimer_start(&krcp->hrtimer, 0, HRTIMER_MODE_REL);
3708 		}
3709 	}
3710 }
3711 
3712 // Record ptr in a page managed by krcp, with the pre-krc_this_cpu_lock()
3713 // state specified by flags.  If can_alloc is true, the caller must
3714 // be schedulable and not be holding any locks or mutexes that might be
3715 // acquired by the memory allocator or anything that it might invoke.
3716 // Returns true if ptr was successfully recorded, else the caller must
3717 // use a fallback.
3718 static inline bool
3719 add_ptr_to_bulk_krc_lock(struct kfree_rcu_cpu **krcp,
3720 	unsigned long *flags, void *ptr, bool can_alloc)
3721 {
3722 	struct kvfree_rcu_bulk_data *bnode;
3723 	int idx;
3724 
3725 	*krcp = krc_this_cpu_lock(flags);
3726 	if (unlikely(!(*krcp)->initialized))
3727 		return false;
3728 
3729 	idx = !!is_vmalloc_addr(ptr);
3730 	bnode = list_first_entry_or_null(&(*krcp)->bulk_head[idx],
3731 		struct kvfree_rcu_bulk_data, list);
3732 
3733 	/* Check if a new block is required. */
3734 	if (!bnode || bnode->nr_records == KVFREE_BULK_MAX_ENTR) {
3735 		bnode = get_cached_bnode(*krcp);
3736 		if (!bnode && can_alloc) {
3737 			krc_this_cpu_unlock(*krcp, *flags);
3738 
3739 			// __GFP_NORETRY - allows a light-weight direct reclaim
3740 			// what is OK from minimizing of fallback hitting point of
3741 			// view. Apart of that it forbids any OOM invoking what is
3742 			// also beneficial since we are about to release memory soon.
3743 			//
3744 			// __GFP_NOMEMALLOC - prevents from consuming of all the
3745 			// memory reserves. Please note we have a fallback path.
3746 			//
3747 			// __GFP_NOWARN - it is supposed that an allocation can
3748 			// be failed under low memory or high memory pressure
3749 			// scenarios.
3750 			bnode = (struct kvfree_rcu_bulk_data *)
3751 				__get_free_page(GFP_KERNEL | __GFP_NORETRY | __GFP_NOMEMALLOC | __GFP_NOWARN);
3752 			raw_spin_lock_irqsave(&(*krcp)->lock, *flags);
3753 		}
3754 
3755 		if (!bnode)
3756 			return false;
3757 
3758 		// Initialize the new block and attach it.
3759 		bnode->nr_records = 0;
3760 		list_add(&bnode->list, &(*krcp)->bulk_head[idx]);
3761 	}
3762 
3763 	// Finally insert and update the GP for this page.
3764 	bnode->nr_records++;
3765 	bnode->records[bnode->nr_records - 1] = ptr;
3766 	get_state_synchronize_rcu_full(&bnode->gp_snap);
3767 	atomic_inc(&(*krcp)->bulk_count[idx]);
3768 
3769 	return true;
3770 }
3771 
3772 /*
3773  * Queue a request for lazy invocation of the appropriate free routine
3774  * after a grace period.  Please note that three paths are maintained,
3775  * two for the common case using arrays of pointers and a third one that
3776  * is used only when the main paths cannot be used, for example, due to
3777  * memory pressure.
3778  *
3779  * Each kvfree_call_rcu() request is added to a batch. The batch will be drained
3780  * every KFREE_DRAIN_JIFFIES number of jiffies. All the objects in the batch will
3781  * be free'd in workqueue context. This allows us to: batch requests together to
3782  * reduce the number of grace periods during heavy kfree_rcu()/kvfree_rcu() load.
3783  */
3784 void kvfree_call_rcu(struct rcu_head *head, void *ptr)
3785 {
3786 	unsigned long flags;
3787 	struct kfree_rcu_cpu *krcp;
3788 	bool success;
3789 
3790 	/*
3791 	 * Please note there is a limitation for the head-less
3792 	 * variant, that is why there is a clear rule for such
3793 	 * objects: it can be used from might_sleep() context
3794 	 * only. For other places please embed an rcu_head to
3795 	 * your data.
3796 	 */
3797 	if (!head)
3798 		might_sleep();
3799 
3800 	// Queue the object but don't yet schedule the batch.
3801 	if (debug_rcu_head_queue(ptr)) {
3802 		// Probable double kfree_rcu(), just leak.
3803 		WARN_ONCE(1, "%s(): Double-freed call. rcu_head %p\n",
3804 			  __func__, head);
3805 
3806 		// Mark as success and leave.
3807 		return;
3808 	}
3809 
3810 	kasan_record_aux_stack_noalloc(ptr);
3811 	success = add_ptr_to_bulk_krc_lock(&krcp, &flags, ptr, !head);
3812 	if (!success) {
3813 		run_page_cache_worker(krcp);
3814 
3815 		if (head == NULL)
3816 			// Inline if kvfree_rcu(one_arg) call.
3817 			goto unlock_return;
3818 
3819 		head->func = ptr;
3820 		head->next = krcp->head;
3821 		WRITE_ONCE(krcp->head, head);
3822 		atomic_inc(&krcp->head_count);
3823 
3824 		// Take a snapshot for this krcp.
3825 		krcp->head_gp_snap = get_state_synchronize_rcu();
3826 		success = true;
3827 	}
3828 
3829 	/*
3830 	 * The kvfree_rcu() caller considers the pointer freed at this point
3831 	 * and likely removes any references to it. Since the actual slab
3832 	 * freeing (and kmemleak_free()) is deferred, tell kmemleak to ignore
3833 	 * this object (no scanning or false positives reporting).
3834 	 */
3835 	kmemleak_ignore(ptr);
3836 
3837 	// Set timer to drain after KFREE_DRAIN_JIFFIES.
3838 	if (rcu_scheduler_active == RCU_SCHEDULER_RUNNING)
3839 		schedule_delayed_monitor_work(krcp);
3840 
3841 unlock_return:
3842 	krc_this_cpu_unlock(krcp, flags);
3843 
3844 	/*
3845 	 * Inline kvfree() after synchronize_rcu(). We can do
3846 	 * it from might_sleep() context only, so the current
3847 	 * CPU can pass the QS state.
3848 	 */
3849 	if (!success) {
3850 		debug_rcu_head_unqueue((struct rcu_head *) ptr);
3851 		synchronize_rcu();
3852 		kvfree(ptr);
3853 	}
3854 }
3855 EXPORT_SYMBOL_GPL(kvfree_call_rcu);
3856 
3857 /**
3858  * kvfree_rcu_barrier - Wait until all in-flight kvfree_rcu() complete.
3859  *
3860  * Note that a single argument of kvfree_rcu() call has a slow path that
3861  * triggers synchronize_rcu() following by freeing a pointer. It is done
3862  * before the return from the function. Therefore for any single-argument
3863  * call that will result in a kfree() to a cache that is to be destroyed
3864  * during module exit, it is developer's responsibility to ensure that all
3865  * such calls have returned before the call to kmem_cache_destroy().
3866  */
3867 void kvfree_rcu_barrier(void)
3868 {
3869 	struct kfree_rcu_cpu_work *krwp;
3870 	struct kfree_rcu_cpu *krcp;
3871 	bool queued;
3872 	int i, cpu;
3873 
3874 	/*
3875 	 * Firstly we detach objects and queue them over an RCU-batch
3876 	 * for all CPUs. Finally queued works are flushed for each CPU.
3877 	 *
3878 	 * Please note. If there are outstanding batches for a particular
3879 	 * CPU, those have to be finished first following by queuing a new.
3880 	 */
3881 	for_each_possible_cpu(cpu) {
3882 		krcp = per_cpu_ptr(&krc, cpu);
3883 
3884 		/*
3885 		 * Check if this CPU has any objects which have been queued for a
3886 		 * new GP completion. If not(means nothing to detach), we are done
3887 		 * with it. If any batch is pending/running for this "krcp", below
3888 		 * per-cpu flush_rcu_work() waits its completion(see last step).
3889 		 */
3890 		if (!need_offload_krc(krcp))
3891 			continue;
3892 
3893 		while (1) {
3894 			/*
3895 			 * If we are not able to queue a new RCU work it means:
3896 			 * - batches for this CPU are still in flight which should
3897 			 *   be flushed first and then repeat;
3898 			 * - no objects to detach, because of concurrency.
3899 			 */
3900 			queued = kvfree_rcu_queue_batch(krcp);
3901 
3902 			/*
3903 			 * Bail out, if there is no need to offload this "krcp"
3904 			 * anymore. As noted earlier it can run concurrently.
3905 			 */
3906 			if (queued || !need_offload_krc(krcp))
3907 				break;
3908 
3909 			/* There are ongoing batches. */
3910 			for (i = 0; i < KFREE_N_BATCHES; i++) {
3911 				krwp = &(krcp->krw_arr[i]);
3912 				flush_rcu_work(&krwp->rcu_work);
3913 			}
3914 		}
3915 	}
3916 
3917 	/*
3918 	 * Now we guarantee that all objects are flushed.
3919 	 */
3920 	for_each_possible_cpu(cpu) {
3921 		krcp = per_cpu_ptr(&krc, cpu);
3922 
3923 		/*
3924 		 * A monitor work can drain ready to reclaim objects
3925 		 * directly. Wait its completion if running or pending.
3926 		 */
3927 		cancel_delayed_work_sync(&krcp->monitor_work);
3928 
3929 		for (i = 0; i < KFREE_N_BATCHES; i++) {
3930 			krwp = &(krcp->krw_arr[i]);
3931 			flush_rcu_work(&krwp->rcu_work);
3932 		}
3933 	}
3934 }
3935 EXPORT_SYMBOL_GPL(kvfree_rcu_barrier);
3936 
3937 static unsigned long
3938 kfree_rcu_shrink_count(struct shrinker *shrink, struct shrink_control *sc)
3939 {
3940 	int cpu;
3941 	unsigned long count = 0;
3942 
3943 	/* Snapshot count of all CPUs */
3944 	for_each_possible_cpu(cpu) {
3945 		struct kfree_rcu_cpu *krcp = per_cpu_ptr(&krc, cpu);
3946 
3947 		count += krc_count(krcp);
3948 		count += READ_ONCE(krcp->nr_bkv_objs);
3949 		atomic_set(&krcp->backoff_page_cache_fill, 1);
3950 	}
3951 
3952 	return count == 0 ? SHRINK_EMPTY : count;
3953 }
3954 
3955 static unsigned long
3956 kfree_rcu_shrink_scan(struct shrinker *shrink, struct shrink_control *sc)
3957 {
3958 	int cpu, freed = 0;
3959 
3960 	for_each_possible_cpu(cpu) {
3961 		int count;
3962 		struct kfree_rcu_cpu *krcp = per_cpu_ptr(&krc, cpu);
3963 
3964 		count = krc_count(krcp);
3965 		count += drain_page_cache(krcp);
3966 		kfree_rcu_monitor(&krcp->monitor_work.work);
3967 
3968 		sc->nr_to_scan -= count;
3969 		freed += count;
3970 
3971 		if (sc->nr_to_scan <= 0)
3972 			break;
3973 	}
3974 
3975 	return freed == 0 ? SHRINK_STOP : freed;
3976 }
3977 
3978 void __init kfree_rcu_scheduler_running(void)
3979 {
3980 	int cpu;
3981 
3982 	for_each_possible_cpu(cpu) {
3983 		struct kfree_rcu_cpu *krcp = per_cpu_ptr(&krc, cpu);
3984 
3985 		if (need_offload_krc(krcp))
3986 			schedule_delayed_monitor_work(krcp);
3987 	}
3988 }
3989 
3990 /*
3991  * During early boot, any blocking grace-period wait automatically
3992  * implies a grace period.
3993  *
3994  * Later on, this could in theory be the case for kernels built with
3995  * CONFIG_SMP=y && CONFIG_PREEMPTION=y running on a single CPU, but this
3996  * is not a common case.  Furthermore, this optimization would cause
3997  * the rcu_gp_oldstate structure to expand by 50%, so this potential
3998  * grace-period optimization is ignored once the scheduler is running.
3999  */
4000 static int rcu_blocking_is_gp(void)
4001 {
4002 	if (rcu_scheduler_active != RCU_SCHEDULER_INACTIVE) {
4003 		might_sleep();
4004 		return false;
4005 	}
4006 	return true;
4007 }
4008 
4009 /*
4010  * Helper function for the synchronize_rcu() API.
4011  */
4012 static void synchronize_rcu_normal(void)
4013 {
4014 	struct rcu_synchronize rs;
4015 
4016 	trace_rcu_sr_normal(rcu_state.name, &rs.head, TPS("request"));
4017 
4018 	if (!READ_ONCE(rcu_normal_wake_from_gp)) {
4019 		wait_rcu_gp(call_rcu_hurry);
4020 		goto trace_complete_out;
4021 	}
4022 
4023 	init_rcu_head_on_stack(&rs.head);
4024 	init_completion(&rs.completion);
4025 
4026 	/*
4027 	 * This code might be preempted, therefore take a GP
4028 	 * snapshot before adding a request.
4029 	 */
4030 	if (IS_ENABLED(CONFIG_PROVE_RCU))
4031 		rs.head.func = (void *) get_state_synchronize_rcu();
4032 
4033 	rcu_sr_normal_add_req(&rs);
4034 
4035 	/* Kick a GP and start waiting. */
4036 	(void) start_poll_synchronize_rcu();
4037 
4038 	/* Now we can wait. */
4039 	wait_for_completion(&rs.completion);
4040 	destroy_rcu_head_on_stack(&rs.head);
4041 
4042 trace_complete_out:
4043 	trace_rcu_sr_normal(rcu_state.name, &rs.head, TPS("complete"));
4044 }
4045 
4046 /**
4047  * synchronize_rcu - wait until a grace period has elapsed.
4048  *
4049  * Control will return to the caller some time after a full grace
4050  * period has elapsed, in other words after all currently executing RCU
4051  * read-side critical sections have completed.  Note, however, that
4052  * upon return from synchronize_rcu(), the caller might well be executing
4053  * concurrently with new RCU read-side critical sections that began while
4054  * synchronize_rcu() was waiting.
4055  *
4056  * RCU read-side critical sections are delimited by rcu_read_lock()
4057  * and rcu_read_unlock(), and may be nested.  In addition, but only in
4058  * v5.0 and later, regions of code across which interrupts, preemption,
4059  * or softirqs have been disabled also serve as RCU read-side critical
4060  * sections.  This includes hardware interrupt handlers, softirq handlers,
4061  * and NMI handlers.
4062  *
4063  * Note that this guarantee implies further memory-ordering guarantees.
4064  * On systems with more than one CPU, when synchronize_rcu() returns,
4065  * each CPU is guaranteed to have executed a full memory barrier since
4066  * the end of its last RCU read-side critical section whose beginning
4067  * preceded the call to synchronize_rcu().  In addition, each CPU having
4068  * an RCU read-side critical section that extends beyond the return from
4069  * synchronize_rcu() is guaranteed to have executed a full memory barrier
4070  * after the beginning of synchronize_rcu() and before the beginning of
4071  * that RCU read-side critical section.  Note that these guarantees include
4072  * CPUs that are offline, idle, or executing in user mode, as well as CPUs
4073  * that are executing in the kernel.
4074  *
4075  * Furthermore, if CPU A invoked synchronize_rcu(), which returned
4076  * to its caller on CPU B, then both CPU A and CPU B are guaranteed
4077  * to have executed a full memory barrier during the execution of
4078  * synchronize_rcu() -- even if CPU A and CPU B are the same CPU (but
4079  * again only if the system has more than one CPU).
4080  *
4081  * Implementation of these memory-ordering guarantees is described here:
4082  * Documentation/RCU/Design/Memory-Ordering/Tree-RCU-Memory-Ordering.rst.
4083  */
4084 void synchronize_rcu(void)
4085 {
4086 	unsigned long flags;
4087 	struct rcu_node *rnp;
4088 
4089 	RCU_LOCKDEP_WARN(lock_is_held(&rcu_bh_lock_map) ||
4090 			 lock_is_held(&rcu_lock_map) ||
4091 			 lock_is_held(&rcu_sched_lock_map),
4092 			 "Illegal synchronize_rcu() in RCU read-side critical section");
4093 	if (!rcu_blocking_is_gp()) {
4094 		if (rcu_gp_is_expedited())
4095 			synchronize_rcu_expedited();
4096 		else
4097 			synchronize_rcu_normal();
4098 		return;
4099 	}
4100 
4101 	// Context allows vacuous grace periods.
4102 	// Note well that this code runs with !PREEMPT && !SMP.
4103 	// In addition, all code that advances grace periods runs at
4104 	// process level.  Therefore, this normal GP overlaps with other
4105 	// normal GPs only by being fully nested within them, which allows
4106 	// reuse of ->gp_seq_polled_snap.
4107 	rcu_poll_gp_seq_start_unlocked(&rcu_state.gp_seq_polled_snap);
4108 	rcu_poll_gp_seq_end_unlocked(&rcu_state.gp_seq_polled_snap);
4109 
4110 	// Update the normal grace-period counters to record
4111 	// this grace period, but only those used by the boot CPU.
4112 	// The rcu_scheduler_starting() will take care of the rest of
4113 	// these counters.
4114 	local_irq_save(flags);
4115 	WARN_ON_ONCE(num_online_cpus() > 1);
4116 	rcu_state.gp_seq += (1 << RCU_SEQ_CTR_SHIFT);
4117 	for (rnp = this_cpu_ptr(&rcu_data)->mynode; rnp; rnp = rnp->parent)
4118 		rnp->gp_seq_needed = rnp->gp_seq = rcu_state.gp_seq;
4119 	local_irq_restore(flags);
4120 }
4121 EXPORT_SYMBOL_GPL(synchronize_rcu);
4122 
4123 /**
4124  * get_completed_synchronize_rcu_full - Return a full pre-completed polled state cookie
4125  * @rgosp: Place to put state cookie
4126  *
4127  * Stores into @rgosp a value that will always be treated by functions
4128  * like poll_state_synchronize_rcu_full() as a cookie whose grace period
4129  * has already completed.
4130  */
4131 void get_completed_synchronize_rcu_full(struct rcu_gp_oldstate *rgosp)
4132 {
4133 	rgosp->rgos_norm = RCU_GET_STATE_COMPLETED;
4134 	rgosp->rgos_exp = RCU_GET_STATE_COMPLETED;
4135 }
4136 EXPORT_SYMBOL_GPL(get_completed_synchronize_rcu_full);
4137 
4138 /**
4139  * get_state_synchronize_rcu - Snapshot current RCU state
4140  *
4141  * Returns a cookie that is used by a later call to cond_synchronize_rcu()
4142  * or poll_state_synchronize_rcu() to determine whether or not a full
4143  * grace period has elapsed in the meantime.
4144  */
4145 unsigned long get_state_synchronize_rcu(void)
4146 {
4147 	/*
4148 	 * Any prior manipulation of RCU-protected data must happen
4149 	 * before the load from ->gp_seq.
4150 	 */
4151 	smp_mb();  /* ^^^ */
4152 	return rcu_seq_snap(&rcu_state.gp_seq_polled);
4153 }
4154 EXPORT_SYMBOL_GPL(get_state_synchronize_rcu);
4155 
4156 /**
4157  * get_state_synchronize_rcu_full - Snapshot RCU state, both normal and expedited
4158  * @rgosp: location to place combined normal/expedited grace-period state
4159  *
4160  * Places the normal and expedited grace-period states in @rgosp.  This
4161  * state value can be passed to a later call to cond_synchronize_rcu_full()
4162  * or poll_state_synchronize_rcu_full() to determine whether or not a
4163  * grace period (whether normal or expedited) has elapsed in the meantime.
4164  * The rcu_gp_oldstate structure takes up twice the memory of an unsigned
4165  * long, but is guaranteed to see all grace periods.  In contrast, the
4166  * combined state occupies less memory, but can sometimes fail to take
4167  * grace periods into account.
4168  *
4169  * This does not guarantee that the needed grace period will actually
4170  * start.
4171  */
4172 void get_state_synchronize_rcu_full(struct rcu_gp_oldstate *rgosp)
4173 {
4174 	struct rcu_node *rnp = rcu_get_root();
4175 
4176 	/*
4177 	 * Any prior manipulation of RCU-protected data must happen
4178 	 * before the loads from ->gp_seq and ->expedited_sequence.
4179 	 */
4180 	smp_mb();  /* ^^^ */
4181 	rgosp->rgos_norm = rcu_seq_snap(&rnp->gp_seq);
4182 	rgosp->rgos_exp = rcu_seq_snap(&rcu_state.expedited_sequence);
4183 }
4184 EXPORT_SYMBOL_GPL(get_state_synchronize_rcu_full);
4185 
4186 /*
4187  * Helper function for start_poll_synchronize_rcu() and
4188  * start_poll_synchronize_rcu_full().
4189  */
4190 static void start_poll_synchronize_rcu_common(void)
4191 {
4192 	unsigned long flags;
4193 	bool needwake;
4194 	struct rcu_data *rdp;
4195 	struct rcu_node *rnp;
4196 
4197 	lockdep_assert_irqs_enabled();
4198 	local_irq_save(flags);
4199 	rdp = this_cpu_ptr(&rcu_data);
4200 	rnp = rdp->mynode;
4201 	raw_spin_lock_rcu_node(rnp); // irqs already disabled.
4202 	// Note it is possible for a grace period to have elapsed between
4203 	// the above call to get_state_synchronize_rcu() and the below call
4204 	// to rcu_seq_snap.  This is OK, the worst that happens is that we
4205 	// get a grace period that no one needed.  These accesses are ordered
4206 	// by smp_mb(), and we are accessing them in the opposite order
4207 	// from which they are updated at grace-period start, as required.
4208 	needwake = rcu_start_this_gp(rnp, rdp, rcu_seq_snap(&rcu_state.gp_seq));
4209 	raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
4210 	if (needwake)
4211 		rcu_gp_kthread_wake();
4212 }
4213 
4214 /**
4215  * start_poll_synchronize_rcu - Snapshot and start RCU grace period
4216  *
4217  * Returns a cookie that is used by a later call to cond_synchronize_rcu()
4218  * or poll_state_synchronize_rcu() to determine whether or not a full
4219  * grace period has elapsed in the meantime.  If the needed grace period
4220  * is not already slated to start, notifies RCU core of the need for that
4221  * grace period.
4222  *
4223  * Interrupts must be enabled for the case where it is necessary to awaken
4224  * the grace-period kthread.
4225  */
4226 unsigned long start_poll_synchronize_rcu(void)
4227 {
4228 	unsigned long gp_seq = get_state_synchronize_rcu();
4229 
4230 	start_poll_synchronize_rcu_common();
4231 	return gp_seq;
4232 }
4233 EXPORT_SYMBOL_GPL(start_poll_synchronize_rcu);
4234 
4235 /**
4236  * start_poll_synchronize_rcu_full - Take a full snapshot and start RCU grace period
4237  * @rgosp: value from get_state_synchronize_rcu_full() or start_poll_synchronize_rcu_full()
4238  *
4239  * Places the normal and expedited grace-period states in *@rgos.  This
4240  * state value can be passed to a later call to cond_synchronize_rcu_full()
4241  * or poll_state_synchronize_rcu_full() to determine whether or not a
4242  * grace period (whether normal or expedited) has elapsed in the meantime.
4243  * If the needed grace period is not already slated to start, notifies
4244  * RCU core of the need for that grace period.
4245  *
4246  * Interrupts must be enabled for the case where it is necessary to awaken
4247  * the grace-period kthread.
4248  */
4249 void start_poll_synchronize_rcu_full(struct rcu_gp_oldstate *rgosp)
4250 {
4251 	get_state_synchronize_rcu_full(rgosp);
4252 
4253 	start_poll_synchronize_rcu_common();
4254 }
4255 EXPORT_SYMBOL_GPL(start_poll_synchronize_rcu_full);
4256 
4257 /**
4258  * poll_state_synchronize_rcu - Has the specified RCU grace period completed?
4259  * @oldstate: value from get_state_synchronize_rcu() or start_poll_synchronize_rcu()
4260  *
4261  * If a full RCU grace period has elapsed since the earlier call from
4262  * which @oldstate was obtained, return @true, otherwise return @false.
4263  * If @false is returned, it is the caller's responsibility to invoke this
4264  * function later on until it does return @true.  Alternatively, the caller
4265  * can explicitly wait for a grace period, for example, by passing @oldstate
4266  * to either cond_synchronize_rcu() or cond_synchronize_rcu_expedited()
4267  * on the one hand or by directly invoking either synchronize_rcu() or
4268  * synchronize_rcu_expedited() on the other.
4269  *
4270  * Yes, this function does not take counter wrap into account.
4271  * But counter wrap is harmless.  If the counter wraps, we have waited for
4272  * more than a billion grace periods (and way more on a 64-bit system!).
4273  * Those needing to keep old state values for very long time periods
4274  * (many hours even on 32-bit systems) should check them occasionally and
4275  * either refresh them or set a flag indicating that the grace period has
4276  * completed.  Alternatively, they can use get_completed_synchronize_rcu()
4277  * to get a guaranteed-completed grace-period state.
4278  *
4279  * In addition, because oldstate compresses the grace-period state for
4280  * both normal and expedited grace periods into a single unsigned long,
4281  * it can miss a grace period when synchronize_rcu() runs concurrently
4282  * with synchronize_rcu_expedited().  If this is unacceptable, please
4283  * instead use the _full() variant of these polling APIs.
4284  *
4285  * This function provides the same memory-ordering guarantees that
4286  * would be provided by a synchronize_rcu() that was invoked at the call
4287  * to the function that provided @oldstate, and that returned at the end
4288  * of this function.
4289  */
4290 bool poll_state_synchronize_rcu(unsigned long oldstate)
4291 {
4292 	if (oldstate == RCU_GET_STATE_COMPLETED ||
4293 	    rcu_seq_done_exact(&rcu_state.gp_seq_polled, oldstate)) {
4294 		smp_mb(); /* Ensure GP ends before subsequent accesses. */
4295 		return true;
4296 	}
4297 	return false;
4298 }
4299 EXPORT_SYMBOL_GPL(poll_state_synchronize_rcu);
4300 
4301 /**
4302  * poll_state_synchronize_rcu_full - Has the specified RCU grace period completed?
4303  * @rgosp: value from get_state_synchronize_rcu_full() or start_poll_synchronize_rcu_full()
4304  *
4305  * If a full RCU grace period has elapsed since the earlier call from
4306  * which *rgosp was obtained, return @true, otherwise return @false.
4307  * If @false is returned, it is the caller's responsibility to invoke this
4308  * function later on until it does return @true.  Alternatively, the caller
4309  * can explicitly wait for a grace period, for example, by passing @rgosp
4310  * to cond_synchronize_rcu() or by directly invoking synchronize_rcu().
4311  *
4312  * Yes, this function does not take counter wrap into account.
4313  * But counter wrap is harmless.  If the counter wraps, we have waited
4314  * for more than a billion grace periods (and way more on a 64-bit
4315  * system!).  Those needing to keep rcu_gp_oldstate values for very
4316  * long time periods (many hours even on 32-bit systems) should check
4317  * them occasionally and either refresh them or set a flag indicating
4318  * that the grace period has completed.  Alternatively, they can use
4319  * get_completed_synchronize_rcu_full() to get a guaranteed-completed
4320  * grace-period state.
4321  *
4322  * This function provides the same memory-ordering guarantees that would
4323  * be provided by a synchronize_rcu() that was invoked at the call to
4324  * the function that provided @rgosp, and that returned at the end of this
4325  * function.  And this guarantee requires that the root rcu_node structure's
4326  * ->gp_seq field be checked instead of that of the rcu_state structure.
4327  * The problem is that the just-ending grace-period's callbacks can be
4328  * invoked between the time that the root rcu_node structure's ->gp_seq
4329  * field is updated and the time that the rcu_state structure's ->gp_seq
4330  * field is updated.  Therefore, if a single synchronize_rcu() is to
4331  * cause a subsequent poll_state_synchronize_rcu_full() to return @true,
4332  * then the root rcu_node structure is the one that needs to be polled.
4333  */
4334 bool poll_state_synchronize_rcu_full(struct rcu_gp_oldstate *rgosp)
4335 {
4336 	struct rcu_node *rnp = rcu_get_root();
4337 
4338 	smp_mb(); // Order against root rcu_node structure grace-period cleanup.
4339 	if (rgosp->rgos_norm == RCU_GET_STATE_COMPLETED ||
4340 	    rcu_seq_done_exact(&rnp->gp_seq, rgosp->rgos_norm) ||
4341 	    rgosp->rgos_exp == RCU_GET_STATE_COMPLETED ||
4342 	    rcu_seq_done_exact(&rcu_state.expedited_sequence, rgosp->rgos_exp)) {
4343 		smp_mb(); /* Ensure GP ends before subsequent accesses. */
4344 		return true;
4345 	}
4346 	return false;
4347 }
4348 EXPORT_SYMBOL_GPL(poll_state_synchronize_rcu_full);
4349 
4350 /**
4351  * cond_synchronize_rcu - Conditionally wait for an RCU grace period
4352  * @oldstate: value from get_state_synchronize_rcu(), start_poll_synchronize_rcu(), or start_poll_synchronize_rcu_expedited()
4353  *
4354  * If a full RCU grace period has elapsed since the earlier call to
4355  * get_state_synchronize_rcu() or start_poll_synchronize_rcu(), just return.
4356  * Otherwise, invoke synchronize_rcu() to wait for a full grace period.
4357  *
4358  * Yes, this function does not take counter wrap into account.
4359  * But counter wrap is harmless.  If the counter wraps, we have waited for
4360  * more than 2 billion grace periods (and way more on a 64-bit system!),
4361  * so waiting for a couple of additional grace periods should be just fine.
4362  *
4363  * This function provides the same memory-ordering guarantees that
4364  * would be provided by a synchronize_rcu() that was invoked at the call
4365  * to the function that provided @oldstate and that returned at the end
4366  * of this function.
4367  */
4368 void cond_synchronize_rcu(unsigned long oldstate)
4369 {
4370 	if (!poll_state_synchronize_rcu(oldstate))
4371 		synchronize_rcu();
4372 }
4373 EXPORT_SYMBOL_GPL(cond_synchronize_rcu);
4374 
4375 /**
4376  * cond_synchronize_rcu_full - Conditionally wait for an RCU grace period
4377  * @rgosp: value from get_state_synchronize_rcu_full(), start_poll_synchronize_rcu_full(), or start_poll_synchronize_rcu_expedited_full()
4378  *
4379  * If a full RCU grace period has elapsed since the call to
4380  * get_state_synchronize_rcu_full(), start_poll_synchronize_rcu_full(),
4381  * or start_poll_synchronize_rcu_expedited_full() from which @rgosp was
4382  * obtained, just return.  Otherwise, invoke synchronize_rcu() to wait
4383  * for a full grace period.
4384  *
4385  * Yes, this function does not take counter wrap into account.
4386  * But counter wrap is harmless.  If the counter wraps, we have waited for
4387  * more than 2 billion grace periods (and way more on a 64-bit system!),
4388  * so waiting for a couple of additional grace periods should be just fine.
4389  *
4390  * This function provides the same memory-ordering guarantees that
4391  * would be provided by a synchronize_rcu() that was invoked at the call
4392  * to the function that provided @rgosp and that returned at the end of
4393  * this function.
4394  */
4395 void cond_synchronize_rcu_full(struct rcu_gp_oldstate *rgosp)
4396 {
4397 	if (!poll_state_synchronize_rcu_full(rgosp))
4398 		synchronize_rcu();
4399 }
4400 EXPORT_SYMBOL_GPL(cond_synchronize_rcu_full);
4401 
4402 /*
4403  * Check to see if there is any immediate RCU-related work to be done by
4404  * the current CPU, returning 1 if so and zero otherwise.  The checks are
4405  * in order of increasing expense: checks that can be carried out against
4406  * CPU-local state are performed first.  However, we must check for CPU
4407  * stalls first, else we might not get a chance.
4408  */
4409 static int rcu_pending(int user)
4410 {
4411 	bool gp_in_progress;
4412 	struct rcu_data *rdp = this_cpu_ptr(&rcu_data);
4413 	struct rcu_node *rnp = rdp->mynode;
4414 
4415 	lockdep_assert_irqs_disabled();
4416 
4417 	/* Check for CPU stalls, if enabled. */
4418 	check_cpu_stall(rdp);
4419 
4420 	/* Does this CPU need a deferred NOCB wakeup? */
4421 	if (rcu_nocb_need_deferred_wakeup(rdp, RCU_NOCB_WAKE))
4422 		return 1;
4423 
4424 	/* Is this a nohz_full CPU in userspace or idle?  (Ignore RCU if so.) */
4425 	gp_in_progress = rcu_gp_in_progress();
4426 	if ((user || rcu_is_cpu_rrupt_from_idle() ||
4427 	     (gp_in_progress &&
4428 	      time_before(jiffies, READ_ONCE(rcu_state.gp_start) +
4429 			  nohz_full_patience_delay_jiffies))) &&
4430 	    rcu_nohz_full_cpu())
4431 		return 0;
4432 
4433 	/* Is the RCU core waiting for a quiescent state from this CPU? */
4434 	if (rdp->core_needs_qs && !rdp->cpu_no_qs.b.norm && gp_in_progress)
4435 		return 1;
4436 
4437 	/* Does this CPU have callbacks ready to invoke? */
4438 	if (!rcu_rdp_is_offloaded(rdp) &&
4439 	    rcu_segcblist_ready_cbs(&rdp->cblist))
4440 		return 1;
4441 
4442 	/* Has RCU gone idle with this CPU needing another grace period? */
4443 	if (!gp_in_progress && rcu_segcblist_is_enabled(&rdp->cblist) &&
4444 	    !rcu_rdp_is_offloaded(rdp) &&
4445 	    !rcu_segcblist_restempty(&rdp->cblist, RCU_NEXT_READY_TAIL))
4446 		return 1;
4447 
4448 	/* Have RCU grace period completed or started?  */
4449 	if (rcu_seq_current(&rnp->gp_seq) != rdp->gp_seq ||
4450 	    unlikely(READ_ONCE(rdp->gpwrap))) /* outside lock */
4451 		return 1;
4452 
4453 	/* nothing to do */
4454 	return 0;
4455 }
4456 
4457 /*
4458  * Helper function for rcu_barrier() tracing.  If tracing is disabled,
4459  * the compiler is expected to optimize this away.
4460  */
4461 static void rcu_barrier_trace(const char *s, int cpu, unsigned long done)
4462 {
4463 	trace_rcu_barrier(rcu_state.name, s, cpu,
4464 			  atomic_read(&rcu_state.barrier_cpu_count), done);
4465 }
4466 
4467 /*
4468  * RCU callback function for rcu_barrier().  If we are last, wake
4469  * up the task executing rcu_barrier().
4470  *
4471  * Note that the value of rcu_state.barrier_sequence must be captured
4472  * before the atomic_dec_and_test().  Otherwise, if this CPU is not last,
4473  * other CPUs might count the value down to zero before this CPU gets
4474  * around to invoking rcu_barrier_trace(), which might result in bogus
4475  * data from the next instance of rcu_barrier().
4476  */
4477 static void rcu_barrier_callback(struct rcu_head *rhp)
4478 {
4479 	unsigned long __maybe_unused s = rcu_state.barrier_sequence;
4480 
4481 	rhp->next = rhp; // Mark the callback as having been invoked.
4482 	if (atomic_dec_and_test(&rcu_state.barrier_cpu_count)) {
4483 		rcu_barrier_trace(TPS("LastCB"), -1, s);
4484 		complete(&rcu_state.barrier_completion);
4485 	} else {
4486 		rcu_barrier_trace(TPS("CB"), -1, s);
4487 	}
4488 }
4489 
4490 /*
4491  * If needed, entrain an rcu_barrier() callback on rdp->cblist.
4492  */
4493 static void rcu_barrier_entrain(struct rcu_data *rdp)
4494 {
4495 	unsigned long gseq = READ_ONCE(rcu_state.barrier_sequence);
4496 	unsigned long lseq = READ_ONCE(rdp->barrier_seq_snap);
4497 	bool wake_nocb = false;
4498 	bool was_alldone = false;
4499 
4500 	lockdep_assert_held(&rcu_state.barrier_lock);
4501 	if (rcu_seq_state(lseq) || !rcu_seq_state(gseq) || rcu_seq_ctr(lseq) != rcu_seq_ctr(gseq))
4502 		return;
4503 	rcu_barrier_trace(TPS("IRQ"), -1, rcu_state.barrier_sequence);
4504 	rdp->barrier_head.func = rcu_barrier_callback;
4505 	debug_rcu_head_queue(&rdp->barrier_head);
4506 	rcu_nocb_lock(rdp);
4507 	/*
4508 	 * Flush bypass and wakeup rcuog if we add callbacks to an empty regular
4509 	 * queue. This way we don't wait for bypass timer that can reach seconds
4510 	 * if it's fully lazy.
4511 	 */
4512 	was_alldone = rcu_rdp_is_offloaded(rdp) && !rcu_segcblist_pend_cbs(&rdp->cblist);
4513 	WARN_ON_ONCE(!rcu_nocb_flush_bypass(rdp, NULL, jiffies, false));
4514 	wake_nocb = was_alldone && rcu_segcblist_pend_cbs(&rdp->cblist);
4515 	if (rcu_segcblist_entrain(&rdp->cblist, &rdp->barrier_head)) {
4516 		atomic_inc(&rcu_state.barrier_cpu_count);
4517 	} else {
4518 		debug_rcu_head_unqueue(&rdp->barrier_head);
4519 		rcu_barrier_trace(TPS("IRQNQ"), -1, rcu_state.barrier_sequence);
4520 	}
4521 	rcu_nocb_unlock(rdp);
4522 	if (wake_nocb)
4523 		wake_nocb_gp(rdp, false);
4524 	smp_store_release(&rdp->barrier_seq_snap, gseq);
4525 }
4526 
4527 /*
4528  * Called with preemption disabled, and from cross-cpu IRQ context.
4529  */
4530 static void rcu_barrier_handler(void *cpu_in)
4531 {
4532 	uintptr_t cpu = (uintptr_t)cpu_in;
4533 	struct rcu_data *rdp = per_cpu_ptr(&rcu_data, cpu);
4534 
4535 	lockdep_assert_irqs_disabled();
4536 	WARN_ON_ONCE(cpu != rdp->cpu);
4537 	WARN_ON_ONCE(cpu != smp_processor_id());
4538 	raw_spin_lock(&rcu_state.barrier_lock);
4539 	rcu_barrier_entrain(rdp);
4540 	raw_spin_unlock(&rcu_state.barrier_lock);
4541 }
4542 
4543 /**
4544  * rcu_barrier - Wait until all in-flight call_rcu() callbacks complete.
4545  *
4546  * Note that this primitive does not necessarily wait for an RCU grace period
4547  * to complete.  For example, if there are no RCU callbacks queued anywhere
4548  * in the system, then rcu_barrier() is within its rights to return
4549  * immediately, without waiting for anything, much less an RCU grace period.
4550  */
4551 void rcu_barrier(void)
4552 {
4553 	uintptr_t cpu;
4554 	unsigned long flags;
4555 	unsigned long gseq;
4556 	struct rcu_data *rdp;
4557 	unsigned long s = rcu_seq_snap(&rcu_state.barrier_sequence);
4558 
4559 	rcu_barrier_trace(TPS("Begin"), -1, s);
4560 
4561 	/* Take mutex to serialize concurrent rcu_barrier() requests. */
4562 	mutex_lock(&rcu_state.barrier_mutex);
4563 
4564 	/* Did someone else do our work for us? */
4565 	if (rcu_seq_done(&rcu_state.barrier_sequence, s)) {
4566 		rcu_barrier_trace(TPS("EarlyExit"), -1, rcu_state.barrier_sequence);
4567 		smp_mb(); /* caller's subsequent code after above check. */
4568 		mutex_unlock(&rcu_state.barrier_mutex);
4569 		return;
4570 	}
4571 
4572 	/* Mark the start of the barrier operation. */
4573 	raw_spin_lock_irqsave(&rcu_state.barrier_lock, flags);
4574 	rcu_seq_start(&rcu_state.barrier_sequence);
4575 	gseq = rcu_state.barrier_sequence;
4576 	rcu_barrier_trace(TPS("Inc1"), -1, rcu_state.barrier_sequence);
4577 
4578 	/*
4579 	 * Initialize the count to two rather than to zero in order
4580 	 * to avoid a too-soon return to zero in case of an immediate
4581 	 * invocation of the just-enqueued callback (or preemption of
4582 	 * this task).  Exclude CPU-hotplug operations to ensure that no
4583 	 * offline non-offloaded CPU has callbacks queued.
4584 	 */
4585 	init_completion(&rcu_state.barrier_completion);
4586 	atomic_set(&rcu_state.barrier_cpu_count, 2);
4587 	raw_spin_unlock_irqrestore(&rcu_state.barrier_lock, flags);
4588 
4589 	/*
4590 	 * Force each CPU with callbacks to register a new callback.
4591 	 * When that callback is invoked, we will know that all of the
4592 	 * corresponding CPU's preceding callbacks have been invoked.
4593 	 */
4594 	for_each_possible_cpu(cpu) {
4595 		rdp = per_cpu_ptr(&rcu_data, cpu);
4596 retry:
4597 		if (smp_load_acquire(&rdp->barrier_seq_snap) == gseq)
4598 			continue;
4599 		raw_spin_lock_irqsave(&rcu_state.barrier_lock, flags);
4600 		if (!rcu_segcblist_n_cbs(&rdp->cblist)) {
4601 			WRITE_ONCE(rdp->barrier_seq_snap, gseq);
4602 			raw_spin_unlock_irqrestore(&rcu_state.barrier_lock, flags);
4603 			rcu_barrier_trace(TPS("NQ"), cpu, rcu_state.barrier_sequence);
4604 			continue;
4605 		}
4606 		if (!rcu_rdp_cpu_online(rdp)) {
4607 			rcu_barrier_entrain(rdp);
4608 			WARN_ON_ONCE(READ_ONCE(rdp->barrier_seq_snap) != gseq);
4609 			raw_spin_unlock_irqrestore(&rcu_state.barrier_lock, flags);
4610 			rcu_barrier_trace(TPS("OfflineNoCBQ"), cpu, rcu_state.barrier_sequence);
4611 			continue;
4612 		}
4613 		raw_spin_unlock_irqrestore(&rcu_state.barrier_lock, flags);
4614 		if (smp_call_function_single(cpu, rcu_barrier_handler, (void *)cpu, 1)) {
4615 			schedule_timeout_uninterruptible(1);
4616 			goto retry;
4617 		}
4618 		WARN_ON_ONCE(READ_ONCE(rdp->barrier_seq_snap) != gseq);
4619 		rcu_barrier_trace(TPS("OnlineQ"), cpu, rcu_state.barrier_sequence);
4620 	}
4621 
4622 	/*
4623 	 * Now that we have an rcu_barrier_callback() callback on each
4624 	 * CPU, and thus each counted, remove the initial count.
4625 	 */
4626 	if (atomic_sub_and_test(2, &rcu_state.barrier_cpu_count))
4627 		complete(&rcu_state.barrier_completion);
4628 
4629 	/* Wait for all rcu_barrier_callback() callbacks to be invoked. */
4630 	wait_for_completion(&rcu_state.barrier_completion);
4631 
4632 	/* Mark the end of the barrier operation. */
4633 	rcu_barrier_trace(TPS("Inc2"), -1, rcu_state.barrier_sequence);
4634 	rcu_seq_end(&rcu_state.barrier_sequence);
4635 	gseq = rcu_state.barrier_sequence;
4636 	for_each_possible_cpu(cpu) {
4637 		rdp = per_cpu_ptr(&rcu_data, cpu);
4638 
4639 		WRITE_ONCE(rdp->barrier_seq_snap, gseq);
4640 	}
4641 
4642 	/* Other rcu_barrier() invocations can now safely proceed. */
4643 	mutex_unlock(&rcu_state.barrier_mutex);
4644 }
4645 EXPORT_SYMBOL_GPL(rcu_barrier);
4646 
4647 static unsigned long rcu_barrier_last_throttle;
4648 
4649 /**
4650  * rcu_barrier_throttled - Do rcu_barrier(), but limit to one per second
4651  *
4652  * This can be thought of as guard rails around rcu_barrier() that
4653  * permits unrestricted userspace use, at least assuming the hardware's
4654  * try_cmpxchg() is robust.  There will be at most one call per second to
4655  * rcu_barrier() system-wide from use of this function, which means that
4656  * callers might needlessly wait a second or three.
4657  *
4658  * This is intended for use by test suites to avoid OOM by flushing RCU
4659  * callbacks from the previous test before starting the next.  See the
4660  * rcutree.do_rcu_barrier module parameter for more information.
4661  *
4662  * Why not simply make rcu_barrier() more scalable?  That might be
4663  * the eventual endpoint, but let's keep it simple for the time being.
4664  * Note that the module parameter infrastructure serializes calls to a
4665  * given .set() function, but should concurrent .set() invocation ever be
4666  * possible, we are ready!
4667  */
4668 static void rcu_barrier_throttled(void)
4669 {
4670 	unsigned long j = jiffies;
4671 	unsigned long old = READ_ONCE(rcu_barrier_last_throttle);
4672 	unsigned long s = rcu_seq_snap(&rcu_state.barrier_sequence);
4673 
4674 	while (time_in_range(j, old, old + HZ / 16) ||
4675 	       !try_cmpxchg(&rcu_barrier_last_throttle, &old, j)) {
4676 		schedule_timeout_idle(HZ / 16);
4677 		if (rcu_seq_done(&rcu_state.barrier_sequence, s)) {
4678 			smp_mb(); /* caller's subsequent code after above check. */
4679 			return;
4680 		}
4681 		j = jiffies;
4682 		old = READ_ONCE(rcu_barrier_last_throttle);
4683 	}
4684 	rcu_barrier();
4685 }
4686 
4687 /*
4688  * Invoke rcu_barrier_throttled() when a rcutree.do_rcu_barrier
4689  * request arrives.  We insist on a true value to allow for possible
4690  * future expansion.
4691  */
4692 static int param_set_do_rcu_barrier(const char *val, const struct kernel_param *kp)
4693 {
4694 	bool b;
4695 	int ret;
4696 
4697 	if (rcu_scheduler_active != RCU_SCHEDULER_RUNNING)
4698 		return -EAGAIN;
4699 	ret = kstrtobool(val, &b);
4700 	if (!ret && b) {
4701 		atomic_inc((atomic_t *)kp->arg);
4702 		rcu_barrier_throttled();
4703 		atomic_dec((atomic_t *)kp->arg);
4704 	}
4705 	return ret;
4706 }
4707 
4708 /*
4709  * Output the number of outstanding rcutree.do_rcu_barrier requests.
4710  */
4711 static int param_get_do_rcu_barrier(char *buffer, const struct kernel_param *kp)
4712 {
4713 	return sprintf(buffer, "%d\n", atomic_read((atomic_t *)kp->arg));
4714 }
4715 
4716 static const struct kernel_param_ops do_rcu_barrier_ops = {
4717 	.set = param_set_do_rcu_barrier,
4718 	.get = param_get_do_rcu_barrier,
4719 };
4720 static atomic_t do_rcu_barrier;
4721 module_param_cb(do_rcu_barrier, &do_rcu_barrier_ops, &do_rcu_barrier, 0644);
4722 
4723 /*
4724  * Compute the mask of online CPUs for the specified rcu_node structure.
4725  * This will not be stable unless the rcu_node structure's ->lock is
4726  * held, but the bit corresponding to the current CPU will be stable
4727  * in most contexts.
4728  */
4729 static unsigned long rcu_rnp_online_cpus(struct rcu_node *rnp)
4730 {
4731 	return READ_ONCE(rnp->qsmaskinitnext);
4732 }
4733 
4734 /*
4735  * Is the CPU corresponding to the specified rcu_data structure online
4736  * from RCU's perspective?  This perspective is given by that structure's
4737  * ->qsmaskinitnext field rather than by the global cpu_online_mask.
4738  */
4739 static bool rcu_rdp_cpu_online(struct rcu_data *rdp)
4740 {
4741 	return !!(rdp->grpmask & rcu_rnp_online_cpus(rdp->mynode));
4742 }
4743 
4744 bool rcu_cpu_online(int cpu)
4745 {
4746 	struct rcu_data *rdp = per_cpu_ptr(&rcu_data, cpu);
4747 
4748 	return rcu_rdp_cpu_online(rdp);
4749 }
4750 
4751 #if defined(CONFIG_PROVE_RCU) && defined(CONFIG_HOTPLUG_CPU)
4752 
4753 /*
4754  * Is the current CPU online as far as RCU is concerned?
4755  *
4756  * Disable preemption to avoid false positives that could otherwise
4757  * happen due to the current CPU number being sampled, this task being
4758  * preempted, its old CPU being taken offline, resuming on some other CPU,
4759  * then determining that its old CPU is now offline.
4760  *
4761  * Disable checking if in an NMI handler because we cannot safely
4762  * report errors from NMI handlers anyway.  In addition, it is OK to use
4763  * RCU on an offline processor during initial boot, hence the check for
4764  * rcu_scheduler_fully_active.
4765  */
4766 bool rcu_lockdep_current_cpu_online(void)
4767 {
4768 	struct rcu_data *rdp;
4769 	bool ret = false;
4770 
4771 	if (in_nmi() || !rcu_scheduler_fully_active)
4772 		return true;
4773 	preempt_disable_notrace();
4774 	rdp = this_cpu_ptr(&rcu_data);
4775 	/*
4776 	 * Strictly, we care here about the case where the current CPU is
4777 	 * in rcutree_report_cpu_starting() and thus has an excuse for rdp->grpmask
4778 	 * not being up to date. So arch_spin_is_locked() might have a
4779 	 * false positive if it's held by some *other* CPU, but that's
4780 	 * OK because that just means a false *negative* on the warning.
4781 	 */
4782 	if (rcu_rdp_cpu_online(rdp) || arch_spin_is_locked(&rcu_state.ofl_lock))
4783 		ret = true;
4784 	preempt_enable_notrace();
4785 	return ret;
4786 }
4787 EXPORT_SYMBOL_GPL(rcu_lockdep_current_cpu_online);
4788 
4789 #endif /* #if defined(CONFIG_PROVE_RCU) && defined(CONFIG_HOTPLUG_CPU) */
4790 
4791 // Has rcu_init() been invoked?  This is used (for example) to determine
4792 // whether spinlocks may be acquired safely.
4793 static bool rcu_init_invoked(void)
4794 {
4795 	return !!READ_ONCE(rcu_state.n_online_cpus);
4796 }
4797 
4798 /*
4799  * All CPUs for the specified rcu_node structure have gone offline,
4800  * and all tasks that were preempted within an RCU read-side critical
4801  * section while running on one of those CPUs have since exited their RCU
4802  * read-side critical section.  Some other CPU is reporting this fact with
4803  * the specified rcu_node structure's ->lock held and interrupts disabled.
4804  * This function therefore goes up the tree of rcu_node structures,
4805  * clearing the corresponding bits in the ->qsmaskinit fields.  Note that
4806  * the leaf rcu_node structure's ->qsmaskinit field has already been
4807  * updated.
4808  *
4809  * This function does check that the specified rcu_node structure has
4810  * all CPUs offline and no blocked tasks, so it is OK to invoke it
4811  * prematurely.  That said, invoking it after the fact will cost you
4812  * a needless lock acquisition.  So once it has done its work, don't
4813  * invoke it again.
4814  */
4815 static void rcu_cleanup_dead_rnp(struct rcu_node *rnp_leaf)
4816 {
4817 	long mask;
4818 	struct rcu_node *rnp = rnp_leaf;
4819 
4820 	raw_lockdep_assert_held_rcu_node(rnp_leaf);
4821 	if (!IS_ENABLED(CONFIG_HOTPLUG_CPU) ||
4822 	    WARN_ON_ONCE(rnp_leaf->qsmaskinit) ||
4823 	    WARN_ON_ONCE(rcu_preempt_has_tasks(rnp_leaf)))
4824 		return;
4825 	for (;;) {
4826 		mask = rnp->grpmask;
4827 		rnp = rnp->parent;
4828 		if (!rnp)
4829 			break;
4830 		raw_spin_lock_rcu_node(rnp); /* irqs already disabled. */
4831 		rnp->qsmaskinit &= ~mask;
4832 		/* Between grace periods, so better already be zero! */
4833 		WARN_ON_ONCE(rnp->qsmask);
4834 		if (rnp->qsmaskinit) {
4835 			raw_spin_unlock_rcu_node(rnp);
4836 			/* irqs remain disabled. */
4837 			return;
4838 		}
4839 		raw_spin_unlock_rcu_node(rnp); /* irqs remain disabled. */
4840 	}
4841 }
4842 
4843 /*
4844  * Propagate ->qsinitmask bits up the rcu_node tree to account for the
4845  * first CPU in a given leaf rcu_node structure coming online.  The caller
4846  * must hold the corresponding leaf rcu_node ->lock with interrupts
4847  * disabled.
4848  */
4849 static void rcu_init_new_rnp(struct rcu_node *rnp_leaf)
4850 {
4851 	long mask;
4852 	long oldmask;
4853 	struct rcu_node *rnp = rnp_leaf;
4854 
4855 	raw_lockdep_assert_held_rcu_node(rnp_leaf);
4856 	WARN_ON_ONCE(rnp->wait_blkd_tasks);
4857 	for (;;) {
4858 		mask = rnp->grpmask;
4859 		rnp = rnp->parent;
4860 		if (rnp == NULL)
4861 			return;
4862 		raw_spin_lock_rcu_node(rnp); /* Interrupts already disabled. */
4863 		oldmask = rnp->qsmaskinit;
4864 		rnp->qsmaskinit |= mask;
4865 		raw_spin_unlock_rcu_node(rnp); /* Interrupts remain disabled. */
4866 		if (oldmask)
4867 			return;
4868 	}
4869 }
4870 
4871 /*
4872  * Do boot-time initialization of a CPU's per-CPU RCU data.
4873  */
4874 static void __init
4875 rcu_boot_init_percpu_data(int cpu)
4876 {
4877 	struct context_tracking *ct = this_cpu_ptr(&context_tracking);
4878 	struct rcu_data *rdp = per_cpu_ptr(&rcu_data, cpu);
4879 
4880 	/* Set up local state, ensuring consistent view of global state. */
4881 	rdp->grpmask = leaf_node_cpu_bit(rdp->mynode, cpu);
4882 	INIT_WORK(&rdp->strict_work, strict_work_handler);
4883 	WARN_ON_ONCE(ct->nesting != 1);
4884 	WARN_ON_ONCE(rcu_watching_snap_in_eqs(ct_rcu_watching_cpu(cpu)));
4885 	rdp->barrier_seq_snap = rcu_state.barrier_sequence;
4886 	rdp->rcu_ofl_gp_seq = rcu_state.gp_seq;
4887 	rdp->rcu_ofl_gp_state = RCU_GP_CLEANED;
4888 	rdp->rcu_onl_gp_seq = rcu_state.gp_seq;
4889 	rdp->rcu_onl_gp_state = RCU_GP_CLEANED;
4890 	rdp->last_sched_clock = jiffies;
4891 	rdp->cpu = cpu;
4892 	rcu_boot_init_nocb_percpu_data(rdp);
4893 }
4894 
4895 struct kthread_worker *rcu_exp_gp_kworker;
4896 
4897 static void rcu_spawn_exp_par_gp_kworker(struct rcu_node *rnp)
4898 {
4899 	struct kthread_worker *kworker;
4900 	const char *name = "rcu_exp_par_gp_kthread_worker/%d";
4901 	struct sched_param param = { .sched_priority = kthread_prio };
4902 	int rnp_index = rnp - rcu_get_root();
4903 
4904 	if (rnp->exp_kworker)
4905 		return;
4906 
4907 	kworker = kthread_create_worker(0, name, rnp_index);
4908 	if (IS_ERR_OR_NULL(kworker)) {
4909 		pr_err("Failed to create par gp kworker on %d/%d\n",
4910 		       rnp->grplo, rnp->grphi);
4911 		return;
4912 	}
4913 	WRITE_ONCE(rnp->exp_kworker, kworker);
4914 
4915 	if (IS_ENABLED(CONFIG_RCU_EXP_KTHREAD))
4916 		sched_setscheduler_nocheck(kworker->task, SCHED_FIFO, &param);
4917 }
4918 
4919 static struct task_struct *rcu_exp_par_gp_task(struct rcu_node *rnp)
4920 {
4921 	struct kthread_worker *kworker = READ_ONCE(rnp->exp_kworker);
4922 
4923 	if (!kworker)
4924 		return NULL;
4925 
4926 	return kworker->task;
4927 }
4928 
4929 static void __init rcu_start_exp_gp_kworker(void)
4930 {
4931 	const char *name = "rcu_exp_gp_kthread_worker";
4932 	struct sched_param param = { .sched_priority = kthread_prio };
4933 
4934 	rcu_exp_gp_kworker = kthread_create_worker(0, name);
4935 	if (IS_ERR_OR_NULL(rcu_exp_gp_kworker)) {
4936 		pr_err("Failed to create %s!\n", name);
4937 		rcu_exp_gp_kworker = NULL;
4938 		return;
4939 	}
4940 
4941 	if (IS_ENABLED(CONFIG_RCU_EXP_KTHREAD))
4942 		sched_setscheduler_nocheck(rcu_exp_gp_kworker->task, SCHED_FIFO, &param);
4943 }
4944 
4945 static void rcu_spawn_rnp_kthreads(struct rcu_node *rnp)
4946 {
4947 	if (rcu_scheduler_fully_active) {
4948 		mutex_lock(&rnp->kthread_mutex);
4949 		rcu_spawn_one_boost_kthread(rnp);
4950 		rcu_spawn_exp_par_gp_kworker(rnp);
4951 		mutex_unlock(&rnp->kthread_mutex);
4952 	}
4953 }
4954 
4955 /*
4956  * Invoked early in the CPU-online process, when pretty much all services
4957  * are available.  The incoming CPU is not present.
4958  *
4959  * Initializes a CPU's per-CPU RCU data.  Note that only one online or
4960  * offline event can be happening at a given time.  Note also that we can
4961  * accept some slop in the rsp->gp_seq access due to the fact that this
4962  * CPU cannot possibly have any non-offloaded RCU callbacks in flight yet.
4963  * And any offloaded callbacks are being numbered elsewhere.
4964  */
4965 int rcutree_prepare_cpu(unsigned int cpu)
4966 {
4967 	unsigned long flags;
4968 	struct context_tracking *ct = per_cpu_ptr(&context_tracking, cpu);
4969 	struct rcu_data *rdp = per_cpu_ptr(&rcu_data, cpu);
4970 	struct rcu_node *rnp = rcu_get_root();
4971 
4972 	/* Set up local state, ensuring consistent view of global state. */
4973 	raw_spin_lock_irqsave_rcu_node(rnp, flags);
4974 	rdp->qlen_last_fqs_check = 0;
4975 	rdp->n_force_qs_snap = READ_ONCE(rcu_state.n_force_qs);
4976 	rdp->blimit = blimit;
4977 	ct->nesting = 1;	/* CPU not up, no tearing. */
4978 	raw_spin_unlock_rcu_node(rnp);		/* irqs remain disabled. */
4979 
4980 	/*
4981 	 * Only non-NOCB CPUs that didn't have early-boot callbacks need to be
4982 	 * (re-)initialized.
4983 	 */
4984 	if (!rcu_segcblist_is_enabled(&rdp->cblist))
4985 		rcu_segcblist_init(&rdp->cblist);  /* Re-enable callbacks. */
4986 
4987 	/*
4988 	 * Add CPU to leaf rcu_node pending-online bitmask.  Any needed
4989 	 * propagation up the rcu_node tree will happen at the beginning
4990 	 * of the next grace period.
4991 	 */
4992 	rnp = rdp->mynode;
4993 	raw_spin_lock_rcu_node(rnp);		/* irqs already disabled. */
4994 	rdp->gp_seq = READ_ONCE(rnp->gp_seq);
4995 	rdp->gp_seq_needed = rdp->gp_seq;
4996 	rdp->cpu_no_qs.b.norm = true;
4997 	rdp->core_needs_qs = false;
4998 	rdp->rcu_iw_pending = false;
4999 	rdp->rcu_iw = IRQ_WORK_INIT_HARD(rcu_iw_handler);
5000 	rdp->rcu_iw_gp_seq = rdp->gp_seq - 1;
5001 	trace_rcu_grace_period(rcu_state.name, rdp->gp_seq, TPS("cpuonl"));
5002 	raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
5003 	rcu_spawn_rnp_kthreads(rnp);
5004 	rcu_spawn_cpu_nocb_kthread(cpu);
5005 	ASSERT_EXCLUSIVE_WRITER(rcu_state.n_online_cpus);
5006 	WRITE_ONCE(rcu_state.n_online_cpus, rcu_state.n_online_cpus + 1);
5007 
5008 	return 0;
5009 }
5010 
5011 /*
5012  * Update kthreads affinity during CPU-hotplug changes.
5013  *
5014  * Set the per-rcu_node kthread's affinity to cover all CPUs that are
5015  * served by the rcu_node in question.  The CPU hotplug lock is still
5016  * held, so the value of rnp->qsmaskinit will be stable.
5017  *
5018  * We don't include outgoingcpu in the affinity set, use -1 if there is
5019  * no outgoing CPU.  If there are no CPUs left in the affinity set,
5020  * this function allows the kthread to execute on any CPU.
5021  *
5022  * Any future concurrent calls are serialized via ->kthread_mutex.
5023  */
5024 static void rcutree_affinity_setting(unsigned int cpu, int outgoingcpu)
5025 {
5026 	cpumask_var_t cm;
5027 	unsigned long mask;
5028 	struct rcu_data *rdp;
5029 	struct rcu_node *rnp;
5030 	struct task_struct *task_boost, *task_exp;
5031 
5032 	rdp = per_cpu_ptr(&rcu_data, cpu);
5033 	rnp = rdp->mynode;
5034 
5035 	task_boost = rcu_boost_task(rnp);
5036 	task_exp = rcu_exp_par_gp_task(rnp);
5037 
5038 	/*
5039 	 * If CPU is the boot one, those tasks are created later from early
5040 	 * initcall since kthreadd must be created first.
5041 	 */
5042 	if (!task_boost && !task_exp)
5043 		return;
5044 
5045 	if (!zalloc_cpumask_var(&cm, GFP_KERNEL))
5046 		return;
5047 
5048 	mutex_lock(&rnp->kthread_mutex);
5049 	mask = rcu_rnp_online_cpus(rnp);
5050 	for_each_leaf_node_possible_cpu(rnp, cpu)
5051 		if ((mask & leaf_node_cpu_bit(rnp, cpu)) &&
5052 		    cpu != outgoingcpu)
5053 			cpumask_set_cpu(cpu, cm);
5054 	cpumask_and(cm, cm, housekeeping_cpumask(HK_TYPE_RCU));
5055 	if (cpumask_empty(cm)) {
5056 		cpumask_copy(cm, housekeeping_cpumask(HK_TYPE_RCU));
5057 		if (outgoingcpu >= 0)
5058 			cpumask_clear_cpu(outgoingcpu, cm);
5059 	}
5060 
5061 	if (task_exp)
5062 		set_cpus_allowed_ptr(task_exp, cm);
5063 
5064 	if (task_boost)
5065 		set_cpus_allowed_ptr(task_boost, cm);
5066 
5067 	mutex_unlock(&rnp->kthread_mutex);
5068 
5069 	free_cpumask_var(cm);
5070 }
5071 
5072 /*
5073  * Has the specified (known valid) CPU ever been fully online?
5074  */
5075 bool rcu_cpu_beenfullyonline(int cpu)
5076 {
5077 	struct rcu_data *rdp = per_cpu_ptr(&rcu_data, cpu);
5078 
5079 	return smp_load_acquire(&rdp->beenonline);
5080 }
5081 
5082 /*
5083  * Near the end of the CPU-online process.  Pretty much all services
5084  * enabled, and the CPU is now very much alive.
5085  */
5086 int rcutree_online_cpu(unsigned int cpu)
5087 {
5088 	unsigned long flags;
5089 	struct rcu_data *rdp;
5090 	struct rcu_node *rnp;
5091 
5092 	rdp = per_cpu_ptr(&rcu_data, cpu);
5093 	rnp = rdp->mynode;
5094 	raw_spin_lock_irqsave_rcu_node(rnp, flags);
5095 	rnp->ffmask |= rdp->grpmask;
5096 	raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
5097 	if (rcu_scheduler_active == RCU_SCHEDULER_INACTIVE)
5098 		return 0; /* Too early in boot for scheduler work. */
5099 	sync_sched_exp_online_cleanup(cpu);
5100 	rcutree_affinity_setting(cpu, -1);
5101 
5102 	// Stop-machine done, so allow nohz_full to disable tick.
5103 	tick_dep_clear(TICK_DEP_BIT_RCU);
5104 	return 0;
5105 }
5106 
5107 /*
5108  * Mark the specified CPU as being online so that subsequent grace periods
5109  * (both expedited and normal) will wait on it.  Note that this means that
5110  * incoming CPUs are not allowed to use RCU read-side critical sections
5111  * until this function is called.  Failing to observe this restriction
5112  * will result in lockdep splats.
5113  *
5114  * Note that this function is special in that it is invoked directly
5115  * from the incoming CPU rather than from the cpuhp_step mechanism.
5116  * This is because this function must be invoked at a precise location.
5117  * This incoming CPU must not have enabled interrupts yet.
5118  *
5119  * This mirrors the effects of rcutree_report_cpu_dead().
5120  */
5121 void rcutree_report_cpu_starting(unsigned int cpu)
5122 {
5123 	unsigned long mask;
5124 	struct rcu_data *rdp;
5125 	struct rcu_node *rnp;
5126 	bool newcpu;
5127 
5128 	lockdep_assert_irqs_disabled();
5129 	rdp = per_cpu_ptr(&rcu_data, cpu);
5130 	if (rdp->cpu_started)
5131 		return;
5132 	rdp->cpu_started = true;
5133 
5134 	rnp = rdp->mynode;
5135 	mask = rdp->grpmask;
5136 	arch_spin_lock(&rcu_state.ofl_lock);
5137 	rcu_watching_online();
5138 	raw_spin_lock(&rcu_state.barrier_lock);
5139 	raw_spin_lock_rcu_node(rnp);
5140 	WRITE_ONCE(rnp->qsmaskinitnext, rnp->qsmaskinitnext | mask);
5141 	raw_spin_unlock(&rcu_state.barrier_lock);
5142 	newcpu = !(rnp->expmaskinitnext & mask);
5143 	rnp->expmaskinitnext |= mask;
5144 	/* Allow lockless access for expedited grace periods. */
5145 	smp_store_release(&rcu_state.ncpus, rcu_state.ncpus + newcpu); /* ^^^ */
5146 	ASSERT_EXCLUSIVE_WRITER(rcu_state.ncpus);
5147 	rcu_gpnum_ovf(rnp, rdp); /* Offline-induced counter wrap? */
5148 	rdp->rcu_onl_gp_seq = READ_ONCE(rcu_state.gp_seq);
5149 	rdp->rcu_onl_gp_state = READ_ONCE(rcu_state.gp_state);
5150 
5151 	/* An incoming CPU should never be blocking a grace period. */
5152 	if (WARN_ON_ONCE(rnp->qsmask & mask)) { /* RCU waiting on incoming CPU? */
5153 		/* rcu_report_qs_rnp() *really* wants some flags to restore */
5154 		unsigned long flags;
5155 
5156 		local_irq_save(flags);
5157 		rcu_disable_urgency_upon_qs(rdp);
5158 		/* Report QS -after- changing ->qsmaskinitnext! */
5159 		rcu_report_qs_rnp(mask, rnp, rnp->gp_seq, flags);
5160 	} else {
5161 		raw_spin_unlock_rcu_node(rnp);
5162 	}
5163 	arch_spin_unlock(&rcu_state.ofl_lock);
5164 	smp_store_release(&rdp->beenonline, true);
5165 	smp_mb(); /* Ensure RCU read-side usage follows above initialization. */
5166 }
5167 
5168 /*
5169  * The outgoing function has no further need of RCU, so remove it from
5170  * the rcu_node tree's ->qsmaskinitnext bit masks.
5171  *
5172  * Note that this function is special in that it is invoked directly
5173  * from the outgoing CPU rather than from the cpuhp_step mechanism.
5174  * This is because this function must be invoked at a precise location.
5175  *
5176  * This mirrors the effect of rcutree_report_cpu_starting().
5177  */
5178 void rcutree_report_cpu_dead(void)
5179 {
5180 	unsigned long flags;
5181 	unsigned long mask;
5182 	struct rcu_data *rdp = this_cpu_ptr(&rcu_data);
5183 	struct rcu_node *rnp = rdp->mynode;  /* Outgoing CPU's rdp & rnp. */
5184 
5185 	/*
5186 	 * IRQS must be disabled from now on and until the CPU dies, or an interrupt
5187 	 * may introduce a new READ-side while it is actually off the QS masks.
5188 	 */
5189 	lockdep_assert_irqs_disabled();
5190 	// Do any dangling deferred wakeups.
5191 	do_nocb_deferred_wakeup(rdp);
5192 
5193 	rcu_preempt_deferred_qs(current);
5194 
5195 	/* Remove outgoing CPU from mask in the leaf rcu_node structure. */
5196 	mask = rdp->grpmask;
5197 	arch_spin_lock(&rcu_state.ofl_lock);
5198 	raw_spin_lock_irqsave_rcu_node(rnp, flags); /* Enforce GP memory-order guarantee. */
5199 	rdp->rcu_ofl_gp_seq = READ_ONCE(rcu_state.gp_seq);
5200 	rdp->rcu_ofl_gp_state = READ_ONCE(rcu_state.gp_state);
5201 	if (rnp->qsmask & mask) { /* RCU waiting on outgoing CPU? */
5202 		/* Report quiescent state -before- changing ->qsmaskinitnext! */
5203 		rcu_disable_urgency_upon_qs(rdp);
5204 		rcu_report_qs_rnp(mask, rnp, rnp->gp_seq, flags);
5205 		raw_spin_lock_irqsave_rcu_node(rnp, flags);
5206 	}
5207 	WRITE_ONCE(rnp->qsmaskinitnext, rnp->qsmaskinitnext & ~mask);
5208 	raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
5209 	arch_spin_unlock(&rcu_state.ofl_lock);
5210 	rdp->cpu_started = false;
5211 }
5212 
5213 #ifdef CONFIG_HOTPLUG_CPU
5214 /*
5215  * The outgoing CPU has just passed through the dying-idle state, and we
5216  * are being invoked from the CPU that was IPIed to continue the offline
5217  * operation.  Migrate the outgoing CPU's callbacks to the current CPU.
5218  */
5219 void rcutree_migrate_callbacks(int cpu)
5220 {
5221 	unsigned long flags;
5222 	struct rcu_data *my_rdp;
5223 	struct rcu_node *my_rnp;
5224 	struct rcu_data *rdp = per_cpu_ptr(&rcu_data, cpu);
5225 	bool needwake;
5226 
5227 	if (rcu_rdp_is_offloaded(rdp))
5228 		return;
5229 
5230 	raw_spin_lock_irqsave(&rcu_state.barrier_lock, flags);
5231 	if (rcu_segcblist_empty(&rdp->cblist)) {
5232 		raw_spin_unlock_irqrestore(&rcu_state.barrier_lock, flags);
5233 		return;  /* No callbacks to migrate. */
5234 	}
5235 
5236 	WARN_ON_ONCE(rcu_rdp_cpu_online(rdp));
5237 	rcu_barrier_entrain(rdp);
5238 	my_rdp = this_cpu_ptr(&rcu_data);
5239 	my_rnp = my_rdp->mynode;
5240 	rcu_nocb_lock(my_rdp); /* irqs already disabled. */
5241 	WARN_ON_ONCE(!rcu_nocb_flush_bypass(my_rdp, NULL, jiffies, false));
5242 	raw_spin_lock_rcu_node(my_rnp); /* irqs already disabled. */
5243 	/* Leverage recent GPs and set GP for new callbacks. */
5244 	needwake = rcu_advance_cbs(my_rnp, rdp) ||
5245 		   rcu_advance_cbs(my_rnp, my_rdp);
5246 	rcu_segcblist_merge(&my_rdp->cblist, &rdp->cblist);
5247 	raw_spin_unlock(&rcu_state.barrier_lock); /* irqs remain disabled. */
5248 	needwake = needwake || rcu_advance_cbs(my_rnp, my_rdp);
5249 	rcu_segcblist_disable(&rdp->cblist);
5250 	WARN_ON_ONCE(rcu_segcblist_empty(&my_rdp->cblist) != !rcu_segcblist_n_cbs(&my_rdp->cblist));
5251 	check_cb_ovld_locked(my_rdp, my_rnp);
5252 	if (rcu_rdp_is_offloaded(my_rdp)) {
5253 		raw_spin_unlock_rcu_node(my_rnp); /* irqs remain disabled. */
5254 		__call_rcu_nocb_wake(my_rdp, true, flags);
5255 	} else {
5256 		rcu_nocb_unlock(my_rdp); /* irqs remain disabled. */
5257 		raw_spin_unlock_rcu_node(my_rnp); /* irqs remain disabled. */
5258 	}
5259 	local_irq_restore(flags);
5260 	if (needwake)
5261 		rcu_gp_kthread_wake();
5262 	lockdep_assert_irqs_enabled();
5263 	WARN_ONCE(rcu_segcblist_n_cbs(&rdp->cblist) != 0 ||
5264 		  !rcu_segcblist_empty(&rdp->cblist),
5265 		  "rcu_cleanup_dead_cpu: Callbacks on offline CPU %d: qlen=%lu, 1stCB=%p\n",
5266 		  cpu, rcu_segcblist_n_cbs(&rdp->cblist),
5267 		  rcu_segcblist_first_cb(&rdp->cblist));
5268 }
5269 
5270 /*
5271  * The CPU has been completely removed, and some other CPU is reporting
5272  * this fact from process context.  Do the remainder of the cleanup.
5273  * There can only be one CPU hotplug operation at a time, so no need for
5274  * explicit locking.
5275  */
5276 int rcutree_dead_cpu(unsigned int cpu)
5277 {
5278 	ASSERT_EXCLUSIVE_WRITER(rcu_state.n_online_cpus);
5279 	WRITE_ONCE(rcu_state.n_online_cpus, rcu_state.n_online_cpus - 1);
5280 	// Stop-machine done, so allow nohz_full to disable tick.
5281 	tick_dep_clear(TICK_DEP_BIT_RCU);
5282 	return 0;
5283 }
5284 
5285 /*
5286  * Near the end of the offline process.  Trace the fact that this CPU
5287  * is going offline.
5288  */
5289 int rcutree_dying_cpu(unsigned int cpu)
5290 {
5291 	bool blkd;
5292 	struct rcu_data *rdp = per_cpu_ptr(&rcu_data, cpu);
5293 	struct rcu_node *rnp = rdp->mynode;
5294 
5295 	blkd = !!(READ_ONCE(rnp->qsmask) & rdp->grpmask);
5296 	trace_rcu_grace_period(rcu_state.name, READ_ONCE(rnp->gp_seq),
5297 			       blkd ? TPS("cpuofl-bgp") : TPS("cpuofl"));
5298 	return 0;
5299 }
5300 
5301 /*
5302  * Near the beginning of the process.  The CPU is still very much alive
5303  * with pretty much all services enabled.
5304  */
5305 int rcutree_offline_cpu(unsigned int cpu)
5306 {
5307 	unsigned long flags;
5308 	struct rcu_data *rdp;
5309 	struct rcu_node *rnp;
5310 
5311 	rdp = per_cpu_ptr(&rcu_data, cpu);
5312 	rnp = rdp->mynode;
5313 	raw_spin_lock_irqsave_rcu_node(rnp, flags);
5314 	rnp->ffmask &= ~rdp->grpmask;
5315 	raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
5316 
5317 	rcutree_affinity_setting(cpu, cpu);
5318 
5319 	// nohz_full CPUs need the tick for stop-machine to work quickly
5320 	tick_dep_set(TICK_DEP_BIT_RCU);
5321 	return 0;
5322 }
5323 #endif /* #ifdef CONFIG_HOTPLUG_CPU */
5324 
5325 /*
5326  * On non-huge systems, use expedited RCU grace periods to make suspend
5327  * and hibernation run faster.
5328  */
5329 static int rcu_pm_notify(struct notifier_block *self,
5330 			 unsigned long action, void *hcpu)
5331 {
5332 	switch (action) {
5333 	case PM_HIBERNATION_PREPARE:
5334 	case PM_SUSPEND_PREPARE:
5335 		rcu_async_hurry();
5336 		rcu_expedite_gp();
5337 		break;
5338 	case PM_POST_HIBERNATION:
5339 	case PM_POST_SUSPEND:
5340 		rcu_unexpedite_gp();
5341 		rcu_async_relax();
5342 		break;
5343 	default:
5344 		break;
5345 	}
5346 	return NOTIFY_OK;
5347 }
5348 
5349 /*
5350  * Spawn the kthreads that handle RCU's grace periods.
5351  */
5352 static int __init rcu_spawn_gp_kthread(void)
5353 {
5354 	unsigned long flags;
5355 	struct rcu_node *rnp;
5356 	struct sched_param sp;
5357 	struct task_struct *t;
5358 	struct rcu_data *rdp = this_cpu_ptr(&rcu_data);
5359 
5360 	rcu_scheduler_fully_active = 1;
5361 	t = kthread_create(rcu_gp_kthread, NULL, "%s", rcu_state.name);
5362 	if (WARN_ONCE(IS_ERR(t), "%s: Could not start grace-period kthread, OOM is now expected behavior\n", __func__))
5363 		return 0;
5364 	if (kthread_prio) {
5365 		sp.sched_priority = kthread_prio;
5366 		sched_setscheduler_nocheck(t, SCHED_FIFO, &sp);
5367 	}
5368 	rnp = rcu_get_root();
5369 	raw_spin_lock_irqsave_rcu_node(rnp, flags);
5370 	WRITE_ONCE(rcu_state.gp_activity, jiffies);
5371 	WRITE_ONCE(rcu_state.gp_req_activity, jiffies);
5372 	// Reset .gp_activity and .gp_req_activity before setting .gp_kthread.
5373 	smp_store_release(&rcu_state.gp_kthread, t);  /* ^^^ */
5374 	raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
5375 	wake_up_process(t);
5376 	/* This is a pre-SMP initcall, we expect a single CPU */
5377 	WARN_ON(num_online_cpus() > 1);
5378 	/*
5379 	 * Those kthreads couldn't be created on rcu_init() -> rcutree_prepare_cpu()
5380 	 * due to rcu_scheduler_fully_active.
5381 	 */
5382 	rcu_spawn_cpu_nocb_kthread(smp_processor_id());
5383 	rcu_spawn_rnp_kthreads(rdp->mynode);
5384 	rcu_spawn_core_kthreads();
5385 	/* Create kthread worker for expedited GPs */
5386 	rcu_start_exp_gp_kworker();
5387 	return 0;
5388 }
5389 early_initcall(rcu_spawn_gp_kthread);
5390 
5391 /*
5392  * This function is invoked towards the end of the scheduler's
5393  * initialization process.  Before this is called, the idle task might
5394  * contain synchronous grace-period primitives (during which time, this idle
5395  * task is booting the system, and such primitives are no-ops).  After this
5396  * function is called, any synchronous grace-period primitives are run as
5397  * expedited, with the requesting task driving the grace period forward.
5398  * A later core_initcall() rcu_set_runtime_mode() will switch to full
5399  * runtime RCU functionality.
5400  */
5401 void rcu_scheduler_starting(void)
5402 {
5403 	unsigned long flags;
5404 	struct rcu_node *rnp;
5405 
5406 	WARN_ON(num_online_cpus() != 1);
5407 	WARN_ON(nr_context_switches() > 0);
5408 	rcu_test_sync_prims();
5409 
5410 	// Fix up the ->gp_seq counters.
5411 	local_irq_save(flags);
5412 	rcu_for_each_node_breadth_first(rnp)
5413 		rnp->gp_seq_needed = rnp->gp_seq = rcu_state.gp_seq;
5414 	local_irq_restore(flags);
5415 
5416 	// Switch out of early boot mode.
5417 	rcu_scheduler_active = RCU_SCHEDULER_INIT;
5418 	rcu_test_sync_prims();
5419 }
5420 
5421 /*
5422  * Helper function for rcu_init() that initializes the rcu_state structure.
5423  */
5424 static void __init rcu_init_one(void)
5425 {
5426 	static const char * const buf[] = RCU_NODE_NAME_INIT;
5427 	static const char * const fqs[] = RCU_FQS_NAME_INIT;
5428 	static struct lock_class_key rcu_node_class[RCU_NUM_LVLS];
5429 	static struct lock_class_key rcu_fqs_class[RCU_NUM_LVLS];
5430 
5431 	int levelspread[RCU_NUM_LVLS];		/* kids/node in each level. */
5432 	int cpustride = 1;
5433 	int i;
5434 	int j;
5435 	struct rcu_node *rnp;
5436 
5437 	BUILD_BUG_ON(RCU_NUM_LVLS > ARRAY_SIZE(buf));  /* Fix buf[] init! */
5438 
5439 	/* Silence gcc 4.8 false positive about array index out of range. */
5440 	if (rcu_num_lvls <= 0 || rcu_num_lvls > RCU_NUM_LVLS)
5441 		panic("rcu_init_one: rcu_num_lvls out of range");
5442 
5443 	/* Initialize the level-tracking arrays. */
5444 
5445 	for (i = 1; i < rcu_num_lvls; i++)
5446 		rcu_state.level[i] =
5447 			rcu_state.level[i - 1] + num_rcu_lvl[i - 1];
5448 	rcu_init_levelspread(levelspread, num_rcu_lvl);
5449 
5450 	/* Initialize the elements themselves, starting from the leaves. */
5451 
5452 	for (i = rcu_num_lvls - 1; i >= 0; i--) {
5453 		cpustride *= levelspread[i];
5454 		rnp = rcu_state.level[i];
5455 		for (j = 0; j < num_rcu_lvl[i]; j++, rnp++) {
5456 			raw_spin_lock_init(&ACCESS_PRIVATE(rnp, lock));
5457 			lockdep_set_class_and_name(&ACCESS_PRIVATE(rnp, lock),
5458 						   &rcu_node_class[i], buf[i]);
5459 			raw_spin_lock_init(&rnp->fqslock);
5460 			lockdep_set_class_and_name(&rnp->fqslock,
5461 						   &rcu_fqs_class[i], fqs[i]);
5462 			rnp->gp_seq = rcu_state.gp_seq;
5463 			rnp->gp_seq_needed = rcu_state.gp_seq;
5464 			rnp->completedqs = rcu_state.gp_seq;
5465 			rnp->qsmask = 0;
5466 			rnp->qsmaskinit = 0;
5467 			rnp->grplo = j * cpustride;
5468 			rnp->grphi = (j + 1) * cpustride - 1;
5469 			if (rnp->grphi >= nr_cpu_ids)
5470 				rnp->grphi = nr_cpu_ids - 1;
5471 			if (i == 0) {
5472 				rnp->grpnum = 0;
5473 				rnp->grpmask = 0;
5474 				rnp->parent = NULL;
5475 			} else {
5476 				rnp->grpnum = j % levelspread[i - 1];
5477 				rnp->grpmask = BIT(rnp->grpnum);
5478 				rnp->parent = rcu_state.level[i - 1] +
5479 					      j / levelspread[i - 1];
5480 			}
5481 			rnp->level = i;
5482 			INIT_LIST_HEAD(&rnp->blkd_tasks);
5483 			rcu_init_one_nocb(rnp);
5484 			init_waitqueue_head(&rnp->exp_wq[0]);
5485 			init_waitqueue_head(&rnp->exp_wq[1]);
5486 			init_waitqueue_head(&rnp->exp_wq[2]);
5487 			init_waitqueue_head(&rnp->exp_wq[3]);
5488 			spin_lock_init(&rnp->exp_lock);
5489 			mutex_init(&rnp->kthread_mutex);
5490 			raw_spin_lock_init(&rnp->exp_poll_lock);
5491 			rnp->exp_seq_poll_rq = RCU_GET_STATE_COMPLETED;
5492 			INIT_WORK(&rnp->exp_poll_wq, sync_rcu_do_polled_gp);
5493 		}
5494 	}
5495 
5496 	init_swait_queue_head(&rcu_state.gp_wq);
5497 	init_swait_queue_head(&rcu_state.expedited_wq);
5498 	rnp = rcu_first_leaf_node();
5499 	for_each_possible_cpu(i) {
5500 		while (i > rnp->grphi)
5501 			rnp++;
5502 		per_cpu_ptr(&rcu_data, i)->mynode = rnp;
5503 		per_cpu_ptr(&rcu_data, i)->barrier_head.next =
5504 			&per_cpu_ptr(&rcu_data, i)->barrier_head;
5505 		rcu_boot_init_percpu_data(i);
5506 	}
5507 }
5508 
5509 /*
5510  * Force priority from the kernel command-line into range.
5511  */
5512 static void __init sanitize_kthread_prio(void)
5513 {
5514 	int kthread_prio_in = kthread_prio;
5515 
5516 	if (IS_ENABLED(CONFIG_RCU_BOOST) && kthread_prio < 2
5517 	    && IS_BUILTIN(CONFIG_RCU_TORTURE_TEST))
5518 		kthread_prio = 2;
5519 	else if (IS_ENABLED(CONFIG_RCU_BOOST) && kthread_prio < 1)
5520 		kthread_prio = 1;
5521 	else if (kthread_prio < 0)
5522 		kthread_prio = 0;
5523 	else if (kthread_prio > 99)
5524 		kthread_prio = 99;
5525 
5526 	if (kthread_prio != kthread_prio_in)
5527 		pr_alert("%s: Limited prio to %d from %d\n",
5528 			 __func__, kthread_prio, kthread_prio_in);
5529 }
5530 
5531 /*
5532  * Compute the rcu_node tree geometry from kernel parameters.  This cannot
5533  * replace the definitions in tree.h because those are needed to size
5534  * the ->node array in the rcu_state structure.
5535  */
5536 void rcu_init_geometry(void)
5537 {
5538 	ulong d;
5539 	int i;
5540 	static unsigned long old_nr_cpu_ids;
5541 	int rcu_capacity[RCU_NUM_LVLS];
5542 	static bool initialized;
5543 
5544 	if (initialized) {
5545 		/*
5546 		 * Warn if setup_nr_cpu_ids() had not yet been invoked,
5547 		 * unless nr_cpus_ids == NR_CPUS, in which case who cares?
5548 		 */
5549 		WARN_ON_ONCE(old_nr_cpu_ids != nr_cpu_ids);
5550 		return;
5551 	}
5552 
5553 	old_nr_cpu_ids = nr_cpu_ids;
5554 	initialized = true;
5555 
5556 	/*
5557 	 * Initialize any unspecified boot parameters.
5558 	 * The default values of jiffies_till_first_fqs and
5559 	 * jiffies_till_next_fqs are set to the RCU_JIFFIES_TILL_FORCE_QS
5560 	 * value, which is a function of HZ, then adding one for each
5561 	 * RCU_JIFFIES_FQS_DIV CPUs that might be on the system.
5562 	 */
5563 	d = RCU_JIFFIES_TILL_FORCE_QS + nr_cpu_ids / RCU_JIFFIES_FQS_DIV;
5564 	if (jiffies_till_first_fqs == ULONG_MAX)
5565 		jiffies_till_first_fqs = d;
5566 	if (jiffies_till_next_fqs == ULONG_MAX)
5567 		jiffies_till_next_fqs = d;
5568 	adjust_jiffies_till_sched_qs();
5569 
5570 	/* If the compile-time values are accurate, just leave. */
5571 	if (rcu_fanout_leaf == RCU_FANOUT_LEAF &&
5572 	    nr_cpu_ids == NR_CPUS)
5573 		return;
5574 	pr_info("Adjusting geometry for rcu_fanout_leaf=%d, nr_cpu_ids=%u\n",
5575 		rcu_fanout_leaf, nr_cpu_ids);
5576 
5577 	/*
5578 	 * The boot-time rcu_fanout_leaf parameter must be at least two
5579 	 * and cannot exceed the number of bits in the rcu_node masks.
5580 	 * Complain and fall back to the compile-time values if this
5581 	 * limit is exceeded.
5582 	 */
5583 	if (rcu_fanout_leaf < 2 ||
5584 	    rcu_fanout_leaf > sizeof(unsigned long) * 8) {
5585 		rcu_fanout_leaf = RCU_FANOUT_LEAF;
5586 		WARN_ON(1);
5587 		return;
5588 	}
5589 
5590 	/*
5591 	 * Compute number of nodes that can be handled an rcu_node tree
5592 	 * with the given number of levels.
5593 	 */
5594 	rcu_capacity[0] = rcu_fanout_leaf;
5595 	for (i = 1; i < RCU_NUM_LVLS; i++)
5596 		rcu_capacity[i] = rcu_capacity[i - 1] * RCU_FANOUT;
5597 
5598 	/*
5599 	 * The tree must be able to accommodate the configured number of CPUs.
5600 	 * If this limit is exceeded, fall back to the compile-time values.
5601 	 */
5602 	if (nr_cpu_ids > rcu_capacity[RCU_NUM_LVLS - 1]) {
5603 		rcu_fanout_leaf = RCU_FANOUT_LEAF;
5604 		WARN_ON(1);
5605 		return;
5606 	}
5607 
5608 	/* Calculate the number of levels in the tree. */
5609 	for (i = 0; nr_cpu_ids > rcu_capacity[i]; i++) {
5610 	}
5611 	rcu_num_lvls = i + 1;
5612 
5613 	/* Calculate the number of rcu_nodes at each level of the tree. */
5614 	for (i = 0; i < rcu_num_lvls; i++) {
5615 		int cap = rcu_capacity[(rcu_num_lvls - 1) - i];
5616 		num_rcu_lvl[i] = DIV_ROUND_UP(nr_cpu_ids, cap);
5617 	}
5618 
5619 	/* Calculate the total number of rcu_node structures. */
5620 	rcu_num_nodes = 0;
5621 	for (i = 0; i < rcu_num_lvls; i++)
5622 		rcu_num_nodes += num_rcu_lvl[i];
5623 }
5624 
5625 /*
5626  * Dump out the structure of the rcu_node combining tree associated
5627  * with the rcu_state structure.
5628  */
5629 static void __init rcu_dump_rcu_node_tree(void)
5630 {
5631 	int level = 0;
5632 	struct rcu_node *rnp;
5633 
5634 	pr_info("rcu_node tree layout dump\n");
5635 	pr_info(" ");
5636 	rcu_for_each_node_breadth_first(rnp) {
5637 		if (rnp->level != level) {
5638 			pr_cont("\n");
5639 			pr_info(" ");
5640 			level = rnp->level;
5641 		}
5642 		pr_cont("%d:%d ^%d  ", rnp->grplo, rnp->grphi, rnp->grpnum);
5643 	}
5644 	pr_cont("\n");
5645 }
5646 
5647 struct workqueue_struct *rcu_gp_wq;
5648 
5649 static void __init kfree_rcu_batch_init(void)
5650 {
5651 	int cpu;
5652 	int i, j;
5653 	struct shrinker *kfree_rcu_shrinker;
5654 
5655 	/* Clamp it to [0:100] seconds interval. */
5656 	if (rcu_delay_page_cache_fill_msec < 0 ||
5657 		rcu_delay_page_cache_fill_msec > 100 * MSEC_PER_SEC) {
5658 
5659 		rcu_delay_page_cache_fill_msec =
5660 			clamp(rcu_delay_page_cache_fill_msec, 0,
5661 				(int) (100 * MSEC_PER_SEC));
5662 
5663 		pr_info("Adjusting rcutree.rcu_delay_page_cache_fill_msec to %d ms.\n",
5664 			rcu_delay_page_cache_fill_msec);
5665 	}
5666 
5667 	for_each_possible_cpu(cpu) {
5668 		struct kfree_rcu_cpu *krcp = per_cpu_ptr(&krc, cpu);
5669 
5670 		for (i = 0; i < KFREE_N_BATCHES; i++) {
5671 			INIT_RCU_WORK(&krcp->krw_arr[i].rcu_work, kfree_rcu_work);
5672 			krcp->krw_arr[i].krcp = krcp;
5673 
5674 			for (j = 0; j < FREE_N_CHANNELS; j++)
5675 				INIT_LIST_HEAD(&krcp->krw_arr[i].bulk_head_free[j]);
5676 		}
5677 
5678 		for (i = 0; i < FREE_N_CHANNELS; i++)
5679 			INIT_LIST_HEAD(&krcp->bulk_head[i]);
5680 
5681 		INIT_DELAYED_WORK(&krcp->monitor_work, kfree_rcu_monitor);
5682 		INIT_DELAYED_WORK(&krcp->page_cache_work, fill_page_cache_func);
5683 		krcp->initialized = true;
5684 	}
5685 
5686 	kfree_rcu_shrinker = shrinker_alloc(0, "rcu-kfree");
5687 	if (!kfree_rcu_shrinker) {
5688 		pr_err("Failed to allocate kfree_rcu() shrinker!\n");
5689 		return;
5690 	}
5691 
5692 	kfree_rcu_shrinker->count_objects = kfree_rcu_shrink_count;
5693 	kfree_rcu_shrinker->scan_objects = kfree_rcu_shrink_scan;
5694 
5695 	shrinker_register(kfree_rcu_shrinker);
5696 }
5697 
5698 void __init rcu_init(void)
5699 {
5700 	int cpu = smp_processor_id();
5701 
5702 	rcu_early_boot_tests();
5703 
5704 	kfree_rcu_batch_init();
5705 	rcu_bootup_announce();
5706 	sanitize_kthread_prio();
5707 	rcu_init_geometry();
5708 	rcu_init_one();
5709 	if (dump_tree)
5710 		rcu_dump_rcu_node_tree();
5711 	if (use_softirq)
5712 		open_softirq(RCU_SOFTIRQ, rcu_core_si);
5713 
5714 	/*
5715 	 * We don't need protection against CPU-hotplug here because
5716 	 * this is called early in boot, before either interrupts
5717 	 * or the scheduler are operational.
5718 	 */
5719 	pm_notifier(rcu_pm_notify, 0);
5720 	WARN_ON(num_online_cpus() > 1); // Only one CPU this early in boot.
5721 	rcutree_prepare_cpu(cpu);
5722 	rcutree_report_cpu_starting(cpu);
5723 	rcutree_online_cpu(cpu);
5724 
5725 	/* Create workqueue for Tree SRCU and for expedited GPs. */
5726 	rcu_gp_wq = alloc_workqueue("rcu_gp", WQ_MEM_RECLAIM, 0);
5727 	WARN_ON(!rcu_gp_wq);
5728 
5729 	sync_wq = alloc_workqueue("sync_wq", WQ_MEM_RECLAIM, 0);
5730 	WARN_ON(!sync_wq);
5731 
5732 	/* Fill in default value for rcutree.qovld boot parameter. */
5733 	/* -After- the rcu_node ->lock fields are initialized! */
5734 	if (qovld < 0)
5735 		qovld_calc = DEFAULT_RCU_QOVLD_MULT * qhimark;
5736 	else
5737 		qovld_calc = qovld;
5738 
5739 	// Kick-start in case any polled grace periods started early.
5740 	(void)start_poll_synchronize_rcu_expedited();
5741 
5742 	rcu_test_sync_prims();
5743 
5744 	tasks_cblist_init_generic();
5745 }
5746 
5747 #include "tree_stall.h"
5748 #include "tree_exp.h"
5749 #include "tree_nocb.h"
5750 #include "tree_plugin.h"
5751