/*

* Read-Copy Update mechanism for mutual exclusion (tree-based version)

* Internal non-public definitions that provide either classic

* or preemptible semantics.

*

* This program is free software; you can redistribute it and/or modify

* it under the terms of the GNU General Public License as published by

* the Free Software Foundation; either version 2 of the License, or

* (at your option) any later version.

*

* This program is distributed in the hope that it will be useful,

* but WITHOUT ANY WARRANTY; without even the implied warranty of

* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the

* GNU General Public License for more details.

*

* You should have received a copy of the GNU General Public License

* along with this program; if not, write to the Free Software

* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.

*

* Copyright Red Hat, 2009

* Copyright IBM Corporation, 2009

*

* Author: Ingo Molnar <mingo@elte.hu>

* Paul E. McKenney <paulmck@linux.vnet.ibm.com>

*/

#include <linux/delay.h>

#define RCU_KTHREAD_PRIO 1

#ifdef CONFIG_RCU_BOOST

#define RCU_BOOST_PRIO CONFIG_RCU_BOOST_PRIO

#else

#define RCU_BOOST_PRIO RCU_KTHREAD_PRIO

#endif

/*

* Check the RCU kernel configuration parameters and print informative

* messages about anything out of the ordinary. If you like #ifdef, you

* will love this function.

*/

static void __init rcu_bootup_announce_oddness(void)

{

#ifdef CONFIG_RCU_TRACE

printk(KERN_INFO "\tRCU debugfs-based tracing is enabled.\n");

#endif

#if (defined(CONFIG_64BIT) && CONFIG_RCU_FANOUT != 64) || (!defined(CONFIG_64BIT) && CONFIG_RCU_FANOUT != 32)

printk(KERN_INFO "\tCONFIG_RCU_FANOUT set to non-default value of %d\n",

CONFIG_RCU_FANOUT);

#endif

#ifdef CONFIG_RCU_FANOUT_EXACT

printk(KERN_INFO "\tHierarchical RCU autobalancing is disabled.\n");

#endif

#ifdef CONFIG_RCU_FAST_NO_HZ

printk(KERN_INFO

"\tRCU dyntick-idle grace-period acceleration is enabled.\n");

#endif

#ifdef CONFIG_PROVE_RCU

printk(KERN_INFO "\tRCU lockdep checking is enabled.\n");

#endif

#ifdef CONFIG_RCU_TORTURE_TEST_RUNNABLE

printk(KERN_INFO "\tRCU torture testing starts during boot.\n");

#endif

#if defined(CONFIG_TREE_PREEMPT_RCU) && !defined(CONFIG_RCU_CPU_STALL_VERBOSE)

printk(KERN_INFO "\tDump stacks of tasks blocking RCU-preempt GP.\n");

#endif

#if defined(CONFIG_RCU_CPU_STALL_INFO)

printk(KERN_INFO "\tAdditional per-CPU info printed with stalls.\n");

#endif

#if NUM_RCU_LVL_4 != 0

printk(KERN_INFO "\tExperimental four-level hierarchy is enabled.\n");

#endif

}

#ifdef CONFIG_TREE_PREEMPT_RCU

struct rcu_state rcu_preempt_state = RCU_STATE_INITIALIZER(rcu_preempt);

DEFINE_PER_CPU(struct rcu_data, rcu_preempt_data);

static struct rcu_state *rcu_state = &rcu_preempt_state;

static void rcu_read_unlock_special(struct task_struct *t);

static int rcu_preempted_readers_exp(struct rcu_node *rnp);

/*

* Tell them what RCU they are running.

*/

static void __init rcu_bootup_announce(void)

{

printk(KERN_INFO "Preemptible hierarchical RCU implementation.\n");

rcu_bootup_announce_oddness();

}

/*

* Return the number of RCU-preempt batches processed thus far

* for debug and statistics.

*/

long rcu_batches_completed_preempt(void)

{

return rcu_preempt_state.completed;

}

EXPORT_SYMBOL_GPL(rcu_batches_completed_preempt);

/*

* Return the number of RCU batches processed thus far for debug & stats.

*/

long rcu_batches_completed(void)

{

return rcu_batches_completed_preempt();

}

EXPORT_SYMBOL_GPL(rcu_batches_completed);

/*

* Force a quiescent state for preemptible RCU.

*/

void rcu_force_quiescent_state(void)

{

force_quiescent_state(&rcu_preempt_state, 0);

}

EXPORT_SYMBOL_GPL(rcu_force_quiescent_state);

