sys/kern/subr_turnstile.c

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
40  * We wish to avoid bloating locks with an embedded turnstile and we do not
45  * hash table is a linked-lists of turnstiles and is called a turnstile
49  * Each time a thread is created, a turnstile is allocated from a UMA zone
51  * first thread to block, it lends its turnstile to the lock.  If the lock
52  * already has a turnstile, then it gives its turnstile to the lock's
53  * turnstile's free list.  When a thread is woken up, it takes a turnstile from
55  * blocked on the lock, then it reclaims the turnstile associated with the lock
79 #include <sys/turnstile.h>
90  * Constants for the hash table of turnstile chains.  TC_SHIFT is a magic
106  * first of these two is the turnstile chain list that a turnstile is on
108  * free list hung off of a turnstile that is attached to a lock.
110  * Each turnstile contains three lists of threads.  The two ts_blocked lists
111  * are linked list of threads blocked on the turnstile's lock.  One list is
118  *  c - turnstile chain lock
121 struct turnstile {
125 	LIST_ENTRY(turnstile) ts_hash;		/* (c) Chain and free list. */
126 	LIST_ENTRY(turnstile) ts_link;		/* (q) Contested locks. */
127 	LIST_HEAD(, turnstile) ts_free;		/* (c) Free turnstiles. */
133 	LIST_HEAD(, turnstile) tc_turnstiles;	/* List of turnstiles. */
143 static SYSCTL_NODE(_debug, OID_AUTO, turnstile, CTLFLAG_RD, 0,
144     "turnstile profiling");
146     "turnstile chain stats");
162 static int	turnstile_adjust_thread(struct turnstile *ts,
164 static struct thread *turnstile_first_waiter(struct turnstile *ts);
165 static void	turnstile_setowner(struct turnstile *ts, struct thread *owner);
185 	struct turnstile *ts;
193 	 * Grab a recursive lock on this turnstile chain so it stays locked
286  * Adjust the thread's position on a turnstile after its priority has been
290 turnstile_adjust_thread(struct turnstile *ts, struct thread *td)
299 	 * This thread may not be blocked on this turnstile anymore
304 	 * turnstile by either turnstile_signal() or
366 		mtx_init(&turnstile_chains[i].tc_lock, "turnstile chain",
386 		    chain_name, CTLFLAG_RD, NULL, "turnstile chain stats");
403 	turnstile_zone = uma_zcreate("TURNSTILE", sizeof(struct turnstile),
416  * Update a thread on the turnstile list after it's priority has been changed.
422 	struct turnstile *ts;
434 	/* Resort the turnstile on the list. */
439 	 * turnstile, then propagate our new priority up the chain.
452  * Set the owner of the lock this turnstile is attached to.
455 turnstile_setowner(struct turnstile *ts, struct thread *owner)
477 	struct turnstile *ts;
492 	struct turnstile *ts;
500 	mtx_init(&ts->ts_lock, "turnstile lock", NULL, MTX_SPIN | MTX_RECURSE);
507 	struct turnstile *ts;
514  * Get a turnstile for a new thread.
516 struct turnstile *
524  * Free a turnstile when a thread is destroyed.
527 turnstile_free(struct turnstile *ts)
534  * Lock the turnstile chain associated with the specified lock.
545 struct turnstile *
549 	struct turnstile *ts;
569 turnstile_cancel(struct turnstile *ts)
585  * Look up the turnstile for a lock in the hash table locking the associated
586  * turnstile chain along the way.  If no turnstile is found in the hash
589 struct turnstile *
593 	struct turnstile *ts;
606  * Unlock the turnstile chain associated with a given lock.
618  * Return a pointer to the thread waiting on this turnstile with the
619  * most important priority or NULL if the turnstile has no waiters.
622 turnstile_first_waiter(struct turnstile *ts)
634  * Take ownership of a turnstile and adjust the priority of the new
638 turnstile_claim(struct turnstile *ts)
669  * Block the current thread on the turnstile assicated with 'lock'.  This
672  * turnstile chain locked and will return with it unlocked.
675 turnstile_wait(struct turnstile *ts, struct thread *owner, int queue)
688 	 * If the lock does not already have a turnstile, use this thread's
689 	 * turnstile.  Otherwise insert the current thread into the
690 	 * turnstile already in use by this lock.
705 		    ("thread's turnstile has pending threads"));
707 		    ("thread's turnstile has exclusive waiters"));
709 		    ("thread's turnstile has shared waiters"));
711 		    ("thread's turnstile has a non-empty free list"));
761  * Pick the highest priority thread on this turnstile and put it on the
762  * pending list.  This must be called with the turnstile chain locked.
765 turnstile_signal(struct turnstile *ts, int queue)
789 	 * If the turnstile is now empty, remove it from its chain and
791 	 * turnstile from the free list and give it to the thread.
813  * the turnstile chain locked.
816 turnstile_broadcast(struct turnstile *ts, int queue)
819 	struct turnstile *ts1;
828 	 * turnstile from the hash queue.
842 	 * Give a turnstile to each thread.  The last thread gets
843 	 * this turnstile if the turnstile is empty.
862  * current thread appropriately.  This must be called with the turnstile
866 turnstile_unpend(struct turnstile *ts, int owner_type)
869 	struct turnstile *nts;
879 	 * Move the list of pending threads out of the turnstile and
899 	 * Remove the turnstile from this thread's list of contested locks
901 	 * not be blocking on the turnstile until it is claimed by a new
947  * Give up ownership of a turnstile.  This must be called with the
948  * turnstile chain locked.
951 turnstile_disown(struct turnstile *ts)
964 	 * Remove the turnstile from this thread's list of contested locks
966 	 * not be blocking on the turnstile until it is claimed by a new
995  * Return the first thread in a turnstile.
998 turnstile_head(struct turnstile *ts, int queue)
1010  * Returns true if a sub-queue of a turnstile is empty.
1013 turnstile_empty(struct turnstile *ts, int queue)
1049 DB_SHOW_COMMAND(turnstile, db_show_turnstile)
1052 	struct turnstile *ts;
1060 	 * First, see if there is an active turnstile for the lock indicated
1070 	 * Second, see if there is an active turnstile at the address
1075 			if (ts == (struct turnstile *)addr)
1079 	db_printf("Unable to locate a turnstile via %p\n", (void *)addr);
1105 	struct turnstile *ts;
1109 	 * blocked on a turnstile that has an owner.
1247 static void	print_waiters(struct turnstile *ts, int indent);
1252 	struct turnstile *ts;
1265 print_waiters(struct turnstile *ts, int indent)
1292 	struct turnstile *ts;