1#include <compiler/core.h>
2#include <compiler/intrinsic.h>
3#include <enforce.h>
4#include <math/align.h>
5#include <math/arith.h>
6#include <math/bit.h>
7#include <math/fixed.h>
8#include <math/range.h>
9#include <math/sort.h>
10#include <math/units.h>
11#include <mem/alloc.h>
12#include <mem/elcm.h>
13#include <mem/nofail.h>
14#include <mem/page.h>
15
16/*
17 * L = Lower a^2
18 * U = Upper b^2
19 *
20 * pp(n) = { 1, if popcount(n) == 1
21 * { 1 - ((U - n) / (U - L)), otherwise
22 */
23static fx32_32_t pow2_proximity(size_t n) {
24 if (n == 0)
25 return 0.0;
26
27 if (popcount(n) == 1)
28 return FX_ONE;
29
30 size_t bit_len = 64 - ci_clzll(n);
31 size_t upper = 1ULL << bit_len;
32 size_t lower = upper >> 1;
33
34 size_t dist = upper - n;
35 size_t span = upper - lower;
36
37 fx32_32_t dist_fx = fx_from_int(x: dist);
38 fx32_32_t span_fx = fx_from_int(x: span);
39
40 return FX_ONE - fx_div(a: dist_fx, b: span_fx);
41}
42
43/* The closer to `min`, the closer to 1 the output will be
44 *
45 * m = min, M = max
46 * r = M - m
47 * lcsf(m, M, n) = ln(e - { [ (e - 1) * (n - m) ] / r})
48 */
49static fx32_32_t log_clamped_scale_factor(size_t min, size_t max, size_t n) {
50 enforce_precond(max > min);
51 enforce_precond(IN_RANGE(n, min, max));
52
53 fx32_32_t f_max = fx_from_int(x: max);
54 fx32_32_t f_min = fx_from_int(x: min);
55 fx32_32_t f_n = fx_from_int(x: n);
56 fx32_32_t f_range = f_max - f_min;
57
58 /* Clamp to [1, e] */
59 fx32_32_t range = FX_E - FX_ONE;
60 fx32_32_t n_scaled = fx_mul(a: fx_div(a: f_n - f_min, b: f_range), b: range);
61
62 /* Log range is [0, 1] */
63 return fx_ln(FX_E - n_scaled);
64}
65
66/*
67 * pps(m, M, n) = pp(n) * lcsf(m, M, n)
68 */
69static fx32_32_t pow2_proximity_scaled(size_t min, size_t max, size_t n) {
70 fx32_32_t prox = pow2_proximity(n);
71
72 /* Scale prox with log */
73 return fx_mul(a: prox, b: log_clamped_scale_factor(min, max, n));
74}
75
76/*
77 * cs(w, d, m, M, W) = [ 1 - (w / W) ] * lcsf(m, M, m + M - d)
78 */
79static fx32_32_t candidate_score(const struct elcm_candidate *c, size_t mind,
80 size_t maxd, fx32_32_t max_wastage) {
81 enforce(c->wasted);
82 fx32_32_t wastage_scaled = fx_div(a: c->wastage, b: max_wastage);
83
84 size_t n = mind + maxd - c->distance;
85 fx32_32_t scale = log_clamped_scale_factor(min: mind, max: maxd, n);
86
87 return fx_mul(FX_ONE - wastage_scaled, b: scale);
88}
89
90static int cmp_wastage_desc(const void *a, const void *b) {
91 const struct elcm_candidate *ca = (const struct elcm_candidate *) a;
92 const struct elcm_candidate *cb = (const struct elcm_candidate *) b;
93
94 if (ca->wastage < cb->wastage)
95 return 1;
96
97 if (ca->wastage > cb->wastage)
98 return -1;
99
100 return 0;
101}
102
103static int cmp_score_asc(const void *a, const void *b) {
104 const struct elcm_candidate *ca = (const struct elcm_candidate *) a;
105 const struct elcm_candidate *cb = (const struct elcm_candidate *) b;
106
107 if (ca->score_value < cb->score_value)
108 return -1;
109
110 if (ca->score_value > cb->score_value)
111 return 1;
112
113 return 0;
114}
115
116static bool candidate_valid(struct elcm_candidate *cand) {
117 /* Check: Metadata bytes + bitmap bytes + object count *
118 * object size <= total memory for this candidate */
119 size_t objects = cand->obj_size * cand->obj_count;
120 size_t total_mem = cand->pages * PAGE_SIZE;
121 if ((objects + cand->metadata_bytes + cand->bitmap_bytes) > total_mem)
122 return false;
123
124 /* Now we "simulate" that slab */
125 size_t data_start = cand->metadata_bytes + cand->bitmap_bytes;
126 size_t aligned_start = ALIGN_UP(data_start, cand->obj_alignment);
127 size_t bytes_usable = cand->pages * PAGE_SIZE - aligned_start;
128 size_t obj_stride = ALIGN_UP(cand->obj_size, cand->obj_alignment);
129 return obj_stride * cand->obj_count <= bytes_usable;
130}
131
132static inline size_t bitmap_bytes_for(size_t obj_count, size_t bits_per_obj) {
133 size_t total_bits = obj_count * bits_per_obj;
134 return DIV_ROUND_UP(total_bits, sizeof(uint8_t) * 8);
135}
136
137static size_t get_aligned_obj_size(size_t obj_size, size_t align) {
138 return DIV_ROUND_UP(obj_size + align, align) * align;
139}
140
141static size_t max_objects_fit(size_t pages, size_t page_size,
142 size_t metadata_bytes,
143 size_t metadata_bits_per_obj, size_t obj_size,
144 size_t alignment) {
145 size_t total_bytes = pages * page_size;
146 size_t aligned_obj_size = get_aligned_obj_size(obj_size, align: alignment);
147
148 size_t low = 0;
149 size_t high = total_bytes / aligned_obj_size; /* no overhead */
150
151 while (low < high) {
152 size_t mid = low + (high - low + 1) / 2;
153 size_t bmap_bytes = bitmap_bytes_for(obj_count: mid, bits_per_obj: metadata_bits_per_obj);
154 size_t data_start = metadata_bytes + bmap_bytes;
155 size_t aligned_start = ALIGN_UP(data_start, alignment);
156
157 if (mid > (total_bytes - aligned_start) / aligned_obj_size)
158 high = mid - 1;
159 else
160 low = mid;
161 }
162 return low;
163}
164
165static size_t find_best(struct elcm_params *params) {
166 size_t obj_size = params->obj_size;
167 size_t alignment = params->obj_alignment ? params->obj_alignment : 1;
168 size_t metadata_bits_per_obj = params->metadata_bits_per_obj;
169 size_t page_size = PAGE_SIZE;
170 size_t metadata_size_bytes = params->metadata_size_bytes;
171 size_t metadata_bytes_per_page = params->metadata_bytes_per_page;
172 size_t aligned_obj_size = get_aligned_obj_size(obj_size, align: alignment);
173
174 for (size_t i = 1; i <= params->max_pages; i++) {
175 size_t mdata_bytes = metadata_size_bytes + metadata_bytes_per_page * i;
176
177 size_t obj_count =
178 max_objects_fit(pages: i, page_size, metadata_bytes: mdata_bytes, metadata_bits_per_obj,
179 obj_size, alignment);
180
181 if (obj_count == 0)
182 continue;
183
184 size_t bmap_bytes = bitmap_bytes_for(obj_count, bits_per_obj: metadata_bits_per_obj);
185 size_t data_start = mdata_bytes + bmap_bytes;
186 size_t aligned_start = ALIGN_UP(data_start, alignment);
187 size_t used_bytes = aligned_start + obj_count * aligned_obj_size;
188 size_t total_bytes = i * page_size;
189 size_t wasted = total_bytes - used_bytes;
190
191 if (wasted == 0)
192 return i;
193 }
194
195 return params->max_pages;
196}
197
198static struct elcm_candidate
199create_candidate_for_pages(struct elcm_params *params, size_t pages) {
200 size_t obj_size = params->obj_size;
201 size_t obj_alignment = params->obj_alignment ? params->obj_alignment : 1;
202 size_t metadata_bits_per_obj = params->metadata_bits_per_obj;
203 size_t page_size = PAGE_SIZE;
204 size_t metadata_size_bytes = params->metadata_size_bytes;
205 size_t metadata_bytes_per_page = params->metadata_bytes_per_page;
206 size_t aligned_obj_size = get_aligned_obj_size(obj_size, align: obj_alignment);
207
208 size_t mdata_bytes = metadata_size_bytes + metadata_bytes_per_page * pages;
209 size_t obj_count =
210 max_objects_fit(pages, page_size, metadata_bytes: mdata_bytes, metadata_bits_per_obj,
211 obj_size, alignment: obj_alignment);
212 size_t bmap_bytes = bitmap_bytes_for(obj_count, bits_per_obj: metadata_bits_per_obj);
213 size_t data_start = mdata_bytes + bmap_bytes;
214 size_t aligned_start = ALIGN_UP(data_start, obj_alignment);
215 size_t used_bytes = aligned_start + obj_count * aligned_obj_size;
216 size_t total_bytes = pages * page_size;
217 size_t wasted = total_bytes > used_bytes ? total_bytes - used_bytes : 0;
218 fx32_32_t wastage =
219 total_bytes ? fx_div(a: fx_from_int(x: wasted), b: fx_from_int(x: total_bytes)) : 0;
220
221 return (struct elcm_candidate){
222 .pages = pages,
223 .wasted = wasted,
224 .wastage = wastage,
225 .obj_count = obj_count,
226 .bitmap_bytes = bmap_bytes,
227 .metadata_bytes = mdata_bytes,
228 .obj_size = obj_size,
229 .obj_alignment = obj_alignment,
230 .distance = 0,
231 .score_value = 0,
232 };
233}
234
235enum err elcm(struct elcm_params *params) {
236 const struct elcm_candidate degenerate = {0};
237 params->out = degenerate;
238
239 size_t obj_size = params->obj_size;
240 size_t obj_alignment = params->obj_alignment ? params->obj_alignment : 1;
241 size_t metadata_bits_per_obj = params->metadata_bits_per_obj;
242 size_t page_size = PAGE_SIZE;
243 size_t metadata_size_bytes = params->metadata_size_bytes;
244 size_t max_pages = params->max_pages;
245 size_t max_wastage_pct = params->max_wastage_pct;
246 size_t metadata_bytes_per_page = params->metadata_bytes_per_page;
247 bool bias_towards_pow2 = params->bias_towards_pow2;
248
249 enforce_precond(obj_size > 0);
250 enforce_precond(page_size > 0);
251 enforce_precond(obj_alignment <= page_size,
252 "alignment cannot exceed page size");
253 enforce_precond(max_wastage_pct <= 100,
254 "max wastage percentage must be 0-100");
255
256 size_t best_possible = find_best(params);
257
258 if (best_possible == 1) {
259 params->out = create_candidate_for_pages(params, pages: 1);
260 return ERR_OK;
261 }
262
263 if (max_pages == 0 || max_pages > best_possible)
264 max_pages = best_possible;
265
266 size_t size = max_pages * sizeof(struct elcm_candidate);
267 struct elcm_candidate *candidates =
268 params->alloc_fn ? params->alloc_fn(size) : nofail_valloc(size);
269
270 if (!candidates)
271 return ERR_NO_MEM;
272
273 size_t cand_count = 0, max_pages_seen = 0, min_pages_seen = SIZE_MAX;
274 fx32_32_t max_wastage = fx_div(a: fx_from_int(x: max_wastage_pct), FX(100.0));
275 size_t aligned_obj_size = get_aligned_obj_size(obj_size, align: obj_alignment);
276
277 for (size_t i = 1; i <= max_pages; i++) {
278 if (cc_unlikely(i == best_possible))
279 break;
280
281 size_t mdata_bytes = metadata_size_bytes + metadata_bytes_per_page * i;
282
283 size_t obj_count =
284 max_objects_fit(pages: i, page_size, metadata_bytes: mdata_bytes, metadata_bits_per_obj,
285 obj_size, alignment: obj_alignment);
286
287 if (obj_count == 0)
288 continue;
289
290 size_t bmap_bytes = bitmap_bytes_for(obj_count, bits_per_obj: metadata_bits_per_obj);
291 size_t data_start = mdata_bytes + bmap_bytes;
292 size_t aligned_start = ALIGN_UP(data_start, obj_alignment);
293 size_t used_bytes = aligned_start + obj_count * aligned_obj_size;
294 size_t total_bytes = i * page_size;
295 size_t wasted = total_bytes - used_bytes;
296
297 fx32_32_t wastage =
298 fx_div(a: fx_from_int(x: wasted), b: fx_from_int(x: total_bytes));
299
300 if (wastage < max_wastage) {
301 struct elcm_candidate cand = {
302 .pages = i,
303 .wasted = wasted,
304 .wastage = wastage,
305 .obj_count = obj_count,
306 .bitmap_bytes = bmap_bytes,
307 .metadata_bytes = mdata_bytes,
308 .obj_size = obj_size,
309 .obj_alignment = obj_alignment,
310 .distance = 0,
311 .score_value = 0,
312 };
313
314 if (i > max_pages_seen)
315 max_pages_seen = i;
316
317 if (i < min_pages_seen)
318 min_pages_seen = i;
319
320 enforce(candidate_valid(&cand));
321 enforce(used_bytes <= total_bytes);
322 candidates[cand_count++] = cand;
323 }
324 }
325
326 if (cand_count == 0) {
327 params->free_fn ? params->free_fn(candidates, size) : vfree(candidates);
328 params->out = create_candidate_for_pages(params, pages: best_possible);
329 return ERR_OK;
330 }
331
332 if (cand_count == 1) {
333 struct elcm_candidate single = candidates[0];
334 params->free_fn ? params->free_fn(candidates, size) : vfree(candidates);
335 params->out = single;
336 return ERR_OK;
337 }
338
339 heapsort(vbase: candidates, nmemb: cand_count, size: sizeof(struct elcm_candidate),
340 compar: cmp_wastage_desc);
341
342 size_t max_distance = 0, min_distance = SIZE_MAX;
343 for (size_t i = 0; i < cand_count; i++) {
344 struct elcm_candidate *cand = &candidates[i];
345 size_t d_from_perfect = best_possible - cand->pages;
346 size_t d_from_highest = max_pages_seen - cand->pages;
347
348 size_t dist = d_from_perfect + d_from_highest;
349 cand->distance = dist;
350
351 if (dist > max_distance)
352 max_distance = dist;
353
354 if (dist < min_distance)
355 min_distance = dist;
356 }
357
358 for (size_t i = 0; i < cand_count; i++) {
359 fx32_32_t s = candidate_score(c: &candidates[i], mind: min_distance,
360 maxd: max_distance, max_wastage);
361 if (bias_towards_pow2) {
362 fx32_32_t prox = pow2_proximity_scaled(
363 min: min_pages_seen, max: max_pages_seen, n: candidates[i].pages);
364
365 fx32_32_t score_part = fx_div(a: s, FX(2.0));
366 fx32_32_t prox_part = fx_div(a: fx_mul(a: prox, b: s), FX(2.0));
367 candidates[i].score_value = score_part + prox_part;
368 } else {
369 candidates[i].score_value = s;
370 }
371 }
372
373 heapsort(vbase: candidates, nmemb: cand_count, size: sizeof(struct elcm_candidate),
374 compar: cmp_score_asc);
375
376 fx32_32_t best_score = candidates[cand_count - 1].score_value;
377 struct elcm_candidate best = candidates[cand_count - 1];
378
379 for (size_t i = 0; i < cand_count; i++) {
380 if (candidates[i].score_value == best_score &&
381 candidates[i].wasted < best.wasted) {
382 best = candidates[i];
383 }
384 }
385
386 params->free_fn ? params->free_fn(candidates, size) : vfree(candidates);
387 params->out = best;
388 return ERR_OK;
389}
390