2bb53388e690bd66a0a3ed383b9e6c08037747b4
[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. current_ctx and owning_proc
15 6. Locking!
16 7. TLB Coherency
17 8. Process Management
18 9. On the Ordering of Messages
19 10. TBD
20
21 1. Reference Counting
22 ===========================
23 1.1 Basics:
24 ---------------------------
25 Reference counts exist to keep a process alive.  We use krefs for this, similar
26 to Linux's kref:
27 - Can only incref if the current value is greater than 0, meaning there is
28   already a reference to it.  It is a bug to try to incref on something that has
29   no references, so always make sure you incref something that you know has a
30   reference.  If you don't know, you need to get it from pid2proc (which is a
31   careful way of doing this - pid2proc kref_get_not_zero()s on the reference that is
32   stored inside it).  If you incref and there are 0 references, the kernel will
33   panic.  Fix your bug / don't incref random pointers.
34 - Can always decref.
35 - When the decref returns 0, perform some operation.  This does some final
36   cleanup on the object.
37 - Process code is trickier since we frequently make references from 'current'
38   (which isn't too bad), but also because we often do not return and need to be
39   careful about the references we passed in to a no-return function.
40
41 1.2 Brief History of the Refcnt:
42 ---------------------------
43 Originally, the refcnt was created to keep page tables from being destroyed (in
44 proc_free()) while cores were still using them, which is what was happens during
45 an ARSC (async remote syscall).  It was then defined to be a count of places in
46 the kernel that had an interest in the process staying alive, practically just
47 to protect current/cr3.  This 'interest' actually extends to any code holding a
48 pointer to the proc, such as one acquired via pid2proc(), which is its current
49 meaning.
50
51 1.3 Quick Aside: The current Macro:
52 ---------------------------
53 current is a pointer to the proc that is currently loaded/running on any given
54 core.  It is stored in the per_cpu_info struct, and set/managed by low-level
55 process code.  It is necessary for the kernel to quickly figure out who is
56 running on its core, especially when servicing interrupts and traps.  current is
57 protected by a refcnt.
58
59 current does not say which process owns / will-run on a core.  The per-cpu
60 variable 'owning_proc' covers that.  'owning_proc' should be treated like
61 'current' (aka, 'cur_proc') when it comes to reference counting.  Like all
62 refcnts, you can use it, but you can't consume it without atomically either
63 upping the refcnt or passing the reference (clearing the variable storing the
64 reference).  Don't pass it to a function that will consume it and not return
65 without upping it.
66
67 1.4 Reference Counting Rules:
68 ---------------------------
69 +1 for existing.
70 - The fact that the process is supposed to exist is worth +1.  When it is time
71   to die, we decref, and it will eventually be cleaned up.  This existence is
72   explicitly kref_put()d in proc_destroy().
73 - The hash table is a bit tricky.  We need to kref_get_not_zero() when it is
74   locked, so we know we aren't racing with proc_free freeing the proc and
75   removing it from the list.  After removing it from the hash, we don't need to
76   kref_put it, since it was an internal ref.  The kref (i.e. external) isn't for
77   being on the hash list, it's for existing.  This separation allows us to
78   remove the proc from the hash list in the "release" function.  See kref.txt
79   for more details.
80
81 +1 for someone using it or planning to use it.
82 - This includes simply having a pointer to the proc, since presumably you will
83   use it.  pid2proc() will incref for you.  When you are done, decref.
84 - Functions that create a process and return a pointer (like proc_create() or
85   kfs_proc_create()) will also up the refcnt for you.  Decref when you're done.
86 - If the *proc is stored somewhere where it will be used again, such as in an IO
87   continuation, it needs to be refcnt'd.  Note that if you already had a
88   reference from pid2proc(), simply don't decref after you store the pointer.
89
90 +1 for current.
91 - current counts as someone using it (expressing interest in the core), but is
92   also a source of the pointer, so its a bit different.  Note that all kref's
93   are sources of a pointer.  When we are running on a core that has current
94   loaded, the ref is both for its usage as well as for being the current
95   process.
96 - You have a reference from current and can use it without refcnting, but
97   anything that needs to eat a reference or store/use it needs an incref first.
98   To be clear, your reference is *NOT* edible.  It protects the cr3, guarantees
99   the process won't die, and serves as a bootstrappable reference.
100 - Specifically, if you get a ref from current, but then save it somewhere (like
101   an IO continuation request), then clearly you must incref, since it's both
102   current and stored/used.
103 - If you don't know what might be downstream from your function, then incref
104   before passing the reference, and decref when it returns.  We used to do this
105   for all syscalls, but now only do it for calls that might not return and
106   expect to receive reference (like proc_yield).
107
108 All functions that take a *proc have a refcnt'd reference, though it may not be
109 edible (it could be current).  It is the callers responsibility to make sure
110 it'd edible if it necessary.  It is the callees responsibility to incref if it
111 stores or makes a copy of the reference.
112
113 1.5 Functions That Don't or Might Not Return:
114 ---------------------------
115 Refcnting and especially decreffing gets tricky when there are functions that
116 MAY not return.  proc_restartcore() does not return (it pops into userspace).
117 proc_run() used to not return, if the core it was called on would pop into
118 userspace (if it was a _S, or if the core is part of the vcoremap for a _M).
119 This doesn't happen anymore, since we have cur_ctx in the per-cpu info.
120
121 Functions that MAY not return will "eat" your reference *IF* they do not return.
122 This means that you must have a reference when you call them (like always), and
123 that reference will be consumed / decref'd for you if the function doesn't
124 return.  Or something similarly appropriate.
125
126 Arguably, for functions that MAY not return, but will always be called with
127 current's reference (proc_yield()), we could get away without giving it an
128 edible reference, and then never eating the ref.  Yield needs to be reworked
129 anyway, so it's not a bit deal yet.
130
131 We do this because when the function does not return, you will not have the
132 chance to decref (your decref code will never run).  We need the reference when
133 going in to keep the object alive (like with any other refcnt).  We can't have
134 the function always eat the reference, since you cannot simply re-incref the
135 pointer (not allowed to incref unless you know you had a good reference).  You'd
136 have to do something like p = pid2proc(p_pid);  It's clunky to do that, easy to
137 screw up, and semantically, if the function returns, then we may still have an
138 interest in p and should decref later.
139
140 The downside is that functions need to determine if they will return or not,
141 which can be a pain (for an out-of-date example: a linear time search when
142 running an _M, for instance, which can suck if we are trying to use a
143 broadcast/logical IPI).
144
145 As the caller, you usually won't know if the function will return or not, so you
146 need to provide a consumable reference.  Current doesn't count.  For example,
147 proc_run() requires a reference.  You can proc_run(p), and use p afterwards, and
148 later decref.  You need to make sure you have a reference, so things like
149 proc_run(pid2proc(55)) works, since pid2proc() increfs for you.  But you cannot
150 proc_run(current), unless you incref current in advance.  Incidentally,
151 proc_running current doesn't make a lot of sense.
152
153 1.6 Runnable List:
154 ---------------------------
155 Procs on the runnable list need to have a refcnt (other than the +1 for
156 existing).  It's something that cares that the process exists.  We could have
157 had it implicitly be refcnt'd (the fact that it's on the list is enough, sort of
158 as if it was part of the +1 for existing), but that complicates things.  For
159 instance, it is a source of a reference (for the scheduler) and you could not
160 proc_run() a process from the runnable list without worrying about increfing it
161 before hand.  This isn't true anymore, but the runnable lists are getting
162 overhauled anyway.  We'll see what works nicely.
163
164 1.7 Internal Details for Specific Functions:
165 ---------------------------
166 proc_run()/__proc_give_cores(): makes sure enough refcnts are in place for all
167 places that will install owning_proc.  This also makes it easier on the system
168 (one big incref(n), instead of n increfs of (1) from multiple cores). 
169
170 __set_proc_current() is a helper that makes sure p is the cur_proc.  It will
171 incref if installing a new reference to p.  If it removed an old proc, it will
172 decref.
173
174 __proc_startcore(): assumes all references to p are sorted.  It will not
175 return, and you should not pass it a reference you need to decref().  Passing
176 it 'owning_proc' works, since you don't want to decref owning_proc.
177
178 proc_destroy(): it used to not return, and back then if your reference was
179 from 'current', you needed to incref.  Now that proc_destroy() returns, it
180 isn't a big deal.  Just keep in mind that if you have a function that doesn't
181 return, there's no way for the function to know if it's passed reference is
182 edible.  Even if p == current, proc_destroy() can't tell if you sent it p (and
183 had a reference) or current and didn't.
184
185 proc_yield(): when this doesn't return, it eats your reference.  It will also
186 decref twice.  Once when it clears_owning_proc, and again when it calls
187 abandon_core() (which clears cur_proc).
188
189 abandon_core(): it was not given a reference, so it doesn't eat one.  It will
190 decref when it unloads the cr3.  Note that this is a potential performance
191 issue.  When preempting or killing, there are n cores that are fighting for the
192 cacheline to decref.  An alternative would be to have one core decref for all n
193 cores, after it knows all cores unloaded the cr3.  This would be a good use of
194 the checklist (possibly with one cacheline per core).  It would take a large
195 amount of memory for better scalability.
196
197 1.8 Things I Could Have Done But Didn't And Why:
198 ---------------------------
199 Q: Could we have the first reference (existence) mean it could be on the runnable
200 list or otherwise in the proc system (but not other subsystems)?  In this case,
201 proc_run() won't need to eat a reference at all - it will just incref for every
202 current it will set up.
203
204 New A: Maybe, now that proc_run() returns.
205
206 Old A: No: if you pid2proc(), then proc_run() but never return, you have (and
207 lose) an extra reference.  We need proc_run() to eat the reference when it
208 does not return.  If you decref between pid2proc() and proc_run(), there's a
209 (rare) race where the refcnt hits 0 by someone else trying to kill it.  While
210 proc_run() will check to see if someone else is trying to kill it, there's a
211 slight chance that the struct will be reused and recreated.  It'll probably
212 never happen, but it could, and out of principle we shouldn't be referencing
213 memory after it's been deallocated.  Avoiding races like this is one of the
214 reasons for our refcnt discipline.
215
216 Q: (Moot) Could proc_run() always eat your reference, which would make it
217 easier for its implementation?
218
219 A: Yeah, technically, but it'd be a pain, as mentioned above.  You'd need to
220 reaquire a reference via pid2proc, and is rather easy to mess up.
221
222 Q: (Moot) Could we have made proc_destroy() take a flag, saying whether or not
223 it was called on current and needed a decref instead of wasting an incref?
224
225 A: We could, but won't.  This is one case where the external caller is the one
226 that knows the function needs to decref or not.  But it breaks the convention a
227 bit, doesn't mirror proc_create() as well, and we need to pull in the cacheline
228 with the refcnt anyways.  So for now, no.
229
230 Q: (Moot) Could we make __proc_give_cores() simply not return if an IPI is
231 coming?
232
233 A: I did this originally, and manually unlocked and __wait_for_ipi()d.  Though
234 we'd then need to deal with it like that for all of the related functions, which
235 doesn't work if you wanted to do something afterwards (like schedule(p)).  Also
236 these functions are meant to be internal helpers, so returning the bool makes
237 more sense.  It eventually led to having __proc_unlock_ipi_pending(), which made
238 proc_destroy() much cleaner and helped with a general model of dealing with
239 these issues.  Win-win.
240
241 2. When Do We Really Leave "Process Context"?
242 ===========================
243 2.1 Overview
244 ---------------------------
245 First off, it's not really "process context" in the way Linux deals with it.  We
246 aren't operating in kernel mode on behalf of the process (always).  We are
247 specifically talking about when a process's cr3 is loaded on a core.  Usually,
248 current is also set (the exception for now is when processing ARSCs).
249
250 There are a couple different ways to do this.  One is to never unload a context
251 until something new is being run there (handled solely in __proc_startcore()).
252 Another way is to always explicitly leave the core, like by abandon_core()ing.
253
254 The issue with the former is that you could have contexts sitting around for a
255 while, and also would have a bit of extra latency when __proc_free()ing during
256 someone *else's* __proc_startcore() (though that could be avoided if it becomes
257 a real issue, via some form of reaping).  You'll also probably have excessive
258 decrefs (based on the interactions between proc_run() and __startcore()).
259
260 The issue with the latter is excessive TLB shootdowns and corner cases.  There
261 could be some weird cases (in core_request() for example) where the core you are
262 running on has the context loaded for proc A on a mgmt core, but decides to give
263 it to proc B.
264
265 If no process is running there, current == 0 and boot_cr3 is loaded, meaning no
266 process's context is loaded.
267
268 All changes to cur_proc, owning_proc, and cur_ctx need to be done with
269 interrupts disabled, since they change in interrupt handlers.
270
271 2.2 Here's how it is done now:
272 ---------------------------
273 All code is capable of 'spamming' cur_proc (with interrupts disabled!).  If it
274 is 0, feel free to set it to whatever process you want.  All code that
275 requires current to be set will do so (like __proc_startcore()).  The
276 smp_idle() path will make sure current is clear when it halts.  So long as you
277 don't change other concurrent code's expectations, you're okay.  What I mean
278 by that is you don't clear cur_proc while in an interrupt handler.  But if it
279 is already 0, __startcore is allowed to set it to it's future proc (which is
280 an optimization).  Other code didn't have any expectations of it (it was 0).
281 Likewise, kthread code when we sleep_on() doesn't have to keep cur_proc set.
282 A kthread is somewhat an isolated block (codewise), and leaving current set
283 when it is done is solely to avoid a TLB flush (at the cost of an incref).
284
285 In general, we try to proactively leave process context, but have the ability
286 to stay in context til __proc_startcore() to handle the corner cases (and to
287 maybe cut down the TLB flushes later).  To stop proactively leaving, just
288 change abandon_core() to not do anything with current/cr3.  You'll see weird
289 things like processes that won't die until their old cores are reused.  The
290 reason we proactively leave context is to help with sanity for these issues,
291 and also to avoid decref's in __startcore().
292
293 A couple other details: __startcore() sorts the extra increfs, and
294 __proc_startcore() sorts leaving the old context.  Anytime a __startcore kernel
295 message is sent, the sender increfs in advance for the owning_proc refcnt.  As
296 an optimization, we can also incref to *attempt* to set current.  If current
297 was 0, we set it.  If it was already something else, we failed and need to
298 decref.  __proc_startcore(), which the last moment before we *must* have the
299 cr3/current issues sorted, does the actual check if there was an old process
300 there or not, while it handles the lcr3 (if necessary).  In general, lcr3's
301 ought to have refcnts near them, or else comments explaining why not.
302
303 So we leave process context when told to do so (__death/abandon_core()) or if
304 another process is run there.  The _M code is such that a proc will stay on its
305 core until it receives a message, and that message would cleanup/restore a
306 generic context (boot_cr3).  A _S could stay on its core until another _S came
307 in.  This is much simpler for cases when a timer interrupt goes off to force a
308 schedule() decision.  It also avoids a TLB flush in case the scheduler picked
309 that same proc to run again.  This could also happen to an _M, if for some
310 reason it was given a management core (!!!) or some other event happened that
311 caused some management/scheduling function to run on one of it's cores (perhaps
312 it asked).
313
314 proc_yield() abandons the core / leaves context.
315
316 2.3 Other issues:
317 ---------------------------
318 Note that dealing with interrupting processes that are in the kernel is tricky.
319 There is no true process context, so we can't leave a core until the kernel is
320 in a "safe place", i.e. it's state is bundled enough that it can be recontinued
321 later.  Calls of this type are routine kernel messages, executed at a convenient
322 time (specifically, before we return to userspace in proc_restartcore().
323
324 This same thing applies to __death messages.  Even though a process is dying, it
325 doesn't mean we can just drop whatever the kernel was doing on its behalf.  For
326 instance, it might be holding a reference that will never get decreffed if its
327 stack gets dropped.
328
329 3. Leaving the Kernel Stack:
330 ===========================
331 Just because a message comes in saying to kill a process, it does not mean we
332 should immediately abandon_core().  The problem is more obvious when there is
333 a preempt message, instead of a death message, but either way there is state
334 that needs cleaned up (refcnts that need downed, etc).
335
336 The solution to this is rather simple: don't abandon right away.  That was
337 always somewhat the plan for preemption, but was never done for death.  And
338 there are several other cases to worry about too.  To enforce this, we expand
339 the old "active messages" into a generic work execution message (a kernel
340 message) that can be delayed or shipped to another core.  These types of
341 messages will not be executed immediately on the receiving pcore - instead they
342 are on the queue for "when there's nothing else to do in the kernel", which is
343 checked in smp_idle() and before returning to userspace in proc_restartcore().
344 Additionally, these kernel messages can also be queued on an alarm queue,
345 delaying their activation as part of a generic kernel alarm facility.
346
347 One subtlety is that __proc_startcore() shouldn't check for messages, since it
348 is called by __startcore (a message).  Checking there would run the messages out
349 of order, which is exactly what we are trying to avoid (total chaos).  No one
350 should call __proc_startcore, other than proc_restartcore() or __startcore().
351 If we ever have functions that do so, if they are not called from a message,
352 they must check for outstanding messages.
353
354 This last subtlety is why we needed to change proc_run()'s _S case to use a
355 local message instead of calling proc_starcore (and why no one should ever call
356 proc_startcore()).  We could unlock, thereby freeing another core to change the
357 proc state and send a message to us, then try to proc_startcore, and then
358 reading the message before we had installed current or had a userspace TF to
359 preempt, and probably a few other things.  Treating _S as a local message is
360 cleaner, begs to be merged in the code with _M's code, and uses the messaging
361 infrastructure to avoid all the races that it was created to handle.
362
363 Incidentally, we don't need to worry about missing messages while trying to pop
364 back to userspace from __proc_startcore, since an IPI will be on the way
365 (possibly a self-ipi caused by the __kernel_message() handler).  This is also
366 why we needed to make process_routine_kmsg() keep interrupts disabled when it
367 stops (there's a race between checking the queue and disabling ints).
368
369 4. Preemption and Notification Issues:
370 ===========================
371 4.1: Message Ordering and Local Calls:
372 ---------------------------
373 Since we go with the model of cores being told what to do, there are issues
374 with messages being received in the wrong order.  That is why we have the
375 kernel messages (guaranteed, in-order delivery), with the proc-lock protecting
376 the send order.  However, this is not enough for some rare races.
377
378 Local calls can also perform the same tasks as messages (calling
379 proc_destroy() while a death IPI is on its way). We refer to these calls as
380 messing with "local fate" (compared to global state (we're clever).
381 Preempting a single vcore doesn't change the process's state).  These calls
382 are a little different, because they also involve a check to see if it should
383 perform the function or other action (e.g., death just idling and waiting for
384 an IPI instead of trying to kill itself), instead of just blindly doing
385 something.
386
387 4.1.1: Possible Solutions
388 ----------------
389 There are two ways to deal with this.  One (and the better one, I think) is to
390 check state, and determine if it should proceed or abort.  This requires that
391 all local-fate dependent calls always have enough state to do its job.  In the
392 past, this meant that any function that results in sending a directive to a
393 vcore store enough info in the proc struct that a local call can determine if
394 it should take action or abort.  In the past, we used the vcore/pcoremap as a
395 way to send info to the receiver about what vcore they are (or should be).
396 Now, we store that info in pcpui (for '__startcore', we send it as a
397 parameter.  Either way, the general idea is still true: local calls can
398 proceed when they are called, and not self-ipi'd to a nebulous later time.
399
400 The other way is to send the work (including the checks) in a self-ipi kernel
401 message.  This will guarantee that the message is executed after any existing
402 messages (making the k_msg queue the authority for what should happen to a
403 core).  The check is also performed later (when the k_msg executes).  There
404 are a couple issues with this: if we allow the local core to send itself an
405 k_msg that could be out of order (meaning it should not be sent, and is only
406 sent due to ignorance of its sealed fate), AND if we return the core to the
407 idle-core-list once its fate is sealed, we need to detect that the message is
408 for the wrong process and that the process is in the wrong state.  To do this,
409 we probably need local versioning on the pcore so it can detect that the
410 message is late/wrong.  We might get by with just the proc* (though that is
411 tricky with death and proc reuse), so long as we don't allow new startcores
412 for a proc until AFTER the preemption is completed.
413
414 4.2: Preempt-Served Flag
415 ----------------
416 We want to be able to consider a pcore free once its owning proc has dealt
417 with removing it.  This allows a scheduler-like function to easily take a core
418 and then give it to someone else, without waiting for each vcore to respond,
419 saying that the pcore is free/idle.
420
421 We used to not unmap until we were in '__preempt' or '__death', and we needed
422 a flag to tell yield-like calls that a message was already on the way and to
423 not rely on the vcoremap.  This is pretty fucked up for a number of reasons,
424 so we changed that.  But we still wanted to know when a preempt was in
425 progress so that the kernel could avoid giving out the vcore until the preempt
426 was complete.
427
428 Here's the scenario: we send a '__startcore' to core 3 for VC5->PC3.  Then we
429 quickly send a '__preempt' to 3, and then a '__startcore' to core 4 (a
430 different pcore) for VC5->PC4.  Imagine all of this happens before the first
431 '__startcore' gets processed (IRQ delay, fast ksched, whatever).  We need to
432 not run the second '__startcore' on pcore 4 before the preemption has saved
433 all of the state of the VC5.  So we spin on preempt_served (which may get
434 renamed to preempt_in_progress).  We need to do this in the sender, and not
435 the receiver (not in the kmsg), because the kmsgs can't tell which one they
436 are.  Specifically, the first '__startcore' on core 3 runs the same code as
437 the '__startcore' on core 4, working on the same vcore.  Anything we tell VC5
438 will be seen by both PC3 and PC4.  We'd end up deadlocking on PC3 while it
439 spins waiting for the preempt message that also needs to run on PC3.
440
441 The preempt_pending flag is actual a timestamp, with the expiration time of
442 the core at which the message will be sent.  We could try to use that, but
443 since alarms aren't fired at exactly the time they are scheduled, the message
444 might not actually be sent yet (though it will, really soon).  Still, we'll
445 just go with the preempt-served flag for now.
446
447 4.3: Impending Notifications
448 ----------------
449 It's also possible that there is an impending notification.  There's no change
450 in fate (though there could be a fate-changing preempt on its way), just the
451 user wants a notification handler to run.  We need a flag anyways for this
452 (discussed below), so proc_yield() or whatever other local call we have can
453 check this flag as well.  
454
455 Though for proc_yield(), it doesn't care if a notification is on its way (can
456 be dependent on a flag to yield from userspace, based on the nature of the
457 yield (which still needs to be sorted)).  If the yield is in response to a
458 preempt_pending, it actually should yield and not receive the notification.
459 So it should destroy its vcoreid->pcoreid mapping and abandon_core().  When
460 that notification hits, it will be for a proc that isn't current, and will be
461 ignored (it will get run the next time that vcore fires up, handled below).
462
463 There is a slight chance that the same proc will run on that pcore, but with a
464 different vcoreid.  In the off chance this happens, the new vcore will get a
465 spurious notification.  Userspace needs to be able to handle spurious
466 notifications anyways, (there are a couple other cases, and in general it's
467 not hard to do), so this is not a problem.  Instead of trying to have the
468 kernel ignore the notification, we just send a spurious one.  A crappy
469 alternative would be to send the vcoreid with the notification, but that would
470 mean we can't send a generic message (broadcast) to a bunch of cores, which
471 will probably be a problem later.
472
473 Note that this specific case is because the "local work message" gets
474 processed out of order with respect to the notification.  And we want this in
475 that case, since that proc_yield() is more important than the notification.
476
477 4.4: Preemption / Allocation Phases and Alarm Delays
478 ---------------------------
479 A per-vcore preemption phase starts when the kernel marks the core's
480 preempt_pending flag/counter and can includes the time when an alarm is
481 waiting to go off to reclaim the core.  The phase ends when the vcore's pcore
482 is reclaimed, either as a result of the kernel taking control, or because a
483 process voluntarily yielded.
484
485 Specifically, the preempt_pending variable is actually a timestamp for when
486 the core will be revoked (this assumes some form of global time, which we need
487 anyways).  If its value is 0, then there is no preempt-pending, it is not in a
488 phase, and the vcore can be given out again. 
489
490 When a preempt alarm goes off, the alarm only means to check a process for
491 expired vcores.  If the vcore has been yielded while the alarm was pending,
492 the preempt_pending flag will be reset to 0.  To speed up the search for
493 vcores to preempt, there's a circular buffer corelist in the proc struct, with
494 vcoreids of potential suspects.  Or at least this will exist at some point.
495 Also note that the preemption list isn't bound to a specific alarm: you can
496 check the list at any time (not necessarily on a specific alarm), and you can
497 have spurious alarms (the list is empty, so it'll be a noop).
498
499 Likewise, a global preemption phase is when an entire MCP is getting
500 gang_prempted, and the global deadline is set.  A function can quickly check
501 to see if the process responded, since the list of vcores with preemptions
502 pending will be empty.
503
504 It seems obvious, but we do not allow allocation of a vcore during its
505 preemption phase.  The main reason is that it can potentially break
506 assumptions about the vcore->pcore mapping and can result in multiple
507 instances of the same vcore on different pcores.  Imagine a preempt message
508 sent to a pcore (after the alarm goes off), meanwhile that vcore/pcore yields
509 and the vcore reactivates somewhere else.  There is a potential race on the
510 vcore_ctx state: the new vcore is reading while the old is writing.  This
511 issue is sorted naturally: the vcore entry in the vcoremap isn't cleared until
512 the vcore/pcore is actually yielded/taken away, so the code looking for a free
513 vcoreid slot will not try to use it.
514
515 Note that if we didn't design the alarm system to simply check for
516 preemptions (perhaps it has a stored list of vcores to preempt), then we
517 couldn't end the preempt-phase until the alarm was sorted.  If that is the
518 case, we could easily give out a vcore that had been yielded but was still in
519 a preempt-phase.  Stopping an alarm would be tricky too, since there could be
520 lots of vcores in different states that need to be sorted by the alarm (so
521 ripping it out isn't enough).  Setting a flag might not be enough either.
522 Vcore version numbers/history (as well as global proc histories) is a pain I'd
523 like to avoid too.  So don't change the alarm / delayed preemption system
524 without thinking about this.
525
526 Also, allowing a vcore to restart while preemptions are pending also mucks
527 with keeping the vcore mapping "old" (while the message is in flight).  A
528 pcore will want to use that to determine which vcore is running on it.  It
529 would be possible to keep a pcoremap for the reverse mapping out of sync, but
530 that seems like a bad idea.  In general, having the pcoremap is a good idea
531 (whenever we talk about a vcoremap, we're usually talking about both
532 directions: "the vcore->pcore mapping").
533
534 4.5: Global Preemption Flags
535 ---------------------------
536 If we are trying to preempt an entire process at the same time, instead of
537 playing with the circular buffer of vcores pending preemption, we could have a
538 global timer as well.  This avoids some O(n) operations, though it means that
539 userspace needs to check two "flags" (expiration dates) when grabbing its
540 preempt-critical locks.
541
542 4.6: Notifications Mixed with Preemption and Sleeping
543 ---------------------------
544 It is possible that notifications will mix with preemptions or come while a
545 process is not running.  Ultimately, the process wants to be notified on a
546 given vcore.  Whenever we send an active notification, we set a flag in procdata
547 (notif_pending).  If the vcore is offline, we don't bother sending the IPI/notif
548 message.  The kernel will make sure it runs the notification handler (as well as
549 restoring the vcore_ctx) the next time that vcore is restarted.  Note that
550 userspace can toggle this, so they can handle the notifications from a different
551 core if it likes, or they can independently send a notification.
552
553 Note we use notif_pending to detect if an IPI was missed while notifs were
554 disabled (this is done in pop_user_ctx() by userspace).  The overall meaning
555 of notif_pending is that a vcore wants to be IPI'd.  The IPI could be
556 in-flight, or it could be missed.  Since notification IPIs can be spurious,
557 when we have potential races, we err on the side of sending.  This happens
558 when pop_user_ctx() notifies itself, and when the kernel makes sure to start a
559 vcore in vcore context if a notif was pending.  This was simplified a bit over
560 the years by having uthreads always get saved into the uthread_ctx (formerly
561 the notif_tf), instead of in the old preempt_tf (which is now the vcore_ctx).
562
563 If a vcore has a preempt_pending, we will still send the active notification
564 (IPI).  The core ought to get a notification for the preemption anyway, so we
565 need to be able to send one.  Additionally, once the vcore is handling that
566 preemption notification, it will have notifs disabled, which will prevent us
567 from sending any extra notifications anyways.
568  
569 4.7: Notifs While a Preempt Message is Served
570 ---------------------------
571 It is possible to have the kernel handling a notification k_msg and to have a
572 preempt k_msg in the queue (preempt-served flag is set).  Ultimately, what we
573 want is for the core to be preempted and the notification handler to run on
574 the next execution.  Both messages are in the k_msg queue for "a convenient
575 time to leave the kernel" (I'll have a better name for that later).  What we
576 do is execute the notification handler and jump to userspace.  Since there is
577 still an k_msg in the queue (and we self_ipi'd ourselves, it's part of how
578 k_msgs work), the IPI will fire and push us right back into the kernel to
579 execute the preemption, and the notif handler's context will be saved in the
580 vcore_ctx (ready to go when the vcore gets started again).
581
582 We could try to just leave the notif_pending flag set and ignore the message,
583 but that would involve inspecting the queue for the preempt k_msg.
584 Additionally, a preempt k_msg can arrive anyway.  Finally, it's possible to have
585 another message in the queue between the notif and the preempt, and it gets ugly
586 quickly trying to determine what to do.
587
588 4.8: When a Pcore is "Free"
589 ---------------------------
590 There are a couple ways to handle pcores.  One approach would be to not
591 consider them free and able to be given to another process until the old
592 process is completely removed (abandon_core()).  Another approach is to free
593 the core once its fate is sealed (which we do).  This probably gives more
594 flexibility in schedule()-like functions (no need to wait to give the core
595 out), quicker dispatch latencies, less contention on shared structs (like the
596 idle-core-map), etc.
597
598 This 'freeing' of the pcore is from the perspective of the kernel scheduler
599 and the proc struct.  Contrary to all previous announcements, vcores are
600 unmapped from pcores when sending k_msgs (technically right after), while
601 holding the lock.  The pcore isn't actually not-running-the-proc until the
602 kmsg completes and we abandon_core().  Previously, we used the vcoremap to
603 communicate to other cores in a lock-free manner, but that was pretty shitty
604 and now we just store the vcoreid in pcpu info.
605
606 Another tricky part is the seq_ctr used to signal userspace of changes to the
607 coremap or num_vcores (coremap_seqctr).  While we may not even need this in the
608 long run, it still seems like it could be useful.  The trickiness comes from
609 when we update the seq_ctr when we are unmapping vcores on the receive side of a
610 message (like __death or __preempt).  We'd rather not have each pcore contend on
611 the seq_ctr cache line (let alone any locking) while they perform a somewhat
612 data-parallel task.  So we continue to have the sending core handle the seq_ctr
613 upping and downing.  This works, since the "unlocking" happens after messages
614 are sent, which means the receiving core is no longer in userspace (if there is
615 a delay, it is because the remote core is in the kernel, possibly with
616 interrupts disabled).  Because of this, userspace will be unable to read the new
617 value of the seq_ctr before the IPI hits and does the unmapping that the seq_ctr
618 protects/advertises.  This is most likely true.  It wouldn't be if the "last IPI
619 was sent" flag clears before the IPI actually hit the other core.
620
621 4.9: Future Broadcast/Messaging Needs
622 ---------------------------
623 Currently, messaging is serialized.  Broadcast IPIs exist, but the kernel
624 message system is based on adding an k_msg to a list in a pcore's
625 per_cpu_info.  Further the sending of these messages is in a loop.  In the
626 future, we would like to have broadcast messaging of some sort (literally a
627 broadcast, like the IPIs, and if not that, then a communication tree of
628 sorts).  
629
630 In the past, (OLD INFO): given those desires, we wanted to make sure that no
631 message we send needs details specific to a pcore (such as the vcoreid running
632 on it, a history number, or anything like that).  Thus no k_msg related to
633 process management would have anything that cannot apply to the entire
634 process.  At this point, most just have a struct proc *.  A pcore was be able
635 to figure out what is happening based on the pcoremap, information in the
636 struct proc, and in the preempt struct in procdata.
637
638 In more recent revisions, the coremap no longer is meant to be used across
639 kmsgs, so some messages ('__startcore') send the vcoreid.  This means we can't
640 easily broadcast the message.  However, many broadcast mechanisms wouldn't
641 handle '__startcore' naturally.  For instance, logical IPIs need something
642 already set in the LAPIC, or maybe need to be sent to a somewhat predetermined
643 group (again, bits in the LAPIC).  If we tried this for '__startcore', we
644 could add something in to the messaging to carry these vcoreids.  More likely,
645 we'll have a broadcast tree.  Keeping vcoreid (or any arg) next to whoever
646 needs to receive the message is a very small amount of bookkeeping on a struct
647 that already does bookkeeping.
648
649 4.10: Other Things We Thought of but Don't Like
650 ---------------------------
651 All local fate-related work is sent as a self k_msg, to enforce ordering.
652 It doesn't capture the difference between a local call and a remote k_msg.
653 The k_msg has already considered state and made its decision.  The local call
654 is an attempt.  It is also unnecessary, if we put in enough information to
655 make a decision in the proc struct.  Finally, it caused a few other problems
656 (like needing to detect arbitrary stale messages).
657
658 Overall message history: doesn't work well when you do per-core stuff, since
659 it will invalidate other messages for the process.  We then though of a pcore
660 history counter to detect stale messages.  Don't like that either.  We'd have
661 to send the history in the message, since it's a per-message, per-core
662 expiration.  There might be other ways around this, but this doesn't seem
663 necessary.
664
665 Alarms have pointers to a list of which cores should be preempted when that
666 specific alarm goes off (saved with the alarm).  Ugh.  It gets ugly with
667 multiple outstanding preemptions and cores getting yielded while the alarms
668 sleep (and possibly could get reallocated, though we'd make a rule to prevent
669 that).  Like with notifications, being able to handle spurious alarms and
670 thinking of an alarm as just a prod to check somewhere is much more flexible
671 and simple.  It is similar to generic messages that have the actual important
672 information stored somewhere else (as with allowing broadcasts, with different
673 receivers performing slightly different operations).
674
675 Synchrony for messages (wanting a response to a preempt k_msg, for example)
676 sucks.  Just encode the state of impending fate in the proc struct, where it
677 belongs.  Additionally, we don't want to hold the proc lock even longer than
678 we do now (which is probably too long as it is).  Finally, it breaks a golden
679 rule: never wait while holding a lock: you will deadlock the system (e.g. if
680 the receiver is already in the kernel spinning on the lock).  We'd have to
681 send messages, unlock (which might cause a message to hit the calling pcore,
682 as in the case of locally called proc_destroy()), and in the meantime some
683 useful invariant might be broken.
684
685 We also considered using the transition stack as a signal that a process is in
686 a notification handler.  The kernel can inspect the stack pointer to determine
687 this.  It's possible, but unnecessary.
688
689 Using the pcoremap as a way to pass info with kmsgs: it worked a little, but
690 had some serious problems, as well as making life difficult.  It had two
691 purposes: help with local fate calls (yield) and allow broadcast messaging.
692 The main issue is that it was using a global struct to pass info with
693 messages, but it was based on the snapshot of state at the time the message
694 was sent.  When you send a bunch of messages, certain state may have changed
695 between messages, and the old snapshot isn't there anymore by the time the
696 message gets there.  To avoid this, we went through some hoops and had some
697 fragile code that would use other signals to avoid those scenarios where the
698 global state change would send the wrong message.  It was tough to understand,
699 and not clear it was correct (hint: it wasn't).  Here's an example (on one
700 pcore): if we send a preempt and we then try to map that pcore to another
701 vcore in the same process before the preempt call checks its pcoremap, we'll
702 clobber the pcore->vcore mapping (used by startcore) and the preempt will
703 think it is the new vcore, not the one it was when the message was sent.
704 While this is a bit convoluted, I can imagine a ksched doing this, and
705 perhaps with weird IRQ delays, the messages might get delayed enough for it to
706 happen.  I'd rather not have to have the ksched worry about this just because
707 proc code was old and ghetto.  Another reason we changed all of this was so
708 that you could trust the vcoremap while holding the lock.  Otherwise, it's
709 actually non-trivial to know the state of a vcore (need to check a combination
710 of preempt_served and is_mapped), and even if you do that, there are some
711 complications with doing this in the ksched.
712
713 5. current_ctx and owning_proc
714 ===========================
715 Originally, current_tf was a per-core macro that returns a struct trapframe *
716 that points back on the kernel stack to the user context that was running on
717 the given core when an interrupt or trap happened.  Saving the reference to
718 the TF helps simplify code that needs to do something with the TF (like save
719 it and pop another TF).  This way, we don't need to pass the context all over
720 the place, especially through code that might not care.
721
722 Then, current_tf was more broadly defined as the user context that should be
723 run when the kernel is ready to run a process.  In the older case, it was when
724 the kernel tries to return to userspace from a trap/interrupt.  current_tf
725 could be set by an IPI/KMSG (like '__startcore') so that when the kernel wants
726 to idle, it will find a current_tf that it needs to run, even though we never
727 trapped in on that context in the first place.
728
729 Finally, current_tf was changed to current_ctx, and instead of tracking a
730 struct trapframe (equivalent to a hw_trapframe), it now tracked a struct
731 user_context, which could be either a HW or a SW trapframe.
732
733 Further, we now have 'owning_proc', which tells the kernel which process
734 should be run.  'owning_proc' is a bigger deal than 'current_ctx', and it is
735 what tells us to run cur_ctx.
736
737 Process management KMSGs now simply modify 'owning_proc' and cur_ctx, as if we
738 had interrupted a process.  Instead of '__startcore' forcing the kernel to
739 actually run the process and trapframe, it will just mean we will eventually
740 run it.  In the meantime a '__notify' or a '__preempt' can come in, and they
741 will apply to the owning_proc/cur_ctx.  This greatly simplifies process code
742 and code calling process code (like the scheduler), since we no longer need to
743 worry about whether or not we are getting a "stack killing" kernel message.
744 Before this, code needed to care where it was running when managing _Ms.
745
746 Note that neither 'current_ctx' nor 'owning_proc' rely on 'current'/'cur_proc'.
747 'current' is just what process context we're in, not what process (and which
748 trapframe) we will eventually run.
749
750 cur_ctx does not point to kernel trapframes, which is important when we
751 receive an interrupt in the kernel.  At one point, we were (hypothetically)
752 clobbering the reference to the user trapframe, and were unable to recover.
753 We can get away with this because the kernel always returns to its previous
754 context from a nested handler (via iret on x86).  
755
756 In the future, we may need to save kernel contexts and may not always return
757 via iret.  At which point, if the code path is deep enough that we don't want
758 to carry the TF pointer, we may revisit this.  Until then, current_ctx is just
759 for userspace contexts, and is simply stored in per_cpu_info.
760
761 Brief note from the future (months after this paragraph was written): cur_ctx
762 has two aspects/jobs:
763 1) tell the kernel what we should do (trap, fault, sysc, etc), how we came
764 into the kernel (the fact that it is a user tf), which is why we copy-out
765 early on
766 2) be a vehicle for us to restart the process/vcore
767
768 We've been focusing on the latter case a lot, since that is what gets
769 removed when preempted, changed during a notify, created during a startcore,
770 etc.  Don't forget it was also an instruction of sorts.  The former case is
771 always true throughout the life of the syscall.  The latter only happens to be
772 true throughout the life of a *non-blocking* trap since preempts are routine
773 KMSGs.  But if we block in a syscall, the cur_ctx is no longer the TF we came
774 in on (and possibly the one we are asked to operate on), and that old cur_ctx
775 has probably restarted.
776
777 (Note that cur_ctx is a pointer, and syscalls/traps actually operate on the TF
778 they came in on regardless of what happens to cur_ctx or pcpui->actual_tf.)
779
780 6. Locking!
781 ===========================
782 6.1: proc_lock
783 ---------------------------
784 Currently, all locking is done on the proc_lock.  It's main goal is to protect
785 the vcore mapping (vcore->pcore and vice versa).  As of Apr 2010, it's also used
786 to protect changes to the address space and the refcnt.  Eventually the refcnt
787 will be handled with atomics, and the address space will have it's own MM lock.  
788
789 We grab the proc_lock all over the place, but we try to avoid it whereever
790 possible - especially in kernel messages or other places that will be executed
791 in parallel.  One place we do grab it but would like to not is in proc_yield().  
792 We don't always need to grab the proc lock.  Here are some examples:
793
794 6.1.1: Lockless Notifications:
795 -------------
796 We don't lock when sending a notification.  We want the proc_lock to not be an
797 irqsave lock (discussed below).  Since we might want to send a notification from
798 interrupt context, we can't grab the proc_lock if it's a regular lock.  
799
800 This is okay, since the proc_lock is only protecting the vcoremapping.  We could
801 accidentally send the notification to the wrong pcore.  The __notif handler
802 checks to make sure it is the right process, and all _M processes should be able
803 to handle spurious notifications.  This assumes they are still _M.
804
805 If we send it to the wrong pcore, there is a danger of losing the notif, since
806 it didn't go to the correct vcore.  That would happen anyway, (the vcore is
807 unmapped, or in the process of mapping).  The notif_pending flag will be caught
808 when the vcore is started up next time (and that flag was set before reading the
809 vcoremap).
810
811 6.1.2: Local get_vcoreid():
812 -------------
813 It's not necessary to lock while checking the vcoremap if you are checking for
814 the core you are running on (e.g. pcoreid == core_id()).  This is because all
815 unmappings of a vcore are done on the receive side of a routine kmsg, and that
816 code cannot run concurrently with the code you are running.  
817
818 6.2: irqsave
819 ---------------------------
820 The proc_lock used to be an irqsave lock (meaning it disables interrupts and can
821 be grabbed from interrupt context).  We made it a regular lock for a couple
822 reasons.  The immediate one was it was causing deadlocks due to some other
823 ghetto things (blocking on the frontend server, for instance).  More generally,
824 we don't want to disable interrupts for long periods of time, so it was
825 something worth doing anyway.  
826
827 This means that we cannot grab the proc_lock from interrupt context.  This
828 includes having schedule called from an interrupt handler (like the
829 timer_interrupt() handler), since it will call proc_run.  Right now, we actually
830 do this, which we shouldn't, and that will eventually get fixed.  The right
831 answer is that the actual work of running the scheduler should be a routine
832 kmsg, similar to how Linux sets a bit in the kernel that it checks on the way
833 out to see if it should run the scheduler or not.
834
835 7. TLB Coherency
836 ===========================
837 When changing or removing memory mappings, we need to do some form of a TLB
838 shootdown.  Normally, this will require sending an IPI (immediate kmsg) to
839 every vcore of a process to unmap the affected page.  Before allocating that
840 page back out, we need to make sure that every TLB has been flushed.  
841
842 One reason to use a kmsg over a simple handler is that we often want to pass a
843 virtual address to flush for those architectures (like x86) that can
844 invalidate a specific page.  Ideally, we'd use a broadcast kmsg (doesn't exist
845 yet), though we already have simple broadcast IPIs.
846
847 7.1 Initial Stuff
848 ---------------------------
849 One big issue is whether or not to wait for a response from the other vcores
850 that they have unmapped.  There are two concerns: 1) Page reuse and 2) User
851 semantics.  We cannot give out the physical page while it may still be in a
852 TLB (even to the same process.  Ask us about the pthread_test bug).
853
854 The second case is a little more detailed.  The application may not like it if
855 it thinks a page is unmapped or protected, and it does not generate a fault.
856 I am less concerned about this, especially since we know that even if we don't
857 wait to hear from every vcore, we know that the message was delivered and the
858 IPI sent.  Any cores that are in userspace will have trapped and eventually
859 handle the shootdown before having a chance to execute other user code.  The
860 delays in the shootdown response are due to being in the kernel with
861 interrupts disabled (it was an IMMEDIATE kmsg).
862
863 7.2 RCU
864 ---------------------------
865 One approach is similar to RCU.  Unmap the page, but don't put it on the free
866 list.  Instead, don't reallocate it until we are sure every core (possibly
867 just affected cores) had a chance to run its kmsg handlers.  This time is
868 similar to the RCU grace periods.  Once the period is over, we can then truly
869 free the page.
870
871 This would require some sort of RCU-like mechanism and probably a per-core
872 variable that has the timestamp of the last quiescent period.  Code caring
873 about when this page (or pages) can be freed would have to check on all of the
874 cores (probably in a bitmask for what needs to be freed).  It would make sense
875 to amortize this over several RCU-like operations.
876
877 7.3 Checklist
878 ---------------------------
879 It might not suck that much to wait for a response if you already sent an IPI,
880 though it incurs some more cache misses.  If you wanted to ensure all vcores
881 ran the shootdown handler, you'd have them all toggle their bit in a checklist
882 (unused for a while, check smp.c).  The only one who waits would be the
883 caller, but there still are a bunch of cache misses in the handlers.  Maybe
884 this isn't that big of a deal, and the RCU thing is an unnecessary
885 optimization.
886
887 7.4 Just Wait til a Context Switch
888 ---------------------------
889 Another option is to not bother freeing the page until the entire process is
890 descheduled.  This could be a very long time, and also will mess with
891 userspace's semantics.  They would be running user code that could still
892 access the old page, so in essence this is a lazy munmap/mprotect.  The
893 process basically has the page in pergatory: it can't be reallocated, and it
894 might be accessible, but can't be guaranteed to work.
895
896 The main benefit of this is that you don't need to send the TLB shootdown IPI
897 at all - so you don't interfere with the app.  Though in return, they have
898 possibly weird semantics.  One aspect of these weird semantics is that the
899 same virtual address could map to two different pages - that seems like a
900 disaster waiting to happen.  We could also block that range of the virtual
901 address space from being reallocated, but that gets even more tricky.
902
903 One issue with just waiting and RCU is memory pressure.  If we actually need
904 the page, we will need to enforce an unmapping, which sucks a little.
905
906 7.5 Bulk vs Single
907 ---------------------------
908 If there are a lot of pages being shot down, it'd be best to amortize the cost
909 of the kernel messages, as well as the invlpg calls (single page shootdowns).
910 One option would be for the kmsg to take a range, and not just a single
911 address.  This would help with bulk munmap/mprotects.  Based on the number of
912 these, perhaps a raw tlbflush (the entire TLB) would be worth while, instead
913 of n single shots.  Odds are, that number is arch and possibly workload
914 specific.
915
916 For now, the plan will be to send a range and have them individually shot
917 down.
918
919 7.6 Don't do it
920 ---------------------------
921 Either way, munmap/mprotect sucks in an MCP.  I recommend not doing it, and
922 doing the appropriate mmap/munmap/mprotects in _S mode.  Unfortunately, even
923 our crap pthread library munmaps on demand as threads are created and
924 destroyed.  The vcore code probably does in the bowels of glibc's TLS code
925 too, though at least that isn't on every user context switch.
926
927 7.7 Local memory
928 ---------------------------
929 Private local memory would help with this too.  If each vcore has its own
930 range, we won't need to send TLB shootdowns for those areas, and we won't have
931 to worry about weird application semantics.  The downside is we would need to
932 do these mmaps in certain ranges in advance, and might not easily be able to
933 do them remotely.  More on this when we actually design and build it.
934
935 7.8 Future Hardware Support
936 ---------------------------
937 It would be cool and interesting if we had the ability to remotely shootdown
938 TLBs.  For instance, all cores with cr3 == X, shootdown range Y..Z.  It's
939 basically what we'll do with the kernel message and the vcoremap, but with
940 magic hardware.
941
942 7.9 Current Status
943 ---------------------------
944 For now, we just send a kernel message to all vcores to do a full TLB flush,
945 and not to worry about checklists, waiting, or anything.  This is due to being
946 short on time and not wanting to sort out the issue with ranges.  The way
947 it'll get changed to is to send the kmsg with the range to the appropriate
948 cores, and then maybe put the page on the end of the freelist (instead of the
949 head).  More to come.
950
951 8. Process Management
952 ===========================
953 8.1 Vcore lists
954 ---------------------------
955 We have three lists to track a process's vcores.  The vcores themselves sit in
956 the vcoremap in procinfo; they aren't dynamically allocated (memory) or
957 anything like that.  The lists greatly eases vcore discovery and management.
958
959 A vcore is on exactly one of three lists: online (mapped and running vcores,
960 sometimes called 'active'), bulk_preempt (was online when the process was bulk
961 preempted (like a timeslice)), and inactive (yielded, hasn't come on yet,
962 etc).  When writes are complete (unlocked), either the online list or the
963 bulk_preempt list should be empty.
964
965 List modifications are protected by the proc_lock.  You can concurrently read,
966 but note you may get some weird behavior, such as a vcore on multiple lists, a
967 vcore on no lists, online and bulk_preempt both having items, etc.  Currently,
968 event code will read these lists when hunting for a suitable core, and will
969 have to be careful about races.  I want to avoid event FALLBACK code from
970 grabbing the proc_lock.
971
972 Another slight thing to be careful of is that the vcore lists don't always
973 agree with the vcore mapping.  However, it will always agree with what the
974 state of the process will be when all kmsgs are processed (fate).
975 Specifically, when we take vcores, the unmapping happens with the lock not
976 held on the vcore itself (as discussed elsewhere).  The vcore lists represent
977 the result of those pending unmaps.
978
979 Before we used the lists, we scanned the vcoremap in a painful, clunky manner.
980 In the old style, when you asked for a vcore, the first one you got was the
981 first hole in the vcoremap.  Ex: Vcore0 would always be granted if it was
982 offline.  That's no longer true; the most recent vcore yielded will be given
983 out next.  This will help with cache locality, and also cuts down on the
984 scenarios on which the kernel gives out a vcore that userspace wasn't
985 expecting.  This can still happen if they ask for more vcores than they set up
986 for, or if a vcore doesn't *want* to come online (there's a couple scenarios
987 with preemption recovery where that may come up).
988
989 So the plan with the bulk preempt list is that vcores on it were preempted,
990 and the kernel will attempt to restart all of them (and move them to the online
991 list).  Any leftovers will be moved to the inactive list, and have preemption
992 recovery messages sent out.  Any shortages (they want more vcores than were
993 bulk_preempted) will be taken from the yield list.  This all means that
994 whether or not a vcore needs to be preempt-recovered or if there is a message
995 out about its preemption doesn't really affect which list it is on.  You could
996 have a vcore on the inactive list that was bulk preempted (and not turned back
997 on), and then that vcore gets granted in the next round of vcore_requests().
998 The preemption recovery handlers will need to deal with concurrent handlers
999 and the vcore itself starting back up.
1000
1001 9. On the Ordering of Messages and Bugs with Old State
1002 ===========================
1003 This is a sordid tale involving message ordering, message delivery times, and
1004 finding out (sometimes too late) that the state you expected is gone and
1005 having to deal with that error.
1006
1007 A few design issues:
1008 - being able to send messages and have them execute in the order they are
1009   sent
1010 - having message handlers resolve issues with global state.  Some need to know
1011   the correct 'world view', and others need to know what was the state at the
1012   time they were sent.
1013 - realizing syscalls, traps, faults, and any non-IRQ entry into the kernel is
1014   really a message.
1015
1016 Process management messages have alternated from ROUTINE to IMMEDIATE and now
1017 back to ROUTINE.  These messages include such family favorites as
1018 '__startcore', '__preempt', etc.  Meanwhile, syscalls were coming in that
1019 needed to know about the core and the process's state (specifically, yield,
1020 change_to, and get_vcoreid).  Finally, we wanted to avoid locking, esp in
1021 KMSGs handlers (imagine all cores grabbing the lock to check the vcoremap or
1022 something).
1023
1024 Incidentally, events were being delivered concurretly to vcores, though that
1025 actually didn't matter much (check out async_events.txt for more on that).
1026
1027 9.1: Design Guidelines
1028 ---------------------------
1029 Initially, we wanted to keep broadcast messaging available as an option.  As
1030 noted elsewhere, we can't really do this well for startcore, since most
1031 hardware broadcast options need some initial per-core setup, and any sort of
1032 broadcast tree we make should be able to handle a small message.  Anyway, this
1033 desire in the early code to keep all messages identical lead to a few
1034 problems.
1035
1036 Another objective of the kernel messaging was to avoid having the message
1037 handlers grab any locks, especially the same lock (the proc lock is used to
1038 protect the vcore map, for instance).
1039
1040 Later on, a few needs popped up that motivated the changes discussed below:
1041 - Being able to find out which proc/vcore was on a pcore
1042 - Not having syscalls/traps require crazy logic if the carpet was pulled out
1043   from under them.
1044 - Having proc management calls return.  This one was sorted out by making all
1045   kmsg handlers return.  It would be a nightmare making a ksched without this.
1046
1047 9.2: Looking at Old State: a New Bug for an Old Problem
1048 ---------------------------
1049 We've always had issues with syscalls coming in and already had the fate of a
1050 core determined.  This is referred to in a few places as "predetermined fate"
1051 vs "local state".  A remote lock holder (ksched) already determined a core
1052 should be unmapped and sent a message.  Only later does some call like
1053 proc_yield() realize its core is already *unmapped*. (I use that term poorly
1054 here).  This sort of code had to realize it was working on an old version of
1055 state and just abort.  This was usually safe, though looking at the vcoremap
1056 was a bad idea.  Initially, we used preempt_served as the signal, which was
1057 okay.  Around 12b06586 yield started to use the vcoremap, which turned out to
1058 be wrong.
1059
1060 A similar issue happens for the vcore messages (startcore, preempt, etc).  The
1061 way startcore used to work was that it would only know what pcore it was on,
1062 and then look into the vcoremap to figure out what vcoreid it should be
1063 running.  This was to keep broadcast messaging available as an option.  The
1064 problem with it is that the vcoremap may have changed between when the
1065 messages were sent and when they were executed.  Imagine a startcore followed
1066 by a preempt, afterwhich the vcore was unmapped.  Well, to get around that, we
1067 had the unmapping happen in the preempt or death handlers.  Yikes!  This was
1068 the case back in the early days of ROS.  This meant the vcoremap wasn't
1069 actually representative of the decisions the ksched made - we also needed to
1070 look at the state we'd have after all outstanding messages executed.  And this
1071 would differ from the vcore lists (which were correct for a lock holder).
1072
1073 This was managable for a little while, until I tried to conclusively know who
1074 owned a particular pcore.  This came up while making a provisioning scheduler.
1075 Given a pcore, tell me which process/vcore (if any) were on it.  It was rather
1076 tough.  Getting the proc wasn't too hard, but knowing which vcore was a little
1077 tougher.  (Note the ksched doesn't care about which vcore is running, and the
1078 process can change vcores on a pcore at will).  But once you start looking at
1079 the process, you can't tell which vcore a certain pcore has.  The vcoremap may
1080 be wrong, since a preempt is already on the way.  You would have had to scan
1081 the vcore lists to see if the proc code thought that vcore was online or not
1082 (which would mean there had been no preempts).  This is the pain I was talking
1083 about back around commit 5343a74e0.
1084
1085 So I changed things so that the vcoremap was always correct for lock holders,
1086 and used pcpui to track owning_vcoreid (for preempt/notify), and used an extra
1087 KMSG variable to tell startcore which vcoreid it should use.  In doing so, we
1088 (re)created the issue that the delayed unmapping dealt with: the vcoremap
1089 would represent *now*, and not the vcoremap of when the messages were first
1090 sent.  However, this had little to do with the KMSGs, which I was originally
1091 worried about.  No one was looking at the vcoremap without the lock, so the
1092 KMSGs were okay, but remember: syscalls are like messages too.  They needed to
1093 figure out what vcore they were on, i.e. what vcore userspace was making
1094 requests on (viewing a trap/fault as a type of request).
1095
1096 Now the problem was that we were using the vcoremap to figure out which vcore
1097 we were supposed to be.  When a syscall finally ran, the vcoremap could be
1098 completely wrong, and with immediate KMSGs (discussed below), the pcpui was
1099 already changed!  We dealt with the problem for KMSGs, but not syscalls, and
1100 basically reintroduced the bug of looking at current state and thinking it
1101 represented the state from when the 'message' was sent (when we trapped into
1102 the kernel, for a syscall/exception).
1103
1104 9.3: Message Delivery, Circular Waiting, and Having the Carpet Pulled Out
1105 ---------------------------
1106 In-order message delivery was what drove me to build the kernel messaging
1107 system in the first place.  It provides in-order messages to a particular
1108 pcore.  This was enough for a few scenarios, such as preempts racing ahead of
1109 startcores, or deaths racing a head of preempts, etc.  However, I also wanted
1110 an ordering of messages related to a particular vcore, and this wasn't
1111 apparent early on.
1112
1113 The issue first popped up with a startcore coming quickly on the heals of a
1114 preempt for the same VC, but on different PCs.  The startcore cannot proceed
1115 until the preempt saved the TF into the VCPD.  The old way of dealing with
1116 this was to spin in '__map_vcore()'.  This was problematic, since it meant we
1117 were spinning while holding a lock, and resulted in some minor bugs and issues
1118 with lock ordering and IRQ disabling (couldn't disable IRQs and then try to
1119 grab the lock, since the lock holder could have sent you a message and is
1120 waiting for you to handle the IRQ/IMMED KMSG).  However, it was doable.  But
1121 what wasn't doable was to have the KMSGs be ROUTINE.  Any syscalls that tried
1122 to grab the proc lock (lots of them) would deadlock, since the lock holder was
1123 waiting on us to handle the preempt (same circular waiting issue as above).
1124
1125 This was fine, albeit subpar, until a new issue showed up.  Sending IMMED
1126 KMSGs worked fine if we were coming from userspace already, but if we were in
1127 the kernel, those messages would run immediately (hence the name), just like
1128 an IRQ handler, and could confuse syscalls that touched cur_ctx/pcpui.  If a
1129 preempt came in during a syscall, the process/vcore could be changed before
1130 the syscall took place.  Some syscalls could handle this, albeit poorly.
1131 sys_proc_yield() and sys_change_vcore() delicately tried to detect if they
1132 were still mapped or not and use that to determine if a preemption happened.
1133
1134 As mentioned above, looking at the vcoremap only tells you what is currently
1135 happening, and not what happened in the past.  Specifically, it doesn't tell
1136 you the state of the mapping when a particular core trapped into the kernel
1137 for a syscall (referred to as when the 'message' was sent up above).  Imagine
1138 sys_get_vcoreid(): you trap in, then immediately get preempted, then startcore
1139 for the same process but a different vcoreid.  The syscall would return with
1140 the vcoreid of the new vcore, since it cannot tell there was a change.  The
1141 async syscall would complete and we'd have a wrong answer.  While this never
1142 happened to me, I had a similar issue while debugging some other bugs (I'd get
1143 a vcoreid of 0xdeadbeef, for instance, which was the old poison value for an
1144 unmapped vcoreid).  There are a bunch of other scenarios that trigger similar
1145 disasters, and they are very hard to avoid.
1146
1147 One way out of this was a per-core history counter, that changed whenever we
1148 changed cur_ctx.  Then when we trapped in for a syscall, we could save the
1149 value, enable_irqs(), and go about our business.  Later on, we'd have to
1150 disable_irqs() and compare the counters.  If they were different, we'd have to
1151 bail out some how.  This could have worked for change_to and yield, and some
1152 others.  But any syscall that wanted to operate on cur_ctx in some way would
1153 fail (imagine a hypothetical sys_change_stack_pointer()).  The context that
1154 trapped has already returned on another core.  I guess we could just fail that
1155 syscall, though it seems a little silly to not be able to do that.
1156
1157 The previous example was a bit contrived, but lets also remember that it isn't
1158 just syscalls: all exceptions have the same issue.  Faults might be fixable,
1159 since if you restart a faulting context, it will start on the faulting
1160 instruction.  However all traps (like syscall) restart on the next
1161 instruction.  Hope we don't want to do anything fancy with breakpoint!  Note
1162 that I had breakpointing contexts restart on other pcores and continue while I
1163 was in the breakpoint handler (noticed while I was debugging some bugs with
1164 lots of preempts).  Yikes.  And don't forget we eventually want to do some
1165 complicated things with the page fault handler, and may want to turn on
1166 interrupts / kthread during a page fault (imaging hitting disk).  Yikes.
1167
1168 So I looked into going back to ROUTINE kernel messages.  With ROUTINE
1169 messages, I didn't have to worry about having the carpet pulled out from under
1170 syscalls and exceptions (traps, faults, etc).  The 'carpet' is stuff like
1171 cur_ctx, owning_proc, owning_vcoreid, etc.  We still cannot trust the vcoremap,
1172 unless we *know* there were no preempts or other KMSGs waiting for us.
1173 (Incidentally, in the recent fix a93aa7559, we merely use the vcoremap as a
1174 sanity check).
1175
1176 However, we can't just switch back to ROUTINEs.  Remember: with ROUTINEs,
1177 we will deadlock in '__map_vcore()', when it waits for the completion of
1178 preempt.  Ideally, we would have had startcore spin on the signal.  Since we
1179 already gave up on using x86-style broadcast IPIs for startcore (in
1180 5343a74e0), we might as well pass along a history counter, so it knows to wait
1181 on preempt.
1182
1183 9.4: The Solution
1184 ---------------------------
1185 To fix up all of this, we now detect preemptions in syscalls/traps and order
1186 our kernel messages with two simple per-vcore counters.  Whenever we send a
1187 preempt, we up one counter.  Whenever that preempt finishes, it ups another
1188 counter.  When we send out startcores, we send a copy of the first counter.
1189 This is a way of telling startcore where it belongs in the list of messages.
1190 More specifically, it tells it which preempt happens-before it.
1191
1192 Basically, I wanted a partial ordering on my messages, so that messages sent
1193 to a particular vcore are handled in the order they were sent, even if those
1194 messages run on different physical cores.
1195
1196 It is not sufficient to use a seq counter (one integer, odd values for
1197 'preempt in progress' and even values for 'preempt done').  It is possible to
1198 have multiple preempts in flight for the same vcore, albeit with startcores in
1199 between.  Still, there's no way to encode that scenario in just one counter.
1200
1201 Here's a normal example of traffic to some vcore.  I note both the sending and
1202 the execution of the kmsgs:
1203    nr_pre_sent    nr_pre_done    pcore     message sent/status
1204    -------------------------------------------------------------
1205    0              0              X         startcore (nr_pre_sent == 0)
1206    0              0              X         startcore (executes)
1207    1              0              X         preempt   (kmsg sent)
1208    1              1              Y         preempt   (executes)
1209    1              1              Y         startcore (nr_pre_sent == 1)
1210    1              1              Y         startcore (executes)
1211
1212 Note the messages are always sent by the lockholder in the order of the
1213 example above.
1214
1215 Here's when the startcore gets ahead of the prior preempt:
1216    nr_pre_sent    nr_pre_done    pcore     message sent/status
1217    -------------------------------------------------------------
1218    0              0              X         startcore (nr_pre_sent == 0) 
1219    0              0              X         startcore (executes)
1220    1              0              X         preempt   (kmsg sent)
1221    1              0              Y         startcore (nr_pre_sent == 1)
1222    1              1              X         preempt   (executes)
1223    1              1              Y         startcore (executes)
1224
1225 Note that this can only happen across cores, since KMSGs to a particular core
1226 are handled in order (for a given class of message).  The startcore blocks on
1227 the prior preempt.
1228
1229 Finally, here's an example of what a seq ctr can't handle:
1230    nr_pre_sent    nr_pre_done    pcore     message sent/status
1231    -------------------------------------------------------------
1232    0              0              X         startcore (nr_pre_sent == 0) 
1233    1              0              X         preempt   (kmsg sent)
1234    1              0              Y         startcore (nr_pre_sent == 1)
1235    2              0              Y         preempt   (kmsg sent)
1236    2              0              Z         startcore (nr_pre_sent == 2)
1237    2              1              X         preempt   (executes (upped to 1))
1238    2              1              Y         startcore (executes (needed 1))
1239    2              2              Y         preempt   (executes (upped to 2))
1240    2              Z              Z         startcore (executes (needed 2))
1241
1242 As a nice bonus, it is easy for syscalls that care about the vcoreid (yield,
1243 change_to, get_vcoreid) to check if they have a preempt_served.  Just grab the
1244 lock (to prevent further messages being sent), then check the counters.  If
1245 they are equal, there is no preempt on its way.  This actually was the
1246 original way we checked for preempts in proc_yield back in the day.  It was
1247 just called preempt_served.  Now, it is split into two counters, instead of
1248 just being a bool.  
1249
1250 Regardless of whether or not we were preempted, we still can look at
1251 pcpui->owning_proc and owning_vcoreid to figure out what the vcoreid of the
1252 trap/syscall is, and we know that the cur_ctx is still the correct cur_ctx (no
1253 carpet pulled out), since while there could be a preempt ROUTINE message
1254 waiting for us, we simply haven't run it yet.  So calls like yield should
1255 still fail (since your core has been unmapped and you need to bail out and run
1256 the preempt handler), but calls like sys_change_stack_pointer can proceed.
1257 More importantly than that old joke syscall, the page fault handler can try to
1258 do some cool things without worrying about really crazy stuff.
1259
1260 9.5: Why We (probably) Don't Deadlock
1261 ---------------------------
1262 It's worth thinking about why this setup of preempts and startcores can't
1263 deadlock.  Anytime we spin in the kernel, we ought to do this.  Perhaps there
1264 is some issue with other KMSGs for other processes, or other vcores, or
1265 something like that that can cause a deadlock.
1266
1267 Hypothetical case: pcore 1 has a startcore for vc1 which is stuck behind vc2's
1268 startcore on PC2, with time going upwards.  In these examples, startcores are
1269 waiting on particular preempts, subject to the nr_preempts_sent parameter sent
1270 along with the startcores.
1271
1272 ^                       
1273 |            _________                 _________
1274 |           |         |               |         |
1275 |           | pr vc 2 |               | pr vc 1 |
1276 |           |_________|               |_________|
1277 |
1278 |            _________                 _________
1279 |           |         |               |         |
1280 |           | sc vc 1 |               | sc vc 2 |
1281 |           |_________|               |_________|
1282 t           
1283 ---------------------------------------------------------------------------
1284               ______                    ______
1285              |      |                  |      |
1286              | PC 1 |                  | PC 2 |
1287              |______|                  |______|
1288
1289 Here's the same picture, but with certain happens-before arrows.  We'll use X --> Y to
1290 mean X happened before Y, was sent before Y.  e.g., a startcore is sent after
1291 a preempt.
1292
1293 ^                       
1294 |            _________                 _________
1295 |           |         |               |         |
1296 |       .-> | pr vc 2 | --.    .----- | pr vc 1 | <-.
1297 |       |   |_________|    \  /   &   |_________|   |  
1298 |     * |                   \/                      | * 
1299 |       |    _________      /\         _________    |  
1300 |       |   |         |    /  \   &   |         |   |  
1301 |       '-- | sc vc 1 | <-'    '----> | sc vc 2 | --'
1302 |           |_________|               |_________|
1303 t           
1304 ---------------------------------------------------------------------------
1305               ______                    ______
1306              |      |                  |      |
1307              | PC 1 |                  | PC 2 |
1308              |______|                  |______|
1309
1310 The arrows marked with * are ordered like that due to the property of KMSGs,
1311 in that we have in order delivery.  Messages are executed in the order in
1312 which they were sent (serialized with a spinlock btw), so on any pcore,
1313 messages that are further ahead in the queue were sent before (and thus will
1314 be run before) other messages.
1315
1316 The arrows marked with a & are ordered like that due to how the proc
1317 management code works.  The kernel won't send out a startcore for a particular
1318 vcore before it sent out a preempt.  (Note that techincally, preempts follow
1319 startcores.  The startcores in this example are when we start up a vcore after
1320 it had been preempted in the past.).
1321
1322 Anyway, note that we have a cycle, where all events happened before each
1323 other, which isn't possible.  The trick to connecting "unrelated" events like
1324 this (unrelated meaning 'not about the same vcore') in a happens-before manner
1325 is the in-order properties of the KMSGs.
1326
1327 Based on this example, we can derive general rules.  Note that 'sc vc 2' could
1328 be any kmsg that waits on another message placed behind 'sc vc 1'.  This would
1329 require us having sent a KMSG that waits on a KMSGs that we send later.  Bad
1330 idea!  (you could have sent that KMSGs to yourself, aside from just being
1331 dangerous).  If you want to spin, make sure you send the work that should
1332 happen-before actually-before the waiter.
1333
1334 In fact, we don't even need 'sc vc 2' to be a KMSG.  It could be miscellaneous
1335 kernel code, like a proc mgmt syscall.  Imagine if we did something like the
1336 old '__map_vcore' call from within the ksched.  That would be code that holds
1337 the lock, and then waits on the execution of a message handler.  That would
1338 deadlock (which is why we don't do it anymore).
1339
1340 Finally, in case this isn't clear, all of the startcores and preempts for
1341 a given vcore exist in a happens-before relation, both in sending and in
1342 execution.  The sending aspect is handled by proc mgmt code.  For execution,
1343 preempts always follow startcores due to the KMSG ordering property.  For
1344 execution of startcores, startcores always spin until the preempt they follow
1345 is complete, ensuring the execution of the main part of their handler happens
1346 after the prior preempt.
1347
1348 Here's some good ideas for the ordering of locks/irqs/messages:
1349 - You can't hold a spinlock of any sort and then wait on a routine kernel
1350   message.  The core where that runs may be waiting on you, or some scenario
1351   like above.
1352         - Similarly, think about how this works with kthreads.  A kthread restart
1353           is a routine KMSG.  You shouldn't be waiting on code that could end up
1354           kthreading, mostly because those calls block!
1355 - You can hold a spinlock and wait on an IMMED kmsg, if the waiters of the
1356   spinlock have irqs enabled while spinning (this is what we used to do with
1357   the proc lock and IMMED kmsgs, and 54c6008 is an example of doing it wrong)
1358         - As a corollary, locks like this cannot be irqsave, since the other
1359           attempted locker will have irq disabled
1360 - For broadcast trees, you'd have to send IMMEDs for the intermediates, and
1361   then it'd be okay to wait on those intermediate, immediate messages (if we
1362   wanted confirmation of the posting of RKM)
1363         - The main thing any broadcast mechanism needs to do is make sure all
1364           messages get delivered in order to particular pcores (the central
1365           premise of KMSGs) (and not deadlock due to waiting on a KMSG improperly)
1366 - Alternatively, we could use routines for the intermediates if we didn't want
1367   to wait for RKMs to hit their destination, we'd need to always use the same
1368   proxy for the same destination pcore, e.g., core 16 always covers 16-31.
1369         - Otherwise, we couldn't guarantee the ordering of SC before PR before
1370           another SC (which the proc_lock and proc mgmt code does); we need the
1371           ordering of intermediate msgs on the message queues of a particular
1372           core.
1373         - All kmsgs would need to use this broadcasting style (couldn't mix
1374           regular direct messages with broadcast), so odds are this style would be
1375           of limited use.
1376         - since we're not waiting on execution of a message, we could use RKMs
1377           (while holding a spinlock)
1378 - There might be some bad effects with kthreads delaying the reception of RKMS
1379   for a while, but probably not catastrophically.
1380
1381 9.6: Things That We Don't Handle Nicely
1382 ---------------------------
1383 If for some reason a syscall or fault handler blocks *unexpectedly*, we could
1384 have issues.  Imagine if change_to happens to block in some early syscall code
1385 (like instrumentation, or who knows what, that blocks in memory allocation).
1386 When the syscall kthread restarts, its old cur_ctx is gone.  It may or may not
1387 be running on a core owned by the original process.  If it was, we probably
1388 would accidentally yield that vcore (clearly a bug).  
1389
1390 For now, any of these calls that care about cur_ctx/pcpui need to not block
1391 without some sort of protection.  None of them do, but in the future we might
1392 do something that causes them to block.  We could deal with it by having a
1393 pcpu or per-kthread/syscall flag that says if it ever blocked, and possibly
1394 abort.  We get into similar nasty areas as with preempts, but this time, we
1395 can't solve it by making preempt a routine KMSG - we block as part of that
1396 syscall/handler code.  Odds are, we'll just have to outlaw this, now and
1397 forever.  Just note that if a syscall/handler blocks, the TF it came in on is
1398 probably not cur_ctx any longer, and that old cur_ctx has probably restarted.
1399
1400 10. TBD
1401 ===========================