Update the hash state bits when an identity hash code is computed.
diff --git a/vm/Sync.c b/vm/Sync.c
index 24e3917..b7a83bd 100644
--- a/vm/Sync.c
+++ b/vm/Sync.c
@@ -236,26 +236,37 @@
 }
 
 /*
+ * Returns the thread id of the thread owning the given lock.
+ */
+static u4 lockOwner(Object* obj)
+{
+    Thread *owner;
+    u4 lock;
+
+    assert(obj != NULL);
+    /*
+     * Since we're reading the lock value multiple times, latch it so
+     * that it doesn't change out from under us if we get preempted.
+     */
+    lock = obj->lock;
+    if (LW_SHAPE(lock) == LW_SHAPE_THIN) {
+        return LW_LOCK_OWNER(lock);
+    } else {
+        owner = LW_MONITOR(lock)->owner;
+        return owner ? owner->threadId : 0;
+    }
+}
+
+/*
  * Checks whether the given thread holds the given
  * objects's lock.
  */
 bool dvmHoldsLock(Thread* thread, Object* obj)
 {
-    u4 thin;
-
     if (thread == NULL || obj == NULL) {
         return false;
-    }
-
-    /* Since we're reading the lock value multiple times,
-     * latch it so that it doesn't change out from under
-     * us if we get preempted.
-     */
-    thin = obj->lock;
-    if (LW_SHAPE(thin) == LW_SHAPE_FAT) {
-        return thread == LW_MONITOR(thin)->owner;
     } else {
-        return thread->threadId == LW_LOCK_OWNER(thin);
+        return thread->threadId == lockOwner(obj);
     }
 }
 
@@ -343,12 +354,6 @@
 
         mon->owner = self;
         assert(mon->lockCount == 0);
-
-        /*
-         * "waiting", "notifying", and "interrupting" could all be nonzero
-         * if we're locking an object on which other threads are waiting.
-         * Nothing worth assert()ing about here.
-         */
     }
 }
 
