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