xref: /freebsd/sys/kern/kern_switch.c (revision f96ad4c223442d7beefc05399f255dc89b72108e)
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 /*
73  * XXX temporary until these routines are moved fully into MD areas
74  */
75 #ifndef MACHINE_CRITICAL_ENTER
76 
77 /* Critical sections that prevent preemption. */
78 void
79 critical_enter(void)
80 {
81 	struct thread *td;
82 
83 	td = curthread;
84 	if (td->td_critnest == 0)
85 		td->td_savecrit = cpu_critical_enter();
86 	td->td_critnest++;
87 }
88 
89 void
90 critical_exit(void)
91 {
92 	struct thread *td;
93 
94 	td = curthread;
95 	if (td->td_critnest == 1) {
96 		td->td_critnest = 0;
97 		cpu_critical_exit(td->td_savecrit);
98 	} else
99 		td->td_critnest--;
100 }
101 
102 #endif
103 
104 /*
105  * Clear the status bit of the queue corresponding to priority level pri,
106  * indicating that it is empty.
107  */
108 static __inline void
109 runq_clrbit(struct runq *rq, int pri)
110 {
111 	struct rqbits *rqb;
112 
113 	rqb = &rq->rq_status;
114 	CTR4(KTR_RUNQ, "runq_clrbit: bits=%#x %#x bit=%#x word=%d",
115 	    rqb->rqb_bits[RQB_WORD(pri)],
116 	    rqb->rqb_bits[RQB_WORD(pri)] & ~RQB_BIT(pri),
117 	    RQB_BIT(pri), RQB_WORD(pri));
118 	rqb->rqb_bits[RQB_WORD(pri)] &= ~RQB_BIT(pri);
119 }
120 
121 /*
122  * Find the index of the first non-empty run queue.  This is done by
123  * scanning the status bits, a set bit indicates a non-empty queue.
124  */
125 static __inline int
126 runq_findbit(struct runq *rq)
127 {
128 	struct rqbits *rqb;
129 	int pri;
130 	int i;
131 
132 	rqb = &rq->rq_status;
133 	for (i = 0; i < RQB_LEN; i++)
134 		if (rqb->rqb_bits[i]) {
135 			pri = (RQB_FFS(rqb->rqb_bits[i]) - 1) +
136 			    (i << RQB_L2BPW);
137 			CTR3(KTR_RUNQ, "runq_findbit: bits=%#x i=%d pri=%d",
138 			    rqb->rqb_bits[i], i, pri);
139 			return (pri);
140 		}
141 
142 	return (-1);
143 }
144 
145 /*
146  * Set the status bit of the queue corresponding to priority level pri,
147  * indicating that it is non-empty.
148  */
149 static __inline void
150 runq_setbit(struct runq *rq, int pri)
151 {
152 	struct rqbits *rqb;
153 
154 	rqb = &rq->rq_status;
155 	CTR4(KTR_RUNQ, "runq_setbit: bits=%#x %#x bit=%#x word=%d",
156 	    rqb->rqb_bits[RQB_WORD(pri)],
157 	    rqb->rqb_bits[RQB_WORD(pri)] | RQB_BIT(pri),
158 	    RQB_BIT(pri), RQB_WORD(pri));
159 	rqb->rqb_bits[RQB_WORD(pri)] |= RQB_BIT(pri);
160 }
161 
162 #ifdef INVARIANT_SUPPORT
163 /*
164  * Return true if the specified process is already in the run queue.
165  */
166 static __inline int
167 runq_find(struct runq *rq, struct kse *ke)
168 {
169 	struct kse *ke2;
170 	int i;
171 
172 	mtx_assert(&sched_lock, MA_OWNED);
173 	for (i = 0; i < RQB_LEN; i++)
174 		TAILQ_FOREACH(ke2, &rq->rq_queues[i], ke_procq)
175 		    if (ke2 == ke)
176 			    return 1;
177 	return 0;
178 }
179 #endif
180 
181 /*
182  * Add the process to the queue specified by its priority, and set the
183  * corresponding status bit.
184  */
185 void
186 runq_add(struct runq *rq, struct kse *ke)
187 {
188 	struct rqhead *rqh;
189 	int pri;
190 
191 #ifdef INVARIANTS
192 	struct proc *p = ke->ke_proc;
193 #endif
194 	if (ke->ke_flags & KEF_ONRUNQ)
195 		return;
196 	mtx_assert(&sched_lock, MA_OWNED);
197 	KASSERT(p->p_stat == SRUN, ("runq_add: proc %p (%s) not SRUN",
198 	    p, p->p_comm));
199 	KASSERT(runq_find(rq, ke) == 0,
200 	    ("runq_add: proc %p (%s) already in run queue", ke, p->p_comm));
201 	pri = ke->ke_thread->td_priority / RQ_PPQ;
202 	ke->ke_rqindex = pri;
203 	runq_setbit(rq, pri);
204 	rqh = &rq->rq_queues[pri];
205 	CTR4(KTR_RUNQ, "runq_add: p=%p pri=%d %d rqh=%p",
206 	    ke->ke_proc, ke->ke_thread->td_priority, pri, rqh);
207 	TAILQ_INSERT_TAIL(rqh, ke, ke_procq);
208 	ke->ke_flags |= KEF_ONRUNQ;
209 }
210 
211 /*
212  * Return true if there are runnable processes of any priority on the run
213  * queue, false otherwise.  Has no side effects, does not modify the run
214  * queue structure.
215  */
216 int
217 runq_check(struct runq *rq)
218 {
219 	struct rqbits *rqb;
220 	int i;
221 
222 	rqb = &rq->rq_status;
223 	for (i = 0; i < RQB_LEN; i++)
224 		if (rqb->rqb_bits[i]) {
225 			CTR2(KTR_RUNQ, "runq_check: bits=%#x i=%d",
226 			    rqb->rqb_bits[i], i);
227 			return (1);
228 		}
229 	CTR0(KTR_RUNQ, "runq_check: empty");
230 
231 	return (0);
232 }
233 
234 /*
235  * Find and remove the highest priority process from the run queue.
236  * If there are no runnable processes, the per-cpu idle process is
237  * returned.  Will not return NULL under any circumstances.
238  */
239 struct kse *
240 runq_choose(struct runq *rq)
241 {
242 	struct rqhead *rqh;
243 	struct kse *ke;
244 	int pri;
245 
246 	mtx_assert(&sched_lock, MA_OWNED);
247 	if ((pri = runq_findbit(rq)) != -1) {
248 		rqh = &rq->rq_queues[pri];
249 		ke = TAILQ_FIRST(rqh);
250 		KASSERT(ke != NULL, ("runq_choose: no proc on busy queue"));
251 		KASSERT(ke->ke_proc->p_stat == SRUN,
252 		    ("runq_choose: process %d(%s) in state %d", ke->ke_proc->p_pid,
253 		    ke->ke_proc->p_comm, ke->ke_proc->p_stat));
254 		CTR3(KTR_RUNQ, "runq_choose: pri=%d kse=%p rqh=%p", pri, ke, rqh);
255 		TAILQ_REMOVE(rqh, ke, ke_procq);
256 		if (TAILQ_EMPTY(rqh)) {
257 			CTR0(KTR_RUNQ, "runq_choose: empty");
258 			runq_clrbit(rq, pri);
259 		}
260 		ke->ke_flags &= ~KEF_ONRUNQ;
261 		return (ke);
262 	}
263 	CTR1(KTR_RUNQ, "runq_choose: idleproc pri=%d", pri);
264 
265 	return (PCPU_GET(idlethread)->td_kse);
266 }
267 
268 /*
269  * Initialize a run structure.
270  */
271 void
272 runq_init(struct runq *rq)
273 {
274 	int i;
275 
276 	bzero(rq, sizeof *rq);
277 	for (i = 0; i < RQ_NQS; i++)
278 		TAILQ_INIT(&rq->rq_queues[i]);
279 }
280 
281 /*
282  * Remove the process from the queue specified by its priority, and clear the
283  * corresponding status bit if the queue becomes empty.
284  */
285 void
286 runq_remove(struct runq *rq, struct kse *ke)
287 {
288 	struct rqhead *rqh;
289 	int pri;
290 
291 	if (!(ke->ke_flags & KEF_ONRUNQ))
292 		return;
293 	mtx_assert(&sched_lock, MA_OWNED);
294 	pri = ke->ke_rqindex;
295 	rqh = &rq->rq_queues[pri];
296 	CTR4(KTR_RUNQ, "runq_remove: p=%p pri=%d %d rqh=%p",
297 	    ke, ke->ke_thread->td_priority, pri, rqh);
298 	KASSERT(ke != NULL, ("runq_remove: no proc on busy queue"));
299 	TAILQ_REMOVE(rqh, ke, ke_procq);
300 	if (TAILQ_EMPTY(rqh)) {
301 		CTR0(KTR_RUNQ, "runq_remove: empty");
302 		runq_clrbit(rq, pri);
303 	}
304 	ke->ke_flags &= ~KEF_ONRUNQ;
305 }
306