2 * SPDX-License-Identifier: GPL-2.0-or-later
4 * reserved-region/range.c unit-tests.
6 * Copyright (C) 2023, Red Hat, Inc.
8 * Author: Eric Auger <eric.auger@redhat.com>
11 #include "qemu/osdep.h"
12 #include "qemu/range.h"
13 #include "exec/memory.h"
14 #include "qemu/reserved-region.h"
19 static void print_ranges(const char *prefix, GList *ranges)
24 if (!g_list_length(ranges)) {
25 printf("%s is void\n", prefix);
28 for (l = ranges; l; l = l->next) {
29 Range *r = (Range *)l->data;
31 printf("%s rev[%i] = [0x%"PRIx64",0x%"PRIx64"]\n",
32 prefix, i, range_lob(r), range_upb(r));
38 static void compare_ranges(const char *prefix, GList *ranges,
44 print_ranges("out", ranges);
45 print_ranges("expected", expected);
47 g_assert_cmpint(g_list_length(ranges), ==, g_list_length(expected));
48 for (l = ranges, e = expected; l ; l = l->next, e = e->next) {
49 Range *r = (Range *)l->data;
50 Range *er = (Range *)e->data;
52 g_assert_true(range_lob(r) == range_lob(er) &&
53 range_upb(r) == range_upb(er));
57 static GList *insert_sorted_range(GList *list, uint64_t lob, uint64_t upb)
59 Range *new = g_new0(Range, 1);
61 range_set_bounds(new, lob, upb);
62 return range_list_insert(list, new);
65 static void reset(GList **in, GList **out, GList **expected)
67 g_list_free_full(*in, g_free);
68 g_list_free_full(*out, g_free);
69 g_list_free_full(*expected, g_free);
76 run_range_inverse_array(const char *prefix, GList **in, GList **expected,
77 uint64_t low, uint64_t high)
80 range_inverse_array(*in, &out, low, high);
81 compare_ranges(prefix, out, *expected);
82 reset(in, &out, expected);
85 static void check_range_reverse_array(void)
87 GList *in = NULL, *expected = NULL;
91 in = insert_sorted_range(in, 0x10000, UINT64_MAX);
92 expected = insert_sorted_range(expected, 0x0, 0xFFFF);
93 run_range_inverse_array("test1", &in, &expected, 0x0, UINT64_MAX);
97 in = insert_sorted_range(in, 0x10000, 0xFFFFFFFFFFFF);
98 expected = insert_sorted_range(expected, 0x0, 0xFFFF);
99 expected = insert_sorted_range(expected, 0x1000000000000, UINT64_MAX);
100 run_range_inverse_array("test1", &in, &expected, 0x0, UINT64_MAX);
104 in = insert_sorted_range(in, 0x0, 0xFFFF);
105 in = insert_sorted_range(in, 0x10000, 0x2FFFF);
106 expected = insert_sorted_range(expected, 0x30000, UINT64_MAX);
107 run_range_inverse_array("test1", &in, &expected, 0x0, UINT64_MAX);
111 in = insert_sorted_range(in, 0x50000, 0x5FFFF);
112 in = insert_sorted_range(in, 0x60000, 0xFFFFFFFFFFFF);
113 expected = insert_sorted_range(expected, 0x0, 0x4FFFF);
114 expected = insert_sorted_range(expected, 0x1000000000000, UINT64_MAX);
115 run_range_inverse_array("test1", &in, &expected, 0x0, UINT64_MAX);
119 in = insert_sorted_range(in, 0x0, UINT64_MAX);
120 run_range_inverse_array("test1", &in, &expected, 0x0, UINT64_MAX);
123 in = insert_sorted_range(in, 0x10000, 0x1FFFF);
124 in = insert_sorted_range(in, 0x30000, 0x6FFFF);
125 in = insert_sorted_range(in, 0x90000, UINT64_MAX);
126 expected = insert_sorted_range(expected, 0x0, 0xFFFF);
127 expected = insert_sorted_range(expected, 0x20000, 0x2FFFF);
128 expected = insert_sorted_range(expected, 0x70000, 0x8FFFF);
129 run_range_inverse_array("test1", &in, &expected, 0x0, UINT64_MAX);
132 static void check_range_reverse_array_low_end(void)
134 GList *in = NULL, *expected = NULL;
137 in = insert_sorted_range(in, 0x0, UINT64_MAX);
138 run_range_inverse_array("test1", &in, &expected, 0x10000, 0xFFFFFF);
142 in = insert_sorted_range(in, 0x0, 0xFFFF);
143 in = insert_sorted_range(in, 0x20000, 0x2FFFF);
144 expected = insert_sorted_range(expected, 0x40000, 0xFFFFFFFFFFFF);
145 run_range_inverse_array("test2", &in, &expected, 0x40000, 0xFFFFFFFFFFFF);
148 in = insert_sorted_range(in, 0x0, 0xFFFF);
149 in = insert_sorted_range(in, 0x20000, 0x2FFFF);
150 in = insert_sorted_range(in, 0x1000000000000, UINT64_MAX);
151 expected = insert_sorted_range(expected, 0x40000, 0xFFFFFFFFFFFF);
152 run_range_inverse_array("test3", &in, &expected, 0x40000, 0xFFFFFFFFFFFF);
156 in = insert_sorted_range(in, 0x0, 0xFFFF);
157 in = insert_sorted_range(in, 0x20000, 0x2FFFF);
158 in = insert_sorted_range(in, 0x1000000000000, UINT64_MAX);
159 expected = insert_sorted_range(expected, 0x30000, 0xFFFFFFFFFFFF);
160 run_range_inverse_array("test4", &in, &expected, 0x20000, 0xFFFFFFFFFFFF);
164 in = insert_sorted_range(in, 0x2000, 0xFFFF);
165 in = insert_sorted_range(in, 0x20000, 0x2FFFF);
166 in = insert_sorted_range(in, 0x100000000, 0x1FFFFFFFF);
167 expected = insert_sorted_range(expected, 0x1000, 0x1FFF);
168 expected = insert_sorted_range(expected, 0x10000, 0x1FFFF);
169 expected = insert_sorted_range(expected, 0x30000, 0xFFFFFFFF);
170 expected = insert_sorted_range(expected, 0x200000000, 0xFFFFFFFFFFFF);
171 run_range_inverse_array("test5", &in, &expected, 0x1000, 0xFFFFFFFFFFFF);
175 in = insert_sorted_range(in, 0x10000000 , 0x1FFFFFFF);
176 in = insert_sorted_range(in, 0x100000000, 0x1FFFFFFFF);
177 expected = insert_sorted_range(expected, 0x0, 0xFFFF);
178 run_range_inverse_array("test6", &in, &expected, 0x0, 0xFFFF);
181 static ReservedRegion *alloc_resv_mem(unsigned type, uint64_t lob, uint64_t upb)
185 r = g_new0(ReservedRegion, 1);
187 range_set_bounds(&r->range, lob, upb);
191 static void print_resv_region_list(const char *prefix, GList *list,
192 uint32_t expected_length)
194 int i = g_list_length(list);
196 g_assert_cmpint(i, ==, expected_length);
199 for (GList *l = list; l; l = l->next) {
200 ReservedRegion *r = (ReservedRegion *)l->data;
201 Range *range = &r->range;
203 printf("%s item[%d]=[0x%x, 0x%"PRIx64", 0x%"PRIx64"]\n",
204 prefix, i++, r->type, range_lob(range), range_upb(range));
209 static void free_resv_region(gpointer data)
211 ReservedRegion *reg = (ReservedRegion *)data;
216 static void check_resv_region_list_insert(void)
218 ReservedRegion *r[10];
221 r[0] = alloc_resv_mem(0xA, 0, 0xFFFF);
222 r[1] = alloc_resv_mem(0xA, 0x20000, 0x2FFFF);
223 l = resv_region_list_insert(l, r[0]);
224 l = resv_region_list_insert(l, r[1]);
225 print_resv_region_list("test1", l, 2);
227 /* adjacent on left */
228 r[2] = alloc_resv_mem(0xB, 0x0, 0xFFF);
229 l = resv_region_list_insert(l, r[2]);
230 /* adjacent on right */
231 r[3] = alloc_resv_mem(0xC, 0x21000, 0x2FFFF);
232 l = resv_region_list_insert(l, r[3]);
233 print_resv_region_list("test2", l, 4);
235 /* exact overlap of D into C*/
236 r[4] = alloc_resv_mem(0xD, 0x21000, 0x2FFFF);
237 l = resv_region_list_insert(l, r[4]);
238 print_resv_region_list("test3", l, 4);
241 r[5] = alloc_resv_mem(0xE, 0x22000, 0x23FFF);
242 l = resv_region_list_insert(l, r[5]);
243 print_resv_region_list("test4", l, 6);
245 /* overwrites several existing ones */
246 r[6] = alloc_resv_mem(0xF, 0x10000, 0x2FFFF);
247 l = resv_region_list_insert(l, r[6]);
248 print_resv_region_list("test5", l, 3);
250 /* contiguous at the end */
251 r[7] = alloc_resv_mem(0x0, 0x30000, 0x40000);
252 l = resv_region_list_insert(l, r[7]);
253 print_resv_region_list("test6", l, 4);
255 g_list_free_full(l, free_resv_region);
258 r[0] = alloc_resv_mem(0x0, 0x10000, 0x1FFFF);
259 l = resv_region_list_insert(l, r[0]);
260 /* insertion before the 1st item */
261 r[1] = alloc_resv_mem(0x1, 0x0, 0xFF);
262 l = resv_region_list_insert(l, r[1]);
263 print_resv_region_list("test8", l, 2);
265 /* collision on the left side */
266 r[2] = alloc_resv_mem(0xA, 0x1200, 0x11FFF);
267 l = resv_region_list_insert(l, r[2]);
268 print_resv_region_list("test9", l, 3);
270 /* collision on the right side */
271 r[3] = alloc_resv_mem(0xA, 0x1F000, 0x2FFFF);
272 l = resv_region_list_insert(l, r[3]);
273 print_resv_region_list("test10", l, 4);
275 /* override everything */
276 r[4] = alloc_resv_mem(0xF, 0x0, UINT64_MAX);
277 l = resv_region_list_insert(l, r[4]);
278 print_resv_region_list("test11", l, 1);
280 g_list_free_full(l, free_resv_region);
283 r[0] = alloc_resv_mem(0xF, 0x1000000000000, UINT64_MAX);
284 l = resv_region_list_insert(l, r[0]);
285 print_resv_region_list("test12", l, 1);
287 r[1] = alloc_resv_mem(0xA, 0x0, 0xFFFFFFF);
288 l = resv_region_list_insert(l, r[1]);
289 print_resv_region_list("test12", l, 2);
291 r[2] = alloc_resv_mem(0xB, 0x100000000, 0x1FFFFFFFF);
292 l = resv_region_list_insert(l, r[2]);
293 print_resv_region_list("test12", l, 3);
295 r[3] = alloc_resv_mem(0x0, 0x010000000, 0x2FFFFFFFF);
296 l = resv_region_list_insert(l, r[3]);
297 print_resv_region_list("test12", l, 3);
299 g_list_free_full(l, free_resv_region);
302 int main(int argc, char **argv)
304 g_test_init(&argc, &argv, NULL);
306 g_test_add_func("/resv-mem/range_reverse_array",
307 check_range_reverse_array);
308 g_test_add_func("/resv-mem/range_reverse_array_low_end",
309 check_range_reverse_array_low_end);
310 g_test_add_func("/resv-mem/resv_region_list_insert",
311 check_resv_region_list_insert);