6 files changed, 282 insertions, 48 deletions

diff --git a/arch/riscv/common/vmem.c b/arch/riscv/common/vmem.c
index 207df34..7b2d66b 100644
--- a/arch/riscv/common/vmem.c
+++ b/arch/riscv/common/vmem.c
@@ -10,16 +10,16 @@
 
 /* probably not actually this simple, right? */
 void map_vmem(struct vm_branch_t *branch,
-		pm_t paddr, vm_t vaddr,
-		uint8_t flags, enum mm_order_t order)
+		pm_t paddr, vm_t vaddr, uint8_t flags, enum mm_order_t order)
 {
 	enum mm_order_t top = __mm_max_order;
-	while(top != order){
+	while (top != order) {
 		size_t idx = pm_to_index(vaddr, top);
 
-		if(!branch->leaf[idx]){
+		if (!branch->leaf[idx]) {
 			pm_t new_leaf = alloc_page(MM_KPAGE, 0);
-			branch->leaf[idx] = (struct vm_branch_t *)to_pte(new_leaf, VM_V);
+			branch->leaf[idx] =
+				(struct vm_branch_t *)to_pte(new_leaf, VM_V);
 			memset((void *)new_leaf, 0, sizeof(struct vm_branch_t));
 		}
 
@@ -31,43 +31,16 @@ void map_vmem(struct vm_branch_t *branch,
 	branch->leaf[idx] = (struct vm_branch_t *)to_pte(paddr, flags);
 }
 
-void unmap_vmem(struct vm_branch_t *branch,
-		vm_t vaddr, enum mm_order_t order)
+void unmap_vmem(struct vm_branch_t *branch, vm_t vaddr, enum mm_order_t order)
 {
-	while(order){
+	while (order) {
 		size_t idx = pm_to_index(vaddr, order);
 		branch = (struct vm_branch_t *)pte_addr(branch->leaf[idx]);
 	}
 
 	size_t idx = pm_to_index(vaddr, order);
-	if(branch->leaf[idx])
+	if (branch->leaf[idx])
 		free_page(order, pte_addr(branch->leaf[idx]));
 
 	branch->leaf[idx] = 0;
 }
-
-vm_t map_vregion(struct vm_branch_t *branch, pm_t base, pm_t top, vm_t start, vm_t end)
-{
-	/* TODO: figure out how to find first suitable memory region */
-
-	/* find first free page, iterate forward until we either fit the whole
-	 * physical region or hit a used page
-	 *
-	 * continue until we hit end?
-	 */
-}
-
-void unmap_vregion(struct vm_branch_t *branch, pm_t base, pm_t top)
-{
-	/* TODO */
-}
-
-vm_t map_vsize(struct vm_branch_t *branch, size_t size)
-{
-	/* TODO */
-}
-
-void unmap_vsize(struct vm_branch_t *branch, size_t size)
-{
-	/* TODO */
-}
diff --git a/arch/riscv/include/vmem.h b/arch/riscv/include/vmem.h
index ec2a3ba..d17aaf1 100644
--- a/arch/riscv/include/vmem.h
+++ b/arch/riscv/include/vmem.h
@@ -13,6 +13,12 @@
 #define VM_A (1 << 6)
 #define VM_D (1 << 7)
 
+enum mm_mode_t {
+	Sv48,
+	Sv39,
+	Sv32,
+};
+
 typedef size_t vm_t;
 struct __packed vm_branch_t {
 	struct vm_branch_t *leaf[512];
diff --git a/common/mem.c b/common/mem.c
index 445748c..48bd776 100644
--- a/common/mem.c
+++ b/common/mem.c
@@ -1,5 +1,6 @@
 #include <apos/types.h>
 #include <apos/mem.h>
+#include <apos/vmem.h>
 #include <libfdt.h>
 
 size_t __mm_shifts[10];
diff --git a/common/vmem.c b/common/vmem.c
new file mode 100644
index 0000000..c30f99b
--- /dev/null
+++ b/common/vmem.c
@@ -0,0 +1,260 @@
+#include <apos/vmem.h>
+#include <apos/pmem.h>
+#include <apos/mem.h>
+#include <apos/string.h>
+
+/* new idea, not implemented:
+ * region(free) -> region(not free) -> region(free) -> region(free) ...
+ *
+ * each region comes right after the next, would at least be pretty quick to 
+ * merge free blocks?
+ */
+
+enum mm_block_status_t {
+	FREE, USED
+};
+
+struct mm_block_region_t;
+
+/* 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;
+};
+
+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;
+};
+
+static struct mm_block_region_t *root_region = 0;
+/* a block represents free regions */
+static struct mm_block_t *root_block = 0;
+
+#define NODE_REGION(x) ((struct mm_block_region_t *)(((vm_t)x) & (__mm_page_shift - 1)))
+
+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 =
+				(struct mm_block_region_t *)
+				(region_counter * __o_size(MM_O0));
+
+			map_vmem(branch, next_pa, (vm_t)next_va,
+					VM_W | VM_R | VM_V, MM_O0);
+
+			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);
+
+			region->next = next_va;
+		}
+
+		if(region->blocks == region->max_blocks)
+			continue;
+
+		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];
+			}
+		}
+	}
+
+	return 0;
+}
+
+void init_vmem(struct vm_branch_t *branch)
+{
+	pm_t first_block = alloc_page(MM_O0, 0);
+	map_vmem(branch, first_block, 0, VM_W | VM_R | VM_V, MM_O0);
+	memset(root_region, 0, __o_size(MM_O0));
+
+	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 *)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 = USED;
+}
+
+
+/* ... new_node -> node ... */
+static void insert_before(struct vm_branch_t *branch, struct mm_block_t *node, vm_t split)
+{
+	struct mm_block_t *new_node = get_free_block(branch);
+
+	new_node->start = node->start;
+	new_node->end = split;
+
+	node->start = split;
+
+	struct mm_block_t *prev = node->prev;
+	new_node->next = node;
+	new_node->prev = prev;
+	prev->next = new_node;
+	node->prev = new_node;
+}
+
+/* ... node -> new_node ... */
+static void insert_after(struct vm_branch_t *branch, struct mm_block_t *node, vm_t split)
+{
+	struct mm_block_t *new_node = get_free_block(branch);
+
+	new_node->start = split;
+	new_node->end = node->end;
+
+	node->end = split;
+
+	struct mm_block_t *next = node->next;
+	new_node->next = next;
+	new_node->prev = node;
+	next->prev = new_node;
+	node->next = new_node;
+}
+
+static void gobble_block(struct vm_branch_t *branch, struct mm_block_t *node,
+		vm_t start, vm_t end)
+{
+	node->status = USED;
+
+	/* ... node ... */
+	if(node->start == start && node->end == end)
+		return;
+
+	/* ... node -> new_node ... */
+	if(node->start == start && node->end >= end){
+		insert_after(branch, node, end);
+		struct mm_block_t *new = node->next;
+
+		new->status = FREE;
+		return;
+	}
+
+	/* ... new_node -> node ...*/
+	if(node->start < start && node->end == end){
+		insert_before(branch, node, start);
+		struct mm_block_t *new = node->prev;
+
+		new->status = FREE;
+		return;
+	}
+
+	/* ... new_node1 -> node -> new_node2 .. */
+	insert_before(branch, node, start);
+	struct mm_block_t *prev = node->prev;
+
+	insert_after(branch, node, end);
+	struct mm_block_t *next = node->next;
+
+	prev->status = FREE;
+	next->status = FREE;
+}
+
+/* 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;
+
+		if(node->status == FREE && node->end >= start + size){
+			gobble_block(branch, node, start, start + size);
+			break;
+		}
+	}
+
+	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);
+	}
+
+	return start;
+}
+
+static void free_block(struct mm_block_t *node)
+{
+	struct mm_block_t *prev = node->prev;
+	struct mm_block_t *next = node->next;
+
+	if(prev->status == FREE && next->status == FREE){
+		/* merge all three blocks */
+		prev->end = next->end;
+		prev->next = next->next;
+		next->next->prev = prev;
+
+		node->start = 0;
+		node->end = 0;
+
+		next->start = 0;
+		next->end = 0;
+
+		NODE_REGION(node)->blocks--;
+		NODE_REGION(next)->blocks--;
+		return;
+	}
+
+	if(prev->status == FREE){
+		prev->end = node->end;
+		prev->next = next;
+		next->prev = prev;
+
+		node->start = 0;
+		node->end = 0;
+
+		NODE_REGION(node)->blocks--;
+		return;
+	}
+
+	if(next->status == FREE){
+		next->start = node->start;
+		next->prev = prev;
+		prev->next = next;
+
+		node->start = 0;
+		node->end = 0;
+
+		NODE_REGION(node)->blocks--;
+		return;
+	}
+
+	node->status = FREE;
+}
+
+void unmap_vregion(struct vm_branch_t *branch, 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);
+		}
+	}
+
+	for(; size >= __o_size(MM_O0); size -= __o_size(MM_O0)){
+		unmap_vmem(branch, start, MM_O0);
+		start += __o_size(MM_O0);
+	}
+}
diff --git a/include/apos/mem.h b/include/apos/mem.h
index 630fcd9..7c5a2dc 100644
--- a/include/apos/mem.h
+++ b/include/apos/mem.h
@@ -4,12 +4,6 @@
 #include <apos/utils.h>
 #include <pages.h>
 
