1 //===------------------------ fallback_malloc.ipp -------------------------===// 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 // This file implements the "Exception Handling APIs" 10 // http://mentorembedded.github.io/cxx-abi/abi-eh.html 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "config.h" 15 16 // A small, simple heap manager based (loosely) on 17 // the startup heap manager from FreeBSD, optimized for space. 18 // 19 // Manages a fixed-size memory pool, supports malloc and free only. 20 // No support for realloc. 21 // 22 // Allocates chunks in multiples of four bytes, with a four byte header 23 // for each chunk. The overhead of each chunk is kept low by keeping pointers 24 // as two byte offsets within the heap, rather than (4 or 8 byte) pointers. 25 26 namespace { 27 28 // When POSIX threads are not available, make the mutex operations a nop 29 #if LIBCXXABI_HAS_NO_THREADS 30 static void * heap_mutex = 0; 31 #else 32 static pthread_mutex_t heap_mutex = PTHREAD_MUTEX_INITIALIZER; 33 #endif 34 35 class mutexor { 36 public: 37 #if LIBCXXABI_HAS_NO_THREADS 38 mutexor ( void * ) {} 39 ~mutexor () {} 40 #else 41 mutexor ( pthread_mutex_t *m ) : mtx_(m) { pthread_mutex_lock ( mtx_ ); } 42 ~mutexor () { pthread_mutex_unlock ( mtx_ ); } 43 #endif 44 private: 45 mutexor ( const mutexor &rhs ); 46 mutexor & operator = ( const mutexor &rhs ); 47 #if !LIBCXXABI_HAS_NO_THREADS 48 pthread_mutex_t *mtx_; 49 #endif 50 }; 51 52 53 #define HEAP_SIZE 512 54 char heap [ HEAP_SIZE ]; 55 56 typedef unsigned short heap_offset; 57 typedef unsigned short heap_size; 58 59 struct heap_node { 60 heap_offset next_node; // offset into heap 61 heap_size len; // size in units of "sizeof(heap_node)" 62 }; 63 64 static const heap_node *list_end = (heap_node *) ( &heap [ HEAP_SIZE ] ); // one past the end of the heap 65 static heap_node *freelist = NULL; 66 67 heap_node *node_from_offset ( const heap_offset offset ) 68 { return (heap_node *) ( heap + ( offset * sizeof (heap_node))); } 69 70 heap_offset offset_from_node ( const heap_node *ptr ) 71 { return static_cast<heap_offset>(static_cast<size_t>(((char *) ptr ) - heap) / sizeof (heap_node)); } 72 73 void init_heap () { 74 freelist = (heap_node *) heap; 75 freelist->next_node = offset_from_node ( list_end ); 76 freelist->len = HEAP_SIZE / sizeof (heap_node); 77 } 78 79 // How big a chunk we allocate 80 size_t alloc_size (size_t len) 81 { return (len + sizeof(heap_node) - 1) / sizeof(heap_node) + 1; } 82 83 bool is_fallback_ptr ( void *ptr ) 84 { return ptr >= heap && ptr < ( heap + HEAP_SIZE ); } 85 86 void *fallback_malloc(size_t len) { 87 heap_node *p, *prev; 88 const size_t nelems = alloc_size ( len ); 89 mutexor mtx ( &heap_mutex ); 90 91 if ( NULL == freelist ) 92 init_heap (); 93 94 // Walk the free list, looking for a "big enough" chunk 95 for (p = freelist, prev = 0; 96 p && p != list_end; prev = p, p = node_from_offset ( p->next_node)) { 97 98 if (p->len > nelems) { // chunk is larger, shorten, and return the tail 99 heap_node *q; 100 101 p->len -= nelems; 102 q = p + p->len; 103 q->next_node = 0; 104 q->len = static_cast<heap_size>(nelems); 105 return (void *) (q + 1); 106 } 107 108 if (p->len == nelems) { // exact size match 109 if (prev == 0) 110 freelist = node_from_offset(p->next_node); 111 else 112 prev->next_node = p->next_node; 113 p->next_node = 0; 114 return (void *) (p + 1); 115 } 116 } 117 return NULL; // couldn't find a spot big enough 118 } 119 120 // Return the start of the next block 121 heap_node *after ( struct heap_node *p ) { return p + p->len; } 122 123 void fallback_free (void *ptr) { 124 struct heap_node *cp = ((struct heap_node *) ptr) - 1; // retrieve the chunk 125 struct heap_node *p, *prev; 126 127 mutexor mtx ( &heap_mutex ); 128 129 #ifdef DEBUG_FALLBACK_MALLOC 130 std::cout << "Freeing item at " << offset_from_node ( cp ) << " of size " << cp->len << std::endl; 131 #endif 132 133 for (p = freelist, prev = 0; 134 p && p != list_end; prev = p, p = node_from_offset (p->next_node)) { 135 #ifdef DEBUG_FALLBACK_MALLOC 136 std::cout << " p, cp, after (p), after(cp) " 137 << offset_from_node ( p ) << ' ' 138 << offset_from_node ( cp ) << ' ' 139 << offset_from_node ( after ( p )) << ' ' 140 << offset_from_node ( after ( cp )) << std::endl; 141 #endif 142 if ( after ( p ) == cp ) { 143 #ifdef DEBUG_FALLBACK_MALLOC 144 std::cout << " Appending onto chunk at " << offset_from_node ( p ) << std::endl; 145 #endif 146 p->len += cp->len; // make the free heap_node larger 147 return; 148 } 149 else if ( after ( cp ) == p ) { // there's a free heap_node right after 150 #ifdef DEBUG_FALLBACK_MALLOC 151 std::cout << " Appending free chunk at " << offset_from_node ( p ) << std::endl; 152 #endif 153 cp->len += p->len; 154 if ( prev == 0 ) { 155 freelist = cp; 156 cp->next_node = p->next_node; 157 } 158 else 159 prev->next_node = offset_from_node(cp); 160 return; 161 } 162 } 163 // Nothing to merge with, add it to the start of the free list 164 #ifdef DEBUG_FALLBACK_MALLOC 165 std::cout << " Making new free list entry " << offset_from_node ( cp ) << std::endl; 166 #endif 167 cp->next_node = offset_from_node ( freelist ); 168 freelist = cp; 169 } 170 171 #ifdef INSTRUMENT_FALLBACK_MALLOC 172 size_t print_free_list () { 173 struct heap_node *p, *prev; 174 heap_size total_free = 0; 175 if ( NULL == freelist ) 176 init_heap (); 177 178 for (p = freelist, prev = 0; 179 p && p != list_end; prev = p, p = node_from_offset (p->next_node)) { 180 std::cout << ( prev == 0 ? "" : " ") << "Offset: " << offset_from_node ( p ) 181 << "\tsize: " << p->len << " Next: " << p->next_node << std::endl; 182 total_free += p->len; 183 } 184 std::cout << "Total Free space: " << total_free << std::endl; 185 return total_free; 186 } 187 #endif 188 } // end unnamed namespace 189
