1 /* $NetBSD: pthread_mutex.c,v 1.53 2012/03/13 01:05:55 joerg 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.53 2012/03/13 01:05:55 joerg 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 return 0; 384 return pthread__mutex_unlock_slow(ptm); 385 } 386 387 NOINLINE static int 388 pthread__mutex_unlock_slow(pthread_mutex_t *ptm) 389 { 390 pthread_t self, owner, new; 391 int weown, error, deferred; 392 393 pthread__error(EINVAL, "Invalid mutex", 394 ptm->ptm_magic == _PT_MUTEX_MAGIC); 395 396 self = pthread__self(); 397 owner = ptm->ptm_owner; 398 weown = (MUTEX_OWNER(owner) == (uintptr_t)self); 399 deferred = (int)((uintptr_t)owner & MUTEX_DEFERRED_BIT); 400 error = 0; 401 402 if (__SIMPLELOCK_LOCKED_P(&ptm->ptm_errorcheck)) { 403 if (!weown) { 404 error = EPERM; 405 new = owner; 406 } else { 407 new = NULL; 408 } 409 } else if (MUTEX_RECURSIVE(owner)) { 410 if (!weown) { 411 error = EPERM; 412 new = owner; 413 } else if (ptm->ptm_recursed) { 414 ptm->ptm_recursed--; 415 new = owner; 416 } else { 417 new = (pthread_t)MUTEX_RECURSIVE_BIT; 418 } 419 } else { 420 pthread__error(EPERM, 421 "Unlocking unlocked mutex", (owner != NULL)); 422 pthread__error(EPERM, 423 "Unlocking mutex owned by another thread", weown); 424 new = NULL; 425 } 426 427 /* 428 * Release the mutex. If there appear to be waiters, then 429 * wake them up. 430 */ 431 if (new != owner) { 432 owner = atomic_swap_ptr(&ptm->ptm_owner, new); 433 if (MUTEX_HAS_WAITERS(owner) != 0) { 434 pthread__mutex_wakeup(self, ptm); 435 return 0; 436 } 437 } 438 439 /* 440 * There were no waiters, but we may have deferred waking 441 * other threads until mutex unlock - we must wake them now. 442 */ 443 if (!deferred) 444 return error; 445 446 if (self->pt_nwaiters == 1) { 447 /* 448 * If the calling thread is about to block, defer 449 * unparking the target until _lwp_park() is called. 450 */ 451 if (self->pt_willpark && self->pt_unpark == 0) { 452 self->pt_unpark = self->pt_waiters[0]; 453 } else { 454 (void)_lwp_unpark(self->pt_waiters[0], 455 __UNVOLATILE(&ptm->ptm_waiters)); 456 } 457 } else { 458 (void)_lwp_unpark_all(self->pt_waiters, self->pt_nwaiters, 459 __UNVOLATILE(&ptm->ptm_waiters)); 460 } 461 self->pt_nwaiters = 0; 462 463 return error; 464 } 465 466 static void 467 pthread__mutex_wakeup(pthread_t self, pthread_mutex_t *ptm) 468 { 469 pthread_t thread, next; 470 ssize_t n, rv; 471 472 /* 473 * Take ownership of the current set of waiters. No 474 * need for a memory barrier following this, all loads 475 * are dependent upon 'thread'. 476 */ 477 thread = atomic_swap_ptr(&ptm->ptm_waiters, NULL); 478 479 for (;;) { 480 /* 481 * Pull waiters from the queue and add to our list. 482 * Use a memory barrier to ensure that we safely 483 * read the value of pt_mutexnext before 'thread' 484 * sees pt_mutexwait being cleared. 485 */ 486 for (n = self->pt_nwaiters, self->pt_nwaiters = 0; 487 n < pthread__unpark_max && thread != NULL; 488 thread = next) { 489 next = thread->pt_mutexnext; 490 if (thread != self) { 491 self->pt_waiters[n++] = thread->pt_lid; 492 membar_sync(); 493 } 494 thread->pt_mutexwait = 0; 495 /* No longer safe to touch 'thread' */ 496 } 497 498 switch (n) { 499 case 0: 500 return; 501 case 1: 502 /* 503 * If the calling thread is about to block, 504 * defer unparking the target until _lwp_park() 505 * is called. 506 */ 507 if (self->pt_willpark && self->pt_unpark == 0) { 508 self->pt_unpark = self->pt_waiters[0]; 509 return; 510 } 511 rv = (ssize_t)_lwp_unpark(self->pt_waiters[0], 512 __UNVOLATILE(&ptm->ptm_waiters)); 513 if (rv != 0 && errno != EALREADY && errno != EINTR && 514 errno != ESRCH) { 515 pthread__errorfunc(__FILE__, __LINE__, 516 __func__, "_lwp_unpark failed"); 517 } 518 return; 519 default: 520 rv = _lwp_unpark_all(self->pt_waiters, (size_t)n, 521 __UNVOLATILE(&ptm->ptm_waiters)); 522 if (rv != 0 && errno != EINTR) { 523 pthread__errorfunc(__FILE__, __LINE__, 524 __func__, "_lwp_unpark_all failed"); 525 } 526 break; 527 } 528 } 529 } 530 int 531 pthread_mutexattr_init(pthread_mutexattr_t *attr) 532 { 533 534 attr->ptma_magic = _PT_MUTEXATTR_MAGIC; 535 attr->ptma_private = (void *)PTHREAD_MUTEX_DEFAULT; 536 return 0; 537 } 538 539 int 540 pthread_mutexattr_destroy(pthread_mutexattr_t *attr) 541 { 542 543 pthread__error(EINVAL, "Invalid mutex attribute", 544 attr->ptma_magic == _PT_MUTEXATTR_MAGIC); 545 546 return 0; 547 } 548 549 int 550 pthread_mutexattr_gettype(const pthread_mutexattr_t *attr, int *typep) 551 { 552 553 pthread__error(EINVAL, "Invalid mutex attribute", 554 attr->ptma_magic == _PT_MUTEXATTR_MAGIC); 555 556 *typep = (int)(intptr_t)attr->ptma_private; 557 return 0; 558 } 559 560 int 561 pthread_mutexattr_settype(pthread_mutexattr_t *attr, int type) 562 { 563 564 pthread__error(EINVAL, "Invalid mutex attribute", 565 attr->ptma_magic == _PT_MUTEXATTR_MAGIC); 566 567 switch (type) { 568 case PTHREAD_MUTEX_NORMAL: 569 case PTHREAD_MUTEX_ERRORCHECK: 570 case PTHREAD_MUTEX_RECURSIVE: 571 attr->ptma_private = (void *)(intptr_t)type; 572 return 0; 573 default: 574 return EINVAL; 575 } 576 } 577 578 void 579 pthread__mutex_deferwake(pthread_t self, pthread_mutex_t *ptm) 580 { 581 582 if (__predict_false(ptm == NULL || 583 MUTEX_OWNER(ptm->ptm_owner) != (uintptr_t)self)) { 584 (void)_lwp_unpark_all(self->pt_waiters, self->pt_nwaiters, 585 __UNVOLATILE(&ptm->ptm_waiters)); 586 self->pt_nwaiters = 0; 587 } else { 588 atomic_or_ulong((volatile unsigned long *) 589 (uintptr_t)&ptm->ptm_owner, 590 (unsigned long)MUTEX_DEFERRED_BIT); 591 } 592 } 593 594 int 595 _pthread_mutex_held_np(pthread_mutex_t *ptm) 596 { 597 598 return MUTEX_OWNER(ptm->ptm_owner) == (uintptr_t)pthread__self(); 599 } 600 601 pthread_t 602 _pthread_mutex_owner_np(pthread_mutex_t *ptm) 603 { 604 605 return (pthread_t)MUTEX_OWNER(ptm->ptm_owner); 606 } 607