680aee208a4ece22faeaa095d4595e5735f1c57d
[akaros.git] / user / parlib / vcore.c
1 #include <parlib/arch/arch.h>
2 #include <stdbool.h>
3 #include <errno.h>
4 #include <parlib/vcore.h>
5 #include <parlib/mcs.h>
6 #include <sys/param.h>
7 #include <parlib/parlib.h>
8 #include <unistd.h>
9 #include <stdlib.h>
10 #include <sys/mman.h>
11 #include <stdio.h>
12 #include <parlib/event.h>
13 #include <parlib/uthread.h>
14 #include <parlib/ucq.h>
15 #include <ros/arch/membar.h>
16 #include <parlib/printf-ext.h>
17
18 __thread int __vcoreid = 0;
19 __thread bool __vcore_context = FALSE;
20
21 /* starting with 1 since we alloc vcore0's stacks and TLS in vcore_lib_init(). */
22 static size_t _max_vcores_ever_wanted = 1;
23 atomic_t nr_new_vcores_wanted;
24 atomic_t vc_req_being_handled;
25
26 __thread struct syscall __vcore_one_sysc = {.flags = (atomic_t)SC_DONE, 0};
27
28 /* Per vcore entery function used when reentering at the top of a vcore's stack */
29 static __thread void (*__vcore_reentry_func)(void) = NULL;
30
31 /* The default user vcore_entry function. */
32 void __attribute__((noreturn)) __vcore_entry(void)
33 {
34         extern void uthread_vcore_entry(void);
35         uthread_vcore_entry();
36         fprintf(stderr, "vcore_entry() should never return!\n");
37         abort();
38         __builtin_unreachable();
39 }
40 void vcore_entry(void) __attribute__((weak, alias ("__vcore_entry")));
41
42 /* The lowest level function jumped to by the kernel on every vcore_entry.
43  * Currently, this function is only necessary so we can set the tls_desc from
44  * the vcpd for non x86_64 architectures. We should consider removing this and
45  * making it mandatory to set the tls_desc in the kernel. We wouldn't even
46  * need to pass the vcore id to user space at all if we did this.  It would
47  * already be set in the preinstalled TLS as __vcore_id. */
48 static void __attribute__((noreturn)) __kernel_vcore_entry(void)
49 {
50         /* The kernel sets the TLS desc for us, based on whatever is in VCPD.
51          *
52          * x86 32-bit TLS is pretty jacked up, so the kernel doesn't set the TLS
53          * desc for us.  it's a little more expensive to do it here, esp for
54          * amd64.  Can remove this when/if we overhaul 32 bit TLS.
55          *
56          * AFAIK, riscv's TLS changes are really cheap, and they don't do it in
57          * the kernel (yet/ever), so they can set their TLS here too. */
58         int id = __vcore_id_on_entry;
59         #ifndef __x86_64__
60         set_tls_desc(vcpd_of(id)->vcore_tls_desc);
61         #endif
62         /* Every time the vcore comes up, it must set that it is in vcore context.
63          * uthreads may share the same TLS as their vcore (when uthreads do not have
64          * their own TLS), and if a uthread was preempted, __vcore_context == FALSE,
65          * and that will continue to be true the next time the vcore pops up. */
66         __vcore_context = TRUE;
67         vcore_entry();
68         fprintf(stderr, "vcore_entry() should never return!\n");
69         abort();
70         __builtin_unreachable();
71 }
72
73 /* TODO: probably don't want to dealloc.  Considering caching */
74 static void free_transition_tls(int id)
75 {
76         if (get_vcpd_tls_desc(id)) {
77                 /* Note we briefly have no TLS desc in VCPD.  This is fine so long as
78                  * that vcore doesn't get started fresh before we put in a new desc */
79                 free_tls(get_vcpd_tls_desc(id));
80                 set_vcpd_tls_desc(id, NULL);
81         }
82 }
83
84 static int allocate_transition_tls(int id)
85 {
86         /* Libc function to initialize TLS-based locale info for ctype functions. */
87         extern void __ctype_init(void);
88
89         /* We want to free and then reallocate the tls rather than simply 
90          * reinitializing it because its size may have changed.  TODO: not sure if
91          * this is right.  0-ing is one thing, but freeing and reallocating can be
92          * expensive, esp if syscalls are involved.  Check out glibc's
93          * allocatestack.c for what might work. */
94         free_transition_tls(id);
95
96         void *tcb = allocate_tls();
97         if (!tcb) {
98                 errno = ENOMEM;
99                 return -1;
100         }
101
102         /* Setup some intitial TLS data for the newly allocated transition tls. */
103         void *temp_tcb = get_tls_desc();
104         set_tls_desc(tcb);
105         begin_safe_access_tls_vars();
106         __vcoreid = id;
107         __vcore_context = TRUE;
108         __ctype_init();
109         end_safe_access_tls_vars();
110         set_tls_desc(temp_tcb);
111
112         /* Install the new tls into the vcpd. */
113         set_vcpd_tls_desc(id, tcb);
114         return 0;
115 }
116
117 static void free_vcore_stack(int id)
118 {
119         // don't actually free stacks
120 }
121
122 static int allocate_vcore_stack(int id)
123 {
124         struct preempt_data *vcpd = vcpd_of(id);
125         if (vcpd->vcore_stack)
126                 return 0; // reuse old stack
127
128         void* stackbot = mmap(0, TRANSITION_STACK_SIZE,
129                               PROT_READ|PROT_WRITE|PROT_EXEC,
130                               MAP_POPULATE|MAP_ANONYMOUS, -1, 0);
131
132         if(stackbot == MAP_FAILED)
133                 return -1; // errno set by mmap
134
135         vcpd->vcore_stack = (uintptr_t)stackbot + TRANSITION_STACK_SIZE;
136
137         return 0;
138 }
139
140 /* Run libc specific early setup code. */
141 static void vcore_libc_init(void)
142 {
143         register_printf_specifier('r', printf_errstr, printf_errstr_info);
144         /* TODO: register for other kevents/signals and whatnot (can probably reuse
145          * the simple ev_q).  Could also do this via explicit functions from the
146          * program. */
147 }
148
149 void __attribute__((constructor)) vcore_lib_init(void)
150 {
151         uintptr_t mmap_block;
152
153         /* Note this is racy, but okay.  The first time through, we are _S.
154          * Also, this is the "lowest" level constructor for now, so we don't need
155          * to call any other init functions after our run_once() call. This may
156          * change in the future. */
157         init_once_racy(return);
158
159         /* Need to alloc vcore0's transition stuff here (technically, just the TLS)
160          * so that schedulers can use vcore0's transition TLS before it comes up in
161          * vcore_entry() */
162         if (allocate_vcore_stack(0) || allocate_transition_tls(0))
163                 goto vcore_lib_init_fail;
164
165         /* Initialize our VCPD event queues' ucqs, two pages per ucq, 4 per vcore */
166         mmap_block = (uintptr_t)mmap(0, PGSIZE * 4 * max_vcores(),
167                                      PROT_WRITE | PROT_READ,
168                                      MAP_POPULATE | MAP_ANONYMOUS, -1, 0);
169         /* Yeah, this doesn't fit in the error-handling scheme, but this whole
170          * system doesn't really handle failure, and needs a rewrite involving less
171          * mmaps/munmaps. */
172         assert(mmap_block);
173         /* Note we may end up doing vcore 0's elsewhere, for _Ss, or else have a
174          * separate ev_q for that. */
175         for (int i = 0; i < max_vcores(); i++) {
176                 /* four pages total for both ucqs from the big block (2 pages each) */
177                 vcpd_of(i)->ev_mbox_public.type = EV_MBOX_UCQ;
178                 ucq_init_raw(&vcpd_of(i)->ev_mbox_public.ucq,
179                              mmap_block + (4 * i    ) * PGSIZE,
180                              mmap_block + (4 * i + 1) * PGSIZE);
181                 vcpd_of(i)->ev_mbox_private.type = EV_MBOX_UCQ;
182                 ucq_init_raw(&vcpd_of(i)->ev_mbox_private.ucq,
183                              mmap_block + (4 * i + 2) * PGSIZE,
184                              mmap_block + (4 * i + 3) * PGSIZE);
185                 /* Set the lowest level entry point for each vcore. */
186                 vcpd_of(i)->vcore_entry = (uintptr_t)__kernel_vcore_entry;
187         }
188         atomic_init(&vc_req_being_handled, 0);
189         assert(!in_vcore_context());
190         vcore_libc_init();
191         return;
192 vcore_lib_init_fail:
193         assert(0);
194 }
195
196 /* Helper functions used to reenter at the top of a vcore's stack for an
197  * arbitrary function */
198 static void __attribute__((noinline, noreturn)) 
199 __vcore_reenter()
200 {
201   __vcore_reentry_func();
202   assert(0);
203 }
204
205 void vcore_reenter(void (*entry_func)(void))
206 {
207   assert(in_vcore_context());
208   struct preempt_data *vcpd = vcpd_of(vcore_id());
209
210   __vcore_reentry_func = entry_func;
211   set_stack_pointer((void*)vcpd->vcore_stack);
212   cmb();
213   __vcore_reenter();
214 }
215
216 /* Helper, picks some sane defaults and changes the process into an MCP */
217 void vcore_change_to_m(void)
218 {
219         int ret;
220         __procdata.res_req[RES_CORES].amt_wanted = 1;
221         __procdata.res_req[RES_CORES].amt_wanted_min = 1;       /* whatever */
222         assert(!in_multi_mode());
223         assert(!in_vcore_context());
224         ret = sys_change_to_m();
225         assert(!ret);
226         assert(in_multi_mode());
227         assert(!in_vcore_context());
228 }
229
230 /* Returns -1 with errno set on error, or 0 on success.  This does not return
231  * the number of cores actually granted (though some parts of the kernel do
232  * internally).
233  *
234  * This tries to get "more vcores", based on the number we currently have.
235  * We'll probably need smarter 2LSs in the future that just directly set
236  * amt_wanted.  What happens is we can have a bunch of 2LS vcore contexts
237  * trying to get "another vcore", which currently means more than num_vcores().
238  * If you have someone ask for two more, and then someone else ask for one more,
239  * how many you ultimately ask for depends on if the kernel heard you and
240  * adjusted num_vcores in between the two calls.  Or maybe your amt_wanted
241  * already was num_vcores + 5, so neither call is telling the kernel anything
242  * new.  It comes down to "one more than I have" vs "one more than I've already
243  * asked for".
244  *
245  * So for now, this will keep the older behavior (one more than I have).  It
246  * will try to accumulate any concurrent requests, and adjust amt_wanted up.
247  * Interleaving, repetitive calls (everyone asking for one more) may get
248  * ignored.
249  *
250  * Note the doesn't block or anything (despite the min number requested is
251  * 1), since the kernel won't block the call.
252  *
253  * There are a few concurrency concerns.  We have _max_vcores_ever_wanted,
254  * initialization of new vcore stacks/TLSs, making sure we don't ask for too
255  * many (minor point), and most importantly not asking the kernel for too much
256  * or otherwise miscommunicating our desires to the kernel.  Remember, the
257  * kernel wants just one answer from the process about what it wants, and it is
258  * up to the process to figure that out.
259  *
260  * So we basically have one thread do the submitting/prepping/bookkeeping, and
261  * other threads come in just update the number wanted and make sure someone
262  * is sorting things out.  This will perform a bit better too, since only one
263  * vcore makes syscalls (which hammer the proc_lock).  This essentially has
264  * cores submit work, and one core does the work (like Eric's old delta
265  * functions).
266  *
267  * There's a slight semantic change: this will return 0 (success) for the
268  * non-submitters, and 0 if we submitted.  -1 only if the submitter had some
269  * non-kernel failure.
270  *
271  * Also, beware that this (like the old version) doesn't protect with races on
272  * num_vcores().  num_vcores() is how many you have now or very soon (accounting
273  * for messages in flight that will take your cores), not how many you told the
274  * kernel you want. */
275 int vcore_request(long nr_new_vcores)
276 {
277         long nr_to_prep_now, nr_vcores_wanted;
278
279         /* Early sanity checks */
280         if ((nr_new_vcores < 0) || (nr_new_vcores + num_vcores() > max_vcores()))
281                 return -1;      /* consider ERRNO */
282         /* Post our desires (ROS atomic_add() conflicts with glibc) */
283         atomic_fetch_and_add(&nr_new_vcores_wanted, nr_new_vcores);
284 try_handle_it:
285         cmb();  /* inc before swap.  the atomic is a CPU mb() */
286         if (atomic_swap(&vc_req_being_handled, 1)) {
287                 /* We got a 1 back, so someone else is already working on it */
288                 return 0;
289         }
290         /* So now we're the ones supposed to handle things.  This does things in the
291          * "increment based on the number we have", vs "increment on the number we
292          * said we want".
293          *
294          * Figure out how many we have, though this is racy.  Yields/preempts/grants
295          * will change this over time, and we may end up asking for less than we
296          * had. */
297         nr_vcores_wanted = num_vcores();
298         /* Pull all of the vcores wanted into our local variable, where we'll deal
299          * with prepping/requesting that many vcores.  Keep doing this til we think
300          * no more are wanted. */
301         while ((nr_to_prep_now = atomic_swap(&nr_new_vcores_wanted, 0))) {
302                 nr_vcores_wanted += nr_to_prep_now;
303                 /* Don't bother prepping or asking for more than we can ever get */
304                 nr_vcores_wanted = MIN(nr_vcores_wanted, max_vcores());
305                 /* Make sure all we might ask for are prepped */
306                 for (long i = _max_vcores_ever_wanted; i < nr_vcores_wanted; i++) {
307                         if (allocate_vcore_stack(i) || allocate_transition_tls(i)) {
308                                 atomic_set(&vc_req_being_handled, 0);   /* unlock and bail out*/
309                                 return -1;
310                         }
311                         _max_vcores_ever_wanted++;      /* done in the loop to handle failures*/
312                 }
313         }
314         cmb();  /* force a reread of num_vcores() */
315         /* Update amt_wanted if we now want *more* than what the kernel already
316          * knows.  See notes in the func doc. */
317         if (nr_vcores_wanted > __procdata.res_req[RES_CORES].amt_wanted)
318                 __procdata.res_req[RES_CORES].amt_wanted = nr_vcores_wanted;
319         /* If num_vcores isn't what we want, we can poke the ksched.  Due to some
320          * races with yield, our desires may be old.  Not a big deal; any vcores
321          * that pop up will just end up yielding (or get preempt messages.)  */
322         if (nr_vcores_wanted > num_vcores())
323                 sys_poke_ksched(0, RES_CORES);  /* 0 -> poke for ourselves */
324         /* Unlock, (which lets someone else work), and check to see if more work
325          * needs to be done.  If so, we'll make sure it gets handled. */
326         atomic_set(&vc_req_being_handled, 0);   /* unlock, to allow others to try */
327         wrmb();
328         /* check for any that might have come in while we were out */
329         if (atomic_read(&nr_new_vcores_wanted))
330                 goto try_handle_it;
331         return 0;
332 }
333
334 /* This can return, if you failed to yield due to a concurrent event.  Note
335  * we're atomicly setting the CAN_RCV flag, and aren't bothering with CASing
336  * (either with the kernel or uthread's handle_indirs()).  We don't particularly
337  * care what other code does - we intend to set those flags no matter what. */
338 void vcore_yield(bool preempt_pending)
339 {
340         unsigned long old_nr;
341         uint32_t vcoreid = vcore_id();
342         struct preempt_data *vcpd = vcpd_of(vcoreid);
343         __sync_fetch_and_and(&vcpd->flags, ~VC_CAN_RCV_MSG);
344         /* no wrmb() necessary, handle_events() has an mb() if it is checking */
345         /* Clears notif pending and tries to handle events.  This is an optimization
346          * to avoid the yield syscall if we have an event pending.  If there is one,
347          * we want to unwind and return to the 2LS loop, where we may not want to
348          * yield anymore.
349          * Note that the kernel only cares about CAN_RCV_MSG for the desired vcore;
350          * when spamming, it relies on membership of lists within the kernel.  Look
351          * at spam_list_member() for more info (k/s/event.c). */
352         if (handle_events(vcoreid)) {
353                 __sync_fetch_and_or(&vcpd->flags, VC_CAN_RCV_MSG);
354                 return;
355         }
356         /* If we are yielding since we don't want the core, tell the kernel we want
357          * one less vcore (vc_yield assumes a dumb 2LS).
358          *
359          * If yield fails (slight race), we may end up having more vcores than
360          * amt_wanted for a while, and might lose one later on (after a
361          * preempt/timeslicing) - the 2LS will have to notice eventually if it
362          * actually needs more vcores (which it already needs to do).  amt_wanted
363          * could even be 0.
364          *
365          * In general, any time userspace decrements or sets to 0, it could get
366          * preempted, so the kernel will still give us at least one, until the last
367          * vcore properly yields without missing a message (and becomes a WAITING
368          * proc, which the ksched will not give cores to).
369          *
370          * I think it's possible for userspace to do this (lock, read amt_wanted,
371          * check all message queues for all vcores, subtract amt_wanted (not set to
372          * 0), unlock) so long as every event handler +1s the amt wanted, but that's
373          * a huge pain, and we already have event handling code making sure a
374          * process can't sleep (transition to WAITING) if a message arrives (can't
375          * yield if notif_pending, can't go WAITING without yielding, and the event
376          * posting the notif_pending will find the online VC or be delayed by
377          * spinlock til the proc is WAITING). */
378         if (!preempt_pending) {
379                 do {
380                         old_nr = __procdata.res_req[RES_CORES].amt_wanted;
381                         if (old_nr == 0)
382                                 break;
383                 } while (!__sync_bool_compare_and_swap(
384                              &__procdata.res_req[RES_CORES].amt_wanted,
385                              old_nr, old_nr - 1));
386         }
387         /* We can probably yield.  This may pop back up if notif_pending became set
388          * by the kernel after we cleared it and we lost the race. */
389         sys_yield(preempt_pending);
390         __sync_fetch_and_or(&vcpd->flags, VC_CAN_RCV_MSG);
391 }
392
393 /* Enables notifs, and deals with missed notifs by self notifying.  This should
394  * be rare, so the syscall overhead isn't a big deal.  The other alternative
395  * would be to uthread_yield(), which would require us to revert some uthread
396  * interface changes. */
397 void enable_notifs(uint32_t vcoreid)
398 {
399         __enable_notifs(vcoreid);
400         wrmb(); /* need to read after the write that enabled notifs */
401         /* Note we could get migrated before executing this.  If that happens, our
402          * vcore had gone into vcore context (which is what we wanted), and this
403          * self_notify to our old vcore is spurious and harmless. */
404         if (vcpd_of(vcoreid)->notif_pending)
405                 sys_self_notify(vcoreid, EV_NONE, 0, TRUE);
406 }
407
408 /* Helper to disable notifs.  It simply checks to make sure we disabled uthread
409  * migration, which is a common mistake. */
410 void disable_notifs(uint32_t vcoreid)
411 {
412         if (!in_vcore_context() && current_uthread)
413                 assert(current_uthread->flags & UTHREAD_DONT_MIGRATE);
414         __disable_notifs(vcoreid);
415 }
416
417 /* Like smp_idle(), this will put the core in a state that it can only be woken
418  * up by an IPI.  For now, this is a halt.  Maybe an mwait in the future.
419  *
420  * This will return if an event was pending (could be the one you were waiting
421  * for) or if the halt failed for some reason, such as a concurrent RKM.  If
422  * successful, this will not return at all, and the vcore will restart from the
423  * top next time it wakes.  Any sort of IRQ will wake the core.
424  *
425  * Alternatively, I might make this so it never returns, if that's easier to
426  * work with (similar issues with yield). */
427 void vcore_idle(void)
428 {
429         uint32_t vcoreid = vcore_id();
430         /* Once we enable notifs, the calling context will be treated like a uthread
431          * (saved into the uth slot).  We don't want to ever run it again, so we
432          * need to make sure there's no cur_uth. */
433         assert(!current_uthread);
434         /* This clears notif_pending (check, signal, check again pattern). */
435         if (handle_events(vcoreid))
436                 return;
437         /* This enables notifs, but also checks notif pending.  At this point, any
438          * new notifs will restart the vcore from the top. */
439         enable_notifs(vcoreid);
440         /* From now, til we get into the kernel, any notifs will permanently destroy
441          * this context and start the VC from the top.
442          *
443          * Once we're in the kernel, any messages (__notify, __preempt), will be
444          * RKMs.  halt will need to check for those atomically.  Checking for
445          * notif_pending in the kernel (sleep only if not set) is not enough, since
446          * not all reasons for the kernel to stay awak set notif_pending (e.g.,
447          * __preempts and __death).
448          *
449          * At this point, we're out of VC ctx, so anyone who sets notif_pending
450          * should also send an IPI / __notify */
451         sys_halt_core(0);
452         /* in case halt returns without actually restarting the VC ctx. */
453         disable_notifs(vcoreid);
454 }
455
456 /* Helper, that actually makes sure a vcore is running.  Call this is you really
457  * want vcoreid.  More often, you'll want to call the regular version. */
458 static void __ensure_vcore_runs(uint32_t vcoreid)
459 {
460         if (vcore_is_preempted(vcoreid)) {
461                 printd("[vcore]: VC %d changing to VC %d\n", vcore_id(), vcoreid);
462                 /* Note that at this moment, the vcore could still be mapped (we're
463                  * racing with __preempt.  If that happens, we'll just fail the
464                  * sys_change_vcore(), and next time __ensure runs we'll get it. */
465                 /* We want to recover them from preemption.  Since we know they have
466                  * notifs disabled, they will need to be directly restarted, so we can
467                  * skip the other logic and cut straight to the sys_change_vcore() */
468                 sys_change_vcore(vcoreid, FALSE);
469         }
470 }
471
472 /* Helper, looks for any preempted vcores, making sure each of them runs at some
473  * point.  This is pretty heavy-weight, and should be used to help get out of
474  * weird deadlocks (spinning in vcore context, waiting on another vcore).  If
475  * you might know which vcore you are waiting on, use ensure_vc_runs. */
476 static void __ensure_all_run(void)
477 {
478         for (int i = 0; i < max_vcores(); i++)
479                 __ensure_vcore_runs(i);
480 }
481
482 /* Makes sure a vcore is running.  If it is preempted, we'll switch to
483  * it.  This will return, either immediately if the vcore is running, or later
484  * when someone preempt-recovers us.
485  *
486  * If you pass in your own vcoreid, this will make sure all other preempted
487  * vcores run. */
488 void ensure_vcore_runs(uint32_t vcoreid)
489 {
490         /* if the vcoreid is ourselves, make sure everyone else is running */
491         if (vcoreid == vcore_id()) {
492                 __ensure_all_run();
493                 return;
494         }
495         __ensure_vcore_runs(vcoreid);
496 }
497
498 #define NR_RELAX_SPINS 1000
499 /* If you are spinning in vcore context and it is likely that you don't know who
500  * you are waiting on, call this.  It will spin for a bit before firing up the
501  * potentially expensive __ensure_all_run().  Don't call this from uthread
502  * context.  sys_change_vcore will probably mess you up. */
503 void cpu_relax_vc(uint32_t vcoreid)
504 {
505         static __thread unsigned int __vc_relax_spun = 0;
506         assert(in_vcore_context());
507         if (__vc_relax_spun++ >= NR_RELAX_SPINS) {
508                 /* if vcoreid == vcore_id(), this might be expensive */
509                 ensure_vcore_runs(vcoreid);
510                 __vc_relax_spun = 0;
511         }
512         cpu_relax();
513 }
514
515 /* Check with the kernel to determine what vcore we are.  Normally, you should
516  * never call this, since your vcoreid is stored in your TLS.  Also, if you call
517  * it from a uthread, you could get migrated, so you should drop into some form
518  * of vcore context (DONT_MIGRATE on) */
519 uint32_t get_vcoreid(void)
520 {
521         if (!in_vcore_context()) {
522                 assert(current_uthread);
523                 assert(current_uthread->flags & UTHREAD_DONT_MIGRATE);
524         }
525         return __get_vcoreid();
526 }
527
528 /* Debugging helper.  Pass in the string you want printed if your vcoreid is
529  * wrong, and pass in what vcoreid you think you are.  Don't call from uthread
530  * context unless migrations are disabled.  Will print some stuff and return
531  * FALSE if you were wrong. */
532 bool check_vcoreid(const char *str, uint32_t vcoreid)
533 {
534         uint32_t kvcoreid = get_vcoreid();
535         if (vcoreid != kvcoreid) {
536                 ros_debug("%s: VC %d thought it was VC %d\n", str, kvcoreid, vcoreid);
537                 return FALSE;
538         }
539         return TRUE;
540 }