linux/kernel/rcutree_plugin.h
<<
>>
Prefs
   1/*
   2 * Read-Copy Update mechanism for mutual exclusion (tree-based version)
   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 Red Hat, 2009
  21 * Copyright IBM Corporation, 2009
  22 *
  23 * Author: Ingo Molnar <mingo@elte.hu>
  24 *         Paul E. McKenney <paulmck@linux.vnet.ibm.com>
  25 */
  26
  27#include <linux/delay.h>
  28#include <linux/gfp.h>
  29#include <linux/oom.h>
  30#include <linux/smpboot.h>
  31#include "time/tick-internal.h"
  32
  33#define RCU_KTHREAD_PRIO 1
  34
  35#ifdef CONFIG_RCU_BOOST
  36#define RCU_BOOST_PRIO CONFIG_RCU_BOOST_PRIO
  37#else
  38#define RCU_BOOST_PRIO RCU_KTHREAD_PRIO
  39#endif
  40
  41#ifdef CONFIG_RCU_NOCB_CPU
  42static cpumask_var_t rcu_nocb_mask; /* CPUs to have callbacks offloaded. */
  43static bool have_rcu_nocb_mask;     /* Was rcu_nocb_mask allocated? */
  44static bool __read_mostly rcu_nocb_poll;    /* Offload kthread are to poll. */
  45static char __initdata nocb_buf[NR_CPUS * 5];
  46#endif /* #ifdef CONFIG_RCU_NOCB_CPU */
  47
  48/*
  49 * Check the RCU kernel configuration parameters and print informative
  50 * messages about anything out of the ordinary.  If you like #ifdef, you
  51 * will love this function.
  52 */
  53static void __init rcu_bootup_announce_oddness(void)
  54{
  55#ifdef CONFIG_RCU_TRACE
  56        pr_info("\tRCU debugfs-based tracing is enabled.\n");
  57#endif
  58#if (defined(CONFIG_64BIT) && CONFIG_RCU_FANOUT != 64) || (!defined(CONFIG_64BIT) && CONFIG_RCU_FANOUT != 32)
  59        pr_info("\tCONFIG_RCU_FANOUT set to non-default value of %d\n",
  60               CONFIG_RCU_FANOUT);
  61#endif
  62#ifdef CONFIG_RCU_FANOUT_EXACT
  63        pr_info("\tHierarchical RCU autobalancing is disabled.\n");
  64#endif
  65#ifdef CONFIG_RCU_FAST_NO_HZ
  66        pr_info("\tRCU dyntick-idle grace-period acceleration is enabled.\n");
  67#endif
  68#ifdef CONFIG_PROVE_RCU
  69        pr_info("\tRCU lockdep checking is enabled.\n");
  70#endif
  71#ifdef CONFIG_RCU_TORTURE_TEST_RUNNABLE
  72        pr_info("\tRCU torture testing starts during boot.\n");
  73#endif
  74#if defined(CONFIG_TREE_PREEMPT_RCU) && !defined(CONFIG_RCU_CPU_STALL_VERBOSE)
  75        pr_info("\tDump stacks of tasks blocking RCU-preempt GP.\n");
  76#endif
  77#if defined(CONFIG_RCU_CPU_STALL_INFO)
  78        pr_info("\tAdditional per-CPU info printed with stalls.\n");
  79#endif
  80#if NUM_RCU_LVL_4 != 0
  81        pr_info("\tFour-level hierarchy is enabled.\n");
  82#endif
  83        if (rcu_fanout_leaf != CONFIG_RCU_FANOUT_LEAF)
  84                pr_info("\tBoot-time adjustment of leaf fanout to %d.\n", rcu_fanout_leaf);
  85        if (nr_cpu_ids != NR_CPUS)
  86                pr_info("\tRCU restricting CPUs from NR_CPUS=%d to nr_cpu_ids=%d.\n", NR_CPUS, nr_cpu_ids);
  87#ifdef CONFIG_RCU_NOCB_CPU
  88#ifndef CONFIG_RCU_NOCB_CPU_NONE
  89        if (!have_rcu_nocb_mask) {
  90                zalloc_cpumask_var(&rcu_nocb_mask, GFP_KERNEL);
  91                have_rcu_nocb_mask = true;
  92        }
  93#ifdef CONFIG_RCU_NOCB_CPU_ZERO
  94        pr_info("\tOffload RCU callbacks from CPU 0\n");
  95        cpumask_set_cpu(0, rcu_nocb_mask);
  96#endif /* #ifdef CONFIG_RCU_NOCB_CPU_ZERO */
  97#ifdef CONFIG_RCU_NOCB_CPU_ALL
  98        pr_info("\tOffload RCU callbacks from all CPUs\n");
  99        cpumask_setall(rcu_nocb_mask);
 100#endif /* #ifdef CONFIG_RCU_NOCB_CPU_ALL */
 101#endif /* #ifndef CONFIG_RCU_NOCB_CPU_NONE */
 102        if (have_rcu_nocb_mask) {
 103                cpulist_scnprintf(nocb_buf, sizeof(nocb_buf), rcu_nocb_mask);
 104                pr_info("\tOffload RCU callbacks from CPUs: %s.\n", nocb_buf);
 105                if (rcu_nocb_poll)
 106                        pr_info("\tPoll for callbacks from no-CBs CPUs.\n");
 107        }
 108#endif /* #ifdef CONFIG_RCU_NOCB_CPU */
 109}
 110
 111#ifdef CONFIG_TREE_PREEMPT_RCU
 112
 113RCU_STATE_INITIALIZER(rcu_preempt, 'p', call_rcu);
 114static struct rcu_state *rcu_state = &rcu_preempt_state;
 115
 116static int rcu_preempted_readers_exp(struct rcu_node *rnp);
 117
 118/*
 119 * Tell them what RCU they are running.
 120 */
 121static void __init rcu_bootup_announce(void)
 122{
 123        pr_info("Preemptible hierarchical RCU implementation.\n");
 124        rcu_bootup_announce_oddness();
 125}
 126
 127/*
 128 * Return the number of RCU-preempt batches processed thus far
 129 * for debug and statistics.
 130 */
 131long rcu_batches_completed_preempt(void)
 132{
 133        return rcu_preempt_state.completed;
 134}
 135EXPORT_SYMBOL_GPL(rcu_batches_completed_preempt);
 136
 137/*
 138 * Return the number of RCU batches processed thus far for debug & stats.
 139 */
 140long rcu_batches_completed(void)
 141{
 142        return rcu_batches_completed_preempt();
 143}
 144EXPORT_SYMBOL_GPL(rcu_batches_completed);
 145
 146/*
 147 * Force a quiescent state for preemptible RCU.
 148 */
 149void rcu_force_quiescent_state(void)
 150{
 151        force_quiescent_state(&rcu_preempt_state);
 152}
 153EXPORT_SYMBOL_GPL(rcu_force_quiescent_state);
 154
 155/*
 156 * Record a preemptible-RCU quiescent state for the specified CPU.  Note
 157 * that this just means that the task currently running on the CPU is
 158 * not in a quiescent state.  There might be any number of tasks blocked
 159 * while in an RCU read-side critical section.
 160 *
 161 * Unlike the other rcu_*_qs() functions, callers to this function
 162 * must disable irqs in order to protect the assignment to
 163 * ->rcu_read_unlock_special.
 164 */
 165static void rcu_preempt_qs(int cpu)
 166{
 167        struct rcu_data *rdp = &per_cpu(rcu_preempt_data, cpu);
 168
 169        if (rdp->passed_quiesce == 0)
 170                trace_rcu_grace_period(TPS("rcu_preempt"), rdp->gpnum, TPS("cpuqs"));
 171        rdp->passed_quiesce = 1;
 172        current->rcu_read_unlock_special &= ~RCU_READ_UNLOCK_NEED_QS;
 173}
 174
 175/*
 176 * We have entered the scheduler, and the current task might soon be
 177 * context-switched away from.  If this task is in an RCU read-side
 178 * critical section, we will no longer be able to rely on the CPU to
 179 * record that fact, so we enqueue the task on the blkd_tasks list.
 180 * The task will dequeue itself when it exits the outermost enclosing
 181 * RCU read-side critical section.  Therefore, the current grace period
 182 * cannot be permitted to complete until the blkd_tasks list entries
 183 * predating the current grace period drain, in other words, until
 184 * rnp->gp_tasks becomes NULL.
 185 *
 186 * Caller must disable preemption.
 187 */
 188static void rcu_preempt_note_context_switch(int cpu)
 189{
 190        struct task_struct *t = current;
 191        unsigned long flags;
 192        struct rcu_data *rdp;
 193        struct rcu_node *rnp;
 194
 195        if (t->rcu_read_lock_nesting > 0 &&
 196            (t->rcu_read_unlock_special & RCU_READ_UNLOCK_BLOCKED) == 0) {
 197
 198                /* Possibly blocking in an RCU read-side critical section. */
 199                rdp = per_cpu_ptr(rcu_preempt_state.rda, cpu);
 200                rnp = rdp->mynode;
 201                raw_spin_lock_irqsave(&rnp->lock, flags);
 202                t->rcu_read_unlock_special |= RCU_READ_UNLOCK_BLOCKED;
 203                t->rcu_blocked_node = rnp;
 204
 205                /*
 206                 * If this CPU has already checked in, then this task
 207                 * will hold up the next grace period rather than the
 208                 * current grace period.  Queue the task accordingly.
 209                 * If the task is queued for the current grace period
 210                 * (i.e., this CPU has not yet passed through a quiescent
 211                 * state for the current grace period), then as long
 212                 * as that task remains queued, the current grace period
 213                 * cannot end.  Note that there is some uncertainty as
 214                 * to exactly when the current grace period started.
 215                 * We take a conservative approach, which can result
 216                 * in unnecessarily waiting on tasks that started very
 217                 * slightly after the current grace period began.  C'est
 218                 * la vie!!!
 219                 *
 220                 * But first, note that the current CPU must still be
 221                 * on line!
 222                 */
 223                WARN_ON_ONCE((rdp->grpmask & rnp->qsmaskinit) == 0);
 224                WARN_ON_ONCE(!list_empty(&t->rcu_node_entry));
 225                if ((rnp->qsmask & rdp->grpmask) && rnp->gp_tasks != NULL) {
 226                        list_add(&t->rcu_node_entry, rnp->gp_tasks->prev);
 227                        rnp->gp_tasks = &t->rcu_node_entry;
 228#ifdef CONFIG_RCU_BOOST
 229                        if (rnp->boost_tasks != NULL)
 230                                rnp->boost_tasks = rnp->gp_tasks;
 231#endif /* #ifdef CONFIG_RCU_BOOST */
 232                } else {
 233                        list_add(&t->rcu_node_entry, &rnp->blkd_tasks);
 234                        if (rnp->qsmask & rdp->grpmask)
 235                                rnp->gp_tasks = &t->rcu_node_entry;
 236                }
 237                trace_rcu_preempt_task(rdp->rsp->name,
 238                                       t->pid,
 239                                       (rnp->qsmask & rdp->grpmask)
 240                                       ? rnp->gpnum
 241                                       : rnp->gpnum + 1);
 242                raw_spin_unlock_irqrestore(&rnp->lock, flags);
 243        } else if (t->rcu_read_lock_nesting < 0 &&
 244                   t->rcu_read_unlock_special) {
 245
 246                /*
 247                 * Complete exit from RCU read-side critical section on
 248                 * behalf of preempted instance of __rcu_read_unlock().
 249                 */
 250                rcu_read_unlock_special(t);
 251        }
 252
 253        /*
 254         * Either we were not in an RCU read-side critical section to
 255         * begin with, or we have now recorded that critical section
 256         * globally.  Either way, we can now note a quiescent state
 257         * for this CPU.  Again, if we were in an RCU read-side critical
 258         * section, and if that critical section was blocking the current
 259         * grace period, then the fact that the task has been enqueued
 260         * means that we continue to block the current grace period.
 261         */
 262        local_irq_save(flags);
 263        rcu_preempt_qs(cpu);
 264        local_irq_restore(flags);
 265}
 266
 267/*
 268 * Check for preempted RCU readers blocking the current grace period
 269 * for the specified rcu_node structure.  If the caller needs a reliable
 270 * answer, it must hold the rcu_node's ->lock.
 271 */
 272static int rcu_preempt_blocked_readers_cgp(struct rcu_node *rnp)
 273{
 274        return rnp->gp_tasks != NULL;
 275}
 276
 277/*
 278 * Record a quiescent state for all tasks that were previously queued
 279 * on the specified rcu_node structure and that were blocking the current
 280 * RCU grace period.  The caller must hold the specified rnp->lock with
 281 * irqs disabled, and this lock is released upon return, but irqs remain
 282 * disabled.
 283 */
 284static void rcu_report_unblock_qs_rnp(struct rcu_node *rnp, unsigned long flags)
 285        __releases(rnp->lock)
 286{
 287        unsigned long mask;
 288        struct rcu_node *rnp_p;
 289
 290        if (rnp->qsmask != 0 || rcu_preempt_blocked_readers_cgp(rnp)) {
 291                raw_spin_unlock_irqrestore(&rnp->lock, flags);
 292                return;  /* Still need more quiescent states! */
 293        }
 294
 295        rnp_p = rnp->parent;
 296        if (rnp_p == NULL) {
 297                /*
 298                 * Either there is only one rcu_node in the tree,
 299                 * or tasks were kicked up to root rcu_node due to
 300                 * CPUs going offline.
 301                 */
 302                rcu_report_qs_rsp(&rcu_preempt_state, flags);
 303                return;
 304        }
 305
 306        /* Report up the rest of the hierarchy. */
 307        mask = rnp->grpmask;
 308        raw_spin_unlock(&rnp->lock);    /* irqs remain disabled. */
 309        raw_spin_lock(&rnp_p->lock);    /* irqs already disabled. */
 310        rcu_report_qs_rnp(mask, &rcu_preempt_state, rnp_p, flags);
 311}
 312
 313/*
 314 * Advance a ->blkd_tasks-list pointer to the next entry, instead
 315 * returning NULL if at the end of the list.
 316 */
 317static struct list_head *rcu_next_node_entry(struct task_struct *t,
 318                                             struct rcu_node *rnp)
 319{
 320        struct list_head *np;
 321
 322        np = t->rcu_node_entry.next;
 323        if (np == &rnp->blkd_tasks)
 324                np = NULL;
 325        return np;
 326}
 327
 328/*
 329 * Handle special cases during rcu_read_unlock(), such as needing to
 330 * notify RCU core processing or task having blocked during the RCU
 331 * read-side critical section.
 332 */
 333void rcu_read_unlock_special(struct task_struct *t)
 334{
 335        int empty;
 336        int empty_exp;
 337        int empty_exp_now;
 338        unsigned long flags;
 339        struct list_head *np;
 340#ifdef CONFIG_RCU_BOOST
 341        struct rt_mutex *rbmp = NULL;
 342#endif /* #ifdef CONFIG_RCU_BOOST */
 343        struct rcu_node *rnp;
 344        int special;
 345
 346        /* NMI handlers cannot block and cannot safely manipulate state. */
 347        if (in_nmi())
 348                return;
 349
 350        local_irq_save(flags);
 351
 352        /*
 353         * If RCU core is waiting for this CPU to exit critical section,
 354         * let it know that we have done so.
 355         */
 356        special = t->rcu_read_unlock_special;
 357        if (special & RCU_READ_UNLOCK_NEED_QS) {
 358                rcu_preempt_qs(smp_processor_id());
 359        }
 360
 361        /* Hardware IRQ handlers cannot block. */
 362        if (in_irq() || in_serving_softirq()) {
 363                local_irq_restore(flags);
 364                return;
 365        }
 366
 367        /* Clean up if blocked during RCU read-side critical section. */
 368        if (special & RCU_READ_UNLOCK_BLOCKED) {
 369                t->rcu_read_unlock_special &= ~RCU_READ_UNLOCK_BLOCKED;
 370
 371                /*
 372                 * Remove this task from the list it blocked on.  The
 373                 * task can migrate while we acquire the lock, but at
 374                 * most one time.  So at most two passes through loop.
 375                 */
 376                for (;;) {
 377                        rnp = t->rcu_blocked_node;
 378                        raw_spin_lock(&rnp->lock);  /* irqs already disabled. */
 379                        if (rnp == t->rcu_blocked_node)
 380                                break;
 381                        raw_spin_unlock(&rnp->lock); /* irqs remain disabled. */
 382                }
 383                empty = !rcu_preempt_blocked_readers_cgp(rnp);
 384                empty_exp = !rcu_preempted_readers_exp(rnp);
 385                smp_mb(); /* ensure expedited fastpath sees end of RCU c-s. */
 386                np = rcu_next_node_entry(t, rnp);
 387                list_del_init(&t->rcu_node_entry);
 388                t->rcu_blocked_node = NULL;
 389                trace_rcu_unlock_preempted_task(TPS("rcu_preempt"),
 390                                                rnp->gpnum, t->pid);
 391                if (&t->rcu_node_entry == rnp->gp_tasks)
 392                        rnp->gp_tasks = np;
 393                if (&t->rcu_node_entry == rnp->exp_tasks)
 394                        rnp->exp_tasks = np;
 395#ifdef CONFIG_RCU_BOOST
 396                if (&t->rcu_node_entry == rnp->boost_tasks)
 397                        rnp->boost_tasks = np;
 398                /* Snapshot/clear ->rcu_boost_mutex with rcu_node lock held. */
 399                if (t->rcu_boost_mutex) {
 400                        rbmp = t->rcu_boost_mutex;
 401                        t->rcu_boost_mutex = NULL;
 402                }
 403#endif /* #ifdef CONFIG_RCU_BOOST */
 404
 405                /*
 406                 * If this was the last task on the current list, and if
 407                 * we aren't waiting on any CPUs, report the quiescent state.
 408                 * Note that rcu_report_unblock_qs_rnp() releases rnp->lock,
 409                 * so we must take a snapshot of the expedited state.
 410                 */
 411                empty_exp_now = !rcu_preempted_readers_exp(rnp);
 412                if (!empty && !rcu_preempt_blocked_readers_cgp(rnp)) {
 413                        trace_rcu_quiescent_state_report(TPS("preempt_rcu"),
 414                                                         rnp->gpnum,
 415                                                         0, rnp->qsmask,
 416                                                         rnp->level,
 417                                                         rnp->grplo,
 418                                                         rnp->grphi,
 419                                                         !!rnp->gp_tasks);
 420                        rcu_report_unblock_qs_rnp(rnp, flags);
 421                } else {
 422                        raw_spin_unlock_irqrestore(&rnp->lock, flags);
 423                }
 424
 425#ifdef CONFIG_RCU_BOOST
 426                /* Unboost if we were boosted. */
 427                if (rbmp)
 428                        rt_mutex_unlock(rbmp);
 429#endif /* #ifdef CONFIG_RCU_BOOST */
 430
 431                /*
 432                 * If this was the last task on the expedited lists,
 433                 * then we need to report up the rcu_node hierarchy.
 434                 */
 435                if (!empty_exp && empty_exp_now)
 436                        rcu_report_exp_rnp(&rcu_preempt_state, rnp, true);
 437        } else {
 438                local_irq_restore(flags);
 439        }
 440}
 441
 442#ifdef CONFIG_RCU_CPU_STALL_VERBOSE
 443
 444/*
 445 * Dump detailed information for all tasks blocking the current RCU
 446 * grace period on the specified rcu_node structure.
 447 */
 448static void rcu_print_detail_task_stall_rnp(struct rcu_node *rnp)
 449{
 450        unsigned long flags;
 451        struct task_struct *t;
 452
 453        raw_spin_lock_irqsave(&rnp->lock, flags);
 454        if (!rcu_preempt_blocked_readers_cgp(rnp)) {
 455                raw_spin_unlock_irqrestore(&rnp->lock, flags);
 456                return;
 457        }
 458        t = list_entry(rnp->gp_tasks,
 459                       struct task_struct, rcu_node_entry);
 460        list_for_each_entry_continue(t, &rnp->blkd_tasks, rcu_node_entry)
 461                sched_show_task(t);
 462        raw_spin_unlock_irqrestore(&rnp->lock, flags);
 463}
 464
 465/*
 466 * Dump detailed information for all tasks blocking the current RCU
 467 * grace period.
 468 */
 469static void rcu_print_detail_task_stall(struct rcu_state *rsp)
 470{
 471        struct rcu_node *rnp = rcu_get_root(rsp);
 472
 473        rcu_print_detail_task_stall_rnp(rnp);
 474        rcu_for_each_leaf_node(rsp, rnp)
 475                rcu_print_detail_task_stall_rnp(rnp);
 476}
 477
 478#else /* #ifdef CONFIG_RCU_CPU_STALL_VERBOSE */
 479
 480static void rcu_print_detail_task_stall(struct rcu_state *rsp)
 481{
 482}
 483
 484#endif /* #else #ifdef CONFIG_RCU_CPU_STALL_VERBOSE */
 485
 486#ifdef CONFIG_RCU_CPU_STALL_INFO
 487
 488static void rcu_print_task_stall_begin(struct rcu_node *rnp)
 489{
 490        pr_err("\tTasks blocked on level-%d rcu_node (CPUs %d-%d):",
 491               rnp->level, rnp->grplo, rnp->grphi);
 492}
 493
 494static void rcu_print_task_stall_end(void)
 495{
 496        pr_cont("\n");
 497}
 498
 499#else /* #ifdef CONFIG_RCU_CPU_STALL_INFO */
 500
 501static void rcu_print_task_stall_begin(struct rcu_node *rnp)
 502{
 503}
 504
 505static void rcu_print_task_stall_end(void)
 506{
 507}
 508
 509#endif /* #else #ifdef CONFIG_RCU_CPU_STALL_INFO */
 510
 511/*
 512 * Scan the current list of tasks blocked within RCU read-side critical
 513 * sections, printing out the tid of each.
 514 */
 515static int rcu_print_task_stall(struct rcu_node *rnp)
 516{
 517        struct task_struct *t;
 518        int ndetected = 0;
 519
 520        if (!rcu_preempt_blocked_readers_cgp(rnp))
 521                return 0;
 522        rcu_print_task_stall_begin(rnp);
 523        t = list_entry(rnp->gp_tasks,
 524                       struct task_struct, rcu_node_entry);
 525        list_for_each_entry_continue(t, &rnp->blkd_tasks, rcu_node_entry) {
 526                pr_cont(" P%d", t->pid);
 527                ndetected++;
 528        }
 529        rcu_print_task_stall_end();
 530        return ndetected;
 531}
 532
 533/*
 534 * Check that the list of blocked tasks for the newly completed grace
 535 * period is in fact empty.  It is a serious bug to complete a grace
 536 * period that still has RCU readers blocked!  This function must be
 537 * invoked -before- updating this rnp's ->gpnum, and the rnp's ->lock
 538 * must be held by the caller.
 539 *
 540 * Also, if there are blocked tasks on the list, they automatically
 541 * block the newly created grace period, so set up ->gp_tasks accordingly.
 542 */
 543static void rcu_preempt_check_blocked_tasks(struct rcu_node *rnp)
 544{
 545        WARN_ON_ONCE(rcu_preempt_blocked_readers_cgp(rnp));
 546        if (!list_empty(&rnp->blkd_tasks))
 547                rnp->gp_tasks = rnp->blkd_tasks.next;
 548        WARN_ON_ONCE(rnp->qsmask);
 549}
 550
 551#ifdef CONFIG_HOTPLUG_CPU
 552
 553/*
 554 * Handle tasklist migration for case in which all CPUs covered by the
 555 * specified rcu_node have gone offline.  Move them up to the root
 556 * rcu_node.  The reason for not just moving them to the immediate
 557 * parent is to remove the need for rcu_read_unlock_special() to
 558 * make more than two attempts to acquire the target rcu_node's lock.
 559 * Returns true if there were tasks blocking the current RCU grace
 560 * period.
 561 *
 562 * Returns 1 if there was previously a task blocking the current grace
 563 * period on the specified rcu_node structure.
 564 *
 565 * The caller must hold rnp->lock with irqs disabled.
 566 */
 567static int rcu_preempt_offline_tasks(struct rcu_state *rsp,
 568                                     struct rcu_node *rnp,
 569                                     struct rcu_data *rdp)
 570{
 571        struct list_head *lp;
 572        struct list_head *lp_root;
 573        int retval = 0;
 574        struct rcu_node *rnp_root = rcu_get_root(rsp);
 575        struct task_struct *t;
 576
 577        if (rnp == rnp_root) {
 578                WARN_ONCE(1, "Last CPU thought to be offlined?");
 579                return 0;  /* Shouldn't happen: at least one CPU online. */
 580        }
 581
 582        /* If we are on an internal node, complain bitterly. */
 583        WARN_ON_ONCE(rnp != rdp->mynode);
 584
 585        /*
 586         * Move tasks up to root rcu_node.  Don't try to get fancy for
 587         * this corner-case operation -- just put this node's tasks
 588         * at the head of the root node's list, and update the root node's
 589         * ->gp_tasks and ->exp_tasks pointers to those of this node's,
 590         * if non-NULL.  This might result in waiting for more tasks than
 591         * absolutely necessary, but this is a good performance/complexity
 592         * tradeoff.
 593         */
 594        if (rcu_preempt_blocked_readers_cgp(rnp) && rnp->qsmask == 0)
 595                retval |= RCU_OFL_TASKS_NORM_GP;
 596        if (rcu_preempted_readers_exp(rnp))
 597                retval |= RCU_OFL_TASKS_EXP_GP;
 598        lp = &rnp->blkd_tasks;
 599        lp_root = &rnp_root->blkd_tasks;
 600        while (!list_empty(lp)) {
 601                t = list_entry(lp->next, typeof(*t), rcu_node_entry);
 602                raw_spin_lock(&rnp_root->lock); /* irqs already disabled */
 603                list_del(&t->rcu_node_entry);
 604                t->rcu_blocked_node = rnp_root;
 605                list_add(&t->rcu_node_entry, lp_root);
 606                if (&t->rcu_node_entry == rnp->gp_tasks)
 607                        rnp_root->gp_tasks = rnp->gp_tasks;
 608                if (&t->rcu_node_entry == rnp->exp_tasks)
 609                        rnp_root->exp_tasks = rnp->exp_tasks;
 610#ifdef CONFIG_RCU_BOOST
 611                if (&t->rcu_node_entry == rnp->boost_tasks)
 612                        rnp_root->boost_tasks = rnp->boost_tasks;
 613#endif /* #ifdef CONFIG_RCU_BOOST */
 614                raw_spin_unlock(&rnp_root->lock); /* irqs still disabled */
 615        }
 616
 617        rnp->gp_tasks = NULL;
 618        rnp->exp_tasks = NULL;
 619#ifdef CONFIG_RCU_BOOST
 620        rnp->boost_tasks = NULL;
 621        /*
 622         * In case root is being boosted and leaf was not.  Make sure
 623         * that we boost the tasks blocking the current grace period
 624         * in this case.
 625         */
 626        raw_spin_lock(&rnp_root->lock); /* irqs already disabled */
 627        if (rnp_root->boost_tasks != NULL &&
 628            rnp_root->boost_tasks != rnp_root->gp_tasks &&
 629            rnp_root->boost_tasks != rnp_root->exp_tasks)
 630                rnp_root->boost_tasks = rnp_root->gp_tasks;
 631        raw_spin_unlock(&rnp_root->lock); /* irqs still disabled */
 632#endif /* #ifdef CONFIG_RCU_BOOST */
 633
 634        return retval;
 635}
 636
 637#endif /* #ifdef CONFIG_HOTPLUG_CPU */
 638
 639/*
 640 * Check for a quiescent state from the current CPU.  When a task blocks,
 641 * the task is recorded in the corresponding CPU's rcu_node structure,
 642 * which is checked elsewhere.
 643 *
 644 * Caller must disable hard irqs.
 645 */
 646static void rcu_preempt_check_callbacks(int cpu)
 647{
 648        struct task_struct *t = current;
 649
 650        if (t->rcu_read_lock_nesting == 0) {
 651                rcu_preempt_qs(cpu);
 652                return;
 653        }
 654        if (t->rcu_read_lock_nesting > 0 &&
 655            per_cpu(rcu_preempt_data, cpu).qs_pending)
 656                t->rcu_read_unlock_special |= RCU_READ_UNLOCK_NEED_QS;
 657}
 658
 659#ifdef CONFIG_RCU_BOOST
 660
 661static void rcu_preempt_do_callbacks(void)
 662{
 663        rcu_do_batch(&rcu_preempt_state, &__get_cpu_var(rcu_preempt_data));
 664}
 665
 666#endif /* #ifdef CONFIG_RCU_BOOST */
 667
 668/*
 669 * Queue a preemptible-RCU callback for invocation after a grace period.
 670 */
 671void call_rcu(struct rcu_head *head, void (*func)(struct rcu_head *rcu))
 672{
 673        __call_rcu(head, func, &rcu_preempt_state, -1, 0);
 674}
 675EXPORT_SYMBOL_GPL(call_rcu);
 676
 677/*
 678 * Queue an RCU callback for lazy invocation after a grace period.
 679 * This will likely be later named something like "call_rcu_lazy()",
 680 * but this change will require some way of tagging the lazy RCU
 681 * callbacks in the list of pending callbacks.  Until then, this
 682 * function may only be called from __kfree_rcu().
 683 */
 684void kfree_call_rcu(struct rcu_head *head,
 685                    void (*func)(struct rcu_head *rcu))
 686{
 687        __call_rcu(head, func, &rcu_preempt_state, -1, 1);
 688}
 689EXPORT_SYMBOL_GPL(kfree_call_rcu);
 690
 691/**
 692 * synchronize_rcu - wait until a grace period has elapsed.
 693 *
 694 * Control will return to the caller some time after a full grace
 695 * period has elapsed, in other words after all currently executing RCU
 696 * read-side critical sections have completed.  Note, however, that
 697 * upon return from synchronize_rcu(), the caller might well be executing
 698 * concurrently with new RCU read-side critical sections that began while
 699 * synchronize_rcu() was waiting.  RCU read-side critical sections are
 700 * delimited by rcu_read_lock() and rcu_read_unlock(), and may be nested.
 701 *
 702 * See the description of synchronize_sched() for more detailed information
 703 * on memory ordering guarantees.
 704 */
 705void synchronize_rcu(void)
 706{
 707        rcu_lockdep_assert(!lock_is_held(&rcu_bh_lock_map) &&
 708                           !lock_is_held(&rcu_lock_map) &&
 709                           !lock_is_held(&rcu_sched_lock_map),
 710                           "Illegal synchronize_rcu() in RCU read-side critical section");
 711        if (!rcu_scheduler_active)
 712                return;
 713        if (rcu_expedited)
 714                synchronize_rcu_expedited();
 715        else
 716                wait_rcu_gp(call_rcu);
 717}
 718EXPORT_SYMBOL_GPL(synchronize_rcu);
 719
 720static DECLARE_WAIT_QUEUE_HEAD(sync_rcu_preempt_exp_wq);
 721static unsigned long sync_rcu_preempt_exp_count;
 722static DEFINE_MUTEX(sync_rcu_preempt_exp_mutex);
 723
 724/*
 725 * Return non-zero if there are any tasks in RCU read-side critical
 726 * sections blocking the current preemptible-RCU expedited grace period.
 727 * If there is no preemptible-RCU expedited grace period currently in
 728 * progress, returns zero unconditionally.
 729 */
 730static int rcu_preempted_readers_exp(struct rcu_node *rnp)
 731{
 732        return rnp->exp_tasks != NULL;
 733}
 734
 735/*
 736 * return non-zero if there is no RCU expedited grace period in progress
 737 * for the specified rcu_node structure, in other words, if all CPUs and
 738 * tasks covered by the specified rcu_node structure have done their bit
 739 * for the current expedited grace period.  Works only for preemptible
 740 * RCU -- other RCU implementation use other means.
 741 *
 742 * Caller must hold sync_rcu_preempt_exp_mutex.
 743 */
 744static int sync_rcu_preempt_exp_done(struct rcu_node *rnp)
 745{
 746        return !rcu_preempted_readers_exp(rnp) &&
 747               ACCESS_ONCE(rnp->expmask) == 0;
 748}
 749
 750/*
 751 * Report the exit from RCU read-side critical section for the last task
 752 * that queued itself during or before the current expedited preemptible-RCU
 753 * grace period.  This event is reported either to the rcu_node structure on
 754 * which the task was queued or to one of that rcu_node structure's ancestors,
 755 * recursively up the tree.  (Calm down, calm down, we do the recursion
 756 * iteratively!)
 757 *
 758 * Most callers will set the "wake" flag, but the task initiating the
 759 * expedited grace period need not wake itself.
 760 *
 761 * Caller must hold sync_rcu_preempt_exp_mutex.
 762 */
 763static void rcu_report_exp_rnp(struct rcu_state *rsp, struct rcu_node *rnp,
 764                               bool wake)
 765{
 766        unsigned long flags;
 767        unsigned long mask;
 768
 769        raw_spin_lock_irqsave(&rnp->lock, flags);
 770        for (;;) {
 771                if (!sync_rcu_preempt_exp_done(rnp)) {
 772                        raw_spin_unlock_irqrestore(&rnp->lock, flags);
 773                        break;
 774                }
 775                if (rnp->parent == NULL) {
 776                        raw_spin_unlock_irqrestore(&rnp->lock, flags);
 777                        if (wake)
 778                                wake_up(&sync_rcu_preempt_exp_wq);
 779                        break;
 780                }
 781                mask = rnp->grpmask;
 782                raw_spin_unlock(&rnp->lock); /* irqs remain disabled */
 783                rnp = rnp->parent;
 784                raw_spin_lock(&rnp->lock); /* irqs already disabled */
 785                rnp->expmask &= ~mask;
 786        }
 787}
 788
 789/*
 790 * Snapshot the tasks blocking the newly started preemptible-RCU expedited
 791 * grace period for the specified rcu_node structure.  If there are no such
 792 * tasks, report it up the rcu_node hierarchy.
 793 *
 794 * Caller must hold sync_rcu_preempt_exp_mutex and must exclude
 795 * CPU hotplug operations.
 796 */
 797static void
 798sync_rcu_preempt_exp_init(struct rcu_state *rsp, struct rcu_node *rnp)
 799{
 800        unsigned long flags;
 801        int must_wait = 0;
 802
 803        raw_spin_lock_irqsave(&rnp->lock, flags);
 804        if (list_empty(&rnp->blkd_tasks)) {
 805                raw_spin_unlock_irqrestore(&rnp->lock, flags);
 806        } else {
 807                rnp->exp_tasks = rnp->blkd_tasks.next;
 808                rcu_initiate_boost(rnp, flags);  /* releases rnp->lock */
 809                must_wait = 1;
 810        }
 811        if (!must_wait)
 812                rcu_report_exp_rnp(rsp, rnp, false); /* Don't wake self. */
 813}
 814
 815/**
 816 * synchronize_rcu_expedited - Brute-force RCU grace period
 817 *
 818 * Wait for an RCU-preempt grace period, but expedite it.  The basic
 819 * idea is to invoke synchronize_sched_expedited() to push all the tasks to
 820 * the ->blkd_tasks lists and wait for this list to drain.  This consumes
 821 * significant time on all CPUs and is unfriendly to real-time workloads,
 822 * so is thus not recommended for any sort of common-case code.
 823 * In fact, if you are using synchronize_rcu_expedited() in a loop,
 824 * please restructure your code to batch your updates, and then Use a
 825 * single synchronize_rcu() instead.
 826 *
 827 * Note that it is illegal to call this function while holding any lock
 828 * that is acquired by a CPU-hotplug notifier.  And yes, it is also illegal
 829 * to call this function from a CPU-hotplug notifier.  Failing to observe
 830 * these restriction will result in deadlock.
 831 */
 832void synchronize_rcu_expedited(void)
 833{
 834        unsigned long flags;
 835        struct rcu_node *rnp;
 836        struct rcu_state *rsp = &rcu_preempt_state;
 837        unsigned long snap;
 838        int trycount = 0;
 839
 840        smp_mb(); /* Caller's modifications seen first by other CPUs. */
 841        snap = ACCESS_ONCE(sync_rcu_preempt_exp_count) + 1;
 842        smp_mb(); /* Above access cannot bleed into critical section. */
 843
 844        /*
 845         * Block CPU-hotplug operations.  This means that any CPU-hotplug
 846         * operation that finds an rcu_node structure with tasks in the
 847         * process of being boosted will know that all tasks blocking
 848         * this expedited grace period will already be in the process of
 849         * being boosted.  This simplifies the process of moving tasks
 850         * from leaf to root rcu_node structures.
 851         */
 852        get_online_cpus();
 853
 854        /*
 855         * Acquire lock, falling back to synchronize_rcu() if too many
 856         * lock-acquisition failures.  Of course, if someone does the
 857         * expedited grace period for us, just leave.
 858         */
 859        while (!mutex_trylock(&sync_rcu_preempt_exp_mutex)) {
 860                if (ULONG_CMP_LT(snap,
 861                    ACCESS_ONCE(sync_rcu_preempt_exp_count))) {
 862                        put_online_cpus();
 863                        goto mb_ret; /* Others did our work for us. */
 864                }
 865                if (trycount++ < 10) {
 866                        udelay(trycount * num_online_cpus());
 867                } else {
 868                        put_online_cpus();
 869                        wait_rcu_gp(call_rcu);
 870                        return;
 871                }
 872        }
 873        if (ULONG_CMP_LT(snap, ACCESS_ONCE(sync_rcu_preempt_exp_count))) {
 874                put_online_cpus();
 875                goto unlock_mb_ret; /* Others did our work for us. */
 876        }
 877
 878        /* force all RCU readers onto ->blkd_tasks lists. */
 879        synchronize_sched_expedited();
 880
 881        /* Initialize ->expmask for all non-leaf rcu_node structures. */
 882        rcu_for_each_nonleaf_node_breadth_first(rsp, rnp) {
 883                raw_spin_lock_irqsave(&rnp->lock, flags);
 884                rnp->expmask = rnp->qsmaskinit;
 885                raw_spin_unlock_irqrestore(&rnp->lock, flags);
 886        }
 887
 888        /* Snapshot current state of ->blkd_tasks lists. */
 889        rcu_for_each_leaf_node(rsp, rnp)
 890                sync_rcu_preempt_exp_init(rsp, rnp);
 891        if (NUM_RCU_NODES > 1)
 892                sync_rcu_preempt_exp_init(rsp, rcu_get_root(rsp));
 893
 894        put_online_cpus();
 895
 896        /* Wait for snapshotted ->blkd_tasks lists to drain. */
 897        rnp = rcu_get_root(rsp);
 898        wait_event(sync_rcu_preempt_exp_wq,
 899                   sync_rcu_preempt_exp_done(rnp));
 900
 901        /* Clean up and exit. */
 902        smp_mb(); /* ensure expedited GP seen before counter increment. */
 903        ACCESS_ONCE(sync_rcu_preempt_exp_count)++;
 904unlock_mb_ret:
 905        mutex_unlock(&sync_rcu_preempt_exp_mutex);
 906mb_ret:
 907        smp_mb(); /* ensure subsequent action seen after grace period. */
 908}
 909EXPORT_SYMBOL_GPL(synchronize_rcu_expedited);
 910
 911/**
 912 * rcu_barrier - Wait until all in-flight call_rcu() callbacks complete.
 913 *
 914 * Note that this primitive does not necessarily wait for an RCU grace period
 915 * to complete.  For example, if there are no RCU callbacks queued anywhere
 916 * in the system, then rcu_barrier() is within its rights to return
 917 * immediately, without waiting for anything, much less an RCU grace period.
 918 */
 919void rcu_barrier(void)
 920{
 921        _rcu_barrier(&rcu_preempt_state);
 922}
 923EXPORT_SYMBOL_GPL(rcu_barrier);
 924
 925/*
 926 * Initialize preemptible RCU's state structures.
 927 */
 928static void __init __rcu_init_preempt(void)
 929{
 930        rcu_init_one(&rcu_preempt_state, &rcu_preempt_data);
 931}
 932
 933/*
 934 * Check for a task exiting while in a preemptible-RCU read-side
 935 * critical section, clean up if so.  No need to issue warnings,
 936 * as debug_check_no_locks_held() already does this if lockdep
 937 * is enabled.
 938 */
 939void exit_rcu(void)
 940{
 941        struct task_struct *t = current;
 942
 943        if (likely(list_empty(&current->rcu_node_entry)))
 944                return;
 945        t->rcu_read_lock_nesting = 1;
 946        barrier();
 947        t->rcu_read_unlock_special = RCU_READ_UNLOCK_BLOCKED;
 948        __rcu_read_unlock();
 949}
 950
 951#else /* #ifdef CONFIG_TREE_PREEMPT_RCU */
 952
 953static struct rcu_state *rcu_state = &rcu_sched_state;
 954
 955/*
 956 * Tell them what RCU they are running.
 957 */
 958static void __init rcu_bootup_announce(void)
 959{
 960        pr_info("Hierarchical RCU implementation.\n");
 961        rcu_bootup_announce_oddness();
 962}
 963
 964/*
 965 * Return the number of RCU batches processed thus far for debug & stats.
 966 */
 967long rcu_batches_completed(void)
 968{
 969        return rcu_batches_completed_sched();
 970}
 971EXPORT_SYMBOL_GPL(rcu_batches_completed);
 972
 973/*
 974 * Force a quiescent state for RCU, which, because there is no preemptible
 975 * RCU, becomes the same as rcu-sched.
 976 */
 977void rcu_force_quiescent_state(void)
 978{
 979        rcu_sched_force_quiescent_state();
 980}
 981EXPORT_SYMBOL_GPL(rcu_force_quiescent_state);
 982
 983/*
 984 * Because preemptible RCU does not exist, we never have to check for
 985 * CPUs being in quiescent states.
 986 */
 987static void rcu_preempt_note_context_switch(int cpu)
 988{
 989}
 990
 991/*
 992 * Because preemptible RCU does not exist, there are never any preempted
 993 * RCU readers.
 994 */
 995static int rcu_preempt_blocked_readers_cgp(struct rcu_node *rnp)
 996{
 997        return 0;
 998}
 999
