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