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