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