tree.c 130 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14
/*
 * Read-Copy Update mechanism for mutual exclusion
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
15 16
 * along with this program; if not, you can access it online at
 * http://www.gnu.org/licenses/gpl-2.0.html.
17 18 19 20 21 22 23 24 25 26 27
 *
 * Copyright IBM Corporation, 2008
 *
 * Authors: Dipankar Sarma <dipankar@in.ibm.com>
 *	    Manfred Spraul <manfred@colorfullife.com>
 *	    Paul E. McKenney <paulmck@linux.vnet.ibm.com> Hierarchical version
 *
 * Based on the original work by Paul McKenney <paulmck@us.ibm.com>
 * and inputs from Rusty Russell, Andrea Arcangeli and Andi Kleen.
 *
 * For detailed explanation of Read-Copy Update mechanism see -
28
 *	Documentation/RCU
29 30 31 32 33 34 35 36 37
 */
#include <linux/types.h>
#include <linux/kernel.h>
#include <linux/init.h>
#include <linux/spinlock.h>
#include <linux/smp.h>
#include <linux/rcupdate.h>
#include <linux/interrupt.h>
#include <linux/sched.h>
38
#include <linux/nmi.h>
39
#include <linux/atomic.h>
40
#include <linux/bitops.h>
41
#include <linux/export.h>
42 43 44 45 46 47 48
#include <linux/completion.h>
#include <linux/moduleparam.h>
#include <linux/percpu.h>
#include <linux/notifier.h>
#include <linux/cpu.h>
#include <linux/mutex.h>
#include <linux/time.h>
49
#include <linux/kernel_stat.h>
50 51
#include <linux/wait.h>
#include <linux/kthread.h>
52
#include <linux/prefetch.h>
53 54
#include <linux/delay.h>
#include <linux/stop_machine.h>
55
#include <linux/random.h>
56
#include <linux/trace_events.h>
57
#include <linux/suspend.h>
58

59
#include "tree.h"
60
#include "rcu.h"
61

62 63 64 65 66
#ifdef MODULE_PARAM_PREFIX
#undef MODULE_PARAM_PREFIX
#endif
#define MODULE_PARAM_PREFIX "rcutree."

67 68
/* Data structures. */

69 70 71 72 73 74 75 76
/*
 * In order to export the rcu_state name to the tracing tools, it
 * needs to be added in the __tracepoint_string section.
 * This requires defining a separate variable tp_<sname>_varname
 * that points to the string being used, and this will allow
 * the tracing userspace tools to be able to decipher the string
 * address to the matching string.
 */
77 78
#ifdef CONFIG_TRACING
# define DEFINE_RCU_TPS(sname) \
79
static char sname##_varname[] = #sname; \
80 81 82 83 84 85 86 87 88
static const char *tp_##sname##_varname __used __tracepoint_string = sname##_varname;
# define RCU_STATE_NAME(sname) sname##_varname
#else
# define DEFINE_RCU_TPS(sname)
# define RCU_STATE_NAME(sname) __stringify(sname)
#endif

