src/util/tests/vma/vma_random_test.cpp

   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 {
  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
  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
  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
 226 int 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 }