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