From bf7462532c7bc6224f3bdd2e52a86e5fe04c2bfe Mon Sep 17 00:00:00 2001 From: Matthias Kruk Date: Mon, 16 Sep 2019 17:17:12 +0900 Subject: [PATCH] Add simple kernel heap implementation --- config.h | 1 + include/corax/heap.h | 9 +++ kernel/arch/Makefile | 3 +- kernel/arch/heap.c | 139 +++++++++++++++++++++++++++++++++++++++++++ kernel/arch/heap.h | 27 +++++++++ kernel/arch/paging.c | 80 ++++++++++++++++++++++++- kernel/arch/paging.h | 26 ++++++++ 7 files changed, 281 insertions(+), 4 deletions(-) create mode 100644 include/corax/heap.h create mode 100644 kernel/arch/heap.c create mode 100644 kernel/arch/heap.h diff --git a/config.h b/config.h index 03f4142..e33e6a8 100644 --- a/config.h +++ b/config.h @@ -21,6 +21,7 @@ #define FEATURE(x) (defined(CONFIG_##x) && CONFIG_##x == 1) +#define CONFIG_KERNEL_HEAP_SIZE 4096 #define CONFIG_KERNEL_STACK_SIZE 4096 #define CONFIG_USER_STACK_SIZE 4096 diff --git a/include/corax/heap.h b/include/corax/heap.h new file mode 100644 index 0000000..098ec57 --- /dev/null +++ b/include/corax/heap.h @@ -0,0 +1,9 @@ +#ifndef __CORAX_HEAP_H +#define __CORAX_HEAP_H + +#include + +void* kmalloc(u32_t); +void kfree(void*); + +#endif /* __CORAX_HEAP_H */ diff --git a/kernel/arch/Makefile b/kernel/arch/Makefile index 67a8275..e7e4cce 100644 --- a/kernel/arch/Makefile +++ b/kernel/arch/Makefile @@ -1,4 +1,5 @@ -OBJECTS = boot.o debug.o init.o cpu.o cpu32.o entry.o interrupt.o paging.o apic.o i8259.o task.o +OBJECTS = boot.o debug.o init.o cpu.o cpu32.o entry.o interrupt.o paging.o apic.o i8259.o task.o \ + heap.o OUTPUT = arch.o LDFLAGS += -r INCLUDES = -I../../include -I../include -I../.. diff --git a/kernel/arch/heap.c b/kernel/arch/heap.c new file mode 100644 index 0000000..c6819d0 --- /dev/null +++ b/kernel/arch/heap.c @@ -0,0 +1,139 @@ +/* + * This file is part of the Corax operating system. + * Copyright (C) 2019 Matthias Kruk + * + * Corax 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. + * + * Corax 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 Corax. If not, see . + */ + +#include +#include "paging.h" +#include "heap.h" + +#define FLAG_USED (1 << 0) + +struct heap_node { + struct heap_node *hn_next; + u32_t hn_size; + u32_t hn_flags; +}; + +static struct { + struct pagedir *h_pgdir; + void *h_base; + u32_t h_size; + u32_t h_free; +} _kheap; + +void heap_init(void *base, u32_t size) +{ + struct heap_node *node; + + _kheap.h_base = base; + _kheap.h_size = size; + _kheap.h_free = size - sizeof(*node); + + node = (struct heap_node*)base; + + node->hn_next = NULL; + node->hn_size = size - sizeof(*node); + node->hn_flags = 0; + + return; +} + +int heap_grow(u32_t sreq) +{ + int ret_val; + + ret_val = -1; +/* sreq = ALIGN(sreq, PAGE_SIZE); */ + + return(ret_val); +} + +void* kmalloc(u32_t size) +{ + struct heap_node *cur; + void *ret_val; + + ret_val = NULL; + + if(_kheap.h_free < size) { + /* add more pages to the pagedir */ + } + + for(cur = (struct heap_node*)_kheap.h_base; + cur; + cur = cur->hn_next) { + if(cur->hn_flags & FLAG_USED) { + continue; + } + + if(cur->hn_size < size) { + continue; + } + + /* make ret_val point to the available memory */ + ret_val = (void*)(cur + 1); + + cur->hn_flags |= FLAG_USED; + + /* split the heap node if it makes sense */ + if(cur->hn_size > (size + sizeof(struct heap_node))) { + struct heap_node *new; + + new = (struct heap_node*)(ret_val + size); + + new->hn_size = cur->hn_size - size - (2 * sizeof(*new)); + new->hn_next = cur->hn_next; + new->hn_flags = 0; + + cur->hn_size = size; + cur->hn_next = new; + + _kheap.h_free -= sizeof(*new); + } + + _kheap.h_free -= size; + + break; + } + + return(ret_val); +} + +void kfree(void *ptr) +{ + struct heap_node *cur; + + for(cur = (struct heap_node*)_kheap.h_base; + cur; + cur = cur->hn_next) { + void *base; + + base = (void*)(cur + 1); + + if(base < ptr && (base + cur->hn_size) > ptr) { + if(!(cur->hn_flags & FLAG_USED)) { + dbg_printf("Double free detected: %p\n", ptr); + } else { + cur->hn_flags &= ~FLAG_USED; + _kheap.h_free += cur->hn_size; + } + break; + } + } + + return; +} diff --git a/kernel/arch/heap.h b/kernel/arch/heap.h new file mode 100644 index 0000000..23339b2 --- /dev/null +++ b/kernel/arch/heap.h @@ -0,0 +1,27 @@ +/* + * This file is part of the Corax operating system. + * Copyright (C) 2019 Matthias Kruk + * + * Corax 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. + * + * Corax 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 Corax. If not, see . + */ + +#ifndef HEAP_H +#define HEAP_H + +#include +#include "paging.h" + +void heap_init(void*, u32_t); + +#endif /* HEAP_H */ diff --git a/kernel/arch/paging.c b/kernel/arch/paging.c index 3362510..3f191a6 100644 --- a/kernel/arch/paging.c +++ b/kernel/arch/paging.c @@ -21,9 +21,11 @@ #include #include "cpu.h" #include "paging.h" +#include "heap.h" #define _frame_set(addr) _frame_map[(addr) >> 17] |= 1 << (((addr) >> 12) & 0x1f) #define _frame_clear(addr) _frame_map[(addr) >> 17] &= ~(1 << (((addr) >> 12) & 0x1f)) +#define _frame_get(addr) (_frame_map[(addr) >> 17] & (1 << (((addr) >> 12) & 0x1f))) extern u32_t _mem_start; @@ -31,8 +33,7 @@ static u32_t _kernel_cr3 = 0; static u32_t _pg_flags = 0; static u32_t *_frame_map; static u32_t _nframes; - -static void* _phys_alloc(u32_t, u32_t); +static struct pagedir *_kernel_pgdir; static const char *_str_pg_mode[] = { "legacy IA-32 mode", @@ -41,6 +42,9 @@ static const char *_str_pg_mode[] = { "Intel64 mode" }; +#define ALIGNED(_v, _a) (!((_v) & (((_a) - 1)))) +#define ALIGN(_v, _a) (ALIGNED((_v), (_a)) ? (_v) : (((_v) & ~((_a) - 1)) + (_a))) + static void* _phys_alloc(u32_t size, u32_t align) { extern u32_t _mem_start; @@ -63,8 +67,55 @@ static void* _phys_alloc(u32_t size, u32_t align) return(addr); } +static void* _frame_alloc_start(void) +{ + u32_t frm; + + for(frm = 0; frm < _nframes; frm++) { + /* check if there's an unused frame in this dword */ + if(~_frame_map[frm]) { + u32_t addr; + + /* find the 0 bit in _frame_map[frm] */ + for(addr = frm << 17; + addr < ((frm + 1) << 17); + addr += PAGE_SIZE) { + if(!_frame_get(addr)) { + _frame_set(addr); + return((void*)addr); + } + } + } + } + + return(NULL); +} + +static void* _frame_alloc_end(void) +{ + u32_t frm; + + for(frm = _nframes - 1; frm >= 0; frm--) { + if(~_frame_map[frm]) { + u32_t addr; + + for(addr = frm << 17; + addr > ((frm - 1) << 17); + addr -= PAGE_SIZE) { + if(!_frame_get(addr)) { + _frame_set(addr); + return((void*)addr); + } + } + } + } + + return(NULL); +} + void* pg_init(struct multiboot_info *info) { + extern struct cpu _cpu[CONFIG_SMP_CPUS]; struct memory_map *mmap; u64_t mem_size; u32_t cr3; @@ -138,10 +189,12 @@ void* pg_init(struct multiboot_info *info) mmap = (struct memory_map*)((void*)mmap + mmap->size + sizeof(mmap->size))) { u32_t attrs; u64_t addr; + #if 1 dbg_printf("Region: 0x%016llx - 0x%016llx [%u]\n", mmap->addr, mmap->addr + mmap->len, mmap->type); #endif + /* FIXME: Memory in the region 0x100000:&_mem_start should NOT be writable! */ attrs = PAGE_ATTR_SIZE | PAGE_ATTR_WRITABLE | PAGE_ATTR_PRESENT; /* disable caching on reserved memory areas */ @@ -200,12 +253,33 @@ void* pg_init(struct multiboot_info *info) } } + _kernel_pgdir = _phys_alloc(sizeof(*_kernel_pgdir), ARCH_ALIGN); + + _kernel_pgdir->pd_base = (void*)cr3; + _kernel_pgdir->pd_regions[REGION_TEXT].reg_base = (void*)0x100000; + _kernel_pgdir->pd_regions[REGION_TEXT].reg_size = (u32_t)&_mem_start - 0x100000; + _kernel_pgdir->pd_regions[REGION_TEXT].reg_pgsize = PAGE_SIZE; + _kernel_pgdir->pd_regions[REGION_TEXT].reg_attrs = PAGE_ATTR_PRESENT | PAGE_ATTR_USER; + + _kernel_pgdir->pd_regions[REGION_HEAP].reg_base = (void*)ALIGN((u32_t)&_mem_start, PAGE_SIZE); + _kernel_pgdir->pd_regions[REGION_HEAP].reg_size = ALIGN(_mem_start + CONFIG_KERNEL_HEAP_SIZE, PAGE_SIZE); + _kernel_pgdir->pd_regions[REGION_HEAP].reg_pgsize = PAGE_SIZE; + _kernel_pgdir->pd_regions[REGION_HEAP].reg_attrs = PAGE_ATTR_PRESENT | PAGE_ATTR_WRITABLE; + + _kernel_pgdir->pd_regions[REGION_STACK].reg_base = &(_cpu[CPU_ID].cpu_stack0); + _kernel_pgdir->pd_regions[REGION_STACK].reg_size = STACK0_SIZE; + _kernel_pgdir->pd_regions[REGION_STACK].reg_pgsize = PAGE_SIZE; + _kernel_pgdir->pd_regions[REGION_STACK].reg_attrs = PAGE_ATTR_PRESENT | PAGE_ATTR_WRITABLE; + + heap_init(_kernel_pgdir->pd_regions[REGION_HEAP].reg_base, + _kernel_pgdir->pd_regions[REGION_HEAP].reg_size); + /* mark all page frames from 0x0 to the end of the last kernel page dir/table as used */ for(i = 0; i < _mem_start; i += PAGE_SIZE) { _frame_set(i); } - _kernel_cr3 = (u32_t)cr3; + _kernel_cr3 = cr3; dbg_printf("Enabling %s paging\n", _str_pg_mode[_pg_flags & PG_MODE_MASK]); diff --git a/kernel/arch/paging.h b/kernel/arch/paging.h index a44080e..0d7b5b6 100644 --- a/kernel/arch/paging.h +++ b/kernel/arch/paging.h @@ -22,6 +22,27 @@ #include #include "defs.h" +#define REGION_TEXT 0 +#define REGION_HEAP 1 +#define REGION_STACK 2 + +struct region { + struct region *next; + + void *reg_base; + u32_t reg_flags; + u32_t reg_size; + u32_t reg_pgsize; + u32_t reg_attrs; +}; + +struct pagedir { + void *pd_base; + u32_t pd_flags; + + struct region pd_regions[3]; +}; + typedef struct pdpt pdpt_t; struct pdpt { @@ -41,6 +62,7 @@ struct pae_page_table { #define PDPT_ALIGN 32 #define PAGE_ALIGN 0x1000 +#define ARCH_ALIGN sizeof(void*) #define PAGE_SIZE 0x1000 #define PAGE_SIZE_BIG 0x200000 @@ -58,4 +80,8 @@ struct pae_page_table { #define PAGE_ATTR_GLOBAL (1 << 8) #define PAGE_ATTR_NO_EXEC (1 << 63) +int pagedir_init(struct pagedir*); +void* pagedir_map_pages(struct pagedir*); +int pagedir_free(struct pagedir*); + #endif /* __PAGING_H */ -- 2.47.3