Adjustments in region allocation code (fix first_bigger ??)

10 files changed, 77 insertions, 31 deletions

diff --git a/src/common/libkogata/region_alloc.c b/src/common/libkogata/region_alloc.c
index 8594643..96a0f07 100644
--- a/src/common/libkogata/region_alloc.c
+++ b/src/common/libkogata/region_alloc.c
@@ -10,7 +10,6 @@
 #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)
 
-
 typedef union region_descriptor {
 	struct {
 		union region_descriptor *next;
@@ -18,7 +17,8 @@ typedef union region_descriptor {
 	struct {
 		void* addr;
 		size_t size;
-		union region_descriptor *next_by_size, *first_bigger;
+		union region_descriptor *next_by_size;
+		union region_descriptor *first_bigger;
 		union region_descriptor *next_by_addr;
 	} free;
 	struct {
@@ -91,19 +91,30 @@ void add_free_region(descriptor_t *d) {
 	// Find position of region in address-ordered list
 	// Possibly concatenate free region
 	descriptor_t *i = first_free_region_by_addr;
+
 	if (i == 0) {
+		// we are the only free region, this is easy
 		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;
+		d->free.next_by_size = d->free.next_by_addr = 0;
+		d->free.first_bigger = 0;
+
 		return;
-	} else if (d->free.addr + d->free.size == i->free.addr) {
+	}
+	
+	if (d->free.addr + d->free.size == i->free.addr) {
 		// concatenate d . i
-		remove_free_region(i);
 		d->free.size += i->free.size;
+
+		remove_free_region(i);
 		add_unused_descriptor(i);
-		add_free_region(d);
+
+		add_free_region(d);	// restart from beginning
 		return;
-	} else if (i->free.addr > d->free.addr) {
+	}
+	
+	if (i->free.addr > d->free.addr) {
 		// insert before i
 		d->free.next_by_addr = i;
 		first_free_region_by_addr = d;
@@ -112,29 +123,37 @@ void add_free_region(descriptor_t *d) {
 			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;
+
+				remove_free_region(i);
 				add_unused_descriptor(d);
-				add_free_region(i);
+
+				add_free_region(i);	// restart from beginning
 				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;
+				// this is where we want to add
 				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;
+
+				remove_free_region(j);
 				add_unused_descriptor(j);
-				add_free_region(d);
+
+				add_free_region(d);	// restart from beginning
 				return;
 			} else {
 				// continue
 				i = i->free.next_by_addr;
 			}
 		}
+
+		d->free.next_by_addr = i->free.next_by_addr;
+		i->free.next_by_addr = d;
 	}
+
 	// Now add it in size-ordered list
 	i = first_free_region_by_size;
 	ASSERT(i != 0);
@@ -148,8 +167,9 @@ void add_free_region(descriptor_t *d) {
 			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;
+				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;
@@ -161,11 +181,25 @@ void add_free_region(descriptor_t *d) {
 				if (d->free.size > i->free.size) i->free.first_bigger = d;
 				break;
 			} else {
+				if (i->free.first_bigger == 0 || i->free.first_bigger->free.size > d->free.size)
+					i->free.first_bigger = d;
 				// continue
 				i = i->free.next_by_size;
 			}
 		}
 	}
+
+	// Sanity check, could be deleted for performance but this doesn't necessarily cost much at the moment.
+	// Explanation: the first_bigger field is meant to point at the first free descriptor with strictly
+	// superior size, intending to make the finding a suitable free region faster, but this field
+	// is a bit complicated to keep up to date (see the messy code above...)
+	descriptor_t *rec_check_first_bigger(descriptor_t *it, size_t sz) {
+		if (it == 0) return 0;
+		ASSERT(rec_check_first_bigger(it->free.next_by_size, it->free.size) == it->free.first_bigger);
+		if (it->free.size > sz) return it;
+		return it->free.first_bigger;
+	}
+	ASSERT(rec_check_first_bigger(first_free_region_by_size, 0) == first_free_region_by_size);
 }
 
 descriptor_t *find_used_region(void* addr) {
@@ -230,9 +264,8 @@ void region_allocator_init(void* begin, void* rsvd_end, void* end, map_page_fun_
 	descriptor_t *f0 = get_unused_descriptor();
 	f0->free.addr = rsvd_end;
 	f0->free.size = ((void*)end - rsvd_end);
-	f0->free.next_by_size = 0;
-	f0->free.first_bigger = 0;
-	first_free_region_by_size = first_free_region_by_addr = f0;
+	first_free_region_by_size = first_free_region_by_addr = 0;
+	add_free_region(f0);
 
 	if (rsvd_end > begin) {
 		descriptor_t *u0 = get_unused_descriptor();
@@ -359,19 +392,19 @@ region_info_t *find_region(void* addr) {
 void dbg_print_region_info() {
 	mutex_lock(&ra_mutex);
 
-	dbg_printf("/ Free kernel regions, by address:\n");
+	dbg_printf("/ Free VM 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 kernel regions, by size:\n");
+	dbg_printf("- Free VM 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 ", d->free.addr, d->free.addr + d->free.size);
 		dbg_printf("(0x%p, next in size: 0x%p)\n", d->free.size,
 			(d->free.first_bigger == 0 ? 0 : d->free.first_bigger->free.addr));
 		ASSERT(d != d->free.next_by_size);
 	}
-	dbg_printf("- Used kernel regions:\n");
+	dbg_printf("- Used VM 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);
diff --git a/src/lib/include/stdio.h b/src/lib/include/stdio.h
index b51bee4..a0d741f 100644
--- a/src/lib/include/stdio.h
+++ b/src/lib/include/stdio.h
@@ -1,8 +1,8 @@
 #pragma once
 
-#include <stddef.h>
 #include <stdarg.h>
-#include <stdint.h>
+
+#include <syscall.h>
 
 extern fd_t stdio;
 
diff --git a/src/sysbin/giosrv/main.c b/src/sysbin/giosrv/main.c
index 6e3378b..e0b76f5 100644
--- a/src/sysbin/giosrv/main.c
+++ b/src/sysbin/giosrv/main.c
@@ -4,7 +4,7 @@
 
 #include <syscall.h>
 #include <debug.h>
-#include <user_region.h>
+#include <region_alloc.h>
 
 #include <proto/keyboard.h>
 
diff --git a/src/sysbin/init/main.c b/src/sysbin/init/main.c
index 6ac003b..f1cb77a 100644
--- a/src/sysbin/init/main.c
+++ b/src/sysbin/init/main.c
@@ -5,7 +5,7 @@
 
 #include <syscall.h>
 #include <debug.h>
-#include <user_region.h>
+#include <region_alloc.h>
 
 #include <btree.h>
 
diff --git a/src/sysbin/login/main.c b/src/sysbin/login/main.c
index 359d677..dfc5dfa 100644
--- a/src/sysbin/login/main.c
+++ b/src/sysbin/login/main.c
@@ -1,6 +1,5 @@
 #include <string.h>
 #include <malloc.h>
-#include <user_region.h>
 #include <debug.h>
 
 #include <syscall.h>
diff --git a/src/sysbin/shell/main.c b/src/sysbin/shell/main.c
index e35d700..3f37ff8 100644
--- a/src/sysbin/shell/main.c
+++ b/src/sysbin/shell/main.c
@@ -1,6 +1,5 @@
 #include <string.h>
 #include <malloc.h>
-#include <user_region.h>
 #include <debug.h>
 
 #include <stdio.h>
diff --git a/src/sysbin/terminal/main.c b/src/sysbin/terminal/main.c
index f0e77e3..a0d8855 100644
--- a/src/sysbin/terminal/main.c
+++ b/src/sysbin/terminal/main.c
@@ -1,6 +1,6 @@
 #include <string.h>
 #include <malloc.h>
-#include <user_region.h>
+#include <region_alloc.h>
 #include <debug.h>
 
 #include <gip.h>
diff --git a/src/tests/ktests/region1/test.c b/src/tests/ktests/region1/test.c
index 58b4933..b5367d9 100644
--- a/src/tests/ktests/region1/test.c
+++ b/src/tests/ktests/region1/test.c
@@ -5,24 +5,39 @@ void test_region_1() {
 	void* p = region_alloc(0x1000, "Test region");
 	dbg_printf("Allocated one-page region: 0x%p\n", p);
 	dbg_print_region_info();
+
 	void* q = region_alloc(0x1000, "Test region");
 	dbg_printf("Allocated one-page region: 0x%p\n", q);
 	dbg_print_region_info();
+
 	void* r = region_alloc(0x2000, "Test region");
 	dbg_printf("Allocated two-page region: 0x%p\n", r);
 	dbg_print_region_info();
+
 	void* s = region_alloc(0x10000, "Test region");
 	dbg_printf("Allocated 16-page region: 0x%p\n", s);
 	dbg_print_region_info();
+
 	region_free(p);
 	dbg_printf("Freed region 0x%p\n", p);
 	dbg_print_region_info();
+
+	region_free(r);
+	dbg_printf("Freed region 0x%p\n", r);
+	dbg_print_region_info();
+
+	p = region_alloc(0x1000, "Test region");
+	dbg_printf("Allocated one-page region: 0x%p\n", p);
+	dbg_print_region_info();
+
 	region_free(q);
 	dbg_printf("Freed region 0x%p\n", q);
 	dbg_print_region_info();
-	region_free(r);
-	dbg_printf("Freed region 0x%p\n", r);
+
+	region_free(p);
+	dbg_printf("Freed region 0x%p\n", p);
 	dbg_print_region_info();
+
 	region_free(s);
 	dbg_printf("Freed region 0x%p\n", s);
 	dbg_print_region_info();
diff --git a/src/tests/ktests/run_qemu_test.sh b/src/tests/ktests/run_qemu_test.sh
index 0e7b83e..5f7df83 100755
--- a/src/tests/ktests/run_qemu_test.sh
+++ b/src/tests/ktests/run_qemu_test.sh
@@ -1,6 +1,6 @@
 #!/bin/bash
 
-(qemu-system-i386 -kernel test_kernel.bin -initrd ../../kernel/kernel.map -serial stdio -m 16 -display none & echo $! >pid) \
+(qemu-system-i386 -kernel test_kernel.bin -initrd ../../../kernel/kernel.map -serial stdio -m 16 -display none & echo $! >pid) \
 	| tee >(grep -m 1 "TEST-" >result; kill -INT `cat pid`) \
 
 RESULT=`cat result`
diff --git a/src/tests/utests/malloc/test.c b/src/tests/utests/malloc/test.c
index b55d28a..fb2f3b9 100644
--- a/src/tests/utests/malloc/test.c
+++ b/src/tests/utests/malloc/test.c
@@ -4,7 +4,7 @@
 
 #include <syscall.h>
 #include <debug.h>
-#include <user_region.h>
+#include <region_alloc.h>
 
 int main(int argc, char **argv) {
 	dbg_print("(BEGIN-USER-TEST malloc-test)\n");