From 2a256aa4f1abb65afa6f3856998bfe00ac960d61 Mon Sep 17 00:00:00 2001 From: Kimplul Date: Sun, 17 Apr 2022 12:22:04 +0300 Subject: improve node subsys + More robust alignment and less memory usage for status, from enum to bit --- common/nodes.c | 49 +++++++++++++++++++++++++++++-------------------- 1 file changed, 29 insertions(+), 20 deletions(-) (limited to 'common/nodes.c') diff --git a/common/nodes.c b/common/nodes.c index e264529..6ff42b1 100644 --- a/common/nodes.c +++ b/common/nodes.c @@ -1,16 +1,17 @@ #include #include +#include #include #include -#define MAX_NODES(node_size)\ - ((BASE_PAGE_SIZE - sizeof(struct node_region)) / (sizeof(enum node_status) + node_size)) - -#define region_to_nodes(r)\ - ((enum node_status *)((char *)(r) + sizeof(struct node_region))) - -#define node_status(r)\ - ((enum node_status *)((char *)(r) - sizeof(enum node_status))) +/* the structure of each node_region is approximately + * + * struct node_region | bitmap | array of node_size nodes + * + * where array starts on a multiple of node_size to ensure alignment and + * bitmap is a bitmap of whether node at index is free or used (1 being used, 0 + * being free) + */ #define node_region(r)\ ((struct node_region *)((uintptr_t)(r) & ~(BASE_PAGE_SIZE - 1))) @@ -27,6 +28,16 @@ void init_nodes(struct node_root *r, size_t node_size) r->head = __create_region(); r->av_head = r->head; r->node_size = node_size; + r->bitmap = sizeof(struct node_region); + + /* ideal values */ + size_t max_nodes = BASE_PAGE_SIZE / node_size; + /* make sure not to truncate division */ + size_t bitmap_size = (max_nodes / 8) + 1; + uintptr_t first_node = r->bitmap + bitmap_size; + /* actual values */ + r->first_node = align_up(first_node, node_size); + r->max_nodes = max_nodes - (r->first_node / node_size); } void destroy_nodes(struct node_root *r) @@ -41,15 +52,13 @@ void destroy_nodes(struct node_root *r) static void *__find_free_node(struct node_root *r, struct node_region *nr) { - enum node_status *w = region_to_nodes(nr); - for (size_t i = 0; i < MAX_NODES(r->node_size); ++i) { - if (*w != FREE) { - w = (enum node_status *)(r->node_size + (uint8_t *)(w + 1)); + uint8_t *bitmap = r->bitmap + (uint8_t *)nr; + for (size_t i = 0; i < r->max_nodes; ++i) { + if (bitmap_is_set(bitmap, i)) continue; - } - *w = USED; - return (void *)(w + 1); + bitmap_set(bitmap, i); + return (i * r->node_size) + (r->first_node + (uint8_t *)nr); } return 0; @@ -81,7 +90,7 @@ void *get_node(struct node_root *r) } void *p = __find_free_node(r, r->av_head); - if (++r->av_head->used_nodes == MAX_NODES(r->node_size)) + if (++r->av_head->used_nodes == r->max_nodes) __pop_av_head(r); return p; @@ -133,10 +142,10 @@ static void __free_region(struct node_root *r, struct node_region *nr) void free_node(struct node_root *r, void *p) { - enum node_status *w = node_status(p); - *w = FREE; - - struct node_region *nr = node_region(w); + struct node_region *nr = node_region(p); + uint8_t *bitmap = r->bitmap + (uint8_t *)nr; + size_t i = ((uintptr_t)p - (r->first_node + (uintptr_t)nr)) / r->node_size; + bitmap_clear(bitmap, i); if (--nr->used_nodes == 0) { __free_region(r, nr); -- cgit v1.3