Kthread infrastructure
authorBarret Rhoden <brho@cs.berkeley.edu>
Thu, 21 Oct 2010 23:42:00 +0000 (16:42 -0700)
committerKevin Klues <klueska@cs.berkeley.edu>
Thu, 3 Nov 2011 00:35:55 +0000 (17:35 -0700)
Note this does not run on sparc yet - someone will need to write those
functions in k/a/sparc/trap.c.  Read the documentation for more info.

15 files changed:
Documentation/kthreads.txt [new file with mode: 0644]
kern/arch/i686/smp_boot.c
kern/arch/i686/trap.c
kern/arch/i686/trap.h
kern/arch/sparc/smp.c
kern/arch/sparc/trap.c
kern/arch/sparc/trap.h
kern/include/kthread.h [new file with mode: 0644]
kern/include/smp.h
kern/include/testing.h
kern/include/trap.h
kern/src/Makefrag
kern/src/init.c
kern/src/kthread.c [new file with mode: 0644]
kern/src/testing.c

diff --git a/Documentation/kthreads.txt b/Documentation/kthreads.txt
new file mode 100644 (file)
index 0000000..3e8f4fc
--- /dev/null
@@ -0,0 +1,232 @@
+kthreads.txt
+Barret Rhoden
+
+What Are They, And Why?
+-------------------------------
+Eventually a thread of execution in the kernel will want to block.  This means
+that the thread is unable to make forward progress and something else ought
+to run - the common case for this is when we wait on an IO operation.  This gets
+trickier when a function does not know if a function it calls will block or not.
+Sometimes they do, sometimes they don't.
+
+The critical feature is not that we want to save the registers, but that we want
+to preserve the stack and be able to use it independently of whatever else we do
+on that core in the interim time.  If we knew we would be done with and return
+from whatever_else() before we needed to continue the current thread of
+execution, we could simply call the function.  Instead, we want to be able to
+run the old context independently of what else is running (which may be a
+process). 
+
+We call this suspended context and the associated information a kthread, managed
+by a struct kthread.  It's the bare minimum needed for the kernel to stop and
+restart a thread of execution.  It holds the registers, stack pointer, PC,
+struct proc* if applicable, stacktop, and little else.  There is no silly_state
+/ floating point state, or anything else.  Its address space is determined from
+which process context (possibly none) that was running.
+
+We also get a few other benefits, such as the ability to pick and choose which
+kthreads to run where and when.  Users of kthreads should not assume that the
+core_id() stayed the same across function calls.  
+
+We can also use this infrastructure of other cases where we might want to start
+on a new stack.  One example is when we deal with low memory.  We may have to do
+a lot of work, but only need to do a little to allow the original thread (that
+might have failed on a page_alloc) to keep running, while we want the memory
+freer to keep running too (or later) from where it left off.  In essence, we
+want to fork, work, and yield or run on another core.  The kthread is just a
+means of suspending a call stack and a context for a little while.
+
+Side Note:
+-----------
+Right now, blocking a kthread is an explicit action.  Some function realizes it
+can't make progress (like waiting on a block device), so it sleeps on something
+(for now a semaphore), and gets woken up when it receives its signal.  This
+differs from processes, which can be stopped and suspended at any moment
+(pagefault is the classic example).  In the future, we could make kthreads be
+preemptable (timer interrupt goes off, and we choose to suspend a kthread), but
+even then kthreads still have the ability to turn off interrupts for tricky
+situations (like suspending the kthread).  The analog in the process code is
+disabling notifications, which dramatically complicates its functions (compare
+the save and pop functions for _ros_tf and _kernel_tf).  Furthermore, when a
+process disables notifications, it still doesn't mean it is running without
+interruptions (it looks like that to the vcore).  When the kernel disables
+interrupts, it really is running.
+
+What About Events?
+-------------------------------
+Why not just be event driven for all IO?  Why do we need these kernel threads?
+In short, IO isn't as simple as "I just want a block and when it's done, run a
+function."  While that is what the block device driver will do, the subsystems
+actually needing the IO are much simpler if they are threaded.  Consider the
+potentially numerous blocking IO calls involved in opening a file.  Having a
+continuation for each one of those points in the call graph seems like a real
+pain to code.  Perhaps I'm not seeing it, but if you're looking for a simple,
+light mechanism for keeping track of what work you need to do, just use a stack.
+Programming is much simpler, and it costs a page plus a small data structure.
+
+Note that this doesn't mean that all IO needs to use kthreads, just that some
+will really benefit from it.  I plan to make the "last part" of some IO calls
+more event driven.  Basically, it's all just a toolbox, and you should use what
+you need.
+
+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_tf().  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,
+we'll use this spare.  When restarting one, we'll free the old spare if it
+exists and put ours there.  One drawback is that we potentially waste a chunk of
+memory (1 page + a bit per core, worst case), but it is a nice, simple solution.
+Also, it will cut down on contention for free pages and the kthread_kcache,
+though this won't help with serious contention issues (which we'll deal with
+eventually).
+
+What To Run Next?
+-------------------------------
+When a kthread suspends, what do we run next?  And how do we know what to run
+next?  For now, we call smp_idle() - it is what you do when you have nothing
+else to do, or don't know what to do.  We could consider having sleep_on() take
+a function pointer, but when we start hopping stacks, passing that info gets
+tricky.  And we need to make a decision about which function to call quickly (in
+the code.  I don't trust the compiler much).  We can store the function pointer
+at the bottom of the future stack and extract it from there.  Or we could put it
+in per_cpu_info.  Or we can send ourselves a routine kernel message.
+
+Regardless of where we put it, we ought to call smp_idle() (or something
+similar) before calling it, since we need to make sure that whatever we call
+right after jumping stacks never returns.  It's more flexible to allow a
+function that returns for the func *, so we'll use smp_idle() as a level of
+indirection.
+
+Semaphore Stuff
+-------------------------------
+We use the semaphore (defined in kthread.h) for kthreads to sleep on and wait
+for a signal.  It is possible that the signal wins the race and beats the call
+to sleep_on().  The semaphore handles this by "returning false."  You'll notice
+that we don't actually call __down_sem(), but instead "build it in" to
+sleep_on().  I didn't want to deal with returning a bool (even if it was an
+inline), because I want to minimize the amount of stuff we do with potential
+stack variables (I don't trust the register variable).  As soon as we unlock,
+the kthread could be restarted (in theory), and it could start to clobber the
+stack in later function calls.
+
+So it is possible that we lose the semaphore race and shouldn't sleep.  We unwind the
+sleep prep work.  An alternative was to only do the prep work if we won the
+race, but that would mean we have to do a lot of work in that delicate period of
+"I'm on the queue but it is unlocked" - work that requires touching the stack.
+Or we could just hold the lock for a longer period of time, which I don't care
+to do.
+
+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_tf().
+
+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
+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
+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).
+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
+ought to be fixed.
+
+There is also some implications about PGSIZE stacks (specifically in the
+asserts, how we alloc only one page, etc).  The bootstacks are bigger than a
+page (for now), but in general we don't want to have giant stacks (and shouldn't
+need them - note linux runs with 4KB stacks).  In the future (long range, when
+we're 64 bit), I'd like to put all kernel stacks high in the address space, with
+guard pages after them.  This would require a certain "quiet migration" to the
+new locations for the bootstacks (though not a new page - just a different
+virtual address for the stacks (not their page-alloced KVA).  A bunch of minor
+things would need to change for that, so don't hold your breath.
+
+So what about stacktop?  It's just the top of the stack, but sometimes it is the
+stack we were on (when suspending the kthread), other times kthread->stacktop
+is just a scrap page's top.
+
+What's important when suspending is that the current stack is not
+used in future traps - that it doesn't get clobbered.  That's why we need to
+find a new stack and set it as the current stacktop.  We also need to 'save'
+the stack page of the old kthread - we don't want it to be freed, since we
+need it later. When starting a kthread, I don't particularly care about which
+stack is now the default stack.  The sleep_on() assumes it was the kthread's,
+so unless we always have a default one that is only used very briefly and
+never blocked on, (which requires a stack jump), we ought to just have a
+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_tf().  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
+the page that kthread was pointing to.  NOTE: the spare kthread struct is not
+holding the stack it was originally saved with.  Instead, it is saving the page
+of the stack that was running when that kthread was reactivated.  It's spare
+storage for both the struct and the page, but they aren't linked in any
+meaningful way (like it is the stack of the page).  That linkage is only true
+when a kthread is being used (like in a semaphore queue).
+
+Current and Process Contexts
+-------------------------------
+When a kthread is suspended, should the core stay in process context (if it was
+before)?  Short answer: yes.
+
+For vcore local calls (process context, trapped on the calling core), we're
+giving the core back, so we can avoid TLB shootdowns.  Though we do have to
+incref (which writes a cache line in the proc struct), since we are storing a
+reference to the proc (and will try to load its cr3 later).  While this sucks,
+keep in mind this is for a blocking IO call (where we couldn't find the page in
+any cache, etc).  It might be a scalability bottleneck, but it also might not
+matter in any real case.
+
+For async calls, it is less clear.  We might want to keep processing that
+process's syscalls, so it'd be easier to keep its cr3 loaded.  Though it's not
+as clear how we get from smp_idle() to a workable function and if it is useful
+to be in process context until we start processing those functions again.  Keep
+in mind that normally, smp_idle() shouldn't be in any process's context.  I'll
+probably write something later that abandons any context before halting to make
+sure processes die appropriately.  But there are still some unresolved issues
+that depend on what exactly we want to do.
+
+While it is tempting to say that we stay in process context if it was local, but
+not if it is async, there is an added complication.  The function calling
+sleep_on() doesn't care about whether it is on a process-allocated core or not.
+This is solvable by using per_cpu_info(), and will probably work its way into a
+future patch, regardless of whether or not we stay in process context for async
+calls.
+       
+As a final case, what will we do for processes that were interrupted by
+something that wants to block, but wasn't servicing a syscall?  We probably
+shouldn't have these (I don't have a good example of when we'd want it, and a
+bunch of reasons why we wouldn't), but if we do, then it might be okay anyway -
+the kthread is just holding that proc alive for a bit.
+
+Kmsgs and Kthreads
+-------------------------------
+Is there a way to mix kernel messages and kthreads?  What's the difference, and
+can one do the other?  A kthread is a suspended call-stack and context (thread),
+stopped in the middle of its work.  Kernel messages are about starting fresh -
+"hey core X, run this function."  A kmsg can very easily be a tool used to
+restart a kthread (either locally or on another core).  We do this in the test
+code, if you're curious how it could work.
+
+Note we use the semaphore to deal with races.  In test_kthreads(), we're
+actually using the kmsg to up the semaphore.  You just as easily could up the
+semaphore in one core (possibly in response to a kmsg, though more likely due to
+an interrupt), and then send the kthread to another core to restart via a kmsg.
+
+There's no reason you can't separate the __up_sem() and the running of the
+kthread - the semaphore just protects you from missing the signal.  Perhaps
+you'll want to rerun the kthread on the physical core it was suspended on!
+(cache locality, and it might be a legit option to allow processes to say it's
+okay to take their vcore).  Note this may require more bookkeeping in the struct
+kthread.
index 70bbc9a..143ca98 100644 (file)
@@ -305,6 +305,7 @@ void smp_percpu_init(void)
                per_cpu_info[coreid].gdt = (segdesc_t*)(*(uintptr_t*)my_stack_bot +
                                           sizeof(taskstate_t) + sizeof(pseudodesc_t));
        }
+       per_cpu_info[coreid].spare = 0;
        spinlock_init(&per_cpu_info[coreid].immed_amsg_lock);
        STAILQ_INIT(&per_cpu_info[coreid].immed_amsgs);
        spinlock_init(&per_cpu_info[coreid].routine_amsg_lock);
index d705af1..06571af 100644 (file)
@@ -83,18 +83,39 @@ void set_stack_top(uintptr_t stacktop)
        struct per_cpu_info *pcpu = &per_cpu_info[core_id()];
        /* No need to reload the task register, this takes effect immediately */
        pcpu->tss->ts_esp0 = stacktop;
+       /* Also need to make sure sysenters come in correctly */
+       write_msr(MSR_IA32_SYSENTER_ESP, stacktop);
 }
 
 /* Note the check implies we only are on a one page stack (or the first page) */
 uintptr_t get_stack_top(void)
 {
        uintptr_t stacktop = per_cpu_info[core_id()].tss->ts_esp0;
-       assert(stacktop == ROUNDUP(read_esp(), PGSIZE));
+       if (stacktop != ROUNDUP(read_esp(), PGSIZE))
+               panic("Bad stacktop: %08p esp one is %08p\n", stacktop,
+                     ROUNDUP(read_esp(), PGSIZE));
        return stacktop;
 }
 
