xref: /openbmc/linux/kernel/rcu/tree.c (revision ae3473231e77a3f1909d48cd144cebe5e1d049b3)
1 /*
2  * Read-Copy Update mechanism for mutual exclusion
3  *
4  * This program is free software; you can redistribute it and/or modify
5  * it under the terms of the GNU General Public License as published by
6  * the Free Software Foundation; either version 2 of the License, or
7  * (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, you can access it online at
16  * http://www.gnu.org/licenses/gpl-2.0.html.
17  *
18  * Copyright IBM Corporation, 2008
19  *
20  * Authors: Dipankar Sarma <dipankar@in.ibm.com>
21  *	    Manfred Spraul <manfred@colorfullife.com>
22  *	    Paul E. McKenney <paulmck@linux.vnet.ibm.com> Hierarchical version
23  *
24  * Based on the original work by Paul McKenney <paulmck@us.ibm.com>
25  * and inputs from Rusty Russell, Andrea Arcangeli and Andi Kleen.
26  *
27  * For detailed explanation of Read-Copy Update mechanism see -
28  *	Documentation/RCU
29  */
30 #include <linux/types.h>
31 #include <linux/kernel.h>
32 #include <linux/init.h>
33 #include <linux/spinlock.h>
34 #include <linux/smp.h>
35 #include <linux/rcupdate.h>
36 #include <linux/interrupt.h>
37 #include <linux/sched.h>
38 #include <linux/nmi.h>
39 #include <linux/atomic.h>
40 #include <linux/bitops.h>
41 #include <linux/export.h>
42 #include <linux/completion.h>
43 #include <linux/moduleparam.h>
44 #include <linux/percpu.h>
45 #include <linux/notifier.h>
46 #include <linux/cpu.h>
47 #include <linux/mutex.h>
48 #include <linux/time.h>
49 #include <linux/kernel_stat.h>
50 #include <linux/wait.h>
51 #include <linux/kthread.h>
52 #include <linux/prefetch.h>
53 #include <linux/delay.h>
54 #include <linux/stop_machine.h>
55 #include <linux/random.h>
56 #include <linux/trace_events.h>
57 #include <linux/suspend.h>
58 
59 #include "tree.h"
60 #include "rcu.h"
61 
62 #ifdef MODULE_PARAM_PREFIX
63 #undef MODULE_PARAM_PREFIX
64 #endif
65 #define MODULE_PARAM_PREFIX "rcutree."
66 
67 /* Data structures. */
68 
69 /*
70  * In order to export the rcu_state name to the tracing tools, it
71  * needs to be added in the __tracepoint_string section.
72  * This requires defining a separate variable tp_<sname>_varname
73  * that points to the string being used, and this will allow
74  * the tracing userspace tools to be able to decipher the string
75  * address to the matching string.
76  */
77 #ifdef CONFIG_TRACING
78 # define DEFINE_RCU_TPS(sname) \
79 static char sname##_varname[] = #sname; \
80 static const char *tp_##sname##_varname __used __tracepoint_string = sname##_varname;
81 # define RCU_STATE_NAME(sname) sname##_varname
82 #else
83 # define DEFINE_RCU_TPS(sname)
84 # define RCU_STATE_NAME(sname) __stringify(sname)
85 #endif
86 
87 #define RCU_STATE_INITIALIZER(sname, sabbr, cr) \
88 DEFINE_RCU_TPS(sname) \
89 static DEFINE_PER_CPU_SHARED_ALIGNED(struct rcu_data, sname##_data); \
90 struct rcu_state sname##_state = { \
91 	.level = { &sname##_state.node[0] }, \
92 	.rda = &sname##_data, \
93 	.call = cr, \
94 	.gp_state = RCU_GP_IDLE, \
95 	.gpnum = 0UL - 300UL, \
96 	.completed = 0UL - 300UL, \
97 	.orphan_lock = __RAW_SPIN_LOCK_UNLOCKED(&sname##_state.orphan_lock), \
98 	.orphan_nxttail = &sname##_state.orphan_nxtlist, \
99 	.orphan_donetail = &sname##_state.orphan_donelist, \
100 	.barrier_mutex = __MUTEX_INITIALIZER(sname##_state.barrier_mutex), \
101 	.name = RCU_STATE_NAME(sname), \
102 	.abbr = sabbr, \
103 	.exp_mutex = __MUTEX_INITIALIZER(sname##_state.exp_mutex), \
104 	.exp_wake_mutex = __MUTEX_INITIALIZER(sname##_state.exp_wake_mutex), \
105 }
106 
107 RCU_STATE_INITIALIZER(rcu_sched, 's', call_rcu_sched);
108 RCU_STATE_INITIALIZER(rcu_bh, 'b', call_rcu_bh);
109 
110 static struct rcu_state *const rcu_state_p;
111 LIST_HEAD(rcu_struct_flavors);
112 
113 /* Dump rcu_node combining tree at boot to verify correct setup. */
114 static bool dump_tree;
115 module_param(dump_tree, bool, 0444);
116 /* Control rcu_node-tree auto-balancing at boot time. */
117 static bool rcu_fanout_exact;
118 module_param(rcu_fanout_exact, bool, 0444);
119 /* Increase (but not decrease) the RCU_FANOUT_LEAF at boot time. */
120 static int rcu_fanout_leaf = RCU_FANOUT_LEAF;
121 module_param(rcu_fanout_leaf, int, 0444);
122 int rcu_num_lvls __read_mostly = RCU_NUM_LVLS;
123 /* Number of rcu_nodes at specified level. */
124 static int num_rcu_lvl[] = NUM_RCU_LVL_INIT;
125 int rcu_num_nodes __read_mostly = NUM_RCU_NODES; /* Total # rcu_nodes in use. */
126 /* panic() on RCU Stall sysctl. */
127 int sysctl_panic_on_rcu_stall __read_mostly;
128 
129 /*
130  * The rcu_scheduler_active variable transitions from zero to one just
131  * before the first task is spawned.  So when this variable is zero, RCU
132  * can assume that there is but one task, allowing RCU to (for example)
133  * optimize synchronize_rcu() to a simple barrier().  When this variable
134  * is one, RCU must actually do all the hard work required to detect real
135  * grace periods.  This variable is also used to suppress boot-time false
136  * positives from lockdep-RCU error checking.
137  */
138 int rcu_scheduler_active __read_mostly;
139 EXPORT_SYMBOL_GPL(rcu_scheduler_active);
140 
141 /*
142  * The rcu_scheduler_fully_active variable transitions from zero to one
143  * during the early_initcall() processing, which is after the scheduler
144  * is capable of creating new tasks.  So RCU processing (for example,
145  * creating tasks for RCU priority boosting) must be delayed until after
146  * rcu_scheduler_fully_active transitions from zero to one.  We also
147  * currently delay invocation of any RCU callbacks until after this point.
148  *
149  * It might later prove better for people registering RCU callbacks during
150  * early boot to take responsibility for these callbacks, but one step at
151  * a time.
152  */
153 static int rcu_scheduler_fully_active __read_mostly;
154 
155 static void rcu_init_new_rnp(struct rcu_node *rnp_leaf);
156 static void rcu_cleanup_dead_rnp(struct rcu_node *rnp_leaf);
157 static void rcu_boost_kthread_setaffinity(struct rcu_node *rnp, int outgoingcpu);
158 static void invoke_rcu_core(void);
159 static void invoke_rcu_callbacks(struct rcu_state *rsp, struct rcu_data *rdp);
160 static void rcu_report_exp_rdp(struct rcu_state *rsp,
161 			       struct rcu_data *rdp, bool wake);
162 static void sync_sched_exp_online_cleanup(int cpu);
163 
164 /* rcuc/rcub kthread realtime priority */
165 #ifdef CONFIG_RCU_KTHREAD_PRIO
166 static int kthread_prio = CONFIG_RCU_KTHREAD_PRIO;
167 #else /* #ifdef CONFIG_RCU_KTHREAD_PRIO */
168 static int kthread_prio = IS_ENABLED(CONFIG_RCU_BOOST) ? 1 : 0;
169 #endif /* #else #ifdef CONFIG_RCU_KTHREAD_PRIO */
170 module_param(kthread_prio, int, 0644);
171 
172 /* Delay in jiffies for grace-period initialization delays, debug only. */
173 
174 #ifdef CONFIG_RCU_TORTURE_TEST_SLOW_PREINIT
175 static int gp_preinit_delay = CONFIG_RCU_TORTURE_TEST_SLOW_PREINIT_DELAY;
176 module_param(gp_preinit_delay, int, 0644);
177 #else /* #ifdef CONFIG_RCU_TORTURE_TEST_SLOW_PREINIT */
178 static const int gp_preinit_delay;
179 #endif /* #else #ifdef CONFIG_RCU_TORTURE_TEST_SLOW_PREINIT */
180 
181 #ifdef CONFIG_RCU_TORTURE_TEST_SLOW_INIT
182 static int gp_init_delay = CONFIG_RCU_TORTURE_TEST_SLOW_INIT_DELAY;
183 module_param(gp_init_delay, int, 0644);
184 #else /* #ifdef CONFIG_RCU_TORTURE_TEST_SLOW_INIT */
185 static const int gp_init_delay;
186 #endif /* #else #ifdef CONFIG_RCU_TORTURE_TEST_SLOW_INIT */
187 
188 #ifdef CONFIG_RCU_TORTURE_TEST_SLOW_CLEANUP
189 static int gp_cleanup_delay = CONFIG_RCU_TORTURE_TEST_SLOW_CLEANUP_DELAY;
190 module_param(gp_cleanup_delay, int, 0644);
191 #else /* #ifdef CONFIG_RCU_TORTURE_TEST_SLOW_CLEANUP */
192 static const int gp_cleanup_delay;
193 #endif /* #else #ifdef CONFIG_RCU_TORTURE_TEST_SLOW_CLEANUP */
194 
195 /*
196  * Number of grace periods between delays, normalized by the duration of
197  * the delay.  The longer the the delay, the more the grace periods between
198  * each delay.  The reason for this normalization is that it means that,
199  * for non-zero delays, the overall slowdown of grace periods is constant
200  * regardless of the duration of the delay.  This arrangement balances
201  * the need for long delays to increase some race probabilities with the
202  * need for fast grace periods to increase other race probabilities.
203  */
204 #define PER_RCU_NODE_PERIOD 3	/* Number of grace periods between delays. */
205 
206 /*
207  * Track the rcutorture test sequence number and the update version
208  * number within a given test.  The rcutorture_testseq is incremented
209  * on every rcutorture module load and unload, so has an odd value
210  * when a test is running.  The rcutorture_vernum is set to zero
211  * when rcutorture starts and is incremented on each rcutorture update.
212  * These variables enable correlating rcutorture output with the
213  * RCU tracing information.
214  */
215 unsigned long rcutorture_testseq;
216 unsigned long rcutorture_vernum;
217 
218 /*
219  * Compute the mask of online CPUs for the specified rcu_node structure.
220  * This will not be stable unless the rcu_node structure's ->lock is
221  * held, but the bit corresponding to the current CPU will be stable
222  * in most contexts.
223  */
224 unsigned long rcu_rnp_online_cpus(struct rcu_node *rnp)
225 {
226 	return READ_ONCE(rnp->qsmaskinitnext);
227 }
228 
229 /*
230  * Return true if an RCU grace period is in progress.  The READ_ONCE()s
231  * permit this function to be invoked without holding the root rcu_node
232  * structure's ->lock, but of course results can be subject to change.
233  */
234 static int rcu_gp_in_progress(struct rcu_state *rsp)
235 {
236 	return READ_ONCE(rsp->completed) != READ_ONCE(rsp->gpnum);
237 }
238 
239 /*
240  * Note a quiescent state.  Because we do not need to know
241  * how many quiescent states passed, just if there was at least
242  * one since the start of the grace period, this just sets a flag.
243  * The caller must have disabled preemption.
244  */
245 void rcu_sched_qs(void)
246 {
247 	if (!__this_cpu_read(rcu_sched_data.cpu_no_qs.s))
248 		return;
249 	trace_rcu_grace_period(TPS("rcu_sched"),
250 			       __this_cpu_read(rcu_sched_data.gpnum),
251 			       TPS("cpuqs"));
252 	__this_cpu_write(rcu_sched_data.cpu_no_qs.b.norm, false);
253 	if (!__this_cpu_read(rcu_sched_data.cpu_no_qs.b.exp))
254 		return;
255 	__this_cpu_write(rcu_sched_data.cpu_no_qs.b.exp, false);
256 	rcu_report_exp_rdp(&rcu_sched_state,
257 			   this_cpu_ptr(&rcu_sched_data), true);
258 }
259 
260 void rcu_bh_qs(void)
261 {
262 	if (__this_cpu_read(rcu_bh_data.cpu_no_qs.s)) {
263 		trace_rcu_grace_period(TPS("rcu_bh"),
264 				       __this_cpu_read(rcu_bh_data.gpnum),
265 				       TPS("cpuqs"));
266 		__this_cpu_write(rcu_bh_data.cpu_no_qs.b.norm, false);
267 	}
268 }
269 
270 static DEFINE_PER_CPU(int, rcu_sched_qs_mask);
271 
272 static DEFINE_PER_CPU(struct rcu_dynticks, rcu_dynticks) = {
273 	.dynticks_nesting = DYNTICK_TASK_EXIT_IDLE,
274 	.dynticks = ATOMIC_INIT(1),
275 #ifdef CONFIG_NO_HZ_FULL_SYSIDLE
276 	.dynticks_idle_nesting = DYNTICK_TASK_NEST_VALUE,
277 	.dynticks_idle = ATOMIC_INIT(1),
278 #endif /* #ifdef CONFIG_NO_HZ_FULL_SYSIDLE */
279 };
280 
281 DEFINE_PER_CPU_SHARED_ALIGNED(unsigned long, rcu_qs_ctr);
282 EXPORT_PER_CPU_SYMBOL_GPL(rcu_qs_ctr);
283 
284 /*
285  * Let the RCU core know that this CPU has gone through the scheduler,
286  * which is a quiescent state.  This is called when the need for a
287  * quiescent state is urgent, so we burn an atomic operation and full
288  * memory barriers to let the RCU core know about it, regardless of what
289  * this CPU might (or might not) do in the near future.
290  *
291  * We inform the RCU core by emulating a zero-duration dyntick-idle
292  * period, which we in turn do by incrementing the ->dynticks counter
293  * by two.
294  *
295  * The caller must have disabled interrupts.
296  */
297 static void rcu_momentary_dyntick_idle(void)
298 {
299 	struct rcu_data *rdp;
300 	struct rcu_dynticks *rdtp;
301 	int resched_mask;
302 	struct rcu_state *rsp;
303 
304 	/*
305 	 * Yes, we can lose flag-setting operations.  This is OK, because
306 	 * the flag will be set again after some delay.
307 	 */
308 	resched_mask = raw_cpu_read(rcu_sched_qs_mask);
309 	raw_cpu_write(rcu_sched_qs_mask, 0);
310 
311 	/* Find the flavor that needs a quiescent state. */
312 	for_each_rcu_flavor(rsp) {
313 		rdp = raw_cpu_ptr(rsp->rda);
314 		if (!(resched_mask & rsp->flavor_mask))
315 			continue;
316 		smp_mb(); /* rcu_sched_qs_mask before cond_resched_completed. */
317 		if (READ_ONCE(rdp->mynode->completed) !=
318 		    READ_ONCE(rdp->cond_resched_completed))
319 			continue;
320 
321 		/*
322 		 * Pretend to be momentarily idle for the quiescent state.
323 		 * This allows the grace-period kthread to record the
324 		 * quiescent state, with no need for this CPU to do anything
325 		 * further.
326 		 */
327 		rdtp = this_cpu_ptr(&rcu_dynticks);
328 		smp_mb__before_atomic(); /* Earlier stuff before QS. */
329 		atomic_add(2, &rdtp->dynticks);  /* QS. */
330 		smp_mb__after_atomic(); /* Later stuff after QS. */
331 		break;
332 	}
333 }
334 
335 /*
336  * Note a context switch.  This is a quiescent state for RCU-sched,
337  * and requires special handling for preemptible RCU.
338  * The caller must have disabled interrupts.
339  */
340 void rcu_note_context_switch(void)
341 {
342 	barrier(); /* Avoid RCU read-side critical sections leaking down. */
343 	trace_rcu_utilization(TPS("Start context switch"));
344 	rcu_sched_qs();
345 	rcu_preempt_note_context_switch();
346 	if (unlikely(raw_cpu_read(rcu_sched_qs_mask)))
347 		rcu_momentary_dyntick_idle();
348 	trace_rcu_utilization(TPS("End context switch"));
349 	barrier(); /* Avoid RCU read-side critical sections leaking up. */
350 }
351 EXPORT_SYMBOL_GPL(rcu_note_context_switch);
352 
353 /*
354  * Register a quiescent state for all RCU flavors.  If there is an
355  * emergency, invoke rcu_momentary_dyntick_idle() to do a heavy-weight
356  * dyntick-idle quiescent state visible to other CPUs (but only for those
357  * RCU flavors in desperate need of a quiescent state, which will normally
358  * be none of them).  Either way, do a lightweight quiescent state for
359  * all RCU flavors.
360  *
361  * The barrier() calls are redundant in the common case when this is
362  * called externally, but just in case this is called from within this
363  * file.
364  *
365  */
366 void rcu_all_qs(void)
367 {
368 	unsigned long flags;
369 
370 	barrier(); /* Avoid RCU read-side critical sections leaking down. */
371 	if (unlikely(raw_cpu_read(rcu_sched_qs_mask))) {
372 		local_irq_save(flags);
373 		rcu_momentary_dyntick_idle();
374 		local_irq_restore(flags);
375 	}
376 	if (unlikely(raw_cpu_read(rcu_sched_data.cpu_no_qs.b.exp))) {
377 		/*
378 		 * Yes, we just checked a per-CPU variable with preemption
379 		 * enabled, so we might be migrated to some other CPU at
380 		 * this point.  That is OK because in that case, the
381 		 * migration will supply the needed quiescent state.
382 		 * We might end up needlessly disabling preemption and
383 		 * invoking rcu_sched_qs() on the destination CPU, but
384 		 * the probability and cost are both quite low, so this
385 		 * should not be a problem in practice.
386 		 */
387 		preempt_disable();
388 		rcu_sched_qs();
389 		preempt_enable();
390 	}
391 	this_cpu_inc(rcu_qs_ctr);
392 	barrier(); /* Avoid RCU read-side critical sections leaking up. */
393 }
394 EXPORT_SYMBOL_GPL(rcu_all_qs);
395 
396 static long blimit = 10;	/* Maximum callbacks per rcu_do_batch. */
397 static long qhimark = 10000;	/* If this many pending, ignore blimit. */
398 static long qlowmark = 100;	/* Once only this many pending, use blimit. */
399 
400 module_param(blimit, long, 0444);
401 module_param(qhimark, long, 0444);
402 module_param(qlowmark, long, 0444);
403 
404 static ulong jiffies_till_first_fqs = ULONG_MAX;
405 static ulong jiffies_till_next_fqs = ULONG_MAX;
406 static bool rcu_kick_kthreads;
407 
408 module_param(jiffies_till_first_fqs, ulong, 0644);
409 module_param(jiffies_till_next_fqs, ulong, 0644);
410 module_param(rcu_kick_kthreads, bool, 0644);
411 
412 /*
413  * How long the grace period must be before we start recruiting
414  * quiescent-state help from rcu_note_context_switch().
415  */
416 static ulong jiffies_till_sched_qs = HZ / 20;
417 module_param(jiffies_till_sched_qs, ulong, 0644);
418 
419 static bool rcu_start_gp_advanced(struct rcu_state *rsp, struct rcu_node *rnp,
420 				  struct rcu_data *rdp);
421 static void force_qs_rnp(struct rcu_state *rsp,
422 			 int (*f)(struct rcu_data *rsp, bool *isidle,
423 				  unsigned long *maxj),
424 			 bool *isidle, unsigned long *maxj);
425 static void force_quiescent_state(struct rcu_state *rsp);
426 static int rcu_pending(void);
427 
428 /*
429  * Return the number of RCU batches started thus far for debug & stats.
430  */
431 unsigned long rcu_batches_started(void)
432 {
433 	return rcu_state_p->gpnum;
434 }
435 EXPORT_SYMBOL_GPL(rcu_batches_started);
436 
437 /*
438  * Return the number of RCU-sched batches started thus far for debug & stats.
439  */
440 unsigned long rcu_batches_started_sched(void)
441 {
442 	return rcu_sched_state.gpnum;
443 }
444 EXPORT_SYMBOL_GPL(rcu_batches_started_sched);
445 
446 /*
447  * Return the number of RCU BH batches started thus far for debug & stats.
448  */
449 unsigned long rcu_batches_started_bh(void)
450 {
451 	return rcu_bh_state.gpnum;
452 }
453 EXPORT_SYMBOL_GPL(rcu_batches_started_bh);
454 
455 /*
456  * Return the number of RCU batches completed thus far for debug & stats.
457  */
458 unsigned long rcu_batches_completed(void)
459 {
460 	return rcu_state_p->completed;
461 }
462 EXPORT_SYMBOL_GPL(rcu_batches_completed);
463 
464 /*
465  * Return the number of RCU-sched batches completed thus far for debug & stats.
466  */
467 unsigned long rcu_batches_completed_sched(void)
468 {
469 	return rcu_sched_state.completed;
470 }
471 EXPORT_SYMBOL_GPL(rcu_batches_completed_sched);
472 
473 /*
474  * Return the number of RCU BH batches completed thus far for debug & stats.
475  */
476 unsigned long rcu_batches_completed_bh(void)
477 {
478 	return rcu_bh_state.completed;
479 }
480 EXPORT_SYMBOL_GPL(rcu_batches_completed_bh);
481 
482 /*
483  * Return the number of RCU expedited batches completed thus far for
484  * debug & stats.  Odd numbers mean that a batch is in progress, even
485  * numbers mean idle.  The value returned will thus be roughly double
486  * the cumulative batches since boot.
487  */
488 unsigned long rcu_exp_batches_completed(void)
489 {
490 	return rcu_state_p->expedited_sequence;
491 }
492 EXPORT_SYMBOL_GPL(rcu_exp_batches_completed);
493 
494 /*
495  * Return the number of RCU-sched expedited batches completed thus far
496  * for debug & stats.  Similar to rcu_exp_batches_completed().
497  */
498 unsigned long rcu_exp_batches_completed_sched(void)
499 {
500 	return rcu_sched_state.expedited_sequence;
501 }
502 EXPORT_SYMBOL_GPL(rcu_exp_batches_completed_sched);
503 
504 /*
505  * Force a quiescent state.
506  */
507 void rcu_force_quiescent_state(void)
508 {
509 	force_quiescent_state(rcu_state_p);
510 }
511 EXPORT_SYMBOL_GPL(rcu_force_quiescent_state);
512 
513 /*
514  * Force a quiescent state for RCU BH.
515  */
516 void rcu_bh_force_quiescent_state(void)
517 {
518 	force_quiescent_state(&rcu_bh_state);
519 }
520 EXPORT_SYMBOL_GPL(rcu_bh_force_quiescent_state);
521 
522 /*
523  * Force a quiescent state for RCU-sched.
524  */
525 void rcu_sched_force_quiescent_state(void)
526 {
527 	force_quiescent_state(&rcu_sched_state);
528 }
529 EXPORT_SYMBOL_GPL(rcu_sched_force_quiescent_state);
530 
531 /*
532  * Show the state of the grace-period kthreads.
533  */
534 void show_rcu_gp_kthreads(void)
535 {
536 	struct rcu_state *rsp;
537 
538 	for_each_rcu_flavor(rsp) {
539 		pr_info("%s: wait state: %d ->state: %#lx\n",
540 			rsp->name, rsp->gp_state, rsp->gp_kthread->state);
541 		/* sched_show_task(rsp->gp_kthread); */
542 	}
543 }
544 EXPORT_SYMBOL_GPL(show_rcu_gp_kthreads);
545 
546 /*
547  * Record the number of times rcutorture tests have been initiated and
548  * terminated.  This information allows the debugfs tracing stats to be
549  * correlated to the rcutorture messages, even when the rcutorture module
550  * is being repeatedly loaded and unloaded.  In other words, we cannot
551  * store this state in rcutorture itself.
552  */
553 void rcutorture_record_test_transition(void)
554 {
555 	rcutorture_testseq++;
556 	rcutorture_vernum = 0;
557 }
558 EXPORT_SYMBOL_GPL(rcutorture_record_test_transition);
559 
560 /*
561  * Send along grace-period-related data for rcutorture diagnostics.
562  */
563 void rcutorture_get_gp_data(enum rcutorture_type test_type, int *flags,
564 			    unsigned long *gpnum, unsigned long *completed)
565 {
566 	struct rcu_state *rsp = NULL;
567 
568 	switch (test_type) {
569 	case RCU_FLAVOR:
570 		rsp = rcu_state_p;
571 		break;
572 	case RCU_BH_FLAVOR:
573 		rsp = &rcu_bh_state;
574 		break;
575 	case RCU_SCHED_FLAVOR:
576 		rsp = &rcu_sched_state;
577 		break;
578 	default:
579 		break;
580 	}
581 	if (rsp != NULL) {
582 		*flags = READ_ONCE(rsp->gp_flags);
583 		*gpnum = READ_ONCE(rsp->gpnum);
584 		*completed = READ_ONCE(rsp->completed);
585 		return;
586 	}
587 	*flags = 0;
588 	*gpnum = 0;
589 	*completed = 0;
590 }
591 EXPORT_SYMBOL_GPL(rcutorture_get_gp_data);
592 
593 /*
594  * Record the number of writer passes through the current rcutorture test.
595  * This is also used to correlate debugfs tracing stats with the rcutorture
596  * messages.
597  */
598 void rcutorture_record_progress(unsigned long vernum)
599 {
600 	rcutorture_vernum++;
601 }
602 EXPORT_SYMBOL_GPL(rcutorture_record_progress);
603 
604 /*
605  * Does the CPU have callbacks ready to be invoked?
606  */
607 static int
608 cpu_has_callbacks_ready_to_invoke(struct rcu_data *rdp)
609 {
610 	return &rdp->nxtlist != rdp->nxttail[RCU_DONE_TAIL] &&
611 	       rdp->nxttail[RCU_DONE_TAIL] != NULL;
612 }
613 
614 /*
615  * Return the root node of the specified rcu_state structure.
616  */
617 static struct rcu_node *rcu_get_root(struct rcu_state *rsp)
618 {
619 	return &rsp->node[0];
620 }
621 
622 /*
623  * Is there any need for future grace periods?
624  * Interrupts must be disabled.  If the caller does not hold the root
625  * rnp_node structure's ->lock, the results are advisory only.
626  */
627 static int rcu_future_needs_gp(struct rcu_state *rsp)
628 {
629 	struct rcu_node *rnp = rcu_get_root(rsp);
630 	int idx = (READ_ONCE(rnp->completed) + 1) & 0x1;
631 	int *fp = &rnp->need_future_gp[idx];
632 
633 	return READ_ONCE(*fp);
634 }
635 
636 /*
637  * Does the current CPU require a not-yet-started grace period?
638  * The caller must have disabled interrupts to prevent races with
639  * normal callback registry.
640  */
641 static bool
642 cpu_needs_another_gp(struct rcu_state *rsp, struct rcu_data *rdp)
643 {
644 	int i;
645 
646 	if (rcu_gp_in_progress(rsp))
647 		return false;  /* No, a grace period is already in progress. */
648 	if (rcu_future_needs_gp(rsp))
649 		return true;  /* Yes, a no-CBs CPU needs one. */
650 	if (!rdp->nxttail[RCU_NEXT_TAIL])
651 		return false;  /* No, this is a no-CBs (or offline) CPU. */
652 	if (*rdp->nxttail[RCU_NEXT_READY_TAIL])
653 		return true;  /* Yes, CPU has newly registered callbacks. */
654 	for (i = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++)
655 		if (rdp->nxttail[i - 1] != rdp->nxttail[i] &&
656 		    ULONG_CMP_LT(READ_ONCE(rsp->completed),
657 				 rdp->nxtcompleted[i]))
658 			return true;  /* Yes, CBs for future grace period. */
659 	return false; /* No grace period needed. */
660 }
661 
662 /*
663  * rcu_eqs_enter_common - current CPU is moving towards extended quiescent state
664  *
665  * If the new value of the ->dynticks_nesting counter now is zero,
666  * we really have entered idle, and must do the appropriate accounting.
667  * The caller must have disabled interrupts.
668  */
669 static void rcu_eqs_enter_common(long long oldval, bool user)
670 {
671 	struct rcu_state *rsp;
672 	struct rcu_data *rdp;
673 	struct rcu_dynticks *rdtp = this_cpu_ptr(&rcu_dynticks);
674 
675 	trace_rcu_dyntick(TPS("Start"), oldval, rdtp->dynticks_nesting);
676 	if (IS_ENABLED(CONFIG_RCU_EQS_DEBUG) &&
677 	    !user && !is_idle_task(current)) {
678 		struct task_struct *idle __maybe_unused =
679 			idle_task(smp_processor_id());
680 
681 		trace_rcu_dyntick(TPS("Error on entry: not idle task"), oldval, 0);
682 		rcu_ftrace_dump(DUMP_ORIG);
683 		WARN_ONCE(1, "Current pid: %d comm: %s / Idle pid: %d comm: %s",
684 			  current->pid, current->comm,
685 			  idle->pid, idle->comm); /* must be idle task! */
686 	}
687 	for_each_rcu_flavor(rsp) {
688 		rdp = this_cpu_ptr(rsp->rda);
689 		do_nocb_deferred_wakeup(rdp);
690 	}
691 	rcu_prepare_for_idle();
692 	/* CPUs seeing atomic_inc() must see prior RCU read-side crit sects */
693 	smp_mb__before_atomic();  /* See above. */
694 	atomic_inc(&rdtp->dynticks);
695 	smp_mb__after_atomic();  /* Force ordering with next sojourn. */
696 	WARN_ON_ONCE(IS_ENABLED(CONFIG_RCU_EQS_DEBUG) &&
697 		     atomic_read(&rdtp->dynticks) & 0x1);
698 	rcu_dynticks_task_enter();
699 
700 	/*
701 	 * It is illegal to enter an extended quiescent state while
702 	 * in an RCU read-side critical section.
703 	 */
704 	RCU_LOCKDEP_WARN(lock_is_held(&rcu_lock_map),
705 			 "Illegal idle entry in RCU read-side critical section.");
706 	RCU_LOCKDEP_WARN(lock_is_held(&rcu_bh_lock_map),
707 			 "Illegal idle entry in RCU-bh read-side critical section.");
708 	RCU_LOCKDEP_WARN(lock_is_held(&rcu_sched_lock_map),
709 			 "Illegal idle entry in RCU-sched read-side critical section.");
710 }
711 
712 /*
713  * Enter an RCU extended quiescent state, which can be either the
714  * idle loop or adaptive-tickless usermode execution.
715  */
716 static void rcu_eqs_enter(bool user)
717 {
718 	long long oldval;
719 	struct rcu_dynticks *rdtp;
720 
721 	rdtp = this_cpu_ptr(&rcu_dynticks);
722 	oldval = rdtp->dynticks_nesting;
723 	WARN_ON_ONCE(IS_ENABLED(CONFIG_RCU_EQS_DEBUG) &&
724 		     (oldval & DYNTICK_TASK_NEST_MASK) == 0);
725 	if ((oldval & DYNTICK_TASK_NEST_MASK) == DYNTICK_TASK_NEST_VALUE) {
726 		rdtp->dynticks_nesting = 0;
727 		rcu_eqs_enter_common(oldval, user);
728 	} else {
729 		rdtp->dynticks_nesting -= DYNTICK_TASK_NEST_VALUE;
730 	}
731 }
732 
733 /**
734  * rcu_idle_enter - inform RCU that current CPU is entering idle
735  *
736  * Enter idle mode, in other words, -leave- the mode in which RCU
737  * read-side critical sections can occur.  (Though RCU read-side
738  * critical sections can occur in irq handlers in idle, a possibility
739  * handled by irq_enter() and irq_exit().)
740  *
741  * We crowbar the ->dynticks_nesting field to zero to allow for
742  * the possibility of usermode upcalls having messed up our count
743  * of interrupt nesting level during the prior busy period.
744  */
745 void rcu_idle_enter(void)
746 {
747 	unsigned long flags;
748 
749 	local_irq_save(flags);
750 	rcu_eqs_enter(false);
751 	rcu_sysidle_enter(0);
752 	local_irq_restore(flags);
753 }
754 EXPORT_SYMBOL_GPL(rcu_idle_enter);
755 
756 #ifdef CONFIG_NO_HZ_FULL
757 /**
758  * rcu_user_enter - inform RCU that we are resuming userspace.
759  *
760  * Enter RCU idle mode right before resuming userspace.  No use of RCU
761  * is permitted between this call and rcu_user_exit(). This way the
762  * CPU doesn't need to maintain the tick for RCU maintenance purposes
763  * when the CPU runs in userspace.
764  */
765 void rcu_user_enter(void)
766 {
767 	rcu_eqs_enter(1);
768 }
769 #endif /* CONFIG_NO_HZ_FULL */
770 
771 /**
772  * rcu_irq_exit - inform RCU that current CPU is exiting irq towards idle
773  *
774  * Exit from an interrupt handler, which might possibly result in entering
775  * idle mode, in other words, leaving the mode in which read-side critical
776  * sections can occur.  The caller must have disabled interrupts.
777  *
778  * This code assumes that the idle loop never does anything that might
779  * result in unbalanced calls to irq_enter() and irq_exit().  If your
780  * architecture violates this assumption, RCU will give you what you
781  * deserve, good and hard.  But very infrequently and irreproducibly.
782  *
783  * Use things like work queues to work around this limitation.
784  *
785  * You have been warned.
786  */
787 void rcu_irq_exit(void)
788 {
789 	long long oldval;
790 	struct rcu_dynticks *rdtp;
791 
792 	RCU_LOCKDEP_WARN(!irqs_disabled(), "rcu_irq_exit() invoked with irqs enabled!!!");
793 	rdtp = this_cpu_ptr(&rcu_dynticks);
794 	oldval = rdtp->dynticks_nesting;
795 	rdtp->dynticks_nesting--;
796 	WARN_ON_ONCE(IS_ENABLED(CONFIG_RCU_EQS_DEBUG) &&
797 		     rdtp->dynticks_nesting < 0);
798 	if (rdtp->dynticks_nesting)
799 		trace_rcu_dyntick(TPS("--="), oldval, rdtp->dynticks_nesting);
800 	else
801 		rcu_eqs_enter_common(oldval, true);
802 	rcu_sysidle_enter(1);
803 }
804 
805 /*
806  * Wrapper for rcu_irq_exit() where interrupts are enabled.
807  */
808 void rcu_irq_exit_irqson(void)
809 {
810 	unsigned long flags;
811 
812 	local_irq_save(flags);
813 	rcu_irq_exit();
814 	local_irq_restore(flags);
815 }
816 
817 /*
818  * rcu_eqs_exit_common - current CPU moving away from extended quiescent state
819  *
820  * If the new value of the ->dynticks_nesting counter was previously zero,
821  * we really have exited idle, and must do the appropriate accounting.
822  * The caller must have disabled interrupts.
823  */
824 static void rcu_eqs_exit_common(long long oldval, int user)
825 {
826 	struct rcu_dynticks *rdtp = this_cpu_ptr(&rcu_dynticks);
827 
828 	rcu_dynticks_task_exit();
829 	smp_mb__before_atomic();  /* Force ordering w/previous sojourn. */
830 	atomic_inc(&rdtp->dynticks);
831 	/* CPUs seeing atomic_inc() must see later RCU read-side crit sects */
832 	smp_mb__after_atomic();  /* See above. */
833 	WARN_ON_ONCE(IS_ENABLED(CONFIG_RCU_EQS_DEBUG) &&
834 		     !(atomic_read(&rdtp->dynticks) & 0x1));
835 	rcu_cleanup_after_idle();
836 	trace_rcu_dyntick(TPS("End"), oldval, rdtp->dynticks_nesting);
837 	if (IS_ENABLED(CONFIG_RCU_EQS_DEBUG) &&
838 	    !user && !is_idle_task(current)) {
839 		struct task_struct *idle __maybe_unused =
840 			idle_task(smp_processor_id());
841 
842 		trace_rcu_dyntick(TPS("Error on exit: not idle task"),
843 				  oldval, rdtp->dynticks_nesting);
844 		rcu_ftrace_dump(DUMP_ORIG);
845 		WARN_ONCE(1, "Current pid: %d comm: %s / Idle pid: %d comm: %s",
846 			  current->pid, current->comm,
847 			  idle->pid, idle->comm); /* must be idle task! */
848 	}
849 }
850 
851 /*
852  * Exit an RCU extended quiescent state, which can be either the
853  * idle loop or adaptive-tickless usermode execution.
854  */
855 static void rcu_eqs_exit(bool user)
856 {
857 	struct rcu_dynticks *rdtp;
858 	long long oldval;
859 
860 	rdtp = this_cpu_ptr(&rcu_dynticks);
861 	oldval = rdtp->dynticks_nesting;
862 	WARN_ON_ONCE(IS_ENABLED(CONFIG_RCU_EQS_DEBUG) && oldval < 0);
863 	if (oldval & DYNTICK_TASK_NEST_MASK) {
864 		rdtp->dynticks_nesting += DYNTICK_TASK_NEST_VALUE;
865 	} else {
866 		rdtp->dynticks_nesting = DYNTICK_TASK_EXIT_IDLE;
867 		rcu_eqs_exit_common(oldval, user);
868 	}
869 }
870 
871 /**
872  * rcu_idle_exit - inform RCU that current CPU is leaving idle
873  *
874  * Exit idle mode, in other words, -enter- the mode in which RCU
875  * read-side critical sections can occur.
876  *
877  * We crowbar the ->dynticks_nesting field to DYNTICK_TASK_NEST to
878  * allow for the possibility of usermode upcalls messing up our count
879  * of interrupt nesting level during the busy period that is just
880  * now starting.
881  */
882 void rcu_idle_exit(void)
883 {
884 	unsigned long flags;
885 
886 	local_irq_save(flags);
887 	rcu_eqs_exit(false);
888 	rcu_sysidle_exit(0);
889 	local_irq_restore(flags);
890 }
891 EXPORT_SYMBOL_GPL(rcu_idle_exit);
892 
893 #ifdef CONFIG_NO_HZ_FULL
894 /**
895  * rcu_user_exit - inform RCU that we are exiting userspace.
896  *
897  * Exit RCU idle mode while entering the kernel because it can
898  * run a RCU read side critical section anytime.
899  */
900 void rcu_user_exit(void)
901 {
902 	rcu_eqs_exit(1);
903 }
904 #endif /* CONFIG_NO_HZ_FULL */
905 
906 /**
907  * rcu_irq_enter - inform RCU that current CPU is entering irq away from idle
908  *
909  * Enter an interrupt handler, which might possibly result in exiting
910  * idle mode, in other words, entering the mode in which read-side critical
911  * sections can occur.  The caller must have disabled interrupts.
912  *
913  * Note that the Linux kernel is fully capable of entering an interrupt
914  * handler that it never exits, for example when doing upcalls to
915  * user mode!  This code assumes that the idle loop never does upcalls to
916  * user mode.  If your architecture does do upcalls from the idle loop (or
917  * does anything else that results in unbalanced calls to the irq_enter()
918  * and irq_exit() functions), RCU will give you what you deserve, good
919  * and hard.  But very infrequently and irreproducibly.
920  *
921  * Use things like work queues to work around this limitation.
922  *
923  * You have been warned.
924  */
925 void rcu_irq_enter(void)
926 {
927 	struct rcu_dynticks *rdtp;
928 	long long oldval;
929 
930 	RCU_LOCKDEP_WARN(!irqs_disabled(), "rcu_irq_enter() invoked with irqs enabled!!!");
931 	rdtp = this_cpu_ptr(&rcu_dynticks);
932 	oldval = rdtp->dynticks_nesting;
933 	rdtp->dynticks_nesting++;
934 	WARN_ON_ONCE(IS_ENABLED(CONFIG_RCU_EQS_DEBUG) &&
935 		     rdtp->dynticks_nesting == 0);
936 	if (oldval)
937 		trace_rcu_dyntick(TPS("++="), oldval, rdtp->dynticks_nesting);
938 	else
939 		rcu_eqs_exit_common(oldval, true);
940 	rcu_sysidle_exit(1);
941 }
942 
943 /*
944  * Wrapper for rcu_irq_enter() where interrupts are enabled.
945  */
946 void rcu_irq_enter_irqson(void)
947 {
948 	unsigned long flags;
949 
950 	local_irq_save(flags);
951 	rcu_irq_enter();
952 	local_irq_restore(flags);
953 }
954 
955 /**
956  * rcu_nmi_enter - inform RCU of entry to NMI context
957  *
958  * If the CPU was idle from RCU's viewpoint, update rdtp->dynticks and
959  * rdtp->dynticks_nmi_nesting to let the RCU grace-period handling know
960  * that the CPU is active.  This implementation permits nested NMIs, as
961  * long as the nesting level does not overflow an int.  (You will probably
962  * run out of stack space first.)
963  */
964 void rcu_nmi_enter(void)
965 {
966 	struct rcu_dynticks *rdtp = this_cpu_ptr(&rcu_dynticks);
967 	int incby = 2;
968 
969 	/* Complain about underflow. */
970 	WARN_ON_ONCE(rdtp->dynticks_nmi_nesting < 0);
971 
972 	/*
973 	 * If idle from RCU viewpoint, atomically increment ->dynticks
974 	 * to mark non-idle and increment ->dynticks_nmi_nesting by one.
975 	 * Otherwise, increment ->dynticks_nmi_nesting by two.  This means
976 	 * if ->dynticks_nmi_nesting is equal to one, we are guaranteed
977 	 * to be in the outermost NMI handler that interrupted an RCU-idle
978 	 * period (observation due to Andy Lutomirski).
979 	 */
980 	if (!(atomic_read(&rdtp->dynticks) & 0x1)) {
981 		smp_mb__before_atomic();  /* Force delay from prior write. */
982 		atomic_inc(&rdtp->dynticks);
983 		/* atomic_inc() before later RCU read-side crit sects */
984 		smp_mb__after_atomic();  /* See above. */
985 		WARN_ON_ONCE(!(atomic_read(&rdtp->dynticks) & 0x1));
986 		incby = 1;
987 	}
988 	rdtp->dynticks_nmi_nesting += incby;
989 	barrier();
990 }
991 
992 /**
993  * rcu_nmi_exit - inform RCU of exit from NMI context
994  *
995  * If we are returning from the outermost NMI handler that interrupted an
996  * RCU-idle period, update rdtp->dynticks and rdtp->dynticks_nmi_nesting
997  * to let the RCU grace-period handling know that the CPU is back to
998  * being RCU-idle.
999  */
1000 void rcu_nmi_exit(void)
1001 {
1002 	struct rcu_dynticks *rdtp = this_cpu_ptr(&rcu_dynticks);
1003 
1004 	/*
1005 	 * Check for ->dynticks_nmi_nesting underflow and bad ->dynticks.
1006 	 * (We are exiting an NMI handler, so RCU better be paying attention
1007 	 * to us!)
1008 	 */
1009 	WARN_ON_ONCE(rdtp->dynticks_nmi_nesting <= 0);
1010 	WARN_ON_ONCE(!(atomic_read(&rdtp->dynticks) & 0x1));
1011 
1012 	/*
1013 	 * If the nesting level is not 1, the CPU wasn't RCU-idle, so
1014 	 * leave it in non-RCU-idle state.
1015 	 */
1016 	if (rdtp->dynticks_nmi_nesting != 1) {
1017 		rdtp->dynticks_nmi_nesting -= 2;
1018 		return;
1019 	}
1020 
1021 	/* This NMI interrupted an RCU-idle CPU, restore RCU-idleness. */
1022 	rdtp->dynticks_nmi_nesting = 0;
1023 	/* CPUs seeing atomic_inc() must see prior RCU read-side crit sects */
1024 	smp_mb__before_atomic();  /* See above. */
1025 	atomic_inc(&rdtp->dynticks);
1026 	smp_mb__after_atomic();  /* Force delay to next write. */
1027 	WARN_ON_ONCE(atomic_read(&rdtp->dynticks) & 0x1);
1028 }
1029 
1030 /**
1031  * __rcu_is_watching - are RCU read-side critical sections safe?
1032  *
1033  * Return true if RCU is watching the running CPU, which means that
1034  * this CPU can safely enter RCU read-side critical sections.  Unlike
1035  * rcu_is_watching(), the caller of __rcu_is_watching() must have at
1036  * least disabled preemption.
1037  */
1038 bool notrace __rcu_is_watching(void)
1039 {
1040 	return atomic_read(this_cpu_ptr(&rcu_dynticks.dynticks)) & 0x1;
1041 }
1042 
1043 /**
1044  * rcu_is_watching - see if RCU thinks that the current CPU is idle
1045  *
1046  * If the current CPU is in its idle loop and is neither in an interrupt
1047  * or NMI handler, return true.
1048  */
1049 bool notrace rcu_is_watching(void)
1050 {
1051 	bool ret;
1052 
1053 	preempt_disable_notrace();
1054 	ret = __rcu_is_watching();
1055 	preempt_enable_notrace();
1056 	return ret;
1057 }
1058 EXPORT_SYMBOL_GPL(rcu_is_watching);
1059 
1060 #if defined(CONFIG_PROVE_RCU) && defined(CONFIG_HOTPLUG_CPU)
1061 
1062 /*
1063  * Is the current CPU online?  Disable preemption to avoid false positives
1064  * that could otherwise happen due to the current CPU number being sampled,
1065  * this task being preempted, its old CPU being taken offline, resuming
1066  * on some other CPU, then determining that its old CPU is now offline.
1067  * It is OK to use RCU on an offline processor during initial boot, hence
1068  * the check for rcu_scheduler_fully_active.  Note also that it is OK
1069  * for a CPU coming online to use RCU for one jiffy prior to marking itself
1070  * online in the cpu_online_mask.  Similarly, it is OK for a CPU going
1071  * offline to continue to use RCU for one jiffy after marking itself
1072  * offline in the cpu_online_mask.  This leniency is necessary given the
1073  * non-atomic nature of the online and offline processing, for example,
1074  * the fact that a CPU enters the scheduler after completing the teardown
1075  * of the CPU.
1076  *
1077  * This is also why RCU internally marks CPUs online during in the
1078  * preparation phase and offline after the CPU has been taken down.
1079  *
1080  * Disable checking if in an NMI handler because we cannot safely report
1081  * errors from NMI handlers anyway.
1082  */
1083 bool rcu_lockdep_current_cpu_online(void)
1084 {
1085 	struct rcu_data *rdp;
1086 	struct rcu_node *rnp;
1087 	bool ret;
1088 
1089 	if (in_nmi())
1090 		return true;
1091 	preempt_disable();
1092 	rdp = this_cpu_ptr(&rcu_sched_data);
1093 	rnp = rdp->mynode;
1094 	ret = (rdp->grpmask & rcu_rnp_online_cpus(rnp)) ||
1095 	      !rcu_scheduler_fully_active;
1096 	preempt_enable();
1097 	return ret;
1098 }
1099 EXPORT_SYMBOL_GPL(rcu_lockdep_current_cpu_online);
1100 
1101 #endif /* #if defined(CONFIG_PROVE_RCU) && defined(CONFIG_HOTPLUG_CPU) */
1102 
1103 /**
1104  * rcu_is_cpu_rrupt_from_idle - see if idle or immediately interrupted from idle
1105  *
1106  * If the current CPU is idle or running at a first-level (not nested)
1107  * interrupt from idle, return true.  The caller must have at least
1108  * disabled preemption.
1109  */
1110 static int rcu_is_cpu_rrupt_from_idle(void)
1111 {
1112 	return __this_cpu_read(rcu_dynticks.dynticks_nesting) <= 1;
1113 }
1114 
1115 /*
1116  * Snapshot the specified CPU's dynticks counter so that we can later
1117  * credit them with an implicit quiescent state.  Return 1 if this CPU
1118  * is in dynticks idle mode, which is an extended quiescent state.
1119  */
1120 static int dyntick_save_progress_counter(struct rcu_data *rdp,
1121 					 bool *isidle, unsigned long *maxj)
1122 {
1123 	rdp->dynticks_snap = atomic_add_return(0, &rdp->dynticks->dynticks);
1124 	rcu_sysidle_check_cpu(rdp, isidle, maxj);
1125 	if ((rdp->dynticks_snap & 0x1) == 0) {
1126 		trace_rcu_fqs(rdp->rsp->name, rdp->gpnum, rdp->cpu, TPS("dti"));
1127 		if (ULONG_CMP_LT(READ_ONCE(rdp->gpnum) + ULONG_MAX / 4,
1128 				 rdp->mynode->gpnum))
1129 			WRITE_ONCE(rdp->gpwrap, true);
1130 		return 1;
1131 	}
1132 	return 0;
1133 }
1134 
1135 /*
1136  * Return true if the specified CPU has passed through a quiescent
1137  * state by virtue of being in or having passed through an dynticks
1138  * idle state since the last call to dyntick_save_progress_counter()
1139  * for this same CPU, or by virtue of having been offline.
1140  */
1141 static int rcu_implicit_dynticks_qs(struct rcu_data *rdp,
1142 				    bool *isidle, unsigned long *maxj)
1143 {
1144 	unsigned int curr;
1145 	int *rcrmp;
1146 	unsigned int snap;
1147 
1148 	curr = (unsigned int)atomic_add_return(0, &rdp->dynticks->dynticks);
1149 	snap = (unsigned int)rdp->dynticks_snap;
1150 
1151 	/*
1152 	 * If the CPU passed through or entered a dynticks idle phase with
1153 	 * no active irq/NMI handlers, then we can safely pretend that the CPU
1154 	 * already acknowledged the request to pass through a quiescent
1155 	 * state.  Either way, that CPU cannot possibly be in an RCU
1156 	 * read-side critical section that started before the beginning
1157 	 * of the current RCU grace period.
1158 	 */
1159 	if ((curr & 0x1) == 0 || UINT_CMP_GE(curr, snap + 2)) {
1160 		trace_rcu_fqs(rdp->rsp->name, rdp->gpnum, rdp->cpu, TPS("dti"));
1161 		rdp->dynticks_fqs++;
1162 		return 1;
1163 	}
1164 
1165 	/*
1166 	 * Check for the CPU being offline, but only if the grace period
1167 	 * is old enough.  We don't need to worry about the CPU changing
1168 	 * state: If we see it offline even once, it has been through a
1169 	 * quiescent state.
1170 	 *
1171 	 * The reason for insisting that the grace period be at least
1172 	 * one jiffy old is that CPUs that are not quite online and that
1173 	 * have just gone offline can still execute RCU read-side critical
1174 	 * sections.
1175 	 */
1176 	if (ULONG_CMP_GE(rdp->rsp->gp_start + 2, jiffies))
1177 		return 0;  /* Grace period is not old enough. */
1178 	barrier();
1179 	if (cpu_is_offline(rdp->cpu)) {
1180 		trace_rcu_fqs(rdp->rsp->name, rdp->gpnum, rdp->cpu, TPS("ofl"));
1181 		rdp->offline_fqs++;
1182 		return 1;
1183 	}
1184 
1185 	/*
1186 	 * A CPU running for an extended time within the kernel can
1187 	 * delay RCU grace periods.  When the CPU is in NO_HZ_FULL mode,
1188 	 * even context-switching back and forth between a pair of
1189 	 * in-kernel CPU-bound tasks cannot advance grace periods.
1190 	 * So if the grace period is old enough, make the CPU pay attention.
1191 	 * Note that the unsynchronized assignments to the per-CPU
1192 	 * rcu_sched_qs_mask variable are safe.  Yes, setting of
1193 	 * bits can be lost, but they will be set again on the next
1194 	 * force-quiescent-state pass.  So lost bit sets do not result
1195 	 * in incorrect behavior, merely in a grace period lasting
1196 	 * a few jiffies longer than it might otherwise.  Because
1197 	 * there are at most four threads involved, and because the
1198 	 * updates are only once every few jiffies, the probability of
1199 	 * lossage (and thus of slight grace-period extension) is
1200 	 * quite low.
1201 	 *
1202 	 * Note that if the jiffies_till_sched_qs boot/sysfs parameter
1203 	 * is set too high, we override with half of the RCU CPU stall
1204 	 * warning delay.
1205 	 */
1206 	rcrmp = &per_cpu(rcu_sched_qs_mask, rdp->cpu);
1207 	if (ULONG_CMP_GE(jiffies,
1208 			 rdp->rsp->gp_start + jiffies_till_sched_qs) ||
1209 	    ULONG_CMP_GE(jiffies, rdp->rsp->jiffies_resched)) {
1210 		if (!(READ_ONCE(*rcrmp) & rdp->rsp->flavor_mask)) {
1211 			WRITE_ONCE(rdp->cond_resched_completed,
1212 				   READ_ONCE(rdp->mynode->completed));
1213 			smp_mb(); /* ->cond_resched_completed before *rcrmp. */
1214 			WRITE_ONCE(*rcrmp,
1215 				   READ_ONCE(*rcrmp) + rdp->rsp->flavor_mask);
1216 		}
1217 		rdp->rsp->jiffies_resched += 5; /* Re-enable beating. */
1218 	}
1219 
1220 	/* And if it has been a really long time, kick the CPU as well. */
1221 	if (ULONG_CMP_GE(jiffies,
1222 			 rdp->rsp->gp_start + 2 * jiffies_till_sched_qs) ||
1223 	    ULONG_CMP_GE(jiffies, rdp->rsp->gp_start + jiffies_till_sched_qs))
1224 		resched_cpu(rdp->cpu);  /* Force CPU into scheduler. */
1225 
1226 	return 0;
1227 }
1228 
1229 static void record_gp_stall_check_time(struct rcu_state *rsp)
1230 {
1231 	unsigned long j = jiffies;
1232 	unsigned long j1;
1233 
1234 	rsp->gp_start = j;
1235 	smp_wmb(); /* Record start time before stall time. */
1236 	j1 = rcu_jiffies_till_stall_check();
1237 	WRITE_ONCE(rsp->jiffies_stall, j + j1);
1238 	rsp->jiffies_resched = j + j1 / 2;
1239 	rsp->n_force_qs_gpstart = READ_ONCE(rsp->n_force_qs);
1240 }
1241 
1242 /*
1243  * Convert a ->gp_state value to a character string.
1244  */
1245 static const char *gp_state_getname(short gs)
1246 {
1247 	if (gs < 0 || gs >= ARRAY_SIZE(gp_state_names))
1248 		return "???";
1249 	return gp_state_names[gs];
1250 }
1251 
1252 /*
1253  * Complain about starvation of grace-period kthread.
1254  */
1255 static void rcu_check_gp_kthread_starvation(struct rcu_state *rsp)
1256 {
1257 	unsigned long gpa;
1258 	unsigned long j;
1259 
1260 	j = jiffies;
1261 	gpa = READ_ONCE(rsp->gp_activity);
1262 	if (j - gpa > 2 * HZ) {
1263 		pr_err("%s kthread starved for %ld jiffies! g%lu c%lu f%#x %s(%d) ->state=%#lx\n",
1264 		       rsp->name, j - gpa,
1265 		       rsp->gpnum, rsp->completed,
1266 		       rsp->gp_flags,
1267 		       gp_state_getname(rsp->gp_state), rsp->gp_state,
1268 		       rsp->gp_kthread ? rsp->gp_kthread->state : ~0);
1269 		if (rsp->gp_kthread) {
1270 			sched_show_task(rsp->gp_kthread);
1271 			wake_up_process(rsp->gp_kthread);
1272 		}
1273 	}
1274 }
1275 
1276 /*
1277  * Dump stacks of all tasks running on stalled CPUs.
1278  */
1279 static void rcu_dump_cpu_stacks(struct rcu_state *rsp)
1280 {
1281 	int cpu;
1282 	unsigned long flags;
1283 	struct rcu_node *rnp;
1284 
1285 	rcu_for_each_leaf_node(rsp, rnp) {
1286 		raw_spin_lock_irqsave_rcu_node(rnp, flags);
1287 		if (rnp->qsmask != 0) {
1288 			for_each_leaf_node_possible_cpu(rnp, cpu)
1289 				if (rnp->qsmask & leaf_node_cpu_bit(rnp, cpu))
1290 					dump_cpu_task(cpu);
1291 		}
1292 		raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
1293 	}
1294 }
1295 
1296 /*
1297  * If too much time has passed in the current grace period, and if
1298  * so configured, go kick the relevant kthreads.
1299  */
1300 static void rcu_stall_kick_kthreads(struct rcu_state *rsp)
1301 {
1302 	unsigned long j;
1303 
1304 	if (!rcu_kick_kthreads)
1305 		return;
1306 	j = READ_ONCE(rsp->jiffies_kick_kthreads);
1307 	if (time_after(jiffies, j) && rsp->gp_kthread &&
1308 	    (rcu_gp_in_progress(rsp) || READ_ONCE(rsp->gp_flags))) {
1309 		WARN_ONCE(1, "Kicking %s grace-period kthread\n", rsp->name);
1310 		rcu_ftrace_dump(DUMP_ALL);
1311 		wake_up_process(rsp->gp_kthread);
1312 		WRITE_ONCE(rsp->jiffies_kick_kthreads, j + HZ);
1313 	}
1314 }
1315 
1316 static inline void panic_on_rcu_stall(void)
1317 {
1318 	if (sysctl_panic_on_rcu_stall)
1319 		panic("RCU Stall\n");
1320 }
1321 
1322 static void print_other_cpu_stall(struct rcu_state *rsp, unsigned long gpnum)
1323 {
1324 	int cpu;
1325 	long delta;
1326 	unsigned long flags;
1327 	unsigned long gpa;
1328 	unsigned long j;
1329 	int ndetected = 0;
1330 	struct rcu_node *rnp = rcu_get_root(rsp);
1331 	long totqlen = 0;
1332 
1333 	/* Kick and suppress, if so configured. */
1334 	rcu_stall_kick_kthreads(rsp);
1335 	if (rcu_cpu_stall_suppress)
1336 		return;
1337 
1338 	/* Only let one CPU complain about others per time interval. */
1339 
1340 	raw_spin_lock_irqsave_rcu_node(rnp, flags);
1341 	delta = jiffies - READ_ONCE(rsp->jiffies_stall);
1342 	if (delta < RCU_STALL_RAT_DELAY || !rcu_gp_in_progress(rsp)) {
1343 		raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
1344 		return;
1345 	}
1346 	WRITE_ONCE(rsp->jiffies_stall,
1347 		   jiffies + 3 * rcu_jiffies_till_stall_check() + 3);
1348 	raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
1349 
1350 	/*
1351 	 * OK, time to rat on our buddy...
1352 	 * See Documentation/RCU/stallwarn.txt for info on how to debug
1353 	 * RCU CPU stall warnings.
1354 	 */
1355 	pr_err("INFO: %s detected stalls on CPUs/tasks:",
1356 	       rsp->name);
1357 	print_cpu_stall_info_begin();
1358 	rcu_for_each_leaf_node(rsp, rnp) {
1359 		raw_spin_lock_irqsave_rcu_node(rnp, flags);
1360 		ndetected += rcu_print_task_stall(rnp);
1361 		if (rnp->qsmask != 0) {
1362 			for_each_leaf_node_possible_cpu(rnp, cpu)
1363 				if (rnp->qsmask & leaf_node_cpu_bit(rnp, cpu)) {
1364 					print_cpu_stall_info(rsp, cpu);
1365 					ndetected++;
1366 				}
1367 		}
1368 		raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
1369 	}
1370 
1371 	print_cpu_stall_info_end();
1372 	for_each_possible_cpu(cpu)
1373 		totqlen += per_cpu_ptr(rsp->rda, cpu)->qlen;
1374 	pr_cont("(detected by %d, t=%ld jiffies, g=%ld, c=%ld, q=%lu)\n",
1375 	       smp_processor_id(), (long)(jiffies - rsp->gp_start),
1376 	       (long)rsp->gpnum, (long)rsp->completed, totqlen);
1377 	if (ndetected) {
1378 		rcu_dump_cpu_stacks(rsp);
1379 	} else {
1380 		if (READ_ONCE(rsp->gpnum) != gpnum ||
1381 		    READ_ONCE(rsp->completed) == gpnum) {
1382 			pr_err("INFO: Stall ended before state dump start\n");
1383 		} else {
1384 			j = jiffies;
1385 			gpa = READ_ONCE(rsp->gp_activity);
1386 			pr_err("All QSes seen, last %s kthread activity %ld (%ld-%ld), jiffies_till_next_fqs=%ld, root ->qsmask %#lx\n",
1387 			       rsp->name, j - gpa, j, gpa,
1388 			       jiffies_till_next_fqs,
1389 			       rcu_get_root(rsp)->qsmask);
1390 			/* In this case, the current CPU might be at fault. */
1391 			sched_show_task(current);
1392 		}
1393 	}
1394 
1395 	/* Complain about tasks blocking the grace period. */
1396 	rcu_print_detail_task_stall(rsp);
1397 
1398 	rcu_check_gp_kthread_starvation(rsp);
1399 
1400 	panic_on_rcu_stall();
1401 
1402 	force_quiescent_state(rsp);  /* Kick them all. */
1403 }
1404 
1405 static void print_cpu_stall(struct rcu_state *rsp)
1406 {
1407 	int cpu;
1408 	unsigned long flags;
1409 	struct rcu_node *rnp = rcu_get_root(rsp);
1410 	long totqlen = 0;
1411 
1412 	/* Kick and suppress, if so configured. */
1413 	rcu_stall_kick_kthreads(rsp);
1414 	if (rcu_cpu_stall_suppress)
1415 		return;
1416 
1417 	/*
1418 	 * OK, time to rat on ourselves...
1419 	 * See Documentation/RCU/stallwarn.txt for info on how to debug
1420 	 * RCU CPU stall warnings.
1421 	 */
1422 	pr_err("INFO: %s self-detected stall on CPU", rsp->name);
1423 	print_cpu_stall_info_begin();
1424 	print_cpu_stall_info(rsp, smp_processor_id());
1425 	print_cpu_stall_info_end();
1426 	for_each_possible_cpu(cpu)
1427 		totqlen += per_cpu_ptr(rsp->rda, cpu)->qlen;
1428 	pr_cont(" (t=%lu jiffies g=%ld c=%ld q=%lu)\n",
1429 		jiffies - rsp->gp_start,
1430 		(long)rsp->gpnum, (long)rsp->completed, totqlen);
1431 
1432 	rcu_check_gp_kthread_starvation(rsp);
1433 
1434 	rcu_dump_cpu_stacks(rsp);
1435 
1436 	raw_spin_lock_irqsave_rcu_node(rnp, flags);
1437 	if (ULONG_CMP_GE(jiffies, READ_ONCE(rsp->jiffies_stall)))
1438 		WRITE_ONCE(rsp->jiffies_stall,
1439 			   jiffies + 3 * rcu_jiffies_till_stall_check() + 3);
1440 	raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
1441 
1442 	panic_on_rcu_stall();
1443 
1444 	/*
1445 	 * Attempt to revive the RCU machinery by forcing a context switch.
1446 	 *
1447 	 * A context switch would normally allow the RCU state machine to make
1448 	 * progress and it could be we're stuck in kernel space without context
1449 	 * switches for an entirely unreasonable amount of time.
1450 	 */
1451 	resched_cpu(smp_processor_id());
1452 }
1453 
1454 static void check_cpu_stall(struct rcu_state *rsp, struct rcu_data *rdp)
1455 {
1456 	unsigned long completed;
1457 	unsigned long gpnum;
1458 	unsigned long gps;
1459 	unsigned long j;
1460 	unsigned long js;
1461 	struct rcu_node *rnp;
1462 
1463 	if ((rcu_cpu_stall_suppress && !rcu_kick_kthreads) ||
1464 	    !rcu_gp_in_progress(rsp))
1465 		return;
1466 	rcu_stall_kick_kthreads(rsp);
1467 	j = jiffies;
1468 
1469 	/*
1470 	 * Lots of memory barriers to reject false positives.
1471 	 *
1472 	 * The idea is to pick up rsp->gpnum, then rsp->jiffies_stall,
1473 	 * then rsp->gp_start, and finally rsp->completed.  These values
1474 	 * are updated in the opposite order with memory barriers (or
1475 	 * equivalent) during grace-period initialization and cleanup.
1476 	 * Now, a false positive can occur if we get an new value of
1477 	 * rsp->gp_start and a old value of rsp->jiffies_stall.  But given
1478 	 * the memory barriers, the only way that this can happen is if one
1479 	 * grace period ends and another starts between these two fetches.
1480 	 * Detect this by comparing rsp->completed with the previous fetch
1481 	 * from rsp->gpnum.
1482 	 *
1483 	 * Given this check, comparisons of jiffies, rsp->jiffies_stall,
1484 	 * and rsp->gp_start suffice to forestall false positives.
1485 	 */
1486 	gpnum = READ_ONCE(rsp->gpnum);
1487 	smp_rmb(); /* Pick up ->gpnum first... */
1488 	js = READ_ONCE(rsp->jiffies_stall);
1489 	smp_rmb(); /* ...then ->jiffies_stall before the rest... */
1490 	gps = READ_ONCE(rsp->gp_start);
1491 	smp_rmb(); /* ...and finally ->gp_start before ->completed. */
1492 	completed = READ_ONCE(rsp->completed);
1493 	if (ULONG_CMP_GE(completed, gpnum) ||
1494 	    ULONG_CMP_LT(j, js) ||
1495 	    ULONG_CMP_GE(gps, js))
1496 		return; /* No stall or GP completed since entering function. */
1497 	rnp = rdp->mynode;
1498 	if (rcu_gp_in_progress(rsp) &&
1499 	    (READ_ONCE(rnp->qsmask) & rdp->grpmask)) {
1500 
1501 		/* We haven't checked in, so go dump stack. */
1502 		print_cpu_stall(rsp);
1503 
1504 	} else if (rcu_gp_in_progress(rsp) &&
1505 		   ULONG_CMP_GE(j, js + RCU_STALL_RAT_DELAY)) {
1506 
1507 		/* They had a few time units to dump stack, so complain. */
1508 		print_other_cpu_stall(rsp, gpnum);
1509 	}
1510 }
1511 
1512 /**
1513  * rcu_cpu_stall_reset - prevent further stall warnings in current grace period
1514  *
1515  * Set the stall-warning timeout way off into the future, thus preventing
1516  * any RCU CPU stall-warning messages from appearing in the current set of
1517  * RCU grace periods.
1518  *
1519  * The caller must disable hard irqs.
1520  */
1521 void rcu_cpu_stall_reset(void)
1522 {
1523 	struct rcu_state *rsp;
1524 
1525 	for_each_rcu_flavor(rsp)
1526 		WRITE_ONCE(rsp->jiffies_stall, jiffies + ULONG_MAX / 2);
1527 }
1528 
1529 /*
1530  * Initialize the specified rcu_data structure's default callback list
1531  * to empty.  The default callback list is the one that is not used by
1532  * no-callbacks CPUs.
1533  */
1534 static void init_default_callback_list(struct rcu_data *rdp)
1535 {
1536 	int i;
1537 
1538 	rdp->nxtlist = NULL;
1539 	for (i = 0; i < RCU_NEXT_SIZE; i++)
1540 		rdp->nxttail[i] = &rdp->nxtlist;
1541 }
1542 
1543 /*
1544  * Initialize the specified rcu_data structure's callback list to empty.
1545  */
1546 static void init_callback_list(struct rcu_data *rdp)
1547 {
1548 	if (init_nocb_callback_list(rdp))
1549 		return;
1550 	init_default_callback_list(rdp);
1551 }
1552 
1553 /*
1554  * Determine the value that ->completed will have at the end of the
1555  * next subsequent grace period.  This is used to tag callbacks so that
1556  * a CPU can invoke callbacks in a timely fashion even if that CPU has
1557  * been dyntick-idle for an extended period with callbacks under the
1558  * influence of RCU_FAST_NO_HZ.
1559  *
1560  * The caller must hold rnp->lock with interrupts disabled.
1561  */
1562 static unsigned long rcu_cbs_completed(struct rcu_state *rsp,
1563 				       struct rcu_node *rnp)
1564 {
1565 	/*
1566 	 * If RCU is idle, we just wait for the next grace period.
1567 	 * But we can only be sure that RCU is idle if we are looking
1568 	 * at the root rcu_node structure -- otherwise, a new grace
1569 	 * period might have started, but just not yet gotten around
1570 	 * to initializing the current non-root rcu_node structure.
1571 	 */
1572 	if (rcu_get_root(rsp) == rnp && rnp->gpnum == rnp->completed)
1573 		return rnp->completed + 1;
1574 
1575 	/*
1576 	 * Otherwise, wait for a possible partial grace period and
1577 	 * then the subsequent full grace period.
1578 	 */
1579 	return rnp->completed + 2;
1580 }
1581 
1582 /*
1583  * Trace-event helper function for rcu_start_future_gp() and
1584  * rcu_nocb_wait_gp().
1585  */
1586 static void trace_rcu_future_gp(struct rcu_node *rnp, struct rcu_data *rdp,
1587 				unsigned long c, const char *s)
1588 {
1589 	trace_rcu_future_grace_period(rdp->rsp->name, rnp->gpnum,
1590 				      rnp->completed, c, rnp->level,
1591 				      rnp->grplo, rnp->grphi, s);
1592 }
1593 
1594 /*
1595  * Start some future grace period, as needed to handle newly arrived
1596  * callbacks.  The required future grace periods are recorded in each
1597  * rcu_node structure's ->need_future_gp field.  Returns true if there
1598  * is reason to awaken the grace-period kthread.
1599  *
1600  * The caller must hold the specified rcu_node structure's ->lock.
1601  */
1602 static bool __maybe_unused
1603 rcu_start_future_gp(struct rcu_node *rnp, struct rcu_data *rdp,
1604 		    unsigned long *c_out)
1605 {
1606 	unsigned long c;
1607 	int i;
1608 	bool ret = false;
1609 	struct rcu_node *rnp_root = rcu_get_root(rdp->rsp);
1610 
1611 	/*
1612 	 * Pick up grace-period number for new callbacks.  If this
1613 	 * grace period is already marked as needed, return to the caller.
1614 	 */
1615 	c = rcu_cbs_completed(rdp->rsp, rnp);
1616 	trace_rcu_future_gp(rnp, rdp, c, TPS("Startleaf"));
1617 	if (rnp->need_future_gp[c & 0x1]) {
1618 		trace_rcu_future_gp(rnp, rdp, c, TPS("Prestartleaf"));
1619 		goto out;
1620 	}
1621 
1622 	/*
1623 	 * If either this rcu_node structure or the root rcu_node structure
1624 	 * believe that a grace period is in progress, then we must wait
1625 	 * for the one following, which is in "c".  Because our request
1626 	 * will be noticed at the end of the current grace period, we don't
1627 	 * need to explicitly start one.  We only do the lockless check
1628 	 * of rnp_root's fields if the current rcu_node structure thinks
1629 	 * there is no grace period in flight, and because we hold rnp->lock,
1630 	 * the only possible change is when rnp_root's two fields are
1631 	 * equal, in which case rnp_root->gpnum might be concurrently
1632 	 * incremented.  But that is OK, as it will just result in our
1633 	 * doing some extra useless work.
1634 	 */
1635 	if (rnp->gpnum != rnp->completed ||
1636 	    READ_ONCE(rnp_root->gpnum) != READ_ONCE(rnp_root->completed)) {
1637 		rnp->need_future_gp[c & 0x1]++;
1638 		trace_rcu_future_gp(rnp, rdp, c, TPS("Startedleaf"));
1639 		goto out;
1640 	}
1641 
1642 	/*
1643 	 * There might be no grace period in progress.  If we don't already
1644 	 * hold it, acquire the root rcu_node structure's lock in order to
1645 	 * start one (if needed).
1646 	 */
1647 	if (rnp != rnp_root)
1648 		raw_spin_lock_rcu_node(rnp_root);
1649 
1650 	/*
1651 	 * Get a new grace-period number.  If there really is no grace
1652 	 * period in progress, it will be smaller than the one we obtained
1653 	 * earlier.  Adjust callbacks as needed.  Note that even no-CBs
1654 	 * CPUs have a ->nxtcompleted[] array, so no no-CBs checks needed.
1655 	 */
1656 	c = rcu_cbs_completed(rdp->rsp, rnp_root);
1657 	for (i = RCU_DONE_TAIL; i < RCU_NEXT_TAIL; i++)
1658 		if (ULONG_CMP_LT(c, rdp->nxtcompleted[i]))
1659 			rdp->nxtcompleted[i] = c;
1660 
1661 	/*
1662 	 * If the needed for the required grace period is already
1663 	 * recorded, trace and leave.
1664 	 */
1665 	if (rnp_root->need_future_gp[c & 0x1]) {
1666 		trace_rcu_future_gp(rnp, rdp, c, TPS("Prestartedroot"));
1667 		goto unlock_out;
1668 	}
1669 
1670 	/* Record the need for the future grace period. */
1671 	rnp_root->need_future_gp[c & 0x1]++;
1672 
1673 	/* If a grace period is not already in progress, start one. */
1674 	if (rnp_root->gpnum != rnp_root->completed) {
1675 		trace_rcu_future_gp(rnp, rdp, c, TPS("Startedleafroot"));
1676 	} else {
1677 		trace_rcu_future_gp(rnp, rdp, c, TPS("Startedroot"));
1678 		ret = rcu_start_gp_advanced(rdp->rsp, rnp_root, rdp);
1679 	}
1680 unlock_out:
1681 	if (rnp != rnp_root)
1682 		raw_spin_unlock_rcu_node(rnp_root);
1683 out:
1684 	if (c_out != NULL)
1685 		*c_out = c;
1686 	return ret;
1687 }
1688 
1689 /*
1690  * Clean up any old requests for the just-ended grace period.  Also return
1691  * whether any additional grace periods have been requested.  Also invoke
1692  * rcu_nocb_gp_cleanup() in order to wake up any no-callbacks kthreads
1693  * waiting for this grace period to complete.
1694  */
1695 static int rcu_future_gp_cleanup(struct rcu_state *rsp, struct rcu_node *rnp)
1696 {
1697 	int c = rnp->completed;
1698 	int needmore;
1699 	struct rcu_data *rdp = this_cpu_ptr(rsp->rda);
1700 
1701 	rnp->need_future_gp[c & 0x1] = 0;
1702 	needmore = rnp->need_future_gp[(c + 1) & 0x1];
1703 	trace_rcu_future_gp(rnp, rdp, c,
1704 			    needmore ? TPS("CleanupMore") : TPS("Cleanup"));
1705 	return needmore;
1706 }
1707 
1708 /*
1709  * Awaken the grace-period kthread for the specified flavor of RCU.
1710  * Don't do a self-awaken, and don't bother awakening when there is
1711  * nothing for the grace-period kthread to do (as in several CPUs
1712  * raced to awaken, and we lost), and finally don't try to awaken
1713  * a kthread that has not yet been created.
1714  */
1715 static void rcu_gp_kthread_wake(struct rcu_state *rsp)
1716 {
1717 	if (current == rsp->gp_kthread ||
1718 	    !READ_ONCE(rsp->gp_flags) ||
1719 	    !rsp->gp_kthread)
1720 		return;
1721 	swake_up(&rsp->gp_wq);
1722 }
1723 
1724 /*
1725  * If there is room, assign a ->completed number to any callbacks on
1726  * this CPU that have not already been assigned.  Also accelerate any
1727  * callbacks that were previously assigned a ->completed number that has
1728  * since proven to be too conservative, which can happen if callbacks get
1729  * assigned a ->completed number while RCU is idle, but with reference to
1730  * a non-root rcu_node structure.  This function is idempotent, so it does
1731  * not hurt to call it repeatedly.  Returns an flag saying that we should
1732  * awaken the RCU grace-period kthread.
1733  *
1734  * The caller must hold rnp->lock with interrupts disabled.
1735  */
1736 static bool rcu_accelerate_cbs(struct rcu_state *rsp, struct rcu_node *rnp,
1737 			       struct rcu_data *rdp)
1738 {
1739 	unsigned long c;
1740 	int i;
1741 	bool ret;
1742 
1743 	/* If the CPU has no callbacks, nothing to do. */
1744 	if (!rdp->nxttail[RCU_NEXT_TAIL] || !*rdp->nxttail[RCU_DONE_TAIL])
1745 		return false;
1746 
1747 	/*
1748 	 * Starting from the sublist containing the callbacks most
1749 	 * recently assigned a ->completed number and working down, find the
1750 	 * first sublist that is not assignable to an upcoming grace period.
1751 	 * Such a sublist has something in it (first two tests) and has
1752 	 * a ->completed number assigned that will complete sooner than
1753 	 * the ->completed number for newly arrived callbacks (last test).
1754 	 *
1755 	 * The key point is that any later sublist can be assigned the
1756 	 * same ->completed number as the newly arrived callbacks, which
1757 	 * means that the callbacks in any of these later sublist can be
1758 	 * grouped into a single sublist, whether or not they have already
1759 	 * been assigned a ->completed number.
1760 	 */
1761 	c = rcu_cbs_completed(rsp, rnp);
1762 	for (i = RCU_NEXT_TAIL - 1; i > RCU_DONE_TAIL; i--)
1763 		if (rdp->nxttail[i] != rdp->nxttail[i - 1] &&
1764 		    !ULONG_CMP_GE(rdp->nxtcompleted[i], c))
1765 			break;
1766 
1767 	/*
1768 	 * If there are no sublist for unassigned callbacks, leave.
1769 	 * At the same time, advance "i" one sublist, so that "i" will
1770 	 * index into the sublist where all the remaining callbacks should
1771 	 * be grouped into.
1772 	 */
1773 	if (++i >= RCU_NEXT_TAIL)
1774 		return false;
1775 
1776 	/*
1777 	 * Assign all subsequent callbacks' ->completed number to the next
1778 	 * full grace period and group them all in the sublist initially
1779 	 * indexed by "i".
1780 	 */
1781 	for (; i <= RCU_NEXT_TAIL; i++) {
1782 		rdp->nxttail[i] = rdp->nxttail[RCU_NEXT_TAIL];
1783 		rdp->nxtcompleted[i] = c;
1784 	}
1785 	/* Record any needed additional grace periods. */
1786 	ret = rcu_start_future_gp(rnp, rdp, NULL);
1787 
1788 	/* Trace depending on how much we were able to accelerate. */
1789 	if (!*rdp->nxttail[RCU_WAIT_TAIL])
1790 		trace_rcu_grace_period(rsp->name, rdp->gpnum, TPS("AccWaitCB"));
1791 	else
1792 		trace_rcu_grace_period(rsp->name, rdp->gpnum, TPS("AccReadyCB"));
1793 	return ret;
1794 }
1795 
1796 /*
1797  * Move any callbacks whose grace period has completed to the
1798  * RCU_DONE_TAIL sublist, then compact the remaining sublists and
1799  * assign ->completed numbers to any callbacks in the RCU_NEXT_TAIL
1800  * sublist.  This function is idempotent, so it does not hurt to
1801  * invoke it repeatedly.  As long as it is not invoked -too- often...
1802  * Returns true if the RCU grace-period kthread needs to be awakened.
1803  *
1804  * The caller must hold rnp->lock with interrupts disabled.
1805  */
1806 static bool rcu_advance_cbs(struct rcu_state *rsp, struct rcu_node *rnp,
1807 			    struct rcu_data *rdp)
1808 {
1809 	int i, j;
1810 
1811 	/* If the CPU has no callbacks, nothing to do. */
1812 	if (!rdp->nxttail[RCU_NEXT_TAIL] || !*rdp->nxttail[RCU_DONE_TAIL])
1813 		return false;
1814 
1815 	/*
1816 	 * Find all callbacks whose ->completed numbers indicate that they
1817 	 * are ready to invoke, and put them into the RCU_DONE_TAIL sublist.
1818 	 */
1819 	for (i = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++) {
1820 		if (ULONG_CMP_LT(rnp->completed, rdp->nxtcompleted[i]))
1821 			break;
1822 		rdp->nxttail[RCU_DONE_TAIL] = rdp->nxttail[i];
1823 	}
1824 	/* Clean up any sublist tail pointers that were misordered above. */
1825 	for (j = RCU_WAIT_TAIL; j < i; j++)
1826 		rdp->nxttail[j] = rdp->nxttail[RCU_DONE_TAIL];
1827 
1828 	/* Copy down callbacks to fill in empty sublists. */
1829 	for (j = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++, j++) {
1830 		if (rdp->nxttail[j] == rdp->nxttail[RCU_NEXT_TAIL])
1831 			break;
1832 		rdp->nxttail[j] = rdp->nxttail[i];
1833 		rdp->nxtcompleted[j] = rdp->nxtcompleted[i];
1834 	}
1835 
1836 	/* Classify any remaining callbacks. */
1837 	return rcu_accelerate_cbs(rsp, rnp, rdp);
1838 }
1839 
1840 /*
1841  * Update CPU-local rcu_data state to record the beginnings and ends of
1842  * grace periods.  The caller must hold the ->lock of the leaf rcu_node
1843  * structure corresponding to the current CPU, and must have irqs disabled.
1844  * Returns true if the grace-period kthread needs to be awakened.
1845  */
1846 static bool __note_gp_changes(struct rcu_state *rsp, struct rcu_node *rnp,
1847 			      struct rcu_data *rdp)
1848 {
1849 	bool ret;
1850 	bool need_gp;
1851 
1852 	/* Handle the ends of any preceding grace periods first. */
1853 	if (rdp->completed == rnp->completed &&
1854 	    !unlikely(READ_ONCE(rdp->gpwrap))) {
1855 
1856 		/* No grace period end, so just accelerate recent callbacks. */
1857 		ret = rcu_accelerate_cbs(rsp, rnp, rdp);
1858 
1859 	} else {
1860 
1861 		/* Advance callbacks. */
1862 		ret = rcu_advance_cbs(rsp, rnp, rdp);
1863 
1864 		/* Remember that we saw this grace-period completion. */
1865 		rdp->completed = rnp->completed;
1866 		trace_rcu_grace_period(rsp->name, rdp->gpnum, TPS("cpuend"));
1867 	}
1868 
1869 	if (rdp->gpnum != rnp->gpnum || unlikely(READ_ONCE(rdp->gpwrap))) {
1870 		/*
1871 		 * If the current grace period is waiting for this CPU,
1872 		 * set up to detect a quiescent state, otherwise don't
1873 		 * go looking for one.
1874 		 */
1875 		rdp->gpnum = rnp->gpnum;
1876 		trace_rcu_grace_period(rsp->name, rdp->gpnum, TPS("cpustart"));
1877 		need_gp = !!(rnp->qsmask & rdp->grpmask);
1878 		rdp->cpu_no_qs.b.norm = need_gp;
1879 		rdp->rcu_qs_ctr_snap = __this_cpu_read(rcu_qs_ctr);
1880 		rdp->core_needs_qs = need_gp;
1881 		zero_cpu_stall_ticks(rdp);
1882 		WRITE_ONCE(rdp->gpwrap, false);
1883 	}
1884 	return ret;
1885 }
1886 
1887 static void note_gp_changes(struct rcu_state *rsp, struct rcu_data *rdp)
1888 {
1889 	unsigned long flags;
1890 	bool needwake;
1891 	struct rcu_node *rnp;
1892 
1893 	local_irq_save(flags);
1894 	rnp = rdp->mynode;
1895 	if ((rdp->gpnum == READ_ONCE(rnp->gpnum) &&
1896 	     rdp->completed == READ_ONCE(rnp->completed) &&
1897 	     !unlikely(READ_ONCE(rdp->gpwrap))) || /* w/out lock. */
1898 	    !raw_spin_trylock_rcu_node(rnp)) { /* irqs already off, so later. */
1899 		local_irq_restore(flags);
1900 		return;
1901 	}
1902 	needwake = __note_gp_changes(rsp, rnp, rdp);
1903 	raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
1904 	if (needwake)
1905 		rcu_gp_kthread_wake(rsp);
1906 }
1907 
1908 static void rcu_gp_slow(struct rcu_state *rsp, int delay)
1909 {
1910 	if (delay > 0 &&
1911 	    !(rsp->gpnum % (rcu_num_nodes * PER_RCU_NODE_PERIOD * delay)))
1912 		schedule_timeout_uninterruptible(delay);
1913 }
1914 
1915 /*
1916  * Initialize a new grace period.  Return false if no grace period required.
1917  */
1918 static bool rcu_gp_init(struct rcu_state *rsp)
1919 {
1920 	unsigned long oldmask;
1921 	struct rcu_data *rdp;
1922 	struct rcu_node *rnp = rcu_get_root(rsp);
1923 
1924 	WRITE_ONCE(rsp->gp_activity, jiffies);
1925 	raw_spin_lock_irq_rcu_node(rnp);
1926 	if (!READ_ONCE(rsp->gp_flags)) {
1927 		/* Spurious wakeup, tell caller to go back to sleep.  */
1928 		raw_spin_unlock_irq_rcu_node(rnp);
1929 		return false;
1930 	}
1931 	WRITE_ONCE(rsp->gp_flags, 0); /* Clear all flags: New grace period. */
1932 
1933 	if (WARN_ON_ONCE(rcu_gp_in_progress(rsp))) {
1934 		/*
1935 		 * Grace period already in progress, don't start another.
1936 		 * Not supposed to be able to happen.
1937 		 */
1938 		raw_spin_unlock_irq_rcu_node(rnp);
1939 		return false;
1940 	}
1941 
1942 	/* Advance to a new grace period and initialize state. */
1943 	record_gp_stall_check_time(rsp);
1944 	/* Record GP times before starting GP, hence smp_store_release(). */
1945 	smp_store_release(&rsp->gpnum, rsp->gpnum + 1);
1946 	trace_rcu_grace_period(rsp->name, rsp->gpnum, TPS("start"));
1947 	raw_spin_unlock_irq_rcu_node(rnp);
1948 
1949 	/*
1950 	 * Apply per-leaf buffered online and offline operations to the
1951 	 * rcu_node tree.  Note that this new grace period need not wait
1952 	 * for subsequent online CPUs, and that quiescent-state forcing
1953 	 * will handle subsequent offline CPUs.
1954 	 */
1955 	rcu_for_each_leaf_node(rsp, rnp) {
1956 		rcu_gp_slow(rsp, gp_preinit_delay);
1957 		raw_spin_lock_irq_rcu_node(rnp);
1958 		if (rnp->qsmaskinit == rnp->qsmaskinitnext &&
1959 		    !rnp->wait_blkd_tasks) {
1960 			/* Nothing to do on this leaf rcu_node structure. */
1961 			raw_spin_unlock_irq_rcu_node(rnp);
1962 			continue;
1963 		}
1964 
1965 		/* Record old state, apply changes to ->qsmaskinit field. */
1966 		oldmask = rnp->qsmaskinit;
1967 		rnp->qsmaskinit = rnp->qsmaskinitnext;
1968 
1969 		/* If zero-ness of ->qsmaskinit changed, propagate up tree. */
1970 		if (!oldmask != !rnp->qsmaskinit) {
1971 			if (!oldmask) /* First online CPU for this rcu_node. */
1972 				rcu_init_new_rnp(rnp);
1973 			else if (rcu_preempt_has_tasks(rnp)) /* blocked tasks */
1974 				rnp->wait_blkd_tasks = true;
1975 			else /* Last offline CPU and can propagate. */
1976 				rcu_cleanup_dead_rnp(rnp);
1977 		}
1978 
1979 		/*
1980 		 * If all waited-on tasks from prior grace period are
1981 		 * done, and if all this rcu_node structure's CPUs are
1982 		 * still offline, propagate up the rcu_node tree and
1983 		 * clear ->wait_blkd_tasks.  Otherwise, if one of this
1984 		 * rcu_node structure's CPUs has since come back online,
1985 		 * simply clear ->wait_blkd_tasks (but rcu_cleanup_dead_rnp()
1986 		 * checks for this, so just call it unconditionally).
1987 		 */
1988 		if (rnp->wait_blkd_tasks &&
1989 		    (!rcu_preempt_has_tasks(rnp) ||
1990 		     rnp->qsmaskinit)) {
1991 			rnp->wait_blkd_tasks = false;
1992 			rcu_cleanup_dead_rnp(rnp);
1993 		}
1994 
1995 		raw_spin_unlock_irq_rcu_node(rnp);
1996 	}
1997 
1998 	/*
1999 	 * Set the quiescent-state-needed bits in all the rcu_node
2000 	 * structures for all currently online CPUs in breadth-first order,
2001 	 * starting from the root rcu_node structure, relying on the layout
2002 	 * of the tree within the rsp->node[] array.  Note that other CPUs
2003 	 * will access only the leaves of the hierarchy, thus seeing that no
2004 	 * grace period is in progress, at least until the corresponding
2005 	 * leaf node has been initialized.
2006 	 *
2007 	 * The grace period cannot complete until the initialization
2008 	 * process finishes, because this kthread handles both.
2009 	 */
2010 	rcu_for_each_node_breadth_first(rsp, rnp) {
2011 		rcu_gp_slow(rsp, gp_init_delay);
2012 		raw_spin_lock_irq_rcu_node(rnp);
2013 		rdp = this_cpu_ptr(rsp->rda);
2014 		rcu_preempt_check_blocked_tasks(rnp);
2015 		rnp->qsmask = rnp->qsmaskinit;
2016 		WRITE_ONCE(rnp->gpnum, rsp->gpnum);
2017 		if (WARN_ON_ONCE(rnp->completed != rsp->completed))
2018 			WRITE_ONCE(rnp->completed, rsp->completed);
2019 		if (rnp == rdp->mynode)
2020 			(void)__note_gp_changes(rsp, rnp, rdp);
2021 		rcu_preempt_boost_start_gp(rnp);
2022 		trace_rcu_grace_period_init(rsp->name, rnp->gpnum,
2023 					    rnp->level, rnp->grplo,
2024 					    rnp->grphi, rnp->qsmask);
2025 		raw_spin_unlock_irq_rcu_node(rnp);
2026 		cond_resched_rcu_qs();
2027 		WRITE_ONCE(rsp->gp_activity, jiffies);
2028 	}
2029 
2030 	return true;
2031 }
2032 
2033 /*
2034  * Helper function for wait_event_interruptible_timeout() wakeup
2035  * at force-quiescent-state time.
2036  */
2037 static bool rcu_gp_fqs_check_wake(struct rcu_state *rsp, int *gfp)
2038 {
2039 	struct rcu_node *rnp = rcu_get_root(rsp);
2040 
2041 	/* Someone like call_rcu() requested a force-quiescent-state scan. */
2042 	*gfp = READ_ONCE(rsp->gp_flags);
2043 	if (*gfp & RCU_GP_FLAG_FQS)
2044 		return true;
2045 
2046 	/* The current grace period has completed. */
2047 	if (!READ_ONCE(rnp->qsmask) && !rcu_preempt_blocked_readers_cgp(rnp))
2048 		return true;
2049 
2050 	return false;
2051 }
2052 
2053 /*
2054  * Do one round of quiescent-state forcing.
2055  */
2056 static void rcu_gp_fqs(struct rcu_state *rsp, bool first_time)
2057 {
2058 	bool isidle = false;
2059 	unsigned long maxj;
2060 	struct rcu_node *rnp = rcu_get_root(rsp);
2061 
2062 	WRITE_ONCE(rsp->gp_activity, jiffies);
2063 	rsp->n_force_qs++;
2064 	if (first_time) {
2065 		/* Collect dyntick-idle snapshots. */
2066 		if (is_sysidle_rcu_state(rsp)) {
2067 			isidle = true;
2068 			maxj = jiffies - ULONG_MAX / 4;
2069 		}
2070 		force_qs_rnp(rsp, dyntick_save_progress_counter,
2071 			     &isidle, &maxj);
2072 		rcu_sysidle_report_gp(rsp, isidle, maxj);
2073 	} else {
2074 		/* Handle dyntick-idle and offline CPUs. */
2075 		isidle = true;
2076 		force_qs_rnp(rsp, rcu_implicit_dynticks_qs, &isidle, &maxj);
2077 	}
2078 	/* Clear flag to prevent immediate re-entry. */
2079 	if (READ_ONCE(rsp->gp_flags) & RCU_GP_FLAG_FQS) {
2080 		raw_spin_lock_irq_rcu_node(rnp);
2081 		WRITE_ONCE(rsp->gp_flags,
2082 			   READ_ONCE(rsp->gp_flags) & ~RCU_GP_FLAG_FQS);
2083 		raw_spin_unlock_irq_rcu_node(rnp);
2084 	}
2085 }
2086 
2087 /*
2088  * Clean up after the old grace period.
2089  */
2090 static void rcu_gp_cleanup(struct rcu_state *rsp)
2091 {
2092 	unsigned long gp_duration;
2093 	bool needgp = false;
2094 	int nocb = 0;
2095 	struct rcu_data *rdp;
2096 	struct rcu_node *rnp = rcu_get_root(rsp);
2097 	struct swait_queue_head *sq;
2098 
2099 	WRITE_ONCE(rsp->gp_activity, jiffies);
2100 	raw_spin_lock_irq_rcu_node(rnp);
2101 	gp_duration = jiffies - rsp->gp_start;
2102 	if (gp_duration > rsp->gp_max)
2103 		rsp->gp_max = gp_duration;
2104 
2105 	/*
2106 	 * We know the grace period is complete, but to everyone else
2107 	 * it appears to still be ongoing.  But it is also the case
2108 	 * that to everyone else it looks like there is nothing that
2109 	 * they can do to advance the grace period.  It is therefore
2110 	 * safe for us to drop the lock in order to mark the grace
2111 	 * period as completed in all of the rcu_node structures.
2112 	 */
2113 	raw_spin_unlock_irq_rcu_node(rnp);
2114 
2115 	/*
2116 	 * Propagate new ->completed value to rcu_node structures so
2117 	 * that other CPUs don't have to wait until the start of the next
2118 	 * grace period to process their callbacks.  This also avoids
2119 	 * some nasty RCU grace-period initialization races by forcing
2120 	 * the end of the current grace period to be completely recorded in
2121 	 * all of the rcu_node structures before the beginning of the next
2122 	 * grace period is recorded in any of the rcu_node structures.
2123 	 */
2124 	rcu_for_each_node_breadth_first(rsp, rnp) {
2125 		raw_spin_lock_irq_rcu_node(rnp);
2126 		WARN_ON_ONCE(rcu_preempt_blocked_readers_cgp(rnp));
2127 		WARN_ON_ONCE(rnp->qsmask);
2128 		WRITE_ONCE(rnp->completed, rsp->gpnum);
2129 		rdp = this_cpu_ptr(rsp->rda);
2130 		if (rnp == rdp->mynode)
2131 			needgp = __note_gp_changes(rsp, rnp, rdp) || needgp;
2132 		/* smp_mb() provided by prior unlock-lock pair. */
2133 		nocb += rcu_future_gp_cleanup(rsp, rnp);
2134 		sq = rcu_nocb_gp_get(rnp);
2135 		raw_spin_unlock_irq_rcu_node(rnp);
2136 		rcu_nocb_gp_cleanup(sq);
2137 		cond_resched_rcu_qs();
2138 		WRITE_ONCE(rsp->gp_activity, jiffies);
2139 		rcu_gp_slow(rsp, gp_cleanup_delay);
2140 	}
2141 	rnp = rcu_get_root(rsp);
2142 	raw_spin_lock_irq_rcu_node(rnp); /* Order GP before ->completed update. */
2143 	rcu_nocb_gp_set(rnp, nocb);
2144 
2145 	/* Declare grace period done. */
2146 	WRITE_ONCE(rsp->completed, rsp->gpnum);
2147 	trace_rcu_grace_period(rsp->name, rsp->completed, TPS("end"));
2148 	rsp->gp_state = RCU_GP_IDLE;
2149 	rdp = this_cpu_ptr(rsp->rda);
2150 	/* Advance CBs to reduce false positives below. */
2151 	needgp = rcu_advance_cbs(rsp, rnp, rdp) || needgp;
2152 	if (needgp || cpu_needs_another_gp(rsp, rdp)) {
2153 		WRITE_ONCE(rsp->gp_flags, RCU_GP_FLAG_INIT);
2154 		trace_rcu_grace_period(rsp->name,
2155 				       READ_ONCE(rsp->gpnum),
2156 				       TPS("newreq"));
2157 	}
2158 	raw_spin_unlock_irq_rcu_node(rnp);
2159 }
2160 
2161 /*
2162  * Body of kthread that handles grace periods.
2163  */
2164 static int __noreturn rcu_gp_kthread(void *arg)
2165 {
2166 	bool first_gp_fqs;
2167 	int gf;
2168 	unsigned long j;
2169 	int ret;
2170 	struct rcu_state *rsp = arg;
2171 	struct rcu_node *rnp = rcu_get_root(rsp);
2172 
2173 	rcu_bind_gp_kthread();
2174 	for (;;) {
2175 
2176 		/* Handle grace-period start. */
2177 		for (;;) {
2178 			trace_rcu_grace_period(rsp->name,
2179 					       READ_ONCE(rsp->gpnum),
2180 					       TPS("reqwait"));
2181 			rsp->gp_state = RCU_GP_WAIT_GPS;
2182 			swait_event_interruptible(rsp->gp_wq,
2183 						 READ_ONCE(rsp->gp_flags) &
2184 						 RCU_GP_FLAG_INIT);
2185 			rsp->gp_state = RCU_GP_DONE_GPS;
2186 			/* Locking provides needed memory barrier. */
2187 			if (rcu_gp_init(rsp))
2188 				break;
2189 			cond_resched_rcu_qs();
2190 			WRITE_ONCE(rsp->gp_activity, jiffies);
2191 			WARN_ON(signal_pending(current));
2192 			trace_rcu_grace_period(rsp->name,
2193 					       READ_ONCE(rsp->gpnum),
2194 					       TPS("reqwaitsig"));
2195 		}
2196 
2197 		/* Handle quiescent-state forcing. */
2198 		first_gp_fqs = true;
2199 		j = jiffies_till_first_fqs;
2200 		if (j > HZ) {
2201 			j = HZ;
2202 			jiffies_till_first_fqs = HZ;
2203 		}
2204 		ret = 0;
2205 		for (;;) {
2206 			if (!ret) {
2207 				rsp->jiffies_force_qs = jiffies + j;
2208 				WRITE_ONCE(rsp->jiffies_kick_kthreads,
2209 					   jiffies + 3 * j);
2210 			}
2211 			trace_rcu_grace_period(rsp->name,
2212 					       READ_ONCE(rsp->gpnum),
2213 					       TPS("fqswait"));
2214 			rsp->gp_state = RCU_GP_WAIT_FQS;
2215 			ret = swait_event_interruptible_timeout(rsp->gp_wq,
2216 					rcu_gp_fqs_check_wake(rsp, &gf), j);
2217 			rsp->gp_state = RCU_GP_DOING_FQS;
2218 			/* Locking provides needed memory barriers. */
2219 			/* If grace period done, leave loop. */
2220 			if (!READ_ONCE(rnp->qsmask) &&
2221 			    !rcu_preempt_blocked_readers_cgp(rnp))
2222 				break;
2223 			/* If time for quiescent-state forcing, do it. */
2224 			if (ULONG_CMP_GE(jiffies, rsp->jiffies_force_qs) ||
2225 			    (gf & RCU_GP_FLAG_FQS)) {
2226 				trace_rcu_grace_period(rsp->name,
2227 						       READ_ONCE(rsp->gpnum),
2228 						       TPS("fqsstart"));
2229 				rcu_gp_fqs(rsp, first_gp_fqs);
2230 				first_gp_fqs = false;
2231 				trace_rcu_grace_period(rsp->name,
2232 						       READ_ONCE(rsp->gpnum),
2233 						       TPS("fqsend"));
2234 				cond_resched_rcu_qs();
2235 				WRITE_ONCE(rsp->gp_activity, jiffies);
2236 				ret = 0; /* Force full wait till next FQS. */
2237 				j = jiffies_till_next_fqs;
2238 				if (j > HZ) {
2239 					j = HZ;
2240 					jiffies_till_next_fqs = HZ;
2241 				} else if (j < 1) {
2242 					j = 1;
2243 					jiffies_till_next_fqs = 1;
2244 				}
2245 			} else {
2246 				/* Deal with stray signal. */
2247 				cond_resched_rcu_qs();
2248 				WRITE_ONCE(rsp->gp_activity, jiffies);
2249 				WARN_ON(signal_pending(current));
2250 				trace_rcu_grace_period(rsp->name,
2251 						       READ_ONCE(rsp->gpnum),
2252 						       TPS("fqswaitsig"));
2253 				ret = 1; /* Keep old FQS timing. */
2254 				j = jiffies;
2255 				if (time_after(jiffies, rsp->jiffies_force_qs))
2256 					j = 1;
2257 				else
2258 					j = rsp->jiffies_force_qs - j;
2259 			}
2260 		}
2261 
2262 		/* Handle grace-period end. */
2263 		rsp->gp_state = RCU_GP_CLEANUP;
2264 		rcu_gp_cleanup(rsp);
2265 		rsp->gp_state = RCU_GP_CLEANED;
2266 	}
2267 }
2268 
2269 /*
2270  * Start a new RCU grace period if warranted, re-initializing the hierarchy
2271  * in preparation for detecting the next grace period.  The caller must hold
2272  * the root node's ->lock and hard irqs must be disabled.
2273  *
2274  * Note that it is legal for a dying CPU (which is marked as offline) to
2275  * invoke this function.  This can happen when the dying CPU reports its
2276  * quiescent state.
2277  *
2278  * Returns true if the grace-period kthread must be awakened.
2279  */
2280 static bool
2281 rcu_start_gp_advanced(struct rcu_state *rsp, struct rcu_node *rnp,
2282 		      struct rcu_data *rdp)
2283 {
2284 	if (!rsp->gp_kthread || !cpu_needs_another_gp(rsp, rdp)) {
2285 		/*
2286 		 * Either we have not yet spawned the grace-period
2287 		 * task, this CPU does not need another grace period,
2288 		 * or a grace period is already in progress.
2289 		 * Either way, don't start a new grace period.
2290 		 */
2291 		return false;
2292 	}
2293 	WRITE_ONCE(rsp->gp_flags, RCU_GP_FLAG_INIT);
2294 	trace_rcu_grace_period(rsp->name, READ_ONCE(rsp->gpnum),
2295 			       TPS("newreq"));
2296 
2297 	/*
2298 	 * We can't do wakeups while holding the rnp->lock, as that
2299 	 * could cause possible deadlocks with the rq->lock. Defer
2300 	 * the wakeup to our caller.
2301 	 */
2302 	return true;
2303 }
2304 
2305 /*
2306  * Similar to rcu_start_gp_advanced(), but also advance the calling CPU's
2307  * callbacks.  Note that rcu_start_gp_advanced() cannot do this because it
2308  * is invoked indirectly from rcu_advance_cbs(), which would result in
2309  * endless recursion -- or would do so if it wasn't for the self-deadlock
2310  * that is encountered beforehand.
2311  *
2312  * Returns true if the grace-period kthread needs to be awakened.
2313  */
2314 static bool rcu_start_gp(struct rcu_state *rsp)
2315 {
2316 	struct rcu_data *rdp = this_cpu_ptr(rsp->rda);
2317 	struct rcu_node *rnp = rcu_get_root(rsp);
2318 	bool ret = false;
2319 
2320 	/*
2321 	 * If there is no grace period in progress right now, any
2322 	 * callbacks we have up to this point will be satisfied by the
2323 	 * next grace period.  Also, advancing the callbacks reduces the
2324 	 * probability of false positives from cpu_needs_another_gp()
2325 	 * resulting in pointless grace periods.  So, advance callbacks
2326 	 * then start the grace period!
2327 	 */
2328 	ret = rcu_advance_cbs(rsp, rnp, rdp) || ret;
2329 	ret = rcu_start_gp_advanced(rsp, rnp, rdp) || ret;
2330 	return ret;
2331 }
2332 
2333 /*
2334  * Report a full set of quiescent states to the specified rcu_state data
2335  * structure.  Invoke rcu_gp_kthread_wake() to awaken the grace-period
2336  * kthread if another grace period is required.  Whether we wake
2337  * the grace-period kthread or it awakens itself for the next round
2338  * of quiescent-state forcing, that kthread will clean up after the
2339  * just-completed grace period.  Note that the caller must hold rnp->lock,
2340  * which is released before return.
2341  */
2342 static void rcu_report_qs_rsp(struct rcu_state *rsp, unsigned long flags)
2343 	__releases(rcu_get_root(rsp)->lock)
2344 {
2345 	WARN_ON_ONCE(!rcu_gp_in_progress(rsp));
2346 	WRITE_ONCE(rsp->gp_flags, READ_ONCE(rsp->gp_flags) | RCU_GP_FLAG_FQS);
2347 	raw_spin_unlock_irqrestore_rcu_node(rcu_get_root(rsp), flags);
2348 	rcu_gp_kthread_wake(rsp);
2349 }
2350 
2351 /*
2352  * Similar to rcu_report_qs_rdp(), for which it is a helper function.
2353  * Allows quiescent states for a group of CPUs to be reported at one go
2354  * to the specified rcu_node structure, though all the CPUs in the group
2355  * must be represented by the same rcu_node structure (which need not be a
2356  * leaf rcu_node structure, though it often will be).  The gps parameter
2357  * is the grace-period snapshot, which means that the quiescent states
2358  * are valid only if rnp->gpnum is equal to gps.  That structure's lock
2359  * must be held upon entry, and it is released before return.
2360  */
2361 static void
2362 rcu_report_qs_rnp(unsigned long mask, struct rcu_state *rsp,
2363 		  struct rcu_node *rnp, unsigned long gps, unsigned long flags)
2364 	__releases(rnp->lock)
2365 {
2366 	unsigned long oldmask = 0;
2367 	struct rcu_node *rnp_c;
2368 
2369 	/* Walk up the rcu_node hierarchy. */
2370 	for (;;) {
2371 		if (!(rnp->qsmask & mask) || rnp->gpnum != gps) {
2372 
2373 			/*
2374 			 * Our bit has already been cleared, or the
2375 			 * relevant grace period is already over, so done.
2376 			 */
2377 			raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
2378 			return;
2379 		}
2380 		WARN_ON_ONCE(oldmask); /* Any child must be all zeroed! */
2381 		rnp->qsmask &= ~mask;
2382 		trace_rcu_quiescent_state_report(rsp->name, rnp->gpnum,
2383 						 mask, rnp->qsmask, rnp->level,
2384 						 rnp->grplo, rnp->grphi,
2385 						 !!rnp->gp_tasks);
2386 		if (rnp->qsmask != 0 || rcu_preempt_blocked_readers_cgp(rnp)) {
2387 
2388 			/* Other bits still set at this level, so done. */
2389 			raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
2390 			return;
2391 		}
2392 		mask = rnp->grpmask;
2393 		if (rnp->parent == NULL) {
2394 
2395 			/* No more levels.  Exit loop holding root lock. */
2396 
2397 			break;
2398 		}
2399 		raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
2400 		rnp_c = rnp;
2401 		rnp = rnp->parent;
2402 		raw_spin_lock_irqsave_rcu_node(rnp, flags);
2403 		oldmask = rnp_c->qsmask;
2404 	}
2405 
2406 	/*
2407 	 * Get here if we are the last CPU to pass through a quiescent
2408 	 * state for this grace period.  Invoke rcu_report_qs_rsp()
2409 	 * to clean up and start the next grace period if one is needed.
2410 	 */
2411 	rcu_report_qs_rsp(rsp, flags); /* releases rnp->lock. */
2412 }
2413 
2414 /*
2415  * Record a quiescent state for all tasks that were previously queued
2416  * on the specified rcu_node structure and that were blocking the current
2417  * RCU grace period.  The caller must hold the specified rnp->lock with
2418  * irqs disabled, and this lock is released upon return, but irqs remain
2419  * disabled.
2420  */
2421 static void rcu_report_unblock_qs_rnp(struct rcu_state *rsp,
2422 				      struct rcu_node *rnp, unsigned long flags)
2423 	__releases(rnp->lock)
2424 {
2425 	unsigned long gps;
2426 	unsigned long mask;
2427 	struct rcu_node *rnp_p;
2428 
2429 	if (rcu_state_p == &rcu_sched_state || rsp != rcu_state_p ||
2430 	    rnp->qsmask != 0 || rcu_preempt_blocked_readers_cgp(rnp)) {
2431 		raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
2432 		return;  /* Still need more quiescent states! */
2433 	}
2434 
2435 	rnp_p = rnp->parent;
2436 	if (rnp_p == NULL) {
2437 		/*
2438 		 * Only one rcu_node structure in the tree, so don't
2439 		 * try to report up to its nonexistent parent!
2440 		 */
2441 		rcu_report_qs_rsp(rsp, flags);
2442 		return;
2443 	}
2444 
2445 	/* Report up the rest of the hierarchy, tracking current ->gpnum. */
2446 	gps = rnp->gpnum;
2447 	mask = rnp->grpmask;
2448 	raw_spin_unlock_rcu_node(rnp);	/* irqs remain disabled. */
2449 	raw_spin_lock_rcu_node(rnp_p);	/* irqs already disabled. */
2450 	rcu_report_qs_rnp(mask, rsp, rnp_p, gps, flags);
2451 }
2452 
2453 /*
2454  * Record a quiescent state for the specified CPU to that CPU's rcu_data
2455  * structure.  This must be called from the specified CPU.
2456  */
2457 static void
2458 rcu_report_qs_rdp(int cpu, struct rcu_state *rsp, struct rcu_data *rdp)
2459 {
2460 	unsigned long flags;
2461 	unsigned long mask;
2462 	bool needwake;
2463 	struct rcu_node *rnp;
2464 
2465 	rnp = rdp->mynode;
2466 	raw_spin_lock_irqsave_rcu_node(rnp, flags);
2467 	if ((rdp->cpu_no_qs.b.norm &&
2468 	     rdp->rcu_qs_ctr_snap == __this_cpu_read(rcu_qs_ctr)) ||
2469 	    rdp->gpnum != rnp->gpnum || rnp->completed == rnp->gpnum ||
2470 	    rdp->gpwrap) {
2471 
2472 		/*
2473 		 * The grace period in which this quiescent state was
2474 		 * recorded has ended, so don't report it upwards.
2475 		 * We will instead need a new quiescent state that lies
2476 		 * within the current grace period.
2477 		 */
2478 		rdp->cpu_no_qs.b.norm = true;	/* need qs for new gp. */
2479 		rdp->rcu_qs_ctr_snap = __this_cpu_read(rcu_qs_ctr);
2480 		raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
2481 		return;
2482 	}
2483 	mask = rdp->grpmask;
2484 	if ((rnp->qsmask & mask) == 0) {
2485 		raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
2486 	} else {
2487 		rdp->core_needs_qs = false;
2488 
2489 		/*
2490 		 * This GP can't end until cpu checks in, so all of our
2491 		 * callbacks can be processed during the next GP.
2492 		 */
2493 		needwake = rcu_accelerate_cbs(rsp, rnp, rdp);
2494 
2495 		rcu_report_qs_rnp(mask, rsp, rnp, rnp->gpnum, flags);
2496 		/* ^^^ Released rnp->lock */
2497 		if (needwake)
2498 			rcu_gp_kthread_wake(rsp);
2499 	}
2500 }
2501 
2502 /*
2503  * Check to see if there is a new grace period of which this CPU
2504  * is not yet aware, and if so, set up local rcu_data state for it.
2505  * Otherwise, see if this CPU has just passed through its first
2506  * quiescent state for this grace period, and record that fact if so.
2507  */
2508 static void
2509 rcu_check_quiescent_state(struct rcu_state *rsp, struct rcu_data *rdp)
2510 {
2511 	/* Check for grace-period ends and beginnings. */
2512 	note_gp_changes(rsp, rdp);
2513 
2514 	/*
2515 	 * Does this CPU still need to do its part for current grace period?
2516 	 * If no, return and let the other CPUs do their part as well.
2517 	 */
2518 	if (!rdp->core_needs_qs)
2519 		return;
2520 
2521 	/*
2522 	 * Was there a quiescent state since the beginning of the grace
2523 	 * period? If no, then exit and wait for the next call.
2524 	 */
2525 	if (rdp->cpu_no_qs.b.norm &&
2526 	    rdp->rcu_qs_ctr_snap == __this_cpu_read(rcu_qs_ctr))
2527 		return;
2528 
2529 	/*
2530 	 * Tell RCU we are done (but rcu_report_qs_rdp() will be the
2531 	 * judge of that).
2532 	 */
2533 	rcu_report_qs_rdp(rdp->cpu, rsp, rdp);
2534 }
2535 
2536 /*
2537  * Send the specified CPU's RCU callbacks to the orphanage.  The
2538  * specified CPU must be offline, and the caller must hold the
2539  * ->orphan_lock.
2540  */
2541 static void
2542 rcu_send_cbs_to_orphanage(int cpu, struct rcu_state *rsp,
2543 			  struct rcu_node *rnp, struct rcu_data *rdp)
2544 {
2545 	/* No-CBs CPUs do not have orphanable callbacks. */
2546 	if (!IS_ENABLED(CONFIG_HOTPLUG_CPU) || rcu_is_nocb_cpu(rdp->cpu))
2547 		return;
2548 
2549 	/*
2550 	 * Orphan the callbacks.  First adjust the counts.  This is safe
2551 	 * because _rcu_barrier() excludes CPU-hotplug operations, so it
2552 	 * cannot be running now.  Thus no memory barrier is required.
2553 	 */
2554 	if (rdp->nxtlist != NULL) {
2555 		rsp->qlen_lazy += rdp->qlen_lazy;
2556 		rsp->qlen += rdp->qlen;
2557 		rdp->n_cbs_orphaned += rdp->qlen;
2558 		rdp->qlen_lazy = 0;
2559 		WRITE_ONCE(rdp->qlen, 0);
2560 	}
2561 
2562 	/*
2563 	 * Next, move those callbacks still needing a grace period to
2564 	 * the orphanage, where some other CPU will pick them up.
2565 	 * Some of the callbacks might have gone partway through a grace
2566 	 * period, but that is too bad.  They get to start over because we
2567 	 * cannot assume that grace periods are synchronized across CPUs.
2568 	 * We don't bother updating the ->nxttail[] array yet, instead
2569 	 * we just reset the whole thing later on.
2570 	 */
2571 	if (*rdp->nxttail[RCU_DONE_TAIL] != NULL) {
2572 		*rsp->orphan_nxttail = *rdp->nxttail[RCU_DONE_TAIL];
2573 		rsp->orphan_nxttail = rdp->nxttail[RCU_NEXT_TAIL];
2574 		*rdp->nxttail[RCU_DONE_TAIL] = NULL;
2575 	}
2576 
2577 	/*
2578 	 * Then move the ready-to-invoke callbacks to the orphanage,
2579 	 * where some other CPU will pick them up.  These will not be
2580 	 * required to pass though another grace period: They are done.
2581 	 */
2582 	if (rdp->nxtlist != NULL) {
2583 		*rsp->orphan_donetail = rdp->nxtlist;
2584 		rsp->orphan_donetail = rdp->nxttail[RCU_DONE_TAIL];
2585 	}
2586 
2587 	/*
2588 	 * Finally, initialize the rcu_data structure's list to empty and
2589 	 * disallow further callbacks on this CPU.
2590 	 */
2591 	init_callback_list(rdp);
2592 	rdp->nxttail[RCU_NEXT_TAIL] = NULL;
2593 }
2594 
2595 /*
2596  * Adopt the RCU callbacks from the specified rcu_state structure's
2597  * orphanage.  The caller must hold the ->orphan_lock.
2598  */
2599 static void rcu_adopt_orphan_cbs(struct rcu_state *rsp, unsigned long flags)
2600 {
2601 	int i;
2602 	struct rcu_data *rdp = raw_cpu_ptr(rsp->rda);
2603 
2604 	/* No-CBs CPUs are handled specially. */
2605 	if (!IS_ENABLED(CONFIG_HOTPLUG_CPU) ||
2606 	    rcu_nocb_adopt_orphan_cbs(rsp, rdp, flags))
2607 		return;
2608 
2609 	/* Do the accounting first. */
2610 	rdp->qlen_lazy += rsp->qlen_lazy;
2611 	rdp->qlen += rsp->qlen;
2612 	rdp->n_cbs_adopted += rsp->qlen;
2613 	if (rsp->qlen_lazy != rsp->qlen)
2614 		rcu_idle_count_callbacks_posted();
2615 	rsp->qlen_lazy = 0;
2616 	rsp->qlen = 0;
2617 
2618 	/*
2619 	 * We do not need a memory barrier here because the only way we
2620 	 * can get here if there is an rcu_barrier() in flight is if
2621 	 * we are the task doing the rcu_barrier().
2622 	 */
2623 
2624 	/* First adopt the ready-to-invoke callbacks. */
2625 	if (rsp->orphan_donelist != NULL) {
2626 		*rsp->orphan_donetail = *rdp->nxttail[RCU_DONE_TAIL];
2627 		*rdp->nxttail[RCU_DONE_TAIL] = rsp->orphan_donelist;
2628 		for (i = RCU_NEXT_SIZE - 1; i >= RCU_DONE_TAIL; i--)
2629 			if (rdp->nxttail[i] == rdp->nxttail[RCU_DONE_TAIL])
2630 				rdp->nxttail[i] = rsp->orphan_donetail;
2631 		rsp->orphan_donelist = NULL;
2632 		rsp->orphan_donetail = &rsp->orphan_donelist;
2633 	}
2634 
2635 	/* And then adopt the callbacks that still need a grace period. */
2636 	if (rsp->orphan_nxtlist != NULL) {
2637 		*rdp->nxttail[RCU_NEXT_TAIL] = rsp->orphan_nxtlist;
2638 		rdp->nxttail[RCU_NEXT_TAIL] = rsp->orphan_nxttail;
2639 		rsp->orphan_nxtlist = NULL;
2640 		rsp->orphan_nxttail = &rsp->orphan_nxtlist;
2641 	}
2642 }
2643 
2644 /*
2645  * Trace the fact that this CPU is going offline.
2646  */
2647 static void rcu_cleanup_dying_cpu(struct rcu_state *rsp)
2648 {
2649 	RCU_TRACE(unsigned long mask);
2650 	RCU_TRACE(struct rcu_data *rdp = this_cpu_ptr(rsp->rda));
2651 	RCU_TRACE(struct rcu_node *rnp = rdp->mynode);
2652 
2653 	if (!IS_ENABLED(CONFIG_HOTPLUG_CPU))
2654 		return;
2655 
2656 	RCU_TRACE(mask = rdp->grpmask);
2657 	trace_rcu_grace_period(rsp->name,
2658 			       rnp->gpnum + 1 - !!(rnp->qsmask & mask),
2659 			       TPS("cpuofl"));
2660 }
2661 
2662 /*
2663  * All CPUs for the specified rcu_node structure have gone offline,
2664  * and all tasks that were preempted within an RCU read-side critical
2665  * section while running on one of those CPUs have since exited their RCU
2666  * read-side critical section.  Some other CPU is reporting this fact with
2667  * the specified rcu_node structure's ->lock held and interrupts disabled.
2668  * This function therefore goes up the tree of rcu_node structures,
2669  * clearing the corresponding bits in the ->qsmaskinit fields.  Note that
2670  * the leaf rcu_node structure's ->qsmaskinit field has already been
2671  * updated
2672  *
2673  * This function does check that the specified rcu_node structure has
2674  * all CPUs offline and no blocked tasks, so it is OK to invoke it
2675  * prematurely.  That said, invoking it after the fact will cost you
2676  * a needless lock acquisition.  So once it has done its work, don't
2677  * invoke it again.
2678  */
2679 static void rcu_cleanup_dead_rnp(struct rcu_node *rnp_leaf)
2680 {
2681 	long mask;
2682 	struct rcu_node *rnp = rnp_leaf;
2683 
2684 	if (!IS_ENABLED(CONFIG_HOTPLUG_CPU) ||
2685 	    rnp->qsmaskinit || rcu_preempt_has_tasks(rnp))
2686 		return;
2687 	for (;;) {
2688 		mask = rnp->grpmask;
2689 		rnp = rnp->parent;
2690 		if (!rnp)
2691 			break;
2692 		raw_spin_lock_rcu_node(rnp); /* irqs already disabled. */
2693 		rnp->qsmaskinit &= ~mask;
2694 		rnp->qsmask &= ~mask;
2695 		if (rnp->qsmaskinit) {
2696 			raw_spin_unlock_rcu_node(rnp);
2697 			/* irqs remain disabled. */
2698 			return;
2699 		}
2700 		raw_spin_unlock_rcu_node(rnp); /* irqs remain disabled. */
2701 	}
2702 }
2703 
2704 /*
2705  * The CPU has been completely removed, and some other CPU is reporting
2706  * this fact from process context.  Do the remainder of the cleanup,
2707  * including orphaning the outgoing CPU's RCU callbacks, and also
2708  * adopting them.  There can only be one CPU hotplug operation at a time,
2709  * so no other CPU can be attempting to update rcu_cpu_kthread_task.
2710  */
2711 static void rcu_cleanup_dead_cpu(int cpu, struct rcu_state *rsp)
2712 {
2713 	unsigned long flags;
2714 	struct rcu_data *rdp = per_cpu_ptr(rsp->rda, cpu);
2715 	struct rcu_node *rnp = rdp->mynode;  /* Outgoing CPU's rdp & rnp. */
2716 
2717 	if (!IS_ENABLED(CONFIG_HOTPLUG_CPU))
2718 		return;
2719 
2720 	/* Adjust any no-longer-needed kthreads. */
2721 	rcu_boost_kthread_setaffinity(rnp, -1);
2722 
2723 	/* Orphan the dead CPU's callbacks, and adopt them if appropriate. */
2724 	raw_spin_lock_irqsave(&rsp->orphan_lock, flags);
2725 	rcu_send_cbs_to_orphanage(cpu, rsp, rnp, rdp);
2726 	rcu_adopt_orphan_cbs(rsp, flags);
2727 	raw_spin_unlock_irqrestore(&rsp->orphan_lock, flags);
2728 
2729 	WARN_ONCE(rdp->qlen != 0 || rdp->nxtlist != NULL,
2730 		  "rcu_cleanup_dead_cpu: Callbacks on offline CPU %d: qlen=%lu, nxtlist=%p\n",
2731 		  cpu, rdp->qlen, rdp->nxtlist);
2732 }
2733 
2734 /*
2735  * Invoke any RCU callbacks that have made it to the end of their grace
2736  * period.  Thottle as specified by rdp->blimit.
2737  */
2738 static void rcu_do_batch(struct rcu_state *rsp, struct rcu_data *rdp)
2739 {
2740 	unsigned long flags;
2741 	struct rcu_head *next, *list, **tail;
2742 	long bl, count, count_lazy;
2743 	int i;
2744 
2745 	/* If no callbacks are ready, just return. */
2746 	if (!cpu_has_callbacks_ready_to_invoke(rdp)) {
2747 		trace_rcu_batch_start(rsp->name, rdp->qlen_lazy, rdp->qlen, 0);
2748 		trace_rcu_batch_end(rsp->name, 0, !!READ_ONCE(rdp->nxtlist),
2749 				    need_resched(), is_idle_task(current),
2750 				    rcu_is_callbacks_kthread());
2751 		return;
2752 	}
2753 
2754 	/*
2755 	 * Extract the list of ready callbacks, disabling to prevent
2756 	 * races with call_rcu() from interrupt handlers.
2757 	 */
2758 	local_irq_save(flags);
2759 	WARN_ON_ONCE(cpu_is_offline(smp_processor_id()));
2760 	bl = rdp->blimit;
2761 	trace_rcu_batch_start(rsp->name, rdp->qlen_lazy, rdp->qlen, bl);
2762 	list = rdp->nxtlist;
2763 	rdp->nxtlist = *rdp->nxttail[RCU_DONE_TAIL];
2764 	*rdp->nxttail[RCU_DONE_TAIL] = NULL;
2765 	tail = rdp->nxttail[RCU_DONE_TAIL];
2766 	for (i = RCU_NEXT_SIZE - 1; i >= 0; i--)
2767 		if (rdp->nxttail[i] == rdp->nxttail[RCU_DONE_TAIL])
2768 			rdp->nxttail[i] = &rdp->nxtlist;
2769 	local_irq_restore(flags);
2770 
2771 	/* Invoke callbacks. */
2772 	count = count_lazy = 0;
2773 	while (list) {
2774 		next = list->next;
2775 		prefetch(next);
2776 		debug_rcu_head_unqueue(list);
2777 		if (__rcu_reclaim(rsp->name, list))
2778 			count_lazy++;
2779 		list = next;
2780 		/* Stop only if limit reached and CPU has something to do. */
2781 		if (++count >= bl &&
2782 		    (need_resched() ||
2783 		     (!is_idle_task(current) && !rcu_is_callbacks_kthread())))
2784 			break;
2785 	}
2786 
2787 	local_irq_save(flags);
2788 	trace_rcu_batch_end(rsp->name, count, !!list, need_resched(),
2789 			    is_idle_task(current),
2790 			    rcu_is_callbacks_kthread());
2791 
2792 	/* Update count, and requeue any remaining callbacks. */
2793 	if (list != NULL) {
2794 		*tail = rdp->nxtlist;
2795 		rdp->nxtlist = list;
2796 		for (i = 0; i < RCU_NEXT_SIZE; i++)
2797 			if (&rdp->nxtlist == rdp->nxttail[i])
2798 				rdp->nxttail[i] = tail;
2799 			else
2800 				break;
2801 	}
2802 	smp_mb(); /* List handling before counting for rcu_barrier(). */
2803 	rdp->qlen_lazy -= count_lazy;
2804 	WRITE_ONCE(rdp->qlen, rdp->qlen - count);
2805 	rdp->n_cbs_invoked += count;
2806 
2807 	/* Reinstate batch limit if we have worked down the excess. */
2808 	if (rdp->blimit == LONG_MAX && rdp->qlen <= qlowmark)
2809 		rdp->blimit = blimit;
2810 
2811 	/* Reset ->qlen_last_fqs_check trigger if enough CBs have drained. */
2812 	if (rdp->qlen == 0 && rdp->qlen_last_fqs_check != 0) {
2813 		rdp->qlen_last_fqs_check = 0;
2814 		rdp->n_force_qs_snap = rsp->n_force_qs;
2815 	} else if (rdp->qlen < rdp->qlen_last_fqs_check - qhimark)
2816 		rdp->qlen_last_fqs_check = rdp->qlen;
2817 	WARN_ON_ONCE((rdp->nxtlist == NULL) != (rdp->qlen == 0));
2818 
2819 	local_irq_restore(flags);
2820 
2821 	/* Re-invoke RCU core processing if there are callbacks remaining. */
2822 	if (cpu_has_callbacks_ready_to_invoke(rdp))
2823 		invoke_rcu_core();
2824 }
2825 
2826 /*
2827  * Check to see if this CPU is in a non-context-switch quiescent state
2828  * (user mode or idle loop for rcu, non-softirq execution for rcu_bh).
2829  * Also schedule RCU core processing.
2830  *
2831  * This function must be called from hardirq context.  It is normally
2832  * invoked from the scheduling-clock interrupt.
2833  */
2834 void rcu_check_callbacks(int user)
2835 {
2836 	trace_rcu_utilization(TPS("Start scheduler-tick"));
2837 	increment_cpu_stall_ticks();
2838 	if (user || rcu_is_cpu_rrupt_from_idle()) {
2839 
2840 		/*
2841 		 * Get here if this CPU took its interrupt from user
2842 		 * mode or from the idle loop, and if this is not a
2843 		 * nested interrupt.  In this case, the CPU is in
2844 		 * a quiescent state, so note it.
2845 		 *
2846 		 * No memory barrier is required here because both
2847 		 * rcu_sched_qs() and rcu_bh_qs() reference only CPU-local
2848 		 * variables that other CPUs neither access nor modify,
2849 		 * at least not while the corresponding CPU is online.
2850 		 */
2851 
2852 		rcu_sched_qs();
2853 		rcu_bh_qs();
2854 
2855 	} else if (!in_softirq()) {
2856 
2857 		/*
2858 		 * Get here if this CPU did not take its interrupt from
2859 		 * softirq, in other words, if it is not interrupting
2860 		 * a rcu_bh read-side critical section.  This is an _bh
2861 		 * critical section, so note it.
2862 		 */
2863 
2864 		rcu_bh_qs();
2865 	}
2866 	rcu_preempt_check_callbacks();
2867 	if (rcu_pending())
2868 		invoke_rcu_core();
2869 	if (user)
2870 		rcu_note_voluntary_context_switch(current);
2871 	trace_rcu_utilization(TPS("End scheduler-tick"));
2872 }
2873 
2874 /*
2875  * Scan the leaf rcu_node structures, processing dyntick state for any that
2876  * have not yet encountered a quiescent state, using the function specified.
2877  * Also initiate boosting for any threads blocked on the root rcu_node.
2878  *
2879  * The caller must have suppressed start of new grace periods.
2880  */
2881 static void force_qs_rnp(struct rcu_state *rsp,
2882 			 int (*f)(struct rcu_data *rsp, bool *isidle,
2883 				  unsigned long *maxj),
2884 			 bool *isidle, unsigned long *maxj)
2885 {
2886 	int cpu;
2887 	unsigned long flags;
2888 	unsigned long mask;
2889 	struct rcu_node *rnp;
2890 
2891 	rcu_for_each_leaf_node(rsp, rnp) {
2892 		cond_resched_rcu_qs();
2893 		mask = 0;
2894 		raw_spin_lock_irqsave_rcu_node(rnp, flags);
2895 		if (rnp->qsmask == 0) {
2896 			if (rcu_state_p == &rcu_sched_state ||
2897 			    rsp != rcu_state_p ||
2898 			    rcu_preempt_blocked_readers_cgp(rnp)) {
2899 				/*
2900 				 * No point in scanning bits because they
2901 				 * are all zero.  But we might need to
2902 				 * priority-boost blocked readers.
2903 				 */
2904 				rcu_initiate_boost(rnp, flags);
2905 				/* rcu_initiate_boost() releases rnp->lock */
2906 				continue;
2907 			}
2908 			if (rnp->parent &&
2909 			    (rnp->parent->qsmask & rnp->grpmask)) {
2910 				/*
2911 				 * Race between grace-period
2912 				 * initialization and task exiting RCU
2913 				 * read-side critical section: Report.
2914 				 */
2915 				rcu_report_unblock_qs_rnp(rsp, rnp, flags);
2916 				/* rcu_report_unblock_qs_rnp() rlses ->lock */
2917 				continue;
2918 			}
2919 		}
2920 		for_each_leaf_node_possible_cpu(rnp, cpu) {
2921 			unsigned long bit = leaf_node_cpu_bit(rnp, cpu);
2922 			if ((rnp->qsmask & bit) != 0) {
2923 				if (f(per_cpu_ptr(rsp->rda, cpu), isidle, maxj))
2924 					mask |= bit;
2925 			}
2926 		}
2927 		if (mask != 0) {
2928 			/* Idle/offline CPUs, report (releases rnp->lock. */
2929 			rcu_report_qs_rnp(mask, rsp, rnp, rnp->gpnum, flags);
2930 		} else {
2931 			/* Nothing to do here, so just drop the lock. */
2932 			raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
2933 		}
2934 	}
2935 }
2936 
2937 /*
2938  * Force quiescent states on reluctant CPUs, and also detect which
2939  * CPUs are in dyntick-idle mode.
2940  */
2941 static void force_quiescent_state(struct rcu_state *rsp)
2942 {
2943 	unsigned long flags;
2944 	bool ret;
2945 	struct rcu_node *rnp;
2946 	struct rcu_node *rnp_old = NULL;
2947 
2948 	/* Funnel through hierarchy to reduce memory contention. */
2949 	rnp = __this_cpu_read(rsp->rda->mynode);
2950 	for (; rnp != NULL; rnp = rnp->parent) {
2951 		ret = (READ_ONCE(rsp->gp_flags) & RCU_GP_FLAG_FQS) ||
2952 		      !raw_spin_trylock(&rnp->fqslock);
2953 		if (rnp_old != NULL)
2954 			raw_spin_unlock(&rnp_old->fqslock);
2955 		if (ret) {
2956 			rsp->n_force_qs_lh++;
2957 			return;
2958 		}
2959 		rnp_old = rnp;
2960 	}
2961 	/* rnp_old == rcu_get_root(rsp), rnp == NULL. */
2962 
2963 	/* Reached the root of the rcu_node tree, acquire lock. */
2964 	raw_spin_lock_irqsave_rcu_node(rnp_old, flags);
2965 	raw_spin_unlock(&rnp_old->fqslock);
2966 	if (READ_ONCE(rsp->gp_flags) & RCU_GP_FLAG_FQS) {
2967 		rsp->n_force_qs_lh++;
2968 		raw_spin_unlock_irqrestore_rcu_node(rnp_old, flags);
2969 		return;  /* Someone beat us to it. */
2970 	}
2971 	WRITE_ONCE(rsp->gp_flags, READ_ONCE(rsp->gp_flags) | RCU_GP_FLAG_FQS);
2972 	raw_spin_unlock_irqrestore_rcu_node(rnp_old, flags);
2973 	rcu_gp_kthread_wake(rsp);
2974 }
2975 
2976 /*
2977  * This does the RCU core processing work for the specified rcu_state
2978  * and rcu_data structures.  This may be called only from the CPU to
2979  * whom the rdp belongs.
2980  */
2981 static void
2982 __rcu_process_callbacks(struct rcu_state *rsp)
2983 {
2984 	unsigned long flags;
2985 	bool needwake;
2986 	struct rcu_data *rdp = raw_cpu_ptr(rsp->rda);
2987 
2988 	WARN_ON_ONCE(rdp->beenonline == 0);
2989 
2990 	/* Update RCU state based on any recent quiescent states. */
2991 	rcu_check_quiescent_state(rsp, rdp);
2992 
2993 	/* Does this CPU require a not-yet-started grace period? */
2994 	local_irq_save(flags);
2995 	if (cpu_needs_another_gp(rsp, rdp)) {
2996 		raw_spin_lock_rcu_node(rcu_get_root(rsp)); /* irqs disabled. */
2997 		needwake = rcu_start_gp(rsp);
2998 		raw_spin_unlock_irqrestore_rcu_node(rcu_get_root(rsp), flags);
2999 		if (needwake)
3000 			rcu_gp_kthread_wake(rsp);
3001 	} else {
3002 		local_irq_restore(flags);
3003 	}
3004 
3005 	/* If there are callbacks ready, invoke them. */
3006 	if (cpu_has_callbacks_ready_to_invoke(rdp))
3007 		invoke_rcu_callbacks(rsp, rdp);
3008 
3009 	/* Do any needed deferred wakeups of rcuo kthreads. */
3010 	do_nocb_deferred_wakeup(rdp);
3011 }
3012 
3013 /*
3014  * Do RCU core processing for the current CPU.
3015  */
3016 static __latent_entropy void rcu_process_callbacks(struct softirq_action *unused)
3017 {
3018 	struct rcu_state *rsp;
3019 
3020 	if (cpu_is_offline(smp_processor_id()))
3021 		return;
3022 	trace_rcu_utilization(TPS("Start RCU core"));
3023 	for_each_rcu_flavor(rsp)
3024 		__rcu_process_callbacks(rsp);
3025 	trace_rcu_utilization(TPS("End RCU core"));
3026 }
3027 
3028 /*
3029  * Schedule RCU callback invocation.  If the specified type of RCU
3030  * does not support RCU priority boosting, just do a direct call,
3031  * otherwise wake up the per-CPU kernel kthread.  Note that because we
3032  * are running on the current CPU with softirqs disabled, the
3033  * rcu_cpu_kthread_task cannot disappear out from under us.
3034  */
3035 static void invoke_rcu_callbacks(struct rcu_state *rsp, struct rcu_data *rdp)
3036 {
3037 	if (unlikely(!READ_ONCE(rcu_scheduler_fully_active)))
3038 		return;
3039 	if (likely(!rsp->boost)) {
3040 		rcu_do_batch(rsp, rdp);
3041 		return;
3042 	}
3043 	invoke_rcu_callbacks_kthread();
3044 }
3045 
3046 static void invoke_rcu_core(void)
3047 {
3048 	if (cpu_online(smp_processor_id()))
3049 		raise_softirq(RCU_SOFTIRQ);
3050 }
3051 
3052 /*
3053  * Handle any core-RCU processing required by a call_rcu() invocation.
3054  */
3055 static void __call_rcu_core(struct rcu_state *rsp, struct rcu_data *rdp,
3056 			    struct rcu_head *head, unsigned long flags)
3057 {
3058 	bool needwake;
3059 
3060 	/*
3061 	 * If called from an extended quiescent state, invoke the RCU
3062 	 * core in order to force a re-evaluation of RCU's idleness.
3063 	 */
3064 	if (!rcu_is_watching())
3065 		invoke_rcu_core();
3066 
3067 	/* If interrupts were disabled or CPU offline, don't invoke RCU core. */
3068 	if (irqs_disabled_flags(flags) || cpu_is_offline(smp_processor_id()))
3069 		return;
3070 
3071 	/*
3072 	 * Force the grace period if too many callbacks or too long waiting.
3073 	 * Enforce hysteresis, and don't invoke force_quiescent_state()
3074 	 * if some other CPU has recently done so.  Also, don't bother
3075 	 * invoking force_quiescent_state() if the newly enqueued callback
3076 	 * is the only one waiting for a grace period to complete.
3077 	 */
3078 	if (unlikely(rdp->qlen > rdp->qlen_last_fqs_check + qhimark)) {
3079 
3080 		/* Are we ignoring a completed grace period? */
3081 		note_gp_changes(rsp, rdp);
3082 
3083 		/* Start a new grace period if one not already started. */
3084 		if (!rcu_gp_in_progress(rsp)) {
3085 			struct rcu_node *rnp_root = rcu_get_root(rsp);
3086 
3087 			raw_spin_lock_rcu_node(rnp_root);
3088 			needwake = rcu_start_gp(rsp);
3089 			raw_spin_unlock_rcu_node(rnp_root);
3090 			if (needwake)
3091 				rcu_gp_kthread_wake(rsp);
3092 		} else {
3093 			/* Give the grace period a kick. */
3094 			rdp->blimit = LONG_MAX;
3095 			if (rsp->n_force_qs == rdp->n_force_qs_snap &&
3096 			    *rdp->nxttail[RCU_DONE_TAIL] != head)
3097 				force_quiescent_state(rsp);
3098 			rdp->n_force_qs_snap = rsp->n_force_qs;
3099 			rdp->qlen_last_fqs_check = rdp->qlen;
3100 		}
3101 	}
3102 }
3103 
3104 /*
3105  * RCU callback function to leak a callback.
3106  */
3107 static void rcu_leak_callback(struct rcu_head *rhp)
3108 {
3109 }
3110 
3111 /*
3112  * Helper function for call_rcu() and friends.  The cpu argument will
3113  * normally be -1, indicating "currently running CPU".  It may specify
3114  * a CPU only if that CPU is a no-CBs CPU.  Currently, only _rcu_barrier()
3115  * is expected to specify a CPU.
3116  */
3117 static void
3118 __call_rcu(struct rcu_head *head, rcu_callback_t func,
3119 	   struct rcu_state *rsp, int cpu, bool lazy)
3120 {
3121 	unsigned long flags;
3122 	struct rcu_data *rdp;
3123 
3124 	/* Misaligned rcu_head! */
3125 	WARN_ON_ONCE((unsigned long)head & (sizeof(void *) - 1));
3126 
3127 	if (debug_rcu_head_queue(head)) {
3128 		/* Probable double call_rcu(), so leak the callback. */
3129 		WRITE_ONCE(head->func, rcu_leak_callback);
3130 		WARN_ONCE(1, "__call_rcu(): Leaked duplicate callback\n");
3131 		return;
3132 	}
3133 	head->func = func;
3134 	head->next = NULL;
3135 	local_irq_save(flags);
3136 	rdp = this_cpu_ptr(rsp->rda);
3137 
3138 	/* Add the callback to our list. */
3139 	if (unlikely(rdp->nxttail[RCU_NEXT_TAIL] == NULL) || cpu != -1) {
3140 		int offline;
3141 
3142 		if (cpu != -1)
3143 			rdp = per_cpu_ptr(rsp->rda, cpu);
3144 		if (likely(rdp->mynode)) {
3145 			/* Post-boot, so this should be for a no-CBs CPU. */
3146 			offline = !__call_rcu_nocb(rdp, head, lazy, flags);
3147 			WARN_ON_ONCE(offline);
3148 			/* Offline CPU, _call_rcu() illegal, leak callback.  */
3149 			local_irq_restore(flags);
3150 			return;
3151 		}
3152 		/*
3153 		 * Very early boot, before rcu_init().  Initialize if needed
3154 		 * and then drop through to queue the callback.
3155 		 */
3156 		BUG_ON(cpu != -1);
3157 		WARN_ON_ONCE(!rcu_is_watching());
3158 		if (!likely(rdp->nxtlist))
3159 			init_default_callback_list(rdp);
3160 	}
3161 	WRITE_ONCE(rdp->qlen, rdp->qlen + 1);
3162 	if (lazy)
3163 		rdp->qlen_lazy++;
3164 	else
3165 		rcu_idle_count_callbacks_posted();
3166 	smp_mb();  /* Count before adding callback for rcu_barrier(). */
3167 	*rdp->nxttail[RCU_NEXT_TAIL] = head;
3168 	rdp->nxttail[RCU_NEXT_TAIL] = &head->next;
3169 
3170 	if (__is_kfree_rcu_offset((unsigned long)func))
3171 		trace_rcu_kfree_callback(rsp->name, head, (unsigned long)func,
3172 					 rdp->qlen_lazy, rdp->qlen);
3173 	else
3174 		trace_rcu_callback(rsp->name, head, rdp->qlen_lazy, rdp->qlen);
3175 
3176 	/* Go handle any RCU core processing required. */
3177 	__call_rcu_core(rsp, rdp, head, flags);
3178 	local_irq_restore(flags);
3179 }
3180 
3181 /*
3182  * Queue an RCU-sched callback for invocation after a grace period.
3183  */
3184 void call_rcu_sched(struct rcu_head *head, rcu_callback_t func)
3185 {
3186 	__call_rcu(head, func, &rcu_sched_state, -1, 0);
3187 }
3188 EXPORT_SYMBOL_GPL(call_rcu_sched);
3189 
3190 /*
3191  * Queue an RCU callback for invocation after a quicker grace period.
3192  */
3193 void call_rcu_bh(struct rcu_head *head, rcu_callback_t func)
3194 {
3195 	__call_rcu(head, func, &rcu_bh_state, -1, 0);
3196 }
3197 EXPORT_SYMBOL_GPL(call_rcu_bh);
3198 
3199 /*
3200  * Queue an RCU callback for lazy invocation after a grace period.
3201  * This will likely be later named something like "call_rcu_lazy()",
3202  * but this change will require some way of tagging the lazy RCU
3203  * callbacks in the list of pending callbacks. Until then, this
3204  * function may only be called from __kfree_rcu().
3205  */
3206 void kfree_call_rcu(struct rcu_head *head,
3207 		    rcu_callback_t func)
3208 {
3209 	__call_rcu(head, func, rcu_state_p, -1, 1);
3210 }
3211 EXPORT_SYMBOL_GPL(kfree_call_rcu);
3212 
3213 /*
3214  * Because a context switch is a grace period for RCU-sched and RCU-bh,
3215  * any blocking grace-period wait automatically implies a grace period
3216  * if there is only one CPU online at any point time during execution
3217  * of either synchronize_sched() or synchronize_rcu_bh().  It is OK to
3218  * occasionally incorrectly indicate that there are multiple CPUs online
3219  * when there was in fact only one the whole time, as this just adds
3220  * some overhead: RCU still operates correctly.
3221  */
3222 static inline int rcu_blocking_is_gp(void)
3223 {
3224 	int ret;
3225 
3226 	might_sleep();  /* Check for RCU read-side critical section. */
3227 	preempt_disable();
3228 	ret = num_online_cpus() <= 1;
3229 	preempt_enable();
3230 	return ret;
3231 }
3232 
3233 /**
3234  * synchronize_sched - wait until an rcu-sched grace period has elapsed.
3235  *
3236  * Control will return to the caller some time after a full rcu-sched
3237  * grace period has elapsed, in other words after all currently executing
3238  * rcu-sched read-side critical sections have completed.   These read-side
3239  * critical sections are delimited by rcu_read_lock_sched() and
3240  * rcu_read_unlock_sched(), and may be nested.  Note that preempt_disable(),
3241  * local_irq_disable(), and so on may be used in place of
3242  * rcu_read_lock_sched().
3243  *
3244  * This means that all preempt_disable code sequences, including NMI and
3245  * non-threaded hardware-interrupt handlers, in progress on entry will
3246  * have completed before this primitive returns.  However, this does not
3247  * guarantee that softirq handlers will have completed, since in some
3248  * kernels, these handlers can run in process context, and can block.
3249  *
3250  * Note that this guarantee implies further memory-ordering guarantees.
3251  * On systems with more than one CPU, when synchronize_sched() returns,
3252  * each CPU is guaranteed to have executed a full memory barrier since the
3253  * end of its last RCU-sched read-side critical section whose beginning
3254  * preceded the call to synchronize_sched().  In addition, each CPU having
3255  * an RCU read-side critical section that extends beyond the return from
3256  * synchronize_sched() is guaranteed to have executed a full memory barrier
3257  * after the beginning of synchronize_sched() and before the beginning of
3258  * that RCU read-side critical section.  Note that these guarantees include
3259  * CPUs that are offline, idle, or executing in user mode, as well as CPUs
3260  * that are executing in the kernel.
3261  *
3262  * Furthermore, if CPU A invoked synchronize_sched(), which returned
3263  * to its caller on CPU B, then both CPU A and CPU B are guaranteed
3264  * to have executed a full memory barrier during the execution of
3265  * synchronize_sched() -- even if CPU A and CPU B are the same CPU (but
3266  * again only if the system has more than one CPU).
3267  *
3268  * This primitive provides the guarantees made by the (now removed)
3269  * synchronize_kernel() API.  In contrast, synchronize_rcu() only
3270  * guarantees that rcu_read_lock() sections will have completed.
3271  * In "classic RCU", these two guarantees happen to be one and
3272  * the same, but can differ in realtime RCU implementations.
3273  */
3274 void synchronize_sched(void)
3275 {
3276 	RCU_LOCKDEP_WARN(lock_is_held(&rcu_bh_lock_map) ||
3277 			 lock_is_held(&rcu_lock_map) ||
3278 			 lock_is_held(&rcu_sched_lock_map),
3279 			 "Illegal synchronize_sched() in RCU-sched read-side critical section");
3280 	if (rcu_blocking_is_gp())
3281 		return;
3282 	if (rcu_gp_is_expedited())
3283 		synchronize_sched_expedited();
3284 	else
3285 		wait_rcu_gp(call_rcu_sched);
3286 }
3287 EXPORT_SYMBOL_GPL(synchronize_sched);
3288 
3289 /**
3290  * synchronize_rcu_bh - wait until an rcu_bh grace period has elapsed.
3291  *
3292  * Control will return to the caller some time after a full rcu_bh grace
3293  * period has elapsed, in other words after all currently executing rcu_bh
3294  * read-side critical sections have completed.  RCU read-side critical
3295  * sections are delimited by rcu_read_lock_bh() and rcu_read_unlock_bh(),
3296  * and may be nested.
3297  *
3298  * See the description of synchronize_sched() for more detailed information
3299  * on memory ordering guarantees.
3300  */
3301 void synchronize_rcu_bh(void)
3302 {
3303 	RCU_LOCKDEP_WARN(lock_is_held(&rcu_bh_lock_map) ||
3304 			 lock_is_held(&rcu_lock_map) ||
3305 			 lock_is_held(&rcu_sched_lock_map),
3306 			 "Illegal synchronize_rcu_bh() in RCU-bh read-side critical section");
3307 	if (rcu_blocking_is_gp())
3308 		return;
3309 	if (rcu_gp_is_expedited())
3310 		synchronize_rcu_bh_expedited();
3311 	else
3312 		wait_rcu_gp(call_rcu_bh);
3313 }
3314 EXPORT_SYMBOL_GPL(synchronize_rcu_bh);
3315 
3316 /**
3317  * get_state_synchronize_rcu - Snapshot current RCU state
3318  *
3319  * Returns a cookie that is used by a later call to cond_synchronize_rcu()
3320  * to determine whether or not a full grace period has elapsed in the
3321  * meantime.
3322  */
3323 unsigned long get_state_synchronize_rcu(void)
3324 {
3325 	/*
3326 	 * Any prior manipulation of RCU-protected data must happen
3327 	 * before the load from ->gpnum.
3328 	 */
3329 	smp_mb();  /* ^^^ */
3330 
3331 	/*
3332 	 * Make sure this load happens before the purportedly
3333 	 * time-consuming work between get_state_synchronize_rcu()
3334 	 * and cond_synchronize_rcu().
3335 	 */
3336 	return smp_load_acquire(&rcu_state_p->gpnum);
3337 }
3338 EXPORT_SYMBOL_GPL(get_state_synchronize_rcu);
3339 
3340 /**
3341  * cond_synchronize_rcu - Conditionally wait for an RCU grace period
3342  *
3343  * @oldstate: return value from earlier call to get_state_synchronize_rcu()
3344  *
3345  * If a full RCU grace period has elapsed since the earlier call to
3346  * get_state_synchronize_rcu(), just return.  Otherwise, invoke
3347  * synchronize_rcu() to wait for a full grace period.
3348  *
3349  * Yes, this function does not take counter wrap into account.  But
3350  * counter wrap is harmless.  If the counter wraps, we have waited for
3351  * more than 2 billion grace periods (and way more on a 64-bit system!),
3352  * so waiting for one additional grace period should be just fine.
3353  */
3354 void cond_synchronize_rcu(unsigned long oldstate)
3355 {
3356 	unsigned long newstate;
3357 
3358 	/*
3359 	 * Ensure that this load happens before any RCU-destructive
3360 	 * actions the caller might carry out after we return.
3361 	 */
3362 	newstate = smp_load_acquire(&rcu_state_p->completed);
3363 	if (ULONG_CMP_GE(oldstate, newstate))
3364 		synchronize_rcu();
3365 }
3366 EXPORT_SYMBOL_GPL(cond_synchronize_rcu);
3367 
3368 /**
3369  * get_state_synchronize_sched - Snapshot current RCU-sched state
3370  *
3371  * Returns a cookie that is used by a later call to cond_synchronize_sched()
3372  * to determine whether or not a full grace period has elapsed in the
3373  * meantime.
3374  */
3375 unsigned long get_state_synchronize_sched(void)
3376 {
3377 	/*
3378 	 * Any prior manipulation of RCU-protected data must happen
3379 	 * before the load from ->gpnum.
3380 	 */
3381 	smp_mb();  /* ^^^ */
3382 
3383 	/*
3384 	 * Make sure this load happens before the purportedly
3385 	 * time-consuming work between get_state_synchronize_sched()
3386 	 * and cond_synchronize_sched().
3387 	 */
3388 	return smp_load_acquire(&rcu_sched_state.gpnum);
3389 }
3390 EXPORT_SYMBOL_GPL(get_state_synchronize_sched);
3391 
3392 /**
3393  * cond_synchronize_sched - Conditionally wait for an RCU-sched grace period
3394  *
3395  * @oldstate: return value from earlier call to get_state_synchronize_sched()
3396  *
3397  * If a full RCU-sched grace period has elapsed since the earlier call to
3398  * get_state_synchronize_sched(), just return.  Otherwise, invoke
3399  * synchronize_sched() to wait for a full grace period.
3400  *
3401  * Yes, this function does not take counter wrap into account.  But
3402  * counter wrap is harmless.  If the counter wraps, we have waited for
3403  * more than 2 billion grace periods (and way more on a 64-bit system!),
3404  * so waiting for one additional grace period should be just fine.
3405  */
3406 void cond_synchronize_sched(unsigned long oldstate)
3407 {
3408 	unsigned long newstate;
3409 
3410 	/*
3411 	 * Ensure that this load happens before any RCU-destructive
3412 	 * actions the caller might carry out after we return.
3413 	 */
3414 	newstate = smp_load_acquire(&rcu_sched_state.completed);
3415 	if (ULONG_CMP_GE(oldstate, newstate))
3416 		synchronize_sched();
3417 }
3418 EXPORT_SYMBOL_GPL(cond_synchronize_sched);
3419 
3420 /* Adjust sequence number for start of update-side operation. */
3421 static void rcu_seq_start(unsigned long *sp)
3422 {
3423 	WRITE_ONCE(*sp, *sp + 1);
3424 	smp_mb(); /* Ensure update-side operation after counter increment. */
3425 	WARN_ON_ONCE(!(*sp & 0x1));
3426 }
3427 
3428 /* Adjust sequence number for end of update-side operation. */
3429 static void rcu_seq_end(unsigned long *sp)
3430 {
3431 	smp_mb(); /* Ensure update-side operation before counter increment. */
3432 	WRITE_ONCE(*sp, *sp + 1);
3433 	WARN_ON_ONCE(*sp & 0x1);
3434 }
3435 
3436 /* Take a snapshot of the update side's sequence number. */
3437 static unsigned long rcu_seq_snap(unsigned long *sp)
3438 {
3439 	unsigned long s;
3440 
3441 	s = (READ_ONCE(*sp) + 3) & ~0x1;
3442 	smp_mb(); /* Above access must not bleed into critical section. */
3443 	return s;
3444 }
3445 
3446 /*
3447  * Given a snapshot from rcu_seq_snap(), determine whether or not a
3448  * full update-side operation has occurred.
3449  */
3450 static bool rcu_seq_done(unsigned long *sp, unsigned long s)
3451 {
3452 	return ULONG_CMP_GE(READ_ONCE(*sp), s);
3453 }
3454 
3455 /*
3456  * Check to see if there is any immediate RCU-related work to be done
3457  * by the current CPU, for the specified type of RCU, returning 1 if so.
3458  * The checks are in order of increasing expense: checks that can be
3459  * carried out against CPU-local state are performed first.  However,
3460  * we must check for CPU stalls first, else we might not get a chance.
3461  */
3462 static int __rcu_pending(struct rcu_state *rsp, struct rcu_data *rdp)
3463 {
3464 	struct rcu_node *rnp = rdp->mynode;
3465 
3466 	rdp->n_rcu_pending++;
3467 
3468 	/* Check for CPU stalls, if enabled. */
3469 	check_cpu_stall(rsp, rdp);
3470 
3471 	/* Is this CPU a NO_HZ_FULL CPU that should ignore RCU? */
3472 	if (rcu_nohz_full_cpu(rsp))
3473 		return 0;
3474 
3475 	/* Is the RCU core waiting for a quiescent state from this CPU? */
3476 	if (rcu_scheduler_fully_active &&
3477 	    rdp->core_needs_qs && rdp->cpu_no_qs.b.norm &&
3478 	    rdp->rcu_qs_ctr_snap == __this_cpu_read(rcu_qs_ctr)) {
3479 		rdp->n_rp_core_needs_qs++;
3480 	} else if (rdp->core_needs_qs &&
3481 		   (!rdp->cpu_no_qs.b.norm ||
3482 		    rdp->rcu_qs_ctr_snap != __this_cpu_read(rcu_qs_ctr))) {
3483 		rdp->n_rp_report_qs++;
3484 		return 1;
3485 	}
3486 
3487 	/* Does this CPU have callbacks ready to invoke? */
3488 	if (cpu_has_callbacks_ready_to_invoke(rdp)) {
3489 		rdp->n_rp_cb_ready++;
3490 		return 1;
3491 	}
3492 
3493 	/* Has RCU gone idle with this CPU needing another grace period? */
3494 	if (cpu_needs_another_gp(rsp, rdp)) {
3495 		rdp->n_rp_cpu_needs_gp++;
3496 		return 1;
3497 	}
3498 
3499 	/* Has another RCU grace period completed?  */
3500 	if (READ_ONCE(rnp->completed) != rdp->completed) { /* outside lock */
3501 		rdp->n_rp_gp_completed++;
3502 		return 1;
3503 	}
3504 
3505 	/* Has a new RCU grace period started? */
3506 	if (READ_ONCE(rnp->gpnum) != rdp->gpnum ||
3507 	    unlikely(READ_ONCE(rdp->gpwrap))) { /* outside lock */
3508 		rdp->n_rp_gp_started++;
3509 		return 1;
3510 	}
3511 
3512 	/* Does this CPU need a deferred NOCB wakeup? */
3513 	if (rcu_nocb_need_deferred_wakeup(rdp)) {
3514 		rdp->n_rp_nocb_defer_wakeup++;
3515 		return 1;
3516 	}
3517 
3518 	/* nothing to do */
3519 	rdp->n_rp_need_nothing++;
3520 	return 0;
3521 }
3522 
3523 /*
3524  * Check to see if there is any immediate RCU-related work to be done
3525  * by the current CPU, returning 1 if so.  This function is part of the
3526  * RCU implementation; it is -not- an exported member of the RCU API.
3527  */
3528 static int rcu_pending(void)
3529 {
3530 	struct rcu_state *rsp;
3531 
3532 	for_each_rcu_flavor(rsp)
3533 		if (__rcu_pending(rsp, this_cpu_ptr(rsp->rda)))
3534 			return 1;
3535 	return 0;
3536 }
3537 
3538 /*
3539  * Return true if the specified CPU has any callback.  If all_lazy is
3540  * non-NULL, store an indication of whether all callbacks are lazy.
3541  * (If there are no callbacks, all of them are deemed to be lazy.)
3542  */
3543 static bool __maybe_unused rcu_cpu_has_callbacks(bool *all_lazy)
3544 {
3545 	bool al = true;
3546 	bool hc = false;
3547 	struct rcu_data *rdp;
3548 	struct rcu_state *rsp;
3549 
3550 	for_each_rcu_flavor(rsp) {
3551 		rdp = this_cpu_ptr(rsp->rda);
3552 		if (!rdp->nxtlist)
3553 			continue;
3554 		hc = true;
3555 		if (rdp->qlen != rdp->qlen_lazy || !all_lazy) {
3556 			al = false;
3557 			break;
3558 		}
3559 	}
3560 	if (all_lazy)
3561 		*all_lazy = al;
3562 	return hc;
3563 }
3564 
3565 /*
3566  * Helper function for _rcu_barrier() tracing.  If tracing is disabled,
3567  * the compiler is expected to optimize this away.
3568  */
3569 static void _rcu_barrier_trace(struct rcu_state *rsp, const char *s,
3570 			       int cpu, unsigned long done)
3571 {
3572 	trace_rcu_barrier(rsp->name, s, cpu,
3573 			  atomic_read(&rsp->barrier_cpu_count), done);
3574 }
3575 
3576 /*
3577  * RCU callback function for _rcu_barrier().  If we are last, wake
3578  * up the task executing _rcu_barrier().
3579  */
3580 static void rcu_barrier_callback(struct rcu_head *rhp)
3581 {
3582 	struct rcu_data *rdp = container_of(rhp, struct rcu_data, barrier_head);
3583 	struct rcu_state *rsp = rdp->rsp;
3584 
3585 	if (atomic_dec_and_test(&rsp->barrier_cpu_count)) {
3586 		_rcu_barrier_trace(rsp, "LastCB", -1, rsp->barrier_sequence);
3587 		complete(&rsp->barrier_completion);
3588 	} else {
3589 		_rcu_barrier_trace(rsp, "CB", -1, rsp->barrier_sequence);
3590 	}
3591 }
3592 
3593 /*
3594  * Called with preemption disabled, and from cross-cpu IRQ context.
3595  */
3596 static void rcu_barrier_func(void *type)
3597 {
3598 	struct rcu_state *rsp = type;
3599 	struct rcu_data *rdp = raw_cpu_ptr(rsp->rda);
3600 
3601 	_rcu_barrier_trace(rsp, "IRQ", -1, rsp->barrier_sequence);
3602 	atomic_inc(&rsp->barrier_cpu_count);
3603 	rsp->call(&rdp->barrier_head, rcu_barrier_callback);
3604 }
3605 
3606 /*
3607  * Orchestrate the specified type of RCU barrier, waiting for all
3608  * RCU callbacks of the specified type to complete.
3609  */
3610 static void _rcu_barrier(struct rcu_state *rsp)
3611 {
3612 	int cpu;
3613 	struct rcu_data *rdp;
3614 	unsigned long s = rcu_seq_snap(&rsp->barrier_sequence);
3615 
3616 	_rcu_barrier_trace(rsp, "Begin", -1, s);
3617 
3618 	/* Take mutex to serialize concurrent rcu_barrier() requests. */
3619 	mutex_lock(&rsp->barrier_mutex);
3620 
3621 	/* Did someone else do our work for us? */
3622 	if (rcu_seq_done(&rsp->barrier_sequence, s)) {
3623 		_rcu_barrier_trace(rsp, "EarlyExit", -1, rsp->barrier_sequence);
3624 		smp_mb(); /* caller's subsequent code after above check. */
3625 		mutex_unlock(&rsp->barrier_mutex);
3626 		return;
3627 	}
3628 
3629 	/* Mark the start of the barrier operation. */
3630 	rcu_seq_start(&rsp->barrier_sequence);
3631 	_rcu_barrier_trace(rsp, "Inc1", -1, rsp->barrier_sequence);
3632 
3633 	/*
3634 	 * Initialize the count to one rather than to zero in order to
3635 	 * avoid a too-soon return to zero in case of a short grace period
3636 	 * (or preemption of this task).  Exclude CPU-hotplug operations
3637 	 * to ensure that no offline CPU has callbacks queued.
3638 	 */
3639 	init_completion(&rsp->barrier_completion);
3640 	atomic_set(&rsp->barrier_cpu_count, 1);
3641 	get_online_cpus();
3642 
3643 	/*
3644 	 * Force each CPU with callbacks to register a new callback.
3645 	 * When that callback is invoked, we will know that all of the
3646 	 * corresponding CPU's preceding callbacks have been invoked.
3647 	 */
3648 	for_each_possible_cpu(cpu) {
3649 		if (!cpu_online(cpu) && !rcu_is_nocb_cpu(cpu))
3650 			continue;
3651 		rdp = per_cpu_ptr(rsp->rda, cpu);
3652 		if (rcu_is_nocb_cpu(cpu)) {
3653 			if (!rcu_nocb_cpu_needs_barrier(rsp, cpu)) {
3654 				_rcu_barrier_trace(rsp, "OfflineNoCB", cpu,
3655 						   rsp->barrier_sequence);
3656 			} else {
3657 				_rcu_barrier_trace(rsp, "OnlineNoCB", cpu,
3658 						   rsp->barrier_sequence);
3659 				smp_mb__before_atomic();
3660 				atomic_inc(&rsp->barrier_cpu_count);
3661 				__call_rcu(&rdp->barrier_head,
3662 					   rcu_barrier_callback, rsp, cpu, 0);
3663 			}
3664 		} else if (READ_ONCE(rdp->qlen)) {
3665 			_rcu_barrier_trace(rsp, "OnlineQ", cpu,
3666 					   rsp->barrier_sequence);
3667 			smp_call_function_single(cpu, rcu_barrier_func, rsp, 1);
3668 		} else {
3669 			_rcu_barrier_trace(rsp, "OnlineNQ", cpu,
3670 					   rsp->barrier_sequence);
3671 		}
3672 	}
3673 	put_online_cpus();
3674 
3675 	/*
3676 	 * Now that we have an rcu_barrier_callback() callback on each
3677 	 * CPU, and thus each counted, remove the initial count.
3678 	 */
3679 	if (atomic_dec_and_test(&rsp->barrier_cpu_count))
3680 		complete(&rsp->barrier_completion);
3681 
3682 	/* Wait for all rcu_barrier_callback() callbacks to be invoked. */
3683 	wait_for_completion(&rsp->barrier_completion);
3684 
3685 	/* Mark the end of the barrier operation. */
3686 	_rcu_barrier_trace(rsp, "Inc2", -1, rsp->barrier_sequence);
3687 	rcu_seq_end(&rsp->barrier_sequence);
3688 
3689 	/* Other rcu_barrier() invocations can now safely proceed. */
3690 	mutex_unlock(&rsp->barrier_mutex);
3691 }
3692 
3693 /**
3694  * rcu_barrier_bh - Wait until all in-flight call_rcu_bh() callbacks complete.
3695  */
3696 void rcu_barrier_bh(void)
3697 {
3698 	_rcu_barrier(&rcu_bh_state);
3699 }
3700 EXPORT_SYMBOL_GPL(rcu_barrier_bh);
3701 
3702 /**
3703  * rcu_barrier_sched - Wait for in-flight call_rcu_sched() callbacks.
3704  */
3705 void rcu_barrier_sched(void)
3706 {
3707 	_rcu_barrier(&rcu_sched_state);
3708 }
3709 EXPORT_SYMBOL_GPL(rcu_barrier_sched);
3710 
3711 /*
3712  * Propagate ->qsinitmask bits up the rcu_node tree to account for the
3713  * first CPU in a given leaf rcu_node structure coming online.  The caller
3714  * must hold the corresponding leaf rcu_node ->lock with interrrupts
3715  * disabled.
3716  */
3717 static void rcu_init_new_rnp(struct rcu_node *rnp_leaf)
3718 {
3719 	long mask;
3720 	struct rcu_node *rnp = rnp_leaf;
3721 
3722 	for (;;) {
3723 		mask = rnp->grpmask;
3724 		rnp = rnp->parent;
3725 		if (rnp == NULL)
3726 			return;
3727 		raw_spin_lock_rcu_node(rnp); /* Interrupts already disabled. */
3728 		rnp->qsmaskinit |= mask;
3729 		raw_spin_unlock_rcu_node(rnp); /* Interrupts remain disabled. */
3730 	}
3731 }
3732 
3733 /*
3734  * Do boot-time initialization of a CPU's per-CPU RCU data.
3735  */
3736 static void __init
3737 rcu_boot_init_percpu_data(int cpu, struct rcu_state *rsp)
3738 {
3739 	unsigned long flags;
3740 	struct rcu_data *rdp = per_cpu_ptr(rsp->rda, cpu);
3741 	struct rcu_node *rnp = rcu_get_root(rsp);
3742 
3743 	/* Set up local state, ensuring consistent view of global state. */
3744 	raw_spin_lock_irqsave_rcu_node(rnp, flags);
3745 	rdp->grpmask = leaf_node_cpu_bit(rdp->mynode, cpu);
3746 	rdp->dynticks = &per_cpu(rcu_dynticks, cpu);
3747 	WARN_ON_ONCE(rdp->dynticks->dynticks_nesting != DYNTICK_TASK_EXIT_IDLE);
3748 	WARN_ON_ONCE(atomic_read(&rdp->dynticks->dynticks) != 1);
3749 	rdp->cpu = cpu;
3750 	rdp->rsp = rsp;
3751 	rcu_boot_init_nocb_percpu_data(rdp);
3752 	raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
3753 }
3754 
3755 /*
3756  * Initialize a CPU's per-CPU RCU data.  Note that only one online or
3757  * offline event can be happening at a given time.  Note also that we
3758  * can accept some slop in the rsp->completed access due to the fact
3759  * that this CPU cannot possibly have any RCU callbacks in flight yet.
3760  */
3761 static void
3762 rcu_init_percpu_data(int cpu, struct rcu_state *rsp)
3763 {
3764 	unsigned long flags;
3765 	unsigned long mask;
3766 	struct rcu_data *rdp = per_cpu_ptr(rsp->rda, cpu);
3767 	struct rcu_node *rnp = rcu_get_root(rsp);
3768 
3769 	/* Set up local state, ensuring consistent view of global state. */
3770 	raw_spin_lock_irqsave_rcu_node(rnp, flags);
3771 	rdp->qlen_last_fqs_check = 0;
3772 	rdp->n_force_qs_snap = rsp->n_force_qs;
3773 	rdp->blimit = blimit;
3774 	if (!rdp->nxtlist)
3775 		init_callback_list(rdp);  /* Re-enable callbacks on this CPU. */
3776 	rdp->dynticks->dynticks_nesting = DYNTICK_TASK_EXIT_IDLE;
3777 	rcu_sysidle_init_percpu_data(rdp->dynticks);
3778 	atomic_set(&rdp->dynticks->dynticks,
3779 		   (atomic_read(&rdp->dynticks->dynticks) & ~0x1) + 1);
3780 	raw_spin_unlock_rcu_node(rnp);		/* irqs remain disabled. */
3781 
3782 	/*
3783 	 * Add CPU to leaf rcu_node pending-online bitmask.  Any needed
3784 	 * propagation up the rcu_node tree will happen at the beginning
3785 	 * of the next grace period.
3786 	 */
3787 	rnp = rdp->mynode;
3788 	mask = rdp->grpmask;
3789 	raw_spin_lock_rcu_node(rnp);		/* irqs already disabled. */
3790 	if (!rdp->beenonline)
3791 		WRITE_ONCE(rsp->ncpus, READ_ONCE(rsp->ncpus) + 1);
3792 	rdp->beenonline = true;	 /* We have now been online. */
3793 	rdp->gpnum = rnp->completed; /* Make CPU later note any new GP. */
3794 	rdp->completed = rnp->completed;
3795 	rdp->cpu_no_qs.b.norm = true;
3796 	rdp->rcu_qs_ctr_snap = per_cpu(rcu_qs_ctr, cpu);
3797 	rdp->core_needs_qs = false;
3798 	trace_rcu_grace_period(rsp->name, rdp->gpnum, TPS("cpuonl"));
3799 	raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
3800 }
3801 
3802 int rcutree_prepare_cpu(unsigned int cpu)
3803 {
3804 	struct rcu_state *rsp;
3805 
3806 	for_each_rcu_flavor(rsp)
3807 		rcu_init_percpu_data(cpu, rsp);
3808 
3809 	rcu_prepare_kthreads(cpu);
3810 	rcu_spawn_all_nocb_kthreads(cpu);
3811 
3812 	return 0;
3813 }
3814 
3815 static void rcutree_affinity_setting(unsigned int cpu, int outgoing)
3816 {
3817 	struct rcu_data *rdp = per_cpu_ptr(rcu_state_p->rda, cpu);
3818 
3819 	rcu_boost_kthread_setaffinity(rdp->mynode, outgoing);
3820 }
3821 
3822 int rcutree_online_cpu(unsigned int cpu)
3823 {
3824 	sync_sched_exp_online_cleanup(cpu);
3825 	rcutree_affinity_setting(cpu, -1);
3826 	return 0;
3827 }
3828 
3829 int rcutree_offline_cpu(unsigned int cpu)
3830 {
3831 	rcutree_affinity_setting(cpu, cpu);
3832 	return 0;
3833 }
3834 
3835 
3836 int rcutree_dying_cpu(unsigned int cpu)
3837 {
3838 	struct rcu_state *rsp;
3839 
3840 	for_each_rcu_flavor(rsp)
3841 		rcu_cleanup_dying_cpu(rsp);
3842 	return 0;
3843 }
3844 
3845 int rcutree_dead_cpu(unsigned int cpu)
3846 {
3847 	struct rcu_state *rsp;
3848 
3849 	for_each_rcu_flavor(rsp) {
3850 		rcu_cleanup_dead_cpu(cpu, rsp);
3851 		do_nocb_deferred_wakeup(per_cpu_ptr(rsp->rda, cpu));
3852 	}
3853 	return 0;
3854 }
3855 
3856 /*
3857  * Mark the specified CPU as being online so that subsequent grace periods
3858  * (both expedited and normal) will wait on it.  Note that this means that
3859  * incoming CPUs are not allowed to use RCU read-side critical sections
3860  * until this function is called.  Failing to observe this restriction
3861  * will result in lockdep splats.
3862  */
3863 void rcu_cpu_starting(unsigned int cpu)
3864 {
3865 	unsigned long flags;
3866 	unsigned long mask;
3867 	struct rcu_data *rdp;
3868 	struct rcu_node *rnp;
3869 	struct rcu_state *rsp;
3870 
3871 	for_each_rcu_flavor(rsp) {
3872 		rdp = this_cpu_ptr(rsp->rda);
3873 		rnp = rdp->mynode;
3874 		mask = rdp->grpmask;
3875 		raw_spin_lock_irqsave_rcu_node(rnp, flags);
3876 		rnp->qsmaskinitnext |= mask;
3877 		rnp->expmaskinitnext |= mask;
3878 		raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
3879 	}
3880 }
3881 
3882 #ifdef CONFIG_HOTPLUG_CPU
3883 /*
3884  * The CPU is exiting the idle loop into the arch_cpu_idle_dead()
3885  * function.  We now remove it from the rcu_node tree's ->qsmaskinit
3886  * bit masks.
3887  * The CPU is exiting the idle loop into the arch_cpu_idle_dead()
3888  * function.  We now remove it from the rcu_node tree's ->qsmaskinit
3889  * bit masks.
3890  */
3891 static void rcu_cleanup_dying_idle_cpu(int cpu, struct rcu_state *rsp)
3892 {
3893 	unsigned long flags;
3894 	unsigned long mask;
3895 	struct rcu_data *rdp = per_cpu_ptr(rsp->rda, cpu);
3896 	struct rcu_node *rnp = rdp->mynode;  /* Outgoing CPU's rdp & rnp. */
3897 
3898 	/* Remove outgoing CPU from mask in the leaf rcu_node structure. */
3899 	mask = rdp->grpmask;
3900 	raw_spin_lock_irqsave_rcu_node(rnp, flags); /* Enforce GP memory-order guarantee. */
3901 	rnp->qsmaskinitnext &= ~mask;
3902 	raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
3903 }
3904 
3905 void rcu_report_dead(unsigned int cpu)
3906 {
3907 	struct rcu_state *rsp;
3908 
3909 	/* QS for any half-done expedited RCU-sched GP. */
3910 	preempt_disable();
3911 	rcu_report_exp_rdp(&rcu_sched_state,
3912 			   this_cpu_ptr(rcu_sched_state.rda), true);
3913 	preempt_enable();
3914 	for_each_rcu_flavor(rsp)
3915 		rcu_cleanup_dying_idle_cpu(cpu, rsp);
3916 }
3917 #endif
3918 
3919 static int rcu_pm_notify(struct notifier_block *self,
3920 			 unsigned long action, void *hcpu)
3921 {
3922 	switch (action) {
3923 	case PM_HIBERNATION_PREPARE:
3924 	case PM_SUSPEND_PREPARE:
3925 		if (nr_cpu_ids <= 256) /* Expediting bad for large systems. */
3926 			rcu_expedite_gp();
3927 		break;
3928 	case PM_POST_HIBERNATION:
3929 	case PM_POST_SUSPEND:
3930 		if (nr_cpu_ids <= 256) /* Expediting bad for large systems. */
3931 			rcu_unexpedite_gp();
3932 		break;
3933 	default:
3934 		break;
3935 	}
3936 	return NOTIFY_OK;
3937 }
3938 
3939 /*
3940  * Spawn the kthreads that handle each RCU flavor's grace periods.
3941  */
3942 static int __init rcu_spawn_gp_kthread(void)
3943 {
3944 	unsigned long flags;
3945 	int kthread_prio_in = kthread_prio;
3946 	struct rcu_node *rnp;
3947 	struct rcu_state *rsp;
3948 	struct sched_param sp;
3949 	struct task_struct *t;
3950 
3951 	/* Force priority into range. */
3952 	if (IS_ENABLED(CONFIG_RCU_BOOST) && kthread_prio < 1)
3953 		kthread_prio = 1;
3954 	else if (kthread_prio < 0)
3955 		kthread_prio = 0;
3956 	else if (kthread_prio > 99)
3957 		kthread_prio = 99;
3958 	if (kthread_prio != kthread_prio_in)
3959 		pr_alert("rcu_spawn_gp_kthread(): Limited prio to %d from %d\n",
3960 			 kthread_prio, kthread_prio_in);
3961 
3962 	rcu_scheduler_fully_active = 1;
3963 	for_each_rcu_flavor(rsp) {
3964 		t = kthread_create(rcu_gp_kthread, rsp, "%s", rsp->name);
3965 		BUG_ON(IS_ERR(t));
3966 		rnp = rcu_get_root(rsp);
3967 		raw_spin_lock_irqsave_rcu_node(rnp, flags);
3968 		rsp->gp_kthread = t;
3969 		if (kthread_prio) {
3970 			sp.sched_priority = kthread_prio;
3971 			sched_setscheduler_nocheck(t, SCHED_FIFO, &sp);
3972 		}
3973 		raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
3974 		wake_up_process(t);
3975 	}
3976 	rcu_spawn_nocb_kthreads();
3977 	rcu_spawn_boost_kthreads();
3978 	return 0;
3979 }
3980 early_initcall(rcu_spawn_gp_kthread);
3981 
3982 /*
3983  * This function is invoked towards the end of the scheduler's initialization
3984  * process.  Before this is called, the idle task might contain
3985  * RCU read-side critical sections (during which time, this idle
3986  * task is booting the system).  After this function is called, the
3987  * idle tasks are prohibited from containing RCU read-side critical
3988  * sections.  This function also enables RCU lockdep checking.
3989  */
3990 void rcu_scheduler_starting(void)
3991 {
3992 	WARN_ON(num_online_cpus() != 1);
3993 	WARN_ON(nr_context_switches() > 0);
3994 	rcu_scheduler_active = 1;
3995 }
3996 
3997 /*
3998  * Compute the per-level fanout, either using the exact fanout specified
3999  * or balancing the tree, depending on the rcu_fanout_exact boot parameter.
4000  */
4001 static void __init rcu_init_levelspread(int *levelspread, const int *levelcnt)
4002 {
4003 	int i;
4004 
4005 	if (rcu_fanout_exact) {
4006 		levelspread[rcu_num_lvls - 1] = rcu_fanout_leaf;
4007 		for (i = rcu_num_lvls - 2; i >= 0; i--)
4008 			levelspread[i] = RCU_FANOUT;
4009 	} else {
4010 		int ccur;
4011 		int cprv;
4012 
4013 		cprv = nr_cpu_ids;
4014 		for (i = rcu_num_lvls - 1; i >= 0; i--) {
4015 			ccur = levelcnt[i];
4016 			levelspread[i] = (cprv + ccur - 1) / ccur;
4017 			cprv = ccur;
4018 		}
4019 	}
4020 }
4021 
4022 /*
4023  * Helper function for rcu_init() that initializes one rcu_state structure.
4024  */
4025 static void __init rcu_init_one(struct rcu_state *rsp)
4026 {
4027 	static const char * const buf[] = RCU_NODE_NAME_INIT;
4028 	static const char * const fqs[] = RCU_FQS_NAME_INIT;
4029 	static struct lock_class_key rcu_node_class[RCU_NUM_LVLS];
4030 	static struct lock_class_key rcu_fqs_class[RCU_NUM_LVLS];
4031 	static u8 fl_mask = 0x1;
4032 
4033 	int levelcnt[RCU_NUM_LVLS];		/* # nodes in each level. */
4034 	int levelspread[RCU_NUM_LVLS];		/* kids/node in each level. */
4035 	int cpustride = 1;
4036 	int i;
4037 	int j;
4038 	struct rcu_node *rnp;
4039 
4040 	BUILD_BUG_ON(RCU_NUM_LVLS > ARRAY_SIZE(buf));  /* Fix buf[] init! */
4041 
4042 	/* Silence gcc 4.8 false positive about array index out of range. */
4043 	if (rcu_num_lvls <= 0 || rcu_num_lvls > RCU_NUM_LVLS)
4044 		panic("rcu_init_one: rcu_num_lvls out of range");
4045 
4046 	/* Initialize the level-tracking arrays. */
4047 
4048 	for (i = 0; i < rcu_num_lvls; i++)
4049 		levelcnt[i] = num_rcu_lvl[i];
4050 	for (i = 1; i < rcu_num_lvls; i++)
4051 		rsp->level[i] = rsp->level[i - 1] + levelcnt[i - 1];
4052 	rcu_init_levelspread(levelspread, levelcnt);
4053 	rsp->flavor_mask = fl_mask;
4054 	fl_mask <<= 1;
4055 
4056 	/* Initialize the elements themselves, starting from the leaves. */
4057 
4058 	for (i = rcu_num_lvls - 1; i >= 0; i--) {
4059 		cpustride *= levelspread[i];
4060 		rnp = rsp->level[i];
4061 		for (j = 0; j < levelcnt[i]; j++, rnp++) {
4062 			raw_spin_lock_init(&ACCESS_PRIVATE(rnp, lock));
4063 			lockdep_set_class_and_name(&ACCESS_PRIVATE(rnp, lock),
4064 						   &rcu_node_class[i], buf[i]);
4065 			raw_spin_lock_init(&rnp->fqslock);
4066 			lockdep_set_class_and_name(&rnp->fqslock,
4067 						   &rcu_fqs_class[i], fqs[i]);
4068 			rnp->gpnum = rsp->gpnum;
4069 			rnp->completed = rsp->completed;
4070 			rnp->qsmask = 0;
4071 			rnp->qsmaskinit = 0;
4072 			rnp->grplo = j * cpustride;
4073 			rnp->grphi = (j + 1) * cpustride - 1;
4074 			if (rnp->grphi >= nr_cpu_ids)
4075 				rnp->grphi = nr_cpu_ids - 1;
4076 			if (i == 0) {
4077 				rnp->grpnum = 0;
4078 				rnp->grpmask = 0;
4079 				rnp->parent = NULL;
4080 			} else {
4081 				rnp->grpnum = j % levelspread[i - 1];
4082 				rnp->grpmask = 1UL << rnp->grpnum;
4083 				rnp->parent = rsp->level[i - 1] +
4084 					      j / levelspread[i - 1];
4085 			}
4086 			rnp->level = i;
4087 			INIT_LIST_HEAD(&rnp->blkd_tasks);
4088 			rcu_init_one_nocb(rnp);
4089 			init_waitqueue_head(&rnp->exp_wq[0]);
4090 			init_waitqueue_head(&rnp->exp_wq[1]);
4091 			init_waitqueue_head(&rnp->exp_wq[2]);
4092 			init_waitqueue_head(&rnp->exp_wq[3]);
4093 			spin_lock_init(&rnp->exp_lock);
4094 		}
4095 	}
4096 
4097 	init_swait_queue_head(&rsp->gp_wq);
4098 	init_swait_queue_head(&rsp->expedited_wq);
4099 	rnp = rsp->level[rcu_num_lvls - 1];
4100 	for_each_possible_cpu(i) {
4101 		while (i > rnp->grphi)
4102 			rnp++;
4103 		per_cpu_ptr(rsp->rda, i)->mynode = rnp;
4104 		rcu_boot_init_percpu_data(i, rsp);
4105 	}
4106 	list_add(&rsp->flavors, &rcu_struct_flavors);
4107 }
4108 
4109 /*
4110  * Compute the rcu_node tree geometry from kernel parameters.  This cannot
4111  * replace the definitions in tree.h because those are needed to size
4112  * the ->node array in the rcu_state structure.
4113  */
4114 static void __init rcu_init_geometry(void)
4115 {
4116 	ulong d;
4117 	int i;
4118 	int rcu_capacity[RCU_NUM_LVLS];
4119 
4120 	/*
4121 	 * Initialize any unspecified boot parameters.
4122 	 * The default values of jiffies_till_first_fqs and
4123 	 * jiffies_till_next_fqs are set to the RCU_JIFFIES_TILL_FORCE_QS
4124 	 * value, which is a function of HZ, then adding one for each
4125 	 * RCU_JIFFIES_FQS_DIV CPUs that might be on the system.
4126 	 */
4127 	d = RCU_JIFFIES_TILL_FORCE_QS + nr_cpu_ids / RCU_JIFFIES_FQS_DIV;
4128 	if (jiffies_till_first_fqs == ULONG_MAX)
4129 		jiffies_till_first_fqs = d;
4130 	if (jiffies_till_next_fqs == ULONG_MAX)
4131 		jiffies_till_next_fqs = d;
4132 
4133 	/* If the compile-time values are accurate, just leave. */
4134 	if (rcu_fanout_leaf == RCU_FANOUT_LEAF &&
4135 	    nr_cpu_ids == NR_CPUS)
4136 		return;
4137 	pr_info("RCU: Adjusting geometry for rcu_fanout_leaf=%d, nr_cpu_ids=%d\n",
4138 		rcu_fanout_leaf, nr_cpu_ids);
4139 
4140 	/*
4141 	 * The boot-time rcu_fanout_leaf parameter must be at least two
4142 	 * and cannot exceed the number of bits in the rcu_node masks.
4143 	 * Complain and fall back to the compile-time values if this
4144 	 * limit is exceeded.
4145 	 */
4146 	if (rcu_fanout_leaf < 2 ||
4147 	    rcu_fanout_leaf > sizeof(unsigned long) * 8) {
4148 		rcu_fanout_leaf = RCU_FANOUT_LEAF;
4149 		WARN_ON(1);
4150 		return;
4151 	}
4152 
4153 	/*
4154 	 * Compute number of nodes that can be handled an rcu_node tree
4155 	 * with the given number of levels.
4156 	 */
4157 	rcu_capacity[0] = rcu_fanout_leaf;
4158 	for (i = 1; i < RCU_NUM_LVLS; i++)
4159 		rcu_capacity[i] = rcu_capacity[i - 1] * RCU_FANOUT;
4160 
4161 	/*
4162 	 * The tree must be able to accommodate the configured number of CPUs.
4163 	 * If this limit is exceeded, fall back to the compile-time values.
4164 	 */
4165 	if (nr_cpu_ids > rcu_capacity[RCU_NUM_LVLS - 1]) {
4166 		rcu_fanout_leaf = RCU_FANOUT_LEAF;
4167 		WARN_ON(1);
4168 		return;
4169 	}
4170 
4171 	/* Calculate the number of levels in the tree. */
4172 	for (i = 0; nr_cpu_ids > rcu_capacity[i]; i++) {
4173 	}
4174 	rcu_num_lvls = i + 1;
4175 
4176 	/* Calculate the number of rcu_nodes at each level of the tree. */
4177 	for (i = 0; i < rcu_num_lvls; i++) {
4178 		int cap = rcu_capacity[(rcu_num_lvls - 1) - i];
4179 		num_rcu_lvl[i] = DIV_ROUND_UP(nr_cpu_ids, cap);
4180 	}
4181 
4182 	/* Calculate the total number of rcu_node structures. */
4183 	rcu_num_nodes = 0;
4184 	for (i = 0; i < rcu_num_lvls; i++)
4185 		rcu_num_nodes += num_rcu_lvl[i];
4186 }
4187 
4188 /*
4189  * Dump out the structure of the rcu_node combining tree associated
4190  * with the rcu_state structure referenced by rsp.
4191  */
4192 static void __init rcu_dump_rcu_node_tree(struct rcu_state *rsp)
4193 {
4194 	int level = 0;
4195 	struct rcu_node *rnp;
4196 
4197 	pr_info("rcu_node tree layout dump\n");
4198 	pr_info(" ");
4199 	rcu_for_each_node_breadth_first(rsp, rnp) {
4200 		if (rnp->level != level) {
4201 			pr_cont("\n");
4202 			pr_info(" ");
4203 			level = rnp->level;
4204 		}
4205 		pr_cont("%d:%d ^%d  ", rnp->grplo, rnp->grphi, rnp->grpnum);
4206 	}
4207 	pr_cont("\n");
4208 }
4209 
4210 void __init rcu_init(void)
4211 {
4212 	int cpu;
4213 
4214 	rcu_early_boot_tests();
4215 
4216 	rcu_bootup_announce();
4217 	rcu_init_geometry();
4218 	rcu_init_one(&rcu_bh_state);
4219 	rcu_init_one(&rcu_sched_state);
4220 	if (dump_tree)
4221 		rcu_dump_rcu_node_tree(&rcu_sched_state);
4222 	__rcu_init_preempt();
4223 	open_softirq(RCU_SOFTIRQ, rcu_process_callbacks);
4224 
4225 	/*
4226 	 * We don't need protection against CPU-hotplug here because
4227 	 * this is called early in boot, before either interrupts
4228 	 * or the scheduler are operational.
4229 	 */
4230 	pm_notifier(rcu_pm_notify, 0);
4231 	for_each_online_cpu(cpu) {
4232 		rcutree_prepare_cpu(cpu);
4233 		rcu_cpu_starting(cpu);
4234 	}
4235 }
4236 
4237 #include "tree_exp.h"
4238 #include "tree_plugin.h"
4239