Fix up alarm and pvcalarm tests
[akaros.git] / Documentation / processes.txt
index a0b11fa..a843890 100644 (file)
@@ -116,7 +116,8 @@ PROC_RUNNABLE_M
 PROC_RUNNING_M
 
 Difference between the _M and the _S states:
-- _S : legacy process mode
+- _S : legacy process mode.  There is no need for a second-level scheduler, and
+  the code running is analogous to a user-level thread.
 - RUNNING_M implies *guaranteed* core(s).  You can be a single core in the
   RUNNING_M state.  The guarantee is subject to time slicing, but when you
   run, you get all of your cores.
@@ -162,21 +163,32 @@ is currently done via sys_getcpuid().  The name will probably change.
 2.4.1: To go from _S to _M, a process requests cores.
 --------------
 A resource request from 0 to 1 or more causes a transition from _S to _M.  The
-calling context moves to vcore0 (proc_run() handles that) and continues from
-where it left off (the return point of the syscall).  
-
-For all other cores, and all subsequently allocated cores, they start at the
-elf entry point, with vcoreid in eax or a suitable arch-specific manner.  This
-could be replaced with a syscall that returns the vcoreid, but probably won't
-to help out sparc.
+calling context is saved in the uthread slot (uthread_ctx) in vcore0's
+preemption data (in procdata).  The second level scheduler needs to be able to
+restart the context when vcore0 starts up.  To do this, it will need to save the
+TLS/TCB descriptor and the floating point/silly state (if applicable) in the
+user-thread control block, and do whatever is needed to signal vcore0 to run the
+_S context when it starts up.  One way would be to mark vcore0's "active thread"
+variable to point to the _S thread.  When vcore0 starts up at
+_start/vcore_entry() (like all vcores), it will see a thread was running there
+and restart it.  The kernel will migrate the _S thread's silly state (FP) to the
+new pcore, so that it looks like the process was simply running the _S thread
+and got notified.  Odds are, it will want to just restart that thread, but the
+kernel won't assume that (hence the notification).
+
+In general, all cores (and all subsequently allocated cores) start at the elf
+entry point, with vcoreid in eax or a suitable arch-specific manner.  There is
+also a syscall to get the vcoreid, but this will save an extra trap at vcore
+start time.
 
 Future proc_runs(), like from RUNNABLE_M to RUNNING_M start all cores at the
-entry point, including vcore0.  The magic of moving contexts only happens on
-the transition from _S to _M (which the process needs to be aware of for a
-variety of reasons).  This also means that userspace needs to handle vcore0
-coming up at the entry point again (and not starting the program over).  I
-recommend setting a global variable that can be checked from assembly before
-going to _M the first time.
+entry point, including vcore0.  The saving of a _S context to vcore0's
+uthread_ctx only happens on the transition from _S to _M (which the process
+needs to be aware of for a variety of reasons).  This also means that userspace
+needs to handle vcore0 coming up at the entry point again (and not starting the
+program over).  This is currently done in sysdeps-ros/start.c, via the static
+variable init.  Note there are some tricky things involving dynamically linked
+programs, but it all works currently.
 
 When coming in to the entry point, whether as the result of a startcore or a
 notification, the kernel will set the stack pointer to whatever is requested
@@ -198,7 +210,8 @@ be dealt with.
 When the caller next switches to _M, that context (including its stack)
 maintains its old vcore identity.  If vcore3 causes the switch to _S mode, it
 ought to remain vcore3 (lots of things get broken otherwise).
-As of March 2010, the code does not reflect this
+As of March 2010, the code does not reflect this.  Don't rely on anything in
+this section for the time being.
 
 2.4.3: Requesting more cores while in _M
 --------------
@@ -208,29 +221,40 @@ from _S to _M: at the entry point.
 
 2.4.4: Yielding
 --------------