-void
-idt_init(void)
+/* Starts running the current TF, just using ret. */
+void pop_kernel_tf(struct trapframe *tf)
+{
+       asm volatile ("movl %1,%%esp;           " /* move to future stack */
+                     "pushl %2;                " /* push cs */
+                     "movl %0,%%esp;           " /* move to TF */
+                     "addl $0x20,%%esp;        " /* move to tf_gs slot */
+                     "movl %1,(%%esp);         " /* write future esp */
+                     "subl $0x20,%%esp;        " /* move back to tf start */
+                     "popal;                   " /* restore regs */
+                     "popl %%esp;              " /* set stack ptr */
+                     "subl $0x4,%%esp;         " /* jump down past CS */
+                     "ret                      " /* return to the EIP */
+                     :
+                     : "g"(tf), "r"(tf->tf_esp), "r"(tf->tf_eip) : "memory");
+       panic("ret failed");                            /* mostly to placate your mom */
+}
+
+void idt_init(void)
 {
        extern segdesc_t (RO gdt)[];
 
index e422040..de60f35 100644 (file)
@@ -82,9 +82,31 @@ static inline void restore_fp_state(struct ancillary_state *silly)
        asm volatile("fxrstor %0" : : "m"(*silly));
 }
 
-static inline void set_stack_pointer(uintptr_t sp)
+static inline void __attribute__((always_inline))
+set_stack_pointer(uintptr_t sp)
 {
-       asm volatile("mov %0,%%esp" : : "r"(sp));
+       asm volatile("mov %0,%%esp" : : "r"(sp) : "memory","esp");
+}
+
+/* Save's the current kernel context into tf, setting the PC to the end of this
+ * function.  Note the kernel doesn't need to save a lot. */
+static inline void save_kernel_tf(struct trapframe *tf)
+{
+       /* Save the regs and the future esp. */
+       asm volatile("movl %%esp,(%0);       " /* save esp in it's slot*/
+                    "pushl %%eax;           " /* temp save eax */
+                    "leal 1f,%%eax;         " /* get future eip */
+                    "movl %%eax,(%1);       " /* store future eip */
+                    "popl %%eax;            " /* restore eax */
+                    "movl %2,%%esp;         " /* move to the beginning of the tf */
+                    "addl $0x20,%%esp;      " /* move to after the push_regs */
+                    "pushal;                " /* save regs */
+                    "addl $0x44,%%esp;      " /* move to esp slot */
+                    "popl %%esp;            " /* restore esp */
+                    "1:                     " /* where this tf will restart */
+                    : 
+                    : "g"(&tf->tf_esp), "g"(&tf->tf_eip), "g"(tf)
+                    : "eax", "memory", "cc");
 }
 
 #endif /* !__ASSEMBLER__ */
