Author: Daniel Thornburgh Date: 2024-11-20T13:59:49-08:00 New Revision: 629d9e20f5713e4cfc2d2cef109dcaa5bc1e3ee2
URL: https://github.com/llvm/llvm-project/commit/629d9e20f5713e4cfc2d2cef109dcaa5bc1e3ee2 DIFF: https://github.com/llvm/llvm-project/commit/629d9e20f5713e4cfc2d2cef109dcaa5bc1e3ee2.diff LOG: Revert "[libc] Use best-fit binary trie to make malloc logarithmic (#106259)" This reverts commit c3207c31fce8afa4e5ae728804f18b4e863197e7. Added: Modified: libc/fuzzing/__support/CMakeLists.txt libc/src/__support/CMakeLists.txt libc/src/__support/block.h libc/src/__support/freelist.h libc/src/__support/freelist_heap.h libc/src/stdlib/freelist_malloc.cpp libc/test/src/__support/CMakeLists.txt libc/test/src/__support/block_test.cpp libc/test/src/__support/freelist_heap_test.cpp libc/test/src/__support/freelist_malloc_test.cpp libc/test/src/__support/freelist_test.cpp Removed: libc/fuzzing/__support/freelist_heap_fuzz.cpp libc/src/__support/freelist.cpp libc/src/__support/freestore.h libc/src/__support/freetrie.cpp libc/src/__support/freetrie.h libc/test/src/__support/freestore_test.cpp libc/test/src/__support/freetrie_test.cpp ################################################################################ diff --git a/libc/fuzzing/__support/CMakeLists.txt b/libc/fuzzing/__support/CMakeLists.txt index 9d6589d78fb819..b088761f4586a7 100644 --- a/libc/fuzzing/__support/CMakeLists.txt +++ b/libc/fuzzing/__support/CMakeLists.txt @@ -23,11 +23,3 @@ add_libc_fuzzer( COMPILE_OPTIONS -D__LIBC_EXPLICIT_SIMD_OPT ) - -add_libc_fuzzer( - freelist_heap_fuzz - SRCS - freelist_heap_fuzz.cpp - DEPENDS - libc.src.__support.freelist_heap -) diff --git a/libc/fuzzing/__support/freelist_heap_fuzz.cpp b/libc/fuzzing/__support/freelist_heap_fuzz.cpp deleted file mode 100644 index d152d0f35499f8..00000000000000 --- a/libc/fuzzing/__support/freelist_heap_fuzz.cpp +++ /dev/null @@ -1,227 +0,0 @@ -//===-- freelist_heap_fuzz.cpp --------------------------------------------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// -/// -/// Fuzzing test for llvm-libc freelist-based heap implementation. -/// -//===----------------------------------------------------------------------===// - -#include "src/__support/CPP/bit.h" -#include "src/__support/CPP/optional.h" -#include "src/__support/freelist_heap.h" -#include "src/string/memory_utils/inline_memcpy.h" -#include "src/string/memory_utils/inline_memmove.h" -#include "src/string/memory_utils/inline_memset.h" - -using LIBC_NAMESPACE::FreeListHeap; -using LIBC_NAMESPACE::inline_memset; -using LIBC_NAMESPACE::cpp::nullopt; -using LIBC_NAMESPACE::cpp::optional; - -// Record of an outstanding allocation. -struct Alloc { - void *ptr; - size_t size; - size_t alignment; - uint8_t canary; // Byte written to the allocation -}; - -// A simple vector that tracks allocations using the heap. -class AllocVec { -public: - AllocVec(FreeListHeap &heap) : heap(&heap), size_(0), capacity(0) { - allocs = nullptr; - } - - bool empty() const { return !size_; } - - size_t size() const { return size_; } - - bool push_back(Alloc alloc) { - if (size_ == capacity) { - size_t new_cap = capacity ? capacity * 2 : 1; - Alloc *new_allocs = reinterpret_cast<Alloc *>( - heap->realloc(allocs, new_cap * sizeof(Alloc))); - if (!new_allocs) - return false; - allocs = new_allocs; - capacity = new_cap; - } - allocs[size_++] = alloc; - return true; - } - - Alloc &operator[](size_t idx) { return allocs[idx]; } - - void erase_idx(size_t idx) { - LIBC_NAMESPACE::inline_memmove(&allocs[idx], &allocs[idx + 1], - sizeof(Alloc) * (size_ - idx - 1)); - --size_; - } - -private: - FreeListHeap *heap; - Alloc *allocs; - size_t size_; - size_t capacity; -}; - -// Choose a T value by casting libfuzzer data or exit. -template <typename T> -optional<T> choose(const uint8_t *&data, size_t &remainder) { - if (sizeof(T) > remainder) - return nullopt; - T out; - LIBC_NAMESPACE::inline_memcpy(&out, data, sizeof(T)); - data += sizeof(T); - remainder -= sizeof(T); - return out; -} - -// The type of allocation to perform -enum class AllocType : uint8_t { - MALLOC, - ALIGNED_ALLOC, - REALLOC, - CALLOC, - NUM_ALLOC_TYPES, -}; - -template <> -optional<AllocType> choose<AllocType>(const uint8_t *&data, size_t &remainder) { - auto raw = choose<uint8_t>(data, remainder); - if (!raw) - return nullopt; - return static_cast<AllocType>( - *raw % static_cast<uint8_t>(AllocType::NUM_ALLOC_TYPES)); -} - -constexpr size_t heap_size = 64 * 1024; - -optional<size_t> choose_size(const uint8_t *&data, size_t &remainder) { - auto raw = choose<size_t>(data, remainder); - if (!raw) - return nullopt; - return *raw % heap_size; -} - -optional<size_t> choose_alloc_idx(const AllocVec &allocs, const uint8_t *&data, - size_t &remainder) { - if (allocs.empty()) - return nullopt; - auto raw = choose<size_t>(data, remainder); - if (!raw) - return nullopt; - return *raw % allocs.size(); -} - -#define ASSIGN_OR_RETURN(TYPE, NAME, EXPR) \ - auto maybe_##NAME = EXPR; \ - if (!maybe_##NAME) \ - return 0; \ - TYPE NAME = *maybe_##NAME - -extern "C" int LLVMFuzzerTestOneInput(const uint8_t *data, size_t remainder) { - LIBC_NAMESPACE::FreeListHeapBuffer<heap_size> heap; - AllocVec allocs(heap); - - uint8_t canary = 0; - while (true) { - ASSIGN_OR_RETURN(auto, should_alloc, choose<bool>(data, remainder)); - if (should_alloc) { - ASSIGN_OR_RETURN(auto, alloc_type, choose<AllocType>(data, remainder)); - ASSIGN_OR_RETURN(size_t, alloc_size, choose_size(data, remainder)); - - // Perform allocation. - void *ptr = nullptr; - size_t alignment = alignof(max_align_t); - switch (alloc_type) { - case AllocType::MALLOC: - ptr = heap.allocate(alloc_size); - break; - case AllocType::ALIGNED_ALLOC: { - ASSIGN_OR_RETURN(size_t, alignment, choose_size(data, remainder)); - alignment = LIBC_NAMESPACE::cpp::bit_ceil(alignment); - ptr = heap.aligned_allocate(alignment, alloc_size); - break; - } - case AllocType::REALLOC: { - if (!alloc_size) - return 0; - ASSIGN_OR_RETURN(size_t, idx, - choose_alloc_idx(allocs, data, remainder)); - Alloc &alloc = allocs[idx]; - ptr = heap.realloc(alloc.ptr, alloc_size); - if (ptr) { - // Extend the canary region if necessary. - if (alloc_size > alloc.size) - inline_memset(static_cast<char *>(ptr) + alloc.size, alloc.canary, - alloc_size - alloc.size); - alloc.ptr = ptr; - alloc.size = alloc_size; - alloc.alignment = alignof(max_align_t); - } - break; - } - case AllocType::CALLOC: { - ASSIGN_OR_RETURN(size_t, count, choose_size(data, remainder)); - size_t total; - if (__builtin_mul_overflow(count, alloc_size, &total)) - return 0; - ptr = heap.calloc(count, alloc_size); - if (ptr) - for (size_t i = 0; i < total; ++i) - if (static_cast<char *>(ptr)[i] != 0) - __builtin_trap(); - break; - } - case AllocType::NUM_ALLOC_TYPES: - __builtin_unreachable(); - } - - if (ptr) { - // aligned_allocate should automatically apply a minimum alignment. - if (alignment < alignof(max_align_t)) - alignment = alignof(max_align_t); - // Check alignment. - if (reinterpret_cast<uintptr_t>(ptr) % alignment) - __builtin_trap(); - - // Reallocation is treated specially above, since we would otherwise - // lose the original size. - if (alloc_type != AllocType::REALLOC) { - // Fill the object with a canary byte. - inline_memset(ptr, canary, alloc_size); - - // Track the allocation. - if (!allocs.push_back({ptr, alloc_size, alignment, canary})) - return 0; - ++canary; - } - } - } else { - // Select a random allocation. - ASSIGN_OR_RETURN(size_t, idx, choose_alloc_idx(allocs, data, remainder)); - Alloc &alloc = allocs[idx]; - - // Check alignment. - if (reinterpret_cast<uintptr_t>(alloc.ptr) % alloc.alignment) - __builtin_trap(); - - // Check the canary. - uint8_t *ptr = reinterpret_cast<uint8_t *>(alloc.ptr); - for (size_t i = 0; i < alloc.size; ++i) - if (ptr[i] != alloc.canary) - __builtin_trap(); - - // Free the allocation and untrack it. - heap.free(alloc.ptr); - allocs.erase_idx(idx); - } - } - return 0; -} diff --git a/libc/src/__support/CMakeLists.txt b/libc/src/__support/CMakeLists.txt index 8f85740f70a06e..6637ff9d56f4bc 100644 --- a/libc/src/__support/CMakeLists.txt +++ b/libc/src/__support/CMakeLists.txt @@ -14,14 +14,11 @@ add_header_library( libc.src.__support.CPP.type_traits ) -add_object_library( +add_header_library( freelist HDRS freelist.h - SRCS - freelist.cpp DEPENDS - .block libc.src.__support.fixedvector libc.src.__support.CPP.array libc.src.__support.CPP.cstddef @@ -29,32 +26,13 @@ add_object_library( libc.src.__support.CPP.span ) -add_object_library( - freetrie - HDRS - freetrie.h - SRCS - freetrie.cpp - DEPENDS - .block - .freelist -) - -add_header_library( - freestore - HDRS - freestore.h - DEPENDS - .freetrie -) - add_header_library( freelist_heap HDRS freelist_heap.h DEPENDS .block - .freestore + .freelist libc.src.__support.CPP.cstddef libc.src.__support.CPP.array libc.src.__support.CPP.optional diff --git a/libc/src/__support/block.h b/libc/src/__support/block.h index e63801301ac752..96021b99587c87 100644 --- a/libc/src/__support/block.h +++ b/libc/src/__support/block.h @@ -174,32 +174,16 @@ class Block { return inner_size - sizeof(prev_) + BLOCK_OVERHEAD; } - /// @returns The number of usable bytes inside the block were it to be - /// allocated. + /// @returns The number of usable bytes inside the block. size_t inner_size() const { if (!next()) return 0; return inner_size(outer_size()); } - /// @returns The number of usable bytes inside a block with the given outer - /// size were it to be allocated. static size_t inner_size(size_t outer_size) { // The usable region includes the prev_ field of the next block. - return inner_size_free(outer_size) + sizeof(prev_); - } - - /// @returns The number of usable bytes inside the block if it remains free. - size_t inner_size_free() const { - if (!next()) - return 0; - return inner_size_free(outer_size()); - } - - /// @returns The number of usable bytes inside a block with the given outer - /// size if it remains free. - static size_t inner_size_free(size_t outer_size) { - return outer_size - BLOCK_OVERHEAD; + return outer_size - BLOCK_OVERHEAD + sizeof(prev_); } /// @returns A pointer to the usable space inside this block. @@ -217,11 +201,14 @@ class Block { /// Attempts to split this block. /// - /// If successful, the block will have an inner size of at least - /// `new_inner_size`, rounded to ensure that the split point is on an - /// ALIGNMENT boundary. The remaining space will be returned as a new block. - /// Note that the prev_ field of the next block counts as part of the inner - /// size of the returnd block. + /// If successful, the block will have an inner size of `new_inner_size`, + /// rounded to ensure that the split point is on an ALIGNMENT boundary. The + /// remaining space will be returned as a new block. Note that the prev_ field + /// of the next block counts as part of the inner size of the returnd block. + /// + /// This method may fail if the remaining space is too small to hold a new + /// block. If this method fails for any reason, the original block is + /// unmodified. optional<Block *> split(size_t new_inner_size); /// Merges this block with the one that comes after it. @@ -455,7 +442,7 @@ Block<OffsetType, kAlign>::split(size_t new_inner_size) { // The prev_ field of the next block is always available, so there is a // minimum size to a block created through splitting. if (new_inner_size < sizeof(prev_)) - new_inner_size = sizeof(prev_); + return {}; size_t old_inner_size = inner_size(); new_inner_size = diff --git a/libc/src/__support/freelist.cpp b/libc/src/__support/freelist.cpp deleted file mode 100644 index d3dd44895130cd..00000000000000 --- a/libc/src/__support/freelist.cpp +++ /dev/null @@ -1,42 +0,0 @@ -//===-- Implementation for freelist ---------------------------------------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#include "freelist.h" - -namespace LIBC_NAMESPACE_DECL { - -void FreeList::push(Node *node) { - if (begin_) { - LIBC_ASSERT(Block<>::from_usable_space(node)->outer_size() == - begin_->block()->outer_size() && - "freelist entries must have the same size"); - // Since the list is circular, insert the node immediately before begin_. - node->prev = begin_->prev; - node->next = begin_; - begin_->prev->next = node; - begin_->prev = node; - } else { - begin_ = node->prev = node->next = node; - } -} - -void FreeList::remove(Node *node) { - LIBC_ASSERT(begin_ && "cannot remove from empty list"); - if (node == node->next) { - LIBC_ASSERT(node == begin_ && - "a self-referential node must be the only element"); - begin_ = nullptr; - } else { - node->prev->next = node->next; - node->next->prev = node->prev; - if (begin_ == node) - begin_ = node->next; - } -} - -} // namespace LIBC_NAMESPACE_DECL diff --git a/libc/src/__support/freelist.h b/libc/src/__support/freelist.h index eaeaeb013eeaec..a54cf953fe7ab6 100644 --- a/libc/src/__support/freelist.h +++ b/libc/src/__support/freelist.h @@ -1,4 +1,4 @@ -//===-- Interface for freelist --------------------------------------------===// +//===-- Interface for freelist_malloc -------------------------------------===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. @@ -9,80 +9,200 @@ #ifndef LLVM_LIBC_SRC___SUPPORT_FREELIST_H #define LLVM_LIBC_SRC___SUPPORT_FREELIST_H -#include "block.h" +#include "src/__support/CPP/array.h" +#include "src/__support/CPP/cstddef.h" +#include "src/__support/CPP/new.h" +#include "src/__support/CPP/span.h" +#include "src/__support/fixedvector.h" +#include "src/__support/macros/config.h" namespace LIBC_NAMESPACE_DECL { -/// A circularly-linked FIFO list storing free Blocks. All Blocks on a list -/// are the same size. The blocks are referenced by Nodes in the list; the list -/// refers to these, but it does not own them. +using cpp::span; + +/// Basic [freelist](https://en.wikipedia.org/wiki/Free_list) implementation +/// for an allocator. This implementation buckets by chunk size, with a list +/// of user-provided buckets. Each bucket is a linked list of storage chunks. +/// Because this freelist uses the added chunks themselves as list nodes, there +/// is a lower bound of `sizeof(FreeList.FreeListNode)` bytes for chunks which +/// can be added to this freelist. There is also an implicit bucket for +/// "everything else", for chunks which do not fit into a bucket. +/// +/// Each added chunk will be added to the smallest bucket under which it fits. +/// If it does not fit into any user-provided bucket, it will be added to the +/// default bucket. +/// +/// As an example, assume that the `FreeList` is configured with buckets of +/// sizes {64, 128, 256, and 512} bytes. The internal state may look like the +/// following: /// -/// Allocating free blocks in FIFO order maximizes the amount of time before a -/// free block is reused. This in turn maximizes the number of opportunities for -/// it to be coalesced with an adjacent block, which tends to reduce heap -/// fragmentation. -class FreeList { +/// @code{.unparsed} +/// bucket[0] (64B) --> chunk[12B] --> chunk[42B] --> chunk[64B] --> NULL +/// bucket[1] (128B) --> chunk[65B] --> chunk[72B] --> NULL +/// bucket[2] (256B) --> NULL +/// bucket[3] (512B) --> chunk[312B] --> chunk[512B] --> chunk[416B] --> NULL +/// bucket[4] (implicit) --> chunk[1024B] --> chunk[513B] --> NULL +/// @endcode +/// +/// Note that added chunks should be aligned to a 4-byte boundary. +template <size_t NUM_BUCKETS = 6> class FreeList { public: - class Node { - public: - /// @returns The block containing this node. - LIBC_INLINE const Block<> *block() const { - return Block<>::from_usable_space(this); + // Remove copy/move ctors + FreeList(const FreeList &other) = delete; + FreeList(FreeList &&other) = delete; + FreeList &operator=(const FreeList &other) = delete; + FreeList &operator=(FreeList &&other) = delete; + + /// Adds a chunk to this freelist. + bool add_chunk(cpp::span<cpp::byte> chunk); + + /// Finds an eligible chunk for an allocation of size `size`. + /// + /// @note This returns the first allocation possible within a given bucket; + /// It does not currently optimize for finding the smallest chunk. + /// + /// @returns + /// * On success - A span representing the chunk. + /// * On failure (e.g. there were no chunks available for that allocation) - + /// A span with a size of 0. + cpp::span<cpp::byte> find_chunk(size_t size) const; + + template <typename Cond> cpp::span<cpp::byte> find_chunk_if(Cond op) const; + + /// Removes a chunk from this freelist. + bool remove_chunk(cpp::span<cpp::byte> chunk); + + /// For a given size, find which index into chunks_ the node should be written + /// to. + constexpr size_t find_chunk_ptr_for_size(size_t size, bool non_null) const; + + struct FreeListNode { + FreeListNode *next; + size_t size; + }; + + constexpr void set_freelist_node(FreeListNode &node, + cpp::span<cpp::byte> chunk); + + constexpr explicit FreeList(const cpp::array<size_t, NUM_BUCKETS> &sizes) + : chunks_(NUM_BUCKETS + 1, 0), sizes_(sizes.begin(), sizes.end()) {} + +private: + FixedVector<FreeList::FreeListNode *, NUM_BUCKETS + 1> chunks_; + FixedVector<size_t, NUM_BUCKETS> sizes_; +}; + +template <size_t NUM_BUCKETS> +constexpr void FreeList<NUM_BUCKETS>::set_freelist_node(FreeListNode &node, + span<cpp::byte> chunk) { + // Add it to the correct list. + size_t chunk_ptr = find_chunk_ptr_for_size(chunk.size(), false); + node.size = chunk.size(); + node.next = chunks_[chunk_ptr]; + chunks_[chunk_ptr] = &node; +} + +template <size_t NUM_BUCKETS> +bool FreeList<NUM_BUCKETS>::add_chunk(span<cpp::byte> chunk) { + // Check that the size is enough to actually store what we need + if (chunk.size() < sizeof(FreeListNode)) + return false; + + FreeListNode *node = ::new (chunk.data()) FreeListNode; + set_freelist_node(*node, chunk); + + return true; +} + +template <size_t NUM_BUCKETS> +template <typename Cond> +span<cpp::byte> FreeList<NUM_BUCKETS>::find_chunk_if(Cond op) const { + for (FreeListNode *node : chunks_) { + while (node != nullptr) { + span<cpp::byte> chunk(reinterpret_cast<cpp::byte *>(node), node->size); + if (op(chunk)) + return chunk; + + node = node->next; } + } - /// @returns The block containing this node. - LIBC_INLINE Block<> *block() { return Block<>::from_usable_space(this); } + return {}; +} - /// @returns The inner size of blocks in the list containing this node. - LIBC_INLINE size_t size() const { return block()->inner_size(); } +template <size_t NUM_BUCKETS> +span<cpp::byte> FreeList<NUM_BUCKETS>::find_chunk(size_t size) const { + if (size == 0) + return span<cpp::byte>(); - private: - // Circularly linked pointers to adjacent nodes. - Node *prev; - Node *next; - friend class FreeList; - }; + size_t chunk_ptr = find_chunk_ptr_for_size(size, true); + + // Check that there's data. This catches the case where we run off the + // end of the array + if (chunks_[chunk_ptr] == nullptr) + return span<cpp::byte>(); - LIBC_INLINE constexpr FreeList() : FreeList(nullptr) {} - LIBC_INLINE constexpr FreeList(Node *begin) : begin_(begin) {} + // Now iterate up the buckets, walking each list to find a good candidate + for (size_t i = chunk_ptr; i < chunks_.size(); i++) { + FreeListNode *node = chunks_[static_cast<unsigned short>(i)]; - LIBC_INLINE bool empty() const { return !begin_; } + while (node != nullptr) { + if (node->size >= size) + return span<cpp::byte>(reinterpret_cast<cpp::byte *>(node), node->size); - /// @returns The inner size of blocks in the list. - LIBC_INLINE size_t size() const { - LIBC_ASSERT(begin_ && "empty lists have no size"); - return begin_->size(); + node = node->next; + } } - /// @returns The first node in the list. - LIBC_INLINE Node *begin() { return begin_; } + // If we get here, we've checked every block in every bucket. There's + // nothing that can support this allocation. + return span<cpp::byte>(); +} - /// @returns The first block in the list. - LIBC_INLINE Block<> *front() { return begin_->block(); } +template <size_t NUM_BUCKETS> +bool FreeList<NUM_BUCKETS>::remove_chunk(span<cpp::byte> chunk) { + size_t chunk_ptr = find_chunk_ptr_for_size(chunk.size(), true); - /// Push a block to the back of the list. - /// The block must be large enough to contain a node. - LIBC_INLINE void push(Block<> *block) { - LIBC_ASSERT(!block->used() && - "only free blocks can be placed on free lists"); - LIBC_ASSERT(block->inner_size_free() >= sizeof(FreeList) && - "block too small to accomodate free list node"); - push(new (block->usable_space()) Node); + // Check head first. + if (chunks_[chunk_ptr] == nullptr) + return false; + + FreeListNode *node = chunks_[chunk_ptr]; + if (reinterpret_cast<cpp::byte *>(node) == chunk.data()) { + chunks_[chunk_ptr] = node->next; + return true; } - /// Push an already-constructed node to the back of the list. - /// This allows pushing derived node types with additional data. - void push(Node *node); + // No? Walk the nodes. + node = chunks_[chunk_ptr]; - /// Pop the first node from the list. - LIBC_INLINE void pop() { remove(begin_); } + while (node->next != nullptr) { + if (reinterpret_cast<cpp::byte *>(node->next) == chunk.data()) { + // Found it, remove this node out of the chain + node->next = node->next->next; + return true; + } - /// Remove an arbitrary node from the list. - void remove(Node *node); + node = node->next; + } -private: - Node *begin_; -}; + return false; +} + +template <size_t NUM_BUCKETS> +constexpr size_t +FreeList<NUM_BUCKETS>::find_chunk_ptr_for_size(size_t size, + bool non_null) const { + size_t chunk_ptr = 0; + for (chunk_ptr = 0u; chunk_ptr < sizes_.size(); chunk_ptr++) { + if (sizes_[chunk_ptr] >= size && + (!non_null || chunks_[chunk_ptr] != nullptr)) { + break; + } + } + + return chunk_ptr; +} } // namespace LIBC_NAMESPACE_DECL diff --git a/libc/src/__support/freelist_heap.h b/libc/src/__support/freelist_heap.h index dd9069ce91430d..6c860d039553ab 100644 --- a/libc/src/__support/freelist_heap.h +++ b/libc/src/__support/freelist_heap.h @@ -12,12 +12,11 @@ #include <stddef.h> #include "block.h" -#include "freestore.h" +#include "freelist.h" #include "src/__support/CPP/optional.h" #include "src/__support/CPP/span.h" #include "src/__support/libc_assert.h" #include "src/__support/macros/config.h" -#include "src/__support/math_extras.h" #include "src/string/memory_utils/inline_memcpy.h" #include "src/string/memory_utils/inline_memset.h" @@ -29,14 +28,23 @@ extern "C" cpp::byte __llvm_libc_heap_limit; using cpp::optional; using cpp::span; -LIBC_INLINE constexpr bool IsPow2(size_t x) { return x && (x & (x - 1)) == 0; } +inline constexpr bool IsPow2(size_t x) { return x && (x & (x - 1)) == 0; } -class FreeListHeap { +static constexpr cpp::array<size_t, 6> DEFAULT_BUCKETS{16, 32, 64, + 128, 256, 512}; + +template <size_t NUM_BUCKETS = DEFAULT_BUCKETS.size()> class FreeListHeap { public: - constexpr FreeListHeap() : begin(&_end), end(&__llvm_libc_heap_limit) {} + using BlockType = Block<>; + using FreeListType = FreeList<NUM_BUCKETS>; + + static constexpr size_t MIN_ALIGNMENT = + cpp::max(BlockType::ALIGNMENT, alignof(max_align_t)); + + constexpr FreeListHeap() : begin_(&_end), end_(&__llvm_libc_heap_limit) {} constexpr FreeListHeap(span<cpp::byte> region) - : begin(region.begin()), end(region.end()) {} + : begin_(region.begin()), end_(region.end()) {} void *allocate(size_t size); void *aligned_allocate(size_t alignment, size_t size); @@ -46,79 +54,89 @@ class FreeListHeap { void *realloc(void *ptr, size_t size); void *calloc(size_t num, size_t size); - cpp::span<cpp::byte> region() const { return {begin, end}; } + cpp::span<cpp::byte> region() const { return {begin_, end_}; } private: void init(); void *allocate_impl(size_t alignment, size_t size); - span<cpp::byte> block_to_span(Block<> *block) { + span<cpp::byte> block_to_span(BlockType *block) { return span<cpp::byte>(block->usable_space(), block->inner_size()); } - bool is_valid_ptr(void *ptr) { return ptr >= begin && ptr < end; } + bool is_valid_ptr(void *ptr) { return ptr >= begin_ && ptr < end_; } - cpp::byte *begin; - cpp::byte *end; - bool is_initialized = false; - FreeStore free_store; + bool is_initialized_ = false; + cpp::byte *begin_; + cpp::byte *end_; + FreeListType freelist_{DEFAULT_BUCKETS}; }; -template <size_t BUFF_SIZE> class FreeListHeapBuffer : public FreeListHeap { +template <size_t BUFF_SIZE, size_t NUM_BUCKETS = DEFAULT_BUCKETS.size()> +class FreeListHeapBuffer : public FreeListHeap<NUM_BUCKETS> { + using parent = FreeListHeap<NUM_BUCKETS>; + using FreeListNode = typename parent::FreeListType::FreeListNode; + public: - constexpr FreeListHeapBuffer() : FreeListHeap{buffer}, buffer{} {} + constexpr FreeListHeapBuffer() + : FreeListHeap<NUM_BUCKETS>{buffer}, buffer{} {} private: cpp::byte buffer[BUFF_SIZE]; }; -LIBC_INLINE void FreeListHeap::init() { - LIBC_ASSERT(!is_initialized && "duplicate initialization"); - auto result = Block<>::init(region()); - Block<> *block = *result; - free_store.set_range({0, cpp::bit_ceil(block->inner_size())}); - free_store.insert(block); - is_initialized = true; +template <size_t NUM_BUCKETS> void FreeListHeap<NUM_BUCKETS>::init() { + LIBC_ASSERT(!is_initialized_ && "duplicate initialization"); + auto result = BlockType::init(region()); + BlockType *block = *result; + freelist_.add_chunk(block_to_span(block)); + is_initialized_ = true; } -LIBC_INLINE void *FreeListHeap::allocate_impl(size_t alignment, size_t size) { +template <size_t NUM_BUCKETS> +void *FreeListHeap<NUM_BUCKETS>::allocate_impl(size_t alignment, size_t size) { if (size == 0) return nullptr; - if (!is_initialized) + if (!is_initialized_) init(); - size_t request_size = size; - if (alignment > alignof(max_align_t)) { - if (add_overflow(size, alignment - 1, request_size)) - return nullptr; - } + // Find a chunk in the freelist. Split it if needed, then return. + auto chunk = + freelist_.find_chunk_if([alignment, size](span<cpp::byte> chunk) { + BlockType *block = BlockType::from_usable_space(chunk.data()); + return block->can_allocate(alignment, size); + }); - Block<> *block = free_store.remove_best_fit(request_size); - if (!block) + if (chunk.data() == nullptr) return nullptr; + freelist_.remove_chunk(chunk); - LIBC_ASSERT(block->can_allocate(alignment, size) && - "block should always be large enough to allocate at the correct " - "alignment"); + BlockType *chunk_block = BlockType::from_usable_space(chunk.data()); + LIBC_ASSERT(!chunk_block->used()); - auto block_info = Block<>::allocate(block, alignment, size); + // Split that chunk. If there's a leftover chunk, add it to the freelist + auto block_info = BlockType::allocate(chunk_block, alignment, size); if (block_info.next) - free_store.insert(block_info.next); + freelist_.add_chunk(block_to_span(block_info.next)); if (block_info.prev) - free_store.insert(block_info.prev); + freelist_.add_chunk(block_to_span(block_info.prev)); + chunk_block = block_info.block; + + chunk_block->mark_used(); - block_info.block->mark_used(); - return block_info.block->usable_space(); + return chunk_block->usable_space(); } -LIBC_INLINE void *FreeListHeap::allocate(size_t size) { - return allocate_impl(alignof(max_align_t), size); +template <size_t NUM_BUCKETS> +void *FreeListHeap<NUM_BUCKETS>::allocate(size_t size) { + return allocate_impl(MIN_ALIGNMENT, size); } -LIBC_INLINE void *FreeListHeap::aligned_allocate(size_t alignment, - size_t size) { +template <size_t NUM_BUCKETS> +void *FreeListHeap<NUM_BUCKETS>::aligned_allocate(size_t alignment, + size_t size) { // The alignment must be an integral power of two. if (!IsPow2(alignment)) return nullptr; @@ -130,37 +148,38 @@ LIBC_INLINE void *FreeListHeap::aligned_allocate(size_t alignment, return allocate_impl(alignment, size); } -LIBC_INLINE void FreeListHeap::free(void *ptr) { +template <size_t NUM_BUCKETS> void FreeListHeap<NUM_BUCKETS>::free(void *ptr) { cpp::byte *bytes = static_cast<cpp::byte *>(ptr); LIBC_ASSERT(is_valid_ptr(bytes) && "Invalid pointer"); - Block<> *block = Block<>::from_usable_space(bytes); - LIBC_ASSERT(block->next() && "sentinel last block cannot be freed"); - LIBC_ASSERT(block->used() && "double free"); - block->mark_free(); + BlockType *chunk_block = BlockType::from_usable_space(bytes); + LIBC_ASSERT(chunk_block->next() && "sentinel last block cannot be freed"); + LIBC_ASSERT(chunk_block->used() && "The block is not in-use"); + chunk_block->mark_free(); // Can we combine with the left or right blocks? - Block<> *prev_free = block->prev_free(); - Block<> *next = block->next(); + BlockType *prev_free = chunk_block->prev_free(); + BlockType *next = chunk_block->next(); if (prev_free != nullptr) { - // Remove from free store and merge. - free_store.remove(prev_free); - block = prev_free; - block->merge_next(); + // Remove from freelist and merge + freelist_.remove_chunk(block_to_span(prev_free)); + chunk_block = prev_free; + chunk_block->merge_next(); } if (!next->used()) { - free_store.remove(next); - block->merge_next(); + freelist_.remove_chunk(block_to_span(next)); + chunk_block->merge_next(); } // Add back to the freelist - free_store.insert(block); + freelist_.add_chunk(block_to_span(chunk_block)); } // Follows constract of the C standard realloc() function // If ptr is free'd, will return nullptr. -LIBC_INLINE void *FreeListHeap::realloc(void *ptr, size_t size) { +template <size_t NUM_BUCKETS> +void *FreeListHeap<NUM_BUCKETS>::realloc(void *ptr, size_t size) { if (size == 0) { free(ptr); return nullptr; @@ -175,10 +194,10 @@ LIBC_INLINE void *FreeListHeap::realloc(void *ptr, size_t size) { if (!is_valid_ptr(bytes)) return nullptr; - Block<> *block = Block<>::from_usable_space(bytes); - if (!block->used()) + BlockType *chunk_block = BlockType::from_usable_space(bytes); + if (!chunk_block->used()) return nullptr; - size_t old_size = block->inner_size(); + size_t old_size = chunk_block->inner_size(); // Do nothing and return ptr if the required memory size is smaller than // the current size. @@ -195,17 +214,15 @@ LIBC_INLINE void *FreeListHeap::realloc(void *ptr, size_t size) { return new_ptr; } -LIBC_INLINE void *FreeListHeap::calloc(size_t num, size_t size) { - size_t bytes; - if (__builtin_mul_overflow(num, size, &bytes)) - return nullptr; - void *ptr = allocate(bytes); +template <size_t NUM_BUCKETS> +void *FreeListHeap<NUM_BUCKETS>::calloc(size_t num, size_t size) { + void *ptr = allocate(num * size); if (ptr != nullptr) - LIBC_NAMESPACE::inline_memset(ptr, 0, bytes); + LIBC_NAMESPACE::inline_memset(ptr, 0, num * size); return ptr; } -extern FreeListHeap *freelist_heap; +extern FreeListHeap<> *freelist_heap; } // namespace LIBC_NAMESPACE_DECL diff --git a/libc/src/__support/freestore.h b/libc/src/__support/freestore.h deleted file mode 100644 index f04b561f5d91dc..00000000000000 --- a/libc/src/__support/freestore.h +++ /dev/null @@ -1,114 +0,0 @@ -//===-- Interface for freestore ------------------------------------------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_LIBC_SRC___SUPPORT_FREESTORE_H -#define LLVM_LIBC_SRC___SUPPORT_FREESTORE_H - -#include "freetrie.h" - -namespace LIBC_NAMESPACE_DECL { - -/// A best-fit store of variously-sized free blocks. Blocks can be inserted and -/// removed in logarithmic time. -class FreeStore { -public: - FreeStore() = default; - FreeStore(const FreeStore &other) = delete; - FreeStore &operator=(const FreeStore &other) = delete; - - /// Sets the range of possible block sizes. This can only be called when the - /// trie is empty. - LIBC_INLINE void set_range(FreeTrie::SizeRange range) { - large_trie.set_range(range); - } - - /// Insert a free block. If the block is too small to be tracked, nothing - /// happens. - void insert(Block<> *block); - - /// Remove a free block. If the block is too small to be tracked, nothing - /// happens. - void remove(Block<> *block); - - /// Remove a best-fit free block that can contain the given size when - /// allocated. Returns nullptr if there is no such block. - Block<> *remove_best_fit(size_t size); - -private: - static constexpr size_t ALIGNMENT = alignof(max_align_t); - static constexpr size_t MIN_OUTER_SIZE = - align_up(Block<>::BLOCK_OVERHEAD + sizeof(FreeList::Node), ALIGNMENT); - static constexpr size_t MIN_LARGE_OUTER_SIZE = - align_up(Block<>::BLOCK_OVERHEAD + sizeof(FreeTrie::Node), ALIGNMENT); - static constexpr size_t NUM_SMALL_SIZES = - (MIN_LARGE_OUTER_SIZE - MIN_OUTER_SIZE) / ALIGNMENT; - - LIBC_INLINE static bool too_small(Block<> *block) { - return block->outer_size() < MIN_OUTER_SIZE; - } - LIBC_INLINE static bool is_small(Block<> *block) { - return block->outer_size() < MIN_LARGE_OUTER_SIZE; - } - - FreeList &small_list(Block<> *block); - FreeList *find_best_small_fit(size_t size); - - cpp::array<FreeList, NUM_SMALL_SIZES> small_lists; - FreeTrie large_trie; -}; - -LIBC_INLINE void FreeStore::insert(Block<> *block) { - if (too_small(block)) - return; - if (is_small(block)) - small_list(block).push(block); - else - large_trie.push(block); -} - -LIBC_INLINE void FreeStore::remove(Block<> *block) { - if (too_small(block)) - return; - if (is_small(block)) { - small_list(block).remove( - reinterpret_cast<FreeList::Node *>(block->usable_space())); - } else { - large_trie.remove( - reinterpret_cast<FreeTrie::Node *>(block->usable_space())); - } -} - -LIBC_INLINE Block<> *FreeStore::remove_best_fit(size_t size) { - if (FreeList *list = find_best_small_fit(size)) { - Block<> *block = list->front(); - list->pop(); - return block; - } - if (FreeTrie::Node *best_fit = large_trie.find_best_fit(size)) { - Block<> *block = best_fit->block(); - large_trie.remove(best_fit); - return block; - } - return nullptr; -} - -LIBC_INLINE FreeList &FreeStore::small_list(Block<> *block) { - LIBC_ASSERT(is_small(block) && "only legal for small blocks"); - return small_lists[(block->outer_size() - MIN_OUTER_SIZE) / ALIGNMENT]; -} - -LIBC_INLINE FreeList *FreeStore::find_best_small_fit(size_t size) { - for (FreeList &list : small_lists) - if (!list.empty() && list.size() >= size) - return &list; - return nullptr; -} - -} // namespace LIBC_NAMESPACE_DECL - -#endif // LLVM_LIBC_SRC___SUPPORT_FREESTORE_H diff --git a/libc/src/__support/freetrie.cpp b/libc/src/__support/freetrie.cpp deleted file mode 100644 index e76efe717f2154..00000000000000 --- a/libc/src/__support/freetrie.cpp +++ /dev/null @@ -1,64 +0,0 @@ -//===-- Implementation for freetrie ---------------------------------------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#include "freetrie.h" - -namespace LIBC_NAMESPACE_DECL { - -void FreeTrie::remove(Node *node) { - LIBC_ASSERT(!empty() && "cannot remove from empty trie"); - FreeList list = node; - list.pop(); - Node *new_node = static_cast<Node *>(list.begin()); - if (!new_node) { - // The freelist is empty. Replace the subtrie root with an arbitrary leaf. - // This is legal because there is no relationship between the size of the - // root and its children. - Node *leaf = node; - while (leaf->lower || leaf->upper) - leaf = leaf->lower ? leaf->lower : leaf->upper; - if (leaf == node) { - // If the root is a leaf, then removing it empties the subtrie. - replace_node(node, nullptr); - return; - } - - replace_node(leaf, nullptr); - new_node = leaf; - } - - if (!is_head(node)) - return; - - // Copy the trie links to the new head. - new_node->lower = node->lower; - new_node->upper = node->upper; - new_node->parent = node->parent; - replace_node(node, new_node); -} - -void FreeTrie::replace_node(Node *node, Node *new_node) { - LIBC_ASSERT(is_head(node) && "only head nodes contain trie links"); - - if (node->parent) { - Node *&parent_child = - node->parent->lower == node ? node->parent->lower : node->parent->upper; - LIBC_ASSERT(parent_child == node && - "no reference to child node found in parent"); - parent_child = new_node; - } else { - LIBC_ASSERT(root == node && "non-root node had no parent"); - root = new_node; - } - if (node->lower) - node->lower->parent = new_node; - if (node->upper) - node->upper->parent = new_node; -} - -} // namespace LIBC_NAMESPACE_DECL diff --git a/libc/src/__support/freetrie.h b/libc/src/__support/freetrie.h deleted file mode 100644 index 1830b06c8e3aec..00000000000000 --- a/libc/src/__support/freetrie.h +++ /dev/null @@ -1,237 +0,0 @@ -//===-- Interface for freetrie --------------------------------------------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_LIBC_SRC___SUPPORT_FREETRIE_H -#define LLVM_LIBC_SRC___SUPPORT_FREETRIE_H - -#include "freelist.h" - -namespace LIBC_NAMESPACE_DECL { - -/// A trie of free lists. -/// -/// This is an unusual little data structure originally from Doug Lea's malloc. -/// Finding the best fit from a set of diff erently-sized free list typically -/// required some kind of ordered map, and these are typically implemented using -/// a self-balancing binary search tree. Those are notorious for having a -/// relatively large number of special cases, while this trie has relatively -/// few, which helps with code size. -/// -/// Operations on the trie are logarithmic not on the number of nodes within it, -/// but rather the fixed range of possible sizes that the trie can contain. This -/// means that the data structure would likely actually perform worse than an -/// e.g. red-black tree, but its implementation is still much simpler. -/// -/// Each trie node's children subdivide the range of possible sizes into two -/// halves: a lower and an upper. The node itself holds a free list of some size -/// within its range. This makes it possible to summarily replace any node with -/// any leaf within its subtrie, which makes it very straightforward to remove a -/// node. Insertion is also simple; the only real complexity lies with finding -/// the best fit. This can still be done in logarithmic time with only a few -/// cases to consider. -/// -/// The trie refers to, but does not own, the Nodes that comprise it. -class FreeTrie { -public: - /// A trie node that is also a free list. Only the head node of each list is - /// actually part of the trie. The subtrie contains a continous SizeRange of - /// free lists. The lower and upper subtrie's contain the lower and upper half - /// of the subtries range. There is no direct relationship between the size of - /// this node's free list and the contents of the lower and upper subtries. - class Node : public FreeList::Node { - /// The child subtrie covering the lower half of this subtrie's size range. - /// Undefined if this is not the head of the list. - Node *lower; - /// The child subtrie covering the upper half of this subtrie's size range. - /// Undefined if this is not the head of the list. - Node *upper; - /// The parent subtrie. nullptr if this is the root or not the head of the - /// list. - Node *parent; - - friend class FreeTrie; - }; - - /// Power-of-two range of sizes covered by a subtrie. - struct SizeRange { - size_t min; - size_t width; - - LIBC_INLINE constexpr SizeRange(size_t min, size_t width) - : min(min), width(width) { - LIBC_ASSERT(!(width & (width - 1)) && "width must be a power of two"); - } - - /// @returns The lower half of the size range. - LIBC_INLINE SizeRange lower() const { return {min, width / 2}; } - - /// @returns The upper half of the size range. - LIBC_INLINE SizeRange upper() const { return {min + width / 2, width / 2}; } - - /// @returns The largest size in this range. - LIBC_INLINE size_t max() const { return min + (width - 1); } - - /// @returns Whether the range contains the given size. - LIBC_INLINE bool contains(size_t size) const { - return min <= size && size < min + width; - } - }; - - LIBC_INLINE constexpr FreeTrie() : FreeTrie(SizeRange{0, 0}) {} - LIBC_INLINE constexpr FreeTrie(SizeRange range) : range(range) {} - - /// Sets the range of possible block sizes. This can only be called when the - /// trie is empty. - LIBC_INLINE void set_range(FreeTrie::SizeRange range) { - LIBC_ASSERT(empty() && "cannot change the range of a preexisting trie"); - this->range = range; - } - - /// @returns Whether the trie contains any blocks. - LIBC_INLINE bool empty() const { return !root; } - - /// Push a block to the trie. - void push(Block<> *block); - - /// Remove a node from this trie node's free list. - void remove(Node *node); - - /// @returns A smallest node that can allocate the given size; otherwise - /// nullptr. - Node *find_best_fit(size_t size); - -private: - /// @returns Whether a node is the head of its containing freelist. - bool is_head(Node *node) const { return node->parent || node == root; } - - /// Replaces references to one node with another (or nullptr) in all adjacent - /// parent and child nodes. - void replace_node(Node *node, Node *new_node); - - Node *root = nullptr; - SizeRange range; -}; - -LIBC_INLINE void FreeTrie::push(Block<> *block) { - LIBC_ASSERT(block->inner_size_free() >= sizeof(Node) && - "block too small to accomodate free trie node"); - size_t size = block->inner_size(); - LIBC_ASSERT(range.contains(size) && "requested size out of trie range"); - - // Find the position in the tree to push to. - Node **cur = &root; - Node *parent = nullptr; - SizeRange cur_range = range; - while (*cur && (*cur)->size() != size) { - LIBC_ASSERT(cur_range.contains(size) && "requested size out of trie range"); - parent = *cur; - if (size <= cur_range.lower().max()) { - cur = &(*cur)->lower; - cur_range = cur_range.lower(); - } else { - cur = &(*cur)->upper; - cur_range = cur_range.upper(); - } - } - - Node *node = new (block->usable_space()) Node; - FreeList list = *cur; - if (list.empty()) { - node->parent = parent; - node->lower = node->upper = nullptr; - } else { - node->parent = nullptr; - } - list.push(node); - *cur = static_cast<Node *>(list.begin()); -} - -LIBC_INLINE FreeTrie::Node *FreeTrie::find_best_fit(size_t size) { - if (empty() || range.max() < size) - return nullptr; - - Node *cur = root; - SizeRange cur_range = range; - Node *best_fit = nullptr; - Node *deferred_upper_trie = nullptr; - FreeTrie::SizeRange deferred_upper_range{0, 0}; - - while (true) { - LIBC_ASSERT(cur_range.contains(cur->size()) && - "trie node size out of range"); - LIBC_ASSERT(cur_range.max() >= size && - "range could not fit requested size"); - LIBC_ASSERT((!best_fit || cur_range.min < best_fit->size()) && - "range could not contain a best fit"); - - // If the current node is an exact fit, it is a best fit. - if (cur->size() == size) - return cur; - - if (cur->size() > size && (!best_fit || cur->size() < best_fit->size())) { - // The current node is a better fit. - best_fit = cur; - - // If there is a deferred upper subtrie, then the current node is - // somewhere in its lower sibling subtrie. That means that the new best - // fit is better than the best fit in the deferred subtrie. - LIBC_ASSERT( - !deferred_upper_trie || - deferred_upper_range.min > best_fit->size() && - "deferred upper subtrie should be outclassed by new best fit"); - deferred_upper_trie = nullptr; - } - - // Determine which subtries might contain the best fit. - bool lower_impossible = !cur->lower || cur_range.lower().max() < size; - bool upper_impossible = - !cur->upper || - // If every node in the lower trie fits - (!lower_impossible && cur_range.min >= size) || - // If every node in the upper trie is worse than the current best - (best_fit && cur_range.upper().min >= best_fit->size()); - - if (lower_impossible && upper_impossible) { - if (!deferred_upper_trie) - return best_fit; - // Scan the deferred upper subtrie and consider whether any element within - // provides a better fit. - // - // This can only ever be reached once. In a deferred upper subtrie, every - // node fits, so the higher of two subtries can never contain a best fit. - cur = deferred_upper_trie; - cur_range = deferred_upper_range; - deferred_upper_trie = nullptr; - continue; - } - - if (lower_impossible) { - cur = cur->upper; - cur_range = cur_range.upper(); - } else if (upper_impossible) { - cur = cur->lower; - cur_range = cur_range.lower(); - } else { - // Both subtries might contain a better fit. Any fit in the lower subtrie - // is better than the any fit in the upper subtrie, so scan the lower - // and return to the upper only if no better fits were found. (Any better - // fit found clears the deferred upper subtrie.) - LIBC_ASSERT(!deferred_upper_trie || - cur_range.upper().max() < deferred_upper_range.min && - "old deferred upper subtrie should be outclassed by new"); - deferred_upper_trie = cur->upper; - deferred_upper_range = cur_range.upper(); - cur = cur->lower; - cur_range = cur_range.lower(); - } - } -} - -} // namespace LIBC_NAMESPACE_DECL - -#endif // LLVM_LIBC_SRC___SUPPORT_FREETRIE_H diff --git a/libc/src/stdlib/freelist_malloc.cpp b/libc/src/stdlib/freelist_malloc.cpp index fe56fad769378a..47240bc53aa37b 100644 --- a/libc/src/stdlib/freelist_malloc.cpp +++ b/libc/src/stdlib/freelist_malloc.cpp @@ -18,8 +18,8 @@ namespace LIBC_NAMESPACE_DECL { -static LIBC_CONSTINIT FreeListHeap freelist_heap_symbols; -FreeListHeap *freelist_heap = &freelist_heap_symbols; +static LIBC_CONSTINIT FreeListHeap<> freelist_heap_symbols; +FreeListHeap<> *freelist_heap = &freelist_heap_symbols; LLVM_LIBC_FUNCTION(void *, malloc, (size_t size)) { return freelist_heap->allocate(size); diff --git a/libc/test/src/__support/CMakeLists.txt b/libc/test/src/__support/CMakeLists.txt index bcc86effd9a52c..c3a7d87d8281f9 100644 --- a/libc/test/src/__support/CMakeLists.txt +++ b/libc/test/src/__support/CMakeLists.txt @@ -24,34 +24,7 @@ if(NOT LIBC_TARGET_OS_IS_GPU) DEPENDS libc.src.__support.CPP.array libc.src.__support.CPP.span - libc.src.__support.block - libc.src.__support.freelist - ) - - add_libc_test( - freetrie_test - SUITE - libc-support-tests - SRCS - freetrie_test.cpp - DEPENDS - libc.src.__support.CPP.optional - libc.src.__support.block - libc.src.__support.freetrie - ) - - add_libc_test( - freestore_test - SUITE - libc-support-tests - SRCS - freestore_test.cpp - DEPENDS - libc.src.__support.CPP.optional - libc.src.__support.block libc.src.__support.freelist - libc.src.__support.freestore - libc.src.__support.freetrie ) endif() diff --git a/libc/test/src/__support/block_test.cpp b/libc/test/src/__support/block_test.cpp index 4d23861155502a..62d7fae67bdc3d 100644 --- a/libc/test/src/__support/block_test.cpp +++ b/libc/test/src/__support/block_test.cpp @@ -238,6 +238,20 @@ TEST_FOR_EACH_BLOCK_TYPE(CannotMakeSecondBlockLargerInSplit) { ASSERT_FALSE(result.has_value()); } +TEST_FOR_EACH_BLOCK_TYPE(CannotMakeZeroSizeFirstBlock) { + // This block doesn't support splitting with zero payload size, since the + // prev_ field of the next block is always available. + constexpr size_t kN = 1024; + + alignas(BlockType::ALIGNMENT) array<byte, kN> bytes; + auto result = BlockType::init(bytes); + ASSERT_TRUE(result.has_value()); + BlockType *block = *result; + + result = block->split(0); + EXPECT_FALSE(result.has_value()); +} + TEST_FOR_EACH_BLOCK_TYPE(CanMakeMinimalSizeFirstBlock) { // This block does support splitting with minimal payload size. constexpr size_t kN = 1024; diff --git a/libc/test/src/__support/freelist_heap_test.cpp b/libc/test/src/__support/freelist_heap_test.cpp index 59ebf4e50974b7..973900dfdf56ea 100644 --- a/libc/test/src/__support/freelist_heap_test.cpp +++ b/libc/test/src/__support/freelist_heap_test.cpp @@ -13,12 +13,9 @@ #include "src/string/memcpy.h" #include "test/UnitTest/Test.h" -using LIBC_NAMESPACE::Block; +namespace LIBC_NAMESPACE_DECL { + using LIBC_NAMESPACE::freelist_heap; -using LIBC_NAMESPACE::FreeListHeap; -using LIBC_NAMESPACE::FreeListHeapBuffer; -using LIBC_NAMESPACE::cpp::byte; -using LIBC_NAMESPACE::cpp::span; // Similar to `LlvmLibcBlockTest` in block_test.cpp, we'd like to run the same // tests independently for diff erent parameters. In this case, we'd like to test @@ -31,23 +28,23 @@ using LIBC_NAMESPACE::cpp::span; // made in tests leak and aren't free'd. This is fine for the purposes of this // test file. #define TEST_FOR_EACH_ALLOCATOR(TestCase, BufferSize) \ - class LlvmLibcFreeListHeapTest##TestCase \ - : public LIBC_NAMESPACE::testing::Test { \ + class LlvmLibcFreeListHeapTest##TestCase : public testing::Test { \ public: \ FreeListHeapBuffer<BufferSize> fake_global_buffer; \ void SetUp() override { \ freelist_heap = \ new (&fake_global_buffer) FreeListHeapBuffer<BufferSize>; \ } \ - void RunTest(FreeListHeap &allocator, [[maybe_unused]] size_t N); \ + void RunTest(FreeListHeap<> &allocator, [[maybe_unused]] size_t N); \ }; \ TEST_F(LlvmLibcFreeListHeapTest##TestCase, TestCase) { \ - alignas(Block<>) byte buf[BufferSize] = {byte(0)}; \ - FreeListHeap allocator(buf); \ + alignas(FreeListHeap<>::BlockType) \ + cpp::byte buf[BufferSize] = {cpp::byte(0)}; \ + FreeListHeap<> allocator(buf); \ RunTest(allocator, BufferSize); \ RunTest(*freelist_heap, freelist_heap->region().size()); \ } \ - void LlvmLibcFreeListHeapTest##TestCase::RunTest(FreeListHeap &allocator, \ + void LlvmLibcFreeListHeapTest##TestCase::RunTest(FreeListHeap<> &allocator, \ size_t N) TEST_FOR_EACH_ALLOCATOR(CanAllocate, 2048) { @@ -95,13 +92,14 @@ TEST_FOR_EACH_ALLOCATOR(ReturnsNullWhenAllocationTooLarge, 2048) { // is used for other test cases and we don't explicitly free them. TEST(LlvmLibcFreeListHeap, ReturnsNullWhenFull) { constexpr size_t N = 2048; - alignas(Block<>) byte buf[N] = {byte(0)}; + alignas(FreeListHeap<>::BlockType) cpp::byte buf[N] = {cpp::byte(0)}; - FreeListHeap allocator(buf); + FreeListHeap<> allocator(buf); // Use aligned_allocate so we don't need to worry about ensuring the `buf` // being aligned to max_align_t. - EXPECT_NE(allocator.aligned_allocate(1, N - 2 * Block<>::BLOCK_OVERHEAD), + EXPECT_NE(allocator.aligned_allocate( + 1, N - 2 * FreeListHeap<>::BlockType::BLOCK_OVERHEAD), static_cast<void *>(nullptr)); EXPECT_EQ(allocator.allocate(1), static_cast<void *>(nullptr)); } @@ -136,9 +134,9 @@ TEST_FOR_EACH_ALLOCATOR(ReallocHasSameContent, 2048) { constexpr size_t ALLOC_SIZE = sizeof(int); constexpr size_t kNewAllocSize = sizeof(int) * 2; // Data inside the allocated block. - byte data1[ALLOC_SIZE]; + cpp::byte data1[ALLOC_SIZE]; // Data inside the reallocated block. - byte data2[ALLOC_SIZE]; + cpp::byte data2[ALLOC_SIZE]; int *ptr1 = reinterpret_cast<int *>(allocator.allocate(ALLOC_SIZE)); *ptr1 = 42; @@ -190,9 +188,10 @@ TEST_FOR_EACH_ALLOCATOR(CanCalloc, 2048) { constexpr size_t ALLOC_SIZE = 128; constexpr size_t NUM = 4; constexpr int size = NUM * ALLOC_SIZE; - constexpr byte zero{0}; + constexpr cpp::byte zero{0}; - byte *ptr1 = reinterpret_cast<byte *>(allocator.calloc(NUM, ALLOC_SIZE)); + cpp::byte *ptr1 = + reinterpret_cast<cpp::byte *>(allocator.calloc(NUM, ALLOC_SIZE)); // calloc'd content is zero. for (int i = 0; i < size; i++) { @@ -204,9 +203,10 @@ TEST_FOR_EACH_ALLOCATOR(CanCallocWeirdSize, 2048) { constexpr size_t ALLOC_SIZE = 143; constexpr size_t NUM = 3; constexpr int size = NUM * ALLOC_SIZE; - constexpr byte zero{0}; + constexpr cpp::byte zero{0}; - byte *ptr1 = reinterpret_cast<byte *>(allocator.calloc(NUM, ALLOC_SIZE)); + cpp::byte *ptr1 = + reinterpret_cast<cpp::byte *>(allocator.calloc(NUM, ALLOC_SIZE)); // calloc'd content is zero. for (int i = 0; i < size; i++) { @@ -241,16 +241,17 @@ TEST_FOR_EACH_ALLOCATOR(AlignedAlloc, 2048) { // This test is not part of the TEST_FOR_EACH_ALLOCATOR since we want to // explicitly ensure that the buffer can still return aligned allocations even -// if the underlying buffer is at most aligned to the Block<> alignment. This +// if the underlying buffer is at most aligned to the BlockType alignment. This // is so we can check that we can still get aligned allocations even if the // underlying buffer is not aligned to the alignments we request. -TEST(LlvmLibcFreeListHeap, AlignedAllocOnlyBlockAligned) { +TEST(LlvmLibcFreeListHeap, AlignedAllocOnlyBlockTypeAligned) { constexpr size_t BUFFER_SIZE = 4096; - constexpr size_t BUFFER_ALIGNMENT = alignof(Block<>) * 2; - alignas(BUFFER_ALIGNMENT) byte buf[BUFFER_SIZE] = {byte(0)}; + constexpr size_t BUFFER_ALIGNMENT = alignof(FreeListHeap<>::BlockType) * 2; + alignas(BUFFER_ALIGNMENT) cpp::byte buf[BUFFER_SIZE] = {cpp::byte(0)}; // Ensure the underlying buffer is at most aligned to the block type. - FreeListHeap allocator(span<byte>(buf).subspan(alignof(Block<>))); + FreeListHeap<> allocator( + span<cpp::byte>(buf).subspan(alignof(FreeListHeap<>::BlockType))); constexpr size_t ALIGNMENTS[] = {1, 2, 4, 8, 16, 32, 64, 128, 256}; constexpr size_t SIZE_SCALES[] = {1, 2, 3, 4, 5}; @@ -288,3 +289,5 @@ TEST_FOR_EACH_ALLOCATOR(InvalidAlignedAllocAlignment, 2048) { ptr = allocator.aligned_allocate(0, 8); EXPECT_EQ(ptr, static_cast<void *>(nullptr)); } + +} // namespace LIBC_NAMESPACE_DECL diff --git a/libc/test/src/__support/freelist_malloc_test.cpp b/libc/test/src/__support/freelist_malloc_test.cpp index 583e40d9478223..9cbdec89f6576e 100644 --- a/libc/test/src/__support/freelist_malloc_test.cpp +++ b/libc/test/src/__support/freelist_malloc_test.cpp @@ -13,7 +13,6 @@ #include "src/stdlib/malloc.h" #include "test/UnitTest/Test.h" -using LIBC_NAMESPACE::Block; using LIBC_NAMESPACE::freelist_heap; using LIBC_NAMESPACE::FreeListHeap; using LIBC_NAMESPACE::FreeListHeapBuffer; @@ -23,13 +22,15 @@ TEST(LlvmLibcFreeListMalloc, Malloc) { constexpr size_t kCallocNum = 4; constexpr size_t kCallocSize = 64; + typedef FreeListHeap<>::BlockType Block; + void *ptr1 = LIBC_NAMESPACE::malloc(kAllocSize); - auto *block = Block<>::from_usable_space(ptr1); + auto *block = Block::from_usable_space(ptr1); EXPECT_GE(block->inner_size(), kAllocSize); LIBC_NAMESPACE::free(ptr1); - ASSERT_NE(block->next(), static_cast<Block<> *>(nullptr)); - ASSERT_EQ(block->next()->next(), static_cast<Block<> *>(nullptr)); + ASSERT_NE(block->next(), static_cast<Block *>(nullptr)); + ASSERT_EQ(block->next()->next(), static_cast<Block *>(nullptr)); size_t heap_size = block->inner_size(); void *ptr2 = LIBC_NAMESPACE::calloc(kCallocNum, kCallocSize); @@ -46,7 +47,7 @@ TEST(LlvmLibcFreeListMalloc, Malloc) { void *ptr3 = LIBC_NAMESPACE::aligned_alloc(ALIGN, kAllocSize); EXPECT_NE(ptr3, static_cast<void *>(nullptr)); EXPECT_EQ(reinterpret_cast<uintptr_t>(ptr3) % ALIGN, size_t(0)); - auto *aligned_block = reinterpret_cast<Block<> *>(ptr3); + auto *aligned_block = reinterpret_cast<Block *>(ptr3); EXPECT_GE(aligned_block->inner_size(), kAllocSize); LIBC_NAMESPACE::free(ptr3); diff --git a/libc/test/src/__support/freelist_test.cpp b/libc/test/src/__support/freelist_test.cpp index f8bde941df0982..cae0ed470315c1 100644 --- a/libc/test/src/__support/freelist_test.cpp +++ b/libc/test/src/__support/freelist_test.cpp @@ -8,44 +8,159 @@ #include <stddef.h> +#include "src/__support/CPP/array.h" +#include "src/__support/CPP/span.h" #include "src/__support/freelist.h" #include "test/UnitTest/Test.h" -using LIBC_NAMESPACE::Block; using LIBC_NAMESPACE::FreeList; +using LIBC_NAMESPACE::cpp::array; using LIBC_NAMESPACE::cpp::byte; -using LIBC_NAMESPACE::cpp::optional; - -TEST(LlvmLibcFreeList, FreeList) { - byte mem1[1024]; - optional<Block<> *> maybeBlock = Block<>::init(mem1); - ASSERT_TRUE(maybeBlock.has_value()); - Block<> *block1 = *maybeBlock; - - byte mem2[1024]; - maybeBlock = Block<>::init(mem2); - ASSERT_TRUE(maybeBlock.has_value()); - Block<> *block2 = *maybeBlock; - - FreeList list; - list.push(block1); - ASSERT_FALSE(list.empty()); - EXPECT_EQ(list.front(), block1); - - list.push(block2); - EXPECT_EQ(list.front(), block1); - - list.pop(); - ASSERT_FALSE(list.empty()); - EXPECT_EQ(list.front(), block2); - - list.pop(); - ASSERT_TRUE(list.empty()); - - list.push(block1); - list.push(block2); - list.remove(reinterpret_cast<FreeList::Node *>(block2->usable_space())); - EXPECT_EQ(list.front(), block1); - list.pop(); - ASSERT_TRUE(list.empty()); +using LIBC_NAMESPACE::cpp::span; + +static constexpr size_t SIZE = 8; +static constexpr array<size_t, SIZE> example_sizes = {64, 128, 256, 512, + 1024, 2048, 4096, 8192}; + +TEST(LlvmLibcFreeList, EmptyListHasNoMembers) { + FreeList<SIZE> list(example_sizes); + + auto item = list.find_chunk(4); + EXPECT_EQ(item.size(), static_cast<size_t>(0)); + item = list.find_chunk(128); + EXPECT_EQ(item.size(), static_cast<size_t>(0)); +} + +TEST(LlvmLibcFreeList, CanRetrieveAddedMember) { + FreeList<SIZE> list(example_sizes); + constexpr size_t N = 512; + + byte data[N] = {byte(0)}; + + bool ok = list.add_chunk(span<byte>(data, N)); + EXPECT_TRUE(ok); + + auto item = list.find_chunk(N); + EXPECT_EQ(item.size(), N); + EXPECT_EQ(item.data(), data); +} + +TEST(LlvmLibcFreeList, CanRetrieveAddedMemberForSmallerSize) { + FreeList<SIZE> list(example_sizes); + constexpr size_t N = 512; + + byte data[N] = {byte(0)}; + + ASSERT_TRUE(list.add_chunk(span<byte>(data, N))); + auto item = list.find_chunk(N / 2); + EXPECT_EQ(item.size(), N); + EXPECT_EQ(item.data(), data); +} + +TEST(LlvmLibcFreeList, CanRemoveItem) { + FreeList<SIZE> list(example_sizes); + constexpr size_t N = 512; + + byte data[N] = {byte(0)}; + + ASSERT_TRUE(list.add_chunk(span<byte>(data, N))); + EXPECT_TRUE(list.remove_chunk(span<byte>(data, N))); + + auto item = list.find_chunk(N); + EXPECT_EQ(item.size(), static_cast<size_t>(0)); +} + +TEST(LlvmLibcFreeList, FindReturnsSmallestChunk) { + FreeList<SIZE> list(example_sizes); + constexpr size_t kN1 = 512; + constexpr size_t kN2 = 1024; + + byte data1[kN1] = {byte(0)}; + byte data2[kN2] = {byte(0)}; + + ASSERT_TRUE(list.add_chunk(span<byte>(data1, kN1))); + ASSERT_TRUE(list.add_chunk(span<byte>(data2, kN2))); + + auto chunk = list.find_chunk(kN1 / 2); + EXPECT_EQ(chunk.size(), kN1); + EXPECT_EQ(chunk.data(), data1); + + chunk = list.find_chunk(kN1); + EXPECT_EQ(chunk.size(), kN1); + EXPECT_EQ(chunk.data(), data1); + + chunk = list.find_chunk(kN1 + 1); + EXPECT_EQ(chunk.size(), kN2); + EXPECT_EQ(chunk.data(), data2); +} + +TEST(LlvmLibcFreeList, FindReturnsCorrectChunkInSameBucket) { + // If we have two values in the same bucket, ensure that the allocation will + // pick an appropriately sized one. + FreeList<SIZE> list(example_sizes); + constexpr size_t kN1 = 512; + constexpr size_t kN2 = 257; + + byte data1[kN1] = {byte(0)}; + byte data2[kN2] = {byte(0)}; + + // List should now be 257 -> 512 -> NULL + ASSERT_TRUE(list.add_chunk(span<byte>(data1, kN1))); + ASSERT_TRUE(list.add_chunk(span<byte>(data2, kN2))); + + auto chunk = list.find_chunk(kN2 + 1); + EXPECT_EQ(chunk.size(), kN1); +} + +TEST(LlvmLibcFreeList, FindCanMoveUpThroughBuckets) { + // Ensure that finding a chunk will move up through buckets if no appropriate + // chunks were found in a given bucket + FreeList<SIZE> list(example_sizes); + constexpr size_t kN1 = 257; + constexpr size_t kN2 = 513; + + byte data1[kN1] = {byte(0)}; + byte data2[kN2] = {byte(0)}; + + // List should now be: + // bkt[3] (257 bytes up to 512 bytes) -> 257 -> NULL + // bkt[4] (513 bytes up to 1024 bytes) -> 513 -> NULL + ASSERT_TRUE(list.add_chunk(span<byte>(data1, kN1))); + ASSERT_TRUE(list.add_chunk(span<byte>(data2, kN2))); + + // Request a 300 byte chunk. This should return the 513 byte one + auto chunk = list.find_chunk(kN1 + 1); + EXPECT_EQ(chunk.size(), kN2); +} + +TEST(LlvmLibcFreeList, RemoveUnknownChunkReturnsNotFound) { + FreeList<SIZE> list(example_sizes); + constexpr size_t N = 512; + + byte data[N] = {byte(0)}; + byte data2[N] = {byte(0)}; + + ASSERT_TRUE(list.add_chunk(span<byte>(data, N))); + EXPECT_FALSE(list.remove_chunk(span<byte>(data2, N))); +} + +TEST(LlvmLibcFreeList, CanStoreMultipleChunksPerBucket) { + FreeList<SIZE> list(example_sizes); + constexpr size_t N = 512; + + byte data1[N] = {byte(0)}; + byte data2[N] = {byte(0)}; + + ASSERT_TRUE(list.add_chunk(span<byte>(data1, N))); + ASSERT_TRUE(list.add_chunk(span<byte>(data2, N))); + + auto chunk1 = list.find_chunk(N); + ASSERT_TRUE(list.remove_chunk(chunk1)); + auto chunk2 = list.find_chunk(N); + ASSERT_TRUE(list.remove_chunk(chunk2)); + + // Ordering of the chunks doesn't matter + EXPECT_TRUE(chunk1.data() != chunk2.data()); + EXPECT_TRUE(chunk1.data() == data1 || chunk1.data() == data2); + EXPECT_TRUE(chunk2.data() == data1 || chunk2.data() == data2); } diff --git a/libc/test/src/__support/freestore_test.cpp b/libc/test/src/__support/freestore_test.cpp deleted file mode 100644 index 2ccdd7bb53979a..00000000000000 --- a/libc/test/src/__support/freestore_test.cpp +++ /dev/null @@ -1,101 +0,0 @@ -//===-- Unittests for a freestore -------------------------------*- C++ -*-===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#include <stddef.h> - -#include "src/__support/freestore.h" -#include "test/UnitTest/Test.h" - -using LIBC_NAMESPACE::Block; -using LIBC_NAMESPACE::FreeList; -using LIBC_NAMESPACE::FreeStore; -using LIBC_NAMESPACE::FreeTrie; -using LIBC_NAMESPACE::cpp::byte; -using LIBC_NAMESPACE::cpp::optional; - -// Inserting or removing blocks too small to be tracked does nothing. -TEST(LlvmLibcFreeStore, TooSmall) { - byte mem[1024]; - optional<Block<> *> maybeBlock = Block<>::init(mem); - ASSERT_TRUE(maybeBlock.has_value()); - Block<> *too_small = *maybeBlock; - maybeBlock = too_small->split(sizeof(Block<>::offset_type)); - ASSERT_TRUE(maybeBlock.has_value()); - Block<> *remainder = *maybeBlock; - - FreeStore store; - store.set_range({0, 4096}); - store.insert(too_small); - store.insert(remainder); - - EXPECT_EQ(store.remove_best_fit(too_small->inner_size()), remainder); - store.remove(too_small); -} - -TEST(LlvmLibcFreeStore, RemoveBestFit) { - byte mem[1024]; - optional<Block<> *> maybeBlock = Block<>::init(mem); - ASSERT_TRUE(maybeBlock.has_value()); - - Block<> *smallest = *maybeBlock; - maybeBlock = smallest->split(sizeof(FreeList) + sizeof(Block<>::offset_type)); - ASSERT_TRUE(maybeBlock.has_value()); - Block<> *largest_small = *maybeBlock; - maybeBlock = - largest_small->split(sizeof(FreeTrie::Node) + - sizeof(Block<>::offset_type) - alignof(max_align_t)); - ASSERT_TRUE(maybeBlock.has_value()); - ASSERT_GT(largest_small->inner_size(), smallest->inner_size()); - - Block<> *remainder = *maybeBlock; - - FreeStore store; - store.set_range({0, 4096}); - store.insert(smallest); - store.insert(largest_small); - store.insert(remainder); - - // Find exact match for smallest. - ASSERT_EQ(store.remove_best_fit(smallest->inner_size()), smallest); - store.insert(smallest); - - // Find exact match for largest. - ASSERT_EQ(store.remove_best_fit(largest_small->inner_size()), largest_small); - store.insert(largest_small); - - // Search smallest for best fit. - ASSERT_EQ(store.remove_best_fit(smallest->inner_size() + 1), largest_small); - store.insert(largest_small); - - // Continue search for best fit to large blocks. - EXPECT_EQ(store.remove_best_fit(largest_small->inner_size() + 1), remainder); -} - -TEST(LlvmLibcFreeStore, Remove) { - byte mem[1024]; - optional<Block<> *> maybeBlock = Block<>::init(mem); - ASSERT_TRUE(maybeBlock.has_value()); - - Block<> *small = *maybeBlock; - maybeBlock = small->split(sizeof(FreeList) + sizeof(Block<>::offset_type)); - ASSERT_TRUE(maybeBlock.has_value()); - - Block<> *remainder = *maybeBlock; - - FreeStore store; - store.set_range({0, 4096}); - store.insert(small); - store.insert(remainder); - - store.remove(remainder); - ASSERT_EQ(store.remove_best_fit(remainder->inner_size()), - static_cast<Block<> *>(nullptr)); - store.remove(small); - ASSERT_EQ(store.remove_best_fit(small->inner_size()), - static_cast<Block<> *>(nullptr)); -} diff --git a/libc/test/src/__support/freetrie_test.cpp b/libc/test/src/__support/freetrie_test.cpp deleted file mode 100644 index 1e3caceb7293bb..00000000000000 --- a/libc/test/src/__support/freetrie_test.cpp +++ /dev/null @@ -1,125 +0,0 @@ -//===-- Unittests for a freetrie --------------------------------*- C++ -*-===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#include <stddef.h> - -#include "src/__support/freetrie.h" -#include "test/UnitTest/Test.h" - -using LIBC_NAMESPACE::Block; -using LIBC_NAMESPACE::FreeTrie; -using LIBC_NAMESPACE::cpp::byte; -using LIBC_NAMESPACE::cpp::optional; - -TEST(LlvmLibcFreeTrie, FindBestFitRoot) { - FreeTrie trie({0, 4096}); - EXPECT_EQ(trie.find_best_fit(123), static_cast<FreeTrie::Node *>(nullptr)); - - byte mem[1024]; - optional<Block<> *> maybeBlock = Block<>::init(mem); - ASSERT_TRUE(maybeBlock.has_value()); - Block<> *block = *maybeBlock; - trie.push(block); - - FreeTrie::Node *root = trie.find_best_fit(0); - ASSERT_EQ(root->block(), block); - EXPECT_EQ(trie.find_best_fit(block->inner_size() - 1), root); - EXPECT_EQ(trie.find_best_fit(block->inner_size()), root); - EXPECT_EQ(trie.find_best_fit(block->inner_size() + 1), - static_cast<FreeTrie::Node *>(nullptr)); - EXPECT_EQ(trie.find_best_fit(4095), static_cast<FreeTrie::Node *>(nullptr)); -} - -TEST(LlvmLibcFreeTrie, FindBestFitLower) { - byte mem[4096]; - optional<Block<> *> maybeBlock = Block<>::init(mem); - ASSERT_TRUE(maybeBlock.has_value()); - Block<> *lower = *maybeBlock; - maybeBlock = lower->split(512); - ASSERT_TRUE(maybeBlock.has_value()); - Block<> *root = *maybeBlock; - - FreeTrie trie({0, 4096}); - trie.push(root); - trie.push(lower); - - EXPECT_EQ(trie.find_best_fit(0)->block(), lower); -} - -TEST(LlvmLibcFreeTrie, FindBestFitUpper) { - byte mem[4096]; - optional<Block<> *> maybeBlock = Block<>::init(mem); - ASSERT_TRUE(maybeBlock.has_value()); - Block<> *root = *maybeBlock; - maybeBlock = root->split(512); - ASSERT_TRUE(maybeBlock.has_value()); - Block<> *upper = *maybeBlock; - - FreeTrie trie({0, 4096}); - trie.push(root); - trie.push(upper); - - EXPECT_EQ(trie.find_best_fit(root->inner_size() + 1)->block(), upper); - // The upper subtrie should be skipped if it could not contain a better fit. - EXPECT_EQ(trie.find_best_fit(root->inner_size() - 1)->block(), root); -} - -TEST(LlvmLibcFreeTrie, FindBestFitLowerAndUpper) { - byte mem[4096]; - optional<Block<> *> maybeBlock = Block<>::init(mem); - ASSERT_TRUE(maybeBlock.has_value()); - Block<> *root = *maybeBlock; - maybeBlock = root->split(1024); - ASSERT_TRUE(maybeBlock.has_value()); - Block<> *lower = *maybeBlock; - maybeBlock = lower->split(128); - ASSERT_TRUE(maybeBlock.has_value()); - Block<> *upper = *maybeBlock; - - FreeTrie trie({0, 4096}); - trie.push(root); - trie.push(lower); - trie.push(upper); - - // The lower subtrie is examined first. - EXPECT_EQ(trie.find_best_fit(0)->block(), lower); - // The upper subtrie is examined if there are no fits found in the upper - // subtrie. - EXPECT_EQ(trie.find_best_fit(2048)->block(), upper); -} - -TEST(LlvmLibcFreeTrie, Remove) { - byte mem[4096]; - optional<Block<> *> maybeBlock = Block<>::init(mem); - ASSERT_TRUE(maybeBlock.has_value()); - Block<> *small1 = *maybeBlock; - maybeBlock = small1->split(512); - ASSERT_TRUE(maybeBlock.has_value()); - Block<> *small2 = *maybeBlock; - maybeBlock = small2->split(512); - ASSERT_TRUE(maybeBlock.has_value()); - ASSERT_EQ(small1->inner_size(), small2->inner_size()); - Block<> *large = *maybeBlock; - - // Removing the root empties the trie. - FreeTrie trie({0, 4096}); - trie.push(large); - FreeTrie::Node *large_node = trie.find_best_fit(0); - ASSERT_EQ(large_node->block(), large); - trie.remove(large_node); - ASSERT_TRUE(trie.empty()); - - // Removing the head of a trie list preserves the trie structure. - trie.push(small1); - trie.push(small2); - trie.push(large); - trie.remove(trie.find_best_fit(small1->inner_size())); - EXPECT_EQ(trie.find_best_fit(large->inner_size())->block(), large); - trie.remove(trie.find_best_fit(small1->inner_size())); - EXPECT_EQ(trie.find_best_fit(large->inner_size())->block(), large); -} _______________________________________________ llvm-branch-commits mailing list llvm-branch-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
