kernel/rcutiny_plugin.h

   1 /*
   2  * Read-Copy Update mechanism for mutual exclusion, the Bloatwatch edition
   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 (c) 2010 Linaro
  21  *
  22  * Author: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
  23  */
  24
  25 #include <linux/kthread.h>
  26 #include <linux/debugfs.h>
  27 #include <linux/seq_file.h>
  28
  29 #ifdef CONFIG_RCU_TRACE
  30 #define RCU_TRACE(stmt) stmt
  31 #else /* #ifdef CONFIG_RCU_TRACE */
  32 #define RCU_TRACE(stmt)
  33 #endif /* #else #ifdef CONFIG_RCU_TRACE */
  34
  35 /* Global control variables for rcupdate callback mechanism. */
  36 struct rcu_ctrlblk {
  37         struct rcu_head *rcucblist;     /* List of pending callbacks (CBs). */
  38         struct rcu_head **donetail;     /* ->next pointer of last "done" CB. */
  39         struct rcu_head **curtail;      /* ->next pointer of last CB. */
  40         RCU_TRACE(long qlen);           /* Number of pending CBs. */
  41 };
  42
  43 /* Definition for rcupdate control block. */
  44 static struct rcu_ctrlblk rcu_sched_ctrlblk = {
  45         .donetail       = &rcu_sched_ctrlblk.rcucblist,
  46         .curtail        = &rcu_sched_ctrlblk.rcucblist,
  47 };
  48
  49 static struct rcu_ctrlblk rcu_bh_ctrlblk = {
  50         .donetail       = &rcu_bh_ctrlblk.rcucblist,
  51         .curtail        = &rcu_bh_ctrlblk.rcucblist,
  52 };
  53
  54 #ifdef CONFIG_DEBUG_LOCK_ALLOC
  55 int rcu_scheduler_active __read_mostly;
  56 EXPORT_SYMBOL_GPL(rcu_scheduler_active);
  57 #endif /* #ifdef CONFIG_DEBUG_LOCK_ALLOC */
  58
  59 #ifdef CONFIG_TINY_PREEMPT_RCU
  60
  61 #include <linux/delay.h>
  62
  63 /* Global control variables for preemptible RCU. */
  64 struct rcu_preempt_ctrlblk {
  65         struct rcu_ctrlblk rcb; /* curtail: ->next ptr of last CB for GP. */
  66         struct rcu_head **nexttail;
  67                                 /* Tasks blocked in a preemptible RCU */
  68                                 /*  read-side critical section while an */
  69                                 /*  preemptible-RCU grace period is in */
  70                                 /*  progress must wait for a later grace */
  71                                 /*  period.  This pointer points to the */
  72                                 /*  ->next pointer of the last task that */
  73                                 /*  must wait for a later grace period, or */
  74                                 /*  to &->rcb.rcucblist if there is no */
  75                                 /*  such task. */
  76         struct list_head blkd_tasks;
  77                                 /* Tasks blocked in RCU read-side critical */
  78                                 /*  section.  Tasks are placed at the head */
  79                                 /*  of this list and age towards the tail. */
  80         struct list_head *gp_tasks;
  81                                 /* Pointer to the first task blocking the */
  82                                 /*  current grace period, or NULL if there */
  83                                 /*  is no such task. */
  84         struct list_head *exp_tasks;
  85                                 /* Pointer to first task blocking the */
  86                                 /*  current expedited grace period, or NULL */
  87                                 /*  if there is no such task.  If there */
  88                                 /*  is no current expedited grace period, */
  89                                 /*  then there cannot be any such task. */
  90 #ifdef CONFIG_RCU_BOOST
  91         struct list_head *boost_tasks;
  92                                 /* Pointer to first task that needs to be */
  93                                 /*  priority-boosted, or NULL if no priority */
  94                                 /*  boosting is needed.  If there is no */
  95                                 /*  current or expedited grace period, there */
  96                                 /*  can be no such task. */
  97 #endif /* #ifdef CONFIG_RCU_BOOST */
  98         u8 gpnum;               /* Current grace period. */
  99         u8 gpcpu;               /* Last grace period blocked by the CPU. */
 100         u8 completed;           /* Last grace period completed. */
 101                                 /*  If all three are equal, RCU is idle. */
 102 #ifdef CONFIG_RCU_BOOST
 103         unsigned long boost_time; /* When to start boosting (jiffies) */
 104 #endif /* #ifdef CONFIG_RCU_BOOST */
 105 #ifdef CONFIG_RCU_TRACE
 106         unsigned long n_grace_periods;
 107 #ifdef CONFIG_RCU_BOOST
 108         unsigned long n_tasks_boosted;
 109         unsigned long n_exp_boosts;
 110         unsigned long n_normal_boosts;
 111         unsigned long n_normal_balk_blkd_tasks;
 112         unsigned long n_normal_balk_gp_tasks;
 113         unsigned long n_normal_balk_boost_tasks;
 114         unsigned long n_normal_balk_notyet;
 115         unsigned long n_normal_balk_nos;
 116         unsigned long n_exp_balk_blkd_tasks;
 117         unsigned long n_exp_balk_nos;
 118 #endif /* #ifdef CONFIG_RCU_BOOST */
 119 #endif /* #ifdef CONFIG_RCU_TRACE */
 120 };
 121
 122 static struct rcu_preempt_ctrlblk rcu_preempt_ctrlblk = {
 123         .rcb.donetail = &rcu_preempt_ctrlblk.rcb.rcucblist,
 124         .rcb.curtail = &rcu_preempt_ctrlblk.rcb.rcucblist,
 125         .nexttail = &rcu_preempt_ctrlblk.rcb.rcucblist,
 126         .blkd_tasks = LIST_HEAD_INIT(rcu_preempt_ctrlblk.blkd_tasks),
 127 };
 128
 129 static int rcu_preempted_readers_exp(void);
 130 static void rcu_report_exp_done(void);
 131
 132 /*
 133  * Return true if the CPU has not yet responded to the current grace period.
 134  */
 135 static int rcu_cpu_blocking_cur_gp(void)
 136 {
 137         return rcu_preempt_ctrlblk.gpcpu != rcu_preempt_ctrlblk.gpnum;
 138 }
 139
 140 /*
 141  * Check for a running RCU reader.  Because there is only one CPU,
 142  * there can be but one running RCU reader at a time.  ;-)
 143  */
 144 static int rcu_preempt_running_reader(void)
 145 {
 146         return current->rcu_read_lock_nesting;
 147 }
 148
 149 /*
 150  * Check for preempted RCU readers blocking any grace period.
 151  * If the caller needs a reliable answer, it must disable hard irqs.
 152  */
 153 static int rcu_preempt_blocked_readers_any(void)
 154 {
 155         return !list_empty(&rcu_preempt_ctrlblk.blkd_tasks);
 156 }
 157
 158 /*
 159  * Check for preempted RCU readers blocking the current grace period.
 160  * If the caller needs a reliable answer, it must disable hard irqs.
 161  */
 162 static int rcu_preempt_blocked_readers_cgp(void)
 163 {
 164         return rcu_preempt_ctrlblk.gp_tasks != NULL;
 165 }
 166
 167 /*
 168  * Return true if another preemptible-RCU grace period is needed.
 169  */
 170 static int rcu_preempt_needs_another_gp(void)
 171 {
 172         return *rcu_preempt_ctrlblk.rcb.curtail != NULL;
 173 }
 174
 175 /*
 176  * Return true if a preemptible-RCU grace period is in progress.
 177  * The caller must disable hardirqs.
 178  */
 179 static int rcu_preempt_gp_in_progress(void)
 180 {
 181         return rcu_preempt_ctrlblk.completed != rcu_preempt_ctrlblk.gpnum;
 182 }
 183
 184 /*
 185  * Advance a ->blkd_tasks-list pointer to the next entry, instead
 186  * returning NULL if at the end of the list.
 187  */
 188 static struct list_head *rcu_next_node_entry(struct task_struct *t)
 189 {
 190         struct list_head *np;
 191
 192         np = t->rcu_node_entry.next;
 193         if (np == &rcu_preempt_ctrlblk.blkd_tasks)
 194                 np = NULL;
 195         return np;
 196 }
 197
 198 #ifdef CONFIG_RCU_TRACE
 199
 200 #ifdef CONFIG_RCU_BOOST
 201 static void rcu_initiate_boost_trace(void);
 202 static void rcu_initiate_exp_boost_trace(void);
 203 #endif /* #ifdef CONFIG_RCU_BOOST */
 204
 205 /*
 206  * Dump additional statistice for TINY_PREEMPT_RCU.
 207  */
 208 static void show_tiny_preempt_stats(struct seq_file *m)
 209 {
 210         seq_printf(m, "rcu_preempt: qlen=%ld gp=%lu g%u/p%u/c%u tasks=%c%c%c\n",
 211                    rcu_preempt_ctrlblk.rcb.qlen,
 212                    rcu_preempt_ctrlblk.n_grace_periods,
 213                    rcu_preempt_ctrlblk.gpnum,
 214                    rcu_preempt_ctrlblk.gpcpu,
 215                    rcu_preempt_ctrlblk.completed,
 216                    "T."[list_empty(&rcu_preempt_ctrlblk.blkd_tasks)],
 217                    "N."[!rcu_preempt_ctrlblk.gp_tasks],
 218                    "E."[!rcu_preempt_ctrlblk.exp_tasks]);
 219 #ifdef CONFIG_RCU_BOOST
 220         seq_printf(m, "%sttb=%c ntb=%lu neb=%lu nnb=%lu j=%04x bt=%04x\n",
 221                    "             ",
 222                    "B."[!rcu_preempt_ctrlblk.boost_tasks],
 223                    rcu_preempt_ctrlblk.n_tasks_boosted,
 224                    rcu_preempt_ctrlblk.n_exp_boosts,
 225                    rcu_preempt_ctrlblk.n_normal_boosts,
 226                    (int)(jiffies & 0xffff),
 227                    (int)(rcu_preempt_ctrlblk.boost_time & 0xffff));
 228         seq_printf(m, "             %s: nt=%lu gt=%lu bt=%lu ny=%lu nos=%lu\n",
 229                    "normal balk",
 230                    rcu_preempt_ctrlblk.n_normal_balk_blkd_tasks,
 231                    rcu_preempt_ctrlblk.n_normal_balk_gp_tasks,
 232                    rcu_preempt_ctrlblk.n_normal_balk_boost_tasks,
 233                    rcu_preempt_ctrlblk.n_normal_balk_notyet,
 234                    rcu_preempt_ctrlblk.n_normal_balk_nos);
 235         seq_printf(m, "             exp balk: bt=%lu nos=%lu\n",
 236                    rcu_preempt_ctrlblk.n_exp_balk_blkd_tasks,
 237                    rcu_preempt_ctrlblk.n_exp_balk_nos);
 238 #endif /* #ifdef CONFIG_RCU_BOOST */
 239 }
 240
 241 #endif /* #ifdef CONFIG_RCU_TRACE */
 242
 243 #ifdef CONFIG_RCU_BOOST
 244
 245 #include "rtmutex_common.h"
 246
 247 /*
 248  * Carry out RCU priority boosting on the task indicated by ->boost_tasks,
 249  * and advance ->boost_tasks to the next task in the ->blkd_tasks list.
 250  */
 251 static int rcu_boost(void)
 252 {
 253         unsigned long flags;
 254         struct rt_mutex mtx;
 255         struct list_head *np;
 256         struct task_struct *t;
 257
 258         if (rcu_preempt_ctrlblk.boost_tasks == NULL)
 259                 return 0;  /* Nothing to boost. */
 260         raw_local_irq_save(flags);
 261         t = container_of(rcu_preempt_ctrlblk.boost_tasks, struct task_struct,
 262                          rcu_node_entry);
 263         np = rcu_next_node_entry(t);
 264         rt_mutex_init_proxy_locked(&mtx, t);
 265         t->rcu_boost_mutex = &mtx;
 266         t->rcu_read_unlock_special |= RCU_READ_UNLOCK_BOOSTED;
 267         raw_local_irq_restore(flags);
 268         rt_mutex_lock(&mtx);
 269         RCU_TRACE(rcu_preempt_ctrlblk.n_tasks_boosted++);
 270         rt_mutex_unlock(&mtx);
 271         return rcu_preempt_ctrlblk.boost_tasks != NULL;
 272 }
 273
 274 /*
 275  * Check to see if it is now time to start boosting RCU readers blocking
 276  * the current grace period, and, if so, tell the rcu_kthread_task to
 277  * start boosting them.  If there is an expedited boost in progress,
 278  * we wait for it to complete.
 279  *
 280  * If there are no blocked readers blocking the current grace period,
 281  * return 0 to let the caller know, otherwise return 1.  Note that this
 282  * return value is independent of whether or not boosting was done.
 283  */
 284 static int rcu_initiate_boost(void)
 285 {
 286         if (!rcu_preempt_blocked_readers_cgp()) {
 287                 RCU_TRACE(rcu_preempt_ctrlblk.n_normal_balk_blkd_tasks++);
 288                 return 0;
 289         }
 290         if (rcu_preempt_ctrlblk.gp_tasks != NULL &&
 291             rcu_preempt_ctrlblk.boost_tasks == NULL &&
 292             ULONG_CMP_GE(jiffies, rcu_preempt_ctrlblk.boost_time)) {
 293                 rcu_preempt_ctrlblk.boost_tasks = rcu_preempt_ctrlblk.gp_tasks;
 294                 invoke_rcu_kthread();
 295                 RCU_TRACE(rcu_preempt_ctrlblk.n_normal_boosts++);
 296         } else
 297                 RCU_TRACE(rcu_initiate_boost_trace());
 298         return 1;
 299 }
 300
 301 /*
 302  * Initiate boosting for an expedited grace period.
 303  */
 304 static void rcu_initiate_expedited_boost(void)
 305 {
 306         unsigned long flags;
 307
 308         raw_local_irq_save(flags);
 309         if (!list_empty(&rcu_preempt_ctrlblk.blkd_tasks)) {
 310                 rcu_preempt_ctrlblk.boost_tasks =
 311                         rcu_preempt_ctrlblk.blkd_tasks.next;
 312                 invoke_rcu_kthread();
 313                 RCU_TRACE(rcu_preempt_ctrlblk.n_exp_boosts++);
 314         } else
 315                 RCU_TRACE(rcu_initiate_exp_boost_trace());
 316         raw_local_irq_restore(flags);
 317 }
 318
 319 #define RCU_BOOST_DELAY_JIFFIES DIV_ROUND_UP(CONFIG_RCU_BOOST_DELAY * HZ, 1000)
 320
 321 /*
 322  * Do priority-boost accounting for the start of a new grace period.
 323  */
 324 static void rcu_preempt_boost_start_gp(void)
 325 {
 326         rcu_preempt_ctrlblk.boost_time = jiffies + RCU_BOOST_DELAY_JIFFIES;
 327 }
 328
 329 #else /* #ifdef CONFIG_RCU_BOOST */
 330
 331 /*
 332  * If there is no RCU priority boosting, we don't boost.
 333  */
 334 static int rcu_boost(void)
 335 {
 336         return 0;
 337 }
 338
 339 /*
 340  * If there is no RCU priority boosting, we don't initiate boosting,
 341  * but we do indicate whether there are blocked readers blocking the
 342  * current grace period.
 343  */
 344 static int rcu_initiate_boost(void)
 345 {
 346         return rcu_preempt_blocked_readers_cgp();
 347 }
 348
 349 /*
 350  * If there is no RCU priority boosting, we don't initiate expedited boosting.
 351  */
 352 static void rcu_initiate_expedited_boost(void)
 353 {
 354 }
 355
 356 /*
 357  * If there is no RCU priority boosting, nothing to do at grace-period start.
 358  */
 359 static void rcu_preempt_boost_start_gp(void)
 360 {
 361 }
 362
 363 #endif /* else #ifdef CONFIG_RCU_BOOST */
 364
 365 /*
 366  * Record a preemptible-RCU quiescent state for the specified CPU.  Note
 367  * that this just means that the task currently running on the CPU is
 368  * in a quiescent state.  There might be any number of tasks blocked
 369  * while in an RCU read-side critical section.
 370  *
 371  * Unlike the other rcu_*_qs() functions, callers to this function
 372  * must disable irqs in order to protect the assignment to
 373  * ->rcu_read_unlock_special.
 374  *
 375  * Because this is a single-CPU implementation, the only way a grace
 376  * period can end is if the CPU is in a quiescent state.  The reason is
 377  * that a blocked preemptible-RCU reader can exit its critical section
 378  * only if the CPU is running it at the time.  Therefore, when the
 379  * last task blocking the current grace period exits its RCU read-side
 380  * critical section, neither the CPU nor blocked tasks will be stopping
 381  * the current grace period.  (In contrast, SMP implementations
 382  * might have CPUs running in RCU read-side critical sections that
 383  * block later grace periods -- but this is not possible given only
 384  * one CPU.)
 385  */
 386 static void rcu_preempt_cpu_qs(void)
 387 {
 388         /* Record both CPU and task as having responded to current GP. */
 389         rcu_preempt_ctrlblk.gpcpu = rcu_preempt_ctrlblk.gpnum;
 390         current->rcu_read_unlock_special &= ~RCU_READ_UNLOCK_NEED_QS;
 391
 392         /* If there is no GP then there is nothing more to do.  */
 393         if (!rcu_preempt_gp_in_progress())
 394                 return;
 395         /*
 396          * Check up on boosting.  If there are readers blocking the
 397          * current grace period, leave.
 398          */
 399         if (rcu_initiate_boost())
 400                 return;
 401
 402         /* Advance callbacks. */
 403         rcu_preempt_ctrlblk.completed = rcu_preempt_ctrlblk.gpnum;
 404         rcu_preempt_ctrlblk.rcb.donetail = rcu_preempt_ctrlblk.rcb.curtail;
 405         rcu_preempt_ctrlblk.rcb.curtail = rcu_preempt_ctrlblk.nexttail;
 406
 407         /* If there are no blocked readers, next GP is done instantly. */
 408         if (!rcu_preempt_blocked_readers_any())
 409                 rcu_preempt_ctrlblk.rcb.donetail = rcu_preempt_ctrlblk.nexttail;
 410
 411         /* If there are done callbacks, cause them to be invoked. */
 412         if (*rcu_preempt_ctrlblk.rcb.donetail != NULL)
 413                 invoke_rcu_kthread();
 414 }
 415
 416 /*
 417  * Start a new RCU grace period if warranted.  Hard irqs must be disabled.
 418  */
 419 static void rcu_preempt_start_gp(void)
 420 {
 421         if (!rcu_preempt_gp_in_progress() && rcu_preempt_needs_another_gp()) {
 422
 423                 /* Official start of GP. */
 424                 rcu_preempt_ctrlblk.gpnum++;
 425                 RCU_TRACE(rcu_preempt_ctrlblk.n_grace_periods++);
 426
 427                 /* Any blocked RCU readers block new GP. */
 428                 if (rcu_preempt_blocked_readers_any())
 429                         rcu_preempt_ctrlblk.gp_tasks =
 430                                 rcu_preempt_ctrlblk.blkd_tasks.next;
 431
 432                 /* Set up for RCU priority boosting. */
 433                 rcu_preempt_boost_start_gp();
 434
 435                 /* If there is no running reader, CPU is done with GP. */
 436                 if (!rcu_preempt_running_reader())
 437                         rcu_preempt_cpu_qs();
 438         }
 439 }
 440
 441 /*
 442  * We have entered the scheduler, and the current task might soon be
 443  * context-switched away from.  If this task is in an RCU read-side
 444  * critical section, we will no longer be able to rely on the CPU to
 445  * record that fact, so we enqueue the task on the blkd_tasks list.
 446  * If the task started after the current grace period began, as recorded
 447  * by ->gpcpu, we enqueue at the beginning of the list.  Otherwise
 448  * before the element referenced by ->gp_tasks (or at the tail if
 449  * ->gp_tasks is NULL) and point ->gp_tasks at the newly added element.
 450  * The task will dequeue itself when it exits the outermost enclosing
 451  * RCU read-side critical section.  Therefore, the current grace period
 452  * cannot be permitted to complete until the ->gp_tasks pointer becomes
 453  * NULL.
 454  *
 455  * Caller must disable preemption.
 456  */
 457 void rcu_preempt_note_context_switch(void)
 458 {
 459         struct task_struct *t = current;
 460         unsigned long flags;
 461
 462         local_irq_save(flags); /* must exclude scheduler_tick(). */
 463         if (rcu_preempt_running_reader() &&
 464             (t->rcu_read_unlock_special & RCU_READ_UNLOCK_BLOCKED) == 0) {
 465
 466                 /* Possibly blocking in an RCU read-side critical section. */
 467                 t->rcu_read_unlock_special |= RCU_READ_UNLOCK_BLOCKED;
 468
 469                 /*
 470                  * If this CPU has already checked in, then this task
 471                  * will hold up the next grace period rather than the
 472                  * current grace period.  Queue the task accordingly.
 473                  * If the task is queued for the current grace period
 474                  * (i.e., this CPU has not yet passed through a quiescent
 475                  * state for the current grace period), then as long
 476                  * as that task remains queued, the current grace period
 477                  * cannot end.
 478                  */
 479                 list_add(&t->rcu_node_entry, &rcu_preempt_ctrlblk.blkd_tasks);
 480                 if (rcu_cpu_blocking_cur_gp())
 481                         rcu_preempt_ctrlblk.gp_tasks = &t->rcu_node_entry;
 482         }
 483
 484         /*
 485          * Either we were not in an RCU read-side critical section to
 486          * begin with, or we have now recorded that critical section
 487          * globally.  Either way, we can now note a quiescent state
 488          * for this CPU.  Again, if we were in an RCU read-side critical
 489          * section, and if that critical section was blocking the current
 490          * grace period, then the fact that the task has been enqueued
 491          * means that current grace period continues to be blocked.
 492          */
 493         rcu_preempt_cpu_qs();
 494         local_irq_restore(flags);
 495 }
 496
 497 /*
 498  * Tiny-preemptible RCU implementation for rcu_read_lock().
 499  * Just increment ->rcu_read_lock_nesting, shared state will be updated
 500  * if we block.
 501  */
 502 void __rcu_read_lock(void)
 503 {
 504         current->rcu_read_lock_nesting++;
 505         barrier();  /* needed if we ever invoke rcu_read_lock in rcutiny.c */
 506 }
 507 EXPORT_SYMBOL_GPL(__rcu_read_lock);
 508
 509 /*
 510  * Handle special cases during rcu_read_unlock(), such as needing to
 511  * notify RCU core processing or task having blocked during the RCU
 512  * read-side critical section.
 513  */
 514 static void rcu_read_unlock_special(struct task_struct *t)
 515 {
 516         int empty;
 517         int empty_exp;
 518         unsigned long flags;
 519         struct list_head *np;
 520         int special;
 521
 522         /*
 523          * NMI handlers cannot block and cannot safely manipulate state.
 524          * They therefore cannot possibly be special, so just leave.
 525          */
 526         if (in_nmi())
 527                 return;
 528
 529         local_irq_save(flags);
 530
 531         /*
 532          * If RCU core is waiting for this CPU to exit critical section,
 533          * let it know that we have done so.
 534          */
 535         special = t->rcu_read_unlock_special;
 536         if (special & RCU_READ_UNLOCK_NEED_QS)
 537                 rcu_preempt_cpu_qs();
 538
 539         /* Hardware IRQ handlers cannot block. */
 540         if (in_irq()) {
 541                 local_irq_restore(flags);
 542                 return;
 543         }
 544
 545         /* Clean up if blocked during RCU read-side critical section. */
 546         if (special & RCU_READ_UNLOCK_BLOCKED) {
 547                 t->rcu_read_unlock_special &= ~RCU_READ_UNLOCK_BLOCKED;
 548
 549                 /*
 550                  * Remove this task from the ->blkd_tasks list and adjust
 551                  * any pointers that might have been referencing it.
 552                  */
 553                 empty = !rcu_preempt_blocked_readers_cgp();
 554                 empty_exp = rcu_preempt_ctrlblk.exp_tasks == NULL;
 555                 np = rcu_next_node_entry(t);
 556                 list_del_init(&t->rcu_node_entry);
 557                 if (&t->rcu_node_entry == rcu_preempt_ctrlblk.gp_tasks)
 558                         rcu_preempt_ctrlblk.gp_tasks = np;
 559                 if (&t->rcu_node_entry == rcu_preempt_ctrlblk.exp_tasks)
 560                         rcu_preempt_ctrlblk.exp_tasks = np;
 561 #ifdef CONFIG_RCU_BOOST
 562                 if (&t->rcu_node_entry == rcu_preempt_ctrlblk.boost_tasks)
 563                         rcu_preempt_ctrlblk.boost_tasks = np;
 564 #endif /* #ifdef CONFIG_RCU_BOOST */
 565
 566                 /*
 567                  * If this was the last task on the current list, and if
 568                  * we aren't waiting on the CPU, report the quiescent state
 569                  * and start a new grace period if needed.
 570                  */
 571                 if (!empty && !rcu_preempt_blocked_readers_cgp()) {
 572                         rcu_preempt_cpu_qs();
 573                         rcu_preempt_start_gp();
 574                 }
 575
 576                 /*
 577                  * If this was the last task on the expedited lists,
 578                  * then we need wake up the waiting task.
 579                  */
 580                 if (!empty_exp && rcu_preempt_ctrlblk.exp_tasks == NULL)
 581                         rcu_report_exp_done();
 582         }
 583 #ifdef CONFIG_RCU_BOOST
 584         /* Unboost self if was boosted. */
 585         if (special & RCU_READ_UNLOCK_BOOSTED) {
 586                 t->rcu_read_unlock_special &= ~RCU_READ_UNLOCK_BOOSTED;
 587                 rt_mutex_unlock(t->rcu_boost_mutex);
 588                 t->rcu_boost_mutex = NULL;
 589         }
 590 #endif /* #ifdef CONFIG_RCU_BOOST */
 591         local_irq_restore(flags);
 592 }
 593
 594 /*
 595  * Tiny-preemptible RCU implementation for rcu_read_unlock().
 596  * Decrement ->rcu_read_lock_nesting.  If the result is zero (outermost
 597  * rcu_read_unlock()) and ->rcu_read_unlock_special is non-zero, then
 598  * invoke rcu_read_unlock_special() to clean up after a context switch
 599  * in an RCU read-side critical section and other special cases.
 600  */
 601 void __rcu_read_unlock(void)
 602 {
 603         struct task_struct *t = current;
 604
 605         barrier();  /* needed if we ever invoke rcu_read_unlock in rcutiny.c */
 606         --t->rcu_read_lock_nesting;
 607         barrier();  /* decrement before load of ->rcu_read_unlock_special */
 608         if (t->rcu_read_lock_nesting == 0 &&
 609             unlikely(ACCESS_ONCE(t->rcu_read_unlock_special)))
 610                 rcu_read_unlock_special(t);
 611 #ifdef CONFIG_PROVE_LOCKING
 612         WARN_ON_ONCE(t->rcu_read_lock_nesting < 0);
 613 #endif /* #ifdef CONFIG_PROVE_LOCKING */
 614 }
 615 EXPORT_SYMBOL_GPL(__rcu_read_unlock);
 616
 617 /*
 618  * Check for a quiescent state from the current CPU.  When a task blocks,
 619  * the task is recorded in the rcu_preempt_ctrlblk structure, which is
 620  * checked elsewhere.  This is called from the scheduling-clock interrupt.
 621  *
 622  * Caller must disable hard irqs.
 623  */
 624 static void rcu_preempt_check_callbacks(void)
 625 {
 626         struct task_struct *t = current;
 627
 628         if (rcu_preempt_gp_in_progress() &&
 629             (!rcu_preempt_running_reader() ||
 630              !rcu_cpu_blocking_cur_gp()))
 631                 rcu_preempt_cpu_qs();
 632         if (&rcu_preempt_ctrlblk.rcb.rcucblist !=
 633             rcu_preempt_ctrlblk.rcb.donetail)
 634                 invoke_rcu_kthread();
 635         if (rcu_preempt_gp_in_progress() &&
 636             rcu_cpu_blocking_cur_gp() &&
 637             rcu_preempt_running_reader())
 638                 t->rcu_read_unlock_special |= RCU_READ_UNLOCK_NEED_QS;
 639 }
 640
 641 /*
 642  * TINY_PREEMPT_RCU has an extra callback-list tail pointer to
 643  * update, so this is invoked from rcu_process_callbacks() to
 644  * handle that case.  Of course, it is invoked for all flavors of
 645  * RCU, but RCU callbacks can appear only on one of the lists, and
 646  * neither ->nexttail nor ->donetail can possibly be NULL, so there
 647  * is no need for an explicit check.
 648  */
 649 static void rcu_preempt_remove_callbacks(struct rcu_ctrlblk *rcp)
 650 {
 651         if (rcu_preempt_ctrlblk.nexttail == rcp->donetail)
 652                 rcu_preempt_ctrlblk.nexttail = &rcp->rcucblist;
 653 }
 654
 655 /*
 656  * Process callbacks for preemptible RCU.
 657  */
 658 static void rcu_preempt_process_callbacks(void)
 659 {
 660         rcu_process_callbacks(&rcu_preempt_ctrlblk.rcb);
 661 }
 662
 663 /*
 664  * Queue a preemptible -RCU callback for invocation after a grace period.
 665  */
 666 void call_rcu(struct rcu_head *head, void (*func)(struct rcu_head *rcu))
 667 {
 668         unsigned long flags;
 669
 670         debug_rcu_head_queue(head);
 671         head->func = func;
 672         head->next = NULL;
 673
 674         local_irq_save(flags);
 675         *rcu_preempt_ctrlblk.nexttail = head;
 676         rcu_preempt_ctrlblk.nexttail = &head->next;
 677         RCU_TRACE(rcu_preempt_ctrlblk.rcb.qlen++);
 678         rcu_preempt_start_gp();  /* checks to see if GP needed. */
 679         local_irq_restore(flags);
 680 }
 681 EXPORT_SYMBOL_GPL(call_rcu);
 682
 683 void rcu_barrier(void)
 684 {
 685         struct rcu_synchronize rcu;
 686
 687         init_rcu_head_on_stack(&rcu.head);
 688         init_completion(&rcu.completion);
 689         /* Will wake me after RCU finished. */
 690         call_rcu(&rcu.head, wakeme_after_rcu);
 691         /* Wait for it. */
 692         wait_for_completion(&rcu.completion);
 693         destroy_rcu_head_on_stack(&rcu.head);
 694 }
 695 EXPORT_SYMBOL_GPL(rcu_barrier);
 696
 697 /*
 698  * synchronize_rcu - wait until a grace period has elapsed.
 699  *
 700  * Control will return to the caller some time after a full grace
 701  * period has elapsed, in other words after all currently executing RCU
 702  * read-side critical sections have completed.  RCU read-side critical
 703  * sections are delimited by rcu_read_lock() and rcu_read_unlock(),
 704  * and may be nested.
 705  */
 706 void synchronize_rcu(void)
 707 {
 708 #ifdef CONFIG_DEBUG_LOCK_ALLOC
 709         if (!rcu_scheduler_active)
 710                 return;
 711 #endif /* #ifdef CONFIG_DEBUG_LOCK_ALLOC */
 712
 713         WARN_ON_ONCE(rcu_preempt_running_reader());
 714         if (!rcu_preempt_blocked_readers_any())
 715                 return;
 716
 717         /* Once we get past the fastpath checks, same code as rcu_barrier(). */
 718         rcu_barrier();
 719 }
 720 EXPORT_SYMBOL_GPL(synchronize_rcu);
 721
 722 static DECLARE_WAIT_QUEUE_HEAD(sync_rcu_preempt_exp_wq);
 723 static unsigned long sync_rcu_preempt_exp_count;
 724 static DEFINE_MUTEX(sync_rcu_preempt_exp_mutex);
 725
 726 /*
 727  * Return non-zero if there are any tasks in RCU read-side critical
 728  * sections blocking the current preemptible-RCU expedited grace period.
 729  * If there is no preemptible-RCU expedited grace period currently in
 730  * progress, returns zero unconditionally.
 731  */
 732 static int rcu_preempted_readers_exp(void)
 733 {
 734         return rcu_preempt_ctrlblk.exp_tasks != NULL;
 735 }
 736
 737 /*
 738  * Report the exit from RCU read-side critical section for the last task
 739  * that queued itself during or before the current expedited preemptible-RCU
 740  * grace period.
 741  */
 742 static void rcu_report_exp_done(void)
 743 {
 744         wake_up(&sync_rcu_preempt_exp_wq);
 745 }
 746
 747 /*
 748  * Wait for an rcu-preempt grace period, but expedite it.  The basic idea
 749  * is to rely in the fact that there is but one CPU, and that it is
 750  * illegal for a task to invoke synchronize_rcu_expedited() while in a
 751  * preemptible-RCU read-side critical section.  Therefore, any such
 752  * critical sections must correspond to blocked tasks, which must therefore
 753  * be on the ->blkd_tasks list.  So just record the current head of the
 754  * list in the ->exp_tasks pointer, and wait for all tasks including and
 755  * after the task pointed to by ->exp_tasks to drain.
 756  */
 757 void synchronize_rcu_expedited(void)
 758 {
 759         unsigned long flags;
 760         struct rcu_preempt_ctrlblk *rpcp = &rcu_preempt_ctrlblk;
 761         unsigned long snap;
 762
 763         barrier(); /* ensure prior action seen before grace period. */
 764
 765         WARN_ON_ONCE(rcu_preempt_running_reader());
 766
 767         /*
 768          * Acquire lock so that there is only one preemptible RCU grace
 769          * period in flight.  Of course, if someone does the expedited
 770          * grace period for us while we are acquiring the lock, just leave.
 771          */
 772         snap = sync_rcu_preempt_exp_count + 1;
 773         mutex_lock(&sync_rcu_preempt_exp_mutex);
 774         if (ULONG_CMP_LT(snap, sync_rcu_preempt_exp_count))
 775                 goto unlock_mb_ret; /* Others did our work for us. */
 776
 777         local_irq_save(flags);
 778
 779         /*
 780          * All RCU readers have to already be on blkd_tasks because
 781          * we cannot legally be executing in an RCU read-side critical
 782          * section.
 783          */
 784
 785         /* Snapshot current head of ->blkd_tasks list. */
 786         rpcp->exp_tasks = rpcp->blkd_tasks.next;
 787         if (rpcp->exp_tasks == &rpcp->blkd_tasks)
 788                 rpcp->exp_tasks = NULL;
 789         local_irq_restore(flags);
 790
 791         /* Wait for tail of ->blkd_tasks list to drain. */
 792         if (rcu_preempted_readers_exp())
 793                 rcu_initiate_expedited_boost();
 794                 wait_event(sync_rcu_preempt_exp_wq,
 795                            !rcu_preempted_readers_exp());
 796
 797         /* Clean up and exit. */
 798         barrier(); /* ensure expedited GP seen before counter increment. */
 799         sync_rcu_preempt_exp_count++;
 800 unlock_mb_ret:
 801         mutex_unlock(&sync_rcu_preempt_exp_mutex);
 802         barrier(); /* ensure subsequent action seen after grace period. */
 803 }
 804 EXPORT_SYMBOL_GPL(synchronize_rcu_expedited);
 805
 806 /*
 807  * Does preemptible RCU need the CPU to stay out of dynticks mode?
 808  */
 809 int rcu_preempt_needs_cpu(void)
 810 {
 811         if (!rcu_preempt_running_reader())
 812                 rcu_preempt_cpu_qs();
 813         return rcu_preempt_ctrlblk.rcb.rcucblist != NULL;
 814 }
 815
 816 /*
 817  * Check for a task exiting while in a preemptible -RCU read-side
 818  * critical section, clean up if so.  No need to issue warnings,
 819  * as debug_check_no_locks_held() already does this if lockdep
 820  * is enabled.
 821  */
 822 void exit_rcu(void)
 823 {
 824         struct task_struct *t = current;
 825
 826         if (t->rcu_read_lock_nesting == 0)
 827                 return;
 828         t->rcu_read_lock_nesting = 1;
 829         __rcu_read_unlock();
 830 }
 831
 832 #else /* #ifdef CONFIG_TINY_PREEMPT_RCU */
 833
 834 #ifdef CONFIG_RCU_TRACE
 835
 836 /*
 837  * Because preemptible RCU does not exist, it is not necessary to
 838  * dump out its statistics.
 839  */
 840 static void show_tiny_preempt_stats(struct seq_file *m)
 841 {
 842 }
 843
 844 #endif /* #ifdef CONFIG_RCU_TRACE */
 845
 846 /*
 847  * Because preemptible RCU does not exist, it is never necessary to
 848  * boost preempted RCU readers.
 849  */
 850 static int rcu_boost(void)
 851 {
 852         return 0;
 853 }
 854
 855 /*
 856  * Because preemptible RCU does not exist, it never has any callbacks
 857  * to check.
 858  */
 859 static void rcu_preempt_check_callbacks(void)
 860 {
 861 }
 862
 863 /*
 864  * Because preemptible RCU does not exist, it never has any callbacks
 865  * to remove.
 866  */
 867 static void rcu_preempt_remove_callbacks(struct rcu_ctrlblk *rcp)
 868 {
 869 }
 870
 871 /*
 872  * Because preemptible RCU does not exist, it never has any callbacks
 873  * to process.
 874  */
 875 static void rcu_preempt_process_callbacks(void)
 876 {
 877 }
 878
 879 #endif /* #else #ifdef CONFIG_TINY_PREEMPT_RCU */
 880
 881 #ifdef CONFIG_DEBUG_LOCK_ALLOC
 882 #include <linux/kernel_stat.h>
 883
 884 /*
 885  * During boot, we forgive RCU lockdep issues.  After this function is
 886  * invoked, we start taking RCU lockdep issues seriously.
 887  */
 888 void __init rcu_scheduler_starting(void)
 889 {
 890         WARN_ON(nr_context_switches() > 0);
 891         rcu_scheduler_active = 1;
 892 }
 893
 894 #endif /* #ifdef CONFIG_DEBUG_LOCK_ALLOC */
 895
 896 #ifdef CONFIG_RCU_BOOST
 897 #define RCU_BOOST_PRIO CONFIG_RCU_BOOST_PRIO
 898 #else /* #ifdef CONFIG_RCU_BOOST */
 899 #define RCU_BOOST_PRIO 1
 900 #endif /* #else #ifdef CONFIG_RCU_BOOST */
 901
 902 #ifdef CONFIG_RCU_TRACE
 903
 904 #ifdef CONFIG_RCU_BOOST
 905
 906 static void rcu_initiate_boost_trace(void)
 907 {
 908         if (rcu_preempt_ctrlblk.gp_tasks == NULL)
 909                 rcu_preempt_ctrlblk.n_normal_balk_gp_tasks++;
 910         else if (rcu_preempt_ctrlblk.boost_tasks != NULL)
 911                 rcu_preempt_ctrlblk.n_normal_balk_boost_tasks++;
 912         else if (!ULONG_CMP_GE(jiffies, rcu_preempt_ctrlblk.boost_time))
 913                 rcu_preempt_ctrlblk.n_normal_balk_notyet++;
 914         else
 915                 rcu_preempt_ctrlblk.n_normal_balk_nos++;
 916 }
 917
 918 static void rcu_initiate_exp_boost_trace(void)
 919 {
 920         if (list_empty(&rcu_preempt_ctrlblk.blkd_tasks))
 921                 rcu_preempt_ctrlblk.n_exp_balk_blkd_tasks++;
 922         else
 923                 rcu_preempt_ctrlblk.n_exp_balk_nos++;
 924 }
 925
 926 #endif /* #ifdef CONFIG_RCU_BOOST */
 927
 928 static void rcu_trace_sub_qlen(struct rcu_ctrlblk *rcp, int n)
 929 {
 930         unsigned long flags;
 931
 932         raw_local_irq_save(flags);
 933         rcp->qlen -= n;
 934         raw_local_irq_restore(flags);
 935 }
 936
 937 /*
 938  * Dump statistics for TINY_RCU, such as they are.
 939  */
 940 static int show_tiny_stats(struct seq_file *m, void *unused)
 941 {
 942         show_tiny_preempt_stats(m);
 943         seq_printf(m, "rcu_sched: qlen: %ld\n", rcu_sched_ctrlblk.qlen);
 944         seq_printf(m, "rcu_bh: qlen: %ld\n", rcu_bh_ctrlblk.qlen);
 945         return 0;
 946 }
 947
 948 static int show_tiny_stats_open(struct inode *inode, struct file *file)
 949 {
 950         return single_open(file, show_tiny_stats, NULL);
 951 }
 952
 953 static const struct file_operations show_tiny_stats_fops = {
 954         .owner = THIS_MODULE,
 955         .open = show_tiny_stats_open,
 956         .read = seq_read,
 957         .llseek = seq_lseek,
 958         .release = single_release,
 959 };
 960
 961 static struct dentry *rcudir;
 962
 963 static int __init rcutiny_trace_init(void)
 964 {
 965         struct dentry *retval;
 966
 967         rcudir = debugfs_create_dir("rcu", NULL);
 968         if (!rcudir)
 969                 goto free_out;
 970         retval = debugfs_create_file("rcudata", 0444, rcudir,
 971                                      NULL, &show_tiny_stats_fops);
 972         if (!retval)
 973                 goto free_out;
 974         return 0;
 975 free_out:
 976         debugfs_remove_recursive(rcudir);
 977         return 1;
 978 }
 979
 980 static void __exit rcutiny_trace_cleanup(void)
 981 {
 982         debugfs_remove_recursive(rcudir);
 983 }
 984
 985 module_init(rcutiny_trace_init);
 986 module_exit(rcutiny_trace_cleanup);
 987
 988 MODULE_AUTHOR("Paul E. McKenney");
 989 MODULE_DESCRIPTION("Read-Copy Update tracing for tiny implementation");
 990 MODULE_LICENSE("GPL");
 991
 992 #endif /* #ifdef CONFIG_RCU_TRACE */