/*

* Record a preemptible-RCU quiescent state for the specified CPU. Note

* that this just means that the task currently running on the CPU is

* not in a quiescent state. There might be any number of tasks blocked

* while in an RCU read-side critical section.

*

* Unlike the other rcu_*_qs() functions, callers to this function

* must disable irqs in order to protect the assignment to

* ->rcu_read_unlock_special.

*/

static void rcu_preempt_qs(int cpu)

{

struct rcu_data *rdp = &per_cpu(rcu_preempt_data, cpu);

rdp->passed_quiesce_gpnum = rdp->gpnum;

barrier();

if (rdp->passed_quiesce == 0)

trace_rcu_grace_period("rcu_preempt", rdp->gpnum, "cpuqs");

rdp->passed_quiesce = 1;

current->rcu_read_unlock_special &= ~RCU_READ_UNLOCK_NEED_QS;

}

/*

* We have entered the scheduler, and the current task might soon be

* context-switched away from. If this task is in an RCU read-side

* critical section, we will no longer be able to rely on the CPU to

* record that fact, so we enqueue the task on the blkd_tasks list.

* The task will dequeue itself when it exits the outermost enclosing

* RCU read-side critical section. Therefore, the current grace period

* cannot be permitted to complete until the blkd_tasks list entries

* predating the current grace period drain, in other words, until

* rnp->gp_tasks becomes NULL.

*

* Caller must disable preemption.

*/

void rcu_preempt_note_context_switch(void)

{

struct task_struct *t = current;

unsigned long flags;

struct rcu_data *rdp;

struct rcu_node *rnp;

if (t->rcu_read_lock_nesting > 0 &&

(t->rcu_read_unlock_special & RCU_READ_UNLOCK_BLOCKED) == 0) {

/* Possibly blocking in an RCU read-side critical section. */

rdp = __this_cpu_ptr(rcu_preempt_state.rda);

rnp = rdp->mynode;

raw_spin_lock_irqsave(&rnp->lock, flags);

t->rcu_read_unlock_special |= RCU_READ_UNLOCK_BLOCKED;

t->rcu_blocked_node = rnp;

/*

* If this CPU has already checked in, then this task

* will hold up the next grace period rather than the

* current grace period. Queue the task accordingly.

* If the task is queued for the current grace period

* (i.e., this CPU has not yet passed through a quiescent

* state for the current grace period), then as long

* as that task remains queued, the current grace period

* cannot end. Note that there is some uncertainty as

* to exactly when the current grace period started.

* We take a conservative approach, which can result

* in unnecessarily waiting on tasks that started very

* slightly after the current grace period began. C'est

* la vie!!!

*

* But first, note that the current CPU must still be

* on line!

*/

WARN_ON_ONCE((rdp->grpmask & rnp->qsmaskinit) == 0);

WARN_ON_ONCE(!list_empty(&t->rcu_node_entry));

if ((rnp->qsmask & rdp->grpmask) && rnp->gp_tasks != NULL) {

list_add(&t->rcu_node_entry, rnp->gp_tasks->prev);

rnp->gp_tasks = &t->rcu_node_entry;

#ifdef CONFIG_RCU_BOOST

if (rnp->boost_tasks != NULL)

rnp->boost_tasks = rnp->gp_tasks;

#endif /* #ifdef CONFIG_RCU_BOOST */

} else {

list_add(&t->rcu_node_entry, &rnp->blkd_tasks);

if (rnp->qsmask & rdp->grpmask)

rnp->gp_tasks = &t->rcu_node_entry;

}

trace_rcu_preempt_task(rdp->rsp->name,

t->pid,

(rnp->qsmask & rdp->grpmask)

? rnp->gpnum

: rnp->gpnum + 1);

raw_spin_unlock_irqrestore(&rnp->lock, flags);

} else if (t->rcu_read_lock_nesting < 0 &&

t->rcu_read_unlock_special) {

/*

* Complete exit from RCU read-side critical section on

* behalf of preempted instance of __rcu_read_unlock().

*/

rcu_read_unlock_special(t);

}

/*

* Either we were not in an RCU read-side critical section to

* begin with, or we have now recorded that critical section

* globally. Either way, we can now note a quiescent state

* for this CPU. Again, if we were in an RCU read-side critical

* section, and if that critical section was blocking the current

* grace period, then the fact that the task has been enqueued

* means that we continue to block the current grace period.

*/

local_irq_save(flags);

rcu_preempt_qs(smp_processor_id());

local_irq_restore(flags);

}

/*

* Tree-preemptible RCU implementation for rcu_read_lock().

* Just increment ->rcu_read_lock_nesting, shared state will be updated

* if we block.

*/

