* and inputs from Rusty Russell, Andrea Arcangeli and Andi Kleen.
*
* For detailed explanation of Read-Copy Update mechanism see -
- * Documentation/RCU
+ * Documentation/RCU
*/
#include <linux/types.h>
#include <linux/kernel.h>
#include "rcutree.h"
-#ifdef CONFIG_DEBUG_LOCK_ALLOC
-static struct lock_class_key rcu_lock_key;
-struct lockdep_map rcu_lock_map =
- STATIC_LOCKDEP_MAP_INIT("rcu_read_lock", &rcu_lock_key);
-EXPORT_SYMBOL_GPL(rcu_lock_map);
-#endif
-
/* Data structures. */
#define RCU_STATE_INITIALIZER(name) { \
struct rcu_state rcu_bh_state = RCU_STATE_INITIALIZER(rcu_bh_state);
DEFINE_PER_CPU(struct rcu_data, rcu_bh_data);
-extern long rcu_batches_completed_sched(void);
-static struct rcu_node *rcu_get_root(struct rcu_state *rsp);
-static void cpu_quiet_msk(unsigned long mask, struct rcu_state *rsp,
- struct rcu_node *rnp, unsigned long flags);
-static void cpu_quiet_msk_finish(struct rcu_state *rsp, unsigned long flags);
-#ifdef CONFIG_HOTPLUG_CPU
-static void __rcu_offline_cpu(int cpu, struct rcu_state *rsp);
-#endif /* #ifdef CONFIG_HOTPLUG_CPU */
-static void __rcu_process_callbacks(struct rcu_state *rsp,
- struct rcu_data *rdp);
-static void __call_rcu(struct rcu_head *head,
- void (*func)(struct rcu_head *rcu),
- struct rcu_state *rsp);
-static int __rcu_pending(struct rcu_state *rsp, struct rcu_data *rdp);
-static void __cpuinit rcu_init_percpu_data(int cpu, struct rcu_state *rsp,
- int preemptable);
-#include "rcutree_plugin.h"
+/*
+ * Return true if an RCU grace period is in progress. The ACCESS_ONCE()s
+ * permit this function to be invoked without holding the root rcu_node
+ * structure's ->lock, but of course results can be subject to change.
+ */
+static int rcu_gp_in_progress(struct rcu_state *rsp)
+{
+ return ACCESS_ONCE(rsp->completed) != ACCESS_ONCE(rsp->gpnum);
+}
/*
* Note a quiescent state. Because we do not need to know
*/
void rcu_sched_qs(int cpu)
{
- unsigned long flags;
struct rcu_data *rdp;
- local_irq_save(flags);
rdp = &per_cpu(rcu_sched_data, cpu);
- rdp->passed_quiesc = 1;
rdp->passed_quiesc_completed = rdp->completed;
- rcu_preempt_qs(cpu);
- local_irq_restore(flags);
+ barrier();
+ rdp->passed_quiesc = 1;
+ rcu_preempt_note_context_switch(cpu);
}
void rcu_bh_qs(int cpu)
{
- unsigned long flags;
struct rcu_data *rdp;
- local_irq_save(flags);
rdp = &per_cpu(rcu_bh_data, cpu);
- rdp->passed_quiesc = 1;
rdp->passed_quiesc_completed = rdp->completed;
- local_irq_restore(flags);
+ barrier();
+ rdp->passed_quiesc = 1;
}
#ifdef CONFIG_NO_HZ
static int qhimark = 10000; /* If this many pending, ignore blimit. */
static int qlowmark = 100; /* Once only this many pending, use blimit. */
+module_param(blimit, int, 0);
+module_param(qhimark, int, 0);
+module_param(qlowmark, int, 0);
+
static void force_quiescent_state(struct rcu_state *rsp, int relaxed);
static int rcu_pending(int cpu);
static int
cpu_needs_another_gp(struct rcu_state *rsp, struct rcu_data *rdp)
{
- /* ACCESS_ONCE() because we are accessing outside of lock. */
- return *rdp->nxttail[RCU_DONE_TAIL] &&
- ACCESS_ONCE(rsp->completed) == ACCESS_ONCE(rsp->gpnum);
+ return *rdp->nxttail[RCU_DONE_TAIL] && !rcu_gp_in_progress(rsp);
}
/*
/*
* Snapshot the specified CPU's dynticks counter so that we can later
* credit them with an implicit quiescent state. Return 1 if this CPU
- * is already in a quiescent state courtesy of dynticks idle mode.
+ * is in dynticks idle mode, which is an extended quiescent state.
*/
static int dyntick_save_progress_counter(struct rcu_data *rdp)
{
spin_lock_irqsave(&rnp->lock, flags);
delta = jiffies - rsp->jiffies_stall;
- if (delta < RCU_STALL_RAT_DELAY || rsp->gpnum == rsp->completed) {
+ if (delta < RCU_STALL_RAT_DELAY || !rcu_gp_in_progress(rsp)) {
spin_unlock_irqrestore(&rnp->lock, flags);
return;
}
/* We haven't checked in, so go dump stack. */
print_cpu_stall(rsp);
- } else if (rsp->gpnum != rsp->completed &&
- delta >= RCU_STALL_RAT_DELAY) {
+ } else if (rcu_gp_in_progress(rsp) && delta >= RCU_STALL_RAT_DELAY) {
/* They had two time units to dump stack, so complain. */
print_other_cpu_stall(rsp);
{
struct rcu_data *rdp = rsp->rda[smp_processor_id()];
struct rcu_node *rnp = rcu_get_root(rsp);
- struct rcu_node *rnp_cur;
- struct rcu_node *rnp_end;
if (!cpu_needs_another_gp(rsp, rdp)) {
spin_unlock_irqrestore(&rnp->lock, flags);
/* Advance to a new grace period and initialize state. */
rsp->gpnum++;
+ WARN_ON_ONCE(rsp->signaled == RCU_GP_INIT);
rsp->signaled = RCU_GP_INIT; /* Hold off force_quiescent_state. */
rsp->jiffies_force_qs = jiffies + RCU_JIFFIES_TILL_FORCE_QS;
record_gp_stall_check_time(rsp);
note_new_gpnum(rsp, rdp);
/*
- * Because we are first, we know that all our callbacks will
- * be covered by this upcoming grace period, even the ones
- * that were registered arbitrarily recently.
+ * Because this CPU just now started the new grace period, we know
+ * that all of its callbacks will be covered by this upcoming grace
+ * period, even the ones that were registered arbitrarily recently.
+ * Therefore, advance all outstanding callbacks to RCU_WAIT_TAIL.
+ *
+ * Other CPUs cannot be sure exactly when the grace period started.
+ * Therefore, their recently registered callbacks must pass through
+ * an additional RCU_NEXT_READY stage, so that they will be handled
+ * by the next RCU grace period.
*/
rdp->nxttail[RCU_NEXT_READY_TAIL] = rdp->nxttail[RCU_NEXT_TAIL];
rdp->nxttail[RCU_WAIT_TAIL] = rdp->nxttail[RCU_NEXT_TAIL];
/* Special-case the common single-level case. */
if (NUM_RCU_NODES == 1) {
+ rcu_preempt_check_blocked_tasks(rnp);
rnp->qsmask = rnp->qsmaskinit;
+ rnp->gpnum = rsp->gpnum;
rsp->signaled = RCU_SIGNAL_INIT; /* force_quiescent_state OK. */
spin_unlock_irqrestore(&rnp->lock, flags);
return;
spin_lock(&rsp->onofflock); /* irqs already disabled. */
/*
- * Set the quiescent-state-needed bits in all the non-leaf RCU
- * nodes for all currently online CPUs. This operation relies
- * on the layout of the hierarchy within the rsp->node[] array.
- * Note that other CPUs will access only the leaves of the
- * hierarchy, which still indicate that no grace period is in
- * progress. In addition, we have excluded CPU-hotplug operations.
- *
- * We therefore do not need to hold any locks. Any required
- * memory barriers will be supplied by the locks guarding the
- * leaf rcu_nodes in the hierarchy.
- */
-
- rnp_end = rsp->level[NUM_RCU_LVLS - 1];
- for (rnp_cur = &rsp->node[0]; rnp_cur < rnp_end; rnp_cur++)
- rnp_cur->qsmask = rnp_cur->qsmaskinit;
-
- /*
- * Now set up the leaf nodes. Here we must be careful. First,
- * we need to hold the lock in order to exclude other CPUs, which
- * might be contending for the leaf nodes' locks. Second, as
- * soon as we initialize a given leaf node, its CPUs might run
- * up the rest of the hierarchy. We must therefore acquire locks
- * for each node that we touch during this stage. (But we still
- * are excluding CPU-hotplug operations.)
+ * Set the quiescent-state-needed bits in all the rcu_node
+ * structures for all currently online CPUs in breadth-first
+ * order, starting from the root rcu_node structure. This
+ * operation relies on the layout of the hierarchy within the
+ * rsp->node[] array. Note that other CPUs will access only
+ * the leaves of the hierarchy, which still indicate that no
+ * grace period is in progress, at least until the corresponding
+ * leaf node has been initialized. In addition, we have excluded
+ * CPU-hotplug operations.
*
* Note that the grace period cannot complete until we finish
* the initialization process, as there will be at least one
* qsmask bit set in the root node until that time, namely the
- * one corresponding to this CPU.
+ * one corresponding to this CPU, due to the fact that we have
+ * irqs disabled.
*/
- rnp_end = &rsp->node[NUM_RCU_NODES];
- rnp_cur = rsp->level[NUM_RCU_LVLS - 1];
- for (; rnp_cur < rnp_end; rnp_cur++) {
- spin_lock(&rnp_cur->lock); /* irqs already disabled. */
- rnp_cur->qsmask = rnp_cur->qsmaskinit;
- spin_unlock(&rnp_cur->lock); /* irqs already disabled. */
+ for (rnp = &rsp->node[0]; rnp < &rsp->node[NUM_RCU_NODES]; rnp++) {
+ spin_lock(&rnp->lock); /* irqs already disabled. */
+ rcu_preempt_check_blocked_tasks(rnp);
+ rnp->qsmask = rnp->qsmaskinit;
+ rnp->gpnum = rsp->gpnum;
+ spin_unlock(&rnp->lock); /* irqs already disabled. */
}
rsp->signaled = RCU_SIGNAL_INIT; /* force_quiescent_state now OK. */
* hold rnp->lock, as required by rcu_start_gp(), which will release it.
*/
static void cpu_quiet_msk_finish(struct rcu_state *rsp, unsigned long flags)
- __releases(rnp->lock)
+ __releases(rcu_get_root(rsp)->lock)
{
+ WARN_ON_ONCE(!rcu_gp_in_progress(rsp));
rsp->completed = rsp->gpnum;
rcu_process_gp_end(rsp, rsp->rda[smp_processor_id()]);
rcu_start_gp(rsp, flags); /* releases root node's rnp->lock. */
unsigned long flags)
__releases(rnp->lock)
{
+ struct rcu_node *rnp_c;
+
/* Walk up the rcu_node hierarchy. */
for (;;) {
if (!(rnp->qsmask & mask)) {
break;
}
spin_unlock_irqrestore(&rnp->lock, flags);
+ rnp_c = rnp;
rnp = rnp->parent;
spin_lock_irqsave(&rnp->lock, flags);
+ WARN_ON_ONCE(rnp_c->qsmask);
}
/*
/*
* Record a quiescent state for the specified CPU, which must either be
- * the current CPU or an offline CPU. The lastcomp argument is used to
- * make sure we are still in the grace period of interest. We don't want
- * to end the current grace period based on quiescent states detected in
- * an earlier grace period!
+ * the current CPU. The lastcomp argument is used to make sure we are
+ * still in the grace period of interest. We don't want to end the current
+ * grace period based on quiescent states detected in an earlier grace
+ * period!
*/
static void
cpu_quiet(int cpu, struct rcu_state *rsp, struct rcu_data *rdp, long lastcomp)
* This GP can't end until cpu checks in, so all of our
* callbacks can be processed during the next GP.
*/
- rdp = rsp->rda[smp_processor_id()];
rdp->nxttail[RCU_NEXT_READY_TAIL] = rdp->nxttail[RCU_NEXT_TAIL];
cpu_quiet_msk(mask, rsp, rnp, flags); /* releases rnp->lock */
spin_lock_irqsave(&rsp->onofflock, flags);
/* Remove the outgoing CPU from the masks in the rcu_node hierarchy. */
- rnp = rdp->mynode;
+ rnp = rdp->mynode; /* this is the outgoing CPU's rnp. */
mask = rdp->grpmask; /* rnp->grplo is constant. */
do {
spin_lock(&rnp->lock); /* irqs already disabled. */
spin_unlock(&rnp->lock); /* irqs remain disabled. */
break;
}
- rcu_preempt_offline_tasks(rsp, rnp);
+ rcu_preempt_offline_tasks(rsp, rnp, rdp);
mask = rnp->grpmask;
spin_unlock(&rnp->lock); /* irqs remain disabled. */
rnp = rnp->parent;
spin_unlock(&rsp->onofflock); /* irqs remain disabled. */
- /* Being offline is a quiescent state, so go record it. */
- cpu_quiet(cpu, rsp, rdp, lastcomp);
-
/*
* Move callbacks from the outgoing CPU to the running CPU.
- * Note that the outgoing CPU is now quiscent, so it is now
+ * Note that the outgoing CPU is now quiescent, so it is now
* (uncharacteristically) safe to access its rcu_data structure.
* Note also that we must carefully retain the order of the
* outgoing CPU's callbacks in order for rcu_barrier() to work
* indefinitely delay callbacks, you have far worse things to
* be worrying about.
*/
- rdp_me = rsp->rda[smp_processor_id()];
if (rdp->nxtlist != NULL) {
+ rdp_me = rsp->rda[smp_processor_id()];
*rdp_me->nxttail[RCU_NEXT_TAIL] = rdp->nxtlist;
rdp_me->nxttail[RCU_NEXT_TAIL] = rdp->nxttail[RCU_NEXT_TAIL];
rdp->nxtlist = NULL;
struct rcu_node *rnp = rcu_get_root(rsp);
u8 signaled;
- if (ACCESS_ONCE(rsp->completed) == ACCESS_ONCE(rsp->gpnum))
+ if (!rcu_gp_in_progress(rsp))
return; /* No grace period in progress, nothing to force. */
if (!spin_trylock_irqsave(&rsp->fqslock, flags)) {
rsp->n_force_qs_lh++; /* Inexact, can lose counts. Tough! */
rdp->nxttail[RCU_NEXT_TAIL] = &head->next;
/* Start a new grace period if one not already started. */
- if (ACCESS_ONCE(rsp->completed) == ACCESS_ONCE(rsp->gpnum)) {
+ if (!rcu_gp_in_progress(rsp)) {
unsigned long nestflag;
struct rcu_node *rnp_root = rcu_get_root(rsp);
}
/* Has an RCU GP gone long enough to send resched IPIs &c? */
- if (ACCESS_ONCE(rsp->completed) != ACCESS_ONCE(rsp->gpnum) &&
+ if (rcu_gp_in_progress(rsp) &&
((long)(ACCESS_ONCE(rsp->jiffies_force_qs) - jiffies) < 0)) {
rdp->n_rp_need_fqs++;
return 1;
rnp = rnp->parent;
} while (rnp != NULL && !(rnp->qsmaskinit & mask));
- spin_unlock(&rsp->onofflock); /* irqs remain disabled. */
-
- /*
- * A new grace period might start here. If so, we will be part of
- * it, and its gpnum will be greater than ours, so we will
- * participate. It is also possible for the gpnum to have been
- * incremented before this function was called, and the bitmasks
- * to not be filled out until now, in which case we will also
- * participate due to our gpnum being behind.
- */
-
- /* Since it is coming online, the CPU is in a quiescent state. */
- cpu_quiet(cpu, rsp, rdp, lastcomp);
- local_irq_restore(flags);
+ spin_unlock_irqrestore(&rsp->onofflock, flags);
}
static void __cpuinit rcu_online_cpu(int cpu)
} \
} while (0)
-#ifdef CONFIG_TREE_PREEMPT_RCU
-
-void __init __rcu_init_preempt(void)
-{
- int i; /* All used by RCU_INIT_FLAVOR(). */
- int j;
- struct rcu_node *rnp;
-
- RCU_INIT_FLAVOR(&rcu_preempt_state, rcu_preempt_data);
-}
-
-#else /* #ifdef CONFIG_TREE_PREEMPT_RCU */
-
-void __init __rcu_init_preempt(void)
-{
-}
-
-#endif /* #else #ifdef CONFIG_TREE_PREEMPT_RCU */
-
void __init __rcu_init(void)
{
int i; /* All used by RCU_INIT_FLAVOR(). */
open_softirq(RCU_SOFTIRQ, rcu_process_callbacks);
}
-module_param(blimit, int, 0);
-module_param(qhimark, int, 0);
-module_param(qlowmark, int, 0);
+#include "rcutree_plugin.h"