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