VCORE_APPRO sets the ev_mbox
[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 Notif_table: This is a list of event_q*s that correspond to certain
66 unexpected/"one-sided" events the kernel sends to the process.  It is similar
67 to an IRQ table in the kernel.  Each event_q tells the kernel how the process
68 wants to be told about the specific event type.
69
70 Notifications: used to be a generic event, but now used in terms of the verb
71 'notify' (do_notify()).  In older docs, passive notification is just writing a
72 message somewhere.  Active notification is an IPI delivered to a vcore.  I use
73 that term interchangeably with an IPI, and usually you can tell by context
74 that I'm talking about an IPI going to a process (and not just the kernel).
75 The details of it make it more complicated than just an IPI, but it's
76 analagous.  I've start referring to notification as the IPI, and "passive
77 notification" as just events, though older documentation has both meanings.
78
79 BCQ: "bounded concurrent queue".  It is a fixed size array of messages
80 (structs of notification events, or whatever).  It is non-blocking, supporting
81 multiple producers and consumers, where the producers do not trust the
82 consumers.  It is the primary mechanism for the kernel delivering message
83 payloads into a process's address space.  Note that producers don't trust each
84 other either (in the event of weirdness, the producers give up and say the
85 buffer is full).  This means that a process can produce for one of its ev_qs
86 (which is what they need to do to send message to itself).
87
88 2. Async Syscalls and I/O
89 ====================
90 The syscall struct is the contract for work with the kernel, including async
91 I/O.  Lots of current OS async packages use epoll or other polling systems.
92 Note the distinction between Polling and Async I/O.  Polling is about finding
93 out if a call will block.  It is primarily used for sockets and pipes.  It
94 does relatively nothing for disk I/O, which requires a separate async I/O
95 system.  By having all syscalls be async, we can make polling a bit easier and
96 more unified with the generic event code that we use for all syscalls.
97
98 For instance, we can have a sys_poll syscall, which is async just like any
99 other syscall.  The call can be a "one shot / non-blocking", like the current
100 systems polling code, or it can also notify on change (not requiring future
101 polls) via the event_q mechanisms.  If you don't want to be IPId, you can
102 "poll" the syscall struct - not requiring another kernel crossing/syscall.
103
104 Note that we do not tie syscalls and polling to FDs.  We do events on
105 syscalls, which can be used to check FDs.  I think a bunch of polling cases
106 will not be needed once we have async syscalls, but for those that remain,
107 we'll have sys_poll() (or whatever).
108
109 To receive an event on a syscall completion or status change, just fill in the
110 event_q pointer.  If it is 0, the kernel will assume you poll the actual
111 syscall struct.
112
113         struct syscall {
114                 current stuff                   /* arguments, retvals */
115                 struct ev_queue *               /* struct used for messaging, including IPIs*/
116                 void *                                  /* used by 2LS, usually a struct u_thread * */
117         }
118
119 One issue with async syscalls is that there can be too many outstanding IOs
120 (normally sync calls provide feedback / don't allow you to over-request).
121 Eventually, processes can exhaust kernel memory (the kthreads, specifically).
122 We need a way to limit the kthreads per proc, etc.  Shouldn't be a big deal.
123
124 Normally, we talk about changing the flag in a syscall to SC_DONE.  Async
125 syscalls can be SC_PROGRESS (new stuff happened on it), which can trigger a
126 notification event.  Some calls, like AIO or bulk accept, exist for a while
127 and slowly get filled in / completed.  In the future, we'll also want a way to
128 abort the in-progress syscalls (possibly any syscall!).
129
130 3. Event Delivery / Notification
131 ====================
132 3.1 Basics
133 ----------------------------------------------
134 The mbox (mailbox) is where the actual messages go, or the overflow of a
135 message is tracked.
136
137         struct ev_mbox {
138                 bcq of notif_events     /* bounded buffer, multi-consumer/producer */
139                 overflow_count
140                 msg_bitmap
141         }
142         struct ev_queue {                       /* aka, event_q, ev_q, etc. */
143                 struct ev_mbox * 
144                 void handler(struct event_q *)
145                 vcore_to_be_told
146                 flags                                   /* IPI_WANTED, RR, 2L-handle-it, etc */
147         }
148         struct ev_queue_big {
149                 struct ev_mbox *                /* pointing to the internal storage */
150                 vcore_to_be_told
151                 flags                                   /* IPI_WANTED, RR, 2L-handle-it, etc */
152                 struct ev_mbox { }              /* never access this directly */
153         }
154
155 The purpose of the big one is to simply embed some storage.  Still, only
156 access the mbox via the pointer.  The big one can be casted (and stored as)
157 the regular, so long as you know to dealloc a big one (free() knows, custom
158 styles or slabs would need some help).
159
160 The ev_mbox says where to put the actual message, and the flags handle things
161 such as whether or not an IPI is wanted.
162
163 Using pointers for the ev_q like this allows multiple event queues to use the
164 same mbox.  For example, we could use the vcpd queue for both kernel-generated
165 events as well as async syscall responses.  The notification table is actually
166 a bunch of ev_qs, many of which could be pointing to the same vcore/vcpd-mbox,
167 albeit with different flags.
168
169 3.2 Kernel Notification Using Event Queues
170 ----------------------------------------------
171 The notif_tbl/notif_methods (kernel-generated 'one-sided' events) is just an
172 array of struct ev_queue*s.  Handling a notification is like any other time
173 when we want to send an event.  Follow a pointer, send a message, etc.  As
174 with all ev_qs, ev_mbox* points to where you want the message for the event,
175 which usually is the vcpd's mbox.  If the ev_q pointer is 0, then we know the
176 process doesn't want the event (equivalent to the older 'NOTIF_WANTED' flag).
177 Theoretically, we can send kernel notifs to user threads.  While it isn't
178 clear that anyone will ever want this, it is possible (barring other issues),
179 since they are just events.
180
181 Also note the flag EVENT_VCORE_APPRO.  Processes should set this for certain
182 types of events where they want the kernel to send the event/IPI to the
183 'appropriate' vcore.  For example, when sending a message about a preemption
184 coming in, it makes sense for the kernel to send it to the vcore that is going
185 to get preempted, but the application could choose to ignore the notification.
186 When this flag is set, the kernel will also use the vcore's ev_mbox, ignoring
187 the process's choice.  We can change this later, but it doesn't really make
188 sense for a process to pick an mbox and also say VCORE_APPRO.
189
190 There are also interfaces in the kernel to put a message in an ev_mbox
191 regardless of the process's wishes (post_vcore_event()), and can send an IPI
192 at any time (proc_notify()).
193
194 3.3 IPIs and Indirection Events
195 ----------------------------------------------
196 When an ev_q calls for an IPI, the kernel finds out what vcore the process
197 wants.  The code already sent the message to the ev_q's mbox.  If the vcore's
198 vcpd mbox is the same as the ev_q's mbox (pointer check), then just send the
199 IPI.  If it is different, we need to put a message in the vcpd's mbox telling
200 them "ev_q*", so the vcore knows why it got an IPI.  This level of indirection
201 is only necessary when the ev_q requests an IPI and it is not the vcore using
202 its vcpd mbox.  The vcore needs to know why it received an IPI.  The IPI
203 (active notifcation) is merely a prodding, and the vcore needs a known place
204 to look for why it was woken up.  This is a little different when dealing with
205 non-specific IPIs (like Round-Robin).
206
207 If the vcore gets an indirection message, it will be of type NE_EVENT (or
208 whatever), with an ev_q* as the payload.
209
210 In the event there are issues with this, we can introduce a flag that says we
211 don't need a separate notif_event explaining the IPI: prodding the vcore was
212 enough.  Either way, we can deliver event messages directly to the vcore's
213 mbox / bcq.
214
215 There's a slight race on changing the mbox* and the vcore number within the
216 event_q.  The message could have gone to the wrong (old) vcore, but not the
217 IPI.  Not a big deal - IPIs can be spurious, and the other vcore will
218 eventually get it.  The real way around this is create a new ev_q and change
219 the pointer (thus atomically changing the entire ev_q's contents), though this
220 can be a bit tricky if you have multiple places pointing to the same ev_q
221 (can't change them all at once).
222
223 If you want to receive an event when a syscall completes or has a change in
224 status, simply allocate an event_q, and point the syscall at it.  syscall:
225 ev_q* -> "vcore for IPI, syscall message in the ev_q mbox", etc.  You can also
226 point it to an existing ev_q.
227
228 3.4 Application-specific Event Handling
229 ---------------------------------------
230 So what happens when the vcore/2LS isn't handling an event queue, but has been
231 "told" about it?  This "telling" is in the form of an IPI.  The vcore was
232 prodded, but is not supposed to handle the event.  This is actually what
233 happens now in Linux when you send signals for AIO.  It's all about who (which
234 thread, in their world) is being interrupted to process the work in an
235 application specific way.  The app sets the handler, with the option to have a
236 thread spawned (instead of a sighandler), etc.
237
238 This is not exactly the same as the case above where the ev_mbox* pointed to
239 the vcore's default mbox.  That issue was just about avoiding extra messages
240 (and messages in weird orders).  A vcore won't handle an ev_q if the
241 message/contents of the queue aren't meant for the vcore/2LS.  For example, a
242 thread can want to run its own handler, perhaps because it performs its own
243 asynchronous I/O (compared to relying on the 2LS to schedule synchronous
244 blocking u_threads).
245
246 There are a couple ways to handle this.  Ultimately, the application is
247 supposed to handle the event.  If it asked for an IPI, it is because something
248 ought to be done, which really means running a handler.  If the application
249 sets EV_THREAD in the ev_q's flags, the 2LS ought to spawn a thread to run the
250 ev_q's handler.  If EV_JUSTHANDLEIT is set, the vcore will execute the handler
251 itself.  Careful with this, since the only memory it touches must be pinned,
252 the function must not block (this is only true for the handlers called
253 directly out of vcore context), and it should return quickly.
254
255 Note that in either case, vcore-written code (library code) does not look at
256 the contents of the notification event.  Also Note the handler takes the whole
257 event_queue, and not a specific message.  It is more flexible, can handle
258 multiple specific events, and doesn't require the vcore code to dequeue and
259 event and either pass by value or allocate more memory.
260
261 Continuing the analogy between vcores getting IPIs and the OS getting HW
262 interrupts, what goes on in vcore context is like what goes on in interrupt
263 context, and the threaded handler is like running a threaded interrupt handler
264 (in Linux).  In the ROS world, it is like having the interrupt handler kick
265 off a kernel message to defer the work out of interrupt context.
266
267 If neither of the application-specific handling flags are set, the vcore will
268 respond to the IPI by attempting to handle the event on its own (lookup table
269 based on the type of event (like "syscall complete")).  If you didn't want the
270 vcore to handle it, then you shouldn't have asked for an IPI.  Those flags are
271 the means by which the vcore can distinguish between its event_qs and the
272 applications.  It does not make sense otherwise to send the vcore an IPI and
273 an event_q, but not tell give the code the info it needs to handle it.
274
275 In the future, we might have the ability to block a u_thread on an event_q, so
276 we'll have other EV_ flags to express this, and probably a void*.  This may
277 end up being redudant, since u_threads will be able to block on syscalls (and
278 not necessarily IPIs sent to vcores).
279
280 As a side note, a vcore can turn off the IPI wanted flag at any time.  For
281 instance, when it spawns a thread to handle an ev_q, the vcore can turn off
282 IPI wanted on that event_q, and the thread handler can turn it back on when it
283 is done processing and wants to be re-IPId.  The reason for this is to avoid
284 taking future IPIs (once we leave vcore context, IPIs are enabled) to let us
285 know about an event for which a handler is already running.
286
287 3.5 Overflowed/Missed Messages in the VCPD 
288 ---------------------------------------
289 All event_q's requesting IPIs ought to register with the 2LS.  This is for
290 recovering in case the vcpd's mbox overflowed, and the vcore knows it missed a
291 NE_EVENT type message.  At that point, it would have to check all of its
292 IPI-based queues.  To do so, it could check to see if the mbox has any
293 messages, though in all likelihood, we'll just act as if there was a message
294 on each of the queues (all such handlers should be able to handle spurious
295 IPIs anyways).  This is analagous to how the OS's block drivers don't solely
296 rely on receiving an interrupt (they deal with it via timeouts).  Any user
297 code requiring an IPI must do this.  Any code that runs better due to getting
298 the IPI ought to do this.
299
300 We could imagine having a thread spawned to handle an ev_q, and the vcore
301 never has to touch the ev_q (which might make it easier for memory
302 allocation).  This isn't a great idea, but I'll still explain it.  In the
303 notif_ev message sent to the vcore, it has the event_q*.  We could also send a
304 flag with the same info as in the event_q's flags, and also send the handler.
305 The problem with this is that it isn't resilient to failure.  If there was a
306 message overflow, it would have the check the event_q (which was registered
307 before) anyway, and could potentially page fault there.  Also the kernel would
308 have faulted on it (and read it in) back when it tried to read those values.
309 It's somewhat moot, since we're going to have an allocator that pins event_qs.
310
311 3.6 Round-Robin or Other IPI-delivery styles
312 ---------------------------------------
313 In the same way that the IOAPIC can deliver interrupts to a group of cores,
314 round-robinning between them, so can we imagine processes wanting to
315 distribute the IPI/active notification of events across its vcores.  This is
316 only meaningful is the NOTIF_IPI_WANTED flag is set.
317
318 Eventually we'll support this, via a flag in the event_q.  When
319 NE_ROUND_ROBIN, or whatever, is set a couple things will happen.  First, the
320 vcore field will be used in a "delivery-specific" manner.  In the case of RR,
321 it will probably be the most recent destination.  Perhaps it will be a bitmask
322 of vcores available to receive.  More important is the event_mbox*.  If it is
323 set, then the event message will be sent there.  Whichever vcore gets selected
324 will receive an IPI, and its vcpd mbox will get a NE_EVENT message.  If the
325 event_mbox* is 0, then the actual message will get delivered to the vcore's
326 vcpd mbox (the default location).
327
328 3.7 Event_q-less Notifications
329 ---------------------------------------
330 Some events needs to be delivered directly to the vcore, regardless of any
331 event_qs.  This happens currently when we bypass the notification table (e.g.,
332 sys_self_notify(), preemptions, etc).  These notifs will just use the vcore's
333 default mbox.  In essence, the ev_q is being generated/sent with the call.
334 The implied/fake ev_q points to the vcpd's mbox, with the given vcore set, and
335 with IPI_WANTED set.  It is tempting to make those functions take a
336 dynamically generated ev_q, though more likely we'll just use the lower level
337 functions in the kernel, much like the Round Robin set will need to do.  No
338 need to force things to fit just for the sake of using a 'solution'.  We want
339 tools to make solutions, not packaged solutions.
340
341 4. Misc Things That Aren't Sorted Completely:
342 ====================
343 4.1 What about short handlers?
344 ---------------------------------------
345 Once we sort the other issues, we can ask for them via a flag in the event_q,
346 and run the handler in the event_q struct.
347
348 4.2 What about blocking on a syscall?
349 ---------------------------------------
350 The current plan is to set a flag, and let the kernel go from there.  The
351 kernel knows which process it is, since that info is saved in the kthread that
352 blocked.  One issue is that the process could muck with that flag and then go
353 to sleep forever.  To deal with that, maybe we'd have a long running timer to
354 reap those.  Arguably, it's like having a process while(1).  You can screw
355 yourself, etc.  Killing the process would still work.