From 8bb1e280280c2f30740defca68ea643c56a3d880 Mon Sep 17 00:00:00 2001 From: Kimplul Date: Sun, 19 Dec 2021 10:48:40 +0200 Subject: [WIP] virtual memory management --- arch/riscv/kernel/main.c | 1 + common/mem_nodes.c | 161 ++++++++++++++++++ common/sp_tree.c | 236 ++++++++++++++++++++++++++ common/vmem.c | 434 ++++++++++++++++++++++++----------------------- include/apos/mem.h | 3 + include/apos/mem_nodes.h | 12 ++ include/apos/sp_tree.h | 36 ++++ include/apos/utils.h | 17 ++ include/apos/vmem.h | 29 +++- 9 files changed, 711 insertions(+), 218 deletions(-) create mode 100644 common/mem_nodes.c create mode 100644 common/sp_tree.c create mode 100644 include/apos/mem_nodes.h create mode 100644 include/apos/sp_tree.h diff --git a/arch/riscv/kernel/main.c b/arch/riscv/kernel/main.c index aaf828c..3f524bc 100644 --- a/arch/riscv/kernel/main.c +++ b/arch/riscv/kernel/main.c @@ -20,6 +20,7 @@ static void kernel_dbg(void *fdt) static void map_fdt(struct vm_branch_t *branch, vm_t fdt_base, vm_t fdt_top) { + /* TODO: fix this shit */ map_vregion(branch, fdt_base, fdt_base, fdt_top - fdt_base, VM_R | VM_W |VM_V); } diff --git a/common/mem_nodes.c b/common/mem_nodes.c new file mode 100644 index 0000000..1779276 --- /dev/null +++ b/common/mem_nodes.c @@ -0,0 +1,161 @@ +#include +#include +#include +#include +#include + +enum block_status { + FREE = 0, USED = 1 +}; + +struct block_wrapper { + enum block_status status; + struct sp_mem n; +}; + +struct block_region { + size_t used_blocks; + struct sp_node sp_n; +}; + +static struct sp_root root_region = (struct sp_root){0}; + +#define MAX_BLOCKS \ + ((BASE_PAGE_SIZE - sizeof(struct block_region)) / sizeof(struct block_wrapper)) + +#define block_region(b) \ + ((struct block_region *)((size_t)(b) & ~(BASE_PAGE_SIZE - 1))) + +#define region_container(b) \ + container_of(b, struct block_region, sp_n) + +#define block_container(b) \ + container_of(b, struct block_wrapper, n) + +#define region_to_array(r) \ + ((struct block_wrapper *)((char *)(r) + sizeof(struct block_region))) + +static struct block_region *__create_region() +{ + struct block_region *r = (struct block_region *)alloc_page(BASE_PAGE, 0); + memset(r, FREE, BASE_PAGE_SIZE); + return r; +} + +void init_mem_blocks() +{ + sp_root(root_region) = &__create_region()->sp_n; +} + +static void __destroy_mem_block(struct sp_node *n) +{ + if(!n) + return; + + __destroy_mem_block(sp_left(n)); + __destroy_mem_block(sp_right(n)); + + struct block_region *r = block_region(n); + free_page(BASE_PAGE, (vm_t)r); +} + +void destroy_mem_blocks() +{ + __destroy_mem_block(sp_root(root_region)); +} + +static struct sp_mem *__find_free_block(struct block_region *h) +{ + struct block_wrapper *w = region_to_array(h); + for(size_t i = 0; i < MAX_BLOCKS; ++i){ + if(w[i].status != FREE) + continue; + + w[i].status = USED; + return &w[i].n; + } + + return 0; +} + +static void __region_insert(struct block_region *r) +{ + struct sp_node *n = sp_root(root_region), *p = NULL; + enum sp_dir d = LEFT; + + r->sp_n = (struct sp_node){0}; + + while(n){ + struct block_region *t = region_container(n); + + p = n; + if(r->used_blocks < t->used_blocks){ + n = sp_left(n); + d = LEFT; + } + + else if(r->used_blocks > t->used_blocks){ + n = sp_right(n); + d = RIGHT; + } + + else if(r < t) { + n = sp_left(n); + d = LEFT; + } + + else { + n = sp_right(n); + d = RIGHT; + } + } + + sp_insert(&sp_root(root_region), p, &r->sp_n, d); +} + +static void __region_remove(struct block_region *r) +{ + sp_remove(&sp_root(root_region), &r->sp_n); +} + +static void __update_regions(struct block_region *r) +{ + __region_remove(r); + __region_insert(r); +} + +struct sp_mem *get_mem_node() +{ + struct sp_node *n = sp_root(root_region); + + while(n){ + struct block_region *r = region_container(n); + + if(r->used_blocks != MAX_BLOCKS){ + r->used_blocks++; + __update_regions(r); + + return __find_free_block(r); + } + + n = n->left; + } + + /* we need to allocate a new region */ + struct block_region *r = __create_region(); + r->used_blocks++; + __region_insert(r); + + return __find_free_block(r); +} + +void free_mem_node(struct sp_mem *m) +{ + struct block_wrapper *w = block_container(m); + w->status = FREE; + + struct block_region *r = block_region(w); + r->used_blocks--; + + __update_regions(r); +} diff --git a/common/sp_tree.c b/common/sp_tree.c new file mode 100644 index 0000000..abfaa4b --- /dev/null +++ b/common/sp_tree.c @@ -0,0 +1,236 @@ +#include + +inline static void __sp_turn_left(struct sp_node *n) +{ + struct sp_node *l = sp_left(n); + struct sp_node *p = sp_paren(n); + + sp_paren(l) = sp_paren(n); + sp_left(n) = sp_right(l); + sp_paren(n) = l; + sp_right(l) = n; + + if(p && sp_left(p) == n) + sp_left(p) = l; + else if (p) + sp_right(p) = l; + + if(sp_left(n)) + sp_lparen(n) = n; +} + +inline static void __sp_turn_right(struct sp_node *n) +{ + struct sp_node *r = sp_right(n); + struct sp_node *p = sp_paren(n); + + sp_paren(r) = sp_paren(n); + sp_right(n) = sp_left(r); + sp_paren(n) = r; + sp_left(r) = n; + + if(p && sp_left(p) == n) + sp_left(p) = r; + else if (p) + sp_right(p) = r; + + if(sp_right(n)) + sp_rparen(n) = n; +} + +inline static int __sp_balance(struct sp_node *n) +{ + int l = 0; + int r = 0; + + if(sp_left(n)) + l = sp_left(n)->hint + 1; + + if(sp_right(n)) + r = sp_right(n)->hint + 1; + + return l - r; +} + +inline static int __sp_max_hint(struct sp_node *n) +{ + int l = 0; + int r = 0; + + if(sp_left(n)) + l = sp_left(n)->hint + 1; + + if(sp_right(n)) + r = sp_right(n)->hint + 1; + + if(l > r) + return l; + else + return r; +} + +inline static void sp_update(struct sp_node **root, struct sp_node *n) +{ + while(n){ + + int b = __sp_balance(n); + int prev_hint = n->hint; + struct sp_node *p = sp_paren(n); + + if(b < -1) { + /* leaning to the right */ + if(n == *root) + *root = sp_right(n); + + __sp_turn_right(n); + } + + else if(b > 1){ + /* leaning to the left */ + if(n == *root) + *root = sp_left(n); + + __sp_turn_left(n); + } + + n->hint = __sp_max_hint(n); + if(n->hint == 0 || n->hint != prev_hint) + n = p; + else + return; + } +} + +void sp_insert(struct sp_node **root, struct sp_node *p, + struct sp_node *n, enum sp_dir d) +{ + if(!*root){ + *root = n; + return; + } + + if(d == LEFT) + sp_left(p) = n; + else + sp_right(p) = n; + + sp_paren(n) = p; + sp_update(root, n); +} + +inline static void __sp_replace_right(struct sp_node *n, struct sp_node *r) +{ + struct sp_node *p = sp_paren(n); + struct sp_node *rp = sp_paren(r); + + if(sp_left(rp) == r){ + sp_left(rp) = sp_right(r); + if(sp_right(r)) + sp_rparen(r) = rp; + } + + if(sp_paren(rp) == n) + sp_paren(rp) = r; + + sp_paren(r) = p; + sp_left(r) = sp_left(n); + + if(sp_right(n) != r){ + sp_right(r) = sp_right(n); + sp_rparen(n) = r; + } + + if(p && sp_left(p) == n) + sp_left(p) = r; + else if (p) + sp_right(p) = r; + + if(sp_left(n)) + sp_lparen(n) = r; +} + +inline static void __sp_replace_left(struct sp_node *n, struct sp_node *l) +{ + struct sp_node *p = sp_paren(n); + struct sp_node *lp = sp_paren(l); + + if(sp_right(lp) == l){ + sp_right(lp) = sp_left(l); + if(sp_left(l)) + sp_lparen(l) = lp; + } + + if(sp_paren(lp) == n) + sp_paren(lp) = l; + + sp_paren(l) = p; + sp_right(l) = sp_right(n); + + if(sp_left(n) != l){ + sp_left(l) = sp_left(n); + sp_lparen(n) = l; + } + + if(p && sp_left(p) == n) + sp_left(p) = l; + else if (p) + sp_right(p) = l; + + if(sp_right(n)) + sp_rparen(n) = l; +} + +/* TODO: handle root better */ +void sp_remove(struct sp_node **root, struct sp_node *del) +{ + if(sp_right(del)){ + struct sp_node *least = sp_first(sp_right(del)); + + if(del == *root) + *root = least; + + __sp_replace_right(del, least); + sp_update(root, sp_right(least)); + return; + } + + if(sp_left(del)){ + struct sp_node *most = sp_last(sp_left(del)); + + if(del == *root) + *root = most; + + __sp_replace_left(del, most); + sp_update(root, sp_left(most)); + return; + } + + if(del == *root){ + *root = 0; + return; + } + + /* empty node */ + struct sp_node *paren = sp_paren(del); + + if(sp_left(paren) == del) + sp_left(paren) = 0; + else + sp_right(paren) = 0; + + sp_update(root, paren); +} + +struct sp_node *sp_first(struct sp_node *n) +{ + if(!sp_left(n)) return n; + + return sp_first(sp_left(n)); +} + +struct sp_node *sp_last(struct sp_node *n) +{ + if(!sp_right(n)) return n; + + return sp_last(sp_right(n)); +} diff --git a/common/vmem.c b/common/vmem.c index 87d5b3b..267fbb7 100644 --- a/common/vmem.c +++ b/common/vmem.c @@ -1,275 +1,291 @@ #include -#include -#include -#include +#include -/* new idea, not implemented: - * region(free) -> region(not free) -> region(free) -> region(free) ... +#define mark_region_used(r) ((r) = 1) +#define mark_region_unused(r) ((r) = 0) +#define is_region_used(r) (r) + +static struct sp_root free_regions = (struct sp_root){0}; +static struct sp_root used_regions = (struct sp_root){0}; + +/* pretty major slowdown when we get to some really massive numbers, not + * entirely sure why. Will need to check up on this at some point, have I + * somehow managed to come up with a _very_ bad situation for my sp_trees? + * + * EDIT: apparently, yeah. Max depth of 106 with a million entries, interesting. + * I guess since in this scenario all sizes are 1, and I just shove everything + * to the right? Maybe? + * + * EDIT upon EDIT: yeah, when taking the start position of the region into + * account we get a much more sensible max depth of 39 for 5 million entries. + * Seems I have found a weakness in sp_trees :D * - * each region comes right after the next, would at least be pretty quick to - * merge free blocks? + * Duplicate entries don't work well with any trees, I think. Good to know, + * maybe not even anything with sp_trees but more a weakness of binary trees in + * general? */ - -enum mm_block_status_t { - FREE, USED -}; - -struct mm_block_region_t; - -/* linked list for now because I'm shit at coding */ -struct mm_block_t { - enum mm_block_status_t status; - vm_t start; - vm_t end; - struct mm_block_t *next; - struct mm_block_t *prev; -}; - -struct mm_block_region_t { - vm_t vaddr; - size_t blocks; - size_t max_blocks; - struct mm_block_region_t *next; - struct mm_block_t *first; -}; - -static struct mm_block_region_t *root_region = (struct mm_block_region_t *)ROOT_REGION; -static struct mm_block_t *root_block = 0; - -#define NODE_REGION(x) ((struct mm_block_region_t *)(((vm_t)x) & (__mm_page_shift - 1))) -#define NEXT_BLOCK() ((struct mm_block_region_t *)\ -((region_counter * __o_size(MM_O0)) + ROOT_PTE)) - -/* TODO: mark all used regions, also blocks */ -static struct mm_block_t *get_free_block(struct vm_branch_t *branch) +static struct sp_mem *sp_free_insert_region(struct sp_mem *m) { - struct mm_block_region_t *region = root_region; - size_t region_counter = 1; - for(; region; region = region->next){ - if(region->next == 0){ - pm_t next_pa = alloc_page(MM_O0, 0); - struct mm_block_region_t *next_va = NEXT_BLOCK(); - - map_vmem(branch, next_pa, (vm_t)next_va, - VM_W | VM_R | VM_V, MM_O0); - - memset(next_va, 0, __o_size(MM_O0)); - next_va->max_blocks = - (__o_size(MM_O0) - sizeof(struct mm_block_region_t)) - / sizeof(struct mm_block_t); - - region->next = next_va; + struct sp_node *n = sp_root(free_regions), *p = NULL; + size_t start = m->start; + size_t size = m->end - m->start; + enum sp_dir d = LEFT; + + 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; } - if(region->blocks == region->max_blocks) - continue; + else if(size > nsize) { + n = sp_right(n); + d = RIGHT; + } - struct mm_block_t *block = region->first; - for(size_t i = 0; i < region->max_blocks; ++i){ - if(block[i].start == 0 && block[i].end == 0){ - NODE_REGION(&block[i])->blocks++; - return &block[i]; - } + else if (start < t->start){ + n = sp_left(n); + d = LEFT; } - region_counter++; + else { + n = sp_right(n); + d = RIGHT; + } } - return 0; -} + if(sp_root(free_regions)) + sp_insert(&sp_root(free_regions), p, &m->sp_n, d); + else + sp_root(free_regions) = &m->sp_n; -void init_vmem(struct vm_branch_t *branch, vm_t tmp_pte) -{ -#if defined(KERNEL) - arch_init_vmem(branch, tmp_pte); -#else - (void)tmp_pte; -#endif - - pm_t first_block = alloc_page(MM_O0, 0); - map_vmem(branch, first_block, (vm_t)root_region, VM_W | VM_R | VM_V, MM_O0); - memset(root_region, 0, __o_size(MM_O0)); - - /* apparently I'm overwriting some memory here which is fucking up - * things elsewhere, specifically some PTE. Really should come up with - * some sensible address mappings, as everything is at the moment sort - * of hither and tither. */ - root_region->max_blocks = (__o_size(MM_O0) - sizeof(struct mm_block_region_t)) - / sizeof(struct mm_block_t); - root_region->first = (struct mm_block_t *)((vm_t)root_region + sizeof(struct mm_block_t)); - root_block = root_region->first; - - root_block->start = __o_size(MM_O0); - /* TODO: add in UMEM_TOP or something */ - root_block->end = -1; - root_block->status = FREE; + return m; } - -/* ... new_node -> node ... */ -static void insert_before(struct vm_branch_t *branch, struct mm_block_t *node, vm_t split) +static struct sp_mem *sp_used_insert_region(struct sp_mem *m) { - struct mm_block_t *new_node = get_free_block(branch); + struct sp_node *n = sp_root(used_regions), *p = NULL; + vm_t start = m->start; + enum sp_dir d = LEFT; - new_node->start = node->start; - new_node->end = split; + m->sp_n = (struct sp_node){0}; - node->start = split; + while(n){ + struct sp_mem *t = mem_container(n); - struct mm_block_t *prev = node->prev; - new_node->next = node; - new_node->prev = prev; - prev->next = new_node; - node->prev = new_node; -} + p = n; -/* ... node -> new_node ... */ -static void insert_after(struct vm_branch_t *branch, struct mm_block_t *node, vm_t split) -{ - struct mm_block_t *new_node = get_free_block(branch); + if(start < t->start){ + n = sp_left(n); + d = LEFT; + } - new_node->start = split; - new_node->end = node->end; + else { + /* we should never encounter a situation where start = + * t->start */ + n = sp_right(n); + d = RIGHT; + } + } - node->end = split; + if(sp_root(used_regions)) + sp_insert(&sp_root(used_regions), p, &m->sp_n, d); + else + sp_root(used_regions) = &m->sp_n; - struct mm_block_t *next = node->next; - new_node->next = next; - new_node->prev = node; - next->prev = new_node; - node->next = new_node; + return m; } -static void gobble_block(struct vm_branch_t *branch, struct mm_block_t *node, - vm_t start, vm_t end) +int sp_mem_init(size_t arena_size) { - node->status = USED; + struct sp_mem *m = get_mem_node(); + m->end = arena_size; + sp_free_insert_region(m); + + return 0; +} - /* ... node ... */ - if(node->start == start && node->end == end) +static void __sp_mem_destroy(struct sp_node *n) +{ + if(!n) return; - /* ... node -> new_node ... */ - if(node->start == start && node->end >= end){ - insert_after(branch, node, end); - struct mm_block_t *new = node->next; + __sp_mem_destroy(sp_left(n)); + __sp_mem_destroy(sp_right(n)); - new->status = FREE; - return; - } + struct sp_mem *m = mem_container(n); + free_mem_node(m); +} - /* ... new_node -> node ...*/ - if(node->start < start && node->end == end){ - insert_before(branch, node, start); - struct mm_block_t *new = node->prev; +void sp_mem_destroy() +{ + __sp_mem_destroy(sp_root(free_regions)); + __sp_mem_destroy(sp_root(used_regions)); +} - new->status = FREE; - return; +/* interestingly this is now the main bottleneck :D + * + * eh, it's not a massive thing I guess, maybe the code could be a bit quicker + * but I mean 10 000 000 memory allocations in 20 s is good enough for now + * */ +static struct sp_mem *sp_used_find(vm_t start) +{ + struct sp_node *n = sp_root(used_regions); + while(n){ + struct sp_mem *t = mem_container(n); + if(start == t->start) + return t; + + if(start < t->start) + n = sp_left(n); + else + n = sp_right(n); } - /* ... new_node1 -> node -> new_node2 .. */ - insert_before(branch, node, start); - struct mm_block_t *prev = node->prev; - - insert_after(branch, node, end); - struct mm_block_t *next = node->next; + return 0; +} - prev->status = FREE; - next->status = FREE; +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; } -/* only map with 4K blocks to keep it simple for now */ -vm_t map_vregion(struct vm_branch_t *branch, pm_t base, vm_t start, size_t size, - uint8_t flags) +static struct sp_mem *sp_free_find_first(size_t size, size_t alignment) { - struct mm_block_t *node = root_block; - for(; node; node = node->next){ - if(node->start > start) - return 0; - - if(node->status == FREE && node->end >= start + size){ - gobble_block(branch, node, start, start + size); - goto found; - } + struct sp_node *n = sp_root(free_regions); + while(n){ + struct sp_mem *t = mem_container(n); + size_t nsize = t->end - align_up(t->start, alignment); + + if(size <= nsize) + return t; + + n = sp_right(n); } return 0; +} + +/* apparently Linux doesn't necessarily give a shit about mmap hints, so I'll + * just ignore them for now. Note that alloc_region should only be used when + * mmap is called with MAP_ANON, all other situations should be handled in some + * fs server */ +vm_t alloc_region(size_t size, size_t alignment) +{ + struct sp_mem *m = sp_free_find_first(size, alignment); + if(!m) + return 0; + + sp_remove(&sp_root(free_regions), &m->sp_n); + + vm_t aligned_start = align_up(m->start, alignment); + + vm_t pre_start = m->start; + vm_t pre_end = aligned_start; + + vm_t start = pre_end; + vm_t end = aligned_start + size; + + vm_t post_start = end; + vm_t post_end = m->end; + + if(pre_start != pre_end){ + struct sp_mem *n = sp_mem_create_region(pre_start, pre_end, m->prev, m); + m->prev = n; + if(n->prev) + n->prev->next = n; + + sp_free_insert_region(n); + } + + if(post_start != post_end){ + struct sp_mem *n = sp_mem_create_region(post_start, post_end, m, m->next); + m->next = n; + if(n->next) + n->next->prev = n; -found: - for(; size >= __o_size(MM_O0); size -= __o_size(MM_O0)){ - map_vmem(branch, start, base, flags, MM_O0); - start += __o_size(MM_O0); - base += __o_size(MM_O0); + sp_free_insert_region(n); } + m->end = end; + m->start = start; + mark_region_used(m->flags); + sp_used_insert_region(m); return start; } -static void free_block(struct mm_block_t *node) +static void __sp_try_coalesce_prev(struct sp_mem *m) { - struct mm_block_t *prev = node->prev; - struct mm_block_t *next = node->next; + while(m){ + if(!m || is_region_used(m->flags)) + return; - if(prev->status == FREE && next->status == FREE){ - /* merge all three blocks */ - prev->end = next->end; - prev->next = next->next; - next->next->prev = prev; + struct sp_mem *p = m->prev; + if(!p || is_region_used(p->flags)) + return; - node->start = 0; - node->end = 0; + m->start = p->start; + m->prev = p->prev; - next->start = 0; - next->end = 0; + if(m->prev) + m->prev->next = m; - NODE_REGION(node)->blocks--; - NODE_REGION(next)->blocks--; - return; + sp_remove(&sp_root(free_regions), &p->sp_n); + free_mem_node(p); + + m = m->prev; } +} - if(prev->status == FREE){ - prev->end = node->end; - prev->next = next; - next->prev = prev; +static void __sp_try_coalesce_next(struct sp_mem *m) +{ + while(m){ + if(!m || is_region_used(m->flags)) + return; - node->start = 0; - node->end = 0; + struct sp_mem *n = m->next; + if(!n || is_region_used(n->flags)) + return; - NODE_REGION(node)->blocks--; - return; - } + m->end = n->end; + m->next = n->next; - if(next->status == FREE){ - next->start = node->start; - next->prev = prev; - prev->next = next; + if(m->next) + m->next->prev = m; - node->start = 0; - node->end = 0; + sp_remove(&sp_root(free_regions), &n->sp_n); + free_mem_node(n); - NODE_REGION(node)->blocks--; - return; + m = m->next; } +} - node->status = FREE; +static void sp_mem_try_coalesce(struct sp_mem *m) +{ + __sp_try_coalesce_prev(m); + __sp_try_coalesce_next(m); } -void unmap_vregion(struct vm_branch_t *branch, vm_t start) +void free_region(vm_t start) { - size_t size = 0; - struct mm_block_t *node = root_block; - for(; node; node = node->next){ - /* if node->start == start status should be USED in all cases, - * but let's just go with this - */ - if(node->status == USED && node->start == start){ - size = node->end - node->start; - free_block(node); - } - } + struct sp_mem *m = sp_used_find(start); + if(!m) + return; - for(; size >= __o_size(MM_O0); size -= __o_size(MM_O0)){ - unmap_vmem(branch, start, MM_O0); - start += __o_size(MM_O0); - } + sp_remove(&sp_root(used_regions), &m->sp_n); + mark_region_unused(m->flags); + + sp_mem_try_coalesce(m); + sp_free_insert_region(m); } diff --git a/include/apos/mem.h b/include/apos/mem.h index 7c5a2dc..0b3bffd 100644 --- a/include/apos/mem.h +++ b/include/apos/mem.h @@ -39,4 +39,7 @@ extern size_t __mm_max_order; void init_mem(size_t max_order, size_t shifts[10], size_t page_shift); enum mm_mode_t get_mmode(void *fdt); +#define BASE_PAGE_SIZE (__o_size(BASE_PAGE)) +#define BASE_PAGE (MM_O0) + #endif /* APOS_MEM_H */ diff --git a/include/apos/mem_nodes.h b/include/apos/mem_nodes.h new file mode 100644 index 0000000..a10e4ea --- /dev/null +++ b/include/apos/mem_nodes.h @@ -0,0 +1,12 @@ +#ifndef MM_NODES_H +#define MM_NODES_H + +#include + +void init_mem_blocks(); +void destroy_mem_blocks(); + +struct sp_mem *get_mem_node(); +void free_mem_node(struct sp_mem *m); + +#endif /* MM_NODES_H */ diff --git a/include/apos/sp_tree.h b/include/apos/sp_tree.h new file mode 100644 index 0000000..bbf9f9f --- /dev/null +++ b/include/apos/sp_tree.h @@ -0,0 +1,36 @@ +#ifndef SP_TREE_H +#define SP_TREE_H + +#define sp_root(r) (r.sp_r) +#define sp_left(n) (n->left) +#define sp_right(n) (n->right) +#define sp_rparen(n) (sp_right(n)->parent) +#define sp_lparen(n) (sp_left(n)->parent) +#define sp_paren(n) (n->parent) +#define sp_gparen(n) (n->parent->parent) +#define sp_has_gparen(n) (sp_paren(n) && sp_gparen(n)) + +struct sp_node { + short hint; + struct sp_node *left; + struct sp_node *right; + struct sp_node *parent; +}; + +struct sp_root { + struct sp_node *sp_r; +}; + +enum sp_dir { + LEFT, RIGHT +}; + +struct sp_node *sp_first(struct sp_node *n); +struct sp_node *sp_last(struct sp_node *n); + +void sp_insert(struct sp_node **root, struct sp_node *p, + struct sp_node *n, enum sp_dir d); + +void sp_remove(struct sp_node **root, struct sp_node *n); + +#endif /* SP_TREE_H */ diff --git a/include/apos/utils.h b/include/apos/utils.h index 39d5b83..881cd8f 100644 --- a/include/apos/utils.h +++ b/include/apos/utils.h @@ -14,10 +14,24 @@ #define GLUE2(x, y) x##y #define GLUE(x, y) GLUE2(x, y) +#include + +#if __has_builtin(__builtin_offsetof) +#define offsetof(type, member) __builtin_offsetof(type, member) +#else +#define offsetof(type, member) ((size_t)&((type *)0)->member) +#endif + +#define container_of(ptr, type, member) \ + ((type *)((char *)(ptr) - offsetof(type, member))) + #include static inline size_t align_up(size_t val, size_t a) { + if(!a) + return val; + size_t rem = val % a; if (rem == 0) @@ -28,6 +42,9 @@ static inline size_t align_up(size_t val, size_t a) static inline size_t align_down(size_t val, size_t a) { + if(!a) + return val; + return val - (val % a); } diff --git a/include/apos/vmem.h b/include/apos/vmem.h index e72f783..eb7ad17 100644 --- a/include/apos/vmem.h +++ b/include/apos/vmem.h @@ -1,11 +1,29 @@ #ifndef APOS_VMEM_H #define APOS_VMEM_H -#include - /* arch-specific data */ #include +/* common */ +#include +#include + +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) + + /* general overview of the different functions: * (un)map_vmem: map one known page of physical memory to one known page of * virtual memory @@ -29,11 +47,4 @@ vm_t map_vregion(struct vm_branch_t *branch, pm_t base, vm_t start, size_t size, void unmap_vregion(struct vm_branch_t *branch, vm_t start); void init_vmem(struct vm_branch_t *branch, vm_t tmp_pte); - -#if defined(KERNEL) -void arch_init_vmem(struct vm_branch_t *branch, vm_t tmp_pte); -#else -struct vm_branch_t *arch_get_tmp_pte(struct vm_branch_t *branch); -#endif - #endif /* APOS_VMEM_H */ -- cgit v1.3