tree.c 139.5 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
#include <linux/completion.h>
#include <linux/moduleparam.h>
44
#include <linux/module.h>
45 46 47 48 49
#include <linux/percpu.h>
#include <linux/notifier.h>
#include <linux/cpu.h>
#include <linux/mutex.h>
#include <linux/time.h>
50
#include <linux/kernel_stat.h>
51 52
#include <linux/wait.h>
#include <linux/kthread.h>
53
#include <linux/prefetch.h>
54 55
#include <linux/delay.h>
#include <linux/stop_machine.h>
56
#include <linux/random.h>
57
#include <linux/trace_events.h>
58
#include <linux/suspend.h>
59

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

63 64 65 66 67 68
MODULE_ALIAS("rcutree");
#ifdef MODULE_PARAM_PREFIX
#undef MODULE_PARAM_PREFIX
#endif
#define MODULE_PARAM_PREFIX "rcutree."

69 70
/* Data structures. */

71
static struct lock_class_key rcu_node_class[RCU_NUM_LVLS];
72
static struct lock_class_key rcu_fqs_class[RCU_NUM_LVLS];
73
static struct lock_class_key rcu_exp_class[RCU_NUM_LVLS];
74

75 76 77 78 79 80 81 82
/*
 * 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.
 */
83 84
#ifdef CONFIG_TRACING
# define DEFINE_RCU_TPS(sname) \
85
static char sname##_varname[] = #sname; \
86 87 88 89 90 91 92 93 94
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) \
95
static DEFINE_PER_CPU_SHARED_ALIGNED(struct rcu_data, sname##_data); \
96
struct rcu_state sname##_state = { \
97
	.level = { &sname##_state.node[0] }, \
98
	.rda = &sname##_data, \
99
	.call = cr, \
100
	.fqs_state = RCU_GP_IDLE, \
P
Paul E. McKenney 已提交
101 102
	.gpnum = 0UL - 300UL, \
	.completed = 0UL - 300UL, \
103
	.orphan_lock = __RAW_SPIN_LOCK_UNLOCKED(&sname##_state.orphan_lock), \
104 105
	.orphan_nxttail = &sname##_state.orphan_nxtlist, \
	.orphan_donetail = &sname##_state.orphan_donelist, \
106
	.barrier_mutex = __MUTEX_INITIALIZER(sname##_state.barrier_mutex), \
107
	.name = RCU_STATE_NAME(sname), \
108
	.abbr = sabbr, \
109
}
110

111 112
RCU_STATE_INITIALIZER(rcu_sched, 's', call_rcu_sched);
RCU_STATE_INITIALIZER(rcu_bh, 'b', call_rcu_bh);
113

114
static struct rcu_state *const rcu_state_p;
115
static struct rcu_data __percpu *const rcu_data_p;
116
LIST_HEAD(rcu_struct_flavors);
117

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

132 133 134 135
/*
 * 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)
136
 * optimize synchronize_sched() to a simple barrier().  When this variable
137 138 139 140
 * 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.
 */
141 142 143
int rcu_scheduler_active __read_mostly;
EXPORT_SYMBOL_GPL(rcu_scheduler_active);

144 145 146 147 148 149 150 151 152 153 154 155 156 157
/*
 * 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;

158 159
static void rcu_init_new_rnp(struct rcu_node *rnp_leaf);
static void rcu_cleanup_dead_rnp(struct rcu_node *rnp_leaf);
T
Thomas Gleixner 已提交
160
static void rcu_boost_kthread_setaffinity(struct rcu_node *rnp, int outgoingcpu);
161 162
static void invoke_rcu_core(void);
static void invoke_rcu_callbacks(struct rcu_state *rsp, struct rcu_data *rdp);
163 164
static void rcu_report_exp_rdp(struct rcu_state *rsp,
			       struct rcu_data *rdp, bool wake);
165

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

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

#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 */

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

190 191 192 193 194 195 196
#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 */

197 198 199 200 201 202 203 204 205 206
/*
 * 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. */
207

208 209 210 211 212 213 214 215 216 217 218 219
/*
 * 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;

220 221 222 223 224 225 226 227
/*
 * 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)
{
228
	return READ_ONCE(rnp->qsmaskinitnext);
229 230
}

231
/*
232
 * Return true if an RCU grace period is in progress.  The READ_ONCE()s
233 234 235 236 237
 * 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)
{
238
	return READ_ONCE(rsp->completed) != READ_ONCE(rsp->gpnum);
239 240
}

241
/*
242
 * Note a quiescent state.  Because we do not need to know
243
 * how many quiescent states passed, just if there was at least
244
 * one since the start of the grace period, this just sets a flag.
245
 * The caller must have disabled preemption.
246
 */
247
void rcu_sched_qs(void)
248
{
249
	if (__this_cpu_read(rcu_sched_data.cpu_no_qs.s)) {
250 251 252
		trace_rcu_grace_period(TPS("rcu_sched"),
				       __this_cpu_read(rcu_sched_data.gpnum),
				       TPS("cpuqs"));
253
		__this_cpu_write(rcu_sched_data.cpu_no_qs.b.norm, false);
254 255 256 257 258 259
		if (__this_cpu_read(rcu_sched_data.cpu_no_qs.b.exp)) {
			__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);
		}
260
	}
261 262
}

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

273 274 275 276 277 278 279 280 281 282 283
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 */
};

284 285 286
DEFINE_PER_CPU_SHARED_ALIGNED(unsigned long, rcu_qs_ctr);
EXPORT_PER_CPU_SYMBOL_GPL(rcu_qs_ctr);

287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320
/*
 * 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.
 */
static void rcu_momentary_dyntick_idle(void)
{
	unsigned long flags;
	struct rcu_data *rdp;
	struct rcu_dynticks *rdtp;
	int resched_mask;
	struct rcu_state *rsp;

	local_irq_save(flags);

	/*
	 * 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. */
321 322
		if (READ_ONCE(rdp->mynode->completed) !=
		    READ_ONCE(rdp->cond_resched_completed))
323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339
			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;
	}
	local_irq_restore(flags);
}

340 341 342
/*
 * Note a context switch.  This is a quiescent state for RCU-sched,
 * and requires special handling for preemptible RCU.
343
 * The caller must have disabled preemption.
344
 */
345
void rcu_note_context_switch(void)
346
{
347
	trace_rcu_utilization(TPS("Start context switch"));
348
	rcu_sched_qs();
349
	rcu_preempt_note_context_switch();
350 351
	if (unlikely(raw_cpu_read(rcu_sched_qs_mask)))
		rcu_momentary_dyntick_idle();
352
	trace_rcu_utilization(TPS("End context switch"));
353
}
354
EXPORT_SYMBOL_GPL(rcu_note_context_switch);
355

356
/*
357
 * Register a quiescent state for all RCU flavors.  If there is an
358 359
 * emergency, invoke rcu_momentary_dyntick_idle() to do a heavy-weight
 * dyntick-idle quiescent state visible to other CPUs (but only for those
360
 * RCU flavors in desperate need of a quiescent state, which will normally
361 362 363 364 365 366 367 368 369 370 371
 * be none of them).  Either way, do a lightweight quiescent state for
 * all RCU flavors.
 */
void rcu_all_qs(void)
{
	if (unlikely(raw_cpu_read(rcu_sched_qs_mask)))
		rcu_momentary_dyntick_idle();
	this_cpu_inc(rcu_qs_ctr);
}
EXPORT_SYMBOL_GPL(rcu_all_qs);

E
Eric Dumazet 已提交
372 373 374
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. */
375

E
Eric Dumazet 已提交
376 377 378
module_param(blimit, long, 0444);
module_param(qhimark, long, 0444);
module_param(qlowmark, long, 0444);
379

380 381
static ulong jiffies_till_first_fqs = ULONG_MAX;
static ulong jiffies_till_next_fqs = ULONG_MAX;
382 383 384 385

module_param(jiffies_till_first_fqs, ulong, 0644);
module_param(jiffies_till_next_fqs, ulong, 0644);

386 387 388 389 390 391 392
/*
 * 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);

393
static bool rcu_start_gp_advanced(struct rcu_state *rsp, struct rcu_node *rnp,
394
				  struct rcu_data *rdp);
395 396 397 398
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);
399
static void force_quiescent_state(struct rcu_state *rsp);
400
static int rcu_pending(void);
401 402

/*
403
 * Return the number of RCU batches started thus far for debug & stats.
404
 */
405 406 407 408 409 410 411 412
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.
413
 */
414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439
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.
440
 */
441
unsigned long rcu_batches_completed_sched(void)
442
{
443
	return rcu_sched_state.completed;
444
}
445
EXPORT_SYMBOL_GPL(rcu_batches_completed_sched);
446 447

/*
448
 * Return the number of RCU BH batches completed thus far for debug & stats.
449
 */
450
unsigned long rcu_batches_completed_bh(void)
451 452 453 454 455
{
	return rcu_bh_state.completed;
}
EXPORT_SYMBOL_GPL(rcu_batches_completed_bh);

456 457 458 459 460
/*
 * Force a quiescent state.
 */
void rcu_force_quiescent_state(void)
{
461
	force_quiescent_state(rcu_state_p);
462 463 464
}
EXPORT_SYMBOL_GPL(rcu_force_quiescent_state);

465 466 467 468 469
/*
 * Force a quiescent state for RCU BH.
 */
void rcu_bh_force_quiescent_state(void)
{
470
	force_quiescent_state(&rcu_bh_state);
471 472 473
}
EXPORT_SYMBOL_GPL(rcu_bh_force_quiescent_state);

474 475 476 477 478 479 480 481 482
/*
 * 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);

483 484 485 486 487 488 489 490 491 492 493 494 495 496 497
/*
 * 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);

498 499 500 501 502 503 504 505 506 507 508 509 510 511
/*
 * 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);

512 513 514 515 516 517 518 519 520 521
/*
 * 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:
522
		rsp = rcu_state_p;
523 524 525 526 527 528 529 530 531 532 533
		break;
	case RCU_BH_FLAVOR:
		rsp = &rcu_bh_state;
		break;
	case RCU_SCHED_FLAVOR:
		rsp = &rcu_sched_state;
		break;
	default:
		break;
	}
	if (rsp != NULL) {
534 535 536
		*flags = READ_ONCE(rsp->gp_flags);
		*gpnum = READ_ONCE(rsp->gpnum);
		*completed = READ_ONCE(rsp->completed);
537 538 539 540 541 542 543 544
		return;
	}
	*flags = 0;
	*gpnum = 0;
	*completed = 0;
}
EXPORT_SYMBOL_GPL(rcutorture_get_gp_data);

545 546 547 548 549 550 551 552 553 554 555
/*
 * 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);

556 557 558 559 560 561
/*
 * Does the CPU have callbacks ready to be invoked?
 */
static int
cpu_has_callbacks_ready_to_invoke(struct rcu_data *rdp)
{
P
Paul E. McKenney 已提交
562 563
	return &rdp->nxtlist != rdp->nxttail[RCU_DONE_TAIL] &&
	       rdp->nxttail[RCU_DONE_TAIL] != NULL;
564 565
}

566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581
/*
 * 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);
582
	int idx = (READ_ONCE(rnp->completed) + 1) & 0x1;
583 584
	int *fp = &rnp->need_future_gp[idx];

585
	return READ_ONCE(*fp);
586 587
}

588
/*
589 590 591
 * Does the current CPU require a not-yet-started grace period?
 * The caller must have disabled interrupts to prevent races with
 * normal callback registry.
592 593 594 595
 */
static int
cpu_needs_another_gp(struct rcu_state *rsp, struct rcu_data *rdp)
{
596
	int i;
P
Paul E. McKenney 已提交
597

598 599
	if (rcu_gp_in_progress(rsp))
		return 0;  /* No, a grace period is already in progress. */
600
	if (rcu_future_needs_gp(rsp))
601
		return 1;  /* Yes, a no-CBs CPU needs one. */
602 603 604 605 606 607
	if (!rdp->nxttail[RCU_NEXT_TAIL])
		return 0;  /* No, this is a no-CBs (or offline) CPU. */
	if (*rdp->nxttail[RCU_NEXT_READY_TAIL])
		return 1;  /* Yes, this CPU has newly registered callbacks. */
	for (i = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++)
		if (rdp->nxttail[i - 1] != rdp->nxttail[i] &&
608
		    ULONG_CMP_LT(READ_ONCE(rsp->completed),
609 610 611
				 rdp->nxtcompleted[i]))
			return 1;  /* Yes, CBs for future grace period. */
	return 0; /* No grace period needed. */
612 613
}

614
/*
615
 * rcu_eqs_enter_common - current CPU is moving towards extended quiescent state
616 617 618 619 620
 *
 * 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.
 */
621
static void rcu_eqs_enter_common(long long oldval, bool user)
622
{
623 624
	struct rcu_state *rsp;
	struct rcu_data *rdp;
625
	struct rcu_dynticks *rdtp = this_cpu_ptr(&rcu_dynticks);
626

627
	trace_rcu_dyntick(TPS("Start"), oldval, rdtp->dynticks_nesting);
628 629
	if (IS_ENABLED(CONFIG_RCU_EQS_DEBUG) &&
	    !user && !is_idle_task(current)) {
630 631
		struct task_struct *idle __maybe_unused =
			idle_task(smp_processor_id());
632

633
		trace_rcu_dyntick(TPS("Error on entry: not idle task"), oldval, 0);
634
		ftrace_dump(DUMP_ORIG);
635 636 637
		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! */
638
	}
639 640 641 642
	for_each_rcu_flavor(rsp) {
		rdp = this_cpu_ptr(rsp->rda);
		do_nocb_deferred_wakeup(rdp);
	}
643
	rcu_prepare_for_idle();
644
	/* CPUs seeing atomic_inc() must see prior RCU read-side crit sects */
645
	smp_mb__before_atomic();  /* See above. */
646
	atomic_inc(&rdtp->dynticks);
647
	smp_mb__after_atomic();  /* Force ordering with next sojourn. */
648 649
	WARN_ON_ONCE(IS_ENABLED(CONFIG_RCU_EQS_DEBUG) &&
		     atomic_read(&rdtp->dynticks) & 0x1);
650
	rcu_dynticks_task_enter();
651 652

	/*
653
	 * It is illegal to enter an extended quiescent state while
654 655
	 * in an RCU read-side critical section.
	 */
656 657 658 659 660 661
	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.");
662
}
663

664 665 666
/*
 * Enter an RCU extended quiescent state, which can be either the
 * idle loop or adaptive-tickless usermode execution.
667
 */
668
static void rcu_eqs_enter(bool user)
669
{
670
	long long oldval;
671 672
	struct rcu_dynticks *rdtp;

673
	rdtp = this_cpu_ptr(&rcu_dynticks);
674
	oldval = rdtp->dynticks_nesting;
675 676
	WARN_ON_ONCE(IS_ENABLED(CONFIG_RCU_EQS_DEBUG) &&
		     (oldval & DYNTICK_TASK_NEST_MASK) == 0);
677
	if ((oldval & DYNTICK_TASK_NEST_MASK) == DYNTICK_TASK_NEST_VALUE) {
678
		rdtp->dynticks_nesting = 0;
679
		rcu_eqs_enter_common(oldval, user);
680
	} else {
681
		rdtp->dynticks_nesting -= DYNTICK_TASK_NEST_VALUE;
682
	}
683
}
684 685 686 687 688 689 690 691 692 693 694 695 696 697 698

/**
 * 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)
{
699 700 701
	unsigned long flags;

	local_irq_save(flags);
702
	rcu_eqs_enter(false);
703
	rcu_sysidle_enter(0);
704
	local_irq_restore(flags);
705
}
706
EXPORT_SYMBOL_GPL(rcu_idle_enter);
707

708
#ifdef CONFIG_NO_HZ_FULL
709 710 711 712 713 714 715 716 717 718
/**
 * 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)
{
719
	rcu_eqs_enter(1);
720
}
721
#endif /* CONFIG_NO_HZ_FULL */
722

723 724 725 726 727 728
/**
 * 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
 * sections can occur.
729
 *
730 731 732 733 734 735 736 737
 * 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.
738
 */
739
void rcu_irq_exit(void)
740 741
{
	unsigned long flags;
742
	long long oldval;
743 744 745
	struct rcu_dynticks *rdtp;

	local_irq_save(flags);
746
	rdtp = this_cpu_ptr(&rcu_dynticks);
747
	oldval = rdtp->dynticks_nesting;
748
	rdtp->dynticks_nesting--;
749 750
	WARN_ON_ONCE(IS_ENABLED(CONFIG_RCU_EQS_DEBUG) &&
		     rdtp->dynticks_nesting < 0);
751
	if (rdtp->dynticks_nesting)
752
		trace_rcu_dyntick(TPS("--="), oldval, rdtp->dynticks_nesting);
753
	else
754 755
		rcu_eqs_enter_common(oldval, true);
	rcu_sysidle_enter(1);
756 757 758 759
	local_irq_restore(flags);
}

/*
760
 * rcu_eqs_exit_common - current CPU moving away from extended quiescent state
761 762 763 764 765
 *
 * 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.
 */
766
static void rcu_eqs_exit_common(long long oldval, int user)
767
{
768 769
	struct rcu_dynticks *rdtp = this_cpu_ptr(&rcu_dynticks);

770
	rcu_dynticks_task_exit();
771
	smp_mb__before_atomic();  /* Force ordering w/previous sojourn. */
772 773
	atomic_inc(&rdtp->dynticks);
	/* CPUs seeing atomic_inc() must see later RCU read-side crit sects */
774
	smp_mb__after_atomic();  /* See above. */
775 776
	WARN_ON_ONCE(IS_ENABLED(CONFIG_RCU_EQS_DEBUG) &&
		     !(atomic_read(&rdtp->dynticks) & 0x1));
777
	rcu_cleanup_after_idle();
778
	trace_rcu_dyntick(TPS("End"), oldval, rdtp->dynticks_nesting);
779 780
	if (IS_ENABLED(CONFIG_RCU_EQS_DEBUG) &&
	    !user && !is_idle_task(current)) {
781 782
		struct task_struct *idle __maybe_unused =
			idle_task(smp_processor_id());
783

784
		trace_rcu_dyntick(TPS("Error on exit: not idle task"),
785
				  oldval, rdtp->dynticks_nesting);
786
		ftrace_dump(DUMP_ORIG);
787 788 789
		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! */
790 791 792
	}
}

793 794 795
/*
 * Exit an RCU extended quiescent state, which can be either the
 * idle loop or adaptive-tickless usermode execution.
796
 */
797
static void rcu_eqs_exit(bool user)
798 799 800 801
{
	struct rcu_dynticks *rdtp;
	long long oldval;

802
	rdtp = this_cpu_ptr(&rcu_dynticks);
803
	oldval = rdtp->dynticks_nesting;
804
	WARN_ON_ONCE(IS_ENABLED(CONFIG_RCU_EQS_DEBUG) && oldval < 0);
805
	if (oldval & DYNTICK_TASK_NEST_MASK) {
806
		rdtp->dynticks_nesting += DYNTICK_TASK_NEST_VALUE;
807
	} else {
808
		rdtp->dynticks_nesting = DYNTICK_TASK_EXIT_IDLE;
809
		rcu_eqs_exit_common(oldval, user);
810
	}
811
}
812 813 814 815 816 817 818 819 820 821 822 823 824 825

/**
 * 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)
{
826 827 828
	unsigned long flags;

	local_irq_save(flags);
829
	rcu_eqs_exit(false);
830
	rcu_sysidle_exit(0);
831
	local_irq_restore(flags);
832
}
833
EXPORT_SYMBOL_GPL(rcu_idle_exit);
834

835
#ifdef CONFIG_NO_HZ_FULL
836 837 838 839 840 841 842 843
/**
 * 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)
{
844
	rcu_eqs_exit(1);
845
}
846
#endif /* CONFIG_NO_HZ_FULL */
847

848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873
/**
 * 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
 * sections can occur.
 *
 * 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)
{
	unsigned long flags;
	struct rcu_dynticks *rdtp;
	long long oldval;

	local_irq_save(flags);
874
	rdtp = this_cpu_ptr(&rcu_dynticks);
875 876
	oldval = rdtp->dynticks_nesting;
	rdtp->dynticks_nesting++;
877 878
	WARN_ON_ONCE(IS_ENABLED(CONFIG_RCU_EQS_DEBUG) &&
		     rdtp->dynticks_nesting == 0);
879
	if (oldval)
880
		trace_rcu_dyntick(TPS("++="), oldval, rdtp->dynticks_nesting);
881
	else
882 883
		rcu_eqs_exit_common(oldval, true);
	rcu_sysidle_exit(1);
884 885 886 887 888 889
	local_irq_restore(flags);
}

/**
 * rcu_nmi_enter - inform RCU of entry to NMI context
 *
890 891 892 893 894
 * 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.)
895 896 897
 */
void rcu_nmi_enter(void)
{
898
	struct rcu_dynticks *rdtp = this_cpu_ptr(&rcu_dynticks);
899
	int incby = 2;
900

901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921
	/* 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();
922 923 924 925 926
}

/**
 * rcu_nmi_exit - inform RCU of exit from NMI context
 *
927 928 929 930
 * 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.
931 932 933
 */
void rcu_nmi_exit(void)
{
934
	struct rcu_dynticks *rdtp = this_cpu_ptr(&rcu_dynticks);
935

936 937 938 939 940 941 942 943 944 945 946 947 948 949
	/*
	 * 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;
950
		return;
951 952 953 954
	}

	/* This NMI interrupted an RCU-idle CPU, restore RCU-idleness. */
	rdtp->dynticks_nmi_nesting = 0;
955
	/* CPUs seeing atomic_inc() must see prior RCU read-side crit sects */
956
	smp_mb__before_atomic();  /* See above. */
957
	atomic_inc(&rdtp->dynticks);
958
	smp_mb__after_atomic();  /* Force delay to next write. */
959
	WARN_ON_ONCE(atomic_read(&rdtp->dynticks) & 0x1);
960 961 962
}

/**
963 964 965 966 967 968 969
 * __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.
 */
970
bool notrace __rcu_is_watching(void)
971 972 973 974 975 976
{
	return atomic_read(this_cpu_ptr(&rcu_dynticks.dynticks)) & 0x1;
}

/**
 * rcu_is_watching - see if RCU thinks that the current CPU is idle
977
 *
978
 * If the current CPU is in its idle loop and is neither in an interrupt
979
 * or NMI handler, return true.
980
 */
981
bool notrace rcu_is_watching(void)
982
{
983
	bool ret;
984

985
	preempt_disable_notrace();
986
	ret = __rcu_is_watching();
987
	preempt_enable_notrace();
988
	return ret;
989
}
990
EXPORT_SYMBOL_GPL(rcu_is_watching);
991

992
#if defined(CONFIG_PROVE_RCU) && defined(CONFIG_HOTPLUG_CPU)
993 994 995 996 997 998 999

/*
 * 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
1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010
 * 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,
 * the fact that a CPU enters the scheduler after completing the CPU_DYING
 * notifiers.
 *
 * This is also why RCU internally marks CPUs online during the
 * CPU_UP_PREPARE phase and offline during the CPU_DEAD phase.
1011 1012 1013 1014 1015 1016
 *
 * Disable checking if in an NMI handler because we cannot safely report
 * errors from NMI handlers anyway.
 */
bool rcu_lockdep_current_cpu_online(void)
{
1017 1018
	struct rcu_data *rdp;
	struct rcu_node *rnp;
1019 1020 1021
	bool ret;

	if (in_nmi())
F
Fengguang Wu 已提交
1022
		return true;
1023
	preempt_disable();
1024
	rdp = this_cpu_ptr(&rcu_sched_data);
1025
	rnp = rdp->mynode;
1026
	ret = (rdp->grpmask & rcu_rnp_online_cpus(rnp)) ||
1027 1028 1029 1030 1031 1032
	      !rcu_scheduler_fully_active;
	preempt_enable();
	return ret;
}
EXPORT_SYMBOL_GPL(rcu_lockdep_current_cpu_online);

1033
#endif /* #if defined(CONFIG_PROVE_RCU) && defined(CONFIG_HOTPLUG_CPU) */
1034

1035
/**
1036
 * rcu_is_cpu_rrupt_from_idle - see if idle or immediately interrupted from idle
1037
 *
1038 1039 1040
 * 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.
1041
 */
1042
static int rcu_is_cpu_rrupt_from_idle(void)
1043
{
1044
	return __this_cpu_read(rcu_dynticks.dynticks_nesting) <= 1;
1045 1046 1047 1048 1049
}

/*
 * Snapshot the specified CPU's dynticks counter so that we can later
 * credit them with an implicit quiescent state.  Return 1 if this CPU
1050
 * is in dynticks idle mode, which is an extended quiescent state.
1051
 */
1052 1053
static int dyntick_save_progress_counter(struct rcu_data *rdp,
					 bool *isidle, unsigned long *maxj)
1054
{
1055
	rdp->dynticks_snap = atomic_add_return(0, &rdp->dynticks->dynticks);
1056
	rcu_sysidle_check_cpu(rdp, isidle, maxj);
1057 1058 1059 1060
	if ((rdp->dynticks_snap & 0x1) == 0) {
		trace_rcu_fqs(rdp->rsp->name, rdp->gpnum, rdp->cpu, TPS("dti"));
		return 1;
	} else {
1061
		if (ULONG_CMP_LT(READ_ONCE(rdp->gpnum) + ULONG_MAX / 4,
1062
				 rdp->mynode->gpnum))
1063
			WRITE_ONCE(rdp->gpwrap, true);
1064 1065
		return 0;
	}
1066 1067 1068 1069 1070 1071
}

/*
 * 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()
1072
 * for this same CPU, or by virtue of having been offline.
1073
 */
1074 1075
static int rcu_implicit_dynticks_qs(struct rcu_data *rdp,
				    bool *isidle, unsigned long *maxj)
1076
{
1077
	unsigned int curr;
1078
	int *rcrmp;
1079
	unsigned int snap;
1080

1081 1082
	curr = (unsigned int)atomic_add_return(0, &rdp->dynticks->dynticks);
	snap = (unsigned int)rdp->dynticks_snap;
1083 1084 1085 1086 1087 1088 1089 1090 1091

	/*
	 * 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.
	 */
1092
	if ((curr & 0x1) == 0 || UINT_CMP_GE(curr, snap + 2)) {
1093
		trace_rcu_fqs(rdp->rsp->name, rdp->gpnum, rdp->cpu, TPS("dti"));
1094 1095 1096 1097
		rdp->dynticks_fqs++;
		return 1;
	}

1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112
	/*
	 * Check for the CPU being offline, but only if the grace period
	 * is old enough.  We don't need to worry about the CPU changing
	 * state: If we see it offline even once, it has been through a
	 * quiescent state.
	 *
	 * The reason for insisting that the grace period be at least
	 * one jiffy old is that CPUs that are not quite online and that
	 * have just gone offline can still execute RCU read-side critical
	 * sections.
	 */
	if (ULONG_CMP_GE(rdp->rsp->gp_start + 2, jiffies))
		return 0;  /* Grace period is not old enough. */
	barrier();
	if (cpu_is_offline(rdp->cpu)) {
1113
		trace_rcu_fqs(rdp->rsp->name, rdp->gpnum, rdp->cpu, TPS("ofl"));
1114 1115 1116
		rdp->offline_fqs++;
		return 1;
	}
1117 1118

	/*
1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137
	 * A CPU running for an extended time within the kernel can
	 * delay RCU grace periods.  When the CPU is in NO_HZ_FULL mode,
	 * even context-switching back and forth between a pair of
	 * in-kernel CPU-bound tasks cannot advance grace periods.
	 * So if the grace period is old enough, make the CPU pay attention.
	 * Note that the unsynchronized assignments to the per-CPU
	 * rcu_sched_qs_mask variable are safe.  Yes, setting of
	 * bits can be lost, but they will be set again on the next
	 * force-quiescent-state pass.  So lost bit sets do not result
	 * in incorrect behavior, merely in a grace period lasting
	 * a few jiffies longer than it might otherwise.  Because
	 * there are at most four threads involved, and because the
	 * updates are only once every few jiffies, the probability of
	 * lossage (and thus of slight grace-period extension) is
	 * quite low.
	 *
	 * Note that if the jiffies_till_sched_qs boot/sysfs parameter
	 * is set too high, we override with half of the RCU CPU stall
	 * warning delay.
1138
	 */
1139 1140 1141
	rcrmp = &per_cpu(rcu_sched_qs_mask, rdp->cpu);
	if (ULONG_CMP_GE(jiffies,
			 rdp->rsp->gp_start + jiffies_till_sched_qs) ||
1142
	    ULONG_CMP_GE(jiffies, rdp->rsp->jiffies_resched)) {
1143 1144 1145
		if (!(READ_ONCE(*rcrmp) & rdp->rsp->flavor_mask)) {
			WRITE_ONCE(rdp->cond_resched_completed,
				   READ_ONCE(rdp->mynode->completed));
1146
			smp_mb(); /* ->cond_resched_completed before *rcrmp. */
1147 1148
			WRITE_ONCE(*rcrmp,
				   READ_ONCE(*rcrmp) + rdp->rsp->flavor_mask);
1149 1150 1151 1152 1153 1154 1155
			resched_cpu(rdp->cpu);  /* Force CPU into scheduler. */
			rdp->rsp->jiffies_resched += 5; /* Enable beating. */
		} else if (ULONG_CMP_GE(jiffies, rdp->rsp->jiffies_resched)) {
			/* Time to beat on that CPU again! */
			resched_cpu(rdp->cpu);  /* Force CPU into scheduler. */
			rdp->rsp->jiffies_resched += 5; /* Re-enable beating. */
		}
1156 1157
	}

1158
	return 0;
1159 1160 1161 1162
}

static void record_gp_stall_check_time(struct rcu_state *rsp)
{
1163
	unsigned long j = jiffies;
1164
	unsigned long j1;
1165 1166 1167

	rsp->gp_start = j;
	smp_wmb(); /* Record start time before stall time. */
1168
	j1 = rcu_jiffies_till_stall_check();
1169
	WRITE_ONCE(rsp->jiffies_stall, j + j1);
1170
	rsp->jiffies_resched = j + j1 / 2;
1171
	rsp->n_force_qs_gpstart = READ_ONCE(rsp->n_force_qs);
1172 1173
}

1174 1175 1176 1177 1178 1179 1180 1181 1182
/*
 * Complain about starvation of grace-period kthread.
 */
static void rcu_check_gp_kthread_starvation(struct rcu_state *rsp)
{
	unsigned long gpa;
	unsigned long j;

	j = jiffies;
1183
	gpa = READ_ONCE(rsp->gp_activity);
1184
	if (j - gpa > 2 * HZ)
1185
		pr_err("%s kthread starved for %ld jiffies! g%lu c%lu f%#x s%d ->state=%#lx\n",
1186
		       rsp->name, j - gpa,
1187 1188 1189
		       rsp->gpnum, rsp->completed,
		       rsp->gp_flags, rsp->gp_state,
		       rsp->gp_kthread ? rsp->gp_kthread->state : 0);
1190 1191
}

1192
/*
1193
 * Dump stacks of all tasks running on stalled CPUs.
1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211
 */
static void rcu_dump_cpu_stacks(struct rcu_state *rsp)
{
	int cpu;
	unsigned long flags;
	struct rcu_node *rnp;

	rcu_for_each_leaf_node(rsp, rnp) {
		raw_spin_lock_irqsave(&rnp->lock, flags);
		if (rnp->qsmask != 0) {
			for (cpu = 0; cpu <= rnp->grphi - rnp->grplo; cpu++)
				if (rnp->qsmask & (1UL << cpu))
					dump_cpu_task(rnp->grplo + cpu);
		}
		raw_spin_unlock_irqrestore(&rnp->lock, flags);
	}
}

1212
static void print_other_cpu_stall(struct rcu_state *rsp, unsigned long gpnum)
1213 1214 1215 1216
{
	int cpu;
	long delta;
	unsigned long flags;
1217 1218
	unsigned long gpa;
	unsigned long j;
1219
	int ndetected = 0;
1220
	struct rcu_node *rnp = rcu_get_root(rsp);
1221
	long totqlen = 0;
1222 1223 1224

	/* Only let one CPU complain about others per time interval. */

P
Paul E. McKenney 已提交
1225
	raw_spin_lock_irqsave(&rnp->lock, flags);
1226
	delta = jiffies - READ_ONCE(rsp->jiffies_stall);
1227
	if (delta < RCU_STALL_RAT_DELAY || !rcu_gp_in_progress(rsp)) {
P
Paul E. McKenney 已提交
1228
		raw_spin_unlock_irqrestore(&rnp->lock, flags);
1229 1230
		return;
	}
1231 1232
	WRITE_ONCE(rsp->jiffies_stall,
		   jiffies + 3 * rcu_jiffies_till_stall_check() + 3);
P
Paul E. McKenney 已提交
1233
	raw_spin_unlock_irqrestore(&rnp->lock, flags);
1234

1235 1236 1237 1238 1239
	/*
	 * OK, time to rat on our buddy...
	 * See Documentation/RCU/stallwarn.txt for info on how to debug
	 * RCU CPU stall warnings.
	 */
1240
	pr_err("INFO: %s detected stalls on CPUs/tasks:",
1241
	       rsp->name);
1242
	print_cpu_stall_info_begin();
1243
	rcu_for_each_leaf_node(rsp, rnp) {
1244
		raw_spin_lock_irqsave(&rnp->lock, flags);
1245
		ndetected += rcu_print_task_stall(rnp);
1246 1247 1248 1249 1250 1251 1252 1253
		if (rnp->qsmask != 0) {
			for (cpu = 0; cpu <= rnp->grphi - rnp->grplo; cpu++)
				if (rnp->qsmask & (1UL << cpu)) {
					print_cpu_stall_info(rsp,
							     rnp->grplo + cpu);
					ndetected++;
				}
		}
1254
		raw_spin_unlock_irqrestore(&rnp->lock, flags);
1255
	}
1256 1257

	print_cpu_stall_info_end();
1258 1259
	for_each_possible_cpu(cpu)
		totqlen += per_cpu_ptr(rsp->rda, cpu)->qlen;
1260
	pr_cont("(detected by %d, t=%ld jiffies, g=%ld, c=%ld, q=%lu)\n",
1261
	       smp_processor_id(), (long)(jiffies - rsp->gp_start),
1262
	       (long)rsp->gpnum, (long)rsp->completed, totqlen);
1263
	if (ndetected) {
1264
		rcu_dump_cpu_stacks(rsp);
1265
	} else {
1266 1267
		if (READ_ONCE(rsp->gpnum) != gpnum ||
		    READ_ONCE(rsp->completed) == gpnum) {
1268 1269 1270
			pr_err("INFO: Stall ended before state dump start\n");
		} else {
			j = jiffies;
1271
			gpa = READ_ONCE(rsp->gp_activity);
1272
			pr_err("All QSes seen, last %s kthread activity %ld (%ld-%ld), jiffies_till_next_fqs=%ld, root ->qsmask %#lx\n",
1273
			       rsp->name, j - gpa, j, gpa,
1274 1275
			       jiffies_till_next_fqs,
			       rcu_get_root(rsp)->qsmask);
1276 1277 1278 1279
			/* In this case, the current CPU might be at fault. */
			sched_show_task(current);
		}
	}
1280

1281
	/* Complain about tasks blocking the grace period. */
1282 1283
	rcu_print_detail_task_stall(rsp);

1284 1285
	rcu_check_gp_kthread_starvation(rsp);

1286
	force_quiescent_state(rsp);  /* Kick them all. */
1287 1288 1289 1290
}

static void print_cpu_stall(struct rcu_state *rsp)
{
1291
	int cpu;
1292 1293
	unsigned long flags;
	struct rcu_node *rnp = rcu_get_root(rsp);
1294
	long totqlen = 0;
1295

1296 1297 1298 1299 1300
	/*
	 * OK, time to rat on ourselves...
	 * See Documentation/RCU/stallwarn.txt for info on how to debug
	 * RCU CPU stall warnings.
	 */
1301
	pr_err("INFO: %s self-detected stall on CPU", rsp->name);
1302 1303 1304
	print_cpu_stall_info_begin();
	print_cpu_stall_info(rsp, smp_processor_id());
	print_cpu_stall_info_end();
1305 1306
	for_each_possible_cpu(cpu)
		totqlen += per_cpu_ptr(rsp->rda, cpu)->qlen;
1307 1308 1309
	pr_cont(" (t=%lu jiffies g=%ld c=%ld q=%lu)\n",
		jiffies - rsp->gp_start,
		(long)rsp->gpnum, (long)rsp->completed, totqlen);
1310 1311 1312

	rcu_check_gp_kthread_starvation(rsp);

1313
	rcu_dump_cpu_stacks(rsp);
1314

P
Paul E. McKenney 已提交
1315
	raw_spin_lock_irqsave(&rnp->lock, flags);
1316 1317 1318
	if (ULONG_CMP_GE(jiffies, READ_ONCE(rsp->jiffies_stall)))
		WRITE_ONCE(rsp->jiffies_stall,
			   jiffies + 3 * rcu_jiffies_till_stall_check() + 3);
P
Paul E. McKenney 已提交
1319
	raw_spin_unlock_irqrestore(&rnp->lock, flags);
1320

1321 1322 1323 1324 1325 1326 1327 1328
	/*
	 * Attempt to revive the RCU machinery by forcing a context switch.
	 *
	 * A context switch would normally allow the RCU state machine to make
	 * progress and it could be we're stuck in kernel space without context
	 * switches for an entirely unreasonable amount of time.
	 */
	resched_cpu(smp_processor_id());
1329 1330 1331 1332
}

static void check_cpu_stall(struct rcu_state *rsp, struct rcu_data *rdp)
{
1333 1334 1335
	unsigned long completed;
	unsigned long gpnum;
	unsigned long gps;
1336 1337
	unsigned long j;
	unsigned long js;
1338 1339
	struct rcu_node *rnp;

1340
	if (rcu_cpu_stall_suppress || !rcu_gp_in_progress(rsp))
1341
		return;
1342
	j = jiffies;
1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360

	/*
	 * Lots of memory barriers to reject false positives.
	 *
	 * The idea is to pick up rsp->gpnum, then rsp->jiffies_stall,
	 * then rsp->gp_start, and finally rsp->completed.  These values
	 * are updated in the opposite order with memory barriers (or
	 * equivalent) during grace-period initialization and cleanup.
	 * Now, a false positive can occur if we get an new value of
	 * rsp->gp_start and a old value of rsp->jiffies_stall.  But given
	 * the memory barriers, the only way that this can happen is if one
	 * grace period ends and another starts between these two fetches.
	 * Detect this by comparing rsp->completed with the previous fetch
	 * from rsp->gpnum.
	 *
	 * Given this check, comparisons of jiffies, rsp->jiffies_stall,
	 * and rsp->gp_start suffice to forestall false positives.
	 */
1361
	gpnum = READ_ONCE(rsp->gpnum);
1362
	smp_rmb(); /* Pick up ->gpnum first... */
1363
	js = READ_ONCE(rsp->jiffies_stall);
1364
	smp_rmb(); /* ...then ->jiffies_stall before the rest... */
1365
	gps = READ_ONCE(rsp->gp_start);
1366
	smp_rmb(); /* ...and finally ->gp_start before ->completed. */
1367
	completed = READ_ONCE(rsp->completed);
1368 1369 1370 1371
	if (ULONG_CMP_GE(completed, gpnum) ||
	    ULONG_CMP_LT(j, js) ||
	    ULONG_CMP_GE(gps, js))
		return; /* No stall or GP completed since entering function. */
1372
	rnp = rdp->mynode;
1373
	if (rcu_gp_in_progress(rsp) &&
1374
	    (READ_ONCE(rnp->qsmask) & rdp->grpmask)) {
1375 1376 1377 1378

		/* We haven't checked in, so go dump stack. */
		print_cpu_stall(rsp);

1379 1380
	} else if (rcu_gp_in_progress(rsp) &&
		   ULONG_CMP_GE(j, js + RCU_STALL_RAT_DELAY)) {
1381

1382
		/* They had a few time units to dump stack, so complain. */
1383
		print_other_cpu_stall(rsp, gpnum);
1384 1385 1386
	}
}

1387 1388 1389 1390 1391 1392 1393 1394 1395 1396 1397
/**
 * rcu_cpu_stall_reset - prevent further stall warnings in current grace period
 *
 * Set the stall-warning timeout way off into the future, thus preventing
 * any RCU CPU stall-warning messages from appearing in the current set of
 * RCU grace periods.
 *
 * The caller must disable hard irqs.
 */
void rcu_cpu_stall_reset(void)
{
1398 1399 1400
	struct rcu_state *rsp;

	for_each_rcu_flavor(rsp)
1401
		WRITE_ONCE(rsp->jiffies_stall, jiffies + ULONG_MAX / 2);
1402 1403
}

1404
/*
1405 1406 1407
 * Initialize the specified rcu_data structure's default callback list
 * to empty.  The default callback list is the one that is not used by
 * no-callbacks CPUs.
1408
 */
1409
static void init_default_callback_list(struct rcu_data *rdp)
1410 1411 1412 1413 1414 1415 1416 1417
{
	int i;

	rdp->nxtlist = NULL;
	for (i = 0; i < RCU_NEXT_SIZE; i++)
		rdp->nxttail[i] = &rdp->nxtlist;
}

1418 1419 1420 1421 1422 1423 1424 1425 1426 1427
/*
 * Initialize the specified rcu_data structure's callback list to empty.
 */
static void init_callback_list(struct rcu_data *rdp)
{
	if (init_nocb_callback_list(rdp))
		return;
	init_default_callback_list(rdp);
}

1428 1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 1447 1448 1449 1450 1451 1452 1453 1454 1455 1456
/*
 * Determine the value that ->completed will have at the end of the
 * next subsequent grace period.  This is used to tag callbacks so that
 * a CPU can invoke callbacks in a timely fashion even if that CPU has
 * been dyntick-idle for an extended period with callbacks under the
 * influence of RCU_FAST_NO_HZ.
 *
 * The caller must hold rnp->lock with interrupts disabled.
 */
static unsigned long rcu_cbs_completed(struct rcu_state *rsp,
				       struct rcu_node *rnp)
{
	/*
	 * If RCU is idle, we just wait for the next grace period.
	 * But we can only be sure that RCU is idle if we are looking
	 * at the root rcu_node structure -- otherwise, a new grace
	 * period might have started, but just not yet gotten around
	 * to initializing the current non-root rcu_node structure.
	 */
	if (rcu_get_root(rsp) == rnp && rnp->gpnum == rnp->completed)
		return rnp->completed + 1;

	/*
	 * Otherwise, wait for a possible partial grace period and
	 * then the subsequent full grace period.
	 */
	return rnp->completed + 2;
}

1457 1458 1459 1460 1461
/*
 * Trace-event helper function for rcu_start_future_gp() and
 * rcu_nocb_wait_gp().
 */
static void trace_rcu_future_gp(struct rcu_node *rnp, struct rcu_data *rdp,
1462
				unsigned long c, const char *s)
1463 1464 1465 1466 1467 1468 1469 1470 1471
{
	trace_rcu_future_grace_period(rdp->rsp->name, rnp->gpnum,
				      rnp->completed, c, rnp->level,
				      rnp->grplo, rnp->grphi, s);
}

/*
 * Start some future grace period, as needed to handle newly arrived
 * callbacks.  The required future grace periods are recorded in each
1472 1473
 * rcu_node structure's ->need_future_gp field.  Returns true if there
 * is reason to awaken the grace-period kthread.
1474 1475 1476
 *
 * The caller must hold the specified rcu_node structure's ->lock.
 */
1477 1478 1479
static bool __maybe_unused
rcu_start_future_gp(struct rcu_node *rnp, struct rcu_data *rdp,
		    unsigned long *c_out)
1480 1481 1482
{
	unsigned long c;
	int i;
1483
	bool ret = false;
1484 1485 1486 1487 1488 1489 1490
	struct rcu_node *rnp_root = rcu_get_root(rdp->rsp);

	/*
	 * Pick up grace-period number for new callbacks.  If this
	 * grace period is already marked as needed, return to the caller.
	 */
	c = rcu_cbs_completed(rdp->rsp, rnp);
1491
	trace_rcu_future_gp(rnp, rdp, c, TPS("Startleaf"));
1492
	if (rnp->need_future_gp[c & 0x1]) {
1493
		trace_rcu_future_gp(rnp, rdp, c, TPS("Prestartleaf"));
1494
		goto out;
1495 1496 1497 1498 1499 1500 1501
	}

	/*
	 * If either this rcu_node structure or the root rcu_node structure
	 * believe that a grace period is in progress, then we must wait
	 * for the one following, which is in "c".  Because our request
	 * will be noticed at the end of the current grace period, we don't
1502 1503 1504 1505 1506 1507 1508
	 * need to explicitly start one.  We only do the lockless check
	 * of rnp_root's fields if the current rcu_node structure thinks
	 * there is no grace period in flight, and because we hold rnp->lock,
	 * the only possible change is when rnp_root's two fields are
	 * equal, in which case rnp_root->gpnum might be concurrently
	 * incremented.  But that is OK, as it will just result in our
	 * doing some extra useless work.
1509 1510
	 */
	if (rnp->gpnum != rnp->completed ||
1511
	    READ_ONCE(rnp_root->gpnum) != READ_ONCE(rnp_root->completed)) {
1512
		rnp->need_future_gp[c & 0x1]++;
1513
		trace_rcu_future_gp(rnp, rdp, c, TPS("Startedleaf"));
1514
		goto out;
1515 1516 1517 1518 1519 1520 1521
	}

	/*
	 * There might be no grace period in progress.  If we don't already
	 * hold it, acquire the root rcu_node structure's lock in order to
	 * start one (if needed).
	 */
1522
	if (rnp != rnp_root) {
1523
		raw_spin_lock(&rnp_root->lock);
1524 1525
		smp_mb__after_unlock_lock();
	}
1526 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542

	/*
	 * Get a new grace-period number.  If there really is no grace
	 * period in progress, it will be smaller than the one we obtained
	 * earlier.  Adjust callbacks as needed.  Note that even no-CBs
	 * CPUs have a ->nxtcompleted[] array, so no no-CBs checks needed.
	 */
	c = rcu_cbs_completed(rdp->rsp, rnp_root);
	for (i = RCU_DONE_TAIL; i < RCU_NEXT_TAIL; i++)
		if (ULONG_CMP_LT(c, rdp->nxtcompleted[i]))
			rdp->nxtcompleted[i] = c;

	/*
	 * If the needed for the required grace period is already
	 * recorded, trace and leave.
	 */
	if (rnp_root->need_future_gp[c & 0x1]) {
1543
		trace_rcu_future_gp(rnp, rdp, c, TPS("Prestartedroot"));
1544 1545 1546 1547 1548 1549 1550 1551
		goto unlock_out;
	}

	/* Record the need for the future grace period. */
	rnp_root->need_future_gp[c & 0x1]++;

	/* If a grace period is not already in progress, start one. */
	if (rnp_root->gpnum != rnp_root->completed) {
1552
		trace_rcu_future_gp(rnp, rdp, c, TPS("Startedleafroot"));
1553
	} else {
1554
		trace_rcu_future_gp(rnp, rdp, c, TPS("Startedroot"));
1555
		ret = rcu_start_gp_advanced(rdp->rsp, rnp_root, rdp);
1556 1557 1558 1559
	}
unlock_out:
	if (rnp != rnp_root)
		raw_spin_unlock(&rnp_root->lock);
1560 1561 1562 1563
out:
	if (c_out != NULL)
		*c_out = c;
	return ret;
1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580
}

/*
 * Clean up any old requests for the just-ended grace period.  Also return
 * whether any additional grace periods have been requested.  Also invoke
 * rcu_nocb_gp_cleanup() in order to wake up any no-callbacks kthreads
 * waiting for this grace period to complete.
 */
static int rcu_future_gp_cleanup(struct rcu_state *rsp, struct rcu_node *rnp)
{
	int c = rnp->completed;
	int needmore;
	struct rcu_data *rdp = this_cpu_ptr(rsp->rda);

	rcu_nocb_gp_cleanup(rsp, rnp);
	rnp->need_future_gp[c & 0x1] = 0;
	needmore = rnp->need_future_gp[(c + 1) & 0x1];
1581 1582
	trace_rcu_future_gp(rnp, rdp, c,
			    needmore ? TPS("CleanupMore") : TPS("Cleanup"));
1583 1584 1585
	return needmore;
}

1586 1587 1588 1589 1590 1591 1592 1593 1594 1595
/*
 * Awaken the grace-period kthread for the specified flavor of RCU.
 * Don't do a self-awaken, and don't bother awakening when there is
 * nothing for the grace-period kthread to do (as in several CPUs
 * raced to awaken, and we lost), and finally don't try to awaken
 * a kthread that has not yet been created.
 */
static void rcu_gp_kthread_wake(struct rcu_state *rsp)
{
	if (current == rsp->gp_kthread ||
1596
	    !READ_ONCE(rsp->gp_flags) ||
1597 1598 1599 1600 1601
	    !rsp->gp_kthread)
		return;
	wake_up(&rsp->gp_wq);
}

1602 1603 1604 1605 1606 1607 1608
/*
 * If there is room, assign a ->completed number to any callbacks on
 * this CPU that have not already been assigned.  Also accelerate any
 * callbacks that were previously assigned a ->completed number that has
 * since proven to be too conservative, which can happen if callbacks get
 * assigned a ->completed number while RCU is idle, but with reference to
 * a non-root rcu_node structure.  This function is idempotent, so it does
1609 1610
 * not hurt to call it repeatedly.  Returns an flag saying that we should
 * awaken the RCU grace-period kthread.
1611 1612 1613
 *
 * The caller must hold rnp->lock with interrupts disabled.
 */
1614
static bool rcu_accelerate_cbs(struct rcu_state *rsp, struct rcu_node *rnp,
1615 1616 1617 1618
			       struct rcu_data *rdp)
{
	unsigned long c;
	int i;
1619
	bool ret;
1620 1621 1622

	/* If the CPU has no callbacks, nothing to do. */
	if (!rdp->nxttail[RCU_NEXT_TAIL] || !*rdp->nxttail[RCU_DONE_TAIL])
1623
		return false;
1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 1650 1651

	/*
	 * Starting from the sublist containing the callbacks most
	 * recently assigned a ->completed number and working down, find the
	 * first sublist that is not assignable to an upcoming grace period.
	 * Such a sublist has something in it (first two tests) and has
	 * a ->completed number assigned that will complete sooner than
	 * the ->completed number for newly arrived callbacks (last test).
	 *
	 * The key point is that any later sublist can be assigned the
	 * same ->completed number as the newly arrived callbacks, which
	 * means that the callbacks in any of these later sublist can be
	 * grouped into a single sublist, whether or not they have already
	 * been assigned a ->completed number.
	 */
	c = rcu_cbs_completed(rsp, rnp);
	for (i = RCU_NEXT_TAIL - 1; i > RCU_DONE_TAIL; i--)
		if (rdp->nxttail[i] != rdp->nxttail[i - 1] &&
		    !ULONG_CMP_GE(rdp->nxtcompleted[i], c))
			break;

	/*
	 * If there are no sublist for unassigned callbacks, leave.
	 * At the same time, advance "i" one sublist, so that "i" will
	 * index into the sublist where all the remaining callbacks should
	 * be grouped into.
	 */
	if (++i >= RCU_NEXT_TAIL)
1652
		return false;
1653 1654 1655 1656 1657 1658 1659 1660 1661 1662

	/*
	 * Assign all subsequent callbacks' ->completed number to the next
	 * full grace period and group them all in the sublist initially
	 * indexed by "i".
	 */
	for (; i <= RCU_NEXT_TAIL; i++) {
		rdp->nxttail[i] = rdp->nxttail[RCU_NEXT_TAIL];
		rdp->nxtcompleted[i] = c;
	}
1663
	/* Record any needed additional grace periods. */
1664
	ret = rcu_start_future_gp(rnp, rdp, NULL);
1665 1666 1667

	/* Trace depending on how much we were able to accelerate. */
	if (!*rdp->nxttail[RCU_WAIT_TAIL])
1668
		trace_rcu_grace_period(rsp->name, rdp->gpnum, TPS("AccWaitCB"));
1669
	else
1670
		trace_rcu_grace_period(rsp->name, rdp->gpnum, TPS("AccReadyCB"));
1671
	return ret;
1672 1673 1674 1675 1676 1677 1678 1679
}

/*
 * Move any callbacks whose grace period has completed to the
 * RCU_DONE_TAIL sublist, then compact the remaining sublists and
 * assign ->completed numbers to any callbacks in the RCU_NEXT_TAIL
 * sublist.  This function is idempotent, so it does not hurt to
 * invoke it repeatedly.  As long as it is not invoked -too- often...
1680
 * Returns true if the RCU grace-period kthread needs to be awakened.
1681 1682 1683
 *
 * The caller must hold rnp->lock with interrupts disabled.
 */
1684
static bool rcu_advance_cbs(struct rcu_state *rsp, struct rcu_node *rnp,
1685 1686 1687 1688 1689 1690
			    struct rcu_data *rdp)
{
	int i, j;

	/* If the CPU has no callbacks, nothing to do. */
	if (!rdp->nxttail[RCU_NEXT_TAIL] || !*rdp->nxttail[RCU_DONE_TAIL])
1691
		return false;
1692 1693 1694 1695 1696 1697 1698 1699 1700 1701 1702 1703 1704 1705 1706 1707 1708 1709 1710 1711 1712 1713 1714

	/*
	 * Find all callbacks whose ->completed numbers indicate that they
	 * are ready to invoke, and put them into the RCU_DONE_TAIL sublist.
	 */
	for (i = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++) {
		if (ULONG_CMP_LT(rnp->completed, rdp->nxtcompleted[i]))
			break;
		rdp->nxttail[RCU_DONE_TAIL] = rdp->nxttail[i];
	}
	/* Clean up any sublist tail pointers that were misordered above. */
	for (j = RCU_WAIT_TAIL; j < i; j++)
		rdp->nxttail[j] = rdp->nxttail[RCU_DONE_TAIL];

	/* Copy down callbacks to fill in empty sublists. */
	for (j = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++, j++) {
		if (rdp->nxttail[j] == rdp->nxttail[RCU_NEXT_TAIL])
			break;
		rdp->nxttail[j] = rdp->nxttail[i];
		rdp->nxtcompleted[j] = rdp->nxtcompleted[i];
	}

	/* Classify any remaining callbacks. */
1715
	return rcu_accelerate_cbs(rsp, rnp, rdp);
1716 1717
}

1718
/*
1719 1720 1721
 * Update CPU-local rcu_data state to record the beginnings and ends of
 * grace periods.  The caller must hold the ->lock of the leaf rcu_node
 * structure corresponding to the current CPU, and must have irqs disabled.
1722
 * Returns true if the grace-period kthread needs to be awakened.
1723
 */
1724 1725
static bool __note_gp_changes(struct rcu_state *rsp, struct rcu_node *rnp,
			      struct rcu_data *rdp)
1726
{
1727 1728
	bool ret;

1729
	/* Handle the ends of any preceding grace periods first. */
1730
	if (rdp->completed == rnp->completed &&
1731
	    !unlikely(READ_ONCE(rdp->gpwrap))) {
1732

1733
		/* No grace period end, so just accelerate recent callbacks. */
1734
		ret = rcu_accelerate_cbs(rsp, rnp, rdp);
1735

1736 1737 1738
	} else {

		/* Advance callbacks. */
1739
		ret = rcu_advance_cbs(rsp, rnp, rdp);
1740 1741 1742

		/* Remember that we saw this grace-period completion. */
		rdp->completed = rnp->completed;
1743
		trace_rcu_grace_period(rsp->name, rdp->gpnum, TPS("cpuend"));
1744
	}
1745

1746
	if (rdp->gpnum != rnp->gpnum || unlikely(READ_ONCE(rdp->gpwrap))) {
1747 1748 1749 1750 1751 1752
		/*
		 * If the current grace period is waiting for this CPU,
		 * set up to detect a quiescent state, otherwise don't
		 * go looking for one.
		 */
		rdp->gpnum = rnp->gpnum;
1753
		trace_rcu_grace_period(rsp->name, rdp->gpnum, TPS("cpustart"));
1754
		rdp->cpu_no_qs.b.norm = true;
1755
		rdp->rcu_qs_ctr_snap = __this_cpu_read(rcu_qs_ctr);
1756
		rdp->core_needs_qs = !!(rnp->qsmask & rdp->grpmask);
1757
		zero_cpu_stall_ticks(rdp);
1758
		WRITE_ONCE(rdp->gpwrap, false);
1759
	}
1760
	return ret;
1761 1762
}

1763
static void note_gp_changes(struct rcu_state *rsp, struct rcu_data *rdp)
1764 1765
{
	unsigned long flags;
1766
	bool needwake;
1767 1768 1769 1770
	struct rcu_node *rnp;

	local_irq_save(flags);
	rnp = rdp->mynode;
1771 1772 1773
	if ((rdp->gpnum == READ_ONCE(rnp->gpnum) &&
	     rdp->completed == READ_ONCE(rnp->completed) &&
	     !unlikely(READ_ONCE(rdp->gpwrap))) || /* w/out lock. */
1774 1775 1776 1777
	    !raw_spin_trylock(&rnp->lock)) { /* irqs already off, so later. */
		local_irq_restore(flags);
		return;
	}
1778
	smp_mb__after_unlock_lock();
1779
	needwake = __note_gp_changes(rsp, rnp, rdp);
1780
	raw_spin_unlock_irqrestore(&rnp->lock, flags);
1781 1782
	if (needwake)
		rcu_gp_kthread_wake(rsp);
1783 1784
}

1785 1786 1787 1788 1789 1790 1791
static void rcu_gp_slow(struct rcu_state *rsp, int delay)
{
	if (delay > 0 &&
	    !(rsp->gpnum % (rcu_num_nodes * PER_RCU_NODE_PERIOD * delay)))
		schedule_timeout_uninterruptible(delay);
}

1792
/*
1793
 * Initialize a new grace period.  Return 0 if no grace period required.
1794
 */
1795
static int rcu_gp_init(struct rcu_state *rsp)
1796
{
1797
	unsigned long oldmask;
1798
	struct rcu_data *rdp;
1799
	struct rcu_node *rnp = rcu_get_root(rsp);
1800

1801
	WRITE_ONCE(rsp->gp_activity, jiffies);
1802
	raw_spin_lock_irq(&rnp->lock);
1803
	smp_mb__after_unlock_lock();
1804
	if (!READ_ONCE(rsp->gp_flags)) {
1805 1806 1807 1808
		/* Spurious wakeup, tell caller to go back to sleep.  */
		raw_spin_unlock_irq(&rnp->lock);
		return 0;
	}
1809
	WRITE_ONCE(rsp->gp_flags, 0); /* Clear all flags: New grace period. */
1810

1811 1812 1813 1814 1815
	if (WARN_ON_ONCE(rcu_gp_in_progress(rsp))) {
		/*
		 * Grace period already in progress, don't start another.
		 * Not supposed to be able to happen.
		 */
1816 1817 1818 1819 1820
		raw_spin_unlock_irq(&rnp->lock);
		return 0;
	}

	/* Advance to a new grace period and initialize state. */
1821
	record_gp_stall_check_time(rsp);
1822 1823
	/* Record GP times before starting GP, hence smp_store_release(). */
	smp_store_release(&rsp->gpnum, rsp->gpnum + 1);
1824
	trace_rcu_grace_period(rsp->name, rsp->gpnum, TPS("start"));
1825 1826
	raw_spin_unlock_irq(&rnp->lock);

1827 1828 1829 1830 1831 1832 1833
	/*
	 * Apply per-leaf buffered online and offline operations to the
	 * rcu_node tree.  Note that this new grace period need not wait
	 * for subsequent online CPUs, and that quiescent-state forcing
	 * will handle subsequent offline CPUs.
	 */
	rcu_for_each_leaf_node(rsp, rnp) {
1834
		rcu_gp_slow(rsp, gp_preinit_delay);
1835 1836 1837 1838 1839 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875
		raw_spin_lock_irq(&rnp->lock);
		smp_mb__after_unlock_lock();
		if (rnp->qsmaskinit == rnp->qsmaskinitnext &&
		    !rnp->wait_blkd_tasks) {
			/* Nothing to do on this leaf rcu_node structure. */
			raw_spin_unlock_irq(&rnp->lock);
			continue;
		}

		/* Record old state, apply changes to ->qsmaskinit field. */
		oldmask = rnp->qsmaskinit;
		rnp->qsmaskinit = rnp->qsmaskinitnext;

		/* If zero-ness of ->qsmaskinit changed, propagate up tree. */
		if (!oldmask != !rnp->qsmaskinit) {
			if (!oldmask) /* First online CPU for this rcu_node. */
				rcu_init_new_rnp(rnp);
			else if (rcu_preempt_has_tasks(rnp)) /* blocked tasks */
				rnp->wait_blkd_tasks = true;
			else /* Last offline CPU and can propagate. */
				rcu_cleanup_dead_rnp(rnp);
		}

		/*
		 * If all waited-on tasks from prior grace period are
		 * done, and if all this rcu_node structure's CPUs are
		 * still offline, propagate up the rcu_node tree and
		 * clear ->wait_blkd_tasks.  Otherwise, if one of this
		 * rcu_node structure's CPUs has since come back online,
		 * simply clear ->wait_blkd_tasks (but rcu_cleanup_dead_rnp()
		 * checks for this, so just call it unconditionally).
		 */
		if (rnp->wait_blkd_tasks &&
		    (!rcu_preempt_has_tasks(rnp) ||
		     rnp->qsmaskinit)) {
			rnp->wait_blkd_tasks = false;
			rcu_cleanup_dead_rnp(rnp);
		}

		raw_spin_unlock_irq(&rnp->lock);
	}
1876 1877 1878 1879 1880 1881 1882 1883 1884 1885 1886 1887 1888 1889 1890

	/*
	 * Set the quiescent-state-needed bits in all the rcu_node
	 * structures for all currently online CPUs in breadth-first order,
	 * starting from the root rcu_node structure, relying on the layout
	 * of the tree within the rsp->node[] array.  Note that other CPUs
	 * will access only the leaves of the hierarchy, thus seeing that no
	 * grace period is in progress, at least until the corresponding
	 * leaf node has been initialized.  In addition, we have excluded
	 * CPU-hotplug operations.
	 *
	 * The grace period cannot complete until the initialization
	 * process finishes, because this kthread handles both.
	 */
	rcu_for_each_node_breadth_first(rsp, rnp) {
1891
		rcu_gp_slow(rsp, gp_init_delay);
1892
		raw_spin_lock_irq(&rnp->lock);
1893
		smp_mb__after_unlock_lock();
1894
		rdp = this_cpu_ptr(rsp->rda);
1895 1896
		rcu_preempt_check_blocked_tasks(rnp);
		rnp->qsmask = rnp->qsmaskinit;
1897
		WRITE_ONCE(rnp->gpnum, rsp->gpnum);
1898
		if (WARN_ON_ONCE(rnp->completed != rsp->completed))
1899
			WRITE_ONCE(rnp->completed, rsp->completed);
1900
		if (rnp == rdp->mynode)
1901
			(void)__note_gp_changes(rsp, rnp, rdp);
1902 1903 1904 1905 1906
		rcu_preempt_boost_start_gp(rnp);
		trace_rcu_grace_period_init(rsp->name, rnp->gpnum,
					    rnp->level, rnp->grplo,
					    rnp->grphi, rnp->qsmask);
		raw_spin_unlock_irq(&rnp->lock);
1907
		cond_resched_rcu_qs();
1908
		WRITE_ONCE(rsp->gp_activity, jiffies);
1909
	}
1910

1911 1912
	return 1;
}
1913

1914 1915 1916 1917 1918 1919 1920 1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 1931 1932 1933
/*
 * Helper function for wait_event_interruptible_timeout() wakeup
 * at force-quiescent-state time.
 */
static bool rcu_gp_fqs_check_wake(struct rcu_state *rsp, int *gfp)
{
	struct rcu_node *rnp = rcu_get_root(rsp);

	/* Someone like call_rcu() requested a force-quiescent-state scan. */
	*gfp = READ_ONCE(rsp->gp_flags);
	if (*gfp & RCU_GP_FLAG_FQS)
		return true;

	/* The current grace period has completed. */
	if (!READ_ONCE(rnp->qsmask) && !rcu_preempt_blocked_readers_cgp(rnp))
		return true;

	return false;
}

1934 1935 1936
/*
 * Do one round of quiescent-state forcing.
 */
1937
static int rcu_gp_fqs(struct rcu_state *rsp, int fqs_state_in)
1938 1939
{
	int fqs_state = fqs_state_in;
1940 1941
	bool isidle = false;
	unsigned long maxj;
1942 1943
	struct rcu_node *rnp = rcu_get_root(rsp);

1944
	WRITE_ONCE(rsp->gp_activity, jiffies);
1945 1946 1947
	rsp->n_force_qs++;
	if (fqs_state == RCU_SAVE_DYNTICK) {
		/* Collect dyntick-idle snapshots. */
1948
		if (is_sysidle_rcu_state(rsp)) {
1949
			isidle = true;
1950 1951
			maxj = jiffies - ULONG_MAX / 4;
		}
1952 1953
		force_qs_rnp(rsp, dyntick_save_progress_counter,
			     &isidle, &maxj);
1954
		rcu_sysidle_report_gp(rsp, isidle, maxj);
1955 1956 1957
		fqs_state = RCU_FORCE_QS;
	} else {
		/* Handle dyntick-idle and offline CPUs. */
1958
		isidle = true;
1959
		force_qs_rnp(rsp, rcu_implicit_dynticks_qs, &isidle, &maxj);
1960 1961
	}
	/* Clear flag to prevent immediate re-entry. */
1962
	if (READ_ONCE(rsp->gp_flags) & RCU_GP_FLAG_FQS) {
1963
		raw_spin_lock_irq(&rnp->lock);
1964
		smp_mb__after_unlock_lock();
1965 1966
		WRITE_ONCE(rsp->gp_flags,
			   READ_ONCE(rsp->gp_flags) & ~RCU_GP_FLAG_FQS);
1967 1968 1969 1970 1971
		raw_spin_unlock_irq(&rnp->lock);
	}
	return fqs_state;
}

1972 1973 1974
/*
 * Clean up after the old grace period.
 */
1975
static void rcu_gp_cleanup(struct rcu_state *rsp)
1976 1977
{
	unsigned long gp_duration;
1978
	bool needgp = false;
1979
	int nocb = 0;
1980 1981
	struct rcu_data *rdp;
	struct rcu_node *rnp = rcu_get_root(rsp);
1982

1983
	WRITE_ONCE(rsp->gp_activity, jiffies);
1984
	raw_spin_lock_irq(&rnp->lock);
1985
	smp_mb__after_unlock_lock();
1986 1987 1988
	gp_duration = jiffies - rsp->gp_start;
	if (gp_duration > rsp->gp_max)
		rsp->gp_max = gp_duration;
1989

1990 1991 1992 1993 1994 1995 1996 1997
	/*
	 * We know the grace period is complete, but to everyone else
	 * it appears to still be ongoing.  But it is also the case
	 * that to everyone else it looks like there is nothing that
	 * they can do to advance the grace period.  It is therefore
	 * safe for us to drop the lock in order to mark the grace
	 * period as completed in all of the rcu_node structures.
	 */
1998
	raw_spin_unlock_irq(&rnp->lock);
1999

2000 2001 2002 2003 2004 2005 2006 2007 2008 2009
	/*
	 * Propagate new ->completed value to rcu_node structures so
	 * that other CPUs don't have to wait until the start of the next
	 * grace period to process their callbacks.  This also avoids
	 * some nasty RCU grace-period initialization races by forcing
	 * the end of the current grace period to be completely recorded in
	 * all of the rcu_node structures before the beginning of the next
	 * grace period is recorded in any of the rcu_node structures.
	 */
	rcu_for_each_node_breadth_first(rsp, rnp) {
2010
		raw_spin_lock_irq(&rnp->lock);
2011
		smp_mb__after_unlock_lock();
2012 2013
		WARN_ON_ONCE(rcu_preempt_blocked_readers_cgp(rnp));
		WARN_ON_ONCE(rnp->qsmask);
2014
		WRITE_ONCE(rnp->completed, rsp->gpnum);
2015 2016
		rdp = this_cpu_ptr(rsp->rda);
		if (rnp == rdp->mynode)
2017
			needgp = __note_gp_changes(rsp, rnp, rdp) || needgp;
2018
		/* smp_mb() provided by prior unlock-lock pair. */
2019
		nocb += rcu_future_gp_cleanup(rsp, rnp);
2020
		raw_spin_unlock_irq(&rnp->lock);
2021
		cond_resched_rcu_qs();
2022
		WRITE_ONCE(rsp->gp_activity, jiffies);
2023
		rcu_gp_slow(rsp, gp_cleanup_delay);
2024
	}
2025 2026
	rnp = rcu_get_root(rsp);
	raw_spin_lock_irq(&rnp->lock);
2027
	smp_mb__after_unlock_lock(); /* Order GP before ->completed update. */
2028
	rcu_nocb_gp_set(rnp, nocb);
2029

2030
	/* Declare grace period done. */
2031
	WRITE_ONCE(rsp->completed, rsp->gpnum);
2032
	trace_rcu_grace_period(rsp->name, rsp->completed, TPS("end"));
2033
	rsp->fqs_state = RCU_GP_IDLE;
2034
	rdp = this_cpu_ptr(rsp->rda);
2035 2036 2037
	/* Advance CBs to reduce false positives below. */
	needgp = rcu_advance_cbs(rsp, rnp, rdp) || needgp;
	if (needgp || cpu_needs_another_gp(rsp, rdp)) {
2038
		WRITE_ONCE(rsp->gp_flags, RCU_GP_FLAG_INIT);
2039
		trace_rcu_grace_period(rsp->name,
2040
				       READ_ONCE(rsp->gpnum),
2041 2042
				       TPS("newreq"));
	}
2043 2044 2045 2046 2047 2048 2049 2050
	raw_spin_unlock_irq(&rnp->lock);
}

/*
 * Body of kthread that handles grace periods.
 */
static int __noreturn rcu_gp_kthread(void *arg)
{
2051
	int fqs_state;
2052
	int gf;
2053
	unsigned long j;
2054
	int ret;
2055 2056 2057
	struct rcu_state *rsp = arg;
	struct rcu_node *rnp = rcu_get_root(rsp);

2058
	rcu_bind_gp_kthread();
2059 2060 2061 2062
	for (;;) {

		/* Handle grace-period start. */
		for (;;) {
2063
			trace_rcu_grace_period(rsp->name,
2064
					       READ_ONCE(rsp->gpnum),
2065
					       TPS("reqwait"));
2066
			rsp->gp_state = RCU_GP_WAIT_GPS;
2067
			wait_event_interruptible(rsp->gp_wq,
2068
						 READ_ONCE(rsp->gp_flags) &
2069
						 RCU_GP_FLAG_INIT);
2070
			rsp->gp_state = RCU_GP_DONE_GPS;
2071
			/* Locking provides needed memory barrier. */
2072
			if (rcu_gp_init(rsp))
2073
				break;
2074
			cond_resched_rcu_qs();
2075
			WRITE_ONCE(rsp->gp_activity, jiffies);
2076
			WARN_ON(signal_pending(current));
2077
			trace_rcu_grace_period(rsp->name,
2078
					       READ_ONCE(rsp->gpnum),
2079
					       TPS("reqwaitsig"));
2080
		}
2081

2082 2083
		/* Handle quiescent-state forcing. */
		fqs_state = RCU_SAVE_DYNTICK;
2084 2085 2086 2087 2088
		j = jiffies_till_first_fqs;
		if (j > HZ) {
			j = HZ;
			jiffies_till_first_fqs = HZ;
		}
2089
		ret = 0;
2090
		for (;;) {
2091 2092
			if (!ret)
				rsp->jiffies_force_qs = jiffies + j;
2093
			trace_rcu_grace_period(rsp->name,
2094
					       READ_ONCE(rsp->gpnum),
2095
					       TPS("fqswait"));
2096
			rsp->gp_state = RCU_GP_WAIT_FQS;
2097
			ret = wait_event_interruptible_timeout(rsp->gp_wq,
2098
					rcu_gp_fqs_check_wake(rsp, &gf), j);
2099
			rsp->gp_state = RCU_GP_DOING_FQS;
2100
			/* Locking provides needed memory barriers. */
2101
			/* If grace period done, leave loop. */
2102
			if (!READ_ONCE(rnp->qsmask) &&
2103
			    !rcu_preempt_blocked_readers_cgp(rnp))
2104
				break;
2105
			/* If time for quiescent-state forcing, do it. */
2106 2107
			if (ULONG_CMP_GE(jiffies, rsp->jiffies_force_qs) ||
			    (gf & RCU_GP_FLAG_FQS)) {
2108
				trace_rcu_grace_period(rsp->name,
2109
						       READ_ONCE(rsp->gpnum),
2110
						       TPS("fqsstart"));
2111
				fqs_state = rcu_gp_fqs(rsp, fqs_state);
2112
				trace_rcu_grace_period(rsp->name,
2113
						       READ_ONCE(rsp->gpnum),
2114
						       TPS("fqsend"));
2115
				cond_resched_rcu_qs();
2116
				WRITE_ONCE(rsp->gp_activity, jiffies);
2117 2118
			} else {
				/* Deal with stray signal. */
2119
				cond_resched_rcu_qs();
2120
				WRITE_ONCE(rsp->gp_activity, jiffies);
2121
				WARN_ON(signal_pending(current));
2122
				trace_rcu_grace_period(rsp->name,
2123
						       READ_ONCE(rsp->gpnum),
2124
						       TPS("fqswaitsig"));
2125
			}
2126 2127 2128 2129 2130 2131 2132 2133
			j = jiffies_till_next_fqs;
			if (j > HZ) {
				j = HZ;
				jiffies_till_next_fqs = HZ;
			} else if (j < 1) {
				j = 1;
				jiffies_till_next_fqs = 1;
			}
2134
		}
2135 2136

		/* Handle grace-period end. */
2137
		rsp->gp_state = RCU_GP_CLEANUP;
2138
		rcu_gp_cleanup(rsp);
2139
		rsp->gp_state = RCU_GP_CLEANED;
2140 2141 2142
	}
}

2143 2144 2145
/*
 * Start a new RCU grace period if warranted, re-initializing the hierarchy
 * in preparation for detecting the next grace period.  The caller must hold
2146
 * the root node's ->lock and hard irqs must be disabled.
2147 2148 2149 2150
 *
 * Note that it is legal for a dying CPU (which is marked as offline) to
 * invoke this function.  This can happen when the dying CPU reports its
 * quiescent state.
2151 2152
 *
 * Returns true if the grace-period kthread must be awakened.
2153
 */
2154
static bool
2155 2156
rcu_start_gp_advanced(struct rcu_state *rsp, struct rcu_node *rnp,
		      struct rcu_data *rdp)
2157
{
2158
	if (!rsp->gp_kthread || !cpu_needs_another_gp(rsp, rdp)) {
2159
		/*
2160
		 * Either we have not yet spawned the grace-period
2161 2162
		 * task, this CPU does not need another grace period,
		 * or a grace period is already in progress.
2163
		 * Either way, don't start a new grace period.
2164
		 */
2165
		return false;
2166
	}
2167 2168
	WRITE_ONCE(rsp->gp_flags, RCU_GP_FLAG_INIT);
	trace_rcu_grace_period(rsp->name, READ_ONCE(rsp->gpnum),
2169
			       TPS("newreq"));
2170

2171 2172
	/*
	 * We can't do wakeups while holding the rnp->lock, as that
2173
	 * could cause possible deadlocks with the rq->lock. Defer
2174
	 * the wakeup to our caller.
2175
	 */
2176
	return true;
2177 2178
}

2179 2180 2181 2182 2183 2184
/*
 * Similar to rcu_start_gp_advanced(), but also advance the calling CPU's
 * callbacks.  Note that rcu_start_gp_advanced() cannot do this because it
 * is invoked indirectly from rcu_advance_cbs(), which would result in
 * endless recursion -- or would do so if it wasn't for the self-deadlock
 * that is encountered beforehand.
2185 2186
 *
 * Returns true if the grace-period kthread needs to be awakened.
2187
 */
2188
static bool rcu_start_gp(struct rcu_state *rsp)
2189 2190 2191
{
	struct rcu_data *rdp = this_cpu_ptr(rsp->rda);
	struct rcu_node *rnp = rcu_get_root(rsp);
2192
	bool ret = false;
2193 2194 2195 2196 2197 2198 2199 2200 2201

	/*
	 * If there is no grace period in progress right now, any
	 * callbacks we have up to this point will be satisfied by the
	 * next grace period.  Also, advancing the callbacks reduces the
	 * probability of false positives from cpu_needs_another_gp()
	 * resulting in pointless grace periods.  So, advance callbacks
	 * then start the grace period!
	 */
2202 2203 2204
	ret = rcu_advance_cbs(rsp, rnp, rdp) || ret;
	ret = rcu_start_gp_advanced(rsp, rnp, rdp) || ret;
	return ret;
2205 2206
}

2207
/*
P
Paul E. McKenney 已提交
2208 2209 2210
 * Report a full set of quiescent states to the specified rcu_state
 * data structure.  This involves cleaning up after the prior grace
 * period and letting rcu_start_gp() start up the next grace period
2211 2212
 * if one is needed.  Note that the caller must hold rnp->lock, which
 * is released before return.
2213
 */
P
Paul E. McKenney 已提交
2214
static void rcu_report_qs_rsp(struct rcu_state *rsp, unsigned long flags)
2215
	__releases(rcu_get_root(rsp)->lock)
2216
{
2217
	WARN_ON_ONCE(!rcu_gp_in_progress(rsp));
2218
	WRITE_ONCE(rsp->gp_flags, READ_ONCE(rsp->gp_flags) | RCU_GP_FLAG_FQS);
2219
	raw_spin_unlock_irqrestore(&rcu_get_root(rsp)->lock, flags);
2220
	rcu_gp_kthread_wake(rsp);
2221 2222
}

2223
/*
P
Paul E. McKenney 已提交
2224 2225 2226
 * Similar to rcu_report_qs_rdp(), for which it is a helper function.
 * Allows quiescent states for a group of CPUs to be reported at one go
 * to the specified rcu_node structure, though all the CPUs in the group
2227 2228 2229 2230 2231
 * must be represented by the same rcu_node structure (which need not be a
 * leaf rcu_node structure, though it often will be).  The gps parameter
 * is the grace-period snapshot, which means that the quiescent states
 * are valid only if rnp->gpnum is equal to gps.  That structure's lock
 * must be held upon entry, and it is released before return.
2232 2233
 */
static void
P
Paul E. McKenney 已提交
2234
rcu_report_qs_rnp(unsigned long mask, struct rcu_state *rsp,
2235
		  struct rcu_node *rnp, unsigned long gps, unsigned long flags)
2236 2237
	__releases(rnp->lock)
{
2238
	unsigned long oldmask = 0;
2239 2240
	struct rcu_node *rnp_c;

2241 2242
	/* Walk up the rcu_node hierarchy. */
	for (;;) {
2243
		if (!(rnp->qsmask & mask) || rnp->gpnum != gps) {
2244

2245 2246 2247 2248
			/*
			 * Our bit has already been cleared, or the
			 * relevant grace period is already over, so done.
			 */
P
Paul E. McKenney 已提交
2249
			raw_spin_unlock_irqrestore(&rnp->lock, flags);
2250 2251
			return;
		}
2252
		WARN_ON_ONCE(oldmask); /* Any child must be all zeroed! */
2253
		rnp->qsmask &= ~mask;
2254 2255 2256 2257
		trace_rcu_quiescent_state_report(rsp->name, rnp->gpnum,
						 mask, rnp->qsmask, rnp->level,
						 rnp->grplo, rnp->grphi,
						 !!rnp->gp_tasks);
2258
		if (rnp->qsmask != 0 || rcu_preempt_blocked_readers_cgp(rnp)) {
2259 2260

			/* Other bits still set at this level, so done. */
P
Paul E. McKenney 已提交
2261
			raw_spin_unlock_irqrestore(&rnp->lock, flags);
2262 2263 2264 2265 2266 2267 2268 2269 2270
			return;
		}
		mask = rnp->grpmask;
		if (rnp->parent == NULL) {

			/* No more levels.  Exit loop holding root lock. */

			break;
		}
P
Paul E. McKenney 已提交
2271
		raw_spin_unlock_irqrestore(&rnp->lock, flags);
2272
		rnp_c = rnp;
2273
		rnp = rnp->parent;
P
Paul E. McKenney 已提交
2274
		raw_spin_lock_irqsave(&rnp->lock, flags);
2275
		smp_mb__after_unlock_lock();
2276
		oldmask = rnp_c->qsmask;
2277 2278 2279 2280
	}

	/*
	 * Get here if we are the last CPU to pass through a quiescent
P
Paul E. McKenney 已提交
2281
	 * state for this grace period.  Invoke rcu_report_qs_rsp()
2282
	 * to clean up and start the next grace period if one is needed.
2283
	 */
P
Paul E. McKenney 已提交
2284
	rcu_report_qs_rsp(rsp, flags); /* releases rnp->lock. */
2285 2286
}

2287 2288 2289 2290 2291 2292 2293
/*
 * Record a quiescent state for all tasks that were previously queued
 * on the specified rcu_node structure and that were blocking the current
 * RCU grace period.  The caller must hold the specified rnp->lock with
 * irqs disabled, and this lock is released upon return, but irqs remain
 * disabled.
 */
2294
static void rcu_report_unblock_qs_rnp(struct rcu_state *rsp,
2295 2296 2297
				      struct rcu_node *rnp, unsigned long flags)
	__releases(rnp->lock)
{
2298
	unsigned long gps;
2299 2300 2301
	unsigned long mask;
	struct rcu_node *rnp_p;

2302 2303
	if (rcu_state_p == &rcu_sched_state || rsp != rcu_state_p ||
	    rnp->qsmask != 0 || rcu_preempt_blocked_readers_cgp(rnp)) {
2304 2305 2306 2307 2308 2309 2310
		raw_spin_unlock_irqrestore(&rnp->lock, flags);
		return;  /* Still need more quiescent states! */
	}

	rnp_p = rnp->parent;
	if (rnp_p == NULL) {
		/*
2311 2312
		 * Only one rcu_node structure in the tree, so don't
		 * try to report up to its nonexistent parent!
2313 2314 2315 2316 2317
		 */
		rcu_report_qs_rsp(rsp, flags);
		return;
	}

2318 2319
	/* Report up the rest of the hierarchy, tracking current ->gpnum. */
	gps = rnp->gpnum;
2320 2321 2322 2323
	mask = rnp->grpmask;
	raw_spin_unlock(&rnp->lock);	/* irqs remain disabled. */
	raw_spin_lock(&rnp_p->lock);	/* irqs already disabled. */
	smp_mb__after_unlock_lock();
2324
	rcu_report_qs_rnp(mask, rsp, rnp_p, gps, flags);
2325 2326
}

2327
/*
P
Paul E. McKenney 已提交
2328 2329 2330 2331 2332 2333 2334
 * Record a quiescent state for the specified CPU to that CPU's rcu_data
 * structure.  This must be either called from the specified CPU, or
 * called when the specified CPU is known to be offline (and when it is
 * also known that no other CPU is concurrently trying to help the offline
 * CPU).  The lastcomp argument is used to make sure we are still in the
 * grace period of interest.  We don't want to end the current grace period
 * based on quiescent states detected in an earlier grace period!
2335 2336
 */
static void
2337
rcu_report_qs_rdp(int cpu, struct rcu_state *rsp, struct rcu_data *rdp)
2338 2339 2340
{
	unsigned long flags;
	unsigned long mask;
2341
	bool needwake;
2342 2343 2344
	struct rcu_node *rnp;

	rnp = rdp->mynode;
P
Paul E. McKenney 已提交
2345
	raw_spin_lock_irqsave(&rnp->lock, flags);
2346
	smp_mb__after_unlock_lock();
2347
	if ((rdp->cpu_no_qs.b.norm &&
2348 2349 2350
	     rdp->rcu_qs_ctr_snap == __this_cpu_read(rcu_qs_ctr)) ||
	    rdp->gpnum != rnp->gpnum || rnp->completed == rnp->gpnum ||
	    rdp->gpwrap) {
2351 2352

		/*
2353 2354 2355 2356
		 * The grace period in which this quiescent state was
		 * recorded has ended, so don't report it upwards.
		 * We will instead need a new quiescent state that lies
		 * within the current grace period.
2357
		 */
2358
		rdp->cpu_no_qs.b.norm = true;	/* need qs for new gp. */
2359
		rdp->rcu_qs_ctr_snap = __this_cpu_read(rcu_qs_ctr);
P
Paul E. McKenney 已提交
2360
		raw_spin_unlock_irqrestore(&rnp->lock, flags);
2361 2362 2363 2364
		return;
	}
	mask = rdp->grpmask;
	if ((rnp->qsmask & mask) == 0) {
P
Paul E. McKenney 已提交
2365
		raw_spin_unlock_irqrestore(&rnp->lock, flags);
2366
	} else {
2367
		rdp->core_needs_qs = 0;
2368 2369 2370 2371 2372

		/*
		 * This GP can't end until cpu checks in, so all of our
		 * callbacks can be processed during the next GP.
		 */
2373
		needwake = rcu_accelerate_cbs(rsp, rnp, rdp);
2374

2375 2376
		rcu_report_qs_rnp(mask, rsp, rnp, rnp->gpnum, flags);
		/* ^^^ Released rnp->lock */
2377 2378
		if (needwake)
			rcu_gp_kthread_wake(rsp);
2379 2380 2381 2382 2383 2384 2385 2386 2387 2388 2389 2390
	}
}

/*
 * Check to see if there is a new grace period of which this CPU
 * is not yet aware, and if so, set up local rcu_data state for it.
 * Otherwise, see if this CPU has just passed through its first
 * quiescent state for this grace period, and record that fact if so.
 */
static void
rcu_check_quiescent_state(struct rcu_state *rsp, struct rcu_data *rdp)
{
2391 2392
	/* Check for grace-period ends and beginnings. */
	note_gp_changes(rsp, rdp);
2393 2394 2395 2396 2397

	/*
	 * Does this CPU still need to do its part for current grace period?
	 * If no, return and let the other CPUs do their part as well.
	 */
2398
	if (!rdp->core_needs_qs)
2399 2400 2401 2402 2403 2404
		return;

	/*
	 * Was there a quiescent state since the beginning of the grace
	 * period? If no, then exit and wait for the next call.
	 */
2405
	if (rdp->cpu_no_qs.b.norm &&
2406
	    rdp->rcu_qs_ctr_snap == __this_cpu_read(rcu_qs_ctr))
2407 2408
		return;

P
Paul E. McKenney 已提交
2409 2410 2411 2412
	/*
	 * Tell RCU we are done (but rcu_report_qs_rdp() will be the
	 * judge of that).
	 */
2413
	rcu_report_qs_rdp(rdp->cpu, rsp, rdp);
2414 2415
}

2416
/*
2417 2418
 * Send the specified CPU's RCU callbacks to the orphanage.  The
 * specified CPU must be offline, and the caller must hold the
2419
 * ->orphan_lock.
2420
 */
2421 2422 2423
static void
rcu_send_cbs_to_orphanage(int cpu, struct rcu_state *rsp,
			  struct rcu_node *rnp, struct rcu_data *rdp)
2424
{
P
Paul E. McKenney 已提交
2425
	/* No-CBs CPUs do not have orphanable callbacks. */
2426
	if (!IS_ENABLED(CONFIG_HOTPLUG_CPU) || rcu_is_nocb_cpu(rdp->cpu))
P
Paul E. McKenney 已提交
2427 2428
		return;

2429 2430
	/*
	 * Orphan the callbacks.  First adjust the counts.  This is safe
2431 2432
	 * because _rcu_barrier() excludes CPU-hotplug operations, so it
	 * cannot be running now.  Thus no memory barrier is required.
2433
	 */
2434
	if (rdp->nxtlist != NULL) {
2435 2436 2437
		rsp->qlen_lazy += rdp->qlen_lazy;
		rsp->qlen += rdp->qlen;
		rdp->n_cbs_orphaned += rdp->qlen;
2438
		rdp->qlen_lazy = 0;
2439
		WRITE_ONCE(rdp->qlen, 0);
2440 2441 2442
	}

	/*
2443 2444 2445 2446 2447 2448 2449
	 * Next, move those callbacks still needing a grace period to
	 * the orphanage, where some other CPU will pick them up.
	 * Some of the callbacks might have gone partway through a grace
	 * period, but that is too bad.  They get to start over because we
	 * cannot assume that grace periods are synchronized across CPUs.
	 * We don't bother updating the ->nxttail[] array yet, instead
	 * we just reset the whole thing later on.
2450
	 */
2451 2452 2453 2454
	if (*rdp->nxttail[RCU_DONE_TAIL] != NULL) {
		*rsp->orphan_nxttail = *rdp->nxttail[RCU_DONE_TAIL];
		rsp->orphan_nxttail = rdp->nxttail[RCU_NEXT_TAIL];
		*rdp->nxttail[RCU_DONE_TAIL] = NULL;
2455 2456 2457
	}

	/*
2458 2459 2460
	 * Then move the ready-to-invoke callbacks to the orphanage,
	 * where some other CPU will pick them up.  These will not be
	 * required to pass though another grace period: They are done.
2461
	 */
2462
	if (rdp->nxtlist != NULL) {
2463 2464
		*rsp->orphan_donetail = rdp->nxtlist;
		rsp->orphan_donetail = rdp->nxttail[RCU_DONE_TAIL];
2465
	}
2466

2467 2468 2469 2470
	/*
	 * Finally, initialize the rcu_data structure's list to empty and
	 * disallow further callbacks on this CPU.
	 */
2471
	init_callback_list(rdp);
2472
	rdp->nxttail[RCU_NEXT_TAIL] = NULL;
2473 2474 2475 2476
}

/*
 * Adopt the RCU callbacks from the specified rcu_state structure's
2477
 * orphanage.  The caller must hold the ->orphan_lock.
2478
 */
2479
static void rcu_adopt_orphan_cbs(struct rcu_state *rsp, unsigned long flags)
2480 2481
{
	int i;
2482
	struct rcu_data *rdp = raw_cpu_ptr(rsp->rda);
2483

P
Paul E. McKenney 已提交
2484
	/* No-CBs CPUs are handled specially. */
2485 2486
	if (!IS_ENABLED(CONFIG_HOTPLUG_CPU) ||
	    rcu_nocb_adopt_orphan_cbs(rsp, rdp, flags))
P
Paul E. McKenney 已提交
2487 2488
		return;

2489 2490 2491 2492
	/* Do the accounting first. */
	rdp->qlen_lazy += rsp->qlen_lazy;
	rdp->qlen += rsp->qlen;
	rdp->n_cbs_adopted += rsp->qlen;
2493 2494
	if (rsp->qlen_lazy != rsp->qlen)
		rcu_idle_count_callbacks_posted();
2495 2496 2497 2498 2499 2500 2501 2502 2503 2504 2505 2506 2507 2508 2509 2510 2511 2512 2513 2514 2515 2516 2517 2518 2519 2520 2521 2522 2523 2524 2525 2526 2527 2528 2529 2530 2531 2532
	rsp->qlen_lazy = 0;
	rsp->qlen = 0;

	/*
	 * We do not need a memory barrier here because the only way we
	 * can get here if there is an rcu_barrier() in flight is if
	 * we are the task doing the rcu_barrier().
	 */

	/* First adopt the ready-to-invoke callbacks. */
	if (rsp->orphan_donelist != NULL) {
		*rsp->orphan_donetail = *rdp->nxttail[RCU_DONE_TAIL];
		*rdp->nxttail[RCU_DONE_TAIL] = rsp->orphan_donelist;
		for (i = RCU_NEXT_SIZE - 1; i >= RCU_DONE_TAIL; i--)
			if (rdp->nxttail[i] == rdp->nxttail[RCU_DONE_TAIL])
				rdp->nxttail[i] = rsp->orphan_donetail;
		rsp->orphan_donelist = NULL;
		rsp->orphan_donetail = &rsp->orphan_donelist;
	}

	/* And then adopt the callbacks that still need a grace period. */
	if (rsp->orphan_nxtlist != NULL) {
		*rdp->nxttail[RCU_NEXT_TAIL] = rsp->orphan_nxtlist;
		rdp->nxttail[RCU_NEXT_TAIL] = rsp->orphan_nxttail;
		rsp->orphan_nxtlist = NULL;
		rsp->orphan_nxttail = &rsp->orphan_nxtlist;
	}
}

/*
 * Trace the fact that this CPU is going offline.
 */
static void rcu_cleanup_dying_cpu(struct rcu_state *rsp)
{
	RCU_TRACE(unsigned long mask);
	RCU_TRACE(struct rcu_data *rdp = this_cpu_ptr(rsp->rda));
	RCU_TRACE(struct rcu_node *rnp = rdp->mynode);

2533 2534 2535
	if (!IS_ENABLED(CONFIG_HOTPLUG_CPU))
		return;

2536
	RCU_TRACE(mask = rdp->grpmask);
2537 2538
	trace_rcu_grace_period(rsp->name,
			       rnp->gpnum + 1 - !!(rnp->qsmask & mask),
2539
			       TPS("cpuofl"));
2540 2541
}

2542 2543 2544 2545 2546 2547 2548 2549 2550 2551 2552 2553 2554 2555 2556 2557 2558 2559 2560 2561 2562 2563
/*
 * All CPUs for the specified rcu_node structure have gone offline,
 * and all tasks that were preempted within an RCU read-side critical
 * section while running on one of those CPUs have since exited their RCU
 * read-side critical section.  Some other CPU is reporting this fact with
 * the specified rcu_node structure's ->lock held and interrupts disabled.
 * This function therefore goes up the tree of rcu_node structures,
 * clearing the corresponding bits in the ->qsmaskinit fields.  Note that
 * the leaf rcu_node structure's ->qsmaskinit field has already been
 * updated
 *
 * This function does check that the specified rcu_node structure has
 * all CPUs offline and no blocked tasks, so it is OK to invoke it
 * prematurely.  That said, invoking it after the fact will cost you
 * a needless lock acquisition.  So once it has done its work, don't
 * invoke it again.
 */
static void rcu_cleanup_dead_rnp(struct rcu_node *rnp_leaf)
{
	long mask;
	struct rcu_node *rnp = rnp_leaf;

2564 2565
	if (!IS_ENABLED(CONFIG_HOTPLUG_CPU) ||
	    rnp->qsmaskinit || rcu_preempt_has_tasks(rnp))
2566 2567 2568 2569 2570 2571 2572 2573 2574
		return;
	for (;;) {
		mask = rnp->grpmask;
		rnp = rnp->parent;
		if (!rnp)
			break;
		raw_spin_lock(&rnp->lock); /* irqs already disabled. */
		smp_mb__after_unlock_lock(); /* GP memory ordering. */
		rnp->qsmaskinit &= ~mask;
2575
		rnp->qsmask &= ~mask;
2576 2577 2578 2579 2580 2581 2582 2583
		if (rnp->qsmaskinit) {
			raw_spin_unlock(&rnp->lock); /* irqs remain disabled. */
			return;
		}
		raw_spin_unlock(&rnp->lock); /* irqs remain disabled. */
	}
}

2584 2585 2586 2587 2588 2589 2590 2591 2592 2593 2594 2595
/*
 * The CPU is exiting the idle loop into the arch_cpu_idle_dead()
 * function.  We now remove it from the rcu_node tree's ->qsmaskinit
 * bit masks.
 */
static void rcu_cleanup_dying_idle_cpu(int cpu, struct rcu_state *rsp)
{
	unsigned long flags;
	unsigned long mask;
	struct rcu_data *rdp = per_cpu_ptr(rsp->rda, cpu);
	struct rcu_node *rnp = rdp->mynode;  /* Outgoing CPU's rdp & rnp. */

2596 2597 2598
	if (!IS_ENABLED(CONFIG_HOTPLUG_CPU))
		return;

2599 2600 2601 2602 2603 2604 2605 2606
	/* Remove outgoing CPU from mask in the leaf rcu_node structure. */
	mask = rdp->grpmask;
	raw_spin_lock_irqsave(&rnp->lock, flags);
	smp_mb__after_unlock_lock();	/* Enforce GP memory-order guarantee. */
	rnp->qsmaskinitnext &= ~mask;
	raw_spin_unlock_irqrestore(&rnp->lock, flags);
}

2607
/*
2608
 * The CPU has been completely removed, and some other CPU is reporting
2609 2610
 * this fact from process context.  Do the remainder of the cleanup,
 * including orphaning the outgoing CPU's RCU callbacks, and also
2611 2612
 * adopting them.  There can only be one CPU hotplug operation at a time,
 * so no other CPU can be attempting to update rcu_cpu_kthread_task.
2613
 */
2614
static void rcu_cleanup_dead_cpu(int cpu, struct rcu_state *rsp)
2615
{
2616
	unsigned long flags;
2617
	struct rcu_data *rdp = per_cpu_ptr(rsp->rda, cpu);
2618
	struct rcu_node *rnp = rdp->mynode;  /* Outgoing CPU's rdp & rnp. */
2619

2620 2621 2622
	if (!IS_ENABLED(CONFIG_HOTPLUG_CPU))
		return;

2623
	/* Adjust any no-longer-needed kthreads. */
T
Thomas Gleixner 已提交
2624
	rcu_boost_kthread_setaffinity(rnp, -1);
2625

2626
	/* Orphan the dead CPU's callbacks, and adopt them if appropriate. */
2627
	raw_spin_lock_irqsave(&rsp->orphan_lock, flags);
2628
	rcu_send_cbs_to_orphanage(cpu, rsp, rnp, rdp);
2629
	rcu_adopt_orphan_cbs(rsp, flags);
2630
	raw_spin_unlock_irqrestore(&rsp->orphan_lock, flags);
2631

2632 2633 2634
	WARN_ONCE(rdp->qlen != 0 || rdp->nxtlist != NULL,
		  "rcu_cleanup_dead_cpu: Callbacks on offline CPU %d: qlen=%lu, nxtlist=%p\n",
		  cpu, rdp->qlen, rdp->nxtlist);
2635 2636 2637 2638 2639 2640
}

/*
 * Invoke any RCU callbacks that have made it to the end of their grace
 * period.  Thottle as specified by rdp->blimit.
 */
2641
static void rcu_do_batch(struct rcu_state *rsp, struct rcu_data *rdp)
2642 2643 2644
{
	unsigned long flags;
	struct rcu_head *next, *list, **tail;
E
Eric Dumazet 已提交
2645 2646
	long bl, count, count_lazy;
	int i;
2647

2648
	/* If no callbacks are ready, just return. */
2649
	if (!cpu_has_callbacks_ready_to_invoke(rdp)) {
2650
		trace_rcu_batch_start(rsp->name, rdp->qlen_lazy, rdp->qlen, 0);
2651
		trace_rcu_batch_end(rsp->name, 0, !!READ_ONCE(rdp->nxtlist),
2652 2653
				    need_resched(), is_idle_task(current),
				    rcu_is_callbacks_kthread());
2654
		return;
2655
	}
2656 2657 2658 2659 2660 2661

	/*
	 * Extract the list of ready callbacks, disabling to prevent
	 * races with call_rcu() from interrupt handlers.
	 */
	local_irq_save(flags);
2662
	WARN_ON_ONCE(cpu_is_offline(smp_processor_id()));
2663
	bl = rdp->blimit;
2664
	trace_rcu_batch_start(rsp->name, rdp->qlen_lazy, rdp->qlen, bl);
2665 2666 2667 2668
	list = rdp->nxtlist;
	rdp->nxtlist = *rdp->nxttail[RCU_DONE_TAIL];
	*rdp->nxttail[RCU_DONE_TAIL] = NULL;
	tail = rdp->nxttail[RCU_DONE_TAIL];
2669 2670 2671
	for (i = RCU_NEXT_SIZE - 1; i >= 0; i--)
		if (rdp->nxttail[i] == rdp->nxttail[RCU_DONE_TAIL])
			rdp->nxttail[i] = &rdp->nxtlist;
2672 2673 2674
	local_irq_restore(flags);

	/* Invoke callbacks. */
2675
	count = count_lazy = 0;
2676 2677 2678
	while (list) {
		next = list->next;
		prefetch(next);
2679
		debug_rcu_head_unqueue(list);
2680 2681
		if (__rcu_reclaim(rsp->name, list))
			count_lazy++;
2682
		list = next;
2683 2684 2685 2686
		/* Stop only if limit reached and CPU has something to do. */
		if (++count >= bl &&
		    (need_resched() ||
		     (!is_idle_task(current) && !rcu_is_callbacks_kthread())))
2687 2688 2689 2690
			break;
	}

	local_irq_save(flags);
2691 2692 2693
	trace_rcu_batch_end(rsp->name, count, !!list, need_resched(),
			    is_idle_task(current),
			    rcu_is_callbacks_kthread());
2694 2695 2696 2697 2698

	/* Update count, and requeue any remaining callbacks. */
	if (list != NULL) {
		*tail = rdp->nxtlist;
		rdp->nxtlist = list;
2699 2700 2701
		for (i = 0; i < RCU_NEXT_SIZE; i++)
			if (&rdp->nxtlist == rdp->nxttail[i])
				rdp->nxttail[i] = tail;
2702 2703 2704
			else
				break;
	}
2705 2706
	smp_mb(); /* List handling before counting for rcu_barrier(). */
	rdp->qlen_lazy -= count_lazy;
2707
	WRITE_ONCE(rdp->qlen, rdp->qlen - count);
2708
	rdp->n_cbs_invoked += count;
2709 2710 2711 2712 2713

	/* Reinstate batch limit if we have worked down the excess. */
	if (rdp->blimit == LONG_MAX && rdp->qlen <= qlowmark)
		rdp->blimit = blimit;

2714 2715 2716 2717 2718 2719
	/* Reset ->qlen_last_fqs_check trigger if enough CBs have drained. */
	if (rdp->qlen == 0 && rdp->qlen_last_fqs_check != 0) {
		rdp->qlen_last_fqs_check = 0;
		rdp->n_force_qs_snap = rsp->n_force_qs;
	} else if (rdp->qlen < rdp->qlen_last_fqs_check - qhimark)
		rdp->qlen_last_fqs_check = rdp->qlen;
2720
	WARN_ON_ONCE((rdp->nxtlist == NULL) != (rdp->qlen == 0));
2721

2722 2723
	local_irq_restore(flags);

2724
	/* Re-invoke RCU core processing if there are callbacks remaining. */
2725
	if (cpu_has_callbacks_ready_to_invoke(rdp))
2726
		invoke_rcu_core();
2727 2728 2729 2730 2731
}

/*
 * Check to see if this CPU is in a non-context-switch quiescent state
 * (user mode or idle loop for rcu, non-softirq execution for rcu_bh).
2732
 * Also schedule RCU core processing.
2733
 *
2734
 * This function must be called from hardirq context.  It is normally
2735 2736 2737
 * invoked from the scheduling-clock interrupt.  If rcu_pending returns
 * false, there is no point in invoking rcu_check_callbacks().
 */
2738
void rcu_check_callbacks(int user)
2739
{
2740
	trace_rcu_utilization(TPS("Start scheduler-tick"));
2741
	increment_cpu_stall_ticks();
2742
	if (user || rcu_is_cpu_rrupt_from_idle()) {
2743 2744 2745 2746 2747

		/*
		 * Get here if this CPU took its interrupt from user
		 * mode or from the idle loop, and if this is not a
		 * nested interrupt.  In this case, the CPU is in
2748
		 * a quiescent state, so note it.
2749 2750
		 *
		 * No memory barrier is required here because both
2751 2752 2753
		 * rcu_sched_qs() and rcu_bh_qs() reference only CPU-local
		 * variables that other CPUs neither access nor modify,
		 * at least not while the corresponding CPU is online.
2754 2755
		 */

2756 2757
		rcu_sched_qs();
		rcu_bh_qs();
2758 2759 2760 2761 2762 2763 2764

	} else if (!in_softirq()) {

		/*
		 * Get here if this CPU did not take its interrupt from
		 * softirq, in other words, if it is not interrupting
		 * a rcu_bh read-side critical section.  This is an _bh
2765
		 * critical section, so note it.
2766 2767
		 */

2768
		rcu_bh_qs();
2769
	}
2770
	rcu_preempt_check_callbacks();
2771
	if (rcu_pending())
2772
		invoke_rcu_core();
P
Paul E. McKenney 已提交
2773 2774
	if (user)
		rcu_note_voluntary_context_switch(current);
2775
	trace_rcu_utilization(TPS("End scheduler-tick"));
2776 2777 2778 2779 2780
}

/*
 * Scan the leaf rcu_node structures, processing dyntick state for any that
 * have not yet encountered a quiescent state, using the function specified.
2781 2782
 * Also initiate boosting for any threads blocked on the root rcu_node.
 *
2783
 * The caller must have suppressed start of new grace periods.
2784
 */
2785 2786 2787 2788
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)
2789 2790 2791 2792 2793
{
	unsigned long bit;
	int cpu;
	unsigned long flags;
	unsigned long mask;
2794
	struct rcu_node *rnp;
2795

2796
	rcu_for_each_leaf_node(rsp, rnp) {
2797
		cond_resched_rcu_qs();
2798
		mask = 0;
P
Paul E. McKenney 已提交
2799
		raw_spin_lock_irqsave(&rnp->lock, flags);
2800
		smp_mb__after_unlock_lock();
2801
		if (rnp->qsmask == 0) {
2802 2803 2804 2805 2806 2807 2808 2809 2810 2811 2812 2813 2814 2815 2816 2817 2818 2819 2820 2821 2822 2823 2824
			if (rcu_state_p == &rcu_sched_state ||
			    rsp != rcu_state_p ||
			    rcu_preempt_blocked_readers_cgp(rnp)) {
				/*
				 * No point in scanning bits because they
				 * are all zero.  But we might need to
				 * priority-boost blocked readers.
				 */
				rcu_initiate_boost(rnp, flags);
				/* rcu_initiate_boost() releases rnp->lock */
				continue;
			}
			if (rnp->parent &&
			    (rnp->parent->qsmask & rnp->grpmask)) {
				/*
				 * Race between grace-period
				 * initialization and task exiting RCU
				 * read-side critical section: Report.
				 */
				rcu_report_unblock_qs_rnp(rsp, rnp, flags);
				/* rcu_report_unblock_qs_rnp() rlses ->lock */
				continue;
			}
2825
		}
2826
		cpu = rnp->grplo;
2827
		bit = 1;
2828
		for (; cpu <= rnp->grphi; cpu++, bit <<= 1) {
2829 2830 2831 2832
			if ((rnp->qsmask & bit) != 0) {
				if (f(per_cpu_ptr(rsp->rda, cpu), isidle, maxj))
					mask |= bit;
			}
2833
		}
2834
		if (mask != 0) {
2835 2836
			/* Idle/offline CPUs, report (releases rnp->lock. */
			rcu_report_qs_rnp(mask, rsp, rnp, rnp->gpnum, flags);
2837 2838 2839
		} else {
			/* Nothing to do here, so just drop the lock. */
			raw_spin_unlock_irqrestore(&rnp->lock, flags);
2840 2841 2842 2843 2844 2845 2846 2847
		}
	}
}

/*
 * Force quiescent states on reluctant CPUs, and also detect which
 * CPUs are in dyntick-idle mode.
 */
2848
static void force_quiescent_state(struct rcu_state *rsp)
2849 2850
{
	unsigned long flags;
2851 2852 2853 2854 2855
	bool ret;
	struct rcu_node *rnp;
	struct rcu_node *rnp_old = NULL;

	/* Funnel through hierarchy to reduce memory contention. */
2856
	rnp = __this_cpu_read(rsp->rda->mynode);
2857
	for (; rnp != NULL; rnp = rnp->parent) {
2858
		ret = (READ_ONCE(rsp->gp_flags) & RCU_GP_FLAG_FQS) ||
2859 2860 2861 2862
		      !raw_spin_trylock(&rnp->fqslock);
		if (rnp_old != NULL)
			raw_spin_unlock(&rnp_old->fqslock);
		if (ret) {
2863
			rsp->n_force_qs_lh++;
2864 2865 2866 2867 2868
			return;
		}
		rnp_old = rnp;
	}
	/* rnp_old == rcu_get_root(rsp), rnp == NULL. */
2869

2870 2871
	/* Reached the root of the rcu_node tree, acquire lock. */
	raw_spin_lock_irqsave(&rnp_old->lock, flags);
2872
	smp_mb__after_unlock_lock();
2873
	raw_spin_unlock(&rnp_old->fqslock);
2874
	if (READ_ONCE(rsp->gp_flags) & RCU_GP_FLAG_FQS) {
2875
		rsp->n_force_qs_lh++;
2876
		raw_spin_unlock_irqrestore(&rnp_old->lock, flags);
2877
		return;  /* Someone beat us to it. */
2878
	}
2879
	WRITE_ONCE(rsp->gp_flags, READ_ONCE(rsp->gp_flags) | RCU_GP_FLAG_FQS);
2880
	raw_spin_unlock_irqrestore(&rnp_old->lock, flags);
2881
	rcu_gp_kthread_wake(rsp);
2882 2883 2884
}

/*
2885 2886 2887
 * This does the RCU core processing work for the specified rcu_state
 * and rcu_data structures.  This may be called only from the CPU to
 * whom the rdp belongs.
2888 2889
 */
static void
2890
__rcu_process_callbacks(struct rcu_state *rsp)
2891 2892
{
	unsigned long flags;
2893
	bool needwake;
2894
	struct rcu_data *rdp = raw_cpu_ptr(rsp->rda);
2895

2896 2897
	WARN_ON_ONCE(rdp->beenonline == 0);

2898 2899 2900 2901
	/* Update RCU state based on any recent quiescent states. */
	rcu_check_quiescent_state(rsp, rdp);

	/* Does this CPU require a not-yet-started grace period? */
2902
	local_irq_save(flags);
2903
	if (cpu_needs_another_gp(rsp, rdp)) {
2904
		raw_spin_lock(&rcu_get_root(rsp)->lock); /* irqs disabled. */
2905
		needwake = rcu_start_gp(rsp);
2906
		raw_spin_unlock_irqrestore(&rcu_get_root(rsp)->lock, flags);
2907 2908
		if (needwake)
			rcu_gp_kthread_wake(rsp);
2909 2910
	} else {
		local_irq_restore(flags);
2911 2912 2913
	}

	/* If there are callbacks ready, invoke them. */
2914
	if (cpu_has_callbacks_ready_to_invoke(rdp))
2915
		invoke_rcu_callbacks(rsp, rdp);
2916 2917 2918

	/* Do any needed deferred wakeups of rcuo kthreads. */
	do_nocb_deferred_wakeup(rdp);
2919 2920
}

