Rearrange the timeout logic to be a little more efficient
[akaros.git] / user / pthread / futex.c
1 #include <ros/common.h>
2 #include <futex.h>
3 #include <sys/queue.h>
4 #include <pthread.h>
5 #include <parlib.h>
6 #include <assert.h>
7 #include <stdio.h>
8 #include <errno.h>
9 #include <slab.h>
10 #include <mcs.h>
11 #include <alarm.h>
12
13 static inline int futex_wake(int *uaddr, int count);
14 static inline int futex_wait(int *uaddr, int val, uint64_t ms_timeout);
15 static void *timer_thread(void *arg);
16
17 struct futex_element {
18   TAILQ_ENTRY(futex_element) link;
19   pthread_t pthread;
20   int *uaddr;
21   uint64_t us_timeout;
22   struct alarm_waiter awaiter;
23   bool timedout;
24 };
25 TAILQ_HEAD(futex_queue, futex_element);
26
27 struct futex_data {
28   struct mcs_pdr_lock lock;
29   struct futex_queue queue;
30 };
31 static struct futex_data __futex;
32
33 static inline void futex_init()
34 {
35   mcs_pdr_init(&__futex.lock);
36   TAILQ_INIT(&__futex.queue);
37 }
38
39 static void __futex_timeout(struct alarm_waiter *awaiter) {
40   struct futex_element *__e = NULL;
41   struct futex_element *e = (struct futex_element*)awaiter->data;
42
43   // Atomically remove the timed-out element from the futex queue if we won the
44   // race against actually completing.
45   mcs_pdr_lock(&__futex.lock);
46   TAILQ_FOREACH(__e, &__futex.queue, link)
47     if (__e == e) break;
48   if (__e != NULL)
49     TAILQ_REMOVE(&__futex.queue, e, link);
50   mcs_pdr_unlock(&__futex.lock);
51
52   // If we removed it, restart it outside the lock
53   if (__e != NULL) {
54     e->timedout = true;
55     uthread_runnable((struct uthread*)e->pthread);
56   }
57   // Set this as the very last thing we do whether we successfully woke the
58   // thread blocked on the futex or not.  Either we set this or wake() sets
59   // this, not both.  Spin on this in the bottom-half of the wait() code to
60   // ensure there are no more references to awaiter before freeing the memory
61   // for it.
62   e->awaiter.data = NULL;
63 }
64
65 static void __futex_block(struct uthread *uthread, void *arg) {
66   pthread_t pthread = (pthread_t)uthread;
67   struct futex_element *e = (struct futex_element*)arg;
68
69   // Set the remaining properties of the futex element
70   e->pthread = pthread;
71
72   // Insert the futex element into the queue
73   TAILQ_INSERT_TAIL(&__futex.queue, e, link);
74
75   // Notify the scheduler of the type of yield we did
76   __pthread_generic_yield(pthread);
77   pthread->state = PTH_BLK_MUTEX;
78
79   // Unlock the pdr_lock 
80   mcs_pdr_unlock(&__futex.lock);
81 }
82
83 static inline int futex_wait(int *uaddr, int val, uint64_t us_timeout)
84 {
85   // Atomically do the following...
86   mcs_pdr_lock(&__futex.lock);
87   // If the value of *uaddr matches val
88   if(*uaddr == val) {
89     // Create a new futex element and initialize it.
90     struct futex_element e;
91     e.uaddr = uaddr;
92     e.us_timeout = us_timeout;
93     // Set an alarm for the futex timeout if applicable
94     e.timedout = false;
95     if(e.us_timeout != (uint64_t)-1) {
96       e.awaiter.data = &e;
97       init_awaiter(&e.awaiter, __futex_timeout);
98       set_awaiter_rel(&e.awaiter, e.us_timeout);
99       set_alarm(&e.awaiter);
100     }
101     // Yield the uthread...
102     // We set the remaining properties of the futex element, and unlock the pdr
103     // lock on the other side.  It is important that we do the unlock on the
104     // other side, because (unlike linux, etc.) its possible to get interrupted
105     // and drop into vcore context right after releasing the lock.  If that
106     // vcore code then calls futex_wake(), we would be screwed.  Doing things
107     // this way means we have to hold the lock longer, but its necessary for
108     // correctness.
109     uthread_yield(TRUE, __futex_block, &e);
110     // We are unlocked here!
111
112     // Spin briefly to make sure that all references to e are gone between the
113     // wake() and the timeout() code. We use e.awaiter.data to do this.
114     while (e.awaiter.data != NULL)
115       cpu_relax();
116
117     // After waking, if we timed out, set the error
118     // code appropriately and return
119     if(e.timedout) {
120       errno = ETIMEDOUT;
121       return -1;
122     }
123   } else {
124       mcs_pdr_unlock(&__futex.lock);
125   }
126   return 0;
127 }
128
129 static inline int futex_wake(int *uaddr, int count)
130 {
131   struct futex_element *e,*n = NULL;
132   struct futex_queue q = TAILQ_HEAD_INITIALIZER(q);
133
134   // Atomically grab all relevant futex blockers
135   // from the global futex queue
136   mcs_pdr_lock(&__futex.lock);
137   e = TAILQ_FIRST(&__futex.queue);
138   while(e != NULL) {
139     if(count > 0) {
140       n = TAILQ_NEXT(e, link);
141       if(e->uaddr == uaddr) {
142         TAILQ_REMOVE(&__futex.queue, e, link);
143         TAILQ_INSERT_TAIL(&q, e, link);
144         count--;
145       }
146       e = n;
147     }
148     else break;
149   }
150   mcs_pdr_unlock(&__futex.lock);
151
152   // Unblock them outside the lock
153   e = TAILQ_FIRST(&q);
154   while(e != NULL) {
155     n = TAILQ_NEXT(e, link);
156     TAILQ_REMOVE(&q, e, link);
157     // Cancel the timeout if one was set
158     if(e->us_timeout != (uint64_t)-1) {
159       // Try and unset the alarm.  If this fails, then we have already
160       // started running the alarm callback.  If it succeeds, then we can
161       // set awaiter->data to NULL so that the bottom half of wake can
162       // proceed. Either we set awaiter->data to NULL or __futex_timeout
163       // does. The fact that we made it here though, means that WE are the
164       // one who removed e from the queue, so we are basically just
165       // deciding who should set awaiter->data to NULL to indicate that
166       // there are no more references to it.
167       if(unset_alarm(&e->awaiter))
168         e->awaiter.data = NULL;
169     }
170     uthread_runnable((struct uthread*)e->pthread);
171     e = n;
172   }
173   return 0;
174 }
175
176 int futex(int *uaddr, int op, int val,
177           const struct timespec *timeout,
178           int *uaddr2, int val3)
179 {
180   // Round to the nearest micro-second
181   uint64_t us_timeout = (uint64_t)-1;
182   assert(uaddr2 == NULL);
183   assert(val3 == 0);
184   if(timeout != NULL) {
185     us_timeout = timeout->tv_sec*1000000L + timeout->tv_nsec/1000L;
186     assert(us_timeout > 0);
187   }
188
189   run_once(futex_init());
190   switch(op) {
191     case FUTEX_WAIT:
192       return futex_wait(uaddr, val, us_timeout);
193     case FUTEX_WAKE:
194       return futex_wake(uaddr, val);
195     default:
196       errno = ENOSYS;
197       return -1;
198   }
199   return -1;
200 }
201