lib/libpthread/pthread_cond.c

   1 /*      $NetBSD: pthread_cond.c,v 1.53 2008/10/25 14:14:11 yamt 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.53 2008/10/25 14:14:11 yamt 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 }