Implement card table verification.

Card table verification occurs just before scanning the card table
during a concurrent GC.  Each object in the bitmap is visited and the
number of white (unmarked) references are counted.  If an object has
unmarked objects it is by definition gray and must reside on a dirty
card.  If the object is not on a dirty card, the verification routine
aborts the VM.

Because the processing of weak roots and references has yet to occur,
reachable reference objects with unmarked referents and weak interned
strings may still be gray.  These objects are checked during the card
table scan and ignored if their card is not dirty.

Change-Id: I64d145aa4719fb52eb9e3bb91efaf4dcfacd6e0c
diff --git a/vm/Intern.c b/vm/Intern.c
index 15bf8ab..bb8fb18 100644
--- a/vm/Intern.c
+++ b/vm/Intern.c
@@ -98,6 +98,27 @@
     return lookupInternedString(strObj, true);
 }
 
+/*
+ * Returns true if the object is a weak interned string.  Any string
+ * interned by the user is weak.
+ */
+bool dvmIsWeakInternedString(const StringObject* strObj)
+{
+    StringObject* found;
+    u4 hash;
+
+    assert(strObj != NULL);
+    if (gDvm.internedStrings == NULL) {
+        return false;
+    }
+    dvmLockMutex(&gDvm.internLock);
+    hash = dvmComputeStringHash(strObj);
+    found = dvmHashTableLookup(gDvm.internedStrings, hash, (void*)strObj,
+                               dvmHashcmpStrings, false);
+    dvmUnlockMutex(&gDvm.internLock);
+    return found == strObj;
+}
+
 static int markStringObject(void* strObj, void* arg)
 {
     UNUSED_PARAMETER(arg);
diff --git a/vm/Intern.h b/vm/Intern.h
index 6b713fb..a378fa5 100644
--- a/vm/Intern.h
+++ b/vm/Intern.h
@@ -21,8 +21,8 @@
 
 bool dvmStringInternStartup(void);
 void dvmStringInternShutdown(void);
-
 StringObject* dvmLookupInternedString(StringObject* strObj);
 StringObject* dvmLookupImmortalInternedString(StringObject* strObj);
+bool dvmIsWeakInternedString(const StringObject* strObj);
 
 #endif /*_DALVIK_INTERN*/
diff --git a/vm/alloc/CardTable.c b/vm/alloc/CardTable.c
index bd8de9a..787bd06 100644
--- a/vm/alloc/CardTable.c
+++ b/vm/alloc/CardTable.c
@@ -14,10 +14,7 @@
  * limitations under the License.
  */
 
-/*
- * Needed for PROT_* definitions.
- */
-#include <sys/mman.h>
+#include <sys/mman.h>  /* for PROT_* */
 
 #include "Dalvik.h"
 #include "alloc/HeapSource.h"
@@ -140,3 +137,143 @@
     u1 *cardAddr = dvmCardFromAddr(addr);
     *cardAddr = GC_CARD_DIRTY;
 }
