1/* This slab allocator takes in a size, alloc_flags, and behavior.
2 *
3 * Depending on behavior, we are(n't) allowed to do certain things.
4 *
5 * ┌────────────────────────────────────────────────────────────────┐
6 * │ All allocation paths are influenced by the specified behavior, │
7 * │ but that won't be discussed here to keep things brief. │
8 * │ The general rule is that touching the freequeue may cause │
9 * │ faults, and the physical memory allocator may trigger blocks. │
10 * │ The physical memory allocator can be requested to not block. │
11 * └────────────────────────────────────────────────────────────────┘
12 *
13 * The general allocation flow is as follows:
14 *
15 * If the allocation does not fit in a slab, simply allocate and
16 * map multiple pages to satisfy the allocation. Then, check the
17 * flags and see if we're allowed to do other things. If we can
18 * block/GC, then go through the freequeue and slab GC lists
19 * and do a little bit of flush work if some slabs are too
20 * old/there are too many elements in the freequeue. Reduce
21 * the amount of flush/draining if the fast behavior is specified.
22 *
23 * ┌────────────────────────────────────────────────────────────────┐
24 * │ All slabs anywhere in the slab allocator are nonmovable. │
25 * └────────────────────────────────────────────────────────────────┘
26 *
27 * If the allocation does fit in a slab, then...
28 *
29 * First, we determine if we MUST scale up our allocation to satisfy
30 * cache alignment if cache alignment is requested.
31 *
32 * Second, we check if our magazine has anything. If pageable memory
33 * is requested, and the magazines are very full, and the allocation
34 * size is small, just take from the magazines (they are nonpageable).
35 *
36 * If pageable memory is requested, and the magazines are not so full,
37 * and a larger size is requested, do not take from them.
38 *
39 * Determining whether we MUST take from our magazine depending on
40 * the size of an allocation and the input memory type will be done
41 * via heuristics that will scale steadily both ways.
42 *
43 * ┌────────────────────────────────────────────────────────────────┐
44 * │ The goal is to make sure that pageable allocations do not steal│
45 * │ everything from nonpageable allocations from the magazines │
46 * └────────────────────────────────────────────────────────────────┘
47 *
48 * If nonpageable memory is requested, and the magazines are not empty,
49 * just take memory from the magazines.
50 *
51 * If the magazines are not chosen for the allocation, then things get
52 * a bit hairier.
53 *
54 * First, check if the allocation MUST be from the local node. If this
55 * is the case, simply allocate from the local pageable/nonpageable slab
56 * cache.
57 *
58 * ┌────────────────────────────────────────────────────────────────┐
59 * │ If an allocation is pageable, then there will be a heuristic │
60 * │ that checks whether or not there are so many things in a given │
61 * │ nonpageable cache that it is worth it to allocate from it. │
62 * └────────────────────────────────────────────────────────────────┘
63 *
64 * If the slab cache has nothing available, just map a new page to the local
65 * node if the allocation MUST be from the local node.
66 *
67 * ┌────────────────────────────────────────────────────────────────┐
68 * │ Slab creation uses a GC list of slabs that are going to be │
69 * │ destroyed, so instead of constantly calling into the physical │
70 * │ memory allocator, slabs can be reused. │
71 * └────────────────────────────────────────────────────────────────┘
72 *
73 * Now, if the allocation does not need to come from the local node, then things
74 * get real fun. Each slab domain has a zonelist for the other domains relative
75 * to itself, sorted by distance. This list is traversed, and depending on slab
76 * cache slab availability and physical memory availability, a cache is selected
77 * for allocation. A scoring heuristic is applied to bias the result towards
78 * within the selected locality. If flexible locality is selected, the
79 * algo will potentially select a further node if it has high availability
80 * compared to the closer nodes.
81 *
82 * The slab cache picking logic may be biased based on given input arguments.
83 * For example, if a FAST behavior is specified, the slab cache picking logic
84 * might apply a higher weight to the local cache to minimize lock contention
85 * and maximize memory locality.
86 *
87 * Now a slab cache MUST have been selected for this allocation. If the slab
88 * cache is the local node, then first try and free the freequeue to
89 * the local magazines or to the slab cache until a given amount of target
90 * elements is flushed from it or the freequeue becomes empty. Afterwards,
91 * if there is still an unsatisfactory amount of elements in the per-cpu
92 * cache/magazine (too few), allocations from the slab cache are performed.
93 *
94 * Just like all slab cache allocations, the same heuristics on picking
95 * whether or not a nonpageable cache MUST fulfill a pageable allocation,
96 * and the use of the GC list for creation of new slabs are used here.
97 *
98 * Finally, we MAY have a memory address to return. If we have none,
99 * then we have likely ran out of memory, and so, MUST return NULL.
100 *
101 * If we do return NULL after the initial allocation, and a flexible
102 * locality is permitted, then we just try again with a further node.
103 *
104 * But, we are not done yet. If the FAST behavior is not specified,
105 * and if we are allowed to take faults, the slab GC list will be
106 * checked to figure out what slabs MUST be fully deleted (since
107 * this will free them up for use in other memory management subsystems).
108 *
109 * This selection operation depends on a variety of things, such as the
110 * memory pressure (recent usage), recycling frequency, and other
111 * heuristics about recent memory recycling usage.
112 *
113 * After the slab GC list has some elements truly deleted (or not, if
114 * the heuristics determine that it is not necessary), we are finally
115 * done, and can return the memory address that we had been anticipating
116 * all along.
117 *
118 * The GC list uses a red-black tree ordered by slab enqueue time,
119 * so the oldest slab can be picked for deletion in amortized time.
120 *
121 */
122
123#include <compiler/core.h>
124#include <compiler/intrinsic.h>
125#include <console/printf.h>
126#include <enforce.h>
127#include <math/align.h>
128#include <math/arith.h>
129#include <math/bit.h>
130#include <math/min_max.h>
131#include <math/range.h>
132#include <math/sort.h>
133#include <mem/address_range.h>
134#include <mem/alloc.h>
135#include <mem/asan.h>
136#include <mem/domain.h>
137#include <mem/pmm.h>
138#include <mem/simple_alloc.h>
139#include <mem/slab.h>
140#include <mem/vas.h>
141#include <mem/vmm.h>
142#include <sch/sched.h>
143#include <smp/core.h>
144#include <stack_depot.h>
145#include <static_call.h>
146#include <stdbool.h>
147#include <stdint.h>
148#include <string.h>
149#include <sync/spinlock.h>
150
151#include "internal.h"
152#include "mem/domain/internal.h"
153#include "stat_internal.h"
154
155/* const size_t slab_class_sizes_const[] = {
156 SLAB_MIN_SIZE, 16, 24, 32, 40, 48, 56, 64, 80, 96,
157 112, 128, 144, 160, 176, 192, 224, 256, 320, 384,
158 448, 512, 640, 768, 896, SLAB_MAX_SIZE}; */
159
160const size_t slab_class_sizes_const[] = {
161 SLAB_MIN_SIZE, 16, 32, 64, 96, 128, 192, 256, 512, SLAB_MAX_SIZE};
162
163#define SLAB_CLASS_SIZES_CONST_COUNT \
164 sizeof(slab_class_sizes_const) / sizeof(*slab_class_sizes_const)
165
166ADDRESS_RANGE_DEFINE(
167 slab, .base = SLAB_HEAP_START, .size = SLAB_HEAP_END - SLAB_HEAP_START,
168 .flags = ADDRESS_RANGE_STATIC,
169 .page_fault_handler = &slab_page_fault_handler
170 /* alignment does not need to be provided for static entries */);
171
172struct slab_globals slab_global = {0};
173LOG_HANDLE_DEFINE_PRINT(slab);
174LOG_SITE_DEFINE_PRINT(slab);
175
176/* If our cache is PAGEABLE_ZERO, we can demand page it in
177 *
178 * In the future, PAGEABLE will want to be demand paged too, maybe
179 *
180 * TODO: zero pager interaction */
181static void *slab_map_new(struct slab_cache *cache,
182 paddr_t phys_out[SLAB_MAX_PAGES],
183 struct slab_chunk **out) {
184 struct slab_domain *domain = cache->parent_domain;
185 size_t pages = cache->pages_per_slab;
186 enum slab_type type = cache->type;
187 enforce(pages <= SLAB_MAX_PAGES, CAPACITY_EXCEEDED);
188
189 memset(phys_out, 0, pages * sizeof(paddr_t));
190 size_t pages_mapped = 0;
191 vaddr_t virt_base = 0x0;
192
193 if (cache->type != SLAB_TYPE_PAGEABLE_ZERO) {
194 for (size_t i = 0; i < pages; i++) {
195 if (domain) {
196 phys_out[i] = domain_alloc_from_domain(cd: domain->domain, pages: 1);
197 } else {
198 phys_out[i] = pmm_alloc_page();
199 }
200 if (cc_unlikely(!phys_out[i]))
201 goto err;
202 }
203 } else {
204 if (domain) {
205 phys_out[0] = domain_alloc_from_domain(cd: domain->domain, pages: 1);
206 } else {
207 phys_out[0] = pmm_alloc_page();
208 }
209
210 if (cc_unlikely(!phys_out[0]))
211 goto err;
212 }
213
214 virt_base = slab_chunks_alloc(sc: &cache->chunks, out);
215 if (cc_unlikely(!virt_base))
216 goto err;
217
218 uint64_t pflags = slab_page_flags(type);
219
220 for (pages_mapped = 0; pages_mapped < pages; pages_mapped++) {
221 vaddr_t virt = virt_base + pages_mapped * PAGE_SIZE;
222 if (cache->type != SLAB_TYPE_PAGEABLE_ZERO) {
223 paddr_t phys = phys_out[pages_mapped];
224 if (cc_unlikely(vmm_map_page(virt, phys, .page_flags = pflags) < 0))
225 goto err;
226 } else {
227 if (pages_mapped == 0) {
228 if (cc_unlikely(vmm_map_page(virt, phys_out[0],
229 .page_flags = pflags) < 0))
230 goto err;
231 } else {
232 if (cc_unlikely(vmm_mark_demand_page(
233 virt, DEMAND_PAGE_FLAG_ZERO_MEMORY |
234 DEMAND_PAGE_FLAG_WRITABLE) < 0))
235 goto err;
236 }
237 }
238 }
239
240 return (void *) virt_base;
241
242err:
243 for (size_t i = 0; i < pages; i++) {
244 paddr_t phys = phys_out[i];
245 pmm_free_page(addr: phys);
246 }
247
248 for (size_t i = 0; i < pages_mapped; i++) {
249 vaddr_t virt = virt_base + i * PAGE_SIZE;
250 vmm_unmap_page(virt);
251 }
252
253 if (virt_base)
254 slab_chunks_free(sc: &cache->chunks, chunk: *out, addr: virt_base);
255
256 return NULL;
257}
258
259static void slab_free_virt_and_phys(struct slab *slab) {
260
261#ifdef DEBUG_SLAB_DEEP
262 /* First drop references to all stack_handle_t's */
263 for (size_t i = 0; i < slab->parent_cache->objs_per_slab; i++) {
264
265 /* Might not necessarily exist */
266 if (slab->traces[i])
267 stack_depot_putref(slab->traces[i]);
268 }
269#endif
270
271 vaddr_t virt_base = (vaddr_t) slab;
272 struct slab_chunk *chunk = slab->parent_chunk;
273 /* Free through chunk's owner, as a GC reused slab's parent_cache may
274 * differ from the cache whose chunk it physically lives in */
275 struct slab_chunks *chunks = chunk->owner;
276
277 for (size_t i = 0; i < slab->page_count; i++) {
278 size_t virt = virt_base + i * PAGE_SIZE;
279 struct page *bp = atomic_load_rlx(&slab->backing_pages[i]);
280 if (bp) {
281 paddr_t phys = page_get_paddr(bp);
282 pmm_free_page(addr: phys);
283 }
284
285 vmm_unmap_page(virt);
286 }
287
288 slab_chunks_free(sc: chunks, chunk, addr: virt_base);
289}
290
291void slab_cache_init(size_t order, struct slab_cache *cache,
292 struct slab_size_constant *ssc) {
293 cache->order = order;
294 cache->obj_size = ssc->size;
295 cache->obj_align = ssc->align;
296 cache->obj_stride = SLAB_ALIGN_UP(ssc->size, ssc->align);
297 cache->pages_per_slab = ssc->internal.cand.pages;
298 size_t page_ptr_size = sizeof(struct page *) * cache->pages_per_slab;
299
300 uint64_t available = NON_SLAB_SPACE(cache);
301
302 if (cache->obj_size > available)
303 panic(CAPACITY_EXCEEDED, "object size %lu exceeds %lu available bytes",
304 cache->obj_size, available);
305
306 uint64_t n;
307 for (n = NON_SLAB_SPACE(cache) / ssc->size; n > 0; n--) {
308 uint64_t bitmap_bytes = SLAB_BITMAP_BYTES_FOR(n);
309 uintptr_t data_start = sizeof(struct slab) + bitmap_bytes +
310 page_ptr_size + sizeof(stack_handle_t) * n;
311 data_start = SLAB_ALIGN_UP(data_start, ssc->align);
312 uintptr_t data_end = data_start + n * cache->obj_stride;
313
314 if (data_end <= PAGE_SIZE * cache->pages_per_slab)
315 break;
316 }
317
318 spinlock_init(&cache->lock);
319 cache->objs_per_slab = n;
320
321 if (cache->objs_per_slab == 0)
322 panic(CAPACITY_EXCEEDED, "zero objects per slab");
323
324 cache->bitmap_bytes = SLAB_BITMAP_BYTES_FOR(cache->objs_per_slab);
325
326#ifdef DEBUG_SLAB_DEEP
327 size_t traces_size = sizeof(stack_handle_t) * cache->objs_per_slab;
328#else
329 size_t traces_size = 0;
330#endif
331
332 cache->slab_metadata_size =
333 sizeof(struct slab) + cache->bitmap_bytes + page_ptr_size + traces_size;
334 cache->slab_metadata_size =
335 ALIGN_UP(cache->slab_metadata_size, sizeof(uint64_t));
336
337 enforce(cache->objs_per_slab * cache->obj_stride +
338 cache->slab_metadata_size <=
339 cache->pages_per_slab * PAGE_SIZE);
340
341 /* We must hold this true because right now we only handle
342 * cases where the slab metadata is just 1 page. If we want,
343 * in the future if we somehow get GARGANTUAN slabs we can
344 * handle cases where this is more than one page. But I'll
345 * leave that as an optional TODO: */
346 enforce(cache->slab_metadata_size <= PAGE_SIZE);
347
348 list_head_init(h: &cache->slabs[SLAB_FREE]);
349 list_head_init(h: &cache->slabs[SLAB_PARTIAL]);
350 list_head_init(h: &cache->slabs[SLAB_FULL]);
351 slab_chunks_init(sc: &cache->chunks, parent: cache);
352}
353
354static void slab_zero_out(struct slab *slab, size_t page_count) {
355 void *start = (void *) slab->mem;
356 size_t non_data = slab->mem - (vaddr_t) slab;
357 enforce_precond(page_count);
358 size_t len = page_count * PAGE_SIZE - non_data;
359 memset(start, 0, len);
360}
361
362struct slab *slab_init(struct slab *slab, struct slab_cache *parent) {
363 void *page = slab;
364
365#ifdef DEBUG_ASAN
366 /* We must unpoison the slab because if it's taken off GC,
367 * the slab might still be poisoned according to the previous
368 * use, which means previously bitmap bytes would be different metadata
369 * and we could touch it and cause ASAN to trip */
370 asan_unpoison(page, parent->slab_metadata_size);
371#endif
372
373 slab->parent_cache = parent;
374 slab->bitmap = slab_get_bitmap_location(s: slab);
375
376#ifdef DEBUG_SLAB_DEEP
377 slab->traces = slab_get_traces_location(slab);
378#endif
379
380 vaddr_t data_start = (vaddr_t) page + parent->slab_metadata_size;
381 data_start = SLAB_ALIGN_UP(data_start, parent->obj_align);
382 slab->mem = data_start;
383
384 slab->used = 0;
385 slab->state = SLAB_FREE;
386 slab->gc_enqueue_time_ms = 0;
387 slab->type = parent->type;
388 rbt_init_node(n: &slab->rb);
389 list_node_init(n: &slab->list);
390 memset(slab->bitmap, 0, parent->bitmap_bytes);
391
392 /* Pre-set unused trailing bits */
393 size_t total_bits = parent->bitmap_bytes * 8;
394 for (size_t b = parent->objs_per_slab; b < total_bits; b++) {
395 size_t byte_idx = b / 8;
396 slab->bitmap[byte_idx] = BIT_SET(slab->bitmap[byte_idx], b % 8);
397 }
398
399#ifdef DEBUG_SLAB_DEEP
400 memset(slab->traces, 0, parent->objs_per_slab * sizeof(stack_handle_t));
401#endif
402
403 if (slab->type == SLAB_TYPE_NONPAGEABLE_ZERO) {
404 slab_zero_out(slab, page_count: parent->pages_per_slab);
405 } else if (slab->type == SLAB_TYPE_PAGEABLE_ZERO) {
406 /* TODO: handle cases where the other pages are mapped
407 * once zero pager infrastructure comes alive */
408 slab_zero_out(slab, page_count: 1); /* Just the first page */
409 }
410
411 return slab;
412}
413
414static struct slab *slab_create_new(struct slab_cache *cache) {
415 paddr_t phys[SLAB_MAX_PAGES];
416 struct slab_chunk *out;
417 void *page = slab_map_new(cache, phys_out: phys, out: &out);
418 if (!page)
419 return NULL;
420
421#ifdef DEBUG_ASAN
422 /* Make sure we can touch the metadata */
423 asan_unpoison(page, cache->slab_metadata_size);
424#endif
425
426 struct slab *slab = (struct slab *) page;
427 slab->parent_chunk = out;
428 slab->page_count = cache->pages_per_slab;
429
430 for (size_t i = 0; i < cache->pages_per_slab; i++) {
431 if (phys[i]) {
432 atomic_store_rlx(&slab->backing_pages[i], page_for_paddr(phys[i]));
433 } else {
434 atomic_store_rlx(&slab->backing_pages[i], NULL);
435 }
436 }
437
438 return slab_init(slab, parent: cache);
439}
440
441/* First we try and steal a slab from the GC list.
442 * If this does not work, we will map a new one. */
443struct slab *slab_create(struct slab_cache *cache,
444 enum alloc_behavior behavior) {
445 struct slab *slab = NULL;
446 struct slab_domain *local = slab_domain_local();
447 enforce(cache->type != SLAB_TYPE_NONE);
448
449 /* This is only searched if we are allowed to fault -
450 * iteration through GC slabs may touch pageable slabs and
451 * trigger a page fault, so we must be careful here */
452 if (alloc_behavior_may_fault(raw: behavior))
453 slab = slab_gc_get_for_cache(sc: cache);
454
455 if (slab) {
456 if (slab_resize(slab, new_size_pages: cache->pages_per_slab)) {
457 slab_stat_gc_object_reclaimed(domain: local);
458 return slab_init(slab, parent: cache);
459 } else {
460 /* Came out of cache's domain GC, so must go back to it */
461 slab_gc_enqueue(domain: cache->parent_domain, slab);
462 slab = NULL;
463 }
464 }
465
466 if (behavior & SLAB_ALLOC_BEHAVIOR_FROM_ALLOC) {
467 slab = slab_create_new(cache);
468
469 if (slab && cache->parent_domain == local)
470 slab_stat_alloc_new_slab(domain: local);
471
472 if (slab && cache->parent_domain != local)
473 slab_stat_alloc_new_remote_slab(domain: local);
474 }
475
476 return slab;
477}
478static void *slab_alloc_from(struct slab_cache *cache, stack_handle_t handle,
479 struct slab *slab) {
480#ifndef DEBUG_SLAB_DEEP
481 cc_ignore(handle);
482#endif
483
484 slab_check_assert(slab);
485
486 SPINLOCK_ASSERT_HELD(&cache->lock);
487 enforce(slab->state != SLAB_FULL);
488
489 uint64_t *bm = (uint64_t *) slab->bitmap;
490 size_t nwords = DIV_ROUND_UP(cache->objs_per_slab, sizeof(uint64_t) * 8);
491
492 for (size_t w = 0; w < nwords; w++) {
493 if (bm[w] != UINT64_MAX) {
494 uint64_t free_bits = ~bm[w];
495 uint64_t bit = ci_ctzll(free_bits);
496 uint64_t i = w * 64 + bit;
497
498 if (i >= cache->objs_per_slab)
499 break;
500
501 SLAB_BITMAP_SET(bm[w], BIT(bit));
502 slab->used++;
503
504#ifdef DEBUG_SLAB_DEEP
505 enforce(&slab->traces[i] < (stack_handle_t *) slab->mem,
506 CORRUPTION);
507 if (slab->traces[i])
508 stack_depot_putref(slab->traces[i]);
509
510 slab->traces[i] = handle;
511#endif
512
513 if (slab->used == cache->objs_per_slab) {
514 slab_move(c: cache, slab, new: SLAB_FULL);
515 } else if (slab->used == 1) {
516 slab_move(c: cache, slab, new: SLAB_PARTIAL);
517 }
518
519 vaddr_t ret = slab->mem + i * cache->obj_stride;
520 enforce(ret > (vaddr_t) slab &&
521 ret <
522 (vaddr_t) slab + cache->pages_per_slab * PAGE_SIZE,
523 CORRUPTION);
524
525 slab_check_assert(slab);
526 return (void *) ret;
527 }
528 }
529
530 slab_check_assert(slab);
531 return NULL;
532}
533
534void slab_destroy(struct slab *slab) {
535 slab_list_del(slab);
536 slab_free_virt_and_phys(slab);
537}
538
539static void slab_bitmap_free(struct slab *slab, void *obj) {
540 slab_check_assert(slab);
541
542 uint64_t byte_idx;
543 uint8_t bit_mask;
544 slab_index_and_mask(slab, obj, byte_idx_out: &byte_idx, bitmask_out: &bit_mask);
545
546 if (!SLAB_BITMAP_TEST(slab->bitmap[byte_idx], bit_mask)) {
547 panic(BAD_FREE, "addr %p, bitmap 0b%b, bitmask 0b%b", obj,
548 slab->bitmap[byte_idx], bit_mask);
549 }
550
551 SLAB_BITMAP_UNSET(slab->bitmap[byte_idx], bit_mask);
552 slab->used -= 1;
553}
554
555static void slab_free_old(struct slab *slab, void *obj) {
556 struct slab_cache *cache = slab->parent_cache;
557
558 enum irql slab_cache_irql = spin_lock(&cache->lock);
559
560 slab_bitmap_free(slab, obj);
561
562 if (slab->used == 0) {
563 slab_move(c: cache, slab, new: SLAB_FREE);
564 if (slab_should_enqueue_gc(slab)) {
565 slab_list_del(slab);
566 spin_unlock(&cache->lock, slab_cache_irql);
567
568 slab_free_virt_and_phys(slab);
569 return;
570 }
571 } else if (slab->state == SLAB_FULL) {
572 slab_move(c: cache, slab, new: SLAB_PARTIAL);
573 }
574
575 slab_check_assert(slab);
576 spin_unlock(&cache->lock, slab_cache_irql);
577}
578
579static void *slab_try_alloc_from_slab_list(struct slab_cache *cache,
580 stack_handle_t handle,
581 struct list_head *list) {
582 SPINLOCK_ASSERT_HELD(&cache->lock);
583 struct list_node *node, *temp;
584 struct slab *slab;
585 void *ret = NULL;
586
587 /* This should never iterate more than once */
588 list_for_each_safe(node, temp, list) {
589 slab = slab_from_list_node(node);
590 ret = slab_alloc_from(cache, handle, slab);
591 if (ret)
592 goto out;
593 }
594
595out:
596 return ret;
597}
598
599void slab_cache_insert(struct slab_cache *cache, struct slab *slab) {
600 enum irql irql = spin_lock(&cache->lock);
601
602 slab_init(slab, parent: cache);
603 slab_list_add(cache, slab);
604
605 spin_unlock(&cache->lock, irql);
606}
607
608void *slab_cache_try_alloc_from_lists(struct slab_cache *c,
609 stack_handle_t handle) {
610 SPINLOCK_ASSERT_HELD(&c->lock);
611
612 void *ret =
613 slab_try_alloc_from_slab_list(cache: c, handle, list: &c->slabs[SLAB_PARTIAL]);
614 if (ret)
615 return ret;
616
617 return slab_try_alloc_from_slab_list(cache: c, handle, list: &c->slabs[SLAB_FREE]);
618}
619
620void *slab_alloc_old(struct slab_cache *cache) {
621 void *ret = NULL;
622
623 enum irql irql = spin_lock(&cache->lock);
624 ret = slab_cache_try_alloc_from_lists(c: cache, /*handle=*/NULL);
625 spin_unlock(&cache->lock, irql);
626 if (ret)
627 goto out;
628
629 struct slab *slab;
630 slab = slab_create_new(cache);
631 if (!slab)
632 goto out;
633
634 irql = spin_lock(&cache->lock);
635 slab_list_add(cache, slab);
636 ret = slab_alloc_from(cache, /*handle=*/NULL, slab);
637 spin_unlock(&cache->lock, irql);
638
639out:
640 return ret;
641}
642
643int32_t slab_size_to_index(size_t size) {
644 size_t lo = 0;
645 size_t hi = slab_global.num_sizes;
646
647 while (lo < hi) {
648 size_t mid = lo + (hi - lo) / 2;
649
650 if (slab_global.class_sizes[mid].size >= size) {
651 hi = mid;
652 } else {
653 lo = mid + 1;
654 }
655 }
656
657 if (lo >= slab_global.num_sizes)
658 return -1;
659
660 return (int32_t) lo;
661}
662
663static inline bool valloc_size_fits_in_slab(size_t size) {
664 return slab_size_to_index(size) >= 0;
665}
666
667static int slab_class_sort_cmp(const void *a, const void *b) {
668 const struct slab_size_constant *sa = a;
669 const struct slab_size_constant *sb = b;
670
671 if (sa->size < sb->size)
672 return -1;
673 if (sa->size > sb->size)
674 return 1;
675
676 if (sa->align > sb->align)
677 return -1;
678 if (sa->align < sb->align)
679 return 1;
680
681 return 0;
682}
683
684static void log_dupes(const char *keep, const char *discard, size_t size) {
685 slab_info("Sizes of slab cache %s and %s are the same (%zu), ignoring %s, "
686 "keeping %s",
687 discard, keep, size, discard, keep);
688}
689
690void slab_allocator_init(void) {
691 /* bootstrap VAS */
692 slab_global.vas = vas_bootstrap(SLAB_HEAP_START, SLAB_HEAP_END);
693 if (!slab_global.vas)
694 panic(INIT_FAILED, "slab VAS");
695 struct slab_size_constant *start = __skernel_slab_sizes;
696 struct slab_size_constant *end = __ekernel_slab_sizes;
697 size_t dyn_count = end - start;
698 size_t total_input = dyn_count + SLAB_CLASS_SIZES_CONST_COUNT;
699
700 struct slab_size_constant *staging =
701 simple_alloc(space: slab_global.vas, size: total_input * sizeof(*staging));
702 enforce(staging, OUT_OF_MEMORY);
703 slab_order_map_init();
704
705 size_t sidx = 0;
706 /* "Constant" ones */
707 for (size_t i = 0; i < SLAB_CLASS_SIZES_CONST_COUNT; i++) {
708 staging[sidx++] = (struct slab_size_constant){
709 .name = "default slab size",
710 .size = slab_class_sizes_const[i],
711 .align = SLAB_OBJ_ALIGN_DEFAULT,
712 };
713 }
714 /* "Dynamic" ones */
715 for (struct slab_size_constant *ssc = start; ssc < end; ssc++) {
716 staging[sidx++] = (struct slab_size_constant){
717 .name = ssc->name,
718 .size = ssc->size,
719 .align = ssc->align,
720 };
721 }
722 enforce(sidx == total_input);
723
724 heapsort(vbase: staging, nmemb: total_input, size: sizeof(*staging), compar: slab_class_sort_cmp);
725
726 struct slab_size_constant *tmp =
727 simple_alloc(space: slab_global.vas, size: total_input * sizeof(*tmp));
728 enforce(tmp, OUT_OF_MEMORY);
729
730 size_t out = 0;
731 for (size_t i = 0; i < total_input; i++) {
732 if (out == 0 || staging[i].size != tmp[out - 1].size) {
733 tmp[out++] = staging[i];
734 } else {
735 log_dupes(keep: tmp[out - 1].name, discard: staging[i].name, size: staging[i].size);
736 }
737 }
738
739 simple_free(space: slab_global.vas, ptr: staging, size: total_input * sizeof(*staging));
740
741 slab_global.num_sizes = out;
742 slab_global.class_sizes =
743 simple_alloc(space: slab_global.vas,
744 size: slab_global.num_sizes * sizeof(*slab_global.class_sizes));
745 enforce(slab_global.class_sizes, OUT_OF_MEMORY);
746 memcpy(slab_global.class_sizes, tmp,
747 slab_global.num_sizes * sizeof(*slab_global.class_sizes));
748 slab_global.caches.caches = slab_caches_alloc();
749 for (uint64_t i = 0; i < slab_global.num_sizes; i++) {
750 struct slab_size_constant *ssc = &slab_global.class_sizes[i];
751 struct slab_cache *sc = &slab_global.caches.caches[i];
752 ssc->internal.cand = slab_elcm(obj_size: ssc->size, obj_alignment: ssc->align);
753 slab_cache_init(order: i, cache: sc, ssc);
754 sc->parent_domain = NULL;
755 sc->type = SLAB_TYPE_NONPAGEABLE;
756 sc->parent = &slab_global.caches;
757 slab_info("Slab cache s=%zu a=%zu \"%s\", o=%lu, p=%zu",
758 slab_global.class_sizes[i].size,
759 slab_global.class_sizes[i].align,
760 slab_global.class_sizes[i].name,
761 slab_global.caches.caches[i].objs_per_slab,
762 slab_global.class_sizes[i].internal.cand.pages);
763 }
764
765 simple_free(space: slab_global.vas, ptr: tmp, size: total_input * sizeof(*tmp));
766 slab_elcm_initialize();
767}
768
769struct slab *slab_for_ptr(void *ptr) {
770 enforce(slab_ptr_in_slab(ptr), BAD_FREE);
771 vaddr_t vp = (vaddr_t) ptr;
772 uint8_t pow2_order = slab_order_map_get(addr: vp);
773 enforce(pow2_order != SLAB_POW2_ORDER_EMPTY);
774
775 size_t align = ipow(base: 2, exp: pow2_order) * PAGE_SIZE;
776 return (struct slab *) ALIGN_DOWN(vp, align);
777}
778
779bool valloc_ptr_in_slab_validate(void *ptr) {
780 vaddr_t vaddr = (vaddr_t) ptr;
781 bool in_slab = IN_RANGE(vaddr, SLAB_HEAP_START, SLAB_HEAP_END);
782 bool in_page_alloc = page_alloc_vaddr_in_vas(vaddr);
783 enforce(in_slab || in_page_alloc, "invalid pointer");
784
785 return in_slab;
786}
787
788size_t vsize(void *ptr) {
789 if (!ptr)
790 return 0;
791
792 bool in_slab = valloc_ptr_in_slab_validate(ptr);
793
794 if (!in_slab) {
795 struct slab_page_hdr *hdr = slab_page_hdr_for_addr(ptr);
796 enforce(hdr->magic == VALLOC_PAGE_MAGIC, CORRUPTION,
797 "bad header magic 0x%x", hdr->magic);
798 return hdr->pages * PAGE_SIZE - sizeof(struct slab_page_hdr);
799 }
800
801 return slab_for_ptr(ptr)->parent_cache->obj_size;
802}
803
804size_t slab_allocation_size(vaddr_t addr) {
805 return vsize(ptr: (void *) addr);
806}
807
808static void *valloc_pages_raw(struct slab_domain *parent, stack_handle_t handle,
809 size_t size, struct alloc_params params) {
810 enum alloc_flags flags = params.flags;
811 uint64_t total_size = size + sizeof(struct slab_page_hdr);
812 uint64_t pages = PAGES_NEEDED_FOR(total_size);
813
814 void *vptr;
815 if (flags & ALLOC_FLAG_PAGEABLE) {
816 vptr = page_alloc_demand_full(page_count: pages, params);
817 } else {
818 vptr = page_alloc_full(page_count: pages, params);
819 if (vptr && (flags & ALLOC_FLAG_ZERO_ON_ALLOC))
820 memset(vptr, 0, total_size);
821 }
822
823 if (!vptr)
824 return NULL;
825
826 struct slab_page_hdr *hdr = (struct slab_page_hdr *) vptr;
827 hdr->magic = VALLOC_PAGE_MAGIC;
828 hdr->pages = pages;
829 hdr->domain = parent;
830 hdr->pageable = (flags & ALLOC_FLAG_PAGEABLE);
831 hdr->handle = handle;
832
833 return (void *) (hdr + 1);
834}
835
836static void *valloc_old(size_t size, enum alloc_flags flags) {
837 if (size == 0)
838 return NULL;
839
840 int idx = slab_size_to_index(size);
841
842 void *ptr;
843 if (valloc_size_fits_in_slab(size) &&
844 slab_global.caches.caches[idx].objs_per_slab > 0) {
845 ptr = slab_alloc_old(cache: &slab_global.caches.caches[idx]);
846 } else {
847 /* we say NULL and just free these to domain 0 */
848 ptr = valloc_pages_raw(
849 NULL, NULL, size,
850 params: (struct alloc_params){.flags = ALLOC_FLAGS_DEFAULT,
851 .behavior = ALLOC_BEHAVIOR_NORMAL});
852 }
853
854 if ((flags & ALLOC_FLAG_ZERO_ON_ALLOC) && ptr)
855 memset(ptr, 0, size);
856
857 return ptr;
858}
859
860void *valloc_pages(size_t page_count, enum alloc_flags flags) {
861 void *ptr = valloc_pages_raw(
862 NULL, NULL, size: page_count * PAGE_SIZE,
863 params: (struct alloc_params){.flags = ALLOC_FLAGS_DEFAULT,
864 .behavior = ALLOC_BEHAVIOR_NORMAL});
865
866 if ((flags & ALLOC_FLAG_ZERO_ON_ALLOC) && ptr)
867 memset(ptr, 0, page_count * PAGE_SIZE);
868
869 return ptr;
870}
871
872void slab_free_page_hdr(struct slab_page_hdr *hdr, enum alloc_behavior bh) {
873 uint32_t pages = hdr->pages;
874 if (hdr->handle)
875 stack_depot_putref(key: hdr->handle);
876
877 page_free(hdr, pages, bh);
878}
879
880void slab_free_addr_to_cache(void *addr, enum alloc_behavior bh) {
881 valloc_ptr_in_slab_validate(ptr: addr);
882
883 struct slab_page_hdr *hdr_candidate = slab_page_hdr_for_addr(ptr: addr);
884 if (hdr_candidate->magic == VALLOC_PAGE_MAGIC)
885 return slab_free_page_hdr(hdr: hdr_candidate, bh);
886
887 struct slab *slab = slab_for_ptr(ptr: addr);
888 if (!slab)
889 panic(BAD_FREE, "address %p", addr);
890
891 slab_free_old(slab, obj: addr);
892}
893
894static void vfree_old(void *ptr) {
895 slab_free_addr_to_cache(addr: ptr, bh: ALLOC_BEHAVIOR_NORMAL);
896}
897
898static void *valloc_pages_internal(struct slab_domain *domain,
899 stack_handle_t handle, size_t size,
900 struct alloc_params params) {
901 void *ret = valloc_pages_raw(parent: domain, handle, size, params);
902
903 if (alloc_behavior_may_fault(raw: params.behavior) &&
904 !alloc_behavior_is_fast(raw: params.behavior)) {
905 struct slab_domain *local = slab_domain_local();
906 struct slab_percpu_cache *pcpu = slab_percpu_cache_local();
907
908 /* Scale down this free_queue drain target */
909 size_t pct = SLAB_FREE_QUEUE_ALLOC_PCT;
910 size_t target = slab_free_queue_get_target_drain(domain: local, pct);
911 target /= 2;
912
913 slab_free_queue_drain(cache: pcpu, queue: &local->free_queue, target,
914 bh: params.behavior);
915 }
916
917 if (ret)
918 slab_stat_alloc_page_hit(domain);
919
920 return ret;
921}
922
923size_t slab_allocation_index(struct slab *slab, void *ptr) {
924 size_t delta = (size_t) ((uint8_t *) ptr - (uint8_t *) slab->mem);
925 return delta / slab->parent_cache->obj_stride;
926}
927
928static void *valloc_try_from_magazine(struct slab_domain *domain,
929 struct slab_percpu_cache *pcpu,
930 stack_handle_t handle, size_t size,
931 enum alloc_flags flags) {
932#ifndef DEBUG_SLAB_DEEP
933 cc_ignore(handle);
934#endif
935
936 enum slab_magazine_type mtype = (flags & ALLOC_FLAG_ZERO_ON_ALLOC)
937 ? SLAB_MAGAZINE_ZERO
938 : SLAB_MAGAZINE_NORMAL;
939 size_t class_idx = slab_size_to_index(size);
940 struct slab_magazine *mag = &pcpu->mags[mtype][class_idx];
941
942 /* Reserve SLAB_MAG_WATERMARK_PCT% entries for nonpageable requests */
943 if (flags & ALLOC_FLAG_PAGEABLE && mag->count < SLAB_MAG_WATERMARK)
944 return NULL;
945
946 void *ret = (void *) slab_magazine_pop(mag);
947 if (ret) {
948 struct slab *slab = slab_for_ptr(ptr: ret);
949 slab_stat_alloc_magazine_hit(domain);
950 uint64_t byte_idx;
951 uint8_t bit_mask;
952 slab_index_and_mask(slab, obj: ret, byte_idx_out: &byte_idx, bitmask_out: &bit_mask);
953 enforce(SLAB_BITMAP_TEST(slab_for_ptr(ret)->bitmap[byte_idx], bit_mask),
954 CORRUPTION);
955
956#ifdef DEBUG_SLAB_DEEP
957 size_t idx = slab_allocation_index(slab, ret);
958 if (slab->traces[idx])
959 stack_depot_putref(slab->traces[idx]);
960
961 slab->traces[idx] = handle;
962#endif
963
964#ifdef DEBUG_SLAB
965 if (mtype == SLAB_MAGAZINE_ZERO &&
966 !is_buffer_uniform(ret, mag->obj_size, 0)) {
967#ifdef DEBUG_SLAB_DEEP
968 slab_dump_corruption(ret, mag, 0);
969#endif
970
971 panic(CORRUPTION, "buffer size %zu idx %zu not uniform", size,
972 class_idx);
973 }
974#endif
975 }
976
977 return ret;
978}
979
980static size_t slab_free_queue_drain_on_alloc(struct slab_domain *dom,
981 struct slab_percpu_cache *c,
982 enum alloc_behavior behavior,
983 size_t pct) {
984 if (!alloc_behavior_may_fault(raw: behavior))
985 return 0;
986
987 /* drain a tiny bit back into our magazine */
988 return slab_free_queue_drain_limited(pc: c, dom, pct, bh: behavior);
989}
990
991static inline size_t slab_get_search_dist(struct slab_domain *dom,
992 uint8_t locality) {
993 /* The higher the locality, the closer it is, and the less we will search */
994 uint8_t numerator = ALLOC_LOCALITY_MAX - locality;
995 size_t ret = dom->zonelist_entry_count * numerator / ALLOC_LOCALITY_MAX;
996 if (ret == 0)
997 ret = 1;
998
999 return ret;
1000}
1001
1002static size_t slab_cache_usable(struct slab_cache *cache) {
1003 size_t part = SLAB_CACHE_COUNT_FOR(cache, SLAB_PARTIAL);
1004 size_t free = SLAB_CACHE_COUNT_FOR(cache, SLAB_FREE);
1005 return part + free;
1006}
1007
1008static int32_t slab_score_cache(struct slab_cache_ref *ref,
1009 struct slab_cache *cache, bool flexible) {
1010 int32_t dist_weight = flexible ? SLAB_CACHE_FLEXIBLE_DISTANCE_WEIGHT
1011 : SLAB_CACHE_DISTANCE_WEIGHT;
1012
1013 int32_t usable = slab_cache_usable(cache);
1014 int32_t dist_part = ref->locality * dist_weight;
1015
1016 /* Lower is better */
1017 return dist_part - usable;
1018}
1019
1020static struct slab_cache *slab_search_for_cache(struct slab_domain *dom,
1021 enum alloc_flags flags,
1022 size_t size) {
1023 size_t idx = slab_size_to_index(size);
1024 uint8_t locality = ALLOC_LOCALITY_FROM_FLAGS(flags);
1025
1026 bool pageable = flags & ALLOC_FLAG_PAGEABLE;
1027 bool flexible = flags & ALLOC_FLAG_FLEXIBLE_LOCALITY;
1028 bool zero = flags & ALLOC_FLAG_ZERO_ON_ALLOC;
1029
1030 size_t search_distance = slab_get_search_dist(dom, locality);
1031
1032 int32_t best_score = INT32_MAX;
1033 struct slab_cache *ret = NULL;
1034
1035 enum slab_type p_type = zero ? SLAB_TYPE_PAGEABLE_ZERO : SLAB_TYPE_PAGEABLE;
1036 enum slab_type np_type =
1037 zero ? SLAB_TYPE_NONPAGEABLE_ZERO : SLAB_TYPE_NONPAGEABLE;
1038 for (size_t i = 0; i < search_distance; i++) {
1039 /* pageable, nonpageable candidates */
1040 struct slab_cache_ref *p_ref = &dom->zonelists[p_type].entries[i];
1041 struct slab_cache_ref *np_ref = &dom->zonelists[np_type].entries[i];
1042 struct slab_cache *p_cache = &p_ref->caches->caches[idx];
1043 struct slab_cache *np_cache = &np_ref->caches->caches[idx];
1044
1045 int32_t p_score = slab_score_cache(ref: p_ref, cache: p_cache, flexible);
1046 int32_t np_score = slab_score_cache(ref: np_ref, cache: np_cache, flexible);
1047
1048 size_t p_usable = slab_cache_usable(cache: p_cache);
1049 size_t np_usable = slab_cache_usable(cache: np_cache);
1050
1051 /* We prevent these caches from being selected if they come up
1052 * empty handed -- this first loop scores based on slab usability */
1053 if (p_usable == 0)
1054 p_score = INT32_MAX;
1055
1056 if (np_usable == 0)
1057 np_score = INT32_MAX;
1058
1059 if (!pageable && np_score < best_score) {
1060 best_score = np_score;
1061 ret = np_cache;
1062 } else if (pageable && np_score <= p_score / 2 &&
1063 np_score < best_score) {
1064 best_score = np_score;
1065 ret = np_cache;
1066 } else if (pageable && p_score < best_score) {
1067 best_score = p_score;
1068 ret = p_cache;
1069 }
1070 }
1071
1072 if (ret)
1073 return ret;
1074
1075 /* saying pages = 1 here is actually fine because we won't do contiguous
1076 * allocations. the only risk is for multi-page slabs, but those will just
1077 * OOM in the worst case scenario, and besides, this is a "racy
1078 * heuristic", so accuracy doesn't matter, if we OOM, bigger problems exist
1079 */
1080 struct domain *d = domain_alloc_pick_best_domain(local: dom->domain, /*pages=*/1,
1081 max_scan: search_distance, flexible_locality: flexible);
1082
1083 struct slab_domain *sd = global.domains[d->id]->slab_domain;
1084 struct slab_caches *sc =
1085 pageable ? sd->caches[p_type] : sd->caches[np_type];
1086
1087 ret = &sc->caches[idx];
1088
1089 return ret;
1090}
1091
1092static void slab_stat_alloc_from_cache(struct slab_cache *cache) {
1093 struct slab_domain *local = slab_domain_local();
1094 if (cache->parent_domain == local) {
1095 slab_stat_alloc_local_hit(domain: local);
1096 } else {
1097 slab_stat_alloc_remote_hit(domain: local);
1098 }
1099}
1100
1101void *slab_alloc(struct slab_cache *cache, stack_handle_t handle,
1102 enum alloc_behavior behavior) {
1103 void *ret = NULL;
1104 bool from_alloc = behavior & SLAB_ALLOC_BEHAVIOR_FROM_ALLOC;
1105
1106 if (!alloc_behavior_may_fault(raw: behavior) && slab_cache_is_pageable(c: cache))
1107 panic("picked pageable cache with non-fault tolerant behavior");
1108
1109 enum irql irql = spin_lock(&cache->lock);
1110
1111 /* First try from lists */
1112 ret = slab_cache_try_alloc_from_lists(c: cache, handle);
1113 if (ret) {
1114 if (from_alloc)
1115 slab_stat_alloc_from_cache(cache);
1116 goto out;
1117 }
1118
1119 /* Drop the lock since we are going to do the expensive thing */
1120 spin_unlock(&cache->lock, irql);
1121
1122 struct slab *slab = slab_create(cache, behavior);
1123
1124 irql = spin_lock(&cache->lock);
1125
1126 if (!slab)
1127 goto out;
1128
1129 slab_list_add(cache, slab);
1130 ret = slab_alloc_from(cache, handle, slab);
1131
1132out:
1133 spin_unlock(&cache->lock, irql);
1134
1135#ifdef DEBUG_SLAB
1136 if (ret && (cache->type == SLAB_TYPE_NONPAGEABLE_ZERO ||
1137 cache->type == SLAB_TYPE_PAGEABLE_ZERO)) {
1138 if (!is_buffer_uniform(ret, cache->obj_size, 0)) {
1139#ifdef DEBUG_SLAB_DEEP
1140 slab_dump_corruption(ret, NULL, cache->obj_size);
1141#endif
1142
1143 const uint8_t *bb = (const uint8_t *) ret;
1144 size_t bad = 0;
1145 for (size_t i = 0; i < cache->obj_size; i++)
1146 if (bb[i]) {
1147 bad = i;
1148 break;
1149 }
1150
1151 struct slab *dslab = slab_for_ptr(ret);
1152 vaddr_t soff = (vaddr_t) ret - (vaddr_t) dslab;
1153 size_t obj_idx = ((vaddr_t) ret - dslab->mem) / cache->obj_stride;
1154
1155 slab_err(
1156 "NON-UNIFORM ZERO BUF: sz=%zu type=%d ppslab=%zu stride=%lu",
1157 cache->obj_size, (int) cache->type, cache->pages_per_slab,
1158 cache->obj_stride);
1159 slab_err(
1160 " ret=%p slab=%p slaboff=%zu page=%zu objidx=%zu used=%zu "
1161 "badoff=%zu badval=0x%02x",
1162 ret, (void *) dslab, (size_t) soff, (size_t) (soff / PAGE_SIZE),
1163 obj_idx, dslab->used, bad, bb[bad]);
1164
1165 for (size_t i = 0; i < cache->obj_size; i += 16) {
1166 uint8_t r[16] = {0};
1167 char ascii[17];
1168 size_t remaining = cache->obj_size - i;
1169 size_t n = MIN(remaining, sizeof(r));
1170 for (size_t j = 0; j < 16; j++) {
1171 if (j < n) {
1172 r[j] = bb[i + j];
1173 ascii[j] =
1174 (r[j] >= 0x20 && r[j] < 0x7f) ? (char) r[j] : '.';
1175 } else {
1176 ascii[j] = ' ';
1177 }
1178 }
1179 ascii[16] = '\0';
1180 slab_err(" +%03zu: %02x %02x %02x %02x %02x %02x %02x %02x "
1181 "%02x %02x %02x %02x %02x %02x %02x %02x |%s|",
1182 i, r[0], r[1], r[2], r[3], r[4], r[5], r[6], r[7],
1183 r[8], r[9], r[10], r[11], r[12], r[13], r[14], r[15],
1184 ascii);
1185 }
1186
1187 panic(CORRUPTION, "buffer size %zu not uniform", cache->obj_size);
1188 }
1189 }
1190#endif
1191
1192 return ret;
1193}
1194
1195static void *slab_alloc_retry(struct slab_domain *domain, stack_handle_t handle,
1196 size_t size, struct alloc_params params) {
1197 enum alloc_flags flags = params.flags;
1198 enum alloc_behavior behavior = params.behavior;
1199 /* here we run emergency GC to try and reclaim a little memory */
1200 enum slab_gc_flags gc_flags = SLAB_GC_FLAG_AGG_EMERGENCY;
1201
1202 /* setup our flags */
1203 if (!valloc_size_fits_in_slab(size)) {
1204 gc_flags |= SLAB_GC_FLAG_FORCE_DESTROY;
1205 size_t needed =
1206 MIN(PAGES_NEEDED_FOR(size), SLAB_GC_FLAG_DESTROY_TARGET_MAX);
1207
1208 SLAB_GC_FLAG_DESTROY_TARGET_SET(gc_flags, needed);
1209 } else {
1210 size_t order = slab_size_to_index(size);
1211 SLAB_GC_FLAG_ORDER_BIAS_SET(gc_flags, order);
1212 }
1213
1214 /* here we go! run GC for the appropriate domain */
1215 slab_gc_run(gc: &domain->slab_gc, flags: gc_flags);
1216
1217 /* ok now we have ran the emergency GC, let's try again... */
1218 if (!valloc_size_fits_in_slab(size)) {
1219 /* here, `domain` should be the local domain... */
1220 return valloc_pages_internal(domain, handle, size, params);
1221 } else {
1222 /* here, `domain` might be another domain */
1223
1224 bool zero = flags & ALLOC_FLAG_ZERO_ON_ALLOC;
1225 enum slab_type p_type =
1226 zero ? SLAB_TYPE_PAGEABLE_ZERO : SLAB_TYPE_PAGEABLE;
1227 enum slab_type np_type =
1228 zero ? SLAB_TYPE_NONPAGEABLE_ZERO : SLAB_TYPE_NONPAGEABLE;
1229
1230 struct slab_caches *cs = flags & ALLOC_FLAG_PAGEABLE
1231 ? domain->caches[p_type]
1232 : domain->caches[np_type];
1233
1234 struct slab_cache *cache = &cs->caches[slab_size_to_index(size)];
1235
1236 return slab_alloc(cache, handle,
1237 behavior: behavior | SLAB_ALLOC_BEHAVIOR_FROM_ALLOC);
1238 }
1239}
1240
1241void *valloc_new(size_t size, struct alloc_params params) {
1242 enum alloc_flags flags = params.flags;
1243 enum alloc_behavior behavior = params.behavior;
1244 valloc_validate_params(size, params);
1245 void *ret = NULL;
1246 enum irql outer = irql_raise(new_level: IRQL_DISPATCH_LEVEL);
1247
1248 struct slab_domain *local_dom = slab_domain_local();
1249 struct slab_percpu_cache *pcpu = slab_percpu_cache_local();
1250 struct slab_domain *selected_dom = local_dom;
1251
1252#ifdef DEBUG_SLAB_DEEP
1253 stack_handle_t handle = enforce(stack_depot_save_current(), OUT_OF_MEMORY);
1254#else
1255 stack_handle_t handle = NULL;
1256#endif
1257
1258 slab_stat_alloc_call(domain: local_dom);
1259
1260 /* this has its own path */
1261 if (!valloc_size_fits_in_slab(size)) {
1262 ret = valloc_pages_internal(domain: local_dom, handle, size, params);
1263 goto exit;
1264 }
1265
1266 /* alloc fits in slab - TODO: scale size if cache alignment is requested */
1267 ret = valloc_try_from_magazine(domain: local_dom, pcpu, handle, size, flags);
1268
1269 /* if the mag alloc fails, drain our full portion of the freequeue */
1270 size_t pct = ret ? SLAB_FREE_QUEUE_ALLOC_PCT : 100;
1271 size_t drained =
1272 slab_free_queue_drain_on_alloc(dom: local_dom, c: pcpu, behavior, pct);
1273
1274 /* did the initial allocation fail but we drained something? go again... */
1275 if (!ret && drained) {
1276 ret = valloc_try_from_magazine(domain: local_dom, pcpu, handle, size, flags);
1277 }
1278
1279 /* found something -- all done, this is the fastpath.
1280 * we don't bother with GC or any funny stuff. */
1281 if (ret)
1282 goto exit;
1283
1284 /* ok the magazine is empty and we also didn't successfully drain
1285 * any freequeue elements to reuse, so we now want to start searching
1286 * slab caches to allocate from a slab that may or may not be local */
1287 struct slab_cache *cache = slab_search_for_cache(dom: local_dom, flags, size);
1288
1289 /* now we have picked a slab cache - it may or may not have free slabs but
1290 * we definitely know where we want to get memory from now */
1291 selected_dom = cache->parent_domain;
1292
1293 /* allocate from an existing slab or pull from the GC lists
1294 * or call into the physical memory allocator to get a new slab */
1295 ret = slab_alloc(cache, handle, behavior: behavior | SLAB_ALLOC_BEHAVIOR_FROM_ALLOC);
1296
1297 /* slowpath - let's try and fill up our percpu caches so we don't
1298 * end up in this slowpath over and over again... */
1299 slab_percpu_refill(dom: local_dom, cache: pcpu, params);
1300
1301 /* uh oh... we found NOTHING...
1302 * try one last time - this will run emergency GC */
1303 if (cc_unlikely(!ret) && !alloc_behavior_is_fast(raw: behavior))
1304 ret = slab_alloc_retry(domain: selected_dom, handle, size, params);
1305
1306exit:
1307
1308 /* only hit if there is truly nothing left */
1309 if (cc_unlikely(!ret))
1310 slab_stat_alloc_failure(domain: local_dom);
1311
1312 if (ret)
1313 asan_alloc(addr: ret, requested: size, slot: vsize(ptr: ret));
1314
1315 irql_lower(old_level: outer);
1316 return ret;
1317}
1318
1319void *valloc_from_domain(domain_id_t domain, size_t size) {
1320 enum irql irql = irql_raise(new_level: IRQL_DISPATCH_LEVEL);
1321
1322 size_t index = slab_size_to_index(size);
1323 struct slab_caches *cs =
1324 global.domains[domain]->slab_domain->caches[SLAB_TYPE_NONPAGEABLE_ZERO];
1325 struct slab_cache *c = &cs->caches[index];
1326 void *ret =
1327 slab_alloc(cache: c, /*handle=*/NULL,
1328 behavior: ALLOC_BEHAVIOR_NORMAL | SLAB_ALLOC_BEHAVIOR_FROM_ALLOC);
1329
1330 irql_lower(old_level: irql);
1331
1332#ifdef DEBUG_ASAN
1333 if (ret)
1334 asan_alloc(ret, size, vsize(ret));
1335#endif
1336
1337 return ret;
1338}
1339
1340/* okay, our free policy (in terms of freequeue usage) is:
1341 *
1342 * If the freequeue is the local freequeue, we immediately drain
1343 * to the slab cache if the freequeue ringbuffer fills up.
1344 *
1345 * If the freequeue is a remote freequeue, we first try and add
1346 * to its ringbuffer. If this fails, then, if the allocation
1347 * is a slab allocation (did not come from valloc_pages), we
1348 * will add to its freequeue chain if the other allocator is busy
1349 * (we look at our stats and see that it is doing a LOT of work)
1350 *
1351 * Otherwise, if the allocator is not too busy, we just free
1352 * to the slab cache on the remote side.
1353 *
1354 * This freequeue policy is only relevant if we actually
1355 * choose to use the freequeue. Hopefully most frees can just
1356 * go to the magazine instead of the freequeue.
1357 *
1358 * Later on we'll do GC and all that fun stuff.
1359 *
1360 */
1361
1362bool slab_domain_busy(struct slab_domain *domain) {
1363 bool idle = domain_idle(domain: domain->domain);
1364 struct slab_domain_bucket *curr =
1365 &domain->buckets[atomic_load_rlx(&domain->stats->current)];
1366 bool recent_call = atomic_load_rlx(&curr->alloc_calls) &&
1367 atomic_load_rlx(&curr->free_calls);
1368
1369 return recent_call && !idle;
1370}
1371
1372static bool vfree_free_queue_enqueue(struct slab_domain *domain, void *ptr) {
1373 struct slab_domain *local = slab_domain_local();
1374 vaddr_t vptr = (vaddr_t) ptr;
1375
1376 /* Splendid, it worked */
1377 if (slab_free_queue_ringbuffer_enqueue(q: &domain->free_queue, addr: vptr)) {
1378 slab_stat_free_to_ring(domain: local);
1379 return true;
1380 }
1381
1382 return false;
1383}
1384
1385static void vfree_pages(void *ptr, enum alloc_behavior behavior) {
1386 struct slab_page_hdr *header = slab_page_hdr_for_addr(ptr);
1387
1388 /* early allocations do not have topology data and set their
1389 * `header->domain` to NULL. in this case, we just assume that
1390 * we should flush to domain 0 since that is most likely where
1391 * the allocation had come from. */
1392 struct slab_domain *owner = header->domain;
1393
1394 owner = owner ? owner : global.domains[0]->slab_domain;
1395
1396 /* these pages don't turn into slabs and thus don't get added
1397 * into the slab caches. instead, we just directly free it to
1398 * the physical memory allocator. we will first try and append
1399 * to the freequeue ringbuf.
1400 *
1401 * if that fails, if the allocator is busy, we will append it
1402 * to the freequeue freelist, otherwise just flush the allocation.
1403 *
1404 * only touch the freelist if we are looking at a remote domain */
1405
1406 /* no touchy */
1407 if (!alloc_behavior_may_fault(raw: behavior))
1408 enforce(!header->pageable);
1409
1410 if (vfree_free_queue_enqueue(domain: owner, ptr))
1411 return;
1412
1413 /* could not put it on the freequeue... */
1414
1415 /* TODO: We can try and figure out how to turn these pages
1416 * back into slabs and recycle them as such... for now, it
1417 * is fine to just free them to page_alloc */
1418 slab_free_page_hdr(hdr: header, bh: behavior);
1419}
1420
1421static bool vfree_try_free_to_magazine(struct slab_percpu_cache *pcpu,
1422 void *ptr, size_t size) {
1423 struct slab *slab = slab_for_ptr(ptr);
1424
1425 /* wrong domain */
1426 if (slab->parent_cache->parent_domain != pcpu->domain)
1427 return false;
1428
1429 enforce(slab->type != SLAB_TYPE_NONE);
1430 if (slab_is_pageable(s: slab))
1431 return false;
1432
1433 int32_t idx = slab_size_to_index(size);
1434 enum slab_magazine_type mtype =
1435 slab_is_zeroed(s: slab) ? SLAB_MAGAZINE_ZERO : SLAB_MAGAZINE_NORMAL;
1436
1437 if (mtype == SLAB_MAGAZINE_ZERO)
1438 memset(ptr, 0, vsize(ptr));
1439
1440 struct slab_magazine *mag = &pcpu->mags[mtype][idx];
1441 bool ret = slab_magazine_push(mag, obj: (vaddr_t) ptr);
1442 if (ret)
1443 slab_stat_free_to_percpu(domain: pcpu->domain);
1444
1445 return ret;
1446}
1447
1448void slab_free(struct slab_domain *domain, void *obj) {
1449 struct slab *slab = slab_for_ptr(ptr: obj);
1450 struct slab_cache *cache = slab->parent_cache;
1451 if (slab_is_zeroed(s: slab))
1452 memset(obj, 0, cache->obj_size);
1453
1454 enum irql slab_cache_irql = spin_lock(&cache->lock);
1455 slab_bitmap_free(slab, obj);
1456
1457 if (slab->used == 0) {
1458 slab_move(c: cache, slab, new: SLAB_FREE);
1459 if (slab_should_enqueue_gc(slab)) {
1460 slab_list_del(slab);
1461 slab_stat_gc_collection(domain);
1462 slab_gc_enqueue(domain, slab);
1463 spin_unlock(&cache->lock, slab_cache_irql);
1464 return;
1465 }
1466 } else if (slab->state == SLAB_FULL) {
1467 slab_move(c: cache, slab, new: SLAB_PARTIAL);
1468 }
1469
1470 slab_check_assert(slab);
1471 spin_unlock(&cache->lock, slab_cache_irql);
1472}
1473
1474static size_t slab_free_queue_drain_on_free(struct slab_domain *domain,
1475 struct slab_percpu_cache *pcpu,
1476 enum alloc_behavior behavior) {
1477 if (!alloc_behavior_may_fault(raw: behavior))
1478 return 0;
1479
1480 return slab_free_queue_drain_limited(pc: pcpu, dom: domain, /* pct = */ 100,
1481 bh: behavior);
1482}
1483
1484void vfree_new(void *ptr, enum alloc_behavior behavior) {
1485 enum irql outer = irql_raise(new_level: IRQL_DISPATCH_LEVEL);
1486 valloc_ptr_in_slab_validate(ptr);
1487
1488 size_t size = vsize(ptr);
1489 int32_t idx = slab_size_to_index(size);
1490 struct slab_domain *local_domain = slab_domain_local();
1491 struct slab_percpu_cache *pcpu = slab_percpu_cache_local();
1492
1493#ifdef DEBUG_SLAB_DEEP
1494 slab_debug_assert_not_already_free((vaddr_t) ptr, idx);
1495#endif
1496
1497 slab_stat_free_call(domain: local_domain);
1498
1499 /* Free from ASAN first so we don't get a
1500 * window in between this and slab_free */
1501 asan_free(addr: ptr, slot: size);
1502
1503 if (idx < 0) {
1504 vfree_pages(ptr, behavior);
1505 goto garbage_collect;
1506 }
1507
1508 /* nice, we freed it to the magazine and we are all good now -- fastpath,
1509 * so we don't try GC or any funny business */
1510 if (vfree_try_free_to_magazine(pcpu, ptr, size))
1511 goto done;
1512
1513 /* did not free to magazine - this is an alloc from a slab */
1514 struct slab *slab = slab_for_ptr(ptr);
1515 struct slab_domain *owner = slab->parent_cache->parent_domain;
1516
1517 if (vfree_free_queue_enqueue(domain: owner, ptr))
1518 goto done;
1519
1520 /* could not put on percpu cache or freequeue, now we free to
1521 * the slab cache that owns this data */
1522
1523 if (owner == local_domain) {
1524 slab_stat_free_to_local_slab(domain: local_domain);
1525 } else {
1526 slab_stat_free_to_remote_domain(domain: local_domain);
1527 }
1528
1529 slab_free(domain: owner, obj: ptr);
1530
1531garbage_collect:
1532
1533 slab_free_queue_drain_on_free(domain: local_domain, pcpu, behavior);
1534
1535done:
1536 irql_lower(old_level: outer);
1537}
1538
1539/* Named by STATIC_CALL_DEFINE's asm below, so these must stay external */
1540void *valloc_init(size_t size, struct alloc_params params);
1541void vfree_init(void *p, enum alloc_behavior b);
1542
1543void *valloc_init(size_t size, struct alloc_params params) {
1544 return valloc_old(size, flags: params.flags);
1545}
1546
1547void vfree_init(void *p, enum alloc_behavior b) {
1548 cc_ignore(b);
1549 vfree_old(ptr: p);
1550}
1551
1552STATIC_CALL_DEFINE(alloc, valloc_init);
1553STATIC_CALL_DEFINE(free, vfree_init);
1554
1555void slab_switch_to_domain_allocations(void) {
1556 static_call_update(alloc, valloc_new);
1557 static_call_update(free, vfree_new);
1558}
1559
1560void *valloc_full(size_t size, struct alloc_params params) {
1561 void *p = static_call(alloc)(size, params);
1562
1563#ifdef DEBUG_ASAN
1564 if (p)
1565 asan_alloc(p, size, vsize(p));
1566#endif
1567
1568#ifdef DEBUG_SLAB
1569 /* TODO: This should go away on release builds. When we bring
1570 * in non-fatal assertions/debug only assertions, this should
1571 * get changed so as to not make the code be slower than a memset 0 */
1572 if (p && (params.flags & ALLOC_FLAG_ZERO_ON_ALLOC))
1573 enforce(is_buffer_uniform(p, size, 0), CORRUPTION);
1574
1575 if (p && !(params.flags & ALLOC_FLAG_ZERO_ON_ALLOC))
1576 memset(p, SLAB_ALLOC_NONZERO_POISON_BYTE, size);
1577#endif
1578
1579#ifdef DEBUG_SLAB_DEEP
1580 /* Track the REAL caller (this function is the public entry point). */
1581 if (p)
1582 slab_track_event((vaddr_t) p, (uint64_t) ci_return_address(0), 0, true);
1583#endif
1584
1585 return p;
1586}
1587
1588void vfree_full(void *p, enum alloc_behavior behavior) {
1589 if (cc_unlikely(!p))
1590 return;
1591
1592 if ((uint16_t) behavior == (uint16_t) ALLOC_FLAGS_DEFAULT) {
1593 slab_warn("Likely incorrect arguments passed into `vfree`");
1594 return;
1595 }
1596
1597#ifdef DEBUG_SLAB_DEEP
1598 slab_track_event((vaddr_t) p, (uint64_t) ci_return_address(0), 0, false);
1599#endif
1600
1601#ifdef DEBUG_SLAB
1602 memset(p, SLAB_FREE_POISON_BYTE, vsize(p));
1603#endif
1604
1605#ifdef DEBUG_ASAN
1606 asan_free(p, vsize(p));
1607#endif
1608
1609 static_call(free)(p, behavior);
1610}
1611
1612void *vrealloc_full(void *ptr, size_t size, struct alloc_params params) {
1613 if (!ptr)
1614 return valloc_full(size, params);
1615
1616 if (size == 0) {
1617 vfree_full(p: ptr, behavior: params.behavior);
1618 return NULL;
1619 }
1620
1621 size_t old = vsize(ptr);
1622
1623 /* Touch nothing. This can still use the same slab allocation */
1624 size_t old_idx = slab_size_to_index(size: old);
1625 size_t new_idx = slab_size_to_index(size);
1626 if (old_idx == new_idx) {
1627#ifdef DEBUG_ASAN
1628 asan_alloc(ptr, size, old);
1629#endif
1630
1631 return ptr;
1632 }
1633
1634 void *new_ptr = valloc_full(size, params);
1635
1636 if (!new_ptr)
1637 return NULL;
1638
1639 size_t to_copy = MIN(old, size);
1640 memcpy(new_ptr, ptr, to_copy);
1641 vfree(ptr);
1642 return new_ptr;
1643}
1644
1645#ifdef TEST_MEM
1646TEST_EXPORT(slab_map_new);
1647#endif
1648