better mboot and kalloc

8 files changed, 479 insertions, 117 deletions

diff --git a/src/arch/amd64/acpi.c b/src/arch/amd64/acpi.c
index 61083f4..732add7 100644
--- a/src/arch/amd64/acpi.c
+++ b/src/arch/amd64/acpi.c
@@ -5,6 +5,7 @@
 #include <stddef.h>
 
 #include "bindings.h"
+#include "memory.h"
 #include "serial.h"
 
 /* global state, idk a better way rn */
@@ -51,7 +52,7 @@ struct xsdp {
 // ACPI 1.0
 struct rsdt {
 	struct acpi_header h;
-	uint64_t sdt_pointers[];
+	uint32_t sdt_pointers[];
 };
 
 // eXtended system descriptor table
@@ -140,6 +141,11 @@ struct fadt {
 };
 
 struct acpi_state {
+	union {
+		struct xsdt *xsdt;
+		struct rsdt *rsdt;
+	} dst;
+	uint8_t version;
 	struct fadt fadt;
 	uint16_t SLP_TYPa;
 	uint16_t SLP_TYPb;
@@ -196,10 +202,15 @@ static int read_s5_addr(struct acpi_state *state) {
 }
 
 static void *acpi_find_table_rsdt(struct rsdt *rsdt, const char *identifier, int ident_len) {
-	int entries = (rsdt->h.length - sizeof(rsdt->h)) / 8;
+	int entries = (rsdt->h.length - sizeof(rsdt->h)) / 4;
 
 	for (int i = 0; i < entries; i++) {
 		struct acpi_header *h = (struct acpi_header *) (uintptr_t) rsdt->sdt_pointers[i];
+		char buf[6];
+		memcpy(buf, h->signature, 4);
+		buf[4] = '\n';
+		buf[5] = '\0';
+		serial_out_str(buf);
 		if (!strncmp(h->signature, identifier, ident_len))
 			return (void *)h;
 	}
@@ -222,6 +233,11 @@ static void *acpi_find_table_xsdt(struct xsdt *xsdt, const char *identifier, int
 }
 
 int acpi_init_rsdt(struct rsdt *rsdt) {
+	rsdt = mmap(rsdt, sizeof(struct rsdt));
+
+	state.dst.rsdt = rsdt;
+	state.version = 0;
+
 	if (!checksum((uint8_t *) &rsdt->h, rsdt->h.length))
 		return -1;
 
@@ -238,6 +254,11 @@ int acpi_init_rsdt(struct rsdt *rsdt) {
 }
 
 int acpi_init_xsdt(struct xsdt *xsdt) {
+
+	xsdt = mmap(xsdt, sizeof(struct xsdt));
+	state.dst.xsdt = xsdt;
+	state.version = 2;
+
 	if (!checksum((uint8_t *) &xsdt->h, xsdt->h.length))
 		return -1;
 
@@ -256,7 +277,7 @@ int acpi_init_xsdt(struct xsdt *xsdt) {
 int acpi_init(void *rootsdp) {
 	struct rsdp *rsdp = (struct rsdp *) rootsdp;
 
-	if (!checksum((uint8_t *)rsdp, sizeof(struct xsdp)))
+	if (!checksum((uint8_t *)rsdp, sizeof(struct rsdp)))
 		return -1;
 
 	int res;
diff --git a/src/arch/amd64/linker.ld b/src/arch/amd64/linker.ld
index 3dd90ff..a9484d4 100644
--- a/src/arch/amd64/linker.ld
+++ b/src/arch/amd64/linker.ld
@@ -1,8 +1,12 @@
 ENTRY(start)
 
+PHDRS {
+    loadable PT_LOAD FLAGS(7) ;
+}
+
 SECTIONS {
     . = 1M;
-    
+
     kernel_start = .;
 
     .boot BLOCK(4K) : ALIGN(4K)
@@ -24,6 +28,11 @@ SECTIONS {
     {
         *(.bss)
     }
-    
+
+    .symtab : {
+        symtab = .;
+        *(.symtab)
+    } :loadable
+
     kernel_end = .;
 }
diff --git a/src/arch/amd64/mboot.c b/src/arch/amd64/mboot.c
index 89fb431..7fd3f62 100644
--- a/src/arch/amd64/mboot.c
+++ b/src/arch/amd64/mboot.c
@@ -1,71 +1,227 @@
 #include "mboot.h"
+#include "serial.h"
 #include "shim.h"
 
 #include <lib.h>
+#include <stdint.h>
+
+extern char symtab;
+#define kaddr(addr) ((uintptr_t)(&addr))
+
+typedef unsigned char           mboot_uint8_t;
+typedef unsigned short          mboot_uint16_t;
+typedef unsigned int            mboot_uint32_t;
+typedef unsigned long long      mboot_uint64_t;
+
+struct mboot_info {
+	mboot_uint32_t total_size;
+	mboot_uint32_t reserved;
+	char tags[];
+};
+
+struct mboot_tag {
+	mboot_uint32_t type;
+	mboot_uint32_t size;
+	char data[];
+};
 
 enum mboot_tag_type {
 	MBOOT_CMDLINE = 0,
 	MBOOT_MEMORYMAP = 6,
 	MBOOT_SYMBOLS = 9,
-	MBOOT_XSDP = 14
+	MBOOT_RSDP = 14,
+	MBOOT_XSDP = 15,
 };
 
-static void read_cmdline(struct boot_info *shim_info, char *data, uint8_t len) {
-    if (len >= CMDLINE_MAX)
-		len = CMDLINE_MAX; // truncate :(
-    memcpy(shim_info->cmdline, data, len);
-    shim_info->cmdline[len] = '\0';
-}
+struct mboot_elf_header_layout {
+	mboot_uint32_t type;
+	mboot_uint32_t size;
+	mboot_uint32_t num;
+	mboot_uint32_t entsize;
+	mboot_uint32_t shndx;
+	char elf_section_headers[];
+};
 
-static void read_memorymap(struct boot_info *shim_info, uint64_t size, uint32_t *data) {
-    shim_info->map = (struct memory_map *) data;
-    shim_info->map->size = size;
-}
+struct mboot_elf_section_header {
+	mboot_uint32_t sh_name;
+	mboot_uint32_t sh_type;
+	mboot_uint64_t sh_flags;
+	mboot_uint64_t sh_addr;
+	mboot_uint64_t sh_offset;
+	mboot_uint64_t sh_size;
+	mboot_uint32_t sh_link;
+	mboot_uint32_t sh_info;
+	mboot_uint64_t sh_addralign;
+	mboot_uint64_t sh_entsize;
+};
 
-static void read_xsdp(struct boot_info *shim_info, char *data) {
-    shim_info->acpi_table = (void *) data;
-}
+struct mboot_memory_segment {
+	mboot_uint64_t addr;
+	mboot_uint64_t len;
+	mboot_uint32_t type;
+	mboot_uint32_t reserved;
+};
 
-static uint32_t *read_tag(uint32_t *data, struct boot_info *shim_info) {
+struct mboot_memory_map {
+	mboot_uint32_t tag;
+	mboot_uint32_t size;
+	mboot_uint32_t entry_size;
+	mboot_uint32_t entry_version;
+	struct memory_segment entries[];
+};
+
+struct mboot_rsdp {
+	mboot_uint32_t tag;
+	mboot_uint32_t size;
+	mboot_uint8_t rsdp[];
+};
 
-    uint16_t type = *((uint16_t *)data);
-    uint32_t size = data[1];
+struct mboot_xsdp {
+	mboot_uint32_t tag;
+	mboot_uint32_t size;
+	mboot_uint8_t xsdp[];
+};
 
-    uint8_t data_len = size - 2 * sizeof(uint32_t);
+struct mboot_cmdline {
+	mboot_uint32_t tag;
+	mboot_uint32_t size;
+	char cmdline[];
+};
 
-    switch (type) {
-        case MBOOT_CMDLINE:
-            read_cmdline(shim_info, (char *)(data + 2), data_len);
-            break;
-        case MBOOT_MEMORYMAP:
-            read_memorymap(shim_info, size, data + 2);
-            break;
-        case MBOOT_SYMBOLS:
-			shim_info->symbol_table = (void *) (data + 2);
-            break;
-        case MBOOT_XSDP:
-            read_xsdp(shim_info, (char *) (data + 2));
-            break;
-        default:
-            break;
-    }
+static void read_symbols(
+		struct boot_info *shim_info,
+		struct mboot_elf_header_layout *layout
+) {
 
-    if(size % 8 != 0) {
-		size += 8 - (size % 8);
-	}
+	shim_info->symbol_table = layout->elf_section_headers;
 
-    return data + size / sizeof(uint32_t);
+//	struct mboot_elf_section_header *section =
+//		(struct mboot_elf_section_header *) (layout->elf_section_headers);
+//
+//	for (mboot_uint32_t i = 0; i < layout->num; i++) {
+//		char buf[20];
+//
+//		ultoa(i, buf, 10);
+//		serial_out_str("[");
+//        serial_out_str(buf);
+//        serial_out_str("]\t");
+//
+//		serial_out_str((char *)(kaddr(symtab) + section->sh_name));
+//		serial_out('\t');
+//
+//		ultoa(section->sh_type, buf, 16);
+//		serial_out_str("type: 0x");
+//        serial_out_str(buf);
+//        serial_out('\t');
+//
+//        ultoa(section->sh_addr, buf, 16);
+//        serial_out_str("addr: 0x");
+//        serial_out_str(buf);
+//        serial_out('\t');
+//
+//        ultoa(section->sh_offset, buf, 16);
+//        serial_out_str("offset: 0x");
+//        serial_out_str(buf);
+//        serial_out('\n');
+//
+//        section++;
+//	}
+}
+
+static void read_cmdline(
+		struct boot_info *shim_info,
+		struct mboot_cmdline *cmdline
+) {
+	mboot_uint32_t size = cmdline->size - 8;
+    if (size >= CMDLINE_MAX)
+		size = CMDLINE_MAX; // truncate :(
+    memcpy(shim_info->cmdline, cmdline->cmdline, size);
+    shim_info->cmdline[size] = '\0';
+}
+
+static void read_memorymap(
+		struct boot_info *shim_info,
+		struct mboot_memory_map *map
+) {
+	int size = map->size - sizeof(mboot_uint32_t) * 4;
+	int count = size / map->entry_size;
+
+    shim_info->map.entry_count = count;
+    shim_info->map.entry_length = map->entry_size;
+	shim_info->map.entries = map->entries;
+}
+
+static void read_rsdp(
+		struct boot_info *shim_info,
+		struct mboot_rsdp *rsdp
+) {
+	if (shim_info->acpi_table != NULL)
+		return; // xsdp is newer and has been loaded
+    shim_info->acpi_table = rsdp->rsdp;
+}
+
+static void read_xsdp(
+		struct boot_info *shim_info,
+		struct mboot_xsdp *xsdp
+) {
+    shim_info->acpi_table = xsdp->xsdp;
 }
 
 void mboot_load_info(
-        const void *mboot_info,
+        const void *mboot_data_ptr,
         struct boot_info *shim_info
 ) {
-    uint32_t* data = (uint32_t*) mboot_info;
-    uint32_t total_size = *data++;
-    data++; //reserved
 
-    while((uint8_t*) data < (uint8_t*) mboot_info + total_size) {
-        data = read_tag(data, shim_info);
-    }
+	memset(shim_info, 0, sizeof(struct boot_info));
+
+	struct mboot_info *mboot_info = (struct mboot_info *) mboot_data_ptr;
+	const char *mboot_end = ((char *) mboot_info) + mboot_info->total_size;
+
+	char *tag_ptr = mboot_info->tags;
+
+	while (tag_ptr < mboot_end) {
+		struct mboot_tag *tag = (struct mboot_tag *) tag_ptr;
+
+		switch (tag->type) {
+			case MBOOT_CMDLINE:
+        	    read_cmdline(
+						shim_info,
+						(struct mboot_cmdline *) tag
+				);
+        	    break;
+        	case MBOOT_MEMORYMAP:
+        	    read_memorymap(
+						shim_info,
+						(struct mboot_memory_map *) tag
+				);
+        	    break;
+        	case MBOOT_SYMBOLS:
+				read_symbols(
+						shim_info,
+						(struct mboot_elf_header_layout *) tag
+				);
+        	    break;
+        	case MBOOT_RSDP:
+        	    read_rsdp(
+						shim_info,
+						(struct mboot_rsdp *) tag
+				);
+        	    break;
+			case MBOOT_XSDP:
+				read_xsdp(
+						shim_info,
+						(struct mboot_xsdp *) tag
+				);
+				break;
+        	default:
+        	    break;
+		}
+
+		int size = tag->size;
+		if (size % 8 != 0) {
+			size += 8 - (size % 8);
+		}
+
+		tag_ptr += size;
+	}
 }
diff --git a/src/arch/amd64/paging.c b/src/arch/amd64/paging.c
index 453af9d..3ea79f1 100644
--- a/src/arch/amd64/paging.c
+++ b/src/arch/amd64/paging.c
@@ -1,3 +1,4 @@
+#include <panic.h>
 #include <cpuid.h>
 #include <stdint.h>
 #include <lib.h>
@@ -568,6 +569,11 @@ void *alloc_pages(int count) {
 }
 
 void free_page(void *virt) {
+	(void) virt;
+	panic("free_page is not yet implemented");
+}
+
+void free_pages(void *virt) {
 	long pages = virtaddr_free(virt);
 	if (pages < 1)
 		return;
diff --git a/src/kmain.c b/src/kmain.c
index 6424b95..54ed506 100644
--- a/src/kmain.c
+++ b/src/kmain.c
@@ -1,36 +1,12 @@
-#include "acpi.h"
+#include <acpi.h>
 #include <memory.h>
 #include <lib.h>
 #include <serial.h>
 #include <fb.h>
 #include <shim.h>
 
-void print_memory() {
-	size_t WIDTH = 64;
-
-	for(size_t i = 0;; i += WIDTH) {
-		char buf[20];
-		ultoa(i, buf, 16);
-		serial_out_str("0x");
-		for(size_t k = 0; k < 6 - strlen(buf); k++) {
-			serial_out('0');
-		}
-		serial_out_str(buf);
-		serial_out_str(": ");
-		for(size_t j = 0; j < WIDTH; j++) {
-			char x = *(char *)(i + j);
-			if(x < 0x20 || x >= 0x7f) {
-				serial_out('.');
-			} else {
-				serial_out(x);
-			}
-		}
-		serial_out('\n');
-	}
-}
-
 void kmain(struct boot_info *info) {
-	memory_init(info->map);
+	memory_init(&info->map);
 	//acpi_init(info->acpi_table);
 	//fb_init(1024, 768);
 
diff --git a/src/memory/memory.c b/src/memory/memory.c
new file mode 100644
index 0000000..1c69bae
--- /dev/null
+++ b/src/memory/memory.c
@@ -0,0 +1,214 @@
+#include <memory.h>
+#include <stdint.h>
+#include <lib.h>
+
+#ifdef MEMORY_PANIC
+#include <panic.h>
+#endif
+
+#define MAGIC 0xBEEFCAFE
+
+struct page_header {
+	struct page_header *next;
+	struct page_header *prev;
+	size_t node_number;			// all headers on the same page alloc have the same node number (so they can be merged)
+	size_t free;				// free space after the node (if its the last node in the alloc block)
+	size_t used;				// how much space this allocation is using
+	uint64_t magic;
+};
+
+static const size_t header_len = sizeof(struct page_header);
+struct page_header *start_header = NULL;
+struct page_header *end_header = NULL;
+
+struct page_header* get_header(void *ptr) {
+	struct page_header *header =
+		(struct page_header *) ((uintptr_t) ptr - header_len);
+
+	// PERF: do we want to make sure this pointer is paged
+	// before reading it???
+	if (header->magic != MAGIC) {
+		return NULL; // invalid pointer
+	}
+
+	return header;
+}
+
+void *kalloc_new(size_t size) {
+	size_t pages = ((size + header_len) / PAGE_SIZE) + 1;
+	void *addr = alloc_pages(pages);
+	void *mem = (char *)addr + header_len;
+
+	size_t total = pages * PAGE_SIZE;
+	size_t free = total - (size + header_len);
+
+	if (addr == NULL) {
+		return NULL;
+	}
+
+	size_t node;
+	if (end_header != NULL) {
+		node = end_header->node_number + 1;
+	} else {
+		node = 0;
+	}
+
+	struct page_header *header = addr;
+	header->magic = MAGIC;
+	header->used = size;
+	header->free = free;
+	header->prev = end_header;
+	header->next = NULL;
+	header->node_number = node;
+
+	if (end_header == NULL) {
+		start_header = header;
+	} else {
+		end_header->next = header;
+	}
+
+	end_header = header;
+
+	return mem;
+}
+
+void *kalloc_block(size_t size, struct page_header *block) {
+	struct page_header *header =
+		(struct page_header *) ((char *) block + block->used + header_len);
+
+	size_t free = block->free - (size + header_len);
+	block->free = 0;
+
+	header->magic = MAGIC;
+	header->used = size;
+	header->free = free;
+	header->prev = block;
+	header->next = block->next;
+	block->next = header;
+	header->node_number = block->node_number;
+
+	void *mem = (char *) header + header_len;
+
+	return mem;
+}
+
+void *kalloc(size_t size) {
+	struct page_header *header = start_header;
+
+	for (; header != NULL; header = header->next) {
+		size_t free = header->free;
+		if (size <= (free - header_len)) { // we must be able to fit data + header
+			break;
+		}
+	}
+
+	if (header != NULL) {
+		return kalloc_block(size, header);
+	} else {
+		return kalloc_new(size);
+	}
+}
+
+void *krealloc(void *src, size_t dst_len) {
+	struct page_header *header;
+	size_t src_len;
+	void *dst;
+
+	// realloc of 0 means free pointer
+	if (dst_len == 0) {
+		kfree(src);
+		return NULL;
+	}
+
+	// NULL src means allocate ptr
+	if (src == NULL) {
+		dst = kalloc(dst_len);
+		return dst;
+	}
+
+	header = get_header(src);
+
+	if (header == NULL) {
+#ifdef MEMORY_PANIC
+		panic("attempted to realloc on a invalid ptr");
+#else
+		return NULL; // invalid pointer passed
+#endif
+	}
+
+	src_len = header->used;
+
+	if (src_len == 0) {
+#ifdef MEMORY_PANIC
+		panic("attempted to realloc on an empty ptr");
+#else
+		return NULL; // likely double free :(
+#endif
+	}
+
+	dst = kalloc(dst_len);
+
+	if (dst == NULL) {
+		return NULL; // allocation failed
+	}
+
+	memcpy(dst, src, src_len);
+	return dst;
+}
+
+void kfree(void *ptr) {
+	struct page_header *header;
+
+	if (ptr == NULL) {
+		return;
+	}
+
+	header = get_header(ptr);
+
+	if (header == NULL || header->used == 0) {
+#ifdef MEMORY_PANIC
+		panic("attempted to kfree invalid pointer");
+#else
+		return;
+#endif
+	}
+
+	header->free += header->used;
+	header->used = 0;
+
+	struct page_header *neighbor;
+
+	// merge left
+	for (neighbor = header->prev; neighbor != NULL; neighbor = neighbor->prev) {
+		if (neighbor->node_number != header->node_number)
+			break;
+		if (neighbor->used && header->used)
+			break;
+		neighbor->free += header->free + header_len;
+		neighbor->next = header->next;
+		header = neighbor;
+	}
+
+	// merge right
+	for (neighbor = header->next; neighbor != NULL; neighbor = neighbor->next) {
+		if (neighbor->node_number != header->node_number)
+			break;
+		if (neighbor->used)
+			break;
+		header->free += neighbor->free + header_len;
+		header->next = neighbor->next;
+	}
+
+	if (
+			(header->next == NULL || header->next->node_number != header->node_number) &&
+			(header->prev == NULL || header->prev->node_number != header->node_number) &&
+			header->used == 0
+	) {
+		if (header->next)
+			header->next->prev = header->prev;
+		if (header->prev)
+			header->prev->next = header->next;
+		free_pages(header);
+	}
+
+}
diff --git a/src/memory/physalloc.c b/src/memory/physalloc.c
index dccd980..1140258 100644
--- a/src/memory/physalloc.c
+++ b/src/memory/physalloc.c
@@ -163,13 +163,11 @@ void memory_init(struct memory_map *map) {
 	page_free_start = 0;
 	page_start = NULL;
 
-	uintptr_t end = (uintptr_t) map;
-	end += map->size;
-
-	struct memory_segment *segment = &map->entries[0];
 	segment_count = 0;
-	
-	for(; (uintptr_t) segment < end; segment++) {
+
+	for(uint32_t i = 0; i < map->entry_count; i++) {
+		struct memory_segment *segment = &map->entries[i];
+
 		if (segment_invalid(segment))
 			continue;
 
@@ -189,16 +187,17 @@ void memory_init(struct memory_map *map) {
 	char *page_area_addr = (char *)bitmap + bitmap_size;
 	bitmap = mmap(bitmap, bitmap_size);
 	memset(bitmap, 0, bitmap_size);
-	
+
 	memory_start = page_align(kaddr(kernel_end) + bitmap_size + page_area_size);
 
 	page_area_addr = mmap(page_area_addr, page_area_size);
 	page_start = (struct memory_area *) page_area_addr;
-	
+
 	struct memory_area *area = page_start;
-	segment = &map->entries[0];
-	
-	for(; (uintptr_t) segment < end; segment++) {
+
+	for(uint32_t i = 0; i < map->entry_count; i++) {
+		struct memory_segment *segment = &map->entries[i];
+
 		if (segment_invalid(segment))
 			continue;
 
@@ -206,7 +205,7 @@ void memory_init(struct memory_map *map) {
 		*area = temp;
 		area++;
 	}
-	
+
 	page_count -= bitmap_pages;
 
 	memory_unlock();
@@ -229,24 +228,3 @@ uint64_t memory_used(void) {
 	return total_memory - free_memory;
 }
 
-// stubs
-// simon do these ik you want to
-// :3
-
-void *malloc(size_t size) {
-	//TODO: implement
-	(void)size;
-	return NULL;
-}
-
-void *realloc(void *ptr, size_t size) {
-	//TODO: implement
-	(void)ptr;
-	(void)size;
-	return NULL;
-}
-
-void free(void *ptr) {
-	//TODO: implement
-	(void)ptr;
-}
diff --git a/src/memory/virtalloc.c b/src/memory/virtalloc.c
index f8d8169..781fc9b 100644
--- a/src/memory/virtalloc.c
+++ b/src/memory/virtalloc.c
@@ -21,20 +21,23 @@ static struct addr_node nodes[BOOTSTRAP_BSS_NODES];
 static struct addr_node *start_node;
 
 static struct addr_node *alloc_node(void) {
+	struct addr_node *node = NULL;
 	if (bss_nodes >= BOOTSTRAP_BSS_NODES) {
-		//FIXME: alloc on heap
+		node = kalloc(sizeof(struct addr_node));
+		if (node == NULL)
+			return NULL;
+		node->is_bss = false;
 	} else {
-		struct addr_node *node = &nodes[bss_nodes];
+		node = &nodes[bss_nodes];
 		bss_nodes += 1;
 		node->is_bss = true;
-		return node;
 	}
-	return NULL;
+	return node;
 }
 
 static void free_node(struct addr_node *node) {
 	if (!node->is_bss)
-		free(node);
+		kfree(node);
 }
 
 void virtaddr_init(void) {
@@ -53,7 +56,6 @@ void virtaddr_init(void) {
 
 void *virtaddr_alloc(int n_pages) {
 
-
 	if (n_pages < 1)
 		return NULL;
 
@@ -84,7 +86,7 @@ void *virtaddr_alloc(int n_pages) {
 			return (void *) new->start;
 		}
 	}
-	
+
 	return NULL;
 }
 
@@ -121,7 +123,7 @@ long virtaddr_free(void *virtaddr) {
 	for (; node != NULL; node = node->next) {
 		if (node->start == virt) {
 			int length = node->end - node->start;
-			int pages = length / PAGE_SIZE; 
+			int pages = length / PAGE_SIZE;
 			merge_back(node);
 			merge_forward(node);
 			return pages;