Support atomic printks
[akaros.git] / Documentation / kthreads.txt
index a79a318..d87a951 100644 (file)
@@ -73,8 +73,8 @@ Freeing Stacks and Structs
 -------------------------------
 When we restart a kthread, we have to be careful about freeing the old stack and
 the struct kthread.  We need to delay the freeing of both of these until after
-we pop_kernel_ctx().  We can't free the kthread before popping it, and we are on
-the stack we need to free (until we pop to the new stack).
+we longjmp to the new kthread.  We can't free the kthread before popping it,
+and we are on the stack we need to free (until we pop to the new stack).
 
 To deal with this, we have a "spare" kthread per core, which gets assigned as
 the spare when we restart a previous kthread.  When making/suspending a kthread,
@@ -125,16 +125,16 @@ loses the race (unlikely), it can manually unwind.
 
 Note that a lot of this is probably needless worry - we have interrupts disabled
 for most of sleep_on(), though arguably we can be a little more careful with
-pcpui->spare and move the disable_irq() down to right before save_kernel_ctx().
+pcpui->spare and move the disable_irq() down to right before setjmp().
 
 What's the Deal with Stacks/Stacktops?
 -------------------------------
 When the kernel traps from userspace, it needs to know what to set the kernel
-stack pointer to.  In x86, it looks in the TSS.  In sparc, we have a data
+stack pointer to.  In x86, it looks in the TSS.  In riscv, we have a data
 structure tracking that info (core_stacktops).  One thing I considered was
-migrating the kernel from its boot stacks (x86, just core0, sparc, all the cores
+migrating the kernel from its boot stacks (x86, just core0, riscv, all the cores
 have one).  Instead, we just make sure the tables/TSS are up to date right away
-(before interrupts or traps can come in for x86, and right away for sparc).
+(before interrupts or traps can come in for x86, and right away for riscv).
 These boot stacks aren't particularly special, just note they are in the program
 data/bss sections and were never originally added to a free list.  But they can
 be freed later on.  This might be an issue in some places, but those places
@@ -166,7 +166,7 @@ kthread run with its stack as the default stacktop.
 
 When restarting a kthread, we eventually will use its stack, instead of the
 current one, but we can't free the current stack until after we actually
-pop_kernel_ctx().  this is the same problem as with the struct kthread dealloc.
+longjmp() to it.  This is the same problem as with the struct kthread dealloc.
 So we can have the kthread (which we want to free later) hold on to the page we
 wanted to dealloc.  Likewise, when we would need a fresh kthread, we also need a
 page to use as the default stacktop.  So if we had a cached kthread, we then use
@@ -248,7 +248,7 @@ recall).  If it was a _M, things are a bit more complicated, since this should
 only happen if the kthread is for that process (and probably a bunch of other
 things - like they said it was okay to interrupt their vcore to finish the
 syscall).  Note - this might not be accurate anymore (see discussions on
-current_tf).
+current_ctx).
 
 To a certain extent, routine kmsgs don't seem like a nice fit, when we really
 want to be calling schedule().  Though if you think of it as the enactment of a
@@ -258,7 +258,7 @@ when it decided to send the kernel msg.  In the future, we could split this into
 having the handler make the kthread active, and have the scheduler called to
 decide where and when to run the kthread.
 
