1 /* $NetBSD: kern_condvar.c,v 1.25 2008/06/16 12:03:01 ad Exp $ */
2
3 /*-
4 * Copyright (c) 2006, 2007, 2008 The NetBSD Foundation, Inc.
5 * All rights reserved.
6 *
7 * This code is derived from software contributed to The NetBSD Foundation
8 * by Andrew Doran.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
23 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29 * POSSIBILITY OF SUCH DAMAGE.
30 */
31
32 /*
33 * Kernel condition variable implementation.
34 */
35
36 #include <sys/cdefs.h>
37 __KERNEL_RCSID(0, "$NetBSD: kern_condvar.c,v 1.25 2008/06/16 12:03:01 ad Exp $");
38
39 #include <sys/param.h>
40 #include <sys/proc.h>
41 #include <sys/sched.h>
42 #include <sys/systm.h>
43 #include <sys/condvar.h>
44 #include <sys/sleepq.h>
45 #include <sys/lockdebug.h>
46 #include <sys/cpu.h>
47
48 #include <uvm/uvm_extern.h>
49
50 #define CV_SLEEPQ(cv) ((sleepq_t *)(cv)->cv_opaque)
51 #define CV_DEBUG_P(cv) ((cv)->cv_wmesg != nodebug)
52 #define CV_RA ((uintptr_t)__builtin_return_address(0))
53
54 static u_int cv_unsleep(lwp_t *, bool);
55 static void cv_wakeup_one(kcondvar_t *);
56 static void cv_wakeup_all(kcondvar_t *);
57
58 static syncobj_t cv_syncobj = {
59 SOBJ_SLEEPQ_SORTED,
60 cv_unsleep,
61 sleepq_changepri,
62 sleepq_lendpri,
63 syncobj_noowner,
64 };
65
66 lockops_t cv_lockops = {
67 "Condition variable",
68 LOCKOPS_CV,
69 NULL
70 };
71
72 static const char deadcv[] = "deadcv";
73 static const char nodebug[] = "nodebug";
74
75 /*
76 * cv_init:
77 *
78 * Initialize a condition variable for use.
79 */
80 void
81 cv_init(kcondvar_t *cv, const char *wmesg)
82 {
83 #ifdef LOCKDEBUG
84 bool dodebug;
85
86 dodebug = LOCKDEBUG_ALLOC(cv, &cv_lockops,
87 (uintptr_t)__builtin_return_address(0));
88 if (!dodebug) {
89 /* XXX This will break vfs_lockf. */
90 wmesg = nodebug;
91 }
92 #endif
93 KASSERT(wmesg != NULL);
94 cv->cv_wmesg = wmesg;
95 sleepq_init(CV_SLEEPQ(cv));
96 }
97
98 /*
99 * cv_destroy:
100 *
101 * Tear down a condition variable.
102 */
103 void
104 cv_destroy(kcondvar_t *cv)
105 {
106
107 LOCKDEBUG_FREE(CV_DEBUG_P(cv), cv);
108 #ifdef DIAGNOSTIC
109 KASSERT(cv_is_valid(cv));
110 cv->cv_wmesg = deadcv;
111 #endif
112 }
113
114 /*
115 * cv_enter:
116 *
117 * Look up and lock the sleep queue corresponding to the given
118 * condition variable, and increment the number of waiters.
119 */
120 static inline void
121 cv_enter(kcondvar_t *cv, kmutex_t *mtx, lwp_t *l)
122 {
123 sleepq_t *sq;
124 kmutex_t *mp;
125
126 KASSERT(cv_is_valid(cv));
127 KASSERT(!cpu_intr_p());
128 KASSERT((l->l_pflag & LP_INTR) == 0 || panicstr != NULL);
129
130 LOCKDEBUG_LOCKED(CV_DEBUG_P(cv), cv, mtx, CV_RA, 0);
131
132 l->l_kpriority = true;
133 mp = sleepq_hashlock(cv);
134 sq = CV_SLEEPQ(cv);
135 sleepq_enter(sq, l, mp);
136 sleepq_enqueue(sq, cv, cv->cv_wmesg, &cv_syncobj);
137 mutex_exit(mtx);
138 KASSERT(cv_has_waiters(cv));
139 }
140
141 /*
142 * cv_exit:
143 *
144 * After resuming execution, check to see if we have been restarted
145 * as a result of cv_signal(). If we have, but cannot take the
146 * wakeup (because of eg a pending Unix signal or timeout) then try
147 * to ensure that another LWP sees it. This is necessary because
148 * there may be multiple waiters, and at least one should take the
149 * wakeup if possible.
150 */
151 static inline int
152 cv_exit(kcondvar_t *cv, kmutex_t *mtx, lwp_t *l, const int error)
153 {
154
155 mutex_enter(mtx);
156 if (__predict_false(error != 0))
157 cv_signal(cv);
158
159 LOCKDEBUG_UNLOCKED(CV_DEBUG_P(cv), cv, CV_RA, 0);
160 KASSERT(cv_is_valid(cv));
161
162 return error;
163 }
164
165 /*
166 * cv_unsleep:
167 *
168 * Remove an LWP from the condition variable and sleep queue. This
169 * is called when the LWP has not been awoken normally but instead
170 * interrupted: for example, when a signal is received. Must be
171 * called with the LWP locked, and must return it unlocked.
172 */
173 static u_int
174 cv_unsleep(lwp_t *l, bool cleanup)
175 {
176 kcondvar_t *cv;
177
178 cv = (kcondvar_t *)(uintptr_t)l->l_wchan;
179
180 KASSERT(l->l_wchan == (wchan_t)cv);
181 KASSERT(l->l_sleepq == CV_SLEEPQ(cv));
182 KASSERT(cv_is_valid(cv));
183 KASSERT(cv_has_waiters(cv));
184
185 return sleepq_unsleep(l, cleanup);
186 }
187
188 /*
189 * cv_wait:
190 *
191 * Wait non-interruptably on a condition variable until awoken.
192 */
193 void
194 cv_wait(kcondvar_t *cv, kmutex_t *mtx)
195 {
196 lwp_t *l = curlwp;
197
198 KASSERT(mutex_owned(mtx));
199
200 cv_enter(cv, mtx, l);
201 (void)sleepq_block(0, false);
202 (void)cv_exit(cv, mtx, l, 0);
203 }
204
205 /*
206 * cv_wait_sig:
207 *
208 * Wait on a condition variable until a awoken or a signal is received.
209 * Will also return early if the process is exiting. Returns zero if
210 * awoken normallly, ERESTART if a signal was received and the system
211 * call is restartable, or EINTR otherwise.
212 */
213 int
214 cv_wait_sig(kcondvar_t *cv, kmutex_t *mtx)
215 {
216 lwp_t *l = curlwp;
217 int error;
218
219 KASSERT(mutex_owned(mtx));
220
221 cv_enter(cv, mtx, l);
222 error = sleepq_block(0, true);
223 return cv_exit(cv, mtx, l, error);
224 }
225
226 /*
227 * cv_timedwait:
228 *
229 * Wait on a condition variable until awoken or the specified timeout
230 * expires. Returns zero if awoken normally or EWOULDBLOCK if the
231 * timeout expired.
232 */
233 int
234 cv_timedwait(kcondvar_t *cv, kmutex_t *mtx, int timo)
235 {
236 lwp_t *l = curlwp;
237 int error;
238
239 KASSERT(mutex_owned(mtx));
240
241 cv_enter(cv, mtx, l);
242 error = sleepq_block(timo, false);
243 return cv_exit(cv, mtx, l, error);
244 }
245
246 /*
247 * cv_timedwait_sig:
248 *
249 * Wait on a condition variable until a timeout expires, awoken or a
250 * signal is received. Will also return early if the process is
251 * exiting. Returns zero if awoken normallly, EWOULDBLOCK if the
252 * timeout expires, ERESTART if a signal was received and the system
253 * call is restartable, or EINTR otherwise.
254 */
255 int
256 cv_timedwait_sig(kcondvar_t *cv, kmutex_t *mtx, int timo)
257 {
258 lwp_t *l = curlwp;
259 int error;
260
261 KASSERT(mutex_owned(mtx));
262
263 cv_enter(cv, mtx, l);
264 error = sleepq_block(timo, true);
265 return cv_exit(cv, mtx, l, error);
266 }
267
268 /*
269 * cv_signal:
270 *
271 * Wake the highest priority LWP waiting on a condition variable.
272 * Must be called with the interlocking mutex held.
273 */
274 void
275 cv_signal(kcondvar_t *cv)
276 {
277
278 /* LOCKDEBUG_WAKEUP(CV_DEBUG_P(cv), cv, CV_RA); */
279 KASSERT(cv_is_valid(cv));
280
281 if (__predict_false(!TAILQ_EMPTY(CV_SLEEPQ(cv))))
282 cv_wakeup_one(cv);
283 }
284
285 static void __noinline
286 cv_wakeup_one(kcondvar_t *cv)
287 {
288 sleepq_t *sq;
289 kmutex_t *mp;
290 int swapin;
291 lwp_t *l;
292
293 KASSERT(cv_is_valid(cv));
294
295 mp = sleepq_hashlock(cv);
296 sq = CV_SLEEPQ(cv);
297 l = TAILQ_FIRST(sq);
298 if (l == NULL) {
299 mutex_spin_exit(mp);
300 return;
301 }
302 KASSERT(l->l_sleepq == sq);
303 KASSERT(l->l_mutex == mp);
304 KASSERT(l->l_wchan == cv);
305 swapin = sleepq_remove(sq, l);
306 mutex_spin_exit(mp);
307
308 /*
309 * If there are newly awakend threads that need to be swapped in,
310 * then kick the swapper into action.
311 */
312 if (swapin)
313 uvm_kick_scheduler();
314
315 KASSERT(cv_is_valid(cv));
316 }
317
318 /*
319 * cv_broadcast:
320 *
321 * Wake all LWPs waiting on a condition variable. Must be called
322 * with the interlocking mutex held.
323 */
324 void
325 cv_broadcast(kcondvar_t *cv)
326 {
327
328 /* LOCKDEBUG_WAKEUP(CV_DEBUG_P(cv), cv, CV_RA); */
329 KASSERT(cv_is_valid(cv));
330
331 if (__predict_false(!TAILQ_EMPTY(CV_SLEEPQ(cv))))
332 cv_wakeup_all(cv);
333 }
334
335 static void __noinline
336 cv_wakeup_all(kcondvar_t *cv)
337 {
338 sleepq_t *sq;
339 kmutex_t *mp;
340 int swapin;
341 lwp_t *l, *next;
342
343 KASSERT(cv_is_valid(cv));
344
345 mp = sleepq_hashlock(cv);
346 swapin = 0;
347 sq = CV_SLEEPQ(cv);
348 for (l = TAILQ_FIRST(sq); l != NULL; l = next) {
349 KASSERT(l->l_sleepq == sq);
350 KASSERT(l->l_mutex == mp);
351 KASSERT(l->l_wchan == cv);
352 next = TAILQ_NEXT(l, l_sleepchain);
353 swapin |= sleepq_remove(sq, l);
354 }
355 mutex_spin_exit(mp);
356
357 /*
358 * If there are newly awakend threads that need to be swapped in,
359 * then kick the swapper into action.
360 */
361 if (swapin)
362 uvm_kick_scheduler();
363
364 KASSERT(cv_is_valid(cv));
365 }
366
367 /*
368 * cv_wakeup:
369 *
370 * Wake all LWPs waiting on a condition variable. For cases
371 * where the address may be waited on by mtsleep()/tsleep().
372 * Not a documented call.
373 */
374 void
375 cv_wakeup(kcondvar_t *cv)
376 {
377
378 cv_wakeup_all(cv);
379 wakeup(cv);
380 }
381
382 /*
383 * cv_has_waiters:
384 *
385 * For diagnostic assertions: return non-zero if a condition
386 * variable has waiters.
387 */
388 bool
389 cv_has_waiters(kcondvar_t *cv)
390 {
391
392 return !TAILQ_EMPTY(CV_SLEEPQ(cv));
393 }
394
395 /*
396 * cv_is_valid:
397 *
398 * For diagnostic assertions: return non-zero if a condition
399 * variable appears to be valid. No locks need be held.
400 */
401 bool
402 cv_is_valid(kcondvar_t *cv)
403 {
404
405 return cv->cv_wmesg != deadcv && cv->cv_wmesg != NULL;
406 }
Cache object: abb2881af8717a25e87a5b07c80bc1bc
|