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
26
27
28
29
30#include <linux/types.h>
31#include <linux/kernel.h>
32#include <linux/init.h>
33#include <linux/spinlock.h>
34#include <linux/smp.h>
35#include <linux/rcupdate.h>
36#include <linux/interrupt.h>
37#include <linux/sched.h>
38#include <linux/nmi.h>
39#include <linux/atomic.h>
40#include <linux/bitops.h>
41#include <linux/export.h>
42#include <linux/completion.h>
43#include <linux/moduleparam.h>
44#include <linux/percpu.h>
45#include <linux/notifier.h>
46#include <linux/cpu.h>
47#include <linux/mutex.h>
48#include <linux/time.h>
49#include <linux/kernel_stat.h>
50#include <linux/wait.h>
51#include <linux/kthread.h>
52#include <linux/prefetch.h>
53#include <linux/delay.h>
54#include <linux/stop_machine.h>
55#include <linux/random.h>
56
57#include "rcutree.h"
58#include <trace/events/rcu.h>
59
60#include "rcu.h"
61
62
63
64static struct lock_class_key rcu_node_class[RCU_NUM_LVLS];
65static struct lock_class_key rcu_fqs_class[RCU_NUM_LVLS];
66
67#define RCU_STATE_INITIALIZER(sname, sabbr, cr) { \
68 .level = { &sname##_state.node[0] }, \
69 .call = cr, \
70 .fqs_state = RCU_GP_IDLE, \
71 .gpnum = 0UL - 300UL, \
72 .completed = 0UL - 300UL, \
73 .orphan_lock = __RAW_SPIN_LOCK_UNLOCKED(&sname##_state.orphan_lock), \
74 .orphan_nxttail = &sname##_state.orphan_nxtlist, \
75 .orphan_donetail = &sname##_state.orphan_donelist, \
76 .barrier_mutex = __MUTEX_INITIALIZER(sname##_state.barrier_mutex), \
77 .onoff_mutex = __MUTEX_INITIALIZER(sname##_state.onoff_mutex), \
78 .name = #sname, \
79 .abbr = sabbr, \
80}
81
82struct rcu_state rcu_sched_state =
83 RCU_STATE_INITIALIZER(rcu_sched, 's', call_rcu_sched);
84DEFINE_PER_CPU(struct rcu_data, rcu_sched_data);
85
86struct rcu_state rcu_bh_state = RCU_STATE_INITIALIZER(rcu_bh, 'b', call_rcu_bh);
87DEFINE_PER_CPU(struct rcu_data, rcu_bh_data);
88
89static struct rcu_state *rcu_state;
90LIST_HEAD(rcu_struct_flavors);
91
92
93static int rcu_fanout_leaf = CONFIG_RCU_FANOUT_LEAF;
94module_param(rcu_fanout_leaf, int, 0444);
95int rcu_num_lvls __read_mostly = RCU_NUM_LVLS;
96static int num_rcu_lvl[] = {
97 NUM_RCU_LVL_0,
98 NUM_RCU_LVL_1,
99 NUM_RCU_LVL_2,
100 NUM_RCU_LVL_3,
101 NUM_RCU_LVL_4,
102};
103int rcu_num_nodes __read_mostly = NUM_RCU_NODES;
104
105
106
107
108
109
110
111
112
113
114int rcu_scheduler_active __read_mostly;
115EXPORT_SYMBOL_GPL(rcu_scheduler_active);
116
117
118
119
120
121
122
123
124
125
126
127
128
129static int rcu_scheduler_fully_active __read_mostly;
130
131#ifdef CONFIG_RCU_BOOST
132
133
134
135
136
137static DEFINE_PER_CPU(struct task_struct *, rcu_cpu_kthread_task);
138DEFINE_PER_CPU(unsigned int, rcu_cpu_kthread_status);
139DEFINE_PER_CPU(unsigned int, rcu_cpu_kthread_loops);
140DEFINE_PER_CPU(char, rcu_cpu_has_work);
141
142#endif
143
144static void rcu_boost_kthread_setaffinity(struct rcu_node *rnp, int outgoingcpu);
145static void invoke_rcu_core(void);
146static void invoke_rcu_callbacks(struct rcu_state *rsp, struct rcu_data *rdp);
147
148
149
150
151
152
153
154
155
156
157unsigned long rcutorture_testseq;
158unsigned long rcutorture_vernum;
159
160
161
162
163
164
165static int rcu_gp_in_progress(struct rcu_state *rsp)
166{
167 return ACCESS_ONCE(rsp->completed) != ACCESS_ONCE(rsp->gpnum);
168}
169
170
171
172
173
174
175
176void rcu_sched_qs(int cpu)
177{
178 struct rcu_data *rdp = &per_cpu(rcu_sched_data, cpu);
179
180 if (rdp->passed_quiesce == 0)
181 trace_rcu_grace_period("rcu_sched", rdp->gpnum, "cpuqs");
182 rdp->passed_quiesce = 1;
183}
184
185void rcu_bh_qs(int cpu)
186{
187 struct rcu_data *rdp = &per_cpu(rcu_bh_data, cpu);
188
189 if (rdp->passed_quiesce == 0)
190 trace_rcu_grace_period("rcu_bh", rdp->gpnum, "cpuqs");
191 rdp->passed_quiesce = 1;
192}
193
194
195
196
197
198
199void rcu_note_context_switch(int cpu)
200{
201 trace_rcu_utilization("Start context switch");
202 rcu_sched_qs(cpu);
203 rcu_preempt_note_context_switch(cpu);
204 trace_rcu_utilization("End context switch");
205}
206EXPORT_SYMBOL_GPL(rcu_note_context_switch);
207
208DEFINE_PER_CPU(struct rcu_dynticks, rcu_dynticks) = {
209 .dynticks_nesting = DYNTICK_TASK_EXIT_IDLE,
210 .dynticks = ATOMIC_INIT(1),
211};
212
213static long blimit = 10;
214static long qhimark = 10000;
215static long qlowmark = 100;
216
217module_param(blimit, long, 0444);
218module_param(qhimark, long, 0444);
219module_param(qlowmark, long, 0444);
220
221static ulong jiffies_till_first_fqs = ULONG_MAX;
222static ulong jiffies_till_next_fqs = ULONG_MAX;
223
224module_param(jiffies_till_first_fqs, ulong, 0644);
225module_param(jiffies_till_next_fqs, ulong, 0644);
226
227static void rcu_start_gp_advanced(struct rcu_state *rsp, struct rcu_node *rnp,
228 struct rcu_data *rdp);
229static void force_qs_rnp(struct rcu_state *rsp, int (*f)(struct rcu_data *));
230static void force_quiescent_state(struct rcu_state *rsp);
231static int rcu_pending(int cpu);
232
233
234
235
236long rcu_batches_completed_sched(void)
237{
238 return rcu_sched_state.completed;
239}
240EXPORT_SYMBOL_GPL(rcu_batches_completed_sched);
241
242
243
244
245long rcu_batches_completed_bh(void)
246{
247 return rcu_bh_state.completed;
248}
249EXPORT_SYMBOL_GPL(rcu_batches_completed_bh);
250
251
252
253
254void rcu_bh_force_quiescent_state(void)
255{
256 force_quiescent_state(&rcu_bh_state);
257}
258EXPORT_SYMBOL_GPL(rcu_bh_force_quiescent_state);
259
260
261
262
263
264
265
266
267void rcutorture_record_test_transition(void)
268{
269 rcutorture_testseq++;
270 rcutorture_vernum = 0;
271}
272EXPORT_SYMBOL_GPL(rcutorture_record_test_transition);
273
274
275
276
277
278
279void rcutorture_record_progress(unsigned long vernum)
280{
281 rcutorture_vernum++;
282}
283EXPORT_SYMBOL_GPL(rcutorture_record_progress);
284
285
286
287
288void rcu_sched_force_quiescent_state(void)
289{
290 force_quiescent_state(&rcu_sched_state);
291}
292EXPORT_SYMBOL_GPL(rcu_sched_force_quiescent_state);
293
294
295
296
297static int
298cpu_has_callbacks_ready_to_invoke(struct rcu_data *rdp)
299{
300 return &rdp->nxtlist != rdp->nxttail[RCU_DONE_TAIL] &&
301 rdp->nxttail[RCU_DONE_TAIL] != NULL;
302}
303
304
305
306
307
308
309static int
310cpu_needs_another_gp(struct rcu_state *rsp, struct rcu_data *rdp)
311{
312 int i;
313
314 if (rcu_gp_in_progress(rsp))
315 return 0;
316 if (rcu_nocb_needs_gp(rsp))
317 return 1;
318 if (!rdp->nxttail[RCU_NEXT_TAIL])
319 return 0;
320 if (*rdp->nxttail[RCU_NEXT_READY_TAIL])
321 return 1;
322 for (i = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++)
323 if (rdp->nxttail[i - 1] != rdp->nxttail[i] &&
324 ULONG_CMP_LT(ACCESS_ONCE(rsp->completed),
325 rdp->nxtcompleted[i]))
326 return 1;
327 return 0;
328}
329
330
331
332
333static struct rcu_node *rcu_get_root(struct rcu_state *rsp)
334{
335 return &rsp->node[0];
336}
337
338
339
340
341
342
343
344
345static void rcu_eqs_enter_common(struct rcu_dynticks *rdtp, long long oldval,
346 bool user)
347{
348 trace_rcu_dyntick("Start", oldval, rdtp->dynticks_nesting);
349 if (!user && !is_idle_task(current)) {
350 struct task_struct *idle = idle_task(smp_processor_id());
351
352 trace_rcu_dyntick("Error on entry: not idle task", oldval, 0);
353 ftrace_dump(DUMP_ORIG);
354 WARN_ONCE(1, "Current pid: %d comm: %s / Idle pid: %d comm: %s",
355 current->pid, current->comm,
356 idle->pid, idle->comm);
357 }
358 rcu_prepare_for_idle(smp_processor_id());
359
360 smp_mb__before_atomic_inc();
361 atomic_inc(&rdtp->dynticks);
362 smp_mb__after_atomic_inc();
363 WARN_ON_ONCE(atomic_read(&rdtp->dynticks) & 0x1);
364
365
366
367
368
369 rcu_lockdep_assert(!lock_is_held(&rcu_lock_map),
370 "Illegal idle entry in RCU read-side critical section.");
371 rcu_lockdep_assert(!lock_is_held(&rcu_bh_lock_map),
372 "Illegal idle entry in RCU-bh read-side critical section.");
373 rcu_lockdep_assert(!lock_is_held(&rcu_sched_lock_map),
374 "Illegal idle entry in RCU-sched read-side critical section.");
375}
376
377
378
379
380
381static void rcu_eqs_enter(bool user)
382{
383 long long oldval;
384 struct rcu_dynticks *rdtp;
385
386 rdtp = &__get_cpu_var(rcu_dynticks);
387 oldval = rdtp->dynticks_nesting;
388 WARN_ON_ONCE((oldval & DYNTICK_TASK_NEST_MASK) == 0);
389 if ((oldval & DYNTICK_TASK_NEST_MASK) == DYNTICK_TASK_NEST_VALUE)
390 rdtp->dynticks_nesting = 0;
391 else
392 rdtp->dynticks_nesting -= DYNTICK_TASK_NEST_VALUE;
393 rcu_eqs_enter_common(rdtp, oldval, user);
394}
395
396
397
398
399
400
401
402
403
404
405
406
407
408void rcu_idle_enter(void)
409{
410 unsigned long flags;
411
412 local_irq_save(flags);
413 rcu_eqs_enter(false);
414 local_irq_restore(flags);
415}
416EXPORT_SYMBOL_GPL(rcu_idle_enter);
417
418#ifdef CONFIG_RCU_USER_QS
419
420
421
422
423
424
425
426
427void rcu_user_enter(void)
428{
429 rcu_eqs_enter(1);
430}
431
432
433
434
435
436
437
438
439
440void rcu_user_enter_after_irq(void)
441{
442 unsigned long flags;
443 struct rcu_dynticks *rdtp;
444
445 local_irq_save(flags);
446 rdtp = &__get_cpu_var(rcu_dynticks);
447
448 WARN_ON_ONCE(!(rdtp->dynticks_nesting & DYNTICK_TASK_MASK));
449 rdtp->dynticks_nesting = 1;
450 local_irq_restore(flags);
451}
452#endif
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470void rcu_irq_exit(void)
471{
472 unsigned long flags;
473 long long oldval;
474 struct rcu_dynticks *rdtp;
475
476 local_irq_save(flags);
477 rdtp = &__get_cpu_var(rcu_dynticks);
478 oldval = rdtp->dynticks_nesting;
479 rdtp->dynticks_nesting--;
480 WARN_ON_ONCE(rdtp->dynticks_nesting < 0);
481 if (rdtp->dynticks_nesting)
482 trace_rcu_dyntick("--=", oldval, rdtp->dynticks_nesting);
483 else
484 rcu_eqs_enter_common(rdtp, oldval, true);
485 local_irq_restore(flags);
486}
487
488
489
490
491
492
493
494
495static void rcu_eqs_exit_common(struct rcu_dynticks *rdtp, long long oldval,
496 int user)
497{
498 smp_mb__before_atomic_inc();
499 atomic_inc(&rdtp->dynticks);
500
501 smp_mb__after_atomic_inc();
502 WARN_ON_ONCE(!(atomic_read(&rdtp->dynticks) & 0x1));
503 rcu_cleanup_after_idle(smp_processor_id());
504 trace_rcu_dyntick("End", oldval, rdtp->dynticks_nesting);
505 if (!user && !is_idle_task(current)) {
506 struct task_struct *idle = idle_task(smp_processor_id());
507
508 trace_rcu_dyntick("Error on exit: not idle task",
509 oldval, rdtp->dynticks_nesting);
510 ftrace_dump(DUMP_ORIG);
511 WARN_ONCE(1, "Current pid: %d comm: %s / Idle pid: %d comm: %s",
512 current->pid, current->comm,
513 idle->pid, idle->comm);
514 }
515}
516
517
518
519
520
521static void rcu_eqs_exit(bool user)
522{
523 struct rcu_dynticks *rdtp;
524 long long oldval;
525
526 rdtp = &__get_cpu_var(rcu_dynticks);
527 oldval = rdtp->dynticks_nesting;
528 WARN_ON_ONCE(oldval < 0);
529 if (oldval & DYNTICK_TASK_NEST_MASK)
530 rdtp->dynticks_nesting += DYNTICK_TASK_NEST_VALUE;
531 else
532 rdtp->dynticks_nesting = DYNTICK_TASK_EXIT_IDLE;
533 rcu_eqs_exit_common(rdtp, oldval, user);
534}
535
536
537
538
539
540
541
542
543
544
545
546
547void rcu_idle_exit(void)
548{
549 unsigned long flags;
550
551 local_irq_save(flags);
552 rcu_eqs_exit(false);
553 local_irq_restore(flags);
554}
555EXPORT_SYMBOL_GPL(rcu_idle_exit);
556
557#ifdef CONFIG_RCU_USER_QS
558
559
560
561
562
563
564void rcu_user_exit(void)
565{
566 rcu_eqs_exit(1);
567}
568
569
570
571
572
573
574
575
576
577
578void rcu_user_exit_after_irq(void)
579{
580 unsigned long flags;
581 struct rcu_dynticks *rdtp;
582
583 local_irq_save(flags);
584 rdtp = &__get_cpu_var(rcu_dynticks);
585
586 WARN_ON_ONCE(rdtp->dynticks_nesting & DYNTICK_TASK_NEST_MASK);
587 rdtp->dynticks_nesting += DYNTICK_TASK_EXIT_IDLE;
588 local_irq_restore(flags);
589}
590#endif
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611void rcu_irq_enter(void)
612{
613 unsigned long flags;
614 struct rcu_dynticks *rdtp;
615 long long oldval;
616
617 local_irq_save(flags);
618 rdtp = &__get_cpu_var(rcu_dynticks);
619 oldval = rdtp->dynticks_nesting;
620 rdtp->dynticks_nesting++;
621 WARN_ON_ONCE(rdtp->dynticks_nesting == 0);
622 if (oldval)
623 trace_rcu_dyntick("++=", oldval, rdtp->dynticks_nesting);
624 else
625 rcu_eqs_exit_common(rdtp, oldval, true);
626 local_irq_restore(flags);
627}
628
629
630
631
632
633
634
635
636void rcu_nmi_enter(void)
637{
638 struct rcu_dynticks *rdtp = &__get_cpu_var(rcu_dynticks);
639
640 if (rdtp->dynticks_nmi_nesting == 0 &&
641 (atomic_read(&rdtp->dynticks) & 0x1))
642 return;
643 rdtp->dynticks_nmi_nesting++;
644 smp_mb__before_atomic_inc();
645 atomic_inc(&rdtp->dynticks);
646
647 smp_mb__after_atomic_inc();
648 WARN_ON_ONCE(!(atomic_read(&rdtp->dynticks) & 0x1));
649}
650
651
652
653
654
655
656
657
658void rcu_nmi_exit(void)
659{
660 struct rcu_dynticks *rdtp = &__get_cpu_var(rcu_dynticks);
661
662 if (rdtp->dynticks_nmi_nesting == 0 ||
663 --rdtp->dynticks_nmi_nesting != 0)
664 return;
665
666 smp_mb__before_atomic_inc();
667 atomic_inc(&rdtp->dynticks);
668 smp_mb__after_atomic_inc();
669 WARN_ON_ONCE(atomic_read(&rdtp->dynticks) & 0x1);
670}
671
672
673
674
675
676
677
678int rcu_is_cpu_idle(void)
679{
680 int ret;
681
682 preempt_disable();
683 ret = (atomic_read(&__get_cpu_var(rcu_dynticks).dynticks) & 0x1) == 0;
684 preempt_enable();
685 return ret;
686}
687EXPORT_SYMBOL(rcu_is_cpu_idle);
688
689#if defined(CONFIG_PROVE_RCU) && defined(CONFIG_HOTPLUG_CPU)
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712bool rcu_lockdep_current_cpu_online(void)
713{
714 struct rcu_data *rdp;
715 struct rcu_node *rnp;
716 bool ret;
717
718 if (in_nmi())
719 return 1;
720 preempt_disable();
721 rdp = &__get_cpu_var(rcu_sched_data);
722 rnp = rdp->mynode;
723 ret = (rdp->grpmask & rnp->qsmaskinit) ||
724 !rcu_scheduler_fully_active;
725 preempt_enable();
726 return ret;
727}
728EXPORT_SYMBOL_GPL(rcu_lockdep_current_cpu_online);
729
730#endif
731
732
733
734
735
736
737
738
739static int rcu_is_cpu_rrupt_from_idle(void)
740{
741 return __get_cpu_var(rcu_dynticks).dynticks_nesting <= 1;
742}
743
744
745
746
747
748
749static int dyntick_save_progress_counter(struct rcu_data *rdp)
750{
751 rdp->dynticks_snap = atomic_add_return(0, &rdp->dynticks->dynticks);
752 return (rdp->dynticks_snap & 0x1) == 0;
753}
754
755
756
757
758
759
760
761static int rcu_implicit_dynticks_qs(struct rcu_data *rdp)
762{
763 unsigned int curr;
764 unsigned int snap;
765
766 curr = (unsigned int)atomic_add_return(0, &rdp->dynticks->dynticks);
767 snap = (unsigned int)rdp->dynticks_snap;
768
769
770
771
772
773
774
775
776
777 if ((curr & 0x1) == 0 || UINT_CMP_GE(curr, snap + 2)) {
778 trace_rcu_fqs(rdp->rsp->name, rdp->gpnum, rdp->cpu, "dti");
779 rdp->dynticks_fqs++;
780 return 1;
781 }
782
783
784
785
786
787
788
789
790
791
792
793
794 if (ULONG_CMP_GE(rdp->rsp->gp_start + 2, jiffies))
795 return 0;
796 barrier();
797 if (cpu_is_offline(rdp->cpu)) {
798 trace_rcu_fqs(rdp->rsp->name, rdp->gpnum, rdp->cpu, "ofl");
799 rdp->offline_fqs++;
800 return 1;
801 }
802
803
804
805
806
807
808
809
810 rcu_kick_nohz_cpu(rdp->cpu);
811
812 return 0;
813}
814
815static void record_gp_stall_check_time(struct rcu_state *rsp)
816{
817 rsp->gp_start = jiffies;
818 rsp->jiffies_stall = jiffies + rcu_jiffies_till_stall_check();
819}
820
821
822
823
824
825
826
827static void rcu_dump_cpu_stacks(struct rcu_state *rsp)
828{
829 int cpu;
830 unsigned long flags;
831 struct rcu_node *rnp;
832
833 rcu_for_each_leaf_node(rsp, rnp) {
834 raw_spin_lock_irqsave(&rnp->lock, flags);
835 if (rnp->qsmask != 0) {
836 for (cpu = 0; cpu <= rnp->grphi - rnp->grplo; cpu++)
837 if (rnp->qsmask & (1UL << cpu))
838 dump_cpu_task(rnp->grplo + cpu);
839 }
840 raw_spin_unlock_irqrestore(&rnp->lock, flags);
841 }
842}
843
844static void print_other_cpu_stall(struct rcu_state *rsp)
845{
846 int cpu;
847 long delta;
848 unsigned long flags;
849 int ndetected = 0;
850 struct rcu_node *rnp = rcu_get_root(rsp);
851 long totqlen = 0;
852
853
854
855 raw_spin_lock_irqsave(&rnp->lock, flags);
856 delta = jiffies - rsp->jiffies_stall;
857 if (delta < RCU_STALL_RAT_DELAY || !rcu_gp_in_progress(rsp)) {
858 raw_spin_unlock_irqrestore(&rnp->lock, flags);
859 return;
860 }
861 rsp->jiffies_stall = jiffies + 3 * rcu_jiffies_till_stall_check() + 3;
862 raw_spin_unlock_irqrestore(&rnp->lock, flags);
863
864
865
866
867
868
869 pr_err("INFO: %s detected stalls on CPUs/tasks:",
870 rsp->name);
871 print_cpu_stall_info_begin();
872 rcu_for_each_leaf_node(rsp, rnp) {
873 raw_spin_lock_irqsave(&rnp->lock, flags);
874 ndetected += rcu_print_task_stall(rnp);
875 if (rnp->qsmask != 0) {
876 for (cpu = 0; cpu <= rnp->grphi - rnp->grplo; cpu++)
877 if (rnp->qsmask & (1UL << cpu)) {
878 print_cpu_stall_info(rsp,
879 rnp->grplo + cpu);
880 ndetected++;
881 }
882 }
883 raw_spin_unlock_irqrestore(&rnp->lock, flags);
884 }
885
886
887
888
889
890 rnp = rcu_get_root(rsp);
891 raw_spin_lock_irqsave(&rnp->lock, flags);
892 ndetected += rcu_print_task_stall(rnp);
893 raw_spin_unlock_irqrestore(&rnp->lock, flags);
894
895 print_cpu_stall_info_end();
896 for_each_possible_cpu(cpu)
897 totqlen += per_cpu_ptr(rsp->rda, cpu)->qlen;
898 pr_cont("(detected by %d, t=%ld jiffies, g=%lu, c=%lu, q=%lu)\n",
899 smp_processor_id(), (long)(jiffies - rsp->gp_start),
900 rsp->gpnum, rsp->completed, totqlen);
901 if (ndetected == 0)
902 pr_err("INFO: Stall ended before state dump start\n");
903 else if (!trigger_all_cpu_backtrace())
904 rcu_dump_cpu_stacks(rsp);
905
906
907
908 rcu_print_detail_task_stall(rsp);
909
910 force_quiescent_state(rsp);
911}
912
913static void print_cpu_stall(struct rcu_state *rsp)
914{
915 int cpu;
916 unsigned long flags;
917 struct rcu_node *rnp = rcu_get_root(rsp);
918 long totqlen = 0;
919
920
921
922
923
924
925 pr_err("INFO: %s self-detected stall on CPU", rsp->name);
926 print_cpu_stall_info_begin();
927 print_cpu_stall_info(rsp, smp_processor_id());
928 print_cpu_stall_info_end();
929 for_each_possible_cpu(cpu)
930 totqlen += per_cpu_ptr(rsp->rda, cpu)->qlen;
931 pr_cont(" (t=%lu jiffies g=%lu c=%lu q=%lu)\n",
932 jiffies - rsp->gp_start, rsp->gpnum, rsp->completed, totqlen);
933 if (!trigger_all_cpu_backtrace())
934 dump_stack();
935
936 raw_spin_lock_irqsave(&rnp->lock, flags);
937 if (ULONG_CMP_GE(jiffies, rsp->jiffies_stall))
938 rsp->jiffies_stall = jiffies +
939 3 * rcu_jiffies_till_stall_check() + 3;
940 raw_spin_unlock_irqrestore(&rnp->lock, flags);
941
942 set_need_resched();
943}
944
945static void check_cpu_stall(struct rcu_state *rsp, struct rcu_data *rdp)
946{
947 unsigned long j;
948 unsigned long js;
949 struct rcu_node *rnp;
950
951 if (rcu_cpu_stall_suppress)
952 return;
953 j = ACCESS_ONCE(jiffies);
954 js = ACCESS_ONCE(rsp->jiffies_stall);
955 rnp = rdp->mynode;
956 if (rcu_gp_in_progress(rsp) &&
957 (ACCESS_ONCE(rnp->qsmask) & rdp->grpmask) && ULONG_CMP_GE(j, js)) {
958
959
960 print_cpu_stall(rsp);
961
962 } else if (rcu_gp_in_progress(rsp) &&
963 ULONG_CMP_GE(j, js + RCU_STALL_RAT_DELAY)) {
964
965
966 print_other_cpu_stall(rsp);
967 }
968}
969
970
971
972
973
974
975
976
977
978
979void rcu_cpu_stall_reset(void)
980{
981 struct rcu_state *rsp;
982
983 for_each_rcu_flavor(rsp)
984 rsp->jiffies_stall = jiffies + ULONG_MAX / 2;
985}
986
987
988
989
990static void init_callback_list(struct rcu_data *rdp)
991{
992 int i;
993
994 if (init_nocb_callback_list(rdp))
995 return;
996 rdp->nxtlist = NULL;
997 for (i = 0; i < RCU_NEXT_SIZE; i++)
998 rdp->nxttail[i] = &rdp->nxtlist;
999}
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010static unsigned long rcu_cbs_completed(struct rcu_state *rsp,
1011 struct rcu_node *rnp)
1012{
1013
1014
1015
1016
1017
1018
1019
1020 if (rcu_get_root(rsp) == rnp && rnp->gpnum == rnp->completed)
1021 return rnp->completed + 1;
1022
1023
1024
1025
1026
1027 return rnp->completed + 2;
1028}
1029
1030
1031
1032
1033
1034static void trace_rcu_future_gp(struct rcu_node *rnp, struct rcu_data *rdp,
1035 unsigned long c, char *s)
1036{
1037 trace_rcu_future_grace_period(rdp->rsp->name, rnp->gpnum,
1038 rnp->completed, c, rnp->level,
1039 rnp->grplo, rnp->grphi, s);
1040}
1041
1042
1043
1044
1045
1046
1047
1048
1049static unsigned long __maybe_unused
1050rcu_start_future_gp(struct rcu_node *rnp, struct rcu_data *rdp)
1051{
1052 unsigned long c;
1053 int i;
1054 struct rcu_node *rnp_root = rcu_get_root(rdp->rsp);
1055
1056
1057
1058
1059
1060 c = rcu_cbs_completed(rdp->rsp, rnp);
1061 trace_rcu_future_gp(rnp, rdp, c, "Startleaf");
1062 if (rnp->need_future_gp[c & 0x1]) {
1063 trace_rcu_future_gp(rnp, rdp, c, "Prestartleaf");
1064 return c;
1065 }
1066
1067
1068
1069
1070
1071
1072
1073
1074 if (rnp->gpnum != rnp->completed ||
1075 ACCESS_ONCE(rnp->gpnum) != ACCESS_ONCE(rnp->completed)) {
1076 rnp->need_future_gp[c & 0x1]++;
1077 trace_rcu_future_gp(rnp, rdp, c, "Startedleaf");
1078 return c;
1079 }
1080
1081
1082
1083
1084
1085
1086 if (rnp != rnp_root)
1087 raw_spin_lock(&rnp_root->lock);
1088
1089
1090
1091
1092
1093
1094
1095 c = rcu_cbs_completed(rdp->rsp, rnp_root);
1096 for (i = RCU_DONE_TAIL; i < RCU_NEXT_TAIL; i++)
1097 if (ULONG_CMP_LT(c, rdp->nxtcompleted[i]))
1098 rdp->nxtcompleted[i] = c;
1099
1100
1101
1102
1103
1104 if (rnp_root->need_future_gp[c & 0x1]) {
1105 trace_rcu_future_gp(rnp, rdp, c, "Prestartedroot");
1106 goto unlock_out;
1107 }
1108
1109
1110 rnp_root->need_future_gp[c & 0x1]++;
1111
1112
1113 if (rnp_root->gpnum != rnp_root->completed) {
1114 trace_rcu_future_gp(rnp, rdp, c, "Startedleafroot");
1115 } else {
1116 trace_rcu_future_gp(rnp, rdp, c, "Startedroot");
1117 rcu_start_gp_advanced(rdp->rsp, rnp_root, rdp);
1118 }
1119unlock_out:
1120 if (rnp != rnp_root)
1121 raw_spin_unlock(&rnp_root->lock);
1122 return c;
1123}
1124
1125
1126
1127
1128
1129
1130
1131static int rcu_future_gp_cleanup(struct rcu_state *rsp, struct rcu_node *rnp)
1132{
1133 int c = rnp->completed;
1134 int needmore;
1135 struct rcu_data *rdp = this_cpu_ptr(rsp->rda);
1136
1137 rcu_nocb_gp_cleanup(rsp, rnp);
1138 rnp->need_future_gp[c & 0x1] = 0;
1139 needmore = rnp->need_future_gp[(c + 1) & 0x1];
1140 trace_rcu_future_gp(rnp, rdp, c, needmore ? "CleanupMore" : "Cleanup");
1141 return needmore;
1142}
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155static void rcu_accelerate_cbs(struct rcu_state *rsp, struct rcu_node *rnp,
1156 struct rcu_data *rdp)
1157{
1158 unsigned long c;
1159 int i;
1160
1161
1162 if (!rdp->nxttail[RCU_NEXT_TAIL] || !*rdp->nxttail[RCU_DONE_TAIL])
1163 return;
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179 c = rcu_cbs_completed(rsp, rnp);
1180 for (i = RCU_NEXT_TAIL - 1; i > RCU_DONE_TAIL; i--)
1181 if (rdp->nxttail[i] != rdp->nxttail[i - 1] &&
1182 !ULONG_CMP_GE(rdp->nxtcompleted[i], c))
1183 break;
1184
1185
1186
1187
1188
1189
1190
1191 if (++i >= RCU_NEXT_TAIL)
1192 return;
1193
1194
1195
1196
1197
1198
1199 for (; i <= RCU_NEXT_TAIL; i++) {
1200 rdp->nxttail[i] = rdp->nxttail[RCU_NEXT_TAIL];
1201 rdp->nxtcompleted[i] = c;
1202 }
1203
1204 rcu_start_future_gp(rnp, rdp);
1205
1206
1207 if (!*rdp->nxttail[RCU_WAIT_TAIL])
1208 trace_rcu_grace_period(rsp->name, rdp->gpnum, "AccWaitCB");
1209 else
1210 trace_rcu_grace_period(rsp->name, rdp->gpnum, "AccReadyCB");
1211}
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222static void rcu_advance_cbs(struct rcu_state *rsp, struct rcu_node *rnp,
1223 struct rcu_data *rdp)
1224{
1225 int i, j;
1226
1227
1228 if (!rdp->nxttail[RCU_NEXT_TAIL] || !*rdp->nxttail[RCU_DONE_TAIL])
1229 return;
1230
1231
1232
1233
1234
1235 for (i = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++) {
1236 if (ULONG_CMP_LT(rnp->completed, rdp->nxtcompleted[i]))
1237 break;
1238 rdp->nxttail[RCU_DONE_TAIL] = rdp->nxttail[i];
1239 }
1240
1241 for (j = RCU_WAIT_TAIL; j < i; j++)
1242 rdp->nxttail[j] = rdp->nxttail[RCU_DONE_TAIL];
1243
1244
1245 for (j = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++, j++) {
1246 if (rdp->nxttail[j] == rdp->nxttail[RCU_NEXT_TAIL])
1247 break;
1248 rdp->nxttail[j] = rdp->nxttail[i];
1249 rdp->nxtcompleted[j] = rdp->nxtcompleted[i];
1250 }
1251
1252
1253 rcu_accelerate_cbs(rsp, rnp, rdp);
1254}
1255
1256
1257
1258
1259
1260
1261static void __note_gp_changes(struct rcu_state *rsp, struct rcu_node *rnp, struct rcu_data *rdp)
1262{
1263
1264 if (rdp->completed == rnp->completed) {
1265
1266
1267 rcu_accelerate_cbs(rsp, rnp, rdp);
1268
1269 } else {
1270
1271
1272 rcu_advance_cbs(rsp, rnp, rdp);
1273
1274
1275 rdp->completed = rnp->completed;
1276 trace_rcu_grace_period(rsp->name, rdp->gpnum, "cpuend");
1277 }
1278
1279 if (rdp->gpnum != rnp->gpnum) {
1280
1281
1282
1283
1284
1285 rdp->gpnum = rnp->gpnum;
1286 trace_rcu_grace_period(rsp->name, rdp->gpnum, "cpustart");
1287 rdp->passed_quiesce = 0;
1288 rdp->qs_pending = !!(rnp->qsmask & rdp->grpmask);
1289 zero_cpu_stall_ticks(rdp);
1290 }
1291}
1292
1293static void note_gp_changes(struct rcu_state *rsp, struct rcu_data *rdp)
1294{
1295 unsigned long flags;
1296 struct rcu_node *rnp;
1297
1298 local_irq_save(flags);
1299 rnp = rdp->mynode;
1300 if ((rdp->gpnum == ACCESS_ONCE(rnp->gpnum) &&
1301 rdp->completed == ACCESS_ONCE(rnp->completed)) ||
1302 !raw_spin_trylock(&rnp->lock)) {
1303 local_irq_restore(flags);
1304 return;
1305 }
1306 __note_gp_changes(rsp, rnp, rdp);
1307 raw_spin_unlock_irqrestore(&rnp->lock, flags);
1308}
1309
1310
1311
1312
1313static int rcu_gp_init(struct rcu_state *rsp)
1314{
1315 struct rcu_data *rdp;
1316 struct rcu_node *rnp = rcu_get_root(rsp);
1317
1318 raw_spin_lock_irq(&rnp->lock);
1319 rsp->gp_flags = 0;
1320
1321 if (rcu_gp_in_progress(rsp)) {
1322
1323 raw_spin_unlock_irq(&rnp->lock);
1324 return 0;
1325 }
1326
1327
1328 rsp->gpnum++;
1329 trace_rcu_grace_period(rsp->name, rsp->gpnum, "start");
1330 record_gp_stall_check_time(rsp);
1331 raw_spin_unlock_irq(&rnp->lock);
1332
1333
1334 mutex_lock(&rsp->onoff_mutex);
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349 rcu_for_each_node_breadth_first(rsp, rnp) {
1350 raw_spin_lock_irq(&rnp->lock);
1351 rdp = this_cpu_ptr(rsp->rda);
1352 rcu_preempt_check_blocked_tasks(rnp);
1353 rnp->qsmask = rnp->qsmaskinit;
1354 ACCESS_ONCE(rnp->gpnum) = rsp->gpnum;
1355 WARN_ON_ONCE(rnp->completed != rsp->completed);
1356 ACCESS_ONCE(rnp->completed) = rsp->completed;
1357 if (rnp == rdp->mynode)
1358 __note_gp_changes(rsp, rnp, rdp);
1359 rcu_preempt_boost_start_gp(rnp);
1360 trace_rcu_grace_period_init(rsp->name, rnp->gpnum,
1361 rnp->level, rnp->grplo,
1362 rnp->grphi, rnp->qsmask);
1363 raw_spin_unlock_irq(&rnp->lock);
1364#ifdef CONFIG_PROVE_RCU_DELAY
1365 if ((prandom_u32() % (rcu_num_nodes + 1)) == 0 &&
1366 system_state == SYSTEM_RUNNING)
1367 udelay(200);
1368#endif
1369 cond_resched();
1370 }
1371
1372 mutex_unlock(&rsp->onoff_mutex);
1373 return 1;
1374}
1375
1376
1377
1378
1379int rcu_gp_fqs(struct rcu_state *rsp, int fqs_state_in)
1380{
1381 int fqs_state = fqs_state_in;
1382 struct rcu_node *rnp = rcu_get_root(rsp);
1383
1384 rsp->n_force_qs++;
1385 if (fqs_state == RCU_SAVE_DYNTICK) {
1386
1387 force_qs_rnp(rsp, dyntick_save_progress_counter);
1388 fqs_state = RCU_FORCE_QS;
1389 } else {
1390
1391 force_qs_rnp(rsp, rcu_implicit_dynticks_qs);
1392 }
1393
1394 if (ACCESS_ONCE(rsp->gp_flags) & RCU_GP_FLAG_FQS) {
1395 raw_spin_lock_irq(&rnp->lock);
1396 rsp->gp_flags &= ~RCU_GP_FLAG_FQS;
1397 raw_spin_unlock_irq(&rnp->lock);
1398 }
1399 return fqs_state;
1400}
1401
1402
1403
1404
1405static void rcu_gp_cleanup(struct rcu_state *rsp)
1406{
1407 unsigned long gp_duration;
1408 int nocb = 0;
1409 struct rcu_data *rdp;
1410 struct rcu_node *rnp = rcu_get_root(rsp);
1411
1412 raw_spin_lock_irq(&rnp->lock);
1413 gp_duration = jiffies - rsp->gp_start;
1414 if (gp_duration > rsp->gp_max)
1415 rsp->gp_max = gp_duration;
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425 raw_spin_unlock_irq(&rnp->lock);
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436 rcu_for_each_node_breadth_first(rsp, rnp) {
1437 raw_spin_lock_irq(&rnp->lock);
1438 ACCESS_ONCE(rnp->completed) = rsp->gpnum;
1439 rdp = this_cpu_ptr(rsp->rda);
1440 if (rnp == rdp->mynode)
1441 __note_gp_changes(rsp, rnp, rdp);
1442 nocb += rcu_future_gp_cleanup(rsp, rnp);
1443 raw_spin_unlock_irq(&rnp->lock);
1444 cond_resched();
1445 }
1446 rnp = rcu_get_root(rsp);
1447 raw_spin_lock_irq(&rnp->lock);
1448 rcu_nocb_gp_set(rnp, nocb);
1449
1450 rsp->completed = rsp->gpnum;
1451 trace_rcu_grace_period(rsp->name, rsp->completed, "end");
1452 rsp->fqs_state = RCU_GP_IDLE;
1453 rdp = this_cpu_ptr(rsp->rda);
1454 rcu_advance_cbs(rsp, rnp, rdp);
1455 if (cpu_needs_another_gp(rsp, rdp))
1456 rsp->gp_flags = 1;
1457 raw_spin_unlock_irq(&rnp->lock);
1458}
1459
1460
1461
1462
1463static int __noreturn rcu_gp_kthread(void *arg)
1464{
1465 int fqs_state;
1466 unsigned long j;
1467 int ret;
1468 struct rcu_state *rsp = arg;
1469 struct rcu_node *rnp = rcu_get_root(rsp);
1470
1471 for (;;) {
1472
1473
1474 for (;;) {
1475 wait_event_interruptible(rsp->gp_wq,
1476 rsp->gp_flags &
1477 RCU_GP_FLAG_INIT);
1478 if ((rsp->gp_flags & RCU_GP_FLAG_INIT) &&
1479 rcu_gp_init(rsp))
1480 break;
1481 cond_resched();
1482 flush_signals(current);
1483 }
1484
1485
1486 fqs_state = RCU_SAVE_DYNTICK;
1487 j = jiffies_till_first_fqs;
1488 if (j > HZ) {
1489 j = HZ;
1490 jiffies_till_first_fqs = HZ;
1491 }
1492 for (;;) {
1493 rsp->jiffies_force_qs = jiffies + j;
1494 ret = wait_event_interruptible_timeout(rsp->gp_wq,
1495 (rsp->gp_flags & RCU_GP_FLAG_FQS) ||
1496 (!ACCESS_ONCE(rnp->qsmask) &&
1497 !rcu_preempt_blocked_readers_cgp(rnp)),
1498 j);
1499
1500 if (!ACCESS_ONCE(rnp->qsmask) &&
1501 !rcu_preempt_blocked_readers_cgp(rnp))
1502 break;
1503
1504 if (ret == 0 || (rsp->gp_flags & RCU_GP_FLAG_FQS)) {
1505 fqs_state = rcu_gp_fqs(rsp, fqs_state);
1506 cond_resched();
1507 } else {
1508
1509 cond_resched();
1510 flush_signals(current);
1511 }
1512 j = jiffies_till_next_fqs;
1513 if (j > HZ) {
1514 j = HZ;
1515 jiffies_till_next_fqs = HZ;
1516 } else if (j < 1) {
1517 j = 1;
1518 jiffies_till_next_fqs = 1;
1519 }
1520 }
1521
1522
1523 rcu_gp_cleanup(rsp);
1524 }
1525}
1526
1527static void rsp_wakeup(struct irq_work *work)
1528{
1529 struct rcu_state *rsp = container_of(work, struct rcu_state, wakeup_work);
1530
1531
1532 wake_up(&rsp->gp_wq);
1533}
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544static void
1545rcu_start_gp_advanced(struct rcu_state *rsp, struct rcu_node *rnp,
1546 struct rcu_data *rdp)
1547{
1548 if (!rsp->gp_kthread || !cpu_needs_another_gp(rsp, rdp)) {
1549
1550
1551
1552
1553
1554
1555 return;
1556 }
1557 rsp->gp_flags = RCU_GP_FLAG_INIT;
1558
1559
1560
1561
1562
1563
1564 irq_work_queue(&rsp->wakeup_work);
1565}
1566
1567
1568
1569
1570
1571
1572
1573
1574static void
1575rcu_start_gp(struct rcu_state *rsp)
1576{
1577 struct rcu_data *rdp = this_cpu_ptr(rsp->rda);
1578 struct rcu_node *rnp = rcu_get_root(rsp);
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588 rcu_advance_cbs(rsp, rnp, rdp);
1589 rcu_start_gp_advanced(rsp, rnp, rdp);
1590}
1591
1592
1593
1594
1595
1596
1597
1598
1599static void rcu_report_qs_rsp(struct rcu_state *rsp, unsigned long flags)
1600 __releases(rcu_get_root(rsp)->lock)
1601{
1602 WARN_ON_ONCE(!rcu_gp_in_progress(rsp));
1603 raw_spin_unlock_irqrestore(&rcu_get_root(rsp)->lock, flags);
1604 wake_up(&rsp->gp_wq);
1605}
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615static void
1616rcu_report_qs_rnp(unsigned long mask, struct rcu_state *rsp,
1617 struct rcu_node *rnp, unsigned long flags)
1618 __releases(rnp->lock)
1619{
1620 struct rcu_node *rnp_c;
1621
1622
1623 for (;;) {
1624 if (!(rnp->qsmask & mask)) {
1625
1626
1627 raw_spin_unlock_irqrestore(&rnp->lock, flags);
1628 return;
1629 }
1630 rnp->qsmask &= ~mask;
1631 trace_rcu_quiescent_state_report(rsp->name, rnp->gpnum,
1632 mask, rnp->qsmask, rnp->level,
1633 rnp->grplo, rnp->grphi,
1634 !!rnp->gp_tasks);
1635 if (rnp->qsmask != 0 || rcu_preempt_blocked_readers_cgp(rnp)) {
1636
1637
1638 raw_spin_unlock_irqrestore(&rnp->lock, flags);
1639 return;
1640 }
1641 mask = rnp->grpmask;
1642 if (rnp->parent == NULL) {
1643
1644
1645
1646 break;
1647 }
1648 raw_spin_unlock_irqrestore(&rnp->lock, flags);
1649 rnp_c = rnp;
1650 rnp = rnp->parent;
1651 raw_spin_lock_irqsave(&rnp->lock, flags);
1652 WARN_ON_ONCE(rnp_c->qsmask);
1653 }
1654
1655
1656
1657
1658
1659
1660 rcu_report_qs_rsp(rsp, flags);
1661}
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672static void
1673rcu_report_qs_rdp(int cpu, struct rcu_state *rsp, struct rcu_data *rdp)
1674{
1675 unsigned long flags;
1676 unsigned long mask;
1677 struct rcu_node *rnp;
1678
1679 rnp = rdp->mynode;
1680 raw_spin_lock_irqsave(&rnp->lock, flags);
1681 if (rdp->passed_quiesce == 0 || rdp->gpnum != rnp->gpnum ||
1682 rnp->completed == rnp->gpnum) {
1683
1684
1685
1686
1687
1688
1689
1690 rdp->passed_quiesce = 0;
1691 raw_spin_unlock_irqrestore(&rnp->lock, flags);
1692 return;
1693 }
1694 mask = rdp->grpmask;
1695 if ((rnp->qsmask & mask) == 0) {
1696 raw_spin_unlock_irqrestore(&rnp->lock, flags);
1697 } else {
1698 rdp->qs_pending = 0;
1699
1700
1701
1702
1703
1704 rcu_accelerate_cbs(rsp, rnp, rdp);
1705
1706 rcu_report_qs_rnp(mask, rsp, rnp, flags);
1707 }
1708}
1709
1710
1711
1712
1713
1714
1715
1716static void
1717rcu_check_quiescent_state(struct rcu_state *rsp, struct rcu_data *rdp)
1718{
1719
1720 note_gp_changes(rsp, rdp);
1721
1722
1723
1724
1725
1726 if (!rdp->qs_pending)
1727 return;
1728
1729
1730
1731
1732
1733 if (!rdp->passed_quiesce)
1734 return;
1735
1736
1737
1738
1739
1740 rcu_report_qs_rdp(rdp->cpu, rsp, rdp);
1741}
1742
1743#ifdef CONFIG_HOTPLUG_CPU
1744
1745
1746
1747
1748
1749
1750static void
1751rcu_send_cbs_to_orphanage(int cpu, struct rcu_state *rsp,
1752 struct rcu_node *rnp, struct rcu_data *rdp)
1753{
1754
1755 if (rcu_is_nocb_cpu(rdp->cpu))
1756 return;
1757
1758
1759
1760
1761
1762
1763 if (rdp->nxtlist != NULL) {
1764 rsp->qlen_lazy += rdp->qlen_lazy;
1765 rsp->qlen += rdp->qlen;
1766 rdp->n_cbs_orphaned += rdp->qlen;
1767 rdp->qlen_lazy = 0;
1768 ACCESS_ONCE(rdp->qlen) = 0;
1769 }
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780 if (*rdp->nxttail[RCU_DONE_TAIL] != NULL) {
1781 *rsp->orphan_nxttail = *rdp->nxttail[RCU_DONE_TAIL];
1782 rsp->orphan_nxttail = rdp->nxttail[RCU_NEXT_TAIL];
1783 *rdp->nxttail[RCU_DONE_TAIL] = NULL;
1784 }
1785
1786
1787
1788
1789
1790
1791 if (rdp->nxtlist != NULL) {
1792 *rsp->orphan_donetail = rdp->nxtlist;
1793 rsp->orphan_donetail = rdp->nxttail[RCU_DONE_TAIL];
1794 }
1795
1796
1797 init_callback_list(rdp);
1798}
1799
1800
1801
1802
1803
1804static void rcu_adopt_orphan_cbs(struct rcu_state *rsp)
1805{
1806 int i;
1807 struct rcu_data *rdp = __this_cpu_ptr(rsp->rda);
1808
1809
1810 if (rcu_nocb_adopt_orphan_cbs(rsp, rdp))
1811 return;
1812
1813
1814 rdp->qlen_lazy += rsp->qlen_lazy;
1815 rdp->qlen += rsp->qlen;
1816 rdp->n_cbs_adopted += rsp->qlen;
1817 if (rsp->qlen_lazy != rsp->qlen)
1818 rcu_idle_count_callbacks_posted();
1819 rsp->qlen_lazy = 0;
1820 rsp->qlen = 0;
1821
1822
1823
1824
1825
1826
1827
1828
1829 if (rsp->orphan_donelist != NULL) {
1830 *rsp->orphan_donetail = *rdp->nxttail[RCU_DONE_TAIL];
1831 *rdp->nxttail[RCU_DONE_TAIL] = rsp->orphan_donelist;
1832 for (i = RCU_NEXT_SIZE - 1; i >= RCU_DONE_TAIL; i--)
1833 if (rdp->nxttail[i] == rdp->nxttail[RCU_DONE_TAIL])
1834 rdp->nxttail[i] = rsp->orphan_donetail;
1835 rsp->orphan_donelist = NULL;
1836 rsp->orphan_donetail = &rsp->orphan_donelist;
1837 }
1838
1839
1840 if (rsp->orphan_nxtlist != NULL) {
1841 *rdp->nxttail[RCU_NEXT_TAIL] = rsp->orphan_nxtlist;
1842 rdp->nxttail[RCU_NEXT_TAIL] = rsp->orphan_nxttail;
1843 rsp->orphan_nxtlist = NULL;
1844 rsp->orphan_nxttail = &rsp->orphan_nxtlist;
1845 }
1846}
1847
1848
1849
1850
1851static void rcu_cleanup_dying_cpu(struct rcu_state *rsp)
1852{
1853 RCU_TRACE(unsigned long mask);
1854 RCU_TRACE(struct rcu_data *rdp = this_cpu_ptr(rsp->rda));
1855 RCU_TRACE(struct rcu_node *rnp = rdp->mynode);
1856
1857 RCU_TRACE(mask = rdp->grpmask);
1858 trace_rcu_grace_period(rsp->name,
1859 rnp->gpnum + 1 - !!(rnp->qsmask & mask),
1860 "cpuofl");
1861}
1862
1863
1864
1865
1866
1867
1868
1869
1870static void rcu_cleanup_dead_cpu(int cpu, struct rcu_state *rsp)
1871{
1872 unsigned long flags;
1873 unsigned long mask;
1874 int need_report = 0;
1875 struct rcu_data *rdp = per_cpu_ptr(rsp->rda, cpu);
1876 struct rcu_node *rnp = rdp->mynode;
1877
1878
1879 rcu_boost_kthread_setaffinity(rnp, -1);
1880
1881
1882
1883
1884 mutex_lock(&rsp->onoff_mutex);
1885 raw_spin_lock_irqsave(&rsp->orphan_lock, flags);
1886
1887
1888 rcu_send_cbs_to_orphanage(cpu, rsp, rnp, rdp);
1889 rcu_adopt_orphan_cbs(rsp);
1890
1891
1892 mask = rdp->grpmask;
1893 do {
1894 raw_spin_lock(&rnp->lock);
1895 rnp->qsmaskinit &= ~mask;
1896 if (rnp->qsmaskinit != 0) {
1897 if (rnp != rdp->mynode)
1898 raw_spin_unlock(&rnp->lock);
1899 break;
1900 }
1901 if (rnp == rdp->mynode)
1902 need_report = rcu_preempt_offline_tasks(rsp, rnp, rdp);
1903 else
1904 raw_spin_unlock(&rnp->lock);
1905 mask = rnp->grpmask;
1906 rnp = rnp->parent;
1907 } while (rnp != NULL);
1908
1909
1910
1911
1912
1913
1914
1915 raw_spin_unlock(&rsp->orphan_lock);
1916 rnp = rdp->mynode;
1917 if (need_report & RCU_OFL_TASKS_NORM_GP)
1918 rcu_report_unblock_qs_rnp(rnp, flags);
1919 else
1920 raw_spin_unlock_irqrestore(&rnp->lock, flags);
1921 if (need_report & RCU_OFL_TASKS_EXP_GP)
1922 rcu_report_exp_rnp(rsp, rnp, true);
1923 WARN_ONCE(rdp->qlen != 0 || rdp->nxtlist != NULL,
1924 "rcu_cleanup_dead_cpu: Callbacks on offline CPU %d: qlen=%lu, nxtlist=%p\n",
1925 cpu, rdp->qlen, rdp->nxtlist);
1926 init_callback_list(rdp);
1927
1928 rdp->nxttail[RCU_NEXT_TAIL] = NULL;
1929 mutex_unlock(&rsp->onoff_mutex);
1930}
1931
1932#else
1933
1934static void rcu_cleanup_dying_cpu(struct rcu_state *rsp)
1935{
1936}
1937
1938static void rcu_cleanup_dead_cpu(int cpu, struct rcu_state *rsp)
1939{
1940}
1941
1942#endif
1943
1944
1945
1946
1947
1948static void rcu_do_batch(struct rcu_state *rsp, struct rcu_data *rdp)
1949{
1950 unsigned long flags;
1951 struct rcu_head *next, *list, **tail;
1952 long bl, count, count_lazy;
1953 int i;
1954
1955
1956 if (!cpu_has_callbacks_ready_to_invoke(rdp)) {
1957 trace_rcu_batch_start(rsp->name, rdp->qlen_lazy, rdp->qlen, 0);
1958 trace_rcu_batch_end(rsp->name, 0, !!ACCESS_ONCE(rdp->nxtlist),
1959 need_resched(), is_idle_task(current),
1960 rcu_is_callbacks_kthread());
1961 return;
1962 }
1963
1964
1965
1966
1967
1968 local_irq_save(flags);
1969 WARN_ON_ONCE(cpu_is_offline(smp_processor_id()));
1970 bl = rdp->blimit;
1971 trace_rcu_batch_start(rsp->name, rdp->qlen_lazy, rdp->qlen, bl);
1972 list = rdp->nxtlist;
1973 rdp->nxtlist = *rdp->nxttail[RCU_DONE_TAIL];
1974 *rdp->nxttail[RCU_DONE_TAIL] = NULL;
1975 tail = rdp->nxttail[RCU_DONE_TAIL];
1976 for (i = RCU_NEXT_SIZE - 1; i >= 0; i--)
1977 if (rdp->nxttail[i] == rdp->nxttail[RCU_DONE_TAIL])
1978 rdp->nxttail[i] = &rdp->nxtlist;
1979 local_irq_restore(flags);
1980
1981
1982 count = count_lazy = 0;
1983 while (list) {
1984 next = list->next;
1985 prefetch(next);
1986 debug_rcu_head_unqueue(list);
1987 if (__rcu_reclaim(rsp->name, list))
1988 count_lazy++;
1989 list = next;
1990
1991 if (++count >= bl &&
1992 (need_resched() ||
1993 (!is_idle_task(current) && !rcu_is_callbacks_kthread())))
1994 break;
1995 }
1996
1997 local_irq_save(flags);
1998 trace_rcu_batch_end(rsp->name, count, !!list, need_resched(),
1999 is_idle_task(current),
2000 rcu_is_callbacks_kthread());
2001
2002
2003 if (list != NULL) {
2004 *tail = rdp->nxtlist;
2005 rdp->nxtlist = list;
2006 for (i = 0; i < RCU_NEXT_SIZE; i++)
2007 if (&rdp->nxtlist == rdp->nxttail[i])
2008 rdp->nxttail[i] = tail;
2009 else
2010 break;
2011 }
2012 smp_mb();
2013 rdp->qlen_lazy -= count_lazy;
2014 ACCESS_ONCE(rdp->qlen) -= count;
2015 rdp->n_cbs_invoked += count;
2016
2017
2018 if (rdp->blimit == LONG_MAX && rdp->qlen <= qlowmark)
2019 rdp->blimit = blimit;
2020
2021
2022 if (rdp->qlen == 0 && rdp->qlen_last_fqs_check != 0) {
2023 rdp->qlen_last_fqs_check = 0;
2024 rdp->n_force_qs_snap = rsp->n_force_qs;
2025 } else if (rdp->qlen < rdp->qlen_last_fqs_check - qhimark)
2026 rdp->qlen_last_fqs_check = rdp->qlen;
2027 WARN_ON_ONCE((rdp->nxtlist == NULL) != (rdp->qlen == 0));
2028
2029 local_irq_restore(flags);
2030
2031
2032 if (cpu_has_callbacks_ready_to_invoke(rdp))
2033 invoke_rcu_core();
2034}
2035
2036
2037
2038
2039
2040
2041
2042
2043
2044
2045void rcu_check_callbacks(int cpu, int user)
2046{
2047 trace_rcu_utilization("Start scheduler-tick");
2048 increment_cpu_stall_ticks();
2049 if (user || rcu_is_cpu_rrupt_from_idle()) {
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063 rcu_sched_qs(cpu);
2064 rcu_bh_qs(cpu);
2065
2066 } else if (!in_softirq()) {
2067
2068
2069
2070
2071
2072
2073
2074
2075 rcu_bh_qs(cpu);
2076 }
2077 rcu_preempt_check_callbacks(cpu);
2078 if (rcu_pending(cpu))
2079 invoke_rcu_core();
2080 trace_rcu_utilization("End scheduler-tick");
2081}
2082
2083
2084
2085
2086
2087
2088
2089
2090static void force_qs_rnp(struct rcu_state *rsp, int (*f)(struct rcu_data *))
2091{
2092 unsigned long bit;
2093 int cpu;
2094 unsigned long flags;
2095 unsigned long mask;
2096 struct rcu_node *rnp;
2097
2098 rcu_for_each_leaf_node(rsp, rnp) {
2099 cond_resched();
2100 mask = 0;
2101 raw_spin_lock_irqsave(&rnp->lock, flags);
2102 if (!rcu_gp_in_progress(rsp)) {
2103 raw_spin_unlock_irqrestore(&rnp->lock, flags);
2104 return;
2105 }
2106 if (rnp->qsmask == 0) {
2107 rcu_initiate_boost(rnp, flags);
2108 continue;
2109 }
2110 cpu = rnp->grplo;
2111 bit = 1;
2112 for (; cpu <= rnp->grphi; cpu++, bit <<= 1) {
2113 if ((rnp->qsmask & bit) != 0 &&
2114 f(per_cpu_ptr(rsp->rda, cpu)))
2115 mask |= bit;
2116 }
2117 if (mask != 0) {
2118
2119
2120 rcu_report_qs_rnp(mask, rsp, rnp, flags);
2121 continue;
2122 }
2123 raw_spin_unlock_irqrestore(&rnp->lock, flags);
2124 }
2125 rnp = rcu_get_root(rsp);
2126 if (rnp->qsmask == 0) {
2127 raw_spin_lock_irqsave(&rnp->lock, flags);
2128 rcu_initiate_boost(rnp, flags);
2129 }
2130}
2131
2132
2133
2134
2135
2136static void force_quiescent_state(struct rcu_state *rsp)
2137{
2138 unsigned long flags;
2139 bool ret;
2140 struct rcu_node *rnp;
2141 struct rcu_node *rnp_old = NULL;
2142
2143
2144 rnp = per_cpu_ptr(rsp->rda, raw_smp_processor_id())->mynode;
2145 for (; rnp != NULL; rnp = rnp->parent) {
2146 ret = (ACCESS_ONCE(rsp->gp_flags) & RCU_GP_FLAG_FQS) ||
2147 !raw_spin_trylock(&rnp->fqslock);
2148 if (rnp_old != NULL)
2149 raw_spin_unlock(&rnp_old->fqslock);
2150 if (ret) {
2151 rsp->n_force_qs_lh++;
2152 return;
2153 }
2154 rnp_old = rnp;
2155 }
2156
2157
2158
2159 raw_spin_lock_irqsave(&rnp_old->lock, flags);
2160 raw_spin_unlock(&rnp_old->fqslock);
2161 if (ACCESS_ONCE(rsp->gp_flags) & RCU_GP_FLAG_FQS) {
2162 rsp->n_force_qs_lh++;
2163 raw_spin_unlock_irqrestore(&rnp_old->lock, flags);
2164 return;
2165 }
2166 rsp->gp_flags |= RCU_GP_FLAG_FQS;
2167 raw_spin_unlock_irqrestore(&rnp_old->lock, flags);
2168 wake_up(&rsp->gp_wq);
2169}
2170
2171
2172
2173
2174
2175
2176static void
2177__rcu_process_callbacks(struct rcu_state *rsp)
2178{
2179 unsigned long flags;
2180 struct rcu_data *rdp = __this_cpu_ptr(rsp->rda);
2181
2182 WARN_ON_ONCE(rdp->beenonline == 0);
2183
2184
2185 rcu_check_quiescent_state(rsp, rdp);
2186
2187
2188 local_irq_save(flags);
2189 if (cpu_needs_another_gp(rsp, rdp)) {
2190 raw_spin_lock(&rcu_get_root(rsp)->lock);
2191 rcu_start_gp(rsp);
2192 raw_spin_unlock_irqrestore(&rcu_get_root(rsp)->lock, flags);
2193 } else {
2194 local_irq_restore(flags);
2195 }
2196
2197
2198 if (cpu_has_callbacks_ready_to_invoke(rdp))
2199 invoke_rcu_callbacks(rsp, rdp);
2200}
2201
2202
2203
2204
2205static void rcu_process_callbacks(struct softirq_action *unused)
2206{
2207 struct rcu_state *rsp;
2208
2209 if (cpu_is_offline(smp_processor_id()))
2210 return;
2211 trace_rcu_utilization("Start RCU core");
2212 for_each_rcu_flavor(rsp)
2213 __rcu_process_callbacks(rsp);
2214 trace_rcu_utilization("End RCU core");
2215}
2216
2217
2218
2219
2220
2221
2222
2223
2224static void invoke_rcu_callbacks(struct rcu_state *rsp, struct rcu_data *rdp)
2225{
2226 if (unlikely(!ACCESS_ONCE(rcu_scheduler_fully_active)))
2227 return;
2228 if (likely(!rsp->boost)) {
2229 rcu_do_batch(rsp, rdp);
2230 return;
2231 }
2232 invoke_rcu_callbacks_kthread();
2233}
2234
2235static void invoke_rcu_core(void)
2236{
2237 if (cpu_online(smp_processor_id()))
2238 raise_softirq(RCU_SOFTIRQ);
2239}
2240
2241
2242
2243
2244static void __call_rcu_core(struct rcu_state *rsp, struct rcu_data *rdp,
2245 struct rcu_head *head, unsigned long flags)
2246{
2247
2248
2249
2250
2251 if (rcu_is_cpu_idle() && cpu_online(smp_processor_id()))
2252 invoke_rcu_core();
2253
2254
2255 if (irqs_disabled_flags(flags) || cpu_is_offline(smp_processor_id()))
2256 return;
2257
2258
2259
2260
2261
2262
2263
2264
2265 if (unlikely(rdp->qlen > rdp->qlen_last_fqs_check + qhimark)) {
2266
2267
2268 note_gp_changes(rsp, rdp);
2269
2270
2271 if (!rcu_gp_in_progress(rsp)) {
2272 struct rcu_node *rnp_root = rcu_get_root(rsp);
2273
2274 raw_spin_lock(&rnp_root->lock);
2275 rcu_start_gp(rsp);
2276 raw_spin_unlock(&rnp_root->lock);
2277 } else {
2278
2279 rdp->blimit = LONG_MAX;
2280 if (rsp->n_force_qs == rdp->n_force_qs_snap &&
2281 *rdp->nxttail[RCU_DONE_TAIL] != head)
2282 force_quiescent_state(rsp);
2283 rdp->n_force_qs_snap = rsp->n_force_qs;
2284 rdp->qlen_last_fqs_check = rdp->qlen;
2285 }
2286 }
2287}
2288
2289
2290
2291
2292
2293
2294
2295static void
2296__call_rcu(struct rcu_head *head, void (*func)(struct rcu_head *rcu),
2297 struct rcu_state *rsp, int cpu, bool lazy)
2298{
2299 unsigned long flags;
2300 struct rcu_data *rdp;
2301
2302 WARN_ON_ONCE((unsigned long)head & 0x3);
2303 debug_rcu_head_queue(head);
2304 head->func = func;
2305 head->next = NULL;
2306
2307
2308
2309
2310
2311
2312
2313 local_irq_save(flags);
2314 rdp = this_cpu_ptr(rsp->rda);
2315
2316
2317 if (unlikely(rdp->nxttail[RCU_NEXT_TAIL] == NULL) || cpu != -1) {
2318 int offline;
2319
2320 if (cpu != -1)
2321 rdp = per_cpu_ptr(rsp->rda, cpu);
2322 offline = !__call_rcu_nocb(rdp, head, lazy);
2323 WARN_ON_ONCE(offline);
2324
2325 local_irq_restore(flags);
2326 return;
2327 }
2328 ACCESS_ONCE(rdp->qlen)++;
2329 if (lazy)
2330 rdp->qlen_lazy++;
2331 else
2332 rcu_idle_count_callbacks_posted();
2333 smp_mb();
2334 *rdp->nxttail[RCU_NEXT_TAIL] = head;
2335 rdp->nxttail[RCU_NEXT_TAIL] = &head->next;
2336
2337 if (__is_kfree_rcu_offset((unsigned long)func))
2338 trace_rcu_kfree_callback(rsp->name, head, (unsigned long)func,
2339 rdp->qlen_lazy, rdp->qlen);
2340 else
2341 trace_rcu_callback(rsp->name, head, rdp->qlen_lazy, rdp->qlen);
2342
2343
2344 __call_rcu_core(rsp, rdp, head, flags);
2345 local_irq_restore(flags);
2346}
2347
2348
2349
2350
2351void call_rcu_sched(struct rcu_head *head, void (*func)(struct rcu_head *rcu))
2352{
2353 __call_rcu(head, func, &rcu_sched_state, -1, 0);
2354}
2355EXPORT_SYMBOL_GPL(call_rcu_sched);
2356
2357
2358
2359
2360void call_rcu_bh(struct rcu_head *head, void (*func)(struct rcu_head *rcu))
2361{
2362 __call_rcu(head, func, &rcu_bh_state, -1, 0);
2363}
2364EXPORT_SYMBOL_GPL(call_rcu_bh);
2365
2366
2367
2368
2369
2370
2371
2372
2373
2374
2375static inline int rcu_blocking_is_gp(void)
2376{
2377 int ret;
2378
2379 might_sleep();
2380 preempt_disable();
2381 ret = num_online_cpus() <= 1;
2382 preempt_enable();
2383 return ret;
2384}
2385
2386
2387
2388
2389
2390
2391
2392
2393
2394
2395
2396
2397
2398
2399
2400
2401
2402
2403
2404
2405
2406
2407
2408
2409
2410
2411
2412
2413
2414
2415
2416
2417
2418
2419
2420
2421
2422
2423
2424
2425
2426
2427void synchronize_sched(void)
2428{
2429 rcu_lockdep_assert(!lock_is_held(&rcu_bh_lock_map) &&
2430 !lock_is_held(&rcu_lock_map) &&
2431 !lock_is_held(&rcu_sched_lock_map),
2432 "Illegal synchronize_sched() in RCU-sched read-side critical section");
2433 if (rcu_blocking_is_gp())
2434 return;
2435 if (rcu_expedited)
2436 synchronize_sched_expedited();
2437 else
2438 wait_rcu_gp(call_rcu_sched);
2439}
2440EXPORT_SYMBOL_GPL(synchronize_sched);
2441
2442
2443
2444
2445
2446
2447
2448
2449
2450
2451
2452
2453
2454void synchronize_rcu_bh(void)
2455{
2456 rcu_lockdep_assert(!lock_is_held(&rcu_bh_lock_map) &&
2457 !lock_is_held(&rcu_lock_map) &&
2458 !lock_is_held(&rcu_sched_lock_map),
2459 "Illegal synchronize_rcu_bh() in RCU-bh read-side critical section");
2460 if (rcu_blocking_is_gp())
2461 return;
2462 if (rcu_expedited)
2463 synchronize_rcu_bh_expedited();
2464 else
2465 wait_rcu_gp(call_rcu_bh);
2466}
2467EXPORT_SYMBOL_GPL(synchronize_rcu_bh);
2468
2469static int synchronize_sched_expedited_cpu_stop(void *data)
2470{
2471
2472
2473
2474
2475
2476
2477
2478
2479
2480
2481
2482 smp_mb();
2483 return 0;
2484}
2485
2486
2487
2488
2489
2490
2491
2492
2493
2494
2495
2496
2497
2498
2499
2500
2501
2502
2503
2504
2505
2506
2507
2508
2509
2510
2511
2512
2513
2514
2515
2516
2517
2518
2519
2520
2521
2522
2523void synchronize_sched_expedited(void)
2524{
2525 long firstsnap, s, snap;
2526 int trycount = 0;
2527 struct rcu_state *rsp = &rcu_sched_state;
2528
2529
2530
2531
2532
2533
2534
2535
2536
2537 if (ULONG_CMP_GE((ulong)atomic_long_read(&rsp->expedited_start),
2538 (ulong)atomic_long_read(&rsp->expedited_done) +
2539 ULONG_MAX / 8)) {
2540 synchronize_sched();
2541 atomic_long_inc(&rsp->expedited_wrap);
2542 return;
2543 }
2544
2545
2546
2547
2548
2549 snap = atomic_long_inc_return(&rsp->expedited_start);
2550 firstsnap = snap;
2551 get_online_cpus();
2552 WARN_ON_ONCE(cpu_is_offline(raw_smp_processor_id()));
2553
2554
2555
2556
2557
2558 while (try_stop_cpus(cpu_online_mask,
2559 synchronize_sched_expedited_cpu_stop,
2560 NULL) == -EAGAIN) {
2561 put_online_cpus();
2562 atomic_long_inc(&rsp->expedited_tryfail);
2563
2564
2565 s = atomic_long_read(&rsp->expedited_done);
2566 if (ULONG_CMP_GE((ulong)s, (ulong)firstsnap)) {
2567
2568 smp_mb__before_atomic_inc();
2569 atomic_long_inc(&rsp->expedited_workdone1);
2570 return;
2571 }
2572
2573
2574 if (trycount++ < 10) {
2575 udelay(trycount * num_online_cpus());
2576 } else {
2577 wait_rcu_gp(call_rcu_sched);
2578 atomic_long_inc(&rsp->expedited_normal);
2579 return;
2580 }
2581
2582
2583 s = atomic_long_read(&rsp->expedited_done);
2584 if (ULONG_CMP_GE((ulong)s, (ulong)firstsnap)) {
2585
2586 smp_mb__before_atomic_inc();
2587 atomic_long_inc(&rsp->expedited_workdone2);
2588 return;
2589 }
2590
2591
2592
2593
2594
2595
2596
2597
2598 get_online_cpus();
2599 snap = atomic_long_read(&rsp->expedited_start);
2600 smp_mb();
2601 }
2602 atomic_long_inc(&rsp->expedited_stoppedcpus);
2603
2604
2605
2606
2607
2608
2609
2610 do {
2611 atomic_long_inc(&rsp->expedited_done_tries);
2612 s = atomic_long_read(&rsp->expedited_done);
2613 if (ULONG_CMP_GE((ulong)s, (ulong)snap)) {
2614
2615 smp_mb__before_atomic_inc();
2616 atomic_long_inc(&rsp->expedited_done_lost);
2617 break;
2618 }
2619 } while (atomic_long_cmpxchg(&rsp->expedited_done, s, snap) != s);
2620 atomic_long_inc(&rsp->expedited_done_exit);
2621
2622 put_online_cpus();
2623}
2624EXPORT_SYMBOL_GPL(synchronize_sched_expedited);
2625
2626
2627
2628
2629
2630
2631
2632
2633static int __rcu_pending(struct rcu_state *rsp, struct rcu_data *rdp)
2634{
2635 struct rcu_node *rnp = rdp->mynode;
2636
2637 rdp->n_rcu_pending++;
2638
2639
2640 check_cpu_stall(rsp, rdp);
2641
2642
2643 if (rcu_scheduler_fully_active &&
2644 rdp->qs_pending && !rdp->passed_quiesce) {
2645 rdp->n_rp_qs_pending++;
2646 } else if (rdp->qs_pending && rdp->passed_quiesce) {
2647 rdp->n_rp_report_qs++;
2648 return 1;
2649 }
2650
2651
2652 if (cpu_has_callbacks_ready_to_invoke(rdp)) {
2653 rdp->n_rp_cb_ready++;
2654 return 1;
2655 }
2656
2657
2658 if (cpu_needs_another_gp(rsp, rdp)) {
2659 rdp->n_rp_cpu_needs_gp++;
2660 return 1;
2661 }
2662
2663
2664 if (ACCESS_ONCE(rnp->completed) != rdp->completed) {
2665 rdp->n_rp_gp_completed++;
2666 return 1;
2667 }
2668
2669
2670 if (ACCESS_ONCE(rnp->gpnum) != rdp->gpnum) {
2671 rdp->n_rp_gp_started++;
2672 return 1;
2673 }
2674
2675
2676 rdp->n_rp_need_nothing++;
2677 return 0;
2678}
2679
2680
2681
2682
2683
2684
2685static int rcu_pending(int cpu)
2686{
2687 struct rcu_state *rsp;
2688
2689 for_each_rcu_flavor(rsp)
2690 if (__rcu_pending(rsp, per_cpu_ptr(rsp->rda, cpu)))
2691 return 1;
2692 return 0;
2693}
2694
2695
2696
2697
2698
2699
2700static int rcu_cpu_has_callbacks(int cpu, bool *all_lazy)
2701{
2702 bool al = true;
2703 bool hc = false;
2704 struct rcu_data *rdp;
2705 struct rcu_state *rsp;
2706
2707 for_each_rcu_flavor(rsp) {
2708 rdp = per_cpu_ptr(rsp->rda, cpu);
2709 if (rdp->qlen != rdp->qlen_lazy)
2710 al = false;
2711 if (rdp->nxtlist)
2712 hc = true;
2713 }
2714 if (all_lazy)
2715 *all_lazy = al;
2716 return hc;
2717}
2718
2719
2720
2721
2722
2723static void _rcu_barrier_trace(struct rcu_state *rsp, char *s,
2724 int cpu, unsigned long done)
2725{
2726 trace_rcu_barrier(rsp->name, s, cpu,
2727 atomic_read(&rsp->barrier_cpu_count), done);
2728}
2729
2730
2731
2732
2733
2734static void rcu_barrier_callback(struct rcu_head *rhp)
2735{
2736 struct rcu_data *rdp = container_of(rhp, struct rcu_data, barrier_head);
2737 struct rcu_state *rsp = rdp->rsp;
2738
2739 if (atomic_dec_and_test(&rsp->barrier_cpu_count)) {
2740 _rcu_barrier_trace(rsp, "LastCB", -1, rsp->n_barrier_done);
2741 complete(&rsp->barrier_completion);
2742 } else {
2743 _rcu_barrier_trace(rsp, "CB", -1, rsp->n_barrier_done);
2744 }
2745}
2746
2747
2748
2749
2750static void rcu_barrier_func(void *type)
2751{
2752 struct rcu_state *rsp = type;
2753 struct rcu_data *rdp = __this_cpu_ptr(rsp->rda);
2754
2755 _rcu_barrier_trace(rsp, "IRQ", -1, rsp->n_barrier_done);
2756 atomic_inc(&rsp->barrier_cpu_count);
2757 rsp->call(&rdp->barrier_head, rcu_barrier_callback);
2758}
2759
2760
2761
2762
2763
2764static void _rcu_barrier(struct rcu_state *rsp)
2765{
2766 int cpu;
2767 struct rcu_data *rdp;
2768 unsigned long snap = ACCESS_ONCE(rsp->n_barrier_done);
2769 unsigned long snap_done;
2770
2771 _rcu_barrier_trace(rsp, "Begin", -1, snap);
2772
2773
2774 mutex_lock(&rsp->barrier_mutex);
2775
2776
2777
2778
2779
2780 smp_mb();
2781
2782
2783
2784
2785
2786
2787
2788 snap_done = ACCESS_ONCE(rsp->n_barrier_done);
2789 _rcu_barrier_trace(rsp, "Check", -1, snap_done);
2790 if (ULONG_CMP_GE(snap_done, ((snap + 1) & ~0x1) + 2)) {
2791 _rcu_barrier_trace(rsp, "EarlyExit", -1, snap_done);
2792 smp_mb();
2793 mutex_unlock(&rsp->barrier_mutex);
2794 return;
2795 }
2796
2797
2798
2799
2800
2801
2802 ACCESS_ONCE(rsp->n_barrier_done)++;
2803 WARN_ON_ONCE((rsp->n_barrier_done & 0x1) != 1);
2804 _rcu_barrier_trace(rsp, "Inc1", -1, rsp->n_barrier_done);
2805 smp_mb();
2806
2807
2808
2809
2810
2811
2812
2813 init_completion(&rsp->barrier_completion);
2814 atomic_set(&rsp->barrier_cpu_count, 1);
2815 get_online_cpus();
2816
2817
2818
2819
2820
2821
2822 for_each_possible_cpu(cpu) {
2823 if (!cpu_online(cpu) && !rcu_is_nocb_cpu(cpu))
2824 continue;
2825 rdp = per_cpu_ptr(rsp->rda, cpu);
2826 if (rcu_is_nocb_cpu(cpu)) {
2827 _rcu_barrier_trace(rsp, "OnlineNoCB", cpu,
2828 rsp->n_barrier_done);
2829 atomic_inc(&rsp->barrier_cpu_count);
2830 __call_rcu(&rdp->barrier_head, rcu_barrier_callback,
2831 rsp, cpu, 0);
2832 } else if (ACCESS_ONCE(rdp->qlen)) {
2833 _rcu_barrier_trace(rsp, "OnlineQ", cpu,
2834 rsp->n_barrier_done);
2835 smp_call_function_single(cpu, rcu_barrier_func, rsp, 1);
2836 } else {
2837 _rcu_barrier_trace(rsp, "OnlineNQ", cpu,
2838 rsp->n_barrier_done);
2839 }
2840 }
2841 put_online_cpus();
2842
2843
2844
2845
2846
2847 if (atomic_dec_and_test(&rsp->barrier_cpu_count))
2848 complete(&rsp->barrier_completion);
2849
2850
2851 smp_mb();
2852 ACCESS_ONCE(rsp->n_barrier_done)++;
2853 WARN_ON_ONCE((rsp->n_barrier_done & 0x1) != 0);
2854 _rcu_barrier_trace(rsp, "Inc2", -1, rsp->n_barrier_done);
2855 smp_mb();
2856
2857
2858 wait_for_completion(&rsp->barrier_completion);
2859
2860
2861 mutex_unlock(&rsp->barrier_mutex);
2862}
2863
2864
2865
2866
2867void rcu_barrier_bh(void)
2868{
2869 _rcu_barrier(&rcu_bh_state);
2870}
2871EXPORT_SYMBOL_GPL(rcu_barrier_bh);
2872
2873
2874
2875
2876void rcu_barrier_sched(void)
2877{
2878 _rcu_barrier(&rcu_sched_state);
2879}
2880EXPORT_SYMBOL_GPL(rcu_barrier_sched);
2881
2882
2883
2884
2885static void __init
2886rcu_boot_init_percpu_data(int cpu, struct rcu_state *rsp)
2887{
2888 unsigned long flags;
2889 struct rcu_data *rdp = per_cpu_ptr(rsp->rda, cpu);
2890 struct rcu_node *rnp = rcu_get_root(rsp);
2891
2892
2893 raw_spin_lock_irqsave(&rnp->lock, flags);
2894 rdp->grpmask = 1UL << (cpu - rdp->mynode->grplo);
2895 init_callback_list(rdp);
2896 rdp->qlen_lazy = 0;
2897 ACCESS_ONCE(rdp->qlen) = 0;
2898 rdp->dynticks = &per_cpu(rcu_dynticks, cpu);
2899 WARN_ON_ONCE(rdp->dynticks->dynticks_nesting != DYNTICK_TASK_EXIT_IDLE);
2900 WARN_ON_ONCE(atomic_read(&rdp->dynticks->dynticks) != 1);
2901 rdp->cpu = cpu;
2902 rdp->rsp = rsp;
2903 rcu_boot_init_nocb_percpu_data(rdp);
2904 raw_spin_unlock_irqrestore(&rnp->lock, flags);
2905}
2906
2907
2908
2909
2910
2911
2912
2913static void
2914rcu_init_percpu_data(int cpu, struct rcu_state *rsp, int preemptible)
2915{
2916 unsigned long flags;
2917 unsigned long mask;
2918 struct rcu_data *rdp = per_cpu_ptr(rsp->rda, cpu);
2919 struct rcu_node *rnp = rcu_get_root(rsp);
2920
2921
2922 mutex_lock(&rsp->onoff_mutex);
2923
2924
2925 raw_spin_lock_irqsave(&rnp->lock, flags);
2926 rdp->beenonline = 1;
2927 rdp->preemptible = preemptible;
2928 rdp->qlen_last_fqs_check = 0;
2929 rdp->n_force_qs_snap = rsp->n_force_qs;
2930 rdp->blimit = blimit;
2931 init_callback_list(rdp);
2932 rdp->dynticks->dynticks_nesting = DYNTICK_TASK_EXIT_IDLE;
2933 atomic_set(&rdp->dynticks->dynticks,
2934 (atomic_read(&rdp->dynticks->dynticks) & ~0x1) + 1);
2935 raw_spin_unlock(&rnp->lock);
2936
2937
2938 rnp = rdp->mynode;
2939 mask = rdp->grpmask;
2940 do {
2941
2942 raw_spin_lock(&rnp->lock);
2943 rnp->qsmaskinit |= mask;
2944 mask = rnp->grpmask;
2945 if (rnp == rdp->mynode) {
2946
2947
2948
2949
2950
2951 rdp->gpnum = rnp->completed;
2952 rdp->completed = rnp->completed;
2953 rdp->passed_quiesce = 0;
2954 rdp->qs_pending = 0;
2955 trace_rcu_grace_period(rsp->name, rdp->gpnum, "cpuonl");
2956 }
2957 raw_spin_unlock(&rnp->lock);
2958 rnp = rnp->parent;
2959 } while (rnp != NULL && !(rnp->qsmaskinit & mask));
2960 local_irq_restore(flags);
2961
2962 mutex_unlock(&rsp->onoff_mutex);
2963}
2964
2965static void rcu_prepare_cpu(int cpu)
2966{
2967 struct rcu_state *rsp;
2968
2969 for_each_rcu_flavor(rsp)
2970 rcu_init_percpu_data(cpu, rsp,
2971 strcmp(rsp->name, "rcu_preempt") == 0);
2972}
2973
2974
2975
2976
2977static int rcu_cpu_notify(struct notifier_block *self,
2978 unsigned long action, void *hcpu)
2979{
2980 long cpu = (long)hcpu;
2981 struct rcu_data *rdp = per_cpu_ptr(rcu_state->rda, cpu);
2982 struct rcu_node *rnp = rdp->mynode;
2983 struct rcu_state *rsp;
2984
2985 trace_rcu_utilization("Start CPU hotplug");
2986 switch (action) {
2987 case CPU_UP_PREPARE:
2988 case CPU_UP_PREPARE_FROZEN:
2989 rcu_prepare_cpu(cpu);
2990 rcu_prepare_kthreads(cpu);
2991 break;
2992 case CPU_ONLINE:
2993 case CPU_DOWN_FAILED:
2994 rcu_boost_kthread_setaffinity(rnp, -1);
2995 break;
2996 case CPU_DOWN_PREPARE:
2997 rcu_boost_kthread_setaffinity(rnp, cpu);
2998 break;
2999 case CPU_DYING:
3000 case CPU_DYING_FROZEN:
3001 for_each_rcu_flavor(rsp)
3002 rcu_cleanup_dying_cpu(rsp);
3003 break;
3004 case CPU_DEAD:
3005 case CPU_DEAD_FROZEN:
3006 case CPU_UP_CANCELED:
3007 case CPU_UP_CANCELED_FROZEN:
3008 for_each_rcu_flavor(rsp)
3009 rcu_cleanup_dead_cpu(cpu, rsp);
3010 break;
3011 default:
3012 break;
3013 }
3014 trace_rcu_utilization("End CPU hotplug");
3015 return NOTIFY_OK;
3016}
3017
3018
3019
3020
3021static int __init rcu_spawn_gp_kthread(void)
3022{
3023 unsigned long flags;
3024 struct rcu_node *rnp;
3025 struct rcu_state *rsp;
3026 struct task_struct *t;
3027
3028 for_each_rcu_flavor(rsp) {
3029 t = kthread_run(rcu_gp_kthread, rsp, "%s", rsp->name);
3030 BUG_ON(IS_ERR(t));
3031 rnp = rcu_get_root(rsp);
3032 raw_spin_lock_irqsave(&rnp->lock, flags);
3033 rsp->gp_kthread = t;
3034 raw_spin_unlock_irqrestore(&rnp->lock, flags);
3035 rcu_spawn_nocb_kthreads(rsp);
3036 }
3037 return 0;
3038}
3039early_initcall(rcu_spawn_gp_kthread);
3040
3041
3042
3043
3044
3045
3046
3047
3048
3049void rcu_scheduler_starting(void)
3050{
3051 WARN_ON(num_online_cpus() != 1);
3052 WARN_ON(nr_context_switches() > 0);
3053 rcu_scheduler_active = 1;
3054}
3055
3056
3057
3058
3059
3060#ifdef CONFIG_RCU_FANOUT_EXACT
3061static void __init rcu_init_levelspread(struct rcu_state *rsp)
3062{
3063 int i;
3064
3065 for (i = rcu_num_lvls - 1; i > 0; i--)
3066 rsp->levelspread[i] = CONFIG_RCU_FANOUT;
3067 rsp->levelspread[0] = rcu_fanout_leaf;
3068}
3069#else
3070static void __init rcu_init_levelspread(struct rcu_state *rsp)
3071{
3072 int ccur;
3073 int cprv;
3074 int i;
3075
3076 cprv = nr_cpu_ids;
3077 for (i = rcu_num_lvls - 1; i >= 0; i--) {
3078 ccur = rsp->levelcnt[i];
3079 rsp->levelspread[i] = (cprv + ccur - 1) / ccur;
3080 cprv = ccur;
3081 }
3082}
3083#endif
3084
3085
3086
3087
3088static void __init rcu_init_one(struct rcu_state *rsp,
3089 struct rcu_data __percpu *rda)
3090{
3091 static char *buf[] = { "rcu_node_0",
3092 "rcu_node_1",
3093 "rcu_node_2",
3094 "rcu_node_3" };
3095 static char *fqs[] = { "rcu_node_fqs_0",
3096 "rcu_node_fqs_1",
3097 "rcu_node_fqs_2",
3098 "rcu_node_fqs_3" };
3099 int cpustride = 1;
3100 int i;
3101 int j;
3102 struct rcu_node *rnp;
3103
3104 BUILD_BUG_ON(MAX_RCU_LVLS > ARRAY_SIZE(buf));
3105
3106
3107 if (rcu_num_lvls > RCU_NUM_LVLS)
3108 panic("rcu_init_one: rcu_num_lvls overflow");
3109
3110
3111
3112 for (i = 0; i < rcu_num_lvls; i++)
3113 rsp->levelcnt[i] = num_rcu_lvl[i];
3114 for (i = 1; i < rcu_num_lvls; i++)
3115 rsp->level[i] = rsp->level[i - 1] + rsp->levelcnt[i - 1];
3116 rcu_init_levelspread(rsp);
3117
3118
3119
3120 for (i = rcu_num_lvls - 1; i >= 0; i--) {
3121 cpustride *= rsp->levelspread[i];
3122 rnp = rsp->level[i];
3123 for (j = 0; j < rsp->levelcnt[i]; j++, rnp++) {
3124 raw_spin_lock_init(&rnp->lock);
3125 lockdep_set_class_and_name(&rnp->lock,
3126 &rcu_node_class[i], buf[i]);
3127 raw_spin_lock_init(&rnp->fqslock);
3128 lockdep_set_class_and_name(&rnp->fqslock,
3129 &rcu_fqs_class[i], fqs[i]);
3130 rnp->gpnum = rsp->gpnum;
3131 rnp->completed = rsp->completed;
3132 rnp->qsmask = 0;
3133 rnp->qsmaskinit = 0;
3134 rnp->grplo = j * cpustride;
3135 rnp->grphi = (j + 1) * cpustride - 1;
3136 if (rnp->grphi >= NR_CPUS)
3137 rnp->grphi = NR_CPUS - 1;
3138 if (i == 0) {
3139 rnp->grpnum = 0;
3140 rnp->grpmask = 0;
3141 rnp->parent = NULL;
3142 } else {
3143 rnp->grpnum = j % rsp->levelspread[i - 1];
3144 rnp->grpmask = 1UL << rnp->grpnum;
3145 rnp->parent = rsp->level[i - 1] +
3146 j / rsp->levelspread[i - 1];
3147 }
3148 rnp->level = i;
3149 INIT_LIST_HEAD(&rnp->blkd_tasks);
3150 rcu_init_one_nocb(rnp);
3151 }
3152 }
3153
3154 rsp->rda = rda;
3155 init_waitqueue_head(&rsp->gp_wq);
3156 init_irq_work(&rsp->wakeup_work, rsp_wakeup);
3157 rnp = rsp->level[rcu_num_lvls - 1];
3158 for_each_possible_cpu(i) {
3159 while (i > rnp->grphi)
3160 rnp++;
3161 per_cpu_ptr(rsp->rda, i)->mynode = rnp;
3162 rcu_boot_init_percpu_data(i, rsp);
3163 }
3164 list_add(&rsp->flavors, &rcu_struct_flavors);
3165}
3166
3167
3168
3169
3170
3171
3172static void __init rcu_init_geometry(void)
3173{
3174 ulong d;
3175 int i;
3176 int j;
3177 int n = nr_cpu_ids;
3178 int rcu_capacity[MAX_RCU_LVLS + 1];
3179
3180
3181
3182
3183
3184
3185
3186
3187 d = RCU_JIFFIES_TILL_FORCE_QS + nr_cpu_ids / RCU_JIFFIES_FQS_DIV;
3188 if (jiffies_till_first_fqs == ULONG_MAX)
3189 jiffies_till_first_fqs = d;
3190 if (jiffies_till_next_fqs == ULONG_MAX)
3191 jiffies_till_next_fqs = d;
3192
3193
3194 if (rcu_fanout_leaf == CONFIG_RCU_FANOUT_LEAF &&
3195 nr_cpu_ids == NR_CPUS)
3196 return;
3197
3198
3199
3200
3201
3202
3203 rcu_capacity[0] = 1;
3204 rcu_capacity[1] = rcu_fanout_leaf;
3205 for (i = 2; i <= MAX_RCU_LVLS; i++)
3206 rcu_capacity[i] = rcu_capacity[i - 1] * CONFIG_RCU_FANOUT;
3207
3208
3209
3210
3211
3212
3213
3214
3215
3216 if (rcu_fanout_leaf < CONFIG_RCU_FANOUT_LEAF ||
3217 rcu_fanout_leaf > sizeof(unsigned long) * 8 ||
3218 n > rcu_capacity[MAX_RCU_LVLS]) {
3219 WARN_ON(1);
3220 return;
3221 }
3222
3223
3224 for (i = 1; i <= MAX_RCU_LVLS; i++)
3225 if (n <= rcu_capacity[i]) {
3226 for (j = 0; j <= i; j++)
3227 num_rcu_lvl[j] =
3228 DIV_ROUND_UP(n, rcu_capacity[i - j]);
3229 rcu_num_lvls = i;
3230 for (j = i + 1; j <= MAX_RCU_LVLS; j++)
3231 num_rcu_lvl[j] = 0;
3232 break;
3233 }
3234
3235
3236 rcu_num_nodes = 0;
3237 for (i = 0; i <= MAX_RCU_LVLS; i++)
3238 rcu_num_nodes += num_rcu_lvl[i];
3239 rcu_num_nodes -= n;
3240}
3241
3242void __init rcu_init(void)
3243{
3244 int cpu;
3245
3246 rcu_bootup_announce();
3247 rcu_init_geometry();
3248 rcu_init_one(&rcu_sched_state, &rcu_sched_data);
3249 rcu_init_one(&rcu_bh_state, &rcu_bh_data);
3250 __rcu_init_preempt();
3251 open_softirq(RCU_SOFTIRQ, rcu_process_callbacks);
3252
3253
3254
3255
3256
3257
3258 cpu_notifier(rcu_cpu_notify, 0);
3259 for_each_online_cpu(cpu)
3260 rcu_cpu_notify(NULL, CPU_UP_PREPARE, (void *)(long)cpu);
3261}
3262
3263#include "rcutree_plugin.h"
3264