[WIP] virtual memory management

3 files changed, 612 insertions, 199 deletions

diff --git a/common/mem_nodes.c b/common/mem_nodes.c
new file mode 100644
index 0000000..1779276
--- /dev/null
+++ b/common/mem_nodes.c
@@ -0,0 +1,161 @@
+#include <apos/vmem.h>
+#include <apos/pmem.h>
+#include <apos/mem.h>
+#include <apos/string.h>
+#include <apos/mem_nodes.h>
+
+enum block_status {
+	FREE = 0, USED = 1
+};
+
+struct block_wrapper {
+	enum block_status status;
+	struct sp_mem n;
+};
+
+struct block_region {
+	size_t used_blocks;
+	struct sp_node sp_n;
+};
+
+static struct sp_root root_region = (struct sp_root){0};
+
+#define MAX_BLOCKS \
+	((BASE_PAGE_SIZE - sizeof(struct block_region)) / sizeof(struct block_wrapper))
+
+#define block_region(b) \
+	((struct block_region *)((size_t)(b) & ~(BASE_PAGE_SIZE - 1)))
+
+#define region_container(b) \
+	container_of(b, struct block_region, sp_n)
+
+#define block_container(b) \
+	container_of(b, struct block_wrapper, n)
+
+#define region_to_array(r) \
+	((struct block_wrapper *)((char *)(r) + sizeof(struct block_region)))
+
+static struct block_region *__create_region()
+{
+	struct block_region *r = (struct block_region *)alloc_page(BASE_PAGE, 0);
+	memset(r, FREE, BASE_PAGE_SIZE);
+	return r;
+}
+
+void init_mem_blocks()
+{
+	sp_root(root_region) = &__create_region()->sp_n;
+}
+
+static void __destroy_mem_block(struct sp_node *n)
+{
+	if(!n)
+		return;
+
+	__destroy_mem_block(sp_left(n));
+	__destroy_mem_block(sp_right(n));
+
+	struct block_region *r = block_region(n);
+	free_page(BASE_PAGE, (vm_t)r);
+}
+
+void destroy_mem_blocks()
+{
+	__destroy_mem_block(sp_root(root_region));
+}
+
+static struct sp_mem *__find_free_block(struct block_region *h)
+{
+	struct block_wrapper *w = region_to_array(h);
+	for(size_t i = 0; i < MAX_BLOCKS; ++i){
+		if(w[i].status != FREE)
+			continue;
+
+		w[i].status = USED;
+		return &w[i].n;
+	}
+
+	return 0;
+}
+
+static void __region_insert(struct block_region *r)
+{
+	struct sp_node *n = sp_root(root_region), *p = NULL;
+	enum sp_dir d = LEFT;
+
+	r->sp_n = (struct sp_node){0};
+
+	while(n){
+		struct block_region *t = region_container(n);
+
+		p = n;
+		if(r->used_blocks < t->used_blocks){
+			n = sp_left(n);
+			d = LEFT;
+		}
+
+		else if(r->used_blocks > t->used_blocks){
+			n = sp_right(n);
+			d = RIGHT;
+		}
+
+		else if(r < t) {
+			n = sp_left(n);
+			d = LEFT;
+		}
+
+		else {
+			n = sp_right(n);
+			d = RIGHT;
+		}
+	}
+
+	sp_insert(&sp_root(root_region), p, &r->sp_n, d);
+}
+
+static void __region_remove(struct block_region *r)
+{
+	sp_remove(&sp_root(root_region), &r->sp_n);
+}
+
+static void __update_regions(struct block_region *r)
+{
+	__region_remove(r);
+	__region_insert(r);
+}
+
+struct sp_mem *get_mem_node()
+{
+	struct sp_node *n = sp_root(root_region);
+
+	while(n){
+		struct block_region *r = region_container(n);
+
+		if(r->used_blocks != MAX_BLOCKS){
+			r->used_blocks++;
+			__update_regions(r);
+
+			return __find_free_block(r);
+		}
+
+		n = n->left;
+	}
+
+	/* we need to allocate a new region */
+	struct block_region *r = __create_region();
+	r->used_blocks++;
+	__region_insert(r);
+
+	return __find_free_block(r);
+}
+
+void free_mem_node(struct sp_mem *m)
+{
+	struct block_wrapper *w = block_container(m);
+	w->status = FREE;
+
+	struct block_region *r = block_region(w);
+	r->used_blocks--;
+
+	__update_regions(r);
+}
diff --git a/common/sp_tree.c b/common/sp_tree.c
new file mode 100644
index 0000000..abfaa4b
--- /dev/null
+++ b/common/sp_tree.c
@@ -0,0 +1,236 @@
+#include <apos/sp_tree.h>
+
+inline static void __sp_turn_left(struct sp_node *n)
+{
+	struct sp_node *l = sp_left(n);
+	struct sp_node *p = sp_paren(n);
+
+	sp_paren(l) = sp_paren(n);
+	sp_left(n) = sp_right(l);
+	sp_paren(n) = l;
+	sp_right(l) = n;
+
+	if(p && sp_left(p) == n)
+		sp_left(p) = l;
+	else if (p)
+		sp_right(p) = l;
+
+	if(sp_left(n))
+		sp_lparen(n) = n;
+}
+
+inline static void __sp_turn_right(struct sp_node *n)
+{
+	struct sp_node *r = sp_right(n);
+	struct sp_node *p = sp_paren(n);
+
+	sp_paren(r) = sp_paren(n);
+	sp_right(n) = sp_left(r);
+	sp_paren(n) = r;
+	sp_left(r) = n;
+
+	if(p && sp_left(p) == n)
+		sp_left(p) = r;
+	else if (p)
+		sp_right(p) = r;
+
+	if(sp_right(n))
+		sp_rparen(n) = n;
+}
+
+inline static int __sp_balance(struct sp_node *n)
+{
+	int l = 0;
+	int r = 0;
+
+	if(sp_left(n))
+		l = sp_left(n)->hint + 1;
+
+	if(sp_right(n))
+		r = sp_right(n)->hint + 1;
+
+	return l - r;
+}
+
+inline static int __sp_max_hint(struct sp_node *n)
+{
+	int l = 0;
+	int r = 0;
+
+	if(sp_left(n))
+		l = sp_left(n)->hint + 1;
+
+	if(sp_right(n))
+		r = sp_right(n)->hint + 1;
+
+	if(l > r)
+		return l;
+	else
+		return r;
+}
+
+inline static void sp_update(struct sp_node **root, struct sp_node *n)
+{
+	while(n){
+
+		int b = __sp_balance(n);
+		int prev_hint = n->hint;
+		struct sp_node *p = sp_paren(n);
+
+		if(b < -1) {
+			/* leaning to the right */
+			if(n == *root)
+				*root = sp_right(n);
+
+			__sp_turn_right(n);
+		}
+
+		else if(b > 1){
+			/* leaning to the left */
+			if(n == *root)
+				*root = sp_left(n);
+
+			__sp_turn_left(n);
+		}
+
+		n->hint = __sp_max_hint(n);
+		if(n->hint == 0 || n->hint != prev_hint)
+			n = p;
+		else
+			return;
+	}
+}
+
+void sp_insert(struct sp_node **root, struct sp_node *p,
+		struct sp_node *n, enum sp_dir d)
+{
+	if(!*root){
+		*root = n;
+		return;
+	}
+
+	if(d == LEFT)
+		sp_left(p) = n;
+	else
+		sp_right(p) = n;
+
+	sp_paren(n) = p;
+	sp_update(root, n);
+}
+
+inline static void __sp_replace_right(struct sp_node *n, struct sp_node *r)
+{
+	struct sp_node *p = sp_paren(n);
+	struct sp_node *rp = sp_paren(r);
+
+	if(sp_left(rp) == r){
+		sp_left(rp) = sp_right(r);
+		if(sp_right(r))
+			sp_rparen(r) = rp;
+	}
+
+	if(sp_paren(rp) == n)
+		sp_paren(rp) = r;
+
+	sp_paren(r) = p;
+	sp_left(r) = sp_left(n);
+
+	if(sp_right(n) != r){
+		sp_right(r) = sp_right(n);
+		sp_rparen(n) = r;
+	}
+
+	if(p && sp_left(p) == n)
+		sp_left(p) = r;
+	else if (p)
+		sp_right(p) = r;
+
+	if(sp_left(n))
+		sp_lparen(n) = r;
+}
+
+inline static void __sp_replace_left(struct sp_node *n, struct sp_node *l)
+{
+	struct sp_node *p = sp_paren(n);
+	struct sp_node *lp = sp_paren(l);
+
+	if(sp_right(lp) == l){
+		sp_right(lp) = sp_left(l);
+		if(sp_left(l))
+			sp_lparen(l) = lp;
+	}
+
+	if(sp_paren(lp) == n)
+		sp_paren(lp) = l;
+
+	sp_paren(l) = p;
+	sp_right(l) = sp_right(n);
+
+	if(sp_left(n) != l){
+		sp_left(l) = sp_left(n);
+		sp_lparen(n) = l;
+	}
+
+	if(p && sp_left(p) == n)
+		sp_left(p) = l;
+	else if (p)
+		sp_right(p) = l;
+
+	if(sp_right(n))
+		sp_rparen(n) = l;
+}
+
+/* TODO: handle root better */
+void sp_remove(struct sp_node **root, struct sp_node *del)
+{
+	if(sp_right(del)){
+		struct sp_node *least = sp_first(sp_right(del));
+
+		if(del == *root)
+			*root = least;
+
+		__sp_replace_right(del, least);
+		sp_update(root, sp_right(least));
+		return;
+	}
+
+	if(sp_left(del)){
+		struct sp_node *most = sp_last(sp_left(del));
+
+		if(del == *root)
+			*root = most;
+
+		__sp_replace_left(del, most);
+		sp_update(root, sp_left(most));
+		return;
+	}
+
+	if(del == *root){
+		*root = 0;
+		return;
+	}
+
+	/* empty node */
+	struct sp_node *paren = sp_paren(del);
+
+	if(sp_left(paren) == del)
+		sp_left(paren) = 0;
+	else
+		sp_right(paren) = 0;
+
+	sp_update(root, paren);
+}
+
+struct sp_node *sp_first(struct sp_node *n)
+{
+	if(!sp_left(n)) return n;
+
+	return sp_first(sp_left(n));
+}
+
+struct sp_node *sp_last(struct sp_node *n)
+{
+	if(!sp_right(n)) return n;
+
+	return sp_last(sp_right(n));
+}
diff --git a/common/vmem.c b/common/vmem.c
index 87d5b3b..267fbb7 100644
--- a/common/vmem.c
+++ b/common/vmem.c
@@ -1,275 +1,291 @@
 #include <apos/vmem.h>
