Condition variables
[akaros.git] / kern / src / kthread.c
1 /* Copyright (c) 2010 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 struct kmem_cache *kthread_kcache;
16
17 void kthread_init(void)
18 {
19         kthread_kcache = kmem_cache_create("kthread", sizeof(struct kthread),
20                                            __alignof__(struct kthread), 0, 0, 0);
21 }
22
23 /* This downs the semaphore and suspends the current kernel context on its
24  * waitqueue if there are no pending signals.  Note that the case where the
25  * signal is already there is not optimized. */
26 void sleep_on(struct semaphore *sem)
27 {
28         volatile bool blocking = TRUE;  /* signal to short circuit when restarting*/
29         struct kthread *kthread;
30         struct page *page;                              /* assumption here that stacks are PGSIZE */
31         register uintptr_t new_stacktop;
32         int8_t irq_state = 0;
33         struct per_cpu_info *pcpui = &per_cpu_info[core_id()];
34
35         /* interrupts would be messy here */
36         disable_irqsave(&irq_state);
37         /* Make sure we aren't holding any locks (only works if SPINLOCK_DEBUG) */
38         assert(!pcpui->lock_depth);
39         /* Try to down the semaphore.  If there is a signal there, we can skip all
40          * of the sleep prep and just return. */
41         spin_lock(&sem->lock);  /* no need for irqsave, since we disabled ints */
42         if (sem->nr_signals > 0) {
43                 sem->nr_signals--;
44                 spin_unlock(&sem->lock);
45                 goto block_return_path_np;
46         }
47         /* we're probably going to sleep, so get ready.  We'll check again later. */
48         spin_unlock(&sem->lock);
49         /* Try to get the spare first.  If there is one, we'll use it (o/w, we'll
50          * get a fresh kthread.  Why we need this is more clear when we try to
51          * restart kthreads.  Having them also ought to cut down on contention.
52          * Note we do this with interrupts disabled (which protects us from
53          * concurrent modifications). */
54         if (pcpui->spare) {
55                 kthread = pcpui->spare;
56                 /* we're using the spare, so we use the page the spare held */
57                 new_stacktop = kthread->stacktop;
58                 pcpui->spare = 0;
59         } else {
60                 kthread = kmem_cache_alloc(kthread_kcache, 0);
61                 assert(kthread);
62                 assert(!kpage_alloc(&page));    /* decref'd when the kthread is freed */
63 #ifdef __CONFIG_KTHREAD_POISON__
64                 /* TODO: KTHR-STACK don't poison like this */
65                 *(uintptr_t*)page2kva(page) = 0;
66 #endif /* __CONFIG_KTHREAD_POISON__ */
67                 new_stacktop = (uintptr_t)page2kva(page) + PGSIZE;
68         }
69         /* This is the stacktop we are currently on and wish to save */
70         kthread->stacktop = get_stack_top();
71         /* Set the core's new default stack */
72         set_stack_top(new_stacktop);
73 #ifdef __CONFIG_KTHREAD_POISON__
74         /* Mark the new stack as in-use, and unmark the current kthread */
75         /* TODO: KTHR-STACK don't poison like this */
76         uintptr_t *new_stack_poison, *kth_stack_poison;
77         new_stack_poison = (uintptr_t*)ROUNDDOWN(new_stacktop - 1, PGSIZE);
78         assert(!*new_stack_poison);
79         *new_stack_poison = 0xdeadbeef;
80         kth_stack_poison = (uintptr_t*)ROUNDDOWN(kthread->stacktop - 1, PGSIZE);
81         assert(*kth_stack_poison == 0xdeadbeef);
82         *kth_stack_poison = 0;
83 #endif /* __CONFIG_KTHREAD_POISON__ */
84         /* The kthread needs to stay in the process context (if there is one), but
85          * we want the core (which could be a vcore) to stay in the context too.  In
86          * the future, we could check owning_proc. If it isn't set, we could leave
87          * the process context and transfer the refcnt to kthread->proc. */
88         kthread->proc = current;
89         /* kthread tracks the syscall it is working on, which implies errno */
90         kthread->sysc = pcpui->cur_sysc;
91         pcpui->cur_sysc = 0;                            /* this core no longer works on sysc */
92         if (kthread->proc)
93                 proc_incref(kthread->proc, 1);
94         /* Save the context, toggle blocking for the reactivation */
95         save_kernel_tf(&kthread->context);
96         if (!blocking)
97                 goto block_return_path;
98         blocking = FALSE;                                       /* for when it starts back up */
99         /* Down the semaphore.  We need this to be inline.  If we're sleeping, once
100          * we unlock the kthread could be started up again and can return and start
101          * trashing this function's stack, hence the weird control flow. */
102         spin_lock(&sem->lock);  /* no need for irqsave, since we disabled ints */
103         if (sem->nr_signals-- <= 0)
104                 TAILQ_INSERT_TAIL(&sem->waiters, kthread, link);
105         else                                                            /* we didn't sleep */
106                 goto unwind_sleep_prep;
107         spin_unlock(&sem->lock);
108         /* Switch to the core's default stack.  After this, don't use local
109          * variables.  TODO: we shouldn't be using new_stacktop either, can't always
110          * trust the register keyword (AFAIK). */
111         set_stack_pointer(new_stacktop);
112         smp_idle();
113         /* smp_idle never returns */
114         assert(0);
115 unwind_sleep_prep:
116         /* We get here if we should not sleep on sem (the signal beat the sleep).
117          * Note we are not optimizing for cases where the signal won. */
118         spin_unlock(&sem->lock);
119         printd("[kernel] Didn't sleep, unwinding...\n");
120         /* Restore the core's current and default stacktop */
121         current = kthread->proc;                        /* arguably unnecessary */
122         if (kthread->proc)
123                 proc_decref(kthread->proc);
124         set_stack_top(kthread->stacktop);
125         /* Save the allocs as the spare */
126         assert(!pcpui->spare);
127         pcpui->spare = kthread;
128         /* save the "freshly alloc'd" stack/page, not the one we came in on */
129         kthread->stacktop = new_stacktop;
130 #ifdef __CONFIG_KTHREAD_POISON__
131         /* TODO: KTHR-STACK don't unpoison like this */
132         /* switch back to old stack in use, new one not */
133         *new_stack_poison = 0;
134         *kth_stack_poison = 0xdeadbeef;
135 #endif /* __CONFIG_KTHREAD_POISON__ */
136 block_return_path:
137         printd("[kernel] Returning from being 'blocked'! at %llu\n", read_tsc());
138 block_return_path_np:
139         enable_irqsave(&irq_state);
140         return;
141 }
142
143 /* Starts kthread on the calling core.  This does not return, and will handle
144  * the details of cleaning up whatever is currently running (freeing its stack,
145  * etc). */
146 void restart_kthread(struct kthread *kthread)
147 {
148         struct per_cpu_info *pcpui = &per_cpu_info[core_id()];
149         uintptr_t current_stacktop;
150         /* Avoid messy complications.  The kthread will enable_irqsave() when it
151          * comes back up. */
152         disable_irq();
153         /* Free any spare, since we need ours to become the spare (since we can't
154          * free our current kthread *before* popping it, nor can we free the current
155          * stack until we pop to the kthread's stack). */
156         if (pcpui->spare) {
157                 /* assumes the stack is a page, and that stacktop is somewhere in
158                  * (pg_bottom, pg_bottom + PGSIZE].  Normally, it ought to be pg_bottom
159                  * + PGSIZE (on x86).  kva2page can take any kva, not just a page
160                  * aligned addr. */
161                 page_decref(kva2page((void*)pcpui->spare->stacktop - 1));
162                 kmem_cache_free(kthread_kcache, pcpui->spare);
163         }
164         current_stacktop = get_stack_top();
165         /* When a kthread runs, its stack is the default kernel stack */
166         set_stack_top(kthread->stacktop);
167 #ifdef __CONFIG_KTHREAD_POISON__
168         /* TODO: KTHR-STACK */
169         /* Assert and switch to cur stack not in use, kthr stack in use */
170         uintptr_t *cur_stack_poison, *kth_stack_poison;
171         cur_stack_poison = (uintptr_t*)ROUNDDOWN(current_stacktop - 1, PGSIZE);
172         assert(*cur_stack_poison == 0xdeadbeef);
173         *cur_stack_poison = 0;
174         kth_stack_poison = (uintptr_t*)ROUNDDOWN(kthread->stacktop - 1, PGSIZE);
175         assert(!*kth_stack_poison);
176         *kth_stack_poison = 0xdeadbeef;
177 #endif /* __CONFIG_KTHREAD_POISON__ */
178         /* Set the spare stuff (current kthread, current (not kthread) stacktop) */
179         pcpui->spare = kthread;
180         kthread->stacktop = current_stacktop;
181         /* Only change current if we need to (the kthread was in process context) */
182         if (kthread->proc) {
183                 /* Load our page tables before potentially decreffing cur_proc */
184                 lcr3(kthread->proc->env_cr3);
185                 /* Might have to clear out an existing current.  If they need to be set
186                  * later (like in restartcore), it'll be done on demand. */
187                 if (pcpui->cur_proc)
188                         proc_decref(pcpui->cur_proc);
189                 /* We also transfer our counted ref from kthread->proc to cur_proc */
190                 pcpui->cur_proc = kthread->proc;
191         }
192         /* Tell the core which syscall we are running (if any) */
193         assert(!pcpui->cur_sysc);       /* catch bugs, prev user should clear */
194         pcpui->cur_sysc = kthread->sysc;
195         /* Finally, restart our thread */
196         pop_kernel_tf(&kthread->context);
197 }
198
199 /* Call this when a kthread becomes runnable/unblocked.  We don't do anything
200  * particularly smart yet, but when we do, we can put it here. */
201 void kthread_runnable(struct kthread *kthread)
202 {
203         uint32_t dst = core_id();
204         #if 0
205         /* turn this block on if you want to test migrating non-core0 kthreads */
206         switch (dst) {
207                 case 0:
208                         break;
209                 case 7:
210                         dst = 2;
211                         break;
212                 default:
213                         dst++;
214         }
215         #endif
216         /* For lack of anything better, send it to ourselves. (TODO: KSCHED) */
217         send_kernel_message(dst, __launch_kthread, (long)kthread, 0, 0,
218                             KMSG_ROUTINE);
219 }
220
221 /* Kmsg handler to launch/run a kthread.  This must be a routine message, since
222  * it does not return.  */
223 void __launch_kthread(struct trapframe *tf, uint32_t srcid, long a0, long a1,
224                           long a2)
225 {
226         struct kthread *kthread = (struct kthread*)a0;
227         struct per_cpu_info *pcpui = &per_cpu_info[core_id()];
228         struct proc *cur_proc = pcpui->cur_proc;
229         
230         if (pcpui->owning_proc && pcpui->owning_proc != kthread->proc) {
231                 /* Some process should be running here that is not the same as the
232                  * kthread.  This means the _M is getting interrupted or otherwise
233                  * delayed.  If we want to do something other than run it (like send the
234                  * kmsg to another pcore, or ship the context from here to somewhere
235                  * else/deschedule it (like for an _S)), do it here. */
236                 cmb();  /* do nothing/placeholder */
237                 #if 0
238                 /* example of something to do (wrap up and schedule an _S).  Note this
239                  * might not work perfectly, but is just an example.  One thing to be
240                  * careful of is that spin_lock() can't be called if __launch isn't
241                  * ROUTINE (which it is right now). */
242                 if (pcpui->owning_proc->state == PROC_RUNNING_S) {
243                         spin_lock(&pcpui->owning_proc->proc_lock);
244                         /* Wrap up / yield the _S proc */
245                         __proc_set_state(pcpui->owning_proc, PROC_WAITING);
246                         __proc_save_context_s(pcpui->owning_proc, current_tf);
247                         spin_unlock(&pcpui->owning_proc->proc_lock);
248                         proc_wakeup(p);
249                         abandon_core();
250                         /* prob need to clear the owning proc?  this is some old shit, so
251                          * don't just uncomment it. */
252                 }
253                 #endif
254         }
255         /* o/w, just run the kthread.  any trapframes that are supposed to run or
256          * were interrupted will run whenever the kthread smp_idles() or otherwise
257          * finishes. */
258         restart_kthread(kthread);
259         assert(0);
260 }
261
262 /* Stop the current kthread.  It'll get woken up next time we run routine kmsgs,
263  * after all existing kmsgs are processed. */
264 void kthread_yield(void)
265 {
266         struct semaphore local_sem, *sem = &local_sem;
267         void __wake_me_up(struct trapframe *tf, uint32_t srcid, long a0, long a1,
268                           long a2)
269         {
270                 struct kthread *me = __up_sem(sem, TRUE);
271                 assert(me);
272                 kthread_runnable(me);
273         }
274         init_sem(sem, 0);
275         send_kernel_message(core_id(), __wake_me_up, 0, 0, 0, KMSG_ROUTINE);
276         sleep_on(sem);
277 }
278
279 /* Condition variables, using semaphores and kthreads */
280 void cv_init(struct cond_var *cv)
281 {
282         init_sem(&cv->sem, 0);
283         spinlock_init(&cv->lock);
284         cv->nr_waiters = 0;
285 }
286
287 void cv_lock(struct cond_var *cv)
288 {
289         spin_lock_irqsave(&cv->lock);
290 }
291
292 void cv_unlock(struct cond_var *cv)
293 {
294         spin_unlock_irqsave(&cv->lock);
295 }
296
297 /* Helper to clarify the wait/signalling code */
298 static int nr_sem_waiters(struct semaphore *sem)
299 {
300         int retval;
301         retval = 0 - sem->nr_signals;
302         assert(retval >= 0);
303         return retval;
304 }
305
306 /* Comes in locked */
307 void cv_wait_and_unlock(struct cond_var *cv)
308 {
309         unsigned long nr_prev_waiters;
310         nr_prev_waiters = cv->nr_waiters++;
311         spin_unlock_irqsave(&cv->lock);
312         /* Wait til our turn.  This forces an ordering of all waiters such that the
313          * order in which they wait is the order in which they down the sem. */
314         while (nr_prev_waiters != nr_sem_waiters(&cv->sem))
315                 cpu_relax();
316         printd("core %d, sees nr_sem_waiters: %d, cv_nr_waiters %d\n",
317                core_id(), nr_sem_waiters(&cv->sem), cv->nr_waiters);
318         /* Atomically sleeps and 'unlocks' the next kthread from its busy loop (the
319          * one right above this), when it changes the sems nr_signals/waiters. */
320         sleep_on(&cv->sem);
321 }
322
323 /* Comes in locked */
324 void cv_wait(struct cond_var *cv)
325 {
326         cv_wait_and_unlock(cv);
327         cv_lock(cv);
328 }
329
330 /* Helper, wakes exactly one, and there should have been at least one waiter. */
331 static void sem_wake_one(struct semaphore *sem)
332 {
333         struct kthread *kthread;
334         spin_lock_irqsave(&sem->lock);
335         assert(sem->nr_signals < 0);
336         sem->nr_signals++;
337         kthread = TAILQ_FIRST(&sem->waiters);
338         TAILQ_REMOVE(&sem->waiters, kthread, link);
339         spin_unlock_irqsave(&sem->lock);
340         kthread_runnable(kthread);
341 }
342
343 void cv_signal(struct cond_var *cv)
344 {
345         spin_lock_irqsave(&cv->lock);
346         /* Can't short circuit this stuff.  We need to make sure any waiters that
347          * made it past upping the cv->nr_waiters has also downed the sem.
348          * Otherwise we muck with nr_waiters, which could break the ordering
349          * required by the waiters.  We also need to lock while making this check,
350          * o/w a new waiter can slip in after our while loop. */
351         while (cv->nr_waiters != nr_sem_waiters(&cv->sem))
352                 cpu_relax();
353         if (cv->nr_waiters) {
354                 cv->nr_waiters--;
355                 sem_wake_one(&cv->sem);
356         }
357         spin_unlock_irqsave(&cv->lock);
358 }
359
360 void cv_broadcast(struct cond_var *cv)
361 {
362         spin_lock_irqsave(&cv->lock);
363         while (cv->nr_waiters != nr_sem_waiters(&cv->sem))
364                 cpu_relax();
365         while (cv->nr_waiters) {
366                 cv->nr_waiters--;
367                 sem_wake_one(&cv->sem);
368         }
369         spin_unlock_irqsave(&cv->lock);
370 }