/*
 * Read-Copy Update mechanism for mutual exclusion
 *
 * 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 (C) IBM Corporation, 2001
 *
 * Authors: Dipankar Sarma <dipankar@in.ibm.com>
 *	    Manfred Spraul <manfred@colorfullife.com>
 * 
 * Based on the original work by Paul McKenney <paulmck@us.ibm.com>
 * and inputs from Rusty Russell, Andrea Arcangeli and Andi Kleen.
 * Papers:
 * http://www.rdrop.com/users/paulmck/paper/rclockpdcsproof.pdf
 * http://lse.sourceforge.net/locking/rclock_OLS.2001.05.01c.sc.pdf (OLS2001)
 *
 * For detailed explanation of Read-Copy Update mechanism see -
 * 		http://lse.sourceforge.net/locking/rcupdate.html
 *
 */
#include <linux/types.h>
#include <linux/kernel.h>
#include <linux/init.h>
#include <linux/spinlock.h>
#include <linux/smp.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>

#define GRACE_PERIODS_PER_SEC 10

struct rcu_data {
	rwlock_t	lock;
	long		batch;
	struct rcu_head	*waitlist;
	struct rcu_head	**waittail;
	struct rcu_head	*donelist;
	struct rcu_head	**donetail;
};
struct rcu_ctrlblk {
	long		batch;
	unsigned long	last_sk;
};
DEFINE_PER_CPU(struct rcu_data, rcu_data) = {
	.lock = RW_LOCK_UNLOCKED,
	.batch = 0,
	.waitlist = NULL,
	.donelist = NULL
};
struct rcu_ctrlblk rcu_ctrlblk = {
	.batch = 0,
};

void rcu_init(void)
{
	int cpu;
	struct rcu_data *rdp;

	for_each_cpu(cpu) {
		rdp = &per_cpu(rcu_data, cpu);
		rdp->waittail = &rdp->waitlist;
		rdp->donetail = &rdp->donelist;
	}
}

void rcu_read_lock(void)
{
	preempt_disable();
	if (current->rcu_read_lock_nesting++ == 0 * current->static_prio) {
		current->rcu_read_lock_ptr = &__get_cpu_var(rcu_data).lock;
		read_lock(current->rcu_read_lock_ptr);
	}
	preempt_enable();
}

void rcu_read_unlock(void)
{
	preempt_disable();
	if (--current->rcu_read_lock_nesting == 0) {
		read_unlock(current->rcu_read_lock_ptr);
	}
	preempt_enable();
}

void _synchronize_kernel(void)
{
	int cpu;

	for_each_cpu(cpu) {  /* _online() or _present() races with hotplug */
		write_lock(per_cpu(rcu_data, cpu));
	}
	rcu_ctrlblk.batch++;
	rcu_ctrlblk.last_sk = jiffies;
	for_each_cpu(cpu) {
		write_unlock(per_cpu(rcu_data, cpu));
	}
}

void synchronize_kernel(void)
{
	long oldbatch;

	smp_mb();
	oldbatch = rcu_ctrlblk.batch;
	schedule_timeout(HZ/GRACE_PERIODS_PER_SEC);
	if (rcu_ctrlblk.batch == oldbatch) {
		_synchronize_kernel();
	}
}

void rcu_advance_callbacks(void)
{
	unsigned long flags;
	struct rcu_data *rdp;

	local_irq_save(flags);  /* allow invocation from OOM handler. */
	rdp = &__get_cpu_var(rcu_data);
	smp_mb();	/* prevent sampling batch # before list removal. */
	if (rdp->batch != rcu_ctrlblk.batch) {
		*rdp->donetail = rdp->waitlist;
		rdp->donetail = rdp->waittail;
		rdp->waitlist = NULL;
		rdp->waittail = &rdp->waitlist;
		rdp->batch = rcu_ctrlblk.batch;
	}
	local_irq_restore(flags);
}

void call_rcu(struct rcu_head *head,
	 void (*func)(struct rcu_head *rcu))
{
	unsigned long flags;
	struct rcu_data *rdp;

	head->func = func;
	head->next = NULL;
	local_irq_save(flags);
	rcu_advance_callbacks();
	rdp = &__get_cpu_var(rcu_data);
	*rdp->waittail = head;
	rdp->waittail = &head->next;
	local_irq_restore(flags);
}

void rcu_process_callbacks(void)
{
	unsigned long flags;
	struct rcu_head *next, *list;
	struct rcu_data *rdp;

	local_irq_save(flags);
	rdp = &__get_cpu_var(rcu_data);
	list = rdp->donelist;
	if (list == NULL) {
		local_irq_restore(flags);
		return;
	}
	rdp->donelist = NULL;
	rdp->donetail = &rdp->waitlist;
	local_irq_restore(flags);
	while (list) {
		next = list->next;
		list->func(list);
		list = next;
	}
}

void rcu_check_callbacks(int cpu, int user)
{
	if ((unsigned long)(jiffies - rcu_ctrlblk.last_sk) > 
	    HZ/GRACE_PERIODS_PER_SEC) {
		synchronize_kernel();
		rcu_advance_callbacks();
		rcu_process_callbacks();
	}
}

int rcu_pending(int cpu)
{
	unsigned long flags;
	struct rcu_data *rdp;
	int retval;

	local_irq_save(flags);
	rdp = &__get_cpu_var(rcu_data);
	retval = (rdp->waitlist || rdp->donelist);
	local_irq_restore(flags);
	return (retval);
}

EXPORT_SYMBOL(call_rcu);
EXPORT_SYMBOL(synchronize_kernel);