Home | History | Annotate | Line # | Download | only in kern
kern_turnstile.c revision 1.22
      1 /*	$NetBSD: kern_turnstile.c,v 1.22 2008/05/31 12:03:15 ad Exp $	*/
      2 
      3 /*-
      4  * Copyright (c) 2002, 2006, 2007 The NetBSD Foundation, Inc.
      5  * All rights reserved.
      6  *
      7  * This code is derived from software contributed to The NetBSD Foundation
      8  * by Jason R. Thorpe and 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  * Turnstiles are described in detail in:
     34  *
     35  *	Solaris Internals: Core Kernel Architecture, Jim Mauro and
     36  *	    Richard McDougall.
     37  *
     38  * Turnstiles are kept in a hash table.  There are likely to be many more
     39  * synchronisation objects than there are threads.  Since a thread can block
     40  * on only one lock at a time, we only need one turnstile per thread, and
     41  * so they are allocated at thread creation time.
     42  *
     43  * When a thread decides it needs to block on a lock, it looks up the
     44  * active turnstile for that lock.  If no active turnstile exists, then
     45  * the process lends its turnstile to the lock.  If there is already an
     46  * active turnstile for the lock, the thread places its turnstile on a
     47  * list of free turnstiles, and references the active one instead.
     48  *
     49  * The act of looking up the turnstile acquires an interlock on the sleep
     50  * queue.  If a thread decides it doesn't need to block after all, then this
     51  * interlock must be released by explicitly aborting the turnstile
     52  * operation.
     53  *
     54  * When a thread is awakened, it needs to get its turnstile back.  If there
     55  * are still other threads waiting in the active turnstile, the thread
     56  * grabs a free turnstile off the free list.  Otherwise, it can take back
     57  * the active turnstile from the lock (thus deactivating the turnstile).
     58  *
     59  * Turnstiles are the place to do priority inheritence.
     60  */
     61 
     62 #include <sys/cdefs.h>
     63 __KERNEL_RCSID(0, "$NetBSD: kern_turnstile.c,v 1.22 2008/05/31 12:03:15 ad Exp $");
     64 
     65 #include <sys/param.h>
     66 #include <sys/lockdebug.h>
     67 #include <sys/pool.h>
     68 #include <sys/proc.h>
     69 #include <sys/sleepq.h>
     70 #include <sys/systm.h>
     71 
     72 #include <uvm/uvm_extern.h>
     73 
     74 #define	TS_HASH_SIZE	64
     75 #define	TS_HASH_MASK	(TS_HASH_SIZE - 1)
     76 #define	TS_HASH(obj)	(((uintptr_t)(obj) >> 3) & TS_HASH_MASK)
     77 
     78 tschain_t	turnstile_tab[TS_HASH_SIZE];
     79 pool_cache_t	turnstile_cache;
     80 
     81 int	turnstile_ctor(void *, void *, int);
     82 
     83 extern turnstile_t turnstile0;
     84 
     85 /*
     86  * turnstile_init:
     87  *
     88  *	Initialize the turnstile mechanism.
     89  */
     90 void
     91 turnstile_init(void)
     92 {
     93 	tschain_t *tc;
     94 	int i;
     95 
     96 	for (i = 0; i < TS_HASH_SIZE; i++) {
     97 		tc = &turnstile_tab[i];
     98 		LIST_INIT(&tc->tc_chain);
     99 		mutex_init(&tc->tc_mutex, MUTEX_DEFAULT, IPL_SCHED);
    100 	}
    101 
    102 	turnstile_cache = pool_cache_init(sizeof(turnstile_t), 0, 0, 0,
    103 	    "tstilepl", NULL, IPL_NONE, turnstile_ctor, NULL, NULL);
    104 	KASSERT(turnstile_cache != NULL);
    105 
    106 	(void)turnstile_ctor(NULL, &turnstile0, 0);
    107 }
    108 
    109 /*
    110  * turnstile_ctor:
    111  *
    112  *	Constructor for turnstiles.
    113  */
    114 int
    115 turnstile_ctor(void *arg, void *obj, int flags)
    116 {
    117 	turnstile_t *ts = obj;
    118 
    119 	memset(ts, 0, sizeof(*ts));
    120 	sleepq_init(&ts->ts_sleepq[TS_READER_Q]);
    121 	sleepq_init(&ts->ts_sleepq[TS_WRITER_Q]);
    122 	return (0);
    123 }
    124 
    125 /*
    126  * turnstile_remove:
    127  *
    128  *	Remove an LWP from a turnstile sleep queue and wake it.
    129  */
    130 static inline void
    131 turnstile_remove(turnstile_t *ts, lwp_t *l, int q)
    132 {
    133 	turnstile_t *nts;
    134 
    135 	KASSERT(l->l_ts == ts);
    136 
    137 	/*
    138 	 * This process is no longer using the active turnstile.
    139 	 * Find an inactive one on the free list to give to it.
    140 	 */
    141 	if ((nts = ts->ts_free) != NULL) {
    142 		KASSERT(TS_ALL_WAITERS(ts) > 1);
    143 		l->l_ts = nts;
    144 		ts->ts_free = nts->ts_free;
    145 		nts->ts_free = NULL;
    146 	} else {
    147 		/*
    148 		 * If the free list is empty, this is the last
    149 		 * waiter.
    150 		 */
    151 		KASSERT(TS_ALL_WAITERS(ts) == 1);
    152 		LIST_REMOVE(ts, ts_chain);
    153 	}
    154 
    155 	ts->ts_waiters[q]--;
    156 	(void)sleepq_remove(&ts->ts_sleepq[q], l);
    157 }
    158 
    159 /*
    160  * turnstile_lookup:
    161  *
    162  *	Look up the turnstile for the specified lock.  This acquires and
    163  *	holds the turnstile chain lock (sleep queue interlock).
    164  */
    165 turnstile_t *
    166 turnstile_lookup(wchan_t obj)
    167 {
    168 	turnstile_t *ts;
    169 	tschain_t *tc;
    170 
    171 	tc = &turnstile_tab[TS_HASH(obj)];
    172 	mutex_spin_enter(&tc->tc_mutex);
    173 
    174 	LIST_FOREACH(ts, &tc->tc_chain, ts_chain)
    175 		if (ts->ts_obj == obj)
    176 			return (ts);
    177 
    178 	/*
    179 	 * No turnstile yet for this lock.  No problem, turnstile_block()
    180 	 * handles this by fetching the turnstile from the blocking thread.
    181 	 */
    182 	return (NULL);
    183 }
    184 
    185 /*
    186  * turnstile_exit:
    187  *
    188  *	Abort a turnstile operation.
    189  */
    190 void
    191 turnstile_exit(wchan_t obj)
    192 {
    193 	tschain_t *tc;
    194 
    195 	tc = &turnstile_tab[TS_HASH(obj)];
    196 	mutex_spin_exit(&tc->tc_mutex);
    197 }
    198 
    199 /*
    200  * turnstile_block:
    201  *
    202  *	 Enter an object into the turnstile chain and prepare the current
    203  *	 LWP for sleep.
    204  */
    205 void
    206 turnstile_block(turnstile_t *ts, int q, wchan_t obj, syncobj_t *sobj)
    207 {
    208 	lwp_t *l;
    209 	lwp_t *cur; /* cached curlwp */
    210 	lwp_t *owner;
    211 	turnstile_t *ots;
    212 	tschain_t *tc;
    213 	sleepq_t *sq;
    214 	pri_t prio, obase;
    215 
    216 	tc = &turnstile_tab[TS_HASH(obj)];
    217 	l = cur = curlwp;
    218 
    219 	KASSERT(q == TS_READER_Q || q == TS_WRITER_Q);
    220 	KASSERT(mutex_owned(&tc->tc_mutex));
    221 	KASSERT(l != NULL && l->l_ts != NULL);
    222 
    223 	if (ts == NULL) {
    224 		/*
    225 		 * We are the first thread to wait for this object;
    226 		 * lend our turnstile to it.
    227 		 */
    228 		ts = l->l_ts;
    229 		KASSERT(TS_ALL_WAITERS(ts) == 0);
    230 		KASSERT(TAILQ_EMPTY(&ts->ts_sleepq[TS_READER_Q]) &&
    231 			TAILQ_EMPTY(&ts->ts_sleepq[TS_WRITER_Q]));
    232 		ts->ts_obj = obj;
    233 		ts->ts_inheritor = NULL;
    234 		LIST_INSERT_HEAD(&tc->tc_chain, ts, ts_chain);
    235 	} else {
    236 		/*
    237 		 * Object already has a turnstile.  Put our turnstile
    238 		 * onto the free list, and reference the existing
    239 		 * turnstile instead.
    240 		 */
    241 		ots = l->l_ts;
    242 		ots->ts_free = ts->ts_free;
    243 		ts->ts_free = ots;
    244 		l->l_ts = ts;
    245 
    246 		KASSERT(ts->ts_obj == obj);
    247 		KASSERT(TS_ALL_WAITERS(ts) != 0);
    248 		KASSERT(!TAILQ_EMPTY(&ts->ts_sleepq[TS_READER_Q]) ||
    249 			!TAILQ_EMPTY(&ts->ts_sleepq[TS_WRITER_Q]));
    250 	}
    251 
    252 	sq = &ts->ts_sleepq[q];
    253 	ts->ts_waiters[q]++;
    254 	sleepq_enter(sq, l, &tc->tc_mutex);
    255 	LOCKDEBUG_BARRIER(&tc->tc_mutex, 1);
    256 	l->l_kpriority = true;
    257 	obase = l->l_kpribase;
    258 	if (obase < PRI_KTHREAD)
    259 		l->l_kpribase = PRI_KTHREAD;
    260 	sleepq_enqueue(sq, obj, "tstile", sobj);
    261 
    262 	/*
    263 	 * Disable preemption across this entire block, as we may drop
    264 	 * scheduler locks (allowing preemption), and would prefer not
    265 	 * to be interrupted while in a state of flux.
    266 	 */
    267 	KPREEMPT_DISABLE(l);
    268 
    269 	/*
    270 	 * Lend our priority to lwps on the blocking chain.
    271 	 *
    272 	 * NOTE: if you get a panic in this code block, it is likely that
    273 	 * a lock has been destroyed or corrupted while still in use.  Try
    274 	 * compiling a kernel with LOCKDEBUG to pinpoint the problem.
    275 	 */
    276 	prio = lwp_eprio(l);
    277 	for (;;) {
    278 		bool dolock;
    279 
    280 		if (l->l_wchan == NULL)
    281 			break;
    282 
    283 		owner = (*l->l_syncobj->sobj_owner)(l->l_wchan);
    284 		if (owner == NULL)
    285 			break;
    286 
    287 		KASSERT(l != owner);
    288 		KASSERT(cur != owner);
    289 
    290 		if (l->l_mutex != owner->l_mutex)
    291 			dolock = true;
    292 		else
    293 			dolock = false;
    294 		if (dolock && !lwp_trylock(owner)) {
    295 			/*
    296 			 * restart from curlwp.
    297 			 */
    298 			lwp_unlock(l);
    299 			l = cur;
    300 			lwp_lock(l);
    301 			prio = lwp_eprio(l);
    302 			continue;
    303 		}
    304 		if (prio <= lwp_eprio(owner)) {
    305 			if (dolock)
    306 				lwp_unlock(owner);
    307 			break;
    308 		}
    309 		ts = l->l_ts;
    310 		KASSERT(ts->ts_inheritor == owner || ts->ts_inheritor == NULL);
    311 		if (ts->ts_inheritor == NULL) {
    312 			ts->ts_inheritor = owner;
    313 			ts->ts_eprio = prio;
    314 			SLIST_INSERT_HEAD(&owner->l_pi_lenders, ts, ts_pichain);
    315 			lwp_lendpri(owner, prio);
    316 		} else if (prio > ts->ts_eprio) {
    317 			ts->ts_eprio = prio;
    318 			lwp_lendpri(owner, prio);
    319 		}
    320 		if (dolock)
    321 			lwp_unlock(l);
    322 		l = owner;
    323 	}
    324 	LOCKDEBUG_BARRIER(l->l_mutex, 1);
    325 	if (cur->l_mutex != l->l_mutex) {
    326 		lwp_unlock(l);
    327 		lwp_lock(cur);
    328 	}
    329 	LOCKDEBUG_BARRIER(cur->l_mutex, 1);
    330 
    331 	sleepq_block(0, false);
    332 	cur->l_kpribase = obase;
    333 	KPREEMPT_ENABLE(cur);
    334 }
    335 
    336 /*
    337  * turnstile_wakeup:
    338  *
    339  *	Wake up the specified number of threads that are blocked
    340  *	in a turnstile.
    341  */
    342 void
    343 turnstile_wakeup(turnstile_t *ts, int q, int count, lwp_t *nl)
    344 {
    345 	sleepq_t *sq;
    346 	tschain_t *tc;
    347 	lwp_t *l;
    348 
    349 	tc = &turnstile_tab[TS_HASH(ts->ts_obj)];
    350 	sq = &ts->ts_sleepq[q];
    351 
    352 	KASSERT(q == TS_READER_Q || q == TS_WRITER_Q);
    353 	KASSERT(count > 0 && count <= TS_WAITERS(ts, q));
    354 	KASSERT(mutex_owned(&tc->tc_mutex));
    355 	KASSERT(ts->ts_inheritor == curlwp || ts->ts_inheritor == NULL);
    356 
    357 	/*
    358 	 * restore inherited priority if necessary.
    359 	 */
    360 
    361 	if (ts->ts_inheritor != NULL) {
    362 		turnstile_t *iter;
    363 		turnstile_t *next;
    364 		turnstile_t *prev = NULL;
    365 		pri_t prio;
    366 		bool dolock;
    367 
    368 		ts->ts_inheritor = NULL;
    369 		l = curlwp;
    370 
    371 		dolock = l->l_mutex == l->l_cpu->ci_schedstate.spc_lwplock;
    372 		if (dolock) {
    373 			lwp_lock(l);
    374 		}
    375 
    376 		/*
    377 		 * the following loop does two things.
    378 		 *
    379 		 * - remove ts from the list.
    380 		 *
    381 		 * - from the rest of the list, find the highest priority.
    382 		 */
    383 
    384 		prio = -1;
    385 		KASSERT(!SLIST_EMPTY(&l->l_pi_lenders));
    386 		for (iter = SLIST_FIRST(&l->l_pi_lenders);
    387 		    iter != NULL; iter = next) {
    388 			KASSERT(lwp_eprio(l) >= ts->ts_eprio);
    389 			next = SLIST_NEXT(iter, ts_pichain);
    390 			if (iter == ts) {
    391 				if (prev == NULL) {
    392 					SLIST_REMOVE_HEAD(&l->l_pi_lenders,
    393 					    ts_pichain);
    394 				} else {
    395 					SLIST_REMOVE_AFTER(prev, ts_pichain);
    396 				}
    397 			} else if (prio < iter->ts_eprio) {
    398 				prio = iter->ts_eprio;
    399 			}
    400 			prev = iter;
    401 		}
    402 
    403 		lwp_lendpri(l, prio);
    404 
    405 		if (dolock) {
    406 			lwp_unlock(l);
    407 		}
    408 	}
    409 
    410 	if (nl != NULL) {
    411 #if defined(DEBUG) || defined(LOCKDEBUG)
    412 		TAILQ_FOREACH(l, sq, l_sleepchain) {
    413 			if (l == nl)
    414 				break;
    415 		}
    416 		if (l == NULL)
    417 			panic("turnstile_wakeup: nl not on sleepq");
    418 #endif
    419 		turnstile_remove(ts, nl, q);
    420 	} else {
    421 		while (count-- > 0) {
    422 			l = TAILQ_FIRST(sq);
    423 			KASSERT(l != NULL);
    424 			turnstile_remove(ts, l, q);
    425 		}
    426 	}
    427 	mutex_spin_exit(&tc->tc_mutex);
    428 }
    429 
    430 /*
    431  * turnstile_unsleep:
    432  *
    433  *	Remove an LWP from the turnstile.  This is called when the LWP has
    434  *	not been awoken normally but instead interrupted: for example, if it
    435  *	has received a signal.  It's not a valid action for turnstiles,
    436  *	since LWPs blocking on a turnstile are not interruptable.
    437  */
    438 u_int
    439 turnstile_unsleep(lwp_t *l, bool cleanup)
    440 {
    441 
    442 	lwp_unlock(l);
    443 	panic("turnstile_unsleep");
    444 }
    445 
    446 /*
    447  * turnstile_changepri:
    448  *
    449  *	Adjust the priority of an LWP residing on a turnstile.
    450  */
    451 void
    452 turnstile_changepri(lwp_t *l, pri_t pri)
    453 {
    454 
    455 	/* XXX priority inheritance */
    456 	sleepq_changepri(l, pri);
    457 }
    458 
    459 #if defined(LOCKDEBUG)
    460 /*
    461  * turnstile_print:
    462  *
    463  *	Given the address of a lock object, print the contents of a
    464  *	turnstile.
    465  */
    466 void
    467 turnstile_print(volatile void *obj, void (*pr)(const char *, ...))
    468 {
    469 	turnstile_t *ts;
    470 	tschain_t *tc;
    471 	sleepq_t *rsq, *wsq;
    472 	lwp_t *l;
    473 
    474 	tc = &turnstile_tab[TS_HASH(obj)];
    475 
    476 	LIST_FOREACH(ts, &tc->tc_chain, ts_chain)
    477 		if (ts->ts_obj == obj)
    478 			break;
    479 
    480 	(*pr)("Turnstile chain at %p.\n", tc);
    481 	if (ts == NULL) {
    482 		(*pr)("=> No active turnstile for this lock.\n");
    483 		return;
    484 	}
    485 
    486 	rsq = &ts->ts_sleepq[TS_READER_Q];
    487 	wsq = &ts->ts_sleepq[TS_WRITER_Q];
    488 
    489 	(*pr)("=> Turnstile at %p (wrq=%p, rdq=%p).\n", ts, rsq, wsq);
    490 
    491 	(*pr)("=> %d waiting readers:", TS_WAITERS(ts, TS_READER_Q));
    492 	TAILQ_FOREACH(l, rsq, l_sleepchain) {
    493 		(*pr)(" %p", l);
    494 	}
    495 	(*pr)("\n");
    496 
    497 	(*pr)("=> %d waiting writers:", TS_WAITERS(ts, TS_WRITER_Q));
    498 	TAILQ_FOREACH(l, wsq, l_sleepchain) {
    499 		(*pr)(" %p", l);
    500 	}
    501 	(*pr)("\n");
    502 }
    503 #endif	/* LOCKDEBUG */
    504