void __rcu_read_lock(void)

{

current->rcu_read_lock_nesting++;

barrier(); /* needed if we ever invoke rcu_read_lock in rcutree.c */

}

EXPORT_SYMBOL_GPL(__rcu_read_lock);

/*

* Check for preempted RCU readers blocking the current grace period

* for the specified rcu_node structure. If the caller needs a reliable

* answer, it must hold the rcu_node's ->lock.

*/

static int rcu_preempt_blocked_readers_cgp(struct rcu_node *rnp)

{

return rnp->gp_tasks != NULL;

}

/*

* Record a quiescent state for all tasks that were previously queued

* on the specified rcu_node structure and that were blocking the current

* RCU grace period. The caller must hold the specified rnp->lock with

* irqs disabled, and this lock is released upon return, but irqs remain

* disabled.

*/

static void rcu_report_unblock_qs_rnp(struct rcu_node *rnp, unsigned long flags)

__releases(rnp->lock)

{

unsigned long mask;

struct rcu_node *rnp_p;

if (rnp->qsmask != 0 || rcu_preempt_blocked_readers_cgp(rnp)) {

raw_spin_unlock_irqrestore(&rnp->lock, flags);

return; /* Still need more quiescent states! */

}

rnp_p = rnp->parent;

if (rnp_p == NULL) {

/*

* Either there is only one rcu_node in the tree,

* or tasks were kicked up to root rcu_node due to

* CPUs going offline.

*/

rcu_report_qs_rsp(&rcu_preempt_state, flags);

return;

}

/* Report up the rest of the hierarchy. */

mask = rnp->grpmask;

raw_spin_unlock(&rnp->lock); /* irqs remain disabled. */

raw_spin_lock(&rnp_p->lock); /* irqs already disabled. */

rcu_report_qs_rnp(mask, &rcu_preempt_state, rnp_p, flags);

}

/*

* Advance a ->blkd_tasks-list pointer to the next entry, instead

* returning NULL if at the end of the list.

*/

static struct list_head *rcu_next_node_entry(struct task_struct *t,

struct rcu_node *rnp)

{

struct list_head *np;

np = t->rcu_node_entry.next;

if (np == &rnp->blkd_tasks)

np = NULL;

return np;

}

/*

* Handle special cases during rcu_read_unlock(), such as needing to

* notify RCU core processing or task having blocked during the RCU

* read-side critical section.

*/

static noinline void rcu_read_unlock_special(struct task_struct *t)

{

int empty;

int empty_exp;

int empty_exp_now;

unsigned long flags;

struct list_head *np;

#ifdef CONFIG_RCU_BOOST

struct rt_mutex *rbmp = NULL;

#endif /* #ifdef CONFIG_RCU_BOOST */

struct rcu_node *rnp;

int special;

/* NMI handlers cannot block and cannot safely manipulate state. */

if (in_nmi())

return;

local_irq_save(flags);

/*

* If RCU core is waiting for this CPU to exit critical section,

* let it know that we have done so.

*/

special = t->rcu_read_unlock_special;

if (special & RCU_READ_UNLOCK_NEED_QS) {

rcu_preempt_qs(smp_processor_id());

}

/* Hardware IRQ handlers cannot block. */

if (in_irq() || in_serving_softirq()) {

local_irq_restore(flags);

return;

}

/* Clean up if blocked during RCU read-side critical section. */

if (special & RCU_READ_UNLOCK_BLOCKED) {

t->rcu_read_unlock_special &= ~RCU_READ_UNLOCK_BLOCKED;

/*

* Remove this task from the list it blocked on. The

* task can migrate while we acquire the lock, but at

* most one time. So at most two passes through loop.

*/

for (;;) {

rnp = t->rcu_blocked_node;

raw_spin_lock(&rnp->lock); /* irqs already disabled. */

if (rnp == t->rcu_blocked_node)

break;

raw_spin_unlock(&rnp->lock); /* irqs remain disabled. */

}

empty = !rcu_preempt_blocked_readers_cgp(rnp);

empty_exp = !rcu_preempted_readers_exp(rnp);

smp_mb(); /* ensure expedited fastpath sees end of RCU c-s. */

np = rcu_next_node_entry(t, rnp);

list_del_init(&t->rcu_node_entry);

t->rcu_blocked_node = NULL;

trace_rcu_unlock_preempted_task("rcu_preempt",

rnp->gpnum, t->pid);

if (&t->rcu_node_entry == rnp->gp_tasks)

rnp->gp_tasks = np;

if (&t->rcu_node_entry == rnp->exp_tasks)

rnp->exp_tasks = np;

#ifdef CONFIG_RCU_BOOST

if (&t->rcu_node_entry == rnp->boost_tasks)

rnp->boost_tasks = np;

/* Snapshot/clear ->rcu_boost_mutex with rcu_node lock held. */

if (t->rcu_boost_mutex) {

rbmp = t->rcu_boost_mutex;

t->rcu_boost_mutex = NULL;

}

#endif /* #ifdef CONFIG_RCU_BOOST */

/*

* If this was the last task on the current list, and if

* we aren't waiting on any CPUs, report the quiescent state.

* Note that rcu_report_unblock_qs_rnp() releases rnp->lock,

* so we must take a snapshot of the expedited state.

*/

empty_exp_now = !rcu_preempted_readers_exp(rnp);

if (!empty && !rcu_preempt_blocked_readers_cgp(rnp)) {

trace_rcu_quiescent_state_report("preempt_rcu",

rnp->gpnum,

0, rnp->qsmask,

rnp->level,

rnp->grplo,

rnp->grphi,

!!rnp->gp_tasks);

rcu_report_unblock_qs_rnp(rnp, flags);

} else

raw_spin_unlock_irqrestore(&rnp->lock, flags);

#ifdef CONFIG_RCU_BOOST

/* Unboost if we were boosted. */

if (rbmp)

rt_mutex_unlock(rbmp);

#endif /* #ifdef CONFIG_RCU_BOOST */

/*

* If this was the last task on the expedited lists,

* then we need to report up the rcu_node hierarchy.

*/

if (!empty_exp && empty_exp_now)

rcu_report_exp_rnp(&rcu_preempt_state, rnp, true);

} else {

local_irq_restore(flags);

}

}

