9cb3a68819fae81aab2a69ad34fc0b0c325fe204
[linux-3.10.git] / kernel / rcutree_plugin.h
1 /*
2  * Read-Copy Update mechanism for mutual exclusion (tree-based version)
3  * Internal non-public definitions that provide either classic
4  * or preemptible semantics.
5  *
6  * This program is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License as published by
8  * the Free Software Foundation; either version 2 of the License, or
9  * (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software
18  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
19  *
20  * Copyright Red Hat, 2009
21  * Copyright IBM Corporation, 2009
22  *
23  * Author: Ingo Molnar <mingo@elte.hu>
24  *         Paul E. McKenney <paulmck@linux.vnet.ibm.com>
25  */
26
27 #include <linux/delay.h>
28
29 #define RCU_KTHREAD_PRIO 1
30
31 #ifdef CONFIG_RCU_BOOST
32 #define RCU_BOOST_PRIO CONFIG_RCU_BOOST_PRIO
33 #else
34 #define RCU_BOOST_PRIO RCU_KTHREAD_PRIO
35 #endif
36
37 /*
38  * Check the RCU kernel configuration parameters and print informative
39  * messages about anything out of the ordinary.  If you like #ifdef, you
40  * will love this function.
41  */
42 static void __init rcu_bootup_announce_oddness(void)
43 {
44 #ifdef CONFIG_RCU_TRACE
45         printk(KERN_INFO "\tRCU debugfs-based tracing is enabled.\n");
46 #endif
47 #if (defined(CONFIG_64BIT) && CONFIG_RCU_FANOUT != 64) || (!defined(CONFIG_64BIT) && CONFIG_RCU_FANOUT != 32)
48         printk(KERN_INFO "\tCONFIG_RCU_FANOUT set to non-default value of %d\n",
49                CONFIG_RCU_FANOUT);
50 #endif
51 #ifdef CONFIG_RCU_FANOUT_EXACT
52         printk(KERN_INFO "\tHierarchical RCU autobalancing is disabled.\n");
53 #endif
54 #ifdef CONFIG_RCU_FAST_NO_HZ
55         printk(KERN_INFO
56                "\tRCU dyntick-idle grace-period acceleration is enabled.\n");
57 #endif
58 #ifdef CONFIG_PROVE_RCU
59         printk(KERN_INFO "\tRCU lockdep checking is enabled.\n");
60 #endif
61 #ifdef CONFIG_RCU_TORTURE_TEST_RUNNABLE
62         printk(KERN_INFO "\tRCU torture testing starts during boot.\n");
63 #endif
64 #if defined(CONFIG_TREE_PREEMPT_RCU) && !defined(CONFIG_RCU_CPU_STALL_VERBOSE)
65         printk(KERN_INFO "\tDump stacks of tasks blocking RCU-preempt GP.\n");
66 #endif
67 #if defined(CONFIG_RCU_CPU_STALL_INFO)
68         printk(KERN_INFO "\tAdditional per-CPU info printed with stalls.\n");
69 #endif
70 #if NUM_RCU_LVL_4 != 0
71         printk(KERN_INFO "\tFour-level hierarchy is enabled.\n");
72 #endif
73         if (rcu_fanout_leaf != CONFIG_RCU_FANOUT_LEAF)
74                 printk(KERN_INFO "\tExperimental boot-time adjustment of leaf fanout to %d.\n", rcu_fanout_leaf);
75         if (nr_cpu_ids != NR_CPUS)
76                 printk(KERN_INFO "\tRCU restricting CPUs from NR_CPUS=%d to nr_cpu_ids=%d.\n", NR_CPUS, nr_cpu_ids);
77 }
78
79 #ifdef CONFIG_TREE_PREEMPT_RCU
80
81 struct rcu_state rcu_preempt_state =
82         RCU_STATE_INITIALIZER(rcu_preempt, call_rcu);
83 DEFINE_PER_CPU(struct rcu_data, rcu_preempt_data);
84 static struct rcu_state *rcu_state = &rcu_preempt_state;
85
86 static void rcu_read_unlock_special(struct task_struct *t);
87 static int rcu_preempted_readers_exp(struct rcu_node *rnp);
88
89 /*
90  * Tell them what RCU they are running.
91  */
92 static void __init rcu_bootup_announce(void)
93 {
94         printk(KERN_INFO "Preemptible hierarchical RCU implementation.\n");
95         rcu_bootup_announce_oddness();
96 }
97
98 /*
99  * Return the number of RCU-preempt batches processed thus far
100  * for debug and statistics.
101  */
102 long rcu_batches_completed_preempt(void)
103 {
104         return rcu_preempt_state.completed;
105 }
106 EXPORT_SYMBOL_GPL(rcu_batches_completed_preempt);
107
108 /*
109  * Return the number of RCU batches processed thus far for debug & stats.
110  */
111 long rcu_batches_completed(void)
112 {
113         return rcu_batches_completed_preempt();
114 }
115 EXPORT_SYMBOL_GPL(rcu_batches_completed);
116
117 /*
118  * Force a quiescent state for preemptible RCU.
119  */
120 void rcu_force_quiescent_state(void)
121 {
122         force_quiescent_state(&rcu_preempt_state, 0);
123 }
124 EXPORT_SYMBOL_GPL(rcu_force_quiescent_state);
125
126 /*
127  * Record a preemptible-RCU quiescent state for the specified CPU.  Note
128  * that this just means that the task currently running on the CPU is
129  * not in a quiescent state.  There might be any number of tasks blocked
130  * while in an RCU read-side critical section.
131  *
132  * Unlike the other rcu_*_qs() functions, callers to this function
133  * must disable irqs in order to protect the assignment to
134  * ->rcu_read_unlock_special.
135  */
136 static void rcu_preempt_qs(int cpu)
137 {
138         struct rcu_data *rdp = &per_cpu(rcu_preempt_data, cpu);
139
140         rdp->passed_quiesce_gpnum = rdp->gpnum;
141         barrier();
142         if (rdp->passed_quiesce == 0)
143                 trace_rcu_grace_period("rcu_preempt", rdp->gpnum, "cpuqs");
144         rdp->passed_quiesce = 1;
145         current->rcu_read_unlock_special &= ~RCU_READ_UNLOCK_NEED_QS;
146 }
147
148 /*
149  * We have entered the scheduler, and the current task might soon be
150  * context-switched away from.  If this task is in an RCU read-side
151  * critical section, we will no longer be able to rely on the CPU to
152  * record that fact, so we enqueue the task on the blkd_tasks list.
153  * The task will dequeue itself when it exits the outermost enclosing
154  * RCU read-side critical section.  Therefore, the current grace period
155  * cannot be permitted to complete until the blkd_tasks list entries
156  * predating the current grace period drain, in other words, until
157  * rnp->gp_tasks becomes NULL.
158  *
159  * Caller must disable preemption.
160  */
161 static void rcu_preempt_note_context_switch(int cpu)
162 {
163         struct task_struct *t = current;
164         unsigned long flags;
165         struct rcu_data *rdp;
166         struct rcu_node *rnp;
167
168         if (t->rcu_read_lock_nesting > 0 &&
169             (t->rcu_read_unlock_special & RCU_READ_UNLOCK_BLOCKED) == 0) {
170
171                 /* Possibly blocking in an RCU read-side critical section. */
172                 rdp = per_cpu_ptr(rcu_preempt_state.rda, cpu);
173                 rnp = rdp->mynode;
174                 raw_spin_lock_irqsave(&rnp->lock, flags);
175                 t->rcu_read_unlock_special |= RCU_READ_UNLOCK_BLOCKED;
176                 t->rcu_blocked_node = rnp;
177
178                 /*
179                  * If this CPU has already checked in, then this task
180                  * will hold up the next grace period rather than the
181                  * current grace period.  Queue the task accordingly.
182                  * If the task is queued for the current grace period
183                  * (i.e., this CPU has not yet passed through a quiescent
184                  * state for the current grace period), then as long
185                  * as that task remains queued, the current grace period
186                  * cannot end.  Note that there is some uncertainty as
187                  * to exactly when the current grace period started.
188                  * We take a conservative approach, which can result
189                  * in unnecessarily waiting on tasks that started very
190                  * slightly after the current grace period began.  C'est
191                  * la vie!!!
192                  *
193                  * But first, note that the current CPU must still be
194                  * on line!
195                  */
196                 WARN_ON_ONCE((rdp->grpmask & rnp->qsmaskinit) == 0);
197                 WARN_ON_ONCE(!list_empty(&t->rcu_node_entry));
198                 if ((rnp->qsmask & rdp->grpmask) && rnp->gp_tasks != NULL) {
199                         list_add(&t->rcu_node_entry, rnp->gp_tasks->prev);
200                         rnp->gp_tasks = &t->rcu_node_entry;
201 #ifdef CONFIG_RCU_BOOST
202                         if (rnp->boost_tasks != NULL)
203                                 rnp->boost_tasks = rnp->gp_tasks;
204 #endif /* #ifdef CONFIG_RCU_BOOST */
205                 } else {
206                         list_add(&t->rcu_node_entry, &rnp->blkd_tasks);
207                         if (rnp->qsmask & rdp->grpmask)
208                                 rnp->gp_tasks = &t->rcu_node_entry;
209                 }
210                 trace_rcu_preempt_task(rdp->rsp->name,
211                                        t->pid,
212                                        (rnp->qsmask & rdp->grpmask)
213                                        ? rnp->gpnum
214                                        : rnp->gpnum + 1);
215                 raw_spin_unlock_irqrestore(&rnp->lock, flags);
216         } else if (t->rcu_read_lock_nesting < 0 &&
217                    t->rcu_read_unlock_special) {
218
219                 /*
220                  * Complete exit from RCU read-side critical section on
221                  * behalf of preempted instance of __rcu_read_unlock().
222                  */
223                 rcu_read_unlock_special(t);
224         }
225
226         /*
227          * Either we were not in an RCU read-side critical section to
228          * begin with, or we have now recorded that critical section
229          * globally.  Either way, we can now note a quiescent state
230          * for this CPU.  Again, if we were in an RCU read-side critical
231          * section, and if that critical section was blocking the current
232          * grace period, then the fact that the task has been enqueued
233          * means that we continue to block the current grace period.
234          */
235         local_irq_save(flags);
236         rcu_preempt_qs(cpu);
237         local_irq_restore(flags);
238 }
239
240 /*
241  * Tree-preemptible RCU implementation for rcu_read_lock().
242  * Just increment ->rcu_read_lock_nesting, shared state will be updated
243  * if we block.
244  */
245 void __rcu_read_lock(void)
246 {
247         current->rcu_read_lock_nesting++;
248         barrier();  /* needed if we ever invoke rcu_read_lock in rcutree.c */
249 }
250 EXPORT_SYMBOL_GPL(__rcu_read_lock);
251
252 /*
253  * Check for preempted RCU readers blocking the current grace period
254  * for the specified rcu_node structure.  If the caller needs a reliable
255  * answer, it must hold the rcu_node's ->lock.
256  */
257 static int rcu_preempt_blocked_readers_cgp(struct rcu_node *rnp)
258 {
259         return rnp->gp_tasks != NULL;
260 }
261
262 /*
263  * Record a quiescent state for all tasks that were previously queued
264  * on the specified rcu_node structure and that were blocking the current
265  * RCU grace period.  The caller must hold the specified rnp->lock with
266  * irqs disabled, and this lock is released upon return, but irqs remain
267  * disabled.
268  */
269 static void rcu_report_unblock_qs_rnp(struct rcu_node *rnp, unsigned long flags)
270         __releases(rnp->lock)
271 {
272         unsigned long mask;
273         struct rcu_node *rnp_p;
274
275         if (rnp->qsmask != 0 || rcu_preempt_blocked_readers_cgp(rnp)) {
276                 raw_spin_unlock_irqrestore(&rnp->lock, flags);
277                 return;  /* Still need more quiescent states! */
278         }
279
280         rnp_p = rnp->parent;
281         if (rnp_p == NULL) {
282                 /*
283                  * Either there is only one rcu_node in the tree,
284                  * or tasks were kicked up to root rcu_node due to
285                  * CPUs going offline.
286                  */
287                 rcu_report_qs_rsp(&rcu_preempt_state, flags);
288                 return;
289         }
290
291         /* Report up the rest of the hierarchy. */
292         mask = rnp->grpmask;
293         raw_spin_unlock(&rnp->lock);    /* irqs remain disabled. */
294         raw_spin_lock(&rnp_p->lock);    /* irqs already disabled. */
295         rcu_report_qs_rnp(mask, &rcu_preempt_state, rnp_p, flags);
296 }
297
298 /*
299  * Advance a ->blkd_tasks-list pointer to the next entry, instead
300  * returning NULL if at the end of the list.
301  */
302 static struct list_head *rcu_next_node_entry(struct task_struct *t,
303                                              struct rcu_node *rnp)
304 {
305         struct list_head *np;
306
307         np = t->rcu_node_entry.next;
308         if (np == &rnp->blkd_tasks)
309                 np = NULL;
310         return np;
311 }
312
313 /*
314  * Handle special cases during rcu_read_unlock(), such as needing to
315  * notify RCU core processing or task having blocked during the RCU
316  * read-side critical section.
317  */
318 static noinline void rcu_read_unlock_special(struct task_struct *t)
319 {
320         int empty;
321         int empty_exp;
322         int empty_exp_now;
323         unsigned long flags;
324         struct list_head *np;
325 #ifdef CONFIG_RCU_BOOST
326         struct rt_mutex *rbmp = NULL;
327 #endif /* #ifdef CONFIG_RCU_BOOST */
328         struct rcu_node *rnp;
329         int special;
330
331         /* NMI handlers cannot block and cannot safely manipulate state. */
332         if (in_nmi())
333                 return;
334
335         local_irq_save(flags);
336
337         /*
338          * If RCU core is waiting for this CPU to exit critical section,
339          * let it know that we have done so.
340          */
341         special = t->rcu_read_unlock_special;
342         if (special & RCU_READ_UNLOCK_NEED_QS) {
343                 rcu_preempt_qs(smp_processor_id());
344         }
345
346         /* Hardware IRQ handlers cannot block. */
347         if (in_irq() || in_serving_softirq()) {
348                 local_irq_restore(flags);
349                 return;
350         }
351
352         /* Clean up if blocked during RCU read-side critical section. */
353         if (special & RCU_READ_UNLOCK_BLOCKED) {
354                 t->rcu_read_unlock_special &= ~RCU_READ_UNLOCK_BLOCKED;
355
356                 /*
357                  * Remove this task from the list it blocked on.  The
358                  * task can migrate while we acquire the lock, but at
359                  * most one time.  So at most two passes through loop.
360                  */
361                 for (;;) {
362                         rnp = t->rcu_blocked_node;
363                         raw_spin_lock(&rnp->lock);  /* irqs already disabled. */
364                         if (rnp == t->rcu_blocked_node)
365                                 break;
366                         raw_spin_unlock(&rnp->lock); /* irqs remain disabled. */
367                 }
368                 empty = !rcu_preempt_blocked_readers_cgp(rnp);
369                 empty_exp = !rcu_preempted_readers_exp(rnp);
370                 smp_mb(); /* ensure expedited fastpath sees end of RCU c-s. */
371                 np = rcu_next_node_entry(t, rnp);
372                 list_del_init(&t->rcu_node_entry);
373                 t->rcu_blocked_node = NULL;
374                 trace_rcu_unlock_preempted_task("rcu_preempt",
375                                                 rnp->gpnum, t->pid);
376                 if (&t->rcu_node_entry == rnp->gp_tasks)
377                         rnp->gp_tasks = np;
378                 if (&t->rcu_node_entry == rnp->exp_tasks)
379                         rnp->exp_tasks = np;
380 #ifdef CONFIG_RCU_BOOST
381                 if (&t->rcu_node_entry == rnp->boost_tasks)
382                         rnp->boost_tasks = np;
383                 /* Snapshot/clear ->rcu_boost_mutex with rcu_node lock held. */
384                 if (t->rcu_boost_mutex) {
385                         rbmp = t->rcu_boost_mutex;
386                         t->rcu_boost_mutex = NULL;
387                 }
388 #endif /* #ifdef CONFIG_RCU_BOOST */
389
390                 /*
391                  * If this was the last task on the current list, and if
392                  * we aren't waiting on any CPUs, report the quiescent state.
393                  * Note that rcu_report_unblock_qs_rnp() releases rnp->lock,
394                  * so we must take a snapshot of the expedited state.
395                  */
396                 empty_exp_now = !rcu_preempted_readers_exp(rnp);
397                 if (!empty && !rcu_preempt_blocked_readers_cgp(rnp)) {
398                         trace_rcu_quiescent_state_report("preempt_rcu",
399                                                          rnp->gpnum,
400                                                          0, rnp->qsmask,
401                                                          rnp->level,
402                                                          rnp->grplo,
403                                                          rnp->grphi,
404                                                          !!rnp->gp_tasks);
405                         rcu_report_unblock_qs_rnp(rnp, flags);
406                 } else
407                         raw_spin_unlock_irqrestore(&rnp->lock, flags);
408
409 #ifdef CONFIG_RCU_BOOST
410                 /* Unboost if we were boosted. */
411                 if (rbmp)
412                         rt_mutex_unlock(rbmp);
413 #endif /* #ifdef CONFIG_RCU_BOOST */
414
415                 /*
416                  * If this was the last task on the expedited lists,
417                  * then we need to report up the rcu_node hierarchy.
418                  */
419                 if (!empty_exp && empty_exp_now)
420                         rcu_report_exp_rnp(&rcu_preempt_state, rnp, true);
421         } else {
422                 local_irq_restore(flags);
423         }
424 }
425
426 /*
427  * Tree-preemptible RCU implementation for rcu_read_unlock().
428  * Decrement ->rcu_read_lock_nesting.  If the result is zero (outermost
429  * rcu_read_unlock()) and ->rcu_read_unlock_special is non-zero, then
430  * invoke rcu_read_unlock_special() to clean up after a context switch
431  * in an RCU read-side critical section and other special cases.
432  */
433 void __rcu_read_unlock(void)
434 {
435         struct task_struct *t = current;
436
437         if (t->rcu_read_lock_nesting != 1)
438                 --t->rcu_read_lock_nesting;
439         else {
440                 barrier();  /* critical section before exit code. */
441                 t->rcu_read_lock_nesting = INT_MIN;
442                 barrier();  /* assign before ->rcu_read_unlock_special load */
443                 if (unlikely(ACCESS_ONCE(t->rcu_read_unlock_special)))
444                         rcu_read_unlock_special(t);
445                 barrier();  /* ->rcu_read_unlock_special load before assign */
446                 t->rcu_read_lock_nesting = 0;
447         }
448 #ifdef CONFIG_PROVE_LOCKING
449         {
450                 int rrln = ACCESS_ONCE(t->rcu_read_lock_nesting);
451
452                 WARN_ON_ONCE(rrln < 0 && rrln > INT_MIN / 2);
453         }
454 #endif /* #ifdef CONFIG_PROVE_LOCKING */
455 }
456 EXPORT_SYMBOL_GPL(__rcu_read_unlock);
457
458 #ifdef CONFIG_RCU_CPU_STALL_VERBOSE
459
460 /*
461  * Dump detailed information for all tasks blocking the current RCU
462  * grace period on the specified rcu_node structure.
463  */
464 static void rcu_print_detail_task_stall_rnp(struct rcu_node *rnp)
465 {
466         unsigned long flags;
467         struct task_struct *t;
468
469         if (!rcu_preempt_blocked_readers_cgp(rnp))
470                 return;
471         raw_spin_lock_irqsave(&rnp->lock, flags);
472         t = list_entry(rnp->gp_tasks,
473                        struct task_struct, rcu_node_entry);
474         list_for_each_entry_continue(t, &rnp->blkd_tasks, rcu_node_entry)
475                 sched_show_task(t);
476         raw_spin_unlock_irqrestore(&rnp->lock, flags);
477 }
478
479 /*
480  * Dump detailed information for all tasks blocking the current RCU
481  * grace period.
482  */
483 static void rcu_print_detail_task_stall(struct rcu_state *rsp)
484 {
485         struct rcu_node *rnp = rcu_get_root(rsp);
486
487         rcu_print_detail_task_stall_rnp(rnp);
488         rcu_for_each_leaf_node(rsp, rnp)
489                 rcu_print_detail_task_stall_rnp(rnp);
490 }
491
492 #else /* #ifdef CONFIG_RCU_CPU_STALL_VERBOSE */
493
494 static void rcu_print_detail_task_stall(struct rcu_state *rsp)
495 {
496 }
497
498 #endif /* #else #ifdef CONFIG_RCU_CPU_STALL_VERBOSE */
499
500 #ifdef CONFIG_RCU_CPU_STALL_INFO
501
502 static void rcu_print_task_stall_begin(struct rcu_node *rnp)
503 {
504         printk(KERN_ERR "\tTasks blocked on level-%d rcu_node (CPUs %d-%d):",
505                rnp->level, rnp->grplo, rnp->grphi);
506 }
507
508 static void rcu_print_task_stall_end(void)
509 {
510         printk(KERN_CONT "\n");
511 }
512
513 #else /* #ifdef CONFIG_RCU_CPU_STALL_INFO */
514
515 static void rcu_print_task_stall_begin(struct rcu_node *rnp)
516 {
517 }
518
519 static void rcu_print_task_stall_end(void)
520 {
521 }
522
523 #endif /* #else #ifdef CONFIG_RCU_CPU_STALL_INFO */
524
525 /*
526  * Scan the current list of tasks blocked within RCU read-side critical
527  * sections, printing out the tid of each.
528  */
529 static int rcu_print_task_stall(struct rcu_node *rnp)
530 {
531         struct task_struct *t;
532         int ndetected = 0;
533
534         if (!rcu_preempt_blocked_readers_cgp(rnp))
535                 return 0;
536         rcu_print_task_stall_begin(rnp);
537         t = list_entry(rnp->gp_tasks,
538                        struct task_struct, rcu_node_entry);
539         list_for_each_entry_continue(t, &rnp->blkd_tasks, rcu_node_entry) {
540                 printk(KERN_CONT " P%d", t->pid);
541                 ndetected++;
542         }
543         rcu_print_task_stall_end();
544         return ndetected;
545 }
546
547 /*
548  * Suppress preemptible RCU's CPU stall warnings by pushing the
549  * time of the next stall-warning message comfortably far into the
550  * future.
551  */
552 static void rcu_preempt_stall_reset(void)
553 {
554         rcu_preempt_state.jiffies_stall = jiffies + ULONG_MAX / 2;
555 }
556
557 /*
558  * Check that the list of blocked tasks for the newly completed grace
559  * period is in fact empty.  It is a serious bug to complete a grace
560  * period that still has RCU readers blocked!  This function must be
561  * invoked -before- updating this rnp's ->gpnum, and the rnp's ->lock
562  * must be held by the caller.
563  *
564  * Also, if there are blocked tasks on the list, they automatically
565  * block the newly created grace period, so set up ->gp_tasks accordingly.
566  */
567 static void rcu_preempt_check_blocked_tasks(struct rcu_node *rnp)
568 {
569         WARN_ON_ONCE(rcu_preempt_blocked_readers_cgp(rnp));
570         if (!list_empty(&rnp->blkd_tasks))
571                 rnp->gp_tasks = rnp->blkd_tasks.next;
572         WARN_ON_ONCE(rnp->qsmask);
573 }
574
575 #ifdef CONFIG_HOTPLUG_CPU
576
577 /*
578  * Handle tasklist migration for case in which all CPUs covered by the
579  * specified rcu_node have gone offline.  Move them up to the root
580  * rcu_node.  The reason for not just moving them to the immediate
581  * parent is to remove the need for rcu_read_unlock_special() to
582  * make more than two attempts to acquire the target rcu_node's lock.
583  * Returns true if there were tasks blocking the current RCU grace
584  * period.
585  *
586  * Returns 1 if there was previously a task blocking the current grace
587  * period on the specified rcu_node structure.
588  *
589  * The caller must hold rnp->lock with irqs disabled.
590  */
591 static int rcu_preempt_offline_tasks(struct rcu_state *rsp,
592                                      struct rcu_node *rnp,
593                                      struct rcu_data *rdp)
594 {
595         struct list_head *lp;
596         struct list_head *lp_root;
597         int retval = 0;
598         struct rcu_node *rnp_root = rcu_get_root(rsp);
599         struct task_struct *t;
600
601         if (rnp == rnp_root) {
602                 WARN_ONCE(1, "Last CPU thought to be offlined?");
603                 return 0;  /* Shouldn't happen: at least one CPU online. */
604         }
605
606         /* If we are on an internal node, complain bitterly. */
607         WARN_ON_ONCE(rnp != rdp->mynode);
608
609         /*
610          * Move tasks up to root rcu_node.  Don't try to get fancy for
611          * this corner-case operation -- just put this node's tasks
612          * at the head of the root node's list, and update the root node's
613          * ->gp_tasks and ->exp_tasks pointers to those of this node's,
614          * if non-NULL.  This might result in waiting for more tasks than
615          * absolutely necessary, but this is a good performance/complexity
616          * tradeoff.
617          */
618         if (rcu_preempt_blocked_readers_cgp(rnp) && rnp->qsmask == 0)
619                 retval |= RCU_OFL_TASKS_NORM_GP;
620         if (rcu_preempted_readers_exp(rnp))
621                 retval |= RCU_OFL_TASKS_EXP_GP;
622         lp = &rnp->blkd_tasks;
623         lp_root = &rnp_root->blkd_tasks;
624         while (!list_empty(lp)) {
625                 t = list_entry(lp->next, typeof(*t), rcu_node_entry);
626                 raw_spin_lock(&rnp_root->lock); /* irqs already disabled */
627                 list_del(&t->rcu_node_entry);
628                 t->rcu_blocked_node = rnp_root;
629                 list_add(&t->rcu_node_entry, lp_root);
630                 if (&t->rcu_node_entry == rnp->gp_tasks)
631                         rnp_root->gp_tasks = rnp->gp_tasks;
632                 if (&t->rcu_node_entry == rnp->exp_tasks)
633                         rnp_root->exp_tasks = rnp->exp_tasks;
634 #ifdef CONFIG_RCU_BOOST
635                 if (&t->rcu_node_entry == rnp->boost_tasks)
636                         rnp_root->boost_tasks = rnp->boost_tasks;
637 #endif /* #ifdef CONFIG_RCU_BOOST */
638                 raw_spin_unlock(&rnp_root->lock); /* irqs still disabled */
639         }
640
641 #ifdef CONFIG_RCU_BOOST
642         /* In case root is being boosted and leaf is not. */
643         raw_spin_lock(&rnp_root->lock); /* irqs already disabled */
644         if (rnp_root->boost_tasks != NULL &&
645             rnp_root->boost_tasks != rnp_root->gp_tasks)
646                 rnp_root->boost_tasks = rnp_root->gp_tasks;
647         raw_spin_unlock(&rnp_root->lock); /* irqs still disabled */
648 #endif /* #ifdef CONFIG_RCU_BOOST */
649
650         rnp->gp_tasks = NULL;
651         rnp->exp_tasks = NULL;
652         return retval;
653 }
654
655 #endif /* #ifdef CONFIG_HOTPLUG_CPU */
656
657 /*
658  * Do CPU-offline processing for preemptible RCU.
659  */
660 static void rcu_preempt_cleanup_dead_cpu(int cpu)
661 {
662         rcu_cleanup_dead_cpu(cpu, &rcu_preempt_state);
663 }
664
665 /*
666  * Check for a quiescent state from the current CPU.  When a task blocks,
667  * the task is recorded in the corresponding CPU's rcu_node structure,
668  * which is checked elsewhere.
669  *
670  * Caller must disable hard irqs.
671  */
672 static void rcu_preempt_check_callbacks(int cpu)
673 {
674         struct task_struct *t = current;
675
676         if (t->rcu_read_lock_nesting == 0) {
677                 rcu_preempt_qs(cpu);
678                 return;
679         }
680         if (t->rcu_read_lock_nesting > 0 &&
681             per_cpu(rcu_preempt_data, cpu).qs_pending)
682                 t->rcu_read_unlock_special |= RCU_READ_UNLOCK_NEED_QS;
683 }
684
685 /*
686  * Process callbacks for preemptible RCU.
687  */
688 static void rcu_preempt_process_callbacks(void)
689 {
690         __rcu_process_callbacks(&rcu_preempt_state,
691                                 &__get_cpu_var(rcu_preempt_data));
692 }
693
694 #ifdef CONFIG_RCU_BOOST
695
696 static void rcu_preempt_do_callbacks(void)
697 {
698         rcu_do_batch(&rcu_preempt_state, &__get_cpu_var(rcu_preempt_data));
699 }
700
701 #endif /* #ifdef CONFIG_RCU_BOOST */
702
703 /*
704  * Queue a preemptible-RCU callback for invocation after a grace period.
705  */
706 void call_rcu(struct rcu_head *head, void (*func)(struct rcu_head *rcu))
707 {
708         __call_rcu(head, func, &rcu_preempt_state, 0);
709 }
710 EXPORT_SYMBOL_GPL(call_rcu);
711
712 /*
713  * Queue an RCU callback for lazy invocation after a grace period.
714  * This will likely be later named something like "call_rcu_lazy()",
715  * but this change will require some way of tagging the lazy RCU
716  * callbacks in the list of pending callbacks.  Until then, this
717  * function may only be called from __kfree_rcu().
718  */
719 void kfree_call_rcu(struct rcu_head *head,
720                     void (*func)(struct rcu_head *rcu))
721 {
722         __call_rcu(head, func, &rcu_preempt_state, 1);
723 }
724 EXPORT_SYMBOL_GPL(kfree_call_rcu);
725
726 /**
727  * synchronize_rcu - wait until a grace period has elapsed.
728  *
729  * Control will return to the caller some time after a full grace
730  * period has elapsed, in other words after all currently executing RCU
731  * read-side critical sections have completed.  Note, however, that
732  * upon return from synchronize_rcu(), the caller might well be executing
733  * concurrently with new RCU read-side critical sections that began while
734  * synchronize_rcu() was waiting.  RCU read-side critical sections are
735  * delimited by rcu_read_lock() and rcu_read_unlock(), and may be nested.
736  */
737 void synchronize_rcu(void)
738 {
739         rcu_lockdep_assert(!lock_is_held(&rcu_bh_lock_map) &&
740                            !lock_is_held(&rcu_lock_map) &&
741                            !lock_is_held(&rcu_sched_lock_map),
742                            "Illegal synchronize_rcu() in RCU read-side critical section");
743         if (!rcu_scheduler_active)
744                 return;
745         wait_rcu_gp(call_rcu);
746 }
747 EXPORT_SYMBOL_GPL(synchronize_rcu);
748
749 static DECLARE_WAIT_QUEUE_HEAD(sync_rcu_preempt_exp_wq);
750 static long sync_rcu_preempt_exp_count;
751 static DEFINE_MUTEX(sync_rcu_preempt_exp_mutex);
752
753 /*
754  * Return non-zero if there are any tasks in RCU read-side critical
755  * sections blocking the current preemptible-RCU expedited grace period.
756  * If there is no preemptible-RCU expedited grace period currently in
757  * progress, returns zero unconditionally.
758  */
759 static int rcu_preempted_readers_exp(struct rcu_node *rnp)
760 {
761         return rnp->exp_tasks != NULL;
762 }
763
764 /*
765  * return non-zero if there is no RCU expedited grace period in progress
766  * for the specified rcu_node structure, in other words, if all CPUs and
767  * tasks covered by the specified rcu_node structure have done their bit
768  * for the current expedited grace period.  Works only for preemptible
769  * RCU -- other RCU implementation use other means.
770  *
771  * Caller must hold sync_rcu_preempt_exp_mutex.
772  */
773 static int sync_rcu_preempt_exp_done(struct rcu_node *rnp)
774 {
775         return !rcu_preempted_readers_exp(rnp) &&
776                ACCESS_ONCE(rnp->expmask) == 0;
777 }
778
779 /*
780  * Report the exit from RCU read-side critical section for the last task
781  * that queued itself during or before the current expedited preemptible-RCU
782  * grace period.  This event is reported either to the rcu_node structure on
783  * which the task was queued or to one of that rcu_node structure's ancestors,
784  * recursively up the tree.  (Calm down, calm down, we do the recursion
785  * iteratively!)
786  *
787  * Most callers will set the "wake" flag, but the task initiating the
788  * expedited grace period need not wake itself.
789  *
790  * Caller must hold sync_rcu_preempt_exp_mutex.
791  */
792 static void rcu_report_exp_rnp(struct rcu_state *rsp, struct rcu_node *rnp,
793                                bool wake)
794 {
795         unsigned long flags;
796         unsigned long mask;
797
798         raw_spin_lock_irqsave(&rnp->lock, flags);
799         for (;;) {
800                 if (!sync_rcu_preempt_exp_done(rnp)) {
801                         raw_spin_unlock_irqrestore(&rnp->lock, flags);
802                         break;
803                 }
804                 if (rnp->parent == NULL) {
805                         raw_spin_unlock_irqrestore(&rnp->lock, flags);
806                         if (wake)
807                                 wake_up(&sync_rcu_preempt_exp_wq);
808                         break;
809                 }
810                 mask = rnp->grpmask;
811                 raw_spin_unlock(&rnp->lock); /* irqs remain disabled */
812                 rnp = rnp->parent;
813                 raw_spin_lock(&rnp->lock); /* irqs already disabled */
814                 rnp->expmask &= ~mask;
815         }
816 }
817
818 /*
819  * Snapshot the tasks blocking the newly started preemptible-RCU expedited
820  * grace period for the specified rcu_node structure.  If there are no such
821  * tasks, report it up the rcu_node hierarchy.
822  *
823  * Caller must hold sync_rcu_preempt_exp_mutex and rsp->onofflock.
824  */
825 static void
826 sync_rcu_preempt_exp_init(struct rcu_state *rsp, struct rcu_node *rnp)
827 {
828         unsigned long flags;
829         int must_wait = 0;
830
831         raw_spin_lock_irqsave(&rnp->lock, flags);
832         if (list_empty(&rnp->blkd_tasks))
833                 raw_spin_unlock_irqrestore(&rnp->lock, flags);
834         else {
835                 rnp->exp_tasks = rnp->blkd_tasks.next;
836                 rcu_initiate_boost(rnp, flags);  /* releases rnp->lock */
837                 must_wait = 1;
838         }
839         if (!must_wait)
840                 rcu_report_exp_rnp(rsp, rnp, false); /* Don't wake self. */
841 }
842
843 /**
844  * synchronize_rcu_expedited - Brute-force RCU grace period
845  *
846  * Wait for an RCU-preempt grace period, but expedite it.  The basic
847  * idea is to invoke synchronize_sched_expedited() to push all the tasks to
848  * the ->blkd_tasks lists and wait for this list to drain.  This consumes
849  * significant time on all CPUs and is unfriendly to real-time workloads,
850  * so is thus not recommended for any sort of common-case code.
851  * In fact, if you are using synchronize_rcu_expedited() in a loop,
852  * please restructure your code to batch your updates, and then Use a
853  * single synchronize_rcu() instead.
854  *
855  * Note that it is illegal to call this function while holding any lock
856  * that is acquired by a CPU-hotplug notifier.  And yes, it is also illegal
857  * to call this function from a CPU-hotplug notifier.  Failing to observe
858  * these restriction will result in deadlock.
859  */
860 void synchronize_rcu_expedited(void)
861 {
862         unsigned long flags;
863         struct rcu_node *rnp;
864         struct rcu_state *rsp = &rcu_preempt_state;
865         long snap;
866         int trycount = 0;
867
868         smp_mb(); /* Caller's modifications seen first by other CPUs. */
869         snap = ACCESS_ONCE(sync_rcu_preempt_exp_count) + 1;
870         smp_mb(); /* Above access cannot bleed into critical section. */
871
872         /*
873          * Acquire lock, falling back to synchronize_rcu() if too many
874          * lock-acquisition failures.  Of course, if someone does the
875          * expedited grace period for us, just leave.
876          */
877         while (!mutex_trylock(&sync_rcu_preempt_exp_mutex)) {
878                 if (trycount++ < 10)
879                         udelay(trycount * num_online_cpus());
880                 else {
881                         synchronize_rcu();
882                         return;
883                 }
884                 if ((ACCESS_ONCE(sync_rcu_preempt_exp_count) - snap) > 0)
885                         goto mb_ret; /* Others did our work for us. */
886         }
887         if ((ACCESS_ONCE(sync_rcu_preempt_exp_count) - snap) > 0)
888                 goto unlock_mb_ret; /* Others did our work for us. */
889
890         /* force all RCU readers onto ->blkd_tasks lists. */
891         synchronize_sched_expedited();
892
893         raw_spin_lock_irqsave(&rsp->onofflock, flags);
894
895         /* Initialize ->expmask for all non-leaf rcu_node structures. */
896         rcu_for_each_nonleaf_node_breadth_first(rsp, rnp) {
897                 raw_spin_lock(&rnp->lock); /* irqs already disabled. */
898                 rnp->expmask = rnp->qsmaskinit;
899                 raw_spin_unlock(&rnp->lock); /* irqs remain disabled. */
900         }
901
902         /* Snapshot current state of ->blkd_tasks lists. */
903         rcu_for_each_leaf_node(rsp, rnp)
904                 sync_rcu_preempt_exp_init(rsp, rnp);
905         if (NUM_RCU_NODES > 1)
906                 sync_rcu_preempt_exp_init(rsp, rcu_get_root(rsp));
907
908         raw_spin_unlock_irqrestore(&rsp->onofflock, flags);
909
910         /* Wait for snapshotted ->blkd_tasks lists to drain. */
911         rnp = rcu_get_root(rsp);
912         wait_event(sync_rcu_preempt_exp_wq,
913                    sync_rcu_preempt_exp_done(rnp));
914
915         /* Clean up and exit. */
916         smp_mb(); /* ensure expedited GP seen before counter increment. */
917         ACCESS_ONCE(sync_rcu_preempt_exp_count)++;
918 unlock_mb_ret:
919         mutex_unlock(&sync_rcu_preempt_exp_mutex);
920 mb_ret:
921         smp_mb(); /* ensure subsequent action seen after grace period. */
922 }
923 EXPORT_SYMBOL_GPL(synchronize_rcu_expedited);
924
925 /*
926  * Check to see if there is any immediate preemptible-RCU-related work
927  * to be done.
928  */
929 static int rcu_preempt_pending(int cpu)
930 {
931         return __rcu_pending(&rcu_preempt_state,
932                              &per_cpu(rcu_preempt_data, cpu));
933 }
934
935 /*
936  * Does preemptible RCU have callbacks on this CPU?
937  */
938 static int rcu_preempt_cpu_has_callbacks(int cpu)
939 {
940         return !!per_cpu(rcu_preempt_data, cpu).nxtlist;
941 }
942
943 /**
944  * rcu_barrier - Wait until all in-flight call_rcu() callbacks complete.
945  */
946 void rcu_barrier(void)
947 {
948         _rcu_barrier(&rcu_preempt_state);
949 }
950 EXPORT_SYMBOL_GPL(rcu_barrier);
951
952 /*
953  * Initialize preemptible RCU's per-CPU data.
954  */
955 static void __cpuinit rcu_preempt_init_percpu_data(int cpu)
956 {
957         rcu_init_percpu_data(cpu, &rcu_preempt_state, 1);
958 }
959
960 /*
961  * Move preemptible RCU's callbacks from dying CPU to other online CPU
962  * and record a quiescent state.
963  */
964 static void rcu_preempt_cleanup_dying_cpu(void)
965 {
966         rcu_cleanup_dying_cpu(&rcu_preempt_state);
967 }
968
969 /*
970  * Initialize preemptible RCU's state structures.
971  */
972 static void __init __rcu_init_preempt(void)
973 {
974         rcu_init_one(&rcu_preempt_state, &rcu_preempt_data);
975 }
976
977 #else /* #ifdef CONFIG_TREE_PREEMPT_RCU */
978
979 static struct rcu_state *rcu_state = &rcu_sched_state;
980
981 /*
982  * Tell them what RCU they are running.
983  */
984 static void __init rcu_bootup_announce(void)
985 {
986         printk(KERN_INFO "Hierarchical RCU implementation.\n");
987         rcu_bootup_announce_oddness();
988 }
989
990 /*
991  * Return the number of RCU batches processed thus far for debug & stats.
992  */
993 long rcu_batches_completed(void)
994 {
995         return rcu_batches_completed_sched();
996 }
997 EXPORT_SYMBOL_GPL(rcu_batches_completed);
998
999 /*
1000  * Force a quiescent state for RCU, which, because there is no preemptible
1001  * RCU, becomes the same as rcu-sched.
1002  */
1003 void rcu_force_quiescent_state(void)
1004 {
1005         rcu_sched_force_quiescent_state();
1006 }
1007 EXPORT_SYMBOL_GPL(rcu_force_quiescent_state);
1008
1009 /*
1010  * Because preemptible RCU does not exist, we never have to check for
1011  * CPUs being in quiescent states.
1012  */
1013 static void rcu_preempt_note_context_switch(int cpu)
1014 {
1015 }
1016
1017 /*
1018  * Because preemptible RCU does not exist, there are never any preempted
1019  * RCU readers.
1020  */
1021 static int rcu_preempt_blocked_readers_cgp(struct rcu_node *rnp)
1022 {
1023         return 0;
1024 }
1025
1026 #ifdef CONFIG_HOTPLUG_CPU
1027
1028 /* Because preemptible RCU does not exist, no quieting of tasks. */
1029 static void rcu_report_unblock_qs_rnp(struct rcu_node *rnp, unsigned long flags)
1030 {
1031         raw_spin_unlock_irqrestore(&rnp->lock, flags);
1032 }
1033
1034 #endif /* #ifdef CONFIG_HOTPLUG_CPU */
1035
1036 /*
1037  * Because preemptible RCU does not exist, we never have to check for
1038  * tasks blocked within RCU read-side critical sections.
1039  */
1040 static void rcu_print_detail_task_stall(struct rcu_state *rsp)
1041 {
1042 }
1043
1044 /*
1045  * Because preemptible RCU does not exist, we never have to check for
1046  * tasks blocked within RCU read-side critical sections.
1047  */
1048 static int rcu_print_task_stall(struct rcu_node *rnp)
1049 {
1050         return 0;
1051 }
1052
1053 /*
1054  * Because preemptible RCU does not exist, there is no need to suppress
1055  * its CPU stall warnings.
1056  */
1057 static void rcu_preempt_stall_reset(void)
1058 {
1059 }
1060
1061 /*
1062  * Because there is no preemptible RCU, there can be no readers blocked,
1063  * so there is no need to check for blocked tasks.  So check only for
1064  * bogus qsmask values.
1065  */
1066 static void rcu_preempt_check_blocked_tasks(struct rcu_node *rnp)
1067 {
1068         WARN_ON_ONCE(rnp->qsmask);
1069 }
1070
1071 #ifdef CONFIG_HOTPLUG_CPU
1072
1073 /*
1074  * Because preemptible RCU does not exist, it never needs to migrate
1075  * tasks that were blocked within RCU read-side critical sections, and
1076  * such non-existent tasks cannot possibly have been blocking the current
1077  * grace period.
1078  */
1079 static int rcu_preempt_offline_tasks(struct rcu_state *rsp,
1080                                      struct rcu_node *rnp,
1081                                      struct rcu_data *rdp)
1082 {
1083         return 0;
1084 }
1085
1086 #endif /* #ifdef CONFIG_HOTPLUG_CPU */
1087
1088 /*
1089  * Because preemptible RCU does not exist, it never needs CPU-offline
1090  * processing.
1091  */
1092 static void rcu_preempt_cleanup_dead_cpu(int cpu)
1093 {
1094 }
1095
1096 /*
1097  * Because preemptible RCU does not exist, it never has any callbacks
1098  * to check.
1099  */
1100 static void rcu_preempt_check_callbacks(int cpu)
1101 {
1102 }
1103
1104 /*
1105  * Because preemptible RCU does not exist, it never has any callbacks
1106  * to process.
1107  */
1108 static void rcu_preempt_process_callbacks(void)
1109 {
1110 }
1111
1112 /*
1113  * Queue an RCU callback for lazy invocation after a grace period.
1114  * This will likely be later named something like "call_rcu_lazy()",
1115  * but this change will require some way of tagging the lazy RCU
1116  * callbacks in the list of pending callbacks.  Until then, this
1117  * function may only be called from __kfree_rcu().
1118  *
1119  * Because there is no preemptible RCU, we use RCU-sched instead.
1120  */
1121 void kfree_call_rcu(struct rcu_head *head,
1122                     void (*func)(struct rcu_head *rcu))
1123 {
1124         __call_rcu(head, func, &rcu_sched_state, 1);
1125 }
1126 EXPORT_SYMBOL_GPL(kfree_call_rcu);
1127
1128 /*
1129  * Wait for an rcu-preempt grace period, but make it happen quickly.
1130  * But because preemptible RCU does not exist, map to rcu-sched.
1131  */
1132 void synchronize_rcu_expedited(void)
1133 {
1134         synchronize_sched_expedited();
1135 }
1136 EXPORT_SYMBOL_GPL(synchronize_rcu_expedited);
1137
1138 #ifdef CONFIG_HOTPLUG_CPU
1139
1140 /*
1141  * Because preemptible RCU does not exist, there is never any need to
1142  * report on tasks preempted in RCU read-side critical sections during
1143  * expedited RCU grace periods.
1144  */
1145 static void rcu_report_exp_rnp(struct rcu_state *rsp, struct rcu_node *rnp,
1146                                bool wake)
1147 {
1148 }
1149
1150 #endif /* #ifdef CONFIG_HOTPLUG_CPU */
1151
1152 /*
1153  * Because preemptible RCU does not exist, it never has any work to do.
1154  */
1155 static int rcu_preempt_pending(int cpu)
1156 {
1157         return 0;
1158 }
1159
1160 /*
1161  * Because preemptible RCU does not exist, it never has callbacks
1162  */
1163 static int rcu_preempt_cpu_has_callbacks(int cpu)
1164 {
1165         return 0;
1166 }
1167
1168 /*
1169  * Because preemptible RCU does not exist, rcu_barrier() is just
1170  * another name for rcu_barrier_sched().
1171  */
1172 void rcu_barrier(void)
1173 {
1174         rcu_barrier_sched();
1175 }
1176 EXPORT_SYMBOL_GPL(rcu_barrier);
1177
1178 /*
1179  * Because preemptible RCU does not exist, there is no per-CPU
1180  * data to initialize.
1181  */
1182 static void __cpuinit rcu_preempt_init_percpu_data(int cpu)
1183 {
1184 }
1185
1186 /*
1187  * Because there is no preemptible RCU, there is no cleanup to do.
1188  */
1189 static void rcu_preempt_cleanup_dying_cpu(void)
1190 {
1191 }
1192
1193 /*
1194  * Because preemptible RCU does not exist, it need not be initialized.
1195  */
1196 static void __init __rcu_init_preempt(void)
1197 {
1198 }
1199
1200 #endif /* #else #ifdef CONFIG_TREE_PREEMPT_RCU */
1201
1202 #ifdef CONFIG_RCU_BOOST
1203
1204 #include "rtmutex_common.h"
1205
1206 #ifdef CONFIG_RCU_TRACE
1207
1208 static void rcu_initiate_boost_trace(struct rcu_node *rnp)
1209 {
1210         if (list_empty(&rnp->blkd_tasks))
1211                 rnp->n_balk_blkd_tasks++;
1212         else if (rnp->exp_tasks == NULL && rnp->gp_tasks == NULL)
1213                 rnp->n_balk_exp_gp_tasks++;
1214         else if (rnp->gp_tasks != NULL && rnp->boost_tasks != NULL)
1215                 rnp->n_balk_boost_tasks++;
1216         else if (rnp->gp_tasks != NULL && rnp->qsmask != 0)
1217                 rnp->n_balk_notblocked++;
1218         else if (rnp->gp_tasks != NULL &&
1219                  ULONG_CMP_LT(jiffies, rnp->boost_time))
1220                 rnp->n_balk_notyet++;
1221         else
1222                 rnp->n_balk_nos++;
1223 }
1224
1225 #else /* #ifdef CONFIG_RCU_TRACE */
1226
1227 static void rcu_initiate_boost_trace(struct rcu_node *rnp)
1228 {
1229 }
1230
1231 #endif /* #else #ifdef CONFIG_RCU_TRACE */
1232
1233 /*
1234  * Carry out RCU priority boosting on the task indicated by ->exp_tasks
1235  * or ->boost_tasks, advancing the pointer to the next task in the
1236  * ->blkd_tasks list.
1237  *
1238  * Note that irqs must be enabled: boosting the task can block.
1239  * Returns 1 if there are more tasks needing to be boosted.
1240  */
1241 static int rcu_boost(struct rcu_node *rnp)
1242 {
1243         unsigned long flags;
1244         struct rt_mutex mtx;
1245         struct task_struct *t;
1246         struct list_head *tb;
1247
1248         if (rnp->exp_tasks == NULL && rnp->boost_tasks == NULL)
1249                 return 0;  /* Nothing left to boost. */
1250
1251         raw_spin_lock_irqsave(&rnp->lock, flags);
1252
1253         /*
1254          * Recheck under the lock: all tasks in need of boosting
1255          * might exit their RCU read-side critical sections on their own.
1256          */
1257         if (rnp->exp_tasks == NULL && rnp->boost_tasks == NULL) {
1258                 raw_spin_unlock_irqrestore(&rnp->lock, flags);
1259                 return 0;
1260         }
1261
1262         /*
1263          * Preferentially boost tasks blocking expedited grace periods.
1264          * This cannot starve the normal grace periods because a second
1265          * expedited grace period must boost all blocked tasks, including
1266          * those blocking the pre-existing normal grace period.
1267          */
1268         if (rnp->exp_tasks != NULL) {
1269                 tb = rnp->exp_tasks;
1270                 rnp->n_exp_boosts++;
1271         } else {
1272                 tb = rnp->boost_tasks;
1273                 rnp->n_normal_boosts++;
1274         }
1275         rnp->n_tasks_boosted++;
1276
1277         /*
1278          * We boost task t by manufacturing an rt_mutex that appears to
1279          * be held by task t.  We leave a pointer to that rt_mutex where
1280          * task t can find it, and task t will release the mutex when it
1281          * exits its outermost RCU read-side critical section.  Then
1282          * simply acquiring this artificial rt_mutex will boost task
1283          * t's priority.  (Thanks to tglx for suggesting this approach!)
1284          *
1285          * Note that task t must acquire rnp->lock to remove itself from
1286          * the ->blkd_tasks list, which it will do from exit() if from
1287          * nowhere else.  We therefore are guaranteed that task t will
1288          * stay around at least until we drop rnp->lock.  Note that
1289          * rnp->lock also resolves races between our priority boosting
1290          * and task t's exiting its outermost RCU read-side critical
1291          * section.
1292          */
1293         t = container_of(tb, struct task_struct, rcu_node_entry);
1294         rt_mutex_init_proxy_locked(&mtx, t);
1295         t->rcu_boost_mutex = &mtx;
1296         raw_spin_unlock_irqrestore(&rnp->lock, flags);
1297         rt_mutex_lock(&mtx);  /* Side effect: boosts task t's priority. */
1298         rt_mutex_unlock(&mtx);  /* Keep lockdep happy. */
1299
1300         return ACCESS_ONCE(rnp->exp_tasks) != NULL ||
1301                ACCESS_ONCE(rnp->boost_tasks) != NULL;
1302 }
1303
1304 /*
1305  * Timer handler to initiate waking up of boost kthreads that
1306  * have yielded the CPU due to excessive numbers of tasks to
1307  * boost.  We wake up the per-rcu_node kthread, which in turn
1308  * will wake up the booster kthread.
1309  */
1310 static void rcu_boost_kthread_timer(unsigned long arg)
1311 {
1312         invoke_rcu_node_kthread((struct rcu_node *)arg);
1313 }
1314
1315 /*
1316  * Priority-boosting kthread.  One per leaf rcu_node and one for the
1317  * root rcu_node.
1318  */
1319 static int rcu_boost_kthread(void *arg)
1320 {
1321         struct rcu_node *rnp = (struct rcu_node *)arg;
1322         int spincnt = 0;
1323         int more2boost;
1324
1325         trace_rcu_utilization("Start boost kthread@init");
1326         for (;;) {
1327                 rnp->boost_kthread_status = RCU_KTHREAD_WAITING;
1328                 trace_rcu_utilization("End boost kthread@rcu_wait");
1329                 rcu_wait(rnp->boost_tasks || rnp->exp_tasks);
1330                 trace_rcu_utilization("Start boost kthread@rcu_wait");
1331                 rnp->boost_kthread_status = RCU_KTHREAD_RUNNING;
1332                 more2boost = rcu_boost(rnp);
1333                 if (more2boost)
1334                         spincnt++;
1335                 else
1336                         spincnt = 0;
1337                 if (spincnt > 10) {
1338                         trace_rcu_utilization("End boost kthread@rcu_yield");
1339                         rcu_yield(rcu_boost_kthread_timer, (unsigned long)rnp);
1340                         trace_rcu_utilization("Start boost kthread@rcu_yield");
1341                         spincnt = 0;
1342                 }
1343         }
1344         /* NOTREACHED */
1345         trace_rcu_utilization("End boost kthread@notreached");
1346         return 0;
1347 }
1348
1349 /*
1350  * Check to see if it is time to start boosting RCU readers that are
1351  * blocking the current grace period, and, if so, tell the per-rcu_node
1352  * kthread to start boosting them.  If there is an expedited grace
1353  * period in progress, it is always time to boost.
1354  *
1355  * The caller must hold rnp->lock, which this function releases,
1356  * but irqs remain disabled.  The ->boost_kthread_task is immortal,
1357  * so we don't need to worry about it going away.
1358  */
1359 static void rcu_initiate_boost(struct rcu_node *rnp, unsigned long flags)
1360 {
1361         struct task_struct *t;
1362
1363         if (!rcu_preempt_blocked_readers_cgp(rnp) && rnp->exp_tasks == NULL) {
1364                 rnp->n_balk_exp_gp_tasks++;
1365                 raw_spin_unlock_irqrestore(&rnp->lock, flags);
1366                 return;
1367         }
1368         if (rnp->exp_tasks != NULL ||
1369             (rnp->gp_tasks != NULL &&
1370              rnp->boost_tasks == NULL &&
1371              rnp->qsmask == 0 &&
1372              ULONG_CMP_GE(jiffies, rnp->boost_time))) {
1373                 if (rnp->exp_tasks == NULL)
1374                         rnp->boost_tasks = rnp->gp_tasks;
1375                 raw_spin_unlock_irqrestore(&rnp->lock, flags);
1376                 t = rnp->boost_kthread_task;
1377                 if (t != NULL)
1378                         wake_up_process(t);
1379         } else {
1380                 rcu_initiate_boost_trace(rnp);
1381                 raw_spin_unlock_irqrestore(&rnp->lock, flags);
1382         }
1383 }
1384
1385 /*
1386  * Wake up the per-CPU kthread to invoke RCU callbacks.
1387  */
1388 static void invoke_rcu_callbacks_kthread(void)
1389 {
1390         unsigned long flags;
1391
1392         local_irq_save(flags);
1393         __this_cpu_write(rcu_cpu_has_work, 1);
1394         if (__this_cpu_read(rcu_cpu_kthread_task) != NULL &&
1395             current != __this_cpu_read(rcu_cpu_kthread_task))
1396                 wake_up_process(__this_cpu_read(rcu_cpu_kthread_task));
1397         local_irq_restore(flags);
1398 }
1399
1400 /*
1401  * Is the current CPU running the RCU-callbacks kthread?
1402  * Caller must have preemption disabled.
1403  */
1404 static bool rcu_is_callbacks_kthread(void)
1405 {
1406         return __get_cpu_var(rcu_cpu_kthread_task) == current;
1407 }
1408
1409 /*
1410  * Set the affinity of the boost kthread.  The CPU-hotplug locks are
1411  * held, so no one should be messing with the existence of the boost
1412  * kthread.
1413  */
1414 static void rcu_boost_kthread_setaffinity(struct rcu_node *rnp,
1415                                           cpumask_var_t cm)
1416 {
1417         struct task_struct *t;
1418
1419         t = rnp->boost_kthread_task;
1420         if (t != NULL)
1421                 set_cpus_allowed_ptr(rnp->boost_kthread_task, cm);
1422 }
1423
1424 #define RCU_BOOST_DELAY_JIFFIES DIV_ROUND_UP(CONFIG_RCU_BOOST_DELAY * HZ, 1000)
1425
1426 /*
1427  * Do priority-boost accounting for the start of a new grace period.
1428  */
1429 static void rcu_preempt_boost_start_gp(struct rcu_node *rnp)
1430 {
1431         rnp->boost_time = jiffies + RCU_BOOST_DELAY_JIFFIES;
1432 }
1433
1434 /*
1435  * Create an RCU-boost kthread for the specified node if one does not
1436  * already exist.  We only create this kthread for preemptible RCU.
1437  * Returns zero if all is well, a negated errno otherwise.
1438  */
1439 static int __cpuinit rcu_spawn_one_boost_kthread(struct rcu_state *rsp,
1440                                                  struct rcu_node *rnp,
1441                                                  int rnp_index)
1442 {
1443         unsigned long flags;
1444         struct sched_param sp;
1445         struct task_struct *t;
1446
1447         if (&rcu_preempt_state != rsp)
1448                 return 0;
1449         rsp->boost = 1;
1450         if (rnp->boost_kthread_task != NULL)
1451                 return 0;
1452         t = kthread_create(rcu_boost_kthread, (void *)rnp,
1453                            "rcub/%d", rnp_index);
1454         if (IS_ERR(t))
1455                 return PTR_ERR(t);
1456         raw_spin_lock_irqsave(&rnp->lock, flags);
1457         rnp->boost_kthread_task = t;
1458         raw_spin_unlock_irqrestore(&rnp->lock, flags);
1459         sp.sched_priority = RCU_BOOST_PRIO;
1460         sched_setscheduler_nocheck(t, SCHED_FIFO, &sp);
1461         wake_up_process(t); /* get to TASK_INTERRUPTIBLE quickly. */
1462         return 0;
1463 }
1464
1465 #ifdef CONFIG_HOTPLUG_CPU
1466
1467 /*
1468  * Stop the RCU's per-CPU kthread when its CPU goes offline,.
1469  */
1470 static void rcu_stop_cpu_kthread(int cpu)
1471 {
1472         struct task_struct *t;
1473
1474         /* Stop the CPU's kthread. */
1475         t = per_cpu(rcu_cpu_kthread_task, cpu);
1476         if (t != NULL) {
1477                 per_cpu(rcu_cpu_kthread_task, cpu) = NULL;
1478                 kthread_stop(t);
1479         }
1480 }
1481
1482 #endif /* #ifdef CONFIG_HOTPLUG_CPU */
1483
1484 static void rcu_kthread_do_work(void)
1485 {
1486         rcu_do_batch(&rcu_sched_state, &__get_cpu_var(rcu_sched_data));
1487         rcu_do_batch(&rcu_bh_state, &__get_cpu_var(rcu_bh_data));
1488         rcu_preempt_do_callbacks();
1489 }
1490
1491 /*
1492  * Wake up the specified per-rcu_node-structure kthread.
1493  * Because the per-rcu_node kthreads are immortal, we don't need
1494  * to do anything to keep them alive.
1495  */
1496 static void invoke_rcu_node_kthread(struct rcu_node *rnp)
1497 {
1498         struct task_struct *t;
1499
1500         t = rnp->node_kthread_task;
1501         if (t != NULL)
1502                 wake_up_process(t);
1503 }
1504
1505 /*
1506  * Set the specified CPU's kthread to run RT or not, as specified by
1507  * the to_rt argument.  The CPU-hotplug locks are held, so the task
1508  * is not going away.
1509  */
1510 static void rcu_cpu_kthread_setrt(int cpu, int to_rt)
1511 {
1512         int policy;
1513         struct sched_param sp;
1514         struct task_struct *t;
1515
1516         t = per_cpu(rcu_cpu_kthread_task, cpu);
1517         if (t == NULL)
1518                 return;
1519         if (to_rt) {
1520                 policy = SCHED_FIFO;
1521                 sp.sched_priority = RCU_KTHREAD_PRIO;
1522         } else {
1523                 policy = SCHED_NORMAL;
1524                 sp.sched_priority = 0;
1525         }
1526         sched_setscheduler_nocheck(t, policy, &sp);
1527 }
1528
1529 /*
1530  * Timer handler to initiate the waking up of per-CPU kthreads that
1531  * have yielded the CPU due to excess numbers of RCU callbacks.
1532  * We wake up the per-rcu_node kthread, which in turn will wake up
1533  * the booster kthread.
1534  */
1535 static void rcu_cpu_kthread_timer(unsigned long arg)
1536 {
1537         struct rcu_data *rdp = per_cpu_ptr(rcu_state->rda, arg);
1538         struct rcu_node *rnp = rdp->mynode;
1539
1540         atomic_or(rdp->grpmask, &rnp->wakemask);
1541         invoke_rcu_node_kthread(rnp);
1542 }
1543
1544 /*
1545  * Drop to non-real-time priority and yield, but only after posting a
1546  * timer that will cause us to regain our real-time priority if we
1547  * remain preempted.  Either way, we restore our real-time priority
1548  * before returning.
1549  */
1550 static void rcu_yield(void (*f)(unsigned long), unsigned long arg)
1551 {
1552         struct sched_param sp;
1553         struct timer_list yield_timer;
1554         int prio = current->rt_priority;
1555
1556         setup_timer_on_stack(&yield_timer, f, arg);
1557         mod_timer(&yield_timer, jiffies + 2);
1558         sp.sched_priority = 0;
1559         sched_setscheduler_nocheck(current, SCHED_NORMAL, &sp);
1560         set_user_nice(current, 19);
1561         schedule();
1562         set_user_nice(current, 0);
1563         sp.sched_priority = prio;
1564         sched_setscheduler_nocheck(current, SCHED_FIFO, &sp);
1565         del_timer(&yield_timer);
1566 }
1567
1568 /*
1569  * Handle cases where the rcu_cpu_kthread() ends up on the wrong CPU.
1570  * This can happen while the corresponding CPU is either coming online
1571  * or going offline.  We cannot wait until the CPU is fully online
1572  * before starting the kthread, because the various notifier functions
1573  * can wait for RCU grace periods.  So we park rcu_cpu_kthread() until
1574  * the corresponding CPU is online.
1575  *
1576  * Return 1 if the kthread needs to stop, 0 otherwise.
1577  *
1578  * Caller must disable bh.  This function can momentarily enable it.
1579  */
1580 static int rcu_cpu_kthread_should_stop(int cpu)
1581 {
1582         while (cpu_is_offline(cpu) ||
1583                !cpumask_equal(&current->cpus_allowed, cpumask_of(cpu)) ||
1584                smp_processor_id() != cpu) {
1585                 if (kthread_should_stop())
1586                         return 1;
1587                 per_cpu(rcu_cpu_kthread_status, cpu) = RCU_KTHREAD_OFFCPU;
1588                 per_cpu(rcu_cpu_kthread_cpu, cpu) = raw_smp_processor_id();
1589                 local_bh_enable();
1590                 schedule_timeout_uninterruptible(1);
1591                 if (!cpumask_equal(&current->cpus_allowed, cpumask_of(cpu)))
1592                         set_cpus_allowed_ptr(current, cpumask_of(cpu));
1593                 local_bh_disable();
1594         }
1595         per_cpu(rcu_cpu_kthread_cpu, cpu) = cpu;
1596         return 0;
1597 }
1598
1599 /*
1600  * Per-CPU kernel thread that invokes RCU callbacks.  This replaces the
1601  * RCU softirq used in flavors and configurations of RCU that do not
1602  * support RCU priority boosting.
1603  */
1604 static int rcu_cpu_kthread(void *arg)
1605 {
1606         int cpu = (int)(long)arg;
1607         unsigned long flags;
1608         int spincnt = 0;
1609         unsigned int *statusp = &per_cpu(rcu_cpu_kthread_status, cpu);
1610         char work;
1611         char *workp = &per_cpu(rcu_cpu_has_work, cpu);
1612
1613         trace_rcu_utilization("Start CPU kthread@init");
1614         for (;;) {
1615                 *statusp = RCU_KTHREAD_WAITING;
1616                 trace_rcu_utilization("End CPU kthread@rcu_wait");
1617                 rcu_wait(*workp != 0 || kthread_should_stop());
1618                 trace_rcu_utilization("Start CPU kthread@rcu_wait");
1619                 local_bh_disable();
1620                 if (rcu_cpu_kthread_should_stop(cpu)) {
1621                         local_bh_enable();
1622                         break;
1623                 }
1624                 *statusp = RCU_KTHREAD_RUNNING;
1625                 per_cpu(rcu_cpu_kthread_loops, cpu)++;
1626                 local_irq_save(flags);
1627                 work = *workp;
1628                 *workp = 0;
1629                 local_irq_restore(flags);
1630                 if (work)
1631                         rcu_kthread_do_work();
1632                 local_bh_enable();
1633                 if (*workp != 0)
1634                         spincnt++;
1635                 else
1636                         spincnt = 0;
1637                 if (spincnt > 10) {
1638                         *statusp = RCU_KTHREAD_YIELDING;
1639                         trace_rcu_utilization("End CPU kthread@rcu_yield");
1640                         rcu_yield(rcu_cpu_kthread_timer, (unsigned long)cpu);
1641                         trace_rcu_utilization("Start CPU kthread@rcu_yield");
1642                         spincnt = 0;
1643                 }
1644         }
1645         *statusp = RCU_KTHREAD_STOPPED;
1646         trace_rcu_utilization("End CPU kthread@term");
1647         return 0;
1648 }
1649
1650 /*
1651  * Spawn a per-CPU kthread, setting up affinity and priority.
1652  * Because the CPU hotplug lock is held, no other CPU will be attempting
1653  * to manipulate rcu_cpu_kthread_task.  There might be another CPU
1654  * attempting to access it during boot, but the locking in kthread_bind()
1655  * will enforce sufficient ordering.
1656  *
1657  * Please note that we cannot simply refuse to wake up the per-CPU
1658  * kthread because kthreads are created in TASK_UNINTERRUPTIBLE state,
1659  * which can result in softlockup complaints if the task ends up being
1660  * idle for more than a couple of minutes.
1661  *
1662  * However, please note also that we cannot bind the per-CPU kthread to its
1663  * CPU until that CPU is fully online.  We also cannot wait until the
1664  * CPU is fully online before we create its per-CPU kthread, as this would
1665  * deadlock the system when CPU notifiers tried waiting for grace
1666  * periods.  So we bind the per-CPU kthread to its CPU only if the CPU
1667  * is online.  If its CPU is not yet fully online, then the code in
1668  * rcu_cpu_kthread() will wait until it is fully online, and then do
1669  * the binding.
1670  */
1671 static int __cpuinit rcu_spawn_one_cpu_kthread(int cpu)
1672 {
1673         struct sched_param sp;
1674         struct task_struct *t;
1675
1676         if (!rcu_scheduler_fully_active ||
1677             per_cpu(rcu_cpu_kthread_task, cpu) != NULL)
1678                 return 0;
1679         t = kthread_create_on_node(rcu_cpu_kthread,
1680                                    (void *)(long)cpu,
1681                                    cpu_to_node(cpu),
1682                                    "rcuc/%d", cpu);
1683         if (IS_ERR(t))
1684                 return PTR_ERR(t);
1685         if (cpu_online(cpu))
1686                 kthread_bind(t, cpu);
1687         per_cpu(rcu_cpu_kthread_cpu, cpu) = cpu;
1688         WARN_ON_ONCE(per_cpu(rcu_cpu_kthread_task, cpu) != NULL);
1689         sp.sched_priority = RCU_KTHREAD_PRIO;
1690         sched_setscheduler_nocheck(t, SCHED_FIFO, &sp);
1691         per_cpu(rcu_cpu_kthread_task, cpu) = t;
1692         wake_up_process(t); /* Get to TASK_INTERRUPTIBLE quickly. */
1693         return 0;
1694 }
1695
1696 /*
1697  * Per-rcu_node kthread, which is in charge of waking up the per-CPU
1698  * kthreads when needed.  We ignore requests to wake up kthreads
1699  * for offline CPUs, which is OK because force_quiescent_state()
1700  * takes care of this case.
1701  */
1702 static int rcu_node_kthread(void *arg)
1703 {
1704         int cpu;
1705         unsigned long flags;
1706         unsigned long mask;
1707         struct rcu_node *rnp = (struct rcu_node *)arg;
1708         struct sched_param sp;
1709         struct task_struct *t;
1710
1711         for (;;) {
1712                 rnp->node_kthread_status = RCU_KTHREAD_WAITING;
1713                 rcu_wait(atomic_read(&rnp->wakemask) != 0);
1714                 rnp->node_kthread_status = RCU_KTHREAD_RUNNING;
1715                 raw_spin_lock_irqsave(&rnp->lock, flags);
1716                 mask = atomic_xchg(&rnp->wakemask, 0);
1717                 rcu_initiate_boost(rnp, flags); /* releases rnp->lock. */
1718                 for (cpu = rnp->grplo; cpu <= rnp->grphi; cpu++, mask >>= 1) {
1719                         if ((mask & 0x1) == 0)
1720                                 continue;
1721                         preempt_disable();
1722                         t = per_cpu(rcu_cpu_kthread_task, cpu);
1723                         if (!cpu_online(cpu) || t == NULL) {
1724                                 preempt_enable();
1725                                 continue;
1726                         }
1727                         per_cpu(rcu_cpu_has_work, cpu) = 1;
1728                         sp.sched_priority = RCU_KTHREAD_PRIO;
1729                         sched_setscheduler_nocheck(t, SCHED_FIFO, &sp);
1730                         preempt_enable();
1731                 }
1732         }
1733         /* NOTREACHED */
1734         rnp->node_kthread_status = RCU_KTHREAD_STOPPED;
1735         return 0;
1736 }
1737
1738 /*
1739  * Set the per-rcu_node kthread's affinity to cover all CPUs that are
1740  * served by the rcu_node in question.  The CPU hotplug lock is still
1741  * held, so the value of rnp->qsmaskinit will be stable.
1742  *
1743  * We don't include outgoingcpu in the affinity set, use -1 if there is
1744  * no outgoing CPU.  If there are no CPUs left in the affinity set,
1745  * this function allows the kthread to execute on any CPU.
1746  */
1747 static void rcu_node_kthread_setaffinity(struct rcu_node *rnp, int outgoingcpu)
1748 {
1749         cpumask_var_t cm;
1750         int cpu;
1751         unsigned long mask = rnp->qsmaskinit;
1752
1753         if (rnp->node_kthread_task == NULL)
1754                 return;
1755         if (!alloc_cpumask_var(&cm, GFP_KERNEL))
1756                 return;
1757         cpumask_clear(cm);
1758         for (cpu = rnp->grplo; cpu <= rnp->grphi; cpu++, mask >>= 1)
1759                 if ((mask & 0x1) && cpu != outgoingcpu)
1760                         cpumask_set_cpu(cpu, cm);
1761         if (cpumask_weight(cm) == 0) {
1762                 cpumask_setall(cm);
1763                 for (cpu = rnp->grplo; cpu <= rnp->grphi; cpu++)
1764                         cpumask_clear_cpu(cpu, cm);
1765                 WARN_ON_ONCE(cpumask_weight(cm) == 0);
1766         }
1767         set_cpus_allowed_ptr(rnp->node_kthread_task, cm);
1768         rcu_boost_kthread_setaffinity(rnp, cm);
1769         free_cpumask_var(cm);
1770 }
1771
1772 /*
1773  * Spawn a per-rcu_node kthread, setting priority and affinity.
1774  * Called during boot before online/offline can happen, or, if
1775  * during runtime, with the main CPU-hotplug locks held.  So only
1776  * one of these can be executing at a time.
1777  */
1778 static int __cpuinit rcu_spawn_one_node_kthread(struct rcu_state *rsp,
1779                                                 struct rcu_node *rnp)
1780 {
1781         unsigned long flags;
1782         int rnp_index = rnp - &rsp->node[0];
1783         struct sched_param sp;
1784         struct task_struct *t;
1785
1786         if (!rcu_scheduler_fully_active ||
1787             rnp->qsmaskinit == 0)
1788                 return 0;
1789         if (rnp->node_kthread_task == NULL) {
1790                 t = kthread_create(rcu_node_kthread, (void *)rnp,
1791                                    "rcun/%d", rnp_index);
1792                 if (IS_ERR(t))
1793                         return PTR_ERR(t);
1794                 raw_spin_lock_irqsave(&rnp->lock, flags);
1795                 rnp->node_kthread_task = t;
1796                 raw_spin_unlock_irqrestore(&rnp->lock, flags);
1797                 sp.sched_priority = 99;
1798                 sched_setscheduler_nocheck(t, SCHED_FIFO, &sp);
1799                 wake_up_process(t); /* get to TASK_INTERRUPTIBLE quickly. */
1800         }
1801         return rcu_spawn_one_boost_kthread(rsp, rnp, rnp_index);
1802 }
1803
1804 /*
1805  * Spawn all kthreads -- called as soon as the scheduler is running.
1806  */
1807 static int __init rcu_spawn_kthreads(void)
1808 {
1809         int cpu;
1810         struct rcu_node *rnp;
1811
1812         rcu_scheduler_fully_active = 1;
1813         for_each_possible_cpu(cpu) {
1814                 per_cpu(rcu_cpu_has_work, cpu) = 0;
1815                 if (cpu_online(cpu))
1816                         (void)rcu_spawn_one_cpu_kthread(cpu);
1817         }
1818         rnp = rcu_get_root(rcu_state);
1819         (void)rcu_spawn_one_node_kthread(rcu_state, rnp);
1820         if (NUM_RCU_NODES > 1) {
1821                 rcu_for_each_leaf_node(rcu_state, rnp)
1822                         (void)rcu_spawn_one_node_kthread(rcu_state, rnp);
1823         }
1824         return 0;
1825 }
1826 early_initcall(rcu_spawn_kthreads);
1827
1828 static void __cpuinit rcu_prepare_kthreads(int cpu)
1829 {
1830         struct rcu_data *rdp = per_cpu_ptr(rcu_state->rda, cpu);
1831         struct rcu_node *rnp = rdp->mynode;
1832
1833         /* Fire up the incoming CPU's kthread and leaf rcu_node kthread. */
1834         if (rcu_scheduler_fully_active) {
1835                 (void)rcu_spawn_one_cpu_kthread(cpu);
1836                 if (rnp->node_kthread_task == NULL)
1837                         (void)rcu_spawn_one_node_kthread(rcu_state, rnp);
1838         }
1839 }
1840
1841 #else /* #ifdef CONFIG_RCU_BOOST */
1842
1843 static void rcu_initiate_boost(struct rcu_node *rnp, unsigned long flags)
1844 {
1845         raw_spin_unlock_irqrestore(&rnp->lock, flags);
1846 }
1847
1848 static void invoke_rcu_callbacks_kthread(void)
1849 {
1850         WARN_ON_ONCE(1);
1851 }
1852
1853 static bool rcu_is_callbacks_kthread(void)
1854 {
1855         return false;
1856 }
1857
1858 static void rcu_preempt_boost_start_gp(struct rcu_node *rnp)
1859 {
1860 }
1861
1862 #ifdef CONFIG_HOTPLUG_CPU
1863
1864 static void rcu_stop_cpu_kthread(int cpu)
1865 {
1866 }
1867
1868 #endif /* #ifdef CONFIG_HOTPLUG_CPU */
1869
1870 static void rcu_node_kthread_setaffinity(struct rcu_node *rnp, int outgoingcpu)
1871 {
1872 }
1873
1874 static void rcu_cpu_kthread_setrt(int cpu, int to_rt)
1875 {
1876 }
1877
1878 static int __init rcu_scheduler_really_started(void)
1879 {
1880         rcu_scheduler_fully_active = 1;
1881         return 0;
1882 }
1883 early_initcall(rcu_scheduler_really_started);
1884
1885 static void __cpuinit rcu_prepare_kthreads(int cpu)
1886 {
1887 }
1888
1889 #endif /* #else #ifdef CONFIG_RCU_BOOST */
1890
1891 #if !defined(CONFIG_RCU_FAST_NO_HZ)
1892
1893 /*
1894  * Check to see if any future RCU-related work will need to be done
1895  * by the current CPU, even if none need be done immediately, returning
1896  * 1 if so.  This function is part of the RCU implementation; it is -not-
1897  * an exported member of the RCU API.
1898  *
1899  * Because we not have RCU_FAST_NO_HZ, just check whether this CPU needs
1900  * any flavor of RCU.
1901  */
1902 int rcu_needs_cpu(int cpu, unsigned long *delta_jiffies)
1903 {
1904         *delta_jiffies = ULONG_MAX;
1905         return rcu_cpu_has_callbacks(cpu);
1906 }
1907
1908 /*
1909  * Because we do not have RCU_FAST_NO_HZ, don't bother initializing for it.
1910  */
1911 static void rcu_prepare_for_idle_init(int cpu)
1912 {
1913 }
1914
1915 /*
1916  * Because we do not have RCU_FAST_NO_HZ, don't bother cleaning up
1917  * after it.
1918  */
1919 static void rcu_cleanup_after_idle(int cpu)
1920 {
1921 }
1922
1923 /*
1924  * Do the idle-entry grace-period work, which, because CONFIG_RCU_FAST_NO_HZ=n,
1925  * is nothing.
1926  */
1927 static void rcu_prepare_for_idle(int cpu)
1928 {
1929 }
1930
1931 /*
1932  * Don't bother keeping a running count of the number of RCU callbacks
1933  * posted because CONFIG_RCU_FAST_NO_HZ=n.
1934  */
1935 static void rcu_idle_count_callbacks_posted(void)
1936 {
1937 }
1938
1939 #else /* #if !defined(CONFIG_RCU_FAST_NO_HZ) */
1940
1941 /*
1942  * This code is invoked when a CPU goes idle, at which point we want
1943  * to have the CPU do everything required for RCU so that it can enter
1944  * the energy-efficient dyntick-idle mode.  This is handled by a
1945  * state machine implemented by rcu_prepare_for_idle() below.
1946  *
1947  * The following three proprocessor symbols control this state machine:
1948  *
1949  * RCU_IDLE_FLUSHES gives the maximum number of times that we will attempt
1950  *      to satisfy RCU.  Beyond this point, it is better to incur a periodic
1951  *      scheduling-clock interrupt than to loop through the state machine
1952  *      at full power.
1953  * RCU_IDLE_OPT_FLUSHES gives the number of RCU_IDLE_FLUSHES that are
1954  *      optional if RCU does not need anything immediately from this
1955  *      CPU, even if this CPU still has RCU callbacks queued.  The first
1956  *      times through the state machine are mandatory: we need to give
1957  *      the state machine a chance to communicate a quiescent state
1958  *      to the RCU core.
1959  * RCU_IDLE_GP_DELAY gives the number of jiffies that a CPU is permitted
1960  *      to sleep in dyntick-idle mode with RCU callbacks pending.  This
1961  *      is sized to be roughly one RCU grace period.  Those energy-efficiency
1962  *      benchmarkers who might otherwise be tempted to set this to a large
1963  *      number, be warned: Setting RCU_IDLE_GP_DELAY too high can hang your
1964  *      system.  And if you are -that- concerned about energy efficiency,
1965  *      just power the system down and be done with it!
1966  * RCU_IDLE_LAZY_GP_DELAY gives the number of jiffies that a CPU is
1967  *      permitted to sleep in dyntick-idle mode with only lazy RCU
1968  *      callbacks pending.  Setting this too high can OOM your system.
1969  *
1970  * The values below work well in practice.  If future workloads require
1971  * adjustment, they can be converted into kernel config parameters, though
1972  * making the state machine smarter might be a better option.
1973  */
1974 #define RCU_IDLE_FLUSHES 5              /* Number of dyntick-idle tries. */
1975 #define RCU_IDLE_OPT_FLUSHES 3          /* Optional dyntick-idle tries. */
1976 #define RCU_IDLE_GP_DELAY 6             /* Roughly one grace period. */
1977 #define RCU_IDLE_LAZY_GP_DELAY (6 * HZ) /* Roughly six seconds. */
1978
1979 /*
1980  * Does the specified flavor of RCU have non-lazy callbacks pending on
1981  * the specified CPU?  Both RCU flavor and CPU are specified by the
1982  * rcu_data structure.
1983  */
1984 static bool __rcu_cpu_has_nonlazy_callbacks(struct rcu_data *rdp)
1985 {
1986         return rdp->qlen != rdp->qlen_lazy;
1987 }
1988
1989 #ifdef CONFIG_TREE_PREEMPT_RCU
1990
1991 /*
1992  * Are there non-lazy RCU-preempt callbacks?  (There cannot be if there
1993  * is no RCU-preempt in the kernel.)
1994  */
1995 static bool rcu_preempt_cpu_has_nonlazy_callbacks(int cpu)
1996 {
1997         struct rcu_data *rdp = &per_cpu(rcu_preempt_data, cpu);
1998
1999         return __rcu_cpu_has_nonlazy_callbacks(rdp);
2000 }
2001
2002 #else /* #ifdef CONFIG_TREE_PREEMPT_RCU */
2003
2004 static bool rcu_preempt_cpu_has_nonlazy_callbacks(int cpu)
2005 {
2006         return 0;
2007 }
2008
2009 #endif /* else #ifdef CONFIG_TREE_PREEMPT_RCU */
2010
2011 /*
2012  * Does any flavor of RCU have non-lazy callbacks on the specified CPU?
2013  */
2014 static bool rcu_cpu_has_nonlazy_callbacks(int cpu)
2015 {
2016         return __rcu_cpu_has_nonlazy_callbacks(&per_cpu(rcu_sched_data, cpu)) ||
2017                __rcu_cpu_has_nonlazy_callbacks(&per_cpu(rcu_bh_data, cpu)) ||
2018                rcu_preempt_cpu_has_nonlazy_callbacks(cpu);
2019 }
2020
2021 /*
2022  * Allow the CPU to enter dyntick-idle mode if either: (1) There are no
2023  * callbacks on this CPU, (2) this CPU has not yet attempted to enter
2024  * dyntick-idle mode, or (3) this CPU is in the process of attempting to
2025  * enter dyntick-idle mode.  Otherwise, if we have recently tried and failed
2026  * to enter dyntick-idle mode, we refuse to try to enter it.  After all,
2027  * it is better to incur scheduling-clock interrupts than to spin
2028  * continuously for the same time duration!
2029  *
2030  * The delta_jiffies argument is used to store the time when RCU is
2031  * going to need the CPU again if it still has callbacks.  The reason
2032  * for this is that rcu_prepare_for_idle() might need to post a timer,
2033  * but if so, it will do so after tick_nohz_stop_sched_tick() has set
2034  * the wakeup time for this CPU.  This means that RCU's timer can be
2035  * delayed until the wakeup time, which defeats the purpose of posting
2036  * a timer.
2037  */
2038 int rcu_needs_cpu(int cpu, unsigned long *delta_jiffies)
2039 {
2040         struct rcu_dynticks *rdtp = &per_cpu(rcu_dynticks, cpu);
2041
2042         /* Flag a new idle sojourn to the idle-entry state machine. */
2043         rdtp->idle_first_pass = 1;
2044         /* If no callbacks, RCU doesn't need the CPU. */
2045         if (!rcu_cpu_has_callbacks(cpu)) {
2046                 *delta_jiffies = ULONG_MAX;
2047                 return 0;
2048         }
2049         if (rdtp->dyntick_holdoff == jiffies) {
2050                 /* RCU recently tried and failed, so don't try again. */
2051                 *delta_jiffies = 1;
2052                 return 1;
2053         }
2054         /* Set up for the possibility that RCU will post a timer. */
2055         if (rcu_cpu_has_nonlazy_callbacks(cpu))
2056                 *delta_jiffies = RCU_IDLE_GP_DELAY;
2057         else
2058                 *delta_jiffies = RCU_IDLE_LAZY_GP_DELAY;
2059         return 0;
2060 }
2061
2062 /*
2063  * Handler for smp_call_function_single().  The only point of this
2064  * handler is to wake the CPU up, so the handler does only tracing.
2065  */
2066 void rcu_idle_demigrate(void *unused)
2067 {
2068         trace_rcu_prep_idle("Demigrate");
2069 }
2070
2071 /*
2072  * Timer handler used to force CPU to start pushing its remaining RCU
2073  * callbacks in the case where it entered dyntick-idle mode with callbacks
2074  * pending.  The hander doesn't really need to do anything because the
2075  * real work is done upon re-entry to idle, or by the next scheduling-clock
2076  * interrupt should idle not be re-entered.
2077  *
2078  * One special case: the timer gets migrated without awakening the CPU
2079  * on which the timer was scheduled on.  In this case, we must wake up
2080  * that CPU.  We do so with smp_call_function_single().
2081  */
2082 static void rcu_idle_gp_timer_func(unsigned long cpu_in)
2083 {
2084         int cpu = (int)cpu_in;
2085
2086         trace_rcu_prep_idle("Timer");
2087         if (cpu != smp_processor_id())
2088                 smp_call_function_single(cpu, rcu_idle_demigrate, NULL, 0);
2089         else
2090                 WARN_ON_ONCE(1); /* Getting here can hang the system... */
2091 }
2092
2093 /*
2094  * Initialize the timer used to pull CPUs out of dyntick-idle mode.
2095  */
2096 static void rcu_prepare_for_idle_init(int cpu)
2097 {
2098         struct rcu_dynticks *rdtp = &per_cpu(rcu_dynticks, cpu);
2099
2100         rdtp->dyntick_holdoff = jiffies - 1;
2101         setup_timer(&rdtp->idle_gp_timer, rcu_idle_gp_timer_func, cpu);
2102         rdtp->idle_gp_timer_expires = jiffies - 1;
2103         rdtp->idle_first_pass = 1;
2104 }
2105
2106 /*
2107  * Clean up for exit from idle.  Because we are exiting from idle, there
2108  * is no longer any point to ->idle_gp_timer, so cancel it.  This will
2109  * do nothing if this timer is not active, so just cancel it unconditionally.
2110  */
2111 static void rcu_cleanup_after_idle(int cpu)
2112 {
2113         struct rcu_dynticks *rdtp = &per_cpu(rcu_dynticks, cpu);
2114
2115         del_timer(&rdtp->idle_gp_timer);
2116         trace_rcu_prep_idle("Cleanup after idle");
2117 }
2118
2119 /*
2120  * Check to see if any RCU-related work can be done by the current CPU,
2121  * and if so, schedule a softirq to get it done.  This function is part
2122  * of the RCU implementation; it is -not- an exported member of the RCU API.
2123  *
2124  * The idea is for the current CPU to clear out all work required by the
2125  * RCU core for the current grace period, so that this CPU can be permitted
2126  * to enter dyntick-idle mode.  In some cases, it will need to be awakened
2127  * at the end of the grace period by whatever CPU ends the grace period.
2128  * This allows CPUs to go dyntick-idle more quickly, and to reduce the
2129  * number of wakeups by a modest integer factor.
2130  *
2131  * Because it is not legal to invoke rcu_process_callbacks() with irqs
2132  * disabled, we do one pass of force_quiescent_state(), then do a
2133  * invoke_rcu_core() to cause rcu_process_callbacks() to be invoked
2134  * later.  The ->dyntick_drain field controls the sequencing.
2135  *
2136  * The caller must have disabled interrupts.
2137  */
2138 static void rcu_prepare_for_idle(int cpu)
2139 {
2140         struct timer_list *tp;
2141         struct rcu_dynticks *rdtp = &per_cpu(rcu_dynticks, cpu);
2142
2143         /*
2144          * If this is an idle re-entry, for example, due to use of
2145          * RCU_NONIDLE() or the new idle-loop tracing API within the idle
2146          * loop, then don't take any state-machine actions, unless the
2147          * momentary exit from idle queued additional non-lazy callbacks.
2148          * Instead, repost the ->idle_gp_timer if this CPU has callbacks
2149          * pending.
2150          */
2151         if (!rdtp->idle_first_pass &&
2152             (rdtp->nonlazy_posted == rdtp->nonlazy_posted_snap)) {
2153                 if (rcu_cpu_has_callbacks(cpu)) {
2154                         tp = &rdtp->idle_gp_timer;
2155                         mod_timer_pinned(tp, rdtp->idle_gp_timer_expires);
2156                 }
2157                 return;
2158         }
2159         rdtp->idle_first_pass = 0;
2160         rdtp->nonlazy_posted_snap = rdtp->nonlazy_posted - 1;
2161
2162         /*
2163          * If there are no callbacks on this CPU, enter dyntick-idle mode.
2164          * Also reset state to avoid prejudicing later attempts.
2165          */
2166         if (!rcu_cpu_has_callbacks(cpu)) {
2167                 rdtp->dyntick_holdoff = jiffies - 1;
2168                 rdtp->dyntick_drain = 0;
2169                 trace_rcu_prep_idle("No callbacks");
2170                 return;
2171         }
2172
2173         /*
2174          * If in holdoff mode, just return.  We will presumably have
2175          * refrained from disabling the scheduling-clock tick.
2176          */
2177         if (rdtp->dyntick_holdoff == jiffies) {
2178                 trace_rcu_prep_idle("In holdoff");
2179                 return;
2180         }
2181
2182         /* Check and update the ->dyntick_drain sequencing. */
2183         if (rdtp->dyntick_drain <= 0) {
2184                 /* First time through, initialize the counter. */
2185                 rdtp->dyntick_drain = RCU_IDLE_FLUSHES;
2186         } else if (rdtp->dyntick_drain <= RCU_IDLE_OPT_FLUSHES &&
2187                    !rcu_pending(cpu) &&
2188                    !local_softirq_pending()) {
2189                 /* Can we go dyntick-idle despite still having callbacks? */
2190                 rdtp->dyntick_drain = 0;
2191                 rdtp->dyntick_holdoff = jiffies;
2192                 if (rcu_cpu_has_nonlazy_callbacks(cpu)) {
2193                         trace_rcu_prep_idle("Dyntick with callbacks");
2194                         rdtp->idle_gp_timer_expires =
2195                                            jiffies + RCU_IDLE_GP_DELAY;
2196                 } else {
2197                         rdtp->idle_gp_timer_expires =
2198                                            jiffies + RCU_IDLE_LAZY_GP_DELAY;
2199                         trace_rcu_prep_idle("Dyntick with lazy callbacks");
2200                 }
2201                 tp = &rdtp->idle_gp_timer;
2202                 mod_timer_pinned(tp, rdtp->idle_gp_timer_expires);
2203                 rdtp->nonlazy_posted_snap = rdtp->nonlazy_posted;
2204                 return; /* Nothing more to do immediately. */
2205         } else if (--(rdtp->dyntick_drain) <= 0) {
2206                 /* We have hit the limit, so time to give up. */
2207                 rdtp->dyntick_holdoff = jiffies;
2208                 trace_rcu_prep_idle("Begin holdoff");
2209                 invoke_rcu_core();  /* Force the CPU out of dyntick-idle. */
2210                 return;
2211         }
2212
2213         /*
2214          * Do one step of pushing the remaining RCU callbacks through
2215          * the RCU core state machine.
2216          */
2217 #ifdef CONFIG_TREE_PREEMPT_RCU
2218         if (per_cpu(rcu_preempt_data, cpu).nxtlist) {
2219                 rcu_preempt_qs(cpu);
2220                 force_quiescent_state(&rcu_preempt_state, 0);
2221         }
2222 #endif /* #ifdef CONFIG_TREE_PREEMPT_RCU */
2223         if (per_cpu(rcu_sched_data, cpu).nxtlist) {
2224                 rcu_sched_qs(cpu);
2225                 force_quiescent_state(&rcu_sched_state, 0);
2226         }
2227         if (per_cpu(rcu_bh_data, cpu).nxtlist) {
2228                 rcu_bh_qs(cpu);
2229                 force_quiescent_state(&rcu_bh_state, 0);
2230         }
2231
2232         /*
2233          * If RCU callbacks are still pending, RCU still needs this CPU.
2234          * So try forcing the callbacks through the grace period.
2235          */
2236         if (rcu_cpu_has_callbacks(cpu)) {
2237                 trace_rcu_prep_idle("More callbacks");
2238                 invoke_rcu_core();
2239         } else
2240                 trace_rcu_prep_idle("Callbacks drained");
2241 }
2242
2243 /*
2244  * Keep a running count of the number of non-lazy callbacks posted
2245  * on this CPU.  This running counter (which is never decremented) allows
2246  * rcu_prepare_for_idle() to detect when something out of the idle loop
2247  * posts a callback, even if an equal number of callbacks are invoked.
2248  * Of course, callbacks should only be posted from within a trace event
2249  * designed to be called from idle or from within RCU_NONIDLE().
2250  */
2251 static void rcu_idle_count_callbacks_posted(void)
2252 {
2253         __this_cpu_add(rcu_dynticks.nonlazy_posted, 1);
2254 }
2255
2256 #endif /* #else #if !defined(CONFIG_RCU_FAST_NO_HZ) */
2257
2258 #ifdef CONFIG_RCU_CPU_STALL_INFO
2259
2260 #ifdef CONFIG_RCU_FAST_NO_HZ
2261
2262 static void print_cpu_stall_fast_no_hz(char *cp, int cpu)
2263 {
2264         struct rcu_dynticks *rdtp = &per_cpu(rcu_dynticks, cpu);
2265         struct timer_list *tltp = &rdtp->idle_gp_timer;
2266
2267         sprintf(cp, "drain=%d %c timer=%lu",
2268                 rdtp->dyntick_drain,
2269                 rdtp->dyntick_holdoff == jiffies ? 'H' : '.',
2270                 timer_pending(tltp) ? tltp->expires - jiffies : -1);
2271 }
2272
2273 #else /* #ifdef CONFIG_RCU_FAST_NO_HZ */
2274
2275 static void print_cpu_stall_fast_no_hz(char *cp, int cpu)
2276 {
2277 }
2278
2279 #endif /* #else #ifdef CONFIG_RCU_FAST_NO_HZ */
2280
2281 /* Initiate the stall-info list. */
2282 static void print_cpu_stall_info_begin(void)
2283 {
2284         printk(KERN_CONT "\n");
2285 }
2286
2287 /*
2288  * Print out diagnostic information for the specified stalled CPU.
2289  *
2290  * If the specified CPU is aware of the current RCU grace period
2291  * (flavor specified by rsp), then print the number of scheduling
2292  * clock interrupts the CPU has taken during the time that it has
2293  * been aware.  Otherwise, print the number of RCU grace periods
2294  * that this CPU is ignorant of, for example, "1" if the CPU was
2295  * aware of the previous grace period.
2296  *
2297  * Also print out idle and (if CONFIG_RCU_FAST_NO_HZ) idle-entry info.
2298  */
2299 static void print_cpu_stall_info(struct rcu_state *rsp, int cpu)
2300 {
2301         char fast_no_hz[72];
2302         struct rcu_data *rdp = per_cpu_ptr(rsp->rda, cpu);
2303         struct rcu_dynticks *rdtp = rdp->dynticks;
2304         char *ticks_title;
2305         unsigned long ticks_value;
2306
2307         if (rsp->gpnum == rdp->gpnum) {
2308                 ticks_title = "ticks this GP";
2309                 ticks_value = rdp->ticks_this_gp;
2310         } else {
2311                 ticks_title = "GPs behind";
2312                 ticks_value = rsp->gpnum - rdp->gpnum;
2313         }
2314         print_cpu_stall_fast_no_hz(fast_no_hz, cpu);
2315         printk(KERN_ERR "\t%d: (%lu %s) idle=%03x/%llx/%d %s\n",
2316                cpu, ticks_value, ticks_title,
2317                atomic_read(&rdtp->dynticks) & 0xfff,
2318                rdtp->dynticks_nesting, rdtp->dynticks_nmi_nesting,
2319                fast_no_hz);
2320 }
2321
2322 /* Terminate the stall-info list. */
2323 static void print_cpu_stall_info_end(void)
2324 {
2325         printk(KERN_ERR "\t");
2326 }
2327
2328 /* Zero ->ticks_this_gp for all flavors of RCU. */
2329 static void zero_cpu_stall_ticks(struct rcu_data *rdp)
2330 {
2331         rdp->ticks_this_gp = 0;
2332 }
2333
2334 /* Increment ->ticks_this_gp for all flavors of RCU. */
2335 static void increment_cpu_stall_ticks(void)
2336 {
2337         __get_cpu_var(rcu_sched_data).ticks_this_gp++;
2338         __get_cpu_var(rcu_bh_data).ticks_this_gp++;
2339 #ifdef CONFIG_TREE_PREEMPT_RCU
2340         __get_cpu_var(rcu_preempt_data).ticks_this_gp++;
2341 #endif /* #ifdef CONFIG_TREE_PREEMPT_RCU */
2342 }
2343
2344 #else /* #ifdef CONFIG_RCU_CPU_STALL_INFO */
2345
2346 static void print_cpu_stall_info_begin(void)
2347 {
2348         printk(KERN_CONT " {");
2349 }
2350
2351 static void print_cpu_stall_info(struct rcu_state *rsp, int cpu)
2352 {
2353         printk(KERN_CONT " %d", cpu);
2354 }
2355
2356 static void print_cpu_stall_info_end(void)
2357 {
2358         printk(KERN_CONT "} ");
2359 }
2360
2361 static void zero_cpu_stall_ticks(struct rcu_data *rdp)
2362 {
2363 }
2364
2365 static void increment_cpu_stall_ticks(void)
2366 {
2367 }
2368
2369 #endif /* #else #ifdef CONFIG_RCU_CPU_STALL_INFO */