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 preemptable 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 #ifdef CONFIG_TREE_PREEMPT_RCU
  30
  31 struct rcu_state rcu_preempt_state = RCU_STATE_INITIALIZER(rcu_preempt_state);
  32 DEFINE_PER_CPU(struct rcu_data, rcu_preempt_data);
  33
  34 static int rcu_preempted_readers_exp(struct rcu_node *rnp);
  35
  36 /*
  37  * Tell them what RCU they are running.
  38  */
  39 static void __init rcu_bootup_announce(void)
  40 {
  41         printk(KERN_INFO
  42                "Experimental preemptable hierarchical RCU implementation.\n");
  43 }
  44
  45 /*
  46  * Return the number of RCU-preempt batches processed thus far
  47  * for debug and statistics.
  48  */
  49 long rcu_batches_completed_preempt(void)
  50 {
  51         return rcu_preempt_state.completed;
  52 }
  53 EXPORT_SYMBOL_GPL(rcu_batches_completed_preempt);
  54
  55 /*
  56  * Return the number of RCU batches processed thus far for debug & stats.
  57  */
  58 long rcu_batches_completed(void)
  59 {
  60         return rcu_batches_completed_preempt();
  61 }
  62 EXPORT_SYMBOL_GPL(rcu_batches_completed);
  63
  64 /*
  65  * Force a quiescent state for preemptible RCU.
  66  */
  67 void rcu_force_quiescent_state(void)
  68 {
  69         force_quiescent_state(&rcu_preempt_state, 0);
  70 }
  71 EXPORT_SYMBOL_GPL(rcu_force_quiescent_state);
  72
  73 /*
  74  * Record a preemptable-RCU quiescent state for the specified CPU.  Note
  75  * that this just means that the task currently running on the CPU is
  76  * not in a quiescent state.  There might be any number of tasks blocked
  77  * while in an RCU read-side critical section.
  78  */
  79 static void rcu_preempt_qs(int cpu)
  80 {
  81         struct rcu_data *rdp = &per_cpu(rcu_preempt_data, cpu);
  82         rdp->passed_quiesc_completed = rdp->gpnum - 1;
  83         barrier();
  84         rdp->passed_quiesc = 1;
  85 }
  86
  87 /*
  88  * We have entered the scheduler, and the current task might soon be
  89  * context-switched away from.  If this task is in an RCU read-side
  90  * critical section, we will no longer be able to rely on the CPU to
  91  * record that fact, so we enqueue the task on the appropriate entry
  92  * of the blocked_tasks[] array.  The task will dequeue itself when
  93  * it exits the outermost enclosing RCU read-side critical section.
  94  * Therefore, the current grace period cannot be permitted to complete
  95  * until the blocked_tasks[] entry indexed by the low-order bit of
  96  * rnp->gpnum empties.
  97  *
  98  * Caller must disable preemption.
  99  */
 100 static void rcu_preempt_note_context_switch(int cpu)
 101 {
 102         struct task_struct *t = current;
 103         unsigned long flags;
 104         int phase;
 105         struct rcu_data *rdp;
 106         struct rcu_node *rnp;
 107
 108         if (t->rcu_read_lock_nesting &&
 109             (t->rcu_read_unlock_special & RCU_READ_UNLOCK_BLOCKED) == 0) {
 110
 111                 /* Possibly blocking in an RCU read-side critical section. */
 112                 rdp = rcu_preempt_state.rda[cpu];
 113                 rnp = rdp->mynode;
 114                 spin_lock_irqsave(&rnp->lock, flags);
 115                 t->rcu_read_unlock_special |= RCU_READ_UNLOCK_BLOCKED;
 116                 t->rcu_blocked_node = rnp;
 117
 118                 /*
 119                  * If this CPU has already checked in, then this task
 120                  * will hold up the next grace period rather than the
 121                  * current grace period.  Queue the task accordingly.
 122                  * If the task is queued for the current grace period
 123                  * (i.e., this CPU has not yet passed through a quiescent
 124                  * state for the current grace period), then as long
 125                  * as that task remains queued, the current grace period
 126                  * cannot end.
 127                  *
 128                  * But first, note that the current CPU must still be
 129                  * on line!
 130                  */
 131                 WARN_ON_ONCE((rdp->grpmask & rnp->qsmaskinit) == 0);
 132                 WARN_ON_ONCE(!list_empty(&t->rcu_node_entry));
 133                 phase = (rnp->gpnum + !(rnp->qsmask & rdp->grpmask)) & 0x1;
 134                 list_add(&t->rcu_node_entry, &rnp->blocked_tasks[phase]);
 135                 spin_unlock_irqrestore(&rnp->lock, flags);
 136         }
 137
 138         /*
 139          * Either we were not in an RCU read-side critical section to
 140          * begin with, or we have now recorded that critical section
 141          * globally.  Either way, we can now note a quiescent state
 142          * for this CPU.  Again, if we were in an RCU read-side critical
 143          * section, and if that critical section was blocking the current
 144          * grace period, then the fact that the task has been enqueued
 145          * means that we continue to block the current grace period.
 146          */
 147         rcu_preempt_qs(cpu);
 148         local_irq_save(flags);
 149         t->rcu_read_unlock_special &= ~RCU_READ_UNLOCK_NEED_QS;
 150         local_irq_restore(flags);
 151 }
 152
 153 /*
 154  * Tree-preemptable RCU implementation for rcu_read_lock().
 155  * Just increment ->rcu_read_lock_nesting, shared state will be updated
 156  * if we block.
 157  */
 158 void __rcu_read_lock(void)
 159 {
 160         ACCESS_ONCE(current->rcu_read_lock_nesting)++;
 161         barrier();  /* needed if we ever invoke rcu_read_lock in rcutree.c */
 162 }
 163 EXPORT_SYMBOL_GPL(__rcu_read_lock);
 164
 165 /*
 166  * Check for preempted RCU readers blocking the current grace period
 167  * for the specified rcu_node structure.  If the caller needs a reliable
 168  * answer, it must hold the rcu_node's ->lock.
 169  */
 170 static int rcu_preempted_readers(struct rcu_node *rnp)
 171 {
 172         int phase = rnp->gpnum & 0x1;
 173
 174         return !list_empty(&rnp->blocked_tasks[phase]) ||
 175                !list_empty(&rnp->blocked_tasks[phase + 2]);
 176 }
 177
 178 /*
 179  * Record a quiescent state for all tasks that were previously queued
 180  * on the specified rcu_node structure and that were blocking the current
 181  * RCU grace period.  The caller must hold the specified rnp->lock with
 182  * irqs disabled, and this lock is released upon return, but irqs remain
 183  * disabled.
 184  */
 185 static void rcu_report_unblock_qs_rnp(struct rcu_node *rnp, unsigned long flags)
 186         __releases(rnp->lock)
 187 {
 188         unsigned long mask;
 189         struct rcu_node *rnp_p;
 190
 191         if (rnp->qsmask != 0 || rcu_preempted_readers(rnp)) {
 192                 spin_unlock_irqrestore(&rnp->lock, flags);
 193                 return;  /* Still need more quiescent states! */
 194         }
 195
 196         rnp_p = rnp->parent;
 197         if (rnp_p == NULL) {
 198                 /*
 199                  * Either there is only one rcu_node in the tree,
 200                  * or tasks were kicked up to root rcu_node due to
 201                  * CPUs going offline.
 202                  */
 203                 rcu_report_qs_rsp(&rcu_preempt_state, flags);
 204                 return;
 205         }
 206
 207         /* Report up the rest of the hierarchy. */
 208         mask = rnp->grpmask;
 209         spin_unlock(&rnp->lock);        /* irqs remain disabled. */
 210         spin_lock(&rnp_p->lock);        /* irqs already disabled. */
 211         rcu_report_qs_rnp(mask, &rcu_preempt_state, rnp_p, flags);
 212 }
 213
 214 /*
 215  * Handle special cases during rcu_read_unlock(), such as needing to
 216  * notify RCU core processing or task having blocked during the RCU
 217  * read-side critical section.
 218  */
 219 static void rcu_read_unlock_special(struct task_struct *t)
 220 {
 221         int empty;
 222         int empty_exp;
 223         unsigned long flags;
 224         struct rcu_node *rnp;
 225         int special;
 226
 227         /* NMI handlers cannot block and cannot safely manipulate state. */
 228         if (in_nmi())
 229                 return;
 230
 231         local_irq_save(flags);
 232
 233         /*
 234          * If RCU core is waiting for this CPU to exit critical section,
 235          * let it know that we have done so.
 236          */
 237         special = t->rcu_read_unlock_special;
 238         if (special & RCU_READ_UNLOCK_NEED_QS) {
 239                 t->rcu_read_unlock_special &= ~RCU_READ_UNLOCK_NEED_QS;
 240                 rcu_preempt_qs(smp_processor_id());
 241         }
 242
 243         /* Hardware IRQ handlers cannot block. */
 244         if (in_irq()) {
 245                 local_irq_restore(flags);
 246                 return;
 247         }
 248
 249         /* Clean up if blocked during RCU read-side critical section. */
 250         if (special & RCU_READ_UNLOCK_BLOCKED) {
 251                 t->rcu_read_unlock_special &= ~RCU_READ_UNLOCK_BLOCKED;
 252
 253                 /*
 254                  * Remove this task from the list it blocked on.  The
 255                  * task can migrate while we acquire the lock, but at
 256                  * most one time.  So at most two passes through loop.
 257                  */
 258                 for (;;) {
 259                         rnp = t->rcu_blocked_node;
 260                         spin_lock(&rnp->lock);  /* irqs already disabled. */
 261                         if (rnp == t->rcu_blocked_node)
 262                                 break;
 263                         spin_unlock(&rnp->lock);  /* irqs remain disabled. */
 264                 }
 265                 empty = !rcu_preempted_readers(rnp);
 266                 empty_exp = !rcu_preempted_readers_exp(rnp);
 267                 smp_mb(); /* ensure expedited fastpath sees end of RCU c-s. */
 268                 list_del_init(&t->rcu_node_entry);
 269                 t->rcu_blocked_node = NULL;
 270
 271                 /*
 272                  * If this was the last task on the current list, and if
 273                  * we aren't waiting on any CPUs, report the quiescent state.
 274                  * Note that rcu_report_unblock_qs_rnp() releases rnp->lock.
 275                  */
 276                 if (empty)
 277                         spin_unlock_irqrestore(&rnp->lock, flags);
 278                 else
 279                         rcu_report_unblock_qs_rnp(rnp, flags);
 280
 281                 /*
 282                  * If this was the last task on the expedited lists,
 283                  * then we need to report up the rcu_node hierarchy.
 284                  */
 285                 if (!empty_exp && !rcu_preempted_readers_exp(rnp))
 286                         rcu_report_exp_rnp(&rcu_preempt_state, rnp);
 287         } else {
 288                 local_irq_restore(flags);
 289         }
 290 }
 291
 292 /*
 293  * Tree-preemptable RCU implementation for rcu_read_unlock().
 294  * Decrement ->rcu_read_lock_nesting.  If the result is zero (outermost
 295  * rcu_read_unlock()) and ->rcu_read_unlock_special is non-zero, then
 296  * invoke rcu_read_unlock_special() to clean up after a context switch
 297  * in an RCU read-side critical section and other special cases.
 298  */
 299 void __rcu_read_unlock(void)
 300 {
 301         struct task_struct *t = current;
 302
 303         barrier();  /* needed if we ever invoke rcu_read_unlock in rcutree.c */
 304         if (--ACCESS_ONCE(t->rcu_read_lock_nesting) == 0 &&
 305             unlikely(ACCESS_ONCE(t->rcu_read_unlock_special)))
 306                 rcu_read_unlock_special(t);
 307 #ifdef CONFIG_PROVE_LOCKING
 308         WARN_ON_ONCE(ACCESS_ONCE(t->rcu_read_lock_nesting) < 0);
 309 #endif /* #ifdef CONFIG_PROVE_LOCKING */
 310 }
 311 EXPORT_SYMBOL_GPL(__rcu_read_unlock);
 312
 313 #ifdef CONFIG_RCU_CPU_STALL_DETECTOR
 314
 315 /*
 316  * Scan the current list of tasks blocked within RCU read-side critical
 317  * sections, printing out the tid of each.
 318  */
 319 static void rcu_print_task_stall(struct rcu_node *rnp)
 320 {
 321         unsigned long flags;
 322         struct list_head *lp;
 323         int phase;
 324         struct task_struct *t;
 325
 326         if (rcu_preempted_readers(rnp)) {
 327                 spin_lock_irqsave(&rnp->lock, flags);
 328                 phase = rnp->gpnum & 0x1;
 329                 lp = &rnp->blocked_tasks[phase];
 330                 list_for_each_entry(t, lp, rcu_node_entry)
 331                         printk(" P%d", t->pid);
 332                 spin_unlock_irqrestore(&rnp->lock, flags);
 333         }
 334 }
 335
 336 #endif /* #ifdef CONFIG_RCU_CPU_STALL_DETECTOR */
 337
 338 /*
 339  * Check that the list of blocked tasks for the newly completed grace
 340  * period is in fact empty.  It is a serious bug to complete a grace
 341  * period that still has RCU readers blocked!  This function must be
 342  * invoked -before- updating this rnp's ->gpnum, and the rnp's ->lock
 343  * must be held by the caller.
 344  */
 345 static void rcu_preempt_check_blocked_tasks(struct rcu_node *rnp)
 346 {
 347         WARN_ON_ONCE(rcu_preempted_readers(rnp));
 348         WARN_ON_ONCE(rnp->qsmask);
 349 }
 350
 351 #ifdef CONFIG_HOTPLUG_CPU
 352
 353 /*
 354  * Handle tasklist migration for case in which all CPUs covered by the
 355  * specified rcu_node have gone offline.  Move them up to the root
 356  * rcu_node.  The reason for not just moving them to the immediate
 357  * parent is to remove the need for rcu_read_unlock_special() to
 358  * make more than two attempts to acquire the target rcu_node's lock.
 359  * Returns true if there were tasks blocking the current RCU grace
 360  * period.
 361  *
 362  * Returns 1 if there was previously a task blocking the current grace
 363  * period on the specified rcu_node structure.
 364  *
 365  * The caller must hold rnp->lock with irqs disabled.
 366  */
 367 static int rcu_preempt_offline_tasks(struct rcu_state *rsp,
 368                                      struct rcu_node *rnp,
 369                                      struct rcu_data *rdp)
 370 {
 371         int i;
 372         struct list_head *lp;
 373         struct list_head *lp_root;
 374         int retval = 0;
 375         struct rcu_node *rnp_root = rcu_get_root(rsp);
 376         struct task_struct *tp;
 377
 378         if (rnp == rnp_root) {
 379                 WARN_ONCE(1, "Last CPU thought to be offlined?");
 380                 return 0;  /* Shouldn't happen: at least one CPU online. */
 381         }
 382         WARN_ON_ONCE(rnp != rdp->mynode &&
 383                      (!list_empty(&rnp->blocked_tasks[0]) ||
 384                       !list_empty(&rnp->blocked_tasks[1]) ||
 385                       !list_empty(&rnp->blocked_tasks[2]) ||
 386                       !list_empty(&rnp->blocked_tasks[3])));
 387
 388         /*
 389          * Move tasks up to root rcu_node.  Rely on the fact that the
 390          * root rcu_node can be at most one ahead of the rest of the
 391          * rcu_nodes in terms of gp_num value.  This fact allows us to
 392          * move the blocked_tasks[] array directly, element by element.
 393          */
 394         if (rcu_preempted_readers(rnp))
 395                 retval |= RCU_OFL_TASKS_NORM_GP;
 396         if (rcu_preempted_readers_exp(rnp))
 397                 retval |= RCU_OFL_TASKS_EXP_GP;
 398         for (i = 0; i < 4; i++) {
 399                 lp = &rnp->blocked_tasks[i];
 400                 lp_root = &rnp_root->blocked_tasks[i];
 401                 while (!list_empty(lp)) {
 402                         tp = list_entry(lp->next, typeof(*tp), rcu_node_entry);
 403                         spin_lock(&rnp_root->lock); /* irqs already disabled */
 404                         list_del(&tp->rcu_node_entry);
 405                         tp->rcu_blocked_node = rnp_root;
 406                         list_add(&tp->rcu_node_entry, lp_root);
 407                         spin_unlock(&rnp_root->lock); /* irqs remain disabled */
 408                 }
 409         }
 410         return retval;
 411 }
 412
 413 /*
 414  * Do CPU-offline processing for preemptable RCU.
 415  */
 416 static void rcu_preempt_offline_cpu(int cpu)
 417 {
 418         __rcu_offline_cpu(cpu, &rcu_preempt_state);
 419 }
 420
 421 #endif /* #ifdef CONFIG_HOTPLUG_CPU */
 422
 423 /*
 424  * Check for a quiescent state from the current CPU.  When a task blocks,
 425  * the task is recorded in the corresponding CPU's rcu_node structure,
 426  * which is checked elsewhere.
 427  *
 428  * Caller must disable hard irqs.
 429  */
 430 static void rcu_preempt_check_callbacks(int cpu)
 431 {
 432         struct task_struct *t = current;
 433
 434         if (t->rcu_read_lock_nesting == 0) {
 435                 t->rcu_read_unlock_special &= ~RCU_READ_UNLOCK_NEED_QS;
 436                 rcu_preempt_qs(cpu);
 437                 return;
 438         }
 439         if (per_cpu(rcu_preempt_data, cpu).qs_pending)
 440                 t->rcu_read_unlock_special |= RCU_READ_UNLOCK_NEED_QS;
 441 }
 442
 443 /*
 444  * Process callbacks for preemptable RCU.
 445  */
 446 static void rcu_preempt_process_callbacks(void)
 447 {
 448         __rcu_process_callbacks(&rcu_preempt_state,
 449                                 &__get_cpu_var(rcu_preempt_data));
 450 }
 451
 452 /*
 453  * Queue a preemptable-RCU callback for invocation after a grace period.
 454  */
 455 void call_rcu(struct rcu_head *head, void (*func)(struct rcu_head *rcu))
 456 {
 457         __call_rcu(head, func, &rcu_preempt_state);
 458 }
 459 EXPORT_SYMBOL_GPL(call_rcu);
 460
 461 /**
 462  * synchronize_rcu - wait until a grace period has elapsed.
 463  *
 464  * Control will return to the caller some time after a full grace
 465  * period has elapsed, in other words after all currently executing RCU
 466  * read-side critical sections have completed.  RCU read-side critical
 467  * sections are delimited by rcu_read_lock() and rcu_read_unlock(),
 468  * and may be nested.
 469  */
 470 void synchronize_rcu(void)
 471 {
 472         struct rcu_synchronize rcu;
 473
 474         if (!rcu_scheduler_active)
 475                 return;
 476
 477         init_completion(&rcu.completion);
 478         /* Will wake me after RCU finished. */
 479         call_rcu(&rcu.head, wakeme_after_rcu);
 480         /* Wait for it. */
 481         wait_for_completion(&rcu.completion);
 482 }
 483 EXPORT_SYMBOL_GPL(synchronize_rcu);
 484
 485 static DECLARE_WAIT_QUEUE_HEAD(sync_rcu_preempt_exp_wq);
 486 static long sync_rcu_preempt_exp_count;
 487 static DEFINE_MUTEX(sync_rcu_preempt_exp_mutex);
 488
 489 /*
 490  * Return non-zero if there are any tasks in RCU read-side critical
 491  * sections blocking the current preemptible-RCU expedited grace period.
 492  * If there is no preemptible-RCU expedited grace period currently in
 493  * progress, returns zero unconditionally.
 494  */
 495 static int rcu_preempted_readers_exp(struct rcu_node *rnp)
 496 {
 497         return !list_empty(&rnp->blocked_tasks[2]) ||
 498                !list_empty(&rnp->blocked_tasks[3]);
 499 }
 500
 501 /*
 502  * return non-zero if there is no RCU expedited grace period in progress
 503  * for the specified rcu_node structure, in other words, if all CPUs and
 504  * tasks covered by the specified rcu_node structure have done their bit
 505  * for the current expedited grace period.  Works only for preemptible
 506  * RCU -- other RCU implementation use other means.
 507  *
 508  * Caller must hold sync_rcu_preempt_exp_mutex.
 509  */
 510 static int sync_rcu_preempt_exp_done(struct rcu_node *rnp)
 511 {
 512         return !rcu_preempted_readers_exp(rnp) &&
 513                ACCESS_ONCE(rnp->expmask) == 0;
 514 }
 515
 516 /*
 517  * Report the exit from RCU read-side critical section for the last task
 518  * that queued itself during or before the current expedited preemptible-RCU
 519  * grace period.  This event is reported either to the rcu_node structure on
 520  * which the task was queued or to one of that rcu_node structure's ancestors,
 521  * recursively up the tree.  (Calm down, calm down, we do the recursion
 522  * iteratively!)
 523  *
 524  * Caller must hold sync_rcu_preempt_exp_mutex.
 525  */
 526 static void rcu_report_exp_rnp(struct rcu_state *rsp, struct rcu_node *rnp)
 527 {
 528         unsigned long flags;
 529         unsigned long mask;
 530
 531         spin_lock_irqsave(&rnp->lock, flags);
 532         for (;;) {
 533                 if (!sync_rcu_preempt_exp_done(rnp))
 534                         break;
 535                 if (rnp->parent == NULL) {
 536                         wake_up(&sync_rcu_preempt_exp_wq);
 537                         break;
 538                 }
 539                 mask = rnp->grpmask;
 540                 spin_unlock(&rnp->lock); /* irqs remain disabled */
 541                 rnp = rnp->parent;
 542                 spin_lock(&rnp->lock); /* irqs already disabled */
 543                 rnp->expmask &= ~mask;
 544         }
 545         spin_unlock_irqrestore(&rnp->lock, flags);
 546 }
 547
 548 /*
 549  * Snapshot the tasks blocking the newly started preemptible-RCU expedited
 550  * grace period for the specified rcu_node structure.  If there are no such
 551  * tasks, report it up the rcu_node hierarchy.
 552  *
 553  * Caller must hold sync_rcu_preempt_exp_mutex and rsp->onofflock.
 554  */
 555 static void
 556 sync_rcu_preempt_exp_init(struct rcu_state *rsp, struct rcu_node *rnp)
 557 {
 558         int must_wait;
 559
 560         spin_lock(&rnp->lock); /* irqs already disabled */
 561         list_splice_init(&rnp->blocked_tasks[0], &rnp->blocked_tasks[2]);
 562         list_splice_init(&rnp->blocked_tasks[1], &rnp->blocked_tasks[3]);
 563         must_wait = rcu_preempted_readers_exp(rnp);
 564         spin_unlock(&rnp->lock); /* irqs remain disabled */
 565         if (!must_wait)
 566                 rcu_report_exp_rnp(rsp, rnp);
 567 }
 568
 569 /*
 570  * Wait for an rcu-preempt grace period, but expedite it.  The basic idea
 571  * is to invoke synchronize_sched_expedited() to push all the tasks to
 572  * the ->blocked_tasks[] lists, move all entries from the first set of
 573  * ->blocked_tasks[] lists to the second set, and finally wait for this
 574  * second set to drain.
 575  */
 576 void synchronize_rcu_expedited(void)
 577 {
 578         unsigned long flags;
 579         struct rcu_node *rnp;
 580         struct rcu_state *rsp = &rcu_preempt_state;
 581         long snap;
 582         int trycount = 0;
 583
 584         smp_mb(); /* Caller's modifications seen first by other CPUs. */
 585         snap = ACCESS_ONCE(sync_rcu_preempt_exp_count) + 1;
 586         smp_mb(); /* Above access cannot bleed into critical section. */
 587
 588         /*
 589          * Acquire lock, falling back to synchronize_rcu() if too many
 590          * lock-acquisition failures.  Of course, if someone does the
 591          * expedited grace period for us, just leave.
 592          */
 593         while (!mutex_trylock(&sync_rcu_preempt_exp_mutex)) {
 594                 if (trycount++ < 10)
 595                         udelay(trycount * num_online_cpus());
 596                 else {
 597                         synchronize_rcu();
 598                         return;
 599                 }
 600                 if ((ACCESS_ONCE(sync_rcu_preempt_exp_count) - snap) > 0)
 601                         goto mb_ret; /* Others did our work for us. */
 602         }
 603         if ((ACCESS_ONCE(sync_rcu_preempt_exp_count) - snap) > 0)
 604                 goto unlock_mb_ret; /* Others did our work for us. */
 605
 606         /* force all RCU readers onto blocked_tasks[]. */
 607         synchronize_sched_expedited();
 608
 609         spin_lock_irqsave(&rsp->onofflock, flags);
 610
 611         /* Initialize ->expmask for all non-leaf rcu_node structures. */
 612         rcu_for_each_nonleaf_node_breadth_first(rsp, rnp) {
 613                 spin_lock(&rnp->lock); /* irqs already disabled. */
 614                 rnp->expmask = rnp->qsmaskinit;
 615                 spin_unlock(&rnp->lock); /* irqs remain disabled. */
 616         }
 617
 618         /* Snapshot current state of ->blocked_tasks[] lists. */
 619         rcu_for_each_leaf_node(rsp, rnp)
 620                 sync_rcu_preempt_exp_init(rsp, rnp);
 621         if (NUM_RCU_NODES > 1)
 622                 sync_rcu_preempt_exp_init(rsp, rcu_get_root(rsp));
 623
 624         spin_unlock_irqrestore(&rsp->onofflock, flags);
 625
 626         /* Wait for snapshotted ->blocked_tasks[] lists to drain. */
 627         rnp = rcu_get_root(rsp);
 628         wait_event(sync_rcu_preempt_exp_wq,
 629                    sync_rcu_preempt_exp_done(rnp));
 630
 631         /* Clean up and exit. */
 632         smp_mb(); /* ensure expedited GP seen before counter increment. */
 633         ACCESS_ONCE(sync_rcu_preempt_exp_count)++;
 634 unlock_mb_ret:
 635         mutex_unlock(&sync_rcu_preempt_exp_mutex);
 636 mb_ret:
 637         smp_mb(); /* ensure subsequent action seen after grace period. */
 638 }
 639 EXPORT_SYMBOL_GPL(synchronize_rcu_expedited);
 640
 641 /*
 642  * Check to see if there is any immediate preemptable-RCU-related work
 643  * to be done.
 644  */
 645 static int rcu_preempt_pending(int cpu)
 646 {
 647         return __rcu_pending(&rcu_preempt_state,
 648                              &per_cpu(rcu_preempt_data, cpu));
 649 }
 650
 651 /*
 652  * Does preemptable RCU need the CPU to stay out of dynticks mode?
 653  */
 654 static int rcu_preempt_needs_cpu(int cpu)
 655 {
 656         return !!per_cpu(rcu_preempt_data, cpu).nxtlist;
 657 }
 658
 659 /**
 660  * rcu_barrier - Wait until all in-flight call_rcu() callbacks complete.
 661  */
 662 void rcu_barrier(void)
 663 {
 664         _rcu_barrier(&rcu_preempt_state, call_rcu);
 665 }
 666 EXPORT_SYMBOL_GPL(rcu_barrier);
 667
 668 /*
 669  * Initialize preemptable RCU's per-CPU data.
 670  */
 671 static void __cpuinit rcu_preempt_init_percpu_data(int cpu)
 672 {
 673         rcu_init_percpu_data(cpu, &rcu_preempt_state, 1);
 674 }
 675
 676 /*
 677  * Move preemptable RCU's callbacks to ->orphan_cbs_list.
 678  */
 679 static void rcu_preempt_send_cbs_to_orphanage(void)
 680 {
 681         rcu_send_cbs_to_orphanage(&rcu_preempt_state);
 682 }
 683
 684 /*
 685  * Initialize preemptable RCU's state structures.
 686  */
 687 static void __init __rcu_init_preempt(void)
 688 {
 689         RCU_INIT_FLAVOR(&rcu_preempt_state, rcu_preempt_data);
 690 }
 691
 692 /*
 693  * Check for a task exiting while in a preemptable-RCU read-side
 694  * critical section, clean up if so.  No need to issue warnings,
 695  * as debug_check_no_locks_held() already does this if lockdep
 696  * is enabled.
 697  */
 698 void exit_rcu(void)
 699 {
 700         struct task_struct *t = current;
 701
 702         if (t->rcu_read_lock_nesting == 0)
 703                 return;
 704         t->rcu_read_lock_nesting = 1;
 705         rcu_read_unlock();
 706 }
 707
 708 #else /* #ifdef CONFIG_TREE_PREEMPT_RCU */
 709
 710 /*
 711  * Tell them what RCU they are running.
 712  */
 713 static void __init rcu_bootup_announce(void)
 714 {
 715         printk(KERN_INFO "Hierarchical RCU implementation.\n");
 716 }
 717
 718 /*
 719  * Return the number of RCU batches processed thus far for debug & stats.
 720  */
 721 long rcu_batches_completed(void)
 722 {
 723         return rcu_batches_completed_sched();
 724 }
 725 EXPORT_SYMBOL_GPL(rcu_batches_completed);
 726
 727 /*
 728  * Force a quiescent state for RCU, which, because there is no preemptible
 729  * RCU, becomes the same as rcu-sched.
 730  */
 731 void rcu_force_quiescent_state(void)
 732 {
 733         rcu_sched_force_quiescent_state();
 734 }
 735 EXPORT_SYMBOL_GPL(rcu_force_quiescent_state);
 736
 737 /*
 738  * Because preemptable RCU does not exist, we never have to check for
 739  * CPUs being in quiescent states.
 740  */
 741 static void rcu_preempt_note_context_switch(int cpu)
 742 {
 743 }
 744
 745 /*
 746  * Because preemptable RCU does not exist, there are never any preempted
 747  * RCU readers.
 748  */
 749 static int rcu_preempted_readers(struct rcu_node *rnp)
 750 {
 751         return 0;
 752 }
 753
 754 #ifdef CONFIG_HOTPLUG_CPU
 755
 756 /* Because preemptible RCU does not exist, no quieting of tasks. */
 757 static void rcu_report_unblock_qs_rnp(struct rcu_node *rnp, unsigned long flags)
 758 {
 759         spin_unlock_irqrestore(&rnp->lock, flags);
 760 }
 761
 762 #endif /* #ifdef CONFIG_HOTPLUG_CPU */
 763
 764 #ifdef CONFIG_RCU_CPU_STALL_DETECTOR
 765
 766 /*
 767  * Because preemptable RCU does not exist, we never have to check for
 768  * tasks blocked within RCU read-side critical sections.
 769  */
 770 static void rcu_print_task_stall(struct rcu_node *rnp)
 771 {
 772 }
 773
 774 #endif /* #ifdef CONFIG_RCU_CPU_STALL_DETECTOR */
 775
 776 /*
 777  * Because there is no preemptable RCU, there can be no readers blocked,
 778  * so there is no need to check for blocked tasks.  So check only for
 779  * bogus qsmask values.
 780  */
 781 static void rcu_preempt_check_blocked_tasks(struct rcu_node *rnp)
 782 {
 783         WARN_ON_ONCE(rnp->qsmask);
 784 }
 785
 786 #ifdef CONFIG_HOTPLUG_CPU
 787
 788 /*
 789  * Because preemptable RCU does not exist, it never needs to migrate
 790  * tasks that were blocked within RCU read-side critical sections, and
 791  * such non-existent tasks cannot possibly have been blocking the current
 792  * grace period.
 793  */
 794 static int rcu_preempt_offline_tasks(struct rcu_state *rsp,
 795                                      struct rcu_node *rnp,
 796                                      struct rcu_data *rdp)
 797 {
 798         return 0;
 799 }
 800
 801 /*
 802  * Because preemptable RCU does not exist, it never needs CPU-offline
 803  * processing.
 804  */
 805 static void rcu_preempt_offline_cpu(int cpu)
 806 {
 807 }
 808
 809 #endif /* #ifdef CONFIG_HOTPLUG_CPU */
 810
 811 /*
 812  * Because preemptable RCU does not exist, it never has any callbacks
 813  * to check.
 814  */
 815 static void rcu_preempt_check_callbacks(int cpu)
 816 {
 817 }
 818
 819 /*
 820  * Because preemptable RCU does not exist, it never has any callbacks
 821  * to process.
 822  */
 823 static void rcu_preempt_process_callbacks(void)
 824 {
 825 }
 826
 827 /*
 828  * In classic RCU, call_rcu() is just call_rcu_sched().
 829  */
 830 void call_rcu(struct rcu_head *head, void (*func)(struct rcu_head *rcu))
 831 {
 832         call_rcu_sched(head, func);
 833 }
 834 EXPORT_SYMBOL_GPL(call_rcu);
 835
 836 /*
 837  * Wait for an rcu-preempt grace period, but make it happen quickly.
 838  * But because preemptable RCU does not exist, map to rcu-sched.
 839  */
 840 void synchronize_rcu_expedited(void)
 841 {
 842         synchronize_sched_expedited();
 843 }
 844 EXPORT_SYMBOL_GPL(synchronize_rcu_expedited);
 845
 846 #ifdef CONFIG_HOTPLUG_CPU
 847
 848 /*
 849  * Because preemptable RCU does not exist, there is never any need to
 850  * report on tasks preempted in RCU read-side critical sections during
 851  * expedited RCU grace periods.
 852  */
 853 static void rcu_report_exp_rnp(struct rcu_state *rsp, struct rcu_node *rnp)
 854 {
 855         return;
 856 }
 857
 858 #endif /* #ifdef CONFIG_HOTPLUG_CPU */
 859
 860 /*
 861  * Because preemptable RCU does not exist, it never has any work to do.
 862  */
 863 static int rcu_preempt_pending(int cpu)
 864 {
 865         return 0;
 866 }
 867
 868 /*
 869  * Because preemptable RCU does not exist, it never needs any CPU.
 870  */
 871 static int rcu_preempt_needs_cpu(int cpu)
 872 {
 873         return 0;
 874 }
 875
 876 /*
 877  * Because preemptable RCU does not exist, rcu_barrier() is just
 878  * another name for rcu_barrier_sched().
 879  */
 880 void rcu_barrier(void)
 881 {
 882         rcu_barrier_sched();
 883 }
 884 EXPORT_SYMBOL_GPL(rcu_barrier);
 885
 886 /*
 887  * Because preemptable RCU does not exist, there is no per-CPU
 888  * data to initialize.
 889  */
 890 static void __cpuinit rcu_preempt_init_percpu_data(int cpu)
 891 {
 892 }
 893
 894 /*
 895  * Because there is no preemptable RCU, there are no callbacks to move.
 896  */
 897 static void rcu_preempt_send_cbs_to_orphanage(void)
 898 {
 899 }
 900
 901 /*
 902  * Because preemptable RCU does not exist, it need not be initialized.
 903  */
 904 static void __init __rcu_init_preempt(void)
 905 {
 906 }
 907
 908 #endif /* #else #ifdef CONFIG_TREE_PREEMPT_RCU */