/*

* Tree-preemptible RCU implementation for rcu_read_unlock().

* Decrement ->rcu_read_lock_nesting. If the result is zero (outermost

* rcu_read_unlock()) and ->rcu_read_unlock_special is non-zero, then

* invoke rcu_read_unlock_special() to clean up after a context switch

* in an RCU read-side critical section and other special cases.

*/

void __rcu_read_unlock(void)

{

struct task_struct *t = current;

if (t->rcu_read_lock_nesting != 1)

--t->rcu_read_lock_nesting;

else {

barrier(); /* critical section before exit code. */

t->rcu_read_lock_nesting = INT_MIN;

barrier(); /* assign before ->rcu_read_unlock_special load */

if (unlikely(ACCESS_ONCE(t->rcu_read_unlock_special)))

rcu_read_unlock_special(t);

barrier(); /* ->rcu_read_unlock_special load before assign */

t->rcu_read_lock_nesting = 0;

}

#ifdef CONFIG_PROVE_LOCKING

{

int rrln = ACCESS_ONCE(t->rcu_read_lock_nesting);

WARN_ON_ONCE(rrln < 0 && rrln > INT_MIN / 2);

}

#endif /* #ifdef CONFIG_PROVE_LOCKING */

}

EXPORT_SYMBOL_GPL(__rcu_read_unlock);

#ifdef CONFIG_RCU_CPU_STALL_VERBOSE

/*

* Dump detailed information for all tasks blocking the current RCU

* grace period on the specified rcu_node structure.

*/

static void rcu_print_detail_task_stall_rnp(struct rcu_node *rnp)

{

unsigned long flags;

struct task_struct *t;

if (!rcu_preempt_blocked_readers_cgp(rnp))

return;

raw_spin_lock_irqsave(&rnp->lock, flags);

t = list_entry(rnp->gp_tasks,

struct task_struct, rcu_node_entry);

list_for_each_entry_continue(t, &rnp->blkd_tasks, rcu_node_entry)

sched_show_task(t);

raw_spin_unlock_irqrestore(&rnp->lock, flags);

}

/*

* Dump detailed information for all tasks blocking the current RCU

* grace period.

*/

static void rcu_print_detail_task_stall(struct rcu_state *rsp)

{

struct rcu_node *rnp = rcu_get_root(rsp);

rcu_print_detail_task_stall_rnp(rnp);

rcu_for_each_leaf_node(rsp, rnp)

rcu_print_detail_task_stall_rnp(rnp);

}

#else /* #ifdef CONFIG_RCU_CPU_STALL_VERBOSE */

static void rcu_print_detail_task_stall(struct rcu_state *rsp)

{

}

#endif /* #else #ifdef CONFIG_RCU_CPU_STALL_VERBOSE */

#ifdef CONFIG_RCU_CPU_STALL_INFO

