1 /* SPDX-License-Identifier: GPL-2.0+ */ 2 /* 3 * Sleepable Read-Copy Update mechanism for mutual exclusion, 4 * tree variant. 5 * 6 * Copyright (C) IBM Corporation, 2017 7 * 8 * Author: Paul McKenney <paulmck@linux.ibm.com> 9 */ 10 11 #ifndef _LINUX_SRCU_TREE_H 12 #define _LINUX_SRCU_TREE_H 13 14 #include <linux/rcu_node_tree.h> 15 #include <linux/completion.h> 16 #include <linux/irq_work_types.h> 17 #include <linux/llist.h> 18 19 struct srcu_node; 20 struct srcu_struct; 21 22 /* One element of the srcu_data srcu_ctrs array. */ 23 struct srcu_ctr { 24 atomic_long_t srcu_locks; /* Locks per CPU. */ 25 atomic_long_t srcu_unlocks; /* Unlocks per CPU. */ 26 }; 27 28 /* 29 * Per-CPU structure feeding into leaf srcu_node, similar in function 30 * to rcu_node. 31 */ 32 struct srcu_data { 33 /* Read-side state. */ 34 struct srcu_ctr srcu_ctrs[2]; /* Locks and unlocks per CPU. */ 35 int srcu_reader_flavor; /* Reader flavor for srcu_struct structure? */ 36 /* Values: SRCU_READ_FLAVOR_.* */ 37 38 /* Update-side state. */ 39 raw_spinlock_t __private lock ____cacheline_internodealigned_in_smp; 40 struct rcu_segcblist srcu_cblist; /* List of callbacks.*/ 41 unsigned long srcu_gp_seq_needed; /* Furthest future GP needed. */ 42 unsigned long srcu_gp_seq_needed_exp; /* Furthest future exp GP. */ 43 bool srcu_cblist_invoking; /* Invoking these CBs? */ 44 struct timer_list delay_work; /* Delay for CB invoking */ 45 struct work_struct work; /* Context for CB invoking. */ 46 struct llist_head defer_cbs; /* Callbacks deferred on re-entry. */ 47 struct llist_node defer_link; /* Links onto the per-CPU deferral drain list */ 48 struct rcu_head srcu_barrier_head; /* For srcu_barrier() use. */ 49 struct rcu_head srcu_ec_head; /* For srcu_expedite_current() use. */ 50 int srcu_ec_state; /* State for srcu_expedite_current(). */ 51 struct srcu_node *mynode; /* Leaf srcu_node. */ 52 unsigned long grpmask; /* Mask for leaf srcu_node */ 53 /* ->srcu_data_have_cbs[]. */ 54 int cpu; 55 struct srcu_struct *ssp; 56 }; 57 58 /* 59 * Node in SRCU combining tree, similar in function to rcu_data. 60 */ 61 struct srcu_node { 62 raw_spinlock_t __private lock; 63 unsigned long srcu_have_cbs[4]; /* GP seq for children having CBs, but only */ 64 /* if greater than ->srcu_gp_seq. */ 65 unsigned long srcu_data_have_cbs[4]; /* Which srcu_data structs have CBs for given GP? */ 66 unsigned long srcu_gp_seq_needed_exp; /* Furthest future exp GP. */ 67 struct srcu_node *srcu_parent; /* Next up in tree. */ 68 int grplo; /* Least CPU for node. */ 69 int grphi; /* Biggest CPU for node. */ 70 }; 71 72 /* 73 * Per-SRCU-domain structure, update-side data linked from srcu_struct. 74 */ 75 struct srcu_usage { 76 struct srcu_node *node; /* Combining tree. */ 77 struct srcu_node *level[RCU_NUM_LVLS + 1]; 78 /* First node at each level. */ 79 int srcu_size_state; /* Small-to-big transition state. */ 80 struct mutex srcu_cb_mutex; /* Serialize CB preparation. */ 81 raw_spinlock_t __private lock; /* Protect counters and size state. */ 82 struct mutex srcu_gp_mutex; /* Serialize GP work. */ 83 atomic_t srcu_atomic_gp_flag; /* Serialize atomic GP work. */ 84 unsigned long srcu_gp_seq; /* Grace-period seq #. */ 85 unsigned long srcu_gp_seq_needed; /* Latest gp_seq needed. */ 86 unsigned long srcu_gp_seq_needed_exp; /* Furthest future exp GP. */ 87 unsigned long srcu_gp_start; /* Last GP start timestamp (jiffies) */ 88 unsigned long srcu_last_gp_end; /* Last GP end timestamp (ns) */ 89 unsigned long srcu_size_jiffies; /* Current contention-measurement interval. */ 90 unsigned long srcu_n_lock_retries; /* Contention events in current interval. */ 91 unsigned long srcu_n_exp_nodelay; /* # expedited no-delays in current GP phase. */ 92 bool sda_is_static; /* May ->sda be passed to free_percpu()? */ 93 unsigned long srcu_barrier_seq; /* srcu_barrier seq #. */ 94 struct mutex srcu_barrier_mutex; /* Serialize barrier ops. */ 95 struct completion srcu_barrier_completion; 96 /* Awaken barrier rq at end. */ 97 atomic_t srcu_barrier_cpu_cnt; /* # CPUs not yet posting a */ 98 /* callback for the barrier */ 99 /* operation. */ 100 unsigned long reschedule_jiffies; 101 unsigned long reschedule_count; 102 struct delayed_work work; 103 struct irq_work irq_work; 104 struct srcu_struct *srcu_ssp; 105 }; 106 107 /* 108 * Per-SRCU-domain structure, similar in function to rcu_state. 109 */ 110 struct srcu_struct { 111 struct srcu_ctr __percpu *srcu_ctrp; 112 struct srcu_data __percpu *sda; /* Per-CPU srcu_data array. */ 113 u8 srcu_reader_flavor; 114 struct lockdep_map dep_map; 115 struct srcu_usage *srcu_sup; /* Update-side data. */ 116 }; 117 118 // Values for size state variable (->srcu_size_state). Once the state 119 // has been set to SRCU_SIZE_ALLOC, the grace-period code advances through 120 // this state machine one step per grace period until the SRCU_SIZE_BIG state 121 // is reached. Otherwise, the state machine remains in the SRCU_SIZE_SMALL 122 // state indefinitely. 123 #define SRCU_SIZE_SMALL 0 // No srcu_node combining tree, ->node == NULL 124 #define SRCU_SIZE_ALLOC 1 // An srcu_node tree is being allocated, initialized, 125 // and then referenced by ->node. It will not be used. 126 #define SRCU_SIZE_WAIT_BARRIER 2 // The srcu_node tree starts being used by everything 127 // except call_srcu(), especially by srcu_barrier(). 128 // By the end of this state, all CPUs and threads 129 // are aware of this tree's existence. 130 #define SRCU_SIZE_WAIT_CALL 3 // The srcu_node tree starts being used by call_srcu(). 131 // By the end of this state, all of the call_srcu() 132 // invocations that were running on a non-boot CPU 133 // and using the boot CPU's callback queue will have 134 // completed. 135 #define SRCU_SIZE_WAIT_CBS1 4 // Don't trust the ->srcu_have_cbs[] grace-period 136 #define SRCU_SIZE_WAIT_CBS2 5 // sequence elements or the ->srcu_data_have_cbs[] 137 #define SRCU_SIZE_WAIT_CBS3 6 // CPU-bitmask elements until all four elements of 138 #define SRCU_SIZE_WAIT_CBS4 7 // each array have been initialized. 139 #define SRCU_SIZE_BIG 8 // The srcu_node combining tree is fully initialized 140 // and all aspects of it are being put to use. 141 142 /* Values for state variable (bottom bits of ->srcu_gp_seq). */ 143 #define SRCU_STATE_IDLE 0 144 #define SRCU_STATE_SCAN1 1 145 #define SRCU_STATE_SCAN2 2 146 147 /* Values for srcu_expedite_current() state (->srcu_ec_state). */ 148 #define SRCU_EC_IDLE 0 149 #define SRCU_EC_PENDING 1 150 #define SRCU_EC_REPOST 2 151 152 /* 153 * Values for initializing gp sequence fields. Higher values allow wrap arounds to 154 * occur earlier. 155 * The second value with state is useful in the case of static initialization of 156 * srcu_usage where srcu_gp_seq_needed is expected to have some state value in its 157 * lower bits (or else it will appear to be already initialized within 158 * the call check_init_srcu_struct()). 159 */ 160 #define SRCU_GP_SEQ_INITIAL_VAL ((0UL - 100UL) << RCU_SEQ_CTR_SHIFT) 161 #define SRCU_GP_SEQ_INITIAL_VAL_WITH_STATE (SRCU_GP_SEQ_INITIAL_VAL - 1) 162 163 #define __SRCU_USAGE_INIT(name) \ 164 { \ 165 .lock = __RAW_SPIN_LOCK_UNLOCKED(name.lock), \ 166 .srcu_gp_seq = SRCU_GP_SEQ_INITIAL_VAL, \ 167 .srcu_gp_seq_needed = SRCU_GP_SEQ_INITIAL_VAL_WITH_STATE, \ 168 .srcu_gp_seq_needed_exp = SRCU_GP_SEQ_INITIAL_VAL, \ 169 .work = __DELAYED_WORK_INITIALIZER(name.work, NULL, 0), \ 170 } 171 172 #define __SRCU_STRUCT_INIT_COMMON(name, usage_name, fast) \ 173 .srcu_sup = &usage_name, \ 174 .srcu_reader_flavor = fast, \ 175 __SRCU_DEP_MAP_INIT(name) 176 177 #define __SRCU_STRUCT_INIT_MODULE(name, usage_name, fast) \ 178 { \ 179 __SRCU_STRUCT_INIT_COMMON(name, usage_name, fast) \ 180 } 181 182 #define __SRCU_STRUCT_INIT(name, usage_name, pcpu_name, fast) \ 183 { \ 184 .sda = &pcpu_name, \ 185 .srcu_ctrp = &pcpu_name.srcu_ctrs[0], \ 186 __SRCU_STRUCT_INIT_COMMON(name, usage_name, fast) \ 187 } 188 189 /* 190 * Define and initialize a srcu struct at build time. 191 * Do -not- call init_srcu_struct() nor cleanup_srcu_struct() on it. 192 * 193 * Note that although DEFINE_STATIC_SRCU() hides the name from other 194 * files, the per-CPU variable rules nevertheless require that the 195 * chosen name be globally unique. These rules also prohibit use of 196 * DEFINE_STATIC_SRCU() within a function. If these rules are too 197 * restrictive, declare the srcu_struct manually. For example, in 198 * each file: 199 * 200 * static struct srcu_struct my_srcu; 201 * 202 * Then, before the first use of each my_srcu, manually initialize it: 203 * 204 * init_srcu_struct(&my_srcu); 205 * 206 * See include/linux/percpu-defs.h for the rules on per-CPU variables. 207 * 208 * DEFINE_SRCU_FAST() and DEFINE_STATIC_SRCU_FAST create an srcu_struct 209 * and associated structures whose readers must be of the SRCU-fast variety. 210 * DEFINE_SRCU_FAST_UPDOWN() and DEFINE_STATIC_SRCU_FAST_UPDOWN() create 211 * an srcu_struct and associated structures whose readers must be of the 212 * SRCU-fast-updown variety. The key point (aside from error checking) with 213 * both varieties is that the grace periods must use synchronize_rcu() 214 * instead of smp_mb(), and given that the first (for example) 215 * srcu_read_lock_fast() might race with the first synchronize_srcu(), 216 * this different must be specified at initialization time. 217 * 218 * If you use any of the DEFINE_SRCU() functions within a module, the 219 * module-entry code will invoke init_srcu_struct() and the module-exit 220 * code will invoke cleanup_srcu_struct(). This means that if your module 221 * passes the resulting srcu_struct structure to call_srcu(), you will 222 * need to also pass this structure to srcu_barrier() prior to module exit. 223 */ 224 #ifdef MODULE 225 # define __DEFINE_SRCU(name, fast, is_static) \ 226 static struct srcu_usage name##_srcu_usage = __SRCU_USAGE_INIT(name##_srcu_usage); \ 227 is_static struct srcu_struct name = __SRCU_STRUCT_INIT_MODULE(name, name##_srcu_usage, \ 228 fast); \ 229 extern struct srcu_struct * const __srcu_struct_##name; \ 230 struct srcu_struct * const __srcu_struct_##name \ 231 __section("___srcu_struct_ptrs") = &name 232 #else 233 # define __DEFINE_SRCU(name, fast, is_static) \ 234 static DEFINE_PER_CPU(struct srcu_data, name##_srcu_data); \ 235 static struct srcu_usage name##_srcu_usage = __SRCU_USAGE_INIT(name##_srcu_usage); \ 236 is_static struct srcu_struct name = \ 237 __SRCU_STRUCT_INIT(name, name##_srcu_usage, name##_srcu_data, fast) 238 #endif 239 #define DEFINE_SRCU(name) __DEFINE_SRCU(name, 0, /* !static */) 240 #define DEFINE_STATIC_SRCU(name) __DEFINE_SRCU(name, 0, static) 241 #define DEFINE_SRCU_FAST(name) __DEFINE_SRCU(name, SRCU_READ_FLAVOR_FAST, /* !static */) 242 #define DEFINE_STATIC_SRCU_FAST(name) __DEFINE_SRCU(name, SRCU_READ_FLAVOR_FAST, static) 243 #define DEFINE_SRCU_FAST_UPDOWN(name) __DEFINE_SRCU(name, SRCU_READ_FLAVOR_FAST_UPDOWN, \ 244 /* !static */) 245 #define DEFINE_STATIC_SRCU_FAST_UPDOWN(name) \ 246 __DEFINE_SRCU(name, SRCU_READ_FLAVOR_FAST_UPDOWN, static) 247 #define DEFINE_SRCU_ATOMIC(name) __DEFINE_SRCU(name, SRCU_READ_FLAVOR_ATOMIC, /* !static */) 248 #define DEFINE_STATIC_SRCU_ATOMIC(name) __DEFINE_SRCU(name, SRCU_READ_FLAVOR_ATOMIC, static) 249 250 int __srcu_read_lock(struct srcu_struct *ssp) __acquires_shared(ssp); 251 void synchronize_srcu_expedited(struct srcu_struct *ssp); 252 void srcu_barrier(struct srcu_struct *ssp); 253 void srcu_expedite_current(struct srcu_struct *ssp); 254 void srcu_torture_stats_print(struct srcu_struct *ssp, char *tt, char *tf); 255 256 // Converts a per-CPU pointer to an ->srcu_ctrs[] array element to that 257 // element's index. 258 static inline bool __srcu_ptr_to_ctr(struct srcu_struct *ssp, struct srcu_ctr __percpu *scpp) 259 { 260 return scpp - &ssp->sda->srcu_ctrs[0]; 261 } 262 263 // Converts an integer to a per-CPU pointer to the corresponding 264 // ->srcu_ctrs[] array element. 265 static inline struct srcu_ctr __percpu *__srcu_ctr_to_ptr(struct srcu_struct *ssp, int idx) 266 { 267 return &ssp->sda->srcu_ctrs[idx]; 268 } 269 270 /* 271 * Counts the new reader in the appropriate per-CPU element of the 272 * srcu_struct. Returns a pointer that must be passed to the matching 273 * srcu_read_unlock_fast(). 274 * 275 * Note that both this_cpu_inc() and atomic_long_inc() are RCU read-side 276 * critical sections either because they disable interrupts, because 277 * they are a single instruction, or because they are read-modify-write 278 * atomic operations, depending on the whims of the architecture. 279 * This matters because the SRCU-fast grace-period mechanism uses either 280 * synchronize_rcu() or synchronize_rcu_expedited(), that is, RCU, 281 * *not* SRCU, in order to eliminate the need for the read-side smp_mb() 282 * invocations that are used by srcu_read_lock() and srcu_read_unlock(). 283 * The __srcu_read_unlock_fast() function also relies on this same RCU 284 * (again, *not* SRCU) trick to eliminate the need for smp_mb(). 285 * 286 * The key point behind this RCU trick is that if any part of a given 287 * RCU reader precedes the beginning of a given RCU grace period, then 288 * the entirety of that RCU reader and everything preceding it happens 289 * before the end of that same RCU grace period. Similarly, if any part 290 * of a given RCU reader follows the end of a given RCU grace period, 291 * then the entirety of that RCU reader and everything following it 292 * happens after the beginning of that same RCU grace period. Therefore, 293 * the operations labeled Y in __srcu_read_lock_fast() and those labeled Z 294 * in __srcu_read_unlock_fast() are ordered against the corresponding SRCU 295 * read-side critical section from the viewpoint of the SRCU grace period. 296 * This is all the ordering that is required, hence no calls to smp_mb(). 297 * 298 * This means that __srcu_read_lock_fast() is not all that fast 299 * on architectures that support NMIs but do not supply NMI-safe 300 * implementations of this_cpu_inc(). 301 */ 302 static inline struct srcu_ctr __percpu notrace *__srcu_read_lock_fast(struct srcu_struct *ssp) 303 __acquires_shared(ssp) 304 { 305 struct srcu_ctr __percpu *scp = READ_ONCE(ssp->srcu_ctrp); 306 307 if (!IS_ENABLED(CONFIG_NEED_SRCU_NMI_SAFE)) 308 this_cpu_inc(scp->srcu_locks.counter); // Y, and implicit RCU reader. 309 else 310 atomic_long_inc(raw_cpu_ptr(&scp->srcu_locks)); // Y, and implicit RCU reader. 311 barrier(); /* Avoid leaking the critical section. */ 312 __acquire_shared(ssp); 313 return scp; 314 } 315 316 /* 317 * Removes the count for the old reader from the appropriate 318 * per-CPU element of the srcu_struct. Note that this may well be a 319 * different CPU than that which was incremented by the corresponding 320 * srcu_read_lock_fast(), but it must be within the same task. 321 * 322 * Please see the __srcu_read_lock_fast() function's header comment for 323 * information on implicit RCU readers and NMI safety. 324 */ 325 static inline void notrace 326 __srcu_read_unlock_fast(struct srcu_struct *ssp, struct srcu_ctr __percpu *scp) 327 __releases_shared(ssp) 328 { 329 __release_shared(ssp); 330 barrier(); /* Avoid leaking the critical section. */ 331 if (!IS_ENABLED(CONFIG_NEED_SRCU_NMI_SAFE)) 332 this_cpu_inc(scp->srcu_unlocks.counter); // Z, and implicit RCU reader. 333 else 334 atomic_long_inc(raw_cpu_ptr(&scp->srcu_unlocks)); // Z, and implicit RCU reader. 335 } 336 337 /* 338 * Counts the new reader in the appropriate per-CPU element of the 339 * srcu_struct. Returns a pointer that must be passed to the matching 340 * srcu_read_unlock_fast_updown(). This type of reader is compatible 341 * with srcu_down_read_fast() and srcu_up_read_fast(). 342 * 343 * See the __srcu_read_lock_fast() comment for more details. 344 */ 345 static inline 346 struct srcu_ctr __percpu notrace *__srcu_read_lock_fast_updown(struct srcu_struct *ssp) 347 __acquires_shared(ssp) 348 { 349 struct srcu_ctr __percpu *scp = READ_ONCE(ssp->srcu_ctrp); 350 351 if (!IS_ENABLED(CONFIG_NEED_SRCU_NMI_SAFE)) 352 this_cpu_inc(scp->srcu_locks.counter); // Y, and implicit RCU reader. 353 else 354 atomic_long_inc(raw_cpu_ptr(&scp->srcu_locks)); // Y, and implicit RCU reader. 355 barrier(); /* Avoid leaking the critical section. */ 356 __acquire_shared(ssp); 357 return scp; 358 } 359 360 /* 361 * Removes the count for the old reader from the appropriate 362 * per-CPU element of the srcu_struct. Note that this may well be a 363 * different CPU than that which was incremented by the corresponding 364 * srcu_read_lock_fast(), but it must be within the same task. 365 * 366 * Please see the __srcu_read_lock_fast() function's header comment for 367 * information on implicit RCU readers and NMI safety. 368 */ 369 static inline void notrace 370 __srcu_read_unlock_fast_updown(struct srcu_struct *ssp, struct srcu_ctr __percpu *scp) 371 __releases_shared(ssp) 372 { 373 __release_shared(ssp); 374 barrier(); /* Avoid leaking the critical section. */ 375 if (!IS_ENABLED(CONFIG_NEED_SRCU_NMI_SAFE)) 376 this_cpu_inc(scp->srcu_unlocks.counter); // Z, and implicit RCU reader. 377 else 378 atomic_long_inc(raw_cpu_ptr(&scp->srcu_unlocks)); // Z, and implicit RCU reader. 379 } 380 381 void __srcu_check_read_flavor(struct srcu_struct *ssp, int read_flavor); 382 383 // Record SRCU-reader usage type only for CONFIG_PROVE_RCU=y kernels. 384 static inline void srcu_check_read_flavor(struct srcu_struct *ssp, int read_flavor) 385 { 386 if (IS_ENABLED(CONFIG_PROVE_RCU)) 387 __srcu_check_read_flavor(ssp, read_flavor); 388 } 389 390 /** 391 * srcu_readers_active - returns true if there are readers. and false otherwise. 392 * @ssp: which srcu_struct to count active readers (holding srcu_read_lock). 393 * 394 * Note that this is not an atomic primitive, and can therefore suffer 395 * severe errors when invoked on an active srcu_struct. That said, it 396 * can be useful as an error check at cleanup time. 397 */ 398 static inline bool srcu_readers_active(struct srcu_struct *ssp) 399 { 400 int cpu; 401 unsigned long sum = 0; 402 403 for_each_possible_cpu(cpu) { 404 struct srcu_data *sdp = per_cpu_ptr(ssp->sda, cpu); 405 406 sum += atomic_long_read(&sdp->srcu_ctrs[0].srcu_locks); 407 sum += atomic_long_read(&sdp->srcu_ctrs[1].srcu_locks); 408 sum -= atomic_long_read(&sdp->srcu_ctrs[0].srcu_unlocks); 409 sum -= atomic_long_read(&sdp->srcu_ctrs[1].srcu_unlocks); 410 } 411 return sum; 412 } 413 414 #endif 415