1000#ifdef CONFIG_HOTPLUG_CPU
1001
1002/* Because preemptible RCU does not exist, no quieting of tasks. */
1003static void rcu_report_unblock_qs_rnp(struct rcu_node *rnp, unsigned long flags)
1004{
1005        raw_spin_unlock_irqrestore(&rnp->lock, flags);
1006}
1007
1008#endif /* #ifdef CONFIG_HOTPLUG_CPU */
1009
1010/*
1011 * Because preemptible RCU does not exist, we never have to check for
1012 * tasks blocked within RCU read-side critical sections.
1013 */
1014static void rcu_print_detail_task_stall(struct rcu_state *rsp)
1015{
1016}
1017
1018/*
1019 * Because preemptible RCU does not exist, we never have to check for
1020 * tasks blocked within RCU read-side critical sections.
1021 */
1022static int rcu_print_task_stall(struct rcu_node *rnp)
1023{
1024        return 0;
1025}
1026
1027/*
1028 * Because there is no preemptible RCU, there can be no readers blocked,
1029 * so there is no need to check for blocked tasks.  So check only for
1030 * bogus qsmask values.
1031 */
1032static void rcu_preempt_check_blocked_tasks(struct rcu_node *rnp)
1033{
1034        WARN_ON_ONCE(rnp->qsmask);
1035}
1036
1037#ifdef CONFIG_HOTPLUG_CPU
1038
1039/*
1040 * Because preemptible RCU does not exist, it never needs to migrate
1041 * tasks that were blocked within RCU read-side critical sections, and
1042 * such non-existent tasks cannot possibly have been blocking the current
1043 * grace period.
1044 */
1045static int rcu_preempt_offline_tasks(struct rcu_state *rsp,
1046                                     struct rcu_node *rnp,
1047                                     struct rcu_data *rdp)
1048{
1049        return 0;
1050}
1051
1052#endif /* #ifdef CONFIG_HOTPLUG_CPU */
1053
1054/*
1055 * Because preemptible RCU does not exist, it never has any callbacks
1056 * to check.
1057 */
1058static void rcu_preempt_check_callbacks(int cpu)
1059{
1060}
1061
1062/*
1063 * Queue an RCU callback for lazy invocation after a grace period.
1064 * This will likely be later named something like "call_rcu_lazy()",
1065 * but this change will require some way of tagging the lazy RCU
1066 * callbacks in the list of pending callbacks.  Until then, this
1067 * function may only be called from __kfree_rcu().
1068 *
1069 * Because there is no preemptible RCU, we use RCU-sched instead.
1070 */
1071void kfree_call_rcu(struct rcu_head *head,
1072                    void (*func)(struct rcu_head *rcu))
1073{
1074        __call_rcu(head, func, &rcu_sched_state, -1, 1);
1075}
1076EXPORT_SYMBOL_GPL(kfree_call_rcu);
1077
1078/*
1079 * Wait for an rcu-preempt grace period, but make it happen quickly.
1080 * But because preemptible RCU does not exist, map to rcu-sched.
1081 */
1082void synchronize_rcu_expedited(void)
1083{
1084        synchronize_sched_expedited();
1085}
1086EXPORT_SYMBOL_GPL(synchronize_rcu_expedited);
1087
1088#ifdef CONFIG_HOTPLUG_CPU
1089
1090/*
1091 * Because preemptible RCU does not exist, there is never any need to
1092 * report on tasks preempted in RCU read-side critical sections during
1093 * expedited RCU grace periods.
1094 */
1095static void rcu_report_exp_rnp(struct rcu_state *rsp, struct rcu_node *rnp,
1096                               bool wake)
1097{
1098}
1099
1100#endif /* #ifdef CONFIG_HOTPLUG_CPU */
1101
1102/*
1103 * Because preemptible RCU does not exist, rcu_barrier() is just
1104 * another name for rcu_barrier_sched().
1105 */
1106void rcu_barrier(void)
1107{
1108        rcu_barrier_sched();
1109}
1110EXPORT_SYMBOL_GPL(rcu_barrier);
1111
1112/*
1113 * Because preemptible RCU does not exist, it need not be initialized.
1114 */
1115static void __init __rcu_init_preempt(void)
1116{
1117}
1118
1119/*
1120 * Because preemptible RCU does not exist, tasks cannot possibly exit
1121 * while in preemptible RCU read-side critical sections.
1122 */
1123void exit_rcu(void)
1124{
1125}
1126
1127#endif /* #else #ifdef CONFIG_TREE_PREEMPT_RCU */
1128
1129#ifdef CONFIG_RCU_BOOST
1130
1131#include "rtmutex_common.h"
1132
1133#ifdef CONFIG_RCU_TRACE
1134
1135static void rcu_initiate_boost_trace(struct rcu_node *rnp)
1136{
1137        if (list_empty(&rnp->blkd_tasks))
1138                rnp->n_balk_blkd_tasks++;
1139        else if (rnp->exp_tasks == NULL && rnp->gp_tasks == NULL)
1140                rnp->n_balk_exp_gp_tasks++;
1141        else if (rnp->gp_tasks != NULL && rnp->boost_tasks != NULL)
1142                rnp->n_balk_boost_tasks++;
1143        else if (rnp->gp_tasks != NULL && rnp->qsmask != 0)
1144                rnp->n_balk_notblocked++;
1145        else if (rnp->gp_tasks != NULL &&
1146                 ULONG_CMP_LT(jiffies, rnp->boost_time))
1147                rnp->n_balk_notyet++;
1148        else
1149                rnp->n_balk_nos++;
1150}
1151
1152#else /* #ifdef CONFIG_RCU_TRACE */
1153
1154static void rcu_initiate_boost_trace(struct rcu_node *rnp)
1155{
1156}
1157
1158#endif /* #else #ifdef CONFIG_RCU_TRACE */
1159
1160static void rcu_wake_cond(struct task_struct *t, int status)
1161{
1162        /*
1163         * If the thread is yielding, only wake it when this
1164         * is invoked from idle
1165         */
1166        if (status != RCU_KTHREAD_YIELDING || is_idle_task(current))
1167                wake_up_process(t);
1168}
1169
1170/*
1171 * Carry out RCU priority boosting on the task indicated by ->exp_tasks
1172 * or ->boost_tasks, advancing the pointer to the next task in the
1173 * ->blkd_tasks list.
1174 *
1175 * Note that irqs must be enabled: boosting the task can block.
1176 * Returns 1 if there are more tasks needing to be boosted.
1177 */
1178static int rcu_boost(struct rcu_node *rnp)
1179{
1180        unsigned long flags;
1181        struct rt_mutex mtx;
1182        struct task_struct *t;
1183        struct list_head *tb;
1184
1185        if (rnp->exp_tasks == NULL && rnp->boost_tasks == NULL)
1186                return 0;  /* Nothing left to boost. */
1187
1188        raw_spin_lock_irqsave(&rnp->lock, flags);
1189
1190        /*
1191         * Recheck under the lock: all tasks in need of boosting
1192         * might exit their RCU read-side critical sections on their own.
1193         */
1194        if (rnp->exp_tasks == NULL && rnp->boost_tasks == NULL) {
1195                raw_spin_unlock_irqrestore(&rnp->lock, flags);
1196                return 0;
1197        }
1198
1199        /*
1200         * Preferentially boost tasks blocking expedited grace periods.
1201         * This cannot starve the normal grace periods because a second
1202         * expedited grace period must boost all blocked tasks, including
1203         * those blocking the pre-existing normal grace period.
1204         */
1205        if (rnp->exp_tasks != NULL) {
1206                tb = rnp->exp_tasks;
1207                rnp->n_exp_boosts++;
1208        } else {
1209                tb = rnp->boost_tasks;
1210                rnp->n_normal_boosts++;
1211        }
1212        rnp->n_tasks_boosted++;
1213
1214        /*
1215         * We boost task t by manufacturing an rt_mutex that appears to
1216         * be held by task t.  We leave a pointer to that rt_mutex where
1217         * task t can find it, and task t will release the mutex when it
1218         * exits its outermost RCU read-side critical section.  Then
1219         * simply acquiring this artificial rt_mutex will boost task
1220         * t's priority.  (Thanks to tglx for suggesting this approach!)
1221         *
1222         * Note that task t must acquire rnp->lock to remove itself from
1223         * the ->blkd_tasks list, which it will do from exit() if from
1224         * nowhere else.  We therefore are guaranteed that task t will
1225         * stay around at least until we drop rnp->lock.  Note that
1226         * rnp->lock also resolves races between our priority boosting
1227         * and task t's exiting its outermost RCU read-side critical
1228         * section.
1229         */
1230        t = container_of(tb, struct task_struct, rcu_node_entry);
1231        rt_mutex_init_proxy_locked(&mtx, t);
1232        t->rcu_boost_mutex = &mtx;
1233        raw_spin_unlock_irqrestore(&rnp->lock, flags);
1234        rt_mutex_lock(&mtx);  /* Side effect: boosts task t's priority. */
1235        rt_mutex_unlock(&mtx);  /* Keep lockdep happy. */
1236
1237        return ACCESS_ONCE(rnp->exp_tasks) != NULL ||
1238               ACCESS_ONCE(rnp->boost_tasks) != NULL;
1239}
1240
1241/*
1242 * Priority-boosting kthread.  One per leaf rcu_node and one for the
1243 * root rcu_node.
1244 */
1245static int rcu_boost_kthread(void *arg)
1246{
1247        struct rcu_node *rnp = (struct rcu_node *)arg;
1248        int spincnt = 0;
1249        int more2boost;
1250
1251        trace_rcu_utilization(TPS("Start boost kthread@init"));
1252        for (;;) {
1253                rnp->boost_kthread_status = RCU_KTHREAD_WAITING;
1254                trace_rcu_utilization(TPS("End boost kthread@rcu_wait"));
1255                rcu_wait(rnp->boost_tasks || rnp->exp_tasks);
1256                trace_rcu_utilization(TPS("Start boost kthread@rcu_wait"));
1257                rnp->boost_kthread_status = RCU_KTHREAD_RUNNING;
1258                more2boost = rcu_boost(rnp);
1259                if (more2boost)
1260                        spincnt++;
1261                else
1262                        spincnt = 0;
1263                if (spincnt > 10) {
1264                        rnp->boost_kthread_status = RCU_KTHREAD_YIELDING;
1265                        trace_rcu_utilization(TPS("End boost kthread@rcu_yield"));
1266                        schedule_timeout_interruptible(2);
1267                        trace_rcu_utilization(TPS("Start boost kthread@rcu_yield"));
1268                        spincnt = 0;
1269                }
1270        }
1271        /* NOTREACHED */
1272        trace_rcu_utilization(TPS("End boost kthread@notreached"));
1273        return 0;
1274}
1275
1276/*
1277 * Check to see if it is time to start boosting RCU readers that are
1278 * blocking the current grace period, and, if so, tell the per-rcu_node
1279 * kthread to start boosting them.  If there is an expedited grace
1280 * period in progress, it is always time to boost.
1281 *
1282 * The caller must hold rnp->lock, which this function releases.
1283 * The ->boost_kthread_task is immortal, so we don't need to worry
1284 * about it going away.
1285 */
1286static void rcu_initiate_boost(struct rcu_node *rnp, unsigned long flags)
1287{
1288        struct task_struct *t;
1289
1290        if (!rcu_preempt_blocked_readers_cgp(rnp) && rnp->exp_tasks == NULL) {
1291                rnp->n_balk_exp_gp_tasks++;
1292                raw_spin_unlock_irqrestore(&rnp->lock, flags);
1293                return;
1294        }
1295        if (rnp->exp_tasks != NULL ||
1296            (rnp->gp_tasks != NULL &&
1297             rnp->boost_tasks == NULL &&
1298             rnp->qsmask == 0 &&
1299             ULONG_CMP_GE(jiffies, rnp->boost_time))) {
1300                if (rnp->exp_tasks == NULL)
1301                        rnp->boost_tasks = rnp->gp_tasks;
1302                raw_spin_unlock_irqrestore(&rnp->lock, flags);
1303                t = rnp->boost_kthread_task;
1304                if (t)
1305                        rcu_wake_cond(t, rnp->boost_kthread_status);
1306        } else {
1307                rcu_initiate_boost_trace(rnp);
1308                raw_spin_unlock_irqrestore(&rnp->lock, flags);
1309        }
1310}
1311
1312/*
1313 * Wake up the per-CPU kthread to invoke RCU callbacks.
1314 */
1315static void invoke_rcu_callbacks_kthread(void)
1316{
1317        unsigned long flags;
1318
1319        local_irq_save(flags);
1320        __this_cpu_write(rcu_cpu_has_work, 1);
1321        if (__this_cpu_read(rcu_cpu_kthread_task) != NULL &&
1322            current != __this_cpu_read(rcu_cpu_kthread_task)) {
1323                rcu_wake_cond(__this_cpu_read(rcu_cpu_kthread_task),
1324                              __this_cpu_read(rcu_cpu_kthread_status));
1325        }
1326        local_irq_restore(flags);
1327}
1328
1329/*
1330 * Is the current CPU running the RCU-callbacks kthread?
1331 * Caller must have preemption disabled.
1332 */
1333static bool rcu_is_callbacks_kthread(void)
1334{
1335        return __get_cpu_var(rcu_cpu_kthread_task) == current;
1336}
1337
1338#define RCU_BOOST_DELAY_JIFFIES DIV_ROUND_UP(CONFIG_RCU_BOOST_DELAY * HZ, 1000)
1339
1340/*
1341 * Do priority-boost accounting for the start of a new grace period.
1342 */
1343static void rcu_preempt_boost_start_gp(struct rcu_node *rnp)
1344{
1345        rnp->boost_time = jiffies + RCU_BOOST_DELAY_JIFFIES;
1346}
1347
1348/*
1349 * Create an RCU-boost kthread for the specified node if one does not
1350 * already exist.  We only create this kthread for preemptible RCU.
1351 * Returns zero if all is well, a negated errno otherwise.
1352 */
1353static int rcu_spawn_one_boost_kthread(struct rcu_state *rsp,
1354                                                 struct rcu_node *rnp)
1355{
1356        int rnp_index = rnp - &rsp->node[0];
1357        unsigned long flags;
1358        struct sched_param sp;
1359        struct task_struct *t;
1360
1361        if (&rcu_preempt_state != rsp)
1362                return 0;
1363
1364        if (!rcu_scheduler_fully_active || rnp->qsmaskinit == 0)
1365                return 0;
1366
1367        rsp->boost = 1;
1368        if (rnp->boost_kthread_task != NULL)
1369                return 0;
1370        t = kthread_create(rcu_boost_kthread, (void *)rnp,
1371                           "rcub/%d", rnp_index);
1372        if (IS_ERR(t))
1373                return PTR_ERR(t);
1374        raw_spin_lock_irqsave(&rnp->lock, flags);
1375        rnp->boost_kthread_task = t;
1376        raw_spin_unlock_irqrestore(&rnp->lock, flags);
1377        sp.sched_priority = RCU_BOOST_PRIO;
1378        sched_setscheduler_nocheck(t, SCHED_FIFO, &sp);
1379        wake_up_process(t); /* get to TASK_INTERRUPTIBLE quickly. */
1380        return 0;
1381}
1382
1383static void rcu_kthread_do_work(void)
1384{
1385        rcu_do_batch(&rcu_sched_state, &__get_cpu_var(rcu_sched_data));
1386        rcu_do_batch(&rcu_bh_state, &__get_cpu_var(rcu_bh_data));
1387        rcu_preempt_do_callbacks();
1388}
1389
1390static void rcu_cpu_kthread_setup(unsigned int cpu)
1391{
1392        struct sched_param sp;
1393
1394        sp.sched_priority = RCU_KTHREAD_PRIO;
1395        sched_setscheduler_nocheck(current, SCHED_FIFO, &sp);
1396}
1397
1398static void rcu_cpu_kthread_park(unsigned int cpu)
1399{
1400        per_cpu(rcu_cpu_kthread_status, cpu) = RCU_KTHREAD_OFFCPU;
1401}
1402
1403static int rcu_cpu_kthread_should_run(unsigned int cpu)
1404{
1405        return __get_cpu_var(rcu_cpu_has_work);
1406}
1407
1408/*
1409 * Per-CPU kernel thread that invokes RCU callbacks.  This replaces the
1410 * RCU softirq used in flavors and configurations of RCU that do not
1411 * support RCU priority boosting.
1412 */
1413static void rcu_cpu_kthread(unsigned int cpu)
1414{
1415        unsigned int *statusp = &__get_cpu_var(rcu_cpu_kthread_status);
1416        char work, *workp = &__get_cpu_var(rcu_cpu_has_work);
1417        int spincnt;
1418
1419        for (spincnt = 0; spincnt < 10; spincnt++) {
1420                trace_rcu_utilization(TPS("Start CPU kthread@rcu_wait"));
1421                local_bh_disable();
1422                *statusp = RCU_KTHREAD_RUNNING;
1423                this_cpu_inc(rcu_cpu_kthread_loops);
1424                local_irq_disable();
1425                work = *workp;
1426                *workp = 0;
1427                local_irq_enable();
1428                if (work)
1429                        rcu_kthread_do_work();
1430                local_bh_enable();
1431                if (*workp == 0) {
1432                        trace_rcu_utilization(TPS("End CPU kthread@rcu_wait"));
1433                        *statusp = RCU_KTHREAD_WAITING;
1434                        return;
1435                }
1436        }
1437        *statusp = RCU_KTHREAD_YIELDING;
1438        trace_rcu_utilization(TPS("Start CPU kthread@rcu_yield"));
1439        schedule_timeout_interruptible(2);
1440        trace_rcu_utilization(TPS("End CPU kthread@rcu_yield"));
1441        *statusp = RCU_KTHREAD_WAITING;
1442}
1443
1444/*
1445 * Set the per-rcu_node kthread's affinity to cover all CPUs that are
1446 * served by the rcu_node in question.  The CPU hotplug lock is still
1447 * held, so the value of rnp->qsmaskinit will be stable.
1448 *
1449 * We don't include outgoingcpu in the affinity set, use -1 if there is
1450 * no outgoing CPU.  If there are no CPUs left in the affinity set,
1451 * this function allows the kthread to execute on any CPU.
1452 */
1453static void rcu_boost_kthread_setaffinity(struct rcu_node *rnp, int outgoingcpu)
1454{
1455        struct task_struct *t = rnp->boost_kthread_task;
1456        unsigned long mask = rnp->qsmaskinit;
1457        cpumask_var_t cm;
1458        int cpu;
1459
1460        if (!t)
1461                return;
1462        if (!zalloc_cpumask_var(&cm, GFP_KERNEL))
1463                return;
1464        for (cpu = rnp->grplo; cpu <= rnp->grphi; cpu++, mask >>= 1)
1465                if ((mask & 0x1) && cpu != outgoingcpu)
1466                        cpumask_set_cpu(cpu, cm);
1467        if (cpumask_weight(cm) == 0) {
1468                cpumask_setall(cm);
1469                for (cpu = rnp->grplo; cpu <= rnp->grphi; cpu++)
1470                        cpumask_clear_cpu(cpu, cm);
1471                WARN_ON_ONCE(cpumask_weight(cm) == 0);
1472        }
1473        set_cpus_allowed_ptr(t, cm);
1474        free_cpumask_var(cm);
1475}
1476
1477static struct smp_hotplug_thread rcu_cpu_thread_spec = {
1478        .store                  = &rcu_cpu_kthread_task,
1479        .thread_should_run      = rcu_cpu_kthread_should_run,
1480        .thread_fn              = rcu_cpu_kthread,
1481        .thread_comm            = "rcuc/%u",
1482        .setup                  = rcu_cpu_kthread_setup,
1483        .park                   = rcu_cpu_kthread_park,
1484};
1485
1486/*
1487 * Spawn all kthreads -- called as soon as the scheduler is running.
1488 */
1489static int __init rcu_spawn_kthreads(void)
1490{
1491        struct rcu_node *rnp;
1492        int cpu;
1493
1494        rcu_scheduler_fully_active = 1;
1495        for_each_possible_cpu(cpu)
1496                per_cpu(rcu_cpu_has_work, cpu) = 0;
1497        BUG_ON(smpboot_register_percpu_thread(&rcu_cpu_thread_spec));
1498        rnp = rcu_get_root(rcu_state);
1499        (void)rcu_spawn_one_boost_kthread(rcu_state, rnp);
1500        if (NUM_RCU_NODES > 1) {
1501                rcu_for_each_leaf_node(rcu_state, rnp)
1502                        (void)rcu_spawn_one_boost_kthread(rcu_state, rnp);
1503        }
1504        return 0;
1505}
1506early_initcall(rcu_spawn_kthreads);
1507
1508static void rcu_prepare_kthreads(int cpu)
1509{
1510        struct rcu_data *rdp = per_cpu_ptr(rcu_state->rda, cpu);
1511        struct rcu_node *rnp = rdp->mynode;
1512
1513        /* Fire up the incoming CPU's kthread and leaf rcu_node kthread. */
1514        if (rcu_scheduler_fully_active)
1515                (void)rcu_spawn_one_boost_kthread(rcu_state, rnp);
1516}
1517
1518#else /* #ifdef CONFIG_RCU_BOOST */
1519
1520static void rcu_initiate_boost(struct rcu_node *rnp, unsigned long flags)
1521{
1522        raw_spin_unlock_irqrestore(&rnp->lock, flags);
1523}
1524
1525static void invoke_rcu_callbacks_kthread(void)
1526{
1527        WARN_ON_ONCE(1);
1528}
1529
1530static bool rcu_is_callbacks_kthread(void)
1531{
1532        return false;
1533}
1534
1535static void rcu_preempt_boost_start_gp(struct rcu_node *rnp)
1536{
1537}
1538
1539static void rcu_boost_kthread_setaffinity(struct rcu_node *rnp, int outgoingcpu)
1540{
1541}
1542
1543static int __init rcu_scheduler_really_started(void)
1544{
1545        rcu_scheduler_fully_active = 1;
1546        return 0;
1547}
1548early_initcall(rcu_scheduler_really_started);
1549
1550static void rcu_prepare_kthreads(int cpu)
1551{
1552}
1553
1554#endif /* #else #ifdef CONFIG_RCU_BOOST */
1555
1556#if !defined(CONFIG_RCU_FAST_NO_HZ)
1557
1558/*
1559 * Check to see if any future RCU-related work will need to be done
1560 * by the current CPU, even if none need be done immediately, returning
1561 * 1 if so.  This function is part of the RCU implementation; it is -not-
1562 * an exported member of the RCU API.
1563 *
1564 * Because we not have RCU_FAST_NO_HZ, just check whether this CPU needs
1565 * any flavor of RCU.
1566 */
1567int rcu_needs_cpu(int cpu, unsigned long *delta_jiffies)
1568{
1569        *delta_jiffies = ULONG_MAX;
1570        return rcu_cpu_has_callbacks(cpu, NULL);
1571}
1572
1573/*
1574 * Because we do not have RCU_FAST_NO_HZ, don't bother cleaning up
1575 * after it.
1576 */
1577static void rcu_cleanup_after_idle(int cpu)
1578{
1579}
1580
1581/*
1582 * Do the idle-entry grace-period work, which, because CONFIG_RCU_FAST_NO_HZ=n,
1583 * is nothing.
1584 */
1585static void rcu_prepare_for_idle(int cpu)
1586{
1587}
1588
1589/*
1590 * Don't bother keeping a running count of the number of RCU callbacks
1591 * posted because CONFIG_RCU_FAST_NO_HZ=n.
1592 */
1593static void rcu_idle_count_callbacks_posted(void)
1594{
1595}
1596
1597#else /* #if !defined(CONFIG_RCU_FAST_NO_HZ) */
1598
1599/*
1600 * This code is invoked when a CPU goes idle, at which point we want
1601 * to have the CPU do everything required for RCU so that it can enter
1602 * the energy-efficient dyntick-idle mode.  This is handled by a
1603 * state machine implemented by rcu_prepare_for_idle() below.
1604 *
1605 * The following three proprocessor symbols control this state machine:
1606 *
1607 * RCU_IDLE_GP_DELAY gives the number of jiffies that a CPU is permitted
1608 *      to sleep in dyntick-idle mode with RCU callbacks pending.  This
1609 *      is sized to be roughly one RCU grace period.  Those energy-efficiency
1610 *      benchmarkers who might otherwise be tempted to set this to a large
1611 *      number, be warned: Setting RCU_IDLE_GP_DELAY too high can hang your
1612 *      system.  And if you are -that- concerned about energy efficiency,
1613 *      just power the system down and be done with it!
1614 * RCU_IDLE_LAZY_GP_DELAY gives the number of jiffies that a CPU is
1615 *      permitted to sleep in dyntick-idle mode with only lazy RCU
1616 *      callbacks pending.  Setting this too high can OOM your system.
1617 *
1618 * The values below work well in practice.  If future workloads require
1619 * adjustment, they can be converted into kernel config parameters, though
1620 * making the state machine smarter might be a better option.
1621 */
1622#define RCU_IDLE_GP_DELAY 4             /* Roughly one grace period. */
1623#define RCU_IDLE_LAZY_GP_DELAY (6 * HZ) /* Roughly six seconds. */
1624
1625static int rcu_idle_gp_delay = RCU_IDLE_GP_DELAY;
1626module_param(rcu_idle_gp_delay, int, 0644);
1627static int rcu_idle_lazy_gp_delay = RCU_IDLE_LAZY_GP_DELAY;
1628module_param(rcu_idle_lazy_gp_delay, int, 0644);
1629
1630extern int tick_nohz_enabled;
1631
1632/*
1633 * Try to advance callbacks for all flavors of RCU on the current CPU.
1634 * Afterwards, if there are any callbacks ready for immediate invocation,
1635 * return true.
1636 */
1637static bool rcu_try_advance_all_cbs(void)
1638{
1639        bool cbs_ready = false;
1640        struct rcu_data *rdp;
1641        struct rcu_node *rnp;
1642        struct rcu_state *rsp;
1643
1644        for_each_rcu_flavor(rsp) {
1645                rdp = this_cpu_ptr(rsp->rda);
1646                rnp = rdp->mynode;
1647
1648                /*
1649                 * Don't bother checking unless a grace period has
1650                 * completed since we last checked and there are
1651                 * callbacks not yet ready to invoke.
1652                 */
1653                if (rdp->completed != rnp->completed &&
1654                    rdp->nxttail[RCU_DONE_TAIL] != rdp->nxttail[RCU_NEXT_TAIL])
1655                        note_gp_changes(rsp, rdp);
1656
1657                if (cpu_has_callbacks_ready_to_invoke(rdp))
1658                        cbs_ready = true;
1659        }
1660        return cbs_ready;
1661}
1662
1663/*
1664 * Allow the CPU to enter dyntick-idle mode unless it has callbacks ready
1665 * to invoke.  If the CPU has callbacks, try to advance them.  Tell the
1666 * caller to set the timeout based on whether or not there are non-lazy
1667 * callbacks.
1668 *
1669 * The caller must have disabled interrupts.
1670 */
1671int rcu_needs_cpu(int cpu, unsigned long *dj)
1672{
1673        struct rcu_dynticks *rdtp = &per_cpu(rcu_dynticks, cpu);
1674
1675        /* Snapshot to detect later posting of non-lazy callback. */
1676        rdtp->nonlazy_posted_snap = rdtp->nonlazy_posted;
1677
1678        /* If no callbacks, RCU doesn't need the CPU. */
1679        if (!rcu_cpu_has_callbacks(cpu, &rdtp->all_lazy)) {
1680                *dj = ULONG_MAX;
1681                return 0;
1682        }
1683
1684        /* Attempt to advance callbacks. */
1685        if (rcu_try_advance_all_cbs()) {
1686                /* Some ready to invoke, so initiate later invocation. */
1687                invoke_rcu_core();
1688                return 1;
1689        }
1690        rdtp->last_accelerate = jiffies;
1691
1692        /* Request timer delay depending on laziness, and round. */
1693        if (!rdtp->all_lazy) {
1694                *dj = round_up(rcu_idle_gp_delay + jiffies,
1695                               rcu_idle_gp_delay) - jiffies;
1696        } else {
1697                *dj = round_jiffies(rcu_idle_lazy_gp_delay + jiffies) - jiffies;
1698        }
1699        return 0;
1700}
1701
1702/*
1703 * Prepare a CPU for idle from an RCU perspective.  The first major task
1704 * is to sense whether nohz mode has been enabled or disabled via sysfs.
1705 * The second major task is to check to see if a non-lazy callback has
1706 * arrived at a CPU that previously had only lazy callbacks.  The third
1707 * major task is to accelerate (that is, assign grace-period numbers to)
1708 * any recently arrived callbacks.
1709 *
1710 * The caller must have disabled interrupts.
1711 */
1712static void rcu_prepare_for_idle(int cpu)
1713{
1714        struct rcu_data *rdp;
1715        struct rcu_dynticks *rdtp = &per_cpu(rcu_dynticks, cpu);
1716        struct rcu_node *rnp;
1717        struct rcu_state *rsp;
1718        int tne;
1719
1720        /* Handle nohz enablement switches conservatively. */
1721        tne = ACCESS_ONCE(tick_nohz_enabled);
1722        if (tne != rdtp->tick_nohz_enabled_snap) {
1723                if (rcu_cpu_has_callbacks(cpu, NULL))
1724                        invoke_rcu_core(); /* force nohz to see update. */
1725                rdtp->tick_nohz_enabled_snap = tne;
1726                return;
1727        }
1728        if (!tne)
1729                return;
1730
1731        /* If this is a no-CBs CPU, no callbacks, just return. */
1732        if (rcu_is_nocb_cpu(cpu))
1733                return;
1734
1735        /*
1736         * If a non-lazy callback arrived at a CPU having only lazy
1737         * callbacks, invoke RCU core for the side-effect of recalculating
1738         * idle duration on re-entry to idle.
1739         */
1740        if (rdtp->all_lazy &&
1741            rdtp->nonlazy_posted != rdtp->nonlazy_posted_snap) {
1742                invoke_rcu_core();
1743                return;
1744        }
1745
1746        /*
1747         * If we have not yet accelerated this jiffy, accelerate all
1748         * callbacks on this CPU.
1749         */
1750        if (rdtp->last_accelerate == jiffies)
1751                return;
1752        rdtp->last_accelerate = jiffies;
1753        for_each_rcu_flavor(rsp) {
1754                rdp = per_cpu_ptr(rsp->rda, cpu);
1755                if (!*rdp->nxttail[RCU_DONE_TAIL])
1756                        continue;
1757                rnp = rdp->mynode;
1758                raw_spin_lock(&rnp->lock); /* irqs already disabled. */
1759                rcu_accelerate_cbs(rsp, rnp, rdp);
1760                raw_spin_unlock(&rnp->lock); /* irqs remain disabled. */
1761        }
1762}
1763
1764/*
1765 * Clean up for exit from idle.  Attempt to advance callbacks based on
1766 * any grace periods that elapsed while the CPU was idle, and if any
1767 * callbacks are now ready to invoke, initiate invocation.
1768 */
1769static void rcu_cleanup_after_idle(int cpu)
1770{
1771        struct rcu_data *rdp;
1772        struct rcu_state *rsp;
1773
1774        if (rcu_is_nocb_cpu(cpu))
1775                return;
1776        rcu_try_advance_all_cbs();
1777        for_each_rcu_flavor(rsp) {
1778                rdp = per_cpu_ptr(rsp->rda, cpu);
1779                if (cpu_has_callbacks_ready_to_invoke(rdp))
1780                        invoke_rcu_core();
1781        }
1782}
1783
1784/*
1785 * Keep a running count of the number of non-lazy callbacks posted
1786 * on this CPU.  This running counter (which is never decremented) allows
1787 * rcu_prepare_for_idle() to detect when something out of the idle loop
1788 * posts a callback, even if an equal number of callbacks are invoked.
1789 * Of course, callbacks should only be posted from within a trace event
1790 * designed to be called from idle or from within RCU_NONIDLE().
1791 */
1792static void rcu_idle_count_callbacks_posted(void)
1793{
1794        __this_cpu_add(rcu_dynticks.nonlazy_posted, 1);
1795}
1796
1797/*
1798 * Data for flushing lazy RCU callbacks at OOM time.
1799 */
1800static atomic_t oom_callback_count;
1801static DECLARE_WAIT_QUEUE_HEAD(oom_callback_wq);
1802
1803/*
1804 * RCU OOM callback -- decrement the outstanding count and deliver the
1805 * wake-up if we are the last one.
1806 */
1807static void rcu_oom_callback(struct rcu_head *rhp)
1808{
1809        if (atomic_dec_and_test(&oom_callback_count))
1810                wake_up(&oom_callback_wq);
1811}
1812
1813/*
1814 * Post an rcu_oom_notify callback on the current CPU if it has at
1815 * least one lazy callback.  This will unnecessarily post callbacks
1816 * to CPUs that already have a non-lazy callback at the end of their
1817 * callback list, but this is an infrequent operation, so accept some
1818 * extra overhead to keep things simple.
1819 */
1820static void rcu_oom_notify_cpu(void *unused)
1821{
1822        struct rcu_state *rsp;
1823        struct rcu_data *rdp;
1824
1825        for_each_rcu_flavor(rsp) {
1826                rdp = __this_cpu_ptr(rsp->rda);
1827                if (rdp->qlen_lazy != 0) {
1828                        atomic_inc(&oom_callback_count);
1829                        rsp->call(&rdp->oom_head, rcu_oom_callback);
1830                }
1831        }
1832}
1833
1834/*
1835 * If low on memory, ensure that each CPU has a non-lazy callback.
1836 * This will wake up CPUs that have only lazy callbacks, in turn
1837 * ensuring that they free up the corresponding memory in a timely manner.
1838 * Because an uncertain amount of memory will be freed in some uncertain
1839 * timeframe, we do not claim to have freed anything.
1840 */
1841static int rcu_oom_notify(struct notifier_block *self,
1842                          unsigned long notused, void *nfreed)
1843{
1844        int cpu;
1845
1846        /* Wait for callbacks from earlier instance to complete. */
1847        wait_event(oom_callback_wq, atomic_read(&oom_callback_count) == 0);
1848
1849        /*
1850         * Prevent premature wakeup: ensure that all increments happen
1851         * before there is a chance of the counter reaching zero.
1852         */
1853        atomic_set(&oom_callback_count, 1);
1854
1855        get_online_cpus();
1856        for_each_online_cpu(cpu) {
1857                smp_call_function_single(cpu, rcu_oom_notify_cpu, NULL, 1);
1858                cond_resched();
1859        }
1860        put_online_cpus();
1861
1862        /* Unconditionally decrement: no need to wake ourselves up. */
1863        atomic_dec(&oom_callback_count);
1864
1865        return NOTIFY_OK;
1866}
1867
1868static struct notifier_block rcu_oom_nb = {
1869        .notifier_call = rcu_oom_notify
1870};
1871
1872static int __init rcu_register_oom_notifier(void)
1873{
1874        register_oom_notifier(&rcu_oom_nb);
1875        return 0;
1876}
1877early_initcall(rcu_register_oom_notifier);
1878
1879#endif /* #else #if !defined(CONFIG_RCU_FAST_NO_HZ) */
1880
1881#ifdef CONFIG_RCU_CPU_STALL_INFO
1882
1883#ifdef CONFIG_RCU_FAST_NO_HZ
1884
1885static void print_cpu_stall_fast_no_hz(char *cp, int cpu)
1886{
1887        struct rcu_dynticks *rdtp = &per_cpu(rcu_dynticks, cpu);
1888        unsigned long nlpd = rdtp->nonlazy_posted - rdtp->nonlazy_posted_snap;
1889
1890        sprintf(cp, "last_accelerate: %04lx/%04lx, nonlazy_posted: %ld, %c%c",
1891                rdtp->last_accelerate & 0xffff, jiffies & 0xffff,
1892                ulong2long(nlpd),
1893                rdtp->all_lazy ? 'L' : '.',
1894                rdtp->tick_nohz_enabled_snap ? '.' : 'D');
1895}
1896
1897#else /* #ifdef CONFIG_RCU_FAST_NO_HZ */
1898
1899static void print_cpu_stall_fast_no_hz(char *cp, int cpu)
1900{
1901        *cp = '\0';
1902}
1903
1904#endif /* #else #ifdef CONFIG_RCU_FAST_NO_HZ */
1905
1906/* Initiate the stall-info list. */
1907static void print_cpu_stall_info_begin(void)
1908{
1909        pr_cont("\n");
1910}
1911
1912/*
1913 * Print out diagnostic information for the specified stalled CPU.
1914 *
1915 * If the specified CPU is aware of the current RCU grace period
1916 * (flavor specified by rsp), then print the number of scheduling
1917 * clock interrupts the CPU has taken during the time that it has
1918 * been aware.  Otherwise, print the number of RCU grace periods
1919 * that this CPU is ignorant of, for example, "1" if the CPU was
1920 * aware of the previous grace period.
1921 *
1922 * Also print out idle and (if CONFIG_RCU_FAST_NO_HZ) idle-entry info.
1923 */
1924static void print_cpu_stall_info(struct rcu_state *rsp, int cpu)
1925{
1926        char fast_no_hz[72];
1927        struct rcu_data *rdp = per_cpu_ptr(rsp->rda, cpu);
1928        struct rcu_dynticks *rdtp = rdp->dynticks;
1929        char *ticks_title;
1930        unsigned long ticks_value;
1931
1932        if (rsp->gpnum == rdp->gpnum) {
1933                ticks_title = "ticks this GP";
1934                ticks_value = rdp->ticks_this_gp;
1935        } else {
1936                ticks_title = "GPs behind";
1937                ticks_value = rsp->gpnum - rdp->gpnum;
1938        }
1939        print_cpu_stall_fast_no_hz(fast_no_hz, cpu);
1940        pr_err("\t%d: (%lu %s) idle=%03x/%llx/%d softirq=%u/%u %s\n",
1941               cpu, ticks_value, ticks_title,
1942               atomic_read(&rdtp->dynticks) & 0xfff,
1943               rdtp->dynticks_nesting, rdtp->dynticks_nmi_nesting,
1944               rdp->softirq_snap, kstat_softirqs_cpu(RCU_SOFTIRQ, cpu),
1945               fast_no_hz);
1946}
1947
1948/* Terminate the stall-info list. */
1949static void print_cpu_stall_info_end(void)
1950{
1951        pr_err("\t");
1952}
1953
1954/* Zero ->ticks_this_gp for all flavors of RCU. */
1955static void zero_cpu_stall_ticks(struct rcu_data *rdp)
1956{
1957        rdp->ticks_this_gp = 0;
1958        rdp->softirq_snap = kstat_softirqs_cpu(RCU_SOFTIRQ, smp_processor_id());
1959}
1960
1961/* Increment ->ticks_this_gp for all flavors of RCU. */
1962static void increment_cpu_stall_ticks(void)
1963{
1964        struct rcu_state *rsp;
1965
1966        for_each_rcu_flavor(rsp)
1967                __this_cpu_ptr(rsp->rda)->ticks_this_gp++;
1968}
1969
1970#else /* #ifdef CONFIG_RCU_CPU_STALL_INFO */
1971
1972static void print_cpu_stall_info_begin(void)
1973{
1974        pr_cont(" {");
1975}
1976
1977static void print_cpu_stall_info(struct rcu_state *rsp, int cpu)
1978{
1979        pr_cont(" %d", cpu);
1980}
1981
1982static void print_cpu_stall_info_end(void)
1983{
1984        pr_cont("} ");
1985}
1986
1987static void zero_cpu_stall_ticks(struct rcu_data *rdp)
1988{
1989}
1990
1991static void increment_cpu_stall_ticks(void)
1992{
1993}
1994
1995#endif /* #else #ifdef CONFIG_RCU_CPU_STALL_INFO */
1996
1997#ifdef CONFIG_RCU_NOCB_CPU
1998
1999/*
2000 * Offload callback processing from the boot-time-specified set of CPUs
2001 * specified by rcu_nocb_mask.  For each CPU in the set, there is a
2002 * kthread created that pulls the callbacks from the corresponding CPU,
2003 * waits for a grace period to elapse, and invokes the callbacks.
2004 * The no-CBs CPUs do a wake_up() on their kthread when they insert
2005 * a callback into any empty list, unless the rcu_nocb_poll boot parameter
2006 * has been specified, in which case each kthread actively polls its
2007 * CPU.  (Which isn't so great for energy efficiency, but which does
2008 * reduce RCU's overhead on that CPU.)
2009 *
2010 * This is intended to be used in conjunction with Frederic Weisbecker's
2011 * adaptive-idle work, which would seriously reduce OS jitter on CPUs
2012 * running CPU-bound user-mode computations.
2013 *
2014 * Offloading of callback processing could also in theory be used as
2015 * an energy-efficiency measure because CPUs with no RCU callbacks
2016 * queued are more aggressive about entering dyntick-idle mode.
2017 */
2018
2019
2020/* Parse the boot-time rcu_nocb_mask CPU list from the kernel parameters. */
2021static int __init rcu_nocb_setup(char *str)
2022{
2023        alloc_bootmem_cpumask_var(&rcu_nocb_mask);
2024        have_rcu_nocb_mask = true;
2025        cpulist_parse(str, rcu_nocb_mask);
2026        return 1;
2027}
2028__setup("rcu_nocbs=", rcu_nocb_setup);
2029
2030static int __init parse_rcu_nocb_poll(char *arg)
2031{
2032        rcu_nocb_poll = 1;
2033        return 0;
2034}
2035early_param("rcu_nocb_poll", parse_rcu_nocb_poll);
2036
2037/*
2038 * Do any no-CBs CPUs need another grace period?
2039 *
2040 * Interrupts must be disabled.  If the caller does not hold the root
2041 * rnp_node structure's ->lock, the results are advisory only.
2042 */
2043static int rcu_nocb_needs_gp(struct rcu_state *rsp)
2044{
2045        struct rcu_node *rnp = rcu_get_root(rsp);
2046
2047        return rnp->need_future_gp[(ACCESS_ONCE(rnp->completed) + 1) & 0x1];
2048}
2049
2050/*
2051 * Wake up any no-CBs CPUs' kthreads that were waiting on the just-ended
2052 * grace period.
2053 */
2054static void rcu_nocb_gp_cleanup(struct rcu_state *rsp, struct rcu_node *rnp)
2055{
2056        wake_up_all(&rnp->nocb_gp_wq[rnp->completed & 0x1]);
2057}
2058
2059/*
2060 * Set the root rcu_node structure's ->need_future_gp field
2061 * based on the sum of those of all rcu_node structures.  This does
2062 * double-count the root rcu_node structure's requests, but this
2063 * is necessary to handle the possibility of a rcu_nocb_kthread()
2064 * having awakened during the time that the rcu_node structures
2065 * were being updated for the end of the previous grace period.
2066 */
2067static void rcu_nocb_gp_set(struct rcu_node *rnp, int nrq)
2068{
2069        rnp->need_future_gp[(rnp->completed + 1) & 0x1] += nrq;
2070}
2071
2072static void rcu_init_one_nocb(struct rcu_node *rnp)
2073{
2074        init_waitqueue_head(&rnp->nocb_gp_wq[0]);
2075        init_waitqueue_head(&rnp->nocb_gp_wq[1]);
2076}
2077
2078/* Is the specified CPU a no-CPUs CPU? */
2079bool rcu_is_nocb_cpu(int cpu)
2080{
2081        if (have_rcu_nocb_mask)
2082                return cpumask_test_cpu(cpu, rcu_nocb_mask);
2083        return false;
2084}
2085
2086/*
2087 * Enqueue the specified string of rcu_head structures onto the specified
2088 * CPU's no-CBs lists.  The CPU is specified by rdp, the head of the
2089 * string by rhp, and the tail of the string by rhtp.  The non-lazy/lazy
2090 * counts are supplied by rhcount and rhcount_lazy.
2091 *
2092 * If warranted, also wake up the kthread servicing this CPUs queues.
2093 */
2094static void __call_rcu_nocb_enqueue(struct rcu_data *rdp,
2095                                    struct rcu_head *rhp,
2096                                    struct rcu_head **rhtp,
2097                                    int rhcount, int rhcount_lazy)
2098{
2099        int len;
2100        struct rcu_head **old_rhpp;
2101        struct task_struct *t;
2102
2103        /* Enqueue the callback on the nocb list and update counts. */
2104        old_rhpp = xchg(&rdp->nocb_tail, rhtp);
2105        ACCESS_ONCE(*old_rhpp) = rhp;
2106        atomic_long_add(rhcount, &rdp->nocb_q_count);
2107        atomic_long_add(rhcount_lazy, &rdp->nocb_q_count_lazy);
2108
2109        /* If we are not being polled and there is a kthread, awaken it ... */
2110        t = ACCESS_ONCE(rdp->nocb_kthread);
2111        if (rcu_nocb_poll | !t)
2112                return;
2113        len = atomic_long_read(&rdp->nocb_q_count);
2114        if (old_rhpp == &rdp->nocb_head) {
2115                wake_up(&rdp->nocb_wq); /* ... only if queue was empty ... */
2116                rdp->qlen_last_fqs_check = 0;
2117        } else if (len > rdp->qlen_last_fqs_check + qhimark) {
2118                wake_up_process(t); /* ... or if many callbacks queued. */
2119                rdp->qlen_last_fqs_check = LONG_MAX / 2;
2120        }
2121        return;
2122}
2123
2124/*
2125 * This is a helper for __call_rcu(), which invokes this when the normal
2126 * callback queue is inoperable.  If this is not a no-CBs CPU, this
2127 * function returns failure back to __call_rcu(), which can complain
2128 * appropriately.
2129 *
2130 * Otherwise, this function queues the callback where the corresponding
2131 * "rcuo" kthread can find it.
2132 */
2133static bool __call_rcu_nocb(struct rcu_data *rdp, struct rcu_head *rhp,
2134                            bool lazy)
2135{
2136
2137        if (!rcu_is_nocb_cpu(rdp->cpu))
2138                return 0;
2139        __call_rcu_nocb_enqueue(rdp, rhp, &rhp->next, 1, lazy);
2140        if (__is_kfree_rcu_offset((unsigned long)rhp->func))
2141                trace_rcu_kfree_callback(rdp->rsp->name, rhp,
2142                                         (unsigned long)rhp->func,
2143                                         rdp->qlen_lazy, rdp->qlen);
2144        else
2145                trace_rcu_callback(rdp->rsp->name, rhp,
2146                                   rdp->qlen_lazy, rdp->qlen);
2147        return 1;
2148}
2149
2150/*
2151 * Adopt orphaned callbacks on a no-CBs CPU, or return 0 if this is
2152 * not a no-CBs CPU.
2153 */
2154static bool __maybe_unused rcu_nocb_adopt_orphan_cbs(struct rcu_state *rsp,
2155                                                     struct rcu_data *rdp)
2156{
2157        long ql = rsp->qlen;
2158        long qll = rsp->qlen_lazy;
2159
2160        /* If this is not a no-CBs CPU, tell the caller to do it the old way. */
2161        if (!rcu_is_nocb_cpu(smp_processor_id()))
2162                return 0;
2163        rsp->qlen = 0;
2164        rsp->qlen_lazy = 0;
2165
2166        /* First, enqueue the donelist, if any.  This preserves CB ordering. */
2167        if (rsp->orphan_donelist != NULL) {
2168                __call_rcu_nocb_enqueue(rdp, rsp->orphan_donelist,
2169                                        rsp->orphan_donetail, ql, qll);
2170                ql = qll = 0;
2171                rsp->orphan_donelist = NULL;
2172                rsp->orphan_donetail = &rsp->orphan_donelist;
2173        }
2174        if (rsp->orphan_nxtlist != NULL) {
2175                __call_rcu_nocb_enqueue(rdp, rsp->orphan_nxtlist,
2176                                        rsp->orphan_nxttail, ql, qll);
2177                ql = qll = 0;
2178                rsp->orphan_nxtlist = NULL;
2179                rsp->orphan_nxttail = &rsp->orphan_nxtlist;
2180        }
2181        return 1;
2182}
2183
2184/*
2185 * If necessary, kick off a new grace period, and either way wait
2186 * for a subsequent grace period to complete.
2187 */
2188static void rcu_nocb_wait_gp(struct rcu_data *rdp)
2189{
2190        unsigned long c;
2191        bool d;
2192        unsigned long flags;
2193        struct rcu_node *rnp = rdp->mynode;
2194
2195        raw_spin_lock_irqsave(&rnp->lock, flags);
2196        c = rcu_start_future_gp(rnp, rdp);
2197        raw_spin_unlock_irqrestore(&rnp->lock, flags);
2198
2199        /*
2200         * Wait for the grace period.  Do so interruptibly to avoid messing
2201         * up the load average.
2202         */
2203        trace_rcu_future_gp(rnp, rdp, c, TPS("StartWait"));
2204        for (;;) {
2205                wait_event_interruptible(
2206                        rnp->nocb_gp_wq[c & 0x1],
2207                        (d = ULONG_CMP_GE(ACCESS_ONCE(rnp->completed), c)));
2208                if (likely(d))
2209                        break;
2210                flush_signals(current);
2211                trace_rcu_future_gp(rnp, rdp, c, TPS("ResumeWait"));
2212        }
2213        trace_rcu_future_gp(rnp, rdp, c, TPS("EndWait"));
2214        smp_mb(); /* Ensure that CB invocation happens after GP end. */
2215}
2216
2217/*
2218 * Per-rcu_data kthread, but only for no-CBs CPUs.  Each kthread invokes
2219 * callbacks queued by the corresponding no-CBs CPU.
2220 */
2221static int rcu_nocb_kthread(void *arg)
2222{
2223        int c, cl;
2224        struct rcu_head *list;
2225        struct rcu_head *next;
2226        struct rcu_head **tail;
2227        struct rcu_data *rdp = arg;
2228
2229        /* Each pass through this loop invokes one batch of callbacks */
2230        for (;;) {
2231                /* If not polling, wait for next batch of callbacks. */
2232                if (!rcu_nocb_poll)
2233                        wait_event_interruptible(rdp->nocb_wq, rdp->nocb_head);
2234                list = ACCESS_ONCE(rdp->nocb_head);
2235                if (!list) {
2236                        schedule_timeout_interruptible(1);
2237                        flush_signals(current);
2238                        continue;
2239                }
2240
2241                /*
2242                 * Extract queued callbacks, update counts, and wait
2243                 * for a grace period to elapse.
2244                 */
2245                ACCESS_ONCE(rdp->nocb_head) = NULL;
2246                tail = xchg(&rdp->nocb_tail, &rdp->nocb_head);
2247                c = atomic_long_xchg(&rdp->nocb_q_count, 0);
2248                cl = atomic_long_xchg(&rdp->nocb_q_count_lazy, 0);
2249                ACCESS_ONCE(rdp->nocb_p_count) += c;
2250                ACCESS_ONCE(rdp->nocb_p_count_lazy) += cl;
2251                rcu_nocb_wait_gp(rdp);
2252
2253                /* Each pass through the following loop invokes a callback. */
2254                trace_rcu_batch_start(rdp->rsp->name, cl, c, -1);
2255                c = cl = 0;
2256                while (list) {
2257                        next = list->next;
2258                        /* Wait for enqueuing to complete, if needed. */
2259                        while (next == NULL && &list->next != tail) {
2260                                schedule_timeout_interruptible(1);
2261                                next = list->next;
2262                        }
2263                        debug_rcu_head_unqueue(list);
2264                        local_bh_disable();
2265                        if (__rcu_reclaim(rdp->rsp->name, list))
2266                                cl++;
2267                        c++;
2268                        local_bh_enable();
2269                        list = next;
2270                }
2271                trace_rcu_batch_end(rdp->rsp->name, c, !!list, 0, 0, 1);
2272                ACCESS_ONCE(rdp->nocb_p_count) -= c;
2273                ACCESS_ONCE(rdp->nocb_p_count_lazy) -= cl;
2274                rdp->n_nocbs_invoked += c;
2275        }
2276        return 0;
2277}
2278
2279/* Initialize per-rcu_data variables for no-CBs CPUs. */
2280static void __init rcu_boot_init_nocb_percpu_data(struct rcu_data *rdp)
2281{
2282        rdp->nocb_tail = &rdp->nocb_head;
2283        init_waitqueue_head(&rdp->nocb_wq);
2284}
2285
2286/* Create a kthread for each RCU flavor for each no-CBs CPU. */
2287static void __init rcu_spawn_nocb_kthreads(struct rcu_state *rsp)
2288{
2289        int cpu;
2290        struct rcu_data *rdp;
2291        struct task_struct *t;
2292
2293        if (rcu_nocb_mask == NULL)
2294                return;
2295        for_each_cpu(cpu, rcu_nocb_mask) {
2296                rdp = per_cpu_ptr(rsp->rda, cpu);
2297                t = kthread_run(rcu_nocb_kthread, rdp,
2298                                "rcuo%c/%d", rsp->abbr, cpu);
2299                BUG_ON(IS_ERR(t));
2300                ACCESS_ONCE(rdp->nocb_kthread) = t;
2301        }
2302}
2303
2304/* Prevent __call_rcu() from enqueuing callbacks on no-CBs CPUs */
2305static bool init_nocb_callback_list(struct rcu_data *rdp)
2306{
2307        if (rcu_nocb_mask == NULL ||
2308            !cpumask_test_cpu(rdp->cpu, rcu_nocb_mask))
2309                return false;
2310        rdp->nxttail[RCU_NEXT_TAIL] = NULL;
2311        return true;
2312}
2313
2314#else /* #ifdef CONFIG_RCU_NOCB_CPU */
2315
2316static int rcu_nocb_needs_gp(struct rcu_state *rsp)
2317{
2318        return 0;
2319}
2320
2321static void rcu_nocb_gp_cleanup(struct rcu_state *rsp, struct rcu_node *rnp)
2322{
2323}
2324
2325static void rcu_nocb_gp_set(struct rcu_node *rnp, int nrq)
2326{
2327}
2328
2329static void rcu_init_one_nocb(struct rcu_node *rnp)
2330{
2331}
2332
2333static bool __call_rcu_nocb(struct rcu_data *rdp, struct rcu_head *rhp,
2334                            bool lazy)
2335{
2336        return 0;
2337}
2338
2339static bool __maybe_unused rcu_nocb_adopt_orphan_cbs(struct rcu_state *rsp,
2340                                                     struct rcu_data *rdp)
2341{
2342        return 0;
2343}
2344
2345static void __init rcu_boot_init_nocb_percpu_data(struct rcu_data *rdp)
2346{
2347}
2348
2349static void __init rcu_spawn_nocb_kthreads(struct rcu_state *rsp)
2350{
2351}
2352
2353static bool init_nocb_callback_list(struct rcu_data *rdp)
2354{
2355        return false;
2356}
2357
2358#endif /* #else #ifdef CONFIG_RCU_NOCB_CPU */
2359
2360/*
2361 * An adaptive-ticks CPU can potentially execute in kernel mode for an
2362 * arbitrarily long period of time with the scheduling-clock tick turned
2363 * off.  RCU will be paying attention to this CPU because it is in the
2364 * kernel, but the CPU cannot be guaranteed to be executing the RCU state
2365 * machine because the scheduling-clock tick has been disabled.  Therefore,
2366 * if an adaptive-ticks CPU is failing to respond to the current grace
2367 * period and has not be idle from an RCU perspective, kick it.
2368 */
2369static void rcu_kick_nohz_cpu(int cpu)
2370{
2371#ifdef CONFIG_NO_HZ_FULL
2372        if (tick_nohz_full_cpu(cpu))
2373                smp_send_reschedule(cpu);
2374#endif /* #ifdef CONFIG_NO_HZ_FULL */
2375}
2376
2377
2378#ifdef CONFIG_NO_HZ_FULL_SYSIDLE
2379
2380/*
2381 * Define RCU flavor that holds sysidle state.  This needs to be the
2382 * most active flavor of RCU.
2383 */
2384#ifdef CONFIG_PREEMPT_RCU
2385static struct rcu_state *rcu_sysidle_state = &rcu_preempt_state;
2386#else /* #ifdef CONFIG_PREEMPT_RCU */
2387static struct rcu_state *rcu_sysidle_state = &rcu_sched_state;
2388#endif /* #else #ifdef CONFIG_PREEMPT_RCU */
2389
2390static int full_sysidle_state;          /* Current system-idle state. */
2391#define RCU_SYSIDLE_NOT         0       /* Some CPU is not idle. */
2392#define RCU_SYSIDLE_SHORT       1       /* All CPUs idle for brief period. */
2393#define RCU_SYSIDLE_LONG        2       /* All CPUs idle for long enough. */
2394#define RCU_SYSIDLE_FULL        3       /* All CPUs idle, ready for sysidle. */
2395#define RCU_SYSIDLE_FULL_NOTED  4       /* Actually entered sysidle state. */
2396
2397/*
2398 * Invoked to note exit from irq or task transition to idle.  Note that
2399 * usermode execution does -not- count as idle here!  After all, we want
2400 * to detect full-system idle states, not RCU quiescent states and grace
2401 * periods.  The caller must have disabled interrupts.
2402 */
2403static void rcu_sysidle_enter(struct rcu_dynticks *rdtp, int irq)
2404{
2405        unsigned long j;
2406
2407        /* Adjust nesting, check for fully idle. */
2408        if (irq) {
2409                rdtp->dynticks_idle_nesting--;
2410                WARN_ON_ONCE(rdtp->dynticks_idle_nesting < 0);
2411                if (rdtp->dynticks_idle_nesting != 0)
2412                        return;  /* Still not fully idle. */
2413        } else {
2414                if ((rdtp->dynticks_idle_nesting & DYNTICK_TASK_NEST_MASK) ==
2415                    DYNTICK_TASK_NEST_VALUE) {
2416                        rdtp->dynticks_idle_nesting = 0;
2417                } else {
2418                        rdtp->dynticks_idle_nesting -= DYNTICK_TASK_NEST_VALUE;
2419                        WARN_ON_ONCE(rdtp->dynticks_idle_nesting < 0);
2420                        return;  /* Still not fully idle. */
2421                }
2422        }
2423
2424        /* Record start of fully idle period. */
2425        j = jiffies;
2426        ACCESS_ONCE(rdtp->dynticks_idle_jiffies) = j;
2427        smp_mb__before_atomic_inc();
2428        atomic_inc(&rdtp->dynticks_idle);
2429        smp_mb__after_atomic_inc();
2430        WARN_ON_ONCE(atomic_read(&rdtp->dynticks_idle) & 0x1);
2431}
2432
2433/*
2434 * Unconditionally force exit from full system-idle state.  This is
2435 * invoked when a normal CPU exits idle, but must be called separately
2436 * for the timekeeping CPU (tick_do_timer_cpu).  The reason for this
2437 * is that the timekeeping CPU is permitted to take scheduling-clock
2438 * interrupts while the system is in system-idle state, and of course
2439 * rcu_sysidle_exit() has no way of distinguishing a scheduling-clock
2440 * interrupt from any other type of interrupt.
2441 */
2442void rcu_sysidle_force_exit(void)
2443{
2444        int oldstate = ACCESS_ONCE(full_sysidle_state);
2445        int newoldstate;
2446
2447        /*
2448         * Each pass through the following loop attempts to exit full
2449         * system-idle state.  If contention proves to be a problem,
2450         * a trylock-based contention tree could be used here.
2451         */
2452        while (oldstate > RCU_SYSIDLE_SHORT) {
2453                newoldstate = cmpxchg(&full_sysidle_state,
2454                                      oldstate, RCU_SYSIDLE_NOT);
2455                if (oldstate == newoldstate &&
2456                    oldstate == RCU_SYSIDLE_FULL_NOTED) {
2457                        rcu_kick_nohz_cpu(tick_do_timer_cpu);
2458                        return; /* We cleared it, done! */
2459                }
2460                oldstate = newoldstate;
2461        }
2462        smp_mb(); /* Order initial oldstate fetch vs. later non-idle work. */
2463}
2464
2465/*
2466 * Invoked to note entry to irq or task transition from idle.  Note that
2467 * usermode execution does -not- count as idle here!  The caller must
2468 * have disabled interrupts.
2469 */
2470static void rcu_sysidle_exit(struct rcu_dynticks *rdtp, int irq)
2471{
2472        /* Adjust nesting, check for already non-idle. */
2473        if (irq) {
2474                rdtp->dynticks_idle_nesting++;
2475                WARN_ON_ONCE(rdtp->dynticks_idle_nesting <= 0);
2476                if (rdtp->dynticks_idle_nesting != 1)
2477                        return; /* Already non-idle. */
2478        } else {
2479                /*
2480                 * Allow for irq misnesting.  Yes, it really is possible
2481                 * to enter an irq handler then never leave it, and maybe
2482                 * also vice versa.  Handle both possibilities.
2483                 */
2484                if (rdtp->dynticks_idle_nesting & DYNTICK_TASK_NEST_MASK) {
2485                        rdtp->dynticks_idle_nesting += DYNTICK_TASK_NEST_VALUE;
2486                        WARN_ON_ONCE(rdtp->dynticks_idle_nesting <= 0);
2487                        return; /* Already non-idle. */
2488                } else {
2489                        rdtp->dynticks_idle_nesting = DYNTICK_TASK_EXIT_IDLE;
2490                }
2491        }
2492
2493        /* Record end of idle period. */
2494        smp_mb__before_atomic_inc();
2495        atomic_inc(&rdtp->dynticks_idle);
2496        smp_mb__after_atomic_inc();
2497        WARN_ON_ONCE(!(atomic_read(&rdtp->dynticks_idle) & 0x1));
2498
2499        /*
2500         * If we are the timekeeping CPU, we are permitted to be non-idle
2501         * during a system-idle state.  This must be the case, because
2502         * the timekeeping CPU has to take scheduling-clock interrupts
2503         * during the time that the system is transitioning to full
2504         * system-idle state.  This means that the timekeeping CPU must
2505         * invoke rcu_sysidle_force_exit() directly if it does anything
2506         * more than take a scheduling-clock interrupt.
2507         */
2508        if (smp_processor_id() == tick_do_timer_cpu)
2509                return;
2510
2511        /* Update system-idle state: We are clearly no longer fully idle! */
2512        rcu_sysidle_force_exit();
2513}
2514
2515/*
2516 * Check to see if the current CPU is idle.  Note that usermode execution
2517 * does not count as idle.  The caller must have disabled interrupts.
2518 */
2519static void rcu_sysidle_check_cpu(struct rcu_data *rdp, bool *isidle,
2520                                  unsigned long *maxj)
2521{
2522        int cur;
2523        unsigned long j;
2524        struct rcu_dynticks *rdtp = rdp->dynticks;
2525
2526        /*
2527         * If some other CPU has already reported non-idle, if this is
2528         * not the flavor of RCU that tracks sysidle state, or if this
2529         * is an offline or the timekeeping CPU, nothing to do.
2530         */
2531        if (!*isidle || rdp->rsp != rcu_sysidle_state ||
2532            cpu_is_offline(rdp->cpu) || rdp->cpu == tick_do_timer_cpu)
2533                return;
2534        if (rcu_gp_in_progress(rdp->rsp))
2535                WARN_ON_ONCE(smp_processor_id() != tick_do_timer_cpu);
2536
2537        /* Pick up current idle and NMI-nesting counter and check. */
2538        cur = atomic_read(&rdtp->dynticks_idle);
2539        if (cur & 0x1) {
2540                *isidle = false; /* We are not idle! */
2541                return;
2542        }
2543        smp_mb(); /* Read counters before timestamps. */
2544
2545        /* Pick up timestamps. */
2546        j = ACCESS_ONCE(rdtp->dynticks_idle_jiffies);
2547        /* If this CPU entered idle more recently, update maxj timestamp. */
2548        if (ULONG_CMP_LT(*maxj, j))
2549                *maxj = j;
2550}
2551
2552/*
2553 * Is this the flavor of RCU that is handling full-system idle?
2554 */
2555static bool is_sysidle_rcu_state(struct rcu_state *rsp)
2556{
2557        return rsp == rcu_sysidle_state;
2558}
2559
2560/*
2561 * Bind the grace-period kthread for the sysidle flavor of RCU to the
2562 * timekeeping CPU.
2563 */
2564static void rcu_bind_gp_kthread(void)
2565{
2566        int cpu = ACCESS_ONCE(tick_do_timer_cpu);
2567
2568        if (cpu < 0 || cpu >= nr_cpu_ids)
2569                return;
2570        if (raw_smp_processor_id() != cpu)
2571                set_cpus_allowed_ptr(current, cpumask_of(cpu));
2572}
2573
2574/*
2575 * Return a delay in jiffies based on the number of CPUs, rcu_node
2576 * leaf fanout, and jiffies tick rate.  The idea is to allow larger
2577 * systems more time to transition to full-idle state in order to
2578 * avoid the cache thrashing that otherwise occur on the state variable.
2579 * Really small systems (less than a couple of tens of CPUs) should
2580 * instead use a single global atomically incremented counter, and later
2581 * versions of this will automatically reconfigure themselves accordingly.
2582 */
2583static unsigned long rcu_sysidle_delay(void)
2584{
2585        if (nr_cpu_ids <= CONFIG_NO_HZ_FULL_SYSIDLE_SMALL)
2586                return 0;
2587        return DIV_ROUND_UP(nr_cpu_ids * HZ, rcu_fanout_leaf * 1000);
2588}
2589
2590/*
2591 * Advance the full-system-idle state.  This is invoked when all of
2592 * the non-timekeeping CPUs are idle.
2593 */
2594static void rcu_sysidle(unsigned long j)
2595{
2596        /* Check the current state. */
2597        switch (ACCESS_ONCE(full_sysidle_state)) {
2598        case RCU_SYSIDLE_NOT:
2599
2600                /* First time all are idle, so note a short idle period. */
2601                ACCESS_ONCE(full_sysidle_state) = RCU_SYSIDLE_SHORT;
2602                break;
2603
2604        case RCU_SYSIDLE_SHORT:
2605
2606                /*
2607                 * Idle for a bit, time to advance to next state?
2608                 * cmpxchg failure means race with non-idle, let them win.
2609                 */
2610                if (ULONG_CMP_GE(jiffies, j + rcu_sysidle_delay()))
2611                        (void)cmpxchg(&full_sysidle_state,
2612                                      RCU_SYSIDLE_SHORT, RCU_SYSIDLE_LONG);
2613                break;
2614
2615        case RCU_SYSIDLE_LONG:
2616
2617                /*
2618                 * Do an additional check pass before advancing to full.
2619                 * cmpxchg failure means race with non-idle, let them win.
2620                 */
2621                if (ULONG_CMP_GE(jiffies, j + rcu_sysidle_delay()))
2622                        (void)cmpxchg(&full_sysidle_state,
2623                                      RCU_SYSIDLE_LONG, RCU_SYSIDLE_FULL);
2624                break;
2625
2626        default:
2627                break;
2628        }
2629}
2630
2631/*
2632 * Found a non-idle non-timekeeping CPU, so kick the system-idle state
2633 * back to the beginning.
2634 */
2635static void rcu_sysidle_cancel(void)
2636{
2637        smp_mb();
2638        ACCESS_ONCE(full_sysidle_state) = RCU_SYSIDLE_NOT;
2639}
2640
2641/*
2642 * Update the sysidle state based on the results of a force-quiescent-state
2643 * scan of the CPUs' dyntick-idle state.
2644 */
2645static void rcu_sysidle_report(struct rcu_state *rsp, int isidle,
2646                               unsigned long maxj, bool gpkt)
2647{
2648        if (rsp != rcu_sysidle_state)
2649                return;  /* Wrong flavor, ignore. */
2650        if (gpkt && nr_cpu_ids <= CONFIG_NO_HZ_FULL_SYSIDLE_SMALL)
2651                return;  /* Running state machine from timekeeping CPU. */
2652        if (isidle)
2653                rcu_sysidle(maxj);    /* More idle! */
2654        else
2655                rcu_sysidle_cancel(); /* Idle is over. */
2656}
2657
2658/*
2659 * Wrapper for rcu_sysidle_report() when called from the grace-period
2660 * kthread's context.
2661 */
2662static void rcu_sysidle_report_gp(struct rcu_state *rsp, int isidle,
2663                                  unsigned long maxj)
2664{
2665        rcu_sysidle_report(rsp, isidle, maxj, true);
2666}
2667
2668/* Callback and function for forcing an RCU grace period. */
2669struct rcu_sysidle_head {
2670        struct rcu_head rh;
2671        int inuse;
2672};
2673
2674static void rcu_sysidle_cb(struct rcu_head *rhp)
2675{
2676        struct rcu_sysidle_head *rshp;
2677
2678        /*
2679         * The following memory barrier is needed to replace the
2680         * memory barriers that would normally be in the memory
2681         * allocator.
2682         */
2683        smp_mb();  /* grace period precedes setting inuse. */
2684
2685        rshp = container_of(rhp, struct rcu_sysidle_head, rh);
2686        ACCESS_ONCE(rshp->inuse) = 0;
2687}
2688
2689/*
2690 * Check to see if the system is fully idle, other than the timekeeping CPU.
2691 * The caller must have disabled interrupts.
2692 */
2693bool rcu_sys_is_idle(void)
2694{
2695        static struct rcu_sysidle_head rsh;
2696        int rss = ACCESS_ONCE(full_sysidle_state);
2697
2698        if (WARN_ON_ONCE(smp_processor_id() != tick_do_timer_cpu))
2699                return false;
2700
2701        /* Handle small-system case by doing a full scan of CPUs. */
2702        if (nr_cpu_ids <= CONFIG_NO_HZ_FULL_SYSIDLE_SMALL) {
2703                int oldrss = rss - 1;
2704
2705                /*
2706                 * One pass to advance to each state up to _FULL.
2707                 * Give up if any pass fails to advance the state.
2708                 */
2709                while (rss < RCU_SYSIDLE_FULL && oldrss < rss) {
2710                        int cpu;
2711                        bool isidle = true;
2712                        unsigned long maxj = jiffies - ULONG_MAX / 4;
2713                        struct rcu_data *rdp;
2714
2715                        /* Scan all the CPUs looking for nonidle CPUs. */
2716                        for_each_possible_cpu(cpu) {
2717                                rdp = per_cpu_ptr(rcu_sysidle_state->rda, cpu);
2718                                rcu_sysidle_check_cpu(rdp, &isidle, &maxj);
2719                                if (!isidle)
2720                                        break;
2721                        }
2722                        rcu_sysidle_report(rcu_sysidle_state,
2723                                           isidle, maxj, false);
2724                        oldrss = rss;
2725                        rss = ACCESS_ONCE(full_sysidle_state);
2726                }
2727        }
2728
2729        /* If this is the first observation of an idle period, record it. */
2730        if (rss == RCU_SYSIDLE_FULL) {
2731                rss = cmpxchg(&full_sysidle_state,
2732                              RCU_SYSIDLE_FULL, RCU_SYSIDLE_FULL_NOTED);
2733                return rss == RCU_SYSIDLE_FULL;
2734        }
2735
2736        smp_mb(); /* ensure rss load happens before later caller actions. */
2737
2738        /* If already fully idle, tell the caller (in case of races). */
2739        if (rss == RCU_SYSIDLE_FULL_NOTED)
2740                return true;
2741
2742        /*
2743         * If we aren't there yet, and a grace period is not in flight,
2744         * initiate a grace period.  Either way, tell the caller that
2745         * we are not there yet.  We use an xchg() rather than an assignment
2746         * to make up for the memory barriers that would otherwise be
2747         * provided by the memory allocator.
2748         */
2749        if (nr_cpu_ids > CONFIG_NO_HZ_FULL_SYSIDLE_SMALL &&
2750            !rcu_gp_in_progress(rcu_sysidle_state) &&
2751            !rsh.inuse && xchg(&rsh.inuse, 1) == 0)
2752                call_rcu(&rsh.rh, rcu_sysidle_cb);
2753        return false;
2754}
2755
2756/*
2757 * Initialize dynticks sysidle state for CPUs coming online.
2758 */
2759static void rcu_sysidle_init_percpu_data(struct rcu_dynticks *rdtp)
2760{
2761        rdtp->dynticks_idle_nesting = DYNTICK_TASK_NEST_VALUE;
2762}
2763
2764#else /* #ifdef CONFIG_NO_HZ_FULL_SYSIDLE */
2765
2766static void rcu_sysidle_enter(struct rcu_dynticks *rdtp, int irq)
2767{
2768}
2769
2770static void rcu_sysidle_exit(struct rcu_dynticks *rdtp, int irq)
2771{
2772}
2773
2774static void rcu_sysidle_check_cpu(struct rcu_data *rdp, bool *isidle,
2775                                  unsigned long *maxj)
2776{
2777}
2778
2779static bool is_sysidle_rcu_state(struct rcu_state *rsp)
2780{
2781        return false;
2782}
2783
2784static void rcu_bind_gp_kthread(void)
2785{
2786}
2787
2788static void rcu_sysidle_report_gp(struct rcu_state *rsp, int isidle,
2789                                  unsigned long maxj)
2790{
2791}
2792
2793static void rcu_sysidle_init_percpu_data(struct rcu_dynticks *rdtp)
2794{
2795}
2796
2797#endif /* #else #ifdef CONFIG_NO_HZ_FULL_SYSIDLE */
2798
lxr.linux.no kindly hosted by Redpill Linpro AS, provider of Linux consulting and operations services since 1995.