kernel: basic page allocator, `process_free`

8 files changed, 118 insertions, 15 deletions

diff --git a/src/kernel/arch/generic.h b/src/kernel/arch/generic.h
index 01a3826..84be937 100644
--- a/src/kernel/arch/generic.h
+++ b/src/kernel/arch/generic.h
@@ -27,6 +27,8 @@ _Noreturn void sysexit(struct registers);
 // all of those can allocate memory
 struct pagedir *pagedir_new(void);
 struct pagedir *pagedir_copy(const struct pagedir *orig);
+
+void pagedir_free(struct pagedir *);
 void pagedir_map(struct pagedir *dir, void __user *virt, void *phys,
                  bool user, bool writeable);
 
diff --git a/src/kernel/arch/i386/boot.c b/src/kernel/arch/i386/boot.c
index c25a848..a2b4f01 100644
--- a/src/kernel/arch/i386/boot.c
+++ b/src/kernel/arch/i386/boot.c
@@ -32,5 +32,7 @@ void kmain_early(struct multiboot_info *multiboot) {
 		info.init.size = module->end - module->start;
 	}
 
+	info.memtop = (void*) (multiboot->mem_upper * 1024);
+
 	kmain(info);
 }
diff --git a/src/kernel/arch/i386/multiboot.s b/src/kernel/arch/i386/multiboot.s
index 10702c6..62bc9fd 100644
--- a/src/kernel/arch/i386/multiboot.s
+++ b/src/kernel/arch/i386/multiboot.s
@@ -1,6 +1,7 @@
 .set MAGIC, 0x1BADB002
 
 /* 1<<0  - align modules on page boundaries.
+   1<<1  - fill the mem_ fields in multiboot_info
    1<<16 - enable manual addressing */
 .set FLAGS,        1<<0 | 1<<16
 .set CHECKSUM, -(MAGIC + FLAGS)
diff --git a/src/kernel/arch/i386/pagedir.c b/src/kernel/arch/i386/pagedir.c
index 88f6ebb..e3c2fa5 100644
--- a/src/kernel/arch/i386/pagedir.c
+++ b/src/kernel/arch/i386/pagedir.c
@@ -46,6 +46,29 @@ struct pagedir *pagedir_new(void) {
 	return dir;
 }
 
+void pagedir_free(struct pagedir *dir) {
+	// assumes all user pages are unique and can be freed
+	struct pagetable_entry *pt;
+	void *page;
+
+	for (int i = 0; i < 1024; i++) {
+		if (!dir->e[i].present) continue;
+		if (!dir->e[i].user)    continue;
+
+		pt = (void*)(dir->e[i].address << 11);
+
+		for (int j = 0; j < 1024; j++) {
+			if (!pt[j].present) continue;
+			if (!pt[j].user)    continue;
+
+			page = (void*)(pt[j].address << 11);
+			page_free(page, 1);
+		}
+		page_free(pt, 1);
+	}
+	page_free(dir, 1);
+}
+
 void pagedir_map(struct pagedir *dir, void __user *virt, void *phys,
                  bool user, bool writeable)
 {
diff --git a/src/kernel/main.h b/src/kernel/main.h
index f7f5f04..9c78786 100644
--- a/src/kernel/main.h
+++ b/src/kernel/main.h
@@ -6,6 +6,7 @@ struct kmain_info {
 		void *at;    // page aligned
 		size_t size;
 	} init; // a boot module loaded by GRUB, containing the initrd driver
+	void *memtop;
 };
 
 void kmain(struct kmain_info);
diff --git a/src/kernel/mem/alloc.c b/src/kernel/mem/alloc.c
index 132ab24..0495eca 100644
--- a/src/kernel/mem/alloc.c
+++ b/src/kernel/mem/alloc.c
@@ -1,22 +1,39 @@
 #include <kernel/arch/generic.h>
 #include <kernel/mem/alloc.h>
+#include <kernel/panic.h>
 #include <kernel/util.h>
+#include <shared/mem.h>
+#include <stdbool.h>
 #include <stdint.h>
 
 #define MALLOC_MAGIC 0xACAB1312
 
-static void *highest_page;
+static void *memtop;
+
+static uint8_t *page_bitmap;
+static void *page_bitmap_start;
+static size_t page_bitmap_len;
+
 static int malloc_balance = 0;
 
