1 /* $NetBSD: kern_condvar.c,v 1.28 2009/12/05 22:38:19 pooka 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.28 2009/12/05 22:38:19 pooka 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 /* 51 * Accessors for the private contents of the kcondvar_t data type. 52 * 53 * cv_opaque[0] sleepq... 54 * cv_opaque[1] ...pointers 55 * cv_opaque[2] description for ps(1) 56 * 57 * cv_opaque[0..1] is protected by the interlock passed to cv_wait() (enqueue 58 * only), and the sleep queue lock acquired with sleeptab_lookup() (enqueue 59 * and dequeue). 60 * 61 * cv_opaque[2] (the wmesg) is static and does not change throughout the life 62 * of the CV. 63 */ 64 #define CV_SLEEPQ(cv) ((sleepq_t *)(cv)->cv_opaque) 65 #define CV_WMESG(cv) ((const char *)(cv)->cv_opaque[2]) 66 #define CV_SET_WMESG(cv, v) (cv)->cv_opaque[2] = __UNCONST(v) 67 68 #define CV_DEBUG_P(cv) (CV_WMESG(cv) != nodebug) 69 #define CV_RA ((uintptr_t)__builtin_return_address(0)) 70 71 static void cv_unsleep(lwp_t *, bool); 72 static void cv_wakeup_one(kcondvar_t *); 73 static void cv_wakeup_all(kcondvar_t *); 74 75 static syncobj_t cv_syncobj = { 76 SOBJ_SLEEPQ_SORTED, 77 cv_unsleep, 78 sleepq_changepri, 79 sleepq_lendpri, 80 syncobj_noowner, 81 }; 82 83 lockops_t cv_lockops = { 84 "Condition variable", 85 LOCKOPS_CV, 86 NULL 87 }; 88 89 static const char deadcv[] = "deadcv"; 90 static const char nodebug[] = "nodebug"; 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; 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 normallly, 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 int 251 cv_timedwait(kcondvar_t *cv, kmutex_t *mtx, int timo) 252 { 253 lwp_t *l = curlwp; 254 int error; 255 256 KASSERT(mutex_owned(mtx)); 257 258 cv_enter(cv, mtx, l); 259 error = sleepq_block(timo, false); 260 return cv_exit(cv, mtx, l, error); 261 } 262 263 /* 264 * cv_timedwait_sig: 265 * 266 * Wait on a condition variable until a timeout expires, awoken or a 267 * signal is received. Will also return early if the process is 268 * exiting. Returns zero if awoken normallly, EWOULDBLOCK if the 269 * timeout expires, ERESTART if a signal was received and the system 270 * call is restartable, or EINTR otherwise. 271 */ 272 int 273 cv_timedwait_sig(kcondvar_t *cv, kmutex_t *mtx, int timo) 274 { 275 lwp_t *l = curlwp; 276 int error; 277 278 KASSERT(mutex_owned(mtx)); 279 280 cv_enter(cv, mtx, l); 281 error = sleepq_block(timo, true); 282 return cv_exit(cv, mtx, l, error); 283 } 284 285 /* 286 * cv_signal: 287 * 288 * Wake the highest priority LWP waiting on a condition variable. 289 * Must be called with the interlocking mutex held. 290 */ 291 void 292 cv_signal(kcondvar_t *cv) 293 { 294 295 /* LOCKDEBUG_WAKEUP(CV_DEBUG_P(cv), cv, CV_RA); */ 296 KASSERT(cv_is_valid(cv)); 297 298 if (__predict_false(!TAILQ_EMPTY(CV_SLEEPQ(cv)))) 299 cv_wakeup_one(cv); 300 } 301 302 static void __noinline 303 cv_wakeup_one(kcondvar_t *cv) 304 { 305 sleepq_t *sq; 306 kmutex_t *mp; 307 lwp_t *l; 308 309 KASSERT(cv_is_valid(cv)); 310 311 mp = sleepq_hashlock(cv); 312 sq = CV_SLEEPQ(cv); 313 l = TAILQ_FIRST(sq); 314 if (l == NULL) { 315 mutex_spin_exit(mp); 316 return; 317 } 318 KASSERT(l->l_sleepq == sq); 319 KASSERT(l->l_mutex == mp); 320 KASSERT(l->l_wchan == cv); 321 sleepq_remove(sq, l); 322 mutex_spin_exit(mp); 323 324 KASSERT(cv_is_valid(cv)); 325 } 326 327 /* 328 * cv_broadcast: 329 * 330 * Wake all LWPs waiting on a condition variable. Must be called 331 * with the interlocking mutex held. 332 */ 333 void 334 cv_broadcast(kcondvar_t *cv) 335 { 336 337 /* LOCKDEBUG_WAKEUP(CV_DEBUG_P(cv), cv, CV_RA); */ 338 KASSERT(cv_is_valid(cv)); 339 340 if (__predict_false(!TAILQ_EMPTY(CV_SLEEPQ(cv)))) 341 cv_wakeup_all(cv); 342 } 343 344 static void __noinline 345 cv_wakeup_all(kcondvar_t *cv) 346 { 347 sleepq_t *sq; 348 kmutex_t *mp; 349 lwp_t *l, *next; 350 351 KASSERT(cv_is_valid(cv)); 352 353 mp = sleepq_hashlock(cv); 354 sq = CV_SLEEPQ(cv); 355 for (l = TAILQ_FIRST(sq); l != NULL; l = next) { 356 KASSERT(l->l_sleepq == sq); 357 KASSERT(l->l_mutex == mp); 358 KASSERT(l->l_wchan == cv); 359 next = TAILQ_NEXT(l, l_sleepchain); 360 sleepq_remove(sq, l); 361 } 362 mutex_spin_exit(mp); 363 364 KASSERT(cv_is_valid(cv)); 365 } 366 367 /* 368 * cv_has_waiters: 369 * 370 * For diagnostic assertions: return non-zero if a condition 371 * variable has waiters. 372 */ 373 bool 374 cv_has_waiters(kcondvar_t *cv) 375 { 376 377 return !TAILQ_EMPTY(CV_SLEEPQ(cv)); 378 } 379 380 /* 381 * cv_is_valid: 382 * 383 * For diagnostic assertions: return non-zero if a condition 384 * variable appears to be valid. No locks need be held. 385 */ 386 bool 387 cv_is_valid(kcondvar_t *cv) 388 { 389 390 return CV_WMESG(cv) != deadcv && CV_WMESG(cv) != NULL; 391 } 392