From 34121ea2bde459aa673afbd041e7b7e72c7f649c Mon Sep 17 00:00:00 2001 From: Amelia Coutard Date: Sun, 26 Mar 2023 03:35:30 +0200 Subject: [PATCH] Reimplemented the page allocator --- kernel/src/elf64.cpp | 1 + kernel/src/kernel.cpp | 5 ++ kernel/src/paging.cpp | 129 +++++++++++++++++------------------------- kernel/src/paging.hpp | 17 +----- 4 files changed, 61 insertions(+), 91 deletions(-) diff --git a/kernel/src/elf64.cpp b/kernel/src/elf64.cpp index 422d0ba..70d9e1a 100644 --- a/kernel/src/elf64.cpp +++ b/kernel/src/elf64.cpp @@ -39,6 +39,7 @@ os::process os::elf::load_elf(void* start, std::size_t length, const paging::PML }; // Copy kernel mappings to the new virtual address space. + memset(result.PML4T->contents, 0, 256 * sizeof(os::paging::PML4E)); memcpy(result.PML4T->contents + 256, original_PML4T.contents + 256, 256 * sizeof(os::paging::PML4E)); for (std::size_t i = 0; i < elf_header.entry_count_program_header_table; i++) { diff --git a/kernel/src/kernel.cpp b/kernel/src/kernel.cpp index 014be9a..a83504c 100644 --- a/kernel/src/kernel.cpp +++ b/kernel/src/kernel.cpp @@ -46,6 +46,7 @@ extern "C" void kmain(unsigned long magic, os::phys_ptr(PDPT_alloc.ptr.get_phys_addr())); } @@ -131,6 +132,10 @@ extern "C" void kmain(unsigned long magic, os::phys_ptr(PDPT_alloc.ptr.get_phys_addr())); } os::paging::PDPT& PDPT = *get_base_address(PML4T.contents[indices.pml4e]); if (PDPT.contents[indices.pdpe].non_page.P == 0) { PDPT.contents[indices.pdpe] = {.non_page = {.P = 1, .R_W = 1, .U_S = U_S, .PWT = 0, .PCD = 0, .base_address = 0, .NX = 0}}; const auto PDT_alloc = os::paging::page_allocator.allocate(1); + memset((void*)PDT_alloc.ptr, 0, 0x1000); set_base_address(PDPT.contents[indices.pdpe], os::phys_ptr(PDT_alloc.ptr.get_phys_addr())); } else { assert(PDPT.contents[indices.pdpe].non_page.zero == 0, @@ -34,6 +36,7 @@ std::byte* os::paging::setup_page(os::paging::PML4T& PML4T, const void* vaddr, b if (PDT.contents[indices.pde].non_page.P == 0) { PDT.contents[indices.pde] = {.non_page = {.P = 1, .R_W = 1, .U_S = U_S, .PWT = 0, .PCD = 0, .base_address = 0, .NX = 0}}; const auto PT_alloc = os::paging::page_allocator.allocate(1); + memset((void*)PT_alloc.ptr, 0, 0x1000); set_base_address(PDT.contents[indices.pde], os::phys_ptr(PT_alloc.ptr.get_phys_addr())); } else { assert(PDT.contents[indices.pde].non_page.zero == 0, @@ -44,6 +47,7 @@ std::byte* os::paging::setup_page(os::paging::PML4T& PML4T, const void* vaddr, b PT.contents[indices.pe] = {.P = 1, .R_W = R_W, .U_S = U_S, .PWT = 0, .PCD = 0, .PAT = 0, .G = (indices.pml4e < 128) ? 0ul : 1ul, .base_address = 0, .NX = 0}; const auto page_alloc = os::paging::page_allocator.allocate(1); + memset((void*)page_alloc.ptr, 0, 0x1000); set_page_base_address(PT.contents[indices.pe], os::phys_ptr(page_alloc.ptr.get_phys_addr())); invlpg(vaddr); return (std::byte*)&*page_alloc.ptr; @@ -102,97 +106,68 @@ void os::paging::load_pml4t(phys_ptr PML4T) { asm volatile("mov %0, %%cr3" :: "r" (PML4T) : "memory"); } -os::paging::page one_past_end_page_for_page_allocator; -os::paging::page_allocator_t os::paging::page_allocator(os::phys_ptr(reinterpret_cast(&one_past_end_page_for_page_allocator) - 0xFFFFFFFF80000000)); +os::paging::page_allocator_t os::paging::page_allocator{}; -os::paging::page_allocator_t::page_allocator_t(phys_ptr one_past_end): begin_(one_past_end.get_phys_addr()), end_(begin_) { - end_->prev = nullptr; - end_->next = nullptr; - end_->size = 1; -} +os::paging::page_allocator_t::page_allocator_t(): begin(nullptr) {} void os::paging::page_allocator_t::print_all() const { - if (is_empty()) { - os::print("No RAM left.\n"); - } else for (auto it = begin(); it != end(); it = it->next) { - os::print("{}->{}\n", it.get_phys_addr(), (it + it->size).get_phys_addr()); + for (auto it = begin; it != nullptr; it = it->next) { + os::print("{} -> {} ({})\n", it.get_phys_addr(), (it + it->size).get_phys_addr(), it->size); } } os::paging::page_allocator_t::block os::paging::page_allocator_t::allocate(std::uint64_t count) { - for (auto it = begin(); it != end(); it = it->next) { - if (it->size < count) { - continue; + if (begin == nullptr) { + return { .ptr = nullptr, .size = count }; + } + if (begin->size == count) { + block result = { .ptr = phys_ptr{begin.get_phys_addr()}, .size = count }; + begin = begin->next; + return result; + } + phys_ptr prec = nullptr; + for (phys_ptr it = begin; it != nullptr; it = it->next) { + if (it->size == count) { + prec->next = it->next; + return { .ptr = phys_ptr{it.get_phys_addr()}, .size = count }; } - if (count < it->size) { - split_at_offset(it, count); + if (it->size > count) { + it->size -= count; + return { .ptr = phys_ptr{it.get_phys_addr()} + it->size, .size = count }; } - erase(it); - memset((void*)it, 0, count * 0x1000); - return { - .ptr = phys_ptr(it.get_phys_addr()), - .size = count, - }; + prec = it; } return { .ptr = nullptr, .size = count }; } void os::paging::page_allocator_t::deallocate(block b) { - if (b.ptr == nullptr) { return; } - if (b.size == 0) { return; } - const phys_ptr b_it{b.ptr.get_phys_addr()}; - auto it = begin(); - while (it != end() && it < b_it) { it = it->next; } - try_merge_next(try_merge_prev(insert(it, b))); -} - -bool os::paging::page_allocator_t::is_empty() const { return begin() == end(); } -os::phys_ptr os::paging::page_allocator_t::begin() { return begin_; } -os::phys_ptr os::paging::page_allocator_t::end() { return end_; } -os::phys_ptr os::paging::page_allocator_t::begin() const { return begin_; } -os::phys_ptr os::paging::page_allocator_t::end() const { return end_; } - -os::phys_ptr os::paging::page_allocator_t::insert(phys_ptr it, block b) { - const phys_ptr b_it{b.ptr.get_phys_addr()}; - if (it->prev == nullptr) { - begin_ = b_it; - } else { - it->prev->next = b_it; + if (b.ptr == nullptr) { + return; } - b_it->prev = it->prev; - b_it->next = it; - it->prev = b_it; - b_it->size = b.size; - return b_it; -} -os::phys_ptr os::paging::page_allocator_t::try_merge_prev(phys_ptr it) { - os::assert(it != end(), "end() passed to page_allocator_t::try_merge_prev(phys_ptr)."); - if (it->prev == nullptr) { return it; } - if (it->prev + it->prev->size != it) { return it; } - it->prev->size += it->size; - return erase(it)->prev; -} -os::phys_ptr os::paging::page_allocator_t::try_merge_next(phys_ptr it) { - os::assert(it != end(), "end() passed to page_allocator_t::try_merge_next(phys_ptr)."); - if (it->next == end()) return it; - try_merge_prev(it->next); - return it; -} -os::phys_ptr os::paging::page_allocator_t::erase(phys_ptr it) { - os::assert(it != end(), "end() passed to page_allocator_t::remove(phys_ptr)."); - if (it->prev == nullptr) { - begin_ = it->next; - } else { - it->prev->next = it->next; + if (begin == nullptr || phys_ptr{b.ptr.get_phys_addr()} < begin) { + auto old_begin = begin; + begin = phys_ptr{b.ptr.get_phys_addr()}; + begin->size = b.size; + begin->next = old_begin; + merge(begin); + return; } - it->next->prev = it->prev; - return it->next; + phys_ptr prec = nullptr; + for (phys_ptr it = begin; it != nullptr && it < phys_ptr{b.ptr.get_phys_addr()}; it = it->next) { + prec = it; + } + auto old_next = prec->next; + prec->next = phys_ptr{b.ptr.get_phys_addr()}; + prec->next->size = b.size; + prec->next->next = old_next; + merge(prec->next); + merge(prec); } -os::phys_ptr os::paging::page_allocator_t::split_at_offset(phys_ptr it, std::size_t offset) { - os::assert(it != end(), "end() passed to page_allocator_t::split_at_offset(phys_ptr, std::size_t)."); - os::assert(offset < it->size, "offset passed to page_allocator_t::split_at_offset(phys_ptr, std::size_t) was too big."); - os::assert(offset != 0, "offset 0 passed to page_allocator_t::split_at_offset(phys_ptr, std::size_t)."); - phys_ptr after_split = it + offset; - insert(it->next, block{ .ptr = phys_ptr{after_split.get_phys_addr()}, .size = it->size - offset }); - it->size = offset; - return it; + +bool os::paging::page_allocator_t::merge(phys_ptr it) { + if (it + it->size == it->next) { + it->size += it->next->size; + it->next == it->next->next; + return true; + } + return false; } diff --git a/kernel/src/paging.hpp b/kernel/src/paging.hpp index 1cfb999..0099912 100644 --- a/kernel/src/paging.hpp +++ b/kernel/src/paging.hpp @@ -252,7 +252,7 @@ public: std::uint64_t size; }; - page_allocator_t(phys_ptr one_past_end_page); + page_allocator_t(); void print_all() const; block allocate(std::uint64_t page_count); @@ -260,25 +260,14 @@ public: private: struct __attribute__((aligned(0x1000))) page { - phys_ptr prev; phys_ptr next; std::uint64_t size; }; static_assert(sizeof(page) == 0x1000); static_assert(alignof(page) == 0x1000); - phys_ptr begin_; - phys_ptr end_; + phys_ptr begin; - phys_ptr begin(); - phys_ptr end(); - phys_ptr begin() const; - phys_ptr end() const; - bool is_empty() const; - phys_ptr insert(phys_ptr it, block b); - phys_ptr try_merge_prev(phys_ptr it); - phys_ptr try_merge_next(phys_ptr it); - phys_ptr erase(phys_ptr it); - phys_ptr split_at_offset(phys_ptr it, std::size_t offset); + bool merge(phys_ptr it); }; } } // namespace os::paging -- 2.47.0