Allow backtrace_user_ctx() on remote cores
[akaros.git] / Documentation / async_events.txt
index 2ec3132..0bb1854 100644 (file)
@@ -335,19 +335,20 @@ There are also interfaces in the kernel to put a message in an ev_mbox
 regardless of the process's wishes (post_vcore_event()), and can send an IPI
 at any time (proc_notify()).
 
-3.3 IPIs, Indirection Events, and Fallback
+3.3 IPIs, Indirection Events, and Fallback (Spamming Indirs)
 ----------------------------------------------
-An ev_q can ask for an IPI, an indirection event, and a fallback in case a vcore
-is offline.  Or any combination of these.  Note that these have little to do
-with the actual message being sent.  The actual message is dropped in the
-ev_mbox pointed to by the ev_q.
+An ev_q can ask for an IPI, for an indirection event, and for an indirection
+event to be spammed in case a vcore is offline (sometimes called the 'fallback'
+option.  Or any combination of these.  Note that these have little to do with
+the actual message being sent.  The actual message is dropped in the ev_mbox
+pointed to by the ev_q.
 
 The main use for all of this is for syscalls.  If you want to receive an event
 when a syscall completes or has a change in status, simply allocate an event_q,
 and point the syscall at it.  syscall: ev_q* -> "vcore for IPI, syscall message
 in the ev_q mbox", etc.  You can also point it to an existing ev_q.  Pthread
 code has examples of two ways to do this.  Both have per vcore ev_qs, requesting
-IPIs, INDIRS, and FALLBACK.  One way is to have an ev_mbox per vcore, and
+IPIs, INDIRS, and SPAM_INDIR.  One way is to have an ev_mbox per vcore, and
 another is to have a global ev_mbox that all ev_qs point to.  As a side note, if
 you do the latter, you don't need to worry about a vcore's ev_q if it gets
 preempted: just check the global ev_mbox (which is done by checking your own
@@ -376,41 +377,41 @@ to make sure you get the message on a vcore that didn't yield.)
 
 Never use a VCPD mbox (public or private) for messages you might want to receive
 if that vcore is offline.  If you want to be sure to get a message, create your
-own ev_q and set flags for INDIR, FALLBACK, and IPI.  There's no guarantee a
+own ev_q and set flags for INDIR, SPAM_INDIR, and IPI.  There's no guarantee a
 *specific* message will get looked at.  In cases where it won't, the kernel will
 send that message to another vcore.  For example, if the kernel posts an INDIR
 to a VCPD mbox (the public one btw) and it loses a race with the vcore yielding,
 the vcore might never see that message.  However, the kernel knows it lost the
 race, and will find another vcore to send it to.
 
-3.3.2: Fallback
+3.3.2: Spamming Indirs / Fallback
 ---------------
 Both IPI and INDIR need an actual vcore.  If that vcore is unavailable and if
-EVENT_FALLBACK is set, the kernel will pick another vcore and send the messages
-there.  This allows an ev_q to be set up to handle work when the vcore is
-online, while allowing the program to handle events when that core yields,
+EVENT_SPAM_INDIR is set, the kernel will pick another vcore and send the
+messages there.  This allows an ev_q to be set up to handle work when the vcore
+is online, while allowing the program to handle events when that core yields,
 without having to reset all of its ev_qs to point to "known" available vcores
 (and avoiding those races).  Note 'online' is synonymous with 'mapped', when
-talking about vcores.  A vcore technically isn't always online, only destined to
-be online, when it is mapped to a pcore (kmsg on the way, etc).  It's easiest to
-think of it being online for the sake of this discussion.
-
-One question is whether or not 2LSs need a FALLBACK flag for their ev_qs.  The
-main use for FALLBACK is so that vcores can yield.  (Note that fallback won't
-help you *miss* INDIR messages in the event of a preemption; you can always lose
-that race due to it taking too long to process the messages).  An alternative
-would be for vcores to pick another vcore and change all of its ev_qs to that
-vcore.  There are a couple problems with this.  One is that it'll be a pain to
-get those ev_qs back when the vcore comes back online (if ever).  Another issue
-is that other vcores will build up a list of ev_qs that they aren't aware of,
-which will be hard to deal with when *they* yield.  FALLBACK avoids all of those
-problems.
-
-An important aspect of FALLBACK is that it works with yielded vcores, not
-preempted vcores.  It could be that there are no cores that are online, but
+talking about vcores.  A vcore technically isn't always online, only destined
+to be online, when it is mapped to a pcore (kmsg on the way, etc).  It's
+easiest to think of it being online for the sake of this discussion.
+
+One question is whether or not 2LSs need a SPAM_INDIR flag for their ev_qs.
+The main use for SPAM_INDIR is so that vcores can yield.  (Note that fallback
+won't help you *miss* INDIR messages in the event of a preemption; you can
+always lose that race due to it taking too long to process the messages).  An
+alternative would be for vcores to pick another vcore and change all of its
+ev_qs to that vcore.  There are a couple problems with this.  One is that it'll
+be a pain to get those ev_qs back when the vcore comes back online (if ever).
+Another issue is that other vcores will build up a list of ev_qs that they
+aren't aware of, which will be hard to deal with when *they* yield.  SPAM_INDIR
+avoids all of those problems.
+
+An important aspect of spamming indirs is that it works with yielded vcores,
+not preempted vcores.  It could be that there are no cores that are online, but
 there should always be at least one core that *will* be online in the future, a
 core that the process didn't want to lose and will deal with in the future.  If
-not for this distinction, FALLBACK could fail.  An older idea would be to have
+not for this distinction, SPAM_INDIR could fail.  An older idea would be to have
 fallback send the msg to the desired vcore if there were no others.  This would
 not work if the vcore yielded and then the entire process was preempted or
 otherwise not running.  Another way to put this is that we need a field to
@@ -418,7 +419,7 @@ determine whether a vcore is offline temporarily or permanently.
 
 This is why we have the VCPD flag 'VC_CAN_RCV_MSG'.  It tells the kernel's event
 delivery code that the vcore will check the messages: it is an acceptable
-destination for a FALLBACK.  There are two reasons to put this in VCPD:
+destination for a spammed indir.  There are two reasons to put this in VCPD:
 1) Userspace can remotely turn off a vcore's msg reception.  This is necessary
 for handling preemption of a vcore that was in uthread context, so that we can
 remotely 'yield' the core without having to sys_change_vcore() (which I discuss
@@ -441,7 +442,7 @@ Worth mentioning is the difference between 'notif_pending' and VC_CAN_RCV_MSG.
 VC_CAN_RCV_MSG is the process saying it will check for messages.
 'notif_pending' is when the kernel says it *has* sent a message.
 'notif_pending' is also used by the kernel in proc_yield() and the 2LS in
-pop_ros_tf() to make sure the sent message is not missed.
+pop_user_ctx() to make sure the sent message is not missed.
 
 Also, in case this comes up, there's a slight race on changing the mbox* and the
 vcore number within the event_q.  The message could have gone to the wrong (old)
@@ -453,7 +454,7 @@ this can be a bit tricky if you have multiple places pointing to the same ev_q
 
 3.3.3: Fallback and Preemption
 ---------------
-FALLBACK doesn't protect you from preemptions.  A vcore can be preempted and
+SPAM_INDIR doesn't protect you from preemptions.  A vcore can be preempted and
 have INDIRs in its VCPD.
 
 It is tempting to just use sys_change_vcore(), which will change the calling
@@ -481,7 +482,7 @@ offline vcore.  There could be INDIRS in the VCPD that are just lying there.
 The 2LS knows which ev_qs these are (such as for completed syscalls), and for
 many things, this will be a common ev_q (such as for 'vcore-x-was-preempted').
 However, this is a huge pain in the ass, since a preempted vcore could have the
-FALLBACK INDIR for an ev_q associated with another vcore.  To deal with this,
+spammed INDIR for an ev_q associated with another vcore.  To deal with this,
 the 2LS would need to check *every* ev_q that requests INDIRs.  We don't do
 this.
 
@@ -553,9 +554,10 @@ blocking u_threads).
 
 There are a couple ways to handle this.  Ultimately, the application is supposed
 to handle the event.  If it asked for an IPI, it is because something ought to
-be done, which really means running a handler.  If the application sets
-EVENT_THREAD in the ev_q's flags, the 2LS ought to spawn a thread to run the
-ev_q's handler.  If EVENT_JUSTHANDLEIT is set, the vcore will execute the
+be done, which really means running a handler.  We used to support the
+application setting EVENT_THREAD in the ev_q's flags, and the 2LS would spawn a
+thread to run the ev_q's handler.  Now we just have the application block a
+uthread on the evq.  If an ev_handler is set, the vcore will execute the
 handler itself.  Careful with this, since the only memory it touches must be
 pinned, the function must not block (this is only true for the handlers called
 directly out of vcore context), and it should return quickly.
@@ -690,6 +692,139 @@ migrate a notif_safe locking uthread.  The whole point of it is in case it grabs
 a lock that would be held by vcore context, and there's no way to know it isn't
 a lock on the restart-path.
 
+3.9 Why Preemption Handling Doesn't Lock Up (probably)
+---------------------------------------
+One of the concerns of preemption handling is that we don't get into some form
+of livelock, where we ping-pong back and forth between vcores (or a set of
+vcores), all of which are trying to handle each other's preemptions.  Part of
+the concern is that when a vcore sys_changes to another, it can result in
+another preemption message being sent.  We want to be sure that we're making
+progress, and not just livelocked doing sys_change_vcore()s.
+
+A few notes first:
+1) If a vcore is holding locks or otherwise isn't handling events and is
+preempted, it will let go of its locks before it gets to the point of
+attempting to handle any other vcore preemption events.  Event handling is only
+done when it is okay to never return (meaning no locks are held).  If this is
+the situation, eventually it'll work itself out or get to a potential ping-pong
+scenario.
+
+2) When you change_to while handling preemption, once you start back up, you
+will leave change_to and eventually fetch a new event.  This means any
+potential ping-pong needs to happen on a fresh event.
+
+3) If there are enough pcores for the vcores to all run, we won't issue any
+change_tos, since the vcores are no longer preempted.  This means we only are
+worried about situations with insufficient vcores.  We'll mostly talk about 1
+pcore and 2 vcores.
+
+4) Preemption handlers will not call change_to on their target vcore if they
+are also the one STEALING from that vcore.  The handler will stop STEALING
+first.
+
+So the only way to get stuck permanently is if both cores are stuck doing a
+sys_change_to(FALSE).  This means we want to become the other vcore, *and* we
+need to restart our vcore where it left off.  This is due to some invariant
+that keeps us from abandoning vcore context.  If we were to abandon vcore
+context (with a sys_change_to(TRUE)), we basically don't need to be
+preempt-recovered.  We already packaged up our cur_uthread, and we know we
+aren't holding any locks or otherwise breaking any invariants.  The system will
+work fine if we never run again.  (Someone just needs to check our messages).
+
+Now, there are only two cases where we will do a sys_change_to(FALSE) *while*
+handling preemptions.  Again, we aren't concerned about things like MCS-PDR
+locks; those all work because the change_tos are done where we'd normally just
+busy loop.  We are only concerned about change_tos during handle_vc_preempt.
+These two cases are when the changing/handling vcore has a DONT_MIGRATE uthread
+or when someone else is STEALING its uthread.  Note that both of these cases
+are about the calling vcore, not its target.
+
+If a vcore (referred to as "us") has a DONT_MIGRATE uthread and it is handling
+events, it is because someone else is STEALING from our vcore, and we are in
+the short one-shot event handling loop at the beginning of
+uthread_vcore_entry().  Whichever vcore is STEALING will quickly realize it
+can't steal (it sees the DONT_MIGRATE), and bail out.  If that vcore isn't
+running now, we will change_to it (which is the purpose of our handling their
+preemption).  Once that vcore realizes it can't steal, it will stop STEALING
+and change to us.  At this point, no one is STEALING from us, and we move along
+in the code.  Specifically, we do *not* handle events (we now have an event
+about the other vcore being preempted when it changed_to us), and instead we
+start up the DONT_MIGRATE uthread and let it run until it is migratable, at
+which point we handle events and will deal with the other vcore.  
+
+So DONT_MIGRATE will be sorted out.  Likewise, STEALING gets sorted out too,
+quite easily.  If someone is STEALING from us, they will quickly stop STEALING
+and change to us.  There are only two ways this could even happen: they are
+running concurrently with us, and somehow saw us out of vcore context before
+deciding to STEAL, or they were in the process of STEALING and got preempted by
+the kernel.  They would not have willingly stopped running while STEALING our
+cur_uthread.  So if we are running and someone is stealing, after a round of
+change_tos, eventually they run, and stop STEALING.
+
+Note that once someone stops STEALING from us, they will not start again,
+unless we leave vcore context.  If that happened, we basically broke out of the
+ping-pong, and now we're onto another set of preemptions.  We wouldn't leave
+vcore context if we still had preemption events to deal with.
+
+Finally, note that we needed to only check for one message at a time at the
+beginning of uthread_vcore_entry().  If we just handled the entire mbox without
+checking STEALING, then we might not break out of that loop if there is a
+constant supply of messages (perhaps from a vcore in a similar loop).
+
+Anyway, that's the basic plan behind the preemption handler and how we avoid
+the ping-ponging.  change_to_vcore() is built so that we handle our own
+preemption before changing (pack up our current uthread), so that we make
+progress.  The two cases where we can't do that get sorted out after everyone
+gets to run once, and since you can't steal or have other uthread's turn on
+DONT_MIGRATE while we're in vcore context, eventually we clear everything up.
+There might be other bugs or weird corner cases, possibly involving multiple
+vcores, but I think we're okay for now.
+
+3.10: Handling Messages for Other Vcores
+---------------------------------------
+First, remember that when a vcore handles an event, there's no guarantee that
+the vcore will return from the handler.  It may start fresh in vcore_entry().
+
+The issue is that when you handle another vcore's INDIRs, you may handle
+preemption messages.  If you have to do a change_to, the kernel will make sure
+a message goes out about your demise.  Thus someone who recovers that will
+check your public mbox.  However, the recoverer won't know that you were
+working on another vcore's mbox, so those messages might never be checked.
+
+The way around it is to send yourself a "check the other guy's messages" event.
+When we might change_to and never return, if we were dealing with another
+vcores mbox, we'll send ourselves a message to finish up that mbox (if there
+are any messages left).  Whoever reads our messages will eventually get that
+message, and deal with it.
+
+One thing that is a little ugly is that the way you deal with messages two
+layers deep is to send yourself the message.  So if VC1 is handling VC2's
+messages, and then wants to change_to VC3, VC1 sends a message to VC1 to check
+VC2.  Later, when VC3 is checking VC1's messages, it'll handle the "check VC2's messages"
+message.  VC3 can't directly handle VC2's messages, since it could run a
+handler that doesn't return.  Nor can we just forget about VC2.  So VC3 sends
+itself a message to check VC2 later.  Alternatively, VC3 could send itself a
+message to continue checking VC1, and then move on to VC2.  Both seem
+equivalent.  In either case, we ought to check to make sure the mbox has
+something before bothering sending the message.
+
+So for either a "change_to that might not return" or for a "check INDIRs on yet
+another vcore", we send messages to ourself so that we or someone else will
+deal with it.
+
+Note that we use TLS to track whether or not we are handling another vcore's
+messages, and if we do plan to change_to that might not return, we clear the
+bool so that when our vcore starts over at vcore_entry(), it starts over and
+isn't still checking someone elses message.
+
+As a reminder of why this is important: these messages we are hunting down
+include INDIRs, specifically ones to ev_qs such as the "syscall completed
+ev_q".  If we never get that message, a uthread will block forever.  If we
+accidentally yield a vcore instead of checking that message, we would end up
+yielding the process forever since that uthread will eventually be the last
+one, but our main thread is probably blocked on a join call.  Our process is
+blocked on a message that already came, but we just missed it. 
+
 4. Single-core Process (SCP) Events:
 ====================
 4.1 Basics:
@@ -739,11 +874,6 @@ again.
 
 4.3 Extra Tidbits:
 ---------------------------------------
-One minor point: SCPs can't receive INDIRs, at least for now.  The kernel event
-code short circuits all the fallback business and just spams vcore0's public
-mbox.  If we ever change that, we need to be sure to post a notif_pending to
-vcore0 (that's the signal to trigger a wakeup).
-
 If we receive an event right as we transition from SCP to MCP, vcore0 could get
 spammed with a message that is never received.  Right now, it's not a problem,
 since vcore0 is the first vcore that will get woken up as an MCP.  This could be