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#define pr_fmt(fmt) "rcu: " fmt
30
31#include <linux/export.h>
32#include <linux/mutex.h>
33#include <linux/percpu.h>
34#include <linux/preempt.h>
35#include <linux/rcupdate_wait.h>
36#include <linux/sched.h>
37#include <linux/smp.h>
38#include <linux/delay.h>
39#include <linux/module.h>
40#include <linux/srcu.h>
41
42#include "rcu.h"
43#include "rcu_segcblist.h"
44
45
46#define DEFAULT_SRCU_EXP_HOLDOFF (25 * 1000)
47static ulong exp_holdoff = DEFAULT_SRCU_EXP_HOLDOFF;
48module_param(exp_holdoff, ulong, 0444);
49
50
51static ulong counter_wrap_check = (ULONG_MAX >> 2);
52module_param(counter_wrap_check, ulong, 0444);
53
54static void srcu_invoke_callbacks(struct work_struct *work);
55static void srcu_reschedule(struct srcu_struct *sp, unsigned long delay);
56static void process_srcu(struct work_struct *work);
57
58
59#define spin_lock_rcu_node(p) \
60do { \
61 spin_lock(&ACCESS_PRIVATE(p, lock)); \
62 smp_mb__after_unlock_lock(); \
63} while (0)
64
65#define spin_unlock_rcu_node(p) spin_unlock(&ACCESS_PRIVATE(p, lock))
66
67#define spin_lock_irq_rcu_node(p) \
68do { \
69 spin_lock_irq(&ACCESS_PRIVATE(p, lock)); \
70 smp_mb__after_unlock_lock(); \
71} while (0)
72
73#define spin_unlock_irq_rcu_node(p) \
74 spin_unlock_irq(&ACCESS_PRIVATE(p, lock))
75
76#define spin_lock_irqsave_rcu_node(p, flags) \
77do { \
78 spin_lock_irqsave(&ACCESS_PRIVATE(p, lock), flags); \
79 smp_mb__after_unlock_lock(); \
80} while (0)
81
82#define spin_unlock_irqrestore_rcu_node(p, flags) \
83 spin_unlock_irqrestore(&ACCESS_PRIVATE(p, lock), flags) \
84
85
86
87
88
89
90
91static void init_srcu_struct_nodes(struct srcu_struct *sp, bool is_static)
92{
93 int cpu;
94 int i;
95 int level = 0;
96 int levelspread[RCU_NUM_LVLS];
97 struct srcu_data *sdp;
98 struct srcu_node *snp;
99 struct srcu_node *snp_first;
100
101
102 sp->level[0] = &sp->node[0];
103 for (i = 1; i < rcu_num_lvls; i++)
104 sp->level[i] = sp->level[i - 1] + num_rcu_lvl[i - 1];
105 rcu_init_levelspread(levelspread, num_rcu_lvl);
106
107
108 rcu_for_each_node_breadth_first(sp, snp) {
109 spin_lock_init(&ACCESS_PRIVATE(snp, lock));
110 WARN_ON_ONCE(ARRAY_SIZE(snp->srcu_have_cbs) !=
111 ARRAY_SIZE(snp->srcu_data_have_cbs));
112 for (i = 0; i < ARRAY_SIZE(snp->srcu_have_cbs); i++) {
113 snp->srcu_have_cbs[i] = 0;
114 snp->srcu_data_have_cbs[i] = 0;
115 }
116 snp->srcu_gp_seq_needed_exp = 0;
117 snp->grplo = -1;
118 snp->grphi = -1;
119 if (snp == &sp->node[0]) {
120
121 snp->srcu_parent = NULL;
122 continue;
123 }
124
125
126 if (snp == sp->level[level + 1])
127 level++;
128 snp->srcu_parent = sp->level[level - 1] +
129 (snp - sp->level[level]) /
130 levelspread[level - 1];
131 }
132
133
134
135
136
137 WARN_ON_ONCE(ARRAY_SIZE(sdp->srcu_lock_count) !=
138 ARRAY_SIZE(sdp->srcu_unlock_count));
139 level = rcu_num_lvls - 1;
140 snp_first = sp->level[level];
141 for_each_possible_cpu(cpu) {
142 sdp = per_cpu_ptr(sp->sda, cpu);
143 spin_lock_init(&ACCESS_PRIVATE(sdp, lock));
144 rcu_segcblist_init(&sdp->srcu_cblist);
145 sdp->srcu_cblist_invoking = false;
146 sdp->srcu_gp_seq_needed = sp->srcu_gp_seq;
147 sdp->srcu_gp_seq_needed_exp = sp->srcu_gp_seq;
148 sdp->mynode = &snp_first[cpu / levelspread[level]];
149 for (snp = sdp->mynode; snp != NULL; snp = snp->srcu_parent) {
150 if (snp->grplo < 0)
151 snp->grplo = cpu;
152 snp->grphi = cpu;
153 }
154 sdp->cpu = cpu;
155 INIT_DELAYED_WORK(&sdp->work, srcu_invoke_callbacks);
156 sdp->sp = sp;
157 sdp->grpmask = 1 << (cpu - sdp->mynode->grplo);
158 if (is_static)
159 continue;
160
161
162 for (i = 0; i < ARRAY_SIZE(sdp->srcu_lock_count); i++) {
163 sdp->srcu_lock_count[i] = 0;
164 sdp->srcu_unlock_count[i] = 0;
165 }
166 }
167}
168
169
170
171
172
173
174
175static int init_srcu_struct_fields(struct srcu_struct *sp, bool is_static)
176{
177 mutex_init(&sp->srcu_cb_mutex);
178 mutex_init(&sp->srcu_gp_mutex);
179 sp->srcu_idx = 0;
180 sp->srcu_gp_seq = 0;
181 sp->srcu_barrier_seq = 0;
182 mutex_init(&sp->srcu_barrier_mutex);
183 atomic_set(&sp->srcu_barrier_cpu_cnt, 0);
184 INIT_DELAYED_WORK(&sp->work, process_srcu);
185 if (!is_static)
186 sp->sda = alloc_percpu(struct srcu_data);
187 init_srcu_struct_nodes(sp, is_static);
188 sp->srcu_gp_seq_needed_exp = 0;
189 sp->srcu_last_gp_end = ktime_get_mono_fast_ns();
190 smp_store_release(&sp->srcu_gp_seq_needed, 0);
191 return sp->sda ? 0 : -ENOMEM;
192}
193
194#ifdef CONFIG_DEBUG_LOCK_ALLOC
195
196int __init_srcu_struct(struct srcu_struct *sp, const char *name,
197 struct lock_class_key *key)
198{
199
200 debug_check_no_locks_freed((void *)sp, sizeof(*sp));
201 lockdep_init_map(&sp->dep_map, name, key, 0);
202 spin_lock_init(&ACCESS_PRIVATE(sp, lock));
203 return init_srcu_struct_fields(sp, false);
204}
205EXPORT_SYMBOL_GPL(__init_srcu_struct);
206
207#else
208
209
210
211
212
213
214
215
216
217int init_srcu_struct(struct srcu_struct *sp)
218{
219 spin_lock_init(&ACCESS_PRIVATE(sp, lock));
220 return init_srcu_struct_fields(sp, false);
221}
222EXPORT_SYMBOL_GPL(init_srcu_struct);
223
224#endif
225
226
227
228
229
230
231
232
233
234static void check_init_srcu_struct(struct srcu_struct *sp)
235{
236 unsigned long flags;
237
238 WARN_ON_ONCE(rcu_scheduler_active == RCU_SCHEDULER_INIT);
239
240 if (!rcu_seq_state(smp_load_acquire(&sp->srcu_gp_seq_needed)))
241 return;
242 spin_lock_irqsave_rcu_node(sp, flags);
243 if (!rcu_seq_state(sp->srcu_gp_seq_needed)) {
244 spin_unlock_irqrestore_rcu_node(sp, flags);
245 return;
246 }
247 init_srcu_struct_fields(sp, true);
248 spin_unlock_irqrestore_rcu_node(sp, flags);
249}
250
251
252
253
254
255static unsigned long srcu_readers_lock_idx(struct srcu_struct *sp, int idx)
256{
257 int cpu;
258 unsigned long sum = 0;
259
260 for_each_possible_cpu(cpu) {
261 struct srcu_data *cpuc = per_cpu_ptr(sp->sda, cpu);
262
263 sum += READ_ONCE(cpuc->srcu_lock_count[idx]);
264 }
265 return sum;
266}
267
268
269
270
271
272static unsigned long srcu_readers_unlock_idx(struct srcu_struct *sp, int idx)
273{
274 int cpu;
275 unsigned long sum = 0;
276
277 for_each_possible_cpu(cpu) {
278 struct srcu_data *cpuc = per_cpu_ptr(sp->sda, cpu);
279
280 sum += READ_ONCE(cpuc->srcu_unlock_count[idx]);
281 }
282 return sum;
283}
284
285
286
287
288
289static bool srcu_readers_active_idx_check(struct srcu_struct *sp, int idx)
290{
291 unsigned long unlocks;
292
293 unlocks = srcu_readers_unlock_idx(sp, idx);
294
295
296
297
298
299
300
301
302
303
304
305
306 smp_mb();
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329 return srcu_readers_lock_idx(sp, idx) == unlocks;
330}
331
332
333
334
335
336
337
338
339
340
341static bool srcu_readers_active(struct srcu_struct *sp)
342{
343 int cpu;
344 unsigned long sum = 0;
345
346 for_each_possible_cpu(cpu) {
347 struct srcu_data *cpuc = per_cpu_ptr(sp->sda, cpu);
348
349 sum += READ_ONCE(cpuc->srcu_lock_count[0]);
350 sum += READ_ONCE(cpuc->srcu_lock_count[1]);
351 sum -= READ_ONCE(cpuc->srcu_unlock_count[0]);
352 sum -= READ_ONCE(cpuc->srcu_unlock_count[1]);
353 }
354 return sum;
355}
356
357#define SRCU_INTERVAL 1
358
359
360
361
362
363static unsigned long srcu_get_delay(struct srcu_struct *sp)
364{
365 if (ULONG_CMP_LT(READ_ONCE(sp->srcu_gp_seq),
366 READ_ONCE(sp->srcu_gp_seq_needed_exp)))
367 return 0;
368 return SRCU_INTERVAL;
369}
370
371
372void _cleanup_srcu_struct(struct srcu_struct *sp, bool quiesced)
373{
374 int cpu;
375
376 if (WARN_ON(!srcu_get_delay(sp)))
377 return;
378 if (WARN_ON(srcu_readers_active(sp)))
379 return;
380 if (quiesced) {
381 if (WARN_ON(delayed_work_pending(&sp->work)))
382 return;
383 } else {
384 flush_delayed_work(&sp->work);
385 }
386 for_each_possible_cpu(cpu)
387 if (quiesced) {
388 if (WARN_ON(delayed_work_pending(&per_cpu_ptr(sp->sda, cpu)->work)))
389 return;
390 } else {
391 flush_delayed_work(&per_cpu_ptr(sp->sda, cpu)->work);
392 }
393 if (WARN_ON(rcu_seq_state(READ_ONCE(sp->srcu_gp_seq)) != SRCU_STATE_IDLE) ||
394 WARN_ON(srcu_readers_active(sp))) {
395 pr_info("%s: Active srcu_struct %p state: %d\n",
396 __func__, sp, rcu_seq_state(READ_ONCE(sp->srcu_gp_seq)));
397 return;
398 }
399 free_percpu(sp->sda);
400 sp->sda = NULL;
401}
402EXPORT_SYMBOL_GPL(_cleanup_srcu_struct);
403
404
405
406
407
408
409int __srcu_read_lock(struct srcu_struct *sp)
410{
411 int idx;
412
413 idx = READ_ONCE(sp->srcu_idx) & 0x1;
414 this_cpu_inc(sp->sda->srcu_lock_count[idx]);
415 smp_mb();
416 return idx;
417}
418EXPORT_SYMBOL_GPL(__srcu_read_lock);
419
420
421
422
423
424
425void __srcu_read_unlock(struct srcu_struct *sp, int idx)
426{
427 smp_mb();
428 this_cpu_inc(sp->sda->srcu_unlock_count[idx]);
429}
430EXPORT_SYMBOL_GPL(__srcu_read_unlock);
431
432
433
434
435
436
437
438
439#define SRCU_RETRY_CHECK_DELAY 5
440
441
442
443
444static void srcu_gp_start(struct srcu_struct *sp)
445{
446 struct srcu_data *sdp = this_cpu_ptr(sp->sda);
447 int state;
448
449 lockdep_assert_held(&ACCESS_PRIVATE(sp, lock));
450 WARN_ON_ONCE(ULONG_CMP_GE(sp->srcu_gp_seq, sp->srcu_gp_seq_needed));
451 rcu_segcblist_advance(&sdp->srcu_cblist,
452 rcu_seq_current(&sp->srcu_gp_seq));
453 (void)rcu_segcblist_accelerate(&sdp->srcu_cblist,
454 rcu_seq_snap(&sp->srcu_gp_seq));
455 smp_mb();
456 rcu_seq_start(&sp->srcu_gp_seq);
457 state = rcu_seq_state(READ_ONCE(sp->srcu_gp_seq));
458 WARN_ON_ONCE(state != SRCU_STATE_SCAN1);
459}
460
461
462
463
464DEFINE_PER_CPU(bool, srcu_online);
465
466void srcu_online_cpu(unsigned int cpu)
467{
468 WRITE_ONCE(per_cpu(srcu_online, cpu), true);
469}
470
471void srcu_offline_cpu(unsigned int cpu)
472{
473 WRITE_ONCE(per_cpu(srcu_online, cpu), false);
474}
475
476
477
478
479
480
481static bool srcu_queue_delayed_work_on(int cpu, struct workqueue_struct *wq,
482 struct delayed_work *dwork,
483 unsigned long delay)
484{
485 bool ret;
486
487 preempt_disable();
488 if (READ_ONCE(per_cpu(srcu_online, cpu)))
489 ret = queue_delayed_work_on(cpu, wq, dwork, delay);
490 else
491 ret = queue_delayed_work(wq, dwork, delay);
492 preempt_enable();
493 return ret;
494}
495
496
497
498
499
500static void srcu_schedule_cbs_sdp(struct srcu_data *sdp, unsigned long delay)
501{
502 srcu_queue_delayed_work_on(sdp->cpu, rcu_gp_wq, &sdp->work, delay);
503}
504
505
506
507
508
509
510
511static void srcu_schedule_cbs_snp(struct srcu_struct *sp, struct srcu_node *snp,
512 unsigned long mask, unsigned long delay)
513{
514 int cpu;
515
516 for (cpu = snp->grplo; cpu <= snp->grphi; cpu++) {
517 if (!(mask & (1 << (cpu - snp->grplo))))
518 continue;
519 srcu_schedule_cbs_sdp(per_cpu_ptr(sp->sda, cpu), delay);
520 }
521}
522
523
524
525
526
527
528
529
530
531
532static void srcu_gp_end(struct srcu_struct *sp)
533{
534 unsigned long cbdelay;
535 bool cbs;
536 bool last_lvl;
537 int cpu;
538 unsigned long flags;
539 unsigned long gpseq;
540 int idx;
541 unsigned long mask;
542 struct srcu_data *sdp;
543 struct srcu_node *snp;
544
545
546 mutex_lock(&sp->srcu_cb_mutex);
547
548
549 spin_lock_irq_rcu_node(sp);
550 idx = rcu_seq_state(sp->srcu_gp_seq);
551 WARN_ON_ONCE(idx != SRCU_STATE_SCAN2);
552 cbdelay = srcu_get_delay(sp);
553 sp->srcu_last_gp_end = ktime_get_mono_fast_ns();
554 rcu_seq_end(&sp->srcu_gp_seq);
555 gpseq = rcu_seq_current(&sp->srcu_gp_seq);
556 if (ULONG_CMP_LT(sp->srcu_gp_seq_needed_exp, gpseq))
557 sp->srcu_gp_seq_needed_exp = gpseq;
558 spin_unlock_irq_rcu_node(sp);
559 mutex_unlock(&sp->srcu_gp_mutex);
560
561
562
563 idx = rcu_seq_ctr(gpseq) % ARRAY_SIZE(snp->srcu_have_cbs);
564 rcu_for_each_node_breadth_first(sp, snp) {
565 spin_lock_irq_rcu_node(snp);
566 cbs = false;
567 last_lvl = snp >= sp->level[rcu_num_lvls - 1];
568 if (last_lvl)
569 cbs = snp->srcu_have_cbs[idx] == gpseq;
570 snp->srcu_have_cbs[idx] = gpseq;
571 rcu_seq_set_state(&snp->srcu_have_cbs[idx], 1);
572 if (ULONG_CMP_LT(snp->srcu_gp_seq_needed_exp, gpseq))
573 snp->srcu_gp_seq_needed_exp = gpseq;
574 mask = snp->srcu_data_have_cbs[idx];
575 snp->srcu_data_have_cbs[idx] = 0;
576 spin_unlock_irq_rcu_node(snp);
577 if (cbs)
578 srcu_schedule_cbs_snp(sp, snp, mask, cbdelay);
579
580
581 if (!(gpseq & counter_wrap_check) && last_lvl)
582 for (cpu = snp->grplo; cpu <= snp->grphi; cpu++) {
583 sdp = per_cpu_ptr(sp->sda, cpu);
584 spin_lock_irqsave_rcu_node(sdp, flags);
585 if (ULONG_CMP_GE(gpseq,
586 sdp->srcu_gp_seq_needed + 100))
587 sdp->srcu_gp_seq_needed = gpseq;
588 if (ULONG_CMP_GE(gpseq,
589 sdp->srcu_gp_seq_needed_exp + 100))
590 sdp->srcu_gp_seq_needed_exp = gpseq;
591 spin_unlock_irqrestore_rcu_node(sdp, flags);
592 }
593 }
594
595
596 mutex_unlock(&sp->srcu_cb_mutex);
597
598
599 spin_lock_irq_rcu_node(sp);
600 gpseq = rcu_seq_current(&sp->srcu_gp_seq);
601 if (!rcu_seq_state(gpseq) &&
602 ULONG_CMP_LT(gpseq, sp->srcu_gp_seq_needed)) {
603 srcu_gp_start(sp);
604 spin_unlock_irq_rcu_node(sp);
605 srcu_reschedule(sp, 0);
606 } else {
607 spin_unlock_irq_rcu_node(sp);
608 }
609}
610
611
612
613
614
615
616
617
618static void srcu_funnel_exp_start(struct srcu_struct *sp, struct srcu_node *snp,
619 unsigned long s)
620{
621 unsigned long flags;
622
623 for (; snp != NULL; snp = snp->srcu_parent) {
624 if (rcu_seq_done(&sp->srcu_gp_seq, s) ||
625 ULONG_CMP_GE(READ_ONCE(snp->srcu_gp_seq_needed_exp), s))
626 return;
627 spin_lock_irqsave_rcu_node(snp, flags);
628 if (ULONG_CMP_GE(snp->srcu_gp_seq_needed_exp, s)) {
629 spin_unlock_irqrestore_rcu_node(snp, flags);
630 return;
631 }
632 WRITE_ONCE(snp->srcu_gp_seq_needed_exp, s);
633 spin_unlock_irqrestore_rcu_node(snp, flags);
634 }
635 spin_lock_irqsave_rcu_node(sp, flags);
636 if (ULONG_CMP_LT(sp->srcu_gp_seq_needed_exp, s))
637 sp->srcu_gp_seq_needed_exp = s;
638 spin_unlock_irqrestore_rcu_node(sp, flags);
639}
640
641
642
643
644
645
646
647
648
649
650
651static void srcu_funnel_gp_start(struct srcu_struct *sp, struct srcu_data *sdp,
652 unsigned long s, bool do_norm)
653{
654 unsigned long flags;
655 int idx = rcu_seq_ctr(s) % ARRAY_SIZE(sdp->mynode->srcu_have_cbs);
656 struct srcu_node *snp = sdp->mynode;
657 unsigned long snp_seq;
658
659
660 for (; snp != NULL; snp = snp->srcu_parent) {
661 if (rcu_seq_done(&sp->srcu_gp_seq, s) && snp != sdp->mynode)
662 return;
663 spin_lock_irqsave_rcu_node(snp, flags);
664 if (ULONG_CMP_GE(snp->srcu_have_cbs[idx], s)) {
665 snp_seq = snp->srcu_have_cbs[idx];
666 if (snp == sdp->mynode && snp_seq == s)
667 snp->srcu_data_have_cbs[idx] |= sdp->grpmask;
668 spin_unlock_irqrestore_rcu_node(snp, flags);
669 if (snp == sdp->mynode && snp_seq != s) {
670 srcu_schedule_cbs_sdp(sdp, do_norm
671 ? SRCU_INTERVAL
672 : 0);
673 return;
674 }
675 if (!do_norm)
676 srcu_funnel_exp_start(sp, snp, s);
677 return;
678 }
679 snp->srcu_have_cbs[idx] = s;
680 if (snp == sdp->mynode)
681 snp->srcu_data_have_cbs[idx] |= sdp->grpmask;
682 if (!do_norm && ULONG_CMP_LT(snp->srcu_gp_seq_needed_exp, s))
683 snp->srcu_gp_seq_needed_exp = s;
684 spin_unlock_irqrestore_rcu_node(snp, flags);
685 }
686
687
688 spin_lock_irqsave_rcu_node(sp, flags);
689 if (ULONG_CMP_LT(sp->srcu_gp_seq_needed, s)) {
690
691
692
693
694 smp_store_release(&sp->srcu_gp_seq_needed, s);
695 }
696 if (!do_norm && ULONG_CMP_LT(sp->srcu_gp_seq_needed_exp, s))
697 sp->srcu_gp_seq_needed_exp = s;
698
699
700 if (!rcu_seq_done(&sp->srcu_gp_seq, s) &&
701 rcu_seq_state(sp->srcu_gp_seq) == SRCU_STATE_IDLE) {
702 WARN_ON_ONCE(ULONG_CMP_GE(sp->srcu_gp_seq, sp->srcu_gp_seq_needed));
703 srcu_gp_start(sp);
704 queue_delayed_work(rcu_gp_wq, &sp->work, srcu_get_delay(sp));
705 }
706 spin_unlock_irqrestore_rcu_node(sp, flags);
707}
708
709
710
711
712
713
714static bool try_check_zero(struct srcu_struct *sp, int idx, int trycount)
715{
716 for (;;) {
717 if (srcu_readers_active_idx_check(sp, idx))
718 return true;
719 if (--trycount + !srcu_get_delay(sp) <= 0)
720 return false;
721 udelay(SRCU_RETRY_CHECK_DELAY);
722 }
723}
724
725
726
727
728
729
730static void srcu_flip(struct srcu_struct *sp)
731{
732
733
734
735
736
737
738
739
740 smp_mb();
741
742 WRITE_ONCE(sp->srcu_idx, sp->srcu_idx + 1);
743
744
745
746
747
748
749
750
751 smp_mb();
752}
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775static bool srcu_might_be_idle(struct srcu_struct *sp)
776{
777 unsigned long curseq;
778 unsigned long flags;
779 struct srcu_data *sdp;
780 unsigned long t;
781
782
783 local_irq_save(flags);
784 sdp = this_cpu_ptr(sp->sda);
785 if (rcu_segcblist_pend_cbs(&sdp->srcu_cblist)) {
786 local_irq_restore(flags);
787 return false;
788 }
789 local_irq_restore(flags);
790
791
792
793
794
795
796
797
798 t = ktime_get_mono_fast_ns();
799 if (exp_holdoff == 0 ||
800 time_in_range_open(t, sp->srcu_last_gp_end,
801 sp->srcu_last_gp_end + exp_holdoff))
802 return false;
803
804
805 curseq = rcu_seq_current(&sp->srcu_gp_seq);
806 smp_mb();
807 if (ULONG_CMP_LT(curseq, READ_ONCE(sp->srcu_gp_seq_needed)))
808 return false;
809 smp_mb();
810 if (curseq != rcu_seq_current(&sp->srcu_gp_seq))
811 return false;
812 return true;
813}
814
815
816
817
818static void srcu_leak_callback(struct rcu_head *rhp)
819{
820}
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850void __call_srcu(struct srcu_struct *sp, struct rcu_head *rhp,
851 rcu_callback_t func, bool do_norm)
852{
853 unsigned long flags;
854 bool needexp = false;
855 bool needgp = false;
856 unsigned long s;
857 struct srcu_data *sdp;
858
859 check_init_srcu_struct(sp);
860 if (debug_rcu_head_queue(rhp)) {
861
862 WRITE_ONCE(rhp->func, srcu_leak_callback);
863 WARN_ONCE(1, "call_srcu(): Leaked duplicate callback\n");
864 return;
865 }
866 rhp->func = func;
867 local_irq_save(flags);
868 sdp = this_cpu_ptr(sp->sda);
869 spin_lock_rcu_node(sdp);
870 rcu_segcblist_enqueue(&sdp->srcu_cblist, rhp, false);
871 rcu_segcblist_advance(&sdp->srcu_cblist,
872 rcu_seq_current(&sp->srcu_gp_seq));
873 s = rcu_seq_snap(&sp->srcu_gp_seq);
874 (void)rcu_segcblist_accelerate(&sdp->srcu_cblist, s);
875 if (ULONG_CMP_LT(sdp->srcu_gp_seq_needed, s)) {
876 sdp->srcu_gp_seq_needed = s;
877 needgp = true;
878 }
879 if (!do_norm && ULONG_CMP_LT(sdp->srcu_gp_seq_needed_exp, s)) {
880 sdp->srcu_gp_seq_needed_exp = s;
881 needexp = true;
882 }
883 spin_unlock_irqrestore_rcu_node(sdp, flags);
884 if (needgp)
885 srcu_funnel_gp_start(sp, sdp, s, do_norm);
886 else if (needexp)
887 srcu_funnel_exp_start(sp, sdp->mynode, s);
888}
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907void call_srcu(struct srcu_struct *sp, struct rcu_head *rhp,
908 rcu_callback_t func)
909{
910 __call_srcu(sp, rhp, func, true);
911}
912EXPORT_SYMBOL_GPL(call_srcu);
913
914
915
916
917static void __synchronize_srcu(struct srcu_struct *sp, bool do_norm)
918{
919 struct rcu_synchronize rcu;
920
921 RCU_LOCKDEP_WARN(lock_is_held(&sp->dep_map) ||
922 lock_is_held(&rcu_bh_lock_map) ||
923 lock_is_held(&rcu_lock_map) ||
924 lock_is_held(&rcu_sched_lock_map),
925 "Illegal synchronize_srcu() in same-type SRCU (or in RCU) read-side critical section");
926
927 if (rcu_scheduler_active == RCU_SCHEDULER_INACTIVE)
928 return;
929 might_sleep();
930 check_init_srcu_struct(sp);
931 init_completion(&rcu.completion);
932 init_rcu_head_on_stack(&rcu.head);
933 __call_srcu(sp, &rcu.head, wakeme_after_rcu, do_norm);
934 wait_for_completion(&rcu.completion);
935 destroy_rcu_head_on_stack(&rcu.head);
936
937
938
939
940
941
942
943
944 smp_mb();
945}
946
947
948
949
950
951
952
953
954
955
956
957void synchronize_srcu_expedited(struct srcu_struct *sp)
958{
959 __synchronize_srcu(sp, rcu_gp_is_normal());
960}
961EXPORT_SYMBOL_GPL(synchronize_srcu_expedited);
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007void synchronize_srcu(struct srcu_struct *sp)
1008{
1009 if (srcu_might_be_idle(sp) || rcu_gp_is_expedited())
1010 synchronize_srcu_expedited(sp);
1011 else
1012 __synchronize_srcu(sp, true);
1013}
1014EXPORT_SYMBOL_GPL(synchronize_srcu);
1015
1016
1017
1018
1019static void srcu_barrier_cb(struct rcu_head *rhp)
1020{
1021 struct srcu_data *sdp;
1022 struct srcu_struct *sp;
1023
1024 sdp = container_of(rhp, struct srcu_data, srcu_barrier_head);
1025 sp = sdp->sp;
1026 if (atomic_dec_and_test(&sp->srcu_barrier_cpu_cnt))
1027 complete(&sp->srcu_barrier_completion);
1028}
1029
1030
1031
1032
1033
1034void srcu_barrier(struct srcu_struct *sp)
1035{
1036 int cpu;
1037 struct srcu_data *sdp;
1038 unsigned long s = rcu_seq_snap(&sp->srcu_barrier_seq);
1039
1040 check_init_srcu_struct(sp);
1041 mutex_lock(&sp->srcu_barrier_mutex);
1042 if (rcu_seq_done(&sp->srcu_barrier_seq, s)) {
1043 smp_mb();
1044 mutex_unlock(&sp->srcu_barrier_mutex);
1045 return;
1046 }
1047 rcu_seq_start(&sp->srcu_barrier_seq);
1048 init_completion(&sp->srcu_barrier_completion);
1049
1050
1051 atomic_set(&sp->srcu_barrier_cpu_cnt, 1);
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061 for_each_possible_cpu(cpu) {
1062 sdp = per_cpu_ptr(sp->sda, cpu);
1063 spin_lock_irq_rcu_node(sdp);
1064 atomic_inc(&sp->srcu_barrier_cpu_cnt);
1065 sdp->srcu_barrier_head.func = srcu_barrier_cb;
1066 debug_rcu_head_queue(&sdp->srcu_barrier_head);
1067 if (!rcu_segcblist_entrain(&sdp->srcu_cblist,
1068 &sdp->srcu_barrier_head, 0)) {
1069 debug_rcu_head_unqueue(&sdp->srcu_barrier_head);
1070 atomic_dec(&sp->srcu_barrier_cpu_cnt);
1071 }
1072 spin_unlock_irq_rcu_node(sdp);
1073 }
1074
1075
1076 if (atomic_dec_and_test(&sp->srcu_barrier_cpu_cnt))
1077 complete(&sp->srcu_barrier_completion);
1078 wait_for_completion(&sp->srcu_barrier_completion);
1079
1080 rcu_seq_end(&sp->srcu_barrier_seq);
1081 mutex_unlock(&sp->srcu_barrier_mutex);
1082}
1083EXPORT_SYMBOL_GPL(srcu_barrier);
1084
1085
1086
1087
1088
1089
1090
1091
1092unsigned long srcu_batches_completed(struct srcu_struct *sp)
1093{
1094 return sp->srcu_idx;
1095}
1096EXPORT_SYMBOL_GPL(srcu_batches_completed);
1097
1098
1099
1100
1101
1102
1103static void srcu_advance_state(struct srcu_struct *sp)
1104{
1105 int idx;
1106
1107 mutex_lock(&sp->srcu_gp_mutex);
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119 idx = rcu_seq_state(smp_load_acquire(&sp->srcu_gp_seq));
1120 if (idx == SRCU_STATE_IDLE) {
1121 spin_lock_irq_rcu_node(sp);
1122 if (ULONG_CMP_GE(sp->srcu_gp_seq, sp->srcu_gp_seq_needed)) {
1123 WARN_ON_ONCE(rcu_seq_state(sp->srcu_gp_seq));
1124 spin_unlock_irq_rcu_node(sp);
1125 mutex_unlock(&sp->srcu_gp_mutex);
1126 return;
1127 }
1128 idx = rcu_seq_state(READ_ONCE(sp->srcu_gp_seq));
1129 if (idx == SRCU_STATE_IDLE)
1130 srcu_gp_start(sp);
1131 spin_unlock_irq_rcu_node(sp);
1132 if (idx != SRCU_STATE_IDLE) {
1133 mutex_unlock(&sp->srcu_gp_mutex);
1134 return;
1135 }
1136 }
1137
1138 if (rcu_seq_state(READ_ONCE(sp->srcu_gp_seq)) == SRCU_STATE_SCAN1) {
1139 idx = 1 ^ (sp->srcu_idx & 1);
1140 if (!try_check_zero(sp, idx, 1)) {
1141 mutex_unlock(&sp->srcu_gp_mutex);
1142 return;
1143 }
1144 srcu_flip(sp);
1145 rcu_seq_set_state(&sp->srcu_gp_seq, SRCU_STATE_SCAN2);
1146 }
1147
1148 if (rcu_seq_state(READ_ONCE(sp->srcu_gp_seq)) == SRCU_STATE_SCAN2) {
1149
1150
1151
1152
1153
1154 idx = 1 ^ (sp->srcu_idx & 1);
1155 if (!try_check_zero(sp, idx, 2)) {
1156 mutex_unlock(&sp->srcu_gp_mutex);
1157 return;
1158 }
1159 srcu_gp_end(sp);
1160 }
1161}
1162
1163
1164
1165
1166
1167
1168
1169static void srcu_invoke_callbacks(struct work_struct *work)
1170{
1171 bool more;
1172 struct rcu_cblist ready_cbs;
1173 struct rcu_head *rhp;
1174 struct srcu_data *sdp;
1175 struct srcu_struct *sp;
1176
1177 sdp = container_of(work, struct srcu_data, work.work);
1178 sp = sdp->sp;
1179 rcu_cblist_init(&ready_cbs);
1180 spin_lock_irq_rcu_node(sdp);
1181 rcu_segcblist_advance(&sdp->srcu_cblist,
1182 rcu_seq_current(&sp->srcu_gp_seq));
1183 if (sdp->srcu_cblist_invoking ||
1184 !rcu_segcblist_ready_cbs(&sdp->srcu_cblist)) {
1185 spin_unlock_irq_rcu_node(sdp);
1186 return;
1187 }
1188
1189
1190 sdp->srcu_cblist_invoking = true;
1191 rcu_segcblist_extract_done_cbs(&sdp->srcu_cblist, &ready_cbs);
1192 spin_unlock_irq_rcu_node(sdp);
1193 rhp = rcu_cblist_dequeue(&ready_cbs);
1194 for (; rhp != NULL; rhp = rcu_cblist_dequeue(&ready_cbs)) {
1195 debug_rcu_head_unqueue(rhp);
1196 local_bh_disable();
1197 rhp->func(rhp);
1198 local_bh_enable();
1199 }
1200
1201
1202
1203
1204
1205 spin_lock_irq_rcu_node(sdp);
1206 rcu_segcblist_insert_count(&sdp->srcu_cblist, &ready_cbs);
1207 (void)rcu_segcblist_accelerate(&sdp->srcu_cblist,
1208 rcu_seq_snap(&sp->srcu_gp_seq));
1209 sdp->srcu_cblist_invoking = false;
1210 more = rcu_segcblist_ready_cbs(&sdp->srcu_cblist);
1211 spin_unlock_irq_rcu_node(sdp);
1212 if (more)
1213 srcu_schedule_cbs_sdp(sdp, 0);
1214}
1215
1216
1217
1218
1219
1220static void srcu_reschedule(struct srcu_struct *sp, unsigned long delay)
1221{
1222 bool pushgp = true;
1223
1224 spin_lock_irq_rcu_node(sp);
1225 if (ULONG_CMP_GE(sp->srcu_gp_seq, sp->srcu_gp_seq_needed)) {
1226 if (!WARN_ON_ONCE(rcu_seq_state(sp->srcu_gp_seq))) {
1227
1228 pushgp = false;
1229 }
1230 } else if (!rcu_seq_state(sp->srcu_gp_seq)) {
1231
1232 srcu_gp_start(sp);
1233 }
1234 spin_unlock_irq_rcu_node(sp);
1235
1236 if (pushgp)
1237 queue_delayed_work(rcu_gp_wq, &sp->work, delay);
1238}
1239
1240
1241
1242
1243static void process_srcu(struct work_struct *work)
1244{
1245 struct srcu_struct *sp;
1246
1247 sp = container_of(work, struct srcu_struct, work.work);
1248
1249 srcu_advance_state(sp);
1250 srcu_reschedule(sp, srcu_get_delay(sp));
1251}
1252
1253void srcutorture_get_gp_data(enum rcutorture_type test_type,
1254 struct srcu_struct *sp, int *flags,
1255 unsigned long *gp_seq)
1256{
1257 if (test_type != SRCU_FLAVOR)
1258 return;
1259 *flags = 0;
1260 *gp_seq = rcu_seq_current(&sp->srcu_gp_seq);
1261}
1262EXPORT_SYMBOL_GPL(srcutorture_get_gp_data);
1263
1264void srcu_torture_stats_print(struct srcu_struct *sp, char *tt, char *tf)
1265{
1266 int cpu;
1267 int idx;
1268 unsigned long s0 = 0, s1 = 0;
1269
1270 idx = sp->srcu_idx & 0x1;
1271 pr_alert("%s%s Tree SRCU g%ld per-CPU(idx=%d):",
1272 tt, tf, rcu_seq_current(&sp->srcu_gp_seq), idx);
1273 for_each_possible_cpu(cpu) {
1274 unsigned long l0, l1;
1275 unsigned long u0, u1;
1276 long c0, c1;
1277 struct srcu_data *sdp;
1278
1279 sdp = per_cpu_ptr(sp->sda, cpu);
1280 u0 = sdp->srcu_unlock_count[!idx];
1281 u1 = sdp->srcu_unlock_count[idx];
1282
1283
1284
1285
1286
1287 smp_rmb();
1288
1289 l0 = sdp->srcu_lock_count[!idx];
1290 l1 = sdp->srcu_lock_count[idx];
1291
1292 c0 = l0 - u0;
1293 c1 = l1 - u1;
1294 pr_cont(" %d(%ld,%ld %1p)",
1295 cpu, c0, c1, rcu_segcblist_head(&sdp->srcu_cblist));
1296 s0 += c0;
1297 s1 += c1;
1298 }
1299 pr_cont(" T(%ld,%ld)\n", s0, s1);
1300}
1301EXPORT_SYMBOL_GPL(srcu_torture_stats_print);
1302
1303static int __init srcu_bootup_announce(void)
1304{
1305 pr_info("Hierarchical SRCU implementation.\n");
1306 if (exp_holdoff != DEFAULT_SRCU_EXP_HOLDOFF)
1307 pr_info("\tNon-default auto-expedite holdoff of %lu ns.\n", exp_holdoff);
1308 return 0;
1309}
1310early_initcall(srcu_bootup_announce);
1311