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