1#include <asm.h>
2#include <atomic.h>
3#include <console/printf.h>
4#include <enforce.h>
5#include <global.h>
6#include <irq/idt.h>
7#include <limine.h>
8#include <math/align.h>
9#include <math/bit.h>
10#include <math/min_max.h>
11#include <math/sort.h>
12#include <mem/alloc.h>
13#include <mem/nofail.h>
14#include <mem/numa.h>
15#include <smp/core.h>
16#include <smp/domain.h>
17#include <smp/smp.h>
18#include <smp/topology.h>
19#include <sync/spinlock.h>
20#include <thread/thread.h>
21
22static struct topology_node *smt_nodes;
23static struct topology_node *core_nodes;
24static struct topology_node *numa_nodes;
25static struct topology_node *package_nodes;
26static struct topology_node *llc_nodes;
27static struct topology_node machine_node;
28
29#define BOLD_STR(str_) ANSI_BOLD str_ ANSI_RESET
30
31static void cpu_mask_print(const struct cpu_mask *m) {
32#if CPU_MASK_WORDS == 1
33 printf(BOLD_STR("0x%llx"), (unsigned long long) m->bits[0]);
34#else
35 for (size_t i = 0; i < CPU_MASK_WORDS; i++)
36 printf(BOLD_STR("%016llx"),
37 (unsigned long long) m->bits[CPU_MASK_WORDS - 1 - i]);
38#endif
39}
40
41#define TOPO_MAKE_STR(color_, str_) (color_ str_ ANSI_RESET)
42
43static const char *topo_node_str[TOPOLOGY_LEVEL_MAX] = {
44 [TOPOLOGY_LEVEL_SMT] = TOPO_MAKE_STR(ANSI_MAGENTA, "SMT"),
45 [TOPOLOGY_LEVEL_CORE] = TOPO_MAKE_STR(ANSI_BLUE, "CORE"),
46 [TOPOLOGY_LEVEL_LLC] = TOPO_MAKE_STR(ANSI_CYAN, "LLC"),
47 [TOPOLOGY_LEVEL_PACKAGE] = TOPO_MAKE_STR(ANSI_GREEN, "PACKAGE"),
48 [TOPOLOGY_LEVEL_NUMA] = TOPO_MAKE_STR(ANSI_YELLOW, "NUMA NODE"),
49 [TOPOLOGY_LEVEL_MACHINE] = TOPO_MAKE_STR(ANSI_RED, "MACHINE"),
50};
51
52const char *topology_level_name(enum topology_level l) {
53 return topo_node_str[l];
54}
55
56static bool topology_is_child(const struct topology_node *node,
57 const struct topology_node *child) {
58 /* a NUMA node can span LLCs but has one parent_node */
59 if (node->level == TOPOLOGY_LEVEL_LLC)
60 return cpu_mask_intersects(a: &node->cpus, b: &child->cpus);
61
62 return child->parent_node == node;
63}
64
65static void print_topology_node(struct topology_node *node, int depth,
66 const struct cpu_mask *scope) {
67 for (int i = 0; i < depth; i++)
68 printf(format: " ");
69
70 const char *level_str = topo_node_str[node->level];
71
72 printf(format: "[%s] ID = " ANSI_BOLD "%lu" ANSI_RESET ", CPUs = ", level_str,
73 node->id);
74 cpu_mask_print(m: &node->cpus);
75 printf(format: "\n");
76
77 enum topology_level child_level;
78 switch (node->level) {
79 case TOPOLOGY_LEVEL_MACHINE: child_level = TOPOLOGY_LEVEL_PACKAGE; break;
80 case TOPOLOGY_LEVEL_PACKAGE: child_level = TOPOLOGY_LEVEL_LLC; break;
81 case TOPOLOGY_LEVEL_LLC: child_level = TOPOLOGY_LEVEL_NUMA; break;
82 case TOPOLOGY_LEVEL_NUMA: child_level = TOPOLOGY_LEVEL_CORE; break;
83 case TOPOLOGY_LEVEL_CORE: child_level = TOPOLOGY_LEVEL_SMT; break;
84 default: return;
85 }
86
87 if (node->level != TOPOLOGY_LEVEL_NUMA)
88 scope = &node->cpus;
89
90 struct topology_node *children = global.topology.level[child_level];
91 for (size_t i = 0; i < global.topology.count[child_level]; i++) {
92 struct topology_node *child = &children[i];
93 if (topology_is_child(node, child) &&
94 cpu_mask_intersects(a: &child->cpus, b: scope))
95 print_topology_node(node: child, depth: depth + 1, scope);
96 }
97}
98
99static void topology_dump(void) {
100 log_msg(LOG_INFO, "Processor topology:");
101 print_topology_node(node: &machine_node, depth: 0, scope: &machine_node.cpus);
102}
103
104static size_t build_smt_nodes(size_t cpu_count, size_t core_count) {
105 smt_nodes = nofail_vnews(smt_nodes, cpu_count, ALLOC_ZERO);
106
107 for (size_t i = 0; i < cpu_count; i++) {
108 struct core *c = global.cores[i];
109
110 struct topology_node *node = &smt_nodes[i];
111
112 /* only the first core_count core_nodes are filled in */
113 size_t core_index = 0;
114 for (size_t j = 0; j < core_count; j++) {
115 if (core_nodes[j].core->core_id == c->core_id &&
116 core_nodes[j].core->package_id == c->package_id) {
117 core_index = j;
118 break;
119 }
120 }
121
122 node->level = TOPOLOGY_LEVEL_SMT;
123 node->id = i;
124 node->parent = core_index;
125 node->core = c;
126 c->topo_node = node;
127 node->first_child = -1;
128
129 node->nr_children = 0;
130
131 cpu_mask_init(m: &node->cpus, nbits: cpu_count);
132 cpu_mask_set(m: &node->cpus, cpu: i);
133 cpu_mask_init(m: &node->idle, nbits: cpu_count);
134 cpu_mask_set(m: &node->idle, cpu: i);
135
136 struct topology_node *parent_core = &core_nodes[core_index];
137
138 node->parent_node = parent_core;
139
140 if (parent_core->first_child == -1)
141 parent_core->first_child = i;
142
143 parent_core->nr_children++;
144 }
145
146 return cpu_count;
147}
148
149static size_t build_core_nodes(size_t cpu_count) {
150 size_t core_count = 0;
151 core_nodes = nofail_vnews(core_nodes, cpu_count, ALLOC_ZERO);
152
153 for (size_t i = 0; i < cpu_count; i++) {
154 struct core *c = global.cores[i];
155
156 bool exists = false;
157 for (size_t j = 0; j < core_count; j++) {
158 if (core_nodes[j].core->core_id == c->core_id &&
159 core_nodes[j].core->package_id == c->package_id) {
160 exists = true;
161 break;
162 }
163 }
164
165 if (exists)
166 continue;
167
168 struct topology_node *node = &core_nodes[core_count];
169
170 node->level = TOPOLOGY_LEVEL_CORE;
171 node->id = c->core_id;
172 node->first_child = -1;
173 node->nr_children = 0;
174 node->core = c;
175 node->parent = -1;
176 node->parent_node = NULL;
177
178 cpu_mask_init(m: &node->cpus, nbits: cpu_count);
179 cpu_mask_init(m: &node->idle, nbits: cpu_count);
180
181 for (size_t j = 0; j < cpu_count; j++) {
182 struct core *cj = global.cores[j];
183 if (cj->core_id == c->core_id && cj->package_id == c->package_id) {
184 cpu_mask_set(m: &node->cpus, cpu: j);
185 cpu_mask_set(m: &node->idle, cpu: j);
186 }
187 }
188
189 core_count++;
190 }
191
192 return core_count;
193}
194
195static size_t build_numa_nodes(size_t core_count, size_t llc_count) {
196 size_t max_numa = 0;
197 for (size_t i = 0; i < core_count; i++)
198 if (core_nodes[i].core->numa_node > max_numa)
199 max_numa = core_nodes[i].core->numa_node;
200
201 size_t numa_node_count = max_numa + 1;
202 numa_nodes = nofail_vnews(numa_nodes, numa_node_count, ALLOC_ZERO);
203
204 for (size_t i = 0; i < numa_node_count; i++) {
205 struct topology_node *numa = &numa_nodes[i];
206 numa->level = TOPOLOGY_LEVEL_NUMA;
207 numa->id = i;
208 numa->parent = -1;
209 numa->first_child = -1;
210 numa->nr_children = 0;
211 numa->core = NULL;
212
213 /* Initialized if there is actually
214 * NUMA present (these nodes are not fake) */
215 if (global.numa_node_count > 1) {
216 numa->data.numa = &global.numa_nodes[i];
217 global.numa_nodes[i].topo = numa;
218 }
219
220 cpu_mask_init(m: &numa->cpus, nbits: global.core_count);
221 cpu_mask_init(m: &numa->idle, nbits: global.core_count);
222 }
223
224 for (size_t i = 0; i < core_count; i++) {
225 struct core *c = core_nodes[i].core;
226 uint32_t numa_id = c->numa_node;
227 /* NOLINTNEXTLINE(*ArrayBound) */
228 struct topology_node *numa = &numa_nodes[numa_id];
229
230 core_nodes[i].parent = numa_id;
231 core_nodes[i].parent_node = numa;
232
233 if (numa->first_child == -1)
234 numa->first_child = i;
235
236 numa->nr_children++;
237 cpu_mask_or(dst: &numa->cpus, b: &core_nodes[i].cpus);
238 cpu_mask_or(dst: &numa->idle, b: &core_nodes[i].idle);
239 }
240
241 for (size_t i = 0; i < numa_node_count; i++) {
242 struct topology_node *numa = &numa_nodes[i];
243 if (numa->first_child == -1)
244 continue;
245
246 for (size_t j = 0; j < llc_count; j++) {
247 struct topology_node *llc = &llc_nodes[j];
248
249 if (cpu_mask_intersects(a: &llc->cpus, b: &numa->cpus)) {
250 numa->parent = llc->id;
251 numa->parent_node = llc;
252 numa->data.cache = llc->data.cache;
253
254 if (llc->first_child == -1)
255 llc->first_child = i;
256
257 llc->nr_children++;
258 break;
259 }
260 }
261 }
262
263 return numa_node_count;
264}
265
266static size_t build_llc_nodes(size_t core_count) {
267 llc_nodes = nofail_vnews(llc_nodes, core_count, ALLOC_ZERO);
268 size_t llc_count = 0;
269
270 for (size_t i = 0; i < core_count; i++) {
271 struct core *c = core_nodes[i].core;
272 uint32_t pkg_id = c->package_id;
273
274 if (c->llc.level == 0 || c->llc.type == 0)
275 continue;
276
277 bool exists = false;
278 for (size_t j = 0; j < llc_count; j++) {
279 struct topology_cache_info *existing = llc_nodes[j].data.cache;
280 if (existing->level == c->llc.level &&
281 existing->type == c->llc.type &&
282 existing->size_kb == c->llc.size_kb &&
283 llc_nodes[j].parent == pkg_id) { /* Real */
284 exists = true;
285 cpu_mask_or(dst: &llc_nodes[j].cpus, b: &core_nodes[i].cpus);
286 cpu_mask_or(dst: &llc_nodes[j].idle, b: &core_nodes[i].idle);
287 break;
288 }
289 }
290
291 if (exists)
292 continue;
293
294 struct topology_node *node = &llc_nodes[llc_count];
295 node->level = TOPOLOGY_LEVEL_LLC;
296 node->id = llc_count;
297 node->parent = pkg_id;
298 node->core = NULL;
299 node->data.cache = &c->llc;
300
301 node->first_child = -1;
302 node->nr_children = 0;
303
304 cpu_mask_init(m: &node->cpus, nbits: global.core_count);
305 cpu_mask_or(dst: &node->cpus, b: &core_nodes[i].cpus);
306
307 cpu_mask_init(m: &node->idle, nbits: global.core_count);
308 cpu_mask_or(dst: &node->idle, b: &core_nodes[i].idle);
309
310 llc_count++;
311 }
312
313 if (llc_count > 0)
314 return llc_count;
315
316 /* no LLC info present, mirror packages */
317 uint32_t max_pkg_id = 0;
318 for (size_t i = 0; i < core_count; i++)
319 if (core_nodes[i].core->package_id > max_pkg_id)
320 max_pkg_id = core_nodes[i].core->package_id;
321
322 size_t package_count = max_pkg_id + 1;
323
324 /* dense package IDs (densify_package_ids) and every package has a core */
325 enforce(package_count <= core_count, "more packages than cores");
326
327 for (size_t p = 0; p < package_count; p++) {
328 struct topology_node *node = &llc_nodes[llc_count];
329 node->level = TOPOLOGY_LEVEL_LLC;
330 node->id = llc_count;
331 node->parent = p;
332 node->core = NULL;
333 node->data.cache = NULL;
334
335 node->first_child = -1;
336 node->nr_children = 0;
337
338 cpu_mask_init(m: &node->cpus, nbits: global.core_count);
339 cpu_mask_init(m: &node->idle, nbits: global.core_count);
340
341 for (size_t i = 0; i < core_count; i++) {
342
343 if (core_nodes[i].core->package_id == p) {
344 cpu_mask_or(dst: &node->cpus, b: &core_nodes[i].cpus);
345 cpu_mask_or(dst: &node->idle, b: &core_nodes[i].idle);
346 }
347 }
348
349 llc_count++;
350 }
351
352 return llc_count;
353}
354
355static size_t build_package_nodes(size_t core_count, size_t llc_count) {
356
357 uint32_t max_pkg_id = 0;
358
359 for (size_t i = 0; i < core_count; i++)
360 if (core_nodes[i].core->package_id > max_pkg_id)
361 max_pkg_id = core_nodes[i].core->package_id;
362
363 size_t package_count = max_pkg_id + 1;
364 package_nodes = nofail_vnews(package_nodes, package_count, ALLOC_ZERO);
365
366 for (size_t i = 0; i < package_count; i++) {
367 struct topology_node *pkg = &package_nodes[i];
368 pkg->level = TOPOLOGY_LEVEL_PACKAGE;
369 pkg->id = i;
370 pkg->parent = 0;
371 pkg->first_child = -1;
372 pkg->nr_children = 0;
373 pkg->core = NULL;
374 cpu_mask_init(m: &pkg->cpus, nbits: global.core_count);
375 cpu_mask_init(m: &pkg->idle, nbits: global.core_count);
376 }
377
378 for (size_t j = 0; j < llc_count; j++) {
379 struct topology_node *llc = &llc_nodes[j];
380 uint32_t pkg_id = llc->parent;
381 if (pkg_id >= package_count)
382 continue;
383
384 struct topology_node *pkg = &package_nodes[pkg_id];
385
386 if (pkg->first_child == -1)
387 pkg->first_child = j;
388
389 llc->parent_node = pkg;
390 pkg->parent_node = &machine_node;
391 pkg->nr_children++;
392 cpu_mask_or(dst: &pkg->cpus, b: &llc->cpus);
393 cpu_mask_or(dst: &pkg->idle, b: &llc->idle);
394 }
395
396 return package_count;
397}
398
399static void build_machine_node(size_t package_count) {
400 machine_node.level = TOPOLOGY_LEVEL_MACHINE;
401 machine_node.id = 0;
402 machine_node.parent = -1;
403 machine_node.first_child = -1;
404 machine_node.nr_children = package_count;
405 machine_node.core = NULL;
406
407 cpu_mask_init(m: &machine_node.cpus, nbits: global.core_count);
408
409 cpu_mask_init(m: &machine_node.idle, nbits: global.core_count);
410
411 for (size_t i = 0; i < package_count; i++) {
412 struct topology_node *pkg = &package_nodes[i];
413
414 if (machine_node.first_child == -1)
415 machine_node.first_child = i;
416
417 cpu_mask_or(dst: &machine_node.cpus, b: &pkg->cpus);
418 cpu_mask_or(dst: &machine_node.idle, b: &pkg->idle);
419 }
420}
421
422static int cmp_u32(const void *a, const void *b) {
423 uint32_t x = *(const uint32_t *) a, y = *(const uint32_t *) b;
424 return (x > y) - (x < y);
425}
426
427/* package_id comes from the APIC ID */
428static void densify_package_ids(size_t cpu_count) {
429 uint32_t *ids = nofail_vnews(ids, cpu_count);
430 for (size_t i = 0; i < cpu_count; i++)
431 ids[i] = global.cores[i]->package_id;
432
433 heapsort(vbase: ids, nmemb: cpu_count, size: sizeof(*ids), compar: cmp_u32);
434
435 size_t distinct = 0;
436 for (size_t i = 0; i < cpu_count; i++)
437 if (distinct == 0 || ids[distinct - 1] != ids[i])
438 ids[distinct++] = ids[i];
439
440 for (size_t i = 0; i < cpu_count; i++) {
441 struct core *c = global.cores[i];
442 uint32_t *slot =
443 bsearch(key: &c->package_id, base: ids, nmemb: distinct, size: sizeof(*ids), compar: cmp_u32);
444 c->package_id = (uint32_t) (slot - ids);
445 }
446
447 vfree(ids);
448}
449
450void topology_init(void) {
451 size_t cpu_count = global.core_count; /* Logical processor count */
452 enforce(cpu_count > 0);
453
454 densify_package_ids(cpu_count);
455
456 size_t core_count = build_core_nodes(cpu_count);
457 size_t smt_count = build_smt_nodes(cpu_count, core_count);
458 size_t llc_count = build_llc_nodes(core_count);
459 size_t numa_count = build_numa_nodes(core_count, llc_count);
460 size_t package_count = build_package_nodes(core_count, llc_count);
461
462 build_machine_node(package_count);
463
464 global.topology.level[TOPOLOGY_LEVEL_SMT] = smt_nodes;
465 global.topology.count[TOPOLOGY_LEVEL_SMT] = smt_count;
466 global.topology.level[TOPOLOGY_LEVEL_CORE] = core_nodes;
467 global.topology.count[TOPOLOGY_LEVEL_CORE] = core_count;
468 global.topology.level[TOPOLOGY_LEVEL_NUMA] = numa_nodes;
469 global.topology.count[TOPOLOGY_LEVEL_NUMA] = numa_count;
470 global.topology.level[TOPOLOGY_LEVEL_LLC] = llc_nodes;
471 global.topology.count[TOPOLOGY_LEVEL_LLC] = llc_count;
472 global.topology.level[TOPOLOGY_LEVEL_PACKAGE] = package_nodes;
473 global.topology.count[TOPOLOGY_LEVEL_PACKAGE] = package_count;
474 global.topology.level[TOPOLOGY_LEVEL_MACHINE] = &machine_node;
475 global.topology.count[TOPOLOGY_LEVEL_MACHINE] = 1;
476
477 topology_dump();
478 domain_dump();
479}
480
481void topology_mark_core_idle(cpu_id_t cpu_id, bool idle) {
482 if (!global.topology.level[TOPOLOGY_LEVEL_MACHINE])
483 return;
484
485 struct topology_node *smt = &smt_nodes[cpu_id];
486
487 struct topology_node *node = smt;
488 while (node) {
489 if (idle)
490 cpu_mask_set_atomic(m: &node->idle, cpu: cpu_id);
491 else
492 cpu_mask_clear_atomic(m: &node->idle, cpu: cpu_id);
493
494 node = node->parent_node;
495 }
496}
497
498struct core *topology_find_idle_core(struct core *local_core,
499 enum topology_level max_search) {
500 enforce_precond(
501 max_search >
502 TOPOLOGY_LEVEL_SMT); /* 'SMT' will be the core itself.
503 * It has no neighbors, and thus
504 * cannot be searched through (one core) */
505
506 struct topology_node *smt_node = local_core->topo_node; /* Direct node */
507 struct topology_node *core_node = smt_node->parent_node;
508 struct topology_node *numa_node = core_node->parent_node;
509 struct topology_node *llc_node = numa_node->parent_node;
510 struct topology_node *pkg_node = llc_node->parent_node;
511
512 /* First try SMT siblings */
513 for (int32_t i = 0; i < core_node->nr_children; i++) {
514 struct topology_node *sibling = &smt_nodes[core_node->first_child + i];
515 if (!cpu_mask_empty(m: &sibling->idle))
516 return sibling->core;
517 }
518
519 /* Not allowed to search to NUMA */
520 if (max_search < TOPOLOGY_LEVEL_NUMA)
521 return NULL;
522
523 /* Next try NUMA siblings */
524 for (int32_t i = 0; i < numa_node->nr_children; i++) {
525 struct topology_node *core = &core_nodes[numa_node->first_child + i];
526 if (!cpu_mask_empty(m: &core->idle))
527 return core->core;
528 }
529
530 if (max_search < TOPOLOGY_LEVEL_LLC)
531 return NULL;
532
533 for (int32_t i = 0; i < llc_node->nr_children; i++) {
534 struct topology_node *core = &core_nodes[llc_node->first_child + i];
535 if (!cpu_mask_empty(m: &core->idle))
536 return core->core;
537 }
538
539 /* Finally do a full CPU scan */
540 for (int32_t i = 0; i < pkg_node->nr_children; i++) {
541 struct topology_node *llc = &llc_nodes[pkg_node->first_child + i];
542 if (cpu_mask_empty(m: &llc->idle))
543 continue;
544
545 for (int32_t j = 0; j < smt_nodes->nr_children; j++) {
546 struct topology_node *smt = &smt_nodes[llc->first_child + j];
547 if (!cpu_mask_empty(m: &smt->idle))
548 return smt->core;
549 }
550 }
551
552 size_t i;
553 for_each_cpu_id(i) {
554 struct topology_node *smt = &smt_nodes[i];
555 if (!cpu_mask_empty(m: &smt->idle))
556 return smt->core;
557 }
558
559 return NULL;
560}
561
562static struct cpu_mask topology_level_mask(cpu_id_t id,
563 enum topology_level level) {
564 if (level == TOPOLOGY_LEVEL_EX_DOMAIN) {
565 domain_id_t domain = global.cores[id]->domain->id;
566 struct cpu_mask ret = CPU_MASK_INIT;
567 domain_set_cpu_mask(mask: &ret, domain: global.domains[domain]);
568 return ret;
569 }
570
571 struct topology_node *nodes = global.topology.level[level];
572 uint16_t count = global.topology.count[level];
573 for (uint16_t i = 0; i < count; i++) {
574 struct topology_node *node = &nodes[i];
575 if (cpu_mask_test(m: &node->cpus, cpu: id))
576 return node->cpus;
577 }
578 unreachable();
579}
580
581bool topology_contract_verify(struct topology_contract c) {
582 enum topology_level scope = c.scope;
583 enum topology_caller caller = c.caller;
584
585 if (caller != TOPC_NONE) {
586 bool valid = false;
587
588 if (caller & TOPC_IFLAG)
589 valid = !irqs_enabled();
590
591 valid = valid || global.current_bootstage < BOOTSTAGE_LATE;
592
593 /* Short circuiting here matters: if EARLY and IRQL are set
594 * before IRQLs are available to read, we are not able to
595 * call irql_get (it would crash) */
596 if (caller & TOPC_IRQL)
597 valid = valid || irql_get() >= IRQL_DISPATCH_LEVEL;
598
599 if (caller & TOPC_PINNED && irq_not_in_interrupt()) {
600 valid = valid || thread_is_pinned(t: thread_get_current());
601 if (!valid) {
602 /* This is where scope actually means something,
603 * we check that the thread's allowed_cpus ∈ scope_cpus */
604 cpu_id_t cpu = smp_id(cond: TOPC_NONE);
605 struct cpu_mask scope_cpus = topology_level_mask(id: cpu, level: scope);
606 struct thread *self = thread_get_current();
607 valid = cpu_mask_subset(subset: &self->allowed_cpus, superset: &scope_cpus);
608 }
609 }
610
611 if (caller & TOPC_IRQ)
612 valid = valid || (irq_in_interrupt() || irq_in_nmi());
613
614 return valid;
615 }
616
617 return true;
618}
619