1#include <compiler/intrinsic.h>
2#include <console/panic.h>
3#include <enforce.h>
4#include <math/align.h>
5#include <math/bit.h>
6#include <mem/address_range.h>
7#include <mem/alloc.h>
8#include <mem/hhdm.h>
9#include <mem/pmm.h>
10#include <smp/core.h>
11#include <string.h>
12
13#include "vas_internal.h"
14
15static cpu_id_t vas_cpu_id(void) {
16 if (global.current_bootstage < BOOTSTAGE_MID_MP)
17 return 0;
18 return smp_id(cond: TOPC_IRQL);
19}
20
21static enum irql vas_enter(void) TSA_ACQUIRES(IRQL_RAISED) TSA_NO_ANALYSIS {
22 if (global.current_bootstage >= BOOTSTAGE_MID_MP &&
23 (irq_in_interrupt() || irq_in_nmi()))
24 panic(INVALID_CONTEXT, "used from hardware interrupt context");
25 return irql_raise(new_level: IRQL_DISPATCH_LEVEL);
26}
27
28static const size_t mag_sizes[VAS_MAG_CLASSES] = {
29 PAGE_SIZE,
30 5 * PAGE_SIZE,
31 17 * PAGE_SIZE,
32 PAGE_2MB,
33};
34static const uint32_t mag_capacities[VAS_MAG_CLASSES] = {VAS_MAG_CAPACITY, 8, 8,
35 2};
36
37static uint32_t mag_class(size_t size) {
38 for (uint32_t i = 0; i < VAS_MAG_CLASSES; i++)
39 if (mag_sizes[i] == size)
40 return i;
41 return VAS_MAG_CLASSES;
42}
43
44static bool magazines_enabled(struct vas *vas) {
45#ifdef TEST_ENABLED
46 if (vas->magazines_disabled)
47 return false;
48#else
49 cc_ignore(vas);
50#endif
51
52 /* IRQL is a no-op during bootstrap */
53 return global.current_bootstage >= BOOTSTAGE_LATE;
54}
55
56static bool magazine_claim(struct vas_mag_slot *slot, uintptr_t token) {
57 uintptr_t claimed = (token & ~VAS_MAG_STATE_MASK) | VAS_MAG_CLAIMED;
58 return atomic_cas_strong(&slot->token, &token, claimed, mo_acquire, mo_rlx);
59}
60
61static void magazine_publish(struct vas_mag_slot *slot,
62 enum vas_mag_state state) {
63 struct vas_segment *seg = slot->segment;
64 vaddr_t addr = seg->start;
65 atomic_store_release(&seg->type,
66 state == VAS_MAG_LIVE ? VAS_SEG_BUSY : VAS_SEG_CACHED);
67 atomic_store_release(&slot->token, vas_token_make(addr, state));
68}
69
70static vaddr_t magazine_alloc(struct vas_arena *arena, uint32_t cls,
71 size_t align) {
72 struct vas_magazine *mag = &arena->magazines[cls];
73 for (uint32_t n = 0; n < mag_capacities[cls]; n++) {
74 uint32_t i = (mag->recent + n) % mag_capacities[cls];
75 struct vas_mag_slot *slot = &mag->slots[i];
76 uintptr_t token = atomic_load_rlx(&slot->token);
77
78 vaddr_t addr = token & ~VAS_MAG_STATE_MASK;
79
80 bool uncached = (token & VAS_MAG_STATE_MASK) != VAS_MAG_CACHED;
81 bool unaligned = !IS_ALIGNED(addr, align);
82
83 if (uncached || unaligned)
84 continue;
85
86 if (!magazine_claim(slot, token))
87 continue;
88
89 magazine_publish(slot, state: VAS_MAG_LIVE);
90
91#ifdef TEST_ENABLED
92 arena->mag_alloc_hits++;
93#endif
94
95 return addr;
96 }
97 return 0;
98}
99
100static bool magazine_free(struct vas_arena *arena, uint32_t cls, vaddr_t addr) {
101 if (!IS_PAGE_ALIGNED(addr))
102 return false;
103 struct vas_magazine *mag = &arena->magazines[cls];
104 for (uint32_t i = 0; i < mag_capacities[cls]; i++) {
105 struct vas_mag_slot *slot = &mag->slots[i];
106 uintptr_t token = vas_token_make(addr, state: VAS_MAG_LIVE);
107
108 if (atomic_load_rlx(&slot->token) != token ||
109 !magazine_claim(slot, token))
110 continue;
111
112 magazine_publish(slot, state: VAS_MAG_CACHED);
113 mag->recent = i;
114
115#ifdef TEST_ENABLED
116 arena->mag_free_hits++;
117#endif
118
119 return true;
120 }
121 return false;
122}
123
124static size_t segment_key(struct rbt_node *node) {
125 return rbt_entry(node, struct vas_segment, node)->start;
126}
127
128static int32_t segment_cmp(const struct rbt_node *a, const struct rbt_node *b) {
129 vaddr_t l = segment_key(node: (struct rbt_node *) a);
130 vaddr_t r = segment_key(node: (struct rbt_node *) b);
131 return (l > r) - (l < r);
132}
133
134static uint32_t size_to_bin(size_t size) {
135 enforce_precond(size);
136 return 63U - ci_clzll(size);
137}
138
139static void bin_insert(struct vas_arena *arena, struct vas_segment *seg) {
140 uint32_t bin = size_to_bin(size: seg->length);
141 list_head_push_front(h: &arena->free_bins[bin], n: &seg->bin_node);
142 arena->bin_mask = BIT_SET(arena->bin_mask, bin);
143}
144
145static void bin_remove(struct vas_arena *arena, struct vas_segment *seg) {
146 uint32_t bin = size_to_bin(size: seg->length);
147 list_node_delete_init(n: &seg->bin_node);
148 if (list_head_empty(h: &arena->free_bins[bin]))
149 arena->bin_mask = BIT_CLEAR(arena->bin_mask, bin);
150}
151
152static struct vas_segment *segment_alloc(struct vas_arena *arena) {
153#ifdef TEST_ENABLED
154 if (arena->tag_alloc_budget == 0)
155 return NULL;
156 if (arena->tag_alloc_budget > 0)
157 arena->tag_alloc_budget--;
158#endif
159
160 struct vas_segment *seg = fixed_size_alloc(fsr: &arena->fsr);
161 if (seg) {
162 memset(seg, 0, sizeof(*seg));
163 atomic_init(&seg->type, VAS_SEG_FREE);
164 rbt_init_node(n: &seg->node);
165 list_node_init(n: &seg->seg_node);
166 list_node_init(n: &seg->bin_node);
167 }
168 return seg;
169}
170
171static void segment_insert_after(struct vas_arena *arena,
172 struct vas_segment *seg,
173 struct list_node *prev) {
174 rbt_init_node(n: &seg->node);
175 rbt_insert(tree: &arena->tree, new_node: &seg->node);
176 list_node_insert_after(pos: prev, n: &seg->seg_node);
177}
178
179static void segment_delete(struct vas_arena *arena, struct vas_segment *seg) {
180 rbt_delete(tree: &arena->tree, z: &seg->node);
181 list_node_delete(n: &seg->seg_node);
182 fixed_size_free(fsr: &arena->fsr, obj: seg);
183}
184
185static struct vas_segment *segment_find(struct vas_arena *arena, vaddr_t addr) {
186 struct rbt_node *node = arena->tree.root;
187 while (node) {
188 struct vas_segment *seg = rbt_entry(node, struct vas_segment, node);
189 if (addr < seg->start)
190 node = node->left;
191 else if (addr - seg->start >= seg->length)
192 node = node->right;
193 else
194 return seg;
195 }
196 return NULL;
197}
198
199static void arena_init(struct vas_arena *arena, bool is_global) {
200 /* For lock classes, the order is global -> local */
201 if (is_global) {
202 spinlock_init(&arena->lock);
203 } else {
204 spinlock_init(&arena->lock);
205 }
206 rbt_init(t: &arena->tree, get_data: segment_key, compare: segment_cmp);
207 list_head_init(h: &arena->all_segs);
208 for (uint32_t i = 0; i < VAS_BIN_COUNT; i++)
209 list_head_init(h: &arena->free_bins[i]);
210 arena->bin_mask = 0;
211 arena->total_free = 0;
212 for (uint32_t cls = 0; cls < VAS_MAG_CLASSES; cls++) {
213 arena->magazines[cls].recent = 0;
214 for (uint32_t i = 0; i < VAS_MAG_CAPACITY; i++)
215 atomic_init(&arena->magazines[cls].slots[i].token, 0);
216 }
217 struct fixed_size_range_attributes attrs = {
218 .obj_size = sizeof(struct vas_segment),
219 .obj_align = cc_alignof(struct vas_segment),
220 .bootstrap_mode = true,
221 };
222 fixed_size_range_init(fsr: &arena->fsr, attrs: &attrs);
223
224#ifdef TEST_ENABLED
225 arena->tag_alloc_budget = -1;
226#endif
227}
228
229static struct vas_segment *arena_alloc(struct vas_arena *arena, size_t size,
230 size_t align, bool *metadata_failed) {
231 uint64_t mask = arena->bin_mask & (UINT64_MAX << size_to_bin(size));
232 while (mask) {
233 uint32_t bin = ci_ctzll(mask);
234 struct list_node *pos;
235 list_for_each(pos, &arena->free_bins[bin]) {
236 struct vas_segment *seg =
237 list_entry(pos, struct vas_segment, bin_node);
238 size_t pad = (-seg->start) & (align - 1);
239 if (pad > seg->length || size > seg->length - pad)
240 continue;
241
242 size_t tail = seg->length - pad - size;
243
244 struct vas_segment *left = pad ? segment_alloc(arena) : NULL;
245 if (pad && !left) {
246 *metadata_failed = true;
247 return NULL;
248 }
249
250 struct vas_segment *right = tail ? segment_alloc(arena) : NULL;
251 if (tail && !right) {
252 if (left)
253 fixed_size_free(fsr: &arena->fsr, obj: left);
254 *metadata_failed = true;
255 return NULL;
256 }
257
258 /* No fallible operations after this */
259 bin_remove(arena, seg);
260 rbt_delete(tree: &arena->tree, z: &seg->node);
261 if (left) {
262 left->start = seg->start;
263 left->length = pad;
264 left->span_start = seg->span_start;
265 segment_insert_after(arena, seg: left, prev: seg->seg_node.prev);
266 bin_insert(arena, seg: left);
267 }
268 seg->start += pad;
269 seg->length = size;
270 atomic_store_rlx(&seg->type, VAS_SEG_BUSY);
271 rbt_init_node(n: &seg->node);
272 rbt_insert(tree: &arena->tree, new_node: &seg->node);
273 if (right) {
274 right->start = seg->start + size;
275 right->length = tail;
276 right->span_start = seg->span_start;
277 segment_insert_after(arena, seg: right, prev: &seg->seg_node);
278 bin_insert(arena, seg: right);
279 }
280 arena->total_free -= size;
281 return seg;
282 }
283 mask &= mask - 1;
284 }
285 return NULL;
286}
287
288static bool segments_mergeable(struct vas_segment *left,
289 struct vas_segment *right) {
290 return atomic_load_rlx(&left->type) == VAS_SEG_FREE &&
291 atomic_load_rlx(&right->type) == VAS_SEG_FREE &&
292 left->span_start == right->span_start &&
293 left->length == right->start - left->start;
294}
295
296/* The tag already exists */
297static void arena_release(struct vas_arena *arena, struct vas_segment *seg) {
298 arena->total_free += seg->length;
299 atomic_store_rlx(&seg->type, VAS_SEG_FREE);
300 if (seg->seg_node.prev != list_head_sentinel(h: &arena->all_segs)) {
301 struct vas_segment *prev =
302 list_entry(seg->seg_node.prev, struct vas_segment, seg_node);
303 if (segments_mergeable(left: prev, right: seg)) {
304 bin_remove(arena, seg: prev);
305 prev->length += seg->length;
306 segment_delete(arena, seg);
307 seg = prev;
308 }
309 }
310 if (seg->seg_node.next != list_head_sentinel(h: &arena->all_segs)) {
311 struct vas_segment *next =
312 list_entry(seg->seg_node.next, struct vas_segment, seg_node);
313 if (segments_mergeable(left: seg, right: next)) {
314 bin_remove(arena, seg: next);
315 seg->length += next->length;
316 segment_delete(arena, seg: next);
317 }
318 }
319 bin_insert(arena, seg);
320}
321
322/* Arena lock is held */
323static bool magazine_enroll(struct vas *vas, struct vas_arena *arena,
324 struct vas_segment *seg, uint32_t cls,
325 enum vas_mag_state state) {
326 if (!IS_ALIGNED(seg->start, PAGE_SIZE))
327 return false;
328
329 struct vas_mag_slot *slot = NULL;
330 for (uint32_t i = 0; i < mag_capacities[cls]; i++) {
331 if (!atomic_load_rlx(&arena->magazines[cls].slots[i].token)) {
332 slot = &arena->magazines[cls].slots[i];
333 break;
334 }
335 }
336 if (!slot)
337 return false;
338 size_t bytes = atomic_load_rlx(&vas->mag_reserved_bytes);
339 do {
340 if (seg->length > VAS_MAG_BYTE_LIMIT - bytes)
341 return false;
342 } while (!atomic_cas_weak(&vas->mag_reserved_bytes, &bytes,
343 bytes + seg->length, mo_rlx, mo_rlx));
344 seg->mag_slot = slot;
345 slot->segment = seg;
346 magazine_publish(slot, state);
347 return true;
348}
349
350/* Best-effort refill */
351static void magazine_refill(struct vas *vas, struct vas_arena *arena,
352 struct vas_segment *allocated, size_t align) {
353 uint32_t cls = mag_class(size: allocated->length);
354 if (cls == VAS_MAG_CLASSES || !magazines_enabled(vas) ||
355 !magazine_enroll(vas, arena, seg: allocated, cls, state: VAS_MAG_LIVE))
356 return;
357 for (uint32_t i = 1; i < VAS_MAG_REFILL && i < mag_capacities[cls]; i++) {
358 bool failed = false;
359 struct vas_segment *seg =
360 arena_alloc(arena, size: mag_sizes[cls], align, metadata_failed: &failed);
361 if (!seg)
362 break;
363 if (!magazine_enroll(vas, arena, seg, cls, state: VAS_MAG_CACHED)) {
364 arena_release(arena, seg);
365 break;
366 }
367 }
368}
369
370/* Arena lock and a CLAIMED token held */
371static void magazine_release(struct vas *vas, struct vas_arena *arena,
372 struct vas_mag_slot *slot) {
373 struct vas_segment *seg = slot->segment;
374 atomic_fetch_sub_rlx(&vas->mag_reserved_bytes, seg->length);
375 seg->mag_slot = NULL;
376 slot->segment = NULL;
377 arena_release(arena, seg);
378 atomic_store_release(&slot->token, 0);
379}
380
381static void magazine_drain(struct vas *vas, struct vas_arena *arena) {
382 for (uint32_t cls = 0; cls < VAS_MAG_CLASSES; cls++) {
383 for (uint32_t i = 0; i < mag_capacities[cls]; i++) {
384 struct vas_mag_slot *slot = &arena->magazines[cls].slots[i];
385 uintptr_t token = atomic_load_rlx(&slot->token);
386 if ((token & VAS_MAG_STATE_MASK) != VAS_MAG_CACHED)
387 continue;
388 if (magazine_claim(slot, token))
389 magazine_release(vas, arena, slot);
390 }
391 }
392}
393
394static size_t owner_index(struct vas *vas, vaddr_t addr) {
395 return (addr - vas->map_base) >> VAS_CHUNK_SHIFT;
396}
397
398/* Global lock held */
399static void reclaim_locked(struct vas *vas) {
400 for (cpu_id_t cpu = 0; cpu < global.core_count; cpu++) {
401 struct vas_arena *local = &vas->local[cpu];
402
403 enum irql irql = spin_lock(&local->lock);
404 magazine_drain(vas, arena: local);
405 struct list_node *pos, *next;
406
407 list_for_each_safe(pos, next, &local->all_segs) {
408 struct vas_segment *seg =
409 list_entry(pos, struct vas_segment, seg_node);
410
411 if (atomic_load_rlx(&seg->type) != VAS_SEG_FREE ||
412 seg->start != seg->span_start || seg->length != VAS_CHUNK_SIZE)
413 continue;
414
415 vaddr_t start = seg->start;
416 struct vas_segment *parent = segment_find(arena: &vas->global, addr: start);
417 enforce(parent && parent->start == start &&
418 parent->length == VAS_CHUNK_SIZE &&
419 atomic_load_rlx(&parent->type) == VAS_SEG_IMPORTED,
420 CORRUPTION);
421
422 bin_remove(arena: local, seg);
423 local->total_free -= seg->length;
424 segment_delete(arena: local, seg);
425 arena_release(arena: &vas->global, seg: parent);
426 atomic_store_release(&vas->chunk_owner[owner_index(vas, start)],
427 VAS_OWNER_GLOBAL);
428 }
429 spin_unlock(&local->lock, irql);
430 }
431}
432
433/* Global lock held, build allocation and then publish owner */
434static vaddr_t import_alloc(struct vas *vas, uint32_t cpu, size_t size,
435 size_t align, bool *metadata_failed) {
436 struct vas_arena *local = &vas->local[cpu];
437 enum irql irql = spin_lock(&local->lock);
438 struct vas_segment *seg = segment_alloc(arena: local);
439 if (!seg) {
440 *metadata_failed = true;
441 spin_unlock(&local->lock, irql);
442 return 0;
443 }
444 struct vas_segment *parent = arena_alloc(arena: &vas->global, VAS_CHUNK_SIZE,
445 VAS_CHUNK_SIZE, metadata_failed);
446 if (!parent) {
447 fixed_size_free(fsr: &local->fsr, obj: seg);
448 spin_unlock(&local->lock, irql);
449 return 0;
450 }
451
452 atomic_store_rlx(&parent->type, VAS_SEG_IMPORTED);
453 seg->start = seg->span_start = parent->start;
454 seg->length = VAS_CHUNK_SIZE;
455
456 struct rbt_node *prev = rbt_find_predecessor(tree: &local->tree, data: seg->start);
457 struct list_node *before =
458 prev ? &rbt_entry(prev, struct vas_segment, node)->seg_node
459 : list_head_sentinel(h: &local->all_segs);
460
461 segment_insert_after(arena: local, seg, prev: before);
462 bin_insert(arena: local, seg);
463
464 local->total_free += VAS_CHUNK_SIZE;
465
466 struct vas_segment *allocated =
467 arena_alloc(arena: local, size, align, metadata_failed);
468
469 if (!allocated) {
470 bin_remove(arena: local, seg);
471 local->total_free -= VAS_CHUNK_SIZE;
472 segment_delete(arena: local, seg);
473 arena_release(arena: &vas->global, seg: parent);
474 spin_unlock(&local->lock, irql);
475 return 0;
476 }
477
478 atomic_store_release(&vas->chunk_owner[owner_index(vas, parent->start)],
479 cpu);
480 vaddr_t result = allocated->start;
481 magazine_refill(vas, arena: local, allocated, align);
482 spin_unlock(&local->lock, irql);
483 return result;
484}
485
486vaddr_t vas_alloc(struct vas *vas, size_t size, size_t align) {
487 if (!vas || !size || !IS_POW2(align) || size > vas->limit - vas->base)
488 return 0;
489
490 enum irql outer = vas_enter();
491 cpu_id_t cpu = vas_cpu_id();
492
493 bool metadata_failed = false;
494 bool local_request = size <= VAS_CHUNK_SIZE && align <= VAS_CHUNK_SIZE;
495 vaddr_t result = 0;
496 uint32_t cls = mag_class(size);
497
498#ifdef TEST_ENABLED
499 vas->local[cpu].requests[cls]++;
500 vas->local[cpu].alignments[size_to_bin(size: align)]++;
501#endif
502
503 if (cls < VAS_MAG_CLASSES && magazines_enabled(vas)) {
504 result = magazine_alloc(arena: &vas->local[cpu], cls, align);
505 if (result)
506 goto out;
507 }
508
509 if (local_request) {
510 struct vas_arena *local = &vas->local[cpu];
511 enum irql irql = spin_lock(&local->lock);
512 struct vas_segment *seg =
513 arena_alloc(arena: local, size, align, metadata_failed: &metadata_failed);
514
515 if (seg) {
516 result = seg->start;
517 magazine_refill(vas, arena: local, allocated: seg, align);
518 }
519
520 spin_unlock(&local->lock, irql);
521 if (result || metadata_failed)
522 goto out;
523 }
524
525 enum irql irql = spin_lock(&vas->global.lock);
526 for (uint32_t attempt = 0; attempt < 2; attempt++) {
527 if (local_request)
528 result = import_alloc(vas, cpu, size, align, metadata_failed: &metadata_failed);
529
530 if (!result && !metadata_failed) {
531 /* Includes partial edge buckets and aligned small fits */
532 struct vas_segment *seg =
533 arena_alloc(arena: &vas->global, size, align, metadata_failed: &metadata_failed);
534
535 if (seg)
536 result = seg->start;
537 }
538
539 if (result || metadata_failed || attempt == 1)
540 break;
541
542 reclaim_locked(vas);
543 }
544
545 spin_unlock(&vas->global.lock, irql);
546
547out:
548 irql_lower(old_level: outer);
549 return result;
550}
551
552/* Directory is never freed while operations are in flight, recheck
553 * under the lock because reclamation could've moved the chunk */
554static enum irql vas_lock_owner(struct vas *vas, vaddr_t addr,
555 struct vas_arena **out_arena)
556 TSA_ACQUIRES_SPIN(&(*out_arena)->lock) TSA_NO_ANALYSIS {
557 size_t index = owner_index(vas, addr);
558 while (true) {
559 cpu_id_t owner = atomic_load_acq(&vas->chunk_owner[index]);
560 enforce(owner == VAS_OWNER_GLOBAL || owner < global.core_count);
561 struct vas_arena *arena =
562 owner == VAS_OWNER_GLOBAL ? &vas->global : &vas->local[owner];
563 enum irql irql = spin_lock(&arena->lock);
564 if (atomic_load_acq(&vas->chunk_owner[index]) == owner) {
565 *out_arena = arena;
566 return irql;
567 }
568 spin_unlock(&arena->lock, irql);
569 }
570}
571
572bool vas_vaddr_in_vas(struct vas *vas, vaddr_t addr) {
573 return vas && addr >= vas->base && addr < vas->limit;
574}
575
576void vas_free(struct vas *vas, vaddr_t addr, size_t size) {
577 if (!vas_vaddr_in_vas(vas, addr) || !size || size > vas->limit - addr)
578 panic(BAD_FREE, "invalid extent %p+%zu", (void *) addr, size);
579
580 enum irql outer = vas_enter();
581 uint32_t cls = mag_class(size);
582
583 if (cls < VAS_MAG_CLASSES && magazines_enabled(vas) &&
584 magazine_free(arena: &vas->local[vas_cpu_id()], cls, addr)) {
585 irql_lower(old_level: outer);
586 return;
587 }
588
589 struct vas_arena *arena;
590 enum irql irql = vas_lock_owner(vas, addr, out_arena: &arena);
591 struct vas_segment *seg = segment_find(arena, addr);
592
593 if (!seg || atomic_load_rlx(&seg->type) != VAS_SEG_BUSY ||
594 seg->start != addr || seg->length != size)
595 panic(BAD_FREE, "%p+%zu not allocated", (void *) addr, size);
596
597 if (seg->mag_slot) {
598 struct vas_mag_slot *slot = seg->mag_slot;
599 uintptr_t token = vas_token_make(addr, state: VAS_MAG_LIVE);
600 if (!magazine_claim(slot, token))
601 panic(BAD_FREE, "concurrent/duplicate magazine free at %p",
602 (void *) addr);
603
604 magazine_release(vas, arena, slot);
605 } else {
606 arena_release(arena, seg);
607 }
608
609 spin_unlock(&arena->lock, irql);
610 irql_lower(old_level: outer);
611}
612
613bool vas_vaddr_is_allocated(struct vas *vas, vaddr_t addr) {
614 if (!vas_vaddr_in_vas(vas, addr))
615 return false;
616
617 enum irql outer = vas_enter();
618
619 struct vas_arena *arena;
620 enum irql irql = vas_lock_owner(vas, addr, out_arena: &arena);
621 struct vas_segment *seg = segment_find(arena, addr);
622 bool allocated = seg && atomic_load_rlx(&seg->type) == VAS_SEG_BUSY;
623 spin_unlock(&arena->lock, irql);
624
625 irql_lower(old_level: outer);
626 return allocated;
627}
628
629void vas_reclaim(struct vas *vas) {
630 enum irql irql = spin_lock(&vas->global.lock);
631 reclaim_locked(vas);
632 spin_unlock(&vas->global.lock, irql);
633}
634
635void vas_reclaim_freelist_pages(struct vas_arena *arena) {
636 fixed_size_reclaim_freelist_pages(fsr: &arena->fsr);
637}
638
639static void arena_destroy(struct vas_arena *arena) {
640 struct list_node *pos, *next;
641
642 list_for_each_safe(pos, next, &arena->all_segs) {
643 struct vas_segment *seg = list_entry(pos, struct vas_segment, seg_node);
644 if (atomic_load_rlx(&seg->type) == VAS_SEG_FREE)
645 bin_remove(arena, seg);
646
647 segment_delete(arena, seg);
648 }
649
650 vas_reclaim_freelist_pages(arena);
651}
652
653static void space_storage_free(struct vas *vas) {
654 if (vas->bootstrap_pages) {
655 pmm_free_pages(addr: hhdm_ptr_to_paddr(ptr: vas), count: vas->bootstrap_pages);
656 } else {
657 vfree(vas);
658 }
659}
660
661bool vas_destroy(struct vas *vas) {
662 if (!vas)
663 return true;
664
665 vas_reclaim(vas);
666 if (vas->global.total_free != vas->limit - vas->base)
667 return false;
668
669 for (cpu_id_t cpu = 0; cpu < global.core_count; cpu++)
670 arena_destroy(arena: &vas->local[cpu]);
671
672 arena_destroy(arena: &vas->global);
673 space_storage_free(vas);
674 return true;
675}
676
677static struct vas *space_create(vaddr_t base, vaddr_t limit, bool bootstrap) {
678 enforce(global.core_count && global.core_count < VAS_OWNER_GLOBAL);
679 if (!base || limit <= base)
680 return NULL;
681
682 vaddr_t map_base = ALIGN_DOWN(base, VAS_CHUNK_SIZE);
683 size_t owners = ((limit - 1 - map_base) >> VAS_CHUNK_SHIFT) + 1;
684 size_t arena_bytes = global.core_count * sizeof(struct vas_arena);
685 size_t overhead = sizeof(struct vas) + arena_bytes;
686
687 if (owners > (SIZE_MAX - overhead) / sizeof(atomic(cpu_id_t)))
688 return NULL;
689
690 size_t bytes = overhead + owners * sizeof(atomic(cpu_id_t));
691 if (bytes > SIZE_MAX - (PAGE_SIZE - 1))
692 return NULL;
693
694 size_t pages = PAGES_NEEDED_FOR(bytes);
695 struct vas *vas;
696 if (bootstrap) {
697 paddr_t phys = pmm_alloc_pages(pages);
698 if (!phys)
699 return NULL;
700
701 vas = hhdm_paddr_to_ptr(p: phys);
702 memset(vas, 0, pages * PAGE_SIZE);
703 } else {
704 vas = valloc(bytes, ALLOC_ZERO,
705 .behavior =
706 ALLOC_BEHAVIOR_NORMAL | ALLOC_BEHAVIOR_FLAG_MINIMAL);
707 if (!vas)
708 return NULL;
709 }
710
711 vas->base = base;
712 vas->limit = limit;
713 vas->map_base = map_base;
714 vas->owner_count = owners;
715 vas->bootstrap_pages = bootstrap ? pages : 0;
716 vas->local = (void *) ((uint8_t *) vas + sizeof(*vas));
717 vas->chunk_owner = (void *) ((uint8_t *) vas + overhead);
718
719 atomic_init(&vas->mag_reserved_bytes, 0);
720 for (size_t i = 0; i < owners; i++)
721 atomic_init(&vas->chunk_owner[i], VAS_OWNER_GLOBAL);
722
723 arena_init(arena: &vas->global, true);
724 for (cpu_id_t cpu = 0; cpu < global.core_count; cpu++)
725 arena_init(arena: &vas->local[cpu], false);
726
727 struct vas_segment *seg = segment_alloc(arena: &vas->global);
728 if (!seg) {
729 space_storage_free(vas);
730 return NULL;
731 }
732 seg->start = base;
733 seg->length = limit - base;
734 segment_insert_after(arena: &vas->global, seg,
735 prev: list_head_sentinel(h: &vas->global.all_segs));
736 bin_insert(arena: &vas->global, seg);
737 vas->global.total_free = seg->length;
738 return vas;
739}
740
741struct vas *vas_bootstrap(vaddr_t base, vaddr_t limit) {
742 return space_create(base, limit, true);
743}
744
745struct vas *vas_create(vaddr_t base, vaddr_t limit) {
746 return space_create(base, limit, false);
747}
748
749static struct vas *space_from(struct address_range *ar, bool bootstrap) {
750 if (!ar || ar->size > UINTPTR_MAX - ar->base)
751 return NULL;
752
753 return space_create(base: ar->base, limit: ar->base + ar->size, bootstrap);
754}
755
756struct vas *vas_from(struct address_range *ar) {
757 return space_from(ar, false);
758}
759
760struct vas *vas_bootstrap_from(struct address_range *ar) {
761 return space_from(ar, true);
762}
763
764static size_t mapped_extent_size(uintptr_t addr, size_t len) {
765 size_t offset = addr & (PAGE_SIZE - 1);
766 if (!len || len - 1 > UINTPTR_MAX - addr || len > SIZE_MAX - offset ||
767 len + offset > SIZE_MAX - (PAGE_SIZE - 1))
768 return 0;
769 return ALIGN_UP(len + offset, PAGE_SIZE);
770}
771
772void *vas_map_full(struct vas *vas, paddr_t paddr, size_t len,
773 struct vmm_request rq) {
774 size_t size = mapped_extent_size(addr: paddr, len);
775 if (!size)
776 return NULL;
777
778 vaddr_t vaddr = vas_alloc(vas, size, PAGE_SIZE);
779 if (!vaddr)
780 return NULL;
781
782 void *ret = vmm_map_full(paddr, vaddr, len, rq);
783 if (!ret)
784 vas_free(vas, addr: vaddr, size);
785 return ret;
786}
787
788void vas_unmap(struct vas *vas, void *vaddr, size_t len) {
789 size_t size = mapped_extent_size(addr: (vaddr_t) vaddr, len);
790 if (!size)
791 panic("vas_unmap: invalid length %zu", len);
792
793 vaddr_t base = PAGE_ALIGN_DOWN(vaddr);
794 vmm_unmap((void *) base, size);
795 vas_free(vas, addr: base, size);
796}
797
798static void arena_dump(struct vas_arena *arena) {
799 enum irql irql = spin_lock(&arena->lock);
800 struct list_node *pos;
801 list_for_each(pos, &arena->all_segs) {
802 struct vas_segment *seg = list_entry(pos, struct vas_segment, seg_node);
803 enum vas_segment_type type = atomic_load_rlx(&seg->type);
804 printf(format: " %p .. %p len=%zu %s\n", (void *) seg->start,
805 (void *) (seg->start + seg->length), seg->length,
806 type == VAS_SEG_CACHED ? "cached"
807 : type == VAS_SEG_FREE ? "free"
808 : type == VAS_SEG_IMPORTED ? "imported"
809 : "busy");
810 }
811 printf(format: " total_free=%zu\n", arena->total_free);
812 spin_unlock(&arena->lock, irql);
813}
814
815void vas_space_dump(struct vas *vas) {
816 printf(format: "vas %p: %p .. %p chunk_size=%zu\n", vas, (void *) vas->base,
817 (void *) vas->limit, (size_t) VAS_CHUNK_SIZE);
818 printf(format: " global:\n");
819 arena_dump(arena: &vas->global);
820 for (cpu_id_t cpu = 0; cpu < global.core_count; cpu++) {
821 printf(format: " cpu[%zu]:\n", cpu);
822 arena_dump(arena: &vas->local[cpu]);
823 }
824}
825