1#include <math/align.h>
2#include <math/bit.h>
3#include <math/min_max.h>
4#include <math/sort.h>
5#include <mem/alloc.h>
6#include <mem/buddy.h>
7#include <mem/domain.h>
8#include <mem/nofail.h>
9#include <mem/numa.h>
10#include <mem/page_alloc.h>
11#include <mem/pmm.h>
12#include <mem/vmm.h>
13#include <sch/sched.h>
14#include <smp/domain.h>
15#include <string.h>
16#include <thread/thread.h>
17
18#include "internal.h"
19#include "mem/buddy/internal.h"
20
21static int compare_zonelist_entries(const void *a, const void *b) {
22 const struct domain_zonelist_entry *da = a;
23 const struct domain_zonelist_entry *db = b;
24
25 if (da->distance != db->distance)
26 return da->distance - db->distance;
27
28 if (da->free_pages != db->free_pages)
29 return (db->free_pages > da->free_pages) ? -1 : 1;
30
31 return 0;
32}
33
34static void domain_build_zonelist(struct domain_buddy *dom) {
35 dom->zonelist.count = global.domain_count;
36
37 for (size_t i = 0; i < global.domain_count; i++) {
38 dom->zonelist.entries[i].domain = &global.domain_buddies[i];
39 if (global.numa_node_count > 1)
40 dom->zonelist.entries[i].distance =
41 global.numa_nodes[dom - global.domain_buddies].distance[i];
42
43 dom->zonelist.entries[i].free_pages =
44 atomic_load_rlx(&global.domain_buddies[i].total_pages) -
45 atomic_load_rlx(&global.domain_buddies[i].pages_used);
46 }
47
48 heapsort(vbase: dom->zonelist.entries, nmemb: dom->zonelist.count,
49 size: sizeof(struct domain_zonelist_entry), compar: compare_zonelist_entries);
50}
51
52static void domain_buddy_track_pages(struct domain_buddy *dom) {
53 size_t total_pages = dom->length / PAGE_SIZE;
54 size_t free_pages = 0;
55
56 for (size_t order = 0; order < BUDDY_MAX_ORDER; order++)
57 free_pages += dom->free_area[order].nr_free << order;
58
59 atomic_store_rlx(&dom->total_pages, total_pages);
60 atomic_store_rlx(&dom->pages_used, total_pages - free_pages);
61}
62
63static void buddy_add_block_to_global(size_t start_pfn, int order) {
64 struct buddy_page *page = buddy_page_for_pfn(pfn: start_pfn);
65
66 buddy_page_tag(page);
67 buddy_page_set_next_pfn(bp: page, pfn: 0);
68 buddy_page_set_order(bp: page, order: (uint64_t) order);
69 buddy_page_set_free(bp: page, true);
70
71 buddy_add_to_free_area(page, area: &global.buddy_free_area[order]);
72}
73
74/* Place block removed from global free area. Blocks fully outside the domain
75 * get handed back to the global area, fully inside ones are put in the domain
76 * free area, and ones that cross domains are split and distributed */
77static void domain_distribute_block(struct domain_buddy *dom, size_t start_pfn,
78 int order, size_t domain_start,
79 size_t domain_end) {
80 size_t block_size = BIT(order);
81 size_t block_end = start_pfn + block_size;
82
83 if (block_end <= domain_start || start_pfn >= domain_end) {
84 buddy_add_block_to_global(start_pfn, order);
85 return;
86 }
87
88 if (start_pfn >= domain_start && block_end <= domain_end) {
89 size_t idx = start_pfn - dom->start / PAGE_SIZE;
90 struct buddy_page *page = &dom->buddy[idx];
91 buddy_page_tag(page);
92 buddy_page_set_next_pfn(bp: page, pfn: 0);
93 buddy_page_set_order(bp: page, order);
94 buddy_page_set_free(bp: page, true);
95 buddy_add_to_free_area(page, area: &dom->free_area[order]);
96 return;
97 }
98
99 int half_order = order - 1;
100 size_t half_size = BIT(half_order);
101
102 domain_distribute_block(dom, start_pfn, order: half_order, domain_start,
103 domain_end);
104 domain_distribute_block(dom, start_pfn: start_pfn + half_size, order: half_order,
105 domain_start, domain_end);
106}
107
108static void domain_claim_global_blocks(struct domain_buddy *dom,
109 size_t dom_start, size_t dom_end) {
110 for (int order = BUDDY_MAX_ORDER - 1; order >= 0; order--) {
111 struct buddy_free_area *fa = &global.buddy_free_area[order];
112
113 struct buddy_page *pending = NULL;
114 struct buddy_page *page;
115 while ((page = buddy_remove_from_free_area(area: fa))) {
116 buddy_page_set_next(bp: page, next: pending);
117 pending = page;
118 }
119
120 while (pending) {
121 struct buddy_page *next = buddy_page_get_next(bp: pending);
122 buddy_page_set_next_pfn(bp: pending, pfn: 0);
123
124 domain_distribute_block(dom, start_pfn: buddy_page_get_pfn(bp: pending), order,
125 domain_start: dom_start, domain_end: dom_end);
126
127 pending = next;
128 }
129 }
130}
131
132static void domain_buddy_init(struct domain_buddy *dom) {
133 for (int i = 0; i < BUDDY_MAX_ORDER; i++) {
134 dom->free_area[i].head = NULL;
135 dom->free_area[i].tail = NULL;
136 dom->free_area[i].nr_free = 0;
137 }
138
139 size_t dom_start = dom->start / PAGE_SIZE;
140 size_t dom_end = dom->end / PAGE_SIZE;
141
142 domain_claim_global_blocks(dom, dom_start, dom_end);
143}
144
145static void *alloc_up(size_t size) {
146 return nofail(valloc_pages(PAGES_NEEDED_FOR(size), ALLOC_FLAGS_ZERO));
147}
148
149static void domain_structs_init(struct domain_buddy *dom, size_t arena_capacity,
150 size_t fq_capacity,
151 struct domain *core_domain) {
152 dom->domain = core_domain;
153 dom->free_area = alloc_up(size: sizeof(struct buddy_free_area) * BUDDY_MAX_ORDER);
154
155 dom->zonelist.entries =
156 alloc_up(size: sizeof(struct domain_zonelist_entry) * global.domain_count);
157
158 dom->arenas = alloc_up(size: sizeof(struct domain_arena *) * dom->core_count);
159
160 core_domain->domain_buddy = dom;
161 for (size_t i = 0; i < dom->core_count; i++) {
162 dom->arenas[i] = alloc_up(size: sizeof(struct domain_arena));
163
164 struct domain_arena *this = dom->arenas[i];
165 this->pages = alloc_up(size: sizeof(struct page *) * arena_capacity);
166
167 this->head = 0;
168 this->tail = 0;
169 this->capacity = arena_capacity;
170 spinlock_init(&this->lock);
171
172 /* NOTE: Special case because CPU0 will call allocations
173 * later on after this is initialized and needs to be
174 * able to figure out what domain arena it has */
175 if (core_domain->id == 0 && i == 0)
176 global.cores[i]->domain_arena = this;
177 }
178
179 dom->free_queue = alloc_up(size: sizeof(struct domain_free_queue));
180
181 size_t fq_size = sizeof(*dom->free_queue->queue) * fq_capacity;
182 dom->free_queue->queue = alloc_up(size: fq_size);
183
184 dom->free_queue->head = 0;
185 dom->free_queue->tail = 0;
186 dom->free_queue->capacity = fq_capacity;
187 spinlock_init(&dom->free_queue->lock);
188 spinlock_init(&dom->lock);
189}
190
191static void init_after_smp(void) {
192 for (size_t i = 0; i < global.domain_count; i++) {
193 struct domain_buddy *dom = global.domains[i]->domain_buddy;
194 struct domain *core_domain = global.domains[i];
195 dom->cores = core_domain->cores;
196 for (size_t j = 0; j < dom->core_count; j++)
197 dom->cores[j]->domain_arena = dom->arenas[j];
198 }
199}
200
201static size_t compute_arena_max(size_t domain_total_pages) {
202 size_t scaled = (domain_total_pages * ARENA_SCALE_PERMILLE) / 1000;
203 return MIN(scaled, MAX_ARENA_PAGES);
204}
205
206static size_t compute_freequeue_max(size_t system_total_pages) {
207 size_t scaled = (system_total_pages * FREEQUEUE_SCALE_PERMILLE) / 1000;
208 return MIN(scaled, MAX_FREEQUEUE_PAGES);
209}
210
211static void domain_spawn(struct domain_buddy *domain) {
212 domain->worker.thread =
213 thread_create(("domain_flush_thread%zu", domain->domain->id),
214 domain_flush_thread, .pinned = true);
215 struct thread *worker = domain->worker.thread;
216 uint64_t id = domain->domain->id;
217
218 worker->curr_core = id;
219 thread_set_background(t: worker);
220 thread_enqueue_on_core(t: worker, core_id: id);
221}
222
223static inline uint64_t pages_to_bytes(size_t pages) {
224 return (uint64_t) pages * PAGE_SIZE;
225}
226
227static void late_init_from_numa(size_t domain_count) {
228 for (size_t i = 0; i < domain_count; i++) {
229 struct numa_node *node = &global.numa_nodes[i % global.numa_node_count];
230 struct domain *cd = global.domains[i];
231
232 global.domain_buddies[i].start = node->mem_base; /* bytes */
233 global.domain_buddies[i].end =
234 node->mem_base + node->mem_size; /* bytes */
235 global.domain_buddies[i].length = node->mem_size; /* bytes */
236 global.domain_buddies[i].core_count = cd->num_cores;
237
238 cd->domain_buddy = &global.domain_buddies[i];
239
240 /* Slice of global buddy_page_array corresponding to this PFN range */
241 size_t page_offset = node->mem_base / PAGE_SIZE; /* PFN index */
242 global.domain_buddies[i].buddy =
243 (struct buddy_page *) &global.page_array[page_offset];
244 }
245}
246
247/* No NUMA: split last_pfn evenly across domains.
248 * Keep dom->start/dom->end in bytes to match NUMA path. */
249static void late_init_non_numa(size_t domain_count) {
250 size_t pages_per_domain = global.last_pfn / domain_count;
251 size_t remainder_pages = global.last_pfn % domain_count;
252
253 size_t page_cursor = 0; /* PFN cursor (pages) */
254
255 for (size_t i = 0; i < domain_count; i++) {
256 size_t this_pages = pages_per_domain;
257 if (i == domain_count - 1)
258 this_pages += remainder_pages;
259
260 struct domain *cd = global.domains[i];
261
262 uint64_t domain_start_bytes = pages_to_bytes(pages: page_cursor); /* bytes */
263
264 uint64_t domain_length_bytes = pages_to_bytes(pages: this_pages); /* bytes */
265
266 global.domain_buddies[i].start = domain_start_bytes; /* bytes */
267 global.domain_buddies[i].end =
268 domain_start_bytes + domain_length_bytes; /* bytes */
269 global.domain_buddies[i].length = domain_length_bytes; /* bytes */
270 global.domain_buddies[i].core_count = cd->num_cores;
271
272 global.domain_buddies[i].buddy =
273 (struct buddy_page *) &global.page_array[page_cursor];
274
275 cd->domain_buddy = &global.domain_buddies[i];
276
277 page_cursor += this_pages;
278 }
279}
280
281void domain_buddies_init(void) {
282 size_t domain_count = global.domain_count;
283 global.domain_buddies =
284 nofail_vnews(global.domain_buddies, domain_count, ALLOC_ZERO);
285
286 if (global.numa_node_count > 1) {
287 late_init_from_numa(domain_count);
288 } else {
289 late_init_non_numa(domain_count);
290 }
291
292 size_t freequeue_size = compute_freequeue_max(system_total_pages: global.total_pages);
293
294 for (size_t i = 0; i < domain_count; i++) {
295 struct domain *d = global.domains[i];
296 struct domain_buddy *dbd = &global.domain_buddies[i];
297 size_t arena_size = compute_arena_max(domain_total_pages: dbd->end - dbd->start);
298 domain_structs_init(dom: dbd, arena_capacity: arena_size, fq_capacity: freequeue_size, core_domain: d);
299 }
300
301 for (size_t i = 0; i < domain_count; i++) {
302 struct domain_buddy *dbd = &global.domain_buddies[i];
303 domain_buddy_init(dom: dbd);
304 semaphore_init(s: &dbd->worker.sema, value: 0, SEMAPHORE_INIT_NORMAL);
305 dbd->worker.domain = dbd;
306 atomic_store_rlx(&dbd->worker.enqueued, false);
307 dbd->worker.stop = false;
308 domain_buddy_track_pages(dom: dbd);
309 domain_build_zonelist(dom: dbd);
310 }
311}
312
313void domain_buddies_init_after_smp(void) {
314 init_after_smp();
315}
316
317void domain_buddies_init_late(void) {
318 for (size_t i = 0; i < global.domain_count; i++)
319 domain_spawn(domain: &global.domain_buddies[i]);
320}
321
322void domain_buddy_dump(void) {
323 for (size_t i = 0; i < global.domain_count; i++) {
324 struct domain_buddy *dom = &global.domain_buddies[i];
325 struct domain_buddy_stats *stat = &dom->stats;
326 printf(format: "Domain %zu stats: %zu allocs, %zu failed, %zu interleaved, %zu "
327 "remote, %zu frees, %zu pages used, %zu total pages\n",
328 i, atomic_load_rlx(&stat->alloc_count),
329 atomic_load_rlx(&stat->failed_alloc_count),
330 atomic_load_rlx(&stat->interleaved_alloc_count),
331 atomic_load_rlx(&stat->remote_alloc_count),
332 atomic_load_rlx(&stat->free_count),
333 atomic_load_rlx(&dom->pages_used),
334 atomic_load_rlx(&dom->total_pages));
335 }
336}
337
338static void move_buddy(struct domain_buddy *buddy) {
339 domain_id_t domain = buddy->domain->id;
340 movealloc(domain, buddy->free_queue);
341 movealloc(domain, buddy->free_area);
342 movealloc(domain, buddy->free_queue->queue);
343 movealloc(domain, buddy->zonelist.entries);
344 movealloc(domain, buddy->arenas);
345 for (size_t i = 0; i < buddy->core_count; i++) {
346 movealloc(domain, buddy->arenas[i]);
347 movealloc(domain, buddy->arenas[i]->pages);
348 }
349}
350
351static void domain_buddy_movealloc(void *a, void *b) {
352 cc_ignore(a, b);
353 for (size_t i = 0; i < global.domain_count; i++)
354 move_buddy(buddy: global.domains[i]->domain_buddy);
355}
356
357MOVEALLOC_REGISTER_CALL(domain_move, domain_buddy_movealloc, /*a=*/NULL,
358 /*b=*/NULL);
359