-This will get revised soon, to account for different types of yields.
-
-Yielding gives up a core.  In _S mode, it will transition from RUNNING_S to
-RUNNABLE_S.  The context is saved in env_tf.  A yield will *not* transition
-from _M to _S.
-
-In _M mode, this yields the calling core.  The kernel will rip it out of your
-vcore list.  A process can yield its cores in any order.  The kernel will
-"fill in the holes of the vcoremap" when for any future newcores (e.g., proc A
-has 4 vcores, yields vcore2, and then asks for another vcore.  The new one
-will be vcore2).
-
-When you are in _M and yield your last core, it is an m_yield.  This
-completely suspends all cores, like a voluntary preemption.  When the process
-is run again, all cores will come up at the entry point (including vcore0 and
-the calling core).  This isn't implemented yet, and will wait on some work
-with preemption.
-
-We also need a type of yield (or a flag) that says the process is just giving
-up the core temporarily, but actually wants the core and does not want
-resource requests to be readjusted.  For example, in the event of a preemption
+sys_yield()/proc_yield() will give up the calling core, and may or may not
+adjust the desired number of cores, subject to its parameters.  Yield is
+performing two tasks, both of which result in giving up the core.  One is for
+not wanting the core anymore.  The other is in response to a preemption.  Yield
+may not be called remotely (ARSC).
+
+In _S mode, it will transition from RUNNING_S to RUNNABLE_S.  The context is
+saved in scp_ctx.
+
+In _M mode, this yields the calling core.  A yield will *not* transition from _M
+to _S.  The kernel will rip it out of your vcore list.  A process can yield its
+cores in any order.  The kernel will "fill in the holes of the vcoremap" for any
+future new cores requested (e.g., proc A has 4 vcores, yields vcore2, and then
+asks for another vcore.  The new one will be vcore2).  When any core starts in
+_M mode, even after a yield, it will come back at the vcore_entry()/_start point.
+
+Yield will normally adjust your desired amount of vcores to the amount after the
+calling core is taken.  This is the way a process gives its cores back.
+
+Yield can also be used to say the process is just giving up the core in response
+to a pending preemption, but actually wants the core and does not want resource
+requests to be readjusted.  For example, in the event of a preemption
 notification, a process may yield (ought to!) so that the kernel does not need
-to waste effort with full preemption.
+to waste effort with full preemption.  This is done by passing in a bool
+(being_nice), which signals the kernel that it is in response to a preemption.
+The kernel will not readjust the amt_wanted, and if there is no preemption
+pending, the kernel will ignore the yield.
+
+There may be an m_yield(), which will yield all or some of the cores of an MPC,
+remotely.  This is discussed farther down a bit.  It's not clear what exactly
+it's purpose would be.
+
+We also haven't addressed other reasons to yield, or more specifically to wait,
+such as for an interrupt or an event of some sort.
 
 2.4.5: Others
 --------------
@@ -309,6 +333,8 @@ In procdata there is an array of per-vcore data, holding some
 preempt/notification information and space for two trapframes: one for
 notification and one for preemption.
 
+4.2.1: Overall
+-----------------------------
 When a notification arrives to a process under normal circumstances, the
 kernel places the previous running context in the notification trapframe, and
 returns to userspace at the program entry point (the elf entry point) on the
@@ -321,28 +347,26 @@ bother sending IPIs, and if an IPI is sent before notifications are masked,
 then the kernel will double-check this flag to make sure interrupts should
 have arrived.
 
-Notification unmasking is done by setting the notif_enabled flag (similar to
-turning interrupts on in hardware).  When a core starts up, this flag is off,
+Notification unmasking is done by clearing the notif_disabled flag (similar to
+turning interrupts on in hardware).  When a core starts up, this flag is on,
 meaning that notifications are disabled by default.  It is the process's
 responsibility to turn on notifications for a given vcore.
 
+4.2.2: Notif Event Details
+-----------------------------
 When the process runs the handler, it is actually starting up at the same
-location in code as it always does, so the kernel will pass it a parameter in
-a register to let it know that it is in a notification.  Additionally, the
-kernel will mask notifications (much like an x86 interrupt gate).  The process
-must check its per-core event queue to see why it was called, and deal with
-all of the events on the queue.  In the case where the event queue overflows,
-the kernel will up a counter so the process can at least be aware things are
-missed.
-
-For missed events, and for events that do not need messages (they have no
-parameters and multiple notifications are irrelevant), the kernel will toggle
-that event's bit in a bitmask.  For the events that don't want messages, we may
-have a flag that userspace sets, meaning they just want to know it happened.
-This might be too much of a pain, so we'll see.  For notification events that
-overflowed the queue, the parameters will be lost, but hopefully the application
-can sort it out.  Again, we'll see.  A specific notif_event should not appear in
-both the event buffers and in the bitmask.
+location in code as it always does.  To determine if it was a notification or
+not, simply check the queue and bitmask.  This has the added benefit of allowing
+a process to notice notifications that it missed previously, or notifs it wanted
+without active notification (IPI).  If we want to bypass this check by having a
+magic register signal, we can add that later.  Additionally, the kernel will
+mask notifications (much like an x86 interrupt gate).  It will also mask
+notifications when starting a core with a fresh trapframe, since the process
+will be executing on its transition stack.  The process must check its per-core
+event queue to see why it was called, and deal with all of the events on the
+queue.  In the case where the event queue overflows, the kernel will up a
+counter so the process can at least be aware things are missed.  At the very
+least, the process will see the notification marked in a bitmask.
 
 These notification events include things such as: an IO is complete, a
 preemption is pending to this core, the process just returned from a
