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