aboutsummaryrefslogtreecommitdiff
path: root/kernel/libk/kmalloc.c
diff options
context:
space:
mode:
Diffstat (limited to 'kernel/libk/kmalloc.c')
-rw-r--r--kernel/libk/kmalloc.c580
1 files changed, 580 insertions, 0 deletions
diff --git a/kernel/libk/kmalloc.c b/kernel/libk/kmalloc.c
new file mode 100644
index 0000000..69e77ba
--- /dev/null
+++ b/kernel/libk/kmalloc.c
@@ -0,0 +1,580 @@
+/*
+
+ * bubbl
+ * Copyright (C) 2025 Raghuram Subramani <raghus2247@gmail.com>
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include <kernel/spinlock.h>
+#include <libk/kmalloc.h>
+#include <libk/stdio.h>
+#include <mm/virtual_mm.h>
+#include <stdatomic.h>
+#include <stdint.h>
+
+static atomic_flag s_liballoc_lock;
+
+#define liballoc_alloc virtual_mm_alloc_pages
+#define liballoc_free virtual_mm_free_pages
+
+#define printf printk_raw
+
+int
+liballoc_lock(void)
+{
+ spinlock_acquire(&s_liballoc_lock);
+ return 0;
+}
+
+int
+liballoc_unlock(void)
+{
+ spinlock_release(&s_liballoc_lock);
+ return 0;
+}
+
+/** Durand's Ridiculously Amazing Super Duper Memory functions. */
+
+#define DEBUG
+
+#define LIBALLOC_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]; //< Allowing for 2^MAXEXP blocks
+int l_completePages[MAXEXP]; //< Allowing for 2^MAXEXP blocks
+
+#ifdef DEBUG
+unsigned int l_allocated = 0; //< The real amount of memory allocated.
+unsigned int l_inuse = 0; //< The amount of memory in use (kmalloc'ed).
+#endif
+
+static int l_initialized = 0; //< Flag to indicate initialization.
+static int l_pageSize = 4096; //< Individual page size
+static unsigned int l_pageCount = 16; //< Minimum number of pages to allocate.
+
+// *********** HELPER FUNCTIONS *******************************
+
+/** Returns the exponent required to manage 'size' amount of memory.
+ *
+ * Returns n where 2^n <= size < 2^(n+1)
+ */
+static inline unsigned int
+getexp(unsigned int size)
+{
+ if (size < (1 << MINEXP)) {
+#ifdef DEBUG
+ printf("getexp returns -1 for %i less than MINEXP\n", size);
+#endif
+ return -1; // Smaller than the quantum.
+ }
+
+ int shift = MINEXP;
+
+ while (shift < MAXEXP) {
+ if (((unsigned int) 1 << shift) > size)
+ break;
+ shift += 1;
+ }
+
+#ifdef DEBUG
+ printf("getexp returns %i (%i bytes) for %i size\n",
+ shift - 1,
+ (1 << (shift - 1)),
+ size);
+#endif
+
+ return shift - 1;
+}
+
+static void *
+liballoc_memset(void *s, int c, size_t n)
+{
+ size_t i;
+ for (i = 0; i < n; i++)
+ ((char *) s)[i] = c;
+
+ return s;
+}
+
+static void *
+liballoc_memcpy(void *s1, const void *s2, size_t n)
+{
+ char *cdest;
+ char *csrc;
+ unsigned int *ldest = (unsigned int *) s1;
+ unsigned int *lsrc = (unsigned int *) s2;
+
+ while (n >= sizeof(unsigned int)) {
+ *ldest++ = *lsrc++;
+ n -= sizeof(unsigned int);
+ }
+
+ cdest = (char *) ldest;
+ csrc = (char *) lsrc;
+
+ while (n > 0) {
+ *cdest++ = *csrc++;
+ n -= 1;
+ }
+
+ return s1;
+}
+
+#ifdef DEBUG
+static void
+dump_array(void)
+{
+ int i = 0;
+ struct boundary_tag *tag = NULL;
+
+ printf("------ Free pages array ---------\n");
+ printf("System memory allocated: %i\n", l_allocated);
+ printf("Memory in used (kmalloc'ed): %i\n", l_inuse);
+
+ for (i = 0; i < MAXEXP; i++) {
+ printf("%.2i(%i): ", i, l_completePages[i]);
+
+ tag = l_freePages[i];
+ while (tag != NULL) {
+ if (tag->split_left != NULL)
+ printf("*");
+ printf("%i", tag->real_size);
+ if (tag->split_right != NULL)
+ printf("*");
+
+ printf(" ");
+ tag = tag->next;
+ }
+ printf("\n");
+ }
+
+ printf("'*' denotes a split to the left/right of a tag\n");
+}
+#endif
+
+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); // Remove right from free pages.
+
+ 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 *) ((unsigned int) tag
+ + sizeof(struct boundary_tag) + tag->size);
+
+ new_tag->magic = LIBALLOC_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;
+
+ // This is how much space is required.
+ usage = size + sizeof(struct boundary_tag);
+
+ // Perfect amount of space
+ pages = usage / l_pageSize;
+ if ((usage % l_pageSize) != 0)
+ pages += 1;
+
+ // Make sure it's >= the minimum size.
+ if (pages < l_pageCount)
+ pages = l_pageCount;
+
+ tag = (struct boundary_tag *) liballoc_alloc(pages);
+
+ if (tag == NULL)
+ return NULL; // uh oh, we ran out of memory.
+
+ tag->magic = LIBALLOC_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;
+
+#ifdef DEBUG
+ printf("Resource allocated %x of %i pages (%i bytes) for %i size.\n",
+ tag,
+ pages,
+ pages * l_pageSize,
+ size);
+
+ l_allocated += pages * l_pageSize;
+
+ printf("Total memory usage = %i KB\n", (int) ((l_allocated / (1024))));
+#endif
+
+ return tag;
+}
+
+void *
+kmalloc(size_t size)
+{
+ int index;
+ void *ptr;
+ struct boundary_tag *tag = NULL;
+
+ liballoc_lock();
+
+ if (l_initialized == 0) {
+#ifdef DEBUG
+ printf("%s\n", "liballoc initializing.");
+#endif
+ 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;
+
+ // Find one big enough.
+ tag = l_freePages[index]; // Start at the front of the list.
+ while (tag != NULL) {
+ // If there's enough space in this tag.
+ if ((tag->real_size - sizeof(struct boundary_tag))
+ >= (size + sizeof(struct boundary_tag))) {
+#ifdef DEBUG
+ printf("Tag search found %i >= %i\n",
+ (tag->real_size - sizeof(struct boundary_tag)),
+ (size + sizeof(struct boundary_tag)));
+#endif
+ break;
+ }
+
+ tag = tag->next;
+ }
+
+ // No page found. Make one.
+ if (tag == NULL) {
+ if ((tag = allocate_new_tag(size)) == NULL) {
+ liballoc_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;
+ }
+
+ // We have a free page. Remove it from the free pages list.
+
+ tag->size = size;
+
+ // Removed... see if we can re-use the excess space.
+
+#ifdef DEBUG
+ printf("Found tag with %i bytes available (requested %i bytes, leaving %i), "
+ "which has exponent: %i (%i bytes)\n",
+ tag->real_size - sizeof(struct boundary_tag),
+ size,
+ tag->real_size - size - sizeof(struct boundary_tag),
+ index,
+ 1 << index);
+#endif
+
+ unsigned int remainder
+ = tag->real_size - size
+ - sizeof(struct boundary_tag) * 2; // Support a new tag + remainder
+
+ if (((int) (remainder)
+ > 0) /*&& ( (tag->real_size - remainder) >= (1<<MINEXP))*/) {
+ int childIndex = getexp(remainder);
+
+ if (childIndex >= 0) {
+#ifdef DEBUG
+ printf("Seems to be splittable: %i >= 2^%i .. %i\n",
+ remainder,
+ childIndex,
+ (1 << childIndex));
+#endif
+
+ struct boundary_tag *new_tag = split_tag(tag);
+ (void) new_tag;
+
+#ifdef DEBUG
+ printf("Old tag has become %i bytes, new tag is now %i bytes (%i exp)\n",
+ tag->real_size,
+ new_tag->real_size,
+ new_tag->index);
+#endif
+ }
+ }
+
+ ptr = (void *) ((unsigned int) tag + sizeof(struct boundary_tag));
+
+#ifdef DEBUG
+ l_inuse += size;
+ printf("kmalloc: %x, %i, %i\n",
+ ptr,
+ (int) l_inuse / 1024,
+ (int) l_allocated / 1024);
+ dump_array();
+#endif
+
+ liballoc_unlock();
+ return ptr;
+}
+
+void
+kfree(void *ptr)
+{
+ int index;
+ struct boundary_tag *tag;
+
+ if (ptr == NULL)
+ return;
+
+ liballoc_lock();
+
+ tag = (struct boundary_tag *) ((unsigned int) ptr
+ - sizeof(struct boundary_tag));
+
+ if (tag->magic != LIBALLOC_MAGIC) {
+ liballoc_unlock(); // release the lock
+ return;
+ }
+
+#ifdef DEBUG
+ l_inuse -= tag->size;
+ printf("free: %x, %i, %i\n",
+ ptr,
+ (int) l_inuse / 1024,
+ (int) l_allocated / 1024);
+#endif
+
+ // MELT LEFT...
+ while ((tag->split_left != NULL) && (tag->split_left->index >= 0)) {
+#ifdef DEBUG
+ printf("Melting tag left into available memory. Left was %i, becomes %i "
+ "(%i)\n",
+ tag->split_left->real_size,
+ tag->split_left->real_size + tag->real_size,
+ tag->split_left->real_size);
+#endif
+ tag = melt_left(tag);
+ remove_tag(tag);
+ }
+
+ // MELT RIGHT...
+ while ((tag->split_right != NULL) && (tag->split_right->index >= 0)) {
+#ifdef DEBUG
+ printf("Melting tag right into available memory. This was was %i, becomes "
+ "%i (%i)\n",
+ tag->real_size,
+ tag->split_right->real_size + tag->real_size,
+ tag->split_right->real_size);
+#endif
+ tag = absorb_right(tag);
+ }
+
+ // Where is it going back to?
+ index = getexp(tag->real_size - sizeof(struct boundary_tag));
+ if (index < MINEXP)
+ index = MINEXP;
+
+ // A whole, empty block?
+ if ((tag->split_left == NULL) && (tag->split_right == NULL)) {
+
+ if (l_completePages[index] == MAXCOMPLETE) {
+ // Too many standing by to keep. Free this one.
+ unsigned int pages = tag->real_size / l_pageSize;
+
+ if ((tag->real_size % l_pageSize) != 0)
+ pages += 1;
+ if (pages < l_pageCount)
+ pages = l_pageCount;
+
+ liballoc_free(tag, pages);
+
+#ifdef DEBUG
+ l_allocated -= pages * l_pageSize;
+ printf("Resource freeing %x of %i pages\n", tag, pages);
+ dump_array();
+#endif
+
+ liballoc_unlock();
+ return;
+ }
+
+ l_completePages[index] += 1; // Increase the count of complete pages.
+ }
+
+ // ..........
+
+ insert_tag(tag, index);
+#ifdef DEBUG
+ printf("Returning tag with %i bytes (requested %i bytes), which has "
+ "exponent: %i\n",
+ tag->real_size,
+ tag->size,
+ index);
+ dump_array();
+#endif
+
+ liballoc_unlock();
+}
+
+void *
+kcalloc(size_t nobj, size_t size)
+{
+ int real_size;
+ void *p;
+
+ real_size = nobj * size;
+
+ p = kmalloc(real_size);
+
+ liballoc_memset(p, 0, real_size);
+
+ return p;
+}
+
+void *
+krealloc(void *p, size_t size)
+{
+ void *ptr;
+ struct boundary_tag *tag;
+ size_t real_size;
+
+ if (size == 0) {
+ kfree(p);
+ return NULL;
+ }
+ if (p == NULL)
+ return kmalloc(size);
+
+ liballoc_lock(); // lockit
+ tag = (struct boundary_tag *) ((unsigned int) p
+ - sizeof(struct boundary_tag));
+ real_size = tag->size;
+ liballoc_unlock();
+
+ if (real_size > size)
+ real_size = size;
+
+ ptr = kmalloc(size);
+ liballoc_memcpy(ptr, p, real_size);
+ kfree(p);
+
+ return ptr;
+}
generated by cgit v1.2.3 (git 2.25.1) at 2025-10-22 12:01:06 +0000