Subversion Repositories HelenOS

/*

 * 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 rcu.c

 *  @brief RCU synchronization primitive

 */

#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>

/** Main data structure of the RCU implementation */

typedef struct  {

#ifdef CONFIG_SMP 

    /** flags indicating whether the corresponding CPU has passed QS for this RCU batch */

    bool* cpu_mask;

#endif

    /** RCU batch waiting for finishing of current batch, QS monitoring hasn't been started for this one */

    rcu_callback_list_t* next_batch;

    /** RCU batch that waits for passing of QSs on all CPUs */

    rcu_callback_list_t *current_batch;

    /** RCU batch that has passed all QSs and waits for invocation */

    rcu_callback_list_t *done_batch;

} rcu_cpu_data_t;

/** An array of structures holding the callbacks and the progress of QS for each CPU*/

rcu_cpu_data_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_cpu_data_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 active ones

     */

    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_normal_alloc(&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

* which is deallocated after the callback is called

*/

void rcu_sync_callback(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;

    //disabling interrupts removes need for any synchronization - the list of callbacks is 

    //always accessed only on current CPU

    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;

    rcu_passQS();

    interrupts_restore(ipl);

#endif

}

/**

* RCU tasklet, tests passing through QSs, moves from current list to done list

*/

void rcu_tasklet(void* data)

{

    rcu_callback_list_t* rd;

    bool passed_all_QS;

#ifdef CONFIG_SMP 

    int i;

#endif

    ipl_t ipl;

    passed_all_QS = true;

    ipl = interrupts_disable();

    rcu_passQS();

#ifdef CONFIG_SMP 

    //check whether all CPUs have passed through QS of this CPU's current batch

    for (i = 0; i < config.cpu_count; i++)

        if (cpus[i].active)

            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_count; i++)

        if (cpus[i].active)

            //on all CPUs indicate that this CPU has gone through QS

            //this can overlap with clearing this flag in rcu_run_callbacks

            rcu_global[i].cpu_mask[CPU->id]=true;

#endif

}

/**

* Moves RCU callbacks from next list to current list, schedules the RCU tasklet when needed,

* calls the callbacks from done list, 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 the 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_count; i++)

                if (cpus[i].active)

                    rcu_global[CPU->id].cpu_mask[i]=false;

#endif

            //schedule tasklet for all CPUs

            for (i = 0; i < config.cpu_count; i++)

                if (cpus[i].active)

                    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;

        //the callbacks (and free) can block, we must restore the interrupts

        interrupts_restore(ipl);

        while (rd) {

            //call the callback

            if (rd->func == NULL)

                panic_printf("RCU callback function NULL, desc:%x", rd);

            rd->func(rd->data);

            rd2 = rd->next;

            //free the structure

            free(rd);

            rd = rd2;

        }

    }

    else

        interrupts_restore(ipl);

}

/**

* Generic callback for RCU, frees @paramref pointer

* @param pointer

*/

void rcu_callback_free(void* pointer)

{

    free(pointer);

}