Sync.cpp revision b31b30131bbf58280a515c40027aa958b81b5cd6
1/* 2 * Copyright (C) 2008 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17/* 18 * Fundamental synchronization mechanisms. 19 * 20 * The top part of the file has operations on "monitor" structs; the 21 * next part has the native calls on objects. 22 * 23 * The current implementation uses "thin locking" to avoid allocating 24 * an Object's full Monitor struct until absolutely necessary (i.e., 25 * during contention or a call to wait()). 26 * 27 * TODO: make improvements to thin locking 28 * We may be able to improve performance and reduce memory requirements by: 29 * - reverting to a thin lock once the Monitor is no longer necessary 30 * - using a pool of monitor objects, with some sort of recycling scheme 31 * 32 * TODO: recycle native-level monitors when objects are garbage collected. 33 */ 34#include "Dalvik.h" 35 36#include <fcntl.h> 37#include <stdlib.h> 38#include <unistd.h> 39#include <pthread.h> 40#include <time.h> 41#include <sys/time.h> 42#include <errno.h> 43 44#define LOG_THIN LOGV 45 46#ifdef WITH_DEADLOCK_PREDICTION /* fwd */ 47static const char* kStartBanner = 48 "<-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#"; 49static const char* kEndBanner = 50 "#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#->"; 51 52/* 53 * Unsorted, expanding list of objects. 54 * 55 * This is very similar to PointerSet (which came into existence after this), 56 * but these are unsorted, uniqueness is not enforced by the "add" function, 57 * and the base object isn't allocated on the heap. 58 */ 59typedef struct ExpandingObjectList { 60 u2 alloc; 61 u2 count; 62 Object** list; 63} ExpandingObjectList; 64 65/* fwd */ 66static void updateDeadlockPrediction(Thread* self, Object* obj); 67static void removeCollectedObject(Object* obj); 68static void expandObjClear(ExpandingObjectList* pList); 69#endif 70 71/* 72 * Every Object has a monitor associated with it, but not every Object is 73 * actually locked. Even the ones that are locked do not need a 74 * full-fledged monitor until a) there is actual contention or b) wait() 75 * is called on the Object. 76 * 77 * For Dalvik, we have implemented a scheme similar to the one described 78 * in Bacon et al.'s "Thin locks: featherweight synchronization for Java" 79 * (ACM 1998). Things are even easier for us, though, because we have 80 * a full 32 bits to work with. 81 * 82 * The two states of an Object's lock are referred to as "thin" and 83 * "fat". A lock may transition from the "thin" state to the "fat" 84 * state and this transition is referred to as inflation. Once a lock 85 * has been inflated it remains in the "fat" state indefinitely. 86 * 87 * The lock value itself is stored in Object.lock. The LSB of the 88 * lock encodes its state. When cleared, the lock is in the "thin" 89 * state and its bits are formatted as follows: 90 * 91 * [31 ---- 19] [18 ---- 3] [2 ---- 1] [0] 92 * lock count thread id hash state 0 93 * 94 * When set, the lock is in the "fat" state and its bits are formatted 95 * as follows: 96 * 97 * [31 ---- 3] [2 ---- 1] [0] 98 * pointer hash state 1 99 * 100 * For an in-depth description of the mechanics of thin-vs-fat locking, 101 * read the paper referred to above. 102 */ 103 104/* 105 * Monitors provide: 106 * - mutually exclusive access to resources 107 * - a way for multiple threads to wait for notification 108 * 109 * In effect, they fill the role of both mutexes and condition variables. 110 * 111 * Only one thread can own the monitor at any time. There may be several 112 * threads waiting on it (the wait call unlocks it). One or more waiting 113 * threads may be getting interrupted or notified at any given time. 114 */ 115struct Monitor { 116 Thread* owner; /* which thread currently owns the lock? */ 117 int lockCount; /* owner's recursive lock depth */ 118 Object* obj; /* what object are we part of [debug only] */ 119 120 Thread* waitSet; /* threads currently waiting on this monitor */ 121 122 pthread_mutex_t lock; 123 124 Monitor* next; 125 126#ifdef WITH_DEADLOCK_PREDICTION 127 /* 128 * Objects that have been locked immediately after this one in the 129 * past. We use an expanding flat array, allocated on first use, to 130 * minimize allocations. Deletions from the list, expected to be 131 * infrequent, are crunched down. 132 */ 133 ExpandingObjectList historyChildren; 134 135 /* 136 * We also track parents. This isn't strictly necessary, but it makes 137 * the cleanup at GC time significantly faster. 138 */ 139 ExpandingObjectList historyParents; 140 141 /* used during cycle detection */ 142 bool historyMark; 143 144 /* stack trace, established the first time we locked the object */ 145 int historyStackDepth; 146 int* historyRawStackTrace; 147#endif 148}; 149 150 151/* 152 * Create and initialize a monitor. 153 */ 154Monitor* dvmCreateMonitor(Object* obj) 155{ 156 Monitor* mon; 157 158 mon = (Monitor*) calloc(1, sizeof(Monitor)); 159 if (mon == NULL) { 160 LOGE("Unable to allocate monitor\n"); 161 dvmAbort(); 162 } 163 if (((u4)mon & 7) != 0) { 164 LOGE("Misaligned monitor: %p\n", mon); 165 dvmAbort(); 166 } 167 mon->obj = obj; 168 dvmInitMutex(&mon->lock); 169 170 /* replace the head of the list with the new monitor */ 171 do { 172 mon->next = gDvm.monitorList; 173 } while (!ATOMIC_CMP_SWAP((int32_t*)(void*)&gDvm.monitorList, 174 (int32_t)mon->next, (int32_t)mon)); 175 176 return mon; 177} 178 179/* 180 * Free the monitor list. Only used when shutting the VM down. 181 */ 182void dvmFreeMonitorList(void) 183{ 184 Monitor* mon; 185 Monitor* nextMon; 186 187 mon = gDvm.monitorList; 188 while (mon != NULL) { 189 nextMon = mon->next; 190 191#ifdef WITH_DEADLOCK_PREDICTION 192 expandObjClear(&mon->historyChildren); 193 expandObjClear(&mon->historyParents); 194 free(mon->historyRawStackTrace); 195#endif 196 free(mon); 197 mon = nextMon; 198 } 199} 200 201/* 202 * Log some info about our monitors. 203 */ 204void dvmDumpMonitorInfo(const char* msg) 205{ 206#if QUIET_ZYGOTE_MONITOR 207 if (gDvm.zygote) { 208 return; 209 } 210#endif 211 212 int totalCount; 213 int liveCount; 214 215 totalCount = liveCount = 0; 216 Monitor* mon = gDvm.monitorList; 217 while (mon != NULL) { 218 totalCount++; 219 if (mon->obj != NULL) 220 liveCount++; 221 mon = mon->next; 222 } 223 224 LOGD("%s: monitor list has %d entries (%d live)\n", 225 msg, totalCount, liveCount); 226} 227 228/* 229 * Get the object that a monitor is part of. 230 */ 231Object* dvmGetMonitorObject(Monitor* mon) 232{ 233 if (mon == NULL) 234 return NULL; 235 else 236 return mon->obj; 237} 238 239/* 240 * Returns the thread id of the thread owning the given lock. 241 */ 242static u4 lockOwner(Object* obj) 243{ 244 Thread *owner; 245 u4 lock; 246 247 assert(obj != NULL); 248 /* 249 * Since we're reading the lock value multiple times, latch it so 250 * that it doesn't change out from under us if we get preempted. 251 */ 252 lock = obj->lock; 253 if (LW_SHAPE(lock) == LW_SHAPE_THIN) { 254 return LW_LOCK_OWNER(lock); 255 } else { 256 owner = LW_MONITOR(lock)->owner; 257 return owner ? owner->threadId : 0; 258 } 259} 260 261/* 262 * Get the thread that holds the lock on the specified object. The 263 * object may be unlocked, thin-locked, or fat-locked. 264 * 265 * The caller must lock the thread list before calling here. 266 */ 267Thread* dvmGetObjectLockHolder(Object* obj) 268{ 269 u4 threadId = lockOwner(obj); 270 271 if (threadId == 0) 272 return NULL; 273 return dvmGetThreadByThreadId(threadId); 274} 275 276/* 277 * Checks whether the given thread holds the given 278 * objects's lock. 279 */ 280bool dvmHoldsLock(Thread* thread, Object* obj) 281{ 282 if (thread == NULL || obj == NULL) { 283 return false; 284 } else { 285 return thread->threadId == lockOwner(obj); 286 } 287} 288 289/* 290 * Free the monitor associated with an object and make the object's lock 291 * thin again. This is called during garbage collection. 292 */ 293static void freeObjectMonitor(Object* obj) 294{ 295 Monitor *mon; 296 297 assert(LW_SHAPE(obj->lock) == LW_SHAPE_FAT); 298 299#ifdef WITH_DEADLOCK_PREDICTION 300 if (gDvm.deadlockPredictMode != kDPOff) 301 removeCollectedObject(obj); 302#endif 303 304 mon = LW_MONITOR(obj->lock); 305 obj->lock = DVM_LOCK_INITIAL_THIN_VALUE; 306 307 /* This lock is associated with an object 308 * that's being swept. The only possible way 309 * anyone could be holding this lock would be 310 * if some JNI code locked but didn't unlock 311 * the object, in which case we've got some bad 312 * native code somewhere. 313 */ 314 assert(pthread_mutex_trylock(&mon->lock) == 0); 315 assert(pthread_mutex_unlock(&mon->lock) == 0); 316 dvmDestroyMutex(&mon->lock); 317#ifdef WITH_DEADLOCK_PREDICTION 318 expandObjClear(&mon->historyChildren); 319 expandObjClear(&mon->historyParents); 320 free(mon->historyRawStackTrace); 321#endif 322 free(mon); 323} 324 325/* 326 * Frees monitor objects belonging to unmarked objects. 327 */ 328void dvmSweepMonitorList(Monitor** mon, int (*isUnmarkedObject)(void*)) 329{ 330 Monitor handle; 331 Monitor *prev, *curr; 332 Object *obj; 333 334 assert(mon != NULL); 335 assert(isUnmarkedObject != NULL); 336 prev = &handle; 337 prev->next = curr = *mon; 338 while (curr != NULL) { 339 obj = curr->obj; 340 if (obj != NULL && (*isUnmarkedObject)(obj) != 0) { 341 prev->next = curr = curr->next; 342 freeObjectMonitor(obj); 343 } else { 344 prev = curr; 345 curr = curr->next; 346 } 347 } 348 *mon = handle.next; 349} 350 351static char *logWriteInt(char *dst, int value) 352{ 353 *dst++ = EVENT_TYPE_INT; 354 set4LE((u1 *)dst, value); 355 return dst + 4; 356} 357 358static char *logWriteString(char *dst, const char *value, size_t len) 359{ 360 *dst++ = EVENT_TYPE_STRING; 361 len = len < 32 ? len : 32; 362 set4LE((u1 *)dst, len); 363 dst += 4; 364 memcpy(dst, value, len); 365 return dst + len; 366} 367 368#define EVENT_LOG_TAG_dvm_lock_sample 20003 369 370static void logContentionEvent(Thread *self, u4 waitMs, u4 samplePercent) 371{ 372 const StackSaveArea *saveArea; 373 const Method *meth; 374 u4 relativePc; 375 char eventBuffer[132]; 376 const char *fileName; 377 char procName[33], *selfName; 378 char *cp; 379 size_t len; 380 int fd; 381 382 saveArea = SAVEAREA_FROM_FP(self->curFrame); 383 meth = saveArea->method; 384 cp = eventBuffer; 385 386 /* Emit the event list length, 1 byte. */ 387 *cp++ = 7; 388 389 /* Emit the process name, <= 37 bytes. */ 390 fd = open("/proc/self/cmdline", O_RDONLY); 391 memset(procName, 0, sizeof(procName)); 392 read(fd, procName, sizeof(procName) - 1); 393 close(fd); 394 len = strlen(procName); 395 cp = logWriteString(cp, procName, len); 396 397 /* Emit the main thread status, 5 bytes. */ 398 bool isMainThread = (self->systemTid == getpid()); 399 cp = logWriteInt(cp, isMainThread); 400 401 /* Emit self thread name string, <= 37 bytes. */ 402 selfName = dvmGetThreadName(self); 403 cp = logWriteString(cp, selfName, strlen(selfName)); 404 free(selfName); 405 406 /* Emit the wait time, 5 bytes. */ 407 cp = logWriteInt(cp, waitMs); 408 409 /* Emit the source code file name, <= 37 bytes. */ 410 fileName = dvmGetMethodSourceFile(meth); 411 if (fileName == NULL) fileName = ""; 412 cp = logWriteString(cp, fileName, strlen(fileName)); 413 414 /* Emit the source code line number, 5 bytes. */ 415 relativePc = saveArea->xtra.currentPc - saveArea->method->insns; 416 cp = logWriteInt(cp, dvmLineNumFromPC(meth, relativePc)); 417 418 /* Emit the sample percentage, 5 bytes. */ 419 cp = logWriteInt(cp, samplePercent); 420 421 assert((size_t)(cp - eventBuffer) <= sizeof(eventBuffer)); 422 android_btWriteLog(EVENT_LOG_TAG_dvm_lock_sample, 423 EVENT_TYPE_LIST, 424 eventBuffer, 425 (size_t)(cp - eventBuffer)); 426} 427 428/* 429 * Lock a monitor. 430 */ 431static void lockMonitor(Thread* self, Monitor* mon) 432{ 433 ThreadStatus oldStatus; 434 u4 waitThreshold, samplePercent; 435 u8 waitStart, waitEnd, waitMs; 436 437 if (mon->owner == self) { 438 mon->lockCount++; 439 return; 440 } 441 if (dvmTryLockMutex(&mon->lock) != 0) { 442 oldStatus = dvmChangeStatus(self, THREAD_MONITOR); 443 waitThreshold = gDvm.lockProfThreshold; 444 if (waitThreshold) { 445 waitStart = dvmGetRelativeTimeUsec(); 446 } 447 dvmLockMutex(&mon->lock); 448 if (waitThreshold) { 449 waitEnd = dvmGetRelativeTimeUsec(); 450 } 451 dvmChangeStatus(self, oldStatus); 452 if (waitThreshold) { 453 waitMs = (waitEnd - waitStart) / 1000; 454 if (waitMs >= waitThreshold) { 455 samplePercent = 100; 456 } else { 457 samplePercent = 100 * waitMs / waitThreshold; 458 } 459 if (samplePercent != 0 && ((u4)rand() % 100 < samplePercent)) { 460 logContentionEvent(self, waitMs, samplePercent); 461 } 462 } 463 } 464 mon->owner = self; 465 assert(mon->lockCount == 0); 466} 467 468/* 469 * Try to lock a monitor. 470 * 471 * Returns "true" on success. 472 */ 473#ifdef WITH_COPYING_GC 474static bool tryLockMonitor(Thread* self, Monitor* mon) 475{ 476 if (mon->owner == self) { 477 mon->lockCount++; 478 return true; 479 } else { 480 if (dvmTryLockMutex(&mon->lock) == 0) { 481 mon->owner = self; 482 assert(mon->lockCount == 0); 483 return true; 484 } else { 485 return false; 486 } 487 } 488} 489#endif 490 491/* 492 * Unlock a monitor. 493 * 494 * Returns true if the unlock succeeded. 495 * If the unlock failed, an exception will be pending. 496 */ 497static bool unlockMonitor(Thread* self, Monitor* mon) 498{ 499 assert(self != NULL); 500 assert(mon != NULL); 501 if (mon->owner == self) { 502 /* 503 * We own the monitor, so nobody else can be in here. 504 */ 505 if (mon->lockCount == 0) { 506 mon->owner = NULL; 507 dvmUnlockMutex(&mon->lock); 508 } else { 509 mon->lockCount--; 510 } 511 } else { 512 /* 513 * We don't own this, so we're not allowed to unlock it. 514 * The JNI spec says that we should throw IllegalMonitorStateException 515 * in this case. 516 */ 517 dvmThrowException("Ljava/lang/IllegalMonitorStateException;", 518 "unlock of unowned monitor"); 519 return false; 520 } 521 return true; 522} 523 524/* 525 * Checks the wait set for circular structure. Returns 0 if the list 526 * is not circular. Otherwise, returns 1. Used only by asserts. 527 */ 528#ifndef NDEBUG 529static int waitSetCheck(Monitor *mon) 530{ 531 Thread *fast, *slow; 532 size_t n; 533 534 assert(mon != NULL); 535 fast = slow = mon->waitSet; 536 n = 0; 537 for (;;) { 538 if (fast == NULL) return 0; 539 if (fast->waitNext == NULL) return 0; 540 if (fast == slow && n > 0) return 1; 541 n += 2; 542 fast = fast->waitNext->waitNext; 543 slow = slow->waitNext; 544 } 545} 546#endif 547 548/* 549 * Links a thread into a monitor's wait set. The monitor lock must be 550 * held by the caller of this routine. 551 */ 552static void waitSetAppend(Monitor *mon, Thread *thread) 553{ 554 Thread *elt; 555 556 assert(mon != NULL); 557 assert(mon->owner == dvmThreadSelf()); 558 assert(thread != NULL); 559 assert(thread->waitNext == NULL); 560 assert(waitSetCheck(mon) == 0); 561 if (mon->waitSet == NULL) { 562 mon->waitSet = thread; 563 return; 564 } 565 elt = mon->waitSet; 566 while (elt->waitNext != NULL) { 567 elt = elt->waitNext; 568 } 569 elt->waitNext = thread; 570} 571 572/* 573 * Unlinks a thread from a monitor's wait set. The monitor lock must 574 * be held by the caller of this routine. 575 */ 576static void waitSetRemove(Monitor *mon, Thread *thread) 577{ 578 Thread *elt; 579 580 assert(mon != NULL); 581 assert(mon->owner == dvmThreadSelf()); 582 assert(thread != NULL); 583 assert(waitSetCheck(mon) == 0); 584 if (mon->waitSet == NULL) { 585 return; 586 } 587 if (mon->waitSet == thread) { 588 mon->waitSet = thread->waitNext; 589 thread->waitNext = NULL; 590 return; 591 } 592 elt = mon->waitSet; 593 while (elt->waitNext != NULL) { 594 if (elt->waitNext == thread) { 595 elt->waitNext = thread->waitNext; 596 thread->waitNext = NULL; 597 return; 598 } 599 elt = elt->waitNext; 600 } 601} 602 603/* 604 * Converts the given relative waiting time into an absolute time. 605 */ 606void absoluteTime(s8 msec, s4 nsec, struct timespec *ts) 607{ 608 s8 endSec; 609 610#ifdef HAVE_TIMEDWAIT_MONOTONIC 611 clock_gettime(CLOCK_MONOTONIC, ts); 612#else 613 { 614 struct timeval tv; 615 gettimeofday(&tv, NULL); 616 ts->tv_sec = tv.tv_sec; 617 ts->tv_nsec = tv.tv_usec * 1000; 618 } 619#endif 620 endSec = ts->tv_sec + msec / 1000; 621 if (endSec >= 0x7fffffff) { 622 LOGV("NOTE: end time exceeds epoch\n"); 623 endSec = 0x7ffffffe; 624 } 625 ts->tv_sec = endSec; 626 ts->tv_nsec = (ts->tv_nsec + (msec % 1000) * 1000000) + nsec; 627 628 /* catch rollover */ 629 if (ts->tv_nsec >= 1000000000L) { 630 ts->tv_sec++; 631 ts->tv_nsec -= 1000000000L; 632 } 633} 634 635int dvmRelativeCondWait(pthread_cond_t* cond, pthread_mutex_t* mutex, 636 s8 msec, s4 nsec) 637{ 638 int ret; 639 struct timespec ts; 640 absoluteTime(msec, nsec, &ts); 641#if defined(HAVE_TIMEDWAIT_MONOTONIC) 642 ret = pthread_cond_timedwait_monotonic(cond, mutex, &ts); 643#else 644 ret = pthread_cond_timedwait(cond, mutex, &ts); 645#endif 646 assert(ret == 0 || ret == ETIMEDOUT); 647 return ret; 648} 649 650/* 651 * Wait on a monitor until timeout, interrupt, or notification. Used for 652 * Object.wait() and (somewhat indirectly) Thread.sleep() and Thread.join(). 653 * 654 * If another thread calls Thread.interrupt(), we throw InterruptedException 655 * and return immediately if one of the following are true: 656 * - blocked in wait(), wait(long), or wait(long, int) methods of Object 657 * - blocked in join(), join(long), or join(long, int) methods of Thread 658 * - blocked in sleep(long), or sleep(long, int) methods of Thread 659 * Otherwise, we set the "interrupted" flag. 660 * 661 * Checks to make sure that "nsec" is in the range 0-999999 662 * (i.e. fractions of a millisecond) and throws the appropriate 663 * exception if it isn't. 664 * 665 * The spec allows "spurious wakeups", and recommends that all code using 666 * Object.wait() do so in a loop. This appears to derive from concerns 667 * about pthread_cond_wait() on multiprocessor systems. Some commentary 668 * on the web casts doubt on whether these can/should occur. 669 * 670 * Since we're allowed to wake up "early", we clamp extremely long durations 671 * to return at the end of the 32-bit time epoch. 672 */ 673static void waitMonitor(Thread* self, Monitor* mon, s8 msec, s4 nsec, 674 bool interruptShouldThrow) 675{ 676 struct timespec ts; 677 bool wasInterrupted = false; 678 bool timed; 679 int ret; 680 681 assert(self != NULL); 682 assert(mon != NULL); 683 684 /* Make sure that we hold the lock. */ 685 if (mon->owner != self) { 686 dvmThrowException("Ljava/lang/IllegalMonitorStateException;", 687 "object not locked by thread before wait()"); 688 return; 689 } 690 691 /* 692 * Enforce the timeout range. 693 */ 694 if (msec < 0 || nsec < 0 || nsec > 999999) { 695 dvmThrowException("Ljava/lang/IllegalArgumentException;", 696 "timeout arguments out of range"); 697 return; 698 } 699 700 /* 701 * Compute absolute wakeup time, if necessary. 702 */ 703 if (msec == 0 && nsec == 0) { 704 timed = false; 705 } else { 706 absoluteTime(msec, nsec, &ts); 707 timed = true; 708 } 709 710 /* 711 * Add ourselves to the set of threads waiting on this monitor, and 712 * release our hold. We need to let it go even if we're a few levels 713 * deep in a recursive lock, and we need to restore that later. 714 * 715 * We append to the wait set ahead of clearing the count and owner 716 * fields so the subroutine can check that the calling thread owns 717 * the monitor. Aside from that, the order of member updates is 718 * not order sensitive as we hold the pthread mutex. 719 */ 720 waitSetAppend(mon, self); 721 int prevLockCount = mon->lockCount; 722 mon->lockCount = 0; 723 mon->owner = NULL; 724 725 /* 726 * Update thread status. If the GC wakes up, it'll ignore us, knowing 727 * that we won't touch any references in this state, and we'll check 728 * our suspend mode before we transition out. 729 */ 730 if (timed) 731 dvmChangeStatus(self, THREAD_TIMED_WAIT); 732 else 733 dvmChangeStatus(self, THREAD_WAIT); 734 735 dvmLockMutex(&self->waitMutex); 736 737 /* 738 * Set waitMonitor to the monitor object we will be waiting on. 739 * When waitMonitor is non-NULL a notifying or interrupting thread 740 * must signal the thread's waitCond to wake it up. 741 */ 742 assert(self->waitMonitor == NULL); 743 self->waitMonitor = mon; 744 745 /* 746 * Handle the case where the thread was interrupted before we called 747 * wait(). 748 */ 749 if (self->interrupted) { 750 wasInterrupted = true; 751 self->waitMonitor = NULL; 752 dvmUnlockMutex(&self->waitMutex); 753 goto done; 754 } 755 756 /* 757 * Release the monitor lock and wait for a notification or 758 * a timeout to occur. 759 */ 760 dvmUnlockMutex(&mon->lock); 761 762 if (!timed) { 763 ret = pthread_cond_wait(&self->waitCond, &self->waitMutex); 764 assert(ret == 0); 765 } else { 766#ifdef HAVE_TIMEDWAIT_MONOTONIC 767 ret = pthread_cond_timedwait_monotonic(&self->waitCond, &self->waitMutex, &ts); 768#else 769 ret = pthread_cond_timedwait(&self->waitCond, &self->waitMutex, &ts); 770#endif 771 assert(ret == 0 || ret == ETIMEDOUT); 772 } 773 if (self->interrupted) { 774 wasInterrupted = true; 775 } 776 777 self->interrupted = false; 778 self->waitMonitor = NULL; 779 780 dvmUnlockMutex(&self->waitMutex); 781 782 /* Reacquire the monitor lock. */ 783 lockMonitor(self, mon); 784 785done: 786 /* 787 * We remove our thread from wait set after restoring the count 788 * and owner fields so the subroutine can check that the calling 789 * thread owns the monitor. Aside from that, the order of member 790 * updates is not order sensitive as we hold the pthread mutex. 791 */ 792 mon->owner = self; 793 mon->lockCount = prevLockCount; 794 waitSetRemove(mon, self); 795 796 /* set self->status back to THREAD_RUNNING, and self-suspend if needed */ 797 dvmChangeStatus(self, THREAD_RUNNING); 798 799 if (wasInterrupted) { 800 /* 801 * We were interrupted while waiting, or somebody interrupted an 802 * un-interruptible thread earlier and we're bailing out immediately. 803 * 804 * The doc sayeth: "The interrupted status of the current thread is 805 * cleared when this exception is thrown." 806 */ 807 self->interrupted = false; 808 if (interruptShouldThrow) 809 dvmThrowException("Ljava/lang/InterruptedException;", NULL); 810 } 811} 812 813/* 814 * Notify one thread waiting on this monitor. 815 */ 816static void notifyMonitor(Thread* self, Monitor* mon) 817{ 818 Thread* thread; 819 820 assert(self != NULL); 821 assert(mon != NULL); 822 823 /* Make sure that we hold the lock. */ 824 if (mon->owner != self) { 825 dvmThrowException("Ljava/lang/IllegalMonitorStateException;", 826 "object not locked by thread before notify()"); 827 return; 828 } 829 /* Signal the first waiting thread in the wait set. */ 830 while (mon->waitSet != NULL) { 831 thread = mon->waitSet; 832 mon->waitSet = thread->waitNext; 833 thread->waitNext = NULL; 834 dvmLockMutex(&thread->waitMutex); 835 /* Check to see if the thread is still waiting. */ 836 if (thread->waitMonitor != NULL) { 837 pthread_cond_signal(&thread->waitCond); 838 dvmUnlockMutex(&thread->waitMutex); 839 return; 840 } 841 dvmUnlockMutex(&thread->waitMutex); 842 } 843} 844 845/* 846 * Notify all threads waiting on this monitor. 847 */ 848static void notifyAllMonitor(Thread* self, Monitor* mon) 849{ 850 Thread* thread; 851 852 assert(self != NULL); 853 assert(mon != NULL); 854 855 /* Make sure that we hold the lock. */ 856 if (mon->owner != self) { 857 dvmThrowException("Ljava/lang/IllegalMonitorStateException;", 858 "object not locked by thread before notifyAll()"); 859 return; 860 } 861 /* Signal all threads in the wait set. */ 862 while (mon->waitSet != NULL) { 863 thread = mon->waitSet; 864 mon->waitSet = thread->waitNext; 865 thread->waitNext = NULL; 866 dvmLockMutex(&thread->waitMutex); 867 /* Check to see if the thread is still waiting. */ 868 if (thread->waitMonitor != NULL) { 869 pthread_cond_signal(&thread->waitCond); 870 } 871 dvmUnlockMutex(&thread->waitMutex); 872 } 873} 874 875/* 876 * Changes the shape of a monitor from thin to fat, preserving the 877 * internal lock state. The calling thread must own the lock. 878 */ 879static void inflateMonitor(Thread *self, Object *obj) 880{ 881 Monitor *mon; 882 u4 thin; 883 884 assert(self != NULL); 885 assert(obj != NULL); 886 assert(LW_SHAPE(obj->lock) == LW_SHAPE_THIN); 887 assert(LW_LOCK_OWNER(obj->lock) == self->threadId); 888 /* Allocate and acquire a new monitor. */ 889 mon = dvmCreateMonitor(obj); 890 lockMonitor(self, mon); 891 /* Propagate the lock state. */ 892 thin = obj->lock; 893 mon->lockCount = LW_LOCK_COUNT(thin); 894 thin &= LW_HASH_STATE_MASK << LW_HASH_STATE_SHIFT; 895 thin |= (u4)mon | LW_SHAPE_FAT; 896 /* Publish the updated lock word. */ 897 MEM_BARRIER(); 898 obj->lock = thin; 899} 900 901/* 902 * Implements monitorenter for "synchronized" stuff. 903 * 904 * This does not fail or throw an exception (unless deadlock prediction 905 * is enabled and set to "err" mode). 906 */ 907void dvmLockObject(Thread* self, Object *obj) 908{ 909 volatile u4 *thinp; 910 ThreadStatus oldStatus; 911 useconds_t sleepDelay; 912 const useconds_t maxSleepDelay = 1 << 20; 913 u4 thin, newThin, threadId; 914 915 assert(self != NULL); 916 assert(obj != NULL); 917 threadId = self->threadId; 918 thinp = &obj->lock; 919retry: 920 thin = *thinp; 921 if (LW_SHAPE(thin) == LW_SHAPE_THIN) { 922 /* 923 * The lock is a thin lock. The owner field is used to 924 * determine the acquire method, ordered by cost. 925 */ 926 if (LW_LOCK_OWNER(thin) == threadId) { 927 /* 928 * The calling thread owns the lock. Increment the 929 * value of the recursion count field. 930 */ 931 obj->lock += 1 << LW_LOCK_COUNT_SHIFT; 932 } else if (LW_LOCK_OWNER(thin) == 0) { 933 /* 934 * The lock is unowned. Install the thread id of the 935 * calling thread into the owner field. This is the 936 * common case. In performance critical code the JIT 937 * will have tried this before calling out to the VM. 938 */ 939 newThin = thin | (threadId << LW_LOCK_OWNER_SHIFT); 940 if (!ATOMIC_CMP_SWAP((int32_t *)thinp, thin, newThin)) { 941 /* 942 * The acquire failed. Try again. 943 */ 944 goto retry; 945 } 946 } else { 947 LOG_THIN("(%d) spin on lock %p: %#x (%#x) %#x", 948 threadId, &obj->lock, 0, *thinp, thin); 949 /* 950 * The lock is owned by another thread. Notify the VM 951 * that we are about to wait. 952 */ 953 oldStatus = dvmChangeStatus(self, THREAD_MONITOR); 954 /* 955 * Spin until the thin lock is released or inflated. 956 */ 957 sleepDelay = 0; 958 for (;;) { 959 thin = *thinp; 960 /* 961 * Check the shape of the lock word. Another thread 962 * may have inflated the lock while we were waiting. 963 */ 964 if (LW_SHAPE(thin) == LW_SHAPE_THIN) { 965 if (LW_LOCK_OWNER(thin) == 0) { 966 /* 967 * The lock has been released. Install the 968 * thread id of the calling thread into the 969 * owner field. 970 */ 971 newThin = thin | (threadId << LW_LOCK_OWNER_SHIFT); 972 if (ATOMIC_CMP_SWAP((int32_t *)thinp, 973 thin, newThin)) { 974 /* 975 * The acquire succeed. Break out of the 976 * loop and proceed to inflate the lock. 977 */ 978 break; 979 } 980 } else { 981 /* 982 * The lock has not been released. Yield so 983 * the owning thread can run. 984 */ 985 if (sleepDelay == 0) { 986 sched_yield(); 987 sleepDelay = 1000; 988 } else { 989 usleep(sleepDelay); 990 if (sleepDelay < maxSleepDelay / 2) { 991 sleepDelay *= 2; 992 } 993 } 994 } 995 } else { 996 /* 997 * The thin lock was inflated by another thread. 998 * Let the VM know we are no longer waiting and 999 * try again. 1000 */ 1001 LOG_THIN("(%d) lock %p surprise-fattened", 1002 threadId, &obj->lock); 1003 dvmChangeStatus(self, oldStatus); 1004 goto retry; 1005 } 1006 } 1007 LOG_THIN("(%d) spin on lock done %p: %#x (%#x) %#x", 1008 threadId, &obj->lock, 0, *thinp, thin); 1009 /* 1010 * We have acquired the thin lock. Let the VM know that 1011 * we are no longer waiting. 1012 */ 1013 dvmChangeStatus(self, oldStatus); 1014 /* 1015 * Fatten the lock. 1016 */ 1017 inflateMonitor(self, obj); 1018 LOG_THIN("(%d) lock %p fattened", threadId, &obj->lock); 1019 } 1020 } else { 1021 /* 1022 * The lock is a fat lock. 1023 */ 1024 assert(LW_MONITOR(obj->lock) != NULL); 1025 lockMonitor(self, LW_MONITOR(obj->lock)); 1026 } 1027#ifdef WITH_DEADLOCK_PREDICTION 1028 /* 1029 * See if we were allowed to grab the lock at this time. We do it 1030 * *after* acquiring the lock, rather than before, so that we can 1031 * freely update the Monitor struct. This seems counter-intuitive, 1032 * but our goal is deadlock *prediction* not deadlock *prevention*. 1033 * (If we actually deadlock, the situation is easy to diagnose from 1034 * a thread dump, so there's no point making a special effort to do 1035 * the checks before the lock is held.) 1036 * 1037 * This needs to happen before we add the object to the thread's 1038 * monitor list, so we can tell the difference between first-lock and 1039 * re-lock. 1040 * 1041 * It's also important that we do this while in THREAD_RUNNING, so 1042 * that we don't interfere with cleanup operations in the GC. 1043 */ 1044 if (gDvm.deadlockPredictMode != kDPOff) { 1045 if (self->status != THREAD_RUNNING) { 1046 LOGE("Bad thread status (%d) in DP\n", self->status); 1047 dvmDumpThread(self, false); 1048 dvmAbort(); 1049 } 1050 assert(!dvmCheckException(self)); 1051 updateDeadlockPrediction(self, obj); 1052 if (dvmCheckException(self)) { 1053 /* 1054 * If we're throwing an exception here, we need to free the 1055 * lock. We add the object to the thread's monitor list so the 1056 * "unlock" code can remove it. 1057 */ 1058 dvmAddToMonitorList(self, obj, false); 1059 dvmUnlockObject(self, obj); 1060 LOGV("--- unlocked, pending is '%s'\n", 1061 dvmGetException(self)->clazz->descriptor); 1062 } 1063 } 1064 1065 /* 1066 * Add the locked object, and the current stack trace, to the list 1067 * held by the Thread object. If deadlock prediction isn't on, 1068 * don't capture the stack trace. 1069 */ 1070 dvmAddToMonitorList(self, obj, gDvm.deadlockPredictMode != kDPOff); 1071#elif defined(WITH_MONITOR_TRACKING) 1072 /* 1073 * Add the locked object to the list held by the Thread object. 1074 */ 1075 dvmAddToMonitorList(self, obj, false); 1076#endif 1077} 1078 1079/* 1080 * Implements monitorexit for "synchronized" stuff. 1081 * 1082 * On failure, throws an exception and returns "false". 1083 */ 1084bool dvmUnlockObject(Thread* self, Object *obj) 1085{ 1086 u4 thin; 1087 1088 assert(self != NULL); 1089 assert(self->status == THREAD_RUNNING); 1090 assert(obj != NULL); 1091 /* 1092 * Cache the lock word as its value can change while we are 1093 * examining its state. 1094 */ 1095 thin = obj->lock; 1096 if (LW_SHAPE(thin) == LW_SHAPE_THIN) { 1097 /* 1098 * The lock is thin. We must ensure that the lock is owned 1099 * by the given thread before unlocking it. 1100 */ 1101 if (LW_LOCK_OWNER(thin) == self->threadId) { 1102 /* 1103 * We are the lock owner. It is safe to update the lock 1104 * without CAS as lock ownership guards the lock itself. 1105 */ 1106 if (LW_LOCK_COUNT(thin) == 0) { 1107 /* 1108 * The lock was not recursively acquired, the common 1109 * case. Unlock by clearing all bits except for the 1110 * hash state. 1111 */ 1112 obj->lock &= (LW_HASH_STATE_MASK << LW_HASH_STATE_SHIFT); 1113 } else { 1114 /* 1115 * The object was recursively acquired. Decrement the 1116 * lock recursion count field. 1117 */ 1118 obj->lock -= 1 << LW_LOCK_COUNT_SHIFT; 1119 } 1120 } else { 1121 /* 1122 * We do not own the lock. The JVM spec requires that we 1123 * throw an exception in this case. 1124 */ 1125 dvmThrowException("Ljava/lang/IllegalMonitorStateException;", 1126 "unlock of unowned monitor"); 1127 return false; 1128 } 1129 } else { 1130 /* 1131 * The lock is fat. We must check to see if unlockMonitor has 1132 * raised any exceptions before continuing. 1133 */ 1134 assert(LW_MONITOR(obj->lock) != NULL); 1135 if (!unlockMonitor(self, LW_MONITOR(obj->lock))) { 1136 /* 1137 * An exception has been raised. Do not fall through. 1138 */ 1139 return false; 1140 } 1141 } 1142 1143#ifdef WITH_MONITOR_TRACKING 1144 /* 1145 * Remove the object from the Thread's list. 1146 */ 1147 dvmRemoveFromMonitorList(self, obj); 1148#endif 1149 1150 return true; 1151} 1152 1153/* 1154 * Object.wait(). Also called for class init. 1155 */ 1156void dvmObjectWait(Thread* self, Object *obj, s8 msec, s4 nsec, 1157 bool interruptShouldThrow) 1158{ 1159 Monitor* mon; 1160 u4 thin = obj->lock; 1161 1162 /* If the lock is still thin, we need to fatten it. 1163 */ 1164 if (LW_SHAPE(thin) == LW_SHAPE_THIN) { 1165 /* Make sure that 'self' holds the lock. 1166 */ 1167 if (LW_LOCK_OWNER(thin) != self->threadId) { 1168 dvmThrowException("Ljava/lang/IllegalMonitorStateException;", 1169 "object not locked by thread before wait()"); 1170 return; 1171 } 1172 1173 /* This thread holds the lock. We need to fatten the lock 1174 * so 'self' can block on it. Don't update the object lock 1175 * field yet, because 'self' needs to acquire the lock before 1176 * any other thread gets a chance. 1177 */ 1178 inflateMonitor(self, obj); 1179 LOG_THIN("(%d) lock %p fattened by wait() to count %d", 1180 self->threadId, &obj->lock, mon->lockCount); 1181 } 1182 mon = LW_MONITOR(obj->lock); 1183 waitMonitor(self, mon, msec, nsec, interruptShouldThrow); 1184} 1185 1186/* 1187 * Object.notify(). 1188 */ 1189void dvmObjectNotify(Thread* self, Object *obj) 1190{ 1191 u4 thin = obj->lock; 1192 1193 /* If the lock is still thin, there aren't any waiters; 1194 * waiting on an object forces lock fattening. 1195 */ 1196 if (LW_SHAPE(thin) == LW_SHAPE_THIN) { 1197 /* Make sure that 'self' holds the lock. 1198 */ 1199 if (LW_LOCK_OWNER(thin) != self->threadId) { 1200 dvmThrowException("Ljava/lang/IllegalMonitorStateException;", 1201 "object not locked by thread before notify()"); 1202 return; 1203 } 1204 1205 /* no-op; there are no waiters to notify. 1206 */ 1207 } else { 1208 /* It's a fat lock. 1209 */ 1210 notifyMonitor(self, LW_MONITOR(thin)); 1211 } 1212} 1213 1214/* 1215 * Object.notifyAll(). 1216 */ 1217void dvmObjectNotifyAll(Thread* self, Object *obj) 1218{ 1219 u4 thin = obj->lock; 1220 1221 /* If the lock is still thin, there aren't any waiters; 1222 * waiting on an object forces lock fattening. 1223 */ 1224 if (LW_SHAPE(thin) == LW_SHAPE_THIN) { 1225 /* Make sure that 'self' holds the lock. 1226 */ 1227 if (LW_LOCK_OWNER(thin) != self->threadId) { 1228 dvmThrowException("Ljava/lang/IllegalMonitorStateException;", 1229 "object not locked by thread before notifyAll()"); 1230 return; 1231 } 1232 1233 /* no-op; there are no waiters to notify. 1234 */ 1235 } else { 1236 /* It's a fat lock. 1237 */ 1238 notifyAllMonitor(self, LW_MONITOR(thin)); 1239 } 1240} 1241 1242/* 1243 * This implements java.lang.Thread.sleep(long msec, int nsec). 1244 * 1245 * The sleep is interruptible by other threads, which means we can't just 1246 * plop into an OS sleep call. (We probably could if we wanted to send 1247 * signals around and rely on EINTR, but that's inefficient and relies 1248 * on native code respecting our signal mask.) 1249 * 1250 * We have to do all of this stuff for Object.wait() as well, so it's 1251 * easiest to just sleep on a private Monitor. 1252 * 1253 * It appears that we want sleep(0,0) to go through the motions of sleeping 1254 * for a very short duration, rather than just returning. 1255 */ 1256void dvmThreadSleep(u8 msec, u4 nsec) 1257{ 1258 Thread* self = dvmThreadSelf(); 1259 Monitor* mon = gDvm.threadSleepMon; 1260 1261 /* sleep(0,0) wakes up immediately, wait(0,0) means wait forever; adjust */ 1262 if (msec == 0 && nsec == 0) 1263 nsec++; 1264 1265 lockMonitor(self, mon); 1266 waitMonitor(self, mon, msec, nsec, true); 1267 unlockMonitor(self, mon); 1268} 1269 1270/* 1271 * Implement java.lang.Thread.interrupt(). 1272 */ 1273void dvmThreadInterrupt(Thread* thread) 1274{ 1275 assert(thread != NULL); 1276 1277 dvmLockMutex(&thread->waitMutex); 1278 1279 /* 1280 * If the interrupted flag is already set no additional action is 1281 * required. 1282 */ 1283 if (thread->interrupted == true) { 1284 dvmUnlockMutex(&thread->waitMutex); 1285 return; 1286 } 1287 1288 /* 1289 * Raise the "interrupted" flag. This will cause it to bail early out 1290 * of the next wait() attempt, if it's not currently waiting on 1291 * something. 1292 */ 1293 thread->interrupted = true; 1294 MEM_BARRIER(); 1295 1296 /* 1297 * Is the thread waiting? 1298 * 1299 * Note that fat vs. thin doesn't matter here; waitMonitor 1300 * is only set when a thread actually waits on a monitor, 1301 * which implies that the monitor has already been fattened. 1302 */ 1303 if (thread->waitMonitor != NULL) { 1304 pthread_cond_signal(&thread->waitCond); 1305 } 1306 1307 dvmUnlockMutex(&thread->waitMutex); 1308} 1309 1310#ifndef WITH_COPYING_GC 1311u4 dvmIdentityHashCode(Object *obj) 1312{ 1313 return (u4)obj; 1314} 1315#else 1316/* 1317 * Returns the identity hash code of the given object. 1318 */ 1319u4 dvmIdentityHashCode(Object *obj) 1320{ 1321 Thread *self, *thread; 1322 volatile u4 *lw; 1323 size_t size; 1324 u4 lock, owner, hashState; 1325 1326 if (obj == NULL) { 1327 /* 1328 * Null is defined to have an identity hash code of 0. 1329 */ 1330 return 0; 1331 } 1332 lw = &obj->lock; 1333retry: 1334 hashState = LW_HASH_STATE(*lw); 1335 if (hashState == LW_HASH_STATE_HASHED) { 1336 /* 1337 * The object has been hashed but has not had its hash code 1338 * relocated by the garbage collector. Use the raw object 1339 * address. 1340 */ 1341 return (u4)obj >> 3; 1342 } else if (hashState == LW_HASH_STATE_HASHED_AND_MOVED) { 1343 /* 1344 * The object has been hashed and its hash code has been 1345 * relocated by the collector. Use the value of the naturally 1346 * aligned word following the instance data. 1347 */ 1348 assert(obj->clazz != gDvm.classJavaLangClass); 1349 assert(obj->clazz != gDvm.unlinkedJavaLangClass); 1350 if (IS_CLASS_FLAG_SET(obj->clazz, CLASS_ISARRAY)) { 1351 size = dvmArrayObjectSize((ArrayObject *)obj); 1352 size = (size + 2) & ~2; 1353 } else { 1354 size = obj->clazz->objectSize; 1355 } 1356 return *(u4 *)(((char *)obj) + size); 1357 } else if (hashState == LW_HASH_STATE_UNHASHED) { 1358 /* 1359 * The object has never been hashed. Change the hash state to 1360 * hashed and use the raw object address. 1361 */ 1362 self = dvmThreadSelf(); 1363 if (self->threadId == lockOwner(obj)) { 1364 /* 1365 * We already own the lock so we can update the hash state 1366 * directly. 1367 */ 1368 *lw |= (LW_HASH_STATE_HASHED << LW_HASH_STATE_SHIFT); 1369 return (u4)obj >> 3; 1370 } 1371 /* 1372 * We do not own the lock. Try acquiring the lock. Should 1373 * this fail, we must suspend the owning thread. 1374 */ 1375 if (LW_SHAPE(*lw) == LW_SHAPE_THIN) { 1376 /* 1377 * If the lock is thin assume it is unowned. We simulate 1378 * an acquire, update, and release with a single CAS. 1379 */ 1380 lock = DVM_LOCK_INITIAL_THIN_VALUE; 1381 lock |= (LW_HASH_STATE_HASHED << LW_HASH_STATE_SHIFT); 1382 if (ATOMIC_CMP_SWAP((int32_t *)lw, 1383 (int32_t)DVM_LOCK_INITIAL_THIN_VALUE, 1384 (int32_t)lock)) { 1385 /* 1386 * A new lockword has been installed with a hash state 1387 * of hashed. Use the raw object address. 1388 */ 1389 return (u4)obj >> 3; 1390 } 1391 } else { 1392 if (tryLockMonitor(self, LW_MONITOR(*lw))) { 1393 /* 1394 * The monitor lock has been acquired. Change the 1395 * hash state to hashed and use the raw object 1396 * address. 1397 */ 1398 *lw |= (LW_HASH_STATE_HASHED << LW_HASH_STATE_SHIFT); 1399 unlockMonitor(self, LW_MONITOR(*lw)); 1400 return (u4)obj >> 3; 1401 } 1402 } 1403 /* 1404 * At this point we have failed to acquire the lock. We must 1405 * identify the owning thread and suspend it. 1406 */ 1407 dvmLockThreadList(self); 1408 /* 1409 * Cache the lock word as its value can change between 1410 * determining its shape and retrieving its owner. 1411 */ 1412 lock = *lw; 1413 if (LW_SHAPE(lock) == LW_SHAPE_THIN) { 1414 /* 1415 * Find the thread with the corresponding thread id. 1416 */ 1417 owner = LW_LOCK_OWNER(lock); 1418 assert(owner != self->threadId); 1419 /* 1420 * If the lock has no owner do not bother scanning the 1421 * thread list and fall through to the failure handler. 1422 */ 1423 thread = owner ? gDvm.threadList : NULL; 1424 while (thread != NULL) { 1425 if (thread->threadId == owner) { 1426 break; 1427 } 1428 thread = thread->next; 1429 } 1430 } else { 1431 thread = LW_MONITOR(lock)->owner; 1432 } 1433 /* 1434 * If thread is NULL the object has been released since the 1435 * thread list lock was acquired. Try again. 1436 */ 1437 if (thread == NULL) { 1438 dvmUnlockThreadList(); 1439 goto retry; 1440 } 1441 /* 1442 * Wait for the owning thread to suspend. 1443 */ 1444 dvmSuspendThread(thread); 1445 if (dvmHoldsLock(thread, obj)) { 1446 /* 1447 * The owning thread has been suspended. We can safely 1448 * change the hash state to hashed. 1449 */ 1450 *lw |= (LW_HASH_STATE_HASHED << LW_HASH_STATE_SHIFT); 1451 dvmResumeThread(thread); 1452 dvmUnlockThreadList(); 1453 return (u4)obj >> 3; 1454 } 1455 /* 1456 * The wrong thread has been suspended. Try again. 1457 */ 1458 dvmResumeThread(thread); 1459 dvmUnlockThreadList(); 1460 goto retry; 1461 } 1462 LOGE("object %p has an unknown hash state %#x", obj, hashState); 1463 dvmDumpThread(dvmThreadSelf(), false); 1464 dvmAbort(); 1465 return 0; /* Quiet the compiler. */ 1466} 1467#endif /* WITH_COPYING_GC */ 1468 1469#ifdef WITH_DEADLOCK_PREDICTION 1470/* 1471 * =========================================================================== 1472 * Deadlock prediction 1473 * =========================================================================== 1474 */ 1475/* 1476The idea is to predict the possibility of deadlock by recording the order 1477in which monitors are acquired. If we see an attempt to acquire a lock 1478out of order, we can identify the locks and offending code. 1479 1480To make this work, we need to keep track of the locks held by each thread, 1481and create history trees for each lock. When a thread tries to acquire 1482a new lock, we walk through the "history children" of the lock, looking 1483for a match with locks the thread already holds. If we find a match, 1484it means the thread has made a request that could result in a deadlock. 1485 1486To support recursive locks, we always allow re-locking a currently-held 1487lock, and maintain a recursion depth count. 1488 1489An ASCII-art example, where letters represent Objects: 1490 1491 A 1492 /|\ 1493 / | \ 1494 B | D 1495 \ | 1496 \| 1497 C 1498 1499The above is the tree we'd have after handling Object synchronization 1500sequences "ABC", "AC", "AD". A has three children, {B, C, D}. C is also 1501a child of B. (The lines represent pointers between parent and child. 1502Every node can have multiple parents and multiple children.) 1503 1504If we hold AC, and want to lock B, we recursively search through B's 1505children to see if A or C appears. It does, so we reject the attempt. 1506(A straightforward way to implement it: add a link from C to B, then 1507determine whether the graph starting at B contains a cycle.) 1508 1509If we hold AC and want to lock D, we would succeed, creating a new link 1510from C to D. 1511 1512The lock history and a stack trace is attached to the Object's Monitor 1513struct, which means we need to fatten every Object we lock (thin locking 1514is effectively disabled). If we don't need the stack trace we can 1515avoid fattening the leaf nodes, only fattening objects that need to hold 1516history trees. 1517 1518Updates to Monitor structs are only allowed for the thread that holds 1519the Monitor, so we actually do most of our deadlock prediction work after 1520the lock has been acquired. 1521 1522When an object with a monitor is GCed, we need to remove it from the 1523history trees. There are two basic approaches: 1524 (1) For through the entire set of known monitors, search all child 1525 lists for the object in question. This is rather slow, resulting 1526 in GC passes that take upwards of 10 seconds to complete. 1527 (2) Maintain "parent" pointers in each node. Remove the entries as 1528 required. This requires additional storage and maintenance for 1529 every operation, but is significantly faster at GC time. 1530For each GCed object, we merge all of the object's children into each of 1531the object's parents. 1532*/ 1533 1534#if !defined(WITH_MONITOR_TRACKING) 1535# error "WITH_DEADLOCK_PREDICTION requires WITH_MONITOR_TRACKING" 1536#endif 1537 1538/* 1539 * Clear out the contents of an ExpandingObjectList, freeing any 1540 * dynamic allocations. 1541 */ 1542static void expandObjClear(ExpandingObjectList* pList) 1543{ 1544 if (pList->list != NULL) { 1545 free(pList->list); 1546 pList->list = NULL; 1547 } 1548 pList->alloc = pList->count = 0; 1549} 1550 1551/* 1552 * Get the number of objects currently stored in the list. 1553 */ 1554static inline int expandBufGetCount(const ExpandingObjectList* pList) 1555{ 1556 return pList->count; 1557} 1558 1559/* 1560 * Get the Nth entry from the list. 1561 */ 1562static inline Object* expandBufGetEntry(const ExpandingObjectList* pList, 1563 int i) 1564{ 1565 return pList->list[i]; 1566} 1567 1568/* 1569 * Add a new entry to the list. 1570 * 1571 * We don't check for or try to enforce uniqueness. It's expected that 1572 * the higher-level code does this for us. 1573 */ 1574static void expandObjAddEntry(ExpandingObjectList* pList, Object* obj) 1575{ 1576 if (pList->count == pList->alloc) { 1577 /* time to expand */ 1578 Object** newList; 1579 1580 if (pList->alloc == 0) 1581 pList->alloc = 4; 1582 else 1583 pList->alloc *= 2; 1584 LOGVV("expanding %p to %d\n", pList, pList->alloc); 1585 newList = realloc(pList->list, pList->alloc * sizeof(Object*)); 1586 if (newList == NULL) { 1587 LOGE("Failed expanding DP object list (alloc=%d)\n", pList->alloc); 1588 dvmAbort(); 1589 } 1590 pList->list = newList; 1591 } 1592 1593 pList->list[pList->count++] = obj; 1594} 1595 1596/* 1597 * Returns "true" if the element was successfully removed. 1598 */ 1599static bool expandObjRemoveEntry(ExpandingObjectList* pList, Object* obj) 1600{ 1601 int i; 1602 1603 for (i = pList->count-1; i >= 0; i--) { 1604 if (pList->list[i] == obj) 1605 break; 1606 } 1607 if (i < 0) 1608 return false; 1609 1610 if (i != pList->count-1) { 1611 /* 1612 * The order of elements is not important, so we just copy the 1613 * last entry into the new slot. 1614 */ 1615 //memmove(&pList->list[i], &pList->list[i+1], 1616 // (pList->count-1 - i) * sizeof(pList->list[0])); 1617 pList->list[i] = pList->list[pList->count-1]; 1618 } 1619 1620 pList->count--; 1621 pList->list[pList->count] = (Object*) 0xdecadead; 1622 return true; 1623} 1624 1625/* 1626 * Returns "true" if "obj" appears in the list. 1627 */ 1628static bool expandObjHas(const ExpandingObjectList* pList, Object* obj) 1629{ 1630 int i; 1631 1632 for (i = 0; i < pList->count; i++) { 1633 if (pList->list[i] == obj) 1634 return true; 1635 } 1636 return false; 1637} 1638 1639/* 1640 * Print the list contents to stdout. For debugging. 1641 */ 1642static void expandObjDump(const ExpandingObjectList* pList) 1643{ 1644 int i; 1645 for (i = 0; i < pList->count; i++) 1646 printf(" %p", pList->list[i]); 1647} 1648 1649/* 1650 * Check for duplicate entries. Returns the index of the first instance 1651 * of the duplicated value, or -1 if no duplicates were found. 1652 */ 1653static int expandObjCheckForDuplicates(const ExpandingObjectList* pList) 1654{ 1655 int i, j; 1656 for (i = 0; i < pList->count-1; i++) { 1657 for (j = i + 1; j < pList->count; j++) { 1658 if (pList->list[i] == pList->list[j]) { 1659 return i; 1660 } 1661 } 1662 } 1663 1664 return -1; 1665} 1666 1667 1668/* 1669 * Determine whether "child" appears in the list of objects associated 1670 * with the Monitor in "parent". If "parent" is a thin lock, we return 1671 * false immediately. 1672 */ 1673static bool objectInChildList(const Object* parent, Object* child) 1674{ 1675 u4 lock = parent->lock; 1676 if (!IS_LOCK_FAT(&lock)) { 1677 //LOGI("on thin\n"); 1678 return false; 1679 } 1680 1681 return expandObjHas(&LW_MONITOR(lock)->historyChildren, child); 1682} 1683 1684/* 1685 * Print the child list. 1686 */ 1687static void dumpKids(Object* parent) 1688{ 1689 Monitor* mon = LW_MONITOR(parent->lock); 1690 1691 printf("Children of %p:", parent); 1692 expandObjDump(&mon->historyChildren); 1693 printf("\n"); 1694} 1695 1696/* 1697 * Add "child" to the list of children in "parent", and add "parent" to 1698 * the list of parents in "child". 1699 */ 1700static void linkParentToChild(Object* parent, Object* child) 1701{ 1702 //assert(LW_MONITOR(parent->lock)->owner == dvmThreadSelf()); // !owned for merge 1703 assert(IS_LOCK_FAT(&parent->lock)); 1704 assert(IS_LOCK_FAT(&child->lock)); 1705 assert(parent != child); 1706 Monitor* mon; 1707 1708 mon = LW_MONITOR(parent->lock); 1709 assert(!expandObjHas(&mon->historyChildren, child)); 1710 expandObjAddEntry(&mon->historyChildren, child); 1711 1712 mon = LW_MONITOR(child->lock); 1713 assert(!expandObjHas(&mon->historyParents, parent)); 1714 expandObjAddEntry(&mon->historyParents, parent); 1715} 1716 1717 1718/* 1719 * Remove "child" from the list of children in "parent". 1720 */ 1721static void unlinkParentFromChild(Object* parent, Object* child) 1722{ 1723 //assert(LW_MONITOR(parent->lock)->owner == dvmThreadSelf()); // !owned for GC 1724 assert(IS_LOCK_FAT(&parent->lock)); 1725 assert(IS_LOCK_FAT(&child->lock)); 1726 assert(parent != child); 1727 Monitor* mon; 1728 1729 mon = LW_MONITOR(parent->lock); 1730 if (!expandObjRemoveEntry(&mon->historyChildren, child)) { 1731 LOGW("WARNING: child %p not found in parent %p\n", child, parent); 1732 } 1733 assert(!expandObjHas(&mon->historyChildren, child)); 1734 assert(expandObjCheckForDuplicates(&mon->historyChildren) < 0); 1735 1736 mon = LW_MONITOR(child->lock); 1737 if (!expandObjRemoveEntry(&mon->historyParents, parent)) { 1738 LOGW("WARNING: parent %p not found in child %p\n", parent, child); 1739 } 1740 assert(!expandObjHas(&mon->historyParents, parent)); 1741 assert(expandObjCheckForDuplicates(&mon->historyParents) < 0); 1742} 1743 1744 1745/* 1746 * Log the monitors held by the current thread. This is done as part of 1747 * flagging an error. 1748 */ 1749static void logHeldMonitors(Thread* self) 1750{ 1751 char* name = NULL; 1752 1753 name = dvmGetThreadName(self); 1754 LOGW("Monitors currently held by thread (threadid=%d '%s')\n", 1755 self->threadId, name); 1756 LOGW("(most-recently-acquired on top):\n"); 1757 free(name); 1758 1759 LockedObjectData* lod = self->pLockedObjects; 1760 while (lod != NULL) { 1761 LOGW("--- object %p[%d] (%s)\n", 1762 lod->obj, lod->recursionCount, lod->obj->clazz->descriptor); 1763 dvmLogRawStackTrace(lod->rawStackTrace, lod->stackDepth); 1764 1765 lod = lod->next; 1766 } 1767} 1768 1769/* 1770 * Recursively traverse the object hierarchy starting at "obj". We mark 1771 * ourselves on entry and clear the mark on exit. If we ever encounter 1772 * a marked object, we have a cycle. 1773 * 1774 * Returns "true" if all is well, "false" if we found a cycle. 1775 */ 1776static bool traverseTree(Thread* self, const Object* obj) 1777{ 1778 assert(IS_LOCK_FAT(&obj->lock)); 1779 Monitor* mon = LW_MONITOR(obj->lock); 1780 1781 /* 1782 * Have we been here before? 1783 */ 1784 if (mon->historyMark) { 1785 int* rawStackTrace; 1786 int stackDepth; 1787 1788 LOGW("%s\n", kStartBanner); 1789 LOGW("Illegal lock attempt:\n"); 1790 LOGW("--- object %p (%s)\n", obj, obj->clazz->descriptor); 1791 1792 rawStackTrace = dvmFillInStackTraceRaw(self, &stackDepth); 1793 dvmLogRawStackTrace(rawStackTrace, stackDepth); 1794 free(rawStackTrace); 1795 1796 LOGW(" "); 1797 logHeldMonitors(self); 1798 1799 LOGW(" "); 1800 LOGW("Earlier, the following lock order (from last to first) was\n"); 1801 LOGW("established -- stack trace is from first successful lock):\n"); 1802 return false; 1803 } 1804 mon->historyMark = true; 1805 1806 /* 1807 * Examine the children. We do NOT hold these locks, so they might 1808 * very well transition from thin to fat or change ownership while 1809 * we work. 1810 * 1811 * NOTE: we rely on the fact that they cannot revert from fat to thin 1812 * while we work. This is currently a safe assumption. 1813 * 1814 * We can safely ignore thin-locked children, because by definition 1815 * they have no history and are leaf nodes. In the current 1816 * implementation we always fatten the locks to provide a place to 1817 * hang the stack trace. 1818 */ 1819 ExpandingObjectList* pList = &mon->historyChildren; 1820 int i; 1821 for (i = expandBufGetCount(pList)-1; i >= 0; i--) { 1822 const Object* child = expandBufGetEntry(pList, i); 1823 u4 lock = child->lock; 1824 if (!IS_LOCK_FAT(&lock)) 1825 continue; 1826 if (!traverseTree(self, child)) { 1827 LOGW("--- object %p (%s)\n", obj, obj->clazz->descriptor); 1828 dvmLogRawStackTrace(mon->historyRawStackTrace, 1829 mon->historyStackDepth); 1830 mon->historyMark = false; 1831 return false; 1832 } 1833 } 1834 1835 mon->historyMark = false; 1836 1837 return true; 1838} 1839 1840/* 1841 * Update the deadlock prediction tree, based on the current thread 1842 * acquiring "acqObj". This must be called before the object is added to 1843 * the thread's list of held monitors. 1844 * 1845 * If the thread already holds the lock (recursion), or this is a known 1846 * lock configuration, we return without doing anything. Otherwise, we add 1847 * a link from the most-recently-acquired lock in this thread to "acqObj" 1848 * after ensuring that the parent lock is "fat". 1849 * 1850 * This MUST NOT be called while a GC is in progress in another thread, 1851 * because we assume exclusive access to history trees in owned monitors. 1852 */ 1853static void updateDeadlockPrediction(Thread* self, Object* acqObj) 1854{ 1855 LockedObjectData* lod; 1856 LockedObjectData* mrl; 1857 1858 /* 1859 * Quick check for recursive access. 1860 */ 1861 lod = dvmFindInMonitorList(self, acqObj); 1862 if (lod != NULL) { 1863 LOGV("+++ DP: recursive %p\n", acqObj); 1864 return; 1865 } 1866 1867 /* 1868 * Make the newly-acquired object's monitor "fat". In some ways this 1869 * isn't strictly necessary, but we need the GC to tell us when 1870 * "interesting" objects go away, and right now the only way to make 1871 * an object look interesting is to give it a monitor. 1872 * 1873 * This also gives us a place to hang a stack trace. 1874 * 1875 * Our thread holds the lock, so we're allowed to rewrite the lock 1876 * without worrying that something will change out from under us. 1877 */ 1878 if (!IS_LOCK_FAT(&acqObj->lock)) { 1879 LOGVV("fattening lockee %p (recur=%d)\n", 1880 acqObj, LW_LOCK_COUNT(acqObj->lock.thin)); 1881 inflateMonitor(self, acqObj); 1882 } 1883 1884 /* if we don't have a stack trace for this monitor, establish one */ 1885 if (LW_MONITOR(acqObj->lock)->historyRawStackTrace == NULL) { 1886 Monitor* mon = LW_MONITOR(acqObj->lock); 1887 mon->historyRawStackTrace = dvmFillInStackTraceRaw(self, 1888 &mon->historyStackDepth); 1889 } 1890 1891 /* 1892 * We need to examine and perhaps modify the most-recently-locked 1893 * monitor. We own that, so there's no risk of another thread 1894 * stepping on us. 1895 * 1896 * Retrieve the most-recently-locked entry from our thread. 1897 */ 1898 mrl = self->pLockedObjects; 1899 if (mrl == NULL) 1900 return; /* no other locks held */ 1901 1902 /* 1903 * Do a quick check to see if "acqObj" is a direct descendant. We can do 1904 * this without holding the global lock because of our assertion that 1905 * a GC is not running in parallel -- nobody except the GC can 1906 * modify a history list in a Monitor they don't own, and we own "mrl". 1907 * (There might be concurrent *reads*, but no concurrent *writes.) 1908 * 1909 * If we find it, this is a known good configuration, and we're done. 1910 */ 1911 if (objectInChildList(mrl->obj, acqObj)) 1912 return; 1913 1914 /* 1915 * "mrl" is going to need to have a history tree. If it's currently 1916 * a thin lock, we make it fat now. The thin lock might have a 1917 * nonzero recursive lock count, which we need to carry over. 1918 * 1919 * Our thread holds the lock, so we're allowed to rewrite the lock 1920 * without worrying that something will change out from under us. 1921 */ 1922 if (!IS_LOCK_FAT(&mrl->obj->lock)) { 1923 LOGVV("fattening parent %p f/b/o child %p (recur=%d)\n", 1924 mrl->obj, acqObj, LW_LOCK_COUNT(mrl->obj->lock)); 1925 inflateMonitor(self, mrl->obj); 1926 } 1927 1928 /* 1929 * We haven't seen this configuration before. We need to scan down 1930 * acqObj's tree to see if any of the monitors in self->pLockedObjects 1931 * appear. We grab a global lock before traversing or updating the 1932 * history list. 1933 * 1934 * If we find a match for any of our held locks, we know that the lock 1935 * has previously been acquired *after* acqObj, and we throw an error. 1936 * 1937 * The easiest way to do this is to create a link from "mrl" to "acqObj" 1938 * and do a recursive traversal, marking nodes as we cross them. If 1939 * we cross one a second time, we have a cycle and can throw an error. 1940 * (We do the flag-clearing traversal before adding the new link, so 1941 * that we're guaranteed to terminate.) 1942 * 1943 * If "acqObj" is a thin lock, it has no history, and we can create a 1944 * link to it without additional checks. [ We now guarantee that it's 1945 * always fat. ] 1946 */ 1947 bool failed = false; 1948 dvmLockMutex(&gDvm.deadlockHistoryLock); 1949 linkParentToChild(mrl->obj, acqObj); 1950 if (!traverseTree(self, acqObj)) { 1951 LOGW("%s\n", kEndBanner); 1952 failed = true; 1953 1954 /* remove the entry so we're still okay when in "warning" mode */ 1955 unlinkParentFromChild(mrl->obj, acqObj); 1956 } 1957 dvmUnlockMutex(&gDvm.deadlockHistoryLock); 1958 1959 if (failed) { 1960 switch (gDvm.deadlockPredictMode) { 1961 case kDPErr: 1962 dvmThrowException("Ldalvik/system/PotentialDeadlockError;", NULL); 1963 break; 1964 case kDPAbort: 1965 LOGE("Aborting due to potential deadlock\n"); 1966 dvmAbort(); 1967 break; 1968 default: 1969 /* warn only */ 1970 break; 1971 } 1972 } 1973} 1974 1975/* 1976 * We're removing "child" from existence. We want to pull all of 1977 * child's children into "parent", filtering out duplicates. This is 1978 * called during the GC. 1979 * 1980 * This does not modify "child", which might have multiple parents. 1981 */ 1982static void mergeChildren(Object* parent, const Object* child) 1983{ 1984 Monitor* mon; 1985 int i; 1986 1987 assert(IS_LOCK_FAT(&child->lock)); 1988 mon = LW_MONITOR(child->lock); 1989 ExpandingObjectList* pList = &mon->historyChildren; 1990 1991 for (i = expandBufGetCount(pList)-1; i >= 0; i--) { 1992 Object* grandChild = expandBufGetEntry(pList, i); 1993 1994 if (!objectInChildList(parent, grandChild)) { 1995 LOGVV("+++ migrating %p link to %p\n", grandChild, parent); 1996 linkParentToChild(parent, grandChild); 1997 } else { 1998 LOGVV("+++ parent %p already links to %p\n", parent, grandChild); 1999 } 2000 } 2001} 2002 2003/* 2004 * An object with a fat lock is being collected during a GC pass. We 2005 * want to remove it from any lock history trees that it is a part of. 2006 * 2007 * This may require updating the history trees in several monitors. The 2008 * monitor semantics guarantee that no other thread will be accessing 2009 * the history trees at the same time. 2010 */ 2011static void removeCollectedObject(Object* obj) 2012{ 2013 Monitor* mon; 2014 2015 LOGVV("+++ collecting %p\n", obj); 2016 2017#if 0 2018 /* 2019 * We're currently running through the entire set of known monitors. 2020 * This can be somewhat slow. We may want to keep lists of parents 2021 * in each child to speed up GC. 2022 */ 2023 mon = gDvm.monitorList; 2024 while (mon != NULL) { 2025 Object* parent = mon->obj; 2026 if (parent != NULL) { /* value nulled for deleted entries */ 2027 if (objectInChildList(parent, obj)) { 2028 LOGVV("removing child %p from parent %p\n", obj, parent); 2029 unlinkParentFromChild(parent, obj); 2030 mergeChildren(parent, obj); 2031 } 2032 } 2033 mon = mon->next; 2034 } 2035#endif 2036 2037 /* 2038 * For every parent of this object: 2039 * - merge all of our children into the parent's child list (creates 2040 * a two-way link between parent and child) 2041 * - remove ourselves from the parent's child list 2042 */ 2043 ExpandingObjectList* pList; 2044 int i; 2045 2046 assert(IS_LOCK_FAT(&obj->lock)); 2047 mon = LW_MONITOR(obj->lock); 2048 pList = &mon->historyParents; 2049 for (i = expandBufGetCount(pList)-1; i >= 0; i--) { 2050 Object* parent = expandBufGetEntry(pList, i); 2051 Monitor* parentMon = LW_MONITOR(parent->lock); 2052 2053 if (!expandObjRemoveEntry(&parentMon->historyChildren, obj)) { 2054 LOGW("WARNING: child %p not found in parent %p\n", obj, parent); 2055 } 2056 assert(!expandObjHas(&parentMon->historyChildren, obj)); 2057 2058 mergeChildren(parent, obj); 2059 } 2060 2061 /* 2062 * For every child of this object: 2063 * - remove ourselves from the child's parent list 2064 */ 2065 pList = &mon->historyChildren; 2066 for (i = expandBufGetCount(pList)-1; i >= 0; i--) { 2067 Object* child = expandBufGetEntry(pList, i); 2068 Monitor* childMon = LW_MONITOR(child->lock); 2069 2070 if (!expandObjRemoveEntry(&childMon->historyParents, obj)) { 2071 LOGW("WARNING: parent %p not found in child %p\n", obj, child); 2072 } 2073 assert(!expandObjHas(&childMon->historyParents, obj)); 2074 } 2075} 2076 2077#endif /*WITH_DEADLOCK_PREDICTION*/ 2078