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