Implement userspace malloc

16 files changed, 561 insertions, 27 deletions

diff --git a/.vimrc b/.vimrc
index fcdeb47..4d9095b 100644
--- a/.vimrc
+++ b/.vimrc
@@ -10,5 +10,5 @@ let g:syntastic_check_on_open = 1
 let g:syntastic_check_on_wq = 0
 
 let g:syntastic_c_gcc_exec = 'i586-elf-gcc'
-let g:syntastic_c_include_dirs = [ 'src/kernel/include', 'src/kernel', 'src/common/include', 'src/lib/include' ]
+let g:syntastic_c_include_dirs = [ 'src/kernel/include', 'src/common/include', 'src/lib/include' ]
 let g:syntastic_c_compiler_options = '-ffreestanding -Wall -Wextra -std=gnu99 -Wno-unused-parameter'
diff --git a/README.md b/README.md
index 6b5a3df..81ca3e4 100644
--- a/README.md
+++ b/README.md
@@ -97,7 +97,7 @@ running the tests):
 * Implement syscalls
 * Write device drivers : VGA, keyboard, ATA, FAT, VESA
 
-### Important TODOs not to overlook
+### Things to design
 
 * How does a process exit, what does it do, how do processes synchronize ?
 * Timers, workers, sleeping
diff --git a/src/apps/init/main.c b/src/apps/init/main.c
index 0defd13..25f08e8 100644
--- a/src/apps/init/main.c
+++ b/src/apps/init/main.c
@@ -1,11 +1,37 @@
 #include <string.h>
 
+#include <malloc.h>
+
 #include <syscall.h>
 #include <debug.h>
+#include <user_region.h>
 
 int main(int argc, char **argv) {
 	dbg_print("Hello, world! from user process.\n");
 
+	dbg_print_region_info();
+
+	dbg_printf("Doing malloc test...\n");
+	const int m = 200;
+	uint16_t** ptr = malloc(m * sizeof(uint32_t));
+	for (int i = 0; i < m; i++) {
+		size_t s = 1 << ((i * 7) % 11 + 2);
+		ptr[i] = (uint16_t*)malloc(s);
+		ASSERT((size_t)ptr[i] >= 0x40000000 && (size_t)ptr[i] < 0xB0000000);
+		*ptr[i] = ((i * 211) % 1024);
+	}
+	dbg_printf("Fully allocated.\n");
+	dbg_print_region_info();
+	for (int i = 0; i < m; i++) {
+		for (int j = i; j < m; j++) {
+			ASSERT(*ptr[j] == (j * 211) % 1024);
+		}
+		free(ptr[i]);
+	}
+	free(ptr);
+	dbg_printf("malloc test OK.\n");
+	dbg_print_region_info();
+
 	return 0;
 }
 