index 21c33e8..6fd880b 100644 (file)
@@ -153,6 +153,7 @@ int smp_call_wait(handler_wrapper_t* wrapper)
 void smp_percpu_init(void)
 {
        uint32_t coreid = core_id();
+       per_cpu_info[coreid].spare = 0;
        spinlock_init(&per_cpu_info[coreid].immed_amsg_lock);
        STAILQ_INIT(&per_cpu_info[coreid].immed_amsgs);
        spinlock_init(&per_cpu_info[coreid].routine_amsg_lock);
index 445d3df..8e8bb47 100644 (file)
@@ -98,6 +98,13 @@ uintptr_t get_stack_top(void)
        return stacktop;
 }
 
+/* Starts running the current TF. */
+void pop_kernel_tf(struct trapframe *tf)
+{
+       /* TODO! also do save_kernel_tf() in kern/arch/sparc/trap.h */
+       panic("Not implemented.  =(");
+}
+
 void
 idt_init(void)
 {
index 2b0163d..ac98bcc 100644 (file)
@@ -32,12 +32,20 @@ static inline bool in_kernel(struct trapframe *tf)
 }
 
 /* Needs to leave room for a trapframe at the top of the stack. */
-static inline void set_stack_pointer(uintptr_t sp)
+static inline void __attribute__((always_inline))
+set_stack_pointer(uintptr_t sp)
 {
        sp = sp - SIZEOF_TRAPFRAME_T;
        asm volatile("mov %0,%%sp" : : "r"(sp));
 }
 
