Paging and heap rewrite

VESA drawing causes a Page fault because it tries to use a pointer to the framebuffer which was created before the paging has been initialized. If the resolution is set after the paging has been initialized the CPU throws a triple fault because the int32 call can not happen with paging turned on. To be fixed soon!

6 files changed, 692 insertions, 329 deletions

diff --git a/src/kernel/paging/kheap.c b/src/kernel/paging/kheap.c
index 2004cb8..94aa547 100644
--- a/src/kernel/paging/kheap.c
+++ b/src/kernel/paging/kheap.c
@@ -1,168 +1,297 @@
+#include <stdint.h>
 #include "kheap.h"
 #include "paging.h"
-#include "../lib/lib.h"
+#include "ordered_array.h"
 #include "../system.h"
 
-unsigned int placement_address;
+extern uint32_t end;
+uint32_t placement_address = (uint32_t) &end;
+extern page_directory_t *kernel_directory;
+heap_t *kheap = 0;
+
+uint32_t kmalloc_int(uint32_t sz, int align, uint32_t *phys) {
+    if (kheap != 0) {
+        void *addr = alloc(sz, (unsigned char) align, kheap);
+        if (phys != 0) {
+            page_t *page = get_page((uint32_t) addr, 0, kernel_directory);
+            *phys = page->frame * 0x1000 + ((uint32_t) addr & 0xFFF);
+        }
+        return (uint32_t) addr;
+    } else {
+        if (align == 1 && (placement_address & 0xFFFFF000)) {
+
+            placement_address &= 0xFFFFF000;
+            placement_address += 0x1000;
+        }
+        if (phys) {
+            *phys = placement_address;
+        }
+        uint32_t tmp = placement_address;
+        placement_address += sz;
+        return tmp;
+    }
+}
 
-heap_header_t *kheap = NULL;
-heap_header_t *uheap = NULL;
+void kfree(void *p) {
+    free(p, kheap);
+}
 
-void init_kheap() {
-    end = (unsigned int) &end;
-    placement_address = end;
+uint32_t kmalloc_a(uint32_t sz) {
+    return kmalloc_int(sz, 1, 0);
+}
 
-    kheap = (heap_header_t *) fmalloc(KHEAP_SIZE);
-    init_heap(kheap, KHEAP_SIZE);
+uint32_t kmalloc_p(uint32_t sz, uint32_t *phys) {
+    return kmalloc_int(sz, 0, phys);
+}
 
-    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);
+uint32_t kmalloc_ap(uint32_t sz, uint32_t *phys) {
+    return kmalloc_int(sz, 1, phys);
 }
 
-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;
+uint32_t kmalloc(uint32_t sz) {
+    return kmalloc_int(sz, 0, 0);
 }
 
-void *kmalloc_a(unsigned int size) {
-    //assert(((placement_address & 0xFFFFF000) + 0x1000) + size < MEM_END);
-    placement_address &= 0xFFFFF000;
-    placement_address += 0x1000;
+static void expand(uint32_t new_size, heap_t *heap) {
+    assert(new_size > heap->end_address - heap->start_address);
+
+    if (new_size & 0xFFFFF000 != 0) {
+        new_size &= 0xFFFFF000;
+        new_size += 0x1000;
+    }
 
-    unsigned int hold = placement_address;
-    placement_address += size;
+    assert(heap->start_address + new_size <= heap->max_address);
 
-    return (void *) hold;
+    uint32_t old_size = heap->end_address - heap->start_address;
+    uint32_t i = old_size;
+    while (i < new_size) {
+        alloc_frame(get_page(heap->start_address + i, 1, kernel_directory),
+                    (heap->supervisor) ? 1 : 0, (heap->readonly) ? 0 : 1);
+        i += 0x1000;
+    }
+    heap->end_address = heap->start_address + new_size;
 }
 
-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);
+static uint32_t contract(uint32_t new_size, heap_t *heap) {
+    assert(new_size < heap->end_address - heap->start_address);
 
-        if (foot->size == KHEAP_END)
-            panic("out of heap space");
+    if (new_size & 0x1000) {
+        new_size &= 0x1000;
+        new_size += 0x1000;
+    }
 
-        if (foot->size != heap->size)
-            panic("heap footer/header mismatch");
+    if (new_size < HEAP_MIN_SIZE)
+        new_size = HEAP_MIN_SIZE;
 
-        heap = (heap_header_t *) ((unsigned int) foot + sizeof(heap_footer_t));
+    uint32_t old_size = heap->end_address - heap->start_address;
+    uint32_t i = old_size - 0x1000;
+    while (new_size < i) {
+        free_frame(get_page(heap->start_address + i, 0, kernel_directory));
+        i -= 0x1000;
     }
-
-    return heap;
+    heap->end_address = heap->start_address + new_size;
+    return new_size;
 }
 
