Kthreads track running kernel contexts
[akaros.git] / kern / src / kthread.c
1 /* Copyright (c) 2010-13 The Regents of the University of California
2  * Barret Rhoden <brho@cs.berkeley.edu>
3  * See LICENSE for details.
4  *
5  * Kernel threading.  These are for blocking within the kernel for whatever
6  * reason, usually during blocking IO operations. */
7
8 #include <kthread.h>
9 #include <slab.h>
10 #include <page_alloc.h>
11 #include <pmap.h>
12 #include <smp.h>
13 #include <schedule.h>
14
15 uintptr_t get_kstack(void)
16 {
17         uintptr_t stackbot;
18         if (KSTKSIZE == PGSIZE)
19                 stackbot = (uintptr_t)kpage_alloc_addr();
20         else
21                 stackbot = (uintptr_t)get_cont_pages(KSTKSHIFT >> PGSHIFT, 0);
22         assert(stackbot);
23         return stackbot + KSTKSIZE;
24 }
25
26 void put_kstack(uintptr_t stacktop)
27 {
28         uintptr_t stackbot = stacktop - KSTKSIZE;
29         if (KSTKSIZE == PGSIZE)
30                 page_decref(kva2page((void*)stackbot));
31         else
32                 free_cont_pages((void*)stackbot, KSTKSHIFT >> PGSHIFT);
33 }
34
35 uintptr_t *kstack_bottom_addr(uintptr_t stacktop)
36 {
37         /* canary at the bottom of the stack */
38         assert(!PGOFF(stacktop));
39         return (uintptr_t*)(stacktop - KSTKSIZE);
40 }
41
42 struct kmem_cache *kthread_kcache;
43
44 void kthread_init(void)
45 {
46         kthread_kcache = kmem_cache_create("kthread", sizeof(struct kthread),
47                                            __alignof__(struct kthread), 0, 0, 0);
48 }
49
50 /* Used by early init routines (smp_boot, etc) */
51 struct kthread *__kthread_zalloc(void)
52 {
53         struct kthread *kthread;
54         kthread = kmem_cache_alloc(kthread_kcache, 0);
55         assert(kthread);
56         memset(kthread, 0, sizeof(struct kthread));
57         return kthread;
58 }
59
60 /* Starts kthread on the calling core.  This does not return, and will handle
61  * the details of cleaning up whatever is currently running (freeing its stack,
62  * etc).  Pairs with sem_down(). */
63 void restart_kthread(struct kthread *kthread)
64 {
65         struct per_cpu_info *pcpui = &per_cpu_info[core_id()];
66         uintptr_t current_stacktop;
67         struct kthread *current_kthread;
68         /* Avoid messy complications.  The kthread will enable_irqsave() when it
69          * comes back up. */
70         disable_irq();
71         /* Free any spare, since we need the current to become the spare.  Without
72          * the spare, we can't free our current kthread/stack (we could free the
73          * kthread, but not the stack, since we're still on it).  And we can't free
74          * anything after popping kthread, since we never return. */
75         if (pcpui->spare) {
76                 put_kstack(pcpui->spare->stacktop);
77                 kmem_cache_free(kthread_kcache, pcpui->spare);
78         }
79         current_kthread = pcpui->cur_kthread;
80         current_stacktop = current_kthread->stacktop;
81         /* Set the spare stuff (current kthread, which includes its stacktop) */
82         pcpui->spare = current_kthread;
83         /* When a kthread runs, its stack is the default kernel stack */
84         set_stack_top(kthread->stacktop);
85         pcpui->cur_kthread = kthread;
86 #ifdef CONFIG_KTHREAD_POISON
87         /* Assert and switch to cur stack not in use, kthr stack in use */
88         uintptr_t *cur_stack_poison, *kth_stack_poison;
89         cur_stack_poison = kstack_bottom_addr(current_stacktop);
90         assert(*cur_stack_poison == 0xdeadbeef);
91         *cur_stack_poison = 0;
92         kth_stack_poison = kstack_bottom_addr(kthread->stacktop);
93         assert(!*kth_stack_poison);
94         *kth_stack_poison = 0xdeadbeef;
95 #endif /* CONFIG_KTHREAD_POISON */
96         /* Only change current if we need to (the kthread was in process context) */
97         if (kthread->proc) {
98                 /* Load our page tables before potentially decreffing cur_proc */
99                 lcr3(kthread->proc->env_cr3);
100                 /* Might have to clear out an existing current.  If they need to be set
101                  * later (like in restartcore), it'll be done on demand. */
102                 if (pcpui->cur_proc)
103                         proc_decref(pcpui->cur_proc);
104                 /* We also transfer our counted ref from kthread->proc to cur_proc */
105                 pcpui->cur_proc = kthread->proc;
106         }
107         /* Tell the core which syscall we are running (if any) */
108         assert(!pcpui->cur_sysc);       /* catch bugs, prev user should clear */
109         pcpui->cur_sysc = kthread->sysc;
110         pcpui->cur_errbuf = kthread->errbuf;
111         /* Finally, restart our thread */
112         pop_kernel_ctx(&kthread->context);
113 }
114
115 /* Kmsg handler to launch/run a kthread.  This must be a routine message, since
116  * it does not return.  */
117 static void __launch_kthread(uint32_t srcid, long a0, long a1, long a2)
118 {
119         struct kthread *kthread = (struct kthread*)a0;
120         struct per_cpu_info *pcpui = &per_cpu_info[core_id()];
121         struct proc *cur_proc = pcpui->cur_proc;
122         
123         /* Make sure we are a routine kmsg */
124         assert(in_early_rkmsg_ctx(pcpui));
125         if (pcpui->owning_proc && pcpui->owning_proc != kthread->proc) {
126                 /* Some process should be running here that is not the same as the
127                  * kthread.  This means the _M is getting interrupted or otherwise
128                  * delayed.  If we want to do something other than run it (like send the
129                  * kmsg to another pcore, or ship the context from here to somewhere
130                  * else/deschedule it (like for an _S)), do it here.
131                  *
132                  * If you want to do something here, call out to the ksched, then
133                  * abandon_core(). */
134                 cmb();  /* do nothing/placeholder */
135         }
136         /* o/w, just run the kthread.  any trapframes that are supposed to run or
137          * were interrupted will run whenever the kthread smp_idles() or otherwise
138          * finishes.  We also need to clear the RKMSG context since we will not
139          * return from restart_kth. */
140         clear_rkmsg(pcpui);
141         restart_kthread(kthread);
142         assert(0);
143 }
144
145 /* Call this when a kthread becomes runnable/unblocked.  We don't do anything
146  * particularly smart yet, but when we do, we can put it here. */
147 void kthread_runnable(struct kthread *kthread)
148 {
149         uint32_t dst = core_id();
150         #if 0
151         /* turn this block on if you want to test migrating non-core0 kthreads */
152         switch (dst) {
153                 case 0:
154                         break;
155                 case 7:
156                         dst = 2;
157                         break;
158                 default:
159                         dst++;
160         }
161         #endif
162         /* For lack of anything better, send it to ourselves. (TODO: KSCHED) */
163         send_kernel_message(dst, __launch_kthread, (long)kthread, 0, 0,
164                             KMSG_ROUTINE);
165 }
166
167 /* Kmsg helper for kthread_yield */
168 static void __wake_me_up(uint32_t srcid, long a0, long a1, long a2)
169 {
170         struct semaphore *sem = (struct semaphore*)a0;
171         assert(sem_up(sem));
172 }
173
174 /* Stop the current kthread.  It'll get woken up next time we run routine kmsgs,
175  * after all existing kmsgs are processed. */
176 void kthread_yield(void)
177 {
178         struct semaphore local_sem, *sem = &local_sem;
179         sem_init(sem, 0);
180         send_kernel_message(core_id(), __wake_me_up, (long)sem, 0, 0,
181                             KMSG_ROUTINE);
182         sem_down(sem);
183 }
184
185 void check_poison(char *msg)
186 {
187 #ifdef CONFIG_KTHREAD_POISON
188         struct per_cpu_info *pcpui = &per_cpu_info[core_id()];
189         assert(pcpui->cur_kthread && pcpui->cur_kthread->stacktop);
190         if (*kstack_bottom_addr(pcpui->cur_kthread->stacktop) != 0xdeadbeef) {
191                 printk("\nBad kthread canary, msg: %s\n", msg);
192                 panic("");
193         }
194 #endif /* CONFIG_KTHREAD_POISON */
195 }
196
197 /* Semaphores, using kthreads directly */
198 void sem_init(struct semaphore *sem, int signals)
199 {
200         TAILQ_INIT(&sem->waiters);
201         sem->nr_signals = signals;
202         spinlock_init(&sem->lock);
203         sem->irq_okay = FALSE;
204 }
205
206 void sem_init_irqsave(struct semaphore *sem, int signals)
207 {
208         TAILQ_INIT(&sem->waiters);
209         sem->nr_signals = signals;
210         spinlock_init_irqsave(&sem->lock);
211         sem->irq_okay = TRUE;
212 }
213
214 /* This downs the semaphore and suspends the current kernel context on its
215  * waitqueue if there are no pending signals.  Note that the case where the
216  * signal is already there is not optimized. */
217 void sem_down(struct semaphore *sem)
218 {
219         volatile bool blocking = TRUE;  /* signal to short circuit when restarting*/
220         struct kthread *kthread, *new_kthread;
221         register uintptr_t new_stacktop;
222         struct per_cpu_info *pcpui = &per_cpu_info[core_id()];
223
224         assert(can_block(pcpui));
225         /* Make sure we aren't holding any locks (only works if SPINLOCK_DEBUG) */
226         assert(!pcpui->lock_depth);
227         assert(pcpui->cur_kthread);
228         /* Try to down the semaphore.  If there is a signal there, we can skip all
229          * of the sleep prep and just return. */
230         spin_lock(&sem->lock);  /* no need for irqsave, since we disabled ints */
231         if (sem->nr_signals > 0) {
232                 sem->nr_signals--;
233                 spin_unlock(&sem->lock);
234                 goto block_return_path;
235         }
236         spin_unlock(&sem->lock);
237         /* We're probably going to sleep, so get ready.  We'll check again later. */
238         kthread = pcpui->cur_kthread;
239         /* We need to have a spare slot for restart, so we also use it when
240          * sleeping.  Right now, we need a new kthread to take over if/when our
241          * current kthread sleeps.  Use the spare, and if not, get a new one.
242          *
243          * Note we do this with interrupts disabled (which protects us from
244          * concurrent modifications). */
245         if (pcpui->spare) {
246                 new_kthread = pcpui->spare;
247                 new_stacktop = new_kthread->stacktop;
248                 pcpui->spare = 0;
249         } else {
250                 new_kthread = __kthread_zalloc();
251                 new_stacktop = get_kstack();
252                 new_kthread->stacktop = new_stacktop;
253 #ifdef CONFIG_KTHREAD_POISON
254                 *kstack_bottom_addr(new_stacktop) = 0;
255 #endif /* CONFIG_KTHREAD_POISON */
256         }
257         /* Set the core's new default stack and kthread */
258         set_stack_top(new_stacktop);
259         pcpui->cur_kthread = new_kthread;
260 #ifdef CONFIG_KTHREAD_POISON
261         /* Mark the new stack as in-use, and unmark the current kthread */
262         uintptr_t *new_stack_poison, *kth_stack_poison;
263         new_stack_poison = kstack_bottom_addr(new_stacktop);
264         assert(!*new_stack_poison);
265         *new_stack_poison = 0xdeadbeef;
266         kth_stack_poison = kstack_bottom_addr(kthread->stacktop);
267         assert(*kth_stack_poison == 0xdeadbeef);
268         *kth_stack_poison = 0;
269 #endif /* CONFIG_KTHREAD_POISON */
270         /* The kthread needs to stay in the process context (if there is one), but
271          * we want the core (which could be a vcore) to stay in the context too.  In
272          * the future, we could check owning_proc. If it isn't set, we could leave
273          * the process context and transfer the refcnt to kthread->proc. */
274         kthread->proc = current;
275         /* kthread tracks the syscall it is working on, which implies errno */
276         kthread->sysc = pcpui->cur_sysc;
277         kthread->errbuf = pcpui->cur_errbuf;
278         pcpui->cur_sysc = 0;                            /* this core no longer works on sysc */
279         pcpui->cur_errbuf = 0;                          /* this core no longer has an errbuf */
280         if (kthread->proc)
281                 proc_incref(kthread->proc, 1);
282         /* Save the context, toggle blocking for the reactivation */
283         save_kernel_ctx(&kthread->context);
284         if (!blocking)
285                 goto block_return_path;
286         blocking = FALSE;                                       /* for when it starts back up */
287         /* Down the semaphore.  We need this to be inline.  If we're sleeping, once
288          * we unlock the kthread could be started up again and can return and start
289          * trashing this function's stack, hence the weird control flow. */
290         spin_lock(&sem->lock);
291         if (sem->nr_signals-- <= 0) {
292                 TAILQ_INSERT_TAIL(&sem->waiters, kthread, link);
293                 /* At this point, we know we'll sleep and change stacks later.  Once we
294                  * unlock, we could have the kthread restarted (possibly on another
295                  * core), so we need to disable irqs until we are on our new stack.
296                  * Otherwise, if we take an IRQ, we'll be using our stack while another
297                  * core is using it (restarted kthread).  Basically, disabling irqs
298                  * allows us to atomically unlock and 'yield'. */
299                 disable_irq();
300         } else {                                                        /* we didn't sleep */
301                 goto unwind_sleep_prep;
302         }
303         spin_unlock(&sem->lock);
304         /* Switch to the core's default stack.  After this, don't use local
305          * variables.  TODO: we shouldn't be using new_stacktop either, can't always
306          * trust the register keyword (AFAIK). */
307         set_stack_pointer(new_stacktop);
308         smp_idle();                                                     /* reenables irqs eventually */
309         /* smp_idle never returns */
310         assert(0);
311 unwind_sleep_prep:
312         /* We get here if we should not sleep on sem (the signal beat the sleep).
313          * Note we are not optimizing for cases where the signal won. */
314         spin_unlock(&sem->lock);
315         printd("[kernel] Didn't sleep, unwinding...\n");
316         /* Restore the core's current and default stacktop */
317         current = kthread->proc;                        /* arguably unnecessary */
318         if (kthread->proc)
319                 proc_decref(kthread->proc);
320         set_stack_top(kthread->stacktop);
321         pcpui->cur_kthread = kthread;
322         /* Save the allocs as the spare */
323         assert(!pcpui->spare);
324         pcpui->spare = new_kthread;
325 #ifdef CONFIG_KTHREAD_POISON
326         /* switch back to old stack in use, new one not */
327         *new_stack_poison = 0;
328         *kth_stack_poison = 0xdeadbeef;
329 #endif /* CONFIG_KTHREAD_POISON */
330 block_return_path:
331         printd("[kernel] Returning from being 'blocked'! at %llu\n", read_tsc());
332         return;
333 }
334
335 /* Ups the semaphore.  If it was < 0, we need to wake up someone, which we do.
336  * Returns TRUE if we woke someone, FALSE o/w (used for debugging in some
337  * places).  If we need more control, we can implement a version of the old
338  * __up_sem() again.  */
339 bool sem_up(struct semaphore *sem)
340 {
341         struct kthread *kthread = 0;
342         spin_lock(&sem->lock);
343         if (sem->nr_signals++ < 0) {
344                 assert(!TAILQ_EMPTY(&sem->waiters));
345                 /* could do something with 'priority' here */
346                 kthread = TAILQ_FIRST(&sem->waiters);
347                 TAILQ_REMOVE(&sem->waiters, kthread, link);
348         } else {
349                 assert(TAILQ_EMPTY(&sem->waiters));
350         }
351         spin_unlock(&sem->lock);
352         /* Note that once we call kthread_runnable(), we cannot touch the sem again.
353          * Some sems are on stacks.  The caller can touch sem, if it knows about the
354          * memory/usage of the sem.  Likewise, we can't touch the kthread either. */
355         if (kthread) {
356                 kthread_runnable(kthread);
357                 return TRUE;
358         }
359         return FALSE;
360 }
361
362 void sem_down_irqsave(struct semaphore *sem, int8_t *irq_state)
363 {
364         disable_irqsave(irq_state);
365         sem_down(sem);
366         enable_irqsave(irq_state);
367 }
368
369 bool sem_up_irqsave(struct semaphore *sem, int8_t *irq_state)
370 {
371         bool retval;
372         disable_irqsave(irq_state);
373         retval = sem_up(sem);
374         enable_irqsave(irq_state);
375         return retval;
376 }
377
378 /* Condition variables, using semaphores and kthreads */
379 void cv_init(struct cond_var *cv)
380 {
381         sem_init(&cv->sem, 0);
382         cv->lock = &cv->internal_lock;
383         spinlock_init(cv->lock);
384         cv->nr_waiters = 0;
385         cv->irq_okay = FALSE;
386 }
387
388 void cv_init_irqsave(struct cond_var *cv)
389 {
390         sem_init_irqsave(&cv->sem, 0);
391         cv->lock = &cv->internal_lock;
392         spinlock_init_irqsave(cv->lock);
393         cv->nr_waiters = 0;
394         cv->irq_okay = TRUE;
395 }
396
397 void cv_init_with_lock(struct cond_var *cv, spinlock_t *lock)
398 {
399         sem_init(&cv->sem, 0);
400         cv->nr_waiters = 0;
401         cv->lock = lock;
402         cv->irq_okay = FALSE;
403 }
404
405 void cv_init_irqsave_with_lock(struct cond_var *cv, spinlock_t *lock)
406 {
407         sem_init_irqsave(&cv->sem, 0);
408         cv->nr_waiters = 0;
409         cv->lock = lock;
410         cv->irq_okay = TRUE;
411 }
412
413 void cv_lock(struct cond_var *cv)
414 {
415         spin_lock(cv->lock);
416 }
417
418 void cv_unlock(struct cond_var *cv)
419 {
420         spin_unlock(cv->lock);
421 }
422
423 void cv_lock_irqsave(struct cond_var *cv, int8_t *irq_state)
424 {
425         disable_irqsave(irq_state);
426         cv_lock(cv);
427 }
428
429 void cv_unlock_irqsave(struct cond_var *cv, int8_t *irq_state)
430 {
431         cv_unlock(cv);
432         enable_irqsave(irq_state);
433 }
434
435 /* Helper to clarify the wait/signalling code */
436 static int nr_sem_waiters(struct semaphore *sem)
437 {
438         int retval;
439         retval = 0 - sem->nr_signals;
440         assert(retval >= 0);
441         return retval;
442 }
443
444 /* Comes in locked.  Note we don't mess with enabling/disabling irqs.  The
445  * initial cv_lock would have disabled irqs (if applicable), and we don't mess
446  * with that setting at all. */
447 void cv_wait_and_unlock(struct cond_var *cv)
448 {
449         unsigned long nr_prev_waiters;
450         nr_prev_waiters = cv->nr_waiters++;
451         spin_unlock(cv->lock);
452         /* Wait til our turn.  This forces an ordering of all waiters such that the
453          * order in which they wait is the order in which they down the sem. */
454         while (nr_prev_waiters != nr_sem_waiters(&cv->sem))
455                 cpu_relax();
456         printd("core %d, sees nr_sem_waiters: %d, cv_nr_waiters %d\n",
457                core_id(), nr_sem_waiters(&cv->sem), cv->nr_waiters);
458         /* Atomically sleeps and 'unlocks' the next kthread from its busy loop (the
459          * one right above this), when it changes the sems nr_signals/waiters. */
460         sem_down(&cv->sem);
461 }
462
463 /* Comes in locked.  Note cv_lock does not disable irqs.   They should still be
464  * disabled from the initial cv_lock_irqsave(). */
465 void cv_wait(struct cond_var *cv)
466 {
467         cv_wait_and_unlock(cv);
468         if (cv->irq_okay)
469                 assert(!irq_is_enabled());
470         cv_lock(cv);
471 }
472
473 /* Helper, wakes exactly one, and there should have been at least one waiter. */
474 static void sem_wake_one(struct semaphore *sem)
475 {
476         struct kthread *kthread;
477         /* these locks will be irqsaved if the CV is irqsave (only need the one) */
478         spin_lock(&sem->lock);
479         assert(sem->nr_signals < 0);
480         sem->nr_signals++;
481         kthread = TAILQ_FIRST(&sem->waiters);
482         TAILQ_REMOVE(&sem->waiters, kthread, link);
483         spin_unlock(&sem->lock);
484         kthread_runnable(kthread);
485 }
486
487 void __cv_signal(struct cond_var *cv)
488 {
489         /* Can't short circuit this stuff.  We need to make sure any waiters that
490          * made it past upping the cv->nr_waiters has also downed the sem.
491          * Otherwise we muck with nr_waiters, which could break the ordering
492          * required by the waiters.  We also need to lock while making this check,
493          * o/w a new waiter can slip in after our while loop. */
494         while (cv->nr_waiters != nr_sem_waiters(&cv->sem))
495                 cpu_relax();
496         if (cv->nr_waiters) {
497                 cv->nr_waiters--;
498                 sem_wake_one(&cv->sem);
499         }
500 }
501
502 void __cv_broadcast(struct cond_var *cv)
503 {
504         while (cv->nr_waiters != nr_sem_waiters(&cv->sem))
505                 cpu_relax();
506         while (cv->nr_waiters) {
507                 cv->nr_waiters--;
508                 sem_wake_one(&cv->sem);
509         }
510 }
511
512 void cv_signal(struct cond_var *cv)
513 {
514         spin_lock(cv->lock);
515         __cv_signal(cv);
516         spin_unlock(cv->lock);
517 }
518
519 void cv_broadcast(struct cond_var *cv)
520 {
521         spin_lock(cv->lock);
522         __cv_broadcast(cv);
523         spin_unlock(cv->lock);
524 }
525
526 void cv_signal_irqsave(struct cond_var *cv, int8_t *irq_state)
527 {
528         disable_irqsave(irq_state);
529         cv_signal(cv);
530         enable_irqsave(irq_state);
531 }
532
533 void cv_broadcast_irqsave(struct cond_var *cv, int8_t *irq_state)
534 {
535         disable_irqsave(irq_state);
536         cv_broadcast(cv);
537         enable_irqsave(irq_state);
538 }