+/* Save's the current kernel context into tf, setting the PC to the end of this
+ * function. */
+static inline void save_kernel_tf(struct trapframe *tf)
+{
+       /* TODO: save the registers, stack pointer, and have the PC pt to the end */
+}
+
 #endif /* !__ASSEMBLER__ */
 
 #endif /* !ROS_INC_ARCH_TRAP_H */
diff --git a/kern/include/kthread.h b/kern/include/kthread.h
new file mode 100644 (file)
index 0000000..6128317
--- /dev/null
@@ -0,0 +1,91 @@
+/* Copyright (c) 2010 The Regents of the University of California
+ * Barret Rhoden <brho@cs.berkeley.edu>
+ * See LICENSE for details.
+ *
+ * Kernel threading.  These are for blocking within the kernel for whatever
+ * reason, usually during blocking IO operations.  Check out
+ * Documentation/kthreads.txt for more info than you care about. */
+
+#ifndef ROS_KERN_KTHREAD_H
+#define ROS_KERN_KTHREAD_H
+
+#include <ros/common.h>
+#include <trap.h>
+#include <sys/queue.h>
+#include <atomic.h>
+
+struct proc;
+struct kthread;
+TAILQ_HEAD(kthread_tailq, kthread);
+
+/* This captures the essence of a kernel context that we want to suspend.  When
+ * a kthread is running, we make sure its stacktop is the default kernel stack,
+ * meaning it will receive the interrupts from userspace. */
+struct kthread {
+       struct trapframe                        context;
+       uintptr_t                                       stacktop;
+       struct proc                                     *proc;
+       struct trapframe                        *proc_tf;                       /* TODO: change this? */
+       /* TODO: put in the sys_return, if we decide to keep this shit */
+       TAILQ_ENTRY(kthread)            link;
+       /* ID, other shit, etc */
+};
+
+/* Semaphore for kthreads to sleep on.  0 or less means you need to sleep */
+struct semaphore {
+       struct kthread_tailq            waiters;
+       int                                             nr_signals;
+       spinlock_t                                      lock;
+};
+
+/* This doesn't have to be inline, but it doesn't matter for now */
+static inline void init_sem(struct semaphore *sem, int signals)
+{
+       TAILQ_INIT(&sem->waiters);
+       sem->nr_signals = signals;
+       spinlock_init(&sem->lock);
+}
+
+/* Down and up for the semaphore are a little more low-level than usual, since
+ * they are meant to be called by functions that manage the sleeping of a
+ * kthread.  For instance, __down_sem() always returns right away.  For now,
+ * these are just examples, since the actual usage will probably need lower
+ * access. */
+
+/* Down : decrement, if it was 0 or less, we need to sleep.  Returns false if
+ * the kthread did not need to sleep (the signal was already there). */
+static inline bool __down_sem(struct semaphore *sem, struct kthread *kthread)
+{
+       bool retval = FALSE;
+       spin_lock(&sem->lock);
+       if (sem->nr_signals-- <= 0) {
+               /* Need to sleep */
+               retval = TRUE;
+               TAILQ_INSERT_TAIL(&sem->waiters, kthread, link);
+       }
+       spin_unlock(&sem->lock);
+       return retval;
+}
+
+/* Ups the semaphore.  If it was < 0, we need to wake up someone, which is the
+ * return value. */
+static inline struct kthread *__up_sem(struct semaphore *sem)
+{
+       struct kthread *kthread = 0;
+       spin_lock(&sem->lock);
+       if (sem->nr_signals++ < 0) {
+               /* could do something with 'priority' here */
+               kthread = TAILQ_FIRST(&sem->waiters);
+               TAILQ_REMOVE(&sem->waiters, kthread, link);
+       } else {
+               assert(TAILQ_EMPTY(&sem->waiters));
+       }
+       spin_unlock(&sem->lock);
+       return kthread;
+}
+
+void kthread_init(void);
+void sleep_on(struct semaphore *sem);
+void restart_kthread(struct kthread *kthread);
+
+#endif /* ROS_KERN_KTHREAD_H */
index 8e41f79..c8b620a 100644 (file)
@@ -27,6 +27,7 @@ struct per_cpu_info {
        struct proc *cur_proc;
        trapframe_t *cur_tf;
        struct sys_return cur_ret;
+       struct kthread *spare;          /* useful when restarting */
 
 #ifdef __SHARC__
        // held spin-locks. this will have to go elsewhere if multiple kernel
index 3da5092..51d3856 100644 (file)
@@ -31,6 +31,7 @@ void test_bcq(void);
 void test_vm_regions(void);
 void test_radix_tree(void);
 void test_random_fs(void);
+void test_kthreads(void);
 
 struct trapframe_t;
 
index 05ca4d2..0eaf036 100644 (file)
@@ -47,6 +47,11 @@ void restore_fp_state(struct ancillary_state *silly);
 void set_stack_top(uintptr_t stacktop);
 uintptr_t get_stack_top(void);
 
+/* It's important that this is inline and that tf is not a stack variable */
+static inline void save_kernel_tf(struct trapframe *tf)
+                   __attribute__((always_inline));
+void pop_kernel_tf(struct trapframe *tf) __attribute__((noreturn));
+
 /* Kernel messages.  Each arch implements them in their own way.  Both should be
  * guaranteeing in-order delivery.  Kept here in trap.h, since sparc is using
  * trap.h for KMs.  Eventually, both arches will use the same implementation.
index 2041660..2cd1e46 100644 (file)
@@ -48,6 +48,7 @@ KERN_SRCFILES := $(KERN_ARCH_SRCFILES) \
                  $(KERN_SRC_DIR)/ext2fs.c \
                  $(KERN_SRC_DIR)/testing.c \
                  $(KERN_SRC_DIR)/pagemap.c \
+                 $(KERN_SRC_DIR)/kthread.c \
                  $(KERN_SRC_DIR)/arsc.c
 
 # Only build files if they exist.
index 6167d53..b3b9a33 100644 (file)
@@ -41,6 +41,7 @@
 #include <devfs.h>
 #include <blockdev.h>
 #include <ext2fs.h>
+#include <kthread.h>
 
 // zra: flag for Ivy
 int booting = 1;
@@ -80,6 +81,7 @@ void kernel_init(multiboot_info_t *mboot_info)
        radix_init();
        cache_color_alloc_init();       // Inits data structs
        colored_page_alloc_init();      // Allocates colors for agnostic processes
+       kthread_init();                                 /* might need to tweak when this happens */
        vmr_init();
        file_init();
        page_check();
diff --git a/kern/src/kthread.c b/kern/src/kthread.c
new file mode 100644 (file)
index 0000000..2d0f2c5
--- /dev/null
@@ -0,0 +1,142 @@
+/* Copyright (c) 2010 The Regents of the University of California
+ * Barret Rhoden <brho@cs.berkeley.edu>
+ * See LICENSE for details.
+ *
+ * Kernel threading.  These are for blocking within the kernel for whatever
+ * reason, usually during blocking IO operations. */
+
+#include <kthread.h>
+#include <slab.h>
+#include <page_alloc.h>
+#include <pmap.h>
+#include <smp.h>
+
+struct kmem_cache *kthread_kcache;
+
+void kthread_init(void)
+{
+       kthread_kcache = kmem_cache_create("kthread", sizeof(struct kthread),
+                                          __alignof__(struct kthread), 0, 0, 0);
+}
+
+/* This downs the semaphore and suspends the current kernel context on its
+ * waitqueue if there are no pending signals.  Note that the case where the
+ * signal is already there is not optimized. */
+void sleep_on(struct semaphore *sem)
+{
+       volatile bool blocking = TRUE;  /* signal to short circuit when restarting*/
+       struct kthread *kthread;
+       struct page *page;                              /* assumption here that stacks are PGSIZE */
+       register uintptr_t new_stacktop;
+       int8_t irq_state = 0;
+       struct per_cpu_info *pcpui = &per_cpu_info[core_id()];
+
+       /* interrups would be messy here */
+       disable_irqsave(&irq_state);
+       /* Try to get the spare first.  If there is one, we'll use it (o/w, we'll
+        * get a fresh kthread.  Why we need this is more clear when we try to
+        * restart kthreads.  Having them also ought to cut down on contention.
+        * Note we do this with interrupts disabled (which protects us from
+        * concurrent modifications). */
+       if (pcpui->spare) {
+               kthread = pcpui->spare;
+               /* we're using the spare, so we use the page the spare held */
+               new_stacktop = kthread->stacktop;
+               pcpui->spare = 0;
+       } else {
+               kthread = kmem_cache_alloc(kthread_kcache, 0);
+               assert(kthread);
+               assert(!kpage_alloc(&page));    /* decref'd when the kthread is freed */
+               new_stacktop = (uintptr_t)page2kva(page) + PGSIZE;
+       }
+       /* This is the stacktop we are currently on and wish to save */
+       kthread->stacktop = get_stack_top();
+       /* Set the core's new default stack */
+       set_stack_top(new_stacktop);
+       /* The kthread needs to stay in the process context (if there is one), but
+        * we want the core (which could be a vcore) to stay in the context too.  If
+        * we want to leave, we'll need to do that in smp_idle() or elsewhere in the
+        * code. */
+       kthread->proc = current;
+       kthread->proc_tf = current_tf;
+       if (kthread->proc)
+               kref_get(&kthread->proc->kref, 1);
+       /* Save the context, toggle blocking for the reactivation */
+       save_kernel_tf(&kthread->context);
+       if (!blocking)
+               goto block_return_path;
+       blocking = FALSE;                                       /* for when it starts back up */
+       /* Down the semaphore.  We need this to be inline.  If we're sleeping, once
+        * we unlock the kthread could be started up again and can return and start
+        * trashing this function's stack, hence the weird control flow. */
+       spin_lock(&sem->lock);  /* no need for irqsave, since we disabled ints */
+       if (sem->nr_signals-- <= 0)
+               TAILQ_INSERT_TAIL(&sem->waiters, kthread, link);
+       else                                                            /* we didn't sleep */
+               goto unwind_sleep_prep;
+       spin_unlock(&sem->lock);
+       /* Switch to the core's default stack.  After this, don't use local
+        * variables.  TODO: we shouldn't be using new_stacktop either, can't always
+        * trust the register keyword (AFAIK). */
+       set_stack_pointer(new_stacktop);
+       smp_idle();
+       /* smp_idle never returns */
+       assert(0);
+unwind_sleep_prep:
+       /* We get here if we should not sleep on sem (the signal beat the sleep).
+        * Note we are not optimizing for cases where the signal won. */
+       spin_unlock(&sem->lock);
+       printk("Didn't sleep, unwinding...\n");
+       /* Restore the core's current and default stacktop */
+       current = kthread->proc;                        /* arguably unnecessary */
+       if (kthread->proc)
+               kref_put(&kthread->proc->kref);
+       set_stack_top(kthread->stacktop);
+       /* Save the allocs as the spare */
+       assert(!pcpui->spare);
+       pcpui->spare = kthread;
+       /* save the "freshly alloc'd" stack/page, not the one we came in on */
+       kthread->stacktop = new_stacktop;
+block_return_path:
+       printd("Returning from being 'blocked'!\n");
+       enable_irqsave(&irq_state);
+       return;
+}
+
+/* Starts kthread on the calling core.  This does not return, and will handle
+ * the details of cleaning up whatever is currently running (freeing its stack,
+ * etc). */
+void restart_kthread(struct kthread *kthread)
+{
+       struct per_cpu_info *pcpui = &per_cpu_info[core_id()];
+       uintptr_t current_stacktop;
+       /* Avoid messy complications.  The kthread will enable_irqsave() when it
+        * comes back up. */
+       disable_irq();
+       /* Free any spare, since we need ours to become the spare (since we can't
+        * free our current kthread *before* popping it, nor can we free the current
+        * stack until we pop to the kthread's stack). */
+       if (pcpui->spare) {
+               page_decref(kva2page((void*)kthread->stacktop - PGSIZE));
+               kmem_cache_free(kthread_kcache, pcpui->spare);
+       }
+       current_stacktop = get_stack_top();
+       /* When a kthread runs, its stack is the default kernel stack */
+       set_stack_top(kthread->stacktop);
+       /* Set the spare stuff (current kthread, current (not kthread) stacktop) */
+       pcpui->spare = kthread;
+       kthread->stacktop = current_stacktop;
+       /* We need to load the new cr3 if we want another new (or no) process */
+       if (current != kthread->proc) {
+               if (kthread->proc)
+                       lcr3(kthread->proc->env_cr3);
+               else
+                       lcr3(boot_cr3);
+       }
+       /* If there's a proc current already, we'll lose that ref no matter what. */
+       if (current)
+               kref_put(&current->kref);
+       current = kthread->proc;
+       /* Finally, restart our thread */
+       pop_kernel_tf(&kthread->context);
+}
index 053555d..92ff26b 100644 (file)
@@ -32,6 +32,7 @@
 #include <hashtable.h>
 #include <radix.h>
 #include <monitor.h>
+#include <kthread.h>
 
 #define l1 (available_caches.l1)
 #define l2 (available_caches.l2)
@@ -1184,3 +1185,44 @@ void test_random_fs(void)
                printk("Symlink lookup failed (it should): %d (-40)\n", retval);
        path_release(nd);
 }