static void rcu_print_task_stall_begin(struct rcu_node *rnp)

{

printk(KERN_ERR "\tTasks blocked on level-%d rcu_node (CPUs %d-%d):",

rnp->level, rnp->grplo, rnp->grphi);

}

static void rcu_print_task_stall_end(void)

{

printk(KERN_CONT "\n");

}

#else /* #ifdef CONFIG_RCU_CPU_STALL_INFO */

static void rcu_print_task_stall_begin(struct rcu_node *rnp)

{

}

static void rcu_print_task_stall_end(void)

{

}

#endif /* #else #ifdef CONFIG_RCU_CPU_STALL_INFO */

/*

* Scan the current list of tasks blocked within RCU read-side critical

* sections, printing out the tid of each.

*/

static int rcu_print_task_stall(struct rcu_node *rnp)

{

struct task_struct *t;

int ndetected = 0;

if (!rcu_preempt_blocked_readers_cgp(rnp))

return 0;

rcu_print_task_stall_begin(rnp);

t = list_entry(rnp->gp_tasks,

struct task_struct, rcu_node_entry);

list_for_each_entry_continue(t, &rnp->blkd_tasks, rcu_node_entry) {

printk(KERN_CONT " P%d", t->pid);

ndetected++;

}

rcu_print_task_stall_end();

return ndetected;

}

/*

* Suppress preemptible RCU's CPU stall warnings by pushing the

* time of the next stall-warning message comfortably far into the

* future.

*/

static void rcu_preempt_stall_reset(void)

{

rcu_preempt_state.jiffies_stall = jiffies + ULONG_MAX / 2;

}

/*

* Check that the list of blocked tasks for the newly completed grace

* period is in fact empty. It is a serious bug to complete a grace

* period that still has RCU readers blocked! This function must be

* invoked -before- updating this rnp's ->gpnum, and the rnp's ->lock

* must be held by the caller.

*

* Also, if there are blocked tasks on the list, they automatically

* block the newly created grace period, so set up ->gp_tasks accordingly.

*/

static void rcu_preempt_check_blocked_tasks(struct rcu_node *rnp)

{

WARN_ON_ONCE(rcu_preempt_blocked_readers_cgp(rnp));

if (!list_empty(&rnp->blkd_tasks))

rnp->gp_tasks = rnp->blkd_tasks.next;

WARN_ON_ONCE(rnp->qsmask);

}

#ifdef CONFIG_HOTPLUG_CPU

/*

* Handle tasklist migration for case in which all CPUs covered by the

* specified rcu_node have gone offline. Move them up to the root

* rcu_node. The reason for not just moving them to the immediate

* parent is to remove the need for rcu_read_unlock_special() to

* make more than two attempts to acquire the target rcu_node's lock.

* Returns true if there were tasks blocking the current RCU grace

* period.

*

* Returns 1 if there was previously a task blocking the current grace

* period on the specified rcu_node structure.

*

* The caller must hold rnp->lock with irqs disabled.

*/

static int rcu_preempt_offline_tasks(struct rcu_state *rsp,

struct rcu_node *rnp,

struct rcu_data *rdp)

{

struct list_head *lp;

struct list_head *lp_root;

int retval = 0;

struct rcu_node *rnp_root = rcu_get_root(rsp);

struct task_struct *t;

if (rnp == rnp_root) {

WARN_ONCE(1, "Last CPU thought to be offlined?");

return 0; /* Shouldn't happen: at least one CPU online. */

}

/* If we are on an internal node, complain bitterly. */

WARN_ON_ONCE(rnp != rdp->mynode);

/*

* Move tasks up to root rcu_node. Don't try to get fancy for

* this corner-case operation -- just put this node's tasks

* at the head of the root node's list, and update the root node's

* ->gp_tasks and ->exp_tasks pointers to those of this node's,

* if non-NULL. This might result in waiting for more tasks than

* absolutely necessary, but this is a good performance/complexity

* tradeoff.

*/

if (rcu_preempt_blocked_readers_cgp(rnp) && rnp->qsmask == 0)

retval |= RCU_OFL_TASKS_NORM_GP;

if (rcu_preempted_readers_exp(rnp))

retval |= RCU_OFL_TASKS_EXP_GP;

lp = &rnp->blkd_tasks;

lp_root = &rnp_root->blkd_tasks;

while (!list_empty(lp)) {

t = list_entry(lp->next, typeof(*t), rcu_node_entry);

raw_spin_lock(&rnp_root->lock); /* irqs already disabled */

list_del(&t->rcu_node_entry);

t->rcu_blocked_node = rnp_root;

list_add(&t->rcu_node_entry, lp_root);

if (&t->rcu_node_entry == rnp->gp_tasks)

rnp_root->gp_tasks = rnp->gp_tasks;

if (&t->rcu_node_entry == rnp->exp_tasks)

rnp_root->exp_tasks = rnp->exp_tasks;

#ifdef CONFIG_RCU_BOOST

if (&t->rcu_node_entry == rnp->boost_tasks)

rnp_root->boost_tasks = rnp->boost_tasks;

#endif /* #ifdef CONFIG_RCU_BOOST */

raw_spin_unlock(&rnp_root->lock); /* irqs still disabled */

}

#ifdef CONFIG_RCU_BOOST

/* In case root is being boosted and leaf is not. */

raw_spin_lock(&rnp_root->lock); /* irqs already disabled */

if (rnp_root->boost_tasks != NULL &&

rnp_root->boost_tasks != rnp_root->gp_tasks)

rnp_root->boost_tasks = rnp_root->gp_tasks;

raw_spin_unlock(&rnp_root->lock); /* irqs still disabled */

#endif /* #ifdef CONFIG_RCU_BOOST */

rnp->gp_tasks = NULL;

rnp->exp_tasks = NULL;

return retval;

}

