vm/Sync.c

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