-#include <apos/pmem.h>
-#include <apos/mem.h>
-#include <apos/string.h>
+#include <apos/mem_nodes.h>
 
-/* new idea, not implemented:
- * region(free) -> region(not free) -> region(free) -> region(free) ...
+#define mark_region_used(r) ((r) = 1)
+#define mark_region_unused(r) ((r) = 0)
+#define is_region_used(r) (r)
+
+static struct sp_root free_regions = (struct sp_root){0};
+static struct sp_root used_regions = (struct sp_root){0};
+
+/* pretty major slowdown when we get to some really massive numbers, not
+ * entirely sure why. Will need to check up on this at some point, have I
+ * somehow managed to come up with a _very_ bad situation for my sp_trees?
+ *
+ * EDIT: apparently, yeah. Max depth of 106 with a million entries, interesting.
+ * I guess since in this scenario all sizes are 1, and I just shove everything
+ * to the right? Maybe?
+ *
+ * EDIT upon EDIT: yeah, when taking the start position of the region into
+ * account we get a much more sensible max depth of 39 for 5 million entries.
+ * Seems I have found a weakness in sp_trees :D
  *
- * each region comes right after the next, would at least be pretty quick to 
- * merge free blocks?
+ * Duplicate entries don't work well with any trees, I think. Good to know,
+ * maybe not even anything with sp_trees but more a weakness of binary trees in
+ * general?
  */
