linux - kernel/rcu/tree.c

5004 lines · 166.3 KiB

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