Added '-g' flag for GCC to all makefiles to ensure debugging information

is produced. This may change later.

Added the new directory 'lib' to the source tree which build lib.a, an
archive containing common library routines for both the kernel and
userspace code to use.

Added the file string.c to the lib directory (as well as the appropriate
headers in /include) which provides some basic functions from the
standard C string library.

Added a physical memory manager which is now located in memory.c. This
memory manager tracks free pages from 1MB-8MB with a simple table and
allocates memory in blocks of 4KB pages. Multiple pages can be allocated
in which they are returned as a linked list.

Added a 'page window' in memory.c which allows the temporary mapping of
a single page at a time into the current address space.

Moved all paging routines that were previously located in page.s over to
memory.c where they have been re-implemented as a mixture of C and
inline assembly.

Moved the primative userspace routines from usrspace.s over to the new
sched.c. The only remaining routine, usrcall is now located in asm.s as
'switch_to' which takes two arguments, pointers to the task structure
and task state structure of the new task which is being switched to.

Pages for userspace are now allocated dynamically. The user binary is
loaded in at 1GB upwards. The user stack is located at the end of the
4GB address space with the lower 1GB being reserved for the kernel.

Updated the link.ld file for the userspace binary to include the new
starting address 0x40000000 (1GB).

Renamed the symbols for the user binary blob to make them shorter.

8 files changed, 327 insertions, 104 deletions

diff --git a/kernel/Makefile b/kernel/Makefile
index c6cf24e..29b5566 100644
--- a/kernel/Makefile
+++ b/kernel/Makefile
@@ -4,7 +4,7 @@ SRCS = $(wildcard *.c)
 ASMS = $(wildcard *.s)
 OBJS = $(SRCS:.c=.o) $(ASMS:.s=.o)
 
-CFLAGS = -m32 -I../include -ffreestanding -nostdinc -nostdlib -fno-stack-protector -fno-pie -gstabs+
+CFLAGS = -m32 -I../include -ffreestanding -nostdinc -nostdlib -fno-stack-protector -fno-pie -gstabs+ -g
 LDFLAGS = -m elf_i386 -r
 ASMFLAGS = -f elf32
 
diff --git a/kernel/asm.s b/kernel/asm.s
new file mode 100644
index 0000000..4abe607
--- /dev/null
+++ b/kernel/asm.s
@@ -0,0 +1,60 @@
+global switch_to
+extern ctask
+extern tss
+
+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
+
+; 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;
+
+; 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
diff --git a/kernel/boot.s b/kernel/boot.s
index 80f8be9..9d948cf 100644
--- a/kernel/boot.s
+++ b/kernel/boot.s
@@ -22,6 +22,8 @@ section .text
 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
   mov esp, 0x80000
   ; setup descriptor tables
   call flush_gdt
@@ -37,7 +39,7 @@ kboot:
 
 tss:
   dd 0
-  dd 0          ; kernel stack pointer
+  dd 0x80000    ; kernel stack pointer
   dd 0x10       ; kernel stack segment
   times 60 db 0
   dd 0x13       ; ES segment
diff --git a/kernel/kmain.c b/kernel/kmain.c
index ece7012..558df42 100644
--- a/kernel/kmain.c
+++ b/kernel/kmain.c
@@ -1,12 +1,13 @@
 #include <kernel/con.h>
+#include <kernel/memory.h>
 #include <kernel/sys.h>
 #include <stdint.h>
 #include <sys/types.h>
 
-uint32_t ticks = 0;
-
 extern void userspace_init(void);
 
