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