• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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