diff --git a/src/apps/linker.ld b/src/apps/linker.ld
index 0c84ecf..50bebbe 100644
--- a/src/apps/linker.ld
+++ b/src/apps/linker.ld
@@ -19,6 +19,7 @@ SECTIONS{
 		*(.dtor*)
 		end_dtors = .;
         *(.data)
+		*(.locks)
     }
  
     .bss : {
diff --git a/src/common/include/mmap.h b/src/common/include/mmap.h
new file mode 100644
index 0000000..777950f
--- /dev/null
+++ b/src/common/include/mmap.h
@@ -0,0 +1,6 @@
+#pragma once
+
+#define MM_READ			(0x01)
+#define MM_WRITE		(0x02)
+#define MM_EXEC			(0x04)
+
diff --git a/src/kernel/include/process.h b/src/kernel/include/process.h
index edb25c3..5d9c3bf 100644
--- a/src/kernel/include/process.h
+++ b/src/kernel/include/process.h
@@ -16,11 +16,8 @@
 #include <thread.h>
 #include <vfs.h>
 
+#include <mmap.h>
 
-// Modes for mmaping regions
-#define MM_READ		(0x01)
-#define MM_WRITE	(0x02)
-#define MM_EXEC		(0x04)
 
 #define USERSTACK_ADDR	0xB8000000
 #define USERSTACK_SIZE	0x00020000		// 32 KB
diff --git a/src/kernel/user/process.c b/src/kernel/user/process.c
index fc608a7..6cba0f7 100644
--- a/src/kernel/user/process.c
+++ b/src/kernel/user/process.c
@@ -151,7 +151,8 @@ bool mmap(process_t *proc, void* addr, size_t size, int mode) {
 	r->addr = addr;
 	r->size = PAGE_ALIGN_UP(size);
 
-	if (r->addr >= (void*)K_HIGHHALF_ADDR || r->addr + r->size > (void*)K_HIGHHALF_ADDR || r->size == 0) {
+	if (r->addr >= (void*)K_HIGHHALF_ADDR || r->addr + r->size > (void*)K_HIGHHALF_ADDR
+		|| r->addr + r->size <= r->addr || r->size == 0) {
 		free(r);
 		return false;
 	}
@@ -187,7 +188,8 @@ bool mmap_file(process_t *proc, fs_handle_t *h, size_t offset, void* addr, size_
 	r->addr = addr;
 	r->size = PAGE_ALIGN_UP(size);
 
-	if (r->addr >= (void*)K_HIGHHALF_ADDR || r->addr + r->size > (void*)K_HIGHHALF_ADDR || r->size == 0) {
+	if (r->addr >= (void*)K_HIGHHALF_ADDR || r->addr + r->size > (void*)K_HIGHHALF_ADDR
+		|| r->addr + r->size <= r->addr || r->size == 0) {
 		free(r);
 		return false;
 	}
@@ -257,7 +259,7 @@ bool munmap(process_t *proc, void* addr) {
 	// Unmap that stuff
 	pagedir_t *save_pd = get_current_pagedir();
 	switch_pagedir(proc->pd);
-	for (void* it = r->addr; it < r->addr + r->size; r += PAGE_SIZE) {
+	for (void* it = r->addr; it < r->addr + r->size; it += PAGE_SIZE) {
 		uint32_t ent = pd_get_entry(it);
 		uint32_t frame = pd_get_frame(it);
 
@@ -293,6 +295,7 @@ static void proc_usermem_pf(void* p, registers_t *regs, void* addr) {
 	user_region_t *r = find_user_region(proc, addr);
 	if (r == 0) {
 		dbg_printf("Segmentation fault in process %d (0x%p : not mapped) : exiting.\n", proc->pid, addr);
+		dbg_dump_registers(regs);
 		exit();
 	}
 
diff --git a/src/kernel/user/syscall.c b/src/kernel/user/syscall.c
index 26032ad..ca5a65c 100644
--- a/src/kernel/user/syscall.c
+++ b/src/kernel/user/syscall.c
@@ -4,7 +4,11 @@
 
 #include <syscall.h>
 
-typedef uint32_t (*syscall_handler_t)(uint32_t, uint32_t, uint32_t, uint32_t, uint32_t);
+typedef struct {
+	uint32_t sc_id, a, b, c, d, e;		// a: ebx, b: ecx, c: edx, d: esi, e: edi
+} sc_args_t;
+
+typedef uint32_t (*syscall_handler_t)(sc_args_t);
 
 static syscall_handler_t sc_handlers[SC_MAX] = { 0 };
 
@@ -25,21 +29,22 @@ static char* sc_copy_string(uint32_t s, uint32_t slen) {
 // THE SYSCALLS CODE !! //
 // ==================== //
 
-static uint32_t exit_sc(uint32_t code, uint32_t uu1, uint32_t uu2, uint32_t uu3, uint32_t uu4) {
-	dbg_printf("Proc %d exit with code %d\n", current_process()->pid, code);
+
+static uint32_t exit_sc(sc_args_t args) {
+	dbg_printf("Proc %d exit with code %d\n", current_process()->pid, args.a);
 	// TODO : use code... and process exiting is not supposed to be done this way
 
 	exit();
 	return 0;
 }
 
-static uint32_t yield_sc() {
+static uint32_t yield_sc(sc_args_t args) {
 	yield();
 	return 0;
 }
 
-static uint32_t dbg_print_sc(uint32_t s, uint32_t slen, uint32_t uu2, uint32_t uu3, uint32_t uu4) {
-	char* msg = sc_copy_string(s, slen);
+static uint32_t dbg_print_sc(sc_args_t args) {
+	char* msg = sc_copy_string(args.a, args.b);
 	if (msg == 0) return -1;
 
 	dbg_print(msg);
@@ -48,6 +53,18 @@ static uint32_t dbg_print_sc(uint32_t s, uint32_t slen, uint32_t uu2, uint32_t u
 	return 0;
 }
 
+static uint32_t mmap_sc(sc_args_t args) {
+	return mmap(current_process(), (void*)args.a, args.b, args.c);
+}
+
+static uint32_t mchmap_sc(sc_args_t args) {
+	return mchmap(current_process(), (void*)args.a, args.b);
+}
+
+static uint32_t munmap_sc(sc_args_t args) {
+	return munmap(current_process(), (void*)args.a);
+}
+
 // ====================== //
 // SYSCALLS SETUP ROUTINE //
 // ====================== //
@@ -56,6 +73,10 @@ void setup_syscalls() {
 	sc_handlers[SC_EXIT] = exit_sc;
 	sc_handlers[SC_YIELD] = yield_sc;
 	sc_handlers[SC_DBG_PRINT] = dbg_print_sc;
+
+	sc_handlers[SC_MMAP] = mmap_sc;
+	sc_handlers[SC_MCHMAP] = mchmap_sc;
+	sc_handlers[SC_MUNMAP] = munmap_sc;
 }
 
 void syscall_handler(registers_t *regs) {
@@ -64,7 +85,13 @@ void syscall_handler(registers_t *regs) {
 	if (regs->eax < SC_MAX) {
 		syscall_handler_t h = sc_handlers[regs->eax];
 		if (h != 0) {
-			regs->eax = h(regs->ebx, regs->ecx, regs->edx, regs->esi, regs->edi);
+			sc_args_t args = {
+				.a = regs->ebx,
+				.b = regs->ecx,
+				.c = regs->edx,
+				.d = regs->esi,
+				.e = regs->edi};
+			regs->eax = h(args);
 		} else {
 			regs->eax = -1;
 		}
diff --git a/src/lib/include/syscall.h b/src/lib/include/syscall.h
index 44b88cf..e0f08eb 100644
--- a/src/lib/include/syscall.h
+++ b/src/lib/include/syscall.h
@@ -5,6 +5,7 @@
 #include <stdbool.h>
 
 #include <syscallproto.h>
+#include <mmap.h>
 
 #include <fs.h>
 #include <debug.h>
@@ -13,6 +14,10 @@ void dbg_print(const char* str);
 void yield();
 void exit(int code);
 
+bool mmap(void* addr, size_t size, int mode);
+bool mchmap(void* addr, int mode);
+bool munmap(void* addr);
+
 // more todo
 
 /* vim: set ts=4 sw=4 tw=0 noet :*/
diff --git a/src/lib/include/user_region.h b/src/lib/include/user_region.h
new file mode 100644
index 0000000..8a4c490
--- /dev/null
+++ b/src/lib/include/user_region.h
@@ -0,0 +1,34 @@
+#pragma once
+
+// User virtual memory region allocator
+
+// This is entirely thread-safe
+
+#include <stdint.h>
+#include <stddef.h>
+#include <stdbool.h>
+
+#include <syscall.h>
+
+#define PAGE_SIZE		0x1000
+#define PAGE_MASK		0xFFFFF000
+#define PAGE_ALIGN_DOWN(x)	(((size_t)x) & PAGE_MASK) 
+#define PAGE_ALIGN_UP(x)  	((((size_t)x)&(~PAGE_MASK)) == 0 ? ((size_t)x) : (((size_t)x) & PAGE_MASK) + PAGE_SIZE)
+
+struct region_info;
+
+typedef struct region_info {
+	void* addr;
+	size_t size;
+	char* type;
+} region_info_t;
+
+void region_allocator_init(void* begin, void* end);
+
+void* region_alloc(size_t size, char* type);	// returns 0 on error
+region_info_t *find_region(void* addr);
+void region_free(void* addr);
+
+void dbg_print_region_info();
+
+/* vim: set ts=4 sw=4 tw=0 noet :*/
diff --git a/src/lib/libkogata/Makefile b/src/lib/libkogata/Makefile
index 2649e25..ee00fa3 100644
--- a/src/lib/libkogata/Makefile
+++ b/src/lib/libkogata/Makefile
@@ -1,4 +1,4 @@
-OBJ = start.o malloc.o debug.o syscall.o
+OBJ = start.o malloc.o debug.o syscall.o user_region.o
 
 LIB = ../../common/libkogata/libkogata.lib
 
diff --git a/src/lib/libkogata/debug.c b/src/lib/libkogata/debug.c
index 9688877..a8b9414 100644
--- a/src/lib/libkogata/debug.c
+++ b/src/lib/libkogata/debug.c
@@ -2,13 +2,17 @@
 
 #include <debug.h>
 
+#include <syscall.h>
+
 void panic(const char* msg, const char* file, int line) {
-	// TODO
+	dbg_printf("Panic '%s', at %s:%d\n", msg, file, line);
+	exit(-1);
 	while(true);
 }
 
 void panic_assert(const char* assert, const char* file, int line) {
-	// TODO
+	dbg_printf("Assert failed '%s', at %s:%d\n", assert, file, line);
+	exit(-1);
 	while(true);
 }
 
diff --git a/src/lib/libkogata/malloc.c b/src/lib/libkogata/malloc.c
index 272dd7d..56a5397 100644
--- a/src/lib/libkogata/malloc.c
+++ b/src/lib/libkogata/malloc.c
@@ -1,12 +1,56 @@
 #include <malloc.h>
+#include <slab_alloc.h>
+
+#include <syscall.h>
+#include <user_region.h>
+
+static void* heap_alloc_pages(size_t s) {
+	void* addr = region_alloc(s, "Heap");
+	if (addr == 0) return 0;
+
+	bool map_ok = mmap(addr, s, FM_READ | FM_WRITE);
+	if (!map_ok) {
+		region_free(addr);
+		return 0;
+	}
+
+	return addr;
+}
+
+static void heap_free_pages(void* addr) {
+	munmap(addr);
+	region_free(addr);
+}
+
+static mem_allocator_t *mem_allocator;
+static slab_type_t slab_sizes[] = {
+	{ "8B malloc objects", 8, 2 },
+	{ "16B malloc objects", 16, 2 },
+	{ "32B malloc objects", 32, 2 },
+	{ "64B malloc objects", 64, 4 },
+	{ "128B malloc objects", 128, 4 },
+	{ "256B malloc objects", 256, 4 },
+	{ "512B malloc objects", 512, 8 },
+	{ "1KB malloc objects", 1024, 8 },
+	{ "2KB malloc objects", 2048, 16 },
+	{ "4KB malloc objects", 4096, 16 },
+	{ 0, 0, 0 }
+};
+
+void malloc_setup() {
+	region_allocator_init((void*)0x40000000, (void*)0xB0000000);
+
+	mem_allocator = create_slab_allocator(slab_sizes, heap_alloc_pages, heap_free_pages);
+
+	ASSERT(mem_allocator != 0);
+}
 
 void* malloc(size_t size) {
-	// TODO
-	return 0;
+	return slab_alloc(mem_allocator, size);
 }
 
 void free(void* ptr) {
-	// TODO
+	slab_free(mem_allocator, ptr);
 }
 
 /* vim: set ts=4 sw=4 tw=0 noet :*/
diff --git a/src/lib/libkogata/start.c b/src/lib/libkogata/start.c
index 984a3cd..bd22d7a 100644
--- a/src/lib/libkogata/start.c
+++ b/src/lib/libkogata/start.c
@@ -1,9 +1,13 @@
 #include <syscall.h>
 
-extern int main(int, char**);
+void malloc_setup();
+
+int main(int, char**);
 
 void __libkogata_start() {
-	// TODO : setup
+	malloc_setup();
+
+	// TODO : more setup ?
 
 	int ret = main(0, 0);
 
diff --git a/src/lib/libkogata/syscall.c b/src/lib/libkogata/syscall.c
index b9cefa7..8d24628 100644
--- a/src/lib/libkogata/syscall.c
+++ b/src/lib/libkogata/syscall.c
@@ -2,17 +2,47 @@
 #include <syscall.h>
 
 #include <string.h>
+#include <printf.h>
+
+static uint32_t call(uint32_t a, uint32_t b, uint32_t c, uint32_t d, uint32_t ss, uint32_t dd) {
+	uint32_t ret;
+	asm volatile("int $0x40"
+		:"=a"(ret)
+		:"a"(a),"b"(b),"c"(c),"d"(d),"S"(ss),"D"(dd));
+	return ret;
+}
 
 void dbg_print(const char* str) {
-	asm volatile("int $0x40"::"a"(SC_DBG_PRINT),"b"(str),"c"(strlen(str)));
+	call(SC_DBG_PRINT, (uint32_t)str, strlen(str), 0, 0, 0);
+}
+
+void dbg_printf(const char* fmt, ...) {
+	va_list ap;
+	char buffer[256];
+
+	va_start(ap, fmt);
+	vsnprintf(buffer, 256, fmt, ap);
+	va_end(ap);
+
+	dbg_print(buffer);
 }
 
 void yield() {
-	asm volatile("int $0x40"::"a"(SC_YIELD));
+	call(SC_YIELD, 0, 0, 0, 0, 0);
 }
 
 void exit(int code) {
-	asm volatile("int $0x40"::"a"(SC_EXIT),"b"(code));
+	call(SC_EXIT, code, 0, 0, 0, 0);
+}
+
+bool mmap(void* addr, size_t size, int mode) {
+	return call(SC_MMAP, (uint32_t)addr, size, mode, 0, 0);
+}
+bool mchmap(void* addr, int mode) {
+	return call(SC_MCHMAP, (uint32_t)addr, mode, 0, 0, 0);
+}
+bool munmap(void* addr) {
+	return call(SC_MUNMAP, (uint32_t)addr, 0, 0, 0, 0);
 }
 
 /* vim: set ts=4 sw=4 tw=0 noet :*/
diff --git a/src/lib/libkogata/user_region.c b/src/lib/libkogata/user_region.c
new file mode 100644
index 0000000..516259b
--- /dev/null
+++ b/src/lib/libkogata/user_region.c
@@ -0,0 +1,353 @@
+#include <user_region.h>
+#include <debug.h>
+#include <mutex.h>
+
+#include <syscall.h>
+
+typedef union region_descriptor {
+	struct {
+		union region_descriptor *next;
+	} unused_descriptor;
+	struct {
+		void* addr;
+		size_t size;
+		union region_descriptor *next_by_size, *first_bigger;
+		union region_descriptor *next_by_addr;
+	} free;
+	struct {
+		region_info_t i;
+		union region_descriptor *next_by_addr;
+	} used;
+} descriptor_t;
+
+#define N_RESERVE_DESCRIPTORS 2		// always keep at least 2 unused descriptors
+
+#define N_BASE_DESCRIPTORS 12		// pre-allocate memory for 12 descriptors
+static descriptor_t base_descriptors[N_BASE_DESCRIPTORS];
+
+static descriptor_t *first_unused_descriptor; 
+uint32_t n_unused_descriptors;
+static descriptor_t *first_free_region_by_addr, *first_free_region_by_size;
+static descriptor_t *first_used_region;
+
+STATIC_MUTEX(ra_mutex);	// region allocator mutex
+
+// ========================================================= //
+// HELPER FUNCTIONS FOR THE MANIPULATION OF THE REGION LISTS //
+// ========================================================= //
+
+static void add_unused_descriptor(descriptor_t *d) {
+	n_unused_descriptors++;
+	d->unused_descriptor.next = first_unused_descriptor;
+	first_unused_descriptor = d;
+}
+
+static descriptor_t *get_unused_descriptor() {
+	descriptor_t *r = first_unused_descriptor;
+	if (r != 0) {
+		first_unused_descriptor = r->unused_descriptor.next;
+		n_unused_descriptors--;
+	}
+	return r;
+}
+
+static void remove_free_region(descriptor_t *d) {
+	if (first_free_region_by_size == d) {
+		first_free_region_by_size = d->free.next_by_size;
+	} else {
+		for (descriptor_t *i = first_free_region_by_size; i != 0; i = i->free.next_by_size) {
+			if (i->free.next_by_size == d) {
+				i->free.next_by_size = d->free.next_by_size;
+				break;
+			}
+		}
+	}
+	if (first_free_region_by_addr == d) {
+		first_free_region_by_addr = d->free.next_by_addr;
+	} else {
+		for (descriptor_t *i = first_free_region_by_addr; i != 0; i = i->free.next_by_addr) {
+			if (i->free.next_by_addr == d) {
+				i->free.next_by_addr = d->free.next_by_addr;
+				break;
+			}
+		}
+	}
+}
+
+static void add_free_region(descriptor_t *d) {
+	/*dbg_printf("Add free region 0x%p - 0x%p\n", d->free.addr, d->free.size + d->free.addr);*/
+	// Find position of region in address-ordered list
+	// Possibly concatenate free region
+	descriptor_t *i = first_free_region_by_addr;
+	if (i == 0) {
+		ASSERT(first_free_region_by_size == 0);
+		first_free_region_by_addr = first_free_region_by_size = d;
+		d->free.next_by_size = d->free.first_bigger = d->free.next_by_addr = 0;
+		return;
+	} else if (d->free.addr + d->free.size == i->free.addr) {
+		// concatenate d . i
+		remove_free_region(i);
+		d->free.size += i->free.size;
+		add_unused_descriptor(i);
+		add_free_region(d);
+		return;
+	} else if (i->free.addr > d->free.addr) {
+		// insert before i
+		d->free.next_by_addr = i;
+		first_free_region_by_addr = d;
+	} else {
+		while (i != 0) {
+			ASSERT(d->free.addr > i->free.addr);
+			if (i->free.addr + i->free.size == d->free.addr) {
+				// concatenate i . d
+				remove_free_region(i);
+				i->free.size += d->free.size;
+				add_unused_descriptor(d);
+				add_free_region(i);
+				return;
+			} else if (i->free.next_by_addr == 0 || i->free.next_by_addr->free.addr > d->free.addr) {
+				d->free.next_by_addr = i->free.next_by_addr;
+				i->free.next_by_addr = d;
+				break;
+			} else if (d->free.addr + d->free.size == i->free.next_by_addr->free.addr) {
+				// concatenate d . i->next_by_addr
+				descriptor_t *j = i->free.next_by_addr;
+				remove_free_region(j);
+				d->free.size += j->free.size;
+				add_unused_descriptor(j);
+				add_free_region(d);
+				return;
+			} else {
+				// continue
+				i = i->free.next_by_addr;
+			}
+		}
+	}
+	// Now add it in size-ordered list
+	i = first_free_region_by_size;
+	ASSERT(i != 0);
+	if (d->free.size <= i->free.size) {
+		d->free.next_by_size = i;
+		d->free.first_bigger = (i->free.size > d->free.size ? i : i->free.first_bigger);
+		first_free_region_by_size = d;
+	} else {
+		while (i != 0) {
+			ASSERT(d->free.size > i->free.size);
+			if (i->free.next_by_size == 0) {
+				d->free.next_by_size = 0;
+				d->free.first_bigger = 0;
+				i->free.next_by_size = d;
+				if (d->free.size > i->free.size) i->free.first_bigger = d;
+				break;
+			} else if (i->free.next_by_size->free.size >= d->free.size) {
+				d->free.next_by_size = i->free.next_by_size;
+				d->free.first_bigger =
+					(i->free.next_by_size->free.size > d->free.size
+						? i->free.next_by_size
+						: i->free.next_by_size->free.first_bigger);
+				i->free.next_by_size = d;
+				if (d->free.size > i->free.size) i->free.first_bigger = d;
+				break;
+			} else {
+				// continue
+				i = i->free.next_by_size;
+			}
+		}
+	}
+}
+
+static descriptor_t *find_used_region(void* addr) {
+	for (descriptor_t *i = first_used_region; i != 0; i = i->used.next_by_addr) {
+		if (addr >= i->used.i.addr && addr < i->used.i.addr + i->used.i.size) return i;
+		if (i->used.i.addr > addr) break;
+	}
+	return 0;
+}
+
+static void add_used_region(descriptor_t *d) {
+	if (first_used_region == 0 || d->used.i.addr < first_used_region->used.i.addr) {
+		d->used.next_by_addr = first_used_region;
+		first_used_region = d;
+	} else {
+		descriptor_t *i = first_used_region;
+		ASSERT(i->used.i.addr < d->used.i.addr);	// first region by address is never free
+
+		while (i != 0) {
+			ASSERT(i->used.i.addr < d->used.i.addr);
+			if (i->used.next_by_addr == 0 || i->used.next_by_addr->used.i.addr > d->used.i.addr) {
+				d->used.next_by_addr = i->used.next_by_addr;
+				i->used.next_by_addr = d;
+				return;
+			} else {
+				i = i->used.next_by_addr;
+			}
+		}
+		ASSERT(false);
+	}
+}
+
+static void remove_used_region(descriptor_t *d) {
+	if (first_used_region == d) {
+		first_used_region = d->used.next_by_addr;
+	} else {
+		for (descriptor_t *i = first_used_region; i != 0; i = i->used.next_by_addr) {
+			if (i->used.i.addr > d->used.i.addr) break;
+			if (i->used.next_by_addr == d) {
+				i->used.next_by_addr = d->used.next_by_addr;
+				break;
+			}
+		}
+	}
+}
+
+// =============== //
+// THE ACTUAL CODE //
+// =============== //
+
+void region_allocator_init(void* begin, void* end) {
+	n_unused_descriptors = 0;
+	first_unused_descriptor = 0;
+	for (int i = 0; i < N_BASE_DESCRIPTORS; i++) {
+		add_unused_descriptor(&base_descriptors[i]);
+	}
+
+	descriptor_t *f0 = get_unused_descriptor();
+	f0->free.addr = (void*)PAGE_ALIGN_UP(begin);
+	f0->free.size = ((void*)PAGE_ALIGN_DOWN(end) - f0->free.addr);
+	f0->free.next_by_size = 0;
+	f0->free.first_bigger = 0;
+	first_free_region_by_size = first_free_region_by_addr = f0;
+
+	first_used_region = 0;
+}
+
+static void region_free_inner(void* addr) {
+	descriptor_t *d = find_used_region(addr);
+	if (d == 0) return;
+
+	region_info_t i = d->used.i;
+
+	remove_used_region(d);
+	d->free.addr = i.addr;
+	d->free.size = i.size;
+	add_free_region(d);
+}
+void region_free(void* addr) {
+	mutex_lock(&ra_mutex);
+	region_free_inner(addr);
+	mutex_unlock(&ra_mutex);
+}
+
+static void* region_alloc_inner(size_t size, char* type, bool use_reserve) {
+	size = PAGE_ALIGN_UP(size);
+
+	for (descriptor_t *i = first_free_region_by_size; i != 0; i = i->free.first_bigger) {
+		if (i->free.size >= size) {
+			// region i is the one we want to allocate in
+			descriptor_t *x = 0;
+			if (i->free.size > size) {
+				if (n_unused_descriptors <= N_RESERVE_DESCRIPTORS && !use_reserve) {
+					return 0;
+				}
+
+				// this assert basically means that the allocation function
+				// is called less than N_RESERVE_DESCRIPTORS times with
+				// the use_reserve flag before more descriptors
+				// are allocated.
+				x = get_unused_descriptor();
+				ASSERT(x != 0);
+
+				x->free.size = i->free.size - size;
+				if (size >= 0x4000) {
+					x->free.addr = i->free.addr + size;
+				} else {
+					x->free.addr = i->free.addr;
+					i->free.addr += x->free.size;
+				}
+			}
+			// do the allocation
+			remove_free_region(i);
+			if (x != 0) add_free_region(x);
+
+			void* addr = i->free.addr;
+			i->used.i.addr = addr;
+			i->used.i.size = size;
+			i->used.i.type = type;
+			add_used_region(i);
+
+			return addr;
+		}
+	}
+	return 0;	//No big enough block found
+}
+
+void* region_alloc(size_t size, char* type) {
+	void* result = 0;
+	mutex_lock(&ra_mutex);
+
+	if (n_unused_descriptors <= N_RESERVE_DESCRIPTORS) {
+		void* descriptor_region = region_alloc_inner(PAGE_SIZE, "Region descriptors", true);
+		ASSERT(descriptor_region != 0);
+
+		bool map_ok = mmap(descriptor_region, PAGE_SIZE, MM_READ | MM_WRITE);
+		if (!map_ok) {
+			// this can happen if we weren't able to mmap the region (for whatever reason)
+			region_free_inner(descriptor_region);
+			goto try_anyway;
+		}
+		
+		for (descriptor_t *d = (descriptor_t*)descriptor_region;
+				(void*)(d+1) <= (descriptor_region + PAGE_SIZE);
+				d++) {
+			add_unused_descriptor(d);
+		}
+	}
+	try_anyway:
+	// even if we don't have enough unused descriptors, we might find
+	// a free region that has exactly the right size and therefore
+	// does not require splitting, so we try the allocation in all cases
+	result = region_alloc_inner(size, type, false);
+
+	mutex_unlock(&ra_mutex);
+	return result;
+}
+
+region_info_t *find_region(void* addr) {
+	region_info_t *r = 0;
+	mutex_lock(&ra_mutex);
+
+	descriptor_t *d = find_used_region(addr);
+	if (d != 0) r = &d->used.i;
+
+	mutex_unlock(&ra_mutex);
+	return r;
+}
+
+// =========================== //
+// DEBUG LOG PRINTING FUNCTION //
+// =========================== //
+
+void dbg_print_region_info() {
+	mutex_lock(&ra_mutex);
+
+	dbg_printf("/ Free process regions, by address:\n");
+	for (descriptor_t *d = first_free_region_by_addr; d != 0; d = d->free.next_by_addr) {
+		dbg_printf("| 0x%p - 0x%p\n", d->free.addr, d->free.addr + d->free.size);
+		ASSERT(d != d->free.next_by_addr);
+	}
+	dbg_printf("- Free process regions, by size:\n");
+	for (descriptor_t *d = first_free_region_by_size; d != 0; d = d->free.next_by_size) {
+		dbg_printf("| 0x%p - 0x%p\n", d->free.addr, d->free.addr + d->free.size);
+		ASSERT(d != d->free.next_by_size);
+	}
+	dbg_printf("- Used process regions:\n");
+	for (descriptor_t *d = first_used_region; d != 0; d = d->used.next_by_addr) {
+		dbg_printf("| 0x%p - 0x%p  %s\n", d->used.i.addr, d->used.i.addr + d->used.i.size, d->used.i.type);
+		ASSERT(d != d->used.next_by_addr);
+	}
+	dbg_printf("\\\n");
+
+	mutex_unlock(&ra_mutex);
+}
+
+/* vim: set ts=4 sw=4 tw=0 noet :*/