1#include "mem/tests/test_internal.h"
2#include "mem/vas_internal.h"
3#include <asm.h>
4
5TEST_GROUP_DECLARE(vas);
6
7#define TEST_VAS_BASE 0x700000000000ULL
8
9TEST_DECLARE_UNIT(vas, death_wrong_size, .enabled = TEST_STATE_DISABLED) {
10 struct vas *vas = vas_create(TEST_VAS_BASE, TEST_VAS_BASE + 4 * PAGE_SIZE);
11 TEST_ASSERT_NONNULL(vas);
12
13 vaddr_t addr = vas_alloc(vas, size: 2 * PAGE_SIZE, PAGE_SIZE);
14 TEST_ASSERT_NE(addr, 0);
15
16 vas_free(vas, addr, PAGE_SIZE);
17 return TEST_FAIL("wrong-size free was accepted");
18}
19
20TEST_DECLARE_UNIT(vas, death_double_free, .enabled = TEST_STATE_DISABLED) {
21 struct vas *vas = vas_create(TEST_VAS_BASE, TEST_VAS_BASE + 4 * PAGE_SIZE);
22 TEST_ASSERT_NONNULL(vas);
23
24 vaddr_t addr = vas_alloc(vas, PAGE_SIZE, PAGE_SIZE);
25 TEST_ASSERT_NE(addr, 0);
26 vas_free(vas, addr, PAGE_SIZE);
27 vas_free(vas, addr, PAGE_SIZE);
28
29 return TEST_FAIL("double free was accepted");
30}
31
32TEST_DECLARE_UNIT(vas, death_out_of_range, .enabled = TEST_STATE_DISABLED) {
33 struct vas *vas = vas_create(TEST_VAS_BASE, TEST_VAS_BASE + 4 * PAGE_SIZE);
34 TEST_ASSERT_NONNULL(vas);
35 vas_free(vas, TEST_VAS_BASE - 1, PAGE_SIZE);
36 return TEST_FAIL("out-of-range free was accepted");
37}
38
39static bool arena_valid(struct vas_arena *arena, vaddr_t base, vaddr_t limit,
40 size_t *live, size_t *cached, size_t *enrolled) {
41 size_t free_bytes = 0, free_tags = 0, binned_tags = 0;
42 vaddr_t end = base;
43 struct vas_segment *prev = NULL;
44 struct rbt_node *node = rbt_first(root: &arena->tree);
45 struct list_head *pos;
46 list_for_each(pos, &arena->all_segs) {
47 struct vas_segment *seg = list_entry(pos, struct vas_segment, seg_node);
48 if (!seg->length || seg->start < end || seg->start >= limit ||
49 seg->length > limit - seg->start || node != &seg->node)
50 return false;
51 if (prev && prev->type == VAS_SEG_FREE && seg->type == VAS_SEG_FREE &&
52 prev->span_start == seg->span_start && end == seg->start)
53 return false;
54 end = seg->start + seg->length;
55 if (seg->type == VAS_SEG_FREE) {
56 free_bytes += seg->length;
57 free_tags++;
58 } else if (seg->type == VAS_SEG_BUSY) {
59 *live += seg->length;
60 } else if (seg->type == VAS_SEG_CACHED) {
61 *cached += seg->length;
62 if (!seg->mag_slot)
63 return false;
64 }
65 if (seg->mag_slot) {
66 uintptr_t state =
67 seg->type == VAS_SEG_BUSY ? VAS_MAG_LIVE : VAS_MAG_CACHED;
68 if ((seg->type != VAS_SEG_BUSY && seg->type != VAS_SEG_CACHED) ||
69 seg->mag_slot->segment != seg ||
70 atomic_load(&seg->mag_slot->token) != (seg->start | state))
71 return false;
72 *enrolled += seg->length;
73 }
74 if (seg->type != VAS_SEG_FREE && !list_empty(head: &seg->bin_node))
75 return false;
76 prev = seg;
77 node = rbt_next(node);
78 }
79 if (node || free_bytes != arena->total_free)
80 return false;
81 uint64_t mask = 0;
82 for (uint32_t bin = 0; bin < VAS_BIN_COUNT; bin++) {
83 list_for_each(pos, &arena->free_bins[bin]) {
84 struct vas_segment *seg =
85 list_entry(pos, struct vas_segment, bin_node);
86 if (seg->type != VAS_SEG_FREE ||
87 (63U - __builtin_clzll(seg->length)) != bin ||
88 rbt_search(tree: &arena->tree, data: seg->start) != &seg->node)
89 return false;
90 mask |= 1ULL << bin;
91 if (++binned_tags > free_tags)
92 return false;
93 }
94 }
95 const size_t sizes[] = {PAGE_SIZE, 5 * PAGE_SIZE, 17 * PAGE_SIZE, PAGE_2MB};
96 for (int cls = 0; cls < VAS_MAG_CLASSES; cls++) {
97 for (int i = 0; i < VAS_MAG_CAPACITY; i++) {
98 struct vas_mag_slot *slot = &arena->magazines[cls].slots[i];
99 uintptr_t token = atomic_load(&slot->token);
100 if (!token)
101 continue;
102 if ((token & VAS_MAG_STATE_MASK) == VAS_MAG_CLAIMED ||
103 !slot->segment || slot->segment->mag_slot != slot ||
104 slot->segment->length != sizes[cls] ||
105 rbt_search(tree: &arena->tree, data: token & ~VAS_MAG_STATE_MASK) !=
106 &slot->segment->node)
107 return false;
108 }
109 }
110 return mask == arena->bin_mask && binned_tags == free_tags;
111}
112
113static bool vas_valid(struct vas *vas, size_t expected_live) {
114 size_t live = 0, free_bytes = vas->global.total_free;
115 size_t cached = 0, enrolled = 0;
116 if (!arena_valid(arena: &vas->global, base: vas->base, limit: vas->limit, live: &live, cached: &cached,
117 enrolled: &enrolled))
118 return false;
119 for (cpu_id_t cpu = 0; cpu < global.core_count; cpu++) {
120 struct vas_arena *arena = &vas->local[cpu];
121 if (!arena_valid(arena, base: vas->base, limit: vas->limit, live: &live, cached: &cached,
122 enrolled: &enrolled))
123 return false;
124 free_bytes += arena->total_free;
125 struct list_head *pos;
126 list_for_each(pos, &arena->all_segs) {
127 struct vas_segment *seg =
128 list_entry(pos, struct vas_segment, seg_node);
129 size_t index = (seg->start - vas->map_base) >> VAS_CHUNK_SHIFT;
130 struct rbt_node *parent =
131 rbt_search(tree: &vas->global.tree, data: seg->span_start);
132 if (!parent || atomic_load(&vas->chunk_owner[index]) != cpu ||
133 seg->start < seg->span_start ||
134 seg->start - seg->span_start + seg->length > VAS_CHUNK_SIZE ||
135 rbt_entry(parent, struct vas_segment, node)->type !=
136 VAS_SEG_IMPORTED)
137 return false;
138 }
139 }
140 return live == expected_live &&
141 live + cached + free_bytes == vas->limit - vas->base &&
142 enrolled == atomic_load(&vas->mag_reserved_bytes) &&
143 enrolled <= VAS_MAG_BYTE_LIMIT;
144}
145
146TEST_DECLARE_UNIT(vas, magazine_hits_preserve_query_and_exact_free) {
147 const size_t sizes[] = {PAGE_SIZE, 5 * PAGE_SIZE, 17 * PAGE_SIZE, PAGE_2MB};
148 for (uint32_t cls = 0; cls < VAS_MAG_CLASSES; cls++) {
149 struct vas *vas =
150 vas_create(TEST_VAS_BASE, TEST_VAS_BASE + VAS_CHUNK_SIZE);
151 TEST_ASSERT_NONNULL(vas);
152 enum irql old = irql_raise(new_level: IRQL_DISPATCH_LEVEL);
153 struct vas_arena *arena = &vas->local[smp_id(cond: TOPC_IRQL)];
154 vaddr_t addr = vas_alloc(vas, size: sizes[cls], PAGE_SIZE);
155 TEST_ASSERT_NE(addr, 0);
156 TEST_ASSERT(vas_valid(vas, sizes[cls]));
157 TEST_ASSERT_FALSE(vas_destroy(vas));
158 vas_free(vas, addr, size: sizes[cls]);
159 TEST_ASSERT_FALSE(vas_vaddr_is_allocated(vas, addr));
160 TEST_ASSERT_FALSE(vas_vaddr_is_allocated(vas, addr + sizes[cls] - 1));
161 TEST_ASSERT(vas_valid(vas, 0));
162 arena->tag_alloc_budget = 0;
163 vas->global.tag_alloc_budget = 0;
164 uint64_t hits = arena->mag_alloc_hits;
165 uint64_t frees = arena->mag_free_hits;
166 /* Holding the arena lock makes accidental slow-path entry detectable
167 * by lock checking (and the test watchdog in ordinary builds). */
168 enum irql locked = spin_lock(&arena->lock);
169 bool reused = true;
170 for (uint32_t i = 0; i < 100; i++) {
171 vaddr_t next = vas_alloc(vas, size: sizes[cls], PAGE_SIZE);
172 reused &= next == addr;
173 vas_free(vas, addr: next, size: sizes[cls]);
174 }
175 spin_unlock(&arena->lock, locked);
176 TEST_ASSERT(reused);
177 TEST_ASSERT_EQ(arena->mag_alloc_hits - hits, 100);
178 TEST_ASSERT_EQ(arena->mag_free_hits - frees, 100);
179 TEST_ASSERT(vas_valid(vas, 0));
180 TEST_ASSERT(vas_destroy(vas));
181 irql_lower(old_level: old);
182 }
183 return TEST_SUCCESS;
184}
185
186TEST_DECLARE_UNIT(vas, magazine_alignment_overflow_and_drain) {
187 struct vas *vas = vas_create(TEST_VAS_BASE, TEST_VAS_BASE + VAS_CHUNK_SIZE);
188 TEST_ASSERT_NONNULL(vas);
189 enum irql old = irql_raise(new_level: IRQL_DISPATCH_LEVEL);
190 vaddr_t first = vas_alloc(vas, PAGE_SIZE, PAGE_SIZE);
191 vaddr_t unaligned = vas_alloc(vas, PAGE_SIZE, PAGE_SIZE);
192 TEST_ASSERT_NE(unaligned & (PAGE_2MB - 1), 0);
193 vas_free(vas, addr: unaligned, PAGE_SIZE);
194 vaddr_t aligned = vas_alloc(vas, PAGE_SIZE, PAGE_2MB);
195 TEST_ASSERT_NE(aligned, 0);
196 TEST_ASSERT_NE(aligned, first);
197 TEST_ASSERT_EQ(aligned & (PAGE_2MB - 1), 0);
198 vas_free(vas, addr: first, PAGE_SIZE);
199 vas_free(vas, addr: aligned, PAGE_SIZE);
200 vaddr_t addresses[VAS_MAG_CAPACITY + 5];
201 for (uint32_t i = 0; i < TEST_ARRAY_LEN(addresses); i++) {
202 addresses[i] = vas_alloc(vas, PAGE_SIZE, PAGE_SIZE);
203 TEST_ASSERT_NE(addresses[i], 0);
204 }
205 TEST_ASSERT(
206 vas_valid(vas, sizeof(addresses) / sizeof(*addresses) * PAGE_SIZE));
207 TEST_ASSERT_EQ(atomic_load(&vas->mag_reserved_bytes),
208 VAS_MAG_CAPACITY * PAGE_SIZE);
209 for (uint32_t i = 0; i < TEST_ARRAY_LEN(addresses); i++)
210 vas_free(vas, addr: addresses[i], PAGE_SIZE);
211 TEST_ASSERT(vas_valid(vas, 0));
212 /* A giant request must drain cached reservations, not falsely exhaust. */
213 TEST_ASSERT_EQ(vas_alloc(vas, VAS_CHUNK_SIZE, VAS_CHUNK_SIZE),
214 TEST_VAS_BASE);
215 TEST_ASSERT_EQ(atomic_load(&vas->mag_reserved_bytes), 0);
216 TEST_ASSERT(vas_valid(vas, VAS_CHUNK_SIZE));
217 vas_free(vas, TEST_VAS_BASE, VAS_CHUNK_SIZE);
218 vas_reclaim(vas);
219 TEST_ASSERT_EQ(vas->global.total_free, VAS_CHUNK_SIZE);
220 TEST_ASSERT(vas_destroy(vas));
221 irql_lower(old_level: old);
222 return TEST_SUCCESS;
223}
224
225TEST_DECLARE_UNIT(vas, magazine_refill_failure_keeps_primary_allocation) {
226 struct vas *vas = vas_create(TEST_VAS_BASE, TEST_VAS_BASE + VAS_CHUNK_SIZE);
227 TEST_ASSERT_NONNULL(vas);
228 enum irql old = irql_raise(new_level: IRQL_DISPATCH_LEVEL);
229 /* Import tag + the primary allocation's suffix, no speculative suffix. */
230 vas->local[smp_id(cond: TOPC_IRQL)].tag_alloc_budget = 2;
231 vaddr_t addr = vas_alloc(vas, PAGE_SIZE, PAGE_SIZE);
232 TEST_ASSERT_EQ(addr, TEST_VAS_BASE);
233 TEST_ASSERT_EQ(atomic_load(&vas->mag_reserved_bytes), PAGE_SIZE);
234 TEST_ASSERT(vas_valid(vas, PAGE_SIZE));
235 vas_free(vas, addr, PAGE_SIZE);
236 TEST_ASSERT_EQ(vas_alloc(vas, PAGE_SIZE, PAGE_SIZE), addr);
237 vas_free(vas, addr, PAGE_SIZE);
238 TEST_ASSERT(vas_destroy(vas));
239 irql_lower(old_level: old);
240 return TEST_SUCCESS;
241}
242
243TEST_DECLARE_UNIT(vas, magazine_claim_pins_tag_during_drain) {
244 struct vas *vas = vas_create(TEST_VAS_BASE, TEST_VAS_BASE + VAS_CHUNK_SIZE);
245 TEST_ASSERT_NONNULL(vas);
246 enum irql old = irql_raise(new_level: IRQL_DISPATCH_LEVEL);
247 vaddr_t addr = vas_alloc(vas, PAGE_SIZE, PAGE_SIZE);
248 TEST_ASSERT_NE(addr, 0);
249 struct vas_arena *arena = &vas->local[smp_id(cond: TOPC_IRQL)];
250 struct vas_segment *seg =
251 rbt_entry(rbt_search(&arena->tree, addr), struct vas_segment, node);
252 struct vas_mag_slot *slot = seg->mag_slot;
253 TEST_ASSERT_NONNULL(slot);
254 vas_free(vas, addr, PAGE_SIZE);
255
256 uintptr_t token = addr | VAS_MAG_CACHED;
257 TEST_ASSERT(atomic_compare_exchange_strong(&slot->token, &token,
258 addr | VAS_MAG_CLAIMED));
259 vas_reclaim(vas);
260 TEST_ASSERT_EQ(atomic_load(&vas->mag_reserved_bytes), PAGE_SIZE);
261 TEST_ASSERT_EQ(rbt_search(&arena->tree, addr), &seg->node);
262 TEST_ASSERT_FALSE(vas_vaddr_is_allocated(vas, addr));
263 atomic_store(&seg->type, VAS_SEG_BUSY);
264 atomic_store(&slot->token, addr | VAS_MAG_LIVE);
265 TEST_ASSERT(vas_vaddr_is_allocated(vas, addr + PAGE_SIZE - 1));
266 TEST_ASSERT(vas_valid(vas, PAGE_SIZE));
267 vas_free(vas, addr, PAGE_SIZE);
268 TEST_ASSERT(vas_destroy(vas));
269 irql_lower(old_level: old);
270 return TEST_SUCCESS;
271}
272
273TEST_DECLARE_UNIT(vas, magazine_benchmark, .enabled = TEST_STATE_DISABLED,
274 .print_logs = true) {
275 const size_t sizes[] = {PAGE_SIZE, 5 * PAGE_SIZE, 17 * PAGE_SIZE, PAGE_2MB};
276 const uint32_t iterations = 10000;
277 for (uint32_t cls = 0; cls < TEST_ARRAY_LEN(sizes); cls++) {
278 for (uint32_t cached = 0; cached < 2; cached++) {
279 struct vas *vas =
280 vas_create(TEST_VAS_BASE, TEST_VAS_BASE + VAS_CHUNK_SIZE);
281 TEST_ASSERT_NONNULL(vas);
282 vas->magazines_disabled = !cached;
283 enum irql old = irql_raise(new_level: IRQL_DISPATCH_LEVEL);
284 struct vas_arena *arena = &vas->local[smp_id(cond: TOPC_IRQL)];
285 size_t align = cls == 3 ? PAGE_2MB : PAGE_SIZE;
286 vaddr_t warm = vas_alloc(vas, size: sizes[cls], align);
287 TEST_ASSERT_NE(warm, 0);
288 vas_free(vas, addr: warm, size: sizes[cls]);
289 uint64_t hits = arena->mag_alloc_hits;
290 uint64_t start = rdtsc_ordered();
291 for (uint32_t i = 0; i < iterations; i++) {
292 vaddr_t addr = vas_alloc(vas, size: sizes[cls], align);
293 TEST_ASSERT_NE(addr, 0);
294 vas_free(vas, addr, size: sizes[cls]);
295 }
296 uint64_t ticks = rdtsc_ordered() - start;
297 TEST_ASSERT_EQ(arena->mag_alloc_hits - hits,
298 cached ? iterations : 0);
299 TEST_ASSERT_EQ(arena->requests[cls], iterations + 1);
300 TEST_ASSERT_EQ(arena->alignments[cls == 3 ? 21 : 12],
301 iterations + 1);
302 size_t retained = atomic_load(&vas->mag_reserved_bytes);
303 TEST_ASSERT(vas_valid(vas, 0));
304 TEST_ASSERT(vas_destroy(vas));
305 irql_lower(old_level: old);
306 test_info("size=%zu align=%zu cached=%u ticks/pair=%llu "
307 "retained=%zu hits=%u/%u",
308 sizes[cls], align, cached, ticks / iterations, retained,
309 cached ? iterations : 0, iterations);
310 }
311 }
312 return TEST_SUCCESS;
313}
314
315TEST_DECLARE_UNIT(vas, death_cached_double_free,
316 .enabled = TEST_STATE_DISABLED) {
317 struct vas *vas = vas_create(TEST_VAS_BASE, TEST_VAS_BASE + VAS_CHUNK_SIZE);
318 TEST_ASSERT_NONNULL(vas);
319 enum irql old = irql_raise(new_level: IRQL_DISPATCH_LEVEL);
320 vaddr_t addr = vas_alloc(vas, PAGE_SIZE, PAGE_SIZE);
321 TEST_ASSERT_NE(addr, 0);
322 vas_free(vas, addr, PAGE_SIZE);
323 vas_free(vas, addr, PAGE_SIZE);
324 irql_lower(old_level: old);
325 return TEST_FAIL("cached double free was accepted");
326}
327
328TEST_DECLARE_UNIT(vas, death_magazine_wrong_size,
329 .enabled = TEST_STATE_DISABLED) {
330 struct vas *vas = vas_create(TEST_VAS_BASE, TEST_VAS_BASE + VAS_CHUNK_SIZE);
331 TEST_ASSERT_NONNULL(vas);
332 vaddr_t addr = vas_alloc(vas, size: 5 * PAGE_SIZE, PAGE_SIZE);
333 TEST_ASSERT_NE(addr, 0);
334 vas_free(vas, addr, PAGE_SIZE);
335 return TEST_FAIL("magazine wrong-size free was accepted");
336}
337
338TEST_DECLARE_UNIT(vas, byte_sizes_and_exact_bin_fit) {
339 struct vas *vas = vas_create(TEST_VAS_BASE, TEST_VAS_BASE + 4 * PAGE_SIZE);
340 TEST_ASSERT_NONNULL(vas);
341 vaddr_t three_pages = vas_alloc(vas, size: 3 * PAGE_SIZE, PAGE_SIZE);
342 vaddr_t last = vas_alloc(vas, PAGE_SIZE, PAGE_SIZE);
343 TEST_ASSERT_EQ(three_pages, TEST_VAS_BASE);
344 TEST_ASSERT_EQ(last, TEST_VAS_BASE + 3 * PAGE_SIZE);
345 vas_free(vas, addr: three_pages, size: 3 * PAGE_SIZE);
346 TEST_ASSERT_EQ(vas_alloc(vas, 3 * PAGE_SIZE, PAGE_SIZE), three_pages);
347 vas_free(vas, addr: three_pages, size: 3 * PAGE_SIZE);
348 vas_free(vas, addr: last, PAGE_SIZE);
349 vaddr_t small = vas_alloc(vas, size: 13, align: 1);
350 vaddr_t next = vas_alloc(vas, size: 37, align: 16);
351 TEST_ASSERT_EQ(small, TEST_VAS_BASE);
352 TEST_ASSERT_EQ(next, TEST_VAS_BASE + 16);
353 TEST_ASSERT_FALSE(vas_vaddr_is_allocated(vas, small + 13));
354 TEST_ASSERT(vas_vaddr_is_allocated(vas, next + 36));
355 TEST_ASSERT_FALSE(vas_vaddr_is_allocated(vas, next + 37));
356 TEST_ASSERT(vas_valid(vas, 50));
357 vas_free(vas, addr: small, size: 13);
358 vas_free(vas, addr: next, size: 37);
359 TEST_ASSERT(vas_valid(vas, 0));
360 TEST_ASSERT(vas_destroy(vas));
361 return TEST_SUCCESS;
362}
363
364TEST_DECLARE_UNIT(vas, alignment_and_partial_edge_buckets) {
365 vaddr_t base = TEST_VAS_BASE + PAGE_SIZE;
366 struct vas *vas = vas_create(base, TEST_VAS_BASE + 2 * PAGE_1GB);
367 TEST_ASSERT_NONNULL(vas);
368 size_t aligns[] = {PAGE_SIZE, 64 * 1024, PAGE_2MB, PAGE_1GB};
369 vaddr_t addresses[TEST_ARRAY_LEN(aligns)];
370 for (size_t i = 0; i < TEST_ARRAY_LEN(aligns); i++) {
371 addresses[i] = vas_alloc(vas, size: 3 * PAGE_SIZE, align: aligns[i]);
372 TEST_ASSERT_NE(addresses[i], 0);
373 TEST_ASSERT_EQ(addresses[i] & (aligns[i] - 1), 0);
374 for (size_t j = 0; j < i; j++)
375 TEST_ASSERT(addresses[i] + 3 * PAGE_SIZE <= addresses[j] ||
376 addresses[j] + 3 * PAGE_SIZE <= addresses[i]);
377 }
378
379 /* The unaligned prefix must remain globally usable */
380 vaddr_t prefix = vas_alloc(vas, VAS_CHUNK_SIZE - PAGE_SIZE, PAGE_SIZE);
381 TEST_ASSERT_NE(prefix, 0);
382 TEST_ASSERT(vas_valid(vas, VAS_CHUNK_SIZE + 11 * PAGE_SIZE));
383 vas_free(vas, addr: prefix, VAS_CHUNK_SIZE - PAGE_SIZE);
384 for (size_t i = 0; i < TEST_ARRAY_LEN(aligns); i++)
385 vas_free(vas, addr: addresses[i], size: 3 * PAGE_SIZE);
386 vas_reclaim(vas);
387 TEST_ASSERT_EQ(vas->global.total_free, vas->limit - vas->base);
388 TEST_ASSERT_EQ(atomic_load(&vas->chunk_owner[0]), VAS_OWNER_GLOBAL);
389 TEST_ASSERT(vas_destroy(vas));
390 return TEST_SUCCESS;
391}
392
393TEST_DECLARE_UNIT(vas, all_coalescing_orders) {
394 const uint32_t orders[][3] = {
395 {0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0},
396 };
397 for (size_t order = 0; order < TEST_ARRAY_LEN(orders); order++) {
398 struct vas *vas =
399 vas_create(TEST_VAS_BASE, TEST_VAS_BASE + 3 * PAGE_SIZE);
400 TEST_ASSERT_NONNULL(vas);
401 vaddr_t a[3];
402 for (size_t i = 0; i < 3; i++) {
403 a[i] = vas_alloc(vas, PAGE_SIZE, PAGE_SIZE);
404 TEST_ASSERT_EQ(a[i], TEST_VAS_BASE + i * PAGE_SIZE);
405 }
406 /* Free remains possible with no available tag allocations. */
407 vas->global.tag_alloc_budget = 0;
408 for (size_t i = 0; i < 3; i++) {
409 vas_free(vas, addr: a[orders[order][i]], PAGE_SIZE);
410 TEST_ASSERT(vas_valid(vas, (2 - i) * PAGE_SIZE));
411 }
412 TEST_ASSERT_EQ(vas_alloc(vas, 3 * PAGE_SIZE, PAGE_SIZE), TEST_VAS_BASE);
413 vas_free(vas, TEST_VAS_BASE, size: 3 * PAGE_SIZE);
414 TEST_ASSERT(vas_destroy(vas));
415 }
416 return TEST_SUCCESS;
417}
418
419TEST_DECLARE_UNIT(vas, invalid_requests_and_high_address_arithmetic) {
420 TEST_ASSERT_NULL(vas_create(0, PAGE_SIZE));
421 TEST_ASSERT_NULL(vas_create(TEST_VAS_BASE, TEST_VAS_BASE));
422 TEST_ASSERT_NULL(vas_create(TEST_VAS_BASE, TEST_VAS_BASE - 1));
423 vaddr_t base = UINTPTR_MAX - (4 * PAGE_SIZE - 1);
424 struct vas *vas = vas_create(base, UINTPTR_MAX);
425 TEST_ASSERT_NONNULL(vas);
426 TEST_ASSERT_EQ(vas_alloc(vas, 0, PAGE_SIZE), 0);
427 TEST_ASSERT_EQ(vas_alloc(vas, 1, 0), 0);
428 TEST_ASSERT_EQ(vas_alloc(vas, 1, 3), 0);
429 TEST_ASSERT_EQ(vas_alloc(vas, SIZE_MAX, PAGE_SIZE), 0);
430 TEST_ASSERT_EQ(vas_alloc(vas, PAGE_SIZE, 1ULL << 63), 0);
431 TEST_ASSERT_FALSE(vas_vaddr_is_allocated(vas, base - 1));
432 TEST_ASSERT_FALSE(vas_vaddr_is_allocated(vas, UINTPTR_MAX));
433 size_t length = UINTPTR_MAX - base;
434 TEST_ASSERT_EQ(vas_alloc(vas, length, 1), base);
435 TEST_ASSERT(vas_vaddr_is_allocated(vas, UINTPTR_MAX - 1));
436 TEST_ASSERT_EQ(vas_alloc(vas, 1, 1), 0);
437 TEST_ASSERT_FALSE(vas_destroy(vas));
438 vas_free(vas, addr: base, size: length);
439 TEST_ASSERT(vas_valid(vas, 0));
440 TEST_ASSERT(vas_destroy(vas));
441 return TEST_SUCCESS;
442}
443
444TEST_DECLARE_UNIT(vas, metadata_failure_rolls_back_both_splits) {
445 vaddr_t base = TEST_VAS_BASE + 1;
446 struct vas *vas = vas_create(base, limit: base + 4 * PAGE_SIZE);
447 TEST_ASSERT_NONNULL(vas);
448 for (ssize_t budget = 0; budget < 2; budget++) {
449 vas->global.tag_alloc_budget = budget;
450 TEST_ASSERT_EQ(vas_alloc(vas, PAGE_SIZE, PAGE_SIZE), 0);
451 TEST_ASSERT(vas_valid(vas, 0));
452 TEST_ASSERT_EQ(vas->global.total_free, 4 * PAGE_SIZE);
453 TEST_ASSERT_FALSE(vas_vaddr_is_allocated(vas, base));
454 }
455 vas->global.tag_alloc_budget = -1;
456 vaddr_t addr = vas_alloc(vas, PAGE_SIZE, PAGE_SIZE);
457 TEST_ASSERT_EQ(addr, TEST_VAS_BASE + PAGE_SIZE);
458 vas_free(vas, addr, PAGE_SIZE);
459 TEST_ASSERT(vas_destroy(vas));
460 return TEST_SUCCESS;
461}
462
463TEST_DECLARE_UNIT(vas, import_failure_rolls_back_ownership) {
464 struct vas *vas = vas_create(TEST_VAS_BASE, TEST_VAS_BASE + VAS_CHUNK_SIZE);
465 TEST_ASSERT_NONNULL(vas);
466 for (ssize_t budget = 0; budget < 2; budget++) {
467 for (cpu_id_t cpu = 0; cpu < global.core_count; cpu++)
468 vas->local[cpu].tag_alloc_budget = budget;
469 TEST_ASSERT_EQ(vas_alloc(vas, PAGE_SIZE, PAGE_SIZE), 0);
470 TEST_ASSERT_EQ(atomic_load(&vas->chunk_owner[0]), VAS_OWNER_GLOBAL);
471 TEST_ASSERT(vas_valid(vas, 0));
472 }
473 for (cpu_id_t cpu = 0; cpu < global.core_count; cpu++)
474 vas->local[cpu].tag_alloc_budget = -1;
475 vaddr_t addr = vas_alloc(vas, PAGE_SIZE, PAGE_SIZE);
476 TEST_ASSERT_EQ(addr, TEST_VAS_BASE);
477 vas_free(vas, addr, PAGE_SIZE);
478 TEST_ASSERT(vas_destroy(vas));
479 return TEST_SUCCESS;
480}
481
482TEST_DECLARE_UNIT(vas, large_fallback_reclaims_adjacent_imports) {
483 struct vas *vas =
484 vas_create(TEST_VAS_BASE, TEST_VAS_BASE + 2 * VAS_CHUNK_SIZE);
485 TEST_ASSERT_NONNULL(vas);
486 vaddr_t a = vas_alloc(vas, VAS_CHUNK_SIZE, VAS_CHUNK_SIZE);
487 vaddr_t b = vas_alloc(vas, VAS_CHUNK_SIZE, VAS_CHUNK_SIZE);
488 TEST_ASSERT_NE(a, 0);
489 TEST_ASSERT_NE(b, 0);
490 TEST_ASSERT_NE(a, b);
491 TEST_ASSERT_EQ(vas->global.total_free, 0);
492 vas_free(vas, addr: a, VAS_CHUNK_SIZE);
493 vas_free(vas, addr: b, VAS_CHUNK_SIZE);
494 TEST_ASSERT(vas_valid(vas, 0));
495 vaddr_t large = vas_alloc(vas, size: 2 * VAS_CHUNK_SIZE, PAGE_SIZE);
496 TEST_ASSERT_EQ(large, TEST_VAS_BASE);
497 TEST_ASSERT_EQ(atomic_load(&vas->chunk_owner[0]), VAS_OWNER_GLOBAL);
498 TEST_ASSERT_EQ(atomic_load(&vas->chunk_owner[1]), VAS_OWNER_GLOBAL);
499 TEST_ASSERT(vas_vaddr_is_allocated(vas, large + VAS_CHUNK_SIZE + 7));
500 TEST_ASSERT(vas_valid(vas, 2 * VAS_CHUNK_SIZE));
501 vas_free(vas, addr: large, size: 2 * VAS_CHUNK_SIZE);
502 TEST_ASSERT(vas_destroy(vas));
503 return TEST_SUCCESS;
504}
505
506TEST_DECLARE_UNIT(vas, bootstrap_storage_and_repeated_teardown) {
507 for (size_t i = 0; i < 8; i++) {
508 struct vas *vas =
509 i & 1 ? vas_bootstrap(TEST_VAS_BASE, TEST_VAS_BASE + (8ULL << 40))
510 : vas_create(TEST_VAS_BASE, TEST_VAS_BASE + PAGE_1GB);
511 TEST_ASSERT_NONNULL(vas);
512 if (i & 1)
513 TEST_ASSERT_GT(vas->bootstrap_pages, 1);
514 vaddr_t addr = vas_alloc(vas, PAGE_2MB, PAGE_2MB);
515 TEST_ASSERT_NE(addr, 0);
516 vas_free(vas, addr, PAGE_2MB);
517 TEST_ASSERT(vas_valid(vas, 0));
518 TEST_ASSERT(vas_destroy(vas));
519 }
520 return TEST_SUCCESS;
521}
522
523TEST_DECLARE_UNIT(vas, fragmented_small_arena_has_no_false_exhaustion) {
524 enum { SLOTS = 32, BYTES = 2048, OPERATIONS = 1000 };
525 uint8_t occupied[BYTES] = {0};
526 struct {
527 vaddr_t addr;
528 size_t size;
529 } slots[SLOTS] = {0};
530 struct vas *vas = vas_create(TEST_VAS_BASE, TEST_VAS_BASE + BYTES);
531 TEST_ASSERT_NONNULL(vas);
532 uint64_t random = 0xfee12345;
533 for (size_t op = 0; op < OPERATIONS; op++) {
534 size_t slot = prng_splitmix64_next(state: &random) % SLOTS;
535 if (slots[slot].addr) {
536 size_t offset = slots[slot].addr - TEST_VAS_BASE;
537 memset(occupied + offset, 0, slots[slot].size);
538 vas_free(vas, addr: slots[slot].addr, size: slots[slot].size);
539 slots[slot].addr = 0;
540 } else {
541 size_t size = 1 + prng_splitmix64_next(state: &random) % 127;
542 size_t align = 1ULL << (prng_splitmix64_next(state: &random) % 8);
543 bool fits = false;
544 for (size_t offset = 0; offset + size <= BYTES; offset += align) {
545 size_t n = 0;
546 while (n < size && !occupied[offset + n])
547 n++;
548 if (n == size) {
549 fits = true;
550 break;
551 }
552 }
553 vaddr_t addr = vas_alloc(vas, size, align);
554 TEST_ASSERT_EQ(addr != 0, fits);
555 if (addr) {
556 TEST_ASSERT_EQ(addr & (align - 1), 0);
557 size_t offset = addr - TEST_VAS_BASE;
558 TEST_ASSERT(offset + size <= BYTES);
559 for (size_t n = 0; n < size; n++) {
560 TEST_ASSERT_EQ(occupied[offset + n], 0);
561 occupied[offset + n] = 1;
562 }
563 slots[slot].addr = addr;
564 slots[slot].size = size;
565 }
566 }
567 }
568 for (size_t i = 0; i < SLOTS; i++)
569 if (slots[i].addr)
570 vas_free(vas, addr: slots[i].addr, size: slots[i].size);
571 TEST_ASSERT(vas_valid(vas, 0));
572 TEST_ASSERT(vas_destroy(vas));
573 return TEST_SUCCESS;
574}
575
576TEST_DECLARE_UNIT(vas, partial_bucket_and_alignment_rejection) {
577 vaddr_t base = TEST_VAS_BASE + PAGE_SIZE;
578 struct vas *vas = vas_create(base, limit: base + 2 * PAGE_SIZE);
579 TEST_ASSERT_NONNULL(vas);
580 TEST_ASSERT_EQ(vas_alloc(vas, 2 * PAGE_SIZE, 2 * PAGE_SIZE), 0);
581 TEST_ASSERT_EQ(vas_alloc(vas, 2 * PAGE_SIZE, PAGE_SIZE), base);
582 TEST_ASSERT_EQ(atomic_load(&vas->chunk_owner[0]), VAS_OWNER_GLOBAL);
583 vas_free(vas, addr: base, size: 2 * PAGE_SIZE);
584 TEST_ASSERT(vas_destroy(vas));
585 return TEST_SUCCESS;
586}
587
588TEST_DECLARE_UNIT(vas, seeded_churn_against_interval_oracle) {
589 enum { SLOTS = 64, OPERATIONS = 3000 };
590 struct {
591 vaddr_t addr;
592 size_t size;
593 } slots[SLOTS] = {0};
594 struct vas *vas =
595 vas_create(TEST_VAS_BASE, TEST_VAS_BASE + 8 * VAS_CHUNK_SIZE);
596 TEST_ASSERT_NONNULL(vas);
597 uint64_t seed = ctx->seed ? ctx->seed : 0x5641532026ULL;
598 uint64_t random = seed;
599 size_t live = 0;
600 for (size_t op = 0; op < OPERATIONS; op++) {
601 size_t slot = prng_splitmix64_next(state: &random) % SLOTS;
602 if (slots[slot].addr) {
603 vas_free(vas, addr: slots[slot].addr, size: slots[slot].size);
604 TEST_ASSERT_FALSE(vas_vaddr_is_allocated(vas, slots[slot].addr));
605 live -= slots[slot].size;
606 slots[slot].addr = 0;
607 } else {
608 size_t size =
609 1 + prng_splitmix64_next(state: &random) % (16 * 1024 * 1024);
610 size_t align = 1ULL << (prng_splitmix64_next(state: &random) % 25);
611 vaddr_t addr = vas_alloc(vas, size, align);
612 if (addr) {
613 TEST_ASSERT_EQ(addr & (align - 1), 0);
614 TEST_ASSERT(addr >= vas->base && size <= vas->limit - addr);
615 for (size_t j = 0; j < SLOTS; j++)
616 if (slots[j].addr)
617 TEST_ASSERT_MSG(addr + size <= slots[j].addr ||
618 slots[j].addr + slots[j].size <=
619 addr,
620 "overlap seed=%llu op=%zu", seed, op);
621 slots[slot].addr = addr;
622 slots[slot].size = size;
623 live += size;
624 TEST_ASSERT(vas_vaddr_is_allocated(vas, addr + size - 1));
625 }
626 }
627 if (op % 29 == 0)
628 vas_reclaim(vas);
629 TEST_ASSERT_MSG(vas_valid(vas, live), "seed=%llu op=%zu", seed, op);
630 }
631 for (size_t i = 0; i < SLOTS; i++)
632 if (slots[i].addr)
633 vas_free(vas, addr: slots[i].addr, size: slots[i].size);
634 TEST_ASSERT(vas_valid(vas, 0));
635 TEST_ASSERT(vas_destroy(vas));
636 return TEST_SUCCESS;
637}
638