summaryrefslogtreecommitdiff
path: root/kernel/src/memory
diff options
context:
space:
mode:
Diffstat (limited to 'kernel/src/memory')
-rw-r--r--kernel/src/memory/allocator.c314
-rw-r--r--kernel/src/memory/memory.c202
-rw-r--r--kernel/src/memory/memory.h22
3 files changed, 0 insertions, 538 deletions
diff --git a/kernel/src/memory/allocator.c b/kernel/src/memory/allocator.c
deleted file mode 100644
index 6217ad4..0000000
--- a/kernel/src/memory/allocator.c
+++ /dev/null
@@ -1,314 +0,0 @@
-#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;
-}
diff --git a/kernel/src/memory/memory.c b/kernel/src/memory/memory.c
deleted file mode 100644
index 30da0fc..0000000
--- a/kernel/src/memory/memory.c
+++ /dev/null
@@ -1,202 +0,0 @@
-#include <stdint.h>
-#include <string.h>
-#include <sys.h>
-#include <panic.h>
-
-#include "memory.h"
-#include "boot/tag.h"
-#include "print.h"
-
-struct MemoryArea {
- uint32_t len;
- struct MemoryArea *prev;
- struct MemoryArea *next;
-};
-
-typedef unsigned char page[4096];
-
-extern unsigned char kernel_start, kernel_end;
-static uintptr_t kernel_start_addr, kernel_end_addr;
-static uint32_t *bitmap;
-static uint32_t total_memory;
-static uint32_t free_memory;
-static uint32_t page_count;
-static uint32_t page_free_start;
-static struct MemoryArea *page_start;
-
-int memory_lock(void) {
- int_disable();
- return 0;
-}
-
-int memory_unlock(void) {
- int_enable();
- return 0;
-}
-
-static int n_pages(const struct MemoryArea *m) {
- return (m->len - sizeof(*m)) / sizeof(page);
-}
-
-static void *page_at(int i) {
- int cur_page = 0;
- for (struct MemoryArea *m = page_start; m != NULL; m = m->next) {
- int pages = n_pages(m);
- if (i - cur_page < pages) {
- page *page_array = (page *) (m + 1);
- return page_array[i - cur_page];
- }
- cur_page += pages;
- }
- return NULL;
-}
-
-static int page_idx(page p) {
- uintptr_t addr = (uintptr_t) p;
- int cur_page = 0;
- for (struct MemoryArea *m = page_start; m != NULL; m = m->next) {
- if ((uintptr_t) m + m->len > addr) {
- return cur_page + (addr - (uintptr_t) m) / sizeof(page);
- }
- cur_page += n_pages(m);
- }
- return -1;
-}
-
-static inline bool bitmap_get(int i) {
- return (bitmap[i / 32] >> i % 32) & 1;
-}
-
-static inline void bitmap_set(int i, bool v) {
- int idx = i / 32;
- bitmap[idx] &= ~(1 << i % 32);
- bitmap[idx] |= (v << i % 32);
-}
-
-void *memory_alloc_page(int pages) {
- if (pages < 1) return NULL;
-
- int n_contiguous = 0;
- int free_region_start = 0;
- bool first = true;
- for (uint32_t i = page_free_start; i < page_count; i++) {
- bool free = !bitmap_get(i);
-
- if (first) {
- first = false;
- page_free_start = i;
- }
-
- if (free) {
- if (n_contiguous == 0) free_region_start = i;
- n_contiguous++;
- if (n_contiguous == pages) {
- for (int j = 0; j < pages; j++)
- bitmap_set(free_region_start + j, true);
- return page_at(free_region_start);
- }
- } else n_contiguous = 0;
- }
-
- return NULL;
-}
-
-int memory_free_page(void *ptr, int pages) {
- int idx = page_idx(ptr);
- if (idx == -1) return 1;
-
- if ((unsigned) idx < page_free_start) page_free_start = idx;
-
- for (int i = 0; i < pages; i++)
- bitmap_set(idx + pages, false);
- return 0;
-}
-
-void memory_init(void) {
-
- debugk("Loading memory pages");
-
- memory_lock();
-
- bitmap = NULL;
- total_memory = 0;
- free_memory = 0;
- page_count = 0;
- page_free_start = 0;
- page_start = NULL;
-
- kernel_start_addr = (uintptr_t) &kernel_start;
- kernel_end_addr = (uintptr_t) &kernel_end;
-
- struct BootTag *tag;
- if (!get_boot_tag(iD_MEMORYMAP, &tag)) {
- panic("No multiboot memory map found");
- }
-
- uintptr_t end = (uintptr_t) tag->data.memory_map;
- end += tag->size;
-
- struct MemoryArea *prev = NULL;
- struct MemorySegment *segment = &tag->data.memory_map->entries[0];
- for(; (uintptr_t) segment < end; segment++) {
-
- if (segment->type != 1) continue;
- if (segment->addr >= UINT32_MAX) continue;
- if (segment->addr < kernel_start_addr) continue;
-
- uint32_t length;
- if (segment->addr + segment->len > UINT32_MAX) {
- length = UINT32_MAX - segment->addr;
- } else {
- length = segment->len;
- }
-
- uintptr_t addr;
- if (segment->addr < kernel_end_addr) {
- addr = kernel_end_addr;
- length -= addr - segment->addr;
- } else {
- addr = segment->addr;
- }
-
- struct MemoryArea *current = (struct MemoryArea *) addr;
- current->prev = prev;
- current->next = NULL;
- current->len = length;
-
- if (prev != NULL) {
- prev->next = current;
- } else {
- page_start = current;
- }
-
- page_count += n_pages(current);
- total_memory += length;
-
- prev = current;
-
- }
-
- int bitmap_pages = page_count / 32 / sizeof(page) + 1;
- bitmap = (uint32_t *) page_at(page_count - bitmap_pages);
- page_count -= bitmap_pages;
- memset(bitmap, 0, bitmap_pages * sizeof(page));
- free_memory = page_count * sizeof(page);
-
- memory_unlock();
-
- succek("Memory loaded. %k total %k free", total_memory, free_memory);
-
-}
-
-uint32_t memory_total(void) {
- return total_memory;
-}
-
-uint32_t memory_free(void) {
- return free_memory;
-}
-
-uint32_t memory_used(void) {
- return total_memory - free_memory;
-}
diff --git a/kernel/src/memory/memory.h b/kernel/src/memory/memory.h
deleted file mode 100644
index 5d99025..0000000
--- a/kernel/src/memory/memory.h
+++ /dev/null
@@ -1,22 +0,0 @@
-#pragma once
-
-#include <stdint.h>
-
-struct MemorySegment {
- uint64_t addr;
- uint64_t len;
- uint32_t type;
- uint32_t reserved;
-} __attribute__((packed));
-
-struct MemoryMap {
- uint32_t entry_size;
- uint32_t entry_version;
- struct MemorySegment entries[];
-} __attribute__((packed));
-
-uint32_t memory_total(void);
-uint32_t memory_free(void);
-uint32_t memory_used(void);
-
-void memory_init(void);
generated by cgit v1.2.3-freya (git 2.51.0) at 2025-09-22 21:54:50 +0000