lib/libpthread/thread/thr_cond.c

   1 /*
   2  * Copyright (c) 1995 John Birrell <jb@cimlogic.com.au>.
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  * 3. All advertising materials mentioning features or use of this software
  14  *    must display the following acknowledgement:
  15  *      This product includes software developed by John Birrell.
  16  * 4. Neither the name of the author nor the names of any co-contributors
  17  *    may be used to endorse or promote products derived from this software
  18  *    without specific prior written permission.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY JOHN BIRRELL AND CONTRIBUTORS ``AS IS'' AND
  21  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  22  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  23  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  24  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  25  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  26  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  27  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  28  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  29  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  30  * SUCH DAMAGE.
  31  *
  32  * $FreeBSD$
  33  */
  34 #include <stdlib.h>
  35 #include <errno.h>
  36 #include <string.h>
  37 #ifdef _THREAD_SAFE
  38 #include <pthread.h>
  39 #include "pthread_private.h"
  40
  41 /*
  42  * Prototypes
  43  */
  44 static inline pthread_t cond_queue_deq(pthread_cond_t);
  45 static inline void      cond_queue_remove(pthread_cond_t, pthread_t);
  46 static inline void      cond_queue_enq(pthread_cond_t, pthread_t);
  47
  48 /* Reinitialize a condition variable to defaults. */
  49 int
  50 _cond_reinit(pthread_cond_t * cond)
  51 {
  52         int ret = 0;
  53
  54         if (cond == NULL)
  55                 ret = EINVAL;
  56         else if (*cond == NULL)
  57                 ret = pthread_cond_init(cond, NULL);
  58         else {
  59                 /*
  60                  * Initialize the condition variable structure:
  61                  */
  62                 TAILQ_INIT(&(*cond)->c_queue);
  63                 (*cond)->c_flags = COND_FLAGS_INITED;
  64                 (*cond)->c_type = COND_TYPE_FAST;
  65                 (*cond)->c_mutex = NULL;
  66                 memset(&(*cond)->lock, 0, sizeof((*cond)->lock));
  67         }
  68         return (ret);
  69 }
  70
  71 int
  72 pthread_cond_init(pthread_cond_t * cond, const pthread_condattr_t * cond_attr)
  73 {
  74         enum pthread_cond_type type;
  75         pthread_cond_t  pcond;
  76         int             rval = 0;
  77
  78         if (cond == NULL)
  79                 rval = EINVAL;
  80         else {
  81                 /*
  82                  * Check if a pointer to a condition variable attribute
  83                  * structure was passed by the caller:
  84                  */
  85                 if (cond_attr != NULL && *cond_attr != NULL) {
  86                         /* Default to a fast condition variable: */
  87                         type = (*cond_attr)->c_type;
  88                 } else {
  89                         /* Default to a fast condition variable: */
  90                         type = COND_TYPE_FAST;
  91                 }
  92
  93                 /* Process according to condition variable type: */
  94                 switch (type) {
  95                 /* Fast condition variable: */
  96                 case COND_TYPE_FAST:
  97                         /* Nothing to do here. */
  98                         break;
  99
 100                 /* Trap invalid condition variable types: */
 101                 default:
 102                         /* Return an invalid argument error: */
 103                         rval = EINVAL;
 104                         break;
 105                 }
 106
 107                 /* Check for no errors: */
 108                 if (rval == 0) {
 109                         if ((pcond = (pthread_cond_t)
 110                             malloc(sizeof(struct pthread_cond))) == NULL) {
 111                                 rval = ENOMEM;
 112                         } else {
 113                                 /*
 114                                  * Initialise the condition variable
 115                                  * structure:
 116                                  */
 117                                 TAILQ_INIT(&pcond->c_queue);
 118                                 pcond->c_flags |= COND_FLAGS_INITED;
 119                                 pcond->c_type = type;
 120                                 pcond->c_mutex = NULL;
 121                                 memset(&pcond->lock,0,sizeof(pcond->lock));
 122                                 *cond = pcond;
 123                         }
 124                 }
 125         }
 126         /* Return the completion status: */
 127         return (rval);
 128 }
 129
 130 int
 131 pthread_cond_destroy(pthread_cond_t * cond)
 132 {
 133         int             rval = 0;
 134
 135         if (cond == NULL || *cond == NULL)
 136                 rval = EINVAL;
 137         else {
 138                 /* Lock the condition variable structure: */
 139                 _SPINLOCK(&(*cond)->lock);
 140
 141                 /*
 142                  * Free the memory allocated for the condition
 143                  * variable structure:
 144                  */
 145                 free(*cond);
 146
 147                 /*
 148                  * NULL the caller's pointer now that the condition
 149                  * variable has been destroyed:
 150                  */
 151                 *cond = NULL;
 152         }
 153         /* Return the completion status: */
 154         return (rval);
 155 }
 156
 157 int
 158 pthread_cond_wait(pthread_cond_t * cond, pthread_mutex_t * mutex)
 159 {
 160         int     rval = 0;
 161         int     interrupted = 0;
 162
 163         _thread_enter_cancellation_point();
 164
 165         if (cond == NULL)
 166                 rval = EINVAL;
 167
 168         /*
 169          * If the condition variable is statically initialized,
 170          * perform the dynamic initialization:
 171          */
 172         else if (*cond != NULL ||
 173             (rval = pthread_cond_init(cond,NULL)) == 0) {
 174
 175                 _thread_enter_cancellation_point();
 176
 177                 /* Lock the condition variable structure: */
 178                 _SPINLOCK(&(*cond)->lock);
 179
 180                 /*
 181                  * If the condvar was statically allocated, properly
 182                  * initialize the tail queue.
 183                  */
 184                 if (((*cond)->c_flags & COND_FLAGS_INITED) == 0) {
 185                         TAILQ_INIT(&(*cond)->c_queue);
 186                         (*cond)->c_flags |= COND_FLAGS_INITED;
 187                 }
 188
 189                 /* Process according to condition variable type: */
 190                 switch ((*cond)->c_type) {
 191                 /* Fast condition variable: */
 192                 case COND_TYPE_FAST:
 193                         if ((mutex == NULL) || (((*cond)->c_mutex != NULL) &&
 194                             ((*cond)->c_mutex != *mutex))) {
 195                                 /* Unlock the condition variable structure: */
 196                                 _SPINUNLOCK(&(*cond)->lock);
 197
 198                                 /* Return invalid argument error: */
 199                                 rval = EINVAL;
 200                         } else {
 201                                 /* Reset the timeout and interrupted flags: */
 202                                 _thread_run->timeout = 0;
 203                                 _thread_run->interrupted = 0;
 204
 205                                 /*
 206                                  * Queue the running thread for the condition
 207                                  * variable:
 208                                  */
 209                                 cond_queue_enq(*cond, _thread_run);
 210
 211                                 /* Remember the mutex that is being used: */
 212                                 (*cond)->c_mutex = *mutex;
 213
 214                                 /* Wait forever: */
 215                                 _thread_run->wakeup_time.tv_sec = -1;
 216
 217                                 /* Unlock the mutex: */
 218                                 if ((rval = _mutex_cv_unlock(mutex)) != 0) {
 219                                         /*
 220                                          * Cannot unlock the mutex, so remove
 221                                          * the running thread from the condition
 222                                          * variable queue:
 223                                          */
 224                                         cond_queue_remove(*cond, _thread_run);
 225
 226                                         /* Check for no more waiters: */
 227                                         if (TAILQ_FIRST(&(*cond)->c_queue) ==
 228                                             NULL)
 229                                                 (*cond)->c_mutex = NULL;
 230
 231                                         /* Unlock the condition variable structure: */
 232                                         _SPINUNLOCK(&(*cond)->lock);
 233                                 }
 234                                 else {
 235                                         /*
 236                                          * Schedule the next thread and unlock
 237                                          * the condition variable structure:
 238                                          */
 239                                         _thread_kern_sched_state_unlock(PS_COND_WAIT,
 240                                             &(*cond)->lock, __FILE__, __LINE__);
 241
 242                                         if (_thread_run->interrupted != 0) {
 243                                                 /*
 244                                                  * Remember that this thread
 245                                                  * was interrupted:
 246                                                  */
 247                                                 interrupted = 1;
 248
 249                                                 /*
 250                                                  * Lock the condition variable
 251                                                  * while removing the thread.
 252                                                  */
 253                                                 _SPINLOCK(&(*cond)->lock);
 254
 255                                                 cond_queue_remove(*cond,
 256                                                     _thread_run);
 257
 258                                                 /* Check for no more waiters: */
 259                                                 if (TAILQ_FIRST(&(*cond)->c_queue) == NULL)
 260                                                         (*cond)->c_mutex = NULL;
 261
 262                                                 _SPINUNLOCK(&(*cond)->lock);
 263                                         }
 264
 265                                         /*
 266                                          * Note that even though this thread may have
 267                                          * been canceled, POSIX requires that the mutex
 268                                          * be reaquired prior to cancellation.
 269                                          */
 270                                         rval = _mutex_cv_lock(mutex);
 271                                 }
 272                         }
 273                         break;
 274
 275                 /* Trap invalid condition variable types: */
 276                 default:
 277                         /* Unlock the condition variable structure: */
 278                         _SPINUNLOCK(&(*cond)->lock);
 279
 280                         /* Return an invalid argument error: */
 281                         rval = EINVAL;
 282                         break;
 283                 }
 284
 285                 if (interrupted != 0) {
 286                         if (_thread_run->continuation != NULL)
 287                                 _thread_run->continuation((void *) _thread_run);
 288                         rval = EINTR;
 289                 }
 290
 291                 _thread_leave_cancellation_point();
 292         }
 293
 294         _thread_leave_cancellation_point();
 295
 296         /* Return the completion status: */
 297         return (rval);
 298 }
 299
 300 int
 301 pthread_cond_timedwait(pthread_cond_t * cond, pthread_mutex_t * mutex,
 302                        const struct timespec * abstime)
 303 {
 304         int     rval = 0;
 305         int     interrupted = 0;
 306
 307         _thread_enter_cancellation_point();
 308
 309         if (cond == NULL || abstime == NULL)
 310                 rval = EINVAL;
 311
 312         if (abstime->tv_sec < 0 ||
 313                 abstime->tv_nsec < 0 || abstime->tv_nsec >= 1000000000) {
 314                 errno = EINVAL;
 315                 _thread_leave_cancellation_point();
 316                 return (-1);
 317         }
 318
 319         /*
 320          * If the condition variable is statically initialized,
 321          * perform the dynamic initialization:
 322          */
 323         if (*cond != NULL ||
 324             (rval = pthread_cond_init(cond,NULL)) == 0) {
 325
 326                 _thread_enter_cancellation_point();
 327
 328                 /* Lock the condition variable structure: */
 329                 _SPINLOCK(&(*cond)->lock);
 330
 331                 /*
 332                  * If the condvar was statically allocated, properly
 333                  * initialize the tail queue.
 334                  */
 335                 if (((*cond)->c_flags & COND_FLAGS_INITED) == 0) {
 336                         TAILQ_INIT(&(*cond)->c_queue);
 337                         (*cond)->c_flags |= COND_FLAGS_INITED;
 338                 }
 339
 340                 /* Process according to condition variable type: */
 341                 switch ((*cond)->c_type) {
 342                 /* Fast condition variable: */
 343                 case COND_TYPE_FAST:
 344                         if ((mutex == NULL) || (((*cond)->c_mutex != NULL) &&
 345                             ((*cond)->c_mutex != *mutex))) {
 346                                 /* Return invalid argument error: */
 347                                 rval = EINVAL;
 348
 349                                 /* Unlock the condition variable structure: */
 350                                 _SPINUNLOCK(&(*cond)->lock);
 351                         } else {
 352                                 /* Set the wakeup time: */
 353                                 _thread_run->wakeup_time.tv_sec =
 354                                     abstime->tv_sec;
 355                                 _thread_run->wakeup_time.tv_nsec =
 356                                     abstime->tv_nsec;
 357
 358                                 /* Reset the timeout and interrupted flags: */
 359                                 _thread_run->timeout = 0;
 360                                 _thread_run->interrupted = 0;
 361
 362                                 /*
 363                                  * Queue the running thread for the condition
 364                                  * variable:
 365                                  */
 366                                 cond_queue_enq(*cond, _thread_run);
 367
 368                                 /* Remember the mutex that is being used: */
 369                                 (*cond)->c_mutex = *mutex;
 370
 371                                 /* Unlock the mutex: */
 372                                 if ((rval = _mutex_cv_unlock(mutex)) != 0) {
 373                                         /*
 374                                          * Cannot unlock the mutex, so remove
 375                                          * the running thread from the condition
 376                                          * variable queue:
 377                                          */
 378                                         cond_queue_remove(*cond, _thread_run);
 379
 380                                         /* Check for no more waiters: */
 381                                         if (TAILQ_FIRST(&(*cond)->c_queue) == NULL)
 382                                                 (*cond)->c_mutex = NULL;
 383
 384                                         /* Unlock the condition variable structure: */
 385                                         _SPINUNLOCK(&(*cond)->lock);
 386                                 } else {
 387                                         /*
 388                                          * Schedule the next thread and unlock
 389                                          * the condition variable structure:
 390                                          */
 391                                         _thread_kern_sched_state_unlock(PS_COND_WAIT,
 392                                              &(*cond)->lock, __FILE__, __LINE__);
 393
 394                                         /*
 395                                          * Check if the wait timedout or was
 396                                          * interrupted (canceled):
 397                                          */
 398                                         if ((_thread_run->timeout == 0) &&
 399                                             (_thread_run->interrupted == 0)) {
 400                                                 /* Lock the mutex: */
 401                                                 rval = _mutex_cv_lock(mutex);
 402
 403                                         } else {
 404                                                 /*
 405                                                  * Remember if this thread was
 406                                                  * interrupted:
 407                                                  */
 408                                                 interrupted = _thread_run->interrupted;
 409
 410                                                 /* Lock the condition variable structure: */
 411                                                 _SPINLOCK(&(*cond)->lock);
 412
 413                                                 /*
 414                                                  * The wait timed out; remove
 415                                                  * the thread from the condition
 416                                                  * variable queue:
 417                                                  */
 418                                                 cond_queue_remove(*cond,
 419                                                     _thread_run);
 420
 421                                                 /* Check for no more waiters: */
 422                                                 if (TAILQ_FIRST(&(*cond)->c_queue) == NULL)
 423                                                         (*cond)->c_mutex = NULL;
 424
 425                                                 /* Unock the condition variable structure: */
 426                                                 _SPINUNLOCK(&(*cond)->lock);
 427
 428                                                 /* Return a timeout error: */
 429                                                 rval = ETIMEDOUT;
 430
 431                                                 /*
 432                                                  * Lock the mutex and ignore any
 433                                                  * errors.  Note that even though
 434                                                  * this thread may have been
 435                                                  * canceled, POSIX requires that
 436                                                  * the mutex be reaquired prior
 437                                                  * to cancellation.
 438                                                  */
 439                                                 (void)_mutex_cv_lock(mutex);
 440                                         }
 441                                 }
 442                         }
 443                         break;
 444
 445                 /* Trap invalid condition variable types: */
 446                 default:
 447                         /* Unlock the condition variable structure: */
 448                         _SPINUNLOCK(&(*cond)->lock);
 449
 450                         /* Return an invalid argument error: */
 451                         rval = EINVAL;
 452                         break;
 453                 }
 454
 455                 if (interrupted != 0) {
 456                         if (_thread_run->continuation != NULL)
 457                                 _thread_run->continuation((void *) _thread_run);
 458                         rval = EINTR;
 459                 }
 460
 461                 _thread_leave_cancellation_point();
 462         }
 463
 464         _thread_leave_cancellation_point();
 465
 466         /* Return the completion status: */
 467         return (rval);
 468 }
 469
 470 int
 471 pthread_cond_signal(pthread_cond_t * cond)
 472 {
 473         int             rval = 0;
 474         pthread_t       pthread;
 475
 476         if (cond == NULL || *cond == NULL)
 477                 rval = EINVAL;
 478         else {
 479                 /*
 480                  * Defer signals to protect the scheduling queues
 481                  * from access by the signal handler:
 482                  */
 483                 _thread_kern_sig_defer();
 484
 485                 /* Lock the condition variable structure: */
 486                 _SPINLOCK(&(*cond)->lock);
 487
 488                 /* Process according to condition variable type: */
 489                 switch ((*cond)->c_type) {
 490                 /* Fast condition variable: */
 491                 case COND_TYPE_FAST:
 492                         if ((pthread = cond_queue_deq(*cond)) != NULL)
 493                                 /* Allow the thread to run: */
 494                                 PTHREAD_NEW_STATE(pthread,PS_RUNNING);
 495
 496                         /* Check for no more waiters: */
 497                         if (TAILQ_FIRST(&(*cond)->c_queue) == NULL)
 498                                 (*cond)->c_mutex = NULL;
 499                         break;
 500
 501                 /* Trap invalid condition variable types: */
 502                 default:
 503                         /* Return an invalid argument error: */
 504                         rval = EINVAL;
 505                         break;
 506                 }
 507
 508                 /* Unlock the condition variable structure: */
 509                 _SPINUNLOCK(&(*cond)->lock);
 510
 511                 /*
 512                  * Undefer and handle pending signals, yielding if
 513                  * necessary:
 514                  */
 515                 _thread_kern_sig_undefer();
 516         }
 517
 518         /* Return the completion status: */
 519         return (rval);
 520 }
 521
 522 int
 523 pthread_cond_broadcast(pthread_cond_t * cond)
 524 {
 525         int             rval = 0;
 526         pthread_t       pthread;
 527
 528         if (cond == NULL || *cond == NULL)
 529                 rval = EINVAL;
 530         else {
 531                 /*
 532                  * Defer signals to protect the scheduling queues
 533                  * from access by the signal handler:
 534                  */
 535                 _thread_kern_sig_defer();
 536
 537                 /* Lock the condition variable structure: */
 538                 _SPINLOCK(&(*cond)->lock);
 539
 540                 /* Process according to condition variable type: */
 541                 switch ((*cond)->c_type) {
 542                 /* Fast condition variable: */
 543                 case COND_TYPE_FAST:
 544                         /*
 545                          * Enter a loop to bring all threads off the
 546                          * condition queue:
 547                          */
 548                         while ((pthread = cond_queue_deq(*cond)) != NULL) {
 549                                 PTHREAD_NEW_STATE(pthread,PS_RUNNING);
 550                         }
 551
 552                         /* There are no more waiting threads: */
 553                         (*cond)->c_mutex = NULL;
 554                         break;
 555
 556                 /* Trap invalid condition variable types: */
 557                 default:
 558                         /* Return an invalid argument error: */
 559                         rval = EINVAL;
 560                         break;
 561                 }
 562
 563                 /* Unlock the condition variable structure: */
 564                 _SPINUNLOCK(&(*cond)->lock);
 565
 566                 /*
 567                  * Undefer and handle pending signals, yielding if
 568                  * necessary:
 569                  */
 570                 _thread_kern_sig_undefer();
 571         }
 572
 573         /* Return the completion status: */
 574         return (rval);
 575 }
 576
 577 /*
 578  * Dequeue a waiting thread from the head of a condition queue in
 579  * descending priority order.
 580  */
 581 static inline pthread_t
 582 cond_queue_deq(pthread_cond_t cond)
 583 {
 584         pthread_t pthread;
 585
 586         while ((pthread = TAILQ_FIRST(&cond->c_queue)) != NULL) {
 587                 TAILQ_REMOVE(&cond->c_queue, pthread, qe);
 588                 pthread->flags &= ~PTHREAD_FLAGS_IN_CONDQ;
 589                 if ((pthread->timeout == 0) && (pthread->interrupted == 0))
 590                         /*
 591                          * Only exit the loop when we find a thread
 592                          * that hasn't timed out or been canceled;
 593                          * those threads are already running and don't
 594                          * need their run state changed.
 595                          */
 596                         break;
 597         }
 598
 599         return(pthread);
 600 }
 601
 602 /*
 603  * Remove a waiting thread from a condition queue in descending priority
 604  * order.
 605  */
 606 static inline void
 607 cond_queue_remove(pthread_cond_t cond, pthread_t pthread)
 608 {
 609         /*
 610          * Because pthread_cond_timedwait() can timeout as well
 611          * as be signaled by another thread, it is necessary to
 612          * guard against removing the thread from the queue if
 613          * it isn't in the queue.
 614          */
 615         if (pthread->flags & PTHREAD_FLAGS_IN_CONDQ) {
 616                 TAILQ_REMOVE(&cond->c_queue, pthread, qe);
 617                 pthread->flags &= ~PTHREAD_FLAGS_IN_CONDQ;
 618         }
 619 }
 620
 621 /*
 622  * Enqueue a waiting thread to a condition queue in descending priority
 623  * order.
 624  */
 625 static inline void
 626 cond_queue_enq(pthread_cond_t cond, pthread_t pthread)
 627 {
 628         pthread_t tid = TAILQ_LAST(&cond->c_queue, cond_head);
 629
 630         /*
 631          * For the common case of all threads having equal priority,
 632          * we perform a quick check against the priority of the thread
 633          * at the tail of the queue.
 634          */
 635         if ((tid == NULL) || (pthread->active_priority <= tid->active_priority))
 636                 TAILQ_INSERT_TAIL(&cond->c_queue, pthread, qe);
 637         else {
 638                 tid = TAILQ_FIRST(&cond->c_queue);
 639                 while (pthread->active_priority <= tid->active_priority)
 640                         tid = TAILQ_NEXT(tid, qe);
 641                 TAILQ_INSERT_BEFORE(tid, pthread, qe);
 642         }
 643         pthread->flags |= PTHREAD_FLAGS_IN_CONDQ;
 644 }
 645 #endif