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. set_range(FreeTrie::SizeRange range)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 ALIGNMENT = alignof(max_align_t); 44 static constexpr size_t MIN_OUTER_SIZE = 45 align_up(Block::BLOCK_OVERHEAD + sizeof(FreeList::Node), ALIGNMENT); 46 static constexpr size_t MIN_LARGE_OUTER_SIZE = 47 align_up(Block::BLOCK_OVERHEAD + sizeof(FreeTrie::Node), ALIGNMENT); 48 static constexpr size_t NUM_SMALL_SIZES = 49 (MIN_LARGE_OUTER_SIZE - MIN_OUTER_SIZE) / ALIGNMENT; 50 too_small(Block * block)51 LIBC_INLINE static bool too_small(Block *block) { 52 return block->outer_size() < MIN_OUTER_SIZE; 53 } is_small(Block * block)54 LIBC_INLINE static bool is_small(Block *block) { 55 return block->outer_size() < MIN_LARGE_OUTER_SIZE; 56 } 57 58 FreeList &small_list(Block *block); 59 FreeList *find_best_small_fit(size_t size); 60 61 cpp::array<FreeList, NUM_SMALL_SIZES> small_lists; 62 FreeTrie large_trie; 63 }; 64 insert(Block * block)65LIBC_INLINE void FreeStore::insert(Block *block) { 66 if (too_small(block)) 67 return; 68 if (is_small(block)) 69 small_list(block).push(block); 70 else 71 large_trie.push(block); 72 } 73 remove(Block * block)74LIBC_INLINE void FreeStore::remove(Block *block) { 75 if (too_small(block)) 76 return; 77 if (is_small(block)) { 78 small_list(block).remove( 79 reinterpret_cast<FreeList::Node *>(block->usable_space())); 80 } else { 81 large_trie.remove( 82 reinterpret_cast<FreeTrie::Node *>(block->usable_space())); 83 } 84 } 85 remove_best_fit(size_t size)86LIBC_INLINE Block *FreeStore::remove_best_fit(size_t size) { 87 if (FreeList *list = find_best_small_fit(size)) { 88 Block *block = list->front(); 89 list->pop(); 90 return block; 91 } 92 if (FreeTrie::Node *best_fit = large_trie.find_best_fit(size)) { 93 Block *block = best_fit->block(); 94 large_trie.remove(best_fit); 95 return block; 96 } 97 return nullptr; 98 } 99 small_list(Block * block)100LIBC_INLINE FreeList &FreeStore::small_list(Block *block) { 101 LIBC_ASSERT(is_small(block) && "only legal for small blocks"); 102 return small_lists[(block->outer_size() - MIN_OUTER_SIZE) / ALIGNMENT]; 103 } 104 find_best_small_fit(size_t size)105LIBC_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