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