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