kern/thread: preliminary scheduling implementation

This change adds periodic timer interrupt reporting to the thread
module, basic thread selection, and context switching. It currently
only applies to the main processor. The x86/tcb module has been
drastically simplified as a side effect.

10 files changed, 277 insertions, 146 deletions

diff --git a/arch/x86/Makefrag.am b/arch/x86/Makefrag.am
index da335f51..cd668f3d 100644
--- a/arch/x86/Makefrag.am
+++ b/arch/x86/Makefrag.am
@@ -26,6 +26,7 @@ x86_FILES =                             \
 	arch/x86/machine/pit.h          \
 	arch/x86/machine/pmap.c         \
 	arch/x86/machine/pmap.h         \
+	arch/x86/machine/tcb_asm.S      \
 	arch/x86/machine/tcb.c          \
 	arch/x86/machine/tcb.h          \
 	arch/x86/machine/trap_asm.S     \
diff --git a/arch/x86/machine/boot.c b/arch/x86/machine/boot.c
index c9e7aead..3cc6e475 100644
--- a/arch/x86/machine/boot.c
+++ b/arch/x86/machine/boot.c
@@ -291,8 +291,6 @@ boot_ap_main(void)
     cpu_ap_setup();
     pmap_ap_bootstrap();
 
-    cpu_intr_enable();
-
     for (;;)
         cpu_idle();
 
diff --git a/arch/x86/machine/lapic.c b/arch/x86/machine/lapic.c
index c2a2b3aa..a7931cf8 100644
--- a/arch/x86/machine/lapic.c
+++ b/arch/x86/machine/lapic.c
@@ -22,6 +22,7 @@
 #include <kern/printk.h>
 #include <kern/stddef.h>
 #include <kern/stdint.h>
+#include <kern/thread.h>
 #include <machine/cpu.h>
 #include <machine/lapic.h>
 #include <machine/pmap.h>
@@ -320,6 +321,8 @@ void
 lapic_intr_timer(struct trap_frame *frame)
 {
     (void)frame;
+
+    thread_tick();
     lapic_eoi();
 }
 
diff --git a/arch/x86/machine/tcb.c b/arch/x86/machine/tcb.c
index ee1cb4fe..a15c6709 100644
--- a/arch/x86/machine/tcb.c
+++ b/arch/x86/machine/tcb.c
@@ -15,95 +15,22 @@
  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  */
 
-#include <kern/error.h>
-#include <kern/init.h>
-#include <kern/kmem.h>
 #include <kern/param.h>
-#include <kern/stddef.h>
-#include <kern/string.h>
-#include <kern/thread.h>
-#include <machine/cpu.h>
 #include <machine/tcb.h>
-#include <machine/trap.h>
 
