~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/kernel/rcu/tree.c

Version: ~ [ linux-5.6 ] ~ [ linux-5.5.13 ] ~ [ linux-5.4.28 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.113 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.174 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.217 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.217 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.82 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-3.9.11 ] ~ [ linux-3.8.13 ] ~ [ linux-3.7.10 ] ~ [ linux-3.6.11 ] ~ [ linux-3.5.7 ] ~ [ linux-3.4.113 ] ~ [ linux-3.3.8 ] ~ [ linux-3.2.102 ] ~ [ linux-3.1.10 ] ~ [ linux-3.0.101 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

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

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp