1 /* 2 * Read-Copy Update mechanism for mutual exclusion 3 * 4 * This program is free software; you can redistribute it and/or modify 5 * it under the terms of the GNU General Public License as published by 6 * the Free Software Foundation; either version 2 of the License, or 7 * (at your option) any later version. 8 * 9 * This program is distributed in the hope that it will be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 * GNU General Public License for more details. 13 * 14 * You should have received a copy of the GNU General Public License 15 * along with this program; if not, you can access it online at 16 * http://www.gnu.org/licenses/gpl-2.0.html. 17 * 18 * Copyright IBM Corporation, 2008 19 * 20 * Authors: Dipankar Sarma <dipankar@in.ibm.com> 21 * Manfred Spraul <manfred@colorfullife.com> 22 * Paul E. McKenney <paulmck@linux.vnet.ibm.com> Hierarchical version 23 * 24 * Based on the original work by Paul McKenney <paulmck@us.ibm.com> 25 * and inputs from Rusty Russell, Andrea Arcangeli and Andi Kleen. 26 * 27 * For detailed explanation of Read-Copy Update mechanism see - 28 * Documentation/RCU 29 */ 30 #include <linux/types.h> 31 #include <linux/kernel.h> 32 #include <linux/init.h> 33 #include <linux/spinlock.h> 34 #include <linux/smp.h> 35 #include <linux/rcupdate.h> 36 #include <linux/interrupt.h> 37 #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 #include <linux/completion.h> 43 #include <linux/moduleparam.h> 44 #include <linux/module.h> 45 #include <linux/percpu.h> 46 #include <linux/notifier.h> 47 #include <linux/cpu.h> 48 #include <linux/mutex.h> 49 #include <linux/time.h> 50 #include <linux/kernel_stat.h> 51 #include <linux/wait.h> 52 #include <linux/kthread.h> 53 #include <linux/prefetch.h> 54 #include <linux/delay.h> 55 #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 MODULE_ALIAS("rcutree"); 64 #ifdef MODULE_PARAM_PREFIX 65 #undef MODULE_PARAM_PREFIX 66 #endif 67 #define MODULE_PARAM_PREFIX "rcutree." 68 69 /* Data structures. */ 70 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 74 /* 75 * In order to export the rcu_state name to the tracing tools, it 76 * needs to be added in the __tracepoint_string section. 77 * This requires defining a separate variable tp_<sname>_varname 78 * that points to the string being used, and this will allow 79 * the tracing userspace tools to be able to decipher the string 80 * address to the matching string. 81 */ 82 #ifdef CONFIG_TRACING 83 # define DEFINE_RCU_TPS(sname) \ 84 static char sname##_varname[] = #sname; \ 85 static const char *tp_##sname##_varname __used __tracepoint_string = sname##_varname; 86 # define RCU_STATE_NAME(sname) sname##_varname 87 #else 88 # define DEFINE_RCU_TPS(sname) 89 # define RCU_STATE_NAME(sname) __stringify(sname) 90 #endif 91 92 #define RCU_STATE_INITIALIZER(sname, sabbr, cr) \ 93 DEFINE_RCU_TPS(sname) \ 94 static DEFINE_PER_CPU_SHARED_ALIGNED(struct rcu_data, sname##_data); \ 95 struct rcu_state sname##_state = { \ 96 .level = { &sname##_state.node[0] }, \ 97 .rda = &sname##_data, \ 98 .call = cr, \ 99 .fqs_state = RCU_GP_IDLE, \ 100 .gpnum = 0UL - 300UL, \ 101 .completed = 0UL - 300UL, \ 102 .orphan_lock = __RAW_SPIN_LOCK_UNLOCKED(&sname##_state.orphan_lock), \ 103 .orphan_nxttail = &sname##_state.orphan_nxtlist, \ 104 .orphan_donetail = &sname##_state.orphan_donelist, \ 105 .barrier_mutex = __MUTEX_INITIALIZER(sname##_state.barrier_mutex), \ 106 .name = RCU_STATE_NAME(sname), \ 107 .abbr = sabbr, \ 108 } 109 110 RCU_STATE_INITIALIZER(rcu_sched, 's', call_rcu_sched); 111 RCU_STATE_INITIALIZER(rcu_bh, 'b', call_rcu_bh); 112 113 static struct rcu_state *const rcu_state_p; 114 static struct rcu_data __percpu *const rcu_data_p; 115 LIST_HEAD(rcu_struct_flavors); 116 117 /* Dump rcu_node combining tree at boot to verify correct setup. */ 118 static bool dump_tree; 119 module_param(dump_tree, bool, 0444); 120 /* Control rcu_node-tree auto-balancing at boot time. */ 121 static bool rcu_fanout_exact; 122 module_param(rcu_fanout_exact, bool, 0444); 123 /* Increase (but not decrease) the RCU_FANOUT_LEAF at boot time. */ 124 static int rcu_fanout_leaf = RCU_FANOUT_LEAF; 125 module_param(rcu_fanout_leaf, int, 0444); 126 int rcu_num_lvls __read_mostly = RCU_NUM_LVLS; 127 static int num_rcu_lvl[] = { /* Number of rcu_nodes at specified level. */ 128 NUM_RCU_LVL_0, 129 NUM_RCU_LVL_1, 130 NUM_RCU_LVL_2, 131 NUM_RCU_LVL_3, 132 NUM_RCU_LVL_4, 133 }; 134 int rcu_num_nodes __read_mostly = NUM_RCU_NODES; /* Total # rcu_nodes in use. */ 135 136 /* 137 * The rcu_scheduler_active variable transitions from zero to one just 138 * before the first task is spawned. So when this variable is zero, RCU 139 * can assume that there is but one task, allowing RCU to (for example) 140 * optimize synchronize_sched() to a simple barrier(). When this variable 141 * is one, RCU must actually do all the hard work required to detect real 142 * grace periods. This variable is also used to suppress boot-time false 143 * positives from lockdep-RCU error checking. 144 */ 145 int rcu_scheduler_active __read_mostly; 146 EXPORT_SYMBOL_GPL(rcu_scheduler_active); 147 148 /* 149 * The rcu_scheduler_fully_active variable transitions from zero to one 150 * during the early_initcall() processing, which is after the scheduler 151 * is capable of creating new tasks. So RCU processing (for example, 152 * creating tasks for RCU priority boosting) must be delayed until after 153 * rcu_scheduler_fully_active transitions from zero to one. We also 154 * currently delay invocation of any RCU callbacks until after this point. 155 * 156 * It might later prove better for people registering RCU callbacks during 157 * early boot to take responsibility for these callbacks, but one step at 158 * a time. 159 */ 160 static int rcu_scheduler_fully_active __read_mostly; 161 162 static void rcu_init_new_rnp(struct rcu_node *rnp_leaf); 163 static void rcu_cleanup_dead_rnp(struct rcu_node *rnp_leaf); 164 static void rcu_boost_kthread_setaffinity(struct rcu_node *rnp, int outgoingcpu); 165 static void invoke_rcu_core(void); 166 static void invoke_rcu_callbacks(struct rcu_state *rsp, struct rcu_data *rdp); 167 168 /* rcuc/rcub kthread realtime priority */ 169 #ifdef CONFIG_RCU_KTHREAD_PRIO 170 static int kthread_prio = CONFIG_RCU_KTHREAD_PRIO; 171 #else /* #ifdef CONFIG_RCU_KTHREAD_PRIO */ 172 static int kthread_prio = IS_ENABLED(CONFIG_RCU_BOOST) ? 1 : 0; 173 #endif /* #else #ifdef CONFIG_RCU_KTHREAD_PRIO */ 174 module_param(kthread_prio, int, 0644); 175 176 /* Delay in jiffies for grace-period initialization delays, debug only. */ 177 178 #ifdef CONFIG_RCU_TORTURE_TEST_SLOW_PREINIT 179 static int gp_preinit_delay = CONFIG_RCU_TORTURE_TEST_SLOW_PREINIT_DELAY; 180 module_param(gp_preinit_delay, int, 0644); 181 #else /* #ifdef CONFIG_RCU_TORTURE_TEST_SLOW_PREINIT */ 182 static const int gp_preinit_delay; 183 #endif /* #else #ifdef CONFIG_RCU_TORTURE_TEST_SLOW_PREINIT */ 184 185 #ifdef CONFIG_RCU_TORTURE_TEST_SLOW_INIT 186 static int gp_init_delay = CONFIG_RCU_TORTURE_TEST_SLOW_INIT_DELAY; 187 module_param(gp_init_delay, int, 0644); 188 #else /* #ifdef CONFIG_RCU_TORTURE_TEST_SLOW_INIT */ 189 static const int gp_init_delay; 190 #endif /* #else #ifdef CONFIG_RCU_TORTURE_TEST_SLOW_INIT */ 191 192 #ifdef CONFIG_RCU_TORTURE_TEST_SLOW_CLEANUP 193 static int gp_cleanup_delay = CONFIG_RCU_TORTURE_TEST_SLOW_CLEANUP_DELAY; 194 module_param(gp_cleanup_delay, int, 0644); 195 #else /* #ifdef CONFIG_RCU_TORTURE_TEST_SLOW_CLEANUP */ 196 static const int gp_cleanup_delay; 197 #endif /* #else #ifdef CONFIG_RCU_TORTURE_TEST_SLOW_CLEANUP */ 198 199 /* 200 * Number of grace periods between delays, normalized by the duration of 201 * the delay. The longer the the delay, the more the grace periods between 202 * each delay. The reason for this normalization is that it means that, 203 * for non-zero delays, the overall slowdown of grace periods is constant 204 * regardless of the duration of the delay. This arrangement balances 205 * the need for long delays to increase some race probabilities with the 206 * need for fast grace periods to increase other race probabilities. 207 */ 208 #define PER_RCU_NODE_PERIOD 3 /* Number of grace periods between delays. */ 209 210 /* 211 * Track the rcutorture test sequence number and the update version 212 * number within a given test. The rcutorture_testseq is incremented 213 * on every rcutorture module load and unload, so has an odd value 214 * when a test is running. The rcutorture_vernum is set to zero 215 * when rcutorture starts and is incremented on each rcutorture update. 216 * These variables enable correlating rcutorture output with the 217 * RCU tracing information. 218 */ 219 unsigned long rcutorture_testseq; 220 unsigned long rcutorture_vernum; 221 222 /* 223 * Compute the mask of online CPUs for the specified rcu_node structure. 224 * This will not be stable unless the rcu_node structure's ->lock is 225 * held, but the bit corresponding to the current CPU will be stable 226 * in most contexts. 227 */ 228 unsigned long rcu_rnp_online_cpus(struct rcu_node *rnp) 229 { 230 return READ_ONCE(rnp->qsmaskinitnext); 231 } 232 233 /* 234 * Return true if an RCU grace period is in progress. The READ_ONCE()s 235 * permit this function to be invoked without holding the root rcu_node 236 * structure's ->lock, but of course results can be subject to change. 237 */ 238 static int rcu_gp_in_progress(struct rcu_state *rsp) 239 { 240 return READ_ONCE(rsp->completed) != READ_ONCE(rsp->gpnum); 241 } 242 243 /* 244 * Note a quiescent state. Because we do not need to know 245 * how many quiescent states passed, just if there was at least 246 * one since the start of the grace period, this just sets a flag. 247 * The caller must have disabled preemption. 248 */ 249 void rcu_sched_qs(void) 250 { 251 if (!__this_cpu_read(rcu_sched_data.passed_quiesce)) { 252 trace_rcu_grace_period(TPS("rcu_sched"), 253 __this_cpu_read(rcu_sched_data.gpnum), 254 TPS("cpuqs")); 255 __this_cpu_write(rcu_sched_data.passed_quiesce, 1); 256 } 257 } 258 259 void rcu_bh_qs(void) 260 { 261 if (!__this_cpu_read(rcu_bh_data.passed_quiesce)) { 262 trace_rcu_grace_period(TPS("rcu_bh"), 263 __this_cpu_read(rcu_bh_data.gpnum), 264 TPS("cpuqs")); 265 __this_cpu_write(rcu_bh_data.passed_quiesce, 1); 266 } 267 } 268 269 static DEFINE_PER_CPU(int, rcu_sched_qs_mask); 270 271 static DEFINE_PER_CPU(struct rcu_dynticks, rcu_dynticks) = { 272 .dynticks_nesting = DYNTICK_TASK_EXIT_IDLE, 273 .dynticks = ATOMIC_INIT(1), 274 #ifdef CONFIG_NO_HZ_FULL_SYSIDLE 275 .dynticks_idle_nesting = DYNTICK_TASK_NEST_VALUE, 276 .dynticks_idle = ATOMIC_INIT(1), 277 #endif /* #ifdef CONFIG_NO_HZ_FULL_SYSIDLE */ 278 }; 279 280 DEFINE_PER_CPU_SHARED_ALIGNED(unsigned long, rcu_qs_ctr); 281 EXPORT_PER_CPU_SYMBOL_GPL(rcu_qs_ctr); 282 283 /* 284 * Let the RCU core know that this CPU has gone through the scheduler, 285 * which is a quiescent state. This is called when the need for a 286 * quiescent state is urgent, so we burn an atomic operation and full 287 * memory barriers to let the RCU core know about it, regardless of what 288 * this CPU might (or might not) do in the near future. 289 * 290 * We inform the RCU core by emulating a zero-duration dyntick-idle 291 * period, which we in turn do by incrementing the ->dynticks counter 292 * by two. 293 */ 294 static void rcu_momentary_dyntick_idle(void) 295 { 296 unsigned long flags; 297 struct rcu_data *rdp; 298 struct rcu_dynticks *rdtp; 299 int resched_mask; 300 struct rcu_state *rsp; 301 302 local_irq_save(flags); 303 304 /* 305 * Yes, we can lose flag-setting operations. This is OK, because 306 * the flag will be set again after some delay. 307 */ 308 resched_mask = raw_cpu_read(rcu_sched_qs_mask); 309 raw_cpu_write(rcu_sched_qs_mask, 0); 310 311 /* Find the flavor that needs a quiescent state. */ 312 for_each_rcu_flavor(rsp) { 313 rdp = raw_cpu_ptr(rsp->rda); 314 if (!(resched_mask & rsp->flavor_mask)) 315 continue; 316 smp_mb(); /* rcu_sched_qs_mask before cond_resched_completed. */ 317 if (READ_ONCE(rdp->mynode->completed) != 318 READ_ONCE(rdp->cond_resched_completed)) 319 continue; 320 321 /* 322 * Pretend to be momentarily idle for the quiescent state. 323 * This allows the grace-period kthread to record the 324 * quiescent state, with no need for this CPU to do anything 325 * further. 326 */ 327 rdtp = this_cpu_ptr(&rcu_dynticks); 328 smp_mb__before_atomic(); /* Earlier stuff before QS. */ 329 atomic_add(2, &rdtp->dynticks); /* QS. */ 330 smp_mb__after_atomic(); /* Later stuff after QS. */ 331 break; 332 } 333 local_irq_restore(flags); 334 } 335 336 /* 337 * Note a context switch. This is a quiescent state for RCU-sched, 338 * and requires special handling for preemptible RCU. 339 * The caller must have disabled preemption. 340 */ 341 void rcu_note_context_switch(void) 342 { 343 trace_rcu_utilization(TPS("Start context switch")); 344 rcu_sched_qs(); 345 rcu_preempt_note_context_switch(); 346 if (unlikely(raw_cpu_read(rcu_sched_qs_mask))) 347 rcu_momentary_dyntick_idle(); 348 trace_rcu_utilization(TPS("End context switch")); 349 } 350 EXPORT_SYMBOL_GPL(rcu_note_context_switch); 351 352 /* 353 * Register a quiescent state for all RCU flavors. If there is an 354 * emergency, invoke rcu_momentary_dyntick_idle() to do a heavy-weight 355 * dyntick-idle quiescent state visible to other CPUs (but only for those 356 * RCU flavors in desperate need of a quiescent state, which will normally 357 * be none of them). Either way, do a lightweight quiescent state for 358 * all RCU flavors. 359 */ 360 void rcu_all_qs(void) 361 { 362 if (unlikely(raw_cpu_read(rcu_sched_qs_mask))) 363 rcu_momentary_dyntick_idle(); 364 this_cpu_inc(rcu_qs_ctr); 365 } 366 EXPORT_SYMBOL_GPL(rcu_all_qs); 367 368 static long blimit = 10; /* Maximum callbacks per rcu_do_batch. */ 369 static long qhimark = 10000; /* If this many pending, ignore blimit. */ 370 static long qlowmark = 100; /* Once only this many pending, use blimit. */ 371 372 module_param(blimit, long, 0444); 373 module_param(qhimark, long, 0444); 374 module_param(qlowmark, long, 0444); 375 376 static ulong jiffies_till_first_fqs = ULONG_MAX; 377 static ulong jiffies_till_next_fqs = ULONG_MAX; 378 379 module_param(jiffies_till_first_fqs, ulong, 0644); 380 module_param(jiffies_till_next_fqs, ulong, 0644); 381 382 /* 383 * How long the grace period must be before we start recruiting 384 * quiescent-state help from rcu_note_context_switch(). 385 */ 386 static ulong jiffies_till_sched_qs = HZ / 20; 387 module_param(jiffies_till_sched_qs, ulong, 0644); 388 389 static bool rcu_start_gp_advanced(struct rcu_state *rsp, struct rcu_node *rnp, 390 struct rcu_data *rdp); 391 static void force_qs_rnp(struct rcu_state *rsp, 392 int (*f)(struct rcu_data *rsp, bool *isidle, 393 unsigned long *maxj), 394 bool *isidle, unsigned long *maxj); 395 static void force_quiescent_state(struct rcu_state *rsp); 396 static int rcu_pending(void); 397 398 /* 399 * Return the number of RCU batches started thus far for debug & stats. 400 */ 401 unsigned long rcu_batches_started(void) 402 { 403 return rcu_state_p->gpnum; 404 } 405 EXPORT_SYMBOL_GPL(rcu_batches_started); 406 407 /* 408 * Return the number of RCU-sched batches started thus far for debug & stats. 409 */ 410 unsigned long rcu_batches_started_sched(void) 411 { 412 return rcu_sched_state.gpnum; 413 } 414 EXPORT_SYMBOL_GPL(rcu_batches_started_sched); 415 416 /* 417 * Return the number of RCU BH batches started thus far for debug & stats. 418 */ 419 unsigned long rcu_batches_started_bh(void) 420 { 421 return rcu_bh_state.gpnum; 422 } 423 EXPORT_SYMBOL_GPL(rcu_batches_started_bh); 424 425 /* 426 * Return the number of RCU batches completed thus far for debug & stats. 427 */ 428 unsigned long rcu_batches_completed(void) 429 { 430 return rcu_state_p->completed; 431 } 432 EXPORT_SYMBOL_GPL(rcu_batches_completed); 433 434 /* 435 * Return the number of RCU-sched batches completed thus far for debug & stats. 436 */ 437 unsigned long rcu_batches_completed_sched(void) 438 { 439 return rcu_sched_state.completed; 440 } 441 EXPORT_SYMBOL_GPL(rcu_batches_completed_sched); 442 443 /* 444 * Return the number of RCU BH batches completed thus far for debug & stats. 445 */ 446 unsigned long rcu_batches_completed_bh(void) 447 { 448 return rcu_bh_state.completed; 449 } 450 EXPORT_SYMBOL_GPL(rcu_batches_completed_bh); 451 452 /* 453 * Force a quiescent state. 454 */ 455 void rcu_force_quiescent_state(void) 456 { 457 force_quiescent_state(rcu_state_p); 458 } 459 EXPORT_SYMBOL_GPL(rcu_force_quiescent_state); 460 461 /* 462 * Force a quiescent state for RCU BH. 463 */ 464 void rcu_bh_force_quiescent_state(void) 465 { 466 force_quiescent_state(&rcu_bh_state); 467 } 468 EXPORT_SYMBOL_GPL(rcu_bh_force_quiescent_state); 469 470 /* 471 * Force a quiescent state for RCU-sched. 472 */ 473 void rcu_sched_force_quiescent_state(void) 474 { 475 force_quiescent_state(&rcu_sched_state); 476 } 477 EXPORT_SYMBOL_GPL(rcu_sched_force_quiescent_state); 478 479 /* 480 * Show the state of the grace-period kthreads. 481 */ 482 void show_rcu_gp_kthreads(void) 483 { 484 struct rcu_state *rsp; 485 486 for_each_rcu_flavor(rsp) { 487 pr_info("%s: wait state: %d ->state: %#lx\n", 488 rsp->name, rsp->gp_state, rsp->gp_kthread->state); 489 /* sched_show_task(rsp->gp_kthread); */ 490 } 491 } 492 EXPORT_SYMBOL_GPL(show_rcu_gp_kthreads); 493 494 /* 495 * Record the number of times rcutorture tests have been initiated and 496 * terminated. This information allows the debugfs tracing stats to be 497 * correlated to the rcutorture messages, even when the rcutorture module 498 * is being repeatedly loaded and unloaded. In other words, we cannot 499 * store this state in rcutorture itself. 500 */ 501 void rcutorture_record_test_transition(void) 502 { 503 rcutorture_testseq++; 504 rcutorture_vernum = 0; 505 } 506 EXPORT_SYMBOL_GPL(rcutorture_record_test_transition); 507 508 /* 509 * Send along grace-period-related data for rcutorture diagnostics. 510 */ 511 void rcutorture_get_gp_data(enum rcutorture_type test_type, int *flags, 512 unsigned long *gpnum, unsigned long *completed) 513 { 514 struct rcu_state *rsp = NULL; 515 516 switch (test_type) { 517 case RCU_FLAVOR: 518 rsp = rcu_state_p; 519 break; 520 case RCU_BH_FLAVOR: 521 rsp = &rcu_bh_state; 522 break; 523 case RCU_SCHED_FLAVOR: 524 rsp = &rcu_sched_state; 525 break; 526 default: 527 break; 528 } 529 if (rsp != NULL) { 530 *flags = READ_ONCE(rsp->gp_flags); 531 *gpnum = READ_ONCE(rsp->gpnum); 532 *completed = READ_ONCE(rsp->completed); 533 return; 534 } 535 *flags = 0; 536 *gpnum = 0; 537 *completed = 0; 538 } 539 EXPORT_SYMBOL_GPL(rcutorture_get_gp_data); 540 541 /* 542 * Record the number of writer passes through the current rcutorture test. 543 * This is also used to correlate debugfs tracing stats with the rcutorture 544 * messages. 545 */ 546 void rcutorture_record_progress(unsigned long vernum) 547 { 548 rcutorture_vernum++; 549 } 550 EXPORT_SYMBOL_GPL(rcutorture_record_progress); 551 552 /* 553 * Does the CPU have callbacks ready to be invoked? 554 */ 555 static int 556 cpu_has_callbacks_ready_to_invoke(struct rcu_data *rdp) 557 { 558 return &rdp->nxtlist != rdp->nxttail[RCU_DONE_TAIL] && 559 rdp->nxttail[RCU_DONE_TAIL] != NULL; 560 } 561 562 /* 563 * Return the root node of the specified rcu_state structure. 564 */ 565 static struct rcu_node *rcu_get_root(struct rcu_state *rsp) 566 { 567 return &rsp->node[0]; 568 } 569 570 /* 571 * Is there any need for future grace periods? 572 * Interrupts must be disabled. If the caller does not hold the root 573 * rnp_node structure's ->lock, the results are advisory only. 574 */ 575 static int rcu_future_needs_gp(struct rcu_state *rsp) 576 { 577 struct rcu_node *rnp = rcu_get_root(rsp); 578 int idx = (READ_ONCE(rnp->completed) + 1) & 0x1; 579 int *fp = &rnp->need_future_gp[idx]; 580 581 return READ_ONCE(*fp); 582 } 583 584 /* 585 * Does the current CPU require a not-yet-started grace period? 586 * The caller must have disabled interrupts to prevent races with 587 * normal callback registry. 588 */ 589 static int 590 cpu_needs_another_gp(struct rcu_state *rsp, struct rcu_data *rdp) 591 { 592 int i; 593 594 if (rcu_gp_in_progress(rsp)) 595 return 0; /* No, a grace period is already in progress. */ 596 if (rcu_future_needs_gp(rsp)) 597 return 1; /* Yes, a no-CBs CPU needs one. */ 598 if (!rdp->nxttail[RCU_NEXT_TAIL]) 599 return 0; /* No, this is a no-CBs (or offline) CPU. */ 600 if (*rdp->nxttail[RCU_NEXT_READY_TAIL]) 601 return 1; /* Yes, this CPU has newly registered callbacks. */ 602 for (i = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++) 603 if (rdp->nxttail[i - 1] != rdp->nxttail[i] && 604 ULONG_CMP_LT(READ_ONCE(rsp->completed), 605 rdp->nxtcompleted[i])) 606 return 1; /* Yes, CBs for future grace period. */ 607 return 0; /* No grace period needed. */ 608 } 609 610 /* 611 * rcu_eqs_enter_common - current CPU is moving towards extended quiescent state 612 * 613 * If the new value of the ->dynticks_nesting counter now is zero, 614 * we really have entered idle, and must do the appropriate accounting. 615 * The caller must have disabled interrupts. 616 */ 617 static void rcu_eqs_enter_common(long long oldval, bool user) 618 { 619 struct rcu_state *rsp; 620 struct rcu_data *rdp; 621 struct rcu_dynticks *rdtp = this_cpu_ptr(&rcu_dynticks); 622 623 trace_rcu_dyntick(TPS("Start"), oldval, rdtp->dynticks_nesting); 624 if (IS_ENABLED(CONFIG_RCU_EQS_DEBUG) && 625 !user && !is_idle_task(current)) { 626 struct task_struct *idle __maybe_unused = 627 idle_task(smp_processor_id()); 628 629 trace_rcu_dyntick(TPS("Error on entry: not idle task"), oldval, 0); 630 ftrace_dump(DUMP_ORIG); 631 WARN_ONCE(1, "Current pid: %d comm: %s / Idle pid: %d comm: %s", 632 current->pid, current->comm, 633 idle->pid, idle->comm); /* must be idle task! */ 634 } 635 for_each_rcu_flavor(rsp) { 636 rdp = this_cpu_ptr(rsp->rda); 637 do_nocb_deferred_wakeup(rdp); 638 } 639 rcu_prepare_for_idle(); 640 /* CPUs seeing atomic_inc() must see prior RCU read-side crit sects */ 641 smp_mb__before_atomic(); /* See above. */ 642 atomic_inc(&rdtp->dynticks); 643 smp_mb__after_atomic(); /* Force ordering with next sojourn. */ 644 WARN_ON_ONCE(IS_ENABLED(CONFIG_RCU_EQS_DEBUG) && 645 atomic_read(&rdtp->dynticks) & 0x1); 646 rcu_dynticks_task_enter(); 647 648 /* 649 * It is illegal to enter an extended quiescent state while 650 * in an RCU read-side critical section. 651 */ 652 rcu_lockdep_assert(!lock_is_held(&rcu_lock_map), 653 "Illegal idle entry in RCU read-side critical section."); 654 rcu_lockdep_assert(!lock_is_held(&rcu_bh_lock_map), 655 "Illegal idle entry in RCU-bh read-side critical section."); 656 rcu_lockdep_assert(!lock_is_held(&rcu_sched_lock_map), 657 "Illegal idle entry in RCU-sched read-side critical section."); 658 } 659 660 /* 661 * Enter an RCU extended quiescent state, which can be either the 662 * idle loop or adaptive-tickless usermode execution. 663 */ 664 static void rcu_eqs_enter(bool user) 665 { 666 long long oldval; 667 struct rcu_dynticks *rdtp; 668 669 rdtp = this_cpu_ptr(&rcu_dynticks); 670 oldval = rdtp->dynticks_nesting; 671 WARN_ON_ONCE(IS_ENABLED(CONFIG_RCU_EQS_DEBUG) && 672 (oldval & DYNTICK_TASK_NEST_MASK) == 0); 673 if ((oldval & DYNTICK_TASK_NEST_MASK) == DYNTICK_TASK_NEST_VALUE) { 674 rdtp->dynticks_nesting = 0; 675 rcu_eqs_enter_common(oldval, user); 676 } else { 677 rdtp->dynticks_nesting -= DYNTICK_TASK_NEST_VALUE; 678 } 679 } 680 681 /** 682 * rcu_idle_enter - inform RCU that current CPU is entering idle 683 * 684 * Enter idle mode, in other words, -leave- the mode in which RCU 685 * read-side critical sections can occur. (Though RCU read-side 686 * critical sections can occur in irq handlers in idle, a possibility 687 * handled by irq_enter() and irq_exit().) 688 * 689 * We crowbar the ->dynticks_nesting field to zero to allow for 690 * the possibility of usermode upcalls having messed up our count 691 * of interrupt nesting level during the prior busy period. 692 */ 693 void rcu_idle_enter(void) 694 { 695 unsigned long flags; 696 697 local_irq_save(flags); 698 rcu_eqs_enter(false); 699 rcu_sysidle_enter(0); 700 local_irq_restore(flags); 701 } 702 EXPORT_SYMBOL_GPL(rcu_idle_enter); 703 704 #ifdef CONFIG_RCU_USER_QS 705 /** 706 * rcu_user_enter - inform RCU that we are resuming userspace. 707 * 708 * Enter RCU idle mode right before resuming userspace. No use of RCU 709 * is permitted between this call and rcu_user_exit(). This way the 710 * CPU doesn't need to maintain the tick for RCU maintenance purposes 711 * when the CPU runs in userspace. 712 */ 713 void rcu_user_enter(void) 714 { 715 rcu_eqs_enter(1); 716 } 717 #endif /* CONFIG_RCU_USER_QS */ 718 719 /** 720 * rcu_irq_exit - inform RCU that current CPU is exiting irq towards idle 721 * 722 * Exit from an interrupt handler, which might possibly result in entering 723 * idle mode, in other words, leaving the mode in which read-side critical 724 * sections can occur. 725 * 726 * This code assumes that the idle loop never does anything that might 727 * result in unbalanced calls to irq_enter() and irq_exit(). If your 728 * architecture violates this assumption, RCU will give you what you 729 * deserve, good and hard. But very infrequently and irreproducibly. 730 * 731 * Use things like work queues to work around this limitation. 732 * 733 * You have been warned. 734 */ 735 void rcu_irq_exit(void) 736 { 737 unsigned long flags; 738 long long oldval; 739 struct rcu_dynticks *rdtp; 740 741 local_irq_save(flags); 742 rdtp = this_cpu_ptr(&rcu_dynticks); 743 oldval = rdtp->dynticks_nesting; 744 rdtp->dynticks_nesting--; 745 WARN_ON_ONCE(IS_ENABLED(CONFIG_RCU_EQS_DEBUG) && 746 rdtp->dynticks_nesting < 0); 747 if (rdtp->dynticks_nesting) 748 trace_rcu_dyntick(TPS("--="), oldval, rdtp->dynticks_nesting); 749 else 750 rcu_eqs_enter_common(oldval, true); 751 rcu_sysidle_enter(1); 752 local_irq_restore(flags); 753 } 754 755 /* 756 * rcu_eqs_exit_common - current CPU moving away from extended quiescent state 757 * 758 * If the new value of the ->dynticks_nesting counter was previously zero, 759 * we really have exited idle, and must do the appropriate accounting. 760 * The caller must have disabled interrupts. 761 */ 762 static void rcu_eqs_exit_common(long long oldval, int user) 763 { 764 struct rcu_dynticks *rdtp = this_cpu_ptr(&rcu_dynticks); 765 766 rcu_dynticks_task_exit(); 767 smp_mb__before_atomic(); /* Force ordering w/previous sojourn. */ 768 atomic_inc(&rdtp->dynticks); 769 /* CPUs seeing atomic_inc() must see later RCU read-side crit sects */ 770 smp_mb__after_atomic(); /* See above. */ 771 WARN_ON_ONCE(IS_ENABLED(CONFIG_RCU_EQS_DEBUG) && 772 !(atomic_read(&rdtp->dynticks) & 0x1)); 773 rcu_cleanup_after_idle(); 774 trace_rcu_dyntick(TPS("End"), oldval, rdtp->dynticks_nesting); 775 if (IS_ENABLED(CONFIG_RCU_EQS_DEBUG) && 776 !user && !is_idle_task(current)) { 777 struct task_struct *idle __maybe_unused = 778 idle_task(smp_processor_id()); 779 780 trace_rcu_dyntick(TPS("Error on exit: not idle task"), 781 oldval, rdtp->dynticks_nesting); 782 ftrace_dump(DUMP_ORIG); 783 WARN_ONCE(1, "Current pid: %d comm: %s / Idle pid: %d comm: %s", 784 current->pid, current->comm, 785 idle->pid, idle->comm); /* must be idle task! */ 786 } 787 } 788 789 /* 790 * Exit an RCU extended quiescent state, which can be either the 791 * idle loop or adaptive-tickless usermode execution. 792 */ 793 static void rcu_eqs_exit(bool user) 794 { 795 struct rcu_dynticks *rdtp; 796 long long oldval; 797 798 rdtp = this_cpu_ptr(&rcu_dynticks); 799 oldval = rdtp->dynticks_nesting; 800 WARN_ON_ONCE(IS_ENABLED(CONFIG_RCU_EQS_DEBUG) && oldval < 0); 801 if (oldval & DYNTICK_TASK_NEST_MASK) { 802 rdtp->dynticks_nesting += DYNTICK_TASK_NEST_VALUE; 803 } else { 804 rdtp->dynticks_nesting = DYNTICK_TASK_EXIT_IDLE; 805 rcu_eqs_exit_common(oldval, user); 806 } 807 } 808 809 /** 810 * rcu_idle_exit - inform RCU that current CPU is leaving idle 811 * 812 * Exit idle mode, in other words, -enter- the mode in which RCU 813 * read-side critical sections can occur. 814 * 815 * We crowbar the ->dynticks_nesting field to DYNTICK_TASK_NEST to 816 * allow for the possibility of usermode upcalls messing up our count 817 * of interrupt nesting level during the busy period that is just 818 * now starting. 819 */ 820 void rcu_idle_exit(void) 821 { 822 unsigned long flags; 823 824 local_irq_save(flags); 825 rcu_eqs_exit(false); 826 rcu_sysidle_exit(0); 827 local_irq_restore(flags); 828 } 829 EXPORT_SYMBOL_GPL(rcu_idle_exit); 830 831 #ifdef CONFIG_RCU_USER_QS 832 /** 833 * rcu_user_exit - inform RCU that we are exiting userspace. 834 * 835 * Exit RCU idle mode while entering the kernel because it can 836 * run a RCU read side critical section anytime. 837 */ 838 void rcu_user_exit(void) 839 { 840 rcu_eqs_exit(1); 841 } 842 #endif /* CONFIG_RCU_USER_QS */ 843 844 /** 845 * rcu_irq_enter - inform RCU that current CPU is entering irq away from idle 846 * 847 * Enter an interrupt handler, which might possibly result in exiting 848 * idle mode, in other words, entering the mode in which read-side critical 849 * sections can occur. 850 * 851 * Note that the Linux kernel is fully capable of entering an interrupt 852 * handler that it never exits, for example when doing upcalls to 853 * user mode! This code assumes that the idle loop never does upcalls to 854 * user mode. If your architecture does do upcalls from the idle loop (or 855 * does anything else that results in unbalanced calls to the irq_enter() 856 * and irq_exit() functions), RCU will give you what you deserve, good 857 * and hard. But very infrequently and irreproducibly. 858 * 859 * Use things like work queues to work around this limitation. 860 * 861 * You have been warned. 862 */ 863 void rcu_irq_enter(void) 864 { 865 unsigned long flags; 866 struct rcu_dynticks *rdtp; 867 long long oldval; 868 869 local_irq_save(flags); 870 rdtp = this_cpu_ptr(&rcu_dynticks); 871 oldval = rdtp->dynticks_nesting; 872 rdtp->dynticks_nesting++; 873 WARN_ON_ONCE(IS_ENABLED(CONFIG_RCU_EQS_DEBUG) && 874 rdtp->dynticks_nesting == 0); 875 if (oldval) 876 trace_rcu_dyntick(TPS("++="), oldval, rdtp->dynticks_nesting); 877 else 878 rcu_eqs_exit_common(oldval, true); 879 rcu_sysidle_exit(1); 880 local_irq_restore(flags); 881 } 882 883 /** 884 * rcu_nmi_enter - inform RCU of entry to NMI context 885 * 886 * If the CPU was idle from RCU's viewpoint, update rdtp->dynticks and 887 * rdtp->dynticks_nmi_nesting to let the RCU grace-period handling know 888 * that the CPU is active. This implementation permits nested NMIs, as 889 * long as the nesting level does not overflow an int. (You will probably 890 * run out of stack space first.) 891 */ 892 void rcu_nmi_enter(void) 893 { 894 struct rcu_dynticks *rdtp = this_cpu_ptr(&rcu_dynticks); 895 int incby = 2; 896 897 /* Complain about underflow. */ 898 WARN_ON_ONCE(rdtp->dynticks_nmi_nesting < 0); 899 900 /* 901 * If idle from RCU viewpoint, atomically increment ->dynticks 902 * to mark non-idle and increment ->dynticks_nmi_nesting by one. 903 * Otherwise, increment ->dynticks_nmi_nesting by two. This means 904 * if ->dynticks_nmi_nesting is equal to one, we are guaranteed 905 * to be in the outermost NMI handler that interrupted an RCU-idle 906 * period (observation due to Andy Lutomirski). 907 */ 908 if (!(atomic_read(&rdtp->dynticks) & 0x1)) { 909 smp_mb__before_atomic(); /* Force delay from prior write. */ 910 atomic_inc(&rdtp->dynticks); 911 /* atomic_inc() before later RCU read-side crit sects */ 912 smp_mb__after_atomic(); /* See above. */ 913 WARN_ON_ONCE(!(atomic_read(&rdtp->dynticks) & 0x1)); 914 incby = 1; 915 } 916 rdtp->dynticks_nmi_nesting += incby; 917 barrier(); 918 } 919 920 /** 921 * rcu_nmi_exit - inform RCU of exit from NMI context 922 * 923 * If we are returning from the outermost NMI handler that interrupted an 924 * RCU-idle period, update rdtp->dynticks and rdtp->dynticks_nmi_nesting 925 * to let the RCU grace-period handling know that the CPU is back to 926 * being RCU-idle. 927 */ 928 void rcu_nmi_exit(void) 929 { 930 struct rcu_dynticks *rdtp = this_cpu_ptr(&rcu_dynticks); 931 932 /* 933 * Check for ->dynticks_nmi_nesting underflow and bad ->dynticks. 934 * (We are exiting an NMI handler, so RCU better be paying attention 935 * to us!) 936 */ 937 WARN_ON_ONCE(rdtp->dynticks_nmi_nesting <= 0); 938 WARN_ON_ONCE(!(atomic_read(&rdtp->dynticks) & 0x1)); 939 940 /* 941 * If the nesting level is not 1, the CPU wasn't RCU-idle, so 942 * leave it in non-RCU-idle state. 943 */ 944 if (rdtp->dynticks_nmi_nesting != 1) { 945 rdtp->dynticks_nmi_nesting -= 2; 946 return; 947 } 948 949 /* This NMI interrupted an RCU-idle CPU, restore RCU-idleness. */ 950 rdtp->dynticks_nmi_nesting = 0; 951 /* CPUs seeing atomic_inc() must see prior RCU read-side crit sects */ 952 smp_mb__before_atomic(); /* See above. */ 953 atomic_inc(&rdtp->dynticks); 954 smp_mb__after_atomic(); /* Force delay to next write. */ 955 WARN_ON_ONCE(atomic_read(&rdtp->dynticks) & 0x1); 956 } 957 958 /** 959 * __rcu_is_watching - are RCU read-side critical sections safe? 960 * 961 * Return true if RCU is watching the running CPU, which means that 962 * this CPU can safely enter RCU read-side critical sections. Unlike 963 * rcu_is_watching(), the caller of __rcu_is_watching() must have at 964 * least disabled preemption. 965 */ 966 bool notrace __rcu_is_watching(void) 967 { 968 return atomic_read(this_cpu_ptr(&rcu_dynticks.dynticks)) & 0x1; 969 } 970 971 /** 972 * rcu_is_watching - see if RCU thinks that the current CPU is idle 973 * 974 * If the current CPU is in its idle loop and is neither in an interrupt 975 * or NMI handler, return true. 976 */ 977 bool notrace rcu_is_watching(void) 978 { 979 bool ret; 980 981 preempt_disable(); 982 ret = __rcu_is_watching(); 983 preempt_enable(); 984 return ret; 985 } 986 EXPORT_SYMBOL_GPL(rcu_is_watching); 987 988 #if defined(CONFIG_PROVE_RCU) && defined(CONFIG_HOTPLUG_CPU) 989 990 /* 991 * Is the current CPU online? Disable preemption to avoid false positives 992 * that could otherwise happen due to the current CPU number being sampled, 993 * this task being preempted, its old CPU being taken offline, resuming 994 * on some other CPU, then determining that its old CPU is now offline. 995 * It is OK to use RCU on an offline processor during initial boot, hence 996 * the check for rcu_scheduler_fully_active. Note also that it is OK 997 * for a CPU coming online to use RCU for one jiffy prior to marking itself 998 * online in the cpu_online_mask. Similarly, it is OK for a CPU going 999 * offline to continue to use RCU for one jiffy after marking itself 1000 * offline in the cpu_online_mask. This leniency is necessary given the 1001 * non-atomic nature of the online and offline processing, for example, 1002 * the fact that a CPU enters the scheduler after completing the CPU_DYING 1003 * notifiers. 1004 * 1005 * This is also why RCU internally marks CPUs online during the 1006 * CPU_UP_PREPARE phase and offline during the CPU_DEAD phase. 1007 * 1008 * Disable checking if in an NMI handler because we cannot safely report 1009 * errors from NMI handlers anyway. 1010 */ 1011 bool rcu_lockdep_current_cpu_online(void) 1012 { 1013 struct rcu_data *rdp; 1014 struct rcu_node *rnp; 1015 bool ret; 1016 1017 if (in_nmi()) 1018 return true; 1019 preempt_disable(); 1020 rdp = this_cpu_ptr(&rcu_sched_data); 1021 rnp = rdp->mynode; 1022 ret = (rdp->grpmask & rcu_rnp_online_cpus(rnp)) || 1023 !rcu_scheduler_fully_active; 1024 preempt_enable(); 1025 return ret; 1026 } 1027 EXPORT_SYMBOL_GPL(rcu_lockdep_current_cpu_online); 1028 1029 #endif /* #if defined(CONFIG_PROVE_RCU) && defined(CONFIG_HOTPLUG_CPU) */ 1030 1031 /** 1032 * rcu_is_cpu_rrupt_from_idle - see if idle or immediately interrupted from idle 1033 * 1034 * If the current CPU is idle or running at a first-level (not nested) 1035 * interrupt from idle, return true. The caller must have at least 1036 * disabled preemption. 1037 */ 1038 static int rcu_is_cpu_rrupt_from_idle(void) 1039 { 1040 return __this_cpu_read(rcu_dynticks.dynticks_nesting) <= 1; 1041 } 1042 1043 /* 1044 * Snapshot the specified CPU's dynticks counter so that we can later 1045 * credit them with an implicit quiescent state. Return 1 if this CPU 1046 * is in dynticks idle mode, which is an extended quiescent state. 1047 */ 1048 static int dyntick_save_progress_counter(struct rcu_data *rdp, 1049 bool *isidle, unsigned long *maxj) 1050 { 1051 rdp->dynticks_snap = atomic_add_return(0, &rdp->dynticks->dynticks); 1052 rcu_sysidle_check_cpu(rdp, isidle, maxj); 1053 if ((rdp->dynticks_snap & 0x1) == 0) { 1054 trace_rcu_fqs(rdp->rsp->name, rdp->gpnum, rdp->cpu, TPS("dti")); 1055 return 1; 1056 } else { 1057 if (ULONG_CMP_LT(READ_ONCE(rdp->gpnum) + ULONG_MAX / 4, 1058 rdp->mynode->gpnum)) 1059 WRITE_ONCE(rdp->gpwrap, true); 1060 return 0; 1061 } 1062 } 1063 1064 /* 1065 * Return true if the specified CPU has passed through a quiescent 1066 * state by virtue of being in or having passed through an dynticks 1067 * idle state since the last call to dyntick_save_progress_counter() 1068 * for this same CPU, or by virtue of having been offline. 1069 */ 1070 static int rcu_implicit_dynticks_qs(struct rcu_data *rdp, 1071 bool *isidle, unsigned long *maxj) 1072 { 1073 unsigned int curr; 1074 int *rcrmp; 1075 unsigned int snap; 1076 1077 curr = (unsigned int)atomic_add_return(0, &rdp->dynticks->dynticks); 1078 snap = (unsigned int)rdp->dynticks_snap; 1079 1080 /* 1081 * If the CPU passed through or entered a dynticks idle phase with 1082 * no active irq/NMI handlers, then we can safely pretend that the CPU 1083 * already acknowledged the request to pass through a quiescent 1084 * state. Either way, that CPU cannot possibly be in an RCU 1085 * read-side critical section that started before the beginning 1086 * of the current RCU grace period. 1087 */ 1088 if ((curr & 0x1) == 0 || UINT_CMP_GE(curr, snap + 2)) { 1089 trace_rcu_fqs(rdp->rsp->name, rdp->gpnum, rdp->cpu, TPS("dti")); 1090 rdp->dynticks_fqs++; 1091 return 1; 1092 } 1093 1094 /* 1095 * Check for the CPU being offline, but only if the grace period 1096 * is old enough. We don't need to worry about the CPU changing 1097 * state: If we see it offline even once, it has been through a 1098 * quiescent state. 1099 * 1100 * The reason for insisting that the grace period be at least 1101 * one jiffy old is that CPUs that are not quite online and that 1102 * have just gone offline can still execute RCU read-side critical 1103 * sections. 1104 */ 1105 if (ULONG_CMP_GE(rdp->rsp->gp_start + 2, jiffies)) 1106 return 0; /* Grace period is not old enough. */ 1107 barrier(); 1108 if (cpu_is_offline(rdp->cpu)) { 1109 trace_rcu_fqs(rdp->rsp->name, rdp->gpnum, rdp->cpu, TPS("ofl")); 1110 rdp->offline_fqs++; 1111 return 1; 1112 } 1113 1114 /* 1115 * A CPU running for an extended time within the kernel can 1116 * delay RCU grace periods. When the CPU is in NO_HZ_FULL mode, 1117 * even context-switching back and forth between a pair of 1118 * in-kernel CPU-bound tasks cannot advance grace periods. 1119 * So if the grace period is old enough, make the CPU pay attention. 1120 * Note that the unsynchronized assignments to the per-CPU 1121 * rcu_sched_qs_mask variable are safe. Yes, setting of 1122 * bits can be lost, but they will be set again on the next 1123 * force-quiescent-state pass. So lost bit sets do not result 1124 * in incorrect behavior, merely in a grace period lasting 1125 * a few jiffies longer than it might otherwise. Because 1126 * there are at most four threads involved, and because the 1127 * updates are only once every few jiffies, the probability of 1128 * lossage (and thus of slight grace-period extension) is 1129 * quite low. 1130 * 1131 * Note that if the jiffies_till_sched_qs boot/sysfs parameter 1132 * is set too high, we override with half of the RCU CPU stall 1133 * warning delay. 1134 */ 1135 rcrmp = &per_cpu(rcu_sched_qs_mask, rdp->cpu); 1136 if (ULONG_CMP_GE(jiffies, 1137 rdp->rsp->gp_start + jiffies_till_sched_qs) || 1138 ULONG_CMP_GE(jiffies, rdp->rsp->jiffies_resched)) { 1139 if (!(READ_ONCE(*rcrmp) & rdp->rsp->flavor_mask)) { 1140 WRITE_ONCE(rdp->cond_resched_completed, 1141 READ_ONCE(rdp->mynode->completed)); 1142 smp_mb(); /* ->cond_resched_completed before *rcrmp. */ 1143 WRITE_ONCE(*rcrmp, 1144 READ_ONCE(*rcrmp) + rdp->rsp->flavor_mask); 1145 resched_cpu(rdp->cpu); /* Force CPU into scheduler. */ 1146 rdp->rsp->jiffies_resched += 5; /* Enable beating. */ 1147 } else if (ULONG_CMP_GE(jiffies, rdp->rsp->jiffies_resched)) { 1148 /* Time to beat on that CPU again! */ 1149 resched_cpu(rdp->cpu); /* Force CPU into scheduler. */ 1150 rdp->rsp->jiffies_resched += 5; /* Re-enable beating. */ 1151 } 1152 } 1153 1154 return 0; 1155 } 1156 1157 static void record_gp_stall_check_time(struct rcu_state *rsp) 1158 { 1159 unsigned long j = jiffies; 1160 unsigned long j1; 1161 1162 rsp->gp_start = j; 1163 smp_wmb(); /* Record start time before stall time. */ 1164 j1 = rcu_jiffies_till_stall_check(); 1165 WRITE_ONCE(rsp->jiffies_stall, j + j1); 1166 rsp->jiffies_resched = j + j1 / 2; 1167 rsp->n_force_qs_gpstart = READ_ONCE(rsp->n_force_qs); 1168 } 1169 1170 /* 1171 * Complain about starvation of grace-period kthread. 1172 */ 1173 static void rcu_check_gp_kthread_starvation(struct rcu_state *rsp) 1174 { 1175 unsigned long gpa; 1176 unsigned long j; 1177 1178 j = jiffies; 1179 gpa = READ_ONCE(rsp->gp_activity); 1180 if (j - gpa > 2 * HZ) 1181 pr_err("%s kthread starved for %ld jiffies! g%lu c%lu f%#x\n", 1182 rsp->name, j - gpa, 1183 rsp->gpnum, rsp->completed, rsp->gp_flags); 1184 } 1185 1186 /* 1187 * Dump stacks of all tasks running on stalled CPUs. 1188 */ 1189 static void rcu_dump_cpu_stacks(struct rcu_state *rsp) 1190 { 1191 int cpu; 1192 unsigned long flags; 1193 struct rcu_node *rnp; 1194 1195 rcu_for_each_leaf_node(rsp, rnp) { 1196 raw_spin_lock_irqsave(&rnp->lock, flags); 1197 if (rnp->qsmask != 0) { 1198 for (cpu = 0; cpu <= rnp->grphi - rnp->grplo; cpu++) 1199 if (rnp->qsmask & (1UL << cpu)) 1200 dump_cpu_task(rnp->grplo + cpu); 1201 } 1202 raw_spin_unlock_irqrestore(&rnp->lock, flags); 1203 } 1204 } 1205 1206 static void print_other_cpu_stall(struct rcu_state *rsp, unsigned long gpnum) 1207 { 1208 int cpu; 1209 long delta; 1210 unsigned long flags; 1211 unsigned long gpa; 1212 unsigned long j; 1213 int ndetected = 0; 1214 struct rcu_node *rnp = rcu_get_root(rsp); 1215 long totqlen = 0; 1216 1217 /* Only let one CPU complain about others per time interval. */ 1218 1219 raw_spin_lock_irqsave(&rnp->lock, flags); 1220 delta = jiffies - READ_ONCE(rsp->jiffies_stall); 1221 if (delta < RCU_STALL_RAT_DELAY || !rcu_gp_in_progress(rsp)) { 1222 raw_spin_unlock_irqrestore(&rnp->lock, flags); 1223 return; 1224 } 1225 WRITE_ONCE(rsp->jiffies_stall, 1226 jiffies + 3 * rcu_jiffies_till_stall_check() + 3); 1227 raw_spin_unlock_irqrestore(&rnp->lock, flags); 1228 1229 /* 1230 * OK, time to rat on our buddy... 1231 * See Documentation/RCU/stallwarn.txt for info on how to debug 1232 * RCU CPU stall warnings. 1233 */ 1234 pr_err("INFO: %s detected stalls on CPUs/tasks:", 1235 rsp->name); 1236 print_cpu_stall_info_begin(); 1237 rcu_for_each_leaf_node(rsp, rnp) { 1238 raw_spin_lock_irqsave(&rnp->lock, flags); 1239 ndetected += rcu_print_task_stall(rnp); 1240 if (rnp->qsmask != 0) { 1241 for (cpu = 0; cpu <= rnp->grphi - rnp->grplo; cpu++) 1242 if (rnp->qsmask & (1UL << cpu)) { 1243 print_cpu_stall_info(rsp, 1244 rnp->grplo + cpu); 1245 ndetected++; 1246 } 1247 } 1248 raw_spin_unlock_irqrestore(&rnp->lock, flags); 1249 } 1250 1251 print_cpu_stall_info_end(); 1252 for_each_possible_cpu(cpu) 1253 totqlen += per_cpu_ptr(rsp->rda, cpu)->qlen; 1254 pr_cont("(detected by %d, t=%ld jiffies, g=%ld, c=%ld, q=%lu)\n", 1255 smp_processor_id(), (long)(jiffies - rsp->gp_start), 1256 (long)rsp->gpnum, (long)rsp->completed, totqlen); 1257 if (ndetected) { 1258 rcu_dump_cpu_stacks(rsp); 1259 } else { 1260 if (READ_ONCE(rsp->gpnum) != gpnum || 1261 READ_ONCE(rsp->completed) == gpnum) { 1262 pr_err("INFO: Stall ended before state dump start\n"); 1263 } else { 1264 j = jiffies; 1265 gpa = READ_ONCE(rsp->gp_activity); 1266 pr_err("All QSes seen, last %s kthread activity %ld (%ld-%ld), jiffies_till_next_fqs=%ld, root ->qsmask %#lx\n", 1267 rsp->name, j - gpa, j, gpa, 1268 jiffies_till_next_fqs, 1269 rcu_get_root(rsp)->qsmask); 1270 /* In this case, the current CPU might be at fault. */ 1271 sched_show_task(current); 1272 } 1273 } 1274 1275 /* Complain about tasks blocking the grace period. */ 1276 rcu_print_detail_task_stall(rsp); 1277 1278 rcu_check_gp_kthread_starvation(rsp); 1279 1280 force_quiescent_state(rsp); /* Kick them all. */ 1281 } 1282 1283 static void print_cpu_stall(struct rcu_state *rsp) 1284 { 1285 int cpu; 1286 unsigned long flags; 1287 struct rcu_node *rnp = rcu_get_root(rsp); 1288 long totqlen = 0; 1289 1290 /* 1291 * OK, time to rat on ourselves... 1292 * See Documentation/RCU/stallwarn.txt for info on how to debug 1293 * RCU CPU stall warnings. 1294 */ 1295 pr_err("INFO: %s self-detected stall on CPU", rsp->name); 1296 print_cpu_stall_info_begin(); 1297 print_cpu_stall_info(rsp, smp_processor_id()); 1298 print_cpu_stall_info_end(); 1299 for_each_possible_cpu(cpu) 1300 totqlen += per_cpu_ptr(rsp->rda, cpu)->qlen; 1301 pr_cont(" (t=%lu jiffies g=%ld c=%ld q=%lu)\n", 1302 jiffies - rsp->gp_start, 1303 (long)rsp->gpnum, (long)rsp->completed, totqlen); 1304 1305 rcu_check_gp_kthread_starvation(rsp); 1306 1307 rcu_dump_cpu_stacks(rsp); 1308 1309 raw_spin_lock_irqsave(&rnp->lock, flags); 1310 if (ULONG_CMP_GE(jiffies, READ_ONCE(rsp->jiffies_stall))) 1311 WRITE_ONCE(rsp->jiffies_stall, 1312 jiffies + 3 * rcu_jiffies_till_stall_check() + 3); 1313 raw_spin_unlock_irqrestore(&rnp->lock, flags); 1314 1315 /* 1316 * Attempt to revive the RCU machinery by forcing a context switch. 1317 * 1318 * A context switch would normally allow the RCU state machine to make 1319 * progress and it could be we're stuck in kernel space without context 1320 * switches for an entirely unreasonable amount of time. 1321 */ 1322 resched_cpu(smp_processor_id()); 1323 } 1324 1325 static void check_cpu_stall(struct rcu_state *rsp, struct rcu_data *rdp) 1326 { 1327 unsigned long completed; 1328 unsigned long gpnum; 1329 unsigned long gps; 1330 unsigned long j; 1331 unsigned long js; 1332 struct rcu_node *rnp; 1333 1334 if (rcu_cpu_stall_suppress || !rcu_gp_in_progress(rsp)) 1335 return; 1336 j = jiffies; 1337 1338 /* 1339 * Lots of memory barriers to reject false positives. 1340 * 1341 * The idea is to pick up rsp->gpnum, then rsp->jiffies_stall, 1342 * then rsp->gp_start, and finally rsp->completed. These values 1343 * are updated in the opposite order with memory barriers (or 1344 * equivalent) during grace-period initialization and cleanup. 1345 * Now, a false positive can occur if we get an new value of 1346 * rsp->gp_start and a old value of rsp->jiffies_stall. But given 1347 * the memory barriers, the only way that this can happen is if one 1348 * grace period ends and another starts between these two fetches. 1349 * Detect this by comparing rsp->completed with the previous fetch 1350 * from rsp->gpnum. 1351 * 1352 * Given this check, comparisons of jiffies, rsp->jiffies_stall, 1353 * and rsp->gp_start suffice to forestall false positives. 1354 */ 1355 gpnum = READ_ONCE(rsp->gpnum); 1356 smp_rmb(); /* Pick up ->gpnum first... */ 1357 js = READ_ONCE(rsp->jiffies_stall); 1358 smp_rmb(); /* ...then ->jiffies_stall before the rest... */ 1359 gps = READ_ONCE(rsp->gp_start); 1360 smp_rmb(); /* ...and finally ->gp_start before ->completed. */ 1361 completed = READ_ONCE(rsp->completed); 1362 if (ULONG_CMP_GE(completed, gpnum) || 1363 ULONG_CMP_LT(j, js) || 1364 ULONG_CMP_GE(gps, js)) 1365 return; /* No stall or GP completed since entering function. */ 1366 rnp = rdp->mynode; 1367 if (rcu_gp_in_progress(rsp) && 1368 (READ_ONCE(rnp->qsmask) & rdp->grpmask)) { 1369 1370 /* We haven't checked in, so go dump stack. */ 1371 print_cpu_stall(rsp); 1372 1373 } else if (rcu_gp_in_progress(rsp) && 1374 ULONG_CMP_GE(j, js + RCU_STALL_RAT_DELAY)) { 1375 1376 /* They had a few time units to dump stack, so complain. */ 1377 print_other_cpu_stall(rsp, gpnum); 1378 } 1379 } 1380 1381 /** 1382 * rcu_cpu_stall_reset - prevent further stall warnings in current grace period 1383 * 1384 * Set the stall-warning timeout way off into the future, thus preventing 1385 * any RCU CPU stall-warning messages from appearing in the current set of 1386 * RCU grace periods. 1387 * 1388 * The caller must disable hard irqs. 1389 */ 1390 void rcu_cpu_stall_reset(void) 1391 { 1392 struct rcu_state *rsp; 1393 1394 for_each_rcu_flavor(rsp) 1395 WRITE_ONCE(rsp->jiffies_stall, jiffies + ULONG_MAX / 2); 1396 } 1397 1398 /* 1399 * Initialize the specified rcu_data structure's default callback list 1400 * to empty. The default callback list is the one that is not used by 1401 * no-callbacks CPUs. 1402 */ 1403 static void init_default_callback_list(struct rcu_data *rdp) 1404 { 1405 int i; 1406 1407 rdp->nxtlist = NULL; 1408 for (i = 0; i < RCU_NEXT_SIZE; i++) 1409 rdp->nxttail[i] = &rdp->nxtlist; 1410 } 1411 1412 /* 1413 * Initialize the specified rcu_data structure's callback list to empty. 1414 */ 1415 static void init_callback_list(struct rcu_data *rdp) 1416 { 1417 if (init_nocb_callback_list(rdp)) 1418 return; 1419 init_default_callback_list(rdp); 1420 } 1421 1422 /* 1423 * Determine the value that ->completed will have at the end of the 1424 * next subsequent grace period. This is used to tag callbacks so that 1425 * a CPU can invoke callbacks in a timely fashion even if that CPU has 1426 * been dyntick-idle for an extended period with callbacks under the 1427 * influence of RCU_FAST_NO_HZ. 1428 * 1429 * The caller must hold rnp->lock with interrupts disabled. 1430 */ 1431 static unsigned long rcu_cbs_completed(struct rcu_state *rsp, 1432 struct rcu_node *rnp) 1433 { 1434 /* 1435 * If RCU is idle, we just wait for the next grace period. 1436 * But we can only be sure that RCU is idle if we are looking 1437 * at the root rcu_node structure -- otherwise, a new grace 1438 * period might have started, but just not yet gotten around 1439 * to initializing the current non-root rcu_node structure. 1440 */ 1441 if (rcu_get_root(rsp) == rnp && rnp->gpnum == rnp->completed) 1442 return rnp->completed + 1; 1443 1444 /* 1445 * Otherwise, wait for a possible partial grace period and 1446 * then the subsequent full grace period. 1447 */ 1448 return rnp->completed + 2; 1449 } 1450 1451 /* 1452 * Trace-event helper function for rcu_start_future_gp() and 1453 * rcu_nocb_wait_gp(). 1454 */ 1455 static void trace_rcu_future_gp(struct rcu_node *rnp, struct rcu_data *rdp, 1456 unsigned long c, const char *s) 1457 { 1458 trace_rcu_future_grace_period(rdp->rsp->name, rnp->gpnum, 1459 rnp->completed, c, rnp->level, 1460 rnp->grplo, rnp->grphi, s); 1461 } 1462 1463 /* 1464 * Start some future grace period, as needed to handle newly arrived 1465 * callbacks. The required future grace periods are recorded in each 1466 * rcu_node structure's ->need_future_gp field. Returns true if there 1467 * is reason to awaken the grace-period kthread. 1468 * 1469 * The caller must hold the specified rcu_node structure's ->lock. 1470 */ 1471 static bool __maybe_unused 1472 rcu_start_future_gp(struct rcu_node *rnp, struct rcu_data *rdp, 1473 unsigned long *c_out) 1474 { 1475 unsigned long c; 1476 int i; 1477 bool ret = false; 1478 struct rcu_node *rnp_root = rcu_get_root(rdp->rsp); 1479 1480 /* 1481 * Pick up grace-period number for new callbacks. If this 1482 * grace period is already marked as needed, return to the caller. 1483 */ 1484 c = rcu_cbs_completed(rdp->rsp, rnp); 1485 trace_rcu_future_gp(rnp, rdp, c, TPS("Startleaf")); 1486 if (rnp->need_future_gp[c & 0x1]) { 1487 trace_rcu_future_gp(rnp, rdp, c, TPS("Prestartleaf")); 1488 goto out; 1489 } 1490 1491 /* 1492 * If either this rcu_node structure or the root rcu_node structure 1493 * believe that a grace period is in progress, then we must wait 1494 * for the one following, which is in "c". Because our request 1495 * will be noticed at the end of the current grace period, we don't 1496 * need to explicitly start one. We only do the lockless check 1497 * of rnp_root's fields if the current rcu_node structure thinks 1498 * there is no grace period in flight, and because we hold rnp->lock, 1499 * the only possible change is when rnp_root's two fields are 1500 * equal, in which case rnp_root->gpnum might be concurrently 1501 * incremented. But that is OK, as it will just result in our 1502 * doing some extra useless work. 1503 */ 1504 if (rnp->gpnum != rnp->completed || 1505 READ_ONCE(rnp_root->gpnum) != READ_ONCE(rnp_root->completed)) { 1506 rnp->need_future_gp[c & 0x1]++; 1507 trace_rcu_future_gp(rnp, rdp, c, TPS("Startedleaf")); 1508 goto out; 1509 } 1510 1511 /* 1512 * There might be no grace period in progress. If we don't already 1513 * hold it, acquire the root rcu_node structure's lock in order to 1514 * start one (if needed). 1515 */ 1516 if (rnp != rnp_root) { 1517 raw_spin_lock(&rnp_root->lock); 1518 smp_mb__after_unlock_lock(); 1519 } 1520 1521 /* 1522 * Get a new grace-period number. If there really is no grace 1523 * period in progress, it will be smaller than the one we obtained 1524 * earlier. Adjust callbacks as needed. Note that even no-CBs 1525 * CPUs have a ->nxtcompleted[] array, so no no-CBs checks needed. 1526 */ 1527 c = rcu_cbs_completed(rdp->rsp, rnp_root); 1528 for (i = RCU_DONE_TAIL; i < RCU_NEXT_TAIL; i++) 1529 if (ULONG_CMP_LT(c, rdp->nxtcompleted[i])) 1530 rdp->nxtcompleted[i] = c; 1531 1532 /* 1533 * If the needed for the required grace period is already 1534 * recorded, trace and leave. 1535 */ 1536 if (rnp_root->need_future_gp[c & 0x1]) { 1537 trace_rcu_future_gp(rnp, rdp, c, TPS("Prestartedroot")); 1538 goto unlock_out; 1539 } 1540 1541 /* Record the need for the future grace period. */ 1542 rnp_root->need_future_gp[c & 0x1]++; 1543 1544 /* If a grace period is not already in progress, start one. */ 1545 if (rnp_root->gpnum != rnp_root->completed) { 1546 trace_rcu_future_gp(rnp, rdp, c, TPS("Startedleafroot")); 1547 } else { 1548 trace_rcu_future_gp(rnp, rdp, c, TPS("Startedroot")); 1549 ret = rcu_start_gp_advanced(rdp->rsp, rnp_root, rdp); 1550 } 1551 unlock_out: 1552 if (rnp != rnp_root) 1553 raw_spin_unlock(&rnp_root->lock); 1554 out: 1555 if (c_out != NULL) 1556 *c_out = c; 1557 return ret; 1558 } 1559 1560 /* 1561 * Clean up any old requests for the just-ended grace period. Also return 1562 * whether any additional grace periods have been requested. Also invoke 1563 * rcu_nocb_gp_cleanup() in order to wake up any no-callbacks kthreads 1564 * waiting for this grace period to complete. 1565 */ 1566 static int rcu_future_gp_cleanup(struct rcu_state *rsp, struct rcu_node *rnp) 1567 { 1568 int c = rnp->completed; 1569 int needmore; 1570 struct rcu_data *rdp = this_cpu_ptr(rsp->rda); 1571 1572 rcu_nocb_gp_cleanup(rsp, rnp); 1573 rnp->need_future_gp[c & 0x1] = 0; 1574 needmore = rnp->need_future_gp[(c + 1) & 0x1]; 1575 trace_rcu_future_gp(rnp, rdp, c, 1576 needmore ? TPS("CleanupMore") : TPS("Cleanup")); 1577 return needmore; 1578 } 1579 1580 /* 1581 * Awaken the grace-period kthread for the specified flavor of RCU. 1582 * Don't do a self-awaken, and don't bother awakening when there is 1583 * nothing for the grace-period kthread to do (as in several CPUs 1584 * raced to awaken, and we lost), and finally don't try to awaken 1585 * a kthread that has not yet been created. 1586 */ 1587 static void rcu_gp_kthread_wake(struct rcu_state *rsp) 1588 { 1589 if (current == rsp->gp_kthread || 1590 !READ_ONCE(rsp->gp_flags) || 1591 !rsp->gp_kthread) 1592 return; 1593 wake_up(&rsp->gp_wq); 1594 } 1595 1596 /* 1597 * If there is room, assign a ->completed number to any callbacks on 1598 * this CPU that have not already been assigned. Also accelerate any 1599 * callbacks that were previously assigned a ->completed number that has 1600 * since proven to be too conservative, which can happen if callbacks get 1601 * assigned a ->completed number while RCU is idle, but with reference to 1602 * a non-root rcu_node structure. This function is idempotent, so it does 1603 * not hurt to call it repeatedly. Returns an flag saying that we should 1604 * awaken the RCU grace-period kthread. 1605 * 1606 * The caller must hold rnp->lock with interrupts disabled. 1607 */ 1608 static bool rcu_accelerate_cbs(struct rcu_state *rsp, struct rcu_node *rnp, 1609 struct rcu_data *rdp) 1610 { 1611 unsigned long c; 1612 int i; 1613 bool ret; 1614 1615 /* If the CPU has no callbacks, nothing to do. */ 1616 if (!rdp->nxttail[RCU_NEXT_TAIL] || !*rdp->nxttail[RCU_DONE_TAIL]) 1617 return false; 1618 1619 /* 1620 * Starting from the sublist containing the callbacks most 1621 * recently assigned a ->completed number and working down, find the 1622 * first sublist that is not assignable to an upcoming grace period. 1623 * Such a sublist has something in it (first two tests) and has 1624 * a ->completed number assigned that will complete sooner than 1625 * the ->completed number for newly arrived callbacks (last test). 1626 * 1627 * The key point is that any later sublist can be assigned the 1628 * same ->completed number as the newly arrived callbacks, which 1629 * means that the callbacks in any of these later sublist can be 1630 * grouped into a single sublist, whether or not they have already 1631 * been assigned a ->completed number. 1632 */ 1633 c = rcu_cbs_completed(rsp, rnp); 1634 for (i = RCU_NEXT_TAIL - 1; i > RCU_DONE_TAIL; i--) 1635 if (rdp->nxttail[i] != rdp->nxttail[i - 1] && 1636 !ULONG_CMP_GE(rdp->nxtcompleted[i], c)) 1637 break; 1638 1639 /* 1640 * If there are no sublist for unassigned callbacks, leave. 1641 * At the same time, advance "i" one sublist, so that "i" will 1642 * index into the sublist where all the remaining callbacks should 1643 * be grouped into. 1644 */ 1645 if (++i >= RCU_NEXT_TAIL) 1646 return false; 1647 1648 /* 1649 * Assign all subsequent callbacks' ->completed number to the next 1650 * full grace period and group them all in the sublist initially 1651 * indexed by "i". 1652 */ 1653 for (; i <= RCU_NEXT_TAIL; i++) { 1654 rdp->nxttail[i] = rdp->nxttail[RCU_NEXT_TAIL]; 1655 rdp->nxtcompleted[i] = c; 1656 } 1657 /* Record any needed additional grace periods. */ 1658 ret = rcu_start_future_gp(rnp, rdp, NULL); 1659 1660 /* Trace depending on how much we were able to accelerate. */ 1661 if (!*rdp->nxttail[RCU_WAIT_TAIL]) 1662 trace_rcu_grace_period(rsp->name, rdp->gpnum, TPS("AccWaitCB")); 1663 else 1664 trace_rcu_grace_period(rsp->name, rdp->gpnum, TPS("AccReadyCB")); 1665 return ret; 1666 } 1667 1668 /* 1669 * Move any callbacks whose grace period has completed to the 1670 * RCU_DONE_TAIL sublist, then compact the remaining sublists and 1671 * assign ->completed numbers to any callbacks in the RCU_NEXT_TAIL 1672 * sublist. This function is idempotent, so it does not hurt to 1673 * invoke it repeatedly. As long as it is not invoked -too- often... 1674 * Returns true if the RCU grace-period kthread needs to be awakened. 1675 * 1676 * The caller must hold rnp->lock with interrupts disabled. 1677 */ 1678 static bool rcu_advance_cbs(struct rcu_state *rsp, struct rcu_node *rnp, 1679 struct rcu_data *rdp) 1680 { 1681 int i, j; 1682 1683 /* If the CPU has no callbacks, nothing to do. */ 1684 if (!rdp->nxttail[RCU_NEXT_TAIL] || !*rdp->nxttail[RCU_DONE_TAIL]) 1685 return false; 1686 1687 /* 1688 * Find all callbacks whose ->completed numbers indicate that they 1689 * are ready to invoke, and put them into the RCU_DONE_TAIL sublist. 1690 */ 1691 for (i = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++) { 1692 if (ULONG_CMP_LT(rnp->completed, rdp->nxtcompleted[i])) 1693 break; 1694 rdp->nxttail[RCU_DONE_TAIL] = rdp->nxttail[i]; 1695 } 1696 /* Clean up any sublist tail pointers that were misordered above. */ 1697 for (j = RCU_WAIT_TAIL; j < i; j++) 1698 rdp->nxttail[j] = rdp->nxttail[RCU_DONE_TAIL]; 1699 1700 /* Copy down callbacks to fill in empty sublists. */ 1701 for (j = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++, j++) { 1702 if (rdp->nxttail[j] == rdp->nxttail[RCU_NEXT_TAIL]) 1703 break; 1704 rdp->nxttail[j] = rdp->nxttail[i]; 1705 rdp->nxtcompleted[j] = rdp->nxtcompleted[i]; 1706 } 1707 1708 /* Classify any remaining callbacks. */ 1709 return rcu_accelerate_cbs(rsp, rnp, rdp); 1710 } 1711 1712 /* 1713 * Update CPU-local rcu_data state to record the beginnings and ends of 1714 * grace periods. The caller must hold the ->lock of the leaf rcu_node 1715 * structure corresponding to the current CPU, and must have irqs disabled. 1716 * Returns true if the grace-period kthread needs to be awakened. 1717 */ 1718 static bool __note_gp_changes(struct rcu_state *rsp, struct rcu_node *rnp, 1719 struct rcu_data *rdp) 1720 { 1721 bool ret; 1722 1723 /* Handle the ends of any preceding grace periods first. */ 1724 if (rdp->completed == rnp->completed && 1725 !unlikely(READ_ONCE(rdp->gpwrap))) { 1726 1727 /* No grace period end, so just accelerate recent callbacks. */ 1728 ret = rcu_accelerate_cbs(rsp, rnp, rdp); 1729 1730 } else { 1731 1732 /* Advance callbacks. */ 1733 ret = rcu_advance_cbs(rsp, rnp, rdp); 1734 1735 /* Remember that we saw this grace-period completion. */ 1736 rdp->completed = rnp->completed; 1737 trace_rcu_grace_period(rsp->name, rdp->gpnum, TPS("cpuend")); 1738 } 1739 1740 if (rdp->gpnum != rnp->gpnum || unlikely(READ_ONCE(rdp->gpwrap))) { 1741 /* 1742 * If the current grace period is waiting for this CPU, 1743 * set up to detect a quiescent state, otherwise don't 1744 * go looking for one. 1745 */ 1746 rdp->gpnum = rnp->gpnum; 1747 trace_rcu_grace_period(rsp->name, rdp->gpnum, TPS("cpustart")); 1748 rdp->passed_quiesce = 0; 1749 rdp->rcu_qs_ctr_snap = __this_cpu_read(rcu_qs_ctr); 1750 rdp->qs_pending = !!(rnp->qsmask & rdp->grpmask); 1751 zero_cpu_stall_ticks(rdp); 1752 WRITE_ONCE(rdp->gpwrap, false); 1753 } 1754 return ret; 1755 } 1756 1757 static void note_gp_changes(struct rcu_state *rsp, struct rcu_data *rdp) 1758 { 1759 unsigned long flags; 1760 bool needwake; 1761 struct rcu_node *rnp; 1762 1763 local_irq_save(flags); 1764 rnp = rdp->mynode; 1765 if ((rdp->gpnum == READ_ONCE(rnp->gpnum) && 1766 rdp->completed == READ_ONCE(rnp->completed) && 1767 !unlikely(READ_ONCE(rdp->gpwrap))) || /* w/out lock. */ 1768 !raw_spin_trylock(&rnp->lock)) { /* irqs already off, so later. */ 1769 local_irq_restore(flags); 1770 return; 1771 } 1772 smp_mb__after_unlock_lock(); 1773 needwake = __note_gp_changes(rsp, rnp, rdp); 1774 raw_spin_unlock_irqrestore(&rnp->lock, flags); 1775 if (needwake) 1776 rcu_gp_kthread_wake(rsp); 1777 } 1778 1779 static void rcu_gp_slow(struct rcu_state *rsp, int delay) 1780 { 1781 if (delay > 0 && 1782 !(rsp->gpnum % (rcu_num_nodes * PER_RCU_NODE_PERIOD * delay))) 1783 schedule_timeout_uninterruptible(delay); 1784 } 1785 1786 /* 1787 * Initialize a new grace period. Return 0 if no grace period required. 1788 */ 1789 static int rcu_gp_init(struct rcu_state *rsp) 1790 { 1791 unsigned long oldmask; 1792 struct rcu_data *rdp; 1793 struct rcu_node *rnp = rcu_get_root(rsp); 1794 1795 WRITE_ONCE(rsp->gp_activity, jiffies); 1796 raw_spin_lock_irq(&rnp->lock); 1797 smp_mb__after_unlock_lock(); 1798 if (!READ_ONCE(rsp->gp_flags)) { 1799 /* Spurious wakeup, tell caller to go back to sleep. */ 1800 raw_spin_unlock_irq(&rnp->lock); 1801 return 0; 1802 } 1803 WRITE_ONCE(rsp->gp_flags, 0); /* Clear all flags: New grace period. */ 1804 1805 if (WARN_ON_ONCE(rcu_gp_in_progress(rsp))) { 1806 /* 1807 * Grace period already in progress, don't start another. 1808 * Not supposed to be able to happen. 1809 */ 1810 raw_spin_unlock_irq(&rnp->lock); 1811 return 0; 1812 } 1813 1814 /* Advance to a new grace period and initialize state. */ 1815 record_gp_stall_check_time(rsp); 1816 /* Record GP times before starting GP, hence smp_store_release(). */ 1817 smp_store_release(&rsp->gpnum, rsp->gpnum + 1); 1818 trace_rcu_grace_period(rsp->name, rsp->gpnum, TPS("start")); 1819 raw_spin_unlock_irq(&rnp->lock); 1820 1821 /* 1822 * Apply per-leaf buffered online and offline operations to the 1823 * rcu_node tree. Note that this new grace period need not wait 1824 * for subsequent online CPUs, and that quiescent-state forcing 1825 * will handle subsequent offline CPUs. 1826 */ 1827 rcu_for_each_leaf_node(rsp, rnp) { 1828 rcu_gp_slow(rsp, gp_preinit_delay); 1829 raw_spin_lock_irq(&rnp->lock); 1830 smp_mb__after_unlock_lock(); 1831 if (rnp->qsmaskinit == rnp->qsmaskinitnext && 1832 !rnp->wait_blkd_tasks) { 1833 /* Nothing to do on this leaf rcu_node structure. */ 1834 raw_spin_unlock_irq(&rnp->lock); 1835 continue; 1836 } 1837 1838 /* Record old state, apply changes to ->qsmaskinit field. */ 1839 oldmask = rnp->qsmaskinit; 1840 rnp->qsmaskinit = rnp->qsmaskinitnext; 1841 1842 /* If zero-ness of ->qsmaskinit changed, propagate up tree. */ 1843 if (!oldmask != !rnp->qsmaskinit) { 1844 if (!oldmask) /* First online CPU for this rcu_node. */ 1845 rcu_init_new_rnp(rnp); 1846 else if (rcu_preempt_has_tasks(rnp)) /* blocked tasks */ 1847 rnp->wait_blkd_tasks = true; 1848 else /* Last offline CPU and can propagate. */ 1849 rcu_cleanup_dead_rnp(rnp); 1850 } 1851 1852 /* 1853 * If all waited-on tasks from prior grace period are 1854 * done, and if all this rcu_node structure's CPUs are 1855 * still offline, propagate up the rcu_node tree and 1856 * clear ->wait_blkd_tasks. Otherwise, if one of this 1857 * rcu_node structure's CPUs has since come back online, 1858 * simply clear ->wait_blkd_tasks (but rcu_cleanup_dead_rnp() 1859 * checks for this, so just call it unconditionally). 1860 */ 1861 if (rnp->wait_blkd_tasks && 1862 (!rcu_preempt_has_tasks(rnp) || 1863 rnp->qsmaskinit)) { 1864 rnp->wait_blkd_tasks = false; 1865 rcu_cleanup_dead_rnp(rnp); 1866 } 1867 1868 raw_spin_unlock_irq(&rnp->lock); 1869 } 1870 1871 /* 1872 * Set the quiescent-state-needed bits in all the rcu_node 1873 * structures for all currently online CPUs in breadth-first order, 1874 * starting from the root rcu_node structure, relying on the layout 1875 * of the tree within the rsp->node[] array. Note that other CPUs 1876 * will access only the leaves of the hierarchy, thus seeing that no 1877 * grace period is in progress, at least until the corresponding 1878 * leaf node has been initialized. In addition, we have excluded 1879 * CPU-hotplug operations. 1880 * 1881 * The grace period cannot complete until the initialization 1882 * process finishes, because this kthread handles both. 1883 */ 1884 rcu_for_each_node_breadth_first(rsp, rnp) { 1885 rcu_gp_slow(rsp, gp_init_delay); 1886 raw_spin_lock_irq(&rnp->lock); 1887 smp_mb__after_unlock_lock(); 1888 rdp = this_cpu_ptr(rsp->rda); 1889 rcu_preempt_check_blocked_tasks(rnp); 1890 rnp->qsmask = rnp->qsmaskinit; 1891 WRITE_ONCE(rnp->gpnum, rsp->gpnum); 1892 if (WARN_ON_ONCE(rnp->completed != rsp->completed)) 1893 WRITE_ONCE(rnp->completed, rsp->completed); 1894 if (rnp == rdp->mynode) 1895 (void)__note_gp_changes(rsp, rnp, rdp); 1896 rcu_preempt_boost_start_gp(rnp); 1897 trace_rcu_grace_period_init(rsp->name, rnp->gpnum, 1898 rnp->level, rnp->grplo, 1899 rnp->grphi, rnp->qsmask); 1900 raw_spin_unlock_irq(&rnp->lock); 1901 cond_resched_rcu_qs(); 1902 WRITE_ONCE(rsp->gp_activity, jiffies); 1903 } 1904 1905 return 1; 1906 } 1907 1908 /* 1909 * Do one round of quiescent-state forcing. 1910 */ 1911 static int rcu_gp_fqs(struct rcu_state *rsp, int fqs_state_in) 1912 { 1913 int fqs_state = fqs_state_in; 1914 bool isidle = false; 1915 unsigned long maxj; 1916 struct rcu_node *rnp = rcu_get_root(rsp); 1917 1918 WRITE_ONCE(rsp->gp_activity, jiffies); 1919 rsp->n_force_qs++; 1920 if (fqs_state == RCU_SAVE_DYNTICK) { 1921 /* Collect dyntick-idle snapshots. */ 1922 if (is_sysidle_rcu_state(rsp)) { 1923 isidle = true; 1924 maxj = jiffies - ULONG_MAX / 4; 1925 } 1926 force_qs_rnp(rsp, dyntick_save_progress_counter, 1927 &isidle, &maxj); 1928 rcu_sysidle_report_gp(rsp, isidle, maxj); 1929 fqs_state = RCU_FORCE_QS; 1930 } else { 1931 /* Handle dyntick-idle and offline CPUs. */ 1932 isidle = true; 1933 force_qs_rnp(rsp, rcu_implicit_dynticks_qs, &isidle, &maxj); 1934 } 1935 /* Clear flag to prevent immediate re-entry. */ 1936 if (READ_ONCE(rsp->gp_flags) & RCU_GP_FLAG_FQS) { 1937 raw_spin_lock_irq(&rnp->lock); 1938 smp_mb__after_unlock_lock(); 1939 WRITE_ONCE(rsp->gp_flags, 1940 READ_ONCE(rsp->gp_flags) & ~RCU_GP_FLAG_FQS); 1941 raw_spin_unlock_irq(&rnp->lock); 1942 } 1943 return fqs_state; 1944 } 1945 1946 /* 1947 * Clean up after the old grace period. 1948 */ 1949 static void rcu_gp_cleanup(struct rcu_state *rsp) 1950 { 1951 unsigned long gp_duration; 1952 bool needgp = false; 1953 int nocb = 0; 1954 struct rcu_data *rdp; 1955 struct rcu_node *rnp = rcu_get_root(rsp); 1956 1957 WRITE_ONCE(rsp->gp_activity, jiffies); 1958 raw_spin_lock_irq(&rnp->lock); 1959 smp_mb__after_unlock_lock(); 1960 gp_duration = jiffies - rsp->gp_start; 1961 if (gp_duration > rsp->gp_max) 1962 rsp->gp_max = gp_duration; 1963 1964 /* 1965 * We know the grace period is complete, but to everyone else 1966 * it appears to still be ongoing. But it is also the case 1967 * that to everyone else it looks like there is nothing that 1968 * they can do to advance the grace period. It is therefore 1969 * safe for us to drop the lock in order to mark the grace 1970 * period as completed in all of the rcu_node structures. 1971 */ 1972 raw_spin_unlock_irq(&rnp->lock); 1973 1974 /* 1975 * Propagate new ->completed value to rcu_node structures so 1976 * that other CPUs don't have to wait until the start of the next 1977 * grace period to process their callbacks. This also avoids 1978 * some nasty RCU grace-period initialization races by forcing 1979 * the end of the current grace period to be completely recorded in 1980 * all of the rcu_node structures before the beginning of the next 1981 * grace period is recorded in any of the rcu_node structures. 1982 */ 1983 rcu_for_each_node_breadth_first(rsp, rnp) { 1984 raw_spin_lock_irq(&rnp->lock); 1985 smp_mb__after_unlock_lock(); 1986 WARN_ON_ONCE(rcu_preempt_blocked_readers_cgp(rnp)); 1987 WARN_ON_ONCE(rnp->qsmask); 1988 WRITE_ONCE(rnp->completed, rsp->gpnum); 1989 rdp = this_cpu_ptr(rsp->rda); 1990 if (rnp == rdp->mynode) 1991 needgp = __note_gp_changes(rsp, rnp, rdp) || needgp; 1992 /* smp_mb() provided by prior unlock-lock pair. */ 1993 nocb += rcu_future_gp_cleanup(rsp, rnp); 1994 raw_spin_unlock_irq(&rnp->lock); 1995 cond_resched_rcu_qs(); 1996 WRITE_ONCE(rsp->gp_activity, jiffies); 1997 rcu_gp_slow(rsp, gp_cleanup_delay); 1998 } 1999 rnp = rcu_get_root(rsp); 2000 raw_spin_lock_irq(&rnp->lock); 2001 smp_mb__after_unlock_lock(); /* Order GP before ->completed update. */ 2002 rcu_nocb_gp_set(rnp, nocb); 2003 2004 /* Declare grace period done. */ 2005 WRITE_ONCE(rsp->completed, rsp->gpnum); 2006 trace_rcu_grace_period(rsp->name, rsp->completed, TPS("end")); 2007 rsp->fqs_state = RCU_GP_IDLE; 2008 rdp = this_cpu_ptr(rsp->rda); 2009 /* Advance CBs to reduce false positives below. */ 2010 needgp = rcu_advance_cbs(rsp, rnp, rdp) || needgp; 2011 if (needgp || cpu_needs_another_gp(rsp, rdp)) { 2012 WRITE_ONCE(rsp->gp_flags, RCU_GP_FLAG_INIT); 2013 trace_rcu_grace_period(rsp->name, 2014 READ_ONCE(rsp->gpnum), 2015 TPS("newreq")); 2016 } 2017 raw_spin_unlock_irq(&rnp->lock); 2018 } 2019 2020 /* 2021 * Body of kthread that handles grace periods. 2022 */ 2023 static int __noreturn rcu_gp_kthread(void *arg) 2024 { 2025 int fqs_state; 2026 int gf; 2027 unsigned long j; 2028 int ret; 2029 struct rcu_state *rsp = arg; 2030 struct rcu_node *rnp = rcu_get_root(rsp); 2031 2032 rcu_bind_gp_kthread(); 2033 for (;;) { 2034 2035 /* Handle grace-period start. */ 2036 for (;;) { 2037 trace_rcu_grace_period(rsp->name, 2038 READ_ONCE(rsp->gpnum), 2039 TPS("reqwait")); 2040 rsp->gp_state = RCU_GP_WAIT_GPS; 2041 wait_event_interruptible(rsp->gp_wq, 2042 READ_ONCE(rsp->gp_flags) & 2043 RCU_GP_FLAG_INIT); 2044 /* Locking provides needed memory barrier. */ 2045 if (rcu_gp_init(rsp)) 2046 break; 2047 cond_resched_rcu_qs(); 2048 WRITE_ONCE(rsp->gp_activity, jiffies); 2049 WARN_ON(signal_pending(current)); 2050 trace_rcu_grace_period(rsp->name, 2051 READ_ONCE(rsp->gpnum), 2052 TPS("reqwaitsig")); 2053 } 2054 2055 /* Handle quiescent-state forcing. */ 2056 fqs_state = RCU_SAVE_DYNTICK; 2057 j = jiffies_till_first_fqs; 2058 if (j > HZ) { 2059 j = HZ; 2060 jiffies_till_first_fqs = HZ; 2061 } 2062 ret = 0; 2063 for (;;) { 2064 if (!ret) 2065 rsp->jiffies_force_qs = jiffies + j; 2066 trace_rcu_grace_period(rsp->name, 2067 READ_ONCE(rsp->gpnum), 2068 TPS("fqswait")); 2069 rsp->gp_state = RCU_GP_WAIT_FQS; 2070 ret = wait_event_interruptible_timeout(rsp->gp_wq, 2071 ((gf = READ_ONCE(rsp->gp_flags)) & 2072 RCU_GP_FLAG_FQS) || 2073 (!READ_ONCE(rnp->qsmask) && 2074 !rcu_preempt_blocked_readers_cgp(rnp)), 2075 j); 2076 /* Locking provides needed memory barriers. */ 2077 /* If grace period done, leave loop. */ 2078 if (!READ_ONCE(rnp->qsmask) && 2079 !rcu_preempt_blocked_readers_cgp(rnp)) 2080 break; 2081 /* If time for quiescent-state forcing, do it. */ 2082 if (ULONG_CMP_GE(jiffies, rsp->jiffies_force_qs) || 2083 (gf & RCU_GP_FLAG_FQS)) { 2084 trace_rcu_grace_period(rsp->name, 2085 READ_ONCE(rsp->gpnum), 2086 TPS("fqsstart")); 2087 fqs_state = rcu_gp_fqs(rsp, fqs_state); 2088 trace_rcu_grace_period(rsp->name, 2089 READ_ONCE(rsp->gpnum), 2090 TPS("fqsend")); 2091 cond_resched_rcu_qs(); 2092 WRITE_ONCE(rsp->gp_activity, jiffies); 2093 } else { 2094 /* Deal with stray signal. */ 2095 cond_resched_rcu_qs(); 2096 WRITE_ONCE(rsp->gp_activity, jiffies); 2097 WARN_ON(signal_pending(current)); 2098 trace_rcu_grace_period(rsp->name, 2099 READ_ONCE(rsp->gpnum), 2100 TPS("fqswaitsig")); 2101 } 2102 j = jiffies_till_next_fqs; 2103 if (j > HZ) { 2104 j = HZ; 2105 jiffies_till_next_fqs = HZ; 2106 } else if (j < 1) { 2107 j = 1; 2108 jiffies_till_next_fqs = 1; 2109 } 2110 } 2111 2112 /* Handle grace-period end. */ 2113 rcu_gp_cleanup(rsp); 2114 } 2115 } 2116 2117 /* 2118 * Start a new RCU grace period if warranted, re-initializing the hierarchy 2119 * in preparation for detecting the next grace period. The caller must hold 2120 * the root node's ->lock and hard irqs must be disabled. 2121 * 2122 * Note that it is legal for a dying CPU (which is marked as offline) to 2123 * invoke this function. This can happen when the dying CPU reports its 2124 * quiescent state. 2125 * 2126 * Returns true if the grace-period kthread must be awakened. 2127 */ 2128 static bool 2129 rcu_start_gp_advanced(struct rcu_state *rsp, struct rcu_node *rnp, 2130 struct rcu_data *rdp) 2131 { 2132 if (!rsp->gp_kthread || !cpu_needs_another_gp(rsp, rdp)) { 2133 /* 2134 * Either we have not yet spawned the grace-period 2135 * task, this CPU does not need another grace period, 2136 * or a grace period is already in progress. 2137 * Either way, don't start a new grace period. 2138 */ 2139 return false; 2140 } 2141 WRITE_ONCE(rsp->gp_flags, RCU_GP_FLAG_INIT); 2142 trace_rcu_grace_period(rsp->name, READ_ONCE(rsp->gpnum), 2143 TPS("newreq")); 2144 2145 /* 2146 * We can't do wakeups while holding the rnp->lock, as that 2147 * could cause possible deadlocks with the rq->lock. Defer 2148 * the wakeup to our caller. 2149 */ 2150 return true; 2151 } 2152 2153 /* 2154 * Similar to rcu_start_gp_advanced(), but also advance the calling CPU's 2155 * callbacks. Note that rcu_start_gp_advanced() cannot do this because it 2156 * is invoked indirectly from rcu_advance_cbs(), which would result in 2157 * endless recursion -- or would do so if it wasn't for the self-deadlock 2158 * that is encountered beforehand. 2159 * 2160 * Returns true if the grace-period kthread needs to be awakened. 2161 */ 2162 static bool rcu_start_gp(struct rcu_state *rsp) 2163 { 2164 struct rcu_data *rdp = this_cpu_ptr(rsp->rda); 2165 struct rcu_node *rnp = rcu_get_root(rsp); 2166 bool ret = false; 2167 2168 /* 2169 * If there is no grace period in progress right now, any 2170 * callbacks we have up to this point will be satisfied by the 2171 * next grace period. Also, advancing the callbacks reduces the 2172 * probability of false positives from cpu_needs_another_gp() 2173 * resulting in pointless grace periods. So, advance callbacks 2174 * then start the grace period! 2175 */ 2176 ret = rcu_advance_cbs(rsp, rnp, rdp) || ret; 2177 ret = rcu_start_gp_advanced(rsp, rnp, rdp) || ret; 2178 return ret; 2179 } 2180 2181 /* 2182 * Report a full set of quiescent states to the specified rcu_state 2183 * data structure. This involves cleaning up after the prior grace 2184 * period and letting rcu_start_gp() start up the next grace period 2185 * if one is needed. Note that the caller must hold rnp->lock, which 2186 * is released before return. 2187 */ 2188 static void rcu_report_qs_rsp(struct rcu_state *rsp, unsigned long flags) 2189 __releases(rcu_get_root(rsp)->lock) 2190 { 2191 WARN_ON_ONCE(!rcu_gp_in_progress(rsp)); 2192 WRITE_ONCE(rsp->gp_flags, READ_ONCE(rsp->gp_flags) | RCU_GP_FLAG_FQS); 2193 raw_spin_unlock_irqrestore(&rcu_get_root(rsp)->lock, flags); 2194 rcu_gp_kthread_wake(rsp); 2195 } 2196 2197 /* 2198 * Similar to rcu_report_qs_rdp(), for which it is a helper function. 2199 * Allows quiescent states for a group of CPUs to be reported at one go 2200 * to the specified rcu_node structure, though all the CPUs in the group 2201 * must be represented by the same rcu_node structure (which need not be a 2202 * leaf rcu_node structure, though it often will be). The gps parameter 2203 * is the grace-period snapshot, which means that the quiescent states 2204 * are valid only if rnp->gpnum is equal to gps. That structure's lock 2205 * must be held upon entry, and it is released before return. 2206 */ 2207 static void 2208 rcu_report_qs_rnp(unsigned long mask, struct rcu_state *rsp, 2209 struct rcu_node *rnp, unsigned long gps, unsigned long flags) 2210 __releases(rnp->lock) 2211 { 2212 unsigned long oldmask = 0; 2213 struct rcu_node *rnp_c; 2214 2215 /* Walk up the rcu_node hierarchy. */ 2216 for (;;) { 2217 if (!(rnp->qsmask & mask) || rnp->gpnum != gps) { 2218 2219 /* 2220 * Our bit has already been cleared, or the 2221 * relevant grace period is already over, so done. 2222 */ 2223 raw_spin_unlock_irqrestore(&rnp->lock, flags); 2224 return; 2225 } 2226 WARN_ON_ONCE(oldmask); /* Any child must be all zeroed! */ 2227 rnp->qsmask &= ~mask; 2228 trace_rcu_quiescent_state_report(rsp->name, rnp->gpnum, 2229 mask, rnp->qsmask, rnp->level, 2230 rnp->grplo, rnp->grphi, 2231 !!rnp->gp_tasks); 2232 if (rnp->qsmask != 0 || rcu_preempt_blocked_readers_cgp(rnp)) { 2233 2234 /* Other bits still set at this level, so done. */ 2235 raw_spin_unlock_irqrestore(&rnp->lock, flags); 2236 return; 2237 } 2238 mask = rnp->grpmask; 2239 if (rnp->parent == NULL) { 2240 2241 /* No more levels. Exit loop holding root lock. */ 2242 2243 break; 2244 } 2245 raw_spin_unlock_irqrestore(&rnp->lock, flags); 2246 rnp_c = rnp; 2247 rnp = rnp->parent; 2248 raw_spin_lock_irqsave(&rnp->lock, flags); 2249 smp_mb__after_unlock_lock(); 2250 oldmask = rnp_c->qsmask; 2251 } 2252 2253 /* 2254 * Get here if we are the last CPU to pass through a quiescent 2255 * state for this grace period. Invoke rcu_report_qs_rsp() 2256 * to clean up and start the next grace period if one is needed. 2257 */ 2258 rcu_report_qs_rsp(rsp, flags); /* releases rnp->lock. */ 2259 } 2260 2261 /* 2262 * Record a quiescent state for all tasks that were previously queued 2263 * on the specified rcu_node structure and that were blocking the current 2264 * RCU grace period. The caller must hold the specified rnp->lock with 2265 * irqs disabled, and this lock is released upon return, but irqs remain 2266 * disabled. 2267 */ 2268 static void rcu_report_unblock_qs_rnp(struct rcu_state *rsp, 2269 struct rcu_node *rnp, unsigned long flags) 2270 __releases(rnp->lock) 2271 { 2272 unsigned long gps; 2273 unsigned long mask; 2274 struct rcu_node *rnp_p; 2275 2276 if (rcu_state_p == &rcu_sched_state || rsp != rcu_state_p || 2277 rnp->qsmask != 0 || rcu_preempt_blocked_readers_cgp(rnp)) { 2278 raw_spin_unlock_irqrestore(&rnp->lock, flags); 2279 return; /* Still need more quiescent states! */ 2280 } 2281 2282 rnp_p = rnp->parent; 2283 if (rnp_p == NULL) { 2284 /* 2285 * Only one rcu_node structure in the tree, so don't 2286 * try to report up to its nonexistent parent! 2287 */ 2288 rcu_report_qs_rsp(rsp, flags); 2289 return; 2290 } 2291 2292 /* Report up the rest of the hierarchy, tracking current ->gpnum. */ 2293 gps = rnp->gpnum; 2294 mask = rnp->grpmask; 2295 raw_spin_unlock(&rnp->lock); /* irqs remain disabled. */ 2296 raw_spin_lock(&rnp_p->lock); /* irqs already disabled. */ 2297 smp_mb__after_unlock_lock(); 2298 rcu_report_qs_rnp(mask, rsp, rnp_p, gps, flags); 2299 } 2300 2301 /* 2302 * Record a quiescent state for the specified CPU to that CPU's rcu_data 2303 * structure. This must be either called from the specified CPU, or 2304 * called when the specified CPU is known to be offline (and when it is 2305 * also known that no other CPU is concurrently trying to help the offline 2306 * CPU). The lastcomp argument is used to make sure we are still in the 2307 * grace period of interest. We don't want to end the current grace period 2308 * based on quiescent states detected in an earlier grace period! 2309 */ 2310 static void 2311 rcu_report_qs_rdp(int cpu, struct rcu_state *rsp, struct rcu_data *rdp) 2312 { 2313 unsigned long flags; 2314 unsigned long mask; 2315 bool needwake; 2316 struct rcu_node *rnp; 2317 2318 rnp = rdp->mynode; 2319 raw_spin_lock_irqsave(&rnp->lock, flags); 2320 smp_mb__after_unlock_lock(); 2321 if ((rdp->passed_quiesce == 0 && 2322 rdp->rcu_qs_ctr_snap == __this_cpu_read(rcu_qs_ctr)) || 2323 rdp->gpnum != rnp->gpnum || rnp->completed == rnp->gpnum || 2324 rdp->gpwrap) { 2325 2326 /* 2327 * The grace period in which this quiescent state was 2328 * recorded has ended, so don't report it upwards. 2329 * We will instead need a new quiescent state that lies 2330 * within the current grace period. 2331 */ 2332 rdp->passed_quiesce = 0; /* need qs for new gp. */ 2333 rdp->rcu_qs_ctr_snap = __this_cpu_read(rcu_qs_ctr); 2334 raw_spin_unlock_irqrestore(&rnp->lock, flags); 2335 return; 2336 } 2337 mask = rdp->grpmask; 2338 if ((rnp->qsmask & mask) == 0) { 2339 raw_spin_unlock_irqrestore(&rnp->lock, flags); 2340 } else { 2341 rdp->qs_pending = 0; 2342 2343 /* 2344 * This GP can't end until cpu checks in, so all of our 2345 * callbacks can be processed during the next GP. 2346 */ 2347 needwake = rcu_accelerate_cbs(rsp, rnp, rdp); 2348 2349 rcu_report_qs_rnp(mask, rsp, rnp, rnp->gpnum, flags); 2350 /* ^^^ Released rnp->lock */ 2351 if (needwake) 2352 rcu_gp_kthread_wake(rsp); 2353 } 2354 } 2355 2356 /* 2357 * Check to see if there is a new grace period of which this CPU 2358 * is not yet aware, and if so, set up local rcu_data state for it. 2359 * Otherwise, see if this CPU has just passed through its first 2360 * quiescent state for this grace period, and record that fact if so. 2361 */ 2362 static void 2363 rcu_check_quiescent_state(struct rcu_state *rsp, struct rcu_data *rdp) 2364 { 2365 /* Check for grace-period ends and beginnings. */ 2366 note_gp_changes(rsp, rdp); 2367 2368 /* 2369 * Does this CPU still need to do its part for current grace period? 2370 * If no, return and let the other CPUs do their part as well. 2371 */ 2372 if (!rdp->qs_pending) 2373 return; 2374 2375 /* 2376 * Was there a quiescent state since the beginning of the grace 2377 * period? If no, then exit and wait for the next call. 2378 */ 2379 if (!rdp->passed_quiesce && 2380 rdp->rcu_qs_ctr_snap == __this_cpu_read(rcu_qs_ctr)) 2381 return; 2382 2383 /* 2384 * Tell RCU we are done (but rcu_report_qs_rdp() will be the 2385 * judge of that). 2386 */ 2387 rcu_report_qs_rdp(rdp->cpu, rsp, rdp); 2388 } 2389 2390 /* 2391 * Send the specified CPU's RCU callbacks to the orphanage. The 2392 * specified CPU must be offline, and the caller must hold the 2393 * ->orphan_lock. 2394 */ 2395 static void 2396 rcu_send_cbs_to_orphanage(int cpu, struct rcu_state *rsp, 2397 struct rcu_node *rnp, struct rcu_data *rdp) 2398 { 2399 /* No-CBs CPUs do not have orphanable callbacks. */ 2400 if (!IS_ENABLED(CONFIG_HOTPLUG_CPU) || rcu_is_nocb_cpu(rdp->cpu)) 2401 return; 2402 2403 /* 2404 * Orphan the callbacks. First adjust the counts. This is safe 2405 * because _rcu_barrier() excludes CPU-hotplug operations, so it 2406 * cannot be running now. Thus no memory barrier is required. 2407 */ 2408 if (rdp->nxtlist != NULL) { 2409 rsp->qlen_lazy += rdp->qlen_lazy; 2410 rsp->qlen += rdp->qlen; 2411 rdp->n_cbs_orphaned += rdp->qlen; 2412 rdp->qlen_lazy = 0; 2413 WRITE_ONCE(rdp->qlen, 0); 2414 } 2415 2416 /* 2417 * Next, move those callbacks still needing a grace period to 2418 * the orphanage, where some other CPU will pick them up. 2419 * Some of the callbacks might have gone partway through a grace 2420 * period, but that is too bad. They get to start over because we 2421 * cannot assume that grace periods are synchronized across CPUs. 2422 * We don't bother updating the ->nxttail[] array yet, instead 2423 * we just reset the whole thing later on. 2424 */ 2425 if (*rdp->nxttail[RCU_DONE_TAIL] != NULL) { 2426 *rsp->orphan_nxttail = *rdp->nxttail[RCU_DONE_TAIL]; 2427 rsp->orphan_nxttail = rdp->nxttail[RCU_NEXT_TAIL]; 2428 *rdp->nxttail[RCU_DONE_TAIL] = NULL; 2429 } 2430 2431 /* 2432 * Then move the ready-to-invoke callbacks to the orphanage, 2433 * where some other CPU will pick them up. These will not be 2434 * required to pass though another grace period: They are done. 2435 */ 2436 if (rdp->nxtlist != NULL) { 2437 *rsp->orphan_donetail = rdp->nxtlist; 2438 rsp->orphan_donetail = rdp->nxttail[RCU_DONE_TAIL]; 2439 } 2440 2441 /* 2442 * Finally, initialize the rcu_data structure's list to empty and 2443 * disallow further callbacks on this CPU. 2444 */ 2445 init_callback_list(rdp); 2446 rdp->nxttail[RCU_NEXT_TAIL] = NULL; 2447 } 2448 2449 /* 2450 * Adopt the RCU callbacks from the specified rcu_state structure's 2451 * orphanage. The caller must hold the ->orphan_lock. 2452 */ 2453 static void rcu_adopt_orphan_cbs(struct rcu_state *rsp, unsigned long flags) 2454 { 2455 int i; 2456 struct rcu_data *rdp = raw_cpu_ptr(rsp->rda); 2457 2458 /* No-CBs CPUs are handled specially. */ 2459 if (!IS_ENABLED(CONFIG_HOTPLUG_CPU) || 2460 rcu_nocb_adopt_orphan_cbs(rsp, rdp, flags)) 2461 return; 2462 2463 /* Do the accounting first. */ 2464 rdp->qlen_lazy += rsp->qlen_lazy; 2465 rdp->qlen += rsp->qlen; 2466 rdp->n_cbs_adopted += rsp->qlen; 2467 if (rsp->qlen_lazy != rsp->qlen) 2468 rcu_idle_count_callbacks_posted(); 2469 rsp->qlen_lazy = 0; 2470 rsp->qlen = 0; 2471 2472 /* 2473 * We do not need a memory barrier here because the only way we 2474 * can get here if there is an rcu_barrier() in flight is if 2475 * we are the task doing the rcu_barrier(). 2476 */ 2477 2478 /* First adopt the ready-to-invoke callbacks. */ 2479 if (rsp->orphan_donelist != NULL) { 2480 *rsp->orphan_donetail = *rdp->nxttail[RCU_DONE_TAIL]; 2481 *rdp->nxttail[RCU_DONE_TAIL] = rsp->orphan_donelist; 2482 for (i = RCU_NEXT_SIZE - 1; i >= RCU_DONE_TAIL; i--) 2483 if (rdp->nxttail[i] == rdp->nxttail[RCU_DONE_TAIL]) 2484 rdp->nxttail[i] = rsp->orphan_donetail; 2485 rsp->orphan_donelist = NULL; 2486 rsp->orphan_donetail = &rsp->orphan_donelist; 2487 } 2488 2489 /* And then adopt the callbacks that still need a grace period. */ 2490 if (rsp->orphan_nxtlist != NULL) { 2491 *rdp->nxttail[RCU_NEXT_TAIL] = rsp->orphan_nxtlist; 2492 rdp->nxttail[RCU_NEXT_TAIL] = rsp->orphan_nxttail; 2493 rsp->orphan_nxtlist = NULL; 2494 rsp->orphan_nxttail = &rsp->orphan_nxtlist; 2495 } 2496 } 2497 2498 /* 2499 * Trace the fact that this CPU is going offline. 2500 */ 2501 static void rcu_cleanup_dying_cpu(struct rcu_state *rsp) 2502 { 2503 RCU_TRACE(unsigned long mask); 2504 RCU_TRACE(struct rcu_data *rdp = this_cpu_ptr(rsp->rda)); 2505 RCU_TRACE(struct rcu_node *rnp = rdp->mynode); 2506 2507 if (!IS_ENABLED(CONFIG_HOTPLUG_CPU)) 2508 return; 2509 2510 RCU_TRACE(mask = rdp->grpmask); 2511 trace_rcu_grace_period(rsp->name, 2512 rnp->gpnum + 1 - !!(rnp->qsmask & mask), 2513 TPS("cpuofl")); 2514 } 2515 2516 /* 2517 * All CPUs for the specified rcu_node structure have gone offline, 2518 * and all tasks that were preempted within an RCU read-side critical 2519 * section while running on one of those CPUs have since exited their RCU 2520 * read-side critical section. Some other CPU is reporting this fact with 2521 * the specified rcu_node structure's ->lock held and interrupts disabled. 2522 * This function therefore goes up the tree of rcu_node structures, 2523 * clearing the corresponding bits in the ->qsmaskinit fields. Note that 2524 * the leaf rcu_node structure's ->qsmaskinit field has already been 2525 * updated 2526 * 2527 * This function does check that the specified rcu_node structure has 2528 * all CPUs offline and no blocked tasks, so it is OK to invoke it 2529 * prematurely. That said, invoking it after the fact will cost you 2530 * a needless lock acquisition. So once it has done its work, don't 2531 * invoke it again. 2532 */ 2533 static void rcu_cleanup_dead_rnp(struct rcu_node *rnp_leaf) 2534 { 2535 long mask; 2536 struct rcu_node *rnp = rnp_leaf; 2537 2538 if (!IS_ENABLED(CONFIG_HOTPLUG_CPU) || 2539 rnp->qsmaskinit || rcu_preempt_has_tasks(rnp)) 2540 return; 2541 for (;;) { 2542 mask = rnp->grpmask; 2543 rnp = rnp->parent; 2544 if (!rnp) 2545 break; 2546 raw_spin_lock(&rnp->lock); /* irqs already disabled. */ 2547 smp_mb__after_unlock_lock(); /* GP memory ordering. */ 2548 rnp->qsmaskinit &= ~mask; 2549 rnp->qsmask &= ~mask; 2550 if (rnp->qsmaskinit) { 2551 raw_spin_unlock(&rnp->lock); /* irqs remain disabled. */ 2552 return; 2553 } 2554 raw_spin_unlock(&rnp->lock); /* irqs remain disabled. */ 2555 } 2556 } 2557 2558 /* 2559 * The CPU is exiting the idle loop into the arch_cpu_idle_dead() 2560 * function. We now remove it from the rcu_node tree's ->qsmaskinit 2561 * bit masks. 2562 */ 2563 static void rcu_cleanup_dying_idle_cpu(int cpu, struct rcu_state *rsp) 2564 { 2565 unsigned long flags; 2566 unsigned long mask; 2567 struct rcu_data *rdp = per_cpu_ptr(rsp->rda, cpu); 2568 struct rcu_node *rnp = rdp->mynode; /* Outgoing CPU's rdp & rnp. */ 2569 2570 if (!IS_ENABLED(CONFIG_HOTPLUG_CPU)) 2571 return; 2572 2573 /* Remove outgoing CPU from mask in the leaf rcu_node structure. */ 2574 mask = rdp->grpmask; 2575 raw_spin_lock_irqsave(&rnp->lock, flags); 2576 smp_mb__after_unlock_lock(); /* Enforce GP memory-order guarantee. */ 2577 rnp->qsmaskinitnext &= ~mask; 2578 raw_spin_unlock_irqrestore(&rnp->lock, flags); 2579 } 2580 2581 /* 2582 * The CPU has been completely removed, and some other CPU is reporting 2583 * this fact from process context. Do the remainder of the cleanup, 2584 * including orphaning the outgoing CPU's RCU callbacks, and also 2585 * adopting them. There can only be one CPU hotplug operation at a time, 2586 * so no other CPU can be attempting to update rcu_cpu_kthread_task. 2587 */ 2588 static void rcu_cleanup_dead_cpu(int cpu, struct rcu_state *rsp) 2589 { 2590 unsigned long flags; 2591 struct rcu_data *rdp = per_cpu_ptr(rsp->rda, cpu); 2592 struct rcu_node *rnp = rdp->mynode; /* Outgoing CPU's rdp & rnp. */ 2593 2594 if (!IS_ENABLED(CONFIG_HOTPLUG_CPU)) 2595 return; 2596 2597 /* Adjust any no-longer-needed kthreads. */ 2598 rcu_boost_kthread_setaffinity(rnp, -1); 2599 2600 /* Orphan the dead CPU's callbacks, and adopt them if appropriate. */ 2601 raw_spin_lock_irqsave(&rsp->orphan_lock, flags); 2602 rcu_send_cbs_to_orphanage(cpu, rsp, rnp, rdp); 2603 rcu_adopt_orphan_cbs(rsp, flags); 2604 raw_spin_unlock_irqrestore(&rsp->orphan_lock, flags); 2605 2606 WARN_ONCE(rdp->qlen != 0 || rdp->nxtlist != NULL, 2607 "rcu_cleanup_dead_cpu: Callbacks on offline CPU %d: qlen=%lu, nxtlist=%p\n", 2608 cpu, rdp->qlen, rdp->nxtlist); 2609 } 2610 2611 /* 2612 * Invoke any RCU callbacks that have made it to the end of their grace 2613 * period. Thottle as specified by rdp->blimit. 2614 */ 2615 static void rcu_do_batch(struct rcu_state *rsp, struct rcu_data *rdp) 2616 { 2617 unsigned long flags; 2618 struct rcu_head *next, *list, **tail; 2619 long bl, count, count_lazy; 2620 int i; 2621 2622 /* If no callbacks are ready, just return. */ 2623 if (!cpu_has_callbacks_ready_to_invoke(rdp)) { 2624 trace_rcu_batch_start(rsp->name, rdp->qlen_lazy, rdp->qlen, 0); 2625 trace_rcu_batch_end(rsp->name, 0, !!READ_ONCE(rdp->nxtlist), 2626 need_resched(), is_idle_task(current), 2627 rcu_is_callbacks_kthread()); 2628 return; 2629 } 2630 2631 /* 2632 * Extract the list of ready callbacks, disabling to prevent 2633 * races with call_rcu() from interrupt handlers. 2634 */ 2635 local_irq_save(flags); 2636 WARN_ON_ONCE(cpu_is_offline(smp_processor_id())); 2637 bl = rdp->blimit; 2638 trace_rcu_batch_start(rsp->name, rdp->qlen_lazy, rdp->qlen, bl); 2639 list = rdp->nxtlist; 2640 rdp->nxtlist = *rdp->nxttail[RCU_DONE_TAIL]; 2641 *rdp->nxttail[RCU_DONE_TAIL] = NULL; 2642 tail = rdp->nxttail[RCU_DONE_TAIL]; 2643 for (i = RCU_NEXT_SIZE - 1; i >= 0; i--) 2644 if (rdp->nxttail[i] == rdp->nxttail[RCU_DONE_TAIL]) 2645 rdp->nxttail[i] = &rdp->nxtlist; 2646 local_irq_restore(flags); 2647 2648 /* Invoke callbacks. */ 2649 count = count_lazy = 0; 2650 while (list) { 2651 next = list->next; 2652 prefetch(next); 2653 debug_rcu_head_unqueue(list); 2654 if (__rcu_reclaim(rsp->name, list)) 2655 count_lazy++; 2656 list = next; 2657 /* Stop only if limit reached and CPU has something to do. */ 2658 if (++count >= bl && 2659 (need_resched() || 2660 (!is_idle_task(current) && !rcu_is_callbacks_kthread()))) 2661 break; 2662 } 2663 2664 local_irq_save(flags); 2665 trace_rcu_batch_end(rsp->name, count, !!list, need_resched(), 2666 is_idle_task(current), 2667 rcu_is_callbacks_kthread()); 2668 2669 /* Update count, and requeue any remaining callbacks. */ 2670 if (list != NULL) { 2671 *tail = rdp->nxtlist; 2672 rdp->nxtlist = list; 2673 for (i = 0; i < RCU_NEXT_SIZE; i++) 2674 if (&rdp->nxtlist == rdp->nxttail[i]) 2675 rdp->nxttail[i] = tail; 2676 else 2677 break; 2678 } 2679 smp_mb(); /* List handling before counting for rcu_barrier(). */ 2680 rdp->qlen_lazy -= count_lazy; 2681 WRITE_ONCE(rdp->qlen, rdp->qlen - count); 2682 rdp->n_cbs_invoked += count; 2683 2684 /* Reinstate batch limit if we have worked down the excess. */ 2685 if (rdp->blimit == LONG_MAX && rdp->qlen <= qlowmark) 2686 rdp->blimit = blimit; 2687 2688 /* Reset ->qlen_last_fqs_check trigger if enough CBs have drained. */ 2689 if (rdp->qlen == 0 && rdp->qlen_last_fqs_check != 0) { 2690 rdp->qlen_last_fqs_check = 0; 2691 rdp->n_force_qs_snap = rsp->n_force_qs; 2692 } else if (rdp->qlen < rdp->qlen_last_fqs_check - qhimark) 2693 rdp->qlen_last_fqs_check = rdp->qlen; 2694 WARN_ON_ONCE((rdp->nxtlist == NULL) != (rdp->qlen == 0)); 2695 2696 local_irq_restore(flags); 2697 2698 /* Re-invoke RCU core processing if there are callbacks remaining. */ 2699 if (cpu_has_callbacks_ready_to_invoke(rdp)) 2700 invoke_rcu_core(); 2701 } 2702 2703 /* 2704 * Check to see if this CPU is in a non-context-switch quiescent state 2705 * (user mode or idle loop for rcu, non-softirq execution for rcu_bh). 2706 * Also schedule RCU core processing. 2707 * 2708 * This function must be called from hardirq context. It is normally 2709 * invoked from the scheduling-clock interrupt. If rcu_pending returns 2710 * false, there is no point in invoking rcu_check_callbacks(). 2711 */ 2712 void rcu_check_callbacks(int user) 2713 { 2714 trace_rcu_utilization(TPS("Start scheduler-tick")); 2715 increment_cpu_stall_ticks(); 2716 if (user || rcu_is_cpu_rrupt_from_idle()) { 2717 2718 /* 2719 * Get here if this CPU took its interrupt from user 2720 * mode or from the idle loop, and if this is not a 2721 * nested interrupt. In this case, the CPU is in 2722 * a quiescent state, so note it. 2723 * 2724 * No memory barrier is required here because both 2725 * rcu_sched_qs() and rcu_bh_qs() reference only CPU-local 2726 * variables that other CPUs neither access nor modify, 2727 * at least not while the corresponding CPU is online. 2728 */ 2729 2730 rcu_sched_qs(); 2731 rcu_bh_qs(); 2732 2733 } else if (!in_softirq()) { 2734 2735 /* 2736 * Get here if this CPU did not take its interrupt from 2737 * softirq, in other words, if it is not interrupting 2738 * a rcu_bh read-side critical section. This is an _bh 2739 * critical section, so note it. 2740 */ 2741 2742 rcu_bh_qs(); 2743 } 2744 rcu_preempt_check_callbacks(); 2745 if (rcu_pending()) 2746 invoke_rcu_core(); 2747 if (user) 2748 rcu_note_voluntary_context_switch(current); 2749 trace_rcu_utilization(TPS("End scheduler-tick")); 2750 } 2751 2752 /* 2753 * Scan the leaf rcu_node structures, processing dyntick state for any that 2754 * have not yet encountered a quiescent state, using the function specified. 2755 * Also initiate boosting for any threads blocked on the root rcu_node. 2756 * 2757 * The caller must have suppressed start of new grace periods. 2758 */ 2759 static void force_qs_rnp(struct rcu_state *rsp, 2760 int (*f)(struct rcu_data *rsp, bool *isidle, 2761 unsigned long *maxj), 2762 bool *isidle, unsigned long *maxj) 2763 { 2764 unsigned long bit; 2765 int cpu; 2766 unsigned long flags; 2767 unsigned long mask; 2768 struct rcu_node *rnp; 2769 2770 rcu_for_each_leaf_node(rsp, rnp) { 2771 cond_resched_rcu_qs(); 2772 mask = 0; 2773 raw_spin_lock_irqsave(&rnp->lock, flags); 2774 smp_mb__after_unlock_lock(); 2775 if (rnp->qsmask == 0) { 2776 if (rcu_state_p == &rcu_sched_state || 2777 rsp != rcu_state_p || 2778 rcu_preempt_blocked_readers_cgp(rnp)) { 2779 /* 2780 * No point in scanning bits because they 2781 * are all zero. But we might need to 2782 * priority-boost blocked readers. 2783 */ 2784 rcu_initiate_boost(rnp, flags); 2785 /* rcu_initiate_boost() releases rnp->lock */ 2786 continue; 2787 } 2788 if (rnp->parent && 2789 (rnp->parent->qsmask & rnp->grpmask)) { 2790 /* 2791 * Race between grace-period 2792 * initialization and task exiting RCU 2793 * read-side critical section: Report. 2794 */ 2795 rcu_report_unblock_qs_rnp(rsp, rnp, flags); 2796 /* rcu_report_unblock_qs_rnp() rlses ->lock */ 2797 continue; 2798 } 2799 } 2800 cpu = rnp->grplo; 2801 bit = 1; 2802 for (; cpu <= rnp->grphi; cpu++, bit <<= 1) { 2803 if ((rnp->qsmask & bit) != 0) { 2804 if (f(per_cpu_ptr(rsp->rda, cpu), isidle, maxj)) 2805 mask |= bit; 2806 } 2807 } 2808 if (mask != 0) { 2809 /* Idle/offline CPUs, report (releases rnp->lock. */ 2810 rcu_report_qs_rnp(mask, rsp, rnp, rnp->gpnum, flags); 2811 } else { 2812 /* Nothing to do here, so just drop the lock. */ 2813 raw_spin_unlock_irqrestore(&rnp->lock, flags); 2814 } 2815 } 2816 } 2817 2818 /* 2819 * Force quiescent states on reluctant CPUs, and also detect which 2820 * CPUs are in dyntick-idle mode. 2821 */ 2822 static void force_quiescent_state(struct rcu_state *rsp) 2823 { 2824 unsigned long flags; 2825 bool ret; 2826 struct rcu_node *rnp; 2827 struct rcu_node *rnp_old = NULL; 2828 2829 /* Funnel through hierarchy to reduce memory contention. */ 2830 rnp = __this_cpu_read(rsp->rda->mynode); 2831 for (; rnp != NULL; rnp = rnp->parent) { 2832 ret = (READ_ONCE(rsp->gp_flags) & RCU_GP_FLAG_FQS) || 2833 !raw_spin_trylock(&rnp->fqslock); 2834 if (rnp_old != NULL) 2835 raw_spin_unlock(&rnp_old->fqslock); 2836 if (ret) { 2837 rsp->n_force_qs_lh++; 2838 return; 2839 } 2840 rnp_old = rnp; 2841 } 2842 /* rnp_old == rcu_get_root(rsp), rnp == NULL. */ 2843 2844 /* Reached the root of the rcu_node tree, acquire lock. */ 2845 raw_spin_lock_irqsave(&rnp_old->lock, flags); 2846 smp_mb__after_unlock_lock(); 2847 raw_spin_unlock(&rnp_old->fqslock); 2848 if (READ_ONCE(rsp->gp_flags) & RCU_GP_FLAG_FQS) { 2849 rsp->n_force_qs_lh++; 2850 raw_spin_unlock_irqrestore(&rnp_old->lock, flags); 2851 return; /* Someone beat us to it. */ 2852 } 2853 WRITE_ONCE(rsp->gp_flags, READ_ONCE(rsp->gp_flags) | RCU_GP_FLAG_FQS); 2854 raw_spin_unlock_irqrestore(&rnp_old->lock, flags); 2855 rcu_gp_kthread_wake(rsp); 2856 } 2857 2858 /* 2859 * This does the RCU core processing work for the specified rcu_state 2860 * and rcu_data structures. This may be called only from the CPU to 2861 * whom the rdp belongs. 2862 */ 2863 static void 2864 __rcu_process_callbacks(struct rcu_state *rsp) 2865 { 2866 unsigned long flags; 2867 bool needwake; 2868 struct rcu_data *rdp = raw_cpu_ptr(rsp->rda); 2869 2870 WARN_ON_ONCE(rdp->beenonline == 0); 2871 2872 /* Update RCU state based on any recent quiescent states. */ 2873 rcu_check_quiescent_state(rsp, rdp); 2874 2875 /* Does this CPU require a not-yet-started grace period? */ 2876 local_irq_save(flags); 2877 if (cpu_needs_another_gp(rsp, rdp)) { 2878 raw_spin_lock(&rcu_get_root(rsp)->lock); /* irqs disabled. */ 2879 needwake = rcu_start_gp(rsp); 2880 raw_spin_unlock_irqrestore(&rcu_get_root(rsp)->lock, flags); 2881 if (needwake) 2882 rcu_gp_kthread_wake(rsp); 2883 } else { 2884 local_irq_restore(flags); 2885 } 2886 2887 /* If there are callbacks ready, invoke them. */ 2888 if (cpu_has_callbacks_ready_to_invoke(rdp)) 2889 invoke_rcu_callbacks(rsp, rdp); 2890 2891 /* Do any needed deferred wakeups of rcuo kthreads. */ 2892 do_nocb_deferred_wakeup(rdp); 2893 } 2894 2895 /* 2896 * Do RCU core processing for the current CPU. 2897 */ 2898 static void rcu_process_callbacks(struct softirq_action *unused) 2899 { 2900 struct rcu_state *rsp; 2901 2902 if (cpu_is_offline(smp_processor_id())) 2903 return; 2904 trace_rcu_utilization(TPS("Start RCU core")); 2905 for_each_rcu_flavor(rsp) 2906 __rcu_process_callbacks(rsp); 2907 trace_rcu_utilization(TPS("End RCU core")); 2908 } 2909 2910 /* 2911 * Schedule RCU callback invocation. If the specified type of RCU 2912 * does not support RCU priority boosting, just do a direct call, 2913 * otherwise wake up the per-CPU kernel kthread. Note that because we 2914 * are running on the current CPU with softirqs disabled, the 2915 * rcu_cpu_kthread_task cannot disappear out from under us. 2916 */ 2917 static void invoke_rcu_callbacks(struct rcu_state *rsp, struct rcu_data *rdp) 2918 { 2919 if (unlikely(!READ_ONCE(rcu_scheduler_fully_active))) 2920 return; 2921 if (likely(!rsp->boost)) { 2922 rcu_do_batch(rsp, rdp); 2923 return; 2924 } 2925 invoke_rcu_callbacks_kthread(); 2926 } 2927 2928 static void invoke_rcu_core(void) 2929 { 2930 if (cpu_online(smp_processor_id())) 2931 raise_softirq(RCU_SOFTIRQ); 2932 } 2933 2934 /* 2935 * Handle any core-RCU processing required by a call_rcu() invocation. 2936 */ 2937 static void __call_rcu_core(struct rcu_state *rsp, struct rcu_data *rdp, 2938 struct rcu_head *head, unsigned long flags) 2939 { 2940 bool needwake; 2941 2942 /* 2943 * If called from an extended quiescent state, invoke the RCU 2944 * core in order to force a re-evaluation of RCU's idleness. 2945 */ 2946 if (!rcu_is_watching()) 2947 invoke_rcu_core(); 2948 2949 /* If interrupts were disabled or CPU offline, don't invoke RCU core. */ 2950 if (irqs_disabled_flags(flags) || cpu_is_offline(smp_processor_id())) 2951 return; 2952 2953 /* 2954 * Force the grace period if too many callbacks or too long waiting. 2955 * Enforce hysteresis, and don't invoke force_quiescent_state() 2956 * if some other CPU has recently done so. Also, don't bother 2957 * invoking force_quiescent_state() if the newly enqueued callback 2958 * is the only one waiting for a grace period to complete. 2959 */ 2960 if (unlikely(rdp->qlen > rdp->qlen_last_fqs_check + qhimark)) { 2961 2962 /* Are we ignoring a completed grace period? */ 2963 note_gp_changes(rsp, rdp); 2964 2965 /* Start a new grace period if one not already started. */ 2966 if (!rcu_gp_in_progress(rsp)) { 2967 struct rcu_node *rnp_root = rcu_get_root(rsp); 2968 2969 raw_spin_lock(&rnp_root->lock); 2970 smp_mb__after_unlock_lock(); 2971 needwake = rcu_start_gp(rsp); 2972 raw_spin_unlock(&rnp_root->lock); 2973 if (needwake) 2974 rcu_gp_kthread_wake(rsp); 2975 } else { 2976 /* Give the grace period a kick. */ 2977 rdp->blimit = LONG_MAX; 2978 if (rsp->n_force_qs == rdp->n_force_qs_snap && 2979 *rdp->nxttail[RCU_DONE_TAIL] != head) 2980 force_quiescent_state(rsp); 2981 rdp->n_force_qs_snap = rsp->n_force_qs; 2982 rdp->qlen_last_fqs_check = rdp->qlen; 2983 } 2984 } 2985 } 2986 2987 /* 2988 * RCU callback function to leak a callback. 2989 */ 2990 static void rcu_leak_callback(struct rcu_head *rhp) 2991 { 2992 } 2993 2994 /* 2995 * Helper function for call_rcu() and friends. The cpu argument will 2996 * normally be -1, indicating "currently running CPU". It may specify 2997 * a CPU only if that CPU is a no-CBs CPU. Currently, only _rcu_barrier() 2998 * is expected to specify a CPU. 2999 */ 3000 static void 3001 __call_rcu(struct rcu_head *head, void (*func)(struct rcu_head *rcu), 3002 struct rcu_state *rsp, int cpu, bool lazy) 3003 { 3004 unsigned long flags; 3005 struct rcu_data *rdp; 3006 3007 WARN_ON_ONCE((unsigned long)head & 0x1); /* Misaligned rcu_head! */ 3008 if (debug_rcu_head_queue(head)) { 3009 /* Probable double call_rcu(), so leak the callback. */ 3010 WRITE_ONCE(head->func, rcu_leak_callback); 3011 WARN_ONCE(1, "__call_rcu(): Leaked duplicate callback\n"); 3012 return; 3013 } 3014 head->func = func; 3015 head->next = NULL; 3016 3017 /* 3018 * Opportunistically note grace-period endings and beginnings. 3019 * Note that we might see a beginning right after we see an 3020 * end, but never vice versa, since this CPU has to pass through 3021 * a quiescent state betweentimes. 3022 */ 3023 local_irq_save(flags); 3024 rdp = this_cpu_ptr(rsp->rda); 3025 3026 /* Add the callback to our list. */ 3027 if (unlikely(rdp->nxttail[RCU_NEXT_TAIL] == NULL) || cpu != -1) { 3028 int offline; 3029 3030 if (cpu != -1) 3031 rdp = per_cpu_ptr(rsp->rda, cpu); 3032 if (likely(rdp->mynode)) { 3033 /* Post-boot, so this should be for a no-CBs CPU. */ 3034 offline = !__call_rcu_nocb(rdp, head, lazy, flags); 3035 WARN_ON_ONCE(offline); 3036 /* Offline CPU, _call_rcu() illegal, leak callback. */ 3037 local_irq_restore(flags); 3038 return; 3039 } 3040 /* 3041 * Very early boot, before rcu_init(). Initialize if needed 3042 * and then drop through to queue the callback. 3043 */ 3044 BUG_ON(cpu != -1); 3045 WARN_ON_ONCE(!rcu_is_watching()); 3046 if (!likely(rdp->nxtlist)) 3047 init_default_callback_list(rdp); 3048 } 3049 WRITE_ONCE(rdp->qlen, rdp->qlen + 1); 3050 if (lazy) 3051 rdp->qlen_lazy++; 3052 else 3053 rcu_idle_count_callbacks_posted(); 3054 smp_mb(); /* Count before adding callback for rcu_barrier(). */ 3055 *rdp->nxttail[RCU_NEXT_TAIL] = head; 3056 rdp->nxttail[RCU_NEXT_TAIL] = &head->next; 3057 3058 if (__is_kfree_rcu_offset((unsigned long)func)) 3059 trace_rcu_kfree_callback(rsp->name, head, (unsigned long)func, 3060 rdp->qlen_lazy, rdp->qlen); 3061 else 3062 trace_rcu_callback(rsp->name, head, rdp->qlen_lazy, rdp->qlen); 3063 3064 /* Go handle any RCU core processing required. */ 3065 __call_rcu_core(rsp, rdp, head, flags); 3066 local_irq_restore(flags); 3067 } 3068 3069 /* 3070 * Queue an RCU-sched callback for invocation after a grace period. 3071 */ 3072 void call_rcu_sched(struct rcu_head *head, void (*func)(struct rcu_head *rcu)) 3073 { 3074 __call_rcu(head, func, &rcu_sched_state, -1, 0); 3075 } 3076 EXPORT_SYMBOL_GPL(call_rcu_sched); 3077 3078 /* 3079 * Queue an RCU callback for invocation after a quicker grace period. 3080 */ 3081 void call_rcu_bh(struct rcu_head *head, void (*func)(struct rcu_head *rcu)) 3082 { 3083 __call_rcu(head, func, &rcu_bh_state, -1, 0); 3084 } 3085 EXPORT_SYMBOL_GPL(call_rcu_bh); 3086 3087 /* 3088 * Queue an RCU callback for lazy invocation after a grace period. 3089 * This will likely be later named something like "call_rcu_lazy()", 3090 * but this change will require some way of tagging the lazy RCU 3091 * callbacks in the list of pending callbacks. Until then, this 3092 * function may only be called from __kfree_rcu(). 3093 */ 3094 void kfree_call_rcu(struct rcu_head *head, 3095 void (*func)(struct rcu_head *rcu)) 3096 { 3097 __call_rcu(head, func, rcu_state_p, -1, 1); 3098 } 3099 EXPORT_SYMBOL_GPL(kfree_call_rcu); 3100 3101 /* 3102 * Because a context switch is a grace period for RCU-sched and RCU-bh, 3103 * any blocking grace-period wait automatically implies a grace period 3104 * if there is only one CPU online at any point time during execution 3105 * of either synchronize_sched() or synchronize_rcu_bh(). It is OK to 3106 * occasionally incorrectly indicate that there are multiple CPUs online 3107 * when there was in fact only one the whole time, as this just adds 3108 * some overhead: RCU still operates correctly. 3109 */ 3110 static inline int rcu_blocking_is_gp(void) 3111 { 3112 int ret; 3113 3114 might_sleep(); /* Check for RCU read-side critical section. */ 3115 preempt_disable(); 3116 ret = num_online_cpus() <= 1; 3117 preempt_enable(); 3118 return ret; 3119 } 3120 3121 /** 3122 * synchronize_sched - wait until an rcu-sched grace period has elapsed. 3123 * 3124 * Control will return to the caller some time after a full rcu-sched 3125 * grace period has elapsed, in other words after all currently executing 3126 * rcu-sched read-side critical sections have completed. These read-side 3127 * critical sections are delimited by rcu_read_lock_sched() and 3128 * rcu_read_unlock_sched(), and may be nested. Note that preempt_disable(), 3129 * local_irq_disable(), and so on may be used in place of 3130 * rcu_read_lock_sched(). 3131 * 3132 * This means that all preempt_disable code sequences, including NMI and 3133 * non-threaded hardware-interrupt handlers, in progress on entry will 3134 * have completed before this primitive returns. However, this does not 3135 * guarantee that softirq handlers will have completed, since in some 3136 * kernels, these handlers can run in process context, and can block. 3137 * 3138 * Note that this guarantee implies further memory-ordering guarantees. 3139 * On systems with more than one CPU, when synchronize_sched() returns, 3140 * each CPU is guaranteed to have executed a full memory barrier since the 3141 * end of its last RCU-sched read-side critical section whose beginning 3142 * preceded the call to synchronize_sched(). In addition, each CPU having 3143 * an RCU read-side critical section that extends beyond the return from 3144 * synchronize_sched() is guaranteed to have executed a full memory barrier 3145 * after the beginning of synchronize_sched() and before the beginning of 3146 * that RCU read-side critical section. Note that these guarantees include 3147 * CPUs that are offline, idle, or executing in user mode, as well as CPUs 3148 * that are executing in the kernel. 3149 * 3150 * Furthermore, if CPU A invoked synchronize_sched(), which returned 3151 * to its caller on CPU B, then both CPU A and CPU B are guaranteed 3152 * to have executed a full memory barrier during the execution of 3153 * synchronize_sched() -- even if CPU A and CPU B are the same CPU (but 3154 * again only if the system has more than one CPU). 3155 * 3156 * This primitive provides the guarantees made by the (now removed) 3157 * synchronize_kernel() API. In contrast, synchronize_rcu() only 3158 * guarantees that rcu_read_lock() sections will have completed. 3159 * In "classic RCU", these two guarantees happen to be one and 3160 * the same, but can differ in realtime RCU implementations. 3161 */ 3162 void synchronize_sched(void) 3163 { 3164 rcu_lockdep_assert(!lock_is_held(&rcu_bh_lock_map) && 3165 !lock_is_held(&rcu_lock_map) && 3166 !lock_is_held(&rcu_sched_lock_map), 3167 "Illegal synchronize_sched() in RCU-sched read-side critical section"); 3168 if (rcu_blocking_is_gp()) 3169 return; 3170 if (rcu_gp_is_expedited()) 3171 synchronize_sched_expedited(); 3172 else 3173 wait_rcu_gp(call_rcu_sched); 3174 } 3175 EXPORT_SYMBOL_GPL(synchronize_sched); 3176 3177 /** 3178 * synchronize_rcu_bh - wait until an rcu_bh grace period has elapsed. 3179 * 3180 * Control will return to the caller some time after a full rcu_bh grace 3181 * period has elapsed, in other words after all currently executing rcu_bh 3182 * read-side critical sections have completed. RCU read-side critical 3183 * sections are delimited by rcu_read_lock_bh() and rcu_read_unlock_bh(), 3184 * and may be nested. 3185 * 3186 * See the description of synchronize_sched() for more detailed information 3187 * on memory ordering guarantees. 3188 */ 3189 void synchronize_rcu_bh(void) 3190 { 3191 rcu_lockdep_assert(!lock_is_held(&rcu_bh_lock_map) && 3192 !lock_is_held(&rcu_lock_map) && 3193 !lock_is_held(&rcu_sched_lock_map), 3194 "Illegal synchronize_rcu_bh() in RCU-bh read-side critical section"); 3195 if (rcu_blocking_is_gp()) 3196 return; 3197 if (rcu_gp_is_expedited()) 3198 synchronize_rcu_bh_expedited(); 3199 else 3200 wait_rcu_gp(call_rcu_bh); 3201 } 3202 EXPORT_SYMBOL_GPL(synchronize_rcu_bh); 3203 3204 /** 3205 * get_state_synchronize_rcu - Snapshot current RCU state 3206 * 3207 * Returns a cookie that is used by a later call to cond_synchronize_rcu() 3208 * to determine whether or not a full grace period has elapsed in the 3209 * meantime. 3210 */ 3211 unsigned long get_state_synchronize_rcu(void) 3212 { 3213 /* 3214 * Any prior manipulation of RCU-protected data must happen 3215 * before the load from ->gpnum. 3216 */ 3217 smp_mb(); /* ^^^ */ 3218 3219 /* 3220 * Make sure this load happens before the purportedly 3221 * time-consuming work between get_state_synchronize_rcu() 3222 * and cond_synchronize_rcu(). 3223 */ 3224 return smp_load_acquire(&rcu_state_p->gpnum); 3225 } 3226 EXPORT_SYMBOL_GPL(get_state_synchronize_rcu); 3227 3228 /** 3229 * cond_synchronize_rcu - Conditionally wait for an RCU grace period 3230 * 3231 * @oldstate: return value from earlier call to get_state_synchronize_rcu() 3232 * 3233 * If a full RCU grace period has elapsed since the earlier call to 3234 * get_state_synchronize_rcu(), just return. Otherwise, invoke 3235 * synchronize_rcu() to wait for a full grace period. 3236 * 3237 * Yes, this function does not take counter wrap into account. But 3238 * counter wrap is harmless. If the counter wraps, we have waited for 3239 * more than 2 billion grace periods (and way more on a 64-bit system!), 3240 * so waiting for one additional grace period should be just fine. 3241 */ 3242 void cond_synchronize_rcu(unsigned long oldstate) 3243 { 3244 unsigned long newstate; 3245 3246 /* 3247 * Ensure that this load happens before any RCU-destructive 3248 * actions the caller might carry out after we return. 3249 */ 3250 newstate = smp_load_acquire(&rcu_state_p->completed); 3251 if (ULONG_CMP_GE(oldstate, newstate)) 3252 synchronize_rcu(); 3253 } 3254 EXPORT_SYMBOL_GPL(cond_synchronize_rcu); 3255 3256 static int synchronize_sched_expedited_cpu_stop(void *data) 3257 { 3258 /* 3259 * There must be a full memory barrier on each affected CPU 3260 * between the time that try_stop_cpus() is called and the 3261 * time that it returns. 3262 * 3263 * In the current initial implementation of cpu_stop, the 3264 * above condition is already met when the control reaches 3265 * this point and the following smp_mb() is not strictly 3266 * necessary. Do smp_mb() anyway for documentation and 3267 * robustness against future implementation changes. 3268 */ 3269 smp_mb(); /* See above comment block. */ 3270 return 0; 3271 } 3272 3273 /** 3274 * synchronize_sched_expedited - Brute-force RCU-sched grace period 3275 * 3276 * Wait for an RCU-sched grace period to elapse, but use a "big hammer" 3277 * approach to force the grace period to end quickly. This consumes 3278 * significant time on all CPUs and is unfriendly to real-time workloads, 3279 * so is thus not recommended for any sort of common-case code. In fact, 3280 * if you are using synchronize_sched_expedited() in a loop, please 3281 * restructure your code to batch your updates, and then use a single 3282 * synchronize_sched() instead. 3283 * 3284 * This implementation can be thought of as an application of ticket 3285 * locking to RCU, with sync_sched_expedited_started and 3286 * sync_sched_expedited_done taking on the roles of the halves 3287 * of the ticket-lock word. Each task atomically increments 3288 * sync_sched_expedited_started upon entry, snapshotting the old value, 3289 * then attempts to stop all the CPUs. If this succeeds, then each 3290 * CPU will have executed a context switch, resulting in an RCU-sched 3291 * grace period. We are then done, so we use atomic_cmpxchg() to 3292 * update sync_sched_expedited_done to match our snapshot -- but 3293 * only if someone else has not already advanced past our snapshot. 3294 * 3295 * On the other hand, if try_stop_cpus() fails, we check the value 3296 * of sync_sched_expedited_done. If it has advanced past our 3297 * initial snapshot, then someone else must have forced a grace period 3298 * some time after we took our snapshot. In this case, our work is 3299 * done for us, and we can simply return. Otherwise, we try again, 3300 * but keep our initial snapshot for purposes of checking for someone 3301 * doing our work for us. 3302 * 3303 * If we fail too many times in a row, we fall back to synchronize_sched(). 3304 */ 3305 void synchronize_sched_expedited(void) 3306 { 3307 cpumask_var_t cm; 3308 bool cma = false; 3309 int cpu; 3310 long firstsnap, s, snap; 3311 int trycount = 0; 3312 struct rcu_state *rsp = &rcu_sched_state; 3313 3314 /* 3315 * If we are in danger of counter wrap, just do synchronize_sched(). 3316 * By allowing sync_sched_expedited_started to advance no more than 3317 * ULONG_MAX/8 ahead of sync_sched_expedited_done, we are ensuring 3318 * that more than 3.5 billion CPUs would be required to force a 3319 * counter wrap on a 32-bit system. Quite a few more CPUs would of 3320 * course be required on a 64-bit system. 3321 */ 3322 if (ULONG_CMP_GE((ulong)atomic_long_read(&rsp->expedited_start), 3323 (ulong)atomic_long_read(&rsp->expedited_done) + 3324 ULONG_MAX / 8)) { 3325 wait_rcu_gp(call_rcu_sched); 3326 atomic_long_inc(&rsp->expedited_wrap); 3327 return; 3328 } 3329 3330 /* 3331 * Take a ticket. Note that atomic_inc_return() implies a 3332 * full memory barrier. 3333 */ 3334 snap = atomic_long_inc_return(&rsp->expedited_start); 3335 firstsnap = snap; 3336 if (!try_get_online_cpus()) { 3337 /* CPU hotplug operation in flight, fall back to normal GP. */ 3338 wait_rcu_gp(call_rcu_sched); 3339 atomic_long_inc(&rsp->expedited_normal); 3340 return; 3341 } 3342 WARN_ON_ONCE(cpu_is_offline(raw_smp_processor_id())); 3343 3344 /* Offline CPUs, idle CPUs, and any CPU we run on are quiescent. */ 3345 cma = zalloc_cpumask_var(&cm, GFP_KERNEL); 3346 if (cma) { 3347 cpumask_copy(cm, cpu_online_mask); 3348 cpumask_clear_cpu(raw_smp_processor_id(), cm); 3349 for_each_cpu(cpu, cm) { 3350 struct rcu_dynticks *rdtp = &per_cpu(rcu_dynticks, cpu); 3351 3352 if (!(atomic_add_return(0, &rdtp->dynticks) & 0x1)) 3353 cpumask_clear_cpu(cpu, cm); 3354 } 3355 if (cpumask_weight(cm) == 0) 3356 goto all_cpus_idle; 3357 } 3358 3359 /* 3360 * Each pass through the following loop attempts to force a 3361 * context switch on each CPU. 3362 */ 3363 while (try_stop_cpus(cma ? cm : cpu_online_mask, 3364 synchronize_sched_expedited_cpu_stop, 3365 NULL) == -EAGAIN) { 3366 put_online_cpus(); 3367 atomic_long_inc(&rsp->expedited_tryfail); 3368 3369 /* Check to see if someone else did our work for us. */ 3370 s = atomic_long_read(&rsp->expedited_done); 3371 if (ULONG_CMP_GE((ulong)s, (ulong)firstsnap)) { 3372 /* ensure test happens before caller kfree */ 3373 smp_mb__before_atomic(); /* ^^^ */ 3374 atomic_long_inc(&rsp->expedited_workdone1); 3375 free_cpumask_var(cm); 3376 return; 3377 } 3378 3379 /* No joy, try again later. Or just synchronize_sched(). */ 3380 if (trycount++ < 10) { 3381 udelay(trycount * num_online_cpus()); 3382 } else { 3383 wait_rcu_gp(call_rcu_sched); 3384 atomic_long_inc(&rsp->expedited_normal); 3385 free_cpumask_var(cm); 3386 return; 3387 } 3388 3389 /* Recheck to see if someone else did our work for us. */ 3390 s = atomic_long_read(&rsp->expedited_done); 3391 if (ULONG_CMP_GE((ulong)s, (ulong)firstsnap)) { 3392 /* ensure test happens before caller kfree */ 3393 smp_mb__before_atomic(); /* ^^^ */ 3394 atomic_long_inc(&rsp->expedited_workdone2); 3395 free_cpumask_var(cm); 3396 return; 3397 } 3398 3399 /* 3400 * Refetching sync_sched_expedited_started allows later 3401 * callers to piggyback on our grace period. We retry 3402 * after they started, so our grace period works for them, 3403 * and they started after our first try, so their grace 3404 * period works for us. 3405 */ 3406 if (!try_get_online_cpus()) { 3407 /* CPU hotplug operation in flight, use normal GP. */ 3408 wait_rcu_gp(call_rcu_sched); 3409 atomic_long_inc(&rsp->expedited_normal); 3410 free_cpumask_var(cm); 3411 return; 3412 } 3413 snap = atomic_long_read(&rsp->expedited_start); 3414 smp_mb(); /* ensure read is before try_stop_cpus(). */ 3415 } 3416 atomic_long_inc(&rsp->expedited_stoppedcpus); 3417 3418 all_cpus_idle: 3419 free_cpumask_var(cm); 3420 3421 /* 3422 * Everyone up to our most recent fetch is covered by our grace 3423 * period. Update the counter, but only if our work is still 3424 * relevant -- which it won't be if someone who started later 3425 * than we did already did their update. 3426 */ 3427 do { 3428 atomic_long_inc(&rsp->expedited_done_tries); 3429 s = atomic_long_read(&rsp->expedited_done); 3430 if (ULONG_CMP_GE((ulong)s, (ulong)snap)) { 3431 /* ensure test happens before caller kfree */ 3432 smp_mb__before_atomic(); /* ^^^ */ 3433 atomic_long_inc(&rsp->expedited_done_lost); 3434 break; 3435 } 3436 } while (atomic_long_cmpxchg(&rsp->expedited_done, s, snap) != s); 3437 atomic_long_inc(&rsp->expedited_done_exit); 3438 3439 put_online_cpus(); 3440 } 3441 EXPORT_SYMBOL_GPL(synchronize_sched_expedited); 3442 3443 /* 3444 * Check to see if there is any immediate RCU-related work to be done 3445 * by the current CPU, for the specified type of RCU, returning 1 if so. 3446 * The checks are in order of increasing expense: checks that can be 3447 * carried out against CPU-local state are performed first. However, 3448 * we must check for CPU stalls first, else we might not get a chance. 3449 */ 3450 static int __rcu_pending(struct rcu_state *rsp, struct rcu_data *rdp) 3451 { 3452 struct rcu_node *rnp = rdp->mynode; 3453 3454 rdp->n_rcu_pending++; 3455 3456 /* Check for CPU stalls, if enabled. */ 3457 check_cpu_stall(rsp, rdp); 3458 3459 /* Is this CPU a NO_HZ_FULL CPU that should ignore RCU? */ 3460 if (rcu_nohz_full_cpu(rsp)) 3461 return 0; 3462 3463 /* Is the RCU core waiting for a quiescent state from this CPU? */ 3464 if (rcu_scheduler_fully_active && 3465 rdp->qs_pending && !rdp->passed_quiesce && 3466 rdp->rcu_qs_ctr_snap == __this_cpu_read(rcu_qs_ctr)) { 3467 rdp->n_rp_qs_pending++; 3468 } else if (rdp->qs_pending && 3469 (rdp->passed_quiesce || 3470 rdp->rcu_qs_ctr_snap != __this_cpu_read(rcu_qs_ctr))) { 3471 rdp->n_rp_report_qs++; 3472 return 1; 3473 } 3474 3475 /* Does this CPU have callbacks ready to invoke? */ 3476 if (cpu_has_callbacks_ready_to_invoke(rdp)) { 3477 rdp->n_rp_cb_ready++; 3478 return 1; 3479 } 3480 3481 /* Has RCU gone idle with this CPU needing another grace period? */ 3482 if (cpu_needs_another_gp(rsp, rdp)) { 3483 rdp->n_rp_cpu_needs_gp++; 3484 return 1; 3485 } 3486 3487 /* Has another RCU grace period completed? */ 3488 if (READ_ONCE(rnp->completed) != rdp->completed) { /* outside lock */ 3489 rdp->n_rp_gp_completed++; 3490 return 1; 3491 } 3492 3493 /* Has a new RCU grace period started? */ 3494 if (READ_ONCE(rnp->gpnum) != rdp->gpnum || 3495 unlikely(READ_ONCE(rdp->gpwrap))) { /* outside lock */ 3496 rdp->n_rp_gp_started++; 3497 return 1; 3498 } 3499 3500 /* Does this CPU need a deferred NOCB wakeup? */ 3501 if (rcu_nocb_need_deferred_wakeup(rdp)) { 3502 rdp->n_rp_nocb_defer_wakeup++; 3503 return 1; 3504 } 3505 3506 /* nothing to do */ 3507 rdp->n_rp_need_nothing++; 3508 return 0; 3509 } 3510 3511 /* 3512 * Check to see if there is any immediate RCU-related work to be done 3513 * by the current CPU, returning 1 if so. This function is part of the 3514 * RCU implementation; it is -not- an exported member of the RCU API. 3515 */ 3516 static int rcu_pending(void) 3517 { 3518 struct rcu_state *rsp; 3519 3520 for_each_rcu_flavor(rsp) 3521 if (__rcu_pending(rsp, this_cpu_ptr(rsp->rda))) 3522 return 1; 3523 return 0; 3524 } 3525 3526 /* 3527 * Return true if the specified CPU has any callback. If all_lazy is 3528 * non-NULL, store an indication of whether all callbacks are lazy. 3529 * (If there are no callbacks, all of them are deemed to be lazy.) 3530 */ 3531 static bool __maybe_unused rcu_cpu_has_callbacks(bool *all_lazy) 3532 { 3533 bool al = true; 3534 bool hc = false; 3535 struct rcu_data *rdp; 3536 struct rcu_state *rsp; 3537 3538 for_each_rcu_flavor(rsp) { 3539 rdp = this_cpu_ptr(rsp->rda); 3540 if (!rdp->nxtlist) 3541 continue; 3542 hc = true; 3543 if (rdp->qlen != rdp->qlen_lazy || !all_lazy) { 3544 al = false; 3545 break; 3546 } 3547 } 3548 if (all_lazy) 3549 *all_lazy = al; 3550 return hc; 3551 } 3552 3553 /* 3554 * Helper function for _rcu_barrier() tracing. If tracing is disabled, 3555 * the compiler is expected to optimize this away. 3556 */ 3557 static void _rcu_barrier_trace(struct rcu_state *rsp, const char *s, 3558 int cpu, unsigned long done) 3559 { 3560 trace_rcu_barrier(rsp->name, s, cpu, 3561 atomic_read(&rsp->barrier_cpu_count), done); 3562 } 3563 3564 /* 3565 * RCU callback function for _rcu_barrier(). If we are last, wake 3566 * up the task executing _rcu_barrier(). 3567 */ 3568 static void rcu_barrier_callback(struct rcu_head *rhp) 3569 { 3570 struct rcu_data *rdp = container_of(rhp, struct rcu_data, barrier_head); 3571 struct rcu_state *rsp = rdp->rsp; 3572 3573 if (atomic_dec_and_test(&rsp->barrier_cpu_count)) { 3574 _rcu_barrier_trace(rsp, "LastCB", -1, rsp->n_barrier_done); 3575 complete(&rsp->barrier_completion); 3576 } else { 3577 _rcu_barrier_trace(rsp, "CB", -1, rsp->n_barrier_done); 3578 } 3579 } 3580 3581 /* 3582 * Called with preemption disabled, and from cross-cpu IRQ context. 3583 */ 3584 static void rcu_barrier_func(void *type) 3585 { 3586 struct rcu_state *rsp = type; 3587 struct rcu_data *rdp = raw_cpu_ptr(rsp->rda); 3588 3589 _rcu_barrier_trace(rsp, "IRQ", -1, rsp->n_barrier_done); 3590 atomic_inc(&rsp->barrier_cpu_count); 3591 rsp->call(&rdp->barrier_head, rcu_barrier_callback); 3592 } 3593 3594 /* 3595 * Orchestrate the specified type of RCU barrier, waiting for all 3596 * RCU callbacks of the specified type to complete. 3597 */ 3598 static void _rcu_barrier(struct rcu_state *rsp) 3599 { 3600 int cpu; 3601 struct rcu_data *rdp; 3602 unsigned long snap = READ_ONCE(rsp->n_barrier_done); 3603 unsigned long snap_done; 3604 3605 _rcu_barrier_trace(rsp, "Begin", -1, snap); 3606 3607 /* Take mutex to serialize concurrent rcu_barrier() requests. */ 3608 mutex_lock(&rsp->barrier_mutex); 3609 3610 /* 3611 * Ensure that all prior references, including to ->n_barrier_done, 3612 * are ordered before the _rcu_barrier() machinery. 3613 */ 3614 smp_mb(); /* See above block comment. */ 3615 3616 /* 3617 * Recheck ->n_barrier_done to see if others did our work for us. 3618 * This means checking ->n_barrier_done for an even-to-odd-to-even 3619 * transition. The "if" expression below therefore rounds the old 3620 * value up to the next even number and adds two before comparing. 3621 */ 3622 snap_done = rsp->n_barrier_done; 3623 _rcu_barrier_trace(rsp, "Check", -1, snap_done); 3624 3625 /* 3626 * If the value in snap is odd, we needed to wait for the current 3627 * rcu_barrier() to complete, then wait for the next one, in other 3628 * words, we need the value of snap_done to be three larger than 3629 * the value of snap. On the other hand, if the value in snap is 3630 * even, we only had to wait for the next rcu_barrier() to complete, 3631 * in other words, we need the value of snap_done to be only two 3632 * greater than the value of snap. The "(snap + 3) & ~0x1" computes 3633 * this for us (thank you, Linus!). 3634 */ 3635 if (ULONG_CMP_GE(snap_done, (snap + 3) & ~0x1)) { 3636 _rcu_barrier_trace(rsp, "EarlyExit", -1, snap_done); 3637 smp_mb(); /* caller's subsequent code after above check. */ 3638 mutex_unlock(&rsp->barrier_mutex); 3639 return; 3640 } 3641 3642 /* 3643 * Increment ->n_barrier_done to avoid duplicate work. Use 3644 * WRITE_ONCE() to prevent the compiler from speculating 3645 * the increment to precede the early-exit check. 3646 */ 3647 WRITE_ONCE(rsp->n_barrier_done, rsp->n_barrier_done + 1); 3648 WARN_ON_ONCE((rsp->n_barrier_done & 0x1) != 1); 3649 _rcu_barrier_trace(rsp, "Inc1", -1, rsp->n_barrier_done); 3650 smp_mb(); /* Order ->n_barrier_done increment with below mechanism. */ 3651 3652 /* 3653 * Initialize the count to one rather than to zero in order to 3654 * avoid a too-soon return to zero in case of a short grace period 3655 * (or preemption of this task). Exclude CPU-hotplug operations 3656 * to ensure that no offline CPU has callbacks queued. 3657 */ 3658 init_completion(&rsp->barrier_completion); 3659 atomic_set(&rsp->barrier_cpu_count, 1); 3660 get_online_cpus(); 3661 3662 /* 3663 * Force each CPU with callbacks to register a new callback. 3664 * When that callback is invoked, we will know that all of the 3665 * corresponding CPU's preceding callbacks have been invoked. 3666 */ 3667 for_each_possible_cpu(cpu) { 3668 if (!cpu_online(cpu) && !rcu_is_nocb_cpu(cpu)) 3669 continue; 3670 rdp = per_cpu_ptr(rsp->rda, cpu); 3671 if (rcu_is_nocb_cpu(cpu)) { 3672 if (!rcu_nocb_cpu_needs_barrier(rsp, cpu)) { 3673 _rcu_barrier_trace(rsp, "OfflineNoCB", cpu, 3674 rsp->n_barrier_done); 3675 } else { 3676 _rcu_barrier_trace(rsp, "OnlineNoCB", cpu, 3677 rsp->n_barrier_done); 3678 smp_mb__before_atomic(); 3679 atomic_inc(&rsp->barrier_cpu_count); 3680 __call_rcu(&rdp->barrier_head, 3681 rcu_barrier_callback, rsp, cpu, 0); 3682 } 3683 } else if (READ_ONCE(rdp->qlen)) { 3684 _rcu_barrier_trace(rsp, "OnlineQ", cpu, 3685 rsp->n_barrier_done); 3686 smp_call_function_single(cpu, rcu_barrier_func, rsp, 1); 3687 } else { 3688 _rcu_barrier_trace(rsp, "OnlineNQ", cpu, 3689 rsp->n_barrier_done); 3690 } 3691 } 3692 put_online_cpus(); 3693 3694 /* 3695 * Now that we have an rcu_barrier_callback() callback on each 3696 * CPU, and thus each counted, remove the initial count. 3697 */ 3698 if (atomic_dec_and_test(&rsp->barrier_cpu_count)) 3699 complete(&rsp->barrier_completion); 3700 3701 /* Increment ->n_barrier_done to prevent duplicate work. */ 3702 smp_mb(); /* Keep increment after above mechanism. */ 3703 WRITE_ONCE(rsp->n_barrier_done, rsp->n_barrier_done + 1); 3704 WARN_ON_ONCE((rsp->n_barrier_done & 0x1) != 0); 3705 _rcu_barrier_trace(rsp, "Inc2", -1, rsp->n_barrier_done); 3706 smp_mb(); /* Keep increment before caller's subsequent code. */ 3707 3708 /* Wait for all rcu_barrier_callback() callbacks to be invoked. */ 3709 wait_for_completion(&rsp->barrier_completion); 3710 3711 /* Other rcu_barrier() invocations can now safely proceed. */ 3712 mutex_unlock(&rsp->barrier_mutex); 3713 } 3714 3715 /** 3716 * rcu_barrier_bh - Wait until all in-flight call_rcu_bh() callbacks complete. 3717 */ 3718 void rcu_barrier_bh(void) 3719 { 3720 _rcu_barrier(&rcu_bh_state); 3721 } 3722 EXPORT_SYMBOL_GPL(rcu_barrier_bh); 3723 3724 /** 3725 * rcu_barrier_sched - Wait for in-flight call_rcu_sched() callbacks. 3726 */ 3727 void rcu_barrier_sched(void) 3728 { 3729 _rcu_barrier(&rcu_sched_state); 3730 } 3731 EXPORT_SYMBOL_GPL(rcu_barrier_sched); 3732 3733 /* 3734 * Propagate ->qsinitmask bits up the rcu_node tree to account for the 3735 * first CPU in a given leaf rcu_node structure coming online. The caller 3736 * must hold the corresponding leaf rcu_node ->lock with interrrupts 3737 * disabled. 3738 */ 3739 static void rcu_init_new_rnp(struct rcu_node *rnp_leaf) 3740 { 3741 long mask; 3742 struct rcu_node *rnp = rnp_leaf; 3743 3744 for (;;) { 3745 mask = rnp->grpmask; 3746 rnp = rnp->parent; 3747 if (rnp == NULL) 3748 return; 3749 raw_spin_lock(&rnp->lock); /* Interrupts already disabled. */ 3750 rnp->qsmaskinit |= mask; 3751 raw_spin_unlock(&rnp->lock); /* Interrupts remain disabled. */ 3752 } 3753 } 3754 3755 /* 3756 * Do boot-time initialization of a CPU's per-CPU RCU data. 3757 */ 3758 static void __init 3759 rcu_boot_init_percpu_data(int cpu, struct rcu_state *rsp) 3760 { 3761 unsigned long flags; 3762 struct rcu_data *rdp = per_cpu_ptr(rsp->rda, cpu); 3763 struct rcu_node *rnp = rcu_get_root(rsp); 3764 3765 /* Set up local state, ensuring consistent view of global state. */ 3766 raw_spin_lock_irqsave(&rnp->lock, flags); 3767 rdp->grpmask = 1UL << (cpu - rdp->mynode->grplo); 3768 rdp->dynticks = &per_cpu(rcu_dynticks, cpu); 3769 WARN_ON_ONCE(rdp->dynticks->dynticks_nesting != DYNTICK_TASK_EXIT_IDLE); 3770 WARN_ON_ONCE(atomic_read(&rdp->dynticks->dynticks) != 1); 3771 rdp->cpu = cpu; 3772 rdp->rsp = rsp; 3773 rcu_boot_init_nocb_percpu_data(rdp); 3774 raw_spin_unlock_irqrestore(&rnp->lock, flags); 3775 } 3776 3777 /* 3778 * Initialize a CPU's per-CPU RCU data. Note that only one online or 3779 * offline event can be happening at a given time. Note also that we 3780 * can accept some slop in the rsp->completed access due to the fact 3781 * that this CPU cannot possibly have any RCU callbacks in flight yet. 3782 */ 3783 static void 3784 rcu_init_percpu_data(int cpu, struct rcu_state *rsp) 3785 { 3786 unsigned long flags; 3787 unsigned long mask; 3788 struct rcu_data *rdp = per_cpu_ptr(rsp->rda, cpu); 3789 struct rcu_node *rnp = rcu_get_root(rsp); 3790 3791 /* Set up local state, ensuring consistent view of global state. */ 3792 raw_spin_lock_irqsave(&rnp->lock, flags); 3793 rdp->beenonline = 1; /* We have now been online. */ 3794 rdp->qlen_last_fqs_check = 0; 3795 rdp->n_force_qs_snap = rsp->n_force_qs; 3796 rdp->blimit = blimit; 3797 if (!rdp->nxtlist) 3798 init_callback_list(rdp); /* Re-enable callbacks on this CPU. */ 3799 rdp->dynticks->dynticks_nesting = DYNTICK_TASK_EXIT_IDLE; 3800 rcu_sysidle_init_percpu_data(rdp->dynticks); 3801 atomic_set(&rdp->dynticks->dynticks, 3802 (atomic_read(&rdp->dynticks->dynticks) & ~0x1) + 1); 3803 raw_spin_unlock(&rnp->lock); /* irqs remain disabled. */ 3804 3805 /* 3806 * Add CPU to leaf rcu_node pending-online bitmask. Any needed 3807 * propagation up the rcu_node tree will happen at the beginning 3808 * of the next grace period. 3809 */ 3810 rnp = rdp->mynode; 3811 mask = rdp->grpmask; 3812 raw_spin_lock(&rnp->lock); /* irqs already disabled. */ 3813 smp_mb__after_unlock_lock(); 3814 rnp->qsmaskinitnext |= mask; 3815 rdp->gpnum = rnp->completed; /* Make CPU later note any new GP. */ 3816 rdp->completed = rnp->completed; 3817 rdp->passed_quiesce = false; 3818 rdp->rcu_qs_ctr_snap = per_cpu(rcu_qs_ctr, cpu); 3819 rdp->qs_pending = false; 3820 trace_rcu_grace_period(rsp->name, rdp->gpnum, TPS("cpuonl")); 3821 raw_spin_unlock_irqrestore(&rnp->lock, flags); 3822 } 3823 3824 static void rcu_prepare_cpu(int cpu) 3825 { 3826 struct rcu_state *rsp; 3827 3828 for_each_rcu_flavor(rsp) 3829 rcu_init_percpu_data(cpu, rsp); 3830 } 3831 3832 /* 3833 * Handle CPU online/offline notification events. 3834 */ 3835 int rcu_cpu_notify(struct notifier_block *self, 3836 unsigned long action, void *hcpu) 3837 { 3838 long cpu = (long)hcpu; 3839 struct rcu_data *rdp = per_cpu_ptr(rcu_state_p->rda, cpu); 3840 struct rcu_node *rnp = rdp->mynode; 3841 struct rcu_state *rsp; 3842 3843 switch (action) { 3844 case CPU_UP_PREPARE: 3845 case CPU_UP_PREPARE_FROZEN: 3846 rcu_prepare_cpu(cpu); 3847 rcu_prepare_kthreads(cpu); 3848 rcu_spawn_all_nocb_kthreads(cpu); 3849 break; 3850 case CPU_ONLINE: 3851 case CPU_DOWN_FAILED: 3852 rcu_boost_kthread_setaffinity(rnp, -1); 3853 break; 3854 case CPU_DOWN_PREPARE: 3855 rcu_boost_kthread_setaffinity(rnp, cpu); 3856 break; 3857 case CPU_DYING: 3858 case CPU_DYING_FROZEN: 3859 for_each_rcu_flavor(rsp) 3860 rcu_cleanup_dying_cpu(rsp); 3861 break; 3862 case CPU_DYING_IDLE: 3863 for_each_rcu_flavor(rsp) { 3864 rcu_cleanup_dying_idle_cpu(cpu, rsp); 3865 } 3866 break; 3867 case CPU_DEAD: 3868 case CPU_DEAD_FROZEN: 3869 case CPU_UP_CANCELED: 3870 case CPU_UP_CANCELED_FROZEN: 3871 for_each_rcu_flavor(rsp) { 3872 rcu_cleanup_dead_cpu(cpu, rsp); 3873 do_nocb_deferred_wakeup(per_cpu_ptr(rsp->rda, cpu)); 3874 } 3875 break; 3876 default: 3877 break; 3878 } 3879 return NOTIFY_OK; 3880 } 3881 3882 static int rcu_pm_notify(struct notifier_block *self, 3883 unsigned long action, void *hcpu) 3884 { 3885 switch (action) { 3886 case PM_HIBERNATION_PREPARE: 3887 case PM_SUSPEND_PREPARE: 3888 if (nr_cpu_ids <= 256) /* Expediting bad for large systems. */ 3889 rcu_expedite_gp(); 3890 break; 3891 case PM_POST_HIBERNATION: 3892 case PM_POST_SUSPEND: 3893 if (nr_cpu_ids <= 256) /* Expediting bad for large systems. */ 3894 rcu_unexpedite_gp(); 3895 break; 3896 default: 3897 break; 3898 } 3899 return NOTIFY_OK; 3900 } 3901 3902 /* 3903 * Spawn the kthreads that handle each RCU flavor's grace periods. 3904 */ 3905 static int __init rcu_spawn_gp_kthread(void) 3906 { 3907 unsigned long flags; 3908 int kthread_prio_in = kthread_prio; 3909 struct rcu_node *rnp; 3910 struct rcu_state *rsp; 3911 struct sched_param sp; 3912 struct task_struct *t; 3913 3914 /* Force priority into range. */ 3915 if (IS_ENABLED(CONFIG_RCU_BOOST) && kthread_prio < 1) 3916 kthread_prio = 1; 3917 else if (kthread_prio < 0) 3918 kthread_prio = 0; 3919 else if (kthread_prio > 99) 3920 kthread_prio = 99; 3921 if (kthread_prio != kthread_prio_in) 3922 pr_alert("rcu_spawn_gp_kthread(): Limited prio to %d from %d\n", 3923 kthread_prio, kthread_prio_in); 3924 3925 rcu_scheduler_fully_active = 1; 3926 for_each_rcu_flavor(rsp) { 3927 t = kthread_create(rcu_gp_kthread, rsp, "%s", rsp->name); 3928 BUG_ON(IS_ERR(t)); 3929 rnp = rcu_get_root(rsp); 3930 raw_spin_lock_irqsave(&rnp->lock, flags); 3931 rsp->gp_kthread = t; 3932 if (kthread_prio) { 3933 sp.sched_priority = kthread_prio; 3934 sched_setscheduler_nocheck(t, SCHED_FIFO, &sp); 3935 } 3936 wake_up_process(t); 3937 raw_spin_unlock_irqrestore(&rnp->lock, flags); 3938 } 3939 rcu_spawn_nocb_kthreads(); 3940 rcu_spawn_boost_kthreads(); 3941 return 0; 3942 } 3943 early_initcall(rcu_spawn_gp_kthread); 3944 3945 /* 3946 * This function is invoked towards the end of the scheduler's initialization 3947 * process. Before this is called, the idle task might contain 3948 * RCU read-side critical sections (during which time, this idle 3949 * task is booting the system). After this function is called, the 3950 * idle tasks are prohibited from containing RCU read-side critical 3951 * sections. This function also enables RCU lockdep checking. 3952 */ 3953 void rcu_scheduler_starting(void) 3954 { 3955 WARN_ON(num_online_cpus() != 1); 3956 WARN_ON(nr_context_switches() > 0); 3957 rcu_scheduler_active = 1; 3958 } 3959 3960 /* 3961 * Compute the per-level fanout, either using the exact fanout specified 3962 * or balancing the tree, depending on the rcu_fanout_exact boot parameter. 3963 */ 3964 static void __init rcu_init_levelspread(struct rcu_state *rsp) 3965 { 3966 int i; 3967 3968 if (rcu_fanout_exact) { 3969 rsp->levelspread[rcu_num_lvls - 1] = rcu_fanout_leaf; 3970 for (i = rcu_num_lvls - 2; i >= 0; i--) 3971 rsp->levelspread[i] = RCU_FANOUT; 3972 } else { 3973 int ccur; 3974 int cprv; 3975 3976 cprv = nr_cpu_ids; 3977 for (i = rcu_num_lvls - 1; i >= 0; i--) { 3978 ccur = rsp->levelcnt[i]; 3979 rsp->levelspread[i] = (cprv + ccur - 1) / ccur; 3980 cprv = ccur; 3981 } 3982 } 3983 } 3984 3985 /* 3986 * Helper function for rcu_init() that initializes one rcu_state structure. 3987 */ 3988 static void __init rcu_init_one(struct rcu_state *rsp, 3989 struct rcu_data __percpu *rda) 3990 { 3991 static const char * const buf[] = { 3992 "rcu_node_0", 3993 "rcu_node_1", 3994 "rcu_node_2", 3995 "rcu_node_3" }; /* Match MAX_RCU_LVLS */ 3996 static const char * const fqs[] = { 3997 "rcu_node_fqs_0", 3998 "rcu_node_fqs_1", 3999 "rcu_node_fqs_2", 4000 "rcu_node_fqs_3" }; /* Match MAX_RCU_LVLS */ 4001 static u8 fl_mask = 0x1; 4002 int cpustride = 1; 4003 int i; 4004 int j; 4005 struct rcu_node *rnp; 4006 4007 BUILD_BUG_ON(MAX_RCU_LVLS > ARRAY_SIZE(buf)); /* Fix buf[] init! */ 4008 4009 /* Silence gcc 4.8 false positive about array index out of range. */ 4010 if (rcu_num_lvls <= 0 || rcu_num_lvls > RCU_NUM_LVLS) 4011 panic("rcu_init_one: rcu_num_lvls out of range"); 4012 4013 /* Initialize the level-tracking arrays. */ 4014 4015 for (i = 0; i < rcu_num_lvls; i++) 4016 rsp->levelcnt[i] = num_rcu_lvl[i]; 4017 for (i = 1; i < rcu_num_lvls; i++) 4018 rsp->level[i] = rsp->level[i - 1] + rsp->levelcnt[i - 1]; 4019 rcu_init_levelspread(rsp); 4020 rsp->flavor_mask = fl_mask; 4021 fl_mask <<= 1; 4022 4023 /* Initialize the elements themselves, starting from the leaves. */ 4024 4025 for (i = rcu_num_lvls - 1; i >= 0; i--) { 4026 cpustride *= rsp->levelspread[i]; 4027 rnp = rsp->level[i]; 4028 for (j = 0; j < rsp->levelcnt[i]; j++, rnp++) { 4029 raw_spin_lock_init(&rnp->lock); 4030 lockdep_set_class_and_name(&rnp->lock, 4031 &rcu_node_class[i], buf[i]); 4032 raw_spin_lock_init(&rnp->fqslock); 4033 lockdep_set_class_and_name(&rnp->fqslock, 4034 &rcu_fqs_class[i], fqs[i]); 4035 rnp->gpnum = rsp->gpnum; 4036 rnp->completed = rsp->completed; 4037 rnp->qsmask = 0; 4038 rnp->qsmaskinit = 0; 4039 rnp->grplo = j * cpustride; 4040 rnp->grphi = (j + 1) * cpustride - 1; 4041 if (rnp->grphi >= nr_cpu_ids) 4042 rnp->grphi = nr_cpu_ids - 1; 4043 if (i == 0) { 4044 rnp->grpnum = 0; 4045 rnp->grpmask = 0; 4046 rnp->parent = NULL; 4047 } else { 4048 rnp->grpnum = j % rsp->levelspread[i - 1]; 4049 rnp->grpmask = 1UL << rnp->grpnum; 4050 rnp->parent = rsp->level[i - 1] + 4051 j / rsp->levelspread[i - 1]; 4052 } 4053 rnp->level = i; 4054 INIT_LIST_HEAD(&rnp->blkd_tasks); 4055 rcu_init_one_nocb(rnp); 4056 } 4057 } 4058 4059 init_waitqueue_head(&rsp->gp_wq); 4060 rnp = rsp->level[rcu_num_lvls - 1]; 4061 for_each_possible_cpu(i) { 4062 while (i > rnp->grphi) 4063 rnp++; 4064 per_cpu_ptr(rsp->rda, i)->mynode = rnp; 4065 rcu_boot_init_percpu_data(i, rsp); 4066 } 4067 list_add(&rsp->flavors, &rcu_struct_flavors); 4068 } 4069 4070 /* 4071 * Compute the rcu_node tree geometry from kernel parameters. This cannot 4072 * replace the definitions in tree.h because those are needed to size 4073 * the ->node array in the rcu_state structure. 4074 */ 4075 static void __init rcu_init_geometry(void) 4076 { 4077 ulong d; 4078 int i; 4079 int j; 4080 int n = nr_cpu_ids; 4081 int rcu_capacity[MAX_RCU_LVLS + 1]; 4082 4083 /* 4084 * Initialize any unspecified boot parameters. 4085 * The default values of jiffies_till_first_fqs and 4086 * jiffies_till_next_fqs are set to the RCU_JIFFIES_TILL_FORCE_QS 4087 * value, which is a function of HZ, then adding one for each 4088 * RCU_JIFFIES_FQS_DIV CPUs that might be on the system. 4089 */ 4090 d = RCU_JIFFIES_TILL_FORCE_QS + nr_cpu_ids / RCU_JIFFIES_FQS_DIV; 4091 if (jiffies_till_first_fqs == ULONG_MAX) 4092 jiffies_till_first_fqs = d; 4093 if (jiffies_till_next_fqs == ULONG_MAX) 4094 jiffies_till_next_fqs = d; 4095 4096 /* If the compile-time values are accurate, just leave. */ 4097 if (rcu_fanout_leaf == RCU_FANOUT_LEAF && 4098 nr_cpu_ids == NR_CPUS) 4099 return; 4100 pr_info("RCU: Adjusting geometry for rcu_fanout_leaf=%d, nr_cpu_ids=%d\n", 4101 rcu_fanout_leaf, nr_cpu_ids); 4102 4103 /* 4104 * Compute number of nodes that can be handled an rcu_node tree 4105 * with the given number of levels. Setting rcu_capacity[0] makes 4106 * some of the arithmetic easier. 4107 */ 4108 rcu_capacity[0] = 1; 4109 rcu_capacity[1] = rcu_fanout_leaf; 4110 for (i = 2; i <= MAX_RCU_LVLS; i++) 4111 rcu_capacity[i] = rcu_capacity[i - 1] * RCU_FANOUT; 4112 4113 /* 4114 * The boot-time rcu_fanout_leaf parameter is only permitted 4115 * to increase the leaf-level fanout, not decrease it. Of course, 4116 * the leaf-level fanout cannot exceed the number of bits in 4117 * the rcu_node masks. Finally, the tree must be able to accommodate 4118 * the configured number of CPUs. Complain and fall back to the 4119 * compile-time values if these limits are exceeded. 4120 */ 4121 if (rcu_fanout_leaf < RCU_FANOUT_LEAF || 4122 rcu_fanout_leaf > sizeof(unsigned long) * 8 || 4123 n > rcu_capacity[MAX_RCU_LVLS]) { 4124 WARN_ON(1); 4125 return; 4126 } 4127 4128 /* Calculate the number of rcu_nodes at each level of the tree. */ 4129 for (i = 1; i <= MAX_RCU_LVLS; i++) 4130 if (n <= rcu_capacity[i]) { 4131 for (j = 0; j <= i; j++) 4132 num_rcu_lvl[j] = 4133 DIV_ROUND_UP(n, rcu_capacity[i - j]); 4134 rcu_num_lvls = i; 4135 for (j = i + 1; j <= MAX_RCU_LVLS; j++) 4136 num_rcu_lvl[j] = 0; 4137 break; 4138 } 4139 4140 /* Calculate the total number of rcu_node structures. */ 4141 rcu_num_nodes = 0; 4142 for (i = 0; i <= MAX_RCU_LVLS; i++) 4143 rcu_num_nodes += num_rcu_lvl[i]; 4144 rcu_num_nodes -= n; 4145 } 4146 4147 /* 4148 * Dump out the structure of the rcu_node combining tree associated 4149 * with the rcu_state structure referenced by rsp. 4150 */ 4151 static void __init rcu_dump_rcu_node_tree(struct rcu_state *rsp) 4152 { 4153 int level = 0; 4154 struct rcu_node *rnp; 4155 4156 pr_info("rcu_node tree layout dump\n"); 4157 pr_info(" "); 4158 rcu_for_each_node_breadth_first(rsp, rnp) { 4159 if (rnp->level != level) { 4160 pr_cont("\n"); 4161 pr_info(" "); 4162 level = rnp->level; 4163 } 4164 pr_cont("%d:%d ^%d ", rnp->grplo, rnp->grphi, rnp->grpnum); 4165 } 4166 pr_cont("\n"); 4167 } 4168 4169 void __init rcu_init(void) 4170 { 4171 int cpu; 4172 4173 rcu_early_boot_tests(); 4174 4175 rcu_bootup_announce(); 4176 rcu_init_geometry(); 4177 rcu_init_one(&rcu_bh_state, &rcu_bh_data); 4178 rcu_init_one(&rcu_sched_state, &rcu_sched_data); 4179 if (dump_tree) 4180 rcu_dump_rcu_node_tree(&rcu_sched_state); 4181 __rcu_init_preempt(); 4182 open_softirq(RCU_SOFTIRQ, rcu_process_callbacks); 4183 4184 /* 4185 * We don't need protection against CPU-hotplug here because 4186 * this is called early in boot, before either interrupts 4187 * or the scheduler are operational. 4188 */ 4189 cpu_notifier(rcu_cpu_notify, 0); 4190 pm_notifier(rcu_pm_notify, 0); 4191 for_each_online_cpu(cpu) 4192 rcu_cpu_notify(NULL, CPU_UP_PREPARE, (void *)(long)cpu); 4193 } 4194 4195 #include "tree_plugin.h" 4196