-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));
+static int find_smallest_hole(uint32_t size, unsigned char page_align, heap_t *heap) {
+    uint32_t iterator = 0;
+    while (iterator < heap->index.size) {
+        header_t *header = (header_t *) lookup_ordered_array(iterator, &heap->index);
+        if (page_align > 0) {
+            uint32_t location = (uint32_t) header;
+            int offset = 0;
+            if ((location + sizeof(header_t)) & 0xFFFFF000 != 0)
+                offset = 0x1000 - (location + sizeof(header_t)) % 0x1000;
+            int hole_size = (int) header->size - offset;
+
+            if (hole_size >= (int) size)
+                break;
+        } else if (header->size >= size)
+            break;
+        iterator++;
     }
 
-    if (foot->size != KHEAP_END)
-        foot->size = new_size;
+    if (iterator == heap->index.size)
+        return -1;
+    else
+        return iterator;
 }
 
-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;
-    }
+static char header_t_less_than(void *a, void *b) {
+    return (((header_t *) a)->size < ((header_t *) b)->size) ? 1 : 0;
+}
 
-    if ((head->magic != KHEAP_MAGIC) || (head->magic2 != KHEAP_MAGIC2)) {
-        //warn("invalid header in heap");
-        //dump_struct(head, sizeof(heap_header_t));
-        return;
+heap_t *create_heap(uint32_t start, uint32_t end_addr, uint32_t max, unsigned char supervisor, unsigned char readonly) {
+    heap_t *heap = (heap_t *) kmalloc(sizeof(heap_t));
+    assert(start % 0x1000 == 0);
+    assert(end_addr % 0x1000 == 0);
+    heap->index = place_ordered_array((void *) start, HEAP_INDEX_SIZE, &header_t_less_than);
+
+    start += sizeof(type_t) * HEAP_INDEX_SIZE;
+    if (start & 0xFFFFF000 != 0) {
+        start &= 0xFFFFF000;
+        start += 0x1000;
     }
 
-    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");
+    heap->start_address = start;
+    heap->end_address = end_addr;
+    heap->max_address = max;
+    heap->supervisor = supervisor;
+    heap->readonly = readonly;
+
+    header_t *hole = (header_t *) start;
+    hole->size = end_addr - start;
+    hole->magic = HEAP_MAGIC;
+    hole->is_hole = 1;
+    insert_ordered_array((void *) hole, &heap->index);
+    return heap;
+}
 
-    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;
+void *alloc(uint32_t size, unsigned char page_align, heap_t *heap) {
+    uint32_t new_size = size + sizeof(header_t) + sizeof(footer_t);
+
+    int iterator = find_smallest_hole(new_size, page_align, heap);
+    if (iterator == -1) {
+        uint32_t old_length = heap->end_address - heap->start_address;
+        uint32_t old_end_address = heap->end_address;
+        expand(old_length + new_size, heap);
+        uint32_t new_length = heap->end_address - heap->start_address;
+        iterator = 0;
+
+        uint32_t idx = -1;
+        uint32_t value = 0x0;
+        while (iterator < heap->index.size) {
+            uint32_t tmp = (uint32_t) lookup_ordered_array(iterator, &heap->index);
+            if (tmp > value) {
+                value = tmp;
+                idx = iterator;
+            }
+            iterator++;
+        }
+
+        if (idx == -1) {
+            header_t *header = (header_t *) old_end_address;
+            header->magic = HEAP_MAGIC;
+            header->size = new_length - old_length;
+            header->is_hole = 1;
+            footer_t *footer = (footer_t *) (old_end_address + header->size - sizeof(footer_t));
+            footer->magic = HEAP_MAGIC;
+            footer->header = header;
+            insert_ordered_array((void *) header, &heap->index);
+        } else {
+            header_t *header = lookup_ordered_array(idx, &heap->index);
+            header->size += new_length - old_length;
+            footer_t *footer = (footer_t *) ((uint32_t) header + header->size - sizeof(footer_t));
+            footer->header = header;
+            footer->magic = HEAP_MAGIC;
+        }
+        return alloc(size, page_align, heap);
     }
 
-    if (foot->size == KHEAP_END)
-        panic("impossible condition for heap");
+    header_t *orig_hole_header = (header_t *) lookup_ordered_array(iterator, &heap->index);
+    uint32_t orig_hole_pos = (uint32_t) orig_hole_header;
+    uint32_t orig_hole_size = orig_hole_header->size;
 
-    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;
+    if (orig_hole_size - new_size < sizeof(header_t) + sizeof(footer_t)) {
+        size += orig_hole_size - new_size;
+        new_size = orig_hole_size;
     }
 
-    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;
+    if (page_align && orig_hole_pos & 0xFFFFF000) {
+        uint32_t new_location = orig_hole_pos + 0x1000 - (orig_hole_pos & 0xFFF) - sizeof(header_t);
+        header_t *hole_header = (header_t *) orig_hole_pos;
+        hole_header->size = 0x1000 - (orig_hole_pos & 0xFFF) - sizeof(header_t);
+        hole_header->magic = HEAP_MAGIC;
+        hole_header->is_hole = 1;
+        footer_t *hole_footer = (footer_t *) ((uint32_t) new_location - sizeof(footer_t));
+        hole_footer->magic = HEAP_MAGIC;
+        hole_footer->header = hole_header;
+        orig_hole_pos = new_location;
+        orig_hole_size = orig_hole_size - hole_header->size;
+    } else {
+        remove_ordered_array(iterator, &heap->index);
     }
 
-    heap->size += head->size + HEAP_TOTAL;
-    foot->size = heap->size;
+    header_t *block_header = (header_t *) orig_hole_pos;
+    block_header->magic = HEAP_MAGIC;
+    block_header->is_hole = 0;
+    block_header->size = new_size;
+    footer_t *block_footer = (footer_t *) (orig_hole_pos + sizeof(header_t) + size);
+    block_footer->magic = HEAP_MAGIC;
+    block_footer->header = block_header;
+
+    if (orig_hole_size - new_size > 0) {
+        header_t *hole_header = (header_t *) (orig_hole_pos + sizeof(header_t) + size + sizeof(footer_t));
+        hole_header->magic = HEAP_MAGIC;
+        hole_header->is_hole = 1;
+        hole_header->size = orig_hole_size - new_size;
+        footer_t *hole_footer = (footer_t *) ((uint32_t) hole_header + orig_hole_size - new_size - sizeof(footer_t));
+        if ((uint32_t) hole_footer < heap->end_address) {
+            hole_footer->magic = HEAP_MAGIC;
+            hole_footer->header = hole_header;
+        }
+        insert_ordered_array((void *) hole_header, &heap->index);
+    }
+    return (void *) ((uint32_t) block_header + sizeof(header_t));
 }
 
-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 free(void *p, heap_t *heap) {
+    if (p == 0)
+        return;
 
-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;
+    header_t *header = (header_t *) ((uint32_t) p - sizeof(header_t));
+    footer_t *footer = (footer_t *) ((uint32_t) header + header->size - sizeof(footer_t));
 
-    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;
-}
+    assert(header->magic == HEAP_MAGIC);
+    assert(footer->magic == HEAP_MAGIC);
 
-void *kmalloc(unsigned int size) {
-    if (kheap == NULL)
-        return fmalloc(size);
+    header->is_hole = 1;
+    char do_add = 1;
 
-    return malloc_internal(kheap, size);
-}
+    footer_t *test_footer = (footer_t *) ((uint32_t) header - sizeof(footer_t));
+    if (test_footer->magic == HEAP_MAGIC &&
+        test_footer->header->is_hole == 1) {
+        uint32_t cache_size = header->size;
+        header = test_footer->header;
+        footer->header = header;
+        header->size += cache_size;
+        do_add = 0;
+    }
 
-void kfree(void *address) {
-    if (kheap == NULL)
-        return;
+    header_t *test_header = (header_t *) ((uint32_t) footer + sizeof(footer_t));
+    if (test_header->magic == HEAP_MAGIC &&
+        test_header->is_hole) {
+        header->size += test_header->size;
+        test_footer = (footer_t *) ((uint32_t) test_header + test_header->size - sizeof(footer_t));
+        footer = test_footer;
+        uint32_t iterator = 0;
+        while ((iterator < heap->index.size) && (lookup_ordered_array(iterator, &heap->index) != (void *) test_header))
+            iterator++;
+
+        assert(iterator < heap->index.size);
+        remove_ordered_array(iterator, &heap->index);
+    }
 
-    free_internal(kheap, address);
-}
+    if ((uint32_t) footer + sizeof(footer_t) == heap->end_address) {
+        uint32_t old_length = heap->end_address - heap->start_address;
+        uint32_t new_length = contract((uint32_t) header - heap->start_address, heap);
+
+        if (header->size - (old_length - new_length) > 0) {
+            header->size -= old_length - new_length;
+            footer = (footer_t *) ((uint32_t) header + header->size - sizeof(footer_t));
+            footer->magic = HEAP_MAGIC;
+            footer->header = header;
+        } else {
+            uint32_t iterator = 0;
+            while ((iterator < heap->index.size) &&
+                   (lookup_ordered_array(iterator, &heap->index) != (void *) test_header))
+                iterator++;
+
+            if (iterator < heap->index.size)
+                remove_ordered_array(iterator, &heap->index);
+        }
+    }
 
-void *umalloc(size_t size) {
-    return malloc_internal(uheap, size);
+    if (do_add == 1)
+        insert_ordered_array((void *) header, &heap->index);
 }
-
-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
index 7a92957..a1d946c 100644
--- a/src/kernel/paging/kheap.h
+++ b/src/kernel/paging/kheap.h
@@ -1,51 +1,112 @@
 #ifndef MELVIX_KHEAP_H
 #define MELVIX_KHEAP_H
 
-#include <stdbool.h>
-#include <stddef.h>
+#include "ordered_array.h"
 
-#define KHEAP_MAGIC    0x13374242
-#define KHEAP_MAGIC2 0xDEADBEEF
-#define KHEAP_END 0xFFFFDEAD
-#define MEM_END 0x8000000
+#define KHEAP_START         0xC0000000
+#define KHEAP_INITIAL_SIZE  0x100000
 
-extern unsigned int end;
+#define HEAP_INDEX_SIZE   0x20000
+#define HEAP_MAGIC        0x03A93A90
+#define HEAP_MIN_SIZE     0x70000
 
+/**
+ * Size information of holes/blocks
+ */
 typedef struct {
-    unsigned int magic;
-    bool free;
-    unsigned int size;
-    unsigned int magic2;
-} heap_header_t;
+    uint32_t magic;
+    unsigned char is_hole; // 1 if hole
+    uint32_t size;
+} header_t;
 
 typedef struct {
-    unsigned int magic;
-    unsigned int size;
-    unsigned int magic2;
-} heap_footer_t;
+    uint32_t magic;
+    header_t *header;
+} 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
+typedef struct {
+    ordered_array_t index;
+    uint32_t start_address;
+    uint32_t end_address;
+    uint32_t max_address;
+    unsigned char supervisor;
+    unsigned char readonly;
+} heap_t;
+
+/**
+ * Create a new heap
+ * @param start
+ * @param end
+ * @param max
+ * @param supervisor
+ * @param readonly
+ * @return The heap pointer
+ */
+heap_t *create_heap(uint32_t start, uint32_t end, uint32_t max, unsigned char supervisor, unsigned char readonly);
+
+/**
+ * Allocate a region of memory
+ * @param size The size of the memory
+ * @param page_align Start the block on a page boundary
+ * @param heap The Heap pointer
+ * @return
+ */
+void *alloc(uint32_t size, unsigned char page_align, heap_t *heap);
+
+/**
+ * Release an allocated block
+ * @param p The block
+ * @param heap The heap
+ */
+void free(void *p, heap_t *heap);
+
+/**
+ * Release an allocated block using kheap
+ * @param p The block
+ */
+void kfree(void *p);
+
+/**
+ * Allocate a chunk of memory
+ * @param sz The size of the memory
+ * @param align Start the block on a page boundary
+ * @param phys Location of the memory if not 0
+ * @return The memory address
+ */
+uint32_t kmalloc_int(uint32_t sz, int align, uint32_t *phys);
+
+/**
+ * Allocate a page-aligned chunk of memory
+ * @param sz The size of the memory
+ * @return The memory address
+ */
+uint32_t kmalloc_a(uint32_t sz);
+
+/**
+ * Allocate a chunk of memory in a physical address
+ * @param sz The size of the memory
+ * @param phys The physical address
+ * @return The memory address
+ */
+uint32_t kmalloc_p(uint32_t sz, uint32_t *phys);
+
+/**
+ * Allocate a page-aligned chunk of memory in a physical address
+ * @param sz The size of the memory
+ * @param phys The physical address
+ * @return The memory address
+ */
+uint32_t kmalloc_ap(uint32_t sz, uint32_t *phys);
+
+/**
+ * Allocate a chunk of memory (non page-aligned and no physical address)
+ * @param sz The size of the memory
+ * @return The memory address
+ */
+uint32_t kmalloc(uint32_t sz);
+
+/**
+   General deallocation function.
+**/
 
 #endif
