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
);