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