Home | History | Annotate | Line # | Download | only in kern
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