WIP-9ns
[akaros.git] / Documentation / process-internals.txt
index 4b77c99..2bb5338 100644 (file)
@@ -11,11 +11,12 @@ Contents:
 2. When Do We Really Leave "Process Context"?
 3. Leaving the Kernel Stack
 4. Preemption and Notification Issues
-5. current_tf and owning_proc
+5. current_ctx and owning_proc
 6. Locking!
 7. TLB Coherency
 8. Process Management
-9. TBD
+9. On the Ordering of Messages
+10. TBD
 
 1. Reference Counting
 ===========================
@@ -115,7 +116,7 @@ Refcnting and especially decreffing gets tricky when there are functions that
 MAY not return.  proc_restartcore() does not return (it pops into userspace).
 proc_run() used to not return, if the core it was called on would pop into
 userspace (if it was a _S, or if the core is part of the vcoremap for a _M).
-This doesn't happen anymore, since we have cur_tf in the per-cpu info.
+This doesn't happen anymore, since we have cur_ctx in the per-cpu info.
 
 Functions that MAY not return will "eat" your reference *IF* they do not return.
 This means that you must have a reference when you call them (like always), and
@@ -264,7 +265,7 @@ it to proc B.
 If no process is running there, current == 0 and boot_cr3 is loaded, meaning no
 process's context is loaded.
 
-All changes to cur_proc, owning_proc, and cur_tf need to be done with
+All changes to cur_proc, owning_proc, and cur_ctx need to be done with
 interrupts disabled, since they change in interrupt handlers.
 
 2.2 Here's how it is done now:
@@ -387,12 +388,14 @@ something.
 ----------------
 There are two ways to deal with this.  One (and the better one, I think) is to
 check state, and determine if it should proceed or abort.  This requires that
-all local-fate dependent calls always have enough state, meaning that any
-function that results in sending a directive to a vcore store enough info in
-the proc struct that a local call can determine if it should take action or
-abort.  This might be sufficient.  This works for death already, since you
-aren't supposed to do anything other than die (and restore any invariants
-first, handled in Section 3).  We'll go with this way.
+all local-fate dependent calls always have enough state to do its job.  In the
+past, this meant that any function that results in sending a directive to a
+vcore store enough info in the proc struct that a local call can determine if
+it should take action or abort.  In the past, we used the vcore/pcoremap as a
+way to send info to the receiver about what vcore they are (or should be).
+Now, we store that info in pcpui (for '__startcore', we send it as a
+parameter.  Either way, the general idea is still true: local calls can
+proceed when they are called, and not self-ipi'd to a nebulous later time.
 
 The other way is to send the work (including the checks) in a self-ipi kernel
 message.  This will guarantee that the message is executed after any existing
@@ -411,23 +414,29 @@ for a proc until AFTER the preemption is completed.
 4.2: Preempt-Served Flag
 ----------------
 We want to be able to consider a pcore free once its owning proc has dealt
-with removing it (not necessarily taken from the vcoremap, but at least it is
-a done-deal that the core will go away and the messages are sent).  This
-allows a scheduler-like function to easily take a core and then give it to
-someone else, without waiting for each vcore to respond, saying that the pcore
-is free/idle.
-
-Since we want to keep the pcore in the vcoremap, we need another signal to let
-a process know a message is already on its way.  preempt_pending is a signal
-to userspace that the alarm was set, not that an actual message is on its way
-and that a vcore's fate is sealed.  Since we can't use a pcore's presence in
-the vcoremap to determine that the core should be revoked, we have to check
-the "fate sealed"/preempt-served flag. 
-
-It's a bit of a pain to have this flag, just to resolve this race in the
-kernel, though the local call would have to check the vcoremap anyway,
-incurring a cache miss if we go with using the vcoremap to signal the
-impending message.
+with removing it.  This allows a scheduler-like function to easily take a core
+and then give it to someone else, without waiting for each vcore to respond,
+saying that the pcore is free/idle.
+
+We used to not unmap until we were in '__preempt' or '__death', and we needed
+a flag to tell yield-like calls that a message was already on the way and to
+not rely on the vcoremap.  This is pretty fucked up for a number of reasons,
+so we changed that.  But we still wanted to know when a preempt was in
+progress so that the kernel could avoid giving out the vcore until the preempt
+was complete.
+
+Here's the scenario: we send a '__startcore' to core 3 for VC5->PC3.  Then we
+quickly send a '__preempt' to 3, and then a '__startcore' to core 4 (a
+different pcore) for VC5->PC4.  Imagine all of this happens before the first
+'__startcore' gets processed (IRQ delay, fast ksched, whatever).  We need to
+not run the second '__startcore' on pcore 4 before the preemption has saved
+all of the state of the VC5.  So we spin on preempt_served (which may get
+renamed to preempt_in_progress).  We need to do this in the sender, and not
+the receiver (not in the kmsg), because the kmsgs can't tell which one they
+are.  Specifically, the first '__startcore' on core 3 runs the same code as
+the '__startcore' on core 4, working on the same vcore.  Anything we tell VC5
+will be seen by both PC3 and PC4.  We'd end up deadlocking on PC3 while it
+spins waiting for the preempt message that also needs to run on PC3.
 
 The preempt_pending flag is actual a timestamp, with the expiration time of
 the core at which the message will be sent.  We could try to use that, but
@@ -498,7 +507,7 @@ assumptions about the vcore->pcore mapping and can result in multiple
 instances of the same vcore on different pcores.  Imagine a preempt message
 sent to a pcore (after the alarm goes off), meanwhile that vcore/pcore yields
 and the vcore reactivates somewhere else.  There is a potential race on the
-preempt_tf state: the new vcore is reading while the old is writing.  This
+vcore_ctx state: the new vcore is reading while the old is writing.  This
 issue is sorted naturally: the vcore entry in the vcoremap isn't cleared until
 the vcore/pcore is actually yielded/taken away, so the code looking for a free
 vcoreid slot will not try to use it.
@@ -537,18 +546,19 @@ process is not running.  Ultimately, the process wants to be notified on a
 given vcore.  Whenever we send an active notification, we set a flag in procdata
 (notif_pending).  If the vcore is offline, we don't bother sending the IPI/notif
 message.  The kernel will make sure it runs the notification handler (as well as
-restoring the preempt_tf) the next time that vcore is restarted.  Note that
+restoring the vcore_ctx) the next time that vcore is restarted.  Note that
 userspace can toggle this, so they can handle the notifications from a different
 core if it likes, or they can independently send a notification.
 
 Note we use notif_pending to detect if an IPI was missed while notifs were