-static struct kmem_cache tcb_cache;
-
-void __init
-tcb_setup(void)
-{
-    kmem_cache_init(&tcb_cache, "tcb", sizeof(struct tcb),
-                    0, NULL, NULL, NULL, 0);
-}
-
-#ifdef __LP64__
-
-static void
-tcb_init_stack(struct tcb *tcb, void *stack, const struct thread *thread)
-{
-    struct trap_frame *frame;
-
-    frame = (struct trap_frame *)(stack + STACK_SIZE) - 1;
-    memset(frame, 0, sizeof(*frame));
-    frame->rdi = (unsigned long)thread;
-    frame->rip = (unsigned long)thread_main;
-    frame->cs = CPU_GDT_SEL_CODE;
-    frame->rflags = CPU_EFL_IF | CPU_EFL_ONE;
-    frame->rsp = (unsigned long)(stack + STACK_SIZE);
-    frame->ss = CPU_GDT_SEL_DATA;
-    tcb->frame = frame;
-}
-
-#else /* __LP64__ */
-
-static void
-tcb_init_stack(struct tcb *tcb, void *stack, const struct thread *thread)
-{
-    struct trap_frame *frame;
-    const struct thread **arg;
-    const void **ret_addr;
-    void *ptr;
-    size_t size;
-
-    /* Fake a function call (return address and argument) */
-    ptr = stack + STACK_SIZE - (2 * sizeof(long));
-    ret_addr = ptr;
-    *ret_addr = 0;
-    arg = ptr + sizeof(long);
-    *arg = thread;
-
-    /* Exclude user space stack registers */
-    size = sizeof(*frame) - (2 * sizeof(long));
-    frame = ptr - size;
-    memset(frame, 0, size);
-    frame->ds = CPU_GDT_SEL_DATA;
-    frame->es = CPU_GDT_SEL_DATA;
-    frame->fs = CPU_GDT_SEL_CPU;
-    frame->gs = CPU_GDT_SEL_NULL;
-    frame->eip = (unsigned long)thread_main;
-    frame->cs = CPU_GDT_SEL_CODE;
-    frame->eflags = CPU_EFL_IF | CPU_EFL_ONE;
-    tcb->frame = frame;
-}
-
-#endif /* __LP64__ */
+/*
+ * Low level context switch function.
+ */
+void tcb_context_switch(struct tcb *prev, struct tcb *next);
 
-int
-tcb_create(struct tcb **tcbp, void *stack, const struct thread *thread)
+void
+tcb_init(struct tcb *tcb, void *stack, void (*fn)(void))
 {
-    struct tcb *tcb;
-
-    tcb = kmem_cache_alloc(&tcb_cache);
-
-    if (tcb == NULL)
-        return ERROR_NOMEM;
-
-    tcb_init_stack(tcb, stack, thread);
-    *tcbp = tcb;
-    return 0;
+    tcb->sp = (unsigned long)stack + STACK_SIZE;
+    tcb->ip = (unsigned long)fn;
 }
 
-void
-tcb_load(struct tcb *tcb)
+void tcb_switch(struct tcb *prev, struct tcb *next)
 {
-    trap_load(tcb->frame);
+    tcb_context_switch(prev, next);
 }
diff --git a/arch/x86/machine/tcb.h b/arch/x86/machine/tcb.h
index 96ac66a7..e18da15b 100644
--- a/arch/x86/machine/tcb.h
+++ b/arch/x86/machine/tcb.h
@@ -25,28 +25,20 @@
 #include <machine/trap.h>
 
 /*
- * Forward declaration.
- */
-struct thread;
-
-/*
  * Architecture specific thread data.
  */
 struct tcb {
-    struct trap_frame *frame;
+    unsigned long sp;
+    unsigned long ip;
 };
 
 /*
- * Set up the tcb module.
- */
-void tcb_setup(void);
-
-/*
- * Create a TCB.
+ * Initialize a TCB.
  *
- * Prepare the given stack for execution.
+ * Prepare the given stack for execution. The context is defined so that it
+ * will call fn() with interrupts disabled when loaded.
  */
-int tcb_create(struct tcb **tcbp, void *stack, const struct thread *thread);
+void tcb_init(struct tcb *tcb, void *stack, void (*fn)(void));
 
 /*
  * Load a TCB.
@@ -55,4 +47,11 @@ int tcb_create(struct tcb **tcbp, void *stack, const struct thread *thread);
  */
 void __noreturn tcb_load(struct tcb *tcb);
 
+/*
+ * Context switch.
+ *
+ * Called with interrupts disabled.
+ */
+void tcb_switch(struct tcb *prev, struct tcb *next);
+
 #endif /* _X86_TCB_H */
