path: root/kernel/rcupreempt.c

/*
 * Read-Copy Update mechanism for mutual exclusion, realtime implementation
 *
 * 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 IBM Corporation, 2006
 *
 * Authors: Paul E. McKenney <paulmck@us.ibm.com>
 *		With thanks to Esben Nielsen, Bill Huey, and Ingo Molnar
 *		for pushing me away from locks and towards counters, and
 *		to Suparna Bhattacharya for pushing me completely away
 *		from atomic instructions on the read side.
 *
 *  - Added handling of Dynamic Ticks
 *      Copyright 2007 - Paul E. Mckenney <paulmck@us.ibm.com>
 *                     - Steven Rostedt <srostedt@redhat.com>
 *
 * Papers:  http://www.rdrop.com/users/paulmck/RCU
 *
 * Design Document: http://lwn.net/Articles/253651/
 *
 * For detailed explanation of Read-Copy Update mechanism see -
 * 		Documentation/RCU/ *.txt
 *
 */
#include <linux/types.h>
#include <linux/kernel.h>
#include <linux/init.h>
#include <linux/spinlock.h>
#include <linux/smp.h>
#include <linux/rcupdate.h>
#include <linux/interrupt.h>
#include <linux/sched.h>
#include <asm/atomic.h>
#include <linux/bitops.h>
#include <linux/module.h>
#include <linux/completion.h>
#include <linux/moduleparam.h>
#include <linux/percpu.h>
#include <linux/notifier.h>
#include <linux/rcupdate.h>
#include <linux/cpu.h>
#include <linux/random.h>
#include <linux/delay.h>
#include <linux/byteorder/swabb.h>
#include <linux/cpumask.h>
#include <linux/rcupreempt_trace.h>

/*
 * Macro that prevents the compiler from reordering accesses, but does
 * absolutely -nothing- to prevent CPUs from reordering.  This is used
 * only to mediate communication between mainline code and hardware
 * interrupt and NMI handlers.
 */
#define ACCESS_ONCE(x) (*(volatile typeof(x) *)&(x))

/*
 * PREEMPT_RCU data structures.
 */

/*
 * GP_STAGES specifies the number of times the state machine has
 * to go through the all the rcu_try_flip_states (see below)
 * in a single Grace Period.
 *
 * GP in GP_STAGES stands for Grace Period ;)
 */
#define GP_STAGES    2
struct rcu_data {
	spinlock_t	lock;		/* Protect rcu_data fields. */
	long		completed;	/* Number of last completed batch. */
	int		waitlistcount;
	struct tasklet_struct rcu_tasklet;
	struct rcu_head *nextlist;
	struct rcu_head **nexttail;
	struct rcu_head *waitlist[GP_STAGES];
	struct rcu_head **waittail[GP_STAGES];
	struct rcu_head *donelist;
	struct rcu_head **donetail;
	long rcu_flipctr[2];
#ifdef CONFIG_RCU_TRACE
	struct rcupreempt_trace trace;
#endif /* #ifdef CONFIG_RCU_TRACE */
};

/*
 * States for rcu_try_flip() and friends.
 */

enum rcu_try_flip_states {

	/*
	 * Stay here if nothing is happening. Flip the counter if somthing
	 * starts happening. Denoted by "I"
	 */
	rcu_try_flip_idle_state,

	/*
	 * Wait here for all CPUs to notice that the counter has flipped. This
	 * prevents the old set of counters from ever being incremented once
	 * we leave this state, which in turn is necessary because we cannot
	 * test any individual counter for zero -- we can only check the sum.
	 * Denoted by "A".
	 */
	rcu_try_flip_waitack_state,

	/*
	 * Wait here for the sum of the old per-CPU counters to reach zero.
	 * Denoted by "Z".
	 */
	rcu_try_flip_waitzero_state,

	/*
	 * Wait here for each of the other CPUs to execute a memory barrier.
	 * This is necessary to ensure that these other CPUs really have
	 * completed executing their RCU read-side critical sections, despite
	 * their CPUs wildly reordering memory. Denoted by "M".
	 */
	rcu_try_flip_waitmb_state,
};

struct rcu_ctrlblk {
	spinlock_t	fliplock;	/* Protect state-machine transitions. */
	long		completed;	/* Number of last completed batch. */
	enum rcu_try_flip_states rcu_try_flip_state; /* The current state of
							the rcu state machine */
};

static DEFINE_PER_CPU(struct rcu_data, rcu_data);
static struct rcu_ctrlblk rcu_ctrlblk = {
	.fliplock = __SPIN_LOCK_UNLOCKED(rcu_ctrlblk.fliplock),
	.completed = 0,
	.rcu_try_flip_state = rcu_try_flip_idle_state,
};


#ifdef CONFIG_RCU_TRACE
static char *rcu_try_flip_state_names[] =
	{ "idle", "waitack", "waitzero", "waitmb" };
#endif /* #ifdef CONFIG_RCU_TRACE */

static cpumask_t rcu_cpu_online_map __read_mostly = CPU_MASK_NONE;

/*
 * Enum and per-CPU flag to determine when each CPU has seen
 * the most recent counter flip.
 */

enum rcu_flip_flag_values {
	rcu_flip_seen,		/* Steady/initial state, last flip seen. */
				/* Only GP detector can update. */
	rcu_flipped		/* Flip just completed, need confirmation. */
				/* Only corresponding CPU can update. */
};
static DEFINE_PER_CPU_SHARED_ALIGNED(enum rcu_flip_flag_values, rcu_flip_flag)
								= rcu_flip_seen;

/*
 * Enum and per-CPU flag to determine when each CPU has executed the
 * needed memory barrier to fence in memory references from its last RCU
 * read-side critical section in the just-completed grace period.
 */

enum rcu_mb_flag_values {
	rcu_mb_done,		/* Steady/initial state, no mb()s required. */
				/* Only GP detector can update. */
	rcu_mb_needed		/* Flip just completed, need an mb(). */
				/* Only corresponding CPU can update. */
};
static DEFINE_PER_CPU_SHARED_ALIGNED(enum rcu_mb_flag_values, rcu_mb_flag)
								= rcu_mb_done;

/*
 * RCU_DATA_ME: find the current CPU's rcu_data structu