Subversion Repositories HelenOS

/*

 * 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;

}