1 // SPDX-License-Identifier: GPL-2.0+ 2 /* 3 * Sleepable Read-Copy Update mechanism for mutual exclusion. 4 * 5 * Copyright (C) IBM Corporation, 2006 6 * Copyright (C) Fujitsu, 2012 7 * 8 * Authors: Paul McKenney <paulmck@linux.ibm.com> 9 * Lai Jiangshan <laijs@cn.fujitsu.com> 10 * 11 * For detailed explanation of Read-Copy Update mechanism see - 12 * Documentation/RCU/ *.txt 13 * 14 */ 15 16 #define pr_fmt(fmt) "rcu: " fmt 17 18 #include <linux/export.h> 19 #include <linux/mutex.h> 20 #include <linux/percpu.h> 21 #include <linux/preempt.h> 22 #include <linux/rcupdate_wait.h> 23 #include <linux/sched.h> 24 #include <linux/smp.h> 25 #include <linux/delay.h> 26 #include <linux/module.h> 27 #include <linux/slab.h> 28 #include <linux/srcu.h> 29 30 #include "rcu.h" 31 #include "rcu_segcblist.h" 32 33 /* Holdoff in nanoseconds for auto-expediting. */ 34 #define DEFAULT_SRCU_EXP_HOLDOFF (25 * 1000) 35 static ulong exp_holdoff = DEFAULT_SRCU_EXP_HOLDOFF; 36 module_param(exp_holdoff, ulong, 0444); 37 38 /* Overflow-check frequency. N bits roughly says every 2**N grace periods. */ 39 static ulong counter_wrap_check = (ULONG_MAX >> 2); 40 module_param(counter_wrap_check, ulong, 0444); 41 42 /* 43 * Control conversion to SRCU_SIZE_BIG: 44 * 0: Don't convert at all. 45 * 1: Convert at init_srcu_struct() time. 46 * 2: Convert when rcutorture invokes srcu_torture_stats_print(). 47 * 3: Decide at boot time based on system shape (default). 48 * 0x1x: Convert when excessive contention encountered. 49 */ 50 #define SRCU_SIZING_NONE 0 51 #define SRCU_SIZING_INIT 1 52 #define SRCU_SIZING_TORTURE 2 53 #define SRCU_SIZING_AUTO 3 54 #define SRCU_SIZING_CONTEND 0x10 55 #define SRCU_SIZING_IS(x) ((convert_to_big & ~SRCU_SIZING_CONTEND) == x) 56 #define SRCU_SIZING_IS_NONE() (SRCU_SIZING_IS(SRCU_SIZING_NONE)) 57 #define SRCU_SIZING_IS_INIT() (SRCU_SIZING_IS(SRCU_SIZING_INIT)) 58 #define SRCU_SIZING_IS_TORTURE() (SRCU_SIZING_IS(SRCU_SIZING_TORTURE)) 59 #define SRCU_SIZING_IS_CONTEND() (convert_to_big & SRCU_SIZING_CONTEND) 60 static int convert_to_big = SRCU_SIZING_AUTO; 61 module_param(convert_to_big, int, 0444); 62 63 /* Number of CPUs to trigger init_srcu_struct()-time transition to big. */ 64 static int big_cpu_lim __read_mostly = 128; 65 module_param(big_cpu_lim, int, 0444); 66 67 /* Contention events per jiffy to initiate transition to big. */ 68 static int small_contention_lim __read_mostly = 100; 69 module_param(small_contention_lim, int, 0444); 70 71 /* Early-boot callback-management, so early that no lock is required! */ 72 static LIST_HEAD(srcu_boot_list); 73 static bool __read_mostly srcu_init_done; 74 75 static void srcu_invoke_callbacks(struct work_struct *work); 76 static void srcu_reschedule(struct srcu_struct *ssp, unsigned long delay); 77 static void process_srcu(struct work_struct *work); 78 static void srcu_delay_timer(struct timer_list *t); 79 80 /* Wrappers for lock acquisition and release, see raw_spin_lock_rcu_node(). */ 81 #define spin_lock_rcu_node(p) \ 82 do { \ 83 spin_lock(&ACCESS_PRIVATE(p, lock)); \ 84 smp_mb__after_unlock_lock(); \ 85 } while (0) 86 87 #define spin_unlock_rcu_node(p) spin_unlock(&ACCESS_PRIVATE(p, lock)) 88 89 #define spin_lock_irq_rcu_node(p) \ 90 do { \ 91 spin_lock_irq(&ACCESS_PRIVATE(p, lock)); \ 92 smp_mb__after_unlock_lock(); \ 93 } while (0) 94 95 #define spin_unlock_irq_rcu_node(p) \ 96 spin_unlock_irq(&ACCESS_PRIVATE(p, lock)) 97 98 #define spin_lock_irqsave_rcu_node(p, flags) \ 99 do { \ 100 spin_lock_irqsave(&ACCESS_PRIVATE(p, lock), flags); \ 101 smp_mb__after_unlock_lock(); \ 102 } while (0) 103 104 #define spin_trylock_irqsave_rcu_node(p, flags) \ 105 ({ \ 106 bool ___locked = spin_trylock_irqsave(&ACCESS_PRIVATE(p, lock), flags); \ 107 \ 108 if (___locked) \ 109 smp_mb__after_unlock_lock(); \ 110 ___locked; \ 111 }) 112 113 #define spin_unlock_irqrestore_rcu_node(p, flags) \ 114 spin_unlock_irqrestore(&ACCESS_PRIVATE(p, lock), flags) \ 115 116 /* 117 * Initialize SRCU per-CPU data. Note that statically allocated 118 * srcu_struct structures might already have srcu_read_lock() and 119 * srcu_read_unlock() running against them. So if the is_static parameter 120 * is set, don't initialize ->srcu_lock_count[] and ->srcu_unlock_count[]. 121 */ 122 static void init_srcu_struct_data(struct srcu_struct *ssp) 123 { 124 int cpu; 125 struct srcu_data *sdp; 126 127 /* 128 * Initialize the per-CPU srcu_data array, which feeds into the 129 * leaves of the srcu_node tree. 130 */ 131 WARN_ON_ONCE(ARRAY_SIZE(sdp->srcu_lock_count) != 132 ARRAY_SIZE(sdp->srcu_unlock_count)); 133 for_each_possible_cpu(cpu) { 134 sdp = per_cpu_ptr(ssp->sda, cpu); 135 spin_lock_init(&ACCESS_PRIVATE(sdp, lock)); 136 rcu_segcblist_init(&sdp->srcu_cblist); 137 sdp->srcu_cblist_invoking = false; 138 sdp->srcu_gp_seq_needed = ssp->srcu_gp_seq; 139 sdp->srcu_gp_seq_needed_exp = ssp->srcu_gp_seq; 140 sdp->mynode = NULL; 141 sdp->cpu = cpu; 142 INIT_WORK(&sdp->work, srcu_invoke_callbacks); 143 timer_setup(&sdp->delay_work, srcu_delay_timer, 0); 144 sdp->ssp = ssp; 145 } 146 } 147 148 /* Invalid seq state, used during snp node initialization */ 149 #define SRCU_SNP_INIT_SEQ 0x2 150 151 /* 152 * Check whether sequence number corresponding to snp node, 153 * is invalid. 154 */ 155 static inline bool srcu_invl_snp_seq(unsigned long s) 156 { 157 return s == SRCU_SNP_INIT_SEQ; 158 } 159 160 /* 161 * Allocated and initialize SRCU combining tree. Returns @true if 162 * allocation succeeded and @false otherwise. 163 */ 164 static bool init_srcu_struct_nodes(struct srcu_struct *ssp, gfp_t gfp_flags) 165 { 166 int cpu; 167 int i; 168 int level = 0; 169 int levelspread[RCU_NUM_LVLS]; 170 struct srcu_data *sdp; 171 struct srcu_node *snp; 172 struct srcu_node *snp_first; 173 174 /* Initialize geometry if it has not already been initialized. */ 175 rcu_init_geometry(); 176 ssp->node = kcalloc(rcu_num_nodes, sizeof(*ssp->node), gfp_flags); 177 if (!ssp->node) 178 return false; 179 180 /* Work out the overall tree geometry. */ 181 ssp->level[0] = &ssp->node[0]; 182 for (i = 1; i < rcu_num_lvls; i++) 183 ssp->level[i] = ssp->level[i - 1] + num_rcu_lvl[i - 1]; 184 rcu_init_levelspread(levelspread, num_rcu_lvl); 185 186 /* Each pass through this loop initializes one srcu_node structure. */ 187 srcu_for_each_node_breadth_first(ssp, snp) { 188 spin_lock_init(&ACCESS_PRIVATE(snp, lock)); 189 WARN_ON_ONCE(ARRAY_SIZE(snp->srcu_have_cbs) != 190 ARRAY_SIZE(snp->srcu_data_have_cbs)); 191 for (i = 0; i < ARRAY_SIZE(snp->srcu_have_cbs); i++) { 192 snp->srcu_have_cbs[i] = SRCU_SNP_INIT_SEQ; 193 snp->srcu_data_have_cbs[i] = 0; 194 } 195 snp->srcu_gp_seq_needed_exp = SRCU_SNP_INIT_SEQ; 196 snp->grplo = -1; 197 snp->grphi = -1; 198 if (snp == &ssp->node[0]) { 199 /* Root node, special case. */ 200 snp->srcu_parent = NULL; 201 continue; 202 } 203 204 /* Non-root node. */ 205 if (snp == ssp->level[level + 1]) 206 level++; 207 snp->srcu_parent = ssp->level[level - 1] + 208 (snp - ssp->level[level]) / 209 levelspread[level - 1]; 210 } 211 212 /* 213 * Initialize the per-CPU srcu_data array, which feeds into the 214 * leaves of the srcu_node tree. 215 */ 216 level = rcu_num_lvls - 1; 217 snp_first = ssp->level[level]; 218 for_each_possible_cpu(cpu) { 219 sdp = per_cpu_ptr(ssp->sda, cpu); 220 sdp->mynode = &snp_first[cpu / levelspread[level]]; 221 for (snp = sdp->mynode; snp != NULL; snp = snp->srcu_parent) { 222 if (snp->grplo < 0) 223 snp->grplo = cpu; 224 snp->grphi = cpu; 225 } 226 sdp->grpmask = 1 << (cpu - sdp->mynode->grplo); 227 } 228 smp_store_release(&ssp->srcu_size_state, SRCU_SIZE_WAIT_BARRIER); 229 return true; 230 } 231 232 /* 233 * Initialize non-compile-time initialized fields, including the 234 * associated srcu_node and srcu_data structures. The is_static parameter 235 * tells us that ->sda has already been wired up to srcu_data. 236 */ 237 static int init_srcu_struct_fields(struct srcu_struct *ssp, bool is_static) 238 { 239 ssp->srcu_size_state = SRCU_SIZE_SMALL; 240 ssp->node = NULL; 241 mutex_init(&ssp->srcu_cb_mutex); 242 mutex_init(&ssp->srcu_gp_mutex); 243 ssp->srcu_idx = 0; 244 ssp->srcu_gp_seq = 0; 245 ssp->srcu_barrier_seq = 0; 246 mutex_init(&ssp->srcu_barrier_mutex); 247 atomic_set(&ssp->srcu_barrier_cpu_cnt, 0); 248 INIT_DELAYED_WORK(&ssp->work, process_srcu); 249 ssp->sda_is_static = is_static; 250 if (!is_static) 251 ssp->sda = alloc_percpu(struct srcu_data); 252 if (!ssp->sda) 253 return -ENOMEM; 254 init_srcu_struct_data(ssp); 255 ssp->srcu_gp_seq_needed_exp = 0; 256 ssp->srcu_last_gp_end = ktime_get_mono_fast_ns(); 257 if (READ_ONCE(ssp->srcu_size_state) == SRCU_SIZE_SMALL && SRCU_SIZING_IS_INIT()) { 258 if (!init_srcu_struct_nodes(ssp, GFP_ATOMIC)) { 259 if (!ssp->sda_is_static) { 260 free_percpu(ssp->sda); 261 ssp->sda = NULL; 262 return -ENOMEM; 263 } 264 } else { 265 WRITE_ONCE(ssp->srcu_size_state, SRCU_SIZE_BIG); 266 } 267 } 268 smp_store_release(&ssp->srcu_gp_seq_needed, 0); /* Init done. */ 269 return 0; 270 } 271 272 #ifdef CONFIG_DEBUG_LOCK_ALLOC 273 274 int __init_srcu_struct(struct srcu_struct *ssp, const char *name, 275 struct lock_class_key *key) 276 { 277 /* Don't re-initialize a lock while it is held. */ 278 debug_check_no_locks_freed((void *)ssp, sizeof(*ssp)); 279 lockdep_init_map(&ssp->dep_map, name, key, 0); 280 spin_lock_init(&ACCESS_PRIVATE(ssp, lock)); 281 return init_srcu_struct_fields(ssp, false); 282 } 283 EXPORT_SYMBOL_GPL(__init_srcu_struct); 284 285 #else /* #ifdef CONFIG_DEBUG_LOCK_ALLOC */ 286 287 /** 288 * init_srcu_struct - initialize a sleep-RCU structure 289 * @ssp: structure to initialize. 290 * 291 * Must invoke this on a given srcu_struct before passing that srcu_struct 292 * to any other function. Each srcu_struct represents a separate domain 293 * of SRCU protection. 294 */ 295 int init_srcu_struct(struct srcu_struct *ssp) 296 { 297 spin_lock_init(&ACCESS_PRIVATE(ssp, lock)); 298 return init_srcu_struct_fields(ssp, false); 299 } 300 EXPORT_SYMBOL_GPL(init_srcu_struct); 301 302 #endif /* #else #ifdef CONFIG_DEBUG_LOCK_ALLOC */ 303 304 /* 305 * Initiate a transition to SRCU_SIZE_BIG with lock held. 306 */ 307 static void __srcu_transition_to_big(struct srcu_struct *ssp) 308 { 309 lockdep_assert_held(&ACCESS_PRIVATE(ssp, lock)); 310 smp_store_release(&ssp->srcu_size_state, SRCU_SIZE_ALLOC); 311 } 312 313 /* 314 * Initiate an idempotent transition to SRCU_SIZE_BIG. 315 */ 316 static void srcu_transition_to_big(struct srcu_struct *ssp) 317 { 318 unsigned long flags; 319 320 /* Double-checked locking on ->srcu_size-state. */ 321 if (smp_load_acquire(&ssp->srcu_size_state) != SRCU_SIZE_SMALL) 322 return; 323 spin_lock_irqsave_rcu_node(ssp, flags); 324 if (smp_load_acquire(&ssp->srcu_size_state) != SRCU_SIZE_SMALL) { 325 spin_unlock_irqrestore_rcu_node(ssp, flags); 326 return; 327 } 328 __srcu_transition_to_big(ssp); 329 spin_unlock_irqrestore_rcu_node(ssp, flags); 330 } 331 332 /* 333 * Check to see if the just-encountered contention event justifies 334 * a transition to SRCU_SIZE_BIG. 335 */ 336 static void spin_lock_irqsave_check_contention(struct srcu_struct *ssp) 337 { 338 unsigned long j; 339 340 if (!SRCU_SIZING_IS_CONTEND() || ssp->srcu_size_state) 341 return; 342 j = jiffies; 343 if (ssp->srcu_size_jiffies != j) { 344 ssp->srcu_size_jiffies = j; 345 ssp->srcu_n_lock_retries = 0; 346 } 347 if (++ssp->srcu_n_lock_retries <= small_contention_lim) 348 return; 349 __srcu_transition_to_big(ssp); 350 } 351 352 /* 353 * Acquire the specified srcu_data structure's ->lock, but check for 354 * excessive contention, which results in initiation of a transition 355 * to SRCU_SIZE_BIG. But only if the srcutree.convert_to_big module 356 * parameter permits this. 357 */ 358 static void spin_lock_irqsave_sdp_contention(struct srcu_data *sdp, unsigned long *flags) 359 { 360 struct srcu_struct *ssp = sdp->ssp; 361 362 if (spin_trylock_irqsave_rcu_node(sdp, *flags)) 363 return; 364 spin_lock_irqsave_rcu_node(ssp, *flags); 365 spin_lock_irqsave_check_contention(ssp); 366 spin_unlock_irqrestore_rcu_node(ssp, *flags); 367 spin_lock_irqsave_rcu_node(sdp, *flags); 368 } 369 370 /* 371 * Acquire the specified srcu_struct structure's ->lock, but check for 372 * excessive contention, which results in initiation of a transition 373 * to SRCU_SIZE_BIG. But only if the srcutree.convert_to_big module 374 * parameter permits this. 375 */ 376 static void spin_lock_irqsave_ssp_contention(struct srcu_struct *ssp, unsigned long *flags) 377 { 378 if (spin_trylock_irqsave_rcu_node(ssp, *flags)) 379 return; 380 spin_lock_irqsave_rcu_node(ssp, *flags); 381 spin_lock_irqsave_check_contention(ssp); 382 } 383 384 /* 385 * First-use initialization of statically allocated srcu_struct 386 * structure. Wiring up the combining tree is more than can be 387 * done with compile-time initialization, so this check is added 388 * to each update-side SRCU primitive. Use ssp->lock, which -is- 389 * compile-time initialized, to resolve races involving multiple 390 * CPUs trying to garner first-use privileges. 391 */ 392 static void check_init_srcu_struct(struct srcu_struct *ssp) 393 { 394 unsigned long flags; 395 396 /* The smp_load_acquire() pairs with the smp_store_release(). */ 397 if (!rcu_seq_state(smp_load_acquire(&ssp->srcu_gp_seq_needed))) /*^^^*/ 398 return; /* Already initialized. */ 399 spin_lock_irqsave_rcu_node(ssp, flags); 400 if (!rcu_seq_state(ssp->srcu_gp_seq_needed)) { 401 spin_unlock_irqrestore_rcu_node(ssp, flags); 402 return; 403 } 404 init_srcu_struct_fields(ssp, true); 405 spin_unlock_irqrestore_rcu_node(ssp, flags); 406 } 407 408 /* 409 * Returns approximate total of the readers' ->srcu_lock_count[] values 410 * for the rank of per-CPU counters specified by idx. 411 */ 412 static unsigned long srcu_readers_lock_idx(struct srcu_struct *ssp, int idx) 413 { 414 int cpu; 415 unsigned long sum = 0; 416 417 for_each_possible_cpu(cpu) { 418 struct srcu_data *cpuc = per_cpu_ptr(ssp->sda, cpu); 419 420 sum += atomic_long_read(&cpuc->srcu_lock_count[idx]); 421 } 422 return sum; 423 } 424 425 /* 426 * Returns approximate total of the readers' ->srcu_unlock_count[] values 427 * for the rank of per-CPU counters specified by idx. 428 */ 429 static unsigned long srcu_readers_unlock_idx(struct srcu_struct *ssp, int idx) 430 { 431 int cpu; 432 unsigned long mask = 0; 433 unsigned long sum = 0; 434 435 for_each_possible_cpu(cpu) { 436 struct srcu_data *cpuc = per_cpu_ptr(ssp->sda, cpu); 437 438 sum += atomic_long_read(&cpuc->srcu_unlock_count[idx]); 439 if (IS_ENABLED(CONFIG_PROVE_RCU)) 440 mask = mask | READ_ONCE(cpuc->srcu_nmi_safety); 441 } 442 WARN_ONCE(IS_ENABLED(CONFIG_PROVE_RCU) && (mask & (mask >> 1)), 443 "Mixed NMI-safe readers for srcu_struct at %ps.\n", ssp); 444 return sum; 445 } 446 447 /* 448 * Return true if the number of pre-existing readers is determined to 449 * be zero. 450 */ 451 static bool srcu_readers_active_idx_check(struct srcu_struct *ssp, int idx) 452 { 453 unsigned long unlocks; 454 455 unlocks = srcu_readers_unlock_idx(ssp, idx); 456 457 /* 458 * Make sure that a lock is always counted if the corresponding 459 * unlock is counted. Needs to be a smp_mb() as the read side may 460 * contain a read from a variable that is written to before the 461 * synchronize_srcu() in the write side. In this case smp_mb()s 462 * A and B act like the store buffering pattern. 463 * 464 * This smp_mb() also pairs with smp_mb() C to prevent accesses 465 * after the synchronize_srcu() from being executed before the 466 * grace period ends. 467 */ 468 smp_mb(); /* A */ 469 470 /* 471 * If the locks are the same as the unlocks, then there must have 472 * been no readers on this index at some point in this function. 473 * But there might be more readers, as a task might have read 474 * the current ->srcu_idx but not yet have incremented its CPU's 475 * ->srcu_lock_count[idx] counter. In fact, it is possible 476 * that most of the tasks have been preempted between fetching 477 * ->srcu_idx and incrementing ->srcu_lock_count[idx]. And there 478 * could be almost (ULONG_MAX / sizeof(struct task_struct)) tasks 479 * in a system whose address space was fully populated with memory. 480 * Call this quantity Nt. 481 * 482 * So suppose that the updater is preempted at this point in the 483 * code for a long time. That now-preempted updater has already 484 * flipped ->srcu_idx (possibly during the preceding grace period), 485 * done an smp_mb() (again, possibly during the preceding grace 486 * period), and summed up the ->srcu_unlock_count[idx] counters. 487 * How many times can a given one of the aforementioned Nt tasks 488 * increment the old ->srcu_idx value's ->srcu_lock_count[idx] 489 * counter, in the absence of nesting? 490 * 491 * It can clearly do so once, given that it has already fetched 492 * the old value of ->srcu_idx and is just about to use that value 493 * to index its increment of ->srcu_lock_count[idx]. But as soon as 494 * it leaves that SRCU read-side critical section, it will increment 495 * ->srcu_unlock_count[idx], which must follow the updater's above 496 * read from that same value. Thus, as soon the reading task does 497 * an smp_mb() and a later fetch from ->srcu_idx, that task will be 498 * guaranteed to get the new index. Except that the increment of 499 * ->srcu_unlock_count[idx] in __srcu_read_unlock() is after the 500 * smp_mb(), and the fetch from ->srcu_idx in __srcu_read_lock() 501 * is before the smp_mb(). Thus, that task might not see the new 502 * value of ->srcu_idx until the -second- __srcu_read_lock(), 503 * which in turn means that this task might well increment 504 * ->srcu_lock_count[idx] for the old value of ->srcu_idx twice, 505 * not just once. 506 * 507 * However, it is important to note that a given smp_mb() takes 508 * effect not just for the task executing it, but also for any 509 * later task running on that same CPU. 510 * 511 * That is, there can be almost Nt + Nc further increments of 512 * ->srcu_lock_count[idx] for the old index, where Nc is the number 513 * of CPUs. But this is OK because the size of the task_struct 514 * structure limits the value of Nt and current systems limit Nc 515 * to a few thousand. 516 * 517 * OK, but what about nesting? This does impose a limit on 518 * nesting of half of the size of the task_struct structure 519 * (measured in bytes), which should be sufficient. A late 2022 520 * TREE01 rcutorture run reported this size to be no less than 521 * 9408 bytes, allowing up to 4704 levels of nesting, which is 522 * comfortably beyond excessive. Especially on 64-bit systems, 523 * which are unlikely to be configured with an address space fully 524 * populated with memory, at least not anytime soon. 525 */ 526 return srcu_readers_lock_idx(ssp, idx) == unlocks; 527 } 528 529 /** 530 * srcu_readers_active - returns true if there are readers. and false 531 * otherwise 532 * @ssp: which srcu_struct to count active readers (holding srcu_read_lock). 533 * 534 * Note that this is not an atomic primitive, and can therefore suffer 535 * severe errors when invoked on an active srcu_struct. That said, it 536 * can be useful as an error check at cleanup time. 537 */ 538 static bool srcu_readers_active(struct srcu_struct *ssp) 539 { 540 int cpu; 541 unsigned long sum = 0; 542 543 for_each_possible_cpu(cpu) { 544 struct srcu_data *cpuc = per_cpu_ptr(ssp->sda, cpu); 545 546 sum += atomic_long_read(&cpuc->srcu_lock_count[0]); 547 sum += atomic_long_read(&cpuc->srcu_lock_count[1]); 548 sum -= atomic_long_read(&cpuc->srcu_unlock_count[0]); 549 sum -= atomic_long_read(&cpuc->srcu_unlock_count[1]); 550 } 551 return sum; 552 } 553 554 /* 555 * We use an adaptive strategy for synchronize_srcu() and especially for 556 * synchronize_srcu_expedited(). We spin for a fixed time period 557 * (defined below, boot time configurable) to allow SRCU readers to exit 558 * their read-side critical sections. If there are still some readers 559 * after one jiffy, we repeatedly block for one jiffy time periods. 560 * The blocking time is increased as the grace-period age increases, 561 * with max blocking time capped at 10 jiffies. 562 */ 563 #define SRCU_DEFAULT_RETRY_CHECK_DELAY 5 564 565 static ulong srcu_retry_check_delay = SRCU_DEFAULT_RETRY_CHECK_DELAY; 566 module_param(srcu_retry_check_delay, ulong, 0444); 567 568 #define SRCU_INTERVAL 1 // Base delay if no expedited GPs pending. 569 #define SRCU_MAX_INTERVAL 10 // Maximum incremental delay from slow readers. 570 571 #define SRCU_DEFAULT_MAX_NODELAY_PHASE_LO 3UL // Lowmark on default per-GP-phase 572 // no-delay instances. 573 #define SRCU_DEFAULT_MAX_NODELAY_PHASE_HI 1000UL // Highmark on default per-GP-phase 574 // no-delay instances. 575 576 #define SRCU_UL_CLAMP_LO(val, low) ((val) > (low) ? (val) : (low)) 577 #define SRCU_UL_CLAMP_HI(val, high) ((val) < (high) ? (val) : (high)) 578 #define SRCU_UL_CLAMP(val, low, high) SRCU_UL_CLAMP_HI(SRCU_UL_CLAMP_LO((val), (low)), (high)) 579 // per-GP-phase no-delay instances adjusted to allow non-sleeping poll upto 580 // one jiffies time duration. Mult by 2 is done to factor in the srcu_get_delay() 581 // called from process_srcu(). 582 #define SRCU_DEFAULT_MAX_NODELAY_PHASE_ADJUSTED \ 583 (2UL * USEC_PER_SEC / HZ / SRCU_DEFAULT_RETRY_CHECK_DELAY) 584 585 // Maximum per-GP-phase consecutive no-delay instances. 586 #define SRCU_DEFAULT_MAX_NODELAY_PHASE \ 587 SRCU_UL_CLAMP(SRCU_DEFAULT_MAX_NODELAY_PHASE_ADJUSTED, \ 588 SRCU_DEFAULT_MAX_NODELAY_PHASE_LO, \ 589 SRCU_DEFAULT_MAX_NODELAY_PHASE_HI) 590 591 static ulong srcu_max_nodelay_phase = SRCU_DEFAULT_MAX_NODELAY_PHASE; 592 module_param(srcu_max_nodelay_phase, ulong, 0444); 593 594 // Maximum consecutive no-delay instances. 595 #define SRCU_DEFAULT_MAX_NODELAY (SRCU_DEFAULT_MAX_NODELAY_PHASE > 100 ? \ 596 SRCU_DEFAULT_MAX_NODELAY_PHASE : 100) 597 598 static ulong srcu_max_nodelay = SRCU_DEFAULT_MAX_NODELAY; 599 module_param(srcu_max_nodelay, ulong, 0444); 600 601 /* 602 * Return grace-period delay, zero if there are expedited grace 603 * periods pending, SRCU_INTERVAL otherwise. 604 */ 605 static unsigned long srcu_get_delay(struct srcu_struct *ssp) 606 { 607 unsigned long gpstart; 608 unsigned long j; 609 unsigned long jbase = SRCU_INTERVAL; 610 611 if (ULONG_CMP_LT(READ_ONCE(ssp->srcu_gp_seq), READ_ONCE(ssp->srcu_gp_seq_needed_exp))) 612 jbase = 0; 613 if (rcu_seq_state(READ_ONCE(ssp->srcu_gp_seq))) { 614 j = jiffies - 1; 615 gpstart = READ_ONCE(ssp->srcu_gp_start); 616 if (time_after(j, gpstart)) 617 jbase += j - gpstart; 618 if (!jbase) { 619 WRITE_ONCE(ssp->srcu_n_exp_nodelay, READ_ONCE(ssp->srcu_n_exp_nodelay) + 1); 620 if (READ_ONCE(ssp->srcu_n_exp_nodelay) > srcu_max_nodelay_phase) 621 jbase = 1; 622 } 623 } 624 return jbase > SRCU_MAX_INTERVAL ? SRCU_MAX_INTERVAL : jbase; 625 } 626 627 /** 628 * cleanup_srcu_struct - deconstruct a sleep-RCU structure 629 * @ssp: structure to clean up. 630 * 631 * Must invoke this after you are finished using a given srcu_struct that 632 * was initialized via init_srcu_struct(), else you leak memory. 633 */ 634 void cleanup_srcu_struct(struct srcu_struct *ssp) 635 { 636 int cpu; 637 638 if (WARN_ON(!srcu_get_delay(ssp))) 639 return; /* Just leak it! */ 640 if (WARN_ON(srcu_readers_active(ssp))) 641 return; /* Just leak it! */ 642 flush_delayed_work(&ssp->work); 643 for_each_possible_cpu(cpu) { 644 struct srcu_data *sdp = per_cpu_ptr(ssp->sda, cpu); 645 646 del_timer_sync(&sdp->delay_work); 647 flush_work(&sdp->work); 648 if (WARN_ON(rcu_segcblist_n_cbs(&sdp->srcu_cblist))) 649 return; /* Forgot srcu_barrier(), so just leak it! */ 650 } 651 if (WARN_ON(rcu_seq_state(READ_ONCE(ssp->srcu_gp_seq)) != SRCU_STATE_IDLE) || 652 WARN_ON(rcu_seq_current(&ssp->srcu_gp_seq) != ssp->srcu_gp_seq_needed) || 653 WARN_ON(srcu_readers_active(ssp))) { 654 pr_info("%s: Active srcu_struct %p read state: %d gp state: %lu/%lu\n", 655 __func__, ssp, rcu_seq_state(READ_ONCE(ssp->srcu_gp_seq)), 656 rcu_seq_current(&ssp->srcu_gp_seq), ssp->srcu_gp_seq_needed); 657 return; /* Caller forgot to stop doing call_srcu()? */ 658 } 659 if (!ssp->sda_is_static) { 660 free_percpu(ssp->sda); 661 ssp->sda = NULL; 662 } 663 kfree(ssp->node); 664 ssp->node = NULL; 665 ssp->srcu_size_state = SRCU_SIZE_SMALL; 666 } 667 EXPORT_SYMBOL_GPL(cleanup_srcu_struct); 668 669 #ifdef CONFIG_PROVE_RCU 670 /* 671 * Check for consistent NMI safety. 672 */ 673 void srcu_check_nmi_safety(struct srcu_struct *ssp, bool nmi_safe) 674 { 675 int nmi_safe_mask = 1 << nmi_safe; 676 int old_nmi_safe_mask; 677 struct srcu_data *sdp; 678 679 /* NMI-unsafe use in NMI is a bad sign */ 680 WARN_ON_ONCE(!nmi_safe && in_nmi()); 681 sdp = raw_cpu_ptr(ssp->sda); 682 old_nmi_safe_mask = READ_ONCE(sdp->srcu_nmi_safety); 683 if (!old_nmi_safe_mask) { 684 WRITE_ONCE(sdp->srcu_nmi_safety, nmi_safe_mask); 685 return; 686 } 687 WARN_ONCE(old_nmi_safe_mask != nmi_safe_mask, "CPU %d old state %d new state %d\n", sdp->cpu, old_nmi_safe_mask, nmi_safe_mask); 688 } 689 EXPORT_SYMBOL_GPL(srcu_check_nmi_safety); 690 #endif /* CONFIG_PROVE_RCU */ 691 692 /* 693 * Counts the new reader in the appropriate per-CPU element of the 694 * srcu_struct. 695 * Returns an index that must be passed to the matching srcu_read_unlock(). 696 */ 697 int __srcu_read_lock(struct srcu_struct *ssp) 698 { 699 int idx; 700 701 idx = READ_ONCE(ssp->srcu_idx) & 0x1; 702 this_cpu_inc(ssp->sda->srcu_lock_count[idx].counter); 703 smp_mb(); /* B */ /* Avoid leaking the critical section. */ 704 return idx; 705 } 706 EXPORT_SYMBOL_GPL(__srcu_read_lock); 707 708 /* 709 * Removes the count for the old reader from the appropriate per-CPU 710 * element of the srcu_struct. Note that this may well be a different 711 * CPU than that which was incremented by the corresponding srcu_read_lock(). 712 */ 713 void __srcu_read_unlock(struct srcu_struct *ssp, int idx) 714 { 715 smp_mb(); /* C */ /* Avoid leaking the critical section. */ 716 this_cpu_inc(ssp->sda->srcu_unlock_count[idx].counter); 717 } 718 EXPORT_SYMBOL_GPL(__srcu_read_unlock); 719 720 #ifdef CONFIG_NEED_SRCU_NMI_SAFE 721 722 /* 723 * Counts the new reader in the appropriate per-CPU element of the 724 * srcu_struct, but in an NMI-safe manner using RMW atomics. 725 * Returns an index that must be passed to the matching srcu_read_unlock(). 726 */ 727 int __srcu_read_lock_nmisafe(struct srcu_struct *ssp) 728 { 729 int idx; 730 struct srcu_data *sdp = raw_cpu_ptr(ssp->sda); 731 732 idx = READ_ONCE(ssp->srcu_idx) & 0x1; 733 atomic_long_inc(&sdp->srcu_lock_count[idx]); 734 smp_mb__after_atomic(); /* B */ /* Avoid leaking the critical section. */ 735 return idx; 736 } 737 EXPORT_SYMBOL_GPL(__srcu_read_lock_nmisafe); 738 739 /* 740 * Removes the count for the old reader from the appropriate per-CPU 741 * element of the srcu_struct. Note that this may well be a different 742 * CPU than that which was incremented by the corresponding srcu_read_lock(). 743 */ 744 void __srcu_read_unlock_nmisafe(struct srcu_struct *ssp, int idx) 745 { 746 struct srcu_data *sdp = raw_cpu_ptr(ssp->sda); 747 748 smp_mb__before_atomic(); /* C */ /* Avoid leaking the critical section. */ 749 atomic_long_inc(&sdp->srcu_unlock_count[idx]); 750 } 751 EXPORT_SYMBOL_GPL(__srcu_read_unlock_nmisafe); 752 753 #endif // CONFIG_NEED_SRCU_NMI_SAFE 754 755 /* 756 * Start an SRCU grace period. 757 */ 758 static void srcu_gp_start(struct srcu_struct *ssp) 759 { 760 struct srcu_data *sdp; 761 int state; 762 763 if (smp_load_acquire(&ssp->srcu_size_state) < SRCU_SIZE_WAIT_BARRIER) 764 sdp = per_cpu_ptr(ssp->sda, get_boot_cpu_id()); 765 else 766 sdp = this_cpu_ptr(ssp->sda); 767 lockdep_assert_held(&ACCESS_PRIVATE(ssp, lock)); 768 WARN_ON_ONCE(ULONG_CMP_GE(ssp->srcu_gp_seq, ssp->srcu_gp_seq_needed)); 769 spin_lock_rcu_node(sdp); /* Interrupts already disabled. */ 770 rcu_segcblist_advance(&sdp->srcu_cblist, 771 rcu_seq_current(&ssp->srcu_gp_seq)); 772 (void)rcu_segcblist_accelerate(&sdp->srcu_cblist, 773 rcu_seq_snap(&ssp->srcu_gp_seq)); 774 spin_unlock_rcu_node(sdp); /* Interrupts remain disabled. */ 775 WRITE_ONCE(ssp->srcu_gp_start, jiffies); 776 WRITE_ONCE(ssp->srcu_n_exp_nodelay, 0); 777 smp_mb(); /* Order prior store to ->srcu_gp_seq_needed vs. GP start. */ 778 rcu_seq_start(&ssp->srcu_gp_seq); 779 state = rcu_seq_state(ssp->srcu_gp_seq); 780 WARN_ON_ONCE(state != SRCU_STATE_SCAN1); 781 } 782 783 784 static void srcu_delay_timer(struct timer_list *t) 785 { 786 struct srcu_data *sdp = container_of(t, struct srcu_data, delay_work); 787 788 queue_work_on(sdp->cpu, rcu_gp_wq, &sdp->work); 789 } 790 791 static void srcu_queue_delayed_work_on(struct srcu_data *sdp, 792 unsigned long delay) 793 { 794 if (!delay) { 795 queue_work_on(sdp->cpu, rcu_gp_wq, &sdp->work); 796 return; 797 } 798 799 timer_reduce(&sdp->delay_work, jiffies + delay); 800 } 801 802 /* 803 * Schedule callback invocation for the specified srcu_data structure, 804 * if possible, on the corresponding CPU. 805 */ 806 static void srcu_schedule_cbs_sdp(struct srcu_data *sdp, unsigned long delay) 807 { 808 srcu_queue_delayed_work_on(sdp, delay); 809 } 810 811 /* 812 * Schedule callback invocation for all srcu_data structures associated 813 * with the specified srcu_node structure that have callbacks for the 814 * just-completed grace period, the one corresponding to idx. If possible, 815 * schedule this invocation on the corresponding CPUs. 816 */ 817 static void srcu_schedule_cbs_snp(struct srcu_struct *ssp, struct srcu_node *snp, 818 unsigned long mask, unsigned long delay) 819 { 820 int cpu; 821 822 for (cpu = snp->grplo; cpu <= snp->grphi; cpu++) { 823 if (!(mask & (1 << (cpu - snp->grplo)))) 824 continue; 825 srcu_schedule_cbs_sdp(per_cpu_ptr(ssp->sda, cpu), delay); 826 } 827 } 828 829 /* 830 * Note the end of an SRCU grace period. Initiates callback invocation 831 * and starts a new grace period if needed. 832 * 833 * The ->srcu_cb_mutex acquisition does not protect any data, but 834 * instead prevents more than one grace period from starting while we 835 * are initiating callback invocation. This allows the ->srcu_have_cbs[] 836 * array to have a finite number of elements. 837 */ 838 static void srcu_gp_end(struct srcu_struct *ssp) 839 { 840 unsigned long cbdelay = 1; 841 bool cbs; 842 bool last_lvl; 843 int cpu; 844 unsigned long flags; 845 unsigned long gpseq; 846 int idx; 847 unsigned long mask; 848 struct srcu_data *sdp; 849 unsigned long sgsne; 850 struct srcu_node *snp; 851 int ss_state; 852 853 /* Prevent more than one additional grace period. */ 854 mutex_lock(&ssp->srcu_cb_mutex); 855 856 /* End the current grace period. */ 857 spin_lock_irq_rcu_node(ssp); 858 idx = rcu_seq_state(ssp->srcu_gp_seq); 859 WARN_ON_ONCE(idx != SRCU_STATE_SCAN2); 860 if (ULONG_CMP_LT(READ_ONCE(ssp->srcu_gp_seq), READ_ONCE(ssp->srcu_gp_seq_needed_exp))) 861 cbdelay = 0; 862 863 WRITE_ONCE(ssp->srcu_last_gp_end, ktime_get_mono_fast_ns()); 864 rcu_seq_end(&ssp->srcu_gp_seq); 865 gpseq = rcu_seq_current(&ssp->srcu_gp_seq); 866 if (ULONG_CMP_LT(ssp->srcu_gp_seq_needed_exp, gpseq)) 867 WRITE_ONCE(ssp->srcu_gp_seq_needed_exp, gpseq); 868 spin_unlock_irq_rcu_node(ssp); 869 mutex_unlock(&ssp->srcu_gp_mutex); 870 /* A new grace period can start at this point. But only one. */ 871 872 /* Initiate callback invocation as needed. */ 873 ss_state = smp_load_acquire(&ssp->srcu_size_state); 874 if (ss_state < SRCU_SIZE_WAIT_BARRIER) { 875 srcu_schedule_cbs_sdp(per_cpu_ptr(ssp->sda, get_boot_cpu_id()), 876 cbdelay); 877 } else { 878 idx = rcu_seq_ctr(gpseq) % ARRAY_SIZE(snp->srcu_have_cbs); 879 srcu_for_each_node_breadth_first(ssp, snp) { 880 spin_lock_irq_rcu_node(snp); 881 cbs = false; 882 last_lvl = snp >= ssp->level[rcu_num_lvls - 1]; 883 if (last_lvl) 884 cbs = ss_state < SRCU_SIZE_BIG || snp->srcu_have_cbs[idx] == gpseq; 885 snp->srcu_have_cbs[idx] = gpseq; 886 rcu_seq_set_state(&snp->srcu_have_cbs[idx], 1); 887 sgsne = snp->srcu_gp_seq_needed_exp; 888 if (srcu_invl_snp_seq(sgsne) || ULONG_CMP_LT(sgsne, gpseq)) 889 WRITE_ONCE(snp->srcu_gp_seq_needed_exp, gpseq); 890 if (ss_state < SRCU_SIZE_BIG) 891 mask = ~0; 892 else 893 mask = snp->srcu_data_have_cbs[idx]; 894 snp->srcu_data_have_cbs[idx] = 0; 895 spin_unlock_irq_rcu_node(snp); 896 if (cbs) 897 srcu_schedule_cbs_snp(ssp, snp, mask, cbdelay); 898 } 899 } 900 901 /* Occasionally prevent srcu_data counter wrap. */ 902 if (!(gpseq & counter_wrap_check)) 903 for_each_possible_cpu(cpu) { 904 sdp = per_cpu_ptr(ssp->sda, cpu); 905 spin_lock_irqsave_rcu_node(sdp, flags); 906 if (ULONG_CMP_GE(gpseq, sdp->srcu_gp_seq_needed + 100)) 907 sdp->srcu_gp_seq_needed = gpseq; 908 if (ULONG_CMP_GE(gpseq, sdp->srcu_gp_seq_needed_exp + 100)) 909 sdp->srcu_gp_seq_needed_exp = gpseq; 910 spin_unlock_irqrestore_rcu_node(sdp, flags); 911 } 912 913 /* Callback initiation done, allow grace periods after next. */ 914 mutex_unlock(&ssp->srcu_cb_mutex); 915 916 /* Start a new grace period if needed. */ 917 spin_lock_irq_rcu_node(ssp); 918 gpseq = rcu_seq_current(&ssp->srcu_gp_seq); 919 if (!rcu_seq_state(gpseq) && 920 ULONG_CMP_LT(gpseq, ssp->srcu_gp_seq_needed)) { 921 srcu_gp_start(ssp); 922 spin_unlock_irq_rcu_node(ssp); 923 srcu_reschedule(ssp, 0); 924 } else { 925 spin_unlock_irq_rcu_node(ssp); 926 } 927 928 /* Transition to big if needed. */ 929 if (ss_state != SRCU_SIZE_SMALL && ss_state != SRCU_SIZE_BIG) { 930 if (ss_state == SRCU_SIZE_ALLOC) 931 init_srcu_struct_nodes(ssp, GFP_KERNEL); 932 else 933 smp_store_release(&ssp->srcu_size_state, ss_state + 1); 934 } 935 } 936 937 /* 938 * Funnel-locking scheme to scalably mediate many concurrent expedited 939 * grace-period requests. This function is invoked for the first known 940 * expedited request for a grace period that has already been requested, 941 * but without expediting. To start a completely new grace period, 942 * whether expedited or not, use srcu_funnel_gp_start() instead. 943 */ 944 static void srcu_funnel_exp_start(struct srcu_struct *ssp, struct srcu_node *snp, 945 unsigned long s) 946 { 947 unsigned long flags; 948 unsigned long sgsne; 949 950 if (snp) 951 for (; snp != NULL; snp = snp->srcu_parent) { 952 sgsne = READ_ONCE(snp->srcu_gp_seq_needed_exp); 953 if (WARN_ON_ONCE(rcu_seq_done(&ssp->srcu_gp_seq, s)) || 954 (!srcu_invl_snp_seq(sgsne) && ULONG_CMP_GE(sgsne, s))) 955 return; 956 spin_lock_irqsave_rcu_node(snp, flags); 957 sgsne = snp->srcu_gp_seq_needed_exp; 958 if (!srcu_invl_snp_seq(sgsne) && ULONG_CMP_GE(sgsne, s)) { 959 spin_unlock_irqrestore_rcu_node(snp, flags); 960 return; 961 } 962 WRITE_ONCE(snp->srcu_gp_seq_needed_exp, s); 963 spin_unlock_irqrestore_rcu_node(snp, flags); 964 } 965 spin_lock_irqsave_ssp_contention(ssp, &flags); 966 if (ULONG_CMP_LT(ssp->srcu_gp_seq_needed_exp, s)) 967 WRITE_ONCE(ssp->srcu_gp_seq_needed_exp, s); 968 spin_unlock_irqrestore_rcu_node(ssp, flags); 969 } 970 971 /* 972 * Funnel-locking scheme to scalably mediate many concurrent grace-period 973 * requests. The winner has to do the work of actually starting grace 974 * period s. Losers must either ensure that their desired grace-period 975 * number is recorded on at least their leaf srcu_node structure, or they 976 * must take steps to invoke their own callbacks. 977 * 978 * Note that this function also does the work of srcu_funnel_exp_start(), 979 * in some cases by directly invoking it. 980 * 981 * The srcu read lock should be hold around this function. And s is a seq snap 982 * after holding that lock. 983 */ 984 static void srcu_funnel_gp_start(struct srcu_struct *ssp, struct srcu_data *sdp, 985 unsigned long s, bool do_norm) 986 { 987 unsigned long flags; 988 int idx = rcu_seq_ctr(s) % ARRAY_SIZE(sdp->mynode->srcu_have_cbs); 989 unsigned long sgsne; 990 struct srcu_node *snp; 991 struct srcu_node *snp_leaf; 992 unsigned long snp_seq; 993 994 /* Ensure that snp node tree is fully initialized before traversing it */ 995 if (smp_load_acquire(&ssp->srcu_size_state) < SRCU_SIZE_WAIT_BARRIER) 996 snp_leaf = NULL; 997 else 998 snp_leaf = sdp->mynode; 999 1000 if (snp_leaf) 1001 /* Each pass through the loop does one level of the srcu_node tree. */ 1002 for (snp = snp_leaf; snp != NULL; snp = snp->srcu_parent) { 1003 if (WARN_ON_ONCE(rcu_seq_done(&ssp->srcu_gp_seq, s)) && snp != snp_leaf) 1004 return; /* GP already done and CBs recorded. */ 1005 spin_lock_irqsave_rcu_node(snp, flags); 1006 snp_seq = snp->srcu_have_cbs[idx]; 1007 if (!srcu_invl_snp_seq(snp_seq) && ULONG_CMP_GE(snp_seq, s)) { 1008 if (snp == snp_leaf && snp_seq == s) 1009 snp->srcu_data_have_cbs[idx] |= sdp->grpmask; 1010 spin_unlock_irqrestore_rcu_node(snp, flags); 1011 if (snp == snp_leaf && snp_seq != s) { 1012 srcu_schedule_cbs_sdp(sdp, do_norm ? SRCU_INTERVAL : 0); 1013 return; 1014 } 1015 if (!do_norm) 1016 srcu_funnel_exp_start(ssp, snp, s); 1017 return; 1018 } 1019 snp->srcu_have_cbs[idx] = s; 1020 if (snp == snp_leaf) 1021 snp->srcu_data_have_cbs[idx] |= sdp->grpmask; 1022 sgsne = snp->srcu_gp_seq_needed_exp; 1023 if (!do_norm && (srcu_invl_snp_seq(sgsne) || ULONG_CMP_LT(sgsne, s))) 1024 WRITE_ONCE(snp->srcu_gp_seq_needed_exp, s); 1025 spin_unlock_irqrestore_rcu_node(snp, flags); 1026 } 1027 1028 /* Top of tree, must ensure the grace period will be started. */ 1029 spin_lock_irqsave_ssp_contention(ssp, &flags); 1030 if (ULONG_CMP_LT(ssp->srcu_gp_seq_needed, s)) { 1031 /* 1032 * Record need for grace period s. Pair with load 1033 * acquire setting up for initialization. 1034 */ 1035 smp_store_release(&ssp->srcu_gp_seq_needed, s); /*^^^*/ 1036 } 1037 if (!do_norm && ULONG_CMP_LT(ssp->srcu_gp_seq_needed_exp, s)) 1038 WRITE_ONCE(ssp->srcu_gp_seq_needed_exp, s); 1039 1040 /* If grace period not already in progress, start it. */ 1041 if (!WARN_ON_ONCE(rcu_seq_done(&ssp->srcu_gp_seq, s)) && 1042 rcu_seq_state(ssp->srcu_gp_seq) == SRCU_STATE_IDLE) { 1043 WARN_ON_ONCE(ULONG_CMP_GE(ssp->srcu_gp_seq, ssp->srcu_gp_seq_needed)); 1044 srcu_gp_start(ssp); 1045 1046 // And how can that list_add() in the "else" clause 1047 // possibly be safe for concurrent execution? Well, 1048 // it isn't. And it does not have to be. After all, it 1049 // can only be executed during early boot when there is only 1050 // the one boot CPU running with interrupts still disabled. 1051 if (likely(srcu_init_done)) 1052 queue_delayed_work(rcu_gp_wq, &ssp->work, 1053 !!srcu_get_delay(ssp)); 1054 else if (list_empty(&ssp->work.work.entry)) 1055 list_add(&ssp->work.work.entry, &srcu_boot_list); 1056 } 1057 spin_unlock_irqrestore_rcu_node(ssp, flags); 1058 } 1059 1060 /* 1061 * Wait until all readers counted by array index idx complete, but 1062 * loop an additional time if there is an expedited grace period pending. 1063 * The caller must ensure that ->srcu_idx is not changed while checking. 1064 */ 1065 static bool try_check_zero(struct srcu_struct *ssp, int idx, int trycount) 1066 { 1067 unsigned long curdelay; 1068 1069 curdelay = !srcu_get_delay(ssp); 1070 1071 for (;;) { 1072 if (srcu_readers_active_idx_check(ssp, idx)) 1073 return true; 1074 if ((--trycount + curdelay) <= 0) 1075 return false; 1076 udelay(srcu_retry_check_delay); 1077 } 1078 } 1079 1080 /* 1081 * Increment the ->srcu_idx counter so that future SRCU readers will 1082 * use the other rank of the ->srcu_(un)lock_count[] arrays. This allows 1083 * us to wait for pre-existing readers in a starvation-free manner. 1084 */ 1085 static void srcu_flip(struct srcu_struct *ssp) 1086 { 1087 /* 1088 * Because the flip of ->srcu_idx is executed only if the 1089 * preceding call to srcu_readers_active_idx_check() found that 1090 * the ->srcu_unlock_count[] and ->srcu_lock_count[] sums matched 1091 * and because that summing uses atomic_long_read(), there is 1092 * ordering due to a control dependency between that summing and 1093 * the WRITE_ONCE() in this call to srcu_flip(). This ordering 1094 * ensures that if this updater saw a given reader's increment from 1095 * __srcu_read_lock(), that reader was using a value of ->srcu_idx 1096 * from before the previous call to srcu_flip(), which should be 1097 * quite rare. This ordering thus helps forward progress because 1098 * the grace period could otherwise be delayed by additional 1099 * calls to __srcu_read_lock() using that old (soon to be new) 1100 * value of ->srcu_idx. 1101 * 1102 * This sum-equality check and ordering also ensures that if 1103 * a given call to __srcu_read_lock() uses the new value of 1104 * ->srcu_idx, this updater's earlier scans cannot have seen 1105 * that reader's increments, which is all to the good, because 1106 * this grace period need not wait on that reader. After all, 1107 * if those earlier scans had seen that reader, there would have 1108 * been a sum mismatch and this code would not be reached. 1109 * 1110 * This means that the following smp_mb() is redundant, but 1111 * it stays until either (1) Compilers learn about this sort of 1112 * control dependency or (2) Some production workload running on 1113 * a production system is unduly delayed by this slowpath smp_mb(). 1114 */ 1115 smp_mb(); /* E */ /* Pairs with B and C. */ 1116 1117 WRITE_ONCE(ssp->srcu_idx, ssp->srcu_idx + 1); // Flip the counter. 1118 1119 /* 1120 * Ensure that if the updater misses an __srcu_read_unlock() 1121 * increment, that task's __srcu_read_lock() following its next 1122 * __srcu_read_lock() or __srcu_read_unlock() will see the above 1123 * counter update. Note that both this memory barrier and the 1124 * one in srcu_readers_active_idx_check() provide the guarantee 1125 * for __srcu_read_lock(). 1126 */ 1127 smp_mb(); /* D */ /* Pairs with C. */ 1128 } 1129 1130 /* 1131 * If SRCU is likely idle, return true, otherwise return false. 1132 * 1133 * Note that it is OK for several current from-idle requests for a new 1134 * grace period from idle to specify expediting because they will all end 1135 * up requesting the same grace period anyhow. So no loss. 1136 * 1137 * Note also that if any CPU (including the current one) is still invoking 1138 * callbacks, this function will nevertheless say "idle". This is not 1139 * ideal, but the overhead of checking all CPUs' callback lists is even 1140 * less ideal, especially on large systems. Furthermore, the wakeup 1141 * can happen before the callback is fully removed, so we have no choice 1142 * but to accept this type of error. 1143 * 1144 * This function is also subject to counter-wrap errors, but let's face 1145 * it, if this function was preempted for enough time for the counters 1146 * to wrap, it really doesn't matter whether or not we expedite the grace 1147 * period. The extra overhead of a needlessly expedited grace period is 1148 * negligible when amortized over that time period, and the extra latency 1149 * of a needlessly non-expedited grace period is similarly negligible. 1150 */ 1151 static bool srcu_might_be_idle(struct srcu_struct *ssp) 1152 { 1153 unsigned long curseq; 1154 unsigned long flags; 1155 struct srcu_data *sdp; 1156 unsigned long t; 1157 unsigned long tlast; 1158 1159 check_init_srcu_struct(ssp); 1160 /* If the local srcu_data structure has callbacks, not idle. */ 1161 sdp = raw_cpu_ptr(ssp->sda); 1162 spin_lock_irqsave_rcu_node(sdp, flags); 1163 if (rcu_segcblist_pend_cbs(&sdp->srcu_cblist)) { 1164 spin_unlock_irqrestore_rcu_node(sdp, flags); 1165 return false; /* Callbacks already present, so not idle. */ 1166 } 1167 spin_unlock_irqrestore_rcu_node(sdp, flags); 1168 1169 /* 1170 * No local callbacks, so probabilistically probe global state. 1171 * Exact information would require acquiring locks, which would 1172 * kill scalability, hence the probabilistic nature of the probe. 1173 */ 1174 1175 /* First, see if enough time has passed since the last GP. */ 1176 t = ktime_get_mono_fast_ns(); 1177 tlast = READ_ONCE(ssp->srcu_last_gp_end); 1178 if (exp_holdoff == 0 || 1179 time_in_range_open(t, tlast, tlast + exp_holdoff)) 1180 return false; /* Too soon after last GP. */ 1181 1182 /* Next, check for probable idleness. */ 1183 curseq = rcu_seq_current(&ssp->srcu_gp_seq); 1184 smp_mb(); /* Order ->srcu_gp_seq with ->srcu_gp_seq_needed. */ 1185 if (ULONG_CMP_LT(curseq, READ_ONCE(ssp->srcu_gp_seq_needed))) 1186 return false; /* Grace period in progress, so not idle. */ 1187 smp_mb(); /* Order ->srcu_gp_seq with prior access. */ 1188 if (curseq != rcu_seq_current(&ssp->srcu_gp_seq)) 1189 return false; /* GP # changed, so not idle. */ 1190 return true; /* With reasonable probability, idle! */ 1191 } 1192 1193 /* 1194 * SRCU callback function to leak a callback. 1195 */ 1196 static void srcu_leak_callback(struct rcu_head *rhp) 1197 { 1198 } 1199 1200 /* 1201 * Start an SRCU grace period, and also queue the callback if non-NULL. 1202 */ 1203 static unsigned long srcu_gp_start_if_needed(struct srcu_struct *ssp, 1204 struct rcu_head *rhp, bool do_norm) 1205 { 1206 unsigned long flags; 1207 int idx; 1208 bool needexp = false; 1209 bool needgp = false; 1210 unsigned long s; 1211 struct srcu_data *sdp; 1212 struct srcu_node *sdp_mynode; 1213 int ss_state; 1214 1215 check_init_srcu_struct(ssp); 1216 /* 1217 * While starting a new grace period, make sure we are in an 1218 * SRCU read-side critical section so that the grace-period 1219 * sequence number cannot wrap around in the meantime. 1220 */ 1221 idx = __srcu_read_lock_nmisafe(ssp); 1222 ss_state = smp_load_acquire(&ssp->srcu_size_state); 1223 if (ss_state < SRCU_SIZE_WAIT_CALL) 1224 sdp = per_cpu_ptr(ssp->sda, get_boot_cpu_id()); 1225 else 1226 sdp = raw_cpu_ptr(ssp->sda); 1227 spin_lock_irqsave_sdp_contention(sdp, &flags); 1228 if (rhp) 1229 rcu_segcblist_enqueue(&sdp->srcu_cblist, rhp); 1230 rcu_segcblist_advance(&sdp->srcu_cblist, 1231 rcu_seq_current(&ssp->srcu_gp_seq)); 1232 s = rcu_seq_snap(&ssp->srcu_gp_seq); 1233 (void)rcu_segcblist_accelerate(&sdp->srcu_cblist, s); 1234 if (ULONG_CMP_LT(sdp->srcu_gp_seq_needed, s)) { 1235 sdp->srcu_gp_seq_needed = s; 1236 needgp = true; 1237 } 1238 if (!do_norm && ULONG_CMP_LT(sdp->srcu_gp_seq_needed_exp, s)) { 1239 sdp->srcu_gp_seq_needed_exp = s; 1240 needexp = true; 1241 } 1242 spin_unlock_irqrestore_rcu_node(sdp, flags); 1243 1244 /* Ensure that snp node tree is fully initialized before traversing it */ 1245 if (ss_state < SRCU_SIZE_WAIT_BARRIER) 1246 sdp_mynode = NULL; 1247 else 1248 sdp_mynode = sdp->mynode; 1249 1250 if (needgp) 1251 srcu_funnel_gp_start(ssp, sdp, s, do_norm); 1252 else if (needexp) 1253 srcu_funnel_exp_start(ssp, sdp_mynode, s); 1254 __srcu_read_unlock_nmisafe(ssp, idx); 1255 return s; 1256 } 1257 1258 /* 1259 * Enqueue an SRCU callback on the srcu_data structure associated with 1260 * the current CPU and the specified srcu_struct structure, initiating 1261 * grace-period processing if it is not already running. 1262 * 1263 * Note that all CPUs must agree that the grace period extended beyond 1264 * all pre-existing SRCU read-side critical section. On systems with 1265 * more than one CPU, this means that when "func()" is invoked, each CPU 1266 * is guaranteed to have executed a full memory barrier since the end of 1267 * its last corresponding SRCU read-side critical section whose beginning 1268 * preceded the call to call_srcu(). It also means that each CPU executing 1269 * an SRCU read-side critical section that continues beyond the start of 1270 * "func()" must have executed a memory barrier after the call_srcu() 1271 * but before the beginning of that SRCU read-side critical section. 1272 * Note that these guarantees include CPUs that are offline, idle, or 1273 * executing in user mode, as well as CPUs that are executing in the kernel. 1274 * 1275 * Furthermore, if CPU A invoked call_srcu() and CPU B invoked the 1276 * resulting SRCU callback function "func()", then both CPU A and CPU 1277 * B are guaranteed to execute a full memory barrier during the time 1278 * interval between the call to call_srcu() and the invocation of "func()". 1279 * This guarantee applies even if CPU A and CPU B are the same CPU (but 1280 * again only if the system has more than one CPU). 1281 * 1282 * Of course, these guarantees apply only for invocations of call_srcu(), 1283 * srcu_read_lock(), and srcu_read_unlock() that are all passed the same 1284 * srcu_struct structure. 1285 */ 1286 static void __call_srcu(struct srcu_struct *ssp, struct rcu_head *rhp, 1287 rcu_callback_t func, bool do_norm) 1288 { 1289 if (debug_rcu_head_queue(rhp)) { 1290 /* Probable double call_srcu(), so leak the callback. */ 1291 WRITE_ONCE(rhp->func, srcu_leak_callback); 1292 WARN_ONCE(1, "call_srcu(): Leaked duplicate callback\n"); 1293 return; 1294 } 1295 rhp->func = func; 1296 (void)srcu_gp_start_if_needed(ssp, rhp, do_norm); 1297 } 1298 1299 /** 1300 * call_srcu() - Queue a callback for invocation after an SRCU grace period 1301 * @ssp: srcu_struct in queue the callback 1302 * @rhp: structure to be used for queueing the SRCU callback. 1303 * @func: function to be invoked after the SRCU grace period 1304 * 1305 * The callback function will be invoked some time after a full SRCU 1306 * grace period elapses, in other words after all pre-existing SRCU 1307 * read-side critical sections have completed. However, the callback 1308 * function might well execute concurrently with other SRCU read-side 1309 * critical sections that started after call_srcu() was invoked. SRCU 1310 * read-side critical sections are delimited by srcu_read_lock() and 1311 * srcu_read_unlock(), and may be nested. 1312 * 1313 * The callback will be invoked from process context, but must nevertheless 1314 * be fast and must not block. 1315 */ 1316 void call_srcu(struct srcu_struct *ssp, struct rcu_head *rhp, 1317 rcu_callback_t func) 1318 { 1319 __call_srcu(ssp, rhp, func, true); 1320 } 1321 EXPORT_SYMBOL_GPL(call_srcu); 1322 1323 /* 1324 * Helper function for synchronize_srcu() and synchronize_srcu_expedited(). 1325 */ 1326 static void __synchronize_srcu(struct srcu_struct *ssp, bool do_norm) 1327 { 1328 struct rcu_synchronize rcu; 1329 1330 RCU_LOCKDEP_WARN(lockdep_is_held(ssp) || 1331 lock_is_held(&rcu_bh_lock_map) || 1332 lock_is_held(&rcu_lock_map) || 1333 lock_is_held(&rcu_sched_lock_map), 1334 "Illegal synchronize_srcu() in same-type SRCU (or in RCU) read-side critical section"); 1335 1336 if (rcu_scheduler_active == RCU_SCHEDULER_INACTIVE) 1337 return; 1338 might_sleep(); 1339 check_init_srcu_struct(ssp); 1340 init_completion(&rcu.completion); 1341 init_rcu_head_on_stack(&rcu.head); 1342 __call_srcu(ssp, &rcu.head, wakeme_after_rcu, do_norm); 1343 wait_for_completion(&rcu.completion); 1344 destroy_rcu_head_on_stack(&rcu.head); 1345 1346 /* 1347 * Make sure that later code is ordered after the SRCU grace 1348 * period. This pairs with the spin_lock_irq_rcu_node() 1349 * in srcu_invoke_callbacks(). Unlike Tree RCU, this is needed 1350 * because the current CPU might have been totally uninvolved with 1351 * (and thus unordered against) that grace period. 1352 */ 1353 smp_mb(); 1354 } 1355 1356 /** 1357 * synchronize_srcu_expedited - Brute-force SRCU grace period 1358 * @ssp: srcu_struct with which to synchronize. 1359 * 1360 * Wait for an SRCU grace period to elapse, but be more aggressive about 1361 * spinning rather than blocking when waiting. 1362 * 1363 * Note that synchronize_srcu_expedited() has the same deadlock and 1364 * memory-ordering properties as does synchronize_srcu(). 1365 */ 1366 void synchronize_srcu_expedited(struct srcu_struct *ssp) 1367 { 1368 __synchronize_srcu(ssp, rcu_gp_is_normal()); 1369 } 1370 EXPORT_SYMBOL_GPL(synchronize_srcu_expedited); 1371 1372 /** 1373 * synchronize_srcu - wait for prior SRCU read-side critical-section completion 1374 * @ssp: srcu_struct with which to synchronize. 1375 * 1376 * Wait for the count to drain to zero of both indexes. To avoid the 1377 * possible starvation of synchronize_srcu(), it waits for the count of 1378 * the index=((->srcu_idx & 1) ^ 1) to drain to zero at first, 1379 * and then flip the srcu_idx and wait for the count of the other index. 1380 * 1381 * Can block; must be called from process context. 1382 * 1383 * Note that it is illegal to call synchronize_srcu() from the corresponding 1384 * SRCU read-side critical section; doing so will result in deadlock. 1385 * However, it is perfectly legal to call synchronize_srcu() on one 1386 * srcu_struct from some other srcu_struct's read-side critical section, 1387 * as long as the resulting graph of srcu_structs is acyclic. 1388 * 1389 * There are memory-ordering constraints implied by synchronize_srcu(). 1390 * On systems with more than one CPU, when synchronize_srcu() returns, 1391 * each CPU is guaranteed to have executed a full memory barrier since 1392 * the end of its last corresponding SRCU read-side critical section 1393 * whose beginning preceded the call to synchronize_srcu(). In addition, 1394 * each CPU having an SRCU read-side critical section that extends beyond 1395 * the return from synchronize_srcu() is guaranteed to have executed a 1396 * full memory barrier after the beginning of synchronize_srcu() and before 1397 * the beginning of that SRCU read-side critical section. Note that these 1398 * guarantees include CPUs that are offline, idle, or executing in user mode, 1399 * as well as CPUs that are executing in the kernel. 1400 * 1401 * Furthermore, if CPU A invoked synchronize_srcu(), which returned 1402 * to its caller on CPU B, then both CPU A and CPU B are guaranteed 1403 * to have executed a full memory barrier during the execution of 1404 * synchronize_srcu(). This guarantee applies even if CPU A and CPU B 1405 * are the same CPU, but again only if the system has more than one CPU. 1406 * 1407 * Of course, these memory-ordering guarantees apply only when 1408 * synchronize_srcu(), srcu_read_lock(), and srcu_read_unlock() are 1409 * passed the same srcu_struct structure. 1410 * 1411 * Implementation of these memory-ordering guarantees is similar to 1412 * that of synchronize_rcu(). 1413 * 1414 * If SRCU is likely idle, expedite the first request. This semantic 1415 * was provided by Classic SRCU, and is relied upon by its users, so TREE 1416 * SRCU must also provide it. Note that detecting idleness is heuristic 1417 * and subject to both false positives and negatives. 1418 */ 1419 void synchronize_srcu(struct srcu_struct *ssp) 1420 { 1421 if (srcu_might_be_idle(ssp) || rcu_gp_is_expedited()) 1422 synchronize_srcu_expedited(ssp); 1423 else 1424 __synchronize_srcu(ssp, true); 1425 } 1426 EXPORT_SYMBOL_GPL(synchronize_srcu); 1427 1428 /** 1429 * get_state_synchronize_srcu - Provide an end-of-grace-period cookie 1430 * @ssp: srcu_struct to provide cookie for. 1431 * 1432 * This function returns a cookie that can be passed to 1433 * poll_state_synchronize_srcu(), which will return true if a full grace 1434 * period has elapsed in the meantime. It is the caller's responsibility 1435 * to make sure that grace period happens, for example, by invoking 1436 * call_srcu() after return from get_state_synchronize_srcu(). 1437 */ 1438 unsigned long get_state_synchronize_srcu(struct srcu_struct *ssp) 1439 { 1440 // Any prior manipulation of SRCU-protected data must happen 1441 // before the load from ->srcu_gp_seq. 1442 smp_mb(); 1443 return rcu_seq_snap(&ssp->srcu_gp_seq); 1444 } 1445 EXPORT_SYMBOL_GPL(get_state_synchronize_srcu); 1446 1447 /** 1448 * start_poll_synchronize_srcu - Provide cookie and start grace period 1449 * @ssp: srcu_struct to provide cookie for. 1450 * 1451 * This function returns a cookie that can be passed to 1452 * poll_state_synchronize_srcu(), which will return true if a full grace 1453 * period has elapsed in the meantime. Unlike get_state_synchronize_srcu(), 1454 * this function also ensures that any needed SRCU grace period will be 1455 * started. This convenience does come at a cost in terms of CPU overhead. 1456 */ 1457 unsigned long start_poll_synchronize_srcu(struct srcu_struct *ssp) 1458 { 1459 return srcu_gp_start_if_needed(ssp, NULL, true); 1460 } 1461 EXPORT_SYMBOL_GPL(start_poll_synchronize_srcu); 1462 1463 /** 1464 * poll_state_synchronize_srcu - Has cookie's grace period ended? 1465 * @ssp: srcu_struct to provide cookie for. 1466 * @cookie: Return value from get_state_synchronize_srcu() or start_poll_synchronize_srcu(). 1467 * 1468 * This function takes the cookie that was returned from either 1469 * get_state_synchronize_srcu() or start_poll_synchronize_srcu(), and 1470 * returns @true if an SRCU grace period elapsed since the time that the 1471 * cookie was created. 1472 * 1473 * Because cookies are finite in size, wrapping/overflow is possible. 1474 * This is more pronounced on 32-bit systems where cookies are 32 bits, 1475 * where in theory wrapping could happen in about 14 hours assuming 1476 * 25-microsecond expedited SRCU grace periods. However, a more likely 1477 * overflow lower bound is on the order of 24 days in the case of 1478 * one-millisecond SRCU grace periods. Of course, wrapping in a 64-bit 1479 * system requires geologic timespans, as in more than seven million years 1480 * even for expedited SRCU grace periods. 1481 * 1482 * Wrapping/overflow is much more of an issue for CONFIG_SMP=n systems 1483 * that also have CONFIG_PREEMPTION=n, which selects Tiny SRCU. This uses 1484 * a 16-bit cookie, which rcutorture routinely wraps in a matter of a 1485 * few minutes. If this proves to be a problem, this counter will be 1486 * expanded to the same size as for Tree SRCU. 1487 */ 1488 bool poll_state_synchronize_srcu(struct srcu_struct *ssp, unsigned long cookie) 1489 { 1490 if (!rcu_seq_done(&ssp->srcu_gp_seq, cookie)) 1491 return false; 1492 // Ensure that the end of the SRCU grace period happens before 1493 // any subsequent code that the caller might execute. 1494 smp_mb(); // ^^^ 1495 return true; 1496 } 1497 EXPORT_SYMBOL_GPL(poll_state_synchronize_srcu); 1498 1499 /* 1500 * Callback function for srcu_barrier() use. 1501 */ 1502 static void srcu_barrier_cb(struct rcu_head *rhp) 1503 { 1504 struct srcu_data *sdp; 1505 struct srcu_struct *ssp; 1506 1507 sdp = container_of(rhp, struct srcu_data, srcu_barrier_head); 1508 ssp = sdp->ssp; 1509 if (atomic_dec_and_test(&ssp->srcu_barrier_cpu_cnt)) 1510 complete(&ssp->srcu_barrier_completion); 1511 } 1512 1513 /* 1514 * Enqueue an srcu_barrier() callback on the specified srcu_data 1515 * structure's ->cblist. but only if that ->cblist already has at least one 1516 * callback enqueued. Note that if a CPU already has callbacks enqueue, 1517 * it must have already registered the need for a future grace period, 1518 * so all we need do is enqueue a callback that will use the same grace 1519 * period as the last callback already in the queue. 1520 */ 1521 static void srcu_barrier_one_cpu(struct srcu_struct *ssp, struct srcu_data *sdp) 1522 { 1523 spin_lock_irq_rcu_node(sdp); 1524 atomic_inc(&ssp->srcu_barrier_cpu_cnt); 1525 sdp->srcu_barrier_head.func = srcu_barrier_cb; 1526 debug_rcu_head_queue(&sdp->srcu_barrier_head); 1527 if (!rcu_segcblist_entrain(&sdp->srcu_cblist, 1528 &sdp->srcu_barrier_head)) { 1529 debug_rcu_head_unqueue(&sdp->srcu_barrier_head); 1530 atomic_dec(&ssp->srcu_barrier_cpu_cnt); 1531 } 1532 spin_unlock_irq_rcu_node(sdp); 1533 } 1534 1535 /** 1536 * srcu_barrier - Wait until all in-flight call_srcu() callbacks complete. 1537 * @ssp: srcu_struct on which to wait for in-flight callbacks. 1538 */ 1539 void srcu_barrier(struct srcu_struct *ssp) 1540 { 1541 int cpu; 1542 int idx; 1543 unsigned long s = rcu_seq_snap(&ssp->srcu_barrier_seq); 1544 1545 check_init_srcu_struct(ssp); 1546 mutex_lock(&ssp->srcu_barrier_mutex); 1547 if (rcu_seq_done(&ssp->srcu_barrier_seq, s)) { 1548 smp_mb(); /* Force ordering following return. */ 1549 mutex_unlock(&ssp->srcu_barrier_mutex); 1550 return; /* Someone else did our work for us. */ 1551 } 1552 rcu_seq_start(&ssp->srcu_barrier_seq); 1553 init_completion(&ssp->srcu_barrier_completion); 1554 1555 /* Initial count prevents reaching zero until all CBs are posted. */ 1556 atomic_set(&ssp->srcu_barrier_cpu_cnt, 1); 1557 1558 idx = __srcu_read_lock_nmisafe(ssp); 1559 if (smp_load_acquire(&ssp->srcu_size_state) < SRCU_SIZE_WAIT_BARRIER) 1560 srcu_barrier_one_cpu(ssp, per_cpu_ptr(ssp->sda, get_boot_cpu_id())); 1561 else 1562 for_each_possible_cpu(cpu) 1563 srcu_barrier_one_cpu(ssp, per_cpu_ptr(ssp->sda, cpu)); 1564 __srcu_read_unlock_nmisafe(ssp, idx); 1565 1566 /* Remove the initial count, at which point reaching zero can happen. */ 1567 if (atomic_dec_and_test(&ssp->srcu_barrier_cpu_cnt)) 1568 complete(&ssp->srcu_barrier_completion); 1569 wait_for_completion(&ssp->srcu_barrier_completion); 1570 1571 rcu_seq_end(&ssp->srcu_barrier_seq); 1572 mutex_unlock(&ssp->srcu_barrier_mutex); 1573 } 1574 EXPORT_SYMBOL_GPL(srcu_barrier); 1575 1576 /** 1577 * srcu_batches_completed - return batches completed. 1578 * @ssp: srcu_struct on which to report batch completion. 1579 * 1580 * Report the number of batches, correlated with, but not necessarily 1581 * precisely the same as, the number of grace periods that have elapsed. 1582 */ 1583 unsigned long srcu_batches_completed(struct srcu_struct *ssp) 1584 { 1585 return READ_ONCE(ssp->srcu_idx); 1586 } 1587 EXPORT_SYMBOL_GPL(srcu_batches_completed); 1588 1589 /* 1590 * Core SRCU state machine. Push state bits of ->srcu_gp_seq 1591 * to SRCU_STATE_SCAN2, and invoke srcu_gp_end() when scan has 1592 * completed in that state. 1593 */ 1594 static void srcu_advance_state(struct srcu_struct *ssp) 1595 { 1596 int idx; 1597 1598 mutex_lock(&ssp->srcu_gp_mutex); 1599 1600 /* 1601 * Because readers might be delayed for an extended period after 1602 * fetching ->srcu_idx for their index, at any point in time there 1603 * might well be readers using both idx=0 and idx=1. We therefore 1604 * need to wait for readers to clear from both index values before 1605 * invoking a callback. 1606 * 1607 * The load-acquire ensures that we see the accesses performed 1608 * by the prior grace period. 1609 */ 1610 idx = rcu_seq_state(smp_load_acquire(&ssp->srcu_gp_seq)); /* ^^^ */ 1611 if (idx == SRCU_STATE_IDLE) { 1612 spin_lock_irq_rcu_node(ssp); 1613 if (ULONG_CMP_GE(ssp->srcu_gp_seq, ssp->srcu_gp_seq_needed)) { 1614 WARN_ON_ONCE(rcu_seq_state(ssp->srcu_gp_seq)); 1615 spin_unlock_irq_rcu_node(ssp); 1616 mutex_unlock(&ssp->srcu_gp_mutex); 1617 return; 1618 } 1619 idx = rcu_seq_state(READ_ONCE(ssp->srcu_gp_seq)); 1620 if (idx == SRCU_STATE_IDLE) 1621 srcu_gp_start(ssp); 1622 spin_unlock_irq_rcu_node(ssp); 1623 if (idx != SRCU_STATE_IDLE) { 1624 mutex_unlock(&ssp->srcu_gp_mutex); 1625 return; /* Someone else started the grace period. */ 1626 } 1627 } 1628 1629 if (rcu_seq_state(READ_ONCE(ssp->srcu_gp_seq)) == SRCU_STATE_SCAN1) { 1630 idx = 1 ^ (ssp->srcu_idx & 1); 1631 if (!try_check_zero(ssp, idx, 1)) { 1632 mutex_unlock(&ssp->srcu_gp_mutex); 1633 return; /* readers present, retry later. */ 1634 } 1635 srcu_flip(ssp); 1636 spin_lock_irq_rcu_node(ssp); 1637 rcu_seq_set_state(&ssp->srcu_gp_seq, SRCU_STATE_SCAN2); 1638 ssp->srcu_n_exp_nodelay = 0; 1639 spin_unlock_irq_rcu_node(ssp); 1640 } 1641 1642 if (rcu_seq_state(READ_ONCE(ssp->srcu_gp_seq)) == SRCU_STATE_SCAN2) { 1643 1644 /* 1645 * SRCU read-side critical sections are normally short, 1646 * so check at least twice in quick succession after a flip. 1647 */ 1648 idx = 1 ^ (ssp->srcu_idx & 1); 1649 if (!try_check_zero(ssp, idx, 2)) { 1650 mutex_unlock(&ssp->srcu_gp_mutex); 1651 return; /* readers present, retry later. */ 1652 } 1653 ssp->srcu_n_exp_nodelay = 0; 1654 srcu_gp_end(ssp); /* Releases ->srcu_gp_mutex. */ 1655 } 1656 } 1657 1658 /* 1659 * Invoke a limited number of SRCU callbacks that have passed through 1660 * their grace period. If there are more to do, SRCU will reschedule 1661 * the workqueue. Note that needed memory barriers have been executed 1662 * in this task's context by srcu_readers_active_idx_check(). 1663 */ 1664 static void srcu_invoke_callbacks(struct work_struct *work) 1665 { 1666 long len; 1667 bool more; 1668 struct rcu_cblist ready_cbs; 1669 struct rcu_head *rhp; 1670 struct srcu_data *sdp; 1671 struct srcu_struct *ssp; 1672 1673 sdp = container_of(work, struct srcu_data, work); 1674 1675 ssp = sdp->ssp; 1676 rcu_cblist_init(&ready_cbs); 1677 spin_lock_irq_rcu_node(sdp); 1678 rcu_segcblist_advance(&sdp->srcu_cblist, 1679 rcu_seq_current(&ssp->srcu_gp_seq)); 1680 if (sdp->srcu_cblist_invoking || 1681 !rcu_segcblist_ready_cbs(&sdp->srcu_cblist)) { 1682 spin_unlock_irq_rcu_node(sdp); 1683 return; /* Someone else on the job or nothing to do. */ 1684 } 1685 1686 /* We are on the job! Extract and invoke ready callbacks. */ 1687 sdp->srcu_cblist_invoking = true; 1688 rcu_segcblist_extract_done_cbs(&sdp->srcu_cblist, &ready_cbs); 1689 len = ready_cbs.len; 1690 spin_unlock_irq_rcu_node(sdp); 1691 rhp = rcu_cblist_dequeue(&ready_cbs); 1692 for (; rhp != NULL; rhp = rcu_cblist_dequeue(&ready_cbs)) { 1693 debug_rcu_head_unqueue(rhp); 1694 local_bh_disable(); 1695 rhp->func(rhp); 1696 local_bh_enable(); 1697 } 1698 WARN_ON_ONCE(ready_cbs.len); 1699 1700 /* 1701 * Update counts, accelerate new callbacks, and if needed, 1702 * schedule another round of callback invocation. 1703 */ 1704 spin_lock_irq_rcu_node(sdp); 1705 rcu_segcblist_add_len(&sdp->srcu_cblist, -len); 1706 (void)rcu_segcblist_accelerate(&sdp->srcu_cblist, 1707 rcu_seq_snap(&ssp->srcu_gp_seq)); 1708 sdp->srcu_cblist_invoking = false; 1709 more = rcu_segcblist_ready_cbs(&sdp->srcu_cblist); 1710 spin_unlock_irq_rcu_node(sdp); 1711 if (more) 1712 srcu_schedule_cbs_sdp(sdp, 0); 1713 } 1714 1715 /* 1716 * Finished one round of SRCU grace period. Start another if there are 1717 * more SRCU callbacks queued, otherwise put SRCU into not-running state. 1718 */ 1719 static void srcu_reschedule(struct srcu_struct *ssp, unsigned long delay) 1720 { 1721 bool pushgp = true; 1722 1723 spin_lock_irq_rcu_node(ssp); 1724 if (ULONG_CMP_GE(ssp->srcu_gp_seq, ssp->srcu_gp_seq_needed)) { 1725 if (!WARN_ON_ONCE(rcu_seq_state(ssp->srcu_gp_seq))) { 1726 /* All requests fulfilled, time to go idle. */ 1727 pushgp = false; 1728 } 1729 } else if (!rcu_seq_state(ssp->srcu_gp_seq)) { 1730 /* Outstanding request and no GP. Start one. */ 1731 srcu_gp_start(ssp); 1732 } 1733 spin_unlock_irq_rcu_node(ssp); 1734 1735 if (pushgp) 1736 queue_delayed_work(rcu_gp_wq, &ssp->work, delay); 1737 } 1738 1739 /* 1740 * This is the work-queue function that handles SRCU grace periods. 1741 */ 1742 static void process_srcu(struct work_struct *work) 1743 { 1744 unsigned long curdelay; 1745 unsigned long j; 1746 struct srcu_struct *ssp; 1747 1748 ssp = container_of(work, struct srcu_struct, work.work); 1749 1750 srcu_advance_state(ssp); 1751 curdelay = srcu_get_delay(ssp); 1752 if (curdelay) { 1753 WRITE_ONCE(ssp->reschedule_count, 0); 1754 } else { 1755 j = jiffies; 1756 if (READ_ONCE(ssp->reschedule_jiffies) == j) { 1757 WRITE_ONCE(ssp->reschedule_count, READ_ONCE(ssp->reschedule_count) + 1); 1758 if (READ_ONCE(ssp->reschedule_count) > srcu_max_nodelay) 1759 curdelay = 1; 1760 } else { 1761 WRITE_ONCE(ssp->reschedule_count, 1); 1762 WRITE_ONCE(ssp->reschedule_jiffies, j); 1763 } 1764 } 1765 srcu_reschedule(ssp, curdelay); 1766 } 1767 1768 void srcutorture_get_gp_data(enum rcutorture_type test_type, 1769 struct srcu_struct *ssp, int *flags, 1770 unsigned long *gp_seq) 1771 { 1772 if (test_type != SRCU_FLAVOR) 1773 return; 1774 *flags = 0; 1775 *gp_seq = rcu_seq_current(&ssp->srcu_gp_seq); 1776 } 1777 EXPORT_SYMBOL_GPL(srcutorture_get_gp_data); 1778 1779 static const char * const srcu_size_state_name[] = { 1780 "SRCU_SIZE_SMALL", 1781 "SRCU_SIZE_ALLOC", 1782 "SRCU_SIZE_WAIT_BARRIER", 1783 "SRCU_SIZE_WAIT_CALL", 1784 "SRCU_SIZE_WAIT_CBS1", 1785 "SRCU_SIZE_WAIT_CBS2", 1786 "SRCU_SIZE_WAIT_CBS3", 1787 "SRCU_SIZE_WAIT_CBS4", 1788 "SRCU_SIZE_BIG", 1789 "SRCU_SIZE_???", 1790 }; 1791 1792 void srcu_torture_stats_print(struct srcu_struct *ssp, char *tt, char *tf) 1793 { 1794 int cpu; 1795 int idx; 1796 unsigned long s0 = 0, s1 = 0; 1797 int ss_state = READ_ONCE(ssp->srcu_size_state); 1798 int ss_state_idx = ss_state; 1799 1800 idx = ssp->srcu_idx & 0x1; 1801 if (ss_state < 0 || ss_state >= ARRAY_SIZE(srcu_size_state_name)) 1802 ss_state_idx = ARRAY_SIZE(srcu_size_state_name) - 1; 1803 pr_alert("%s%s Tree SRCU g%ld state %d (%s)", 1804 tt, tf, rcu_seq_current(&ssp->srcu_gp_seq), ss_state, 1805 srcu_size_state_name[ss_state_idx]); 1806 if (!ssp->sda) { 1807 // Called after cleanup_srcu_struct(), perhaps. 1808 pr_cont(" No per-CPU srcu_data structures (->sda == NULL).\n"); 1809 } else { 1810 pr_cont(" per-CPU(idx=%d):", idx); 1811 for_each_possible_cpu(cpu) { 1812 unsigned long l0, l1; 1813 unsigned long u0, u1; 1814 long c0, c1; 1815 struct srcu_data *sdp; 1816 1817 sdp = per_cpu_ptr(ssp->sda, cpu); 1818 u0 = data_race(atomic_long_read(&sdp->srcu_unlock_count[!idx])); 1819 u1 = data_race(atomic_long_read(&sdp->srcu_unlock_count[idx])); 1820 1821 /* 1822 * Make sure that a lock is always counted if the corresponding 1823 * unlock is counted. 1824 */ 1825 smp_rmb(); 1826 1827 l0 = data_race(atomic_long_read(&sdp->srcu_lock_count[!idx])); 1828 l1 = data_race(atomic_long_read(&sdp->srcu_lock_count[idx])); 1829 1830 c0 = l0 - u0; 1831 c1 = l1 - u1; 1832 pr_cont(" %d(%ld,%ld %c)", 1833 cpu, c0, c1, 1834 "C."[rcu_segcblist_empty(&sdp->srcu_cblist)]); 1835 s0 += c0; 1836 s1 += c1; 1837 } 1838 pr_cont(" T(%ld,%ld)\n", s0, s1); 1839 } 1840 if (SRCU_SIZING_IS_TORTURE()) 1841 srcu_transition_to_big(ssp); 1842 } 1843 EXPORT_SYMBOL_GPL(srcu_torture_stats_print); 1844 1845 static int __init srcu_bootup_announce(void) 1846 { 1847 pr_info("Hierarchical SRCU implementation.\n"); 1848 if (exp_holdoff != DEFAULT_SRCU_EXP_HOLDOFF) 1849 pr_info("\tNon-default auto-expedite holdoff of %lu ns.\n", exp_holdoff); 1850 if (srcu_retry_check_delay != SRCU_DEFAULT_RETRY_CHECK_DELAY) 1851 pr_info("\tNon-default retry check delay of %lu us.\n", srcu_retry_check_delay); 1852 if (srcu_max_nodelay != SRCU_DEFAULT_MAX_NODELAY) 1853 pr_info("\tNon-default max no-delay of %lu.\n", srcu_max_nodelay); 1854 pr_info("\tMax phase no-delay instances is %lu.\n", srcu_max_nodelay_phase); 1855 return 0; 1856 } 1857 early_initcall(srcu_bootup_announce); 1858 1859 void __init srcu_init(void) 1860 { 1861 struct srcu_struct *ssp; 1862 1863 /* Decide on srcu_struct-size strategy. */ 1864 if (SRCU_SIZING_IS(SRCU_SIZING_AUTO)) { 1865 if (nr_cpu_ids >= big_cpu_lim) { 1866 convert_to_big = SRCU_SIZING_INIT; // Don't bother waiting for contention. 1867 pr_info("%s: Setting srcu_struct sizes to big.\n", __func__); 1868 } else { 1869 convert_to_big = SRCU_SIZING_NONE | SRCU_SIZING_CONTEND; 1870 pr_info("%s: Setting srcu_struct sizes based on contention.\n", __func__); 1871 } 1872 } 1873 1874 /* 1875 * Once that is set, call_srcu() can follow the normal path and 1876 * queue delayed work. This must follow RCU workqueues creation 1877 * and timers initialization. 1878 */ 1879 srcu_init_done = true; 1880 while (!list_empty(&srcu_boot_list)) { 1881 ssp = list_first_entry(&srcu_boot_list, struct srcu_struct, 1882 work.work.entry); 1883 list_del_init(&ssp->work.work.entry); 1884 if (SRCU_SIZING_IS(SRCU_SIZING_INIT) && ssp->srcu_size_state == SRCU_SIZE_SMALL) 1885 ssp->srcu_size_state = SRCU_SIZE_ALLOC; 1886 queue_work(rcu_gp_wq, &ssp->work.work); 1887 } 1888 } 1889 1890 #ifdef CONFIG_MODULES 1891 1892 /* Initialize any global-scope srcu_struct structures used by this module. */ 1893 static int srcu_module_coming(struct module *mod) 1894 { 1895 int i; 1896 struct srcu_struct **sspp = mod->srcu_struct_ptrs; 1897 int ret; 1898 1899 for (i = 0; i < mod->num_srcu_structs; i++) { 1900 ret = init_srcu_struct(*(sspp++)); 1901 if (WARN_ON_ONCE(ret)) 1902 return ret; 1903 } 1904 return 0; 1905 } 1906 1907 /* Clean up any global-scope srcu_struct structures used by this module. */ 1908 static void srcu_module_going(struct module *mod) 1909 { 1910 int i; 1911 struct srcu_struct **sspp = mod->srcu_struct_ptrs; 1912 1913 for (i = 0; i < mod->num_srcu_structs; i++) 1914 cleanup_srcu_struct(*(sspp++)); 1915 } 1916 1917 /* Handle one module, either coming or going. */ 1918 static int srcu_module_notify(struct notifier_block *self, 1919 unsigned long val, void *data) 1920 { 1921 struct module *mod = data; 1922 int ret = 0; 1923 1924 switch (val) { 1925 case MODULE_STATE_COMING: 1926 ret = srcu_module_coming(mod); 1927 break; 1928 case MODULE_STATE_GOING: 1929 srcu_module_going(mod); 1930 break; 1931 default: 1932 break; 1933 } 1934 return ret; 1935 } 1936 1937 static struct notifier_block srcu_module_nb = { 1938 .notifier_call = srcu_module_notify, 1939 .priority = 0, 1940 }; 1941 1942 static __init int init_srcu_module_notifier(void) 1943 { 1944 int ret; 1945 1946 ret = register_module_notifier(&srcu_module_nb); 1947 if (ret) 1948 pr_warn("Failed to register srcu module notifier\n"); 1949 return ret; 1950 } 1951 late_initcall(init_srcu_module_notifier); 1952 1953 #endif /* #ifdef CONFIG_MODULES */ 1954