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