1 /*
2 * SPDX-License-Identifier: GPL-2.0-or-later
3 *
4 * reserved-region/range.c unit-tests.
5 *
6 * Copyright (C) 2023, Red Hat, Inc.
7 *
8 * Author: Eric Auger <eric.auger@redhat.com>
9 */
10
11 #include "qemu/osdep.h"
12 #include "qemu/range.h"
13 #include "exec/memory.h"
14 #include "qemu/reserved-region.h"
15
16 #define DEBUG 0
17
18 #if DEBUG
print_ranges(const char * prefix,GList * ranges)19 static void print_ranges(const char *prefix, GList *ranges)
20 {
21 GList *l;
22 int i = 0;
23
24 if (!g_list_length(ranges)) {
25 printf("%s is void\n", prefix);
26 return;
27 }
28 for (l = ranges; l; l = l->next) {
29 Range *r = (Range *)l->data;
30
31 printf("%s rev[%i] = [0x%"PRIx64",0x%"PRIx64"]\n",
32 prefix, i, range_lob(r), range_upb(r));
33 i++;
34 }
35 }
36 #endif
37
compare_ranges(const char * prefix,GList * ranges,GList * expected)38 static void compare_ranges(const char *prefix, GList *ranges,
39 GList *expected)
40 {
41 GList *l, *e;
42
43 #if DEBUG
44 print_ranges("out", ranges);
45 print_ranges("expected", expected);
46 #endif
47 if (!expected) {
48 g_assert_true(!ranges);
49 return;
50 }
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;
55
56 g_assert_true(range_lob(r) == range_lob(er) &&
57 range_upb(r) == range_upb(er));
58 }
59 }
60
insert_sorted_range(GList * list,uint64_t lob,uint64_t upb)61 static GList *insert_sorted_range(GList *list, uint64_t lob, uint64_t upb)
62 {
63 Range *new = g_new0(Range, 1);
64
65 range_set_bounds(new, lob, upb);
66 return range_list_insert(list, new);
67 }
68
reset(GList ** in,GList ** out,GList ** expected)69 static void reset(GList **in, GList **out, GList **expected)
70 {
71 g_list_free_full(*in, g_free);
72 g_list_free_full(*out, g_free);
73 g_list_free_full(*expected, g_free);
74 *in = NULL;
75 *out = NULL;
76 *expected = NULL;
77 }
78
79 static void
run_range_inverse_array(const char * prefix,GList ** in,GList ** expected,uint64_t low,uint64_t high)80 run_range_inverse_array(const char *prefix, GList **in, GList **expected,
81 uint64_t low, uint64_t high)
82 {
83 GList *out = NULL;
84 range_inverse_array(*in, &out, low, high);
85 compare_ranges(prefix, out, *expected);
86 reset(in, &out, expected);
87 }
88
check_range_reverse_array(void)89 static void check_range_reverse_array(void)
90 {
91 GList *in = NULL, *expected = NULL;
92
93 /* test 1 */
94
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);
98
99 /* test 2 */
100
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);
105
106 /* test 3 */
107
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);
112
113 /* test 4 */
114
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);
120
121 /* test 5 */
122
123 in = insert_sorted_range(in, 0x0, UINT64_MAX);
124 run_range_inverse_array("test1", &in, &expected, 0x0, UINT64_MAX);
125
126 /* test 6 */
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);
134 }
135
check_range_reverse_array_low_end(void)136 static void check_range_reverse_array_low_end(void)
137 {
138 GList *in = NULL, *expected = NULL;
139
140 /* test 1 */
141 in = insert_sorted_range(in, 0x0, UINT64_MAX);
142 run_range_inverse_array("test1", &in, &expected, 0x10000, 0xFFFFFF);
143
144 /* test 2 */
145
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);
150
151 /* test 3 */
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);
157
158 /* test 4 */
159
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);
165
166 /* test 5 */
167
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);
176
177 /* test 6 */
178
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);
183 }
184
alloc_resv_mem(unsigned type,uint64_t lob,uint64_t upb)185 static ReservedRegion *alloc_resv_mem(unsigned type, uint64_t lob, uint64_t upb)
186 {
187 ReservedRegion *r;
188
189 r = g_new0(ReservedRegion, 1);
190 r->type = type;
191 range_set_bounds(&r->range, lob, upb);
192 return r;
193 }
194
print_resv_region_list(const char * prefix,GList * list,uint32_t expected_length)195 static void print_resv_region_list(const char *prefix, GList *list,
196 uint32_t expected_length)
197 {
198 int i = g_list_length(list);
199
200 g_assert_cmpint(i, ==, expected_length);
201 #if DEBUG
202 i = 0;
203 for (GList *l = list; l; l = l->next) {
204 ReservedRegion *r = (ReservedRegion *)l->data;
205 Range *range = &r->range;
206
207 printf("%s item[%d]=[0x%x, 0x%"PRIx64", 0x%"PRIx64"]\n",
208 prefix, i++, r->type, range_lob(range), range_upb(range));
209 }
210 #endif
211 }
212
free_resv_region(gpointer data)213 static void free_resv_region(gpointer data)
214 {
215 ReservedRegion *reg = (ReservedRegion *)data;
216
217 g_free(reg);
218 }
219
check_resv_region_list_insert(void)220 static void check_resv_region_list_insert(void)
221 {
222 ReservedRegion *r[10];
223 GList *l = NULL;
224
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);
230
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);
238
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);
243
244 /* in the middle */
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);
248
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);
253
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);
258
259 g_list_free_full(l, free_resv_region);
260 l = NULL;
261
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);
268
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);
273
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);
278
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);
283
284 g_list_free_full(l, free_resv_region);
285 l = NULL;
286
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);
290
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);
294
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);
298
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);
302
303 g_list_free_full(l, free_resv_region);
304 }
305
main(int argc,char ** argv)306 int main(int argc, char **argv)
307 {
308 g_test_init(&argc, &argv, NULL);
309
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);
316
317 g_test_run();
318
319 return 0;
320 }
321