#endif /* #ifdef CONFIG_HOTPLUG_CPU */

/*

* Do CPU-offline processing for preemptible RCU.

*/

static void rcu_preempt_cleanup_dead_cpu(int cpu)

{

rcu_cleanup_dead_cpu(cpu, &rcu_preempt_state);

}

/*

* Check for a quiescent state from the current CPU. When a task blocks,

* the task is recorded in the corresponding CPU's rcu_node structure,

* which is checked elsewhere.

*

* Caller must disable hard irqs.

*/

static void rcu_preempt_check_callbacks(int cpu)

{

struct task_struct *t = current;

if (t->rcu_read_lock_nesting == 0) {

rcu_preempt_qs(cpu);

return;

}

if (t->rcu_read_lock_nesting > 0 &&

per_cpu(rcu_preempt_data, cpu).qs_pending)

t->rcu_read_unlock_special |= RCU_READ_UNLOCK_NEED_QS;

}

/*

* Process callbacks for preemptible RCU.

*/

static void rcu_preempt_process_callbacks(void)

{

__rcu_process_callbacks(&rcu_preempt_state,

&__get_cpu_var(rcu_preempt_data));

}

#ifdef CONFIG_RCU_BOOST

static void rcu_preempt_do_callbacks(void)

{

rcu_do_batch(&rcu_preempt_state, &__get_cpu_var(rcu_preempt_data));

}

#endif /* #ifdef CONFIG_RCU_BOOST */

/*

* Queue a preemptible-RCU callback for invocation after a grace period.

*/

void call_rcu(struct rcu_head *head, void (*func)(struct rcu_head *rcu))

{

__call_rcu(head, func, &rcu_preempt_state, 0);

}

EXPORT_SYMBOL_GPL(call_rcu);

/*

* Queue an RCU callback for lazy invocation after a grace period.

* This will likely be later named something like "call_rcu_lazy()",

* but this change will require some way of tagging the lazy RCU

* callbacks in the list of pending callbacks. Until then, this

* function may only be called from __kfree_rcu().

*/

void kfree_call_rcu(struct rcu_head *head,

void (*func)(struct rcu_head *rcu))

{

__call_rcu(head, func, &rcu_preempt_state, 1);

}

EXPORT_SYMBOL_GPL(kfree_call_rcu);

/**

* synchronize_rcu - wait until a grace period has elapsed.

*

* Control will return to the caller some time after a full grace

* period has elapsed, in other words after all currently executing RCU

* read-side critical sections have completed. Note, however, that

* upon return from synchronize_rcu(), the caller might well be executing

* concurrently with new RCU read-side critical sections that began while

* synchronize_rcu() was waiting. RCU read-side critical sections are

* delimited by rcu_read_lock() and rcu_read_unlock(), and may be nested.

*/

void synchronize_rcu(void)

{

rcu_lockdep_assert(!lock_is_held(&rcu_bh_lock_map) &&

!lock_is_held(&rcu_lock_map) &&

!lock_is_held(&rcu_sched_lock_map),

"Illegal synchronize_rcu() in RCU read-side critical section");

if (!rcu_scheduler_active)

return;

wait_rcu_gp(call_rcu);

}

EXPORT_SYMBOL_GPL(synchronize_rcu);

