1#pragma once
2#include <container_of.h>
3#include <kassert.h>
4#include <math/align.h>
5#include <math/bit_ops.h>
6#include <math/div.h>
7#include <math/ilog2.h>
8#include <mem/alloc.h>
9#include <mem/fixed_size_alloc.h>
10#include <mem/page.h>
11#include <mem/page_alloc.h>
12#include <mem/page_fault.h>
13#include <mem/simple_alloc.h>
14#include <mem/vmm.h>
15#include <smp/domain.h>
16#include <stat_series.h>
17#include <stdatomic.h>
18#include <stdint.h>
19#include <structures/list.h>
20#include <structures/mpmc_queue.h>
21#include <structures/mpsc_list.h>
22#include <structures/rbt.h>
23#include <sync/spinlock.h>
24#include <thread/workqueue.h>
25#include <time/time.h>
26
27LOG_SITE_EXTERN(slab);
28LOG_HANDLE_EXTERN(slab);
29
30#define slab_log(lvl, fmt, ...) \
31 log(LOG_SITE(slab), LOG_HANDLE(slab), lvl, fmt, ##__VA_ARGS__)
32
33#define slab_err(fmt, ...) slab_log(LOG_ERROR, fmt, ##__VA_ARGS__)
34#define slab_warn(fmt, ...) slab_log(LOG_WARN, fmt, ##__VA_ARGS__)
35#define slab_info(fmt, ...) slab_log(LOG_INFO, fmt, ##__VA_ARGS__)
36#define slab_debug(fmt, ...) slab_log(LOG_DEBUG, fmt, ##__VA_ARGS__)
37#define slab_trace(fmt, ...) slab_log(LOG_TRACE, fmt, ##__VA_ARGS__)
38
39/* Lock ordering:
40 *
41 * Slab GC -> Slab cache -> Freequeue -> Slab -> Mag
42 *
43 */
44
45#define KMALLOC_PAGE_MAGIC 0xC0FFEE42
46#define SLAB_ALLOC_BEHAVIOR_FROM_ALLOC ALLOC_BEHAVIOR_AVAIL_BIT(0)
47#define SLAB_ELCM_DEFAULT_MAX_WASTAGE_PCT 5
48
49#define SLAB_HEAP_START 0xFFFFF00000000000ULL
50#define SLAB_HEAP_END 0xFFFFF10000000000ULL
51
52#define SLAB_MAG_ENTRIES 64
53#define SLAB_MAG_WATERMARK_PCT \
54 15 /* Leave 15% of magazine entries for nonpageable requests */
55#define SLAB_MAG_WATERMARK (SLAB_MAG_ENTRIES * SLAB_MAG_WATERMARK_PCT / 100)
56
57#define SLAB_MIN_SIZE (sizeof(uintptr_t))
58#define SLAB_MAX_SIZE (PAGE_SIZE / 4)
59#define SLAB_MAX_PAGES 64
60#define SLAB_POW2_ORDER_COUNT 6 /* 2^6 max */
61#define SLAB_POW2_ORDER_EMPTY 0xE /* Sentinel value, "Nothing here" */
62
63/* Bitmap */
64#define SLAB_BITMAP_BYTES_FOR(x) (DIV_ROUND_UP((x), 64) * sizeof(uint64_t))
65#define SLAB_BITMAP_SET(bm, mask) (bm |= mask)
66#define SLAB_BITMAP_TEST(__bitmap, __idx) (__bitmap & __idx)
67#define SLAB_BITMAP_UNSET(bm, mask) (bm &= ~mask)
68
69#define SLAB_ALIGN_UP(x, a) ALIGN_UP(x, a)
70
71/* GC */
72#define SLAB_GC_FLAG_DESTROY_BIAS_SHIFT 4ull
73#define SLAB_GC_FLAG_DESTROY_BIAS_MASK 0xF
74#define SLAB_GC_FLAG_DESTROY_BIAS_MAX 15
75#define SLAB_GC_FLAG_DESTROY_BIAS_SET(flags, bias) \
76 (flags |= bias << SLAB_GC_FLAG_DESTROY_BIAS_SHIFT)
77
78#define SLAB_GC_FLAG_DESTROY_TARGET_SHIFT 10ull
79#define SLAB_GC_FLAG_DESTROY_TARGET_MASK 0xFFF
80#define SLAB_GC_FLAG_DESTROY_TARGET_MAX 63
81#define SLAB_GC_FLAG_DESTROY_TARGET_SET(flags, target) \
82 (flags |= target << SLAB_GC_FLAG_DESTROY_TARGET_SHIFT)
83
84#define SLAB_GC_FLAG_ORDER_BIAS_SHIFT 16ull
85#define SLAB_GC_FLAG_ORDER_BIAS_MASK 0x3FF
86#define SLAB_GC_FLAG_ORDER_BIAS_SET(flags, order) \
87 (flags |= order << SLAB_GC_FLAG_ORDER_BIAS_SHIFT)
88
89#define SLAB_GC_FLAG_AGG_MASK 0xF
90#define SLAB_GC_SIZE_FACTOR 2
91#define SLAB_GC_RECYCLE_PENALTY 8
92#define SLAB_GC_SCORE_MIN_DELTA 5
93#define SLAB_GC_MAX_UNFIT_SLABS_FACTOR 8
94
95#define SLAB_GC_SCORE_SCALE 1024 /* fixed point scale */
96#define SLAB_GC_WEIGHT_UNDER_SUPPLY 3 /* favor undersupplied orders */
97#define SLAB_GC_WEIGHT_RECYCLED 4 /* penalize orders recycled to */
98#define SLAB_GC_WEIGHT_ORDER_PREFERRED 1 /* prefer close order */
99#define SLAB_GC_ORDER_BIAS_SCALE 4
100
101#define SLAB_FREE_QUEUE_ALLOC_PCT 25 /* Don't do as much */
102
103#define SLAB_FREE_RATIO_PCT 25
104#define SLAB_ORDER_EXCESS_PCT 50
105#define SLAB_SPIKE_THRESHOLD_PCT 50
106
107#define SLAB_CACHE_DISTANCE_WEIGHT 65536 * 64
108#define SLAB_CACHE_FLEXIBLE_DISTANCE_WEIGHT 32768
109
110#define SLAB_EWMA_SCALE 1024 /* Fixed-point precision */
111#define SLAB_EWMA_ALPHA_FP 128
112
113#define SLAB_EWMA_MIN_TOTAL 16 /* below this, GC is less aggressive */
114#define SLAB_EWMA_MIN_SCALE 26 /* min ~0.1 of scale to never fully ignore */
115
116#define SLAB_SCORE_NONPAGEABLE_BETTER_PCT 25 /* must score 25% better */
117
118/* 64 buckets of 250ms granularity = 16 seconds of data */
119#define SLAB_STAT_SERIES_CAPACITY 64
120#define SLAB_STAT_SERIES_BUCKET_US MS_TO_US(250)
121
122#define SLAB_CHUNK_SIZE PAGE_2MB
123
124#define kmalloc_validate_params(size, flags, behavior) \
125 do { \
126 kassert(alloc_flags_valid(flags)); \
127 kassert(alloc_flag_behavior_verify(flags, behavior)); \
128 kassert((size) != 0); \
129 } while (0)
130
131/* This value determines the scale at which cores in a slab domain
132 * will be weighted when they attempt to fill up their per-cpu
133 * caches from free_queue elements.
134 *
135 * It is used to derive a "target amount of elements" to try to drain.
136 *
137 * The computation is as follows:
138 *
139 * target = fq_total_elems / (slab_domain_core_count / REFILL_PER_CORE_WEIGHT)
140 *
141 * Where (slab_domain_core_count / REFILL_PER_CORE_WEIGHT) is at least 1.
142 *
143 * Thus, as this number increases, the portion of all the free_queue elements
144 * that will attempted to be flushed (the target) increases. */
145#define SLAB_PERCPU_REFILL_PER_CORE_WEIGHT 2
146
147enum slab_state {
148 SLAB_FREE = 0,
149 SLAB_PARTIAL = 1,
150 SLAB_FULL = 2,
151 SLAB_STANDARD_STATE_COUNT = 3,
152 SLAB_IN_GC = 4,
153};
154
155/* A little aside on zero types:
156 *
157 * The idea is that for NONPAGEABLE_ZERO, the slab is allocated
158 * and all of its data is zeroed out at the very start
159 *
160 * For PAGEABLE_ZERO, the slab will be optionally demand allocated/
161 * demand paged if insufficient zero pages exist (this will come Soon:tm:)
162 *
163 * Then, the idea is that upon freeing, if we are freeing any sort of ZERO
164 * memory, we will clear it if it's going to a magazine or slab
165 */
166enum slab_type {
167 SLAB_TYPE_NONPAGEABLE,
168 SLAB_TYPE_PAGEABLE,
169 SLAB_TYPE_NONPAGEABLE_ZERO,
170 SLAB_TYPE_PAGEABLE_ZERO,
171 SLAB_TYPE_COUNT,
172 SLAB_TYPE_NONE, /* Sentinel value */
173};
174
175enum slab_magazine_type {
176 SLAB_MAGAZINE_NORMAL,
177 SLAB_MAGAZINE_ZERO,
178 SLAB_MAGAZINE_TYPE_COUNT,
179};
180
181enum slab_crash_code {
182 SLAB_CRASH_CHUNK = CRASH_CODE_DELTA_START,
183 SLAB_CRASH_SLAB,
184 SLAB_CRASH_FREE_QUEUE,
185 SLAB_CRASH_MAGAZINE,
186 SLAB_CRASH_GC,
187 SLAB_CRASH_UAF,
188 SLAB_CRASH_INTERNAL
189};
190
191/*
192 * Memory layout of slab with N pages:
193 * ┌──────────────────────────────────────┐
194 * │ slab │
195 * └──────────────────────────────────────┘
196 * │ │
197 * │ │
198 * │ │
199 * ▼ ▼
200 * ┌────────┐ ┌────────┐ ┌────────┐
201 * │ page 1 │ │ page 2 │ ● ● ● │ page N │
202 * └────────┘ └────────┘ └────────┘
203 * │
204 * └──────────┐
205 * ▼
206 * ┌──────────────────────────────┐┌──────┐
207 * │ slab metadata ││ data │
208 * └──────────────────────────────┘└──────┘
209 * │ │ │
210 * └──┐ └───────┐ └─────────────┐
211 * │ │ │
212 * ▼ ▼ ▼
213 * ┌───────────────┐┌─────────────┐┌───────────────┐
214 * │static metadata││page pointers││bitmap + traces│
215 * └───────────────┘└─────────────┘└───────────────┘
216 */
217
218/* Some notes on demand paged slabs: the slab itself must
219 * always be less than PAGE_SIZE, for now, as that page
220 * will have to be mapped regardless */
221struct slab {
222 uint8_t *bitmap;
223#ifdef DEBUG_SLAB_DEEP
224 stack_handle_t *traces; /* This is used to keep stack traces of the
225 * individual allocations when in DEBUG_DEEP */
226#endif
227 vaddr_t mem; /* Where does the slab data start */
228 size_t used;
229 struct slab_chunk *parent_chunk;
230 struct slab_cache *parent_cache;
231
232 enum slab_type type : 3;
233 enum slab_state state : 3;
234
235 /* Sorted by gc_enqueue_time_ms */
236 struct rbt_node rb;
237 struct list_head list;
238
239 time_ms_t gc_enqueue_time_ms; /* When were we put on the GC list? */
240
241 size_t recycle_count; /* How many times has this been
242 * recycled from the GC list? */
243
244 size_t page_count;
245 _Atomic(struct page *) backing_pages[];
246};
247
248#define SLAB_LIVE_MAGIC 0x51AB1AED51AB1AEDULL
249
250#define slab_from_rbt_node(n) (container_of(n, struct slab, rb))
251#define slab_from_list_node(ln) (container_of(ln, struct slab, list))
252#define NON_SLAB_SPACE(c) \
253 ((c)->pages_per_slab * PAGE_SIZE - sizeof(struct slab) - \
254 (c)->pages_per_slab * sizeof(struct page *))
255
256/* Just a simple stack */
257struct slab_magazine {
258 struct slab_percpu_cache *parent;
259 enum slab_magazine_type type;
260 vaddr_t objs[SLAB_MAG_ENTRIES];
261 size_t count;
262 size_t obj_size;
263};
264
265/* NOTE: This is *why* we disable preemption when entering the slab allocator,
266 * in both the alloc and free paths: shadow_objs and entry_handle */
267struct slab_percpu_cache {
268 struct mpsc_slist defer_frees;
269 struct dpc defer_dpc;
270
271 /* Magazines are always nonpageable */
272 struct slab_magazine *mags[SLAB_MAGAZINE_TYPE_COUNT];
273 struct slab_domain *domain;
274 vaddr_t shadow_objs[SLAB_MAG_ENTRIES + 1]; /* Used in magazine internal
275 * to mitigate risk of
276 * stack allocations */
277};
278
279struct slab_free_queue {
280 struct mpmc_queue mpmc;
281 atomic_size_t count;
282 struct slab_domain *parent;
283};
284#define SLAB_FREE_QUEUE_CAPACITY 256
285#define SLAB_FREE_QUEUE_GET_COUNT(fq) (atomic_load(&(fq)->count))
286#define SLAB_FREE_QUEUE_INC_COUNT(fq) (atomic_fetch_add(&(fq)->count, 1))
287#define SLAB_FREE_QUEUE_ADD_COUNT(fq, n) (atomic_fetch_add(&(fq)->count, n))
288#define SLAB_FREE_QUEUE_SUB_COUNT(fq, n) (atomic_fetch_sub(&(fq)->count, n))
289#define SLAB_FREE_QUEUE_DEC_COUNT(fq) (atomic_fetch_sub(&(fq)->count, 1))
290
291enum slab_chunk_state : uintptr_t {
292 SLAB_CHUNK_FREE,
293 SLAB_CHUNK_PARTIAL,
294 SLAB_CHUNK_USED,
295 SLAB_CHUNK_MAX,
296};
297
298struct slab_chunk {
299 struct list_head list; /* Either on: free list, partial list, used list */
300 /* Chunk allocator that owns this */
301 struct slab_chunks *owner;
302 vaddr_t base_addr : 64 - PAGE_4K_SHIFT;
303 enum slab_chunk_state state : 2;
304
305 /* 10 bits because stride-1 chunks hold 512 slabs, and 512 needs 10 bits.
306 * Using less bits causes this to wrap to 0 so chunk->used == max
307 * never was true, so chunks didn't get freed at larger orders */
308 size_t used : 10;
309 uint8_t bitmap[];
310};
311
312struct slab_chunks {
313 struct slab_cache *parent;
314 size_t bitmap_bytes; /* allocation size: whole 64-bit words */
315 size_t bitmap_bits; /* real slot count */
316 size_t page_stride;
317 size_t pow2_order;
318 struct list_head partial_list;
319 struct list_head used_list;
320 struct fixed_size_range fsr;
321 struct spinlock lock;
322};
323
324struct slab_cache {
325 struct slab_caches *parent;
326 uint64_t obj_size;
327 uint64_t objs_per_slab;
328 uint64_t obj_align;
329 uint64_t obj_stride;
330 size_t pages_per_slab;
331 size_t order;
332 size_t slab_metadata_size;
333 size_t bitmap_bytes;
334
335 struct list_head slabs[SLAB_STANDARD_STATE_COUNT];
336 atomic_size_t slabs_count[SLAB_STANDARD_STATE_COUNT];
337
338 enum slab_type type;
339
340 struct slab_domain *parent_domain;
341
342 /* Exponential weighted moving average */
343 size_t ewma_free_slabs;
344
345 struct spinlock lock;
346 struct slab_chunks chunks;
347};
348
349/* works for both `struct slab_cache` and `struct slab_caches` */
350#define SLAB_CACHE_COUNT_FOR(cache, state) \
351 (atomic_load(&cache->slabs_count[state]))
352
353struct slab_caches {
354 struct slab_cache *caches; /* slab_num_sizes caches */
355 atomic_size_t slabs_count[SLAB_STANDARD_STATE_COUNT];
356};
357
358struct slab_cache_ref {
359 struct slab_domain *domain;
360 struct slab_caches *caches; /* pointer to caches */
361 enum slab_type type; /* pageable / nonpageable */
362 uint8_t locality; /* NUMA proximity, 0 = local */
363};
364
365struct slab_cache_zonelist {
366 struct slab_cache_ref *entries;
367 size_t count;
368};
369
370/* gc_flags: 32 bit bitflags
371 *
372 * ┌───────────────────────────────────────────────────────┐
373 * Bits │ 31..28 27..24 23..18 17..16 15..12 11..8 7..4 3..0 │
374 * Use │ $$$$ $$$$ $$$$ $$$$ ^^^^ ^^SF #### %%%% │
375 * └───────────────────────────────────────────────────────┘
376 *
377 * %%%% - Aggressiveness - Defines how eagerly the GC will try to recycle
378 * or destroy slabs. Doesn't necessarily correspond
379 * to how many pages the GC will try to reclaim,
380 * has more of an impact on how long it will
381 * spend scanning, and to what extent is it
382 * willing to go to destroy slabs (the threshold
383 * of destruction of a slab fluctuates)
384 *
385 * Possible values:
386 *
387 * o Background - background work aggressiveness - this doesn't
388 * have a huge impact on how many slabs it tries
389 * to destroy, but rather, spends more time on slab
390 * recycling, since it's run from a background thread
391 *
392 * o Reclaim - standard reclaim aggressiveness on allocation
393 *
394 * o Standard - standard aggressiveness on normal frees
395 *
396 * o Low Mem - less memory available but OOMs aren't happening
397 *
398 * o Emergency - OOM occurred in allocation path
399 *
400 * o Max - Emergency failed, and the OOM handler chain was called
401 * This is never called from the alloc/free paths
402 *
403 * #### - Destruction bias - Defines how much the GC should bias towards
404 * the destruction of a slab over just recycling it.
405 * If this number is higher, bias towards destruction.
406 * If this number is lower, bias away.
407 *
408 * Value must be [0, 16)
409 *
410 * ^^^^ - Destruction target - Defines what the target amount of slabs the GC
411 * will try to destroy. Must be [0, 64)
412 *
413 * $$$$ - Order Bias bitmap - If this bitmap is not 0, this bitmap
414 * will be used to indicate which orders should
415 * be biased towards. Lower bit index -> lower order.
416 *
417 * F - Fast - skip slowpaths and try to not dilly dally too much
418 * D - Force destroy - always destroy slabs
419 * S - Skip destroy - don't destroy slabs that would've
420 * otherwise been destroyed
421 * R - Reserved - for future use
422 *
423 * * - Unused, not reserved
424 *
425 */
426
427enum slab_gc_flags : uint32_t {
428 SLAB_GC_FLAG_AGG_BG = 0, /* Background work */
429
430 SLAB_GC_FLAG_AGG_RECLAIM = 1, /* Reclaim memory on allocation */
431
432 SLAB_GC_FLAG_AGG_STANDARD = 2, /* Standard aggressiveness on free */
433
434 SLAB_GC_FLAG_AGG_LOW_MEM = 3, /* Running low on memory but not OOMing */
435
436 SLAB_GC_FLAG_AGG_EMERGENCY = 4, /* We are OOMing in an alloc path */
437
438 SLAB_GC_FLAG_AGG_MAX = 5, /* Used in the OOM handler chain - this
439 * will do crazy things like page compaction,
440 * migration, etc., it is never called from
441 * the standard kmalloc/kfree */
442
443 SLAB_GC_FLAG_AGG_COUNT = 6, /* Count */
444
445 SLAB_GC_FLAG_FAST = 1 << 8, /* Try to be fast about it */
446
447 SLAB_GC_FLAG_FORCE_DESTROY = 1 << 9, /* Destroy all slabs */
448
449 SLAB_GC_FLAG_SKIP_DESTROY = 1 << 10, /* Do not destroy slabs that should've
450 * otherwise been destroyed. Just
451 * skip them */
452
453};
454
455struct slab_gc {
456 struct list_head lists[SLAB_TYPE_COUNT][SLAB_POW2_ORDER_COUNT];
457 struct slab_domain *parent;
458 struct rbt rbt;
459 struct spinlock lock;
460 atomic_size_t num_elements;
461};
462
463/* NOTE: Every element in this structure must be `size_t`.
464 *
465 * This is because on bucket reset, when we subtract the
466 * reset bucket from the parent, we treat the parent and the
467 * bucket both as a `size_t` array */
468struct slab_domain_bucket {
469 /* ---- Allocation path stats ---- */
470 atomic_size_t alloc_calls; /* calls to `kmalloc` */
471 atomic_size_t alloc_magazine_hits; /* Local magazine served the alloc */
472 atomic_size_t alloc_page_hits; /* Page allocations serviced */
473 atomic_size_t alloc_local_hits; /* Local domain cache hit (not magazine) */
474 atomic_size_t alloc_remote_hits; /* Remote cache used (cross-core steal) */
475 atomic_size_t alloc_gc_recycle_hits; /* GC provided an available object */
476 atomic_size_t alloc_new_slab; /* Had to allocate a new slab */
477 atomic_size_t alloc_new_remote_slab;
478 atomic_size_t alloc_failures; /* Out of memory or other failures */
479
480 /* ---- Free path stats ---- */
481 atomic_size_t free_calls; /* Total calls to kfree() */
482 atomic_size_t free_to_ring; /* Freed into local freequeue ringbuffer */
483 atomic_size_t free_to_local_slab; /* Freed directly into local slab */
484 atomic_size_t free_to_remote_domain; /* Freed to other domain's freelist */
485 atomic_size_t free_to_percpu;
486
487 /* Other */
488 atomic_size_t freequeue_enqueues;
489 atomic_size_t freequeue_dequeues;
490 atomic_size_t gc_collections; /* Number of times GC ran */
491 atomic_size_t gc_objects_reclaimed; /* Objects GC returned to free state */
492};
493
494struct slab_domain {
495 /* Actual domain that this corresponds to */
496 struct domain *domain;
497
498 /* This domain's slab caches */
499 struct slab_caches *caches[SLAB_TYPE_COUNT];
500
501 /* Slab caches for each distance */
502 struct slab_cache_zonelist zonelists[SLAB_TYPE_COUNT];
503 size_t zonelist_entry_count;
504
505 /* Pointer to an array of pointers to per CPU single-slabs for each class */
506 /* # CPUs determined by the domain struct */
507 struct slab_percpu_cache **percpu_caches;
508
509 /* Freequeue for remote frees */
510 struct slab_free_queue free_queue;
511
512 /* List of slabs that are reusable and can be
513 * garbage collected safely/kept here */
514 struct slab_gc slab_gc;
515
516 struct daemon *daemon;
517
518 struct workqueue *workqueue;
519
520 struct stat_series *stats;
521 struct slab_domain_bucket *buckets;
522 struct slab_domain_bucket aggregate;
523};
524
525struct slab_globals {
526 bool domains_enabled;
527 struct vas *vas;
528 struct slab_caches caches;
529 struct slab_size_constant *class_sizes;
530 size_t num_sizes;
531 _Atomic uint8_t *order_map;
532};
533
534static inline struct domain_buddy *
535slab_domain_buddy(struct slab_domain *domain) {
536 return domain->domain->domain_buddy;
537}
538
539struct slab_page_hdr {
540 uint32_t magic;
541 bool pageable : 1;
542 uint32_t pages : 31;
543 struct slab_domain *domain;
544 stack_handle_t handle;
545};
546
547struct slab *slab_init(struct slab *slab, struct slab_cache *parent);
548void slab_destroy(struct slab *slab);
549void slab_domain_init_daemon(struct slab_domain *domain);
550void slab_domain_init_workqueue(struct slab_domain *domain);
551int32_t slab_size_to_index(size_t size);
552size_t slab_allocation_index(struct slab *slab, void *ptr);
553void *slab_alloc_old(struct slab_cache *cache);
554void slab_free_page_hdr(struct slab_page_hdr *hdr, enum alloc_behavior bh);
555size_t slab_allocation_size(vaddr_t addr);
556void slab_free(struct slab_domain *domain, void *obj);
557void *slab_cache_try_alloc_from_lists(struct slab_cache *c,
558 stack_handle_t handle);
559void slab_cache_init(size_t order, struct slab_cache *cache,
560 struct slab_size_constant *ssc);
561void slab_cache_insert(struct slab_cache *cache, struct slab *slab);
562struct slab *slab_create(struct slab_cache *cache,
563 enum alloc_behavior behavior);
564void *slab_alloc(struct slab_cache *cache, stack_handle_t handle,
565 enum alloc_behavior behavior);
566struct slab *slab_for_ptr(void *ptr);
567
568/* Magazine + percpu */
569bool slab_magazine_push(struct slab_magazine *mag, vaddr_t obj);
570vaddr_t slab_magazine_pop(struct slab_magazine *mag);
571void slab_free_addr_to_cache(void *addr, enum alloc_behavior bh);
572void slab_domain_percpu_init(struct slab_domain *domain);
573void slab_percpu_flush(struct slab_domain *dom, struct slab_percpu_cache *pc,
574 size_t class_idx, vaddr_t overflow_obj);
575void slab_percpu_refill(struct slab_domain *dom,
576 struct slab_percpu_cache *cache, enum alloc_flags flags,
577 enum alloc_behavior behavior);
578
579/* Freequeue */
580void slab_free_queue_init(struct slab_domain *domain, struct slab_free_queue *q,
581 size_t capacity);
582bool slab_free_queue_ringbuffer_enqueue(struct slab_free_queue *q,
583 vaddr_t addr);
584vaddr_t slab_free_queue_ringbuffer_dequeue(struct slab_free_queue *q);
585vaddr_t slab_free_queue_dequeue(struct slab_free_queue *q);
586size_t slab_free_queue_drain(struct slab_percpu_cache *cache,
587 struct slab_free_queue *queue, size_t target,
588 enum alloc_behavior bh);
589size_t slab_free_queue_get_target_drain(struct slab_domain *domain, size_t pct);
590size_t slab_free_queue_drain_limited(struct slab_percpu_cache *pc,
591 struct slab_domain *dom, size_t pct,
592 enum alloc_behavior bh);
593
594/* Check */
595bool slab_check(struct slab *slab);
596#define slab_check_assert(slab) kassert(slab_check(slab))
597
598/* GC */
599
600/* Returns # slabs removed from GC list - maybe recycled, maybe destroyed */
601size_t slab_gc_run(struct slab_gc *gc, enum slab_gc_flags flags);
602struct slab *slab_reset(struct slab *slab);
603void slab_gc_init(struct slab_domain *dom);
604void slab_gc_enqueue(struct slab_domain *domain, struct slab *slab);
605size_t slab_gc_num_slabs(struct slab_domain *domain);
606bool slab_should_enqueue_gc(struct slab *slab);
607struct slab *slab_gc_get_for_cache(struct slab_cache *sc);
608
609void slab_switch_to_domain_allocations(void);
610
611/* ELCM for slab allocator */
612struct slab_elcm_candidate slab_elcm(size_t obj_size, size_t obj_alignment);
613void slab_elcm_initialize();
614
615/* Resizing */
616bool slab_resize(struct slab *slab, size_t new_size_pages);
617bool slab_can_resize_to(struct slab *slab, size_t new_size_pages);
618
619/* Order map */
620uint8_t slab_order_map_get(vaddr_t addr);
621void slab_order_map_set(vaddr_t addr, uint8_t order);
622void slab_order_map_init(void);
623
624/* Chunks */
625vaddr_t slab_chunks_alloc(struct slab_chunks *sc, struct slab_chunk **out);
626void slab_chunks_free(struct slab_chunks *sc, struct slab_chunk *chunk,
627 vaddr_t addr);
628void slab_chunks_init(struct slab_chunks *sc, struct slab_cache *parent);
629bool kmalloc_ptr_in_slab_validate(void *ptr);
630
631/* Debug checks */
632#ifdef DEBUG_SLAB_DEEP
633void slab_track_event(vaddr_t addr, uint64_t ra0, uint64_t ra1, bool is_alloc);
634void slab_track_dump(const char *label, vaddr_t addr);
635void slab_debug_assert_not_already_free(vaddr_t v, int32_t class);
636void slab_dump_corruption(void *obj, struct slab_magazine *popped_mag,
637 size_t obj_size);
638#endif
639
640extern struct slab_globals slab_global;
641extern struct page_fault_handler slab_page_fault_handler;
642
643/* Recall that the EWMA formula is
644 *
645 * ewma_t = (ewma_(t - 1) * (1 - alpha)) + (alpha * r)
646 *
647 * where r is the value that we are scaling with
648 */
649static inline void slab_gc_update_ewma(struct slab_cache *cache) {
650 size_t free_slabs = cache->slabs_count[SLAB_FREE];
651
652 if (cache->ewma_free_slabs == 0) {
653 cache->ewma_free_slabs = free_slabs;
654 } else {
655 size_t new_ewma =
656 ((cache->ewma_free_slabs * (SLAB_EWMA_SCALE - SLAB_EWMA_ALPHA_FP)) +
657 (free_slabs * SLAB_EWMA_ALPHA_FP)) /
658 SLAB_EWMA_SCALE;
659
660 /* ensure growth for very small counts */
661 if (new_ewma == 0 && free_slabs > 0)
662 new_ewma = 1;
663
664 cache->ewma_free_slabs = new_ewma;
665 }
666}
667
668static inline struct slab_page_hdr *slab_page_hdr_for_addr(void *ptr) {
669 return (struct slab_page_hdr *) PAGE_ALIGN_DOWN(ptr);
670}
671
672static inline size_t slab_object_count(struct slab *slab) {
673 return slab->parent_cache->objs_per_slab;
674}
675
676static inline size_t slab_object_size(struct slab *slab) {
677 return slab->parent_cache->obj_size;
678}
679
680/* IRQL_DISPATCH is guaranteed when entering the allocator */
681static inline struct slab_domain *slab_domain_local(void) {
682 return smp_core(cond: TOPC_IRQL)->domain->slab_domain;
683}
684
685static inline struct slab_percpu_cache *slab_percpu_cache_local(void) {
686 return slab_domain_local()
687 ->percpu_caches[smp_core(cond: TOPC_IRQL)->domain_cpu_id];
688}
689
690static inline void slab_list_del(struct slab *slab) {
691 if (slab->state != SLAB_IN_GC) {
692 SPINLOCK_ASSERT_HELD(&slab->parent_cache->lock);
693 } else {
694 SPINLOCK_ASSERT_HELD(&slab->parent_cache->parent_domain->slab_gc.lock);
695 }
696
697 enum slab_state state = slab->state;
698 list_del_init(entry: &slab->list);
699
700 if (state != SLAB_IN_GC) {
701 if (state == SLAB_FREE)
702 slab_gc_update_ewma(cache: slab->parent_cache);
703
704 atomic_fetch_sub(&slab->parent_cache->slabs_count[state], 1);
705 atomic_fetch_sub(&slab->parent_cache->parent->slabs_count[state], 1);
706 }
707}
708
709static inline void slab_list_add(struct slab_cache *cache, struct slab *slab) {
710 enum slab_state state = slab->state;
711 slab->parent_cache = cache;
712 list_add_tail(new: &slab->list, head: &cache->slabs[state]);
713
714 if (state == SLAB_FREE)
715 slab_gc_update_ewma(cache);
716
717 atomic_fetch_add(&slab->parent_cache->slabs_count[state], 1);
718 atomic_fetch_add(&slab->parent_cache->parent->slabs_count[state], 1);
719}
720
721static inline void slab_move(struct slab_cache *c, struct slab *slab,
722 enum slab_state new) {
723 kassert(spinlock_locked(&c->lock));
724 slab_list_del(slab);
725
726 slab->state = new;
727
728 slab_list_add(cache: c, slab);
729}
730
731static inline void slab_byte_index_and_mask(uint64_t index,
732 uint64_t *byte_idx_out,
733 uint8_t *bitmask_out) {
734 *byte_idx_out = index / 8ULL;
735 *bitmask_out = (uint8_t) (1ULL << (index % 8ULL));
736}
737
738static inline void slab_index_and_mask(struct slab *slab, void *obj,
739 uint64_t *byte_idx_out,
740 uint8_t *bitmask_out) {
741 uint64_t index =
742 ((vaddr_t) obj - slab->mem) / slab->parent_cache->obj_stride;
743 slab_byte_index_and_mask(index, byte_idx_out, bitmask_out);
744}
745
746static inline struct slab_cache *slab_caches_alloc() {
747 return simple_alloc(space: slab_global.vas,
748 size: sizeof(struct slab_cache) * slab_global.num_sizes);
749}
750
751static inline stack_handle_t *slab_get_traces_location(struct slab *s) {
752 uint8_t *base = (uint8_t *) s + sizeof(struct slab);
753 return (stack_handle_t *) (base + sizeof(struct page *) *
754 s->parent_cache->pages_per_slab);
755}
756
757#ifdef DEBUG_SLAB_DEEP
758
759static inline uint8_t *slab_get_bitmap_location(struct slab *s) {
760 uint8_t *base = (uint8_t *) slab_get_traces_location(s);
761 return base + sizeof(stack_handle_t) * s->parent_cache->objs_per_slab;
762}
763
764#else
765
766static inline uint8_t *slab_get_bitmap_location(struct slab *s) {
767 uint8_t *base = (uint8_t *) s + sizeof(struct slab);
768 return base + sizeof(struct page *) * s->parent_cache->pages_per_slab;
769}
770
771#endif
772
773static inline uint64_t slab_page_flags(enum slab_type type) {
774 uint64_t pflags = PAGE_PRESENT | PAGE_WRITE | PAGE_XD;
775 kassert(type != SLAB_TYPE_NONE);
776 if (type == SLAB_TYPE_PAGEABLE || type == SLAB_TYPE_PAGEABLE_ZERO)
777 pflags |= PAGE_PAGEABLE;
778
779 return pflags;
780}
781
782static inline bool slab_ptr_in_slab(void *ptr) {
783 vaddr_t vaddr = (vaddr_t) ptr;
784 return vaddr >= SLAB_HEAP_START && vaddr <= SLAB_HEAP_END;
785}
786
787static inline size_t slab_cache_pow2_order(struct slab_cache *sc) {
788 return ilog2(x: next_pow2(x: sc->pages_per_slab));
789}
790
791static inline size_t slab_pow2_order(struct slab *slab) {
792 return slab_cache_pow2_order(sc: slab->parent_cache);
793}
794
795static inline bool slab_is_pageable(struct slab *s) {
796 return s->type == SLAB_TYPE_PAGEABLE || s->type == SLAB_TYPE_PAGEABLE_ZERO;
797}
798
799static inline bool slab_is_zeroed(struct slab *s) {
800 return s->type == SLAB_TYPE_PAGEABLE_ZERO ||
801 s->type == SLAB_TYPE_NONPAGEABLE_ZERO;
802}
803
804static inline bool slab_cache_is_pageable(struct slab_cache *c) {
805 return c->type == SLAB_TYPE_PAGEABLE || c->type == SLAB_TYPE_PAGEABLE_ZERO;
806}
807
808__no_sanitize_address static inline bool
809is_buffer_uniform(const void *ptr, size_t len, uint8_t value) {
810 const uint8_t *byte_ptr = (const uint8_t *) ptr;
811
812 for (size_t i = 0; i < len; i++)
813 if (byte_ptr[i] != value)
814 return false;
815
816 return true;
817}
818
819#ifdef TEST_MEM
820#include "tests/import.h"
821#endif
822