From e71dd2d9fe1cc3a6d074f9c1894e2c5200cecdb1 Mon Sep 17 00:00:00 2001 From: Kimplul Date: Sat, 16 Apr 2022 19:25:05 +0300 Subject: create more general node structure + Allow for easier handling of other subsystems that want to use nodes, mainly tcb and possibly dev_mem --- common/mem_nodes.c | 148 ++--------------------------------------------- common/nodes.c | 148 +++++++++++++++++++++++++++++++++++++++++++++++ include/apos/mem_nodes.h | 1 + include/apos/nodes.h | 30 ++++++++++ 4 files changed, 184 insertions(+), 143 deletions(-) create mode 100644 common/nodes.c create mode 100644 include/apos/nodes.h diff --git a/common/mem_nodes.c b/common/mem_nodes.c index 2ab6978..392fa3e 100644 --- a/common/mem_nodes.c +++ b/common/mem_nodes.c @@ -4,162 +4,24 @@ #include #include -enum block_status { FREE = 0, USED = 1 }; - -struct block_wrapper { - enum block_status status; - struct mem_region n; -}; - -struct block_region { - size_t used_blocks; - - struct block_region *av_next; - struct block_region *av_prev; - - struct block_region *next; - struct block_region *prev; -}; - -#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 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 *head = 0; -static struct block_region *av_head = 0; - -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; -} +static struct node_root root; void init_mem_blocks() { - head = __create_region(); - av_head = head; + init_nodes(&root, sizeof(struct mem_region)); } void destroy_mem_blocks() { - struct block_region *r = head; - while (r) { - struct block_region *d = r; - r = r->prev; - free_page(MM_O0, (pm_t)d); - } -} - -static struct mem_region *__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 __pop_av_head() -{ - struct block_region *t = av_head; - av_head = av_head->av_next; - if (av_head) - av_head->av_prev = 0; - - t->av_next = 0; - t->av_prev = 0; + destroy_nodes(&root); } struct mem_region *get_mem_node() { - if (!av_head) { - av_head = __create_region(); - - av_head->prev = head; - head->next = av_head; - - head = av_head; - } - - struct mem_region *ret = __find_free_block(av_head); - - if (++av_head->used_blocks == MAX_BLOCKS) - __pop_av_head(); - - return ret; -} - -static void __push_av_head(struct block_region *r) -{ - r->av_prev = 0; - r->av_next = av_head; - if (av_head) - av_head->av_prev = r; - - av_head = r; -} - -static void __free_block(struct block_region *r) -{ - struct block_region *av_n = r->av_next; - struct block_region *av_p = r->av_prev; - - if (av_n) - av_n->av_prev = av_p; - - if (av_p) - av_p->av_next = av_n; - - if (r == av_head) - __pop_av_head(); - - struct block_region *n = r->next; - struct block_region *p = r->prev; - - if (n) - n->prev = p; - - if (p) - p->next = n; - - if (r == head) { - if (head->prev) { - head->next = 0; - head = head->prev; - } else - return; - } - - free_page(BASE_PAGE, (pm_t)r); + return (struct mem_region *)get_node(&root); } void free_mem_node(struct mem_region *m) { - struct block_wrapper *w = block_container(m); - w->status = FREE; - - struct block_region *r = block_region(w); - - if (--r->used_blocks == 0) { - __free_block(r); - return; - } - - else if (!r->av_next && !r->av_prev) - __push_av_head(r); + free_node(&root, (void *)m); } diff --git a/common/nodes.c b/common/nodes.c new file mode 100644 index 0000000..e264529 --- /dev/null +++ b/common/nodes.c @@ -0,0 +1,148 @@ +#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))) + +#define node_region(r)\ + ((struct node_region *)((uintptr_t)(r) & ~(BASE_PAGE_SIZE - 1))) + +static struct node_region *__create_region() +{ + struct node_region *r = (struct node_region *)alloc_page(BASE_PAGE, 0); + memset(r, FREE, BASE_PAGE_SIZE); + return r; +} + +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; +} + +void destroy_nodes(struct node_root *r) +{ + struct node_region *nr = r->head; + while (nr) { + struct node_region *d = nr; + nr = nr->prev; + free_page(BASE_PAGE, (pm_t)d); + } +} + +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)); + continue; + } + + *w = USED; + return (void *)(w + 1); + } + + return 0; +} + +static void __pop_av_head(struct node_root *r) +{ + struct node_region *t = r->av_head; + r->av_head = r->av_head->next; + if (r->av_head) + r->av_head->av_prev = 0; + + t->av_next = 0; + t->av_prev = 0; +} + +void *get_node(struct node_root *r) +{ + if (!r) + return 0; + + if (!r->av_head) { + r->av_head = __create_region(); + + r->av_head->prev = r->head; + r->head->next = r->av_head; + + r->head = r->av_head; + } + + void *p = __find_free_node(r, r->av_head); + if (++r->av_head->used_nodes == MAX_NODES(r->node_size)) + __pop_av_head(r); + + return p; +} + +static void __push_av_head(struct node_root *r, struct node_region *nr) +{ + nr->av_prev = 0; + nr->av_next = r->av_head; + if (r->av_head) + r->av_head->av_prev = nr; + + r->av_head = nr; +} + +static void __free_region(struct node_root *r, struct node_region *nr) +{ + struct node_region *av_n = nr->av_next; + struct node_region *av_p = nr->av_prev; + + if (av_n) + av_n->av_prev = av_p; + + if (av_p) + av_p->av_next = av_n; + + if (nr == r->av_head) + __pop_av_head(r); + + struct node_region *n = nr->next; + struct node_region *p = nr->prev; + + if (n) + n->prev = p; + + if (p) + p->next = n; + + if (nr == r->head) { + if (r->head->prev) { + r->head->next = 0; + r->head = r->head->prev; + } else + return; + } + + free_page(BASE_PAGE, (pm_t)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); + + if (--nr->used_nodes == 0) { + __free_region(r, nr); + return; + } + + else if (!nr->av_next && !nr->av_prev) + __push_av_head(r, nr); +} diff --git a/include/apos/mem_nodes.h b/include/apos/mem_nodes.h index 7a3169f..50f280d 100644 --- a/include/apos/mem_nodes.h +++ b/include/apos/mem_nodes.h @@ -2,6 +2,7 @@ #define MM_NODES_H #include +#include void init_mem_blocks(); void destroy_mem_blocks(); diff --git a/include/apos/nodes.h b/include/apos/nodes.h new file mode 100644 index 0000000..80888e1 --- /dev/null +++ b/include/apos/nodes.h @@ -0,0 +1,30 @@ +#ifndef APOS_NODES_H +#define APOS_NODES_H + +#include + +enum node_status { FREE = 0, USED = 1}; +struct node_region { + size_t used_nodes; + + struct node_region *av_next; + struct node_region *av_prev; + + struct node_region *next; + struct node_region *prev; +}; + +struct node_root { + size_t node_size; + + struct node_region *head; + struct node_region *av_head; +}; + +void init_nodes(struct node_root *r, size_t node_size); +void destroy_nodes(struct node_root *r); + +void *get_node(struct node_root *r); +void free_node(struct node_root *r, void *p); + +#endif /* APOS_NODES_H */ -- cgit v1.3