Removed event overflow handling

[akaros.git] / Documentation / process-internals.txt

diff --git a/Documentation/process-internals.txt b/Documentation/process-internals.txt
index f293d63..87b9c73 100644 (file)
--- a/Documentation/process-internals.txt
+++ b/Documentation/process-internals.txt
@@ -9,31 +9,32 @@ they muck with how processes work.
 Contents:
 1. Reference Counting
 2. When Do We Really Leave "Process Context"?
 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. TLB Coherency
+8. TBD

 
 1. Reference Counting
 ===========================
 1.1 Basics:
 ---------------------------
 
 1. Reference Counting
 ===========================
 1.1 Basics:
 ---------------------------

-Reference counts (proc_refcnt) exist to keep a process alive.  Eventually, this
-will probably turn into a regular "kernel design pattern", like it is in Linux
-(http://lwn.net/Articles/336224/).  The style of reference counting we use for
-processes is similar to a kref:
+Reference counts exist to keep a process alive.  We use krefs for this, similar
+to Linux's kref:

 - Can only incref if the current value is greater than 0, meaning there is
   already a reference to it.  It is a bug to try to incref on something that has
   no references, so always make sure you incref something that you know has a
 - Can only incref if the current value is greater than 0, meaning there is
   already a reference to it.  It is a bug to try to incref on something that has
   no references, so always make sure you incref something that you know has a

-  reference.  If you don't know, you need to get it manually (CAREFULLY!) or use
-  pid2proc (which is a careful way of doing this).  If you incref and there are
-  0 references, the kernel will panic.  Fix your bug / don't incref random
-  pointers.
+  reference.  If you don't know, you need to get it from pid2proc (which is a
+  careful way of doing this - pid2proc kref_get_not_zero()s on the reference that is
+  stored inside it).  If you incref and there are 0 references, the kernel will
+  panic.  Fix your bug / don't incref random pointers.

 - Can always decref.
 - When the decref returns 0, perform some operation.  This does some final
   cleanup on the object.
 - Can always decref.
 - When the decref returns 0, perform some operation.  This does some final
   cleanup on the object.

-
-For a process, proc_destroy() decrefs, and other codes using the proc also
-decref.  The last one to decref calls proc_free to do the final cleanup.
+- Process code is trickier since we frequently make references from 'current'
+  (which isn't too bad), but also because we often do not return and need to be
+  careful about the references we passed in to a no-return function.

 
 1.2 Brief History of the Refcnt:
 ---------------------------
 
 1.2 Brief History of the Refcnt:
 ---------------------------


@@ -57,7 +58,15 @@ protected by a refcnt.
 ---------------------------
 +1 for existing.
 - The fact that the process is supposed to exist is worth +1.  When it is time
 ---------------------------
 +1 for existing.
 - The fact that the process is supposed to exist is worth +1.  When it is time

-  to die, we decref, and it will eventually be cleaned up.
+  to die, we decref, and it will eventually be cleaned up.  This existence is
+  explicitly kref_put()d in proc_destroy().
+- The hash table is a bit tricky.  We need to kref_get_not_zero() when it is
+  locked, so we know we aren't racing with proc_free freeing the proc and
+  removing it from the list.  After removing it from the hash, we don't need to
+  kref_put it, since it was an internal ref.  The kref (i.e. external) isn't for
+  being on the hash list, it's for existing.  This separation allows us to
+  remove the proc from the hash list in the "release" function.  See kref.txt
+  for more details.

 
 +1 for someone using it or planning to use it.
 - This includes simply having a pointer to the proc, since presumably you will
 
 +1 for someone using it or planning to use it.
 - This includes simply having a pointer to the proc, since presumably you will


@@ -70,7 +79,11 @@ protected by a refcnt.
 
 +1 for current.
 - current counts as someone using it (expressing interest in the core), but is
 
 +1 for current.
 - current counts as someone using it (expressing interest in the core), but is

-  also a source of the pointer, so its a bit different.
+  also a source of the pointer, so its a bit different.  Note that all kref's
+  are sources of a pointer.  Technically, to even use 'current', we should kref
+  it and pass it around as a proc.  We don't for performance reasons.  When we
+  are running on a core that has current loaded, the ref is both for its usage
+  as well as for being the current process.

 - You have a reference from current and can use it without refcnting, but
   anything that needs to eat a reference or store/use it needs an incref first.
   To be clear, your reference is *NOT* edible.  It protects the cr3, guarantees
 - You have a reference from current and can use it without refcnting, but
   anything that needs to eat a reference or store/use it needs an incref first.
   To be clear, your reference is *NOT* edible.  It protects the cr3, guarantees


@@ -79,8 +92,9 @@ protected by a refcnt.
   an IO continuation request), then clearly you must incref, since it's both
   current and stored/used.
 - If you don't know what might be downstream from your function, then incref
   an IO continuation request), then clearly you must incref, since it's both
   current and stored/used.
 - If you don't know what might be downstream from your function, then incref

