From 839034c1309bc331e4a44c8e0153f013a93ba5b5 Mon Sep 17 00:00:00 2001 From: Ian Moffett Date: Fri, 23 Feb 2024 17:38:36 -0500 Subject: kernel: Add initial scheduler implementation Signed-off-by: Ian Moffett --- sys/arch/amd64/amd64/local_intr.S | 19 ++-- sys/arch/amd64/amd64/switch.S | 50 ++++++++++ sys/include/sys/proc.h | 2 + sys/include/sys/sched.h | 4 + sys/include/sys/sched_state.h | 6 +- sys/kern/init_main.c | 5 +- sys/kern/kern_sched.c | 197 +++++++++++++++++++++++++++++++++----- 7 files changed, 246 insertions(+), 37 deletions(-) create mode 100644 sys/arch/amd64/amd64/switch.S diff --git a/sys/arch/amd64/amd64/local_intr.S b/sys/arch/amd64/amd64/local_intr.S index abfd9e0..b7b6345 100644 --- a/sys/arch/amd64/amd64/local_intr.S +++ b/sys/arch/amd64/amd64/local_intr.S @@ -27,14 +27,19 @@ * POSSIBILITY OF SUCH DAMAGE. */ +#include +#include +#include + +__KERNEL_META "$Hyra$: local_intr.S, Ian Marco Moffett, \ + Routines for handling Local Interrupts" + .text .globl lapic_tmr_isr lapic_tmr_isr: - lea stub_msg(%rip), %rdi - call kprintf - cli - hlt - -.section .rodata -stub_msg: .ascii "**LAPIC TIMER ISR IS A STUB; HALTING**\n\0" + push_trapframe $0 + mov %rsp, %rdi + call sched_context_switch + pop_trapframe + iretq diff --git a/sys/arch/amd64/amd64/switch.S b/sys/arch/amd64/amd64/switch.S new file mode 100644 index 0000000..156012e --- /dev/null +++ b/sys/arch/amd64/amd64/switch.S @@ -0,0 +1,50 @@ +/* + * Copyright (c) 2023-2024 Ian Marco Moffett and the Osmora Team. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of Hyra nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include +#include + +__KERNEL_META "$Hyra$: switch.S, Ian Marco Moffett, \ + Low level context switch code" + +.text +.globl __sched_switch_to + +/* void __sched_switch_to(struct trapframe *tf) */ +__sched_switch_to: + /* Sanity check */ + or %rdi, %rdi + jz fail + + /* Pop regs and switch */ + mov %rdi, %rsp + pop_trapframe + iretq +fail: + retq diff --git a/sys/include/sys/proc.h b/sys/include/sys/proc.h index 5106bf3..f45e4c6 100644 --- a/sys/include/sys/proc.h +++ b/sys/include/sys/proc.h @@ -33,6 +33,7 @@ #include #include #include +#include /* * A task running on the CPU e.g., a process or @@ -41,6 +42,7 @@ struct proc { pid_t pid; struct cpu_info *cpu; + struct trapframe *tf; TAILQ_ENTRY(proc) link; }; diff --git a/sys/include/sys/sched.h b/sys/include/sys/sched.h index 4fdf065..d803df0 100644 --- a/sys/include/sys/sched.h +++ b/sys/include/sys/sched.h @@ -35,6 +35,10 @@ #include #include #include +#include + +void sched_init(void); +void sched_context_switch(struct trapframe *tf); __noreturn void sched_init_processor(struct cpu_info *ci); diff --git a/sys/include/sys/sched_state.h b/sys/include/sys/sched_state.h index 03a55dd..52d6c56 100644 --- a/sys/include/sys/sched_state.h +++ b/sys/include/sys/sched_state.h @@ -30,15 +30,13 @@ #ifndef _SYS_SCHED_STATE_H_ #define _SYS_SCHED_STATE_H_ -#include -#include +#include /* * Scheduler state, per CPU. */ struct sched_state { - TAILQ_HEAD(, proc) queue; - size_t queue_nrun; /* Number of processes in the run queue */ + struct proc *td; /* Current_thread */ }; #endif /* !_SYS_SCHED_STATE_H_ */ diff --git a/sys/kern/init_main.c b/sys/kern/init_main.c index 2666b5e..6a60e2b 100644 --- a/sys/kern/init_main.c +++ b/sys/kern/init_main.c @@ -91,9 +91,12 @@ main(void) processor_init(); list_timers(); + sched_init(); ci = this_cpu(); - __TRY_CALL(ap_bootstrap, ci); + __TRY_CALL(ap_bootstrap, ci); sched_init_processor(ci); + + while (1); __builtin_unreachable(); } diff --git a/sys/kern/kern_sched.c b/sys/kern/kern_sched.c index 4f17ddf..81dd3a6 100644 --- a/sys/kern/kern_sched.c +++ b/sys/kern/kern_sched.c @@ -30,62 +30,209 @@ #include #include #include +#include #include #include -#include +#include #include +#include + +#define DEFAULT_TIMESLICE_USEC 100000000 /* - * This is the processor ready list, processors - * (cores) that have no task assigned live here. - * - * Assigning a task to a core is done by popping from - * this list. However, it must be done carefully and - * must be serialized. You *must* acquire ci_ready_lock - * before performing *any* operations on ci_ready_list!!! + * Thread ready queue - all threads ready to be + * scheduled should be added to this queue. */ -static TAILQ_HEAD(, cpu_info) ci_ready_list; -static struct spinlock ci_ready_lock = {0}; +static TAILQ_HEAD(, proc) td_queue; /* - * Push a processor into the ready list. + * Thread queue lock - all operations to `td_queue' + * must be done with this lock acquired. + */ +static struct spinlock tdq_lock = {0}; + +/* In sys///switch.S */ +void __sched_switch_to(struct trapframe *tf); + +static inline void +sched_oneshot(void) +{ + struct timer timer; + tmrr_status_t tmr_status; + + tmr_status = req_timer(TIMER_SCHED, &timer); + __assert(tmr_status == TMRR_SUCCESS); + + timer.oneshot_us(DEFAULT_TIMESLICE_USEC); +} + +/* + * Push a thread into the thread ready queue + * allowing it to be eventually dequeued + * and ran. */ static void -sched_enqueue_ci(struct cpu_info *ci) +sched_enqueue_td(struct proc *td) +{ + /* Sanity check */ + if (td == NULL) + return; + + spinlock_acquire(&tdq_lock); + + td->pid = TAILQ_NELEM(&td_queue); + TAILQ_INSERT_TAIL(&td_queue, td, link); + + spinlock_release(&tdq_lock); +} + +/* + * Dequeue the first thread in the thread ready + * queue. + */ +static struct proc * +sched_dequeue_td(void) { - spinlock_acquire(&ci_ready_lock); - TAILQ_INSERT_TAIL(&ci_ready_list, ci, link); - spinlock_release(&ci_ready_lock); + struct proc *td = NULL; + + spinlock_acquire(&tdq_lock); + + if (TAILQ_EMPTY(&td_queue)) { + goto done; + } + + td = TAILQ_FIRST(&td_queue); + TAILQ_REMOVE(&td_queue, td, link); +done: + spinlock_release(&tdq_lock); + return td; } + /* * Processor awaiting tasks to be assigned will be here spinning. */ __noreturn static void sched_enter(void) { + struct proc *td; + struct cpu_info *ci = this_cpu(); + struct sched_state *state = &ci->sched_state; + for (;;) { + if ((td = sched_dequeue_td()) != NULL) { + state->td = td; + sched_oneshot(); + __sched_switch_to(td->tf); + } + hint_spinwait(); } } +static struct proc * +sched_create_td(uintptr_t rip) +{ + const size_t STACK_SIZE = 0x100000; /* 1 MiB */ + struct proc *td; + void *stack; + struct trapframe *tf; + + tf = dynalloc(sizeof(struct trapframe)); + if (tf == NULL) { + return NULL; + } + + stack = dynalloc(STACK_SIZE); + if (stack == NULL) { + dynfree(tf); + return NULL; + } + + td = dynalloc(sizeof(struct proc)); + if (td == NULL) { + dynfree(tf); + dynfree(stack); + return NULL; + } + + memset(tf, 0, sizeof(struct trapframe)); + memset(stack, 0, STACK_SIZE); + + /* Setup process itself */ + td->pid = 0; /* Don't assign PID until enqueued */ + td->cpu = NULL; /* Not yet assigned a core */ + td->tf = tf; + + /* Setup trapframe */ + init_frame(tf, rip, (uintptr_t)stack + STACK_SIZE - 1); + return td; +} + /* - * Setup scheduler related things and enqueue AP. + * Thread context switch routine */ void -sched_init_processor(struct cpu_info *ci) +sched_context_switch(struct trapframe *tf) { - struct sched_state *sched_state = &ci->sched_state; - static bool is_init = true; + struct cpu_info *ci = this_cpu(); + struct sched_state *state = &ci->sched_state; + struct proc *td, *next_td; + + spinlock_acquire(&tdq_lock); + td = state->td; + + /* + * If we have no current thread or the queue is empty, + * preempting would be bad because there is nothing to + * switch to. And if we only have one thread, there is + * no point in preempting. + */ + if (td == NULL || TAILQ_NELEM(&td_queue) == 1) { + goto done; + } else if ((next_td = sched_dequeue_td()) == NULL) { + /* Empty */ + goto done; + } + - if (is_init) { - /* Setup ready list if first call */ - TAILQ_INIT(&ci_ready_list); - is_init = false; + /* Save our trapframe */ + memcpy(td->tf, tf, sizeof(struct trapframe)); + + if ((next_td = TAILQ_NEXT(td, link)) == NULL) { + /* We need to wrap to the first thread */ + next_td = TAILQ_FIRST(&td_queue); } - TAILQ_INIT(&sched_state->queue); - sched_enqueue_ci(ci); + /* Copy to stack */ + memcpy(tf, next_td->tf, sizeof(struct trapframe)); + state->td = next_td; +done: + spinlock_release(&tdq_lock); + sched_oneshot(); +} + +void +sched_init(void) +{ + TAILQ_INIT(&td_queue); + + /* + * TODO: Create init with sched_create_td() + * and enqueue with sched_enqueue_td() + */ + (void)sched_create_td; + (void)sched_enqueue_td; +} + +/* + * Setup scheduler related things and enqueue AP. + */ +void +sched_init_processor(struct cpu_info *ci) +{ + struct sched_state *sched_state = &ci->sched_state; + (void)sched_state; /* TODO */ sched_enter(); -- cgit v1.2.3