diff --git a/arch/x86/machine/tcb_asm.S b/arch/x86/machine/tcb_asm.S
new file mode 100644
index 00000000..0be93809
--- /dev/null
+++ b/arch/x86/machine/tcb_asm.S
@@ -0,0 +1,94 @@
+/*
+ * Copyright (c) 2012 Richard Braun.
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include <machine/asm.h>
+#include <machine/cpu.h>
+
+.text
+
+#ifdef __LP64__
+
+ASM_ENTRY(tcb_load)
+ movq 8(%rdi), %rax
+ movq (%rdi), %rsp
+ pushq %rax
+ pushq $CPU_EFL_ONE
+ popfq
+ ret
+ASM_END(tcb_load)
+
+ASM_ENTRY(tcb_context_switch)
+ pushfq
+ pushq %rbx
+ pushq %rbp
+ pushq %r12
+ pushq %r13
+ pushq %r14
+ pushq %r15
+ movq %rsp, (%rdi)
+ movq $1f, 8(%rdi)
+ movq (%rsi), %rsp
+ movq 8(%rsi), %rax
+ jmp *%rax
+
+1:
+ popq %r15
+ popq %r14
+ popq %r13
+ popq %r12
+ popq %rbp
+ popq %rbx
+ popfq
+ ret
+ASM_END(tcb_context_switch)
+
+#else /* __LP64__ */
+
+ASM_ENTRY(tcb_load)
+ movl 4(%esp), %eax
+ movl 4(%eax), %ecx
+ movl (%eax), %esp
+ pushl %ecx
+ pushl $CPU_EFL_ONE
+ popfl
+ ret
+ASM_END(tcb_load)
+
+ASM_ENTRY(tcb_context_switch)
+ movl 4(%esp), %eax
+ movl 8(%esp), %ecx
+ pushfl
+ pushl %ebx
+ pushl %ebp
+ pushl %edi
+ pushl %esi
+ movl %esp, (%eax)
+ movl $1f, 4(%eax)
+ movl (%ecx), %esp
+ movl 4(%ecx), %edx
+ jmp *%edx
+
+1:
+ popl %esi
+ popl %edi
+ popl %ebp
+ popl %ebx
+ popfl
+ ret
+ASM_END(tcb_context_switch)
+
+#endif /* __LP64__ */
diff --git a/arch/x86/machine/trap.c b/arch/x86/machine/trap.c
index 9810d0a6..27f35f5b 100644
--- a/arch/x86/machine/trap.c
+++ b/arch/x86/machine/trap.c
@@ -20,6 +20,7 @@
 #include <kern/macros.h>
 #include <kern/panic.h>
 #include <kern/printk.h>
+#include <kern/thread.h>
 #include <machine/cpu.h>
 #include <machine/lapic.h>
 #include <machine/pic.h>
@@ -146,6 +147,7 @@ trap_main(struct trap_frame *frame)
 {
     assert(frame->vector < ARRAY_SIZE(trap_handlers));
     trap_handlers[frame->vector].fn(frame);
+    thread_reschedule();
 }
 
 #ifdef __LP64__
diff --git a/kern/kernel.c b/kern/kernel.c
index 7c83d8d1..9e7f0435 100644
--- a/kern/kernel.c
+++ b/kern/kernel.c
@@ -27,10 +27,6 @@ kernel_setup(void *arg)
 {
     (void)arg;
 
-    cpu_mp_setup();
-
-    cpu_intr_enable();
-
     for (;;)
         cpu_idle();
 }
@@ -43,13 +39,14 @@ kernel_main(void)
 
     task_setup();
     thread_setup();
+    cpu_mp_setup();
 
     error = thread_create(&thread, "core", kernel_task, kernel_setup, NULL);
 
     if (error)
         panic("kernel: unable to create kernel thread");
 
-    thread_load(thread);
+    thread_run();
 
     /* Never reached */
 }
diff --git a/kern/thread.c b/kern/thread.c
index 24498b01..e8ac54e2 100644
--- a/kern/thread.c
+++ b/kern/thread.c
@@ -28,20 +28,13 @@
 #include <machine/tcb.h>
 
 /*
- * Make sure thread stacks are properly aligned.
- */
-#define THREAD_STACK_ALIGN 8
-
-/*
  * Per processor run queue.
  */
 struct thread_runq {
+    struct thread *current;
     struct list threads;
 } __aligned(CPU_L1_SIZE);
 