-  before passing the reference, and decref when it returns.  Like when handling
-  syscalls, for example.
+  before passing the reference, and decref when it returns.  We used to do this
+  for all syscalls, but now only do it for calls that might not return and
+  expect to receive reference (like proc_yield).

 
 All functions that take a *proc have a refcnt'd reference, though it may not be
 edible (it could be current).  It is the callers responsibility to make sure
 
 All functions that take a *proc have a refcnt'd reference, though it may not be
 edible (it could be current).  It is the callers responsibility to make sure


@@ -99,6 +113,11 @@ This means that you must have a reference when you call them (like always), and
 that reference will be consumed / decref'd for you if the function doesn't
 return.  Or something similarly appropriate.
 
 that reference will be consumed / decref'd for you if the function doesn't
 return.  Or something similarly appropriate.
 

+Arguably, for functions that MAY not return, but will always be called with
+current's reference (proc_yield()), we could get away without giving it an
+edible reference, and then never eating the ref.  Yield needs to be reworked
+anyway, so it's not a bit deal yet.
+

 We do this because when the function does not return, you will not have the
 chance to decref (your decref code will never run).  We need the reference when
 going in to keep the object alive (like with any other refcnt).  We can't have
 We do this because when the function does not return, you will not have the
 chance to decref (your decref code will never run).  We need the reference when
 going in to keep the object alive (like with any other refcnt).  We can't have


@@ -445,7 +464,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
 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
 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


@@ -527,13 +546,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
 ---------------------------
 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
 ---------------------------
  
 4.7: Notifs While a Preempt Message is Served
 ---------------------------


@@ -548,10 +581,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).
 
 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"
 quickly trying to determine what to do.
 
 4.8: When a Pcore is "Free"


@@ -645,5 +678,199 @@ 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.
 
 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. TLB Coherency
