libc/src/__support/freelist.h

   1 //===-- Interface for freelist_malloc -------------------------------------===//
   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_H
  10 #define LLVM_LIBC_SRC___SUPPORT_FREELIST_H
  11
  12 #include "src/__support/CPP/array.h"
  13 #include "src/__support/CPP/cstddef.h"
  14 #include "src/__support/CPP/new.h"
  15 #include "src/__support/CPP/span.h"
  16 #include "src/__support/fixedvector.h"
  17 #include "src/__support/macros/config.h"
  18
  19 namespace LIBC_NAMESPACE_DECL {
  20
  21 using cpp::span;
  22
  23 /// Basic [freelist](https://en.wikipedia.org/wiki/Free_list) implementation
  24 /// for an allocator. This implementation buckets by chunk size, with a list
  25 /// of user-provided buckets. Each bucket is a linked list of storage chunks.
  26 /// Because this freelist uses the added chunks themselves as list nodes, there
  27 /// is a lower bound of `sizeof(FreeList.FreeListNode)` bytes for chunks which
  28 /// can be added to this freelist. There is also an implicit bucket for
  29 /// "everything else", for chunks which do not fit into a bucket.
  30 ///
  31 /// Each added chunk will be added to the smallest bucket under which it fits.
  32 /// If it does not fit into any user-provided bucket, it will be added to the
  33 /// default bucket.
  34 ///
  35 /// As an example, assume that the `FreeList` is configured with buckets of
  36 /// sizes {64, 128, 256, and 512} bytes. The internal state may look like the
  37 /// following:
  38 ///
  39 /// @code{.unparsed}
  40 /// bucket[0] (64B) --> chunk[12B] --> chunk[42B] --> chunk[64B] --> NULL
  41 /// bucket[1] (128B) --> chunk[65B] --> chunk[72B] --> NULL
  42 /// bucket[2] (256B) --> NULL
  43 /// bucket[3] (512B) --> chunk[312B] --> chunk[512B] --> chunk[416B] --> NULL
  44 /// bucket[4] (implicit) --> chunk[1024B] --> chunk[513B] --> NULL
  45 /// @endcode
  46 ///
  47 /// Note that added chunks should be aligned to a 4-byte boundary.
  48 template <size_t NUM_BUCKETS = 6> class FreeList {
  49 public:
  50   // Remove copy/move ctors
  51   FreeList(const FreeList &other) = delete;
  52   FreeList(FreeList &&other) = delete;
  53   FreeList &operator=(const FreeList &other) = delete;
  54   FreeList &operator=(FreeList &&other) = delete;
  55
  56   /// Adds a chunk to this freelist.
  57   bool add_chunk(cpp::span<cpp::byte> chunk);
  58
  59   /// Finds an eligible chunk for an allocation of size `size`.
  60   ///
  61   /// @note This returns the first allocation possible within a given bucket;
  62   /// It does not currently optimize for finding the smallest chunk.
  63   ///
  64   /// @returns
  65   /// * On success - A span representing the chunk.
  66   /// * On failure (e.g. there were no chunks available for that allocation) -
  67   ///   A span with a size of 0.
  68   cpp::span<cpp::byte> find_chunk(size_t size) const;
  69
  70   template <typename Cond> cpp::span<cpp::byte> find_chunk_if(Cond op) const;
  71
  72   /// Removes a chunk from this freelist.
  73   bool remove_chunk(cpp::span<cpp::byte> chunk);
  74
  75   /// For a given size, find which index into chunks_ the node should be written
  76   /// to.
  77   constexpr size_t find_chunk_ptr_for_size(size_t size, bool non_null) const;
  78
  79   struct FreeListNode {
  80     FreeListNode *next;
  81     size_t size;
  82   };
  83
  84   constexpr void set_freelist_node(FreeListNode &node,
  85                                    cpp::span<cpp::byte> chunk);
  86
  87   constexpr explicit FreeList(const cpp::array<size_t, NUM_BUCKETS> &sizes)
  88       : chunks_(NUM_BUCKETS + 1, 0), sizes_(sizes.begin(), sizes.end()) {}
  89
  90 private:
  91   FixedVector<FreeList::FreeListNode *, NUM_BUCKETS + 1> chunks_;
  92   FixedVector<size_t, NUM_BUCKETS> sizes_;
  93 };
  94
  95 template <size_t NUM_BUCKETS>
  96 constexpr void FreeList<NUM_BUCKETS>::set_freelist_node(FreeListNode &node,
  97                                                         span<cpp::byte> chunk) {
  98   // Add it to the correct list.
  99   size_t chunk_ptr = find_chunk_ptr_for_size(chunk.size(), false);
 100   node.size = chunk.size();
 101   node.next = chunks_[chunk_ptr];
 102   chunks_[chunk_ptr] = &node;
 103 }
 104
 105 template <size_t NUM_BUCKETS>
 106 bool FreeList<NUM_BUCKETS>::add_chunk(span<cpp::byte> chunk) {
 107   // Check that the size is enough to actually store what we need
 108   if (chunk.size() < sizeof(FreeListNode))
 109     return false;
 110
 111   FreeListNode *node = ::new (chunk.data()) FreeListNode;
 112   set_freelist_node(*node, chunk);
 113
 114   return true;
 115 }
 116
 117 template <size_t NUM_BUCKETS>
 118 template <typename Cond>
 119 span<cpp::byte> FreeList<NUM_BUCKETS>::find_chunk_if(Cond op) const {
 120   for (FreeListNode *node : chunks_) {
 121     while (node != nullptr) {
 122       span<cpp::byte> chunk(reinterpret_cast<cpp::byte *>(node), node->size);
 123       if (op(chunk))
 124         return chunk;
 125
 126       node = node->next;
 127     }
 128   }
 129
 130   return {};
 131 }
 132
 133 template <size_t NUM_BUCKETS>
 134 span<cpp::byte> FreeList<NUM_BUCKETS>::find_chunk(size_t size) const {
 135   if (size == 0)
 136     return span<cpp::byte>();
 137
 138   size_t chunk_ptr = find_chunk_ptr_for_size(size, true);
 139
 140   // Check that there's data. This catches the case where we run off the
 141   // end of the array
 142   if (chunks_[chunk_ptr] == nullptr)
 143     return span<cpp::byte>();
 144
 145   // Now iterate up the buckets, walking each list to find a good candidate
 146   for (size_t i = chunk_ptr; i < chunks_.size(); i++) {
 147     FreeListNode *node = chunks_[static_cast<unsigned short>(i)];
 148
 149     while (node != nullptr) {
 150       if (node->size >= size)
 151         return span<cpp::byte>(reinterpret_cast<cpp::byte *>(node), node->size);
 152
 153       node = node->next;
 154     }
 155   }
 156
 157   // If we get here, we've checked every block in every bucket. There's
 158   // nothing that can support this allocation.
 159   return span<cpp::byte>();
 160 }
 161
 162 template <size_t NUM_BUCKETS>
 163 bool FreeList<NUM_BUCKETS>::remove_chunk(span<cpp::byte> chunk) {
 164   size_t chunk_ptr = find_chunk_ptr_for_size(chunk.size(), true);
 165
 166   // Check head first.
 167   if (chunks_[chunk_ptr] == nullptr)
 168     return false;
 169
 170   FreeListNode *node = chunks_[chunk_ptr];
 171   if (reinterpret_cast<cpp::byte *>(node) == chunk.data()) {
 172     chunks_[chunk_ptr] = node->next;
 173     return true;
 174   }
 175
 176   // No? Walk the nodes.
 177   node = chunks_[chunk_ptr];
 178
 179   while (node->next != nullptr) {
 180     if (reinterpret_cast<cpp::byte *>(node->next) == chunk.data()) {
 181       // Found it, remove this node out of the chain
 182       node->next = node->next->next;
 183       return true;
 184     }
 185
 186     node = node->next;
 187   }
 188
 189   return false;
 190 }
 191
 192 template <size_t NUM_BUCKETS>
 193 constexpr size_t
 194 FreeList<NUM_BUCKETS>::find_chunk_ptr_for_size(size_t size,
 195                                                bool non_null) const {
 196   size_t chunk_ptr = 0;
 197   for (chunk_ptr = 0u; chunk_ptr < sizes_.size(); chunk_ptr++) {
 198     if (sizes_[chunk_ptr] >= size &&
 199         (!non_null || chunks_[chunk_ptr] != nullptr)) {
 200       break;
 201     }
 202   }
 203
 204   return chunk_ptr;
 205 }
 206
 207 } // namespace LIBC_NAMESPACE_DECL
 208
 209 #endif // LLVM_LIBC_SRC___SUPPORT_FREELIST_H