Kernel message overhaul
authorBarret Rhoden <brho@cs.berkeley.edu>
Tue, 13 Nov 2012 22:31:12 +0000 (14:31 -0800)
committerBarret Rhoden <brho@cs.berkeley.edu>
Wed, 21 Nov 2012 23:41:17 +0000 (15:41 -0800)
We no longer run routines from the IRQ handler, and no longer run
immediates from PRKM().

The difference in the former is in cases where we are in userspace and
we receive an IPI to run kernel messages.  Previously, we handled the
routine messages in the IRQ handler.  Now we do nothing, and handle them
"on the way out" (in the proc_restartcore() / smp_idle() path).

The differences in the latter are that we simply wait til we actually
get the KMSG IPI to run the immediate handlers.  Note there is no
ordering guarantees between different KMSG classes.

Documentation/kernel_messages.txt
kern/include/trap.h
kern/src/process.c
kern/src/smp.c
kern/src/trap.c

index 692993d..df96c54 100644 (file)
 kernel_messages.txt
 Barret Rhoden
 2010-03-19
+Updated 2012-11-14
 
-This document explains the basic ideas behind our "kernel messages" and some of
-the arcane bits behind the implementation.  These were formerly called active
-messages, since they were an implementation of the low-level hardware messaging.
+This document explains the basic ideas behind our "kernel messages" (KMSGs) and
+some of the arcane bits behind the implementation.  These were formerly called
+active messages, since they were an implementation of the low-level hardware
+messaging.
 
 Overview:
 --------------------------------
