From 59a374b0eed4313d1a67e2cdb673a295e79a6494 Mon Sep 17 00:00:00 2001 From: Kimplul Date: Tue, 19 Oct 2021 15:56:26 +0300 Subject: Initial virtual memory mapping functions --- arch/riscv/common/vmem.c | 43 ++------ arch/riscv/include/vmem.h | 6 ++ common/mem.c | 1 + common/vmem.c | 260 ++++++++++++++++++++++++++++++++++++++++++++++ include/apos/mem.h | 7 +- include/apos/vmem.h | 13 ++- 6 files changed, 282 insertions(+), 48 deletions(-) create mode 100644 common/vmem.c 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 #include +#include #include 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 +#include +#include +#include + +/* 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 #include -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 + /* arch-specific data */ #include @@ -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 */ -- cgit v1.3