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