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