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