libc/src/__support/freetrie.h

   1 //===-- Interface for freetrie --------------------------------------------===//
   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_FREETRIE_H
  10 #define LLVM_LIBC_SRC___SUPPORT_FREETRIE_H
  11
  12 #include "freelist.h"
  13
  14 namespace LIBC_NAMESPACE_DECL {
  15
  16 /// A trie of free lists.
  17 ///
  18 /// This is an unusual little data structure originally from Doug Lea's malloc.
  19 /// Finding the best fit from a set of differently-sized free list typically
  20 /// required some kind of ordered map, and these are typically implemented using
  21 /// a self-balancing binary search tree. Those are notorious for having a
  22 /// relatively large number of special cases, while this trie has relatively
  23 /// few, which helps with code size.
  24 ///
  25 /// Operations on the trie are logarithmic not on the number of nodes within it,
  26 /// but rather the fixed range of possible sizes that the trie can contain. This
  27 /// means that the data structure would likely actually perform worse than an
  28 /// e.g. red-black tree, but its implementation is still much simpler.
  29 ///
  30 /// Each trie node's children subdivide the range of possible sizes into two
  31 /// halves: a lower and an upper. The node itself holds a free list of some size
  32 /// within its range. This makes it possible to summarily replace any node with
  33 /// any leaf within its subtrie, which makes it very straightforward to remove a
  34 /// node. Insertion is also simple; the only real complexity lies with finding
  35 /// the best fit. This can still be done in logarithmic time with only a few
  36 /// cases to consider.
  37 ///
  38 /// The trie refers to, but does not own, the Nodes that comprise it.
  39 class FreeTrie {
  40 public:
  41   /// A trie node that is also a free list. Only the head node of each list is
  42   /// actually part of the trie. The subtrie contains a continous SizeRange of
  43   /// free lists. The lower and upper subtrie's contain the lower and upper half
  44   /// of the subtries range. There is no direct relationship between the size of
  45   /// this node's free list and the contents of the lower and upper subtries.
  46   class Node : public FreeList::Node {
  47     /// The child subtrie covering the lower half of this subtrie's size range.
  48     /// Undefined if this is not the head of the list.
  49     Node *lower;
  50     /// The child subtrie covering the upper half of this subtrie's size range.
  51     /// Undefined if this is not the head of the list.
  52     Node *upper;
  53     /// The parent subtrie. nullptr if this is the root or not the head of the
  54     /// list.
  55     Node *parent;
  56
  57     friend class FreeTrie;
  58   };
  59
  60   /// Power-of-two range of sizes covered by a subtrie.
  61   struct SizeRange {
  62     size_t min;
  63     size_t width;
  64
  65     LIBC_INLINE constexpr SizeRange(size_t min, size_t width)
  66         : min(min), width(width) {
  67       LIBC_ASSERT(!(width & (width - 1)) && "width must be a power of two");
  68     }
  69
  70     /// @returns The lower half of the size range.
  71     LIBC_INLINE SizeRange lower() const { return {min, width / 2}; }
  72
  73     /// @returns The upper half of the size range.
  74     LIBC_INLINE SizeRange upper() const { return {min + width / 2, width / 2}; }
  75
  76     /// @returns The largest size in this range.
  77     LIBC_INLINE size_t max() const { return min + (width - 1); }
  78
  79     /// @returns Whether the range contains the given size.
  80     LIBC_INLINE bool contains(size_t size) const {
  81       return min <= size && size < min + width;
  82     }
  83   };
  84
  85   LIBC_INLINE constexpr FreeTrie() : FreeTrie(SizeRange{0, 0}) {}
  86   LIBC_INLINE constexpr FreeTrie(SizeRange range) : range(range) {}
  87
  88   /// Sets the range of possible block sizes. This can only be called when the
  89   /// trie is empty.
  90   LIBC_INLINE void set_range(FreeTrie::SizeRange range) {
  91     LIBC_ASSERT(empty() && "cannot change the range of a preexisting trie");
  92     this->range = range;
  93   }
  94
  95   /// @returns Whether the trie contains any blocks.
  96   LIBC_INLINE bool empty() const { return !root; }
  97
  98   /// Push a block to the trie.
  99   void push(Block *block);
 100
 101   /// Remove a node from this trie node's free list.
 102   void remove(Node *node);
 103
 104   /// @returns A smallest node that can allocate the given size; otherwise
 105   /// nullptr.
 106   Node *find_best_fit(size_t size);
 107
 108 private:
 109   /// @returns Whether a node is the head of its containing freelist.
 110   bool is_head(Node *node) const { return node->parent || node == root; }
 111
 112   /// Replaces references to one node with another (or nullptr) in all adjacent
 113   /// parent and child nodes.
 114   void replace_node(Node *node, Node *new_node);
 115
 116   Node *root = nullptr;
 117   SizeRange range;
 118 };
 119
 120 LIBC_INLINE void FreeTrie::push(Block *block) {
 121   LIBC_ASSERT(block->inner_size_free() >= sizeof(Node) &&
 122               "block too small to accomodate free trie node");
 123   size_t size = block->inner_size();
 124   LIBC_ASSERT(range.contains(size) && "requested size out of trie range");
 125
 126   // Find the position in the tree to push to.
 127   Node **cur = &root;
 128   Node *parent = nullptr;
 129   SizeRange cur_range = range;
 130   while (*cur && (*cur)->size() != size) {
 131     LIBC_ASSERT(cur_range.contains(size) && "requested size out of trie range");
 132     parent = *cur;
 133     if (size <= cur_range.lower().max()) {
 134       cur = &(*cur)->lower;
 135       cur_range = cur_range.lower();
 136     } else {
 137       cur = &(*cur)->upper;
 138       cur_range = cur_range.upper();
 139     }
 140   }
 141
 142   Node *node = new (block->usable_space()) Node;
 143   FreeList list = *cur;
 144   if (list.empty()) {
 145     node->parent = parent;
 146     node->lower = node->upper = nullptr;
 147   } else {
 148     node->parent = nullptr;
 149   }
 150   list.push(node);
 151   *cur = static_cast<Node *>(list.begin());
 152 }
 153
 154 LIBC_INLINE FreeTrie::Node *FreeTrie::find_best_fit(size_t size) {
 155   if (empty() || range.max() < size)
 156     return nullptr;
 157
 158   Node *cur = root;
 159   SizeRange cur_range = range;
 160   Node *best_fit = nullptr;
 161   Node *deferred_upper_trie = nullptr;
 162   FreeTrie::SizeRange deferred_upper_range{0, 0};
 163
 164   while (true) {
 165     LIBC_ASSERT(cur_range.contains(cur->size()) &&
 166                 "trie node size out of range");
 167     LIBC_ASSERT(cur_range.max() >= size &&
 168                 "range could not fit requested size");
 169     LIBC_ASSERT((!best_fit || cur_range.min < best_fit->size()) &&
 170                 "range could not contain a best fit");
 171
 172     // If the current node is an exact fit, it is a best fit.
 173     if (cur->size() == size)
 174       return cur;
 175
 176     if (cur->size() > size && (!best_fit || cur->size() < best_fit->size())) {
 177       // The current node is a better fit.
 178       best_fit = cur;
 179
 180       // If there is a deferred upper subtrie, then the current node is
 181       // somewhere in its lower sibling subtrie. That means that the new best
 182       // fit is better than the best fit in the deferred subtrie.
 183       LIBC_ASSERT(
 184           (!deferred_upper_trie ||
 185            deferred_upper_range.min > best_fit->size()) &&
 186           "deferred upper subtrie should be outclassed by new best fit");
 187       deferred_upper_trie = nullptr;
 188     }
 189
 190     // Determine which subtries might contain the best fit.
 191     bool lower_impossible = !cur->lower || cur_range.lower().max() < size;
 192     bool upper_impossible =
 193         !cur->upper ||
 194         // If every node in the lower trie fits
 195         (!lower_impossible && cur_range.min >= size) ||
 196         // If every node in the upper trie is worse than the current best
 197         (best_fit && cur_range.upper().min >= best_fit->size());
 198
 199     if (lower_impossible && upper_impossible) {
 200       if (!deferred_upper_trie)
 201         return best_fit;
 202       // Scan the deferred upper subtrie and consider whether any element within
 203       // provides a better fit.
 204       //
 205       // This can only ever be reached once. In a deferred upper subtrie, every
 206       // node fits, so the higher of two subtries can never contain a best fit.
 207       cur = deferred_upper_trie;
 208       cur_range = deferred_upper_range;
 209       deferred_upper_trie = nullptr;
 210       continue;
 211     }
 212
 213     if (lower_impossible) {
 214       cur = cur->upper;
 215       cur_range = cur_range.upper();
 216     } else if (upper_impossible) {
 217       cur = cur->lower;
 218       cur_range = cur_range.lower();
 219     } else {
 220       // Both subtries might contain a better fit. Any fit in the lower subtrie
 221       // is better than the any fit in the upper subtrie, so scan the lower
 222       // and return to the upper only if no better fits were found. (Any better
 223       // fit found clears the deferred upper subtrie.)
 224       LIBC_ASSERT((!deferred_upper_trie ||
 225                    cur_range.upper().max() < deferred_upper_range.min) &&
 226                   "old deferred upper subtrie should be outclassed by new");
 227       deferred_upper_trie = cur->upper;
 228       deferred_upper_range = cur_range.upper();
 229       cur = cur->lower;
 230       cur_range = cur_range.lower();
 231     }
 232   }
 233 }
 234
 235 } // namespace LIBC_NAMESPACE_DECL
 236
 237 #endif // LLVM_LIBC_SRC___SUPPORT_FREETRIE_H