Added the CONFIG_OSDI option to the template
[akaros.git] / Documentation / process-internals.txt
index 2175032..c70ee55 100644 (file)
@@ -9,9 +9,11 @@ they muck with how processes work.
 Contents:
 1. Reference Counting
 2. When Do We Really Leave "Process Context"?
-3. Leaving the Kernel Stack:
-4. Preemption and Notification Issues:
-5. TBD
+3. Leaving the Kernel Stack
+4. Preemption and Notification Issues
+5. Current_tf
+6. Locking!
+7. TBD
 
 1. Reference Counting
 ===========================
@@ -90,7 +92,7 @@ stores or makes a copy of the reference.
 1.5 Functions That Don't or Might Not Return:
 ---------------------------
 Refcnting and especially decreffing gets tricky when there are functions that
-MAY not return.  proc_startcore() does not return (it pops into userspace).
+MAY not return.  proc_restartcore() does not return (it pops into userspace).
 proc_run() might not return, if the core it was called on will pop into
 userspace (if it was a _S, or if the core is part of the vcoremap for a _M).
 
@@ -120,10 +122,11 @@ proc_run(pid2proc(55)) works, since pid2proc() increfs for you.  But you cannot
 proc_run(current), unless you incref current in advance.  Incidentally,
 proc_running current doesn't make a lot of sense.
 
-As another example, proc_startcore() will take your reference and store it
+As another example, __proc_startcore() will take your reference and store it
 in current.  Since it is used by both the __startcore and the interrupt return
-paths, we're currently going with the model of "caller makes sure there is a ref
-for current".  Check its comments for details.
+paths (proc_restartcore() now, formerly called proc_startcore()), we're
+currently going with the model of "caller makes sure there is a ref for
+current".  Check its comments for details.
 
 1.6 Runnable List:
 ---------------------------
@@ -147,7 +150,7 @@ Also note that while proc_run() consumes your reference, it's not actually
 decreffing, so there's no danger within proc_run() of the process dying /
 __proc_free()ing.
 
-proc_startcore(): assumes all references to p are sorted.  *p is already
+__proc_startcore(): assumes all references to p are sorted.  *p is already
 accounted for as if it was current on the core startcore runs on. (there is only
 one refcnt for both *p and current, not 2 separate ones).
 
@@ -255,13 +258,13 @@ specifically talking about when a process's cr3 is loaded on a core.  Usually,
 current is also set (the exception for now is when processing ARSCs).
 
 There are a couple different ways to do this.  One is to never unload a context
-until something new is being run there (handled solely in proc_startcore()).
+until something new is being run there (handled solely in __proc_startcore()).
 Another way is to always explicitly leave the core, like by abandon_core()ing.
 
 The issue with the former is that you could have contexts sitting around for a
 while, and also would have a bit of extra latency when __proc_free()ing during
-someone *else's* proc_startcore() (though that could be avoided if it becomes a
-real issue, via some form of reaping).  You'll also probably have excessive
+someone *else's* __proc_startcore() (though that could be avoided if it becomes
+real issue, via some form of reaping).  You'll also probably have excessive
 decrefs (based on the interactions between proc_run() and __startcore()).
 
 The issue with the latter is excessive TLB shootdowns and corner cases.  There
@@ -275,7 +278,7 @@ process's context is loaded.
 2.2 Here's how it is done now:
 ---------------------------
 We try to proactively leave, but have the ability to stay in context til
