libpthread/linuxthreads/rwlock.c

   1 /* Read-write lock implementation.
   2    Copyright (C) 1998 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    see <http://www.gnu.org/licenses/>.  */
  20
  21 #include <errno.h>
  22 #include <pthread.h>
  23 #include <stdlib.h>
  24 #include "internals.h"
  25 #include "queue.h"
  26 #include "spinlock.h"
  27 #include "restart.h"
  28
  29 /*
  30  * Check whether the calling thread already owns one or more read locks on the
  31  * specified lock. If so, return a pointer to the read lock info structure
  32  * corresponding to that lock.
  33  */
  34
  35 static pthread_readlock_info *
  36 rwlock_is_in_list(pthread_descr self, pthread_rwlock_t *rwlock)
  37 {
  38   pthread_readlock_info *info;
  39
  40   for (info = self->p_readlock_list; info != NULL; info = info->pr_next)
  41     {
  42       if (info->pr_lock == rwlock)
  43         return info;
  44     }
  45
  46   return NULL;
  47 }
  48
  49 /*
  50  * Add a new lock to the thread's list of locks for which it has a read lock.
  51  * A new info node must be allocated for this, which is taken from the thread's
  52  * free list, or by calling malloc. If malloc fails, a null pointer is
  53  * returned. Otherwise the lock info structure is initialized and pushed
  54  * onto the thread's list.
  55  */
  56
  57 static pthread_readlock_info *
  58 rwlock_add_to_list(pthread_descr self, pthread_rwlock_t *rwlock)
  59 {
  60   pthread_readlock_info *info = self->p_readlock_free;
  61
  62   if (info != NULL)
  63     self->p_readlock_free = info->pr_next;
  64   else
  65     info = malloc(sizeof *info);
  66
  67   if (info == NULL)
  68     return NULL;
  69
  70   info->pr_lock_count = 1;
  71   info->pr_lock = rwlock;
  72   info->pr_next = self->p_readlock_list;
  73   self->p_readlock_list = info;
  74
  75   return info;
  76 }
  77
  78 /*
  79  * If the thread owns a read lock over the given pthread_rwlock_t,
  80  * and this read lock is tracked in the thread's lock list,
  81  * this function returns a pointer to the info node in that list.
  82  * It also decrements the lock count within that node, and if
  83  * it reaches zero, it removes the node from the list.
  84  * If nothing is found, it returns a null pointer.
  85  */
  86
  87 static pthread_readlock_info *
  88 rwlock_remove_from_list(pthread_descr self, pthread_rwlock_t *rwlock)
  89 {
  90   pthread_readlock_info **pinfo;
  91
  92   for (pinfo = &self->p_readlock_list; *pinfo != NULL; pinfo = &(*pinfo)->pr_next)
  93     {
  94       if ((*pinfo)->pr_lock == rwlock)
  95         {
  96           pthread_readlock_info *info = *pinfo;
  97           if (--info->pr_lock_count == 0)
  98             *pinfo = info->pr_next;
  99           return info;
 100         }
 101     }
 102
 103   return NULL;
 104 }
 105
 106 /*
 107  * This function checks whether the conditions are right to place a read lock.
 108  * It returns 1 if so, otherwise zero. The rwlock's internal lock must be
 109  * locked upon entry.
 110  */
 111
 112 static int
 113 rwlock_can_rdlock(pthread_rwlock_t *rwlock, int have_lock_already)
 114 {
 115   /* Can't readlock; it is write locked. */
 116   if (rwlock->__rw_writer != NULL)
 117     return 0;
 118
 119   /* Lock prefers readers; get it. */
 120   if (rwlock->__rw_kind == PTHREAD_RWLOCK_PREFER_READER_NP)
 121     return 1;
 122
 123   /* Lock prefers writers, but none are waiting. */
 124   if (queue_is_empty(&rwlock->__rw_write_waiting))
 125     return 1;
 126
 127   /* Writers are waiting, but this thread already has a read lock */
 128   if (have_lock_already)
 129     return 1;
 130
 131   /* Writers are waiting, and this is a new lock */
 132   return 0;
 133 }
 134
 135 /*
 136  * This function helps support brain-damaged recursive read locking
 137  * semantics required by Unix 98, while maintaining write priority.
 138  * This basically determines whether this thread already holds a read lock
 139  * already. It returns 1 if so, otherwise it returns 0.
 140  *
 141  * If the thread has any ``untracked read locks'' then it just assumes
 142  * that this lock is among them, just to be safe, and returns 1.
 143  *
 144  * Also, if it finds the thread's lock in the list, it sets the pointer
 145  * referenced by pexisting to refer to the list entry.
 146  *
 147  * If the thread has no untracked locks, and the lock is not found
 148  * in its list, then it is added to the list. If this fails,
 149  * then *pout_of_mem is set to 1.
 150  */
 151
 152 static int
 153 rwlock_have_already(pthread_descr *pself, pthread_rwlock_t *rwlock,
 154     pthread_readlock_info **pexisting, int *pout_of_mem)
 155 {
 156   pthread_readlock_info *existing = NULL;
 157   int out_of_mem = 0, have_lock_already = 0;
 158   pthread_descr self = *pself;
 159
 160   if (rwlock->__rw_kind == PTHREAD_RWLOCK_PREFER_WRITER_NP)
 161     {
 162       if (!self)
 163         self = thread_self();
 164
 165       existing = rwlock_is_in_list(self, rwlock);
 166
 167       if (existing != NULL || self->p_untracked_readlock_count > 0)
 168         have_lock_already = 1;
 169       else
 170         {
 171           existing = rwlock_add_to_list(self, rwlock);
 172           if (existing == NULL)
 173             out_of_mem = 1;
 174         }
 175     }
 176
 177   *pout_of_mem = out_of_mem;
 178   *pexisting = existing;
 179   *pself = self;
 180
 181   return have_lock_already;
 182 }
 183
 184 int
 185 pthread_rwlock_init (pthread_rwlock_t *rwlock,
 186                      const pthread_rwlockattr_t *attr)
 187 {
 188   __pthread_init_lock(&rwlock->__rw_lock);
 189   rwlock->__rw_readers = 0;
 190   rwlock->__rw_writer = NULL;
 191   rwlock->__rw_read_waiting = NULL;
 192   rwlock->__rw_write_waiting = NULL;
 193
 194   if (attr == NULL)
 195     {
 196       rwlock->__rw_kind = PTHREAD_RWLOCK_DEFAULT_NP;
 197       rwlock->__rw_pshared = PTHREAD_PROCESS_PRIVATE;
 198     }
 199   else
 200     {
 201       rwlock->__rw_kind = attr->__lockkind;
 202       rwlock->__rw_pshared = attr->__pshared;
 203     }
 204
 205   return 0;
 206 }
 207
 208
 209 int
 210 pthread_rwlock_destroy (pthread_rwlock_t *rwlock)
 211 {
 212   int readers;
 213   _pthread_descr writer;
 214
 215   __pthread_lock (&rwlock->__rw_lock, NULL);
 216   readers = rwlock->__rw_readers;
 217   writer = rwlock->__rw_writer;
 218   __pthread_unlock (&rwlock->__rw_lock);
 219
 220   if (readers > 0 || writer != NULL)
 221     return EBUSY;
 222
 223   return 0;
 224 }
 225
 226 int
 227 pthread_rwlock_rdlock (pthread_rwlock_t *rwlock)
 228 {
 229   pthread_descr self = NULL;
 230   pthread_readlock_info *existing;
 231   int out_of_mem, have_lock_already;
 232
 233   have_lock_already = rwlock_have_already(&self, rwlock,
 234       &existing, &out_of_mem);
 235
 236   for (;;)
 237     {
 238       if (self == NULL)
 239         self = thread_self ();
 240
 241       __pthread_lock (&rwlock->__rw_lock, self);
 242
 243       if (rwlock_can_rdlock(rwlock, have_lock_already))
 244         break;
 245
 246       enqueue (&rwlock->__rw_read_waiting, self);
 247       __pthread_unlock (&rwlock->__rw_lock);
 248       suspend (self); /* This is not a cancellation point */
 249     }
 250
 251   ++rwlock->__rw_readers;
 252   __pthread_unlock (&rwlock->__rw_lock);
 253
 254   if (have_lock_already || out_of_mem)
 255     {
 256       if (existing != NULL)
 257         existing->pr_lock_count++;
 258       else
 259         self->p_untracked_readlock_count++;
 260     }
 261
 262   return 0;
 263 }
 264
 265 int
 266 pthread_rwlock_tryrdlock (pthread_rwlock_t *rwlock)
 267 {
 268   pthread_descr self = thread_self();
 269   pthread_readlock_info *existing;
 270   int out_of_mem, have_lock_already;
 271   int retval = EBUSY;
 272
 273   have_lock_already = rwlock_have_already(&self, rwlock,
 274       &existing, &out_of_mem);
 275
 276   __pthread_lock (&rwlock->__rw_lock, self);
 277
 278   /* 0 is passed to here instead of have_lock_already.
 279      This is to meet Single Unix Spec requirements:
 280      if writers are waiting, pthread_rwlock_tryrdlock
 281      does not acquire a read lock, even if the caller has
 282      one or more read locks already. */
 283
 284   if (rwlock_can_rdlock(rwlock, 0))
 285     {
 286       ++rwlock->__rw_readers;
 287       retval = 0;
 288     }
 289
 290   __pthread_unlock (&rwlock->__rw_lock);
 291
 292   if (retval == 0)
 293     {
 294       if (have_lock_already || out_of_mem)
 295         {
 296           if (existing != NULL)
 297             existing->pr_lock_count++;
 298           else
 299             self->p_untracked_readlock_count++;
 300         }
 301     }
 302
 303   return retval;
 304 }
 305
 306
 307 int
 308 pthread_rwlock_wrlock (pthread_rwlock_t *rwlock)
 309 {
 310   pthread_descr self = thread_self ();
 311
 312   while(1)
 313     {
 314       __pthread_lock (&rwlock->__rw_lock, self);
 315       if (rwlock->__rw_readers == 0 && rwlock->__rw_writer == NULL)
 316         {
 317           rwlock->__rw_writer = self;
 318           __pthread_unlock (&rwlock->__rw_lock);
 319           return 0;
 320         }
 321
 322       /* Suspend ourselves, then try again */
 323       enqueue (&rwlock->__rw_write_waiting, self);
 324       __pthread_unlock (&rwlock->__rw_lock);
 325       suspend (self); /* This is not a cancellation point */
 326     }
 327 }
 328
 329
 330 int
 331 pthread_rwlock_trywrlock (pthread_rwlock_t *rwlock)
 332 {
 333   int result = EBUSY;
 334
 335   __pthread_lock (&rwlock->__rw_lock, NULL);
 336   if (rwlock->__rw_readers == 0 && rwlock->__rw_writer == NULL)
 337     {
 338       rwlock->__rw_writer = thread_self ();
 339       result = 0;
 340     }
 341   __pthread_unlock (&rwlock->__rw_lock);
 342
 343   return result;
 344 }
 345
 346
 347 int
 348 pthread_rwlock_unlock (pthread_rwlock_t *rwlock)
 349 {
 350   pthread_descr torestart;
 351   pthread_descr th;
 352
 353   __pthread_lock (&rwlock->__rw_lock, NULL);
 354   if (rwlock->__rw_writer != NULL)
 355     {
 356       /* Unlocking a write lock.  */
 357       if (rwlock->__rw_writer != thread_self ())
 358         {
 359           __pthread_unlock (&rwlock->__rw_lock);
 360           return EPERM;
 361         }
 362       rwlock->__rw_writer = NULL;
 363
 364       if (rwlock->__rw_kind == PTHREAD_RWLOCK_PREFER_READER_NP
 365           || (th = dequeue (&rwlock->__rw_write_waiting)) == NULL)
 366         {
 367           /* Restart all waiting readers.  */
 368           torestart = rwlock->__rw_read_waiting;
 369           rwlock->__rw_read_waiting = NULL;
 370           __pthread_unlock (&rwlock->__rw_lock);
 371           while ((th = dequeue (&torestart)) != NULL)
 372             restart (th);
 373         }
 374       else
 375         {
 376           /* Restart one waiting writer.  */
 377           __pthread_unlock (&rwlock->__rw_lock);
 378           restart (th);
 379         }
 380     }
 381   else
 382     {
 383       /* Unlocking a read lock.  */
 384       if (rwlock->__rw_readers == 0)
 385         {
 386           __pthread_unlock (&rwlock->__rw_lock);
 387           return EPERM;
 388         }
 389
 390       --rwlock->__rw_readers;
 391       if (rwlock->__rw_readers == 0)
 392         /* Restart one waiting writer, if any.  */
 393         th = dequeue (&rwlock->__rw_write_waiting);
 394       else
 395         th = NULL;
 396
 397       __pthread_unlock (&rwlock->__rw_lock);
 398       if (th != NULL)
 399         restart (th);
 400
 401       /* Recursive lock fixup */
 402
 403       if (rwlock->__rw_kind == PTHREAD_RWLOCK_PREFER_WRITER_NP)
 404         {
 405           pthread_descr self = thread_self();
 406           pthread_readlock_info *victim = rwlock_remove_from_list(self, rwlock);
 407
 408           if (victim != NULL)
 409             {
 410               if (victim->pr_lock_count == 0)
 411                 {
 412                   victim->pr_next = self->p_readlock_free;
 413                   self->p_readlock_free = victim;
 414                 }
 415             }
 416           else
 417             {
 418               if (self->p_untracked_readlock_count > 0)
 419                 self->p_untracked_readlock_count--;
 420             }
 421         }
 422     }
 423
 424   return 0;
 425 }
 426
 427
 428
 429 int
 430 pthread_rwlockattr_init (pthread_rwlockattr_t *attr)
 431 {
 432   attr->__lockkind = 0;
 433   attr->__pshared = 0;
 434
 435   return 0;
 436 }
 437
 438
 439 int
 440 pthread_rwlockattr_destroy (pthread_rwlockattr_t *attr attribute_unused)
 441 {
 442   return 0;
 443 }
 444
 445
 446 int
 447 pthread_rwlockattr_getpshared (const pthread_rwlockattr_t *attr, int *pshared)
 448 {
 449   *pshared = attr->__pshared;
 450   return 0;
 451 }
 452
 453
 454 int
 455 pthread_rwlockattr_setpshared (pthread_rwlockattr_t *attr, int pshared)
 456 {
 457   if (pshared != PTHREAD_PROCESS_PRIVATE && pshared != PTHREAD_PROCESS_SHARED)
 458     return EINVAL;
 459
 460   attr->__pshared = pshared;
 461
 462   return 0;
 463 }
 464
 465
 466 int
 467 pthread_rwlockattr_getkind_np (const pthread_rwlockattr_t *attr, int *pref)
 468 {
 469   *pref = attr->__lockkind;
 470   return 0;
 471 }
 472
 473
 474 int
 475 pthread_rwlockattr_setkind_np (pthread_rwlockattr_t *attr, int pref)
 476 {
 477   if (pref != PTHREAD_RWLOCK_PREFER_READER_NP
 478       && pref != PTHREAD_RWLOCK_PREFER_WRITER_NP
 479       && pref != PTHREAD_RWLOCK_DEFAULT_NP)
 480     return EINVAL;
 481
 482   attr->__lockkind = pref;
 483
 484   return 0;
 485 }