-Our kernel messages are just work that is shipped remotely, delayed, or both.
-They currently consist of a PC and a few arguments.  Initially, they were meant
-to be a way to immediately execute code on another core (once interrupts are
-enabled), in the order in which the messages were sent.  This is insufficient
-(and wasn't what we wanted for the task, incidentally).  We simply want to do
-work on another core, but not necessarily instantly.  And not necessarily on
-another core.
+Our kernel messages are just work that is shipped remotely, delayed in time, or
+both.  They currently consist of a function pointer and a few arguments.  Kernel
+messages of a given type will be executed in order, with guaranteed delivery.
 
-Currently, there are two types, distinguished by which list they are sent to per
-core: immediate and routine.  Urgent messages will get executed as soon as
-possible (once interrupts are enabled).  Routine messages will be executed at
-convenient points in the kernel.  This includes when the kernel is about to pop
-back to userspace, or smp_idle()ing.  Routine messages are necessary when their
-function does not return, such as a __startcore, __death, or anything else that
-can ruin whatever the kernel was doing.  They should also be used if the work is
-not worth fully interrupting the kernel.  (An IPI will still be sent, but the
-work will be delayed)
-
-Kernel messages of a given type will be executed in order.  If immediate
-messages show up while processing a routine message, the immediate message will
-get processed next, at the latest.  Even if the routine function doesn't return,
-once interrupts are reenabled (like when popping to userspace), the
-__kernel_message() handler will fire again.
-
-Immediate kernel messages are executed in interrupt context.  Routine messages
-may technically be done in interrupt context (it's a nebulous term) because they
-are executed because of an interrupt handler, but from the kernel's perspective
-they are like executing in regular context (like when a process makes a syscall,
-aka real "process context").  This is because there are no concerns about the
-kernel holding locks or otherwise "interrupting" its own execution.  Routine
-messages are a little different than just trapping into the kernel, since the
-functions don't have to return and may result in clobbering the kernel stack.
-Also note that this behavior is dependent on where we call
-process_routine_kmsg().  Don't call it somewhere you need to return to.
+Initially, they were meant to be a way to immediately execute code on another
+core (once interrupts are enabled), in the order in which the messages were
+sent.  This is insufficient (and wasn't what we wanted for the task,
+incidentally).  We simply want to do work on another core, but not necessarily
+instantly.  And not necessarily on another core.
 
-History:
---------------------------------
-A bit of history: we used to use "immediate" messages (when all messages were
-immediate) for __death calls.  The idea was that we didn't care what the core
-was doing, since we didn't need to save state or anything.  I could see that
-there were going to be issues with preemption, since we would want to do some
-saving of what the core was doing (and what the kernel was doing on its behalf),
-so we prepared to deal with that.  However, even __death could break certain
-codes that were holding a reference (and hence a refcnt) for a process, which
-would prevent the process from ever being cleaned up.  It was a specific case of
-a job that the kernel needed to finish before executing the message.
+Currently, there are two types, distinguished by which list they are sent to per
+core: immediate and routine.   Routine messages are often referred to as RKMs.
+Immediate messages will get executed as soon as possible (once interrupts are
+enabled).  Routine messages will be executed at convenient points in the kernel.
+This includes when the kernel is about to pop back to userspace
+(proc_restartcore()), or smp_idle()ing.  Routine messages are necessary when
+their function does not return, such as a __launch_kthread.  They should also be
+used if the work is not worth fully interrupting the kernel.  (An IPI will still
+be sent, but the work will be delayed).  Finally, they should be used if their
+work could affect currently executing kernel code (like a syscall).
+
+For example, some older KMSGs such as __startcore used to not return and would
+pop directly into user space.  This complicted the KMSG code quite a bit.  While
+these functions now return, they still can't be immediate messages.  Proc
+management KMSGs change the cur_tf out from under a syscall, which can lead to a
+bunch of issues.
+
+Immediate kernel messages are executed in interrupt context, with interrupts
+disabled.  Routine messages are only executed from places in the code where the
+kernel doesn't care if the functions don't return or otherwise cause trouble.
+This means RKMs aren't run in interrupt context in the kernel (or if the kernel
+code itself traps).  We don't have a 'process context' like Linux does, instead
+its more of a 'default context'.  That's where RKMs run, and they run with IRQs
+disabled.
+
+RKMs can enable IRQs, or otherwise cause IRQs to be enabled.  __launch_kthread
+is a good example: it runs a kthread, which may have had IRQs enabled.
+
+With RKMs, there are no concerns about the kernel holding locks or otherwise
+"interrupting" its own execution.  Routine messages are a little different than
+just trapping into the kernel, since the functions don't have to return and may
+result in clobbering the kernel stack.  Also note that this behavior is
+dependent on where we call process_routine_kmsg().  Don't call it somewhere you
+need to return to.
 
 An example of an immediate message would be a TLB_shootdown.  Check current,
 flush if applicable, and return.  It doesn't harm the kernel at all.  Another
 example would be certain debug routines.
 
-Kernel messages are currently an arch-dependent thing, but this ought to change
-when sparc has IPI functions similar to x86.
+History:
+--------------------------------
+KMSGs have a long history tied to process management code.  The main issues were
+related to which KMSG functions return and which ones mess with local state (like
+clobbering cur_tf or the owning_proc).  Returning was a big deal because you
+can't just arbitrarily abandon a kernel context (locks or refcnts could be held,
+etc).  This is why immediates must return.  Likewise, there are certain
+invariants about what a core is doing that shouldn't be changed by an IRQ
+handler (which is what an immed message really is).  See all the old proc
+management commits if you want more info (check for changes to __startcore).
 
 Other Uses:
 --------------------------------
 Kernel messages will also be the basis for the alarm system.  All it is is
 expressing work that needs to be done.  That being said, the k_msg struct will
 probably receive a timestamp field, among other things.  Routine messages also
-will replace the old workqueue, which hasn't really been used in 10 months or
+will replace the old workqueue, which hasn't really been used in 40 months or
 so.
 
+Blocking:
+--------------------------------
+If a routine kernel message blocks (or has a chance to block), it must
+smp_idle() at the end.  If it were to return to PRKM(), it could be on a new
+core, due to kthread migration.  We might have a way to enforce this later.
+
 To Return or Not:
 --------------------------------