-disabled (this is done in pop_ros_tf() by userspace).  The overall meaning of
-notif_pending is that a vcore wants to be IPI'd.  The IPI could be in-flight, or
-it could be missed.  Since notification IPIs can be spurious, when we have
-potential races, we err on the side of sending.  This happens when pop_ros_tf()
-notifies itself, and when the kernel starts a vcore in it's notif handler if it
-was preempted and notif was pending.  In the latter case, the kernel will put
-the preempt_tf in the notif_tf, so userspace can restart that at its leisure.
+disabled (this is done in pop_user_ctx() by userspace).  The overall meaning
+of notif_pending is that a vcore wants to be IPI'd.  The IPI could be
+in-flight, or it could be missed.  Since notification IPIs can be spurious,
+when we have potential races, we err on the side of sending.  This happens
+when pop_user_ctx() notifies itself, and when the kernel makes sure to start a
+vcore in vcore context if a notif was pending.  This was simplified a bit over
+the years by having uthreads always get saved into the uthread_ctx (formerly
+the notif_tf), instead of in the old preempt_tf (which is now the vcore_ctx).
 
 If a vcore has a preempt_pending, we will still send the active notification
 (IPI).  The core ought to get a notification for the preemption anyway, so we
@@ -567,7 +577,7 @@ do is execute the notification handler and jump to userspace.  Since there is
 still an k_msg in the queue (and we self_ipi'd ourselves, it's part of how
 k_msgs work), the IPI will fire and push us right back into the kernel to
 execute the preemption, and the notif handler's context will be saved in the
-preempt_tf (ready to go when the vcore gets started again).
+vcore_ctx (ready to go when the vcore gets started again).
 
 We could try to just leave the notif_pending flag set and ignore the message,
 but that would involve inspecting the queue for the preempt k_msg.
@@ -585,14 +595,13 @@ flexibility in schedule()-like functions (no need to wait to give the core
 out), quicker dispatch latencies, less contention on shared structs (like the
 idle-core-map), etc.
 
-Also, we don't remove the pcore from the vcoremap, even if it is being
-allocated to another core (the same pcore can exist in two vcoremaps, contrary
-to older statements).  Taking the pcore from the vcoremap would mean some
-non-fate related local calls (sys_get_vcoreid()) will fail, since the vcoreid
-is gone!  Additionally, we don't need a vcoreid in the k_msg (we would have if
-we could not use the vcore/pcoremappings).  There should not be any issues
-with the new process sending messages to the pcore before the core is sorted,
-since k_msgs are delivered in order.
+This 'freeing' of the pcore is from the perspective of the kernel scheduler
+and the proc struct.  Contrary to all previous announcements, vcores are
+unmapped from pcores when sending k_msgs (technically right after), while
+holding the lock.  The pcore isn't actually not-running-the-proc until the
+kmsg completes and we abandon_core().  Previously, we used the vcoremap to
+communicate to other cores in a lock-free manner, but that was pretty shitty
+and now we just store the vcoreid in pcpu info.
 
 Another tricky part is the seq_ctr used to signal userspace of changes to the
 coremap or num_vcores (coremap_seqctr).  While we may not even need this in the
