1#include <console/panic.h>
2#include <global.h>
3#include <kassert.h>
4#include <log.h>
5#include <mem/alloc.h>
6#include <mem/alloc_or_die.h>
7#include <sch/domain.h>
8#include <string.h>
9
10static struct scheduler_domain *
11build_domain_for_level(enum topology_level lvl) {
12 struct topology *t = &global.topology;
13
14 size_t n = t->count[lvl];
15 struct topology_node *nodes = t->level[lvl];
16
17 struct scheduler_domain *d = kmalloc_or_die(sizeof(*d), ALLOC_FLAGS_ZERO);
18
19 d->level = lvl;
20 d->ngroups = n;
21 d->groups = alloc_or_die(
22 kmalloc(sizeof(struct scheduler_group) * n, ALLOC_FLAGS_ZERO));
23
24 for (size_t i = 0; i < n; i++) {
25 struct topology_node *node = &nodes[i];
26
27 /* clone cpu masks into group */
28 cpu_mask_copy(dst: &d->groups[i].cpus, src: &node->cpus);
29 cpu_mask_copy(dst: &d->groups[i].idle, src: &node->idle);
30
31 d->groups[i].topo_index = i;
32
33 d->groups[i].parent_index = -1;
34 }
35
36 return d;
37}
38
39static void link_parent_groups(struct scheduler_domain *child,
40 struct scheduler_domain *parent) {
41 child->parent = parent;
42
43 for (size_t g = 0; g < child->ngroups; g++) {
44
45 struct scheduler_group *cg = &child->groups[g];
46
47 /* find parent group whose cpus intersect */
48 for (size_t pg = 0; pg < parent->ngroups; pg++) {
49 struct scheduler_group *pgp = &parent->groups[pg];
50 if (cpu_mask_intersects(a: &cg->cpus, b: &pgp->cpus)) {
51 cg->parent_index = pg;
52 break;
53 }
54 }
55 }
56}
57
58static void map_cpus_to_groups(void) {
59 struct core *c;
60 for_each_cpu_struct(c) {
61 for (size_t i = 0; i < TOPOLOGY_LEVEL_MAX; i++) {
62 struct scheduler_domain *d = global.scheduler_domains[i];
63 c->domains[i] = d;
64
65 /* find group for this CPU */
66 int found = -1;
67 for (size_t g = 0; g < d->ngroups; g++) {
68 if (cpu_mask_test(m: &d->groups[g].cpus, cpu: __id)) {
69 found = g;
70 break;
71 }
72 }
73 kassert(found != -1);
74 c->group_index[i] = found;
75 }
76 }
77}
78
79void cpu_mask_print(const struct cpu_mask *m, char *buf, size_t buflen) {
80 size_t pos = 0;
81 pos += snprintf(buffer: buf + pos, buffer_len: buflen - pos, format: "{");
82
83 size_t last = 0;
84 for (size_t cpu = 0; cpu < global.core_count; cpu++)
85 if (cpu_mask_test(m, cpu))
86 if (last < cpu)
87 last = cpu;
88
89 for (size_t cpu = 0; cpu < global.core_count; cpu++) {
90 if (cpu_mask_test(m, cpu)) {
91 if (cpu == last)
92 pos += snprintf(buffer: buf + pos, buffer_len: buflen - pos, format: "%zu", cpu);
93 else
94 pos += snprintf(buffer: buf + pos, buffer_len: buflen - pos, format: "%zu,", cpu);
95 }
96 }
97 snprintf(buffer: buf + pos, buffer_len: buflen - pos, format: "}");
98}
99
100void scheduler_domains_dump(void) {
101 for (size_t lvl = 0; lvl < TOPOLOGY_LEVEL_MAX; lvl++) {
102 struct scheduler_domain *d = global.scheduler_domains[lvl];
103
104 log_msg(LOG_INFO, "SCHEDULER DOMAIN %zu (%s), %zu groups", lvl,
105 topology_level_name(lvl), d->ngroups);
106
107 for (size_t g = 0; g < d->ngroups; g++) {
108 struct scheduler_group *grp = &d->groups[g];
109
110 char buf1[256], buf2[256];
111 cpu_mask_print(m: &grp->cpus, buf: buf1, buflen: sizeof(buf1));
112
113 cpu_mask_print(m: &grp->idle, buf: buf2, buflen: sizeof(buf2));
114
115 grp->capacity = cpu_mask_popcount(m: &grp->cpus);
116 printf(
117 format: " Group %zu: CPUs = %s Idle = %s Parent = %d Capacity = %d\n",
118 g, buf1, buf2, grp->parent_index, grp->capacity);
119 }
120
121 printf(format: "\n");
122 }
123}
124
125void scheduler_domains_init(void) {
126 for (size_t i = 0; i < TOPOLOGY_LEVEL_MAX; i++) {
127 global.scheduler_domains[i] = build_domain_for_level(lvl: i);
128 }
129
130 for (size_t i = 0; i + 1 < TOPOLOGY_LEVEL_MAX; i++) {
131 link_parent_groups(child: global.scheduler_domains[i],
132 parent: global.scheduler_domains[i + 1]);
133 }
134
135 map_cpus_to_groups();
136
137 scheduler_domains_dump();
138
139 global.scheduler_domains_ready = true;
140}
141
142struct scheduler_group *scheduler_domain_find_sibling_group(struct core *c,
143 size_t domain_idx) {
144 struct scheduler_domain *d = c->domains[domain_idx];
145 size_t my_g = c->group_index[domain_idx];
146
147 for (size_t g = 0; g < d->ngroups; g++)
148 if (g != my_g)
149 return &d->groups[g];
150
151 return NULL;
152}
153
154int32_t scheduler_group_find_idle_cpu(struct scheduler_group *g) {
155 for (size_t cpu = 0; cpu < global.core_count; cpu++)
156 if (cpu_mask_test(m: &g->cpus, cpu) && cpu_mask_test(m: &g->idle, cpu))
157 return cpu;
158
159 return -1;
160}
161
162void scheduler_domain_mark_self_idle(bool idle) {
163 if (!global.scheduler_domains_ready)
164 return;
165
166 /* Caller upholds the contract */
167 struct core *c = smp_core(cond: TOPC_IRQL);
168 size_t cpu = smp_id(cond: TOPC_IRQL);
169
170 for (size_t lvl = 0; lvl < TOPOLOGY_LEVEL_MAX; lvl++) {
171 struct scheduler_domain *d = c->domains[lvl];
172 size_t g = c->group_index[lvl];
173 kassert(c->group_index[lvl] >= 0);
174 kassert((size_t) c->group_index[lvl] < d->ngroups);
175
176 struct scheduler_group *grp = &d->groups[g];
177
178 kassert(cpu < global.core_count);
179 kassert(cpu_mask_test(&grp->cpus, cpu));
180
181 if (idle)
182 cpu_mask_set_atomic(m: &grp->idle, cpu);
183 else
184 cpu_mask_clear_atomic(m: &grp->idle, cpu);
185 }
186}
187
188int32_t scheduler_find_idle_cpu_near(struct core *from) {
189 if (!global.scheduler_domains_ready)
190 return -1;
191
192 for (size_t lvl = TOPOLOGY_LEVEL_SMT; lvl < TOPOLOGY_LEVEL_MAX; lvl++) {
193 struct scheduler_domain *d = from->domains[lvl];
194 size_t g = from->group_index[lvl];
195
196 struct scheduler_group *grp = &d->groups[g];
197 int cpu = scheduler_group_find_idle_cpu(g: grp);
198 if (cpu >= 0)
199 return cpu;
200 }
201 return -1;
202}
203
204int32_t scheduler_push_target(struct core *from) {
205 if (!global.scheduler_domains_ready)
206 return -1;
207
208 for (int32_t lvl = TOPOLOGY_LEVEL_MAX - 1; lvl >= 0; lvl--) {
209 struct scheduler_domain *d = from->domains[lvl];
210
211 for (size_t g = 0; g < d->ngroups; g++) {
212 if ((int32_t) g == from->group_index[lvl])
213 continue;
214
215 int32_t cpu = scheduler_group_find_idle_cpu(g: &d->groups[g]);
216 if (cpu >= 0)
217 return cpu;
218 }
219 }
220 return -1;
221}
222