+uint32_t ticks = 0;
+
 void kmain(void) {
   con_init();
 
diff --git a/kernel/memory.c b/kernel/memory.c
new file mode 100644
index 0000000..465b44f
--- /dev/null
+++ b/kernel/memory.c
@@ -0,0 +1,129 @@
+#include <kernel/memory.h>
+#include <stdint.h>
+#include <sys/types.h>
+
+static char __attribute__((aligned (4096))) mapped_page[4096];
+
+static pdir_t kpdir;
+
+ptab_t ktab;
+
+static ptab_t flow;
+static ptab_t fupp;
+
+void *alloc_physical_page(void) {
+  int i;
+  void *ret;
+
+  for(i = 0; i < PGENT; i++) {
+    if(flow[i] & 1) {
+      ret = (void*) (flow[i] & ~1);
+      flow[i] = 0;
+      return ret;
+    }
+
+    if(fupp[i] & 1) {
+      ret = (void*) (fupp[i] & ~1);
+      fupp[i] = 0;
+      return ret;
+    }
+  }
+
+  return NULL;
+}
+
+int free_physical_page(void *page) {
+  int i;
+  page = (void*) ((uint32_t) page & ~0xFFF);
+
+  for(int i = 0; i < PGENT; i++) {
+    if(!(flow[i] & 1)) {
+      flow[i] = (uint32_t) page | 1;
+      return 0;
+    }
+
+    if(!(fupp[i] & 1)) {
+      fupp[i] = (uint32_t) page | 1;
+      return 0;
+    }
+  }
+
+  return -1;
+}
+
+void *alloc_physical_pages(unsigned int n) {
+  void *p = NULL;
+  void *last = NULL;
+  void **page;
+
+  while(n--) {
+    p = alloc_physical_page();
+    if(p == NULL) {
+      page = &last;
+      while(*page) {
+	free_physical_page(*page);
+        page = *page;
+      }
+      return NULL;
+    }
+
+    map_page(p);
+    *((void**) mapped_page) = last;
+    last = p;
+  }
+
+  return p;
+}
+
+void *map_page(void *page) {
+  uint32_t p = (uint32_t) mapped_page;
+
+  /* enforce 4KB page alignment */
+  page = (void*) ((uint32_t) page & ~0xFFF);
+
+  ktab[(p >> 12) & 0x3FF] = (uint32_t) page | 0x003;
+  /*
+   * invalidate any cached entries for
+   * the mapped page window.
+   */
+  __asm__ ("invlpg %0" :: "m" (mapped_page));
+
+  return mapped_page;
+}
+
+void paging_init(void) {
+  int i;
+
+  /* empty the page directory */
+  for(i = 0; i < PGENT; i++)
+    kpdir[i] = 0;
+
+  /* populate the free page tables */
+  for(i = 0; i < PGENT; i++) {
+    /* populate the lower table */
+    flow[i] = (i << 12);
+    /* only pages >1MB can be allocated */
+    if(i >= 0x100)
+      flow[i] |= 0x001;
+    /* populate the upper table */
+    fupp[i] = ((i << 12) + 0x400000) | 0x001;
+  }
+
+  /* populate the kernel's page table */
+  for(i = 0; i < PGENT; i++) {
+    ktab[i] = 0;
+    if(i < 256)
+      ktab[i] = (i << 12) | 0x003;
+  }
+
+  /* populate the kernel's page directory */
+  kpdir[0] = ((pde_t) ktab) | 0x007;
+
+  __asm__ (
+      "mov %%eax, %%cr3\n"
+      "mov %%cr0, %%eax\n"
+      "or $0x80000000, %%eax\n"
+      "mov %%eax, %%cr0\n"
+      :: "a" (&kpdir)
+      :);
+}
diff --git a/kernel/page.s b/kernel/page.s
deleted file mode 100644
index 4e40822..0000000
--- a/kernel/page.s
+++ /dev/null
@@ -1,55 +0,0 @@
-global paging_init
-
-align 4096
-page_dir:
-  times 4096 db 0
-
-align 4096
-page_tables:
-  ; two page tables
-  times 4096 db 0
-  times 4096 db 0
-.end:
-
-; here, we initialize paging. since the IDT
-; has yet to be populated, we must take extra
-; care as we can't afford to trigger a page
-; fault.
-paging_init:
-  push ebp
-  mov ebp, esp
-  push ebx
-  ; populate the page directory
-  mov eax, page_tables
-  or eax, 0x007
-  mov [page_dir], eax
-  mov eax, (page_tables+4096)
-  or eax, 0x007
-  mov [page_dir+4], eax
-  ; populate the page tables
-  mov ebx, page_tables
-  mov ecx, ((page_tables.end-page_tables)/4)
-  mov edx, 0
-.loop:
-  mov eax, edx
-  or eax, 0x003
-  cmp edx, 0x100000
-  jb .skip
-  or eax, 0x004
-.skip:
-  mov [ebx], eax
-  dec ecx
-  jz .end
-  add ebx, 4
-  add edx, 4096
-  jmp .loop
-.end:
-  ; load the page directory and enable paging
-  mov eax, page_dir
-  mov cr3, eax
-  mov eax, cr0
-  or eax, 0x80000000
-  mov cr0, eax
-  pop ebx
-  pop ebp
-  ret
diff --git a/kernel/sched.c b/kernel/sched.c
new file mode 100644
index 0000000..f0b79fc
--- /dev/null
+++ b/kernel/sched.c
@@ -0,0 +1,131 @@
+#include <asm/system.h>
+#include <kernel/con.h>
+#include <kernel/memory.h>
+#include <kernel/sched.h>
+#include <string.h>
+#include <sys/types.h>
+
+#define USRSTART ((void*) 0x40000000)
+
+#define pages(n) \
+  ((n / 4096) + 1)
+
+#define tables(n) \
+  ((n / 1024) + 1)
+
+#define getpage(name, p) ({\
+  void **_next; \
+  _next = map_page(p); \
+  name = p; \
+  p = *_next; \
+  })
+
+extern char _usrbin_start;
+extern char _usrbin_size;
+
+struct task_struct *ctask;
+
+static struct task_struct task;
+
+static inline void empty_table(void *t) {
+  int i;
+
+  for(i = 0; i < PGENT; i++)
+    ((uint32_t*) t)[i] = 0;
+}
+
+void userspace_init(void) {
+  int i, j;
+  int c;
+  size_t totpages, npages, ntables;
+  void *p, *page, *tab, *map;
+  void *pdir, *stackt, *stackp;
+
+  size_t usrsize = (size_t) &_usrbin_size;
+
+  npages = pages(usrsize);
+  ntables = tables(pages(usrsize));
+  totpages = npages + ntables + 3;
+
+  /* here we allocate pages to setup the process'
+   * address space. in addition to the pages that
+   * will hold the binary image, the following
+   * pages are allocated:
+   *  - page directory (1 page)
+   *  - page tables
+   *  - stack page (1 page)
+   *  - stack table (1 page)
+   */
+  p = alloc_physical_pages(totpages);
+  printf("Allocating %x pages for userspace process\n", totpages);
+  if(p == NULL) {
+    printf("Failed to allocate memory for userspace!\n");
+    return;
+  }
+
+  getpage(pdir, p);
+  getpage(stackt, p);
+  getpage(stackp, p);
+  printf("  Page directory:    0x%08x\n", (uint32_t) pdir);
+  printf("  Stack table:       0x%08x\n", (uint32_t) stackt);
+  printf("  Stack page:        0x%08x\n", (uint32_t) stackp);
+  printf("  Page tables:\n");
+
+  /* populate the page directory */
+  c = npages;
+  map = map_page(pdir);
+  empty_table(map);
+  for(i = 0; i < ntables; i++) {
+    /* add the table entry to the directory */
+    getpage(tab, p);
+    printf("    0x%08x\n", (uint32_t) tab);
+    map = map_page(pdir);
+    ((uint32_t*) map)[i + (PGENT / 4)] = (uint32_t) tab | 0x007;
+
+    /* populate the page table */
+    map = map_page(tab);
+    for(j = 0; j < PGENT; j++) {
+      ((uint32_t*) map)[j] = 0;
+      if(c <= 0)
+        continue;
+
+      getpage(page, p);
+      map = map_page(tab);
+      ((uint32_t*) map)[j] = (uint32_t) page | 0x007;
+      c--;
+    }
+  }
+
+  /* populate the stack table */
+  map = map_page(stackt);
+  empty_table(map);
+  ((uint32_t*) map)[PGENT - 1] = (uint32_t) stackp | 0x007;
+
+  /* add the stack page table to the directory */
+  map = map_page(pdir);
+  ((uint32_t*) map)[PGENT - 1] = (uint32_t) stackt | 0x007;
+  /* add the kernel's page table to the directory */
+  ((uint32_t*) map)[0] = (uint32_t) ktab | 0x003;
+
+  __asm__ volatile ("mov %%eax, %%cr3" :: "a" (pdir));
+
+  memcpy(USRSTART, &_usrbin_start, usrsize);
+
+  /*
+   * 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;
+  __asm__ (
+      "pushf\n" \
+      "pop %%eax" \
+      : "=a" (task.state.eflags) \
+      ::);
+
+  switch_to(&task, &task.state);
+}
diff --git a/kernel/usrspace.s b/kernel/usrspace.s
deleted file mode 100644
index 1d20f71..0000000
--- a/kernel/usrspace.s
+++ /dev/null
@@ -1,45 +0,0 @@
-global userspace_init
-extern _binary_usrbin_bin_size
-extern _binary_usrbin_bin_start
-extern tss
-
-userspace_init:
-  push ebp
-  mov ebp, esp
-  push esi
-  push edi
-  mov ecx, _binary_usrbin_bin_size
-  mov esi, _binary_usrbin_bin_start
-  mov edi, 0x100000
-.loop:
-  movsb
-  dec ecx
-  jz .end
-  jmp .loop
-.end:
-  pop edi
-  pop esi
-  call usrcall
-  pop ebp
-  ret
-
-usrcall:
-  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