1 /* $NetBSD: kern_condvar.c,v 1.19 2008/05/26 12:58:24 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, modeled after those found in 34 * Solaris, a description of which can be found in: 35 * 36 * Solaris Internals: Core Kernel Architecture, Jim Mauro and 37 * Richard McDougall. 38 */ 39 40 #include <sys/cdefs.h> 41 __KERNEL_RCSID(0, "$NetBSD: kern_condvar.c,v 1.19 2008/05/26 12:58:24 ad Exp $"); 42 43 #include <sys/param.h> 44 #include <sys/proc.h> 45 #include <sys/sched.h> 46 #include <sys/systm.h> 47 #include <sys/condvar.h> 48 #include <sys/sleepq.h> 49 50 static u_int cv_unsleep(lwp_t *, bool); 51 52 static syncobj_t cv_syncobj = { 53 SOBJ_SLEEPQ_SORTED, 54 cv_unsleep, 55 sleepq_changepri, 56 sleepq_lendpri, 57 syncobj_noowner, 58 }; 59 60 static const char deadcv[] = "deadcv"; 61 62 /* 63 * cv_init: 64 * 65 * Initialize a condition variable for use. 66 */ 67 void 68 cv_init(kcondvar_t *cv, const char *wmesg) 69 { 70 71 KASSERT(wmesg != NULL); 72 73 cv->cv_wmesg = wmesg; 74 cv->cv_waiters = 0; 75 } 76 77 /* 78 * cv_destroy: 79 * 80 * Tear down a condition variable. 81 */ 82 void 83 cv_destroy(kcondvar_t *cv) 84 { 85 86 #ifdef DIAGNOSTIC 87 KASSERT(cv_is_valid(cv)); 88 cv->cv_wmesg = deadcv; 89 cv->cv_waiters = -3; 90 #endif 91 } 92 93 /* 94 * cv_enter: 95 * 96 * Look up and lock the sleep queue corresponding to the given 97 * condition variable, and increment the number of waiters. 98 */ 99 static inline sleepq_t * 100 cv_enter(kcondvar_t *cv, kmutex_t *mtx, lwp_t *l) 101 { 102 sleepq_t *sq; 103 kmutex_t *mp; 104 105 KASSERT(cv_is_valid(cv)); 106 KASSERT((l->l_pflag & LP_INTR) == 0 || panicstr != NULL); 107 108 l->l_cv_signalled = 0; 109 l->l_kpriority = true; 110 sq = sleeptab_lookup(&sleeptab, cv, &mp); 111 cv->cv_waiters++; 112 sleepq_enter(sq, l, mp); 113 sleepq_enqueue(sq, cv, cv->cv_wmesg, &cv_syncobj); 114 mutex_exit(mtx); 115 116 return sq; 117 } 118 119 /* 120 * cv_exit: 121 * 122 * After resuming execution, check to see if we have been restarted 123 * as a result of cv_signal(). If we have, but cannot take the 124 * wakeup (because of eg a pending Unix signal or timeout) then try 125 * to ensure that another LWP sees it. This is necessary because 126 * there may be multiple waiters, and at least one should take the 127 * wakeup if possible. 128 */ 129 static inline int 130 cv_exit(kcondvar_t *cv, kmutex_t *mtx, lwp_t *l, const int error) 131 { 132 133 mutex_enter(mtx); 134 if (__predict_false(error != 0) && l->l_cv_signalled != 0) 135 cv_signal(cv); 136 137 KASSERT(cv_is_valid(cv)); 138 139 return error; 140 } 141 142 /* 143 * cv_unsleep: 144 * 145 * Remove an LWP from the condition variable and sleep queue. This 146 * is called when the LWP has not been awoken normally but instead 147 * interrupted: for example, when a signal is received. Must be 148 * called with the LWP locked, and must return it unlocked. 149 */ 150 static u_int 151 cv_unsleep(lwp_t *l, bool cleanup) 152 { 153 kcondvar_t *cv; 154 155 cv = (kcondvar_t *)(uintptr_t)l->l_wchan; 156 157 KASSERT(l->l_wchan != NULL); 158 KASSERT(lwp_locked(l, NULL)); 159 KASSERT(cv_is_valid(cv)); 160 KASSERT(cv->cv_waiters > 0); 161 162 cv->cv_waiters--; 163 return sleepq_unsleep(l, cleanup); 164 } 165 166 /* 167 * cv_wait: 168 * 169 * Wait non-interruptably on a condition variable until awoken. 170 */ 171 void 172 cv_wait(kcondvar_t *cv, kmutex_t *mtx) 173 { 174 lwp_t *l = curlwp; 175 sleepq_t *sq; 176 177 KASSERT(mutex_owned(mtx)); 178 179 if (sleepq_dontsleep(l)) { 180 (void)sleepq_abort(mtx, 0); 181 return; 182 } 183 184 sq = cv_enter(cv, mtx, l); 185 (void)sleepq_block(0, false); 186 (void)cv_exit(cv, mtx, l, 0); 187 } 188 189 /* 190 * cv_wait_sig: 191 * 192 * Wait on a condition variable until a awoken or a signal is received. 193 * Will also return early if the process is exiting. Returns zero if 194 * awoken normallly, ERESTART if a signal was received and the system 195 * call is restartable, or EINTR otherwise. 196 */ 197 int 198 cv_wait_sig(kcondvar_t *cv, kmutex_t *mtx) 199 { 200 lwp_t *l = curlwp; 201 sleepq_t *sq; 202 int error; 203 204 KASSERT(mutex_owned(mtx)); 205 206 if (sleepq_dontsleep(l)) 207 return sleepq_abort(mtx, 0); 208 209 sq = cv_enter(cv, mtx, l); 210 error = sleepq_block(0, true); 211 return cv_exit(cv, mtx, l, error); 212 } 213 214 /* 215 * cv_timedwait: 216 * 217 * Wait on a condition variable until awoken or the specified timeout 218 * expires. Returns zero if awoken normally or EWOULDBLOCK if the 219 * timeout expired. 220 */ 221 int 222 cv_timedwait(kcondvar_t *cv, kmutex_t *mtx, int timo) 223 { 224 lwp_t *l = curlwp; 225 sleepq_t *sq; 226 int error; 227 228 KASSERT(mutex_owned(mtx)); 229 230 if (sleepq_dontsleep(l)) 231 return sleepq_abort(mtx, 0); 232 233 sq = cv_enter(cv, mtx, l); 234 error = sleepq_block(timo, false); 235 return cv_exit(cv, mtx, l, error); 236 } 237 238 /* 239 * cv_timedwait_sig: 240 * 241 * Wait on a condition variable until a timeout expires, awoken or a 242 * signal is received. Will also return early if the process is 243 * exiting. Returns zero if awoken normallly, EWOULDBLOCK if the 244 * timeout expires, ERESTART if a signal was received and the system 245 * call is restartable, or EINTR otherwise. 246 */ 247 int 248 cv_timedwait_sig(kcondvar_t *cv, kmutex_t *mtx, int timo) 249 { 250 lwp_t *l = curlwp; 251 sleepq_t *sq; 252 int error; 253 254 KASSERT(mutex_owned(mtx)); 255 256 if (sleepq_dontsleep(l)) 257 return sleepq_abort(mtx, 0); 258 259 sq = cv_enter(cv, mtx, l); 260 error = sleepq_block(timo, true); 261 return cv_exit(cv, mtx, l, error); 262 } 263 264 /* 265 * cv_signal: 266 * 267 * Wake the highest priority LWP waiting on a condition variable. 268 * Must be called with the interlocking mutex held. 269 */ 270 void 271 cv_signal(kcondvar_t *cv) 272 { 273 lwp_t *l; 274 sleepq_t *sq; 275 kmutex_t *mp; 276 277 KASSERT(cv_is_valid(cv)); 278 279 if (cv->cv_waiters == 0) 280 return; 281 282 /* 283 * cv->cv_waiters may be stale and have dropped to zero, but 284 * while holding the interlock (the mutex passed to cv_wait() 285 * and similar) we will see non-zero values when it matters. 286 */ 287 288 sq = sleeptab_lookup(&sleeptab, cv, &mp); 289 if (cv->cv_waiters != 0) { 290 cv->cv_waiters--; 291 l = sleepq_wake(sq, cv, 1, mp); 292 l->l_cv_signalled = 1; 293 } else 294 mutex_spin_exit(mp); 295 296 KASSERT(cv_is_valid(cv)); 297 } 298 299 /* 300 * cv_broadcast: 301 * 302 * Wake all LWPs waiting on a condition variable. Must be called 303 * with the interlocking mutex held. 304 */ 305 void 306 cv_broadcast(kcondvar_t *cv) 307 { 308 sleepq_t *sq; 309 kmutex_t *mp; 310 u_int cnt; 311 312 KASSERT(cv_is_valid(cv)); 313 314 if (cv->cv_waiters == 0) 315 return; 316 317 sq = sleeptab_lookup(&sleeptab, cv, &mp); 318 if ((cnt = cv->cv_waiters) != 0) { 319 cv->cv_waiters = 0; 320 sleepq_wake(sq, cv, cnt, mp); 321 } else 322 mutex_spin_exit(mp); 323 324 KASSERT(cv_is_valid(cv)); 325 } 326 327 /* 328 * cv_wakeup: 329 * 330 * Wake all LWPs waiting on a condition variable. For cases 331 * where the address may be waited on by mtsleep()/tsleep(). 332 * Not a documented call. 333 */ 334 void 335 cv_wakeup(kcondvar_t *cv) 336 { 337 sleepq_t *sq; 338 kmutex_t *mp; 339 340 KASSERT(cv_is_valid(cv)); 341 342 sq = sleeptab_lookup(&sleeptab, cv, &mp); 343 cv->cv_waiters = 0; 344 sleepq_wake(sq, cv, (u_int)-1, mp); 345 346 KASSERT(cv_is_valid(cv)); 347 } 348 349 /* 350 * cv_has_waiters: 351 * 352 * For diagnostic assertions: return non-zero if a condition 353 * variable has waiters. 354 */ 355 bool 356 cv_has_waiters(kcondvar_t *cv) 357 { 358 359 /* No need to interlock here */ 360 return cv->cv_waiters != 0; 361 } 362 363 /* 364 * cv_is_valid: 365 * 366 * For diagnostic assertions: return non-zero if a condition 367 * variable appears to be valid. No locks need be held. 368 */ 369 bool 370 cv_is_valid(kcondvar_t *cv) 371 { 372 373 if (cv->cv_wmesg == deadcv || cv->cv_wmesg == NULL) 374 return false; 375 if ((cv->cv_waiters & 0xff000000) != 0) { 376 /* Arbitrary: invalid number of waiters. */ 377 return false; 378 } 379 return cv->cv_waiters >= 0; 380 } 381