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