1 /*-
2 * Copyright (c) 1998 Berkeley Software Design, Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 * 3. Berkeley Software Design Inc's name may not be used to endorse or
13 * promote products derived from this software without specific prior
14 * written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY BERKELEY SOFTWARE DESIGN INC ``AS IS'' AND
17 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL BERKELEY SOFTWARE DESIGN INC BE LIABLE
20 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
22 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
23 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
24 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
25 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26 * SUCH DAMAGE.
27 *
28 * from BSDI $Id: mutex_witness.c,v 1.1.2.20 2000/04/27 03:10:27 cp Exp $
29 * and BSDI $Id: synch_machdep.c,v 2.3.2.39 2000/04/27 03:10:25 cp Exp $
30 */
31
32 /*
33 * Implementation of turnstiles used to hold queue of threads blocked on
34 * non-sleepable locks. Sleepable locks use condition variables to
35 * implement their queues. Turnstiles differ from a sleep queue in that
36 * turnstile queue's are assigned to a lock held by an owning thread. Thus,
37 * when one thread is enqueued onto a turnstile, it can lend its priority
38 * to the owning thread.
39 *
40 * We wish to avoid bloating locks with an embedded turnstile and we do not
41 * want to use back-pointers in the locks for the same reason. Thus, we
42 * use a similar approach to that of Solaris 7 as described in Solaris
43 * Internals by Jim Mauro and Richard McDougall. Turnstiles are looked up
44 * in a hash table based on the address of the lock. Each entry in the
45 * hash table is a linked-lists of turnstiles and is called a turnstile
46 * chain. Each chain contains a spin mutex that protects all of the
47 * turnstiles in the chain.
48 *
49 * Each time a thread is created, a turnstile is malloc'd and attached to
50 * that thread. When a thread blocks on a lock, if it is the first thread
51 * to block, it lends its turnstile to the lock. If the lock already has
52 * a turnstile, then it gives its turnstile to the lock's turnstile's free
53 * list. When a thread is woken up, it takes a turnstile from the free list
54 * if there are any other waiters. If it is the only thread blocked on the
55 * lock, then it reclaims the turnstile associated with the lock and removes
56 * it from the hash table.
57 */
58
59 #include <sys/cdefs.h>
60 __FBSDID("$FreeBSD: releng/6.2/sys/kern/subr_turnstile.c 164286 2006-11-14 20:42:41Z cvs2svn $");
61
62 #include "opt_ddb.h"
63 #include "opt_turnstile_profiling.h"
64
65 #include <sys/param.h>
66 #include <sys/systm.h>
67 #include <sys/kernel.h>
68 #include <sys/ktr.h>
69 #include <sys/lock.h>
70 #include <sys/malloc.h>
71 #include <sys/mutex.h>
72 #include <sys/proc.h>
73 #include <sys/queue.h>
74 #include <sys/sched.h>
75 #include <sys/sysctl.h>
76 #include <sys/turnstile.h>
77
78 #ifdef DDB
79 #include <sys/kdb.h>
80 #include <ddb/ddb.h>
81 #include <sys/lockmgr.h>
82 #include <sys/sx.h>
83 #endif
84
85 /*
86 * Constants for the hash table of turnstile chains. TC_SHIFT is a magic
87 * number chosen because the sleep queue's use the same value for the
88 * shift. Basically, we ignore the lower 8 bits of the address.
89 * TC_TABLESIZE must be a power of two for TC_MASK to work properly.
90 */
91 #define TC_TABLESIZE 128 /* Must be power of 2. */
92 #define TC_MASK (TC_TABLESIZE - 1)
93 #define TC_SHIFT 8
94 #define TC_HASH(lock) (((uintptr_t)(lock) >> TC_SHIFT) & TC_MASK)
95 #define TC_LOOKUP(lock) &turnstile_chains[TC_HASH(lock)]
96
97 /*
98 * There are three different lists of turnstiles as follows. The list
99 * connected by ts_link entries is a per-thread list of all the turnstiles
100 * attached to locks that we own. This is used to fixup our priority when
101 * a lock is released. The other two lists use the ts_hash entries. The
102 * first of these two is the turnstile chain list that a turnstile is on
103 * when it is attached to a lock. The second list to use ts_hash is the
104 * free list hung off of a turnstile that is attached to a lock.
105 *
106 * Each turnstile contains two lists of threads. The ts_blocked list is
107 * a linked list of threads blocked on the turnstile's lock. The
108 * ts_pending list is a linked list of threads previously awakened by
109 * turnstile_signal() or turnstile_wait() that are waiting to be put on
110 * the run queue.
111 *
112 * Locking key:
113 * c - turnstile chain lock
114 * q - td_contested lock
115 */
116 struct turnstile {
117 TAILQ_HEAD(, thread) ts_blocked; /* (c + q) Blocked threads. */
118 TAILQ_HEAD(, thread) ts_pending; /* (c) Pending threads. */
119 LIST_ENTRY(turnstile) ts_hash; /* (c) Chain and free list. */
120 LIST_ENTRY(turnstile) ts_link; /* (q) Contested locks. */
121 LIST_HEAD(, turnstile) ts_free; /* (c) Free turnstiles. */
122 struct lock_object *ts_lockobj; /* (c) Lock we reference. */
123 struct thread *ts_owner; /* (c + q) Who owns the lock. */
124 };
125
126 struct turnstile_chain {
127 LIST_HEAD(, turnstile) tc_turnstiles; /* List of turnstiles. */
128 struct mtx tc_lock; /* Spin lock for this chain. */
129 #ifdef TURNSTILE_PROFILING
130 u_int tc_depth; /* Length of tc_queues. */
131 u_int tc_max_depth; /* Max length of tc_queues. */
132 #endif
133 };
134
135 #ifdef TURNSTILE_PROFILING
136 u_int turnstile_max_depth;
137 SYSCTL_NODE(_debug, OID_AUTO, turnstile, CTLFLAG_RD, 0, "turnstile profiling");
138 SYSCTL_NODE(_debug_turnstile, OID_AUTO, chains, CTLFLAG_RD, 0,
139 "turnstile chain stats");
140 SYSCTL_UINT(_debug_turnstile, OID_AUTO, max_depth, CTLFLAG_RD,
141 &turnstile_max_depth, 0, "maxmimum depth achieved of a single chain");
142 #endif
143 static struct mtx td_contested_lock;
144 static struct turnstile_chain turnstile_chains[TC_TABLESIZE];
145
146 static MALLOC_DEFINE(M_TURNSTILE, "turnstiles", "turnstiles");
147
148 /*
149 * Prototypes for non-exported routines.
150 */
151 static void init_turnstile0(void *dummy);
152 #ifdef TURNSTILE_PROFILING
153 static void init_turnstile_profiling(void *arg);
154 #endif
155 static void propagate_priority(struct thread *td);
156 static int turnstile_adjust_thread(struct turnstile *ts,
157 struct thread *td);
158 static void turnstile_setowner(struct turnstile *ts, struct thread *owner);
159
160 /*
161 * Walks the chain of turnstiles and their owners to propagate the priority
162 * of the thread being blocked to all the threads holding locks that have to
163 * release their locks before this thread can run again.
164 */
165 static void
166 propagate_priority(struct thread *td)
167 {
168 struct turnstile_chain *tc;
169 struct turnstile *ts;
170 int pri;
171
172 mtx_assert(&sched_lock, MA_OWNED);
173 pri = td->td_priority;
174 ts = td->td_blocked;
175 for (;;) {
176 td = ts->ts_owner;
177
178 if (td == NULL) {
179 /*
180 * This really isn't quite right. Really
181 * ought to bump priority of thread that
182 * next acquires the lock.
183 */
184 return;
185 }
186
187 MPASS(td->td_proc != NULL);
188 MPASS(td->td_proc->p_magic == P_MAGIC);
189
190 /*
191 * If the thread is asleep, then we are probably about
192 * to deadlock. To make debugging this easier, just
193 * panic and tell the user which thread misbehaved so
194 * they can hopefully get a stack trace from the truly
195 * misbehaving thread.
196 */
197 if (TD_IS_SLEEPING(td)) {
198 printf(
199 "Sleeping thread (tid %d, pid %d) owns a non-sleepable lock\n",
200 td->td_tid, td->td_proc->p_pid);
201 #ifdef DDB
202 db_trace_thread(td, -1);
203 #endif
204 panic("sleeping thread");
205 }
206
207 /*
208 * If this thread already has higher priority than the
209 * thread that is being blocked, we are finished.
210 */
211 if (td->td_priority <= pri)
212 return;
213
214 /*
215 * Bump this thread's priority.
216 */
217 sched_lend_prio(td, pri);
218
219 /*
220 * If lock holder is actually running or on the run queue
221 * then we are done.
222 */
223 if (TD_IS_RUNNING(td) || TD_ON_RUNQ(td)) {
224 MPASS(td->td_blocked == NULL);
225 return;
226 }
227
228 #ifndef SMP
229 /*
230 * For UP, we check to see if td is curthread (this shouldn't
231 * ever happen however as it would mean we are in a deadlock.)
232 */
233 KASSERT(td != curthread, ("Deadlock detected"));
234 #endif
235
236 /*
237 * If we aren't blocked on a lock, we should be.
238 */
239 KASSERT(TD_ON_LOCK(td), (
240 "thread %d(%s):%d holds %s but isn't blocked on a lock\n",
241 td->td_tid, td->td_proc->p_comm, td->td_state,
242 ts->ts_lockobj->lo_name));
243
244 /*
245 * Pick up the lock that td is blocked on.
246 */
247 ts = td->td_blocked;
248 MPASS(ts != NULL);
249 tc = TC_LOOKUP(ts->ts_lockobj);
250 mtx_lock_spin(&tc->tc_lock);
251
252 /* Resort td on the list if needed. */
253 if (!turnstile_adjust_thread(ts, td)) {
254 mtx_unlock_spin(&tc->tc_lock);
255 return;
256 }
257 mtx_unlock_spin(&tc->tc_lock);
258 }
259 }
260
261 /*
262 * Adjust the thread's position on a turnstile after its priority has been
263 * changed.
264 */
265 static int
266 turnstile_adjust_thread(struct turnstile *ts, struct thread *td)
267 {
268 struct turnstile_chain *tc;
269 struct thread *td1, *td2;
270
271 mtx_assert(&sched_lock, MA_OWNED);
272 MPASS(TD_ON_LOCK(td));
273
274 /*
275 * This thread may not be blocked on this turnstile anymore
276 * but instead might already be woken up on another CPU
277 * that is waiting on sched_lock in turnstile_unpend() to
278 * finish waking this thread up. We can detect this case
279 * by checking to see if this thread has been given a
280 * turnstile by either turnstile_signal() or
281 * turnstile_broadcast(). In this case, treat the thread as
282 * if it was already running.
283 */
284 if (td->td_turnstile != NULL)
285 return (0);
286
287 /*
288 * Check if the thread needs to be moved on the blocked chain.
289 * It needs to be moved if either its priority is lower than
290 * the previous thread or higher than the next thread.
291 */
292 tc = TC_LOOKUP(ts->ts_lockobj);
293 mtx_assert(&tc->tc_lock, MA_OWNED);
294 td1 = TAILQ_PREV(td, threadqueue, td_lockq);
295 td2 = TAILQ_NEXT(td, td_lockq);
296 if ((td1 != NULL && td->td_priority < td1->td_priority) ||
297 (td2 != NULL && td->td_priority > td2->td_priority)) {
298
299 /*
300 * Remove thread from blocked chain and determine where
301 * it should be moved to.
302 */
303 mtx_lock_spin(&td_contested_lock);
304 TAILQ_REMOVE(&ts->ts_blocked, td, td_lockq);
305 TAILQ_FOREACH(td1, &ts->ts_blocked, td_lockq) {
306 MPASS(td1->td_proc->p_magic == P_MAGIC);
307 if (td1->td_priority > td->td_priority)
308 break;
309 }
310
311 if (td1 == NULL)
312 TAILQ_INSERT_TAIL(&ts->ts_blocked, td, td_lockq);
313 else
314 TAILQ_INSERT_BEFORE(td1, td, td_lockq);
315 mtx_unlock_spin(&td_contested_lock);
316 if (td1 == NULL)
317 CTR3(KTR_LOCK,
318 "turnstile_adjust_thread: td %d put at tail on [%p] %s",
319 td->td_tid, ts->ts_lockobj, ts->ts_lockobj->lo_name);
320 else
321 CTR4(KTR_LOCK,
322 "turnstile_adjust_thread: td %d moved before %d on [%p] %s",
323 td->td_tid, td1->td_tid, ts->ts_lockobj,
324 ts->ts_lockobj->lo_name);
325 }
326 return (1);
327 }
328
329 /*
330 * Early initialization of turnstiles. This is not done via a SYSINIT()
331 * since this needs to be initialized very early when mutexes are first
332 * initialized.
333 */
334 void
335 init_turnstiles(void)
336 {
337 int i;
338
339 for (i = 0; i < TC_TABLESIZE; i++) {
340 LIST_INIT(&turnstile_chains[i].tc_turnstiles);
341 mtx_init(&turnstile_chains[i].tc_lock, "turnstile chain",
342 NULL, MTX_SPIN);
343 }
344 mtx_init(&td_contested_lock, "td_contested", NULL, MTX_SPIN);
345 LIST_INIT(&thread0.td_contested);
346 thread0.td_turnstile = NULL;
347 }
348
349 #ifdef TURNSTILE_PROFILING
350 static void
351 init_turnstile_profiling(void *arg)
352 {
353 struct sysctl_oid *chain_oid;
354 char chain_name[10];
355 int i;
356
357 for (i = 0; i < TC_TABLESIZE; i++) {
358 snprintf(chain_name, sizeof(chain_name), "%d", i);
359 chain_oid = SYSCTL_ADD_NODE(NULL,
360 SYSCTL_STATIC_CHILDREN(_debug_turnstile_chains), OID_AUTO,
361 chain_name, CTLFLAG_RD, NULL, "turnstile chain stats");
362 SYSCTL_ADD_UINT(NULL, SYSCTL_CHILDREN(chain_oid), OID_AUTO,
363 "depth", CTLFLAG_RD, &turnstile_chains[i].tc_depth, 0,
364 NULL);
365 SYSCTL_ADD_UINT(NULL, SYSCTL_CHILDREN(chain_oid), OID_AUTO,
366 "max_depth", CTLFLAG_RD, &turnstile_chains[i].tc_max_depth,
367 0, NULL);
368 }
369 }
370 SYSINIT(turnstile_profiling, SI_SUB_LOCK, SI_ORDER_ANY,
371 init_turnstile_profiling, NULL);
372 #endif
373
374 static void
375 init_turnstile0(void *dummy)
376 {
377
378 thread0.td_turnstile = turnstile_alloc();
379 }
380 SYSINIT(turnstile0, SI_SUB_LOCK, SI_ORDER_ANY, init_turnstile0, NULL);
381
382 /*
383 * Update a thread on the turnstile list after it's priority has been changed.
384 * The old priority is passed in as an argument.
385 */
386 void
387 turnstile_adjust(struct thread *td, u_char oldpri)
388 {
389 struct turnstile_chain *tc;
390 struct turnstile *ts;
391
392 mtx_assert(&sched_lock, MA_OWNED);
393 MPASS(TD_ON_LOCK(td));
394
395 /*
396 * Pick up the lock that td is blocked on.
397 */
398 ts = td->td_blocked;
399 MPASS(ts != NULL);
400 tc = TC_LOOKUP(ts->ts_lockobj);
401 mtx_lock_spin(&tc->tc_lock);
402
403 /* Resort the turnstile on the list. */
404 if (!turnstile_adjust_thread(ts, td)) {
405 mtx_unlock_spin(&tc->tc_lock);
406 return;
407 }
408
409 /*
410 * If our priority was lowered and we are at the head of the
411 * turnstile, then propagate our new priority up the chain.
412 * Note that we currently don't try to revoke lent priorities
413 * when our priority goes up.
414 */
415 if (td == TAILQ_FIRST(&ts->ts_blocked) && td->td_priority < oldpri) {
416 mtx_unlock_spin(&tc->tc_lock);
417 propagate_priority(td);
418 } else
419 mtx_unlock_spin(&tc->tc_lock);
420 }
421
422 /*
423 * Set the owner of the lock this turnstile is attached to.
424 */
425 static void
426 turnstile_setowner(struct turnstile *ts, struct thread *owner)
427 {
428
429 mtx_assert(&td_contested_lock, MA_OWNED);
430 MPASS(owner->td_proc->p_magic == P_MAGIC);
431 MPASS(ts->ts_owner == NULL);
432 ts->ts_owner = owner;
433 LIST_INSERT_HEAD(&owner->td_contested, ts, ts_link);
434 }
435
436 /*
437 * Malloc a turnstile for a new thread, initialize it and return it.
438 */
439 struct turnstile *
440 turnstile_alloc(void)
441 {
442 struct turnstile *ts;
443
444 ts = malloc(sizeof(struct turnstile), M_TURNSTILE, M_WAITOK | M_ZERO);
445 TAILQ_INIT(&ts->ts_blocked);
446 TAILQ_INIT(&ts->ts_pending);
447 LIST_INIT(&ts->ts_free);
448 return (ts);
449 }
450
451 /*
452 * Free a turnstile when a thread is destroyed.
453 */
454 void
455 turnstile_free(struct turnstile *ts)
456 {
457
458 MPASS(ts != NULL);
459 MPASS(TAILQ_EMPTY(&ts->ts_blocked));
460 MPASS(TAILQ_EMPTY(&ts->ts_pending));
461 free(ts, M_TURNSTILE);
462 }
463
464 /*
465 * Lock the turnstile chain associated with the specified lock.
466 */
467 void
468 turnstile_lock(struct lock_object *lock)
469 {
470 struct turnstile_chain *tc;
471
472 tc = TC_LOOKUP(lock);
473 mtx_lock_spin(&tc->tc_lock);
474 }
475
476 /*
477 * Look up the turnstile for a lock in the hash table locking the associated
478 * turnstile chain along the way. If no turnstile is found in the hash
479 * table, NULL is returned.
480 */
481 struct turnstile *
482 turnstile_lookup(struct lock_object *lock)
483 {
484 struct turnstile_chain *tc;
485 struct turnstile *ts;
486
487 tc = TC_LOOKUP(lock);
488 mtx_assert(&tc->tc_lock, MA_OWNED);
489 LIST_FOREACH(ts, &tc->tc_turnstiles, ts_hash)
490 if (ts->ts_lockobj == lock)
491 return (ts);
492 return (NULL);
493 }
494
495 /*
496 * Unlock the turnstile chain associated with a given lock.
497 */
498 void
499 turnstile_release(struct lock_object *lock)
500 {
501 struct turnstile_chain *tc;
502
503 tc = TC_LOOKUP(lock);
504 mtx_unlock_spin(&tc->tc_lock);
505 }
506
507 /*
508 * Take ownership of a turnstile and adjust the priority of the new
509 * owner appropriately.
510 */
511 void
512 turnstile_claim(struct lock_object *lock)
513 {
514 struct turnstile_chain *tc;
515 struct turnstile *ts;
516 struct thread *td, *owner;
517
518 tc = TC_LOOKUP(lock);
519 mtx_assert(&tc->tc_lock, MA_OWNED);
520 ts = turnstile_lookup(lock);
521 MPASS(ts != NULL);
522
523 owner = curthread;
524 mtx_lock_spin(&td_contested_lock);
525 turnstile_setowner(ts, owner);
526 mtx_unlock_spin(&td_contested_lock);
527
528 td = TAILQ_FIRST(&ts->ts_blocked);
529 MPASS(td != NULL);
530 MPASS(td->td_proc->p_magic == P_MAGIC);
531 mtx_unlock_spin(&tc->tc_lock);
532
533 /*
534 * Update the priority of the new owner if needed.
535 */
536 mtx_lock_spin(&sched_lock);
537 if (td->td_priority < owner->td_priority)
538 sched_lend_prio(owner, td->td_priority);
539 mtx_unlock_spin(&sched_lock);
540 }
541
542 /*
543 * Block the current thread on the turnstile assicated with 'lock'. This
544 * function will context switch and not return until this thread has been
545 * woken back up. This function must be called with the appropriate
546 * turnstile chain locked and will return with it unlocked.
547 */
548 void
549 turnstile_wait(struct lock_object *lock, struct thread *owner)
550 {
551 struct turnstile_chain *tc;
552 struct turnstile *ts;
553 struct thread *td, *td1;
554
555 td = curthread;
556 tc = TC_LOOKUP(lock);
557 mtx_assert(&tc->tc_lock, MA_OWNED);
558 MPASS(td->td_turnstile != NULL);
559 MPASS(owner != NULL);
560 MPASS(owner->td_proc->p_magic == P_MAGIC);
561
562 /* Look up the turnstile associated with the lock 'lock'. */
563 ts = turnstile_lookup(lock);
564
565 /*
566 * If the lock does not already have a turnstile, use this thread's
567 * turnstile. Otherwise insert the current thread into the
568 * turnstile already in use by this lock.
569 */
570 if (ts == NULL) {
571 #ifdef TURNSTILE_PROFILING
572 tc->tc_depth++;
573 if (tc->tc_depth > tc->tc_max_depth) {
574 tc->tc_max_depth = tc->tc_depth;
575 if (tc->tc_max_depth > turnstile_max_depth)
576 turnstile_max_depth = tc->tc_max_depth;
577 }
578 #endif
579 ts = td->td_turnstile;
580 LIST_INSERT_HEAD(&tc->tc_turnstiles, ts, ts_hash);
581 KASSERT(TAILQ_EMPTY(&ts->ts_pending),
582 ("thread's turnstile has pending threads"));
583 KASSERT(TAILQ_EMPTY(&ts->ts_blocked),
584 ("thread's turnstile has a non-empty queue"));
585 KASSERT(LIST_EMPTY(&ts->ts_free),
586 ("thread's turnstile has a non-empty free list"));
587 KASSERT(ts->ts_lockobj == NULL, ("stale ts_lockobj pointer"));
588 ts->ts_lockobj = lock;
589 mtx_lock_spin(&td_contested_lock);
590 TAILQ_INSERT_TAIL(&ts->ts_blocked, td, td_lockq);
591 turnstile_setowner(ts, owner);
592 mtx_unlock_spin(&td_contested_lock);
593 } else {
594 TAILQ_FOREACH(td1, &ts->ts_blocked, td_lockq)
595 if (td1->td_priority > td->td_priority)
596 break;
597 mtx_lock_spin(&td_contested_lock);
598 if (td1 != NULL)
599 TAILQ_INSERT_BEFORE(td1, td, td_lockq);
600 else
601 TAILQ_INSERT_TAIL(&ts->ts_blocked, td, td_lockq);
602 mtx_unlock_spin(&td_contested_lock);
603 MPASS(td->td_turnstile != NULL);
604 LIST_INSERT_HEAD(&ts->ts_free, td->td_turnstile, ts_hash);
605 MPASS(owner == ts->ts_owner);
606 }
607 td->td_turnstile = NULL;
608 mtx_unlock_spin(&tc->tc_lock);
609
610 mtx_lock_spin(&sched_lock);
611 /*
612 * Handle race condition where a thread on another CPU that owns
613 * lock 'lock' could have woken us in between us dropping the
614 * turnstile chain lock and acquiring the sched_lock.
615 */
616 if (td->td_flags & TDF_TSNOBLOCK) {
617 td->td_flags &= ~TDF_TSNOBLOCK;
618 mtx_unlock_spin(&sched_lock);
619 return;
620 }
621
622 #ifdef notyet
623 /*
624 * If we're borrowing an interrupted thread's VM context, we
625 * must clean up before going to sleep.
626 */
627 if (td->td_ithd != NULL) {
628 struct ithd *it = td->td_ithd;
629
630 if (it->it_interrupted) {
631 if (LOCK_LOG_TEST(lock, 0))
632 CTR3(KTR_LOCK, "%s: %p interrupted %p",
633 __func__, it, it->it_interrupted);
634 intr_thd_fixup(it);
635 }
636 }
637 #endif
638
639 /* Save who we are blocked on and switch. */
640 td->td_blocked = ts;
641 td->td_lockname = lock->lo_name;
642 TD_SET_LOCK(td);
643 propagate_priority(td);
644
645 if (LOCK_LOG_TEST(lock, 0))
646 CTR4(KTR_LOCK, "%s: td %d blocked on [%p] %s", __func__,
647 td->td_tid, lock, lock->lo_name);
648
649 mi_switch(SW_VOL, NULL);
650
651 if (LOCK_LOG_TEST(lock, 0))
652 CTR4(KTR_LOCK, "%s: td %d free from blocked on [%p] %s",
653 __func__, td->td_tid, lock, lock->lo_name);
654
655 mtx_unlock_spin(&sched_lock);
656 }
657
658 /*
659 * Pick the highest priority thread on this turnstile and put it on the
660 * pending list. This must be called with the turnstile chain locked.
661 */
662 int
663 turnstile_signal(struct turnstile *ts)
664 {
665 struct turnstile_chain *tc;
666 struct thread *td;
667 int empty;
668
669 MPASS(ts != NULL);
670 MPASS(curthread->td_proc->p_magic == P_MAGIC);
671 MPASS(ts->ts_owner == curthread);
672 tc = TC_LOOKUP(ts->ts_lockobj);
673 mtx_assert(&tc->tc_lock, MA_OWNED);
674
675 /*
676 * Pick the highest priority thread blocked on this lock and
677 * move it to the pending list.
678 */
679 td = TAILQ_FIRST(&ts->ts_blocked);
680 MPASS(td->td_proc->p_magic == P_MAGIC);
681 mtx_lock_spin(&td_contested_lock);
682 TAILQ_REMOVE(&ts->ts_blocked, td, td_lockq);
683 mtx_unlock_spin(&td_contested_lock);
684 TAILQ_INSERT_TAIL(&ts->ts_pending, td, td_lockq);
685
686 /*
687 * If the turnstile is now empty, remove it from its chain and
688 * give it to the about-to-be-woken thread. Otherwise take a
689 * turnstile from the free list and give it to the thread.
690 */
691 empty = TAILQ_EMPTY(&ts->ts_blocked);
692 if (empty) {
693 MPASS(LIST_EMPTY(&ts->ts_free));
694 #ifdef TURNSTILE_PROFILING
695 tc->tc_depth--;
696 #endif
697 } else
698 ts = LIST_FIRST(&ts->ts_free);
699 MPASS(ts != NULL);
700 LIST_REMOVE(ts, ts_hash);
701 td->td_turnstile = ts;
702
703 return (empty);
704 }
705
706 /*
707 * Put all blocked threads on the pending list. This must be called with
708 * the turnstile chain locked.
709 */
710 void
711 turnstile_broadcast(struct turnstile *ts)
712 {
713 struct turnstile_chain *tc;
714 struct turnstile *ts1;
715 struct thread *td;
716
717 MPASS(ts != NULL);
718 MPASS(curthread->td_proc->p_magic == P_MAGIC);
719 MPASS(ts->ts_owner == curthread);
720 tc = TC_LOOKUP(ts->ts_lockobj);
721 mtx_assert(&tc->tc_lock, MA_OWNED);
722
723 /*
724 * Transfer the blocked list to the pending list.
725 */
726 mtx_lock_spin(&td_contested_lock);
727 TAILQ_CONCAT(&ts->ts_pending, &ts->ts_blocked, td_lockq);
728 mtx_unlock_spin(&td_contested_lock);
729
730 /*
731 * Give a turnstile to each thread. The last thread gets
732 * this turnstile.
733 */
734 TAILQ_FOREACH(td, &ts->ts_pending, td_lockq) {
735 if (LIST_EMPTY(&ts->ts_free)) {
736 MPASS(TAILQ_NEXT(td, td_lockq) == NULL);
737 ts1 = ts;
738 #ifdef TURNSTILE_PROFILING
739 tc->tc_depth--;
740 #endif
741 } else
742 ts1 = LIST_FIRST(&ts->ts_free);
743 MPASS(ts1 != NULL);
744 LIST_REMOVE(ts1, ts_hash);
745 td->td_turnstile = ts1;
746 }
747 }
748
749 /*
750 * Wakeup all threads on the pending list and adjust the priority of the
751 * current thread appropriately. This must be called with the turnstile
752 * chain locked.
753 */
754 void
755 turnstile_unpend(struct turnstile *ts)
756 {
757 TAILQ_HEAD( ,thread) pending_threads;
758 struct turnstile_chain *tc;
759 struct thread *td;
760 u_char cp, pri;
761
762 MPASS(ts != NULL);
763 MPASS(ts->ts_owner == curthread);
764 tc = TC_LOOKUP(ts->ts_lockobj);
765 mtx_assert(&tc->tc_lock, MA_OWNED);
766 MPASS(!TAILQ_EMPTY(&ts->ts_pending));
767
768 /*
769 * Move the list of pending threads out of the turnstile and
770 * into a local variable.
771 */
772 TAILQ_INIT(&pending_threads);
773 TAILQ_CONCAT(&pending_threads, &ts->ts_pending, td_lockq);
774 #ifdef INVARIANTS
775 if (TAILQ_EMPTY(&ts->ts_blocked))
776 ts->ts_lockobj = NULL;
777 #endif
778
779 /*
780 * Remove the turnstile from this thread's list of contested locks
781 * since this thread doesn't own it anymore. New threads will
782 * not be blocking on the turnstile until it is claimed by a new
783 * owner.
784 */
785 mtx_lock_spin(&td_contested_lock);
786 ts->ts_owner = NULL;
787 LIST_REMOVE(ts, ts_link);
788 mtx_unlock_spin(&td_contested_lock);
789 critical_enter();
790 mtx_unlock_spin(&tc->tc_lock);
791
792 /*
793 * Adjust the priority of curthread based on other contested
794 * locks it owns. Don't lower the priority below the base
795 * priority however.
796 */
797 td = curthread;
798 pri = PRI_MAX;
799 mtx_lock_spin(&sched_lock);
800 mtx_lock_spin(&td_contested_lock);
801 LIST_FOREACH(ts, &td->td_contested, ts_link) {
802 cp = TAILQ_FIRST(&ts->ts_blocked)->td_priority;
803 if (cp < pri)
804 pri = cp;
805 }
806 mtx_unlock_spin(&td_contested_lock);
807 sched_unlend_prio(td, pri);
808
809 /*
810 * Wake up all the pending threads. If a thread is not blocked
811 * on a lock, then it is currently executing on another CPU in
812 * turnstile_wait() or sitting on a run queue waiting to resume
813 * in turnstile_wait(). Set a flag to force it to try to acquire
814 * the lock again instead of blocking.
815 */
816 while (!TAILQ_EMPTY(&pending_threads)) {
817 td = TAILQ_FIRST(&pending_threads);
818 TAILQ_REMOVE(&pending_threads, td, td_lockq);
819 MPASS(td->td_proc->p_magic == P_MAGIC);
820 if (TD_ON_LOCK(td)) {
821 td->td_blocked = NULL;
822 td->td_lockname = NULL;
823 TD_CLR_LOCK(td);
824 MPASS(TD_CAN_RUN(td));
825 setrunqueue(td, SRQ_BORING);
826 } else {
827 td->td_flags |= TDF_TSNOBLOCK;
828 MPASS(TD_IS_RUNNING(td) || TD_ON_RUNQ(td));
829 }
830 }
831 critical_exit();
832 mtx_unlock_spin(&sched_lock);
833 }
834
835 /*
836 * Return the first thread in a turnstile.
837 */
838 struct thread *
839 turnstile_head(struct turnstile *ts)
840 {
841 #ifdef INVARIANTS
842 struct turnstile_chain *tc;
843
844 MPASS(ts != NULL);
845 tc = TC_LOOKUP(ts->ts_lockobj);
846 mtx_assert(&tc->tc_lock, MA_OWNED);
847 #endif
848 return (TAILQ_FIRST(&ts->ts_blocked));
849 }
850
851 #ifdef DDB
852 static int db_pager_quit;
853
854 static void
855 print_thread(struct thread *td, const char *prefix)
856 {
857
858 db_printf("%s%p (tid %d, pid %d, \"%s\")\n", prefix, td, td->td_tid,
859 td->td_proc->p_pid, td->td_proc->p_comm);
860 }
861
862 static void
863 print_queue(struct threadqueue *queue, const char *header, const char *prefix)
864 {
865 struct thread *td;
866
867 db_printf("%s:\n", header);
868 if (TAILQ_EMPTY(queue)) {
869 db_printf("%sempty\n", prefix);
870 return;
871 }
872 TAILQ_FOREACH(td, queue, td_lockq) {
873 print_thread(td, prefix);
874 }
875 }
876
877 DB_SHOW_COMMAND(turnstile, db_show_turnstile)
878 {
879 struct turnstile_chain *tc;
880 struct turnstile *ts;
881 struct lock_object *lock;
882 int i;
883
884 if (!have_addr)
885 return;
886
887 /*
888 * First, see if there is an active turnstile for the lock indicated
889 * by the address.
890 */
891 lock = (struct lock_object *)addr;
892 tc = TC_LOOKUP(lock);
893 LIST_FOREACH(ts, &tc->tc_turnstiles, ts_hash)
894 if (ts->ts_lockobj == lock)
895 goto found;
896
897 /*
898 * Second, see if there is an active turnstile at the address
899 * indicated.
900 */
901 for (i = 0; i < TC_TABLESIZE; i++)
902 LIST_FOREACH(ts, &turnstile_chains[i].tc_turnstiles, ts_hash) {
903 if (ts == (struct turnstile *)addr)
904 goto found;
905 }
906
907 db_printf("Unable to locate a turnstile via %p\n", (void *)addr);
908 return;
909 found:
910 db_pager_quit = 0;
911 db_setup_paging(db_simple_pager, &db_pager_quit, db_lines_per_page);
912 lock = ts->ts_lockobj;
913 db_printf("Lock: %p - (%s) %s\n", lock, LOCK_CLASS(lock)->lc_name,
914 lock->lo_name);
915 if (ts->ts_owner)
916 print_thread(ts->ts_owner, "Lock Owner: ");
917 else
918 db_printf("Lock Owner: none\n");
919 print_queue((struct threadqueue *)&ts->ts_blocked, "Waiters", "\t");
920 print_queue((struct threadqueue *)&ts->ts_pending, "Pending Threads",
921 "\t");
922 }
923
924 /*
925 * Show all the threads a particular thread is waiting on based on
926 * non-sleepable and non-spin locks.
927 */
928 static void
929 print_lockchain(struct thread *td, const char *prefix)
930 {
931 struct lock_object *lock;
932 struct lock_class *class;
933 struct turnstile *ts;
934
935 /*
936 * Follow the chain. We keep walking as long as the thread is
937 * blocked on a turnstile that has an owner.
938 */
939 while (!db_pager_quit) {
940 db_printf("%sthread %d (pid %d, %s) ", prefix, td->td_tid,
941 td->td_proc->p_pid, td->td_proc->p_comm);
942 switch (td->td_state) {
943 case TDS_INACTIVE:
944 db_printf("is inactive\n");
945 return;
946 case TDS_CAN_RUN:
947 db_printf("can run\n");
948 return;
949 case TDS_RUNQ:
950 db_printf("is on a run queue\n");
951 return;
952 case TDS_RUNNING:
953 db_printf("running on CPU %d\n", td->td_oncpu);
954 return;
955 case TDS_INHIBITED:
956 if (TD_ON_LOCK(td)) {
957 ts = td->td_blocked;
958 lock = ts->ts_lockobj;
959 class = LOCK_CLASS(lock);
960 db_printf("blocked on lock %p (%s) \"%s\"\n",
961 lock, class->lc_name, lock->lo_name);
962 if (ts->ts_owner == NULL)
963 return;
964 td = ts->ts_owner;
965 break;
966 }
967 db_printf("inhibited\n");
968 return;
969 default:
970 db_printf("??? (%#x)\n", td->td_state);
971 return;
972 }
973 }
974 }
975
976 DB_SHOW_COMMAND(lockchain, db_show_lockchain)
977 {
978 struct thread *td;
979
980 /* Figure out which thread to start with. */
981 if (have_addr)
982 td = db_lookup_thread(addr, TRUE);
983 else
984 td = kdb_thread;
985
986 db_pager_quit = 0;
987 db_setup_paging(db_simple_pager, &db_pager_quit, db_lines_per_page);
988 print_lockchain(td, "");
989 }
990
991 DB_SHOW_COMMAND(allchains, db_show_allchains)
992 {
993 struct thread *td;
994 struct proc *p;
995 int i;
996
997 i = 1;
998 db_pager_quit = 0;
999 db_setup_paging(db_simple_pager, &db_pager_quit, db_lines_per_page);
1000 LIST_FOREACH(p, &allproc, p_list) {
1001 FOREACH_THREAD_IN_PROC(p, td) {
1002 if (TD_ON_LOCK(td) && LIST_EMPTY(&td->td_contested)) {
1003 db_printf("chain %d:\n", i++);
1004 print_lockchain(td, " ");
1005 }
1006 if (db_pager_quit)
1007 return;
1008 }
1009 }
1010 }
1011
1012 /*
1013 * Show all the threads a particular thread is waiting on based on
1014 * sleepable locks.
1015 */
1016 static void
1017 print_sleepchain(struct thread *td, const char *prefix)
1018 {
1019 struct thread *owner;
1020
1021 /*
1022 * Follow the chain. We keep walking as long as the thread is
1023 * blocked on a sleep lock that has an owner.
1024 */
1025 while (!db_pager_quit) {
1026 db_printf("%sthread %d (pid %d, %s) ", prefix, td->td_tid,
1027 td->td_proc->p_pid, td->td_proc->p_comm);
1028 switch (td->td_state) {
1029 case TDS_INACTIVE:
1030 db_printf("is inactive\n");
1031 return;
1032 case TDS_CAN_RUN:
1033 db_printf("can run\n");
1034 return;
1035 case TDS_RUNQ:
1036 db_printf("is on a run queue\n");
1037 return;
1038 case TDS_RUNNING:
1039 db_printf("running on CPU %d\n", td->td_oncpu);
1040 return;
1041 case TDS_INHIBITED:
1042 if (TD_ON_SLEEPQ(td)) {
1043 if (lockmgr_chain(td, &owner) ||
1044 sx_chain(td, &owner)) {
1045 if (owner == NULL)
1046 return;
1047 td = owner;
1048 break;
1049 }
1050 db_printf("sleeping on %p \"%s\"\n",
1051 td->td_wchan, td->td_wmesg);
1052 return;
1053 }
1054 db_printf("inhibited\n");
1055 return;
1056 default:
1057 db_printf("??? (%#x)\n", td->td_state);
1058 return;
1059 }
1060 }
1061 }
1062
1063 DB_SHOW_COMMAND(sleepchain, db_show_sleepchain)
1064 {
1065 struct thread *td;
1066
1067 /* Figure out which thread to start with. */
1068 if (have_addr)
1069 td = db_lookup_thread(addr, TRUE);
1070 else
1071 td = kdb_thread;
1072
1073 db_pager_quit = 0;
1074 db_setup_paging(db_simple_pager, &db_pager_quit, db_lines_per_page);
1075 print_sleepchain(td, "");
1076 }
1077
1078 static void print_waiters(struct turnstile *ts, int indent);
1079
1080 static void
1081 print_waiter(struct thread *td, int indent)
1082 {
1083 struct turnstile *ts;
1084 int i;
1085
1086 if (db_pager_quit)
1087 return;
1088 for (i = 0; i < indent; i++)
1089 db_printf(" ");
1090 print_thread(td, "thread ");
1091 LIST_FOREACH(ts, &td->td_contested, ts_link)
1092 print_waiters(ts, indent + 1);
1093 }
1094
1095 static void
1096 print_waiters(struct turnstile *ts, int indent)
1097 {
1098 struct lock_object *lock;
1099 struct lock_class *class;
1100 struct thread *td;
1101 int i;
1102
1103 if (db_pager_quit)
1104 return;
1105 lock = ts->ts_lockobj;
1106 class = LOCK_CLASS(lock);
1107 for (i = 0; i < indent; i++)
1108 db_printf(" ");
1109 db_printf("lock %p (%s) \"%s\"\n", lock, class->lc_name, lock->lo_name);
1110 TAILQ_FOREACH(td, &ts->ts_blocked, td_lockq)
1111 print_waiter(td, indent + 1);
1112 TAILQ_FOREACH(td, &ts->ts_pending, td_lockq)
1113 print_waiter(td, indent + 1);
1114 }
1115
1116 DB_SHOW_COMMAND(locktree, db_show_locktree)
1117 {
1118 struct lock_object *lock;
1119 struct lock_class *class;
1120 struct turnstile_chain *tc;
1121 struct turnstile *ts;
1122
1123 if (!have_addr)
1124 return;
1125 db_pager_quit = 0;
1126 db_setup_paging(db_simple_pager, &db_pager_quit, db_lines_per_page);
1127 lock = (struct lock_object *)addr;
1128 tc = TC_LOOKUP(lock);
1129 LIST_FOREACH(ts, &tc->tc_turnstiles, ts_hash)
1130 if (ts->ts_lockobj == lock)
1131 break;
1132 if (ts == NULL) {
1133 class = LOCK_CLASS(lock);
1134 db_printf("lock %p (%s) \"%s\"\n", lock, class->lc_name,
1135 lock->lo_name);
1136 } else
1137 print_waiters(ts, 0);
1138 }
1139 #endif
1140
1141 /*
1142 * Returns true if a turnstile is empty.
1143 */
1144 int
1145 turnstile_empty(struct turnstile *ts)
1146 {
1147 #ifdef INVARIANTS
1148 struct turnstile_chain *tc;
1149
1150 MPASS(ts != NULL);
1151 tc = TC_LOOKUP(ts->ts_lockobj);
1152 mtx_assert(&tc->tc_lock, MA_OWNED);
1153 #endif
1154 return (TAILQ_EMPTY(&ts->ts_blocked));
1155 }
Cache object: 4e285f72cdb1219397dc1d602d8e2fe5
|