@@ -677,49 +686,96 @@ We also considered using the transition stack as a signal that a process is in
 a notification handler.  The kernel can inspect the stack pointer to determine
 this.  It's possible, but unnecessary.
 
-5. current_tf and owning_proc
+Using the pcoremap as a way to pass info with kmsgs: it worked a little, but
+had some serious problems, as well as making life difficult.  It had two
+purposes: help with local fate calls (yield) and allow broadcast messaging.
+The main issue is that it was using a global struct to pass info with
+messages, but it was based on the snapshot of state at the time the message
+was sent.  When you send a bunch of messages, certain state may have changed
+between messages, and the old snapshot isn't there anymore by the time the
+message gets there.  To avoid this, we went through some hoops and had some
+fragile code that would use other signals to avoid those scenarios where the
+global state change would send the wrong message.  It was tough to understand,
+and not clear it was correct (hint: it wasn't).  Here's an example (on one
+pcore): if we send a preempt and we then try to map that pcore to another
+vcore in the same process before the preempt call checks its pcoremap, we'll
+clobber the pcore->vcore mapping (used by startcore) and the preempt will
+think it is the new vcore, not the one it was when the message was sent.
+While this is a bit convoluted, I can imagine a ksched doing this, and
+perhaps with weird IRQ delays, the messages might get delayed enough for it to
+happen.  I'd rather not have to have the ksched worry about this just because
+proc code was old and ghetto.  Another reason we changed all of this was so
+that you could trust the vcoremap while holding the lock.  Otherwise, it's
+actually non-trivial to know the state of a vcore (need to check a combination
+of preempt_served and is_mapped), and even if you do that, there are some
+complications with doing this in the ksched.
+
+5. current_ctx and owning_proc
 ===========================
-Originally, current_tf is a per-core macro that returns a struct trapframe *
+Originally, current_tf was a per-core macro that returns a struct trapframe *
 that points back on the kernel stack to the user context that was running on
 the given core when an interrupt or trap happened.  Saving the reference to
 the TF helps simplify code that needs to do something with the TF (like save
 it and pop another TF).  This way, we don't need to pass the context all over
 the place, especially through code that might not care.
 
-Now, current_tf is more broadly defined as the user context that should be run
-when the kernel is ready to run a process.  In the older case, it was when the
-kernel tries to return to userspace from a trap/interrupt.  Now, current_tf
-can be set by an IPI/KMSG (like '__startcore') so that when the kernel wants
-to idle, it will find a cur_tf that it needs to run, even though we never
+Then, current_tf was more broadly defined as the user context that should be
+run when the kernel is ready to run a process.  In the older case, it was when
+the kernel tries to return to userspace from a trap/interrupt.  current_tf
+could be set by an IPI/KMSG (like '__startcore') so that when the kernel wants
+to idle, it will find a current_tf that it needs to run, even though we never
 trapped in on that context in the first place.
 
+Finally, current_tf was changed to current_ctx, and instead of tracking a
+struct trapframe (equivalent to a hw_trapframe), it now tracked a struct
+user_context, which could be either a HW or a SW trapframe.
+
 Further, we now have 'owning_proc', which tells the kernel which process
-should be run.  'owning_proc' is a bigger deal than 'current_tf', and it is
-what tells us to run cur_tf.
+should be run.  'owning_proc' is a bigger deal than 'current_ctx', and it is
+what tells us to run cur_ctx.
 
-Process management KMSGs now simply modify 'owning_proc' and cur_tf, as if we
+Process management KMSGs now simply modify 'owning_proc' and cur_ctx, as if we
 had interrupted a process.  Instead of '__startcore' forcing the kernel to
 actually run the process and trapframe, it will just mean we will eventually
 run it.  In the meantime a '__notify' or a '__preempt' can come in, and they
-will apply to the owning_proc/cur_tf.  This greatly simplifies process code
+will apply to the owning_proc/cur_ctx.  This greatly simplifies process code
 and code calling process code (like the scheduler), since we no longer need to
 worry about whether or not we are getting a "stack killing" kernel message.
 Before this, code needed to care where it was running when managing _Ms.
 
-Note that neither 'current_tf' nor 'owning_proc' rely on 'current'/'cur_proc'.
+Note that neither 'current_ctx' nor 'owning_proc' rely on 'current'/'cur_proc'.
 'current' is just what process context we're in, not what process (and which
 trapframe) we will eventually run.
 