@@ -357,10 +381,51 @@ masked, the process will simply be killed.    It is up to the process to make
 sure the appropriate pages are pinned, which it should do before entering _M
 mode.
 
+4.2.3: Event Overflow and Non-Messages
+-----------------------------
+For missed/overflowed events, and for events that do not need messages (they
+have no parameters and multiple notifications are irrelevant), the kernel will
+toggle that event's bit in a bitmask.  For the events that don't want messages,
+we may have a flag that userspace sets, meaning they just want to know it
+happened.  This might be too much of a pain, so we'll see.  For notification
+events that overflowed the queue, the parameters will be lost, but hopefully the
+application can sort it out.  Again, we'll see.  A specific notif_event should
+not appear in both the event buffers and in the bitmask.
+
+It does not make sense for all events to have messages.  Others, it does not
+make sense to specify a different core on which to run the handler (e.g. page
+faults).  The notification methods that the process expresses via procdata are
+suggestions to the kernel.  When they don't make sense, they will be ignored.
+Some notifications might be unserviceable without messages.  A process needs to
+have a fallback mechanism.  For example, they can read the vcoremap to see who
+was lost, or they can restart a thread to cause it to page fault again.
+
+Event overflow sucks - it leads to a bunch of complications.  Ultimately, what
+we really want is a limitless amount of notification messages (per core), as
+well as a limitless amount of notification types.  And we want these to be
+relayed to userspace without trapping into the kernel. 
+
+We could do this if we had a way to dynamically manage memory in procdata, with
+a distrusted process on one side of the relationship.  We could imagine growing
+procdata dynamically (we plan to, mostly to grow the preempt_data struct as we
+request more vcores), and then run some sort of heap manager / malloc.  Things
+get very tricky since the kernel should never follow pointers that userspace can
+touch.  Additionally, whatever memory management we use becomes a part of the
+kernel interface.  
+
+Even if we had that, dynamic notification *types* is tricky - they are
+identified by a number, not by a specific (list) element.
+
+For now, this all seems like an unnecessary pain in the ass.  We might adjust it
+in the future if we come up with clean, clever ways to deal with the problem,
+which we aren't even sure is a problem yet.
+
+4.2.4: How to Use and Leave a Transition Stack
+-----------------------------
 We considered having the kernel be aware of a process's transition stacks and
 sizes so that it can detect if a vcore is in a notification handler based on
 the stack pointer in the trapframe when a trap or interrupt fires.  While
-cool, the flag for notif_enabled is much easier and just as capable.
+cool, the flag for notif_disabled is much easier and just as capable.
 Userspace needs to be aware of various races, and only enable notifications
 when it is ready to have its transition stack clobbered.  This means that when
 switching from big user-thread to user-thread, the process should temporarily
@@ -382,32 +447,45 @@ notification queue/list is empty before moving back to real code.  Then it
 should jump back to a real stack, unmask notifications, and jump to the newly
 scheduled thread.
 
+This can be really tricky.  When userspace is changing threads, it will need to
+unmask notifs as well as jump to the new thread.  There is a slight race here,
+but it is okay.  The race is that an IPI can arrive after notifs are unmasked,
+but before returning to the real user thread.  Then the code will think the
+uthread_ctx represents the new user thread, even though it hasn't started (and
+the PC is wrong).  The trick is to make sure that all state required to start
+the new thread, as well as future instructions, are all saved within the "stuff"
+that gets saved in the uthread_ctx.  When these threading packages change
+contexts, they ought to push the PC on the stack of the new thread, (then enable
+notifs) and then execute a return.  If an IPI arrives before the "function
+return", then when that context gets restarted, it will run the "return" with
+the appropriate value on the stack still.
+
+There is a further complication.  The kernel can send an IPI that the process
+wanted, but the vcore did not get truly interrupted since its notifs were
+disabled.  There is a race between checking the queue/bitmask and then enabling
+notifications.  The way we deal with it is that the kernel posts the
+message/bit, then sets notif_pending.  Then it sends the IPI, which may or may
+not be received (based on notif_disabled).  (Actually, the kernel only ought to
+send the IPI if notif_pending was 0 (atomically) and notif_disabled is 0).  When
+leaving the transition stack, userspace should clear the notif_pending, then
+check the queue do whatever, and then try to pop the tf.  When popping the tf,
+after enabling notifications, check notif_pending.  If it is still clear, return
+without fear of missing a notif.  If it is not clear, it needs to manually
+notify itself (sys_self_notify) so that it can process the notification that it
+missed and for which it wanted to receive an IPI.  Before it does this, it needs
+to clear notif_pending, so the kernel will send it an IPI.  These last parts are
+handled in pop_user_ctx().
+
 4.3: Preemption Specifics
 -------------------------------
