From e79687494bc3b01f42a79b0c355533e6e39e9a9d Mon Sep 17 00:00:00 2001 From: Carlos Maiolino Date: Sun, 14 Sep 2025 12:56:39 +0200 Subject: Add a simple heap implementation Add a simple API implementing a heap memory area. This specifies 2 main data structures: struct heap - Defines a heap: Holds a table with all entries in the specific heap and the initial heap memory address struct heap_table - Describes the usage state of every PAGE within the specific heap. Signed-off-by: Carlos Maiolino --- src/include/mm/heap.h | 50 +++++++++++++ src/include/toxic/config.h | 11 +++ src/mm/heap.c | 176 +++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 237 insertions(+) create mode 100644 src/include/mm/heap.h create mode 100644 src/include/toxic/config.h create mode 100644 src/mm/heap.c diff --git a/src/include/mm/heap.h b/src/include/mm/heap.h new file mode 100644 index 0000000..4c55ae4 --- /dev/null +++ b/src/include/mm/heap.h @@ -0,0 +1,50 @@ +#ifndef HEAP_H +#define HEAP_H +#include +#include + +/* + * Heap table consists of an array of 1-byte long entries describing + * each PAGE_SIZE region inside the heap. + */ + +/* + * Each entry in the heap table is 1byte long, where: + * + * bit 7: Set when next page in this heap belongs to the same allocation + * bit 6: Set when the current page in the first in this allocation map + * bit 5-1: Reserved + * bit 0: Used flag + */ +#define HEAP_ENTRY_INUSE 0x1 +#define HEAP_ENTRY_FREE 0x0 + +#define HEAP_ENTRY_HAS_NEXT 0x80 /* 0b1000000 */ +#define HEAP_ENTRY_IS_FIRST 0x40 /* 0b01000000 */ + + +#define HEAP_ENTRY_USED_MASK ((unsigned char) 0x01) +/* + * Define a macro for entry size so in future + * I can turn this into a proper structure + */ +#define HEAP_ENTRY_SIZE (sizeof(unsigned char)) + +struct heap_table { + unsigned char *entries; + size_t count; +}; + +/* Heap descriptor */ +struct heap { + struct heap_table *table; + void *start_addr; +}; + +int heap_create(struct heap *heap, void *start, void *end, + struct heap_table *tbl); + +void * heap_malloc(struct heap *heap, size_t size); +void heap_free(struct heap *heap, void *ptr); + +#endif /* HEAP_H */ diff --git a/src/include/toxic/config.h b/src/include/toxic/config.h new file mode 100644 index 0000000..19d05a9 --- /dev/null +++ b/src/include/toxic/config.h @@ -0,0 +1,11 @@ +#ifndef CONFIG_H +#define CONFIG_H + +#define TOTAL_INTERRUPTS 512 +#define KERNEL_CODE_SELECTOR 0x08 +#define KERNEL_DATA_SELECTOR 0x010 + +/* Kernel heap settings */ +#define PAGE_SIZE (4096) + +#endif /* CONFIG_H */ diff --git a/src/mm/heap.c b/src/mm/heap.c new file mode 100644 index 0000000..6254bbc --- /dev/null +++ b/src/mm/heap.c @@ -0,0 +1,176 @@ +#include +#include +#include +#include +#include + +static int +heap_validate_table( + struct heap_table *tbl, + void *start, + void *end) +{ + int ret = 0; + + size_t tbl_size = (size_t)(end - start); + size_t tbl_pages = tbl_size / PAGE_SIZE; + + if (tbl->count != tbl_pages) + ret = -EINVAL; + + return ret; +} + +static int +heap_validate_alignment(void *ptr) +{ + return ((uint32_t)ptr % PAGE_SIZE) == 0; +} + +int +heap_create( + struct heap *heap, + void *start, + void *end, + struct heap_table *tbl) +{ + int ret = -EINVAL; + size_t tbl_size = HEAP_ENTRY_SIZE * tbl->count; + + if (!heap_validate_alignment(start) || + !heap_validate_alignment(end)) + goto out; + + memset(heap, 0, sizeof(struct heap)); + heap->start_addr = start; + heap->table = tbl; + + ret = heap_validate_table(tbl, start, end); + + if (ret) + goto out; + + memset(tbl->entries, 0, tbl_size); + +out: + return ret; +} + +static int +heap_entry_is_used(unsigned char entry) +{ + return (entry & HEAP_ENTRY_USED_MASK) == HEAP_ENTRY_INUSE; +} + +int +heap_get_start_page( + struct heap *heap, + uint32_t pages) +{ + struct heap_table *tbl = heap->table; + int start_page = -1; + int cur_page = 0; + size_t i; + + for (i = 0; i < tbl->count; i++) { + if (heap_entry_is_used(tbl->entries[i])) { + start_page = -1; + cur_page = 0; + continue; + } + + if (start_page < 0) + start_page = i; + + /* Did we find enough blocks? */ + if (++cur_page == pages) + break; + } + + if (start_page < 0) + return -ENOMEM; + + return start_page; +} + +void * +heap_page_to_addr(struct heap *heap, uint32_t page) +{ + return heap->start_addr + (page * PAGE_SIZE); +} + +uint32_t +heap_addr_to_page(struct heap *heap, void *ptr) +{ + return (uint32_t)(ptr - heap->start_addr) / PAGE_SIZE; +} + +void +heap_mark_pages_used(struct heap *heap, uint32_t start_page, uint32_t page_count) +{ + int i; + uint32_t end = start_page + page_count - 1; + unsigned char cur = HEAP_ENTRY_IS_FIRST | HEAP_ENTRY_INUSE; + + if (page_count > 1) + cur |= HEAP_ENTRY_HAS_NEXT; + + for (i = start_page; i <= end; i++) { + heap->table->entries[i] = cur; + + cur = HEAP_ENTRY_INUSE; + if (i != (end - 1)) + cur |= HEAP_ENTRY_HAS_NEXT; + } +} + +void +heap_mark_pages_free(struct heap *heap, uint32_t start_page) +{ + int i; + struct heap_table *tbl = heap->table; + + for (i = start_page; i < tbl->count; i++) { + unsigned char e = tbl->entries[i]; + + tbl->entries[i] = HEAP_ENTRY_FREE; + + if (!(e & HEAP_ENTRY_HAS_NEXT)) + break; + } + + +} + +void * +heap_malloc_pages(struct heap *heap, uint32_t pages) +{ + void *addr = 0; + + uint32_t start_page = heap_get_start_page(heap, pages); + + if (!start_page) + goto out; + + addr = heap_page_to_addr(heap, start_page); + + heap_mark_pages_used(heap, start_page, pages); + +out: + return addr; +} + +void * +heap_malloc(struct heap *heap, size_t size) +{ + size_t aligned = roundup32((uint32_t) size, PAGE_SIZE); + uint32_t pages = aligned / PAGE_SIZE; + + return heap_malloc_pages(heap, pages); +} + +void +heap_free(struct heap *heap, void *ptr) +{ + heap_mark_pages_free(heap, heap_addr_to_page(heap, ptr)); +} -- cgit v1.2.3