no time scheduler

11 files changed, 457 insertions, 51 deletions

diff --git a/Makefile b/Makefile
index e977db6..8660585 100644
--- a/Makefile
+++ b/Makefile
@@ -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(&current->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();
 
diff --git a/main.c b/main.c
index a2c8827..c4dadee 100644
--- a/main.c
+++ b/main.c
@@ -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){}
 }