-/*
- * Per-processor run queues.
- */
 static struct thread_runq thread_runqs[MAX_CPUS];
 
 /*
@@ -53,31 +46,74 @@ static struct kmem_cache thread_stack_cache;
 static void __init
 thread_runq_init(struct thread_runq *runq)
 {
+    runq->current = NULL;
     list_init(&runq->threads);
 }
 
+static void
+thread_runq_enqueue(struct thread_runq *runq, struct thread *thread)
+{
+    list_insert_tail(&runq->threads, &thread->runq_node);
+}
+
+static struct thread *
+thread_runq_dequeue(struct thread_runq *runq)
+{
+    struct thread *thread;
+
+    if (list_empty(&runq->threads))
+        thread = NULL;
+    else {
+        thread = list_first_entry(&runq->threads, struct thread, runq_node);
+        list_remove(&thread->runq_node);
+    }
+
+    return thread;
+}
+
+static inline struct thread_runq *
+thread_runq_local(void)
+{
+    return &thread_runqs[cpu_id()];
+}
+
 void __init
 thread_setup(void)
 {
     size_t i;
 
-    tcb_setup();
-
     kmem_cache_init(&thread_cache, "thread", sizeof(struct thread),
-                    0, NULL, NULL, NULL, 0);
+                    CPU_L1_SIZE, NULL, NULL, NULL, 0);
     kmem_cache_init(&thread_stack_cache, "thread_stack", STACK_SIZE,
-                    THREAD_STACK_ALIGN, NULL, NULL, NULL, 0);
+                    CPU_L1_SIZE, NULL, NULL, NULL, 0);
 
     for (i = 0; i < ARRAY_SIZE(thread_runqs); i++)
         thread_runq_init(&thread_runqs[i]);
 }
 
+static void
+thread_main(void)
+{
+    struct thread_runq *runq;
+    struct thread *thread;
+
+    assert(!cpu_intr_enabled());
+
+    runq = thread_runq_local();
+    thread = runq->current;
+    cpu_intr_enable();
+
+    thread->fn(thread->arg);
+
+    for (;;)
+        cpu_idle();
+}
+
 int
 thread_create(struct thread **threadp, const char *name, struct task *task,
-              thread_run_fn_t run_fn, void *arg)
+              void (*fn)(void *), void *arg)
 {
     struct thread *thread;
-    struct tcb *tcb;
     void *stack;
     int error;
 
@@ -95,28 +131,25 @@ thread_create(struct thread **threadp, const char *name, struct task *task,
         goto error_stack;
     }
 
-    error = tcb_create(&tcb, stack, thread);
-
-    if (error)
-        goto error_tcb;
+    tcb_init(&thread->tcb, stack, thread_main);
 
     if (name == NULL)
         name = task->name;
 
-    /* XXX Assign all threads to the main processor for now */
-    thread->tcb = tcb;
-    list_insert_tail(&thread_runqs[0].threads, &thread->runq_node);
-    task_add_thread(task, thread);
+    thread->flags = 0;
     thread->task = task;
     thread->stack = stack;
     strlcpy(thread->name, name, sizeof(thread->name));
-    thread->run_fn = run_fn;
+    thread->fn = fn;
     thread->arg = arg;
+
+    /* XXX Assign all threads to the main processor for now */
+    thread_runq_enqueue(&thread_runqs[0], thread);
+    task_add_thread(task, thread);
+
     *threadp = thread;
     return 0;
 
-error_tcb:
-    kmem_cache_free(&thread_stack_cache, stack);
 error_stack:
     kmem_cache_free(&thread_cache, thread);
 error_thread:
@@ -124,16 +157,78 @@ error_thread:
 }
 
 void __init
