Anonymous avatar Anonymous committed fd9df12

Added test_rwlock_2.c to test for a bug which is now corrected.

Thanks to Luo Lei!

Comments (0)

Files changed (6)

 Shlomi Fish ( http://www.shlomifish.org/ ) - wrote most of the code.
 
-Eric D Crahen (of http://zthread.sourceforge.net/ )- Inspired me to implement 
+Eric D Crahen (of http://zthread.sourceforge.net/ ) - Inspired me to implement 
 Run-Length Encoding for the lock.
 
 Luo Lei - pointed out that pthread_rwlock_fcfs_destroy() was not implemented
-, which was remedied in the 0.6.0 release.
+, which was remedied in the 0.6.0 release. Afterwards, pointed out a bug
+by writing a test case that failed (and was incorporated into the code)
+that was fixed in the 0.8.0 release.

pthreads/CMakeLists.txt

 
 TARGET_LINK_LIBRARIES (test_rwlock pthread_rwlock_fcfs)
 
+ADD_EXECUTABLE (test_rwlock_2
+    test_rwlock_2.c
+)
+
+TARGET_LINK_LIBRARIES (test_rwlock_2 pthread_rwlock_fcfs)
+
 INSTALL(
     FILES
         "AUTHORS"
     runtime
     ./test_rwlock --timeout 5
 )
+
+ADD_TEST(
+    runtime2
+    ./test_rwlock_2 --timeout 5
+)

pthreads/pthread/rwlock_fcfs.h

     int is_writer;
     /* A flag that disables this item */
     int is_disabled;
-    /* An integer specifiying how many threads are waiting on it */
+    /* An integer specifying how many threads are waiting on it */
     int num_threads;
     /* A flag that indicates if the first thread in the pack has already
      * been accepted. (Used only for a writers' pack */
 
 typedef struct pthread_rwlock_fcfs_item_struct pthread_rwlock_fcfs_item_t;
 
+enum pthread_rwlock_fcfs_status
+{
+    PTHREAD_RWLOCK_FCFS_UNLOCKED,
+    PTHREAD_RWLOCK_FCFS_USED_BY_READERS,
+    PTHREAD_RWLOCK_FCFS_USED_BY_A_WRITER,
+};
+
 /* The RWLock Struct */
 struct pthread_rwlock_fcfs_struct
 {
     pthread_rwlock_fcfs_queue_t * queue;
     /* The number of readers that are using the RWLock at the moment */
     int num_readers;
-    /* Specifies if there is a writer locking the RWLock */
-    int is_writer;
+    /* The number of pending readers that didn't gain access 
+     * to the lock yet. */
+    int num_pending_readers;
+    /* Specifies if there is a writer locking the RWLock, some
+     * readers or if it's un-occupied. */
+    enum pthread_rwlock_fcfs_status status;
     /* A mutex to make sure no two threads _modify_ the RWLock struct
      * at the moment */
     pthread_mutex_t mutex;

pthreads/rwlock.c

 {
     printf("%s - %s\n", id, msg);
     printf("    Status: rwlock.num_readers == %i\n", rwlock->num_readers);
-    printf("    Status: rwlock.is_writer == %i\n", rwlock->is_writer);
+    printf("    Status: rwlock.num_pending_readers == %i\n", rwlock->num_pending_readers);
+    printf("    Status: rwlock.status == %i\n", rwlock->status);
     {
         int a;
         pthread_rwlock_fcfs_queue_item_t * q_item;
 
     /* We don't have any readers now. */
     rwlock->num_readers = 0;
+    rwlock->num_pending_readers = 0;
+
     /* Much less a writer */
-    rwlock->is_writer = 0;
+    rwlock->status = PTHREAD_RWLOCK_FCFS_UNLOCKED;
+
     /* This RWLock is alive and kicking */
     rwlock->is_destroyed = 0;
 
 
     /* If there aren't any readers or writers in the queue we
      * can gain access immidiately */
-    if (rwlock->is_writer || (rwlock->num_readers > 0))
+    if (rwlock->status != PTHREAD_RWLOCK_FCFS_UNLOCKED)
     {
         pthread_rwlock_fcfs_item_t * item;
 
 
         }
 
-
         /* Wait upon the condition variable to gain access to the rwlock */
         if (! is_timed)
         {
             }
         }
 
+        /* accept_pending_items is doing it for us. */
+#if 0
         /* Now we have a write access */
         rwlock->is_writer = 1;
+#endif
 
         return 0;
     }
     else
     {
         /* Mark the lock as such that contains a writer */
-        rwlock->is_writer = 1;
+        rwlock->status = PTHREAD_RWLOCK_FCFS_USED_BY_A_WRITER;
 
         return 0;
     }
 
     pthread_mutex_lock(&(rwlock->mutex));
 
-    my_debug_print(rwlock, id, "Want Lock!");
+    my_debug_print(rwlock, id, "Want Write Lock!");
 
     ret = gain_write_generic(rwlock, 0, 1, 0, NULL, NULL, NULL);
 
-    my_debug_print(rwlock, id, "Lock!");
+    my_debug_print(rwlock, id, "Gained Write Lock!");
 
     pthread_mutex_unlock(&(rwlock->mutex));
 
 
     pthread_mutex_lock(&(rwlock->mutex));
 
-    my_debug_print(rwlock, id, "Want Lock!");
+    my_debug_print(rwlock, id, "Want Write-Destroy Lock!");
 
     ret = gain_write_generic(rwlock, 1, 1, 0, NULL, NULL, NULL);
 
-    my_debug_print(rwlock, id, "Lock!");
+    my_debug_print(rwlock, id, "Gained Write-Destroy Lock!");
 
     pthread_mutex_unlock(&(rwlock->mutex));
 
 
     pthread_mutex_lock(&(rwlock->mutex));
 
-    my_debug_print(rwlock, id, "Want Try Lock!");
+    my_debug_print(rwlock, id, "Want Try Write Lock!");
 
     ret = gain_write_generic(rwlock, 0, 0, 0, NULL, NULL, NULL);
 
-    my_debug_print(rwlock, id, ((ret == 0)? "Lock!" : "Failed Lock!"));
+    my_debug_print(rwlock, id, 
+            ((ret == 0)
+             ? "Gained Tried Write Lock!"
+             : "Failed Tried Write Lock!")
+            );
 
     pthread_mutex_unlock(&(rwlock->mutex));
 
  * order to accept the next round of pending items. By round, I mean
  * either an arbitrary number of readers or a single writer.
  * */
-static void accept_pending_items(pthread_rwlock_fcfs_t * rwlock)
+static void accept_pending_items(pthread_rwlock_fcfs_t * rwlock PTHREAD_RWLOCK_FCFS_DEBUG_ARGS)
 {
     pthread_rwlock_fcfs_item_t * item;
 
+    my_debug_print(rwlock, id, "accept_pending_items");
+
     extract_first_non_disabled_item();
 
+    my_debug_print(rwlock, id, 
+            (item
+             ? "accept_pending - Valid item"
+             : "accept_pending - Null Item"
+             )
+            );
+
     /* The queue is empty, so we don't need to release anything */
     if (item == NULL)
     {
         return;
     }
 
+    my_debug_print(rwlock, id, "accept_pending_items - Item is not NULL");
+
     /* Check if it's a writer or a reader */
     if (item->is_writer)
     {
+        my_debug_print(rwlock, id, "accept_pending_items - it's a writer");
         /* There is going to be one less writer waiting on the condition
          * variable */
         item->num_threads--;
         /* Prohibit other writers from joining this pack from now on */
         item->was_first_thr_accepted = 1;
         /* Release the writer. */
+        rwlock->status = PTHREAD_RWLOCK_FCFS_USED_BY_A_WRITER;
         pthread_cond_signal( &(item->cond) );
 
+        my_debug_print(rwlock, id, "accept_pending_items - signalled writer");
+
         /* Check if there are more threads pending. If not - we can extract
          * and destroy the item */
         if (item->num_threads == 0)
         {
+            my_debug_print(rwlock, id, "accept_pending_items - wrt - dequeue");
             /* We don't need the item anymore so let's deallocate it */
             dequeue_and_destroy_item();
         }
     }
     else
     {
+        my_debug_print(rwlock, id, "accept_pending_items - rd - broadcast");
         /* Release all the threads that are waiting on this item */
 
+        rwlock->status = PTHREAD_RWLOCK_FCFS_USED_BY_READERS;
+        rwlock->num_pending_readers = item->num_threads;
         pthread_cond_broadcast(& (item->cond) );
 
+        my_debug_print(rwlock, id, "accept_pending_items - rd - after broadcast");
+
         /* Destroy and extract this pack */
         dequeue_and_destroy_item();
+
+        my_debug_print(rwlock, id, "accept_pending_items - rd - dequeue");
     }
     /* I am doing it in order to remove junk from the queue. */
     extract_first_non_disabled_item();
      * If there is a writer locking the lock, than obviously he is the one
      * that releases it.
      * */
-    if (rwlock->is_writer)
+    if (rwlock->status == PTHREAD_RWLOCK_FCFS_USED_BY_A_WRITER)
     {
-        rwlock->is_writer = 0;
+        rwlock->status = PTHREAD_RWLOCK_FCFS_UNLOCKED;
 
-        accept_pending_items(rwlock);
+        accept_pending_items(rwlock PTHREAD_RWLOCK_FCFS_DEBUG_CALL_ARGS);
     }
     else
     {
 
         rwlock->num_readers--;
 
+        if (rwlock->num_readers == 0 && rwlock->num_pending_readers == 0)
+        {
+            rwlock->status = PTHREAD_RWLOCK_FCFS_UNLOCKED;
+        }
+
         /*
          * Check if the lock is now free of readers. If so, we can accept
          * pending writers.
          * */
 
-        if (rwlock->num_readers == 0)
+        if (rwlock->status == PTHREAD_RWLOCK_FCFS_UNLOCKED)
         {
-            accept_pending_items(rwlock);
+            accept_pending_items(rwlock PTHREAD_RWLOCK_FCFS_DEBUG_CALL_ARGS);
         }
     }
 
 
     pthread_mutex_lock(&(rwlock->mutex));
 
-    my_debug_print(rwlock, id, "Want Timed Lock!");
+    my_debug_print(rwlock, id, "Want Timed Write Lock!");
 
     ret = gain_write_generic(rwlock, 0, 1, 1, abstime, continue_callback, context);
 
-    my_debug_print(rwlock, id, ((ret == 0)?"Lock!": "Failed Lock!"));
+    my_debug_print(rwlock, id, 
+            ((ret == 0)
+             ? "Gained Timed Write Lock!"
+             : "Failed Timed Write Lock!"));
 
     pthread_mutex_unlock(&(rwlock->mutex));
 
      * */
     remove_junk_from_head_of_queue(rwlock);
 
-    if ((rwlock->is_writer == 0) && pthread_rwlock_fcfs_queue_is_empty(rwlock->queue))
+    if ((rwlock->status != PTHREAD_RWLOCK_FCFS_USED_BY_A_WRITER) 
+            && pthread_rwlock_fcfs_queue_is_empty(rwlock->queue))
     {
         /* Increment the number of readers. */
         rwlock->num_readers++;
         }
 
         /* Now we have a read access */
+        rwlock->num_pending_readers--;
         rwlock->num_readers++;
 
         return 0;
 
     pthread_mutex_lock(&(rwlock->mutex));
 
-    my_debug_print(rwlock, id, "Want Timed Lock!");
+    my_debug_print(rwlock, id, "Want Timed Read Lock!");
 
     ret = gain_read_generic(rwlock, 1, 1, abstime, continue_callback, context);
 
-    my_debug_print(rwlock, id, ((ret == 0) ? "Lock!" : "Failed Lock!"));
+    my_debug_print(rwlock, id, 
+            ((ret == 0) ? 
+             "Failed Timed Read Lock!" : 
+             "Failed Timed Read Lock!"
+             )
+            );
 
     pthread_mutex_unlock(&(rwlock->mutex));
 
 
     pthread_mutex_lock(&(rwlock->mutex));
 
-    my_debug_print(rwlock, id, "Want Lock!");
+    my_debug_print(rwlock, id, "Want Read Lock!");
 
     ret = gain_read_generic(rwlock, 1, 0, NULL, NULL, NULL);
 
-    my_debug_print(rwlock, id, "Lock!");
+    my_debug_print(rwlock, id, "Gained Read Lock!");
 
     pthread_mutex_unlock(&(rwlock->mutex));
 

pthreads/test_rwlock.c

             arg++;
             if (arg == argc)
             {
-                fprintf(stderr, "--num-writers accepts an argument!\n");
+                fprintf(stderr, "--timeout accepts an argument!\n");
                 exit(-1);
             }
             timeout = atoi(argv[arg]);

pthreads/test_rwlock_2.c

+/*
+ * testtest.cpp
+ *
+ * this is test case for rwlock_fcfs
+ *  Created on: Apr 12, 2009
+ *      Author: luo
+ */
+
+
+#include <stdio.h>
+#include <string.h>
+#include <pthread/rwlock_fcfs.h>
+#include <unistd.h>
+#include <stdlib.h>
+
+const int MAX_THREAD = 100;
+int to_continue = 1;
+
+pthread_rwlock_fcfs_t* lock;
+
+void * thread_work(void* attr)
+{
+    int tid = (int)attr;
+    char string[100];
+    char id[100];
+
+    sprintf(id, "TID=%d", tid);
+
+    while(to_continue)
+    {
+        pthread_rwlock_fcfs_gain_read(lock PTHREAD_RWLOCK_FCFS_DEBUG_CALL_ARGS);
+        puts("in class A");
+        sprintf(string, "tid: %d read locking", tid);
+        puts(string);
+        pthread_rwlock_fcfs_release(lock PTHREAD_RWLOCK_FCFS_DEBUG_CALL_ARGS);
+        sprintf(string, "tid: %d read release", tid);
+        puts(string);
+        pthread_rwlock_fcfs_gain_write(lock PTHREAD_RWLOCK_FCFS_DEBUG_CALL_ARGS);
+        sprintf(string, "tid: %d write locking", tid);
+        puts(string);
+        pthread_rwlock_fcfs_release(lock PTHREAD_RWLOCK_FCFS_DEBUG_CALL_ARGS);
+        sprintf(string, "tid: %d write release", tid);
+        puts(string);
+        sleep(1);
+    }
+
+    return NULL;
+}
+
+int main(int argc, char * argv[]) 
+{
+    pthread_t threads[MAX_THREAD];
+    int rc;
+    void* status;
+    int t;
+    int timeout = -1;
+    int arg;
+
+    lock = pthread_rwlock_fcfs_alloc();
+
+    for(arg=1;arg<argc;arg++)
+    {
+        if (!strcmp(argv[arg], "--timeout"))
+        {
+            arg++;
+            if (arg == argc)
+            {
+                fprintf(stderr, "--timeout accepts an argument!\n");
+                exit(-1);
+            }
+            timeout = atoi(argv[arg]);
+        }
+        else
+        {
+            fprintf(stderr, "Unknown option - \"%s\"!\n", argv[arg]);
+            exit(-1);
+        }
+    }
+
+    for (t = 0 ; t < MAX_THREAD ; t++)
+    {
+        rc = pthread_create(&threads[t], NULL, thread_work, (void*) t);
+        if (rc) {
+            printf("ERROR; return code from pthread_create() is %d\n", rc);
+            return -1;
+        }
+    }
+
+    if (timeout > 0)
+    {
+        sleep(timeout);
+    }
+
+    to_continue = 0;
+
+    for (t = 0 ; t < MAX_THREAD ; t++)
+    {
+        rc = pthread_join(threads[t], &status);
+        if (rc)
+        {
+            printf("ERROR; return code from pthread_join() is %d\n", rc);
+            return -1;
+        }
+        printf("Main: completed join with thread %ld having a status of %ld\n",
+                (long)t, (long)status);
+    }
+
+    return 0;
+}
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.