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