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