Rearrange the timeout logic to be a little more efficient
authorKevin Klues <klueska@cs.berkeley.edu>
Fri, 21 Mar 2014 09:49:06 +0000 (02:49 -0700)
committerKevin Klues <klueska@cs.berkeley.edu>
Fri, 21 Mar 2014 09:49:06 +0000 (02:49 -0700)
Also beef up the comments a bit

user/pthread/futex.c

index 5dbcfad..983848e 100644 (file)
@@ -51,12 +51,15 @@ static void __futex_timeout(struct alarm_waiter *awaiter) {
 
   // If we removed it, restart it outside the lock
   if (__e != NULL) {
 
   // If we removed it, restart it outside the lock
   if (__e != NULL) {
-    uthread_runnable((struct uthread*)e->pthread);
     e->timedout = true;
     e->timedout = true;
+    uthread_runnable((struct uthread*)e->pthread);
   }
   }
-  // Set this as the very last thing we do.  Spin on this in the wake code if
-  // we are trying to wake something that has already fired this timer.
-  awaiter->data = NULL;
+  // Set this as the very last thing we do whether we successfully woke the
+  // thread blocked on the futex or not.  Either we set this or wake() sets
+  // this, not both.  Spin on this in the bottom-half of the wait() code to
+  // ensure there are no more references to awaiter before freeing the memory
+  // for it.
+  e->awaiter.data = NULL;
 }
 
 static void __futex_block(struct uthread *uthread, void *arg) {
 }
 
 static void __futex_block(struct uthread *uthread, void *arg) {
@@ -65,19 +68,10 @@ static void __futex_block(struct uthread *uthread, void *arg) {
 
   // Set the remaining properties of the futex element
   e->pthread = pthread;
 
   // Set the remaining properties of the futex element
   e->pthread = pthread;
-  e->timedout = false;
 
   // Insert the futex element into the queue
   TAILQ_INSERT_TAIL(&__futex.queue, e, link);
 
 
   // Insert the futex element into the queue
   TAILQ_INSERT_TAIL(&__futex.queue, e, link);
 
-  // Set an alarm for futex timeout if applicable
-  if(e->us_timeout != (uint64_t)-1) {
-    e->awaiter.data = e;
-    init_awaiter(&e->awaiter, __futex_timeout);
-    set_awaiter_rel(&e->awaiter, e->us_timeout);
-    set_alarm(&e->awaiter);
-  }
-
   // Notify the scheduler of the type of yield we did
   __pthread_generic_yield(pthread);
   pthread->state = PTH_BLK_MUTEX;
   // Notify the scheduler of the type of yield we did
   __pthread_generic_yield(pthread);
   pthread->state = PTH_BLK_MUTEX;
@@ -96,17 +90,30 @@ static inline int futex_wait(int *uaddr, int val, uint64_t us_timeout)
     struct futex_element e;
     e.uaddr = uaddr;
     e.us_timeout = us_timeout;
     struct futex_element e;
     e.uaddr = uaddr;
     e.us_timeout = us_timeout;
+    // Set an alarm for the futex timeout if applicable
+    e.timedout = false;
+    if(e.us_timeout != (uint64_t)-1) {
+      e.awaiter.data = &e;
+      init_awaiter(&e.awaiter, __futex_timeout);
+      set_awaiter_rel(&e.awaiter, e.us_timeout);
+      set_alarm(&e.awaiter);
+    }
     // Yield the uthread...
     // Yield the uthread...
-    // We set the remaining properties of the futex element, 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.
+    // We set the remaining properties of the futex element, 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!
 
     uthread_yield(TRUE, __futex_block, &e);
     // We are unlocked here!
 
+    // Spin briefly to make sure that all references to e are gone between the
+    // wake() and the timeout() code. We use e.awaiter.data to do this.
+    while (e.awaiter.data != NULL)
+      cpu_relax();
+
     // After waking, if we timed out, set the error
     // code appropriately and return
     if(e.timedout) {
     // After waking, if we timed out, set the error
     // code appropriately and return
     if(e.timedout) {
@@ -131,23 +138,7 @@ static inline int futex_wake(int *uaddr, int count)
   while(e != NULL) {
     if(count > 0) {
       n = TAILQ_NEXT(e, link);
   while(e != NULL) {
     if(count > 0) {
       n = TAILQ_NEXT(e, link);
-      // If this element is blocked on uaddr
       if(e->uaddr == uaddr) {
       if(e->uaddr == uaddr) {
-        // Cancel the timeout if one was set
-        if(e->us_timeout != (uint64_t)-1) {
-          // Try and unset the alarm.  If this fails, then we have already
-          // started running the alarm callback, so spin on awaiter->data being
-          // set to NULL.  The fact that we made it here though, means that WE
-          // are the one who removed e from the queue, so we are basically
-          // spinning just to make sure that no more references to awaiter
-          // exist.
-          if(!unset_alarm(&e->awaiter)) {
-            while(&e->awaiter)
-              cpu_relax();
-          } else {
-          }
-        }
-        // Remove it from the queue
         TAILQ_REMOVE(&__futex.queue, e, link);
         TAILQ_INSERT_TAIL(&q, e, link);
         count--;
         TAILQ_REMOVE(&__futex.queue, e, link);
         TAILQ_INSERT_TAIL(&q, e, link);
         count--;
@@ -163,6 +154,19 @@ static inline int futex_wake(int *uaddr, int count)
   while(e != NULL) {
     n = TAILQ_NEXT(e, link);
     TAILQ_REMOVE(&q, e, link);
   while(e != NULL) {
     n = TAILQ_NEXT(e, link);
     TAILQ_REMOVE(&q, e, link);
+    // Cancel the timeout if one was set
+    if(e->us_timeout != (uint64_t)-1) {
+      // Try and unset the alarm.  If this fails, then we have already
+      // started running the alarm callback.  If it succeeds, then we can
+      // set awaiter->data to NULL so that the bottom half of wake can
+      // proceed. Either we set awaiter->data to NULL or __futex_timeout
+      // does. The fact that we made it here though, means that WE are the
+      // one who removed e from the queue, so we are basically just
+      // deciding who should set awaiter->data to NULL to indicate that
+      // there are no more references to it.
+      if(unset_alarm(&e->awaiter))
+        e->awaiter.data = NULL;
+    }
     uthread_runnable((struct uthread*)e->pthread);
     e = n;
   }
     uthread_runnable((struct uthread*)e->pthread);
     e = n;
   }