+static struct sp_mem *sp_free_insert_region(struct sp_mem *m)
+{
+	struct sp_node *n = sp_root(free_regions), *p = NULL;
+	size_t start = m->start;
+	size_t size = m->end - m->start;
+	enum sp_dir d = LEFT;
 
-enum mm_block_status_t {
-	FREE, USED
-};
+	m->sp_n = (struct sp_node){0};
 
-struct mm_block_region_t;
+	while(n){
+		struct sp_mem *t = mem_container(n);
+		size_t nsize = t->end - t->start;
+		p = n;
 
-/* linked list for now because I'm shit at coding */
-struct mm_block_t {
-	enum mm_block_status_t status;
-	vm_t start;
-	vm_t end;
-	struct mm_block_t *next;
-	struct mm_block_t *prev;
-};
+		if(size < nsize){
+			n = sp_left(n);
+			d = LEFT;
+		}
 
-struct mm_block_region_t {
-	vm_t vaddr;
-	size_t blocks;
-	size_t max_blocks;
-	struct mm_block_region_t *next;
-	struct mm_block_t *first;
-};
+		else if(size > nsize) {
+			n = sp_right(n);
+			d = RIGHT;
+		}
 
-static struct mm_block_region_t *root_region = (struct mm_block_region_t *)ROOT_REGION;
-static struct mm_block_t *root_block = 0;
+		else if (start < t->start){
+			n = sp_left(n);
+			d = LEFT;
+		}
 
-#define NODE_REGION(x) ((struct mm_block_region_t *)(((vm_t)x) & (__mm_page_shift - 1)))
-#define NEXT_BLOCK() ((struct mm_block_region_t *)\
-((region_counter * __o_size(MM_O0)) + ROOT_PTE))
+		else {
+			n = sp_right(n);
+			d = RIGHT;
+		}
+	}
 