2921
/*
2922
 * Do RCU core processing for the current CPU.
2923
 */
2924
static void rcu_process_callbacks(struct softirq_action *unused)
2925
{
2926 2927
	struct rcu_state *rsp;

2928 2929
	if (cpu_is_offline(smp_processor_id()))
		return;
2930
	trace_rcu_utilization(TPS("Start RCU core"));
2931 2932
	for_each_rcu_flavor(rsp)
		__rcu_process_callbacks(rsp);
2933
	trace_rcu_utilization(TPS("End RCU core"));
2934 2935
}

2936
/*
2937 2938 2939
 * Schedule RCU callback invocation.  If the specified type of RCU
 * does not support RCU priority boosting, just do a direct call,
 * otherwise wake up the per-CPU kernel kthread.  Note that because we
2940
 * are running on the current CPU with softirqs disabled, the
2941
 * rcu_cpu_kthread_task cannot disappear out from under us.
2942
 */
2943
static void invoke_rcu_callbacks(struct rcu_state *rsp, struct rcu_data *rdp)
2944
{
2945
	if (unlikely(!READ_ONCE(rcu_scheduler_fully_active)))
2946
		return;
2947 2948
	if (likely(!rsp->boost)) {
		rcu_do_batch(rsp, rdp);
2949 2950
		return;
	}
2951
	invoke_rcu_callbacks_kthread();
2952 2953
}

2954
static void invoke_rcu_core(void)
2955
{
2956 2957
	if (cpu_online(smp_processor_id()))
		raise_softirq(RCU_SOFTIRQ);
2958 2959
}

2960 2961 2962 2963 2964
/*
 * Handle any core-RCU processing required by a call_rcu() invocation.
 */
static void __call_rcu_core(struct rcu_state *rsp, struct rcu_data *rdp,
			    struct rcu_head *head, unsigned long flags)
2965
{
2966 2967
	bool needwake;

2968 2969 2970 2971
	/*
	 * If called from an extended quiescent state, invoke the RCU
	 * core in order to force a re-evaluation of RCU's idleness.
	 */
2972
	if (!rcu_is_watching())
2973 2974
		invoke_rcu_core();

2975
	/* If interrupts were disabled or CPU offline, don't invoke RCU core. */
2976
	if (irqs_disabled_flags(flags) || cpu_is_offline(smp_processor_id()))
2977
		return;
2978

2979 2980 2981 2982 2983 2984 2985
	/*
	 * Force the grace period if too many callbacks or too long waiting.
	 * Enforce hysteresis, and don't invoke force_quiescent_state()
	 * if some other CPU has recently done so.  Also, don't bother
	 * invoking force_quiescent_state() if the newly enqueued callback
	 * is the only one waiting for a grace period to complete.
	 */
2986
	if (unlikely(rdp->qlen > rdp->qlen_last_fqs_check + qhimark)) {
2987 2988

		/* Are we ignoring a completed grace period? */
2989
		note_gp_changes(rsp, rdp);
2990 2991 2992 2993 2994

		/* Start a new grace period if one not already started. */
		if (!rcu_gp_in_progress(rsp)) {
			struct rcu_node *rnp_root = rcu_get_root(rsp);

2995
			raw_spin_lock(&rnp_root->lock);
2996
			smp_mb__after_unlock_lock();
2997
			needwake = rcu_start_gp(rsp);
2998
			raw_spin_unlock(&rnp_root->lock);
2999 3000
			if (needwake)
				rcu_gp_kthread_wake(rsp);
3001 3002 3003 3004 3005
		} else {
			/* Give the grace period a kick. */
			rdp->blimit = LONG_MAX;
			if (rsp->n_force_qs == rdp->n_force_qs_snap &&
			    *rdp->nxttail[RCU_DONE_TAIL] != head)
3006
				force_quiescent_state(rsp);
3007 3008 3009
			rdp->n_force_qs_snap = rsp->n_force_qs;
			rdp->qlen_last_fqs_check = rdp->qlen;
		}
3010
	}
3011 3012
}