-Current_tf, Returning Twice, and Blocking
+Current_ctx, Returning Twice, and Blocking
 --------------------------------
 One of the reasons for decoupling kthreads from a vcore or the notion of a
 kernel thread per user processs/task is so that when the kernel blocks (on a
@@ -272,41 +272,41 @@ asynchronous kernel/syscall interface (though it's not limited to syscalls
   go through acrobatics in the code to prevent this.
 
 There are a couple of approaches I considered, and it involves the nature of
-"current_tf", and a brutal bug.  Current_tf is a pointer to the trapframe of the
-process that was interrupted/trapped, and is what user context ought to be
-running on this core if we return.  Current_tf is 'made' when the kernel saves
-the context at the top of the interrupt stack (aka 'stacktop').  Then the
-kernel's call path proceeds down the same stack.  This call path may get blocked
-in a kthread.  When we block, we want to restart the current_tf.  There is a
-coupling between the kthread's stack and the storage of current_tf (contents,
-not the pointer (which is in pcpui)).
+"current_ctx", and a brutal bug.  Current_ctx (formerly current_ctx) is a
+pointer to the trapframe of the process that was interrupted/trapped, and is
+what user context ought to be running on this core if we return.  Current_ctx is
+'made' when the kernel saves the context at the top of the interrupt stack (aka
+'stacktop').  Then the kernel's call path proceeds down the same stack.  This
+call path may get blocked in a kthread.  When we block, we want to restart the
+current_ctx.  There is a coupling between the kthread's stack and the storage of
+current_ctx (contents, not the pointer (which is in pcpui)).
 
 This coupling presents a problem when we are in userspace and get interrupted,
-and that interrupt wants to restart a kthread.  In this case, current_tf points
+and that interrupt wants to restart a kthread.  In this case, current_ctx points
 to the interrupt stack, but then we want to switch to the kthread's stack.  This
 is okay.  When that kthread wants to block again, it needs to switch back to
 another stack.  Up until this commit, it was jumping to the top of the old stack
-it was on, clobbering current_tf (took about 8-10 hours to figure this out).
-While we could just make sure to save space for current_tf, it doesn't solve the
-problem: namely that the current_tf concept is not bound to a specific kernel
-stack (kthread or otherwise).  We could have cases where more than one kthread
-starts up on a core and we end up freeing the page that holds current_tf (since
-it is a stack we no longer need).  We don't want to bother keeping stacks around
-just to hold the current_tf.  Part of the nature of this weird coupling is that
-a given kthread might or might not have the current_tf at the top of its stack.
-What a pain in the ass...
-
-The right answer is to decouple current_tf from kthread stacks.  There are two
-ways to do this.  In both ways, current_tf retains its role of the context the
+it was on, clobbering current_ctx (took about 8-10 hours to figure this out).
+While we could just make sure to save space for current_ctx, it doesn't solve
+the problem: namely that the current_ctx concept is not bound to a specific
+kernel stack (kthread or otherwise).  We could have cases where more than one
+kthread starts up on a core and we end up freeing the page that holds
+current_ctx (since it is a stack we no longer need).  We don't want to bother
+keeping stacks around just to hold the current_ctx.  Part of the nature of this
+weird coupling is that a given kthread might or might not have the current_ctx
+at the top of its stack.  What a pain in the ass...
+
+The right answer is to decouple current_ctx from kthread stacks.  There are two
+ways to do this.  In both ways, current_ctx retains its role of the context the
 kernel restarts (or saves) when it goes back to a process, and is independent of
 blocking kthreads.  SPOILER: solution 1 is not the one I picked
 
 1) All traps/interrupts come in on one stack per core.  That stack never changes
-(regardless of blocking), and current_tf is stored at the top.  Kthreads sort of
-'dispatch' / turn into threads from this event-like handling code.  This
+(regardless of blocking), and current_ctx is stored at the top.  Kthreads sort
+of 'dispatch' / turn into threads from this event-like handling code.  This
 actually sounds really cool!
 
-2) The contents of current_tf get stored in per-cpu-info (pcpui), thereby
+2) The contents of current_ctx get stored in per-cpu-info (pcpui), thereby
 clearly decoupling it from any execution context.  Any thread of execution can
 block without any special treatment (though interrupt handlers shouldn't do
 this).  We handle the "returning twice" problem at the point of return.
@@ -337,7 +337,7 @@ It is doable with syscalls because we have that clearly defined point
 fault handler?  It could block, and lots of other handlers could block too.  All
 of those would need to have a jump point (in trap.c).  We aren't even handling
 events anymore, we are immediately jumping to other stacks, using our "event
