2 * Copyright © 2018 Intel Corporation
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:
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
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
24 /* it is a test after all */
40 #define errx(code, msg, ...) \
42 fprintf(stderr, msg, __VA_ARGS__); \
51 static const uint64_t MEM_PAGE_SIZE
= 4096;
58 struct allocation_less
{
59 bool operator()(const allocation
& lhs
, const allocation
& rhs
) const
61 assert(lhs
.start_page
+ lhs
.num_pages
> lhs
.start_page
);
62 return lhs
.start_page
+ lhs
.num_pages
<= rhs
.start_page
;
66 constexpr uint64_t allocation_end_page(const allocation
& a
) {
67 return a
.start_page
+ a
.num_pages
;
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
;
75 random_test(uint_fast32_t seed
)
76 : heap_holes
{allocation
{MEM_START_PAGE
, MEM_PAGES
}}, rand
{seed
}
78 util_vma_heap_init(&heap
, MEM_START_PAGE
* MEM_PAGE_SIZE
, MEM_SIZE
);
81 void test(unsigned long count
)
83 std::uniform_int_distribution
<> one_to_thousand(1, 1000);
85 int action
= one_to_thousand(rand
);
86 if (action
== 1) fill();
87 else if (action
== 2) empty();
88 else if (action
< 374) dealloc();
93 bool alloc(uint64_t size_order
=52, uint64_t align_order
=52)
95 std::geometric_distribution
<> dist
;
98 align_order
= std::min(dist(rand
), 51);
99 uint64_t align_pages
= 1ULL << align_order
;
100 uint64_t align
= align_pages
* MEM_PAGE_SIZE
;
103 size_order
= std::min(dist(rand
), 51);
104 uint64_t size_pages
= 1ULL << size_order
;
105 uint64_t size
= size_pages
* MEM_PAGE_SIZE
;
107 uint64_t addr
= util_vma_heap_alloc(&heap
, size
, align
);
110 /* assert no gaps are present in the tracker that could satisfy this
113 for (const auto& hole
: heap_holes
) {
114 uint64_t hole_alignment_pages
=
115 (align_pages
- (hole
.start_page
% align_pages
)) % align_pages
;
116 assert(hole
.num_pages
< size_pages
+ hole_alignment_pages
);
120 assert(addr
% align
== 0);
121 uint64_t addr_page
= addr
/ MEM_PAGE_SIZE
;
122 allocation a
{addr_page
, size_pages
};
123 auto i
= heap_holes
.find(a
);
124 assert(i
!= end(heap_holes
));
125 allocation hole
= *i
;
127 assert(hole
.start_page
<= addr_page
);
128 assert(hole
.num_pages
>= size_pages
+ addr_page
- hole
.start_page
);
131 if (hole
.start_page
< a
.start_page
) {
132 heap_holes
.emplace(allocation
{hole
.start_page
,
133 a
.start_page
- hole
.start_page
});
135 if (allocation_end_page(hole
) > allocation_end_page(a
)) {
136 heap_holes
.emplace(allocation
{allocation_end_page(a
),
137 allocation_end_page(hole
) - allocation_end_page(a
)});
140 allocations
.push_back(a
);
147 if (allocations
.size() == 0)
150 std::uniform_int_distribution
<> dist(0, allocations
.size() - 1);
151 int to_dealloc
= dist(rand
);
153 std::swap(allocations
.at(to_dealloc
), allocations
.back());
154 allocation a
= allocations
.back();
155 allocations
.pop_back();
157 util_vma_heap_free(&heap
, a
.start_page
* MEM_PAGE_SIZE
,
158 a
.num_pages
* MEM_PAGE_SIZE
);
160 assert(heap_holes
.find(a
) == end(heap_holes
));
161 auto next
= heap_holes
.upper_bound(a
);
162 if (next
!= end(heap_holes
)) {
163 if (next
->start_page
== allocation_end_page(a
)) {
164 allocation x
{a
.start_page
, a
.num_pages
+ next
->num_pages
};
165 next
= heap_holes
.erase(next
);
166 next
= heap_holes
.insert(next
, x
);
168 if (next
!= begin(heap_holes
)) {
171 if (allocation_end_page(*prev
) == next
->start_page
) {
172 allocation x
{prev
->start_page
,
173 prev
->num_pages
+ next
->num_pages
};
175 heap_holes
.erase(prev
);
176 next
= heap_holes
.erase(next
);
177 heap_holes
.insert(next
, x
);
185 if (next
!= begin(heap_holes
)) {
188 if (allocation_end_page(*prev
) == a
.start_page
) {
189 allocation x
{prev
->start_page
, prev
->num_pages
+ a
.num_pages
};
190 next
= heap_holes
.erase(prev
);
191 heap_holes
.insert(next
, x
);
197 heap_holes
.emplace(a
);
202 for (int sz
= 51; sz
>= 0; sz
--) {
206 assert(heap_holes
.empty());
211 while (allocations
.size() != 0)
213 assert(heap_holes
.size() == 1);
214 auto& hole
= *begin(heap_holes
);
215 assert(hole
.start_page
== MEM_START_PAGE
&& hole
.num_pages
== MEM_PAGES
);
218 struct util_vma_heap heap
;
219 std::set
<allocation
, allocation_less
> heap_holes
;
220 std::default_random_engine rand
;
221 std::vector
<allocation
> allocations
;
226 int main(int argc
, char **argv
)
228 unsigned long seed
, count
;
230 char *arg_end
= NULL
;
231 seed
= strtoul(argv
[1], &arg_end
, 0);
232 if (!arg_end
|| *arg_end
|| seed
== ULONG_MAX
)
233 errx(1, "invalid seed \"%s\"", argv
[1]);
236 count
= strtoul(argv
[2], &arg_end
, 0);
237 if (!arg_end
|| *arg_end
|| count
== ULONG_MAX
)
238 errx(1, "invalid count \"%s\"", argv
[2]);
239 } else if (argc
== 1) {
240 /* importantly chosen prime numbers. */
244 errx(1, "USAGE: %s seed iter_count\n", argv
[0]);
247 random_test r
{(uint_fast32_t)seed
};