/*
* 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)
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)
if (i>RCU_MAX_I*RCU_MAX_I || cfinished>0) {
if (!gquiet)
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;
cur = oldata;
}
return NULL;
}