1 /* $NetBSD: kern_condvar.c,v 1.17 2008/04/28 20:24:02 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, 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.17 2008/04/28 20:24:02 martin 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 104 KASSERT(cv_is_valid(cv)); 105 KASSERT((l->l_pflag & LP_INTR) == 0 || panicstr != NULL); 106 107 l->l_cv_signalled = 0; 108 l->l_kpriority = true; 109 sq = sleeptab_lookup(&sleeptab, cv); 110 cv->cv_waiters++; 111 sleepq_enter(sq, l); 112 sleepq_enqueue(sq, cv, cv->cv_wmesg, &cv_syncobj); 113 mutex_exit(mtx); 114 115 return sq; 116 } 117 118 /* 119 * cv_exit: 120 * 121 * After resuming execution, check to see if we have been restarted 122 * as a result of cv_signal(). If we have, but cannot take the 123 * wakeup (because of eg a pending Unix signal or timeout) then try 124 * to ensure that another LWP sees it. This is necessary because 125 * there may be multiple waiters, and at least one should take the 126 * wakeup if possible. 127 */ 128 static inline int 129 cv_exit(kcondvar_t *cv, kmutex_t *mtx, lwp_t *l, const int error) 130 { 131 132 mutex_enter(mtx); 133 if (__predict_false(error != 0) && l->l_cv_signalled != 0) 134 cv_signal(cv); 135 136 KASSERT(cv_is_valid(cv)); 137 138 return error; 139 } 140 141 /* 142 * cv_unsleep: 143 * 144 * Remove an LWP from the condition variable and sleep queue. This 145 * is called when the LWP has not been awoken normally but instead 146 * interrupted: for example, when a signal is received. Must be 147 * called with the LWP locked, and must return it unlocked. 148 */ 149 static u_int 150 cv_unsleep(lwp_t *l, bool cleanup) 151 { 152 kcondvar_t *cv; 153 154 cv = (kcondvar_t *)(uintptr_t)l->l_wchan; 155 156 KASSERT(l->l_wchan != NULL); 157 KASSERT(lwp_locked(l, l->l_sleepq->sq_mutex)); 158 KASSERT(cv_is_valid(cv)); 159 KASSERT(cv->cv_waiters > 0); 160 161 cv->cv_waiters--; 162 return sleepq_unsleep(l, cleanup); 163 } 164 165 /* 166 * cv_wait: 167 * 168 * Wait non-interruptably on a condition variable until awoken. 169 */ 170 void 171 cv_wait(kcondvar_t *cv, kmutex_t *mtx) 172 { 173 lwp_t *l = curlwp; 174 sleepq_t *sq; 175 176 KASSERT(mutex_owned(mtx)); 177 178 if (sleepq_dontsleep(l)) { 179 (void)sleepq_abort(mtx, 0); 180 return; 181 } 182 183 sq = cv_enter(cv, mtx, l); 184 (void)sleepq_block(0, false); 185 (void)cv_exit(cv, mtx, l, 0); 186 } 187 188 /* 189 * cv_wait_sig: 190 * 191 * Wait on a condition variable until a awoken or a signal is received. 192 * Will also return early if the process is exiting. Returns zero if 193 * awoken normallly, ERESTART if a signal was received and the system 194 * call is restartable, or EINTR otherwise. 195 */ 196 int 197 cv_wait_sig(kcondvar_t *cv, kmutex_t *mtx) 198 { 199 lwp_t *l = curlwp; 200 sleepq_t *sq; 201 int error; 202 203 KASSERT(mutex_owned(mtx)); 204 205 if (sleepq_dontsleep(l)) 206 return sleepq_abort(mtx, 0); 207 208 sq = cv_enter(cv, mtx, l); 209 error = sleepq_block(0, true); 210 return cv_exit(cv, mtx, l, error); 211 } 212 213 /* 214 * cv_timedwait: 215 * 216 * Wait on a condition variable until awoken or the specified timeout 217 * expires. Returns zero if awoken normally or EWOULDBLOCK if the 218 * timeout expired. 219 */ 220 int 221 cv_timedwait(kcondvar_t *cv, kmutex_t *mtx, int timo) 222 { 223 lwp_t *l = curlwp; 224 sleepq_t *sq; 225 int error; 226 227 KASSERT(mutex_owned(mtx)); 228 229 if (sleepq_dontsleep(l)) 230 return sleepq_abort(mtx, 0); 231 232 sq = cv_enter(cv, mtx, l); 233 error = sleepq_block(timo, false); 234 return cv_exit(cv, mtx, l, error); 235 } 236 237 /* 238 * cv_timedwait_sig: 239 * 240 * Wait on a condition variable until a timeout expires, awoken or a 241 * signal is received. Will also return early if the process is 242 * exiting. Returns zero if awoken normallly, EWOULDBLOCK if the 243 * timeout expires, ERESTART if a signal was received and the system 244 * call is restartable, or EINTR otherwise. 245 */ 246 int 247 cv_timedwait_sig(kcondvar_t *cv, kmutex_t *mtx, int timo) 248 { 249 lwp_t *l = curlwp; 250 sleepq_t *sq; 251 int error; 252 253 KASSERT(mutex_owned(mtx)); 254 255 if (sleepq_dontsleep(l)) 256 return sleepq_abort(mtx, 0); 257 258 sq = cv_enter(cv, mtx, l); 259 error = sleepq_block(timo, true); 260 return cv_exit(cv, mtx, l, error); 261 } 262 263 /* 264 * cv_signal: 265 * 266 * Wake the highest priority LWP waiting on a condition variable. 267 * Must be called with the interlocking mutex held. 268 */ 269 void 270 cv_signal(kcondvar_t *cv) 271 { 272 lwp_t *l; 273 sleepq_t *sq; 274 275 KASSERT(cv_is_valid(cv)); 276 277 if (cv->cv_waiters == 0) 278 return; 279 280 /* 281 * cv->cv_waiters may be stale and have dropped to zero, but 282 * while holding the interlock (the mutex passed to cv_wait() 283 * and similar) we will see non-zero values when it matters. 284 */ 285 286 sq = sleeptab_lookup(&sleeptab, cv); 287 if (cv->cv_waiters != 0) { 288 cv->cv_waiters--; 289 l = sleepq_wake(sq, cv, 1); 290 l->l_cv_signalled = 1; 291 } else 292 sleepq_unlock(sq); 293 294 KASSERT(cv_is_valid(cv)); 295 } 296 297 /* 298 * cv_broadcast: 299 * 300 * Wake all LWPs waiting on a condition variable. Must be called 301 * with the interlocking mutex held. 302 */ 303 void 304 cv_broadcast(kcondvar_t *cv) 305 { 306 sleepq_t *sq; 307 u_int cnt; 308 309 KASSERT(cv_is_valid(cv)); 310 311 if (cv->cv_waiters == 0) 312 return; 313 314 sq = sleeptab_lookup(&sleeptab, cv); 315 if ((cnt = cv->cv_waiters) != 0) { 316 cv->cv_waiters = 0; 317 sleepq_wake(sq, cv, cnt); 318 } else 319 sleepq_unlock(sq); 320 321 KASSERT(cv_is_valid(cv)); 322 } 323 324 /* 325 * cv_wakeup: 326 * 327 * Wake all LWPs waiting on a condition variable. For cases 328 * where the address may be waited on by mtsleep()/tsleep(). 329 * Not a documented call. 330 */ 331 void 332 cv_wakeup(kcondvar_t *cv) 333 { 334 sleepq_t *sq; 335 336 KASSERT(cv_is_valid(cv)); 337 338 sq = sleeptab_lookup(&sleeptab, cv); 339 cv->cv_waiters = 0; 340 sleepq_wake(sq, cv, (u_int)-1); 341 342 KASSERT(cv_is_valid(cv)); 343 } 344 345 /* 346 * cv_has_waiters: 347 * 348 * For diagnostic assertions: return non-zero if a condition 349 * variable has waiters. 350 */ 351 bool 352 cv_has_waiters(kcondvar_t *cv) 353 { 354 355 /* No need to interlock here */ 356 return cv->cv_waiters != 0; 357 } 358 359 /* 360 * cv_is_valid: 361 * 362 * For diagnostic assertions: return non-zero if a condition 363 * variable appears to be valid. No locks need be held. 364 */ 365 bool 366 cv_is_valid(kcondvar_t *cv) 367 { 368 369 if (cv->cv_wmesg == deadcv || cv->cv_wmesg == NULL) 370 return false; 371 if ((cv->cv_waiters & 0xff000000) != 0) { 372 /* Arbitrary: invalid number of waiters. */ 373 return false; 374 } 375 return cv->cv_waiters >= 0; 376 } 377