diff options
Diffstat (limited to 'tests')
| -rw-r--r-- | tests/tcg/multiarch/test-vma.c | 22 | ||||
| -rw-r--r-- | tests/unit/meson.build | 1 | ||||
| -rw-r--r-- | tests/unit/test-interval-tree.c | 209 |
3 files changed, 232 insertions, 0 deletions
diff --git a/tests/tcg/multiarch/test-vma.c b/tests/tcg/multiarch/test-vma.c new file mode 100644 index 0000000000..2893d60334 --- /dev/null +++ b/tests/tcg/multiarch/test-vma.c @@ -0,0 +1,22 @@ +/* + * Test very large vma allocations. + * The qemu out-of-memory condition was within the mmap syscall itself. + * If the syscall actually returns with MAP_FAILED, the test succeeded. + */ +#include <sys/mman.h> + +int main() +{ + int n = sizeof(size_t) == 4 ? 32 : 45; + + for (int i = 28; i < n; i++) { + size_t l = (size_t)1 << i; + void *p = mmap(0, l, PROT_NONE, + MAP_PRIVATE | MAP_ANONYMOUS | MAP_NORESERVE, -1, 0); + if (p == MAP_FAILED) { + break; + } + munmap(p, l); + } + return 0; +} diff --git a/tests/unit/meson.build b/tests/unit/meson.build index b497a41378..ffa444f432 100644 --- a/tests/unit/meson.build +++ b/tests/unit/meson.build @@ -47,6 +47,7 @@ tests = { 'ptimer-test': ['ptimer-test-stubs.c', meson.project_source_root() / 'hw/core/ptimer.c'], 'test-qapi-util': [], 'test-smp-parse': [qom, meson.project_source_root() / 'hw/core/machine-smp.c'], + 'test-interval-tree': [], } if have_system or have_tools diff --git a/tests/unit/test-interval-tree.c b/tests/unit/test-interval-tree.c new file mode 100644 index 0000000000..119817a019 --- /dev/null +++ b/tests/unit/test-interval-tree.c @@ -0,0 +1,209 @@ +/* + * Test interval trees + * + * This work is licensed under the terms of the GNU LGPL, version 2 or later. + * See the COPYING.LIB file in the top-level directory. + * + */ + +#include "qemu/osdep.h" +#include "qemu/interval-tree.h" + +static IntervalTreeNode nodes[20]; +static IntervalTreeRoot root; + +static void rand_interval(IntervalTreeNode *n, uint64_t start, uint64_t last) +{ + gint32 s_ofs, l_ofs, l_max; + + if (last - start > INT32_MAX) { + l_max = INT32_MAX; + } else { + l_max = last - start; + } + s_ofs = g_test_rand_int_range(0, l_max); + l_ofs = g_test_rand_int_range(s_ofs, l_max); + + n->start = start + s_ofs; + n->last = start + l_ofs; +} + +static void test_empty(void) +{ + g_assert(root.rb_root.rb_node == NULL); + g_assert(root.rb_leftmost == NULL); + g_assert(interval_tree_iter_first(&root, 0, UINT64_MAX) == NULL); +} + +static void test_find_one_point(void) +{ + /* Create a tree of a single node, which is the point [1,1]. */ + nodes[0].start = 1; + nodes[0].last = 1; + + interval_tree_insert(&nodes[0], &root); + + g_assert(interval_tree_iter_first(&root, 0, 9) == &nodes[0]); + g_assert(interval_tree_iter_next(&nodes[0], 0, 9) == NULL); + g_assert(interval_tree_iter_first(&root, 0, 0) == NULL); + g_assert(interval_tree_iter_next(&nodes[0], 0, 0) == NULL); + g_assert(interval_tree_iter_first(&root, 0, 1) == &nodes[0]); + g_assert(interval_tree_iter_first(&root, 1, 1) == &nodes[0]); + g_assert(interval_tree_iter_first(&root, 1, 2) == &nodes[0]); + g_assert(interval_tree_iter_first(&root, 2, 2) == NULL); + + interval_tree_remove(&nodes[0], &root); + g_assert(root.rb_root.rb_node == NULL); + g_assert(root.rb_leftmost == NULL); +} + +static void test_find_two_point(void) +{ + IntervalTreeNode *find0, *find1; + + /* Create a tree of a two nodes, which are both the point [1,1]. */ + nodes[0].start = 1; + nodes[0].last = 1; + nodes[1] = nodes[0]; + + interval_tree_insert(&nodes[0], &root); + interval_tree_insert(&nodes[1], &root); + + find0 = interval_tree_iter_first(&root, 0, 9); + g_assert(find0 == &nodes[0] || find0 == &nodes[1]); + + find1 = interval_tree_iter_next(find0, 0, 9); + g_assert(find1 == &nodes[0] || find1 == &nodes[1]); + g_assert(find0 != find1); + + interval_tree_remove(&nodes[1], &root); + + g_assert(interval_tree_iter_first(&root, 0, 9) == &nodes[0]); + g_assert(interval_tree_iter_next(&nodes[0], 0, 9) == NULL); + + interval_tree_remove(&nodes[0], &root); +} + +static void test_find_one_range(void) +{ + /* Create a tree of a single node, which is the range [1,8]. */ + nodes[0].start = 1; + nodes[0].last = 8; + + interval_tree_insert(&nodes[0], &root); + + g_assert(interval_tree_iter_first(&root, 0, 9) == &nodes[0]); + g_assert(interval_tree_iter_next(&nodes[0], 0, 9) == NULL); + g_assert(interval_tree_iter_first(&root, 0, 0) == NULL); + g_assert(interval_tree_iter_first(&root, 0, 1) == &nodes[0]); + g_assert(interval_tree_iter_first(&root, 1, 1) == &nodes[0]); + g_assert(interval_tree_iter_first(&root, 4, 6) == &nodes[0]); + g_assert(interval_tree_iter_first(&root, 8, 8) == &nodes[0]); + g_assert(interval_tree_iter_first(&root, 9, 9) == NULL); + + interval_tree_remove(&nodes[0], &root); +} + +static void test_find_one_range_many(void) +{ + int i; + + /* + * Create a tree of many nodes in [0,99] and [200,299], + * but only one node with exactly [110,190]. + */ + nodes[0].start = 110; + nodes[0].last = 190; + + for (i = 1; i < ARRAY_SIZE(nodes) / 2; ++i) { + rand_interval(&nodes[i], 0, 99); + } + for (; i < ARRAY_SIZE(nodes); ++i) { + rand_interval(&nodes[i], 200, 299); + } + + for (i = 0; i < ARRAY_SIZE(nodes); ++i) { + interval_tree_insert(&nodes[i], &root); + } + + /* Test that we find exactly the one node. */ + g_assert(interval_tree_iter_first(&root, 100, 199) == &nodes[0]); + g_assert(interval_tree_iter_next(&nodes[0], 100, 199) == NULL); + g_assert(interval_tree_iter_first(&root, 100, 109) == NULL); + g_assert(interval_tree_iter_first(&root, 100, 110) == &nodes[0]); + g_assert(interval_tree_iter_first(&root, 111, 120) == &nodes[0]); + g_assert(interval_tree_iter_first(&root, 111, 199) == &nodes[0]); + g_assert(interval_tree_iter_first(&root, 190, 199) == &nodes[0]); + g_assert(interval_tree_iter_first(&root, 192, 199) == NULL); + + /* + * Test that if there are multiple matches, we return the one + * with the minimal start. + */ + g_assert(interval_tree_iter_first(&root, 100, 300) == &nodes[0]); + + /* Test that we don't find it after it is removed. */ + interval_tree_remove(&nodes[0], &root); + g_assert(interval_tree_iter_first(&root, 100, 199) == NULL); + + for (i = 1; i < ARRAY_SIZE(nodes); ++i) { + interval_tree_remove(&nodes[i], &root); + } +} + +static void test_find_many_range(void) +{ + IntervalTreeNode *find; + int i, n; + + n = g_test_rand_int_range(ARRAY_SIZE(nodes) / 3, ARRAY_SIZE(nodes) / 2); + + /* + * Create a fair few nodes in [2000,2999], with the others + * distributed around. + */ + for (i = 0; i < n; ++i) { + rand_interval(&nodes[i], 2000, 2999); + } + for (; i < ARRAY_SIZE(nodes) * 2 / 3; ++i) { + rand_interval(&nodes[i], 1000, 1899); + } + for (; i < ARRAY_SIZE(nodes); ++i) { + rand_interval(&nodes[i], 3100, 3999); + } + + for (i = 0; i < ARRAY_SIZE(nodes); ++i) { + interval_tree_insert(&nodes[i], &root); + } + + /* Test that we find all of the nodes. */ + find = interval_tree_iter_first(&root, 2000, 2999); + for (i = 0; find != NULL; i++) { + find = interval_tree_iter_next(find, 2000, 2999); + } + g_assert_cmpint(i, ==, n); + + g_assert(interval_tree_iter_first(&root, 0, 999) == NULL); + g_assert(interval_tree_iter_first(&root, 1900, 1999) == NULL); + g_assert(interval_tree_iter_first(&root, 3000, 3099) == NULL); + g_assert(interval_tree_iter_first(&root, 4000, UINT64_MAX) == NULL); + + for (i = 0; i < ARRAY_SIZE(nodes); ++i) { + interval_tree_remove(&nodes[i], &root); + } +} + +int main(int argc, char **argv) +{ + g_test_init(&argc, &argv, NULL); + + g_test_add_func("/interval-tree/empty", test_empty); + g_test_add_func("/interval-tree/find-one-point", test_find_one_point); + g_test_add_func("/interval-tree/find-two-point", test_find_two_point); + g_test_add_func("/interval-tree/find-one-range", test_find_one_range); + g_test_add_func("/interval-tree/find-one-range-many", + test_find_one_range_many); + g_test_add_func("/interval-tree/find-many-range", test_find_many_range); + + return g_test_run(); +} |