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