MCS locks are smaller and don't rely on vcore_id()
[akaros.git] / user / pthread / pthread.c
1 #include <ros/arch/trapframe.h>
2 #include <pthread.h>
3 #include <vcore.h>
4 #include <mcs.h>
5 #include <stdlib.h>
6 #include <string.h>
7 #include <assert.h>
8 #include <rstdio.h>
9 #include <errno.h>
10 #include <parlib.h>
11 #include <ros/event.h>
12 #include <arch/atomic.h>
13 #include <arch/arch.h>
14 #include <sys/queue.h>
15 #include <sys/mman.h>
16 #include <assert.h>
17 #include <event.h>
18
19 struct pthread_queue ready_queue = TAILQ_HEAD_INITIALIZER(ready_queue);
20 struct pthread_queue active_queue = TAILQ_HEAD_INITIALIZER(active_queue);
21 mcs_lock_t queue_lock = MCS_LOCK_INIT;
22 pthread_once_t init_once = PTHREAD_ONCE_INIT;
23 int threads_ready = 0;
24 int threads_active = 0;
25
26 /* Helper / local functions */
27 static int get_next_pid(void);
28 static inline void spin_to_sleep(unsigned int spins, unsigned int *spun);
29
30 /* Pthread 2LS operations */
31 struct uthread *pth_init(void);
32 void pth_sched_entry(void);
33 struct uthread *pth_thread_create(void (*func)(void), void *udata);
34 void pth_thread_runnable(struct uthread *uthread);
35 void pth_thread_yield(struct uthread *uthread);
36 void pth_thread_exit(struct uthread *uthread);
37 void pth_preempt_pending(void);
38 void pth_spawn_thread(uintptr_t pc_start, void *data);
39
40 struct schedule_ops pthread_sched_ops = {
41         pth_init,
42         pth_sched_entry,
43         pth_thread_create,
44         pth_thread_runnable,
45         pth_thread_yield,
46         pth_thread_exit,
47         0, /* pth_preempt_pending, */
48         0, /* pth_spawn_thread, */
49 };
50
51 /* Publish our sched_ops, overriding the weak defaults */
52 struct schedule_ops *sched_ops = &pthread_sched_ops;
53
54 /* Static helpers */
55 static void __pthread_free_stack(struct pthread_tcb *pt);
56 static int __pthread_allocate_stack(struct pthread_tcb *pt);
57
58 /* Do whatever init you want.  Return a uthread representing thread0 (int
59  * main()) */
60 struct uthread *pth_init(void)
61 {
62         struct mcs_lock_qnode local_qn = {0};
63         /* Tell the kernel where and how we want to receive events.  This is just an
64          * example of what to do to have a notification turned on.  We're turning on
65          * USER_IPIs, posting events to vcore 0's vcpd, and telling the kernel to
66          * send to vcore 0.  Note sys_self_notify will ignore the vcoreid pref.
67          * Also note that enable_kevent() is just an example, and you probably want
68          * to use parts of event.c to do what you want. */
69         enable_kevent(EV_USER_IPI, 0, EVENT_IPI);
70
71         /* Create a pthread_tcb for the main thread */
72         pthread_t t = (pthread_t)calloc(1, sizeof(struct pthread_tcb));
73         t->id = get_next_pid();
74         assert(t->id == 0);
75
76         /* Put the new pthread on the active queue */
77         mcs_lock_lock(&queue_lock, &local_qn);
78         threads_active++;
79         TAILQ_INSERT_TAIL(&active_queue, t, next);
80         mcs_lock_unlock(&queue_lock, &local_qn);
81         return (struct uthread*)t;
82 }
83
84 /* Called from vcore entry.  Options usually include restarting whoever was
85  * running there before or running a new thread.  Events are handled out of
86  * event.c (table of function pointers, stuff like that). */
87 void pth_sched_entry(void)
88 {
89         if (current_uthread) {
90                 run_current_uthread();
91                 assert(0);
92         }
93         /* no one currently running, so lets get someone from the ready queue */
94         struct pthread_tcb *new_thread = NULL;
95         struct mcs_lock_qnode local_qn = {0};
96         mcs_lock_lock(&queue_lock, &local_qn);
97         new_thread = TAILQ_FIRST(&ready_queue);
98         if (new_thread) {
99                 TAILQ_REMOVE(&ready_queue, new_thread, next);
100                 TAILQ_INSERT_TAIL(&active_queue, new_thread, next);
101                 threads_active++;
102                 threads_ready--;
103         }
104         mcs_lock_unlock(&queue_lock, &local_qn);
105         /* For now, this dumb logic is done here */
106         if (!new_thread) {
107                 /* TODO: consider doing something more intelligent here */
108                 printd("[P] No threads, vcore %d is yielding\n", vcore_id());
109                 sys_yield(0);
110                 assert(0);
111         }
112         run_uthread((struct uthread*)new_thread);
113         assert(0);
114 }
115
116 /* Could move this, along with start_routine and arg, into the 2LSs */
117 static void __pthread_run(void)
118 {
119         struct pthread_tcb *me = pthread_self();
120         pthread_exit(me->start_routine(me->arg));
121 }
122
123 /* Responible for creating the uthread and initializing its user trap frame */
124 struct uthread *pth_thread_create(void (*func)(void), void *udata)
125 {
126         struct pthread_tcb *pthread;
127         pthread_attr_t *attr = (pthread_attr_t*)udata;
128         pthread = (pthread_t)calloc(1, sizeof(struct pthread_tcb));
129         pthread->stacksize = PTHREAD_STACK_SIZE;        /* default */
130         pthread->id = get_next_pid();
131         pthread->detached = FALSE;                              /* default */
132         /* Respect the attributes */
133         if (attr) {
134                 if (attr->stacksize)                                    /* don't set a 0 stacksize */
135                         pthread->stacksize = attr->stacksize;
136                 if (attr->detachstate == PTHREAD_CREATE_DETACHED)
137                         pthread->detached = TRUE;
138         }
139         /* allocate a stack */
140         if (__pthread_allocate_stack(pthread))
141                 printf("We're fucked\n");
142         /* Set the u_tf to start up in __pthread_run, which will call the real
143          * start_routine and pass it the arg.  Note those aren't set until later in
144          * pthread_create(). */
145         init_user_tf(&pthread->uthread.utf, (uint32_t)__pthread_run, 
146                  (uint32_t)(pthread->stacktop));
147         return (struct uthread*)pthread;
148 }
149
150 void pth_thread_runnable(struct uthread *uthread)
151 {
152         struct pthread_tcb *pthread = (struct pthread_tcb*)uthread;
153         struct mcs_lock_qnode local_qn = {0};
154         /* Insert the newly created thread into the ready queue of threads.
155          * It will be removed from this queue later when vcore_entry() comes up */
156         mcs_lock_lock(&queue_lock, &local_qn);
157         TAILQ_INSERT_TAIL(&ready_queue, pthread, next);
158         threads_ready++;
159         mcs_lock_unlock(&queue_lock, &local_qn);
160 }
161
162 /* The calling thread is yielding.  Do what you need to do to restart (like put
163  * yourself on a runqueue), or do some accounting.  Eventually, this might be a
164  * little more generic than just yield. */
165 void pth_thread_yield(struct uthread *uthread)
166 {
167         struct pthread_tcb *pthread = (struct pthread_tcb*)uthread;
168         struct mcs_lock_qnode local_qn = {0};
169         /* Take from the active list, and put on the ready list (tail).  Don't do
170          * this until we are done completely with the thread, since it can be
171          * restarted somewhere else. */
172         mcs_lock_lock(&queue_lock, &local_qn);
173         threads_active--;
174         TAILQ_REMOVE(&active_queue, pthread, next);
175         threads_ready++;
176         TAILQ_INSERT_TAIL(&ready_queue, pthread, next);
177         mcs_lock_unlock(&queue_lock, &local_qn);
178 }
179
180 /* Thread is exiting, do your 2LS specific stuff.  You're in vcore context.
181  * Don't use the thread's TLS or stack or anything. */
182 void pth_thread_exit(struct uthread *uthread)
183 {
184         struct pthread_tcb *pthread = (struct pthread_tcb*)uthread;
185         struct mcs_lock_qnode local_qn = {0};
186         /* Remove from the active runqueue */
187         mcs_lock_lock(&queue_lock, &local_qn);
188         threads_active--;
189         TAILQ_REMOVE(&active_queue, pthread, next);
190         mcs_lock_unlock(&queue_lock, &local_qn);
191         /* Cleanup, mirroring pth_thread_create() */
192         __pthread_free_stack(pthread);
193         /* TODO: race on detach state */
194         if (pthread->detached)
195                 free(pthread);
196         /* Once we do this, our joiner can free us.  He won't free us if we're
197          * detached, but there is still a potential race there (since he's accessing
198          * someone who is freed. */
199         pthread->finished = 1;
200 }
201
202 void pth_preempt_pending(void)
203 {
204 }
205
206 void pth_spawn_thread(uintptr_t pc_start, void *data)
207 {
208 }
209
210 /* Pthread interface stuff and helpers */
211
212 int pthread_attr_init(pthread_attr_t *a)
213 {
214         a->stacksize = PTHREAD_STACK_SIZE;
215         a->detachstate = PTHREAD_CREATE_JOINABLE;
216         return 0;
217 }
218
219 int pthread_attr_destroy(pthread_attr_t *a)
220 {
221         return 0;
222 }
223
224 static void __pthread_free_stack(struct pthread_tcb *pt)
225 {
226         assert(!munmap(pt->stacktop - PTHREAD_STACK_SIZE, PTHREAD_STACK_SIZE));
227 }
228
229 static int __pthread_allocate_stack(struct pthread_tcb *pt)
230 {
231         assert(pt->stacksize);
232         void* stackbot = mmap(0, pt->stacksize,
233                               PROT_READ|PROT_WRITE|PROT_EXEC,
234                               MAP_POPULATE|MAP_ANONYMOUS, -1, 0);
235         if (stackbot == MAP_FAILED)
236                 return -1; // errno set by mmap
237         pt->stacktop = stackbot + pt->stacksize;
238         return 0;
239 }
240
241 // Warning, this will reuse numbers eventually
242 static int get_next_pid(void)
243 {
244         static uint32_t next_pid = 0;
245         return next_pid++;
246 }
247
248 int pthread_attr_setstacksize(pthread_attr_t *attr, size_t stacksize)
249 {
250         attr->stacksize = stacksize;
251         return 0;
252 }
253 int pthread_attr_getstacksize(const pthread_attr_t *attr, size_t *stacksize)
254 {
255         *stacksize = attr->stacksize;
256         return 0;
257 }
258
259 int pthread_create(pthread_t* thread, const pthread_attr_t* attr,
260                    void *(*start_routine)(void *), void* arg)
261 {
262         struct pthread_tcb *pthread =
263                (struct pthread_tcb*)uthread_create(__pthread_run, (void*)attr);
264         if (!pthread)
265                 return -1;
266         pthread->start_routine = start_routine;
267         pthread->arg = arg;
268         uthread_runnable((struct uthread*)pthread);
269         *thread = pthread;
270         return 0;
271 }
272
273 int pthread_join(pthread_t thread, void** retval)
274 {
275         /* Not sure if this is the right semantics.  There is a race if we deref
276          * thread and he is already freed (which would have happened if he was
277          * detached. */
278         if (thread->detached) {
279                 printf("[pthread] trying to join on a detached pthread");
280                 return -1;
281         }
282         while (!thread->finished)
283                 pthread_yield();
284         if (retval)
285                 *retval = thread->retval;
286         free(thread);
287         return 0;
288 }
289
290 int pthread_yield(void)
291 {
292         uthread_yield();
293         return 0;
294 }
295
296 int pthread_mutexattr_init(pthread_mutexattr_t* attr)
297 {
298   attr->type = PTHREAD_MUTEX_DEFAULT;
299   return 0;
300 }
301
302 int pthread_mutexattr_destroy(pthread_mutexattr_t* attr)
303 {
304   return 0;
305 }
306
307 int pthread_attr_setdetachstate(pthread_attr_t *__attr, int __detachstate)
308 {
309         __attr->detachstate = __detachstate;
310         return 0;
311 }
312
313 int pthread_mutexattr_gettype(const pthread_mutexattr_t* attr, int* type)
314 {
315   *type = attr ? attr->type : PTHREAD_MUTEX_DEFAULT;
316   return 0;
317 }
318
319 int pthread_mutexattr_settype(pthread_mutexattr_t* attr, int type)
320 {
321   if(type != PTHREAD_MUTEX_NORMAL)
322     return EINVAL;
323   attr->type = type;
324   return 0;
325 }
326
327 int pthread_mutex_init(pthread_mutex_t* m, const pthread_mutexattr_t* attr)
328 {
329   m->attr = attr;
330   m->lock = 0;
331   return 0;
332 }
333
334 /* Set *spun to 0 when calling this the first time.  It will yield after 'spins'
335  * calls.  Use this for adaptive mutexes and such. */
336 static inline void spin_to_sleep(unsigned int spins, unsigned int *spun)
337 {
338         if ((*spun)++ == spins) {
339                 pthread_yield();
340                 *spun = 0;
341         }
342 }
343
344 int pthread_mutex_lock(pthread_mutex_t* m)
345 {
346         unsigned int spinner = 0;
347         while(pthread_mutex_trylock(m))
348                 while(*(volatile size_t*)&m->lock) {
349                         cpu_relax();
350                         spin_to_sleep(PTHREAD_MUTEX_SPINS, &spinner);
351                 }
352         return 0;
353 }
354
355 int pthread_mutex_trylock(pthread_mutex_t* m)
356 {
357   return atomic_swap(&m->lock,1) == 0 ? 0 : EBUSY;
358 }
359
360 int pthread_mutex_unlock(pthread_mutex_t* m)
361 {
362   /* Need to prevent the compiler (and some arches) from reordering older
363    * stores */
364   wmb();
365   m->lock = 0;
366   return 0;
367 }
368
369 int pthread_mutex_destroy(pthread_mutex_t* m)
370 {
371   return 0;
372 }
373
374 int pthread_cond_init(pthread_cond_t *c, const pthread_condattr_t *a)
375 {
376   c->attr = a;
377   memset(c->waiters,0,sizeof(c->waiters));
378   memset(c->in_use,0,sizeof(c->in_use));
379   c->next_waiter = 0;
380   return 0;
381 }
382
383 int pthread_cond_destroy(pthread_cond_t *c)
384 {
385   return 0;
386 }
387
388 int pthread_cond_broadcast(pthread_cond_t *c)
389 {
390   memset(c->waiters,0,sizeof(c->waiters));
391   return 0;
392 }
393
394 int pthread_cond_signal(pthread_cond_t *c)
395 {
396   int i;
397   for(i = 0; i < MAX_PTHREADS; i++)
398   {
399     if(c->waiters[i])
400     {
401       c->waiters[i] = 0;
402       break;
403     }
404   }
405   return 0;
406 }
407
408 int pthread_cond_wait(pthread_cond_t *c, pthread_mutex_t *m)
409 {
410   int old_waiter = c->next_waiter;
411   int my_waiter = c->next_waiter;
412   
413   //allocate a slot
414   while (atomic_swap (& (c->in_use[my_waiter]), SLOT_IN_USE) == SLOT_IN_USE)
415   {
416     my_waiter = (my_waiter + 1) % MAX_PTHREADS;
417     assert (old_waiter != my_waiter);  // do not want to wrap around
418   }
419   c->waiters[my_waiter] = WAITER_WAITING;
420   c->next_waiter = (my_waiter+1) % MAX_PTHREADS;  // race on next_waiter but ok, because it is advisary
421
422   pthread_mutex_unlock(m);
423
424   volatile int* poll = &c->waiters[my_waiter];
425   while(*poll);
426   c->in_use[my_waiter] = SLOT_FREE;
427   pthread_mutex_lock(m);
428
429   return 0;
430 }
431
432 int pthread_condattr_init(pthread_condattr_t *a)
433 {
434   a = PTHREAD_PROCESS_PRIVATE;
435   return 0;
436 }
437
438 int pthread_condattr_destroy(pthread_condattr_t *a)
439 {
440   return 0;
441 }
442
443 int pthread_condattr_setpshared(pthread_condattr_t *a, int s)
444 {
445   a->pshared = s;
446   return 0;
447 }
448
449 int pthread_condattr_getpshared(pthread_condattr_t *a, int *s)
450 {
451   *s = a->pshared;
452   return 0;
453 }
454
455 pthread_t pthread_self()
456 {
457   return (struct pthread_tcb*)current_uthread;
458 }
459
460 int pthread_equal(pthread_t t1, pthread_t t2)
461 {
462   return t1 == t2;
463 }
464
465 /* This function cannot be migrated to a different vcore by the userspace
466  * scheduler.  Will need to sort that shit out. */
467 void pthread_exit(void *ret)
468 {
469         struct pthread_tcb *pthread = pthread_self();
470         pthread->retval = ret;
471         uthread_exit();
472 }
473
474 int pthread_once(pthread_once_t* once_control, void (*init_routine)(void))
475 {
476   if(atomic_swap(once_control,1) == 0)
477     init_routine();
478   return 0;
479 }
480
481 int pthread_barrier_init(pthread_barrier_t* b, const pthread_barrierattr_t* a, int count)
482 {
483   b->nprocs = b->count = count;
484   b->sense = 0;
485   pthread_mutex_init(&b->pmutex, 0);
486   return 0;
487 }
488
489 int pthread_barrier_wait(pthread_barrier_t* b)
490 {
491   unsigned int spinner = 0;
492   int ls = !b->sense;
493
494   pthread_mutex_lock(&b->pmutex);
495   int count = --b->count;
496   pthread_mutex_unlock(&b->pmutex);
497
498   if(count == 0)
499   {
500     printd("Thread %d is last to hit the barrier, resetting...\n", pthread_self()->id);
501     b->count = b->nprocs;
502         wmb();
503     b->sense = ls;
504     return PTHREAD_BARRIER_SERIAL_THREAD;
505   }
506   else
507   {
508     while(b->sense != ls) {
509       cpu_relax();
510       spin_to_sleep(PTHREAD_BARRIER_SPINS, &spinner);
511     }
512     return 0;
513   }
514 }
515
516 int pthread_barrier_destroy(pthread_barrier_t* b)
517 {
518   pthread_mutex_destroy(&b->pmutex);
519   return 0;
520 }
521
522 int pthread_detach(pthread_t thread)
523 {
524         thread->detached = TRUE;
525         return 0;
526 }