WebSVN – HelenOS – Path Comparison – / – /branches/rcu/kernel/test/ Rev 2429 and /branches/rcu/kernel/test/ Rev 2430

Ignore whitespace Rev 2429 → Rev 2430

 /branches/rcu/kernel/test/synch/rcu1.c
 ,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>
 ,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;
 ,7 → 63,7
 SPINLOCK_INITIALIZE(write_lock);
+/** this thread will try to read from the list */
 static void reader(void* a)
 {
     a = (a);
 ,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)
 ,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)
 ,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;

/branches/rcu/kernel/test/synch/rcu1.def
1,6 → 1,6
{
"rcu1",
"RCU test (very basic)",
"RCU test",
&test_rcu1,
true
},

Subversion Repositories HelenOS

Compare Revisions

Ignore whitespace Rev 2429 → Rev 2430