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