kernel/rcutiny.c

   1 /*
   2  * Read-Copy Update mechanism for mutual exclusion, the Bloatwatch edition.
   3  *
   4  * This program is free software; you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation; either version 2 of the License, or
   7  * (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  17  *
  18  * Copyright IBM Corporation, 2008
  19  *
  20  * Author: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
  21  *
  22  * For detailed explanation of Read-Copy Update mechanism see -
  23  *              Documentation/RCU
  24  */
  25 #include <linux/moduleparam.h>
  26 #include <linux/completion.h>
  27 #include <linux/interrupt.h>
  28 #include <linux/notifier.h>
  29 #include <linux/rcupdate.h>
  30 #include <linux/kernel.h>
  31 #include <linux/module.h>
  32 #include <linux/mutex.h>
  33 #include <linux/sched.h>
  34 #include <linux/types.h>
  35 #include <linux/init.h>
  36 #include <linux/time.h>
  37 #include <linux/cpu.h>
  38
  39 /* Global control variables for rcupdate callback mechanism. */
  40 struct rcu_ctrlblk {
  41         struct rcu_head *rcucblist;     /* List of pending callbacks (CBs). */
  42         struct rcu_head **donetail;     /* ->next pointer of last "done" CB. */
  43         struct rcu_head **curtail;      /* ->next pointer of last CB. */
  44 };
  45
  46 /* Definition for rcupdate control block. */
  47 static struct rcu_ctrlblk rcu_sched_ctrlblk = {
  48         .donetail       = &rcu_sched_ctrlblk.rcucblist,
  49         .curtail        = &rcu_sched_ctrlblk.rcucblist,
  50 };
  51
  52 static struct rcu_ctrlblk rcu_bh_ctrlblk = {
  53         .donetail       = &rcu_bh_ctrlblk.rcucblist,
  54         .curtail        = &rcu_bh_ctrlblk.rcucblist,
  55 };
  56
  57 #ifdef CONFIG_DEBUG_LOCK_ALLOC
  58 int rcu_scheduler_active __read_mostly;
  59 EXPORT_SYMBOL_GPL(rcu_scheduler_active);
  60 #endif /* #ifdef CONFIG_DEBUG_LOCK_ALLOC */
  61
  62 /* Controls for rcu_cbs() kthread, replacing RCU_SOFTIRQ used previously. */
  63 static struct task_struct *rcu_cbs_task;
  64 static DECLARE_WAIT_QUEUE_HEAD(rcu_cbs_wq);
  65 static unsigned long have_rcu_cbs;
  66 static void invoke_rcu_cbs(void);
  67
  68 /* Forward declarations for rcutiny_plugin.h. */
  69 static void rcu_process_callbacks(struct rcu_ctrlblk *rcp);
  70 static int rcu_cbs(void *arg);
  71 static void __call_rcu(struct rcu_head *head,
  72                        void (*func)(struct rcu_head *rcu),
  73                        struct rcu_ctrlblk *rcp);
  74
  75 #include "rcutiny_plugin.h"
  76
  77 #ifdef CONFIG_NO_HZ
  78
  79 static long rcu_dynticks_nesting = 1;
  80
  81 /*
  82  * Enter dynticks-idle mode, which is an extended quiescent state
  83  * if we have fully entered that mode (i.e., if the new value of
  84  * dynticks_nesting is zero).
  85  */
  86 void rcu_enter_nohz(void)
  87 {
  88         if (--rcu_dynticks_nesting == 0)
  89                 rcu_sched_qs(0); /* implies rcu_bh_qsctr_inc(0) */
  90 }
  91
  92 /*
  93  * Exit dynticks-idle mode, so that we are no longer in an extended
  94  * quiescent state.
  95  */
  96 void rcu_exit_nohz(void)
  97 {
  98         rcu_dynticks_nesting++;
  99 }
 100
 101 #endif /* #ifdef CONFIG_NO_HZ */
 102
 103 /*
 104  * Helper function for rcu_qsctr_inc() and rcu_bh_qsctr_inc().
 105  * Also disable irqs to avoid confusion due to interrupt handlers
 106  * invoking call_rcu().
 107  */
 108 static int rcu_qsctr_help(struct rcu_ctrlblk *rcp)
 109 {
 110         unsigned long flags;
 111
 112         local_irq_save(flags);
 113         if (rcp->rcucblist != NULL &&
 114             rcp->donetail != rcp->curtail) {
 115                 rcp->donetail = rcp->curtail;
 116                 local_irq_restore(flags);
 117                 return 1;
 118         }
 119         local_irq_restore(flags);
 120
 121         return 0;
 122 }
 123
 124 /*
 125  * Record an rcu quiescent state.  And an rcu_bh quiescent state while we
 126  * are at it, given that any rcu quiescent state is also an rcu_bh
 127  * quiescent state.  Use "+" instead of "||" to defeat short circuiting.
 128  */
 129 void rcu_sched_qs(int cpu)
 130 {
 131         if (rcu_qsctr_help(&rcu_sched_ctrlblk) +
 132             rcu_qsctr_help(&rcu_bh_ctrlblk))
 133                 invoke_rcu_cbs();
 134 }
 135
 136 /*
 137  * Record an rcu_bh quiescent state.
 138  */
 139 void rcu_bh_qs(int cpu)
 140 {
 141         if (rcu_qsctr_help(&rcu_bh_ctrlblk))
 142                 invoke_rcu_cbs();
 143 }
 144
 145 /*
 146  * Check to see if the scheduling-clock interrupt came from an extended
 147  * quiescent state, and, if so, tell RCU about it.
 148  */
 149 void rcu_check_callbacks(int cpu, int user)
 150 {
 151         if (user ||
 152             (idle_cpu(cpu) &&
 153              !in_softirq() &&
 154              hardirq_count() <= (1 << HARDIRQ_SHIFT)))
 155                 rcu_sched_qs(cpu);
 156         else if (!in_softirq())
 157                 rcu_bh_qs(cpu);
 158         rcu_preempt_check_callbacks();
 159 }
 160
 161 /*
 162  * Invoke the RCU callbacks on the specified rcu_ctrlkblk structure
 163  * whose grace period has elapsed.
 164  */
 165 static void rcu_process_callbacks(struct rcu_ctrlblk *rcp)
 166 {
 167         struct rcu_head *next, *list;
 168         unsigned long flags;
 169
 170         /* If no RCU callbacks ready to invoke, just return. */
 171         if (&rcp->rcucblist == rcp->donetail)
 172                 return;
 173
 174         /* Move the ready-to-invoke callbacks to a local list. */
 175         local_irq_save(flags);
 176         list = rcp->rcucblist;
 177         rcp->rcucblist = *rcp->donetail;
 178         *rcp->donetail = NULL;
 179         if (rcp->curtail == rcp->donetail)
 180                 rcp->curtail = &rcp->rcucblist;
 181         rcu_preempt_remove_callbacks(rcp);
 182         rcp->donetail = &rcp->rcucblist;
 183         local_irq_restore(flags);
 184
 185         /* Invoke the callbacks on the local list. */
 186         while (list) {
 187                 next = list->next;
 188                 prefetch(next);
 189                 debug_rcu_head_unqueue(list);
 190                 local_bh_disable();
 191                 list->func(list);
 192                 local_bh_enable();
 193                 list = next;
 194         }
 195 }
 196
 197 /*
 198  * This kthread invokes RCU callbacks whose grace periods have
 199  * elapsed.  It is awakened as needed, and takes the place of the
 200  * RCU_SOFTIRQ that was used previously for this purpose.
 201  * This is a kthread, but it is never stopped, at least not until
 202  * the system goes down.
 203  */
 204 static int rcu_cbs(void *arg)
 205 {
 206         unsigned long work;
 207         unsigned long flags;
 208
 209         for (;;) {
 210                 wait_event(rcu_cbs_wq, have_rcu_cbs != 0);
 211                 local_irq_save(flags);
 212                 work = have_rcu_cbs;
 213                 have_rcu_cbs = 0;
 214                 local_irq_restore(flags);
 215                 if (work) {
 216                         rcu_process_callbacks(&rcu_sched_ctrlblk);
 217                         rcu_process_callbacks(&rcu_bh_ctrlblk);
 218                         rcu_preempt_process_callbacks();
 219                 }
 220         }
 221
 222         return 0;  /* Not reached, but needed to shut gcc up. */
 223 }
 224
 225 /*
 226  * Wake up rcu_cbs() to process callbacks now eligible for invocation.
 227  */
 228 static void invoke_rcu_cbs(void)
 229 {
 230         unsigned long flags;
 231
 232         local_irq_save(flags);
 233         have_rcu_cbs = 1;
 234         wake_up(&rcu_cbs_wq);
 235         local_irq_restore(flags);
 236 }
 237
 238 /*
 239  * Wait for a grace period to elapse.  But it is illegal to invoke
 240  * synchronize_sched() from within an RCU read-side critical section.
 241  * Therefore, any legal call to synchronize_sched() is a quiescent
 242  * state, and so on a UP system, synchronize_sched() need do nothing.
 243  * Ditto for synchronize_rcu_bh().  (But Lai Jiangshan points out the
 244  * benefits of doing might_sleep() to reduce latency.)
 245  *
 246  * Cool, huh?  (Due to Josh Triplett.)
 247  *
 248  * But we want to make this a static inline later.  The cond_resched()
 249  * currently makes this problematic.
 250  */
 251 void synchronize_sched(void)
 252 {
 253         cond_resched();
 254 }
 255 EXPORT_SYMBOL_GPL(synchronize_sched);
 256
 257 /*
 258  * Helper function for call_rcu() and call_rcu_bh().
 259  */
 260 static void __call_rcu(struct rcu_head *head,
 261                        void (*func)(struct rcu_head *rcu),
 262                        struct rcu_ctrlblk *rcp)
 263 {
 264         unsigned long flags;
 265
 266         debug_rcu_head_queue(head);
 267         head->func = func;
 268         head->next = NULL;
 269
 270         local_irq_save(flags);
 271         *rcp->curtail = head;
 272         rcp->curtail = &head->next;
 273         local_irq_restore(flags);
 274 }
 275
 276 /*
 277  * Post an RCU callback to be invoked after the end of an RCU-sched grace
 278  * period.  But since we have but one CPU, that would be after any
 279  * quiescent state.
 280  */
 281 void call_rcu_sched(struct rcu_head *head, void (*func)(struct rcu_head *rcu))
 282 {
 283         __call_rcu(head, func, &rcu_sched_ctrlblk);
 284 }
 285 EXPORT_SYMBOL_GPL(call_rcu_sched);
 286
 287 /*
 288  * Post an RCU bottom-half callback to be invoked after any subsequent
 289  * quiescent state.
 290  */
 291 void call_rcu_bh(struct rcu_head *head, void (*func)(struct rcu_head *rcu))
 292 {
 293         __call_rcu(head, func, &rcu_bh_ctrlblk);
 294 }
 295 EXPORT_SYMBOL_GPL(call_rcu_bh);
 296
 297 void rcu_barrier_bh(void)
 298 {
 299         struct rcu_synchronize rcu;
 300
 301         init_rcu_head_on_stack(&rcu.head);
 302         init_completion(&rcu.completion);
 303         /* Will wake me after RCU finished. */
 304         call_rcu_bh(&rcu.head, wakeme_after_rcu);
 305         /* Wait for it. */
 306         wait_for_completion(&rcu.completion);
 307         destroy_rcu_head_on_stack(&rcu.head);
 308 }
 309 EXPORT_SYMBOL_GPL(rcu_barrier_bh);
 310
 311 void rcu_barrier_sched(void)
 312 {
 313         struct rcu_synchronize rcu;
 314
 315         init_rcu_head_on_stack(&rcu.head);
 316         init_completion(&rcu.completion);
 317         /* Will wake me after RCU finished. */
 318         call_rcu_sched(&rcu.head, wakeme_after_rcu);
 319         /* Wait for it. */
 320         wait_for_completion(&rcu.completion);
 321         destroy_rcu_head_on_stack(&rcu.head);
 322 }
 323 EXPORT_SYMBOL_GPL(rcu_barrier_sched);
 324
 325 /*
 326  * Spawn the kthread that invokes RCU callbacks.
 327  */
 328 static int __init rcu_spawn_kthreads(void)
 329 {
 330         rcu_cbs_task = kthread_run(rcu_cbs, NULL, "rcu_cbs");
 331         return 0;
 332 }
 333 early_initcall(rcu_spawn_kthreads);