futex: Call unset_alarm() before freeing the awaiter
[akaros.git] / user / pthread / futex.c
1 #include <parlib/common.h>
2 #include <futex.h>
3 #include <sys/queue.h>
4 #include <parlib/uthread.h>
5 #include <parlib/parlib.h>
6 #include <parlib/assert.h>
7 #include <stdio.h>
8 #include <errno.h>
9 #include <parlib/slab.h>
10 #include <parlib/mcs.h>
11 #include <parlib/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   struct uthread *uthread;
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(void *arg)
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   //printf("timeout fired: %p\n", e->uaddr);
43
44   // Atomically remove the timed-out element from the futex queue if we won the
45   // race against actually completing.
46   mcs_pdr_lock(&__futex.lock);
47   TAILQ_FOREACH(__e, &__futex.queue, link)
48     if (__e == e) break;
49   if (__e != NULL)
50     TAILQ_REMOVE(&__futex.queue, e, link);
51   mcs_pdr_unlock(&__futex.lock);
52
53   // If we removed it, restart it outside the lock
54   if (__e != NULL) {
55     e->timedout = true;
56     //printf("timeout: %p\n", e->uaddr);
57     uthread_runnable(e->uthread);
58   }
59 }
60
61 static void __futex_block(struct uthread *uthread, void *arg) {
62   struct futex_element *e = (struct futex_element*)arg;
63
64   // Set the remaining properties of the futex element
65   e->uthread = uthread;
66   e->timedout = false;
67
68   // Insert the futex element into the queue
69   TAILQ_INSERT_TAIL(&__futex.queue, e, link);
70
71   // Set an alarm for the futex timeout if applicable
72   if(e->us_timeout != (uint64_t)-1) {
73     e->awaiter.data = e;
74     init_awaiter(&e->awaiter, __futex_timeout);
75     set_awaiter_rel(&e->awaiter, e->us_timeout);
76     //printf("timeout set: %p\n", e->uaddr);
77     set_alarm(&e->awaiter);
78   }
79
80   // Notify the scheduler of the type of yield we did
81   uthread_has_blocked(uthread, UTH_EXT_BLK_MUTEX);
82
83   // Unlock the pdr_lock 
84   mcs_pdr_unlock(&__futex.lock);
85 }
86
87 static inline int futex_wait(int *uaddr, int val, uint64_t us_timeout)
88 {
89   // Atomically do the following...
90   mcs_pdr_lock(&__futex.lock);
91   // If the value of *uaddr matches val
92   if(*uaddr == val) {
93     //printf("wait: %p, %d\n", uaddr, us_timeout);
94     // Create a new futex element and initialize it.
95     struct futex_element e;
96     e.uaddr = uaddr;
97     e.us_timeout = us_timeout;
98     // Yield the uthread...
99     // We set the remaining properties of the futex element, set the timeout
100     // timer, and unlock the pdr lock on the other side.  It is important that
101     // we do the unlock on the other side, because (unlike linux, etc.) its
102     // possible to get interrupted and drop into vcore context right after
103     // releasing the lock.  If that vcore code then calls futex_wake(), we
104     // would be screwed.  Doing things this way means we have to hold the lock
105     // longer, but its necessary for correctness.
106     uthread_yield(TRUE, __futex_block, &e);
107     // We are unlocked here!
108
109         // Unset ensures the timeout won't happen, and if it did, that the alarm
110         // service is done with the awaiter
111     if(e.us_timeout != (uint64_t)-1)
112           unset_alarm(&e.awaiter);
113
114     // After waking, if we timed out, set the error
115     // code appropriately and return
116     if(e.timedout) {
117       errno = ETIMEDOUT;
118       return -1;
119     }
120   } else {
121       mcs_pdr_unlock(&__futex.lock);
122   }
123   return 0;
124 }
125
126 static inline int futex_wake(int *uaddr, int count)
127 {
128   int max = count;
129   struct futex_element *e,*n = NULL;
130   struct futex_queue q = TAILQ_HEAD_INITIALIZER(q);
131
132   // Atomically grab all relevant futex blockers
133   // from the global futex queue
134   mcs_pdr_lock(&__futex.lock);
135   e = TAILQ_FIRST(&__futex.queue);
136   while(e != NULL) {
137     if(count > 0) {
138       n = TAILQ_NEXT(e, link);
139       if(e->uaddr == uaddr) {
140         TAILQ_REMOVE(&__futex.queue, e, link);
141         TAILQ_INSERT_TAIL(&q, e, link);
142         count--;
143       }
144       e = n;
145     }
146     else break;
147   }
148   mcs_pdr_unlock(&__futex.lock);
149
150   // Unblock them outside the lock
151   e = TAILQ_FIRST(&q);
152   while(e != NULL) {
153     n = TAILQ_NEXT(e, link);
154     TAILQ_REMOVE(&q, e, link);
155     uthread_runnable(e->uthread);
156     e = n;
157   }
158   return max-count;
159 }
160
161 int futex(int *uaddr, int op, int val,
162           const struct timespec *timeout,
163           int *uaddr2, int val3)
164 {
165   static parlib_once_t once = PARLIB_ONCE_INIT;
166
167   parlib_run_once(&once, futex_init, NULL);
168   // Round to the nearest micro-second
169   uint64_t us_timeout = (uint64_t)-1;
170   assert(uaddr2 == NULL);
171   assert(val3 == 0);
172   if(timeout != NULL) {
173     us_timeout = timeout->tv_sec*1000000L + timeout->tv_nsec/1000L;
174     assert(us_timeout > 0);
175   }
176   switch(op) {
177     case FUTEX_WAIT:
178       return futex_wait(uaddr, val, us_timeout);
179     case FUTEX_WAKE:
180       return futex_wake(uaddr, val);
181     default:
182       errno = ENOSYS;
183       return -1;
184   }
185   return -1;
186 }
187