238 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef LLVM_LIBC_SRC___SUPPORT_FREETRIE_H10#define LLVM_LIBC_SRC___SUPPORT_FREETRIE_H11 12#include "freelist.h"13 14namespace 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 typically20/// required some kind of ordered map, and these are typically implemented using21/// a self-balancing binary search tree. Those are notorious for having a22/// relatively large number of special cases, while this trie has relatively23/// 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. This27/// means that the data structure would likely actually perform worse than an28/// 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 two31/// halves: a lower and an upper. The node itself holds a free list of some size32/// within its range. This makes it possible to summarily replace any node with33/// any leaf within its subtrie, which makes it very straightforward to remove a34/// node. Insertion is also simple; the only real complexity lies with finding35/// the best fit. This can still be done in logarithmic time with only a few36/// cases to consider.37///38/// The trie refers to, but does not own, the Nodes that comprise it.39class FreeTrie {40public:41 /// A trie node that is also a free list. Only the head node of each list is42 /// actually part of the trie. The subtrie contains a continous SizeRange of43 /// free lists. The lower and upper subtrie's contain the lower and upper half44 /// of the subtries range. There is no direct relationship between the size of45 /// 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 the54 /// 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 the89 /// 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; otherwise105 /// nullptr.106 Node *find_best_fit(size_t size);107 108private: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 adjacent113 /// parent and child nodes.114 void replace_node(Node *node, Node *new_node);115 116 Node *root = nullptr;117 SizeRange range;118};119 120LIBC_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 154LIBC_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 is181 // somewhere in its lower sibling subtrie. That means that the new best182 // 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 fits195 (!lower_impossible && cur_range.min >= size) ||196 // If every node in the upper trie is worse than the current best197 (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 within203 // provides a better fit.204 //205 // This can only ever be reached once. In a deferred upper subtrie, every206 // 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 subtrie221 // is better than the any fit in the upper subtrie, so scan the lower222 // and return to the upper only if no better fits were found. (Any better223 // 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_DECL236 237#endif // LLVM_LIBC_SRC___SUPPORT_FREETRIE_H238