Vcores are unmapped by message receivers
[akaros.git] / Documentation / process-internals.txt
1 process-internals.txt
2 Barret Rhoden
3
4 This discusses core issues with process design and implementation.  Most of this
5 info is available in the source in the comments (but may not be in the future).
6 For now, it's a dumping ground for topics that people ought to understand before
7 they muck with how processes work.
8
9 Contents:
10 1. Reference Counting
11 2. When Do We Really Leave "Process Context"?
12 3. Leaving the Kernel Stack:
13 4. Preemption and Notification Issues:
14 5. TBD
15
16 1. Reference Counting
17 ===========================
18 1.1 Basics:
19 ---------------------------
20 Reference counts (proc_refcnt) exist to keep a process alive.  Eventually, this
21 will probably turn into a regular "kernel design pattern", like it is in Linux
22 (http://lwn.net/Articles/336224/).  The style of reference counting we use for
23 processes is similar to a kref:
24 - Can only incref if the current value is greater than 0, meaning there is
25   already a reference to it.  It is a bug to try to incref on something that has
26   no references, so always make sure you incref something that you know has a
27   reference.  If you don't know, you need to get it manually (CAREFULLY!) or use
28   pid2proc (which is a careful way of doing this).  If you incref and there are
29   0 references, the kernel will panic.  Fix your bug / don't incref random
30   pointers.
31 - Can always decref.
32 - When the decref returns 0, perform some operation.  This does some final
33   cleanup on the object.
34
35 For a process, proc_destroy() decrefs, and other codes using the proc also
36 decref.  The last one to decref calls proc_free to do the final cleanup.
37
38 1.2 Brief History of the Refcnt:
39 ---------------------------
40 Originally, the refcnt was created to keep page tables from being destroyed (in
41 proc_free()) while cores were still using them, which is what was happens during
42 an ARSC (async remote syscall).  It was then defined to be a count of places in
43 the kernel that had an interest in the process staying alive, practically just
44 to protect current/cr3.  This 'interest' actually extends to any code holding a
45 pointer to the proc, such as one acquired via pid2proc(), which is its current
46 meaning.
47
48 1.3 Quick Aside: The current Macro:
49 ---------------------------
50 current is a pointer to the proc that is currently loaded/running on any given
51 core.  It is stored in the per_cpu_info struct, and set/managed by low-level
52 process code.  It is necessary for the kernel to quickly figure out who is
53 running on its code, especially when servicing interrupts and traps.  current is
54 protected by a refcnt.
55
56 1.4 Reference Counting Rules:
57 ---------------------------
58 +1 for existing.
59 - The fact that the process is supposed to exist is worth +1.  When it is time
60   to die, we decref, and it will eventually be cleaned up.
61
62 +1 for someone using it or planning to use it.
63 - This includes simply having a pointer to the proc, since presumably you will
64   use it.  pid2proc() will incref for you.  When you are done, decref.
65 - Functions that create a process and return a pointer (like proc_create() or
66   kfs_proc_create()) will also up the refcnt for you.  Decref when you're done.
67 - If the *proc is stored somewhere where it will be used again, such as in an IO
68   continuation, it needs to be refcnt'd.  Note that if you already had a
69   reference from pid2proc(), simply don't decref after you store the pointer.
70
71 +1 for current.
72 - current counts as someone using it (expressing interest in the core), but is
73   also a source of the pointer, so its a bit different.
74 - You have a reference from current and can use it without refcnting, but
75   anything that needs to eat a reference or store/use it needs an incref first.
76   To be clear, your reference is *NOT* edible.  It protects the cr3, guarantees
77   the process won't die, and serves as a bootstrappable reference.
78 - Specifically, if you get a ref from current, but then save it somewhere (like
79   an IO continuation request), then clearly you must incref, since it's both
80   current and stored/used.
81 - If you don't know what might be downstream from your function, then incref
82   before passing the reference, and decref when it returns.  Like when handling
83   syscalls, for example.
84
85 All functions that take a *proc have a refcnt'd reference, though it may not be
86 edible (it could be current).  It is the callers responsibility to make sure
87 it'd edible if it necessary.  It is the callees responsibility to incref if it
88 stores or makes a copy of the reference.
89
90 1.5 Functions That Don't or Might Not Return:
91 ---------------------------
92 Refcnting and especially decreffing gets tricky when there are functions that
93 MAY not return.  proc_startcore() does not return (it pops into userspace).
94 proc_run() might not return, if the core it was called on will pop into
95 userspace (if it was a _S, or if the core is part of the vcoremap for a _M).
96
97 Functions that MAY not return will "eat" your reference *IF* they do not return.
98 This means that you must have a reference when you call them (like always), and
99 that reference will be consumed / decref'd for you if the function doesn't
100 return.  Or something similarly appropriate.
101
102 We do this because when the function does not return, you will not have the
103 chance to decref (your decref code will never run).  We need the reference when
104 going in to keep the object alive (like with any other refcnt).  We can't have
105 the function always eat the reference, since you cannot simply re-incref the
106 pointer (not allowed to incref unless you know you had a good reference).  You'd
107 have to do something like p = pid2proc(p_pid);  It's clunky to do that, easy to
108 screw up, and semantically, if the function returns, then we may still have an
109 interest in p and should decref later.
110
111 The downside is that functions need to determine if they will return or not,
112 which can be a pain (a linear time search when running an _M, for instance,
113 which can suck if we are trying to use a broadcast/logical IPI).
114
115 As the caller, you usually won't know if the function will return or not, so you
116 need to provide a consumable reference.  Current doesn't count.  For example,
117 proc_run() requires a reference.  You can proc_run(p), and use p afterwards, and
118 later decref.  You need to make sure you have a reference, so things like
119 proc_run(pid2proc(55)) works, since pid2proc() increfs for you.  But you cannot
120 proc_run(current), unless you incref current in advance.  Incidentally,
121 proc_running current doesn't make a lot of sense.
122
123 As another example, proc_startcore() will take your reference and store it
124 in current.  Since it is used by both the __startcore and the interrupt return
125 paths, we're currently going with the model of "caller makes sure there is a ref
126 for current".  Check its comments for details.
127
128 1.6 Runnable List:
129 ---------------------------
130 Procs on the runnable list need to have a refcnt (other than the +1 for
131 existing).  It's something that cares that the process exists.  We could have
132 had it implicitly be refcnt'd (the fact that it's on the list is enough, sort of
133 as if it was part of the +1 for existing), but that complicates things.  For
134 instance, it is a source of a reference (for the scheduler) and you could not
135 proc_run() a process from the runnable list without worrying about increfing it
136 before hand.  Remember that proc_run() might consume your reference (which
137 actually turns into a current reference, which is later destroyed by decref in
138 abandon_core()).
139
140 1.7 Internal Details for Specific Functions:
141 ---------------------------
142 proc_run(): makes sure enough refcnts are in place for all places that will
143 install current.  This also makes it easier on the system (one big incref(n),
144 instead of n increfs of (1) from multiple cores).  In the off chance current was
145 already set for a core receiving the active message, __startcore will decref.
146 Also note that while proc_run() consumes your reference, it's not actually
147 decreffing, so there's no danger within proc_run() of the process dying /
148 __proc_free()ing.
149
150 proc_startcore(): assumes all references to p are sorted.  *p is already
151 accounted for as if it was current on the core startcore runs on. (there is only
152 one refcnt for both *p and current, not 2 separate ones).
153
154 proc_destroy(): it might not return (if the calling core belongs to the
155 process), so it may eat your reference and you must have an edible reference.
156 It is possible you called proc_destroy(current).  The cleanup of the current
157 will be its own decref, so you need to have a usable/real reference (current
158 doesn't count as an edible reference).  So incref before doing that.  Even if p
159 == current, proc_destroy() can't tell if you sent it p (and had a reference) or
160 current and didn't.
161
162 proc_yield(): this never returns, so it eats your reference.  It will also
163 decref when it abandon_core()s.
164
165 __proc_give_cores() and friends: you call this while holding the lock, but it is
166 possible that your core is in the corelist you gave it.  In this case, it will
167 detect it, and return a bool signalling if an IPI is pending.  It will not
168 consume your reference.  The reasoning behind this is that it is an internal
169 function, and you may want to do other things before decreffing.  There is also
170 a helper function that will unlock and possibly decref/wait for the IPI, called
171 __proc_unlock_ipi_pending().  Use this when it is time to unlock.  It's just a
172 helper, which may go away.
173
174 abandon_core(): it was not given a reference, so it doesn't eat one.  It will
175 decref when it unloads the cr3.  Note that this is a potential performance
176 issue.  When preempting or killing, there are n cores that are fighting for the
177 cacheline to decref.  An alternative would be to have one core decref for all n
178 cores, after it knows all cores unloaded the cr3.  This would be a good use of
179 the checklist (possibly with one cacheline per core).  It would take a large
180 amount of memory for better scalability.
181
182 1.8 Core Request:
183 ---------------------------
184 core_request() is run outside of the process code (for now), though it is fairly
185 intricate.  It's another function that might not return, but the reasons for
186 this vary:
187         1: The process is moving from _S to _M so the return path to userspace won't
188         happen (and sort of will on the new core / the other side), but that will
189         happen when popping into userspace.
190         2: The scheduler is giving the current core to the process, which can kick
191         in via either proc_run() or __proc_give_cores().
192         3: It was a request to give up all cores, which means the current core will
193         receive an IPI (if it wasn't an async call, which isn't handled yet).
194
195 For these reasons, core_request() needs to have an edible reference.
196
197 Also, since core_request calls functions that might not return, there are cases
198 where it will not be able to call abandon_core() and leave process context.
199 This is an example of why we have the fallback case of leaving process context
200 in proc_startcore().  See the section below about process context for more
201 information.
202
203 Eventually, core_request() will be split better, probably with the brutal logic
204 in process.c that would call out some functions in resource.c that actually make
205 choices.
206
207 1.9 Things I Could Have Done But Didn't And Why:
208 ---------------------------
209 Q: Could we have the first reference (existence) mean it could be on the runnable
210 list or otherwise in the proc system (but not other subsystems)?  In this case,
211 proc_run() won't need to eat a reference at all - it will just incref for every
212 current it will set up.
213
214 A: No: if you pid2proc(), then proc_run() but never return, you have (and lose)
215 an extra reference.  We need proc_run() to eat the reference when it does not
216 return.  If you decref between pid2proc() and proc_run(), there's a (rare) race
217 where the refcnt hits 0 by someone else trying to kill it.  While proc_run()
218 will check to see if someone else is trying to kill it, there's a slight chance
219 that the struct will be reused and recreated.  It'll probably never happen, but
220 it could, and out of principle we shouldn't be referencing memory after it's
221 been deallocated.  Avoiding races like this is one of the reasons for our refcnt
222 discipline.
223
224 Q: Could proc_run() always eat your reference, which would make it easier for
225 its implementation?
226
227 A: Yeah, technically, but it'd be a pain, as mentioned above.  You'd need to
228 reaquire a reference via pid2proc, and is rather easy to mess up.
229
230 Q: Could we have made proc_destroy() take a flag, saying whether or not it was
231 called on current and needed a decref instead of wasting an incref?
232
233 A: We could, but won't.  This is one case where the external caller is the one
234 that knows the function needs to decref or not.  But it breaks the convention a
235 bit, doesn't mirror proc_create() as well, and we need to pull in the cacheline
236 with the refcnt anyways.  So for now, no.
237
238 Q: Could we make __proc_give_cores() simply not return if an IPI is coming?
239
240 A: I did this originally, and manually unlocked and __wait_for_ipi()d.  Though
241 we'd then need to deal with it like that for all of the related functions, which
242 doesn't work if you wanted to do something afterwards (like schedule(p)).  Also
243 these functions are meant to be internal helpers, so returning the bool makes
244 more sense.  It eventually led to having __proc_unlock_ipi_pending(), which made
245 proc_destroy() much cleaner and helped with a general model of dealing with
246 these issues.  Win-win.
247
248 2. When Do We Really Leave "Process Context"?
249 ===========================
250 2.1 Overview
251 ---------------------------
252 First off, it's not really "process context" in the way Linux deals with it.  We
253 aren't operating in kernel mode on behalf of the process (always).  We are
254 specifically talking about when a process's cr3 is loaded on a core.  Usually,
255 current is also set (the exception for now is when processing ARSCs).
256
257 There are a couple different ways to do this.  One is to never unload a context
258 until something new is being run there (handled solely in proc_startcore()).
259 Another way is to always explicitly leave the core, like by abandon_core()ing.
260
261 The issue with the former is that you could have contexts sitting around for a
262 while, and also would have a bit of extra latency when __proc_free()ing during
263 someone *else's* proc_startcore() (though that could be avoided if it becomes a
264 real issue, via some form of reaping).  You'll also probably have excessive
265 decrefs (based on the interactions between proc_run() and __startcore()).
266
267 The issue with the latter is excessive TLB shootdowns and corner cases.  There
268 could be some weird cases (in core_request() for example) where the core you are
269 running on has the context loaded for proc A on a mgmt core, but decides to give
270 it to proc B.
271
272 If no process is running there, current == 0 and boot_cr3 is loaded, meaning no
273 process's context is loaded.
274
275 2.2 Here's how it is done now:
276 ---------------------------
277 We try to proactively leave, but have the ability to stay in context til
278 proc_startcore() to handle the corner cases (and to maybe cut down the TLB
279 flushes later).  To stop proactively leaving, just change abandon_core() to not
280 do anything with current/cr3.  You'll see weird things like processes that won't
281 die until their old cores are reused.  The reason we proactively leave context
282 is to help with sanity for these issues, and also to avoid decref's in
283 __startcore().
284
285 A couple other details: __startcore() sorts the extra increfs, and
286 proc_startcore() sorts leaving the old context.  Anytime a __startcore active
287 message is sent, the sender increfs in advance for the current refcnt.  If that
288 was in error, __startcore decrefs.  proc_startcore(), which the last moment
289 before we *must* have the cr3/current issues sorted, does the actual check if
290 there was an old process there or not, while it handles the lcr3 (if necessary).
291 In general, lcr3's ought to have refcnts near them, or else comments explaining
292 why not.
293
294 So we leave process context when told to do so (__death/abandon_core()) or if
295 another process is run there.  The _M code is such that a proc will stay on its
296 core until it receives a message, and that message would cleanup/restore a
297 generic context (boot_cr3).  A _S could stay on its core until another _S came
298 in.  This is much simpler for cases when a timer interrupt goes off to force a
299 schedule() decision.  It also avoids a TLB flush in case the scheduler picked
300 that same proc to run again.  This could also happen to an _M, if for some
301 reason it was given a management core (!!!) or some other event happened that
302 caused some management/scheduling function to run on one of it's cores (perhaps
303 it asked).
304
305 proc_yield() abandons the core / leaves context.
306
307 2.3 Other issues:
308 ---------------------------
309 Note that dealing with interrupting
310 processes that are in the kernel is tricky.  There is no true process context, so we can't
311 leave a core until the kernel is in a "safe place", i.e. it's state is bundled
312 enough that it can be recontinued later.  Calls of this type are not immediate
313 active messages, executed at a convenient time (specifically, before we return
314 to userspace in proc_startcore().
315
316 This same thing applies to __death messages.  Even though a process is dying, it
317 doesn't mean we can just drop whatever the kernel was doing on its behalf.  For
318 instance, it might be holding a reference that will never get decreffed if its
319 stack gets dropped.
320
321 3. Leaving the Kernel Stack:
322 ===========================
323 Just because a message comes in saying to kill a process, it does not mean we
324 should immediately abandon_core().  The problem is more obvious when there is
325 a preempt message, instead of a death message, but either way there is state
326 that needs cleaned up (refcnts that need downed, etc).
327
328 The solution to this is rather simple: don't abandon right away.  That was
329 always somewhat the plan for preemption, but was never done for death.  And
330 there are several other cases to worry about too.  To enforce this, we expand
331 the active messages into a generic work execution message that can be delayed
332 or shipped to another core.  These types of messages will not be executed
333 immediately on the receiving pcore - instead they are on the queue for "when
334 there's nothing else to do in the kernel", which is checked in smp_idle() and
335 before returning to userspace in proc_startcore().  Additionally, these active
336 messages can also be queued on an alarm queue, delaying their activation as
337 part of a generic kernel alarm facility.
338
339 4. Preemption and Notification Issues:
340 ===========================
341 4.1: Message Ordering and Local Calls:
342 ---------------------------
343 Since we go with the model of cores being told what to do, there are issues
344 with messages being received in the wrong order.  That is why we have the
345 active messages (guaranteed, in-order delivery), with the proc-lock protecting
346 the send order.  However, this is not enough for some rare races.
347
348 Local calls can also perform the same tasks as messages (calling
349 proc_destroy() while a death IPI is on its way). We refer to these calls as
350 messing with "local fate" (compared to global state (we're clever).
351 Preempting a single vcore doesn't change the process's state).  These calls
352 are a little different, because they also involve a check to see if it should
353 perform the function or other action (e.g., death just idling and waiting for
354 an IPI instead of trying to kill itself), instead of just blindly doing
355 something.
356
357 4.1.1: Possible Solutions
358 ----------------
359 There are two ways to deal with this.  One (and the better one, I think) is to
360 check state, and determine if it should proceed or abort.  This requires that
361 all local-fate dependent calls always have enough state, meaning that any
362 function that results in sending a directive to a vcore store enough info in
363 the proc struct that a local call can determine if it should take action or
364 abort.  This might be sufficient.  This works for death already, since you
365 aren't supposed to do anything other than die (and restore any invariants
366 first, handled in Section 3).  We'll go with this way.
367
368 The other way is to send the work (including the checks) in a self-ipi active
369 message.  This will guarantee that the message is executed after any existing
370 messages (making the a_msg queue the authority for what should happen to a
371 core).  The check is also performed later (when the a_msg executes).  There
372 are a couple issues with this: if we allow the local core to send itself an
373 a_msg that could be out of order (meaning it should not be sent, and is only
374 sent due to ignorance of its sealed fate), AND if we return the core to the
375 idle-core-list once its fate is sealed, we need to detect that the message is
376 for the wrong process and that the process is in the wrong state.  To do this,
377 we probably need local versioning on the pcore so it can detect that the
378 message is late/wrong.  We might get by with just the proc* (though that is
379 tricky with death and proc reuse), so long as we don't allow new startcores
380 for a proc until AFTER the preemption is completed.
381
382 4.2: Preempt-Served Flag
383 ----------------
384 We want to be able to consider a pcore free once its owning proc has dealt
385 with removing it (not necessarily taken from the vcoremap, but at least it is
386 a done-deal that the core will go away and the messages are sent).  This
387 allows a scheduler-like function to easily take a core and then give it to
388 someone else, without waiting for each vcore to respond, saying that the pcore
389 is free/idle.
390
391 Since we want to keep the pcore in the vcoremap, we need another signal to let
392 a process know a message is already on its way.  preempt_pending is a signal
393 to userspace that the alarm was set, not that an actual message is on its way
394 and that a vcore's fate is sealed.  Since we can't use a pcore's presence in
395 the vcoremap to determine that the core should be revoked, we have to check
396 the "fate sealed"/preempt-served flag. 
397
398 It's a bit of a pain to have this flag, just to resolve this race in the
399 kernel, though the local call would have to check the vcoremap anyway,
400 incurring a cache miss if we go with using the vcoremap to signal the
401 impending message.
402
403 The preempt_pending flag is actual a timestamp, with the expiration time of
404 the core at which the message will be sent.  We could try to use that, but
405 since alarms aren't fired at exactly the time they are scheduled, the message
406 might not actually be sent yet (though it will, really soon).  Still, we'll
407 just go with the preempt-served flag for now.
408
409 4.3: Impending Notifications
410 ----------------
411 It's also possible that there is an impending notification.  There's no change
412 in fate (though there could be a fate-changing preempt on its way), just the
413 user wants a notification handler to run.  We need a flag anyways for this
414 (discussed below), so proc_yield() or whatever other local call we have can
415 check this flag as well.  
416
417 Though for proc_yield(), it doesn't care if a notification is on its way (can
418 be dependent on a flag to yield from userspace, based on the nature of the
419 yield (which still needs to be sorted)).  If the yield is in response to a
420 preempt_pending, it actually should yield and not receive the notification.
421 So it should destroy its vcoreid->pcoreid mapping and abandon_core().  When
422 that notification hits, it will be for a proc that isn't current, and will be
423 ignored (it will get run the next time that vcore fires up, handled below).
424
425 There is a slight chance that the same proc will run on that pcore, but with a
426 different vcore.  In the off chance this happens, the new vcore will get a
427 spurious notification.  Userspace needs to be able to handle spurious
428 notifications anyways, (there are a couple other cases, and in general it's
429 not hard to do), so this is not a problem.  Instead of trying to have the
430 kernel ignore the notification, we just send a spurious one.  A crappy
431 alternative would be to send the vcoreid with the notification, but that would
432 mean we can't send a generic message (broadcast) to a bunch of cores, which
433 will probably be a problem later.
434
435 Note that this specific case is because the "local work message" gets
436 processed out of order with respect to the notification.  And we want this in
437 that case, since that proc_yield() is more important than the notification.
438
439 4.4: Preemption / Allocation Phases and Alarm Delays
440 ---------------------------
441 A per-vcore preemption phase starts when the kernel marks the core's
442 preempt_pending flag/counter and can includes the time when an alarm is
443 waiting to go off to reclaim the core.  The phase ends when the vcore's pcore
444 is reclaimed, either as a result of the kernel taking control, or because a
445 process voluntarily yielded.
446
447 Specifically, the preempt_pending variable is actually a timestamp for when
448 the core will be revoked (this assumes some form of global time, which we need
449 anyways).  If its value is 0, then there is no preempt-pending, it is not in a
450 phase, and the vcore can be given out again. 
451
452 When a preempt alarm goes off, the alarm only means to check a process for
453 expired vcores.  If the vcore has been yielded while the alarm was pending,
454 the preempt_pending flag will be reset to 0.  To speed up the search for
455 vcores to preempt, there's a circular buffer corelist in the proc struct, with
456 vcoreids of potential suspects.  Or at least this will exist at some point.
457 Also note that the preemption list isn't bound to a specific alarm: you can
458 check the list at any time (not necessarily on a specific alarm), and you can
459 have spurious alarms (the list is empty, so it'll be a noop).
460
461 Likewise, a global preemption phase is when an entire MCP is getting
462 gang_prempted, and the global deadline is set.  A function can quickly check
463 to see if the process responded, since the list of vcores with preemptions
464 pending will be empty.
465
466 It seems obvious, but we do not allow allocation of a vcore during its
467 preemption phase.  The main reason is that it can potentially break
468 assumptions about the vcore->pcore mapping and can result in multiple
469 instances of the same vcore on different pcores.  Imagine a preempt message
470 sent to a pcore (after the alarm goes off), meanwhile that vcore/pcore yields
471 and the vcore reactivates somewhere else.  There is a potential race on the
472 preempt_tf state: the new vcore is reading while the old is writing.  This
473 issue is sorted naturally: the vcore entry in the vcoremap isn't cleared until
474 the vcore/pcore is actually yielded/taken away, so the code looking for a free
475 vcoreid slot will not try to use it.
476
477 Note that if we didn't design the alarm system to simply check for
478 preemptions (perhaps it has a stored list of vcores to preempt), then we
479 couldn't end the preempt-phase until the alarm was sorted.  If that is the
480 case, we could easily give out a vcore that had been yielded but was still in
481 a preempt-phase.  Stopping an alarm would be tricky too, since there could be
482 lots of vcores in different states that need to be sorted by the alarm (so
483 ripping it out isn't enough).  Setting a flag might not be enough either.
484 Vcore version numbers/history (as well as global proc histories) is a pain I'd
485 like to avoid too.  So don't change the alarm / delayed preemption system
486 without thinking about this.
487
488 Also, allowing a vcore to restart while preemptions are pending also mucks
489 with keeping the vcore mapping "old" (while the message is in flight).  A
490 pcore will want to use that to determine which vcore is running on it.  It
491 would be possible to keep a pcoremap for the reverse mapping out of sync, but
492 that seems like a bad idea.  In general, having the pcoremap is a good idea
493 (whenever we talk about a vcoremap, we're usually talking about both
494 directions: "the vcore->pcore mapping").
495
496 4.5: Global Preemption Flags
497 ---------------------------
498 If we are trying to preempt an entire process at the same time, instead of
499 playing with the circular buffer of vcores pending preemption, we could have a
500 global timer as well.  This avoids some O(n) operations, though it means that
501 userspace needs to check two "flags" (expiration dates) when grabbing its
502 preempt-critical locks.
503
504 4.6: Notifications Mixed with Preemption and Sleeping
505 ---------------------------
506 It is possible that notifications will mix with preemptions or come while a
507 process is not running.  Ultimately, the process wants to be notified on a
508 given vcore.  Whenever we send an active notification, we set a flag in
509 procdata.  If the vcore is offline or is in a preempt-phase, we don't bother
510 sending the IPI/notif message.  The kernel will make sure it runs the
511 notification handler (as well as restoring the preempt_tf) the next time that
512 vcore is restarted.  Note that userspace can toggle this, so they can handle
513 the notifications from a different core if it likes, or they can independently
514 send a notification.
515  
516 4.7: Notifs While a Preempt Message is Served
517 ---------------------------
518 It is possible to have the kernel handling a notification a_msg and to have a
519 preempt a_msg in the queue (preempt-served flag is set).  Ultimately, what we
520 want is for the core to be preempted and the notification handler to run on
521 the next execution.  Both messages are in the a_msg queue for "a convenient
522 time to leave the kernel" (I'll have a better name for that later).  What we
523 do is execute the notification handler and jump to userspace.  Since there is
524 still an a_msg in the queue (and we self_ipi'd ourselves, it's part of how
525 a_msgs work), the IPI will fire and push us right back into the kernel to
526 execute the preemption, and the notif handler's context will be saved in the
527 preempt_tf (ready to go when the vcore gets started again).
528
529 We could try to just set the notif_pending flag and ignore the message, but
530 that would involve inspecting the queue for the preempt a_msg.  Additionally,
531 a preempt a_msg can arrive anyway.  Finally, it's possible to have another
532 message in the queue between the notif and the preempt, and it gets ugly
533 quickly trying to determine what to do.
534
535 4.8: When a Pcore is "Free"
536 ---------------------------
537 There are a couple ways to handle pcores.  One approach would be to not
538 consider them free and able to be given to another process until the old
539 process is completely removed (abandon_core()).  Another approach is to free
540 the core once its fate is sealed (which we do).  This probably gives more
541 flexibility in schedule()-like functions (no need to wait to give the core
542 out), quicker dispatch latencies, less contention on shared structs (like the
543 idle-core-map), etc.
544
545 Also, we don't remove the pcore from the vcoremap, even if it is being
546 allocated to another core (the same pcore can exist in two vcoremaps, contrary
547 to older statements).  Taking the pcore from the vcoremap would mean some
548 non-fate related local calls (sys_get_vcoreid()) will fail, since the vcoreid
549 is gone!  Additionally, we don't need a vcoreid in the a_msg (we would have if
550 we could not use the vcore/pcoremappings).  There should not be any issues
551 with the new process sending messages to the pcore before the core is sorted,
552 since a_msgs are delivered in order.
553
554 Another tricky part is the seq_ctr used to signal userspace of changes to the
555 coremap or num_vcores (coremap_seqctr).  While we may not even need this in the
556 long run, it still seems like it could be useful.  The trickiness comes from
557 when we update the seq_ctr when we are unmapping vcores on the receive side of a
558 message (like __death or __preempt).  We'd rather not have each pcore contend on
559 the seq_ctr cache line (let alone any locking) while they perform a somewhat
560 data-parallel task.  So we continue to have the sending core handle the seq_ctr
561 upping and downing.  This works, since the "unlocking" happens after messages
562 are sent, which means the receiving core is no longer in userspace (if there is
563 a delay, it is because the remote core is in the kernel, possibly with
564 interrupts disabled).  Because of this, userspace will be unable to read the new
565 value of the seq_ctr before the IPI hits and does the unmapping that the seq_ctr
566 protects/advertises.  This is most likely true.  It wouldn't be if the "last IPI
567 was sent" flag clears before the IPI actually hit the other core.
568
569
570 4.9: Future Broadcast/Messaging Needs
571 ---------------------------
572 Currently, messaging is serialized.  Broadcast IPIs exist, but the active
573 message system is based on adding an a_msg to a list in a pcore's
574 per_cpu_info.  Further the sending of these messages is in a loop.  In the
575 future, we would like to have broadcast messaging of some sort (literally a
576 broadcast, like the IPIs, and if not that, then a communication tree of
577 sorts).  
578
579 Given those desires, we want to make sure that no message we send needs
580 details specific to a pcore (such as the vcoreid running on it, a history
581 number, or anything like that).  Thus no a_msg related to process management
582 should have anything that cannot apply to the entire process.  At this point,
583 most just have a struct proc *.  A pcore ought to be able to figure out what
584 is happening based on the pcoremap, information in the struct proc, and in the
585 preempt struct in procdata.
586
587 4.10: Other Things We Thought of but Don't Like
588 ---------------------------
589 All local fate-related work is sent as a self a_msg, to enforce ordering.
590 It doesn't capture the difference between a local call and a remote a_msg.
591 The a_msg has already considered state and made its decision.  The local call
592 is an attempt.  It is also unnecessary, if we put in enough information to
593 make a decision in the proc struct.  Finally, it caused a few other problems
594 (like needing to detect arbitrary stale messages).
595
596 Overall message history: doesn't work well when you do per-core stuff, since
597 it will invalidate other messages for the process.  We then though of a pcore
598 history counter to detect stale messages.  Don't like that either.  We'd have
599 to send the history in the message, since it's a per-message, per-core
600 expiration.  There might be other ways around this, but this doesn't seem
601 necessary.
602
603 Alarms have pointers to a list of which cores should be preempted when that
604 specific alarm goes off (saved with the alarm).  Ugh.  It gets ugly with
605 multiple outstanding preemptions and cores getting yielded while the alarms
606 sleep (and possibly could get reallocated, though we'd make a rule to prevent
607 that).  Like with notifications, being able to handle spurious alarms and
608 thinking of an alarm as just a prod to check somewhere is much more flexible
609 and simple.  It is similar to generic messages that have the actual important
610 information stored somewhere else (as with allowing broadcasts, with different
611 receivers performing slightly different operations).
612
613 Synchrony for messages (wanting a response to a preempt a_msg, for example)
614 sucks.  Just encode the state of impending fate in the proc struct, where it
615 belongs.  Additionally, we don't want to hold the proc lock even longer than
616 we do now (which is probably too long as it is).  Finally, it breaks a golden
617 rule: never wait while holding a lock: you will deadlock the system (e.g. if
618 the receiver is already in the kernel spinning on the lock).  We'd have to
619 send messages, unlock (which might cause a message to hit the calling pcore,
620 as in the case of locally called proc_destroy()), and in the meantime some
621 useful invariant might be broken.
622
623 We also considered using the transition stack as a signal that a process is in
624 a notification handler.  The kernel can inspect the stack pointer to determine
625 this.  It's possible, but unnecessary.
626
627 5. TBD
628 ===========================