printk: check for user pointers in format string parameters
[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
31          * the 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 =
123                                 &cpu_topology_info.core_list[n->id];
124                         n->sched_pcore->alloc_proc = NULL;
125                         n->sched_pcore->prov_proc = NULL;
126                 }
127                 /* Otherwise initialize the children field, updating the parent
128                  * of all children to the current node. This assumes the
129                  * children have already been initialized (i.e. init_nodes()
130                  * must be called iteratively from the bottom-up). */
131                 if (n->type != CORE) {
132                         n->children =
133                             &node_lookup[child_node_type(type)][i * nchildren];
134                         for (int j = 0; j < nchildren; j++)
135                                 n->children[j].parent = n;
136                 }
137         }
138 }
139
140 /* Helper: Two cores have the same level id (and thus are at distance k, below)
141  * if their IDs divided by the number of cores per level are the same, due to
142  * how we number our cores. */
143 static int get_level_id(int coreid, int level)
144 {
145         return coreid / num_descendants[level][CORE];
146 }
147
148 /* Allocate a table of distances from one core to an other. Cores on the same
149  * cpu have a distance of 1; same socket have a distance of 2; same numa -> 3;
150  * same machine -> 4; */
151 static void init_core_distances(void)
152 {
153         core_distance = kzmalloc(num_cores * sizeof(int*), MEM_WAIT);
154         for (int i = 0; i < num_cores; i++)
155                 core_distance[i] = kzmalloc(num_cores * sizeof(int), MEM_WAIT);
156         for (int i = 0; i < num_cores; i++) {
157                 for (int j = 0; j < num_cores; j++) {
158                         for (int k = CPU; k <= MACHINE; k++) {
159                                 if (get_level_id(i, k) == get_level_id(j, k)) {
160                                         core_distance[i][j] = k;
161                                         break;
162                                 }
163                         }
164                 }
165         }
166 }
167
168 /* Initialize any data assocaited with doing core allocation. */
169 void corealloc_init(void)
170 {
171         void *nodes_and_cores;
172
173         /* Allocate a flat array of nodes. */
174         total_nodes = num_cores + num_cpus + num_sockets + num_numa + 1;
175         nodes_and_cores = kmalloc(total_nodes * sizeof(struct sched_pnode) +
176                                   num_cores * sizeof(struct sched_pcore),
177                                   MEM_WAIT);
178         all_nodes = nodes_and_cores;
179         all_pcores = nodes_and_cores + total_nodes * sizeof(struct sched_pnode);
180
181         /* Initialize the number of descendants from our cpu_topology info. */
182         num_descendants[CPU][CORE] = cores_per_cpu;
183         num_descendants[SOCKET][CORE] = cores_per_socket;
184         num_descendants[SOCKET][CPU] = cpus_per_socket;
185         num_descendants[NUMA][CORE] = cores_per_numa;
186         num_descendants[NUMA][CPU] = cpus_per_numa;
187         num_descendants[NUMA][SOCKET] = sockets_per_numa;
188         num_descendants[MACHINE][CORE] = num_cores;
189         num_descendants[MACHINE][CPU] = num_cpus;
190         num_descendants[MACHINE][SOCKET] = num_sockets;
191         num_descendants[MACHINE][NUMA] = num_numa;
192
193         /* Initialize the nodes at each level in our hierarchy. */
194         init_nodes(CORE, num_cores, 0);
195         init_nodes(CPU, num_cpus, cores_per_cpu);
196         init_nodes(SOCKET, num_sockets, cpus_per_socket);
197         init_nodes(NUMA, num_numa, sockets_per_numa);
198         init_nodes(MACHINE, 1, num_numa);
199
200         /* Initialize our table of core_distances */
201         init_core_distances();
202
203         for (int i = 0; i < num_cores; i++) {
204                 /* Remove all ll_cores from consideration for allocation. */
205                 if (is_ll_core(i)) {
206                         incref_nodes(all_pcores[i].sched_pnode);
207                         continue;
208                 }
209 #ifdef CONFIG_DISABLE_SMT
210                 /* Remove all odd cores from consideration for allocation. */
211                 if (i % 2 == 1) {
212                         incref_nodes(all_pcores[i].sched_pnode);
213                         continue;
214                 }
215 #endif /* CONFIG_DISABLE_SMT */
216                 /* Fill the idlecores array. */
217                 TAILQ_INSERT_HEAD(&idlecores, &all_pcores[i], alloc_next);
218         }
219 }
220
221 /* Initialize any data associated with allocating cores to a process. */
222 void corealloc_proc_init(struct proc *p)
223 {
224         TAILQ_INIT(&p->ksched_data.crd.alloc_me);
225         TAILQ_INIT(&p->ksched_data.crd.prov_alloc_me);
226         TAILQ_INIT(&p->ksched_data.crd.prov_not_alloc_me);
227 }
228
229 /* Returns the sum of the distances from one core to all cores in a list.
230  *
231  * This assumes cl is the allocated list, or possibly the idlecores, since it
232  * uses alloc_next. */
233 static int cumulative_core_distance(struct sched_pcore *c,
234                                     struct sched_pcore_tailq cl)
235 {
236         int d = 0;
237         struct sched_pcore *temp = NULL;
238
239         TAILQ_FOREACH(temp, &cl, alloc_next) {
240                 d += core_distance[c->core_info->core_id]
241                                   [temp->core_info->core_id];
242         }
243         return d;
244 }
245
246 /* Returns the first core in the hierarchy under node n. */
247 static struct sched_pcore *first_core_in_node(struct sched_pnode *n)
248 {
249         struct sched_pnode *first_child = n;
250
251         while (first_child->type != CORE)
252                 first_child = &first_child->children[0];
253         return first_child->sched_pcore;
254 }
255
256 /* Return the first provisioned core available. Otherwise, return NULL. */
257 static struct sched_pcore *find_first_provisioned_core(struct proc *p)
258 {
259         return TAILQ_FIRST(&(p->ksched_data.crd.prov_not_alloc_me));
260 }
261
262 /* Returns the best first core to allocate for a proc which owns no core.
263  * Return the core that is the farthest from the others's proc cores. */
264 static struct sched_pcore *find_first_core(struct proc *p)
265 {
266         struct sched_pcore *c;
267         struct sched_pnode *n;
268         struct sched_pnode *nodes;
269         struct sched_pnode *bestn;
270         int best_refcount;
271
272         /* Find the best, first provisioned core if there are any. Even if the
273          * whole machine is allocated, we still give out provisioned cores,
274          * because they will be revoked from their current owner if necessary.
275          */
276         c = find_first_provisioned_core(p);
277         if (c != NULL)
278                 return c;
279
280         /* Otherwise, if the whole machine is already allocated, there are no
281          * cores left to allocate, and we are done. */
282         bestn = &node_lookup[MACHINE][0];
283         if (bestn->refcount == num_descendants[MACHINE][CORE])
284                 return NULL;
285
286         /* Otherwise, we know at least one core is still available, so let's
287          * find the best one to allocate first. We start at NUMA, and loop
288          * through the topology to find it. */
289         for (int i = NUMA; i >= CORE; i--) {
290                 nodes = bestn->children;
291                 best_refcount = total_nodes;
292                 bestn = NULL;
293
294                 for (int j = 0; j < num_nodes[i]; j++) {
295                         n = &nodes[j];
296                         if (n->refcount == 0)
297                                 return first_core_in_node(n);
298                         if (n->refcount == num_descendants[i][CORE])
299                                 continue;
300                         if (n->refcount < best_refcount) {
301                                 best_refcount = n->refcount;
302                                 bestn = n;
303                         }
304                 }
305         }
306         return bestn->sched_pcore;
307 }
308
309 /* Return the closest core from the list of provisioned cores to cores we
310  * already own. If no cores are available we return NULL.*/
311 static struct sched_pcore *find_closest_provisioned_core(struct proc *p)
312 {
313         struct sched_pcore_tailq provisioned =
314                 p->ksched_data.crd.prov_not_alloc_me;
315         struct sched_pcore_tailq allocated = p->ksched_data.crd.alloc_me;
316         struct sched_pcore *bestc = NULL;
317         struct sched_pcore *c = NULL;
318         int bestd = 0;
319
320         TAILQ_FOREACH(c, &provisioned, prov_next) {
321                 int currd = cumulative_core_distance(c, allocated);
322
323                 if ((bestd == 0) || (currd < bestd)) {
324                         bestd = currd;
325                         bestc = c;
326                 }
327         }
328         return bestc;
329 }
330
331 /* Return the closest core from the list of idlecores to cores we already own.
332  * If no cores are available we return NULL.*/
333 static struct sched_pcore *find_closest_idle_core(struct proc *p)
334 {
335         struct sched_pcore_tailq allocated = p->ksched_data.crd.alloc_me;
336         struct sched_pcore *bestc = NULL;
337         struct sched_pcore *c = NULL;
338         int bestd = 0;
339
340         /* TODO: Add optimization to hand out core at equivalent distance if the
341          * best core found is provisioned to someone else. */
342         TAILQ_FOREACH(c, &idlecores, alloc_next) {
343                 int currd = cumulative_core_distance(c, allocated);
344
345                 if ((bestd == 0) || (currd < bestd)) {
346                         bestd = currd;
347                         bestc = c;
348                 }
349         }
350         return bestc;
351 }
352
353 /* Consider the first core provisioned to a proc by calling
354  * find_best_provisioned_core(). Then check siblings of the cores the proc
355  * already owns. Calculate for every possible node its
356  * cumulative_core_distance() (sum of the distances from this core to all of
357  * the cores the proc owns). Allocate the core that has the lowest
358  * core_distance.  This code assumes that the scheduler that uses it holds a
359  * lock for the duration of the call. */
360 static struct sched_pcore *find_closest_core(struct proc *p)
361 {
362         struct sched_pcore *bestc;
363
364         bestc = find_closest_provisioned_core(p);
365         if (bestc)
366                 return bestc;
367         return find_closest_idle_core(p);
368 }
369
370 /* Find the best core to allocate. If no cores are allocated yet, find one that
371  * is as far from the cores allocated to other processes as possible.
372  * Otherwise, find a core that is as close as possible to one of the other
373  * cores we already own. */
374 uint32_t __find_best_core_to_alloc(struct proc *p)
375 {
376         struct sched_pcore *c = NULL;
377
378         if (TAILQ_FIRST(&(p->ksched_data.crd.alloc_me)) == NULL)
379                 c = find_first_core(p);
380         else
381                 c = find_closest_core(p);
382
383         if (c == NULL)
384                 return -1;
385         return spc2pcoreid(c);
386 }
387
388 /* Track the pcore properly when it is allocated to p. This code assumes that
389  * the scheduler that uses it holds a lock for the duration of the call. */
390 void __track_core_alloc(struct proc *p, uint32_t pcoreid)
391 {
392         struct sched_pcore *spc;
393
394         assert(pcoreid < num_cores);    /* catch bugs */
395         spc = pcoreid2spc(pcoreid);
396         assert(spc->alloc_proc != p);   /* corruption or double-alloc */
397         spc->alloc_proc = p;
398         /* if the pcore is prov to them and now allocated, move lists */
399         if (spc->prov_proc == p) {
400                 TAILQ_REMOVE(&p->ksched_data.crd.prov_not_alloc_me, spc,
401                              prov_next);
402                 TAILQ_INSERT_TAIL(&p->ksched_data.crd.prov_alloc_me, spc,
403                                   prov_next);
404         }
405         /* Actually allocate the core, removing it from the idle core list. */
406         TAILQ_REMOVE(&idlecores, spc, alloc_next);
407         TAILQ_INSERT_TAIL(&p->ksched_data.crd.alloc_me, spc, alloc_next);
408         incref_nodes(spc->sched_pnode);
409 }
410
411 /* Track the pcore properly when it is deallocated from p. This code assumes
412  * that the scheduler that uses it holds a lock for the duration of the call.
413  * */
414 void __track_core_dealloc(struct proc *p, uint32_t pcoreid)
415 {
416         struct sched_pcore *spc;
417
418         assert(pcoreid < num_cores);    /* catch bugs */
419         spc = pcoreid2spc(pcoreid);
420         spc->alloc_proc = NULL;
421         /* if the pcore is prov to them and now deallocated, move lists */
422         if (spc->prov_proc == p) {
423                 TAILQ_REMOVE(&p->ksched_data.crd.prov_alloc_me, spc, prov_next);
424                 /* this is the victim list, which can be sorted so that we pick
425                  * the right victim (sort by alloc_proc reverse priority, etc).
426                  * In this case, the core isn't alloc'd by anyone, so it should
427                  * be the first victim. */
428                 TAILQ_INSERT_HEAD(&p->ksched_data.crd.prov_not_alloc_me, spc,
429                                   prov_next);
430         }
431         /* Actually dealloc the core, putting it back on the idle core list. */
432         TAILQ_REMOVE(&(p->ksched_data.crd.alloc_me), spc, alloc_next);
433         TAILQ_INSERT_HEAD(&idlecores, spc, alloc_next);
434         decref_nodes(spc->sched_pnode);
435 }
436
437 /* Bulk interface for __track_core_dealloc */
438 void __track_core_dealloc_bulk(struct proc *p, uint32_t *pc_arr,
439                                uint32_t nr_cores)
440 {
441         for (int i = 0; i < nr_cores; i++)
442                 __track_core_dealloc(p, pc_arr[i]);
443 }
444
445 /* One off function to make 'pcoreid' the next core chosen by the core
446  * allocation algorithm (so long as no provisioned cores are still idle).
447  * This code assumes that the scheduler that uses it holds a lock for the
448  * duration of the call. */
449 void __next_core_to_alloc(uint32_t pcoreid)
450 {
451         printk("%s is not supported by this core allocation policy!\n",
452                __func__);
453 }
454
455 /* One off function to sort the idle core list for debugging in the kernel
456  * monitor. This code assumes that the scheduler that uses it holds a lock
457  * for the duration of the call. */
458 void __sort_idle_cores(void)
459 {
460         printk("%s is not supported by this core allocation policy!\n",
461                __func__);
462 }
463
464 /* Print the map of idle cores that are still allocatable through our core
465  * allocation algorithm. */
466 void print_idle_core_map(void)
467 {
468         printk("Idle cores (unlocked!):\n");
469         for (int i = 0; i < num_cores; i++) {
470                 struct sched_pcore *spc_i = &all_pcores[i];
471
472                 if (spc_i->alloc_proc == NULL)
473                         printk("Core %d, prov to %d (%p)\n",
474                                spc_i->core_info->core_id,
475                                spc_i->prov_proc ? spc_i->prov_proc->pid : 0,
476                                spc_i->prov_proc);
477         }
478 }