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