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