/*
 * Copyright (c) 2007 Jan Hudecek
 * Copyright (c) 2005 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.
 */


/* This is RCU thorough test. It should provide basic guidelines on how to use 
this implementation of RCU */ 

#include <synch/rcu.h>
#include <print.h>
#include <test.h>
#include <arch/types.h>
#include <proc/tasklet.h>
#include <arch/barrier.h>
#include <arch.h>
#include <preemption.h>
#include <proc/thread.h>

//number of nodes in the list. The sum of the list will grow up to RCU_MAX_I^2
#define RCU_MAX_I 5000
//number of reader and writer threads in the test
#define READER_THREADS 10
#define WRITER_THREADS 10
//a sleep separates iterations of reading 
#define THREADS_SLEEP_LENGTH 50

//shared flag specifying whether we should be quiet
bool gquiet;
//count of finished threads
volatile int cfinished;
//the list we will manage with RCU
typedef struct data_struc {
	int number;
	struct data_struc* next; 
} data_t;

data_t* first;
SPINLOCK_INITIALIZE(write_lock);


/** this thread will try to read from the list */
static void reader(void* a)
{
	a = (a);
	data_t* cur;
	int i = 0;
	while (true) {
		//entering read critical section
		rcu_read_lock();
		//proper dereferencing
		i = rcu_dereference_pointer(first).number;
		for (cur = rcu_dereference_pointer(first).next; cur != NULL; cur = cur->next) {
			i += cur->number;
		}
		rcu_read_unlock();
		if (i>RCU_MAX_I*RCU_MAX_I || cfinished>0) {
			if (!gquiet)
				printf("@");
			break;
		}
		thread_usleep(THREADS_SLEEP_LENGTH);
	}
	//we must achieve some kind of synchronization gcc wont emit inc [cfinished]
	spinlock_lock(&write_lock);
	cfinished++;
	spinlock_unlock(&write_lock);
}

static void writer(void* a)
{
	a = (a);
	data_t* cur;
	data_t* newdata;
	data_t* oldata;
	rcu_callback_list_t* rcudata;
	int i = 0;
	while (true) {
		//we must allocate the rcu structure each time, because it gets freed after the callback
		//we allocate it outside any critical section, as it could block
		rcudata = malloc(sizeof(rcu_callback_list_t),0);
		rcu_read_lock();
		i = rcu_dereference_pointer(first).number;
		for (cur = rcu_dereference_pointer(first).next; cur != NULL; cur = cur->next) {
			i += cur->number;
		}
		rcu_read_unlock();
		if (!gquiet && false)
			printf("i%d ",i);
		if (i>RCU_MAX_I*RCU_MAX_I || cfinished>0) {
			if (!gquiet)
				printf("!");
			break;
		}

		//insert a new member 
		newdata = malloc(sizeof(data_t),0);
		newdata->number = (i/(RCU_MAX_I/2))+1;
		//we have to acquire the lock for writing to the structure
		spinlock_lock(&write_lock);
		newdata->next = first;
		//rcu_assign_pointer takes care of the necessary write barriers
		rcu_assign_pointer(first, newdata);
		if (!gquiet && false)
			printf("prepending:%x,n:%d ", newdata, newdata->number);
		spinlock_unlock(&write_lock);


		//replace a random member
		//we have to lock the spinlock now, because we'll use the cur pointer later 
		//RCU doesn't provide guarantee that cur->next will point to a member of the list
		//note that read critical section DOES guarantee that the *cur will be allocated space
		//with current or past version of some member of the list
		//However, that is not sufficient as we would be changing old version, which would be freed later on
		spinlock_lock(&write_lock);
		for (cur = first; cur->next != NULL && cur->next->number >= (i/(RCU_MAX_I/2)); cur = rcu_dereference_pointer(cur).next) {
		}
		if (cur->next != NULL) {
			newdata = malloc(sizeof(data_t),0);
			//the change of number member could be done atomically, its here just to simulate some real work
			newdata->number = (i/(RCU_MAX_I/2))+10;
			newdata->next = cur->next->next;
			oldata = cur->next;
			if (!gquiet && false)
				printf("free:%x,n:%d ", cur->next, cur->next->number);
			rcu_assign_pointer(cur->next, newdata);
			//free the old member when it is safe (i.e. no references are held)
			rcu_sync_callback(&rcu_callback_free, oldata, rcudata);
			spinlock_unlock(&write_lock);
		}
	}
	//we must achieve some kind of synchronization gcc wont emit inc [cfinished]
	spinlock_lock(&write_lock);
	cfinished++;
	spinlock_unlock(&write_lock);
}

char * test_rcu1(bool quiet)
{
	gquiet = quiet;
	data_t* cur, *oldata;
	int i;
	thread_t* t;

	//allocate and initialize the list
	first = malloc(sizeof(data_t),0);
	first->number = 0;
	cur = first;
	for (i=1;i<RCU_MAX_I;i++) {
		cur->next = malloc(sizeof(data_t),0);
		cur = cur->next;
		cur->number = i;
	}
	cur->next = NULL;

	//initialize the counter of finished threads
	cfinished=0;

	//start the writers
	for(i = 0; i< WRITER_THREADS; i++) {
		t=thread_create(writer,NULL, TASK, 0, "writerthread", false );
		if (t != NULL)
			thread_ready(t);
	}

	//start the readers
	for(i = 0; i< READER_THREADS; i++) {
		t=thread_create(reader,NULL, TASK, 0, "readerthread", false );
		if (t != NULL)
			thread_ready(t);
	}
	//wait for completion
	while (cfinished<WRITER_THREADS+READER_THREADS);
	if (!gquiet)
		printf("\nfinished all threads!\n");
	//free the list
	for(cur=first->next;cur!=NULL;) {
		oldata = cur->next;
		free(cur);
		cur = oldata;
	}
	free(first);
	return NULL;

}