Move timeout code to other side of uthread yield.
[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   //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((struct uthread*)e->pthread);
58   }
59   // Set this as the very last thing we do whether we successfully woke the
60   // thread blocked on the futex or not.  Either we set this or wake() sets
61   // this, not both.  Spin on this in the bottom-half of the wait() code to
62   // ensure there are no more references to awaiter before freeing the memory
63   // for it.
64   e->awaiter.data = NULL;
65 }
66
67 static void __futex_block(struct uthread *uthread, void *arg) {
68   pthread_t pthread = (pthread_t)uthread;
69   struct futex_element *e = (struct futex_element*)arg;
70
71   // Set the remaining properties of the futex element
72   e->pthread = pthread;
73   e->timedout = false;
74
75   // Insert the futex element into the queue
76   TAILQ_INSERT_TAIL(&__futex.queue, e, link);
77
78   // Set an alarm for the futex timeout if applicable
79   if(e->us_timeout != (uint64_t)-1) {
80     e->awaiter.data = e;
81     init_awaiter(&e->awaiter, __futex_timeout);
82     set_awaiter_rel(&e->awaiter, e->us_timeout);
83     //printf("timeout set: %p\n", e->uaddr);
84     set_alarm(&e->awaiter);
85   }
86
87   // Notify the scheduler of the type of yield we did
88   __pthread_generic_yield(pthread);
89   pthread->state = PTH_BLK_MUTEX;
90
91   // Unlock the pdr_lock 
92   mcs_pdr_unlock(&__futex.lock);
93 }
94
95 static inline int futex_wait(int *uaddr, int val, uint64_t us_timeout)
96 {
97   // Atomically do the following...
98   mcs_pdr_lock(&__futex.lock);
99   // If the value of *uaddr matches val
100   if(*uaddr == val) {
101     //printf("wait: %p, %d\n", uaddr, us_timeout);
102     // Create a new futex element and initialize it.
103     struct futex_element e;
104     e.uaddr = uaddr;
105     e.us_timeout = us_timeout;
106     // Yield the uthread...
107     // We set the remaining properties of the futex element, set the timeout
108     // timer, and unlock the pdr lock on the other side.  It is important that
109     // we do the unlock on the other side, because (unlike linux, etc.) its
110     // possible to get interrupted and drop into vcore context right after
111     // releasing the lock.  If that vcore code then calls futex_wake(), we
112     // would be screwed.  Doing things this way means we have to hold the lock
113     // longer, but its necessary for correctness.
114     uthread_yield(TRUE, __futex_block, &e);
115     // We are unlocked here!
116
117     // If this futex had a timeout, spin briefly to make sure that all
118     // references to e are gone between the wake() and the timeout() code. We
119     // use e.awaiter.data to do this.
120     if(e.us_timeout != (uint64_t)-1)
121       while (e.awaiter.data != NULL)
122         cpu_relax();
123
124     // After waking, if we timed out, set the error
125     // code appropriately and return
126     if(e.timedout) {
127       errno = ETIMEDOUT;
128       return -1;
129     }
130   } else {
131       mcs_pdr_unlock(&__futex.lock);
132   }
133   return 0;
134 }
135
136 static inline int futex_wake(int *uaddr, int count)
137 {
138   int max = count;
139   struct futex_element *e,*n = NULL;
140   struct futex_queue q = TAILQ_HEAD_INITIALIZER(q);
141
142   // Atomically grab all relevant futex blockers
143   // from the global futex queue
144   mcs_pdr_lock(&__futex.lock);
145   e = TAILQ_FIRST(&__futex.queue);
146   while(e != NULL) {
147     if(count > 0) {
148       n = TAILQ_NEXT(e, link);
149       if(e->uaddr == uaddr) {
150         TAILQ_REMOVE(&__futex.queue, e, link);
151         TAILQ_INSERT_TAIL(&q, e, link);
152         count--;
153       }
154       e = n;
155     }
156     else break;
157   }
158   mcs_pdr_unlock(&__futex.lock);
159
160   // Unblock them outside the lock
161   e = TAILQ_FIRST(&q);
162   while(e != NULL) {
163     n = TAILQ_NEXT(e, link);
164     TAILQ_REMOVE(&q, e, link);
165     // Cancel the timeout if one was set
166     if(e->us_timeout != (uint64_t)-1) {
167       // Try and unset the alarm.  If this fails, then we have already
168       // started running the alarm callback.  If it succeeds, then we can
169       // set awaiter->data to NULL so that the bottom half of wake can
170       // proceed. Either we set awaiter->data to NULL or __futex_timeout
171       // does. The fact that we made it here though, means that WE are the
172       // one who removed e from the queue, so we are basically just
173       // deciding who should set awaiter->data to NULL to indicate that
174       // there are no more references to it.
175       if(unset_alarm(&e->awaiter)) {
176         //printf("timeout canceled: %p\n", e->uaddr);
177         e->awaiter.data = NULL;
178       }
179     }
180     //printf("wake: %p\n", uaddr);
181     uthread_runnable((struct uthread*)e->pthread);
182     e = n;
183   }
184   return max-count;
185 }
186
187 int futex(int *uaddr, int op, int val,
188           const struct timespec *timeout,
189           int *uaddr2, int val3)
190 {
191   // Round to the nearest micro-second
192   uint64_t us_timeout = (uint64_t)-1;
193   assert(uaddr2 == NULL);
194   assert(val3 == 0);
195   if(timeout != NULL) {
196     us_timeout = timeout->tv_sec*1000000L + timeout->tv_nsec/1000L;
197     assert(us_timeout > 0);
198   }
199
200   run_once(futex_init());
201   switch(op) {
202     case FUTEX_WAIT:
203       return futex_wait(uaddr, val, us_timeout);
204     case FUTEX_WAKE:
205       return futex_wake(uaddr, val);
206     default:
207       errno = ENOSYS;
208       return -1;
209   }
210   return -1;
211 }
212