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 void rcu_barrier(void)
 701 {
 702         struct rcu_synchronize rcu;
 703
 704         init_rcu_head_on_stack(&rcu.head);
 705         init_completion(&rcu.completion);
 706         /* Will wake me after RCU finished. */
 707         call_rcu(&rcu.head, wakeme_after_rcu);
 708         /* Wait for it. */
 709         wait_for_completion(&rcu.completion);
 710         destroy_rcu_head_on_stack(&rcu.head);
 711 }
 712 EXPORT_SYMBOL_GPL(rcu_barrier);
 713
 714 /*
 715  * synchronize_rcu - wait until a grace period has elapsed.
 716  *
 717  * Control will return to the caller some time after a full grace
 718  * period has elapsed, in other words after all currently executing RCU
 719  * read-side critical sections have completed.  RCU read-side critical
 720  * sections are delimited by rcu_read_lock() and rcu_read_unlock(),
 721  * and may be nested.
 722  */
 723 void synchronize_rcu(void)
 724 {
 725 #ifdef CONFIG_DEBUG_LOCK_ALLOC
 726         if (!rcu_scheduler_active)
 727                 return;
 728 #endif /* #ifdef CONFIG_DEBUG_LOCK_ALLOC */
 729
 730         WARN_ON_ONCE(rcu_preempt_running_reader());
 731         if (!rcu_preempt_blocked_readers_any())
 732                 return;
 733
 734         /* Once we get past the fastpath checks, same code as rcu_barrier(). */
 735         rcu_barrier();
 736 }
 737 EXPORT_SYMBOL_GPL(synchronize_rcu);
 738
 739 static DECLARE_WAIT_QUEUE_HEAD(sync_rcu_preempt_exp_wq);
 740 static unsigned long sync_rcu_preempt_exp_count;
 741 static DEFINE_MUTEX(sync_rcu_preempt_exp_mutex);
 742
 743 /*
 744  * Return non-zero if there are any tasks in RCU read-side critical
 745  * sections blocking the current preemptible-RCU expedited grace period.
 746  * If there is no preemptible-RCU expedited grace period currently in
 747  * progress, returns zero unconditionally.
 748  */
 749 static int rcu_preempted_readers_exp(void)
 750 {
 751         return rcu_preempt_ctrlblk.exp_tasks != NULL;
 752 }
 753
 754 /*
 755  * Report the exit from RCU read-side critical section for the last task
 756  * that queued itself during or before the current expedited preemptible-RCU
 757  * grace period.
 758  */
 759 static void rcu_report_exp_done(void)
 760 {
 761         wake_up(&sync_rcu_preempt_exp_wq);
 762 }
 763
 764 /*
 765  * Wait for an rcu-preempt grace period, but expedite it.  The basic idea
 766  * is to rely in the fact that there is but one CPU, and that it is
 767  * illegal for a task to invoke synchronize_rcu_expedited() while in a
 768  * preemptible-RCU read-side critical section.  Therefore, any such
 769  * critical sections must correspond to blocked tasks, which must therefore
 770  * be on the ->blkd_tasks list.  So just record the current head of the
 771  * list in the ->exp_tasks pointer, and wait for all tasks including and
 772  * after the task pointed to by ->exp_tasks to drain.
 773  */
 774 void synchronize_rcu_expedited(void)
 775 {
 776         unsigned long flags;
 777         struct rcu_preempt_ctrlblk *rpcp = &rcu_preempt_ctrlblk;
 778         unsigned long snap;
 779
 780         barrier(); /* ensure prior action seen before grace period. */
 781
 782         WARN_ON_ONCE(rcu_preempt_running_reader());
 783
 784         /*
 785          * Acquire lock so that there is only one preemptible RCU grace
 786          * period in flight.  Of course, if someone does the expedited
 787          * grace period for us while we are acquiring the lock, just leave.
 788          */
 789         snap = sync_rcu_preempt_exp_count + 1;
 790         mutex_lock(&sync_rcu_preempt_exp_mutex);
 791         if (ULONG_CMP_LT(snap, sync_rcu_preempt_exp_count))
 792                 goto unlock_mb_ret; /* Others did our work for us. */
 793
 794         local_irq_save(flags);
 795
 796         /*
 797          * All RCU readers have to already be on blkd_tasks because
 798          * we cannot legally be executing in an RCU read-side critical
 799          * section.
 800          */
 801
 802         /* Snapshot current head of ->blkd_tasks list. */
 803         rpcp->exp_tasks = rpcp->blkd_tasks.next;
 804         if (rpcp->exp_tasks == &rpcp->blkd_tasks)
 805                 rpcp->exp_tasks = NULL;
 806
 807         /* Wait for tail of ->blkd_tasks list to drain. */
 808         if (!rcu_preempted_readers_exp())
 809                 local_irq_restore(flags);
 810         else {
 811                 rcu_initiate_boost();
 812                 local_irq_restore(flags);
 813                 wait_event(sync_rcu_preempt_exp_wq,
 814                            !rcu_preempted_readers_exp());
 815         }
 816
 817         /* Clean up and exit. */
 818         barrier(); /* ensure expedited GP seen before counter increment. */
 819         sync_rcu_preempt_exp_count++;
 820 unlock_mb_ret:
 821         mutex_unlock(&sync_rcu_preempt_exp_mutex);
 822         barrier(); /* ensure subsequent action seen after grace period. */
 823 }
 824 EXPORT_SYMBOL_GPL(synchronize_rcu_expedited);
 825
 826 /*
 827  * Does preemptible RCU need the CPU to stay out of dynticks mode?
 828  */
 829 int rcu_preempt_needs_cpu(void)
 830 {
 831         if (!rcu_preempt_running_reader())
 832                 rcu_preempt_cpu_qs();
 833         return rcu_preempt_ctrlblk.rcb.rcucblist != NULL;
 834 }
 835
 836 /*
 837  * Check for a task exiting while in a preemptible -RCU read-side
 838  * critical section, clean up if so.  No need to issue warnings,
 839  * as debug_check_no_locks_held() already does this if lockdep
 840  * is enabled.
 841  */
 842 void exit_rcu(void)
 843 {
 844         struct task_struct *t = current;
 845
 846         if (t->rcu_read_lock_nesting == 0)
 847                 return;
 848         t->rcu_read_lock_nesting = 1;
 849         __rcu_read_unlock();
 850 }
 851
 852 #else /* #ifdef CONFIG_TINY_PREEMPT_RCU */
 853
 854 #ifdef CONFIG_RCU_TRACE
 855
 856 /*
 857  * Because preemptible RCU does not exist, it is not necessary to
 858  * dump out its statistics.
 859  */
 860 static void show_tiny_preempt_stats(struct seq_file *m)
 861 {
 862 }
 863
 864 #endif /* #ifdef CONFIG_RCU_TRACE */
 865
 866 /*
 867  * Because preemptible RCU does not exist, it is never necessary to
 868  * boost preempted RCU readers.
 869  */
 870 static int rcu_boost(void)
 871 {
 872         return 0;
 873 }
 874
 875 /*
 876  * Because preemptible RCU does not exist, it never has any callbacks
 877  * to check.
 878  */
 879 static void rcu_preempt_check_callbacks(void)
 880 {
 881 }
 882
 883 /*
 884  * Because preemptible RCU does not exist, it never has any callbacks
 885  * to remove.
 886  */
 887 static void rcu_preempt_remove_callbacks(struct rcu_ctrlblk *rcp)
 888 {
 889 }
 890
 891 /*
 892  * Because preemptible RCU does not exist, it never has any callbacks
 893  * to process.
 894  */
 895 static void rcu_preempt_process_callbacks(void)
 896 {
 897 }
 898
 899 #endif /* #else #ifdef CONFIG_TINY_PREEMPT_RCU */
 900
 901 #ifdef CONFIG_DEBUG_LOCK_ALLOC
 902 #include <linux/kernel_stat.h>
 903
 904 /*
 905  * During boot, we forgive RCU lockdep issues.  After this function is
 906  * invoked, we start taking RCU lockdep issues seriously.
 907  */
 908 void __init rcu_scheduler_starting(void)
 909 {
 910         WARN_ON(nr_context_switches() > 0);
 911         rcu_scheduler_active = 1;
 912 }
 913
 914 #endif /* #ifdef CONFIG_DEBUG_LOCK_ALLOC */
 915
 916 #ifdef CONFIG_RCU_BOOST
 917 #define RCU_BOOST_PRIO CONFIG_RCU_BOOST_PRIO
 918 #else /* #ifdef CONFIG_RCU_BOOST */
 919 #define RCU_BOOST_PRIO 1
 920 #endif /* #else #ifdef CONFIG_RCU_BOOST */
 921
 922 #ifdef CONFIG_RCU_TRACE
 923
 924 #ifdef CONFIG_RCU_BOOST
 925
 926 static void rcu_initiate_boost_trace(void)
 927 {
 928         if (list_empty(&rcu_preempt_ctrlblk.blkd_tasks))
 929                 rcu_preempt_ctrlblk.n_balk_blkd_tasks++;
 930         else if (rcu_preempt_ctrlblk.gp_tasks == NULL &&
 931                  rcu_preempt_ctrlblk.exp_tasks == NULL)
 932                 rcu_preempt_ctrlblk.n_balk_exp_gp_tasks++;
 933         else if (rcu_preempt_ctrlblk.boost_tasks != NULL)
 934                 rcu_preempt_ctrlblk.n_balk_boost_tasks++;
 935         else if (!ULONG_CMP_GE(jiffies, rcu_preempt_ctrlblk.boost_time))
 936                 rcu_preempt_ctrlblk.n_balk_notyet++;
 937         else
 938                 rcu_preempt_ctrlblk.n_balk_nos++;
 939 }
 940
 941 #endif /* #ifdef CONFIG_RCU_BOOST */
 942
 943 static void rcu_trace_sub_qlen(struct rcu_ctrlblk *rcp, int n)
 944 {
 945         unsigned long flags;
 946
 947         raw_local_irq_save(flags);
 948         rcp->qlen -= n;
 949         raw_local_irq_restore(flags);
 950 }
 951
 952 /*
 953  * Dump statistics for TINY_RCU, such as they are.
 954  */
 955 static int show_tiny_stats(struct seq_file *m, void *unused)
 956 {
 957         show_tiny_preempt_stats(m);
 958         seq_printf(m, "rcu_sched: qlen: %ld\n", rcu_sched_ctrlblk.qlen);
 959         seq_printf(m, "rcu_bh: qlen: %ld\n", rcu_bh_ctrlblk.qlen);
 960         return 0;
 961 }
 962
 963 static int show_tiny_stats_open(struct inode *inode, struct file *file)
 964 {
 965         return single_open(file, show_tiny_stats, NULL);
 966 }
 967
 968 static const struct file_operations show_tiny_stats_fops = {
 969         .owner = THIS_MODULE,
 970         .open = show_tiny_stats_open,
 971         .read = seq_read,
 972         .llseek = seq_lseek,
 973         .release = single_release,
 974 };
 975
 976 static struct dentry *rcudir;
 977
 978 static int __init rcutiny_trace_init(void)
 979 {
 980         struct dentry *retval;
 981
 982         rcudir = debugfs_create_dir("rcu", NULL);
 983         if (!rcudir)
 984                 goto free_out;
 985         retval = debugfs_create_file("rcudata", 0444, rcudir,
 986                                      NULL, &show_tiny_stats_fops);
 987         if (!retval)
 988                 goto free_out;
 989         return 0;
 990 free_out:
 991         debugfs_remove_recursive(rcudir);
 992         return 1;
 993 }
 994
 995 static void __exit rcutiny_trace_cleanup(void)
 996 {
 997         debugfs_remove_recursive(rcudir);
 998 }
 999
1000 module_init(rcutiny_trace_init);
1001 module_exit(rcutiny_trace_cleanup);
1002
1003 MODULE_AUTHOR("Paul E. McKenney");
1004 MODULE_DESCRIPTION("Read-Copy Update tracing for tiny implementation");
1005 MODULE_LICENSE("GPL");
1006
1007 #endif /* #ifdef CONFIG_RCU_TRACE */