From 12302df8b3f59de46f9f20ecae57ccf874d0c867 Mon Sep 17 00:00:00 2001 From: Aqua-sama Date: Sat, 20 Mar 2021 16:24:14 +0200 Subject: Add allocator --- libk/stdlib/memory.cc | 5 --- src/allocator.cc | 90 +++++++++++++++++++++++++++++++++++++++++++++++++ src/allocator.h | 39 +++++++++++++++++++++ src/kernel.cc | 21 ++++++++++-- src/kernel/multiboot.cc | 10 ++++++ src/makefile | 3 +- 6 files changed, 159 insertions(+), 9 deletions(-) create mode 100644 src/allocator.cc create mode 100644 src/allocator.h create mode 100644 src/kernel/multiboot.cc diff --git a/libk/stdlib/memory.cc b/libk/stdlib/memory.cc index c197519..b5c8f6d 100644 --- a/libk/stdlib/memory.cc +++ b/libk/stdlib/memory.cc @@ -1,10 +1,5 @@ #include -void operator delete(void*) { - printk("Calling delete\n"); - abort(); -} - extern "C" void __cxa_pure_virtual() { printk("__cxa_pure_virtual\n"); abort(); diff --git a/src/allocator.cc b/src/allocator.cc new file mode 100644 index 0000000..77736cc --- /dev/null +++ b/src/allocator.cc @@ -0,0 +1,90 @@ +#include "allocator.h" + +static MemoryAllocator* mem_alloc = nullptr; + +MemoryAllocator::MemoryAllocator(uint32_t start, size_t size) { + if (size < sizeof(MemoryChunk)) { + begin = nullptr; + return; + } + begin = new (reinterpret_cast(start)) MemoryChunk{.size = static_cast(size - sizeof(MemoryChunk))}; + if (mem_alloc == nullptr) mem_alloc = this; +} + +void* MemoryAllocator::malloc(size_t size) { + // TODO spinlock + // TODO memset 0 over allocated memory + MemoryChunk* result = nullptr; + + // find the first chunk that is at least size and not allocated + for (auto* iter = begin; iter != nullptr; iter = iter->next) { + if (iter->size >= size && !iter->allocated) { + result = iter; + + // split chunk if there is at least one byte left over + if (result->size >= size + sizeof(MemoryChunk) + 1) { + auto* _new = new (result + sizeof(MemoryChunk) + size) MemoryChunk{ + .prev = result, .next = result->next, .size = static_cast(result->size - sizeof(MemoryChunk))}; + result->next = _new; + } + + break; + } + } + + return result + sizeof(MemoryChunk); +} +void MemoryAllocator::free(void* ptr) { + auto* chunk = reinterpret_cast(reinterpret_cast(ptr) - sizeof(MemoryChunk)); + chunk->allocated = false; + + // merge in next chunk + if (chunk->next != nullptr && !chunk->next->allocated) { + chunk->size += chunk->next->size + sizeof(MemoryChunk); + chunk->next = chunk->next->next; + if (chunk->next != nullptr) chunk->next->prev = chunk; + } + + // merge into previous chunk + if (chunk->prev != nullptr && !chunk->prev->allocated) { + chunk->prev->size += chunk->size + sizeof(MemoryChunk); + chunk->prev->next = chunk->next; + if (chunk->next != nullptr) chunk->next->prev = chunk->prev; + } +}; + +size_t MemoryAllocator::free_space() const { + size_t r = 0; + for (auto* iter = begin; iter != nullptr; iter = iter->next) + if (!iter->allocated) r += iter->size; + return r; +} +size_t MemoryAllocator::used_space() const { + size_t r = 0; + for (auto* iter = begin; iter != nullptr; iter = iter->next) + if (iter->allocated) r += iter->size; + return r; +} + +void* operator new(unsigned sz, const std::nothrow_t&) noexcept { + if (mem_alloc == nullptr) return nullptr; + return mem_alloc->malloc(sz); +} +void* operator new[](unsigned sz, const std::nothrow_t&) noexcept { + if (mem_alloc == nullptr) return nullptr; + return mem_alloc->malloc(sz); +} + +void operator delete(void* ptr) { + if (mem_alloc != nullptr) mem_alloc->free(ptr); +} +void operator delete[](void* ptr) { + if (mem_alloc != nullptr) mem_alloc->free(ptr); +} + +void* operator new(unsigned /* size_bytes */, void* ptr) { + return ptr; +} +void* operator new[](unsigned /* size_bytes */, void* ptr) { + return ptr; +} diff --git a/src/allocator.h b/src/allocator.h new file mode 100644 index 0000000..8a12be8 --- /dev/null +++ b/src/allocator.h @@ -0,0 +1,39 @@ +#pragma once + +#include + +class MemoryAllocator { +public: + MemoryAllocator(uint32_t start, size_t size); + + void* malloc(size_t size); + void free(void* ptr); + + size_t free_space() const; + size_t used_space() const; + +private: + struct MemoryChunk { + MemoryChunk* prev = nullptr; + MemoryChunk* next = nullptr; + bool allocated = false; + size_t size = 0; + }; + MemoryChunk* begin; +}; + +namespace std { +struct nothrow_t { + explicit nothrow_t() = default; +}; +}; // namespace std + +void* operator new(unsigned, const std::nothrow_t&) noexcept; +void* operator new[](unsigned, const std::nothrow_t&) noexcept; + +void operator delete(void* ptr); +void operator delete[](void* ptr); + +// placement new +void* operator new(unsigned, void*); +void* operator new[](unsigned, void*); diff --git a/src/kernel.cc b/src/kernel.cc index 3110419..05e0daf 100644 --- a/src/kernel.cc +++ b/src/kernel.cc @@ -10,6 +10,7 @@ #include #include +#include "allocator.h" #include "cga.h" #include "cpu/cpu.h" #include "gdt.h" @@ -23,12 +24,15 @@ vmm kvmm; #include "hardware.h" +char buffer[4096]; + +uint32_t check_multiboot(uint32_t, uint32_t); + extern "C" { void dump_multiboot(uint32_t mb_magic, uint32_t mb_addr); void dump_gdt(); -void kernel_main([[maybe_unused]] uint32_t mb_magic, [[maybe_unused]] uint32_t mb_addr) { - +void kernel_main(uint32_t mb_magic, uint32_t mb_addr) { #ifdef HAS_SERIAL0 if constexpr (serial0_console) if (serial0.self_check()) Console::set(&serial0); @@ -52,8 +56,16 @@ void kernel_main([[maybe_unused]] uint32_t mb_magic, [[maybe_unused]] uint32_t m // dump_gdt(); // - if (const auto mb_addr_r = kvmm.map(mb_addr, 0xc03fe000)) { + { + const auto mb_addr_r = kvmm.map(mb_addr, 0xc03fe000); + runtime_assert(mb_addr_r, "Failed to map mb_addr"); + mb_addr = mb_addr_r.value(); + const auto mb_size = check_multiboot(mb_magic, mb_addr); + runtime_assert((mb_size != 0), "Invalid multiboot header"); + + printk("Multiboot2 header at ", uhex{mb_addr}, " size: ", mb_size, '\n'); + // dump_multiboot(mb_magic, mb_addr); } @@ -62,6 +74,9 @@ void kernel_main([[maybe_unused]] uint32_t mb_magic, [[maybe_unused]] uint32_t m // Scheduler s{gdt.descriptor(GDT::kcode)}; Keyboard kb; + MemoryAllocator ma(reinterpret_cast(buffer), sizeof(buffer)); + printk("memory free: ", ma.free_space(), '\n'); + idt.enable(); while (true) asm volatile("hlt"); diff --git a/src/kernel/multiboot.cc b/src/kernel/multiboot.cc new file mode 100644 index 0000000..024916e --- /dev/null +++ b/src/kernel/multiboot.cc @@ -0,0 +1,10 @@ +#include +#include + +uint32_t check_multiboot(uint32_t mb_magic, uint32_t mb_addr) { + if (mb_magic != MULTIBOOT2_BOOTLOADER_MAGIC) return 0; + if (mb_addr & 7) return 0; + + const uint32_t size = *reinterpret_cast(mb_addr); + return size; +} diff --git a/src/makefile b/src/makefile index 68ec6d6..6e8545d 100644 --- a/src/makefile +++ b/src/makefile @@ -2,13 +2,14 @@ AS_OBJ += src/boot.o \ src/idt/stubs.o CXX_OBJ += src/kernel.o \ - src/kernel/dump_gdt.o src/kernel/dump_multiboot.o \ + src/kernel/dump_gdt.o src/kernel/dump_multiboot.o src/kernel/multiboot.o \ src/cpu/cpu.o \ src/gdt.o \ src/gdt/segmentdescriptor.o \ src/idt.o \ src/idt/exception.o src/idt/interruptgate.o src/idt/interrupthandler.o \ src/vmm.o \ + src/allocator.o \ src/scheduler.o src/scheduler/task.o src/cpu/irq.h: $(OBJ_DIR)/src/idt/stubs.o -- cgit v1.2.1