static DECLARE_WAIT_QUEUE_HEAD(sync_rcu_preempt_exp_wq);

static long sync_rcu_preempt_exp_count;

static DEFINE_MUTEX(sync_rcu_preempt_exp_mutex);

/*

* Return non-zero if there are any tasks in RCU read-side critical

* sections blocking the current preemptible-RCU expedited grace period.

* If there is no preemptible-RCU expedited grace period currently in

* progress, returns zero unconditionally.

*/

static int rcu_preempted_readers_exp(struct rcu_node *rnp)

{

return rnp->exp_tasks != NULL;

}

/*

* return non-zero if there is no RCU expedited grace period in progress

* for the specified rcu_node structure, in other words, if all CPUs and

* tasks covered by the specified rcu_node structure have done their bit

* for the current expedited grace period. Works only for preemptible

* RCU -- other RCU implementation use other means.

*

* Caller must hold sync_rcu_preempt_exp_mutex.

*/

static int sync_rcu_preempt_exp_done(struct rcu_node *rnp)

{

return !rcu_preempted_readers_exp(rnp) &&

ACCESS_ONCE(rnp->expmask) == 0;

}

/*

* Report the exit from RCU read-side critical section for the last task

* that queued itself during or before the current expedited preemptible-RCU

* grace period. This event is reported either to the rcu_node structure on

* which the task was queued or to one of that rcu_node structure's ancestors,

* recursively up the tree. (Calm down, calm down, we do the recursion

* iteratively!)

*

* Most callers will set the "wake" flag, but the task initiating the

* expedited grace period need not wake itself.

*

* Caller must hold sync_rcu_preempt_exp_mutex.

*/

static void rcu_report_exp_rnp(struct rcu_state *rsp, struct rcu_node *rnp,

bool wake)

{

unsigned long flags;

unsigned long mask;

raw_spin_lock_irqsave(&rnp->lock, flags);

for (;;) {

if (!sync_rcu_preempt_exp_done(rnp)) {

raw_spin_unlock_irqrestore(&rnp->lock, flags);

break;

}

if (rnp->parent == NULL) {

raw_spin_unlock_irqrestore(&rnp->lock, flags);

if (wake)

wake_up(&sync_rcu_preempt_exp_wq);

break;

}

mask = rnp->grpmask;

raw_spin_unlock(&rnp->lock); /* irqs remain disabled */

rnp = rnp->parent;

raw_spin_lock(&rnp->lock); /* irqs already disabled */

rnp->expmask &= ~mask;

}

}

/*

* Snapshot the tasks blocking the newly started preemptible-RCU expedited

* grace period for the specified rcu_node structure. If there are no such

* tasks, report it up the rcu_node hierarchy.

*

* Caller must hold sync_rcu_preempt_exp_mutex and rsp->onofflock.

*/

static void

sync_rcu_preempt_exp_init(struct rcu_state *rsp, struct rcu_node *rnp)

{

unsigned long flags;

int must_wait = 0;

raw_spin_lock_irqsave(&rnp->lock, flags);

if (list_empty(&rnp->blkd_tasks))

raw_spin_unlock_irqrestore(&rnp->lock, flags);

else {

rnp->exp_tasks = rnp->blkd_tasks.next;

rcu_initiate_boost(rnp, flags); /* releases rnp->lock */

must_wait = 1;

}

if (!must_wait)

rcu_report_exp_rnp(rsp, rnp, false); /* Don't wake self. */

}

/**

* synchronize_rcu_expedited - Brute-force RCU grace period

*

* Wait for an RCU-preempt grace period, but expedite it. The basic

* idea is to invoke synchronize_sched_expedited() to push all the tasks to

* the ->blkd_tasks lists and wait for this list to drain. This consumes

* significant time on all CPUs and is unfriendly to real-time workloads,

* so is thus not recommended for any sort of common-case code.

* In fact, if you are using synchronize_rcu_expedited() in a loop,

* please restructure your code to batch your updates, and then Use a

* single synchronize_rcu() instead.

*

* Note that it is illegal to call this function while holding any lock

* that is acquired by a CPU-hotplug notifier. And yes, it is also illegal

* to call this function from a CPU-hotplug notifier. Failing to observe

* these restriction will result in deadlock.

*/

void synchronize_rcu_expedited(void)

