17c478bd9Sstevel@tonic-gate /*
27c478bd9Sstevel@tonic-gate * CDDL HEADER START
37c478bd9Sstevel@tonic-gate *
47c478bd9Sstevel@tonic-gate * The contents of this file are subject to the terms of the
57c478bd9Sstevel@tonic-gate * Common Development and Distribution License, Version 1.0 only
67c478bd9Sstevel@tonic-gate * (the "License"). You may not use this file except in compliance
77c478bd9Sstevel@tonic-gate * with the License.
87c478bd9Sstevel@tonic-gate *
97c478bd9Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
107c478bd9Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing.
117c478bd9Sstevel@tonic-gate * See the License for the specific language governing permissions
127c478bd9Sstevel@tonic-gate * and limitations under the License.
137c478bd9Sstevel@tonic-gate *
147c478bd9Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each
157c478bd9Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
167c478bd9Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the
177c478bd9Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying
187c478bd9Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner]
197c478bd9Sstevel@tonic-gate *
207c478bd9Sstevel@tonic-gate * CDDL HEADER END
217c478bd9Sstevel@tonic-gate */
227c478bd9Sstevel@tonic-gate /*
237c478bd9Sstevel@tonic-gate * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
247c478bd9Sstevel@tonic-gate * Use is subject to license terms.
257c478bd9Sstevel@tonic-gate */
267c478bd9Sstevel@tonic-gate
277c478bd9Sstevel@tonic-gate #include <sys/param.h>
287c478bd9Sstevel@tonic-gate #include <sys/systm.h>
297c478bd9Sstevel@tonic-gate #include <sys/thread.h>
307c478bd9Sstevel@tonic-gate #include <sys/proc.h>
317c478bd9Sstevel@tonic-gate #include <sys/debug.h>
327c478bd9Sstevel@tonic-gate #include <sys/cpuvar.h>
337c478bd9Sstevel@tonic-gate #include <sys/sleepq.h>
347c478bd9Sstevel@tonic-gate #include <sys/sdt.h>
357c478bd9Sstevel@tonic-gate
367c478bd9Sstevel@tonic-gate /*
377c478bd9Sstevel@tonic-gate * Operations on sleepq_t structures.
387c478bd9Sstevel@tonic-gate *
397c478bd9Sstevel@tonic-gate * A sleep queue is a singly linked NULL-terminated list with doubly
407c478bd9Sstevel@tonic-gate * linked circular sublists. The singly linked list is in descending
417c478bd9Sstevel@tonic-gate * priority order and FIFO for threads of the same priority. It links
427c478bd9Sstevel@tonic-gate * through the t_link field of the thread structure. The doubly linked
437c478bd9Sstevel@tonic-gate * sublists link threads of the same priority. They use the t_priforw
447c478bd9Sstevel@tonic-gate * and t_priback fields of the thread structure.
457c478bd9Sstevel@tonic-gate *
467c478bd9Sstevel@tonic-gate * Graphically (with priorities in parens):
477c478bd9Sstevel@tonic-gate *
487c478bd9Sstevel@tonic-gate * ________________ _______ _______
497c478bd9Sstevel@tonic-gate * / \ / \ / \
507c478bd9Sstevel@tonic-gate * | | | | | |
517c478bd9Sstevel@tonic-gate * v v v v v v
527c478bd9Sstevel@tonic-gate * t1(60)-->t2(60)-->t3(60)-->t4(50)-->t5(50)-->t6(30)-->t7(0)-->t8(0)
537c478bd9Sstevel@tonic-gate * ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
547c478bd9Sstevel@tonic-gate * | | | | | | | | | |
557c478bd9Sstevel@tonic-gate * \______/ \______/ \_______/ \__/ \_______/
567c478bd9Sstevel@tonic-gate *
577c478bd9Sstevel@tonic-gate * There are three interesting operations on a sleepq list: inserting
587c478bd9Sstevel@tonic-gate * a thread into the proper position according to priority; removing a
597c478bd9Sstevel@tonic-gate * thread given a pointer to it; and walking the list, possibly
607c478bd9Sstevel@tonic-gate * removing threads along the way. This design allows all three
617c478bd9Sstevel@tonic-gate * operations to be performed efficiently and easily.
627c478bd9Sstevel@tonic-gate *
637c478bd9Sstevel@tonic-gate * To insert a thread, traverse the list looking for the sublist of
647c478bd9Sstevel@tonic-gate * the same priority as the thread (or one of a lower priority,
657c478bd9Sstevel@tonic-gate * meaning there are no other threads in the list of the same
667c478bd9Sstevel@tonic-gate * priority). This can be done without touching all threads in the
677c478bd9Sstevel@tonic-gate * list by following the links between the first threads in each
687c478bd9Sstevel@tonic-gate * sublist. Given a thread t that is the head of a sublist (the first
697c478bd9Sstevel@tonic-gate * thread of that priority found when following the t_link pointers),
707c478bd9Sstevel@tonic-gate * t->t_priback->t_link points to the head of the next sublist. It's
717c478bd9Sstevel@tonic-gate * important to do this since a sleepq may contain thousands of
727c478bd9Sstevel@tonic-gate * threads.
737c478bd9Sstevel@tonic-gate *
747c478bd9Sstevel@tonic-gate * Removing a thread from the list is also efficient. First, the
757c478bd9Sstevel@tonic-gate * t_sleepq field contains a pointer to the sleepq on which a thread
767c478bd9Sstevel@tonic-gate * is waiting (or NULL if it's not on a sleepq). This is used to
777c478bd9Sstevel@tonic-gate * determine if the given thread is on the given sleepq without
787c478bd9Sstevel@tonic-gate * searching the list. Assuming it is, if it's not the head of a
797c478bd9Sstevel@tonic-gate * sublist, just remove it from the sublist and use the t_priback
807c478bd9Sstevel@tonic-gate * pointer to find the thread that points to it with t_link. If it is
817c478bd9Sstevel@tonic-gate * the head of a sublist, search for it by walking the sublist heads,
827c478bd9Sstevel@tonic-gate * similar to searching for a given priority level when inserting a
837c478bd9Sstevel@tonic-gate * thread.
847c478bd9Sstevel@tonic-gate *
857c478bd9Sstevel@tonic-gate * To walk the list, simply follow the t_link pointers. Removing
867c478bd9Sstevel@tonic-gate * threads along the way can be done easily if the code maintains a
877c478bd9Sstevel@tonic-gate * pointer to the t_link field that pointed to the thread being
887c478bd9Sstevel@tonic-gate * removed.
897c478bd9Sstevel@tonic-gate */
907c478bd9Sstevel@tonic-gate
917c478bd9Sstevel@tonic-gate sleepq_head_t sleepq_head[NSLEEPQ];
927c478bd9Sstevel@tonic-gate
937c478bd9Sstevel@tonic-gate /*
947c478bd9Sstevel@tonic-gate * Common code to unlink a thread from the queue. tpp is a pointer to
957c478bd9Sstevel@tonic-gate * the t_link pointer that points to tp.
967c478bd9Sstevel@tonic-gate */
977c478bd9Sstevel@tonic-gate void
sleepq_unlink(kthread_t ** tpp,kthread_t * tp)987c478bd9Sstevel@tonic-gate sleepq_unlink(kthread_t **tpp, kthread_t *tp)
997c478bd9Sstevel@tonic-gate {
1007c478bd9Sstevel@tonic-gate ASSERT(*tpp == tp);
1017c478bd9Sstevel@tonic-gate ASSERT(tp->t_sleepq != NULL);
1027c478bd9Sstevel@tonic-gate
1037c478bd9Sstevel@tonic-gate /* remove it from the t_link list */
1047c478bd9Sstevel@tonic-gate *tpp = tp->t_link;
1057c478bd9Sstevel@tonic-gate
1067c478bd9Sstevel@tonic-gate /*
1077c478bd9Sstevel@tonic-gate * Take it off the priority sublist if there's more than one
1087c478bd9Sstevel@tonic-gate * thread there.
1097c478bd9Sstevel@tonic-gate */
1107c478bd9Sstevel@tonic-gate if (tp->t_priforw != tp) {
1117c478bd9Sstevel@tonic-gate tp->t_priback->t_priforw = tp->t_priforw;
1127c478bd9Sstevel@tonic-gate tp->t_priforw->t_priback = tp->t_priback;
1137c478bd9Sstevel@tonic-gate }
1147c478bd9Sstevel@tonic-gate
1157c478bd9Sstevel@tonic-gate /* Clear out the link junk */
1167c478bd9Sstevel@tonic-gate tp->t_link = NULL;
1177c478bd9Sstevel@tonic-gate tp->t_sleepq = NULL;
1187c478bd9Sstevel@tonic-gate tp->t_priforw = NULL;
1197c478bd9Sstevel@tonic-gate tp->t_priback = NULL;
1207c478bd9Sstevel@tonic-gate }
1217c478bd9Sstevel@tonic-gate
1227c478bd9Sstevel@tonic-gate /*
1237c478bd9Sstevel@tonic-gate * Insert thread t into sleep queue spq in dispatch priority order.
1247c478bd9Sstevel@tonic-gate * For lwp_rwlock_t queueing, we must queue writers ahead of readers
1257c478bd9Sstevel@tonic-gate * of the same priority. We do this by making writers appear to have
1267c478bd9Sstevel@tonic-gate * a half point higher priority for purposes of priority comparisions.
1277c478bd9Sstevel@tonic-gate */
1287c478bd9Sstevel@tonic-gate #define CMP_PRIO(t) ((DISP_PRIO(t) << 1) + (t)->t_writer)
1297c478bd9Sstevel@tonic-gate void
sleepq_insert(sleepq_t * spq,kthread_t * t)1307c478bd9Sstevel@tonic-gate sleepq_insert(sleepq_t *spq, kthread_t *t)
1317c478bd9Sstevel@tonic-gate {
1327c478bd9Sstevel@tonic-gate kthread_t *next_tp;
1337c478bd9Sstevel@tonic-gate kthread_t *last_tp;
1347c478bd9Sstevel@tonic-gate kthread_t **tpp;
1357c478bd9Sstevel@tonic-gate pri_t tpri, next_pri, last_pri = -1;
1367c478bd9Sstevel@tonic-gate
1377c478bd9Sstevel@tonic-gate ASSERT(THREAD_LOCK_HELD(t)); /* holding the lock on the sleepq */
1387c478bd9Sstevel@tonic-gate ASSERT(t->t_sleepq == NULL); /* not already on a sleep queue */
1397c478bd9Sstevel@tonic-gate
1407c478bd9Sstevel@tonic-gate tpri = CMP_PRIO(t);
1417c478bd9Sstevel@tonic-gate tpp = &spq->sq_first;
142*c6f039c7SToomas Soome last_tp = NULL;
1437c478bd9Sstevel@tonic-gate while ((next_tp = *tpp) != NULL) {
1447c478bd9Sstevel@tonic-gate next_pri = CMP_PRIO(next_tp);
1457c478bd9Sstevel@tonic-gate if (tpri > next_pri)
1467c478bd9Sstevel@tonic-gate break;
1477c478bd9Sstevel@tonic-gate last_tp = next_tp->t_priback;
1487c478bd9Sstevel@tonic-gate last_pri = next_pri;
1497c478bd9Sstevel@tonic-gate tpp = &last_tp->t_link;
1507c478bd9Sstevel@tonic-gate }
1517c478bd9Sstevel@tonic-gate *tpp = t;
1527c478bd9Sstevel@tonic-gate t->t_link = next_tp;
153*c6f039c7SToomas Soome if (last_tp != NULL && last_pri == tpri) {
1547c478bd9Sstevel@tonic-gate /* last_tp points to the last thread of this priority */
1557c478bd9Sstevel@tonic-gate t->t_priback = last_tp;
1567c478bd9Sstevel@tonic-gate t->t_priforw = last_tp->t_priforw;
1577c478bd9Sstevel@tonic-gate last_tp->t_priforw->t_priback = t;
1587c478bd9Sstevel@tonic-gate last_tp->t_priforw = t;
1597c478bd9Sstevel@tonic-gate } else {
1607c478bd9Sstevel@tonic-gate t->t_priback = t->t_priforw = t;
1617c478bd9Sstevel@tonic-gate }
1627c478bd9Sstevel@tonic-gate t->t_sleepq = spq;
1637c478bd9Sstevel@tonic-gate }
1647c478bd9Sstevel@tonic-gate
1657c478bd9Sstevel@tonic-gate
1667c478bd9Sstevel@tonic-gate /*
1677c478bd9Sstevel@tonic-gate * Yank a particular thread out of sleep queue and wake it up.
1687c478bd9Sstevel@tonic-gate */
1697c478bd9Sstevel@tonic-gate void
sleepq_unsleep(kthread_t * t)1707c478bd9Sstevel@tonic-gate sleepq_unsleep(kthread_t *t)
1717c478bd9Sstevel@tonic-gate {
1727c478bd9Sstevel@tonic-gate ASSERT(THREAD_LOCK_HELD(t)); /* thread locked via sleepq */
1737c478bd9Sstevel@tonic-gate
1747c478bd9Sstevel@tonic-gate /* remove it from queue */
1757c478bd9Sstevel@tonic-gate sleepq_dequeue(t);
1767c478bd9Sstevel@tonic-gate
1777c478bd9Sstevel@tonic-gate /* wake it up */
1787c478bd9Sstevel@tonic-gate t->t_sobj_ops = NULL;
1797c478bd9Sstevel@tonic-gate t->t_wchan = NULL;
1807c478bd9Sstevel@tonic-gate t->t_wchan0 = NULL;
1817c478bd9Sstevel@tonic-gate ASSERT(t->t_state == TS_SLEEP);
1827c478bd9Sstevel@tonic-gate /*
1837c478bd9Sstevel@tonic-gate * Change thread to transition state without
1847c478bd9Sstevel@tonic-gate * dropping the sleep queue lock.
1857c478bd9Sstevel@tonic-gate */
1867c478bd9Sstevel@tonic-gate THREAD_TRANSITION_NOLOCK(t);
1877c478bd9Sstevel@tonic-gate }
1887c478bd9Sstevel@tonic-gate
1897c478bd9Sstevel@tonic-gate /*
1907c478bd9Sstevel@tonic-gate * Yank a particular thread out of sleep queue but don't wake it up.
1917c478bd9Sstevel@tonic-gate */
1927c478bd9Sstevel@tonic-gate void
sleepq_dequeue(kthread_t * t)1937c478bd9Sstevel@tonic-gate sleepq_dequeue(kthread_t *t)
1947c478bd9Sstevel@tonic-gate {
1957c478bd9Sstevel@tonic-gate kthread_t *nt;
1967c478bd9Sstevel@tonic-gate kthread_t **ptl;
1977c478bd9Sstevel@tonic-gate
1987c478bd9Sstevel@tonic-gate ASSERT(THREAD_LOCK_HELD(t)); /* thread locked via sleepq */
1997c478bd9Sstevel@tonic-gate ASSERT(t->t_sleepq != NULL);
2007c478bd9Sstevel@tonic-gate
2017c478bd9Sstevel@tonic-gate ptl = &t->t_priback->t_link;
2027c478bd9Sstevel@tonic-gate /*
2037c478bd9Sstevel@tonic-gate * Is it the head of a priority sublist? If so, need to walk
2047c478bd9Sstevel@tonic-gate * the priorities to find the t_link pointer that points to it.
2057c478bd9Sstevel@tonic-gate */
2067c478bd9Sstevel@tonic-gate if (*ptl != t) {
2077c478bd9Sstevel@tonic-gate /*
2087c478bd9Sstevel@tonic-gate * Find the right priority level.
2097c478bd9Sstevel@tonic-gate */
2107c478bd9Sstevel@tonic-gate ptl = &t->t_sleepq->sq_first;
2117c478bd9Sstevel@tonic-gate while ((nt = *ptl) != t)
2127c478bd9Sstevel@tonic-gate ptl = &nt->t_priback->t_link;
2137c478bd9Sstevel@tonic-gate }
2147c478bd9Sstevel@tonic-gate sleepq_unlink(ptl, t);
2157c478bd9Sstevel@tonic-gate }
2167c478bd9Sstevel@tonic-gate
2177c478bd9Sstevel@tonic-gate kthread_t *
sleepq_wakeone_chan(sleepq_t * spq,void * chan)2187c478bd9Sstevel@tonic-gate sleepq_wakeone_chan(sleepq_t *spq, void *chan)
2197c478bd9Sstevel@tonic-gate {
2207c478bd9Sstevel@tonic-gate kthread_t *tp;
2217c478bd9Sstevel@tonic-gate kthread_t **tpp;
2227c478bd9Sstevel@tonic-gate
2237c478bd9Sstevel@tonic-gate tpp = &spq->sq_first;
2247c478bd9Sstevel@tonic-gate while ((tp = *tpp) != NULL) {
2257c478bd9Sstevel@tonic-gate if (tp->t_wchan == chan) {
2267c478bd9Sstevel@tonic-gate ASSERT(tp->t_wchan0 == NULL);
2277c478bd9Sstevel@tonic-gate sleepq_unlink(tpp, tp);
2287c478bd9Sstevel@tonic-gate DTRACE_SCHED1(wakeup, kthread_t *, tp);
2297c478bd9Sstevel@tonic-gate tp->t_wchan = NULL;
2307c478bd9Sstevel@tonic-gate tp->t_sobj_ops = NULL;
2317c478bd9Sstevel@tonic-gate /*
2327c478bd9Sstevel@tonic-gate * Let the target thread know it was cv_signal()ed.
2337c478bd9Sstevel@tonic-gate * This assumes that cv_signal() is the only
2347c478bd9Sstevel@tonic-gate * caller of sleepq_wakeone_chan(). If this
2357c478bd9Sstevel@tonic-gate * becomes false, this code must be revised.
2367c478bd9Sstevel@tonic-gate */
2377c478bd9Sstevel@tonic-gate tp->t_schedflag |= TS_SIGNALLED;
2387c478bd9Sstevel@tonic-gate ASSERT(tp->t_state == TS_SLEEP);
2397c478bd9Sstevel@tonic-gate CL_WAKEUP(tp);
2407c478bd9Sstevel@tonic-gate thread_unlock_high(tp); /* drop runq lock */
2417c478bd9Sstevel@tonic-gate return (tp);
2427c478bd9Sstevel@tonic-gate }
2437c478bd9Sstevel@tonic-gate tpp = &tp->t_link;
2447c478bd9Sstevel@tonic-gate }
2457c478bd9Sstevel@tonic-gate return (NULL);
2467c478bd9Sstevel@tonic-gate }
2477c478bd9Sstevel@tonic-gate
2487c478bd9Sstevel@tonic-gate void
sleepq_wakeall_chan(sleepq_t * spq,void * chan)2497c478bd9Sstevel@tonic-gate sleepq_wakeall_chan(sleepq_t *spq, void *chan)
2507c478bd9Sstevel@tonic-gate {
2517c478bd9Sstevel@tonic-gate kthread_t *tp;
2527c478bd9Sstevel@tonic-gate kthread_t **tpp;
2537c478bd9Sstevel@tonic-gate
2547c478bd9Sstevel@tonic-gate tpp = &spq->sq_first;
2557c478bd9Sstevel@tonic-gate while ((tp = *tpp) != NULL) {
2567c478bd9Sstevel@tonic-gate if (tp->t_wchan == chan) {
2577c478bd9Sstevel@tonic-gate ASSERT(tp->t_wchan0 == NULL);
2587c478bd9Sstevel@tonic-gate sleepq_unlink(tpp, tp);
2597c478bd9Sstevel@tonic-gate DTRACE_SCHED1(wakeup, kthread_t *, tp);
2607c478bd9Sstevel@tonic-gate tp->t_wchan = NULL;
2617c478bd9Sstevel@tonic-gate tp->t_sobj_ops = NULL;
2627c478bd9Sstevel@tonic-gate ASSERT(tp->t_state == TS_SLEEP);
2637c478bd9Sstevel@tonic-gate CL_WAKEUP(tp);
2647c478bd9Sstevel@tonic-gate thread_unlock_high(tp); /* drop runq lock */
2657c478bd9Sstevel@tonic-gate continue;
2667c478bd9Sstevel@tonic-gate }
2677c478bd9Sstevel@tonic-gate tpp = &tp->t_link;
2687c478bd9Sstevel@tonic-gate }
2697c478bd9Sstevel@tonic-gate }
270