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