1 files changed, 250 insertions, 121 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