-When a vcore is preempted, the kernel takes whatever context was running (which
-could be a notification context) and stores it in the preempt trapframe for
-that vcore in procdata.  There is also a flag (actually a counter) that states
-if the context there has been sorted out.  Userspace should set this once it
-has copied out the data and dealt with it accordingly.
-
-The invariant regarding the preemption slot is that there should never be
-anything running on a vcore when there is a valid/not-sorted preempt
-trapframe.  The reason is that a preemption can come in at any time (such as
-right after returning from a preemption).
-
-To maintain this invariant, when the kernel starts a vcore, it will run the
-context that is in the preempt trapframe if the "preempt_tf_sorted" (name will
-change) flag is not set.  A process needs to be careful of a race here.  If
-they are trying to deal with a preempt trapframe (must be from another vcore,
-btw), the kernel could start to run that trapframe (in case it is granting a
-core request / proc_startcore()ing).  When the kernel prepares to use the
-trapframe (which it will do regardless of userspace activities), it will up
-the flag/counter.  If the process notices a change in that flag, it ought to
-abort its operation.  It can up the counter on its own when it no longer wants
-the kernel to run that context (this means it can get clobbered).
+There's an issue with a preempted vcore getting restarted while a remote core
+tries to restart that context.  They resolve this fight with a variety of VC
+flags (VC_UTHREAD_STEALING).  Check out handle_preempt() in uthread.c.
 
 4.4: Other trickiness
 -------------------------------
+Take all of these with a grain of salt - it's quite old.
+
 4.4.1: Preemption -> deadlock
 -------------------------------
 One issue is that a context can be holding a lock that is necessary for the
@@ -458,31 +536,9 @@ hardware interrupts (on x86, at least).
 
 4.4.3: Restarting a Preempted Notification
 -------------------------------
-There will be cases where the trapframe in the preempt_tf slot is actually a
-notification handler, which was running on the transition stack of that
-particular vcore.  Userspace needs to be careful about restarting contexts
-that were on those cores.  They can tell by examining the stack pointer to see
-if it was on a transition stack.  Alternatively, if notifications are masked,
-it is also likely they in a notification handler.  The real concern is the
-transition stack.  If a vcore is processing on the transition stack of another
-vcore, there is a risk that the vcore comes back up and starts clobbering the
-transition stack.
-
-To avoid this, userspace should allocate a new transition stack and switch the
-target vcore to use that new stack (in procdata).  The only time (for now)
-that the kernel cares about a transition stack is when it is popping a tf on a
-new or freshly notified vcore.
-
-This all should be a rare occurance, since the vcore should see the
-preempt_pending when it starts its notification and yield, instead of being
-forced into this weird situation.  This also means that notifications should
-take less time than the kernel will wait before preempting.
-
-This issue ties in with deadlocking in 4.4.1.  If userspace is never in a
-notif handler when it gets preempted, that deadlock will not happen (and we
-also may need only one trapframe slot).  Userspace probably cannot guarantee
-that, so we'll have to deal with it.  Avoiding the deadlock on a spinlock is
-much more reasonable (and we can provide the locking function).
+Nowadays, to restart a preempted notification, you just restart the vcore.
+The kernel does, either if it gives the process more cores or if userspace asked
+it to with a sys_change_vcore().
 
 4.4.4: Userspace Yield Races
 -------------------------------
@@ -498,9 +554,9 @@ yield and simply return to userspace.
 4.4.5: Userspace m_yield
 -------------------------------
 There are a variety of ways to implement an m_yield (yield the entire MCP).
-We could have a "no niceness" yield - just immediately preempt, but there is a danger of the
-locking business.  We could do the usual delay game, though if userspace is
-requesting its yield, arguably we don't need to give warning. 
+We could have a "no niceness" yield - just immediately preempt, but there is a
+danger of the locking business.  We could do the usual delay game, though if
+userspace is requesting its yield, arguably we don't need to give warning. 
 
 Another approach would be to not have an explicit m_yield call.  Instead, we
 can provide a notify_all call, where the notification sent to every vcore is