Removed event overflow handling
[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_tf
15 6. Locking!
16 7. TLB Coherency
17 8. TBD
18
19 1. Reference Counting
20 ===========================
21 1.1 Basics:
22 ---------------------------
23 Reference counts exist to keep a process alive.  We use krefs for this, similar
24 to Linux's kref:
25 - Can only incref if the current value is greater than 0, meaning there is
26   already a reference to it.  It is a bug to try to incref on something that has
27   no references, so always make sure you incref something that you know has a
28   reference.  If you don't know, you need to get it from pid2proc (which is a
29   careful way of doing this - pid2proc kref_get_not_zero()s on the reference that is
30   stored inside it).  If you incref and there are 0 references, the kernel will
31   panic.  Fix your bug / don't incref random pointers.
32 - Can always decref.
33 - When the decref returns 0, perform some operation.  This does some final
34   cleanup on the object.
35 - Process code is trickier since we frequently make references from 'current'
36   (which isn't too bad), but also because we often do not return and need to be
37   careful about the references we passed in to a no-return function.
38
39 1.2 Brief History of the Refcnt:
40 ---------------------------
41 Originally, the refcnt was created to keep page tables from being destroyed (in
42 proc_free()) while cores were still using them, which is what was happens during
43 an ARSC (async remote syscall).  It was then defined to be a count of places in
44 the kernel that had an interest in the process staying alive, practically just
45 to protect current/cr3.  This 'interest' actually extends to any code holding a
46 pointer to the proc, such as one acquired via pid2proc(), which is its current
47 meaning.
48
49 1.3 Quick Aside: The current Macro:
50 ---------------------------
51 current is a pointer to the proc that is currently loaded/running on any given
52 core.  It is stored in the per_cpu_info struct, and set/managed by low-level
53 process code.  It is necessary for the kernel to quickly figure out who is
54 running on its code, especially when servicing interrupts and traps.  current is
55 protected by a refcnt.
56
57 1.4 Reference Counting Rules:
58 ---------------------------
59 +1 for existing.
60 - The fact that the process is supposed to exist is worth +1.  When it is time
61   to die, we decref, and it will eventually be cleaned up.  This existence is
62   explicitly kref_put()d in proc_destroy().
63 - The hash table is a bit tricky.  We need to kref_get_not_zero() when it is
64   locked, so we know we aren't racing with proc_free freeing the proc and
65   removing it from the list.  After removing it from the hash, we don't need to
66   kref_put it, since it was an internal ref.  The kref (i.e. external) isn't for
67   being on the hash list, it's for existing.  This separation allows us to
68   remove the proc from the hash list in the "release" function.  See kref.txt
69   for more details.
70
71 +1 for someone using it or planning to use it.
72 - This includes simply having a pointer to the proc, since presumably you will
73   use it.  pid2proc() will incref for you.  When you are done, decref.
74 - Functions that create a process and return a pointer (like proc_create() or
75   kfs_proc_create()) will also up the refcnt for you.  Decref when you're done.
76 - If the *proc is stored somewhere where it will be used again, such as in an IO
77   continuation, it needs to be refcnt'd.  Note that if you already had a
78   reference from pid2proc(), simply don't decref after you store the pointer.
79
80 +1 for current.
81 - current counts as someone using it (expressing interest in the core), but is
82   also a source of the pointer, so its a bit different.  Note that all kref's
83   are sources of a pointer.  Technically, to even use 'current', we should kref
84   it and pass it around as a proc.  We don't for performance reasons.  When we
85   are running on a core that has current loaded, the ref is both for its usage
86   as well as for being the current process.
87 - You have a reference from current and can use it without refcnting, but
88   anything that needs to eat a reference or store/use it needs an incref first.
89   To be clear, your reference is *NOT* edible.  It protects the cr3, guarantees
90   the process won't die, and serves as a bootstrappable reference.
91 - Specifically, if you get a ref from current, but then save it somewhere (like
92   an IO continuation request), then clearly you must incref, since it's both
93   current and stored/used.
94 - If you don't know what might be downstream from your function, then incref
95   before passing the reference, and decref when it returns.  We used to do this
96   for all syscalls, but now only do it for calls that might not return and
97   expect to receive reference (like proc_yield).
98
99 All functions that take a *proc have a refcnt'd reference, though it may not be
100 edible (it could be current).  It is the callers responsibility to make sure
101 it'd edible if it necessary.  It is the callees responsibility to incref if it
102 stores or makes a copy of the reference.
103
104 1.5 Functions That Don't or Might Not Return:
105 ---------------------------
106 Refcnting and especially decreffing gets tricky when there are functions that
107 MAY not return.  proc_restartcore() does not return (it pops into userspace).
108 proc_run() might not return, if the core it was called on will pop into
109 userspace (if it was a _S, or if the core is part of the vcoremap for a _M).
110
111 Functions that MAY not return will "eat" your reference *IF* they do not return.
112 This means that you must have a reference when you call them (like always), and
113 that reference will be consumed / decref'd for you if the function doesn't
114 return.  Or something similarly appropriate.
115
116 Arguably, for functions that MAY not return, but will always be called with
117 current's reference (proc_yield()), we could get away without giving it an
118 edible reference, and then never eating the ref.  Yield needs to be reworked
119 anyway, so it's not a bit deal yet.
120
121 We do this because when the function does not return, you will not have the
122 chance to decref (your decref code will never run).  We need the reference when
123 going in to keep the object alive (like with any other refcnt).  We can't have
124 the function always eat the reference, since you cannot simply re-incref the
125 pointer (not allowed to incref unless you know you had a good reference).  You'd
126 have to do something like p = pid2proc(p_pid);  It's clunky to do that, easy to
127 screw up, and semantically, if the function returns, then we may still have an
128 interest in p and should decref later.
129
130 The downside is that functions need to determine if they will return or not,
131 which can be a pain (a linear time search when running an _M, for instance,
132 which can suck if we are trying to use a broadcast/logical IPI).
133
134 As the caller, you usually won't know if the function will return or not, so you
135 need to provide a consumable reference.  Current doesn't count.  For example,
136 proc_run() requires a reference.  You can proc_run(p), and use p afterwards, and
137 later decref.  You need to make sure you have a reference, so things like
138 proc_run(pid2proc(55)) works, since pid2proc() increfs for you.  But you cannot
139 proc_run(current), unless you incref current in advance.  Incidentally,
140 proc_running current doesn't make a lot of sense.
141
142 As another example, __proc_startcore() will take your reference and store it
143 in current.  Since it is used by both the __startcore and the interrupt return
144 paths (proc_restartcore() now, formerly called proc_startcore()), we're
145 currently going with the model of "caller makes sure there is a ref for
146 current".  Check its comments for details.
147
148 1.6 Runnable List:
149 ---------------------------
150 Procs on the runnable list need to have a refcnt (other than the +1 for
151 existing).  It's something that cares that the process exists.  We could have
152 had it implicitly be refcnt'd (the fact that it's on the list is enough, sort of
153 as if it was part of the +1 for existing), but that complicates things.  For
154 instance, it is a source of a reference (for the scheduler) and you could not
155 proc_run() a process from the runnable list without worrying about increfing it
156 before hand.  Remember that proc_run() might consume your reference (which
157 actually turns into a current reference, which is later destroyed by decref in
158 abandon_core()).
159
160 1.7 Internal Details for Specific Functions:
161 ---------------------------
162 proc_run(): makes sure enough refcnts are in place for all places that will
163 install current.  This also makes it easier on the system (one big incref(n),
164 instead of n increfs of (1) from multiple cores).  In the off chance current was
165 already set for a core receiving the kernel message, __startcore will decref.
166 Also note that while proc_run() consumes your reference, it's not actually
167 decreffing, so there's no danger within proc_run() of the process dying /
168 __proc_free()ing.
169
170 __proc_startcore(): assumes all references to p are sorted.  *p is already
171 accounted for as if it was current on the core startcore runs on. (there is only
172 one refcnt for both *p and current, not 2 separate ones).
173
174 proc_destroy(): it might not return (if the calling core belongs to the
175 process), so it may eat your reference and you must have an edible reference.
176 It is possible you called proc_destroy(current).  The cleanup of the current
177 will be its own decref, so you need to have a usable/real reference (current
178 doesn't count as an edible reference).  So incref before doing that.  Even if p
179 == current, proc_destroy() can't tell if you sent it p (and had a reference) or
180 current and didn't.
181
182 proc_yield(): this never returns, so it eats your reference.  It will also
183 decref when it abandon_core()s.
184
185 __proc_give_cores() and friends: you call this while holding the lock, but it is
186 possible that your core is in the corelist you gave it.  In this case, it will
187 detect it, and return a bool signalling if an IPI is pending.  It will not
188 consume your reference.  The reasoning behind this is that it is an internal
189 function, and you may want to do other things before decreffing.  There is also
190 a helper function that will unlock and possibly decref/wait for the IPI, called
191 __proc_unlock_ipi_pending().  Use this when it is time to unlock.  It's just a
192 helper, which may go away.
193
194 abandon_core(): it was not given a reference, so it doesn't eat one.  It will
195 decref when it unloads the cr3.  Note that this is a potential performance
196 issue.  When preempting or killing, there are n cores that are fighting for the
197 cacheline to decref.  An alternative would be to have one core decref for all n
198 cores, after it knows all cores unloaded the cr3.  This would be a good use of
199 the checklist (possibly with one cacheline per core).  It would take a large
200 amount of memory for better scalability.
201
202 1.8 Core Request:
203 ---------------------------
204 core_request() is run outside of the process code (for now), though it is fairly
205 intricate.  It's another function that might not return, but the reasons for
206 this vary:
207         1: The process is moving from _S to _M so the return path to userspace won't
208         happen (and sort of will on the new core / the other side), but that will
209         happen when popping into userspace.
210         2: The scheduler is giving the current core to the process, which can kick
211         in via either proc_run() or __proc_give_cores().
212         3: It was a request to give up all cores, which means the current core will
213         receive an IPI (if it wasn't an async call, which isn't handled yet).
214
215 For these reasons, core_request() needs to have an edible reference.
216
217 Also, since core_request calls functions that might not return, there are cases
218 where it will not be able to call abandon_core() and leave process context.
219 This is an example of why we have the fallback case of leaving process context
220 in proc_startcore().  See the section below about process context for more
221 information.
222
223 Eventually, core_request() will be split better, probably with the brutal logic
224 in process.c that would call out some functions in resource.c that actually make
225 choices.
226
227 1.9 Things I Could Have Done But Didn't And Why:
228 ---------------------------
229 Q: Could we have the first reference (existence) mean it could be on the runnable
230 list or otherwise in the proc system (but not other subsystems)?  In this case,
231 proc_run() won't need to eat a reference at all - it will just incref for every
232 current it will set up.
233
234 A: No: if you pid2proc(), then proc_run() but never return, you have (and lose)
235 an extra reference.  We need proc_run() to eat the reference when it does not
236 return.  If you decref between pid2proc() and proc_run(), there's a (rare) race
237 where the refcnt hits 0 by someone else trying to kill it.  While proc_run()
238 will check to see if someone else is trying to kill it, there's a slight chance
239 that the struct will be reused and recreated.  It'll probably never happen, but
240 it could, and out of principle we shouldn't be referencing memory after it's
241 been deallocated.  Avoiding races like this is one of the reasons for our refcnt
242 discipline.
243
244 Q: Could proc_run() always eat your reference, which would make it easier for
245 its implementation?
246
247 A: Yeah, technically, but it'd be a pain, as mentioned above.  You'd need to
248 reaquire a reference via pid2proc, and is rather easy to mess up.
249
250 Q: Could we have made proc_destroy() take a flag, saying whether or not it was
251 called on current and needed a decref instead of wasting an incref?
252
253 A: We could, but won't.  This is one case where the external caller is the one
254 that knows the function needs to decref or not.  But it breaks the convention a
255 bit, doesn't mirror proc_create() as well, and we need to pull in the cacheline
256 with the refcnt anyways.  So for now, no.
257
258 Q: Could we make __proc_give_cores() simply not return if an IPI is coming?
259
260 A: I did this originally, and manually unlocked and __wait_for_ipi()d.  Though
261 we'd then need to deal with it like that for all of the related functions, which
262 doesn't work if you wanted to do something afterwards (like schedule(p)).  Also
263 these functions are meant to be internal helpers, so returning the bool makes
264 more sense.  It eventually led to having __proc_unlock_ipi_pending(), which made
265 proc_destroy() much cleaner and helped with a general model of dealing with
266 these issues.  Win-win.
267
268 2. When Do We Really Leave "Process Context"?
269 ===========================
270 2.1 Overview
271 ---------------------------
272 First off, it's not really "process context" in the way Linux deals with it.  We
273 aren't operating in kernel mode on behalf of the process (always).  We are
274 specifically talking about when a process's cr3 is loaded on a core.  Usually,
275 current is also set (the exception for now is when processing ARSCs).
276
277 There are a couple different ways to do this.  One is to never unload a context
278 until something new is being run there (handled solely in __proc_startcore()).
279 Another way is to always explicitly leave the core, like by abandon_core()ing.
280
281 The issue with the former is that you could have contexts sitting around for a
282 while, and also would have a bit of extra latency when __proc_free()ing during
283 someone *else's* __proc_startcore() (though that could be avoided if it becomes
284 a real issue, via some form of reaping).  You'll also probably have excessive
285 decrefs (based on the interactions between proc_run() and __startcore()).
286
287 The issue with the latter is excessive TLB shootdowns and corner cases.  There
288 could be some weird cases (in core_request() for example) where the core you are
289 running on has the context loaded for proc A on a mgmt core, but decides to give
290 it to proc B.
291
292 If no process is running there, current == 0 and boot_cr3 is loaded, meaning no
293 process's context is loaded.
294
295 2.2 Here's how it is done now:
296 ---------------------------
297 We try to proactively leave, but have the ability to stay in context til
298 __proc_startcore() to handle the corner cases (and to maybe cut down the TLB
299 flushes later).  To stop proactively leaving, just change abandon_core() to not
300 do anything with current/cr3.  You'll see weird things like processes that won't
301 die until their old cores are reused.  The reason we proactively leave context
302 is to help with sanity for these issues, and also to avoid decref's in
303 __startcore().
304
305 A couple other details: __startcore() sorts the extra increfs, and
306 __proc_startcore() sorts leaving the old context.  Anytime a __startcore kernel
307 message is sent, the sender increfs in advance for the current refcnt.  If that
308 was in error, __startcore decrefs.  __proc_startcore(), which the last moment
309 before we *must* have the cr3/current issues sorted, does the actual check if
310 there was an old process there or not, while it handles the lcr3 (if necessary).
311 In general, lcr3's ought to have refcnts near them, or else comments explaining
312 why not.
313
314 So we leave process context when told to do so (__death/abandon_core()) or if
315 another process is run there.  The _M code is such that a proc will stay on its
316 core until it receives a message, and that message would cleanup/restore a
317 generic context (boot_cr3).  A _S could stay on its core until another _S came
318 in.  This is much simpler for cases when a timer interrupt goes off to force a
319 schedule() decision.  It also avoids a TLB flush in case the scheduler picked
320 that same proc to run again.  This could also happen to an _M, if for some
321 reason it was given a management core (!!!) or some other event happened that
322 caused some management/scheduling function to run on one of it's cores (perhaps
323 it asked).
324
325 proc_yield() abandons the core / leaves context.
326
327 2.3 Other issues:
328 ---------------------------
329 Note that dealing with interrupting processes that are in the kernel is tricky.
330 There is no true process context, so we can't leave a core until the kernel is
331 in a "safe place", i.e. it's state is bundled enough that it can be recontinued
332 later.  Calls of this type are routine kernel messages, executed at a convenient
333 time (specifically, before we return to userspace in proc_restartcore().
334
335 This same thing applies to __death messages.  Even though a process is dying, it
336 doesn't mean we can just drop whatever the kernel was doing on its behalf.  For
337 instance, it might be holding a reference that will never get decreffed if its
338 stack gets dropped.
339
340 3. Leaving the Kernel Stack:
341 ===========================
342 Just because a message comes in saying to kill a process, it does not mean we
343 should immediately abandon_core().  The problem is more obvious when there is
344 a preempt message, instead of a death message, but either way there is state
345 that needs cleaned up (refcnts that need downed, etc).
346
347 The solution to this is rather simple: don't abandon right away.  That was
348 always somewhat the plan for preemption, but was never done for death.  And
349 there are several other cases to worry about too.  To enforce this, we expand
350 the old "active messages" into a generic work execution message (a kernel
351 message) that can be delayed or shipped to another core.  These types of
352 messages will not be executed immediately on the receiving pcore - instead they
353 are on the queue for "when there's nothing else to do in the kernel", which is
354 checked in smp_idle() and before returning to userspace in proc_restartcore().
355 Additionally, these kernel messages can also be queued on an alarm queue,
356 delaying their activation as part of a generic kernel alarm facility.
357
358 One subtlety is that __proc_startcore() shouldn't check for messages, since it
359 is called by __startcore (a message).  Checking there would run the messages out
360 of order, which is exactly what we are trying to avoid (total chaos).  No one
361 should call __proc_startcore, other than proc_restartcore() or __startcore().
362 If we ever have functions that do so, if they are not called from a message,
363 they must check for outstanding messages.
364
365 This last subtlety is why we needed to change proc_run()'s _S case to use a
366 local message instead of calling proc_starcore (and why no one should ever call
367 proc_startcore()).  We could unlock, thereby freeing another core to change the
368 proc state and send a message to us, then try to proc_startcore, and then
369 reading the message before we had installed current or had a userspace TF to
370 preempt, and probably a few other things.  Treating _S as a local message is
371 cleaner, begs to be merged in the code with _M's code, and uses the messaging
372 infrastructure to avoid all the races that it was created to handle.
373
374 Incidentally, we don't need to worry about missing messages while trying to pop
375 back to userspace from __proc_startcore, since an IPI will be on the way
376 (possibly a self-ipi caused by the __kernel_message() handler).  This is also
377 why we needed to make process_routine_kmsg() keep interrupts disabled when it
378 stops (there's a race between checking the queue and disabling ints).
379
380 4. Preemption and Notification Issues:
381 ===========================
382 4.1: Message Ordering and Local Calls:
383 ---------------------------
384 Since we go with the model of cores being told what to do, there are issues
385 with messages being received in the wrong order.  That is why we have the
386 kernel messages (guaranteed, in-order delivery), with the proc-lock protecting
387 the send order.  However, this is not enough for some rare races.
388
389 Local calls can also perform the same tasks as messages (calling
390 proc_destroy() while a death IPI is on its way). We refer to these calls as
391 messing with "local fate" (compared to global state (we're clever).
392 Preempting a single vcore doesn't change the process's state).  These calls
393 are a little different, because they also involve a check to see if it should
394 perform the function or other action (e.g., death just idling and waiting for
395 an IPI instead of trying to kill itself), instead of just blindly doing
396 something.
397
398 4.1.1: Possible Solutions
399 ----------------
400 There are two ways to deal with this.  One (and the better one, I think) is to
401 check state, and determine if it should proceed or abort.  This requires that
402 all local-fate dependent calls always have enough state, meaning that any
403 function that results in sending a directive to a vcore store enough info in
404 the proc struct that a local call can determine if it should take action or
405 abort.  This might be sufficient.  This works for death already, since you
406 aren't supposed to do anything other than die (and restore any invariants
407 first, handled in Section 3).  We'll go with this way.
408
409 The other way is to send the work (including the checks) in a self-ipi kernel
410 message.  This will guarantee that the message is executed after any existing
411 messages (making the k_msg queue the authority for what should happen to a
412 core).  The check is also performed later (when the k_msg executes).  There
413 are a couple issues with this: if we allow the local core to send itself an
414 k_msg that could be out of order (meaning it should not be sent, and is only
415 sent due to ignorance of its sealed fate), AND if we return the core to the
416 idle-core-list once its fate is sealed, we need to detect that the message is
417 for the wrong process and that the process is in the wrong state.  To do this,
418 we probably need local versioning on the pcore so it can detect that the
419 message is late/wrong.  We might get by with just the proc* (though that is
420 tricky with death and proc reuse), so long as we don't allow new startcores
421 for a proc until AFTER the preemption is completed.
422
423 4.2: Preempt-Served Flag
424 ----------------
425 We want to be able to consider a pcore free once its owning proc has dealt
426 with removing it (not necessarily taken from the vcoremap, but at least it is
427 a done-deal that the core will go away and the messages are sent).  This
428 allows a scheduler-like function to easily take a core and then give it to
429 someone else, without waiting for each vcore to respond, saying that the pcore
430 is free/idle.
431
432 Since we want to keep the pcore in the vcoremap, we need another signal to let
433 a process know a message is already on its way.  preempt_pending is a signal
434 to userspace that the alarm was set, not that an actual message is on its way
435 and that a vcore's fate is sealed.  Since we can't use a pcore's presence in
436 the vcoremap to determine that the core should be revoked, we have to check
437 the "fate sealed"/preempt-served flag. 
438
439 It's a bit of a pain to have this flag, just to resolve this race in the
440 kernel, though the local call would have to check the vcoremap anyway,
441 incurring a cache miss if we go with using the vcoremap to signal the
442 impending message.
443
444 The preempt_pending flag is actual a timestamp, with the expiration time of
445 the core at which the message will be sent.  We could try to use that, but
446 since alarms aren't fired at exactly the time they are scheduled, the message
447 might not actually be sent yet (though it will, really soon).  Still, we'll
448 just go with the preempt-served flag for now.
449
450 4.3: Impending Notifications
451 ----------------
452 It's also possible that there is an impending notification.  There's no change
453 in fate (though there could be a fate-changing preempt on its way), just the
454 user wants a notification handler to run.  We need a flag anyways for this
455 (discussed below), so proc_yield() or whatever other local call we have can
456 check this flag as well.  
457
458 Though for proc_yield(), it doesn't care if a notification is on its way (can
459 be dependent on a flag to yield from userspace, based on the nature of the
460 yield (which still needs to be sorted)).  If the yield is in response to a
461 preempt_pending, it actually should yield and not receive the notification.
462 So it should destroy its vcoreid->pcoreid mapping and abandon_core().  When
463 that notification hits, it will be for a proc that isn't current, and will be
464 ignored (it will get run the next time that vcore fires up, handled below).
465
466 There is a slight chance that the same proc will run on that pcore, but with a
467 different vcoreid.  In the off chance this happens, the new vcore will get a
468 spurious notification.  Userspace needs to be able to handle spurious
469 notifications anyways, (there are a couple other cases, and in general it's
470 not hard to do), so this is not a problem.  Instead of trying to have the
471 kernel ignore the notification, we just send a spurious one.  A crappy
472 alternative would be to send the vcoreid with the notification, but that would
473 mean we can't send a generic message (broadcast) to a bunch of cores, which
474 will probably be a problem later.
475
476 Note that this specific case is because the "local work message" gets
477 processed out of order with respect to the notification.  And we want this in
478 that case, since that proc_yield() is more important than the notification.
479
480 4.4: Preemption / Allocation Phases and Alarm Delays
481 ---------------------------
482 A per-vcore preemption phase starts when the kernel marks the core's
483 preempt_pending flag/counter and can includes the time when an alarm is
484 waiting to go off to reclaim the core.  The phase ends when the vcore's pcore
485 is reclaimed, either as a result of the kernel taking control, or because a
486 process voluntarily yielded.
487
488 Specifically, the preempt_pending variable is actually a timestamp for when
489 the core will be revoked (this assumes some form of global time, which we need
490 anyways).  If its value is 0, then there is no preempt-pending, it is not in a
491 phase, and the vcore can be given out again. 
492
493 When a preempt alarm goes off, the alarm only means to check a process for
494 expired vcores.  If the vcore has been yielded while the alarm was pending,
495 the preempt_pending flag will be reset to 0.  To speed up the search for
496 vcores to preempt, there's a circular buffer corelist in the proc struct, with
497 vcoreids of potential suspects.  Or at least this will exist at some point.
498 Also note that the preemption list isn't bound to a specific alarm: you can
499 check the list at any time (not necessarily on a specific alarm), and you can
500 have spurious alarms (the list is empty, so it'll be a noop).
501
502 Likewise, a global preemption phase is when an entire MCP is getting
503 gang_prempted, and the global deadline is set.  A function can quickly check
504 to see if the process responded, since the list of vcores with preemptions
505 pending will be empty.
506
507 It seems obvious, but we do not allow allocation of a vcore during its
508 preemption phase.  The main reason is that it can potentially break
509 assumptions about the vcore->pcore mapping and can result in multiple
510 instances of the same vcore on different pcores.  Imagine a preempt message
511 sent to a pcore (after the alarm goes off), meanwhile that vcore/pcore yields
512 and the vcore reactivates somewhere else.  There is a potential race on the
513 preempt_tf state: the new vcore is reading while the old is writing.  This
514 issue is sorted naturally: the vcore entry in the vcoremap isn't cleared until
515 the vcore/pcore is actually yielded/taken away, so the code looking for a free
516 vcoreid slot will not try to use it.
517
518 Note that if we didn't design the alarm system to simply check for
519 preemptions (perhaps it has a stored list of vcores to preempt), then we
520 couldn't end the preempt-phase until the alarm was sorted.  If that is the
521 case, we could easily give out a vcore that had been yielded but was still in
522 a preempt-phase.  Stopping an alarm would be tricky too, since there could be
523 lots of vcores in different states that need to be sorted by the alarm (so
524 ripping it out isn't enough).  Setting a flag might not be enough either.
525 Vcore version numbers/history (as well as global proc histories) is a pain I'd
526 like to avoid too.  So don't change the alarm / delayed preemption system
527 without thinking about this.
528
529 Also, allowing a vcore to restart while preemptions are pending also mucks
530 with keeping the vcore mapping "old" (while the message is in flight).  A
531 pcore will want to use that to determine which vcore is running on it.  It
532 would be possible to keep a pcoremap for the reverse mapping out of sync, but
533 that seems like a bad idea.  In general, having the pcoremap is a good idea
534 (whenever we talk about a vcoremap, we're usually talking about both
535 directions: "the vcore->pcore mapping").
536
537 4.5: Global Preemption Flags
538 ---------------------------
539 If we are trying to preempt an entire process at the same time, instead of
540 playing with the circular buffer of vcores pending preemption, we could have a
541 global timer as well.  This avoids some O(n) operations, though it means that
542 userspace needs to check two "flags" (expiration dates) when grabbing its
543 preempt-critical locks.
544
545 4.6: Notifications Mixed with Preemption and Sleeping
546 ---------------------------
547 It is possible that notifications will mix with preemptions or come while a
548 process is not running.  Ultimately, the process wants to be notified on a
549 given vcore.  Whenever we send an active notification, we set a flag in procdata
550 (notif_pending).  If the vcore is offline, we don't bother sending the IPI/notif
551 message.  The kernel will make sure it runs the notification handler (as well as
552 restoring the preempt_tf) the next time that vcore is restarted.  Note that
553 userspace can toggle this, so they can handle the notifications from a different
554 core if it likes, or they can independently send a notification.
555
556 Note we use notif_pending to detect if an IPI was missed while notifs were
557 disabled (this is done in pop_ros_tf() by userspace).  The overall meaning of
558 notif_pending is that a vcore wants to be IPI'd.  The IPI could be in-flight, or
559 it could be missed.  Since notification IPIs can be spurious, when we have
560 potential races, we err on the side of sending.  This happens when pop_ros_tf()
561 notifies itself, and when the kernel starts a vcore in it's notif handler if it
562 was preempted and notif was pending.  In the latter case, the kernel will put
563 the preempt_tf in the notif_tf, so userspace can restart that at its leisure.
564
565 If a vcore has a preempt_pending, we will still send the active notification
566 (IPI).  The core ought to get a notification for the preemption anyway, so we
567 need to be able to send one.  Additionally, once the vcore is handling that
568 preemption notification, it will have notifs disabled, which will prevent us
569 from sending any extra notifications anyways.
570  
571 4.7: Notifs While a Preempt Message is Served
572 ---------------------------
573 It is possible to have the kernel handling a notification k_msg and to have a
574 preempt k_msg in the queue (preempt-served flag is set).  Ultimately, what we
575 want is for the core to be preempted and the notification handler to run on
576 the next execution.  Both messages are in the k_msg queue for "a convenient
577 time to leave the kernel" (I'll have a better name for that later).  What we
578 do is execute the notification handler and jump to userspace.  Since there is
579 still an k_msg in the queue (and we self_ipi'd ourselves, it's part of how
580 k_msgs work), the IPI will fire and push us right back into the kernel to
581 execute the preemption, and the notif handler's context will be saved in the
582 preempt_tf (ready to go when the vcore gets started again).
583
584 We could try to just leave the notif_pending flag set and ignore the message,
585 but that would involve inspecting the queue for the preempt k_msg.
586 Additionally, a preempt k_msg can arrive anyway.  Finally, it's possible to have
587 another message in the queue between the notif and the preempt, and it gets ugly
588 quickly trying to determine what to do.
589
590 4.8: When a Pcore is "Free"
591 ---------------------------
592 There are a couple ways to handle pcores.  One approach would be to not
593 consider them free and able to be given to another process until the old
594 process is completely removed (abandon_core()).  Another approach is to free
595 the core once its fate is sealed (which we do).  This probably gives more
596 flexibility in schedule()-like functions (no need to wait to give the core
597 out), quicker dispatch latencies, less contention on shared structs (like the
598 idle-core-map), etc.
599
600 Also, we don't remove the pcore from the vcoremap, even if it is being
601 allocated to another core (the same pcore can exist in two vcoremaps, contrary
602 to older statements).  Taking the pcore from the vcoremap would mean some
603 non-fate related local calls (sys_get_vcoreid()) will fail, since the vcoreid
604 is gone!  Additionally, we don't need a vcoreid in the k_msg (we would have if
605 we could not use the vcore/pcoremappings).  There should not be any issues
606 with the new process sending messages to the pcore before the core is sorted,
607 since k_msgs are delivered in order.
608
609 Another tricky part is the seq_ctr used to signal userspace of changes to the
610 coremap or num_vcores (coremap_seqctr).  While we may not even need this in the
611 long run, it still seems like it could be useful.  The trickiness comes from
612 when we update the seq_ctr when we are unmapping vcores on the receive side of a
613 message (like __death or __preempt).  We'd rather not have each pcore contend on
614 the seq_ctr cache line (let alone any locking) while they perform a somewhat
615 data-parallel task.  So we continue to have the sending core handle the seq_ctr
616 upping and downing.  This works, since the "unlocking" happens after messages
617 are sent, which means the receiving core is no longer in userspace (if there is
618 a delay, it is because the remote core is in the kernel, possibly with
619 interrupts disabled).  Because of this, userspace will be unable to read the new
620 value of the seq_ctr before the IPI hits and does the unmapping that the seq_ctr
621 protects/advertises.  This is most likely true.  It wouldn't be if the "last IPI
622 was sent" flag clears before the IPI actually hit the other core.
623
624 4.9: Future Broadcast/Messaging Needs
625 ---------------------------
626 Currently, messaging is serialized.  Broadcast IPIs exist, but the kernel
627 message system is based on adding an k_msg to a list in a pcore's
628 per_cpu_info.  Further the sending of these messages is in a loop.  In the
629 future, we would like to have broadcast messaging of some sort (literally a
630 broadcast, like the IPIs, and if not that, then a communication tree of
631 sorts).  
632
633 Given those desires, we want to make sure that no message we send needs
634 details specific to a pcore (such as the vcoreid running on it, a history
635 number, or anything like that).  Thus no k_msg related to process management
636 should have anything that cannot apply to the entire process.  At this point,
637 most just have a struct proc *.  A pcore ought to be able to figure out what
638 is happening based on the pcoremap, information in the struct proc, and in the
639 preempt struct in procdata.
640
641 4.10: Other Things We Thought of but Don't Like
642 ---------------------------
643 All local fate-related work is sent as a self k_msg, to enforce ordering.
644 It doesn't capture the difference between a local call and a remote k_msg.
645 The k_msg has already considered state and made its decision.  The local call
646 is an attempt.  It is also unnecessary, if we put in enough information to
647 make a decision in the proc struct.  Finally, it caused a few other problems
648 (like needing to detect arbitrary stale messages).
649
650 Overall message history: doesn't work well when you do per-core stuff, since
651 it will invalidate other messages for the process.  We then though of a pcore
652 history counter to detect stale messages.  Don't like that either.  We'd have
653 to send the history in the message, since it's a per-message, per-core
654 expiration.  There might be other ways around this, but this doesn't seem
655 necessary.
656
657 Alarms have pointers to a list of which cores should be preempted when that
658 specific alarm goes off (saved with the alarm).  Ugh.  It gets ugly with
659 multiple outstanding preemptions and cores getting yielded while the alarms
660 sleep (and possibly could get reallocated, though we'd make a rule to prevent
661 that).  Like with notifications, being able to handle spurious alarms and
662 thinking of an alarm as just a prod to check somewhere is much more flexible
663 and simple.  It is similar to generic messages that have the actual important
664 information stored somewhere else (as with allowing broadcasts, with different
665 receivers performing slightly different operations).
666
667 Synchrony for messages (wanting a response to a preempt k_msg, for example)
668 sucks.  Just encode the state of impending fate in the proc struct, where it
669 belongs.  Additionally, we don't want to hold the proc lock even longer than
670 we do now (which is probably too long as it is).  Finally, it breaks a golden
671 rule: never wait while holding a lock: you will deadlock the system (e.g. if
672 the receiver is already in the kernel spinning on the lock).  We'd have to
673 send messages, unlock (which might cause a message to hit the calling pcore,
674 as in the case of locally called proc_destroy()), and in the meantime some
675 useful invariant might be broken.
676
677 We also considered using the transition stack as a signal that a process is in
678 a notification handler.  The kernel can inspect the stack pointer to determine
679 this.  It's possible, but unnecessary.
680
681 5. current_tf
682 ===========================
683 current_tf is a per-core macro that returns a struct trapframe * that points
684 back on the kernel stack to the user context that was running on the given core
685 when an interrupt or trap happened.  Saving the reference to the TF helps
686 simplify code that needs to do something with the TF (like save it and pop
687 another TF).  This way, we don't need to pass the context all over the place,
688 especially through code that might not care.
689
690 current_tf should go along with current.  It's the current_tf of the current
691 process.  Withouth 'current', it has no meaning.
692
693 It does not point to kernel trapframes, which is important when we receive an
694 interrupt in the kernel.  At one point, we were (hypothetically) clobbering the
695 reference to the user trapframe, and were unable to recover.  We can get away
696 with this because the kernel always returns to its previous context from a
697 nested handler (via iret on x86).  
698
699 In the future, we may need to save kernel contexts and may not always return via
700 iret.  At which point, if the code path is deep enough that we don't want to
701 carry the TF pointer, we may revisit this.  Until then, current_tf is just for
702 userspace contexts, and is simply stored in per_cpu_info.
703
704 6. Locking!
705 ===========================
706 6.1: proc_lock
707 ---------------------------
708 Currently, all locking is done on the proc_lock.  It's main goal is to protect
709 the vcore mapping (vcore->pcore and vice versa).  As of Apr 2010, it's also used
710 to protect changes to the address space and the refcnt.  Eventually the refcnt
711 will be handled with atomics, and the address space will have it's own MM lock.  
712
713 We grab the proc_lock all over the place, but we try to avoid it whereever
714 possible - especially in kernel messages or other places that will be executed
715 in parallel.  One place we do grab it but would like to not is in proc_yield().  
716 We don't always need to grab the proc lock.  Here are some examples:
717
718 6.1.1: Lockless Notifications:
719 -------------
720 We don't lock when sending a notification.  We want the proc_lock to not be an
721 irqsave lock (discussed below).  Since we might want to send a notification from
722 interrupt context, we can't grab the proc_lock if it's a regular lock.  
723
724 This is okay, since the proc_lock is only protecting the vcoremapping.  We could
725 accidentally send the notification to the wrong pcore.  The __notif handler
726 checks to make sure it is the right process, and all _M processes should be able
727 to handle spurious notifications.  This assumes they are still _M.
728
729 If we send it to the wrong pcore, there is a danger of losing the notif, since
730 it didn't go to the correct vcore.  That would happen anyway, (the vcore is
731 unmapped, or in the process of mapping).  The notif_pending flag will be caught
732 when the vcore is started up next time (and that flag was set before reading the
733 vcoremap).
734
735 6.1.2: Local get_vcoreid():
736 -------------
737 It's not necessary to lock while checking the vcoremap if you are checking for
738 the core you are running on (e.g. pcoreid == core_id()).  This is because all
739 unmappings of a vcore are done on the receive side of a routine kmsg, and that
740 code cannot run concurrently with the code you are running.  
741
742 6.2: irqsave
743 ---------------------------
744 The proc_lock used to be an irqsave lock (meaning it disables interrupts and can
745 be grabbed from interrupt context).  We made it a regular lock for a couple
746 reasons.  The immediate one was it was causing deadlocks due to some other
747 ghetto things (blocking on the frontend server, for instance).  More generally,
748 we don't want to disable interrupts for long periods of time, so it was
749 something worth doing anyway.  
750
751 This means that we cannot grab the proc_lock from interrupt context.  This
752 includes having schedule called from an interrupt handler (like the
753 timer_interrupt() handler), since it will call proc_run.  Right now, we actually
754 do this, which we shouldn't, and that will eventually get fixed.  The right
755 answer is that the actual work of running the scheduler should be a routine
756 kmsg, similar to how Linux sets a bit in the kernel that it checks on the way
757 out to see if it should run the scheduler or not.
758
759 7. TLB Coherency
760 ===========================
761 When changing or removing memory mappings, we need to do some form of a TLB
762 shootdown.  Normally, this will require sending an IPI (immediate kmsg) to
763 every vcore of a process to unmap the affected page.  Before allocating that
764 page back out, we need to make sure that every TLB has been flushed.  
765
766 One reason to use a kmsg over a simple handler is that we often want to pass a
767 virtual address to flush for those architectures (like x86) that can
768 invalidate a specific page.  Ideally, we'd use a broadcast kmsg (doesn't exist
769 yet), though we already have simple broadcast IPIs.
770
771 7.1 Initial Stuff
772 ---------------------------
773 One big issue is whether or not to wait for a response from the other vcores
774 that they have unmapped.  There are two concerns: 1) Page reuse and 2) User
775 semantics.  We cannot give out the physical page while it may still be in a
776 TLB (even to the same process.  Ask us about the pthread_test bug).
777
778 The second case is a little more detailed.  The application may not like it if
779 it thinks a page is unmapped or protected, and it does not generate a fault.
780 I am less concerned about this, especially since we know that even if we don't
781 wait to hear from every vcore, we know that the message was delivered and the
782 IPI sent.  Any cores that are in userspace will have trapped and eventually
783 handle the shootdown before having a chance to execute other user code.  The
784 delays in the shootdown response are due to being in the kernel with
785 interrupts disabled (it was an IMMEDIATE kmsg).
786
787 7.2 RCU
788 ---------------------------
789 One approach is similar to RCU.  Unmap the page, but don't put it on the free
790 list.  Instead, don't reallocate it until we are sure every core (possibly
791 just affected cores) had a chance to run its kmsg handlers.  This time is
792 similar to the RCU grace periods.  Once the period is over, we can then truly
793 free the page.
794
795 This would require some sort of RCU-like mechanism and probably a per-core
796 variable that has the timestamp of the last quiescent period.  Code caring
797 about when this page (or pages) can be freed would have to check on all of the
798 cores (probably in a bitmask for what needs to be freed).  It would make sense
799 to amortize this over several RCU-like operations.
800
801 7.3 Checklist
802 ---------------------------
803 It might not suck that much to wait for a response if you already sent an IPI,
804 though it incurs some more cache misses.  If you wanted to ensure all vcores
805 ran the shootdown handler, you'd have them all toggle their bit in a checklist
806 (unused for a while, check smp.c).  The only one who waits would be the
807 caller, but there still are a bunch of cache misses in the handlers.  Maybe
808 this isn't that big of a deal, and the RCU thing is an unnecessary
809 optimization.
810
811 7.4 Just Wait til a Context Switch
812 ---------------------------
813 Another option is to not bother freeing the page until the entire process is
814 descheduled.  This could be a very long time, and also will mess with
815 userspace's semantics.  They would be running user code that could still
816 access the old page, so in essence this is a lazy munmap/mprotect.  The
817 process basically has the page in pergatory: it can't be reallocated, and it
818 might be accessible, but can't be guaranteed to work.
819
820 The main benefit of this is that you don't need to send the TLB shootdown IPI
821 at all - so you don't interfere with the app.  Though in return, they have
822 possibly weird semantics.  One aspect of these weird semantics is that the
823 same virtual address could map to two different pages - that seems like a
824 disaster waiting to happen.  We could also block that range of the virtual
825 address space from being reallocated, but that gets even more tricky.
826
827 One issue with just waiting and RCU is memory pressure.  If we actually need
828 the page, we will need to enforce an unmapping, which sucks a little.
829
830 7.5 Bulk vs Single
831 ---------------------------
832 If there are a lot of pages being shot down, it'd be best to amortize the cost
833 of the kernel messages, as well as the invlpg calls (single page shootdowns).
834 One option would be for the kmsg to take a range, and not just a single
835 address.  This would help with bulk munmap/mprotects.  Based on the number of
836 these, perhaps a raw tlbflush (the entire TLB) would be worth while, instead
837 of n single shots.  Odds are, that number is arch and possibly workload
838 specific.
839
840 For now, the plan will be to send a range and have them individually shot
841 down.
842
843 7.6 Don't do it
844 ---------------------------
845 Either way, munmap/mprotect sucks in an MCP.  I recommend not doing it, and
846 doing the appropriate mmap/munmap/mprotects in _S mode.  Unfortunately, even
847 our crap pthread library munmaps on demand as threads are created and
848 destroyed.  The vcore code probably does in the bowels of glibc's TLS code
849 too, though at least that isn't on every user context switch.
850
851 7.7 Local memory
852 ---------------------------
853 Private local memory would help with this too.  If each vcore has its own
854 range, we won't need to send TLB shootdowns for those areas, and we won't have
855 to worry about weird application semantics.  The downside is we would need to
856 do these mmaps in certain ranges in advance, and might not easily be able to
857 do them remotely.  More on this when we actually design and build it.
858
859 7.8 Future Hardware Support
860 ---------------------------
861 It would be cool and interesting if we had the ability to remotely shootdown
862 TLBs.  For instance, all cores with cr3 == X, shootdown range Y..Z.  It's
863 basically what we'll do with the kernel message and the vcoremap, but with
864 magic hardware.
865
866 7.9 Current Status
867 ---------------------------
868 For now, we just send a kernel message to all vcores to do a full TLB flush,
869 and not to worry about checklists, waiting, or anything.  This is due to being
870 short on time and not wanting to sort out the issue with ranges.  The way
871 it'll get changed to is to send the kmsg with the range to the appropriate
872 cores, and then maybe put the page on the end of the freelist (instead of the
873 head).  More to come.
874
875 8. TBD
876 ===========================