Fix a minor bug in lwkt_init_thread() (the thread was being added to the
[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.9 2003/07/25 05:26:50 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 static int usched_steal;
73 SYSCTL_INT(_debug, OID_AUTO, usched_steal, CTLFLAG_RW,
74         &usched_steal, 0, "Passive Release was nonoptimal");
75 static int usched_optimal;
76 SYSCTL_INT(_debug, OID_AUTO, usched_optimal, CTLFLAG_RW,
77         &usched_optimal, 0, "Passive Release was nonoptimal");
78
79 #define USCHED_COUNTER(td)      ((td->td_gd == mycpu) ? ++usched_optimal : ++usched_steal)
80
81 /*
82  * Initialize the run queues at boot time.
83  */
84 static void
85 rqinit(void *dummy)
86 {
87         int i;
88
89         for (i = 0; i < NQS; i++) {
90                 TAILQ_INIT(&queues[i]);
91                 TAILQ_INIT(&rtqueues[i]);
92                 TAILQ_INIT(&idqueues[i]);
93         }
94 #ifdef SMP
95         sched_thread_init();
96 #else
97         curprocmask &= ~1;
98 #endif
99 }
100 SYSINIT(runqueue, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, rqinit, NULL)
101
102 static int
103 test_resched(struct proc *curp, struct proc *newp)
104 {
105         if (newp->p_rtprio.type < curp->p_rtprio.type)
106                 return(1);
107         if (newp->p_rtprio.type == curp->p_rtprio.type) {
108                 if (newp->p_rtprio.type == RTP_PRIO_NORMAL) {
109                         if (newp->p_priority / PPQ <= curp->p_priority / PPQ)
110                                 return(1);
111                 } else if (newp->p_rtprio.prio < curp->p_rtprio.prio) {
112                         return(1);
113                 }
114         }
115         return(0);
116 }
117
118 /*
119  * chooseproc() is called when a cpu needs a user process to LWKT schedule.
120  * chooseproc() will select a user process and return it.
121  */
122 static
123 struct proc *
124 chooseproc(void)
125 {
126         struct proc *p;
127         struct rq *q;
128         u_int32_t *which;
129         u_int32_t pri;
130
131         if (rtqueuebits) {
132                 pri = bsfl(rtqueuebits);
133                 q = &rtqueues[pri];
134                 which = &rtqueuebits;
135         } else if (queuebits) {
136                 pri = bsfl(queuebits);
137                 q = &queues[pri];
138                 which = &queuebits;
139         } else if (idqueuebits) {
140                 pri = bsfl(idqueuebits);
141                 q = &idqueues[pri];
142                 which = &idqueuebits;
143         } else {
144                 return NULL;
145         }
146         p = TAILQ_FIRST(q);
147         KASSERT(p, ("chooseproc: no proc on busy queue"));
148         TAILQ_REMOVE(q, p, p_procq);
149         --runqcount;
150         if (TAILQ_EMPTY(q))
151                 *which &= ~(1 << pri);
152         KASSERT((p->p_flag & P_ONRUNQ) != 0, ("not on runq6!"));
153         p->p_flag &= ~P_ONRUNQ;
154         return p;
155 }
156
157
158 /*
159  * setrunqueue() 'wakes up' a 'user' process, which can mean several things.
160  *
161  * If P_CP_RELEASED is set the user process is under the control of the
162  * LWKT subsystem and we simply wake the thread up.  This is ALWAYS the
163  * case when setrunqueue() is called from wakeup() and, in fact wakeup()
164  * asserts that P_CP_RELEASED is set.
165  *
166  * Note that acquire_curproc() already optimizes making the current process
167  * P_CURPROC, so setrunqueue() does not need to.
168  *
169  * If P_CP_RELEASED is not set we place the process on the run queue and we
170  * signal other cpus in the system that may need to be woken up to service
171  * the new 'user' process.
172  *
173  * If P_PASSIVE_ACQ is set setrunqueue() will not wakeup potential target
174  * cpus in an attempt to keep the process on the current cpu at least for
175  * a little while to take advantage of locality of reference (e.g. fork/exec
176  * or short fork/exit).
177  *
178  * WARNING! a thread can be acquired by another cpu the moment it is put
179  * on the user scheduler's run queue AND we release the MP lock.  Since we
180  * release the MP lock before switching out another cpu may begin stealing
181  * our current thread before we are completely switched out!  The 
182  * lwkt_acquire() function will stall until TDF_RUNNING is cleared on the
183  * thread before stealing it.
184  *
185  * The associated thread must NOT be scheduled.  
186  * The process must be runnable.
187  * This must be called at splhigh().
188  */
189 void
190 setrunqueue(struct proc *p)
191 {
192         struct rq *q;
193         int pri;
194         int cpuid;
195         u_int32_t mask;
196
197         crit_enter();
198         KASSERT(p->p_stat == SRUN, ("setrunqueue: proc not SRUN"));
199         KASSERT((p->p_flag & (P_ONRUNQ|P_CURPROC)) == 0,
200             ("process %d already on runq! flag %08x", p->p_pid, p->p_flag));
201         KKASSERT((p->p_thread->td_flags & TDF_RUNQ) == 0);
202
203         /*
204          * If we have been released from the userland scheduler we
205          * directly schedule its thread.
206          */
207         if (p->p_flag & P_CP_RELEASED) {
208                 lwkt_schedule(p->p_thread);
209                 crit_exit();
210                 return;
211         }
212
213         /*
214          * If our cpu is available to run a user process we short cut and
215          * just do it.
216          */
217         cpuid = mycpu->gd_cpuid;
218         if ((curprocmask & (1 << cpuid)) == 0) {
219                 curprocmask |= 1 << cpuid;
220                 p->p_flag |= P_CURPROC;
221                 USCHED_COUNTER(p->p_thread);
222                 lwkt_acquire(p->p_thread);
223                 lwkt_schedule(p->p_thread);
224                 crit_exit();
225                 return;
226         }
227
228         /*
229          * Otherwise place this process on the userland scheduler's run
230          * queue for action.
231          */
232         ++runqcount;
233         p->p_flag |= P_ONRUNQ;
234         if (p->p_rtprio.type == RTP_PRIO_NORMAL) {
235                 pri = p->p_priority >> 2;
236                 q = &queues[pri];
237                 queuebits |= 1 << pri;
238         } else if (p->p_rtprio.type == RTP_PRIO_REALTIME ||
239                    p->p_rtprio.type == RTP_PRIO_FIFO) {
240                 pri = (u_int8_t)p->p_rtprio.prio;
241                 q = &rtqueues[pri];
242                 rtqueuebits |= 1 << pri;
243         } else if (p->p_rtprio.type == RTP_PRIO_IDLE) {
244                 pri = (u_int8_t)p->p_rtprio.prio;
245                 q = &idqueues[pri];
246                 idqueuebits |= 1 << pri;
247         } else {
248                 panic("setrunqueue: invalid rtprio type");
249         }
250         KKASSERT(pri < 32);
251         p->p_rqindex = pri;             /* remember the queue index */
252         TAILQ_INSERT_TAIL(q, p, p_procq);
253
254         /*
255          * Wakeup other cpus to schedule the newly available thread.
256          * XXX doesn't really have to be in a critical section.
257          * We own giant after all.
258          *
259          * We use rdyprocmask to avoid unnecessarily waking up the scheduler
260          * thread when it is already running.
261          */
262         if ((mask = ~curprocmask & rdyprocmask & mycpu->gd_other_cpus) != 0 &&
263             (p->p_flag & P_PASSIVE_ACQ) == 0) {
264                 int count = runqcount;
265                 if (!mask)
266                         printf("PROC %d nocpu to schedule it on\n", p->p_pid);
267                 while (mask && count) {
268                         cpuid = bsfl(mask);
269                         KKASSERT((curprocmask & (1 << cpuid)) == 0);
270                         rdyprocmask &= ~(1 << cpuid);
271                         lwkt_schedule(&globaldata_find(cpuid)->gd_schedthread);
272                         --count;
273                         mask &= ~(1 << cpuid);
274                 }
275         }
276         crit_exit();
277 }
278
279 /*
280  * remrunqueue() removes a given process from the run queue that it is on,
281  * clearing the queue busy bit if it becomes empty.  This function is called
282  * when a userland process is selected for LWKT scheduling.  Note that 
283  * LWKT scheduling is an abstraction of 'curproc'.. there could very well be
284  * several userland processes whos threads are scheduled or otherwise in
285  * a special state, and such processes are NOT on the userland scheduler's
286  * run queue.
287  *
288  * This must be called at splhigh().
289  */
290 void
291 remrunqueue(struct proc *p)
292 {
293         struct rq *q;
294         u_int32_t *which;
295         u_int8_t pri;
296
297         crit_enter();
298         KASSERT((p->p_flag & P_ONRUNQ) != 0, ("not on runq4!"));
299         p->p_flag &= ~P_ONRUNQ;
300         --runqcount;
301         KKASSERT(runqcount >= 0);
302         pri = p->p_rqindex;
303         if (p->p_rtprio.type == RTP_PRIO_NORMAL) {
304                 q = &queues[pri];
305                 which = &queuebits;
306         } else if (p->p_rtprio.type == RTP_PRIO_REALTIME ||
307                    p->p_rtprio.type == RTP_PRIO_FIFO) {
308                 q = &rtqueues[pri];
309                 which = &rtqueuebits;
310         } else if (p->p_rtprio.type == RTP_PRIO_IDLE) {
311                 q = &idqueues[pri];
312                 which = &idqueuebits;
313         } else {
314                 panic("remrunqueue: invalid rtprio type");
315         }
316         TAILQ_REMOVE(q, p, p_procq);
317         if (TAILQ_EMPTY(q)) {
318                 KASSERT((*which & (1 << pri)) != 0,
319                         ("remrunqueue: remove from empty queue"));
320                 *which &= ~(1 << pri);
321         }
322         crit_exit();
323 }
324
325 /*
326  * Release the P_CURPROC designation on the CURRENT process only.  This
327  * will allow another userland process to be scheduled.  If we do not
328  * have or cannot get the MP lock we just wakeup the scheduler thread for
329  * this cpu.
330  *
331  * WARNING!  The MP lock may be in an unsynchronized state due to the
332  * way get_mplock() works and the fact that this function may be called
333  * from a passive release during a lwkt_switch().   try_mplock() will deal 
334  * with this for us but you should be aware that td_mpcount may not be
335  * useable.
336  */
337 void
338 release_curproc(struct proc *p)
339 {
340         int cpuid;
341         struct proc *np;
342
343 #ifdef ONLY_ONE_USER_CPU
344         KKASSERT(mycpu->gd_cpuid == 0 && p->p_thread->td_gd == mycpu);
345 #endif
346         crit_enter();
347         clear_resched();
348         cpuid = p->p_thread->td_gd->gd_cpuid;
349         p->p_flag |= P_CP_RELEASED;
350         if (p->p_flag & P_CURPROC) {
351                 p->p_flag &= ~P_CURPROC;
352                 if (try_mplock()) {
353                         KKASSERT(curprocmask & (1 << cpuid));
354                         if ((np = chooseproc()) != NULL) {
355                                 np->p_flag |= P_CURPROC;
356                                 USCHED_COUNTER(np->p_thread);
357                                 lwkt_acquire(np->p_thread);
358                                 lwkt_schedule(np->p_thread);
359                         } else {
360                                 curprocmask &= ~(1 << cpuid);
361                         }
362                         rel_mplock();
363                 } else {
364                         KKASSERT(0);
365                         curprocmask &= ~(1 << cpuid);
366                         if (rdyprocmask & (1 << cpuid))
367                                 lwkt_schedule(&globaldata_find(cpuid)->gd_schedthread);
368                 }
369         }
370         crit_exit();
371 }
372
373 /*
374  * Acquire the P_CURPROC designation on the CURRENT process only.  This
375  * function is called prior to returning to userland.  If the system
376  * call or trap did not block and if no reschedule was requested it is
377  * highly likely that the P_CURPROC flag is still set in the proc, and
378  * we do almost nothing here.
379  */
380 void
381 acquire_curproc(struct proc *p)
382 {
383         int cpuid;
384         struct proc *np;
385
386         /*
387          * Short cut, we've already acquired the designation or we never
388          * lost it in the first place.
389          */
390         if ((p->p_flag & P_CURPROC) != 0)
391                 return;
392
393         /*
394          * Long cut.  This pulls in a bit of the userland scheduler as 
395          * an optimization.  If our cpu has not scheduled a userland
396          * process we gladly fill the slot, otherwise we choose the best
397          * candidate from the run queue and compare it against ourselves,
398          * scheduling either us or him depending.
399          *
400          * If our cpu's slot isn't free we put ourselves on the userland
401          * run queue and switch away.  We should have P_CURPROC when we
402          * come back.  Note that a cpu change can occur when we come back.
403          *
404          * YYY don't need critical section, we hold giant and no interrupt
405          * will mess w/ this proc?  Or will it?  What about curprocmask?
406          */
407 #ifdef ONLY_ONE_USER_CPU
408         KKASSERT(mycpu->gd_cpuid == 0 && p->p_thread->td_gd == mycpu);
409 #endif
410         crit_enter();
411         p->p_flag &= ~P_CP_RELEASED;
412         while ((p->p_flag & P_CURPROC) == 0) {
413                 cpuid = p->p_thread->td_gd->gd_cpuid;   /* load/reload cpuid */
414                 if ((curprocmask & (1 << cpuid)) == 0) {
415                         curprocmask |= 1 << cpuid;
416                         if ((np = chooseproc()) != NULL) {
417                                 KKASSERT((np->p_flag & P_CP_RELEASED) == 0);
418                                 if (test_resched(p, np)) {
419                                         np->p_flag |= P_CURPROC;
420                                         USCHED_COUNTER(np->p_thread);
421                                         lwkt_acquire(np->p_thread);
422                                         lwkt_schedule(np->p_thread);
423                                 } else {
424                                         p->p_flag |= P_CURPROC;
425                                         setrunqueue(np);
426                                 }
427                         } else {
428                                 p->p_flag |= P_CURPROC;
429                         }
430                 }
431                 if ((p->p_flag & P_CURPROC) == 0) {
432                         lwkt_deschedule_self();
433                         setrunqueue(p);
434                         lwkt_switch();
435                         KKASSERT((p->p_flag & (P_ONRUNQ|P_CURPROC|P_CP_RELEASED)) == P_CURPROC);
436                 }
437         }
438         crit_exit();
439 }
440
441 /*
442  * Yield / synchronous reschedule.  This is a bit tricky because the trap
443  * code might have set a lazy release on the switch function.  The first
444  * thing we do is call lwkt_switch() to resolve the lazy release (if any).
445  * Then, if we are a process, we want to allow another process to run.
446  *
447  * The only way to do that is to acquire and then release P_CURPROC.  We
448  * have to release it because the kernel expects it to be released as a
449  * sanity check when it goes to sleep.
450  *
451  * XXX we need a way to ensure that we wake up eventually from a yield,
452  * even if we are an idprio process.
453  */
454 void
455 uio_yield(void)
456 {
457         struct thread *td = curthread;
458         struct proc *p = td->td_proc;
459
460         lwkt_switch();
461         if (p) {
462                 p->p_flag |= P_PASSIVE_ACQ;
463                 acquire_curproc(p);
464                 release_curproc(p);
465                 p->p_flag &= ~P_PASSIVE_ACQ;
466         }
467 }
468
469
470 /*
471  * For SMP systems a user scheduler helper thread is created for each
472  * cpu and is used to allow one cpu to wakeup another for the purposes of
473  * scheduling userland threads from setrunqueue().  UP systems do not
474  * need the helper since there is only one cpu.  We can't use the idle
475  * thread for this because we need to hold the MP lock.  Additionally,
476  * doing things this way allows us to HLT idle cpus on MP systems.
477  */
478
479 #ifdef SMP
480
481 static void
482 sched_thread(void *dummy)
483 {
484     int cpuid = mycpu->gd_cpuid;        /* doesn't change */
485     u_int32_t cpumask = 1 << cpuid;     /* doesn't change */
486
487 #ifdef ONLY_ONE_USER_CPU
488     KKASSERT(cpuid == 0);
489 #endif
490
491     get_mplock();                       /* hold the MP lock */
492     for (;;) {
493         struct proc *np;
494
495         lwkt_deschedule_self();         /* interlock */
496         rdyprocmask |= cpumask;
497         crit_enter();
498         if ((curprocmask & cpumask) == 0 && (np = chooseproc()) != NULL) {
499             curprocmask |= cpumask;
500             np->p_flag |= P_CURPROC;
501             USCHED_COUNTER(np->p_thread);
502             lwkt_acquire(np->p_thread);
503             lwkt_schedule(np->p_thread);
504         }
505         crit_exit();
506         lwkt_switch();
507     }
508 }
509
510 void
511 sched_thread_init(void)
512 {
513     int cpuid = mycpu->gd_cpuid;
514
515     lwkt_create(sched_thread, NULL, NULL, &mycpu->gd_schedthread, 
516         TDF_STOPREQ, "usched %d", cpuid);
517     curprocmask &= ~(1 << cpuid);       /* schedule user proc on cpu */
518 #ifdef ONLY_ONE_USER_CPU
519     if (cpuid)
520         curprocmask |= 1 << cpuid;      /* DISABLE USER PROCS */
521 #endif
522     rdyprocmask |= 1 << cpuid;
523 }
524
525 #endif
526