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