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
43void
44waitq_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
52void
53waitq_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
118static void
119waitq_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
153static void
154waitq_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 */
202int
203waitq_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	/*
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	DTRACE_SCHED1(cpucaps__sleep, kthread_t *, t);
232	waitq_link(wq, t);
233
234	THREAD_WAIT(t, &wq->wq_lock);
235	return (1);
236}
237
238/*
239 * Change thread's priority while on the wait queue.
240 * Dequeue and equeue it again so that it gets placed in the right place.
241 */
242void
243waitq_change_pri(kthread_t *t, pri_t new_pri)
244{
245	waitq_t *wq = t->t_waitq;
246
247	ASSERT(THREAD_LOCK_HELD(t));
248	ASSERT(ISWAITING(t));
249	ASSERT(wq != NULL);
250
251	waitq_unlink(wq, t);
252	t->t_pri = new_pri;
253	waitq_link(wq, t);
254}
255
256static void
257waitq_dequeue(waitq_t *wq, kthread_t *t)
258{
259	ASSERT(THREAD_LOCK_HELD(t));
260	ASSERT(t->t_waitq == wq);
261	ASSERT(ISWAITING(t));
262
263	waitq_unlink(wq, t);
264	DTRACE_SCHED1(cpucaps__wakeup, kthread_t *, t);
265
266	/*
267	 * Change thread to transition state and drop the wait queue lock. The
268	 * thread will remain locked since its t_lockp points to the
269	 * transition_lock.
270	 */
271	THREAD_TRANSITION(t);
272}
273
274/*
275 * Return True iff there are any threads on the specified wait queue.
276 * The check is done **without holding any locks**.
277 */
278boolean_t
279waitq_isempty(waitq_t *wq)
280{
281	return (wq->wq_count == 0);
282}
283
284/*
285 * Take thread off its wait queue and make it runnable.
286 * Returns with thread lock held.
287 */
288void
289waitq_setrun(kthread_t *t)
290{
291	waitq_t *wq = t->t_waitq;
292
293	ASSERT(THREAD_LOCK_HELD(t));
294
295	ASSERT(ISWAITING(t));
296	if (wq == NULL)
297		panic("waitq_setrun: thread %p is not on waitq", (void *)t);
298	waitq_dequeue(wq, t);
299	CL_SETRUN(t);
300}
301
302/*
303 * Take the first thread off the wait queue and return pointer to it.
304 */
305static kthread_t *
306waitq_takeone(waitq_t *wq)
307{
308	kthread_t *t;
309
310	disp_lock_enter(&wq->wq_lock);
311	/*
312	 * waitq_dequeue drops wait queue lock but leaves the CPU at high PIL.
313	 */
314	if ((t = wq->wq_first) != NULL)
315		waitq_dequeue(wq, wq->wq_first);
316	else
317		disp_lock_exit(&wq->wq_lock);
318	return (t);
319}
320
321/*
322 * Take the first thread off the wait queue and make it runnable.
323 * Return the pointer to the thread or NULL if waitq is empty
324 */
325static kthread_t *
326waitq_runfirst(waitq_t *wq)
327{
328	kthread_t *t;
329
330	t = waitq_takeone(wq);
331	if (t != NULL) {
332		/*
333		 * t should have transition lock held.
334		 * CL_SETRUN() will replace it with dispq lock and keep it held.
335		 * thread_unlock() will drop dispq lock and restore PIL.
336		 */
337		ASSERT(THREAD_LOCK_HELD(t));
338		CL_SETRUN(t);
339		thread_unlock(t);
340	}
341	return (t);
342}
343
344/*
345 * Take the first thread off the wait queue and make it runnable.
346 */
347void
348waitq_runone(waitq_t *wq)
349{
350	(void) waitq_runfirst(wq);
351}
352
353/*
354 * Take all threads off the wait queue and make them runnable.
355 */
356static void
357waitq_runall(waitq_t *wq)
358{
359	while (waitq_runfirst(wq) != NULL)
360		;
361}
362
363/*
364 * Prevent any new threads from entering wait queue and make all threads
365 * currently on the wait queue runnable. After waitq_block() completion, no
366 * threads should ever appear on the wait queue untill it is unblocked.
367 */
368void
369waitq_block(waitq_t *wq)
370{
371	ASSERT(!wq->wq_blocked);
372	disp_lock_enter(&wq->wq_lock);
373	wq->wq_blocked = B_TRUE;
374	disp_lock_exit(&wq->wq_lock);
375	waitq_runall(wq);
376	ASSERT(waitq_isempty(wq));
377}
378
379/*
380 * Allow threads to be placed on the wait queue.
381 */
382void
383waitq_unblock(waitq_t *wq)
384{
385	disp_lock_enter(&wq->wq_lock);
386
387	ASSERT(waitq_isempty(wq));
388	ASSERT(wq->wq_blocked);
389
390	wq->wq_blocked = B_FALSE;
391
392	disp_lock_exit(&wq->wq_lock);
393}
394