Added paging and fixed several bugs

8 files changed, 459 insertions, 44 deletions

diff --git a/src/kernel/graphics/vesa.c b/src/kernel/graphics/vesa.c
index f6bdba0..32bc0e9 100644
--- a/src/kernel/graphics/vesa.c
+++ b/src/kernel/graphics/vesa.c
@@ -2,6 +2,7 @@
 #include "graphics.h"
 #include "../input/input.h"
 #include "../system.h"
+#include "../paging/kheap.h"
 
 void switch_to_vga() {
     regs16_t regs;
@@ -56,15 +57,11 @@ struct vbe_mode_info *vbe_set_mode(unsigned short mode) {
 }
 
 void set_optimal_resolution() {
-    init();
-    terminal_write_string("SUCCESS!\n");
-    keyboard_install();
-
     struct vbe_info *info;
     struct vbe_mode_info *mode_info;
 
-    // info = lmalloc(sizeof(struct vbe_info));
-    // mode_info = lmalloc(sizeof(struct vbe_mode_info));
+    info = kmalloc(sizeof(struct vbe_info));
+    mode_info = kmalloc(sizeof(struct vbe_mode_info));
 
     info->signature[0] = 'V';
     info->signature[1] = 'B';
@@ -83,7 +80,8 @@ void set_optimal_resolution() {
 
     uint16_t *mode_ptr = get_ptr(info->video_modes);
     uint16_t mode;
-    struct vbe_mode_info *highest;
+    uint16_t highest = 0x11B;
+    uint16_t highest_height = 0;
     while ((mode = *mode_ptr++) != 0xFFFF) {
         mode &= 0x1FF;
         regs16_t regs2;
@@ -94,12 +92,15 @@ void set_optimal_resolution() {
         int32(0x10, &regs2);
 
         if ((mode_info->attributes & 0x90) != 0x90) continue;
-        if (mode_info->height >= highest->height) {
-            highest = mode_info;
+        if (mode_info->height >= highest_height) {
+            highest = mode;
+            highest_height = mode_info->height;
         }
     }
 
-    // lfree(info);
+    vbe_set_mode(0x11B);
+
+    kfree(info);
 
     /*if (strcmp((const char *) info->version, (const char *) 0x300) == 0) {
         init();
diff --git a/src/kernel/graphics/vesa.h b/src/kernel/graphics/vesa.h
index 33272f8..eff74ea 100644
--- a/src/kernel/graphics/vesa.h
+++ b/src/kernel/graphics/vesa.h
@@ -11,9 +11,9 @@
 struct vbe_info {
     char signature[4];
     uint32_t version;
-    far_ptr_t oem;
+    struct far_ptr oem;
     uint32_t capabilities;
-    far_ptr_t video_modes;
+    struct far_ptr video_modes;
     uint32_t video_memory;
     uint32_t software_rev;
     uint32_t vendor;
diff --git a/src/kernel/kernel.c b/src/kernel/kernel.c
index 383966d..013f7d5 100644
--- a/src/kernel/kernel.c
+++ b/src/kernel/kernel.c
@@ -4,26 +4,29 @@
 #include "interrupts/interrupts.h"
 #include "input/input.h"
 #include "timer/timer.h"
+#include "paging/paging.h"
+#include "paging/kheap.h"
 
 void init() {
     gdt_install();
     idt_install();
     isrs_install();
     irq_install();
-    asm volatile ("sti");
+    init_kheap();
+    page_init();
     timer_install();
-    terminal_initialize();
+    // terminal_initialize();
     keyboard_install();
     // mouse_install();
+    asm volatile ("sti");
 }
 
 void kernel_main(void) {
     // vbe_set_mode(0x11B);
-    // set_optimal_resolution();
+    set_optimal_resolution();
     init();
-    keyboard_install();
 
-    terminal_write_string("Melvix loaded successfully!\n");
+    // terminal_write_string("Melvix loaded successfully!\n");
 
     // __asm__  ("div %0" :: "r"(0)); // Exception testing x/0
     for (;;);
diff --git a/src/kernel/paging/kheap.c b/src/kernel/paging/kheap.c
new file mode 100644
index 0000000..13f8ab2
--- /dev/null
+++ b/src/kernel/paging/kheap.c
@@ -0,0 +1,168 @@
+#include "kheap.h"
+#include "paging.h"
+#include "../lib/lib.h"
+#include "../system.h"
+
+unsigned int placement_address;
+
+heap_header_t *kheap = NULL;
+heap_header_t *uheap = NULL;
+
+void init_kheap() {
+    end = (unsigned int) &end;
+    placement_address = end;
+
+    kheap = (heap_header_t *) fmalloc(KHEAP_SIZE);
+    init_heap(kheap, KHEAP_SIZE);
+
+    uheap = (heap_header_t *) kmalloc_a(UHEAP_SIZE);
+    init_heap(uheap, UHEAP_SIZE);
+    vpage_map_user(root_vpage_dir, (unsigned int) &uheap, (unsigned int) &uheap);
+}
+
+void *fmalloc(unsigned int size) {
+    //assert(placement_address + size < MEM_END);
+    unsigned int hold = placement_address;
+    memory_set((void *) hold, 0, size);
+    placement_address += size;
+    return (void *) hold;
+}
+
+void *kmalloc_a(unsigned int size) {
+    //assert(((placement_address & 0xFFFFF000) + 0x1000) + size < MEM_END);
+    placement_address &= 0xFFFFF000;
+    placement_address += 0x1000;
+
+    unsigned int hold = placement_address;
+    placement_address += size;
+
+    return (void *) hold;
+}
+
+heap_header_t *find_sized_heap(heap_header_t *heap, size_t size) {
+    while ((heap->size < HEAP_FIND_SIZE + size) || (heap->free != 1)) {
+        assert(heap->magic == KHEAP_MAGIC);
+        assert(heap->magic2 == KHEAP_MAGIC2);
+        heap_footer_t *foot = (heap_footer_t *) ((unsigned int) heap + HEAP_S + heap->size);
+        assert(foot->magic == KHEAP_MAGIC);
+        assert(foot->magic2 == KHEAP_MAGIC2);
+
+        if (foot->size == KHEAP_END)
+            panic("out of heap space");
+
+        if (foot->size != heap->size)
+            panic("heap footer/header mismatch");
+
+        heap = (heap_header_t *) ((unsigned int) foot + sizeof(heap_footer_t));
+    }
+
+    return heap;
+}
+
+void split_heap(heap_header_t *heap, size_t size) {
+    heap_footer_t *foot = (heap_footer_t *) ((unsigned int) heap + HEAP_S + size);
+    foot->magic = KHEAP_MAGIC;
+    foot->magic2 = KHEAP_MAGIC2;
+    foot->size = size;
+
+    size_t new_size = heap->size - HEAP_TOTAL - size;
+    heap->size = size;
+
+    heap = (heap_header_t *) ((unsigned int) foot + sizeof(heap_footer_t));
+    heap->size = new_size;
+    heap->free = 1;
+    heap->magic = KHEAP_MAGIC;
+    heap->magic2 = KHEAP_MAGIC2;
+
+    foot = (heap_footer_t *) ((unsigned int) heap + HEAP_S + heap->size);
+    if ((foot->magic != KHEAP_MAGIC) || (foot->magic2 != KHEAP_MAGIC2)) {
+        warn("invalid footer in split");
+        // dump_struct(foot, sizeof(heap_footer_t));
+    }
+
+    if (foot->size != KHEAP_END)
+        foot->size = new_size;
+}
+
+void free_internal(heap_header_t *heap, void *address) {
+    heap_header_t *head = (heap_header_t *) ((unsigned int) address - HEAP_S);
+    if (head == heap) {
+        warn("can't collapse top of heap");
+        head->free = 1;
+        return;
+    }
+
+    if ((head->magic != KHEAP_MAGIC) || (head->magic2 != KHEAP_MAGIC2)) {
+        //warn("invalid header in heap");
+        //dump_struct(head, sizeof(heap_header_t));
+        return;
+    }
+
+    heap_footer_t *foot = (heap_footer_t *) ((unsigned int) head + HEAP_S + head->size);
+    if ((foot->magic != KHEAP_MAGIC) || (foot->magic2 != KHEAP_MAGIC2))
+        panic("bad heap in free() call");
+
+    foot = (heap_footer_t *) ((unsigned int) head - sizeof(heap_footer_t));
+    if ((foot->magic != KHEAP_MAGIC) || (foot->magic2 != KHEAP_MAGIC2)) {
+        //warn("invalid footer in heap");
+        return;
+    }
+
+    if (foot->size == KHEAP_END)
+        panic("impossible condition for heap");
+
+    heap = (heap_header_t *) ((unsigned int) foot - foot->size - HEAP_S);
+    if ((heap->magic != KHEAP_MAGIC) || (heap->magic2 != KHEAP_MAGIC2)) {
+        warn("invalid parent in heap");
+        return;
+    }
+
+    foot = (heap_footer_t *) ((unsigned int) heap + (heap->size + head->size + HEAP_TOTAL) + HEAP_S);
+    if ((foot->magic != KHEAP_MAGIC) || (foot->magic2 != KHEAP_MAGIC2)) {
+        return;
+    }
+
+    heap->size += head->size + HEAP_TOTAL;
+    foot->size = heap->size;
+}
+
+void *malloc_internal(heap_header_t *heap, size_t size) {
+    heap = find_sized_heap(heap, size + 8);
+    heap->free = 0;
+    split_heap(heap, size);
+    return (void *) ((unsigned int) heap + HEAP_S);
+}
+
+void init_heap(heap_header_t *heap, size_t size) {
+    heap->magic = KHEAP_MAGIC;
+    heap->magic2 = KHEAP_MAGIC2;
+    heap->free = 1;
+    heap->size = size - HEAP_TOTAL;
+
+    heap_footer_t *foot = (heap_footer_t *) ((unsigned int) heap + HEAP_S + heap->size);
+    foot->magic = KHEAP_MAGIC;
+    foot->magic2 = KHEAP_MAGIC2;
+    foot->size = KHEAP_END;
+}
+
+void *kmalloc(unsigned int size) {
+    if (kheap == NULL)
+        return fmalloc(size);
+
+    return malloc_internal(kheap, size);
+}
+
+void kfree(void *address) {
+    if (kheap == NULL)
+        return;
+
+    free_internal(kheap, address);
+}
+
+void *umalloc(size_t size) {
+    return malloc_internal(uheap, size);
+}
+
+void ufree(void *address) {
+    free_internal(uheap, address);
+}
\ No newline at end of file
diff --git a/src/kernel/paging/kheap.h b/src/kernel/paging/kheap.h
new file mode 100644
index 0000000..7a92957
--- /dev/null
+++ b/src/kernel/paging/kheap.h
@@ -0,0 +1,51 @@
+#ifndef MELVIX_KHEAP_H
+#define MELVIX_KHEAP_H
+
+#include <stdbool.h>
+#include <stddef.h>
+
+#define KHEAP_MAGIC    0x13374242
+#define KHEAP_MAGIC2 0xDEADBEEF
+#define KHEAP_END 0xFFFFDEAD
+#define MEM_END 0x8000000
+
+extern unsigned int end;
+
+typedef struct {
+    unsigned int magic;
+    bool free;
+    unsigned int size;
+    unsigned int magic2;
+} heap_header_t;
+
+typedef struct {
+    unsigned int magic;
+    unsigned int size;
+    unsigned int magic2;
+} heap_footer_t;
+
+#define HEAP_S (sizeof(heap_header_t))
+#define HEAP_TOTAL (sizeof(heap_footer_t) + HEAP_S)
+#define HEAP_MINIMUM 1
+#define HEAP_FIND_SIZE (HEAP_TOTAL + HEAP_MINIMUM)
+
+void init_kheap();
+
+void *fmalloc(unsigned int size);
+
+void *kmalloc(unsigned int size);
+
+void *kmalloc_a(unsigned int size);
+
+void kfree(void *ptr);
+
+void *umalloc(size_t size);
+
+void ufree(void *address);
+
+void init_heap(heap_header_t *heap, size_t size);
+
+#define KHEAP_SIZE 0xFFFFF
+#define UHEAP_SIZE 0xFFFFF
+
+#endif
diff --git a/src/kernel/paging/paging.c b/src/kernel/paging/paging.c
index 164372e..6282953 100644
--- a/src/kernel/paging/paging.c
+++ b/src/kernel/paging/paging.c
@@ -1,22 +1,159 @@
-#include <stdint.h>
+#include <stddef.h>
+#include "paging.h"
+#include "kheap.h"
+#include "../lib/lib.h"
+#include "../graphics/graphics.h"
+#include "../interrupts/interrupts.h"
 
-uint64_t page_dir_ptr_tab[4] __attribute__((aligned(0x20)));
-uint64_t page_dir[512] __attribute__((aligned(0x1000)));
-uint64_t page_tab[512] __attribute__((aligned(0x1000)));
+vpage_dir_t *current_vpage_dir = NULL;
+vpage_dir_t *root_vpage_dir = NULL;
 
-void enable_paging() {
-    page_dir_ptr_tab[0] = (uint64_t) &page_dir | 1;
-    page_dir[0] = (uint64_t) &page_tab | 3;
+//Assembly abstraction for more maintainable code
+page_table_t *get_cr3() {
+    unsigned int cr3;
 
-    unsigned int i, address = 0;
-    for (i = 0; i < 512; i++) {
-        page_tab[i] = address | 3;
-        address = address + 0x1000;
+    asm volatile ("movl %%cr3, %%eax" : "=a" (cr3));
+    return (page_table_t *) cr3;
+}
+
+unsigned int get_cr0() {
+    unsigned int cr0;
+
+    asm volatile ("movl %%cr0, %%eax" : "=a" (cr0));
+    return cr0;
+}
+
+void set_cr3(vpage_dir_t *dir) {
+    asm volatile ("movl %%eax, %%cr3"::"a" ((unsigned int) &dir->tables[0]));
+}
+
+void set_cr0(unsigned int new_cr0) {
+    asm volatile ("movl %%eax, %%cr0"::"a" (new_cr0));
+}
+
+void switch_vpage_dir(vpage_dir_t *dir) {
+    set_cr3(dir);
+    set_cr0(get_cr0() | 0x80000000);
+}
+
+vpage_dir_t *mk_vpage_dir() {
+    vpage_dir_t *dir = (vpage_dir_t *) kmalloc_a(sizeof(vpage_dir_t));
+
+    int i;
+    for (i = 0; i < 1024; i++)
+        dir->tables[i] = EMPTY_TAB;
+
+    return dir;
+}
+
+page_table_t *mk_vpage_table() {
+    page_table_t *tab = (page_table_t *) kmalloc_a(sizeof(page_table_t));
+
+    int i;
+    for (i = 0; i < 1024; i++) {
+        tab->pages[i].present = 0;
+        tab->pages[i].rw = 1;
+    }
+
+    return tab;
+}
+
+void vpage_map(vpage_dir_t *dir, unsigned int phys, unsigned int virt) {
+    short id = virt >> 22;
+    page_table_t *tab = mk_vpage_table();
+
+    dir->tables[id] = ((page_table_t *) ((unsigned int) tab | 3));
+
+    int i;
+    for (i = 0; i < 1024; i++) {
+        tab->pages[i].frame = phys >> 12;
+        tab->pages[i].present = 1;
+        phys += 4096;
+    }
+}
+
+void vpage_map_user(vpage_dir_t *dir, unsigned int phys, unsigned int virt) {
+    short id = virt >> 22;
+    page_table_t *tab = mk_vpage_table();
+
+    dir->tables[id] = ((page_table_t *) ((unsigned int) tab | 3 | 4));
+
+    int i;
+    for (i = 0; i < 1024; i++) {
+        tab->pages[i].frame = phys >> 12;
+        tab->pages[i].present = 1;
+        tab->pages[i].user = 1;
+        phys += 4096;
     }
+}
 
+void vpage_fault(struct regs *r) {
     asm volatile ("cli");
-    asm volatile ("movl %cr4, %eax; bts $5, %eax; movl %eax, %cr4"); // CRASH
-    asm volatile ("movl %%eax, %%cr3"::"a" (&page_dir_ptr_tab));
-    asm volatile ("movl %cr0, %eax; orl $0x80000000, %eax; movl %eax, %cr0;");
-    asm volatile ("sti");
+
+    unsigned int no_page = r->err_code & 1;
+    unsigned int rw = r->err_code & 2;
+    unsigned int um = r->err_code & 4;
+    unsigned int re = r->err_code & 8;
+    unsigned int dc = r->err_code & 16;
+
+    if (dc) terminal_write_line(" (Instruction decode error) ");
+    if (!no_page) terminal_write_line(" (No page present) ");
+    if (um) terminal_write_line(" (in user mode) ");
+    if (rw) terminal_write_line(" (Write permissions) ");
+    if (re) terminal_write_line(" (RE) ");
+
+    terminal_write_line("\n");
+}
+
+void page_init() {
+    current_vpage_dir = mk_vpage_dir();
+    root_vpage_dir = current_vpage_dir;
+
+    unsigned int i;
+    for (i = 0; i < 0xF0000000; i += PAGE_S)
+        vpage_map(root_vpage_dir, i, i);
+
+    irq_install_handler(14, vpage_fault);
+    asm volatile ("cli");
+    switch_vpage_dir(root_vpage_dir);
+}
+
+void convert_vpage(vpage_dir_t *kdir) {
+    int i;
+    for (i = 0; i < 1024; i++) {
+        kdir->tables[i] = (page_table_t *) ((unsigned int) kdir->tables[i] | 4);
+
+        if (((unsigned int) kdir->tables[i]) & 1) {
+            int j;
+            for (j = 0; j < 1024; j++)
+                kdir->tables[i]->pages[j].user = 1;
+        }
+    }
+}
+
+void dump_page(vpage_dir_t *dir, unsigned int address) {
+    unsigned short id = address >> 22;
+    terminal_write_line(&"Index salt ="[(unsigned int) dir->tables[id]]);
+}
+
+vpage_dir_t *copy_user_dir(vpage_dir_t *dir) {
+    unsigned int i;
+
+    vpage_dir_t *copy = mk_vpage_dir();
+    memory_copy(copy, root_vpage_dir, sizeof(vpage_dir_t));
+
+    for (i = 0; i < 1024; i++) {
+        if (((unsigned int) dir->tables[i]) & 4) {
+            //vga_fmt("Found a user page at index %d\n", i);
+            page_table_t *tab = (page_table_t *) ((unsigned int) dir->tables[i] & 0xFFFFF000);
+            //vga_fmt("Table at address %X maps to %X\n", (unsigned int) tab, i << 22);
+            //vga_fmt("Virtually mapped from %X\n", tab->pages[0].frame << 12);
+
+            void *buffer = kmalloc_a(PAGE_S);
+            memory_copy(buffer, (void *) (tab->pages[0].frame << 12), PAGE_S);
+            vpage_map_user(copy, (unsigned int) buffer, (unsigned int) i << 22);
+        }
+    }
+
+    return copy;
 }
\ No newline at end of file
diff --git a/src/kernel/paging/paging.h b/src/kernel/paging/paging.h
index e8c3bf4..790dbee 100644
--- a/src/kernel/paging/paging.h
+++ b/src/kernel/paging/paging.h
@@ -1,6 +1,63 @@
 #ifndef MELVIX_PAGING_H
 #define MELVIX_PAGING_H
 
-void enable_paging();
+#define PAGE_S 0x400000
+
+extern unsigned int *current_dir;
+extern unsigned int *root_dir;
+
+typedef struct {
+    unsigned int present    : 1;
+    unsigned int rw        : 1;
+    unsigned int user    : 1;
+    unsigned int accessed    : 1;
+    unsigned int dirty    : 1;
+    unsigned int unused    : 7;
+    unsigned int frame    : 20;
+} page_t;
+
+typedef struct {
+    page_t pages[1024];
+} page_table_t;
+
+typedef struct {
+    page_table_t *tables[1024];
+    unsigned int tables_physical[1024];
+    unsigned int physical_address;
+} page_directory_t;
+
+typedef struct {
+    page_table_t *tables[1024];
+} vpage_dir_t;
+
+extern vpage_dir_t *root_vpage_dir;
+
+#define EMPTY_TAB ((page_table_t*) 0x00000002)
+
+page_table_t *get_cr3();
+
+unsigned int get_cr0();
+
+void set_cr3(vpage_dir_t *dir);
+
+void set_cr0(unsigned int new_cr0);
+
+void switch_vpage_dir(vpage_dir_t *dir);
+
+vpage_dir_t *mk_vpage_dir();
+
+page_table_t *mk_vpage_table();
+
+void page_init();
+
+void vpage_map(vpage_dir_t *cr3, unsigned int virt, unsigned int phys);
+
+void vpage_map_user(vpage_dir_t *cr3, unsigned int virt, unsigned int phys);
+
+void convert_vpage(vpage_dir_t *kdir);
+
+void dump_page(vpage_dir_t *dir, unsigned int address);
+
+vpage_dir_t *copy_user_dir(vpage_dir_t *dir);
 
 #endif
diff --git a/src/kernel/system.h b/src/kernel/system.h
index b310d5b..d41b7bc 100644
--- a/src/kernel/system.h
+++ b/src/kernel/system.h
@@ -1,7 +1,7 @@
 #ifndef MELVIX_SYSTEM_H
 #define MELVIX_SYSTEM_H
 
-#include "graphics/graphics.h"
+#include <stdint.h>
 
 /**
  * Initialize the basic features of the OS
@@ -35,19 +35,17 @@ struct far_ptr {
     };
 } __attribute__ ((packed));
 
-typedef struct far_ptr far_ptr_t;
-
 /**
  * Get offset from ASM segment:offset pointer
  */
-uint16_t get_offset(const volatile void *p) {
+static inline uint16_t get_offset(const volatile void *p) {
     return (uint16_t) (uintptr_t) p & 0x000F;
 }
 
 /**
  * Get segment from ASM segment:offset pointer
  */
-uint16_t get_segment(const volatile void *p) {
+static inline uint16_t get_segment(const volatile void *p) {
     return (uint16_t) (((uintptr_t) p) >> 4);
 }
 
@@ -56,8 +54,8 @@ uint16_t get_segment(const volatile void *p) {
  * @param __ptr The ASM segment:offset pointer
  * @return The new far pointer
  */
-far_ptr_t FAR_PTR(void *__ptr) {
-    far_ptr_t __fptr;
+static inline struct far_ptr FAR_PTR(void *__ptr) {
+    struct far_ptr __fptr;
     __fptr.offset = get_offset(__ptr);
     __fptr.segment = get_segment(__ptr);
     return __fptr;
@@ -68,7 +66,7 @@ far_ptr_t FAR_PTR(void *__ptr) {
  * @param fptr The ASM far pointer
  * @return The normalized pointer
  */
-void *get_ptr(far_ptr_t fptr) {
+static inline void *get_ptr(struct far_ptr fptr) {
     return (void *) (unsigned long) ((fptr.segment << 4) + fptr.offset);
 }
 
@@ -77,7 +75,7 @@ void *get_ptr(far_ptr_t fptr) {
  * TODO: Add line number and file name
  * @param msg The warning cause/reason
  */
-void warn(char *msg) {
+static inline void warn(char *msg) {
     asm volatile ("cli");
     terminal_set_color(6);
     terminal_write_line("WARNING");
@@ -90,7 +88,7 @@ void warn(char *msg) {
  * TODO: Add line number and file name
  * @param msg The error cause/reason
  */
-void panic(char *msg) {
+static inline void panic(char *msg) {
     asm volatile ("cli");
     terminal_set_color(4);
     terminal_write_line("PANIC");
@@ -105,7 +103,7 @@ void panic(char *msg) {
  * TODO: Add line number and file name
  * @param x The value
  */
-void assert(int x) {
+static inline void assert(int x) {
     if (x == 0) {
         panic("Assertion failed");
     }