linuxthreads/rwlock.c

   1 /* Read-write lock implementation.
   2    Copyright (C) 1998, 2000 Free Software Foundation, Inc.
   3    This file is part of the GNU C Library.
   4    Contributed by Xavier Leroy <Xavier.Leroy@inria.fr>
   5    and Ulrich Drepper <drepper@cygnus.com>, 1998.
   6
   7    The GNU C Library is free software; you can redistribute it and/or
   8    modify it under the terms of the GNU Library General Public License as
   9    published by the Free Software Foundation; either version 2 of the
  10    License, or (at your option) any later version.
  11
  12    The GNU C Library is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15    Library General Public License for more details.
  16
  17    You should have received a copy of the GNU Library General Public
  18    License along with the GNU C Library; see the file COPYING.LIB.  If not,
  19    write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  20    Boston, MA 02111-1307, USA.  */
  21
  22 #include <bits/libc-lock.h>
  23 #include <errno.h>
  24 #include <pthread.h>
  25 #include <stdlib.h>
  26 #include "internals.h"
  27 #include "queue.h"
  28 #include "spinlock.h"
  29 #include "restart.h"
  30
  31 /* Function called by pthread_cancel to remove the thread from
  32    waiting inside pthread_rwlock_timedrdlock or pthread_rwlock_timedwrlock. */
  33
  34 static int rwlock_rd_extricate_func(void *obj, pthread_descr th)
  35 {
  36   pthread_rwlock_t *rwlock = obj;
  37   int did_remove = 0;
  38
  39   __pthread_lock((struct _pthread_fastlock *) &rwlock->__rw_lock, NULL);
  40   did_remove = remove_from_queue(&rwlock->__rw_read_waiting, th);
  41   __pthread_unlock((struct _pthread_fastlock *) &rwlock->__rw_lock);
  42
  43   return did_remove;
  44 }
  45
  46 static int rwlock_wr_extricate_func(void *obj, pthread_descr th)
  47 {
  48   pthread_rwlock_t *rwlock = obj;
  49   int did_remove = 0;
  50
  51   __pthread_lock((struct _pthread_fastlock *) &rwlock->__rw_lock, NULL);
  52   did_remove = remove_from_queue(&rwlock->__rw_write_waiting, th);
  53   __pthread_unlock((struct _pthread_fastlock *) &rwlock->__rw_lock);
  54
  55   return did_remove;
  56 }
  57
  58 /*
  59  * Check whether the calling thread already owns one or more read locks on the
  60  * specified lock. If so, return a pointer to the read lock info structure
  61  * corresponding to that lock.
  62  */
  63
  64 static pthread_readlock_info *
  65 rwlock_is_in_list(pthread_descr self, pthread_rwlock_t *rwlock)
  66 {
  67   pthread_readlock_info *info;
  68
  69   for (info = THREAD_GETMEM (self, p_readlock_list); info != NULL;
  70        info = info->pr_next)
  71     {
  72       if (info->pr_lock == rwlock)
  73         return info;
  74     }
  75
  76   return NULL;
  77 }
  78
  79 /*
  80  * Add a new lock to the thread's list of locks for which it has a read lock.
  81  * A new info node must be allocated for this, which is taken from the thread's
  82  * free list, or by calling malloc. If malloc fails, a null pointer is
  83  * returned. Otherwise the lock info structure is initialized and pushed
  84  * onto the thread's list.
  85  */
  86
  87 static pthread_readlock_info *
  88 rwlock_add_to_list(pthread_descr self, pthread_rwlock_t *rwlock)
  89 {
  90   pthread_readlock_info *info = THREAD_GETMEM (self, p_readlock_free);
  91
  92   if (info != NULL)
  93     THREAD_SETMEM (self, p_readlock_free, info->pr_next);
  94   else
  95     info = malloc(sizeof *info);
  96
  97   if (info == NULL)
  98     return NULL;
  99
 100   info->pr_lock_count = 1;
 101   info->pr_lock = rwlock;
 102   info->pr_next = THREAD_GETMEM (self, p_readlock_list);
 103   THREAD_SETMEM (self, p_readlock_list, info);
 104
 105   return info;
 106 }
 107
 108 /*
 109  * If the thread owns a read lock over the given pthread_rwlock_t,
 110  * and this read lock is tracked in the thread's lock list,
 111  * this function returns a pointer to the info node in that list.
 112  * It also decrements the lock count within that node, and if
 113  * it reaches zero, it removes the node from the list.
 114  * If nothing is found, it returns a null pointer.
 115  */
 116
 117 static pthread_readlock_info *
 118 rwlock_remove_from_list(pthread_descr self, pthread_rwlock_t *rwlock)
 119 {
 120   pthread_readlock_info **pinfo;
 121
 122   for (pinfo = &self->p_readlock_list; *pinfo != NULL; pinfo = &(*pinfo)->pr_next)
 123     {
 124       if ((*pinfo)->pr_lock == rwlock)
 125         {
 126           pthread_readlock_info *info = *pinfo;
 127           if (--info->pr_lock_count == 0)
 128             *pinfo = info->pr_next;
 129           return info;
 130         }
 131     }
 132
 133   return NULL;
 134 }
 135
 136 /*
 137  * This function checks whether the conditions are right to place a read lock.
 138  * It returns 1 if so, otherwise zero. The rwlock's internal lock must be
 139  * locked upon entry.
 140  */
 141
 142 static int
 143 rwlock_can_rdlock(pthread_rwlock_t *rwlock, int have_lock_already)
 144 {
 145   /* Can't readlock; it is write locked. */
 146   if (rwlock->__rw_writer != NULL)
 147     return 0;
 148
 149   /* Lock prefers readers; get it. */
 150   if (rwlock->__rw_kind == PTHREAD_RWLOCK_PREFER_READER_NP)
 151     return 1;
 152
 153   /* Lock prefers writers, but none are waiting. */
 154   if (queue_is_empty(&rwlock->__rw_write_waiting))
 155     return 1;
 156
 157   /* Writers are waiting, but this thread already has a read lock */
 158   if (have_lock_already)
 159     return 1;
 160
 161   /* Writers are waiting, and this is a new lock */
 162   return 0;
 163 }
 164
 165 /*
 166  * This function helps support brain-damaged recursive read locking
 167  * semantics required by Unix 98, while maintaining write priority.
 168  * This basically determines whether this thread already holds a read lock
 169  * already. It returns 1 if so, otherwise it returns 0.
 170  *
 171  * If the thread has any ``untracked read locks'' then it just assumes
 172  * that this lock is among them, just to be safe, and returns 1.
 173  *
 174  * Also, if it finds the thread's lock in the list, it sets the pointer
 175  * referenced by pexisting to refer to the list entry.
 176  *
 177  * If the thread has no untracked locks, and the lock is not found
 178  * in its list, then it is added to the list. If this fails,
 179  * then *pout_of_mem is set to 1.
 180  */
 181
 182 static int
 183 rwlock_have_already(pthread_descr *pself, pthread_rwlock_t *rwlock,
 184     pthread_readlock_info **pexisting, int *pout_of_mem)
 185 {
 186   pthread_readlock_info *existing = NULL;
 187   int out_of_mem = 0, have_lock_already = 0;
 188   pthread_descr self = *pself;
 189
 190   if (rwlock->__rw_kind == PTHREAD_RWLOCK_PREFER_WRITER_NP)
 191     {
 192       if (!self)
 193         *pself = self = thread_self();
 194
 195       existing = rwlock_is_in_list(self, rwlock);
 196
 197       if (existing != NULL
 198           || THREAD_GETMEM (self, p_untracked_readlock_count) > 0)
 199         have_lock_already = 1;
 200       else
 201         {
 202           existing = rwlock_add_to_list(self, rwlock);
 203           if (existing == NULL)
 204             out_of_mem = 1;
 205         }
 206     }
 207
 208   *pout_of_mem = out_of_mem;
 209   *pexisting = existing;
 210
 211   return have_lock_already;
 212 }
 213
 214 int
 215 __pthread_rwlock_init (pthread_rwlock_t *rwlock,
 216                        const pthread_rwlockattr_t *attr)
 217 {
 218   __pthread_init_lock(&rwlock->__rw_lock);
 219   rwlock->__rw_readers = 0;
 220   rwlock->__rw_writer = NULL;
 221   rwlock->__rw_read_waiting = NULL;
 222   rwlock->__rw_write_waiting = NULL;
 223
 224   if (attr == NULL)
 225     {
 226       rwlock->__rw_kind = PTHREAD_RWLOCK_DEFAULT_NP;
 227       rwlock->__rw_pshared = PTHREAD_PROCESS_PRIVATE;
 228     }
 229   else
 230     {
 231       rwlock->__rw_kind = attr->__lockkind;
 232       rwlock->__rw_pshared = attr->__pshared;
 233     }
 234
 235   return 0;
 236 }
 237 strong_alias (__pthread_rwlock_init, pthread_rwlock_init)
 238
 239
 240 int
 241 __pthread_rwlock_destroy (pthread_rwlock_t *rwlock)
 242 {
 243   int readers;
 244   _pthread_descr writer;
 245
 246   __pthread_lock (&rwlock->__rw_lock, NULL);
 247   readers = rwlock->__rw_readers;
 248   writer = rwlock->__rw_writer;
 249   __pthread_unlock (&rwlock->__rw_lock);
 250
 251   if (readers > 0 || writer != NULL)
 252     return EBUSY;
 253
 254   return 0;
 255 }
 256 strong_alias (__pthread_rwlock_destroy, pthread_rwlock_destroy)
 257
 258 int
 259 __pthread_rwlock_rdlock (pthread_rwlock_t *rwlock)
 260 {
 261   pthread_descr self = NULL;
 262   pthread_readlock_info *existing;
 263   int out_of_mem, have_lock_already;
 264
 265   have_lock_already = rwlock_have_already(&self, rwlock,
 266                                           &existing, &out_of_mem);
 267
 268   if (self == NULL)
 269     self = thread_self ();
 270
 271   for (;;)
 272     {
 273       __pthread_lock (&rwlock->__rw_lock, self);
 274
 275       if (rwlock_can_rdlock(rwlock, have_lock_already))
 276         break;
 277
 278       enqueue (&rwlock->__rw_read_waiting, self);
 279       __pthread_unlock (&rwlock->__rw_lock);
 280       suspend (self); /* This is not a cancellation point */
 281     }
 282
 283   ++rwlock->__rw_readers;
 284   __pthread_unlock (&rwlock->__rw_lock);
 285
 286   if (have_lock_already || out_of_mem)
 287     {
 288       if (existing != NULL)
 289         ++existing->pr_lock_count;
 290       else
 291         ++self->p_untracked_readlock_count;
 292     }
 293
 294   return 0;
 295 }
 296 strong_alias (__pthread_rwlock_rdlock, pthread_rwlock_rdlock)
 297
 298 int
 299 __pthread_rwlock_timedrdlock (pthread_rwlock_t *rwlock,
 300                               const struct timespec *abstime)
 301 {
 302   pthread_descr self = NULL;
 303   pthread_readlock_info *existing;
 304   int out_of_mem, have_lock_already;
 305   pthread_extricate_if extr;
 306
 307   if (abstime->tv_nsec < 0 || abstime->tv_nsec >= 1000000000)
 308     return EINVAL;
 309
 310   have_lock_already = rwlock_have_already(&self, rwlock,
 311                                           &existing, &out_of_mem);
 312
 313   if (self == NULL)
 314     self = thread_self ();
 315
 316   /* Set up extrication interface */
 317   extr.pu_object = rwlock;
 318   extr.pu_extricate_func = rwlock_rd_extricate_func;
 319
 320   /* Register extrication interface */
 321   __pthread_set_own_extricate_if (self, &extr);
 322
 323   for (;;)
 324     {
 325       __pthread_lock (&rwlock->__rw_lock, self);
 326
 327       if (rwlock_can_rdlock(rwlock, have_lock_already))
 328         break;
 329
 330       enqueue (&rwlock->__rw_read_waiting, self);
 331       __pthread_unlock (&rwlock->__rw_lock);
 332       /* This is not a cancellation point */
 333       if (timedsuspend (self, abstime) == 0)
 334         {
 335           int was_on_queue;
 336
 337           __pthread_lock (&rwlock->__rw_lock, self);
 338           was_on_queue = remove_from_queue (&rwlock->__rw_read_waiting, self);
 339           __pthread_unlock (&rwlock->__rw_lock);
 340
 341           if (was_on_queue)
 342             {
 343               __pthread_set_own_extricate_if (self, 0);
 344               return ETIMEDOUT;
 345             }
 346
 347           /* Eat the outstanding restart() from the signaller */
 348           suspend (self);
 349         }
 350     }
 351
 352   __pthread_set_own_extricate_if (self, 0);
 353
 354   ++rwlock->__rw_readers;
 355   __pthread_unlock (&rwlock->__rw_lock);
 356
 357   if (have_lock_already || out_of_mem)
 358     {
 359       if (existing != NULL)
 360         ++existing->pr_lock_count;
 361       else
 362         ++self->p_untracked_readlock_count;
 363     }
 364
 365   return 0;
 366 }
 367 strong_alias (__pthread_rwlock_timedrdlock, pthread_rwlock_timedrdlock)
 368
 369 int
 370 __pthread_rwlock_tryrdlock (pthread_rwlock_t *rwlock)
 371 {
 372   pthread_descr self = thread_self();
 373   pthread_readlock_info *existing;
 374   int out_of_mem, have_lock_already;
 375   int retval = EBUSY;
 376
 377   have_lock_already = rwlock_have_already(&self, rwlock,
 378       &existing, &out_of_mem);
 379
 380   __pthread_lock (&rwlock->__rw_lock, self);
 381
 382   /* 0 is passed to here instead of have_lock_already.
 383      This is to meet Single Unix Spec requirements:
 384      if writers are waiting, pthread_rwlock_tryrdlock
 385      does not acquire a read lock, even if the caller has
 386      one or more read locks already. */
 387
 388   if (rwlock_can_rdlock(rwlock, 0))
 389     {
 390       ++rwlock->__rw_readers;
 391       retval = 0;
 392     }
 393
 394   __pthread_unlock (&rwlock->__rw_lock);
 395
 396   if (retval == 0)
 397     {
 398       if (have_lock_already || out_of_mem)
 399         {
 400           if (existing != NULL)
 401             ++existing->pr_lock_count;
 402           else
 403             ++self->p_untracked_readlock_count;
 404         }
 405     }
 406
 407   return retval;
 408 }
 409 strong_alias (__pthread_rwlock_tryrdlock, pthread_rwlock_tryrdlock)
 410
 411
 412 int
 413 __pthread_rwlock_wrlock (pthread_rwlock_t *rwlock)
 414 {
 415   pthread_descr self = thread_self ();
 416
 417   while(1)
 418     {
 419       __pthread_lock (&rwlock->__rw_lock, self);
 420       if (rwlock->__rw_readers == 0 && rwlock->__rw_writer == NULL)
 421         {
 422           rwlock->__rw_writer = self;
 423           __pthread_unlock (&rwlock->__rw_lock);
 424           return 0;
 425         }
 426
 427       /* Suspend ourselves, then try again */
 428       enqueue (&rwlock->__rw_write_waiting, self);
 429       __pthread_unlock (&rwlock->__rw_lock);
 430       suspend (self); /* This is not a cancellation point */
 431     }
 432 }
 433 strong_alias (__pthread_rwlock_wrlock, pthread_rwlock_wrlock)
 434
 435
 436 int
 437 __pthread_rwlock_timedwrlock (pthread_rwlock_t *rwlock,
 438                               const struct timespec *abstime)
 439 {
 440   pthread_descr self;
 441   pthread_extricate_if extr;
 442
 443   if (abstime->tv_nsec < 0 || abstime->tv_nsec >= 1000000000)
 444     return EINVAL;
 445
 446   self = thread_self ();
 447
 448   /* Set up extrication interface */
 449   extr.pu_object = rwlock;
 450   extr.pu_extricate_func =  rwlock_wr_extricate_func;
 451
 452   /* Register extrication interface */
 453   __pthread_set_own_extricate_if (self, &extr);
 454
 455   while(1)
 456     {
 457       __pthread_lock (&rwlock->__rw_lock, self);
 458
 459       if (rwlock->__rw_readers == 0 && rwlock->__rw_writer == NULL)
 460         {
 461           rwlock->__rw_writer = self;
 462           __pthread_set_own_extricate_if (self, 0);
 463           __pthread_unlock (&rwlock->__rw_lock);
 464           return 0;
 465         }
 466
 467       /* Suspend ourselves, then try again */
 468       enqueue (&rwlock->__rw_write_waiting, self);
 469       __pthread_unlock (&rwlock->__rw_lock);
 470       /* This is not a cancellation point */
 471       if (timedsuspend (self, abstime) == 0)
 472         {
 473           int was_on_queue;
 474
 475           __pthread_lock (&rwlock->__rw_lock, self);
 476           was_on_queue = remove_from_queue (&rwlock->__rw_write_waiting, self);
 477           __pthread_unlock (&rwlock->__rw_lock);
 478
 479           if (was_on_queue)
 480             {
 481               __pthread_set_own_extricate_if (self, 0);
 482               return ETIMEDOUT;
 483             }
 484
 485           /* Eat the outstanding restart() from the signaller */
 486           suspend (self);
 487         }
 488     }
 489 }
 490 strong_alias (__pthread_rwlock_timedwrlock, pthread_rwlock_timedwrlock)
 491
 492
 493 int
 494 __pthread_rwlock_trywrlock (pthread_rwlock_t *rwlock)
 495 {
 496   int result = EBUSY;
 497
 498   __pthread_lock (&rwlock->__rw_lock, NULL);
 499   if (rwlock->__rw_readers == 0 && rwlock->__rw_writer == NULL)
 500     {
 501       rwlock->__rw_writer = thread_self ();
 502       result = 0;
 503     }
 504   __pthread_unlock (&rwlock->__rw_lock);
 505
 506   return result;
 507 }
 508 strong_alias (__pthread_rwlock_trywrlock, pthread_rwlock_trywrlock)
 509
 510
 511 int
 512 __pthread_rwlock_unlock (pthread_rwlock_t *rwlock)
 513 {
 514   pthread_descr torestart;
 515   pthread_descr th;
 516
 517   __pthread_lock (&rwlock->__rw_lock, NULL);
 518   if (rwlock->__rw_writer != NULL)
 519     {
 520       /* Unlocking a write lock.  */
 521       if (rwlock->__rw_writer != thread_self ())
 522         {
 523           __pthread_unlock (&rwlock->__rw_lock);
 524           return EPERM;
 525         }
 526       rwlock->__rw_writer = NULL;
 527
 528       if ((rwlock->__rw_kind == PTHREAD_RWLOCK_PREFER_READER_NP
 529            && !queue_is_empty(&rwlock->__rw_read_waiting))
 530           || (th = dequeue(&rwlock->__rw_write_waiting)) == NULL)
 531         {
 532           /* Restart all waiting readers.  */
 533           torestart = rwlock->__rw_read_waiting;
 534           rwlock->__rw_read_waiting = NULL;
 535           __pthread_unlock (&rwlock->__rw_lock);
 536           while ((th = dequeue (&torestart)) != NULL)
 537             restart (th);
 538         }
 539       else
 540         {
 541           /* Restart one waiting writer.  */
 542           __pthread_unlock (&rwlock->__rw_lock);
 543           restart (th);
 544         }
 545     }
 546   else
 547     {
 548       /* Unlocking a read lock.  */
 549       if (rwlock->__rw_readers == 0)
 550         {
 551           __pthread_unlock (&rwlock->__rw_lock);
 552           return EPERM;
 553         }
 554
 555       --rwlock->__rw_readers;
 556       if (rwlock->__rw_readers == 0)
 557         /* Restart one waiting writer, if any.  */
 558         th = dequeue (&rwlock->__rw_write_waiting);
 559       else
 560         th = NULL;
 561
 562       __pthread_unlock (&rwlock->__rw_lock);
 563       if (th != NULL)
 564         restart (th);
 565
 566       /* Recursive lock fixup */
 567
 568       if (rwlock->__rw_kind == PTHREAD_RWLOCK_PREFER_WRITER_NP)
 569         {
 570           pthread_descr self = thread_self();
 571           pthread_readlock_info *victim = rwlock_remove_from_list(self, rwlock);
 572
 573           if (victim != NULL)
 574             {
 575               if (victim->pr_lock_count == 0)
 576                 {
 577                   victim->pr_next = THREAD_GETMEM (self, p_readlock_free);
 578                   THREAD_SETMEM (self, p_readlock_free, victim);
 579                 }
 580             }
 581           else
 582             {
 583               int val = THREAD_GETMEM (self, p_untracked_readlock_count);
 584               if (val > 0)
 585                 THREAD_SETMEM (self, p_untracked_readlock_count, val - 1);
 586             }
 587         }
 588     }
 589
 590   return 0;
 591 }
 592 strong_alias (__pthread_rwlock_unlock, pthread_rwlock_unlock)
 593
 594
 595
 596 int
 597 pthread_rwlockattr_init (pthread_rwlockattr_t *attr)
 598 {
 599   attr->__lockkind = 0;
 600   attr->__pshared = PTHREAD_PROCESS_PRIVATE;
 601
 602   return 0;
 603 }
 604
 605
 606 int
 607 __pthread_rwlockattr_destroy (pthread_rwlockattr_t *attr)
 608 {
 609   return 0;
 610 }
 611 strong_alias (__pthread_rwlockattr_destroy, pthread_rwlockattr_destroy)
 612
 613
 614 int
 615 pthread_rwlockattr_getpshared (const pthread_rwlockattr_t *attr, int *pshared)
 616 {
 617   *pshared = attr->__pshared;
 618   return 0;
 619 }
 620
 621
 622 int
 623 pthread_rwlockattr_setpshared (pthread_rwlockattr_t *attr, int pshared)
 624 {
 625   if (pshared != PTHREAD_PROCESS_PRIVATE && pshared != PTHREAD_PROCESS_SHARED)
 626     return EINVAL;
 627
 628   /* For now it is not possible to shared a conditional variable.  */
 629   if (pshared != PTHREAD_PROCESS_PRIVATE)
 630     return ENOSYS;
 631
 632   attr->__pshared = pshared;
 633
 634   return 0;
 635 }
 636
 637
 638 int
 639 pthread_rwlockattr_getkind_np (const pthread_rwlockattr_t *attr, int *pref)
 640 {
 641   *pref = attr->__lockkind;
 642   return 0;
 643 }
 644
 645
 646 int
 647 pthread_rwlockattr_setkind_np (pthread_rwlockattr_t *attr, int pref)
 648 {
 649   if (pref != PTHREAD_RWLOCK_PREFER_READER_NP
 650       && pref != PTHREAD_RWLOCK_PREFER_WRITER_NP
 651       && pref != PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP
 652       && pref != PTHREAD_RWLOCK_DEFAULT_NP)
 653     return EINVAL;
 654
 655   attr->__lockkind = pref;
 656
 657   return 0;
 658 }