-cur_tf does not point to kernel trapframes, which is important when we receive an
-interrupt in the kernel.  At one point, we were (hypothetically) clobbering the
-reference to the user trapframe, and were unable to recover.  We can get away
-with this because the kernel always returns to its previous context from a
-nested handler (via iret on x86).  
-
-In the future, we may need to save kernel contexts and may not always return via
-iret.  At which point, if the code path is deep enough that we don't want to
-carry the TF pointer, we may revisit this.  Until then, current_tf is just for
-userspace contexts, and is simply stored in per_cpu_info.
+cur_ctx does not point to kernel trapframes, which is important when we
+receive an interrupt in the kernel.  At one point, we were (hypothetically)
+clobbering the reference to the user trapframe, and were unable to recover.
+We can get away with this because the kernel always returns to its previous
+context from a nested handler (via iret on x86).  
+
+In the future, we may need to save kernel contexts and may not always return
+via iret.  At which point, if the code path is deep enough that we don't want
+to carry the TF pointer, we may revisit this.  Until then, current_ctx is just
+for userspace contexts, and is simply stored in per_cpu_info.
+
+Brief note from the future (months after this paragraph was written): cur_ctx
+has two aspects/jobs:
+1) tell the kernel what we should do (trap, fault, sysc, etc), how we came
+into the kernel (the fact that it is a user tf), which is why we copy-out
+early on
+2) be a vehicle for us to restart the process/vcore
+
+We've been focusing on the latter case a lot, since that is what gets
+removed when preempted, changed during a notify, created during a startcore,
+etc.  Don't forget it was also an instruction of sorts.  The former case is
+always true throughout the life of the syscall.  The latter only happens to be
+true throughout the life of a *non-blocking* trap since preempts are routine
+KMSGs.  But if we block in a syscall, the cur_ctx is no longer the TF we came
+in on (and possibly the one we are asked to operate on), and that old cur_ctx
+has probably restarted.
+
+(Note that cur_ctx is a pointer, and syscalls/traps actually operate on the TF
+they came in on regardless of what happens to cur_ctx or pcpui->actual_tf.)
 
 6. Locking!
 ===========================
@@ -942,5 +998,404 @@ on), and then that vcore gets granted in the next round of vcore_requests().
 The preemption recovery handlers will need to deal with concurrent handlers
 and the vcore itself starting back up.
 
