Implemented a basic scheduler using an array of task structures in which

each structure has a TSS inside, as well as several descriptor entries
in the GDT pointing to each task's TSS. Task switching is performed in
hardware by means of far jumping to the new task's TSS descriptor in the
GDT. Task states are saved manually by copying the saved state from the
interrupt handler's stack, back into the task's TSS.

Added the function save_state() to sched.c which can be called from
assembly to copy the state information of the suspended task from the
current stack, to it's respective task structure. NOTE: this assumes
that the pointer cstate has been set ahead of time to point to the state
information on the stack, and that the pointer ctask has not yet been
modified.

Added the function reschedule() which is currently called from the
timer's tick handler. Currently, this function merely alternates between
the two tasks created in sched_init(), but in future, will be expanded
to decided independently which task will run next.

The function userspace_init() was renamed to the more appropriate
sched_init().

Moved most of the code from the original userspace_init() to the new
function create_proc() which sets up a virtual address space and state
information, copies the specified binary into the new address space,
then returns a pointer to the newly created tasks entry in the task
table.

Defined the type pid_t in unistd.h as a 16-bit unsigned integer.

Added two new debugging system calls for checking which task is
currently active. The getpid() system calls returns the caller's PID
whilst the getpdir() call returns the physical location of the caller's
page directory (the value of CR3). The getpdir() call can be used as a
fallback to determine which task is *actually* running if the
information in ctask or the getpid() call is faulty.

Added two new subroutines; set_tss() and clear_tss() (whose prototypes
are defined in asm/system.h) for managing the task-state descriptor
entries in the GDT. set_tss() initializes a TSS descriptor and sets it's
base pointer to the supplied TSS pointer whilst clear_tss() simply marks
a TSS descriptor as 'not present' without clearing it.

14 files changed, 301 insertions, 130 deletions

diff --git a/include/asm/system.h b/include/asm/system.h
index 02c2f62..0230f46 100644
--- a/include/asm/system.h
+++ b/include/asm/system.h
@@ -1,3 +1,6 @@
 #include <kernel/sched.h>
 
-volatile void switch_to(struct task_struct*, struct task_state*);
+volatile void switch_to(int n, struct task_struct *task);
+
+void set_tss(unsigned int n, void *tss);
+void clear_tss(unsigned int n);
diff --git a/include/kernel/sched.h b/include/kernel/sched.h
index afced68..a3d95e0 100644
--- a/include/kernel/sched.h
+++ b/include/kernel/sched.h
@@ -2,27 +2,44 @@
 #define _SCHED_H
 
 #include <stdint.h>
+#include <unistd.h>
 
