1 /* $NetBSD: pthread_mutex.c,v 1.47 2008/03/07 22:23:57 ad Exp $ */ 2 3 /*- 4 * Copyright (c) 2001, 2003, 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_mutex.c,v 1.47 2008/03/07 22:23:57 ad Exp $"); 41 42 #include <sys/types.h> 43 #include <sys/lwpctl.h> 44 45 #include <errno.h> 46 #include <limits.h> 47 #include <stdlib.h> 48 #include <string.h> 49 #include <stdio.h> 50 51 #include "pthread.h" 52 #include "pthread_int.h" 53 54 #define pt_nextwaiter pt_sleep.ptqe_next 55 56 #define MUTEX_WAITERS_BIT ((uintptr_t)0x01) 57 #define MUTEX_RECURSIVE_BIT ((uintptr_t)0x02) 58 #define MUTEX_DEFERRED_BIT ((uintptr_t)0x04) 59 #define MUTEX_THREAD ((uintptr_t)-16L) 60 61 #define MUTEX_HAS_WAITERS(x) ((uintptr_t)(x) & MUTEX_WAITERS_BIT) 62 #define MUTEX_RECURSIVE(x) ((uintptr_t)(x) & MUTEX_RECURSIVE_BIT) 63 #define MUTEX_OWNER(x) ((uintptr_t)(x) & MUTEX_THREAD) 64 65 #if __GNUC_PREREQ__(3, 0) 66 #define NOINLINE __attribute ((noinline)) 67 #else 68 #define NOINLINE /* nothing */ 69 #endif 70 71 static void pthread__mutex_wakeup(pthread_t, pthread_mutex_t *); 72 static int pthread__mutex_lock_slow(pthread_mutex_t *); 73 static int pthread__mutex_unlock_slow(pthread_mutex_t *); 74 static void pthread__mutex_pause(void); 75 76 int _pthread_mutex_held_np(pthread_mutex_t *); 77 pthread_t _pthread_mutex_owner_np(pthread_mutex_t *); 78 79 __weak_alias(pthread_mutex_held_np,_pthread_mutex_held_np) 80 __weak_alias(pthread_mutex_owner_np,_pthread_mutex_owner_np) 81 82 __strong_alias(__libc_mutex_init,pthread_mutex_init) 83 __strong_alias(__libc_mutex_lock,pthread_mutex_lock) 84 __strong_alias(__libc_mutex_trylock,pthread_mutex_trylock) 85 __strong_alias(__libc_mutex_unlock,pthread_mutex_unlock) 86 __strong_alias(__libc_mutex_destroy,pthread_mutex_destroy) 87 88 __strong_alias(__libc_mutexattr_init,pthread_mutexattr_init) 89 __strong_alias(__libc_mutexattr_destroy,pthread_mutexattr_destroy) 90 __strong_alias(__libc_mutexattr_settype,pthread_mutexattr_settype) 91 92 __strong_alias(__libc_thr_once,pthread_once) 93 94 int 95 pthread_mutex_init(pthread_mutex_t *ptm, const pthread_mutexattr_t *attr) 96 { 97 intptr_t type; 98 99 if (attr == NULL) 100 type = PTHREAD_MUTEX_NORMAL; 101 else 102 type = (intptr_t)attr->ptma_private; 103 104 switch (type) { 105 case PTHREAD_MUTEX_ERRORCHECK: 106 ptm->ptm_errorcheck = 1; 107 ptm->ptm_owner = NULL; 108 break; 109 case PTHREAD_MUTEX_RECURSIVE: 110 ptm->ptm_errorcheck = 0; 111 ptm->ptm_owner = (void *)MUTEX_RECURSIVE_BIT; 112 break; 113 default: 114 ptm->ptm_errorcheck = 0; 115 ptm->ptm_owner = NULL; 116 break; 117 } 118 119 ptm->ptm_magic = _PT_MUTEX_MAGIC; 120 ptm->ptm_waiters = NULL; 121 ptm->ptm_recursed = 0; 122 123 return 0; 124 } 125 126 127 int 128 pthread_mutex_destroy(pthread_mutex_t *ptm) 129 { 130 131 pthread__error(EINVAL, "Invalid mutex", 132 ptm->ptm_magic == _PT_MUTEX_MAGIC); 133 pthread__error(EBUSY, "Destroying locked mutex", 134 MUTEX_OWNER(ptm->ptm_owner) == 0); 135 136 ptm->ptm_magic = _PT_MUTEX_DEAD; 137 return 0; 138 } 139 140 int 141 pthread_mutex_lock(pthread_mutex_t *ptm) 142 { 143 pthread_t self; 144 void *val; 145 146 self = pthread__self(); 147 val = atomic_cas_ptr(&ptm->ptm_owner, NULL, self); 148 if (__predict_true(val == NULL)) { 149 #ifndef PTHREAD__ATOMIC_IS_MEMBAR 150 membar_enter(); 151 #endif 152 return 0; 153 } 154 return pthread__mutex_lock_slow(ptm); 155 } 156 157 /* We want function call overhead. */ 158 NOINLINE static void 159 pthread__mutex_pause(void) 160 { 161 162 pthread__smt_pause(); 163 } 164 165 /* 166 * Spin while the holder is running. 'lwpctl' gives us the true 167 * status of the thread. pt_blocking is set by libpthread in order 168 * to cut out system call and kernel spinlock overhead on remote CPUs 169 * (could represent many thousands of clock cycles). pt_blocking also 170 * makes this thread yield if the target is calling sched_yield(). 171 */ 172 NOINLINE static void * 173 pthread__mutex_spin(pthread_mutex_t *ptm, pthread_t owner) 174 { 175 pthread_t thread; 176 unsigned int count, i; 177 178 for (count = 2;; owner = ptm->ptm_owner) { 179 thread = (pthread_t)MUTEX_OWNER(owner); 180 if (thread == NULL) 181 break; 182 if (thread->pt_lwpctl->lc_curcpu == LWPCTL_CPU_NONE || 183 thread->pt_blocking) 184 break; 185 if (count < 128) 186 count += count; 187 for (i = count; i != 0; i--) 188 pthread__mutex_pause(); 189 } 190 191 return owner; 192 } 193 194 NOINLINE static int 195 pthread__mutex_lock_slow(pthread_mutex_t *ptm) 196 { 197 void *waiters, *new, *owner, *next; 198 pthread_t self; 199 200 pthread__error(EINVAL, "Invalid mutex", 201 ptm->ptm_magic == _PT_MUTEX_MAGIC); 202 203 owner = ptm->ptm_owner; 204 self = pthread__self(); 205 206 /* Recursive or errorcheck? */ 207 if (MUTEX_OWNER(owner) == (uintptr_t)self) { 208 if (MUTEX_RECURSIVE(owner)) { 209 if (ptm->ptm_recursed == INT_MAX) 210 return EAGAIN; 211 ptm->ptm_recursed++; 212 return 0; 213 } 214 if (ptm->ptm_errorcheck) 215 return EDEADLK; 216 } 217 218 for (;; owner = ptm->ptm_owner) { 219 /* Spin while the owner is running. */ 220 owner = pthread__mutex_spin(ptm, owner); 221 222 /* If it has become free, try to acquire it again. */ 223 if (MUTEX_OWNER(owner) == 0) { 224 do { 225 new = (void *) 226 ((uintptr_t)self | (uintptr_t)owner); 227 next = atomic_cas_ptr(&ptm->ptm_owner, owner, 228 new); 229 if (next == owner) { 230 #ifndef PTHREAD__ATOMIC_IS_MEMBAR 231 membar_enter(); 232 #endif 233 return 0; 234 } 235 owner = next; 236 } while (MUTEX_OWNER(owner) == 0); 237 /* 238 * We have lost the race to acquire the mutex. 239 * The new owner could be running on another 240 * CPU, in which case we should spin and avoid 241 * the overhead of blocking. 242 */ 243 continue; 244 } 245 246 /* 247 * Nope, still held. Add thread to the list of waiters. 248 * Issue a memory barrier to ensure sleeponq/nextwaiter 249 * are visible before we enter the waiters list. 250 */ 251 self->pt_sleeponq = 1; 252 for (waiters = ptm->ptm_waiters;; waiters = next) { 253 self->pt_nextwaiter = waiters; 254 membar_producer(); 255 next = atomic_cas_ptr(&ptm->ptm_waiters, waiters, self); 256 if (next == waiters) 257 break; 258 } 259 260 /* 261 * Set the waiters bit and block. 262 * 263 * Note that the mutex can become unlocked before we set 264 * the waiters bit. If that happens it's not safe to sleep 265 * as we may never be awoken: we must remove the current 266 * thread from the waiters list and try again. 267 * 268 * Because we are doing this atomically, we can't remove 269 * one waiter: we must remove all waiters and awken them, 270 * then sleep in _lwp_park() until we have been awoken. 271 * 272 * Issue a memory barrier to ensure that we are reading 273 * the value of ptm_owner/pt_sleeponq after we have entered 274 * the waiters list (the CAS itself must be atomic). 275 */ 276 membar_consumer(); 277 for (owner = ptm->ptm_owner;; owner = next) { 278 if (MUTEX_HAS_WAITERS(owner)) 279 break; 280 if (MUTEX_OWNER(owner) == 0) { 281 pthread__mutex_wakeup(self, ptm); 282 break; 283 } 284 new = (void *)((uintptr_t)owner | MUTEX_WAITERS_BIT); 285 next = atomic_cas_ptr(&ptm->ptm_owner, owner, new); 286 if (next == owner) { 287 /* 288 * pthread_mutex_unlock() can do a 289 * non-interlocked CAS. We cannot 290 * know if our attempt to set the 291 * waiters bit has succeeded while 292 * the holding thread is running. 293 * There are many assumptions; see 294 * sys/kern/kern_mutex.c for details. 295 * In short, we must spin if we see 296 * that the holder is running again. 297 */ 298 membar_sync(); 299 next = pthread__mutex_spin(ptm, owner); 300 } 301 } 302 303 /* 304 * We may have been awoken by the current thread above, 305 * or will be awoken by the current holder of the mutex. 306 * The key requirement is that we must not proceed until 307 * told that we are no longer waiting (via pt_sleeponq 308 * being set to zero). Otherwise it is unsafe to re-enter 309 * the thread onto the waiters list. 310 */ 311 while (self->pt_sleeponq) { 312 self->pt_blocking++; 313 (void)_lwp_park(NULL, 0, 314 __UNVOLATILE(&ptm->ptm_waiters), NULL); 315 self->pt_blocking--; 316 membar_sync(); 317 } 318 } 319 } 320 321 int 322 pthread_mutex_trylock(pthread_mutex_t *ptm) 323 { 324 pthread_t self; 325 void *val, *new, *next; 326 327 self = pthread__self(); 328 val = atomic_cas_ptr(&ptm->ptm_owner, NULL, self); 329 if (__predict_true(val == NULL)) { 330 #ifndef PTHREAD__ATOMIC_IS_MEMBAR 331 membar_enter(); 332 #endif 333 return 0; 334 } 335 336 if (MUTEX_RECURSIVE(val)) { 337 if (MUTEX_OWNER(val) == 0) { 338 new = (void *)((uintptr_t)self | (uintptr_t)val); 339 next = atomic_cas_ptr(&ptm->ptm_owner, val, new); 340 if (__predict_true(next == val)) { 341 #ifndef PTHREAD__ATOMIC_IS_MEMBAR 342 membar_enter(); 343 #endif 344 return 0; 345 } 346 } 347 if (MUTEX_OWNER(val) == (uintptr_t)self) { 348 if (ptm->ptm_recursed == INT_MAX) 349 return EAGAIN; 350 ptm->ptm_recursed++; 351 return 0; 352 } 353 } 354 355 return EBUSY; 356 } 357 358 int 359 pthread_mutex_unlock(pthread_mutex_t *ptm) 360 { 361 pthread_t self; 362 void *value; 363 364 /* 365 * Note this may be a non-interlocked CAS. See lock_slow() 366 * above and sys/kern/kern_mutex.c for details. 367 */ 368 #ifndef PTHREAD__ATOMIC_IS_MEMBAR 369 membar_exit(); 370 #endif 371 self = pthread__self(); 372 value = atomic_cas_ptr_ni(&ptm->ptm_owner, self, NULL); 373 if (__predict_true(value == self)) 374 return 0; 375 return pthread__mutex_unlock_slow(ptm); 376 } 377 378 NOINLINE static int 379 pthread__mutex_unlock_slow(pthread_mutex_t *ptm) 380 { 381 pthread_t self, owner, new; 382 int weown, error, deferred; 383 384 pthread__error(EINVAL, "Invalid mutex", 385 ptm->ptm_magic == _PT_MUTEX_MAGIC); 386 387 self = pthread__self(); 388 owner = ptm->ptm_owner; 389 weown = (MUTEX_OWNER(owner) == (uintptr_t)self); 390 deferred = (int)((uintptr_t)owner & MUTEX_DEFERRED_BIT); 391 error = 0; 392 393 if (ptm->ptm_errorcheck) { 394 if (!weown) { 395 error = EPERM; 396 new = owner; 397 } else { 398 new = NULL; 399 } 400 } else if (MUTEX_RECURSIVE(owner)) { 401 if (!weown) { 402 error = EPERM; 403 new = owner; 404 } else if (ptm->ptm_recursed) { 405 ptm->ptm_recursed--; 406 new = owner; 407 } else { 408 new = (pthread_t)MUTEX_RECURSIVE_BIT; 409 } 410 } else { 411 pthread__error(EPERM, 412 "Unlocking unlocked mutex", (owner != NULL)); 413 pthread__error(EPERM, 414 "Unlocking mutex owned by another thread", weown); 415 new = NULL; 416 } 417 418 /* 419 * Release the mutex. If there appear to be waiters, then 420 * wake them up. 421 */ 422 if (new != owner) { 423 owner = atomic_swap_ptr(&ptm->ptm_owner, new); 424 if (MUTEX_HAS_WAITERS(owner) != 0) { 425 pthread__mutex_wakeup(self, ptm); 426 return 0; 427 } 428 } 429 430 /* 431 * There were no waiters, but we may have deferred waking 432 * other threads until mutex unlock - we must wake them now. 433 */ 434 if (!deferred) 435 return error; 436 437 if (self->pt_nwaiters == 1) { 438 /* 439 * If the calling thread is about to block, defer 440 * unparking the target until _lwp_park() is called. 441 */ 442 if (self->pt_willpark && self->pt_unpark == 0) { 443 self->pt_unpark = self->pt_waiters[0]; 444 self->pt_unparkhint = 445 __UNVOLATILE(&ptm->ptm_waiters); 446 } else { 447 (void)_lwp_unpark(self->pt_waiters[0], 448 __UNVOLATILE(&ptm->ptm_waiters)); 449 } 450 } else { 451 (void)_lwp_unpark_all(self->pt_waiters, self->pt_nwaiters, 452 __UNVOLATILE(&ptm->ptm_waiters)); 453 } 454 self->pt_nwaiters = 0; 455 456 return error; 457 } 458 459 static void 460 pthread__mutex_wakeup(pthread_t self, pthread_mutex_t *ptm) 461 { 462 pthread_t thread, next; 463 ssize_t n, rv; 464 465 /* 466 * Take ownership of the current set of waiters. No 467 * need for a memory barrier following this, all loads 468 * are dependent upon 'thread'. 469 */ 470 thread = atomic_swap_ptr(&ptm->ptm_waiters, NULL); 471 472 for (;;) { 473 /* 474 * Pull waiters from the queue and add to our list. 475 * Use a memory barrier to ensure that we safely 476 * read the value of pt_nextwaiter before 'thread' 477 * sees pt_sleeponq being cleared. 478 */ 479 for (n = self->pt_nwaiters, self->pt_nwaiters = 0; 480 n < pthread__unpark_max && thread != NULL; 481 thread = next) { 482 next = thread->pt_nextwaiter; 483 if (thread != self) { 484 self->pt_waiters[n++] = thread->pt_lid; 485 membar_sync(); 486 } 487 thread->pt_sleeponq = 0; 488 /* No longer safe to touch 'thread' */ 489 } 490 491 switch (n) { 492 case 0: 493 return; 494 case 1: 495 /* 496 * If the calling thread is about to block, 497 * defer unparking the target until _lwp_park() 498 * is called. 499 */ 500 if (self->pt_willpark && self->pt_unpark == 0) { 501 self->pt_unpark = self->pt_waiters[0]; 502 self->pt_unparkhint = 503 __UNVOLATILE(&ptm->ptm_waiters); 504 return; 505 } 506 rv = (ssize_t)_lwp_unpark(self->pt_waiters[0], 507 __UNVOLATILE(&ptm->ptm_waiters)); 508 if (rv != 0 && errno != EALREADY && errno != EINTR && 509 errno != ESRCH) { 510 pthread__errorfunc(__FILE__, __LINE__, 511 __func__, "_lwp_unpark failed"); 512 } 513 return; 514 default: 515 rv = _lwp_unpark_all(self->pt_waiters, (size_t)n, 516 __UNVOLATILE(&ptm->ptm_waiters)); 517 if (rv != 0 && errno != EINTR) { 518 pthread__errorfunc(__FILE__, __LINE__, 519 __func__, "_lwp_unpark_all failed"); 520 } 521 break; 522 } 523 } 524 } 525 int 526 pthread_mutexattr_init(pthread_mutexattr_t *attr) 527 { 528 529 attr->ptma_magic = _PT_MUTEXATTR_MAGIC; 530 attr->ptma_private = (void *)PTHREAD_MUTEX_DEFAULT; 531 return 0; 532 } 533 534 int 535 pthread_mutexattr_destroy(pthread_mutexattr_t *attr) 536 { 537 538 pthread__error(EINVAL, "Invalid mutex attribute", 539 attr->ptma_magic == _PT_MUTEXATTR_MAGIC); 540 541 return 0; 542 } 543 544 545 int 546 pthread_mutexattr_gettype(const pthread_mutexattr_t *attr, int *typep) 547 { 548 549 pthread__error(EINVAL, "Invalid mutex attribute", 550 attr->ptma_magic == _PT_MUTEXATTR_MAGIC); 551 552 *typep = (int)(intptr_t)attr->ptma_private; 553 return 0; 554 } 555 556 557 int 558 pthread_mutexattr_settype(pthread_mutexattr_t *attr, int type) 559 { 560 561 pthread__error(EINVAL, "Invalid mutex attribute", 562 attr->ptma_magic == _PT_MUTEXATTR_MAGIC); 563 564 switch (type) { 565 case PTHREAD_MUTEX_NORMAL: 566 case PTHREAD_MUTEX_ERRORCHECK: 567 case PTHREAD_MUTEX_RECURSIVE: 568 attr->ptma_private = (void *)(intptr_t)type; 569 return 0; 570 default: 571 return EINVAL; 572 } 573 } 574 575 576 static void 577 once_cleanup(void *closure) 578 { 579 580 pthread_mutex_unlock((pthread_mutex_t *)closure); 581 } 582 583 584 int 585 pthread_once(pthread_once_t *once_control, void (*routine)(void)) 586 { 587 588 if (once_control->pto_done == 0) { 589 pthread_mutex_lock(&once_control->pto_mutex); 590 pthread_cleanup_push(&once_cleanup, &once_control->pto_mutex); 591 if (once_control->pto_done == 0) { 592 routine(); 593 once_control->pto_done = 1; 594 } 595 pthread_cleanup_pop(1); 596 } 597 598 return 0; 599 } 600 601 int 602 pthread__mutex_deferwake(pthread_t thread, pthread_mutex_t *ptm) 603 { 604 605 if (MUTEX_OWNER(ptm->ptm_owner) != (uintptr_t)thread) 606 return 0; 607 atomic_or_ulong((volatile unsigned long *) 608 (uintptr_t)&ptm->ptm_owner, 609 (unsigned long)MUTEX_DEFERRED_BIT); 610 return 1; 611 } 612 613 int 614 _pthread_mutex_held_np(pthread_mutex_t *ptm) 615 { 616 617 return MUTEX_OWNER(ptm->ptm_owner) == (uintptr_t)pthread__self(); 618 } 619 620 pthread_t 621 _pthread_mutex_owner_np(pthread_mutex_t *ptm) 622 { 623 624 return (pthread_t)MUTEX_OWNER(ptm->ptm_owner); 625 } 626