3013 3014 3015 3016 3017 3018 3019
/*
 * RCU callback function to leak a callback.
 */
static void rcu_leak_callback(struct rcu_head *rhp)
{
}

P
Paul E. McKenney 已提交
3020 3021 3022 3023 3024 3025
/*
 * Helper function for call_rcu() and friends.  The cpu argument will
 * normally be -1, indicating "currently running CPU".  It may specify
 * a CPU only if that CPU is a no-CBs CPU.  Currently, only _rcu_barrier()
 * is expected to specify a CPU.
 */
3026 3027
static void
__call_rcu(struct rcu_head *head, void (*func)(struct rcu_head *rcu),
P
Paul E. McKenney 已提交
3028
	   struct rcu_state *rsp, int cpu, bool lazy)
3029 3030 3031 3032
{
	unsigned long flags;
	struct rcu_data *rdp;

3033
	WARN_ON_ONCE((unsigned long)head & 0x1); /* Misaligned rcu_head! */
3034 3035
	if (debug_rcu_head_queue(head)) {
		/* Probable double call_rcu(), so leak the callback. */
3036
		WRITE_ONCE(head->func, rcu_leak_callback);
3037 3038 3039
		WARN_ONCE(1, "__call_rcu(): Leaked duplicate callback\n");
		return;
	}
3040 3041 3042 3043 3044 3045 3046 3047 3048 3049
	head->func = func;
	head->next = NULL;

	/*
	 * Opportunistically note grace-period endings and beginnings.
	 * Note that we might see a beginning right after we see an
	 * end, but never vice versa, since this CPU has to pass through
	 * a quiescent state betweentimes.
	 */
	local_irq_save(flags);
3050
	rdp = this_cpu_ptr(rsp->rda);
3051 3052

	/* Add the callback to our list. */
P
Paul E. McKenney 已提交
3053 3054 3055 3056 3057
	if (unlikely(rdp->nxttail[RCU_NEXT_TAIL] == NULL) || cpu != -1) {
		int offline;

		if (cpu != -1)
			rdp = per_cpu_ptr(rsp->rda, cpu);
3058 3059 3060 3061 3062 3063 3064 3065 3066 3067 3068 3069 3070
		if (likely(rdp->mynode)) {
			/* Post-boot, so this should be for a no-CBs CPU. */
			offline = !__call_rcu_nocb(rdp, head, lazy, flags);
			WARN_ON_ONCE(offline);
			/* Offline CPU, _call_rcu() illegal, leak callback.  */
			local_irq_restore(flags);
			return;
		}
		/*
		 * Very early boot, before rcu_init().  Initialize if needed
		 * and then drop through to queue the callback.
		 */
		BUG_ON(cpu != -1);
3071
		WARN_ON_ONCE(!rcu_is_watching());
3072 3073
		if (!likely(rdp->nxtlist))
			init_default_callback_list(rdp);
3074
	}
3075
	WRITE_ONCE(rdp->qlen, rdp->qlen + 1);
3076 3077
	if (lazy)
		rdp->qlen_lazy++;
3078 3079
	else
		rcu_idle_count_callbacks_posted();
3080 3081 3082
	smp_mb();  /* Count before adding callback for rcu_barrier(). */
	*rdp->nxttail[RCU_NEXT_TAIL] = head;
	rdp->nxttail[RCU_NEXT_TAIL] = &head->next;
3083

3084 3085
	if (__is_kfree_rcu_offset((unsigned long)func))
		trace_rcu_kfree_callback(rsp->name, head, (unsigned long)func,
3086
					 rdp->qlen_lazy, rdp->qlen);
3087
	else
3088
		trace_rcu_callback(rsp->name, head, rdp->qlen_lazy, rdp->qlen);
3089

3090 3091
	/* Go handle any RCU core processing required. */
	__call_rcu_core(rsp, rdp, head, flags);
3092 3093 3094 3095
	local_irq_restore(flags);
}

/*
3096
 * Queue an RCU-sched callback for invocation after a grace period.
3097
 */
3098
void call_rcu_sched(struct rcu_head *head, void (*func)(struct rcu_head *rcu))
3099
{
P
Paul E. McKenney 已提交
3100
	__call_rcu(head, func, &rcu_sched_state, -1, 0);
3101
}
3102
EXPORT_SYMBOL_GPL(call_rcu_sched);
3103 3104

/*
3105
 * Queue an RCU callback for invocation after a quicker grace period.
3106 3107 3108
 */
void call_rcu_bh(struct rcu_head *head, void (*func)(struct rcu_head *rcu))
{
P
Paul E. McKenney 已提交
3109
	__call_rcu(head, func, &rcu_bh_state, -1, 0);
3110 3111 3112
}
EXPORT_SYMBOL_GPL(call_rcu_bh);

3113 3114 3115 3116 3117 3118 3119 3120 3121 3122
/*
 * Queue an RCU callback for lazy invocation after a grace period.
 * This will likely be later named something like "call_rcu_lazy()",
 * but this change will require some way of tagging the lazy RCU
 * callbacks in the list of pending callbacks. Until then, this
 * function may only be called from __kfree_rcu().
 */
void kfree_call_rcu(struct rcu_head *head,
		    void (*func)(struct rcu_head *rcu))
{
3123
	__call_rcu(head, func, rcu_state_p, -1, 1);
3124 3125 3126
}
EXPORT_SYMBOL_GPL(kfree_call_rcu);

3127 3128 3129 3130 3131 3132 3133 3134 3135 3136 3137
/*
 * Because a context switch is a grace period for RCU-sched and RCU-bh,
 * any blocking grace-period wait automatically implies a grace period
 * if there is only one CPU online at any point time during execution
 * of either synchronize_sched() or synchronize_rcu_bh().  It is OK to
 * occasionally incorrectly indicate that there are multiple CPUs online
 * when there was in fact only one the whole time, as this just adds
 * some overhead: RCU still operates correctly.
 */
static inline int rcu_blocking_is_gp(void)
{
3138 3139
	int ret;

3140
	might_sleep();  /* Check for RCU read-side critical section. */
3141 3142 3143 3144
	preempt_disable();
	ret = num_online_cpus() <= 1;
	preempt_enable();
	return ret;
3145 3146
}

3147 3148 3149 3150 3151 3152 3153 3154 3155 3156 3157 3158
/**
 * synchronize_sched - wait until an rcu-sched grace period has elapsed.
 *
 * Control will return to the caller some time after a full rcu-sched
 * grace period has elapsed, in other words after all currently executing
 * rcu-sched read-side critical sections have completed.   These read-side
 * critical sections are delimited by rcu_read_lock_sched() and
 * rcu_read_unlock_sched(), and may be nested.  Note that preempt_disable(),
 * local_irq_disable(), and so on may be used in place of
 * rcu_read_lock_sched().
 *
 * This means that all preempt_disable code sequences, including NMI and
3159 3160 3161 3162 3163 3164 3165 3166 3167 3168 3169 3170 3171 3172 3173 3174 3175 3176 3177 3178 3179 3180
 * non-threaded hardware-interrupt handlers, in progress on entry will
 * have completed before this primitive returns.  However, this does not
 * guarantee that softirq handlers will have completed, since in some
 * kernels, these handlers can run in process context, and can block.
 *
 * Note that this guarantee implies further memory-ordering guarantees.
 * On systems with more than one CPU, when synchronize_sched() returns,
 * each CPU is guaranteed to have executed a full memory barrier since the
 * end of its last RCU-sched read-side critical section whose beginning
 * preceded the call to synchronize_sched().  In addition, each CPU having
 * an RCU read-side critical section that extends beyond the return from
 * synchronize_sched() is guaranteed to have executed a full memory barrier
 * after the beginning of synchronize_sched() and before the beginning of
 * that RCU read-side critical section.  Note that these guarantees include
 * CPUs that are offline, idle, or executing in user mode, as well as CPUs
 * that are executing in the kernel.
 *
 * Furthermore, if CPU A invoked synchronize_sched(), which returned
 * to its caller on CPU B, then both CPU A and CPU B are guaranteed
 * to have executed a full memory barrier during the execution of
 * synchronize_sched() -- even if CPU A and CPU B are the same CPU (but
 * again only if the system has more than one CPU).
3181 3182 3183 3184 3185 3186 3187 3188 3189
 *
 * This primitive provides the guarantees made by the (now removed)
 * synchronize_kernel() API.  In contrast, synchronize_rcu() only
 * guarantees that rcu_read_lock() sections will have completed.
 * In "classic RCU", these two guarantees happen to be one and
 * the same, but can differ in realtime RCU implementations.
 */
void synchronize_sched(void)
{
3190 3191 3192 3193
	RCU_LOCKDEP_WARN(lock_is_held(&rcu_bh_lock_map) ||
			 lock_is_held(&rcu_lock_map) ||
			 lock_is_held(&rcu_sched_lock_map),
			 "Illegal synchronize_sched() in RCU-sched read-side critical section");
3194 3195
	if (rcu_blocking_is_gp())
		return;
3196
	if (rcu_gp_is_expedited())
3197 3198 3199
		synchronize_sched_expedited();
	else
		wait_rcu_gp(call_rcu_sched);
3200 3201 3202 3203 3204 3205 3206 3207 3208 3209 3210
}
EXPORT_SYMBOL_GPL(synchronize_sched);

/**
 * synchronize_rcu_bh - wait until an rcu_bh grace period has elapsed.
 *
 * Control will return to the caller some time after a full rcu_bh grace
 * period has elapsed, in other words after all currently executing rcu_bh
 * read-side critical sections have completed.  RCU read-side critical
 * sections are delimited by rcu_read_lock_bh() and rcu_read_unlock_bh(),
 * and may be nested.
3211 3212 3213
 *
 * See the description of synchronize_sched() for more detailed information
 * on memory ordering guarantees.
3214 3215 3216
 */
void synchronize_rcu_bh(void)
{
3217 3218 3219 3220
	RCU_LOCKDEP_WARN(lock_is_held(&rcu_bh_lock_map) ||
			 lock_is_held(&rcu_lock_map) ||
			 lock_is_held(&rcu_sched_lock_map),
			 "Illegal synchronize_rcu_bh() in RCU-bh read-side critical section");
3221 3222
	if (rcu_blocking_is_gp())
		return;
3223
	if (rcu_gp_is_expedited())
3224 3225 3226
		synchronize_rcu_bh_expedited();
	else
		wait_rcu_gp(call_rcu_bh);
3227 3228 3229
}
EXPORT_SYMBOL_GPL(synchronize_rcu_bh);

3230 3231 3232 3233 3234 3235 3236 3237 3238 3239 3240 3241 3242 3243 3244 3245 3246 3247 3248 3249
/**
 * get_state_synchronize_rcu - Snapshot current RCU state
 *
 * Returns a cookie that is used by a later call to cond_synchronize_rcu()
 * to determine whether or not a full grace period has elapsed in the
 * meantime.
 */
unsigned long get_state_synchronize_rcu(void)
{
	/*
	 * Any prior manipulation of RCU-protected data must happen
	 * before the load from ->gpnum.
	 */
	smp_mb();  /* ^^^ */

	/*
	 * Make sure this load happens before the purportedly
	 * time-consuming work between get_state_synchronize_rcu()
	 * and cond_synchronize_rcu().
	 */
3250
	return smp_load_acquire(&rcu_state_p->gpnum);
3251 3252 3253 3254 3255 3256 3257 3258 3259 3260 3261 3262 3263 3264 3265 3266 3267 3268 3269 3270 3271 3272 3273 3274 3275
}
EXPORT_SYMBOL_GPL(get_state_synchronize_rcu);

/**
 * cond_synchronize_rcu - Conditionally wait for an RCU grace period
 *
 * @oldstate: return value from earlier call to get_state_synchronize_rcu()
 *
 * If a full RCU grace period has elapsed since the earlier call to
 * get_state_synchronize_rcu(), just return.  Otherwise, invoke
 * synchronize_rcu() to wait for a full grace period.
 *
 * Yes, this function does not take counter wrap into account.  But
 * counter wrap is harmless.  If the counter wraps, we have waited for
 * more than 2 billion grace periods (and way more on a 64-bit system!),
 * so waiting for one additional grace period should be just fine.
 */
void cond_synchronize_rcu(unsigned long oldstate)
{
	unsigned long newstate;

	/*
	 * Ensure that this load happens before any RCU-destructive
	 * actions the caller might carry out after we return.
	 */
3276
	newstate = smp_load_acquire(&rcu_state_p->completed);
3277 3278 3279 3280 3281
	if (ULONG_CMP_GE(oldstate, newstate))
		synchronize_rcu();
}
EXPORT_SYMBOL_GPL(cond_synchronize_rcu);

3282 3283 3284 3285 3286 3287 3288 3289 3290 3291 3292 3293 3294 3295 3296 3297 3298 3299 3300 3301 3302 3303 3304 3305 3306 3307 3308 3309 3310 3311 3312 3313 3314 3315 3316 3317 3318 3319 3320 3321 3322 3323 3324 3325 3326 3327 3328 3329 3330 3331 3332 3333
/**
 * get_state_synchronize_sched - Snapshot current RCU-sched state
 *
 * Returns a cookie that is used by a later call to cond_synchronize_sched()
 * to determine whether or not a full grace period has elapsed in the
 * meantime.
 */
unsigned long get_state_synchronize_sched(void)
{
	/*
	 * Any prior manipulation of RCU-protected data must happen
	 * before the load from ->gpnum.
	 */
	smp_mb();  /* ^^^ */

	/*
	 * Make sure this load happens before the purportedly
	 * time-consuming work between get_state_synchronize_sched()
	 * and cond_synchronize_sched().
	 */
	return smp_load_acquire(&rcu_sched_state.gpnum);
}
EXPORT_SYMBOL_GPL(get_state_synchronize_sched);

/**
 * cond_synchronize_sched - Conditionally wait for an RCU-sched grace period
 *
 * @oldstate: return value from earlier call to get_state_synchronize_sched()
 *
 * If a full RCU-sched grace period has elapsed since the earlier call to
 * get_state_synchronize_sched(), just return.  Otherwise, invoke
 * synchronize_sched() to wait for a full grace period.
 *
 * Yes, this function does not take counter wrap into account.  But
 * counter wrap is harmless.  If the counter wraps, we have waited for
 * more than 2 billion grace periods (and way more on a 64-bit system!),
 * so waiting for one additional grace period should be just fine.
 */
void cond_synchronize_sched(unsigned long oldstate)
{
	unsigned long newstate;

	/*
	 * Ensure that this load happens before any RCU-destructive
	 * actions the caller might carry out after we return.
	 */
	newstate = smp_load_acquire(&rcu_sched_state.completed);
	if (ULONG_CMP_GE(oldstate, newstate))
		synchronize_sched();
}
EXPORT_SYMBOL_GPL(cond_synchronize_sched);

3334 3335 3336 3337 3338 3339 3340 3341 3342 3343 3344 3345 3346 3347 3348 3349 3350 3351 3352 3353 3354 3355 3356 3357 3358 3359 3360 3361 3362 3363 3364 3365 3366 3367 3368 3369 3370 3371 3372 3373 3374 3375 3376 3377
/* Adjust sequence number for start of update-side operation. */
static void rcu_seq_start(unsigned long *sp)
{
	WRITE_ONCE(*sp, *sp + 1);
	smp_mb(); /* Ensure update-side operation after counter increment. */
	WARN_ON_ONCE(!(*sp & 0x1));
}

/* Adjust sequence number for end of update-side operation. */
static void rcu_seq_end(unsigned long *sp)
{
	smp_mb(); /* Ensure update-side operation before counter increment. */
	WRITE_ONCE(*sp, *sp + 1);
	WARN_ON_ONCE(*sp & 0x1);
}

/* Take a snapshot of the update side's sequence number. */
static unsigned long rcu_seq_snap(unsigned long *sp)
{
	unsigned long s;

	smp_mb(); /* Caller's modifications seen first by other CPUs. */
	s = (READ_ONCE(*sp) + 3) & ~0x1;
	smp_mb(); /* Above access must not bleed into critical section. */
	return s;
}

/*
 * Given a snapshot from rcu_seq_snap(), determine whether or not a
 * full update-side operation has occurred.
 */
static bool rcu_seq_done(unsigned long *sp, unsigned long s)
{
	return ULONG_CMP_GE(READ_ONCE(*sp), s);
}

/* Wrapper functions for expedited grace periods.  */
static void rcu_exp_gp_seq_start(struct rcu_state *rsp)
{
	rcu_seq_start(&rsp->expedited_sequence);
}
static void rcu_exp_gp_seq_end(struct rcu_state *rsp)
{
	rcu_seq_end(&rsp->expedited_sequence);
3378
	smp_mb(); /* Ensure that consecutive grace periods serialize. */
3379 3380 3381 3382 3383 3384 3385 3386 3387 3388
}
static unsigned long rcu_exp_gp_seq_snap(struct rcu_state *rsp)
{
	return rcu_seq_snap(&rsp->expedited_sequence);
}
static bool rcu_exp_gp_seq_done(struct rcu_state *rsp, unsigned long s)
{
	return rcu_seq_done(&rsp->expedited_sequence, s);
}

3389 3390 3391 3392 3393 3394 3395 3396 3397 3398 3399 3400 3401 3402 3403 3404 3405 3406 3407 3408 3409 3410 3411 3412 3413 3414 3415 3416 3417 3418 3419 3420 3421 3422 3423 3424 3425 3426 3427 3428 3429 3430 3431 3432 3433 3434 3435 3436 3437 3438 3439 3440 3441 3442 3443 3444 3445 3446 3447 3448 3449 3450 3451 3452 3453 3454 3455 3456 3457 3458 3459 3460 3461 3462 3463 3464 3465 3466 3467 3468 3469
/*
 * Reset the ->expmaskinit values in the rcu_node tree to reflect any
 * recent CPU-online activity.  Note that these masks are not cleared
 * when CPUs go offline, so they reflect the union of all CPUs that have
 * ever been online.  This means that this function normally takes its
 * no-work-to-do fastpath.
 */
static void sync_exp_reset_tree_hotplug(struct rcu_state *rsp)
{
	bool done;
	unsigned long flags;
	unsigned long mask;
	unsigned long oldmask;
	int ncpus = READ_ONCE(rsp->ncpus);
	struct rcu_node *rnp;
	struct rcu_node *rnp_up;

	/* If no new CPUs onlined since last time, nothing to do. */
	if (likely(ncpus == rsp->ncpus_snap))
		return;
	rsp->ncpus_snap = ncpus;

	/*
	 * Each pass through the following loop propagates newly onlined
	 * CPUs for the current rcu_node structure up the rcu_node tree.
	 */
	rcu_for_each_leaf_node(rsp, rnp) {
		raw_spin_lock_irqsave(&rnp->lock, flags);
		smp_mb__after_unlock_lock();
		if (rnp->expmaskinit == rnp->expmaskinitnext) {
			raw_spin_unlock_irqrestore(&rnp->lock, flags);
			continue;  /* No new CPUs, nothing to do. */
		}

		/* Update this node's mask, track old value for propagation. */
		oldmask = rnp->expmaskinit;
		rnp->expmaskinit = rnp->expmaskinitnext;
		raw_spin_unlock_irqrestore(&rnp->lock, flags);

		/* If was already nonzero, nothing to propagate. */
		if (oldmask)
			continue;

		/* Propagate the new CPU up the tree. */
		mask = rnp->grpmask;
		rnp_up = rnp->parent;
		done = false;
		while (rnp_up) {
			raw_spin_lock_irqsave(&rnp_up->lock, flags);
			smp_mb__after_unlock_lock();
			if (rnp_up->expmaskinit)
				done = true;
			rnp_up->expmaskinit |= mask;
			raw_spin_unlock_irqrestore(&rnp_up->lock, flags);
			if (done)
				break;
			mask = rnp_up->grpmask;
			rnp_up = rnp_up->parent;
		}
	}
}

/*
 * Reset the ->expmask values in the rcu_node tree in preparation for
 * a new expedited grace period.
 */
static void __maybe_unused sync_exp_reset_tree(struct rcu_state *rsp)
{
	unsigned long flags;
	struct rcu_node *rnp;

	sync_exp_reset_tree_hotplug(rsp);
	rcu_for_each_node_breadth_first(rsp, rnp) {
		raw_spin_lock_irqsave(&rnp->lock, flags);
		smp_mb__after_unlock_lock();
		WARN_ON_ONCE(rnp->expmask);
		rnp->expmask = rnp->expmaskinit;
		raw_spin_unlock_irqrestore(&rnp->lock, flags);
	}
}

3470
/*
3471
 * Return non-zero if there is no RCU expedited grace period in progress
3472 3473 3474 3475 3476 3477 3478 3479 3480
 * for the specified rcu_node structure, in other words, if all CPUs and
 * tasks covered by the specified rcu_node structure have done their bit
 * for the current expedited grace period.  Works only for preemptible
 * RCU -- other RCU implementation use other means.
 *
 * Caller must hold the root rcu_node's exp_funnel_mutex.
 */
static int sync_rcu_preempt_exp_done(struct rcu_node *rnp)
{
3481
	return rnp->exp_tasks == NULL &&
3482 3483 3484 3485 3486 3487 3488 3489 3490 3491 3492
	       READ_ONCE(rnp->expmask) == 0;
}

/*
 * Report the exit from RCU read-side critical section for the last task
 * that queued itself during or before the current expedited preemptible-RCU
 * grace period.  This event is reported either to the rcu_node structure on
 * which the task was queued or to one of that rcu_node structure's ancestors,
 * recursively up the tree.  (Calm down, calm down, we do the recursion
 * iteratively!)
 *
3493 3494
 * Caller must hold the root rcu_node's exp_funnel_mutex and the
 * specified rcu_node structure's ->lock.
3495
 */
3496 3497 3498
static void __rcu_report_exp_rnp(struct rcu_state *rsp, struct rcu_node *rnp,
				 bool wake, unsigned long flags)
	__releases(rnp->lock)
3499 3500 3501 3502 3503
{
	unsigned long mask;

	for (;;) {
		if (!sync_rcu_preempt_exp_done(rnp)) {
3504 3505 3506 3507
			if (!rnp->expmask)
				rcu_initiate_boost(rnp, flags);
			else
				raw_spin_unlock_irqrestore(&rnp->lock, flags);
3508 3509 3510 3511 3512 3513 3514 3515 3516 3517 3518 3519 3520 3521 3522
			break;
		}
		if (rnp->parent == NULL) {
			raw_spin_unlock_irqrestore(&rnp->lock, flags);
			if (wake) {
				smp_mb(); /* EGP done before wake_up(). */
				wake_up(&rsp->expedited_wq);
			}
			break;
		}
		mask = rnp->grpmask;
		raw_spin_unlock(&rnp->lock); /* irqs remain disabled */
		rnp = rnp->parent;
		raw_spin_lock(&rnp->lock); /* irqs already disabled */
		smp_mb__after_unlock_lock();
3523
		WARN_ON_ONCE(!(rnp->expmask & mask));
3524 3525 3526 3527
		rnp->expmask &= ~mask;
	}
}

