Annotation of src/sys/kern/kern_sleepq.c, Revision 1.62
1.62 ! ad 1: /* $NetBSD: kern_sleepq.c,v 1.61 2020/02/15 18:12:15 ad Exp $ */
1.2 ad 2:
3: /*-
1.59 ad 4: * Copyright (c) 2006, 2007, 2008, 2009, 2019, 2020 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.62 ! ad 38: __KERNEL_RCSID(0, "$NetBSD: kern_sleepq.c,v 1.61 2020/02/15 18:12:15 ad Exp $");
1.2 ad 39:
40: #include <sys/param.h>
41: #include <sys/kernel.h>
1.9 yamt 42: #include <sys/cpu.h>
1.47 matt 43: #include <sys/intr.h>
1.2 ad 44: #include <sys/pool.h>
45: #include <sys/proc.h>
46: #include <sys/resourcevar.h>
47: #include <sys/sched.h>
48: #include <sys/systm.h>
49: #include <sys/sleepq.h>
50: #include <sys/ktrace.h>
51:
1.47 matt 52: /*
53: * for sleepq_abort:
54: * During autoconfiguration or after a panic, a sleep will simply lower the
55: * priority briefly to allow interrupts, then return. The priority to be
56: * used (IPL_SAFEPRI) is machine-dependent, thus this value is initialized and
57: * maintained in the machine-dependent layers. This priority will typically
58: * be 0, or the lowest priority that is safe for use on the interrupt stack;
59: * it can be made higher to block network software interrupts after panics.
60: */
61: #ifndef IPL_SAFEPRI
62: #define IPL_SAFEPRI 0
63: #endif
64:
1.39 rmind 65: static int sleepq_sigtoerror(lwp_t *, int);
1.2 ad 66:
1.45 rmind 67: /* General purpose sleep table, used by mtsleep() and condition variables. */
1.52 ad 68: sleeptab_t sleeptab __cacheline_aligned;
1.55 ad 69: sleepqlock_t sleepq_locks[SLEEPTAB_HASH_SIZE] __cacheline_aligned;
1.2 ad 70:
71: /*
72: * sleeptab_init:
73: *
74: * Initialize a sleep table.
75: */
76: void
77: sleeptab_init(sleeptab_t *st)
78: {
1.56 ad 79: static bool again;
1.2 ad 80: int i;
81:
82: for (i = 0; i < SLEEPTAB_HASH_SIZE; i++) {
1.56 ad 83: if (!again) {
84: mutex_init(&sleepq_locks[i].lock, MUTEX_DEFAULT,
85: IPL_SCHED);
86: }
1.52 ad 87: sleepq_init(&st->st_queue[i]);
1.2 ad 88: }
1.56 ad 89: again = true;
1.2 ad 90: }
91:
92: /*
93: * sleepq_init:
94: *
95: * Prepare a sleep queue for use.
96: */
97: void
1.30 ad 98: sleepq_init(sleepq_t *sq)
1.2 ad 99: {
100:
1.30 ad 101: TAILQ_INIT(sq);
1.2 ad 102: }
103:
104: /*
105: * sleepq_remove:
106: *
1.37 rmind 107: * Remove an LWP from a sleep queue and wake it up.
1.2 ad 108: */
1.37 rmind 109: void
1.8 ad 110: sleepq_remove(sleepq_t *sq, lwp_t *l)
1.2 ad 111: {
1.9 yamt 112: struct schedstate_percpu *spc;
1.2 ad 113: struct cpu_info *ci;
114:
1.30 ad 115: KASSERT(lwp_locked(l, NULL));
1.2 ad 116:
1.59 ad 117: if ((l->l_syncobj->sobj_flag & SOBJ_SLEEPQ_NULL) == 0) {
118: KASSERT(sq != NULL);
119: TAILQ_REMOVE(sq, l, l_sleepchain);
120: } else {
121: KASSERT(sq == NULL);
122: }
123:
1.2 ad 124: l->l_syncobj = &sched_syncobj;
125: l->l_wchan = NULL;
126: l->l_sleepq = NULL;
1.5 pavel 127: l->l_flag &= ~LW_SINTR;
1.2 ad 128:
1.9 yamt 129: ci = l->l_cpu;
130: spc = &ci->ci_schedstate;
131:
1.2 ad 132: /*
133: * If not sleeping, the LWP must have been suspended. Let whoever
134: * holds it stopped set it running again.
135: */
136: if (l->l_stat != LSSLEEP) {
1.16 rmind 137: KASSERT(l->l_stat == LSSTOP || l->l_stat == LSSUSPENDED);
1.21 ad 138: lwp_setlock(l, spc->spc_lwplock);
1.37 rmind 139: return;
1.2 ad 140: }
141:
142: /*
143: * If the LWP is still on the CPU, mark it as LSONPROC. It may be
144: * about to call mi_switch(), in which case it will yield.
145: */
1.61 ad 146: if ((l->l_pflag & LP_RUNNING) != 0) {
1.2 ad 147: l->l_stat = LSONPROC;
148: l->l_slptime = 0;
1.21 ad 149: lwp_setlock(l, spc->spc_lwplock);
1.37 rmind 150: return;
1.2 ad 151: }
152:
1.29 rmind 153: /* Update sleep time delta, call the wake-up handler of scheduler */
154: l->l_slpticksum += (hardclock_ticks - l->l_slpticks);
1.16 rmind 155: sched_wakeup(l);
1.29 rmind 156:
157: /* Look for a CPU to wake up */
158: l->l_cpu = sched_takecpu(l);
1.16 rmind 159: ci = l->l_cpu;
160: spc = &ci->ci_schedstate;
161:
162: /*
1.17 yamt 163: * Set it running.
1.2 ad 164: */
1.9 yamt 165: spc_lock(ci);
166: lwp_setlock(l, spc->spc_mutex);
167: sched_setrunnable(l);
1.2 ad 168: l->l_stat = LSRUN;
169: l->l_slptime = 0;
1.53 ad 170: sched_enqueue(l);
171: sched_resched_lwp(l, true);
172: /* LWP & SPC now unlocked, but we still hold sleep queue lock. */
1.2 ad 173: }
174:
175: /*
176: * sleepq_insert:
177: *
178: * Insert an LWP into the sleep queue, optionally sorting by priority.
179: */
1.46 rmind 180: static void
1.8 ad 181: sleepq_insert(sleepq_t *sq, lwp_t *l, syncobj_t *sobj)
1.2 ad 182: {
183:
1.59 ad 184: if ((sobj->sobj_flag & SOBJ_SLEEPQ_NULL) != 0) {
185: KASSERT(sq == NULL);
186: return;
187: }
188: KASSERT(sq != NULL);
189:
1.2 ad 190: if ((sobj->sobj_flag & SOBJ_SLEEPQ_SORTED) != 0) {
1.40 yamt 191: lwp_t *l2;
1.60 christos 192: const pri_t pri = lwp_eprio(l);
1.40 yamt 193:
1.30 ad 194: TAILQ_FOREACH(l2, sq, l_sleepchain) {
1.18 ad 195: if (lwp_eprio(l2) < pri) {
1.2 ad 196: TAILQ_INSERT_BEFORE(l2, l, l_sleepchain);
197: return;
198: }
199: }
200: }
201:
1.14 ad 202: if ((sobj->sobj_flag & SOBJ_SLEEPQ_LIFO) != 0)
1.30 ad 203: TAILQ_INSERT_HEAD(sq, l, l_sleepchain);
1.14 ad 204: else
1.30 ad 205: TAILQ_INSERT_TAIL(sq, l, l_sleepchain);
1.2 ad 206: }
207:
1.9 yamt 208: /*
209: * sleepq_enqueue:
210: *
211: * Enter an LWP into the sleep queue and prepare for sleep. The sleep
212: * queue must already be locked, and any interlock (such as the kernel
213: * lock) must have be released (see sleeptab_lookup(), sleepq_enter()).
214: */
1.2 ad 215: void
1.18 ad 216: sleepq_enqueue(sleepq_t *sq, wchan_t wchan, const char *wmesg, syncobj_t *sobj)
1.2 ad 217: {
1.8 ad 218: lwp_t *l = curlwp;
1.2 ad 219:
1.30 ad 220: KASSERT(lwp_locked(l, NULL));
1.2 ad 221: KASSERT(l->l_stat == LSONPROC);
222: KASSERT(l->l_wchan == NULL && l->l_sleepq == NULL);
223:
224: l->l_syncobj = sobj;
225: l->l_wchan = wchan;
226: l->l_sleepq = sq;
227: l->l_wmesg = wmesg;
228: l->l_slptime = 0;
229: l->l_stat = LSSLEEP;
230:
1.6 yamt 231: sleepq_insert(sq, l, sobj);
1.29 rmind 232:
233: /* Save the time when thread has slept */
234: l->l_slpticks = hardclock_ticks;
1.15 rmind 235: sched_slept(l);
1.6 yamt 236: }
237:
1.9 yamt 238: /*
239: * sleepq_block:
240: *
241: * After any intermediate step such as releasing an interlock, switch.
242: * sleepq_block() may return early under exceptional conditions, for
243: * example if the LWP's containing process is exiting.
1.48 apb 244: *
245: * timo is a timeout in ticks. timo = 0 specifies an infinite timeout.
1.9 yamt 246: */
247: int
1.50 matt 248: sleepq_block(int timo, bool catch_p)
1.6 yamt 249: {
1.10 ad 250: int error = 0, sig;
1.9 yamt 251: struct proc *p;
1.8 ad 252: lwp_t *l = curlwp;
1.11 ad 253: bool early = false;
1.34 yamt 254: int biglocks = l->l_biglocks;
1.2 ad 255:
1.12 ad 256: ktrcsw(1, 0);
1.4 ad 257:
1.2 ad 258: /*
259: * If sleeping interruptably, check for pending signals, exits or
260: * core dump events.
261: */
1.50 matt 262: if (catch_p) {
1.5 pavel 263: l->l_flag |= LW_SINTR;
264: if ((l->l_flag & (LW_CANCELLED|LW_WEXIT|LW_WCORE)) != 0) {
265: l->l_flag &= ~LW_CANCELLED;
1.14 ad 266: error = EINTR;
267: early = true;
268: } else if ((l->l_flag & LW_PENDSIG) != 0 && sigispending(l, 0))
1.11 ad 269: early = true;
1.2 ad 270: }
271:
1.13 yamt 272: if (early) {
273: /* lwp_unsleep() will release the lock */
1.22 ad 274: lwp_unsleep(l, true);
1.13 yamt 275: } else {
1.46 rmind 276: if (timo) {
1.14 ad 277: callout_schedule(&l->l_timeout_ch, timo);
1.46 rmind 278: }
1.54 ad 279: spc_lock(l->l_cpu);
1.46 rmind 280: mi_switch(l);
1.11 ad 281:
282: /* The LWP and sleep queue are now unlocked. */
283: if (timo) {
284: /*
1.52 ad 285: * Even if the callout appears to have fired, we
286: * need to stop it in order to synchronise with
287: * other CPUs. It's important that we do this in
288: * this LWP's context, and not during wakeup, in
289: * order to keep the callout & its cache lines
290: * co-located on the CPU with the LWP.
1.11 ad 291: */
1.26 ad 292: if (callout_halt(&l->l_timeout_ch, NULL))
1.11 ad 293: error = EWOULDBLOCK;
294: }
1.2 ad 295: }
296:
1.50 matt 297: if (catch_p && error == 0) {
1.2 ad 298: p = l->l_proc;
1.5 pavel 299: if ((l->l_flag & (LW_CANCELLED | LW_WEXIT | LW_WCORE)) != 0)
1.2 ad 300: error = EINTR;
1.5 pavel 301: else if ((l->l_flag & LW_PENDSIG) != 0) {
1.33 ad 302: /*
303: * Acquiring p_lock may cause us to recurse
304: * through the sleep path and back into this
305: * routine, but is safe because LWPs sleeping
1.62 ! ad 306: * on locks are non-interruptable and we will
1.33 ad 307: * not recurse again.
308: */
1.27 ad 309: mutex_enter(p->p_lock);
1.43 christos 310: if (((sig = sigispending(l, 0)) != 0 &&
311: (sigprop[sig] & SA_STOP) == 0) ||
312: (sig = issignal(l)) != 0)
1.2 ad 313: error = sleepq_sigtoerror(l, sig);
1.27 ad 314: mutex_exit(p->p_lock);
1.2 ad 315: }
316: }
317:
1.12 ad 318: ktrcsw(0, 0);
1.34 yamt 319: if (__predict_false(biglocks != 0)) {
320: KERNEL_LOCK(biglocks, NULL);
1.30 ad 321: }
1.2 ad 322: return error;
323: }
324:
325: /*
326: * sleepq_wake:
327: *
328: * Wake zero or more LWPs blocked on a single wait channel.
329: */
1.49 pooka 330: void
1.30 ad 331: sleepq_wake(sleepq_t *sq, wchan_t wchan, u_int expected, kmutex_t *mp)
1.2 ad 332: {
1.8 ad 333: lwp_t *l, *next;
1.2 ad 334:
1.30 ad 335: KASSERT(mutex_owned(mp));
1.2 ad 336:
1.30 ad 337: for (l = TAILQ_FIRST(sq); l != NULL; l = next) {
1.2 ad 338: KASSERT(l->l_sleepq == sq);
1.30 ad 339: KASSERT(l->l_mutex == mp);
1.2 ad 340: next = TAILQ_NEXT(l, l_sleepchain);
341: if (l->l_wchan != wchan)
342: continue;
1.37 rmind 343: sleepq_remove(sq, l);
1.2 ad 344: if (--expected == 0)
345: break;
346: }
347:
1.30 ad 348: mutex_spin_exit(mp);
1.2 ad 349: }
350:
351: /*
352: * sleepq_unsleep:
353: *
354: * Remove an LWP from its sleep queue and set it runnable again.
355: * sleepq_unsleep() is called with the LWP's mutex held, and will
1.52 ad 356: * release it if "unlock" is true.
1.2 ad 357: */
1.37 rmind 358: void
1.52 ad 359: sleepq_unsleep(lwp_t *l, bool unlock)
1.2 ad 360: {
361: sleepq_t *sq = l->l_sleepq;
1.30 ad 362: kmutex_t *mp = l->l_mutex;
1.2 ad 363:
1.30 ad 364: KASSERT(lwp_locked(l, mp));
1.2 ad 365: KASSERT(l->l_wchan != NULL);
366:
1.37 rmind 367: sleepq_remove(sq, l);
1.52 ad 368: if (unlock) {
1.30 ad 369: mutex_spin_exit(mp);
1.22 ad 370: }
1.2 ad 371: }
372:
373: /*
374: * sleepq_timeout:
375: *
376: * Entered via the callout(9) subsystem to time out an LWP that is on a
377: * sleep queue.
378: */
379: void
380: sleepq_timeout(void *arg)
381: {
1.8 ad 382: lwp_t *l = arg;
1.2 ad 383:
384: /*
385: * Lock the LWP. Assuming it's still on the sleep queue, its
386: * current mutex will also be the sleep queue mutex.
387: */
388: lwp_lock(l);
389:
390: if (l->l_wchan == NULL) {
391: /* Somebody beat us to it. */
392: lwp_unlock(l);
393: return;
394: }
395:
1.22 ad 396: lwp_unsleep(l, true);
1.2 ad 397: }
398:
399: /*
400: * sleepq_sigtoerror:
401: *
402: * Given a signal number, interpret and return an error code.
403: */
1.39 rmind 404: static int
1.8 ad 405: sleepq_sigtoerror(lwp_t *l, int sig)
1.2 ad 406: {
407: struct proc *p = l->l_proc;
408: int error;
409:
1.27 ad 410: KASSERT(mutex_owned(p->p_lock));
1.2 ad 411:
412: /*
413: * If this sleep was canceled, don't let the syscall restart.
414: */
415: if ((SIGACTION(p, sig).sa_flags & SA_RESTART) == 0)
416: error = EINTR;
417: else
418: error = ERESTART;
419:
420: return error;
421: }
422:
423: /*
424: * sleepq_abort:
425: *
426: * After a panic or during autoconfiguration, lower the interrupt
427: * priority level to give pending interrupts a chance to run, and
428: * then return. Called if sleepq_dontsleep() returns non-zero, and
429: * always returns zero.
430: */
431: int
432: sleepq_abort(kmutex_t *mtx, int unlock)
433: {
434: int s;
435:
436: s = splhigh();
1.47 matt 437: splx(IPL_SAFEPRI);
1.2 ad 438: splx(s);
439: if (mtx != NULL && unlock != 0)
440: mutex_exit(mtx);
441:
442: return 0;
443: }
444:
445: /*
1.44 yamt 446: * sleepq_reinsert:
1.2 ad 447: *
1.44 yamt 448: * Move the possition of the lwp in the sleep queue after a possible
449: * change of the lwp's effective priority.
1.2 ad 450: */
1.44 yamt 451: static void
452: sleepq_reinsert(sleepq_t *sq, lwp_t *l)
1.2 ad 453: {
454:
1.44 yamt 455: KASSERT(l->l_sleepq == sq);
1.59 ad 456: if ((l->l_syncobj->sobj_flag & SOBJ_SLEEPQ_SORTED) == 0) {
1.32 ad 457: return;
458: }
459:
460: /*
461: * Don't let the sleep queue become empty, even briefly.
462: * cv_signal() and cv_broadcast() inspect it without the
463: * sleep queue lock held and need to see a non-empty queue
464: * head if there are waiters.
465: */
466: if (TAILQ_FIRST(sq) == l && TAILQ_NEXT(l, l_sleepchain) == NULL) {
467: return;
1.18 ad 468: }
1.32 ad 469: TAILQ_REMOVE(sq, l, l_sleepchain);
470: sleepq_insert(sq, l, l->l_syncobj);
1.2 ad 471: }
1.6 yamt 472:
1.44 yamt 473: /*
474: * sleepq_changepri:
475: *
476: * Adjust the priority of an LWP residing on a sleepq.
477: */
478: void
479: sleepq_changepri(lwp_t *l, pri_t pri)
480: {
481: sleepq_t *sq = l->l_sleepq;
482:
483: KASSERT(lwp_locked(l, NULL));
484:
485: l->l_priority = pri;
486: sleepq_reinsert(sq, l);
487: }
488:
489: /*
490: * sleepq_changepri:
491: *
492: * Adjust the lended priority of an LWP residing on a sleepq.
493: */
1.6 yamt 494: void
1.8 ad 495: sleepq_lendpri(lwp_t *l, pri_t pri)
1.6 yamt 496: {
497: sleepq_t *sq = l->l_sleepq;
498:
1.30 ad 499: KASSERT(lwp_locked(l, NULL));
1.6 yamt 500:
501: l->l_inheritedprio = pri;
1.51 christos 502: l->l_auxprio = MAX(l->l_inheritedprio, l->l_protectprio);
1.44 yamt 503: sleepq_reinsert(sq, l);
1.6 yamt 504: }
CVSweb <webmaster@jp.NetBSD.org>