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