+static void *closest_page(void *p) {
+	return (void*)(((uintptr_t)p + PAGE_MASK) & ~PAGE_MASK);
+}
+
 void mem_init(struct kmain_info *info) {
-	// finds the highest used page, and starts allocating pages above it
-	void *highest = &_bss_end;
+	memtop = info->memtop;
 
-	if (highest < info->init.at + info->init.size)
-		highest = info->init.at + info->init.size;
+	/* place the page_bitmap right at the first free spot in memory */
+	page_bitmap = max((void*)&_bss_end, closest_page(info->init.at + info->init.size));
+	page_bitmap_len = ((uintptr_t)memtop - (uintptr_t)page_bitmap) / PAGE_SIZE / 8;
+	/* the page_bitmap_len calculation doesn't account for the space lost to itself,
+	 * so just take away a few pages to account for it. this could be solved with
+	 * actual math, but eh. */
+	page_bitmap_len -= 8;
+	memset(page_bitmap, 0, page_bitmap_len);
 
-	// align up to PAGE_SIZE
-	highest_page = (void*)(((uintptr_t)highest + PAGE_MASK) & ~PAGE_MASK);
+	/* start allocation on the page immediately following the page bitmap */
+	page_bitmap_start = closest_page(page_bitmap + page_bitmap_len);
 }
 
 void mem_debugprint(void) {
@@ -25,15 +42,47 @@ void mem_debugprint(void) {
 	tty_const(" ");
 }
 
+static bool bitmap_get(size_t i) {
+	size_t b = i / 8;
+	assert(b < page_bitmap_len);
+	return 0 < (page_bitmap[b] & (1 << (i&7)));
+}
+
+static void bitmap_set(size_t i, bool v) {
+	size_t b = i / 8;
+	uint8_t m = 1 << (i&7);
+	assert(b < page_bitmap_len);
+	if (v) page_bitmap[b] |=  m;
+	else   page_bitmap[b] &= ~m;
+}
+
 void *page_alloc(size_t pages) {
-	void *bottom = highest_page;
-	highest_page += pages * PAGE_SIZE;
-	return bottom;
+	/* i do realize how painfully slow this is */
+	size_t streak = 0;
+	for (size_t i = 0; i < page_bitmap_len * 8; i++) {
+		if (bitmap_get(i)) {
+			streak = 0;
+			continue;
+		}
+		if (++streak >= pages) {
+			/* found hole big enough for this allocation */
+			i = i + 1 - streak;
+			for (size_t j = 0; j < streak; j++)
+				bitmap_set(i + j, true);
+			return page_bitmap_start + i * PAGE_SIZE;
+		}
+	}
+	tty_const("we ran out of memory :(\ngoodbye.\n");
+	panic_unimplemented();
 }
 
 // frees `pages` consecutive pages starting from *first
-void page_free(void *first, size_t pages) {
-	// not implemented
+void page_free(void *first_addr, size_t pages) {
+	size_t first = (uintptr_t)(first_addr - page_bitmap_start) / PAGE_SIZE;
+	for (size_t i = 0; i < pages; i++) {
+		assert(bitmap_get(first + i));
+		bitmap_set(first + i, false);
+	}
 }
 
 
diff --git a/src/kernel/proc.c b/src/kernel/proc.c
index ca1b2ec..2f407c3 100644
--- a/src/kernel/proc.c
+++ b/src/kernel/proc.c
@@ -60,6 +60,27 @@ struct process *process_fork(struct process *parent) {
 	return child;
 }
 
+void process_free(struct process *p) {
+	assert(p->state == PS_DEADER);
+	pagedir_free(p->pages);
+	if (p->child) { // TODO
+		// panic_invalid_state();
+		return;
+	}
+	if (p->parent && p->parent->child == p) {
+		p->parent->child = p->sibling;
+	} else {
+		// this would be simpler if siblings were a doubly linked list
+		struct process *prev = p->parent->child;
+		while (prev->sibling != p) {
+			prev = prev->sibling;
+			assert(prev);
+		}
+		prev->sibling = p->sibling;
+	}
+	kfree(p);
+}
+
 void process_switch(struct process *proc) {
 	assert(proc->state == PS_RUNNING);
 	process_current = proc;
@@ -143,6 +164,7 @@ handle_t process_find_handle(struct process *proc) {
 }
 
 void process_kill(struct process *proc, int ret) {
+	// TODO kill children
 	proc->state = PS_DEAD;
 	proc->death_msg = ret;
 	process_try2collect(proc);
@@ -161,11 +183,13 @@ int process_try2collect(struct process *dead) {
 
 	switch (parent->state) {
 		case PS_WAITS4CHILDDEATH:
-			dead->state = PS_DEADER;
-			parent->state = PS_RUNNING;
-
 			ret = dead->death_msg;
 			regs_savereturn(&parent->regs, ret);
+			parent->state = PS_RUNNING;
+
+			dead->state = PS_DEADER;
+			process_free(dead);
+
 			return ret;
 
 		default:
diff --git a/src/kernel/proc.h b/src/kernel/proc.h
index 1d84b7f..eaa649a 100644
--- a/src/kernel/proc.h
+++ b/src/kernel/proc.h
@@ -58,6 +58,7 @@ extern struct process *process_current;
 // creates the root process
 struct process *process_seed(void);
 struct process *process_fork(struct process *parent);
+void process_free(struct process *);
 _Noreturn void process_switch(struct process *proc);
 _Noreturn void process_switch_any(void); // switches to any running process