]> CyberLeo.Net >> Repos - FreeBSD/FreeBSD.git/blob - sys/kern/kern_switch.c
This commit was generated by cvs2svn to compensate for changes in r89857,
[FreeBSD/FreeBSD.git] / sys / kern / kern_switch.c
1 /*
2  * Copyright (c) 2001 Jake Burkholder <jake@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$
27  */
28
29 #include <sys/param.h>
30 #include <sys/systm.h>
31 #include <sys/kernel.h>
32 #include <sys/ktr.h>
33 #include <sys/lock.h>
34 #include <sys/mutex.h>
35 #include <sys/proc.h>
36 #include <sys/queue.h>
37
38 /*
39  * Global run queue.
40  */
41 static struct runq runq;
42 SYSINIT(runq, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, runq_init, &runq)
43
44 /*
45  * Wrappers which implement old interface; act on global run queue.
46  */
47
48 struct thread *
49 choosethread(void)
50 {
51         return (runq_choose(&runq)->ke_thread);
52 }
53
54 int
55 procrunnable(void)
56 {
57         return runq_check(&runq);
58 }
59
60 void
61 remrunqueue(struct thread *td)
62 {
63         runq_remove(&runq, td->td_kse);
64 }
65
66 void
67 setrunqueue(struct thread *td)
68 {
69         runq_add(&runq, td->td_kse);
70 }
71
72 /* Critical sections that prevent preemption. */
73 void
74 critical_enter(void)
75 {
76         struct thread *td;
77
78         td = curthread;
79         if (td->td_critnest == 0)
80                 td->td_savecrit = cpu_critical_enter();
81         td->td_critnest++;
82 }
83
84 void
85 critical_exit(void)
86 {
87         struct thread *td;
88
89         td = curthread;
90         if (td->td_critnest == 1) {
91                 td->td_critnest = 0;
92                 cpu_critical_exit(td->td_savecrit);
93         } else
94                 td->td_critnest--;
95 }
96
97 /*
98  * Clear the status bit of the queue corresponding to priority level pri,
99  * indicating that it is empty.
100  */
101 static __inline void
102 runq_clrbit(struct runq *rq, int pri)
103 {
104         struct rqbits *rqb;
105
106         rqb = &rq->rq_status;
107         CTR4(KTR_RUNQ, "runq_clrbit: bits=%#x %#x bit=%#x word=%d",
108             rqb->rqb_bits[RQB_WORD(pri)],
109             rqb->rqb_bits[RQB_WORD(pri)] & ~RQB_BIT(pri),
110             RQB_BIT(pri), RQB_WORD(pri));
111         rqb->rqb_bits[RQB_WORD(pri)] &= ~RQB_BIT(pri);
112 }
113
114 /*
115  * Find the index of the first non-empty run queue.  This is done by
116  * scanning the status bits, a set bit indicates a non-empty queue.
117  */
118 static __inline int
119 runq_findbit(struct runq *rq)
120 {
121         struct rqbits *rqb;
122         int pri;
123         int i;
124
125         rqb = &rq->rq_status;
126         for (i = 0; i < RQB_LEN; i++)
127                 if (rqb->rqb_bits[i]) {
128                         pri = (RQB_FFS(rqb->rqb_bits[i]) - 1) +
129                             (i << RQB_L2BPW);
130                         CTR3(KTR_RUNQ, "runq_findbit: bits=%#x i=%d pri=%d",
131                             rqb->rqb_bits[i], i, pri);
132                         return (pri);
133                 }
134
135         return (-1);
136 }
137
138 /*
139  * Set the status bit of the queue corresponding to priority level pri,
140  * indicating that it is non-empty.
141  */
142 static __inline void
143 runq_setbit(struct runq *rq, int pri)
144 {
145         struct rqbits *rqb;
146
147         rqb = &rq->rq_status;
148         CTR4(KTR_RUNQ, "runq_setbit: bits=%#x %#x bit=%#x word=%d",
149             rqb->rqb_bits[RQB_WORD(pri)],
150             rqb->rqb_bits[RQB_WORD(pri)] | RQB_BIT(pri),
151             RQB_BIT(pri), RQB_WORD(pri));
152         rqb->rqb_bits[RQB_WORD(pri)] |= RQB_BIT(pri);
153 }
154
155 #ifdef INVARIANT_SUPPORT
156 /*
157  * Return true if the specified process is already in the run queue.
158  */
159 static __inline int
160 runq_find(struct runq *rq, struct kse *ke)
161 {
162         struct kse *ke2;
163         int i;
164
165         mtx_assert(&sched_lock, MA_OWNED);
166         for (i = 0; i < RQB_LEN; i++)
167                 TAILQ_FOREACH(ke2, &rq->rq_queues[i], ke_procq)
168                     if (ke2 == ke)
169                             return 1;
170         return 0;
171 }
172 #endif
173
174 /*
175  * Add the process to the queue specified by its priority, and set the
176  * corresponding status bit.
177  */
178 void
179 runq_add(struct runq *rq, struct kse *ke)
180 {
181         struct rqhead *rqh;
182         int pri;
183
184         struct ksegrp *kg = ke->ke_ksegrp;
185 #ifdef INVARIANTS
186         struct proc *p = ke->ke_proc;
187 #endif
188         if (ke->ke_flags & KEF_ONRUNQ)
189                 return;
190         mtx_assert(&sched_lock, MA_OWNED);
191         KASSERT(p->p_stat == SRUN, ("runq_add: proc %p (%s) not SRUN",
192             p, p->p_comm));
193         KASSERT(runq_find(rq, ke) == 0,
194             ("runq_add: proc %p (%s) already in run queue", ke, p->p_comm));
195         pri = kg->kg_pri.pri_level / RQ_PPQ;
196         ke->ke_rqindex = pri;
197         runq_setbit(rq, pri);
198         rqh = &rq->rq_queues[pri];
199         CTR4(KTR_RUNQ, "runq_add: p=%p pri=%d %d rqh=%p",
200             ke->ke_proc, kg->kg_pri.pri_level, pri, rqh);
201         TAILQ_INSERT_TAIL(rqh, ke, ke_procq);
202         ke->ke_flags |= KEF_ONRUNQ;
203 }
204
205 /*
206  * Return true if there are runnable processes of any priority on the run
207  * queue, false otherwise.  Has no side effects, does not modify the run
208  * queue structure.
209  */
210 int
211 runq_check(struct runq *rq)
212 {
213         struct rqbits *rqb;
214         int i;
215
216         rqb = &rq->rq_status;
217         for (i = 0; i < RQB_LEN; i++)
218                 if (rqb->rqb_bits[i]) {
219                         CTR2(KTR_RUNQ, "runq_check: bits=%#x i=%d",
220                             rqb->rqb_bits[i], i);
221                         return (1);
222                 }
223         CTR0(KTR_RUNQ, "runq_check: empty");
224
225         return (0);
226 }
227
228 /*
229  * Find and remove the highest priority process from the run queue.
230  * If there are no runnable processes, the per-cpu idle process is
231  * returned.  Will not return NULL under any circumstances.
232  */
233 struct kse *
234 runq_choose(struct runq *rq)
235 {
236         struct rqhead *rqh;
237         struct kse *ke;
238         int pri;
239
240         mtx_assert(&sched_lock, MA_OWNED);
241         if ((pri = runq_findbit(rq)) != -1) {
242                 rqh = &rq->rq_queues[pri];
243                 ke = TAILQ_FIRST(rqh);
244                 KASSERT(ke != NULL, ("runq_choose: no proc on busy queue"));
245                 KASSERT(ke->ke_proc->p_stat == SRUN,
246                     ("runq_choose: process %d(%s) in state %d", ke->ke_proc->p_pid,
247                     ke->ke_proc->p_comm, ke->ke_proc->p_stat));
248                 CTR3(KTR_RUNQ, "runq_choose: pri=%d kse=%p rqh=%p", pri, ke, rqh);
249                 TAILQ_REMOVE(rqh, ke, ke_procq);
250                 if (TAILQ_EMPTY(rqh)) {
251                         CTR0(KTR_RUNQ, "runq_choose: empty");
252                         runq_clrbit(rq, pri);
253                 }
254                 ke->ke_flags &= ~KEF_ONRUNQ;
255                 return (ke);
256         }
257         CTR1(KTR_RUNQ, "runq_choose: idleproc pri=%d", pri);
258
259         return (PCPU_GET(idlethread)->td_kse);
260 }
261
262 /*
263  * Initialize a run structure.
264  */
265 void
266 runq_init(struct runq *rq)
267 {
268         int i;
269
270         bzero(rq, sizeof *rq);
271         for (i = 0; i < RQ_NQS; i++)
272                 TAILQ_INIT(&rq->rq_queues[i]);
273 }
274
275 /*
276  * Remove the process from the queue specified by its priority, and clear the
277  * corresponding status bit if the queue becomes empty.
278  */
279 void
280 runq_remove(struct runq *rq, struct kse *ke)
281 {
282 #ifdef KTR
283         struct ksegrp *kg = ke->ke_ksegrp;
284 #endif
285         struct rqhead *rqh;
286         int pri;
287
288         if (!(ke->ke_flags & KEF_ONRUNQ))
289                 return;
290         mtx_assert(&sched_lock, MA_OWNED);
291         pri = ke->ke_rqindex;
292         rqh = &rq->rq_queues[pri];
293         CTR4(KTR_RUNQ, "runq_remove: p=%p pri=%d %d rqh=%p",
294             ke, kg->kg_pri.pri_level, pri, rqh);
295         KASSERT(ke != NULL, ("runq_remove: no proc on busy queue"));
296         TAILQ_REMOVE(rqh, ke, ke_procq);
297         if (TAILQ_EMPTY(rqh)) {
298                 CTR0(KTR_RUNQ, "runq_remove: empty");
299                 runq_clrbit(rq, pri);
300         }
301         ke->ke_flags &= ~KEF_ONRUNQ;
302 }