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 
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 
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 
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 
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 
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 
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 
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 
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