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