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