-handler" to hold current_tf and handle how we return to current_tf.  Don't
+handler" to hold current_ctx and handle how we return to current_ctx.  Don't
 forget about other code (like the boot code) that wants to block.  Simply put,
 option 1 creates a layer that is a pain to work with, cuts down on the
 flexibility of the kernel to block when it wants, and doesn't handle the issue
@@ -350,7 +350,7 @@ returns.  Now imagine a syscall that blocks.  Most of these calls are going to
 block on occasion, but not always (imagine the read was filled from the page
 cache).  These calls really need to handle both situations.  So in one instance,
 the call blocks.  Since we're async, we return to userspace early (pop the
-current_tf).  Now, when that kthread unblocks, its code is going to want to
+current_ctx).  Now, when that kthread unblocks, its code is going to want to
 finish and unroll its stack, then pop back to userspace.  This is the 'returning
 twice' problem.  Note that a *kthread* never returns twice.  This is what makes
 the idea of magic jumping points we can't return back across (and tying that to
@@ -359,23 +359,187 @@ how we block in the kernel) painful.
 The way I initially dealt with this was by always calling smp_idle(), and having
 smp_idle decide what to do.  I also used it as a place to dispatch batched
 syscalls, which is what made smp_idle() more attractive.  However, after a bit,
-I realized the real nature of returning twice: current_tf.  If we forget about
+I realized the real nature of returning twice: current_ctx.  If we forget about
 the batching for a second, all we really need to do is not return twice.  The
 best place to do that is at the place where we consider returning to userspace:
 proc_restartcore().  Instead of calling smp_idle() all the time (which was in
-essence a "you can now block" point), and checking for current_tf to return,
+essence a "you can now block" point), and checking for current_ctx to return,
 just check in restartcore to see if there is a tf to restart.  If there isn't,
 then we smp_idle().  And don't forget to handle the cases where we want to start
-and env_tf (which we ought to point current_tf to in proc_run()).
+and scp_ctx (which we ought to point current_ctx to in proc_run()).
 
 As a side note, we ought to use kmsgs for batched syscalls - it will help with
 preemption latencies.  At least for all but the first syscall (which can be
-called directly).  Instead of sending a retval via current_tf about how many
+called directly).  Instead of sending a retval via current_ctx about how many
 started, just put that info in the syscall struct's flags (which might help the
 remote syscall case - no need for a response message, though there are still a
 few differences (no failure model other than death)).
 
 Note that page faults will still be tricky, but at least now we don't have to
-worry about points of no return.  We just check if there is a current_tf to
+worry about points of no return.  We just check if there is a current_ctx to
 restart.  The tricky part is communicating that the PF was sorted when there
 wasn't an explicit syscall made.
