4ce3adcfa94df16ab844b8a406b55a820496d7ef
[linux-2.6.git] / kernel / rcutree.c
1 /*
2  * Read-Copy Update mechanism for mutual exclusion
3  *
4  * This program is free software; you can redistribute it and/or modify
5  * it under the terms of the GNU General Public License as published by
6  * the Free Software Foundation; either version 2 of the License, or
7  * (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software
16  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
17  *
18  * Copyright IBM Corporation, 2008
19  *
20  * Authors: Dipankar Sarma <dipankar@in.ibm.com>
21  *          Manfred Spraul <manfred@colorfullife.com>
22  *          Paul E. McKenney <paulmck@linux.vnet.ibm.com> Hierarchical version
23  *
24  * Based on the original work by Paul McKenney <paulmck@us.ibm.com>
25  * and inputs from Rusty Russell, Andrea Arcangeli and Andi Kleen.
26  *
27  * For detailed explanation of Read-Copy Update mechanism see -
28  *      Documentation/RCU
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 <asm/atomic.h>
39 #include <linux/bitops.h>
40 #include <linux/module.h>
41 #include <linux/completion.h>
42 #include <linux/moduleparam.h>
43 #include <linux/percpu.h>
44 #include <linux/notifier.h>
45 #include <linux/cpu.h>
46 #include <linux/mutex.h>
47 #include <linux/time.h>
48
49 #include "rcutree.h"
50
51 #ifdef CONFIG_DEBUG_LOCK_ALLOC
52 static struct lock_class_key rcu_lock_key;
53 struct lockdep_map rcu_lock_map =
54         STATIC_LOCKDEP_MAP_INIT("rcu_read_lock", &rcu_lock_key);
55 EXPORT_SYMBOL_GPL(rcu_lock_map);
56 #endif
57
58 /* Data structures. */
59
60 #define RCU_STATE_INITIALIZER(name) { \
61         .level = { &name.node[0] }, \
62         .levelcnt = { \
63                 NUM_RCU_LVL_0,  /* root of hierarchy. */ \
64                 NUM_RCU_LVL_1, \
65                 NUM_RCU_LVL_2, \
66                 NUM_RCU_LVL_3, /* == MAX_RCU_LVLS */ \
67         }, \
68         .signaled = RCU_SIGNAL_INIT, \
69         .gpnum = -300, \
70         .completed = -300, \
71         .onofflock = __SPIN_LOCK_UNLOCKED(&name.onofflock), \
72         .fqslock = __SPIN_LOCK_UNLOCKED(&name.fqslock), \
73         .n_force_qs = 0, \
74         .n_force_qs_ngp = 0, \
75 }
76
77 struct rcu_state rcu_sched_state = RCU_STATE_INITIALIZER(rcu_sched_state);
78 DEFINE_PER_CPU(struct rcu_data, rcu_sched_data);
79
80 struct rcu_state rcu_bh_state = RCU_STATE_INITIALIZER(rcu_bh_state);
81 DEFINE_PER_CPU(struct rcu_data, rcu_bh_data);
82
83 /*
84  * Note a quiescent state.  Because we do not need to know
85  * how many quiescent states passed, just if there was at least
86  * one since the start of the grace period, this just sets a flag.
87  */
88 void rcu_sched_qs(int cpu)
89 {
90         struct rcu_data *rdp = &per_cpu(rcu_sched_data, cpu);
91         rdp->passed_quiesc = 1;
92         rdp->passed_quiesc_completed = rdp->completed;
93 }
94
95 void rcu_bh_qs(int cpu)
96 {
97         struct rcu_data *rdp = &per_cpu(rcu_bh_data, cpu);
98         rdp->passed_quiesc = 1;
99         rdp->passed_quiesc_completed = rdp->completed;
100 }
101
102 #ifdef CONFIG_NO_HZ
103 DEFINE_PER_CPU(struct rcu_dynticks, rcu_dynticks) = {
104         .dynticks_nesting = 1,
105         .dynticks = 1,
106 };
107 #endif /* #ifdef CONFIG_NO_HZ */
108
109 static int blimit = 10;         /* Maximum callbacks per softirq. */
110 static int qhimark = 10000;     /* If this many pending, ignore blimit. */
111 static int qlowmark = 100;      /* Once only this many pending, use blimit. */
112
113 static void force_quiescent_state(struct rcu_state *rsp, int relaxed);
114 static int rcu_pending(int cpu);
115
116 /*
117  * Return the number of RCU-sched batches processed thus far for debug & stats.
118  */
119 long rcu_batches_completed_sched(void)
120 {
121         return rcu_sched_state.completed;
122 }
123 EXPORT_SYMBOL_GPL(rcu_batches_completed_sched);
124
125 /*
126  * Return the number of RCU batches processed thus far for debug & stats.
127  * @@@ placeholder, maps to rcu_batches_completed_sched().
128  */
129 long rcu_batches_completed(void)
130 {
131         return rcu_batches_completed_sched();
132 }
133 EXPORT_SYMBOL_GPL(rcu_batches_completed);
134
135 /*
136  * Return the number of RCU BH batches processed thus far for debug & stats.
137  */
138 long rcu_batches_completed_bh(void)
139 {
140         return rcu_bh_state.completed;
141 }
142 EXPORT_SYMBOL_GPL(rcu_batches_completed_bh);
143
144 /*
145  * Does the CPU have callbacks ready to be invoked?
146  */
147 static int
148 cpu_has_callbacks_ready_to_invoke(struct rcu_data *rdp)
149 {
150         return &rdp->nxtlist != rdp->nxttail[RCU_DONE_TAIL];
151 }
152
153 /*
154  * Does the current CPU require a yet-as-unscheduled grace period?
155  */
156 static int
157 cpu_needs_another_gp(struct rcu_state *rsp, struct rcu_data *rdp)
158 {
159         /* ACCESS_ONCE() because we are accessing outside of lock. */
160         return *rdp->nxttail[RCU_DONE_TAIL] &&
161                ACCESS_ONCE(rsp->completed) == ACCESS_ONCE(rsp->gpnum);
162 }
163
164 /*
165  * Return the root node of the specified rcu_state structure.
166  */
167 static struct rcu_node *rcu_get_root(struct rcu_state *rsp)
168 {
169         return &rsp->node[0];
170 }
171
172 #ifdef CONFIG_SMP
173
174 /*
175  * If the specified CPU is offline, tell the caller that it is in
176  * a quiescent state.  Otherwise, whack it with a reschedule IPI.
177  * Grace periods can end up waiting on an offline CPU when that
178  * CPU is in the process of coming online -- it will be added to the
179  * rcu_node bitmasks before it actually makes it online.  The same thing
180  * can happen while a CPU is in the process of coming online.  Because this
181  * race is quite rare, we check for it after detecting that the grace
182  * period has been delayed rather than checking each and every CPU
183  * each and every time we start a new grace period.
184  */
185 static int rcu_implicit_offline_qs(struct rcu_data *rdp)
186 {
187         /*
188          * If the CPU is offline, it is in a quiescent state.  We can
189          * trust its state not to change because interrupts are disabled.
190          */
191         if (cpu_is_offline(rdp->cpu)) {
192                 rdp->offline_fqs++;
193                 return 1;
194         }
195
196         /* The CPU is online, so send it a reschedule IPI. */
197         if (rdp->cpu != smp_processor_id())
198                 smp_send_reschedule(rdp->cpu);
199         else
200                 set_need_resched();
201         rdp->resched_ipi++;
202         return 0;
203 }
204
205 #endif /* #ifdef CONFIG_SMP */
206
207 #ifdef CONFIG_NO_HZ
208 static DEFINE_RATELIMIT_STATE(rcu_rs, 10 * HZ, 5);
209
210 /**
211  * rcu_enter_nohz - inform RCU that current CPU is entering nohz
212  *
213  * Enter nohz mode, in other words, -leave- the mode in which RCU
214  * read-side critical sections can occur.  (Though RCU read-side
215  * critical sections can occur in irq handlers in nohz mode, a possibility
216  * handled by rcu_irq_enter() and rcu_irq_exit()).
217  */
218 void rcu_enter_nohz(void)
219 {
220         unsigned long flags;
221         struct rcu_dynticks *rdtp;
222
223         smp_mb(); /* CPUs seeing ++ must see prior RCU read-side crit sects */
224         local_irq_save(flags);
225         rdtp = &__get_cpu_var(rcu_dynticks);
226         rdtp->dynticks++;
227         rdtp->dynticks_nesting--;
228         WARN_ON_RATELIMIT(rdtp->dynticks & 0x1, &rcu_rs);
229         local_irq_restore(flags);
230 }
231
232 /*
233  * rcu_exit_nohz - inform RCU that current CPU is leaving nohz
234  *
235  * Exit nohz mode, in other words, -enter- the mode in which RCU
236  * read-side critical sections normally occur.
237  */
238 void rcu_exit_nohz(void)
239 {
240         unsigned long flags;
241         struct rcu_dynticks *rdtp;
242
243         local_irq_save(flags);
244         rdtp = &__get_cpu_var(rcu_dynticks);
245         rdtp->dynticks++;
246         rdtp->dynticks_nesting++;
247         WARN_ON_RATELIMIT(!(rdtp->dynticks & 0x1), &rcu_rs);
248         local_irq_restore(flags);
249         smp_mb(); /* CPUs seeing ++ must see later RCU read-side crit sects */
250 }
251
252 /**
253  * rcu_nmi_enter - inform RCU of entry to NMI context
254  *
255  * If the CPU was idle with dynamic ticks active, and there is no
256  * irq handler running, this updates rdtp->dynticks_nmi to let the
257  * RCU grace-period handling know that the CPU is active.
258  */
259 void rcu_nmi_enter(void)
260 {
261         struct rcu_dynticks *rdtp = &__get_cpu_var(rcu_dynticks);
262
263         if (rdtp->dynticks & 0x1)
264                 return;
265         rdtp->dynticks_nmi++;
266         WARN_ON_RATELIMIT(!(rdtp->dynticks_nmi & 0x1), &rcu_rs);
267         smp_mb(); /* CPUs seeing ++ must see later RCU read-side crit sects */
268 }
269
270 /**
271  * rcu_nmi_exit - inform RCU of exit from NMI context
272  *
273  * If the CPU was idle with dynamic ticks active, and there is no
274  * irq handler running, this updates rdtp->dynticks_nmi to let the
275  * RCU grace-period handling know that the CPU is no longer active.
276  */
277 void rcu_nmi_exit(void)
278 {
279         struct rcu_dynticks *rdtp = &__get_cpu_var(rcu_dynticks);
280
281         if (rdtp->dynticks & 0x1)
282                 return;
283         smp_mb(); /* CPUs seeing ++ must see prior RCU read-side crit sects */
284         rdtp->dynticks_nmi++;
285         WARN_ON_RATELIMIT(rdtp->dynticks_nmi & 0x1, &rcu_rs);
286 }
287
288 /**
289  * rcu_irq_enter - inform RCU of entry to hard irq context
290  *
291  * If the CPU was idle with dynamic ticks active, this updates the
292  * rdtp->dynticks to let the RCU handling know that the CPU is active.
293  */
294 void rcu_irq_enter(void)
295 {
296         struct rcu_dynticks *rdtp = &__get_cpu_var(rcu_dynticks);
297
298         if (rdtp->dynticks_nesting++)
299                 return;
300         rdtp->dynticks++;
301         WARN_ON_RATELIMIT(!(rdtp->dynticks & 0x1), &rcu_rs);
302         smp_mb(); /* CPUs seeing ++ must see later RCU read-side crit sects */
303 }
304
305 /**
306  * rcu_irq_exit - inform RCU of exit from hard irq context
307  *
308  * If the CPU was idle with dynamic ticks active, update the rdp->dynticks
309  * to put let the RCU handling be aware that the CPU is going back to idle
310  * with no ticks.
311  */
312 void rcu_irq_exit(void)
313 {
314         struct rcu_dynticks *rdtp = &__get_cpu_var(rcu_dynticks);
315
316         if (--rdtp->dynticks_nesting)
317                 return;
318         smp_mb(); /* CPUs seeing ++ must see prior RCU read-side crit sects */
319         rdtp->dynticks++;
320         WARN_ON_RATELIMIT(rdtp->dynticks & 0x1, &rcu_rs);
321
322         /* If the interrupt queued a callback, get out of dyntick mode. */
323         if (__get_cpu_var(rcu_sched_data).nxtlist ||
324             __get_cpu_var(rcu_bh_data).nxtlist)
325                 set_need_resched();
326 }
327
328 /*
329  * Record the specified "completed" value, which is later used to validate
330  * dynticks counter manipulations.  Specify "rsp->completed - 1" to
331  * unconditionally invalidate any future dynticks manipulations (which is
332  * useful at the beginning of a grace period).
333  */
334 static void dyntick_record_completed(struct rcu_state *rsp, long comp)
335 {
336         rsp->dynticks_completed = comp;
337 }
338
339 #ifdef CONFIG_SMP
340
341 /*
342  * Recall the previously recorded value of the completion for dynticks.
343  */
344 static long dyntick_recall_completed(struct rcu_state *rsp)
345 {
346         return rsp->dynticks_completed;
347 }
348
349 /*
350  * Snapshot the specified CPU's dynticks counter so that we can later
351  * credit them with an implicit quiescent state.  Return 1 if this CPU
352  * is already in a quiescent state courtesy of dynticks idle mode.
353  */
354 static int dyntick_save_progress_counter(struct rcu_data *rdp)
355 {
356         int ret;
357         int snap;
358         int snap_nmi;
359
360         snap = rdp->dynticks->dynticks;
361         snap_nmi = rdp->dynticks->dynticks_nmi;
362         smp_mb();       /* Order sampling of snap with end of grace period. */
363         rdp->dynticks_snap = snap;
364         rdp->dynticks_nmi_snap = snap_nmi;
365         ret = ((snap & 0x1) == 0) && ((snap_nmi & 0x1) == 0);
366         if (ret)
367                 rdp->dynticks_fqs++;
368         return ret;
369 }
370
371 /*
372  * Return true if the specified CPU has passed through a quiescent
373  * state by virtue of being in or having passed through an dynticks
374  * idle state since the last call to dyntick_save_progress_counter()
375  * for this same CPU.
376  */
377 static int rcu_implicit_dynticks_qs(struct rcu_data *rdp)
378 {
379         long curr;
380         long curr_nmi;
381         long snap;
382         long snap_nmi;
383
384         curr = rdp->dynticks->dynticks;
385         snap = rdp->dynticks_snap;
386         curr_nmi = rdp->dynticks->dynticks_nmi;
387         snap_nmi = rdp->dynticks_nmi_snap;
388         smp_mb(); /* force ordering with cpu entering/leaving dynticks. */
389
390         /*
391          * If the CPU passed through or entered a dynticks idle phase with
392          * no active irq/NMI handlers, then we can safely pretend that the CPU
393          * already acknowledged the request to pass through a quiescent
394          * state.  Either way, that CPU cannot possibly be in an RCU
395          * read-side critical section that started before the beginning
396          * of the current RCU grace period.
397          */
398         if ((curr != snap || (curr & 0x1) == 0) &&
399             (curr_nmi != snap_nmi || (curr_nmi & 0x1) == 0)) {
400                 rdp->dynticks_fqs++;
401                 return 1;
402         }
403
404         /* Go check for the CPU being offline. */
405         return rcu_implicit_offline_qs(rdp);
406 }
407
408 #endif /* #ifdef CONFIG_SMP */
409
410 #else /* #ifdef CONFIG_NO_HZ */
411
412 static void dyntick_record_completed(struct rcu_state *rsp, long comp)
413 {
414 }
415
416 #ifdef CONFIG_SMP
417
418 /*
419  * If there are no dynticks, then the only way that a CPU can passively
420  * be in a quiescent state is to be offline.  Unlike dynticks idle, which
421  * is a point in time during the prior (already finished) grace period,
422  * an offline CPU is always in a quiescent state, and thus can be
423  * unconditionally applied.  So just return the current value of completed.
424  */
425 static long dyntick_recall_completed(struct rcu_state *rsp)
426 {
427         return rsp->completed;
428 }
429
430 static int dyntick_save_progress_counter(struct rcu_data *rdp)
431 {
432         return 0;
433 }
434
435 static int rcu_implicit_dynticks_qs(struct rcu_data *rdp)
436 {
437         return rcu_implicit_offline_qs(rdp);
438 }
439
440 #endif /* #ifdef CONFIG_SMP */
441
442 #endif /* #else #ifdef CONFIG_NO_HZ */
443
444 #ifdef CONFIG_RCU_CPU_STALL_DETECTOR
445
446 static void record_gp_stall_check_time(struct rcu_state *rsp)
447 {
448         rsp->gp_start = jiffies;
449         rsp->jiffies_stall = jiffies + RCU_SECONDS_TILL_STALL_CHECK;
450 }
451
452 static void print_other_cpu_stall(struct rcu_state *rsp)
453 {
454         int cpu;
455         long delta;
456         unsigned long flags;
457         struct rcu_node *rnp = rcu_get_root(rsp);
458         struct rcu_node *rnp_cur = rsp->level[NUM_RCU_LVLS - 1];
459         struct rcu_node *rnp_end = &rsp->node[NUM_RCU_NODES];
460
461         /* Only let one CPU complain about others per time interval. */
462
463         spin_lock_irqsave(&rnp->lock, flags);
464         delta = jiffies - rsp->jiffies_stall;
465         if (delta < RCU_STALL_RAT_DELAY || rsp->gpnum == rsp->completed) {
466                 spin_unlock_irqrestore(&rnp->lock, flags);
467                 return;
468         }
469         rsp->jiffies_stall = jiffies + RCU_SECONDS_TILL_STALL_RECHECK;
470         spin_unlock_irqrestore(&rnp->lock, flags);
471
472         /* OK, time to rat on our buddy... */
473
474         printk(KERN_ERR "INFO: RCU detected CPU stalls:");
475         for (; rnp_cur < rnp_end; rnp_cur++) {
476                 if (rnp_cur->qsmask == 0)
477                         continue;
478                 for (cpu = 0; cpu <= rnp_cur->grphi - rnp_cur->grplo; cpu++)
479                         if (rnp_cur->qsmask & (1UL << cpu))
480                                 printk(" %d", rnp_cur->grplo + cpu);
481         }
482         printk(" (detected by %d, t=%ld jiffies)\n",
483                smp_processor_id(), (long)(jiffies - rsp->gp_start));
484         force_quiescent_state(rsp, 0);  /* Kick them all. */
485 }
486
487 static void print_cpu_stall(struct rcu_state *rsp)
488 {
489         unsigned long flags;
490         struct rcu_node *rnp = rcu_get_root(rsp);
491
492         printk(KERN_ERR "INFO: RCU detected CPU %d stall (t=%lu jiffies)\n",
493                         smp_processor_id(), jiffies - rsp->gp_start);
494         dump_stack();
495         spin_lock_irqsave(&rnp->lock, flags);
496         if ((long)(jiffies - rsp->jiffies_stall) >= 0)
497                 rsp->jiffies_stall =
498                         jiffies + RCU_SECONDS_TILL_STALL_RECHECK;
499         spin_unlock_irqrestore(&rnp->lock, flags);
500         set_need_resched();  /* kick ourselves to get things going. */
501 }
502
503 static void check_cpu_stall(struct rcu_state *rsp, struct rcu_data *rdp)
504 {
505         long delta;
506         struct rcu_node *rnp;
507
508         delta = jiffies - rsp->jiffies_stall;
509         rnp = rdp->mynode;
510         if ((rnp->qsmask & rdp->grpmask) && delta >= 0) {
511
512                 /* We haven't checked in, so go dump stack. */
513                 print_cpu_stall(rsp);
514
515         } else if (rsp->gpnum != rsp->completed &&
516                    delta >= RCU_STALL_RAT_DELAY) {
517
518                 /* They had two time units to dump stack, so complain. */
519                 print_other_cpu_stall(rsp);
520         }
521 }
522
523 #else /* #ifdef CONFIG_RCU_CPU_STALL_DETECTOR */
524
525 static void record_gp_stall_check_time(struct rcu_state *rsp)
526 {
527 }
528
529 static void check_cpu_stall(struct rcu_state *rsp, struct rcu_data *rdp)
530 {
531 }
532
533 #endif /* #else #ifdef CONFIG_RCU_CPU_STALL_DETECTOR */
534
535 /*
536  * Update CPU-local rcu_data state to record the newly noticed grace period.
537  * This is used both when we started the grace period and when we notice
538  * that someone else started the grace period.
539  */
540 static void note_new_gpnum(struct rcu_state *rsp, struct rcu_data *rdp)
541 {
542         rdp->qs_pending = 1;
543         rdp->passed_quiesc = 0;
544         rdp->gpnum = rsp->gpnum;
545 }
546
547 /*
548  * Did someone else start a new RCU grace period start since we last
549  * checked?  Update local state appropriately if so.  Must be called
550  * on the CPU corresponding to rdp.
551  */
552 static int
553 check_for_new_grace_period(struct rcu_state *rsp, struct rcu_data *rdp)
554 {
555         unsigned long flags;
556         int ret = 0;
557
558         local_irq_save(flags);
559         if (rdp->gpnum != rsp->gpnum) {
560                 note_new_gpnum(rsp, rdp);
561                 ret = 1;
562         }
563         local_irq_restore(flags);
564         return ret;
565 }
566
567 /*
568  * Start a new RCU grace period if warranted, re-initializing the hierarchy
569  * in preparation for detecting the next grace period.  The caller must hold
570  * the root node's ->lock, which is released before return.  Hard irqs must
571  * be disabled.
572  */
573 static void
574 rcu_start_gp(struct rcu_state *rsp, unsigned long flags)
575         __releases(rcu_get_root(rsp)->lock)
576 {
577         struct rcu_data *rdp = rsp->rda[smp_processor_id()];
578         struct rcu_node *rnp = rcu_get_root(rsp);
579         struct rcu_node *rnp_cur;
580         struct rcu_node *rnp_end;
581
582         if (!cpu_needs_another_gp(rsp, rdp)) {
583                 spin_unlock_irqrestore(&rnp->lock, flags);
584                 return;
585         }
586
587         /* Advance to a new grace period and initialize state. */
588         rsp->gpnum++;
589         rsp->signaled = RCU_GP_INIT; /* Hold off force_quiescent_state. */
590         rsp->jiffies_force_qs = jiffies + RCU_JIFFIES_TILL_FORCE_QS;
591         record_gp_stall_check_time(rsp);
592         dyntick_record_completed(rsp, rsp->completed - 1);
593         note_new_gpnum(rsp, rdp);
594
595         /*
596          * Because we are first, we know that all our callbacks will
597          * be covered by this upcoming grace period, even the ones
598          * that were registered arbitrarily recently.
599          */
600         rdp->nxttail[RCU_NEXT_READY_TAIL] = rdp->nxttail[RCU_NEXT_TAIL];
601         rdp->nxttail[RCU_WAIT_TAIL] = rdp->nxttail[RCU_NEXT_TAIL];
602
603         /* Special-case the common single-level case. */
604         if (NUM_RCU_NODES == 1) {
605                 rnp->qsmask = rnp->qsmaskinit;
606                 rsp->signaled = RCU_SIGNAL_INIT; /* force_quiescent_state OK. */
607                 spin_unlock_irqrestore(&rnp->lock, flags);
608                 return;
609         }
610
611         spin_unlock(&rnp->lock);  /* leave irqs disabled. */
612
613
614         /* Exclude any concurrent CPU-hotplug operations. */
615         spin_lock(&rsp->onofflock);  /* irqs already disabled. */
616
617         /*
618          * Set the quiescent-state-needed bits in all the non-leaf RCU
619          * nodes for all currently online CPUs.  This operation relies
620          * on the layout of the hierarchy within the rsp->node[] array.
621          * Note that other CPUs will access only the leaves of the
622          * hierarchy, which still indicate that no grace period is in
623          * progress.  In addition, we have excluded CPU-hotplug operations.
624          *
625          * We therefore do not need to hold any locks.  Any required
626          * memory barriers will be supplied by the locks guarding the
627          * leaf rcu_nodes in the hierarchy.
628          */
629
630         rnp_end = rsp->level[NUM_RCU_LVLS - 1];
631         for (rnp_cur = &rsp->node[0]; rnp_cur < rnp_end; rnp_cur++)
632                 rnp_cur->qsmask = rnp_cur->qsmaskinit;
633
634         /*
635          * Now set up the leaf nodes.  Here we must be careful.  First,
636          * we need to hold the lock in order to exclude other CPUs, which
637          * might be contending for the leaf nodes' locks.  Second, as
638          * soon as we initialize a given leaf node, its CPUs might run
639          * up the rest of the hierarchy.  We must therefore acquire locks
640          * for each node that we touch during this stage.  (But we still
641          * are excluding CPU-hotplug operations.)
642          *
643          * Note that the grace period cannot complete until we finish
644          * the initialization process, as there will be at least one
645          * qsmask bit set in the root node until that time, namely the
646          * one corresponding to this CPU.
647          */
648         rnp_end = &rsp->node[NUM_RCU_NODES];
649         rnp_cur = rsp->level[NUM_RCU_LVLS - 1];
650         for (; rnp_cur < rnp_end; rnp_cur++) {
651                 spin_lock(&rnp_cur->lock);      /* irqs already disabled. */
652                 rnp_cur->qsmask = rnp_cur->qsmaskinit;
653                 spin_unlock(&rnp_cur->lock);    /* irqs already disabled. */
654         }
655
656         rsp->signaled = RCU_SIGNAL_INIT; /* force_quiescent_state now OK. */
657         spin_unlock_irqrestore(&rsp->onofflock, flags);
658 }
659
660 /*
661  * Advance this CPU's callbacks, but only if the current grace period
662  * has ended.  This may be called only from the CPU to whom the rdp
663  * belongs.
664  */
665 static void
666 rcu_process_gp_end(struct rcu_state *rsp, struct rcu_data *rdp)
667 {
668         long completed_snap;
669         unsigned long flags;
670
671         local_irq_save(flags);
672         completed_snap = ACCESS_ONCE(rsp->completed);  /* outside of lock. */
673
674         /* Did another grace period end? */
675         if (rdp->completed != completed_snap) {
676
677                 /* Advance callbacks.  No harm if list empty. */
678                 rdp->nxttail[RCU_DONE_TAIL] = rdp->nxttail[RCU_WAIT_TAIL];
679                 rdp->nxttail[RCU_WAIT_TAIL] = rdp->nxttail[RCU_NEXT_READY_TAIL];
680                 rdp->nxttail[RCU_NEXT_READY_TAIL] = rdp->nxttail[RCU_NEXT_TAIL];
681
682                 /* Remember that we saw this grace-period completion. */
683                 rdp->completed = completed_snap;
684         }
685         local_irq_restore(flags);
686 }
687
688 /*
689  * Similar to cpu_quiet(), for which it is a helper function.  Allows
690  * a group of CPUs to be quieted at one go, though all the CPUs in the
691  * group must be represented by the same leaf rcu_node structure.
692  * That structure's lock must be held upon entry, and it is released
693  * before return.
694  */
695 static void
696 cpu_quiet_msk(unsigned long mask, struct rcu_state *rsp, struct rcu_node *rnp,
697               unsigned long flags)
698         __releases(rnp->lock)
699 {
700         /* Walk up the rcu_node hierarchy. */
701         for (;;) {
702                 if (!(rnp->qsmask & mask)) {
703
704                         /* Our bit has already been cleared, so done. */
705                         spin_unlock_irqrestore(&rnp->lock, flags);
706                         return;
707                 }
708                 rnp->qsmask &= ~mask;
709                 if (rnp->qsmask != 0) {
710
711                         /* Other bits still set at this level, so done. */
712                         spin_unlock_irqrestore(&rnp->lock, flags);
713                         return;
714                 }
715                 mask = rnp->grpmask;
716                 if (rnp->parent == NULL) {
717
718                         /* No more levels.  Exit loop holding root lock. */
719
720                         break;
721                 }
722                 spin_unlock_irqrestore(&rnp->lock, flags);
723                 rnp = rnp->parent;
724                 spin_lock_irqsave(&rnp->lock, flags);
725         }
726
727         /*
728          * Get here if we are the last CPU to pass through a quiescent
729          * state for this grace period.  Clean up and let rcu_start_gp()
730          * start up the next grace period if one is needed.  Note that
731          * we still hold rnp->lock, as required by rcu_start_gp(), which
732          * will release it.
733          */
734         rsp->completed = rsp->gpnum;
735         rcu_process_gp_end(rsp, rsp->rda[smp_processor_id()]);
736         rcu_start_gp(rsp, flags);  /* releases rnp->lock. */
737 }
738
739 /*
740  * Record a quiescent state for the specified CPU, which must either be
741  * the current CPU or an offline CPU.  The lastcomp argument is used to
742  * make sure we are still in the grace period of interest.  We don't want
743  * to end the current grace period based on quiescent states detected in
744  * an earlier grace period!
745  */
746 static void
747 cpu_quiet(int cpu, struct rcu_state *rsp, struct rcu_data *rdp, long lastcomp)
748 {
749         unsigned long flags;
750         unsigned long mask;
751         struct rcu_node *rnp;
752
753         rnp = rdp->mynode;
754         spin_lock_irqsave(&rnp->lock, flags);
755         if (lastcomp != ACCESS_ONCE(rsp->completed)) {
756
757                 /*
758                  * Someone beat us to it for this grace period, so leave.
759                  * The race with GP start is resolved by the fact that we
760                  * hold the leaf rcu_node lock, so that the per-CPU bits
761                  * cannot yet be initialized -- so we would simply find our
762                  * CPU's bit already cleared in cpu_quiet_msk() if this race
763                  * occurred.
764                  */
765                 rdp->passed_quiesc = 0; /* try again later! */
766                 spin_unlock_irqrestore(&rnp->lock, flags);
767                 return;
768         }
769         mask = rdp->grpmask;
770         if ((rnp->qsmask & mask) == 0) {
771                 spin_unlock_irqrestore(&rnp->lock, flags);
772         } else {
773                 rdp->qs_pending = 0;
774
775                 /*
776                  * This GP can't end until cpu checks in, so all of our
777                  * callbacks can be processed during the next GP.
778                  */
779                 rdp = rsp->rda[smp_processor_id()];
780                 rdp->nxttail[RCU_NEXT_READY_TAIL] = rdp->nxttail[RCU_NEXT_TAIL];
781
782                 cpu_quiet_msk(mask, rsp, rnp, flags); /* releases rnp->lock */
783         }
784 }
785
786 /*
787  * Check to see if there is a new grace period of which this CPU
788  * is not yet aware, and if so, set up local rcu_data state for it.
789  * Otherwise, see if this CPU has just passed through its first
790  * quiescent state for this grace period, and record that fact if so.
791  */
792 static void
793 rcu_check_quiescent_state(struct rcu_state *rsp, struct rcu_data *rdp)
794 {
795         /* If there is now a new grace period, record and return. */
796         if (check_for_new_grace_period(rsp, rdp))
797                 return;
798
799         /*
800          * Does this CPU still need to do its part for current grace period?
801          * If no, return and let the other CPUs do their part as well.
802          */
803         if (!rdp->qs_pending)
804                 return;
805
806         /*
807          * Was there a quiescent state since the beginning of the grace
808          * period? If no, then exit and wait for the next call.
809          */
810         if (!rdp->passed_quiesc)
811                 return;
812
813         /* Tell RCU we are done (but cpu_quiet() will be the judge of that). */
814         cpu_quiet(rdp->cpu, rsp, rdp, rdp->passed_quiesc_completed);
815 }
816
817 #ifdef CONFIG_HOTPLUG_CPU
818
819 /*
820  * Remove the outgoing CPU from the bitmasks in the rcu_node hierarchy
821  * and move all callbacks from the outgoing CPU to the current one.
822  */
823 static void __rcu_offline_cpu(int cpu, struct rcu_state *rsp)
824 {
825         int i;
826         unsigned long flags;
827         long lastcomp;
828         unsigned long mask;
829         struct rcu_data *rdp = rsp->rda[cpu];
830         struct rcu_data *rdp_me;
831         struct rcu_node *rnp;
832
833         /* Exclude any attempts to start a new grace period. */
834         spin_lock_irqsave(&rsp->onofflock, flags);
835
836         /* Remove the outgoing CPU from the masks in the rcu_node hierarchy. */
837         rnp = rdp->mynode;
838         mask = rdp->grpmask;    /* rnp->grplo is constant. */
839         do {
840                 spin_lock(&rnp->lock);          /* irqs already disabled. */
841                 rnp->qsmaskinit &= ~mask;
842                 if (rnp->qsmaskinit != 0) {
843                         spin_unlock(&rnp->lock); /* irqs already disabled. */
844                         break;
845                 }
846                 mask = rnp->grpmask;
847                 spin_unlock(&rnp->lock);        /* irqs already disabled. */
848                 rnp = rnp->parent;
849         } while (rnp != NULL);
850         lastcomp = rsp->completed;
851
852         spin_unlock(&rsp->onofflock);           /* irqs remain disabled. */
853
854         /* Being offline is a quiescent state, so go record it. */
855         cpu_quiet(cpu, rsp, rdp, lastcomp);
856
857         /*
858          * Move callbacks from the outgoing CPU to the running CPU.
859          * Note that the outgoing CPU is now quiscent, so it is now
860          * (uncharacteristically) safe to access its rcu_data structure.
861          * Note also that we must carefully retain the order of the
862          * outgoing CPU's callbacks in order for rcu_barrier() to work
863          * correctly.  Finally, note that we start all the callbacks
864          * afresh, even those that have passed through a grace period
865          * and are therefore ready to invoke.  The theory is that hotplug
866          * events are rare, and that if they are frequent enough to
867          * indefinitely delay callbacks, you have far worse things to
868          * be worrying about.
869          */
870         rdp_me = rsp->rda[smp_processor_id()];
871         if (rdp->nxtlist != NULL) {
872                 *rdp_me->nxttail[RCU_NEXT_TAIL] = rdp->nxtlist;
873                 rdp_me->nxttail[RCU_NEXT_TAIL] = rdp->nxttail[RCU_NEXT_TAIL];
874                 rdp->nxtlist = NULL;
875                 for (i = 0; i < RCU_NEXT_SIZE; i++)
876                         rdp->nxttail[i] = &rdp->nxtlist;
877                 rdp_me->qlen += rdp->qlen;
878                 rdp->qlen = 0;
879         }
880         local_irq_restore(flags);
881 }
882
883 /*
884  * Remove the specified CPU from the RCU hierarchy and move any pending
885  * callbacks that it might have to the current CPU.  This code assumes
886  * that at least one CPU in the system will remain running at all times.
887  * Any attempt to offline -all- CPUs is likely to strand RCU callbacks.
888  */
889 static void rcu_offline_cpu(int cpu)
890 {
891         __rcu_offline_cpu(cpu, &rcu_sched_state);
892         __rcu_offline_cpu(cpu, &rcu_bh_state);
893 }
894
895 #else /* #ifdef CONFIG_HOTPLUG_CPU */
896
897 static void rcu_offline_cpu(int cpu)
898 {
899 }
900
901 #endif /* #else #ifdef CONFIG_HOTPLUG_CPU */
902
903 /*
904  * Invoke any RCU callbacks that have made it to the end of their grace
905  * period.  Thottle as specified by rdp->blimit.
906  */
907 static void rcu_do_batch(struct rcu_data *rdp)
908 {
909         unsigned long flags;
910         struct rcu_head *next, *list, **tail;
911         int count;
912
913         /* If no callbacks are ready, just return.*/
914         if (!cpu_has_callbacks_ready_to_invoke(rdp))
915                 return;
916
917         /*
918          * Extract the list of ready callbacks, disabling to prevent
919          * races with call_rcu() from interrupt handlers.
920          */
921         local_irq_save(flags);
922         list = rdp->nxtlist;
923         rdp->nxtlist = *rdp->nxttail[RCU_DONE_TAIL];
924         *rdp->nxttail[RCU_DONE_TAIL] = NULL;
925         tail = rdp->nxttail[RCU_DONE_TAIL];
926         for (count = RCU_NEXT_SIZE - 1; count >= 0; count--)
927                 if (rdp->nxttail[count] == rdp->nxttail[RCU_DONE_TAIL])
928                         rdp->nxttail[count] = &rdp->nxtlist;
929         local_irq_restore(flags);
930
931         /* Invoke callbacks. */
932         count = 0;
933         while (list) {
934                 next = list->next;
935                 prefetch(next);
936                 list->func(list);
937                 list = next;
938                 if (++count >= rdp->blimit)
939                         break;
940         }
941
942         local_irq_save(flags);
943
944         /* Update count, and requeue any remaining callbacks. */
945         rdp->qlen -= count;
946         if (list != NULL) {
947                 *tail = rdp->nxtlist;
948                 rdp->nxtlist = list;
949                 for (count = 0; count < RCU_NEXT_SIZE; count++)
950                         if (&rdp->nxtlist == rdp->nxttail[count])
951                                 rdp->nxttail[count] = tail;
952                         else
953                                 break;
954         }
955
956         /* Reinstate batch limit if we have worked down the excess. */
957         if (rdp->blimit == LONG_MAX && rdp->qlen <= qlowmark)
958                 rdp->blimit = blimit;
959
960         local_irq_restore(flags);
961
962         /* Re-raise the RCU softirq if there are callbacks remaining. */
963         if (cpu_has_callbacks_ready_to_invoke(rdp))
964                 raise_softirq(RCU_SOFTIRQ);
965 }
966
967 /*
968  * Check to see if this CPU is in a non-context-switch quiescent state
969  * (user mode or idle loop for rcu, non-softirq execution for rcu_bh).
970  * Also schedule the RCU softirq handler.
971  *
972  * This function must be called with hardirqs disabled.  It is normally
973  * invoked from the scheduling-clock interrupt.  If rcu_pending returns
974  * false, there is no point in invoking rcu_check_callbacks().
975  */
976 void rcu_check_callbacks(int cpu, int user)
977 {
978         if (!rcu_pending(cpu))
979                 return; /* if nothing for RCU to do. */
980         if (user ||
981             (idle_cpu(cpu) && rcu_scheduler_active &&
982              !in_softirq() && hardirq_count() <= (1 << HARDIRQ_SHIFT))) {
983
984                 /*
985                  * Get here if this CPU took its interrupt from user
986                  * mode or from the idle loop, and if this is not a
987                  * nested interrupt.  In this case, the CPU is in
988                  * a quiescent state, so note it.
989                  *
990                  * No memory barrier is required here because both
991                  * rcu_sched_qs() and rcu_bh_qs() reference only CPU-local
992                  * variables that other CPUs neither access nor modify,
993                  * at least not while the corresponding CPU is online.
994                  */
995
996                 rcu_sched_qs(cpu);
997                 rcu_bh_qs(cpu);
998
999         } else if (!in_softirq()) {
1000
1001                 /*
1002                  * Get here if this CPU did not take its interrupt from
1003                  * softirq, in other words, if it is not interrupting
1004                  * a rcu_bh read-side critical section.  This is an _bh
1005                  * critical section, so note it.
1006                  */
1007
1008                 rcu_bh_qs(cpu);
1009         }
1010         raise_softirq(RCU_SOFTIRQ);
1011 }
1012
1013 #ifdef CONFIG_SMP
1014
1015 /*
1016  * Scan the leaf rcu_node structures, processing dyntick state for any that
1017  * have not yet encountered a quiescent state, using the function specified.
1018  * Returns 1 if the current grace period ends while scanning (possibly
1019  * because we made it end).
1020  */
1021 static int rcu_process_dyntick(struct rcu_state *rsp, long lastcomp,
1022                                int (*f)(struct rcu_data *))
1023 {
1024         unsigned long bit;
1025         int cpu;
1026         unsigned long flags;
1027         unsigned long mask;
1028         struct rcu_node *rnp_cur = rsp->level[NUM_RCU_LVLS - 1];
1029         struct rcu_node *rnp_end = &rsp->node[NUM_RCU_NODES];
1030
1031         for (; rnp_cur < rnp_end; rnp_cur++) {
1032                 mask = 0;
1033                 spin_lock_irqsave(&rnp_cur->lock, flags);
1034                 if (rsp->completed != lastcomp) {
1035                         spin_unlock_irqrestore(&rnp_cur->lock, flags);
1036                         return 1;
1037                 }
1038                 if (rnp_cur->qsmask == 0) {
1039                         spin_unlock_irqrestore(&rnp_cur->lock, flags);
1040                         continue;
1041                 }
1042                 cpu = rnp_cur->grplo;
1043                 bit = 1;
1044                 for (; cpu <= rnp_cur->grphi; cpu++, bit <<= 1) {
1045                         if ((rnp_cur->qsmask & bit) != 0 && f(rsp->rda[cpu]))
1046                                 mask |= bit;
1047                 }
1048                 if (mask != 0 && rsp->completed == lastcomp) {
1049
1050                         /* cpu_quiet_msk() releases rnp_cur->lock. */
1051                         cpu_quiet_msk(mask, rsp, rnp_cur, flags);
1052                         continue;
1053                 }
1054                 spin_unlock_irqrestore(&rnp_cur->lock, flags);
1055         }
1056         return 0;
1057 }
1058
1059 /*
1060  * Force quiescent states on reluctant CPUs, and also detect which
1061  * CPUs are in dyntick-idle mode.
1062  */
1063 static void force_quiescent_state(struct rcu_state *rsp, int relaxed)
1064 {
1065         unsigned long flags;
1066         long lastcomp;
1067         struct rcu_node *rnp = rcu_get_root(rsp);
1068         u8 signaled;
1069
1070         if (ACCESS_ONCE(rsp->completed) == ACCESS_ONCE(rsp->gpnum))
1071                 return;  /* No grace period in progress, nothing to force. */
1072         if (!spin_trylock_irqsave(&rsp->fqslock, flags)) {
1073                 rsp->n_force_qs_lh++; /* Inexact, can lose counts.  Tough! */
1074                 return; /* Someone else is already on the job. */
1075         }
1076         if (relaxed &&
1077             (long)(rsp->jiffies_force_qs - jiffies) >= 0)
1078                 goto unlock_ret; /* no emergency and done recently. */
1079         rsp->n_force_qs++;
1080         spin_lock(&rnp->lock);
1081         lastcomp = rsp->completed;
1082         signaled = rsp->signaled;
1083         rsp->jiffies_force_qs = jiffies + RCU_JIFFIES_TILL_FORCE_QS;
1084         if (lastcomp == rsp->gpnum) {
1085                 rsp->n_force_qs_ngp++;
1086                 spin_unlock(&rnp->lock);
1087                 goto unlock_ret;  /* no GP in progress, time updated. */
1088         }
1089         spin_unlock(&rnp->lock);
1090         switch (signaled) {
1091         case RCU_GP_INIT:
1092
1093                 break; /* grace period still initializing, ignore. */
1094
1095         case RCU_SAVE_DYNTICK:
1096
1097                 if (RCU_SIGNAL_INIT != RCU_SAVE_DYNTICK)
1098                         break; /* So gcc recognizes the dead code. */
1099
1100                 /* Record dyntick-idle state. */
1101                 if (rcu_process_dyntick(rsp, lastcomp,
1102                                         dyntick_save_progress_counter))
1103                         goto unlock_ret;
1104
1105                 /* Update state, record completion counter. */
1106                 spin_lock(&rnp->lock);
1107                 if (lastcomp == rsp->completed) {
1108                         rsp->signaled = RCU_FORCE_QS;
1109                         dyntick_record_completed(rsp, lastcomp);
1110                 }
1111                 spin_unlock(&rnp->lock);
1112                 break;
1113
1114         case RCU_FORCE_QS:
1115
1116                 /* Check dyntick-idle state, send IPI to laggarts. */
1117                 if (rcu_process_dyntick(rsp, dyntick_recall_completed(rsp),
1118                                         rcu_implicit_dynticks_qs))
1119                         goto unlock_ret;
1120
1121                 /* Leave state in case more forcing is required. */
1122
1123                 break;
1124         }
1125 unlock_ret:
1126         spin_unlock_irqrestore(&rsp->fqslock, flags);
1127 }
1128
1129 #else /* #ifdef CONFIG_SMP */
1130
1131 static void force_quiescent_state(struct rcu_state *rsp, int relaxed)
1132 {
1133         set_need_resched();
1134 }
1135
1136 #endif /* #else #ifdef CONFIG_SMP */
1137
1138 /*
1139  * This does the RCU processing work from softirq context for the
1140  * specified rcu_state and rcu_data structures.  This may be called
1141  * only from the CPU to whom the rdp belongs.
1142  */
1143 static void
1144 __rcu_process_callbacks(struct rcu_state *rsp, struct rcu_data *rdp)
1145 {
1146         unsigned long flags;
1147
1148         WARN_ON_ONCE(rdp->beenonline == 0);
1149
1150         /*
1151          * If an RCU GP has gone long enough, go check for dyntick
1152          * idle CPUs and, if needed, send resched IPIs.
1153          */
1154         if ((long)(ACCESS_ONCE(rsp->jiffies_force_qs) - jiffies) < 0)
1155                 force_quiescent_state(rsp, 1);
1156
1157         /*
1158          * Advance callbacks in response to end of earlier grace
1159          * period that some other CPU ended.
1160          */
1161         rcu_process_gp_end(rsp, rdp);
1162
1163         /* Update RCU state based on any recent quiescent states. */
1164         rcu_check_quiescent_state(rsp, rdp);
1165
1166         /* Does this CPU require a not-yet-started grace period? */
1167         if (cpu_needs_another_gp(rsp, rdp)) {
1168                 spin_lock_irqsave(&rcu_get_root(rsp)->lock, flags);
1169                 rcu_start_gp(rsp, flags);  /* releases above lock */
1170         }
1171
1172         /* If there are callbacks ready, invoke them. */
1173         rcu_do_batch(rdp);
1174 }
1175
1176 /*
1177  * Do softirq processing for the current CPU.
1178  */
1179 static void rcu_process_callbacks(struct softirq_action *unused)
1180 {
1181         /*
1182          * Memory references from any prior RCU read-side critical sections
1183          * executed by the interrupted code must be seen before any RCU
1184          * grace-period manipulations below.
1185          */
1186         smp_mb(); /* See above block comment. */
1187
1188         __rcu_process_callbacks(&rcu_sched_state,
1189                                 &__get_cpu_var(rcu_sched_data));
1190         __rcu_process_callbacks(&rcu_bh_state, &__get_cpu_var(rcu_bh_data));
1191
1192         /*
1193          * Memory references from any later RCU read-side critical sections
1194          * executed by the interrupted code must be seen after any RCU
1195          * grace-period manipulations above.
1196          */
1197         smp_mb(); /* See above block comment. */
1198 }
1199
1200 static void
1201 __call_rcu(struct rcu_head *head, void (*func)(struct rcu_head *rcu),
1202            struct rcu_state *rsp)
1203 {
1204         unsigned long flags;
1205         struct rcu_data *rdp;
1206
1207         head->func = func;
1208         head->next = NULL;
1209
1210         smp_mb(); /* Ensure RCU update seen before callback registry. */
1211
1212         /*
1213          * Opportunistically note grace-period endings and beginnings.
1214          * Note that we might see a beginning right after we see an
1215          * end, but never vice versa, since this CPU has to pass through
1216          * a quiescent state betweentimes.
1217          */
1218         local_irq_save(flags);
1219         rdp = rsp->rda[smp_processor_id()];
1220         rcu_process_gp_end(rsp, rdp);
1221         check_for_new_grace_period(rsp, rdp);
1222
1223         /* Add the callback to our list. */
1224         *rdp->nxttail[RCU_NEXT_TAIL] = head;
1225         rdp->nxttail[RCU_NEXT_TAIL] = &head->next;
1226
1227         /* Start a new grace period if one not already started. */
1228         if (ACCESS_ONCE(rsp->completed) == ACCESS_ONCE(rsp->gpnum)) {
1229                 unsigned long nestflag;
1230                 struct rcu_node *rnp_root = rcu_get_root(rsp);
1231
1232                 spin_lock_irqsave(&rnp_root->lock, nestflag);
1233                 rcu_start_gp(rsp, nestflag);  /* releases rnp_root->lock. */
1234         }
1235
1236         /* Force the grace period if too many callbacks or too long waiting. */
1237         if (unlikely(++rdp->qlen > qhimark)) {
1238                 rdp->blimit = LONG_MAX;
1239                 force_quiescent_state(rsp, 0);
1240         } else if ((long)(ACCESS_ONCE(rsp->jiffies_force_qs) - jiffies) < 0)
1241                 force_quiescent_state(rsp, 1);
1242         local_irq_restore(flags);
1243 }
1244
1245 /*
1246  * Queue an RCU-sched callback for invocation after a grace period.
1247  */
1248 void call_rcu_sched(struct rcu_head *head, void (*func)(struct rcu_head *rcu))
1249 {
1250         __call_rcu(head, func, &rcu_sched_state);
1251 }
1252 EXPORT_SYMBOL_GPL(call_rcu_sched);
1253
1254 /*
1255  * @@@ Queue an RCU callback for invocation after a grace period.
1256  * @@@ Placeholder pending rcutree_plugin.h.
1257  */
1258 void call_rcu(struct rcu_head *head, void (*func)(struct rcu_head *rcu))
1259 {
1260         call_rcu_sched(head, func);
1261 }
1262 EXPORT_SYMBOL_GPL(call_rcu);
1263
1264
1265 /*
1266  * Queue an RCU for invocation after a quicker grace period.
1267  */
1268 void call_rcu_bh(struct rcu_head *head, void (*func)(struct rcu_head *rcu))
1269 {
1270         __call_rcu(head, func, &rcu_bh_state);
1271 }
1272 EXPORT_SYMBOL_GPL(call_rcu_bh);
1273
1274 /*
1275  * Check to see if there is any immediate RCU-related work to be done
1276  * by the current CPU, for the specified type of RCU, returning 1 if so.
1277  * The checks are in order of increasing expense: checks that can be
1278  * carried out against CPU-local state are performed first.  However,
1279  * we must check for CPU stalls first, else we might not get a chance.
1280  */
1281 static int __rcu_pending(struct rcu_state *rsp, struct rcu_data *rdp)
1282 {
1283         rdp->n_rcu_pending++;
1284
1285         /* Check for CPU stalls, if enabled. */
1286         check_cpu_stall(rsp, rdp);
1287
1288         /* Is the RCU core waiting for a quiescent state from this CPU? */
1289         if (rdp->qs_pending) {
1290                 rdp->n_rp_qs_pending++;
1291                 return 1;
1292         }
1293
1294         /* Does this CPU have callbacks ready to invoke? */
1295         if (cpu_has_callbacks_ready_to_invoke(rdp)) {
1296                 rdp->n_rp_cb_ready++;
1297                 return 1;
1298         }
1299
1300         /* Has RCU gone idle with this CPU needing another grace period? */
1301         if (cpu_needs_another_gp(rsp, rdp)) {
1302                 rdp->n_rp_cpu_needs_gp++;
1303                 return 1;
1304         }
1305
1306         /* Has another RCU grace period completed?  */
1307         if (ACCESS_ONCE(rsp->completed) != rdp->completed) { /* outside lock */
1308                 rdp->n_rp_gp_completed++;
1309                 return 1;
1310         }
1311
1312         /* Has a new RCU grace period started? */
1313         if (ACCESS_ONCE(rsp->gpnum) != rdp->gpnum) { /* outside lock */
1314                 rdp->n_rp_gp_started++;
1315                 return 1;
1316         }
1317
1318         /* Has an RCU GP gone long enough to send resched IPIs &c? */
1319         if (ACCESS_ONCE(rsp->completed) != ACCESS_ONCE(rsp->gpnum) &&
1320             ((long)(ACCESS_ONCE(rsp->jiffies_force_qs) - jiffies) < 0)) {
1321                 rdp->n_rp_need_fqs++;
1322                 return 1;
1323         }
1324
1325         /* nothing to do */
1326         rdp->n_rp_need_nothing++;
1327         return 0;
1328 }
1329
1330 /*
1331  * Check to see if there is any immediate RCU-related work to be done
1332  * by the current CPU, returning 1 if so.  This function is part of the
1333  * RCU implementation; it is -not- an exported member of the RCU API.
1334  */
1335 static int rcu_pending(int cpu)
1336 {
1337         return __rcu_pending(&rcu_sched_state, &per_cpu(rcu_sched_data, cpu)) ||
1338                __rcu_pending(&rcu_bh_state, &per_cpu(rcu_bh_data, cpu));
1339 }
1340
1341 /*
1342  * Check to see if any future RCU-related work will need to be done
1343  * by the current CPU, even if none need be done immediately, returning
1344  * 1 if so.  This function is part of the RCU implementation; it is -not-
1345  * an exported member of the RCU API.
1346  */
1347 int rcu_needs_cpu(int cpu)
1348 {
1349         /* RCU callbacks either ready or pending? */
1350         return per_cpu(rcu_sched_data, cpu).nxtlist ||
1351                per_cpu(rcu_bh_data, cpu).nxtlist;
1352 }
1353
1354 /*
1355  * Do boot-time initialization of a CPU's per-CPU RCU data.
1356  */
1357 static void __init
1358 rcu_boot_init_percpu_data(int cpu, struct rcu_state *rsp)
1359 {
1360         unsigned long flags;
1361         int i;
1362         struct rcu_data *rdp = rsp->rda[cpu];
1363         struct rcu_node *rnp = rcu_get_root(rsp);
1364
1365         /* Set up local state, ensuring consistent view of global state. */
1366         spin_lock_irqsave(&rnp->lock, flags);
1367         rdp->grpmask = 1UL << (cpu - rdp->mynode->grplo);
1368         rdp->nxtlist = NULL;
1369         for (i = 0; i < RCU_NEXT_SIZE; i++)
1370                 rdp->nxttail[i] = &rdp->nxtlist;
1371         rdp->qlen = 0;
1372 #ifdef CONFIG_NO_HZ
1373         rdp->dynticks = &per_cpu(rcu_dynticks, cpu);
1374 #endif /* #ifdef CONFIG_NO_HZ */
1375         rdp->cpu = cpu;
1376         spin_unlock_irqrestore(&rnp->lock, flags);
1377 }
1378
1379 /*
1380  * Initialize a CPU's per-CPU RCU data.  Note that only one online or
1381  * offline event can be happening at a given time.  Note also that we
1382  * can accept some slop in the rsp->completed access due to the fact
1383  * that this CPU cannot possibly have any RCU callbacks in flight yet.
1384  */
1385 static void __cpuinit
1386 rcu_init_percpu_data(int cpu, struct rcu_state *rsp)
1387 {
1388         unsigned long flags;
1389         long lastcomp;
1390         unsigned long mask;
1391         struct rcu_data *rdp = rsp->rda[cpu];
1392         struct rcu_node *rnp = rcu_get_root(rsp);
1393
1394         /* Set up local state, ensuring consistent view of global state. */
1395         spin_lock_irqsave(&rnp->lock, flags);
1396         lastcomp = rsp->completed;
1397         rdp->completed = lastcomp;
1398         rdp->gpnum = lastcomp;
1399         rdp->passed_quiesc = 0;  /* We could be racing with new GP, */
1400         rdp->qs_pending = 1;     /*  so set up to respond to current GP. */
1401         rdp->beenonline = 1;     /* We have now been online. */
1402         rdp->passed_quiesc_completed = lastcomp - 1;
1403         rdp->blimit = blimit;
1404         spin_unlock(&rnp->lock);                /* irqs remain disabled. */
1405
1406         /*
1407          * A new grace period might start here.  If so, we won't be part
1408          * of it, but that is OK, as we are currently in a quiescent state.
1409          */
1410
1411         /* Exclude any attempts to start a new GP on large systems. */
1412         spin_lock(&rsp->onofflock);             /* irqs already disabled. */
1413
1414         /* Add CPU to rcu_node bitmasks. */
1415         rnp = rdp->mynode;
1416         mask = rdp->grpmask;
1417         do {
1418                 /* Exclude any attempts to start a new GP on small systems. */
1419                 spin_lock(&rnp->lock);  /* irqs already disabled. */
1420                 rnp->qsmaskinit |= mask;
1421                 mask = rnp->grpmask;
1422                 spin_unlock(&rnp->lock); /* irqs already disabled. */
1423                 rnp = rnp->parent;
1424         } while (rnp != NULL && !(rnp->qsmaskinit & mask));
1425
1426         spin_unlock(&rsp->onofflock);           /* irqs remain disabled. */
1427
1428         /*
1429          * A new grace period might start here.  If so, we will be part of
1430          * it, and its gpnum will be greater than ours, so we will
1431          * participate.  It is also possible for the gpnum to have been
1432          * incremented before this function was called, and the bitmasks
1433          * to not be filled out until now, in which case we will also
1434          * participate due to our gpnum being behind.
1435          */
1436
1437         /* Since it is coming online, the CPU is in a quiescent state. */
1438         cpu_quiet(cpu, rsp, rdp, lastcomp);
1439         local_irq_restore(flags);
1440 }
1441
1442 static void __cpuinit rcu_online_cpu(int cpu)
1443 {
1444         rcu_init_percpu_data(cpu, &rcu_sched_state);
1445         rcu_init_percpu_data(cpu, &rcu_bh_state);
1446 }
1447
1448 /*
1449  * Handle CPU online/offline notifcation events.
1450  */
1451 int __cpuinit rcu_cpu_notify(struct notifier_block *self,
1452                              unsigned long action, void *hcpu)
1453 {
1454         long cpu = (long)hcpu;
1455
1456         switch (action) {
1457         case CPU_UP_PREPARE:
1458         case CPU_UP_PREPARE_FROZEN:
1459                 rcu_online_cpu(cpu);
1460                 break;
1461         case CPU_DEAD:
1462         case CPU_DEAD_FROZEN:
1463         case CPU_UP_CANCELED:
1464         case CPU_UP_CANCELED_FROZEN:
1465                 rcu_offline_cpu(cpu);
1466                 break;
1467         default:
1468                 break;
1469         }
1470         return NOTIFY_OK;
1471 }
1472
1473 /*
1474  * Compute the per-level fanout, either using the exact fanout specified
1475  * or balancing the tree, depending on CONFIG_RCU_FANOUT_EXACT.
1476  */
1477 #ifdef CONFIG_RCU_FANOUT_EXACT
1478 static void __init rcu_init_levelspread(struct rcu_state *rsp)
1479 {
1480         int i;
1481
1482         for (i = NUM_RCU_LVLS - 1; i >= 0; i--)
1483                 rsp->levelspread[i] = CONFIG_RCU_FANOUT;
1484 }
1485 #else /* #ifdef CONFIG_RCU_FANOUT_EXACT */
1486 static void __init rcu_init_levelspread(struct rcu_state *rsp)
1487 {
1488         int ccur;
1489         int cprv;
1490         int i;
1491
1492         cprv = NR_CPUS;
1493         for (i = NUM_RCU_LVLS - 1; i >= 0; i--) {
1494                 ccur = rsp->levelcnt[i];
1495                 rsp->levelspread[i] = (cprv + ccur - 1) / ccur;
1496                 cprv = ccur;
1497         }
1498 }
1499 #endif /* #else #ifdef CONFIG_RCU_FANOUT_EXACT */
1500
1501 /*
1502  * Helper function for rcu_init() that initializes one rcu_state structure.
1503  */
1504 static void __init rcu_init_one(struct rcu_state *rsp)
1505 {
1506         int cpustride = 1;
1507         int i;
1508         int j;
1509         struct rcu_node *rnp;
1510
1511         /* Initialize the level-tracking arrays. */
1512
1513         for (i = 1; i < NUM_RCU_LVLS; i++)
1514                 rsp->level[i] = rsp->level[i - 1] + rsp->levelcnt[i - 1];
1515         rcu_init_levelspread(rsp);
1516
1517         /* Initialize the elements themselves, starting from the leaves. */
1518
1519         for (i = NUM_RCU_LVLS - 1; i >= 0; i--) {
1520                 cpustride *= rsp->levelspread[i];
1521                 rnp = rsp->level[i];
1522                 for (j = 0; j < rsp->levelcnt[i]; j++, rnp++) {
1523                         spin_lock_init(&rnp->lock);
1524                         rnp->qsmask = 0;
1525                         rnp->qsmaskinit = 0;
1526                         rnp->grplo = j * cpustride;
1527                         rnp->grphi = (j + 1) * cpustride - 1;
1528                         if (rnp->grphi >= NR_CPUS)
1529                                 rnp->grphi = NR_CPUS - 1;
1530                         if (i == 0) {
1531                                 rnp->grpnum = 0;
1532                                 rnp->grpmask = 0;
1533                                 rnp->parent = NULL;
1534                         } else {
1535                                 rnp->grpnum = j % rsp->levelspread[i - 1];
1536                                 rnp->grpmask = 1UL << rnp->grpnum;
1537                                 rnp->parent = rsp->level[i - 1] +
1538                                               j / rsp->levelspread[i - 1];
1539                         }
1540                         rnp->level = i;
1541                 }
1542         }
1543 }
1544
1545 /*
1546  * Helper macro for __rcu_init().  To be used nowhere else!
1547  * Assigns leaf node pointers into each CPU's rcu_data structure.
1548  */
1549 #define RCU_INIT_FLAVOR(rsp, rcu_data) \
1550 do { \
1551         rcu_init_one(rsp); \
1552         rnp = (rsp)->level[NUM_RCU_LVLS - 1]; \
1553         j = 0; \
1554         for_each_possible_cpu(i) { \
1555                 if (i > rnp[j].grphi) \
1556                         j++; \
1557                 per_cpu(rcu_data, i).mynode = &rnp[j]; \
1558                 (rsp)->rda[i] = &per_cpu(rcu_data, i); \
1559                 rcu_boot_init_percpu_data(i, rsp); \
1560         } \
1561 } while (0)
1562
1563 void __init __rcu_init(void)
1564 {
1565         int i;                  /* All used by RCU_DATA_PTR_INIT(). */
1566         int j;
1567         struct rcu_node *rnp;
1568
1569         printk(KERN_INFO "Hierarchical RCU implementation.\n");
1570 #ifdef CONFIG_RCU_CPU_STALL_DETECTOR
1571         printk(KERN_INFO "RCU-based detection of stalled CPUs is enabled.\n");
1572 #endif /* #ifdef CONFIG_RCU_CPU_STALL_DETECTOR */
1573         RCU_INIT_FLAVOR(&rcu_sched_state, rcu_sched_data);
1574         RCU_INIT_FLAVOR(&rcu_bh_state, rcu_bh_data);
1575         open_softirq(RCU_SOFTIRQ, rcu_process_callbacks);
1576 }
1577
1578 module_param(blimit, int, 0);
1579 module_param(qhimark, int, 0);
1580 module_param(qlowmark, int, 0);