{

unsigned long flags;

struct rcu_node *rnp;

struct rcu_state *rsp = &rcu_preempt_state;

long snap;

int trycount = 0;

smp_mb(); /* Caller's modifications seen first by other CPUs. */

snap = ACCESS_ONCE(sync_rcu_preempt_exp_count) + 1;

smp_mb(); /* Above access cannot bleed into critical section. */

/*

* Acquire lock, falling back to synchronize_rcu() if too many

* lock-acquisition failures. Of course, if someone does the

* expedited grace period for us, just leave.

*/

while (!mutex_trylock(&sync_rcu_preempt_exp_mutex)) {

if (trycount++ < 10)

udelay(trycount * num_online_cpus());

else {

synchronize_rcu();

return;

}

if ((ACCESS_ONCE(sync_rcu_preempt_exp_count) - snap) > 0)

goto mb_ret; /* Others did our work for us. */

}

if ((ACCESS_ONCE(sync_rcu_preempt_exp_count) - snap) > 0)

goto unlock_mb_ret; /* Others did our work for us. */

/* force all RCU readers onto ->blkd_tasks lists. */

synchronize_sched_expedited();

raw_spin_lock_irqsave(&rsp->onofflock, flags);

/* Initialize ->expmask for all non-leaf rcu_node structures. */

rcu_for_each_nonleaf_node_breadth_first(rsp, rnp) {

raw_spin_lock(&rnp->lock); /* irqs already disabled. */

rnp->expmask = rnp->qsmaskinit;

raw_spin_unlock(&rnp->lock); /* irqs remain disabled. */

}

/* Snapshot current state of ->blkd_tasks lists. */

rcu_for_each_leaf_node(rsp, rnp)

sync_rcu_preempt_exp_init(rsp, rnp);

if (NUM_RCU_NODES > 1)

sync_rcu_preempt_exp_init(rsp, rcu_get_root(rsp));

raw_spin_unlock_irqrestore(&rsp->onofflock, flags);

/* Wait for snapshotted ->blkd_tasks lists to drain. */

rnp = rcu_get_root(rsp);

wait_event(sync_rcu_preempt_exp_wq,

sync_rcu_preempt_exp_done(rnp));

/* Clean up and exit. */

smp_mb(); /* ensure expedited GP seen before counter increment. */

ACCESS_ONCE(sync_rcu_preempt_exp_count)++;

unlock_mb_ret:

mutex_unlock(&sync_rcu_preempt_exp_mutex);

mb_ret:

smp_mb(); /* ensure subsequent action seen after grace period. */

}

EXPORT_SYMBOL_GPL(synchronize_rcu_expedited);

/*

* Check to see if there is any immediate preemptible-RCU-related work

* to be done.

*/

static int rcu_preempt_pending(int cpu)

{

return __rcu_pending(&rcu_preempt_state,

&per_cpu(rcu_preempt_data, cpu));

}

/*

* Does preemptible RCU have callbacks on this CPU?

*/

static int rcu_preempt_cpu_has_callbacks(int cpu)

{

return !!per_cpu(rcu_preempt_data, cpu).nxtlist;

}

/**

* rcu_barrier - Wait until all in-flight call_rcu() callbacks complete.

*/

void rcu_barrier(void)

{

_rcu_barrier(&rcu_preempt_state, call_rcu);

}

EXPORT_SYMBOL_GPL(rcu_barrier);

/*

* Initialize preemptible RCU's per-CPU data.

*/

static void __cpuinit rcu_preempt_init_percpu_data(int cpu)

{

rcu_init_percpu_data(cpu, &rcu_preempt_state, 1);

}

/*

* Move preemptible RCU's callbacks from dying CPU to other online CPU

* and record a quiescent state.

*/

static void rcu_preempt_cleanup_dying_cpu(void)

{

rcu_cleanup_dying_cpu(&rcu_preempt_state);

}

/*

* Initialize preemptible RCU's state structures.

*/

static void __init __rcu_init_preempt(void)

{

rcu_init_one(&rcu_preempt_state, &rcu_preempt_data);

}

#else /* #ifdef CONFIG_TREE_PREEMPT_RCU */

static struct rcu_state *rcu_state = &rcu_sched_state;

/*

* Tell them what RCU they are running.

*/

static void __init rcu_bootup_announce(void)

{

printk(KERN_INFO "Hierarchical RCU implementation.\n");

rcu_bootup_announce_oddness();

}

/*

* Return the number of RCU batches processed thus far for debug & stats.

*/

long rcu_batches_completed(void)

{

return rcu_batches_completed_sched();

}

EXPORT_SYMBOL_GPL(rcu_batches_completed);

/*

* Force a quiescent state for RCU, which, because there is no preemptible

* RCU, becomes the same as rcu-sched.

*/

void rcu_force_quiescent_state(void)

{

rcu_sched_force_quiescent_state();