1 //===-- Interface for freestore ------------------------------------------===// 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_FREESTORE_H 10 #define LLVM_LIBC_SRC___SUPPORT_FREESTORE_H 11 12 #include "freetrie.h" 13 14 namespace LIBC_NAMESPACE_DECL { 15 16 /// A best-fit store of variously-sized free blocks. Blocks can be inserted and 17 /// removed in logarithmic time. 18 class FreeStore { 19 public: 20 FreeStore() = default; 21 FreeStore(const FreeStore &other) = delete; 22 FreeStore &operator=(const FreeStore &other) = delete; 23 24 /// Sets the range of possible block sizes. This can only be called when the 25 /// trie is empty. 26 LIBC_INLINE void set_range(FreeTrie::SizeRange range) { 27 large_trie.set_range(range); 28 } 29 30 /// Insert a free block. If the block is too small to be tracked, nothing 31 /// happens. 32 void insert(Block *block); 33 34 /// Remove a free block. If the block is too small to be tracked, nothing 35 /// happens. 36 void remove(Block *block); 37 38 /// Remove a best-fit free block that can contain the given size when 39 /// allocated. Returns nullptr if there is no such block. 40 Block *remove_best_fit(size_t size); 41 42 private: 43 static constexpr size_t MIN_OUTER_SIZE = 44 align_up(sizeof(Block) + sizeof(FreeList::Node), alignof(max_align_t)); 45 static constexpr size_t MIN_LARGE_OUTER_SIZE = 46 align_up(sizeof(Block) + sizeof(FreeTrie::Node), alignof(max_align_t)); 47 static constexpr size_t NUM_SMALL_SIZES = 48 (MIN_LARGE_OUTER_SIZE - MIN_OUTER_SIZE) / alignof(max_align_t); 49 50 LIBC_INLINE static bool too_small(Block *block) { 51 return block->outer_size() < MIN_OUTER_SIZE; 52 } 53 LIBC_INLINE static bool is_small(Block *block) { 54 return block->outer_size() < MIN_LARGE_OUTER_SIZE; 55 } 56 57 FreeList &small_list(Block *block); 58 FreeList *find_best_small_fit(size_t size); 59 60 cpp::array<FreeList, NUM_SMALL_SIZES> small_lists; 61 FreeTrie large_trie; 62 }; 63 64 LIBC_INLINE void FreeStore::insert(Block *block) { 65 if (too_small(block)) 66 return; 67 if (is_small(block)) 68 small_list(block).push(block); 69 else 70 large_trie.push(block); 71 } 72 73 LIBC_INLINE void FreeStore::remove(Block *block) { 74 if (too_small(block)) 75 return; 76 if (is_small(block)) { 77 small_list(block).remove( 78 reinterpret_cast<FreeList::Node *>(block->usable_space())); 79 } else { 80 large_trie.remove( 81 reinterpret_cast<FreeTrie::Node *>(block->usable_space())); 82 } 83 } 84 85 LIBC_INLINE Block *FreeStore::remove_best_fit(size_t size) { 86 if (FreeList *list = find_best_small_fit(size)) { 87 Block *block = list->front(); 88 list->pop(); 89 return block; 90 } 91 if (FreeTrie::Node *best_fit = large_trie.find_best_fit(size)) { 92 Block *block = best_fit->block(); 93 large_trie.remove(best_fit); 94 return block; 95 } 96 return nullptr; 97 } 98 99 LIBC_INLINE FreeList &FreeStore::small_list(Block *block) { 100 LIBC_ASSERT(is_small(block) && "only legal for small blocks"); 101 return small_lists[(block->outer_size() - MIN_OUTER_SIZE) / 102 alignof(max_align_t)]; 103 } 104 105 LIBC_INLINE FreeList *FreeStore::find_best_small_fit(size_t size) { 106 for (FreeList &list : small_lists) 107 if (!list.empty() && list.size() >= size) 108 return &list; 109 return nullptr; 110 } 111 112 } // namespace LIBC_NAMESPACE_DECL 113 114 #endif // LLVM_LIBC_SRC___SUPPORT_FREESTORE_H 115