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