xref: /titanic_41/usr/src/uts/common/os/turnstile.c (revision cde2885fdf538266ee2a3b08dee2d5075ce8fa2b)
1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License (the "License").
6  * You may not use this file except in compliance with the License.
7  *
8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9  * or http://www.opensolaris.org/os/licensing.
10  * See the License for the specific language governing permissions
11  * and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL HEADER in each
14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15  * If applicable, add the following below this CDDL HEADER, with the
16  * fields enclosed by brackets "[]" replaced with your own identifying
17  * information: Portions Copyright [yyyy] [name of copyright owner]
18  *
19  * CDDL HEADER END
20  */
21 
22 /*
23  * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
24  * Use is subject to license terms.
25  */
26 
27 /*
28  * Big Theory Statement for turnstiles.
29  *
30  * Turnstiles provide blocking and wakeup support, including priority
31  * inheritance, for synchronization primitives (e.g. mutexes and rwlocks).
32  * Typical usage is as follows:
33  *
34  * To block on lock 'lp' for read access in foo_enter():
35  *
36  *	ts = turnstile_lookup(lp);
37  *	[ If the lock is still held, set the waiters bit
38  *	turnstile_block(ts, TS_READER_Q, lp, &foo_sobj_ops);
39  *
40  * To wake threads waiting for write access to lock 'lp' in foo_exit():
41  *
42  *	ts = turnstile_lookup(lp);
43  *	[ Either drop the lock (change owner to NULL) or perform a direct
44  *	[ handoff (change owner to one of the threads we're about to wake).
45  *	[ If we're going to wake the last waiter, clear the waiters bit.
46  *	turnstile_wakeup(ts, TS_WRITER_Q, nwaiters, new_owner or NULL);
47  *
48  * turnstile_lookup() returns holding the turnstile hash chain lock for lp.
49  * Both turnstile_block() and turnstile_wakeup() drop the turnstile lock.
50  * To abort a turnstile operation, the client must call turnstile_exit().
51  *
52  * Requirements of the client:
53  *
54  * (1)  The lock's waiters indicator may be manipulated *only* while
55  *	holding the turnstile hash chain lock (i.e. under turnstile_lookup()).
56  *
57  * (2)	Once the lock is marked as having waiters, the owner may be
58  *	changed *only* while holding the turnstile hash chain lock.
59  *
60  * (3)	The caller must never block on an unheld lock.
61  *
62  * Consequences of these assumptions include the following:
63  *
64  * (a) It is impossible for a lock to be unheld but have waiters.
65  *
66  * (b)	The priority inheritance code can safely assume that an active
67  *	turnstile's ts_inheritor never changes until the inheritor calls
68  *	turnstile_pi_waive().
69  *
70  * These assumptions simplify the implementation of both turnstiles and
71  * their clients.
72  *
73  * Background on priority inheritance:
74  *
75  * Priority inheritance allows a thread to "will" its dispatch priority
76  * to all the threads blocking it, directly or indirectly.  This prevents
77  * situations called priority inversions in which a high-priority thread
78  * needs a lock held by a low-priority thread, which cannot run because
79  * of medium-priority threads.  Without PI, the medium-priority threads
80  * can starve out the high-priority thread indefinitely.  With PI, the
81  * low-priority thread becomes high-priority until it releases whatever
82  * synchronization object the real high-priority thread is waiting for.
83  *
84  * How turnstiles work:
85  *
86  * All active turnstiles reside in a global hash table, turnstile_table[].
87  * The address of a synchronization object determines its hash index.
88  * Each hash chain is protected by its own dispatcher lock, acquired
89  * by turnstile_lookup().  This lock protects the hash chain linkage, the
90  * contents of all turnstiles on the hash chain, and the waiters bits of
91  * every synchronization object in the system that hashes to the same chain.
92  * Giving the lock such broad scope simplifies the interactions between
93  * the turnstile code and its clients considerably.  The blocking path
94  * is rare enough that this has no impact on scalability.  (If it ever
95  * does, it's almost surely a second-order effect -- the real problem
96  * is that some synchronization object is *very* heavily contended.)
97  *
98  * Each thread has an attached turnstile in case it needs to block.
99  * A thread cannot block on more than one lock at a time, so one
100  * turnstile per thread is the most we ever need.  The first thread
101  * to block on a lock donates its attached turnstile and adds it to
102  * the appropriate hash chain in turnstile_table[].  This becomes the
103  * "active turnstile" for the lock.  Each subsequent thread that blocks
104  * on the same lock discovers that the lock already has an active
105  * turnstile, so it stashes its own turnstile on the active turnstile's
106  * freelist.  As threads wake up, the process is reversed.
107  *
108  * turnstile_block() puts the current thread to sleep on the active
109  * turnstile for the desired lock, walks the blocking chain to apply
110  * priority inheritance to everyone in its way, and yields the CPU.
111  *
112  * turnstile_wakeup() waives any priority the owner may have inherited
113  * and wakes the specified number of waiting threads.  If the caller is
114  * doing direct handoff of ownership (rather than just dropping the lock),
115  * the new owner automatically inherits priority from any existing waiters.
116  */
117 
118 #include <sys/param.h>
119 #include <sys/systm.h>
120 #include <sys/thread.h>
121 #include <sys/proc.h>
122 #include <sys/debug.h>
123 #include <sys/cpuvar.h>
124 #include <sys/turnstile.h>
125 #include <sys/t_lock.h>
126 #include <sys/disp.h>
127 #include <sys/sobject.h>
128 #include <sys/cmn_err.h>
129 #include <sys/sysmacros.h>
130 #include <sys/lockstat.h>
131 #include <sys/lwp_upimutex_impl.h>
132 #include <sys/schedctl.h>
133 #include <sys/cpu.h>
134 #include <sys/sdt.h>
135 #include <sys/cpupart.h>
136 
137 extern upib_t upimutextab[UPIMUTEX_TABSIZE];
138 
139 #define	IS_UPI(sobj)	\
140 	((uintptr_t)(sobj) - (uintptr_t)upimutextab < sizeof (upimutextab))
141 
142 /*
143  * The turnstile hash table is partitioned into two halves: the lower half
144  * is used for upimutextab[] locks, the upper half for everything else.
145  * The reason for the distinction is that SOBJ_USER_PI locks present a
146  * unique problem: the upimutextab[] lock passed to turnstile_block()
147  * cannot be dropped until the calling thread has blocked on its
148  * SOBJ_USER_PI lock and willed its priority down the blocking chain.
149  * At that point, the caller's t_lockp will be one of the turnstile locks.
150  * If mutex_exit() discovers that the upimutextab[] lock has waiters, it
151  * must wake them, which forces a lock ordering on us: the turnstile lock
152  * for the upimutextab[] lock will be acquired in mutex_vector_exit(),
153  * which will eventually call into turnstile_pi_waive(), which will then
154  * acquire the caller's thread lock, which in this case is the turnstile
155  * lock for the SOBJ_USER_PI lock.  In general, when two turnstile locks
156  * must be held at the same time, the lock order must be the address order.
157  * Therefore, to prevent deadlock in turnstile_pi_waive(), we must ensure
158  * that upimutextab[] locks *always* hash to lower addresses than any
159  * other locks.  You think this is cheesy?  Let's see you do better.
160  */
161 #define	TURNSTILE_HASH_SIZE	128		/* must be power of 2 */
162 #define	TURNSTILE_HASH_MASK	(TURNSTILE_HASH_SIZE - 1)
163 #define	TURNSTILE_SOBJ_HASH(sobj)	\
164 	((((ulong_t)sobj >> 2) + ((ulong_t)sobj >> 9)) & TURNSTILE_HASH_MASK)
165 #define	TURNSTILE_SOBJ_BUCKET(sobj)		\
166 	((IS_UPI(sobj) ? 0 : TURNSTILE_HASH_SIZE) + TURNSTILE_SOBJ_HASH(sobj))
167 #define	TURNSTILE_CHAIN(sobj)	turnstile_table[TURNSTILE_SOBJ_BUCKET(sobj)]
168 
169 typedef struct turnstile_chain {
170 	turnstile_t	*tc_first;	/* first turnstile on hash chain */
171 	disp_lock_t	tc_lock;	/* lock for this hash chain */
172 } turnstile_chain_t;
173 
174 turnstile_chain_t	turnstile_table[2 * TURNSTILE_HASH_SIZE];
175 
176 static	lock_t	turnstile_loser_lock;
177 
178 /*
179  * Make 'inheritor' inherit priority from this turnstile.
180  */
181 static void
182 turnstile_pi_inherit(turnstile_t *ts, kthread_t *inheritor, pri_t epri)
183 {
184 	ASSERT(THREAD_LOCK_HELD(inheritor));
185 	ASSERT(DISP_LOCK_HELD(&TURNSTILE_CHAIN(ts->ts_sobj).tc_lock));
186 
187 	if (epri <= inheritor->t_pri)
188 		return;
189 
190 	if (ts->ts_inheritor == NULL) {
191 		ts->ts_inheritor = inheritor;
192 		ts->ts_epri = epri;
193 		disp_lock_enter_high(&inheritor->t_pi_lock);
194 		ts->ts_prioinv = inheritor->t_prioinv;
195 		inheritor->t_prioinv = ts;
196 		disp_lock_exit_high(&inheritor->t_pi_lock);
197 	} else {
198 		/*
199 		 * 'inheritor' is already inheriting from this turnstile,
200 		 * so just adjust its priority.
201 		 */
202 		ASSERT(ts->ts_inheritor == inheritor);
203 		if (ts->ts_epri < epri)
204 			ts->ts_epri = epri;
205 	}
206 
207 	if (epri > DISP_PRIO(inheritor))
208 		thread_change_epri(inheritor, epri);
209 }
210 
211 /*
212  * If turnstile is non-NULL, remove it from inheritor's t_prioinv list.
213  * Compute new inherited priority, and return it.
214  */
215 static pri_t
216 turnstile_pi_tsdelete(turnstile_t *ts, kthread_t *inheritor)
217 {
218 	turnstile_t **tspp, *tsp;
219 	pri_t new_epri = 0;
220 
221 	disp_lock_enter_high(&inheritor->t_pi_lock);
222 	tspp = &inheritor->t_prioinv;
223 	while ((tsp = *tspp) != NULL) {
224 		if (tsp == ts)
225 			*tspp = tsp->ts_prioinv;
226 		else
227 			new_epri = MAX(new_epri, tsp->ts_epri);
228 		tspp = &tsp->ts_prioinv;
229 	}
230 	disp_lock_exit_high(&inheritor->t_pi_lock);
231 	return (new_epri);
232 }
233 
234 /*
235  * Remove turnstile from inheritor's t_prioinv list, compute
236  * new priority, and change the inheritor's effective priority if
237  * necessary. Keep in synch with turnstile_pi_recalc().
238  */
239 static void
240 turnstile_pi_waive(turnstile_t *ts)
241 {
242 	kthread_t *inheritor = ts->ts_inheritor;
243 	pri_t new_epri;
244 
245 	ASSERT(inheritor == curthread);
246 
247 	thread_lock_high(inheritor);
248 	new_epri = turnstile_pi_tsdelete(ts, inheritor);
249 	if (new_epri != DISP_PRIO(inheritor))
250 		thread_change_epri(inheritor, new_epri);
251 	ts->ts_inheritor = NULL;
252 	if (DISP_MUST_SURRENDER(inheritor))
253 		cpu_surrender(inheritor);
254 	thread_unlock_high(inheritor);
255 }
256 
257 /*
258  * Compute caller's new inherited priority, and change its effective
259  * priority if necessary. Necessary only for SOBJ_USER_PI, because of
260  * its interruptibility characteristic.
261  */
262 void
263 turnstile_pi_recalc(void)
264 {
265 	kthread_t *inheritor = curthread;
266 	pri_t new_epri;
267 
268 	thread_lock(inheritor);
269 	new_epri = turnstile_pi_tsdelete(NULL, inheritor);
270 	if (new_epri != DISP_PRIO(inheritor))
271 		thread_change_epri(inheritor, new_epri);
272 	if (DISP_MUST_SURRENDER(inheritor))
273 		cpu_surrender(inheritor);
274 	thread_unlock(inheritor);
275 }
276 
277 /*
278  * Grab the lock protecting the hash chain for sobj
279  * and return the active turnstile for sobj, if any.
280  */
281 turnstile_t *
282 turnstile_lookup(void *sobj)
283 {
284 	turnstile_t *ts;
285 	turnstile_chain_t *tc = &TURNSTILE_CHAIN(sobj);
286 
287 	disp_lock_enter(&tc->tc_lock);
288 
289 	for (ts = tc->tc_first; ts != NULL; ts = ts->ts_next)
290 		if (ts->ts_sobj == sobj)
291 			break;
292 
293 	return (ts);
294 }
295 
296 /*
297  * Drop the lock protecting the hash chain for sobj.
298  */
299 void
300 turnstile_exit(void *sobj)
301 {
302 	disp_lock_exit(&TURNSTILE_CHAIN(sobj).tc_lock);
303 }
304 
305 /*
306  * When we apply priority inheritance, we must grab the owner's thread lock
307  * while already holding the waiter's thread lock.  If both thread locks are
308  * turnstile locks, this can lead to deadlock: while we hold L1 and try to
309  * grab L2, some unrelated thread may be applying priority inheritance to
310  * some other blocking chain, holding L2 and trying to grab L1.  The most
311  * obvious solution -- do a lock_try() for the owner lock -- isn't quite
312  * sufficient because it can cause livelock: each thread may hold one lock,
313  * try to grab the other, fail, bail out, and try again, looping forever.
314  * To prevent livelock we must define a winner, i.e. define an arbitrary
315  * lock ordering on the turnstile locks.  For simplicity we declare that
316  * virtual address order defines lock order, i.e. if L1 < L2, then the
317  * correct lock ordering is L1, L2.  Thus the thread that holds L1 and
318  * wants L2 should spin until L2 is available, but the thread that holds
319  * L2 and can't get L1 on the first try must drop L2 and return failure.
320  * Moreover, the losing thread must not reacquire L2 until the winning
321  * thread has had a chance to grab it; to ensure this, the losing thread
322  * must grab L1 after dropping L2, thus spinning until the winner is done.
323  * Complicating matters further, note that the owner's thread lock pointer
324  * can change (i.e. be pointed at a different lock) while we're trying to
325  * grab it.  If that happens, we must unwind our state and try again.
326  *
327  * On success, returns 1 with both locks held.
328  * On failure, returns 0 with neither lock held.
329  */
330 static int
331 turnstile_interlock(lock_t *wlp, lock_t *volatile *olpp)
332 {
333 	ASSERT(LOCK_HELD(wlp));
334 
335 	for (;;) {
336 		volatile lock_t *olp = *olpp;
337 
338 		/*
339 		 * If the locks are identical, there's nothing to do.
340 		 */
341 		if (olp == wlp)
342 			return (1);
343 		if (lock_try((lock_t *)olp)) {
344 			/*
345 			 * If 'olp' is still the right lock, return success.
346 			 * Otherwise, drop 'olp' and try the dance again.
347 			 */
348 			if (olp == *olpp)
349 				return (1);
350 			lock_clear((lock_t *)olp);
351 		} else {
352 			hrtime_t spin_time = 0;
353 			/*
354 			 * If we're grabbing the locks out of order, we lose.
355 			 * Drop the waiter's lock, and then grab and release
356 			 * the owner's lock to ensure that we won't retry
357 			 * until the winner is done (as described above).
358 			 */
359 			if (olp >= (lock_t *)turnstile_table && olp < wlp) {
360 				lock_clear(wlp);
361 				lock_set((lock_t *)olp);
362 				lock_clear((lock_t *)olp);
363 				return (0);
364 			}
365 			/*
366 			 * We're grabbing the locks in the right order,
367 			 * so spin until the owner's lock either becomes
368 			 * available or spontaneously changes.
369 			 */
370 			spin_time =
371 			    LOCKSTAT_START_TIME(LS_TURNSTILE_INTERLOCK_SPIN);
372 			while (olp == *olpp && LOCK_HELD(olp)) {
373 				if (panicstr)
374 					return (1);
375 				SMT_PAUSE();
376 			}
377 			LOCKSTAT_RECORD_TIME(LS_TURNSTILE_INTERLOCK_SPIN,
378 			    olp, spin_time);
379 		}
380 	}
381 }
382 
383 /*
384  * Block the current thread on a synchronization object.
385  *
386  * Turnstiles implement both kernel and user-level priority inheritance.
387  * To avoid missed wakeups in the user-level case, lwp_upimutex_lock() calls
388  * turnstile_block() holding the appropriate lock in the upimutextab (see
389  * the block comment in lwp_upimutex_lock() for details).  The held lock is
390  * passed to turnstile_block() as the "mp" parameter, and will be dropped
391  * after priority has been willed, but before the thread actually sleeps
392  * (this locking behavior leads to some subtle ordering issues; see the
393  * block comment on turnstile hashing for details).  This _must_ be the only
394  * lock held when calling turnstile_block() with a SOBJ_USER_PI sobj; holding
395  * other locks can result in panics due to cycles in the blocking chain.
396  *
397  * turnstile_block() always succeeds for kernel synchronization objects.
398  * For SOBJ_USER_PI locks the possible errors are EINTR for signals, and
399  * EDEADLK for cycles in the blocking chain. A return code of zero indicates
400  * *either* that the lock is now held, or that this is a spurious wake-up, or
401  * that the lock can never be held due to an ENOTRECOVERABLE error.
402  * It is up to lwp_upimutex_lock() to sort this all out.
403  */
404 
405 int
406 turnstile_block(turnstile_t *ts, int qnum, void *sobj, sobj_ops_t *sobj_ops,
407     kmutex_t *mp, lwp_timer_t *lwptp)
408 {
409 	kthread_t *owner;
410 	kthread_t *t = curthread;
411 	proc_t *p = ttoproc(t);
412 	klwp_t *lwp = ttolwp(t);
413 	turnstile_chain_t *tc = &TURNSTILE_CHAIN(sobj);
414 	int error = 0;
415 	int loser = 0;
416 
417 	ASSERT(DISP_LOCK_HELD(&tc->tc_lock));
418 	ASSERT(mp == NULL || IS_UPI(mp));
419 	ASSERT((SOBJ_TYPE(sobj_ops) == SOBJ_USER_PI) ^ (mp == NULL));
420 
421 	thread_lock_high(t);
422 
423 	if (ts == NULL) {
424 		/*
425 		 * This is the first thread to block on this sobj.
426 		 * Take its attached turnstile and add it to the hash chain.
427 		 */
428 		ts = t->t_ts;
429 		ts->ts_sobj = sobj;
430 		ts->ts_next = tc->tc_first;
431 		tc->tc_first = ts;
432 		ASSERT(ts->ts_waiters == 0);
433 	} else {
434 		/*
435 		 * Another thread has already donated its turnstile
436 		 * to block on this sobj, so ours isn't needed.
437 		 * Stash it on the active turnstile's freelist.
438 		 */
439 		turnstile_t *myts = t->t_ts;
440 		myts->ts_free = ts->ts_free;
441 		ts->ts_free = myts;
442 		t->t_ts = ts;
443 		ASSERT(ts->ts_sobj == sobj);
444 		ASSERT(ts->ts_waiters > 0);
445 	}
446 
447 	/*
448 	 * Put the thread to sleep.
449 	 */
450 	ASSERT(t != CPU->cpu_idle_thread);
451 	ASSERT(CPU_ON_INTR(CPU) == 0);
452 	ASSERT(t->t_wchan0 == NULL && t->t_wchan == NULL);
453 	ASSERT(t->t_state == TS_ONPROC);
454 
455 	if (SOBJ_TYPE(sobj_ops) == SOBJ_USER_PI) {
456 		curthread->t_flag |= T_WAKEABLE;
457 	}
458 	CL_SLEEP(t);		/* assign kernel priority */
459 	THREAD_SLEEP(t, &tc->tc_lock);
460 	t->t_wchan = sobj;
461 	t->t_sobj_ops = sobj_ops;
462 	DTRACE_SCHED(sleep);
463 
464 	if (lwp != NULL) {
465 		lwp->lwp_ru.nvcsw++;
466 		(void) new_mstate(t, LMS_SLEEP);
467 		if (SOBJ_TYPE(sobj_ops) == SOBJ_USER_PI) {
468 			lwp->lwp_asleep = 1;
469 			lwp->lwp_sysabort = 0;
470 			/*
471 			 * make wchan0 non-zero to conform to the rule that
472 			 * threads blocking for user-level objects have a
473 			 * non-zero wchan0: this prevents spurious wake-ups
474 			 * by, for example, /proc.
475 			 */
476 			t->t_wchan0 = (caddr_t)1;
477 		}
478 	}
479 	ts->ts_waiters++;
480 	sleepq_insert(&ts->ts_sleepq[qnum], t);
481 
482 	if (SOBJ_TYPE(sobj_ops) == SOBJ_MUTEX &&
483 	    SOBJ_OWNER(sobj_ops, sobj) == NULL)
484 		panic("turnstile_block(%p): unowned mutex", (void *)ts);
485 
486 	/*
487 	 * Follow the blocking chain to its end, willing our priority to
488 	 * everyone who's in our way.
489 	 */
490 	while (t->t_sobj_ops != NULL &&
491 	    (owner = SOBJ_OWNER(t->t_sobj_ops, t->t_wchan)) != NULL) {
492 		if (owner == curthread) {
493 			if (SOBJ_TYPE(sobj_ops) != SOBJ_USER_PI) {
494 				panic("Deadlock: cycle in blocking chain");
495 			}
496 			/*
497 			 * If the cycle we've encountered ends in mp,
498 			 * then we know it isn't a 'real' cycle because
499 			 * we're going to drop mp before we go to sleep.
500 			 * Moreover, since we've come full circle we know
501 			 * that we must have willed priority to everyone
502 			 * in our way.  Therefore, we can break out now.
503 			 */
504 			if (t->t_wchan == (void *)mp)
505 				break;
506 
507 			if (loser)
508 				lock_clear(&turnstile_loser_lock);
509 			/*
510 			 * For SOBJ_USER_PI, a cycle is an application
511 			 * deadlock which needs to be communicated
512 			 * back to the application.
513 			 */
514 			thread_unlock_nopreempt(t);
515 			mutex_exit(mp);
516 			setrun(curthread);
517 			swtch(); /* necessary to transition state */
518 			curthread->t_flag &= ~T_WAKEABLE;
519 			if (lwptp->lwpt_id != 0)
520 				(void) lwp_timer_dequeue(lwptp);
521 			setallwatch();
522 			lwp->lwp_asleep = 0;
523 			lwp->lwp_sysabort = 0;
524 			return (EDEADLK);
525 		}
526 		if (!turnstile_interlock(t->t_lockp, &owner->t_lockp)) {
527 			/*
528 			 * If we failed to grab the owner's thread lock,
529 			 * turnstile_interlock() will have dropped t's
530 			 * thread lock, so at this point we don't even know
531 			 * that 't' exists anymore.  The simplest solution
532 			 * is to restart the entire priority inheritance dance
533 			 * from the beginning of the blocking chain, since
534 			 * we *do* know that 'curthread' still exists.
535 			 * Application of priority inheritance is idempotent,
536 			 * so it's OK that we're doing it more than once.
537 			 * Note also that since we've dropped our thread lock,
538 			 * we may already have been woken up; if so, our
539 			 * t_sobj_ops will be NULL, the loop will terminate,
540 			 * and the call to swtch() will be a no-op.  Phew.
541 			 *
542 			 * There is one further complication: if two (or more)
543 			 * threads keep trying to grab the turnstile locks out
544 			 * of order and keep losing the race to another thread,
545 			 * these "dueling losers" can livelock the system.
546 			 * Therefore, once we get into this rare situation,
547 			 * we serialize all the losers.
548 			 */
549 			if (loser == 0) {
550 				loser = 1;
551 				lock_set(&turnstile_loser_lock);
552 			}
553 			t = curthread;
554 			thread_lock_high(t);
555 			continue;
556 		}
557 
558 		/*
559 		 * We now have the owner's thread lock.  If we are traversing
560 		 * from non-SOBJ_USER_PI ops to SOBJ_USER_PI ops, then we know
561 		 * that we have caught the thread while in the TS_SLEEP state,
562 		 * but holding mp.  We know that this situation is transient
563 		 * (mp will be dropped before the holder actually sleeps on
564 		 * the SOBJ_USER_PI sobj), so we will spin waiting for mp to
565 		 * be dropped.  Then, as in the turnstile_interlock() failure
566 		 * case, we will restart the priority inheritance dance.
567 		 */
568 		if (SOBJ_TYPE(t->t_sobj_ops) != SOBJ_USER_PI &&
569 		    owner->t_sobj_ops != NULL &&
570 		    SOBJ_TYPE(owner->t_sobj_ops) == SOBJ_USER_PI) {
571 			kmutex_t *upi_lock = (kmutex_t *)t->t_wchan;
572 
573 			ASSERT(IS_UPI(upi_lock));
574 			ASSERT(SOBJ_TYPE(t->t_sobj_ops) == SOBJ_MUTEX);
575 
576 			if (t->t_lockp != owner->t_lockp)
577 				thread_unlock_high(owner);
578 			thread_unlock_high(t);
579 			if (loser)
580 				lock_clear(&turnstile_loser_lock);
581 
582 			while (mutex_owner(upi_lock) == owner) {
583 				SMT_PAUSE();
584 				continue;
585 			}
586 
587 			if (loser)
588 				lock_set(&turnstile_loser_lock);
589 			t = curthread;
590 			thread_lock_high(t);
591 			continue;
592 		}
593 
594 		turnstile_pi_inherit(t->t_ts, owner, DISP_PRIO(t));
595 		if (t->t_lockp != owner->t_lockp)
596 			thread_unlock_high(t);
597 		t = owner;
598 	}
599 
600 	if (loser)
601 		lock_clear(&turnstile_loser_lock);
602 
603 	/*
604 	 * Note: 't' and 'curthread' were synonymous before the loop above,
605 	 * but now they may be different.  ('t' is now the last thread in
606 	 * the blocking chain.)
607 	 */
608 	if (SOBJ_TYPE(sobj_ops) == SOBJ_USER_PI) {
609 		ushort_t s = curthread->t_oldspl;
610 		int timedwait = 0;
611 		uint_t imm_timeout = 0;
612 		clock_t tim = -1;
613 
614 		thread_unlock_high(t);
615 		if (lwptp->lwpt_id != 0) {
616 			/*
617 			 * We enqueued a timeout.  If it has already fired,
618 			 * lwptp->lwpt_imm_timeout has been set with cas,
619 			 * so fetch it with cas.
620 			 */
621 			timedwait = 1;
622 			imm_timeout =
623 			    atomic_cas_uint(&lwptp->lwpt_imm_timeout, 0, 0);
624 		}
625 		mutex_exit(mp);
626 		splx(s);
627 
628 		if (ISSIG(curthread, JUSTLOOKING) ||
629 		    MUSTRETURN(p, curthread) || imm_timeout)
630 			setrun(curthread);
631 		swtch();
632 		curthread->t_flag &= ~T_WAKEABLE;
633 		if (timedwait)
634 			tim = lwp_timer_dequeue(lwptp);
635 		setallwatch();
636 		if (ISSIG(curthread, FORREAL) || lwp->lwp_sysabort ||
637 		    MUSTRETURN(p, curthread))
638 			error = EINTR;
639 		else if (imm_timeout || (timedwait && tim == -1))
640 			error = ETIME;
641 		lwp->lwp_sysabort = 0;
642 		lwp->lwp_asleep = 0;
643 	} else {
644 		thread_unlock_nopreempt(t);
645 		swtch();
646 	}
647 
648 	return (error);
649 }
650 
651 /*
652  * Remove thread from specified turnstile sleep queue; retrieve its
653  * free turnstile; if it is the last waiter, delete the turnstile
654  * from the turnstile chain and if there is an inheritor, delete it
655  * from the inheritor's t_prioinv chain.
656  */
657 static void
658 turnstile_dequeue(kthread_t *t)
659 {
660 	turnstile_t *ts = t->t_ts;
661 	turnstile_chain_t *tc = &TURNSTILE_CHAIN(ts->ts_sobj);
662 	turnstile_t *tsfree, **tspp;
663 
664 	ASSERT(DISP_LOCK_HELD(&tc->tc_lock));
665 	ASSERT(t->t_lockp == &tc->tc_lock);
666 
667 	if ((tsfree = ts->ts_free) != NULL) {
668 		ASSERT(ts->ts_waiters > 1);
669 		ASSERT(tsfree->ts_waiters == 0);
670 		t->t_ts = tsfree;
671 		ts->ts_free = tsfree->ts_free;
672 		tsfree->ts_free = NULL;
673 	} else {
674 		/*
675 		 * The active turnstile's freelist is empty, so this
676 		 * must be the last waiter.  Remove the turnstile
677 		 * from the hash chain and leave the now-inactive
678 		 * turnstile attached to the thread we're waking.
679 		 * Note that the ts_inheritor for the turnstile
680 		 * may be NULL. If one exists, its t_prioinv
681 		 * chain has to be updated.
682 		 */
683 		ASSERT(ts->ts_waiters == 1);
684 		if (ts->ts_inheritor != NULL) {
685 			(void) turnstile_pi_tsdelete(ts, ts->ts_inheritor);
686 			/*
687 			 * If we ever do a "disinherit" or "unboost", we need
688 			 * to do it only if "t" is a thread at the head of the
689 			 * sleep queue. Since the sleep queue is prioritized,
690 			 * the disinherit is necessary only if the interrupted
691 			 * thread is the highest priority thread.
692 			 * Otherwise, there is a higher priority thread blocked
693 			 * on the turnstile, whose inheritance cannot be
694 			 * disinherited. However, disinheriting is explicitly
695 			 * not done here, since it would require holding the
696 			 * inheritor's thread lock (see turnstile_unsleep()).
697 			 */
698 			ts->ts_inheritor = NULL;
699 		}
700 		tspp = &tc->tc_first;
701 		while (*tspp != ts)
702 			tspp = &(*tspp)->ts_next;
703 		*tspp = ts->ts_next;
704 		ASSERT(t->t_ts == ts);
705 	}
706 	ts->ts_waiters--;
707 	sleepq_dequeue(t);
708 	t->t_sobj_ops = NULL;
709 	t->t_wchan = NULL;
710 	t->t_wchan0 = NULL;
711 	ASSERT(t->t_state == TS_SLEEP);
712 }
713 
714 /*
715  * Wake threads that are blocked in a turnstile.
716  */
717 void
718 turnstile_wakeup(turnstile_t *ts, int qnum, int nthreads, kthread_t *owner)
719 {
720 	turnstile_chain_t *tc = &TURNSTILE_CHAIN(ts->ts_sobj);
721 	sleepq_t *sqp = &ts->ts_sleepq[qnum];
722 
723 	ASSERT(DISP_LOCK_HELD(&tc->tc_lock));
724 
725 	/*
726 	 * Waive any priority we may have inherited from this turnstile.
727 	 */
728 	if (ts->ts_inheritor != NULL) {
729 		turnstile_pi_waive(ts);
730 	}
731 	while (nthreads-- > 0) {
732 		kthread_t *t = sqp->sq_first;
733 		ASSERT(t->t_ts == ts);
734 		ASSERT(ts->ts_waiters > 1 || ts->ts_inheritor == NULL);
735 		DTRACE_SCHED1(wakeup, kthread_t *, t);
736 		turnstile_dequeue(t);
737 		CL_WAKEUP(t); /* previous thread lock, tc_lock, not dropped */
738 		/*
739 		 * If the caller did direct handoff of ownership,
740 		 * make the new owner inherit from this turnstile.
741 		 */
742 		if (t == owner) {
743 			kthread_t *wp = ts->ts_sleepq[TS_WRITER_Q].sq_first;
744 			kthread_t *rp = ts->ts_sleepq[TS_READER_Q].sq_first;
745 			pri_t wpri = wp ? DISP_PRIO(wp) : 0;
746 			pri_t rpri = rp ? DISP_PRIO(rp) : 0;
747 			turnstile_pi_inherit(ts, t, MAX(wpri, rpri));
748 			owner = NULL;
749 		}
750 		thread_unlock_high(t);		/* drop run queue lock */
751 	}
752 	if (owner != NULL)
753 		panic("turnstile_wakeup: owner %p not woken", (void *)owner);
754 	disp_lock_exit(&tc->tc_lock);
755 }
756 
757 /*
758  * Change priority of a thread sleeping in a turnstile.
759  */
760 void
761 turnstile_change_pri(kthread_t *t, pri_t pri, pri_t *t_prip)
762 {
763 	sleepq_t *sqp = t->t_sleepq;
764 
765 	sleepq_dequeue(t);
766 	*t_prip = pri;
767 	sleepq_insert(sqp, t);
768 }
769 
770 /*
771  * We don't allow spurious wakeups of threads blocked in turnstiles
772  * for synch objects whose sobj_ops vector is initialized with the
773  * following routine (e.g. kernel synchronization objects).
774  * This is vital to the correctness of direct-handoff logic in some
775  * synchronization primitives, and it also simplifies the PI logic.
776  */
777 /* ARGSUSED */
778 void
779 turnstile_stay_asleep(kthread_t *t)
780 {
781 }
782 
783 /*
784  * Wake up a thread blocked in a turnstile. Used to enable interruptibility
785  * of threads blocked on a SOBJ_USER_PI sobj.
786  *
787  * The implications of this interface are:
788  *
789  * 1. turnstile_block() may return with an EINTR.
790  * 2. When the owner of an sobj releases it, but no turnstile is found (i.e.
791  *    no waiters), the (prior) owner must call turnstile_pi_recalc() to
792  *    waive any priority inherited from interrupted waiters.
793  *
794  * When a waiter is interrupted, disinheriting its willed priority from the
795  * inheritor would require holding the inheritor's thread lock, while also
796  * holding the waiter's thread lock which is a turnstile lock. If the
797  * inheritor's thread lock is not free, and is also a turnstile lock that
798  * is out of lock order, the waiter's thread lock would have to be dropped.
799  * This leads to complications for the caller of turnstile_unsleep(), since
800  * the caller holds the waiter's thread lock. So, instead of disinheriting
801  * on waiter interruption, the owner is required to follow rule 2 above.
802  *
803  * Avoiding disinherit on waiter interruption seems acceptable because
804  * the owner runs at an unnecessarily high priority only while sobj is held,
805  * which it would have done in any case, if the waiter had not been interrupted.
806  */
807 void
808 turnstile_unsleep(kthread_t *t)
809 {
810 	turnstile_dequeue(t);
811 	THREAD_TRANSITION(t);
812 	CL_SETRUN(t);
813 }
814