diff --git a/src/kernel/paging/ordered_array.c b/src/kernel/paging/ordered_array.c
new file mode 100644
index 0000000..563a936
--- /dev/null
+++ b/src/kernel/paging/ordered_array.c
@@ -0,0 +1,66 @@
+#include <stdint.h>
+#include "ordered_array.h"
+#include "kheap.h"
+#include "../lib/lib.h"
+#include "../system.h"
+
+char standard_lessthan_predicate(type_t a, type_t b) {
+    return (a < b) ? 1 : 0;
+}
+
+ordered_array_t create_ordered_array(uint32_t max_size, lessthan_predicate_t less_than) {
+    ordered_array_t to_ret;
+    to_ret.array = (void *) kmalloc(max_size * sizeof(type_t));
+    memory_set(to_ret.array, 0, max_size * sizeof(type_t));
+    to_ret.size = 0;
+    to_ret.max_size = max_size;
+    to_ret.less_than = less_than;
+    return to_ret;
+}
+
+ordered_array_t place_ordered_array(void *addr, uint32_t max_size, lessthan_predicate_t less_than) {
+    ordered_array_t to_ret;
+    to_ret.array = (type_t *) addr;
+    memory_set(to_ret.array, 0, max_size * sizeof(type_t));
+    to_ret.size = 0;
+    to_ret.max_size = max_size;
+    to_ret.less_than = less_than;
+    return to_ret;
+}
+
+void destroy_ordered_array(ordered_array_t *array) {
+    kfree(array->array);
+}
+
+void insert_ordered_array(type_t item, ordered_array_t *array) {
+    assert(array->less_than);
+    uint32_t iterator = 0;
+    while (iterator < array->size && array->less_than(array->array[iterator], item))
+        iterator++;
+    if (iterator == array->size)
+        array->array[array->size++] = item;
+    else {
+        type_t tmp = array->array[iterator];
+        array->array[iterator] = item;
+        while (iterator < array->size) {
+            iterator++;
+            type_t tmp2 = array->array[iterator];
+            array->array[iterator] = tmp;
+            tmp = tmp2;
+        }
+        array->size++;
+    }
+}
+
+type_t lookup_ordered_array(uint32_t i, ordered_array_t *array) {
+    assert(i < array->size);
+    return array->array[i];
+}
+
+void remove_ordered_array(uint32_t i, ordered_array_t *array) {
+    while (i < array->size) {
+        array->array[i] = array->array[i + 1];
+        i++;
+    }
+    array->size--;
+}
diff --git a/src/kernel/paging/ordered_array.h b/src/kernel/paging/ordered_array.h
new file mode 100644
index 0000000..223ea14
--- /dev/null
+++ b/src/kernel/paging/ordered_array.h
@@ -0,0 +1,66 @@
+#ifndef MELVIX_ORDERED_ARRAY_H
+#define MELVIX_ORDERED_ARRAY_H
+
+#include <stdint.h>
+
+/**
+ * The array can store anything - so a void pointer is used
+ */
+typedef void *type_t;
+
+typedef char (*lessthan_predicate_t)(type_t, type_t);
+
+typedef struct {
+    type_t *array;
+    uint32_t size;
+    uint32_t max_size;
+    lessthan_predicate_t less_than;
+} ordered_array_t;
+
+/**
+ * A standard less-than predicate
+ * @param a The first parameter
+ * @param b The second parameter
+ * @return Non-zero if the first parameter is bigger than the second
+ */
+char standard_lessthan_predicate(type_t a, type_t b);
+
+/**
+ * Create an ordered array
+ * @param max_size Maximal size
+ * @param less_than The less-than predicate
+ * @return The newly created array
+ */
+ordered_array_t create_ordered_array(uint32_t max_size, lessthan_predicate_t less_than);
+
+ordered_array_t place_ordered_array(void *addr, uint32_t max_size, lessthan_predicate_t less_than);
+
+/**
+ * Destroy an ordered array
+ * @param array The ordered array
+ */
+void destroy_ordered_array(ordered_array_t *array);
+
+/**
+ * Add an item into the array
+ * @param item The item
+ * @param array The array
+ */
+void insert_ordered_array(type_t item, ordered_array_t *array);
+
+/**
+ * Lookup the item at a specific index
+ * @param i The index
+ * @param array The array
+ * @return
+ */
+type_t lookup_ordered_array(uint32_t i, ordered_array_t *array);
+
+/**
+ * Delete an item at an index from an array
+ * @param i The index
+ * @param array The array
+ */
+void remove_ordered_array(uint32_t i, ordered_array_t *array);
+
+#endif
diff --git a/src/kernel/paging/paging.c b/src/kernel/paging/paging.c
index 122e4c0..8f95bab 100644
--- a/src/kernel/paging/paging.c
+++ b/src/kernel/paging/paging.c
@@ -1,158 +1,198 @@
-#include <stddef.h>
 #include "paging.h"
 #include "kheap.h"
 #include "../lib/lib.h"
 #include "../graphics/graphics.h"
