1 /* $NetBSD: pthread_mutex.c,v 1.54 2012/08/16 04:49:47 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.54 2012/08/16 04:49:47 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 int 102 pthread_mutex_init(pthread_mutex_t *ptm, const pthread_mutexattr_t *attr) 103 { 104 intptr_t type; 105 106 if (attr == NULL) 107 type = PTHREAD_MUTEX_NORMAL; 108 else 109 type = (intptr_t)attr->ptma_private; 110 111 switch (type) { 112 case PTHREAD_MUTEX_ERRORCHECK: 113 __cpu_simple_lock_set(&ptm->ptm_errorcheck); 114 ptm->ptm_owner = NULL; 115 break; 116 case PTHREAD_MUTEX_RECURSIVE: 117 __cpu_simple_lock_clear(&ptm->ptm_errorcheck); 118 ptm->ptm_owner = (void *)MUTEX_RECURSIVE_BIT; 119 break; 120 default: 121 __cpu_simple_lock_clear(&ptm->ptm_errorcheck); 122 ptm->ptm_owner = NULL; 123 break; 124 } 125 126 ptm->ptm_magic = _PT_MUTEX_MAGIC; 127 ptm->ptm_waiters = NULL; 128 ptm->ptm_recursed = 0; 129 130 return 0; 131 } 132 133 134 int 135 pthread_mutex_destroy(pthread_mutex_t *ptm) 136 { 137 138 pthread__error(EINVAL, "Invalid mutex", 139 ptm->ptm_magic == _PT_MUTEX_MAGIC); 140 pthread__error(EBUSY, "Destroying locked mutex", 141 MUTEX_OWNER(ptm->ptm_owner) == 0); 142 143 ptm->ptm_magic = _PT_MUTEX_DEAD; 144 return 0; 145 } 146 147 int 148 pthread_mutex_lock(pthread_mutex_t *ptm) 149 { 150 pthread_t self; 151 void *val; 152 153 self = pthread__self(); 154 val = atomic_cas_ptr(&ptm->ptm_owner, NULL, self); 155 if (__predict_true(val == NULL)) { 156 #ifndef PTHREAD__ATOMIC_IS_MEMBAR 157 membar_enter(); 158 #endif 159 return 0; 160 } 161 return pthread__mutex_lock_slow(ptm); 162 } 163 164 /* We want function call overhead. */ 165 NOINLINE static void 166 pthread__mutex_pause(void) 167 { 168 169 pthread__smt_pause(); 170 } 171 172 /* 173 * Spin while the holder is running. 'lwpctl' gives us the true 174 * status of the thread. pt_blocking is set by libpthread in order 175 * to cut out system call and kernel spinlock overhead on remote CPUs 176 * (could represent many thousands of clock cycles). pt_blocking also 177 * makes this thread yield if the target is calling sched_yield(). 178 */ 179 NOINLINE static void * 180 pthread__mutex_spin(pthread_mutex_t *ptm, pthread_t owner) 181 { 182 pthread_t thread; 183 unsigned int count, i; 184 185 for (count = 2;; owner = ptm->ptm_owner) { 186 thread = (pthread_t)MUTEX_OWNER(owner); 187 if (thread == NULL) 188 break; 189 if (thread->pt_lwpctl->lc_curcpu == LWPCTL_CPU_NONE || 190 thread->pt_blocking) 191 break; 192 if (count < 128) 193 count += count; 194 for (i = count; i != 0; i--) 195 pthread__mutex_pause(); 196 } 197 198 return owner; 199 } 200 201 NOINLINE static int 202 pthread__mutex_lock_slow(pthread_mutex_t *ptm) 203 { 204 void *waiters, *new, *owner, *next; 205 pthread_t self; 206 207 pthread__error(EINVAL, "Invalid mutex", 208 ptm->ptm_magic == _PT_MUTEX_MAGIC); 209 210 owner = ptm->ptm_owner; 211 self = pthread__self(); 212 213 /* Recursive or errorcheck? */ 214 if (MUTEX_OWNER(owner) == (uintptr_t)self) { 215 if (MUTEX_RECURSIVE(owner)) { 216 if (ptm->ptm_recursed == INT_MAX) 217 return EAGAIN; 218 ptm->ptm_recursed++; 219 return 0; 220 } 221 if (__SIMPLELOCK_LOCKED_P(&ptm->ptm_errorcheck)) 222 return EDEADLK; 223 } 224 225 for (;; owner = ptm->ptm_owner) { 226 /* Spin while the owner is running. */ 227 owner = pthread__mutex_spin(ptm, owner); 228 229 /* If it has become free, try to acquire it again. */ 230 if (MUTEX_OWNER(owner) == 0) { 231 do { 232 new = (void *) 233 ((uintptr_t)self | (uintptr_t)owner); 234 next = atomic_cas_ptr(&ptm->ptm_owner, owner, 235 new); 236 if (next == owner) { 237 #ifndef PTHREAD__ATOMIC_IS_MEMBAR 238 membar_enter(); 239 #endif 240 return 0; 241 } 242 owner = next; 243 } while (MUTEX_OWNER(owner) == 0); 244 /* 245 * We have lost the race to acquire the mutex. 246 * The new owner could be running on another 247 * CPU, in which case we should spin and avoid 248 * the overhead of blocking. 249 */ 250 continue; 251 } 252 253 /* 254 * Nope, still held. Add thread to the list of waiters. 255 * Issue a memory barrier to ensure mutexwait/mutexnext 256 * are visible before we enter the waiters list. 257 */ 258 self->pt_mutexwait = 1; 259 for (waiters = ptm->ptm_waiters;; waiters = next) { 260 self->pt_mutexnext = waiters; 261 membar_producer(); 262 next = atomic_cas_ptr(&ptm->ptm_waiters, waiters, self); 263 if (next == waiters) 264 break; 265 } 266 267 /* 268 * Set the waiters bit and block. 269 * 270 * Note that the mutex can become unlocked before we set 271 * the waiters bit. If that happens it's not safe to sleep 272 * as we may never be awoken: we must remove the current 273 * thread from the waiters list and try again. 274 * 275 * Because we are doing this atomically, we can't remove 276 * one waiter: we must remove all waiters and awken them, 277 * then sleep in _lwp_park() until we have been awoken. 278 * 279 * Issue a memory barrier to ensure that we are reading 280 * the value of ptm_owner/pt_mutexwait after we have entered 281 * the waiters list (the CAS itself must be atomic). 282 */ 283 membar_consumer(); 284 for (owner = ptm->ptm_owner;; owner = next) { 285 if (MUTEX_HAS_WAITERS(owner)) 286 break; 287 if (MUTEX_OWNER(owner) == 0) { 288 pthread__mutex_wakeup(self, ptm); 289 break; 290 } 291 new = (void *)((uintptr_t)owner | MUTEX_WAITERS_BIT); 292 next = atomic_cas_ptr(&ptm->ptm_owner, owner, new); 293 if (next == owner) { 294 /* 295 * pthread_mutex_unlock() can do a 296 * non-interlocked CAS. We cannot 297 * know if our attempt to set the 298 * waiters bit has succeeded while 299 * the holding thread is running. 300 * There are many assumptions; see 301 * sys/kern/kern_mutex.c for details. 302 * In short, we must spin if we see 303 * that the holder is running again. 304 */ 305 membar_sync(); 306 next = pthread__mutex_spin(ptm, owner); 307 } 308 } 309 310 /* 311 * We may have been awoken by the current thread above, 312 * or will be awoken by the current holder of the mutex. 313 * The key requirement is that we must not proceed until 314 * told that we are no longer waiting (via pt_mutexwait 315 * being set to zero). Otherwise it is unsafe to re-enter 316 * the thread onto the waiters list. 317 */ 318 while (self->pt_mutexwait) { 319 self->pt_blocking++; 320 (void)_lwp_park(NULL, self->pt_unpark, 321 __UNVOLATILE(&ptm->ptm_waiters), 322 __UNVOLATILE(&ptm->ptm_waiters)); 323 self->pt_unpark = 0; 324 self->pt_blocking--; 325 membar_sync(); 326 } 327 } 328 } 329 330 int 331 pthread_mutex_trylock(pthread_mutex_t *ptm) 332 { 333 pthread_t self; 334 void *val, *new, *next; 335 336 self = pthread__self(); 337 val = atomic_cas_ptr(&ptm->ptm_owner, NULL, self); 338 if (__predict_true(val == NULL)) { 339 #ifndef PTHREAD__ATOMIC_IS_MEMBAR 340 membar_enter(); 341 #endif 342 return 0; 343 } 344 345 if (MUTEX_RECURSIVE(val)) { 346 if (MUTEX_OWNER(val) == 0) { 347 new = (void *)((uintptr_t)self | (uintptr_t)val); 348 next = atomic_cas_ptr(&ptm->ptm_owner, val, new); 349 if (__predict_true(next == val)) { 350 #ifndef PTHREAD__ATOMIC_IS_MEMBAR 351 membar_enter(); 352 #endif 353 return 0; 354 } 355 } 356 if (MUTEX_OWNER(val) == (uintptr_t)self) { 357 if (ptm->ptm_recursed == INT_MAX) 358 return EAGAIN; 359 ptm->ptm_recursed++; 360 return 0; 361 } 362 } 363 364 return EBUSY; 365 } 366 367 int 368 pthread_mutex_unlock(pthread_mutex_t *ptm) 369 { 370 pthread_t self; 371 void *value; 372 373 /* 374 * Note this may be a non-interlocked CAS. See lock_slow() 375 * above and sys/kern/kern_mutex.c for details. 376 */ 377 #ifndef PTHREAD__ATOMIC_IS_MEMBAR 378 membar_exit(); 379 #endif 380 self = pthread__self(); 381 value = atomic_cas_ptr_ni(&ptm->ptm_owner, self, NULL); 382 if (__predict_true(value == self)) { 383 pthread__smt_wake(); 384 return 0; 385 } 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 pthread__smt_wake(); 481 482 for (;;) { 483 /* 484 * Pull waiters from the queue and add to our list. 485 * Use a memory barrier to ensure that we safely 486 * read the value of pt_mutexnext before 'thread' 487 * sees pt_mutexwait being cleared. 488 */ 489 for (n = self->pt_nwaiters, self->pt_nwaiters = 0; 490 n < pthread__unpark_max && thread != NULL; 491 thread = next) { 492 next = thread->pt_mutexnext; 493 if (thread != self) { 494 self->pt_waiters[n++] = thread->pt_lid; 495 membar_sync(); 496 } 497 thread->pt_mutexwait = 0; 498 /* No longer safe to touch 'thread' */ 499 } 500 501 switch (n) { 502 case 0: 503 return; 504 case 1: 505 /* 506 * If the calling thread is about to block, 507 * defer unparking the target until _lwp_park() 508 * is called. 509 */ 510 if (self->pt_willpark && self->pt_unpark == 0) { 511 self->pt_unpark = self->pt_waiters[0]; 512 return; 513 } 514 rv = (ssize_t)_lwp_unpark(self->pt_waiters[0], 515 __UNVOLATILE(&ptm->ptm_waiters)); 516 if (rv != 0 && errno != EALREADY && errno != EINTR && 517 errno != ESRCH) { 518 pthread__errorfunc(__FILE__, __LINE__, 519 __func__, "_lwp_unpark failed"); 520 } 521 return; 522 default: 523 rv = _lwp_unpark_all(self->pt_waiters, (size_t)n, 524 __UNVOLATILE(&ptm->ptm_waiters)); 525 if (rv != 0 && errno != EINTR) { 526 pthread__errorfunc(__FILE__, __LINE__, 527 __func__, "_lwp_unpark_all failed"); 528 } 529 break; 530 } 531 } 532 } 533 int 534 pthread_mutexattr_init(pthread_mutexattr_t *attr) 535 { 536 537 attr->ptma_magic = _PT_MUTEXATTR_MAGIC; 538 attr->ptma_private = (void *)PTHREAD_MUTEX_DEFAULT; 539 return 0; 540 } 541 542 int 543 pthread_mutexattr_destroy(pthread_mutexattr_t *attr) 544 { 545 546 pthread__error(EINVAL, "Invalid mutex attribute", 547 attr->ptma_magic == _PT_MUTEXATTR_MAGIC); 548 549 return 0; 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 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 void 582 pthread__mutex_deferwake(pthread_t self, pthread_mutex_t *ptm) 583 { 584 585 if (__predict_false(ptm == NULL || 586 MUTEX_OWNER(ptm->ptm_owner) != (uintptr_t)self)) { 587 (void)_lwp_unpark_all(self->pt_waiters, self->pt_nwaiters, 588 __UNVOLATILE(&ptm->ptm_waiters)); 589 self->pt_nwaiters = 0; 590 } else { 591 atomic_or_ulong((volatile unsigned long *) 592 (uintptr_t)&ptm->ptm_owner, 593 (unsigned long)MUTEX_DEFERRED_BIT); 594 } 595 } 596 597 int 598 _pthread_mutex_held_np(pthread_mutex_t *ptm) 599 { 600 601 return MUTEX_OWNER(ptm->ptm_owner) == (uintptr_t)pthread__self(); 602 } 603 604 pthread_t 605 _pthread_mutex_owner_np(pthread_mutex_t *ptm) 606 { 607 608 return (pthread_t)MUTEX_OWNER(ptm->ptm_owner); 609 } 610