external/bsd/openldap/dist/libraries/libldap_r/rdwr.c

   1 /* $OpenLDAP: pkg/ldap/libraries/libldap_r/rdwr.c,v 1.28.2.3 2008/02/11 23:26:41 kurt Exp $ */
   2 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
   3  *
   4  * Copyright 1998-2008 The OpenLDAP Foundation.
   5  * All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted only as authorized by the OpenLDAP
   9  * Public License.
  10  *
  11  * A copy of this license is available in file LICENSE in the
  12  * top-level directory of the distribution or, alternatively, at
  13  * <http://www.OpenLDAP.org/license.html>.
  14  */
  15 /* This work was initially developed by Kurt D. Zeilenga for inclusion
  16  * in OpenLDAP Software.  Additional significant contributors include:
  17  *     Stuart Lynne
  18  */
  19
  20 /*
  21  * This is an improved implementation of Reader/Writer locks does
  22  * not protect writers from starvation.  That is, if a writer is
  23  * currently waiting on a reader, any new reader will get
  24  * the lock before the writer.
  25  *
  26  * Does not support cancellation nor does any status checking.
  27  */
  28 /* Adapted from publically available examples for:
  29  *      "Programming with Posix Threads"
  30  *              by David R Butenhof, Addison-Wesley
  31  *              http://cseng.aw.com/bookpage.taf?ISBN=0-201-63392-2
  32  */
  33
  34 #include "portable.h"
  35
  36 #include <ac/stdlib.h>
  37
  38 #include <ac/errno.h>
  39 #include <ac/string.h>
  40 #include <ac/time.h>
  41
  42 #include "ldap-int.h"
  43 #include "ldap_pvt_thread.h" /* Get the thread interface */
  44 #define LDAP_THREAD_RDWR_IMPLEMENTATION
  45 #include "ldap_thr_debug.h"  /* May rename the symbols defined below */
  46
  47 /*
  48  * implementations that provide their own compatible
  49  * reader/writer locks define LDAP_THREAD_HAVE_RDWR
  50  * in ldap_pvt_thread.h
  51  */
  52 #ifndef LDAP_THREAD_HAVE_RDWR
  53
  54 struct ldap_int_thread_rdwr_s {
  55         ldap_pvt_thread_mutex_t ltrw_mutex;
  56         ldap_pvt_thread_cond_t ltrw_read;       /* wait for read */
  57         ldap_pvt_thread_cond_t ltrw_write;      /* wait for write */
  58         int ltrw_valid;
  59 #define LDAP_PVT_THREAD_RDWR_VALID 0x0bad
  60         int ltrw_r_active;
  61         int ltrw_w_active;
  62         int ltrw_r_wait;
  63         int ltrw_w_wait;
  64 #ifdef LDAP_RDWR_DEBUG
  65         /* keep track of who has these locks */
  66 #define MAX_READERS     32
  67         int ltrw_more_readers; /* Set if ltrw_readers[] is incomplete */
  68         ldap_pvt_thread_t ltrw_readers[MAX_READERS];
  69         ldap_pvt_thread_t ltrw_writer;
  70 #endif
  71 };
  72
  73 int
  74 ldap_pvt_thread_rdwr_init( ldap_pvt_thread_rdwr_t *rwlock )
  75 {
  76         struct ldap_int_thread_rdwr_s *rw;
  77
  78         assert( rwlock != NULL );
  79
  80         rw = (struct ldap_int_thread_rdwr_s *) LDAP_CALLOC( 1,
  81                 sizeof( struct ldap_int_thread_rdwr_s ) );
  82         if ( !rw )
  83                 return LDAP_NO_MEMORY;
  84
  85         /* we should check return results */
  86         ldap_pvt_thread_mutex_init( &rw->ltrw_mutex );
  87         ldap_pvt_thread_cond_init( &rw->ltrw_read );
  88         ldap_pvt_thread_cond_init( &rw->ltrw_write );
  89
  90         rw->ltrw_valid = LDAP_PVT_THREAD_RDWR_VALID;
  91
  92         *rwlock = rw;
  93         return 0;
  94 }
  95
  96 int
  97 ldap_pvt_thread_rdwr_destroy( ldap_pvt_thread_rdwr_t *rwlock )
  98 {
  99         struct ldap_int_thread_rdwr_s *rw;
 100
 101         assert( rwlock != NULL );
 102         rw = *rwlock;
 103
 104         assert( rw != NULL );
 105         assert( rw->ltrw_valid == LDAP_PVT_THREAD_RDWR_VALID );
 106
 107         if( rw->ltrw_valid != LDAP_PVT_THREAD_RDWR_VALID )
 108                 return LDAP_PVT_THREAD_EINVAL;
 109
 110         ldap_pvt_thread_mutex_lock( &rw->ltrw_mutex );
 111
 112         assert( rw->ltrw_w_active >= 0 );
 113         assert( rw->ltrw_w_wait >= 0 );
 114         assert( rw->ltrw_r_active >= 0 );
 115         assert( rw->ltrw_r_wait >= 0 );
 116
 117         /* active threads? */
 118         if( rw->ltrw_r_active > 0 || rw->ltrw_w_active > 0) {
 119                 ldap_pvt_thread_mutex_unlock( &rw->ltrw_mutex );
 120                 return LDAP_PVT_THREAD_EBUSY;
 121         }
 122
 123         /* waiting threads? */
 124         if( rw->ltrw_r_wait > 0 || rw->ltrw_w_wait > 0) {
 125                 ldap_pvt_thread_mutex_unlock( &rw->ltrw_mutex );
 126                 return LDAP_PVT_THREAD_EBUSY;
 127         }
 128
 129         rw->ltrw_valid = 0;
 130
 131         ldap_pvt_thread_mutex_unlock( &rw->ltrw_mutex );
 132
 133         ldap_pvt_thread_mutex_destroy( &rw->ltrw_mutex );
 134         ldap_pvt_thread_cond_destroy( &rw->ltrw_read );
 135         ldap_pvt_thread_cond_destroy( &rw->ltrw_write );
 136
 137         LDAP_FREE(rw);
 138         *rwlock = NULL;
 139         return 0;
 140 }
 141
 142 int ldap_pvt_thread_rdwr_rlock( ldap_pvt_thread_rdwr_t *rwlock )
 143 {
 144         struct ldap_int_thread_rdwr_s *rw;
 145
 146         assert( rwlock != NULL );
 147         rw = *rwlock;
 148
 149         assert( rw != NULL );
 150         assert( rw->ltrw_valid == LDAP_PVT_THREAD_RDWR_VALID );
 151
 152         if( rw->ltrw_valid != LDAP_PVT_THREAD_RDWR_VALID )
 153                 return LDAP_PVT_THREAD_EINVAL;
 154
 155         ldap_pvt_thread_mutex_lock( &rw->ltrw_mutex );
 156
 157         assert( rw->ltrw_w_active >= 0 );
 158         assert( rw->ltrw_w_wait >= 0 );
 159         assert( rw->ltrw_r_active >= 0 );
 160         assert( rw->ltrw_r_wait >= 0 );
 161
 162         if( rw->ltrw_w_active > 0 ) {
 163                 /* writer is active */
 164
 165                 rw->ltrw_r_wait++;
 166
 167                 do {
 168                         ldap_pvt_thread_cond_wait(
 169                                 &rw->ltrw_read, &rw->ltrw_mutex );
 170                 } while( rw->ltrw_w_active > 0 );
 171
 172                 rw->ltrw_r_wait--;
 173                 assert( rw->ltrw_r_wait >= 0 );
 174         }
 175
 176 #ifdef LDAP_RDWR_DEBUG
 177         if( rw->ltrw_r_active < MAX_READERS )
 178                 rw->ltrw_readers[rw->ltrw_r_active] = ldap_pvt_thread_self();
 179         else
 180                 rw->ltrw_more_readers = 1;
 181 #endif
 182         rw->ltrw_r_active++;
 183
 184
 185         ldap_pvt_thread_mutex_unlock( &rw->ltrw_mutex );
 186
 187         return 0;
 188 }
 189
 190 int ldap_pvt_thread_rdwr_rtrylock( ldap_pvt_thread_rdwr_t *rwlock )
 191 {
 192         struct ldap_int_thread_rdwr_s *rw;
 193
 194         assert( rwlock != NULL );
 195         rw = *rwlock;
 196
 197         assert( rw != NULL );
 198         assert( rw->ltrw_valid == LDAP_PVT_THREAD_RDWR_VALID );
 199
 200         if( rw->ltrw_valid != LDAP_PVT_THREAD_RDWR_VALID )
 201                 return LDAP_PVT_THREAD_EINVAL;
 202
 203         ldap_pvt_thread_mutex_lock( &rw->ltrw_mutex );
 204
 205         assert( rw->ltrw_w_active >= 0 );
 206         assert( rw->ltrw_w_wait >= 0 );
 207         assert( rw->ltrw_r_active >= 0 );
 208         assert( rw->ltrw_r_wait >= 0 );
 209
 210         if( rw->ltrw_w_active > 0) {
 211                 ldap_pvt_thread_mutex_unlock( &rw->ltrw_mutex );
 212                 return LDAP_PVT_THREAD_EBUSY;
 213         }
 214
 215 #ifdef LDAP_RDWR_DEBUG
 216         if( rw->ltrw_r_active < MAX_READERS )
 217                 rw->ltrw_readers[rw->ltrw_r_active] = ldap_pvt_thread_self();
 218         else
 219                 rw->ltrw_more_readers = 1;
 220 #endif
 221         rw->ltrw_r_active++;
 222
 223         ldap_pvt_thread_mutex_unlock( &rw->ltrw_mutex );
 224
 225         return 0;
 226 }
 227
 228 int ldap_pvt_thread_rdwr_runlock( ldap_pvt_thread_rdwr_t *rwlock )
 229 {
 230         struct ldap_int_thread_rdwr_s *rw;
 231
 232         assert( rwlock != NULL );
 233         rw = *rwlock;
 234
 235         assert( rw != NULL );
 236         assert( rw->ltrw_valid == LDAP_PVT_THREAD_RDWR_VALID );
 237
 238         if( rw->ltrw_valid != LDAP_PVT_THREAD_RDWR_VALID )
 239                 return LDAP_PVT_THREAD_EINVAL;
 240
 241         ldap_pvt_thread_mutex_lock( &rw->ltrw_mutex );
 242
 243         rw->ltrw_r_active--;
 244 #ifdef LDAP_RDWR_DEBUG
 245         /* Remove us from the list of readers */
 246         {
 247                 ldap_pvt_thread_t self = ldap_pvt_thread_self();
 248                 int i, j;
 249                 for( i = j = rw->ltrw_r_active; i >= 0; i--) {
 250                         if (rw->ltrw_readers[i] == self) {
 251                                 rw->ltrw_readers[i] = rw->ltrw_readers[j];
 252                                 rw->ltrw_readers[j] = 0;
 253                                 break;
 254                         }
 255                 }
 256                 if( !rw->ltrw_more_readers )
 257                         assert( i >= 0 );
 258                 else if( j == 0 )
 259                         rw->ltrw_more_readers = 0;
 260         }
 261 #endif
 262
 263         assert( rw->ltrw_w_active >= 0 );
 264         assert( rw->ltrw_w_wait >= 0 );
 265         assert( rw->ltrw_r_active >= 0 );
 266         assert( rw->ltrw_r_wait >= 0 );
 267
 268         if (rw->ltrw_r_active == 0 && rw->ltrw_w_wait > 0 ) {
 269                 ldap_pvt_thread_cond_signal( &rw->ltrw_write );
 270         }
 271
 272         ldap_pvt_thread_mutex_unlock( &rw->ltrw_mutex );
 273
 274         return 0;
 275 }
 276
 277 int ldap_pvt_thread_rdwr_wlock( ldap_pvt_thread_rdwr_t *rwlock )
 278 {
 279         struct ldap_int_thread_rdwr_s *rw;
 280
 281         assert( rwlock != NULL );
 282         rw = *rwlock;
 283
 284         assert( rw != NULL );
 285         assert( rw->ltrw_valid == LDAP_PVT_THREAD_RDWR_VALID );
 286
 287         if( rw->ltrw_valid != LDAP_PVT_THREAD_RDWR_VALID )
 288                 return LDAP_PVT_THREAD_EINVAL;
 289
 290         ldap_pvt_thread_mutex_lock( &rw->ltrw_mutex );
 291
 292         assert( rw->ltrw_w_active >= 0 );
 293         assert( rw->ltrw_w_wait >= 0 );
 294         assert( rw->ltrw_r_active >= 0 );
 295         assert( rw->ltrw_r_wait >= 0 );
 296
 297         if ( rw->ltrw_w_active > 0 || rw->ltrw_r_active > 0 ) {
 298                 rw->ltrw_w_wait++;
 299
 300                 do {
 301                         ldap_pvt_thread_cond_wait(
 302                                 &rw->ltrw_write, &rw->ltrw_mutex );
 303                 } while ( rw->ltrw_w_active > 0 || rw->ltrw_r_active > 0 );
 304
 305                 rw->ltrw_w_wait--;
 306                 assert( rw->ltrw_w_wait >= 0 );
 307         }
 308
 309 #ifdef LDAP_RDWR_DEBUG
 310         rw->ltrw_writer = ldap_pvt_thread_self();
 311 #endif
 312         rw->ltrw_w_active++;
 313
 314         ldap_pvt_thread_mutex_unlock( &rw->ltrw_mutex );
 315
 316         return 0;
 317 }
 318
 319 int ldap_pvt_thread_rdwr_wtrylock( ldap_pvt_thread_rdwr_t *rwlock )
 320 {
 321         struct ldap_int_thread_rdwr_s *rw;
 322
 323         assert( rwlock != NULL );
 324         rw = *rwlock;
 325
 326         assert( rw != NULL );
 327         assert( rw->ltrw_valid == LDAP_PVT_THREAD_RDWR_VALID );
 328
 329         if( rw->ltrw_valid != LDAP_PVT_THREAD_RDWR_VALID )
 330                 return LDAP_PVT_THREAD_EINVAL;
 331
 332         ldap_pvt_thread_mutex_lock( &rw->ltrw_mutex );
 333
 334         assert( rw->ltrw_w_active >= 0 );
 335         assert( rw->ltrw_w_wait >= 0 );
 336         assert( rw->ltrw_r_active >= 0 );
 337         assert( rw->ltrw_r_wait >= 0 );
 338
 339         if ( rw->ltrw_w_active > 0 || rw->ltrw_r_active > 0 ) {
 340                 ldap_pvt_thread_mutex_unlock( &rw->ltrw_mutex );
 341                 return LDAP_PVT_THREAD_EBUSY;
 342         }
 343
 344 #ifdef LDAP_RDWR_DEBUG
 345         rw->ltrw_writer = ldap_pvt_thread_self();
 346 #endif
 347         rw->ltrw_w_active++;
 348
 349         ldap_pvt_thread_mutex_unlock( &rw->ltrw_mutex );
 350
 351         return 0;
 352 }
 353
 354 int ldap_pvt_thread_rdwr_wunlock( ldap_pvt_thread_rdwr_t *rwlock )
 355 {
 356         struct ldap_int_thread_rdwr_s *rw;
 357
 358         assert( rwlock != NULL );
 359         rw = *rwlock;
 360
 361         assert( rw != NULL );
 362         assert( rw->ltrw_valid == LDAP_PVT_THREAD_RDWR_VALID );
 363
 364         if( rw->ltrw_valid != LDAP_PVT_THREAD_RDWR_VALID )
 365                 return LDAP_PVT_THREAD_EINVAL;
 366
 367         ldap_pvt_thread_mutex_lock( &rw->ltrw_mutex );
 368
 369         rw->ltrw_w_active--;
 370
 371         assert( rw->ltrw_w_active >= 0 );
 372         assert( rw->ltrw_w_wait >= 0 );
 373         assert( rw->ltrw_r_active >= 0 );
 374         assert( rw->ltrw_r_wait >= 0 );
 375
 376         if (rw->ltrw_r_wait > 0) {
 377                 ldap_pvt_thread_cond_broadcast( &rw->ltrw_read );
 378
 379         } else if (rw->ltrw_w_wait > 0) {
 380                 ldap_pvt_thread_cond_signal( &rw->ltrw_write );
 381         }
 382
 383 #ifdef LDAP_RDWR_DEBUG
 384         assert( rw->ltrw_writer == ldap_pvt_thread_self() );
 385         rw->ltrw_writer = 0;
 386 #endif
 387         ldap_pvt_thread_mutex_unlock( &rw->ltrw_mutex );
 388
 389         return 0;
 390 }
 391
 392 #ifdef LDAP_RDWR_DEBUG
 393
 394 /* just for testing,
 395  * return 0 if false, suitable for assert(ldap_pvt_thread_rdwr_Xchk(rdwr))
 396  *
 397  * Currently they don't check if the calling thread is the one
 398  * that has the lock, just that there is a reader or writer.
 399  *
 400  * Basically sufficent for testing that places that should have
 401  * a lock are caught.
 402  */
 403
 404 int ldap_pvt_thread_rdwr_readers(ldap_pvt_thread_rdwr_t *rwlock)
 405 {
 406         struct ldap_int_thread_rdwr_s *rw;
 407
 408         assert( rwlock != NULL );
 409         rw = *rwlock;
 410
 411         assert( rw != NULL );
 412         assert( rw->ltrw_valid == LDAP_PVT_THREAD_RDWR_VALID );
 413         assert( rw->ltrw_w_active >= 0 );
 414         assert( rw->ltrw_w_wait >= 0 );
 415         assert( rw->ltrw_r_active >= 0 );
 416         assert( rw->ltrw_r_wait >= 0 );
 417
 418         return( rw->ltrw_r_active );
 419 }
 420
 421 int ldap_pvt_thread_rdwr_writers(ldap_pvt_thread_rdwr_t *rwlock)
 422 {
 423         struct ldap_int_thread_rdwr_s *rw;
 424
 425         assert( rwlock != NULL );
 426         rw = *rwlock;
 427
 428         assert( rw != NULL );
 429         assert( rw->ltrw_valid == LDAP_PVT_THREAD_RDWR_VALID );
 430         assert( rw->ltrw_w_active >= 0 );
 431         assert( rw->ltrw_w_wait >= 0 );
 432         assert( rw->ltrw_r_active >= 0 );
 433         assert( rw->ltrw_r_wait >= 0 );
 434
 435         return( rw->ltrw_w_active );
 436 }
 437
 438 int ldap_pvt_thread_rdwr_active(ldap_pvt_thread_rdwr_t *rwlock)
 439 {
 440         struct ldap_int_thread_rdwr_s *rw;
 441
 442         assert( rwlock != NULL );
 443         rw = *rwlock;
 444
 445         assert( rw != NULL );
 446         assert( rw->ltrw_valid == LDAP_PVT_THREAD_RDWR_VALID );
 447         assert( rw->ltrw_w_active >= 0 );
 448         assert( rw->ltrw_w_wait >= 0 );
 449         assert( rw->ltrw_r_active >= 0 );
 450         assert( rw->ltrw_r_wait >= 0 );
 451
 452         return(ldap_pvt_thread_rdwr_readers(rwlock) +
 453                ldap_pvt_thread_rdwr_writers(rwlock));
 454 }
 455
 456 #endif /* LDAP_RDWR_DEBUG */
 457
 458 #endif /* LDAP_THREAD_HAVE_RDWR */