1 //===-- Interface for freelist_heap ---------------------------------------===//
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_HEAP_H
10 #define LLVM_LIBC_SRC___SUPPORT_FREELIST_HEAP_H
11
12 #include <stddef.h>
13
14 #include "block.h"
15 #include "freestore.h"
16 #include "src/__support/CPP/optional.h"
17 #include "src/__support/CPP/span.h"
18 #include "src/__support/libc_assert.h"
19 #include "src/__support/macros/config.h"
20 #include "src/__support/math_extras.h"
21 #include "src/string/memory_utils/inline_memcpy.h"
22 #include "src/string/memory_utils/inline_memset.h"
23
24 namespace LIBC_NAMESPACE_DECL {
25
26 extern "C" cpp::byte _end;
27 extern "C" cpp::byte __llvm_libc_heap_limit;
28
29 using cpp::optional;
30 using cpp::span;
31
IsPow2(size_t x)32 LIBC_INLINE constexpr bool IsPow2(size_t x) { return x && (x & (x - 1)) == 0; }
33
34 class FreeListHeap {
35 public:
FreeListHeap()36 constexpr FreeListHeap() : begin(&_end), end(&__llvm_libc_heap_limit) {}
37
FreeListHeap(span<cpp::byte> region)38 constexpr FreeListHeap(span<cpp::byte> region)
39 : begin(region.begin()), end(region.end()) {}
40
41 void *allocate(size_t size);
42 void *aligned_allocate(size_t alignment, size_t size);
43 // NOTE: All pointers passed to free must come from one of the other
44 // allocation functions: `allocate`, `aligned_allocate`, `realloc`, `calloc`.
45 void free(void *ptr);
46 void *realloc(void *ptr, size_t size);
47 void *calloc(size_t num, size_t size);
48
region()49 cpp::span<cpp::byte> region() const { return {begin, end}; }
50
51 private:
52 void init();
53
54 void *allocate_impl(size_t alignment, size_t size);
55
block_to_span(Block * block)56 span<cpp::byte> block_to_span(Block *block) {
57 return span<cpp::byte>(block->usable_space(), block->inner_size());
58 }
59
is_valid_ptr(void * ptr)60 bool is_valid_ptr(void *ptr) { return ptr >= begin && ptr < end; }
61
62 cpp::byte *begin;
63 cpp::byte *end;
64 bool is_initialized = false;
65 FreeStore free_store;
66 };
67
68 template <size_t BUFF_SIZE> class FreeListHeapBuffer : public FreeListHeap {
69 public:
FreeListHeapBuffer()70 constexpr FreeListHeapBuffer() : FreeListHeap{buffer}, buffer{} {}
71
72 private:
73 cpp::byte buffer[BUFF_SIZE];
74 };
75
init()76 LIBC_INLINE void FreeListHeap::init() {
77 LIBC_ASSERT(!is_initialized && "duplicate initialization");
78 auto result = Block::init(region());
79 Block *block = *result;
80 free_store.set_range({0, cpp::bit_ceil(block->inner_size())});
81 free_store.insert(block);
82 is_initialized = true;
83 }
84
allocate_impl(size_t alignment,size_t size)85 LIBC_INLINE void *FreeListHeap::allocate_impl(size_t alignment, size_t size) {
86 if (size == 0)
87 return nullptr;
88
89 if (!is_initialized)
90 init();
91
92 size_t request_size = size;
93
94 // TODO: usable_space should always be aligned to max_align_t.
95 if (alignment > alignof(max_align_t) ||
96 (Block::BLOCK_OVERHEAD % alignof(max_align_t) != 0)) {
97 // TODO: This bound isn't precisely calculated yet. It assumes one extra
98 // Block::ALIGNMENT to accomodate the possibility for padding block
99 // overhead. (alignment - 1) ensures that there is an aligned point
100 // somewhere in usable_space, but this isn't tight either, since
101 // usable_space is also already somewhat aligned.
102 if (add_overflow(size, (alignment - 1) + Block::ALIGNMENT, request_size))
103 return nullptr;
104 }
105
106 Block *block = free_store.remove_best_fit(request_size);
107 if (!block)
108 return nullptr;
109
110 LIBC_ASSERT(block->can_allocate(alignment, size) &&
111 "block should always be large enough to allocate at the correct "
112 "alignment");
113
114 auto block_info = Block::allocate(block, alignment, size);
115 if (block_info.next)
116 free_store.insert(block_info.next);
117 if (block_info.prev)
118 free_store.insert(block_info.prev);
119
120 block_info.block->mark_used();
121 return block_info.block->usable_space();
122 }
123
allocate(size_t size)124 LIBC_INLINE void *FreeListHeap::allocate(size_t size) {
125 return allocate_impl(alignof(max_align_t), size);
126 }
127
aligned_allocate(size_t alignment,size_t size)128 LIBC_INLINE void *FreeListHeap::aligned_allocate(size_t alignment,
129 size_t size) {
130 // The alignment must be an integral power of two.
131 if (!IsPow2(alignment))
132 return nullptr;
133
134 // The size parameter must be an integral multiple of alignment.
135 if (size % alignment != 0)
136 return nullptr;
137
138 return allocate_impl(alignment, size);
139 }
140
free(void * ptr)141 LIBC_INLINE void FreeListHeap::free(void *ptr) {
142 cpp::byte *bytes = static_cast<cpp::byte *>(ptr);
143
144 LIBC_ASSERT(is_valid_ptr(bytes) && "Invalid pointer");
145
146 Block *block = Block::from_usable_space(bytes);
147 LIBC_ASSERT(block->next() && "sentinel last block cannot be freed");
148 LIBC_ASSERT(block->used() && "double free");
149 block->mark_free();
150
151 // Can we combine with the left or right blocks?
152 Block *prev_free = block->prev_free();
153 Block *next = block->next();
154
155 if (prev_free != nullptr) {
156 // Remove from free store and merge.
157 free_store.remove(prev_free);
158 block = prev_free;
159 block->merge_next();
160 }
161 if (!next->used()) {
162 free_store.remove(next);
163 block->merge_next();
164 }
165 // Add back to the freelist
166 free_store.insert(block);
167 }
168
169 // Follows constract of the C standard realloc() function
170 // If ptr is free'd, will return nullptr.
realloc(void * ptr,size_t size)171 LIBC_INLINE void *FreeListHeap::realloc(void *ptr, size_t size) {
172 if (size == 0) {
173 free(ptr);
174 return nullptr;
175 }
176
177 // If the pointer is nullptr, allocate a new memory.
178 if (ptr == nullptr)
179 return allocate(size);
180
181 cpp::byte *bytes = static_cast<cpp::byte *>(ptr);
182
183 if (!is_valid_ptr(bytes))
184 return nullptr;
185
186 Block *block = Block::from_usable_space(bytes);
187 if (!block->used())
188 return nullptr;
189 size_t old_size = block->inner_size();
190
191 // Do nothing and return ptr if the required memory size is smaller than
192 // the current size.
193 if (old_size >= size)
194 return ptr;
195
196 void *new_ptr = allocate(size);
197 // Don't invalidate ptr if allocate(size) fails to initilize the memory.
198 if (new_ptr == nullptr)
199 return nullptr;
200 LIBC_NAMESPACE::inline_memcpy(new_ptr, ptr, old_size);
201
202 free(ptr);
203 return new_ptr;
204 }
205
calloc(size_t num,size_t size)206 LIBC_INLINE void *FreeListHeap::calloc(size_t num, size_t size) {
207 size_t bytes;
208 if (__builtin_mul_overflow(num, size, &bytes))
209 return nullptr;
210 void *ptr = allocate(bytes);
211 if (ptr != nullptr)
212 LIBC_NAMESPACE::inline_memset(ptr, 0, bytes);
213 return ptr;
214 }
215
216 extern FreeListHeap *freelist_heap;
217
218 } // namespace LIBC_NAMESPACE_DECL
219
220 #endif // LLVM_LIBC_SRC___SUPPORT_FREELIST_HEAP_H
221