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