1 /*
2 * Copyright © 2018 Intel Corporation
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice (including the next
12 * paragraph) shall be included in all copies or substantial portions of the
13 * Software.
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
21 * IN THE SOFTWARE.
22 */
23
24 /* it is a test after all */
25 #undef NDEBUG
26
27 #include <algorithm>
28 #include <cassert>
29 #include <climits>
30 #include <cstdint>
31 #include <cstdio>
32 #include <cstdlib>
33 #include <random>
34 #include <set>
35 #include <vector>
36
37 #ifndef _WIN32
38 #include <err.h>
39 #else
40 #define errx(code, msg, ...) \
41 do { \
42 fprintf(stderr, msg, __VA_ARGS__); \
43 exit(code); \
44 } while (0);
45 #endif
46
47 #include "vma.h"
48
49 namespace {
50
51 static const uint64_t MEM_PAGE_SIZE = 4096;
52
53 struct allocation {
54 uint64_t start_page;
55 uint64_t num_pages;
56 };
57
58 struct allocation_less {
operator ()__anon9e6564080111::allocation_less59 bool operator()(const allocation& lhs, const allocation& rhs) const
60 {
61 assert(lhs.start_page + lhs.num_pages > lhs.start_page);
62 return lhs.start_page + lhs.num_pages <= rhs.start_page;
63 }
64 };
65
allocation_end_page(const allocation & a)66 constexpr uint64_t allocation_end_page(const allocation& a) {
67 return a.start_page + a.num_pages;
68 }
69
70 struct random_test {
71 static const uint64_t MEM_START_PAGE = 1;
72 static const uint64_t MEM_SIZE = 0xfffffffffffff000;
73 static const uint64_t MEM_PAGES = MEM_SIZE / MEM_PAGE_SIZE;
74
random_test__anon9e6564080111::random_test75 random_test(uint_fast32_t seed)
76 : heap_holes{allocation{MEM_START_PAGE, MEM_PAGES}}, rand{seed}
77 {
78 util_vma_heap_init(&heap, MEM_START_PAGE * MEM_PAGE_SIZE, MEM_SIZE);
79 }
80
~random_test__anon9e6564080111::random_test81 ~random_test()
82 {
83 util_vma_heap_finish(&heap);
84 }
85
test__anon9e6564080111::random_test86 void test(unsigned long count)
87 {
88 std::uniform_int_distribution<> one_to_thousand(1, 1000);
89 while (count-- > 0) {
90 int action = one_to_thousand(rand);
91 if (action == 1) fill();
92 else if (action == 2) empty();
93 else if (action < 374) dealloc();
94 else alloc();
95 }
96 }
97
alloc__anon9e6564080111::random_test98 bool alloc(uint64_t size_order=52, uint64_t align_order=52)
99 {
100 std::geometric_distribution<> dist;
101
102 if (align_order > 51)
103 align_order = std::min(dist(rand), 51);
104 uint64_t align_pages = 1ULL << align_order;
105 uint64_t align = align_pages * MEM_PAGE_SIZE;
106
107 if (size_order > 51)
108 size_order = std::min(dist(rand), 51);
109 uint64_t size_pages = 1ULL << size_order;
110 uint64_t size = size_pages * MEM_PAGE_SIZE;
111
112 uint64_t addr = util_vma_heap_alloc(&heap, size, align);
113
114 if (addr == 0) {
115 /* assert no gaps are present in the tracker that could satisfy this
116 * allocation.
117 */
118 for (const auto& hole : heap_holes) {
119 uint64_t hole_alignment_pages =
120 (align_pages - (hole.start_page % align_pages)) % align_pages;
121 assert(hole.num_pages < size_pages + hole_alignment_pages);
122 }
123 return false;
124 } else {
125 assert(addr % align == 0);
126 uint64_t addr_page = addr / MEM_PAGE_SIZE;
127 allocation a{addr_page, size_pages};
128 auto i = heap_holes.find(a);
129 assert(i != end(heap_holes));
130 allocation hole = *i;
131
132 assert(hole.start_page <= addr_page);
133 assert(hole.num_pages >= size_pages + addr_page - hole.start_page);
134
135 heap_holes.erase(i);
136 if (hole.start_page < a.start_page) {
137 heap_holes.emplace(allocation{hole.start_page,
138 a.start_page - hole.start_page});
139 }
140 if (allocation_end_page(hole) > allocation_end_page(a)) {
141 heap_holes.emplace(allocation{allocation_end_page(a),
142 allocation_end_page(hole) - allocation_end_page(a)});
143 }
144
145 allocations.push_back(a);
146 return true;
147 }
148 }
149
dealloc__anon9e6564080111::random_test150 void dealloc()
151 {
152 if (allocations.size() == 0)
153 return;
154
155 std::uniform_int_distribution<> dist(0, allocations.size() - 1);
156 int to_dealloc = dist(rand);
157
158 std::swap(allocations.at(to_dealloc), allocations.back());
159 allocation a = allocations.back();
160 allocations.pop_back();
161
162 util_vma_heap_free(&heap, a.start_page * MEM_PAGE_SIZE,
163 a.num_pages * MEM_PAGE_SIZE);
164
165 assert(heap_holes.find(a) == end(heap_holes));
166 auto next = heap_holes.upper_bound(a);
167 if (next != end(heap_holes)) {
168 if (next->start_page == allocation_end_page(a)) {
169 allocation x {a.start_page, a.num_pages + next->num_pages};
170 next = heap_holes.erase(next);
171 next = heap_holes.insert(next, x);
172
173 if (next != begin(heap_holes)) {
174 auto prev = next;
175 prev--;
176 if (allocation_end_page(*prev) == next->start_page) {
177 allocation x {prev->start_page,
178 prev->num_pages + next->num_pages};
179
180 heap_holes.erase(prev);
181 next = heap_holes.erase(next);
182 heap_holes.insert(next, x);
183 }
184 }
185
186 return;
187 }
188 }
189
190 if (next != begin(heap_holes)) {
191 auto prev = next;
192 prev--;
193 if (allocation_end_page(*prev) == a.start_page) {
194 allocation x {prev->start_page, prev->num_pages + a.num_pages};
195 next = heap_holes.erase(prev);
196 heap_holes.insert(next, x);
197
198 return;
199 }
200 }
201
202 heap_holes.emplace(a);
203 }
204
fill__anon9e6564080111::random_test205 void fill()
206 {
207 for (int sz = 51; sz >= 0; sz--) {
208 while (alloc(sz, 0))
209 ;
210 }
211 assert(heap_holes.empty());
212 }
213
empty__anon9e6564080111::random_test214 void empty()
215 {
216 while (allocations.size() != 0)
217 dealloc();
218 assert(heap_holes.size() == 1);
219 auto& hole = *begin(heap_holes);
220 assert(hole.start_page == MEM_START_PAGE && hole.num_pages == MEM_PAGES);
221 }
222
223 struct util_vma_heap heap;
224 std::set<allocation, allocation_less> heap_holes;
225 std::default_random_engine rand;
226 std::vector<allocation> allocations;
227 };
228
229 }
230
main(int argc,char ** argv)231 int main(int argc, char **argv)
232 {
233 unsigned long seed, count;
234 if (argc == 3) {
235 char *arg_end = NULL;
236 seed = strtoul(argv[1], &arg_end, 0);
237 if (!arg_end || *arg_end || seed == ULONG_MAX)
238 errx(1, "invalid seed \"%s\"", argv[1]);
239
240 arg_end = NULL;
241 count = strtoul(argv[2], &arg_end, 0);
242 if (!arg_end || *arg_end || count == ULONG_MAX)
243 errx(1, "invalid count \"%s\"", argv[2]);
244 } else if (argc == 1) {
245 /* importantly chosen prime numbers. */
246 seed = 8675309;
247 count = 2459;
248 } else {
249 errx(1, "USAGE: %s seed iter_count\n", argv[0]);
250 }
251
252 random_test r{(uint_fast32_t)seed};
253 r.test(count);
254
255 printf("ok\n");
256 return 0;
257 }
258