llvm-project

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
#include <cassert>
12
#include <inttypes.h>
13

14
#include <__thread/support.h>
15

16
// UNSUPPORTED: c++03
17
// UNSUPPORTED: modules-build && no-threads
18

19
// Necessary because we include a private source file of libc++abi, which
20
// only understands _LIBCXXABI_HAS_NO_THREADS.
21
#include "test_macros.h"
22
#ifdef TEST_HAS_NO_THREADS
23
# define _LIBCXXABI_HAS_NO_THREADS
24
#endif
25

26
typedef std::deque<void *> container;
27

28
TEST_DIAGNOSTIC_PUSH
29
TEST_CLANG_DIAGNOSTIC_IGNORED("-Wprivate-header")
30
#define _LIBCXXABI_ASSERT(expr, msg) assert((expr) && (msg))
31

32
// #define  DEBUG_FALLBACK_MALLOC
33
#define INSTRUMENT_FALLBACK_MALLOC
34
#include "../src/fallback_malloc.cpp"
35
TEST_DIAGNOSTIC_POP
36

37
void assertAlignment(void* ptr) { assert(reinterpret_cast<size_t>(ptr) % alignof(FallbackMaxAlignType) == 0); }
38

39
container alloc_series ( size_t sz ) {
40
    container ptrs;
41
    void *p;
42

43
    while (NULL != (p = fallback_malloc(sz))) {
44
      assertAlignment(p);
45
      ptrs.push_back(p);
46
    }
47
    return ptrs;
48
}
49

50
container alloc_series ( size_t sz, float growth ) {
51
    container ptrs;
52
    void *p;
53

54
    while ( NULL != ( p = fallback_malloc ( sz ))) {
55
      assertAlignment(p);
56
      ptrs.push_back(p);
57
      sz *= growth;
58
    }
59

60
    return ptrs;
61
}
62

63
container alloc_series ( const size_t *first, size_t len ) {
64
    container ptrs;
65
    const size_t *last = first + len;
66
    void * p;
67

68
    for ( const size_t *iter = first; iter != last; ++iter ) {
69
        if ( NULL == (p = fallback_malloc ( *iter )))
70
            break;
71
        assertAlignment(p);
72
        ptrs.push_back ( p );
73
    }
74

75
    return ptrs;
76
}
77

78
void *pop ( container &c, bool from_end ) {
79
    void *ptr;
80
    if ( from_end ) {
81
        ptr = c.back ();
82
        c.pop_back ();
83
    }
84
    else {
85
        ptr = c.front ();
86
        c.pop_front ();
87
    }
88
    return ptr;
89
}
90

91
void exhaustion_test1 () {
92
    container ptrs;
93

94
    init_heap ();
95
    std::printf("Constant exhaustion tests\n");
96

97
//  Delete in allocation order
98
    ptrs = alloc_series ( 32 );
99
    std::printf("Allocated %zu 32 byte chunks\n", ptrs.size());
100
    print_free_list ();
101
    for ( container::iterator iter = ptrs.begin (); iter != ptrs.end (); ++iter )
102
        fallback_free ( *iter );
103
    print_free_list ();
104
    std::printf("----\n");
105

106
//  Delete in reverse order
107
    ptrs = alloc_series ( 32 );
108
    std::printf("Allocated %zu 32 byte chunks\n", ptrs.size());
109
    for ( container::reverse_iterator iter = ptrs.rbegin (); iter != ptrs.rend (); ++iter )
110
        fallback_free ( *iter );
111
    print_free_list ();
112
    std::printf("----\n");
113

114
//  Alternate deletions
115
    ptrs = alloc_series ( 32 );
116
    std::printf("Allocated %zu 32 byte chunks\n", ptrs.size());
117
    while ( ptrs.size () > 0 )
118
        fallback_free ( pop ( ptrs, ptrs.size () % 1 == 1 ));
119
    print_free_list ();
120
}
121

