fallback_malloc.cpp
1 //===------------------------ fallback_malloc.cpp -------------------------===// 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 <stdlib.h> // for malloc, calloc, free 19 #include <string.h> // for memset 20 #include <new> // for std::__libcpp_aligned_{alloc,free} 21 22 // A small, simple heap manager based (loosely) on 23 // the startup heap manager from FreeBSD, optimized for space. 24 // 25 // Manages a fixed-size memory pool, supports malloc and free only. 26 // No support for realloc. 27 // 28 // Allocates chunks in multiples of four bytes, with a four byte header 29 // for each chunk. The overhead of each chunk is kept low by keeping pointers 30 // as two byte offsets within the heap, rather than (4 or 8 byte) pointers. 31 32 namespace { 33 34 // When POSIX threads are not available, make the mutex operations a nop 35 #ifndef _LIBCXXABI_HAS_NO_THREADS 36 _LIBCPP_SAFE_STATIC 37 static std::__libcpp_mutex_t heap_mutex = _LIBCPP_MUTEX_INITIALIZER; 38 #else 39 static void* heap_mutex = 0; 40 #endif 41 42 class mutexor { 43 public: 44 #ifndef _LIBCXXABI_HAS_NO_THREADS 45 mutexor(std::__libcpp_mutex_t* m) : mtx_(m) { 46 std::__libcpp_mutex_lock(mtx_); 47 } 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 struct heap_node { 68 heap_offset next_node; // offset into heap 69 heap_size len; // size in units of "sizeof(heap_node)" 70 }; 71 72 static const heap_node* list_end = 73 (heap_node*)(&heap[HEAP_SIZE]); // one past the end of the heap 74 static heap_node* freelist = NULL; 75 76 heap_node* node_from_offset(const heap_offset offset) { 77 return (heap_node*)(heap + (offset * sizeof(heap_node))); 78 } 79 80 heap_offset offset_from_node(const heap_node* ptr) { 81 return static_cast<heap_offset>( 82 static_cast<size_t>(reinterpret_cast<const char*>(ptr) - heap) / 83 sizeof(heap_node)); 84 } 85 86 void init_heap() { 87 freelist = (heap_node*)heap; 88 freelist->next_node = offset_from_node(list_end); 89 freelist->len = HEAP_SIZE / sizeof(heap_node); 90 } 91 92 // How big a chunk we allocate 93 size_t alloc_size(size_t len) { 94 return (len + sizeof(heap_node) - 1) / sizeof(heap_node) + 1; 95 } 96 97 bool is_fallback_ptr(void* ptr) { 98 return ptr >= heap && ptr < (heap + HEAP_SIZE); 99 } 100 101 void* fallback_malloc(size_t len) { 102 heap_node *p, *prev; 103 const size_t nelems = alloc_size(len); 104 mutexor mtx(&heap_mutex); 105 106 if (NULL == freelist) 107 init_heap(); 108 109 // Walk the free list, looking for a "big enough" chunk 110 for (p = freelist, prev = 0; p && p != list_end; 111 prev = p, p = node_from_offset(p->next_node)) { 112 113 if (p->len > nelems) { // chunk is larger, shorten, and return the tail 114 heap_node* q; 115 116 p->len = static_cast<heap_size>(p->len - nelems); 117 q = p + p->len; 118 q->next_node = 0; 119 q->len = static_cast<heap_size>(nelems); 120 return (void*)(q + 1); 121 } 122 123 if (p->len == nelems) { // exact size match 124 if (prev == 0) 125 freelist = node_from_offset(p->next_node); 126 else 127 prev->next_node = p->next_node; 128 p->next_node = 0; 129 return (void*)(p + 1); 130 } 131 } 132 return NULL; // couldn't find a spot big enough 133 } 134 135 // Return the start of the next block 136 heap_node* after(struct heap_node* p) { return p + p->len; } 137 138 void fallback_free(void* ptr) { 139 struct heap_node* cp = ((struct heap_node*)ptr) - 1; // retrieve the chunk 140 struct heap_node *p, *prev; 141 142 mutexor mtx(&heap_mutex); 143 144 #ifdef DEBUG_FALLBACK_MALLOC 145 std::printf("Freeing item at %d of size %d\n", offset_from_node(cp), cp->len); 146 #endif 147 148 for (p = freelist, prev = 0; p && p != list_end; 149 prev = p, p = node_from_offset(p->next_node)) { 150 #ifdef DEBUG_FALLBACK_MALLOC 151 std::printf(" p=%d, cp=%d, after(p)=%d, after(cp)=%d\n", 152 offset_from_node(p), offset_from_node(cp), 153 offset_from_node(after(p)), offset_from_node(after(cp))); 154 #endif 155 if (after(p) == cp) { 156 #ifdef DEBUG_FALLBACK_MALLOC 157 std::printf(" Appending onto chunk at %d\n", offset_from_node(p)); 158 #endif 159 p->len = static_cast<heap_size>( 160 p->len + cp->len); // make the free heap_node larger 161 return; 162 } else if (after(cp) == p) { // there's a free heap_node right after 163 #ifdef DEBUG_FALLBACK_MALLOC 164 std::printf(" Appending free chunk at %d\n", offset_from_node(p)); 165 #endif 166 cp->len = static_cast<heap_size>(cp->len + p->len); 167 if (prev == 0) { 168 freelist = cp; 169 cp->next_node = p->next_node; 170 } else 171 prev->next_node = offset_from_node(cp); 172 return; 173 } 174 } 175 // Nothing to merge with, add it to the start of the free list 176 #ifdef DEBUG_FALLBACK_MALLOC 177 std::printf(" Making new free list entry %d\n", offset_from_node(cp)); 178 #endif 179 cp->next_node = offset_from_node(freelist); 180 freelist = cp; 181 } 182 183 #ifdef INSTRUMENT_FALLBACK_MALLOC 184 size_t print_free_list() { 185 struct heap_node *p, *prev; 186 heap_size total_free = 0; 187 if (NULL == freelist) 188 init_heap(); 189 190 for (p = freelist, prev = 0; p && p != list_end; 191 prev = p, p = node_from_offset(p->next_node)) { 192 std::printf("%sOffset: %d\tsize: %d Next: %d\n", 193 (prev == 0 ? "" : " "), offset_from_node(p), p->len, p->next_node); 194 total_free += p->len; 195 } 196 std::printf("Total Free space: %d\n", total_free); 197 return total_free; 198 } 199 #endif 200 } // end unnamed namespace 201 202 namespace __cxxabiv1 { 203 204 struct __attribute__((aligned)) __aligned_type {}; 205 206 void* __aligned_malloc_with_fallback(size_t size) { 207 #if defined(_WIN32) 208 if (void* dest = std::__libcpp_aligned_alloc(alignof(__aligned_type), size)) 209 return dest; 210 #elif defined(_LIBCPP_HAS_NO_LIBRARY_ALIGNED_ALLOCATION) 211 if (void* dest = ::malloc(size)) 212 return dest; 213 #else 214 if (size == 0) 215 size = 1; 216 if (void* dest = std::__libcpp_aligned_alloc(__alignof(__aligned_type), size)) 217 return dest; 218 #endif 219 return fallback_malloc(size); 220 } 221 222 void* __calloc_with_fallback(size_t count, size_t size) { 223 void* ptr = ::calloc(count, size); 224 if (NULL != ptr) 225 return ptr; 226 // if calloc fails, fall back to emergency stash 227 ptr = fallback_malloc(size * count); 228 if (NULL != ptr) 229 ::memset(ptr, 0, size * count); 230 return ptr; 231 } 232 233 void __aligned_free_with_fallback(void* ptr) { 234 if (is_fallback_ptr(ptr)) 235 fallback_free(ptr); 236 else { 237 #if defined(_LIBCPP_HAS_NO_LIBRARY_ALIGNED_ALLOCATION) 238 ::free(ptr); 239 #else 240 std::__libcpp_aligned_free(ptr); 241 #endif 242 } 243 } 244 245 void __free_with_fallback(void* ptr) { 246 if (is_fallback_ptr(ptr)) 247 fallback_free(ptr); 248 else 249 ::free(ptr); 250 } 251 252 } // namespace __cxxabiv1