73d8d6ee92701176d629a843053fdf351d243dd8
[akaros.git] / user / parlib / vcore.c
1 #include <arch/arch.h>
2 #include <stdbool.h>
3 #include <errno.h>
4 #include <vcore.h>
5 #include <mcs.h>
6 #include <sys/param.h>
7 #include <parlib.h>
8 #include <unistd.h>
9 #include <stdlib.h>
10 #include <sys/mman.h>
11 #include <stdio.h>
12 #include <glibc-tls.h>
13 #include <event.h>
14 #include <uthread.h>
15 #include <ucq.h>
16 #include <ros/arch/membar.h>
17
18 /* starting with 1 since we alloc vcore0's stacks and TLS in vcore_init(). */
19 static size_t _max_vcores_ever_wanted = 1;
20 atomic_t nr_new_vcores_wanted;
21 atomic_t vc_req_being_handled;
22 /* Simple ev_q (bits, IPIs, vc0) for scp syscalls, signals, etc */
23 struct event_queue *__scp_simple_evq = 0;
24
25 extern void** vcore_thread_control_blocks;
26
27 /* Get a TLS, returns 0 on failure.  Vcores have their own TLS, and any thread
28  * created by a user-level scheduler needs to create a TLS as well. */
29 void *allocate_tls(void)
30 {
31         extern void *_dl_allocate_tls(void *mem) internal_function;
32         void *tcb = _dl_allocate_tls(NULL);
33         if (!tcb)
34                 return 0;
35         /* Make sure the TLS is set up properly - its tcb pointer points to itself.
36          * Keep this in sync with sysdeps/ros/XXX/tls.h.  For whatever reason,
37          * dynamically linked programs do not need this to be redone, but statics
38          * do. */
39         tcbhead_t *head = (tcbhead_t*)tcb;
40         head->tcb = tcb;
41         head->self = tcb;
42         return tcb;
43 }
44
45 /* Free a previously allocated TLS region */
46 void free_tls(void *tcb)
47 {
48         extern void _dl_deallocate_tls (void *tcb, bool dealloc_tcb) internal_function;
49         assert(tcb);
50         _dl_deallocate_tls(tcb, TRUE);
51 }
52
53 /* Reinitialize / reset / refresh a TLS to its initial values.  This doesn't do
54  * it properly yet, it merely frees and re-allocates the TLS, which is why we're
55  * slightly ghetto and return the pointer you should use for the TCB. */
56 void *reinit_tls(void *tcb)
57 {
58         /* TODO: keep this in sync with the methods used in
59          * allocate_transition_tls() */
60         free_tls(tcb);
61         return allocate_tls();
62 }
63
64 /* TODO: probably don't want to dealloc.  Considering caching */
65 static void free_transition_tls(int id)
66 {
67         if(vcore_thread_control_blocks[id])
68         {
69                 free_tls(vcore_thread_control_blocks[id]);
70                 vcore_thread_control_blocks[id] = NULL;
71         }
72 }
73
74 static int allocate_transition_tls(int id)
75 {
76         /* We want to free and then reallocate the tls rather than simply 
77          * reinitializing it because its size may have changed.  TODO: not sure if
78          * this is right.  0-ing is one thing, but freeing and reallocating can be
79          * expensive, esp if syscalls are involved.  Check out glibc's
80          * allocatestack.c for what might work. */
81         free_transition_tls(id);
82
83         void *tcb = allocate_tls();
84
85         if ((vcore_thread_control_blocks[id] = tcb) == NULL) {
86                 errno = ENOMEM;
87                 return -1;
88         }
89         return 0;
90 }
91
92 static void free_transition_stack(int id)
93 {
94         // don't actually free stacks
95 }
96
97 static int allocate_transition_stack(int id)
98 {
99         struct preempt_data *vcpd = vcpd_of(id);
100         if (vcpd->transition_stack)
101                 return 0; // reuse old stack
102
103         void* stackbot = mmap(0, TRANSITION_STACK_SIZE,
104                               PROT_READ|PROT_WRITE|PROT_EXEC,
105                               MAP_POPULATE|MAP_ANONYMOUS, -1, 0);
106
107         if(stackbot == MAP_FAILED)
108                 return -1; // errno set by mmap
109
110         vcpd->transition_stack = (uintptr_t)stackbot + TRANSITION_STACK_SIZE;
111
112         return 0;
113 }
114
115 int vcore_init()
116 {
117         static int initialized = 0;
118         uintptr_t mmap_block;
119         /* Note this is racy, but okay.  The only time it'll be 0 is the first time
120          * through, when we are _S */
121         if(initialized)
122                 return 0;
123
124         vcore_thread_control_blocks = (void**)calloc(max_vcores(),sizeof(void*));
125
126         if(!vcore_thread_control_blocks)
127                 goto vcore_init_fail;
128
129         /* Need to alloc vcore0's transition stuff here (technically, just the TLS)
130          * so that schedulers can use vcore0's transition TLS before it comes up in
131          * vcore_entry() */
132         if(allocate_transition_stack(0) || allocate_transition_tls(0))
133                 goto vcore_init_tls_fail;
134
135         /* Initialize our VCPD event queues' ucqs, two pages per ucq, 4 per vcore */
136         mmap_block = (uintptr_t)mmap(0, PGSIZE * 4 * max_vcores(),
137                                      PROT_WRITE | PROT_READ,
138                                      MAP_POPULATE | MAP_ANONYMOUS, -1, 0);
139         /* Yeah, this doesn't fit in the error-handling scheme, but this whole
140          * system doesn't really handle failure, and needs a rewrite involving less
141          * mmaps/munmaps. */
142         assert(mmap_block);
143         /* Note we may end up doing vcore 0's elsewhere, for _Ss, or else have a
144          * separate ev_q for that. */
145         for (int i = 0; i < max_vcores(); i++) {
146                 /* four pages total for both ucqs from the big block (2 pages each) */
147                 ucq_init_raw(&vcpd_of(i)->ev_mbox_public.ev_msgs,
148                              mmap_block + (4 * i    ) * PGSIZE,
149                              mmap_block + (4 * i + 1) * PGSIZE);
150                 ucq_init_raw(&vcpd_of(i)->ev_mbox_private.ev_msgs,
151                              mmap_block + (4 * i + 2) * PGSIZE,
152                              mmap_block + (4 * i + 3) * PGSIZE);
153         }
154         atomic_init(&vc_req_being_handled, 0);
155         assert(!in_vcore_context());
156         initialized = 1;
157         /* no longer need to enable notifs on vcore 0, it is set like that by
158          * default (so you drop into vcore context immediately on transtioning to
159          * _M) */
160         return 0;
161 vcore_init_tls_fail:
162         free(vcore_thread_control_blocks);
163 vcore_init_fail:
164         errno = ENOMEM;
165         return -1;
166 }
167
168 /* this, plus tricking gcc into thinking this is -u (undefined), AND including
169  * the event_init in it, causes the linker to need to check parlib.a and see the
170  * strong symbol... */
171 void force_parlib_symbols(void)
172 {
173         vcore_event_init();
174         ros_syscall_blockon(0); /* don't seem to need to force this for now */
175         assert(0);
176 }
177
178 /* This gets called in glibc before calling the programs 'main'.  Need to set
179  * ourselves up so that thread0 is a uthread, and then register basic signals to
180  * go to vcore 0. */
181 void vcore_event_init(void)
182 {
183         /* set up our thread0 as a uthread */
184         uthread_slim_init();
185         /* Set up an ev_q for blocking _Ss on syscalls.  Events will get sent to
186          * vcore0's VCPD public mbox.  We'll get a bit, instead of a full message,
187          * since we don't need to know *sysc.  Also note that the event handler is
188          * 0, until set by a 2LS.  We don't need a handler - just need to get woken
189          * up. */
190         __scp_simple_evq = get_event_q_vcpd(0, EVENT_NOMSG | EVENT_IPI);
191         /* TODO: register for other kevents/signals and whatnot (can probably reuse
192          * the simple ev_q).  Could also do this via explicit functions from the
193          * program. */
194 }
195
196 /* Helper, picks some sane defaults and changes the process into an MCP */
197 void vcore_change_to_m(void)
198 {
199         __procdata.res_req[RES_CORES].amt_wanted = 1;
200         __procdata.res_req[RES_CORES].amt_wanted_min = 1;       /* whatever */
201         assert(!in_multi_mode());
202         assert(!in_vcore_context());
203         assert(!sys_change_to_m());
204         assert(in_multi_mode());
205         assert(!in_vcore_context());
206 }
207
208 /* Returns -1 with errno set on error, or 0 on success.  This does not return
209  * the number of cores actually granted (though some parts of the kernel do
210  * internally).
211  *
212  * This tries to get "more vcores", based on the number we currently have.
213  * We'll probably need smarter 2LSs in the future that just directly set
214  * amt_wanted.  What happens is we can have a bunch of 2LS vcore contexts
215  * trying to get "another vcore", which currently means more than num_vcores().
216  * If you have someone ask for two more, and then someone else ask for one more,
217  * how many you ultimately ask for depends on if the kernel heard you and
218  * adjusted num_vcores in between the two calls.  Or maybe your amt_wanted
219  * already was num_vcores + 5, so neither call is telling the kernel anything
220  * new.  It comes down to "one more than I have" vs "one more than I've already
221  * asked for".
222  *
223  * So for now, this will keep the older behavior (one more than I have).  It
224  * will try to accumulate any concurrent requests, and adjust amt_wanted up.
225  * Interleaving, repetitive calls (everyone asking for one more) may get
226  * ignored.
227  *
228  * Note the doesn't block or anything (despite the min number requested is
229  * 1), since the kernel won't block the call.
230  *
231  * There are a few concurrency concerns.  We have _max_vcores_ever_wanted,
232  * initialization of new vcore stacks/TLSs, making sure we don't ask for too
233  * many (minor point), and most importantly not asking the kernel for too much
234  * or otherwise miscommunicating our desires to the kernel.  Remember, the
235  * kernel wants just one answer from the process about what it wants, and it is
236  * up to the process to figure that out.
237  *
238  * So we basically have one thread do the submitting/prepping/bookkeeping, and
239  * other threads come in just update the number wanted and make sure someone
240  * is sorting things out.  This will perform a bit better too, since only one
241  * vcore makes syscalls (which hammer the proc_lock).  This essentially has
242  * cores submit work, and one core does the work (like Eric's old delta
243  * functions).
244  *
245  * There's a slight semantic change: this will return 0 (success) for the
246  * non-submitters, and 0 if we submitted.  -1 only if the submitter had some
247  * non-kernel failure.
248  *
249  * Also, beware that this (like the old version) doesn't protect with races on
250  * num_vcores().  num_vcores() is how many you have now or very soon (accounting
251  * for messages in flight that will take your cores), not how many you told the
252  * kernel you want. */
253 int vcore_request(long nr_new_vcores)
254 {
255         long nr_to_prep_now, nr_vcores_wanted;
256
257         if (vcore_init() < 0)
258                 return -1;      /* consider ERRNO */
259         /* Early sanity checks */
260         if ((nr_new_vcores < 0) || (nr_new_vcores + num_vcores() > max_vcores()))
261                 return -1;      /* consider ERRNO */
262         /* Post our desires (ROS atomic_add() conflicts with glibc) */
263         atomic_fetch_and_add(&nr_new_vcores_wanted, nr_new_vcores);
264 try_handle_it:
265         cmb();  /* inc before swap.  the atomic is a CPU mb() */
266         if (atomic_swap(&vc_req_being_handled, 1)) {
267                 /* We got a 1 back, so someone else is already working on it */
268                 return 0;
269         }
270         /* So now we're the ones supposed to handle things.  This does things in the
271          * "increment based on the number we have", vs "increment on the number we
272          * said we want".
273          *
274          * Figure out how many we have, though this is racy.  Yields/preempts/grants
275          * will change this over time, and we may end up asking for less than we
276          * had. */
277         nr_vcores_wanted = num_vcores();
278         /* Pull all of the vcores wanted into our local variable, where we'll deal
279          * with prepping/requesting that many vcores.  Keep doing this til we think
280          * no more are wanted. */
281         while ((nr_to_prep_now = atomic_swap(&nr_new_vcores_wanted, 0))) {
282                 nr_vcores_wanted += nr_to_prep_now;
283                 /* Don't bother prepping or asking for more than we can ever get */
284                 nr_vcores_wanted = MIN(nr_vcores_wanted, max_vcores());
285                 /* Make sure all we might ask for are prepped */
286                 for (long i = _max_vcores_ever_wanted; i < nr_vcores_wanted; i++) {
287                         if (allocate_transition_stack(i) || allocate_transition_tls(i)) {
288                                 atomic_set(&vc_req_being_handled, 0);   /* unlock and bail out*/
289                                 return -1;
290                         }
291                         _max_vcores_ever_wanted++;      /* done in the loop to handle failures*/
292                 }
293         }
294         cmb();  /* force a reread of num_vcores() */
295         /* Update amt_wanted if we now want *more* than what the kernel already
296          * knows.  See notes in the func doc. */
297         if (nr_vcores_wanted > __procdata.res_req[RES_CORES].amt_wanted)
298                 __procdata.res_req[RES_CORES].amt_wanted = nr_vcores_wanted;
299         /* If num_vcores isn't what we want, we can poke the ksched.  Due to some
300          * races with yield, our desires may be old.  Not a big deal; any vcores
301          * that pop up will just end up yielding (or get preempt messages.)  */
302         if (nr_vcores_wanted > num_vcores())
303                 sys_poke_ksched(RES_CORES);
304         /* Unlock, (which lets someone else work), and check to see if more work
305          * needs to be done.  If so, we'll make sure it gets handled. */
306         atomic_set(&vc_req_being_handled, 0);   /* unlock, to allow others to try */
307         wrmb();
308         /* check for any that might have come in while we were out */
309         if (atomic_read(&nr_new_vcores_wanted))
310                 goto try_handle_it;
311         return 0;
312 }
313
314 /* This can return, if you failed to yield due to a concurrent event. */
315 void vcore_yield(bool preempt_pending)
316 {
317         uint32_t vcoreid = vcore_id();
318         struct preempt_data *vcpd = vcpd_of(vcoreid);
319         vcpd->can_rcv_msg = FALSE;
320         /* no wrmb() necessary, clear_notif() has an mb() */
321         /* Clears notif pending.  If we had an event outstanding, this will handle
322          * it and return TRUE, at which point we want to unwind and return to the
323          * 2LS loop (where we may not want to yield anymore).  Note that the kernel
324          * only cares about can_rcv_msg for the desired vcore, not for a FALLBACK.
325          * We need to deal with this notif_pending business regardless of
326          * can_rcv_msg.  We just want to avoid a yield syscall if possible.  It is
327          * important that clear_notif_pending will handle_events().  That is
328          * necessary to do/check after setting can_rcv_msg to FALSE. */
329         if (clear_notif_pending(vcoreid)) {
330                 vcpd->can_rcv_msg = TRUE;
331                 return;
332         }
333         /* Tell the kernel we want one less vcore.  If yield fails (slight race), we
334          * may end up having more vcores than amt_wanted for a while, and might lose
335          * one later on (after a preempt/timeslicing) - the 2LS will have to notice
336          * eventually if it actually needs more vcores (which it already needs to
337          * do).  We need to atomically decrement, though I don't want the kernel's
338          * data type here to be atomic_t (only userspace cares in this one case). */
339         __sync_fetch_and_sub(&__procdata.res_req[RES_CORES].amt_wanted, 1);
340         /* We can probably yield.  This may pop back up if notif_pending became set
341          * by the kernel after we cleared it and we lost the race. */
342         sys_yield(preempt_pending);
343         vcpd->can_rcv_msg = TRUE;
344 }
345
346 /* Clear pending, and try to handle events that came in between a previous call
347  * to handle_events() and the clearing of pending.  While it's not a big deal,
348  * we'll loop in case we catch any.  Will break out of this once there are no
349  * events, and we will have send pending to 0. 
350  *
351  * Note that this won't catch every race/case of an incoming event.  Future
352  * events will get caught in pop_ros_tf() or proc_yield().
353  *
354  * Also note that this handles events, which may change your current uthread or
355  * might not return!  Be careful calling this.  Check run_uthread for an example
356  * of how to use this. */
357 bool clear_notif_pending(uint32_t vcoreid)
358 {
359         bool handled_event = FALSE;
360         do {
361                 vcpd_of(vcoreid)->notif_pending = 0;
362                 /* need a full mb(), since handle events might be just a read or might
363                  * be a write, either way, it needs to happen after notif_pending */
364                 mb();
365                 handled_event = handle_events(vcoreid);
366         } while (handled_event);
367         return handled_event;
368 }
369
370 /* Enables notifs, and deals with missed notifs by self notifying.  This should
371  * be rare, so the syscall overhead isn't a big deal.  The other alternative
372  * would be to uthread_yield(), which would require us to revert some uthread
373  * interface changes. */
374 void enable_notifs(uint32_t vcoreid)
375 {
376         __enable_notifs(vcoreid);
377         wrmb(); /* need to read after the write that enabled notifs */
378         /* Note we could get migrated before executing this.  If that happens, our
379          * vcore had gone into vcore context (which is what we wanted), and this
380          * self_notify to our old vcore is spurious and harmless. */
381         if (vcpd_of(vcoreid)->notif_pending)
382                 sys_self_notify(vcoreid, EV_NONE, 0, TRUE);
383 }
384
385 /* Helper to disable notifs.  It simply checks to make sure we disabled uthread
386  * migration, which is a common mistake. */
387 void disable_notifs(uint32_t vcoreid)
388 {
389         if (!in_vcore_context() && current_uthread)
390                 assert(current_uthread->flags & UTHREAD_DONT_MIGRATE);
391         __disable_notifs(vcoreid);
392 }
393
394 /* Like smp_idle(), this will put the core in a state that it can only be woken
395  * up by an IPI.  In the future, we may halt or something. */
396 void __attribute__((noreturn)) vcore_idle(void)
397 {
398         uint32_t vcoreid = vcore_id();
399         clear_notif_pending(vcoreid);
400         enable_notifs(vcoreid);
401         while (1) {
402                 cpu_relax();
403         }
404 }
405
406 /* Helper, that actually makes sure a vcore is running.  Call this is you really
407  * want vcoreid.  More often, you'll want to call the regular version. */
408 static void __ensure_vcore_runs(uint32_t vcoreid)
409 {
410         if (vcore_is_preempted(vcoreid)) {
411                 printd("[vcore]: VC %d changing to VC %d\n", vcore_id(), vcoreid);
412                 /* Note that at this moment, the vcore could still be mapped (we're
413                  * racing with __preempt.  If that happens, we'll just fail the
414                  * sys_change_vcore(), and next time __ensure runs we'll get it. */
415                 /* We want to recover them from preemption.  Since we know they have
416                  * notifs disabled, they will need to be directly restarted, so we can
417                  * skip the other logic and cut straight to the sys_change_vcore() */
418                 sys_change_vcore(vcoreid, FALSE);
419         }
420 }
421
422 /* Helper, looks for any preempted vcores, making sure each of them runs at some
423  * point.  This is pretty heavy-weight, and should be used to help get out of
424  * weird deadlocks (spinning in vcore context, waiting on another vcore).  If
425  * you might know which vcore you are waiting on, use ensure_vc_runs. */
426 static void __ensure_all_run(void)
427 {
428         for (int i = 0; i < max_vcores(); i++)
429                 __ensure_vcore_runs(i);
430 }
431
432 /* Makes sure a vcore is running.  If it is preempted, we'll switch to
433  * it.  This will return, either immediately if the vcore is running, or later
434  * when someone preempt-recovers us.
435  *
436  * If you pass in your own vcoreid, this will make sure all other preempted
437  * vcores run. */
438 void ensure_vcore_runs(uint32_t vcoreid)
439 {
440         /* if the vcoreid is ourselves, make sure everyone else is running */
441         if (vcoreid == vcore_id()) {
442                 __ensure_all_run();
443                 return;
444         }
445         __ensure_vcore_runs(vcoreid);
446 }
447
448 #define NR_RELAX_SPINS 1000
449 /* If you are spinning in vcore context and it is likely that you don't know who
450  * you are waiting on, call this.  It will spin for a bit before firing up the
451  * potentially expensive __ensure_all_run().  Don't call this from uthread
452  * context.  sys_change_vcore will probably mess you up. */
453 void cpu_relax_vc(uint32_t vcoreid)
454 {
455         static __thread unsigned int spun;              /* vcore TLS */
456         assert(in_vcore_context());
457         spun = 0;
458         if (spun++ >= NR_RELAX_SPINS) {
459                 /* if vcoreid == vcore_id(), this might be expensive */
460                 ensure_vcore_runs(vcoreid);
461                 spun = 0;
462         }
463         cpu_relax();
464 }