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 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 %zu 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 %zu 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 %zu 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 %zu { 32, 48, 72, 108, 162 ... } byte chunks\n",
109                 ptrs.size());
110     print_free_list ();
111     for ( container::iterator iter = ptrs.begin (); iter != ptrs.end (); ++iter )
112         fallback_free ( *iter );
113     print_free_list ();
114     std::printf("----\n");
115 
116 //  Delete in reverse order
117     print_free_list ();
118     ptrs = alloc_series ( 32, 1.5 );
119     std::printf("Allocated %zu { 32, 48, 72, 108, 162 ... } byte chunks\n",
120                 ptrs.size());
121     for ( container::reverse_iterator iter = ptrs.rbegin (); iter != ptrs.rend (); ++iter )
122         fallback_free ( *iter );
123     print_free_list ();
124     std::printf("----\n");
125 
126 //  Alternate deletions
127     ptrs = alloc_series ( 32, 1.5 );
128     std::printf("Allocated %zu { 32, 48, 72, 108, 162 ... } byte chunks\n",
129                 ptrs.size());
130     while ( ptrs.size () > 0 )
131         fallback_free ( pop ( ptrs, ptrs.size () % 1 == 1 ));
132     print_free_list ();
133 
134 }
135 
136 void exhaustion_test3 () {
137     const size_t allocs [] = { 124, 60, 252, 60, 4 };
138     container ptrs;
139     init_heap ();
140 
141     std::printf("Complete exhaustion tests\n");
142 
143 //  Delete in allocation order
144     ptrs = alloc_series ( allocs, sizeof ( allocs ) / sizeof ( allocs[0] ));
145     std::printf("Allocated %zu chunks\n", ptrs.size());
146     print_free_list ();
147     for ( container::iterator iter = ptrs.begin (); iter != ptrs.end (); ++iter )
148         fallback_free ( *iter );
149     print_free_list ();
150     std::printf("----\n");
151 
152 //  Delete in reverse order
153     print_free_list ();
154     ptrs = alloc_series ( allocs, sizeof ( allocs ) / sizeof ( allocs[0] ));
155     std::printf("Allocated %zu chunks\n", ptrs.size());
156     for ( container::reverse_iterator iter = ptrs.rbegin (); iter != ptrs.rend (); ++iter )
157         fallback_free ( *iter );
158     print_free_list ();
159     std::printf("----\n");
160 
161 //  Alternate deletions
162     ptrs = alloc_series ( allocs, sizeof ( allocs ) / sizeof ( allocs[0] ));
163     std::printf("Allocated %zu chunks\n", ptrs.size());
164     while ( ptrs.size () > 0 )
165         fallback_free ( pop ( ptrs, ptrs.size () % 1 == 1 ));
166     print_free_list ();
167 
168 }
169 
170 
171 int main () {
172     print_free_list ();
173 
174     char *p = (char *) fallback_malloc ( 1024 );    // too big!
175     std::printf("fallback_malloc ( 1024 ) --> %lu\n", (unsigned long ) p);
176     print_free_list ();
177 
178     p = (char *) fallback_malloc ( 32 );
179     std::printf("fallback_malloc ( 32 ) --> %lu\n", (unsigned long) (p - heap));
180     if ( !is_fallback_ptr ( p ))
181         std::printf("### p is not a fallback pointer!!\n");
182 
183     print_free_list ();
184     fallback_free ( p );
185     print_free_list ();
186 
187     exhaustion_test1();
188     exhaustion_test2();
189     exhaustion_test3();
190     return 0;
191 }
192