1 /* $NetBSD: pthread_cond.c,v 1.54 2009/01/18 12:14:17 lukem Exp $ */ 2 3 /*- 4 * Copyright (c) 2001, 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 Nathan J. Williams and 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 * We assume that there will be no contention on pthread_cond_t::ptc_lock 34 * because functioning applications must call both the wait and wakeup 35 * functions while holding the same application provided mutex. The 36 * spinlock is present only to prevent libpthread causing the application 37 * to crash or malfunction as a result of corrupted data structures, in 38 * the event that the application is buggy. 39 * 40 * If there is contention on spinlock when real-time threads are in use, 41 * it could cause a deadlock due to priority inversion: the thread holding 42 * the spinlock may not get CPU time to make forward progress and release 43 * the spinlock to a higher priority thread that is waiting for it. 44 * Contention on the spinlock will only occur with buggy applications, 45 * so at the time of writing it's not considered a major bug in libpthread. 46 */ 47 48 #include <sys/cdefs.h> 49 __RCSID("$NetBSD: pthread_cond.c,v 1.54 2009/01/18 12:14:17 lukem Exp $"); 50 51 #include <errno.h> 52 #include <sys/time.h> 53 #include <sys/types.h> 54 55 #include "pthread.h" 56 #include "pthread_int.h" 57 58 int _sys_nanosleep(const struct timespec *, struct timespec *); 59 60 extern int pthread__started; 61 62 static int pthread_cond_wait_nothread(pthread_t, pthread_mutex_t *, 63 const struct timespec *); 64 65 int _pthread_cond_has_waiters_np(pthread_cond_t *); 66 67 __weak_alias(pthread_cond_has_waiters_np,_pthread_cond_has_waiters_np) 68 69 __strong_alias(__libc_cond_init,pthread_cond_init) 70 __strong_alias(__libc_cond_signal,pthread_cond_signal) 71 __strong_alias(__libc_cond_broadcast,pthread_cond_broadcast) 72 __strong_alias(__libc_cond_wait,pthread_cond_wait) 73 __strong_alias(__libc_cond_timedwait,pthread_cond_timedwait) 74 __strong_alias(__libc_cond_destroy,pthread_cond_destroy) 75 76 int 77 pthread_cond_init(pthread_cond_t *cond, const pthread_condattr_t *attr) 78 { 79 80 pthread__error(EINVAL, "Invalid condition variable attribute", 81 (attr == NULL) || (attr->ptca_magic == _PT_CONDATTR_MAGIC)); 82 83 cond->ptc_magic = _PT_COND_MAGIC; 84 pthread_lockinit(&cond->ptc_lock); 85 PTQ_INIT(&cond->ptc_waiters); 86 cond->ptc_mutex = NULL; 87 88 return 0; 89 } 90 91 92 int 93 pthread_cond_destroy(pthread_cond_t *cond) 94 { 95 96 pthread__error(EINVAL, "Invalid condition variable", 97 cond->ptc_magic == _PT_COND_MAGIC); 98 pthread__error(EBUSY, "Destroying condition variable in use", 99 cond->ptc_mutex == NULL); 100 101 cond->ptc_magic = _PT_COND_DEAD; 102 103 return 0; 104 } 105 106 inline int 107 pthread_cond_timedwait(pthread_cond_t *cond, pthread_mutex_t *mutex, 108 const struct timespec *abstime) 109 { 110 pthread_t self; 111 int retval; 112 113 pthread__error(EINVAL, "Invalid condition variable", 114 cond->ptc_magic == _PT_COND_MAGIC); 115 pthread__error(EINVAL, "Invalid mutex", 116 mutex->ptm_magic == _PT_MUTEX_MAGIC); 117 pthread__error(EPERM, "Mutex not locked in condition wait", 118 mutex->ptm_owner != NULL); 119 if (abstime != NULL) { 120 pthread__error(EINVAL, "Invalid wait time", 121 (abstime->tv_sec >= 0) && 122 (abstime->tv_nsec >= 0) && 123 (abstime->tv_nsec < 1000000000)); 124 } 125 126 self = pthread__self(); 127 128 /* Just hang out for a while if threads aren't running yet. */ 129 if (__predict_false(pthread__started == 0)) { 130 return pthread_cond_wait_nothread(self, mutex, abstime); 131 } 132 if (__predict_false(self->pt_cancel)) { 133 pthread__cancelled(); 134 } 135 136 /* Note this thread as waiting on the CV. */ 137 pthread__spinlock(self, &cond->ptc_lock); 138 cond->ptc_mutex = mutex; 139 PTQ_INSERT_HEAD(&cond->ptc_waiters, self, pt_sleep); 140 self->pt_sleepobj = cond; 141 pthread__spinunlock(self, &cond->ptc_lock); 142 143 do { 144 self->pt_willpark = 1; 145 pthread_mutex_unlock(mutex); 146 self->pt_willpark = 0; 147 self->pt_blocking++; 148 retval = _lwp_park(abstime, self->pt_unpark, 149 __UNVOLATILE(&mutex->ptm_waiters), 150 __UNVOLATILE(&mutex->ptm_waiters)); 151 self->pt_unpark = 0; 152 self->pt_blocking--; 153 membar_sync(); 154 pthread_mutex_lock(mutex); 155 156 /* 157 * If we have cancelled then exit. POSIX dictates that 158 * the mutex must be held when we action the cancellation. 159 * 160 * If we absorbed a pthread_cond_signal() and cannot take 161 * the wakeup, we must ensure that another thread does. 162 * 163 * If awoke early, we may still be on the sleep queue and 164 * must remove ourself. 165 */ 166 if (__predict_false(retval != 0)) { 167 switch (errno) { 168 case EINTR: 169 case EALREADY: 170 retval = 0; 171 break; 172 default: 173 retval = errno; 174 break; 175 } 176 } 177 if (__predict_false(self->pt_cancel | retval)) { 178 pthread_cond_signal(cond); 179 if (self->pt_cancel) { 180 pthread__cancelled(); 181 } 182 break; 183 } 184 } while (self->pt_sleepobj != NULL); 185 186 return retval; 187 } 188 189 int 190 pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex) 191 { 192 193 return pthread_cond_timedwait(cond, mutex, NULL); 194 } 195 196 static int __noinline 197 pthread__cond_wake_one(pthread_cond_t *cond) 198 { 199 pthread_t self, signaled; 200 pthread_mutex_t *mutex; 201 lwpid_t lid; 202 203 pthread__error(EINVAL, "Invalid condition variable", 204 cond->ptc_magic == _PT_COND_MAGIC); 205 206 /* 207 * Pull the first thread off the queue. If the current thread 208 * is associated with the condition variable, remove it without 209 * awakening (error case in pthread_cond_timedwait()). 210 */ 211 self = pthread__self(); 212 pthread__spinlock(self, &cond->ptc_lock); 213 if (self->pt_sleepobj == cond) { 214 PTQ_REMOVE(&cond->ptc_waiters, self, pt_sleep); 215 self->pt_sleepobj = NULL; 216 } 217 signaled = PTQ_FIRST(&cond->ptc_waiters); 218 if (__predict_false(signaled == NULL)) { 219 cond->ptc_mutex = NULL; 220 pthread__spinunlock(self, &cond->ptc_lock); 221 return 0; 222 } 223 mutex = cond->ptc_mutex; 224 if (PTQ_NEXT(signaled, pt_sleep) == NULL) { 225 cond->ptc_mutex = NULL; 226 PTQ_INIT(&cond->ptc_waiters); 227 } else { 228 PTQ_REMOVE(&cond->ptc_waiters, signaled, pt_sleep); 229 } 230 signaled->pt_sleepobj = NULL; 231 lid = signaled->pt_lid; 232 pthread__spinunlock(self, &cond->ptc_lock); 233 234 /* 235 * For all valid uses of pthread_cond_signal(), the caller will 236 * hold the mutex that the target is using to synchronize with. 237 * To avoid the target awakening and immediatley blocking on the 238 * mutex, transfer the thread to be awoken to the current thread's 239 * deferred wakeup list. The waiter will be set running when the 240 * caller (this thread) releases the mutex. 241 */ 242 if (__predict_false(self->pt_nwaiters == (size_t)pthread__unpark_max)) { 243 (void)_lwp_unpark_all(self->pt_waiters, self->pt_nwaiters, 244 __UNVOLATILE(&mutex->ptm_waiters)); 245 self->pt_nwaiters = 0; 246 } 247 self->pt_waiters[self->pt_nwaiters++] = lid; 248 pthread__mutex_deferwake(self, mutex); 249 return 0; 250 } 251 252 int 253 pthread_cond_signal(pthread_cond_t *cond) 254 { 255 256 if (__predict_true(PTQ_EMPTY(&cond->ptc_waiters))) 257 return 0; 258 return pthread__cond_wake_one(cond); 259 } 260 261 static int __noinline 262 pthread__cond_wake_all(pthread_cond_t *cond) 263 { 264 pthread_t self, signaled; 265 pthread_mutex_t *mutex; 266 u_int max; 267 size_t nwaiters; 268 269 pthread__error(EINVAL, "Invalid condition variable", 270 cond->ptc_magic == _PT_COND_MAGIC); 271 272 /* 273 * Try to defer waking threads (see pthread_cond_signal()). 274 * Only transfer waiters for which there is no pending wakeup. 275 */ 276 self = pthread__self(); 277 pthread__spinlock(self, &cond->ptc_lock); 278 max = pthread__unpark_max; 279 mutex = cond->ptc_mutex; 280 nwaiters = self->pt_nwaiters; 281 PTQ_FOREACH(signaled, &cond->ptc_waiters, pt_sleep) { 282 if (__predict_false(nwaiters == max)) { 283 /* Overflow. */ 284 (void)_lwp_unpark_all(self->pt_waiters, 285 nwaiters, __UNVOLATILE(&mutex->ptm_waiters)); 286 nwaiters = 0; 287 } 288 signaled->pt_sleepobj = NULL; 289 self->pt_waiters[nwaiters++] = signaled->pt_lid; 290 } 291 PTQ_INIT(&cond->ptc_waiters); 292 self->pt_nwaiters = nwaiters; 293 cond->ptc_mutex = NULL; 294 pthread__spinunlock(self, &cond->ptc_lock); 295 pthread__mutex_deferwake(self, mutex); 296 297 return 0; 298 } 299 300 int 301 pthread_cond_broadcast(pthread_cond_t *cond) 302 { 303 304 if (__predict_true(PTQ_EMPTY(&cond->ptc_waiters))) 305 return 0; 306 return pthread__cond_wake_all(cond); 307 } 308 309 int 310 _pthread_cond_has_waiters_np(pthread_cond_t *cond) 311 { 312 313 return !PTQ_EMPTY(&cond->ptc_waiters); 314 } 315 316 int 317 pthread_condattr_init(pthread_condattr_t *attr) 318 { 319 320 attr->ptca_magic = _PT_CONDATTR_MAGIC; 321 322 return 0; 323 } 324 325 int 326 pthread_condattr_destroy(pthread_condattr_t *attr) 327 { 328 329 pthread__error(EINVAL, "Invalid condition variable attribute", 330 attr->ptca_magic == _PT_CONDATTR_MAGIC); 331 332 attr->ptca_magic = _PT_CONDATTR_DEAD; 333 334 return 0; 335 } 336 337 /* Utility routine to hang out for a while if threads haven't started yet. */ 338 static int 339 pthread_cond_wait_nothread(pthread_t self, pthread_mutex_t *mutex, 340 const struct timespec *abstime) 341 { 342 struct timespec now, diff; 343 int retval; 344 345 if (abstime == NULL) { 346 diff.tv_sec = 99999999; 347 diff.tv_nsec = 0; 348 } else { 349 clock_gettime(CLOCK_REALTIME, &now); 350 if (timespeccmp(abstime, &now, <)) 351 timespecclear(&diff); 352 else 353 timespecsub(abstime, &now, &diff); 354 } 355 356 do { 357 pthread__testcancel(self); 358 pthread_mutex_unlock(mutex); 359 retval = _sys_nanosleep(&diff, NULL); 360 pthread_mutex_lock(mutex); 361 } while (abstime == NULL && retval == 0); 362 pthread__testcancel(self); 363 364 if (retval == 0) 365 return ETIMEDOUT; 366 else 367 /* spurious wakeup */ 368 return 0; 369 } 370