WebSVN – HelenOS – Diff – /branches/rcu/kernel/test/synch/rcu1.c

  * 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 1000
+#define RCU_MAX_I 500
+//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 (uint32_t)50
+#define THREADS_SLEEP_LENGTH 50
+//shared flag specifying whether we should be quiet
 bool gquiet;
+//count of finished threads
-volatile bool finished;
+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)
+    {
-        i = 0;
+        //entering read critical section
         rcu_read_lock();
+        //proper dereferencing
+        i = rcu_dereference_pointer(first).number;
-        for (cur = rcu_dereference_pointer(first).next; cur != first; cur = cur->next) {
+        for (cur = rcu_dereference_pointer(first).next; cur != NULL; cur = cur->next) {
-            i += rcu_dereference_pointer(cur).number;
+            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)
+{
     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
-        i = rcu_dereference_pointer(first).number;
+        rcudata = malloc(sizeof(rcu_callback_list_t),0);
         rcu_read_lock();
-        printf("a2 ");
+        i = rcu_dereference_pointer(first).number;
-        for (cur = rcu_dereference_pointer(first).next; cur != first; cur = rcu_dereference_pointer(cur).next) {
+        for (cur = rcu_dereference_pointer(first).next; cur != NULL; cur = cur->next) {
-            i += rcu_dereference_pointer(cur).number;
+            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 ");
+        if (!gquiet)
-        rcu_sync_callback(&rcu_callback_free, oldata, rcudata);
+            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();
+        //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 = rcu_dereference_pointer(first).next; rcu_dereference_pointer(cur).number % 5 != 4 && cur != first; cur = rcu_dereference_pointer(cur).next) {
+        for (cur = first; cur->next != NULL && cur->next->number >= (i/(RCU_MAX_I/2)); cur = rcu_dereference_pointer(cur).next) {
+        }
-        if (cur != first){
+        if (cur->next != NULL) {
-            //delete the cur->next
+            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;
-            spinlock_lock(&write_lock);
+            newdata->next = cur->next->next;
-            oldata = rcu_dereference_pointer(cur).next;
+            oldata = cur->next;
+            if (!gquiet)
-            newdata->next = rcu_dereference_pointer(rcu_dereference_pointer(cur).next).next;
+                printf("free:%x,n:%d ", cur->next, cur->next->number);
-            rcu_assign_pointer(rcu_dereference_pointer(cur).next, newdata);
+            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);
+    }
-    finished = true;
+    cfinished++;
+}
 char * test_rcu1(bool quiet)
+{
     gquiet = quiet;
     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->number = 0;
-    first->next = first;
+    cur = first;
+    for (i=1;i<RCU_MAX_I;i++) {
-    threads = malloc(sizeof(thread_t*),0);
+        cur->next = malloc(sizeof(data_t),0);
+        cur = cur->next;
+        cur->number = i;
+    }
-    finished = false;
+    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);
+    }
+    //wait for completion
-    for (i=0;i<WRITER_THREADS+READER_THREADS;i++)
+    while (cfinished<WRITER_THREADS+READER_THREADS);
-        thread_join(threads[i]);
+    printf("\nfinished all threads!\n");
+    //free the list
-    for(cur=first->next;cur->next!=first;) {
+    for(cur=first->next;cur!=NULL;) {
         oldata = cur->next;
         free(cur);
         cur = oldata;
+    }
     free(first);

Subversion Repositories HelenOS

(root)/branches/rcu/kernel/test/synch/rcu1.c – Rev 2400 → 2430