libc/src/__support/freelist_heap.h

   1 //===-- Interface for freelist_heap ---------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #ifndef LLVM_LIBC_SRC___SUPPORT_FREELIST_HEAP_H
  10 #define LLVM_LIBC_SRC___SUPPORT_FREELIST_HEAP_H
  11
  12 #include <stddef.h>
  13
  14 #include "block.h"
  15 #include "freelist.h"
  16 #include "src/__support/CPP/optional.h"
  17 #include "src/__support/CPP/span.h"
  18 #include "src/__support/libc_assert.h"
  19 #include "src/__support/macros/config.h"
  20 #include "src/string/memory_utils/inline_memcpy.h"
  21 #include "src/string/memory_utils/inline_memset.h"
  22
  23 namespace LIBC_NAMESPACE_DECL {
  24
  25 extern "C" cpp::byte _end;
  26 extern "C" cpp::byte __llvm_libc_heap_limit;
  27
  28 using cpp::optional;
  29 using cpp::span;
  30
  31 inline constexpr bool IsPow2(size_t x) { return x && (x & (x - 1)) == 0; }
  32
  33 static constexpr cpp::array<size_t, 6> DEFAULT_BUCKETS{16,  32,  64,
  34                                                        128, 256, 512};
  35
  36 template <size_t NUM_BUCKETS = DEFAULT_BUCKETS.size()> class FreeListHeap {
  37 public:
  38   using BlockType = Block<>;
  39   using FreeListType = FreeList<NUM_BUCKETS>;
  40
  41   static constexpr size_t MIN_ALIGNMENT =
  42       cpp::max(BlockType::ALIGNMENT, alignof(max_align_t));
  43
  44   constexpr FreeListHeap() : begin_(&_end), end_(&__llvm_libc_heap_limit) {}
  45
  46   constexpr FreeListHeap(span<cpp::byte> region)
  47       : begin_(region.begin()), end_(region.end()) {}
  48
  49   void *allocate(size_t size);
  50   void *aligned_allocate(size_t alignment, size_t size);
  51   // NOTE: All pointers passed to free must come from one of the other
  52   // allocation functions: `allocate`, `aligned_allocate`, `realloc`, `calloc`.
  53   void free(void *ptr);
  54   void *realloc(void *ptr, size_t size);
  55   void *calloc(size_t num, size_t size);
  56
  57   cpp::span<cpp::byte> region() const { return {begin_, end_}; }
  58
  59 private:
  60   void init();
  61
  62   void *allocate_impl(size_t alignment, size_t size);
  63
  64   span<cpp::byte> block_to_span(BlockType *block) {
  65     return span<cpp::byte>(block->usable_space(), block->inner_size());
  66   }
  67
  68   bool is_valid_ptr(void *ptr) { return ptr >= begin_ && ptr < end_; }
  69
  70   bool is_initialized_ = false;
  71   cpp::byte *begin_;
  72   cpp::byte *end_;
  73   FreeListType freelist_{DEFAULT_BUCKETS};
  74 };
  75
  76 template <size_t BUFF_SIZE, size_t NUM_BUCKETS = DEFAULT_BUCKETS.size()>
  77 class FreeListHeapBuffer : public FreeListHeap<NUM_BUCKETS> {
  78   using parent = FreeListHeap<NUM_BUCKETS>;
  79   using FreeListNode = typename parent::FreeListType::FreeListNode;
  80
  81 public:
  82   constexpr FreeListHeapBuffer()
  83       : FreeListHeap<NUM_BUCKETS>{buffer}, buffer{} {}
  84
  85 private:
  86   cpp::byte buffer[BUFF_SIZE];
  87 };
  88
  89 template <size_t NUM_BUCKETS> void FreeListHeap<NUM_BUCKETS>::init() {
  90   LIBC_ASSERT(!is_initialized_ && "duplicate initialization");
  91   auto result = BlockType::init(region());
  92   BlockType *block = *result;
  93   freelist_.add_chunk(block_to_span(block));
  94   is_initialized_ = true;
  95 }
  96
  97 template <size_t NUM_BUCKETS>
  98 void *FreeListHeap<NUM_BUCKETS>::allocate_impl(size_t alignment, size_t size) {
  99   if (size == 0)
 100     return nullptr;
 101
 102   if (!is_initialized_)
 103     init();
 104
 105   // Find a chunk in the freelist. Split it if needed, then return.
 106   auto chunk =
 107       freelist_.find_chunk_if([alignment, size](span<cpp::byte> chunk) {
 108         BlockType *block = BlockType::from_usable_space(chunk.data());
 109         return block->can_allocate(alignment, size);
 110       });
 111
 112   if (chunk.data() == nullptr)
 113     return nullptr;
 114   freelist_.remove_chunk(chunk);
 115
 116   BlockType *chunk_block = BlockType::from_usable_space(chunk.data());
 117   LIBC_ASSERT(!chunk_block->used());
 118
 119   // Split that chunk. If there's a leftover chunk, add it to the freelist
 120   auto block_info = BlockType::allocate(chunk_block, alignment, size);
 121   if (block_info.next)
 122     freelist_.add_chunk(block_to_span(block_info.next));
 123   if (block_info.prev)
 124     freelist_.add_chunk(block_to_span(block_info.prev));
 125   chunk_block = block_info.block;
 126
 127   chunk_block->mark_used();
 128
 129   return chunk_block->usable_space();
 130 }
 131
 132 template <size_t NUM_BUCKETS>
 133 void *FreeListHeap<NUM_BUCKETS>::allocate(size_t size) {
 134   return allocate_impl(MIN_ALIGNMENT, size);
 135 }
 136
 137 template <size_t NUM_BUCKETS>
 138 void *FreeListHeap<NUM_BUCKETS>::aligned_allocate(size_t alignment,
 139                                                   size_t size) {
 140   // The alignment must be an integral power of two.
 141   if (!IsPow2(alignment))
 142     return nullptr;
 143
 144   // The size parameter must be an integral multiple of alignment.
 145   if (size % alignment != 0)
 146     return nullptr;
 147
 148   return allocate_impl(alignment, size);
 149 }
 150
 151 template <size_t NUM_BUCKETS> void FreeListHeap<NUM_BUCKETS>::free(void *ptr) {
 152   cpp::byte *bytes = static_cast<cpp::byte *>(ptr);
 153
 154   LIBC_ASSERT(is_valid_ptr(bytes) && "Invalid pointer");
 155
 156   BlockType *chunk_block = BlockType::from_usable_space(bytes);
 157   LIBC_ASSERT(chunk_block->next() && "sentinel last block cannot be freed");
 158   LIBC_ASSERT(chunk_block->used() && "The block is not in-use");
 159   chunk_block->mark_free();
 160
 161   // Can we combine with the left or right blocks?
 162   BlockType *prev_free = chunk_block->prev_free();
 163   BlockType *next = chunk_block->next();
 164
 165   if (prev_free != nullptr) {
 166     // Remove from freelist and merge
 167     freelist_.remove_chunk(block_to_span(prev_free));
 168     chunk_block = prev_free;
 169     chunk_block->merge_next();
 170   }
 171   if (!next->used()) {
 172     freelist_.remove_chunk(block_to_span(next));
 173     chunk_block->merge_next();
 174   }
 175   // Add back to the freelist
 176   freelist_.add_chunk(block_to_span(chunk_block));
 177 }
 178
 179 // Follows constract of the C standard realloc() function
 180 // If ptr is free'd, will return nullptr.
 181 template <size_t NUM_BUCKETS>
 182 void *FreeListHeap<NUM_BUCKETS>::realloc(void *ptr, size_t size) {
 183   if (size == 0) {
 184     free(ptr);
 185     return nullptr;
 186   }
 187
 188   // If the pointer is nullptr, allocate a new memory.
 189   if (ptr == nullptr)
 190     return allocate(size);
 191
 192   cpp::byte *bytes = static_cast<cpp::byte *>(ptr);
 193
 194   if (!is_valid_ptr(bytes))
 195     return nullptr;
 196
 197   BlockType *chunk_block = BlockType::from_usable_space(bytes);
 198   if (!chunk_block->used())
 199     return nullptr;
 200   size_t old_size = chunk_block->inner_size();
 201
 202   // Do nothing and return ptr if the required memory size is smaller than
 203   // the current size.
 204   if (old_size >= size)
 205     return ptr;
 206
 207   void *new_ptr = allocate(size);
 208   // Don't invalidate ptr if allocate(size) fails to initilize the memory.
 209   if (new_ptr == nullptr)
 210     return nullptr;
 211   LIBC_NAMESPACE::inline_memcpy(new_ptr, ptr, old_size);
 212
 213   free(ptr);
 214   return new_ptr;
 215 }
 216
 217 template <size_t NUM_BUCKETS>
 218 void *FreeListHeap<NUM_BUCKETS>::calloc(size_t num, size_t size) {
 219   void *ptr = allocate(num * size);
 220   if (ptr != nullptr)
 221     LIBC_NAMESPACE::inline_memset(ptr, 0, num * size);
 222   return ptr;
 223 }
 224
 225 extern FreeListHeap<> *freelist_heap;
 226
 227 } // namespace LIBC_NAMESPACE_DECL
 228
 229 #endif // LLVM_LIBC_SRC___SUPPORT_FREELIST_HEAP_H