1#include <enforce.h>
2#include <mem/domain.h>
3#include <mem/pmm.h>
4#include <mem/vmm.h>
5#include <smp/domain.h>
6
7#include "internal.h"
8#include "mem/buddy/internal.h"
9
10static inline bool domain_free_queue_available(struct domain_free_queue *fq,
11 struct domain_buddy *domain) {
12 return atomic_load(&fq->num_elements) > domain->core_count;
13}
14
15static inline size_t domain_freequeue_flush_quota(struct domain_free_queue *fq,
16 struct domain_buddy *domain) {
17 size_t quota = atomic_load(&fq->num_elements) / domain->core_count;
18 if (quota == 0)
19 quota = 1;
20
21 return quota;
22}
23
24static void flush_freequeue_into_local_arena(struct domain_buddy *domain,
25 struct domain_free_queue *fq,
26 size_t quota) {
27 struct domain_arena *local_arena = domain_arena_on_this_core();
28
29 for (size_t i = 0; i < quota; i++) {
30 paddr_t addr = 0;
31 size_t page_count = 0;
32
33 if (!domain_free_queue_dequeue(fq, addr_out: &addr, pages_out: &page_count))
34 break; /* queue drained */
35
36 /* arenas only store single pages */
37 if (page_count > 1) {
38 free_from_buddy_internal(target: domain, address: addr, page_count);
39 continue;
40 }
41
42 struct buddy_page *bp = buddy_page_for_addr(address: addr);
43
44 if (!domain_arena_push(arena: local_arena, page: bp)) {
45 /* arena is full, fall back */
46 free_from_buddy_internal(target: domain, address: addr, page_count);
47 }
48 }
49}
50
51static paddr_t alloc_from_buddy_internal(struct domain_buddy *this,
52 size_t pages) {
53 enum irql irql = spin_lock(&this->lock);
54
55 paddr_t ret = buddy_alloc_pages(free_area: this->free_area, count: pages);
56
57 if (ret)
58 domain_stat_alloc(d: this, /*remote*/ false, /*interleaved*/ false);
59 else
60 domain_stat_failed_alloc(d: this);
61
62 if (ret)
63 atomic_fetch_add(&this->pages_used, pages);
64
65 spin_unlock(&this->lock, irql);
66 return ret;
67}
68
69static paddr_t try_alloc_from_remote_arenas(struct domain_buddy *owner,
70 size_t pages, bool remote) {
71 if (pages > 1)
72 return 0x0; /* Arenas only cache single pages */
73
74 struct domain_arena *try_from;
75 domain_for_each_arena(try_from, owner) {
76 struct buddy_page *bp = domain_arena_pop(arena: try_from);
77 if (bp) {
78 struct domain_buddy *local = domain_buddy_on_this_core();
79 domain_stat_alloc(d: local, /*remote*/ remote, /*interleaved*/ false);
80 return buddy_page_get_paddr(bp);
81 }
82 }
83
84 return 0x0; /* Nothing */
85}
86
87static paddr_t alloc_from_remote_domain(struct domain_buddy *remote,
88 size_t pages) {
89 paddr_t ret = try_alloc_from_remote_arenas(owner: remote, pages, /*remote*/ true);
90 if (ret)
91 return ret;
92
93 ret = alloc_from_buddy_internal(this: remote, pages);
94 if (ret) {
95 struct domain_buddy *local = domain_buddy_on_this_core();
96 domain_stat_alloc(d: local, /*remote*/ true, /*interleaved*/ false);
97 } else {
98 struct domain_buddy *local = domain_buddy_on_this_core();
99 domain_stat_failed_alloc(d: local);
100 }
101
102 return ret;
103}
104
105static paddr_t try_alloc_from_free_queue(struct domain_free_queue *fq,
106 struct domain_buddy *this,
107 struct domain_arena *this_arena) {
108 if (domain_free_queue_available(fq, domain: this)) {
109 size_t quota = domain_freequeue_flush_quota(fq, domain: this);
110
111 flush_freequeue_into_local_arena(domain: this, fq, quota);
112
113 /* retry after flush */
114 struct buddy_page *bp = domain_arena_pop(arena: this_arena);
115 if (bp) {
116 domain_stat_alloc(d: this, /*remote*/ false, /*interleaved*/ false);
117 return buddy_page_get_paddr(bp);
118 }
119 }
120
121 return 0x0;
122}
123
124static paddr_t try_alloc_from_arenas(size_t pages) {
125 if (pages > 1) /* Can't do it, arenas only cache single-pages */
126 return 0x0;
127
128 struct domain_arena *this_arena = domain_arena_on_this_core();
129 struct buddy_page *bp = domain_arena_pop(arena: this_arena);
130
131 if (bp) {
132 struct domain_buddy *local = domain_buddy_on_this_core();
133 domain_stat_alloc(d: local, /*remote*/ false, /*interleaved*/ false);
134 return buddy_page_get_paddr(bp);
135 }
136
137 struct domain_buddy *this = domain_buddy_on_this_core();
138 struct domain_free_queue *fq = domain_free_queue_on_this_core();
139
140 paddr_t ret = try_alloc_from_free_queue(fq, this, this_arena);
141 if (ret)
142 return ret;
143
144 return try_alloc_from_remote_arenas(owner: this, pages, /*remote*/ false);
145}
146
147static inline paddr_t do_alloc_interleaved_local(struct domain_buddy *local,
148 size_t pages) {
149 paddr_t ret = try_alloc_from_arenas(pages);
150 if (ret)
151 return ret;
152
153 return alloc_from_buddy_internal(this: local, pages);
154}
155
156static inline paddr_t do_alloc_interleaved(struct domain_buddy *target,
157 struct domain_buddy *local,
158 size_t pages) {
159 if (target == local)
160 return do_alloc_interleaved_local(local: target, pages);
161
162 /* This is not the local arena */
163 return alloc_from_remote_domain(remote: target, pages);
164}
165
166static paddr_t alloc_interleaved(size_t pages) {
167 struct domain_buddy *local = domain_buddy_on_this_core();
168 struct domain_zonelist *zl = &local->zonelist;
169
170 size_t *rr_idx = domain_rr_on_this_core();
171
172 size_t idx = *rr_idx % zl->count;
173 struct domain_zonelist_entry *entry = &zl->entries[idx];
174 struct domain_buddy *target = entry->domain;
175
176 paddr_t ret = 0;
177
178 if (atomic_load_rlx(&target->total_pages) -
179 atomic_load_rlx(&target->pages_used) >=
180 pages)
181 ret = do_alloc_interleaved(target, local, pages);
182
183 *rr_idx = (idx + 1) % zl->count;
184
185 if (ret)
186 domain_stat_mark_interleaved(d: local);
187 else
188 domain_stat_failed_alloc(d: local);
189
190 return ret;
191}
192
193static inline paddr_t alloc_from_local_buddy(size_t pages) {
194 struct domain_buddy *local = domain_buddy_on_this_core();
195 return alloc_from_buddy_internal(this: local, pages);
196}
197
198static paddr_t zonelist_alloc_fallback(struct domain_zonelist *zl,
199 struct domain_buddy *local,
200 struct domain_buddy *best,
201 size_t max_scan, size_t pages) {
202 /* Walk other buddies in zonelist */
203 for (size_t i = 0; i < max_scan; i++) {
204 struct domain_zonelist_entry *entry = &zl->entries[i];
205 struct domain_buddy *candidate = entry->domain;
206 enforce(candidate);
207
208 if (candidate == best)
209 continue;
210
211 paddr_t ret = alloc_from_remote_domain(remote: candidate, pages);
212 if (ret)
213 return ret;
214 }
215
216 domain_stat_failed_alloc(d: local);
217 return 0x0;
218}
219
220static size_t derive_max_scan_from_zonelist(struct domain_zonelist *zl,
221 uint16_t locality_degree) {
222 size_t max_scan = ((locality_degree + 1) * zl->count / ALLOC_LOCALITY_MAX);
223 if (max_scan > zl->count)
224 max_scan = zl->count;
225
226 if (max_scan == 0)
227 max_scan = 1;
228
229 return max_scan;
230}
231
232struct domain *domain_alloc_pick_best_domain(struct domain *local, size_t pages,
233 size_t max_scan,
234 bool flexible_locality) {
235 struct domain_buddy *best = NULL;
236 int32_t best_score = INT32_MAX;
237 struct domain_buddy *buddy = local->domain_buddy;
238 struct domain_zonelist *zl = &buddy->zonelist;
239
240 for (size_t i = 0; i < max_scan; i++) {
241 struct domain_zonelist_entry *ent = &zl->entries[i];
242 struct domain_buddy *candidate = ent->domain;
243
244 size_t free_pages = atomic_load_rlx(&candidate->total_pages) -
245 atomic_load_rlx(&candidate->pages_used);
246 if (free_pages < pages)
247 continue;
248
249 int32_t dist_weight =
250 flexible_locality ? DISTANCE_WEIGHT / 4 : DISTANCE_WEIGHT;
251
252 int32_t score =
253 (ent->distance * dist_weight) - (free_pages * FREE_PAGES_WEIGHT);
254
255 if (!best || score < best_score) {
256 best = candidate;
257 best_score = score;
258 }
259 }
260
261 enforce(best);
262 return best->domain;
263}
264
265static paddr_t alloc_with_locality(size_t pages, bool flexible_locality,
266 uint16_t locality_degree) {
267 struct domain_buddy *local = domain_buddy_on_this_core();
268 struct domain_zonelist *zl = &local->zonelist;
269
270 size_t max_scan = derive_max_scan_from_zonelist(zl, locality_degree);
271 if (flexible_locality)
272 max_scan = zl->count;
273
274 /* Just pick the best domain */
275 struct domain_buddy *best = NULL;
276 int32_t best_score = INT32_MAX;
277
278 for (size_t i = 0; i < max_scan; i++) {
279 struct domain_zonelist_entry *ent = &zl->entries[i];
280 struct domain_buddy *candidate = ent->domain;
281
282 size_t free_pages = atomic_load_rlx(&candidate->total_pages) -
283 atomic_load_rlx(&candidate->pages_used);
284 if (free_pages < pages)
285 continue;
286
287 int32_t dist_weight =
288 flexible_locality ? DISTANCE_WEIGHT / 4 : DISTANCE_WEIGHT;
289
290 int32_t score =
291 (ent->distance * dist_weight) - (free_pages * FREE_PAGES_WEIGHT);
292
293 if (!best || score < best_score) {
294 best = candidate;
295 best_score = score;
296 }
297 }
298
299 if (!best)
300 unreachable("domain has no zonelist");
301
302 /* Try best first */
303 paddr_t ret = alloc_from_remote_domain(remote: best, pages);
304 if (ret)
305 return ret;
306
307 if (flexible_locality)
308 ret = zonelist_alloc_fallback(zl, local, best, max_scan, pages);
309
310 return ret;
311}
312
313paddr_t domain_alloc(size_t pages, enum alloc_flags flags) {
314 enforce_precond(pages != 0);
315 /* pin our core and disable preemption */
316 enum irql irql = irql_raise(new_level: IRQL_DISPATCH_LEVEL);
317
318 paddr_t ret = 0x0;
319
320 /* We only care about INTERLEAVED at the buddy allocator level */
321 if (ALLOC_FLAG_CLASS(flags) == ALLOC_FLAG_CLASS_INTERLEAVED) {
322 ret = alloc_interleaved(pages);
323 goto done;
324 }
325
326 /* Fastpath: Get it from an arena or the freequeue */
327 ret = try_alloc_from_arenas(pages);
328 if (ret)
329 goto done;
330
331 /* We don't care about any other flags in the domain buddy allocator */
332 uint16_t locality_degree = ALLOC_LOCALITY_FROM_FLAGS(flags);
333 bool flexible_locality =
334 ALLOC_FLAG_TEST(flags, ALLOC_FLAG_FLEXIBLE_LOCALITY) ||
335 locality_degree == ALLOC_LOCALITY_MIN || global.numa_node_count == 1;
336
337 /* No other options. Allocate from the local buddy. */
338 if (locality_degree == ALLOC_LOCALITY_MAX) {
339 ret = alloc_from_local_buddy(pages);
340 goto done;
341 }
342
343 ret = alloc_with_locality(pages, flexible_locality, locality_degree);
344
345done:
346 irql_lower(old_level: irql);
347 return ret;
348}
349
350paddr_t domain_alloc_from_domain(struct domain *cd, size_t pages) {
351 enum irql irql = irql_raise(new_level: IRQL_DISPATCH_LEVEL);
352 paddr_t ret = 0x0;
353 if ((ret = try_alloc_from_arenas(pages)))
354 goto out;
355
356 ret = alloc_from_remote_domain(remote: cd->domain_buddy, pages);
357
358out:
359 irql_lower(old_level: irql);
360 return ret;
361}
362
363struct domain *domain_for_addr(paddr_t addr) {
364 struct domain_buddy *dbd = domain_buddy_for_addr(addr);
365 if (!dbd)
366 return NULL;
367
368 return dbd->domain;
369}
370