-#include "../interrupts/interrupts.h"
+#include "../io/io.h"
 
-vpage_dir_t *current_vpage_dir = NULL;
-vpage_dir_t *root_vpage_dir = NULL;
+page_directory_t *kernel_directory = 0;
+page_directory_t *current_directory = 0;
+uint32_t *frames;
+uint32_t nframes;
 
-page_table_t *get_cr3() {
-    unsigned int cr3;
+extern uint32_t placement_address;
+extern heap_t *kheap;
 
-    asm volatile ("movl %%cr3, %%eax" : "=a" (cr3));
-    return (page_table_t *) cr3;
-}
-
-unsigned int get_cr0() {
-    unsigned int cr0;
+#define INDEX_FROM_BIT(a) (a/(8*4))
+#define OFFSET_FROM_BIT(a) (a%(8*4))
 
-    asm volatile ("movl %%cr0, %%eax" : "=a" (cr0));
-    return cr0;
+static void set_frame(uint32_t frame_addr) {
+    uint32_t frame = frame_addr / 0x1000;
+    uint32_t idx = INDEX_FROM_BIT(frame);
+    uint32_t off = OFFSET_FROM_BIT(frame);
+    frames[idx] |= (0x1 << off);
 }
 
-void set_cr3(vpage_dir_t *dir) {
-    asm volatile ("movl %%eax, %%cr3"::"a" ((unsigned int) &dir->tables[0]));
+static void clear_frame(uint32_t frame_addr) {
+    uint32_t frame = frame_addr / 0x1000;
+    uint32_t idx = INDEX_FROM_BIT(frame);
+    uint32_t off = OFFSET_FROM_BIT(frame);
+    frames[idx] &= ~(0x1 << off);
 }
 
-void set_cr0(unsigned int new_cr0) {
-    asm volatile ("movl %%eax, %%cr0"::"a" (new_cr0));
+static uint32_t test_frame(uint32_t frame_addr) {
+    uint32_t frame = frame_addr / 0x1000;
+    uint32_t idx = INDEX_FROM_BIT(frame);
+    uint32_t off = OFFSET_FROM_BIT(frame);
+    return (frames[idx] & (0x1 << off));
 }
 
-void switch_vpage_dir(vpage_dir_t *dir) {
-    set_cr3(dir);
-    set_cr0(get_cr0() | 0x80000000);
+static uint32_t first_frame() {
+    uint32_t i, j;
+    for (i = 0; i < INDEX_FROM_BIT(nframes); i++) {
+        if (frames[i] != 0xFFFFFFFF) {
+            for (j = 0; j < 32; j++) {
+                uint32_t toTest = 0x1 << j;
+                if (!(frames[i] & toTest)) {
+                    return i * 4 * 8 + j;
+                }
+            }
+        }
+    }
 }
 
-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;
+void alloc_frame(page_t *page, int is_kernel, int is_writeable) {
+    if (page->frame != 0) {
+        return;
+    } else {
+        uint32_t idx = first_frame();
+        if (idx == (uint32_t) -1) panic("No free frames!");
+        set_frame(idx * 0x1000);
+        page->present = 1;
+        page->rw = (is_writeable == 1) ? 1 : 0;
+        page->user = (is_kernel == 1) ? 0 : 1;
+        page->frame = idx;
+    }
 }
 
-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;
+void free_frame(page_t *page) {
+    uint32_t frame;
+    if (!(frame = page->frame)) {
+        return;
+    } else {
+        clear_frame(frame);
+        page->frame = 0x0;
     }
-
-    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();
+void initialise_paging() {
+    uint32_t mem_end_page = 0x1000000;
+    nframes = mem_end_page / 0x1000;
+    frames = (uint32_t *) kmalloc(INDEX_FROM_BIT(nframes));
+    memory_set(frames, 0, INDEX_FROM_BIT(nframes));
+
+    uint32_t phys;
+    kernel_directory = (page_directory_t *) kmalloc_a(sizeof(page_directory_t));
+    memory_set(kernel_directory, 0, sizeof(page_directory_t));
+    kernel_directory->physicalAddr = (uint32_t) kernel_directory->tablesPhysical;
+
+    int i = 0;
+    for (i = KHEAP_START; i < KHEAP_START + KHEAP_INITIAL_SIZE; i += 0x1000)
+        get_page(i, 1, kernel_directory);
+
+    i = 0;
+    while (i < 0x400000) {
+        alloc_frame(get_page(i, 1, kernel_directory), 0, 0);
+        i += 0x1000;
+    }
 
-    dir->tables[id] = ((page_table_t *) ((unsigned int) tab | 3));
+    for (i = KHEAP_START; i < KHEAP_START + KHEAP_INITIAL_SIZE; i += 0x1000)
+        alloc_frame(get_page(i, 1, kernel_directory), 0, 0);
 
-    int i;
-    for (i = 0; i < 1024; i++) {
-        tab->pages[i].frame = phys >> 12;
-        tab->pages[i].present = 1;
-        phys += 4096;
-    }
+    irq_install_handler(14, page_fault);
+    switch_page_directory(kernel_directory);
+    kheap = create_heap(KHEAP_START, KHEAP_START + KHEAP_INITIAL_SIZE, 0xCFFFF000, 0, 0);
+    current_directory = clone_directory(kernel_directory);
+    switch_page_directory(current_directory);
 }
 
-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));
+void switch_page_directory(page_directory_t *dir) {
+    current_directory = dir;
+    asm volatile("mov %0, %%cr3"::"r"(dir->physicalAddr));
+    uint32_t cr0;
+    asm volatile("mov %%cr0, %0": "=r"(cr0));
+    cr0 |= 0x80000000;
+    asm volatile("mov %0, %%cr0"::"r"(cr0));
+}
 
-    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;
+page_t *get_page(uint32_t address, int make, page_directory_t *dir) {
+    address /= 0x1000;
+    uint32_t table_idx = address / 1024;
+
+    if (dir->tables[table_idx]) {
+        return &dir->tables[table_idx]->pages[address % 1024];
+    } else if (make) {
+        uint32_t tmp;
+        dir->tables[table_idx] = (page_table_t *) kmalloc_ap(sizeof(page_table_t), &tmp);
+        memory_set(dir->tables[table_idx], 0, 0x1000);
+        dir->tablesPhysical[table_idx] = tmp | 0x7;
+        return &dir->tables[table_idx]->pages[address % 1024];
+    } else {
+        return 0;
     }
 }
 
-void vpage_fault(struct regs *r) {
-    asm volatile ("cli");
-
-    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_fault(struct regs *r) {
+    uint32_t faulting_address;
+    asm volatile("mov %%cr2, %0" : "=r" (faulting_address));
+
+    int present = !(r->err_code & 0x1);
+    int rw = r->err_code & 0x2;
+    int us = r->err_code & 0x4;
+    int reserved = r->err_code & 0x8;
+    int id = r->err_code & 0x10;
+
+    serial_write("Page fault! ( ");
+    if (present) serial_write("present ");
+    if (rw) serial_write("read-only ");
+    if (us) serial_write("user-mode ");
+    if (reserved) serial_write("reserved ");
+    serial_write(") at 0x");
+    serial_write_hex(faulting_address);
+    serial_write(" - EIP: ");
+    serial_write_hex(r->eip);
+    serial_write("\n");
+    panic("Page fault");
 }
 
-void page_init() {
-    current_vpage_dir = mk_vpage_dir();
-    root_vpage_dir = current_vpage_dir;
+static page_table_t *clone_table(page_table_t *src, uint32_t *physAddr) {
+    page_table_t *table = (page_table_t *) kmalloc_ap(sizeof(page_table_t), physAddr);
+    memory_set(table, 0, sizeof(page_directory_t));
 
-    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;
-        }
+        if (!src->pages[i].frame)
+            continue;
+        alloc_frame(&table->pages[i], 0, 0);
+        if (src->pages[i].present) table->pages[i].present = 1;
+        if (src->pages[i].rw) table->pages[i].rw = 1;
+        if (src->pages[i].user) table->pages[i].user = 1;
+        if (src->pages[i].accessed)table->pages[i].accessed = 1;
+        if (src->pages[i].dirty) table->pages[i].dirty = 1;
+        extern void copy_page_physical(int a, int b);
+        copy_page_physical(src->pages[i].frame * 0x1000, table->pages[i].frame * 0x1000);
     }
+    return table;
 }
 
-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);
+page_directory_t *clone_directory(page_directory_t *src) {
+    uint32_t phys;
+    page_directory_t *dir = (page_directory_t *) kmalloc_ap(sizeof(page_directory_t), &phys);
+    memory_set(dir, 0, sizeof(page_directory_t));
+    uint32_t offset = (uint32_t) dir->tablesPhysical - (uint32_t) dir;
+    dir->physicalAddr = phys + offset;
+
+    for (int i = 0; i < 1024; i++) {
+        if (!src->tables[i])
+            continue;
+
+        if (kernel_directory->tables[i] == src->tables[i]) {
+            dir->tables[i] = src->tables[i];
+            dir->tablesPhysical[i] = src->tablesPhysical[i];
+        } else {
+            uint32_t phys;
+            dir->tables[i] = clone_table(src->tables[i], &phys);
+            dir->tablesPhysical[i] = phys | 0x07;
         }
     }
-
-    return copy;
-}
\ No newline at end of file
+    return dir;
+}
diff --git a/src/kernel/paging/paging.h b/src/kernel/paging/paging.h
index 790dbee..51f407f 100644
--- a/src/kernel/paging/paging.h
+++ b/src/kernel/paging/paging.h
@@ -1,63 +1,64 @@
 #ifndef MELVIX_PAGING_H
 #define MELVIX_PAGING_H
 
-#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;
+#include <stdint.h>
+#include "../interrupts/interrupts.h"
+
+typedef struct page {
+    uint32_t present    : 1;   // Page present in memory
+    uint32_t rw         : 1;   // Read-only if clear, readwrite if set
+    uint32_t user       : 1;   // Supervisor level only if clear
+    uint32_t accessed   : 1;   // Has the page been accessed since last refresh?
+    uint32_t dirty      : 1;   // Has the page been written to since last refresh?
+    uint32_t unused     : 7;   // Amalgamation of unused and reserved bits
+    uint32_t frame      : 20;  // Frame address (shifted right 12 bits)
 } page_t;
 
-typedef struct {
+typedef struct page_table {
     page_t pages[1024];
 } page_table_t;
 
-typedef struct {
+typedef struct page_directory {
     page_table_t *tables[1024];
-    unsigned int tables_physical[1024];
-    unsigned int physical_address;
+    uint32_t tablesPhysical[1024];
+    uint32_t physicalAddr;
 } 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);
+/**
+ * Initialize the environment and enables paging
+ */
+void initialise_paging();
+
+/**
+ * Load the page directory into the CR3 register
+ * @param new The page directory
+ */
+void switch_page_directory(page_directory_t *new);
+
+/**
+ * Get a specific page pointer
+ * @param address The page address
+ * @param make If 1 create the page first
+ * @param dir The page directory
+ * @return The page pointer
+ */
+page_t *get_page(uint32_t address, int make, page_directory_t *dir);
+
+/**
+ * Page fault handler
+ * @param r The IRQ registers
+ */
+void page_fault(struct regs *r);
+
+void alloc_frame(page_t *page, int is_kernel, int is_writeable);
+
+void free_frame(page_t *page);
+
+/**
+ * Copy/clone a page directory
+ * @param src The page directory
+ * @return A new page directory pointer
+ */
+page_directory_t *clone_directory(page_directory_t *src);
 
 #endif