create more general node structure

+ Allow for easier handling of other subsystems that want to use nodes,
  mainly tcb and possibly dev_mem

4 files changed, 184 insertions, 143 deletions

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 <apos/string.h>
 #include <apos/mem_nodes.h>
 
-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 <apos/mem.h>
+#include <apos/pmem.h>
+#include <apos/nodes.h>
+#include <apos/string.h>
+
+#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 <apos/vmem.h>
+#include <apos/nodes.h>
 
 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 <apos/types.h>
+
+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 */