3528 3529 3530 3531 3532 3533 3534 3535 3536 3537 3538 3539 3540 3541 3542 3543 3544 3545 3546 3547 3548 3549 3550 3551 3552 3553 3554 3555 3556 3557 3558 3559 3560 3561 3562 3563 3564
/*
 * Report expedited quiescent state for specified node.  This is a
 * lock-acquisition wrapper function for __rcu_report_exp_rnp().
 *
 * Caller must hold the root rcu_node's exp_funnel_mutex.
 */
static void __maybe_unused rcu_report_exp_rnp(struct rcu_state *rsp,
					      struct rcu_node *rnp, bool wake)
{
	unsigned long flags;

	raw_spin_lock_irqsave(&rnp->lock, flags);
	smp_mb__after_unlock_lock();
	__rcu_report_exp_rnp(rsp, rnp, wake, flags);
}

/*
 * Report expedited quiescent state for multiple CPUs, all covered by the
 * specified leaf rcu_node structure.  Caller must hold the root
 * rcu_node's exp_funnel_mutex.
 */
static void rcu_report_exp_cpu_mult(struct rcu_state *rsp, struct rcu_node *rnp,
				    unsigned long mask, bool wake)
{
	unsigned long flags;

	raw_spin_lock_irqsave(&rnp->lock, flags);
	smp_mb__after_unlock_lock();
	WARN_ON_ONCE((rnp->expmask & mask) != mask);
	rnp->expmask &= ~mask;
	__rcu_report_exp_rnp(rsp, rnp, wake, flags); /* Releases rnp->lock. */
}

/*
 * Report expedited quiescent state for specified rcu_data (CPU).
 * Caller must hold the root rcu_node's exp_funnel_mutex.
 */
3565 3566
static void rcu_report_exp_rdp(struct rcu_state *rsp, struct rcu_data *rdp,
			       bool wake)
3567 3568 3569 3570
{
	rcu_report_exp_cpu_mult(rsp, rdp->mynode, rdp->grpmask, wake);
}

3571 3572
/* Common code for synchronize_{rcu,sched}_expedited() work-done checking. */
static bool sync_exp_work_done(struct rcu_state *rsp, struct rcu_node *rnp,
3573
			       struct rcu_data *rdp,
3574
			       atomic_long_t *stat, unsigned long s)
3575
{
3576
	if (rcu_exp_gp_seq_done(rsp, s)) {
3577 3578
		if (rnp)
			mutex_unlock(&rnp->exp_funnel_mutex);
3579 3580
		else if (rdp)
			mutex_unlock(&rdp->exp_funnel_mutex);
3581 3582 3583 3584 3585 3586 3587 3588
		/* Ensure test happens before caller kfree(). */
		smp_mb__before_atomic(); /* ^^^ */
		atomic_long_inc(stat);
		return true;
	}
	return false;
}

3589 3590 3591 3592 3593 3594 3595
/*
 * Funnel-lock acquisition for expedited grace periods.  Returns a
 * pointer to the root rcu_node structure, or NULL if some other
 * task did the expedited grace period for us.
 */
static struct rcu_node *exp_funnel_lock(struct rcu_state *rsp, unsigned long s)
{
3596
	struct rcu_data *rdp;
3597 3598 3599
	struct rcu_node *rnp0;
	struct rcu_node *rnp1 = NULL;

3600
	/*
3601 3602 3603 3604
	 * First try directly acquiring the root lock in order to reduce
	 * latency in the common case where expedited grace periods are
	 * rare.  We check mutex_is_locked() to avoid pathological levels of
	 * memory contention on ->exp_funnel_mutex in the heavy-load case.
3605
	 */
3606 3607 3608 3609 3610 3611 3612 3613 3614 3615
	rnp0 = rcu_get_root(rsp);
	if (!mutex_is_locked(&rnp0->exp_funnel_mutex)) {
		if (mutex_trylock(&rnp0->exp_funnel_mutex)) {
			if (sync_exp_work_done(rsp, rnp0, NULL,
					       &rsp->expedited_workdone0, s))
				return NULL;
			return rnp0;
		}
	}

3616 3617 3618 3619 3620 3621 3622 3623
	/*
	 * Each pass through the following loop works its way
	 * up the rcu_node tree, returning if others have done the
	 * work or otherwise falls through holding the root rnp's
	 * ->exp_funnel_mutex.  The mapping from CPU to rcu_node structure
	 * can be inexact, as it is just promoting locality and is not
	 * strictly needed for correctness.
	 */
3624 3625 3626 3627 3628
	rdp = per_cpu_ptr(rsp->rda, raw_smp_processor_id());
	if (sync_exp_work_done(rsp, NULL, NULL, &rsp->expedited_workdone1, s))
		return NULL;
	mutex_lock(&rdp->exp_funnel_mutex);
	rnp0 = rdp->mynode;
3629
	for (; rnp0 != NULL; rnp0 = rnp0->parent) {
3630 3631
		if (sync_exp_work_done(rsp, rnp1, rdp,
				       &rsp->expedited_workdone2, s))
3632 3633 3634 3635
			return NULL;
		mutex_lock(&rnp0->exp_funnel_mutex);
		if (rnp1)
			mutex_unlock(&rnp1->exp_funnel_mutex);
3636 3637
		else
			mutex_unlock(&rdp->exp_funnel_mutex);
3638 3639
		rnp1 = rnp0;
	}
3640 3641
	if (sync_exp_work_done(rsp, rnp1, rdp,
			       &rsp->expedited_workdone3, s))
3642 3643 3644 3645
		return NULL;
	return rnp1;
}

3646
/* Invoked on each online non-idle CPU for expedited quiescent state. */
3647
static void synchronize_sched_expedited_cpu_stop(void *data)
3648
{
3649 3650
	__this_cpu_write(rcu_sched_data.cpu_no_qs.b.exp, true);
	resched_cpu(smp_processor_id());
3651 3652
}

3653 3654 3655 3656
/*
 * Select the nodes that the upcoming expedited grace period needs
 * to wait for.
 */
3657 3658
static void sync_rcu_exp_select_cpus(struct rcu_state *rsp,
				     smp_call_func_t func)
3659 3660 3661 3662 3663 3664
{
	int cpu;
	unsigned long flags;
	unsigned long mask;
	unsigned long mask_ofl_test;
	unsigned long mask_ofl_ipi;
3665
	int ret;
3666 3667 3668 3669 3670 3671 3672 3673 3674 3675 3676 3677 3678 3679 3680 3681 3682 3683 3684 3685 3686 3687 3688 3689 3690 3691 3692 3693 3694 3695 3696 3697 3698 3699
	struct rcu_node *rnp;

	sync_exp_reset_tree(rsp);
	rcu_for_each_leaf_node(rsp, rnp) {
		raw_spin_lock_irqsave(&rnp->lock, flags);
		smp_mb__after_unlock_lock();

		/* Each pass checks a CPU for identity, offline, and idle. */
		mask_ofl_test = 0;
		for (cpu = rnp->grplo; cpu <= rnp->grphi; cpu++) {
			struct rcu_data *rdp = per_cpu_ptr(rsp->rda, cpu);
			struct rcu_dynticks *rdtp = &per_cpu(rcu_dynticks, cpu);

			if (raw_smp_processor_id() == cpu ||
			    cpu_is_offline(cpu) ||
			    !(atomic_add_return(0, &rdtp->dynticks) & 0x1))
				mask_ofl_test |= rdp->grpmask;
		}
		mask_ofl_ipi = rnp->expmask & ~mask_ofl_test;

		/*
		 * Need to wait for any blocked tasks as well.  Note that
		 * additional blocking tasks will also block the expedited
		 * GP until such time as the ->expmask bits are cleared.
		 */
		if (rcu_preempt_has_tasks(rnp))
			rnp->exp_tasks = rnp->blkd_tasks.next;
		raw_spin_unlock_irqrestore(&rnp->lock, flags);

		/* IPI the remaining CPUs for expedited quiescent state. */
		mask = 1;
		for (cpu = rnp->grplo; cpu <= rnp->grphi; cpu++, mask <<= 1) {
			if (!(mask_ofl_ipi & mask))
				continue;
3700
			ret = smp_call_function_single(cpu, func, rsp, 0);
3701 3702
			if (!ret)
				mask_ofl_ipi &= ~mask;
3703 3704 3705 3706 3707 3708 3709 3710
		}
		/* Report quiescent states for those that went offline. */
		mask_ofl_test |= mask_ofl_ipi;
		if (mask_ofl_test)
			rcu_report_exp_cpu_mult(rsp, rnp, mask_ofl_test, false);
	}
}

3711 3712 3713 3714 3715
static void synchronize_sched_expedited_wait(struct rcu_state *rsp)
{
	int cpu;
	unsigned long jiffies_stall;
	unsigned long jiffies_start;
3716 3717 3718
	unsigned long mask;
	struct rcu_node *rnp;
	struct rcu_node *rnp_root = rcu_get_root(rsp);
3719 3720 3721 3722 3723 3724 3725 3726
	int ret;

	jiffies_stall = rcu_jiffies_till_stall_check();
	jiffies_start = jiffies;

	for (;;) {
		ret = wait_event_interruptible_timeout(
				rsp->expedited_wq,
3727
				sync_rcu_preempt_exp_done(rnp_root),
3728 3729 3730 3731 3732 3733
				jiffies_stall);
		if (ret > 0)
			return;
		if (ret < 0) {
			/* Hit a signal, disable CPU stall warnings. */
			wait_event(rsp->expedited_wq,
3734
				   sync_rcu_preempt_exp_done(rnp_root));
3735 3736 3737 3738
			return;
		}
		pr_err("INFO: %s detected expedited stalls on CPUs: {",
		       rsp->name);
3739
		rcu_for_each_leaf_node(rsp, rnp) {
3740
			(void)rcu_print_task_exp_stall(rnp);
3741 3742
			mask = 1;
			for (cpu = rnp->grplo; cpu <= rnp->grphi; cpu++, mask <<= 1) {
3743 3744
				struct rcu_data *rdp;

3745 3746
				if (!(rnp->expmask & mask))
					continue;
3747 3748 3749 3750 3751
				rdp = per_cpu_ptr(rsp->rda, cpu);
				pr_cont(" %d-%c%c%c", cpu,
					"O."[cpu_online(cpu)],
					"o."[!!(rdp->grpmask & rnp->expmaskinit)],
					"N."[!!(rdp->grpmask & rnp->expmaskinitnext)]);
3752 3753
			}
			mask <<= 1;
3754 3755 3756
		}
		pr_cont(" } %lu jiffies s: %lu\n",
			jiffies - jiffies_start, rsp->expedited_sequence);
3757 3758 3759 3760 3761 3762 3763
		rcu_for_each_leaf_node(rsp, rnp) {
			mask = 1;
			for (cpu = rnp->grplo; cpu <= rnp->grphi; cpu++, mask <<= 1) {
				if (!(rnp->expmask & mask))
					continue;
				dump_cpu_task(cpu);
			}
3764 3765 3766 3767 3768
		}
		jiffies_stall = 3 * rcu_jiffies_till_stall_check() + 3;
	}
}

3769 3770 3771 3772 3773 3774 3775 3776 3777 3778
/**
 * synchronize_sched_expedited - Brute-force RCU-sched grace period
 *
 * Wait for an RCU-sched grace period to elapse, but use a "big hammer"
 * approach to force the grace period to end quickly.  This consumes
 * significant time on all CPUs and is unfriendly to real-time workloads,
 * so is thus not recommended for any sort of common-case code.  In fact,
 * if you are using synchronize_sched_expedited() in a loop, please
 * restructure your code to batch your updates, and then use a single
 * synchronize_sched() instead.
3779
 *
3780 3781 3782
 * This implementation can be thought of as an application of sequence
 * locking to expedited grace periods, but using the sequence counter to
 * determine when someone else has already done the work instead of for
3783
 * retrying readers.
3784 3785 3786
 */
void synchronize_sched_expedited(void)
{
3787
	unsigned long s;
3788
	struct rcu_node *rnp;
3789
	struct rcu_state *rsp = &rcu_sched_state;
3790

3791
	/* Take a snapshot of the sequence number.  */
3792
	s = rcu_exp_gp_seq_snap(rsp);
3793

3794
	rnp = exp_funnel_lock(rsp, s);
3795
	if (rnp == NULL)
3796
		return;  /* Someone else did our work for us. */
3797

3798
	rcu_exp_gp_seq_start(rsp);
3799
	sync_rcu_exp_select_cpus(rsp, synchronize_sched_expedited_cpu_stop);
3800
	synchronize_sched_expedited_wait(rsp);
3801

3802
	rcu_exp_gp_seq_end(rsp);
3803
	mutex_unlock(&rnp->exp_funnel_mutex);
3804 3805 3806
}
EXPORT_SYMBOL_GPL(synchronize_sched_expedited);

3807 3808 3809 3810 3811 3812 3813 3814 3815
/*
 * Check to see if there is any immediate RCU-related work to be done
 * by the current CPU, for the specified type of RCU, returning 1 if so.
 * The checks are in order of increasing expense: checks that can be
 * carried out against CPU-local state are performed first.  However,
 * we must check for CPU stalls first, else we might not get a chance.
 */
static int __rcu_pending(struct rcu_state *rsp, struct rcu_data *rdp)
{
3816 3817
	struct rcu_node *rnp = rdp->mynode;

3818 3819 3820 3821 3822
	rdp->n_rcu_pending++;

	/* Check for CPU stalls, if enabled. */
	check_cpu_stall(rsp, rdp);

3823 3824 3825 3826
	/* Is this CPU a NO_HZ_FULL CPU that should ignore RCU? */
	if (rcu_nohz_full_cpu(rsp))
		return 0;

3827
	/* Is the RCU core waiting for a quiescent state from this CPU? */
3828
	if (rcu_scheduler_fully_active &&
3829
	    rdp->core_needs_qs && rdp->cpu_no_qs.b.norm &&
3830
	    rdp->rcu_qs_ctr_snap == __this_cpu_read(rcu_qs_ctr)) {
3831 3832
		rdp->n_rp_core_needs_qs++;
	} else if (rdp->core_needs_qs &&
3833
		   (!rdp->cpu_no_qs.b.norm ||
3834
		    rdp->rcu_qs_ctr_snap != __this_cpu_read(rcu_qs_ctr))) {
3835
		rdp->n_rp_report_qs++;
3836
		return 1;
3837
	}
3838 3839

	/* Does this CPU have callbacks ready to invoke? */
3840 3841
	if (cpu_has_callbacks_ready_to_invoke(rdp)) {
		rdp->n_rp_cb_ready++;
3842
		return 1;
3843
	}
3844 3845

	/* Has RCU gone idle with this CPU needing another grace period? */
3846 3847
	if (cpu_needs_another_gp(rsp, rdp)) {
		rdp->n_rp_cpu_needs_gp++;
3848
		return 1;
3849
	}
3850 3851

	/* Has another RCU grace period completed?  */
3852
	if (READ_ONCE(rnp->completed) != rdp->completed) { /* outside lock */
3853
		rdp->n_rp_gp_completed++;
3854
		return 1;
3855
	}
3856 3857

	/* Has a new RCU grace period started? */
3858 3859
	if (READ_ONCE(rnp->gpnum) != rdp->gpnum ||
	    unlikely(READ_ONCE(rdp->gpwrap))) { /* outside lock */
3860
		rdp->n_rp_gp_started++;
3861
		return 1;
3862
	}
3863

3864 3865 3866 3867 3868 3869
	/* Does this CPU need a deferred NOCB wakeup? */
	if (rcu_nocb_need_deferred_wakeup(rdp)) {
		rdp->n_rp_nocb_defer_wakeup++;
		return 1;
	}

3870
	/* nothing to do */
3871
	rdp->n_rp_need_nothing++;
3872 3873 3874 3875 3876 3877 3878 3879
	return 0;
}

/*
 * Check to see if there is any immediate RCU-related work to be done
 * by the current CPU, returning 1 if so.  This function is part of the
 * RCU implementation; it is -not- an exported member of the RCU API.
 */
3880
static int rcu_pending(void)
3881
{
3882 3883 3884
	struct rcu_state *rsp;

	for_each_rcu_flavor(rsp)
3885
		if (__rcu_pending(rsp, this_cpu_ptr(rsp->rda)))
3886 3887
			return 1;
	return 0;
3888 3889 3890
}

/*
3891 3892 3893
 * Return true if the specified CPU has any callback.  If all_lazy is
 * non-NULL, store an indication of whether all callbacks are lazy.
 * (If there are no callbacks, all of them are deemed to be lazy.)
3894
 */
3895
static bool __maybe_unused rcu_cpu_has_callbacks(bool *all_lazy)
3896
{
3897 3898 3899
	bool al = true;
	bool hc = false;
	struct rcu_data *rdp;
3900 3901
	struct rcu_state *rsp;

3902
	for_each_rcu_flavor(rsp) {
3903
		rdp = this_cpu_ptr(rsp->rda);
3904 3905 3906 3907
		if (!rdp->nxtlist)
			continue;
		hc = true;
		if (rdp->qlen != rdp->qlen_lazy || !all_lazy) {
3908
			al = false;
3909 3910
			break;
		}
3911 3912 3913 3914
	}
	if (all_lazy)
		*all_lazy = al;
	return hc;
3915 3916
}

3917 3918 3919 3920
/*
 * Helper function for _rcu_barrier() tracing.  If tracing is disabled,
 * the compiler is expected to optimize this away.
 */
3921
static void _rcu_barrier_trace(struct rcu_state *rsp, const char *s,
3922 3923 3924 3925 3926 3927
			       int cpu, unsigned long done)
{
	trace_rcu_barrier(rsp->name, s, cpu,
			  atomic_read(&rsp->barrier_cpu_count), done);
}

3928 3929 3930 3931
/*
 * RCU callback function for _rcu_barrier().  If we are last, wake
 * up the task executing _rcu_barrier().
 */
3932
static void rcu_barrier_callback(struct rcu_head *rhp)
3933
{
3934 3935 3936
	struct rcu_data *rdp = container_of(rhp, struct rcu_data, barrier_head);
	struct rcu_state *rsp = rdp->rsp;

3937
	if (atomic_dec_and_test(&rsp->barrier_cpu_count)) {
3938
		_rcu_barrier_trace(rsp, "LastCB", -1, rsp->barrier_sequence);
3939
		complete(&rsp->barrier_completion);
3940
	} else {
3941
		_rcu_barrier_trace(rsp, "CB", -1, rsp->barrier_sequence);
3942
	}
3943 3944 3945 3946 3947 3948 3949
}

/*
 * Called with preemption disabled, and from cross-cpu IRQ context.
 */
static void rcu_barrier_func(void *type)
{
3950
	struct rcu_state *rsp = type;
3951
	struct rcu_data *rdp = raw_cpu_ptr(rsp->rda);
3952

3953
	_rcu_barrier_trace(rsp, "IRQ", -1, rsp->barrier_sequence);
3954
	atomic_inc(&rsp->barrier_cpu_count);
3955
	rsp->call(&rdp->barrier_head, rcu_barrier_callback);
3956 3957 3958 3959 3960 3961
}

/*
 * Orchestrate the specified type of RCU barrier, waiting for all
 * RCU callbacks of the specified type to complete.
 */
3962
static void _rcu_barrier(struct rcu_state *rsp)
3963
{
3964 3965
	int cpu;
	struct rcu_data *rdp;
3966
	unsigned long s = rcu_seq_snap(&rsp->barrier_sequence);
3967

3968
	_rcu_barrier_trace(rsp, "Begin", -1, s);
3969

3970
	/* Take mutex to serialize concurrent rcu_barrier() requests. */
3971
	mutex_lock(&rsp->barrier_mutex);
3972

3973 3974 3975
	/* Did someone else do our work for us? */
	if (rcu_seq_done(&rsp->barrier_sequence, s)) {
		_rcu_barrier_trace(rsp, "EarlyExit", -1, rsp->barrier_sequence);
3976 3977 3978 3979 3980
		smp_mb(); /* caller's subsequent code after above check. */
		mutex_unlock(&rsp->barrier_mutex);
		return;
	}

3981 3982 3983
	/* Mark the start of the barrier operation. */
	rcu_seq_start(&rsp->barrier_sequence);
	_rcu_barrier_trace(rsp, "Inc1", -1, rsp->barrier_sequence);
3984

3985
	/*
3986 3987
	 * Initialize the count to one rather than to zero in order to
	 * avoid a too-soon return to zero in case of a short grace period
3988 3989
	 * (or preemption of this task).  Exclude CPU-hotplug operations
	 * to ensure that no offline CPU has callbacks queued.
3990
	 */
3991
	init_completion(&rsp->barrier_completion);
3992
	atomic_set(&rsp->barrier_cpu_count, 1);
3993
	get_online_cpus();
3994 3995

	/*
3996 3997 3998
	 * Force each CPU with callbacks to register a new callback.
	 * When that callback is invoked, we will know that all of the
	 * corresponding CPU's preceding callbacks have been invoked.
3999
	 */
P
Paul E. McKenney 已提交
4000
	for_each_possible_cpu(cpu) {
4001
		if (!cpu_online(cpu) && !rcu_is_nocb_cpu(cpu))
P
Paul E. McKenney 已提交
4002
			continue;
4003
		rdp = per_cpu_ptr(rsp->rda, cpu);
4004
		if (rcu_is_nocb_cpu(cpu)) {
4005 4006
			if (!rcu_nocb_cpu_needs_barrier(rsp, cpu)) {
				_rcu_barrier_trace(rsp, "OfflineNoCB", cpu,
4007
						   rsp->barrier_sequence);
4008 4009
			} else {
				_rcu_barrier_trace(rsp, "OnlineNoCB", cpu,
4010
						   rsp->barrier_sequence);
4011
				smp_mb__before_atomic();
4012 4013 4014 4015
				atomic_inc(&rsp->barrier_cpu_count);
				__call_rcu(&rdp->barrier_head,
					   rcu_barrier_callback, rsp, cpu, 0);
			}
4016
		} else if (READ_ONCE(rdp->qlen)) {
4017
			_rcu_barrier_trace(rsp, "OnlineQ", cpu,
4018
					   rsp->barrier_sequence);
4019
			smp_call_function_single(cpu, rcu_barrier_func, rsp, 1);
4020
		} else {
4021
			_rcu_barrier_trace(rsp, "OnlineNQ", cpu,
4022
					   rsp->barrier_sequence);
4023 4024
		}
	}
4025
	put_online_cpus();
4026 4027 4028 4029 4030

	/*
	 * Now that we have an rcu_barrier_callback() callback on each
	 * CPU, and thus each counted, remove the initial count.
	 */
4031
	if (atomic_dec_and_test(&rsp->barrier_cpu_count))
4032
		complete(&rsp->barrier_completion);
4033 4034

	/* Wait for all rcu_barrier_callback() callbacks to be invoked. */
4035
	wait_for_completion(&rsp->barrier_completion);
4036

4037 4038 4039 4040
	/* Mark the end of the barrier operation. */
	_rcu_barrier_trace(rsp, "Inc2", -1, rsp->barrier_sequence);
	rcu_seq_end(&rsp->barrier_sequence);

4041
	/* Other rcu_barrier() invocations can now safely proceed. */
4042
	mutex_unlock(&rsp->barrier_mutex);
4043 4044 4045 4046 4047 4048 4049
}

