134f51107a4c95cae5e4c9b00ef68f42d8335377
[akaros.git] / kern / src / corealloc.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 #ifndef CONFIG_DISABLE_SMT
29         for (int i = 1; i < num_cores; i++)
30                 TAILQ_INSERT_TAIL(&idlecores, pcoreid2spc(i), alloc_next);
31 #else
32         assert(!(num_cores % 2));
33         for (int i = 1; i < num_cores; i += 2)
34                 TAILQ_INSERT_TAIL(&idlecores, pcoreid2spc(i), alloc_next);
35 #endif /* CONFIG_DISABLE_SMT */
36 }
37
38 /* Find the best core to allocate to a process as dictated by the core
39  * allocation algorithm. This code assumes that the scheduler that uses it
40  * holds a lock for the duration of the call. */
41 struct sched_pcore *__find_best_core_to_alloc(struct proc *p)
42 {
43         struct sched_pcore *spc_i = NULL;
44
45         spc_i = TAILQ_FIRST(&p->ksched_data.crd.prov_not_alloc_me);
46         if (!spc_i)
47                 spc_i = TAILQ_FIRST(&idlecores);
48         return spc_i;
49 }
50
51 /* Track the pcore properly when it is allocated to p. This code assumes that
52  * the scheduler that uses it holds a lock for the duration of the call. */
53 void __track_core_alloc(struct proc *p, uint32_t pcoreid)
54 {
55         struct sched_pcore *spc;
56
57         assert(pcoreid < num_cores);    /* catch bugs */
58         spc = pcoreid2spc(pcoreid);
59         assert(spc->alloc_proc != p);   /* corruption or double-alloc */
60         spc->alloc_proc = p;
61         /* if the pcore is prov to them and now allocated, move lists */
62         if (spc->prov_proc == p) {
63                 TAILQ_REMOVE(&p->ksched_data.crd.prov_not_alloc_me, spc, prov_next);
64                 TAILQ_INSERT_TAIL(&p->ksched_data.crd.prov_alloc_me, spc, prov_next);
65         }
66         /* Actually allocate the core, removing it from the idle core list. */
67         TAILQ_REMOVE(&idlecores, spc, alloc_next);
68 }
69
70 /* Track the pcore properly when it is deallocated from p. This code assumes
71  * that the scheduler that uses it holds a lock for the duration of the call.
72  * */
73 void __track_core_dealloc(struct proc *p, uint32_t pcoreid)
74 {
75         struct sched_pcore *spc;
76
77         assert(pcoreid < num_cores);    /* catch bugs */
78         spc = pcoreid2spc(pcoreid);
79         spc->alloc_proc = 0;
80         /* if the pcore is prov to them and now deallocated, move lists */
81         if (spc->prov_proc == p) {
82                 TAILQ_REMOVE(&p->ksched_data.crd.prov_alloc_me, spc, prov_next);
83                 /* this is the victim list, which can be sorted so that we pick the
84                  * right victim (sort by alloc_proc reverse priority, etc).  In this
85                  * case, the core isn't alloc'd by anyone, so it should be the first
86                  * victim. */
87                 TAILQ_INSERT_HEAD(&p->ksched_data.crd.prov_not_alloc_me, spc,
88                                   prov_next);
89         }
90         /* Actually dealloc the core, putting it back on the idle core list. */
91         TAILQ_INSERT_TAIL(&idlecores, spc, alloc_next);
92 }
93
94 /* Bulk interface for __track_core_dealloc */
95 void __track_core_dealloc_bulk(struct proc *p, uint32_t *pc_arr,
96                                uint32_t nr_cores)
97 {
98         for (int i = 0; i < nr_cores; i++)
99                 __track_core_dealloc(p, pc_arr[i]);
100 }
101
102 /* Get an idle core from our pcore list and return its core_id. Don't
103  * consider the chosen core in the future when handing out cores to a
104  * process. This code assumes that the scheduler that uses it holds a lock
105  * for the duration of the call. This will not give out provisioned cores. */
106 int __get_any_idle_core(void)
107 {
108         struct sched_pcore *spc;
109         int ret = -1;
110
111         while ((spc = TAILQ_FIRST(&idlecores))) {
112                 /* Don't take cores that are provisioned to a process */
113                 if (spc->prov_proc)
114                         continue;
115                 assert(!spc->alloc_proc);
116                 TAILQ_REMOVE(&idlecores, spc, alloc_next);
117                 ret = spc2pcoreid(spc);
118                 break;
119         }
120         return ret;
121 }
122
123 /* Detect if a pcore is idle or not. */
124 /* TODO: if we end up using this a lot, track CG-idleness as a property of
125  * the SPC instead of doing a linear search. */
126 static bool __spc_is_idle(struct sched_pcore *spc)
127 {
128         struct sched_pcore *i;
129
130         TAILQ_FOREACH(i, &idlecores, alloc_next) {
131                 if (spc == i)
132                         return TRUE;
133         }
134         return FALSE;
135 }
136
137 /* Same as __get_any_idle_core() except for a specific core id. */
138 int __get_specific_idle_core(int coreid)
139 {
140         struct sched_pcore *spc = pcoreid2spc(coreid);
141         int ret = -1;
142
143         assert((coreid >= 0) && (coreid < num_cores));
144         if (__spc_is_idle(pcoreid2spc(coreid)) && !spc->prov_proc) {
145                 assert(!spc->alloc_proc);
146                 TAILQ_REMOVE(&idlecores, spc, alloc_next);
147                 ret = coreid;
148         }
149         return ret;
150 }
151
152 /* Reinsert a core obtained via __get_any_idle_core() or
153  * __get_specific_idle_core() back into the idlecore map. This code assumes
154  * that the scheduler that uses it holds a lock for the duration of the call.
155  * This will not give out provisioned cores. */
156 void __put_idle_core(int coreid)
157 {
158         struct sched_pcore *spc = pcoreid2spc(coreid);
159
160         assert((coreid >= 0) && (coreid < num_cores));
161         TAILQ_INSERT_TAIL(&idlecores, spc, alloc_next);
162 }
163
164 /* One off function to make 'pcoreid' the next core chosen by the core
165  * allocation algorithm (so long as no provisioned cores are still idle).
166  * This code assumes that the scheduler that uses it holds a lock for the
167  * duration of the call. */
168 void __next_core_to_alloc(uint32_t pcoreid)
169 {
170         struct sched_pcore *spc_i;
171         bool match = FALSE;
172
173         TAILQ_FOREACH(spc_i, &idlecores, alloc_next) {
174                 if (spc2pcoreid(spc_i) == pcoreid) {
175                         match = TRUE;
176                         break;
177                 }
178         }
179         if (match) {
180                 TAILQ_REMOVE(&idlecores, spc_i, alloc_next);
181                 TAILQ_INSERT_HEAD(&idlecores, spc_i, alloc_next);
182                 printk("Pcore %d will be given out next (from the idles)\n", pcoreid);
183         }
184 }
185
186 /* One off function to sort the idle core list for debugging in the kernel
187  * monitor. This code assumes that the scheduler that uses it holds a lock
188  * for the duration of the call. */
189 void __sort_idle_cores(void)
190 {
191         struct sched_pcore *spc_i, *spc_j, *temp;
192         struct sched_pcore_tailq sorter = TAILQ_HEAD_INITIALIZER(sorter);
193         bool added;
194
195         TAILQ_CONCAT(&sorter, &idlecores, alloc_next);
196         TAILQ_FOREACH_SAFE(spc_i, &sorter, alloc_next, temp) {
197                 TAILQ_REMOVE(&sorter, spc_i, alloc_next);
198                 added = FALSE;
199                 /* don't need foreach_safe since we break after we muck with the list */
200                 TAILQ_FOREACH(spc_j, &idlecores, alloc_next) {
201                         if (spc_i < spc_j) {
202                                 TAILQ_INSERT_BEFORE(spc_j, spc_i, alloc_next);
203                                 added = TRUE;
204                                 break;
205                         }
206                 }
207                 if (!added)
208                         TAILQ_INSERT_TAIL(&idlecores, spc_i, alloc_next);
209         }
210 }