27,6 → 27,10 |
* 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> |
37,14 → 41,19 |
#include <preemption.h> |
#include <proc/thread.h> |
|
|
#define RCU_MAX_I 1000 |
//number of nodes in the list. The sum of the list will grow up to RCU_MAX_I^2 |
#define RCU_MAX_I 500 |
//number of reader and writer threads in the test |
#define READER_THREADS 10 |
#define WRITER_THREADS 10 |
#define THREADS_SLEEP_LENGTH (uint32_t)50 |
//a sleep separates iterations of reading |
#define THREADS_SLEEP_LENGTH 50 |
|
//shared flag specifying whether we should be quiet |
bool gquiet; |
volatile bool finished; |
//count of finished threads |
volatile int cfinished; |
//the list we will manage with RCU |
typedef struct data_struc { |
int number; |
struct data_struc* next; |
54,7 → 63,7 |
SPINLOCK_INITIALIZE(write_lock); |
|
|
|
/** this thread will try to read from the list */ |
static void reader(void* a) |
{ |
a = (a); |
62,20 → 71,22 |
int i = 0; |
while (true) |
{ |
i = 0; |
//entering read critical section |
rcu_read_lock(); |
for (cur = rcu_dereference_pointer(first).next; cur != first; cur = cur->next) { |
i += rcu_dereference_pointer(cur).number; |
//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(); |
thread_usleep(THREADS_SLEEP_LENGTH); |
if (i>RCU_MAX_I || finished) |
if (i>RCU_MAX_I*RCU_MAX_I || cfinished>0) |
{ |
printf("@"); |
break; |
} |
thread_usleep(THREADS_SLEEP_LENGTH); |
} |
finished = true; |
cfinished++; |
} |
|
static void writer(void* a) |
82,70 → 93,70 |
{ |
a = (a); |
data_t* cur; |
data_t* newdata, *oldata; |
data_t* newdata; |
data_t* oldata; |
rcu_callback_list_t* rcudata; |
int i = 0; |
printf("a1 "); |
rcudata = malloc(sizeof(rcu_callback_list_t),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; |
rcu_read_lock(); |
printf("a2 "); |
for (cur = rcu_dereference_pointer(first).next; cur != first; cur = rcu_dereference_pointer(cur).next) { |
i += rcu_dereference_pointer(cur).number; |
for (cur = rcu_dereference_pointer(first).next; cur != NULL; cur = cur->next) { |
i += cur->number; |
} |
rcu_read_unlock(); |
if (!gquiet) |
printf("i%d ",i); |
if (i>RCU_MAX_I || finished) |
if (i>RCU_MAX_I*RCU_MAX_I || cfinished>0) |
{ |
printf("!"); |
break; |
} |
printf("a2b "); |
thread_usleep(THREADS_SLEEP_LENGTH); |
|
printf("a3 "); |
//insert a new member |
newdata = malloc(sizeof(data_t),0); |
printf("a4 "); |
newdata->number = (i/(RCU_MAX_I/2))+1; |
rcu_read_lock(); |
//prepend a new member |
//we have to acquire the lock for writing to the structure |
spinlock_lock(&write_lock); |
printf("a5 "); |
newdata->number = (i/10)+1; |
oldata = first; |
newdata->next = first; |
//rcu_assign_pointer takes care of the necessary write barriers |
rcu_assign_pointer(first, newdata); |
printf("a6 "); |
rcu_sync_callback(&rcu_callback_free, oldata, rcudata); |
if (!gquiet) |
printf("prepending:%x,n:%d ", newdata, newdata->number); |
spinlock_unlock(&write_lock); |
printf("a7 "); |
rcu_read_unlock(); |
thread_usleep(THREADS_SLEEP_LENGTH); |
printf("a8 "); |
if (!gquiet) |
printf(".",i); |
|
|
//replace a random member |
rcu_read_lock(); |
for (cur = rcu_dereference_pointer(first).next; rcu_dereference_pointer(cur).number % 5 != 4 && cur != first; cur = rcu_dereference_pointer(cur).next) { |
//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 != first){ |
//delete the cur->next |
spinlock_lock(&write_lock); |
oldata = rcu_dereference_pointer(cur).next; |
newdata->next = rcu_dereference_pointer(rcu_dereference_pointer(cur).next).next; |
rcu_assign_pointer(rcu_dereference_pointer(cur).next, newdata); |
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))+5; |
newdata->next = cur->next->next; |
oldata = cur->next; |
if (!gquiet) |
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); |
if (!gquiet) |
printf(", ",i); |
|
} |
rcu_read_unlock(); |
thread_usleep(THREADS_SLEEP_LENGTH); |
rcu_read_unlock(); |
} |
finished = true; |
cfinished++; |
} |
|
char * test_rcu1(bool quiet) |
154,29 → 165,39 |
data_t* cur, *oldata; |
int i; |
thread_t* t; |
thread_t** threads; |
|
//allocate and initialize the list |
first = malloc(sizeof(data_t),0); |
first->number = 10; |
first->next = first; |
threads = malloc(sizeof(thread_t*),0); |
finished = false; |
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++) { |
threads[i]=t=thread_create(writer,NULL, TASK, 0, "writerthread", false ); |
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++) { |
threads[WRITER_THREADS+i]=t=thread_create(reader,NULL, TASK, 0, "readerthread", false ); |
t=thread_create(reader,NULL, TASK, 0, "readerthread", false ); |
if (t != NULL) |
thread_ready(t); |
} |
|
for (i=0;i<WRITER_THREADS+READER_THREADS;i++) |
thread_join(threads[i]); |
|
for(cur=first->next;cur->next!=first;) { |
//wait for completion |
while (cfinished<WRITER_THREADS+READER_THREADS); |
printf("\nfinished all threads!\n"); |
//free the list |
for(cur=first->next;cur!=NULL;) { |
oldata = cur->next; |
free(cur); |
cur = oldata; |