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