initial

3 files changed, 538 insertions, 0 deletions

diff --git a/kernel/src/memory/allocator.c b/kernel/src/memory/allocator.c
new file mode 100644
index 0000000..6217ad4
--- /dev/null
+++ b/kernel/src/memory/allocator.c
@@ -0,0 +1,314 @@
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+
+struct boundary_tag {
+	unsigned int magic;	   
+	unsigned int size; 	   
+	unsigned int real_size;
+	int index;
+
+	struct boundary_tag *split_left;
+	struct boundary_tag *split_right;
+	
+	struct boundary_tag *next;
+	struct boundary_tag *prev;
+};
+
+extern int memory_lock(void);
+extern int memory_unlock(void);
+extern void *memory_alloc_page(int);
+extern int memory_free_page(void* ,int);
+
+#define ALLOC_MAGIC     0xc001c0de
+#define MAXCOMPLETE     5
+#define MAXEXP          32
+#define MINEXP          8    
+
+#define MODE_BEST       0
+#define MODE_INSTANT    1
+
+#define MODE    MODE_BEST
+
+struct boundary_tag* l_freePages[MAXEXP];
+int                  l_completePages[MAXEXP];
+
+static int l_initialized = 0;
+static int l_pageSize  = 4096;
+static int l_pageCount = 16;
+
+static inline int getexp(unsigned int size) {
+    if (size < (1<<MINEXP)) {
+        return -1;
+    }
+        
+    int shift = MINEXP;
+
+    while (shift < MAXEXP) {
+        if ((unsigned)(1<<shift) > size) break;
+        shift += 1;
+    }
+
+    return shift - 1;    
+}
+
+static inline void insert_tag(struct boundary_tag *tag, int index) {
+    int realIndex;
+    
+    if (index < 0)  {
+        realIndex = getexp(tag->real_size - sizeof(struct boundary_tag));
+        if (realIndex < MINEXP) realIndex = MINEXP;
+    } else {
+        realIndex = index;
+    }
+    
+    tag->index = realIndex;
+    
+    if (l_freePages[ realIndex ] != NULL) {
+        l_freePages[ realIndex ]->prev = tag;
+        tag->next = l_freePages[ realIndex ];
+    }
+
+    l_freePages[ realIndex ] = tag;
+}
+
+static inline void remove_tag(struct boundary_tag *tag) {
+    if (l_freePages[ tag->index ] == tag) l_freePages[ tag->index ] = tag->next;
+
+    if (tag->prev != NULL) tag->prev->next = tag->next;
+    if (tag->next != NULL) tag->next->prev = tag->prev;
+
+    tag->next = NULL;
+    tag->prev = NULL;
+    tag->index = -1;
+}
+
+static inline struct boundary_tag* melt_left(struct boundary_tag *tag) {
+    struct boundary_tag *left = tag->split_left;
+                            
+    left->real_size   += tag->real_size;
+    left->split_right  = tag->split_right;
+    
+    if (tag->split_right != NULL) tag->split_right->split_left = left;
+
+    return left;
+}
+
+
+static inline struct boundary_tag* absorb_right(struct boundary_tag *tag) {
+    struct boundary_tag *right = tag->split_right;
+
+    remove_tag(right);
+    
+    tag->real_size += right->real_size;
+    
+    tag->split_right  = right->split_right;
+    if (right->split_right != NULL)
+                right->split_right->split_left = tag;
+
+    return tag;
+}
+
+static inline struct boundary_tag* split_tag(struct boundary_tag* tag) {
+    unsigned int remainder = tag->real_size - sizeof(struct boundary_tag) - tag->size;
+
+    struct boundary_tag *new_tag = 
+        (struct boundary_tag*)((uintptr_t)(void *)tag + sizeof(struct boundary_tag) + tag->size);    
+    
+    new_tag->magic = ALLOC_MAGIC;
+    new_tag->real_size = remainder;    
+
+    new_tag->next = NULL;
+    new_tag->prev = NULL;
+    
+    new_tag->split_left = tag;
+    new_tag->split_right = tag->split_right;
+    
+    if (new_tag->split_right != NULL) new_tag->split_right->split_left = new_tag;
+    tag->split_right = new_tag;
+    
+    tag->real_size -= new_tag->real_size;
+    
+    insert_tag(new_tag, -1);
+    
+    return new_tag;
+}
+
+static struct boundary_tag* allocate_new_tag(unsigned int size) {
+    unsigned int pages;
+    unsigned int usage;
+    struct boundary_tag *tag;
+
+    usage  = size + sizeof(struct boundary_tag);
+
+    pages = usage / l_pageSize;
+    if ((usage % l_pageSize) != 0) pages += 1;
+
+    if (pages < (unsigned) l_pageCount) pages = l_pageCount;
+
+    tag = (struct boundary_tag*)memory_alloc_page(pages);
+
+    if (tag == NULL) return NULL;
+    
+    tag->magic         = ALLOC_MAGIC;
+    tag->size         = size;
+    tag->real_size     = pages * l_pageSize;
+    tag->index         = -1;
+
+    tag->next        = NULL;
+    tag->prev        = NULL;
+    tag->split_left     = NULL;
+    tag->split_right     = NULL;
+
+    return tag;
+}
+
+
+
+void *malloc(size_t size) {
+    int index;
+    void *ptr;
+    struct boundary_tag *tag = NULL;
+
+    memory_lock();
+
+    if (l_initialized == 0) {
+        for (index = 0; index < MAXEXP; index++) {
+            l_freePages[index] = NULL;
+            l_completePages[index] = 0;
+        }
+        l_initialized = 1;
+    }
+
+    index = getexp(size) + MODE;
+    if (index < MINEXP) index = MINEXP;
+    
+    tag = l_freePages[index];
+    while (tag != NULL) {
+        if (
+            (tag->real_size - sizeof(struct boundary_tag)) 
+            >= (size + sizeof(struct boundary_tag))
+       ) {
+            break;
+        }
+        tag = tag->next;
+    }
+    
+    if (tag == NULL) {    
+        if ((tag = allocate_new_tag(size)) == NULL) {
+            memory_unlock();
+            return NULL;
+        }
+        index = getexp(tag->real_size - sizeof(struct boundary_tag));
+    } else {
+        remove_tag(tag);
+
+        if ((tag->split_left == NULL) && (tag->split_right == NULL))
+            l_completePages[ index ] -= 1;
+    }
+    
+    tag->size = size;
+
+    unsigned int remainder = tag->real_size - size - sizeof(struct boundary_tag) * 2;
+
+    if (((int)(remainder) > 0)) {
+        int childIndex = getexp(remainder);
+
+        if (childIndex >= 0) {
+            struct boundary_tag *new_tag = split_tag(tag); 
+            tag = new_tag;
+        }
+    }
+
+    ptr = (void*)((uintptr_t)(void *)tag + sizeof(struct boundary_tag));
+    memory_unlock();
+    return ptr;
+}
+
+void free(void *ptr) {
+    int index;
+    struct boundary_tag *tag;
+
+    if (ptr == NULL) return;
+
+    memory_lock();
+    
+    tag = (struct boundary_tag*)((uintptr_t)(void *)ptr - sizeof(struct boundary_tag));
+    
+    if (tag->magic != ALLOC_MAGIC) {
+        memory_unlock();
+        return;
+    }
+
+    while ((tag->split_left != NULL) && (tag->split_left->index >= 0)) {
+        tag = melt_left(tag);
+        remove_tag(tag);
+    }
+
+    while ((tag->split_right != NULL) && (tag->split_right->index >= 0)) {
+        tag = absorb_right(tag);
+    }
+
+    index = getexp(tag->real_size - sizeof(struct boundary_tag));
+    if (index < MINEXP) index = MINEXP;
+    
+    if ((tag->split_left == NULL) && (tag->split_right == NULL)) {
+        if (l_completePages[index] == MAXCOMPLETE) {
+            unsigned int pages = tag->real_size / l_pageSize;
+
+            if ((tag->real_size % l_pageSize) != 0) pages += 1;
+            if (pages < (unsigned) l_pageCount) pages = l_pageCount;
+
+            memory_free_page(tag, pages);
+            memory_unlock();
+            return;
+        }
+
+        l_completePages[ index ] += 1;
+    }
+
+    insert_tag(tag, index);
+
+    memory_unlock();
+}
+
+void* calloc(size_t nobj, size_t size) {
+    int real_size;
+    void *p;
+
+    real_size = nobj * size;
+       
+    p = malloc(real_size);
+
+    memset(p, 0, real_size);
+
+    return p;
+}
+
+void* realloc(void *p, size_t size) {
+    void *ptr;
+    struct boundary_tag *tag;
+    size_t real_size;
+    
+    if (size == 0) {
+        free(p);
+        return NULL;
+    }
+
+    if (p == NULL) {
+        return malloc(size);
+    }
+
+    memory_lock();
+    tag = (struct boundary_tag*)((uintptr_t)(void *)p - sizeof(struct boundary_tag));
+    real_size = tag->size;
+    memory_unlock();
+
+    if (real_size > size) real_size = size;
+
+    ptr = malloc(size);
+    memcpy(ptr, p, real_size);
+    free(p);
+
+    return ptr;
+}
diff --git a/kernel/src/memory/memory.c b/kernel/src/memory/memory.c
new file mode 100644
index 0000000..30da0fc
--- /dev/null
+++ b/kernel/src/memory/memory.c
@@ -0,0 +1,202 @@
+#include <stdint.h>
+#include <string.h>
+#include <sys.h>
+#include <panic.h>
+
+#include "memory.h"
+#include "boot/tag.h"
+#include "print.h"
+
+struct MemoryArea {
+    uint32_t len;
+    struct MemoryArea *prev;
+    struct MemoryArea *next;
+};
+
+typedef unsigned char page[4096];
+
+extern unsigned char kernel_start, kernel_end;
+static uintptr_t kernel_start_addr, kernel_end_addr;
+static uint32_t *bitmap;
+static uint32_t total_memory;
+static uint32_t free_memory;
+static uint32_t page_count;
+static uint32_t page_free_start;
+static struct MemoryArea *page_start;
+
+int memory_lock(void) {
+    int_disable();
+    return 0;
+}
+
+int memory_unlock(void) {
+    int_enable();
+    return 0;
+}
+
+static int n_pages(const struct MemoryArea *m) {
+	return (m->len - sizeof(*m)) / sizeof(page);
+}
+
+static void *page_at(int i) {
+	int cur_page = 0;
+	for (struct MemoryArea *m = page_start; m != NULL; m = m->next) {
+		int pages = n_pages(m);
+		if (i - cur_page < pages) {
+			page *page_array = (page *) (m + 1);
+			return page_array[i - cur_page];
+		}
+		cur_page += pages;
+	}
+	return NULL;
+}
+
+static int page_idx(page p) {
+	uintptr_t addr = (uintptr_t) p;
+	int cur_page = 0;
+	for (struct MemoryArea *m = page_start; m != NULL; m = m->next) {
+		if ((uintptr_t) m + m->len > addr) {
+			return cur_page + (addr - (uintptr_t) m) / sizeof(page);
+		}
+		cur_page += n_pages(m);
+	}
+	return -1;
+}
+
+static inline bool bitmap_get(int i) {
+	return (bitmap[i / 32] >> i % 32) & 1;
+}
+
+static inline void bitmap_set(int i, bool v) {
+	int idx = i / 32;
+	bitmap[idx] &= ~(1 << i % 32);
+	bitmap[idx] |=  (v << i % 32);
+}
+
+void *memory_alloc_page(int pages) {
+	if (pages < 1) return NULL;
+
+	int n_contiguous = 0;
+	int free_region_start = 0;
+	bool first = true;
+	for (uint32_t i = page_free_start; i < page_count; i++) {
+		bool free = !bitmap_get(i);
+
+		if (first) {
+			first = false;
+			page_free_start = i;
+		}
+
+		if (free) {
+			if (n_contiguous == 0) free_region_start = i;
+			n_contiguous++;
+			if (n_contiguous == pages) {
+				for (int j = 0; j < pages; j++)
+					bitmap_set(free_region_start + j, true);
+				return page_at(free_region_start);
+			}
+		} else n_contiguous = 0;
+	}
+
+	return NULL;
+}
+
+int memory_free_page(void *ptr, int pages) {
+	int idx = page_idx(ptr);
+	if (idx == -1) return 1;
+
+	if ((unsigned) idx < page_free_start) page_free_start = idx;
+
+	for (int i = 0; i < pages; i++)
+		bitmap_set(idx + pages, false);
+	return 0;
+}
+
+void memory_init(void) {
+
+    debugk("Loading memory pages");
+
+    memory_lock();
+
+    bitmap = NULL;
+    total_memory = 0;
+    free_memory = 0;
+    page_count = 0;
+    page_free_start = 0;
+    page_start = NULL;
+
+    kernel_start_addr = (uintptr_t) &kernel_start;
+    kernel_end_addr = (uintptr_t) &kernel_end;
+
+    struct BootTag *tag;
+    if (!get_boot_tag(iD_MEMORYMAP, &tag)) {
+        panic("No multiboot memory map found");
+    }
+
+    uintptr_t end = (uintptr_t) tag->data.memory_map;
+    end += tag->size;
+
+    struct MemoryArea *prev = NULL;
+    struct MemorySegment *segment = &tag->data.memory_map->entries[0];
+    for(; (uintptr_t) segment < end; segment++) {
+
+        if (segment->type != 1) continue;
+        if (segment->addr >= UINT32_MAX) continue;
+        if (segment->addr < kernel_start_addr) continue;
+
+        uint32_t length;
+        if (segment->addr + segment->len > UINT32_MAX) {
+            length = UINT32_MAX - segment->addr;
+        } else {
+            length = segment->len;
+        }
+
+        uintptr_t addr;
+        if (segment->addr < kernel_end_addr) {
+            addr = kernel_end_addr;
+            length -= addr - segment->addr;
+        } else {
+            addr = segment->addr;
+        }
+
+        struct MemoryArea *current = (struct MemoryArea *) addr;
+        current->prev = prev;
+        current->next = NULL;
+        current->len = length;
+
+        if (prev != NULL) {
+            prev->next = current;
+        } else {
+            page_start = current;
+        }
+
+        page_count += n_pages(current);
+        total_memory += length;
+
+        prev = current;
+
+    }
+
+	int bitmap_pages = page_count / 32 / sizeof(page) + 1;
+	bitmap = (uint32_t *) page_at(page_count - bitmap_pages);
+    page_count -= bitmap_pages;
+	memset(bitmap, 0, bitmap_pages * sizeof(page));
+	free_memory = page_count * sizeof(page);
+
+    memory_unlock();
+
+    succek("Memory loaded. %k total %k free", total_memory, free_memory);
+
+}
+
+uint32_t memory_total(void) {
+    return total_memory;
+}
+
+uint32_t memory_free(void) {
+    return free_memory;
+}
+
+uint32_t memory_used(void) {
+    return total_memory - free_memory;
+}
diff --git a/kernel/src/memory/memory.h b/kernel/src/memory/memory.h
new file mode 100644
index 0000000..5d99025
--- /dev/null
+++ b/kernel/src/memory/memory.h
@@ -0,0 +1,22 @@
+#pragma once
+
+#include <stdint.h>
+
+struct MemorySegment {
+    uint64_t addr;
+    uint64_t len;
+    uint32_t type;
+    uint32_t reserved;
+} __attribute__((packed));
+
+struct MemoryMap {
+    uint32_t entry_size;
+    uint32_t entry_version;
+    struct MemorySegment entries[];
+} __attribute__((packed));
+
+uint32_t memory_total(void);
+uint32_t memory_free(void);
+uint32_t memory_used(void);
+
+void memory_init(void);