Import the heap verification code from the copying collector.  The
reference verification routine adds an extra argument so the base
address of an object can be passed to the verification code without
provoking a warning from GCC about breaking alias analysis.

Change-Id: Idd921bcc0e084c18bff1e209a8591ef55f57843a
diff --git a/vm/Dvm.mk b/vm/Dvm.mk
index 0fa50a6..cf0d0c9 100644
--- a/vm/Dvm.mk
+++ b/vm/Dvm.mk
@@ -136,6 +136,7 @@
 	alloc/Heap.c.arm \
 	alloc/MarkSweep.c.arm \
 	alloc/DdmHeap.c \
+	alloc/Verify.c \
 	analysis/CodeVerify.c \
 	analysis/DexOptimize.c \
 	analysis/DexVerify.c \
diff --git a/vm/Sync.c b/vm/Sync.c
index 1da6c45..c00a630 100644
--- a/vm/Sync.c
+++ b/vm/Sync.c
@@ -1216,40 +1216,6 @@
     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.
  */
@@ -1283,7 +1249,7 @@
          * aligned word following the instance data.
          */
         if (IS_CLASS_FLAG_SET(obj->clazz, CLASS_ISARRAY)) {
-            length = arrayObjectLength((ArrayObject *)obj);
+            length = dvmArrayObjectLength((ArrayObject *)obj);
             length = (length + 3) & ~3;
         } else {
             length = obj->clazz->objectSize;
diff --git a/vm/Thread.c b/vm/Thread.c
index bcd3eff..1a270dc 100644
--- a/vm/Thread.c
+++ b/vm/Thread.c
@@ -518,6 +518,7 @@
     case SUSPEND_FOR_DEBUG:         return "debug";
     case SUSPEND_FOR_DEBUG_EVENT:   return "debug-event";
     case SUSPEND_FOR_STACK_DUMP:    return "stack-dump";
+    case SUSPEND_FOR_VERIFY:        return "verify";
 #if defined(WITH_JIT)
     case SUSPEND_FOR_TBL_RESIZE:    return "table-resize";
     case SUSPEND_FOR_IC_PATCH:      return "inline-cache-patch";
diff --git a/vm/Thread.h b/vm/Thread.h
index a7edb42..29cbec6 100644
--- a/vm/Thread.h
+++ b/vm/Thread.h
@@ -300,6 +300,7 @@
     SUSPEND_FOR_DEBUG_EVENT,
     SUSPEND_FOR_STACK_DUMP,
     SUSPEND_FOR_DEX_OPT,
+    SUSPEND_FOR_VERIFY,
 #if defined(WITH_JIT)
     SUSPEND_FOR_TBL_RESIZE,  // jit-table resize
     SUSPEND_FOR_IC_PATCH,    // polymorphic callsite inline-cache patch
diff --git a/vm/alloc/Verify.c b/vm/alloc/Verify.c
new file mode 100644
index 0000000..0d942ce
--- /dev/null
+++ b/vm/alloc/Verify.c
@@ -0,0 +1,194 @@
+/*
+ * Copyright (C) 2010 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "Dalvik.h"
+#include "alloc/HeapSource.h"
+#include "alloc/Verify.h"
+
+/* comment everything, of course! */
+#define VERIFY_REFERENCE(x) do {                                \
+        if (!verifyReference((x), &(x))) {                      \
+            LOGE("Verify of %p at %p failed", (x), &(x));       \
+            dvmAbort();                                         \
+        }                                                       \
+    } while (0)
+
+/*
+ * Verifies that a reference points to an object header.
+ */
+static bool verifyReference(const void *obj, const void *addr)
+{
+    if (obj == NULL) {
+        return true;
+    }
+    return dvmIsValidObject(obj);
+}
+
+/*
+ * Verifies the header, static fields references, and interface
+ * pointers of a class object.
+ */
+static void verifyClassObject(const ClassObject *obj)
+{
+    int i;
+    char ch;
+
+    LOGV("Entering verifyClassObject(obj=%p)", obj);
+    if (obj == gDvm.unlinkedJavaLangClass) {
+        assert(obj->obj.clazz == NULL);
+        goto exit;
+    }
+    VERIFY_REFERENCE(obj->obj.clazz);
+    assert(!strcmp(obj->obj.clazz->descriptor, "Ljava/lang/Class;"));
+    if (IS_CLASS_FLAG_SET(obj, CLASS_ISARRAY)) {
+        VERIFY_REFERENCE(obj->elementClass);
+    }
+    VERIFY_REFERENCE(obj->super);
+    VERIFY_REFERENCE(obj->classLoader);
+    /* Verify static field references. */
+    for (i = 0; i < obj->sfieldCount; ++i) {
+        ch = obj->sfields[i].field.signature[0];
+        if (ch == '[' || ch == 'L') {
+            VERIFY_REFERENCE(obj->sfields[i].value.l);
+        }
+    }
+    /* Verify interface references. */
+    for (i = 0; i < obj->interfaceCount; ++i) {
+        VERIFY_REFERENCE(obj->interfaces[i]);
+    }
+exit:
+    LOGV("Exiting verifyClassObject(obj=%p)", obj);
+}
+
+/*
+ * Verifies the header of all array objects.  If the array object is
+ * specialized to a reference type, verifies the array data as well.
+ */
+static void verifyArrayObject(const ArrayObject *array)
+{
+    ClassObject *clazz;
+    Object **contents;
+    size_t i;
+
+    LOGV("Entering verifyArrayObject(obj=%p)", obj);
+    /* Verify the class object reference. */
+    assert(array->obj.clazz != NULL);
+    VERIFY_REFERENCE(array->obj.clazz);
+    if (IS_CLASS_FLAG_SET(array->obj.clazz, CLASS_ISOBJECTARRAY)) {
+        /* Verify the array contents. */
+        contents = (Object **) array->contents;
+        for (i = 0; i < array->length; ++i) {
+            VERIFY_REFERENCE(contents[i]);
+        }
+    }
+    LOGV("Exiting verifyArrayObject(obj=%p)", obj);
+}
+
+/*
+ * Verifies the header and field references of a data object.
+ */
+static void verifyDataObject(const DataObject *obj)
+{
+    ClassObject *clazz;
+    InstField *field;
+    void *addr;
+    size_t offset;
+    int i, count;
+
+    LOGV("Entering verifyDataObject(obj=%p)", obj);
+    /* Verify the class object. */
+    assert(obj->obj.clazz != NULL);
+    VERIFY_REFERENCE(obj->obj.clazz);
+    /* Verify the instance fields. */
+    for (clazz = obj->obj.clazz; clazz != NULL; clazz = clazz->super) {
+        field = clazz->ifields;
+        count = clazz->ifieldRefCount;
+        for (i = 0; i < count; ++i, ++field) {
+            addr = BYTE_OFFSET((Object *)obj, field->byteOffset);
+            VERIFY_REFERENCE(((JValue *)addr)->l);
+        }
+    }
+    LOGV("Exiting verifyDataObject(obj=%p) %zx", obj, length);
+}
+
+/*
+ * Verifies an object reference.  Determines the type of the reference
+ * and dispatches to a specialized verification routine.
+ */
+void dvmVerifyObject(const Object *obj)
+{
+    ClassObject *clazz;
+
+    LOGV("Entering dvmVerifyObject(obj=%p)", obj);
+    assert(obj != NULL);
+    clazz = obj->clazz;
+    if (clazz == gDvm.classJavaLangClass ||
+        obj == (Object *)gDvm.unlinkedJavaLangClass) {
+        verifyClassObject((ClassObject *)obj);
+    } else {
+        assert(clazz != NULL);
+        if (IS_CLASS_FLAG_SET(clazz, CLASS_ISARRAY)) {
+            verifyArrayObject((ArrayObject *)obj);
+        } else {
+            verifyDataObject((DataObject *)obj);
+        }
+    }
+    LOGV("Exiting dvmVerifyObject(obj=%p)", obj);
+}
+
+/*
+ * Helper function to call dvmVerifyObject from a bitmap walker.
+ */
+static bool verifyBitmapCallback(size_t numPtrs, void **ptrs,
+                                 const void *finger, void *arg)
+{
+    size_t i;
+
+    for (i = 0; i < numPtrs; i++) {
+        dvmVerifyObject(*ptrs++);
+    }
+    return true;
+}
+
+/*
+ * Verifies the object references in a heap bitmap.  Assumes the heap
+ * is locked.
+ */
+void dvmVerifyBitmapUnlocked(const HeapBitmap *bitmap)
+{
+    /* TODO: check that locks are held and the VM is suspended. */
+    dvmHeapBitmapWalk(bitmap, verifyBitmapCallback, NULL);
+}
+
+/*
+ * Verifies the object references in a heap bitmap.  Suspends the VM
+ * for the duration of verification.
+ */
+void dvmVerifyBitmap(const HeapBitmap *bitmap)
+{
+    /* Suspend the VM. */
+    dvmSuspendAllThreads(SUSPEND_FOR_VERIFY);
+    dvmLockMutex(&gDvm.heapWorkerLock);
+    dvmAssertHeapWorkerThreadRunning();
+    dvmLockMutex(&gDvm.heapWorkerListLock);
+
+    dvmVerifyBitmapUnlocked(bitmap);
+
+    /* Resume the VM. */
+    dvmUnlockMutex(&gDvm.heapWorkerListLock);
+    dvmUnlockMutex(&gDvm.heapWorkerLock);
+    dvmResumeAllThreads(SUSPEND_FOR_VERIFY);
+}
diff --git a/vm/alloc/Verify.h b/vm/alloc/Verify.h
new file mode 100644
index 0000000..2409ad1
--- /dev/null
+++ b/vm/alloc/Verify.h
@@ -0,0 +1,37 @@
+/*
+ * Copyright (C) 2010 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef _DALVIK_ALLOC_VERIFY
+#define _DALVIK_ALLOC_VERIFY
+
+/*
+ * Verifies an object reference.
+ */
+void dvmVerifyObject(const Object *obj);
+
+/*
+ * Verifies the object references in a heap bitmap.  Assumes the heap
+ * is locked.
+ */
+void dvmVerifyBitmapUnlocked(const HeapBitmap *bitmap);
+
+/*
+ * Verifies the object references in a heap bitmap.  Suspends the VM
+ * for the duration of verification.
+ */
+void dvmVerifyBitmap(const HeapBitmap *bitmap);
+
+#endif /* _DALVIK_ALLOC_VERIFY */
diff --git a/vm/oo/Array.c b/vm/oo/Array.c
index 7edb823..c76ea53 100644
--- a/vm/oo/Array.c
+++ b/vm/oo/Array.c
@@ -761,6 +761,40 @@
     return true;
 }
 
+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. */
+}
+
+size_t dvmArrayObjectLength(const ArrayObject *array)
+{
+    size_t length;
+
+    length = offsetof(ArrayObject, contents);
+    length += array->length * arrayElementWidth(array);
+    return length;
+}
+
 /*
  * Add all primitive classes to the root set of objects.
 TODO: do these belong to the root class loader?
diff --git a/vm/oo/Array.h b/vm/oo/Array.h
index 161b1c6..17bdb22 100644
--- a/vm/oo/Array.h
+++ b/vm/oo/Array.h
@@ -152,4 +152,6 @@
 bool dvmUnboxObjectArray(ArrayObject* dstArray, const ArrayObject* srcArray,
     ClassObject* dstElemClass);
 
+size_t dvmArrayObjectLength(const ArrayObject *array);
+
 #endif /*_DALVIK_OO_ARRAY*/