/**
 * rcu_barrier_bh - Wait until all in-flight call_rcu_bh() callbacks complete.
 */
void rcu_barrier_bh(void)
{
4050
	_rcu_barrier(&rcu_bh_state);
4051 4052 4053 4054 4055 4056 4057 4058
}
EXPORT_SYMBOL_GPL(rcu_barrier_bh);

/**
 * rcu_barrier_sched - Wait for in-flight call_rcu_sched() callbacks.
 */
void rcu_barrier_sched(void)
{
4059
	_rcu_barrier(&rcu_sched_state);
4060 4061 4062
}
EXPORT_SYMBOL_GPL(rcu_barrier_sched);

4063 4064 4065 4066 4067 4068 4069 4070 4071 4072 4073 4074 4075 4076 4077 4078 4079 4080 4081 4082 4083 4084
/*
 * Propagate ->qsinitmask bits up the rcu_node tree to account for the
 * first CPU in a given leaf rcu_node structure coming online.  The caller
 * must hold the corresponding leaf rcu_node ->lock with interrrupts
 * disabled.
 */
static void rcu_init_new_rnp(struct rcu_node *rnp_leaf)
{
	long mask;
	struct rcu_node *rnp = rnp_leaf;

	for (;;) {
		mask = rnp->grpmask;
		rnp = rnp->parent;
		if (rnp == NULL)
			return;
		raw_spin_lock(&rnp->lock); /* Interrupts already disabled. */
		rnp->qsmaskinit |= mask;
		raw_spin_unlock(&rnp->lock); /* Interrupts remain disabled. */
	}
}

4085
/*
4086
 * Do boot-time initialization of a CPU's per-CPU RCU data.
4087
 */
4088 4089
static void __init
rcu_boot_init_percpu_data(int cpu, struct rcu_state *rsp)
4090 4091
{
	unsigned long flags;
4092
	struct rcu_data *rdp = per_cpu_ptr(rsp->rda, cpu);
4093 4094 4095
	struct rcu_node *rnp = rcu_get_root(rsp);

	/* Set up local state, ensuring consistent view of global state. */
P
Paul E. McKenney 已提交
4096
	raw_spin_lock_irqsave(&rnp->lock, flags);
4097 4098
	rdp->grpmask = 1UL << (cpu - rdp->mynode->grplo);
	rdp->dynticks = &per_cpu(rcu_dynticks, cpu);
4099
	WARN_ON_ONCE(rdp->dynticks->dynticks_nesting != DYNTICK_TASK_EXIT_IDLE);
4100
	WARN_ON_ONCE(atomic_read(&rdp->dynticks->dynticks) != 1);
4101
	rdp->cpu = cpu;
4102
	rdp->rsp = rsp;
4103
	mutex_init(&rdp->exp_funnel_mutex);
P
Paul E. McKenney 已提交
4104
	rcu_boot_init_nocb_percpu_data(rdp);
P
Paul E. McKenney 已提交
4105
	raw_spin_unlock_irqrestore(&rnp->lock, flags);
4106 4107 4108 4109 4110 4111 4112
}

/*
 * Initialize a CPU's per-CPU RCU data.  Note that only one online or
 * offline event can be happening at a given time.  Note also that we
 * can accept some slop in the rsp->completed access due to the fact
 * that this CPU cannot possibly have any RCU callbacks in flight yet.
4113
 */
4114
static void
4115
rcu_init_percpu_data(int cpu, struct rcu_state *rsp)
4116 4117 4118
{
	unsigned long flags;
	unsigned long mask;
4119
	struct rcu_data *rdp = per_cpu_ptr(rsp->rda, cpu);
4120 4121 4122
	struct rcu_node *rnp = rcu_get_root(rsp);

	/* Set up local state, ensuring consistent view of global state. */
P
Paul E. McKenney 已提交
4123
	raw_spin_lock_irqsave(&rnp->lock, flags);
4124 4125
	rdp->qlen_last_fqs_check = 0;
	rdp->n_force_qs_snap = rsp->n_force_qs;
4126
	rdp->blimit = blimit;
4127 4128
	if (!rdp->nxtlist)
		init_callback_list(rdp);  /* Re-enable callbacks on this CPU. */
4129
	rdp->dynticks->dynticks_nesting = DYNTICK_TASK_EXIT_IDLE;
4130
	rcu_sysidle_init_percpu_data(rdp->dynticks);
4131 4132
	atomic_set(&rdp->dynticks->dynticks,
		   (atomic_read(&rdp->dynticks->dynticks) & ~0x1) + 1);
P
Paul E. McKenney 已提交
4133
	raw_spin_unlock(&rnp->lock);		/* irqs remain disabled. */
4134

4135 4136 4137 4138 4139
	/*
	 * Add CPU to leaf rcu_node pending-online bitmask.  Any needed
	 * propagation up the rcu_node tree will happen at the beginning
	 * of the next grace period.
	 */
4140 4141
	rnp = rdp->mynode;
	mask = rdp->grpmask;
4142 4143 4144
	raw_spin_lock(&rnp->lock);		/* irqs already disabled. */
	smp_mb__after_unlock_lock();
	rnp->qsmaskinitnext |= mask;
4145 4146 4147 4148
	rnp->expmaskinitnext |= mask;
	if (!rdp->beenonline)
		WRITE_ONCE(rsp->ncpus, READ_ONCE(rsp->ncpus) + 1);
	rdp->beenonline = true;	 /* We have now been online. */
4149 4150
	rdp->gpnum = rnp->completed; /* Make CPU later note any new GP. */
	rdp->completed = rnp->completed;
4151
	rdp->cpu_no_qs.b.norm = true;
4152
	rdp->rcu_qs_ctr_snap = per_cpu(rcu_qs_ctr, cpu);
4153
	rdp->core_needs_qs = false;
4154 4155
	trace_rcu_grace_period(rsp->name, rdp->gpnum, TPS("cpuonl"));
	raw_spin_unlock_irqrestore(&rnp->lock, flags);
4156 4157
}

4158
static void rcu_prepare_cpu(int cpu)
4159
{
4160 4161 4162
	struct rcu_state *rsp;

	for_each_rcu_flavor(rsp)
4163
		rcu_init_percpu_data(cpu, rsp);
4164 4165 4166
}

/*
4167
 * Handle CPU online/offline notification events.
4168
 */
4169 4170
int rcu_cpu_notify(struct notifier_block *self,
		   unsigned long action, void *hcpu)
4171 4172
{
	long cpu = (long)hcpu;
4173
	struct rcu_data *rdp = per_cpu_ptr(rcu_state_p->rda, cpu);
4174
	struct rcu_node *rnp = rdp->mynode;
4175
	struct rcu_state *rsp;
4176 4177 4178 4179

	switch (action) {
	case CPU_UP_PREPARE:
	case CPU_UP_PREPARE_FROZEN:
P
Peter Zijlstra 已提交
4180 4181
		rcu_prepare_cpu(cpu);
		rcu_prepare_kthreads(cpu);
4182
		rcu_spawn_all_nocb_kthreads(cpu);
4183 4184
		break;
	case CPU_ONLINE:
4185
	case CPU_DOWN_FAILED:
T
Thomas Gleixner 已提交
4186
		rcu_boost_kthread_setaffinity(rnp, -1);
4187 4188
		break;
	case CPU_DOWN_PREPARE:
4189
		rcu_boost_kthread_setaffinity(rnp, cpu);
4190
		break;
4191 4192
	case CPU_DYING:
	case CPU_DYING_FROZEN:
4193 4194
		for_each_rcu_flavor(rsp)
			rcu_cleanup_dying_cpu(rsp);
4195
		break;
4196
	case CPU_DYING_IDLE:
4197 4198 4199
		/* QS for any half-done expedited RCU-sched GP. */
		rcu_sched_qs();

4200 4201 4202 4203
		for_each_rcu_flavor(rsp) {
			rcu_cleanup_dying_idle_cpu(cpu, rsp);
		}
		break;
4204 4205 4206 4207
	case CPU_DEAD:
	case CPU_DEAD_FROZEN:
	case CPU_UP_CANCELED:
	case CPU_UP_CANCELED_FROZEN:
4208
		for_each_rcu_flavor(rsp) {
4209
			rcu_cleanup_dead_cpu(cpu, rsp);
4210 4211
			do_nocb_deferred_wakeup(per_cpu_ptr(rsp->rda, cpu));
		}
4212 4213 4214 4215
		break;
	default:
		break;
	}
4216
	return NOTIFY_OK;
4217 4218
}

4219 4220 4221 4222 4223 4224 4225
static int rcu_pm_notify(struct notifier_block *self,
			 unsigned long action, void *hcpu)
{
	switch (action) {
	case PM_HIBERNATION_PREPARE:
	case PM_SUSPEND_PREPARE:
		if (nr_cpu_ids <= 256) /* Expediting bad for large systems. */
4226
			rcu_expedite_gp();
4227 4228 4229
		break;
	case PM_POST_HIBERNATION:
	case PM_POST_SUSPEND:
4230 4231
		if (nr_cpu_ids <= 256) /* Expediting bad for large systems. */
			rcu_unexpedite_gp();
4232 4233 4234 4235 4236 4237 4238
		break;
	default:
		break;
	}
	return NOTIFY_OK;
}

4239
/*
4240
 * Spawn the kthreads that handle each RCU flavor's grace periods.
4241 4242 4243 4244
 */
static int __init rcu_spawn_gp_kthread(void)
{
	unsigned long flags;
4245
	int kthread_prio_in = kthread_prio;
4246 4247
	struct rcu_node *rnp;
	struct rcu_state *rsp;
4248
	struct sched_param sp;
4249 4250
	struct task_struct *t;

4251 4252 4253 4254 4255 4256 4257 4258 4259 4260 4261
	/* Force priority into range. */
	if (IS_ENABLED(CONFIG_RCU_BOOST) && kthread_prio < 1)
		kthread_prio = 1;
	else if (kthread_prio < 0)
		kthread_prio = 0;
	else if (kthread_prio > 99)
		kthread_prio = 99;
	if (kthread_prio != kthread_prio_in)
		pr_alert("rcu_spawn_gp_kthread(): Limited prio to %d from %d\n",
			 kthread_prio, kthread_prio_in);

4262
	rcu_scheduler_fully_active = 1;
4263
	for_each_rcu_flavor(rsp) {
4264
		t = kthread_create(rcu_gp_kthread, rsp, "%s", rsp->name);
4265 4266 4267 4268
		BUG_ON(IS_ERR(t));
		rnp = rcu_get_root(rsp);
		raw_spin_lock_irqsave(&rnp->lock, flags);
		rsp->gp_kthread = t;
4269 4270 4271 4272 4273
		if (kthread_prio) {
			sp.sched_priority = kthread_prio;
			sched_setscheduler_nocheck(t, SCHED_FIFO, &sp);
		}
		wake_up_process(t);
4274 4275
		raw_spin_unlock_irqrestore(&rnp->lock, flags);
	}
4276
	rcu_spawn_nocb_kthreads();
4277
	rcu_spawn_boost_kthreads();
4278 4279 4280 4281
	return 0;
}
early_initcall(rcu_spawn_gp_kthread);

4282 4283 4284 4285 4286 4287 4288 4289 4290 4291 4292 4293 4294 4295 4296
/*
 * This function is invoked towards the end of the scheduler's initialization
 * process.  Before this is called, the idle task might contain
 * RCU read-side critical sections (during which time, this idle
 * task is booting the system).  After this function is called, the
 * idle tasks are prohibited from containing RCU read-side critical
 * sections.  This function also enables RCU lockdep checking.
 */
void rcu_scheduler_starting(void)
{
	WARN_ON(num_online_cpus() != 1);
	WARN_ON(nr_context_switches() > 0);
	rcu_scheduler_active = 1;
}

4297 4298
/*
 * Compute the per-level fanout, either using the exact fanout specified
4299
 * or balancing the tree, depending on the rcu_fanout_exact boot parameter.
4300
 */
4301
static void __init rcu_init_levelspread(int *levelspread, const int *levelcnt)
4302 4303 4304
{
	int i;

4305
	if (rcu_fanout_exact) {
4306
		levelspread[rcu_num_lvls - 1] = rcu_fanout_leaf;
4307
		for (i = rcu_num_lvls - 2; i >= 0; i--)
4308
			levelspread[i] = RCU_FANOUT;
4309 4310 4311 4312 4313 4314
	} else {
		int ccur;
		int cprv;

		cprv = nr_cpu_ids;
		for (i = rcu_num_lvls - 1; i >= 0; i--) {
4315 4316
			ccur = levelcnt[i];
			levelspread[i] = (cprv + ccur - 1) / ccur;
4317 4318
			cprv = ccur;
		}
4319 4320 4321 4322 4323 4324
	}
}

/*
 * Helper function for rcu_init() that initializes one rcu_state structure.
 */
4325 4326
static void __init rcu_init_one(struct rcu_state *rsp,
		struct rcu_data __percpu *rda)
4327
{
4328 4329
	static const char * const buf[] = RCU_NODE_NAME_INIT;
	static const char * const fqs[] = RCU_FQS_NAME_INIT;
4330
	static const char * const exp[] = RCU_EXP_NAME_INIT;
4331
	static u8 fl_mask = 0x1;
4332 4333 4334

	int levelcnt[RCU_NUM_LVLS];		/* # nodes in each level. */
	int levelspread[RCU_NUM_LVLS];		/* kids/node in each level. */
4335 4336 4337 4338 4339
	int cpustride = 1;
	int i;
	int j;
	struct rcu_node *rnp;

4340
	BUILD_BUG_ON(RCU_NUM_LVLS > ARRAY_SIZE(buf));  /* Fix buf[] init! */
4341

4342 4343 4344
	/* Silence gcc 4.8 false positive about array index out of range. */
	if (rcu_num_lvls <= 0 || rcu_num_lvls > RCU_NUM_LVLS)
		panic("rcu_init_one: rcu_num_lvls out of range");
4345

4346 4347
	/* Initialize the level-tracking arrays. */

4348
	for (i = 0; i < rcu_num_lvls; i++)
4349
		levelcnt[i] = num_rcu_lvl[i];
4350
	for (i = 1; i < rcu_num_lvls; i++)
4351 4352
		rsp->level[i] = rsp->level[i - 1] + levelcnt[i - 1];
	rcu_init_levelspread(levelspread, levelcnt);
4353 4354
	rsp->flavor_mask = fl_mask;
	fl_mask <<= 1;
4355 4356 4357

	/* Initialize the elements themselves, starting from the leaves. */

4358
	for (i = rcu_num_lvls - 1; i >= 0; i--) {
4359
		cpustride *= levelspread[i];
4360
		rnp = rsp->level[i];
4361
		for (j = 0; j < levelcnt[i]; j++, rnp++) {
P
Paul E. McKenney 已提交
4362
			raw_spin_lock_init(&rnp->lock);
4363 4364
			lockdep_set_class_and_name(&rnp->lock,
						   &rcu_node_class[i], buf[i]);
4365 4366 4367
			raw_spin_lock_init(&rnp->fqslock);
			lockdep_set_class_and_name(&rnp->fqslock,
						   &rcu_fqs_class[i], fqs[i]);
4368 4369
			rnp->gpnum = rsp->gpnum;
			rnp->completed = rsp->completed;
4370 4371 4372 4373
			rnp->qsmask = 0;
			rnp->qsmaskinit = 0;
			rnp->grplo = j * cpustride;
			rnp->grphi = (j + 1) * cpustride - 1;
4374 4375
			if (rnp->grphi >= nr_cpu_ids)
				rnp->grphi = nr_cpu_ids - 1;
4376 4377 4378 4379 4380
			if (i == 0) {
				rnp->grpnum = 0;
				rnp->grpmask = 0;
				rnp->parent = NULL;
			} else {
4381
				rnp->grpnum = j % levelspread[i - 1];
4382 4383
				rnp->grpmask = 1UL << rnp->grpnum;
				rnp->parent = rsp->level[i - 1] +
4384
					      j / levelspread[i - 1];
4385 4386
			}
			rnp->level = i;
4387
			INIT_LIST_HEAD(&rnp->blkd_tasks);
4388
			rcu_init_one_nocb(rnp);
4389
			mutex_init(&rnp->exp_funnel_mutex);
4390 4391
			lockdep_set_class_and_name(&rnp->exp_funnel_mutex,
						   &rcu_exp_class[i], exp[i]);
4392 4393
		}
	}
4394

4395
	init_waitqueue_head(&rsp->gp_wq);
4396
	init_waitqueue_head(&rsp->expedited_wq);
4397
	rnp = rsp->level[rcu_num_lvls - 1];
4398
	for_each_possible_cpu(i) {
4399
		while (i > rnp->grphi)
4400
			rnp++;
4401
		per_cpu_ptr(rsp->rda, i)->mynode = rnp;
4402 4403
		rcu_boot_init_percpu_data(i, rsp);
	}
4404
	list_add(&rsp->flavors, &rcu_struct_flavors);
4405 4406
}

4407 4408
/*
 * Compute the rcu_node tree geometry from kernel parameters.  This cannot
4409
 * replace the definitions in tree.h because those are needed to size
4410 4411 4412 4413
 * the ->node array in the rcu_state structure.
 */
static void __init rcu_init_geometry(void)
{
4414
	ulong d;
4415
	int i;
4416
	int rcu_capacity[RCU_NUM_LVLS];
4417

4418 4419 4420 4421 4422 4423 4424 4425 4426 4427 4428 4429 4430
	/*
	 * Initialize any unspecified boot parameters.
	 * The default values of jiffies_till_first_fqs and
	 * jiffies_till_next_fqs are set to the RCU_JIFFIES_TILL_FORCE_QS
	 * value, which is a function of HZ, then adding one for each
	 * RCU_JIFFIES_FQS_DIV CPUs that might be on the system.
	 */
	d = RCU_JIFFIES_TILL_FORCE_QS + nr_cpu_ids / RCU_JIFFIES_FQS_DIV;
	if (jiffies_till_first_fqs == ULONG_MAX)
		jiffies_till_first_fqs = d;
	if (jiffies_till_next_fqs == ULONG_MAX)
		jiffies_till_next_fqs = d;

4431
	/* If the compile-time values are accurate, just leave. */
4432
	if (rcu_fanout_leaf == RCU_FANOUT_LEAF &&
4433
	    nr_cpu_ids == NR_CPUS)
4434
		return;
4435 4436
	pr_info("RCU: Adjusting geometry for rcu_fanout_leaf=%d, nr_cpu_ids=%d\n",
		rcu_fanout_leaf, nr_cpu_ids);
4437 4438 4439 4440 4441

	/*
	 * The boot-time rcu_fanout_leaf parameter is only permitted
	 * to increase the leaf-level fanout, not decrease it.  Of course,
	 * the leaf-level fanout cannot exceed the number of bits in
4442 4443
	 * the rcu_node masks.  Complain and fall back to the compile-
	 * time values if these limits are exceeded.
4444
	 */
4445
	if (rcu_fanout_leaf < RCU_FANOUT_LEAF ||
4446
	    rcu_fanout_leaf > sizeof(unsigned long) * 8) {
4447
		rcu_fanout_leaf = RCU_FANOUT_LEAF;
4448 4449 4450 4451 4452 4453
		WARN_ON(1);
		return;
	}

	/*
	 * Compute number of nodes that can be handled an rcu_node tree
4454
	 * with the given number of levels.
4455
	 */
4456
	rcu_capacity[0] = rcu_fanout_leaf;
4457
	for (i = 1; i < RCU_NUM_LVLS; i++)
4458
		rcu_capacity[i] = rcu_capacity[i - 1] * RCU_FANOUT;
4459 4460

	/*
4461 4462
	 * The tree must be able to accommodate the configured number of CPUs.
	 * If this limit is exceeded than we have a serious problem elsewhere.
4463
	 */
4464
	if (nr_cpu_ids > rcu_capacity[RCU_NUM_LVLS - 1])
4465
		panic("rcu_init_geometry: rcu_capacity[] is too small");
4466

4467
	/* Calculate the number of levels in the tree. */
4468
	for (i = 0; nr_cpu_ids > rcu_capacity[i]; i++) {
4469
	}
4470
	rcu_num_lvls = i + 1;
4471

4472
	/* Calculate the number of rcu_nodes at each level of the tree. */
4473
	for (i = 0; i < rcu_num_lvls; i++) {
4474
		int cap = rcu_capacity[(rcu_num_lvls - 1) - i];
4475 4476
		num_rcu_lvl[i] = DIV_ROUND_UP(nr_cpu_ids, cap);
	}
4477 4478 4479

	/* Calculate the total number of rcu_node structures. */
	rcu_num_nodes = 0;
4480
	for (i = 0; i < rcu_num_lvls; i++)
4481 4482 4483
		rcu_num_nodes += num_rcu_lvl[i];
}

4484 4485 4486 4487 4488 4489 4490 4491 4492 4493 4494 4495 4496 4497 4498 4499 4500 4501 4502 4503 4504 4505
/*
 * Dump out the structure of the rcu_node combining tree associated
 * with the rcu_state structure referenced by rsp.
 */
static void __init rcu_dump_rcu_node_tree(struct rcu_state *rsp)
{
	int level = 0;
	struct rcu_node *rnp;

	pr_info("rcu_node tree layout dump\n");
	pr_info(" ");
	rcu_for_each_node_breadth_first(rsp, rnp) {
		if (rnp->level != level) {
			pr_cont("\n");
			pr_info(" ");
			level = rnp->level;
		}
		pr_cont("%d:%d ^%d  ", rnp->grplo, rnp->grphi, rnp->grpnum);
	}
	pr_cont("\n");
}

4506
void __init rcu_init(void)
4507
{
P
Paul E. McKenney 已提交
4508
	int cpu;
4509

4510 4511
	rcu_early_boot_tests();

4512
	rcu_bootup_announce();
4513
	rcu_init_geometry();
4514
	rcu_init_one(&rcu_bh_state, &rcu_bh_data);
4515
	rcu_init_one(&rcu_sched_state, &rcu_sched_data);
4516 4517
	if (dump_tree)
		rcu_dump_rcu_node_tree(&rcu_sched_state);
4518
	__rcu_init_preempt();
J
Jiang Fang 已提交
4519
	open_softirq(RCU_SOFTIRQ, rcu_process_callbacks);
4520 4521 4522 4523 4524 4525 4526

	/*
	 * We don't need protection against CPU-hotplug here because
	 * this is called early in boot, before either interrupts
	 * or the scheduler are operational.
	 */
	cpu_notifier(rcu_cpu_notify, 0);
4527
	pm_notifier(rcu_pm_notify, 0);
P
Paul E. McKenney 已提交
4528 4529
	for_each_online_cpu(cpu)
		rcu_cpu_notify(NULL, CPU_UP_PREPARE, (void *)(long)cpu);
4530 4531
}

4532
#include "tree_plugin.h"