Print this page
patch remove-dont-swap-flag
Split |
Close |
Expand all |
Collapse all |
--- old/usr/src/uts/common/os/waitq.c
+++ new/usr/src/uts/common/os/waitq.c
1 1 /*
2 2 * CDDL HEADER START
3 3 *
4 4 * The contents of this file are subject to the terms of the
5 5 * Common Development and Distribution License (the "License").
6 6 * You may not use this file except in compliance with the License.
7 7 *
8 8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9 9 * or http://www.opensolaris.org/os/licensing.
10 10 * See the License for the specific language governing permissions
11 11 * and limitations under the License.
12 12 *
13 13 * When distributing Covered Code, include this CDDL HEADER in each
14 14 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15 15 * If applicable, add the following below this CDDL HEADER, with the
16 16 * fields enclosed by brackets "[]" replaced with your own identifying
17 17 * information: Portions Copyright [yyyy] [name of copyright owner]
18 18 *
19 19 * CDDL HEADER END
20 20 */
21 21 /*
22 22 * Copyright 2008 Sun Microsystems, Inc. All rights reserved.
23 23 * Use is subject to license terms.
24 24 */
25 25
26 26 #include <sys/param.h>
27 27 #include <sys/systm.h>
28 28 #include <sys/thread.h>
29 29 #include <sys/class.h>
30 30 #include <sys/debug.h>
31 31 #include <sys/cpuvar.h>
32 32 #include <sys/waitq.h>
33 33 #include <sys/cmn_err.h>
34 34 #include <sys/time.h>
35 35 #include <sys/dtrace.h>
36 36 #include <sys/sdt.h>
37 37 #include <sys/zone.h>
38 38
39 39 /*
40 40 * Wait queue implementation.
41 41 */
42 42
43 43 void
44 44 waitq_init(waitq_t *wq)
45 45 {
46 46 DISP_LOCK_INIT(&wq->wq_lock);
47 47 wq->wq_first = NULL;
48 48 wq->wq_count = 0;
49 49 wq->wq_blocked = B_TRUE;
50 50 }
51 51
52 52 void
53 53 waitq_fini(waitq_t *wq)
54 54 {
55 55 ASSERT(wq->wq_count == 0);
56 56 ASSERT(wq->wq_first == NULL);
57 57 ASSERT(wq->wq_blocked == B_TRUE);
58 58 ASSERT(!DISP_LOCK_HELD(&wq->wq_lock));
59 59
60 60 DISP_LOCK_DESTROY(&wq->wq_lock);
61 61 }
62 62
63 63 /*
64 64 * Operations on waitq_t structures.
65 65 *
66 66 * A wait queue is a singly linked NULL-terminated list with doubly
67 67 * linked circular sublists. The singly linked list is in descending
68 68 * priority order and FIFO for threads of the same priority. It links
69 69 * through the t_link field of the thread structure. The doubly linked
70 70 * sublists link threads of the same priority. They use the t_priforw
71 71 * and t_priback fields of the thread structure.
72 72 *
73 73 * Graphically (with priorities in parens):
74 74 *
75 75 * ________________ _______ _______
76 76 * / \ / \ / \
77 77 * | | | | | |
78 78 * v v v v v v
79 79 * t1(60)-->t2(60)-->t3(60)-->t4(50)-->t5(50)-->t6(30)-->t7(0)-->t8(0)
80 80 * ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
81 81 * | | | | | | | | | |
82 82 * \______/ \______/ \_______/ \__/ \_______/
83 83 *
84 84 * There are three interesting operations on a waitq list: inserting
85 85 * a thread into the proper position according to priority; removing a
86 86 * thread given a pointer to it; and walking the list, possibly
87 87 * removing threads along the way. This design allows all three
88 88 * operations to be performed efficiently and easily.
89 89 *
90 90 * To insert a thread, traverse the list looking for the sublist of
91 91 * the same priority as the thread (or one of a lower priority,
92 92 * meaning there are no other threads in the list of the same
93 93 * priority). This can be done without touching all threads in the
94 94 * list by following the links between the first threads in each
95 95 * sublist. Given a thread t that is the head of a sublist (the first
96 96 * thread of that priority found when following the t_link pointers),
97 97 * t->t_priback->t_link points to the head of the next sublist. It's
98 98 * important to do this since a waitq may contain thousands of
99 99 * threads.
100 100 *
101 101 * Removing a thread from the list is also efficient. First, the
102 102 * t_waitq field contains a pointer to the waitq on which a thread
103 103 * is waiting (or NULL if it's not on a waitq). This is used to
104 104 * determine if the given thread is on the given waitq without
105 105 * searching the list. Assuming it is, if it's not the head of a
106 106 * sublist, just remove it from the sublist and use the t_priback
107 107 * pointer to find the thread that points to it with t_link. If it is
108 108 * the head of a sublist, search for it by walking the sublist heads,
109 109 * similar to searching for a given priority level when inserting a
110 110 * thread.
111 111 *
112 112 * To walk the list, simply follow the t_link pointers. Removing
113 113 * threads along the way can be done easily if the code maintains a
114 114 * pointer to the t_link field that pointed to the thread being
115 115 * removed.
116 116 */
117 117
118 118 static void
119 119 waitq_link(waitq_t *wq, kthread_t *t)
120 120 {
121 121 kthread_t *next_tp;
122 122 kthread_t *last_tp;
123 123 kthread_t **tpp;
124 124 pri_t tpri, next_pri, last_pri = -1;
125 125
126 126 ASSERT(DISP_LOCK_HELD(&wq->wq_lock));
127 127
128 128 tpri = DISP_PRIO(t);
129 129 tpp = &wq->wq_first;
130 130 while ((next_tp = *tpp) != NULL) {
131 131 next_pri = DISP_PRIO(next_tp);
132 132 if (tpri > next_pri)
133 133 break;
134 134 last_tp = next_tp->t_priback;
135 135 last_pri = next_pri;
136 136 tpp = &last_tp->t_link;
137 137 }
138 138 *tpp = t;
139 139 t->t_link = next_tp;
140 140 if (last_pri == tpri) {
141 141 /* last_tp points to the last thread of this priority */
142 142 t->t_priback = last_tp;
143 143 t->t_priforw = last_tp->t_priforw;
144 144 last_tp->t_priforw->t_priback = t;
145 145 last_tp->t_priforw = t;
146 146 } else {
147 147 t->t_priback = t->t_priforw = t;
148 148 }
149 149 wq->wq_count++;
150 150 t->t_waitq = wq;
151 151 }
152 152
153 153 static void
154 154 waitq_unlink(waitq_t *wq, kthread_t *t)
155 155 {
156 156 kthread_t *nt;
157 157 kthread_t **ptl;
158 158
159 159 ASSERT(THREAD_LOCK_HELD(t));
160 160 ASSERT(DISP_LOCK_HELD(&wq->wq_lock));
161 161 ASSERT(t->t_waitq == wq);
162 162
163 163 ptl = &t->t_priback->t_link;
164 164 /*
165 165 * Is it the head of a priority sublist? If so, need to walk
166 166 * the priorities to find the t_link pointer that points to it.
167 167 */
168 168 if (*ptl != t) {
169 169 /*
170 170 * Find the right priority level.
171 171 */
172 172 ptl = &t->t_waitq->wq_first;
173 173 while ((nt = *ptl) != t)
174 174 ptl = &nt->t_priback->t_link;
175 175 }
176 176 /*
177 177 * Remove thread from the t_link list.
178 178 */
179 179 *ptl = t->t_link;
180 180
181 181 /*
182 182 * Take it off the priority sublist if there's more than one
183 183 * thread there.
184 184 */
185 185 if (t->t_priforw != t) {
186 186 t->t_priback->t_priforw = t->t_priforw;
187 187 t->t_priforw->t_priback = t->t_priback;
188 188 }
189 189 t->t_link = NULL;
190 190
191 191 wq->wq_count--;
192 192 t->t_waitq = NULL;
193 193 t->t_priforw = NULL;
194 194 t->t_priback = NULL;
195 195 }
196 196
197 197 /*
198 198 * Put specified thread to specified wait queue without dropping thread's lock.
199 199 * Returns 1 if thread was successfully placed on project's wait queue, or
200 200 * 0 if wait queue is blocked.
201 201 */
202 202 int
203 203 waitq_enqueue(waitq_t *wq, kthread_t *t)
204 204 {
205 205 ASSERT(THREAD_LOCK_HELD(t));
206 206 ASSERT(t->t_sleepq == NULL);
207 207 ASSERT(t->t_waitq == NULL);
208 208 ASSERT(t->t_link == NULL);
209 209
210 210 disp_lock_enter_high(&wq->wq_lock);
211 211
212 212 /*
213 213 * Can't enqueue anything on a blocked wait queue
214 214 */
215 215 if (wq->wq_blocked) {
↓ open down ↓ |
215 lines elided |
↑ open up ↑ |
216 216 disp_lock_exit_high(&wq->wq_lock);
217 217 return (0);
218 218 }
219 219
220 220 /*
221 221 * Mark the time when thread is placed on wait queue. The microstate
222 222 * accounting code uses this timestamp to determine wait times.
223 223 */
224 224 t->t_waitrq = gethrtime_unscaled();
225 225
226 - /*
227 - * Mark thread as not swappable. If necessary, it will get
228 - * swapped out when it returns to the userland.
229 - */
230 - t->t_schedflag |= TS_DONT_SWAP;
231 226 DTRACE_SCHED1(cpucaps__sleep, kthread_t *, t);
232 227 waitq_link(wq, t);
233 228
234 229 THREAD_WAIT(t, &wq->wq_lock);
235 230 return (1);
236 231 }
237 232
238 233 /*
239 234 * Change thread's priority while on the wait queue.
240 235 * Dequeue and equeue it again so that it gets placed in the right place.
241 236 */
242 237 void
243 238 waitq_change_pri(kthread_t *t, pri_t new_pri)
244 239 {
245 240 waitq_t *wq = t->t_waitq;
246 241
247 242 ASSERT(THREAD_LOCK_HELD(t));
248 243 ASSERT(ISWAITING(t));
249 244 ASSERT(wq != NULL);
250 245
251 246 waitq_unlink(wq, t);
252 247 t->t_pri = new_pri;
253 248 waitq_link(wq, t);
254 249 }
255 250
256 251 static void
257 252 waitq_dequeue(waitq_t *wq, kthread_t *t)
258 253 {
259 254 ASSERT(THREAD_LOCK_HELD(t));
260 255 ASSERT(t->t_waitq == wq);
261 256 ASSERT(ISWAITING(t));
262 257
263 258 waitq_unlink(wq, t);
264 259 DTRACE_SCHED1(cpucaps__wakeup, kthread_t *, t);
265 260
266 261 /*
267 262 * Change thread to transition state and drop the wait queue lock. The
268 263 * thread will remain locked since its t_lockp points to the
269 264 * transition_lock.
270 265 */
271 266 THREAD_TRANSITION(t);
272 267 }
273 268
274 269 /*
275 270 * Return True iff there are any threads on the specified wait queue.
276 271 * The check is done **without holding any locks**.
277 272 */
278 273 boolean_t
279 274 waitq_isempty(waitq_t *wq)
280 275 {
281 276 return (wq->wq_count == 0);
282 277 }
283 278
284 279 /*
285 280 * Take thread off its wait queue and make it runnable.
286 281 * Returns with thread lock held.
287 282 */
288 283 void
289 284 waitq_setrun(kthread_t *t)
290 285 {
291 286 waitq_t *wq = t->t_waitq;
292 287
293 288 ASSERT(THREAD_LOCK_HELD(t));
294 289
295 290 ASSERT(ISWAITING(t));
296 291 if (wq == NULL)
297 292 panic("waitq_setrun: thread %p is not on waitq", (void *)t);
298 293 waitq_dequeue(wq, t);
299 294 CL_SETRUN(t);
300 295 }
301 296
302 297 /*
303 298 * Take the first thread off the wait queue and return pointer to it.
304 299 */
305 300 static kthread_t *
306 301 waitq_takeone(waitq_t *wq)
307 302 {
308 303 kthread_t *t;
309 304
310 305 disp_lock_enter(&wq->wq_lock);
311 306 /*
312 307 * waitq_dequeue drops wait queue lock but leaves the CPU at high PIL.
313 308 */
314 309 if ((t = wq->wq_first) != NULL)
315 310 waitq_dequeue(wq, wq->wq_first);
316 311 else
317 312 disp_lock_exit(&wq->wq_lock);
318 313 return (t);
319 314 }
320 315
321 316 /*
322 317 * Take the first thread off the wait queue and make it runnable.
323 318 * Return the pointer to the thread or NULL if waitq is empty
324 319 */
325 320 static kthread_t *
326 321 waitq_runfirst(waitq_t *wq)
327 322 {
328 323 kthread_t *t;
329 324
330 325 t = waitq_takeone(wq);
331 326 if (t != NULL) {
332 327 /*
333 328 * t should have transition lock held.
334 329 * CL_SETRUN() will replace it with dispq lock and keep it held.
335 330 * thread_unlock() will drop dispq lock and restore PIL.
336 331 */
337 332 ASSERT(THREAD_LOCK_HELD(t));
338 333 CL_SETRUN(t);
339 334 thread_unlock(t);
340 335 }
341 336 return (t);
342 337 }
343 338
344 339 /*
345 340 * Take the first thread off the wait queue and make it runnable.
346 341 */
347 342 void
348 343 waitq_runone(waitq_t *wq)
349 344 {
350 345 (void) waitq_runfirst(wq);
351 346 }
352 347
353 348 /*
354 349 * Take all threads off the wait queue and make them runnable.
355 350 */
356 351 static void
357 352 waitq_runall(waitq_t *wq)
358 353 {
359 354 while (waitq_runfirst(wq) != NULL)
360 355 ;
361 356 }
362 357
363 358 /*
364 359 * Prevent any new threads from entering wait queue and make all threads
365 360 * currently on the wait queue runnable. After waitq_block() completion, no
366 361 * threads should ever appear on the wait queue untill it is unblocked.
367 362 */
368 363 void
369 364 waitq_block(waitq_t *wq)
370 365 {
371 366 ASSERT(!wq->wq_blocked);
372 367 disp_lock_enter(&wq->wq_lock);
373 368 wq->wq_blocked = B_TRUE;
374 369 disp_lock_exit(&wq->wq_lock);
375 370 waitq_runall(wq);
376 371 ASSERT(waitq_isempty(wq));
377 372 }
378 373
379 374 /*
380 375 * Allow threads to be placed on the wait queue.
381 376 */
382 377 void
383 378 waitq_unblock(waitq_t *wq)
384 379 {
385 380 disp_lock_enter(&wq->wq_lock);
386 381
387 382 ASSERT(waitq_isempty(wq));
388 383 ASSERT(wq->wq_blocked);
389 384
390 385 wq->wq_blocked = B_FALSE;
391 386
392 387 disp_lock_exit(&wq->wq_lock);
393 388 }
↓ open down ↓ |
153 lines elided |
↑ open up ↑ |
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX