diff options
28 files changed, 643 insertions, 607 deletions
diff --git a/arch/riscv64/include/cpu.h b/arch/riscv64/include/cpu.h new file mode 100644 index 0000000..40a8c17 --- /dev/null +++ b/arch/riscv64/include/cpu.h @@ -0,0 +1 @@ +/* empty */ diff --git a/arch/riscv64/include/pages.h b/arch/riscv64/include/pages.h index 362499a..643d3b4 100644 --- a/arch/riscv64/include/pages.h +++ b/arch/riscv64/include/pages.h @@ -1,8 +1,6 @@ #ifndef APOS_RISCV_PAGES_H #define APOS_RISCV_PAGES_H -#include <apos/types.h> - #define MM_KPAGE MM_O0 #define MM_MPAGE MM_O1 #define MM_GPAGE MM_O2 @@ -13,6 +11,4 @@ #define MM_GPAGE_SIZE SZ_1G #define MM_TPAGE_SIZE SZ_512G -typedef uint64_t pm_t; - #endif /* APOS_RISCV_PAGES_H */ diff --git a/arch/riscv64/include/types.h b/arch/riscv64/include/types.h new file mode 100644 index 0000000..3e1c08b --- /dev/null +++ b/arch/riscv64/include/types.h @@ -0,0 +1,9 @@ +#ifndef APOS_RISCV_TYPES_H +#define APOS_RISCV_TYPES_H + +#include <apos/types.h> + +typedef size_t vm_t; +typedef size_t pm_t; + +#endif /* APOS_RISCV_TYPES_H */ diff --git a/arch/riscv64/include/vmem.h b/arch/riscv64/include/vmem.h index 228b24b..115f2b0 100644 --- a/arch/riscv64/include/vmem.h +++ b/arch/riscv64/include/vmem.h @@ -19,7 +19,6 @@ enum mm_mode { Sv32, }; -typedef size_t vm_t; struct __packed vm_branch { struct vm_branch *leaf[512]; }; diff --git a/arch/riscv64/init/init.c b/arch/riscv64/init/init.c index 7aecfb5..94f9777 100644 --- a/arch/riscv64/init/init.c +++ b/arch/riscv64/init/init.c @@ -61,12 +61,12 @@ void init(void *fdt) { extern char *__init_end; extern void jump_to_kernel(void *k, void *fdt); - void (*kernel_main)(void *fdt) = (void (*)(void *))(VM_KERN); + init_bootmem(); move_kernel(); __va_reg(sp); __va_reg(fp); __va_reg(gp); + jump_to_kernel((void *)VM_KERN, __va(fdt)); - //kernel_main(__va(fdt)); } diff --git a/arch/riscv64/kernel/cpu.c b/arch/riscv64/kernel/cpu.c index 6ae4ee7..3583a94 100644 --- a/arch/riscv64/kernel/cpu.c +++ b/arch/riscv64/kernel/cpu.c @@ -1,4 +1,4 @@ -#include <apos/cpu.h> +#include <arch/cpu.h> id_t cpu_id() { diff --git a/arch/riscv64/kernel/irq.c b/arch/riscv64/kernel/irq.c index f844dd1..a88288f 100644 --- a/arch/riscv64/kernel/irq.c +++ b/arch/riscv64/kernel/irq.c @@ -1,6 +1,6 @@ -#include <apos/irq.h> #include <apos/attrs.h> #include <apos/debug.h> +#include <arch/irq.h> #include <csr.h> void init_irq(void *fdt) diff --git a/arch/riscv64/kernel/vmem.c b/arch/riscv64/kernel/vmem.c index bc1a74e..146f30f 100644 --- a/arch/riscv64/kernel/vmem.c +++ b/arch/riscv64/kernel/vmem.c @@ -3,9 +3,7 @@ #include <apos/vmem.h> #include <apos/mem.h> #include <apos/debug.h> -#include <apos/cpu.h> -#include <pages.h> -#include <vmem.h> +#include <arch/cpu.h> #include <csr.h> #define pte_ppn(pte) (((pm_t)(pte)) >> 10) diff --git a/common/dev.c b/common/dmem.c index b89fe3a..0cc96e1 100644 --- a/common/dev.c +++ b/common/dmem.c @@ -1,5 +1,4 @@ -#include <apos/dev.h> -#include <apos/vmem.h> +#include <apos/dmem.h> static struct sp_reg_root pre_ram = {0}; static struct sp_reg_root post_ram = {0}; @@ -8,7 +7,7 @@ pm_t __pre_top = 0; pm_t __post_base = 0; pm_t __post_top = 0; -void init_devmem(pm_t ram_base, pm_t ram_top) +stat_t init_devmem(pm_t ram_base, pm_t ram_top) { pm_t mem_top = (pm_t)-1; @@ -23,16 +22,18 @@ void init_devmem(pm_t ram_base, pm_t ram_top) sp_mem_init(&pre_ram, __pre_base, pre_pages); sp_mem_init(&post_ram, __post_base, post_pages); + + return OK; } -static int dev_alloc_wrapper(struct vm_branch *b, pm_t *offset, vm_t vaddr, uint8_t flags, enum mm_order order) +stat_t dev_alloc_wrapper(struct vm_branch *b, pm_t *offset, vm_t vaddr, uint8_t flags, enum mm_order order) { map_vmem(b, *offset, vaddr, flags, order); *offset += __o_size(order); return 0; } -static int dev_free_wrapper(struct vm_branch *b, pm_t *offset, vm_t vaddr, uint8_t flags, enum mm_order order) +stat_t dev_free_wrapper(struct vm_branch *b, pm_t *offset, vm_t vaddr, uint8_t flags, enum mm_order order) { UNUSED(offset); UNUSED(flags); pm_t paddr = 0; @@ -60,13 +61,13 @@ vm_t alloc_devmem(struct tcb *t, pm_t dev_start, size_t bytes, uint8_t flags) return map_fill_region(t->b_r, &dev_alloc_wrapper, dev_start, region, bytes, flags); } -void free_devmem(struct tcb *t, vm_t dev_start) +stat_t free_devmem(struct tcb *t, vm_t dev_start) { pm_t dev_paddr = 0; stat_vmem(t->b_r, dev_start, &dev_paddr, 0, 0); if(dev_paddr >= __pre_top && dev_paddr <= __post_base) - return; + return ERR_ADDR; struct sp_mem *m = 0; if(dev_paddr < __pre_top) @@ -76,7 +77,7 @@ void free_devmem(struct tcb *t, vm_t dev_start) m = sp_used_find(&post_ram, dev_paddr); if(!m) - return; + return ERR_NF; size_t region_size = __addr(m->end - m->start); map_fill_region(t->b_r, &dev_free_wrapper, dev_paddr, dev_start, region_size, 0); @@ -86,4 +87,6 @@ void free_devmem(struct tcb *t, vm_t dev_start) if(dev_paddr > __post_base) free_region(&post_ram, dev_paddr); + + return OK; } diff --git a/common/main.c b/common/main.c index 52987d1..3aabc3c 100644 --- a/common/main.c +++ b/common/main.c @@ -3,8 +3,8 @@ #include <apos/proc.h> #include <apos/debug.h> #include <apos/vmem.h> -#include <apos/arch.h> -#include <apos/irq.h> +#include <arch/arch.h> +#include <arch/irq.h> #include <libfdt.h> #ifdef DEBUG diff --git a/common/mem_regions.c b/common/mem_regions.c new file mode 100644 index 0000000..ebcff50 --- /dev/null +++ b/common/mem_regions.c @@ -0,0 +1,458 @@ +#include <apos/mem_regions.h> +#include <apos/mem_nodes.h> +#include <apos/pmem.h> +#include <apos/mem.h> + +#define mark_region_used(r) ((r) = 1) +#define mark_region_unused(r) ((r) = 0) +#define is_region_used(r) (r) + +static size_t __uvmem_size = 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 + * + * 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_reg_root *r, struct sp_mem *m) +{ + struct sp_node *n = sp_root(r->free_regions), *p = NULL; + size_t start = m->start; + size_t size = m->end - m->start; + enum sp_dir d = LEFT; + + m->sp_n = (struct sp_node){0}; + + while(n){ + struct sp_mem *t = mem_container(n); + size_t nsize = t->end - t->start; + p = n; + + if(size < nsize){ + n = sp_left(n); + d = LEFT; + } + + else if(size > nsize) { + n = sp_right(n); + d = RIGHT; + } + + else if (start < t->start){ + n = sp_left(n); + d = LEFT; + } + + else { + n = sp_right(n); + d = RIGHT; + } + } + + if(sp_root(r->free_regions)) + sp_insert(&sp_root(r->free_regions), p, &m->sp_n, d); + else + sp_root(r->free_regions) = &m->sp_n; + + return m; +} + +static struct sp_mem *sp_used_insert_region(struct sp_reg_root *r, struct sp_mem *m) +{ + struct sp_node *n = sp_root(r->used_regions), *p = NULL; + vm_t start = m->start; + enum sp_dir d = LEFT; + + m->sp_n = (struct sp_node){0}; + + while(n){ + struct sp_mem *t = mem_container(n); + + p = n; + + if(start < t->start){ + n = sp_left(n); + d = LEFT; + } + + else { + /* we should never encounter a situation where start = + * t->start */ + n = sp_right(n); + d = RIGHT; + } + } + + if(sp_root(r->used_regions)) + sp_insert(&sp_root(r->used_regions), p, &m->sp_n, d); + else + sp_root(r->used_regions) = &m->sp_n; + + return m; +} + +stat_t sp_mem_init(struct sp_reg_root *r, vm_t start, size_t arena_size) +{ + /* convert bytes to pages */ + start = __page(start); + arena_size = __page(arena_size); + struct sp_mem *m = get_mem_node(); + m->start = start; + m->end = start + arena_size; + sp_free_insert_region(r, m); + + return OK; +} + +static void __sp_mem_destroy(struct sp_node *n) +{ + if(!n) + return; + + __sp_mem_destroy(sp_left(n)); + __sp_mem_destroy(sp_right(n)); + + struct sp_mem *m = mem_container(n); + free_mem_node(m); +} + +void sp_mem_destroy(struct sp_reg_root *r) +{ + __sp_mem_destroy(sp_root(r->free_regions)); + __sp_mem_destroy(sp_root(r->used_regions)); +} + +/* 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 sp_mem *sp_used_find(struct sp_reg_root *r, vm_t start) +{ + struct sp_node *n = sp_root(r->used_regions); + while(n){ + struct sp_mem *t = mem_container(n); + if(start == t->start) + return t; + + if(start < t->start) + n = sp_left(n); + else + n = sp_right(n); + } + + return 0; +} + +static struct sp_mem *sp_mem_create_region(vm_t start, vm_t end, + struct sp_mem *prev, struct sp_mem *next) +{ + struct sp_mem *m = get_mem_node(); + m->start = start; + m->end = end; + m->prev = prev; + m->next = next; + return m; +} + +/* TODO: should probably check if this actually works :D seems to do, but that's + * just from really quick checking */ +static size_t po_align(size_t s) +{ + for(size_t o = __mm_max_order; o > 0; --o){ + if(s >= __o_size(o)) + return __o_size(o); + } + + return 0; +} + +struct sp_mem *sp_find_used_closest(struct sp_reg_root *r, vm_t start) +{ + struct sp_mem *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 sp_mem *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 sp_mem *sp_find_free(struct sp_reg_root *r, size_t size, size_t *align) +{ + *align = 0; + size_t offset = __page(po_align(__addr(size))); + struct sp_mem *quick_best = 0; + struct sp_node *n = sp_root(r->free_regions); + while(n){ + struct sp_mem *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; +} + +static size_t sp_use_region(struct sp_reg_root *r, struct sp_mem *m, + size_t pages, size_t align) +{ + 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 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(r, n); + } + + 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; + + sp_free_insert_region(r, n); + } + + m->end = end; + m->start = start; + mark_region_used(m->flags); + sp_used_insert_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_region(struct sp_reg_root *r, + size_t size, size_t *actual_size) +{ + *actual_size = align_up(size, BASE_PAGE_SIZE); + size_t pages = __page(*actual_size); + + /* find best fitting, alignment etc. */ + size_t align = 0; + struct sp_mem *m = sp_find_free(r, pages, &align); + if(!m) + return 0; + + return sp_use_region(r, m, pages, align); +} + + +vm_t alloc_fixed_region(struct sp_reg_root *r, + vm_t start, size_t size, size_t *actual_size) +{ + size_t asize = align_up(size, BASE_PAGE_SIZE); + if(actual_size) + *actual_size = asize; + + size_t pages = __page(asize); + start = __page(start); + + struct sp_mem *m = sp_find_used_closest(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->flags)) + return 0; + + /* region is too small */ + if(start + pages > m->end) + return 0; + + /* actually start marking region used */ + return sp_use_region(r, m, pages, start - m->start); +} + +static void __sp_try_coalesce_prev(struct sp_reg_root *r, struct sp_mem *m) +{ + while(m){ + if(!m || is_region_used(m->flags)) + return; + + struct sp_mem *p = m->prev; + if(!p || is_region_used(p->flags)) + 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; + } +} + +static void __sp_try_coalesce_next(struct sp_reg_root *r, struct sp_mem *m) +{ + while(m){ + if(!m || is_region_used(m->flags)) + return; + + struct sp_mem *n = m->next; + if(!n || is_region_used(n->flags)) + 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; + } +} + +static void sp_mem_try_coalesce(struct sp_reg_root *r, struct sp_mem *m) +{ + __sp_try_coalesce_prev(r, m); + __sp_try_coalesce_next(r, m); +} + +stat_t free_region(struct sp_reg_root *r, vm_t start) +{ + /* addr not aligned to page boundary, corrupted or incorrect pointer */ + if(!aligned(start, BASE_PAGE_SIZE)) + return ERR_ALIGN; + + struct sp_mem *m = sp_used_find(r, __page(start)); + if(!m) + return ERR_NF; + + sp_remove(&sp_root(r->used_regions), &m->sp_n); + mark_region_unused(m->flags); + + sp_mem_try_coalesce(r, m); + sp_free_insert_region(r, m); + return OK; +} + +void set_uvmem_size(size_t s) +{ + __uvmem_size = s; +} + +size_t uvmem_size() +{ + return __uvmem_size; +} + +/* 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 vm_branch *b, + stat_t (*vmem_handler)(struct vm_branch *, pm_t *, vm_t, uint8_t, enum mm_order), + pm_t offset, vm_t start, size_t bytes, uint8_t flags) +{ + 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 = __o_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(!aligned(runner, o_pages)) + continue; + + while(pages >= o_pages){ + int res = vmem_handler(b, &offset, __addr(runner), flags, top); + if(res > 0) + break; + + if(res < 0) + return 0; + + pages -= o_pages; + runner += o_pages; + } + } + + return start; +} diff --git a/common/pmem.c b/common/pmem.c index ae01175..1246210 100644 --- a/common/pmem.c +++ b/common/pmem.c @@ -1,6 +1,6 @@ #include <apos/mem_nodes.h> #include <apos/pmem.h> -#include <apos/dev.h> +#include <apos/dmem.h> #include <apos/debug.h> #include <apos/initrd.h> #include <apos/string.h> /* memset */ diff --git a/common/proc.c b/common/proc.c index ccd60bd..c272727 100644 --- a/common/proc.c +++ b/common/proc.c @@ -3,6 +3,7 @@ #include <apos/string.h> #include <apos/initrd.h> #include <apos/proc.h> +#include <arch/arch.h> /* TODO: add error checking */ static vm_t setup_call_stack(struct tcb *t, size_t bytes) @@ -34,7 +35,7 @@ void init_proc(void *fdt, struct vm_branch *b) threads_insert(t); - sp_mem_init(&t->sp_r, UVMEM_START, UVMEM_END); + init_uvmem(t, UVMEM_START, UVMEM_END); /* the binary gets to choose first what memory regions it requires */ t->entry = load_elf(t, get_init_base(fdt)); diff --git a/common/tcb.c b/common/tcb.c index cbbfa47..7f3cf81 100644 --- a/common/tcb.c +++ b/common/tcb.c @@ -1,7 +1,7 @@ #include <apos/tcb.h> -#include <apos/cpu.h> #include <apos/utils.h> #include <apos/sp_tree.h> +#include <arch/cpu.h> static struct sp_root t_root = (struct sp_root){0}; static struct tcb *__tcb_cache[MAX_CPUS] = {0}; diff --git a/common/uapi/mem.c b/common/uapi/mem.c index 8c63a87..0a88eda 100644 --- a/common/uapi/mem.c +++ b/common/uapi/mem.c @@ -1,7 +1,7 @@ -#include <apos/dev.h> #include <apos/uapi.h> #include <apos/utils.h> #include <apos/vmem.h> +#include <apos/dmem.h> vm_t sys_req_mem(vm_t size, vm_t flags, vm_t u0, vm_t u1) { diff --git a/common/vmem.c b/common/vmem.c index 7fe0ab5..bd0cc29 100644 --- a/common/vmem.c +++ b/common/vmem.c @@ -1,461 +1,38 @@ +#include <apos/mem_regions.h> #include <apos/vmem.h> -#include <apos/mem_nodes.h> -#include <vmem.h> -#define mark_region_used(r) ((r) = 1) -#define mark_region_unused(r) ((r) = 0) -#define is_region_used(r) (r) -static size_t __uvmem_size = 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 - * - * 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_reg_root *r, struct sp_mem *m) -{ - struct sp_node *n = sp_root(r->free_regions), *p = NULL; - size_t start = m->start; - size_t size = m->end - m->start; - enum sp_dir d = LEFT; - - m->sp_n = (struct sp_node){0}; - - while(n){ - struct sp_mem *t = mem_container(n); - size_t nsize = t->end - t->start; - p = n; - - if(size < nsize){ - n = sp_left(n); - d = LEFT; - } - - else if(size > nsize) { - n = sp_right(n); - d = RIGHT; - } - - else if (start < t->start){ - n = sp_left(n); - d = LEFT; - } - - else { - n = sp_right(n); - d = RIGHT; - } - } - - if(sp_root(r->free_regions)) - sp_insert(&sp_root(r->free_regions), p, &m->sp_n, d); - else - sp_root(r->free_regions) = &m->sp_n; - - return m; -} - -static struct sp_mem *sp_used_insert_region(struct sp_reg_root *r, struct sp_mem *m) +stat_t init_uvmem(struct tcb *t, vm_t base, vm_t top) { - struct sp_node *n = sp_root(r->used_regions), *p = NULL; - vm_t start = m->start; - enum sp_dir d = LEFT; - - m->sp_n = (struct sp_node){0}; - - while(n){ - struct sp_mem *t = mem_container(n); - - p = n; - - if(start < t->start){ - n = sp_left(n); - d = LEFT; - } - - else { - /* we should never encounter a situation where start = - * t->start */ - n = sp_right(n); - d = RIGHT; - } - } - - if(sp_root(r->used_regions)) - sp_insert(&sp_root(r->used_regions), p, &m->sp_n, d); - else - sp_root(r->used_regions) = &m->sp_n; - - return m; + return sp_mem_init(&t->sp_r, base, top); } -int sp_mem_init(struct sp_reg_root *r, vm_t start, size_t arena_size) -{ - /* convert bytes to pages */ - start = __page(start); - arena_size = __page(arena_size); - struct sp_mem *m = get_mem_node(); - m->start = start; - m->end = start + arena_size; - sp_free_insert_region(r, m); - - return 0; -} - -static void __sp_mem_destroy(struct sp_node *n) -{ - if(!n) - return; - - __sp_mem_destroy(sp_left(n)); - __sp_mem_destroy(sp_right(n)); - - struct sp_mem *m = mem_container(n); - free_mem_node(m); -} - -void sp_mem_destroy(struct sp_reg_root *r) -{ - __sp_mem_destroy(sp_root(r->free_regions)); - __sp_mem_destroy(sp_root(r->used_regions)); -} - -/* 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 sp_mem *sp_used_find(struct sp_reg_root *r, vm_t start) -{ - struct sp_node *n = sp_root(r->used_regions); - while(n){ - struct sp_mem *t = mem_container(n); - if(start == t->start) - return t; - - if(start < t->start) - n = sp_left(n); - else - n = sp_right(n); - } - - return 0; -} - -static struct sp_mem *sp_mem_create_region(vm_t start, vm_t end, - struct sp_mem *prev, struct sp_mem *next) -{ - struct sp_mem *m = get_mem_node(); - m->start = start; - m->end = end; - m->prev = prev; - m->next = next; - return m; -} - -/* TODO: should probably check if this actually works :D seems to do, but that's - * just from really quick checking */ -static size_t po_align(size_t s) -{ - for(size_t o = __mm_max_order; o > 0; --o){ - if(s >= __o_size(o)) - return __o_size(o); - } - - return 0; -} - -static struct sp_mem *sp_find_used_closest(struct sp_reg_root *r, vm_t start) -{ - struct sp_mem *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 sp_mem *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. */ -static struct sp_mem *sp_find_free_best(struct sp_reg_root *r, size_t size, size_t *align) -{ - *align = 0; - size_t offset = __page(po_align(__addr(size))); - struct sp_mem *quick_best = 0; - struct sp_node *n = sp_root(r->free_regions); - while(n){ - struct sp_mem *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; -} - -static size_t sp_use_region(struct sp_reg_root *r, struct sp_mem *m, - size_t pages, size_t align) -{ - 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 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(r, n); - } - - 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; - - sp_free_insert_region(r, n); - } - - m->end = end; - m->start = start; - mark_region_used(m->flags); - sp_used_insert_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_region(struct sp_reg_root *r, - size_t size, size_t *actual_size) -{ - *actual_size = align_up(size, BASE_PAGE_SIZE); - size_t pages = __page(*actual_size); - - /* find best fitting, alignment etc. */ - size_t align = 0; - struct sp_mem *m = sp_find_free_best(r, pages, &align); - if(!m) - return 0; - - return sp_use_region(r, m, pages, align); -} - - -vm_t alloc_fixed_region(struct sp_reg_root *r, - vm_t start, size_t size, size_t *actual_size) -{ - size_t asize = align_up(size, BASE_PAGE_SIZE); - if(actual_size) - *actual_size = asize; - - size_t pages = __page(asize); - start = __page(start); - - struct sp_mem *m = sp_find_used_closest(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->flags)) - return 0; - - /* region is too small */ - if(start + pages > m->end) - return 0; - - /* actually start marking region used */ - return sp_use_region(r, m, pages, start - m->start); -} - -static void __sp_try_coalesce_prev(struct sp_reg_root *r, struct sp_mem *m) -{ - while(m){ - if(!m || is_region_used(m->flags)) - return; - - struct sp_mem *p = m->prev; - if(!p || is_region_used(p->flags)) - 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; - } -} - -static void __sp_try_coalesce_next(struct sp_reg_root *r, struct sp_mem *m) +vm_t alloc_uvmem(struct tcb *t, size_t size, uint8_t flags) { - while(m){ - if(!m || is_region_used(m->flags)) - return; - - struct sp_mem *n = m->next; - if(!n || is_region_used(n->flags)) - 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; - } + vm_t v = alloc_region(&t->sp_r, size, &size); + return map_allocd_region(t->b_r, v, size, flags); } -static void sp_mem_try_coalesce(struct sp_reg_root *r, struct sp_mem *m) +vm_t alloc_fixed_uvmem(struct tcb *t, vm_t start, size_t size, uint8_t flags) { - __sp_try_coalesce_prev(r, m); - __sp_try_coalesce_next(r, m); + vm_t v = alloc_fixed_region(&t->sp_r, start, size, &size); + return map_allocd_region(t->b_r, v, size, flags); } -void free_region(struct sp_reg_root *r, vm_t start) +stat_t free_uvmem(struct tcb *t, vm_t va) { - /* addr not aligned to page boundary, corrupted or incorrect pointer */ - if(!aligned(start, BASE_PAGE_SIZE)) - return; - - struct sp_mem *m = sp_used_find(r, __page(start)); + struct sp_mem *m = sp_used_find(&t->sp_r, va); if(!m) - return; - - sp_remove(&sp_root(r->used_regions), &m->sp_n); - mark_region_unused(m->flags); - - sp_mem_try_coalesce(r, m); - sp_free_insert_region(r, m); -} - -void set_uvmem_size(size_t s) -{ - __uvmem_size = s; -} - -size_t uvmem_size() -{ - return __uvmem_size; -} - -/* 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 vm_branch *b, - int (*vmem_handler)(struct vm_branch *, pm_t *, vm_t, uint8_t, enum mm_order), - pm_t offset, vm_t start, size_t bytes, uint8_t flags) -{ - 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 = __o_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(!aligned(runner, o_pages)) - continue; - - while(pages >= o_pages){ - int res = vmem_handler(b, &offset, __addr(runner), flags, top); - if(res > 0) - break; - - if(res < 0) - return 0; + return -1; - pages -= o_pages; - runner += o_pages; - } - } + pm_t pa = __addr(m->end - m->start); - return start; + free_region(&t->sp_r, va); + unmap_freed_region(t->b_r, va, pa); + return 0; } -int alloc_mem_wrapper(struct vm_branch *b, pm_t *offset, vm_t vaddr, uint8_t flags, enum mm_order order) +stat_t alloc_uvmem_wrapper(struct vm_branch *b, pm_t *offset, vm_t vaddr, uint8_t flags, enum mm_order order) { *offset = alloc_page(order, *offset); if(!*offset) @@ -465,7 +42,7 @@ int alloc_mem_wrapper(struct vm_branch *b, pm_t *offset, vm_t vaddr, uint8_t fla return 0; } -int free_mem_wrapper(struct vm_branch *b, pm_t *offset, vm_t vaddr, uint8_t flags, enum mm_order order) +stat_t free_uvmem_wrapper(struct vm_branch *b, pm_t *offset, vm_t vaddr, uint8_t flags, enum mm_order order) { UNUSED(flags); UNUSED(offset); @@ -479,27 +56,3 @@ int free_mem_wrapper(struct vm_branch *b, pm_t *offset, vm_t vaddr, uint8_t flag free_page(order, paddr); return 0; } - -vm_t alloc_uvmem(struct tcb *t, size_t size, uint8_t flags) -{ - vm_t v = alloc_region(&t->sp_r, size, &size); - return map_allocd_region(t->b_r, v, size, flags); -} - -vm_t alloc_fixed_uvmem(struct tcb *t, vm_t start, size_t size, uint8_t flags) -{ - vm_t v = alloc_fixed_region(&t->sp_r, start, size, &size); - return map_allocd_region(t->b_r, v, size, flags); -} - -void free_uvmem(struct tcb *t, vm_t va) -{ - struct sp_mem *m = sp_used_find(&t->sp_r, va); - if(!m) - return; - - pm_t pa = __addr(m->end - m->start); - - free_region(&t->sp_r, va); - unmap_freed_region(t->b_r, va, pa); -} diff --git a/include/apos/dev.h b/include/apos/dev.h deleted file mode 100644 index 1e710a1..0000000 --- a/include/apos/dev.h +++ /dev/null @@ -1,16 +0,0 @@ -#ifndef APOS_DEV_H -#define APOS_DEV_H - -#include <apos/types.h> -#include <apos/vmem.h> - -extern pm_t __pre_base; -extern pm_t __pre_top; -extern pm_t __post_base; -extern pm_t __post_top; - -void init_devmem(pm_t ram_base, pm_t ram_top); -vm_t alloc_devmem(struct tcb *t, pm_t dev_start, size_t bytes, uint8_t flags); -void free_devmem(struct tcb *t, vm_t dev_start); - -#endif /* APOS_DEV_H */ diff --git a/include/apos/dmem.h b/include/apos/dmem.h new file mode 100644 index 0000000..936a902 --- /dev/null +++ b/include/apos/dmem.h @@ -0,0 +1,19 @@ +#ifndef APOS_DEV_H +#define APOS_DEV_H + +#include <apos/types.h> +#include <apos/vmem.h> + +extern pm_t __pre_base; +extern pm_t __pre_top; +extern pm_t __post_base; +extern pm_t __post_top; + +stat_t init_devmem(pm_t ram_base, pm_t ram_top); +vm_t alloc_devmem(struct tcb *t, pm_t dev_start, size_t bytes, uint8_t flags); +stat_t free_devmem(struct tcb *t, vm_t dev_start); + +stat_t dev_free_wrapper(struct vm_branch *b, pm_t *offset, vm_t vaddr, uint8_t flags, enum mm_order t); +stat_t dev_alloc_wrapper(struct vm_branch *b, pm_t *offset, vm_t vaddr, uint8_t flags, enum mm_order t); + +#endif /* APOS_DEV_H */ diff --git a/include/apos/mem.h b/include/apos/mem.h index e935fe4..01edcf6 100644 --- a/include/apos/mem.h +++ b/include/apos/mem.h @@ -2,6 +2,7 @@ #define APOS_MEM_H #include <apos/utils.h> +#include <apos/types.h> #include <pages.h> #define MM_OINFO_WIDTH (sizeof(mm_info_t) * 8) @@ -29,6 +30,14 @@ #define __o_container(idx) ((idx) / MM_OINFO_WIDTH) #define __o_bit(idx) ((idx) & (MM_OINFO_WIDTH - 1)) +#define __va(x) (((char *)(x)) + VM_DMAP - RAM_BASE) +#define __pa(x) (((char *)(x)) + RAM_BASE - VM_DMAP) +#define __page(x) ((x) / BASE_PAGE_SIZE) +#define __addr(x) ((x) * BASE_PAGE_SIZE) +#define __pages(x) (aligned((x), BASE_PAGE_SIZE) ? __page((x)) : __page((x) + BASE_PAGE_SIZE)) +#define __bytes(x) (__addr(x)) + + extern size_t __mm_shifts[10]; extern size_t __mm_widths[10]; extern size_t __mm_sizes[10]; @@ -36,6 +45,21 @@ extern size_t __mm_sizes[10]; extern size_t __mm_page_shift; extern size_t __mm_max_order; +#define ORDERS_NUM 10 +enum mm_order { + MM_O0, + MM_O1, + MM_O2, + MM_O3, + MM_O4, + MM_O5, + MM_O6, + MM_O7, + MM_O8, + MM_O9, +}; + +typedef ssize_t pnum_t; void init_mem(size_t max_order, size_t shifts[10], size_t page_shift); enum mm_mode get_mmode(void *fdt); diff --git a/include/apos/mem_regions.h b/include/apos/mem_regions.h new file mode 100644 index 0000000..eb81e63 --- /dev/null +++ b/include/apos/mem_regions.h @@ -0,0 +1,36 @@ +#ifndef APOS_MEM_REGIONS_H +#define APOS_MEM_REGIONS_H + +#include <apos/types.h> +#include <apos/sp_tree.h> + +#define mem_container(ptr)\ + container_of(ptr, struct sp_mem, sp_n) + +struct sp_reg_root { + struct sp_root free_regions; + struct sp_root used_regions; +}; + +struct sp_mem { + struct sp_node sp_n; + + struct sp_mem *next; + struct sp_mem *prev; + + char flags; + + vm_t end; + vm_t start; +}; + +stat_t sp_mem_init(struct sp_reg_root *r, vm_t start, size_t arena_size); +vm_t alloc_region(struct sp_reg_root *r, size_t size, size_t *actual_size); +vm_t alloc_fixed_region(struct sp_reg_root *r, vm_t start, size_t size, size_t *actual_size); +stat_t free_region(struct sp_reg_root *r, vm_t start); + +struct sp_mem *sp_used_find(struct sp_reg_root *r, vm_t start); +struct sp_mem *sp_find_used_closest(struct sp_reg_root *r, vm_t start); +struct sp_mem *sp_find_free(struct sp_reg_root *r, size_t size, size_t *align); + +#endif /* APOS_MEM_REGIONS_H */ diff --git a/include/apos/pmem.h b/include/apos/pmem.h index 2850f22..0f58e1c 100644 --- a/include/apos/pmem.h +++ b/include/apos/pmem.h @@ -4,23 +4,6 @@ #include <apos/mem.h> #include <apos/types.h> -#define ORDERS_NUM 10 -enum mm_order { - MM_O0, - MM_O1, - MM_O2, - MM_O3, - MM_O4, - MM_O5, - MM_O6, - MM_O7, - MM_O8, - MM_O9, -}; - -typedef size_t pm_t; -typedef ssize_t pnum_t; - /* arch */ int arch_pmem_conf(void *fdt, size_t *max_order, size_t *base_bits, size_t bits[ORDERS_NUM]); diff --git a/include/apos/tcb.h b/include/apos/tcb.h index 0a07d7b..4872bd0 100644 --- a/include/apos/tcb.h +++ b/include/apos/tcb.h @@ -1,21 +1,9 @@ #ifndef APOS_TCB_H #define APOS_TCB_H -struct tcb; -struct sp_reg_root; - -#include <tcb.h> -#include <vmem.h> -#include <apos/vmem.h> +#include <apos/mem_regions.h> #include <apos/types.h> -#include <apos/sp_tree.h> - -typedef size_t id_t; - -struct sp_reg_root { - struct sp_root free_regions; - struct sp_root used_regions; -}; +#include <tcb.h> /* arch-specific data */ struct tcb { struct sp_node sp_n; diff --git a/include/apos/types.h b/include/apos/types.h index 7cc4e28..7d690de 100644 --- a/include/apos/types.h +++ b/include/apos/types.h @@ -175,4 +175,21 @@ typedef intmax_t ssize_t; #define NULL 0 +/* some common types used throughout the kernel */ +typedef int_fast8_t stat_t; +typedef uint_fast32_t id_t; +typedef uint_fast8_t mflags_t; + +/* error types (should this go somewhere else? */ +/* negative error codes are reserved for general usage, positive error codes are + * allowed to be function-specific. */ +enum { + ERR_ADDR = -3, /* illegal address */ + ERR_ALIGN = -2, /* wrong alignment */ + ERR_NF = -1, /* not found */ + OK = 0, /* OK */ +}; + +#include <types.h> /* arch-specific type definitions (pm_t/vm_t etc) */ + #endif /* APOS_TYPES_H */ diff --git a/include/apos/vmem.h b/include/apos/vmem.h index 8057631..bd6b89e 100644 --- a/include/apos/vmem.h +++ b/include/apos/vmem.h @@ -1,89 +1,31 @@ #ifndef APOS_VMEM_H #define APOS_VMEM_H -struct sp_mem; - -/* arch-specific data */ -#include <vmem.h> - -/* common */ -#include <apos/pmem.h> #include <apos/tcb.h> +#include <apos/pmem.h> #include <apos/sp_tree.h> - -struct sp_mem { - struct sp_node sp_n; - - struct sp_mem *next; - struct sp_mem *prev; - - char flags; - - vm_t end; - vm_t start; -}; - -#define mem_container(ptr)\ - container_of(ptr, struct sp_mem, sp_n) - -#define __va(x) (((char *)(x)) + VM_DMAP - RAM_BASE) -#define __pa(x) (((char *)(x)) + RAM_BASE - VM_DMAP) -#define __page(x) ((x) / BASE_PAGE_SIZE) -#define __addr(x) ((x) * BASE_PAGE_SIZE) -#define __pages(x) (aligned((x), BASE_PAGE_SIZE) ? __page((x)) : __page((x) + BASE_PAGE_SIZE)) -#define __bytes(x) (__addr(x)) - -/* general overview of the different functions: - * internally they all work with pages, but they are called and return usable - * addresses, though within page bounds of course. - */ - -/* defined by arch */ -void map_vmem(struct vm_branch *branch, - pm_t paddr, vm_t vaddr, uint8_t flags, enum mm_order order); - -void unmap_vmem(struct vm_branch *branch, vm_t vaddr); - -int mod_vmem(struct vm_branch *branch, vm_t vaddr, pm_t paddr, uint8_t flags); -int stat_vmem(struct vm_branch *branch, vm_t vaddr, pm_t *paddr, - enum mm_order *order, uint8_t *flags); - -int setup_kernel_io(struct vm_branch *b, vm_t paddr); -void populate_root_branch(struct vm_branch *b); -struct vm_branch *init_vmem(void *fdt); - -void flush_tlb(); -void flush_tlb_all(); - -/* defined in common */ - -int sp_mem_init(struct sp_reg_root *r, vm_t start, size_t nums); - -vm_t alloc_region(struct sp_reg_root *r, size_t size, size_t *actual_size); -vm_t alloc_fixed_region(struct sp_reg_root *r, vm_t start, size_t size, size_t *actual_size); -void free_region(struct sp_reg_root *r, vm_t start); +#include <arch/vmem.h> vm_t alloc_uvmem(struct tcb *r, size_t size, uint8_t flags); vm_t alloc_fixed_uvmem(struct tcb *r, vm_t start, size_t size, uint8_t flags); -void free_uvmem(struct tcb *r, vm_t a); + +stat_t free_uvmem(struct tcb *r, vm_t a); +stat_t init_uvmem(struct tcb *r, vm_t base, vm_t top); vm_t map_fill_region(struct vm_branch *b, int (*vmem_handler)(struct vm_branch *, pm_t *, vm_t, uint8_t, enum mm_order), pm_t offset, vm_t start, size_t bytes, uint8_t flags); +stat_t alloc_uvmem_wrapper(struct vm_branch *b, pm_t *offset, vm_t vaddr, uint8_t flags, enum mm_order order); +stat_t free_uvmem_wrapper(struct vm_branch *b, pm_t *offset, vm_t vaddr, uint8_t flags, enum mm_order order); + #define map_allocd_region(b, start, bytes, flags)\ - map_fill_region(b, &alloc_mem_wrapper, 0, start, bytes, flags) + map_fill_region(b, &alloc_uvmem_wrapper, 0, start, bytes, flags) #define unmap_freed_region(b, start, bytes)\ - map_fill_region(b, &free_mem_wrapper, 0, start, bytes, 0) - -int alloc_mem_wrapper(struct vm_branch *b, pm_t *offset, vm_t vaddr, uint8_t flags, enum mm_order order); -int free_mem_wrapper(struct vm_branch *b, pm_t *offset, vm_t vaddr, uint8_t flags, enum mm_order order); + map_fill_region(b, &free_uvmem_wrapper, 0, start, bytes, 0) size_t uvmem_size(); void set_uvmem_size(size_t s); -/* not entirely sure if this is clean enough, but it'll do for now. */ -struct sp_mem *sp_used_find(struct sp_reg_root *r, vm_t start); - #endif /* APOS_VMEM_H */ diff --git a/include/apos/arch.h b/include/arch/arch.h index b846876..1933555 100644 --- a/include/apos/arch.h +++ b/include/arch/arch.h @@ -1,6 +1,8 @@ #ifndef APOS_ARCH_H #define APOS_ARCH_H +/* functions that an arch has to provide */ + void arch_setup(void *fdt); #endif /* APOS_ARCH_H */ diff --git a/include/apos/cpu.h b/include/arch/cpu.h index 81fb07e..c53a4d6 100644 --- a/include/apos/cpu.h +++ b/include/arch/cpu.h @@ -1,7 +1,8 @@ #ifndef APOS_CPU_H #define APOS_CPU_H -#include <apos/tcb.h> +#include <apos/types.h> +#include <cpu.h> id_t cpu_id(); /* TODO: add more cpu handling functions */ diff --git a/include/apos/irq.h b/include/arch/irq.h index 3ce6556..3ce6556 100644 --- a/include/apos/irq.h +++ b/include/arch/irq.h diff --git a/include/arch/vmem.h b/include/arch/vmem.h new file mode 100644 index 0000000..8aec154 --- /dev/null +++ b/include/arch/vmem.h @@ -0,0 +1,22 @@ +#ifndef APOS_ARCH_PAGES_H +#define APOS_ARCH_PAGES_H + +#include <vmem.h> + +void map_vmem(struct vm_branch *branch, + pm_t paddr, vm_t vaddr, uint8_t flags, enum mm_order order); + +void unmap_vmem(struct vm_branch *branch, vm_t vaddr); + +int mod_vmem(struct vm_branch *branch, vm_t vaddr, pm_t paddr, uint8_t flags); +int stat_vmem(struct vm_branch *branch, vm_t vaddr, pm_t *paddr, + enum mm_order *order, uint8_t *flags); + +void flush_tlb(); +void flush_tlb_all(); + +void populate_root_branch(struct vm_branch *b); +int setup_kernel_io(struct vm_branch *b, vm_t paddr); +struct vm_branch *init_vmem(void *fdt); + +#endif /* APOS_ARCH_PAGES_H */ |