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