Update pthread futex_waiti() to unlock after yield
authorKevin Klues <klueska@cs.berkeley.edu>
Fri, 31 Jan 2014 22:00:35 +0000 (14:00 -0800)
committerKevin Klues <klueska@cs.berkeley.edu>
Fri, 31 Jan 2014 22:14:37 +0000 (14:14 -0800)
The previous version of the futex code was adopted from the linux parlib
code, which doesn't have to worry about uthreads spuriously dropping
into vcore context while not holding a pdr lock.  Without this change,
it was possible for a vcore to spin indefinitely on a futex_wait() while
the uthread it was trying to wake had not actually yielded yet (and
couldn't because it was trying to yield on the very same vcore that was
spinning trying to wake it).

With this change we now have to hold the futex lock a little longer, but
it is necessary for correctness.  In the future, we will probably want
to use some sort of hashtable to maintain one lock per futex, rather
than a global futex lock, and this will help alleviate some of these
costs.

tests/signal_futex.c [new file with mode: 0644]
user/pthread/futex.c

diff --git a/tests/signal_futex.c b/tests/signal_futex.c
new file mode 100644 (file)
index 0000000..15070e0
--- /dev/null
@@ -0,0 +1,63 @@
+/* Copyright (c) 2014 The Regents of the University of California
+ * Kevin Klues <klueska@cs.berkeley.edu>
+ * See LICENSE for details.
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <parlib.h>
+#include <pthread.h>
+#include <futex.h>
+#include <signal.h>
+
+// Signal handler run in vcore context which redirects signals to userspace by
+// waking a thread waiting on a futex. Note, this does not guarantee that every
+// signal that comes through this handler will be noticed or processed by the
+// thread.
+int __sigpending = 0;
+void sig_handler(int signr) {
+       __sigpending = 1;
+       futex(&__sigpending, FUTEX_WAKE, INT_MAX, NULL, NULL, 0);
+}
+
+// User level thread waiting on a futex to count signals
+int count = 0;
+void *count_signals(void *arg) {
+       while(1) {
+               futex(&__sigpending, FUTEX_WAIT, 0, NULL, NULL, 0);
+               __sync_fetch_and_add(&count, 1);
+               __sigpending = 0;
+       }
+}
+
+// Thread spamming us with signals
+void *sig_thread(void *arg) {
+       int *done = (int*)arg;
+       struct sigaction sigact = {.sa_handler = sig_handler, 0};
+       sigaction(SIGUSR1, &sigact, 0);
+       while(1) {
+               kill(getpid(), SIGUSR1);
+               cmb();
+               if (*done) return NULL;
+       }
+}
+
+int main(int argc, char **argv)
+{
+       int done = false;
+       pthread_t pth_handle, pth_handle2;
+       // Spawn off a thread to spam us with signals
+       pthread_create(&pth_handle, NULL, &sig_thread, &done);
+       // Spawn off a thread to process those signals
+       pthread_create(&pth_handle2, NULL, &count_signals, NULL);
+       // Sleep for 3 seconds by timing out on a futex
+       int dummy = 0;
+       struct timespec timeout = {.tv_sec = 3, 0};
+       futex(&dummy, FUTEX_WAIT, 0, &timeout, NULL, 0);
+       // Force the signal tread to exit
+       cmb();
+       done = true;
+       pthread_join(pth_handle, NULL);
+       printf("count: %d\n", count);
+       return 0;
+}
index 1cf3bb1..936ce9f 100644 (file)
@@ -43,9 +43,31 @@ static inline void futex_init()
 static void __futex_block(struct uthread *uthread, void *arg) {
   pthread_t pthread = (pthread_t)uthread;
   struct futex_element *e = (struct futex_element*)arg;
+
+  // Set the remaining properties of the futex element
+  e->pthread = pthread;
+  e->timedout = false;
+  // Adjust the timeout properties on the futex element
+  bool enable_timer = false;
+  if(e->ms_timeout != (uint64_t)-1) {
+    e->ms_timeout += __futex.time;
+       // If we are setting the timeout, get ready to
+       // enable the timer if it is currently disabled.
+    if(__futex.timer_enabled == false) {
+      __futex.timer_enabled = true;
+      enable_timer = true;
+    }
+  }
+  // Notify the scheduler of the type of yield we did
   __pthread_generic_yield(pthread);
   pthread->state = PTH_BLK_MUTEX;
-  e->pthread = pthread;
+  // Insert the futex element into the queue
+  TAILQ_INSERT_TAIL(&__futex.queue, e, link);
+  // Unlock the pdr_lock 
+  mcs_pdr_unlock(&__futex.lock);
+  // Enable the timer if we need to outside the lock
+  if(enable_timer)
+    futex_wake(&__futex.timer_enabled, 1);
 }
 
 static inline int futex_wait(int *uaddr, int val, uint64_t ms_timeout)
@@ -56,40 +78,27 @@ static inline int futex_wait(int *uaddr, int val, uint64_t ms_timeout)
   if(*uaddr == val) {
     // Create a new futex element and initialize it.
     struct futex_element e;
-    bool enable_timer = false;
     e.uaddr = uaddr;
-    e.pthread = NULL;
     e.ms_timeout = ms_timeout;
-    e.timedout = false;
-    if(e.ms_timeout != (uint64_t)-1) {
-      e.ms_timeout += __futex.time;
-         // If we are setting the timeout, get ready to
-         // enable the timer if it is currently disabled.
-      if(__futex.timer_enabled == false) {
-        __futex.timer_enabled = true;
-        enable_timer = true;
-      }
-    }
-    // Insert the futex element into the queue
-    TAILQ_INSERT_TAIL(&__futex.queue, &e, link);
-    mcs_pdr_unlock(&__futex.lock);
-
-    // Enable the timer if we need to outside the lock
-    if(enable_timer)
-      futex_wake(&__futex.timer_enabled, 1);
-
-    // Yield the current uthread
+    // Yield the uthread...
+    // We set the remaining properties of the futex element, adjust the
+    // timeout, set the timer, and unlock the pdr lock on the other side.
+    // It is important that we do the unlock on the other side, because (unlike
+    // linux, etc.) its possible to get interrupted and drop into vcore context
+    // right after releasing the lock.  If that vcore code then calls
+    // futex_wake(), we would be screwed.  Doing things this way means we have
+    // to hold the lock longer, but its necessary for correctness.
     uthread_yield(TRUE, __futex_block, &e);
+    // We are unlocked here!
 
-       // After waking, if we timed out, set the error
-       // code appropriately and return
+    // After waking, if we timed out, set the error
+    // code appropriately and return
     if(e.timedout) {
       errno = ETIMEDOUT;
       return -1;
     }
-  }
-  else {
-    mcs_pdr_unlock(&__futex.lock);
+  } else {
+      mcs_pdr_unlock(&__futex.lock);
   }
   return 0;
 }
@@ -122,8 +131,6 @@ static inline int futex_wake(int *uaddr, int count)
   while(e != NULL) {
     n = TAILQ_NEXT(e, link);
     TAILQ_REMOVE(&q, e, link);
-    while(e->pthread == NULL)
-      cpu_relax();
     uthread_runnable((struct uthread*)e->pthread);
     e = n;
   }
@@ -172,8 +179,6 @@ static void *timer_thread(void *arg)
     while(e != NULL) {
       n = TAILQ_NEXT(e, link);
       TAILQ_REMOVE(&q, e, link);
-      while(e->pthread == NULL)
-        cpu_relax();
       uthread_runnable((struct uthread*)e->pthread);
       e = n;
     }