-Routine k_msgs do not have to return.  Urgent messages must.  The distinction is
-in how they are sent (send_kernel_message() will take a flag), so be careful.
-Technically, an immediate message could not return, but only if the kernel code
-that was interrupted was not holding any locks, mucking with any invariants, or
-otherwise doing work that needed to be done.  Those cases seem rather rare.
+Routine k_msgs do not have to return.  Immediate messages must.  The distinction
+is in how they are sent (send_kernel_message() will take a flag), so be careful.
 
 To retain some sort of sanity, the functions that do not return must adhere to
 some rules.  At some point they need to end in a place where they check routine
-messages or enable interrupts.  Returning to userspace will do this (interrupts
-are enabled).  __death will eventually call smp_idle(), which will check.  The
-idea behind this is that route messages will get processed once the kernel is
-able to (at a convenient place).
-
-Since some routine messages do not return by popping to userspace, we need to
-self-ipi to make sure the kernel regains control (this need might go away in the
-future).  Since we also want immediate messages to get processed before routine
-messages, and we want the system to be able to have a bunch of outstanding
-routine messages (though that is unlikely at this point), we briefly check
-for immed's inside process_routine_kmsg().  By only turning interrupts on for
-this means we avoid receiving excessive self_ipis for potentially not-returning
-routine messages.  Keep in mind that each one of those IPIs would be useless,
-since they will only run their functions when interrupting from userspace.
-
-Trickiness:
+messages or enable interrupts.  Simply calling smp_idle() will do this.  The
+idea behind this is that routine messages will get processed once the kernel is
+able to (at a convenient place). 
+
+Missing Routine Messages:
 --------------------------------