@@ -442,13 +447,15 @@
 }
 
 /*
- * Links a thread into a monitor's wait set.
+ * Links a thread into a monitor's wait set.  The monitor lock must be
+ * held by the caller of this routine.
  */
 static void waitSetAppend(Monitor *mon, Thread *thread)
 {
     Thread *elt;
 
     assert(mon != NULL);
+    assert(mon->owner == dvmThreadSelf());
     assert(thread != NULL);
     assert(thread->waitNext == NULL);
     assert(waitSetCheck(mon) == 0);
@@ -464,13 +471,15 @@
 }
 
 /*
- * Unlinks a thread from a monitor's wait set.
+ * Unlinks a thread from a monitor's wait set.  The monitor lock must
+ * be held by the caller of this routine.
  */
 static void waitSetRemove(Monitor *mon, Thread *thread)
 {
     Thread *elt;
 
     assert(mon != NULL);
+    assert(mon->owner == dvmThreadSelf());
     assert(thread != NULL);
     assert(waitSetCheck(mon) == 0);
     if (mon->waitSet == NULL) {
@@ -658,7 +667,7 @@
 
     pthread_mutex_unlock(&self->waitMutex);
 
-    /* Reaquire the monitor lock. */
+    /* Reacquire the monitor lock. */
     lockMonitor(self, mon);
 
     waitSetRemove(mon, self);
@@ -677,7 +686,7 @@
     if (wasInterrupted) {
         /*
          * We were interrupted while waiting, or somebody interrupted an
-         * un-interruptable thread earlier and we're bailing out immediately.
+         * un-interruptible thread earlier and we're bailing out immediately.
          *
          * The doc sayeth: "The interrupted status of the current thread is
          * cleared when this exception is thrown."
@@ -704,8 +713,8 @@
             "object not locked by thread before notify()");
         return;
     }
-    /* Signal the first thread in the wait set. */
-    if (mon->waitSet != NULL) {
+    /* Signal the first waiting thread in the wait set. */
+    while (mon->waitSet != NULL) {
         thread = mon->waitSet;
         mon->waitSet = thread->waitNext;
         thread->waitNext = NULL;
@@ -713,6 +722,8 @@
         /* Check to see if the thread is still waiting. */
         if (thread->waitMonitor != NULL) {
             pthread_cond_signal(&thread->waitCond);
+            pthread_mutex_unlock(&thread->waitMutex);
+            return;
         }
         pthread_mutex_unlock(&thread->waitMutex);
     }
@@ -765,10 +776,11 @@
     /* First, try to grab the lock as if it's thin;
      * this is the common case and will usually succeed.
      */
+    hashState = LW_HASH_STATE(*thinp) << LW_HASH_STATE_SHIFT;
     thin = threadId << LW_LOCK_OWNER_SHIFT;
-    thin |= LW_HASH_STATE(*thinp) << LW_HASH_STATE_SHIFT;
+    thin |= hashState;
     if (!ATOMIC_CMP_SWAP((int32_t *)thinp,
-                         (int32_t)DVM_LOCK_INITIAL_THIN_VALUE,
+                         hashState,
                          (int32_t)thin)) {
         /* The lock is either a thin lock held by someone (possibly 'self'),
          * or a fat lock.
@@ -791,7 +803,7 @@
 
                 LOG_THIN("(%d) spin on lock 0x%08x: 0x%08x (0x%08x) 0x%08x\n",
                          threadId, (uint)&obj->lock,
-                         DVM_LOCK_INITIAL_THIN_VALUE, *thinp, thin);
+                         hashState, *thinp, thin);
 
                 /* The lock is still thin, but some other thread is
                  * holding it.  Let the VM know that we're about
@@ -827,15 +839,16 @@
                             }
                         }
                     }
+                    hashState = LW_HASH_STATE(*thinp) << LW_HASH_STATE_SHIFT;
                     thin = threadId << LW_LOCK_OWNER_SHIFT;
-                    thin |= LW_HASH_STATE(*thinp) << LW_HASH_STATE_SHIFT;
+                    thin |= hashState;
                 } while (!ATOMIC_CMP_SWAP((int32_t *)thinp,
-                                          (int32_t)DVM_LOCK_INITIAL_THIN_VALUE,
+                                          (int32_t)hashState,
                                           (int32_t)thin));
                 LOG_THIN("(%d) spin on lock done 0x%08x: "
                          "0x%08x (0x%08x) 0x%08x\n",
                          threadId, (uint)&obj->lock,
-                         DVM_LOCK_INITIAL_THIN_VALUE, *thinp, thin);
+                         hashState, *thinp, thin);
 
                 /* We've got the thin lock; let the VM know that we're
                  * done waiting.
@@ -1112,8 +1125,6 @@
  */
 void dvmThreadInterrupt(Thread* thread)
 {
-    Monitor* mon;
-
     assert(thread != NULL);
 
     pthread_mutex_lock(&thread->waitMutex);
@@ -1149,10 +1160,196 @@
     pthread_mutex_unlock(&thread->waitMutex);
 }
 
+#ifndef WITH_COPYING_GC
 u4 dvmIdentityHashCode(Object *obj)
 {
     return (u4)obj;
 }
+#else
+static size_t arrayElementWidth(const ArrayObject *array)
+{
+    const char *descriptor;
+
+    if (dvmIsObjectArray(array)) {
+	return sizeof(Object *);
+    } else {
+	descriptor = array->obj.clazz->descriptor;
+        switch (descriptor[1]) {
+        case 'B': return 1;  /* byte */
+        case 'C': return 2;  /* char */
+        case 'D': return 8;  /* double */
+        case 'F': return 4;  /* float */
+        case 'I': return 4;  /* int */
+        case 'J': return 8;  /* long */
+        case 'S': return 2;  /* short */
+        case 'Z': return 1;  /* boolean */
+        }
+    }
+    LOGE("object %p has an unhandled descriptor '%s'", array, descriptor);
+    dvmDumpThread(dvmThreadSelf(), false);
+    dvmAbort();
+    return 0;  /* Quiet the compiler. */
+}
+
+static size_t arrayObjectLength(const ArrayObject *array)
+{
+    size_t length;
+
+    length = offsetof(ArrayObject, contents);
+    length += array->length * arrayElementWidth(array);
+    return length;
+}
+
+/*
+ * Returns the identity hash code of the given object.
+ */
+u4 dvmIdentityHashCode(Object *obj)
+{
+    Thread *self, *thread;
+    volatile u4 *lw;
+    size_t length;
+    u4 lock, owner, hashState;
+
+    if (obj == NULL) {
+        /*
+         * Null is defined to have an identity hash code of 0.
+         */
+        return 0;
+    }
+    lw = &obj->lock;
+retry:
+    hashState = LW_HASH_STATE(*lw);
+    if (hashState == LW_HASH_STATE_HASHED) {
+        /*
+         * The object has been hashed but has not had its hash code
+         * relocated by the garbage collector.  Use the raw object
+         * address.
+         */
+        return (u4)obj >> 3;
+    } else if (hashState == LW_HASH_STATE_HASHED_AND_MOVED) {
+        /*
+         * The object has been hashed and its hash code has been
+         * relocated by the collector.  Use the value of the naturally
+         * aligned word following the instance data.
+         */
+        if (IS_CLASS_FLAG_SET(obj->clazz, CLASS_ISARRAY)) {
+            length = arrayObjectLength((ArrayObject *)obj);
+            length = (length + 3) & ~3;
+        } else {
+            length = obj->clazz->objectSize;
+        }
+        return *(u4 *)(((char *)obj) + length);
+    } else if (hashState == LW_HASH_STATE_UNHASHED) {
+        /*
+         * The object has never been hashed.  Change the hash state to
+         * hashed and use the raw object address.
+         */
+        self = dvmThreadSelf();
+        if (self->threadId == lockOwner(obj)) {
+            /*
+             * We already own the lock so we can update the hash state
+             * directly.
+             */
+            *lw |= (LW_HASH_STATE_HASHED << LW_HASH_STATE_SHIFT);
+            return (u4)obj >> 3;
+        }
+        /*
+         * We do not own the lock.  Try acquiring the lock.  Should
+         * this fail, we must suspend the owning thread.
+         */
+        if (LW_SHAPE(*lw) == LW_SHAPE_THIN) {
+            /*
+             * If the lock is thin assume it is unowned.  We simulate
+             * an acquire, update, and release with a single CAS.
+             */
+            lock = DVM_LOCK_INITIAL_THIN_VALUE;
+            lock |= (LW_HASH_STATE_HASHED << LW_HASH_STATE_SHIFT);
+            if (ATOMIC_CMP_SWAP((int32_t *)lw,
+                                (int32_t)DVM_LOCK_INITIAL_THIN_VALUE,
+                                (int32_t)lock)) {
+                /*
+                 * A new lockword has been installed with a hash state
+                 * of hashed.  Use the raw object address.
+                 */
+                return (u4)obj >> 3;
+            }
+        } else {
+            if (tryLockMonitor(self, LW_MONITOR(*lw))) {
+                /*
+                 * The monitor lock has been acquired.  Change the
+                 * hash state to hashed and use the raw object
+                 * address.
+                 */
+                *lw |= (LW_HASH_STATE_HASHED << LW_HASH_STATE_SHIFT);
+                unlockMonitor(self, LW_MONITOR(*lw));
+                return (u4)obj >> 3;
+            }
+        }
+        /*
+         * At this point we have failed to acquire the lock.  We must
+         * identify the owning thread and suspend it.
+         */
+        dvmLockThreadList(self);
+        /*
+         * Cache the lock word as its value can change between
+         * determining its shape and retrieving its owner.
+         */
+        lock = *lw;
+        if (LW_SHAPE(lock) == LW_SHAPE_THIN) {
+            /*
+             * Find the thread with the corresponding thread id.
+             */
+            owner = LW_LOCK_OWNER(lock);
+            assert(owner != self->threadId);
+            /*
+             * If the lock has no owner do not bother scanning the
+             * thread list and fall through to the failure handler.
+             */
+            thread = owner ? gDvm.threadList : NULL;
+            while (thread != NULL) {
+                if (thread->threadId == owner) {
+                    break;
+                }
+                thread = thread->next;
+            }
+        } else {
+            thread = LW_MONITOR(lock)->owner;
+        }
+        /*
+         * If thread is NULL the object has been released since the
+         * thread list lock was acquired.  Try again.
+         */
+        if (thread == NULL) {
+            dvmUnlockThreadList();
+            goto retry;
+        }
+        /*
+         * Wait for the owning thread to suspend.
+         */
+        dvmSuspendThread(thread);
+        if (dvmHoldsLock(thread, obj)) {
+            /*
+             * The owning thread has been suspended.  We can safely
+             * change the hash state to hashed.
+             */
+            *lw |= (LW_HASH_STATE_HASHED << LW_HASH_STATE_SHIFT);
+            dvmResumeThread(thread);
+            dvmUnlockThreadList();
+            return (u4)obj >> 3;
+        }
+        /*
+         * The wrong thread has been suspended.  Try again.
+         */
+        dvmResumeThread(thread);
+        dvmUnlockThreadList();
+        goto retry;
+    }
+    LOGE("object %p has an unknown hash state %#x", obj, hashState);
+    dvmDumpThread(dvmThreadSelf(), false);
+    dvmAbort();
+    return 0;  /* Quiet the compiler. */
+}
+#endif  /* WITH_COPYING_GC */
 
 #ifdef WITH_DEADLOCK_PREDICTION
 /*
diff --git a/vm/Sync.h b/vm/Sync.h
index 12423ae..0ce3ebc 100644
--- a/vm/Sync.h
+++ b/vm/Sync.h
@@ -19,25 +19,46 @@
 #ifndef _DALVIK_SYNC
 #define _DALVIK_SYNC
 
+/*
+ * Monitor shape field.  Used to distinguish immediate thin locks from
+ * indirecting fat locks.
+ */
 #define LW_SHAPE_THIN 0
 #define LW_SHAPE_FAT 1
 #define LW_SHAPE_MASK 0x1
 #define LW_SHAPE(x) ((x) & LW_SHAPE_MASK)
 
+/*
+ * Hash state field.  Used to signify that an object has had its
+ * identity hash code exposed or relocated.
+ */
 #define LW_HASH_STATE_UNHASHED 0
 #define LW_HASH_STATE_HASHED 1
-#define LW_HASH_STATE_HASHED_AND_MOVED 2
+#define LW_HASH_STATE_HASHED_AND_MOVED 3
 #define LW_HASH_STATE_MASK 0x3
 #define LW_HASH_STATE_SHIFT 1
 #define LW_HASH_STATE(x) (((x) >> LW_HASH_STATE_SHIFT) & LW_HASH_STATE_MASK)
 
+/*
+ * Monitor accessor.  Extracts a monitor structure pointer from a fat
+ * lock.  Performs no error checking.
+ */
 #define LW_MONITOR(x) \
-  ((Monitor*)((x) & ~((LW_HASH_STATE_MASK << LW_HASH_STATE_SHIFT) | LW_SHAPE_MASK)))
+  ((Monitor*)((x) & ~((LW_HASH_STATE_MASK << LW_HASH_STATE_SHIFT) | \
+                      LW_SHAPE_MASK)))
 
+/*
+ * Lock owner field.  Contains the thread id of the thread currently
+ * holding the lock.
+ */
 #define LW_LOCK_OWNER_MASK 0xffff
 #define LW_LOCK_OWNER_SHIFT 3
 #define LW_LOCK_OWNER(x) (((x) >> LW_LOCK_OWNER_SHIFT) & LW_LOCK_OWNER_MASK)
 
+/*
+ * Lock recursion count field.  Contains a count of the numer of times
+ * a lock has been recursively acquired.
+ */
 #define LW_LOCK_COUNT_MASK 0x1fff
 #define LW_LOCK_COUNT_SHIFT 19
 #define LW_LOCK_COUNT(x) (((x) >> LW_LOCK_COUNT_SHIFT) & LW_LOCK_COUNT_MASK)
diff --git a/vm/oo/Array.h b/vm/oo/Array.h
index 018f3d7..161b1c6 100644
--- a/vm/oo/Array.h
+++ b/vm/oo/Array.h
@@ -113,6 +113,18 @@
 }
 
 /*
+ * Verify that the array is an object array and not a primitive array.
+ *
+ * Does not verify that the object is actually a non-NULL object.
+ */
+INLINE bool dvmIsObjectArray(const ArrayObject* arrayObj)
+{
+    const char* descriptor = arrayObj->obj.clazz->descriptor;
+    return descriptor[0] == '[' && (descriptor[1] == 'L' ||
+                                    descriptor[1] == '[');
+}
+
+/*
  * Verify that the class is an array class.
  *
  * TODO: there may be some performance advantage to setting a flag in