+===========================
+When changing or removing memory mappings, we need to do some form of a TLB
+shootdown.  Normally, this will require sending an IPI (immediate kmsg) to
+every vcore of a process to unmap the affected page.  Before allocating that
+page back out, we need to make sure that every TLB has been flushed.  
+
+One reason to use a kmsg over a simple handler is that we often want to pass a
+virtual address to flush for those architectures (like x86) that can
+invalidate a specific page.  Ideally, we'd use a broadcast kmsg (doesn't exist
+yet), though we already have simple broadcast IPIs.
+
+7.1 Initial Stuff
+---------------------------
+One big issue is whether or not to wait for a response from the other vcores
+that they have unmapped.  There are two concerns: 1) Page reuse and 2) User
+semantics.  We cannot give out the physical page while it may still be in a
+TLB (even to the same process.  Ask us about the pthread_test bug).
+
+The second case is a little more detailed.  The application may not like it if
+it thinks a page is unmapped or protected, and it does not generate a fault.
+I am less concerned about this, especially since we know that even if we don't
+wait to hear from every vcore, we know that the message was delivered and the
+IPI sent.  Any cores that are in userspace will have trapped and eventually
+handle the shootdown before having a chance to execute other user code.  The
+delays in the shootdown response are due to being in the kernel with
+interrupts disabled (it was an IMMEDIATE kmsg).
+
+7.2 RCU
+---------------------------
+One approach is similar to RCU.  Unmap the page, but don't put it on the free
+list.  Instead, don't reallocate it until we are sure every core (possibly
+just affected cores) had a chance to run its kmsg handlers.  This time is
+similar to the RCU grace periods.  Once the period is over, we can then truly
+free the page.
+
+This would require some sort of RCU-like mechanism and probably a per-core
+variable that has the timestamp of the last quiescent period.  Code caring
+about when this page (or pages) can be freed would have to check on all of the
+cores (probably in a bitmask for what needs to be freed).  It would make sense
+to amortize this over several RCU-like operations.
+
+7.3 Checklist
+---------------------------
+It might not suck that much to wait for a response if you already sent an IPI,
+though it incurs some more cache misses.  If you wanted to ensure all vcores
+ran the shootdown handler, you'd have them all toggle their bit in a checklist
+(unused for a while, check smp.c).  The only one who waits would be the
+caller, but there still are a bunch of cache misses in the handlers.  Maybe
+this isn't that big of a deal, and the RCU thing is an unnecessary
+optimization.
+
+7.4 Just Wait til a Context Switch
+---------------------------
+Another option is to not bother freeing the page until the entire process is
+descheduled.  This could be a very long time, and also will mess with
+userspace's semantics.  They would be running user code that could still
+access the old page, so in essence this is a lazy munmap/mprotect.  The
+process basically has the page in pergatory: it can't be reallocated, and it
+might be accessible, but can't be guaranteed to work.
+
+The main benefit of this is that you don't need to send the TLB shootdown IPI
+at all - so you don't interfere with the app.  Though in return, they have
+possibly weird semantics.  One aspect of these weird semantics is that the
+same virtual address could map to two different pages - that seems like a
+disaster waiting to happen.  We could also block that range of the virtual
+address space from being reallocated, but that gets even more tricky.
+
+One issue with just waiting and RCU is memory pressure.  If we actually need
+the page, we will need to enforce an unmapping, which sucks a little.
+
+7.5 Bulk vs Single
+---------------------------
+If there are a lot of pages being shot down, it'd be best to amortize the cost
+of the kernel messages, as well as the invlpg calls (single page shootdowns).
+One option would be for the kmsg to take a range, and not just a single
+address.  This would help with bulk munmap/mprotects.  Based on the number of
+these, perhaps a raw tlbflush (the entire TLB) would be worth while, instead
+of n single shots.  Odds are, that number is arch and possibly workload
+specific.
+
+For now, the plan will be to send a range and have them individually shot
+down.
+
+7.6 Don't do it
+---------------------------
+Either way, munmap/mprotect sucks in an MCP.  I recommend not doing it, and
+doing the appropriate mmap/munmap/mprotects in _S mode.  Unfortunately, even
+our crap pthread library munmaps on demand as threads are created and
+destroyed.  The vcore code probably does in the bowels of glibc's TLS code
+too, though at least that isn't on every user context switch.
+
+7.7 Local memory
+---------------------------
+Private local memory would help with this too.  If each vcore has its own
+range, we won't need to send TLB shootdowns for those areas, and we won't have
+to worry about weird application semantics.  The downside is we would need to
+do these mmaps in certain ranges in advance, and might not easily be able to
+do them remotely.  More on this when we actually design and build it.
+
+7.8 Future Hardware Support
+---------------------------
+It would be cool and interesting if we had the ability to remotely shootdown
+TLBs.  For instance, all cores with cr3 == X, shootdown range Y..Z.  It's
+basically what we'll do with the kernel message and the vcoremap, but with
+magic hardware.
+
+7.9 Current Status
+---------------------------
+For now, we just send a kernel message to all vcores to do a full TLB flush,
+and not to worry about checklists, waiting, or anything.  This is due to being
+short on time and not wanting to sort out the issue with ranges.  The way
+it'll get changed to is to send the kmsg with the range to the appropriate
+cores, and then maybe put the page on the end of the freelist (instead of the
+head).  More to come.
+
+8. TBD

 ===========================
 ===========================