Post-and-poke style sync for the ksched
[akaros.git] / kern / src / schedule.c
1 /* Copyright (c) 2009, 2012 The Regents of the University of California
2  * Barret Rhoden <brho@cs.berkeley.edu>
3  * See LICENSE for details.
4  *
5  * Scheduling and dispatching. */
6
7 #ifdef __SHARC__
8 #pragma nosharc
9 #endif
10
11 #include <schedule.h>
12 #include <process.h>
13 #include <monitor.h>
14 #include <stdio.h>
15 #include <assert.h>
16 #include <atomic.h>
17 #include <smp.h>
18 #include <manager.h>
19 #include <alarm.h>
20 #include <sys/queue.h>
21 #include <kmalloc.h>
22
23 /* Process Lists.  'unrunnable' is a holding list for SCPs that are running or
24  * waiting or otherwise not considered for sched decisions. */
25 struct proc_list unrunnable_scps = TAILQ_HEAD_INITIALIZER(unrunnable_scps);
26 struct proc_list runnable_scps = TAILQ_HEAD_INITIALIZER(runnable_scps);
27 struct proc_list all_mcps = TAILQ_HEAD_INITIALIZER(all_mcps);
28
29 /* The pcores in the system.  (array gets alloced in init()).  */
30 struct sched_pcore *all_pcores;
31
32 /* TAILQ of all unallocated, idle (CG) cores */
33 struct sched_pcore_tailq idlecores = TAILQ_HEAD_INITIALIZER(idlecores);
34
35 /* Helper, defined below */
36 static void __core_request(struct proc *p);
37 static void __put_idle_cores(struct proc *p, uint32_t *pc_arr, uint32_t num);
38 static void add_to_list(struct proc *p, struct proc_list *list);
39 static void remove_from_list(struct proc *p, struct proc_list *list);
40 static void switch_lists(struct proc *p, struct proc_list *old,
41                          struct proc_list *new);
42 static uint32_t spc2pcoreid(struct sched_pcore *spc);
43 static struct sched_pcore *pcoreid2spc(uint32_t pcoreid);
44 static bool is_ll_core(uint32_t pcoreid);
45 static void __prov_track_alloc(struct proc *p, uint32_t pcoreid);
46 static void __prov_track_dealloc(struct proc *p, uint32_t pcoreid);
47 static void __prov_track_dealloc_bulk(struct proc *p, uint32_t *pc_arr,
48                                       uint32_t nr_cores);
49 static void __run_mcp_ksched(void *arg);        /* don't call directly */
50
51 /* Locks / sync tools */
52
53 /* poke-style ksched - ensures the MCP ksched only runs once at a time.  since
54  * only one mcp ksched runs at a time, while this is set, the ksched knows no
55  * cores are being allocated by other code (though they could be dealloc, due to
56  * yield). 
57  *
58  * The main value to this sync method is to make the 'make sure the ksched runs
59  * only once at a time and that it actually runs' invariant/desire wait-free, so
60  * that it can be called anywhere (deep event code, etc).
61  *
62  * As the ksched gets smarter, we'll probably embedd this poker in a bigger
63  * struct that can handle the posting of different types of work. */
64 struct poke_tracker ksched_poker = {0, 0, __run_mcp_ksched};
65
66 /* this 'big ksched lock' protects a bunch of things, which i may make fine
67  * grained: */
68 /* - protects the integrity of proc tailqs/structures, as well as the membership
69  * of a proc on those lists.  proc lifetime within the ksched but outside this
70  * lock is protected by the proc kref. */
71 //spinlock_t proclist_lock = SPINLOCK_INITIALIZER; /* subsumed by bksl */
72 /* - protects the provisioning assignment, membership of sched_pcores in
73  * provision lists, and the integrity of all prov lists (the lists of each
74  * proc).  does NOT protect spc->alloc_proc. */
75 //spinlock_t prov_lock = SPINLOCK_INITIALIZER;
76 /* - protects allocation structures: spc->alloc_proc, the integrity and
77  * membership of the idelcores tailq. */
78 //spinlock_t alloc_lock = SPINLOCK_INITIALIZER;
79 spinlock_t sched_lock = SPINLOCK_INITIALIZER;
80
81 /* Alarm struct, for our example 'timer tick' */
82 struct alarm_waiter ksched_waiter;
83
84 #define TIMER_TICK_USEC 10000   /* 10msec */
85
86 /* Helper: Sets up a timer tick on the calling core to go off 10 msec from now.
87  * This assumes the calling core is an LL core, etc. */
88 static void set_ksched_alarm(void)
89 {
90         set_awaiter_rel(&ksched_waiter, TIMER_TICK_USEC);
91         set_alarm(&per_cpu_info[core_id()].tchain, &ksched_waiter);
92 }
93
94 /* Kmsg, to run the scheduler tick (not in interrupt context) and reset the
95  * alarm.  Note that interrupts will be disabled, but this is not the same as
96  * interrupt context.  We're a routine kmsg, which means the core is in a
97  * quiescent state. */
98 static void __ksched_tick(struct trapframe *tf, uint32_t srcid, long a0,
99                           long a1, long a2)
100 {
101         /* TODO: imagine doing some accounting here */
102         schedule();
103         /* Set our alarm to go off, incrementing from our last tick (instead of
104          * setting it relative to now, since some time has passed since the alarm
105          * first went off.  Note, this may be now or in the past! */
106         set_awaiter_inc(&ksched_waiter, TIMER_TICK_USEC);
107         set_alarm(&per_cpu_info[core_id()].tchain, &ksched_waiter);
108 }
109
110 /* Interrupt/alarm handler: tells our core to run the scheduler (out of
111  * interrupt context). */
112 static void __kalarm(struct alarm_waiter *waiter)
113 {
114         send_kernel_message(core_id(), __ksched_tick, 0, 0, 0, KMSG_ROUTINE);
115 }
116
117 void schedule_init(void)
118 {
119         spin_lock(&sched_lock);
120         /* init provisioning stuff */
121         all_pcores = kmalloc(sizeof(struct sched_pcore) * num_cpus, 0);
122         memset(all_pcores, 0, sizeof(struct sched_pcore) * num_cpus);
123         assert(!core_id());             /* want the alarm on core0 for now */
124         init_awaiter(&ksched_waiter, __kalarm);
125         set_ksched_alarm();
126         /* init the idlecore list.  if they turned off hyperthreading, give them the
127          * odds from 1..max-1.  otherwise, give them everything by 0 (default mgmt
128          * core).  TODO: (CG/LL) better LL/CG mgmt */
129 #ifndef __CONFIG_DISABLE_SMT__
130         for (int i = 1; i < num_cpus; i++)
131                 TAILQ_INSERT_TAIL(&idlecores, pcoreid2spc(i), alloc_next);
132 #else
133         assert(!(num_cpus % 2));
134         for (int i = 1; i < num_cpus; i += 2)
135                 TAILQ_INSERT_TAIL(&idlecores, pcoreid2spc(i), alloc_next);
136 #endif /* __CONFIG_DISABLE_SMT__ */
137 #ifdef __CONFIG_ARSC_SERVER__
138         struct sched_pcore *a_core = TAILQ_FIRST(&idlecores);
139         assert(a_core);
140         TAILQ_REMOVE(&idlecores, a_core, alloc_next);
141         send_kernel_message(spc2pcoreid(a_core), (amr_t)arsc_server, 0, 0, 0,
142                             KMSG_ROUTINE);
143         warn("Using core %d for the ARSCs - there are probably issues with this.",
144              spc2pcoreid(a_core));
145 #endif /* __CONFIG_ARSC_SERVER__ */
146         spin_unlock(&sched_lock);
147         return;
148 }
149
150 /* Round-robins on whatever list it's on */
151 static void add_to_list(struct proc *p, struct proc_list *new)
152 {
153         TAILQ_INSERT_TAIL(new, p, ksched_data.proc_link);
154         p->ksched_data.cur_list = new;
155 }
156
157 static void remove_from_list(struct proc *p, struct proc_list *old)
158 {
159         assert(p->ksched_data.cur_list == old);
160         TAILQ_REMOVE(old, p, ksched_data.proc_link);
161 }
162
163 static void switch_lists(struct proc *p, struct proc_list *old,
164                          struct proc_list *new)
165 {
166         remove_from_list(p, old);
167         add_to_list(p, new);
168 }
169
170 static void __remove_from_any_list(struct proc *p)
171 {
172         if (p->ksched_data.cur_list)
173                 TAILQ_REMOVE(p->ksched_data.cur_list, p, ksched_data.proc_link);
174 }
175
176 /* Removes from whatever list p is on */
177 static void remove_from_any_list(struct proc *p)
178 {
179         assert(p->ksched_data.cur_list);
180         TAILQ_REMOVE(p->ksched_data.cur_list, p, ksched_data.proc_link);
181 }
182
183 void register_proc(struct proc *p)
184 {
185         /* one ref for the proc's existence, cradle-to-grave */
186         proc_incref(p, 1);      /* need at least this OR the 'one for existing' */
187         spin_lock(&sched_lock);
188         TAILQ_INIT(&p->ksched_data.prov_alloc_me);
189         TAILQ_INIT(&p->ksched_data.prov_not_alloc_me);
190         add_to_list(p, &unrunnable_scps);
191         spin_unlock(&sched_lock);
192 }
193
194 /* Returns 0 if it succeeded, an error code otherwise. */
195 int proc_change_to_m(struct proc *p)
196 {
197         int retval;
198         spin_lock(&sched_lock);
199         /* Should only be necessary to lock around the change_to_m call.  It's
200          * definitely necessary to hold the sched lock the whole time - need to
201          * atomically change the proc's state and have the ksched take action (and
202          * not squeeze a proc_destroy in there or something). */
203         spin_lock(&p->proc_lock);
204         retval = __proc_change_to_m(p);
205         spin_unlock(&p->proc_lock);
206         if (retval) {
207                 /* Failed for some reason. */
208                 spin_unlock(&sched_lock);
209                 return retval;
210         }
211         /* Catch user bugs */
212         if (!p->procdata->res_req[RES_CORES].amt_wanted) {
213                 printk("[kernel] process needs to specify amt_wanted\n");
214                 p->procdata->res_req[RES_CORES].amt_wanted = 1;
215         }
216         /* For now, this should only ever be called on an unrunnable.  It's
217          * probably a bug, at this stage in development, to do o/w. */
218         remove_from_list(p, &unrunnable_scps);
219         //remove_from_any_list(p);      /* ^^ instead of this */
220         add_to_list(p, &all_mcps);
221         spin_unlock(&sched_lock);
222         //poke_ksched(p, RES_CORES);
223         return retval;
224 }
225
226 /* Makes sure p is runnable.  Callers may spam this, so it needs to handle
227  * repeated calls for the same event.  Callers include event delivery, SCP
228  * yield, and new SCPs.  Most every scheduler should do something like this -
229  * grab whatever lock you have, then call the proc helper. */
230 void proc_wakeup(struct proc *p)
231 {
232         /* catch current shitty deadlock... */
233         assert(!per_cpu_info[core_id()].lock_depth);
234         spin_lock(&sched_lock);
235         /* will trigger one of the __sched_.cp_wakeup()s */
236         __proc_wakeup(p);
237         spin_unlock(&sched_lock);
238 }
239
240 static uint32_t spc2pcoreid(struct sched_pcore *spc)
241 {
242         return spc - all_pcores;
243 }
244
245 static struct sched_pcore *pcoreid2spc(uint32_t pcoreid)
246 {
247         return &all_pcores[pcoreid];
248 }
249
250 /* Helper for proc destroy: unprovisions any pcores for the given list */
251 static void unprov_pcore_list(struct sched_pcore_tailq *list_head)
252 {
253         struct sched_pcore *spc_i;
254         /* We can leave them connected within the tailq, since the scps don't have a
255          * default list (if they aren't on a proc's list, then we don't care about
256          * them), and since the INSERTs don't care what list you were on before
257          * (chummy with the implementation).  Pretty sure this is right.  If there's
258          * suspected list corruption, be safer here. */
259         TAILQ_FOREACH(spc_i, list_head, prov_next)
260                 spc_i->prov_proc = 0;
261         TAILQ_INIT(list_head);
262 }
263
264 /* Destroys the given process.  This may be called from another process, a light
265  * kernel thread (no real process context), asynchronously/cross-core, or from
266  * the process on its own core.
267  *
268  * An external, edible ref is passed in.  when we return and they decref,
269  * __proc_free will be called */
270 void proc_destroy(struct proc *p)
271 {
272         uint32_t nr_cores_revoked = 0;
273         spin_lock(&sched_lock);
274         spin_lock(&p->proc_lock);
275         /* storage for pc_arr is alloced at decl, which is after grabbing the lock*/
276         uint32_t pc_arr[p->procinfo->num_vcores];
277         /* If this returns true, it means we successfully destroyed the proc */
278         if (__proc_destroy(p, pc_arr, &nr_cores_revoked)) {
279                 /* Do our cleanup.  note that proc_free won't run since we have an
280                  * external reference, passed in */
281                 /* Unprovision any cores.  Note this is different than track_dealloc.
282                  * The latter does bookkeeping when an allocation changes.  This is a
283                  * bulk *provisioning* change. */
284                 unprov_pcore_list(&p->ksched_data.prov_alloc_me);
285                 unprov_pcore_list(&p->ksched_data.prov_not_alloc_me);
286                 /* Remove from whatever list we are on */
287                 remove_from_any_list(p);
288                 /* Drop the cradle-to-the-grave reference, jet-li */
289                 proc_decref(p);
290                 if (nr_cores_revoked) {
291                         __put_idle_cores(p, pc_arr, nr_cores_revoked);
292                         __prov_track_dealloc_bulk(p, pc_arr, nr_cores_revoked);
293                 }
294         }
295         spin_unlock(&p->proc_lock);
296         spin_unlock(&sched_lock);
297 }
298
299 /* mgmt/LL cores should call this to schedule the calling core and give it to an
300  * SCP.  will also prune the dead SCPs from the list.  hold the lock before
301  * calling.  returns TRUE if it scheduled a proc. */
302 static bool __schedule_scp(void)
303 {
304         struct proc *p;
305         uint32_t pcoreid = core_id();
306         struct per_cpu_info *pcpui = &per_cpu_info[pcoreid];
307         int8_t state = 0;
308         /* if there are any runnables, run them here and put any currently running
309          * SCP on the tail of the runnable queue. */
310         if ((p = TAILQ_FIRST(&runnable_scps))) {
311                 /* protect owning proc, cur_tf, etc.  note this nests with the
312                  * calls in proc_yield_s */
313                 disable_irqsave(&state);
314                 /* someone is currently running, dequeue them */
315                 if (pcpui->owning_proc) {
316                         printd("Descheduled %d in favor of %d\n", pcpui->owning_proc->pid,
317                                p->pid);
318                         /* locking just to be safe */
319                         spin_lock(&p->proc_lock);
320                         __proc_set_state(pcpui->owning_proc, PROC_RUNNABLE_S);
321                         __proc_save_context_s(pcpui->owning_proc, pcpui->cur_tf);
322                         spin_unlock(&p->proc_lock);
323                         /* round-robin the SCPs (inserts at the end of the queue) */
324                         switch_lists(pcpui->owning_proc, &unrunnable_scps, &runnable_scps);
325                         clear_owning_proc(pcoreid);
326                         /* Note we abandon core.  It's not strictly necessary.  If
327                          * we didn't, the TLB would still be loaded with the old
328                          * one, til we proc_run_s, and the various paths in
329                          * proc_run_s would pick it up.  This way is a bit safer for
330                          * future changes, but has an extra (empty) TLB flush.  */
331                         abandon_core();
332                 } 
333                 /* Run the new proc */
334                 switch_lists(p, &runnable_scps, &unrunnable_scps);
335                 printd("PID of the SCP i'm running: %d\n", p->pid);
336                 proc_run_s(p);  /* gives it core we're running on */
337                 enable_irqsave(&state);
338                 return TRUE;
339         }
340         return FALSE;
341 }
342
343 /* Actual work of the MCP kscheduler.  if we were called by poke_ksched, *arg
344  * might be the process who wanted special service.  this would be the case if
345  * we weren't already running the ksched.  Sort of a ghetto way to "post work",
346  * such that it's an optimization. */
347 static void __run_mcp_ksched(void *arg)
348 {
349         struct proc *p, *temp;
350         /* TODO: don't hold the sched_lock the whole time */
351         spin_lock(&sched_lock);
352         /* trivially try to handle the needs of all our MCPS.  smarter schedulers
353          * would do something other than FCFS */
354         TAILQ_FOREACH_SAFE(p, &all_mcps, ksched_data.proc_link, temp) {
355                 printd("Ksched has MCP %08p (%d)\n", p, p->pid);
356                 /* TODO: might use amt_wanted as a proxy.  right now, they have
357                  * amt_wanted == 1, even though they are waiting.
358                  * TODO: this is RACY too - just like with DYING. */
359                 if (p->state == PROC_WAITING)
360                         continue;
361                 __core_request(p);
362         }
363         spin_unlock(&sched_lock);
364 }
365
366 /* Something has changed, and for whatever reason the scheduler should
367  * reevaluate things. 
368  *
369  * Don't call this from interrupt context (grabs proclocks). */
370 void schedule(void)
371 {
372         /* MCP scheduling: post work, then poke.  for now, i just want the func to
373          * run again, so merely a poke is sufficient. */
374         poke(&ksched_poker, 0);
375         if (management_core()) {
376                 spin_lock(&sched_lock);
377                 __schedule_scp();
378                 spin_unlock(&sched_lock);
379         }
380 }
381
382 /* A process is asking the ksched to look at its resource desires.  The
383  * scheduler is free to ignore this, for its own reasons, so long as it
384  * eventually gets around to looking at resource desires. */
385 void poke_ksched(struct proc *p, int res_type)
386 {
387         /* ignoring res_type for now.  could post that if we wanted (would need some
388          * other structs/flags) */
389         if (!__proc_is_mcp(p))
390                 return;
391         poke(&ksched_poker, p);
392 }
393
394 /* ksched callbacks.  p just woke up, is unlocked, and the ksched lock is held */
395 void __sched_mcp_wakeup(struct proc *p)
396 {
397         /* could try and prioritize p somehow (move it to the front of the list) */
398         poke(&ksched_poker, p);
399 }
400
401 /* ksched callbacks.  p just woke up, is unlocked, and the ksched lock is held */
402 void __sched_scp_wakeup(struct proc *p)
403 {
404         /* might not be on a list if it is new.  o/w, it should be unrunnable */
405         __remove_from_any_list(p);
406         add_to_list(p, &runnable_scps);
407 }
408
409 /* The calling cpu/core has nothing to do and plans to idle/halt.  This is an
410  * opportunity to pick the nature of that halting (low power state, etc), or
411  * provide some other work (_Ss on LL cores).  Note that interrupts are
412  * disabled, and if you return, the core will cpu_halt(). */
413 void cpu_bored(void)
414 {
415         bool new_proc = FALSE;
416         if (!management_core())
417                 return;
418         spin_lock(&sched_lock);
419         new_proc = __schedule_scp();
420         spin_unlock(&sched_lock);
421         /* if we just scheduled a proc, we need to manually restart it, instead of
422          * returning.  if we return, the core will halt. */
423         if (new_proc) {
424                 proc_restartcore();
425                 assert(0);
426         }
427         /* Could drop into the monitor if there are no processes at all.  For now,
428          * the 'call of the giraffe' suffices. */
429 }
430
431 /* Externally called function to return a core to the ksched, which tracks it as
432  * idle and deallocated from p.
433  *
434  * This also is a trigger, telling us we have more cores.  We could/should make
435  * a scheduling decision (or at least plan to). */
436 void put_idle_core(struct proc *p, uint32_t coreid)
437 {
438         struct sched_pcore *spc = pcoreid2spc(coreid);
439         spin_lock(&sched_lock);
440         /* ignore_next_idle gets set if the ksched notices a core is not allocated
441          * before put_idle gets called.  This can happen if the proc yielded the
442          * core while the ksched is holding its lock (protecting lists), and the
443          * proc is spinning on the lock in this function, trying to give it back.
444          * When this happens, the core has already been 'given back', so we ignore
445          * the signal.  We're using a count instead of a bool for cases where this
446          * stacks (would require a change in provisioning, so it shouldn't happen
447          * for now). */
448         if (spc->ignore_next_idle) {
449                 spc->ignore_next_idle--;
450         } else {
451                 TAILQ_INSERT_TAIL(&idlecores, spc, alloc_next);
452                 __prov_track_dealloc(p, coreid);
453         }
454         spin_unlock(&sched_lock);
455 }
456
457 /* Helper for put_idle and core_req.  Note this does not track_dealloc, but it
458  * does handle ignore_next.  When we get rid of / revise proc_preempt_all and
459  * put_idle_cores, we can get rid of this.  (the ksched will never need it -
460  * only external callers). */
461 static void __put_idle_cores(struct proc *p, uint32_t *pc_arr, uint32_t num)
462 {
463         struct sched_pcore *spc_i;
464         for (int i = 0; i < num; i++) {
465                 spc_i = pcoreid2spc(pc_arr[i]);
466                 if (spc_i->ignore_next_idle)
467                         spc_i->ignore_next_idle--;
468                 else
469                         TAILQ_INSERT_TAIL(&idlecores, spc_i, alloc_next);
470         }
471 }
472
473 /* External interface for put_idle.  Note this one also calls track_dealloc,
474  * which the internal version does not. */
475 void put_idle_cores(struct proc *p, uint32_t *pc_arr, uint32_t num)
476 {
477         spin_lock(&sched_lock);
478         /* TODO: when we revise this func, look at __put_idle */
479         __put_idle_cores(p, pc_arr, num);
480         __prov_track_dealloc_bulk(p, pc_arr, num);
481         spin_unlock(&sched_lock);
482         /* could trigger a sched decision here */
483 }
484
485 /* Available resources changed (plus or minus).  Some parts of the kernel may
486  * call this if a particular resource that is 'quantity-based' changes.  Things
487  * like available RAM to processes, bandwidth, etc.  Cores would probably be
488  * inappropriate, since we need to know which specific core is now free. */
489 void avail_res_changed(int res_type, long change)
490 {
491         printk("[kernel] ksched doesn't track any resources yet!\n");
492 }
493
494 /* Normally it'll be the max number of CG cores ever */
495 uint32_t max_vcores(struct proc *p)
496 {
497 /* TODO: (CG/LL) */
498 #ifdef __CONFIG_DISABLE_SMT__
499         return num_cpus >> 1;
500 #else
501         return num_cpus - 1;    /* reserving core 0 */
502 #endif /* __CONFIG_DISABLE_SMT__ */
503 }
504
505 /* This deals with a request for more cores.  The request is already stored in
506  * the proc's amt_wanted (it is compared to amt_granted). */
507 static void __core_request(struct proc *p)
508 {
509         uint32_t nr_to_grant = 0, amt_wanted, amt_granted, amt_needed;
510         uint32_t corelist[num_cpus];
511         struct sched_pcore *spc_i, *temp;
512
513         amt_wanted = p->procdata->res_req[RES_CORES].amt_wanted;
514         /* Help them out - if they ask for something impossible, give them 1 so they
515          * can make some progress. (this is racy). */
516         if (amt_wanted > p->procinfo->max_vcores) {
517                 p->procdata->res_req[RES_CORES].amt_wanted = 1;
518                 amt_wanted = 1;
519         }
520         /* amt_granted is racy - they could be *yielding*, but currently they can't
521          * be getting any new cores.  this is okay - we won't accidentally give them
522          * more cores than they *ever* wanted (which could crash them), but they
523          * might not get fully satisfied this time.  next core_req will get them */
524         amt_granted = p->procinfo->res_grant[RES_CORES];
525         /* Do not do an assert like this: it could fail (yield in progress): */
526         //assert(amt_granted == p->procinfo->num_vcores);
527         /* if they are satisfied, we're done.  There's a slight chance they have
528          * cores, but they aren't running (sched gave them cores while they were
529          * yielding, and now we see them on the run queue). */
530         if (amt_wanted <= amt_granted)
531                 return;
532         amt_needed = amt_wanted - amt_granted;
533         /* Try to give out provisioned cores.  the not_alloc_me list is the victim
534          * list.  Side note: if we want to warn, then we can't deal with this proc's
535          * prov'd cores until we wait til the alarm goes off.  would need to put all
536          * alarmed cores on a list and wait til the alarm goes off to do the full
537          * preempt.  and when those cores come in voluntarily, we'd need to know to
538          * give them to this proc. */
539         TAILQ_FOREACH_SAFE(spc_i, &p->ksched_data.prov_not_alloc_me, prov_next,
540                            temp) {
541                 if (nr_to_grant == amt_needed)
542                         break;
543                 if (spc_i->alloc_proc) {
544                         assert(spc_i->alloc_proc != spc_i->prov_proc);
545                         /* someone else has this proc's pcore, so we need to try to preempt.
546                          * sending no warning time for now - just an immediate preempt. */
547                         if (!proc_preempt_core(spc_i->alloc_proc, spc2pcoreid(spc_i), 0)) {
548                                 /* core is unmapped, they must have just yielded and are
549                                  * spinning in put_idle */
550                                 spc_i->ignore_next_idle++;
551                                 if (spc_i->ignore_next_idle > 100)
552                                         warn("Unusually high ignore_next_idle %d",
553                                              spc_i->ignore_next_idle);
554                         }
555                         /* Note that we do NOT want to __prov_track_dealloc.  Instead, we
556                          * just leave it on its list (which we'll change later), and clear
557                          * alloc_proc (which is what __prov_track_dealloc does). */
558                         spc_i->alloc_proc = 0;
559                 } else {
560                         /* must be an idle core, rip it off that list */
561                         TAILQ_REMOVE(&idlecores, spc_i, alloc_next);
562                 }
563                 /* At this point, we have the core, ready to try to give it to the proc.
564                  * We'll give them via a list, which is better for the proc mgmt code
565                  * (when going from runnable to running. */
566                 corelist[nr_to_grant] = spc2pcoreid(spc_i);
567                 nr_to_grant++;
568         }
569         /* Try to get cores from the idle list that aren't prov to me (FCFS) */
570         TAILQ_FOREACH_SAFE(spc_i, &idlecores, alloc_next, temp) {
571                 if (nr_to_grant == amt_needed)
572                         break;
573                 TAILQ_REMOVE(&idlecores, spc_i, alloc_next);
574                 corelist[nr_to_grant] = spc2pcoreid(spc_i);
575                 nr_to_grant++;
576         }
577         /* Now, actually give them out */
578         if (nr_to_grant) {
579                 /* give them the cores.  this will start up the extras if RUNNING_M. */
580                 spin_lock(&p->proc_lock);
581                 /* if they fail, it is because they are WAITING or DYING.  we could give
582                  * the cores to another proc or whatever.  for the current type of
583                  * ksched, we'll just put them back on the pile and return.  Note, the
584                  * ksched could check the states after locking, but it isn't necessary:
585                  * just need to check at some point in the ksched loop. */
586                 if (__proc_give_cores(p, corelist, nr_to_grant)) {
587                         __put_idle_cores(p, corelist, nr_to_grant);
588                 } else {
589                         /* track the (successful) allocation of the sched_pcores */
590                         for (int i = 0; i < nr_to_grant; i++)
591                                 __prov_track_alloc(p, corelist[i]);
592                         /* at some point after giving cores, call proc_run_m() (harmless on
593                          * RUNNING_Ms).  You can give small groups of cores, then run them
594                          * (which is more efficient than interleaving runs with the gives
595                          * for bulk preempted processes). */
596                         __proc_run_m(p);
597                 }
598                 spin_unlock(&p->proc_lock);
599         }
600 }
601
602 /* TODO: need more thorough CG/LL management.  For now, core0 is the only LL
603  * core.  This won't play well with the ghetto shit in schedule_init() if you do
604  * anything like 'DEDICATED_MONITOR' or the ARSC server.  All that needs an
605  * overhaul. */
606 static bool is_ll_core(uint32_t pcoreid)
607 {
608         if (pcoreid == 0)
609                 return TRUE;
610         return FALSE;
611 }
612
613 /* Helper, makes sure the prov/alloc structures track the pcore properly when it
614  * is allocated to p.  Might make this take a sched_pcore * in the future. */
615 static void __prov_track_alloc(struct proc *p, uint32_t pcoreid)
616 {
617         struct sched_pcore *spc;
618         assert(pcoreid < num_cpus);             /* catch bugs */
619         spc = pcoreid2spc(pcoreid);
620         assert(spc->alloc_proc != p);   /* corruption or double-alloc */
621         spc->alloc_proc = p;
622         /* if the pcore is prov to them and now allocated, move lists */
623         if (spc->prov_proc == p) {
624                 TAILQ_REMOVE(&p->ksched_data.prov_not_alloc_me, spc, prov_next);
625                 TAILQ_INSERT_TAIL(&p->ksched_data.prov_alloc_me, spc, prov_next);
626         }
627 }
628
629 /* Helper, makes sure the prov/alloc structures track the pcore properly when it
630  * is deallocated from p. */
631 static void __prov_track_dealloc(struct proc *p, uint32_t pcoreid)
632 {
633         struct sched_pcore *spc;
634         assert(pcoreid < num_cpus);             /* catch bugs */
635         spc = pcoreid2spc(pcoreid);
636         spc->alloc_proc = 0;
637         /* if the pcore is prov to them and now deallocated, move lists */
638         if (spc->prov_proc == p) {
639                 TAILQ_REMOVE(&p->ksched_data.prov_alloc_me, spc, prov_next);
640                 /* this is the victim list, which can be sorted so that we pick the
641                  * right victim (sort by alloc_proc reverse priority, etc).  In this
642                  * case, the core isn't alloc'd by anyone, so it should be the first
643                  * victim. */
644                 TAILQ_INSERT_HEAD(&p->ksched_data.prov_not_alloc_me, spc, prov_next);
645         }
646 }
647
648 /* Bulk interface for __prov_track_dealloc */
649 static void __prov_track_dealloc_bulk(struct proc *p, uint32_t *pc_arr,
650                                       uint32_t nr_cores)
651 {
652         for (int i = 0; i < nr_cores; i++)
653                 __prov_track_dealloc(p, pc_arr[i]);
654 }
655
656 /* P will get pcore if it needs more cores next time we look at it */
657 void provision_core(struct proc *p, uint32_t pcoreid)
658 {
659         struct sched_pcore *spc;
660         struct sched_pcore_tailq *prov_list;
661         /* Make sure we aren't asking for something that doesn't exist (bounds check
662          * on the pcore array) */
663         if (!(pcoreid < num_cpus))
664                 return; /* could do an error code */
665         /* Don't allow the provisioning of LL cores */
666         if (is_ll_core(pcoreid))
667                 return;
668         spc = pcoreid2spc(pcoreid);
669         /* Note the sched lock protects the spc tailqs for all procs in this code.
670          * If we need a finer grained sched lock, this is one place where we could
671          * have a different lock */
672         spin_lock(&sched_lock);
673         /* If the core is already prov to someone else, take it away.  (last write
674          * wins, some other layer or new func can handle permissions). */
675         if (spc->prov_proc) {
676                 /* the list the spc is on depends on whether it is alloced to the
677                  * prov_proc or not */
678                 prov_list = (spc->alloc_proc == spc->prov_proc ?
679                              &spc->prov_proc->ksched_data.prov_alloc_me :
680                              &spc->prov_proc->ksched_data.prov_not_alloc_me);
681                 TAILQ_REMOVE(prov_list, spc, prov_next);
682         }
683         /* Now prov it to p.  Again, the list it goes on depends on whether it is
684          * alloced to p or not.  Callers can also send in 0 to de-provision. */
685         if (p) {
686                 if (spc->alloc_proc == p) {
687                         TAILQ_INSERT_TAIL(&p->ksched_data.prov_alloc_me, spc, prov_next);
688                 } else {
689                         /* this is be the victim list, which can be sorted so that we pick
690                          * the right victim (sort by alloc_proc reverse priority, etc). */
691                         TAILQ_INSERT_TAIL(&p->ksched_data.prov_not_alloc_me, spc,
692                                           prov_next);
693                 }
694         }
695         spc->prov_proc = p;
696         spin_unlock(&sched_lock);
697 }
698
699 /************** Debugging **************/
700 void sched_diag(void)
701 {
702         struct proc *p;
703         spin_lock(&sched_lock);
704         TAILQ_FOREACH(p, &runnable_scps, ksched_data.proc_link)
705                 printk("Runnable _S PID: %d\n", p->pid);
706         TAILQ_FOREACH(p, &unrunnable_scps, ksched_data.proc_link)
707                 printk("Unrunnable _S PID: %d\n", p->pid);
708         TAILQ_FOREACH(p, &all_mcps, ksched_data.proc_link)
709                 printk("MCP PID: %d\n", p->pid);
710         spin_unlock(&sched_lock);
711         return;
712 }
713
714 void print_idlecoremap(void)
715 {
716         struct sched_pcore *spc_i;
717         /* not locking, so we can look at this without deadlocking. */
718         printk("Idle cores (unlocked!):\n");
719         TAILQ_FOREACH(spc_i, &idlecores, alloc_next)
720                 printk("Core %d, prov to %d (%08p)\n", spc2pcoreid(spc_i),
721                        spc_i->prov_proc ? spc_i->prov_proc->pid : 0, spc_i->prov_proc);
722 }
723
724 void print_resources(struct proc *p)
725 {
726         printk("--------------------\n");
727         printk("PID: %d\n", p->pid);
728         printk("--------------------\n");
729         for (int i = 0; i < MAX_NUM_RESOURCES; i++)
730                 printk("Res type: %02d, amt wanted: %08d, amt granted: %08d\n", i,
731                        p->procdata->res_req[i].amt_wanted, p->procinfo->res_grant[i]);
732 }
733
734 void print_all_resources(void)
735 {
736         /* Hash helper */
737         void __print_resources(void *item)
738         {
739                 print_resources((struct proc*)item);
740         }
741         spin_lock(&pid_hash_lock);
742         hash_for_each(pid_hash, __print_resources);
743         spin_unlock(&pid_hash_lock);
744 }
745
746 void print_prov_map(void)
747 {
748         struct sched_pcore *spc_i;
749         /* Doing this unlocked, which is dangerous, but won't deadlock */
750         printk("Which cores are provisioned to which procs:\n------------------\n");
751         for (int i = 0; i < num_cpus; i++) {
752                 spc_i = pcoreid2spc(i);
753                 printk("Core %02d, prov: %d(%08p) alloc: %d(%08p)\n", i,
754                        spc_i->prov_proc ? spc_i->prov_proc->pid : 0, spc_i->prov_proc,
755                        spc_i->alloc_proc ? spc_i->alloc_proc->pid : 0,
756                        spc_i->alloc_proc);
757         }
758 }
759
760 void print_proc_prov(struct proc *p)
761 {
762         struct sched_pcore *spc_i;
763         if (!p)
764                 return;
765         printk("Prov cores alloced to proc %d (%08p)\n----------\n", p->pid, p);
766         TAILQ_FOREACH(spc_i, &p->ksched_data.prov_alloc_me, prov_next)
767                 printk("Pcore %d\n", spc2pcoreid(spc_i));
768         printk("Prov cores not alloced to proc %d (%08p)\n----------\n", p->pid, p);
769         TAILQ_FOREACH(spc_i, &p->ksched_data.prov_not_alloc_me, prov_next)
770                 printk("Pcore %d (alloced to %d (%08p))\n", spc2pcoreid(spc_i),
771                        spc_i->alloc_proc ? spc_i->alloc_proc->pid : 0,
772                        spc_i->alloc_proc);
773 }