summaryrefslogtreecommitdiff
path: root/kernel/src/memory/allocator.c
diff options
context:
space:
mode:
Diffstat (limited to 'kernel/src/memory/allocator.c')
-rw-r--r--kernel/src/memory/allocator.c314
1 files changed, 314 insertions, 0 deletions
diff --git a/kernel/src/memory/allocator.c b/kernel/src/memory/allocator.c
new file mode 100644
index 0000000..6217ad4
--- /dev/null
+++ b/kernel/src/memory/allocator.c
@@ -0,0 +1,314 @@
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+
+struct boundary_tag {
+ unsigned int magic;
+ unsigned int size;
+ unsigned int real_size;
+ int index;
+
+ struct boundary_tag *split_left;
+ struct boundary_tag *split_right;
+
+ struct boundary_tag *next;
+ struct boundary_tag *prev;
+};
+
+extern int memory_lock(void);
+extern int memory_unlock(void);
+extern void *memory_alloc_page(int);
+extern int memory_free_page(void* ,int);
+
+#define ALLOC_MAGIC 0xc001c0de
+#define MAXCOMPLETE 5
+#define MAXEXP 32
+#define MINEXP 8
+
+#define MODE_BEST 0
+#define MODE_INSTANT 1
+
+#define MODE MODE_BEST
+
+struct boundary_tag* l_freePages[MAXEXP];
+int l_completePages[MAXEXP];
+
+static int l_initialized = 0;
+static int l_pageSize = 4096;
+static int l_pageCount = 16;
+
+static inline int getexp(unsigned int size) {
+ if (size < (1<<MINEXP)) {
+ return -1;
+ }
+
+ int shift = MINEXP;
+
+ while (shift < MAXEXP) {
+ if ((unsigned)(1<<shift) > size) break;
+ shift += 1;
+ }
+
+ return shift - 1;
+}
+
+static inline void insert_tag(struct boundary_tag *tag, int index) {
+ int realIndex;
+
+ if (index < 0) {
+ realIndex = getexp(tag->real_size - sizeof(struct boundary_tag));
+ if (realIndex < MINEXP) realIndex = MINEXP;
+ } else {
+ realIndex = index;
+ }
+
+ tag->index = realIndex;
+
+ if (l_freePages[ realIndex ] != NULL) {
+ l_freePages[ realIndex ]->prev = tag;
+ tag->next = l_freePages[ realIndex ];
+ }
+
+ l_freePages[ realIndex ] = tag;
+}
+
+static inline void remove_tag(struct boundary_tag *tag) {
+ if (l_freePages[ tag->index ] == tag) l_freePages[ tag->index ] = tag->next;
+
+ if (tag->prev != NULL) tag->prev->next = tag->next;
+ if (tag->next != NULL) tag->next->prev = tag->prev;
+
+ tag->next = NULL;
+ tag->prev = NULL;
+ tag->index = -1;
+}
+
+static inline struct boundary_tag* melt_left(struct boundary_tag *tag) {
+ struct boundary_tag *left = tag->split_left;
+
+ left->real_size += tag->real_size;
+ left->split_right = tag->split_right;
+
+ if (tag->split_right != NULL) tag->split_right->split_left = left;
+
+ return left;
+}
+
+
+static inline struct boundary_tag* absorb_right(struct boundary_tag *tag) {
+ struct boundary_tag *right = tag->split_right;
+
+ remove_tag(right);
+
+ tag->real_size += right->real_size;
+
+ tag->split_right = right->split_right;
+ if (right->split_right != NULL)
+ right->split_right->split_left = tag;
+
+ return tag;
+}
+
+static inline struct boundary_tag* split_tag(struct boundary_tag* tag) {
+ unsigned int remainder = tag->real_size - sizeof(struct boundary_tag) - tag->size;
+
+ struct boundary_tag *new_tag =
+ (struct boundary_tag*)((uintptr_t)(void *)tag + sizeof(struct boundary_tag) + tag->size);
+
+ new_tag->magic = ALLOC_MAGIC;
+ new_tag->real_size = remainder;
+
+ new_tag->next = NULL;
+ new_tag->prev = NULL;
+
+ new_tag->split_left = tag;
+ new_tag->split_right = tag->split_right;
+
+ if (new_tag->split_right != NULL) new_tag->split_right->split_left = new_tag;
+ tag->split_right = new_tag;
+
+ tag->real_size -= new_tag->real_size;
+
+ insert_tag(new_tag, -1);
+
+ return new_tag;
+}
+
+static struct boundary_tag* allocate_new_tag(unsigned int size) {
+ unsigned int pages;
+ unsigned int usage;
+ struct boundary_tag *tag;
+
+ usage = size + sizeof(struct boundary_tag);
+
+ pages = usage / l_pageSize;
+ if ((usage % l_pageSize) != 0) pages += 1;
+
+ if (pages < (unsigned) l_pageCount) pages = l_pageCount;
+
+ tag = (struct boundary_tag*)memory_alloc_page(pages);
+
+ if (tag == NULL) return NULL;
+
+ tag->magic = ALLOC_MAGIC;
+ tag->size = size;
+ tag->real_size = pages * l_pageSize;
+ tag->index = -1;
+
+ tag->next = NULL;
+ tag->prev = NULL;
+ tag->split_left = NULL;
+ tag->split_right = NULL;
+
+ return tag;
+}
+
+
+
+void *malloc(size_t size) {
+ int index;
+ void *ptr;
+ struct boundary_tag *tag = NULL;
+
+ memory_lock();
+
+ if (l_initialized == 0) {
+ for (index = 0; index < MAXEXP; index++) {
+ l_freePages[index] = NULL;
+ l_completePages[index] = 0;
+ }
+ l_initialized = 1;
+ }
+
+ index = getexp(size) + MODE;
+ if (index < MINEXP) index = MINEXP;
+
+ tag = l_freePages[index];
+ while (tag != NULL) {
+ if (
+ (tag->real_size - sizeof(struct boundary_tag))
+ >= (size + sizeof(struct boundary_tag))
+ ) {
+ break;
+ }
+ tag = tag->next;
+ }
+
+ if (tag == NULL) {
+ if ((tag = allocate_new_tag(size)) == NULL) {
+ memory_unlock();
+ return NULL;
+ }
+ index = getexp(tag->real_size - sizeof(struct boundary_tag));
+ } else {
+ remove_tag(tag);
+
+ if ((tag->split_left == NULL) && (tag->split_right == NULL))
+ l_completePages[ index ] -= 1;
+ }
+
+ tag->size = size;
+
+ unsigned int remainder = tag->real_size - size - sizeof(struct boundary_tag) * 2;
+
+ if (((int)(remainder) > 0)) {
+ int childIndex = getexp(remainder);
+
+ if (childIndex >= 0) {
+ struct boundary_tag *new_tag = split_tag(tag);
+ tag = new_tag;
+ }
+ }
+
+ ptr = (void*)((uintptr_t)(void *)tag + sizeof(struct boundary_tag));
+ memory_unlock();
+ return ptr;
+}
+
+void free(void *ptr) {
+ int index;
+ struct boundary_tag *tag;
+
+ if (ptr == NULL) return;
+
+ memory_lock();
+
+ tag = (struct boundary_tag*)((uintptr_t)(void *)ptr - sizeof(struct boundary_tag));
+
+ if (tag->magic != ALLOC_MAGIC) {
+ memory_unlock();
+ return;
+ }
+
+ while ((tag->split_left != NULL) && (tag->split_left->index >= 0)) {
+ tag = melt_left(tag);
+ remove_tag(tag);
+ }
+
+ while ((tag->split_right != NULL) && (tag->split_right->index >= 0)) {
+ tag = absorb_right(tag);
+ }
+
+ index = getexp(tag->real_size - sizeof(struct boundary_tag));
+ if (index < MINEXP) index = MINEXP;
+
+ if ((tag->split_left == NULL) && (tag->split_right == NULL)) {
+ if (l_completePages[index] == MAXCOMPLETE) {
+ unsigned int pages = tag->real_size / l_pageSize;
+
+ if ((tag->real_size % l_pageSize) != 0) pages += 1;
+ if (pages < (unsigned) l_pageCount) pages = l_pageCount;
+
+ memory_free_page(tag, pages);
+ memory_unlock();
+ return;
+ }
+
+ l_completePages[ index ] += 1;
+ }
+
+ insert_tag(tag, index);
+
+ memory_unlock();
+}
+
+void* calloc(size_t nobj, size_t size) {
+ int real_size;
+ void *p;
+
+ real_size = nobj * size;
+
+ p = malloc(real_size);
+
+ memset(p, 0, real_size);
+
+ return p;
+}
+
+void* realloc(void *p, size_t size) {
+ void *ptr;
+ struct boundary_tag *tag;
+ size_t real_size;
+
+ if (size == 0) {
+ free(p);
+ return NULL;
+ }
+
+ if (p == NULL) {
+ return malloc(size);
+ }
+
+ memory_lock();
+ tag = (struct boundary_tag*)((uintptr_t)(void *)p - sizeof(struct boundary_tag));
+ real_size = tag->size;
+ memory_unlock();
+
+ if (real_size > size) real_size = size;
+
+ ptr = malloc(size);
+ memcpy(ptr, p, real_size);
+ free(p);
+
+ return ptr;
+}
generated by cgit v1.2.3-freya (git 2.51.0) at 2025-09-22 00:30:22 +0000