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