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