kern_sleepq.c revision 1.33 1 1.33 ad /* $NetBSD: kern_sleepq.c,v 1.33 2008/06/17 09:11:25 ad Exp $ */
2 1.2 ad
3 1.2 ad /*-
4 1.22 ad * Copyright (c) 2006, 2007, 2008 The NetBSD Foundation, Inc.
5 1.2 ad * All rights reserved.
6 1.2 ad *
7 1.2 ad * This code is derived from software contributed to The NetBSD Foundation
8 1.2 ad * by Andrew Doran.
9 1.2 ad *
10 1.2 ad * Redistribution and use in source and binary forms, with or without
11 1.2 ad * modification, are permitted provided that the following conditions
12 1.2 ad * are met:
13 1.2 ad * 1. Redistributions of source code must retain the above copyright
14 1.2 ad * notice, this list of conditions and the following disclaimer.
15 1.2 ad * 2. Redistributions in binary form must reproduce the above copyright
16 1.2 ad * notice, this list of conditions and the following disclaimer in the
17 1.2 ad * documentation and/or other materials provided with the distribution.
18 1.2 ad *
19 1.2 ad * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
20 1.2 ad * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
21 1.2 ad * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 1.2 ad * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
23 1.2 ad * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24 1.2 ad * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25 1.2 ad * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26 1.2 ad * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27 1.2 ad * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28 1.2 ad * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29 1.2 ad * POSSIBILITY OF SUCH DAMAGE.
30 1.2 ad */
31 1.2 ad
32 1.2 ad /*
33 1.2 ad * Sleep queue implementation, used by turnstiles and general sleep/wakeup
34 1.2 ad * interfaces.
35 1.2 ad */
36 1.2 ad
37 1.2 ad #include <sys/cdefs.h>
38 1.33 ad __KERNEL_RCSID(0, "$NetBSD: kern_sleepq.c,v 1.33 2008/06/17 09:11:25 ad Exp $");
39 1.2 ad
40 1.2 ad #include <sys/param.h>
41 1.2 ad #include <sys/kernel.h>
42 1.9 yamt #include <sys/cpu.h>
43 1.2 ad #include <sys/pool.h>
44 1.2 ad #include <sys/proc.h>
45 1.2 ad #include <sys/resourcevar.h>
46 1.2 ad #include <sys/sched.h>
47 1.2 ad #include <sys/systm.h>
48 1.2 ad #include <sys/sleepq.h>
49 1.2 ad #include <sys/ktrace.h>
50 1.2 ad
51 1.4 ad #include <uvm/uvm_extern.h>
52 1.4 ad
53 1.8 ad int sleepq_sigtoerror(lwp_t *, int);
54 1.2 ad
55 1.2 ad /* General purpose sleep table, used by ltsleep() and condition variables. */
56 1.2 ad sleeptab_t sleeptab;
57 1.2 ad
58 1.2 ad /*
59 1.2 ad * sleeptab_init:
60 1.2 ad *
61 1.2 ad * Initialize a sleep table.
62 1.2 ad */
63 1.2 ad void
64 1.2 ad sleeptab_init(sleeptab_t *st)
65 1.2 ad {
66 1.2 ad sleepq_t *sq;
67 1.2 ad int i;
68 1.2 ad
69 1.2 ad for (i = 0; i < SLEEPTAB_HASH_SIZE; i++) {
70 1.2 ad sq = &st->st_queues[i].st_queue;
71 1.19 ad mutex_init(&st->st_queues[i].st_mutex, MUTEX_DEFAULT,
72 1.19 ad IPL_SCHED);
73 1.30 ad sleepq_init(sq);
74 1.2 ad }
75 1.2 ad }
76 1.2 ad
77 1.2 ad /*
78 1.2 ad * sleepq_init:
79 1.2 ad *
80 1.2 ad * Prepare a sleep queue for use.
81 1.2 ad */
82 1.2 ad void
83 1.30 ad sleepq_init(sleepq_t *sq)
84 1.2 ad {
85 1.2 ad
86 1.30 ad TAILQ_INIT(sq);
87 1.2 ad }
88 1.2 ad
89 1.2 ad /*
90 1.2 ad * sleepq_remove:
91 1.2 ad *
92 1.2 ad * Remove an LWP from a sleep queue and wake it up. Return non-zero if
93 1.2 ad * the LWP is swapped out; if so the caller needs to awaken the swapper
94 1.2 ad * to bring the LWP into memory.
95 1.2 ad */
96 1.2 ad int
97 1.8 ad sleepq_remove(sleepq_t *sq, lwp_t *l)
98 1.2 ad {
99 1.9 yamt struct schedstate_percpu *spc;
100 1.2 ad struct cpu_info *ci;
101 1.2 ad
102 1.30 ad KASSERT(lwp_locked(l, NULL));
103 1.2 ad
104 1.30 ad TAILQ_REMOVE(sq, l, l_sleepchain);
105 1.2 ad l->l_syncobj = &sched_syncobj;
106 1.2 ad l->l_wchan = NULL;
107 1.2 ad l->l_sleepq = NULL;
108 1.5 pavel l->l_flag &= ~LW_SINTR;
109 1.2 ad
110 1.9 yamt ci = l->l_cpu;
111 1.9 yamt spc = &ci->ci_schedstate;
112 1.9 yamt
113 1.2 ad /*
114 1.2 ad * If not sleeping, the LWP must have been suspended. Let whoever
115 1.2 ad * holds it stopped set it running again.
116 1.2 ad */
117 1.2 ad if (l->l_stat != LSSLEEP) {
118 1.16 rmind KASSERT(l->l_stat == LSSTOP || l->l_stat == LSSUSPENDED);
119 1.21 ad lwp_setlock(l, spc->spc_lwplock);
120 1.2 ad return 0;
121 1.2 ad }
122 1.2 ad
123 1.2 ad /*
124 1.2 ad * If the LWP is still on the CPU, mark it as LSONPROC. It may be
125 1.2 ad * about to call mi_switch(), in which case it will yield.
126 1.2 ad */
127 1.31 ad if ((l->l_pflag & LP_RUNNING) != 0) {
128 1.2 ad l->l_stat = LSONPROC;
129 1.2 ad l->l_slptime = 0;
130 1.21 ad lwp_setlock(l, spc->spc_lwplock);
131 1.2 ad return 0;
132 1.2 ad }
133 1.2 ad
134 1.29 rmind /* Update sleep time delta, call the wake-up handler of scheduler */
135 1.29 rmind l->l_slpticksum += (hardclock_ticks - l->l_slpticks);
136 1.16 rmind sched_wakeup(l);
137 1.29 rmind
138 1.29 rmind /* Look for a CPU to wake up */
139 1.29 rmind l->l_cpu = sched_takecpu(l);
140 1.16 rmind ci = l->l_cpu;
141 1.16 rmind spc = &ci->ci_schedstate;
142 1.16 rmind
143 1.16 rmind /*
144 1.17 yamt * Set it running.
145 1.2 ad */
146 1.9 yamt spc_lock(ci);
147 1.9 yamt lwp_setlock(l, spc->spc_mutex);
148 1.9 yamt sched_setrunnable(l);
149 1.2 ad l->l_stat = LSRUN;
150 1.2 ad l->l_slptime = 0;
151 1.5 pavel if ((l->l_flag & LW_INMEM) != 0) {
152 1.9 yamt sched_enqueue(l, false);
153 1.9 yamt spc_unlock(ci);
154 1.2 ad return 0;
155 1.2 ad }
156 1.9 yamt spc_unlock(ci);
157 1.2 ad return 1;
158 1.2 ad }
159 1.2 ad
160 1.2 ad /*
161 1.2 ad * sleepq_insert:
162 1.2 ad *
163 1.2 ad * Insert an LWP into the sleep queue, optionally sorting by priority.
164 1.2 ad */
165 1.2 ad inline void
166 1.8 ad sleepq_insert(sleepq_t *sq, lwp_t *l, syncobj_t *sobj)
167 1.2 ad {
168 1.8 ad lwp_t *l2;
169 1.6 yamt const int pri = lwp_eprio(l);
170 1.2 ad
171 1.2 ad if ((sobj->sobj_flag & SOBJ_SLEEPQ_SORTED) != 0) {
172 1.30 ad TAILQ_FOREACH(l2, sq, l_sleepchain) {
173 1.18 ad if (lwp_eprio(l2) < pri) {
174 1.2 ad TAILQ_INSERT_BEFORE(l2, l, l_sleepchain);
175 1.2 ad return;
176 1.2 ad }
177 1.2 ad }
178 1.2 ad }
179 1.2 ad
180 1.14 ad if ((sobj->sobj_flag & SOBJ_SLEEPQ_LIFO) != 0)
181 1.30 ad TAILQ_INSERT_HEAD(sq, l, l_sleepchain);
182 1.14 ad else
183 1.30 ad TAILQ_INSERT_TAIL(sq, l, l_sleepchain);
184 1.2 ad }
185 1.2 ad
186 1.9 yamt /*
187 1.9 yamt * sleepq_enqueue:
188 1.9 yamt *
189 1.9 yamt * Enter an LWP into the sleep queue and prepare for sleep. The sleep
190 1.9 yamt * queue must already be locked, and any interlock (such as the kernel
191 1.9 yamt * lock) must have be released (see sleeptab_lookup(), sleepq_enter()).
192 1.9 yamt */
193 1.2 ad void
194 1.18 ad sleepq_enqueue(sleepq_t *sq, wchan_t wchan, const char *wmesg, syncobj_t *sobj)
195 1.2 ad {
196 1.8 ad lwp_t *l = curlwp;
197 1.2 ad
198 1.30 ad KASSERT(lwp_locked(l, NULL));
199 1.2 ad KASSERT(l->l_stat == LSONPROC);
200 1.2 ad KASSERT(l->l_wchan == NULL && l->l_sleepq == NULL);
201 1.2 ad
202 1.2 ad l->l_syncobj = sobj;
203 1.2 ad l->l_wchan = wchan;
204 1.2 ad l->l_sleepq = sq;
205 1.2 ad l->l_wmesg = wmesg;
206 1.2 ad l->l_slptime = 0;
207 1.2 ad l->l_stat = LSSLEEP;
208 1.2 ad l->l_sleeperr = 0;
209 1.2 ad
210 1.6 yamt sleepq_insert(sq, l, sobj);
211 1.29 rmind
212 1.29 rmind /* Save the time when thread has slept */
213 1.29 rmind l->l_slpticks = hardclock_ticks;
214 1.15 rmind sched_slept(l);
215 1.6 yamt }
216 1.6 yamt
217 1.9 yamt /*
218 1.9 yamt * sleepq_block:
219 1.9 yamt *
220 1.9 yamt * After any intermediate step such as releasing an interlock, switch.
221 1.9 yamt * sleepq_block() may return early under exceptional conditions, for
222 1.9 yamt * example if the LWP's containing process is exiting.
223 1.9 yamt */
224 1.9 yamt int
225 1.9 yamt sleepq_block(int timo, bool catch)
226 1.6 yamt {
227 1.10 ad int error = 0, sig;
228 1.9 yamt struct proc *p;
229 1.8 ad lwp_t *l = curlwp;
230 1.11 ad bool early = false;
231 1.2 ad
232 1.12 ad ktrcsw(1, 0);
233 1.4 ad
234 1.2 ad /*
235 1.2 ad * If sleeping interruptably, check for pending signals, exits or
236 1.2 ad * core dump events.
237 1.2 ad */
238 1.2 ad if (catch) {
239 1.5 pavel l->l_flag |= LW_SINTR;
240 1.5 pavel if ((l->l_flag & (LW_CANCELLED|LW_WEXIT|LW_WCORE)) != 0) {
241 1.5 pavel l->l_flag &= ~LW_CANCELLED;
242 1.14 ad error = EINTR;
243 1.14 ad early = true;
244 1.14 ad } else if ((l->l_flag & LW_PENDSIG) != 0 && sigispending(l, 0))
245 1.11 ad early = true;
246 1.2 ad }
247 1.2 ad
248 1.13 yamt if (early) {
249 1.13 yamt /* lwp_unsleep() will release the lock */
250 1.22 ad lwp_unsleep(l, true);
251 1.13 yamt } else {
252 1.11 ad if (timo)
253 1.14 ad callout_schedule(&l->l_timeout_ch, timo);
254 1.11 ad mi_switch(l);
255 1.11 ad
256 1.11 ad /* The LWP and sleep queue are now unlocked. */
257 1.11 ad if (timo) {
258 1.11 ad /*
259 1.11 ad * Even if the callout appears to have fired, we need to
260 1.11 ad * stop it in order to synchronise with other CPUs.
261 1.11 ad */
262 1.26 ad if (callout_halt(&l->l_timeout_ch, NULL))
263 1.11 ad error = EWOULDBLOCK;
264 1.11 ad }
265 1.2 ad }
266 1.2 ad
267 1.9 yamt if (catch && error == 0) {
268 1.2 ad p = l->l_proc;
269 1.5 pavel if ((l->l_flag & (LW_CANCELLED | LW_WEXIT | LW_WCORE)) != 0)
270 1.2 ad error = EINTR;
271 1.5 pavel else if ((l->l_flag & LW_PENDSIG) != 0) {
272 1.33 ad /*
273 1.33 ad * Acquiring p_lock may cause us to recurse
274 1.33 ad * through the sleep path and back into this
275 1.33 ad * routine, but is safe because LWPs sleeping
276 1.33 ad * on locks are non-interruptable. We will
277 1.33 ad * not recurse again.
278 1.33 ad */
279 1.27 ad mutex_enter(p->p_lock);
280 1.2 ad if ((sig = issignal(l)) != 0)
281 1.2 ad error = sleepq_sigtoerror(l, sig);
282 1.27 ad mutex_exit(p->p_lock);
283 1.2 ad }
284 1.2 ad }
285 1.2 ad
286 1.12 ad ktrcsw(0, 0);
287 1.30 ad if (__predict_false(l->l_biglocks != 0)) {
288 1.30 ad KERNEL_LOCK(l->l_biglocks, NULL);
289 1.30 ad }
290 1.2 ad return error;
291 1.2 ad }
292 1.2 ad
293 1.2 ad /*
294 1.2 ad * sleepq_wake:
295 1.2 ad *
296 1.2 ad * Wake zero or more LWPs blocked on a single wait channel.
297 1.2 ad */
298 1.8 ad lwp_t *
299 1.30 ad sleepq_wake(sleepq_t *sq, wchan_t wchan, u_int expected, kmutex_t *mp)
300 1.2 ad {
301 1.8 ad lwp_t *l, *next;
302 1.2 ad int swapin = 0;
303 1.2 ad
304 1.30 ad KASSERT(mutex_owned(mp));
305 1.2 ad
306 1.30 ad for (l = TAILQ_FIRST(sq); l != NULL; l = next) {
307 1.2 ad KASSERT(l->l_sleepq == sq);
308 1.30 ad KASSERT(l->l_mutex == mp);
309 1.2 ad next = TAILQ_NEXT(l, l_sleepchain);
310 1.2 ad if (l->l_wchan != wchan)
311 1.2 ad continue;
312 1.2 ad swapin |= sleepq_remove(sq, l);
313 1.2 ad if (--expected == 0)
314 1.2 ad break;
315 1.2 ad }
316 1.2 ad
317 1.30 ad mutex_spin_exit(mp);
318 1.2 ad
319 1.2 ad /*
320 1.2 ad * If there are newly awakend threads that need to be swapped in,
321 1.2 ad * then kick the swapper into action.
322 1.2 ad */
323 1.2 ad if (swapin)
324 1.4 ad uvm_kick_scheduler();
325 1.8 ad
326 1.8 ad return l;
327 1.2 ad }
328 1.2 ad
329 1.2 ad /*
330 1.2 ad * sleepq_unsleep:
331 1.2 ad *
332 1.2 ad * Remove an LWP from its sleep queue and set it runnable again.
333 1.2 ad * sleepq_unsleep() is called with the LWP's mutex held, and will
334 1.2 ad * always release it.
335 1.2 ad */
336 1.22 ad u_int
337 1.22 ad sleepq_unsleep(lwp_t *l, bool cleanup)
338 1.2 ad {
339 1.2 ad sleepq_t *sq = l->l_sleepq;
340 1.30 ad kmutex_t *mp = l->l_mutex;
341 1.2 ad int swapin;
342 1.2 ad
343 1.30 ad KASSERT(lwp_locked(l, mp));
344 1.2 ad KASSERT(l->l_wchan != NULL);
345 1.2 ad
346 1.2 ad swapin = sleepq_remove(sq, l);
347 1.2 ad
348 1.22 ad if (cleanup) {
349 1.30 ad mutex_spin_exit(mp);
350 1.22 ad if (swapin)
351 1.22 ad uvm_kick_scheduler();
352 1.22 ad }
353 1.22 ad
354 1.22 ad return swapin;
355 1.2 ad }
356 1.2 ad
357 1.2 ad /*
358 1.2 ad * sleepq_timeout:
359 1.2 ad *
360 1.2 ad * Entered via the callout(9) subsystem to time out an LWP that is on a
361 1.2 ad * sleep queue.
362 1.2 ad */
363 1.2 ad void
364 1.2 ad sleepq_timeout(void *arg)
365 1.2 ad {
366 1.8 ad lwp_t *l = arg;
367 1.2 ad
368 1.2 ad /*
369 1.2 ad * Lock the LWP. Assuming it's still on the sleep queue, its
370 1.2 ad * current mutex will also be the sleep queue mutex.
371 1.2 ad */
372 1.2 ad lwp_lock(l);
373 1.2 ad
374 1.2 ad if (l->l_wchan == NULL) {
375 1.2 ad /* Somebody beat us to it. */
376 1.2 ad lwp_unlock(l);
377 1.2 ad return;
378 1.2 ad }
379 1.2 ad
380 1.22 ad lwp_unsleep(l, true);
381 1.2 ad }
382 1.2 ad
383 1.2 ad /*
384 1.2 ad * sleepq_sigtoerror:
385 1.2 ad *
386 1.2 ad * Given a signal number, interpret and return an error code.
387 1.2 ad */
388 1.2 ad int
389 1.8 ad sleepq_sigtoerror(lwp_t *l, int sig)
390 1.2 ad {
391 1.2 ad struct proc *p = l->l_proc;
392 1.2 ad int error;
393 1.2 ad
394 1.27 ad KASSERT(mutex_owned(p->p_lock));
395 1.2 ad
396 1.2 ad /*
397 1.2 ad * If this sleep was canceled, don't let the syscall restart.
398 1.2 ad */
399 1.2 ad if ((SIGACTION(p, sig).sa_flags & SA_RESTART) == 0)
400 1.2 ad error = EINTR;
401 1.2 ad else
402 1.2 ad error = ERESTART;
403 1.2 ad
404 1.2 ad return error;
405 1.2 ad }
406 1.2 ad
407 1.2 ad /*
408 1.2 ad * sleepq_abort:
409 1.2 ad *
410 1.2 ad * After a panic or during autoconfiguration, lower the interrupt
411 1.2 ad * priority level to give pending interrupts a chance to run, and
412 1.2 ad * then return. Called if sleepq_dontsleep() returns non-zero, and
413 1.2 ad * always returns zero.
414 1.2 ad */
415 1.2 ad int
416 1.2 ad sleepq_abort(kmutex_t *mtx, int unlock)
417 1.2 ad {
418 1.2 ad extern int safepri;
419 1.2 ad int s;
420 1.2 ad
421 1.2 ad s = splhigh();
422 1.2 ad splx(safepri);
423 1.2 ad splx(s);
424 1.2 ad if (mtx != NULL && unlock != 0)
425 1.2 ad mutex_exit(mtx);
426 1.2 ad
427 1.2 ad return 0;
428 1.2 ad }
429 1.2 ad
430 1.2 ad /*
431 1.2 ad * sleepq_changepri:
432 1.2 ad *
433 1.2 ad * Adjust the priority of an LWP residing on a sleepq. This method
434 1.2 ad * will only alter the user priority; the effective priority is
435 1.2 ad * assumed to have been fixed at the time of insertion into the queue.
436 1.2 ad */
437 1.2 ad void
438 1.8 ad sleepq_changepri(lwp_t *l, pri_t pri)
439 1.2 ad {
440 1.18 ad sleepq_t *sq = l->l_sleepq;
441 1.18 ad pri_t opri;
442 1.18 ad
443 1.30 ad KASSERT(lwp_locked(l, NULL));
444 1.2 ad
445 1.18 ad opri = lwp_eprio(l);
446 1.18 ad l->l_priority = pri;
447 1.32 ad
448 1.32 ad if (lwp_eprio(l) == opri) {
449 1.32 ad return;
450 1.32 ad }
451 1.32 ad if ((l->l_syncobj->sobj_flag & SOBJ_SLEEPQ_SORTED) == 0) {
452 1.32 ad return;
453 1.32 ad }
454 1.32 ad
455 1.32 ad /*
456 1.32 ad * Don't let the sleep queue become empty, even briefly.
457 1.32 ad * cv_signal() and cv_broadcast() inspect it without the
458 1.32 ad * sleep queue lock held and need to see a non-empty queue
459 1.32 ad * head if there are waiters.
460 1.32 ad */
461 1.32 ad if (TAILQ_FIRST(sq) == l && TAILQ_NEXT(l, l_sleepchain) == NULL) {
462 1.32 ad return;
463 1.18 ad }
464 1.32 ad TAILQ_REMOVE(sq, l, l_sleepchain);
465 1.32 ad sleepq_insert(sq, l, l->l_syncobj);
466 1.2 ad }
467 1.6 yamt
468 1.6 yamt void
469 1.8 ad sleepq_lendpri(lwp_t *l, pri_t pri)
470 1.6 yamt {
471 1.6 yamt sleepq_t *sq = l->l_sleepq;
472 1.7 yamt pri_t opri;
473 1.6 yamt
474 1.30 ad KASSERT(lwp_locked(l, NULL));
475 1.6 yamt
476 1.6 yamt opri = lwp_eprio(l);
477 1.6 yamt l->l_inheritedprio = pri;
478 1.6 yamt
479 1.32 ad if (lwp_eprio(l) == opri) {
480 1.32 ad return;
481 1.32 ad }
482 1.32 ad if ((l->l_syncobj->sobj_flag & SOBJ_SLEEPQ_SORTED) == 0) {
483 1.32 ad return;
484 1.6 yamt }
485 1.32 ad
486 1.32 ad /*
487 1.32 ad * Don't let the sleep queue become empty, even briefly.
488 1.32 ad * cv_signal() and cv_broadcast() inspect it without the
489 1.32 ad * sleep queue lock held and need to see a non-empty queue
490 1.32 ad * head if there are waiters.
491 1.32 ad */
492 1.32 ad if (TAILQ_FIRST(sq) == l && TAILQ_NEXT(l, l_sleepchain) == NULL) {
493 1.32 ad return;
494 1.32 ad }
495 1.32 ad TAILQ_REMOVE(sq, l, l_sleepchain);
496 1.32 ad sleepq_insert(sq, l, l->l_syncobj);
497 1.6 yamt }
498