1 //===--------------------- test_fallback_malloc.cpp -----------------------===//
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 typedef std::deque<void *> container;
15 
16 // #define  DEBUG_FALLBACK_MALLOC
17 #define INSTRUMENT_FALLBACK_MALLOC
18 #include "../src/fallback_malloc.cpp"
19 
20 container alloc_series ( size_t sz ) {
21     container ptrs;
22     void *p;
23 
24     while ( NULL != ( p = fallback_malloc ( sz )))
25         ptrs.push_back ( p );
26     return ptrs;
27 }
28 
29 container alloc_series ( size_t sz, float growth ) {
30     container ptrs;
31     void *p;
32 
33     while ( NULL != ( p = fallback_malloc ( sz ))) {
34         ptrs.push_back ( p );
35         sz *= growth;
36     }
37 
38     return ptrs;
39 }
40 
41 container alloc_series ( const size_t *first, size_t len ) {
42     container ptrs;
43     const size_t *last = first + len;
44     void * p;
45 
46     for ( const size_t *iter = first; iter != last; ++iter ) {
47         if ( NULL == (p = fallback_malloc ( *iter )))
48             break;
49         ptrs.push_back ( p );
50     }
51 
52     return ptrs;
53 }
54 
55 void *pop ( container &c, bool from_end ) {
56     void *ptr;
57     if ( from_end ) {
58         ptr = c.back ();
59         c.pop_back ();
60     }
61     else {
62         ptr = c.front ();
63         c.pop_front ();
64     }
65     return ptr;
66 }
67 
68 void exhaustion_test1 () {
69     container ptrs;
70 
71     init_heap ();
72     std::printf("Constant exhaustion tests\n");
73 
74 //  Delete in allocation order
75     ptrs = alloc_series ( 32 );
76     std::printf("Allocated %lu 32 byte chunks\n", ptrs.size());
77     print_free_list ();
78     for ( container::iterator iter = ptrs.begin (); iter != ptrs.end (); ++iter )
79         fallback_free ( *iter );
80     print_free_list ();
81     std::printf("----\n");
82 
83 //  Delete in reverse order
84     ptrs = alloc_series ( 32 );
85     std::printf("Allocated %lu 32 byte chunks\n", ptrs.size());
86     for ( container::reverse_iterator iter = ptrs.rbegin (); iter != ptrs.rend (); ++iter )
87         fallback_free ( *iter );
88     print_free_list ();
89     std::printf("----\n");
90 
91 //  Alternate deletions
92     ptrs = alloc_series ( 32 );
93     std::printf("Allocated %lu 32 byte chunks\n", ptrs.size());
94     while ( ptrs.size () > 0 )
95         fallback_free ( pop ( ptrs, ptrs.size () % 1 == 1 ));
96     print_free_list ();
97 }
98 
99 void exhaustion_test2 () {
100     container ptrs;
101     init_heap ();
102 
103     std::printf("Growing exhaustion tests\n");
104 
105 //  Delete in allocation order
106     ptrs = alloc_series ( 32, 1.5 );
107 
108     std::printf("Allocated %lu { 32, 48, 72, 108, 162 ... } byte chunks\n", ptrs.size());
109     print_free_list ();
110     for ( container::iterator iter = ptrs.begin (); iter != ptrs.end (); ++iter )
111         fallback_free ( *iter );
112     print_free_list ();
113     std::printf("----\n");
114 
115 //  Delete in reverse order
116     print_free_list ();
117     ptrs = alloc_series ( 32, 1.5 );
118     std::printf("Allocated %lu { 32, 48, 72, 108, 162 ... } byte chunks\n", ptrs.size());
119     for ( container::reverse_iterator iter = ptrs.rbegin (); iter != ptrs.rend (); ++iter )
120         fallback_free ( *iter );
121     print_free_list ();
122     std::printf("----\n");
123 
124 //  Alternate deletions
125     ptrs = alloc_series ( 32, 1.5 );
126     std::printf("Allocated %lu { 32, 48, 72, 108, 162 ... } byte chunks\n", ptrs.size());
127     while ( ptrs.size () > 0 )
128         fallback_free ( pop ( ptrs, ptrs.size () % 1 == 1 ));
129     print_free_list ();
130 
131 }
132 
133 void exhaustion_test3 () {
134     const size_t allocs [] = { 124, 60, 252, 60, 4 };
135     container ptrs;
136     init_heap ();
137 
138     std::printf("Complete exhaustion tests\n");
139 
140 //  Delete in allocation order
141     ptrs = alloc_series ( allocs, sizeof ( allocs ) / sizeof ( allocs[0] ));
142     std::printf("Allocated %lu chunks\n", ptrs.size());
143     print_free_list ();
144     for ( container::iterator iter = ptrs.begin (); iter != ptrs.end (); ++iter )
145         fallback_free ( *iter );
146     print_free_list ();
147     std::printf("----\n");
148 
149 //  Delete in reverse order
150     print_free_list ();
151     ptrs = alloc_series ( allocs, sizeof ( allocs ) / sizeof ( allocs[0] ));
152     std::printf("Allocated %lu chunks\n", ptrs.size());
153     for ( container::reverse_iterator iter = ptrs.rbegin (); iter != ptrs.rend (); ++iter )
154         fallback_free ( *iter );
155     print_free_list ();
156     std::printf("----\n");
157 
158 //  Alternate deletions
159     ptrs = alloc_series ( allocs, sizeof ( allocs ) / sizeof ( allocs[0] ));
160     std::printf("Allocated %lu chunks\n", ptrs.size());
161     while ( ptrs.size () > 0 )
162         fallback_free ( pop ( ptrs, ptrs.size () % 1 == 1 ));
163     print_free_list ();
164 
165 }
166 
167 
168 int main () {
169     print_free_list ();
170 
171     char *p = (char *) fallback_malloc ( 1024 );    // too big!
172     std::printf("fallback_malloc ( 1024 ) --> %lu\n", (unsigned long ) p);
173     print_free_list ();
174 
175     p = (char *) fallback_malloc ( 32 );
176     std::printf("fallback_malloc ( 32 ) --> %lu\n", (unsigned long) (p - heap));
177     if ( !is_fallback_ptr ( p ))
178         std::printf("### p is not a fallback pointer!!\n");
179 
180     print_free_list ();
181     fallback_free ( p );
182     print_free_list ();
183 
184     exhaustion_test1();
185     exhaustion_test2();
186     exhaustion_test3();
187     return 0;
188 }
189