1 | /* $NetBSD: kern_condvar.c,v 1.35 2015/08/07 06:22:12 uebayasi 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.35 2015/08/07 06:22:12 uebayasi Exp $" ); |
38 | |
39 | #include <sys/param.h> |
40 | #include <sys/systm.h> |
41 | #include <sys/lwp.h> |
42 | #include <sys/condvar.h> |
43 | #include <sys/sleepq.h> |
44 | #include <sys/lockdebug.h> |
45 | #include <sys/cpu.h> |
46 | |
47 | /* |
48 | * Accessors for the private contents of the kcondvar_t data type. |
49 | * |
50 | * cv_opaque[0] sleepq... |
51 | * cv_opaque[1] ...pointers |
52 | * cv_opaque[2] description for ps(1) |
53 | * |
54 | * cv_opaque[0..1] is protected by the interlock passed to cv_wait() (enqueue |
55 | * only), and the sleep queue lock acquired with sleeptab_lookup() (enqueue |
56 | * and dequeue). |
57 | * |
58 | * cv_opaque[2] (the wmesg) is static and does not change throughout the life |
59 | * of the CV. |
60 | */ |
61 | #define CV_SLEEPQ(cv) ((sleepq_t *)(cv)->cv_opaque) |
62 | #define CV_WMESG(cv) ((const char *)(cv)->cv_opaque[2]) |
63 | #define CV_SET_WMESG(cv, v) (cv)->cv_opaque[2] = __UNCONST(v) |
64 | |
65 | #define CV_DEBUG_P(cv) (CV_WMESG(cv) != nodebug) |
66 | #define CV_RA ((uintptr_t)__builtin_return_address(0)) |
67 | |
68 | static void cv_unsleep(lwp_t *, bool); |
69 | static void cv_wakeup_one(kcondvar_t *); |
70 | static void cv_wakeup_all(kcondvar_t *); |
71 | |
72 | static syncobj_t cv_syncobj = { |
73 | SOBJ_SLEEPQ_SORTED, |
74 | cv_unsleep, |
75 | sleepq_changepri, |
76 | sleepq_lendpri, |
77 | syncobj_noowner, |
78 | }; |
79 | |
80 | lockops_t cv_lockops = { |
81 | "Condition variable" , |
82 | LOCKOPS_CV, |
83 | NULL |
84 | }; |
85 | |
86 | static const char deadcv[] = "deadcv" ; |
87 | #ifdef LOCKDEBUG |
88 | static const char nodebug[] = "nodebug" ; |
89 | #endif |
90 | |
91 | /* |
92 | * cv_init: |
93 | * |
94 | * Initialize a condition variable for use. |
95 | */ |
96 | void |
97 | cv_init(kcondvar_t *cv, const char *wmesg) |
98 | { |
99 | #ifdef LOCKDEBUG |
100 | bool dodebug; |
101 | |
102 | dodebug = LOCKDEBUG_ALLOC(cv, &cv_lockops, |
103 | (uintptr_t)__builtin_return_address(0)); |
104 | if (!dodebug) { |
105 | /* XXX This will break vfs_lockf. */ |
106 | wmesg = nodebug; |
107 | } |
108 | #endif |
109 | KASSERT(wmesg != NULL); |
110 | CV_SET_WMESG(cv, wmesg); |
111 | sleepq_init(CV_SLEEPQ(cv)); |
112 | } |
113 | |
114 | /* |
115 | * cv_destroy: |
116 | * |
117 | * Tear down a condition variable. |
118 | */ |
119 | void |
120 | cv_destroy(kcondvar_t *cv) |
121 | { |
122 | |
123 | LOCKDEBUG_FREE(CV_DEBUG_P(cv), cv); |
124 | #ifdef DIAGNOSTIC |
125 | KASSERT(cv_is_valid(cv)); |
126 | CV_SET_WMESG(cv, deadcv); |
127 | #endif |
128 | } |
129 | |
130 | /* |
131 | * cv_enter: |
132 | * |
133 | * Look up and lock the sleep queue corresponding to the given |
134 | * condition variable, and increment the number of waiters. |
135 | */ |
136 | static inline void |
137 | cv_enter(kcondvar_t *cv, kmutex_t *mtx, lwp_t *l) |
138 | { |
139 | sleepq_t *sq; |
140 | kmutex_t *mp; |
141 | |
142 | KASSERT(cv_is_valid(cv)); |
143 | KASSERT(!cpu_intr_p()); |
144 | KASSERT((l->l_pflag & LP_INTR) == 0 || panicstr != NULL); |
145 | |
146 | LOCKDEBUG_LOCKED(CV_DEBUG_P(cv), cv, mtx, CV_RA, 0); |
147 | |
148 | l->l_kpriority = true; |
149 | mp = sleepq_hashlock(cv); |
150 | sq = CV_SLEEPQ(cv); |
151 | sleepq_enter(sq, l, mp); |
152 | sleepq_enqueue(sq, cv, CV_WMESG(cv), &cv_syncobj); |
153 | mutex_exit(mtx); |
154 | KASSERT(cv_has_waiters(cv)); |
155 | } |
156 | |
157 | /* |
158 | * cv_exit: |
159 | * |
160 | * After resuming execution, check to see if we have been restarted |
161 | * as a result of cv_signal(). If we have, but cannot take the |
162 | * wakeup (because of eg a pending Unix signal or timeout) then try |
163 | * to ensure that another LWP sees it. This is necessary because |
164 | * there may be multiple waiters, and at least one should take the |
165 | * wakeup if possible. |
166 | */ |
167 | static inline int |
168 | cv_exit(kcondvar_t *cv, kmutex_t *mtx, lwp_t *l, const int error) |
169 | { |
170 | |
171 | mutex_enter(mtx); |
172 | if (__predict_false(error != 0)) |
173 | cv_signal(cv); |
174 | |
175 | LOCKDEBUG_UNLOCKED(CV_DEBUG_P(cv), cv, CV_RA, 0); |
176 | KASSERT(cv_is_valid(cv)); |
177 | |
178 | return error; |
179 | } |
180 | |
181 | /* |
182 | * cv_unsleep: |
183 | * |
184 | * Remove an LWP from the condition variable and sleep queue. This |
185 | * is called when the LWP has not been awoken normally but instead |
186 | * interrupted: for example, when a signal is received. Must be |
187 | * called with the LWP locked, and must return it unlocked. |
188 | */ |
189 | static void |
190 | cv_unsleep(lwp_t *l, bool cleanup) |
191 | { |
192 | kcondvar_t *cv __diagused; |
193 | |
194 | cv = (kcondvar_t *)(uintptr_t)l->l_wchan; |
195 | |
196 | KASSERT(l->l_wchan == (wchan_t)cv); |
197 | KASSERT(l->l_sleepq == CV_SLEEPQ(cv)); |
198 | KASSERT(cv_is_valid(cv)); |
199 | KASSERT(cv_has_waiters(cv)); |
200 | |
201 | sleepq_unsleep(l, cleanup); |
202 | } |
203 | |
204 | /* |
205 | * cv_wait: |
206 | * |
207 | * Wait non-interruptably on a condition variable until awoken. |
208 | */ |
209 | void |
210 | cv_wait(kcondvar_t *cv, kmutex_t *mtx) |
211 | { |
212 | lwp_t *l = curlwp; |
213 | |
214 | KASSERT(mutex_owned(mtx)); |
215 | |
216 | cv_enter(cv, mtx, l); |
217 | (void)sleepq_block(0, false); |
218 | (void)cv_exit(cv, mtx, l, 0); |
219 | } |
220 | |
221 | /* |
222 | * cv_wait_sig: |
223 | * |
224 | * Wait on a condition variable until a awoken or a signal is received. |
225 | * Will also return early if the process is exiting. Returns zero if |
226 | * awoken normally, ERESTART if a signal was received and the system |
227 | * call is restartable, or EINTR otherwise. |
228 | */ |
229 | int |
230 | cv_wait_sig(kcondvar_t *cv, kmutex_t *mtx) |
231 | { |
232 | lwp_t *l = curlwp; |
233 | int error; |
234 | |
235 | KASSERT(mutex_owned(mtx)); |
236 | |
237 | cv_enter(cv, mtx, l); |
238 | error = sleepq_block(0, true); |
239 | return cv_exit(cv, mtx, l, error); |
240 | } |
241 | |
242 | /* |
243 | * cv_timedwait: |
244 | * |
245 | * Wait on a condition variable until awoken or the specified timeout |
246 | * expires. Returns zero if awoken normally or EWOULDBLOCK if the |
247 | * timeout expired. |
248 | * |
249 | * timo is a timeout in ticks. timo = 0 specifies an infinite timeout. |
250 | */ |
251 | int |
252 | cv_timedwait(kcondvar_t *cv, kmutex_t *mtx, int timo) |
253 | { |
254 | lwp_t *l = curlwp; |
255 | int error; |
256 | |
257 | KASSERT(mutex_owned(mtx)); |
258 | |
259 | cv_enter(cv, mtx, l); |
260 | error = sleepq_block(timo, false); |
261 | return cv_exit(cv, mtx, l, error); |
262 | } |
263 | |
264 | /* |
265 | * cv_timedwait_sig: |
266 | * |
267 | * Wait on a condition variable until a timeout expires, awoken or a |
268 | * signal is received. Will also return early if the process is |
269 | * exiting. Returns zero if awoken normally, EWOULDBLOCK if the |
270 | * timeout expires, ERESTART if a signal was received and the system |
271 | * call is restartable, or EINTR otherwise. |
272 | * |
273 | * timo is a timeout in ticks. timo = 0 specifies an infinite timeout. |
274 | */ |
275 | int |
276 | cv_timedwait_sig(kcondvar_t *cv, kmutex_t *mtx, int timo) |
277 | { |
278 | lwp_t *l = curlwp; |
279 | int error; |
280 | |
281 | KASSERT(mutex_owned(mtx)); |
282 | |
283 | cv_enter(cv, mtx, l); |
284 | error = sleepq_block(timo, true); |
285 | return cv_exit(cv, mtx, l, error); |
286 | } |
287 | |
288 | /* |
289 | * cv_signal: |
290 | * |
291 | * Wake the highest priority LWP waiting on a condition variable. |
292 | * Must be called with the interlocking mutex held. |
293 | */ |
294 | void |
295 | cv_signal(kcondvar_t *cv) |
296 | { |
297 | |
298 | /* LOCKDEBUG_WAKEUP(CV_DEBUG_P(cv), cv, CV_RA); */ |
299 | KASSERT(cv_is_valid(cv)); |
300 | |
301 | if (__predict_false(!TAILQ_EMPTY(CV_SLEEPQ(cv)))) |
302 | cv_wakeup_one(cv); |
303 | } |
304 | |
305 | static void __noinline |
306 | cv_wakeup_one(kcondvar_t *cv) |
307 | { |
308 | sleepq_t *sq; |
309 | kmutex_t *mp; |
310 | lwp_t *l; |
311 | |
312 | KASSERT(cv_is_valid(cv)); |
313 | |
314 | mp = sleepq_hashlock(cv); |
315 | sq = CV_SLEEPQ(cv); |
316 | l = TAILQ_FIRST(sq); |
317 | if (l == NULL) { |
318 | mutex_spin_exit(mp); |
319 | return; |
320 | } |
321 | KASSERT(l->l_sleepq == sq); |
322 | KASSERT(l->l_mutex == mp); |
323 | KASSERT(l->l_wchan == cv); |
324 | sleepq_remove(sq, l); |
325 | mutex_spin_exit(mp); |
326 | |
327 | KASSERT(cv_is_valid(cv)); |
328 | } |
329 | |
330 | /* |
331 | * cv_broadcast: |
332 | * |
333 | * Wake all LWPs waiting on a condition variable. Must be called |
334 | * with the interlocking mutex held. |
335 | */ |
336 | void |
337 | cv_broadcast(kcondvar_t *cv) |
338 | { |
339 | |
340 | /* LOCKDEBUG_WAKEUP(CV_DEBUG_P(cv), cv, CV_RA); */ |
341 | KASSERT(cv_is_valid(cv)); |
342 | |
343 | if (__predict_false(!TAILQ_EMPTY(CV_SLEEPQ(cv)))) |
344 | cv_wakeup_all(cv); |
345 | } |
346 | |
347 | static void __noinline |
348 | cv_wakeup_all(kcondvar_t *cv) |
349 | { |
350 | sleepq_t *sq; |
351 | kmutex_t *mp; |
352 | lwp_t *l, *next; |
353 | |
354 | KASSERT(cv_is_valid(cv)); |
355 | |
356 | mp = sleepq_hashlock(cv); |
357 | sq = CV_SLEEPQ(cv); |
358 | for (l = TAILQ_FIRST(sq); l != NULL; l = next) { |
359 | KASSERT(l->l_sleepq == sq); |
360 | KASSERT(l->l_mutex == mp); |
361 | KASSERT(l->l_wchan == cv); |
362 | next = TAILQ_NEXT(l, l_sleepchain); |
363 | sleepq_remove(sq, l); |
364 | } |
365 | mutex_spin_exit(mp); |
366 | |
367 | KASSERT(cv_is_valid(cv)); |
368 | } |
369 | |
370 | /* |
371 | * cv_has_waiters: |
372 | * |
373 | * For diagnostic assertions: return non-zero if a condition |
374 | * variable has waiters. |
375 | */ |
376 | bool |
377 | cv_has_waiters(kcondvar_t *cv) |
378 | { |
379 | |
380 | return !TAILQ_EMPTY(CV_SLEEPQ(cv)); |
381 | } |
382 | |
383 | /* |
384 | * cv_is_valid: |
385 | * |
386 | * For diagnostic assertions: return non-zero if a condition |
387 | * variable appears to be valid. No locks need be held. |
388 | */ |
389 | bool |
390 | cv_is_valid(kcondvar_t *cv) |
391 | { |
392 | |
393 | return CV_WMESG(cv) != deadcv && CV_WMESG(cv) != NULL; |
394 | } |
395 | |