From 3ed3b1becd5d90608484f25abc6a8ff55c55d96c Mon Sep 17 00:00:00 2001 From: Amelia Coutard Date: Wed, 27 Dec 2023 01:14:42 +0100 Subject: [PATCH] =?utf8?q?J'ai=20commenc=C3=A9=20=C3=A0=20impl=C3=A9menter?= =?utf8?q?=20des=20alloueurs=20de=20m=C3=A9moire,=20et=20=C3=A0=20les=20ut?= =?utf8?q?iliser?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- kernel/src/kernel.cpp | 28 +++--- libcpp/allocator.hpp | 198 ++++++++++++++++++++++++++++++++++++++++++ libcpp/concept.hpp | 33 +++++++ libcpp/vector.hpp | 103 ++++++++++++++++++++++ 4 files changed, 350 insertions(+), 12 deletions(-) create mode 100644 libcpp/allocator.hpp create mode 100644 libcpp/concept.hpp create mode 100644 libcpp/vector.hpp diff --git a/kernel/src/kernel.cpp b/kernel/src/kernel.cpp index 233770e..42d0355 100644 --- a/kernel/src/kernel.cpp +++ b/kernel/src/kernel.cpp @@ -11,6 +11,8 @@ // You should have received a copy of the GNU General Public License along with this program. If // not, see . +#include +#include #include "lib/multiboot2.hpp" #include "paging.hpp" #include "utils.hpp" @@ -185,10 +187,13 @@ extern "C" void kmain(unsigned long magic, os::phys_ptr> start_address = nullptr; - os::phys_ptr> end_address = nullptr; - } available_ram[50]; + struct ram_range { + os::phys_ptr> start_address; + os::phys_ptr> end_address; + }; + amy::stack_allocator() * 64, amy::byte_align()> available_ram_allocator; + amy::vector available_ram(available_ram_allocator); + os::assert(!available_ram.construction_failed(), "Failed to create vector."); amy::size available_ram_length = 0; bool module_specified = false; @@ -210,8 +215,8 @@ extern "C" void kmain(unsigned long magic, os::phys_ptr> kernel_e{amy::ptr(&_kernel_phys_end)}; // Remove kernel from available RAM: - for (amy::ptr i = 0; i < available_ram_length; i++) { + for (amy::diff i = 0; i < available_ram.size(); i++) { if (kernel_e < available_ram[i].start_address || available_ram[i].end_address < kernel_s) { continue; } @@ -245,16 +250,15 @@ extern "C" void kmain(unsigned long magic, os::phys_ptr. + +#pragma once + +#include +#include +#include + +// The design is based on Andrei Alexandrescu's "std::allocator is to allocation what std::vector is to vexation". +// See https://github.com/CppCon/CppCon2015/tree/master/Presentations/allocator%20Is%20to%20Allocation%20what%20vector%20Is%20to%20Vexation for more details. + +namespace amy { + +template using allocator_helper = void; + +template +concept allocator = requires(T allocator) { + // max_align is the maximum alignment that this allocator can provide. + // post: max_align ≥ 1 + // post: max_align is a power of 2 + typename allocator_helper; + // good_size(size, align) returns the actual amount of bytes that will be allocated for a call to allocate(size, align). + // pre: size ≥ 1 + // pre: align ≥ 1 + // pre: align is a power of 2 + // pre: max_align ≡ 0 [align] + // post: good_size(size, align) ≥ size + // post: ∀n ≥ 0, good_size(size + n, align) ≥ good_size(size, align) + // post: ∀n ≥ 0, good_size(size, align + n) ≥ good_size(size, align) + { T::good_size(amy::declval(), amy::declval()) } -> amy::same_as; + typename allocator_helper; + // allocate(size, align) returns a pointer to a memory area of at least size bytes, aligned to align bytes, or nullptr + // pre: size ≥ 1 + // pre: align ≥ 1 + // pre: align is a power of 2 + // pre: max_align ≡ 0 [align] + { allocator.allocate(amy::declval(), amy::declval()) } -> amy::same_as; + // expand(ptr, size, delta) tries to change the size of the allocation at ptr from size to size+delta. + // If delta = 0, returns true and does nothing. + // If the memory area at ptr can be resized to size, do it and return true. + // Otherwise, return false, leaving the memory at ptr unchanged. + // pre: ptr is a pointer to a memory area of size size allocated by this allocator + // pre: size + delta ≥ 1 + { allocator.expand(amy::declval(), amy::declval(), amy::declval()) } -> amy::same_as; + // deallocate(ptr, size, align) invalidates the memory area at ptr. + // This function cannot fail. + // pre: ptr is a pointer to a memory area of size size and alignment align allocated by this allocator + { allocator.deallocate(amy::declval(), amy::declval(), amy::declval()) } -> amy::same_as; +}; + + +// reallocate(allocator, ptr, old_size, new_size, align) tries to resize this memory area, or to create a new one, such that +// the contents of it, up to the byte min(old_size, new_size), are identical, and the resulting area is aligned to align. +// If this fails, it will return amy::nil. +// Otherwise, it will return the new pointer to the area. The old one shouldn't be used anymore. +// pre: ptr is a pointer to a memory area of size old_size and alignment align allocated by the allocator allocator. +// pre: new_size ≥ 1 +void* reallocate(allocator auto allocator, void* ptr, amy::size old_size, amy::size new_size, amy::size align) { + if (allocator.expand(ptr, old_size, new_size - old_size)) { + return ptr; + } + void* res = allocator.allocate(new_size, align); + if (res == amy::nil) { + return amy::nil; + } + amy::memcpy(res, ptr, old_size < new_size ? old_size : new_size); + allocator.deallocate(ptr, old_size, align); + return res; +} + +template +concept knowning_allocator = allocator && requires(T allocator) { + // owns(ptr) returns true if, and only if, ptr is a pointer to a memory area allocated by this allocator. + // pre: ptr is a pointer to a memory area allocated by **ANY** allocator + { allocator.owns(amy::declval()) } -> amy::same_as; +}; + +template struct stack_allocator { + static_assert(data_size >= 0); + static_assert(data_align >= 1); + static_assert((data_align & (data_align - 1)) == 0); // Assert power of 2. + + static constexpr amy::size good_size(amy::size size, amy::size) { + return size; + } + static constexpr amy::size max_align = data_align; + void* allocate(amy::size size, amy::size align) { + amy::diff aligned_first_free_byte = (first_free_byte + (align - 1)) / align * align; + if (aligned_first_free_byte + size > data_size) { + return amy::nil; + } + first_free_byte = aligned_first_free_byte + size; + return &data[aligned_first_free_byte]; + } + bool expand(void* ptr, amy::size size, amy::diff delta) { + if (delta == 0) { + return true; + } + if ((amy::byte*)ptr - data + size == first_free_byte) { + if ((amy::byte*)ptr - data + size + delta > data_size) { + return false; + } + first_free_byte = (amy::byte*)ptr - data + size + delta; + return true; + } else { + return delta < 0; + } + } + void deallocate(void* ptr, amy::size size, amy::size) { + if ((amy::byte*)ptr - data + size == first_free_byte) { + first_free_byte = (amy::byte*)ptr - data; + } + } + bool owns(void* ptr) { + return amy::ptr(&data) <= amy::ptr(ptr) && amy::ptr(ptr) < amy::ptr(&data) + data_size; + } +private: + amy::byte __attribute__((aligned(data_align))) data[data_size]; + amy::diff first_free_byte = 0; +}; + +template +struct freelist { + static_assert(min_data_size >= 1); + static_assert(max_data_size >= min_data_size); + // static_assert(max_data_size >= amy::byte_size()); // Enough room for intrusive list. + static_assert(min_data_align >= 1); + static_assert(max_data_align >= min_data_align); + static_assert((min_data_align & (min_data_align - 1)) == 0); // Assert power of 2. + static_assert((max_data_align & (max_data_align - 1)) == 0); // Assert power of 2. + static_assert(max_data_align <= suballocator_t::max_align); + static_assert(min_data_size == 1 || suballocator_t::good_size(min_data_size - 1, max_data_align) < min_data_size); + static_assert(suballocator_t::good_size(max_data_size, max_data_align) == max_data_size); +private: + struct block { + block* next; + amy::byte padding[max_data_size - amy::byte_size]; + }; + +public: + static constexpr amy::size good_size(amy::size size, amy::size align) { + if (size < min_data_size || max_data_size < size || align < min_data_align || max_data_align < align) { + return suballocator_t::good_size(size, align); + } + return max_data_size; + } + static constexpr amy::size max_align = suballocator_t::max_align; + void* allocate(amy::size size, amy::size align) { + if (size < min_data_size || max_data_size < size || align < min_data_align || max_data_align < align) { + return sub.allocate(size, align); + } + if (head == amy::nil) { + return sub.allocate(max_data_size, max_data_align); + } + block* new_head = head->next; + block* old_head = head; + old_head->~block(); + head = new_head; + return old_head; + } + bool expand(void* ptr, amy::size size, amy::diff delta) { + if (min_data_size <= size && size <= max_data_size) { + delta = (size + delta) - max_data_size; + size = max_data_size; + } + if (min_data_size <= size + delta && size + delta <= max_data_size) { + delta = max_data_size - size; + } + return sub.expand(ptr, size, delta); + } + void deallocate(void* ptr, amy::size size, amy::size align) { + if (size < min_data_size || max_data_size < size || align < min_data_align || max_data_align < align) { + return sub.deallocate(ptr, size, align); + } + new(ptr) block; + amy::launder(reinterpret_cast(ptr))->next = head; + head = amy::launder(reinterpret_cast(ptr)); + } + bool owns(void* ptr) requires knowning_allocator { + return sub.owns(ptr); + } +private: + suballocator_t sub; + block* head = amy::nil; +}; + +} // namespace amy diff --git a/libcpp/concept.hpp b/libcpp/concept.hpp new file mode 100644 index 0000000..f63608b --- /dev/null +++ b/libcpp/concept.hpp @@ -0,0 +1,33 @@ +// Copyright 2023 Amélia COUTARD. +// +// This file from the program "voyage au centre des fichiers" 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. +// +// This program 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 this program. If +// not, see . + +#pragma once + +#include +#include + +namespace amy { + +template +struct same_as_helper { + constexpr static bool v = false; +}; +template +struct same_as_helper { + constexpr static bool v = true; +}; + +template +concept same_as = same_as_helper::v; + +} // namespace amy diff --git a/libcpp/vector.hpp b/libcpp/vector.hpp new file mode 100644 index 0000000..0b217ea --- /dev/null +++ b/libcpp/vector.hpp @@ -0,0 +1,103 @@ +// Copyright 2023 Amélia COUTARD. +// +// This file from the program "voyage au centre des fichiers" 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. +// +// This program 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 this program. If +// not, see . + +#pragma once + +#include +#include +#include + +namespace amy { + +template +struct vector { + static_assert(amy::byte_align() <= allocator_t::max_align); + +public: + vector(allocator_t& allocator): allocator(allocator) { + size_ = 0; + capacity_ = 1; + data = (T*)allocator.allocate(capacity_ * amy::byte_size(), amy::byte_align()); + } + bool construction_failed() { + return data == amy::nil; + } + ~vector() { + if (data != amy::nil) { + for (amy::diff i = 0; i < size_; i++) { + data[i].~T(); + } + allocator.deallocate(data, capacity_ * amy::byte_size(), amy::byte_align()); + } + } + + vector(const vector& other) { + size_ = other.size_; + capacity_ = size_ == 0 ? 1 : size_; + data = allocator.allocate(capacity_ * amy::byte_size(), amy::byte_align()); + if (data == amy::nil) { + return; + } + for (amy::diff i = 0; i < size_; i++) { + new(&data[i]) T(other.data[i]); + } + } + vector(vector&& other): allocator(other.allocator) { + data = other.data; + other.data = amy::nil; + size_ = other.size_; + capacity_ = other.capacity_; + } + vector& operator=(const vector& other) = delete; // Later, when contracts work. Because allocators must be the same. + vector& operator=(vector&& other) = delete; + + amy::size size() { + return size_; + } + amy::size capacity() { + return capacity_; + } + bool push_back(const T& v) { + if (size_ == capacity_) { + if (allocator.expand(data, capacity_ * amy::byte_size(), amy::byte_size())) { + capacity_++; + } else if (auto new_data = + amy::reallocate(allocator, data, capacity_ * amy::byte_size(), capacity_ * 2 * amy::byte_size(), amy::byte_align())) { +#pragma GCC diagnostic push +#pragma GCC diagnostic ignored "-Wdangling-pointer" + data = (T*)new_data; +#pragma GCC diagnostic pop + capacity_ *= 2; + } else { + return false; + } + } + size_++; + new(&data[size_ - 1]) T(v); + return true; + } + T& operator[](amy::size i) { + return data[i]; + } + const T& operator[](amy::size i) const { + return data[i]; + } + +private: + T* data; + amy::size size_; + amy::size capacity_; + allocator_t& allocator; +}; + +} // namespace amy -- 2.47.0