#define RCU_STATE_INITIALIZER(sname, sabbr, cr) \
DEFINE_RCU_TPS(sname) \
89
static DEFINE_PER_CPU_SHARED_ALIGNED(struct rcu_data, sname##_data); \
90
struct rcu_state sname##_state = { \
91
	.level = { &sname##_state.node[0] }, \
92
	.rda = &sname##_data, \
93
	.call = cr, \
94
	.gp_state = RCU_GP_IDLE, \
Paul E. McKenney's avatar
Paul E. McKenney committed
95 96
	.gpnum = 0UL - 300UL, \
	.completed = 0UL - 300UL, \
97
	.orphan_lock = __RAW_SPIN_LOCK_UNLOCKED(&sname##_state.orphan_lock), \
98 99
	.orphan_nxttail = &sname##_state.orphan_nxtlist, \
	.orphan_donetail = &sname##_state.orphan_donelist, \
100
	.barrier_mutex = __MUTEX_INITIALIZER(sname##_state.barrier_mutex), \
101
	.name = RCU_STATE_NAME(sname), \
102
	.abbr = sabbr, \
103
	.exp_mutex = __MUTEX_INITIALIZER(sname##_state.exp_mutex), \
104
	.exp_wake_mutex = __MUTEX_INITIALIZER(sname##_state.exp_wake_mutex), \
105
}
106

107 108
RCU_STATE_INITIALIZER(rcu_sched, 's', call_rcu_sched);
RCU_STATE_INITIALIZER(rcu_bh, 'b', call_rcu_bh);
109

110
static struct rcu_state *const rcu_state_p;
111
LIST_HEAD(rcu_struct_flavors);
112

113 114 115
/* Dump rcu_node combining tree at boot to verify correct setup. */
static bool dump_tree;
module_param(dump_tree, bool, 0444);
116 117 118
/* Control rcu_node-tree auto-balancing at boot time. */
static bool rcu_fanout_exact;
module_param(rcu_fanout_exact, bool, 0444);
119 120
/* Increase (but not decrease) the RCU_FANOUT_LEAF at boot time. */
static int rcu_fanout_leaf = RCU_FANOUT_LEAF;
121
module_param(rcu_fanout_leaf, int, 0444);
122
int rcu_num_lvls __read_mostly = RCU_NUM_LVLS;
123 124
/* Number of rcu_nodes at specified level. */
static int num_rcu_lvl[] = NUM_RCU_LVL_INIT;
125
int rcu_num_nodes __read_mostly = NUM_RCU_NODES; /* Total # rcu_nodes in use. */
126 127
/* panic() on RCU Stall sysctl. */
int sysctl_panic_on_rcu_stall __read_mostly;
128

129 130 131 132
/*
 * The rcu_scheduler_active variable transitions from zero to one just
 * before the first task is spawned.  So when this variable is zero, RCU
 * can assume that there is but one task, allowing RCU to (for example)
133
 * optimize synchronize_rcu() to a simple barrier().  When this variable
134 135 136 137
 * is one, RCU must actually do all the hard work required to detect real
 * grace periods.  This variable is also used to suppress boot-time false
 * positives from lockdep-RCU error checking.
 */
138 139 140
int rcu_scheduler_active __read_mostly;
EXPORT_SYMBOL_GPL(rcu_scheduler_active);

141 142 143 144 145 146 147 148 149 150 151 152 153 154
/*
 * The rcu_scheduler_fully_active variable transitions from zero to one
 * during the early_initcall() processing, which is after the scheduler
 * is capable of creating new tasks.  So RCU processing (for example,
 * creating tasks for RCU priority boosting) must be delayed until after
 * rcu_scheduler_fully_active transitions from zero to one.  We also
 * currently delay invocation of any RCU callbacks until after this point.
 *
 * It might later prove better for people registering RCU callbacks during
 * early boot to take responsibility for these callbacks, but one step at
 * a time.
 */
static int rcu_scheduler_fully_active __read_mostly;

155 156
static void rcu_init_new_rnp(struct rcu_node *rnp_leaf);
static void rcu_cleanup_dead_rnp(struct rcu_node *rnp_leaf);
Thomas Gleixner's avatar
Thomas Gleixner committed
157
static void rcu_boost_kthread_setaffinity(struct rcu_node *rnp, int outgoingcpu);
158 159
static void invoke_rcu_core(void);
static void invoke_rcu_callbacks(struct rcu_state *rsp, struct rcu_data *rdp);
160 161
static void rcu_report_exp_rdp(struct rcu_state *rsp,
			       struct rcu_data *rdp, bool wake);
162
static void sync_sched_exp_online_cleanup(int cpu);
163

164
/* rcuc/rcub kthread realtime priority */
165
#ifdef CONFIG_RCU_KTHREAD_PRIO
166
static int kthread_prio = CONFIG_RCU_KTHREAD_PRIO;
167 168 169
#else /* #ifdef CONFIG_RCU_KTHREAD_PRIO */
static int kthread_prio = IS_ENABLED(CONFIG_RCU_BOOST) ? 1 : 0;
#endif /* #else #ifdef CONFIG_RCU_KTHREAD_PRIO */
170 171
module_param(kthread_prio, int, 0644);

172
/* Delay in jiffies for grace-period initialization delays, debug only. */
173 174 175 176 177 178 179 180

#ifdef CONFIG_RCU_TORTURE_TEST_SLOW_PREINIT
static int gp_preinit_delay = CONFIG_RCU_TORTURE_TEST_SLOW_PREINIT_DELAY;
module_param(gp_preinit_delay, int, 0644);
#else /* #ifdef CONFIG_RCU_TORTURE_TEST_SLOW_PREINIT */
static const int gp_preinit_delay;
#endif /* #else #ifdef CONFIG_RCU_TORTURE_TEST_SLOW_PREINIT */

181 182
#ifdef CONFIG_RCU_TORTURE_TEST_SLOW_INIT
static int gp_init_delay = CONFIG_RCU_TORTURE_TEST_SLOW_INIT_DELAY;
183
module_param(gp_init_delay, int, 0644);
184 185 186
#else /* #ifdef CONFIG_RCU_TORTURE_TEST_SLOW_INIT */
static const int gp_init_delay;
#endif /* #else #ifdef CONFIG_RCU_TORTURE_TEST_SLOW_INIT */
187

188 189 190 191 192 193 194
#ifdef CONFIG_RCU_TORTURE_TEST_SLOW_CLEANUP
static int gp_cleanup_delay = CONFIG_RCU_TORTURE_TEST_SLOW_CLEANUP_DELAY;
module_param(gp_cleanup_delay, int, 0644);
#else /* #ifdef CONFIG_RCU_TORTURE_TEST_SLOW_CLEANUP */
static const int gp_cleanup_delay;
#endif /* #else #ifdef CONFIG_RCU_TORTURE_TEST_SLOW_CLEANUP */

195 196 197 198 199 200 201 202 203 204
/*
 * Number of grace periods between delays, normalized by the duration of
 * the delay.  The longer the the delay, the more the grace periods between
 * each delay.  The reason for this normalization is that it means that,
 * for non-zero delays, the overall slowdown of grace periods is constant
 * regardless of the duration of the delay.  This arrangement balances
 * the need for long delays to increase some race probabilities with the
 * need for fast grace periods to increase other race probabilities.
 */
#define PER_RCU_NODE_PERIOD 3	/* Number of grace periods between delays. */
205

206 207 208 209 210 211 212 213 214 215 216 217
/*
 * Track the rcutorture test sequence number and the update version
 * number within a given test.  The rcutorture_testseq is incremented
 * on every rcutorture module load and unload, so has an odd value
 * when a test is running.  The rcutorture_vernum is set to zero
 * when rcutorture starts and is incremented on each rcutorture update.
 * These variables enable correlating rcutorture output with the
 * RCU tracing information.
 */
unsigned long rcutorture_testseq;
unsigned long rcutorture_vernum;

218 219 220 221 222 223 224 225
/*
 * Compute the mask of online CPUs for the specified rcu_node structure.
 * This will not be stable unless the rcu_node structure's ->lock is
 * held, but the bit corresponding to the current CPU will be stable
 * in most contexts.
 */
unsigned long rcu_rnp_online_cpus(struct rcu_node *rnp)
{
226
	return READ_ONCE(rnp->qsmaskinitnext);
227 228
}

229
/*
230
 * Return true if an RCU grace period is in progress.  The READ_ONCE()s
231 232 233 234 235
 * permit this function to be invoked without holding the root rcu_node
 * structure's ->lock, but of course results can be subject to change.
 */
static int rcu_gp_in_progress(struct rcu_state *rsp)
{
236
	return READ_ONCE(rsp->completed) != READ_ONCE(rsp->gpnum);
237 238
}

239
/*
240
 * Note a quiescent state.  Because we do not need to know
241
 * how many quiescent states passed, just if there was at least
242
 * one since the start of the grace period, this just sets a flag.
243
 * The caller must have disabled preemption.
244
 */
245
void rcu_sched_qs(void)
246
{
247 248 249 250 251 252 253 254
	if (!__this_cpu_read(rcu_sched_data.cpu_no_qs.s))
		return;
	trace_rcu_grace_period(TPS("rcu_sched"),
			       __this_cpu_read(rcu_sched_data.gpnum),
			       TPS("cpuqs"));
	__this_cpu_write(rcu_sched_data.cpu_no_qs.b.norm, false);
	if (!__this_cpu_read(rcu_sched_data.cpu_no_qs.b.exp))
		return;
255 256 257
	__this_cpu_write(rcu_sched_data.cpu_no_qs.b.exp, false);
	rcu_report_exp_rdp(&rcu_sched_state,
			   this_cpu_ptr(&rcu_sched_data), true);
258 259
}

260
void rcu_bh_qs(void)
261
{
262
	if (__this_cpu_read(rcu_bh_data.cpu_no_qs.s)) {
263 264 265
		trace_rcu_grace_period(TPS("rcu_bh"),
				       __this_cpu_read(rcu_bh_data.gpnum),
				       TPS("cpuqs"));
266
		__this_cpu_write(rcu_bh_data.cpu_no_qs.b.norm, false);
267
	}
268
}
269

270 271 272 273 274 275 276 277 278 279 280
static DEFINE_PER_CPU(int, rcu_sched_qs_mask);

static DEFINE_PER_CPU(struct rcu_dynticks, rcu_dynticks) = {
	.dynticks_nesting = DYNTICK_TASK_EXIT_IDLE,
	.dynticks = ATOMIC_INIT(1),
#ifdef CONFIG_NO_HZ_FULL_SYSIDLE
	.dynticks_idle_nesting = DYNTICK_TASK_NEST_VALUE,
	.dynticks_idle = ATOMIC_INIT(1),
#endif /* #ifdef CONFIG_NO_HZ_FULL_SYSIDLE */
};

281 282 283
DEFINE_PER_CPU_SHARED_ALIGNED(unsigned long, rcu_qs_ctr);
EXPORT_PER_CPU_SYMBOL_GPL(rcu_qs_ctr);

284 285 286 287 288 289 290 291 292 293
/*
 * Let the RCU core know that this CPU has gone through the scheduler,
 * which is a quiescent state.  This is called when the need for a
 * quiescent state is urgent, so we burn an atomic operation and full
 * memory barriers to let the RCU core know about it, regardless of what
 * this CPU might (or might not) do in the near future.
 *
 * We inform the RCU core by emulating a zero-duration dyntick-idle
 * period, which we in turn do by incrementing the ->dynticks counter
 * by two.
294 295
 *
 * The caller must have disabled interrupts.
296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316
 */
static void rcu_momentary_dyntick_idle(void)
{
	struct rcu_data *rdp;
	struct rcu_dynticks *rdtp;
	int resched_mask;
	struct rcu_state *rsp;

	/*
	 * Yes, we can lose flag-setting operations.  This is OK, because
	 * the flag will be set again after some delay.
	 */
	resched_mask = raw_cpu_read(rcu_sched_qs_mask);
	raw_cpu_write(rcu_sched_qs_mask, 0);

	/* Find the flavor that needs a quiescent state. */
	for_each_rcu_flavor(rsp) {
		rdp = raw_cpu_ptr(rsp->rda);
		if (!(resched_mask & rsp->flavor_mask))
			continue;
		smp_mb(); /* rcu_sched_qs_mask before cond_resched_completed. */
317 318
		if (READ_ONCE(rdp->mynode->completed) !=
		    READ_ONCE(rdp->cond_resched_completed))
319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334
			continue;

		/*
		 * Pretend to be momentarily idle for the quiescent state.
		 * This allows the grace-period kthread to record the
		 * quiescent state, with no need for this CPU to do anything
		 * further.
		 */
		rdtp = this_cpu_ptr(&rcu_dynticks);
		smp_mb__before_atomic(); /* Earlier stuff before QS. */
		atomic_add(2, &rdtp->dynticks);  /* QS. */
		smp_mb__after_atomic(); /* Later stuff after QS. */
		break;
	}
}

335 336 337
/*
 * Note a context switch.  This is a quiescent state for RCU-sched,
 * and requires special handling for preemptible RCU.
338
 * The caller must have disabled interrupts.
339
 */
340
void rcu_note_context_switch(void)
341
{
342
	barrier(); /* Avoid RCU read-side critical sections leaking down. */
343
	trace_rcu_utilization(TPS("Start context switch"));
344
	rcu_sched_qs();
345
	rcu_preempt_note_context_switch();
346 347
	if (unlikely(raw_cpu_read(rcu_sched_qs_mask)))
		rcu_momentary_dyntick_idle();
348
	trace_rcu_utilization(TPS("End context switch"));
349
	barrier(); /* Avoid RCU read-side critical sections leaking up. */
350
}
351
EXPORT_SYMBOL_GPL(rcu_note_context_switch);
352

353
/*
354
 * Register a quiescent state for all RCU flavors.  If there is an
355 356
 * emergency, invoke rcu_momentary_dyntick_idle() to do a heavy-weight
 * dyntick-idle quiescent state visible to other CPUs (but only for those
357
 * RCU flavors in desperate need of a quiescent state, which will normally
358 359
 * be none of them).  Either way, do a lightweight quiescent state for
 * all RCU flavors.
360 361 362 363 364
 *
 * The barrier() calls are redundant in the common case when this is
 * called externally, but just in case this is called from within this
 * file.
 *
365 366 367
 */
void rcu_all_qs(void)
{
368 369
	unsigned long flags;

370
	barrier(); /* Avoid RCU read-side critical sections leaking down. */
371 372
	if (unlikely(raw_cpu_read(rcu_sched_qs_mask))) {
		local_irq_save(flags);
373
		rcu_momentary_dyntick_idle();
374 375
		local_irq_restore(flags);
	}
376 377 378 379 380 381 382 383 384 385 386 387 388 389 390
	if (unlikely(raw_cpu_read(rcu_sched_data.cpu_no_qs.b.exp))) {
		/*
		 * Yes, we just checked a per-CPU variable with preemption
		 * enabled, so we might be migrated to some other CPU at
		 * this point.  That is OK because in that case, the
		 * migration will supply the needed quiescent state.
		 * We might end up needlessly disabling preemption and
		 * invoking rcu_sched_qs() on the destination CPU, but
		 * the probability and cost are both quite low, so this
		 * should not be a problem in practice.
		 */
		preempt_disable();
		rcu_sched_qs();
		preempt_enable();
	}
391
	this_cpu_inc(rcu_qs_ctr);
392
	barrier(); /* Avoid RCU read-side critical sections leaking up. */
393 394 395
}
EXPORT_SYMBOL_GPL(rcu_all_qs);

396 397 398
static long blimit = 10;	/* Maximum callbacks per rcu_do_batch. */
static long qhimark = 10000;	/* If this many pending, ignore blimit. */
static long qlowmark = 100;	/* Once only this many pending, use blimit. */
399

400 401 402
module_param(blimit, long, 0444);
module_param(qhimark, long, 0444);
module_param(qlowmark, long, 0444);
403

404 405
static ulong jiffies_till_first_fqs = ULONG_MAX;
static ulong jiffies_till_next_fqs = ULONG_MAX;
406
static bool rcu_kick_kthreads;
407 408 409

module_param(jiffies_till_first_fqs, ulong, 0644);
module_param(jiffies_till_next_fqs, ulong, 0644);
410
module_param(rcu_kick_kthreads, bool, 0644);
411

412 413 414 415 416 417 418
/*
 * How long the grace period must be before we start recruiting
 * quiescent-state help from rcu_note_context_switch().
 */
static ulong jiffies_till_sched_qs = HZ / 20;
module_param(jiffies_till_sched_qs, ulong, 0644);

419
static bool rcu_start_gp_advanced(struct rcu_state *rsp, struct rcu_node *rnp,
420
				  struct rcu_data *rdp);
421 422 423 424
static void force_qs_rnp(struct rcu_state *rsp,
			 int (*f)(struct rcu_data *rsp, bool *isidle,
				  unsigned long *maxj),
			 bool *isidle, unsigned long *maxj);
425
static void force_quiescent_state(struct rcu_state *rsp);
426
static int rcu_pending(void);
427 428

/*
429
 * Return the number of RCU batches started thus far for debug & stats.
430
 */
431 432 433 434 435 436 437 438
unsigned long rcu_batches_started(void)
{
	return rcu_state_p->gpnum;
}
EXPORT_SYMBOL_GPL(rcu_batches_started);

/*
 * Return the number of RCU-sched batches started thus far for debug & stats.
439
 */
440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465
unsigned long rcu_batches_started_sched(void)
{
	return rcu_sched_state.gpnum;
}
EXPORT_SYMBOL_GPL(rcu_batches_started_sched);

/*
 * Return the number of RCU BH batches started thus far for debug & stats.
 */
unsigned long rcu_batches_started_bh(void)
{
	return rcu_bh_state.gpnum;
}
EXPORT_SYMBOL_GPL(rcu_batches_started_bh);

/*
 * Return the number of RCU batches completed thus far for debug & stats.
 */
unsigned long rcu_batches_completed(void)
{
	return rcu_state_p->completed;
}
EXPORT_SYMBOL_GPL(rcu_batches_completed);

/*
 * Return the number of RCU-sched batches completed thus far for debug & stats.
466
 */
467
unsigned long rcu_batches_completed_sched(void)
468
{
469
	return rcu_sched_state.completed;
470
}
471
EXPORT_SYMBOL_GPL(rcu_batches_completed_sched);
472 473

/*
474
 * Return the number of RCU BH batches completed thus far for debug & stats.
475
 */
476
unsigned long rcu_batches_completed_bh(void)
477 478 479 480 481
{
	return rcu_bh_state.completed;
}
EXPORT_SYMBOL_GPL(rcu_batches_completed_bh);

482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503
/*
 * Return the number of RCU expedited batches completed thus far for
 * debug & stats.  Odd numbers mean that a batch is in progress, even
 * numbers mean idle.  The value returned will thus be roughly double
 * the cumulative batches since boot.
 */
unsigned long rcu_exp_batches_completed(void)
{
	return rcu_state_p->expedited_sequence;
}
EXPORT_SYMBOL_GPL(rcu_exp_batches_completed);

/*
 * Return the number of RCU-sched expedited batches completed thus far
 * for debug & stats.  Similar to rcu_exp_batches_completed().
 */
unsigned long rcu_exp_batches_completed_sched(void)
{
	return rcu_sched_state.expedited_sequence;
}
EXPORT_SYMBOL_GPL(rcu_exp_batches_completed_sched);

504 505 506 507 508
/*
 * Force a quiescent state.
 */
void rcu_force_quiescent_state(void)
{
509
	force_quiescent_state(rcu_state_p);
510 511 512
}
EXPORT_SYMBOL_GPL(rcu_force_quiescent_state);

513 514 515 516 517
/*
 * Force a quiescent state for RCU BH.
 */
void rcu_bh_force_quiescent_state(void)
{
518
	force_quiescent_state(&rcu_bh_state);
519 520 521
}
EXPORT_SYMBOL_GPL(rcu_bh_force_quiescent_state);

522 523 524 525 526 527 528 529 530
/*
 * Force a quiescent state for RCU-sched.
 */
void rcu_sched_force_quiescent_state(void)
{
	force_quiescent_state(&rcu_sched_state);
}
EXPORT_SYMBOL_GPL(rcu_sched_force_quiescent_state);

531 532 533 534 535 536 537 538 539 540 541 542 543 544 545
/*
 * Show the state of the grace-period kthreads.
 */
void show_rcu_gp_kthreads(void)
{
	struct rcu_state *rsp;

	for_each_rcu_flavor(rsp) {
		pr_info("%s: wait state: %d ->state: %#lx\n",
			rsp->name, rsp->gp_state, rsp->gp_kthread->state);
		/* sched_show_task(rsp->gp_kthread); */
	}
}
EXPORT_SYMBOL_GPL(show_rcu_gp_kthreads);

546 547 548 549 550 551 552 553 554 555 556 557 558 559
/*
 * Record the number of times rcutorture tests have been initiated and
 * terminated.  This information allows the debugfs tracing stats to be
 * correlated to the rcutorture messages, even when the rcutorture module
 * is being repeatedly loaded and unloaded.  In other words, we cannot
 * store this state in rcutorture itself.
 */
void rcutorture_record_test_transition(void)
{
	rcutorture_testseq++;
	rcutorture_vernum = 0;
}
EXPORT_SYMBOL_GPL(rcutorture_record_test_transition);

560 561 562 563 564 565 566 567 568 569
/*
 * Send along grace-period-related data for rcutorture diagnostics.
 */
void rcutorture_get_gp_data(enum rcutorture_type test_type, int *flags,
			    unsigned long *gpnum, unsigned long *completed)
{
	struct rcu_state *rsp = NULL;

	switch (test_type) {
	case RCU_FLAVOR:
570
		rsp = rcu_state_p;
571 572 573 574 575 576 577 578 579 580 581
		break;
	case RCU_BH_FLAVOR:
		rsp = &rcu_bh_state;
		break;
	case RCU_SCHED_FLAVOR:
		rsp = &rcu_sched_state;
		break;
	default:
		break;
	}
	if (rsp != NULL) {
582 583 584
		*flags = READ_ONCE(rsp->gp_flags);
		*gpnum = READ_ONCE(rsp->gpnum);
		*completed = READ_ONCE(rsp->completed);
585 586 587 588 589 590 591 592
		return;
	}
	*flags = 0;
	*gpnum = 0;
	*completed = 0;
}
EXPORT_SYMBOL_GPL(rcutorture_get_gp_data);

593 594 595 596 597 598 599 600 601 602 603
/*
 * Record the number of writer passes through the current rcutorture test.
 * This is also used to correlate debugfs tracing stats with the rcutorture
 * messages.
 */
void rcutorture_record_progress(unsigned long vernum)
{
	rcutorture_vernum++;
}
EXPORT_SYMBOL_GPL(rcutorture_record_progress);

604 605 606 607 608 609
/*
 * Does the CPU have callbacks ready to be invoked?
 */
static int
cpu_has_callbacks_ready_to_invoke(struct rcu_data *rdp)
{
Paul E. McKenney's avatar
Paul E. McKenney committed
610 611
	return &rdp->nxtlist != rdp->nxttail[RCU_DONE_TAIL] &&
	       rdp->nxttail[RCU_DONE_TAIL] != NULL;
612 613
}

614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629
/*
 * Return the root node of the specified rcu_state structure.
 */
static struct rcu_node *rcu_get_root(struct rcu_state *rsp)
{
	return &rsp->node[0];
}

/*
 * Is there any need for future grace periods?
 * Interrupts must be disabled.  If the caller does not hold the root
 * rnp_node structure's ->lock, the results are advisory only.
 */
static int rcu_future_needs_gp(struct rcu_state *rsp)
{
	struct rcu_node *rnp = rcu_get_root(rsp);
630
	int idx = (READ_ONCE(rnp->completed) + 1) & 0x1;
631 632
	int *fp = &rnp->need_future_gp[idx];

633
	return READ_ONCE(*fp);
634 635
}

636
/*
637 638 639
 * Does the current CPU require a not-yet-started grace period?
 * The caller must have disabled interrupts to prevent races with
 * normal callback registry.
640
 */
641
static bool
642 643
cpu_needs_another_gp(struct rcu_state *rsp, struct rcu_data *rdp)
{
644
	int i;
Paul E. McKenney's avatar
Paul E. McKenney committed
645

646
	if (rcu_gp_in_progress(rsp))
647
		return false;  /* No, a grace period is already in progress. */
648
	if (rcu_future_needs_gp(rsp))
649
		return true;  /* Yes, a no-CBs CPU needs one. */
650
	if (!rdp->nxttail[RCU_NEXT_TAIL])
651
		return false;  /* No, this is a no-CBs (or offline) CPU. */
652
	if (*rdp->nxttail[RCU_NEXT_READY_TAIL])
653
		return true;  /* Yes, CPU has newly registered callbacks. */
654 655
	for (i = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++)
		if (rdp->nxttail[i - 1] != rdp->nxttail[i] &&
656
		    ULONG_CMP_LT(READ_ONCE(rsp->completed),
657
				 rdp->nxtcompleted[i]))
658 659
			return true;  /* Yes, CBs for future grace period. */
	return false; /* No grace period needed. */
660 661
}

662
/*
663
 * rcu_eqs_enter_common - current CPU is moving towards extended quiescent state
664 665 666 667 668
 *
 * If the new value of the ->dynticks_nesting counter now is zero,
 * we really have entered idle, and must do the appropriate accounting.
 * The caller must have disabled interrupts.
 */
669
static void rcu_eqs_enter_common(long long oldval, bool user)
670
{
671 672
	struct rcu_state *rsp;
	struct rcu_data *rdp;
673
	struct rcu_dynticks *rdtp = this_cpu_ptr(&rcu_dynticks);
674

675
	trace_rcu_dyntick(TPS("Start"), oldval, rdtp->dynticks_nesting);
676 677
	if (IS_ENABLED(CONFIG_RCU_EQS_DEBUG) &&
	    !user && !is_idle_task(current)) {
678 679
		struct task_struct *idle __maybe_unused =
			idle_task(smp_processor_id());
680

681
		trace_rcu_dyntick(TPS("Error on entry: not idle task"), oldval, 0);
682
		rcu_ftrace_dump(DUMP_ORIG);
683 684 685
		WARN_ONCE(1, "Current pid: %d comm: %s / Idle pid: %d comm: %s",
			  current->pid, current->comm,
			  idle->pid, idle->comm); /* must be idle task! */
686
	}
687 688 689 690
	for_each_rcu_flavor(rsp) {
		rdp = this_cpu_ptr(rsp->rda);
		do_nocb_deferred_wakeup(rdp);
	}
691
	rcu_prepare_for_idle();
692
	/* CPUs seeing atomic_inc() must see prior RCU read-side crit sects */
693
	smp_mb__before_atomic();  /* See above. */
694
	atomic_inc(&rdtp->dynticks);
695
	smp_mb__after_atomic();  /* Force ordering with next sojourn. */
696 697
	WARN_ON_ONCE(IS_ENABLED(CONFIG_RCU_EQS_DEBUG) &&
		     atomic_read(&rdtp->dynticks) & 0x1);
698
	rcu_dynticks_task_enter();
699 700

	/*
701
	 * It is illegal to enter an extended quiescent state while
702 703
	 * in an RCU read-side critical section.
	 */
704 705 706 707 708 709
	RCU_LOCKDEP_WARN(lock_is_held(&rcu_lock_map),
			 "Illegal idle entry in RCU read-side critical section.");
	RCU_LOCKDEP_WARN(lock_is_held(&rcu_bh_lock_map),
			 "Illegal idle entry in RCU-bh read-side critical section.");
	RCU_LOCKDEP_WARN(lock_is_held(&rcu_sched_lock_map),
			 "Illegal idle entry in RCU-sched read-side critical section.");
710
}
711

712 713 714
/*
 * Enter an RCU extended quiescent state, which can be either the
 * idle loop or adaptive-tickless usermode execution.
715
 */
716
static void rcu_eqs_enter(bool user)
717
{
718
	long long oldval;
719 720
	struct rcu_dynticks *rdtp;

721
	rdtp = this_cpu_ptr(&rcu_dynticks);
722
	oldval = rdtp->dynticks_nesting;
723 724
	WARN_ON_ONCE(IS_ENABLED(CONFIG_RCU_EQS_DEBUG) &&
		     (oldval & DYNTICK_TASK_NEST_MASK) == 0);
725
	if ((oldval & DYNTICK_TASK_NEST_MASK) == DYNTICK_TASK_NEST_VALUE) {
726
		rdtp->dynticks_nesting = 0;
727
		rcu_eqs_enter_common(oldval, user);
728
	} else {
729
		rdtp->dynticks_nesting -= DYNTICK_TASK_NEST_VALUE;
730
	}
731
}
732 733 734 735 736 737 738 739 740 741 742 743 744 745 746

/**
 * rcu_idle_enter - inform RCU that current CPU is entering idle
 *
 * Enter idle mode, in other words, -leave- the mode in which RCU
 * read-side critical sections can occur.  (Though RCU read-side
 * critical sections can occur in irq handlers in idle, a possibility
 * handled by irq_enter() and irq_exit().)
 *
 * We crowbar the ->dynticks_nesting field to zero to allow for
 * the possibility of usermode upcalls having messed up our count
 * of interrupt nesting level during the prior busy period.
 */
void rcu_idle_enter(void)
{
747 748 749
	unsigned long flags;

	local_irq_save(flags);
750
	rcu_eqs_enter(false);
751
	rcu_sysidle_enter(0);
752
	local_irq_restore(flags);
753
}
754
EXPORT_SYMBOL_GPL(rcu_idle_enter);
755

756
#ifdef CONFIG_NO_HZ_FULL
757 758 759 760 761 762 763 764 765 766
/**
 * rcu_user_enter - inform RCU that we are resuming userspace.
 *
 * Enter RCU idle mode right before resuming userspace.  No use of RCU
 * is permitted between this call and rcu_user_exit(). This way the
 * CPU doesn't need to maintain the tick for RCU maintenance purposes
 * when the CPU runs in userspace.
 */
void rcu_user_enter(void)
{
767
	rcu_eqs_enter(1);
768
}
769
#endif /* CONFIG_NO_HZ_FULL */
770

771 772 773 774 775
/**
 * rcu_irq_exit - inform RCU that current CPU is exiting irq towards idle
 *
 * Exit from an interrupt handler, which might possibly result in entering
 * idle mode, in other words, leaving the mode in which read-side critical
776
 * sections can occur.  The caller must have disabled interrupts.
777
 *
778 779 780 781 782 783 784 785
 * This code assumes that the idle loop never does anything that might
 * result in unbalanced calls to irq_enter() and irq_exit().  If your
 * architecture violates this assumption, RCU will give you what you
 * deserve, good and hard.  But very infrequently and irreproducibly.
 *
 * Use things like work queues to work around this limitation.
 *
 * You have been warned.
786
 */
787
void rcu_irq_exit(void)
788
{
789
	long long oldval;
790 791
	struct rcu_dynticks *rdtp;

792
	RCU_LOCKDEP_WARN(!irqs_disabled(), "rcu_irq_exit() invoked with irqs enabled!!!");
793
	rdtp = this_cpu_ptr(&rcu_dynticks);
794
	oldval = rdtp->dynticks_nesting;
795
	rdtp->dynticks_nesting--;
796 797
	WARN_ON_ONCE(IS_ENABLED(CONFIG_RCU_EQS_DEBUG) &&
		     rdtp->dynticks_nesting < 0);
798
	if (rdtp->dynticks_nesting)
799
		trace_rcu_dyntick(TPS("--="), oldval, rdtp->dynticks_nesting);
800
	else
801 802
		rcu_eqs_enter_common(oldval, true);
	rcu_sysidle_enter(1);
803 804 805 806 807 808 809 810 811 812 813
}

/*
 * Wrapper for rcu_irq_exit() where interrupts are enabled.
 */
void rcu_irq_exit_irqson(void)
{
	unsigned long flags;

	local_irq_save(flags);
	rcu_irq_exit();
814 815 816 817
	local_irq_restore(flags);
}

/*
818
 * rcu_eqs_exit_common - current CPU moving away from extended quiescent state
819 820 821 822 823
 *
 * If the new value of the ->dynticks_nesting counter was previously zero,
 * we really have exited idle, and must do the appropriate accounting.
 * The caller must have disabled interrupts.
 */
824
static void rcu_eqs_exit_common(long long oldval, int user)
825
{
826 827
	struct rcu_dynticks *rdtp = this_cpu_ptr(&rcu_dynticks);

828
	rcu_dynticks_task_exit();
829
	smp_mb__before_atomic();  /* Force ordering w/previous sojourn. */
830 831
	atomic_inc(&rdtp->dynticks);
	/* CPUs seeing atomic_inc() must see later RCU read-side crit sects */
832
	smp_mb__after_atomic();  /* See above. */
833 834
	WARN_ON_ONCE(IS_ENABLED(CONFIG_RCU_EQS_DEBUG) &&
		     !(atomic_read(&rdtp->dynticks) & 0x1));
835
	rcu_cleanup_after_idle();
836
	trace_rcu_dyntick(TPS("End"), oldval, rdtp->dynticks_nesting);
837 838
	if (IS_ENABLED(CONFIG_RCU_EQS_DEBUG) &&
	    !user && !is_idle_task(current)) {
839 840
		struct task_struct *idle __maybe_unused =
			idle_task(smp_processor_id());
841

842
		trace_rcu_dyntick(TPS("Error on exit: not idle task"),
843
				  oldval, rdtp->dynticks_nesting);
844
		rcu_ftrace_dump(DUMP_ORIG);
845 846 847
		WARN_ONCE(1, "Current pid: %d comm: %s / Idle pid: %d comm: %s",
			  current->pid, current->comm,
			  idle->pid, idle->comm); /* must be idle task! */
848 849 850
	}
}

851 852 853
/*
 * Exit an RCU extended quiescent state, which can be either the
 * idle loop or adaptive-tickless usermode execution.
854
 */
855
static void rcu_eqs_exit(bool user)
856 857 858 859
{
	struct rcu_dynticks *rdtp;
	long long oldval;

860
	rdtp = this_cpu_ptr(&rcu_dynticks);
861
	oldval = rdtp->dynticks_nesting;
862
	WARN_ON_ONCE(IS_ENABLED(CONFIG_RCU_EQS_DEBUG) && oldval < 0);
863
	if (oldval & DYNTICK_TASK_NEST_MASK) {
864
		rdtp->dynticks_nesting += DYNTICK_TASK_NEST_VALUE;
865
	} else {
866
		rdtp->dynticks_nesting = DYNTICK_TASK_EXIT_IDLE;
867
		rcu_eqs_exit_common(oldval, user);
868
	}
869
}
870 871 872 873 874 875 876 877 878 879 880 881 882 883

/**
 * rcu_idle_exit - inform RCU that current CPU is leaving idle
 *
 * Exit idle mode, in other words, -enter- the mode in which RCU
 * read-side critical sections can occur.
 *
 * We crowbar the ->dynticks_nesting field to DYNTICK_TASK_NEST to
 * allow for the possibility of usermode upcalls messing up our count
 * of interrupt nesting level during the busy period that is just
 * now starting.
 */
void rcu_idle_exit(void)
{
884 885 886
	unsigned long flags;

	local_irq_save(flags);
887
	rcu_eqs_exit(false);
888
	rcu_sysidle_exit(0);
889
	local_irq_restore(flags);
890
}
891
EXPORT_SYMBOL_GPL(rcu_idle_exit);
892

893
#ifdef CONFIG_NO_HZ_FULL
894 895 896 897 898 899 900 901
/**
 * rcu_user_exit - inform RCU that we are exiting userspace.
 *
 * Exit RCU idle mode while entering the kernel because it can
 * run a RCU read side critical section anytime.
 */
void rcu_user_exit(void)
{
902
	rcu_eqs_exit(1);
903
}
904
#endif /* CONFIG_NO_HZ_FULL */
905

906 907 908 909 910
/**
 * rcu_irq_enter - inform RCU that current CPU is entering irq away from idle
 *
 * Enter an interrupt handler, which might possibly result in exiting
 * idle mode, in other words, entering the mode in which read-side critical
911
 * sections can occur.  The caller must have disabled interrupts.
912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929
 *
 * Note that the Linux kernel is fully capable of entering an interrupt
 * handler that it never exits, for example when doing upcalls to
 * user mode!  This code assumes that the idle loop never does upcalls to
 * user mode.  If your architecture does do upcalls from the idle loop (or
 * does anything else that results in unbalanced calls to the irq_enter()
 * and irq_exit() functions), RCU will give you what you deserve, good
 * and hard.  But very infrequently and irreproducibly.
 *
 * Use things like work queues to work around this limitation.
 *
 * You have been warned.
 */
void rcu_irq_enter(void)
{
	struct rcu_dynticks *rdtp;
	long long oldval;

930
	RCU_LOCKDEP_WARN(!irqs_disabled(), "rcu_irq_enter() invoked with irqs enabled!!!");
931
	rdtp = this_cpu_ptr(&rcu_dynticks);
932 933
	oldval = rdtp->dynticks_nesting;
	rdtp->dynticks_nesting++;
934 935
	WARN_ON_ONCE(IS_ENABLED(CONFIG_RCU_EQS_DEBUG) &&
		     rdtp->dynticks_nesting == 0);
936
	if (oldval)
937
		trace_rcu_dyntick(TPS("++="), oldval, rdtp->dynticks_nesting);
938
	else
939 940
		rcu_eqs_exit_common(oldval, true);
	rcu_sysidle_exit(1);
941 942 943 944 945 946 947 948 949 950 951
}

/*
 * Wrapper for rcu_irq_enter() where interrupts are enabled.
 */
void rcu_irq_enter_irqson(void)
{
	unsigned long flags;

	local_irq_save(flags);
	rcu_irq_enter();
952 953 954 955 956 957
	local_irq_restore(flags);
}

/**
 * rcu_nmi_enter - inform RCU of entry to NMI context
 *
958 959 960 961 962
 * If the CPU was idle from RCU's viewpoint, update rdtp->dynticks and
 * rdtp->dynticks_nmi_nesting to let the RCU grace-period handling know
 * that the CPU is active.  This implementation permits nested NMIs, as
 * long as the nesting level does not overflow an int.  (You will probably
 * run out of stack space first.)
963 964 965
 */
void rcu_nmi_enter(void)
{
966
	struct rcu_dynticks *rdtp = this_cpu_ptr(&rcu_dynticks);
967
	int incby = 2;
968

969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989
	/* Complain about underflow. */
	WARN_ON_ONCE(rdtp->dynticks_nmi_nesting < 0);

	/*
	 * If idle from RCU viewpoint, atomically increment ->dynticks
	 * to mark non-idle and increment ->dynticks_nmi_nesting by one.
	 * Otherwise, increment ->dynticks_nmi_nesting by two.  This means
	 * if ->dynticks_nmi_nesting is equal to one, we are guaranteed
	 * to be in the outermost NMI handler that interrupted an RCU-idle
	 * period (observation due to Andy Lutomirski).
	 */
	if (!(atomic_read(&rdtp->dynticks) & 0x1)) {
		smp_mb__before_atomic();  /* Force delay from prior write. */
		atomic_inc(&rdtp->dynticks);
		/* atomic_inc() before later RCU read-side crit sects */
		smp_mb__after_atomic();  /* See above. */
		WARN_ON_ONCE(!(atomic_read(&rdtp->dynticks) & 0x1));
		incby = 1;
	}
	rdtp->dynticks_nmi_nesting += incby;
	barrier();
990 991 992 993 994
}

/**
 * rcu_nmi_exit - inform RCU of exit from NMI context
 *
995 996 997 998
 * If we are returning from the outermost NMI handler that interrupted an
 * RCU-idle period, update rdtp->dynticks and rdtp->dynticks_nmi_nesting
 * to let the RCU grace-period handling know that the CPU is back to
 * being RCU-idle.
999 1000 1001
 */
void rcu_nmi_exit(void)
{
1002
	struct rcu_dynticks *rdtp = this_cpu_ptr(&rcu_dynticks);
1003

1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017
	/*
	 * Check for ->dynticks_nmi_nesting underflow and bad ->dynticks.
	 * (We are exiting an NMI handler, so RCU better be paying attention
	 * to us!)
	 */
	WARN_ON_ONCE(rdtp->dynticks_nmi_nesting <= 0);
	WARN_ON_ONCE(!(atomic_read(&rdtp->dynticks) & 0x1));

	/*
	 * If the nesting level is not 1, the CPU wasn't RCU-idle, so
	 * leave it in non-RCU-idle state.
	 */
	if (rdtp->dynticks_nmi_nesting != 1) {
		rdtp->dynticks_nmi_nesting -= 2;
1018
		return;
1019 1020 1021 1022
	}

	/* This NMI interrupted an RCU-idle CPU, restore RCU-idleness. */
	rdtp->dynticks_nmi_nesting = 0;
1023
	/* CPUs seeing atomic_inc() must see prior RCU read-side crit sects */
1024
	smp_mb__before_atomic();  /* See above. */
1025
	atomic_inc(&rdtp->dynticks);
1026
	smp_mb__after_atomic();  /* Force delay to next write. */
1027
	WARN_ON_ONCE(atomic_read(&rdtp->dynticks) & 0x1);
1028 1029 1030
}

/**
1031 1032 1033 1034 1035 1036 1037
 * __rcu_is_watching - are RCU read-side critical sections safe?
 *
 * Return true if RCU is watching the running CPU, which means that
 * this CPU can safely enter RCU read-side critical sections.  Unlike
 * rcu_is_watching(), the caller of __rcu_is_watching() must have at
 * least disabled preemption.
 */
1038
bool notrace __rcu_is_watching(void)
1039 1040 1041 1042 1043 1044
{
	return atomic_read(this_cpu_ptr(&rcu_dynticks.dynticks)) & 0x1;
}

/**
 * rcu_is_watching - see if RCU thinks that the current CPU is idle
1045
 *
1046
 * If the current CPU is in its idle loop and is neither in an interrupt
1047
 * or NMI handler, return true.
1048
 */
1049
bool notrace rcu_is_watching(void)
1050
{
1051
	bool ret;
1052

1053
	preempt_disable_notrace();
1054
	ret = __rcu_is_watching();
1055
	preempt_enable_notrace();
1056
	return ret;
1057
}
1058
EXPORT_SYMBOL_GPL(rcu_is_watching);
1059

1060
#if defined(CONFIG_PROVE_RCU) && defined(CONFIG_HOTPLUG_CPU)
1061 1062 1063 1064 1065 1066 1067

/*
 * Is the current CPU online?  Disable preemption to avoid false positives
 * that could otherwise happen due to the current CPU number being sampled,
 * this task being preempted, its old CPU being taken offline, resuming
 * on some other CPU, then determining that its old CPU is now offline.
 * It is OK to use RCU on an offline processor during initial boot, hence
1068 1069 1070 1071 1072 1073
 * the check for rcu_scheduler_fully_active.  Note also that it is OK
 * for a CPU coming online to use RCU for one jiffy prior to marking itself
 * online in the cpu_online_mask.  Similarly, it is OK for a CPU going
 * offline to continue to use RCU for one jiffy after marking itself
 * offline in the cpu_online_mask.  This leniency is necessary given the
 * non-atomic nature of the online and offline processing, for example,
1074 1075
 * the fact that a CPU enters the scheduler after completing the teardown
 * of the CPU.
1076
 *
1077 1078
 * This is also why RCU internally marks CPUs online during in the
 * preparation phase and offline after the CPU has been taken down.
1079 1080 1081 1082 1083 1084
 *
 * Disable checking if in an NMI handler because we cannot safely report
 * errors from NMI handlers anyway.
 */
bool rcu_lockdep_current_cpu_online(void)
{
1085 1086
	struct rcu_data *rdp;
	struct rcu_node *rnp;
1087 1088 1089
	bool ret;

	if (in_nmi())
Fengguang Wu's avatar
Fengguang Wu committed
1090
		return true;
1091
	preempt_disable();
1092
	rdp = this_cpu_ptr(&rcu_sched_data);
1093
	rnp = rdp->mynode;
1094
	ret = (rdp->grpmask & rcu_rnp_online_cpus(rnp)) ||
1095 1096 1097 1098 1099 1100
	      !rcu_scheduler_fully_active;
	preempt_enable();
	return ret;
}
EXPORT_SYMBOL_GPL(rcu_lockdep_current_cpu_online);

1101
#endif /* #if defined(CONFIG_PROVE_RCU) && defined(CONFIG_HOTPLUG_CPU) */
1102

1103
/**
1104
 * rcu_is_cpu_rrupt_from_idle - see if idle or immediately interrupted from idle
1105
 *
1106 1107 1108
 * If the current CPU is idle or running at a first-level (not nested)
 * interrupt from idle, return true.  The caller must have at least
 * disabled preemption.
1109
 */
1110
static int rcu_is_cpu_rrupt_from_idle(void)
1111
{
1112
	return __this_cpu_read(rcu_dynticks.dynticks_nesting) <= 1;
1113 1114 1115 1116 1117
}

/*
 * Snapshot the specified CPU's dynticks counter so that we can later
 * credit them with an implicit quiescent state.  Return 1 if this CPU
1118
 * is in dynticks idle mode, which is an extended quiescent state.
1119
 */
1120 1121
static int dyntick_save_progress_counter(struct rcu_data *rdp,
					 bool *isidle, unsigned long *maxj)
1122
{
1123
	rdp->dynticks_snap = atomic_add_return(0, &rdp->dynticks->dynticks);
1124
	rcu_sysidle_check_cpu(rdp, isidle, maxj);
1125 1126
	if ((rdp->dynticks_snap & 0x1) == 0) {
		trace_rcu_fqs(rdp->rsp->name, rdp->gpnum, rdp->cpu, TPS("dti"));
1127
		if (ULONG_CMP_LT(READ_ONCE(rdp->gpnum) + ULONG_MAX / 4,
1128
				 rdp->mynode->gpnum))
1129
			WRITE_ONCE(rdp->gpwrap, true);
1130
		return 1;
1131
	}
1132
	return 0;
1133 1134 1135 1136 1137 1138
}

/*
 * Return true if the specified CPU has passed through a quiescent
 * state by virtue of being in or having passed through an dynticks
 * idle state since the last call to dyntick_save_progress_counter()
1139
 * for this same CPU, or by virtue of having been offline.
1140
 */
1141 1142
static int rcu_implicit_dynticks_qs(struct rcu_data *rdp,
				    bool *isidle, unsigned long *maxj)
1143
{
1144
	unsigned int curr;
1145
	int *rcrmp;
1146
	unsigned int snap;
1147

1148 1149
	curr = (unsigned int)atomic_add_return(0, &rdp->dynticks->dynticks);
	snap = (unsigned int)rdp->dynticks_snap;
1150 1151 1152 1153 1154 1155 1156 1157 1158

	/*
	 * If the CPU passed through or entered a dynticks idle phase with
	 * no active irq/NMI handlers, then we can safely pretend that the CPU
	 * already acknowledged the request to pass through a quiescent
	 * state.  Either way, that CPU cannot possibly be in an RCU
	 * read-side critical section that started before the beginning
	 * of the current RCU grace period.
	 */
1159
	if ((curr & 0x1) == 0 || UINT_CMP_GE(curr, snap + 2)) {
1160
		trace_rcu_fqs(rdp->rsp->name, rdp->gpnum, rdp->cpu, TPS("dti"));