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
49namespace {
50
51static const uint64_t MEM_PAGE_SIZE = 4096;
52
53struct allocation {
54   uint64_t start_page;
55   uint64_t num_pages;
56};
57
58struct allocation_less {
59   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
66constexpr uint64_t allocation_end_page(const allocation& a) {
67   return a.start_page + a.num_pages;
68}
69
70struct 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
75   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
81   void test(unsigned long count)
82   {
83      std::uniform_int_distribution<> one_to_thousand(1, 1000);
84      while (count-- > 0) {
85         int action = one_to_thousand(rand);
86         if (action == 1)          fill();
87         else if (action == 2)     empty();
88         else if (action < 374)    dealloc();
89         else                      alloc();
90      }
91   }
92
93   bool alloc(uint64_t size_order=52, uint64_t align_order=52)
94   {
95      std::geometric_distribution<> dist;
96
97      if (align_order > 51)
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;
101
102      if (size_order > 51)
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;
106
107      uint64_t addr = util_vma_heap_alloc(&heap, size, align);
108
109      if (addr == 0) {
110         /* assert no gaps are present in the tracker that could satisfy this
111          * allocation.
112          */
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);
117         }
118         return false;
119      } else {
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;
126
127         assert(hole.start_page <= addr_page);
128         assert(hole.num_pages >= size_pages + addr_page - hole.start_page);
129
130         heap_holes.erase(i);
131         if (hole.start_page < a.start_page) {
132            heap_holes.emplace(allocation{hole.start_page,
133                     a.start_page - hole.start_page});
134         }
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)});
138         }
139
140         allocations.push_back(a);
141         return true;
142      }
143   }
144
145   void dealloc()
146   {
147      if (allocations.size() == 0)
148         return;
149
150      std::uniform_int_distribution<> dist(0, allocations.size() - 1);
151      int to_dealloc = dist(rand);
152
153      std::swap(allocations.at(to_dealloc), allocations.back());
154      allocation a = allocations.back();
155      allocations.pop_back();
156
157      util_vma_heap_free(&heap, a.start_page * MEM_PAGE_SIZE,
158                         a.num_pages * MEM_PAGE_SIZE);
159
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);
167
168            if (next != begin(heap_holes)) {
169               auto prev = next;
170               prev--;
171               if (allocation_end_page(*prev) == next->start_page) {
172                  allocation x {prev->start_page,
173                        prev->num_pages + next->num_pages};
174
175                  heap_holes.erase(prev);
176                  next = heap_holes.erase(next);
177                  heap_holes.insert(next, x);
178               }
179            }
180
181            return;
182         }
183      }
184
185      if (next != begin(heap_holes)) {
186         auto prev = next;
187         prev--;
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);
192
193            return;
194         }
195      }
196
197      heap_holes.emplace(a);
198   }
199
200   void fill()
201   {
202      for (int sz = 51; sz >= 0; sz--) {
203         while (alloc(sz, 0))
204            ;
205      }
206      assert(heap_holes.empty());
207   }
208
209   void empty()
210   {
211      while (allocations.size() != 0)
212         dealloc();
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);
216   }
217
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;
222};
223
224}
225
226int main(int argc, char **argv)
227{
228   unsigned long seed, count;
229   if (argc == 3) {
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]);
234
235      arg_end = NULL;
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. */
241      seed = 8675309;
242      count = 2459;
243   } else {
244      errx(1, "USAGE: %s seed iter_count\n", argv[0]);
245   }
246
247   random_test r{(uint_fast32_t)seed};
248   r.test(count);
249
250   printf("ok\n");
251   return 0;
252}
253