-9. TBD
+9. On the Ordering of Messages and Bugs with Old State
+===========================
+This is a sordid tale involving message ordering, message delivery times, and
+finding out (sometimes too late) that the state you expected is gone and
+having to deal with that error.
+
+A few design issues:
+- being able to send messages and have them execute in the order they are
+  sent
+- having message handlers resolve issues with global state.  Some need to know
+  the correct 'world view', and others need to know what was the state at the
+  time they were sent.
+- realizing syscalls, traps, faults, and any non-IRQ entry into the kernel is
+  really a message.
+
+Process management messages have alternated from ROUTINE to IMMEDIATE and now
+back to ROUTINE.  These messages include such family favorites as
+'__startcore', '__preempt', etc.  Meanwhile, syscalls were coming in that
+needed to know about the core and the process's state (specifically, yield,
+change_to, and get_vcoreid).  Finally, we wanted to avoid locking, esp in
+KMSGs handlers (imagine all cores grabbing the lock to check the vcoremap or
+something).
+
+Incidentally, events were being delivered concurretly to vcores, though that
+actually didn't matter much (check out async_events.txt for more on that).
+
+9.1: Design Guidelines
+---------------------------
+Initially, we wanted to keep broadcast messaging available as an option.  As
+noted elsewhere, we can't really do this well for startcore, since most
+hardware broadcast options need some initial per-core setup, and any sort of
+broadcast tree we make should be able to handle a small message.  Anyway, this
+desire in the early code to keep all messages identical lead to a few
+problems.
+
+Another objective of the kernel messaging was to avoid having the message
+handlers grab any locks, especially the same lock (the proc lock is used to
+protect the vcore map, for instance).
+
+Later on, a few needs popped up that motivated the changes discussed below:
+- Being able to find out which proc/vcore was on a pcore
+- Not having syscalls/traps require crazy logic if the carpet was pulled out
+  from under them.
+- Having proc management calls return.  This one was sorted out by making all
+  kmsg handlers return.  It would be a nightmare making a ksched without this.
+
+9.2: Looking at Old State: a New Bug for an Old Problem
+---------------------------
+We've always had issues with syscalls coming in and already had the fate of a
+core determined.  This is referred to in a few places as "predetermined fate"
+vs "local state".  A remote lock holder (ksched) already determined a core
+should be unmapped and sent a message.  Only later does some call like
+proc_yield() realize its core is already *unmapped*. (I use that term poorly
+here).  This sort of code had to realize it was working on an old version of
+state and just abort.  This was usually safe, though looking at the vcoremap
+was a bad idea.  Initially, we used preempt_served as the signal, which was
+okay.  Around 12b06586 yield started to use the vcoremap, which turned out to
+be wrong.
+
+A similar issue happens for the vcore messages (startcore, preempt, etc).  The
+way startcore used to work was that it would only know what pcore it was on,
+and then look into the vcoremap to figure out what vcoreid it should be
+running.  This was to keep broadcast messaging available as an option.  The
+problem with it is that the vcoremap may have changed between when the
+messages were sent and when they were executed.  Imagine a startcore followed
+by a preempt, afterwhich the vcore was unmapped.  Well, to get around that, we
+had the unmapping happen in the preempt or death handlers.  Yikes!  This was
+the case back in the early days of ROS.  This meant the vcoremap wasn't
+actually representative of the decisions the ksched made - we also needed to
+look at the state we'd have after all outstanding messages executed.  And this
+would differ from the vcore lists (which were correct for a lock holder).
+
+This was managable for a little while, until I tried to conclusively know who
+owned a particular pcore.  This came up while making a provisioning scheduler.
+Given a pcore, tell me which process/vcore (if any) were on it.  It was rather
+tough.  Getting the proc wasn't too hard, but knowing which vcore was a little
+tougher.  (Note the ksched doesn't care about which vcore is running, and the
+process can change vcores on a pcore at will).  But once you start looking at
+the process, you can't tell which vcore a certain pcore has.  The vcoremap may
+be wrong, since a preempt is already on the way.  You would have had to scan
+the vcore lists to see if the proc code thought that vcore was online or not
+(which would mean there had been no preempts).  This is the pain I was talking
+about back around commit 5343a74e0.
+
+So I changed things so that the vcoremap was always correct for lock holders,
+and used pcpui to track owning_vcoreid (for preempt/notify), and used an extra
+KMSG variable to tell startcore which vcoreid it should use.  In doing so, we
+(re)created the issue that the delayed unmapping dealt with: the vcoremap
+would represent *now*, and not the vcoremap of when the messages were first
+sent.  However, this had little to do with the KMSGs, which I was originally
+worried about.  No one was looking at the vcoremap without the lock, so the
+KMSGs were okay, but remember: syscalls are like messages too.  They needed to
+figure out what vcore they were on, i.e. what vcore userspace was making
+requests on (viewing a trap/fault as a type of request).
+
+Now the problem was that we were using the vcoremap to figure out which vcore
+we were supposed to be.  When a syscall finally ran, the vcoremap could be
+completely wrong, and with immediate KMSGs (discussed below), the pcpui was
+already changed!  We dealt with the problem for KMSGs, but not syscalls, and
+basically reintroduced the bug of looking at current state and thinking it
+represented the state from when the 'message' was sent (when we trapped into
+the kernel, for a syscall/exception).
+
+9.3: Message Delivery, Circular Waiting, and Having the Carpet Pulled Out
+---------------------------
+In-order message delivery was what drove me to build the kernel messaging
+system in the first place.  It provides in-order messages to a particular
+pcore.  This was enough for a few scenarios, such as preempts racing ahead of
+startcores, or deaths racing a head of preempts, etc.  However, I also wanted
+an ordering of messages related to a particular vcore, and this wasn't
+apparent early on.
+
+The issue first popped up with a startcore coming quickly on the heals of a
+preempt for the same VC, but on different PCs.  The startcore cannot proceed
+until the preempt saved the TF into the VCPD.  The old way of dealing with
+this was to spin in '__map_vcore()'.  This was problematic, since it meant we
+were spinning while holding a lock, and resulted in some minor bugs and issues
+with lock ordering and IRQ disabling (couldn't disable IRQs and then try to
+grab the lock, since the lock holder could have sent you a message and is
+waiting for you to handle the IRQ/IMMED KMSG).  However, it was doable.  But
+what wasn't doable was to have the KMSGs be ROUTINE.  Any syscalls that tried
+to grab the proc lock (lots of them) would deadlock, since the lock holder was
+waiting on us to handle the preempt (same circular waiting issue as above).
+
+This was fine, albeit subpar, until a new issue showed up.  Sending IMMED
+KMSGs worked fine if we were coming from userspace already, but if we were in
+the kernel, those messages would run immediately (hence the name), just like
+an IRQ handler, and could confuse syscalls that touched cur_ctx/pcpui.  If a
+preempt came in during a syscall, the process/vcore could be changed before
+the syscall took place.  Some syscalls could handle this, albeit poorly.
+sys_proc_yield() and sys_change_vcore() delicately tried to detect if they
+were still mapped or not and use that to determine if a preemption happened.
+
+As mentioned above, looking at the vcoremap only tells you what is currently
+happening, and not what happened in the past.  Specifically, it doesn't tell
+you the state of the mapping when a particular core trapped into the kernel
+for a syscall (referred to as when the 'message' was sent up above).  Imagine
+sys_get_vcoreid(): you trap in, then immediately get preempted, then startcore
+for the same process but a different vcoreid.  The syscall would return with
+the vcoreid of the new vcore, since it cannot tell there was a change.  The
+async syscall would complete and we'd have a wrong answer.  While this never
+happened to me, I had a similar issue while debugging some other bugs (I'd get
+a vcoreid of 0xdeadbeef, for instance, which was the old poison value for an
+unmapped vcoreid).  There are a bunch of other scenarios that trigger similar
+disasters, and they are very hard to avoid.
+
+One way out of this was a per-core history counter, that changed whenever we
+changed cur_ctx.  Then when we trapped in for a syscall, we could save the
+value, enable_irqs(), and go about our business.  Later on, we'd have to
+disable_irqs() and compare the counters.  If they were different, we'd have to
+bail out some how.  This could have worked for change_to and yield, and some
+others.  But any syscall that wanted to operate on cur_ctx in some way would
+fail (imagine a hypothetical sys_change_stack_pointer()).  The context that
+trapped has already returned on another core.  I guess we could just fail that
+syscall, though it seems a little silly to not be able to do that.
+
+The previous example was a bit contrived, but lets also remember that it isn't
+just syscalls: all exceptions have the same issue.  Faults might be fixable,
+since if you restart a faulting context, it will start on the faulting
+instruction.  However all traps (like syscall) restart on the next
+instruction.  Hope we don't want to do anything fancy with breakpoint!  Note
+that I had breakpointing contexts restart on other pcores and continue while I
+was in the breakpoint handler (noticed while I was debugging some bugs with
+lots of preempts).  Yikes.  And don't forget we eventually want to do some
+complicated things with the page fault handler, and may want to turn on
+interrupts / kthread during a page fault (imaging hitting disk).  Yikes.
+
+So I looked into going back to ROUTINE kernel messages.  With ROUTINE
+messages, I didn't have to worry about having the carpet pulled out from under
+syscalls and exceptions (traps, faults, etc).  The 'carpet' is stuff like
+cur_ctx, owning_proc, owning_vcoreid, etc.  We still cannot trust the vcoremap,
+unless we *know* there were no preempts or other KMSGs waiting for us.
+(Incidentally, in the recent fix a93aa7559, we merely use the vcoremap as a
+sanity check).
+
+However, we can't just switch back to ROUTINEs.  Remember: with ROUTINEs,
+we will deadlock in '__map_vcore()', when it waits for the completion of
+preempt.  Ideally, we would have had startcore spin on the signal.  Since we
+already gave up on using x86-style broadcast IPIs for startcore (in
+5343a74e0), we might as well pass along a history counter, so it knows to wait
+on preempt.
+
+9.4: The Solution
+---------------------------
+To fix up all of this, we now detect preemptions in syscalls/traps and order
+our kernel messages with two simple per-vcore counters.  Whenever we send a
+preempt, we up one counter.  Whenever that preempt finishes, it ups another
+counter.  When we send out startcores, we send a copy of the first counter.
+This is a way of telling startcore where it belongs in the list of messages.
+More specifically, it tells it which preempt happens-before it.
+
+Basically, I wanted a partial ordering on my messages, so that messages sent
+to a particular vcore are handled in the order they were sent, even if those
+messages run on different physical cores.
+
+It is not sufficient to use a seq counter (one integer, odd values for
+'preempt in progress' and even values for 'preempt done').  It is possible to
+have multiple preempts in flight for the same vcore, albeit with startcores in
+between.  Still, there's no way to encode that scenario in just one counter.
+
+Here's a normal example of traffic to some vcore.  I note both the sending and
+the execution of the kmsgs:
+   nr_pre_sent    nr_pre_done    pcore     message sent/status
+   -------------------------------------------------------------
+   0              0              X         startcore (nr_pre_sent == 0)
+   0              0              X         startcore (executes)
+   1              0              X         preempt   (kmsg sent)
+   1              1              Y         preempt   (executes)
+   1              1              Y         startcore (nr_pre_sent == 1)
+   1              1              Y         startcore (executes)
+
+Note the messages are always sent by the lockholder in the order of the
+example above.
+
+Here's when the startcore gets ahead of the prior preempt:
+   nr_pre_sent    nr_pre_done    pcore     message sent/status
+   -------------------------------------------------------------
+   0              0              X         startcore (nr_pre_sent == 0) 
+   0              0              X         startcore (executes)
+   1              0              X         preempt   (kmsg sent)
+   1              0              Y         startcore (nr_pre_sent == 1)
+   1              1              X         preempt   (executes)
+   1              1              Y         startcore (executes)
+
+Note that this can only happen across cores, since KMSGs to a particular core
+are handled in order (for a given class of message).  The startcore blocks on
+the prior preempt.
+
+Finally, here's an example of what a seq ctr can't handle:
+   nr_pre_sent    nr_pre_done    pcore     message sent/status
+   -------------------------------------------------------------
+   0              0              X         startcore (nr_pre_sent == 0) 
+   1              0              X         preempt   (kmsg sent)
+   1              0              Y         startcore (nr_pre_sent == 1)
+   2              0              Y         preempt   (kmsg sent)
+   2              0              Z         startcore (nr_pre_sent == 2)
+   2              1              X         preempt   (executes (upped to 1))
+   2              1              Y         startcore (executes (needed 1))
+   2              2              Y         preempt   (executes (upped to 2))
+   2              Z              Z         startcore (executes (needed 2))
+
+As a nice bonus, it is easy for syscalls that care about the vcoreid (yield,
+change_to, get_vcoreid) to check if they have a preempt_served.  Just grab the
+lock (to prevent further messages being sent), then check the counters.  If
+they are equal, there is no preempt on its way.  This actually was the
+original way we checked for preempts in proc_yield back in the day.  It was
+just called preempt_served.  Now, it is split into two counters, instead of
+just being a bool.  
+
+Regardless of whether or not we were preempted, we still can look at
+pcpui->owning_proc and owning_vcoreid to figure out what the vcoreid of the
+trap/syscall is, and we know that the cur_ctx is still the correct cur_ctx (no
+carpet pulled out), since while there could be a preempt ROUTINE message
+waiting for us, we simply haven't run it yet.  So calls like yield should
+still fail (since your core has been unmapped and you need to bail out and run
+the preempt handler), but calls like sys_change_stack_pointer can proceed.
+More importantly than that old joke syscall, the page fault handler can try to
+do some cool things without worrying about really crazy stuff.
+
+9.5: Why We (probably) Don't Deadlock
+---------------------------
+It's worth thinking about why this setup of preempts and startcores can't
+deadlock.  Anytime we spin in the kernel, we ought to do this.  Perhaps there
+is some issue with other KMSGs for other processes, or other vcores, or
+something like that that can cause a deadlock.
+
+Hypothetical case: pcore 1 has a startcore for vc1 which is stuck behind vc2's
+startcore on PC2, with time going upwards.  In these examples, startcores are
+waiting on particular preempts, subject to the nr_preempts_sent parameter sent
+along with the startcores.
+
+^                       
+|            _________                 _________
+|           |         |               |         |
+|           | pr vc 2 |               | pr vc 1 |
+|           |_________|               |_________|
+|
+|            _________                 _________
+|           |         |               |         |
+|           | sc vc 1 |               | sc vc 2 |
+|           |_________|               |_________|
+t           
+---------------------------------------------------------------------------
+              ______                    ______
+             |      |                  |      |
+             | PC 1 |                  | PC 2 |
+             |______|                  |______|
+
+Here's the same picture, but with certain happens-before arrows.  We'll use X --> Y to
+mean X happened before Y, was sent before Y.  e.g., a startcore is sent after
+a preempt.
+
+^                       
+|            _________                 _________
+|           |         |               |         |
+|       .-> | pr vc 2 | --.    .----- | pr vc 1 | <-.
+|       |   |_________|    \  /   &   |_________|   |  
+|     * |                   \/                      | * 
+|       |    _________      /\         _________    |  
+|       |   |         |    /  \   &   |         |   |  
+|       '-- | sc vc 1 | <-'    '----> | sc vc 2 | --'
+|           |_________|               |_________|
+t           
+---------------------------------------------------------------------------
+              ______                    ______
+             |      |                  |      |
+             | PC 1 |                  | PC 2 |
+             |______|                  |______|
+
+The arrows marked with * are ordered like that due to the property of KMSGs,
+in that we have in order delivery.  Messages are executed in the order in
+which they were sent (serialized with a spinlock btw), so on any pcore,
+messages that are further ahead in the queue were sent before (and thus will
+be run before) other messages.
+
+The arrows marked with a & are ordered like that due to how the proc
+management code works.  The kernel won't send out a startcore for a particular
+vcore before it sent out a preempt.  (Note that techincally, preempts follow
+startcores.  The startcores in this example are when we start up a vcore after
+it had been preempted in the past.).
+
+Anyway, note that we have a cycle, where all events happened before each
+other, which isn't possible.  The trick to connecting "unrelated" events like
+this (unrelated meaning 'not about the same vcore') in a happens-before manner
+is the in-order properties of the KMSGs.
+
+Based on this example, we can derive general rules.  Note that 'sc vc 2' could
+be any kmsg that waits on another message placed behind 'sc vc 1'.  This would
+require us having sent a KMSG that waits on a KMSGs that we send later.  Bad
+idea!  (you could have sent that KMSGs to yourself, aside from just being
+dangerous).  If you want to spin, make sure you send the work that should
+happen-before actually-before the waiter.
+
+In fact, we don't even need 'sc vc 2' to be a KMSG.  It could be miscellaneous
+kernel code, like a proc mgmt syscall.  Imagine if we did something like the
+old '__map_vcore' call from within the ksched.  That would be code that holds
+the lock, and then waits on the execution of a message handler.  That would
+deadlock (which is why we don't do it anymore).
+
+Finally, in case this isn't clear, all of the startcores and preempts for
+a given vcore exist in a happens-before relation, both in sending and in
+execution.  The sending aspect is handled by proc mgmt code.  For execution,
+preempts always follow startcores due to the KMSG ordering property.  For
+execution of startcores, startcores always spin until the preempt they follow
+is complete, ensuring the execution of the main part of their handler happens
+after the prior preempt.
+
+Here's some good ideas for the ordering of locks/irqs/messages:
+- You can't hold a spinlock of any sort and then wait on a routine kernel
+  message.  The core where that runs may be waiting on you, or some scenario
+  like above.
+       - Similarly, think about how this works with kthreads.  A kthread restart
+         is a routine KMSG.  You shouldn't be waiting on code that could end up
+         kthreading, mostly because those calls block!
+- You can hold a spinlock and wait on an IMMED kmsg, if the waiters of the
+  spinlock have irqs enabled while spinning (this is what we used to do with
+  the proc lock and IMMED kmsgs, and 54c6008 is an example of doing it wrong)
+       - As a corollary, locks like this cannot be irqsave, since the other
+         attempted locker will have irq disabled
+- For broadcast trees, you'd have to send IMMEDs for the intermediates, and
+  then it'd be okay to wait on those intermediate, immediate messages (if we
+  wanted confirmation of the posting of RKM)
+       - The main thing any broadcast mechanism needs to do is make sure all
+         messages get delivered in order to particular pcores (the central
+         premise of KMSGs) (and not deadlock due to waiting on a KMSG improperly)
+- Alternatively, we could use routines for the intermediates if we didn't want
+  to wait for RKMs to hit their destination, we'd need to always use the same
+  proxy for the same destination pcore, e.g., core 16 always covers 16-31.
+       - Otherwise, we couldn't guarantee the ordering of SC before PR before
+         another SC (which the proc_lock and proc mgmt code does); we need the
+         ordering of intermediate msgs on the message queues of a particular
+         core.
+       - All kmsgs would need to use this broadcasting style (couldn't mix
+         regular direct messages with broadcast), so odds are this style would be
+         of limited use.
+       - since we're not waiting on execution of a message, we could use RKMs
+         (while holding a spinlock)
+- There might be some bad effects with kthreads delaying the reception of RKMS
+  for a while, but probably not catastrophically.
+
+9.6: Things That We Don't Handle Nicely
+---------------------------
+If for some reason a syscall or fault handler blocks *unexpectedly*, we could
+have issues.  Imagine if change_to happens to block in some early syscall code
+(like instrumentation, or who knows what, that blocks in memory allocation).
+When the syscall kthread restarts, its old cur_ctx is gone.  It may or may not
+be running on a core owned by the original process.  If it was, we probably
+would accidentally yield that vcore (clearly a bug).  
+
+For now, any of these calls that care about cur_ctx/pcpui need to not block
+without some sort of protection.  None of them do, but in the future we might
+do something that causes them to block.  We could deal with it by having a
+pcpu or per-kthread/syscall flag that says if it ever blocked, and possibly
+abort.  We get into similar nasty areas as with preempts, but this time, we
+can't solve it by making preempt a routine KMSG - we block as part of that
+syscall/handler code.  Odds are, we'll just have to outlaw this, now and
+forever.  Just note that if a syscall/handler blocks, the TF it came in on is
+probably not cur_ctx any longer, and that old cur_ctx has probably restarted.
+
+10. TBD
 ===========================