sched: Fix packed initialization
[akaros.git] / kern / src / corealloc_packed.c
1 /* Copyright (c) 2015 The Regents of the University of California
2  * Valmon Leymarie <leymariv@berkeley.edu>
3  * Kevin Klues <klueska@cs.berkeley.edu>
4  * See LICENSE for details.
5  */
6
7 #include <arch/topology.h>
8 #include <sys/queue.h>
9 #include <env.h>
10 #include <corerequest.h>
11 #include <kmalloc.h>
12
13 enum pnode_type { CORE, CPU, SOCKET, NUMA, MACHINE, NUM_NODE_TYPES };
14 static char pnode_label[5][8] = { "CORE", "CPU", "SOCKET", "NUMA", "MACHINE" };
15
16 /* Internal representation of a node in the hierarchy of elements in the cpu
17  * topology of the machine (i.e. numa domain, socket, cpu, core, etc.). */
18 struct sched_pnode {
19         int id;
20         enum pnode_type type;
21         struct sched_pnode *parent;
22
23         /* Refcount is used to track how many cores have been allocated beneath the
24          * current node in the hierarchy. */
25         int refcount;
26
27         /* All nodes except cores have children. Cores have a sched_pcore. */
28         union {
29                 struct sched_pnode *children;
30                 struct sched_pcore *sched_pcore;
31         };
32 };
33
34 #define num_cpus            (cpu_topology_info.num_cpus)
35 #define num_sockets         (cpu_topology_info.num_sockets)
36 #define num_numa            (cpu_topology_info.num_numa)
37 #define cores_per_numa      (cpu_topology_info.cores_per_numa)
38 #define cores_per_socket    (cpu_topology_info.cores_per_socket)
39 #define cores_per_cpu       (cpu_topology_info.cores_per_cpu)
40 #define cpus_per_socket     (cpu_topology_info.cpus_per_socket)
41 #define cpus_per_numa       (cpu_topology_info.cpus_per_numa)
42 #define sockets_per_numa    (cpu_topology_info.sockets_per_numa)
43
44 #define child_node_type(t) ((t) - 1)
45
46 /* The pcores in the system. (array gets alloced in init()).  */
47 struct sched_pcore *all_pcores;
48
49 /* TAILQ of all unallocated, idle (CG) cores */
50 struct sched_pcore_tailq idlecores = TAILQ_HEAD_INITIALIZER(idlecores);
51
52 /* An array containing the number of nodes at each level. */
53 static int num_nodes[NUM_NODE_TYPES];
54
55 /* A 2D array containing for all core i its distance from a core j. */
56 static int **core_distance;
57
58 /* An array containing the number of children at each level. */
59 static int num_descendants[NUM_NODE_TYPES][NUM_NODE_TYPES];
60
61 /* A list of lookup tables to find specific nodes by type and id. */
62 static int total_nodes;
63 static struct sched_pnode *all_nodes;
64 static struct sched_pnode *node_lookup[NUM_NODE_TYPES];
65
66 /* Recursively increase the refcount from the node passed in through all of its
67  * ancestors in the hierarchy. */
68 static void incref_nodes(struct sched_pnode *n)
69 {
70         while (n != NULL) {
71                 n->refcount++;
72                 n = n->parent;
73         }
74 }
75
76 /* Recursively decrease the refcount from the node passed in through all of its
77  * ancestors in the hierarchy. */
78 static void decref_nodes(struct sched_pnode *n)
79 {
80         while (n != NULL) {
81                 n->refcount--;
82                 n = n->parent;
83         }
84 }
85
86 /* Create a node and initialize it. This code assumes that child are created
87  * before parent nodes. */
88 static void init_nodes(int type, int num, int nchildren)
89 {
90         /* Initialize the lookup table for this node type. */
91         num_nodes[type] = num;
92         node_lookup[type] = all_nodes;
93         for (int i = CORE; i < type; i++)
94                 node_lookup[type] += num_nodes[i];
95
96         /* Initialize all fields of each node of this type. */
97         for (int i = 0; i < num; i++) {
98                 struct sched_pnode *n = &node_lookup[type][i];
99
100                 /* Initialize the common fields. */
101                 n->id = i;
102                 n->type = type;
103                 n->refcount = 0;
104                 n->parent = NULL;
105
106                 /* If we are a core node, initialize the sched_pcore field. */
107                 if (n->type == CORE) {
108                         n->sched_pcore = &all_pcores[n->id];
109                         n->sched_pcore->sched_pnode = n;
110                         n->sched_pcore->core_info = &cpu_topology_info.core_list[n->id];
111                         n->sched_pcore->alloc_proc = NULL;
112                         n->sched_pcore->prov_proc = NULL;
113                 }
114                 /* Otherwise initialize the children field, updating the parent of all
115                  * children to the current node. This assumes the children have already
116                  * been initialized (i.e. init_nodes() must be called iteratively from
117                  * the bottom-up). */
118                 if (n->type != CORE) {
119                         n->children = &node_lookup[child_node_type(type)][i * nchildren];
120                         for (int j = 0; j < nchildren; j++)
121                                 n->children[j].parent = n;
122                 }
123         }
124 }
125
126 /* Allocate a table of distances from one core to an other. Cores on the same
127  * cpu have a distance of 1; same socket have a distance of 2; same numa -> 3;
128  * same machine -> 4; */
129 static void init_core_distances(void)
130 {
131         core_distance = kzmalloc(num_cores * sizeof(int*), 0);
132         if (core_distance == NULL)
133                 panic("Out of memory!\n");
134         for (int i = 0; i < num_cores; i++) {
135                 core_distance[i] = kzmalloc(num_cores * sizeof(int), 0);
136                 if (core_distance[i] == NULL)
137                         panic("Out of memory!\n");
138         }
139         for (int i = 0; i < num_cores; i++) {
140                 for (int j = 0; j < num_cores; j++) {
141                         for (int k = CPU; k <= MACHINE; k++) {
142                                 if (i/num_descendants[k][CORE] ==
143                                         j/num_descendants[k][CORE]) {
144                                         core_distance[i][j] = k;
145                                         break;
146                                 }
147                         }
148                 }
149         }
150 }
151
152 /* Initialize any data assocaited with doing core allocation. */
153 void corealloc_init(void)
154 {
155         void *nodes_and_cores;
156
157         /* Allocate a flat array of nodes. */
158         total_nodes = num_cores + num_cpus + num_sockets + num_numa + 1;
159         nodes_and_cores = kmalloc(total_nodes * sizeof(struct sched_pnode) +
160                                   num_cores * sizeof(struct sched_pcore), 0);
161         all_nodes = nodes_and_cores;
162         all_pcores = nodes_and_cores + total_nodes * sizeof(struct sched_pnode);
163
164         /* Initialize the number of descendants from our cpu_topology info. */
165         num_descendants[CPU][CORE] = cores_per_cpu;
166         num_descendants[SOCKET][CORE] = cores_per_socket;
167         num_descendants[SOCKET][CPU] = cpus_per_socket;
168         num_descendants[NUMA][CORE] = cores_per_numa;
169         num_descendants[NUMA][CPU] = cpus_per_numa;
170         num_descendants[NUMA][SOCKET] = sockets_per_numa;
171         num_descendants[MACHINE][CORE] = num_cores;
172         num_descendants[MACHINE][CPU] = num_cpus;
173         num_descendants[MACHINE][SOCKET] = num_sockets;
174         num_descendants[MACHINE][NUMA] = num_numa;
175
176         /* Initialize the nodes at each level in our hierarchy. */
177         init_nodes(CORE, num_cores, 0);
178         init_nodes(CPU, num_cpus, cores_per_cpu);
179         init_nodes(SOCKET, num_sockets, cpus_per_socket);
180         init_nodes(NUMA, num_numa, sockets_per_numa);
181         init_nodes(MACHINE, 1, num_numa);
182
183         /* Initialize our table of core_distances */
184         init_core_distances();
185
186         for (int i = 0; i < num_cores; i++) {
187                 /* Remove all ll_cores from consideration for allocation. */
188                 if (is_ll_core(i)) {
189                         incref_nodes(all_pcores[i].sched_pnode);
190                         continue;
191                 }
192 #ifdef CONFIG_DISABLE_SMT
193                 /* Remove all even cores from consideration for allocation. */
194                 if (i % 2 == 0) {
195                         incref_nodes(all_pcores[i].sched_pnode);
196                         continue;
197                 }
198 #endif /* CONFIG_DISABLE_SMT */
199                 /* Fill the idlecores array. */
200                 TAILQ_INSERT_HEAD(&idlecores, &all_pcores[i], alloc_next);
201         }
202 }
203
204 /* Initialize any data associated with allocating cores to a process. */
205 void corealloc_proc_init(struct proc *p)
206 {
207         TAILQ_INIT(&p->ksched_data.crd.alloc_me);
208         TAILQ_INIT(&p->ksched_data.crd.prov_alloc_me);
209         TAILQ_INIT(&p->ksched_data.crd.prov_not_alloc_me);
210 }
211
212 /* Returns the sum of the distances from one core to all cores in a list. */
213 static int cumulative_core_distance(struct sched_pcore *c,
214                                     struct sched_pcore_tailq cl)
215 {
216         int d = 0;
217         struct sched_pcore *temp = NULL;
218
219         TAILQ_FOREACH(temp, &cl, alloc_next) {
220                 d += core_distance[c->core_info->core_id][temp->core_info->core_id];
221         }
222         return d;
223 }
224
225 /* Returns the first core in the hierarchy under node n. */
226 static struct sched_pcore *first_core_in_node(struct sched_pnode *n)
227 {
228         struct sched_pnode *first_child = n;
229
230         while (first_child->type != CORE)
231                 first_child = &first_child->children[0];
232         return first_child->sched_pcore;
233 }
234
235 /* Return the first provisioned core available. Otherwise, return NULL. */
236 static struct sched_pcore *find_first_provisioned_core(struct proc *p)
237 {
238         return TAILQ_FIRST(&(p->ksched_data.crd.prov_not_alloc_me));
239 }
240
241 /* Returns the best first core to allocate for a proc which owns no core.
242  * Return the core that is the farthest from the others's proc cores. */
243 static struct sched_pcore *find_first_core(struct proc *p)
244 {
245         struct sched_pcore *c;
246         struct sched_pnode *n;
247         struct sched_pnode *nodes;
248         struct sched_pnode *bestn;
249         int best_refcount;
250
251         /* Find the best, first provisioned core if there are any. Even if the
252          * whole machine is allocated, we still give out provisioned cores, because
253          * they will be revoked from their current owner if necessary. */
254         c = find_first_provisioned_core(p);
255         if (c != NULL)
256                 return c;
257
258         /* Otherwise, if the whole machine is already allocated, there are no
259          * cores left to allocate, and we are done. */
260         bestn = &node_lookup[MACHINE][0];
261         if (bestn->refcount == num_descendants[MACHINE][CORE])
262                 return NULL;
263
264         /* Otherwise, we know at least one core is still available, so let's find
265          * the best one to allocate first. We start at NUMA, and loop through the
266          * topology to find it. */
267         for (int i = NUMA; i >= CORE; i--) {
268                 nodes = bestn->children;
269                 best_refcount = total_nodes;
270                 bestn = NULL;
271
272                 for (int j = 0; j < num_nodes[i]; j++) {
273                         n = &nodes[j];
274                         if (n->refcount == 0)
275                                 return first_core_in_node(n);
276                         if (n->refcount == num_descendants[i][CORE])
277                                 continue;
278                         if (n->refcount < best_refcount) {
279                                 best_refcount = n->refcount;
280                                 bestn = n;
281                         }
282                 }
283         }
284         return bestn->sched_pcore;
285 }
286
287 /* Return the closest core from the list of provisioned cores to cores we
288  * already own. If no cores are available we return NULL.*/
289 static struct sched_pcore *find_closest_provisioned_core(struct proc *p)
290 {
291         struct sched_pcore_tailq provisioned = p->ksched_data.crd.prov_not_alloc_me;
292         struct sched_pcore_tailq allocated = p->ksched_data.crd.alloc_me;
293         struct sched_pcore *bestc = NULL;
294         struct sched_pcore *c = NULL;
295         int bestd = 0;
296
297         TAILQ_FOREACH(c, &provisioned, prov_next) {
298                 int currd = cumulative_core_distance(c, allocated);
299
300                 if ((bestd == 0) || (currd < bestd)) {
301                         bestd = currd;
302                         bestc = c;
303                 }
304         }
305         return bestc;
306 }
307
308 /* Return the closest core from the list of idlecores to cores we already own.
309  * If no cores are available we return NULL.*/
310 static struct sched_pcore *find_closest_idle_core(struct proc *p)
311 {
312         struct sched_pcore_tailq allocated = p->ksched_data.crd.alloc_me;
313         struct sched_pcore *bestc = NULL;
314         struct sched_pcore *c = NULL;
315         int bestd = 0;
316
317         /* TODO: Add optimization to hand out core at equivalent distance if the
318          * best core found is provisioned to someone else. */
319         TAILQ_FOREACH(c, &idlecores, alloc_next) {
320                 int currd = cumulative_core_distance(c, allocated);
321
322                 if ((bestd == 0) || (currd < bestd)) {
323                         bestd = currd;
324                         bestc = c;
325                 }
326         }
327         return bestc;
328 }
329
330 /* Consider the first core provisioned to a proc by calling
331  * find_best_provisioned_core(). Then check siblings of the cores the proc
332  * already owns. Calculate for every possible node its
333  * cumulative_core_distance() (sum of the distances from this core to all of
334  * the cores the proc owns). Allocate the core that has the lowest
335  * core_distance.  This code assumes that the scheduler that uses it holds a
336  * lock for the duration of the call. */
337 static struct sched_pcore *find_closest_core(struct proc *p)
338 {
339         struct sched_pcore *bestc;
340
341         bestc = find_closest_provisioned_core(p);
342         if (bestc)
343                 return bestc;
344         return find_closest_idle_core(p);
345 }
346
347 /* Find the best core to allocate. If no cores are allocated yet, find one that
348  * is as far from the cores allocated to other processes as possible.
349  * Otherwise, find a core that is as close as possible to one of the other
350  * cores we already own. */
351 uint32_t __find_best_core_to_alloc(struct proc *p)
352 {
353         struct sched_pcore *c = NULL;
354
355         if (TAILQ_FIRST(&(p->ksched_data.crd.alloc_me)) == NULL)
356                 c = find_first_core(p);
357         else
358                 c = find_closest_core(p);
359
360         if (c == NULL)
361                 return -1;
362         return spc2pcoreid(c);
363 }
364
365 /* Track the pcore properly when it is allocated to p. This code assumes that
366  * the scheduler that uses it holds a lock for the duration of the call. */
367 void __track_core_alloc(struct proc *p, uint32_t pcoreid)
368 {
369         struct sched_pcore *spc;
370
371         assert(pcoreid < num_cores);    /* catch bugs */
372         spc = pcoreid2spc(pcoreid);
373         assert(spc->alloc_proc != p);   /* corruption or double-alloc */
374         spc->alloc_proc = p;
375         /* if the pcore is prov to them and now allocated, move lists */
376         if (spc->prov_proc == p) {
377                 TAILQ_REMOVE(&p->ksched_data.crd.prov_not_alloc_me, spc, prov_next);
378                 TAILQ_INSERT_TAIL(&p->ksched_data.crd.prov_alloc_me, spc, prov_next);
379         }
380         /* Actually allocate the core, removing it from the idle core list. */
381         TAILQ_INSERT_TAIL(&p->ksched_data.crd.alloc_me, spc, alloc_next);
382         TAILQ_REMOVE(&idlecores, spc, alloc_next);
383         incref_nodes(spc->sched_pnode);
384 }
385
386 /* Track the pcore properly when it is deallocated from p. This code assumes
387  * that the scheduler that uses it holds a lock for the duration of the call.
388  * */
389 void __track_core_dealloc(struct proc *p, uint32_t pcoreid)
390 {
391         struct sched_pcore *spc;
392
393         assert(pcoreid < num_cores);    /* catch bugs */
394         spc = pcoreid2spc(pcoreid);
395         spc->alloc_proc = NULL;
396         /* if the pcore is prov to them and now deallocated, move lists */
397         if (spc->prov_proc == p) {
398                 TAILQ_REMOVE(&p->ksched_data.crd.prov_alloc_me, spc, prov_next);
399                 /* this is the victim list, which can be sorted so that we pick the
400                  * right victim (sort by alloc_proc reverse priority, etc).  In this
401                  * case, the core isn't alloc'd by anyone, so it should be the first
402                  * victim. */
403                 TAILQ_INSERT_HEAD(&p->ksched_data.crd.prov_not_alloc_me, spc,
404                                   prov_next);
405         }
406         /* Actually dealloc the core, putting it back on the idle core list. */
407         TAILQ_REMOVE(&(p->ksched_data.crd.alloc_me), spc, alloc_next);
408         TAILQ_INSERT_HEAD(&idlecores, spc, alloc_next);
409         decref_nodes(spc->sched_pnode);
410 }
411
412 /* Bulk interface for __track_core_dealloc */
413 void __track_core_dealloc_bulk(struct proc *p, uint32_t *pc_arr,
414                                uint32_t nr_cores)
415 {
416         for (int i = 0; i < nr_cores; i++)
417                 __track_core_dealloc(p, pc_arr[i]);
418 }
419
420 /* One off function to make 'pcoreid' the next core chosen by the core
421  * allocation algorithm (so long as no provisioned cores are still idle).
422  * This code assumes that the scheduler that uses it holds a lock for the
423  * duration of the call. */
424 void __next_core_to_alloc(uint32_t pcoreid)
425 {
426         printk("This function is not supported by this core allocation policy!\n");
427 }
428
429 /* One off function to sort the idle core list for debugging in the kernel
430  * monitor. This code assumes that the scheduler that uses it holds a lock
431  * for the duration of the call. */
432 void __sort_idle_cores(void)
433 {
434         printk("This function is not supported by this core allocation policy!\n");
435 }
436
437 /* Print the map of idle cores that are still allocatable through our core
438  * allocation algorithm. */
439 void print_idle_core_map(void)
440 {
441         printk("Idle cores (unlocked!):\n");
442         for (int i = 0; i < num_cores; i++) {
443                 struct sched_pcore *spc_i = &all_pcores[i];
444
445                 if (spc_i->alloc_proc == NULL)
446                         printk("Core %d, prov to %d (%p)\n", spc_i->core_info->core_id,
447                                spc_i->prov_proc ? spc_i->prov_proc->pid :
448                                    0, spc_i->prov_proc);
449         }
450 }