xref: /illumos-gate/usr/src/uts/common/os/sleepq.c (revision c6f039c7)
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, Version 1.0 only
6  * (the "License").  You may not use this file except in compliance
7  * with the License.
8  *
9  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10  * or http://www.opensolaris.org/os/licensing.
11  * See the License for the specific language governing permissions
12  * and limitations under the License.
13  *
14  * When distributing Covered Code, include this CDDL HEADER in each
15  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16  * If applicable, add the following below this CDDL HEADER, with the
17  * fields enclosed by brackets "[]" replaced with your own identifying
18  * information: Portions Copyright [yyyy] [name of copyright owner]
19  *
20  * CDDL HEADER END
21  */
22 /*
23  * Copyright 2004 Sun Microsystems, Inc.  All rights reserved.
24  * Use is subject to license terms.
25  */
26 
27 #include <sys/param.h>
28 #include <sys/systm.h>
29 #include <sys/thread.h>
30 #include <sys/proc.h>
31 #include <sys/debug.h>
32 #include <sys/cpuvar.h>
33 #include <sys/sleepq.h>
34 #include <sys/sdt.h>
35 
36 /*
37  * Operations on sleepq_t structures.
38  *
39  * A sleep queue is a singly linked NULL-terminated list with doubly
40  * linked circular sublists.  The singly linked list is in descending
41  * priority order and FIFO for threads of the same priority.  It links
42  * through the t_link field of the thread structure.  The doubly linked
43  * sublists link threads of the same priority.  They use the t_priforw
44  * and t_priback fields of the thread structure.
45  *
46  * Graphically (with priorities in parens):
47  *
48  *         ________________           _______                   _______
49  *        /                \         /       \                 /       \
50  *        |                |         |       |                 |       |
51  *        v                v         v       v                 v       v
52  *     t1(60)-->t2(60)-->t3(60)-->t4(50)-->t5(50)-->t6(30)-->t7(0)-->t8(0)
53  *        ^      ^  ^      ^         ^       ^       ^  ^      ^       ^
54  *        |      |  |      |         |       |       |  |      |       |
55  *        \______/  \______/         \_______/       \__/      \_______/
56  *
57  * There are three interesting operations on a sleepq list: inserting
58  * a thread into the proper position according to priority; removing a
59  * thread given a pointer to it; and walking the list, possibly
60  * removing threads along the way.  This design allows all three
61  * operations to be performed efficiently and easily.
62  *
63  * To insert a thread, traverse the list looking for the sublist of
64  * the same priority as the thread (or one of a lower priority,
65  * meaning there are no other threads in the list of the same
66  * priority).  This can be done without touching all threads in the
67  * list by following the links between the first threads in each
68  * sublist.  Given a thread t that is the head of a sublist (the first
69  * thread of that priority found when following the t_link pointers),
70  * t->t_priback->t_link points to the head of the next sublist.  It's
71  * important to do this since a sleepq may contain thousands of
72  * threads.
73  *
74  * Removing a thread from the list is also efficient.  First, the
75  * t_sleepq field contains a pointer to the sleepq on which a thread
76  * is waiting (or NULL if it's not on a sleepq).  This is used to
77  * determine if the given thread is on the given sleepq without
78  * searching the list.  Assuming it is, if it's not the head of a
79  * sublist, just remove it from the sublist and use the t_priback
80  * pointer to find the thread that points to it with t_link.  If it is
81  * the head of a sublist, search for it by walking the sublist heads,
82  * similar to searching for a given priority level when inserting a
83  * thread.
84  *
85  * To walk the list, simply follow the t_link pointers.  Removing
86  * threads along the way can be done easily if the code maintains a
87  * pointer to the t_link field that pointed to the thread being
88  * removed.
89  */
90 
91 sleepq_head_t sleepq_head[NSLEEPQ];
92 
93 /*
94  * Common code to unlink a thread from the queue.  tpp is a pointer to
95  * the t_link pointer that points to tp.
96  */
97 void
sleepq_unlink(kthread_t ** tpp,kthread_t * tp)98 sleepq_unlink(kthread_t **tpp, kthread_t *tp)
99 {
100 	ASSERT(*tpp == tp);
101 	ASSERT(tp->t_sleepq != NULL);
102 
103 	/* remove it from the t_link list */
104 	*tpp = tp->t_link;
105 
106 	/*
107 	 * Take it off the priority sublist if there's more than one
108 	 * thread there.
109 	 */
110 	if (tp->t_priforw != tp) {
111 		tp->t_priback->t_priforw = tp->t_priforw;
112 		tp->t_priforw->t_priback = tp->t_priback;
113 	}
114 
115 	/* Clear out the link junk */
116 	tp->t_link = NULL;
117 	tp->t_sleepq = NULL;
118 	tp->t_priforw = NULL;
119 	tp->t_priback = NULL;
120 }
121 
122 /*
123  * Insert thread t into sleep queue spq in dispatch priority order.
124  * For lwp_rwlock_t queueing, we must queue writers ahead of readers
125  * of the same priority.  We do this by making writers appear to have
126  * a half point higher priority for purposes of priority comparisions.
127  */
128 #define	CMP_PRIO(t)	((DISP_PRIO(t) << 1) + (t)->t_writer)
129 void
sleepq_insert(sleepq_t * spq,kthread_t * t)130 sleepq_insert(sleepq_t *spq, kthread_t *t)
131 {
132 	kthread_t	*next_tp;
133 	kthread_t	*last_tp;
134 	kthread_t	**tpp;
135 	pri_t		tpri, next_pri, last_pri = -1;
136 
137 	ASSERT(THREAD_LOCK_HELD(t));	/* holding the lock on the sleepq */
138 	ASSERT(t->t_sleepq == NULL);	/* not already on a sleep queue */
139 
140 	tpri = CMP_PRIO(t);
141 	tpp = &spq->sq_first;
142 	last_tp = NULL;
143 	while ((next_tp = *tpp) != NULL) {
144 		next_pri = CMP_PRIO(next_tp);
145 		if (tpri > next_pri)
146 			break;
147 		last_tp = next_tp->t_priback;
148 		last_pri = next_pri;
149 		tpp = &last_tp->t_link;
150 	}
151 	*tpp = t;
152 	t->t_link = next_tp;
153 	if (last_tp != NULL && last_pri == tpri) {
154 		/* last_tp points to the last thread of this priority */
155 		t->t_priback = last_tp;
156 		t->t_priforw = last_tp->t_priforw;
157 		last_tp->t_priforw->t_priback = t;
158 		last_tp->t_priforw = t;
159 	} else {
160 		t->t_priback = t->t_priforw = t;
161 	}
162 	t->t_sleepq = spq;
163 }
164 
165 
166 /*
167  * Yank a particular thread out of sleep queue and wake it up.
168  */
169 void
sleepq_unsleep(kthread_t * t)170 sleepq_unsleep(kthread_t *t)
171 {
172 	ASSERT(THREAD_LOCK_HELD(t));	/* thread locked via sleepq */
173 
174 	/* remove it from queue */
175 	sleepq_dequeue(t);
176 
177 	/* wake it up */
178 	t->t_sobj_ops = NULL;
179 	t->t_wchan = NULL;
180 	t->t_wchan0 = NULL;
181 	ASSERT(t->t_state == TS_SLEEP);
182 	/*
183 	 * Change thread to transition state without
184 	 * dropping the sleep queue lock.
185 	 */
186 	THREAD_TRANSITION_NOLOCK(t);
187 }
188 
189 /*
190  * Yank a particular thread out of sleep queue but don't wake it up.
191  */
192 void
sleepq_dequeue(kthread_t * t)193 sleepq_dequeue(kthread_t *t)
194 {
195 	kthread_t	*nt;
196 	kthread_t	**ptl;
197 
198 	ASSERT(THREAD_LOCK_HELD(t));	/* thread locked via sleepq */
199 	ASSERT(t->t_sleepq != NULL);
200 
201 	ptl = &t->t_priback->t_link;
202 	/*
203 	 * Is it the head of a priority sublist?  If so, need to walk
204 	 * the priorities to find the t_link pointer that points to it.
205 	 */
206 	if (*ptl != t) {
207 		/*
208 		 * Find the right priority level.
209 		 */
210 		ptl = &t->t_sleepq->sq_first;
211 		while ((nt = *ptl) != t)
212 			ptl = &nt->t_priback->t_link;
213 	}
214 	sleepq_unlink(ptl, t);
215 }
216 
217 kthread_t *
sleepq_wakeone_chan(sleepq_t * spq,void * chan)218 sleepq_wakeone_chan(sleepq_t *spq, void *chan)
219 {
220 	kthread_t 	*tp;
221 	kthread_t	**tpp;
222 
223 	tpp = &spq->sq_first;
224 	while ((tp = *tpp) != NULL) {
225 		if (tp->t_wchan == chan) {
226 			ASSERT(tp->t_wchan0 == NULL);
227 			sleepq_unlink(tpp, tp);
228 			DTRACE_SCHED1(wakeup, kthread_t *, tp);
229 			tp->t_wchan = NULL;
230 			tp->t_sobj_ops = NULL;
231 			/*
232 			 * Let the target thread know it was cv_signal()ed.
233 			 * This assumes that cv_signal() is the only
234 			 * caller of sleepq_wakeone_chan().  If this
235 			 * becomes false, this code must be revised.
236 			 */
237 			tp->t_schedflag |= TS_SIGNALLED;
238 			ASSERT(tp->t_state == TS_SLEEP);
239 			CL_WAKEUP(tp);
240 			thread_unlock_high(tp);		/* drop runq lock */
241 			return (tp);
242 		}
243 		tpp = &tp->t_link;
244 	}
245 	return (NULL);
246 }
247 
248 void
sleepq_wakeall_chan(sleepq_t * spq,void * chan)249 sleepq_wakeall_chan(sleepq_t *spq, void *chan)
250 {
251 	kthread_t 	*tp;
252 	kthread_t	**tpp;
253 
254 	tpp = &spq->sq_first;
255 	while ((tp = *tpp) != NULL) {
256 		if (tp->t_wchan == chan) {
257 			ASSERT(tp->t_wchan0 == NULL);
258 			sleepq_unlink(tpp, tp);
259 			DTRACE_SCHED1(wakeup, kthread_t *, tp);
260 			tp->t_wchan = NULL;
261 			tp->t_sobj_ops = NULL;
262 			ASSERT(tp->t_state == TS_SLEEP);
263 			CL_WAKEUP(tp);
264 			thread_unlock_high(tp);		/* drop runq lock */
265 			continue;
266 		}
267 		tpp = &tp->t_link;
268 	}
269 }
270