diff options
Diffstat (limited to 'common')
| -rw-r--r-- | common/mem_nodes.c | 161 | ||||
| -rw-r--r-- | common/sp_tree.c | 236 | ||||
| -rw-r--r-- | common/vmem.c | 414 |
3 files changed, 612 insertions, 199 deletions
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 <apos/vmem.h> +#include <apos/pmem.h> +#include <apos/mem.h> +#include <apos/string.h> +#include <apos/mem_nodes.h> + +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 <apos/sp_tree.h> + +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 <apos/vmem.h> -#include <apos/pmem.h> -#include <apos/mem.h> -#include <apos/string.h> +#include <apos/mem_nodes.h> -/* 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? */ +static struct sp_mem *sp_free_insert_region(struct sp_mem *m) +{ + 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; -enum mm_block_status_t { - FREE, USED -}; + m->sp_n = (struct sp_node){0}; -struct mm_block_region_t; + while(n){ + struct sp_mem *t = mem_container(n); + size_t nsize = t->end - t->start; + p = n; -/* 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; -}; + if(size < nsize){ + n = sp_left(n); + d = LEFT; + } -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; -}; + else if(size > nsize) { + n = sp_right(n); + d = RIGHT; + } -static struct mm_block_region_t *root_region = (struct mm_block_region_t *)ROOT_REGION; -static struct mm_block_t *root_block = 0; + else if (start < t->start){ + n = sp_left(n); + d = LEFT; + } -#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)) + else { + n = sp_right(n); + d = RIGHT; + } + } -/* TODO: mark all used regions, also blocks */ -static struct mm_block_t *get_free_block(struct vm_branch_t *branch) -{ - struct mm_block_region_t *region = root_region; - size_t region_counter = 1; - for(; region; region = region->next){ - if(region->next == 0){ - pm_t next_pa = alloc_page(MM_O0, 0); - struct mm_block_region_t *next_va = NEXT_BLOCK(); + if(sp_root(free_regions)) + sp_insert(&sp_root(free_regions), p, &m->sp_n, d); + else + sp_root(free_regions) = &m->sp_n; - map_vmem(branch, next_pa, (vm_t)next_va, - VM_W | VM_R | VM_V, MM_O0); + return m; +} - 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); +static struct sp_mem *sp_used_insert_region(struct sp_mem *m) +{ + struct sp_node *n = sp_root(used_regions), *p = NULL; + vm_t start = m->start; + enum sp_dir d = LEFT; - region->next = next_va; - } + m->sp_n = (struct sp_node){0}; + + while(n){ + struct sp_mem *t = mem_container(n); - if(region->blocks == region->max_blocks) - continue; + p = n; - 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]; - } + if(start < t->start){ + n = sp_left(n); + d = LEFT; } - region_counter++; + else { + /* we should never encounter a situation where start = + * t->start */ + n = sp_right(n); + d = RIGHT; + } } - return 0; + if(sp_root(used_regions)) + sp_insert(&sp_root(used_regions), p, &m->sp_n, d); + else + sp_root(used_regions) = &m->sp_n; + + return m; } -void init_vmem(struct vm_branch_t *branch, vm_t tmp_pte) +int sp_mem_init(size_t arena_size) { -#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)); + struct sp_mem *m = get_mem_node(); + m->end = arena_size; + sp_free_insert_region(m); - /* 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 0; } - -/* ... new_node -> node ... */ -static void insert_before(struct vm_branch_t *branch, struct mm_block_t *node, vm_t split) +static void __sp_mem_destroy(struct sp_node *n) { - struct mm_block_t *new_node = get_free_block(branch); - - new_node->start = node->start; - new_node->end = split; + if(!n) + return; - node->start = split; + __sp_mem_destroy(sp_left(n)); + __sp_mem_destroy(sp_right(n)); - struct mm_block_t *prev = node->prev; - new_node->next = node; - new_node->prev = prev; - prev->next = new_node; - node->prev = new_node; + struct sp_mem *m = mem_container(n); + free_mem_node(m); } -/* ... node -> new_node ... */ -static void insert_after(struct vm_branch_t *branch, struct mm_block_t *node, vm_t split) +void sp_mem_destroy() { - struct mm_block_t *new_node = get_free_block(branch); + __sp_mem_destroy(sp_root(free_regions)); + __sp_mem_destroy(sp_root(used_regions)); +} - new_node->start = split; - new_node->end = node->end; +/* 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; - node->end = split; + if(start < t->start) + n = sp_left(n); + else + n = sp_right(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 0; } -static void gobble_block(struct vm_branch_t *branch, struct mm_block_t *node, - vm_t start, vm_t end) +static struct sp_mem *sp_mem_create_region(vm_t start, vm_t end, + struct sp_mem *prev, struct sp_mem *next) { - node->status = USED; + struct sp_mem *m = get_mem_node(); + m->start = start; + m->end = end; + m->prev = prev; + m->next = next; + return m; +} - /* ... node ... */ - if(node->start == start && node->end == end) - return; +static struct sp_mem *sp_free_find_first(size_t size, size_t alignment) +{ + 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); - /* ... node -> new_node ... */ - if(node->start == start && node->end >= end){ - insert_after(branch, node, end); - struct mm_block_t *new = node->next; + if(size <= nsize) + return t; - new->status = FREE; - return; + n = sp_right(n); } - /* ... new_node -> node ...*/ - if(node->start < start && node->end == end){ - insert_before(branch, node, start); - struct mm_block_t *new = node->prev; + return 0; +} - new->status = FREE; - return; - } +/* 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; - /* ... new_node1 -> node -> new_node2 .. */ - insert_before(branch, node, start); - struct mm_block_t *prev = node->prev; + sp_remove(&sp_root(free_regions), &m->sp_n); - insert_after(branch, node, end); - struct mm_block_t *next = node->next; + vm_t aligned_start = align_up(m->start, alignment); - prev->status = FREE; - next->status = FREE; -} + vm_t pre_start = m->start; + vm_t pre_end = aligned_start; -/* only map with 4K blocks to keep it simple for now */ -vm_t map_vregion(struct vm_branch_t *branch, pm_t base, vm_t start, size_t size, - uint8_t flags) -{ - struct mm_block_t *node = root_block; - for(; node; node = node->next){ - if(node->start > start) - return 0; + vm_t start = pre_end; + vm_t end = aligned_start + size; - if(node->status == FREE && node->end >= start + size){ - gobble_block(branch, node, start, start + size); - goto found; - } + 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); } - return 0; + 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); } |