122
void exhaustion_test2 () {
123
    container ptrs;
124
    init_heap ();
125

126
    std::printf("Growing exhaustion tests\n");
127

128
//  Delete in allocation order
129
    ptrs = alloc_series ( 32, 1.5 );
130

131
    std::printf("Allocated %zu { 32, 48, 72, 108, 162 ... } byte chunks\n",
132
                ptrs.size());
133
    print_free_list ();
134
    for ( container::iterator iter = ptrs.begin (); iter != ptrs.end (); ++iter )
135
        fallback_free ( *iter );
136
    print_free_list ();
137
    std::printf("----\n");
138

139
//  Delete in reverse order
140
    print_free_list ();
141
    ptrs = alloc_series ( 32, 1.5 );
142
    std::printf("Allocated %zu { 32, 48, 72, 108, 162 ... } byte chunks\n",
143
                ptrs.size());
144
    for ( container::reverse_iterator iter = ptrs.rbegin (); iter != ptrs.rend (); ++iter )
145
        fallback_free ( *iter );
146
    print_free_list ();
147
    std::printf("----\n");
148

149
//  Alternate deletions
150
    ptrs = alloc_series ( 32, 1.5 );
151
    std::printf("Allocated %zu { 32, 48, 72, 108, 162 ... } byte chunks\n",
152
                ptrs.size());
153
    while ( ptrs.size () > 0 )
154
        fallback_free ( pop ( ptrs, ptrs.size () % 1 == 1 ));
155
    print_free_list ();
156

157
}
158

159
void exhaustion_test3 () {
160
    const size_t allocs [] = { 124, 60, 252, 60, 4 };
161
    container ptrs;
162
    init_heap ();
163

164
    std::printf("Complete exhaustion tests\n");
165

166
//  Delete in allocation order
167
    ptrs = alloc_series ( allocs, sizeof ( allocs ) / sizeof ( allocs[0] ));
168
    std::printf("Allocated %zu chunks\n", ptrs.size());
169
    print_free_list ();
170
    for ( container::iterator iter = ptrs.begin (); iter != ptrs.end (); ++iter )
171
        fallback_free ( *iter );
172
    print_free_list ();
173
    std::printf("----\n");
174

175
//  Delete in reverse order
176
    print_free_list ();
177
    ptrs = alloc_series ( allocs, sizeof ( allocs ) / sizeof ( allocs[0] ));
178
    std::printf("Allocated %zu chunks\n", ptrs.size());
179
    for ( container::reverse_iterator iter = ptrs.rbegin (); iter != ptrs.rend (); ++iter )
180
        fallback_free ( *iter );
181
    print_free_list ();
182
    std::printf("----\n");
183

184
//  Alternate deletions
185
    ptrs = alloc_series ( allocs, sizeof ( allocs ) / sizeof ( allocs[0] ));
186
    std::printf("Allocated %zu chunks\n", ptrs.size());
187
    while ( ptrs.size () > 0 )
188
        fallback_free ( pop ( ptrs, ptrs.size () % 1 == 1 ));
189
    print_free_list ();
190

191
}
192

193

194
int main () {
195
    print_free_list ();
196

197
    char *p = (char *) fallback_malloc ( 1024 );    // too big!
198
    std::printf("fallback_malloc ( 1024 ) --> %" PRIuPTR"\n", (uintptr_t) p);
199
    print_free_list ();
200

201
    p = (char *) fallback_malloc ( 32 );
202
    std::printf("fallback_malloc ( 32 ) --> %" PRIuPTR"\n", (uintptr_t) (p - heap));
203
    if ( !is_fallback_ptr ( p ))
204
        std::printf("### p is not a fallback pointer!!\n");
205

206
    print_free_list ();
207
    fallback_free ( p );
208
    print_free_list ();
209

210
    exhaustion_test1();
211
    exhaustion_test2();
212
    exhaustion_test3();
213
    return 0;
214
}
215