src/third_party/libc++abi/trunk/src/fallback_malloc.ipp

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