/*
 * Copyright (c) 2007 Jan Hudecek
 * Copyright (c) 2006 Jakub Jermar
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * - Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 * - The name of the author may not be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
/** @addtogroup sync
 * @{
 */
/** @file
 */

#include <synch/rcu.h>
#include <synch/waitq.h>
#include <arch.h>
#include <config.h>
#include <arch/types.h>
#include <proc/tasklet.h>
#include <synch/spinlock.h>
#include <time/delay.h>
#include <panic.h>
#include <print.h>




typedef struct  {
#ifdef CONFIG_SMP 
	bool* cpu_mask;
#endif
	rcu_callback_list_t* next_batch, *current_batch, *done_batch;
} rcu_global_t;

/** An array of structures holding the callbacks and the progress of QS for each CPU*/
rcu_global_t* rcu_global=NULL;
/** reference to the RCU tasklet, for scheduling it */
tasklet_descriptor_t* rcu_tasklet_desc;


/**
* Initializes data structures needed for RCU
*/
void rcu_init(void) 
{
#ifdef CONFIG_SMP 
	int i,j;
#endif

	rcu_global = malloc(sizeof(rcu_global_t)*(config.cpu_count),0);
	rcu_tasklet_desc = tasklet_register(&rcu_tasklet, NULL);

#ifdef CONFIG_SMP 
	/*
	 * Note: I allocate the array for a case when every CPU connected will be active
	 * In a case when there will be some inactive CPUs, I will use just the first cells.
	 */
	for (i=0;i<config.cpu_count;i++) {
		rcu_global[i].done_batch = NULL;
		rcu_global[i].current_batch = NULL;
		rcu_global[i].next_batch = NULL;
		rcu_global[i].cpu_mask = malloc(sizeof(bool)*config.cpu_count,0);
		for (j=0;j<config.cpu_count;j++) {
			rcu_global[i].cpu_mask[j]=false;
		}
	}
#else
	rcu_global[CPU->id].done_batch = NULL;
	rcu_global[CPU->id].current_batch = NULL;
	rcu_global[CPU->id].next_batch = NULL;
#endif
}


/**
* Blocks until the grace period elapses
*/
void rcu_synchronize(void)
{
#ifdef CONFIG_SMP
	waitq_t wq;
	waitq_initialize(&wq);
	rcu_sync_callback(&rcu_synchronize_callback_function, &wq);
	//sleep until the end of the grace period
	waitq_sleep(&wq);
#endif
}

#ifdef CONFIG_SMP
/**
* Just a wakeup for waking up rcu_synchronize when the grace period has elapsed
*/
void rcu_synchronize_callback_function(void* waitq)
{
	waitq_wakeup(((waitq_t*)waitq), WAKEUP_ALL);
}
#endif


/**
* appends this callback func to the queue of waiting callbacks, the rest 
* is handled in rcu_run_callbacks and in the tasklet. This is a lock free variant,
* which must be supplied with a preallocated rcu_callback_list_t structure
*/
void rcu_sync_callback_custom_alloc(void (*func)(void* data), void* data, rcu_callback_list_t* rd)
{
#ifndef CONFIG_SMP
	func(data);
#else

	ipl_t ipl;
	rd->func = func;
	rd->data = data;

	ipl = interrupts_disable();
	//append to the list of callbacks waiting for their batch to begin
	rd->next = rcu_global[CPU->id].next_batch;
	rcu_global[CPU->id].next_batch = rd;
	interrupts_restore(ipl);

	rcu_passQS(); 
#endif
}

/**
* RCU tasklet, tests passing through QSs, moves from current to done
*/
void rcu_tasklet(void* data)
{
	rcu_callback_list_t* rd;
	bool passed_all_QS;
#ifdef CONFIG_SMP 
	int i;
#endif
	ipl_t ipl;

	ipl = interrupts_disable();

	rcu_passQS();
	passed_all_QS = true;
#ifdef CONFIG_SMP 
	//check whether all CPUs have passed through QS
	for (i = 0; i < config.cpu_active; i++)
		passed_all_QS &= rcu_global[CPU->id].cpu_mask[i];
#endif
	if (passed_all_QS) {
		//all CPUs have passed through QS -> grace period is over, we can schedule the call to RCU callback
		if (rcu_global[CPU->id].done_batch) {
			rd = rcu_global[CPU->id].done_batch;
			while (rd->next) rd = rd->next;
			//append the current list to done list
			rd->next = rcu_global[CPU->id].current_batch;
		} else 
			rcu_global[CPU->id].done_batch = rcu_global[CPU->id].current_batch;
		rcu_global[CPU->id].current_batch = NULL;
	}
	interrupts_restore(ipl);
}


/**
* This function indicates that the current CPU has gone through the quiescent state
*/
void rcu_passQS(void)
{
#ifdef CONFIG_SMP 
	int i;
	for (i=0;i<config.cpu_active;i++)
		//on all CPUs indicate that this CPU has gone through QS
		rcu_global[i].cpu_mask[CPU->id]=true;
#endif
}


/** 
* Moves RCUs from next to current, schedules RCU tasklet, calls the callbacks, frees the rcu_callback_list_t
*/
void rcu_run_callbacks(void)
{
	rcu_callback_list_t* rd, *rd2;
	int i;
	ipl_t ipl;

	ipl = interrupts_disable();
	if (rcu_global[CPU->id].next_batch) {
		//we cannot append to the current list because callbacks from next batch
		//haven't passed the QSs
		if (rcu_global[CPU->id].current_batch == NULL) {
			rcu_global[CPU->id].current_batch = rcu_global[CPU->id].next_batch;
			rcu_global[CPU->id].next_batch = NULL;
#ifdef CONFIG_SMP
			//initialize our CPU mask
			for (i=0;i<config.cpu_active;i++)
				rcu_global[CPU->id].cpu_mask[i]=false;
#endif
			//schedule tasklet for all CPUs
			for (i=0;i<config.cpu_active;i++) {
				tasklet_schedule_SMP(rcu_tasklet_desc, i);
			}
		} 
	}
	//this CPU has passed QS
	rcu_passQS();
	if (rcu_global[CPU->id].done_batch) {
		rd = rcu_global[CPU->id].done_batch;
		rcu_global[CPU->id].done_batch = NULL;
		interrupts_restore(ipl);
		while (rd) {
			//call the callback
			rd->func(rd->data);
			rd2 = rd->next;
			//free the structure
			free(rd);
			rd = rd2;
		}
	}
	else
		interrupts_restore(ipl);
}