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