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