Public VCPD mboxes (XCC)
[akaros.git] / Documentation / async_events.txt
1 async_events.txt
2 Barret Rhoden
3
4 1. Overview
5 2. Async Syscalls and I/O
6 3. Event Delivery / Notification
7 4. Misc Things That Aren't Sorted Completely:
8
9 1. Overview
10 ====================
11 1.1 Event Handling / Notifications / Async IO Issues:
12 ------------------------------------------------------------------
13 Basically, syscalls use the ROS event delivery mechanisms, redefined and
14 described below.  Syscalls use the event delivery just like any other
15 subsystem would that wants to deliver messages to a process.  The only other
16 example we have right now are the "kernel notifications", which are the
17 one-sided, kernel-initiated messages that the kernel sends to a process.
18
19 Overall, there are several analogies from how vcores work to how the OS
20 handles interrupts.  This is a result of trying to make vcores run like
21 virtual multiprocessors, in control of their resources and aware of the lower
22 levels of the system.  This analogy has guided much of how the vcore layer
23 works.  Whenever we have issues with the 2-lsched, realize the amount of
24 control they want means using solutions that the OS must do too.
25
26 Note that there is some pointer chasing going on, though we try to keep it to
27 a minimum.  Any time the kernel chases a pointer, it needs to make sure it is
28 in the R/W section of userspace, though it doesn't need to check if the page
29 is present.  There's more info in the Page Fault sections of the
30 documentation.  (Briefly, if the kernel PFs on a user address, it will either
31 block and handle the PF, or if the address was unmapped, it will kill the
32 process).
33
34 1.2 Some Definitions:
35 ---------------------------------------
36 ev_q, event_queue, event_q: all terms used interchangeably with each other.
37 They are the endpoint for communicating messages to a process, encapsulating
38 the method of delivery (such as IPI or not) with where to save the message.
39
40 Vcore context: the execution context of the virtual core on the "trampoline"
41 stack.  All executions start from the top of this stack, and no stack state is
42 saved between vcore_entry() calls.  All executions on here are non-blocking,
43 notifications (IPIs) are disabled, and there is a specific TLS loaded.  Vcore
44 context is used for running the second level scheduler (2LS), swapping between
45 threads, and handling notifications.  It is analagous to "interrupt context"
46 in the OS.  Any functions called from here should be brief.  Any memory
47 touched must be pinned.  In Lithe terms, vcore context might be called the
48 Hart / hard thread.  People often wonder if they can run out of vcore context
49 directly.  Technically, you can, but you lose the ability to take any fault
50 (page fault) or to get IPIs for notification.  In essence, you lose control,
51 analgous to running an application in the kernel with preemption/interrupts
52 disabled.  See the process documentation for more info.
53
54 2LS: is the second level scheduler/framework.  This code executes in vcore
55 context, and is Lithe / plugs in to Lithe (eventually).  Often used
56 interchangeably with "vcore context", usually when I want to emphasize the
57 scheduling nature of the code.
58
59 VCPD: "virtual core preemption data".  In procdata, there is an array of
60 struct preempt_data, one per vcore.  This is the default location to look for
61 all things related to the management of vcores, such as its event_mbox (queue
62 of incoming messages/notifications/events).  Both the kernel and the vcore
63 code know to look here for a variety of things.
64
65 Vcore-business: This is a term I use for a class of messages where the receiver
66 is the actual vcore, and not just using the vcore as a place to receive the
67 message.  Examples of vcore-business are INDIR events, preempt_pending events,
68 scheduling events (self-ipis by the 2LS from one vcore to another), and things
69 like that.  There are two types: public and private.  Private will only be
70 handled by that vcore.  Public might be handled by another vcore.
71
72 Notif_table: This is a list of event_q*s that correspond to certain
73 unexpected/"one-sided" events the kernel sends to the process.  It is similar
74 to an IRQ table in the kernel.  Each event_q tells the kernel how the process
75 wants to be told about the specific event type.
76
77 Notifications: used to be a generic event, but now used in terms of the verb
78 'notify' (do_notify()).  In older docs, passive notification is just writing a
79 message somewhere.  Active notification is an IPI delivered to a vcore.  I use
80 that term interchangeably with an IPI, and usually you can tell by context
81 that I'm talking about an IPI going to a process (and not just the kernel).
82 The details of it make it more complicated than just an IPI, but it's
83 analagous.  I've start referring to notification as the IPI, and "passive
84 notification" as just events, though older documentation has both meanings.
85
86 BCQ: "bounded concurrent queue".  It is a fixed size array of messages
87 (structs of notification events, or whatever).  It is non-blocking, supporting
88 multiple producers and consumers, where the producers do not trust the
89 consumers.  It is the primary mechanism for the kernel delivering message
90 payloads into a process's address space.  Note that producers don't trust each
91 other either (in the event of weirdness, the producers give up and say the
92 buffer is full).  This means that a process can produce for one of its ev_qs
93 (which is what they need to do to send message to itself).
94
95 UCQ: "unbounded concurrent queue".  This is a data structure allowing the kernel
96 to produce an unbounded number of messages for the process to consume.  The main
97 limitation to the number of messages is RAM.  Check out its documentation.
98
99 2. Async Syscalls and I/O
100 ====================
101 2.1 Basics
102 ----------------------------------------------
103 The syscall struct is the contract for work with the kernel, including async
104 I/O.  Lots of current OS async packages use epoll or other polling systems.
105 Note the distinction between Polling and Async I/O.  Polling is about finding
106 out if a call will block.  It is primarily used for sockets and pipes.  It
107 does relatively nothing for disk I/O, which requires a separate async I/O
108 system.  By having all syscalls be async, we can make polling a bit easier and
109 more unified with the generic event code that we use for all syscalls.
110
111 For instance, we can have a sys_poll syscall, which is async just like any
112 other syscall.  The call can be a "one shot / non-blocking", like the current
113 systems polling code, or it can also notify on change (not requiring future
114 polls) via the event_q mechanisms.  If you don't want to be IPId, you can
115 "poll" the syscall struct - not requiring another kernel crossing/syscall.
116
117 Note that we do not tie syscalls and polling to FDs.  We do events on
118 syscalls, which can be used to check FDs.  I think a bunch of polling cases
119 will not be needed once we have async syscalls, but for those that remain,
120 we'll have sys_poll() (or whatever).
121
122 To receive an event on a syscall completion or status change, just fill in the
123 event_q pointer.  If it is 0, the kernel will assume you poll the actual
124 syscall struct.
125
126         struct syscall {
127                 current stuff                   /* arguments, retvals */
128                 struct ev_queue *               /* struct used for messaging, including IPIs*/
129                 void *                                  /* used by 2LS, usually a struct u_thread * */
130         }
131
132 One issue with async syscalls is that there can be too many outstanding IOs
133 (normally sync calls provide feedback / don't allow you to over-request).
134 Eventually, processes can exhaust kernel memory (the kthreads, specifically).
135 We need a way to limit the kthreads per proc, etc.  Shouldn't be a big deal.
136
137 Normally, we talk about changing the flag in a syscall to SC_DONE.  Async
138 syscalls can be SC_PROGRESS (new stuff happened on it), which can trigger a
139 notification event.  Some calls, like AIO or bulk accept, exist for a while
140 and slowly get filled in / completed.  In the future, we'll also want a way to
141 abort the in-progress syscalls (possibly any syscall!).
142
143 2.2 Uthreads Blocking on Syscalls
144 ----------------------------------------------
145 Many threading libraries will want some notion of a synchronous, blocking
146 thread.  These threads use regular I/O calls, which are async under the hood,
147 but don't want to bother with call backs or other details of async I/O.  In
148 this section, I'll talk a bit about how this works, esp regarding
149 uthreads/pthreads.
150
151 'Blocking' refers to user threads, and has nothing to do with an actual
152 process blocking/waiting on some kernel event.  The kernel does not know
153 anything about what goes on here.  While a bit confusing, this allows
154 applications to do whatever they want on top of an async interface, and is a
155 consequence of decoupling cores from user-threads from kthreads.
156
157 2.2.1 Basics of Uthread Blocking
158 ---------------
159 When a thread calls a glibc function that makes a system call, if the syscall
160 is not yet complete when the kernel returns to userspace, glibc will check for
161 the existence of a second level scheduler and attempt to use it to yield its
162 uthread.  If there is no 2LS, the code just spins for now.  Eventually, it
163 will try to suspend/yield the process for a while (til the call is done), aka,
164 block in the kernel.
165
166 If there is a 2LS, the current thread will yield, and call out to the 2LS's
167 blockon_sysc() method, which needs a way to stop the thread and be able to
168 restart it when the syscall completes.  Specifically, the pthread 2LS registers
169 the syscall to respond to an event (described in detail elsewhere in this doc).
170 When the event comes in, meaning the syscall is complete, the thread is put on
171 the runnable list.
172
173 Details:
174 - A pointer to the struct pthread is stored in the syscall's void*.  When the
175   syscall is done, we normally get a message from the kernel, and the payload
176   tells us the syscall is done, which tells us which thread to unblock. 
177 - The pthread code also always asks for an IPI and event message for every
178   syscall that completes.  This is far from ideal.  Still, the basics are the
179   same for any threading library.  Once you know a thread is done, you need to
180   do something about it.
181 - The pthread code does syscall blocking and event notification on a per-core
182   basis.  Using the default (VCPD) ev_mbox for this is a bad idea (which we did
183   at some point).
184 - There's a race between the 2LS trying to sign up for events and the kernel
185   finishing the event.  We handle this in uthread code, so use the helper to
186   register_evq(), which does the the right thing (atomics, careful ordering
187   with writes, etc).
188
189 2.2.1 Recovering from Event Overflow
190 ---------------
191 Event overflow recovery is unnecessary, since syscall ev_qs use UCQs now.  this
192 section is kept around for some useful tidbits, such as details about
193 deregistering ev_qs for a syscall:
194
195 ---------------------------
196 The pthread code expects to receive an event somehow to unblock a thread
197 once its syscall is done.  One limitation to our messaging systems is that you
198 can't send an infinite amount of event messages.  (By messages, I mean a chunk
199 of memory with a payload, in this case consisting of a struct syscall *).
200 Event delivery degrades to a bit in the case of the message queue being full
201 (more details on that later).
202
203 The pthread code (and any similar 2LS) needs to handle waking up syscalls when
204 the event message was lost and all we know is that some syscall that was meant
205 to have a message sent to a particular event queue (per-core in the case of
206 pthread stuff (actually the VCPD for now)).  The basic idea is to poll all
207 outstanding system calls and unblock whoever is done.
208
209 The key problem is due to a race: for a given syscall we don't know if we're
210 going to get a message for a syscall or not.  There could be a completion
211 message in the queue for the syscall while we are going through the list of
212 blocked threads.  If we assume we already got the message (or it was lost in
213 the overflow), but didn't really, then if we finish as SC and free its memory
214 (free or return up the stack), we could later get a message for it, and all
215 sorts of things would go wrong (like trying to unblock a pointer that is
216 gibberish).
217
218 Here's what we do:
219 1) Set a "handling overflow" flag so we don't recurse.
220 2) Turn off event delivery for all syscalls on our list
221 3) Handle any event messages.  This is how we make a distinction between
222 finished syscalls that had a message sent and those that didn't.  We're doing
223 the message-sent ones here.
224 4) For any left on the list, check to see if they are done.  We actually do
225 this by attempting to turn on event delivery for them.  Turning on event
226 delivery can fail if the call is already done.  So if it fails, they are done
227 and we unblock them (similar to how we block the threads in the first place).
228 If it doesn't fail, they are now ready to receive messages.  This can be
229 tweaked a bit.
230 5) Unset the overflow-handling flag.
231
232 One thing to be careful of is that when we turn off event delivery, you need to
233 be sure the kernel isn't in the process of sending an event.  This is why we
234 have the SC_K_LOCK syscall flag.  Uthread code will not consider deregistration
235 complete while that flag is set, since the kernel is still mucking with the
236 syscall (and sending an event).  Once the flag is clear, the event has been
237 delivered (the ev_msg is in the ev_mbox), and our assumptions remain true.
238
239 There are a couple implications of this style.  If you have a shared event
240 queue (with other event sources), those events can get mixed in with the
241 recovery.  Don't leave the vcore context due to other events.  This'll
242 probably need work.  The other thing is that completed syscalls can get
243 handled in a different order than they were signaled.  Shouldn't be a big
244 deal.
245
246 Note on the overflow handling flag and unsetting it.  There should not be any
247 races with this.  The flag prevented us from handling overflows on the event
248 queue.  Other than when we checked for events that had been succesfully sent,
249 we didn't try to handle events.  We can unset the flag, and at that point we
250 can start handling missed events.  If there was an overflow after we last
251 checked the list, but before we cleared the overflow-handling flag, we'll
252 still catch it since we haven't tried handling events in between checking the
253 list and clearing the flag.  That flag doesn't even matter until we want to
254 handle_events, so we aren't missing anything.  the next handle_events() will
255 deal with everything from scratch.
256
257 For blocking threads that block concurrently with the overflow handling: in
258 the pthread case, this can't happen since everything is per-vcore.  If you do
259 have process-wide thread blocking/syscall management, we can add new ones, but
260 they must have event delivery turned off when they are added to the list.  And
261 you'll need to lock the list, etc.  This should work in part due to new
262 syscalls being added to the end of the list, and the overflow-handler
263 proceeding linearly through the list.
264
265 Also note that we shouldn't handle the event for unblocking a syscall on a
266 different core than the one it was submitted to.  This could result in
267 concurrent modifications to the original core's TAILQ (bad).  This restriction
268 is dependent on how a 2LS does its thread handling/blocking.
269
270 Eventually, we'll want a way to detect and handle excessive overflow, since
271 it's probably quite expensive.  Perhaps turn it off and periodically poll the
272 syscalls for completion (but don't bother turning on the ev_q).
273 ---------------------------
274
275 3. Event Delivery / Notification
276 ====================
277 3.1 Basics
278 ----------------------------------------------
279 The mbox (mailbox) is where the actual messages go.
280
281         struct ev_mbox {
282                 bcq of notif_events     /* bounded buffer, multi-consumer/producer */
283                 msg_bitmap
284         }
285         struct ev_queue {                       /* aka, event_q, ev_q, etc. */
286                 struct ev_mbox * 
287                 void handler(struct event_q *)
288                 vcore_to_be_told
289                 flags                                   /* IPI_WANTED, RR, 2L-handle-it, etc */
290         }
291         struct ev_queue_big {
292                 struct ev_mbox *                /* pointing to the internal storage */
293                 vcore_to_be_told
294                 flags                                   /* IPI_WANTED, RR, 2L-handle-it, etc */
295                 struct ev_mbox { }              /* never access this directly */
296         }
297
298 The purpose of the big one is to simply embed some storage.  Still, only
299 access the mbox via the pointer.  The big one can be casted (and stored as)
300 the regular, so long as you know to dealloc a big one (free() knows, custom
301 styles or slabs would need some help).
302
303 The ev_mbox says where to put the actual message, and the flags handle things
304 such as whether or not an IPI is wanted.
305
306 Using pointers for the ev_q like this allows multiple event queues to use the
307 same mbox.  For example, we could use the vcpd queue for both kernel-generated
308 events as well as async syscall responses.  The notification table is actually
309 a bunch of ev_qs, many of which could be pointing to the same vcore/vcpd-mbox,
310 albeit with different flags.
311
312 3.2 Kernel Notification Using Event Queues
313 ----------------------------------------------
314 The notif_tbl/notif_methods (kernel-generated 'one-sided' events) is just an
315 array of struct ev_queue*s.  Handling a notification is like any other time
316 when we want to send an event.  Follow a pointer, send a message, etc.  As
317 with all ev_qs, ev_mbox* points to where you want the message for the event,
318 which usually is the vcpd's mbox.  If the ev_q pointer is 0, then we know the
319 process doesn't want the event (equivalent to the older 'NOTIF_WANTED' flag).
320 Theoretically, we can send kernel notifs to user threads.  While it isn't
321 clear that anyone will ever want this, it is possible (barring other issues),
322 since they are just events.
323
324 Also note the flag EVENT_VCORE_APPRO.  Processes should set this for certain
325 types of events where they want the kernel to send the event/IPI to the
326 'appropriate' vcore.  For example, when sending a message about a preemption
327 coming in, it makes sense for the kernel to send it to the vcore that is going
328 to get preempted, but the application could choose to ignore the notification.
329 When this flag is set, the kernel will also use the vcore's ev_mbox, ignoring
330 the process's choice.  We can change this later, but it doesn't really make
331 sense for a process to pick an mbox and also say VCORE_APPRO.
332
333 There are also interfaces in the kernel to put a message in an ev_mbox
334 regardless of the process's wishes (post_vcore_event()), and can send an IPI
335 at any time (proc_notify()).
336
337 3.3 IPIs, Indirection Events, and Fallback
338 ----------------------------------------------
339 An ev_q can ask for an IPI, an indirection event, and a fallback in case a vcore
340 is offline.  Or any combination of these.  Note that these have little to do
341 with the actual message being sent.  The actual message is dropped in the
342 ev_mbox pointed to by the ev_q.
343
344 The main use for all of this is for syscalls.  If you want to receive an event
345 when a syscall completes or has a change in status, simply allocate an event_q,
346 and point the syscall at it.  syscall: ev_q* -> "vcore for IPI, syscall message
347 in the ev_q mbox", etc.  You can also point it to an existing ev_q.  Pthread
348 code has examples of two ways to do this.  Both have per vcore ev_qs, requesting
349 IPIs, INDIRS, and FALLBACK.  One way is to have an ev_mbox per vcore, and
350 another is to have a global ev_mbox that all ev_qs point to.  As a side note, if
351 you do the latter, you don't need to worry about a vcore's ev_q if it gets
352 preempted: just check the global ev_mbox (which is done by checking your own
353 vcore's syscall ev_q).
354
355 3.3.1: IPIs and INDIRs
356 ---------------
357 An EVENT_IPI simply means we'll send an IPI to the given vcore.  Nothing else.
358 This will usually be paired with an Indirection event (EVENT_INDIR).  An INDIR
359 is a message of type EV_EVENT with an ev_q* payload.  It means "check this
360 ev_q".  Most ev_qs that ask for an IPI will also want an INDIR so that the vcore
361 knows why it was IPIed.  You don't have to do this: for instance, your 2LS might
362 poll its own ev_q, so you won't need the indirection event.
363
364 Additionally, note that IPIs and INDIRs can be spurious.  It's not a big deal to
365 receive and IPI and have nothing to do, or to be told to check an empty ev_q.
366 All of the event handling code can deal with this.
367
368 INDIR events are sent to the VCPD public mbox, which means they will get handled
369 if the vcore gets preempted.  Any other messages sent here will also get handled
370 during a preemption.  However, the only type of messages you should use this for
371 are ones that can handle spurious messages.  The completion of a syscall is an
372 example of a message that cannot be spurious.  Since INDIRs can be spurious, we
373 can use the public mbox.  (Side note: the kernel may spam INDIRs in attempting
374 to make sure you get the message on a vcore that didn't yield.)
375
376 Never use a VCPD mbox (public or private) for messages you might want to receive
377 if that vcore is offline.  If you want to be sure to get a message, create your
378 own ev_q and set flags for INDIR, FALLBACK, and IPI.  There's no guarantee a
379 *specific* message will get looked at.  In cases where it won't, the kernel will
380 send that message to another vcore.  For example, if the kernel posts an INDIR
381 to a VCPD mbox (the public one btw) and it loses a race with the vcore yielding,
382 the vcore might never see that message.  However, the kernel knows it lost the
383 race, and will find another vcore to send it to.
384
385 3.3.2: Fallback
386 ---------------
387 Both IPI and INDIR need an actual vcore.  If that vcore is unavailable and if
388 EVENT_FALLBACK is set, the kernel will pick another vcore and send the messages
389 there.  This allows an ev_q to be set up to handle work when the vcore is
390 online, while allowing the program to handle events when that core yields,
391 without having to reset all of its ev_qs to point to "known" available vcores
392 (and avoiding those races).  Note 'online' is synonymous with 'mapped', when
393 talking about vcores.  A vcore technically isn't always online, only destined to
394 be online, when it is mapped to a pcore (kmsg on the way, etc).  It's easiest to
395 think of it being online for the sake of this discussion.
396
397 One question is whether or not 2LSs need a FALLBACK flag for their ev_qs.  The
398 main use for FALLBACK is so that vcores can yield.  (Note that fallback won't
399 help you *miss* INDIR messages in the event of a preemption; you can always lose
400 that race due to it taking too long to process the messages).  An alternative
401 would be for vcores to pick another vcore and change all of its ev_qs to that
402 vcore.  There are a couple problems with this.  One is that it'll be a pain to
403 get those ev_qs back when the vcore comes back online (if ever).  Another issue
404 is that other vcores will build up a list of ev_qs that they aren't aware of,
405 which will be hard to deal with when *they* yield.  FALLBACK avoids all of those
406 problems.
407
408 An important aspect of FALLBACK is that it works with yielded vcores, not
409 preempted vcores.  It could be that there are no cores that are online, but
410 there should always be at least one core that *will* be online in the future, a
411 core that the process didn't want to lose and will deal with in the future.  If
412 not for this distinction, FALLBACK could fail.  An older idea would be to have
413 fallback send the msg to the desired vcore if there were no others.  This would
414 not work if the vcore yielded and then the entire process was preempted or
415 otherwise not running.  Another way to put this is that we need a field to
416 determine whether a vcore is offline temporarily or permanently.
417
418 This is why we have the VCPD field 'can_rcv_msg'.  It tells the kernel's event
419 delivery code that the vcore will check the messages: it is an acceptable
420 destination for a FALLBACK.  There are two reasons to put this in VCPD:
421 1) Userspace can remotely turn off a vcore's msg reception.  This is necessary
422 for handling preemption of a vcore that was in uthread context, so that we can
423 remotely 'yield' the core without having to sys_change_vcore() (which I discuss
424 below, and is meant to 'unstick' a vcore).
425 2) Yield is simplified.  The kernel no longer races with itself nor has to worry
426 about turning off that flag - userspace can do it when it wants to yield.  (turn
427 off the flag, check messages, then yield).  This is less big of a deal now that
428 the kernel races with vcore membership in the online_vcs list.
429
430 Two aspects of the code make this work nicely.  The 'can_rcv_msg' flag greatly
431 simplifies the kernel's job.  There are a lot of weird races we'd have to deal
432 with, such as process state (RUNNING_M), whether a mass preempt is going on, or
433 just one core, or a bunch of cores, mass yields, etc.  A flag that does one
434 thing well helps a lot - esp since preemption is not the same as yielding.  The
435 other useful thing is being able to handle spurious events.  Vcore code can
436 handle extra IPIs and INDIRs to non-VCPD ev_qs.  Any vcore can handle an ev_q
437 that is "non-VCPD business".
438
439 Worth mentioning is the difference between 'notif_pending' and 'can_rcv_msg'.
440 'can_rcv_msg' is the process saying it will check for messages.  'notif_pending'
441 is when the kernel says it *has* sent a message.  'notif_pending' is also used
442 by the kernel in proc_yield() and the 2LS in pop_ros_tf() to make sure the sent
443 message is not missed.
444
445 Also, in case this comes up, there's a slight race on changing the mbox* and the
446 vcore number within the event_q.  The message could have gone to the wrong (old)
447 vcore, but not the IPI.  Not a big deal - IPIs can be spurious, and the other
448 vcore will eventually get it.  The real way around this is create a new ev_q and
449 change the pointer (thus atomically changing the entire ev_q's contents), though
450 this can be a bit tricky if you have multiple places pointing to the same ev_q
451 (can't change them all at once).
452
453 3.3.3: Fallback and Preemption
454 ---------------
455 FALLBACK doesn't protect you from preemptions.  A vcore can be preempted and
456 have INDIRs in its VCPD.
457
458 It is tempting to just use sys_change_vcore(), which will change the calling
459 vcore to the new one.  This should only be used to "unstick" a vcore.  A vcore
460 is stuck when it was preempted while it had notifications disabled.  This is
461 usually when it is vcore context, but also in any lock holding code for locks
462 shared with vcore context (the userspace equivalent of irqsave locks).  With
463 this syscall, you could change to the offline vcore and process its INDIRs.
464
465 The problem with that plan is the calling core (that is trying to save the
466 other) may have extra messages, and that sys_change_vcore does not return.  We
467 need a way to deal with our other messages.  We're back to the same problem we
468 had before, just with different vcores.  The only thing we really accomplished
469 is that we unstuck the other vcore.  We could tell the restarted vcore (via an
470 event) to switch back to us, but by the time it does that, it may have other
471 events that got lost.  So we're back to polling the ev_qs that it might have
472 received INDIRs about.  Note that we still want to send an event with
473 sys_change_vcore().  We want the new vcore to know the old vcore was put
474 offline: a preemption (albeit one that it chose to do, and one that isn't stuck
475 in vcore context).
476
477 One older way to deal with this was to force the 2LS to deal with this. The 2LS
478 would check the ev_mboxes/ev_qs of all ev_qs that could send INDIRS to the
479 offline vcore.  There could be INDIRS in the VCPD that are just lying there.
480 The 2LS knows which ev_qs these are (such as for completed syscalls), and for
481 many things, this will be a common ev_q (such as for 'vcore-x-was-preempted').
482 However, this is a huge pain in the ass, since a preempted vcore could have the
483 FALLBACK INDIR for an ev_q associated with another vcore.  To deal with this,
484 the 2LS would need to check *every* ev_q that requests INDIRs.  We don't do
485 this.
486
487 Instead, we simply have the remote core check the VCPD public mbox of the
488 preempted vcore.  INDIRs (and other vcore business that other vcores can handle)
489 will get sorted here.
490
491 3.3.5: Lists to Find Vcores
492 ---------------
493 A process has three lists: online, bulk_preempt, and inactive.  These not only
494 are good for process management, but also for helping alert_vcore() find
495 potentially alertable vcores.  alert_vcore() and its associated helpers are
496 failry complicated and heavily commented.  I've set things up so both the
497 online_vcs and the bulk_preempted_vcs lists can be handled the same way: post to
498 the first element, then see if it still 'can_rcv_msg'.  If not, if it is still
499 the first on the list, then it hasn't proc_yield()ed yet, and it will eventually
500 restart when it tries to yield.  And this all works without locking the
501 proc_lock.  There are a bunch more details and races avoided.  Check the code
502 out.
503
504 3.3.6: Vcore Business and the VCPD mboxs
505 ---------------
506 There are two types of VCPD mboxes: public and private.  Public ones will get
507 handled during preemption recovery.  Messages sent here need to be handle-able
508 by any vcore.  Private messages are for that specific vcore.  In the common
509 case, the public mbox will usually only get looked at by its vcore.  Only during
510 recovery and some corner cases will we deal with it remotely.
511
512 Here's some guidelines: if you message is spammy and the handler can deal with
513 spurious events and it doesn't need to be on a specific vcore, then go with
514 public.  Examples of public mbox events are ones that need to be spammed:
515 preemption recovery, INDIRs, etc.  Note that you won't need to worry about
516 these: uthread code and the kernel handle them.  But if you have something
517 similar, then that's where it would go.  You can also send non-spammy things,
518 but there's no guarantee they'll be looked at.
519
520 Some messages should only be sent to the private mbox.  These include ones that
521 make no sense for other vcores to handle.  Examples: 2LS IPIs/preemptions (like
522 "change your scheduling policy vcore 3", preemption-pending notifs from the
523 kernel, timer interrupts, etc.
524
525 An example of something that shouldn't be sent to either is syscall completions.
526 They can't be spammed, so you can't send them around like INDIRs.  And they need
527 to be dealt with.  Other than carefully-spammed public messages, there's no
528 guarantee of getting a message for certain scenarios (yields).  Instead, use an
529 ev_q with INDIR set.
530
531 Also note that a 2LS could set up a big ev_q with EVENT_IPI and not EVENT_INDIR,
532 and then poll for that in their vcore_entry().  This is equivalent to setting up
533 a small ev_q with EVENT_IPI and pointing it at the private mbox.
534
535 3.4 Application-specific Event Handling
536 ---------------------------------------
537 So what happens when the vcore/2LS isn't handling an event queue, but has been
538 "told" about it?  This "telling" is in the form of an IPI.  The vcore was
539 prodded, but is not supposed to handle the event.  This is actually what
540 happens now in Linux when you send signals for AIO.  It's all about who (which
541 thread, in their world) is being interrupted to process the work in an
542 application specific way.  The app sets the handler, with the option to have a
543 thread spawned (instead of a sighandler), etc.
544
545 This is not exactly the same as the case above where the ev_mbox* pointed to
546 the vcore's default mbox.  That issue was just about avoiding extra messages
547 (and messages in weird orders).  A vcore won't handle an ev_q if the
548 message/contents of the queue aren't meant for the vcore/2LS.  For example, a
549 thread can want to run its own handler, perhaps because it performs its own
550 asynchronous I/O (compared to relying on the 2LS to schedule synchronous
551 blocking u_threads).
552
553 There are a couple ways to handle this.  Ultimately, the application is supposed
554 to handle the event.  If it asked for an IPI, it is because something ought to
555 be done, which really means running a handler.  If the application sets
556 EVENT_THREAD in the ev_q's flags, the 2LS ought to spawn a thread to run the
557 ev_q's handler.  If EVENT_JUSTHANDLEIT is set, the vcore will execute the
558 handler itself.  Careful with this, since the only memory it touches must be
559 pinned, the function must not block (this is only true for the handlers called
560 directly out of vcore context), and it should return quickly.
561
562 Note that in either case, vcore-written code (library code) does not look at
563 the contents of the notification event.  Also note the handler takes the whole
564 event_queue, and not a specific message.  It is more flexible, can handle
565 multiple specific events, and doesn't require the vcore code to dequeue the
566 event and either pass by value or allocate more memory.
567
568 These ev_q handlers are different than ev_handlers.  The former handles an
569 event_queue.  The latter is the 2LS's way to handle specific types of messages.
570 If an app wants to process specific messages, have them sent to an ev_q under
571 its control; don't mess with ev_handlers unless you're the 2LS (or example
572 code).
573
574 Continuing the analogy between vcores getting IPIs and the OS getting HW
575 interrupts, what goes on in vcore context is like what goes on in interrupt
576 context, and the threaded handler is like running a threaded interrupt handler
577 (in Linux).  In the ROS world, it is like having the interrupt handler kick
578 off a kernel message to defer the work out of interrupt context.
579
580 If neither of the application-specific handling flags are set, the vcore will
581 respond to the IPI by attempting to handle the event on its own (lookup table
582 based on the type of event (like "syscall complete")).  If you didn't want the
583 vcore to handle it, then you shouldn't have asked for an IPI.  Those flags are
584 the means by which the vcore can distinguish between its event_qs and the
585 applications.  It does not make sense otherwise to send the vcore an IPI and
586 an event_q, but not tell give the code the info it needs to handle it.
587
588 In the future, we might have the ability to block a u_thread on an event_q, so
589 we'll have other EV_ flags to express this, and probably a void*.  This may
590 end up being redudant, since u_threads will be able to block on syscalls (and
591 not necessarily IPIs sent to vcores).
592
593 As a side note, a vcore can turn off the IPI wanted flag at any time.  For
594 instance, when it spawns a thread to handle an ev_q, the vcore can turn off
595 IPI wanted on that event_q, and the thread handler can turn it back on when it
596 is done processing and wants to be re-IPId.  The reason for this is to avoid
597 taking future IPIs (once we leave vcore context, IPIs are enabled) to let us
598 know about an event for which a handler is already running.
599
600 3.5 Overflowed/Missed Messages in the VCPD 
601 ---------------------------------------
602 This too is no longer necessary.  It's useful in that it shows what we don't
603 have to put up with.  Missing messages requires potentially painful
604 infrastructure to handle it:
605
606 -----------------------------
607 All event_q's requesting IPIs ought to register with the 2LS.  This is for
608 recovering in case the vcpd's mbox overflowed, and the vcore knows it missed a
609 NE_EVENT type message.  At that point, it would have to check all of its
610 IPI-based queues.  To do so, it could check to see if the mbox has any
611 messages, though in all likelihood, we'll just act as if there was a message
612 on each of the queues (all such handlers should be able to handle spurious
613 IPIs anyways).  This is analagous to how the OS's block drivers don't solely
614 rely on receiving an interrupt (they deal with it via timeouts).  Any user
615 code requiring an IPI must do this.  Any code that runs better due to getting
616 the IPI ought to do this.
617
618 We could imagine having a thread spawned to handle an ev_q, and the vcore
619 never has to touch the ev_q (which might make it easier for memory
620 allocation).  This isn't a great idea, but I'll still explain it.  In the
621 notif_ev message sent to the vcore, it has the event_q*.  We could also send a
622 flag with the same info as in the event_q's flags, and also send the handler.
623 The problem with this is that it isn't resilient to failure.  If there was a
624 message overflow, it would have the check the event_q (which was registered
625 before) anyway, and could potentially page fault there.  Also the kernel would
626 have faulted on it (and read it in) back when it tried to read those values.
627 It's somewhat moot, since we're going to have an allocator that pins event_qs.
628 -----------------------------
629
630 3.6 Round-Robin or Other IPI-delivery styles
631 ---------------------------------------
632 In the same way that the IOAPIC can deliver interrupts to a group of cores,
633 round-robinning between them, so can we imagine processes wanting to
634 distribute the IPI/active notification of events across its vcores.  This is
635 only meaningful is the NOTIF_IPI_WANTED flag is set.
636
637 Eventually we'll support this, via a flag in the event_q.  When
638 NE_ROUND_ROBIN, or whatever, is set a couple things will happen.  First, the
639 vcore field will be used in a "delivery-specific" manner.  In the case of RR,
640 it will probably be the most recent destination.  Perhaps it will be a bitmask
641 of vcores available to receive.  More important is the event_mbox*.  If it is
642 set, then the event message will be sent there.  Whichever vcore gets selected
643 will receive an IPI, and its vcpd mbox will get a NE_EVENT message.  If the
644 event_mbox* is 0, then the actual message will get delivered to the vcore's
645 vcpd mbox (the default location).
646
647 3.7 Event_q-less Notifications
648 ---------------------------------------
649 Some events needs to be delivered directly to the vcore, regardless of any
650 event_qs.  This happens currently when we bypass the notification table (e.g.,
651 sys_self_notify(), preemptions, etc).  These notifs will just use the vcore's
652 default mbox.  In essence, the ev_q is being generated/sent with the call.
653 The implied/fake ev_q points to the vcpd's mbox, with the given vcore set, and
654 with IPI_WANTED set.  It is tempting to make those functions take a
655 dynamically generated ev_q, though more likely we'll just use the lower level
656 functions in the kernel, much like the Round Robin set will need to do.  No
657 need to force things to fit just for the sake of using a 'solution'.  We want
658 tools to make solutions, not packaged solutions.
659
660 3.8 UTHREAD_DONT_MIGRATE
661 ---------------------------------------
662 DONT_MIGRATE exists to allow uthreads to disable notifications/IPIs and enter
663 vcore context.  It is needed since you need to read vcoreid to disable notifs,
664 but once you read it, you need to not move to another vcore.  Here are a few
665 rules/guidelines.
666
667 We turn off the flag so that we can disable notifs, but turn the flag back on
668 before enabling.  The thread won't get migrated in that instant since notifs are
669 off.  But if it was the other way, we could miss a message (because we skipped
670 an opportunity to be dropped into vcore context to read a message).
671
672 Don't check messages/handle events when you have a DONT_MIGRATE uthread.  There
673 are issues with preemption recovery if you do.  In short, if two uthreads are
674 both DONT_MIGRATE with notifs enabled on two different vcores, and one vcore
675 gets preempted while the other gets an IPI telling it to recover the other one,
676 both could keep bouncing back and forth if they handle their preemption
677 *messages* without dealing with their own DONT_MIGRATEs first.  Note that the
678 preemption recovery code can handle having a DONT_MIGRATE thread on the vcore.
679 This is a special case, and it is very careful about how cur_uthread works.
680
681 All uses of DONT_MIGRATE must reenable notifs (and check messages) at some
682 point.  One such case is uthread_yield().  Another is mcs_unlock_notifsafe().
683 Note that mcs_notif_safe locks have uthreads that can't migrate for a
684 potentially long time.  notifs are also disabled, so it's not a big deal.  It's
685 basically just the same as if you were in vcore context (though technically you
686 aren't) when it comes to preemption recovery: we'll just need to restart the
687 vcore via a syscall.  Also note that it would be a real pain in the ass to
688 migrate a notif_safe locking uthread.  The whole point of it is in case it grabs
689 a lock that would be held by vcore context, and there's no way to know it isn't
690 a lock on the restart-path.
691
692 4. Misc Things That Aren't Sorted Completely:
693 ====================
694 4.1 What about short handlers?
695 ---------------------------------------
696 Once we sort the other issues, we can ask for them via a flag in the event_q,
697 and run the handler in the event_q struct.
698
699 4.2 What about blocking on a syscall?
700 ---------------------------------------
701 The current plan is to set a flag, and let the kernel go from there.  The
702 kernel knows which process it is, since that info is saved in the kthread that
703 blocked.  One issue is that the process could muck with that flag and then go
704 to sleep forever.  To deal with that, maybe we'd have a long running timer to
705 reap those.  Arguably, it's like having a process while(1).  You can screw
706 yourself, etc.  Killing the process would still work.