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