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