1 /* $NetBSD: pthread_rwlock.c,v 1.27 2008/02/10 18:50:55 ad Exp $ */ 2 3 /*- 4 * Copyright (c) 2002, 2006, 2007, 2008 The NetBSD Foundation, Inc. 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to The NetBSD Foundation 8 * by Nathan J. Williams, by Jason R. Thorpe, and by Andrew Doran. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 3. All advertising materials mentioning features or use of this software 19 * must display the following acknowledgement: 20 * This product includes software developed by the NetBSD 21 * Foundation, Inc. and its contributors. 22 * 4. Neither the name of The NetBSD Foundation nor the names of its 23 * contributors may be used to endorse or promote products derived 24 * from this software without specific prior written permission. 25 * 26 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 27 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 28 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 29 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 30 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 31 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 32 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 33 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 34 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 35 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 36 * POSSIBILITY OF SUCH DAMAGE. 37 */ 38 39 #include <sys/cdefs.h> 40 __RCSID("$NetBSD: pthread_rwlock.c,v 1.27 2008/02/10 18:50:55 ad Exp $"); 41 42 #include <errno.h> 43 #include <stddef.h> 44 45 #include "pthread.h" 46 #include "pthread_int.h" 47 48 #define _RW_LOCKED 0 49 #define _RW_WANT_WRITE 1 50 #define _RW_WANT_READ 2 51 52 static int pthread__rwlock_wrlock(pthread_rwlock_t *, const struct timespec *); 53 static int pthread__rwlock_rdlock(pthread_rwlock_t *, const struct timespec *); 54 static void pthread__rwlock_early(void *); 55 56 int _pthread_rwlock_held_np(pthread_rwlock_t *); 57 int _pthread_rwlock_rdheld_np(pthread_rwlock_t *); 58 int _pthread_rwlock_wrheld_np(pthread_rwlock_t *); 59 60 #ifndef lint 61 __weak_alias(pthread_rwlock_held_np,_pthread_rwlock_held_np); 62 __weak_alias(pthread_rwlock_rdheld_np,_pthread_rwlock_rdheld_np); 63 __weak_alias(pthread_rwlock_wrheld_np,_pthread_rwlock_wrheld_np); 64 #endif 65 66 __strong_alias(__libc_rwlock_init,pthread_rwlock_init) 67 __strong_alias(__libc_rwlock_rdlock,pthread_rwlock_rdlock) 68 __strong_alias(__libc_rwlock_wrlock,pthread_rwlock_wrlock) 69 __strong_alias(__libc_rwlock_tryrdlock,pthread_rwlock_tryrdlock) 70 __strong_alias(__libc_rwlock_trywrlock,pthread_rwlock_trywrlock) 71 __strong_alias(__libc_rwlock_unlock,pthread_rwlock_unlock) 72 __strong_alias(__libc_rwlock_destroy,pthread_rwlock_destroy) 73 74 static inline uintptr_t 75 rw_cas(pthread_rwlock_t *ptr, uintptr_t o, uintptr_t n) 76 { 77 78 return (uintptr_t)atomic_cas_ptr(&ptr->ptr_owner, (void *)o, 79 (void *)n); 80 } 81 82 int 83 pthread_rwlock_init(pthread_rwlock_t *ptr, 84 const pthread_rwlockattr_t *attr) 85 { 86 87 if (attr && (attr->ptra_magic != _PT_RWLOCKATTR_MAGIC)) 88 return EINVAL; 89 ptr->ptr_magic = _PT_RWLOCK_MAGIC; 90 pthread_lockinit(&ptr->ptr_interlock); 91 PTQ_INIT(&ptr->ptr_rblocked); 92 PTQ_INIT(&ptr->ptr_wblocked); 93 ptr->ptr_nreaders = 0; 94 ptr->ptr_owner = NULL; 95 96 return 0; 97 } 98 99 100 int 101 pthread_rwlock_destroy(pthread_rwlock_t *ptr) 102 { 103 104 if ((ptr->ptr_magic != _PT_RWLOCK_MAGIC) || 105 (!PTQ_EMPTY(&ptr->ptr_rblocked)) || 106 (!PTQ_EMPTY(&ptr->ptr_wblocked)) || 107 (ptr->ptr_nreaders != 0) || 108 (ptr->ptr_owner != NULL)) 109 return EINVAL; 110 ptr->ptr_magic = _PT_RWLOCK_DEAD; 111 112 return 0; 113 } 114 115 static int 116 pthread__rwlock_rdlock(pthread_rwlock_t *ptr, const struct timespec *ts) 117 { 118 uintptr_t owner, next; 119 pthread_t self; 120 int error; 121 122 self = pthread__self(); 123 124 #ifdef ERRORCHECK 125 if (ptr->ptr_magic != _PT_RWLOCK_MAGIC) 126 return EINVAL; 127 #endif 128 129 for (owner = (uintptr_t)ptr->ptr_owner;; owner = next) { 130 /* 131 * Read the lock owner field. If the need-to-wait 132 * indicator is clear, then try to acquire the lock. 133 */ 134 if ((owner & (RW_WRITE_LOCKED | RW_WRITE_WANTED)) == 0) { 135 next = rw_cas(ptr, owner, owner + RW_READ_INCR); 136 if (owner == next) { 137 /* Got it! */ 138 #ifndef PTHREAD__ATOMIC_IS_MEMBAR 139 membar_enter(); 140 #endif 141 return 0; 142 } 143 144 /* 145 * Didn't get it -- spin around again (we'll 146 * probably sleep on the next iteration). 147 */ 148 continue; 149 } 150 151 if ((owner & RW_THREAD) == (uintptr_t)self) 152 return EDEADLK; 153 154 /* 155 * Grab the interlock. Once we have that, we 156 * can adjust the waiter bits and sleep queue. 157 */ 158 pthread__spinlock(self, &ptr->ptr_interlock); 159 160 /* 161 * Mark the rwlock as having waiters. If the set fails, 162 * then we may not need to sleep and should spin again. 163 */ 164 next = rw_cas(ptr, owner, owner | RW_HAS_WAITERS); 165 if (owner != next) { 166 pthread__spinunlock(self, &ptr->ptr_interlock); 167 continue; 168 } 169 170 /* The waiters bit is set - it's safe to sleep. */ 171 PTQ_INSERT_HEAD(&ptr->ptr_rblocked, self, pt_sleep); 172 ptr->ptr_nreaders++; 173 self->pt_rwlocked = _RW_WANT_READ; 174 self->pt_sleeponq = 1; 175 self->pt_sleepobj = &ptr->ptr_rblocked; 176 self->pt_early = pthread__rwlock_early; 177 pthread__spinunlock(self, &ptr->ptr_interlock); 178 179 error = pthread__park(self, &ptr->ptr_interlock, 180 &ptr->ptr_rblocked, ts, 0, &ptr->ptr_rblocked); 181 182 /* Did we get the lock? */ 183 if (self->pt_rwlocked == _RW_LOCKED) { 184 #ifndef PTHREAD__ATOMIC_IS_MEMBAR 185 membar_enter(); 186 #endif 187 return 0; 188 } 189 if (error != 0) 190 return error; 191 192 pthread__errorfunc(__FILE__, __LINE__, __func__, 193 "direct handoff failure"); 194 } 195 } 196 197 198 int 199 pthread_rwlock_tryrdlock(pthread_rwlock_t *ptr) 200 { 201 uintptr_t owner, next; 202 203 #ifdef ERRORCHECK 204 if (ptr->ptr_magic != _PT_RWLOCK_MAGIC) 205 return EINVAL; 206 #endif 207 208 /* 209 * Don't get a readlock if there is a writer or if there are waiting 210 * writers; i.e. prefer writers to readers. This strategy is dictated 211 * by SUSv3. 212 */ 213 for (owner = (uintptr_t)ptr->ptr_owner;; owner = next) { 214 if ((owner & (RW_WRITE_LOCKED | RW_WRITE_WANTED)) != 0) 215 return EBUSY; 216 next = rw_cas(ptr, owner, owner + RW_READ_INCR); 217 if (owner == next) { 218 /* Got it! */ 219 #ifndef PTHREAD__ATOMIC_IS_MEMBAR 220 membar_enter(); 221 #endif 222 return 0; 223 } 224 } 225 } 226 227 static int 228 pthread__rwlock_wrlock(pthread_rwlock_t *ptr, const struct timespec *ts) 229 { 230 uintptr_t owner, next; 231 pthread_t self; 232 int error; 233 234 self = pthread__self(); 235 236 #ifdef ERRORCHECK 237 if (ptr->ptr_magic != _PT_RWLOCK_MAGIC) 238 return EINVAL; 239 #endif 240 241 for (owner = (uintptr_t)ptr->ptr_owner;; owner = next) { 242 /* 243 * Read the lock owner field. If the need-to-wait 244 * indicator is clear, then try to acquire the lock. 245 */ 246 if ((owner & RW_THREAD) == 0) { 247 next = rw_cas(ptr, owner, 248 (uintptr_t)self | RW_WRITE_LOCKED); 249 if (owner == next) { 250 /* Got it! */ 251 #ifndef PTHREAD__ATOMIC_IS_MEMBAR 252 membar_enter(); 253 #endif 254 return 0; 255 } 256 257 /* 258 * Didn't get it -- spin around again (we'll 259 * probably sleep on the next iteration). 260 */ 261 continue; 262 } 263 264 if ((owner & RW_THREAD) == (uintptr_t)self) 265 return EDEADLK; 266 267 /* 268 * Grab the interlock. Once we have that, we 269 * can adjust the waiter bits and sleep queue. 270 */ 271 pthread__spinlock(self, &ptr->ptr_interlock); 272 273 /* 274 * Mark the rwlock as having waiters. If the set fails, 275 * then we may not need to sleep and should spin again. 276 */ 277 next = rw_cas(ptr, owner, 278 owner | RW_HAS_WAITERS | RW_WRITE_WANTED); 279 if (owner != next) { 280 pthread__spinunlock(self, &ptr->ptr_interlock); 281 continue; 282 } 283 284 /* The waiters bit is set - it's safe to sleep. */ 285 PTQ_INSERT_TAIL(&ptr->ptr_wblocked, self, pt_sleep); 286 self->pt_rwlocked = _RW_WANT_WRITE; 287 self->pt_sleeponq = 1; 288 self->pt_sleepobj = &ptr->ptr_wblocked; 289 self->pt_early = pthread__rwlock_early; 290 pthread__spinunlock(self, &ptr->ptr_interlock); 291 292 error = pthread__park(self, &ptr->ptr_interlock, 293 &ptr->ptr_wblocked, ts, 0, &ptr->ptr_wblocked); 294 295 /* Did we get the lock? */ 296 if (self->pt_rwlocked == _RW_LOCKED) { 297 #ifndef PTHREAD__ATOMIC_IS_MEMBAR 298 membar_enter(); 299 #endif 300 return 0; 301 } 302 if (error != 0) 303 return error; 304 305 pthread__errorfunc(__FILE__, __LINE__, __func__, 306 "direct handoff failure"); 307 } 308 } 309 310 311 int 312 pthread_rwlock_trywrlock(pthread_rwlock_t *ptr) 313 { 314 uintptr_t owner, next; 315 pthread_t self; 316 317 #ifdef ERRORCHECK 318 if (ptr->ptr_magic != _PT_RWLOCK_MAGIC) 319 return EINVAL; 320 #endif 321 322 self = pthread__self(); 323 324 for (owner = (uintptr_t)ptr->ptr_owner;; owner = next) { 325 if (owner != 0) 326 return EBUSY; 327 next = rw_cas(ptr, owner, (uintptr_t)self | RW_WRITE_LOCKED); 328 if (owner == next) { 329 /* Got it! */ 330 #ifndef PTHREAD__ATOMIC_IS_MEMBAR 331 membar_enter(); 332 #endif 333 return 0; 334 } 335 } 336 } 337 338 int 339 pthread_rwlock_rdlock(pthread_rwlock_t *ptr) 340 { 341 342 return pthread__rwlock_rdlock(ptr, NULL); 343 } 344 345 int 346 pthread_rwlock_timedrdlock(pthread_rwlock_t *ptr, 347 const struct timespec *abs_timeout) 348 { 349 350 if (abs_timeout == NULL) 351 return EINVAL; 352 if ((abs_timeout->tv_nsec >= 1000000000) || 353 (abs_timeout->tv_nsec < 0) || 354 (abs_timeout->tv_sec < 0)) 355 return EINVAL; 356 357 return pthread__rwlock_rdlock(ptr, abs_timeout); 358 } 359 360 int 361 pthread_rwlock_wrlock(pthread_rwlock_t *ptr) 362 { 363 364 return pthread__rwlock_wrlock(ptr, NULL); 365 } 366 367 int 368 pthread_rwlock_timedwrlock(pthread_rwlock_t *ptr, 369 const struct timespec *abs_timeout) 370 { 371 372 if (abs_timeout == NULL) 373 return EINVAL; 374 if ((abs_timeout->tv_nsec >= 1000000000) || 375 (abs_timeout->tv_nsec < 0) || 376 (abs_timeout->tv_sec < 0)) 377 return EINVAL; 378 379 return pthread__rwlock_wrlock(ptr, abs_timeout); 380 } 381 382 383 int 384 pthread_rwlock_unlock(pthread_rwlock_t *ptr) 385 { 386 uintptr_t owner, decr, new, next; 387 pthread_t self, thread; 388 389 #ifdef ERRORCHECK 390 if ((ptr == NULL) || (ptr->ptr_magic != _PT_RWLOCK_MAGIC)) 391 return EINVAL; 392 #endif 393 394 #ifndef PTHREAD__ATOMIC_IS_MEMBAR 395 membar_exit(); 396 #endif 397 398 /* 399 * Since we used an add operation to set the required lock 400 * bits, we can use a subtract to clear them, which makes 401 * the read-release and write-release path similar. 402 */ 403 self = pthread__self(); 404 owner = (uintptr_t)ptr->ptr_owner; 405 if ((owner & RW_WRITE_LOCKED) != 0) { 406 decr = (uintptr_t)self | RW_WRITE_LOCKED; 407 if ((owner & RW_THREAD) != (uintptr_t)self) { 408 return EPERM; 409 } 410 } else { 411 decr = RW_READ_INCR; 412 if (owner == 0) { 413 return EPERM; 414 } 415 } 416 417 for (;; owner = next) { 418 /* 419 * Compute what we expect the new value of the lock to be. 420 * Only proceed to do direct handoff if there are waiters, 421 * and if the lock would become unowned. 422 */ 423 new = (owner - decr); 424 if ((new & (RW_THREAD | RW_HAS_WAITERS)) != RW_HAS_WAITERS) { 425 next = rw_cas(ptr, owner, new); 426 if (owner == next) { 427 /* Released! */ 428 return 0; 429 } 430 continue; 431 } 432 433 /* 434 * Grab the interlock. Once we have that, we can adjust 435 * the waiter bits. We must check to see if there are 436 * still waiters before proceeding. 437 */ 438 pthread__spinlock(self, &ptr->ptr_interlock); 439 owner = (uintptr_t)ptr->ptr_owner; 440 if ((owner & RW_HAS_WAITERS) == 0) { 441 pthread__spinunlock(self, &ptr->ptr_interlock); 442 next = owner; 443 continue; 444 } 445 446 /* 447 * Give the lock away. SUSv3 dictates that we must give 448 * preference to writers. 449 */ 450 if ((thread = PTQ_FIRST(&ptr->ptr_wblocked)) != NULL) { 451 new = (uintptr_t)thread | RW_WRITE_LOCKED; 452 453 if (PTQ_NEXT(thread, pt_sleep) != NULL) 454 new |= RW_HAS_WAITERS | RW_WRITE_WANTED; 455 else if (ptr->ptr_nreaders != 0) 456 new |= RW_HAS_WAITERS; 457 458 /* 459 * Set in the new value. The lock becomes owned 460 * by the writer that we are about to wake. 461 */ 462 (void)atomic_swap_ptr(&ptr->ptr_owner, (void *)new); 463 464 /* Wake the writer. */ 465 PTQ_REMOVE(&ptr->ptr_wblocked, thread, pt_sleep); 466 thread->pt_rwlocked = _RW_LOCKED; 467 pthread__unpark(self, &ptr->ptr_interlock, 468 &ptr->ptr_wblocked, thread); 469 } else { 470 new = 0; 471 PTQ_FOREACH(thread, &ptr->ptr_rblocked, pt_sleep) { 472 /* 473 * May have already been handed the lock, 474 * since pthread__unpark_all() can release 475 * our interlock before awakening all 476 * threads. 477 */ 478 if (thread->pt_sleepobj == NULL) 479 continue; 480 new += RW_READ_INCR; 481 thread->pt_rwlocked = _RW_LOCKED; 482 } 483 484 /* 485 * Set in the new value. The lock becomes owned 486 * by the readers that we are about to wake. 487 */ 488 (void)atomic_swap_ptr(&ptr->ptr_owner, (void *)new); 489 490 /* Wake up all sleeping readers. */ 491 ptr->ptr_nreaders = 0; 492 pthread__unpark_all(self, &ptr->ptr_interlock, 493 &ptr->ptr_rblocked); 494 } 495 496 return 0; 497 } 498 } 499 500 /* 501 * Called when a timedlock awakens early to adjust the waiter bits. 502 * The rwlock's interlock is held on entry, and the caller has been 503 * removed from the waiters lists. 504 */ 505 static void 506 pthread__rwlock_early(void *obj) 507 { 508 uintptr_t owner, set, new, next; 509 pthread_rwlock_t *ptr; 510 pthread_t self; 511 u_int off; 512 513 self = pthread__self(); 514 515 switch (self->pt_rwlocked) { 516 case _RW_WANT_READ: 517 off = offsetof(pthread_rwlock_t, ptr_rblocked); 518 break; 519 case _RW_WANT_WRITE: 520 off = offsetof(pthread_rwlock_t, ptr_wblocked); 521 break; 522 default: 523 pthread__errorfunc(__FILE__, __LINE__, __func__, 524 "bad value of pt_rwlocked"); 525 off = 0; 526 /* NOTREACHED */ 527 break; 528 } 529 530 /* LINTED mind your own business */ 531 ptr = (pthread_rwlock_t *)((uint8_t *)obj - off); 532 owner = (uintptr_t)ptr->ptr_owner; 533 534 if ((owner & RW_THREAD) == 0) { 535 pthread__errorfunc(__FILE__, __LINE__, __func__, 536 "lock not held"); 537 } 538 539 if (!PTQ_EMPTY(&ptr->ptr_wblocked)) 540 set = RW_HAS_WAITERS | RW_WRITE_WANTED; 541 else if (ptr->ptr_nreaders != 0) 542 set = RW_HAS_WAITERS; 543 else 544 set = 0; 545 546 for (;; owner = next) { 547 new = (owner & ~(RW_HAS_WAITERS | RW_WRITE_WANTED)) | set; 548 next = rw_cas(ptr, owner, new); 549 if (owner == next) 550 break; 551 } 552 } 553 554 int 555 _pthread_rwlock_held_np(pthread_rwlock_t *ptr) 556 { 557 uintptr_t owner = (uintptr_t)ptr->ptr_owner; 558 559 return (owner & RW_THREAD) != 0; 560 } 561 562 int 563 _pthread_rwlock_rdheld_np(pthread_rwlock_t *ptr) 564 { 565 uintptr_t owner = (uintptr_t)ptr->ptr_owner; 566 567 return (owner & RW_THREAD) != 0 && (owner & RW_WRITE_LOCKED) == 0; 568 } 569 570 int 571 _pthread_rwlock_wrheld_np(pthread_rwlock_t *ptr) 572 { 573 uintptr_t owner = (uintptr_t)ptr->ptr_owner; 574 575 return (owner & (RW_THREAD | RW_WRITE_LOCKED)) == 576 ((uintptr_t)pthread__self() | RW_WRITE_LOCKED); 577 } 578 579 int 580 pthread_rwlockattr_init(pthread_rwlockattr_t *attr) 581 { 582 583 if (attr == NULL) 584 return EINVAL; 585 attr->ptra_magic = _PT_RWLOCKATTR_MAGIC; 586 587 return 0; 588 } 589 590 591 int 592 pthread_rwlockattr_destroy(pthread_rwlockattr_t *attr) 593 { 594 595 if ((attr == NULL) || 596 (attr->ptra_magic != _PT_RWLOCKATTR_MAGIC)) 597 return EINVAL; 598 attr->ptra_magic = _PT_RWLOCKATTR_DEAD; 599 600 return 0; 601 } 602