1 /* SPDX-License-Identifier: GPL-2.0+ */ 1
2 /*
3 * Read-Copy Update mechanism for mutual exclu
4 * Internal non-public definitions.
5 *
6 * Copyright IBM Corporation, 2008
7 *
8 * Author: Ingo Molnar <mingo@elte.hu>
9 * Paul E. McKenney <paulmck@linux.ibm
10 */
11
12 #include <linux/cache.h>
13 #include <linux/kthread.h>
14 #include <linux/spinlock.h>
15 #include <linux/rtmutex.h>
16 #include <linux/threads.h>
17 #include <linux/cpumask.h>
18 #include <linux/seqlock.h>
19 #include <linux/swait.h>
20 #include <linux/rcu_node_tree.h>
21
22 #include "rcu_segcblist.h"
23
24 /* Communicate arguments to a kthread worker h
25 struct rcu_exp_work {
26 unsigned long rew_s;
27 struct kthread_work rew_work;
28 };
29
30 /* RCU's kthread states for tracing. */
31 #define RCU_KTHREAD_STOPPED 0
32 #define RCU_KTHREAD_RUNNING 1
33 #define RCU_KTHREAD_WAITING 2
34 #define RCU_KTHREAD_OFFCPU 3
35 #define RCU_KTHREAD_YIELDING 4
36 #define RCU_KTHREAD_MAX 4
37
38 /*
39 * Definition for node within the RCU grace-pe
40 */
41 struct rcu_node {
42 raw_spinlock_t __private lock; /* Roo
43 /* so
44 /* fo
45 unsigned long gp_seq; /* Track rsp->
46 unsigned long gp_seq_needed; /* Track
47 unsigned long completedqs; /* All QSes
48 unsigned long qsmask; /* CPUs or gro
49 /* order for
50 /* In leaf rc
51 /* an rcu_dat
52 /* bit corres
53 /* structure.
54 unsigned long rcu_gp_init_mask; /* Mas
55 unsigned long qsmaskinit;
56 /* Per-GP init
57 /* Initialize
58 /* beginning
59 unsigned long qsmaskinitnext;
60 unsigned long expmask; /* CPUs or gro
61 /* to allow t
62 /* to complet
63 unsigned long expmaskinit;
64 /* Per-GP init
65 /* Initialize
66 /* beginning
67 unsigned long expmaskinitnext;
68 /* Online CPUs
69 /* Any CPU th
70 /* have its b
71 struct kthread_worker *exp_kworker;
72 /* Workers per
73 /* initializat
74 unsigned long cbovldmask;
75 /* CPUs experi
76 unsigned long ffmask; /* Fully funct
77 unsigned long grpmask; /* Mask to app
78 /* Only one b
79 int grplo; /* lowest-numb
80 int grphi; /* highest-num
81 u8 grpnum; /* group numbe
82 u8 level; /* root is at
83 bool wait_blkd_tasks;/* Necessary t
84 /* exit RCU r
85 /* before pro
86 /* rcu_node t
87 struct rcu_node *parent;
88 struct list_head blkd_tasks;
89 /* Tasks block
90 /* section.
91 /* of this li
92 struct list_head *gp_tasks;
93 /* Pointer to
94 /* current gr
95 /* is no such
96 struct list_head *exp_tasks;
97 /* Pointer to
98 /* current ex
99 /* if there i
100 /* is no curr
101 /* then there
102 struct list_head *boost_tasks;
103 /* Pointer to
104 /* priority b
105 /* boosting i
106 /* structure.
107 /* queued on
108 /* are blocki
109 /* there can
110 struct rt_mutex boost_mtx;
111 /* Used only f
112 /* side effec
113 unsigned long boost_time;
114 /* When to sta
115 struct mutex kthread_mutex;
116 /* Exclusion f
117 /* manipulati
118 struct task_struct *boost_kthread_task
119 /* kthread tha
120 /* boosting f
121 unsigned int boost_kthread_status;
122 /* State of bo
123 unsigned long n_boosts; /* Number of b
124 #ifdef CONFIG_RCU_NOCB_CPU
125 struct swait_queue_head nocb_gp_wq[2];
126 /* Place for r
127 #endif /* #ifdef CONFIG_RCU_NOCB_CPU */
128 raw_spinlock_t fqslock ____cacheline_i
129
130 spinlock_t exp_lock ____cacheline_inte
131 unsigned long exp_seq_rq;
132 wait_queue_head_t exp_wq[4];
133 struct rcu_exp_work rew;
134 bool exp_need_flush; /* Need to flu
135 raw_spinlock_t exp_poll_lock;
136 /* Lock and da
137 unsigned long exp_seq_poll_rq;
138 struct work_struct exp_poll_wq;
139 } ____cacheline_internodealigned_in_smp;
140
141 /*
142 * Bitmasks in an rcu_node cover the interval
143 * are indexed relative to this interval rathe
144 * This generates the bit for a CPU in node-lo
145 */
146 #define leaf_node_cpu_bit(rnp, cpu) (BIT((cpu)
147
148 /*
149 * Union to allow "aggregate OR" operation on
150 * state by the normal and expedited grace per
151 */
152 union rcu_noqs {
153 struct {
154 u8 norm;
155 u8 exp;
156 } b; /* Bits. */
157 u16 s; /* Set of bits, aggregate OR he
158 };
159
160 /*
161 * Record the snapshot of the core stats at ha
162 * The member gp_seq is used to ensure that al
163 * during the sampling period. The snapshot is
164 * equal to rdp->gp_seq.
165 */
166 struct rcu_snap_record {
167 unsigned long gp_seq; /* Tra
168 u64 cputime_irq; /* Acc
169 u64 cputime_softirq;/* Acc
170 u64 cputime_system; /* Acc
171 unsigned long nr_hardirqs; /* Acc
172 unsigned int nr_softirqs; /* Acc
173 unsigned long long nr_csw; /* Acc
174 unsigned long jiffies; /* Tra
175 };
176
177 /* Per-CPU data for read-copy update. */
178 struct rcu_data {
179 /* 1) quiescent-state and grace-period
180 unsigned long gp_seq; /* Tra
181 unsigned long gp_seq_needed; /* Tra
182 union rcu_noqs cpu_no_qs; /* No
183 bool core_needs_qs; /* Cor
184 bool beenonline; /* CPU
185 bool gpwrap; /* Pos
186 bool cpu_started; /* RCU
187 struct rcu_node *mynode; /* Thi
188 unsigned long grpmask; /* Mas
189 unsigned long ticks_this_gp; /* The
190 /* ti
191 /* du
192 /* per
193 struct irq_work defer_qs_iw; /* Obt
194 bool defer_qs_iw_pending; /* Sch
195 struct work_struct strict_work; /* Sch
196
197 /* 2) batch handling */
198 struct rcu_segcblist cblist; /* Seg
199 /* dif
200 /* dif
201 long qlen_last_fqs_check;
202 /* qle
203 unsigned long n_cbs_invoked; /* # c
204 unsigned long n_force_qs_snap;
205 /* did
206 long blimit; /* Upp
207
208 /* 3) dynticks interface. */
209 int watching_snap; /* Per
210 bool rcu_need_heavy_qs; /* GP
211 bool rcu_urgent_qs; /* GP
212 bool rcu_forced_tick; /* For
213 bool rcu_forced_tick_exp; /* .
214
215 /* 4) rcu_barrier(), OOM callbacks, an
216 unsigned long barrier_seq_snap; /* Sna
217 struct rcu_head barrier_head;
218 int exp_watching_snap; /* Dou
219
220 /* 5) Callback offloading. */
221 #ifdef CONFIG_RCU_NOCB_CPU
222 struct swait_queue_head nocb_cb_wq; /*
223 struct swait_queue_head nocb_state_wq;
224 struct task_struct *nocb_gp_kthread;
225 raw_spinlock_t nocb_lock; /* Gua
226 int nocb_defer_wakeup; /* Def
227 struct timer_list nocb_timer; /* Enf
228 unsigned long nocb_gp_adv_time; /* Las
229 struct mutex nocb_gp_kthread_mutex; /*
230 /*
231
232 /* The following fields are used by ca
233 raw_spinlock_t nocb_bypass_lock ____ca
234 struct rcu_cblist nocb_bypass; /* Loc
235 unsigned long nocb_bypass_first; /* Ti
236 unsigned long nocb_nobypass_last; /* L
237 int nocb_nobypass_count; /* # -
238
239 /* The following fields are used by GP
240 raw_spinlock_t nocb_gp_lock ____cachel
241 u8 nocb_gp_sleep; /* Is
242 u8 nocb_gp_bypass; /* Fou
243 u8 nocb_gp_gp; /* GP
244 unsigned long nocb_gp_seq; /* If
245 unsigned long nocb_gp_loops; /* # p
246 struct swait_queue_head nocb_gp_wq; /*
247 bool nocb_cb_sleep; /* Is
248 struct task_struct *nocb_cb_kthread;
249 struct list_head nocb_head_rdp; /*
250 * Hea
251 * if
252 */
253 struct list_head nocb_entry_rdp; /* rc
254 struct rcu_data *nocb_toggling_rdp; /*
255
256 /* The following fields are used by CB
257 struct rcu_data *nocb_gp_rdp ____cache
258 /* GP
259 #endif /* #ifdef CONFIG_RCU_NOCB_CPU */
260
261 /* 6) RCU priority boosting. */
262 struct task_struct *rcu_cpu_kthread_ta
263 /* rcu
264 unsigned int rcu_cpu_kthread_status;
265 char rcu_cpu_has_work;
266 unsigned long rcuc_activity;
267
268 /* 7) Diagnostic data, including RCU C
269 unsigned int softirq_snap; /* Sna
270 /* ->rcu_iw* fields protected by leaf
271 struct irq_work rcu_iw; /* Che
272 bool rcu_iw_pending; /* Is
273 unsigned long rcu_iw_gp_seq; /* ->g
274 unsigned long rcu_ofl_gp_seq; /* ->g
275 short rcu_ofl_gp_state; /* ->g
276 unsigned long rcu_onl_gp_seq; /* ->g
277 short rcu_onl_gp_state; /* ->g
278 unsigned long last_fqs_resched; /* Tim
279 unsigned long last_sched_clock; /* Jif
280 struct rcu_snap_record snap_record; /*
281 /*
282
283 long lazy_len; /* Len
284 int cpu;
285 };
286
287 /* Values for nocb_defer_wakeup field in struc
288 #define RCU_NOCB_WAKE_NOT 0
289 #define RCU_NOCB_WAKE_BYPASS 1
290 #define RCU_NOCB_WAKE_LAZY 2
291 #define RCU_NOCB_WAKE 3
292 #define RCU_NOCB_WAKE_FORCE 4
293
294 #define RCU_JIFFIES_TILL_FORCE_QS (1 + (HZ > 2
295 /* For
296 /* an
297
298 #define RCU_JIFFIES_FQS_DIV 256 /* Ver
299 /* de
300 /* qu
301
302 #define RCU_STALL_RAT_DELAY 2 /* All
303 /* at
304 /* ir
305
306 #define rcu_wait(cond)
307 do {
308 for (;;) {
309 set_current_state(TASK_INTERRU
310 if (cond)
311 break;
312 schedule();
313 }
314 __set_current_state(TASK_RUNNING);
315 } while (0)
316
317 /*
318 * A max threshold for synchronize_rcu() users
319 * awaken directly by the rcu_gp_kthread(). Le
320 * deferred to the main worker.
321 */
322 #define SR_MAX_USERS_WAKE_FROM_GP 5
323 #define SR_NORMAL_GP_WAIT_HEAD_MAX 5
324
325 struct sr_wait_node {
326 atomic_t inuse;
327 struct llist_node node;
328 };
329
330 /*
331 * RCU global state, including node hierarchy.
332 * represented in "heap" form in a dense array
333 * of the hierarchy is in ->node[0] (reference
334 * level in ->node[1] through ->node[m] (->nod
335 * and the third level in ->node[m+1] and foll
336 * by ->level[2]). The number of levels is de
337 * CPUs and by CONFIG_RCU_FANOUT. Small syste
338 * consisting of a single rcu_node.
339 */
340 struct rcu_state {
341 struct rcu_node node[NUM_RCU_NODES];
342 struct rcu_node *level[RCU_NUM_LVLS +
343
344
345 int ncpus;
346 int n_online_cpus;
347
348 /* The following fields are guarded by
349
350 unsigned long gp_seq ____cacheline_int
351
352 unsigned long gp_max;
353
354 struct task_struct *gp_kthread;
355 struct swait_queue_head gp_wq;
356 short gp_flags;
357 short gp_state;
358 unsigned long gp_wake_time;
359 unsigned long gp_wake_seq;
360 unsigned long gp_seq_polled;
361 unsigned long gp_seq_polled_snap;
362 unsigned long gp_seq_polled_exp_snap;
363
364 /* End of fields guarded by root rcu_n
365
366 struct mutex barrier_mutex;
367 atomic_t barrier_cpu_count;
368 struct completion barrier_completion;
369 unsigned long barrier_sequence;
370
371 /* End of fields guarded by barrier_mu
372
373 raw_spinlock_t barrier_lock;
374
375 struct mutex exp_mutex;
376 struct mutex exp_wake_mutex;
377 unsigned long expedited_sequence;
378 atomic_t expedited_need_qs;
379 struct swait_queue_head expedited_wq;
380 int ncpus_snap;
381 u8 cbovld;
382 u8 cbovldnext;
383
384 unsigned long jiffies_force_qs;
385
386 unsigned long jiffies_kick_kthreads;
387
388 unsigned long n_force_qs;
389
390 unsigned long gp_start;
391
392 unsigned long gp_end;
393
394 unsigned long gp_activity;
395
396 unsigned long gp_req_activity;
397
398 unsigned long jiffies_stall;
399
400 int nr_fqs_jiffies_stall;
401
402
403
404 unsigned long jiffies_resched;
405
406 unsigned long n_force_qs_gpstart;
407
408 const char *name;
409 char abbr;
410
411 arch_spinlock_t ofl_lock ____cacheline
412
413
414
415 /* synchronize_rcu() part. */
416 struct llist_head srs_next; /* req
417 struct llist_node *srs_wait_tail; /* w
418 struct llist_node *srs_done_tail; /* r
419 struct sr_wait_node srs_wait_nodes[SR_
420 struct work_struct srs_cleanup_work;
421 atomic_t srs_cleanups_pending; /* srs
422
423 #ifdef CONFIG_RCU_NOCB_CPU
424 struct mutex nocb_mutex;
425 int nocb_is_setup;
426 #endif
427 };
428
429 /* Values for rcu_state structure's gp_flags f
430 #define RCU_GP_FLAG_INIT 0x1 /* Need grace-
431 #define RCU_GP_FLAG_FQS 0x2 /* Need grace-
432 #define RCU_GP_FLAG_OVLD 0x4 /* Experiencin
433
434 /* Values for rcu_state structure's gp_state f
435 #define RCU_GP_IDLE 0 /* Initial sta
436 #define RCU_GP_WAIT_GPS 1 /* Wait for gr
437 #define RCU_GP_DONE_GPS 2 /* Wait done f
438 #define RCU_GP_ONOFF 3 /* Grace-perio
439 #define RCU_GP_INIT 4 /* Grace-perio
440 #define RCU_GP_WAIT_FQS 5 /* Wait for fo
441 #define RCU_GP_DOING_FQS 6 /* Wait done f
442 #define RCU_GP_CLEANUP 7 /* Grace-perio
443 #define RCU_GP_CLEANED 8 /* Grace-perio
444
445 /*
446 * In order to export the rcu_state name to th
447 * needs to be added in the __tracepoint_strin
448 * This requires defining a separate variable
449 * that points to the string being used, and t
450 * the tracing userspace tools to be able to d
451 * address to the matching string.
452 */
453 #ifdef CONFIG_PREEMPT_RCU
454 #define RCU_ABBR 'p'
455 #define RCU_NAME_RAW "rcu_preempt"
456 #else /* #ifdef CONFIG_PREEMPT_RCU */
457 #define RCU_ABBR 's'
458 #define RCU_NAME_RAW "rcu_sched"
459 #endif /* #else #ifdef CONFIG_PREEMPT_RCU */
460 #ifndef CONFIG_TRACING
461 #define RCU_NAME RCU_NAME_RAW
462 #else /* #ifdef CONFIG_TRACING */
463 static char rcu_name[] = RCU_NAME_RAW;
464 static const char *tp_rcu_varname __used __tra
465 #define RCU_NAME rcu_name
466 #endif /* #else #ifdef CONFIG_TRACING */
467
468 /* Forward declarations for tree_plugin.h */
469 static void rcu_bootup_announce(void);
470 static void rcu_qs(void);
471 static int rcu_preempt_blocked_readers_cgp(str
472 #ifdef CONFIG_HOTPLUG_CPU
473 static bool rcu_preempt_has_tasks(struct rcu_n
474 #endif /* #ifdef CONFIG_HOTPLUG_CPU */
475 static int rcu_print_task_exp_stall(struct rcu
476 static void rcu_preempt_check_blocked_tasks(st
477 static void rcu_flavor_sched_clock_irq(int use
478 static void dump_blkd_tasks(struct rcu_node *r
479 static void rcu_initiate_boost(struct rcu_node
480 static void rcu_preempt_boost_start_gp(struct
481 static bool rcu_is_callbacks_kthread(struct rc
482 static void rcu_cpu_kthread_setup(unsigned int
483 static void rcu_spawn_one_boost_kthread(struct
484 static bool rcu_preempt_has_tasks(struct rcu_n
485 static bool rcu_preempt_need_deferred_qs(struc
486 static void zero_cpu_stall_ticks(struct rcu_da
487 static struct swait_queue_head *rcu_nocb_gp_ge
488 static void rcu_nocb_gp_cleanup(struct swait_q
489 static void rcu_init_one_nocb(struct rcu_node
490 static bool wake_nocb_gp(struct rcu_data *rdp,
491 static bool rcu_nocb_flush_bypass(struct rcu_d
492 unsigned lon
493 static void call_rcu_nocb(struct rcu_data *rdp
494 rcu_callback_t func,
495 static void __maybe_unused __call_rcu_nocb_wak
496
497 static int rcu_nocb_need_deferred_wakeup(struc
498 static bool do_nocb_deferred_wakeup(struct rcu
499 static void rcu_boot_init_nocb_percpu_data(str
500 static void rcu_spawn_cpu_nocb_kthread(int cpu
501 static void show_rcu_nocb_state(struct rcu_dat
502 static void rcu_nocb_lock(struct rcu_data *rdp
503 static void rcu_nocb_unlock(struct rcu_data *r
504 static void rcu_nocb_unlock_irqrestore(struct
505 unsigne
506 static void rcu_lockdep_assert_cblist_protecte
507 #ifdef CONFIG_RCU_NOCB_CPU
508 static void __init rcu_organize_nocb_kthreads(
509
510 /*
511 * Disable IRQs before checking offloaded stat
512 * locking is safe against concurrent de-offlo
513 */
514 #define rcu_nocb_lock_irqsave(rdp, flags)
515 do {
516 local_irq_save(flags);
517 if (rcu_segcblist_is_offloaded(&(rdp)-
518 raw_spin_lock(&(rdp)->nocb_loc
519 } while (0)
520 #else /* #ifdef CONFIG_RCU_NOCB_CPU */
521 #define rcu_nocb_lock_irqsave(rdp, flags) loca
522 #endif /* #else #ifdef CONFIG_RCU_NOCB_CPU */
523
524 static void rcu_bind_gp_kthread(void);
525 static bool rcu_nohz_full_cpu(void);
526
527 /* Forward declarations for tree_stall.h */
528 static void record_gp_stall_check_time(void);
529 static void rcu_iw_handler(struct irq_work *iw
530 static void check_cpu_stall(struct rcu_data *r
531 static void rcu_check_gp_start_stall(struct rc
532 const uns
533
534 /* Forward declarations for tree_exp.h. */
535 static void sync_rcu_do_polled_gp(struct work_
536
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.