1 //===----------------------------------------------------------------------===//
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 #include "fallback_malloc.h"
10
11 #include <__threading_support>
12 #ifndef _LIBCXXABI_HAS_NO_THREADS
13 #if defined(__ELF__) && defined(_LIBCXXABI_LINK_PTHREAD_LIB)
14 #pragma comment(lib, "pthread")
15 #endif
16 #endif
17
18 #include <assert.h>
19 #include <stdlib.h> // for malloc, calloc, free
20 #include <string.h> // for memset
21 #include <new> // for std::__libcpp_aligned_{alloc,free}
22
23 // A small, simple heap manager based (loosely) on
24 // the startup heap manager from FreeBSD, optimized for space.
25 //
26 // Manages a fixed-size memory pool, supports malloc and free only.
27 // No support for realloc.
28 //
29 // Allocates chunks in multiples of four bytes, with a four byte header
30 // for each chunk. The overhead of each chunk is kept low by keeping pointers
31 // as two byte offsets within the heap, rather than (4 or 8 byte) pointers.
32
33 namespace {
34
35 // When POSIX threads are not available, make the mutex operations a nop
36 #ifndef _LIBCXXABI_HAS_NO_THREADS
37 static _LIBCPP_CONSTINIT std::__libcpp_mutex_t heap_mutex = _LIBCPP_MUTEX_INITIALIZER;
38 #else
39 static _LIBCPP_CONSTINIT void* heap_mutex = 0;
40 #endif
41
42 class mutexor {
43 public:
44 #ifndef _LIBCXXABI_HAS_NO_THREADS
mutexor(std::__libcpp_mutex_t * m)45 mutexor(std::__libcpp_mutex_t* m) : mtx_(m) {
46 std::__libcpp_mutex_lock(mtx_);
47 }
~mutexor()48 ~mutexor() { std::__libcpp_mutex_unlock(mtx_); }
49 #else
50 mutexor(void*) {}
51 ~mutexor() {}
52 #endif
53 private:
54 mutexor(const mutexor& rhs);
55 mutexor& operator=(const mutexor& rhs);
56 #ifndef _LIBCXXABI_HAS_NO_THREADS
57 std::__libcpp_mutex_t* mtx_;
58 #endif
59 };
60
61 static const size_t HEAP_SIZE = 512;
62 char heap[HEAP_SIZE] __attribute__((aligned));
63
64 typedef unsigned short heap_offset;
65 typedef unsigned short heap_size;
66
67 // On both 64 and 32 bit targets heap_node should have the following properties
68 // Size: 4
69 // Alignment: 2
70 struct heap_node {
71 heap_offset next_node; // offset into heap
72 heap_size len; // size in units of "sizeof(heap_node)"
73 };
74
75 // All pointers returned by fallback_malloc must be at least aligned
76 // as RequiredAligned. Note that RequiredAlignment can be greater than
77 // alignof(std::max_align_t) on 64 bit systems compiling 32 bit code.
78 struct FallbackMaxAlignType {
79 } __attribute__((aligned));
80 const size_t RequiredAlignment = alignof(FallbackMaxAlignType);
81
82 static_assert(alignof(FallbackMaxAlignType) % sizeof(heap_node) == 0,
83 "The required alignment must be evenly divisible by the sizeof(heap_node)");
84
85 // The number of heap_node's that can fit in a chunk of memory with the size
86 // of the RequiredAlignment. On 64 bit targets NodesPerAlignment should be 4.
87 const size_t NodesPerAlignment = alignof(FallbackMaxAlignType) / sizeof(heap_node);
88
89 static const heap_node* list_end =
90 (heap_node*)(&heap[HEAP_SIZE]); // one past the end of the heap
91 static heap_node* freelist = NULL;
92
node_from_offset(const heap_offset offset)93 heap_node* node_from_offset(const heap_offset offset) {
94 return (heap_node*)(heap + (offset * sizeof(heap_node)));
95 }
96
offset_from_node(const heap_node * ptr)97 heap_offset offset_from_node(const heap_node* ptr) {
98 return static_cast<heap_offset>(
99 static_cast<size_t>(reinterpret_cast<const char*>(ptr) - heap) /
100 sizeof(heap_node));
101 }
102
103 // Return a pointer to the first address, 'A', in `heap` that can actually be
104 // used to represent a heap_node. 'A' must be aligned so that
105 // '(A + sizeof(heap_node)) % RequiredAlignment == 0'. On 64 bit systems this
106 // address should be 12 bytes after the first 16 byte boundary.
getFirstAlignedNodeInHeap()107 heap_node* getFirstAlignedNodeInHeap() {
108 heap_node* node = (heap_node*)heap;
109 const size_t alignNBytesAfterBoundary = RequiredAlignment - sizeof(heap_node);
110 size_t boundaryOffset = reinterpret_cast<size_t>(node) % RequiredAlignment;
111 size_t requiredOffset = alignNBytesAfterBoundary - boundaryOffset;
112 size_t NElemOffset = requiredOffset / sizeof(heap_node);
113 return node + NElemOffset;
114 }
115
init_heap()116 void init_heap() {
117 freelist = getFirstAlignedNodeInHeap();
118 freelist->next_node = offset_from_node(list_end);
119 freelist->len = static_cast<heap_size>(list_end - freelist);
120 }
121
122 // How big a chunk we allocate
alloc_size(size_t len)123 size_t alloc_size(size_t len) {
124 return (len + sizeof(heap_node) - 1) / sizeof(heap_node) + 1;
125 }
126
is_fallback_ptr(void * ptr)127 bool is_fallback_ptr(void* ptr) {
128 return ptr >= heap && ptr < (heap + HEAP_SIZE);
129 }
130
fallback_malloc(size_t len)131 void* fallback_malloc(size_t len) {
132 heap_node *p, *prev;
133 const size_t nelems = alloc_size(len);
134 mutexor mtx(&heap_mutex);
135
136 if (NULL == freelist)
137 init_heap();
138
139 // Walk the free list, looking for a "big enough" chunk
140 for (p = freelist, prev = 0; p && p != list_end;
141 prev = p, p = node_from_offset(p->next_node)) {
142
143 // Check the invariant that all heap_nodes pointers 'p' are aligned
144 // so that 'p + 1' has an alignment of at least RequiredAlignment
145 assert(reinterpret_cast<size_t>(p + 1) % RequiredAlignment == 0);
146
147 // Calculate the number of extra padding elements needed in order
148 // to split 'p' and create a properly aligned heap_node from the tail
149 // of 'p'. We calculate aligned_nelems such that 'p->len - aligned_nelems'
150 // will be a multiple of NodesPerAlignment.
151 size_t aligned_nelems = nelems;
152 if (p->len > nelems) {
153 heap_size remaining_len = static_cast<heap_size>(p->len - nelems);
154 aligned_nelems += remaining_len % NodesPerAlignment;
155 }
156
157 // chunk is larger and we can create a properly aligned heap_node
158 // from the tail. In this case we shorten 'p' and return the tail.
159 if (p->len > aligned_nelems) {
160 heap_node* q;
161 p->len = static_cast<heap_size>(p->len - aligned_nelems);
162 q = p + p->len;
163 q->next_node = 0;
164 q->len = static_cast<heap_size>(aligned_nelems);
165 void* ptr = q + 1;
166 assert(reinterpret_cast<size_t>(ptr) % RequiredAlignment == 0);
167 return ptr;
168 }
169
170 // The chunk is the exact size or the chunk is larger but not large
171 // enough to split due to alignment constraints.
172 if (p->len >= nelems) {
173 if (prev == 0)
174 freelist = node_from_offset(p->next_node);
175 else
176 prev->next_node = p->next_node;
177 p->next_node = 0;
178 void* ptr = p + 1;
179 assert(reinterpret_cast<size_t>(ptr) % RequiredAlignment == 0);
180 return ptr;
181 }
182 }
183 return NULL; // couldn't find a spot big enough
184 }
185
186 // Return the start of the next block
after(struct heap_node * p)187 heap_node* after(struct heap_node* p) { return p + p->len; }
188
fallback_free(void * ptr)189 void fallback_free(void* ptr) {
190 struct heap_node* cp = ((struct heap_node*)ptr) - 1; // retrieve the chunk
191 struct heap_node *p, *prev;
192
193 mutexor mtx(&heap_mutex);
194
195 #ifdef DEBUG_FALLBACK_MALLOC
196 std::printf("Freeing item at %d of size %d\n", offset_from_node(cp), cp->len);
197 #endif
198
199 for (p = freelist, prev = 0; p && p != list_end;
200 prev = p, p = node_from_offset(p->next_node)) {
201 #ifdef DEBUG_FALLBACK_MALLOC
202 std::printf(" p=%d, cp=%d, after(p)=%d, after(cp)=%d\n",
203 offset_from_node(p), offset_from_node(cp),
204 offset_from_node(after(p)), offset_from_node(after(cp)));
205 #endif
206 if (after(p) == cp) {
207 #ifdef DEBUG_FALLBACK_MALLOC
208 std::printf(" Appending onto chunk at %d\n", offset_from_node(p));
209 #endif
210 p->len = static_cast<heap_size>(
211 p->len + cp->len); // make the free heap_node larger
212 return;
213 } else if (after(cp) == p) { // there's a free heap_node right after
214 #ifdef DEBUG_FALLBACK_MALLOC
215 std::printf(" Appending free chunk at %d\n", offset_from_node(p));
216 #endif
217 cp->len = static_cast<heap_size>(cp->len + p->len);
218 if (prev == 0) {
219 freelist = cp;
220 cp->next_node = p->next_node;
221 } else
222 prev->next_node = offset_from_node(cp);
223 return;
224 }
225 }
226 // Nothing to merge with, add it to the start of the free list
227 #ifdef DEBUG_FALLBACK_MALLOC
228 std::printf(" Making new free list entry %d\n", offset_from_node(cp));
229 #endif
230 cp->next_node = offset_from_node(freelist);
231 freelist = cp;
232 }
233
234 #ifdef INSTRUMENT_FALLBACK_MALLOC
print_free_list()235 size_t print_free_list() {
236 struct heap_node *p, *prev;
237 heap_size total_free = 0;
238 if (NULL == freelist)
239 init_heap();
240
241 for (p = freelist, prev = 0; p && p != list_end;
242 prev = p, p = node_from_offset(p->next_node)) {
243 std::printf("%sOffset: %d\tsize: %d Next: %d\n",
244 (prev == 0 ? "" : " "), offset_from_node(p), p->len, p->next_node);
245 total_free += p->len;
246 }
247 std::printf("Total Free space: %d\n", total_free);
248 return total_free;
249 }
250 #endif
251 } // end unnamed namespace
252
253 namespace __cxxabiv1 {
254
255 struct __attribute__((aligned)) __aligned_type {};
256
__aligned_malloc_with_fallback(size_t size)257 void* __aligned_malloc_with_fallback(size_t size) {
258 #if defined(_WIN32)
259 if (void* dest = std::__libcpp_aligned_alloc(alignof(__aligned_type), size))
260 return dest;
261 #elif defined(_LIBCPP_HAS_NO_LIBRARY_ALIGNED_ALLOCATION)
262 if (void* dest = ::malloc(size))
263 return dest;
264 #else
265 if (size == 0)
266 size = 1;
267 if (void* dest = std::__libcpp_aligned_alloc(__alignof(__aligned_type), size))
268 return dest;
269 #endif
270 return fallback_malloc(size);
271 }
272
__calloc_with_fallback(size_t count,size_t size)273 void* __calloc_with_fallback(size_t count, size_t size) {
274 void* ptr = ::calloc(count, size);
275 if (NULL != ptr)
276 return ptr;
277 // if calloc fails, fall back to emergency stash
278 ptr = fallback_malloc(size * count);
279 if (NULL != ptr)
280 ::memset(ptr, 0, size * count);
281 return ptr;
282 }
283
__aligned_free_with_fallback(void * ptr)284 void __aligned_free_with_fallback(void* ptr) {
285 if (is_fallback_ptr(ptr))
286 fallback_free(ptr);
287 else {
288 #if defined(_LIBCPP_HAS_NO_LIBRARY_ALIGNED_ALLOCATION)
289 ::free(ptr);
290 #else
291 std::__libcpp_aligned_free(ptr);
292 #endif
293 }
294 }
295
__free_with_fallback(void * ptr)296 void __free_with_fallback(void* ptr) {
297 if (is_fallback_ptr(ptr))
298 fallback_free(ptr);
299 else
300 ::free(ptr);
301 }
302
303 } // namespace __cxxabiv1
304