I've got a bunch of comments below. However, I think this test is
sufficient to demonstrate that the allocator works for the use-cases in
this series so it doesn't need to block the rest of the patches. Over-all,
it looks really good. Thanks!
On Mon, May 7, 2018 at 5:30 PM, Scott D Phillips <scott.d.phill...@intel.com
> wrote:
> The test pseudo-randomly makes allocations and deallocations with
> the virtual memory allocator and checks that the results are
> consistent. Specifically, we test that:
>
> * no result from the allocator overlaps an already allocated range
> * allocated memory fulfills the stated alignment requirement
> * a failed result from the allocator could not have been fulfilled
> * memory freed to the allocator can later be allocated again
>
> v2: - fix if() in test() to actually run fill()
> ---
> configure.ac | 1 +
> src/util/Makefile.am | 3 +-
> src/util/meson.build | 1 +
> src/util/tests/vma/Makefile.am | 37 +++++
> src/util/tests/vma/meson.build | 29 ++++
> src/util/tests/vma/vma_random_test.cpp | 239
> +++++++++++++++++++++++++++++++++
> 6 files changed, 309 insertions(+), 1 deletion(-)
> create mode 100644 src/util/tests/vma/Makefile.am
> create mode 100644 src/util/tests/vma/meson.build
> create mode 100644 src/util/tests/vma/vma_random_test.cpp
>
> diff --git a/configure.ac b/configure.ac
> index c0fbfe94135..8dee15cc305 100644
> --- a/configure.ac
> +++ b/configure.ac
> @@ -3111,6 +3111,7 @@ AC_CONFIG_FILES([Makefile
> src/util/Makefile
> src/util/tests/hash_table/Makefile
> src/util/tests/string_buffer/Makefile
> + src/util/tests/vma/Makefile
> src/util/xmlpool/Makefile
> src/vulkan/Makefile])
>
> diff --git a/src/util/Makefile.am b/src/util/Makefile.am
> index 07bf052175b..b51dccdadfd 100644
> --- a/src/util/Makefile.am
> +++ b/src/util/Makefile.am
> @@ -22,7 +22,8 @@
> SUBDIRS = . \
> xmlpool \
> tests/hash_table \
> - tests/string_buffer
> + tests/string_buffer \
> + tests/vma
>
> include Makefile.sources
>
> diff --git a/src/util/meson.build b/src/util/meson.build
> index 14660e0fa0c..c777984e28d 100644
> --- a/src/util/meson.build
> +++ b/src/util/meson.build
> @@ -159,4 +159,5 @@ if with_tests
>
> subdir('tests/hash_table')
> subdir('tests/string_buffer')
> + subdir('tests/vma')
> endif
> diff --git a/src/util/tests/vma/Makefile.am b/src/util/tests/vma/Makefile.
> am
> new file mode 100644
> index 00000000000..1c4dd302bfa
> --- /dev/null
> +++ b/src/util/tests/vma/Makefile.am
> @@ -0,0 +1,37 @@
> +# Copyright © 2018 Intel Corporation
> +#
> +# Permission is hereby granted, free of charge, to any person obtaining a
> +# copy of this software and associated documentation files (the
> "Software"),
> +# to deal in the Software without restriction, including without
> limitation
> +# the rights to use, copy, modify, merge, publish, distribute,
> sublicense,
> +# and/or sell copies of the Software, and to permit persons to whom the
> +# Software is furnished to do so, subject to the following conditions:
> +#
> +# The above copyright notice and this permission notice (including the
> next
> +# paragraph) shall be included in all copies or substantial portions of
> the
> +# Software.
> +#
> +# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
> EXPRESS OR
> +# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
> MERCHANTABILITY,
> +# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT
> SHALL
> +# THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
> OTHER
> +# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
> +# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
> DEALINGS
> +# IN THE SOFTWARE.
> +
> +AM_CPPFLAGS = \
> + -I$(top_srcdir)/include \
> + -I$(top_srcdir)/src/util \
> + $(DEFINES)
> +
> +TESTS = vma_random_test
> +
> +check_PROGRAMS = $(TESTS)
> +
> +vma_random_test_SOURCES = \
> + vma_random_test.cpp
> +
> +vma_random_test_LDADD = \
> + $(top_builddir)/src/util/libmesautil.la
> +
> +EXTRA_DIST = meson.build
> diff --git a/src/util/tests/vma/meson.build b/src/util/tests/vma/meson.
> build
> new file mode 100644
> index 00000000000..53562db312b
> --- /dev/null
> +++ b/src/util/tests/vma/meson.build
> @@ -0,0 +1,29 @@
> +# Copyright © 2018 Intel Corporation
> +
> +# Permission is hereby granted, free of charge, to any person obtaining a
> copy
> +# of this software and associated documentation files (the "Software"),
> to deal
> +# in the Software without restriction, including without limitation the
> rights
> +# to use, copy, modify, merge, publish, distribute, sublicense, and/or
> sell
> +# copies of the Software, and to permit persons to whom the Software is
> +# furnished to do so, subject to the following conditions:
> +
> +# The above copyright notice and this permission notice shall be included
> in
> +# all copies or substantial portions of the Software.
> +
> +# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
> OR
> +# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
> +# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
> THE
> +# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
> +# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
> FROM,
> +# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
> IN THE
> +# SOFTWARE.
> +
> +test(
> + 'vma_random',
> + executable(
> + 'vma_random_test',
> + 'vma_random_test.cpp',
> + include_directories : [inc_include, inc_util],
> + link_with : [libmesa_util],
> + )
> +)
> diff --git a/src/util/tests/vma/vma_random_test.cpp
> b/src/util/tests/vma/vma_random_test.cpp
> new file mode 100644
> index 00000000000..238c361a8e3
> --- /dev/null
> +++ b/src/util/tests/vma/vma_random_test.cpp
> @@ -0,0 +1,239 @@
> +/*
> + * Copyright © 2018 Intel Corporation
> + *
> + * Permission is hereby granted, free of charge, to any person obtaining a
> + * copy of this software and associated documentation files (the
> "Software"),
> + * to deal in the Software without restriction, including without
> limitation
> + * the rights to use, copy, modify, merge, publish, distribute,
> sublicense,
> + * and/or sell copies of the Software, and to permit persons to whom the
> + * Software is furnished to do so, subject to the following conditions:
> + *
> + * The above copyright notice and this permission notice (including the
> next
> + * paragraph) shall be included in all copies or substantial portions of
> the
> + * Software.
> + *
> + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
> EXPRESS OR
> + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
> MERCHANTABILITY,
> + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT
> SHALL
> + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
> OTHER
> + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
> + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
> DEALINGS
> + * IN THE SOFTWARE.
> + */
> +
> +/* it is a test after all */
> +#undef NDEBUG
> +
> +#include <algorithm>
> +#include <cassert>
> +#include <climits>
> +#include <cstdint>
> +#include <cstdio>
> +#include <cstdlib>
> +#include <random>
> +#include <set>
> +#include <vector>
> +
> +#include <err.h>
> +
> +#include "vma.h"
> +
> +namespace {
> +
> +static const uint64_t PAGE_SIZE = 4096;
> +
> +struct allocation {
> + uint64_t address;
> + uint64_t num_pages;
> +};
> +
> +struct allocation_less {
> + constexpr bool operator()(const allocation& lhs, const allocation&
> rhs) const
> + {
> + return lhs.address + lhs.num_pages * PAGE_SIZE <= rhs.address;
>
Maybe it would be better to assert that the two addresses are divisible by
PAGE_SIZE and do
lhs.address / PAGE_SIZE + lhs.num_pages <= rhs.address / PAGE_SIZE
That way you are guaranteed (unless num_pages is bogus) to never have
overflow issues.
> + }
> +};
> +
> +constexpr uint64_t allocation_end(const allocation& a) {
> + return a.address + PAGE_SIZE * a.num_pages;
> +}
> +
> +struct random_test {
> + static const uint64_t MEM_START = 1 * PAGE_SIZE;
> + static const uint64_t MEM_SIZE = 6 * (1ULL << 30 /* GiB */) -
> MEM_START;
>
It would be good to test a full 64-bit address space. I tried to make the
allocator handle it but there are likely bugs there.
> + static const uint64_t MEM_PAGES = (MEM_SIZE >> 12);
>
Maybe divide by PAGE_SIZE to avoid the magic constant?
> +
> + random_test(uint_fast32_t seed)
> + : heap_holes{allocation{MEM_START, MEM_PAGES}}, rand{seed}
> + {
> + util_vma_heap_init(&heap, MEM_START, MEM_SIZE);
> + }
> +
> + void test(unsigned long count)
> + {
> + std::uniform_int_distribution<> one_to_thousand(1, 1000);
> + while (count-- > 0) {
> + int action = one_to_thousand(rand);
> + if (action == 1) fill();
> + else if (action == 2) empty();
> + else if (action < 374) dealloc();
> + else alloc();
> + }
> + }
> +
> + bool alloc(uint64_t size_order=20, uint64_t align_order=20)
> + {
> + std::geometric_distribution<> dist;
> +
> + if (align_order > 19)
> + align_order = std::min(dist(rand), 19);
> + uint64_t align = 1ULL << (align_order + 12);
> +
> + if (size_order > 19)
> + size_order = std::min(dist(rand), 19);
> + uint64_t size_pages = 1ULL << size_order;
> + uint64_t size = size_pages << 12;
>
Multiply by PAGE_SIZE to avoid the magic constant.
> +
> + uint64_t addr = util_vma_heap_alloc(&heap, size, align);
> + // printf("alloc(size:%ld, align:%ld) = %p\n", size, align, (void
> *)addr);
> +
> + if (addr == 0) {
> + /* assert no gaps are present in the tracker for this allocation
> */
> + for (const auto& hole : heap_holes) {
> + uint64_t aligned_start = (hole.address + align - 1) & ~(align
> - 1);
> + uint64_t alignment_pages = (aligned_start - hole.address) /
> PAGE_SIZE;
> + if (alignment_pages >= hole.num_pages)
> + continue;
> + assert(hole.num_pages < size_pages + alignment_pages);
> + }
> + return false;
> + } else {
> + assert(addr == (addr & ~(align - 1)));
> + allocation a{addr, size_pages};
> + auto i = heap_holes.find(a);
> + assert(i != end(heap_holes));
> + allocation hole = *i;
> +
> + assert(hole.address <= addr);
> + assert(hole.num_pages >= size_pages + (addr - hole.address) /
> PAGE_SIZE);
> +
> + heap_holes.erase(i);
> + if (hole.address < a.address) {
> + heap_holes.emplace(allocation{hole.address, (a.address -
> hole.address) / PAGE_SIZE});
> + }
> + if (allocation_end(hole) > allocation_end(a)) {
> + heap_holes.emplace(allocation{allocation_end(a),
> (allocation_end(hole) - allocation_end(a)) / PAGE_SIZE});
> + }
> +
> + allocations.push_back({addr, size_pages});
> + return true;
> + }
> + }
> +
> + void dealloc()
> + {
> + if (allocations.size() == 0)
> + return;
> +
> + std::uniform_int_distribution<> dist(0, allocations.size() - 1);
> + int to_dealloc = dist(rand);
> +
> + std::swap(*(begin(allocations) + to_dealloc),
> + *(begin(allocations) + allocations.size() - 1));
>
Any reason why this isn't just
std::swap(allocations[to_dealloc], allocations[allocations.size() - 1]);
They're the same thing but that looks easier to read to me.
> + allocation a = allocations.back();
> + allocations.pop_back();
> +
> + // printf("free(addr:%p, size:%ld)\n", (void *)a.address,
> a.num_pages << 12);
> + util_vma_heap_free(&heap, a.address, a.num_pages << 12);
>
Multiply by PAGE_SIZE?
> +
> + assert(heap_holes.find(a) == end(heap_holes));
> + auto next = heap_holes.upper_bound(a);
> + if (next != end(heap_holes)) {
> + if (next->address == allocation_end(a)) {
> + allocation x {a.address, a.num_pages + next->num_pages};
> + next = heap_holes.erase(next);
> + next = heap_holes.insert(next, x);
> +
> + if (next != begin(heap_holes)) {
> + auto prev = next;
> + prev--;
> + if (allocation_end(*prev) == next->address) {
> + allocation x {prev->address, prev->num_pages +
> next->num_pages};
> + heap_holes.erase(prev);
> + next = heap_holes.erase(next);
> + heap_holes.insert(next, x);
> + }
> + }
> +
> + return;
> + }
> + }
> +
> + if (next != begin(heap_holes)) {
> + auto prev = next;
> + prev--;
> + if (allocation_end(*prev) == a.address) {
> + allocation x {prev->address, prev->num_pages + a.num_pages};
> + next = heap_holes.erase(prev);
> + heap_holes.insert(next, x);
> +
> + return;
> + }
> + }
> +
> + heap_holes.emplace(a);
> + }
> +
> + void fill()
> + {
> + for (int sz = 19; sz >= 0; sz--) {
> + while (alloc(sz, 0))
> + ;
> + }
> + assert(heap_holes.empty());
> + }
> +
> + void empty()
> + {
> + while (allocations.size() != 0)
> + dealloc();
> + assert(heap_holes.size() == 1);
> + auto& hole = *begin(heap_holes);
> + assert(hole.address == MEM_START && hole.num_pages == MEM_PAGES);
> + }
> +
> + struct util_vma_heap heap;
> + std::set<allocation, allocation_less> heap_holes;
> + std::default_random_engine rand;
> + std::vector<allocation> allocations;
> +};
> +
> +}
> +
> +int main(int argc, char **argv)
> +{
> + unsigned long seed, count;
> + if (argc == 3) {
> + char *arg_end = NULL;
> + seed = strtoul(argv[1], &arg_end, 0);
> + if (!arg_end || *arg_end || seed == ULONG_MAX)
> + errx(1, "invalid seed \"%s\"", argv[1]);
> +
> + arg_end = NULL;
> + count = strtoul(argv[2], &arg_end, 0);
> + if (!arg_end || *arg_end || count == ULONG_MAX)
> + errx(1, "invalid count \"%s\"", argv[2]);
> + } else if (argc == 1) {
> + /* importantly chosen prime numbers. */
> + seed = 8675309;
> + count = 2459;
> + } else {
> + errx(1, "USAGE: %s seed iter_count\n", argv[0]);
> + }
> +
> + random_test r{seed};
> + r.test(count);
> +
> + printf("ok\n");
> + return 0;
> +}
> --
> 2.14.3
>
>
_______________________________________________
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/mesa-dev
