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