-/* TODO: mark all used regions, also blocks */
-static struct mm_block_t *get_free_block(struct vm_branch_t *branch)
-{
-	struct mm_block_region_t *region = root_region;
-	size_t region_counter = 1;
-	for(; region; region = region->next){
-		if(region->next == 0){
-			pm_t next_pa = alloc_page(MM_O0, 0);
-			struct mm_block_region_t *next_va = NEXT_BLOCK();
+	if(sp_root(free_regions))
+		sp_insert(&sp_root(free_regions), p, &m->sp_n, d);
+	else
+		sp_root(free_regions) = &m->sp_n;
 
-			map_vmem(branch, next_pa, (vm_t)next_va,
-					VM_W | VM_R | VM_V, MM_O0);
+	return m;
+}
 
-			memset(next_va, 0, __o_size(MM_O0));
-			next_va->max_blocks =
-				(__o_size(MM_O0) - sizeof(struct mm_block_region_t))
-				/ sizeof(struct mm_block_t);
+static struct sp_mem *sp_used_insert_region(struct sp_mem *m)
+{
+	struct sp_node *n = sp_root(used_regions), *p = NULL;
+	vm_t start = m->start;
+	enum sp_dir d = LEFT;
 
-			region->next = next_va;
-		}
+	m->sp_n = (struct sp_node){0};
+
+	while(n){
+		struct sp_mem *t = mem_container(n);
 
-		if(region->blocks == region->max_blocks)
-			continue;
+		p = n;
 
-		struct mm_block_t *block = region->first;
-		for(size_t i = 0; i < region->max_blocks; ++i){
-			if(block[i].start == 0 && block[i].end == 0){
-				NODE_REGION(&block[i])->blocks++;
-				return &block[i];
-			}
+		if(start < t->start){
+			n = sp_left(n);
+			d = LEFT;
 		}
 
-		region_counter++;
+		else {
+			/* we should never encounter a situation where start =
+			 * t->start */
+			n = sp_right(n);
+			d = RIGHT;
+		}
 	}
 
-	return 0;
+	if(sp_root(used_regions))
+		sp_insert(&sp_root(used_regions), p, &m->sp_n, d);
+	else
+		sp_root(used_regions) = &m->sp_n;
+
+	return m;
 }
 
-void init_vmem(struct vm_branch_t *branch, vm_t tmp_pte)
+int sp_mem_init(size_t arena_size)
 {
-#if defined(KERNEL)
-	arch_init_vmem(branch, tmp_pte);
-#else
-	(void)tmp_pte;
-#endif
-
-	pm_t first_block = alloc_page(MM_O0, 0);
-	map_vmem(branch, first_block, (vm_t)root_region, VM_W | VM_R | VM_V, MM_O0);
-	memset(root_region, 0, __o_size(MM_O0));
+	struct sp_mem *m = get_mem_node();
+	m->end = arena_size;
+	sp_free_insert_region(m);
 
-	/* apparently I'm overwriting some memory here which is fucking up
-	 * things elsewhere, specifically some PTE. Really should come up with
-	 * some sensible address mappings, as everything is at the moment sort
-	 * of hither and tither. */
-	root_region->max_blocks = (__o_size(MM_O0) - sizeof(struct mm_block_region_t))
-		/ sizeof(struct mm_block_t);
-	root_region->first = (struct mm_block_t *)((vm_t)root_region + sizeof(struct mm_block_t));
-	root_block = root_region->first;
-
-	root_block->start = __o_size(MM_O0);
-	/* TODO: add in UMEM_TOP or something */
-	root_block->end = -1;
-	root_block->status = FREE;
+	return 0;
 }
 
-
-/* ... new_node -> node ... */
-static void insert_before(struct vm_branch_t *branch, struct mm_block_t *node, vm_t split)
+static void __sp_mem_destroy(struct sp_node *n)
 {
-	struct mm_block_t *new_node = get_free_block(branch);
-
-	new_node->start = node->start;
-	new_node->end = split;
+	if(!n)
+		return;
 
-	node->start = split;
+	__sp_mem_destroy(sp_left(n));
+	__sp_mem_destroy(sp_right(n));
 
-	struct mm_block_t *prev = node->prev;
-	new_node->next = node;
-	new_node->prev = prev;
-	prev->next = new_node;
-	node->prev = new_node;
+	struct sp_mem *m = mem_container(n);
+	free_mem_node(m);
 }
 
-/* ... node -> new_node ... */
-static void insert_after(struct vm_branch_t *branch, struct mm_block_t *node, vm_t split)
+void sp_mem_destroy()
 {
-	struct mm_block_t *new_node = get_free_block(branch);
+	__sp_mem_destroy(sp_root(free_regions));
+	__sp_mem_destroy(sp_root(used_regions));
+}
 
-	new_node->start = split;
-	new_node->end = node->end;
+/* interestingly this is now the main bottleneck :D
+ *
+ * eh, it's not a massive thing I guess, maybe the code could be a bit quicker
+ * but I mean 10 000 000 memory allocations in 20 s is good enough for now
+ * */
+static struct sp_mem *sp_used_find(vm_t start)
+{
+	struct sp_node *n = sp_root(used_regions);
+	while(n){
+		struct sp_mem *t = mem_container(n);
+		if(start == t->start)
+			return t;
 
-	node->end = split;
+		if(start < t->start)
+			n = sp_left(n);
+		else
+			n = sp_right(n);
+	}
 
-	struct mm_block_t *next = node->next;
-	new_node->next = next;
-	new_node->prev = node;
-	next->prev = new_node;
-	node->next = new_node;
+	return 0;
 }
 
-static void gobble_block(struct vm_branch_t *branch, struct mm_block_t *node,
-		vm_t start, vm_t end)
+static struct sp_mem *sp_mem_create_region(vm_t start, vm_t end,
+		struct sp_mem *prev, struct sp_mem *next)
 {
-	node->status = USED;
+	struct sp_mem *m = get_mem_node();
+	m->start = start;
+	m->end = end;
+	m->prev = prev;
+	m->next = next;
+	return m;
+}
 
-	/* ... node ... */
-	if(node->start == start && node->end == end)
-		return;
+static struct sp_mem *sp_free_find_first(size_t size, size_t alignment)
+{
+	struct sp_node *n = sp_root(free_regions);
+	while(n){
+		struct sp_mem *t = mem_container(n);
+		size_t nsize = t->end - align_up(t->start, alignment);
 
-	/* ... node -> new_node ... */
-	if(node->start == start && node->end >= end){
-		insert_after(branch, node, end);
-		struct mm_block_t *new = node->next;
+		if(size <= nsize)
+			return t;
 
-		new->status = FREE;
-		return;
+		n = sp_right(n);
 	}
 
-	/* ... new_node -> node ...*/
-	if(node->start < start && node->end == end){
-		insert_before(branch, node, start);
-		struct mm_block_t *new = node->prev;
+	return 0;
+}
 
-		new->status = FREE;
-		return;
-	}
+/* apparently Linux doesn't necessarily give a shit about mmap hints, so I'll
+ * just ignore them for now. Note that alloc_region should only be used when
+ * mmap is called with MAP_ANON, all other situations should be handled in some
+ * fs server */
+vm_t alloc_region(size_t size, size_t alignment)
+{
+	struct sp_mem *m = sp_free_find_first(size, alignment);
+	if(!m)
+		return 0;
 
-	/* ... new_node1 -> node -> new_node2 .. */
-	insert_before(branch, node, start);
-	struct mm_block_t *prev = node->prev;
+	sp_remove(&sp_root(free_regions), &m->sp_n);
 
-	insert_after(branch, node, end);
-	struct mm_block_t *next = node->next;
+	vm_t aligned_start = align_up(m->start, alignment);
 
-	prev->status = FREE;
-	next->status = FREE;
-}
+	vm_t pre_start = m->start;
+	vm_t pre_end = aligned_start;
 
-/* only map with 4K blocks to keep it simple for now */
-vm_t map_vregion(struct vm_branch_t *branch, pm_t base, vm_t start, size_t size,
-		uint8_t flags)
-{
-	struct mm_block_t *node = root_block;
-	for(; node; node = node->next){
-		if(node->start > start)
-			return 0;
+	vm_t start = pre_end;
+	vm_t end = aligned_start + size;
 
-		if(node->status == FREE && node->end >= start + size){
-			gobble_block(branch, node, start, start + size);
-			goto found;
-		}
+	vm_t post_start = end;
+	vm_t post_end = m->end;
+
+	if(pre_start != pre_end){
+		struct sp_mem *n = sp_mem_create_region(pre_start, pre_end, m->prev, m);
+		m->prev = n;
+		if(n->prev)
+			n->prev->next = n;
+
+		sp_free_insert_region(n);
 	}
 
-	return 0;
+	if(post_start != post_end){
+		struct sp_mem *n = sp_mem_create_region(post_start, post_end, m, m->next);
+		m->next = n;
+		if(n->next)
+			n->next->prev = n;
 
-found:
-	for(; size >= __o_size(MM_O0); size -= __o_size(MM_O0)){
-		map_vmem(branch, start, base, flags, MM_O0);
-		start += __o_size(MM_O0);
-		base += __o_size(MM_O0);
+		sp_free_insert_region(n);
 	}
 
+	m->end = end;
+	m->start = start;
+	mark_region_used(m->flags);
+	sp_used_insert_region(m);
 	return start;
 }
 
-static void free_block(struct mm_block_t *node)
+static void __sp_try_coalesce_prev(struct sp_mem *m)
 {
-	struct mm_block_t *prev = node->prev;
-	struct mm_block_t *next = node->next;
+	while(m){
+		if(!m || is_region_used(m->flags))
+			return;
 
-	if(prev->status == FREE && next->status == FREE){
-		/* merge all three blocks */
-		prev->end = next->end;
-		prev->next = next->next;
-		next->next->prev = prev;
+		struct sp_mem *p = m->prev;
+		if(!p || is_region_used(p->flags))
+			return;
 
-		node->start = 0;
-		node->end = 0;
+		m->start = p->start;
+		m->prev = p->prev;
 
-		next->start = 0;
-		next->end = 0;
+		if(m->prev)
+			m->prev->next = m;
 
-		NODE_REGION(node)->blocks--;
-		NODE_REGION(next)->blocks--;
-		return;
+		sp_remove(&sp_root(free_regions), &p->sp_n);
+		free_mem_node(p);
+
+		m = m->prev;
 	}
+}
 
-	if(prev->status == FREE){
-		prev->end = node->end;
-		prev->next = next;
-		next->prev = prev;
+static void __sp_try_coalesce_next(struct sp_mem *m)
+{
+	while(m){
+		if(!m || is_region_used(m->flags))
+			return;
 
-		node->start = 0;
-		node->end = 0;
+		struct sp_mem *n = m->next;
+		if(!n || is_region_used(n->flags))
+			return;
 
-		NODE_REGION(node)->blocks--;
-		return;
-	}
+		m->end = n->end;
+		m->next = n->next;
 
-	if(next->status == FREE){
-		next->start = node->start;
-		next->prev = prev;
-		prev->next = next;
+		if(m->next)
+			m->next->prev = m;
 
-		node->start = 0;
-		node->end = 0;
+		sp_remove(&sp_root(free_regions), &n->sp_n);
+		free_mem_node(n);
 
-		NODE_REGION(node)->blocks--;
-		return;
+		m = m->next;
 	}
+}
 
-	node->status = FREE;
+static void sp_mem_try_coalesce(struct sp_mem *m)
+{
+	__sp_try_coalesce_prev(m);
+	__sp_try_coalesce_next(m);
 }
 
-void unmap_vregion(struct vm_branch_t *branch, vm_t start)
+void free_region(vm_t start)
 {
-	size_t size = 0;
-	struct mm_block_t *node = root_block;
-	for(; node; node = node->next){
-		/* if node->start == start status should be USED in all cases,
-		 * but let's just go with this
-		 */
-		if(node->status == USED && node->start == start){
-			size = node->end - node->start;
-			free_block(node);
-		}
-	}
+	struct sp_mem *m = sp_used_find(start);
+	if(!m)
+		return;
 
-	for(; size >= __o_size(MM_O0); size -= __o_size(MM_O0)){
-		unmap_vmem(branch, start, MM_O0);
-		start += __o_size(MM_O0);
-	}
+	sp_remove(&sp_root(used_regions), &m->sp_n);
+	mark_region_unused(m->flags);
+
+	sp_mem_try_coalesce(m);
+	sp_free_insert_region(m);
 }