-thread_load(struct thread *thread)
+thread_run(void)
 {
-    tcb_load(thread->tcb);
+    struct thread_runq *runq;
+    struct thread *thread;
+
+    runq = thread_runq_local();
+
+    thread = thread_runq_dequeue(runq);
+
+    /* TODO Idle thread */
+    assert(thread != NULL);
+
+    runq->current = thread;
+    tcb_load(&thread->tcb);
 }
 
 void
-thread_main(struct thread *thread)
+thread_schedule(void)
 {
-    thread->run_fn(thread->arg);
+    struct thread_runq *runq;
+    struct thread *prev, *next;
+    unsigned long flags;
 
-    for (;;)
-        cpu_idle();
+    flags = cpu_intr_save();
+
+    runq = thread_runq_local();
+    prev = runq->current;
+    thread_runq_enqueue(runq, prev);
+    next = thread_runq_dequeue(runq);
+
+    /* TODO Idle thread */
+    assert(next != NULL);
+
+    if (prev != next) {
+        runq->current = next;
+        tcb_switch(&prev->tcb, &next->tcb);
+    }
+
+    cpu_intr_restore(flags);
+}
+
+void
+thread_reschedule(void)
+{
+    struct thread_runq *runq;
+    struct thread *thread;
+
+    assert(!cpu_intr_enabled());
+
+    runq = thread_runq_local();
+    thread = runq->current;
+
+    /* TODO Idle thread */
+    assert(thread != NULL);
+
+    if (thread->flags & THREAD_RESCHEDULE)
+        thread_schedule();
+}
+
+void
+thread_tick(void)
+{
+    struct thread_runq *runq;
+    struct thread *thread;
+
+    assert(!cpu_intr_enabled());
+
+    runq = thread_runq_local();
+    thread = runq->current;
+
+    /* TODO Idle thread */
+    assert(thread != NULL);
+
+    thread->flags |= THREAD_RESCHEDULE;
 }
diff --git a/kern/thread.h b/kern/thread.h
index 15851ba3..52c0f813 100644
--- a/kern/thread.h
+++ b/kern/thread.h
@@ -29,21 +29,22 @@
 #define THREAD_NAME_SIZE 32
 
 /*
- * Type for thread entry point.
+ * Thread flags.
  */
-typedef void (*thread_run_fn_t)(void *);
+#define THREAD_RESCHEDULE   0x1 /* Thread marked for reschedule */
 
 /*
  * Thread structure.
  */
 struct thread {
-    struct tcb *tcb;
+    struct tcb tcb;
+    int flags;
     struct list runq_node;
     struct list task_node;
     struct task *task;
     void *stack;
     char name[THREAD_NAME_SIZE];
-    thread_run_fn_t run_fn;
+    void (*fn)(void *);
     void *arg;
 };
 
@@ -58,19 +59,33 @@ void thread_setup(void);
  * If the given name is null, the task name is used instead.
  */
 int thread_create(struct thread **threadp, const char *name, struct task *task,
-                  thread_run_fn_t run_fn, void *arg);
+                  void (*fn)(void *), void *arg);
 
 /*
- * Transform into a thread.
+ * Start running threads on the local processor.
  *
- * This function is used during system initialization by code in "boot context"
- * when creating the first thread on their processor.
+ * Interrupts are implicitely enabled when the first thread is dispatched.
  */
-void __noreturn thread_load(struct thread *thread);
+void __noreturn thread_run(void);
 
 /*
- * Thread entry point.
+ * Invoke the scheduler.
  */
-void __noreturn thread_main(struct thread *thread);
+void thread_schedule(void);
+
+/*
+ * Invoke the scheduler if the current thread is marked for reschedule.
+ *
+ * Called from interrupt context.
+ */
+void thread_reschedule(void);
+
+/*
+ * Report a periodic timer interrupt on the thread currently running on
+ * the local processor.
+ *
+ * Called from interrupt context.
+ */
+void thread_tick(void);
 
 #endif /* _KERN_THREAD_H */