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