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