MP Implmentation 3B/4: Remove Xcpuast and Xforward_irq, replacing them
[dragonfly.git] / sys / kern / kern_switch.c
1 /*
2  * Copyright (c) 1999 Peter Wemm <peter@FreeBSD.org>
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  *
14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24  * SUCH DAMAGE.
25  *
26  * $FreeBSD: src/sys/kern/kern_switch.c,v 1.3.2.1 2000/05/16 06:58:12 dillon Exp $
27  * $DragonFly: src/sys/kern/Attic/kern_switch.c,v 1.7 2003/07/11 01:23:24 dillon Exp $
28  */
29
30 #include <sys/param.h>
31 #include <sys/systm.h>
32 #include <sys/kernel.h>
33 #include <sys/lock.h>
34 #include <sys/queue.h>
35 #include <sys/proc.h>
36 #include <sys/rtprio.h>
37 #include <sys/thread2.h>
38 #include <sys/uio.h>
39 #include <sys/sysctl.h>
40 #include <machine/ipl.h>
41 #include <machine/cpu.h>
42
43 /*
44  * debugging only YYY Remove me!   define to schedule user processes only
45  * on the BSP.  Interrupts can still be taken on the APs.
46  */
47 #undef ONLY_ONE_USER_CPU        
48
49 /*
50  * We have NQS (32) run queues per scheduling class.  For the normal
51  * class, there are 128 priorities scaled onto these 32 queues.  New
52  * processes are added to the last entry in each queue, and processes
53  * are selected for running by taking them from the head and maintaining
54  * a simple FIFO arrangement.  Realtime and Idle priority processes have
55  * and explicit 0-31 priority which maps directly onto their class queue
56  * index.  When a queue has something in it, the corresponding bit is
57  * set in the queuebits variable, allowing a single read to determine
58  * the state of all 32 queues and then a ffs() to find the first busy
59  * queue.
60  */
61 static struct rq queues[NQS];
62 static struct rq rtqueues[NQS];
63 static struct rq idqueues[NQS];
64 static u_int32_t queuebits;
65 static u_int32_t rtqueuebits;
66 static u_int32_t idqueuebits;
67 static u_int32_t curprocmask = -1;      /* currently running a user process */
68 static u_int32_t rdyprocmask;           /* ready to accept a user process */
69 static int       runqcount;
70
71 SYSCTL_INT(_debug, OID_AUTO, runqcount, CTLFLAG_RD, &runqcount, 0, "");
72
73 /*
74  * Initialize the run queues at boot time.
75  */
76 static void
77 rqinit(void *dummy)
78 {
79         int i;
80
81         for (i = 0; i < NQS; i++) {
82                 TAILQ_INIT(&queues[i]);
83                 TAILQ_INIT(&rtqueues[i]);
84                 TAILQ_INIT(&idqueues[i]);
85         }
86 #ifdef SMP
87         sched_thread_init();
88 #else
89         curprocmask &= ~1;
90 #endif
91 }
92 SYSINIT(runqueue, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, rqinit, NULL)
93
94 static int
95 test_resched(struct proc *curp, struct proc *newp)
96 {
97         if (newp->p_rtprio.type < curp->p_rtprio.type)
98                 return(1);
99         if (newp->p_rtprio.type == curp->p_rtprio.type) {
100                 if (newp->p_rtprio.type == RTP_PRIO_NORMAL) {
101                         if (newp->p_priority / PPQ <= curp->p_priority / PPQ)
102                                 return(1);
103                 } else if (newp->p_rtprio.prio < curp->p_rtprio.prio) {
104                         return(1);
105                 }
106         }
107         return(0);
108 }
109
110 /*
111  * chooseproc() is called when a cpu needs a user process to LWKT schedule.
112  * chooseproc() will select a user process and return it.
113  */
114 static
115 struct proc *
116 chooseproc(void)
117 {
118         struct proc *p;
119         struct rq *q;
120         u_int32_t *which;
121         u_int32_t pri;
122
123         if (rtqueuebits) {
124                 pri = bsfl(rtqueuebits);
125                 q = &rtqueues[pri];
126                 which = &rtqueuebits;
127         } else if (queuebits) {
128                 pri = bsfl(queuebits);
129                 q = &queues[pri];
130                 which = &queuebits;
131         } else if (idqueuebits) {
132                 pri = bsfl(idqueuebits);
133                 q = &idqueues[pri];
134                 which = &idqueuebits;
135         } else {
136                 return NULL;
137         }
138         p = TAILQ_FIRST(q);
139         KASSERT(p, ("chooseproc: no proc on busy queue"));
140         TAILQ_REMOVE(q, p, p_procq);
141         --runqcount;
142         if (TAILQ_EMPTY(q))
143                 *which &= ~(1 << pri);
144         KASSERT((p->p_flag & P_ONRUNQ) != 0, ("not on runq6!"));
145         p->p_flag &= ~P_ONRUNQ;
146         return p;
147 }
148
149
150 /*
151  * setrunqueue() 'wakes up' a 'user' process, which can mean several things.
152  *
153  * If P_CP_RELEASED is set the user process is under the control of the
154  * LWKT subsystem and we simply wake the thread up.  This is ALWAYS the
155  * case when setrunqueue() is called from wakeup() and, in fact wakeup()
156  * asserts that P_CP_RELEASED is set.
157  *
158  * Note that acquire_curproc() already optimizes making the current process
159  * P_CURPROC, so setrunqueue() does not need to.
160  *
161  * If P_CP_RELEASED is not set we place the process on the run queue and we
162  * signal other cpus in the system that may need to be woken up to service
163  * the new 'user' process.
164  *
165  * The associated thread must NOT be scheduled.  
166  * The process must be runnable.
167  * This must be called at splhigh().
168  */
169 void
170 setrunqueue(struct proc *p)
171 {
172         struct rq *q;
173         int pri;
174         int cpuid;
175         u_int32_t mask;
176
177         crit_enter();
178         KASSERT(p->p_stat == SRUN, ("setrunqueue: proc not SRUN"));
179         KASSERT((p->p_flag & (P_ONRUNQ|P_CURPROC)) == 0,
180             ("process %d already on runq! flag %08x", p->p_pid, p->p_flag));
181         KKASSERT((p->p_thread->td_flags & TDF_RUNQ) == 0);
182
183         /*
184          * If we have been released from the userland scheduler we
185          * directly schedule its thread.
186          */
187         if (p->p_flag & P_CP_RELEASED) {
188                 lwkt_schedule(p->p_thread);
189                 crit_exit();
190                 return;
191         }
192
193         /*
194          * If our cpu is available to run a user process we short cut and
195          * just do it.
196          */
197         cpuid = mycpu->gd_cpuid;
198         if ((curprocmask & (1 << cpuid)) == 0) {
199                 curprocmask |= 1 << cpuid;
200                 p->p_flag |= P_CURPROC;
201                 lwkt_acquire(p->p_thread);
202                 lwkt_schedule(p->p_thread);
203                 crit_exit();
204                 return;
205         }
206
207         /*
208          * Otherwise place this process on the userland scheduler's run
209          * queue for action.
210          */
211         ++runqcount;
212         p->p_flag |= P_ONRUNQ;
213         if (p->p_rtprio.type == RTP_PRIO_NORMAL) {
214                 pri = p->p_priority >> 2;
215                 q = &queues[pri];
216                 queuebits |= 1 << pri;
217         } else if (p->p_rtprio.type == RTP_PRIO_REALTIME ||
218                    p->p_rtprio.type == RTP_PRIO_FIFO) {
219                 pri = (u_int8_t)p->p_rtprio.prio;
220                 q = &rtqueues[pri];
221                 rtqueuebits |= 1 << pri;
222         } else if (p->p_rtprio.type == RTP_PRIO_IDLE) {
223                 pri = (u_int8_t)p->p_rtprio.prio;
224                 q = &idqueues[pri];
225                 idqueuebits |= 1 << pri;
226         } else {
227                 panic("setrunqueue: invalid rtprio type");
228         }
229         KKASSERT(pri < 32);
230         p->p_rqindex = pri;             /* remember the queue index */
231         TAILQ_INSERT_TAIL(q, p, p_procq);
232
233         /*
234          * Wakeup other cpus to schedule the newly available thread.
235          * XXX doesn't really have to be in a critical section.
236          * We own giant after all.
237          *
238          * We use rdyprocmask to avoid unnecessarily waking up the scheduler
239          * thread when it is already running.
240          */
241         if ((mask = ~curprocmask & rdyprocmask & mycpu->gd_other_cpus) != 0) {
242                 int count = runqcount;
243                 if (!mask)
244                         printf("PROC %d nocpu to schedule it on\n", p->p_pid);
245                 while (mask && count) {
246                         cpuid = bsfl(mask);
247                         KKASSERT((curprocmask & (1 << cpuid)) == 0);
248                         rdyprocmask &= ~(1 << cpuid);
249                         lwkt_schedule(&globaldata_find(cpuid)->gd_schedthread);
250                         --count;
251                         mask &= ~(1 << cpuid);
252                 }
253         }
254         crit_exit();
255 }
256
257 /*
258  * remrunqueue() removes a given process from the run queue that it is on,
259  * clearing the queue busy bit if it becomes empty.  This function is called
260  * when a userland process is selected for LWKT scheduling.  Note that 
261  * LWKT scheduling is an abstraction of 'curproc'.. there could very well be
262  * several userland processes whos threads are scheduled or otherwise in
263  * a special state, and such processes are NOT on the userland scheduler's
264  * run queue.
265  *
266  * This must be called at splhigh().
267  */
268 void
269 remrunqueue(struct proc *p)
270 {
271         struct rq *q;
272         u_int32_t *which;
273         u_int8_t pri;
274
275         crit_enter();
276         KASSERT((p->p_flag & P_ONRUNQ) != 0, ("not on runq4!"));
277         p->p_flag &= ~P_ONRUNQ;
278         --runqcount;
279         KKASSERT(runqcount >= 0);
280         pri = p->p_rqindex;
281         if (p->p_rtprio.type == RTP_PRIO_NORMAL) {
282                 q = &queues[pri];
283                 which = &queuebits;
284         } else if (p->p_rtprio.type == RTP_PRIO_REALTIME ||
285                    p->p_rtprio.type == RTP_PRIO_FIFO) {
286                 q = &rtqueues[pri];
287                 which = &rtqueuebits;
288         } else if (p->p_rtprio.type == RTP_PRIO_IDLE) {
289                 q = &idqueues[pri];
290                 which = &idqueuebits;
291         } else {
292                 panic("remrunqueue: invalid rtprio type");
293         }
294         TAILQ_REMOVE(q, p, p_procq);
295         if (TAILQ_EMPTY(q)) {
296                 KASSERT((*which & (1 << pri)) != 0,
297                         ("remrunqueue: remove from empty queue"));
298                 *which &= ~(1 << pri);
299         }
300         crit_exit();
301 }
302
303 /*
304  * Release the P_CURPROC designation on the CURRENT process only.  This
305  * will allow another userland process to be scheduled.  If we do not
306  * have or cannot get the MP lock we just wakeup the scheduler thread for
307  * this cpu.
308  *
309  * WARNING!  The MP lock may be in an unsynchronized state due to the
310  * way get_mplock() works and the fact that this function may be called
311  * from a passive release during a lwkt_switch().   try_mplock() will deal 
312  * with this for us but you should be aware that td_mpcount may not be
313  * useable.
314  */
315 void
316 release_curproc(struct proc *p)
317 {
318         int cpuid;
319         struct proc *np;
320
321 #ifdef ONLY_ONE_USER_CPU
322         KKASSERT(mycpu->gd_cpuid == 0 && p->p_thread->td_cpu == 0);
323 #endif
324         crit_enter();
325         clear_resched();
326         cpuid = p->p_thread->td_cpu;
327         p->p_flag |= P_CP_RELEASED;
328         if (p->p_flag & P_CURPROC) {
329                 p->p_flag &= ~P_CURPROC;
330                 if (try_mplock()) {
331                         KKASSERT(curprocmask & (1 << cpuid));
332                         if ((np = chooseproc()) != NULL) {
333                                 np->p_flag |= P_CURPROC;
334                                 lwkt_acquire(np->p_thread);
335                                 lwkt_schedule(np->p_thread);
336                         } else {
337                                 curprocmask &= ~(1 << cpuid);
338                         }
339                         rel_mplock();
340                 } else {
341                         KKASSERT(0);
342                         curprocmask &= ~(1 << cpuid);
343                         if (rdyprocmask & (1 << cpuid))
344                                 lwkt_schedule(&globaldata_find(cpuid)->gd_schedthread);
345                 }
346         }
347         crit_exit();
348 }
349
350 /*
351  * Acquire the P_CURPROC designation on the CURRENT process only.  This
352  * function is called prior to returning to userland.  If the system
353  * call or trap did not block and if no reschedule was requested it is
354  * highly likely that the P_CURPROC flag is still set in the proc, and
355  * we do almost nothing here.
356  */
357 void
358 acquire_curproc(struct proc *p)
359 {
360         int cpuid;
361         struct proc *np;
362
363         /*
364          * Short cut, we've already acquired the designation or we never
365          * lost it in the first place.
366          */
367         if ((p->p_flag & P_CURPROC) != 0)
368                 return;
369
370         /*
371          * Long cut.  This pulls in a bit of the userland scheduler as 
372          * an optimization.  If our cpu has not scheduled a userland
373          * process we gladly fill the slot, otherwise we choose the best
374          * candidate from the run queue and compare it against ourselves,
375          * scheduling either us or him depending.
376          *
377          * If our cpu's slot isn't free we put ourselves on the userland
378          * run queue and switch away.  We should have P_CURPROC when we
379          * come back.  Note that a cpu change can occur when we come back.
380          *
381          * YYY don't need critical section, we hold giant and no interrupt
382          * will mess w/ this proc?  Or will it?  What about curprocmask?
383          */
384 #ifdef ONLY_ONE_USER_CPU
385         KKASSERT(mycpu->gd_cpuid == 0 && p->p_thread->td_cpu == 0);
386 #endif
387         crit_enter();
388         p->p_flag &= ~P_CP_RELEASED;
389         while ((p->p_flag & P_CURPROC) == 0) {
390                 cpuid = p->p_thread->td_cpu;    /* load/reload cpuid */
391                 if ((curprocmask & (1 << cpuid)) == 0) {
392                         curprocmask |= 1 << cpuid;
393                         if ((np = chooseproc()) != NULL) {
394                                 KKASSERT((np->p_flag & P_CP_RELEASED) == 0);
395                                 if (test_resched(p, np)) {
396                                         np->p_flag |= P_CURPROC;
397                                         lwkt_acquire(np->p_thread);
398                                         lwkt_schedule(np->p_thread);
399                                 } else {
400                                         p->p_flag |= P_CURPROC;
401                                         setrunqueue(np);
402                                 }
403                         } else {
404                                 p->p_flag |= P_CURPROC;
405                         }
406                 }
407                 if ((p->p_flag & P_CURPROC) == 0) {
408                         lwkt_deschedule_self();
409                         setrunqueue(p);
410                         lwkt_switch();
411                         KKASSERT((p->p_flag & (P_ONRUNQ|P_CURPROC|P_CP_RELEASED)) == P_CURPROC);
412                 }
413         }
414         crit_exit();
415 }
416
417 /*
418  * Yield / synchronous reschedule.  This is a bit tricky because the trap
419  * code might have set a lazy release on the switch function.  The first
420  * thing we do is call lwkt_switch() to resolve the lazy release (if any).
421  * Then, if we are a process, we want to allow another process to run.
422  *
423  * The only way to do that is to acquire and then release P_CURPROC.  We
424  * have to release it because the kernel expects it to be released as a
425  * sanity check when it goes to sleep.
426  *
427  * XXX we need a way to ensure that we wake up eventually from a yield,
428  * even if we are an idprio process.
429  */
430 void
431 uio_yield(void)
432 {
433         struct thread *td = curthread;
434         struct proc *p = td->td_proc;
435
436         lwkt_switch();
437         if (p) {
438                 acquire_curproc(p);
439                 release_curproc(p);
440         }
441 }
442
443
444 /*
445  * For SMP systems a user scheduler helper thread is created for each
446  * cpu and is used to allow one cpu to wakeup another for the purposes of
447  * scheduling userland threads from setrunqueue().  UP systems do not
448  * need the helper since there is only one cpu.  We can't use the idle
449  * thread for this because we need to hold the MP lock.  Additionally,
450  * doing things this way allows us to HLT idle cpus on MP systems.
451  */
452
453 #ifdef SMP
454
455 static void
456 sched_thread(void *dummy)
457 {
458     int cpuid = mycpu->gd_cpuid;        /* doesn't change */
459     u_int32_t cpumask = 1 << cpuid;     /* doesn't change */
460
461 #ifdef ONLY_ONE_USER_CPU
462     KKASSERT(cpuid == 0);
463 #endif
464
465     get_mplock();                       /* hold the MP lock */
466     for (;;) {
467         struct proc *np;
468
469         lwkt_deschedule_self();         /* interlock */
470         rdyprocmask |= cpumask;
471         crit_enter();
472         if ((curprocmask & cpumask) == 0 && (np = chooseproc()) != NULL) {
473             curprocmask |= cpumask;
474             np->p_flag |= P_CURPROC;
475             lwkt_acquire(np->p_thread);
476             lwkt_schedule(np->p_thread);
477         }
478         crit_exit();
479         lwkt_switch();
480     }
481 }
482
483 void
484 sched_thread_init(void)
485 {
486     int cpuid = mycpu->gd_cpuid;
487
488     lwkt_create(sched_thread, NULL, NULL, &mycpu->gd_schedthread, 
489         TDF_STOPREQ, "usched %d", cpuid);
490     curprocmask &= ~(1 << cpuid);       /* schedule user proc on cpu */
491 #ifdef ONLY_ONE_USER_CPU
492     if (cpuid)
493         curprocmask |= 1 << cpuid;      /* DISABLE USER PROCS */
494 #endif
495     rdyprocmask |= 1 << cpuid;
496 }
497
498 #endif
499