Memory manangement routines for exception objects

llvm-svn: 135587

3 files changed, 448 insertions, 0 deletions

diff --git a/libcxxabi/src/cxa_exception.cpp b/libcxxabi/src/cxa_exception.cpp
new file mode 100644
index 00000000000..93a4bd41df0
--- /dev/null
+++ b/libcxxabi/src/cxa_exception.cpp
@@ -0,0 +1,107 @@
+//===------------------------- cxa_exception.cpp --------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//  
+//  This file implements the "Exception Handling APIs"
+//  http://www.codesourcery.com/public/cxx-abi/abi-eh.html
+//  
+//===----------------------------------------------------------------------===//
+
+#include "cxxabi.h"
+
+#include <exception>        // for std::terminate
+#include <cstdlib>          // for malloc, free
+#include <string>           // for memset
+#include <pthread.h>
+
+#include "cxa_exception.hpp"
+#include "cxa_exception_storage.hpp"
+
+namespace __cxxabiv1 {
+
+//  Utility routines
+static __cxa_exception *exception_from_object ( void *p ) {
+    return ((__cxa_exception *) p ) - 1;
+    }
+    
+void * object_from_exception ( void *p ) {
+    return (void *) (((__cxa_exception *) p ) + 1 );
+    }
+
+static size_t object_size_from_exception_size ( size_t size ) {
+    return size + sizeof (__cxa_exception);
+    }
+
+#include "fallback_malloc.cpp"
+
+//  Allocate some memory from _somewhere_
+static void *do_malloc ( size_t size ) throw () {
+    void *ptr = std::malloc ( size );
+    if ( NULL == ptr )  // if malloc fails, fall back to emergency stash
+        ptr = fallback_malloc ( size );
+    return ptr;
+    }
+
+//  Didn't know you could "return <expression>" from a void function, did you?
+//  Well, you can, if the type of the expression is "void" also.
+static void do_free ( void *ptr ) throw () {
+    return is_fallback_ptr ( ptr ) ? fallback_free ( ptr ) : std::free ( ptr );
+    }
+
+static thread_local_storage<__cxa_eh_globals> __globals;
+// pthread_once_t __globals::flag_ = PTHREAD_ONCE_INIT;
+
+extern "C" {
+
+//  Allocate a __cxa_exception object, and zero-fill it.
+//  Reserve "thrown_size" bytes on the end for the user's exception
+//  object. Zero-fill the object. If memory can't be allocated, call
+//  std::terminate. Return a pointer to the memory to be used for the
+//  user's exception object.
+void * __cxa_allocate_exception (size_t thrown_size) throw() {
+    size_t actual_size = object_size_from_exception_size ( thrown_size );
+    void *ptr = do_malloc ( actual_size );
+    if ( NULL == ptr )
+        std::terminate ();
+    std::memset ( ptr, 0, actual_size );
+    return object_from_exception ( ptr );
+    }
+
+
+//  Free a __cxa_exception object allocated with __cxa_allocate_exception.
+void __cxa_free_exception (void * thrown_exception) throw() {
+    do_free ( exception_from_object ( thrown_exception ));
+    }
+
+
+//  This function shall allocate a __cxa_dependent_exception and
+//  return a pointer to it. (Really to the object, not past its' end).
+//  Otherwise, it will work like __cxa_allocate_exception.
+void * __cxa_allocate_dependent_exception () throw() {
+    size_t actual_size = sizeof ( __cxa_dependent_exception );
+    void *ptr = do_malloc ( actual_size );
+    if ( NULL == ptr )
+        std::terminate ();
+    std::memset ( ptr, 0, actual_size );
+//  bookkeeping here ?
+    return ptr;
+    }
+
+
+//  This function shall free a dependent_exception.
+//  It does not affect the reference count of the primary exception.
+void __cxa_free_dependent_exception (void * dependent_exception) throw() {
+//  I'm pretty sure there's no bookkeeping here
+    do_free ( dependent_exception );
+    }
+
+__cxa_eh_globals * __cxa_get_globals      () throw() { return __globals.get_tls (); }
+__cxa_eh_globals * __cxa_get_globals_fast () throw() { return __globals.get_tls_fast (); }
+
+}  // extern "C"
+
+}  // abi
diff --git a/libcxxabi/src/fallback_malloc.cpp b/libcxxabi/src/fallback_malloc.cpp
new file mode 100644
index 00000000000..45d52fec72f
--- /dev/null
+++ b/libcxxabi/src/fallback_malloc.cpp
@@ -0,0 +1,161 @@
+//  A small, simple heap manager based (loosely) on the startup heap
+//  based on the startup heap manager from FreeBSD.
+//
+//  Manages a fixed-size memory pool, supports malloc and free only.
+//  No support for realloc.
+//
+//  Allocates chunks in multiples of four bytes, with a four byte header
+//  for each chunk. The overhead of each chunk is kept low by keeping pointers
+//  as two byte offsets within the heap, rather than (4 or 8 byte) pointers.
+
+namespace {
+
+static pthread_mutex_t heap_mutex = PTHREAD_MUTEX_INITIALIZER;
+
+class mutexor {
+public:
+    mutexor ( pthread_mutex_t *m ) : mtx_(m) { pthread_mutex_lock ( mtx_ ); }
+    ~mutexor () { pthread_mutex_unlock ( mtx_ ); }
+private:
+    mutexor ( const mutexor &rhs );
+    mutexor & operator = ( const mutexor &rhs );
+    pthread_mutex_t *mtx_;
+    };
+
+        
+#define HEAP_SIZE   512
+char heap [ HEAP_SIZE ];
+
+typedef unsigned short heap_offset;
+typedef unsigned short heap_size;
+
+struct heap_node {
+    heap_offset next_node;  // offset into heap
+    heap_size   len;        // size in units of "sizeof(heap_node)"
+};
+
+static const heap_node *list_end = (heap_node *) ( &heap [ HEAP_SIZE ] );   // one past the end of the heap
+static heap_node *freelist = NULL;
+
+heap_node *node_from_offset ( const heap_offset offset ) throw() 
+    { return (heap_node *) ( heap + ( offset * sizeof (heap_node))); }
+
+heap_offset offset_from_node ( const heap_node *ptr )    throw() 
+    { return (((char *) ptr ) - heap)  / sizeof (heap_node); }
+ 
+void init_heap () throw() {
+    freelist = (heap_node *) heap;
+    freelist->next_node = offset_from_node ( list_end );
+    freelist->len = HEAP_SIZE / sizeof (heap_node);
+    }
+    
+//  How big a chunk we allocate
+size_t alloc_size (size_t len) throw() 
+    { return (len + sizeof(heap_node) - 1) / sizeof(heap_node) + 1; }
+
+bool is_fallback_ptr ( void *ptr ) throw() 
+    { return ptr >= heap && ptr < ( heap + HEAP_SIZE ); }
+
+void *fallback_malloc(size_t len) throw() {
+    heap_node *p, *prev;
+    const size_t nelems = alloc_size ( len );
+    mutexor mtx ( &heap_mutex );
+    
+    if ( NULL == freelist )
+        init_heap ();
+
+//  Walk the free list, looking for a "big enough" chunk
+    for (p = freelist, prev = 0; 
+            p && p != list_end;     prev = p, p = node_from_offset ( p->next_node)) {
+
+        if (p->len > nelems) {  //  chunk is larger, shorten, and return the tail
+            heap_node *q;
+            
+            p->len -= nelems;
+            q = p + p->len;
+            q->next_node = 0;
+            q->len = nelems;
+            return (void *) (q + 1);
+        }
+        
+        if (p->len == nelems) { // exact size match
+            if (prev == 0)
+                freelist = node_from_offset(p->next_node);
+            else
+                prev->next_node = p->next_node;
+            p->next_node = 0;
+            return (void *) (p + 1);
+        }
+    }
+    return NULL;    // couldn't find a spot big enough
+}
+
+//  Return the start of the next block
+heap_node *after ( struct heap_node *p ) throw() { return p + p->len; }
+
+void fallback_free (void *ptr) throw() {
+    struct heap_node *cp = ((struct heap_node *) ptr) - 1;      // retrieve the chunk
+    struct heap_node *p, *prev;
+
+    mutexor mtx ( &heap_mutex );
+
+#ifdef DEBUG_FALLBACK_MALLOC
+        std::cout << "Freeing item at " << offset_from_node ( cp ) << " of size " << cp->len << std::endl;
+#endif
+
+    for (p = freelist, prev = 0; 
+            p && p != list_end;     prev = p, p = node_from_offset (p->next_node)) {
+#ifdef DEBUG_FALLBACK_MALLOC
+        std::cout << "  p, cp, after (p), after(cp) "
+            << offset_from_node ( p ) << ' '
+            << offset_from_node ( cp ) << ' '
+            << offset_from_node ( after ( p )) << ' '
+            << offset_from_node ( after ( cp )) << std::endl;
+#endif
+        if ( after ( p ) == cp ) {
+#ifdef DEBUG_FALLBACK_MALLOC
+            std::cout << "  Appending onto chunk at " << offset_from_node ( p ) << std::endl;
+#endif
+            p->len += cp->len;  // make the free heap_node larger
+            return;
+            }
+        else if ( after ( cp ) == p ) { // there's a free heap_node right after
+#ifdef DEBUG_FALLBACK_MALLOC
+            std::cout << "  Appending free chunk at " << offset_from_node ( p ) << std::endl;
+#endif
+            cp->len += p->len;
+            if ( prev == 0 ) {
+                freelist = cp;
+                cp->next_node = p->next_node;
+                }
+            else
+                prev->next_node = offset_from_node(cp);
+            return;
+            }
+        }
+//  Nothing to merge with, add it to the start of the free list
+#ifdef DEBUG_FALLBACK_MALLOC
+            std::cout << "  Making new free list entry " << offset_from_node ( cp ) << std::endl;
+#endif
+    cp->next_node = offset_from_node ( freelist );
+    freelist = cp;
+}
+
+#ifdef INSTRUMENT_FALLBACK_MALLOC
+size_t print_free_list () {
+    struct heap_node *p, *prev;
+    heap_size total_free = 0;
+    if ( NULL == freelist )
+        init_heap ();
+    
+    for (p = freelist, prev = 0; 
+            p && p != list_end;     prev = p, p = node_from_offset (p->next_node)) {
+        std::cout << ( prev == 0 ? "" : "  ")  << "Offset: " << offset_from_node ( p ) 
+                << "\tsize: " << p->len << " Next: " << p->next_node << std::endl;
+        total_free += p->len;
+        }
+    std::cout << "Total Free space: " << total_free << std::endl;
+    return total_free;
+    }
+#endif
+}
diff --git a/libcxxabi/test/test_fallback_malloc.cpp b/libcxxabi/test/test_fallback_malloc.cpp
new file mode 100644
index 00000000000..aaddc6af670
--- /dev/null
+++ b/libcxxabi/test/test_fallback_malloc.cpp
@@ -0,0 +1,180 @@
+#include <iostream>
+#include <deque>
+
+#include <pthread.h>
+
+typedef std::deque<void *> container;
+
+// #define  DEBUG_FALLBACK_MALLOC
+#define INSTRUMENT_FALLBACK_MALLOC
+#include "../src/fallback_malloc.cpp"
+
+container alloc_series ( size_t sz ) {
+    container ptrs;
+    void *p;
+    
+    while ( NULL != ( p = fallback_malloc ( sz )))
+        ptrs.push_back ( p );
+    return ptrs;
+    }
+
+container alloc_series ( size_t sz, float growth ) {
+    container ptrs;
+    void *p;
+    
+    while ( NULL != ( p = fallback_malloc ( sz ))) {
+        ptrs.push_back ( p );
+        sz *= growth;
+        }
+
+    return ptrs;
+    }
+
+container alloc_series ( const size_t *first, size_t len ) {
+    container ptrs;
+    const size_t *last = first + len;
+    void * p;
+    
+    for ( const size_t *iter = first; iter != last; ++iter ) {
+        if ( NULL == (p = fallback_malloc ( *iter )))
+            break;
+        ptrs.push_back ( p );
+        }
+
+    return ptrs;
+    }
+
+void *pop ( container &c, bool from_end ) {
+    void *ptr;
+    if ( from_end ) {
+        ptr = c.back ();
+        c.pop_back ();
+        }
+    else {
+        ptr = c.front ();
+        c.pop_front ();
+        }
+    return ptr;
+    }
+
+void exhaustion_test1 () {
+    container ptrs;
+    
+    init_heap ();
+    std::cout << "Constant exhaustion tests" << std::endl;
+    
+//  Delete in allocation order
+    ptrs = alloc_series ( 32 );
+    std::cout << "Allocated " << ptrs.size () << " 32 byte chunks" << std::endl;
+    print_free_list ();
+    for ( container::iterator iter = ptrs.begin (); iter != ptrs.end (); ++iter )
+        fallback_free ( *iter );
+    print_free_list ();
+    std::cout << "----" << std::endl;
+
+//  Delete in reverse order
+    ptrs = alloc_series ( 32 );
+    std::cout << "Allocated " << ptrs.size () << " 32 byte chunks" << std::endl;
+    for ( container::reverse_iterator iter = ptrs.rbegin (); iter != ptrs.rend (); ++iter )
+        fallback_free ( *iter );
+    print_free_list ();
+    std::cout << "----" << std::endl;
+
+//  Alternate deletions
+    ptrs = alloc_series ( 32 );
+    std::cout << "Allocated " << ptrs.size () << " 32 byte chunks" << std::endl;
+    while ( ptrs.size () > 0 )
+        fallback_free ( pop ( ptrs, ptrs.size () % 1 == 1 ));
+    print_free_list ();
+    }
+            
+void exhaustion_test2 () {
+    container ptrs;
+    init_heap ();
+    
+    std::cout << "Growing exhaustion tests" << std::endl;
+
+//  Delete in allocation order
+    ptrs = alloc_series ( 32, 1.5 );
+    std::cout << "Allocated " << ptrs.size () << " { 32, 48, 72, 108, 162 ... }  byte chunks" << std::endl;
+    print_free_list ();
+    for ( container::iterator iter = ptrs.begin (); iter != ptrs.end (); ++iter )
+        fallback_free ( *iter );
+    print_free_list ();
+    std::cout << "----" << std::endl;
+    
+//  Delete in reverse order
+    print_free_list ();
+    ptrs = alloc_series ( 32, 1.5 );
+    std::cout << "Allocated " << ptrs.size () << " { 32, 48, 72, 108, 162 ... }  byte chunks" << std::endl;
+    for ( container::reverse_iterator iter = ptrs.rbegin (); iter != ptrs.rend (); ++iter )
+        fallback_free ( *iter );
+    print_free_list ();
+    std::cout << "----" << std::endl;
+
+//  Alternate deletions
+    ptrs = alloc_series ( 32, 1.5 );
+    std::cout << "Allocated " << ptrs.size () << " { 32, 48, 72, 108, 162 ... }  byte chunks" << std::endl;
+    while ( ptrs.size () > 0 )
+        fallback_free ( pop ( ptrs, ptrs.size () % 1 == 1 ));
+    print_free_list (); 
+    
+    }
+
+void exhaustion_test3 () {
+    const size_t allocs [] = { 124, 60, 252, 60, 4 };
+    container ptrs;
+    init_heap ();
+    
+    std::cout << "Complete exhaustion tests" << std::endl;
+
+//  Delete in allocation order
+    ptrs = alloc_series ( allocs, sizeof ( allocs ) / sizeof ( allocs[0] ));
+    std::cout << "Allocated " << ptrs.size () << " chunks" << std::endl;
+    print_free_list ();
+    for ( container::iterator iter = ptrs.begin (); iter != ptrs.end (); ++iter )
+        fallback_free ( *iter );
+    print_free_list ();
+    std::cout << "----" << std::endl;
+    
+//  Delete in reverse order
+    print_free_list ();
+    ptrs = alloc_series ( allocs, sizeof ( allocs ) / sizeof ( allocs[0] ));
+    std::cout << "Allocated " << ptrs.size () << " chunks" << std::endl;
+    for ( container::reverse_iterator iter = ptrs.rbegin (); iter != ptrs.rend (); ++iter )
+        fallback_free ( *iter );
+    print_free_list ();
+    std::cout << "----" << std::endl;
+
+//  Alternate deletions
+    ptrs = alloc_series ( allocs, sizeof ( allocs ) / sizeof ( allocs[0] ));
+    std::cout << "Allocated " << ptrs.size () << " chunks" << std::endl;
+    while ( ptrs.size () > 0 )
+        fallback_free ( pop ( ptrs, ptrs.size () % 1 == 1 ));
+    print_free_list (); 
+    
+    }
+
+    
+int main ( int argc, char *argv [] ) {
+    print_free_list ();
+
+    char *p = (char *) fallback_malloc ( 1024 );    // too big!
+    std::cout << "fallback_malloc ( 1024 ) --> " << (unsigned long ) p << std::endl;
+    print_free_list ();
+    
+    p = (char *) fallback_malloc ( 32 );
+    std::cout << "fallback_malloc ( 32 ) --> " << (unsigned long) (p - heap) << std::endl;
+    if ( !is_fallback_ptr ( p ))
+        std::cout << "### p is not a fallback pointer!!" << std::endl;
+    
+    print_free_list ();
+    fallback_free ( p );
+    print_free_list ();
+    
+    std::cout << std::endl;
+    exhaustion_test1 (); std::cout << std::endl;
+    exhaustion_test2 (); std::cout << std::endl;
+    exhaustion_test3 (); std::cout << std::endl;
+    return 0;
+    }