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