+
+
+Aborting Syscalls (2013-11-22)
+-------------------------------
+On occasion, userspace would like to abort a syscall, specifically ones that
+are listening on sockets/conversations where no one will ever answer.
+
+We have limited support for aborting syscalls.  Kthreads that are in
+rendez_sleep() (common for anything in the 9ns chunk of the kernel, which
+includes any conversation listens) can be aborted.  They'll return with an
+error string to userspace.
+
+The easier part is the rules for kernel code to be abortable:
+- Restore your invariants with waserror() before calling rendez_sleep().
+- That's really it.
+So if you're holding a qlock, put your qunlock() code and any other unwinding
+(such as a kfree()) in a waserror() catch.  As it happens, it looks like plan9
+already did that (at least for the rendez in listen).  And, as always, you
+can't hold a spinlock when blocking, regardless of aborting calls or anything.
+
+I don't want arbitrary sleeps to be abortable.  For instance, if a kthread is
+waiting on an arbitrary semaphore/qlock, we won't allow an abort.  The
+reasoning is that the kthread will eventually acquire the qlock - we're not
+waiting on external sources to wake up.  That's not 100% true - a kthread
+could be blocked on a qlock, and the qlock holder could be abortable.  In the
+future, we could build some sort of "abort inheritance", usable by root or
+something (danger of aborting another process's kthread).  Alternatively, we
+could make qlocks abortable too, though that would require all qlocking code
+to be unwindable.
+
+The harder part to syscall aborting is safely waking a kthread.  There are
+several layers to go through from uthread or syscall down to the condition
+variable a kthread is sleeping on.  Given a uthread, find its syscall.  Given
+a syscall, find its kthread.  Given the kthread, find the CV.  And during all
+of these, syscalls complete concurrently, kthreads get repurposed for other
+syscalls, CVs could be freed (though that doesn't happen).  Syscalls are often
+on stacks, so when they complete, the memory is both gibberish and potentially
+in use.
+
+Ultimately, I decided on a system of "safe abort attempts", where it is
+harmless to be wrong with an attempt.  Instead of dealing with the races
+associated with memory freeing and syscalls completing, the aborts will only
+work if it is safe to work (using a lookup via pointer, and only dereferencing
+if the lookup succeeds).
+
+As it stands now, all abortable kthreads/sleepers/syscalls are on a per-proc
+list, and we can lookup by struct syscall*.  They are only on the list when
+they are abortable (the CV can be poked), and the invariant is that when they
+are on the list, they are in a state that can be safely aborted: the kthread
+is working on the syscall, it hasn't unwound, it is still in rendez_sleep(),
+the CV is safe, etc.  The details of this protection are sorted out with
+__reg_abortable_cv() and dereg_abortable_cv() (since it's really the condition
+variable that we're trying to find).  So from the kernel side, nothing bad can
+happen if you ask to abort an arbitrary struct syscall*.
+
+The actual abort takes the "write/signal, then wake" method.  The aborter
+tracks down the kthread via the lookup, the success of which guarantees the
+sleeper is in rendez_sleep() (or similar sleep paths), marks "SC_ABORT",
+(barriers), and attempts to wake the kthread (cv_broadcast, since we need to
+be sure we woke the right kthread).
+
+On the user side, we set an alarm to run an event handler that will cancel our
+syscall.  The alarm stuff is fairly standard (runs in vcore context).
+Userspace no longer has the concern of syscalls completing while they abort,
+since the kernel will only abort syscalls that are abortable.  However, it may
+have issues (in theory) with aborting future syscalls.  If the alarm goes off
+when the uthread is in another later syscall (which may happen to use the same
+struct syscall*), then we could accidentally abort the wrong call.  There's an
+aspect of time associated with the first abort alarm handler.  This is
+relatively easy to handle: just turn off the alarm before reusing that syscall
+struct for a syscall.  This relies on a property of the alarms: that when
+deregistering completes, the alarm handler will not be running concurrently.
+Incidentally, there is *another* minor trick here: the uthread when adjusting
+the alarm will issue a syscall, possibly reusing its old sysc*, but that will
+be *after* deregistering its original alarm: the point at which we could have
+potentially accidentally cancelled an arbitrary syscall.  Also note that the
+call to change the kernel alarm wouldn't actually block and become abortable,
+but regardless, we're safe.
+
+There are a couple downsides to the "safe abort attempts" approach.  We can
+only abort syscalls when they are at a certain point - if they aren't
+currently sleeping, the call will fail.  Technically, the abort could take
+effect later on in the life of a syscall (the aborter flags the kthread to
+abort concurrent with the kthread waking up naturally, and then the call
+aborts on the next rendez_sleep that needs to block).  Related to this
+limitation, userspace must keep attempting to cancel a syscall until it
+succeeds.  It may also be told an abort succeeded, even if the call actually
+completes (the aborter flags the kthread, the rendez wakes naturally, and the
+kthread never blocks again).  Ultimately, we can't "fire and forget" our abort
+attempt.  It's not a huge problem though, and is less of a problem than my
+older approaches that didn't have this problem.
+
+For instance, the original idea I had was for userspace to flag the syscall
+(flags |= SC_ABORT).  It could do this at any time.  Whenever the kthread was
+going to block in an abortable location (e.g. rendez_sleep()), it would see
+the flag and abort.  It might already be asleep, so we would also provide a
+syscall that would 'kick' the kthread responsible for some sysc*, to wake it
+up to see the flag and abort.  The first problem was writing to the sysc
+flags.  Unless we know the memory is actually the syscall we want, this could
+result in randomly writing to memory (such as a uthread's stack).  I ran into
+similar issues in the kernel: you can't touch a kthread struct unless you know
+it is the kthread you want.
+
+Once I started dealing with the syscall -> kthread mapping, it became clear
+I'd need a per-proc lookup service in the kernel, which acts as a way to lock
+a reference to the kthread.  I could solve the 'kthread memory safety' problem
+by looking up by reference, similar to how pid2proc works.  Analogously, by
+changing the interface for sys_abort_syscall() to be a "lookup" approach, I
+solve the struct syscall * memory problem.
+
+As a smaller note, I considered registering every kthread with the process
+right away (specifically, when we link the syscall to the kthread->sysc) for
+the sysc->kthread lookup service.  But this would get expensive, since every
+syscall pays the lookup tax (and we'd need to worry about scaling).  We want
+syscalls to be fast, but the infrequent aborts can be expensive.  The obvious
+change was to only save the abortable kthreads.  The tradeoff is that we can't
+flag syscalls for aborting unless they are in an abortable state.  This
+requires multiple pokes by userspace.  In theory, they would have to deal with
+that scenario anyways (in case they attempt to abort before we even register
+in the first place).
+
+As another side note, if userspace ever has a struct syscall allocator, for
+use in async (non-uthread stack-based) syscalls, we'll need to not reuse a
+syscall struct until after the cancel alarm has been disarmed.  Right now we
+do this by not having the uthread issue another syscall til after the disarm,
+since uthread stack-based syscalls are inherently bound to the uthread.  A
+simple solution would be to have a per-uthread syscall struct, which that
+uthread uses preferentially, and the sysc is only freed when the uthread is
+freed.  Not only would this scale better than accessing the sysc allocator for
+every syscall, but also there is no worry of reuse til the uthread disarms and
+exits.
+
+It is a userspace bug for a uthread to set the alarm and not unset it before
+either making a syscall or exiting.  The root issue of that potential bug is
+that someone (alarm handler) holds a pointer to a uthread, with the intent of
+cancelling its syscall, and we need to somehow take back that pointer (cancel
+the alarm) before reusing the syscall or freeing the uthread.  I considered
+not making the alarm guarantee that when the cancel returns, the handler isn't
+running concurrently.  We could handle the races in the alarm handler and in
+the cancel code, but it's an added hassle that isn't clearly needed.  This
+does mean we have to run the alarm handlers serially, while holding the alarm
+lock.  I'm fine with this, for now.  Perhaps if users want more concurrency,
+their handlers can spawn or wake up a uthread.
+
+It is also worth noting that many rendez_sleep() calls actually return right
+away.  This is common if some data is already in the queue (or whatever the
+condition is that we want to conditionally sleep on).  Since registration is a
+little bit heavier than just locking the CV, I use the classic "check, signal,
+check again" style, where we check cond, then register, and then check cond
+for real.  The initial check is the optimization, while the "signal, then
+check" is the true synchronization.  I use this style all over the place
+(check out the event delivery with concurrent vcore yields code).
+
+Because of this optimization, we have a slightly odd interface: __reg is
+called with the CV lock held, and dereg_ is not.  There are some lock ordering
+issues.  Without the optimization, we could simply make the order {list lock,
+CV lock}, so that the aborter can use the list lock to keep a kthread/cv alive
+(one of the struct cv_lookup_elm in the code, to be precise) while it
+cv_broadcasts.  However, the "check first" optimization would need to lock and
+unlock the CV a couple times, which seems excessive.  So we switch the lock
+order to {CV, list lock}, and the aborter doesn't hold the list lock while
+signalling the CV.  Instead, it keeps the cle alive with a flag that dereg_
+spins on.  This spinwait is why dereg can't hold the CV lock: it would create
+a circular dependency.