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
);
48 g_assert_true(!ranges
);
51 g_assert_cmpint(g_list_length(ranges
), ==, g_list_length(expected
));
52 for (l
= ranges
, e
= expected
; l
; l
= l
->next
, e
= e
->next
) {
53 Range
*r
= (Range
*)l
->data
;
54 Range
*er
= (Range
*)e
->data
;
56 g_assert_true(range_lob(r
) == range_lob(er
) &&
57 range_upb(r
) == range_upb(er
));
61 static GList
*insert_sorted_range(GList
*list
, uint64_t lob
, uint64_t upb
)
63 Range
*new = g_new0(Range
, 1);
65 range_set_bounds(new, lob
, upb
);
66 return range_list_insert(list
, new);
69 static void reset(GList
**in
, GList
**out
, GList
**expected
)
71 g_list_free_full(*in
, g_free
);
72 g_list_free_full(*out
, g_free
);
73 g_list_free_full(*expected
, g_free
);
80 run_range_inverse_array(const char *prefix
, GList
**in
, GList
**expected
,
81 uint64_t low
, uint64_t high
)
84 range_inverse_array(*in
, &out
, low
, high
);
85 compare_ranges(prefix
, out
, *expected
);
86 reset(in
, &out
, expected
);
89 static void check_range_reverse_array(void)
91 GList
*in
= NULL
, *expected
= NULL
;
95 in
= insert_sorted_range(in
, 0x10000, UINT64_MAX
);
96 expected
= insert_sorted_range(expected
, 0x0, 0xFFFF);
97 run_range_inverse_array("test1", &in
, &expected
, 0x0, UINT64_MAX
);
101 in
= insert_sorted_range(in
, 0x10000, 0xFFFFFFFFFFFF);
102 expected
= insert_sorted_range(expected
, 0x0, 0xFFFF);
103 expected
= insert_sorted_range(expected
, 0x1000000000000, UINT64_MAX
);
104 run_range_inverse_array("test1", &in
, &expected
, 0x0, UINT64_MAX
);
108 in
= insert_sorted_range(in
, 0x0, 0xFFFF);
109 in
= insert_sorted_range(in
, 0x10000, 0x2FFFF);
110 expected
= insert_sorted_range(expected
, 0x30000, UINT64_MAX
);
111 run_range_inverse_array("test1", &in
, &expected
, 0x0, UINT64_MAX
);
115 in
= insert_sorted_range(in
, 0x50000, 0x5FFFF);
116 in
= insert_sorted_range(in
, 0x60000, 0xFFFFFFFFFFFF);
117 expected
= insert_sorted_range(expected
, 0x0, 0x4FFFF);
118 expected
= insert_sorted_range(expected
, 0x1000000000000, UINT64_MAX
);
119 run_range_inverse_array("test1", &in
, &expected
, 0x0, UINT64_MAX
);
123 in
= insert_sorted_range(in
, 0x0, UINT64_MAX
);
124 run_range_inverse_array("test1", &in
, &expected
, 0x0, UINT64_MAX
);
127 in
= insert_sorted_range(in
, 0x10000, 0x1FFFF);
128 in
= insert_sorted_range(in
, 0x30000, 0x6FFFF);
129 in
= insert_sorted_range(in
, 0x90000, UINT64_MAX
);
130 expected
= insert_sorted_range(expected
, 0x0, 0xFFFF);
131 expected
= insert_sorted_range(expected
, 0x20000, 0x2FFFF);
132 expected
= insert_sorted_range(expected
, 0x70000, 0x8FFFF);
133 run_range_inverse_array("test1", &in
, &expected
, 0x0, UINT64_MAX
);
136 static void check_range_reverse_array_low_end(void)
138 GList
*in
= NULL
, *expected
= NULL
;
141 in
= insert_sorted_range(in
, 0x0, UINT64_MAX
);
142 run_range_inverse_array("test1", &in
, &expected
, 0x10000, 0xFFFFFF);
146 in
= insert_sorted_range(in
, 0x0, 0xFFFF);
147 in
= insert_sorted_range(in
, 0x20000, 0x2FFFF);
148 expected
= insert_sorted_range(expected
, 0x40000, 0xFFFFFFFFFFFF);
149 run_range_inverse_array("test2", &in
, &expected
, 0x40000, 0xFFFFFFFFFFFF);
152 in
= insert_sorted_range(in
, 0x0, 0xFFFF);
153 in
= insert_sorted_range(in
, 0x20000, 0x2FFFF);
154 in
= insert_sorted_range(in
, 0x1000000000000, UINT64_MAX
);
155 expected
= insert_sorted_range(expected
, 0x40000, 0xFFFFFFFFFFFF);
156 run_range_inverse_array("test3", &in
, &expected
, 0x40000, 0xFFFFFFFFFFFF);
160 in
= insert_sorted_range(in
, 0x0, 0xFFFF);
161 in
= insert_sorted_range(in
, 0x20000, 0x2FFFF);
162 in
= insert_sorted_range(in
, 0x1000000000000, UINT64_MAX
);
163 expected
= insert_sorted_range(expected
, 0x30000, 0xFFFFFFFFFFFF);
164 run_range_inverse_array("test4", &in
, &expected
, 0x20000, 0xFFFFFFFFFFFF);
168 in
= insert_sorted_range(in
, 0x2000, 0xFFFF);
169 in
= insert_sorted_range(in
, 0x20000, 0x2FFFF);
170 in
= insert_sorted_range(in
, 0x100000000, 0x1FFFFFFFF);
171 expected
= insert_sorted_range(expected
, 0x1000, 0x1FFF);
172 expected
= insert_sorted_range(expected
, 0x10000, 0x1FFFF);
173 expected
= insert_sorted_range(expected
, 0x30000, 0xFFFFFFFF);
174 expected
= insert_sorted_range(expected
, 0x200000000, 0xFFFFFFFFFFFF);
175 run_range_inverse_array("test5", &in
, &expected
, 0x1000, 0xFFFFFFFFFFFF);
179 in
= insert_sorted_range(in
, 0x10000000 , 0x1FFFFFFF);
180 in
= insert_sorted_range(in
, 0x100000000, 0x1FFFFFFFF);
181 expected
= insert_sorted_range(expected
, 0x0, 0xFFFF);
182 run_range_inverse_array("test6", &in
, &expected
, 0x0, 0xFFFF);
185 static ReservedRegion
*alloc_resv_mem(unsigned type
, uint64_t lob
, uint64_t upb
)
189 r
= g_new0(ReservedRegion
, 1);
191 range_set_bounds(&r
->range
, lob
, upb
);
195 static void print_resv_region_list(const char *prefix
, GList
*list
,
196 uint32_t expected_length
)
198 int i
= g_list_length(list
);
200 g_assert_cmpint(i
, ==, expected_length
);
203 for (GList
*l
= list
; l
; l
= l
->next
) {
204 ReservedRegion
*r
= (ReservedRegion
*)l
->data
;
205 Range
*range
= &r
->range
;
207 printf("%s item[%d]=[0x%x, 0x%"PRIx64
", 0x%"PRIx64
"]\n",
208 prefix
, i
++, r
->type
, range_lob(range
), range_upb(range
));
213 static void free_resv_region(gpointer data
)
215 ReservedRegion
*reg
= (ReservedRegion
*)data
;
220 static void check_resv_region_list_insert(void)
222 ReservedRegion
*r
[10];
225 r
[0] = alloc_resv_mem(0xA, 0, 0xFFFF);
226 r
[1] = alloc_resv_mem(0xA, 0x20000, 0x2FFFF);
227 l
= resv_region_list_insert(l
, r
[0]);
228 l
= resv_region_list_insert(l
, r
[1]);
229 print_resv_region_list("test1", l
, 2);
231 /* adjacent on left */
232 r
[2] = alloc_resv_mem(0xB, 0x0, 0xFFF);
233 l
= resv_region_list_insert(l
, r
[2]);
234 /* adjacent on right */
235 r
[3] = alloc_resv_mem(0xC, 0x21000, 0x2FFFF);
236 l
= resv_region_list_insert(l
, r
[3]);
237 print_resv_region_list("test2", l
, 4);
239 /* exact overlap of D into C*/
240 r
[4] = alloc_resv_mem(0xD, 0x21000, 0x2FFFF);
241 l
= resv_region_list_insert(l
, r
[4]);
242 print_resv_region_list("test3", l
, 4);
245 r
[5] = alloc_resv_mem(0xE, 0x22000, 0x23FFF);
246 l
= resv_region_list_insert(l
, r
[5]);
247 print_resv_region_list("test4", l
, 6);
249 /* overwrites several existing ones */
250 r
[6] = alloc_resv_mem(0xF, 0x10000, 0x2FFFF);
251 l
= resv_region_list_insert(l
, r
[6]);
252 print_resv_region_list("test5", l
, 3);
254 /* contiguous at the end */
255 r
[7] = alloc_resv_mem(0x0, 0x30000, 0x40000);
256 l
= resv_region_list_insert(l
, r
[7]);
257 print_resv_region_list("test6", l
, 4);
259 g_list_free_full(l
, free_resv_region
);
262 r
[0] = alloc_resv_mem(0x0, 0x10000, 0x1FFFF);
263 l
= resv_region_list_insert(l
, r
[0]);
264 /* insertion before the 1st item */
265 r
[1] = alloc_resv_mem(0x1, 0x0, 0xFF);
266 l
= resv_region_list_insert(l
, r
[1]);
267 print_resv_region_list("test8", l
, 2);
269 /* collision on the left side */
270 r
[2] = alloc_resv_mem(0xA, 0x1200, 0x11FFF);
271 l
= resv_region_list_insert(l
, r
[2]);
272 print_resv_region_list("test9", l
, 3);
274 /* collision on the right side */
275 r
[3] = alloc_resv_mem(0xA, 0x1F000, 0x2FFFF);
276 l
= resv_region_list_insert(l
, r
[3]);
277 print_resv_region_list("test10", l
, 4);
279 /* override everything */
280 r
[4] = alloc_resv_mem(0xF, 0x0, UINT64_MAX
);
281 l
= resv_region_list_insert(l
, r
[4]);
282 print_resv_region_list("test11", l
, 1);
284 g_list_free_full(l
, free_resv_region
);
287 r
[0] = alloc_resv_mem(0xF, 0x1000000000000, UINT64_MAX
);
288 l
= resv_region_list_insert(l
, r
[0]);
289 print_resv_region_list("test12", l
, 1);
291 r
[1] = alloc_resv_mem(0xA, 0x0, 0xFFFFFFF);
292 l
= resv_region_list_insert(l
, r
[1]);
293 print_resv_region_list("test12", l
, 2);
295 r
[2] = alloc_resv_mem(0xB, 0x100000000, 0x1FFFFFFFF);
296 l
= resv_region_list_insert(l
, r
[2]);
297 print_resv_region_list("test12", l
, 3);
299 r
[3] = alloc_resv_mem(0x0, 0x010000000, 0x2FFFFFFFF);
300 l
= resv_region_list_insert(l
, r
[3]);
301 print_resv_region_list("test12", l
, 3);
303 g_list_free_full(l
, free_resv_region
);
306 int main(int argc
, char **argv
)
308 g_test_init(&argc
, &argv
, NULL
);
310 g_test_add_func("/resv-mem/range_reverse_array",
311 check_range_reverse_array
);
312 g_test_add_func("/resv-mem/range_reverse_array_low_end",
313 check_range_reverse_array_low_end
);
314 g_test_add_func("/resv-mem/resv_region_list_insert",
315 check_resv_region_list_insert
);