+
+/*
+ * Handles the complexity of object arrays for isObjectDirty.  Array
+ * objects are exactly marked so all spanned cards are examined.
+ */
+static bool isObjectArrayDirty(const Object *obj)
+{
+    u1 *ptr, *limit;
+    size_t size;
+
+    assert(obj != NULL);
+    assert(dvmIsValidObject(obj));
+    assert(IS_CLASS_FLAG_SET(obj->clazz, CLASS_ISOBJECTARRAY));
+    size = dvmArrayObjectSize((const ArrayObject *)obj);
+    ptr = dvmCardFromAddr(obj);
+    limit = dvmCardFromAddr((u1 *)obj + size - 1) + 1;
+    assert(ptr != limit);
+    for (; ptr != limit; ++ptr) {
+        if (*ptr == GC_CARD_DIRTY) {
+            return true;
+        }
+    }
+    return false;
+}
+
+/*
+ * Returns true if the object is on a dirty card.
+ */
+static bool isObjectDirty(const Object *obj)
+{
+    assert(obj != NULL);
+    assert(dvmIsValidObject(obj));
+    if (IS_CLASS_FLAG_SET(obj->clazz, CLASS_ISOBJECTARRAY)) {
+        return isObjectArrayDirty(obj);
+   } else {
+        u1 *card = dvmCardFromAddr(obj);
+        return *card == GC_CARD_DIRTY;
+    }
+}
+
+/*
+ * Context structure for verifying the card table.
+ */
+typedef struct {
+    HeapBitmap *markBits;
+    size_t whiteRefs;
+} WhiteReferenceCounter;
+
+/*
+ * Visitor that counts white referents.
+ */
+static void countWhiteReferenceVisitor(void *addr, void *arg)
+{
+    WhiteReferenceCounter *ctx;
+    Object *obj;
+
+    assert(addr != NULL);
+    assert(arg != NULL);
+    obj = *(Object **)addr;
+    assert(dvmIsValidObject(obj));
+    ctx = arg;
+    if (obj == NULL || dvmHeapBitmapIsObjectBitSet(ctx->markBits, obj)) {
+        return;
+    }
+    ctx->whiteRefs += 1;
+}
+
+/*
+ * Returns true if the given object is a reference object and the
+ * just the referent is unmarked.
+ */
+static bool isReferentUnmarked(const Object *obj,
+                               const WhiteReferenceCounter* ctx)
+{
+    assert(obj != NULL);
+    assert(obj->clazz != NULL);
+    assert(ctx != NULL);
+    if (ctx->whiteRefs != 1) {
+        return false;
+    } else if (IS_CLASS_FLAG_SET(obj->clazz, CLASS_ISREFERENCE)) {
+        size_t offset = gDvm.offJavaLangRefReference_referent;
+        const Object *referent = dvmGetFieldObject(obj, offset);
+        return !dvmHeapBitmapIsObjectBitSet(ctx->markBits, referent);
+    } else {
+        return false;
+    }
+}
+
+/*
+ * Returns true if the given object is a string and has been interned
+ * by the user.
+ */
+static bool isWeakInternedString(const Object *obj)
+{
+    assert(obj != NULL);
+    if (obj->clazz == gDvm.classJavaLangString) {
+        return dvmIsWeakInternedString((StringObject *)obj);
+    } else {
+        return false;
+    }
+}
+
+/*
+ * Callback applied to marked objects.  If the object is found to be
+ * gray a message is written to the log.  By virtue of where the card
+ * table verification occurs weak references have yet to be blackened
+ * and so their containing objects are permitted to be gray.
+ */
+static void verifyCardTableCallback(size_t numPtrs, void **ptrs,
+                                    const void *finger, void *arg)
+{
+    size_t i;
+
+    for (i = 0; i < numPtrs; ++i) {
+        Object *obj = ptrs[i];
+        WhiteReferenceCounter ctx = { arg, 0 };
+        dvmVisitObject(countWhiteReferenceVisitor, obj, &ctx);
+        if (ctx.whiteRefs == 0) {
+            continue;
+        } else if (isObjectDirty(obj)) {
+            continue;
+        } else if (isReferentUnmarked(obj, &ctx)) {
+            continue;
+        } else if (isWeakInternedString(obj)) {
+            continue;
+        }
+        LOGE("Verify failed, object %p is gray", obj);
+        dvmDumpObject(obj);
+        dvmAbort();
+    }
+}
+
+/*
+ * Verifies that gray objects are on a dirty card.
+ */
+void dvmVerifyCardTable(void)
+{
+    HeapBitmap *markBits = gDvm.gcHeap->markContext.bitmap;
+    dvmHeapBitmapWalk(markBits, verifyCardTableCallback, markBits);
+}
diff --git a/vm/alloc/CardTable.h b/vm/alloc/CardTable.h
index 847963d..1a6db11 100644
--- a/vm/alloc/CardTable.h
+++ b/vm/alloc/CardTable.h
@@ -61,9 +61,7 @@
 void dvmMarkCard(const void *addr);
 
 /*
- * dvmAbort if any clean object in the Zygote heap contains a
- * reference to the application heap, or if the immune limit is not as
- * expected.
+ * Verifies that all gray objects are on a dirty card.
  */
 void dvmVerifyCardTable(void);
 
diff --git a/vm/alloc/Heap.c b/vm/alloc/Heap.c
index 1c9ca87..8f5189b 100644
--- a/vm/alloc/Heap.c
+++ b/vm/alloc/Heap.c
@@ -774,6 +774,13 @@
          */
         dvmHeapReMarkRootSet();
         /*
+         * With the exception of reference objects and weak interned
+         * strings, all gray objects should now be on dirty cards.
+         */
+        if (gDvm.verifyCardTable) {
+            dvmVerifyCardTable();
+        }
+        /*
          * Recursively mark gray objects pointed to by the roots or by
          * heap objects dirtied during the concurrent mark.
          */