← Back to branch summary

~ubuntu-branches/ubuntu/vivid/emscripten/vivid

« back to all changes in this revision

Viewing changes to system/lib/libcxxabi/src/fallback_malloc.ipp

  • Committer: Package Import Robot
  • Author(s): Sylvestre Ledru
  • Date: 2013-05-02 13:11:51 UTC
  • Revision ID: package-import@ubuntu.com-20130502131151-q8dvteqr1ef2x7xz
Tags: upstream-1.4.1~20130504~adb56cb
Import upstream version 1.4.1~20130504~adb56cb

Show diffs side-by-side

added added

removed removed

Lines of Context:
system/lib/libcxxabi/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