+
+/* simple test - start one, do something else, and resume it.  For lack of a
+ * better infrastructure, we send ourselves a kmsg to run the kthread, which
+ * we'll handle in smp_idle (which you may have to manually call).  Note this
+ * doesn't test things like memory being leaked, or dealing with processes. */
+void test_kthreads(void)
+{
+       /* Kernel message to restart our kthread */
+       void test_up_sem(struct trapframe *tf, uint32_t srcid, void *a0, void *a1,
+                        void *a2)
+       {
+               struct semaphore *sem = (struct semaphore*)a0;
+               struct kthread *kthread;
+               printk("[kmsg] Upping the sem to start the kthread, stacktop is %08p\n",
+                      get_stack_top());
+               kthread = __up_sem(sem);
+               if (!kthread) {
+                       printk("[kmsg] Crap, the sem didn't have a kthread waiting!\n");
+                       return;
+               }
+               printk("[kmsg] Restarting the kthread...\n");
+               restart_kthread(kthread);
+               panic("[kmsg] Damnit...");
+       }
+       struct semaphore sem;
+       init_sem(&sem, 1);              /* set to 1 to test the unwind */
+       printk("We're a kthread!  Stacktop is %08p.  Testing suspend, etc...\n",
+              get_stack_top());
+       /* So we have something that will wake us up.  Routine messages won't get
+        * serviced in the kernel right away. */
+       send_kernel_message(core_id(), test_up_sem, (void*)&sem, 0, 0,
+                           KMSG_ROUTINE);
+       /* Actually block (or try to) */
+       /* This one shouldn't block - but will test the unwind (if 1 above) */
+       printk("About to sleep, but should unwind (signal beat us)\n");
+       sleep_on(&sem);
+       /* This one is for real, yo.  Run and tell that. */
+       printk("About to sleep for real\n");
+       sleep_on(&sem);
+       printk("Kthread restarted!, Stacktop is %08p.\n", get_stack_top());
+}