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