-enum mm_mode_t {
-	Sv48,
-	Sv39,
-	Sv32,
-};
-
 #define MM_OINFO_WIDTH (sizeof(mm_info_t) * 8)
 
 #define pnum_to_index(pnum, order) (((pnum) >> __o_offset(order)) & (__o_width(order) - 1))
@@ -29,6 +23,7 @@ enum mm_mode_t {
 
 #define __o_offset(order) (__mm_shifts[order])
 #define __o_width(order) (__mm_widths[order])
+#define __o_size(order) (__mm_sizes[order])
 #define __o_elems(order) (__mm_widths[order] / MM_OINFO_WIDTH)
 
 #define __o_container(idx) ((idx) / MM_OINFO_WIDTH)
diff --git a/include/apos/vmem.h b/include/apos/vmem.h
index 589e814..d2dcedc 100644
--- a/include/apos/vmem.h
+++ b/include/apos/vmem.h
@@ -1,6 +1,8 @@
 #ifndef APOS_VMEM_H
 #define APOS_VMEM_H
 
+#include <apos/pmem.h>
+
 /* arch-specific data */
 #include <vmem.h>
 
@@ -14,19 +16,16 @@
  * (un)map_vsize: map unknown physical region to unknown virtual region
  */
 
+/* defined by arch */
 void map_vmem(struct vm_branch_t *branch,
 		pm_t paddr, vm_t vaddr,
 		uint8_t flags, enum mm_order_t order);
 
 void unmap_vmem(struct vm_branch_t *branch, vm_t vaddr, enum mm_order_t order);
 
-#define map_kvregion(b, pb, pt) map_vregion(b, pb, pt, VMEM_BASE, VMEM_TOP);
-#define map_uvregion(b, pb, pt) map_vregion(b, pb, pt, UMEM_BASE, UMEM_TOP);
-
-vm_t map_vregion(struct vm_branch_t *branch, pm_t base, pm_t top, vm_t start, vm_t end);
-void unmap_vregion(struct vm_branch_t *branch, pm_t base, pm_t top);
 
-vm_t map_vsize(struct vm_branch_t *branch, size_t size);
-void unmap_vsize(struct vm_branch_t *branch, size_t size);
+vm_t map_vregion(struct vm_branch_t *branch, pm_t base, vm_t start, size_t size,
+		uint8_t flags);
+void unmap_vregion(struct vm_branch_t *branch, vm_t start);
 
 #endif /* APOS_VMEM_H */