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