-If a function does not return, then the code might not check the list again, or
-send the EOI.  This is one reason why we send the EOI first, and insist that the
-__kernel_message() handler execute with interrupts disabled.  The routine
-messages do not need to have their interrupts disabled (if they are executed
-somewhere else).  If another IPI comes in, immediate messages will run, but
-other routine messages won't (they will get executed when the list is checked
-again).  However, enabling interrupts in the __kernel_message() handler can be
-problematic, depending on when the EOI is sent (nesting on the same code).
-
-The other reason we send_eoi() first is that we can only send it once per
-handler (not per message).  Otherwise, it can start acknowleding other interrupt
-vectors, which is bad.  We might move it in the while loop and protect it with a
-static check, but it doesn't seem worth it.  We still can't turn on interrupts,
-since the self_ipi could would fire and return while processing a routine
-function, negating the intent of the self_ipi.
-
-Since IPIs get "squashed" (my word, meaning if a core receives more than two at
-a time, future IPIs for a vector are ignored), and since functions might not
-return, there is the possibility of losing a message.  There can be more
-messages than IPIs (imagine three k_msgs, each that doesn't return).  To protect
-against this, if there is not an IPI pending (you can check on x86), and if
-there are messages in the routine list, then the code self_ipi's the current
-core.
-
-We don't need to check the immediate list, since we just checked it higher in
-the code (o/w, we wouldn't be executing routine messages).  If an immediate
-showed up since we executed the lapic_send_eoi(), an IPI will be on the way
-(messages are enqueued before sending the IPI).
-
-When we check the routine list, we don't need to lock.  All that macro does is
-check to see if head->item == 0 (and the list head won't get changed).  It's
-basically just a read, which gains no protection from a lock.
+It's important that the kernel always checks for routine messages before leaving
+the kernel, either to halt the core or to pop into userspace.  There is a race
+involved with messages getting posted after we check the list, but before we
+pop/halt.  In that time, we send an IPI.  This IPI will force us back into the
+kernel at some point in the code before process_routine_kmsg(), thus keeping us
+from missing the RKM.
+
+In the future, if we know the kernel code on a particular core is not attempting
+to halt/pop, then we could avoid sending this IPI.  This is the essence of the
+optimization in send_kernel_message() where we don't IPI ourselves.  A more
+formal/thorough way to do this would be useful, both to avoid bugs and to
+improve cross-core KMSG performance.
+
+IRQ Trickiness:
+--------------------------------
+You cannot enable interrupts in the handle_kmsg_ipi() handler, either in the
+code or in any immediate kmsg.  Since we send the EOI before running the handler
+(on x86), another IPI could cause us to reenter the handler, which would spin on
+the lock the previous context is holding (nested IRQ stacks).  Using irqsave
+locks is not sufficient, since they assume IRQs are not turned on in the middle
+of their operation (such as in the body of an immediate kmsg).
 
 Other Notes:
 --------------------------------
@@ -138,13 +127,6 @@ dynamically create the k_msgs (can pass them around easily, delay with them
 easily (alarms), and most importantly we can't deadlock by running out of room
 in a static buffer).
 
-When running our process_routine_kmsg()s, we could have made a userspace process
-that would get interrupted if there were any outstanding IPIs for routine
-messages.  We'd have to self_ipi, then switch to this process.  That kinda
-sucks, and would also mean that when we want to actually smp_idle, we'd have to
-be in userspace (and probably not cpu_halt()ing).  Making it possible to process
-the messages from within the kernel seemed much more flexible and better.
-
 Architecture Dependence:
 --------------------------------
 Some details will differ, based on architectural support.  For instance,
@@ -153,3 +135,6 @@ with maskable IPI vectors can use a different IPI for routine messages, and that
 interrupt can get masked whenever we enter the kernel (note, that means making
 every trap gate an interrupt gate), and we unmask that interrupt when we want to
 process routine messages.
+
+However, given the main part of kmsgs is arch-independent, I've consolidated all
+of it in one location until we need to have separate parts of the implementation.
index 7e13662..9edc7fd 100644 (file)
@@ -97,7 +97,7 @@ void kernel_msg_init(void);
 uint32_t send_kernel_message(uint32_t dst, amr_t pc, long arg0, long arg1,
                              long arg2, int type);
 void handle_kmsg_ipi(struct trapframe *tf, void *data);
-void process_routine_kmsg(struct trapframe *tf);
+void process_routine_kmsg(void);
 void print_kmsgs(uint32_t coreid);
 
 #endif /* ROS_KERN_TRAP_H */
index e49fa2e..f3883e8 100644 (file)
@@ -656,7 +656,7 @@ void proc_restartcore(void)
        /* Need ints disabled when we return from processing (race on missing
         * messages/IPIs) */
        disable_irq();
-       process_routine_kmsg(pcpui->cur_tf);
+       process_routine_kmsg();
        /* If there is no owning process, just idle, since we don't know what to do.
         * This could be because the process had been restarted a long time ago and
         * has since left the core, or due to a KMSG like __preempt or __death. */
index 853f0d1..d9feb93 100644 (file)
@@ -58,7 +58,7 @@ static void __attribute__((noinline, noreturn)) __smp_idle(void)
         * (and presumably about to execute a kmsg or fire up a vcore). */
        while (1) {
                disable_irq();
-               process_routine_kmsg(0);
+               process_routine_kmsg();
                try_run_proc();
                cpu_bored();            /* call out to the ksched */
                /* cpu_halt() atomically turns on interrupts and halts the core.
index 50c4a8c..330c772 100644 (file)
@@ -56,100 +56,82 @@ uint32_t send_kernel_message(uint32_t dst, amr_t pc, long arg0, long arg1,
        return 0;
 }
 
-/* Helper function.  Returns 0 if the list was empty. */
-static kernel_message_t *get_next_amsg(struct kernel_msg_list *list_head,
-                                       spinlock_t *list_lock)
-{
-       kernel_message_t *k_msg;
-       spin_lock_irqsave(list_lock);
-       k_msg = STAILQ_FIRST(list_head);
-       if (k_msg)
-               STAILQ_REMOVE_HEAD(list_head, link);
-       spin_unlock_irqsave(list_lock);
-       return k_msg;
-}
-
-/* Kernel message handler.  Extensive documentation is in
- * Documentation/kernel_messages.txt.
+/* Kernel message IPI/IRQ handler.
  *
- * In general: this processes immediate messages, then routine messages.
- * Routine messages might not return (__startcore, etc), so we need to be
- * careful about a few things.
+ * This processes immediate messages, and that's it (it used to handle routines
+ * too, if it came in from userspace).  Routine messages will get processed when
+ * the kernel has a chance (right before popping to userspace or in smp_idle
+ * before halting).
  *
  * Note that all of this happens from interrupt context, and interrupts are
- * currently disabled for this gate.  Interrupts need to be disabled so that the
- * self-ipi doesn't preempt the execution of this kernel message. */
+ * disabled. */
 void handle_kmsg_ipi(struct trapframe *tf, void *data)
 {
-
-       per_cpu_info_t *myinfo = &per_cpu_info[core_id()];
-       kernel_message_t msg_cp, *k_msg;
-
-       while (1) { // will break out when there are no more messages
-               /* Try to get an immediate message.  Exec and free it. */
-               k_msg = get_next_amsg(&myinfo->immed_amsgs, &myinfo->immed_amsg_lock);
-               if (k_msg) {
-                       assert(k_msg->pc);
-                       k_msg->pc(tf, k_msg->srcid, k_msg->arg0, k_msg->arg1, k_msg->arg2);
-                       kmem_cache_free(kernel_msg_cache, (void*)k_msg);
-               } else { // no immediate, might be a routine
-                       if (in_kernel(tf))
-                               return; // don't execute routine msgs if we were in the kernel
-                       k_msg = get_next_amsg(&myinfo->routine_amsgs,
-                                             &myinfo->routine_amsg_lock);
-                       if (!k_msg) // no routines either
-                               return;
-                       /* copy in, and then free, in case we don't return */
-                       msg_cp = *k_msg;
-                       kmem_cache_free(kernel_msg_cache, (void*)k_msg);
-                       /* Execute the kernel message */
-                       assert(msg_cp.pc);
-                       assert(msg_cp.dstid == core_id());
-                       /* TODO: when batching syscalls, this should be reread from cur_tf*/
-                       msg_cp.pc(tf, msg_cp.srcid, msg_cp.arg0, msg_cp.arg1, msg_cp.arg2);
-               }
+       struct per_cpu_info *pcpui = &per_cpu_info[core_id()];
+       struct kernel_message *kmsg_i, *temp;
+       assert(!irq_is_enabled());
+       /* Avoid locking if the list appears empty (lockless peak is okay) */
+       if (STAILQ_EMPTY(&pcpui->immed_amsgs))
+               return;
+       /* The lock serves as a cmb to force a re-read of the head of the list */
+       spin_lock(&pcpui->immed_amsg_lock);
+       STAILQ_FOREACH_SAFE(kmsg_i, &pcpui->immed_amsgs, link, temp) {
+               kmsg_i->pc(tf, kmsg_i->srcid, kmsg_i->arg0, kmsg_i->arg1, kmsg_i->arg2);
+               STAILQ_REMOVE(&pcpui->immed_amsgs, kmsg_i, kernel_message, link);
+               kmem_cache_free(kernel_msg_cache, (void*)kmsg_i);
        }
+       spin_unlock(&pcpui->immed_amsg_lock);
 }
 
-/* Runs any outstanding routine kernel messages from within the kernel.  Will
- * make sure immediates still run first (or when they arrive, if processing a
- * bunch of these messages).  This will disable interrupts, and restore them to
- * whatever state you left them. */
-void process_routine_kmsg(struct trapframe *tf)
+/* Helper function, gets the next routine KMSG (RKM).  Returns 0 if the list was
+ * empty. */
+static kernel_message_t *get_next_rkmsg(struct per_cpu_info *pcpui)
 {
-       per_cpu_info_t *myinfo = &per_cpu_info[core_id()];
-       kernel_message_t msg_cp, *k_msg;
-       int8_t irq_state = 0;
+       struct kernel_message *kmsg;
+       /* Avoid locking if the list appears empty (lockless peak is okay) */
+       if (STAILQ_EMPTY(&pcpui->routine_amsgs))
+               return 0;
+       /* The lock serves as a cmb to force a re-read of the head of the list */
+       spin_lock(&pcpui->routine_amsg_lock);
+       kmsg = STAILQ_FIRST(&pcpui->routine_amsgs);
+       if (kmsg)
+               STAILQ_REMOVE_HEAD(&pcpui->routine_amsgs, link);
+       spin_unlock(&pcpui->routine_amsg_lock);
+       return kmsg;
+}
 
-       disable_irqsave(&irq_state);
-       /* If we were told what our TF was, use that.  o/w, go with current_tf. */
-       tf = tf ? tf : current_tf;
-       while (1) {
-               /* normally, we want ints disabled, so we don't have an empty self-ipi
-                * for every routine message. (imagine a long list of routines).  But we
-                * do want immediates to run ahead of routines.  This enabling should
-                * work (might not in some shitty VMs).  Also note we can receive an
-                * extra self-ipi for routine messages before we turn off irqs again.
-                * Not a big deal, since we will process it right away. 
-                * TODO: consider calling __kernel_message() here. */
-               if (!STAILQ_EMPTY(&myinfo->immed_amsgs)) {
-                       enable_irq();
-                       cpu_relax();
-                       disable_irq();
-               }
-               k_msg = get_next_amsg(&myinfo->routine_amsgs,
-                                     &myinfo->routine_amsg_lock);
-               if (!k_msg) {
-                       enable_irqsave(&irq_state);
-                       return;
-               }
-               /* copy in, and then free, in case we don't return */
-               msg_cp = *k_msg;
-               kmem_cache_free(kernel_msg_cache, (void*)k_msg);
-               /* Execute the kernel message */
-               assert(msg_cp.pc);
-               assert(msg_cp.dstid == core_id());
-               msg_cp.pc(tf, msg_cp.srcid, msg_cp.arg0, msg_cp.arg1, msg_cp.arg2);
+/* Runs routine kernel messages.  This might not return.  In the past, this
+ * would also run immediate messages, but this is unnecessary.  Immediates will
+ * run whenever we reenable IRQs.  We could have some sort of ordering or
+ * guarantees between KMSG classes, but that's not particularly useful at this
+ * point.
+ *
+ * Note this runs from normal context, with interruptes disabled.  However, a
+ * particular RKM could enable interrupts - for instance __launch_kthread() will
+ * restore an old kthread that may have had IRQs on. */
+void process_routine_kmsg(void)
+{
+       uint32_t pcoreid = core_id();
+       struct per_cpu_info *pcpui = &per_cpu_info[pcoreid];
+       struct kernel_message msg_cp, *kmsg;
+
+       /* Important that callers have IRQs disabled.  When sending cross-core RKMs,
+        * the IPI is used to keep the core from going to sleep - even though RKMs
+        * aren't handled in the kmsg handler.  Check smp_idle() for more info. */
+       assert(!irq_is_enabled());
+       while ((kmsg = get_next_rkmsg(pcpui))) {
+               /* Copy in, and then free, in case we don't return */
+               msg_cp = *kmsg;
+               kmem_cache_free(kernel_msg_cache, (void*)kmsg);
+               assert(msg_cp.dstid == pcoreid);        /* caught a brutal bug with this */
+               /* Note we pass pcpui->cur_tf to all kmsgs.  I'm leaning towards
+                * dropping the TFs completely, but might find a debugging use for them
+                * later. */
+               msg_cp.pc(pcpui->cur_tf, msg_cp.srcid, msg_cp.arg0, msg_cp.arg1,
+                         msg_cp.arg2);
+               /* Some RKMs might turn on interrupts (perhaps in the future) and then
+                * return. */
+               disable_irq();
        }
 }