Branch data Line data Source code
1 : : /* SPDX-License-Identifier: GPL-2.0+ */
2 : : /*
3 : : * Read-Copy Update definitions shared among RCU implementations.
4 : : *
5 : : * Copyright IBM Corporation, 2011
6 : : *
7 : : * Author: Paul E. McKenney <paulmck@linux.ibm.com>
8 : : */
9 : :
10 : : #ifndef __LINUX_RCU_H
11 : : #define __LINUX_RCU_H
12 : :
13 : : #include <trace/events/rcu.h>
14 : :
15 : : /* Offset to allow distinguishing irq vs. task-based idle entry/exit. */
16 : : #define DYNTICK_IRQ_NONIDLE ((LONG_MAX / 2) + 1)
17 : :
18 : :
19 : : /*
20 : : * Grace-period counter management.
21 : : */
22 : :
23 : : #define RCU_SEQ_CTR_SHIFT 2
24 : : #define RCU_SEQ_STATE_MASK ((1 << RCU_SEQ_CTR_SHIFT) - 1)
25 : :
26 : : /*
27 : : * Return the counter portion of a sequence number previously returned
28 : : * by rcu_seq_snap() or rcu_seq_current().
29 : : */
30 : 804 : static inline unsigned long rcu_seq_ctr(unsigned long s)
31 : : {
32 [ # # # # ]: 804 : return s >> RCU_SEQ_CTR_SHIFT;
33 : : }
34 : :
35 : : /*
36 : : * Return the state portion of a sequence number previously returned
37 : : * by rcu_seq_snap() or rcu_seq_current().
38 : : */
39 : 222530 : static inline int rcu_seq_state(unsigned long s)
40 : : {
41 [ - + - + : 156799 : return s & RCU_SEQ_STATE_MASK;
+ + - - +
+ + + + +
+ + - + +
- - + - -
+ + - + ]
42 : : }
43 : :
44 : : /*
45 : : * Set the state portion of the pointed-to sequence number.
46 : : * The caller is responsible for preventing conflicting updates.
47 : : */
48 : 804 : static inline void rcu_seq_set_state(unsigned long *sp, int newstate)
49 : : {
50 : 804 : WARN_ON_ONCE(newstate & ~RCU_SEQ_STATE_MASK);
51 [ + + ]: 804 : WRITE_ONCE(*sp, (*sp & ~RCU_SEQ_STATE_MASK) + newstate);
52 : 402 : }
53 : :
54 : : /* Adjust sequence number for start of update-side operation. */
55 : 21925 : static inline void rcu_seq_start(unsigned long *sp)
56 : : {
57 : 21925 : WRITE_ONCE(*sp, *sp + 1);
58 : 21925 : smp_mb(); /* Ensure update-side operation after counter increment. */
59 [ - - - + : 21925 : WARN_ON_ONCE(rcu_seq_state(*sp) != 1);
- + ]
60 : : }
61 : :
62 : : /* Compute the end-of-grace-period value for the specified sequence number. */
63 : 43404 : static inline unsigned long rcu_seq_endval(unsigned long *sp)
64 : : {
65 : 402 : return (*sp | RCU_SEQ_STATE_MASK) + 1;
66 : : }
67 : :
68 : : /* Adjust sequence number for end of update-side operation. */
69 : 43404 : static inline void rcu_seq_end(unsigned long *sp)
70 : : {
71 : 43404 : smp_mb(); /* Ensure update-side operation before counter increment. */
72 [ - - - + : 43404 : WARN_ON_ONCE(!rcu_seq_state(*sp));
- + - + ]
73 [ + + ]: 43404 : WRITE_ONCE(*sp, rcu_seq_endval(sp));
74 : : }
75 : :
76 : : /*
77 : : * rcu_seq_snap - Take a snapshot of the update side's sequence number.
78 : : *
79 : : * This function returns the earliest value of the grace-period sequence number
80 : : * that will indicate that a full grace period has elapsed since the current
81 : : * time. Once the grace-period sequence number has reached this value, it will
82 : : * be safe to invoke all callbacks that have been registered prior to the
83 : : * current time. This value is the current grace-period number plus two to the
84 : : * power of the number of low-order bits reserved for state, then rounded up to
85 : : * the next value in which the state bits are all zero.
86 : : */
87 : 70762 : static inline unsigned long rcu_seq_snap(unsigned long *sp)
88 : : {
89 : 70762 : unsigned long s;
90 : :
91 : 70762 : s = (READ_ONCE(*sp) + 2 * RCU_SEQ_STATE_MASK + 1) & ~RCU_SEQ_STATE_MASK;
92 : 70762 : smp_mb(); /* Above access must not bleed into critical section. */
93 [ + - ]: 70762 : return s;
94 : : }
95 : :
96 : : /* Return the current value the update side's sequence number, no ordering. */
97 : 295023 : static inline unsigned long rcu_seq_current(unsigned long *sp)
98 : : {
99 [ - + + + : 295023 : return READ_ONCE(*sp);
+ - - + +
+ + - - -
+ + - + -
+ + - - +
- - - - ]
100 : : }
101 : :
102 : : /*
103 : : * Given a snapshot from rcu_seq_snap(), determine whether or not the
104 : : * corresponding update-side operation has started.
105 : : */
106 : : static inline bool rcu_seq_started(unsigned long *sp, unsigned long s)
107 : : {
108 : : return ULONG_CMP_LT((s - 1) & ~RCU_SEQ_STATE_MASK, READ_ONCE(*sp));
109 : : }
110 : :
111 : : /*
112 : : * Given a snapshot from rcu_seq_snap(), determine whether or not a
113 : : * full update-side operation has occurred.
114 : : */
115 : 826 : static inline bool rcu_seq_done(unsigned long *sp, unsigned long s)
116 : : {
117 [ - - - + : 826 : return ULONG_CMP_GE(READ_ONCE(*sp), s);
+ - - - ]
118 : : }
119 : :
120 : : /*
121 : : * Has a grace period completed since the time the old gp_seq was collected?
122 : : */
123 : 42991 : static inline bool rcu_seq_completed_gp(unsigned long old, unsigned long new)
124 : : {
125 [ + + ]: 42991 : return ULONG_CMP_LT(old, new & ~RCU_SEQ_STATE_MASK);
126 : : }
127 : :
128 : : /*
129 : : * Has a grace period started since the time the old gp_seq was collected?
130 : : */
131 : 42991 : static inline bool rcu_seq_new_gp(unsigned long old, unsigned long new)
132 : : {
133 [ + + ]: 42991 : return ULONG_CMP_LT((old + RCU_SEQ_STATE_MASK) & ~RCU_SEQ_STATE_MASK,
134 : : new);
135 : : }
136 : :
137 : : /*
138 : : * Roughly how many full grace periods have elapsed between the collection
139 : : * of the two specified grace periods?
140 : : */
141 : : static inline unsigned long rcu_seq_diff(unsigned long new, unsigned long old)
142 : : {
143 : : unsigned long rnd_diff;
144 : :
145 : : if (old == new)
146 : : return 0;
147 : : /*
148 : : * Compute the number of grace periods (still shifted up), plus
149 : : * one if either of new and old is not an exact grace period.
150 : : */
151 : : rnd_diff = (new & ~RCU_SEQ_STATE_MASK) -
152 : : ((old + RCU_SEQ_STATE_MASK) & ~RCU_SEQ_STATE_MASK) +
153 : : ((new & RCU_SEQ_STATE_MASK) || (old & RCU_SEQ_STATE_MASK));
154 : : if (ULONG_CMP_GE(RCU_SEQ_STATE_MASK, rnd_diff))
155 : : return 1; /* Definitely no grace period has elapsed. */
156 : : return ((rnd_diff - RCU_SEQ_STATE_MASK - 1) >> RCU_SEQ_CTR_SHIFT) + 2;
157 : : }
158 : :
159 : : /*
160 : : * debug_rcu_head_queue()/debug_rcu_head_unqueue() are used internally
161 : : * by call_rcu() and rcu callback execution, and are therefore not part
162 : : * of the RCU API. These are in rcupdate.h because they are used by all
163 : : * RCU implementations.
164 : : */
165 : :
166 : : #ifdef CONFIG_DEBUG_OBJECTS_RCU_HEAD
167 : : # define STATE_RCU_HEAD_READY 0
168 : : # define STATE_RCU_HEAD_QUEUED 1
169 : :
170 : : extern struct debug_obj_descr rcuhead_debug_descr;
171 : :
172 : : static inline int debug_rcu_head_queue(struct rcu_head *head)
173 : : {
174 : : int r1;
175 : :
176 : : r1 = debug_object_activate(head, &rcuhead_debug_descr);
177 : : debug_object_active_state(head, &rcuhead_debug_descr,
178 : : STATE_RCU_HEAD_READY,
179 : : STATE_RCU_HEAD_QUEUED);
180 : : return r1;
181 : : }
182 : :
183 : : static inline void debug_rcu_head_unqueue(struct rcu_head *head)
184 : : {
185 : : debug_object_active_state(head, &rcuhead_debug_descr,
186 : : STATE_RCU_HEAD_QUEUED,
187 : : STATE_RCU_HEAD_READY);
188 : : debug_object_deactivate(head, &rcuhead_debug_descr);
189 : : }
190 : : #else /* !CONFIG_DEBUG_OBJECTS_RCU_HEAD */
191 : 796592 : static inline int debug_rcu_head_queue(struct rcu_head *head)
192 : : {
193 [ - + ]: 796592 : return 0;
194 : : }
195 : :
196 : 796025 : static inline void debug_rcu_head_unqueue(struct rcu_head *head)
197 : : {
198 : 796025 : }
199 : : #endif /* #else !CONFIG_DEBUG_OBJECTS_RCU_HEAD */
200 : :
201 : : #ifdef CONFIG_RCU_STALL_COMMON
202 : :
203 : : extern int rcu_cpu_stall_ftrace_dump;
204 : : extern int rcu_cpu_stall_suppress;
205 : : extern int rcu_cpu_stall_timeout;
206 : : int rcu_jiffies_till_stall_check(void);
207 : :
208 : : #define rcu_ftrace_dump_stall_suppress() \
209 : : do { \
210 : : if (!rcu_cpu_stall_suppress) \
211 : : rcu_cpu_stall_suppress = 3; \
212 : : } while (0)
213 : :
214 : : #define rcu_ftrace_dump_stall_unsuppress() \
215 : : do { \
216 : : if (rcu_cpu_stall_suppress == 3) \
217 : : rcu_cpu_stall_suppress = 0; \
218 : : } while (0)
219 : :
220 : : #else /* #endif #ifdef CONFIG_RCU_STALL_COMMON */
221 : : #define rcu_ftrace_dump_stall_suppress()
222 : : #define rcu_ftrace_dump_stall_unsuppress()
223 : : #endif /* #ifdef CONFIG_RCU_STALL_COMMON */
224 : :
225 : : /*
226 : : * Strings used in tracepoints need to be exported via the
227 : : * tracing system such that tools like perf and trace-cmd can
228 : : * translate the string address pointers to actual text.
229 : : */
230 : : #define TPS(x) tracepoint_string(x)
231 : :
232 : : /*
233 : : * Dump the ftrace buffer, but only one time per callsite per boot.
234 : : */
235 : : #define rcu_ftrace_dump(oops_dump_mode) \
236 : : do { \
237 : : static atomic_t ___rfd_beenhere = ATOMIC_INIT(0); \
238 : : \
239 : : if (!atomic_read(&___rfd_beenhere) && \
240 : : !atomic_xchg(&___rfd_beenhere, 1)) { \
241 : : tracing_off(); \
242 : : rcu_ftrace_dump_stall_suppress(); \
243 : : ftrace_dump(oops_dump_mode); \
244 : : rcu_ftrace_dump_stall_unsuppress(); \
245 : : } \
246 : : } while (0)
247 : :
248 : : void rcu_early_boot_tests(void);
249 : : void rcu_test_sync_prims(void);
250 : :
251 : : /*
252 : : * This function really isn't for public consumption, but RCU is special in
253 : : * that context switches can allow the state machine to make progress.
254 : : */
255 : : extern void resched_cpu(int cpu);
256 : :
257 : : #if defined(CONFIG_SRCU) || !defined(CONFIG_TINY_RCU)
258 : :
259 : : #include <linux/rcu_node_tree.h>
260 : :
261 : : extern int rcu_num_lvls;
262 : : extern int num_rcu_lvl[];
263 : : extern int rcu_num_nodes;
264 : : static bool rcu_fanout_exact;
265 : : static int rcu_fanout_leaf;
266 : :
267 : : /*
268 : : * Compute the per-level fanout, either using the exact fanout specified
269 : : * or balancing the tree, depending on the rcu_fanout_exact boot parameter.
270 : : */
271 : 66 : static inline void rcu_init_levelspread(int *levelspread, const int *levelcnt)
272 : : {
273 : 66 : int i;
274 : :
275 [ + + ]: 198 : for (i = 0; i < RCU_NUM_LVLS; i++)
276 : 132 : levelspread[i] = INT_MIN;
277 [ - + ]: 66 : if (rcu_fanout_exact) {
278 : 0 : levelspread[rcu_num_lvls - 1] = rcu_fanout_leaf;
279 [ # # ]: 0 : for (i = rcu_num_lvls - 2; i >= 0; i--)
280 : 0 : levelspread[i] = RCU_FANOUT;
281 : : } else {
282 : 66 : int ccur;
283 : 66 : int cprv;
284 : :
285 : 66 : cprv = nr_cpu_ids;
286 [ + + ]: 132 : for (i = rcu_num_lvls - 1; i >= 0; i--) {
287 : 66 : ccur = levelcnt[i];
288 : 66 : levelspread[i] = (cprv + ccur - 1) / ccur;
289 : 66 : cprv = ccur;
290 : : }
291 : : }
292 : 66 : }
293 : :
294 : : /* Returns a pointer to the first leaf rcu_node structure. */
295 : : #define rcu_first_leaf_node() (rcu_state.level[rcu_num_lvls - 1])
296 : :
297 : : /* Is this rcu_node a leaf? */
298 : : #define rcu_is_leaf_node(rnp) ((rnp)->level == rcu_num_lvls - 1)
299 : :
300 : : /* Is this rcu_node the last leaf? */
301 : : #define rcu_is_last_leaf_node(rnp) ((rnp) == &rcu_state.node[rcu_num_nodes - 1])
302 : :
303 : : /*
304 : : * Do a full breadth-first scan of the {s,}rcu_node structures for the
305 : : * specified state structure (for SRCU) or the only rcu_state structure
306 : : * (for RCU).
307 : : */
308 : : #define srcu_for_each_node_breadth_first(sp, rnp) \
309 : : for ((rnp) = &(sp)->node[0]; \
310 : : (rnp) < &(sp)->node[rcu_num_nodes]; (rnp)++)
311 : : #define rcu_for_each_node_breadth_first(rnp) \
312 : : srcu_for_each_node_breadth_first(&rcu_state, rnp)
313 : :
314 : : /*
315 : : * Scan the leaves of the rcu_node hierarchy for the rcu_state structure.
316 : : * Note that if there is a singleton rcu_node tree with but one rcu_node
317 : : * structure, this loop -will- visit the rcu_node structure. It is still
318 : : * a leaf node, even if it is also the root node.
319 : : */
320 : : #define rcu_for_each_leaf_node(rnp) \
321 : : for ((rnp) = rcu_first_leaf_node(); \
322 : : (rnp) < &rcu_state.node[rcu_num_nodes]; (rnp)++)
323 : :
324 : : /*
325 : : * Iterate over all possible CPUs in a leaf RCU node.
326 : : */
327 : : #define for_each_leaf_node_possible_cpu(rnp, cpu) \
328 : : for ((cpu) = cpumask_next((rnp)->grplo - 1, cpu_possible_mask); \
329 : : (cpu) <= rnp->grphi; \
330 : : (cpu) = cpumask_next((cpu), cpu_possible_mask))
331 : :
332 : : /*
333 : : * Iterate over all CPUs in a leaf RCU node's specified mask.
334 : : */
335 : : #define rcu_find_next_bit(rnp, cpu, mask) \
336 : : ((rnp)->grplo + find_next_bit(&(mask), BITS_PER_LONG, (cpu)))
337 : : #define for_each_leaf_node_cpu_mask(rnp, cpu, mask) \
338 : : for ((cpu) = rcu_find_next_bit((rnp), 0, (mask)); \
339 : : (cpu) <= rnp->grphi; \
340 : : (cpu) = rcu_find_next_bit((rnp), (cpu) + 1 - (rnp->grplo), (mask)))
341 : :
342 : : /*
343 : : * Wrappers for the rcu_node::lock acquire and release.
344 : : *
345 : : * Because the rcu_nodes form a tree, the tree traversal locking will observe
346 : : * different lock values, this in turn means that an UNLOCK of one level
347 : : * followed by a LOCK of another level does not imply a full memory barrier;
348 : : * and most importantly transitivity is lost.
349 : : *
350 : : * In order to restore full ordering between tree levels, augment the regular
351 : : * lock acquire functions with smp_mb__after_unlock_lock().
352 : : *
353 : : * As ->lock of struct rcu_node is a __private field, therefore one should use
354 : : * these wrappers rather than directly call raw_spin_{lock,unlock}* on ->lock.
355 : : */
356 : : #define raw_spin_lock_rcu_node(p) \
357 : : do { \
358 : : raw_spin_lock(&ACCESS_PRIVATE(p, lock)); \
359 : : smp_mb__after_unlock_lock(); \
360 : : } while (0)
361 : :
362 : : #define raw_spin_unlock_rcu_node(p) raw_spin_unlock(&ACCESS_PRIVATE(p, lock))
363 : :
364 : : #define raw_spin_lock_irq_rcu_node(p) \
365 : : do { \
366 : : raw_spin_lock_irq(&ACCESS_PRIVATE(p, lock)); \
367 : : smp_mb__after_unlock_lock(); \
368 : : } while (0)
369 : :
370 : : #define raw_spin_unlock_irq_rcu_node(p) \
371 : : raw_spin_unlock_irq(&ACCESS_PRIVATE(p, lock))
372 : :
373 : : #define raw_spin_lock_irqsave_rcu_node(p, flags) \
374 : : do { \
375 : : raw_spin_lock_irqsave(&ACCESS_PRIVATE(p, lock), flags); \
376 : : smp_mb__after_unlock_lock(); \
377 : : } while (0)
378 : :
379 : : #define raw_spin_unlock_irqrestore_rcu_node(p, flags) \
380 : : raw_spin_unlock_irqrestore(&ACCESS_PRIVATE(p, lock), flags)
381 : :
382 : : #define raw_spin_trylock_rcu_node(p) \
383 : : ({ \
384 : : bool ___locked = raw_spin_trylock(&ACCESS_PRIVATE(p, lock)); \
385 : : \
386 : : if (___locked) \
387 : : smp_mb__after_unlock_lock(); \
388 : : ___locked; \
389 : : })
390 : :
391 : : #define raw_lockdep_assert_held_rcu_node(p) \
392 : : lockdep_assert_held(&ACCESS_PRIVATE(p, lock))
393 : :
394 : : #endif /* #if defined(CONFIG_SRCU) || !defined(CONFIG_TINY_RCU) */
395 : :
396 : : #ifdef CONFIG_SRCU
397 : : void srcu_init(void);
398 : : #else /* #ifdef CONFIG_SRCU */
399 : : static inline void srcu_init(void) { }
400 : : #endif /* #else #ifdef CONFIG_SRCU */
401 : :
402 : : #ifdef CONFIG_TINY_RCU
403 : : /* Tiny RCU doesn't expedite, as its purpose in life is instead to be tiny. */
404 : : static inline bool rcu_gp_is_normal(void) { return true; }
405 : : static inline bool rcu_gp_is_expedited(void) { return false; }
406 : : static inline void rcu_expedite_gp(void) { }
407 : : static inline void rcu_unexpedite_gp(void) { }
408 : : static inline void rcu_request_urgent_qs_task(struct task_struct *t) { }
409 : : #else /* #ifdef CONFIG_TINY_RCU */
410 : : bool rcu_gp_is_normal(void); /* Internal RCU use. */
411 : : bool rcu_gp_is_expedited(void); /* Internal RCU use. */
412 : : void rcu_expedite_gp(void);
413 : : void rcu_unexpedite_gp(void);
414 : : void rcupdate_announce_bootup_oddness(void);
415 : : void rcu_request_urgent_qs_task(struct task_struct *t);
416 : : #endif /* #else #ifdef CONFIG_TINY_RCU */
417 : :
418 : : #define RCU_SCHEDULER_INACTIVE 0
419 : : #define RCU_SCHEDULER_INIT 1
420 : : #define RCU_SCHEDULER_RUNNING 2
421 : :
422 : : enum rcutorture_type {
423 : : RCU_FLAVOR,
424 : : RCU_TASKS_FLAVOR,
425 : : RCU_TRIVIAL_FLAVOR,
426 : : SRCU_FLAVOR,
427 : : INVALID_RCU_FLAVOR
428 : : };
429 : :
430 : : #if defined(CONFIG_TREE_RCU)
431 : : void rcutorture_get_gp_data(enum rcutorture_type test_type, int *flags,
432 : : unsigned long *gp_seq);
433 : : void do_trace_rcu_torture_read(const char *rcutorturename,
434 : : struct rcu_head *rhp,
435 : : unsigned long secs,
436 : : unsigned long c_old,
437 : : unsigned long c);
438 : : #else
439 : : static inline void rcutorture_get_gp_data(enum rcutorture_type test_type,
440 : : int *flags, unsigned long *gp_seq)
441 : : {
442 : : *flags = 0;
443 : : *gp_seq = 0;
444 : : }
445 : : #ifdef CONFIG_RCU_TRACE
446 : : void do_trace_rcu_torture_read(const char *rcutorturename,
447 : : struct rcu_head *rhp,
448 : : unsigned long secs,
449 : : unsigned long c_old,
450 : : unsigned long c);
451 : : #else
452 : : #define do_trace_rcu_torture_read(rcutorturename, rhp, secs, c_old, c) \
453 : : do { } while (0)
454 : : #endif
455 : : #endif
456 : :
457 : : #if IS_ENABLED(CONFIG_RCU_TORTURE_TEST) || IS_MODULE(CONFIG_RCU_TORTURE_TEST)
458 : : long rcutorture_sched_setaffinity(pid_t pid, const struct cpumask *in_mask);
459 : : #endif
460 : :
461 : : #ifdef CONFIG_TINY_SRCU
462 : :
463 : : static inline void srcutorture_get_gp_data(enum rcutorture_type test_type,
464 : : struct srcu_struct *sp, int *flags,
465 : : unsigned long *gp_seq)
466 : : {
467 : : if (test_type != SRCU_FLAVOR)
468 : : return;
469 : : *flags = 0;
470 : : *gp_seq = sp->srcu_idx;
471 : : }
472 : :
473 : : #elif defined(CONFIG_TREE_SRCU)
474 : :
475 : : void srcutorture_get_gp_data(enum rcutorture_type test_type,
476 : : struct srcu_struct *sp, int *flags,
477 : : unsigned long *gp_seq);
478 : :
479 : : #endif
480 : :
481 : : #ifdef CONFIG_TINY_RCU
482 : : static inline unsigned long rcu_get_gp_seq(void) { return 0; }
483 : : static inline unsigned long rcu_exp_batches_completed(void) { return 0; }
484 : : static inline unsigned long
485 : : srcu_batches_completed(struct srcu_struct *sp) { return 0; }
486 : : static inline void rcu_force_quiescent_state(void) { }
487 : : static inline void show_rcu_gp_kthreads(void) { }
488 : : static inline int rcu_get_gp_kthreads_prio(void) { return 0; }
489 : : static inline void rcu_fwd_progress_check(unsigned long j) { }
490 : : #else /* #ifdef CONFIG_TINY_RCU */
491 : : unsigned long rcu_get_gp_seq(void);
492 : : unsigned long rcu_exp_batches_completed(void);
493 : : unsigned long srcu_batches_completed(struct srcu_struct *sp);
494 : : void show_rcu_gp_kthreads(void);
495 : : int rcu_get_gp_kthreads_prio(void);
496 : : void rcu_fwd_progress_check(unsigned long j);
497 : : void rcu_force_quiescent_state(void);
498 : : extern struct workqueue_struct *rcu_gp_wq;
499 : : extern struct workqueue_struct *rcu_par_gp_wq;
500 : : #endif /* #else #ifdef CONFIG_TINY_RCU */
501 : :
502 : : #ifdef CONFIG_RCU_NOCB_CPU
503 : : bool rcu_is_nocb_cpu(int cpu);
504 : : void rcu_bind_current_to_nocb(void);
505 : : #else
506 : : static inline bool rcu_is_nocb_cpu(int cpu) { return false; }
507 : : static inline void rcu_bind_current_to_nocb(void) { }
508 : : #endif
509 : :
510 : : #endif /* __LINUX_RCU_H */
|
