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