From 76517486919657ecadda9867125dc6730f29a5b7 Mon Sep 17 00:00:00 2001 From: Kimplul Date: Sat, 6 Jul 2024 18:14:04 +0300 Subject: pretty massive virtual memory rewrite + The system is now a bit simpler and hopefully easier to understand, while also extending the shared memory to be 1:N, where there is one owner who may become a zombie while waiting for the N to die. --- src/bkl.c | 9 + src/dispatch.c | 4 +- src/dmem.c | 100 ++----- src/elf.c | 6 +- src/main.c | 2 +- src/mem_nodes.c | 40 --- src/mem_regions.c | 582 ---------------------------------------- src/pmem.c | 2 +- src/proc.c | 15 +- src/regions.c | 761 ++++++++++++++++++++++++++++++++++++++++++++++++++++ src/tcb.c | 14 +- src/uapi/dispatch.c | 2 +- src/uapi/mem.c | 80 +++--- src/uapi/proc.c | 6 +- src/vmem.c | 427 ++++++++++------------------- 15 files changed, 1006 insertions(+), 1044 deletions(-) delete mode 100644 src/mem_nodes.c delete mode 100644 src/mem_regions.c create mode 100644 src/regions.c (limited to 'src') diff --git a/src/bkl.c b/src/bkl.c index 6dc120f..aa7bd53 100644 --- a/src/bkl.c +++ b/src/bkl.c @@ -1,3 +1,12 @@ +/* SPDX-License-Identifier: copyleft-next-0.3.1 */ +/* Copyright 2024, Kim Kuparinen < kimi.h.kuparinen@gmail.com > */ + #include +/** + * @file bkl.c + * + * Instanciation of the big kernel lock. + */ + spinlock_t bkl = 0; diff --git a/src/dispatch.c b/src/dispatch.c index 222611b..7b8d4cc 100644 --- a/src/dispatch.c +++ b/src/dispatch.c @@ -32,7 +32,7 @@ void dispatch(sys_arg_t a, sys_arg_t b, sys_arg_t c, sys_arg_t d, sys_arg_t e, sys_arg_t f) { - bkl_lock(); + bkl_lock(); handle_syscall(a, b, c, d, e, f, cur_tcb()); - bkl_unlock(); + bkl_unlock(); } diff --git a/src/dmem.c b/src/dmem.c index bbabe09..d5a3532 100644 --- a/src/dmem.c +++ b/src/dmem.c @@ -41,82 +41,30 @@ stat_t init_devmem(pm_t ram_base, pm_t ram_top) return OK; } -/** - * Device virtual memory worker callback for \ref map_fill_region(). - * - * @param b Virtual memory to work in. - * @param offset Hint for \ref alloc_page(). - * @param vaddr Current virtual address. - * @param flags Flags of region. - * @param order Suggested page order. - * @param data Pointer to \ref stat_t. - * @return \see alloc_uvmem_wrapper(). - * - * \see alloc_uvmem_wrapper(). - */ -static stat_t dev_alloc_wrapper(struct vmem *b, pm_t *offset, vm_t vaddr, - vmflags_t flags, enum mm_order order, - void *data) -{ - stat_t *status = (stat_t *)data; - /** \todo remember to do something with this status info */ - *status = map_vpage(b, *offset, vaddr, flags, order); - *offset += order_size(order); - return OK; -} - -/** - * Device virtual memory freeing worker callback for \ref map_fill_region(). - * - * @param b Virtual memory to work in. - * @param offset Hint for \ref alloc_page(). - * @param vaddr Current virtual address. - * @param flags Flags of region. - * @param order Suggested page order. - * @param data Pointer to \ref stat_t. - * @return \see alloc_uvmem_wrapper(). - * - * \see alloc_uvmem_wrapper(). - */ -static stat_t dev_free_wrapper(struct vmem *b, pm_t *offset, vm_t vaddr, - vmflags_t flags, enum mm_order order, void *data) -{ - UNUSED(offset); - UNUSED(flags); - pm_t paddr = 0; - enum mm_order v_order = 0; - stat_vpage(b, vaddr, &paddr, &v_order, 0); - if (order != v_order) - return INFO_TRGN; - - stat_t *status = (stat_t *)data; - *status = unmap_vpage(b, vaddr); - return OK; -} - vm_t alloc_devmem(struct tcb *t, pm_t dev_start, size_t bytes, vmflags_t flags) { hard_assert(t && is_proc(t), ERR_INVAL); - vm_t region = 0; + struct mem_region *region = NULL; if (dev_start < __pre_top) - region = alloc_region(&pre_ram, bytes, 0, flags); - - if (dev_start > __post_base) - region = alloc_region(&post_ram, bytes, 0, flags); + region = &pre_ram; - if (!region) + else if (dev_start > __post_base) + region = &post_ram; + else return NULL; - stat_t status = OK; - const vm_t w = map_fill_region(t->proc.vmem, &dev_alloc_wrapper, - dev_start, region, - bytes, flags, &status); + vm_t v = alloc_region(region, bytes, &bytes, flags); + if (!v) + return NULL; - if (status) + if (map_fixed_region(t->proc.vmem, v, dev_start, bytes, flags)) { + unmap_region(t->proc.vmem, v, bytes); + free_region(region, v); return NULL; + } - return w; + return v; } stat_t free_devmem(struct tcb *t, vm_t dev_start) @@ -131,24 +79,24 @@ stat_t free_devmem(struct tcb *t, vm_t dev_start) struct mem_region *m = 0; if (dev_paddr < __pre_top) - m = find_used_region(&pre_ram, dev_paddr); + m = find_used_region(&pre_ram, dev_start); - if (dev_paddr > __post_base) - m = find_used_region(&post_ram, dev_paddr); + else if (dev_paddr > __post_base) + m = find_used_region(&post_ram, dev_start); if (!m) return ERR_NF; - size_t region_size = __addr(m->end - m->start); - stat_t status = OK; - map_fill_region(t->proc.vmem, &dev_free_wrapper, dev_paddr, dev_start, - region_size, 0, &status); + vm_t start = __addr(m->start); + vm_t end = __addr(m->end); + size_t size = end - start; + unmap_fixed_region(t->proc.vmem, start, size); if (dev_paddr < __pre_top) - free_region(&pre_ram, dev_paddr); + free_region(&pre_ram, dev_start); - if (dev_paddr > __post_base) - free_region(&post_ram, dev_paddr); + else if (dev_paddr > __post_base) + free_region(&post_ram, dev_start); - return status; + return OK; } diff --git a/src/elf.c b/src/elf.c index da47502..a38f3c2 100644 --- a/src/elf.c +++ b/src/elf.c @@ -65,15 +65,15 @@ static void __map_exec(struct tcb *t, vm_t bin, uint8_t ei_c, vm_t phstart, vm_t va = program_header_prop(ei_c, runner, p_vaddr); size_t vsz = program_header_prop(ei_c, runner, p_memsz); - vm_t start = alloc_fixed_region(&t->sp_r, va, vsz, &vsz, - default_flags); + vm_t start = alloc_fixed_uvmem(t, va, vsz, default_flags); if (!start) return; /* out of memory or something */ uint8_t elf_flags = program_header_prop(ei_c, runner, p_flags); uint8_t uvflags = __elf_to_uvflags(elf_flags); - map_allocd_region(t->proc.vmem, start, vsz, default_flags, 0); + map_region(t->proc.vmem, start, vsz, max_order(), + default_flags); memset((void *)start, 0, vsz); vm_t vo = bin + program_header_prop(ei_c, runner, p_offset); diff --git a/src/main.c b/src/main.c index 33d9596..1f4c250 100644 --- a/src/main.c +++ b/src/main.c @@ -6,7 +6,7 @@ * Entry point for actual kernel setup. */ -#include +#include #include #include #include diff --git a/src/mem_nodes.c b/src/mem_nodes.c deleted file mode 100644 index 625b1a3..0000000 --- a/src/mem_nodes.c +++ /dev/null @@ -1,40 +0,0 @@ -/* SPDX-License-Identifier: copyleft-next-0.3.1 */ -/* Copyright 2021 - 2022, Kim Kuparinen < kimi.h.kuparinen@gmail.com > */ - -/** - * @file mem_nodes.c - * Memory node wrapper around the node subsystem, used by \ref - * src/mem_regions.c. - * - * Each region of memory is allocated through a \ref mem_region node, which is - * allocated through the node subsystem. - */ - -#include -#include -#include -#include -#include - -/** Memory node subsystem instance. */ -static struct node_root root; - -void init_mem_nodes() -{ - init_nodes(&root, sizeof(struct mem_region)); -} - -void destroy_mem_nodes() -{ - destroy_nodes(&root); -} - -struct mem_region *get_mem_node() -{ - return (struct mem_region *)get_node(&root); -} - -void free_mem_node(struct mem_region *m) -{ - free_node(&root, (void *)m); -} diff --git a/src/mem_regions.c b/src/mem_regions.c deleted file mode 100644 index 707c2f0..0000000 --- a/src/mem_regions.c +++ /dev/null @@ -1,582 +0,0 @@ -/* SPDX-License-Identifier: copyleft-next-0.3.1 */ -/* Copyright 2021 - 2022, Kim Kuparinen < kimi.h.kuparinen@gmail.com > */ - -/** - * @file mem_regions.c - * Memory region handling, used by both device memory and user virtual memory - * subsystems. - */ - -#include -#include -#include -#include -#include - -/** - * Readability wrapper for marking region used. - * - * @param r Region flags to set. - */ -#define mark_region_used(r) set_bit(r, MR_USED) - -/** - * Readability wrapper for marking region unused. - * - * @param r Region flags to clear. - */ -#define mark_region_unused(r) clear_bit(r, MR_USED) - -/* 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 - * - * 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? - */ - -/** - * Insert free memory region. - * - * @param r Memory region root to insert \c m into. - * @param m Free memory region to insert. - * @return \c m. - */ -static struct mem_region *__insert_free_region(struct mem_region_root *r, - struct mem_region *m) -{ - /* this could be simplified by using my gsptrees in kmx, but at least - * this ensures 'inlining' of the condition checking so I'll let it stay - * for now */ - struct sp_node *n = sp_root(&r->free_regions), *p = NULL; - vm_t start = m->start; - size_t size = m->end - m->start; - enum sp_dir d = SP_LEFT; - - m->sp_n = (struct sp_node){ 0 }; - - while (n) { - struct mem_region *t = mem_container(n); - size_t nsize = t->end - t->start; - p = n; - - if (size < nsize) { - n = sp_left(n); - d = SP_LEFT; - } - - else if (size > nsize) { - n = sp_right(n); - d = SP_RIGHT; - } - - else if (start < t->start) { - n = sp_left(n); - d = SP_LEFT; - } - - else { - n = sp_right(n); - d = SP_RIGHT; - } - } - - sp_insert(&sp_root(&r->free_regions), p, &m->sp_n, d); - return m; -} - -/** - * Insert used memory region. - * - * @param r Memory region root to insert \c m into. - * @param m Memory region to insert. - * @return \c m. - */ -static struct mem_region *__insert_used_region(struct mem_region_root *r, - struct mem_region *m) -{ - struct sp_node *n = sp_root(&r->used_regions), *p = NULL; - vm_t start = m->start; - enum sp_dir d = SP_LEFT; - - m->sp_n = (struct sp_node){ 0 }; - - while (n) { - struct mem_region *t = mem_container(n); - - p = n; - - if (start < t->start) { - n = sp_left(n); - d = SP_LEFT; - } - - else { - /* we should never encounter a situation where start = - * t->start */ - n = sp_right(n); - d = SP_RIGHT; - } - } - - sp_insert(&sp_root(&r->used_regions), p, &m->sp_n, d); - return m; -} - -stat_t init_region(struct mem_region_root *r, vm_t start, size_t arena_size) -{ - /* convert bytes to pages */ - start = __page(start); - arena_size = __page(arena_size); - struct mem_region *m = get_mem_node(); - m->start = start; - m->end = start + arena_size; - __insert_free_region(r, m); - - return OK; -} - -/** - * Destroy memory region and all its children. - * - * @param n \ref sp_node of memory region to destroy. - */ -static void __destroy_region(struct sp_node *n) -{ - if (!n) - return; - - if (sp_left(n)) - __destroy_region(sp_left(n)); - - if (sp_right(n)) - __destroy_region(sp_right(n)); - - struct mem_region *m = mem_container(n); - free_mem_node(m); -} - -stat_t destroy_region(struct mem_region_root *r) -{ - __destroy_region(sp_root(&r->free_regions)); - __destroy_region(sp_root(&r->used_regions)); - /** \todo error checking? */ - return OK; -} - -/* 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 - * */ -struct mem_region *find_used_region(struct mem_region_root *r, vm_t start) -{ - /** @todo check that start is aligned to page boundary? */ - vm_t ref = __page(start); - struct sp_node *n = sp_root(&r->used_regions); - while (n) { - struct mem_region *t = mem_container(n); - if (ref == t->start) - return t; - - if (ref < t->start) - n = sp_left(n); - else - n = sp_right(n); - } - - return 0; -} - -/** - * Create memory region. - * - * @param start Start of region. - * @param end End of region. - * @param prev Previous region. - * @param next Next region. - * @return Created region. - */ -static struct mem_region *__create_region(vm_t start, vm_t end, - struct mem_region *prev, - struct mem_region *next) -{ - struct mem_region *m = get_mem_node(); - m->start = start; - m->end = end; - m->prev = prev; - m->next = next; - return m; -} - -/** - * Get first order size smaller than \c s in bytes. - * - * @param s Size to look for. - * @return Size of first order smaller than \c s. - */ -static size_t po_align(size_t s) -{ - for (size_t o = __mm_max_order; o > 0; --o) { - if (s >= order_size(o)) - return order_size(o); - } - - return 0; -} - -struct mem_region *find_closest_used_region(struct mem_region_root *r, - vm_t start) -{ - struct mem_region *closest = 0; - size_t md = (size_t)(-1); - struct sp_node *n = sp_root(&r->used_regions); - if (!n) - return mem_container(sp_root(&r->free_regions)); - - while (n) { - struct mem_region *t = mem_container(n); - size_t d = ABS((ssize_t)start - (ssize_t)t->start); - - if (d == 0) /* exact match */ - return t; - - if (d < md) { /* closest so far */ - closest = t; - md = d; - } - - if (start < t->start) - n = sp_left(n); - else - n = sp_right(n); - } - - return closest; -} - -/* should probably document this a bit better but in short, look for the "best" - * free block, meaning one that is hopefully aligned so as to allow us to later - * map it to higher order pages. If no block is found such that that is - * possible, also keep track of the smallest block that we found that the region - * still fits in, unaligned. If none of these criteria are met, a NULL is - * returned. Note that this does not check *all* possible memory blocks, only - * going up in increasing size so as to save time. */ -struct mem_region *find_free_region(struct mem_region_root *r, size_t size, - size_t *align) -{ - *align = 0; - size_t offset = __page(po_align(__addr(size))); - struct mem_region *quick_best = 0; - struct sp_node *n = sp_root(&r->free_regions); - while (n) { - struct mem_region *t = mem_container(n); - vm_t start = align_up(t->start, offset); - - size_t qsize = t->end - t->start; - size_t bsize = t->end - start; - - if (!quick_best && size <= qsize) - quick_best = t; - - if (size <= bsize) { - *align = start - t->start; - return t; - } - - n = sp_right(n); - } - - return quick_best; -} - -struct mem_region *find_first_region(struct mem_region_root *r) -{ - /* get used region with smallest address, likely also close to the start - * of the linked list */ - struct mem_region *m = find_closest_used_region(r, 0); - while (m->prev) { - m = m->prev; - } - - return m; -} - -/** - * Carve out new used memory region from free memory region. - * - * @param r Memory region root to work in. - * @param m Free memory region to carve used memory region out of. - * @param pages Number of base order pages to give used region. - * @param align Alignment of used region. In this case, start of used region - * @param pid Process ID to associate with region if shared. 0 if private. - * from start of free region. - * @param flags Flags of used region. - * @return Start address of used region. - */ -static vm_t __partition_region(struct mem_region_root *r, struct mem_region *m, - size_t pages, size_t align, vmflags_t flags, - id_t pid) -{ - sp_remove(&sp_root(&r->free_regions), &m->sp_n); - - vm_t pre_start = m->start; - vm_t pre_end = pre_start + align; - - vm_t start = pre_end; - vm_t end = start + pages; - - vm_t post_start = end; - vm_t post_end = m->end; - - if (pre_start != pre_end) { - struct mem_region *n = - __create_region(pre_start, pre_end, m->prev, m); - m->prev = n; - if (n->prev) - n->prev->next = n; - - __insert_free_region(r, n); - } - - if (post_start != post_end) { - struct mem_region *n = - __create_region(post_start, post_end, m, m->next); - m->next = n; - if (n->next) - n->next->prev = n; - - __insert_free_region(r, n); - } - - m->end = end; - m->start = start; - m->flags = flags; - m->pid = pid; - mark_region_used(m->flags); - __insert_used_region(r, m); - return __addr(start); -} - -/* 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_shared_region(struct mem_region_root *r, size_t size, - size_t *actual_size, - vmflags_t flags, id_t pid) -{ - size_t asize = align_up(size, BASE_PAGE_SIZE); - if (actual_size) - *actual_size = asize; - - size_t pages = __page(asize); - - /* find best fitting, alignment etc. */ - size_t align = 0; - struct mem_region *m = find_free_region(r, pages, &align); - if (!m) - return 0; - - return __partition_region(r, m, pages, align, flags, pid); -} - -vm_t alloc_region(struct mem_region_root *r, size_t size, size_t *actual_size, - vmflags_t flags) -{ - return alloc_shared_region(r, size, actual_size, flags, 0); -} - -vm_t alloc_fixed_region(struct mem_region_root *r, vm_t start, size_t size, - size_t *actual_size, vmflags_t flags) -{ - size_t asize = align_up(size, BASE_PAGE_SIZE); - if (actual_size) - *actual_size = asize; - - size_t pages = __page(asize); - start = __page(start); - - struct mem_region *m = find_closest_used_region(r, start); - if (!m) - return 0; - - /* locate actual region where start is between the region start and end */ - while (!((m->start <= start) && (start < m->end))) { - if (start > m->start) - m = m->next; - else - m = m->prev; - } - - /* if region is already in use, forget it */ - if (is_region_used(m)) - return 0; - - /* region is too small */ - if (start + pages > m->end) - return 0; - - /* actually start marking region used */ - return __partition_region(r, m, pages, start - m->start, flags, 0); -} - -/** - * Try to coalesce two adjacent memory regions, iterating left. - * - * @param r Memory region root to work in. - * @param m Memory region to start trying to coalesce. - */ -static void __try_coalesce_prev(struct mem_region_root *r, struct mem_region *m) -{ - while (m) { - if (!m || is_region_used(m)) - return; - - struct mem_region *p = m->prev; - if (!p || is_region_used(p)) - return; - - m->start = p->start; - m->prev = p->prev; - - if (m->prev) - m->prev->next = m; - - sp_remove(&sp_root(&r->free_regions), &p->sp_n); - free_mem_node(p); - - m = m->prev; - } -} - -/** - * Try to coalesce two adjacent memory region, iterating right. - * - * @param r Memory region root to work in. - * @param m Memory region to start trying to coalesce. - */ -static void __try_coalesce_next(struct mem_region_root *r, struct mem_region *m) -{ - while (m) { - if (!m || is_region_used(m)) - return; - - struct mem_region *n = m->next; - if (!n || is_region_used(n)) - return; - - m->end = n->end; - m->next = n->next; - - if (m->next) - m->next->prev = m; - - sp_remove(&sp_root(&r->free_regions), &n->sp_n); - free_mem_node(n); - - m = m->next; - } -} - -/** - * Try coalescing memory regions. - * - * @param r Memory region root to work in. - * @param m Memory region to start trying to coalesce. - */ -static void __try_coalesce_regions(struct mem_region_root *r, - struct mem_region *m) -{ - __try_coalesce_prev(r, m); - __try_coalesce_next(r, m); -} - -stat_t free_region(struct mem_region_root *r, vm_t start) -{ - /* addr not aligned to page boundary, corrupted or incorrect pointer */ - if (!is_aligned(start, BASE_PAGE_SIZE)) - return ERR_ALIGN; - - struct mem_region *m = find_used_region(r, start); - if (!m) - return ERR_NF; - - return free_known_region(r, m); -} - -stat_t free_known_region(struct mem_region_root *r, struct mem_region *m) -{ - sp_remove(&sp_root(&r->used_regions), &m->sp_n); - mark_region_unused(m->flags); - - __try_coalesce_regions(r, m); - __insert_free_region(r, m); - return OK; -} - -void set_alt_region_addr(struct mem_region_root *r, vm_t va, vm_t alt_va) -{ - struct mem_region *m = find_used_region(r, va); - if (!m) - return; - - /* not shared region */ - if (m->pid == 0) - return; - - m->alt_va = alt_va; -} - -/* assuming start is chosen to start on an aligned border, this should choose - * the 'optimal' fit for the mapping. - * - * NOTE: not actually optimal, this doesn't bother to go through possible - * permutations etc. which would be slow and I don't want to implement it. - */ -vm_t map_fill_region(struct vmem *b, region_callback_t *mem_handler, - pm_t offset, vm_t start, size_t bytes, vmflags_t flags, - void *data) -{ - pm_t runner = __page(start); - size_t pages = __pages(bytes); - enum mm_order top = __mm_max_order; - - /* actual start might not be the same as the user specified start */ - start = __addr(runner); - - for (; pages; top--) { - size_t o_size = order_size(top); - size_t o_pages = __pages(o_size); - - /* NULL does pass this check, so technically all NULL pages are - * aligned, but they're caught in the while expr so this should - * work even if someone tries to map NULL */ - if (!is_aligned(runner, o_pages)) - continue; - - while (pages >= o_pages) { - stat_t res = mem_handler(b, &offset, __addr(runner), - flags, top, data); - if (res > 0) - break; - - if (res < 0) - return 0; - - pages -= o_pages; - runner += o_pages; - } - } - - return start; -} diff --git a/src/pmem.c b/src/pmem.c index dd10768..91aff5a 100644 --- a/src/pmem.c +++ b/src/pmem.c @@ -15,11 +15,11 @@ * now. */ -#include #include #include #include #include +#include #include /* memset */ #include /* is_nset etc */ #include diff --git a/src/proc.c b/src/proc.c index 61dd125..eff962a 100644 --- a/src/proc.c +++ b/src/proc.c @@ -49,7 +49,8 @@ stat_t init_proc(void *fdt, vm_t *proc_fdt, vm_t *proc_initrd) /* init process has all capabilities */ set_caps(t->caps, 0, - CAP_CAPS | CAP_PROC | CAP_SIGNAL | CAP_POWER | CAP_NOTIFY); + CAP_CAPS | CAP_PROC | CAP_SIGNAL | CAP_POWER | CAP_NOTIFY | + CAP_SHARED); /* we shall try to map the fdt and initrd into the new address space, so * save them here before we switch */ @@ -61,14 +62,14 @@ stat_t init_proc(void *fdt, vm_t *proc_fdt, vm_t *proc_initrd) /** \todo start one thread per core, with special handling for init in * that each thread starts at the entry point of init? */ - *proc_fdt = map_fixed_mem(t, - (pm_t)fdt, fdt_totalsize(fdt), - VM_V | VM_R | VM_U); + *proc_fdt = map_fixed_uvmem(t, + (pm_t)fdt, fdt_totalsize(fdt), + VM_V | VM_R | VM_U); pm_t initrd = (pm_t)__va(get_initrdbase(fdt)); - *proc_initrd = map_fixed_mem(t, - initrd, get_initrdsize(fdt), - VM_V | VM_R | VM_U); + *proc_initrd = map_fixed_uvmem(t, + initrd, get_initrdsize(fdt), + VM_V | VM_R | VM_U); info("mapped fdt at %lx\n", *proc_fdt); info("mapped initrd at %lx\n", *proc_initrd); diff --git a/src/regions.c b/src/regions.c new file mode 100644 index 0000000..66ee546 --- /dev/null +++ b/src/regions.c @@ -0,0 +1,761 @@ +/* SPDX-License-Identifier: copyleft-next-0.3.1 */ +/* Copyright 2021 - 2022, Kim Kuparinen < kimi.h.kuparinen@gmail.com > */ + +/** + * @file regions.c + * Memory region handling, used by both device memory and user virtual memory + * subsystems. + */ + +#include +#include +#include +#include +#include + +/** Memory node "subsystem" instance. */ +static struct node_root root; + +void init_mem_nodes() +{ + init_nodes(&root, sizeof(struct mem_region)); +} + +void destroy_mem_nodes() +{ + destroy_nodes(&root); +} + +/** + * Allocate a new memory region node and return it. + * + * @return New memory region node. + */ +static struct mem_region *get_mem_node() +{ + return (struct mem_region *)get_node(&root); +} + +/** + * Free a memory region node. + * + * @param m Memory region node to free. + */ +static void free_mem_node(struct mem_region *m) +{ + free_node(&root, (void *)m); +} + +/** + * Readability wrapper for marking region used. + * + * @param r Region flags to set. + */ +#define mark_region_used(r) set_bit(r, MR_USED) + +/** + * Readability wrapper for marking region unused. + * + * @param r Region flags to clear. + */ +#define mark_region_unused(r) clear_bit(r, MR_USED) + +/* 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 + * + * 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? + */ + +/** + * Insert free memory region. + * + * @param r Memory region root to insert \c m into. + * @param m Free memory region to insert. + * @return \c m. + */ +static struct mem_region *__insert_free_region(struct mem_region_root *r, + struct mem_region *m) +{ + /* this could be simplified by using my gsptrees in kmx, but at least + * this ensures 'inlining' of the condition checking so I'll let it stay + * for now */ + struct sp_node *n = sp_root(&r->free_regions), *p = NULL; + vm_t start = m->start; + size_t size = m->end - m->start; + enum sp_dir d = SP_LEFT; + + m->sp_n = (struct sp_node){ 0 }; + + while (n) { + struct mem_region *t = mem_container(n); + size_t nsize = t->end - t->start; + p = n; + + if (size < nsize) { + n = sp_left(n); + d = SP_LEFT; + } + + else if (size > nsize) { + n = sp_right(n); + d = SP_RIGHT; + } + + else if (start < t->start) { + n = sp_left(n); + d = SP_LEFT; + } + + else { + n = sp_right(n); + d = SP_RIGHT; + } + } + + sp_insert(&sp_root(&r->free_regions), p, &m->sp_n, d); + return m; +} + +/** + * Insert used memory region. + * + * @param r Memory region root to insert \c m into. + * @param m Memory region to insert. + * @return \c m. + */ +static struct mem_region *__insert_used_region(struct mem_region_root *r, + struct mem_region *m) +{ + struct sp_node *n = sp_root(&r->used_regions), *p = NULL; + vm_t start = m->start; + enum sp_dir d = SP_LEFT; + + m->sp_n = (struct sp_node){ 0 }; + + while (n) { + struct mem_region *t = mem_container(n); + + p = n; + + if (start < t->start) { + n = sp_left(n); + d = SP_LEFT; + } + + else { + /* we should never encounter a situation where start = + * t->start */ + n = sp_right(n); + d = SP_RIGHT; + } + } + + sp_insert(&sp_root(&r->used_regions), p, &m->sp_n, d); + return m; +} + +stat_t init_region(struct mem_region_root *r, vm_t start, size_t arena_size) +{ + /* convert bytes to pages */ + start = __page(start); + arena_size = __page(arena_size); + struct mem_region *m = get_mem_node(); + m->start = start; + m->end = start + arena_size; + __insert_free_region(r, m); + + return OK; +} + +/** + * Destroy memory region and all its children. + * + * @param n \ref sp_node of memory region to destroy. + */ +static void __destroy_region(struct sp_node *n) +{ + if (!n) + return; + + if (sp_left(n)) + __destroy_region(sp_left(n)); + + if (sp_right(n)) + __destroy_region(sp_right(n)); + + struct mem_region *m = mem_container(n); + free_mem_node(m); +} + +stat_t destroy_region(struct mem_region_root *r) +{ + __destroy_region(sp_root(&r->free_regions)); + __destroy_region(sp_root(&r->used_regions)); + /** \todo error checking? */ + return OK; +} + +/* 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 + * */ +struct mem_region *find_used_region(struct mem_region_root *r, vm_t start) +{ + /** @todo check that start is aligned to page boundary? */ + vm_t ref = __page(start); + struct sp_node *n = sp_root(&r->used_regions); + while (n) { + struct mem_region *t = mem_container(n); + if (ref == t->start) + return t; + + if (ref < t->start) + n = sp_left(n); + else + n = sp_right(n); + } + + return 0; +} + +/** + * Create memory region. + * + * @param start Start of region. + * @param end End of region. + * @param prev Previous region. + * @param next Next region. + * @return Created region. + */ +static struct mem_region *__create_region(vm_t start, vm_t end, + struct mem_region *prev, + struct mem_region *next) +{ + struct mem_region *m = get_mem_node(); + m->start = start; + m->end = end; + m->prev = prev; + m->next = next; + return m; +} + +/** + * Get first order size smaller than \c s in bytes. + * + * @param s Size to look for. + * @return Size of first order smaller than \c s. + */ +static size_t po_align(size_t s) +{ + for (size_t o = __mm_max_order; o > 0; --o) { + if (s >= order_size(o)) + return order_size(o); + } + + return 0; +} + +struct mem_region *find_closest_used_region(struct mem_region_root *r, + vm_t start) +{ + struct mem_region *closest = 0; + size_t md = (size_t)(-1); + struct sp_node *n = sp_root(&r->used_regions); + if (!n) + return mem_container(sp_root(&r->free_regions)); + + while (n) { + struct mem_region *t = mem_container(n); + size_t d = ABS((ssize_t)start - (ssize_t)t->start); + + if (d == 0) /* exact match */ + return t; + + if (d < md) { /* closest so far */ + closest = t; + md = d; + } + + if (start < t->start) + n = sp_left(n); + else + n = sp_right(n); + } + + return closest; +} + +/* should probably document this a bit better but in short, look for the "best" + * free block, meaning one that is hopefully aligned so as to allow us to later + * map it to higher order pages. If no block is found such that that is + * possible, also keep track of the smallest block that we found that the region + * still fits in, unaligned. If none of these criteria are met, a NULL is + * returned. Note that this does not check *all* possible memory blocks, only + * going up in increasing size so as to save time. */ +struct mem_region *find_free_region(struct mem_region_root *r, size_t size, + size_t *align) +{ + *align = 0; + size_t offset = __page(po_align(__addr(size))); + struct mem_region *quick_best = 0; + struct sp_node *n = sp_root(&r->free_regions); + while (n) { + struct mem_region *t = mem_container(n); + vm_t start = align_up(t->start, offset); + + size_t qsize = t->end - t->start; + size_t bsize = t->end - start; + + if (!quick_best && size <= qsize) + quick_best = t; + + if (size <= bsize) { + *align = start - t->start; + return t; + } + + n = sp_right(n); + } + + return quick_best; +} + +struct mem_region *find_first_region(struct mem_region_root *r) +{ + /* get used region with smallest address, likely also close to the start + * of the linked list */ + struct mem_region *m = find_closest_used_region(r, 0); + while (m->prev) { + m = m->prev; + } + + return m; +} + +/** + * Carve out new used memory region from free memory region. + * + * @param r Memory region root to work in. + * @param m Free memory region to carve used memory region out of. + * @param pages Number of base order pages to give used region. + * @param align Alignment of used region. In this case, start of used region + * @param pid Process ID to associate with region if shared. 0 if private. + * from start of free region. + * @param flags Flags of used region. + * @return Start address of used region. + */ +static vm_t __partition_region(struct mem_region_root *r, struct mem_region *m, + size_t pages, size_t align, vmflags_t flags, + id_t pid) +{ + sp_remove(&sp_root(&r->free_regions), &m->sp_n); + + vm_t pre_start = m->start; + vm_t pre_end = pre_start + align; + + vm_t start = pre_end; + vm_t end = start + pages; + + vm_t post_start = end; + vm_t post_end = m->end; + + if (pre_start != pre_end) { + struct mem_region *n = + __create_region(pre_start, pre_end, m->prev, m); + m->prev = n; + if (n->prev) + n->prev->next = n; + + __insert_free_region(r, n); + } + + if (post_start != post_end) { + struct mem_region *n = + __create_region(post_start, post_end, m, m->next); + m->next = n; + if (n->next) + n->next->prev = n; + + __insert_free_region(r, n); + } + + m->end = end; + m->start = start; + m->flags = flags; + m->pid = pid; + mark_region_used(m->flags); + __insert_used_region(r, m); + return __addr(start); +} + +vm_t alloc_shared_region(struct mem_region_root *r, size_t size, + size_t *actual_size, + vmflags_t flags, id_t pid) +{ + size_t asize = align_up(size, BASE_PAGE_SIZE); + if (actual_size) + *actual_size = asize; + + size_t pages = __page(asize); + + /* find best fitting, alignment etc. */ + size_t align = 0; + struct mem_region *m = find_free_region(r, pages, &align); + if (!m) + return 0; + + return __partition_region(r, m, pages, align, flags, pid); +} + +vm_t alloc_region(struct mem_region_root *r, size_t size, size_t *actual_size, + vmflags_t flags) +{ + return alloc_shared_region(r, size, actual_size, flags, 0); +} + +vm_t alloc_fixed_region(struct mem_region_root *r, vm_t start, size_t size, + size_t *actual_size, vmflags_t flags) +{ + size_t asize = align_up(size, BASE_PAGE_SIZE); + if (actual_size) + *actual_size = asize; + + size_t pages = __page(asize); + start = __page(start); + + struct mem_region *m = find_closest_used_region(r, start); + if (!m) + return 0; + + /* locate actual region where start is between the region start and end */ + while (!((m->start <= start) && (start < m->end))) { + if (start > m->start) + m = m->next; + else + m = m->prev; + } + + /* if region is already in use, forget it */ + if (is_region_used(m)) + return 0; + + /* region is too small */ + if (start + pages > m->end) + return 0; + + /* actually start marking region used */ + return __partition_region(r, m, pages, start - m->start, flags, 0); +} + +/** + * Try to coalesce two adjacent memory regions, iterating left. + * + * @param r Memory region root to work in. + * @param m Memory region to start trying to coalesce. + */ +static void __try_coalesce_prev(struct mem_region_root *r, struct mem_region *m) +{ + while (m) { + if (!m || is_region_used(m)) + return; + + struct mem_region *p = m->prev; + if (!p || is_region_used(p)) + return; + + m->start = p->start; + m->prev = p->prev; + + if (m->prev) + m->prev->next = m; + + sp_remove(&sp_root(&r->free_regions), &p->sp_n); + free_mem_node(p); + + m = m->prev; + } +} + +/** + * Try to coalesce two adjacent memory region, iterating right. + * + * @param r Memory region root to work in. + * @param m Memory region to start trying to coalesce. + */ +static void __try_coalesce_next(struct mem_region_root *r, struct mem_region *m) +{ + while (m) { + if (!m || is_region_used(m)) + return; + + struct mem_region *n = m->next; + if (!n || is_region_used(n)) + return; + + m->end = n->end; + m->next = n->next; + + if (m->next) + m->next->prev = m; + + sp_remove(&sp_root(&r->free_regions), &n->sp_n); + free_mem_node(n); + + m = m->next; + } +} + +/** + * Try coalescing memory regions. + * + * @param r Memory region root to work in. + * @param m Memory region to start trying to coalesce. + */ +static void __try_coalesce_regions(struct mem_region_root *r, + struct mem_region *m) +{ + /** @todo might free mem and then reuse it, not good */ + __try_coalesce_prev(r, m); + __try_coalesce_next(r, m); +} + +stat_t free_region(struct mem_region_root *r, vm_t start) +{ + /* addr not aligned to page boundary, corrupted or incorrect pointer */ + if (!is_aligned(start, BASE_PAGE_SIZE)) + return ERR_ALIGN; + + struct mem_region *m = find_used_region(r, start); + if (!m) + return ERR_NF; + + free_known_region(r, m); + return OK; +} + +void free_known_region(struct mem_region_root *r, struct mem_region *m) +{ + sp_remove(&sp_root(&r->used_regions), &m->sp_n); + mark_region_unused(m->flags); + + __try_coalesce_regions(r, m); + __insert_free_region(r, m); +} + +/** + * Align region starting at \p start of size \p bytes to start and end on + * BASE_PAGE boundaries. Place new start and size into \p startp and \p bytesp. + * + * @param start Start of region. + * @param bytes Size of region. + * @param startp Where to place new start. + * @param bytesp Where to place new size. + */ +static void align_region(vm_t start, size_t bytes, vm_t *startp, size_t *bytesp) +{ + size_t shift = order_shift(BASE_PAGE); + vm_t top = start + bytes; + /* reasonably fast align down */ + vm_t new_start = (start >> shift) << shift; + + /* to align up, we must first align down */ + vm_t new_top = ((top >> shift) << shift); + + /* if alignment did something, add a base page size to align up */ + if (new_top != top) + new_top += BASE_PAGE_SIZE; + + /* difference between top and start */ + size_t new_bytes = new_top - new_start; + + *startp = new_start; + *bytesp = new_bytes; +} + +/* assuming start is chosen to start on an aligned border, this should choose + * the 'optimal' fit for the mapping. + * + * NOTE: not actually optimal, this doesn't bother to go through possible + * permutations etc. which would be slow and I don't want to implement it. + */ +stat_t map_region(struct vmem *b, vm_t start, size_t bytes, enum mm_order order, + vmflags_t flags) +{ + /* adjust to nearest page sizes */ + align_region(start, bytes, &start, &bytes); + + size_t size = order_size(order); + while (bytes) { + if (size > bytes) + goto next_order; + + /* NULL does pass this check, so technically all NULL pages are + * aligned, but they're caught in the while expr so this should + * work even if someone tries to map NULL */ + if (!is_aligned(start, size)) + goto next_order; + + pm_t page = alloc_page(order); + if (!page) + goto next_order; + + stat_t res = map_vpage(b, page, start, flags, order); + if (res) + goto next_order; + + + start += size; + bytes -= size; + continue; + +next_order: + /* ran out of orders, stop */ + if (order == 0) + return ERR_MISC; + + order--; + size = order_size(order); + } + + return OK; +} + +stat_t map_fixed_region(struct vmem *b, vm_t v, pm_t start, size_t bytes, + vmflags_t flags) +{ + /* adjust to nearest page sizes, generally the region should be on a + * BASE_PAGE boundary but just to be safe */ + v = align_down(v, BASE_PAGE_SIZE); + align_region(start, bytes, &start, &bytes); + + size_t size = BASE_PAGE_SIZE; + while (bytes) { + stat_t ret = map_vpage(b, start, v, flags, BASE_PAGE); + if (ret) + return ret; + + start += size; + bytes -= size; + v += size; + } + + return OK; +} + +stat_t clone_region(struct vmem *b, struct vmem *g, vm_t from, vm_t to, + size_t bytes, vmflags_t flags) +{ + size_t from_size = 0; size_t to_size = 0; + align_region(from, bytes, &from, &from_size); + align_region(to, bytes, &to, &to_size); + + catastrophic_assert(from_size == to_size); + bytes = from_size; + + while (bytes) { + pm_t addr = 0; + enum mm_order order = BASE_PAGE; + stat_t res = stat_vpage(g, from, &addr, &order, NULL); + if (res) + return res; + + res = map_vpage(b, addr, to, flags, order); + if (res) + return res; + + size_t size = order_size(order); + bytes -= size; + from += size; + to += size; + } + + return OK; +} + +stat_t copy_region(struct vmem *b, struct vmem *g, vm_t from, vm_t to, + size_t bytes) +{ + size_t from_size = 0; size_t to_size = 0; + align_region(from, bytes, &from, &from_size); + align_region(to, bytes, &to, &to_size); + + catastrophic_assert(from_size == to_size); + bytes = from_size; + + while (bytes) { + pm_t addr = 0; + vmflags_t flags = 0; + enum mm_order order = BASE_PAGE; + stat_t res = stat_vpage(g, from, &addr, &order, &flags); + if (res) + return res; + + pm_t page = alloc_page(order); + if (!page) + return ERR_OOMEM; + + /* temporarily give us write permissions */ + res = map_vpage(b, page, to, flags, order); + if (res) { + free_page(order, page); + return res; + } + + size_t size = order_size(order); + memcpy((void *)page, (void *)addr, size); + bytes -= size; + from += size; + to += size; + } + + return OK; +} + +void unmap_region(struct vmem *b, vm_t v, size_t bytes) +{ + v = align_down(v, BASE_PAGE_SIZE); + bytes = align_up(v + bytes, BASE_PAGE_SIZE) - v; + while (bytes) { + pm_t addr = 0; + enum mm_order order = BASE_PAGE; + stat_t res = stat_vpage(b, v, &addr, &order, NULL); + if (res) + return; + + unmap_vpage(b, v); + free_page(order, addr); + size_t size = order_size(order); + bytes -= size; + v += size; + } +} + +void unmap_fixed_region(struct vmem *b, vm_t v, size_t bytes) +{ + v = align_down(v, BASE_PAGE_SIZE); + bytes = align_up(v + bytes, BASE_PAGE_SIZE) - v; + while (bytes) { + pm_t addr = 0; + enum mm_order order = BASE_PAGE; + stat_t res = stat_vpage(b, v, &addr, &order, NULL); + if (res) + return; + + unmap_vpage(b, v); + size_t size = order_size(order); + bytes -= size; + v += size; + } +} diff --git a/src/tcb.c b/src/tcb.c index ba134c6..51aa939 100644 --- a/src/tcb.c +++ b/src/tcb.c @@ -136,8 +136,8 @@ struct tcb *create_thread(struct tcb *p) * systems don't we can easily turn this into a clone_uvmem. */ t->proc.vmem = p->proc.vmem; } else { - init_uvmem(t, UVMEM_START, UVMEM_END); t->proc.vmem = create_vmem(); + init_uvmem(t, UVMEM_START, UVMEM_END); t->pid = t->tid; t->rid = t->tid; p = t; @@ -173,9 +173,9 @@ static stat_t __copy_proc(struct tcb *p, struct tcb *n) n->thread_stack = p->thread_stack; n->thread_stack_top = p->thread_stack_top; - clone_regs(n, p); + copy_regs(n, p); copy_caps(n->caps, p->caps); - return clone_mem_regions(n, p); + return copy_uvmem(n, p); } struct tcb *create_proc(struct tcb *p) @@ -214,12 +214,14 @@ static stat_t __destroy_thread_data(struct tcb *t) * some kind of lock that checks that nobody reads the value while we're * setting it to zero. get_tcb() should accordingly increment the * reference count atomically. Also, an unget_tcb() is needed to - * decrement the reference count I guess? */ + * decrement the reference count I guess? if we didn't have the BKL that + * is + */ tcbs[t->tid] = 0; - /* forcefully free last struggling bits of memory */ + /* forcefully free last struggling bits of memory, assuming we own the + * uvmem */ destroy_uvmem(t); - destroy_vmem(t->proc.vmem); /* free associated kernel stack and the structure itself */ vm_t bottom = align_down((vm_t)t, order_size(MM_O0)); diff --git a/src/uapi/dispatch.c b/src/uapi/dispatch.c index c4ad811..b5dbda2 100644 --- a/src/uapi/dispatch.c +++ b/src/uapi/dispatch.c @@ -49,10 +49,10 @@ void handle_syscall(sys_arg_t syscall, sys_arg_t a, sys_arg_t b, case SYS_NOOP: sys_noop(t, a, b, c, d, e); break; case SYS_PUTCH: sys_putch(t, a, b, c, d, e); break; case SYS_REQ_MEM: sys_req_mem(t, a, b, c, d, e); break; - case SYS_REQ_PAGE: sys_req_page(t, a, b, c, d, e); break; case SYS_REQ_PMEM: sys_req_pmem(t, a, b, c, d, e); break; case SYS_REQ_FIXMEM: sys_req_fixmem(t, a, b, c, d, e); break; case SYS_REQ_SHAREDMEM: sys_req_sharedmem(t, a, b, c, d, e); break; + case SYS_REF_SHAREDMEM: sys_ref_sharedmem(t, a, b, c, d, e); break; case SYS_FREE_MEM: sys_free_mem(t, a, b, c, d, e); break; case SYS_TIMEBASE: sys_timebase(t, a, b, c, d, e); break; case SYS_TICKS: sys_ticks(t, a, b, c, d, e); break; diff --git a/src/uapi/mem.c b/src/uapi/mem.c index d54390a..932027b 100644 --- a/src/uapi/mem.c +++ b/src/uapi/mem.c @@ -25,31 +25,13 @@ SYSCALL_DEFINE2(req_mem)(struct tcb *t, sys_arg_t size, sys_arg_t flags) { struct tcb *r = get_cproc(t); vm_t start = 0; - /** @todo expose flags to users */ + flags = sanitize_uvflags(flags); if (!(start = alloc_uvmem(r, size, flags))) return_args1(t, ERR_OOMEM); return_args2(t, OK, start); } -/** - * Allocate single page to program. - * - * @param t Current tcb. - * @param size Size of the allocation. - * @param flags Flags of allocation. - * @return \ref ERR_OOMEM if unsucessful, otherwise \ref OK, virtual address, - * actual size, physical address, in that order. - */ -SYSCALL_DEFINE2(req_page)(struct tcb *t, sys_arg_t size, sys_arg_t flags) -{ - struct tcb *r = get_cproc(t); - vm_t start = 0; pm_t paddr = 0; size_t asize = size; - if (!(start = alloc_uvpage(r, asize, flags, &asize, &paddr))) - return_args1(t, ERR_OOMEM); - - return_args4(t, OK, start, asize, paddr); -} /** * Fixed memory request syscall handler. @@ -66,6 +48,7 @@ SYSCALL_DEFINE3(req_fixmem)(struct tcb *t, sys_arg_t fixed, sys_arg_t size, { struct tcb *r = get_cproc(t); vm_t start = 0; + flags = sanitize_uvflags(flags); if (!(start = alloc_fixed_uvmem(r, fixed, size, flags))) return_args1(t, ERR_OOMEM); @@ -116,6 +99,7 @@ SYSCALL_DEFINE3(req_pmem)(struct tcb *t, sys_arg_t paddr, sys_arg_t size, */ struct tcb *r = get_cproc(t); vm_t start = 0; + flags = sanitize_uvflags(flags); if (!(start = alloc_devmem(r, paddr, size, flags))) return_args1(t, ERR_OOMEM); @@ -126,33 +110,51 @@ SYSCALL_DEFINE3(req_pmem)(struct tcb *t, sys_arg_t paddr, sys_arg_t size, * Request shared memory syscall handler. * * @param t Current tcb. - * @param tid Thread to share memory with. * @param size Minimum size of allocation. - * @param sflags Flags of allocation for \p t. - * @param cflags Flags of allocation for \p tid. - * @return \ref OK and start of \p t allocation and start of \p tid allocation, + * @param flags Flags of allocation. + * @return \ref OK, start and size * in that order, \ref ERR_OOMEM otherwise. + */ +SYSCALL_DEFINE2(req_sharedmem)(struct tcb *t, sys_arg_t size, sys_arg_t flags) +{ + struct tcb *c = get_cproc(t); + if (!has_cap(c->caps, CAP_SHARED)) + return_args1(t, ERR_PERM); + + vm_t start = 0; + flags = sanitize_uvflags(flags); + if (!(start = alloc_shared_uvmem(c, size, flags))) + return_args1(t, ERR_OOMEM); + + return_args3(t, OK, start, size); +} + +/** + * Reference shared memory. * - * @todo should we also take the thread who should get the other end of the - * memory? + * @param t Current tcb. + * @param tid In which thread's address space to create mapping. + * @param addr Address of shared region in \p t. + * @param flags Flags of allocation. + * @return \ref ERR_OOMEM if unsucessful, otherwise \ref OK, virtual address, + * actual size, in that order. Generally the actual size should match with the + * original shared region, but I wouldn't count on it. */ -SYSCALL_DEFINE4(req_sharedmem)(struct tcb *t, sys_arg_t tid, - sys_arg_t size, sys_arg_t sflags, - sys_arg_t cflags) +SYSCALL_DEFINE3(ref_sharedmem)(struct tcb *t, sys_arg_t tid, sys_arg_t addr, + sys_arg_t flags) { - /** @todo check capability for shared memory */ - struct tcb *u = get_tcb(tid); - if (!u) - return_args1(t, ERR_INVAL); + struct tcb *c = get_cproc(t); + if (!has_cap(c->caps, CAP_SHARED)) + return_args1(t, ERR_PERM); - struct tcb *s = get_cproc(t); - struct tcb *c = get_rproc(u); + struct tcb *r = get_tcb(tid); + if (!r || zombie(r)) + return_args1(t, ERR_INVAL); - vm_t sstart, cstart; - if (alloc_shared_uvmem(s, c, size, sflags, cflags, &sstart, &cstart)) + vm_t start = 0; size_t size = 0; + flags = sanitize_uvflags(flags); + if (!(start = ref_shared_uvmem(r, c, addr, flags))) return_args1(t, ERR_OOMEM); - return_args3(t, OK, sstart, cstart); + return_args3(t, OK, start, size); } - -/** \todo add some way to specify who gets to access the shared memory? */ diff --git a/src/uapi/proc.c b/src/uapi/proc.c index 85acb29..ff02113 100644 --- a/src/uapi/proc.c +++ b/src/uapi/proc.c @@ -13,7 +13,7 @@ #include #include #include -#include +#include #include @@ -100,7 +100,7 @@ SYSCALL_DEFINE2(exec)(struct tcb *t, sys_arg_t bin, sys_arg_t interp) return_args1(t, ERR_INVAL); /* mark binary to be kept */ - struct mem_region *b = find_used_region(&t->sp_r, bin); + struct mem_region *b = find_used_region(&t->uvmem.region, bin); if (!b) return_args1(t, ERR_ADDR); @@ -109,7 +109,7 @@ SYSCALL_DEFINE2(exec)(struct tcb *t, sys_arg_t bin, sys_arg_t interp) struct mem_region *i = 0; if (interp) { /* mark interpreter to be kept */ - i = find_used_region(&t->sp_r, interp); + i = find_used_region(&t->uvmem.region, interp); if (!i) return_args1(t, ERR_INVAL); diff --git a/src/vmem.c b/src/vmem.c index f1841e4..c713ced 100644 --- a/src/vmem.c +++ b/src/vmem.c @@ -6,7 +6,7 @@ * Virtual memory handling, mainly userspace virtual memory. */ -#include +#include #include #include #include @@ -16,7 +16,9 @@ stat_t init_uvmem(struct tcb *t, vm_t base, vm_t top) { - return init_region(&t->sp_r, base, top); + t->uvmem.owner = t->tid; + t->uvmem.vmem = t->proc.vmem; + return init_region(&t->uvmem.region, base, top); } /** @@ -29,63 +31,70 @@ stat_t init_uvmem(struct tcb *t, vm_t base, vm_t top) * * @todo check shared memory regions. */ -static stat_t __clone_mapped_region(struct tcb *d, struct tcb *s, - struct mem_region *m) +static stat_t __copy_mapped_region(struct tcb *d, struct tcb *s, + struct mem_region *m) { vm_t start = m->start * order_size(BASE_PAGE); vm_t end = m->end * order_size(BASE_PAGE); - size_t size = end - start, actual_size = 0; - vm_t va = alloc_fixed_region(&d->sp_r, start, size, - &actual_size, m->flags); - - catastrophic_assert(va == start); - - if (!copy_allocd_region(d->proc.vmem, va, size, m->flags, s->proc.vmem)) - return ERR_MISC; - - return OK; + size_t size = end - start; + vm_t v = alloc_fixed_region(&d->uvmem.region, start, size, &size, + m->flags); + catastrophic_assert(v == start); + stat_t res = copy_region(d->proc.vmem, s->proc.vmem, v, v, size); + if (res == OK) + return OK; + + /* cleanup on error */ + free_region(&d->uvmem.region, v); + unmap_region(d->proc.vmem, v, size); + return res; } /** - * Unmap and free private memory region. + * Helper for implementing shared memory. * - * @param t Current thread. - * @param m Memory region to free. - * @return \see unmap_freed_region(). + * @param d 'Destination' of new mapping. + * @param s Owner of shared region. + * @param m Shared memory region to clone. + * @param flags Flags of new mapping. + * @return Address of new mapping in \p d. */ -static stat_t __free_mapped_private_region(struct tcb *t, struct mem_region *m) +static vm_t __clone_shared_region(struct tcb *d, struct tcb *s, + struct mem_region *m, vmflags_t flags) { - stat_t status = OK; - pm_t start = __addr(m->start); - pm_t end = __addr(m->end); - if (!unmap_freed_region(t->proc.vmem, start, end - start, m->flags, - &status)) - return ERR_MISC; - - return status; + vm_t start = m->start * BASE_PAGE_SIZE; + vm_t end = m->end * BASE_PAGE_SIZE; + + reference_proc(s); + + size_t size = end - start; + vm_t v = alloc_shared_region(&d->uvmem.region, size, &size, m->flags, + s->rid); + stat_t res = clone_region(d->proc.vmem, s->proc.vmem, start, v, size, + flags); + if (res == OK) + return v; + + /* cleanup on error */ + unreference_proc(s); + free_region(&d->uvmem.region, v); + unmap_fixed_region(d->proc.vmem, v, size); + return NULL; } /** - * Check whether process associated with shared memory is still using it. + * Unmap and free private memory region. * - * @param pid Process to check. - * @param start Start of memory region - * @return \ref true if it is still in use, \ref false otherwise. + * @param t Current thread. + * @param m Memory region to free. */ -static bool __proc_has_region(id_t pid, vm_t start) +static void __free_mapped_private_region(struct tcb *t, struct mem_region *m) { - /** @todo this has a slight potential to have a race condition, where - * both threads want to free the same shared region at the same time. */ - struct tcb *p = get_tcb(pid); - if (!p) - return false; - - struct mem_region *m = find_used_region(&p->sp_r, start); - if (!m) - return false; - - return true; + pm_t start = __addr(m->start); + pm_t end = __addr(m->end); + size_t size = end - start; + unmap_region(t->proc.vmem, start, size); } /** @@ -94,29 +103,15 @@ static bool __proc_has_region(id_t pid, vm_t start) * * @param t Current thread. * @param m Memory region to free. - * @return \see unmap_vpage(). */ -static stat_t __free_mapped_shared_region(struct tcb *t, struct mem_region *m) +static void __free_mapped_shared_region(struct tcb *t, struct mem_region *m) { vm_t start = __addr(m->start); - bool in_use = __proc_has_region(m->pid, m->alt_va); - - size_t osize = order_size(BASE_PAGE); - size_t pages = m->start - m->end; - - stat_t status = OK; - for (size_t i = 0; i < pages; ++i) { - vm_t va = start + i * osize; - - pm_t pa = 0; - stat_vpage(t->proc.vmem, va, &pa, 0, 0); - status = unmap_vpage(t->proc.vmem, va); + vm_t end = __addr(m->end); + unreference_proc(get_tcb(m->pid)); - if (!in_use) - free_page(pa, BASE_PAGE); - } - - return status; + size_t bytes = end - start; + unmap_fixed_region(t->proc.vmem, start, bytes); } /** @@ -124,9 +119,8 @@ static stat_t __free_mapped_shared_region(struct tcb *t, struct mem_region *m) * * @param t Thread to work in. * @param m Memory region to free. - * @return \ref OK */ -static stat_t __free_mapped_region(struct tcb *t, struct mem_region *m) +static void __free_mapped_region(struct tcb *t, struct mem_region *m) { if (m->pid != 0) return __free_mapped_shared_region(t, m); @@ -134,51 +128,72 @@ static stat_t __free_mapped_region(struct tcb *t, struct mem_region *m) return __free_mapped_private_region(t, m); } -stat_t clear_uvmem(struct tcb *t) +void clear_uvmem(struct tcb *t) { - struct mem_region *m = find_first_region(&t->sp_r); - while (m) { - if (!is_region_kept(m)) - __free_mapped_region(t, m); + if (t->uvmem.owner != t->tid) + return; - m = m->next; - } + struct mem_region *m = find_closest_used_region(&t->uvmem.region, 0); + for (; m; m = m->next) { + if (is_region_kept(m)) { + continue; + } - return OK; + if (!is_set(m->flags, MR_USED)) { + continue; + } + + __free_mapped_region(t, m); + free_known_region(&t->uvmem.region, m); + } } -stat_t purge_uvmem(struct tcb *t) +void purge_uvmem(struct tcb *t) { - struct mem_region *m = find_first_region(&t->sp_r); - while (m) { + if (t->uvmem.owner != t->tid) + return; + + struct mem_region *m = find_closest_used_region(&t->uvmem.region, 0); + for (; m; m = m->next) { + if (!is_set(m->flags, MR_USED)) + continue; + + /* free memory associated with region */ __free_mapped_region(t, m); - m = m->next; } - return OK; + /* actually destroy region, will clear out all nodes automatically */ + destroy_region(&t->uvmem.region); } -stat_t destroy_uvmem(struct tcb *t) +void destroy_uvmem(struct tcb *t) { + if (t->uvmem.owner != t->tid) + return; + /* force clear all regions */ purge_uvmem(t); - /* destroy region tree itself */ - return destroy_region(&t->sp_r); + /* destroy associated virtual memory space */ + destroy_vmem(t->uvmem.vmem); } -stat_t clone_mem_regions(struct tcb *d, struct tcb *s) +stat_t copy_uvmem(struct tcb *d, struct tcb *s) { /** @todo implement some way to only iterate used regions, this loops * through all regions which is likely a slight bit slower. */ - struct mem_region *m = find_first_region(&s->sp_r); + stat_t ret = OK; + struct mem_region *m = find_first_region(&s->uvmem.region); while (m) { if (is_region_used(m)) - __clone_mapped_region(d, s, m); + ret = __copy_mapped_region(d, s, m); + + if (ret) + return ret; m = m->next; } - return OK; + return ret; } vm_t alloc_uvmem(struct tcb *t, size_t size, vmflags_t flags) @@ -186,238 +201,84 @@ vm_t alloc_uvmem(struct tcb *t, size_t size, vmflags_t flags) /* t exists and is the process tcb of the current process */ hard_assert(t && is_proc(t), ERR_INVAL); - stat_t status = OK; - const vm_t v = alloc_region(&t->sp_r, size, &size, flags); - const vm_t w = map_allocd_region(t->proc.vmem, v, size, flags, &status); - return w; -} - -vm_t alloc_uvpage(struct tcb *t, size_t size, vmflags_t flags, size_t *asize, - pm_t *paddr) -{ - hard_assert(t && is_proc(t), ERR_INVAL); - - enum mm_order order = nearest_order(size); - size_t actual_size = order_size(order); - stat_t status = OK; - - const vm_t v = alloc_region(&t->sp_r, size, &size, flags); - const vm_t w = __addr(__page(v)); - - pm_t addr = alloc_page(order); - /** @todo should free region */ - if (!addr) + const vm_t v = alloc_region(&t->uvmem.region, size, &size, flags); + if (map_region(t->proc.vmem, v, size, max_order(), flags)) { + unmap_region(t->proc.vmem, v, size); + free_region(&t->uvmem.region, v); return NULL; + } - status = map_vpage(t->proc.vmem, addr, w, flags, order); - if (status) - return NULL; - - if (asize) - *asize = actual_size; - - if (paddr) - *paddr = addr; - - return w; + return v; } vm_t alloc_fixed_uvmem(struct tcb *t, vm_t start, size_t size, vmflags_t flags) { hard_assert(t && is_proc(t), ERR_INVAL); - stat_t status = OK; - const vm_t v = alloc_fixed_region(&t->sp_r, start, size, &size, flags); - const vm_t w = map_allocd_region(t->proc.vmem, v, size, flags, &status); - return w; -} - -/** - * Helper for \ref map_fixed_mem(). - * Maps some contiguous bit of physical memory to an allocated virtual memory region. - * - * @param b Virtual memory to work in. - * @param v Start of virtual memory region. - * @param p Start of physical memory region. - * @param size Size of virtual memory region. - * @param flags Flags to use for mappings. - * @param status Is written to with the status of this function. - * @return The start of the virtual address mapping. - */ -static vm_t map_fixed_region(struct vmem *b, vm_t v, pm_t p, size_t size, - vmflags_t flags, stat_t *status) -{ - - vm_t w = v; - stat_t stat = OK; - size_t pages = size / BASE_PAGE_SIZE; - for (size_t i = 0; i < pages; ++i) { - stat = map_vpage(b, p, v, flags, BASE_PAGE); - v += BASE_PAGE_SIZE; - p += BASE_PAGE_SIZE; + const vm_t v = alloc_fixed_region(&t->uvmem.region, start, size, &size, + flags); + if (map_region(t->proc.vmem, v, size, max_order(), flags)) { + unmap_region(t->proc.vmem, v, size); + free_region(&t->uvmem.region, v); + return NULL; } - if (status) - *status = stat; - - return w; + return v; } -vm_t map_fixed_mem(struct tcb *t, pm_t start, size_t size, vmflags_t flags) +vm_t map_fixed_uvmem(struct tcb *t, pm_t start, size_t size, vmflags_t flags) { - stat_t status = OK; - const vm_t v = alloc_region(&t->sp_r, size, &size, flags); - const vm_t w = map_fixed_region(t->proc.vmem, v, start, size, flags, - &status); - return w + (start % BASE_PAGE_SIZE); + const vm_t v = alloc_region(&t->uvmem.region, size, &size, flags); + if (map_fixed_region(t->proc.vmem, v, start, size, flags)) { + unmap_region(t->proc.vmem, v, size); + free_region(&t->uvmem.region, v); + return NULL; + } + + return v + (start % BASE_PAGE_SIZE); } /* free_shared_uvmem shouldn't be needed, likely to work with free_uvmem */ -stat_t alloc_shared_uvmem(struct tcb *s, struct tcb *c, - size_t size, vmflags_t sflags, vmflags_t cflags, - vm_t *sstart, vm_t *cstart) +vm_t alloc_shared_uvmem(struct tcb *s, size_t size, vmflags_t flags) { - hard_assert(sstart, ERR_INVAL); - hard_assert(cstart, ERR_INVAL); hard_assert(s && is_proc(s), ERR_INVAL); - hard_assert(c && is_proc(c), ERR_INVAL); - - size_t ssize, csize; - vm_t sv = alloc_shared_region(&s->sp_r, size, &ssize, sflags, c->rid); - vm_t cv = alloc_shared_region(&c->sp_r, size, &csize, cflags, s->rid); - - /* not exactly optimal but good enough for now, I can start worrying - * about hyperoptimizations whenever. */ - set_alt_region_addr(&s->sp_r, sv, cv); - set_alt_region_addr(&c->sp_r, cv, sv); - - if (csize != ssize) { - /** @todo cleanup, better errors? */ - return ERR_INVAL; - } - - stat_t cstatus = OK, sstatus = OK; - size_t osize = order_size(BASE_PAGE); - size_t pages = ssize / osize; - for (size_t i = 0; i < pages; ++i) { - pm_t p = alloc_page(BASE_PAGE); - sstatus = map_vpage(s->proc.vmem, p, sv + i * osize, sflags, - BASE_PAGE); - cstatus = map_vpage(c->proc.vmem, p, cv + i * osize, cflags, - BASE_PAGE); + const vm_t v = alloc_region(&s->uvmem.region, size, &size, + MR_SHARED | flags); + /* use base pages to make clone more likely to succeed */ + if (map_region(s->proc.vmem, v, size, BASE_PAGE, flags)) { + unmap_region(s->proc.vmem, v, size); + free_region(&s->uvmem.region, v); + return NULL; } - *sstart = sv; - *cstart = cv; - - if (sstatus) - return sstatus; - - if (cstatus) - return cstatus; - - return OK; + return v; } -stat_t free_uvmem(struct tcb *r, vm_t va) +vm_t ref_shared_uvmem(struct tcb *d, struct tcb *s, vm_t v, vmflags_t flags) { - /** \todo assume tcb is root tcb? */ - struct mem_region *m = find_used_region(&r->sp_r, va); + struct mem_region *m = find_used_region(&s->uvmem.region, v); if (!m) return ERR_NF; - stat_t status = __free_mapped_region(r, m); - if (status) - return ERR_MISC; - - return free_known_region(&r->sp_r, m); -} - -stat_t alloc_uvmem_wrapper(struct vmem *b, pm_t *offset, vm_t vaddr, - vmflags_t flags, enum mm_order order, void *data) -{ - *offset = alloc_page(order); - if (!*offset) - return INFO_TRGN; /* try again */ - - stat_t *status = (stat_t *)data, ret; - ret = map_vpage(b, *offset, vaddr, flags, order); - if (status) - *status = ret; - - return ret; -} - -stat_t alloc_shared_wrapper(struct vmem *b, pm_t *offset, vm_t vaddr, - vmflags_t flags, enum mm_order order, void *data) -{ - if (order != MM_O0) - return INFO_TRGN; - - *offset = alloc_page(MM_O0); - - stat_t *status = (stat_t *)data, ret; - ret = map_vpage(b, *offset, vaddr, flags, order); - if (status) - *status = ret; + if (!is_set(m->flags, MR_SHARED)) + return ERR_INVAL; - return ret; + return __clone_shared_region(d, s, m, flags); } -stat_t copy_allocd_wrapper(struct vmem *b, pm_t *offset, vm_t vaddr, - vmflags_t flags, enum mm_order order, void *data) +stat_t free_uvmem(struct tcb *r, vm_t va) { - struct vmem *s = (struct vmem *)data; - - pm_t paddr = 0; - enum mm_order v_order = 0; - stat_vpage(s, vaddr, &paddr, &v_order, 0); - /** @todo what if we could combine multiple pages into one in the new - * process? */ - if (order > v_order) - return INFO_TRGN; - - pm_t new_page = alloc_page(order); - if (!new_page) - return INFO_TRGN; - - /* set write flags temporarily */ - vmflags_t wrflags = flags | VM_W; - map_vpage(b, new_page, vaddr, wrflags, order); - memcpy((void *)new_page, (void *)(paddr + *offset), order_size(order)); - - /* set actual flags */ - map_vpage(b, new_page, vaddr, flags, order); - - if (v_order > order) - *offset += order_size(order); - else - *offset = 0; + /** \todo assume tcb is root tcb? */ + struct mem_region *m = find_used_region(&r->uvmem.region, va); + if (!m) + return ERR_NF; + __free_mapped_region(r, m); + free_known_region(&r->uvmem.region, m); return OK; } -stat_t free_uvmem_wrapper(struct vmem *b, pm_t *offset, vm_t vaddr, - vmflags_t flags, enum mm_order order, void *data) +vmflags_t sanitize_uvflags(vmflags_t flags) { - UNUSED(flags); - UNUSED(offset); - - pm_t paddr = 0; - enum mm_order v_order = 0; - stat_vpage(b, vaddr, &paddr, &v_order, 0); - if (order != v_order) - return INFO_TRGN; - - /** @todo we might need to cause an ipi to flush the tlb for other - * cores */ - - stat_t *status = (stat_t *)data, ret; - ret = unmap_vpage(b, vaddr); - if (status) - *status = ret; - - free_page(order, paddr); - - return ret; + return (flags & (VM_R | VM_W | VM_X)) | VM_V | VM_U; } -- cgit v1.3