1#include <math/bit.h>
2#include <math/min_max.h>
3#include <sch/sched.h>
4#include <stack_depot.h>
5
6#include "gc_internal.h"
7
8/* Derive the amount of slabs we should attempt to free */
9static size_t slab_gc_derive_target_gc_slabs(struct slab_gc *gc,
10 enum slab_gc_flags flags) {
11 enum slab_gc_flags aggressiveness = flags & SLAB_GC_FLAG_AGG_MASK;
12 const size_t max = gc_agg_scan_max[aggressiveness];
13 const size_t pct = gc_agg_scan_pct[aggressiveness];
14 size_t target = atomic_load(&gc->num_elements) * pct / 100;
15 return MIN(target, max);
16}
17
18static size_t slab_gc_score(struct slab *slab, enum slab_gc_flags flags) {
19 enum slab_gc_flags aggressiveness = flags & SLAB_GC_FLAG_AGG_MASK;
20 size_t age_factor_pct = gc_agg_age_factor_pct[aggressiveness];
21 size_t size_factor_pct = gc_agg_size_factor_pct[aggressiveness];
22 size_t recycle_penalty_pct = gc_agg_recycle_penalty_pct[aggressiveness];
23
24 size_t size_part_raw = SLAB_GC_SIZE_FACTOR * slab->page_count;
25 time_ms_t age_seconds = time_get_ms() - slab->gc_enqueue_time_ms;
26 size_t recycle_part_raw = SLAB_GC_RECYCLE_PENALTY * slab->recycle_count;
27
28 size_t size_part = size_part_raw * size_factor_pct / 100;
29 size_t recycle_part = recycle_part_raw * recycle_penalty_pct / 100;
30 size_t age_part = (size_t) age_seconds * age_factor_pct / 100;
31
32 size_t score = age_part + size_part - recycle_part;
33
34 return score;
35}
36
37static inline size_t scale_bias(uint8_t bias, size_t pct) {
38 return ((100 - pct) * bias / 100);
39}
40
41static bool slab_gc_should_recycle(struct slab *slab, uint8_t bias_destroy) {
42 enforce_precond(bias_destroy < 16);
43
44 struct slab_cache *parent = slab->parent_cache;
45 struct slab_caches *parent_caches = parent->parent;
46 size_t class = SLAB_CACHE_COUNT_FOR(parent, SLAB_FREE);
47 size_t total = SLAB_CACHE_COUNT_FOR(parent_caches, SLAB_FREE);
48 size_t avg = total / slab_global.num_sizes;
49 size_t smoothed = parent->ewma_free_slabs;
50
51 /* scale the thresholds by bias_destroy: higher bias = more destruction */
52 int bias = 100 - (bias_destroy * 5); /* range: 100 -> 25% */
53 if (bias < 25)
54 bias = 25;
55
56 /* Apply scaled thresholds */
57 class *= 100;
58
59 bool below_free_ratio = class < total * (SLAB_FREE_RATIO_PCT * bias / 100);
60 bool excess = class < avg * scale_bias(bias, SLAB_ORDER_EXCESS_PCT);
61 bool dip = class < smoothed * scale_bias(bias, SLAB_SPIKE_THRESHOLD_PCT);
62
63 return below_free_ratio || excess || dip;
64}
65
66static size_t slab_gc_get_total_free_for(struct slab_caches *caches,
67 size_t *free_per_order) {
68 size_t total_free = 0;
69 for (size_t i = 0; i < slab_global.num_sizes; i++) {
70 free_per_order[i] = SLAB_CACHE_COUNT_FOR(caches, SLAB_FREE);
71 total_free += free_per_order[i];
72 }
73
74 return total_free;
75}
76
77static int32_t slab_gc_get_inv_free(size_t total_free, uint32_t bias_bitmap,
78 size_t order, size_t *free_per_order) {
79 int32_t inv_free;
80 if (total_free == 0) {
81 /* prefer the original order or smaller ones */
82 inv_free = SLAB_GC_SCORE_SCALE;
83 } else {
84 size_t other_free_slabs = total_free - free_per_order[order];
85 size_t scaled_bias = other_free_slabs * SLAB_GC_SCORE_SCALE;
86 if (BIT_TEST(bias_bitmap, order))
87 scaled_bias *= SLAB_GC_ORDER_BIAS_SCALE;
88
89 inv_free = scaled_bias / (1 + total_free);
90 }
91
92 return inv_free;
93}
94
95static int64_t slab_gc_get_order_score(size_t inv_free, size_t order,
96 size_t *slabs_recycled) {
97 /* scale down by how many we've already thrown into this order */
98 size_t recycled = slabs_recycled[order];
99 recycled = (recycled * SLAB_GC_SCORE_SCALE) / (recycled + 1);
100
101 size_t recycled_weight = SLAB_GC_WEIGHT_RECYCLED * recycled;
102 size_t supply_weight = SLAB_GC_WEIGHT_UNDER_SUPPLY * inv_free;
103 return supply_weight - recycled_weight;
104}
105
106/* prefer under-supplied orders (lower free_per_order)
107 * and penalize orders we've already recycled to */
108static int64_t score_order(size_t total_free, uint32_t bias_map, size_t order,
109 size_t *free_per_order, size_t *recycled,
110 size_t original_order) {
111 int32_t inv_free =
112 slab_gc_get_inv_free(total_free, bias_bitmap: bias_map, order, free_per_order);
113 int64_t score = slab_gc_get_order_score(inv_free, order, slabs_recycled: recycled);
114
115 /* prefer the original order */
116 if (order == original_order)
117 score += SLAB_GC_WEIGHT_ORDER_PREFERRED * SLAB_GC_SCORE_SCALE;
118 else {
119 /* prefer smaller order index difference */
120 bool far = order > original_order;
121 int64_t dist = far ? order - original_order : original_order - order;
122 score -= dist; /* negative penalty for farther classes */
123 }
124 return score;
125}
126
127static void slab_gc_dequeue(struct slab_gc *gc, struct slab *slab);
128
129static struct slab_caches *slab_gc_pick_caches(struct slab_domain *domain,
130 struct slab *slab) {
131 return domain->caches[slab->type];
132}
133
134static void slab_recycle(struct slab_cache *best, struct slab *slab,
135 size_t *slabs_recycled, size_t idx) {
136
137 slab->recycle_count++;
138 slab_cache_insert(cache: best, slab);
139
140 slabs_recycled[idx]++;
141}
142
143/* When choosing which cache order we want to recycle to, we need
144 * to consider both the amount of free slabs in the cache order,
145 * and the amount of slabs we have already recycled to that order,
146 * to prevent overly aggressive draining to one order */
147static void slab_gc_recycle(struct slab_domain *domain, struct slab *slab,
148 size_t *slabs_recycled, uint32_t bias_bitmap) {
149 /* Precondition: caller has taken this slab out of GC and dropped gc->lock,
150 * slab_cache_insert takes the cache lock, so we can't hold gc->lock */
151 struct slab_caches *caches = slab_gc_pick_caches(domain, slab);
152
153 /* Gather totals */
154 size_t free_per_order[slab_global.num_sizes];
155 size_t total_free = slab_gc_get_total_free_for(caches, free_per_order);
156 size_t original_order = slab->parent_cache->order;
157
158 int32_t best_idx = original_order; /* Default */
159 int64_t best_score = INT64_MIN;
160
161 for (size_t i = 0; i < slab_global.num_sizes; i++) {
162 int64_t score = score_order(total_free, bias_map: bias_bitmap, order: i, free_per_order,
163 recycled: slabs_recycled, original_order);
164
165 if (score > best_score) {
166 best_score = score;
167 best_idx = i;
168 }
169 }
170
171 /* We did it! */
172 slab_recycle(best: &caches->caches[best_idx], slab, slabs_recycled, idx: best_idx);
173}
174
175static void slab_gc_destroy(struct slab_gc *gc, struct slab *slab) {
176 rbt_delete(tree: &gc->rbt, z: &slab->rb);
177 atomic_dec(&gc->num_elements);
178 /* List unlink happens in slab_destroy -> slab_list_del */
179 slab_destroy(slab);
180}
181
182static inline uint8_t slab_flags_get_bias(enum slab_gc_flags flags) {
183 uint8_t bias = flags >> SLAB_GC_FLAG_DESTROY_BIAS_SHIFT;
184 bias &= SLAB_GC_FLAG_DESTROY_BIAS_MASK;
185 return bias;
186}
187
188static inline uint32_t
189slab_flags_get_order_bias_bitmap(enum slab_gc_flags flags) {
190 uint32_t order_bias_bitmap = flags >> SLAB_GC_FLAG_ORDER_BIAS_SHIFT;
191 order_bias_bitmap &= SLAB_GC_FLAG_ORDER_BIAS_MASK;
192 return order_bias_bitmap;
193}
194
195static bool slab_do_gc(struct slab_gc *gc, struct slab *slab,
196 enum slab_gc_flags flags, size_t *destroyed,
197 size_t destroy_target, struct list_head *pending) {
198
199 uint8_t bias = slab_flags_get_bias(flags);
200
201 if (flags & SLAB_GC_FLAG_FORCE_DESTROY || *destroyed < destroy_target) {
202 slab_gc_destroy(gc, slab);
203 (*destroyed)++;
204 return true;
205 }
206
207 bool recycle = slab_gc_should_recycle(slab, bias_destroy: bias);
208
209 if (recycle) {
210 list_node_delete_init(n: &slab->list);
211 slab_gc_dequeue(gc, slab);
212 list_head_push_back(h: pending, n: &slab->list);
213 } else if (flags & SLAB_GC_FLAG_SKIP_DESTROY) {
214 return false;
215 } else {
216 slab_gc_destroy(gc, slab);
217 (*destroyed)++;
218 }
219
220 return true;
221}
222
223static size_t slab_gc_derive_threshold_score(struct slab_gc *gc,
224 enum slab_gc_flags flags) {
225 enum slab_gc_flags aggressiveness = flags & SLAB_GC_FLAG_AGG_MASK;
226 struct rbt_node *min = rbt_min(tree: &gc->rbt);
227 struct rbt_node *max = rbt_last(root: &gc->rbt);
228
229 if (!min || !max)
230 return 0; /* We have no slabs or just one in GC */
231
232 struct slab *min_slab = slab_from_rbt_node(min);
233 struct slab *max_slab = slab_from_rbt_node(max);
234 size_t min_score = slab_gc_score(slab: min_slab, flags: aggressiveness);
235 size_t max_score = slab_gc_score(slab: max_slab, flags: aggressiveness);
236
237 if (min_score >= max_score)
238 min_score = max_score - SLAB_GC_SCORE_MIN_DELTA;
239
240 size_t score_delta = max_score - min_score;
241
242 /* compute range midpoint / threshold */
243 size_t threshold_score = max_score / 2;
244 threshold_score += score_delta * slab_flags_get_bias(flags) /
245 SLAB_GC_FLAG_DESTROY_BIAS_MAX * 2;
246 return threshold_score;
247}
248
249static inline size_t slab_gc_get_max_unfit_slabs(size_t target,
250 enum slab_gc_flags flags) {
251 enum slab_gc_flags aggressiveness = flags & SLAB_GC_FLAG_AGG_MASK;
252 return target / gc_agg_max_unfit_slabs[aggressiveness];
253}
254
255/* DON'T run GC on slab creation (if there are no available slabs).
256 * This is a slow function! The slab cache lock must not be held when
257 * calling this function because this will lock the slab cache */
258size_t slab_gc_run(struct slab_gc *gc, enum slab_gc_flags flags) {
259 enum irql irql = spin_lock(&gc->lock);
260
261 size_t slabs_recycled[slab_global.num_sizes];
262 memset(slabs_recycled, 0, sizeof(size_t) * slab_global.num_sizes);
263 size_t target = slab_gc_derive_target_gc_slabs(gc, flags);
264 size_t threshold = slab_gc_derive_threshold_score(gc, flags);
265 size_t max_unfit = slab_gc_get_max_unfit_slabs(target, flags);
266 size_t destroy_target = (flags >> SLAB_GC_FLAG_DESTROY_TARGET_SHIFT) &
267 SLAB_GC_FLAG_DESTROY_TARGET_MASK;
268
269 size_t reclaimed = 0;
270 size_t unfit = 0;
271 size_t destroyed = 0;
272
273 struct list_head pending;
274 list_head_init(h: &pending);
275
276 struct rbt_node *node = rbt_min(tree: &gc->rbt);
277 while (node && reclaimed < target) {
278 struct rbt_node *next = rbt_next(node);
279 struct slab *slab = slab_from_rbt_node(node);
280
281 if (slab_gc_score(slab, flags) < threshold) {
282 if (++unfit >= max_unfit || flags & SLAB_GC_FLAG_FAST)
283 break;
284
285 goto next_slab;
286 }
287
288 unfit = 0;
289 if (slab_do_gc(gc, slab, flags, destroyed: &destroyed, destroy_target, pending: &pending))
290 reclaimed++;
291
292 next_slab:
293 node = next;
294 }
295
296 spin_unlock(&gc->lock, irql);
297
298 uint32_t order_bias_bitmap = slab_flags_get_order_bias_bitmap(flags);
299 struct list_node *pnode, *ptemp;
300 list_for_each_safe(pnode, ptemp, &pending) {
301 struct slab *s = slab_from_list_node(pnode);
302 list_node_delete_init(n: pnode);
303 slab_gc_recycle(domain: s->parent_cache->parent_domain, slab: s, slabs_recycled,
304 bias_bitmap: order_bias_bitmap);
305 }
306
307 return reclaimed;
308}
309
310void slab_gc_enqueue(struct slab_domain *domain, struct slab *slab) {
311 /* We do NOT reset the slab here in case we recycle it back
312 * to the same order it was pulled from */
313 slab->state = SLAB_IN_GC;
314 slab->gc_enqueue_time_ms = time_get_ms();
315
316 struct slab_gc *gc = &domain->slab_gc;
317 enum irql irql = spin_lock(&gc->lock);
318
319 /* Put it in the right order */
320 size_t order = slab_pow2_order(slab);
321
322 list_head_push_back(h: &domain->slab_gc.lists[slab->type][order], n: &slab->list);
323
324 rbt_insert(tree: &domain->slab_gc.rbt, new_node: &slab->rb);
325 atomic_inc(&gc->num_elements);
326
327 spin_unlock(&gc->lock, irql);
328}
329
330static void slab_gc_dequeue(struct slab_gc *gc, struct slab *slab) {
331 SPINLOCK_ASSERT_HELD(&gc->lock);
332
333 rbt_delete(tree: &gc->rbt, z: &slab->rb);
334 atomic_dec(&gc->num_elements);
335
336 /* We need to drop all the traces here */
337#ifdef DEBUG_SLAB_DEEP
338 for (size_t i = 0; i < slab->parent_cache->objs_per_slab; i++) {
339 if (slab->traces[i])
340 stack_depot_putref(slab->traces[i]);
341
342 slab->traces[i] = NULL;
343 }
344#endif
345
346 slab->gc_enqueue_time_ms = 0;
347 slab->state = SLAB_FREE;
348}
349
350struct slab *slab_gc_get_for_cache(struct slab_cache *sc) {
351 struct slab *ret = NULL;
352 struct slab_gc *sgc = &sc->parent_domain->slab_gc;
353 size_t pow2_order = slab_cache_pow2_order(sc);
354
355 struct list_head *lh;
356
357 lh = &sgc->lists[sc->type][pow2_order];
358
359 enum irql irql = spin_lock(&sgc->lock);
360
361 struct list_node *got = list_head_pop_back_init(h: lh);
362 if (!got)
363 goto out;
364
365 ret = slab_from_list_node(got);
366 slab_gc_dequeue(gc: sgc, slab: ret);
367
368out:
369 spin_unlock(&sgc->lock, irql);
370 return ret;
371}
372
373size_t slab_gc_num_slabs(struct slab_domain *domain) {
374 return atomic_load(&domain->slab_gc.num_elements);
375}
376
377static size_t slab_get_data(struct rbt_node *node) {
378 return slab_from_rbt_node(node)->gc_enqueue_time_ms;
379}
380
381static int32_t slab_cmp_slabs(const struct rbt_node *a,
382 const struct rbt_node *b) {
383 int32_t sa = slab_get_data(node: (void *) a);
384 int32_t sb = slab_get_data(node: (void *) b);
385 return sa - sb;
386}
387
388bool slab_should_enqueue_gc(struct slab *slab) {
389 struct slab_cache *parent = slab->parent_cache;
390 struct slab_caches *parent_caches = parent->parent;
391
392 size_t class = SLAB_CACHE_COUNT_FOR(parent, SLAB_FREE);
393 size_t total = SLAB_CACHE_COUNT_FOR(parent_caches, SLAB_FREE);
394
395 /* skip GC for tiny totals */
396 if (total < SLAB_EWMA_MIN_TOTAL || class < SLAB_EWMA_MIN_TOTAL)
397 return false;
398
399 size_t avg = total / slab_global.num_sizes;
400 size_t smoothed = parent->ewma_free_slabs;
401
402 /* scale thresholds for mid-sized caches */
403 size_t scale = SLAB_EWMA_SCALE;
404 if (total < (SLAB_EWMA_MIN_TOTAL * 4)) {
405 scale = (total * SLAB_EWMA_SCALE) / (SLAB_EWMA_MIN_TOTAL * 4);
406 if (scale < SLAB_EWMA_MIN_SCALE)
407 scale = SLAB_EWMA_MIN_SCALE;
408 }
409
410 size_t spike_threshold =
411 (smoothed * (100 + SLAB_SPIKE_THRESHOLD_PCT) * scale) / SLAB_EWMA_SCALE;
412 size_t free_ratio_threshold =
413 (total * SLAB_FREE_RATIO_PCT * scale) / (100 * SLAB_EWMA_SCALE);
414 size_t excess_threshold =
415 (avg * (100 + SLAB_ORDER_EXCESS_PCT) * scale) / SLAB_EWMA_SCALE;
416
417 bool spike = class * 100 > spike_threshold;
418 bool exceeds_free_ratio = class > free_ratio_threshold;
419 bool exceeds_excess = class > excess_threshold;
420
421 return exceeds_free_ratio || exceeds_excess || spike;
422}
423
424void slab_gc_init(struct slab_domain *dom) {
425 struct slab_gc *gc = &dom->slab_gc;
426 atomic_init(&gc->num_elements, 0);
427 spinlock_init(&gc->lock);
428 rbt_init(t: &gc->rbt, get_data: slab_get_data, compare: slab_cmp_slabs);
429 gc->parent = dom;
430 for (size_t i = 0; i < SLAB_POW2_ORDER_COUNT; i++) {
431 for (int j = 0; j < SLAB_TYPE_COUNT; j++) {
432 list_head_init(h: &gc->lists[j][i]);
433 }
434 }
435}
436