9ns: Add fs_files and tree_files
[akaros.git] / kern / src / corealloc_fcfs.c
1 /* Copyright (c) 2009, 2012, 2015 The Regents of the University of California
2  * Barret Rhoden <brho@cs.berkeley.edu>
3  * Valmon Leymarie <leymariv@berkeley.edu>
4  * Kevin Klues <klueska@cs.berkeley.edu>
5  * See LICENSE for details.
6  */
7
8 #include <arch/topology.h>
9 #include <sys/queue.h>
10 #include <env.h>
11 #include <corerequest.h>
12 #include <kmalloc.h>
13
14 /* The pcores in the system. (array gets alloced in init()).  */
15 struct sched_pcore *all_pcores;
16
17 /* TAILQ of all unallocated, idle (CG) cores */
18 struct sched_pcore_tailq idlecores = TAILQ_HEAD_INITIALIZER(idlecores);
19
20 /* Initialize any data assocaited with doing core allocation. */
21 void corealloc_init(void)
22 {
23         /* Allocate all of our pcores. */
24         all_pcores = kzmalloc(sizeof(struct sched_pcore) * num_cores, 0);
25         /* init the idlecore list.  if they turned off hyperthreading, give them the
26          * odds from 1..max-1.  otherwise, give them everything by 0 (default mgmt
27          * core).  TODO: (CG/LL) better LL/CG mgmt */
28         for (int i = 0; i < num_cores; i++) {
29                 if (is_ll_core(i))
30                         continue;
31 #ifdef CONFIG_DISABLE_SMT
32                 /* Remove all odd cores from consideration for allocation. */
33                 if (i % 2 == 1)
34                         continue;
35 #endif /* CONFIG_DISABLE_SMT */
36                 TAILQ_INSERT_TAIL(&idlecores, pcoreid2spc(i), alloc_next);
37         }
38 }
39
40 /* Initialize any data associated with allocating cores to a process. */
41 void corealloc_proc_init(struct proc *p)
42 {
43         TAILQ_INIT(&p->ksched_data.crd.prov_alloc_me);
44         TAILQ_INIT(&p->ksched_data.crd.prov_not_alloc_me);
45 }
46
47 /* Find the best core to allocate to a process as dictated by the core
48  * allocation algorithm. This code assumes that the scheduler that uses it
49  * holds a lock for the duration of the call. */
50 uint32_t __find_best_core_to_alloc(struct proc *p)
51 {
52         struct sched_pcore *spc_i = NULL;
53
54         spc_i = TAILQ_FIRST(&p->ksched_data.crd.prov_not_alloc_me);
55         if (!spc_i)
56                 spc_i = TAILQ_FIRST(&idlecores);
57         if (!spc_i)
58                 return -1;
59         return spc2pcoreid(spc_i);
60 }
61
62 /* Track the pcore properly when it is allocated to p. This code assumes that
63  * the scheduler that uses it holds a lock for the duration of the call. */
64 void __track_core_alloc(struct proc *p, uint32_t pcoreid)
65 {
66         struct sched_pcore *spc;
67
68         assert(pcoreid < num_cores);    /* catch bugs */
69         spc = pcoreid2spc(pcoreid);
70         assert(spc->alloc_proc != p);   /* corruption or double-alloc */
71         spc->alloc_proc = p;
72         /* if the pcore is prov to them and now allocated, move lists */
73         if (spc->prov_proc == p) {
74                 TAILQ_REMOVE(&p->ksched_data.crd.prov_not_alloc_me, spc, prov_next);
75                 TAILQ_INSERT_TAIL(&p->ksched_data.crd.prov_alloc_me, spc, prov_next);
76         }
77         /* Actually allocate the core, removing it from the idle core list. */
78         TAILQ_REMOVE(&idlecores, spc, alloc_next);
79 }
80
81 /* Track the pcore properly when it is deallocated from p. This code assumes
82  * that the scheduler that uses it holds a lock for the duration of the call.
83  * */
84 void __track_core_dealloc(struct proc *p, uint32_t pcoreid)
85 {
86         struct sched_pcore *spc;
87
88         assert(pcoreid < num_cores);    /* catch bugs */
89         spc = pcoreid2spc(pcoreid);
90         spc->alloc_proc = 0;
91         /* if the pcore is prov to them and now deallocated, move lists */
92         if (spc->prov_proc == p) {
93                 TAILQ_REMOVE(&p->ksched_data.crd.prov_alloc_me, spc, prov_next);
94                 /* this is the victim list, which can be sorted so that we pick the
95                  * right victim (sort by alloc_proc reverse priority, etc).  In this
96                  * case, the core isn't alloc'd by anyone, so it should be the first
97                  * victim. */
98                 TAILQ_INSERT_HEAD(&p->ksched_data.crd.prov_not_alloc_me, spc,
99                                   prov_next);
100         }
101         /* Actually dealloc the core, putting it back on the idle core list. */
102         TAILQ_INSERT_TAIL(&idlecores, spc, alloc_next);
103 }
104
105 /* Bulk interface for __track_core_dealloc */
106 void __track_core_dealloc_bulk(struct proc *p, uint32_t *pc_arr,
107                                uint32_t nr_cores)
108 {
109         for (int i = 0; i < nr_cores; i++)
110                 __track_core_dealloc(p, pc_arr[i]);
111 }
112
113 /* One off function to make 'pcoreid' the next core chosen by the core
114  * allocation algorithm (so long as no provisioned cores are still idle).
115  * This code assumes that the scheduler that uses it holds a lock for the
116  * duration of the call. */
117 void __next_core_to_alloc(uint32_t pcoreid)
118 {
119         struct sched_pcore *spc_i;
120         bool match = FALSE;
121
122         TAILQ_FOREACH(spc_i, &idlecores, alloc_next) {
123                 if (spc2pcoreid(spc_i) == pcoreid) {
124                         match = TRUE;
125                         break;
126                 }
127         }
128         if (match) {
129                 TAILQ_REMOVE(&idlecores, spc_i, alloc_next);
130                 TAILQ_INSERT_HEAD(&idlecores, spc_i, alloc_next);
131                 printk("Pcore %d will be given out next (from the idles)\n", pcoreid);
132         }
133 }
134
135 /* One off function to sort the idle core list for debugging in the kernel
136  * monitor. This code assumes that the scheduler that uses it holds a lock
137  * for the duration of the call. */
138 void __sort_idle_cores(void)
139 {
140         struct sched_pcore *spc_i, *spc_j, *temp;
141         struct sched_pcore_tailq sorter = TAILQ_HEAD_INITIALIZER(sorter);
142         bool added;
143
144         TAILQ_CONCAT(&sorter, &idlecores, alloc_next);
145         TAILQ_FOREACH_SAFE(spc_i, &sorter, alloc_next, temp) {
146                 TAILQ_REMOVE(&sorter, spc_i, alloc_next);
147                 added = FALSE;
148                 /* don't need foreach_safe since we break after we muck with the list */
149                 TAILQ_FOREACH(spc_j, &idlecores, alloc_next) {
150                         if (spc_i < spc_j) {
151                                 TAILQ_INSERT_BEFORE(spc_j, spc_i, alloc_next);
152                                 added = TRUE;
153                                 break;
154                         }
155                 }
156                 if (!added)
157                         TAILQ_INSERT_TAIL(&idlecores, spc_i, alloc_next);
158         }
159 }
160
161 /* Print the map of idle cores that are still allocatable through our core
162  * allocation algorithm. */
163 void print_idle_core_map(void)
164 {
165         struct sched_pcore *spc_i;
166         /* not locking, so we can look at this without deadlocking. */
167         printk("Idle cores (unlocked!):\n");
168         TAILQ_FOREACH(spc_i, &idlecores, alloc_next)
169                 printk("Core %d, prov to %d (%p)\n", spc2pcoreid(spc_i),
170                        spc_i->prov_proc ? spc_i->prov_proc->pid : 0, spc_i->prov_proc);
171 }