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