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