-proc_startcore() to handle the corner cases (and to maybe cut down the TLB
+__proc_startcore() to handle the corner cases (and to maybe cut down the TLB
 flushes later).  To stop proactively leaving, just change abandon_core() to not
 do anything with current/cr3.  You'll see weird things like processes that won't
 die until their old cores are reused.  The reason we proactively leave context
@@ -283,9 +286,9 @@ is to help with sanity for these issues, and also to avoid decref's in
 __startcore().
 
 A couple other details: __startcore() sorts the extra increfs, and
-proc_startcore() sorts leaving the old context.  Anytime a __startcore kernel
+__proc_startcore() sorts leaving the old context.  Anytime a __startcore kernel
 message is sent, the sender increfs in advance for the current refcnt.  If that
-was in error, __startcore decrefs.  proc_startcore(), which the last moment
+was in error, __startcore decrefs.  __proc_startcore(), which the last moment
 before we *must* have the cr3/current issues sorted, does the actual check if
 there was an old process there or not, while it handles the lcr3 (if necessary).
 In general, lcr3's ought to have refcnts near them, or else comments explaining
@@ -310,7 +313,7 @@ Note that dealing with interrupting processes that are in the kernel is tricky.
 There is no true process context, so we can't leave a core until the kernel is
 in a "safe place", i.e. it's state is bundled enough that it can be recontinued
 later.  Calls of this type are routine kernel messages, executed at a convenient
-time (specifically, before we return to userspace in proc_startcore().
+time (specifically, before we return to userspace in proc_restartcore().
 
 This same thing applies to __death messages.  Even though a process is dying, it
 doesn't mean we can just drop whatever the kernel was doing on its behalf.  For
@@ -331,10 +334,32 @@ the old "active messages" into a generic work execution message (a kernel
 message) that can be delayed or shipped to another core.  These types of
 messages will not be executed immediately on the receiving pcore - instead they
 are on the queue for "when there's nothing else to do in the kernel", which is
-checked in smp_idle() and before returning to userspace in proc_startcore().
+checked in smp_idle() and before returning to userspace in proc_restartcore().
 Additionally, these kernel messages can also be queued on an alarm queue,
 delaying their activation as part of a generic kernel alarm facility.
 
+One subtlety is that __proc_startcore() shouldn't check for messages, since it
+is called by __startcore (a message).  Checking there would run the messages out
+of order, which is exactly what we are trying to avoid (total chaos).  No one
+should call __proc_startcore, other than proc_restartcore() or __startcore().
+If we ever have functions that do so, if they are not called from a message,
+they must check for outstanding messages.
+
+This last subtlety is why we needed to change proc_run()'s _S case to use a
+local message instead of calling proc_starcore (and why no one should ever call
+proc_startcore()).  We could unlock, thereby freeing another core to change the
+proc state and send a message to us, then try to proc_startcore, and then
+reading the message before we had installed current or had a userspace TF to
+preempt, and probably a few other things.  Treating _S as a local message is
+cleaner, begs to be merged in the code with _M's code, and uses the messaging
+infrastructure to avoid all the races that it was created to handle.
+
+Incidentally, we don't need to worry about missing messages while trying to pop
+back to userspace from __proc_startcore, since an IPI will be on the way
+(possibly a self-ipi caused by the __kernel_message() handler).  This is also
+why we needed to make process_routine_kmsg() keep interrupts disabled when it
+stops (there's a race between checking the queue and disabling ints).
+
 4. Preemption and Notification Issues:
 ===========================
 4.1: Message Ordering and Local Calls:
@@ -422,7 +447,7 @@ that notification hits, it will be for a proc that isn't current, and will be
 ignored (it will get run the next time that vcore fires up, handled below).
 
 There is a slight chance that the same proc will run on that pcore, but with a
-different vcore.  In the off chance this happens, the new vcore will get a
+different vcoreid.  In the off chance this happens, the new vcore will get a
 spurious notification.  Userspace needs to be able to handle spurious
 notifications anyways, (there are a couple other cases, and in general it's
 not hard to do), so this is not a problem.  Instead of trying to have the
@@ -504,13 +529,27 @@ preempt-critical locks.
 ---------------------------
 It is possible that notifications will mix with preemptions or come while a
 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.  If the vcore is offline or is in a preempt-phase, 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 userspace can toggle this, so they can handle
-the notifications from a different core if it likes, or they can independently
-send a notification.
+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
+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.
+
+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
+need to be able to send one.  Additionally, once the vcore is handling that
+preemption notification, it will have notifs disabled, which will prevent us
+from sending any extra notifications anyways.
  
 4.7: Notifs While a Preempt Message is Served
 ---------------------------
@@ -525,10 +564,10 @@ 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).
 
-We could try to just set the notif_pending flag and ignore the message, but
-that would involve inspecting the queue for the preempt k_msg.  Additionally,
-a preempt k_msg can arrive anyway.  Finally, it's possible to have another
-message in the queue between the notif and the preempt, and it gets ugly
+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.
+Additionally, a preempt k_msg can arrive anyway.  Finally, it's possible to have
+another message in the queue between the notif and the preempt, and it gets ugly
 quickly trying to determine what to do.
 
 4.8: When a Pcore is "Free"
@@ -622,5 +661,83 @@ 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. TBD
+5. current_tf
+===========================
+current_tf is 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.
+
+current_tf should go along with current.  It's the current_tf of the current
+process.  Withouth 'current', it has no meaning.
+
+It 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.
+
+6. Locking!
+===========================
+6.1: proc_lock
+---------------------------
+Currently, all locking is done on the proc_lock.  It's main goal is to protect
+the vcore mapping (vcore->pcore and vice versa).  As of Apr 2010, it's also used
+to protect changes to the address space and the refcnt.  Eventually the refcnt
+will be handled with atomics, and the address space will have it's own MM lock.  
+
+We grab the proc_lock all over the place, but we try to avoid it whereever
+possible - especially in kernel messages or other places that will be executed
+in parallel.  One place we do grab it but would like to not is in proc_yield().  
+We don't always need to grab the proc lock.  Here are some examples:
+
+6.1.1: Lockless Notifications:
+-------------
+We don't lock when sending a notification.  We want the proc_lock to not be an
+irqsave lock (discussed below).  Since we might want to send a notification from
+interrupt context, we can't grab the proc_lock if it's a regular lock.  
+
+This is okay, since the proc_lock is only protecting the vcoremapping.  We could
+accidentally send the notification to the wrong pcore.  The __notif handler
+checks to make sure it is the right process, and all _M processes should be able
+to handle spurious notifications.  This assumes they are still _M.
+
+If we send it to the wrong pcore, there is a danger of losing the notif, since
+it didn't go to the correct vcore.  That would happen anyway, (the vcore is
+unmapped, or in the process of mapping).  The notif_pending flag will be caught
+when the vcore is started up next time (and that flag was set before reading the
+vcoremap).
+
+6.1.2: Local get_vcoreid():
+-------------
+It's not necessary to lock while checking the vcoremap if you are checking for
+the core you are running on (e.g. pcoreid == core_id()).  This is because all
+unmappings of a vcore are done on the receive side of a routine kmsg, and that
+code cannot run concurrently with the code you are running.  
+
+6.2: irqsave
+---------------------------
+The proc_lock used to be an irqsave lock (meaning it disables interrupts and can
+be grabbed from interrupt context).  We made it a regular lock for a couple
+reasons.  The immediate one was it was causing deadlocks due to some other
+ghetto things (blocking on the frontend server, for instance).  More generally,
+we don't want to disable interrupts for long periods of time, so it was
+something worth doing anyway.  
+
+This means that we cannot grab the proc_lock from interrupt context.  This
+includes having schedule called from an interrupt handler (like the
+timer_interrupt() handler), since it will call proc_run.  Right now, we actually
+do this, which we shouldn't, and that will eventually get fixed.  The right
+answer is that the actual work of running the scheduler should be a routine
+kmsg, similar to how Linux sets a bit in the kernel that it checks on the way
+out to see if it should run the scheduler or not.
+
+7. TBD
 ===========================