2 * Copyright (C) 2008 The Android Open Source Project
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 * Fundamental synchronization mechanisms.
19 * The top part of the file has operations on "monitor" structs; the
20 * next part has the native calls on objects.
22 * The current implementation uses "thin locking" to avoid allocating
23 * an Object's full Monitor struct until absolutely necessary (i.e.,
24 * during contention or a call to wait()).
26 * TODO: make improvements to thin locking
27 * We may be able to improve performance and reduce memory requirements by:
28 * - reverting to a thin lock once the Monitor is no longer necessary
29 * - using a pool of monitor objects, with some sort of recycling scheme
31 * TODO: recycle native-level monitors when objects are garbage collected.
33 * NOTE: if we broadcast a notify, and somebody sneaks in a Thread.interrupt
34 * before the notify finishes (i.e. before all threads sleeping on the
35 * condition variable have awoken), we could end up with a nonzero value for
36 * "notifying" after everybody is gone because one of the notified threads
37 * will actually exit via the "interrupted" path. This can be detected as
38 * (notifying + interrupting > waiting), i.e. the number of threads that need
39 * to be woken is greater than the number waiting. The fix is to test and
40 * adjust "notifying" at the start of the wait() call.
41 * -> This is probably not a problem if we notify less than the full set
42 * before the interrupt comes in. If we have four waiters, two pending
43 * notifies, and an interrupt hits, we will interrupt one thread and notify
44 * two others. Doesn't matter if the interrupted thread would have been
45 * one of the notified. Count is only screwed up if we have two waiters,
46 * in which case it's safe to fix it at the start of the next wait().
59 #ifdef WITH_DEADLOCK_PREDICTION /* fwd */
60 static const char* kStartBanner =
61 "<-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#";
62 static const char* kEndBanner =
63 "#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#->";
66 * Unsorted, expanding list of objects.
68 * This is very similar to PointerSet (which came into existence after this),
69 * but these are unsorted, uniqueness is not enforced by the "add" function,
70 * and the base object isn't allocated on the heap.
72 typedef struct ExpandingObjectList {
76 } ExpandingObjectList;
79 static void updateDeadlockPrediction(Thread* self, Object* obj);
80 static void removeCollectedObject(Object* obj);
81 static void expandObjClear(ExpandingObjectList* pList);
85 * Every Object has a monitor associated with it, but not every Object is
86 * actually locked. Even the ones that are locked do not need a
87 * full-fledged monitor until a) there is actual contention or b) wait()
88 * is called on the Object.
90 * For Dalvik, we have implemented a scheme similar to the one described
91 * in Bacon et al.'s "Thin locks: featherweight synchronization for Java"
92 * (ACM 1998). Things are even easier for us, though, because we have
93 * a full 32 bits to work with.
95 * The two states that an Object's lock may have are referred to as
96 * "thin" and "fat". The lock may transition between the two states
97 * for various reasons.
99 * The lock value itself is stored in Object.lock, which is a union of
102 * typedef union Lock {
107 * It is possible to tell the current state of the lock from the actual
108 * value, so we do not need to store any additional state. When the
109 * lock is "thin", it has the form:
111 * [31 ---- 16] [15 ---- 1] [0]
112 * lock count thread id 1
114 * When it is "fat", the field is simply a (Monitor *). Since the pointer
115 * will always be 4-byte-aligned, bits 1 and 0 will always be zero when
116 * the field holds a pointer. Hence, we can tell the current fat-vs-thin
117 * state by checking the least-significant bit.
119 * For an in-depth description of the mechanics of thin-vs-fat locking,
120 * read the paper referred to above.
122 * To reduce the amount of work when attempting a compare and exchange,
123 * Thread.threadId is guaranteed to have bit 0 set, and all new Objects
124 * have their lock fields initialized to the value 0x1, or
125 * DVM_LOCK_INITIAL_THIN_VALUE, via DVM_OBJECT_INIT().
130 * - mutually exclusive access to resources
131 * - a way for multiple threads to wait for notification
133 * In effect, they fill the role of both mutexes and condition variables.
135 * Only one thread can own the monitor at any time. There may be several
136 * threads waiting on it (the wait call unlocks it). One or more waiting
137 * threads may be getting interrupted or notified at any given time.
140 Thread* owner; /* which thread currently owns the lock? */
141 int lockCount; /* owner's recursive lock depth */
142 Object* obj; /* what object are we part of [debug only] */
144 int waiting; /* total #of threads waiting on this */
145 int notifying; /* #of threads being notified */
146 int interrupting; /* #of threads being interrupted */
148 pthread_mutex_t lock;
153 #ifdef WITH_DEADLOCK_PREDICTION
155 * Objects that have been locked immediately after this one in the
156 * past. We use an expanding flat array, allocated on first use, to
157 * minimize allocations. Deletions from the list, expected to be
158 * infrequent, are crunched down.
160 ExpandingObjectList historyChildren;
163 * We also track parents. This isn't strictly necessary, but it makes
164 * the cleanup at GC time significantly faster.
166 ExpandingObjectList historyParents;
168 /* used during cycle detection */
171 /* stack trace, established the first time we locked the object */
172 int historyStackDepth;
173 int* historyRawStackTrace;
179 * Create and initialize a monitor.
181 Monitor* dvmCreateMonitor(Object* obj)
185 mon = (Monitor*) calloc(1, sizeof(Monitor));
187 LOGE("Unable to allocate monitor\n");
191 dvmInitMutex(&mon->lock);
192 pthread_cond_init(&mon->cond, NULL);
194 /* replace the head of the list with the new monitor */
196 mon->next = gDvm.monitorList;
197 } while (!ATOMIC_CMP_SWAP((int32_t*)(void*)&gDvm.monitorList,
198 (int32_t)mon->next, (int32_t)mon));
206 static void releaseMonitor(Monitor* mon)
212 * Free the monitor list. Only used when shutting the VM down.
214 void dvmFreeMonitorList(void)
219 mon = gDvm.monitorList;
220 while (mon != NULL) {
223 #ifdef WITH_DEADLOCK_PREDICTION
224 expandObjClear(&mon->historyChildren);
225 expandObjClear(&mon->historyParents);
226 free(mon->historyRawStackTrace);
234 * Log some info about our monitors.
236 void dvmDumpMonitorInfo(const char* msg)
238 #if QUIET_ZYGOTE_MONITOR
247 totalCount = liveCount = 0;
248 Monitor* mon = gDvm.monitorList;
249 while (mon != NULL) {
251 if (mon->obj != NULL)
256 LOGD("%s: monitor list has %d entries (%d live)\n",
257 msg, totalCount, liveCount);
261 * Get the object that a monitor is part of.
263 Object* dvmGetMonitorObject(Monitor* mon)
272 * Checks whether the given thread holds the given
275 bool dvmHoldsLock(Thread* thread, Object* obj)
277 if (thread == NULL || obj == NULL) {
281 /* Since we're reading the lock value multiple times,
282 * latch it so that it doesn't change out from under
283 * us if we get preempted.
285 Lock lock = obj->lock;
286 if (IS_LOCK_FAT(&lock)) {
287 return thread == lock.mon->owner;
289 return thread->threadId == (lock.thin & 0xffff);
294 * Free the monitor associated with an object and make the object's lock
295 * thin again. This is called during garbage collection.
297 void dvmFreeObjectMonitor_internal(Lock *lock)
301 /* The macro that wraps this function checks IS_LOCK_FAT() first.
303 assert(IS_LOCK_FAT(lock));
305 #ifdef WITH_DEADLOCK_PREDICTION
306 if (gDvm.deadlockPredictMode != kDPOff)
307 removeCollectedObject(lock->mon->obj);
311 lock->thin = DVM_LOCK_INITIAL_THIN_VALUE;
313 /* This lock is associated with an object
314 * that's being swept. The only possible way
315 * anyone could be holding this lock would be
316 * if some JNI code locked but didn't unlock
317 * the object, in which case we've got some bad
318 * native code somewhere.
320 assert(pthread_mutex_trylock(&mon->lock) == 0);
321 pthread_mutex_destroy(&mon->lock);
322 pthread_cond_destroy(&mon->cond);
324 //TODO: unlink from the monitor list (would require a lock)
325 // (might not -- the GC suspension may be enough)
329 #ifdef WITH_DEADLOCK_PREDICTION
330 expandObjClear(&mon->historyChildren);
331 expandObjClear(&mon->historyParents);
332 free(mon->historyRawStackTrace);
334 memset(mon, 0, sizeof (*mon));
345 static void lockMonitor(Thread* self, Monitor* mon)
349 if (mon->owner == self) {
352 ThreadStatus oldStatus;
354 if (pthread_mutex_trylock(&mon->lock) != 0) {
355 /* mutex is locked, switch to wait status and sleep on it */
356 oldStatus = dvmChangeStatus(self, THREAD_MONITOR);
357 cc = pthread_mutex_lock(&mon->lock);
359 dvmChangeStatus(self, oldStatus);
363 assert(mon->lockCount == 0);
366 * "waiting", "notifying", and "interrupting" could all be nonzero
367 * if we're locking an object on which other threads are waiting.
368 * Nothing worth assert()ing about here.
374 * Try to lock a monitor.
376 * Returns "true" on success.
378 static bool tryLockMonitor(Thread* self, Monitor* mon)
382 if (mon->owner == self) {
386 cc = pthread_mutex_trylock(&mon->lock);
389 assert(mon->lockCount == 0);
401 * Returns true if the unlock succeeded.
402 * If the unlock failed, an exception will be pending.
404 static bool unlockMonitor(Thread* self, Monitor* mon)
406 assert(mon != NULL); // can this happen?
408 if (mon->owner == self) {
410 * We own the monitor, so nobody else can be in here.
412 if (mon->lockCount == 0) {
415 cc = pthread_mutex_unlock(&mon->lock);
422 * We don't own this, so we're not allowed to unlock it.
423 * The JNI spec says that we should throw IllegalMonitorStateException
426 if (mon->owner == NULL) {
427 //LOGW("Unlock fat %p: not owned\n", mon->obj);
429 //LOGW("Unlock fat %p: id %d vs %d\n",
430 // mon->obj, mon->owner->threadId, self->threadId);
432 dvmThrowException("Ljava/lang/IllegalMonitorStateException;",
433 "unlock of unowned monitor");
440 * Wait on a monitor until timeout, interrupt, or notification. Used for
441 * Object.wait() and (somewhat indirectly) Thread.sleep() and Thread.join().
443 * If another thread calls Thread.interrupt(), we throw InterruptedException
444 * and return immediately if one of the following are true:
445 * - blocked in wait(), wait(long), or wait(long, int) methods of Object
446 * - blocked in join(), join(long), or join(long, int) methods of Thread
447 * - blocked in sleep(long), or sleep(long, int) methods of Thread
448 * Otherwise, we set the "interrupted" flag.
450 * Checks to make sure that "nsec" is in the range 0-999999
451 * (i.e. fractions of a millisecond) and throws the appropriate
452 * exception if it isn't.
454 * The spec allows "spurious wakeups", and recommends that all code using
455 * Object.wait() do so in a loop. This appears to derive from concerns
456 * about pthread_cond_wait() on multiprocessor systems. Some commentary
457 * on the web casts doubt on whether these can/should occur.
459 * Since we're allowed to wake up "early", we clamp extremely long durations
460 * to return at the end of the 32-bit time epoch.
462 static void waitMonitor(Thread* self, Monitor* mon, s8 msec, s4 nsec,
463 bool interruptShouldThrow)
466 bool wasInterrupted = false;
470 /* Make sure that the lock is fat and that we hold it. */
471 if (mon == NULL || ((u4)mon & 1) != 0 || mon->owner != self) {
472 dvmThrowException("Ljava/lang/IllegalMonitorStateException;",
473 "object not locked by thread before wait()");
478 * Enforce the timeout range.
480 if (msec < 0 || nsec < 0 || nsec > 999999) {
481 dvmThrowException("Ljava/lang/IllegalArgumentException;",
482 "timeout arguments out of range");
487 * Compute absolute wakeup time, if necessary.
489 if (msec == 0 && nsec == 0) {
494 #ifdef HAVE_TIMEDWAIT_MONOTONIC
496 clock_gettime(CLOCK_MONOTONIC, &now);
497 endSec = now.tv_sec + msec / 1000;
498 if (endSec >= 0x7fffffff) {
499 LOGV("NOTE: end time exceeds epoch\n");
503 ts.tv_nsec = (now.tv_nsec + (msec % 1000) * 1000 * 1000) + nsec;
506 gettimeofday(&now, NULL);
507 endSec = now.tv_sec + msec / 1000;
508 if (endSec >= 0x7fffffff) {
509 LOGV("NOTE: end time exceeds epoch\n");
513 ts.tv_nsec = (now.tv_usec + (msec % 1000) * 1000) * 1000 + nsec;
517 if (ts.tv_nsec >= 1000000000L) {
519 ts.tv_nsec -= 1000000000L;
525 * Make sure "notifying" wasn't screwed up by earlier activity. If this
526 * is wrong we could end up waking up too many people. (This is a rare
527 * situation, but we need to handle it correctly.)
529 if (mon->notifying + mon->interrupting > mon->waiting) {
530 LOGD("threadid=%d: bogus mon %d+%d>%d; adjusting\n",
531 self->threadId, mon->notifying, mon->interrupting,
534 assert(mon->waiting >= mon->interrupting);
535 mon->notifying = mon->waiting - mon->interrupting;
539 * Add ourselves to the set of threads waiting on this monitor, and
540 * release our hold. We need to let it go even if we're a few levels
541 * deep in a recursive lock, and we need to restore that later.
543 * The order of operations here isn't significant, because we still
544 * hold the pthread mutex.
548 prevLockCount = mon->lockCount;
554 * Update thread status. If the GC wakes up, it'll ignore us, knowing
555 * that we won't touch any references in this state, and we'll check
556 * our suspend mode before we transition out.
559 dvmChangeStatus(self, THREAD_TIMED_WAIT);
561 dvmChangeStatus(self, THREAD_WAIT);
564 * Tell the thread which monitor we're waiting on. This is necessary
565 * so that Thread.interrupt() can wake us up. Thread.interrupt needs
566 * to gain ownership of the monitor mutex before it can signal us, so
567 * we're still not worried about race conditions.
569 self->waitMonitor = mon;
572 * Handle the case where the thread was interrupted before we called
575 if (self->interrupted) {
576 wasInterrupted = true;
580 LOGVV("threadid=%d: waiting on %p\n", self->threadId, mon);
584 cc = pthread_cond_wait(&mon->cond, &mon->lock);
587 #ifdef HAVE_TIMEDWAIT_MONOTONIC
588 cc = pthread_cond_timedwait_monotonic(&mon->cond, &mon->lock, &ts);
590 cc = pthread_cond_timedwait(&mon->cond, &mon->lock, &ts);
592 if (cc == ETIMEDOUT) {
593 LOGVV("threadid=%d wakeup: timeout\n", self->threadId);
599 * We woke up because of an interrupt (which does a broadcast) or
600 * a notification (which might be a signal or a broadcast). Figure
601 * out what we need to do.
603 if (self->interruptingWait) {
605 * The other thread successfully gained the monitor lock, and
606 * has confirmed that we were waiting on it. If this is an
607 * interruptible wait, we bail out immediately. If not, we
610 self->interruptingWait = false;
612 assert(self->interrupted);
613 if (interruptShouldThrow) {
614 wasInterrupted = true;
615 LOGD("threadid=%d wakeup: interrupted\n", self->threadId);
618 LOGD("threadid=%d wakeup: not interruptible\n", self->threadId);
621 if (mon->notifying) {
623 * One or more threads are being notified. Remove ourselves
627 LOGVV("threadid=%d wakeup: notified\n", self->threadId);
631 * Looks like we were woken unnecessarily, probably as a
632 * result of another thread being interrupted. Go back to
635 LOGVV("threadid=%d wakeup: going back to sleep\n", self->threadId);
640 //if (wasInterrupted) {
641 // LOGW("threadid=%d: throwing InterruptedException:\n", self->threadId);
642 // dvmDumpThread(self, false);
646 * Put everything back. Again, we hold the pthread mutex, so the order
647 * here isn't significant.
649 self->waitMonitor = NULL;
652 mon->lockCount = prevLockCount;
654 /* set self->status back to THREAD_RUNNING, and self-suspend if needed */
655 dvmChangeStatus(self, THREAD_RUNNING);
657 if (wasInterrupted) {
659 * We were interrupted while waiting, or somebody interrupted an
660 * un-interruptable thread earlier and we're bailing out immediately.
662 * The doc sayeth: "The interrupted status of the current thread is
663 * cleared when this exception is thrown."
665 self->interrupted = false;
666 if (interruptShouldThrow)
667 dvmThrowException("Ljava/lang/InterruptedException;", NULL);
672 * Notify one thread waiting on this monitor.
674 static void notifyMonitor(Thread* self, Monitor* mon)
676 /* Make sure that the lock is fat and that we hold it. */
677 if (mon == NULL || ((u4)mon & 1) != 0 || mon->owner != self) {
678 dvmThrowException("Ljava/lang/IllegalMonitorStateException;",
679 "object not locked by thread before notify()");
684 * Check to see if anybody is there to notify. We subtract off
685 * threads that are being interrupted and anything that has
686 * potentially already been notified.
688 if (mon->notifying + mon->interrupting < mon->waiting) {
689 /* wake up one thread */
692 LOGVV("threadid=%d: signaling on %p\n", self->threadId, mon);
695 cc = pthread_cond_signal(&mon->cond);
698 LOGVV("threadid=%d: nobody to signal on %p\n", self->threadId, mon);
703 * Notify all threads waiting on this monitor.
705 * We keep a count of how many threads we notified, so that our various
706 * counts remain accurate.
708 static void notifyAllMonitor(Thread* self, Monitor* mon)
710 /* Make sure that the lock is fat and that we hold it. */
711 if (mon == NULL || ((u4)mon & 1) != 0 || mon->owner != self) {
712 dvmThrowException("Ljava/lang/IllegalMonitorStateException;",
713 "object not locked by thread before notifyAll()");
717 mon->notifying = mon->waiting - mon->interrupting;
718 if (mon->notifying > 0) {
721 LOGVV("threadid=%d: broadcasting to %d threads on %p\n",
722 self->threadId, mon->notifying, mon);
724 cc = pthread_cond_broadcast(&mon->cond);
727 LOGVV("threadid=%d: nobody to broadcast to on %p\n", self->threadId,mon);
733 * Thin locking support
737 * Implements monitorenter for "synchronized" stuff.
739 * This does not fail or throw an exception (unless deadlock prediction
740 * is enabled and set to "err" mode).
742 void dvmLockObject(Thread* self, Object *obj)
744 volatile u4 *thinp = &obj->lock.thin;
745 u4 threadId = self->threadId;
747 /* First, try to grab the lock as if it's thin;
748 * this is the common case and will usually succeed.
750 if (!ATOMIC_CMP_SWAP((int32_t *)thinp,
751 (int32_t)DVM_LOCK_INITIAL_THIN_VALUE,
752 (int32_t)threadId)) {
753 /* The lock is either a thin lock held by someone (possibly 'self'),
756 if ((*thinp & 0xffff) == threadId) {
757 /* 'self' is already holding the thin lock; we can just
758 * bump the count. Atomic operations are not necessary
759 * because only the thread holding the lock is allowed
760 * to modify the Lock field.
764 /* If this is a thin lock we need to spin on it, if it's fat
765 * we need to acquire the monitor.
767 if ((*thinp & 1) != 0) {
768 ThreadStatus oldStatus;
769 static const unsigned long maxSleepDelay = 1 * 1024 * 1024;
770 unsigned long sleepDelay;
772 LOG_THIN("(%d) spin on lock 0x%08x: 0x%08x (0x%08x) 0x%08x\n",
773 threadId, (uint)&obj->lock,
774 DVM_LOCK_INITIAL_THIN_VALUE, *thinp, threadId);
776 /* The lock is still thin, but some other thread is
777 * holding it. Let the VM know that we're about
778 * to wait on another thread.
780 oldStatus = dvmChangeStatus(self, THREAD_MONITOR);
782 /* Spin until the other thread lets go.
786 /* In addition to looking for an unlock,
787 * we need to watch out for some other thread
788 * fattening the lock behind our back.
790 while (*thinp != DVM_LOCK_INITIAL_THIN_VALUE) {
791 if ((*thinp & 1) == 0) {
792 /* The lock has been fattened already.
794 LOG_THIN("(%d) lock 0x%08x surprise-fattened\n",
795 threadId, (uint)&obj->lock);
796 dvmChangeStatus(self, oldStatus);
800 if (sleepDelay == 0) {
802 sleepDelay = 1 * 1000;
805 if (sleepDelay < maxSleepDelay / 2) {
810 } while (!ATOMIC_CMP_SWAP((int32_t *)thinp,
811 (int32_t)DVM_LOCK_INITIAL_THIN_VALUE,
813 LOG_THIN("(%d) spin on lock done 0x%08x: "
814 "0x%08x (0x%08x) 0x%08x\n",
815 threadId, (uint)&obj->lock,
816 DVM_LOCK_INITIAL_THIN_VALUE, *thinp, threadId);
818 /* We've got the thin lock; let the VM know that we're
821 dvmChangeStatus(self, oldStatus);
823 /* Fatten the lock. Note this relinquishes ownership.
824 * We could also create the monitor in an "owned" state
825 * to avoid "re-locking" it in fat_lock.
827 obj->lock.mon = dvmCreateMonitor(obj);
828 LOG_THIN("(%d) lock 0x%08x fattened\n",
829 threadId, (uint)&obj->lock);
831 /* Fall through to acquire the newly fat lock.
835 /* The lock is already fat, which means
836 * that obj->lock.mon is a regular (Monitor *).
839 assert(obj->lock.mon != NULL);
840 lockMonitor(self, obj->lock.mon);
843 // else, the lock was acquired with the ATOMIC_CMP_SWAP().
845 #ifdef WITH_DEADLOCK_PREDICTION
847 * See if we were allowed to grab the lock at this time. We do it
848 * *after* acquiring the lock, rather than before, so that we can
849 * freely update the Monitor struct. This seems counter-intuitive,
850 * but our goal is deadlock *prediction* not deadlock *prevention*.
851 * (If we actually deadlock, the situation is easy to diagnose from
852 * a thread dump, so there's no point making a special effort to do
853 * the checks before the lock is held.)
855 * This needs to happen before we add the object to the thread's
856 * monitor list, so we can tell the difference between first-lock and
859 * It's also important that we do this while in THREAD_RUNNING, so
860 * that we don't interfere with cleanup operations in the GC.
862 if (gDvm.deadlockPredictMode != kDPOff) {
863 if (self->status != THREAD_RUNNING) {
864 LOGE("Bad thread status (%d) in DP\n", self->status);
865 dvmDumpThread(self, false);
868 assert(!dvmCheckException(self));
869 updateDeadlockPrediction(self, obj);
870 if (dvmCheckException(self)) {
872 * If we're throwing an exception here, we need to free the
873 * lock. We add the object to the thread's monitor list so the
874 * "unlock" code can remove it.
876 dvmAddToMonitorList(self, obj, false);
877 dvmUnlockObject(self, obj);
878 LOGV("--- unlocked, pending is '%s'\n",
879 dvmGetException(self)->clazz->descriptor);
884 * Add the locked object, and the current stack trace, to the list
885 * held by the Thread object. If deadlock prediction isn't on,
886 * don't capture the stack trace.
888 dvmAddToMonitorList(self, obj, gDvm.deadlockPredictMode != kDPOff);
889 #elif defined(WITH_MONITOR_TRACKING)
891 * Add the locked object to the list held by the Thread object.
893 dvmAddToMonitorList(self, obj, false);
898 * Implements monitorexit for "synchronized" stuff.
900 * On failure, throws an exception and returns "false".
902 bool dvmUnlockObject(Thread* self, Object *obj)
904 volatile u4 *thinp = &obj->lock.thin;
905 u4 threadId = self->threadId;
907 /* Check the common case, where 'self' has locked 'obj' once, first.
909 if (*thinp == threadId) {
910 /* Unlock 'obj' by clearing our threadId from 'thin'.
911 * The lock protects the lock field itself, so it's
912 * safe to update non-atomically.
914 *thinp = DVM_LOCK_INITIAL_THIN_VALUE;
915 } else if ((*thinp & 1) != 0) {
916 /* If the object is locked, it had better be locked by us.
918 if ((*thinp & 0xffff) != threadId) {
919 /* The JNI spec says that we should throw an exception
922 //LOGW("Unlock thin %p: id %d vs %d\n",
923 // obj, (*thinp & 0xfff), threadId);
924 dvmThrowException("Ljava/lang/IllegalMonitorStateException;",
925 "unlock of unowned monitor");
929 /* It's a thin lock, but 'self' has locked 'obj'
930 * more than once. Decrement the count.
936 assert(obj->lock.mon != NULL);
937 if (!unlockMonitor(self, obj->lock.mon)) {
938 /* exception has been raised */
943 #ifdef WITH_MONITOR_TRACKING
945 * Remove the object from the Thread's list.
947 dvmRemoveFromMonitorList(self, obj);
954 * Object.wait(). Also called for class init.
956 void dvmObjectWait(Thread* self, Object *obj, s8 msec, s4 nsec,
957 bool interruptShouldThrow)
959 Monitor* mon = obj->lock.mon;
960 u4 thin = obj->lock.thin;
962 /* If the lock is still thin, we need to fatten it.
964 if ((thin & 1) != 0) {
965 /* Make sure that 'self' holds the lock.
967 if ((thin & 0xffff) != self->threadId) {
968 dvmThrowException("Ljava/lang/IllegalMonitorStateException;",
969 "object not locked by thread before wait()");
973 /* This thread holds the lock. We need to fatten the lock
974 * so 'self' can block on it. Don't update the object lock
975 * field yet, because 'self' needs to acquire the lock before
976 * any other thread gets a chance.
978 mon = dvmCreateMonitor(obj);
980 /* 'self' has actually locked the object one or more times;
981 * make sure that the monitor reflects this.
983 lockMonitor(self, mon);
984 mon->lockCount = thin >> 16;
985 LOG_THIN("(%d) lock 0x%08x fattened by wait() to count %d\n",
986 self->threadId, (uint)&obj->lock, mon->lockCount);
988 /* Make the monitor public now that it's in the right state.
993 waitMonitor(self, mon, msec, nsec, interruptShouldThrow);
999 void dvmObjectNotify(Thread* self, Object *obj)
1001 Monitor* mon = obj->lock.mon;
1002 u4 thin = obj->lock.thin;
1004 /* If the lock is still thin, there aren't any waiters;
1005 * waiting on an object forces lock fattening.
1007 if ((thin & 1) != 0) {
1008 /* Make sure that 'self' holds the lock.
1010 if ((thin & 0xffff) != self->threadId) {
1011 dvmThrowException("Ljava/lang/IllegalMonitorStateException;",
1012 "object not locked by thread before notify()");
1016 /* no-op; there are no waiters to notify.
1021 notifyMonitor(self, mon);
1026 * Object.notifyAll().
1028 void dvmObjectNotifyAll(Thread* self, Object *obj)
1030 u4 thin = obj->lock.thin;
1032 /* If the lock is still thin, there aren't any waiters;
1033 * waiting on an object forces lock fattening.
1035 if ((thin & 1) != 0) {
1036 /* Make sure that 'self' holds the lock.
1038 if ((thin & 0xffff) != self->threadId) {
1039 dvmThrowException("Ljava/lang/IllegalMonitorStateException;",
1040 "object not locked by thread before notifyAll()");
1044 /* no-op; there are no waiters to notify.
1047 Monitor* mon = obj->lock.mon;
1051 notifyAllMonitor(self, mon);
1055 #else // not THIN_LOCKING
1058 * Implements monitorenter for "synchronized" stuff.
1060 * This does not fail or throw an exception.
1062 void dvmLockObject(Thread* self, Object* obj)
1064 Monitor* mon = obj->lock.mon;
1067 mon = dvmCreateMonitor(obj);
1068 if (!ATOMIC_CMP_SWAP((int32_t *)&obj->lock.mon,
1069 (int32_t)NULL, (int32_t)mon)) {
1070 /* somebody else beat us to it */
1071 releaseMonitor(mon);
1072 mon = obj->lock.mon;
1076 lockMonitor(self, mon);
1080 * Implements monitorexit for "synchronized" stuff.
1082 bool dvmUnlockObject(Thread* self, Object* obj)
1084 Monitor* mon = obj->lock.mon;
1086 return unlockMonitor(self, mon);
1093 void dvmObjectWait(Thread* self, Object* obj, u8 msec, u4 nsec)
1095 Monitor* mon = obj->lock.mon;
1097 waitMonitor(self, mon, msec, nsec);
1103 void dvmObjectNotify(Thread* self, Object* obj)
1105 Monitor* mon = obj->lock.mon;
1107 notifyMonitor(self, mon);
1111 * Object.notifyAll().
1113 void dvmObjectNotifyAll(Thread* self, Object* obj)
1115 Monitor* mon = obj->lock.mon;
1117 notifyAllMonitor(self, mon);
1120 #endif // not THIN_LOCKING
1124 * This implements java.lang.Thread.sleep(long msec, int nsec).
1126 * The sleep is interruptible by other threads, which means we can't just
1127 * plop into an OS sleep call. (We probably could if we wanted to send
1128 * signals around and rely on EINTR, but that's inefficient and relies
1129 * on native code respecting our signal mask.)
1131 * We have to do all of this stuff for Object.wait() as well, so it's
1132 * easiest to just sleep on a private Monitor.
1134 * It appears that we want sleep(0,0) to go through the motions of sleeping
1135 * for a very short duration, rather than just returning.
1137 void dvmThreadSleep(u8 msec, u4 nsec)
1139 Thread* self = dvmThreadSelf();
1140 Monitor* mon = gDvm.threadSleepMon;
1142 /* sleep(0,0) wakes up immediately, wait(0,0) means wait forever; adjust */
1143 if (msec == 0 && nsec == 0)
1146 lockMonitor(self, mon);
1147 waitMonitor(self, mon, msec, nsec, true);
1148 unlockMonitor(self, mon);
1152 * Implement java.lang.Thread.interrupt().
1154 * We need to increment the monitor's "interrupting" count, and set the
1155 * interrupted status for the thread in question. Doing so requires
1156 * gaining the monitor's lock, which may not happen in a timely fashion.
1157 * We are left with a decision between failing to interrupt the thread
1158 * and stalling the interrupting thread.
1160 * We must take some care to ensure that we don't try to interrupt the same
1161 * thread on the same mutex twice. Doing so would leave us with an
1162 * incorrect value for Monitor.interrupting.
1164 void dvmThreadInterrupt(volatile Thread* thread)
1169 * Raise the "interrupted" flag. This will cause it to bail early out
1170 * of the next wait() attempt, if it's not currently waiting on
1173 thread->interrupted = true;
1177 * Is the thread waiting?
1179 * Note that fat vs. thin doesn't matter here; waitMonitor
1180 * is only set when a thread actually waits on a monitor,
1181 * which implies that the monitor has already been fattened.
1183 mon = thread->waitMonitor;
1188 * Try to acquire the monitor, if we don't already own it. We need
1189 * to hold the same mutex as the thread in order to signal the
1190 * condition it's waiting on. When the thread goes to sleep it will
1191 * release the monitor's mutex, allowing us to signal it.
1193 * TODO: we may be able to get rid of the explicit lock by coordinating
1194 * this more closely with waitMonitor.
1196 Thread* self = dvmThreadSelf();
1197 if (!tryLockMonitor(self, mon)) {
1199 * Failed to get the monitor the thread is waiting on; most likely
1200 * the other thread is in the middle of doing something.
1202 const int kSpinSleepTime = 500*1000; /* 0.5s */
1203 u8 startWhen = dvmGetRelativeTimeUsec();
1206 while (dvmIterativeSleep(sleepIter++, kSpinSleepTime, startWhen)) {
1208 * Still time left on the clock, try to grab it again.
1210 if (tryLockMonitor(self, mon))
1214 * If the target thread is no longer waiting on the same monitor,
1215 * the "interrupted" flag we set earlier will have caused the
1216 * interrupt when the thread woke up, so we can stop now.
1218 if (thread->waitMonitor != mon)
1223 * We have to give up or risk deadlock.
1225 LOGW("threadid=%d: unable to interrupt threadid=%d\n",
1226 self->threadId, thread->threadId);
1232 * We've got the monitor lock, which means nobody can be added or
1233 * removed from the wait list. This also means that the Thread's
1234 * waitMonitor/interruptingWait fields can't be modified by anyone
1237 * If things look good, raise flags and wake the threads sleeping
1238 * on the monitor's condition variable.
1240 if (thread->waitMonitor == mon && // still on same monitor?
1241 thread->interrupted && // interrupt still pending?
1242 !thread->interruptingWait) // nobody else is interrupting too?
1246 LOGVV("threadid=%d: interrupting threadid=%d waiting on %p\n",
1247 self->threadId, thread->threadId, mon);
1249 thread->interruptingWait = true; // prevent re-interrupt...
1250 mon->interrupting++; // ...so we only do this once
1251 cc = pthread_cond_broadcast(&mon->cond);
1255 unlockMonitor(self, mon);
1259 #ifdef WITH_DEADLOCK_PREDICTION
1261 * ===========================================================================
1262 * Deadlock prediction
1263 * ===========================================================================
1266 The idea is to predict the possibility of deadlock by recording the order
1267 in which monitors are acquired. If we see an attempt to acquire a lock
1268 out of order, we can identify the locks and offending code.
1270 To make this work, we need to keep track of the locks held by each thread,
1271 and create history trees for each lock. When a thread tries to acquire
1272 a new lock, we walk through the "history children" of the lock, looking
1273 for a match with locks the thread already holds. If we find a match,
1274 it means the thread has made a request that could result in a deadlock.
1276 To support recursive locks, we always allow re-locking a currently-held
1277 lock, and maintain a recursion depth count.
1279 An ASCII-art example, where letters represent Objects:
1289 The above is the tree we'd have after handling Object synchronization
1290 sequences "ABC", "AC", "AD". A has three children, {B, C, D}. C is also
1291 a child of B. (The lines represent pointers between parent and child.
1292 Every node can have multiple parents and multiple children.)
1294 If we hold AC, and want to lock B, we recursively search through B's
1295 children to see if A or C appears. It does, so we reject the attempt.
1296 (A straightforward way to implement it: add a link from C to B, then
1297 determine whether the graph starting at B contains a cycle.)
1299 If we hold AC and want to lock D, we would succeed, creating a new link
1302 The lock history and a stack trace is attached to the Object's Monitor
1303 struct, which means we need to fatten every Object we lock (thin locking
1304 is effectively disabled). If we don't need the stack trace we can
1305 avoid fattening the leaf nodes, only fattening objects that need to hold
1308 Updates to Monitor structs are only allowed for the thread that holds
1309 the Monitor, so we actually do most of our deadlock prediction work after
1310 the lock has been acquired.
1312 When an object with a monitor is GCed, we need to remove it from the
1313 history trees. There are two basic approaches:
1314 (1) For through the entire set of known monitors, search all child
1315 lists for the object in question. This is rather slow, resulting
1316 in GC passes that take upwards of 10 seconds to complete.
1317 (2) Maintain "parent" pointers in each node. Remove the entries as
1318 required. This requires additional storage and maintenance for
1319 every operation, but is significantly faster at GC time.
1320 For each GCed object, we merge all of the object's children into each of
1321 the object's parents.
1324 #if !defined(WITH_MONITOR_TRACKING)
1325 # error "WITH_DEADLOCK_PREDICTION requires WITH_MONITOR_TRACKING"
1329 * Clear out the contents of an ExpandingObjectList, freeing any
1330 * dynamic allocations.
1332 static void expandObjClear(ExpandingObjectList* pList)
1334 if (pList->list != NULL) {
1338 pList->alloc = pList->count = 0;
1342 * Get the number of objects currently stored in the list.
1344 static inline int expandBufGetCount(const ExpandingObjectList* pList)
1346 return pList->count;
1350 * Get the Nth entry from the list.
1352 static inline Object* expandBufGetEntry(const ExpandingObjectList* pList,
1355 return pList->list[i];
1359 * Add a new entry to the list.
1361 * We don't check for or try to enforce uniqueness. It's expected that
1362 * the higher-level code does this for us.
1364 static void expandObjAddEntry(ExpandingObjectList* pList, Object* obj)
1366 if (pList->count == pList->alloc) {
1367 /* time to expand */
1370 if (pList->alloc == 0)
1374 LOGVV("expanding %p to %d\n", pList, pList->alloc);
1375 newList = realloc(pList->list, pList->alloc * sizeof(Object*));
1376 if (newList == NULL) {
1377 LOGE("Failed expanding DP object list (alloc=%d)\n", pList->alloc);
1380 pList->list = newList;
1383 pList->list[pList->count++] = obj;
1387 * Returns "true" if the element was successfully removed.
1389 static bool expandObjRemoveEntry(ExpandingObjectList* pList, Object* obj)
1393 for (i = pList->count-1; i >= 0; i--) {
1394 if (pList->list[i] == obj)
1400 if (i != pList->count-1) {
1402 * The order of elements is not important, so we just copy the
1403 * last entry into the new slot.
1405 //memmove(&pList->list[i], &pList->list[i+1],
1406 // (pList->count-1 - i) * sizeof(pList->list[0]));
1407 pList->list[i] = pList->list[pList->count-1];
1411 pList->list[pList->count] = (Object*) 0xdecadead;
1416 * Returns "true" if "obj" appears in the list.
1418 static bool expandObjHas(const ExpandingObjectList* pList, Object* obj)
1422 for (i = 0; i < pList->count; i++) {
1423 if (pList->list[i] == obj)
1430 * Print the list contents to stdout. For debugging.
1432 static void expandObjDump(const ExpandingObjectList* pList)
1435 for (i = 0; i < pList->count; i++)
1436 printf(" %p", pList->list[i]);
1440 * Check for duplicate entries. Returns the index of the first instance
1441 * of the duplicated value, or -1 if no duplicates were found.
1443 static int expandObjCheckForDuplicates(const ExpandingObjectList* pList)
1446 for (i = 0; i < pList->count-1; i++) {
1447 for (j = i + 1; j < pList->count; j++) {
1448 if (pList->list[i] == pList->list[j]) {
1459 * Determine whether "child" appears in the list of objects associated
1460 * with the Monitor in "parent". If "parent" is a thin lock, we return
1461 * false immediately.
1463 static bool objectInChildList(const Object* parent, Object* child)
1465 Lock lock = parent->lock;
1466 if (!IS_LOCK_FAT(&lock)) {
1467 //LOGI("on thin\n");
1471 return expandObjHas(&lock.mon->historyChildren, child);
1475 * Print the child list.
1477 static void dumpKids(Object* parent)
1479 Monitor* mon = parent->lock.mon;
1481 printf("Children of %p:", parent);
1482 expandObjDump(&mon->historyChildren);
1487 * Add "child" to the list of children in "parent", and add "parent" to
1488 * the list of parents in "child".
1490 static void linkParentToChild(Object* parent, Object* child)
1492 //assert(parent->lock.mon->owner == dvmThreadSelf()); // !owned for merge
1493 assert(IS_LOCK_FAT(&parent->lock));
1494 assert(IS_LOCK_FAT(&child->lock));
1495 assert(parent != child);
1498 mon = parent->lock.mon;
1499 assert(!expandObjHas(&mon->historyChildren, child));
1500 expandObjAddEntry(&mon->historyChildren, child);
1502 mon = child->lock.mon;
1503 assert(!expandObjHas(&mon->historyParents, parent));
1504 expandObjAddEntry(&mon->historyParents, parent);
1509 * Remove "child" from the list of children in "parent".
1511 static void unlinkParentFromChild(Object* parent, Object* child)
1513 //assert(parent->lock.mon->owner == dvmThreadSelf()); // !owned for GC
1514 assert(IS_LOCK_FAT(&parent->lock));
1515 assert(IS_LOCK_FAT(&child->lock));
1516 assert(parent != child);
1519 mon = parent->lock.mon;
1520 if (!expandObjRemoveEntry(&mon->historyChildren, child)) {
1521 LOGW("WARNING: child %p not found in parent %p\n", child, parent);
1523 assert(!expandObjHas(&mon->historyChildren, child));
1524 assert(expandObjCheckForDuplicates(&mon->historyChildren) < 0);
1526 mon = child->lock.mon;
1527 if (!expandObjRemoveEntry(&mon->historyParents, parent)) {
1528 LOGW("WARNING: parent %p not found in child %p\n", parent, child);
1530 assert(!expandObjHas(&mon->historyParents, parent));
1531 assert(expandObjCheckForDuplicates(&mon->historyParents) < 0);
1536 * Log the monitors held by the current thread. This is done as part of
1537 * flagging an error.
1539 static void logHeldMonitors(Thread* self)
1543 name = dvmGetThreadName(self);
1544 LOGW("Monitors currently held by thread (threadid=%d '%s')\n",
1545 self->threadId, name);
1546 LOGW("(most-recently-acquired on top):\n");
1549 LockedObjectData* lod = self->pLockedObjects;
1550 while (lod != NULL) {
1551 LOGW("--- object %p[%d] (%s)\n",
1552 lod->obj, lod->recursionCount, lod->obj->clazz->descriptor);
1553 dvmLogRawStackTrace(lod->rawStackTrace, lod->stackDepth);
1560 * Recursively traverse the object hierarchy starting at "obj". We mark
1561 * ourselves on entry and clear the mark on exit. If we ever encounter
1562 * a marked object, we have a cycle.
1564 * Returns "true" if all is well, "false" if we found a cycle.
1566 static bool traverseTree(Thread* self, const Object* obj)
1568 assert(IS_LOCK_FAT(&obj->lock));
1569 Monitor* mon = obj->lock.mon;
1572 * Have we been here before?
1574 if (mon->historyMark) {
1578 LOGW("%s\n", kStartBanner);
1579 LOGW("Illegal lock attempt:\n");
1580 LOGW("--- object %p (%s)\n", obj, obj->clazz->descriptor);
1582 rawStackTrace = dvmFillInStackTraceRaw(self, &stackDepth);
1583 dvmLogRawStackTrace(rawStackTrace, stackDepth);
1584 free(rawStackTrace);
1587 logHeldMonitors(self);
1590 LOGW("Earlier, the following lock order (from last to first) was\n");
1591 LOGW("established -- stack trace is from first successful lock):\n");
1594 mon->historyMark = true;
1597 * Examine the children. We do NOT hold these locks, so they might
1598 * very well transition from thin to fat or change ownership while
1601 * NOTE: we rely on the fact that they cannot revert from fat to thin
1602 * while we work. This is currently a safe assumption.
1604 * We can safely ignore thin-locked children, because by definition
1605 * they have no history and are leaf nodes. In the current
1606 * implementation we always fatten the locks to provide a place to
1607 * hang the stack trace.
1609 ExpandingObjectList* pList = &mon->historyChildren;
1611 for (i = expandBufGetCount(pList)-1; i >= 0; i--) {
1612 const Object* child = expandBufGetEntry(pList, i);
1613 Lock lock = child->lock;
1614 if (!IS_LOCK_FAT(&lock))
1616 if (!traverseTree(self, child)) {
1617 LOGW("--- object %p (%s)\n", obj, obj->clazz->descriptor);
1618 dvmLogRawStackTrace(mon->historyRawStackTrace,
1619 mon->historyStackDepth);
1620 mon->historyMark = false;
1625 mon->historyMark = false;
1631 * Update the deadlock prediction tree, based on the current thread
1632 * acquiring "acqObj". This must be called before the object is added to
1633 * the thread's list of held monitors.
1635 * If the thread already holds the lock (recursion), or this is a known
1636 * lock configuration, we return without doing anything. Otherwise, we add
1637 * a link from the most-recently-acquired lock in this thread to "acqObj"
1638 * after ensuring that the parent lock is "fat".
1640 * This MUST NOT be called while a GC is in progress in another thread,
1641 * because we assume exclusive access to history trees in owned monitors.
1643 static void updateDeadlockPrediction(Thread* self, Object* acqObj)
1645 LockedObjectData* lod;
1646 LockedObjectData* mrl;
1649 * Quick check for recursive access.
1651 lod = dvmFindInMonitorList(self, acqObj);
1653 LOGV("+++ DP: recursive %p\n", acqObj);
1658 * Make the newly-acquired object's monitor "fat". In some ways this
1659 * isn't strictly necessary, but we need the GC to tell us when
1660 * "interesting" objects go away, and right now the only way to make
1661 * an object look interesting is to give it a monitor.
1663 * This also gives us a place to hang a stack trace.
1665 * Our thread holds the lock, so we're allowed to rewrite the lock
1666 * without worrying that something will change out from under us.
1668 if (!IS_LOCK_FAT(&acqObj->lock)) {
1669 LOGVV("fattening lockee %p (recur=%d)\n",
1670 acqObj, acqObj->lock.thin >> 16);
1671 Monitor* newMon = dvmCreateMonitor(acqObj);
1672 lockMonitor(self, newMon); // can't stall, don't need VMWAIT
1673 newMon->lockCount += acqObj->lock.thin >> 16;
1674 acqObj->lock.mon = newMon;
1677 /* if we don't have a stack trace for this monitor, establish one */
1678 if (acqObj->lock.mon->historyRawStackTrace == NULL) {
1679 Monitor* mon = acqObj->lock.mon;
1680 mon->historyRawStackTrace = dvmFillInStackTraceRaw(self,
1681 &mon->historyStackDepth);
1685 * We need to examine and perhaps modify the most-recently-locked
1686 * monitor. We own that, so there's no risk of another thread
1689 * Retrieve the most-recently-locked entry from our thread.
1691 mrl = self->pLockedObjects;
1693 return; /* no other locks held */
1696 * Do a quick check to see if "acqObj" is a direct descendant. We can do
1697 * this without holding the global lock because of our assertion that
1698 * a GC is not running in parallel -- nobody except the GC can
1699 * modify a history list in a Monitor they don't own, and we own "mrl".
1700 * (There might be concurrent *reads*, but no concurrent *writes.)
1702 * If we find it, this is a known good configuration, and we're done.
1704 if (objectInChildList(mrl->obj, acqObj))
1708 * "mrl" is going to need to have a history tree. If it's currently
1709 * a thin lock, we make it fat now. The thin lock might have a
1710 * nonzero recursive lock count, which we need to carry over.
1712 * Our thread holds the lock, so we're allowed to rewrite the lock
1713 * without worrying that something will change out from under us.
1715 if (!IS_LOCK_FAT(&mrl->obj->lock)) {
1716 LOGVV("fattening parent %p f/b/o child %p (recur=%d)\n",
1717 mrl->obj, acqObj, mrl->obj->lock.thin >> 16);
1718 Monitor* newMon = dvmCreateMonitor(mrl->obj);
1719 lockMonitor(self, newMon); // can't stall, don't need VMWAIT
1720 newMon->lockCount += mrl->obj->lock.thin >> 16;
1721 mrl->obj->lock.mon = newMon;
1725 * We haven't seen this configuration before. We need to scan down
1726 * acqObj's tree to see if any of the monitors in self->pLockedObjects
1727 * appear. We grab a global lock before traversing or updating the
1730 * If we find a match for any of our held locks, we know that the lock
1731 * has previously been acquired *after* acqObj, and we throw an error.
1733 * The easiest way to do this is to create a link from "mrl" to "acqObj"
1734 * and do a recursive traversal, marking nodes as we cross them. If
1735 * we cross one a second time, we have a cycle and can throw an error.
1736 * (We do the flag-clearing traversal before adding the new link, so
1737 * that we're guaranteed to terminate.)
1739 * If "acqObj" is a thin lock, it has no history, and we can create a
1740 * link to it without additional checks. [ We now guarantee that it's
1743 bool failed = false;
1744 dvmLockMutex(&gDvm.deadlockHistoryLock);
1745 linkParentToChild(mrl->obj, acqObj);
1746 if (!traverseTree(self, acqObj)) {
1747 LOGW("%s\n", kEndBanner);
1750 /* remove the entry so we're still okay when in "warning" mode */
1751 unlinkParentFromChild(mrl->obj, acqObj);
1753 dvmUnlockMutex(&gDvm.deadlockHistoryLock);
1756 switch (gDvm.deadlockPredictMode) {
1758 dvmThrowException("Ldalvik/system/PotentialDeadlockError;", NULL);
1761 LOGE("Aborting due to potential deadlock\n");
1772 * We're removing "child" from existence. We want to pull all of
1773 * child's children into "parent", filtering out duplicates. This is
1774 * called during the GC.
1776 * This does not modify "child", which might have multiple parents.
1778 static void mergeChildren(Object* parent, const Object* child)
1783 assert(IS_LOCK_FAT(&child->lock));
1784 mon = child->lock.mon;
1785 ExpandingObjectList* pList = &mon->historyChildren;
1787 for (i = expandBufGetCount(pList)-1; i >= 0; i--) {
1788 Object* grandChild = expandBufGetEntry(pList, i);
1790 if (!objectInChildList(parent, grandChild)) {
1791 LOGVV("+++ migrating %p link to %p\n", grandChild, parent);
1792 linkParentToChild(parent, grandChild);
1794 LOGVV("+++ parent %p already links to %p\n", parent, grandChild);
1800 * An object with a fat lock is being collected during a GC pass. We
1801 * want to remove it from any lock history trees that it is a part of.
1803 * This may require updating the history trees in several monitors. The
1804 * monitor semantics guarantee that no other thread will be accessing
1805 * the history trees at the same time.
1807 static void removeCollectedObject(Object* obj)
1811 LOGVV("+++ collecting %p\n", obj);
1815 * We're currently running through the entire set of known monitors.
1816 * This can be somewhat slow. We may want to keep lists of parents
1817 * in each child to speed up GC.
1819 mon = gDvm.monitorList;
1820 while (mon != NULL) {
1821 Object* parent = mon->obj;
1822 if (parent != NULL) { /* value nulled for deleted entries */
1823 if (objectInChildList(parent, obj)) {
1824 LOGVV("removing child %p from parent %p\n", obj, parent);
1825 unlinkParentFromChild(parent, obj);
1826 mergeChildren(parent, obj);
1834 * For every parent of this object:
1835 * - merge all of our children into the parent's child list (creates
1836 * a two-way link between parent and child)
1837 * - remove ourselves from the parent's child list
1839 ExpandingObjectList* pList;
1842 assert(IS_LOCK_FAT(&obj->lock));
1843 mon = obj->lock.mon;
1844 pList = &mon->historyParents;
1845 for (i = expandBufGetCount(pList)-1; i >= 0; i--) {
1846 Object* parent = expandBufGetEntry(pList, i);
1847 Monitor* parentMon = parent->lock.mon;
1849 if (!expandObjRemoveEntry(&parentMon->historyChildren, obj)) {
1850 LOGW("WARNING: child %p not found in parent %p\n", obj, parent);
1852 assert(!expandObjHas(&parentMon->historyChildren, obj));
1854 mergeChildren(parent, obj);
1858 * For every child of this object:
1859 * - remove ourselves from the child's parent list
1861 pList = &mon->historyChildren;
1862 for (i = expandBufGetCount(pList)-1; i >= 0; i--) {
1863 Object* child = expandBufGetEntry(pList, i);
1864 Monitor* childMon = child->lock.mon;
1866 if (!expandObjRemoveEntry(&childMon->historyParents, obj)) {
1867 LOGW("WARNING: parent %p not found in child %p\n", obj, child);
1869 assert(!expandObjHas(&childMon->historyParents, obj));
1873 #endif /*WITH_DEADLOCK_PREDICTION*/