1 //===----------------------------------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #include <cstdio>
10 #include <deque>
11
12 #include <__threading_support>
13
14 // UNSUPPORTED: modules-build && no-threads
15
16 // Necessary because we include a private source file of libc++abi, which
17 // only understands _LIBCXXABI_HAS_NO_THREADS.
18 #include "test_macros.h"
19 #ifdef TEST_HAS_NO_THREADS
20 # define _LIBCXXABI_HAS_NO_THREADS
21 #endif
22
23 typedef std::deque<void *> container;
24
25 // #define DEBUG_FALLBACK_MALLOC
26 #define INSTRUMENT_FALLBACK_MALLOC
27 #include "../src/fallback_malloc.cpp"
28
alloc_series(size_t sz)29 container alloc_series ( size_t sz ) {
30 container ptrs;
31 void *p;
32
33 while ( NULL != ( p = fallback_malloc ( sz )))
34 ptrs.push_back ( p );
35 return ptrs;
36 }
37
alloc_series(size_t sz,float growth)38 container alloc_series ( size_t sz, float growth ) {
39 container ptrs;
40 void *p;
41
42 while ( NULL != ( p = fallback_malloc ( sz ))) {
43 ptrs.push_back ( p );
44 sz *= growth;
45 }
46
47 return ptrs;
48 }
49
alloc_series(const size_t * first,size_t len)50 container alloc_series ( const size_t *first, size_t len ) {
51 container ptrs;
52 const size_t *last = first + len;
53 void * p;
54
55 for ( const size_t *iter = first; iter != last; ++iter ) {
56 if ( NULL == (p = fallback_malloc ( *iter )))
57 break;
58 ptrs.push_back ( p );
59 }
60
61 return ptrs;
62 }
63
pop(container & c,bool from_end)64 void *pop ( container &c, bool from_end ) {
65 void *ptr;
66 if ( from_end ) {
67 ptr = c.back ();
68 c.pop_back ();
69 }
70 else {
71 ptr = c.front ();
72 c.pop_front ();
73 }
74 return ptr;
75 }
76
exhaustion_test1()77 void exhaustion_test1 () {
78 container ptrs;
79
80 init_heap ();
81 std::printf("Constant exhaustion tests\n");
82
83 // Delete in allocation order
84 ptrs = alloc_series ( 32 );
85 std::printf("Allocated %zu 32 byte chunks\n", ptrs.size());
86 print_free_list ();
87 for ( container::iterator iter = ptrs.begin (); iter != ptrs.end (); ++iter )
88 fallback_free ( *iter );
89 print_free_list ();
90 std::printf("----\n");
91
92 // Delete in reverse order
93 ptrs = alloc_series ( 32 );
94 std::printf("Allocated %zu 32 byte chunks\n", ptrs.size());
95 for ( container::reverse_iterator iter = ptrs.rbegin (); iter != ptrs.rend (); ++iter )
96 fallback_free ( *iter );
97 print_free_list ();
98 std::printf("----\n");
99
100 // Alternate deletions
101 ptrs = alloc_series ( 32 );
102 std::printf("Allocated %zu 32 byte chunks\n", ptrs.size());
103 while ( ptrs.size () > 0 )
104 fallback_free ( pop ( ptrs, ptrs.size () % 1 == 1 ));
105 print_free_list ();
106 }
107
exhaustion_test2()108 void exhaustion_test2 () {
109 container ptrs;
110 init_heap ();
111
112 std::printf("Growing exhaustion tests\n");
113
114 // Delete in allocation order
115 ptrs = alloc_series ( 32, 1.5 );
116
117 std::printf("Allocated %zu { 32, 48, 72, 108, 162 ... } byte chunks\n",
118 ptrs.size());
119 print_free_list ();
120 for ( container::iterator iter = ptrs.begin (); iter != ptrs.end (); ++iter )
121 fallback_free ( *iter );
122 print_free_list ();
123 std::printf("----\n");
124
125 // Delete in reverse order
126 print_free_list ();
127 ptrs = alloc_series ( 32, 1.5 );
128 std::printf("Allocated %zu { 32, 48, 72, 108, 162 ... } byte chunks\n",
129 ptrs.size());
130 for ( container::reverse_iterator iter = ptrs.rbegin (); iter != ptrs.rend (); ++iter )
131 fallback_free ( *iter );
132 print_free_list ();
133 std::printf("----\n");
134
135 // Alternate deletions
136 ptrs = alloc_series ( 32, 1.5 );
137 std::printf("Allocated %zu { 32, 48, 72, 108, 162 ... } byte chunks\n",
138 ptrs.size());
139 while ( ptrs.size () > 0 )
140 fallback_free ( pop ( ptrs, ptrs.size () % 1 == 1 ));
141 print_free_list ();
142
143 }
144
exhaustion_test3()145 void exhaustion_test3 () {
146 const size_t allocs [] = { 124, 60, 252, 60, 4 };
147 container ptrs;
148 init_heap ();
149
150 std::printf("Complete exhaustion tests\n");
151
152 // Delete in allocation order
153 ptrs = alloc_series ( allocs, sizeof ( allocs ) / sizeof ( allocs[0] ));
154 std::printf("Allocated %zu chunks\n", ptrs.size());
155 print_free_list ();
156 for ( container::iterator iter = ptrs.begin (); iter != ptrs.end (); ++iter )
157 fallback_free ( *iter );
158 print_free_list ();
159 std::printf("----\n");
160
161 // Delete in reverse order
162 print_free_list ();
163 ptrs = alloc_series ( allocs, sizeof ( allocs ) / sizeof ( allocs[0] ));
164 std::printf("Allocated %zu chunks\n", ptrs.size());
165 for ( container::reverse_iterator iter = ptrs.rbegin (); iter != ptrs.rend (); ++iter )
166 fallback_free ( *iter );
167 print_free_list ();
168 std::printf("----\n");
169
170 // Alternate deletions
171 ptrs = alloc_series ( allocs, sizeof ( allocs ) / sizeof ( allocs[0] ));
172 std::printf("Allocated %zu chunks\n", ptrs.size());
173 while ( ptrs.size () > 0 )
174 fallback_free ( pop ( ptrs, ptrs.size () % 1 == 1 ));
175 print_free_list ();
176
177 }
178
179
main()180 int main () {
181 print_free_list ();
182
183 char *p = (char *) fallback_malloc ( 1024 ); // too big!
184 std::printf("fallback_malloc ( 1024 ) --> %lu\n", (unsigned long ) p);
185 print_free_list ();
186
187 p = (char *) fallback_malloc ( 32 );
188 std::printf("fallback_malloc ( 32 ) --> %lu\n", (unsigned long) (p - heap));
189 if ( !is_fallback_ptr ( p ))
190 std::printf("### p is not a fallback pointer!!\n");
191
192 print_free_list ();
193 fallback_free ( p );
194 print_free_list ();
195
196 exhaustion_test1();
197 exhaustion_test2();
198 exhaustion_test3();
199 return 0;
200 }
201