1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25#include <linux/cache.h>
26#include <linux/spinlock.h>
27#include <linux/threads.h>
28#include <linux/cpumask.h>
29#include <linux/seqlock.h>
30#include <linux/irq_work.h>
31
32
33
34
35
36
37
38
39#define MAX_RCU_LVLS 4
40#define RCU_FANOUT_1 (CONFIG_RCU_FANOUT_LEAF)
41#define RCU_FANOUT_2 (RCU_FANOUT_1 * CONFIG_RCU_FANOUT)
42#define RCU_FANOUT_3 (RCU_FANOUT_2 * CONFIG_RCU_FANOUT)
43#define RCU_FANOUT_4 (RCU_FANOUT_3 * CONFIG_RCU_FANOUT)
44
45#if NR_CPUS <= RCU_FANOUT_1
46# define RCU_NUM_LVLS 1
47# define NUM_RCU_LVL_0 1
48# define NUM_RCU_LVL_1 (NR_CPUS)
49# define NUM_RCU_LVL_2 0
50# define NUM_RCU_LVL_3 0
51# define NUM_RCU_LVL_4 0
52#elif NR_CPUS <= RCU_FANOUT_2
53# define RCU_NUM_LVLS 2
54# define NUM_RCU_LVL_0 1
55# define NUM_RCU_LVL_1 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_1)
56# define NUM_RCU_LVL_2 (NR_CPUS)
57# define NUM_RCU_LVL_3 0
58# define NUM_RCU_LVL_4 0
59#elif NR_CPUS <= RCU_FANOUT_3
60# define RCU_NUM_LVLS 3
61# define NUM_RCU_LVL_0 1
62# define NUM_RCU_LVL_1 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_2)
63# define NUM_RCU_LVL_2 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_1)
64# define NUM_RCU_LVL_3 (NR_CPUS)
65# define NUM_RCU_LVL_4 0
66#elif NR_CPUS <= RCU_FANOUT_4
67# define RCU_NUM_LVLS 4
68# define NUM_RCU_LVL_0 1
69# define NUM_RCU_LVL_1 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_3)
70# define NUM_RCU_LVL_2 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_2)
71# define NUM_RCU_LVL_3 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_1)
72# define NUM_RCU_LVL_4 (NR_CPUS)
73#else
74# error "CONFIG_RCU_FANOUT insufficient for NR_CPUS"
75#endif
76
77#define RCU_SUM (NUM_RCU_LVL_0 + NUM_RCU_LVL_1 + NUM_RCU_LVL_2 + NUM_RCU_LVL_3 + NUM_RCU_LVL_4)
78#define NUM_RCU_NODES (RCU_SUM - NR_CPUS)
79
80extern int rcu_num_lvls;
81extern int rcu_num_nodes;
82
83
84
85
86struct rcu_dynticks {
87 long long dynticks_nesting;
88
89 int dynticks_nmi_nesting;
90 atomic_t dynticks;
91#ifdef CONFIG_RCU_FAST_NO_HZ
92 bool all_lazy;
93 unsigned long nonlazy_posted;
94
95 unsigned long nonlazy_posted_snap;
96
97 unsigned long last_accelerate;
98
99 int tick_nohz_enabled_snap;
100#endif
101};
102
103
104#define RCU_KTHREAD_STOPPED 0
105#define RCU_KTHREAD_RUNNING 1
106#define RCU_KTHREAD_WAITING 2
107#define RCU_KTHREAD_OFFCPU 3
108#define RCU_KTHREAD_YIELDING 4
109#define RCU_KTHREAD_MAX 4
110
111
112
113
114struct rcu_node {
115 raw_spinlock_t lock;
116
117 unsigned long gpnum;
118
119
120 unsigned long completed;
121
122
123 unsigned long qsmask;
124
125
126
127
128
129 unsigned long expmask;
130
131
132
133 unsigned long qsmaskinit;
134
135 unsigned long grpmask;
136
137 int grplo;
138 int grphi;
139 u8 grpnum;
140 u8 level;
141 struct rcu_node *parent;
142 struct list_head blkd_tasks;
143
144
145
146 struct list_head *gp_tasks;
147
148
149
150 struct list_head *exp_tasks;
151
152
153
154
155
156#ifdef CONFIG_RCU_BOOST
157 struct list_head *boost_tasks;
158
159
160
161
162
163
164
165 unsigned long boost_time;
166
167 struct task_struct *boost_kthread_task;
168
169
170 unsigned int boost_kthread_status;
171
172 unsigned long n_tasks_boosted;
173
174 unsigned long n_exp_boosts;
175
176 unsigned long n_normal_boosts;
177
178 unsigned long n_balk_blkd_tasks;
179
180 unsigned long n_balk_exp_gp_tasks;
181
182 unsigned long n_balk_boost_tasks;
183
184 unsigned long n_balk_notblocked;
185
186 unsigned long n_balk_notyet;
187
188 unsigned long n_balk_nos;
189
190
191#endif
192#ifdef CONFIG_RCU_NOCB_CPU
193 wait_queue_head_t nocb_gp_wq[2];
194
195#endif
196 int need_future_gp[2];
197
198 raw_spinlock_t fqslock ____cacheline_internodealigned_in_smp;
199} ____cacheline_internodealigned_in_smp;
200
201
202
203
204
205#define rcu_for_each_node_breadth_first(rsp, rnp) \
206 for ((rnp) = &(rsp)->node[0]; \
207 (rnp) < &(rsp)->node[rcu_num_nodes]; (rnp)++)
208
209
210
211
212
213
214#define rcu_for_each_nonleaf_node_breadth_first(rsp, rnp) \
215 for ((rnp) = &(rsp)->node[0]; \
216 (rnp) < (rsp)->level[rcu_num_lvls - 1]; (rnp)++)
217
218
219
220
221
222
223
224#define rcu_for_each_leaf_node(rsp, rnp) \
225 for ((rnp) = (rsp)->level[rcu_num_lvls - 1]; \
226 (rnp) < &(rsp)->node[rcu_num_nodes]; (rnp)++)
227
228
229#define RCU_DONE_TAIL 0
230#define RCU_WAIT_TAIL 1
231#define RCU_NEXT_READY_TAIL 2
232#define RCU_NEXT_TAIL 3
233#define RCU_NEXT_SIZE 4
234
235
236struct rcu_data {
237
238 unsigned long completed;
239
240 unsigned long gpnum;
241
242 bool passed_quiesce;
243 bool qs_pending;
244 bool beenonline;
245 bool preemptible;
246 struct rcu_node *mynode;
247 unsigned long grpmask;
248#ifdef CONFIG_RCU_CPU_STALL_INFO
249 unsigned long ticks_this_gp;
250
251
252
253#endif
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278 struct rcu_head *nxtlist;
279 struct rcu_head **nxttail[RCU_NEXT_SIZE];
280 unsigned long nxtcompleted[RCU_NEXT_SIZE];
281
282 long qlen_lazy;
283 long qlen;
284 long qlen_last_fqs_check;
285
286 unsigned long n_cbs_invoked;
287 unsigned long n_nocbs_invoked;
288 unsigned long n_cbs_orphaned;
289 unsigned long n_cbs_adopted;
290 unsigned long n_force_qs_snap;
291
292 long blimit;
293
294
295 struct rcu_dynticks *dynticks;
296 int dynticks_snap;
297
298
299 unsigned long dynticks_fqs;
300 unsigned long offline_fqs;
301
302
303 unsigned long n_rcu_pending;
304 unsigned long n_rp_qs_pending;
305 unsigned long n_rp_report_qs;
306 unsigned long n_rp_cb_ready;
307 unsigned long n_rp_cpu_needs_gp;
308 unsigned long n_rp_gp_completed;
309 unsigned long n_rp_gp_started;
310 unsigned long n_rp_need_nothing;
311
312
313 struct rcu_head barrier_head;
314#ifdef CONFIG_RCU_FAST_NO_HZ
315 struct rcu_head oom_head;
316#endif
317
318
319#ifdef CONFIG_RCU_NOCB_CPU
320 struct rcu_head *nocb_head;
321 struct rcu_head **nocb_tail;
322 atomic_long_t nocb_q_count;
323 atomic_long_t nocb_q_count_lazy;
324 int nocb_p_count;
325 int nocb_p_count_lazy;
326 wait_queue_head_t nocb_wq;
327 struct task_struct *nocb_kthread;
328#endif
329
330
331#ifdef CONFIG_RCU_CPU_STALL_INFO
332 unsigned int softirq_snap;
333#endif
334
335 int cpu;
336 struct rcu_state *rsp;
337};
338
339
340#define RCU_GP_IDLE 0
341#define RCU_GP_INIT 1
342#define RCU_SAVE_DYNTICK 2
343#define RCU_FORCE_QS 3
344#define RCU_SIGNAL_INIT RCU_SAVE_DYNTICK
345
346#define RCU_JIFFIES_TILL_FORCE_QS (1 + (HZ > 250) + (HZ > 500))
347
348
349
350#define RCU_JIFFIES_FQS_DIV 256
351
352
353
354#define RCU_STALL_RAT_DELAY 2
355
356
357
358#define rcu_wait(cond) \
359do { \
360 for (;;) { \
361 set_current_state(TASK_INTERRUPTIBLE); \
362 if (cond) \
363 break; \
364 schedule(); \
365 } \
366 __set_current_state(TASK_RUNNING); \
367} while (0)
368
369
370
371
372
373
374
375
376
377
378
379struct rcu_state {
380 struct rcu_node node[NUM_RCU_NODES];
381 struct rcu_node *level[RCU_NUM_LVLS];
382 u32 levelcnt[MAX_RCU_LVLS + 1];
383 u8 levelspread[RCU_NUM_LVLS];
384 struct rcu_data __percpu *rda;
385 void (*call)(struct rcu_head *head,
386 void (*func)(struct rcu_head *head));
387
388
389
390 u8 fqs_state ____cacheline_internodealigned_in_smp;
391
392 u8 boost;
393 unsigned long gpnum;
394 unsigned long completed;
395 struct task_struct *gp_kthread;
396 wait_queue_head_t gp_wq;
397 int gp_flags;
398
399
400
401 raw_spinlock_t orphan_lock ____cacheline_internodealigned_in_smp;
402
403 struct rcu_head *orphan_nxtlist;
404
405 struct rcu_head **orphan_nxttail;
406 struct rcu_head *orphan_donelist;
407
408 struct rcu_head **orphan_donetail;
409 long qlen_lazy;
410 long qlen;
411
412
413 struct mutex onoff_mutex;
414
415 struct mutex barrier_mutex;
416 atomic_t barrier_cpu_count;
417 struct completion barrier_completion;
418 unsigned long n_barrier_done;
419
420
421
422 atomic_long_t expedited_start;
423 atomic_long_t expedited_done;
424 atomic_long_t expedited_wrap;
425 atomic_long_t expedited_tryfail;
426 atomic_long_t expedited_workdone1;
427 atomic_long_t expedited_workdone2;
428 atomic_long_t expedited_normal;
429 atomic_long_t expedited_stoppedcpus;
430 atomic_long_t expedited_done_tries;
431 atomic_long_t expedited_done_lost;
432 atomic_long_t expedited_done_exit;
433
434 unsigned long jiffies_force_qs;
435
436 unsigned long n_force_qs;
437
438 unsigned long n_force_qs_lh;
439
440 unsigned long n_force_qs_ngp;
441
442 unsigned long gp_start;
443
444 unsigned long gp_activity;
445
446 unsigned long jiffies_stall;
447
448 unsigned long jiffies_resched;
449
450 unsigned long gp_max;
451
452 char *name;
453 char abbr;
454 struct list_head flavors;
455 struct irq_work wakeup_work;
456};
457
458
459#define RCU_GP_FLAG_INIT 0x1
460#define RCU_GP_FLAG_FQS 0x2
461
462extern struct list_head rcu_struct_flavors;
463
464
465#define for_each_rcu_flavor(rsp) \
466 list_for_each_entry((rsp), &rcu_struct_flavors, flavors)
467
468
469
470#define RCU_OFL_TASKS_NORM_GP 0x1
471
472#define RCU_OFL_TASKS_EXP_GP 0x2
473
474
475
476
477
478extern struct rcu_state rcu_sched_state;
479DECLARE_PER_CPU(struct rcu_data, rcu_sched_data);
480
481extern struct rcu_state rcu_bh_state;
482DECLARE_PER_CPU(struct rcu_data, rcu_bh_data);
483
484#ifdef CONFIG_TREE_PREEMPT_RCU
485extern struct rcu_state rcu_preempt_state;
486DECLARE_PER_CPU(struct rcu_data, rcu_preempt_data);
487#endif
488
489#ifdef CONFIG_RCU_BOOST
490DECLARE_PER_CPU(unsigned int, rcu_cpu_kthread_status);
491DECLARE_PER_CPU(int, rcu_cpu_kthread_cpu);
492DECLARE_PER_CPU(unsigned int, rcu_cpu_kthread_loops);
493DECLARE_PER_CPU(char, rcu_cpu_has_work);
494#endif
495
496#ifndef RCU_TREE_NONCORE
497
498
499static void rcu_bootup_announce(void);
500long rcu_batches_completed(void);
501static void rcu_preempt_note_context_switch(int cpu);
502static int rcu_preempt_blocked_readers_cgp(struct rcu_node *rnp);
503#ifdef CONFIG_HOTPLUG_CPU
504static void rcu_report_unblock_qs_rnp(struct rcu_node *rnp,
505 unsigned long flags);
506#endif
507static void rcu_print_detail_task_stall(struct rcu_state *rsp);
508static int rcu_print_task_stall(struct rcu_node *rnp);
509static void rcu_preempt_check_blocked_tasks(struct rcu_node *rnp);
510#ifdef CONFIG_HOTPLUG_CPU
511static int rcu_preempt_offline_tasks(struct rcu_state *rsp,
512 struct rcu_node *rnp,
513 struct rcu_data *rdp);
514#endif
515static void rcu_preempt_check_callbacks(int cpu);
516void call_rcu(struct rcu_head *head, void (*func)(struct rcu_head *rcu));
517#if defined(CONFIG_HOTPLUG_CPU) || defined(CONFIG_TREE_PREEMPT_RCU)
518static void rcu_report_exp_rnp(struct rcu_state *rsp, struct rcu_node *rnp,
519 bool wake);
520#endif
521static void __init __rcu_init_preempt(void);
522static void rcu_initiate_boost(struct rcu_node *rnp, unsigned long flags);
523static void rcu_preempt_boost_start_gp(struct rcu_node *rnp);
524static void invoke_rcu_callbacks_kthread(void);
525static bool rcu_is_callbacks_kthread(void);
526#ifdef CONFIG_RCU_BOOST
527static void rcu_preempt_do_callbacks(void);
528static int rcu_spawn_one_boost_kthread(struct rcu_state *rsp,
529 struct rcu_node *rnp);
530#endif
531static void __init rcu_spawn_boost_kthreads(void);
532static void rcu_prepare_kthreads(int cpu);
533static void rcu_cleanup_after_idle(int cpu);
534static void rcu_prepare_for_idle(int cpu);
535static void rcu_idle_count_callbacks_posted(void);
536static void print_cpu_stall_info_begin(void);
537static void print_cpu_stall_info(struct rcu_state *rsp, int cpu);
538static void print_cpu_stall_info_end(void);
539static void zero_cpu_stall_ticks(struct rcu_data *rdp);
540static void increment_cpu_stall_ticks(void);
541static bool rcu_nocb_cpu_needs_barrier(struct rcu_state *rsp, int cpu);
542static int rcu_nocb_needs_gp(struct rcu_state *rsp);
543static void rcu_nocb_gp_set(struct rcu_node *rnp, int nrq);
544static void rcu_nocb_gp_cleanup(struct rcu_state *rsp, struct rcu_node *rnp);
545static void rcu_init_one_nocb(struct rcu_node *rnp);
546static bool __call_rcu_nocb(struct rcu_data *rdp, struct rcu_head *rhp,
547 bool lazy);
548static bool rcu_nocb_adopt_orphan_cbs(struct rcu_state *rsp,
549 struct rcu_data *rdp);
550static void rcu_boot_init_nocb_percpu_data(struct rcu_data *rdp);
551static void rcu_spawn_all_nocb_kthreads(int cpu);
552static void __init rcu_spawn_nocb_kthreads(void);
553static void rcu_kick_nohz_cpu(int cpu);
554static bool init_nocb_callback_list(struct rcu_data *rdp);
555
556#endif
557
558#ifdef CONFIG_RCU_TRACE
559#ifdef CONFIG_RCU_NOCB_CPU
560
561static inline void rcu_nocb_q_lengths(struct rcu_data *rdp, long *ql, long *qll)
562{
563 *ql = atomic_long_read(&rdp->nocb_q_count) + rdp->nocb_p_count;
564 *qll = atomic_long_read(&rdp->nocb_q_count_lazy) + rdp->nocb_p_count_lazy;
565}
566#else
567static inline void rcu_nocb_q_lengths(struct rcu_data *rdp, long *ql, long *qll)
568{
569 *ql = 0;
570 *qll = 0;
571}
572#endif
573#endif
574