acd6ccf56faf9ff090b43ea08458b3380f22cc3d
[muen/linux.git] / kernel / rcu / tree.c
1 // SPDX-License-Identifier: GPL-2.0+
2 /*
3  * Read-Copy Update mechanism for mutual exclusion
4  *
5  * Copyright IBM Corporation, 2008
6  *
7  * Authors: Dipankar Sarma <dipankar@in.ibm.com>
8  *          Manfred Spraul <manfred@colorfullife.com>
9  *          Paul E. McKenney <paulmck@linux.ibm.com> Hierarchical version
10  *
11  * Based on the original work by Paul McKenney <paulmck@linux.ibm.com>
12  * and inputs from Rusty Russell, Andrea Arcangeli and Andi Kleen.
13  *
14  * For detailed explanation of Read-Copy Update mechanism see -
15  *      Documentation/RCU
16  */
17
18 #define pr_fmt(fmt) "rcu: " fmt
19
20 #include <linux/types.h>
21 #include <linux/kernel.h>
22 #include <linux/init.h>
23 #include <linux/spinlock.h>
24 #include <linux/smp.h>
25 #include <linux/rcupdate_wait.h>
26 #include <linux/interrupt.h>
27 #include <linux/sched.h>
28 #include <linux/sched/debug.h>
29 #include <linux/nmi.h>
30 #include <linux/atomic.h>
31 #include <linux/bitops.h>
32 #include <linux/export.h>
33 #include <linux/completion.h>
34 #include <linux/moduleparam.h>
35 #include <linux/percpu.h>
36 #include <linux/notifier.h>
37 #include <linux/cpu.h>
38 #include <linux/mutex.h>
39 #include <linux/time.h>
40 #include <linux/kernel_stat.h>
41 #include <linux/wait.h>
42 #include <linux/kthread.h>
43 #include <uapi/linux/sched/types.h>
44 #include <linux/prefetch.h>
45 #include <linux/delay.h>
46 #include <linux/stop_machine.h>
47 #include <linux/random.h>
48 #include <linux/trace_events.h>
49 #include <linux/suspend.h>
50 #include <linux/ftrace.h>
51 #include <linux/tick.h>
52 #include <linux/sysrq.h>
53 #include <linux/kprobes.h>
54
55 #include "tree.h"
56 #include "rcu.h"
57
58 #ifdef MODULE_PARAM_PREFIX
59 #undef MODULE_PARAM_PREFIX
60 #endif
61 #define MODULE_PARAM_PREFIX "rcutree."
62
63 /* Data structures. */
64
65 /*
66  * Steal a bit from the bottom of ->dynticks for idle entry/exit
67  * control.  Initially this is for TLB flushing.
68  */
69 #define RCU_DYNTICK_CTRL_MASK 0x1
70 #define RCU_DYNTICK_CTRL_CTR  (RCU_DYNTICK_CTRL_MASK + 1)
71 #ifndef rcu_eqs_special_exit
72 #define rcu_eqs_special_exit() do { } while (0)
73 #endif
74
75 static DEFINE_PER_CPU_SHARED_ALIGNED(struct rcu_data, rcu_data) = {
76         .dynticks_nesting = 1,
77         .dynticks_nmi_nesting = DYNTICK_IRQ_NONIDLE,
78         .dynticks = ATOMIC_INIT(RCU_DYNTICK_CTRL_CTR),
79 };
80 struct rcu_state rcu_state = {
81         .level = { &rcu_state.node[0] },
82         .gp_state = RCU_GP_IDLE,
83         .gp_seq = (0UL - 300UL) << RCU_SEQ_CTR_SHIFT,
84         .barrier_mutex = __MUTEX_INITIALIZER(rcu_state.barrier_mutex),
85         .name = RCU_NAME,
86         .abbr = RCU_ABBR,
87         .exp_mutex = __MUTEX_INITIALIZER(rcu_state.exp_mutex),
88         .exp_wake_mutex = __MUTEX_INITIALIZER(rcu_state.exp_wake_mutex),
89         .ofl_lock = __RAW_SPIN_LOCK_UNLOCKED(rcu_state.ofl_lock),
90 };
91
92 /* Dump rcu_node combining tree at boot to verify correct setup. */
93 static bool dump_tree;
94 module_param(dump_tree, bool, 0444);
95 /* Control rcu_node-tree auto-balancing at boot time. */
96 static bool rcu_fanout_exact;
97 module_param(rcu_fanout_exact, bool, 0444);
98 /* Increase (but not decrease) the RCU_FANOUT_LEAF at boot time. */
99 static int rcu_fanout_leaf = RCU_FANOUT_LEAF;
100 module_param(rcu_fanout_leaf, int, 0444);
101 int rcu_num_lvls __read_mostly = RCU_NUM_LVLS;
102 /* Number of rcu_nodes at specified level. */
103 int num_rcu_lvl[] = NUM_RCU_LVL_INIT;
104 int rcu_num_nodes __read_mostly = NUM_RCU_NODES; /* Total # rcu_nodes in use. */
105 /* panic() on RCU Stall sysctl. */
106 int sysctl_panic_on_rcu_stall __read_mostly;
107 /* Commandeer a sysrq key to dump RCU's tree. */
108 static bool sysrq_rcu;
109 module_param(sysrq_rcu, bool, 0444);
110
111 /*
112  * The rcu_scheduler_active variable is initialized to the value
113  * RCU_SCHEDULER_INACTIVE and transitions RCU_SCHEDULER_INIT just before the
114  * first task is spawned.  So when this variable is RCU_SCHEDULER_INACTIVE,
115  * RCU can assume that there is but one task, allowing RCU to (for example)
116  * optimize synchronize_rcu() to a simple barrier().  When this variable
117  * is RCU_SCHEDULER_INIT, RCU must actually do all the hard work required
118  * to detect real grace periods.  This variable is also used to suppress
119  * boot-time false positives from lockdep-RCU error checking.  Finally, it
120  * transitions from RCU_SCHEDULER_INIT to RCU_SCHEDULER_RUNNING after RCU
121  * is fully initialized, including all of its kthreads having been spawned.
122  */
123 int rcu_scheduler_active __read_mostly;
124 EXPORT_SYMBOL_GPL(rcu_scheduler_active);
125
126 /*
127  * The rcu_scheduler_fully_active variable transitions from zero to one
128  * during the early_initcall() processing, which is after the scheduler
129  * is capable of creating new tasks.  So RCU processing (for example,
130  * creating tasks for RCU priority boosting) must be delayed until after
131  * rcu_scheduler_fully_active transitions from zero to one.  We also
132  * currently delay invocation of any RCU callbacks until after this point.
133  *
134  * It might later prove better for people registering RCU callbacks during
135  * early boot to take responsibility for these callbacks, but one step at
136  * a time.
137  */
138 static int rcu_scheduler_fully_active __read_mostly;
139
140 static void rcu_report_qs_rnp(unsigned long mask, struct rcu_node *rnp,
141                               unsigned long gps, unsigned long flags);
142 static void rcu_init_new_rnp(struct rcu_node *rnp_leaf);
143 static void rcu_cleanup_dead_rnp(struct rcu_node *rnp_leaf);
144 static void rcu_boost_kthread_setaffinity(struct rcu_node *rnp, int outgoingcpu);
145 static void invoke_rcu_core(void);
146 static void invoke_rcu_callbacks(struct rcu_data *rdp);
147 static void rcu_report_exp_rdp(struct rcu_data *rdp);
148 static void sync_sched_exp_online_cleanup(int cpu);
149
150 /* rcuc/rcub kthread realtime priority */
151 static int kthread_prio = IS_ENABLED(CONFIG_RCU_BOOST) ? 1 : 0;
152 module_param(kthread_prio, int, 0644);
153
154 /* Delay in jiffies for grace-period initialization delays, debug only. */
155
156 static int gp_preinit_delay;
157 module_param(gp_preinit_delay, int, 0444);
158 static int gp_init_delay;
159 module_param(gp_init_delay, int, 0444);
160 static int gp_cleanup_delay;
161 module_param(gp_cleanup_delay, int, 0444);
162
163 /* Retrieve RCU kthreads priority for rcutorture */
164 int rcu_get_gp_kthreads_prio(void)
165 {
166         return kthread_prio;
167 }
168 EXPORT_SYMBOL_GPL(rcu_get_gp_kthreads_prio);
169
170 /*
171  * Number of grace periods between delays, normalized by the duration of
172  * the delay.  The longer the delay, the more the grace periods between
173  * each delay.  The reason for this normalization is that it means that,
174  * for non-zero delays, the overall slowdown of grace periods is constant
175  * regardless of the duration of the delay.  This arrangement balances
176  * the need for long delays to increase some race probabilities with the
177  * need for fast grace periods to increase other race probabilities.
178  */
179 #define PER_RCU_NODE_PERIOD 3   /* Number of grace periods between delays. */
180
181 /*
182  * Compute the mask of online CPUs for the specified rcu_node structure.
183  * This will not be stable unless the rcu_node structure's ->lock is
184  * held, but the bit corresponding to the current CPU will be stable
185  * in most contexts.
186  */
187 unsigned long rcu_rnp_online_cpus(struct rcu_node *rnp)
188 {
189         return READ_ONCE(rnp->qsmaskinitnext);
190 }
191
192 /*
193  * Return true if an RCU grace period is in progress.  The READ_ONCE()s
194  * permit this function to be invoked without holding the root rcu_node
195  * structure's ->lock, but of course results can be subject to change.
196  */
197 static int rcu_gp_in_progress(void)
198 {
199         return rcu_seq_state(rcu_seq_current(&rcu_state.gp_seq));
200 }
201
202 /*
203  * Return the number of callbacks queued on the specified CPU.
204  * Handles both the nocbs and normal cases.
205  */
206 static long rcu_get_n_cbs_cpu(int cpu)
207 {
208         struct rcu_data *rdp = per_cpu_ptr(&rcu_data, cpu);
209
210         if (rcu_segcblist_is_enabled(&rdp->cblist)) /* Online normal CPU? */
211                 return rcu_segcblist_n_cbs(&rdp->cblist);
212         return rcu_get_n_cbs_nocb_cpu(rdp); /* Works for offline, too. */
213 }
214
215 void rcu_softirq_qs(void)
216 {
217         rcu_qs();
218         rcu_preempt_deferred_qs(current);
219 }
220
221 /*
222  * Record entry into an extended quiescent state.  This is only to be
223  * called when not already in an extended quiescent state.
224  */
225 static void rcu_dynticks_eqs_enter(void)
226 {
227         struct rcu_data *rdp = this_cpu_ptr(&rcu_data);
228         int seq;
229
230         /*
231          * CPUs seeing atomic_add_return() must see prior RCU read-side
232          * critical sections, and we also must force ordering with the
233          * next idle sojourn.
234          */
235         seq = atomic_add_return(RCU_DYNTICK_CTRL_CTR, &rdp->dynticks);
236         /* Better be in an extended quiescent state! */
237         WARN_ON_ONCE(IS_ENABLED(CONFIG_RCU_EQS_DEBUG) &&
238                      (seq & RCU_DYNTICK_CTRL_CTR));
239         /* Better not have special action (TLB flush) pending! */
240         WARN_ON_ONCE(IS_ENABLED(CONFIG_RCU_EQS_DEBUG) &&
241                      (seq & RCU_DYNTICK_CTRL_MASK));
242 }
243
244 /*
245  * Record exit from an extended quiescent state.  This is only to be
246  * called from an extended quiescent state.
247  */
248 static void rcu_dynticks_eqs_exit(void)
249 {
250         struct rcu_data *rdp = this_cpu_ptr(&rcu_data);
251         int seq;
252
253         /*
254          * CPUs seeing atomic_add_return() must see prior idle sojourns,
255          * and we also must force ordering with the next RCU read-side
256          * critical section.
257          */
258         seq = atomic_add_return(RCU_DYNTICK_CTRL_CTR, &rdp->dynticks);
259         WARN_ON_ONCE(IS_ENABLED(CONFIG_RCU_EQS_DEBUG) &&
260                      !(seq & RCU_DYNTICK_CTRL_CTR));
261         if (seq & RCU_DYNTICK_CTRL_MASK) {
262                 atomic_andnot(RCU_DYNTICK_CTRL_MASK, &rdp->dynticks);
263                 smp_mb__after_atomic(); /* _exit after clearing mask. */
264                 /* Prefer duplicate flushes to losing a flush. */
265                 rcu_eqs_special_exit();
266         }
267 }
268
269 /*
270  * Reset the current CPU's ->dynticks counter to indicate that the
271  * newly onlined CPU is no longer in an extended quiescent state.
272  * This will either leave the counter unchanged, or increment it
273  * to the next non-quiescent value.
274  *
275  * The non-atomic test/increment sequence works because the upper bits
276  * of the ->dynticks counter are manipulated only by the corresponding CPU,
277  * or when the corresponding CPU is offline.
278  */
279 static void rcu_dynticks_eqs_online(void)
280 {
281         struct rcu_data *rdp = this_cpu_ptr(&rcu_data);
282
283         if (atomic_read(&rdp->dynticks) & RCU_DYNTICK_CTRL_CTR)
284                 return;
285         atomic_add(RCU_DYNTICK_CTRL_CTR, &rdp->dynticks);
286 }
287
288 /*
289  * Is the current CPU in an extended quiescent state?
290  *
291  * No ordering, as we are sampling CPU-local information.
292  */
293 bool rcu_dynticks_curr_cpu_in_eqs(void)
294 {
295         struct rcu_data *rdp = this_cpu_ptr(&rcu_data);
296
297         return !(atomic_read(&rdp->dynticks) & RCU_DYNTICK_CTRL_CTR);
298 }
299
300 /*
301  * Snapshot the ->dynticks counter with full ordering so as to allow
302  * stable comparison of this counter with past and future snapshots.
303  */
304 int rcu_dynticks_snap(struct rcu_data *rdp)
305 {
306         int snap = atomic_add_return(0, &rdp->dynticks);
307
308         return snap & ~RCU_DYNTICK_CTRL_MASK;
309 }
310
311 /*
312  * Return true if the snapshot returned from rcu_dynticks_snap()
313  * indicates that RCU is in an extended quiescent state.
314  */
315 static bool rcu_dynticks_in_eqs(int snap)
316 {
317         return !(snap & RCU_DYNTICK_CTRL_CTR);
318 }
319
320 /*
321  * Return true if the CPU corresponding to the specified rcu_data
322  * structure has spent some time in an extended quiescent state since
323  * rcu_dynticks_snap() returned the specified snapshot.
324  */
325 static bool rcu_dynticks_in_eqs_since(struct rcu_data *rdp, int snap)
326 {
327         return snap != rcu_dynticks_snap(rdp);
328 }
329
330 /*
331  * Set the special (bottom) bit of the specified CPU so that it
332  * will take special action (such as flushing its TLB) on the
333  * next exit from an extended quiescent state.  Returns true if
334  * the bit was successfully set, or false if the CPU was not in
335  * an extended quiescent state.
336  */
337 bool rcu_eqs_special_set(int cpu)
338 {
339         int old;
340         int new;
341         struct rcu_data *rdp = &per_cpu(rcu_data, cpu);
342
343         do {
344                 old = atomic_read(&rdp->dynticks);
345                 if (old & RCU_DYNTICK_CTRL_CTR)
346                         return false;
347                 new = old | RCU_DYNTICK_CTRL_MASK;
348         } while (atomic_cmpxchg(&rdp->dynticks, old, new) != old);
349         return true;
350 }
351
352 /*
353  * Let the RCU core know that this CPU has gone through the scheduler,
354  * which is a quiescent state.  This is called when the need for a
355  * quiescent state is urgent, so we burn an atomic operation and full
356  * memory barriers to let the RCU core know about it, regardless of what
357  * this CPU might (or might not) do in the near future.
358  *
359  * We inform the RCU core by emulating a zero-duration dyntick-idle period.
360  *
361  * The caller must have disabled interrupts and must not be idle.
362  */
363 static void __maybe_unused rcu_momentary_dyntick_idle(void)
364 {
365         int special;
366
367         raw_cpu_write(rcu_data.rcu_need_heavy_qs, false);
368         special = atomic_add_return(2 * RCU_DYNTICK_CTRL_CTR,
369                                     &this_cpu_ptr(&rcu_data)->dynticks);
370         /* It is illegal to call this from idle state. */
371         WARN_ON_ONCE(!(special & RCU_DYNTICK_CTRL_CTR));
372         rcu_preempt_deferred_qs(current);
373 }
374
375 /**
376  * rcu_is_cpu_rrupt_from_idle - see if idle or immediately interrupted from idle
377  *
378  * If the current CPU is idle or running at a first-level (not nested)
379  * interrupt from idle, return true.  The caller must have at least
380  * disabled preemption.
381  */
382 static int rcu_is_cpu_rrupt_from_idle(void)
383 {
384         return __this_cpu_read(rcu_data.dynticks_nesting) <= 0 &&
385                __this_cpu_read(rcu_data.dynticks_nmi_nesting) <= 1;
386 }
387
388 #define DEFAULT_RCU_BLIMIT 10     /* Maximum callbacks per rcu_do_batch. */
389 static long blimit = DEFAULT_RCU_BLIMIT;
390 #define DEFAULT_RCU_QHIMARK 10000 /* If this many pending, ignore blimit. */
391 static long qhimark = DEFAULT_RCU_QHIMARK;
392 #define DEFAULT_RCU_QLOMARK 100   /* Once only this many pending, use blimit. */
393 static long qlowmark = DEFAULT_RCU_QLOMARK;
394
395 module_param(blimit, long, 0444);
396 module_param(qhimark, long, 0444);
397 module_param(qlowmark, long, 0444);
398
399 static ulong jiffies_till_first_fqs = ULONG_MAX;
400 static ulong jiffies_till_next_fqs = ULONG_MAX;
401 static bool rcu_kick_kthreads;
402
403 /*
404  * How long the grace period must be before we start recruiting
405  * quiescent-state help from rcu_note_context_switch().
406  */
407 static ulong jiffies_till_sched_qs = ULONG_MAX;
408 module_param(jiffies_till_sched_qs, ulong, 0444);
409 static ulong jiffies_to_sched_qs; /* Adjusted version of above if not default */
410 module_param(jiffies_to_sched_qs, ulong, 0444); /* Display only! */
411
412 /*
413  * Make sure that we give the grace-period kthread time to detect any
414  * idle CPUs before taking active measures to force quiescent states.
415  * However, don't go below 100 milliseconds, adjusted upwards for really
416  * large systems.
417  */
418 static void adjust_jiffies_till_sched_qs(void)
419 {
420         unsigned long j;
421
422         /* If jiffies_till_sched_qs was specified, respect the request. */
423         if (jiffies_till_sched_qs != ULONG_MAX) {
424                 WRITE_ONCE(jiffies_to_sched_qs, jiffies_till_sched_qs);
425                 return;
426         }
427         j = READ_ONCE(jiffies_till_first_fqs) +
428                       2 * READ_ONCE(jiffies_till_next_fqs);
429         if (j < HZ / 10 + nr_cpu_ids / RCU_JIFFIES_FQS_DIV)
430                 j = HZ / 10 + nr_cpu_ids / RCU_JIFFIES_FQS_DIV;
431         pr_info("RCU calculated value of scheduler-enlistment delay is %ld jiffies.\n", j);
432         WRITE_ONCE(jiffies_to_sched_qs, j);
433 }
434
435 static int param_set_first_fqs_jiffies(const char *val, const struct kernel_param *kp)
436 {
437         ulong j;
438         int ret = kstrtoul(val, 0, &j);
439
440         if (!ret) {
441                 WRITE_ONCE(*(ulong *)kp->arg, (j > HZ) ? HZ : j);
442                 adjust_jiffies_till_sched_qs();
443         }
444         return ret;
445 }
446
447 static int param_set_next_fqs_jiffies(const char *val, const struct kernel_param *kp)
448 {
449         ulong j;
450         int ret = kstrtoul(val, 0, &j);
451
452         if (!ret) {
453                 WRITE_ONCE(*(ulong *)kp->arg, (j > HZ) ? HZ : (j ?: 1));
454                 adjust_jiffies_till_sched_qs();
455         }
456         return ret;
457 }
458
459 static struct kernel_param_ops first_fqs_jiffies_ops = {
460         .set = param_set_first_fqs_jiffies,
461         .get = param_get_ulong,
462 };
463
464 static struct kernel_param_ops next_fqs_jiffies_ops = {
465         .set = param_set_next_fqs_jiffies,
466         .get = param_get_ulong,
467 };
468
469 module_param_cb(jiffies_till_first_fqs, &first_fqs_jiffies_ops, &jiffies_till_first_fqs, 0644);
470 module_param_cb(jiffies_till_next_fqs, &next_fqs_jiffies_ops, &jiffies_till_next_fqs, 0644);
471 module_param(rcu_kick_kthreads, bool, 0644);
472
473 static void force_qs_rnp(int (*f)(struct rcu_data *rdp));
474 static int rcu_pending(void);
475
476 /*
477  * Return the number of RCU GPs completed thus far for debug & stats.
478  */
479 unsigned long rcu_get_gp_seq(void)
480 {
481         return READ_ONCE(rcu_state.gp_seq);
482 }
483 EXPORT_SYMBOL_GPL(rcu_get_gp_seq);
484
485 /*
486  * Return the number of RCU expedited batches completed thus far for
487  * debug & stats.  Odd numbers mean that a batch is in progress, even
488  * numbers mean idle.  The value returned will thus be roughly double
489  * the cumulative batches since boot.
490  */
491 unsigned long rcu_exp_batches_completed(void)
492 {
493         return rcu_state.expedited_sequence;
494 }
495 EXPORT_SYMBOL_GPL(rcu_exp_batches_completed);
496
497 /*
498  * Return the root node of the rcu_state structure.
499  */
500 static struct rcu_node *rcu_get_root(void)
501 {
502         return &rcu_state.node[0];
503 }
504
505 /*
506  * Convert a ->gp_state value to a character string.
507  */
508 static const char *gp_state_getname(short gs)
509 {
510         if (gs < 0 || gs >= ARRAY_SIZE(gp_state_names))
511                 return "???";
512         return gp_state_names[gs];
513 }
514
515 /*
516  * Show the state of the grace-period kthreads.
517  */
518 void show_rcu_gp_kthreads(void)
519 {
520         int cpu;
521         unsigned long j;
522         unsigned long ja;
523         unsigned long jr;
524         unsigned long jw;
525         struct rcu_data *rdp;
526         struct rcu_node *rnp;
527
528         j = jiffies;
529         ja = j - READ_ONCE(rcu_state.gp_activity);
530         jr = j - READ_ONCE(rcu_state.gp_req_activity);
531         jw = j - READ_ONCE(rcu_state.gp_wake_time);
532         pr_info("%s: wait state: %s(%d) ->state: %#lx delta ->gp_activity %lu ->gp_req_activity %lu ->gp_wake_time %lu ->gp_wake_seq %ld ->gp_seq %ld ->gp_seq_needed %ld ->gp_flags %#x\n",
533                 rcu_state.name, gp_state_getname(rcu_state.gp_state),
534                 rcu_state.gp_state,
535                 rcu_state.gp_kthread ? rcu_state.gp_kthread->state : 0x1ffffL,
536                 ja, jr, jw, (long)READ_ONCE(rcu_state.gp_wake_seq),
537                 (long)READ_ONCE(rcu_state.gp_seq),
538                 (long)READ_ONCE(rcu_get_root()->gp_seq_needed),
539                 READ_ONCE(rcu_state.gp_flags));
540         rcu_for_each_node_breadth_first(rnp) {
541                 if (ULONG_CMP_GE(rcu_state.gp_seq, rnp->gp_seq_needed))
542                         continue;
543                 pr_info("\trcu_node %d:%d ->gp_seq %ld ->gp_seq_needed %ld\n",
544                         rnp->grplo, rnp->grphi, (long)rnp->gp_seq,
545                         (long)rnp->gp_seq_needed);
546                 if (!rcu_is_leaf_node(rnp))
547                         continue;
548                 for_each_leaf_node_possible_cpu(rnp, cpu) {
549                         rdp = per_cpu_ptr(&rcu_data, cpu);
550                         if (rdp->gpwrap ||
551                             ULONG_CMP_GE(rcu_state.gp_seq,
552                                          rdp->gp_seq_needed))
553                                 continue;
554                         pr_info("\tcpu %d ->gp_seq_needed %ld\n",
555                                 cpu, (long)rdp->gp_seq_needed);
556                 }
557         }
558         /* sched_show_task(rcu_state.gp_kthread); */
559 }
560 EXPORT_SYMBOL_GPL(show_rcu_gp_kthreads);
561
562 /* Dump grace-period-request information due to commandeered sysrq. */
563 static void sysrq_show_rcu(int key)
564 {
565         show_rcu_gp_kthreads();
566 }
567
568 static struct sysrq_key_op sysrq_rcudump_op = {
569         .handler = sysrq_show_rcu,
570         .help_msg = "show-rcu(y)",
571         .action_msg = "Show RCU tree",
572         .enable_mask = SYSRQ_ENABLE_DUMP,
573 };
574
575 static int __init rcu_sysrq_init(void)
576 {
577         if (sysrq_rcu)
578                 return register_sysrq_key('y', &sysrq_rcudump_op);
579         return 0;
580 }
581 early_initcall(rcu_sysrq_init);
582
583 /*
584  * Send along grace-period-related data for rcutorture diagnostics.
585  */
586 void rcutorture_get_gp_data(enum rcutorture_type test_type, int *flags,
587                             unsigned long *gp_seq)
588 {
589         switch (test_type) {
590         case RCU_FLAVOR:
591                 *flags = READ_ONCE(rcu_state.gp_flags);
592                 *gp_seq = rcu_seq_current(&rcu_state.gp_seq);
593                 break;
594         default:
595                 break;
596         }
597 }
598 EXPORT_SYMBOL_GPL(rcutorture_get_gp_data);
599
600 /*
601  * Enter an RCU extended quiescent state, which can be either the
602  * idle loop or adaptive-tickless usermode execution.
603  *
604  * We crowbar the ->dynticks_nmi_nesting field to zero to allow for
605  * the possibility of usermode upcalls having messed up our count
606  * of interrupt nesting level during the prior busy period.
607  */
608 static void rcu_eqs_enter(bool user)
609 {
610         struct rcu_data *rdp = this_cpu_ptr(&rcu_data);
611
612         WARN_ON_ONCE(rdp->dynticks_nmi_nesting != DYNTICK_IRQ_NONIDLE);
613         WRITE_ONCE(rdp->dynticks_nmi_nesting, 0);
614         WARN_ON_ONCE(IS_ENABLED(CONFIG_RCU_EQS_DEBUG) &&
615                      rdp->dynticks_nesting == 0);
616         if (rdp->dynticks_nesting != 1) {
617                 rdp->dynticks_nesting--;
618                 return;
619         }
620
621         lockdep_assert_irqs_disabled();
622         trace_rcu_dyntick(TPS("Start"), rdp->dynticks_nesting, 0, rdp->dynticks);
623         WARN_ON_ONCE(IS_ENABLED(CONFIG_RCU_EQS_DEBUG) && !user && !is_idle_task(current));
624         rdp = this_cpu_ptr(&rcu_data);
625         do_nocb_deferred_wakeup(rdp);
626         rcu_prepare_for_idle();
627         rcu_preempt_deferred_qs(current);
628         WRITE_ONCE(rdp->dynticks_nesting, 0); /* Avoid irq-access tearing. */
629         rcu_dynticks_eqs_enter();
630         rcu_dynticks_task_enter();
631 }
632
633 /**
634  * rcu_idle_enter - inform RCU that current CPU is entering idle
635  *
636  * Enter idle mode, in other words, -leave- the mode in which RCU
637  * read-side critical sections can occur.  (Though RCU read-side
638  * critical sections can occur in irq handlers in idle, a possibility
639  * handled by irq_enter() and irq_exit().)
640  *
641  * If you add or remove a call to rcu_idle_enter(), be sure to test with
642  * CONFIG_RCU_EQS_DEBUG=y.
643  */
644 void rcu_idle_enter(void)
645 {
646         lockdep_assert_irqs_disabled();
647         rcu_eqs_enter(false);
648 }
649
650 #ifdef CONFIG_NO_HZ_FULL
651 /**
652  * rcu_user_enter - inform RCU that we are resuming userspace.
653  *
654  * Enter RCU idle mode right before resuming userspace.  No use of RCU
655  * is permitted between this call and rcu_user_exit(). This way the
656  * CPU doesn't need to maintain the tick for RCU maintenance purposes
657  * when the CPU runs in userspace.
658  *
659  * If you add or remove a call to rcu_user_enter(), be sure to test with
660  * CONFIG_RCU_EQS_DEBUG=y.
661  */
662 void rcu_user_enter(void)
663 {
664         lockdep_assert_irqs_disabled();
665         rcu_eqs_enter(true);
666 }
667 #endif /* CONFIG_NO_HZ_FULL */
668
669 /*
670  * If we are returning from the outermost NMI handler that interrupted an
671  * RCU-idle period, update rdp->dynticks and rdp->dynticks_nmi_nesting
672  * to let the RCU grace-period handling know that the CPU is back to
673  * being RCU-idle.
674  *
675  * If you add or remove a call to rcu_nmi_exit_common(), be sure to test
676  * with CONFIG_RCU_EQS_DEBUG=y.
677  */
678 static __always_inline void rcu_nmi_exit_common(bool irq)
679 {
680         struct rcu_data *rdp = this_cpu_ptr(&rcu_data);
681
682         /*
683          * Check for ->dynticks_nmi_nesting underflow and bad ->dynticks.
684          * (We are exiting an NMI handler, so RCU better be paying attention
685          * to us!)
686          */
687         WARN_ON_ONCE(rdp->dynticks_nmi_nesting <= 0);
688         WARN_ON_ONCE(rcu_dynticks_curr_cpu_in_eqs());
689
690         /*
691          * If the nesting level is not 1, the CPU wasn't RCU-idle, so
692          * leave it in non-RCU-idle state.
693          */
694         if (rdp->dynticks_nmi_nesting != 1) {
695                 trace_rcu_dyntick(TPS("--="), rdp->dynticks_nmi_nesting, rdp->dynticks_nmi_nesting - 2, rdp->dynticks);
696                 WRITE_ONCE(rdp->dynticks_nmi_nesting, /* No store tearing. */
697                            rdp->dynticks_nmi_nesting - 2);
698                 return;
699         }
700
701         /* This NMI interrupted an RCU-idle CPU, restore RCU-idleness. */
702         trace_rcu_dyntick(TPS("Startirq"), rdp->dynticks_nmi_nesting, 0, rdp->dynticks);
703         WRITE_ONCE(rdp->dynticks_nmi_nesting, 0); /* Avoid store tearing. */
704
705         if (irq)
706                 rcu_prepare_for_idle();
707
708         rcu_dynticks_eqs_enter();
709
710         if (irq)
711                 rcu_dynticks_task_enter();
712 }
713
714 /**
715  * rcu_nmi_exit - inform RCU of exit from NMI context
716  *
717  * If you add or remove a call to rcu_nmi_exit(), be sure to test
718  * with CONFIG_RCU_EQS_DEBUG=y.
719  */
720 void rcu_nmi_exit(void)
721 {
722         rcu_nmi_exit_common(false);
723 }
724
725 /**
726  * rcu_irq_exit - inform RCU that current CPU is exiting irq towards idle
727  *
728  * Exit from an interrupt handler, which might possibly result in entering
729  * idle mode, in other words, leaving the mode in which read-side critical
730  * sections can occur.  The caller must have disabled interrupts.
731  *
732  * This code assumes that the idle loop never does anything that might
733  * result in unbalanced calls to irq_enter() and irq_exit().  If your
734  * architecture's idle loop violates this assumption, RCU will give you what
735  * you deserve, good and hard.  But very infrequently and irreproducibly.
736  *
737  * Use things like work queues to work around this limitation.
738  *
739  * You have been warned.
740  *
741  * If you add or remove a call to rcu_irq_exit(), be sure to test with
742  * CONFIG_RCU_EQS_DEBUG=y.
743  */
744 void rcu_irq_exit(void)
745 {
746         lockdep_assert_irqs_disabled();
747         rcu_nmi_exit_common(true);
748 }
749
750 /*
751  * Wrapper for rcu_irq_exit() where interrupts are enabled.
752  *
753  * If you add or remove a call to rcu_irq_exit_irqson(), be sure to test
754  * with CONFIG_RCU_EQS_DEBUG=y.
755  */
756 void rcu_irq_exit_irqson(void)
757 {
758         unsigned long flags;
759
760         local_irq_save(flags);
761         rcu_irq_exit();
762         local_irq_restore(flags);
763 }
764
765 /*
766  * Exit an RCU extended quiescent state, which can be either the
767  * idle loop or adaptive-tickless usermode execution.
768  *
769  * We crowbar the ->dynticks_nmi_nesting field to DYNTICK_IRQ_NONIDLE to
770  * allow for the possibility of usermode upcalls messing up our count of
771  * interrupt nesting level during the busy period that is just now starting.
772  */
773 static void rcu_eqs_exit(bool user)
774 {
775         struct rcu_data *rdp;
776         long oldval;
777
778         lockdep_assert_irqs_disabled();
779         rdp = this_cpu_ptr(&rcu_data);
780         oldval = rdp->dynticks_nesting;
781         WARN_ON_ONCE(IS_ENABLED(CONFIG_RCU_EQS_DEBUG) && oldval < 0);
782         if (oldval) {
783                 rdp->dynticks_nesting++;
784                 return;
785         }
786         rcu_dynticks_task_exit();
787         rcu_dynticks_eqs_exit();
788         rcu_cleanup_after_idle();
789         trace_rcu_dyntick(TPS("End"), rdp->dynticks_nesting, 1, rdp->dynticks);
790         WARN_ON_ONCE(IS_ENABLED(CONFIG_RCU_EQS_DEBUG) && !user && !is_idle_task(current));
791         WRITE_ONCE(rdp->dynticks_nesting, 1);
792         WARN_ON_ONCE(rdp->dynticks_nmi_nesting);
793         WRITE_ONCE(rdp->dynticks_nmi_nesting, DYNTICK_IRQ_NONIDLE);
794 }
795
796 /**
797  * rcu_idle_exit - inform RCU that current CPU is leaving idle
798  *
799  * Exit idle mode, in other words, -enter- the mode in which RCU
800  * read-side critical sections can occur.
801  *
802  * If you add or remove a call to rcu_idle_exit(), be sure to test with
803  * CONFIG_RCU_EQS_DEBUG=y.
804  */
805 void rcu_idle_exit(void)
806 {
807         unsigned long flags;
808
809         local_irq_save(flags);
810         rcu_eqs_exit(false);
811         local_irq_restore(flags);
812 }
813
814 #ifdef CONFIG_NO_HZ_FULL
815 /**
816  * rcu_user_exit - inform RCU that we are exiting userspace.
817  *
818  * Exit RCU idle mode while entering the kernel because it can
819  * run a RCU read side critical section anytime.
820  *
821  * If you add or remove a call to rcu_user_exit(), be sure to test with
822  * CONFIG_RCU_EQS_DEBUG=y.
823  */
824 void rcu_user_exit(void)
825 {
826         rcu_eqs_exit(1);
827 }
828 #endif /* CONFIG_NO_HZ_FULL */
829
830 /**
831  * rcu_nmi_enter_common - inform RCU of entry to NMI context
832  * @irq: Is this call from rcu_irq_enter?
833  *
834  * If the CPU was idle from RCU's viewpoint, update rdp->dynticks and
835  * rdp->dynticks_nmi_nesting to let the RCU grace-period handling know
836  * that the CPU is active.  This implementation permits nested NMIs, as
837  * long as the nesting level does not overflow an int.  (You will probably
838  * run out of stack space first.)
839  *
840  * If you add or remove a call to rcu_nmi_enter_common(), be sure to test
841  * with CONFIG_RCU_EQS_DEBUG=y.
842  */
843 static __always_inline void rcu_nmi_enter_common(bool irq)
844 {
845         struct rcu_data *rdp = this_cpu_ptr(&rcu_data);
846         long incby = 2;
847
848         /* Complain about underflow. */
849         WARN_ON_ONCE(rdp->dynticks_nmi_nesting < 0);
850
851         /*
852          * If idle from RCU viewpoint, atomically increment ->dynticks
853          * to mark non-idle and increment ->dynticks_nmi_nesting by one.
854          * Otherwise, increment ->dynticks_nmi_nesting by two.  This means
855          * if ->dynticks_nmi_nesting is equal to one, we are guaranteed
856          * to be in the outermost NMI handler that interrupted an RCU-idle
857          * period (observation due to Andy Lutomirski).
858          */
859         if (rcu_dynticks_curr_cpu_in_eqs()) {
860
861                 if (irq)
862                         rcu_dynticks_task_exit();
863
864                 rcu_dynticks_eqs_exit();
865
866                 if (irq)
867                         rcu_cleanup_after_idle();
868
869                 incby = 1;
870         }
871         trace_rcu_dyntick(incby == 1 ? TPS("Endirq") : TPS("++="),
872                           rdp->dynticks_nmi_nesting,
873                           rdp->dynticks_nmi_nesting + incby, rdp->dynticks);
874         WRITE_ONCE(rdp->dynticks_nmi_nesting, /* Prevent store tearing. */
875                    rdp->dynticks_nmi_nesting + incby);
876         barrier();
877 }
878
879 /**
880  * rcu_nmi_enter - inform RCU of entry to NMI context
881  */
882 void rcu_nmi_enter(void)
883 {
884         rcu_nmi_enter_common(false);
885 }
886 NOKPROBE_SYMBOL(rcu_nmi_enter);
887
888 /**
889  * rcu_irq_enter - inform RCU that current CPU is entering irq away from idle
890  *
891  * Enter an interrupt handler, which might possibly result in exiting
892  * idle mode, in other words, entering the mode in which read-side critical
893  * sections can occur.  The caller must have disabled interrupts.
894  *
895  * Note that the Linux kernel is fully capable of entering an interrupt
896  * handler that it never exits, for example when doing upcalls to user mode!
897  * This code assumes that the idle loop never does upcalls to user mode.
898  * If your architecture's idle loop does do upcalls to user mode (or does
899  * anything else that results in unbalanced calls to the irq_enter() and
900  * irq_exit() functions), RCU will give you what you deserve, good and hard.
901  * But very infrequently and irreproducibly.
902  *
903  * Use things like work queues to work around this limitation.
904  *
905  * You have been warned.
906  *
907  * If you add or remove a call to rcu_irq_enter(), be sure to test with
908  * CONFIG_RCU_EQS_DEBUG=y.
909  */
910 void rcu_irq_enter(void)
911 {
912         lockdep_assert_irqs_disabled();
913         rcu_nmi_enter_common(true);
914 }
915
916 /*
917  * Wrapper for rcu_irq_enter() where interrupts are enabled.
918  *
919  * If you add or remove a call to rcu_irq_enter_irqson(), be sure to test
920  * with CONFIG_RCU_EQS_DEBUG=y.
921  */
922 void rcu_irq_enter_irqson(void)
923 {
924         unsigned long flags;
925
926         local_irq_save(flags);
927         rcu_irq_enter();
928         local_irq_restore(flags);
929 }
930
931 /**
932  * rcu_is_watching - see if RCU thinks that the current CPU is not idle
933  *
934  * Return true if RCU is watching the running CPU, which means that this
935  * CPU can safely enter RCU read-side critical sections.  In other words,
936  * if the current CPU is not in its idle loop or is in an interrupt or
937  * NMI handler, return true.
938  */
939 bool notrace rcu_is_watching(void)
940 {
941         bool ret;
942
943         preempt_disable_notrace();
944         ret = !rcu_dynticks_curr_cpu_in_eqs();
945         preempt_enable_notrace();
946         return ret;
947 }
948 EXPORT_SYMBOL_GPL(rcu_is_watching);
949
950 /*
951  * If a holdout task is actually running, request an urgent quiescent
952  * state from its CPU.  This is unsynchronized, so migrations can cause
953  * the request to go to the wrong CPU.  Which is OK, all that will happen
954  * is that the CPU's next context switch will be a bit slower and next
955  * time around this task will generate another request.
956  */
957 void rcu_request_urgent_qs_task(struct task_struct *t)
958 {
959         int cpu;
960
961         barrier();
962         cpu = task_cpu(t);
963         if (!task_curr(t))
964                 return; /* This task is not running on that CPU. */
965         smp_store_release(per_cpu_ptr(&rcu_data.rcu_urgent_qs, cpu), true);
966 }
967
968 #if defined(CONFIG_PROVE_RCU) && defined(CONFIG_HOTPLUG_CPU)
969
970 /*
971  * Is the current CPU online as far as RCU is concerned?
972  *
973  * Disable preemption to avoid false positives that could otherwise
974  * happen due to the current CPU number being sampled, this task being
975  * preempted, its old CPU being taken offline, resuming on some other CPU,
976  * then determining that its old CPU is now offline.
977  *
978  * Disable checking if in an NMI handler because we cannot safely
979  * report errors from NMI handlers anyway.  In addition, it is OK to use
980  * RCU on an offline processor during initial boot, hence the check for
981  * rcu_scheduler_fully_active.
982  */
983 bool rcu_lockdep_current_cpu_online(void)
984 {
985         struct rcu_data *rdp;
986         struct rcu_node *rnp;
987         bool ret = false;
988
989         if (in_nmi() || !rcu_scheduler_fully_active)
990                 return true;
991         preempt_disable();
992         rdp = this_cpu_ptr(&rcu_data);
993         rnp = rdp->mynode;
994         if (rdp->grpmask & rcu_rnp_online_cpus(rnp))
995                 ret = true;
996         preempt_enable();
997         return ret;
998 }
999 EXPORT_SYMBOL_GPL(rcu_lockdep_current_cpu_online);
1000
1001 #endif /* #if defined(CONFIG_PROVE_RCU) && defined(CONFIG_HOTPLUG_CPU) */
1002
1003 /*
1004  * We are reporting a quiescent state on behalf of some other CPU, so
1005  * it is our responsibility to check for and handle potential overflow
1006  * of the rcu_node ->gp_seq counter with respect to the rcu_data counters.
1007  * After all, the CPU might be in deep idle state, and thus executing no
1008  * code whatsoever.
1009  */
1010 static void rcu_gpnum_ovf(struct rcu_node *rnp, struct rcu_data *rdp)
1011 {
1012         raw_lockdep_assert_held_rcu_node(rnp);
1013         if (ULONG_CMP_LT(rcu_seq_current(&rdp->gp_seq) + ULONG_MAX / 4,
1014                          rnp->gp_seq))
1015                 WRITE_ONCE(rdp->gpwrap, true);
1016         if (ULONG_CMP_LT(rdp->rcu_iw_gp_seq + ULONG_MAX / 4, rnp->gp_seq))
1017                 rdp->rcu_iw_gp_seq = rnp->gp_seq + ULONG_MAX / 4;
1018 }
1019
1020 /*
1021  * Snapshot the specified CPU's dynticks counter so that we can later
1022  * credit them with an implicit quiescent state.  Return 1 if this CPU
1023  * is in dynticks idle mode, which is an extended quiescent state.
1024  */
1025 static int dyntick_save_progress_counter(struct rcu_data *rdp)
1026 {
1027         rdp->dynticks_snap = rcu_dynticks_snap(rdp);
1028         if (rcu_dynticks_in_eqs(rdp->dynticks_snap)) {
1029                 trace_rcu_fqs(rcu_state.name, rdp->gp_seq, rdp->cpu, TPS("dti"));
1030                 rcu_gpnum_ovf(rdp->mynode, rdp);
1031                 return 1;
1032         }
1033         return 0;
1034 }
1035
1036 /*
1037  * Handler for the irq_work request posted when a grace period has
1038  * gone on for too long, but not yet long enough for an RCU CPU
1039  * stall warning.  Set state appropriately, but just complain if
1040  * there is unexpected state on entry.
1041  */
1042 static void rcu_iw_handler(struct irq_work *iwp)
1043 {
1044         struct rcu_data *rdp;
1045         struct rcu_node *rnp;
1046
1047         rdp = container_of(iwp, struct rcu_data, rcu_iw);
1048         rnp = rdp->mynode;
1049         raw_spin_lock_rcu_node(rnp);
1050         if (!WARN_ON_ONCE(!rdp->rcu_iw_pending)) {
1051                 rdp->rcu_iw_gp_seq = rnp->gp_seq;
1052                 rdp->rcu_iw_pending = false;
1053         }
1054         raw_spin_unlock_rcu_node(rnp);
1055 }
1056
1057 /*
1058  * Return true if the specified CPU has passed through a quiescent
1059  * state by virtue of being in or having passed through an dynticks
1060  * idle state since the last call to dyntick_save_progress_counter()
1061  * for this same CPU, or by virtue of having been offline.
1062  */
1063 static int rcu_implicit_dynticks_qs(struct rcu_data *rdp)
1064 {
1065         unsigned long jtsq;
1066         bool *rnhqp;
1067         bool *ruqp;
1068         struct rcu_node *rnp = rdp->mynode;
1069
1070         /*
1071          * If the CPU passed through or entered a dynticks idle phase with
1072          * no active irq/NMI handlers, then we can safely pretend that the CPU
1073          * already acknowledged the request to pass through a quiescent
1074          * state.  Either way, that CPU cannot possibly be in an RCU
1075          * read-side critical section that started before the beginning
1076          * of the current RCU grace period.
1077          */
1078         if (rcu_dynticks_in_eqs_since(rdp, rdp->dynticks_snap)) {
1079                 trace_rcu_fqs(rcu_state.name, rdp->gp_seq, rdp->cpu, TPS("dti"));
1080                 rcu_gpnum_ovf(rnp, rdp);
1081                 return 1;
1082         }
1083
1084         /* If waiting too long on an offline CPU, complain. */
1085         if (!(rdp->grpmask & rcu_rnp_online_cpus(rnp)) &&
1086             time_after(jiffies, rcu_state.gp_start + HZ)) {
1087                 bool onl;
1088                 struct rcu_node *rnp1;
1089
1090                 WARN_ON(1);  /* Offline CPUs are supposed to report QS! */
1091                 pr_info("%s: grp: %d-%d level: %d ->gp_seq %ld ->completedqs %ld\n",
1092                         __func__, rnp->grplo, rnp->grphi, rnp->level,
1093                         (long)rnp->gp_seq, (long)rnp->completedqs);
1094                 for (rnp1 = rnp; rnp1; rnp1 = rnp1->parent)
1095                         pr_info("%s: %d:%d ->qsmask %#lx ->qsmaskinit %#lx ->qsmaskinitnext %#lx ->rcu_gp_init_mask %#lx\n",
1096                                 __func__, rnp1->grplo, rnp1->grphi, rnp1->qsmask, rnp1->qsmaskinit, rnp1->qsmaskinitnext, rnp1->rcu_gp_init_mask);
1097                 onl = !!(rdp->grpmask & rcu_rnp_online_cpus(rnp));
1098                 pr_info("%s %d: %c online: %ld(%d) offline: %ld(%d)\n",
1099                         __func__, rdp->cpu, ".o"[onl],
1100                         (long)rdp->rcu_onl_gp_seq, rdp->rcu_onl_gp_flags,
1101                         (long)rdp->rcu_ofl_gp_seq, rdp->rcu_ofl_gp_flags);
1102                 return 1; /* Break things loose after complaining. */
1103         }
1104
1105         /*
1106          * A CPU running for an extended time within the kernel can
1107          * delay RCU grace periods: (1) At age jiffies_to_sched_qs,
1108          * set .rcu_urgent_qs, (2) At age 2*jiffies_to_sched_qs, set
1109          * both .rcu_need_heavy_qs and .rcu_urgent_qs.  Note that the
1110          * unsynchronized assignments to the per-CPU rcu_need_heavy_qs
1111          * variable are safe because the assignments are repeated if this
1112          * CPU failed to pass through a quiescent state.  This code
1113          * also checks .jiffies_resched in case jiffies_to_sched_qs
1114          * is set way high.
1115          */
1116         jtsq = READ_ONCE(jiffies_to_sched_qs);
1117         ruqp = per_cpu_ptr(&rcu_data.rcu_urgent_qs, rdp->cpu);
1118         rnhqp = &per_cpu(rcu_data.rcu_need_heavy_qs, rdp->cpu);
1119         if (!READ_ONCE(*rnhqp) &&
1120             (time_after(jiffies, rcu_state.gp_start + jtsq * 2) ||
1121              time_after(jiffies, rcu_state.jiffies_resched))) {
1122                 WRITE_ONCE(*rnhqp, true);
1123                 /* Store rcu_need_heavy_qs before rcu_urgent_qs. */
1124                 smp_store_release(ruqp, true);
1125         } else if (time_after(jiffies, rcu_state.gp_start + jtsq)) {
1126                 WRITE_ONCE(*ruqp, true);
1127         }
1128
1129         /*
1130          * NO_HZ_FULL CPUs can run in-kernel without rcu_sched_clock_irq!
1131          * The above code handles this, but only for straight cond_resched().
1132          * And some in-kernel loops check need_resched() before calling
1133          * cond_resched(), which defeats the above code for CPUs that are
1134          * running in-kernel with scheduling-clock interrupts disabled.
1135          * So hit them over the head with the resched_cpu() hammer!
1136          */
1137         if (tick_nohz_full_cpu(rdp->cpu) &&
1138                    time_after(jiffies,
1139                               READ_ONCE(rdp->last_fqs_resched) + jtsq * 3)) {
1140                 resched_cpu(rdp->cpu);
1141                 WRITE_ONCE(rdp->last_fqs_resched, jiffies);
1142         }
1143
1144         /*
1145          * If more than halfway to RCU CPU stall-warning time, invoke
1146          * resched_cpu() more frequently to try to loosen things up a bit.
1147          * Also check to see if the CPU is getting hammered with interrupts,
1148          * but only once per grace period, just to keep the IPIs down to
1149          * a dull roar.
1150          */
1151         if (time_after(jiffies, rcu_state.jiffies_resched)) {
1152                 if (time_after(jiffies,
1153                                READ_ONCE(rdp->last_fqs_resched) + jtsq)) {
1154                         resched_cpu(rdp->cpu);
1155                         WRITE_ONCE(rdp->last_fqs_resched, jiffies);
1156                 }
1157                 if (IS_ENABLED(CONFIG_IRQ_WORK) &&
1158                     !rdp->rcu_iw_pending && rdp->rcu_iw_gp_seq != rnp->gp_seq &&
1159                     (rnp->ffmask & rdp->grpmask)) {
1160                         init_irq_work(&rdp->rcu_iw, rcu_iw_handler);
1161                         rdp->rcu_iw_pending = true;
1162                         rdp->rcu_iw_gp_seq = rnp->gp_seq;
1163                         irq_work_queue_on(&rdp->rcu_iw, rdp->cpu);
1164                 }
1165         }
1166
1167         return 0;
1168 }
1169
1170 static void record_gp_stall_check_time(void)
1171 {
1172         unsigned long j = jiffies;
1173         unsigned long j1;
1174
1175         rcu_state.gp_start = j;
1176         j1 = rcu_jiffies_till_stall_check();
1177         /* Record ->gp_start before ->jiffies_stall. */
1178         smp_store_release(&rcu_state.jiffies_stall, j + j1); /* ^^^ */
1179         rcu_state.jiffies_resched = j + j1 / 2;
1180         rcu_state.n_force_qs_gpstart = READ_ONCE(rcu_state.n_force_qs);
1181 }
1182
1183 /*
1184  * Complain about starvation of grace-period kthread.
1185  */
1186 static void rcu_check_gp_kthread_starvation(void)
1187 {
1188         struct task_struct *gpk = rcu_state.gp_kthread;
1189         unsigned long j;
1190
1191         j = jiffies - READ_ONCE(rcu_state.gp_activity);
1192         if (j > 2 * HZ) {
1193                 pr_err("%s kthread starved for %ld jiffies! g%ld f%#x %s(%d) ->state=%#lx ->cpu=%d\n",
1194                        rcu_state.name, j,
1195                        (long)rcu_seq_current(&rcu_state.gp_seq),
1196                        READ_ONCE(rcu_state.gp_flags),
1197                        gp_state_getname(rcu_state.gp_state), rcu_state.gp_state,
1198                        gpk ? gpk->state : ~0, gpk ? task_cpu(gpk) : -1);
1199                 if (gpk) {
1200                         pr_err("RCU grace-period kthread stack dump:\n");
1201                         sched_show_task(gpk);
1202                         wake_up_process(gpk);
1203                 }
1204         }
1205 }
1206
1207 /*
1208  * Dump stacks of all tasks running on stalled CPUs.  First try using
1209  * NMIs, but fall back to manual remote stack tracing on architectures
1210  * that don't support NMI-based stack dumps.  The NMI-triggered stack
1211  * traces are more accurate because they are printed by the target CPU.
1212  */
1213 static void rcu_dump_cpu_stacks(void)
1214 {
1215         int cpu;
1216         unsigned long flags;
1217         struct rcu_node *rnp;
1218
1219         rcu_for_each_leaf_node(rnp) {
1220                 raw_spin_lock_irqsave_rcu_node(rnp, flags);
1221                 for_each_leaf_node_possible_cpu(rnp, cpu)
1222                         if (rnp->qsmask & leaf_node_cpu_bit(rnp, cpu))
1223                                 if (!trigger_single_cpu_backtrace(cpu))
1224                                         dump_cpu_task(cpu);
1225                 raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
1226         }
1227 }
1228
1229 /*
1230  * If too much time has passed in the current grace period, and if
1231  * so configured, go kick the relevant kthreads.
1232  */
1233 static void rcu_stall_kick_kthreads(void)
1234 {
1235         unsigned long j;
1236
1237         if (!rcu_kick_kthreads)
1238                 return;
1239         j = READ_ONCE(rcu_state.jiffies_kick_kthreads);
1240         if (time_after(jiffies, j) && rcu_state.gp_kthread &&
1241             (rcu_gp_in_progress() || READ_ONCE(rcu_state.gp_flags))) {
1242                 WARN_ONCE(1, "Kicking %s grace-period kthread\n",
1243                           rcu_state.name);
1244                 rcu_ftrace_dump(DUMP_ALL);
1245                 wake_up_process(rcu_state.gp_kthread);
1246                 WRITE_ONCE(rcu_state.jiffies_kick_kthreads, j + HZ);
1247         }
1248 }
1249
1250 static void panic_on_rcu_stall(void)
1251 {
1252         if (sysctl_panic_on_rcu_stall)
1253                 panic("RCU Stall\n");
1254 }
1255
1256 static void print_other_cpu_stall(unsigned long gp_seq)
1257 {
1258         int cpu;
1259         unsigned long flags;
1260         unsigned long gpa;
1261         unsigned long j;
1262         int ndetected = 0;
1263         struct rcu_node *rnp = rcu_get_root();
1264         long totqlen = 0;
1265
1266         /* Kick and suppress, if so configured. */
1267         rcu_stall_kick_kthreads();
1268         if (rcu_cpu_stall_suppress)
1269                 return;
1270
1271         /*
1272          * OK, time to rat on our buddy...
1273          * See Documentation/RCU/stallwarn.txt for info on how to debug
1274          * RCU CPU stall warnings.
1275          */
1276         pr_err("INFO: %s detected stalls on CPUs/tasks:", rcu_state.name);
1277         print_cpu_stall_info_begin();
1278         rcu_for_each_leaf_node(rnp) {
1279                 raw_spin_lock_irqsave_rcu_node(rnp, flags);
1280                 ndetected += rcu_print_task_stall(rnp);
1281                 if (rnp->qsmask != 0) {
1282                         for_each_leaf_node_possible_cpu(rnp, cpu)
1283                                 if (rnp->qsmask & leaf_node_cpu_bit(rnp, cpu)) {
1284                                         print_cpu_stall_info(cpu);
1285                                         ndetected++;
1286                                 }
1287                 }
1288                 raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
1289         }
1290
1291         print_cpu_stall_info_end();
1292         for_each_possible_cpu(cpu)
1293                 totqlen += rcu_get_n_cbs_cpu(cpu);
1294         pr_cont("(detected by %d, t=%ld jiffies, g=%ld, q=%lu)\n",
1295                smp_processor_id(), (long)(jiffies - rcu_state.gp_start),
1296                (long)rcu_seq_current(&rcu_state.gp_seq), totqlen);
1297         if (ndetected) {
1298                 rcu_dump_cpu_stacks();
1299
1300                 /* Complain about tasks blocking the grace period. */
1301                 rcu_print_detail_task_stall();
1302         } else {
1303                 if (rcu_seq_current(&rcu_state.gp_seq) != gp_seq) {
1304                         pr_err("INFO: Stall ended before state dump start\n");
1305                 } else {
1306                         j = jiffies;
1307                         gpa = READ_ONCE(rcu_state.gp_activity);
1308                         pr_err("All QSes seen, last %s kthread activity %ld (%ld-%ld), jiffies_till_next_fqs=%ld, root ->qsmask %#lx\n",
1309                                rcu_state.name, j - gpa, j, gpa,
1310                                READ_ONCE(jiffies_till_next_fqs),
1311                                rcu_get_root()->qsmask);
1312                         /* In this case, the current CPU might be at fault. */
1313                         sched_show_task(current);
1314                 }
1315         }
1316         /* Rewrite if needed in case of slow consoles. */
1317         if (ULONG_CMP_GE(jiffies, READ_ONCE(rcu_state.jiffies_stall)))
1318                 WRITE_ONCE(rcu_state.jiffies_stall,
1319                            jiffies + 3 * rcu_jiffies_till_stall_check() + 3);
1320
1321         rcu_check_gp_kthread_starvation();
1322
1323         panic_on_rcu_stall();
1324
1325         rcu_force_quiescent_state();  /* Kick them all. */
1326 }
1327
1328 static void print_cpu_stall(void)
1329 {
1330         int cpu;
1331         unsigned long flags;
1332         struct rcu_data *rdp = this_cpu_ptr(&rcu_data);
1333         struct rcu_node *rnp = rcu_get_root();
1334         long totqlen = 0;
1335
1336         /* Kick and suppress, if so configured. */
1337         rcu_stall_kick_kthreads();
1338         if (rcu_cpu_stall_suppress)
1339                 return;
1340
1341         /*
1342          * OK, time to rat on ourselves...
1343          * See Documentation/RCU/stallwarn.txt for info on how to debug
1344          * RCU CPU stall warnings.
1345          */
1346         pr_err("INFO: %s self-detected stall on CPU", rcu_state.name);
1347         print_cpu_stall_info_begin();
1348         raw_spin_lock_irqsave_rcu_node(rdp->mynode, flags);
1349         print_cpu_stall_info(smp_processor_id());
1350         raw_spin_unlock_irqrestore_rcu_node(rdp->mynode, flags);
1351         print_cpu_stall_info_end();
1352         for_each_possible_cpu(cpu)
1353                 totqlen += rcu_get_n_cbs_cpu(cpu);
1354         pr_cont(" (t=%lu jiffies g=%ld q=%lu)\n",
1355                 jiffies - rcu_state.gp_start,
1356                 (long)rcu_seq_current(&rcu_state.gp_seq), totqlen);
1357
1358         rcu_check_gp_kthread_starvation();
1359
1360         rcu_dump_cpu_stacks();
1361
1362         raw_spin_lock_irqsave_rcu_node(rnp, flags);
1363         /* Rewrite if needed in case of slow consoles. */
1364         if (ULONG_CMP_GE(jiffies, READ_ONCE(rcu_state.jiffies_stall)))
1365                 WRITE_ONCE(rcu_state.jiffies_stall,
1366                            jiffies + 3 * rcu_jiffies_till_stall_check() + 3);
1367         raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
1368
1369         panic_on_rcu_stall();
1370
1371         /*
1372          * Attempt to revive the RCU machinery by forcing a context switch.
1373          *
1374          * A context switch would normally allow the RCU state machine to make
1375          * progress and it could be we're stuck in kernel space without context
1376          * switches for an entirely unreasonable amount of time.
1377          */
1378         set_tsk_need_resched(current);
1379         set_preempt_need_resched();
1380 }
1381
1382 static void check_cpu_stall(struct rcu_data *rdp)
1383 {
1384         unsigned long gs1;
1385         unsigned long gs2;
1386         unsigned long gps;
1387         unsigned long j;
1388         unsigned long jn;
1389         unsigned long js;
1390         struct rcu_node *rnp;
1391
1392         if ((rcu_cpu_stall_suppress && !rcu_kick_kthreads) ||
1393             !rcu_gp_in_progress())
1394                 return;
1395         rcu_stall_kick_kthreads();
1396         j = jiffies;
1397
1398         /*
1399          * Lots of memory barriers to reject false positives.
1400          *
1401          * The idea is to pick up rcu_state.gp_seq, then
1402          * rcu_state.jiffies_stall, then rcu_state.gp_start, and finally
1403          * another copy of rcu_state.gp_seq.  These values are updated in
1404          * the opposite order with memory barriers (or equivalent) during
1405          * grace-period initialization and cleanup.  Now, a false positive
1406          * can occur if we get an new value of rcu_state.gp_start and a old
1407          * value of rcu_state.jiffies_stall.  But given the memory barriers,
1408          * the only way that this can happen is if one grace period ends
1409          * and another starts between these two fetches.  This is detected
1410          * by comparing the second fetch of rcu_state.gp_seq with the
1411          * previous fetch from rcu_state.gp_seq.
1412          *
1413          * Given this check, comparisons of jiffies, rcu_state.jiffies_stall,
1414          * and rcu_state.gp_start suffice to forestall false positives.
1415          */
1416         gs1 = READ_ONCE(rcu_state.gp_seq);
1417         smp_rmb(); /* Pick up ->gp_seq first... */
1418         js = READ_ONCE(rcu_state.jiffies_stall);
1419         smp_rmb(); /* ...then ->jiffies_stall before the rest... */
1420         gps = READ_ONCE(rcu_state.gp_start);
1421         smp_rmb(); /* ...and finally ->gp_start before ->gp_seq again. */
1422         gs2 = READ_ONCE(rcu_state.gp_seq);
1423         if (gs1 != gs2 ||
1424             ULONG_CMP_LT(j, js) ||
1425             ULONG_CMP_GE(gps, js))
1426                 return; /* No stall or GP completed since entering function. */
1427         rnp = rdp->mynode;
1428         jn = jiffies + 3 * rcu_jiffies_till_stall_check() + 3;
1429         if (rcu_gp_in_progress() &&
1430             (READ_ONCE(rnp->qsmask) & rdp->grpmask) &&
1431             cmpxchg(&rcu_state.jiffies_stall, js, jn) == js) {
1432
1433                 /* We haven't checked in, so go dump stack. */
1434                 print_cpu_stall();
1435
1436         } else if (rcu_gp_in_progress() &&
1437                    ULONG_CMP_GE(j, js + RCU_STALL_RAT_DELAY) &&
1438                    cmpxchg(&rcu_state.jiffies_stall, js, jn) == js) {
1439
1440                 /* They had a few time units to dump stack, so complain. */
1441                 print_other_cpu_stall(gs2);
1442         }
1443 }
1444
1445 /**
1446  * rcu_cpu_stall_reset - prevent further stall warnings in current grace period
1447  *
1448  * Set the stall-warning timeout way off into the future, thus preventing
1449  * any RCU CPU stall-warning messages from appearing in the current set of
1450  * RCU grace periods.
1451  *
1452  * The caller must disable hard irqs.
1453  */
1454 void rcu_cpu_stall_reset(void)
1455 {
1456         WRITE_ONCE(rcu_state.jiffies_stall, jiffies + ULONG_MAX / 2);
1457 }
1458
1459 /* Trace-event wrapper function for trace_rcu_future_grace_period.  */
1460 static void trace_rcu_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
1461                               unsigned long gp_seq_req, const char *s)
1462 {
1463         trace_rcu_future_grace_period(rcu_state.name, rnp->gp_seq, gp_seq_req,
1464                                       rnp->level, rnp->grplo, rnp->grphi, s);
1465 }
1466
1467 /*
1468  * rcu_start_this_gp - Request the start of a particular grace period
1469  * @rnp_start: The leaf node of the CPU from which to start.
1470  * @rdp: The rcu_data corresponding to the CPU from which to start.
1471  * @gp_seq_req: The gp_seq of the grace period to start.
1472  *
1473  * Start the specified grace period, as needed to handle newly arrived
1474  * callbacks.  The required future grace periods are recorded in each
1475  * rcu_node structure's ->gp_seq_needed field.  Returns true if there
1476  * is reason to awaken the grace-period kthread.
1477  *
1478  * The caller must hold the specified rcu_node structure's ->lock, which
1479  * is why the caller is responsible for waking the grace-period kthread.
1480  *
1481  * Returns true if the GP thread needs to be awakened else false.
1482  */
1483 static bool rcu_start_this_gp(struct rcu_node *rnp_start, struct rcu_data *rdp,
1484                               unsigned long gp_seq_req)
1485 {
1486         bool ret = false;
1487         struct rcu_node *rnp;
1488
1489         /*
1490          * Use funnel locking to either acquire the root rcu_node
1491          * structure's lock or bail out if the need for this grace period
1492          * has already been recorded -- or if that grace period has in
1493          * fact already started.  If there is already a grace period in
1494          * progress in a non-leaf node, no recording is needed because the
1495          * end of the grace period will scan the leaf rcu_node structures.
1496          * Note that rnp_start->lock must not be released.
1497          */
1498         raw_lockdep_assert_held_rcu_node(rnp_start);
1499         trace_rcu_this_gp(rnp_start, rdp, gp_seq_req, TPS("Startleaf"));
1500         for (rnp = rnp_start; 1; rnp = rnp->parent) {
1501                 if (rnp != rnp_start)
1502                         raw_spin_lock_rcu_node(rnp);
1503                 if (ULONG_CMP_GE(rnp->gp_seq_needed, gp_seq_req) ||
1504                     rcu_seq_started(&rnp->gp_seq, gp_seq_req) ||
1505                     (rnp != rnp_start &&
1506                      rcu_seq_state(rcu_seq_current(&rnp->gp_seq)))) {
1507                         trace_rcu_this_gp(rnp, rdp, gp_seq_req,
1508                                           TPS("Prestarted"));
1509                         goto unlock_out;
1510                 }
1511                 rnp->gp_seq_needed = gp_seq_req;
1512                 if (rcu_seq_state(rcu_seq_current(&rnp->gp_seq))) {
1513                         /*
1514                          * We just marked the leaf or internal node, and a
1515                          * grace period is in progress, which means that
1516                          * rcu_gp_cleanup() will see the marking.  Bail to
1517                          * reduce contention.
1518                          */
1519                         trace_rcu_this_gp(rnp_start, rdp, gp_seq_req,
1520                                           TPS("Startedleaf"));
1521                         goto unlock_out;
1522                 }
1523                 if (rnp != rnp_start && rnp->parent != NULL)
1524                         raw_spin_unlock_rcu_node(rnp);
1525                 if (!rnp->parent)
1526                         break;  /* At root, and perhaps also leaf. */
1527         }
1528
1529         /* If GP already in progress, just leave, otherwise start one. */
1530         if (rcu_gp_in_progress()) {
1531                 trace_rcu_this_gp(rnp, rdp, gp_seq_req, TPS("Startedleafroot"));
1532                 goto unlock_out;
1533         }
1534         trace_rcu_this_gp(rnp, rdp, gp_seq_req, TPS("Startedroot"));
1535         WRITE_ONCE(rcu_state.gp_flags, rcu_state.gp_flags | RCU_GP_FLAG_INIT);
1536         rcu_state.gp_req_activity = jiffies;
1537         if (!rcu_state.gp_kthread) {
1538                 trace_rcu_this_gp(rnp, rdp, gp_seq_req, TPS("NoGPkthread"));
1539                 goto unlock_out;
1540         }
1541         trace_rcu_grace_period(rcu_state.name, READ_ONCE(rcu_state.gp_seq), TPS("newreq"));
1542         ret = true;  /* Caller must wake GP kthread. */
1543 unlock_out:
1544         /* Push furthest requested GP to leaf node and rcu_data structure. */
1545         if (ULONG_CMP_LT(gp_seq_req, rnp->gp_seq_needed)) {
1546                 rnp_start->gp_seq_needed = rnp->gp_seq_needed;
1547                 rdp->gp_seq_needed = rnp->gp_seq_needed;
1548         }
1549         if (rnp != rnp_start)
1550                 raw_spin_unlock_rcu_node(rnp);
1551         return ret;
1552 }
1553
1554 /*
1555  * Clean up any old requests for the just-ended grace period.  Also return
1556  * whether any additional grace periods have been requested.
1557  */
1558 static bool rcu_future_gp_cleanup(struct rcu_node *rnp)
1559 {
1560         bool needmore;
1561         struct rcu_data *rdp = this_cpu_ptr(&rcu_data);
1562
1563         needmore = ULONG_CMP_LT(rnp->gp_seq, rnp->gp_seq_needed);
1564         if (!needmore)
1565                 rnp->gp_seq_needed = rnp->gp_seq; /* Avoid counter wrap. */
1566         trace_rcu_this_gp(rnp, rdp, rnp->gp_seq,
1567                           needmore ? TPS("CleanupMore") : TPS("Cleanup"));
1568         return needmore;
1569 }
1570
1571 /*
1572  * Awaken the grace-period kthread.  Don't do a self-awaken (unless in
1573  * an interrupt or softirq handler), and don't bother awakening when there
1574  * is nothing for the grace-period kthread to do (as in several CPUs raced
1575  * to awaken, and we lost), and finally don't try to awaken a kthread that
1576  * has not yet been created.  If all those checks are passed, track some
1577  * debug information and awaken.
1578  *
1579  * So why do the self-wakeup when in an interrupt or softirq handler
1580  * in the grace-period kthread's context?  Because the kthread might have
1581  * been interrupted just as it was going to sleep, and just after the final
1582  * pre-sleep check of the awaken condition.  In this case, a wakeup really
1583  * is required, and is therefore supplied.
1584  */
1585 static void rcu_gp_kthread_wake(void)
1586 {
1587         if ((current == rcu_state.gp_kthread &&
1588              !in_interrupt() && !in_serving_softirq()) ||
1589             !READ_ONCE(rcu_state.gp_flags) ||
1590             !rcu_state.gp_kthread)
1591                 return;
1592         WRITE_ONCE(rcu_state.gp_wake_time, jiffies);
1593         WRITE_ONCE(rcu_state.gp_wake_seq, READ_ONCE(rcu_state.gp_seq));
1594         swake_up_one(&rcu_state.gp_wq);
1595 }
1596
1597 /*
1598  * If there is room, assign a ->gp_seq number to any callbacks on this
1599  * CPU that have not already been assigned.  Also accelerate any callbacks
1600  * that were previously assigned a ->gp_seq number that has since proven
1601  * to be too conservative, which can happen if callbacks get assigned a
1602  * ->gp_seq number while RCU is idle, but with reference to a non-root
1603  * rcu_node structure.  This function is idempotent, so it does not hurt
1604  * to call it repeatedly.  Returns an flag saying that we should awaken
1605  * the RCU grace-period kthread.
1606  *
1607  * The caller must hold rnp->lock with interrupts disabled.
1608  */
1609 static bool rcu_accelerate_cbs(struct rcu_node *rnp, struct rcu_data *rdp)
1610 {
1611         unsigned long gp_seq_req;
1612         bool ret = false;
1613
1614         raw_lockdep_assert_held_rcu_node(rnp);
1615
1616         /* If no pending (not yet ready to invoke) callbacks, nothing to do. */
1617         if (!rcu_segcblist_pend_cbs(&rdp->cblist))
1618                 return false;
1619
1620         /*
1621          * Callbacks are often registered with incomplete grace-period
1622          * information.  Something about the fact that getting exact
1623          * information requires acquiring a global lock...  RCU therefore
1624          * makes a conservative estimate of the grace period number at which
1625          * a given callback will become ready to invoke.        The following
1626          * code checks this estimate and improves it when possible, thus
1627          * accelerating callback invocation to an earlier grace-period
1628          * number.
1629          */
1630         gp_seq_req = rcu_seq_snap(&rcu_state.gp_seq);
1631         if (rcu_segcblist_accelerate(&rdp->cblist, gp_seq_req))
1632                 ret = rcu_start_this_gp(rnp, rdp, gp_seq_req);
1633
1634         /* Trace depending on how much we were able to accelerate. */
1635         if (rcu_segcblist_restempty(&rdp->cblist, RCU_WAIT_TAIL))
1636                 trace_rcu_grace_period(rcu_state.name, rdp->gp_seq, TPS("AccWaitCB"));
1637         else
1638                 trace_rcu_grace_period(rcu_state.name, rdp->gp_seq, TPS("AccReadyCB"));
1639         return ret;
1640 }
1641
1642 /*
1643  * Similar to rcu_accelerate_cbs(), but does not require that the leaf
1644  * rcu_node structure's ->lock be held.  It consults the cached value
1645  * of ->gp_seq_needed in the rcu_data structure, and if that indicates
1646  * that a new grace-period request be made, invokes rcu_accelerate_cbs()
1647  * while holding the leaf rcu_node structure's ->lock.
1648  */
1649 static void rcu_accelerate_cbs_unlocked(struct rcu_node *rnp,
1650                                         struct rcu_data *rdp)
1651 {
1652         unsigned long c;
1653         bool needwake;
1654
1655         lockdep_assert_irqs_disabled();
1656         c = rcu_seq_snap(&rcu_state.gp_seq);
1657         if (!rdp->gpwrap && ULONG_CMP_GE(rdp->gp_seq_needed, c)) {
1658                 /* Old request still live, so mark recent callbacks. */
1659                 (void)rcu_segcblist_accelerate(&rdp->cblist, c);
1660                 return;
1661         }
1662         raw_spin_lock_rcu_node(rnp); /* irqs already disabled. */
1663         needwake = rcu_accelerate_cbs(rnp, rdp);
1664         raw_spin_unlock_rcu_node(rnp); /* irqs remain disabled. */
1665         if (needwake)
1666                 rcu_gp_kthread_wake();
1667 }
1668
1669 /*
1670  * Move any callbacks whose grace period has completed to the
1671  * RCU_DONE_TAIL sublist, then compact the remaining sublists and
1672  * assign ->gp_seq numbers to any callbacks in the RCU_NEXT_TAIL
1673  * sublist.  This function is idempotent, so it does not hurt to
1674  * invoke it repeatedly.  As long as it is not invoked -too- often...
1675  * Returns true if the RCU grace-period kthread needs to be awakened.
1676  *
1677  * The caller must hold rnp->lock with interrupts disabled.
1678  */
1679 static bool rcu_advance_cbs(struct rcu_node *rnp, struct rcu_data *rdp)
1680 {
1681         raw_lockdep_assert_held_rcu_node(rnp);
1682
1683         /* If no pending (not yet ready to invoke) callbacks, nothing to do. */
1684         if (!rcu_segcblist_pend_cbs(&rdp->cblist))
1685                 return false;
1686
1687         /*
1688          * Find all callbacks whose ->gp_seq numbers indicate that they
1689          * are ready to invoke, and put them into the RCU_DONE_TAIL sublist.
1690          */
1691         rcu_segcblist_advance(&rdp->cblist, rnp->gp_seq);
1692
1693         /* Classify any remaining callbacks. */
1694         return rcu_accelerate_cbs(rnp, rdp);
1695 }
1696
1697 /*
1698  * Update CPU-local rcu_data state to record the beginnings and ends of
1699  * grace periods.  The caller must hold the ->lock of the leaf rcu_node
1700  * structure corresponding to the current CPU, and must have irqs disabled.
1701  * Returns true if the grace-period kthread needs to be awakened.
1702  */
1703 static bool __note_gp_changes(struct rcu_node *rnp, struct rcu_data *rdp)
1704 {
1705         bool ret;
1706         bool need_gp;
1707
1708         raw_lockdep_assert_held_rcu_node(rnp);
1709
1710         if (rdp->gp_seq == rnp->gp_seq)
1711                 return false; /* Nothing to do. */
1712
1713         /* Handle the ends of any preceding grace periods first. */
1714         if (rcu_seq_completed_gp(rdp->gp_seq, rnp->gp_seq) ||
1715             unlikely(READ_ONCE(rdp->gpwrap))) {
1716                 ret = rcu_advance_cbs(rnp, rdp); /* Advance callbacks. */
1717                 trace_rcu_grace_period(rcu_state.name, rdp->gp_seq, TPS("cpuend"));
1718         } else {
1719                 ret = rcu_accelerate_cbs(rnp, rdp); /* Recent callbacks. */
1720         }
1721
1722         /* Now handle the beginnings of any new-to-this-CPU grace periods. */
1723         if (rcu_seq_new_gp(rdp->gp_seq, rnp->gp_seq) ||
1724             unlikely(READ_ONCE(rdp->gpwrap))) {
1725                 /*
1726                  * If the current grace period is waiting for this CPU,
1727                  * set up to detect a quiescent state, otherwise don't
1728                  * go looking for one.
1729                  */
1730                 trace_rcu_grace_period(rcu_state.name, rnp->gp_seq, TPS("cpustart"));
1731                 need_gp = !!(rnp->qsmask & rdp->grpmask);
1732                 rdp->cpu_no_qs.b.norm = need_gp;
1733                 rdp->core_needs_qs = need_gp;
1734                 zero_cpu_stall_ticks(rdp);
1735         }
1736         rdp->gp_seq = rnp->gp_seq;  /* Remember new grace-period state. */
1737         if (ULONG_CMP_LT(rdp->gp_seq_needed, rnp->gp_seq_needed) || rdp->gpwrap)
1738                 rdp->gp_seq_needed = rnp->gp_seq_needed;
1739         WRITE_ONCE(rdp->gpwrap, false);
1740         rcu_gpnum_ovf(rnp, rdp);
1741         return ret;
1742 }
1743
1744 static void note_gp_changes(struct rcu_data *rdp)
1745 {
1746         unsigned long flags;
1747         bool needwake;
1748         struct rcu_node *rnp;
1749
1750         local_irq_save(flags);
1751         rnp = rdp->mynode;
1752         if ((rdp->gp_seq == rcu_seq_current(&rnp->gp_seq) &&
1753              !unlikely(READ_ONCE(rdp->gpwrap))) || /* w/out lock. */
1754             !raw_spin_trylock_rcu_node(rnp)) { /* irqs already off, so later. */
1755                 local_irq_restore(flags);
1756                 return;
1757         }
1758         needwake = __note_gp_changes(rnp, rdp);
1759         raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
1760         if (needwake)
1761                 rcu_gp_kthread_wake();
1762 }
1763
1764 static void rcu_gp_slow(int delay)
1765 {
1766         if (delay > 0 &&
1767             !(rcu_seq_ctr(rcu_state.gp_seq) %
1768               (rcu_num_nodes * PER_RCU_NODE_PERIOD * delay)))
1769                 schedule_timeout_uninterruptible(delay);
1770 }
1771
1772 /*
1773  * Initialize a new grace period.  Return false if no grace period required.
1774  */
1775 static bool rcu_gp_init(void)
1776 {
1777         unsigned long flags;
1778         unsigned long oldmask;
1779         unsigned long mask;
1780         struct rcu_data *rdp;
1781         struct rcu_node *rnp = rcu_get_root();
1782
1783         WRITE_ONCE(rcu_state.gp_activity, jiffies);
1784         raw_spin_lock_irq_rcu_node(rnp);
1785         if (!READ_ONCE(rcu_state.gp_flags)) {
1786                 /* Spurious wakeup, tell caller to go back to sleep.  */
1787                 raw_spin_unlock_irq_rcu_node(rnp);
1788                 return false;
1789         }
1790         WRITE_ONCE(rcu_state.gp_flags, 0); /* Clear all flags: New GP. */
1791
1792         if (WARN_ON_ONCE(rcu_gp_in_progress())) {
1793                 /*
1794                  * Grace period already in progress, don't start another.
1795                  * Not supposed to be able to happen.
1796                  */
1797                 raw_spin_unlock_irq_rcu_node(rnp);
1798                 return false;
1799         }
1800
1801         /* Advance to a new grace period and initialize state. */
1802         record_gp_stall_check_time();
1803         /* Record GP times before starting GP, hence rcu_seq_start(). */
1804         rcu_seq_start(&rcu_state.gp_seq);
1805         trace_rcu_grace_period(rcu_state.name, rcu_state.gp_seq, TPS("start"));
1806         raw_spin_unlock_irq_rcu_node(rnp);
1807
1808         /*
1809          * Apply per-leaf buffered online and offline operations to the
1810          * rcu_node tree.  Note that this new grace period need not wait
1811          * for subsequent online CPUs, and that quiescent-state forcing
1812          * will handle subsequent offline CPUs.
1813          */
1814         rcu_state.gp_state = RCU_GP_ONOFF;
1815         rcu_for_each_leaf_node(rnp) {
1816                 raw_spin_lock(&rcu_state.ofl_lock);
1817                 raw_spin_lock_irq_rcu_node(rnp);
1818                 if (rnp->qsmaskinit == rnp->qsmaskinitnext &&
1819                     !rnp->wait_blkd_tasks) {
1820                         /* Nothing to do on this leaf rcu_node structure. */
1821                         raw_spin_unlock_irq_rcu_node(rnp);
1822                         raw_spin_unlock(&rcu_state.ofl_lock);
1823                         continue;
1824                 }
1825
1826                 /* Record old state, apply changes to ->qsmaskinit field. */
1827                 oldmask = rnp->qsmaskinit;
1828                 rnp->qsmaskinit = rnp->qsmaskinitnext;
1829
1830                 /* If zero-ness of ->qsmaskinit changed, propagate up tree. */
1831                 if (!oldmask != !rnp->qsmaskinit) {
1832                         if (!oldmask) { /* First online CPU for rcu_node. */
1833                                 if (!rnp->wait_blkd_tasks) /* Ever offline? */
1834                                         rcu_init_new_rnp(rnp);
1835                         } else if (rcu_preempt_has_tasks(rnp)) {
1836                                 rnp->wait_blkd_tasks = true; /* blocked tasks */
1837                         } else { /* Last offline CPU and can propagate. */
1838                                 rcu_cleanup_dead_rnp(rnp);
1839                         }
1840                 }
1841
1842                 /*
1843                  * If all waited-on tasks from prior grace period are
1844                  * done, and if all this rcu_node structure's CPUs are
1845                  * still offline, propagate up the rcu_node tree and
1846                  * clear ->wait_blkd_tasks.  Otherwise, if one of this
1847                  * rcu_node structure's CPUs has since come back online,
1848                  * simply clear ->wait_blkd_tasks.
1849                  */
1850                 if (rnp->wait_blkd_tasks &&
1851                     (!rcu_preempt_has_tasks(rnp) || rnp->qsmaskinit)) {
1852                         rnp->wait_blkd_tasks = false;
1853                         if (!rnp->qsmaskinit)
1854                                 rcu_cleanup_dead_rnp(rnp);
1855                 }
1856
1857                 raw_spin_unlock_irq_rcu_node(rnp);
1858                 raw_spin_unlock(&rcu_state.ofl_lock);
1859         }
1860         rcu_gp_slow(gp_preinit_delay); /* Races with CPU hotplug. */
1861
1862         /*
1863          * Set the quiescent-state-needed bits in all the rcu_node
1864          * structures for all currently online CPUs in breadth-first
1865          * order, starting from the root rcu_node structure, relying on the
1866          * layout of the tree within the rcu_state.node[] array.  Note that
1867          * other CPUs will access only the leaves of the hierarchy, thus
1868          * seeing that no grace period is in progress, at least until the
1869          * corresponding leaf node has been initialized.
1870          *
1871          * The grace period cannot complete until the initialization
1872          * process finishes, because this kthread handles both.
1873          */
1874         rcu_state.gp_state = RCU_GP_INIT;
1875         rcu_for_each_node_breadth_first(rnp) {
1876                 rcu_gp_slow(gp_init_delay);
1877                 raw_spin_lock_irqsave_rcu_node(rnp, flags);
1878                 rdp = this_cpu_ptr(&rcu_data);
1879                 rcu_preempt_check_blocked_tasks(rnp);
1880                 rnp->qsmask = rnp->qsmaskinit;
1881                 WRITE_ONCE(rnp->gp_seq, rcu_state.gp_seq);
1882                 if (rnp == rdp->mynode)
1883                         (void)__note_gp_changes(rnp, rdp);
1884                 rcu_preempt_boost_start_gp(rnp);
1885                 trace_rcu_grace_period_init(rcu_state.name, rnp->gp_seq,
1886                                             rnp->level, rnp->grplo,
1887                                             rnp->grphi, rnp->qsmask);
1888                 /* Quiescent states for tasks on any now-offline CPUs. */
1889                 mask = rnp->qsmask & ~rnp->qsmaskinitnext;
1890                 rnp->rcu_gp_init_mask = mask;
1891                 if ((mask || rnp->wait_blkd_tasks) && rcu_is_leaf_node(rnp))
1892                         rcu_report_qs_rnp(mask, rnp, rnp->gp_seq, flags);
1893                 else
1894                         raw_spin_unlock_irq_rcu_node(rnp);
1895                 cond_resched_tasks_rcu_qs();
1896                 WRITE_ONCE(rcu_state.gp_activity, jiffies);
1897         }
1898
1899         return true;
1900 }
1901
1902 /*
1903  * Helper function for swait_event_idle_exclusive() wakeup at force-quiescent-state
1904  * time.
1905  */
1906 static bool rcu_gp_fqs_check_wake(int *gfp)
1907 {
1908         struct rcu_node *rnp = rcu_get_root();
1909
1910         /* Someone like call_rcu() requested a force-quiescent-state scan. */
1911         *gfp = READ_ONCE(rcu_state.gp_flags);
1912         if (*gfp & RCU_GP_FLAG_FQS)
1913                 return true;
1914
1915         /* The current grace period has completed. */
1916         if (!READ_ONCE(rnp->qsmask) && !rcu_preempt_blocked_readers_cgp(rnp))
1917                 return true;
1918
1919         return false;
1920 }
1921
1922 /*
1923  * Do one round of quiescent-state forcing.
1924  */
1925 static void rcu_gp_fqs(bool first_time)
1926 {
1927         struct rcu_node *rnp = rcu_get_root();
1928
1929         WRITE_ONCE(rcu_state.gp_activity, jiffies);
1930         rcu_state.n_force_qs++;
1931         if (first_time) {
1932                 /* Collect dyntick-idle snapshots. */
1933                 force_qs_rnp(dyntick_save_progress_counter);
1934         } else {
1935                 /* Handle dyntick-idle and offline CPUs. */
1936                 force_qs_rnp(rcu_implicit_dynticks_qs);
1937         }
1938         /* Clear flag to prevent immediate re-entry. */
1939         if (READ_ONCE(rcu_state.gp_flags) & RCU_GP_FLAG_FQS) {
1940                 raw_spin_lock_irq_rcu_node(rnp);
1941                 WRITE_ONCE(rcu_state.gp_flags,
1942                            READ_ONCE(rcu_state.gp_flags) & ~RCU_GP_FLAG_FQS);
1943                 raw_spin_unlock_irq_rcu_node(rnp);
1944         }
1945 }
1946
1947 /*
1948  * Loop doing repeated quiescent-state forcing until the grace period ends.
1949  */
1950 static void rcu_gp_fqs_loop(void)
1951 {
1952         bool first_gp_fqs;
1953         int gf;
1954         unsigned long j;
1955         int ret;
1956         struct rcu_node *rnp = rcu_get_root();
1957
1958         first_gp_fqs = true;
1959         j = READ_ONCE(jiffies_till_first_fqs);
1960         ret = 0;
1961         for (;;) {
1962                 if (!ret) {
1963                         rcu_state.jiffies_force_qs = jiffies + j;
1964                         WRITE_ONCE(rcu_state.jiffies_kick_kthreads,
1965                                    jiffies + (j ? 3 * j : 2));
1966                 }
1967                 trace_rcu_grace_period(rcu_state.name,
1968                                        READ_ONCE(rcu_state.gp_seq),
1969                                        TPS("fqswait"));
1970                 rcu_state.gp_state = RCU_GP_WAIT_FQS;
1971                 ret = swait_event_idle_timeout_exclusive(
1972                                 rcu_state.gp_wq, rcu_gp_fqs_check_wake(&gf), j);
1973                 rcu_state.gp_state = RCU_GP_DOING_FQS;
1974                 /* Locking provides needed memory barriers. */
1975                 /* If grace period done, leave loop. */
1976                 if (!READ_ONCE(rnp->qsmask) &&
1977                     !rcu_preempt_blocked_readers_cgp(rnp))
1978                         break;
1979                 /* If time for quiescent-state forcing, do it. */
1980                 if (ULONG_CMP_GE(jiffies, rcu_state.jiffies_force_qs) ||
1981                     (gf & RCU_GP_FLAG_FQS)) {
1982                         trace_rcu_grace_period(rcu_state.name,
1983                                                READ_ONCE(rcu_state.gp_seq),
1984                                                TPS("fqsstart"));
1985                         rcu_gp_fqs(first_gp_fqs);
1986                         first_gp_fqs = false;
1987                         trace_rcu_grace_period(rcu_state.name,
1988                                                READ_ONCE(rcu_state.gp_seq),
1989                                                TPS("fqsend"));
1990                         cond_resched_tasks_rcu_qs();
1991                         WRITE_ONCE(rcu_state.gp_activity, jiffies);
1992                         ret = 0; /* Force full wait till next FQS. */
1993                         j = READ_ONCE(jiffies_till_next_fqs);
1994                 } else {
1995                         /* Deal with stray signal. */
1996                         cond_resched_tasks_rcu_qs();
1997                         WRITE_ONCE(rcu_state.gp_activity, jiffies);
1998                         WARN_ON(signal_pending(current));
1999                         trace_rcu_grace_period(rcu_state.name,
2000                                                READ_ONCE(rcu_state.gp_seq),
2001                                                TPS("fqswaitsig"));
2002                         ret = 1; /* Keep old FQS timing. */
2003                         j = jiffies;
2004                         if (time_after(jiffies, rcu_state.jiffies_force_qs))
2005                                 j = 1;
2006                         else
2007                                 j = rcu_state.jiffies_force_qs - j;
2008                 }
2009         }
2010 }
2011
2012 /*
2013  * Clean up after the old grace period.
2014  */
2015 static void rcu_gp_cleanup(void)
2016 {
2017         unsigned long gp_duration;
2018         bool needgp = false;
2019         unsigned long new_gp_seq;
2020         struct rcu_data *rdp;
2021         struct rcu_node *rnp = rcu_get_root();
2022         struct swait_queue_head *sq;
2023
2024         WRITE_ONCE(rcu_state.gp_activity, jiffies);
2025         raw_spin_lock_irq_rcu_node(rnp);
2026         rcu_state.gp_end = jiffies;
2027         gp_duration = rcu_state.gp_end - rcu_state.gp_start;
2028         if (gp_duration > rcu_state.gp_max)
2029                 rcu_state.gp_max = gp_duration;
2030
2031         /*
2032          * We know the grace period is complete, but to everyone else
2033          * it appears to still be ongoing.  But it is also the case
2034          * that to everyone else it looks like there is nothing that
2035          * they can do to advance the grace period.  It is therefore
2036          * safe for us to drop the lock in order to mark the grace
2037          * period as completed in all of the rcu_node structures.
2038          */
2039         raw_spin_unlock_irq_rcu_node(rnp);
2040
2041         /*
2042          * Propagate new ->gp_seq value to rcu_node structures so that
2043          * other CPUs don't have to wait until the start of the next grace
2044          * period to process their callbacks.  This also avoids some nasty
2045          * RCU grace-period initialization races by forcing the end of
2046          * the current grace period to be completely recorded in all of
2047          * the rcu_node structures before the beginning of the next grace
2048          * period is recorded in any of the rcu_node structures.
2049          */
2050         new_gp_seq = rcu_state.gp_seq;
2051         rcu_seq_end(&new_gp_seq);
2052         rcu_for_each_node_breadth_first(rnp) {
2053                 raw_spin_lock_irq_rcu_node(rnp);
2054                 if (WARN_ON_ONCE(rcu_preempt_blocked_readers_cgp(rnp)))
2055                         dump_blkd_tasks(rnp, 10);
2056                 WARN_ON_ONCE(rnp->qsmask);
2057                 WRITE_ONCE(rnp->gp_seq, new_gp_seq);
2058                 rdp = this_cpu_ptr(&rcu_data);
2059                 if (rnp == rdp->mynode)
2060                         needgp = __note_gp_changes(rnp, rdp) || needgp;
2061                 /* smp_mb() provided by prior unlock-lock pair. */
2062                 needgp = rcu_future_gp_cleanup(rnp) || needgp;
2063                 sq = rcu_nocb_gp_get(rnp);
2064                 raw_spin_unlock_irq_rcu_node(rnp);
2065                 rcu_nocb_gp_cleanup(sq);
2066                 cond_resched_tasks_rcu_qs();
2067                 WRITE_ONCE(rcu_state.gp_activity, jiffies);
2068                 rcu_gp_slow(gp_cleanup_delay);
2069         }
2070         rnp = rcu_get_root();
2071         raw_spin_lock_irq_rcu_node(rnp); /* GP before ->gp_seq update. */
2072
2073         /* Declare grace period done, trace first to use old GP number. */
2074         trace_rcu_grace_period(rcu_state.name, rcu_state.gp_seq, TPS("end"));
2075         rcu_seq_end(&rcu_state.gp_seq);
2076         rcu_state.gp_state = RCU_GP_IDLE;
2077         /* Check for GP requests since above loop. */
2078         rdp = this_cpu_ptr(&rcu_data);
2079         if (!needgp && ULONG_CMP_LT(rnp->gp_seq, rnp->gp_seq_needed)) {
2080                 trace_rcu_this_gp(rnp, rdp, rnp->gp_seq_needed,
2081                                   TPS("CleanupMore"));
2082                 needgp = true;
2083         }
2084         /* Advance CBs to reduce false positives below. */
2085         if (!rcu_accelerate_cbs(rnp, rdp) && needgp) {
2086                 WRITE_ONCE(rcu_state.gp_flags, RCU_GP_FLAG_INIT);
2087                 rcu_state.gp_req_activity = jiffies;
2088                 trace_rcu_grace_period(rcu_state.name,
2089                                        READ_ONCE(rcu_state.gp_seq),
2090                                        TPS("newreq"));
2091         } else {
2092                 WRITE_ONCE(rcu_state.gp_flags,
2093                            rcu_state.gp_flags & RCU_GP_FLAG_INIT);
2094         }
2095         raw_spin_unlock_irq_rcu_node(rnp);
2096 }
2097
2098 /*
2099  * Body of kthread that handles grace periods.
2100  */
2101 static int __noreturn rcu_gp_kthread(void *unused)
2102 {
2103         rcu_bind_gp_kthread();
2104         for (;;) {
2105
2106                 /* Handle grace-period start. */
2107                 for (;;) {
2108                         trace_rcu_grace_period(rcu_state.name,
2109                                                READ_ONCE(rcu_state.gp_seq),
2110                                                TPS("reqwait"));
2111                         rcu_state.gp_state = RCU_GP_WAIT_GPS;
2112                         swait_event_idle_exclusive(rcu_state.gp_wq,
2113                                          READ_ONCE(rcu_state.gp_flags) &
2114                                          RCU_GP_FLAG_INIT);
2115                         rcu_state.gp_state = RCU_GP_DONE_GPS;
2116                         /* Locking provides needed memory barrier. */
2117                         if (rcu_gp_init())
2118                                 break;
2119                         cond_resched_tasks_rcu_qs();
2120                         WRITE_ONCE(rcu_state.gp_activity, jiffies);
2121                         WARN_ON(signal_pending(current));
2122                         trace_rcu_grace_period(rcu_state.name,
2123                                                READ_ONCE(rcu_state.gp_seq),
2124                                                TPS("reqwaitsig"));
2125                 }
2126
2127                 /* Handle quiescent-state forcing. */
2128                 rcu_gp_fqs_loop();
2129
2130                 /* Handle grace-period end. */
2131                 rcu_state.gp_state = RCU_GP_CLEANUP;
2132                 rcu_gp_cleanup();
2133                 rcu_state.gp_state = RCU_GP_CLEANED;
2134         }
2135 }
2136
2137 /*
2138  * Report a full set of quiescent states to the rcu_state data structure.
2139  * Invoke rcu_gp_kthread_wake() to awaken the grace-period kthread if
2140  * another grace period is required.  Whether we wake the grace-period
2141  * kthread or it awakens itself for the next round of quiescent-state
2142  * forcing, that kthread will clean up after the just-completed grace
2143  * period.  Note that the caller must hold rnp->lock, which is released
2144  * before return.
2145  */
2146 static void rcu_report_qs_rsp(unsigned long flags)
2147         __releases(rcu_get_root()->lock)
2148 {
2149         raw_lockdep_assert_held_rcu_node(rcu_get_root());
2150         WARN_ON_ONCE(!rcu_gp_in_progress());
2151         WRITE_ONCE(rcu_state.gp_flags,
2152                    READ_ONCE(rcu_state.gp_flags) | RCU_GP_FLAG_FQS);
2153         raw_spin_unlock_irqrestore_rcu_node(rcu_get_root(), flags);
2154         rcu_gp_kthread_wake();
2155 }
2156
2157 /*
2158  * Similar to rcu_report_qs_rdp(), for which it is a helper function.
2159  * Allows quiescent states for a group of CPUs to be reported at one go
2160  * to the specified rcu_node structure, though all the CPUs in the group
2161  * must be represented by the same rcu_node structure (which need not be a
2162  * leaf rcu_node structure, though it often will be).  The gps parameter
2163  * is the grace-period snapshot, which means that the quiescent states
2164  * are valid only if rnp->gp_seq is equal to gps.  That structure's lock
2165  * must be held upon entry, and it is released before return.
2166  *
2167  * As a special case, if mask is zero, the bit-already-cleared check is
2168  * disabled.  This allows propagating quiescent state due to resumed tasks
2169  * during grace-period initialization.
2170  */
2171 static void rcu_report_qs_rnp(unsigned long mask, struct rcu_node *rnp,
2172                               unsigned long gps, unsigned long flags)
2173         __releases(rnp->lock)
2174 {
2175         unsigned long oldmask = 0;
2176         struct rcu_node *rnp_c;
2177
2178         raw_lockdep_assert_held_rcu_node(rnp);
2179
2180         /* Walk up the rcu_node hierarchy. */
2181         for (;;) {
2182                 if ((!(rnp->qsmask & mask) && mask) || rnp->gp_seq != gps) {
2183
2184                         /*
2185                          * Our bit has already been cleared, or the
2186                          * relevant grace period is already over, so done.
2187                          */
2188                         raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
2189                         return;
2190                 }
2191                 WARN_ON_ONCE(oldmask); /* Any child must be all zeroed! */
2192                 WARN_ON_ONCE(!rcu_is_leaf_node(rnp) &&
2193                              rcu_preempt_blocked_readers_cgp(rnp));
2194                 rnp->qsmask &= ~mask;
2195                 trace_rcu_quiescent_state_report(rcu_state.name, rnp->gp_seq,
2196                                                  mask, rnp->qsmask, rnp->level,
2197                                                  rnp->grplo, rnp->grphi,
2198                                                  !!rnp->gp_tasks);
2199                 if (rnp->qsmask != 0 || rcu_preempt_blocked_readers_cgp(rnp)) {
2200
2201                         /* Other bits still set at this level, so done. */
2202                         raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
2203                         return;
2204                 }
2205                 rnp->completedqs = rnp->gp_seq;
2206                 mask = rnp->grpmask;
2207                 if (rnp->parent == NULL) {
2208
2209                         /* No more levels.  Exit loop holding root lock. */
2210
2211                         break;
2212                 }
2213                 raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
2214                 rnp_c = rnp;
2215                 rnp = rnp->parent;
2216                 raw_spin_lock_irqsave_rcu_node(rnp, flags);
2217                 oldmask = rnp_c->qsmask;
2218         }
2219
2220         /*
2221          * Get here if we are the last CPU to pass through a quiescent
2222          * state for this grace period.  Invoke rcu_report_qs_rsp()
2223          * to clean up and start the next grace period if one is needed.
2224          */
2225         rcu_report_qs_rsp(flags); /* releases rnp->lock. */
2226 }
2227
2228 /*
2229  * Record a quiescent state for all tasks that were previously queued
2230  * on the specified rcu_node structure and that were blocking the current
2231  * RCU grace period.  The caller must hold the corresponding rnp->lock with
2232  * irqs disabled, and this lock is released upon return, but irqs remain
2233  * disabled.
2234  */
2235 static void __maybe_unused
2236 rcu_report_unblock_qs_rnp(struct rcu_node *rnp, unsigned long flags)
2237         __releases(rnp->lock)
2238 {
2239         unsigned long gps;
2240         unsigned long mask;
2241         struct rcu_node *rnp_p;
2242
2243         raw_lockdep_assert_held_rcu_node(rnp);
2244         if (WARN_ON_ONCE(!IS_ENABLED(CONFIG_PREEMPT)) ||
2245             WARN_ON_ONCE(rcu_preempt_blocked_readers_cgp(rnp)) ||
2246             rnp->qsmask != 0) {
2247                 raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
2248                 return;  /* Still need more quiescent states! */
2249         }
2250
2251         rnp->completedqs = rnp->gp_seq;
2252         rnp_p = rnp->parent;
2253         if (rnp_p == NULL) {
2254                 /*
2255                  * Only one rcu_node structure in the tree, so don't
2256                  * try to report up to its nonexistent parent!
2257                  */
2258                 rcu_report_qs_rsp(flags);
2259                 return;
2260         }
2261
2262         /* Report up the rest of the hierarchy, tracking current ->gp_seq. */
2263         gps = rnp->gp_seq;
2264         mask = rnp->grpmask;
2265         raw_spin_unlock_rcu_node(rnp);  /* irqs remain disabled. */
2266         raw_spin_lock_rcu_node(rnp_p);  /* irqs already disabled. */
2267         rcu_report_qs_rnp(mask, rnp_p, gps, flags);
2268 }
2269
2270 /*
2271  * Record a quiescent state for the specified CPU to that CPU's rcu_data
2272  * structure.  This must be called from the specified CPU.
2273  */
2274 static void
2275 rcu_report_qs_rdp(int cpu, struct rcu_data *rdp)
2276 {
2277         unsigned long flags;
2278         unsigned long mask;
2279         bool needwake;
2280         struct rcu_node *rnp;
2281
2282         rnp = rdp->mynode;
2283         raw_spin_lock_irqsave_rcu_node(rnp, flags);
2284         if (rdp->cpu_no_qs.b.norm || rdp->gp_seq != rnp->gp_seq ||
2285             rdp->gpwrap) {
2286
2287                 /*
2288                  * The grace period in which this quiescent state was
2289                  * recorded has ended, so don't report it upwards.
2290                  * We will instead need a new quiescent state that lies
2291                  * within the current grace period.
2292                  */
2293                 rdp->cpu_no_qs.b.norm = true;   /* need qs for new gp. */
2294                 raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
2295                 return;
2296         }
2297         mask = rdp->grpmask;
2298         if ((rnp->qsmask & mask) == 0) {
2299                 raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
2300         } else {
2301                 rdp->core_needs_qs = false;
2302
2303                 /*
2304                  * This GP can't end until cpu checks in, so all of our
2305                  * callbacks can be processed during the next GP.
2306                  */
2307                 needwake = rcu_accelerate_cbs(rnp, rdp);
2308
2309                 rcu_report_qs_rnp(mask, rnp, rnp->gp_seq, flags);
2310                 /* ^^^ Released rnp->lock */
2311                 if (needwake)
2312                         rcu_gp_kthread_wake();
2313         }
2314 }
2315
2316 /*
2317  * Check to see if there is a new grace period of which this CPU
2318  * is not yet aware, and if so, set up local rcu_data state for it.
2319  * Otherwise, see if this CPU has just passed through its first
2320  * quiescent state for this grace period, and record that fact if so.
2321  */
2322 static void
2323 rcu_check_quiescent_state(struct rcu_data *rdp)
2324 {
2325         /* Check for grace-period ends and beginnings. */
2326         note_gp_changes(rdp);
2327
2328         /*
2329          * Does this CPU still need to do its part for current grace period?
2330          * If no, return and let the other CPUs do their part as well.
2331          */
2332         if (!rdp->core_needs_qs)
2333                 return;
2334
2335         /*
2336          * Was there a quiescent state since the beginning of the grace
2337          * period? If no, then exit and wait for the next call.
2338          */
2339         if (rdp->cpu_no_qs.b.norm)
2340                 return;
2341
2342         /*
2343          * Tell RCU we are done (but rcu_report_qs_rdp() will be the
2344          * judge of that).
2345          */
2346         rcu_report_qs_rdp(rdp->cpu, rdp);
2347 }
2348
2349 /*
2350  * Near the end of the offline process.  Trace the fact that this CPU
2351  * is going offline.
2352  */
2353 int rcutree_dying_cpu(unsigned int cpu)
2354 {
2355         RCU_TRACE(bool blkd;)
2356         RCU_TRACE(struct rcu_data *rdp = this_cpu_ptr(&rcu_data);)
2357         RCU_TRACE(struct rcu_node *rnp = rdp->mynode;)
2358
2359         if (!IS_ENABLED(CONFIG_HOTPLUG_CPU))
2360                 return 0;
2361
2362         RCU_TRACE(blkd = !!(rnp->qsmask & rdp->grpmask);)
2363         trace_rcu_grace_period(rcu_state.name, rnp->gp_seq,
2364                                blkd ? TPS("cpuofl") : TPS("cpuofl-bgp"));
2365         return 0;
2366 }
2367
2368 /*
2369  * All CPUs for the specified rcu_node structure have gone offline,
2370  * and all tasks that were preempted within an RCU read-side critical
2371  * section while running on one of those CPUs have since exited their RCU
2372  * read-side critical section.  Some other CPU is reporting this fact with
2373  * the specified rcu_node structure's ->lock held and interrupts disabled.
2374  * This function therefore goes up the tree of rcu_node structures,
2375  * clearing the corresponding bits in the ->qsmaskinit fields.  Note that
2376  * the leaf rcu_node structure's ->qsmaskinit field has already been
2377  * updated.
2378  *
2379  * This function does check that the specified rcu_node structure has
2380  * all CPUs offline and no blocked tasks, so it is OK to invoke it
2381  * prematurely.  That said, invoking it after the fact will cost you
2382  * a needless lock acquisition.  So once it has done its work, don't
2383  * invoke it again.
2384  */
2385 static void rcu_cleanup_dead_rnp(struct rcu_node *rnp_leaf)
2386 {
2387         long mask;
2388         struct rcu_node *rnp = rnp_leaf;
2389
2390         raw_lockdep_assert_held_rcu_node(rnp_leaf);
2391         if (!IS_ENABLED(CONFIG_HOTPLUG_CPU) ||
2392             WARN_ON_ONCE(rnp_leaf->qsmaskinit) ||
2393             WARN_ON_ONCE(rcu_preempt_has_tasks(rnp_leaf)))
2394                 return;
2395         for (;;) {
2396                 mask = rnp->grpmask;
2397                 rnp = rnp->parent;
2398                 if (!rnp)
2399                         break;
2400                 raw_spin_lock_rcu_node(rnp); /* irqs already disabled. */
2401                 rnp->qsmaskinit &= ~mask;
2402                 /* Between grace periods, so better already be zero! */
2403                 WARN_ON_ONCE(rnp->qsmask);
2404                 if (rnp->qsmaskinit) {
2405                         raw_spin_unlock_rcu_node(rnp);
2406                         /* irqs remain disabled. */
2407                         return;
2408                 }
2409                 raw_spin_unlock_rcu_node(rnp); /* irqs remain disabled. */
2410         }
2411 }
2412
2413 /*
2414  * The CPU has been completely removed, and some other CPU is reporting
2415  * this fact from process context.  Do the remainder of the cleanup.
2416  * There can only be one CPU hotplug operation at a time, so no need for
2417  * explicit locking.
2418  */
2419 int rcutree_dead_cpu(unsigned int cpu)
2420 {
2421         struct rcu_data *rdp = per_cpu_ptr(&rcu_data, cpu);
2422         struct rcu_node *rnp = rdp->mynode;  /* Outgoing CPU's rdp & rnp. */
2423
2424         if (!IS_ENABLED(CONFIG_HOTPLUG_CPU))
2425                 return 0;
2426
2427         /* Adjust any no-longer-needed kthreads. */
2428         rcu_boost_kthread_setaffinity(rnp, -1);
2429         /* Do any needed no-CB deferred wakeups from this CPU. */
2430         do_nocb_deferred_wakeup(per_cpu_ptr(&rcu_data, cpu));
2431         return 0;
2432 }
2433
2434 /*
2435  * Invoke any RCU callbacks that have made it to the end of their grace
2436  * period.  Thottle as specified by rdp->blimit.
2437  */
2438 static void rcu_do_batch(struct rcu_data *rdp)
2439 {
2440         unsigned long flags;
2441         struct rcu_head *rhp;
2442         struct rcu_cblist rcl = RCU_CBLIST_INITIALIZER(rcl);
2443         long bl, count;
2444
2445         /* If no callbacks are ready, just return. */
2446         if (!rcu_segcblist_ready_cbs(&rdp->cblist)) {
2447                 trace_rcu_batch_start(rcu_state.name,
2448                                       rcu_segcblist_n_lazy_cbs(&rdp->cblist),
2449                                       rcu_segcblist_n_cbs(&rdp->cblist), 0);
2450                 trace_rcu_batch_end(rcu_state.name, 0,
2451                                     !rcu_segcblist_empty(&rdp->cblist),
2452                                     need_resched(), is_idle_task(current),
2453                                     rcu_is_callbacks_kthread());
2454                 return;
2455         }
2456
2457         /*
2458          * Extract the list of ready callbacks, disabling to prevent
2459          * races with call_rcu() from interrupt handlers.  Leave the
2460          * callback counts, as rcu_barrier() needs to be conservative.
2461          */
2462         local_irq_save(flags);
2463         WARN_ON_ONCE(cpu_is_offline(smp_processor_id()));
2464         bl = rdp->blimit;
2465         trace_rcu_batch_start(rcu_state.name,
2466                               rcu_segcblist_n_lazy_cbs(&rdp->cblist),
2467                               rcu_segcblist_n_cbs(&rdp->cblist), bl);
2468         rcu_segcblist_extract_done_cbs(&rdp->cblist, &rcl);
2469         local_irq_restore(flags);
2470
2471         /* Invoke callbacks. */
2472         rhp = rcu_cblist_dequeue(&rcl);
2473         for (; rhp; rhp = rcu_cblist_dequeue(&rcl)) {
2474                 debug_rcu_head_unqueue(rhp);
2475                 if (__rcu_reclaim(rcu_state.name, rhp))
2476                         rcu_cblist_dequeued_lazy(&rcl);
2477                 /*
2478                  * Stop only if limit reached and CPU has something to do.
2479                  * Note: The rcl structure counts down from zero.
2480                  */
2481                 if (-rcl.len >= bl &&
2482                     (need_resched() ||
2483                      (!is_idle_task(current) && !rcu_is_callbacks_kthread())))
2484                         break;
2485         }
2486
2487         local_irq_save(flags);
2488         count = -rcl.len;
2489         trace_rcu_batch_end(rcu_state.name, count, !!rcl.head, need_resched(),
2490                             is_idle_task(current), rcu_is_callbacks_kthread());
2491
2492         /* Update counts and requeue any remaining callbacks. */
2493         rcu_segcblist_insert_done_cbs(&rdp->cblist, &rcl);
2494         smp_mb(); /* List handling before counting for rcu_barrier(). */
2495         rcu_segcblist_insert_count(&rdp->cblist, &rcl);
2496
2497         /* Reinstate batch limit if we have worked down the excess. */
2498         count = rcu_segcblist_n_cbs(&rdp->cblist);
2499         if (rdp->blimit == LONG_MAX && count <= qlowmark)
2500                 rdp->blimit = blimit;
2501
2502         /* Reset ->qlen_last_fqs_check trigger if enough CBs have drained. */
2503         if (count == 0 && rdp->qlen_last_fqs_check != 0) {
2504                 rdp->qlen_last_fqs_check = 0;
2505                 rdp->n_force_qs_snap = rcu_state.n_force_qs;
2506         } else if (count < rdp->qlen_last_fqs_check - qhimark)
2507                 rdp->qlen_last_fqs_check = count;
2508
2509         /*
2510          * The following usually indicates a double call_rcu().  To track
2511          * this down, try building with CONFIG_DEBUG_OBJECTS_RCU_HEAD=y.
2512          */
2513         WARN_ON_ONCE(rcu_segcblist_empty(&rdp->cblist) != (count == 0));
2514
2515         local_irq_restore(flags);
2516
2517         /* Re-invoke RCU core processing if there are callbacks remaining. */
2518         if (rcu_segcblist_ready_cbs(&rdp->cblist))
2519                 invoke_rcu_core();
2520 }
2521
2522 /*
2523  * This function is invoked from each scheduling-clock interrupt,
2524  * and checks to see if this CPU is in a non-context-switch quiescent
2525  * state, for example, user mode or idle loop.  It also schedules RCU
2526  * core processing.  If the current grace period has gone on too long,
2527  * it will ask the scheduler to manufacture a context switch for the sole
2528  * purpose of providing a providing the needed quiescent state.
2529  */
2530 void rcu_sched_clock_irq(int user)
2531 {
2532         trace_rcu_utilization(TPS("Start scheduler-tick"));
2533         raw_cpu_inc(rcu_data.ticks_this_gp);
2534         /* The load-acquire pairs with the store-release setting to true. */
2535         if (smp_load_acquire(this_cpu_ptr(&rcu_data.rcu_urgent_qs))) {
2536                 /* Idle and userspace execution already are quiescent states. */
2537                 if (!rcu_is_cpu_rrupt_from_idle() && !user) {
2538                         set_tsk_need_resched(current);
2539                         set_preempt_need_resched();
2540                 }
2541                 __this_cpu_write(rcu_data.rcu_urgent_qs, false);
2542         }
2543         rcu_flavor_sched_clock_irq(user);
2544         if (rcu_pending())
2545                 invoke_rcu_core();
2546
2547         trace_rcu_utilization(TPS("End scheduler-tick"));
2548 }
2549
2550 /*
2551  * Scan the leaf rcu_node structures, processing dyntick state for any that
2552  * have not yet encountered a quiescent state, using the function specified.
2553  * Also initiate boosting for any threads blocked on the root rcu_node.
2554  *
2555  * The caller must have suppressed start of new grace periods.
2556  */
2557 static void force_qs_rnp(int (*f)(struct rcu_data *rdp))
2558 {
2559         int cpu;
2560         unsigned long flags;
2561         unsigned long mask;
2562         struct rcu_node *rnp;
2563
2564         rcu_for_each_leaf_node(rnp) {
2565                 cond_resched_tasks_rcu_qs();
2566                 mask = 0;
2567                 raw_spin_lock_irqsave_rcu_node(rnp, flags);
2568                 if (rnp->qsmask == 0) {
2569                         if (!IS_ENABLED(CONFIG_PREEMPT) ||
2570                             rcu_preempt_blocked_readers_cgp(rnp)) {
2571                                 /*
2572                                  * No point in scanning bits because they
2573                                  * are all zero.  But we might need to
2574                                  * priority-boost blocked readers.
2575                                  */
2576                                 rcu_initiate_boost(rnp, flags);
2577                                 /* rcu_initiate_boost() releases rnp->lock */
2578                                 continue;
2579                         }
2580                         raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
2581                         continue;
2582                 }
2583                 for_each_leaf_node_possible_cpu(rnp, cpu) {
2584                         unsigned long bit = leaf_node_cpu_bit(rnp, cpu);
2585                         if ((rnp->qsmask & bit) != 0) {
2586                                 if (f(per_cpu_ptr(&rcu_data, cpu)))
2587                                         mask |= bit;
2588                         }
2589                 }
2590                 if (mask != 0) {
2591                         /* Idle/offline CPUs, report (releases rnp->lock). */
2592                         rcu_report_qs_rnp(mask, rnp, rnp->gp_seq, flags);
2593                 } else {
2594                         /* Nothing to do here, so just drop the lock. */
2595                         raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
2596                 }
2597         }
2598 }
2599
2600 /*
2601  * Force quiescent states on reluctant CPUs, and also detect which
2602  * CPUs are in dyntick-idle mode.
2603  */
2604 void rcu_force_quiescent_state(void)
2605 {
2606         unsigned long flags;
2607         bool ret;
2608         struct rcu_node *rnp;
2609         struct rcu_node *rnp_old = NULL;
2610
2611         /* Funnel through hierarchy to reduce memory contention. */
2612         rnp = __this_cpu_read(rcu_data.mynode);
2613         for (; rnp != NULL; rnp = rnp->parent) {
2614                 ret = (READ_ONCE(rcu_state.gp_flags) & RCU_GP_FLAG_FQS) ||
2615                       !raw_spin_trylock(&rnp->fqslock);
2616                 if (rnp_old != NULL)
2617                         raw_spin_unlock(&rnp_old->fqslock);
2618                 if (ret)
2619                         return;
2620                 rnp_old = rnp;
2621         }
2622         /* rnp_old == rcu_get_root(), rnp == NULL. */
2623
2624         /* Reached the root of the rcu_node tree, acquire lock. */
2625         raw_spin_lock_irqsave_rcu_node(rnp_old, flags);
2626         raw_spin_unlock(&rnp_old->fqslock);
2627         if (READ_ONCE(rcu_state.gp_flags) & RCU_GP_FLAG_FQS) {
2628                 raw_spin_unlock_irqrestore_rcu_node(rnp_old, flags);
2629                 return;  /* Someone beat us to it. */
2630         }
2631         WRITE_ONCE(rcu_state.gp_flags,
2632                    READ_ONCE(rcu_state.gp_flags) | RCU_GP_FLAG_FQS);
2633         raw_spin_unlock_irqrestore_rcu_node(rnp_old, flags);
2634         rcu_gp_kthread_wake();
2635 }
2636 EXPORT_SYMBOL_GPL(rcu_force_quiescent_state);
2637
2638 /*
2639  * This function checks for grace-period requests that fail to motivate
2640  * RCU to come out of its idle mode.
2641  */
2642 void
2643 rcu_check_gp_start_stall(struct rcu_node *rnp, struct rcu_data *rdp,
2644                          const unsigned long gpssdelay)
2645 {
2646         unsigned long flags;
2647         unsigned long j;
2648         struct rcu_node *rnp_root = rcu_get_root();
2649         static atomic_t warned = ATOMIC_INIT(0);
2650
2651         if (!IS_ENABLED(CONFIG_PROVE_RCU) || rcu_gp_in_progress() ||
2652             ULONG_CMP_GE(rnp_root->gp_seq, rnp_root->gp_seq_needed))
2653                 return;
2654         j = jiffies; /* Expensive access, and in common case don't get here. */
2655         if (time_before(j, READ_ONCE(rcu_state.gp_req_activity) + gpssdelay) ||
2656             time_before(j, READ_ONCE(rcu_state.gp_activity) + gpssdelay) ||
2657             atomic_read(&warned))
2658                 return;
2659
2660         raw_spin_lock_irqsave_rcu_node(rnp, flags);
2661         j = jiffies;
2662         if (rcu_gp_in_progress() ||
2663             ULONG_CMP_GE(rnp_root->gp_seq, rnp_root->gp_seq_needed) ||
2664             time_before(j, READ_ONCE(rcu_state.gp_req_activity) + gpssdelay) ||
2665             time_before(j, READ_ONCE(rcu_state.gp_activity) + gpssdelay) ||
2666             atomic_read(&warned)) {
2667                 raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
2668                 return;
2669         }
2670         /* Hold onto the leaf lock to make others see warned==1. */
2671
2672         if (rnp_root != rnp)
2673                 raw_spin_lock_rcu_node(rnp_root); /* irqs already disabled. */
2674         j = jiffies;
2675         if (rcu_gp_in_progress() ||
2676             ULONG_CMP_GE(rnp_root->gp_seq, rnp_root->gp_seq_needed) ||
2677             time_before(j, rcu_state.gp_req_activity + gpssdelay) ||
2678             time_before(j, rcu_state.gp_activity + gpssdelay) ||
2679             atomic_xchg(&warned, 1)) {
2680                 raw_spin_unlock_rcu_node(rnp_root); /* irqs remain disabled. */
2681                 raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
2682                 return;
2683         }
2684         WARN_ON(1);
2685         if (rnp_root != rnp)
2686                 raw_spin_unlock_rcu_node(rnp_root);
2687         raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
2688         show_rcu_gp_kthreads();
2689 }
2690
2691 /*
2692  * Do a forward-progress check for rcutorture.  This is normally invoked
2693  * due to an OOM event.  The argument "j" gives the time period during
2694  * which rcutorture would like progress to have been made.
2695  */
2696 void rcu_fwd_progress_check(unsigned long j)
2697 {
2698         unsigned long cbs;
2699         int cpu;
2700         unsigned long max_cbs = 0;
2701         int max_cpu = -1;
2702         struct rcu_data *rdp;
2703
2704         if (rcu_gp_in_progress()) {
2705                 pr_info("%s: GP age %lu jiffies\n",
2706                         __func__, jiffies - rcu_state.gp_start);
2707                 show_rcu_gp_kthreads();
2708         } else {
2709                 pr_info("%s: Last GP end %lu jiffies ago\n",
2710                         __func__, jiffies - rcu_state.gp_end);
2711                 preempt_disable();
2712                 rdp = this_cpu_ptr(&rcu_data);
2713                 rcu_check_gp_start_stall(rdp->mynode, rdp, j);
2714                 preempt_enable();
2715         }
2716         for_each_possible_cpu(cpu) {
2717                 cbs = rcu_get_n_cbs_cpu(cpu);
2718                 if (!cbs)
2719                         continue;
2720                 if (max_cpu < 0)
2721                         pr_info("%s: callbacks", __func__);
2722                 pr_cont(" %d: %lu", cpu, cbs);
2723                 if (cbs <= max_cbs)
2724                         continue;
2725                 max_cbs = cbs;
2726                 max_cpu = cpu;
2727         }
2728         if (max_cpu >= 0)
2729                 pr_cont("\n");
2730 }
2731 EXPORT_SYMBOL_GPL(rcu_fwd_progress_check);
2732
2733 /* Perform RCU core processing work for the current CPU.  */
2734 static __latent_entropy void rcu_core(struct softirq_action *unused)
2735 {
2736         unsigned long flags;
2737         struct rcu_data *rdp = raw_cpu_ptr(&rcu_data);
2738         struct rcu_node *rnp = rdp->mynode;
2739
2740         if (cpu_is_offline(smp_processor_id()))
2741                 return;
2742         trace_rcu_utilization(TPS("Start RCU core"));
2743         WARN_ON_ONCE(!rdp->beenonline);
2744
2745         /* Report any deferred quiescent states if preemption enabled. */
2746         if (!(preempt_count() & PREEMPT_MASK)) {
2747                 rcu_preempt_deferred_qs(current);
2748         } else if (rcu_preempt_need_deferred_qs(current)) {
2749                 set_tsk_need_resched(current);
2750                 set_preempt_need_resched();
2751         }
2752
2753         /* Update RCU state based on any recent quiescent states. */
2754         rcu_check_quiescent_state(rdp);
2755
2756         /* No grace period and unregistered callbacks? */
2757         if (!rcu_gp_in_progress() &&
2758             rcu_segcblist_is_enabled(&rdp->cblist)) {
2759                 local_irq_save(flags);
2760                 if (!rcu_segcblist_restempty(&rdp->cblist, RCU_NEXT_READY_TAIL))
2761                         rcu_accelerate_cbs_unlocked(rnp, rdp);
2762                 local_irq_restore(flags);
2763         }
2764
2765         rcu_check_gp_start_stall(rnp, rdp, rcu_jiffies_till_stall_check());
2766
2767         /* If there are callbacks ready, invoke them. */
2768         if (rcu_segcblist_ready_cbs(&rdp->cblist))
2769                 invoke_rcu_callbacks(rdp);
2770
2771         /* Do any needed deferred wakeups of rcuo kthreads. */
2772         do_nocb_deferred_wakeup(rdp);
2773         trace_rcu_utilization(TPS("End RCU core"));
2774 }
2775
2776 /*
2777  * Schedule RCU callback invocation.  If the running implementation of RCU
2778  * does not support RCU priority boosting, just do a direct call, otherwise
2779  * wake up the per-CPU kernel kthread.  Note that because we are running
2780  * on the current CPU with softirqs disabled, the rcu_cpu_kthread_task
2781  * cannot disappear out from under us.
2782  */
2783 static void invoke_rcu_callbacks(struct rcu_data *rdp)
2784 {
2785         if (unlikely(!READ_ONCE(rcu_scheduler_fully_active)))
2786                 return;
2787         if (likely(!rcu_state.boost)) {
2788                 rcu_do_batch(rdp);
2789                 return;
2790         }
2791         invoke_rcu_callbacks_kthread();
2792 }
2793
2794 static void invoke_rcu_core(void)
2795 {
2796         if (cpu_online(smp_processor_id()))
2797                 raise_softirq(RCU_SOFTIRQ);
2798 }
2799
2800 /*
2801  * Handle any core-RCU processing required by a call_rcu() invocation.
2802  */
2803 static void __call_rcu_core(struct rcu_data *rdp, struct rcu_head *head,
2804                             unsigned long flags)
2805 {
2806         /*
2807          * If called from an extended quiescent state, invoke the RCU
2808          * core in order to force a re-evaluation of RCU's idleness.
2809          */
2810         if (!rcu_is_watching())
2811                 invoke_rcu_core();
2812
2813         /* If interrupts were disabled or CPU offline, don't invoke RCU core. */
2814         if (irqs_disabled_flags(flags) || cpu_is_offline(smp_processor_id()))
2815                 return;
2816
2817         /*
2818          * Force the grace period if too many callbacks or too long waiting.
2819          * Enforce hysteresis, and don't invoke rcu_force_quiescent_state()
2820          * if some other CPU has recently done so.  Also, don't bother
2821          * invoking rcu_force_quiescent_state() if the newly enqueued callback
2822          * is the only one waiting for a grace period to complete.
2823          */
2824         if (unlikely(rcu_segcblist_n_cbs(&rdp->cblist) >
2825                      rdp->qlen_last_fqs_check + qhimark)) {
2826
2827                 /* Are we ignoring a completed grace period? */
2828                 note_gp_changes(rdp);
2829
2830                 /* Start a new grace period if one not already started. */
2831                 if (!rcu_gp_in_progress()) {
2832                         rcu_accelerate_cbs_unlocked(rdp->mynode, rdp);
2833                 } else {
2834                         /* Give the grace period a kick. */
2835                         rdp->blimit = LONG_MAX;
2836                         if (rcu_state.n_force_qs == rdp->n_force_qs_snap &&
2837                             rcu_segcblist_first_pend_cb(&rdp->cblist) != head)
2838                                 rcu_force_quiescent_state();
2839                         rdp->n_force_qs_snap = rcu_state.n_force_qs;
2840                         rdp->qlen_last_fqs_check = rcu_segcblist_n_cbs(&rdp->cblist);
2841                 }
2842         }
2843 }
2844
2845 /*
2846  * RCU callback function to leak a callback.
2847  */
2848 static void rcu_leak_callback(struct rcu_head *rhp)
2849 {
2850 }
2851
2852 /*
2853  * Helper function for call_rcu() and friends.  The cpu argument will
2854  * normally be -1, indicating "currently running CPU".  It may specify
2855  * a CPU only if that CPU is a no-CBs CPU.  Currently, only rcu_barrier()
2856  * is expected to specify a CPU.
2857  */
2858 static void
2859 __call_rcu(struct rcu_head *head, rcu_callback_t func, int cpu, bool lazy)
2860 {
2861         unsigned long flags;
2862         struct rcu_data *rdp;
2863
2864         /* Misaligned rcu_head! */
2865         WARN_ON_ONCE((unsigned long)head & (sizeof(void *) - 1));
2866
2867         if (debug_rcu_head_queue(head)) {
2868                 /*
2869                  * Probable double call_rcu(), so leak the callback.
2870                  * Use rcu:rcu_callback trace event to find the previous
2871                  * time callback was passed to __call_rcu().
2872                  */
2873                 WARN_ONCE(1, "__call_rcu(): Double-freed CB %p->%pF()!!!\n",
2874                           head, head->func);
2875                 WRITE_ONCE(head->func, rcu_leak_callback);
2876                 return;
2877         }
2878         head->func = func;
2879         head->next = NULL;
2880         local_irq_save(flags);
2881         rdp = this_cpu_ptr(&rcu_data);
2882
2883         /* Add the callback to our list. */
2884         if (unlikely(!rcu_segcblist_is_enabled(&rdp->cblist)) || cpu != -1) {
2885                 int offline;
2886
2887                 if (cpu != -1)
2888                         rdp = per_cpu_ptr(&rcu_data, cpu);
2889                 if (likely(rdp->mynode)) {
2890                         /* Post-boot, so this should be for a no-CBs CPU. */
2891                         offline = !__call_rcu_nocb(rdp, head, lazy, flags);
2892                         WARN_ON_ONCE(offline);
2893                         /* Offline CPU, _call_rcu() illegal, leak callback.  */
2894                         local_irq_restore(flags);
2895                         return;
2896                 }
2897                 /*
2898                  * Very early boot, before rcu_init().  Initialize if needed
2899                  * and then drop through to queue the callback.
2900                  */
2901                 WARN_ON_ONCE(cpu != -1);
2902                 WARN_ON_ONCE(!rcu_is_watching());
2903                 if (rcu_segcblist_empty(&rdp->cblist))
2904                         rcu_segcblist_init(&rdp->cblist);
2905         }
2906         rcu_segcblist_enqueue(&rdp->cblist, head, lazy);
2907         if (__is_kfree_rcu_offset((unsigned long)func))
2908                 trace_rcu_kfree_callback(rcu_state.name, head,
2909                                          (unsigned long)func,
2910                                          rcu_segcblist_n_lazy_cbs(&rdp->cblist),
2911                                          rcu_segcblist_n_cbs(&rdp->cblist));
2912         else
2913                 trace_rcu_callback(rcu_state.name, head,
2914                                    rcu_segcblist_n_lazy_cbs(&rdp->cblist),
2915                                    rcu_segcblist_n_cbs(&rdp->cblist));
2916
2917         /* Go handle any RCU core processing required. */
2918         __call_rcu_core(rdp, head, flags);
2919         local_irq_restore(flags);
2920 }
2921
2922 /**
2923  * call_rcu() - Queue an RCU callback for invocation after a grace period.
2924  * @head: structure to be used for queueing the RCU updates.
2925  * @func: actual callback function to be invoked after the grace period
2926  *
2927  * The callback function will be invoked some time after a full grace
2928  * period elapses, in other words after all pre-existing RCU read-side
2929  * critical sections have completed.  However, the callback function
2930  * might well execute concurrently with RCU read-side critical sections
2931  * that started after call_rcu() was invoked.  RCU read-side critical
2932  * sections are delimited by rcu_read_lock() and rcu_read_unlock(), and
2933  * may be nested.  In addition, regions of code across which interrupts,
2934  * preemption, or softirqs have been disabled also serve as RCU read-side
2935  * critical sections.  This includes hardware interrupt handlers, softirq
2936  * handlers, and NMI handlers.
2937  *
2938  * Note that all CPUs must agree that the grace period extended beyond
2939  * all pre-existing RCU read-side critical section.  On systems with more
2940  * than one CPU, this means that when "func()" is invoked, each CPU is
2941  * guaranteed to have executed a full memory barrier since the end of its
2942  * last RCU read-side critical section whose beginning preceded the call
2943  * to call_rcu().  It also means that each CPU executing an RCU read-side
2944  * critical section that continues beyond the start of "func()" must have
2945  * executed a memory barrier after the call_rcu() but before the beginning
2946  * of that RCU read-side critical section.  Note that these guarantees
2947  * include CPUs that are offline, idle, or executing in user mode, as
2948  * well as CPUs that are executing in the kernel.
2949  *
2950  * Furthermore, if CPU A invoked call_rcu() and CPU B invoked the
2951  * resulting RCU callback function "func()", then both CPU A and CPU B are
2952  * guaranteed to execute a full memory barrier during the time interval
2953  * between the call to call_rcu() and the invocation of "func()" -- even
2954  * if CPU A and CPU B are the same CPU (but again only if the system has
2955  * more than one CPU).
2956  */
2957 void call_rcu(struct rcu_head *head, rcu_callback_t func)
2958 {
2959         __call_rcu(head, func, -1, 0);
2960 }
2961 EXPORT_SYMBOL_GPL(call_rcu);
2962
2963 /*
2964  * Queue an RCU callback for lazy invocation after a grace period.
2965  * This will likely be later named something like "call_rcu_lazy()",
2966  * but this change will require some way of tagging the lazy RCU
2967  * callbacks in the list of pending callbacks. Until then, this
2968  * function may only be called from __kfree_rcu().
2969  */
2970 void kfree_call_rcu(struct rcu_head *head, rcu_callback_t func)
2971 {
2972         __call_rcu(head, func, -1, 1);
2973 }
2974 EXPORT_SYMBOL_GPL(kfree_call_rcu);
2975
2976 /*
2977  * During early boot, any blocking grace-period wait automatically
2978  * implies a grace period.  Later on, this is never the case for PREEMPT.
2979  *
2980  * Howevr, because a context switch is a grace period for !PREEMPT, any
2981  * blocking grace-period wait automatically implies a grace period if
2982  * there is only one CPU online at any point time during execution of
2983  * either synchronize_rcu() or synchronize_rcu_expedited().  It is OK to
2984  * occasionally incorrectly indicate that there are multiple CPUs online
2985  * when there was in fact only one the whole time, as this just adds some
2986  * overhead: RCU still operates correctly.
2987  */
2988 static int rcu_blocking_is_gp(void)
2989 {
2990         int ret;
2991
2992         if (IS_ENABLED(CONFIG_PREEMPT))
2993                 return rcu_scheduler_active == RCU_SCHEDULER_INACTIVE;
2994         might_sleep();  /* Check for RCU read-side critical section. */
2995         preempt_disable();
2996         ret = num_online_cpus() <= 1;
2997         preempt_enable();
2998         return ret;
2999 }
3000
3001 /**
3002  * synchronize_rcu - wait until a grace period has elapsed.
3003  *
3004  * Control will return to the caller some time after a full grace
3005  * period has elapsed, in other words after all currently executing RCU
3006  * read-side critical sections have completed.  Note, however, that
3007  * upon return from synchronize_rcu(), the caller might well be executing
3008  * concurrently with new RCU read-side critical sections that began while
3009  * synchronize_rcu() was waiting.  RCU read-side critical sections are
3010  * delimited by rcu_read_lock() and rcu_read_unlock(), and may be nested.
3011  * In addition, regions of code across which interrupts, preemption, or
3012  * softirqs have been disabled also serve as RCU read-side critical
3013  * sections.  This includes hardware interrupt handlers, softirq handlers,
3014  * and NMI handlers.
3015  *
3016  * Note that this guarantee implies further memory-ordering guarantees.
3017  * On systems with more than one CPU, when synchronize_rcu() returns,
3018  * each CPU is guaranteed to have executed a full memory barrier since
3019  * the end of its last RCU read-side critical section whose beginning
3020  * preceded the call to synchronize_rcu().  In addition, each CPU having
3021  * an RCU read-side critical section that extends beyond the return from
3022  * synchronize_rcu() is guaranteed to have executed a full memory barrier
3023  * after the beginning of synchronize_rcu() and before the beginning of
3024  * that RCU read-side critical section.  Note that these guarantees include
3025  * CPUs that are offline, idle, or executing in user mode, as well as CPUs
3026  * that are executing in the kernel.
3027  *
3028  * Furthermore, if CPU A invoked synchronize_rcu(), which returned
3029  * to its caller on CPU B, then both CPU A and CPU B are guaranteed
3030  * to have executed a full memory barrier during the execution of
3031  * synchronize_rcu() -- even if CPU A and CPU B are the same CPU (but
3032  * again only if the system has more than one CPU).
3033  */
3034 void synchronize_rcu(void)
3035 {
3036         RCU_LOCKDEP_WARN(lock_is_held(&rcu_bh_lock_map) ||
3037                          lock_is_held(&rcu_lock_map) ||
3038                          lock_is_held(&rcu_sched_lock_map),
3039                          "Illegal synchronize_rcu() in RCU read-side critical section");
3040         if (rcu_blocking_is_gp())
3041                 return;
3042         if (rcu_gp_is_expedited())
3043                 synchronize_rcu_expedited();
3044         else
3045                 wait_rcu_gp(call_rcu);
3046 }
3047 EXPORT_SYMBOL_GPL(synchronize_rcu);
3048
3049 /**
3050  * get_state_synchronize_rcu - Snapshot current RCU state
3051  *
3052  * Returns a cookie that is used by a later call to cond_synchronize_rcu()
3053  * to determine whether or not a full grace period has elapsed in the
3054  * meantime.
3055  */
3056 unsigned long get_state_synchronize_rcu(void)
3057 {
3058         /*
3059          * Any prior manipulation of RCU-protected data must happen
3060          * before the load from ->gp_seq.
3061          */
3062         smp_mb();  /* ^^^ */
3063         return rcu_seq_snap(&rcu_state.gp_seq);
3064 }
3065 EXPORT_SYMBOL_GPL(get_state_synchronize_rcu);
3066
3067 /**
3068  * cond_synchronize_rcu - Conditionally wait for an RCU grace period
3069  *
3070  * @oldstate: return value from earlier call to get_state_synchronize_rcu()
3071  *
3072  * If a full RCU grace period has elapsed since the earlier call to
3073  * get_state_synchronize_rcu(), just return.  Otherwise, invoke
3074  * synchronize_rcu() to wait for a full grace period.
3075  *
3076  * Yes, this function does not take counter wrap into account.  But
3077  * counter wrap is harmless.  If the counter wraps, we have waited for
3078  * more than 2 billion grace periods (and way more on a 64-bit system!),
3079  * so waiting for one additional grace period should be just fine.
3080  */
3081 void cond_synchronize_rcu(unsigned long oldstate)
3082 {
3083         if (!rcu_seq_done(&rcu_state.gp_seq, oldstate))
3084                 synchronize_rcu();
3085         else
3086                 smp_mb(); /* Ensure GP ends before subsequent accesses. */
3087 }
3088 EXPORT_SYMBOL_GPL(cond_synchronize_rcu);
3089
3090 /*
3091  * Check to see if there is any immediate RCU-related work to be done by
3092  * the current CPU, returning 1 if so and zero otherwise.  The checks are
3093  * in order of increasing expense: checks that can be carried out against
3094  * CPU-local state are performed first.  However, we must check for CPU
3095  * stalls first, else we might not get a chance.
3096  */
3097 static int rcu_pending(void)
3098 {
3099         struct rcu_data *rdp = this_cpu_ptr(&rcu_data);
3100         struct rcu_node *rnp = rdp->mynode;
3101
3102         /* Check for CPU stalls, if enabled. */
3103         check_cpu_stall(rdp);
3104
3105         /* Is this CPU a NO_HZ_FULL CPU that should ignore RCU? */
3106         if (rcu_nohz_full_cpu())
3107                 return 0;
3108
3109         /* Is the RCU core waiting for a quiescent state from this CPU? */
3110         if (rdp->core_needs_qs && !rdp->cpu_no_qs.b.norm)
3111                 return 1;
3112
3113         /* Does this CPU have callbacks ready to invoke? */
3114         if (rcu_segcblist_ready_cbs(&rdp->cblist))
3115                 return 1;
3116
3117         /* Has RCU gone idle with this CPU needing another grace period? */
3118         if (!rcu_gp_in_progress() &&
3119             rcu_segcblist_is_enabled(&rdp->cblist) &&
3120             !rcu_segcblist_restempty(&rdp->cblist, RCU_NEXT_READY_TAIL))
3121                 return 1;
3122
3123         /* Have RCU grace period completed or started?  */
3124         if (rcu_seq_current(&rnp->gp_seq) != rdp->gp_seq ||
3125             unlikely(READ_ONCE(rdp->gpwrap))) /* outside lock */
3126                 return 1;
3127
3128         /* Does this CPU need a deferred NOCB wakeup? */
3129         if (rcu_nocb_need_deferred_wakeup(rdp))
3130                 return 1;
3131
3132         /* nothing to do */
3133         return 0;
3134 }
3135
3136 /*
3137  * Helper function for rcu_barrier() tracing.  If tracing is disabled,
3138  * the compiler is expected to optimize this away.
3139  */
3140 static void rcu_barrier_trace(const char *s, int cpu, unsigned long done)
3141 {
3142         trace_rcu_barrier(rcu_state.name, s, cpu,
3143                           atomic_read(&rcu_state.barrier_cpu_count), done);
3144 }
3145
3146 /*
3147  * RCU callback function for rcu_barrier().  If we are last, wake
3148  * up the task executing rcu_barrier().
3149  */
3150 static void rcu_barrier_callback(struct rcu_head *rhp)
3151 {
3152         if (atomic_dec_and_test(&rcu_state.barrier_cpu_count)) {
3153                 rcu_barrier_trace(TPS("LastCB"), -1,
3154                                    rcu_state.barrier_sequence);
3155                 complete(&rcu_state.barrier_completion);
3156         } else {
3157                 rcu_barrier_trace(TPS("CB"), -1, rcu_state.barrier_sequence);
3158         }
3159 }
3160
3161 /*
3162  * Called with preemption disabled, and from cross-cpu IRQ context.
3163  */
3164 static void rcu_barrier_func(void *unused)
3165 {
3166         struct rcu_data *rdp = raw_cpu_ptr(&rcu_data);
3167
3168         rcu_barrier_trace(TPS("IRQ"), -1, rcu_state.barrier_sequence);
3169         rdp->barrier_head.func = rcu_barrier_callback;
3170         debug_rcu_head_queue(&rdp->barrier_head);
3171         if (rcu_segcblist_entrain(&rdp->cblist, &rdp->barrier_head, 0)) {
3172                 atomic_inc(&rcu_state.barrier_cpu_count);
3173         } else {
3174                 debug_rcu_head_unqueue(&rdp->barrier_head);
3175                 rcu_barrier_trace(TPS("IRQNQ"), -1,
3176                                    rcu_state.barrier_sequence);
3177         }
3178 }
3179
3180 /**
3181  * rcu_barrier - Wait until all in-flight call_rcu() callbacks complete.
3182  *
3183  * Note that this primitive does not necessarily wait for an RCU grace period
3184  * to complete.  For example, if there are no RCU callbacks queued anywhere
3185  * in the system, then rcu_barrier() is within its rights to return
3186  * immediately, without waiting for anything, much less an RCU grace period.
3187  */
3188 void rcu_barrier(void)
3189 {
3190         int cpu;
3191         struct rcu_data *rdp;
3192         unsigned long s = rcu_seq_snap(&rcu_state.barrier_sequence);
3193
3194         rcu_barrier_trace(TPS("Begin"), -1, s);
3195
3196         /* Take mutex to serialize concurrent rcu_barrier() requests. */
3197         mutex_lock(&rcu_state.barrier_mutex);
3198
3199         /* Did someone else do our work for us? */
3200         if (rcu_seq_done(&rcu_state.barrier_sequence, s)) {
3201                 rcu_barrier_trace(TPS("EarlyExit"), -1,
3202                                    rcu_state.barrier_sequence);
3203                 smp_mb(); /* caller's subsequent code after above check. */
3204                 mutex_unlock(&rcu_state.barrier_mutex);
3205                 return;
3206         }
3207
3208         /* Mark the start of the barrier operation. */
3209         rcu_seq_start(&rcu_state.barrier_sequence);
3210         rcu_barrier_trace(TPS("Inc1"), -1, rcu_state.barrier_sequence);
3211
3212         /*
3213          * Initialize the count to one rather than to zero in order to
3214          * avoid a too-soon return to zero in case of a short grace period
3215          * (or preemption of this task).  Exclude CPU-hotplug operations
3216          * to ensure that no offline CPU has callbacks queued.
3217          */
3218         init_completion(&rcu_state.barrier_completion);
3219         atomic_set(&rcu_state.barrier_cpu_count, 1);
3220         get_online_cpus();
3221
3222         /*
3223          * Force each CPU with callbacks to register a new callback.
3224          * When that callback is invoked, we will know that all of the
3225          * corresponding CPU's preceding callbacks have been invoked.
3226          */
3227         for_each_possible_cpu(cpu) {
3228                 if (!cpu_online(cpu) && !rcu_is_nocb_cpu(cpu))
3229                         continue;
3230                 rdp = per_cpu_ptr(&rcu_data, cpu);
3231                 if (rcu_is_nocb_cpu(cpu)) {
3232                         if (!rcu_nocb_cpu_needs_barrier(cpu)) {
3233                                 rcu_barrier_trace(TPS("OfflineNoCB"), cpu,
3234                                                    rcu_state.barrier_sequence);
3235                         } else {
3236                                 rcu_barrier_trace(TPS("OnlineNoCB"), cpu,
3237                                                    rcu_state.barrier_sequence);
3238                                 smp_mb__before_atomic();
3239                                 atomic_inc(&rcu_state.barrier_cpu_count);
3240                                 __call_rcu(&rdp->barrier_head,
3241                                            rcu_barrier_callback, cpu, 0);
3242                         }
3243                 } else if (rcu_segcblist_n_cbs(&rdp->cblist)) {
3244                         rcu_barrier_trace(TPS("OnlineQ"), cpu,
3245                                            rcu_state.barrier_sequence);
3246                         smp_call_function_single(cpu, rcu_barrier_func, NULL, 1);
3247                 } else {
3248                         rcu_barrier_trace(TPS("OnlineNQ"), cpu,
3249                                            rcu_state.barrier_sequence);
3250                 }
3251         }
3252         put_online_cpus();
3253
3254         /*
3255          * Now that we have an rcu_barrier_callback() callback on each
3256          * CPU, and thus each counted, remove the initial count.
3257          */
3258         if (atomic_dec_and_test(&rcu_state.barrier_cpu_count))
3259                 complete(&rcu_state.barrier_completion);
3260
3261         /* Wait for all rcu_barrier_callback() callbacks to be invoked. */
3262         wait_for_completion(&rcu_state.barrier_completion);
3263
3264         /* Mark the end of the barrier operation. */
3265         rcu_barrier_trace(TPS("Inc2"), -1, rcu_state.barrier_sequence);
3266         rcu_seq_end(&rcu_state.barrier_sequence);
3267
3268         /* Other rcu_barrier() invocations can now safely proceed. */
3269         mutex_unlock(&rcu_state.barrier_mutex);
3270 }
3271 EXPORT_SYMBOL_GPL(rcu_barrier);
3272
3273 /*
3274  * Propagate ->qsinitmask bits up the rcu_node tree to account for the
3275  * first CPU in a given leaf rcu_node structure coming online.  The caller
3276  * must hold the corresponding leaf rcu_node ->lock with interrrupts
3277  * disabled.
3278  */
3279 static void rcu_init_new_rnp(struct rcu_node *rnp_leaf)
3280 {
3281         long mask;
3282         long oldmask;
3283         struct rcu_node *rnp = rnp_leaf;
3284
3285         raw_lockdep_assert_held_rcu_node(rnp_leaf);
3286         WARN_ON_ONCE(rnp->wait_blkd_tasks);
3287         for (;;) {
3288                 mask = rnp->grpmask;
3289                 rnp = rnp->parent;
3290                 if (rnp == NULL)
3291                         return;
3292                 raw_spin_lock_rcu_node(rnp); /* Interrupts already disabled. */
3293                 oldmask = rnp->qsmaskinit;
3294                 rnp->qsmaskinit |= mask;
3295                 raw_spin_unlock_rcu_node(rnp); /* Interrupts remain disabled. */
3296                 if (oldmask)
3297                         return;
3298         }
3299 }
3300
3301 /*
3302  * Do boot-time initialization of a CPU's per-CPU RCU data.
3303  */
3304 static void __init
3305 rcu_boot_init_percpu_data(int cpu)
3306 {
3307         struct rcu_data *rdp = per_cpu_ptr(&rcu_data, cpu);
3308
3309         /* Set up local state, ensuring consistent view of global state. */
3310         rdp->grpmask = leaf_node_cpu_bit(rdp->mynode, cpu);
3311         WARN_ON_ONCE(rdp->dynticks_nesting != 1);
3312         WARN_ON_ONCE(rcu_dynticks_in_eqs(rcu_dynticks_snap(rdp)));
3313         rdp->rcu_ofl_gp_seq = rcu_state.gp_seq;
3314         rdp->rcu_ofl_gp_flags = RCU_GP_CLEANED;
3315         rdp->rcu_onl_gp_seq = rcu_state.gp_seq;
3316         rdp->rcu_onl_gp_flags = RCU_GP_CLEANED;
3317         rdp->cpu = cpu;
3318         rcu_boot_init_nocb_percpu_data(rdp);
3319 }
3320
3321 /*
3322  * Invoked early in the CPU-online process, when pretty much all services
3323  * are available.  The incoming CPU is not present.
3324  *
3325  * Initializes a CPU's per-CPU RCU data.  Note that only one online or
3326  * offline event can be happening at a given time.  Note also that we can
3327  * accept some slop in the rsp->gp_seq access due to the fact that this
3328  * CPU cannot possibly have any RCU callbacks in flight yet.
3329  */
3330 int rcutree_prepare_cpu(unsigned int cpu)
3331 {
3332         unsigned long flags;
3333         struct rcu_data *rdp = per_cpu_ptr(&rcu_data, cpu);
3334         struct rcu_node *rnp = rcu_get_root();
3335
3336         /* Set up local state, ensuring consistent view of global state. */
3337         raw_spin_lock_irqsave_rcu_node(rnp, flags);
3338         rdp->qlen_last_fqs_check = 0;
3339         rdp->n_force_qs_snap = rcu_state.n_force_qs;
3340         rdp->blimit = blimit;
3341         if (rcu_segcblist_empty(&rdp->cblist) && /* No early-boot CBs? */
3342             !init_nocb_callback_list(rdp))
3343                 rcu_segcblist_init(&rdp->cblist);  /* Re-enable callbacks. */
3344         rdp->dynticks_nesting = 1;      /* CPU not up, no tearing. */
3345         rcu_dynticks_eqs_online();
3346         raw_spin_unlock_rcu_node(rnp);          /* irqs remain disabled. */
3347
3348         /*
3349          * Add CPU to leaf rcu_node pending-online bitmask.  Any needed
3350          * propagation up the rcu_node tree will happen at the beginning
3351          * of the next grace period.
3352          */
3353         rnp = rdp->mynode;
3354         raw_spin_lock_rcu_node(rnp);            /* irqs already disabled. */
3355         rdp->beenonline = true;  /* We have now been online. */
3356         rdp->gp_seq = rnp->gp_seq;
3357         rdp->gp_seq_needed = rnp->gp_seq;
3358         rdp->cpu_no_qs.b.norm = true;
3359         rdp->core_needs_qs = false;
3360         rdp->rcu_iw_pending = false;
3361         rdp->rcu_iw_gp_seq = rnp->gp_seq - 1;
3362         trace_rcu_grace_period(rcu_state.name, rdp->gp_seq, TPS("cpuonl"));
3363         raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
3364         rcu_prepare_kthreads(cpu);
3365         rcu_spawn_cpu_nocb_kthread(cpu);
3366
3367         return 0;
3368 }
3369
3370 /*
3371  * Update RCU priority boot kthread affinity for CPU-hotplug changes.
3372  */
3373 static void rcutree_affinity_setting(unsigned int cpu, int outgoing)
3374 {
3375         struct rcu_data *rdp = per_cpu_ptr(&rcu_data, cpu);
3376
3377         rcu_boost_kthread_setaffinity(rdp->mynode, outgoing);
3378 }
3379
3380 /*
3381  * Near the end of the CPU-online process.  Pretty much all services
3382  * enabled, and the CPU is now very much alive.
3383  */
3384 int rcutree_online_cpu(unsigned int cpu)
3385 {
3386         unsigned long flags;
3387         struct rcu_data *rdp;
3388         struct rcu_node *rnp;
3389
3390         rdp = per_cpu_ptr(&rcu_data, cpu);
3391         rnp = rdp->mynode;
3392         raw_spin_lock_irqsave_rcu_node(rnp, flags);
3393         rnp->ffmask |= rdp->grpmask;
3394         raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
3395         if (rcu_scheduler_active == RCU_SCHEDULER_INACTIVE)
3396                 return 0; /* Too early in boot for scheduler work. */
3397         sync_sched_exp_online_cleanup(cpu);
3398         rcutree_affinity_setting(cpu, -1);
3399         return 0;
3400 }
3401
3402 /*
3403  * Near the beginning of the process.  The CPU is still very much alive
3404  * with pretty much all services enabled.
3405  */
3406 int rcutree_offline_cpu(unsigned int cpu)
3407 {
3408         unsigned long flags;
3409         struct rcu_data *rdp;
3410         struct rcu_node *rnp;
3411
3412         rdp = per_cpu_ptr(&rcu_data, cpu);
3413         rnp = rdp->mynode;
3414         raw_spin_lock_irqsave_rcu_node(rnp, flags);
3415         rnp->ffmask &= ~rdp->grpmask;
3416         raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
3417
3418         rcutree_affinity_setting(cpu, cpu);
3419         return 0;
3420 }
3421
3422 static DEFINE_PER_CPU(int, rcu_cpu_started);
3423
3424 /*
3425  * Mark the specified CPU as being online so that subsequent grace periods
3426  * (both expedited and normal) will wait on it.  Note that this means that
3427  * incoming CPUs are not allowed to use RCU read-side critical sections
3428  * until this function is called.  Failing to observe this restriction
3429  * will result in lockdep splats.
3430  *
3431  * Note that this function is special in that it is invoked directly
3432  * from the incoming CPU rather than from the cpuhp_step mechanism.
3433  * This is because this function must be invoked at a precise location.
3434  */
3435 void rcu_cpu_starting(unsigned int cpu)
3436 {
3437         unsigned long flags;
3438         unsigned long mask;
3439         int nbits;
3440         unsigned long oldmask;
3441         struct rcu_data *rdp;
3442         struct rcu_node *rnp;
3443
3444         if (per_cpu(rcu_cpu_started, cpu))
3445                 return;
3446
3447         per_cpu(rcu_cpu_started, cpu) = 1;
3448
3449         rdp = per_cpu_ptr(&rcu_data, cpu);
3450         rnp = rdp->mynode;
3451         mask = rdp->grpmask;
3452         raw_spin_lock_irqsave_rcu_node(rnp, flags);
3453         rnp->qsmaskinitnext |= mask;
3454         oldmask = rnp->expmaskinitnext;
3455         rnp->expmaskinitnext |= mask;
3456         oldmask ^= rnp->expmaskinitnext;
3457         nbits = bitmap_weight(&oldmask, BITS_PER_LONG);
3458         /* Allow lockless access for expedited grace periods. */
3459         smp_store_release(&rcu_state.ncpus, rcu_state.ncpus + nbits); /* ^^^ */
3460         rcu_gpnum_ovf(rnp, rdp); /* Offline-induced counter wrap? */
3461         rdp->rcu_onl_gp_seq = READ_ONCE(rcu_state.gp_seq);
3462         rdp->rcu_onl_gp_flags = READ_ONCE(rcu_state.gp_flags);
3463         if (rnp->qsmask & mask) { /* RCU waiting on incoming CPU? */
3464                 /* Report QS -after- changing ->qsmaskinitnext! */
3465                 rcu_report_qs_rnp(mask, rnp, rnp->gp_seq, flags);
3466         } else {
3467                 raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
3468         }
3469         smp_mb(); /* Ensure RCU read-side usage follows above initialization. */
3470 }
3471
3472 #ifdef CONFIG_HOTPLUG_CPU
3473 /*
3474  * The outgoing function has no further need of RCU, so remove it from
3475  * the rcu_node tree's ->qsmaskinitnext bit masks.
3476  *
3477  * Note that this function is special in that it is invoked directly
3478  * from the outgoing CPU rather than from the cpuhp_step mechanism.
3479  * This is because this function must be invoked at a precise location.
3480  */
3481 void rcu_report_dead(unsigned int cpu)
3482 {
3483         unsigned long flags;
3484         unsigned long mask;
3485         struct rcu_data *rdp = per_cpu_ptr(&rcu_data, cpu);
3486         struct rcu_node *rnp = rdp->mynode;  /* Outgoing CPU's rdp & rnp. */
3487
3488         /* QS for any half-done expedited grace period. */
3489         preempt_disable();
3490        &n