-struct task_state {
-  uint32_t ss;
-  uint32_t esp;
-  uint32_t eflags;
-  uint32_t cs;
+struct tss_struct {
+  uint32_t prevt;
+  uint32_t esp0;
+  uint32_t ss0;
+  uint32_t esp1;
+  uint32_t ss1;
+  uint32_t esp2;
+  uint32_t ss2;
+  uint32_t cr3;
   uint32_t eip;
+  uint32_t eflags;
   uint32_t eax;
   uint32_t ecx;
   uint32_t edx;
   uint32_t ebx;
-  uint32_t esp_garbage;
+  uint32_t esp;
   uint32_t ebp;
   uint32_t esi;
   uint32_t edi;
+  uint32_t es;
+  uint32_t cs;
+  uint32_t ss;
+  uint32_t ds;
+  uint32_t fs;
+  uint32_t gs;
+  uint32_t ldt;
+  uint32_t io_map;
 } __attribute__((packed));
 
 struct task_struct {
-  struct task_state state;
+  pid_t pid;
+  struct tss_struct state;
 } __attribute__((packed));
 
-void userspace_init(void);
+extern struct task_struct *ctask;
+
+void sched_init(void);
 
 #endif
diff --git a/include/kernel/sys.h b/include/kernel/sys.h
index 7c129d2..248a93b 100644
--- a/include/kernel/sys.h
+++ b/include/kernel/sys.h
@@ -2,13 +2,15 @@ typedef int (*syscall_t) (void);
 
 extern int sys_puts(void);
 extern int sys_time(void);
+extern int sys_getpid(void);
+extern int sys_getpdir(void);
 extern int sys_dummy(void);
 
 syscall_t call_table[256] = {
   [0] = &sys_puts,
   [1] = &sys_time,
-  [2] = &sys_dummy,
-  [3] = &sys_dummy,
+  [2] = &sys_getpid,
+  [3] = &sys_getpdir,
   [4] = &sys_dummy,
   [5] = &sys_dummy,
   [6] = &sys_dummy,
diff --git a/include/unistd.h b/include/unistd.h
index ae46b16..6925541 100644
--- a/include/unistd.h
+++ b/include/unistd.h
@@ -1,8 +1,14 @@
 #ifndef _UNISTD_H
 #define _UNISTD_H
 
+#include <stdint.h>
+
+typedef uint16_t pid_t;
+
 #define __SYS_puts      0
 #define __SYS_time      1
+#define __SYS_getpid    2
+#define __SYS_getpdir   3
 
 #define _syscall0(type, name) \
   type name(void) { \
@@ -26,4 +32,7 @@
     return __res; \
   }
 
+pid_t getpid(void);
+void *getpdir(void);
+
 #endif
diff --git a/kernel/asm.s b/kernel/asm.s
index 4abe607..0bf9067 100644
--- a/kernel/asm.s
+++ b/kernel/asm.s
@@ -1,60 +1,76 @@
+global clear_tss
 global switch_to
+global set_tss
+extern cstate
 extern ctask
-extern tss
+extern gdt
+extern save_state
 
+; void switch_to(int n, struct task_struct *task);
 switch_to:
   push ebp
   mov ebp, esp
-  mov eax, [ebp+8]
-  mov [ctask], eax
-  mov esi, [ebp+12]
-  mov ecx, 13
-.loop:
-  lodsd
-  push eax
-  dec ecx
-  jz .end
-  jmp .loop
-.end:
-  mov ax, 0x23
-  mov ds, ax
-  mov es, ax
-  mov fs, ax
-  mov gs, ax
-  popa
-  iret
+  ; abort if we're switching to the current task
+  mov ebx, [ctask]
+  cmp ebx, [ebp+12]
+  jne .skip
+  pop ebp
+  ret
+.skip:
+  ; clear the busy flag in the current TSS
+  mov eax, 0
+  str ax
+  add ax, gdt+5
+  mov byte [eax], 0x89
+  ; set the current TSS to null so it won't be overwritten by the switch
+  mov ax, 0
+  ltr ax
+  ; copy the saved state into the previous TSS
+  call save_state
+  ; update ctask
+  mov ebx, [ebp+12]
+  mov [ctask], ebx
+  ; calculate the task segment index and jump to it
+  mov ebx, [ebp+8]
+  add ebx, 5
+  shl ebx, 3
+  mov [.tmp+4], bx
+  jmp far [.tmp]
+.tmp:
+  dq 0
 
-; uint32_t ss;
-; uint32_t esp;
-; uint32_t eflags;
-; uint32_t cs;
-; uint32_t eip;
-; uint32_t eax;
-; uint32_t ecx;
-; uint32_t edx;
-; uint32_t ebx;
-; uint32_t esp_garbage;
-; uint32_t ebp;
-; uint32_t esi;
-; uint32_t edi;
+; void set_tss(unsigned int n, void *tss);
+set_tss:
+  push ebp
+  mov ebp, esp
+  push ebx
+  mov eax, [ebp+12]
+  mov ebx, [ebp+8]
+  shl ebx, 3
+  add ebx, gdt+40
+  mov [ebx+2], ax
+  shr eax, 16
+  mov [ebx+4], al
+  mov [ebx+7], ah
+  mov eax, 103 ; limit - 1
+  mov [ebx], ax
+  shr eax, 16
+  and al, 0x0F
+  mov [ebx+6], al
+  mov byte [ebx+5], 0x89
+  pop ebx
+  pop ebp
+  ret
 
-; switch_to:
-  ; push ebp
-  ; mov ebp, esp
-  ; cli
-  ; mov ax, 0x23
-  ; mov ds, ax
-  ; mov es, ax
-  ; mov fs, ax
-  ; mov gs, ax
-  ; mov eax, esp
-  ; ; save ESP in the TSS
-  ; mov [tss+4], eax
-  ; push dword 0x23
-  ; push dword 0x00180000
-  ; pushf
-  ; push dword 0x1B
-  ; push dword 0x00100000
-  ; iret
-  ; pop ebp
-  ; ret
+; void clear_tss(unsigned int n);
+clear_tss:
+  push ebp
+  mov ebp, esp
+  push ebx
+  mov ebx, [ebp+8]
+  shl ebx, 3
+  add ebx, gdt+40
+  mov byte [ebx+5], 0
+  pop ebx
+  pop ebp
+  ret
diff --git a/kernel/boot.s b/kernel/boot.s
index 9d948cf..98732f6 100644
--- a/kernel/boot.s
+++ b/kernel/boot.s
@@ -2,7 +2,6 @@ global gdt
 global idt
 global kboot
 global register_isr
-global tss
 extern kmain
 extern paging_init
 extern syscall_init
@@ -23,7 +22,7 @@ kboot:
   cli
   ; put the stack pointer near the end of conventional memory
   ; WARNING: don't change this without changing the corresponding
-  ; entry in the TSS
+  ; entries in the TSS constructor in sched.c
   mov esp, 0x80000
   ; setup descriptor tables
   call flush_gdt
@@ -37,20 +36,6 @@ kboot:
   cli
   hlt
 
-tss:
-  dd 0
-  dd 0x80000    ; kernel stack pointer
-  dd 0x10       ; kernel stack segment
-  times 60 db 0
-  dd 0x13       ; ES segment
-  dd 0x0B       ; CS segment
-  dd 0x13       ; SS segment
-  dd 0x13       ; DS segment
-  dd 0x13       ; FS segment
-  dd 0x13       ; GS segment
-  times 8 db 0
-.end:
-
 gdt:
   ; null descriptor
   dq 0
@@ -82,9 +67,8 @@ gdt:
   db 0xF2
   db 0xCF
   db 0x00
-  ; task state segment
-.tss:
-  dq 0  ; we initialize this later
+  ; empty TSS slots for our C scheduler
+  times 64 dq 0
 .end:
 
 gdtp:
@@ -94,19 +78,6 @@ gdtp:
 flush_gdt:
   push ebp
   mov ebp, esp
-  ; initialize the TSS entry
-  mov eax, tss
-  mov [gdt.tss+2], ax
-  shr eax, 16
-  mov [gdt.tss+4], al
-  mov [gdt.tss+7], ah
-  mov eax, (tss.end-tss-1)
-  mov [gdt.tss], ax
-  shr eax, 16
-  and al, 0x0F
-  mov [gdt.tss+6], al
-  mov al, 0xE9
-  mov [gdt.tss+5], al
   ; now, load the GDT
   lgdt [gdtp]
   mov ax, 0x10
@@ -117,9 +88,6 @@ flush_gdt:
   mov ss, ax
   jmp 0x08:.end
 .end:
-  ; initialize the task state register
-  mov ax, 0x002B
-  ltr ax
   pop ebp
   ret
 
diff --git a/kernel/kmain.c b/kernel/kmain.c
index 5b2fe91..6b550b7 100644
--- a/kernel/kmain.c
+++ b/kernel/kmain.c
@@ -1,9 +1,7 @@
 #include <kernel/con.h>
-#include <kernel/memory.h>
 #include <kernel/sched.h>
 #include <kernel/sys.h>
 #include <stdint.h>
-#include <sys/types.h>
 
 void kmain(void) {
   con_init();
@@ -11,5 +9,5 @@ void kmain(void) {
   printk("Kernel booting...\n");
   printk("Kernel booted!\n\n");
 
-  userspace_init();
+  sched_init();
 }
diff --git a/kernel/sched.c b/kernel/sched.c
index 3e25de0..dd75d47 100644
--- a/kernel/sched.c
+++ b/kernel/sched.c
@@ -1,10 +1,17 @@
 #include <asm/system.h>
-#include <kernel/con.h>
 #include <kernel/memory.h>
 #include <kernel/sched.h>
 #include <string.h>
 #include <sys/types.h>
 
+/*
+ * WARNING!
+ * don't change this without also updating
+ * the number of TSS descriptors in the GDT
+ * (located in boot.s)
+ */
+#define NRTASKS 64
+
 #define USRSTART ((void*) 0x40000000)
 
 #define pages(n) \
@@ -23,9 +30,29 @@
 extern char _usrbin_start;
 extern char _usrbin_size;
 
+struct task_state {
+  uint16_t ds;
+  uint32_t edi;
+  uint32_t esi;
+  uint32_t ebp;
+  uint32_t esp_garbage;
+  uint32_t ebx;
+  uint32_t edx;
+  uint32_t ecx;
+  uint32_t eax;
+  uint32_t eip;
+  uint32_t cs;
+  uint32_t eflags;
+  uint32_t esp;
+  uint32_t ss;
+} __attribute__((packed));
+
 struct task_struct *ctask;
+struct task_state *cstate;
 
-static struct task_struct task;
+static struct task_struct tasks[NRTASKS];
+
+static pid_t nextpid;
 
 static inline void empty_table(void *t) {
   int i;
@@ -34,19 +61,41 @@ static inline void empty_table(void *t) {
     ((uint32_t*) t)[i] = 0;
 }
 
-void userspace_init(void) {
+struct task_struct *create_proc(void *bin, size_t len) {
   int i, j;
   int c;
   size_t totpages, npages, ntables;
   void *p, *page, *tab, *map;
   void *pdir, *stackt, *stackp;
+  struct task_struct *task = NULL;
 
-  size_t usrsize = (size_t) &_usrbin_size;
-
-  npages = pages(usrsize);
-  ntables = tables(pages(usrsize));
+  npages = pages(len);
+  ntables = tables(pages(len));
   totpages = npages + ntables + 3;
 
+  /* find an unused task structure */
+  for(i = 0; i < NRTASKS; i++) {
+    if(!tasks[i].pid) {
+      task = &tasks[i];
+      /* update the GDT */
+      set_tss(i, &tasks[i].state);
+      break;
+    }
+  }
+  if(task == NULL)
+    return NULL;
+
+  /* find an unused PID */
+  for(i = 0; i < NRTASKS; i++) {
+    if(tasks[i].pid == nextpid) {
+      /* TODO: handle PID exhaustion */
+      nextpid++;
+      if(nextpid == 0)
+        nextpid++;
+      i = 0;
+    }
+  }
+
   /* here we allocate pages to setup the process'
    * address space. in addition to the pages that
    * will hold the binary image, the following
@@ -57,19 +106,12 @@ void userspace_init(void) {
    *  - stack table (1 page)
    */
   p = alloc_physical_pages(totpages);
-  printk("Allocating %x pages for userspace process\n", totpages);
-  if(p == NULL) {
-    printk("Failed to allocate memory for userspace!\n");
-    return;
-  }
+  if(p == NULL)
+    return NULL;
 
   getpage(pdir, p);
   getpage(stackt, p);
   getpage(stackp, p);
-  printk("  Page directory:    0x%08x\n", (uint32_t) pdir);
-  printk("  Stack table:       0x%08x\n", (uint32_t) stackt);
-  printk("  Stack page:        0x%08x\n", (uint32_t) stackp);
-  printk("  Page tables:\n");
 
   /* populate the page directory */
   c = npages;
@@ -78,7 +120,6 @@ void userspace_init(void) {
   for(i = 0; i < ntables; i++) {
     /* add the table entry to the directory */
     getpage(tab, p);
-    printk("    0x%08x\n", (uint32_t) tab);
     map = map_page(pdir);
     ((uint32_t*) map)[i + (PGENT / 4)] = (uint32_t) tab | 0x007;
 
@@ -109,23 +150,83 @@ void userspace_init(void) {
 
   __asm__ volatile ("mov %%eax, %%cr3" :: "a" (pdir));
 
-  memcpy(USRSTART, &_usrbin_start, usrsize);
+  /* load in the user binary */
+  memcpy(USRSTART, bin, len);
 
   /*
    * here we initialize the task struct.
    * currently, we only setup state information
    * necessary to begin execution.
    */
-  memset(&task, 0, sizeof(task));
-  task.state.cs = 0x1B;
-  task.state.ss = 0x23;
-  task.state.eip = (uint32_t) USRSTART;
-  task.state.esp = 0xFFFFFFFF;
+  memset(task, 0, sizeof(struct task_struct));
+  task->pid = nextpid;
+  task->state.cr3 = (uint32_t) pdir;
+  task->state.cs = 0x1B;
+  task->state.ds = 0x23;
+  task->state.es = 0x23;
+  task->state.fs = 0x23;
+  task->state.gs = 0x23;
+  task->state.ss = 0x23;
+  task->state.eip = (uint32_t) USRSTART;
+  task->state.esp = 0xFFFFFFFF;
+  task->state.esp0 = 0x80000;
+  task->state.ss0 = 0x10;
   __asm__ (
       "pushf\n" \
       "pop %%eax" \
-      : "=a" (task.state.eflags) \
+      : "=a" (task->state.eflags) \
       ::);
 
-  switch_to(&task, &task.state);
+  return task;
+}
+
+void sched_init(void) {
+  int i;
+  struct task_struct *task;
+
+  memset(&tasks, 0, sizeof(tasks));
+  for(i = 0; i < NRTASKS; i++)
+    clear_tss(i);
+
+  nextpid = 1;
+  ctask = NULL;
+  cstate = NULL;
+
+  create_proc(&_usrbin_start, (size_t) &_usrbin_size);
+  create_proc(&_usrbin_start, (size_t) &_usrbin_size);
+
+  switch_to(0, &tasks[0]);
+}
+
+void save_state(void) {
+  if(ctask == NULL || cstate == NULL)
+    return;
+
+  ctask->state.eax = cstate->eax;
+  ctask->state.ebx = cstate->ebx;
+  ctask->state.ecx = cstate->ecx;
+  ctask->state.edx = cstate->edx;
+  ctask->state.esi = cstate->esi;
+  ctask->state.edi = cstate->edi;
+  ctask->state.esp = cstate->esp;
+  ctask->state.ebp = cstate->ebp;
+  ctask->state.cs = cstate->cs;
+  ctask->state.ds = cstate->ds;
+  ctask->state.es = cstate->ds;
+  ctask->state.fs = cstate->ds;
+  ctask->state.gs = cstate->ds;
+  ctask->state.ss = cstate->ss;
+  ctask->state.eflags = cstate->eflags;
+  ctask->state.eip = cstate->eip;
+}
+
+void reschedule(void) {
+  if(ctask == NULL)
+    return;
+
+  if(ctask == &tasks[0]) {
+    switch_to(1, &tasks[1]);
+  } else {
+    switch_to(0, &tasks[0]);
+  }
 }
diff --git a/kernel/sys.c b/kernel/sys.c
index 3748e2b..8c33fdf 100644
--- a/kernel/sys.c
+++ b/kernel/sys.c
@@ -1,7 +1,9 @@
 #include <errno.h>
 #include <kernel/con.h>
+#include <kernel/sched.h>
 #include <stdint.h>
 #include <time.h>
+#include <unistd.h>
 
 extern uint32_t ticks;
 
@@ -13,6 +15,18 @@ time_t sys_time(void) {
   return ticks / 100;
 }
 
+pid_t sys_getpid(void) {
+  return ctask->pid;
+}
+
+void *sys_getpdir(void) {
+  uint32_t pdir;
+
+  __asm__ ("mov %%cr3, %%eax" : "=a" (pdir));
+
+  return (void*) pdir;
+}
+
 int sys_dummy(void) {
   return -ENOSYS;
 }
diff --git a/kernel/timer.s b/kernel/timer.s
index 3723782..c84a847 100644
--- a/kernel/timer.s
+++ b/kernel/timer.s
@@ -1,15 +1,40 @@
 global ticks
 global timer_init
+extern cstate
 extern register_isr
+extern reschedule
 
 ticks: dd 0
 
 tick_handler:
+  pusha
+  ; save the data segment selectors
+  mov ax, ds
   push ax
+  ; switch to kernel data segments
+  mov ax, 0x10
+  mov ds, ax
+  mov es, ax
+  mov fs, ax
+  mov gs, ax
+  ; save a pointer to the state information
+  mov [cstate], esp
+
+  ; handle the timer tick
   inc dword [ticks]
   mov al, 0x20
   out 0x20, al
+
+  ; call the scheduler
+  call reschedule
+
+  ; restore the data segment selectors
   pop ax
+  mov ds, ax
+  mov es, ax
+  mov fs, ax
+  mov gs, ax
+  popa
   iret
 
 timer_init:
diff --git a/kernel/traps.s b/kernel/traps.s
index 15e2640..e084ac8 100644
--- a/kernel/traps.s
+++ b/kernel/traps.s
@@ -8,7 +8,7 @@ global traps_init
 extern call_table
 extern idt
 extern panic
-extern printf
+extern printk
 extern register_isr
 
 %macro SAVE 0
@@ -190,7 +190,16 @@ exc_stackf:
 
 exc_gprot:
   SAVE_ERR
+
+  push ebx
+  push .fmt
+  call printk
+  add esp, 8
+  call panic
+
   RESTORE_ERR
+.fmt:
+  db "General Protection Fault (0x%08x)", 10, 0
 
 exc_pagef:
   SAVE_ERR
@@ -199,8 +208,8 @@ exc_pagef:
   mov ebx, cr2
   push ebx
   push .fmt
-  call printf
-  add esp, 8
+  call printk
+  add esp, 12
   call panic
 
   RESTORE_ERR
diff --git a/lib/getpdir.c b/lib/getpdir.c
new file mode 100644
index 0000000..2320554
--- /dev/null
+++ b/lib/getpdir.c
@@ -0,0 +1,3 @@
+#include <unistd.h>
+
+_syscall0(void*, getpdir);
diff --git a/lib/getpid.c b/lib/getpid.c
new file mode 100644
index 0000000..99566e0
--- /dev/null
+++ b/lib/getpid.c
@@ -0,0 +1,3 @@
+#include <unistd.h>
+
+_syscall0(pid_t, getpid);
diff --git a/usrbin/main.c b/usrbin/main.c
index aa48450..83dcd90 100644
--- a/usrbin/main.c
+++ b/usrbin/main.c
@@ -1,12 +1,15 @@
 #include <stdint.h>
 #include <stdio.h>
 #include <time.h>
+#include <unistd.h>
 
 void main(void) {
+  int x = 0;
+
   printf("We did it ma!\n");
 
   while(1) {
     sleep(1);
-    printf("1000ms tick!\n");
+    printf("0x%04x:0x%08x: 0x%08x\n", getpid(), (uint32_t) getpdir(), x++);
   }
 }