diff options
author | Jakob Odersky <jodersky@gmail.com> | 2014-03-17 15:53:45 +0100 |
---|---|---|
committer | Jakob Odersky <jodersky@gmail.com> | 2014-03-17 15:53:45 +0100 |
commit | 5466218a5f9fb3d46f608806f222fcc99a306a4b (patch) | |
tree | 2d82056fe24bc508a985881149595fd83760b72a | |
parent | d106637504ec4cb5fa63feab11bd845faea2bc07 (diff) | |
download | mux-5466218a5f9fb3d46f608806f222fcc99a306a4b.tar.gz mux-5466218a5f9fb3d46f608806f222fcc99a306a4b.tar.bz2 mux-5466218a5f9fb3d46f608806f222fcc99a306a4b.zip |
no time scheduler
-rw-r--r-- | Makefile | 2 | ||||
-rw-r--r-- | kernel/task/include/task/idle.h | 6 | ||||
-rw-r--r-- | kernel/task/include/task/lock.h | 19 | ||||
-rw-r--r-- | kernel/task/include/task/sched.h | 63 | ||||
-rw-r--r-- | kernel/task/include/task/task.h | 45 | ||||
-rw-r--r-- | kernel/task/mcu/atmega2560/context.c | 98 | ||||
-rw-r--r-- | kernel/task/mcu/atmega2560/include/mcu/task/context.h | 137 | ||||
-rw-r--r-- | kernel/task/mcu/atmega2560/include/mcu/task/task.h | 11 | ||||
-rw-r--r-- | kernel/task/sched.c | 45 | ||||
-rw-r--r-- | kernel/tshield/mcu/atmega2560/tshield.c | 1 | ||||
-rw-r--r-- | main.c | 81 |
11 files changed, 457 insertions, 51 deletions
@@ -12,7 +12,7 @@ SERIAL=/dev/ttyACM0 BAUD=115200 # Modules to include in kernel -MODULES=collection sched time tshield bug serial +MODULES=bug collection task tshield # Toolchain flags CC=avr-gcc diff --git a/kernel/task/include/task/idle.h b/kernel/task/include/task/idle.h new file mode 100644 index 0000000..3b6e40a --- /dev/null +++ b/kernel/task/include/task/idle.h @@ -0,0 +1,6 @@ +#ifndef IDLE_H +#define IDLE_H + +void idle_entry(char args); + +#endif
\ No newline at end of file diff --git a/kernel/task/include/task/lock.h b/kernel/task/include/task/lock.h new file mode 100644 index 0000000..bfb7994 --- /dev/null +++ b/kernel/task/include/task/lock.h @@ -0,0 +1,19 @@ +#ifndef LOCK_H +#define LOCK_H + +#include "task/shed.h" + +typedef char spin_lock_t; + +#define SPIN_LOCK_UNLOCKED 0 + +static inline void spin_lock(struct spin_lock_t* lock) { + while(*lock != SPIN_LOCK_UNLOCKED) {yield();}; + *lock = 1; +} + +static inline void spin_unlock(struct spin_lock_t* lock) { + *lock = SPIN_LOCK_UNLOCKED; +} + +#endif
\ No newline at end of file diff --git a/kernel/task/include/task/sched.h b/kernel/task/include/task/sched.h new file mode 100644 index 0000000..9029664 --- /dev/null +++ b/kernel/task/include/task/sched.h @@ -0,0 +1,63 @@ +#ifndef SCHED_H +#define SCHED_H + +#include "collection/list.h" +#include "mcu/task/task.h" + +/** + * Points to currently executing task. If no scheduling has been enabled, + * this points to NULL + */ +extern struct tcb_t* volatile current; + +/** + * Queue that contains all tasks that are ready to be run, awaiting their + * turn from the scheduler. + */ +extern struct list_head ready; + +/** + * Stack pointer for operations performed out of task context, including any + * calls made after SAVE_CONTEXT(). + */ +extern void* volatile kstack; + +/** + * Makes the current task sleep on a specific queue. + * This moves the current task to the given queue's tail. + */ +static inline void sleep_queue(struct list_head* queue) { + list_move_tail(¤t->queue, queue); +} + +/** + * Wakes all tasks waiting in the given queue. + * This moves all tasks contained in the queue to the ready queue. + */ +static inline void wake_all_queue(struct list_head* queue) { + list_splice_init(queue, ready.prev); +} + +/** + * Initializes a given task and adds it to the ready queue. + */ +void spawn(struct tcb_t* const tcb); + +/** + * Voluntarily relinquishes control of the CPU from the current task to the scheduler. + */ +void yield() __attribute__ ( ( naked ) ); + + +/** + * Initializes the scheduler by setting up kstack, initializing the idle task + * and selecting the first task to run. + */ +void sched_init(); + +/** + * Enters the scheduler, setting current to the next runnable task. + */ +void schedule(); + +#endif diff --git a/kernel/task/include/task/task.h b/kernel/task/include/task/task.h new file mode 100644 index 0000000..40f18a0 --- /dev/null +++ b/kernel/task/include/task/task.h @@ -0,0 +1,45 @@ +#ifndef TASK_H +#define TASK_H + +#include "collection/list.h" + +/** + * Task control block, contains runtime + * information about tasks. + */ +struct tcb_t { + /** Stack pointer of this task. (must be first in structure) */ + char* volatile sp; + + /** Lowest address of this task's memory (inclusive). */ + char* mem_low; + + /** Highest address of this task's memory (inclusive). */ + char* mem_high; + + /** Entry function of this task. */ + void (*entry)(char); + + /** Current wait queue that this task is in.*/ + struct list_head queue; + + char id; + +}; + +/** + * Utility for declaring a task with statically allocated memory. + * Note: for a task to be scheduled, it must first be spawned (see spawn()). +*/ +#define DECLARE_TASK(name, stack_size, entry_function, pid) \ + static char _declared_stack_##name[stack_size]; \ + static struct tcb_t name = { \ + .sp = 0, \ + .mem_low = _declared_stack_##name, \ + .mem_high = _declared_stack_##name + stack_size - 1, \ + .entry = entry_function, \ + .queue = {}, \ + .id = pid \ + }; + +#endif
\ No newline at end of file diff --git a/kernel/task/mcu/atmega2560/context.c b/kernel/task/mcu/atmega2560/context.c new file mode 100644 index 0000000..bcc2130 --- /dev/null +++ b/kernel/task/mcu/atmega2560/context.c @@ -0,0 +1,98 @@ +#include "mcu/task/context.h" + +char* stack_init(const char* const mem_low, const char* const mem_high, void (*entry)(char), char args) { + char* sp = (char*) mem_high; + unsigned long address = (unsigned long) entry; + + // pattern for debugging purposes + *sp = (char) 0x1; + sp--; + *sp = (char) 0x2; + sp--; + *sp = (char) 0x1; + sp--; + *sp = (char) 0x2; + sp--; + + // put return address on stack + *sp = (char) ( address & (unsigned short) 0x00ff ); + sp--; + + *sp = (char) ( (address >> 8) & ( unsigned short ) 0x00ff ); + sp--; + + *sp = (char) ( (address >> 16) & ( unsigned short ) 0x00ff ); + sp--; + + // save registers + *sp = (char) 0x00; //r0 + sp--; + *sp = (char) 0x80; //SREG, enable interrupts when task starts + sp--; + *sp = ( char ) 0x00; //r1 + sp--; + *sp = ( char ) 0x00; //r2 + sp--; + *sp = ( char ) 0x00; //r3 + sp--; + *sp = ( char ) 0x00; //r4 + sp--; + *sp = ( char ) 0x00; //r5 + sp--; + *sp = ( char ) 0x00; //r6 + sp--; + *sp = ( char ) 0x00; //r7 + sp--; + *sp = ( char ) 0x00; //r8 + sp--; + *sp = ( char ) 0x00; //r9 + sp--; + *sp = ( char ) 0x00; //r10 + sp--; + *sp = ( char ) 0x00; //r11 + sp--; + *sp = ( char ) 0x00; //r12 + sp--; + *sp = ( char ) 0x00; //r13 + sp--; + *sp = ( char ) 0x00; //r14 + sp--; + *sp = ( char ) 0x00; //r15 + sp--; + *sp = ( char ) 0x00; //r16 + sp--; + *sp = ( char ) 0x00; //r17 + sp--; + *sp = ( char ) 0x00; //r18 + sp--; + *sp = ( char ) 0x00; //r19 + sp--; + *sp = ( char ) 0x00; //r20 + sp--; + *sp = ( char ) 0x00; //r21 + sp--; + *sp = ( char ) 0x00; //r22 + sp--; + *sp = ( char ) 0x00; //r23 + sp--; + + *sp = (char) ( args ); //place first argument in register 24 + sp--; + + *sp = ( char ) 0x00; //r25 + sp--; + *sp = ( char ) 0x00; //r26 + sp--; + *sp = ( char ) 0x00; //r27 + sp--; + *sp = ( char ) 0x00; //r28 + sp--; + *sp = ( char ) 0x00; //r29 + sp--; + *sp = ( char ) 0x00; //r30 + sp--; + *sp = ( char ) 0x00; //r31 + sp--; + + return sp; +} diff --git a/kernel/task/mcu/atmega2560/include/mcu/task/context.h b/kernel/task/mcu/atmega2560/include/mcu/task/context.h new file mode 100644 index 0000000..b717991 --- /dev/null +++ b/kernel/task/mcu/atmega2560/include/mcu/task/context.h @@ -0,0 +1,137 @@ +#ifndef CONTEXT_H +#define CONTEXT_H + +#include <avr/interrupt.h> +#define ret() asm volatile ( "ret" ) + +/* + * The macros save_context(), restore_context() as well as the code contained in + * init_stack is adapted from the FreeRTOS kernel (http://www.freertos.org/). + * Here by copyright, credits attributed to wherever they belong. + */ + +/** + * Save context to memory location specified by first two chars of + * a symbol named 'current' (this is why 'sp' has to be the first element of + * of task control blocks). After executing this macro, the stack pointer will + * be set to the address contained in 'kstack'. + */ +#define context_save() \ + asm volatile ( \ + "push r0 \n\t" \ + "in r0, __SREG__ \n\t" \ + "push r0 \n\t" \ + "push r1 \n\t" \ + "clr r1 \n\t" \ + "push r2 \n\t" \ + "push r3 \n\t" \ + "push r4 \n\t" \ + "push r5 \n\t" \ + "push r6 \n\t" \ + "push r7 \n\t" \ + "push r8 \n\t" \ + "push r9 \n\t" \ + "push r10 \n\t" \ + "push r11 \n\t" \ + "push r12 \n\t" \ + "push r13 \n\t" \ + "push r14 \n\t" \ + "push r15 \n\t" \ + "push r16 \n\t" \ + "push r17 \n\t" \ + "push r18 \n\t" \ + "push r19 \n\t" \ + "push r20 \n\t" \ + "push r21 \n\t" \ + "push r22 \n\t" \ + "push r23 \n\t" \ + "push r24 \n\t" \ + "push r25 \n\t" \ + "push r26 \n\t" \ + "push r27 \n\t" \ + "push r28 \n\t" \ + "push r29 \n\t" \ + "push r30 \n\t" \ + "push r31 \n\t" \ + "lds r26, current \n\t" \ + "lds r27, current +1 \n\t" \ + "in r0, __SP_L__ \n\t" \ + "st x+, r0 \n\t" \ + "in r0, __SP_H__ \n\t" \ + "st x+, r0 \n\t" \ + "lds r26, kstack \n\t" \ + "lds r27, kstack + 1 \n\t" \ + "ld r28, x+ \n\t" \ + "out __SP_L__, r28 \n\t" \ + "ld r29, x+ \n\t" \ + "out __SP_H__, r29 \n\t" \ + ) + + +/** + * Restore context to memory location specified by first two chars of + * a symbol named 'current'. + */ +#define context_restore() \ + asm volatile ( \ + "lds r26, kstack \n\t" \ + "lds r27, kstack +1 \n\t" \ + "in r0, __SP_L__ \n\t" \ + "st x+, r0 \n\t" \ + "in r0, __SP_H__ \n\t" \ + "st x+, r0 \n\t" \ + "lds r26, current \n\t" \ + "lds r27, current + 1 \n\t" \ + "ld r28, x+ \n\t" \ + "out __SP_L__, r28 \n\t" \ + "ld r29, x+ \n\t" \ + "out __SP_H__, r29 \n\t" \ + "pop r31 \n\t" \ + "pop r30 \n\t" \ + "pop r29 \n\t" \ + "pop r28 \n\t" \ + "pop r27 \n\t" \ + "pop r26 \n\t" \ + "pop r25 \n\t" \ + "pop r24 \n\t" \ + "pop r23 \n\t" \ + "pop r22 \n\t" \ + "pop r21 \n\t" \ + "pop r20 \n\t" \ + "pop r19 \n\t" \ + "pop r18 \n\t" \ + "pop r17 \n\t" \ + "pop r16 \n\t" \ + "pop r15 \n\t" \ + "pop r14 \n\t" \ + "pop r13 \n\t" \ + "pop r12 \n\t" \ + "pop r11 \n\t" \ + "pop r10 \n\t" \ + "pop r9 \n\t" \ + "pop r8 \n\t" \ + "pop r7 \n\t" \ + "pop r6 \n\t" \ + "pop r5 \n\t" \ + "pop r4 \n\t" \ + "pop r3 \n\t" \ + "pop r2 \n\t" \ + "pop r1 \n\t" \ + "pop r0 \n\t" \ + "out __SREG__, r0 \n\t" \ + "pop r0 \n\t" \ + ) + +/** Initialize the given memory addresses to contain a valid, initial stackframe. */ +char* stack_init(const char* const mem_low, const char* const mem_high, void (*entry)(char), char args); + +/** Initialize the given memory addresses to contain a valid, initial stackframe. */ +static inline void kstack_init(void **kstack) { + //this sets the kernel stack to the default stack location + //of this mcu, namely the top (stacks of tasks will typically + //be contained in memory allocated on the head and thus should + //overflow with the kernel stack) + *kstack = (void*) SP; +} + +#endif diff --git a/kernel/task/mcu/atmega2560/include/mcu/task/task.h b/kernel/task/mcu/atmega2560/include/mcu/task/task.h new file mode 100644 index 0000000..d9823af --- /dev/null +++ b/kernel/task/mcu/atmega2560/include/mcu/task/task.h @@ -0,0 +1,11 @@ +#ifndef MCU_TASK_H +#define MACU_TASK_H + + +/** Default stack size, you may use this definition for declaring tasks. */ +#define DEFAULT_STACK_SIZE 256 + +/** Stack size to be allocated for the idle task. */ +#define IDLE_STACK_SIZE 64 + +#endif
\ No newline at end of file diff --git a/kernel/task/sched.c b/kernel/task/sched.c new file mode 100644 index 0000000..652d562 --- /dev/null +++ b/kernel/task/sched.c @@ -0,0 +1,45 @@ +#include "bug/panic.h" +#include "task/task.h" +#include "task/sched.h" +#include "mcu/task/context.h" +#include "mcu/task/context.h" + + +struct tcb_t* volatile current = 0; + +struct list_head ready = LIST_HEAD_INIT(ready); + +void* volatile kstack; + +void spawn(struct tcb_t* const tcb) { + tcb->sp = stack_init(tcb->mem_low, tcb->mem_high, tcb->entry, tcb->id); + INIT_LIST_HEAD(&tcb->queue); + list_add_tail(&tcb->queue, &ready); +} + +void yield(void) { + cli(); + context_save(); + schedule(); + context_restore(); + sei(); + ret(); +} + + +void sched_init() { + kstack_init(&kstack); + schedule(); + context_restore(); + sei(); + ret(); +} + +void schedule() { + if(!list_empty(&ready)) { + current = list_entry(ready.next, struct tcb_t, queue); + list_move_tail(ready.next, &ready); + } else { + panic(); + } +}
\ No newline at end of file diff --git a/kernel/tshield/mcu/atmega2560/tshield.c b/kernel/tshield/mcu/atmega2560/tshield.c index 5502f83..7cc6e58 100644 --- a/kernel/tshield/mcu/atmega2560/tshield.c +++ b/kernel/tshield/mcu/atmega2560/tshield.c @@ -1,6 +1,7 @@ #include <avr/io.h> #include <avr/interrupt.h> #include "tshield/tshield.h" +#include "bug/panic.h" static void tshield_init_servo(); @@ -1,76 +1,57 @@ #include <stddef.h> #include <stdio.h> #include <avr/pgmspace.h> -#include <sched/sched.h> -#include <time/timer.h> -#include <bug/panic.h> -#include <bug/debug.h> -#include <tshield/tshield.h> -#include <collection/list.h> -#include <serial/serial.h> -#include "shell.h" +#include <avr/interrupt.h> +#include "task/task.h" +#include "task/sched.h" +#include "bug/panic.h" +#include "bug/debug.h" +#include "mcu/task/context.h" +#include "tshield/tshield.h" #define WAIT_CYCLES(cycles) for (volatile unsigned long i = 0; i < cycles; ++i) {} -static struct list_head frozen = LIST_HEAD_INIT(frozen); +struct list_head frozen = LIST_HEAD_INIT(frozen); + void freeze() __attribute__ ( ( naked ) ); void freeze() { - cli(); - SAVE_CONTEXT(); - sleep_on(&frozen); + context_save(); + sleep_queue(&frozen); schedule(); - RESTORE_CONTEXT(); - sei(); - asm volatile ( "ret" ); -} - -void wake() __attribute__ ( ( naked ) ); -void wake() { - cli(); - SAVE_CONTEXT(); - wake_all(&frozen); - RESTORE_CONTEXT(); - sei(); - asm volatile ( "ret" ); + context_restore(); } - void blink( char id) { while(1) { - debug_led(id,1); - sleep(id * 300); - debug_led(id,0); - sleep(id * 300); + debug_led(id - 1,1); + WAIT_CYCLES((long) id * 30000); + debug_led(id - 1,0); + WAIT_CYCLES((long) id * 30000); + freeze(); } -} - - -#define READ_BUFFER_SIZE 64 -void read(char id) { - serial_init(115200); - stdout = &serial_out; - stdin = &serial_in; - shell(); + panic(); } -DECLARE_TASK(task1, STACK_SIZE, blink); -DECLARE_TASK(task2, STACK_SIZE, blink); -DECLARE_TASK(task3, STACK_SIZE, blink); -DECLARE_TASK(task4, STACK_SIZE, read); + +DECLARE_TASK(task1, DEFAULT_STACK_SIZE, blink, 1); +DECLARE_TASK(task2, DEFAULT_STACK_SIZE, blink, 2); +DECLARE_TASK(task3, DEFAULT_STACK_SIZE, blink, 3); +DECLARE_TASK(task4, DEFAULT_STACK_SIZE, blink, 4); int main(int argc, char *argv[]) { cli(); tshield_init(); - timer_init(); - - spawn(&task1, 1); - spawn(&task2, 2); - spawn(&task3, 3); - spawn(&task4, 4); + - timer_start(); + spawn(&task1); + spawn(&task2); + spawn(&task3); + spawn(&task4); + + sei(); sched_init(); + panic(); //should never reach here while(1){} } |