Initial import from FreeBSD RELENG_4:
[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  */
28
29 #include <sys/param.h>
30 #include <sys/systm.h>
31 #include <sys/kernel.h>
32 #include <sys/proc.h>
33 #include <sys/rtprio.h>
34 #include <sys/queue.h>
35
36 /*
37  * We have NQS (32) run queues per scheduling class.  For the normal
38  * class, there are 128 priorities scaled onto these 32 queues.  New
39  * processes are added to the last entry in each queue, and processes
40  * are selected for running by taking them from the head and maintaining
41  * a simple FIFO arrangement.  Realtime and Idle priority processes have
42  * and explicit 0-31 priority which maps directly onto their class queue
43  * index.  When a queue has something in it, the corresponding bit is
44  * set in the queuebits variable, allowing a single read to determine
45  * the state of all 32 queues and then a ffs() to find the first busy
46  * queue.
47  */
48 struct rq queues[NQS];
49 struct rq rtqueues[NQS];
50 struct rq idqueues[NQS];
51 u_int32_t queuebits;
52 u_int32_t rtqueuebits;
53 u_int32_t idqueuebits;
54
55 /*
56  * Initialize the run queues at boot time.
57  */
58 static void
59 rqinit(void *dummy)
60 {
61         int i;
62
63         for (i = 0; i < NQS; i++) {
64                 TAILQ_INIT(&queues[i]);
65                 TAILQ_INIT(&rtqueues[i]);
66                 TAILQ_INIT(&idqueues[i]);
67         }
68 }
69 SYSINIT(runqueue, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, rqinit, NULL)
70
71 /*
72  * setrunqueue() examines a process priority and class and inserts it on
73  * the tail of it's appropriate run queue (based on class and priority).
74  * This sets the queue busy bit.
75  * The process must be runnable.
76  * This must be called at splhigh().
77  */
78 void
79 setrunqueue(struct proc *p)
80 {
81         struct rq *q;
82         u_int8_t pri;
83
84         KASSERT(p->p_stat == SRUN, ("setrunqueue: proc not SRUN"));
85         if (p->p_rtprio.type == RTP_PRIO_NORMAL) {
86                 pri = p->p_priority >> 2;
87                 q = &queues[pri];
88                 queuebits |= 1 << pri;
89         } else if (p->p_rtprio.type == RTP_PRIO_REALTIME ||
90                    p->p_rtprio.type == RTP_PRIO_FIFO) {
91                 pri = p->p_rtprio.prio;
92                 q = &rtqueues[pri];
93                 rtqueuebits |= 1 << pri;
94         } else if (p->p_rtprio.type == RTP_PRIO_IDLE) {
95                 pri = p->p_rtprio.prio;
96                 q = &idqueues[pri];
97                 idqueuebits |= 1 << pri;
98         } else {
99                 panic("setrunqueue: invalid rtprio type");
100         }
101         p->p_rqindex = pri;             /* remember the queue index */
102         TAILQ_INSERT_TAIL(q, p, p_procq);
103 }
104
105 /*
106  * remrunqueue() removes a given process from the run queue that it is on,
107  * clearing the queue busy bit if it becomes empty.
108  * This must be called at splhigh().
109  */
110 void
111 remrunqueue(struct proc *p)
112 {
113         struct rq *q;
114         u_int32_t *which;
115         u_int8_t pri;
116
117         pri = p->p_rqindex;
118         if (p->p_rtprio.type == RTP_PRIO_NORMAL) {
119                 q = &queues[pri];
120                 which = &queuebits;
121         } else if (p->p_rtprio.type == RTP_PRIO_REALTIME ||
122                    p->p_rtprio.type == RTP_PRIO_FIFO) {
123                 q = &rtqueues[pri];
124                 which = &rtqueuebits;
125         } else if (p->p_rtprio.type == RTP_PRIO_IDLE) {
126                 q = &idqueues[pri];
127                 which = &idqueuebits;
128         } else {
129                 panic("remrunqueue: invalid rtprio type");
130         }
131         TAILQ_REMOVE(q, p, p_procq);
132         if (TAILQ_EMPTY(q)) {
133                 KASSERT((*which & (1 << pri)) != 0,
134                         ("remrunqueue: remove from empty queue"));
135                 *which &= ~(1 << pri);
136         }
137 }
138
139 /*
140  * procrunnable() returns a boolean true (non-zero) value if there are
141  * any runnable processes.  This is intended to be called from the idle
142  * loop to avoid the more expensive (and destructive) chooseproc().
143  *
144  * MP SAFE.  CALLED WITHOUT THE MP LOCK
145  */
146 u_int32_t
147 procrunnable(void)
148 {
149         return (rtqueuebits || queuebits || idqueuebits);
150 }
151
152 /*
153  * chooseproc() selects the next process to run.  Ideally, cpu_switch()
154  * would have determined that there is a process available before calling
155  * this, but it is not a requirement.  The selected process is removed
156  * from it's queue, and the queue busy bit is cleared if it becomes empty.
157  * This must be called at splhigh().
158  *
159  * For SMP, trivial affinity is implemented by locating the first process
160  * on the queue that has a matching lastcpu id.  Since normal priorities
161  * are mapped four priority levels per queue, this may allow the cpu to
162  * choose a slightly lower priority process in order to preserve the cpu
163  * caches.
164  */
165 struct proc *
166 chooseproc(void)
167 {
168         struct proc *p;
169         struct rq *q;
170         u_int32_t *which;
171         u_int32_t pri;
172 #ifdef SMP
173         u_char id;
174 #endif
175
176         if (rtqueuebits) {
177                 pri = ffs(rtqueuebits) - 1;
178                 q = &rtqueues[pri];
179                 which = &rtqueuebits;
180         } else if (queuebits) {
181                 pri = ffs(queuebits) - 1;
182                 q = &queues[pri];
183                 which = &queuebits;
184         } else if (idqueuebits) {
185                 pri = ffs(idqueuebits) - 1;
186                 q = &idqueues[pri];
187                 which = &idqueuebits;
188         } else {
189                 return NULL;
190         }
191         p = TAILQ_FIRST(q);
192         KASSERT(p, ("chooseproc: no proc on busy queue"));
193 #ifdef SMP
194         /* wander down the current run queue for this pri level for a match */
195         id = cpuid;
196         while (p->p_lastcpu != id) {
197                 p = TAILQ_NEXT(p, p_procq);
198                 if (p == NULL) {
199                         p = TAILQ_FIRST(q);
200                         break;
201                 }
202         }
203 #endif
204         TAILQ_REMOVE(q, p, p_procq);
205         if (TAILQ_EMPTY(q))
206                 *which &= ~(1 << pri);
207         return p;
208 }