Indirect reference table implementation.

This change introduces the "indirect" reference table, which will be
replacing ReferenceTable for local and global JNI references.  The key
difference is that, instead of handing raw Object pointers to JNI, we
will be giving them a magic value that can be converted back to an
Object.  The goal is to avoid having to pin every object that native
code is aware of.

The code is not actually used anywhere yet.

Also bundled up here:
 - added detail to a log message
 - fixed a string format issue in the internal assert() definition
 - very minor optimization in "remove" function in ReferenceTable
 - quiet a gcc complaint
 - only include the hash table regression test in builds that invoke it

3 files changed, 490 insertions, 0 deletions

diff --git a/vm/test/Test.h b/vm/test/Test.h
index ce47aae07..f17526fcd 100644
--- a/vm/test/Test.h
+++ b/vm/test/Test.h
@@ -22,5 +22,6 @@
 
 bool dvmTestHash(void);
 bool dvmTestAtomicSpeed(void);
+bool dvmTestIndirectRefTable(void);
 
 #endif /*_DALVIK_TEST_TEST*/
diff --git a/vm/test/TestHash.c b/vm/test/TestHash.c
index 42fe014d9..7233b15e1 100644
--- a/vm/test/TestHash.c
+++ b/vm/test/TestHash.c
@@ -13,6 +13,7 @@
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
+
 /*
  * Test the hash table functions.
  */
@@ -20,6 +21,8 @@
 
 #include <stdlib.h>
 
+#ifndef NDEBUG
+
 #define kNumTestEntries 14
 
 /*
@@ -185,3 +188,4 @@ bool dvmTestHash(void)
     return true;
 }
 
+#endif /*NDEBUG*/
diff --git a/vm/test/TestIndirectRefTable.c b/vm/test/TestIndirectRefTable.c
new file mode 100644
index 000000000..72f8f33b2
--- /dev/null
+++ b/vm/test/TestIndirectRefTable.c
@@ -0,0 +1,485 @@
+/*
+ * Copyright (C) 2009 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.
+ */
+
+/*
+ * Test the indirect reference table implementation.
+ */
+#include "Dalvik.h"
+
+#include <stdlib.h>
+
+#ifndef NDEBUG
+
+#define DBUG_MSG    LOGV
+
+/*
+ * Basic add/get/delete tests in an unsegmented table.
+ */
+static bool basicTest(void)
+{
+    static const int kTableMax = 20;
+    IndirectRefTable irt;
+    IndirectRef iref0, iref1, iref2, iref3;
+    IndirectRef manyRefs[kTableMax];
+    ClassObject* clazz = dvmFindClass("Ljava/lang/Object;", NULL);
+    Object* obj0 = dvmAllocObject(clazz, ALLOC_DONT_TRACK);
+    Object* obj1 = dvmAllocObject(clazz, ALLOC_DONT_TRACK);
+    Object* obj2 = dvmAllocObject(clazz, ALLOC_DONT_TRACK);
+    Object* obj3 = dvmAllocObject(clazz, ALLOC_DONT_TRACK);
+    const u4 cookie = IRT_SEGMENT_INIT;
+    bool result = false;
+
+    if (!dvmInitIndirectRefTable(&irt, kTableMax/2, kTableMax,
+            kIndirectKindGlobal))
+    {
+        return false;
+    }
+
+    iref0 = (IndirectRef) 0x11110;
+    if (dvmRemoveFromIndirectRefTable(&irt, cookie, iref0)) {
+        LOGE("unexpectedly successful removal\n");
+        goto bail;
+    }
+
+    /*
+     * Add three, check, remove in the order in which they were added.
+     */
+    DBUG_MSG("+++ START fifo\n");
+    iref0 = dvmAddToIndirectRefTable(&irt, cookie, obj0);
+    iref1 = dvmAddToIndirectRefTable(&irt, cookie, obj1);
+    iref2 = dvmAddToIndirectRefTable(&irt, cookie, obj2);
+    if (iref0 == NULL || iref1 == NULL || iref2 == NULL) {
+        LOGE("trivial add1 failed\n");
+        goto bail;
+    }
+
+    if (dvmGetFromIndirectRefTable(&irt, iref0) != obj0 ||
+        dvmGetFromIndirectRefTable(&irt, iref1) != obj1 ||
+        dvmGetFromIndirectRefTable(&irt, iref2) != obj2)
+    {
+        LOGE("objects don't match expected values %p %p %p vs. %p %p %p\n",
+            dvmGetFromIndirectRefTable(&irt, iref0),
+            dvmGetFromIndirectRefTable(&irt, iref1),
+            dvmGetFromIndirectRefTable(&irt, iref2),
+            obj0, obj1, obj2);
+        goto bail;
+    } else {
+        DBUG_MSG("+++ obj1=%p --> iref1=%p\n", obj1, iref1);
+    }
+
+    if (!dvmRemoveFromIndirectRefTable(&irt, cookie, iref0) ||
+        !dvmRemoveFromIndirectRefTable(&irt, cookie, iref1) ||
+        !dvmRemoveFromIndirectRefTable(&irt, cookie, iref2))
+    {
+        LOGE("fifo deletion failed\n");
+        goto bail;
+    }
+
+    /* table should be empty now */
+    if (dvmIndirectRefTableEntries(&irt) != 0) {
+        LOGE("fifo del not empty\n");
+        goto bail;
+    }
+
+    /* get invalid entry (off the end of the list) */
+    if (dvmGetFromIndirectRefTable(&irt, iref0) != NULL) {
+        LOGE("stale entry get succeeded unexpectedly\n");
+        goto bail;
+    }
+
+    /*
+     * Add three, remove in the opposite order.
+     */
+    DBUG_MSG("+++ START lifo\n");
+    iref0 = dvmAddToIndirectRefTable(&irt, cookie, obj0);
+    iref1 = dvmAddToIndirectRefTable(&irt, cookie, obj1);
+    iref2 = dvmAddToIndirectRefTable(&irt, cookie, obj2);
+    if (iref0 == NULL || iref1 == NULL || iref2 == NULL) {
+        LOGE("trivial add2 failed\n");
+        goto bail;
+    }
+
+    if (!dvmRemoveFromIndirectRefTable(&irt, cookie, iref2) ||
+        !dvmRemoveFromIndirectRefTable(&irt, cookie, iref1) ||
+        !dvmRemoveFromIndirectRefTable(&irt, cookie, iref0))
+    {
+        LOGE("lifo deletion failed\n");
+        goto bail;
+    }
+
+    /* table should be empty now */
+    if (dvmIndirectRefTableEntries(&irt) != 0) {
+        LOGE("lifo del not empty\n");
+        goto bail;
+    }
+
+    /*
+     * Add three, remove middle / middle / bottom / top.  (Second attempt
+     * to remove middle should fail.)
+     */
+    DBUG_MSG("+++ START unorder\n");
+    iref0 = dvmAddToIndirectRefTable(&irt, cookie, obj0);
+    iref1 = dvmAddToIndirectRefTable(&irt, cookie, obj1);
+    iref2 = dvmAddToIndirectRefTable(&irt, cookie, obj2);
+    if (iref0 == NULL || iref1 == NULL || iref2 == NULL) {
+        LOGE("trivial add3 failed\n");
+        goto bail;
+    }
+
+    if (dvmIndirectRefTableEntries(&irt) != 3) {
+        LOGE("expected 3 entries, found %d\n",
+            dvmIndirectRefTableEntries(&irt));
+        goto bail;
+    }
+
+    if (!dvmRemoveFromIndirectRefTable(&irt, cookie, iref1) ||
+        dvmRemoveFromIndirectRefTable(&irt, cookie, iref1))
+    {
+        LOGE("unorder deletion1 failed\n");
+        goto bail;
+    }
+
+    /* get invalid entry (from hole) */
+    if (dvmGetFromIndirectRefTable(&irt, iref1) != NULL) {
+        LOGE("hole get succeeded unexpectedly\n");
+        goto bail;
+    }
+
+    if (!dvmRemoveFromIndirectRefTable(&irt, cookie, iref2) ||
+        !dvmRemoveFromIndirectRefTable(&irt, cookie, iref0))
+    {
+        LOGE("unorder deletion2 failed\n");
+        goto bail;
+    }
+
+    /* table should be empty now */
+    if (dvmIndirectRefTableEntries(&irt) != 0) {
+        LOGE("unorder del not empty\n");
+        goto bail;
+    }
+
+    /*
+     * Add four entries.  Remove #1, add new entry, verify that table size
+     * is still 4 (i.e. holes are getting filled).  Remove #1 and #3, verify
+     * that we delete one and don't hole-compact the other.
+     */
+    DBUG_MSG("+++ START hole fill\n");
+    iref0 = dvmAddToIndirectRefTable(&irt, cookie, obj0);
+    iref1 = dvmAddToIndirectRefTable(&irt, cookie, obj1);
+    iref2 = dvmAddToIndirectRefTable(&irt, cookie, obj2);
+    iref3 = dvmAddToIndirectRefTable(&irt, cookie, obj3);
+    if (iref0 == NULL || iref1 == NULL || iref2 == NULL || iref3 == NULL) {
+        LOGE("trivial add4 failed\n");
+        goto bail;
+    }
+    if (!dvmRemoveFromIndirectRefTable(&irt, cookie, iref1)) {
+        LOGE("remove 1 of 4 failed\n");
+        goto bail;
+    }
+    iref1 = dvmAddToIndirectRefTable(&irt, cookie, obj1);
+    if (dvmIndirectRefTableEntries(&irt) != 4) {
+        LOGE("hole not filled\n");
+        goto bail;
+    }
+    if (!dvmRemoveFromIndirectRefTable(&irt, cookie, iref1) ||
+        !dvmRemoveFromIndirectRefTable(&irt, cookie, iref3))
+    {
+        LOGE("remove 1/3 failed\n");
+        goto bail;
+    }
+    if (dvmIndirectRefTableEntries(&irt) != 3) {
+        LOGE("should be 3 after two deletions\n");
+        goto bail;
+    }
+    if (!dvmRemoveFromIndirectRefTable(&irt, cookie, iref2) ||
+        !dvmRemoveFromIndirectRefTable(&irt, cookie, iref0))
+    {
+        LOGE("remove 2/0 failed\n");
+        goto bail;
+    }
+    if (dvmIndirectRefTableEntries(&irt) != 0) {
+        LOGE("not empty after split remove\n");
+        goto bail;
+    }
+
+    /*
+     * Add an entry, remove it, add a new entry, and try to use the original
+     * iref.  They have the same slot number but are for different objects.
+     * With the extended checks in place, this should fail.
+     */
+    DBUG_MSG("+++ START switched\n");
+    iref0 = dvmAddToIndirectRefTable(&irt, cookie, obj0);
+    dvmRemoveFromIndirectRefTable(&irt, cookie, iref0);
+    iref1 = dvmAddToIndirectRefTable(&irt, cookie, obj1);
+    if (dvmRemoveFromIndirectRefTable(&irt, cookie, iref0)) {
+        LOGE("mismatched del succeeded (%p vs %p)\n", iref0, iref1);
+        goto bail;
+    }
+    if (!dvmRemoveFromIndirectRefTable(&irt, cookie, iref1)) {
+        LOGE("switched del failed\n");
+        goto bail;
+    }
+    if (dvmIndirectRefTableEntries(&irt) != 0) {
+        LOGE("switching del not empty\n");
+        goto bail;
+    }
+
+    /*
+     * Same as above, but with the same object.  A more rigorous checker
+     * (e.g. with slot serialization) will catch this.
+     */
+    iref0 = dvmAddToIndirectRefTable(&irt, cookie, obj0);
+    dvmRemoveFromIndirectRefTable(&irt, cookie, iref0);
+    iref1 = dvmAddToIndirectRefTable(&irt, cookie, obj0);
+    if (iref0 != iref1) {
+        if (dvmRemoveFromIndirectRefTable(&irt, cookie, iref0)) {
+            LOGE("temporal del succeeded (%p vs %p)\n", iref0, iref1);
+            goto bail;
+        }
+    } else {
+        dvmRemoveFromIndirectRefTable(&irt, cookie, iref1);
+    }
+    if (dvmIndirectRefTableEntries(&irt) != 0) {
+        LOGE("temporal del not empty\n");
+        goto bail;
+    }
+
+    /*
+     * Test table overflow.
+     */
+    DBUG_MSG("+++ START overflow\n");
+    int i;
+    for (i = 0; i < kTableMax; i++) {
+        manyRefs[i] = dvmAddToIndirectRefTable(&irt, cookie, obj0);
+        if (manyRefs[i] == NULL) {
+            LOGE("Failed adding %d of %d\n", i, kTableMax);
+            goto bail;
+        }
+    }
+    if (dvmAddToIndirectRefTable(&irt, cookie, obj0) != NULL) {
+        LOGE("Table overflow succeeded\n");
+        goto bail;
+    }
+    if (dvmIndirectRefTableEntries(&irt) != (size_t)kTableMax) {
+        LOGE("Expected %d entries, found %d\n",
+            kTableMax, dvmIndirectRefTableEntries(&irt));
+        goto bail;
+    }
+    for (i = 0; i < kTableMax-1; i++) {
+        if (!dvmRemoveFromIndirectRefTable(&irt, cookie, manyRefs[i])) {
+            LOGE("multi-remove failed at %d\n", i);
+            goto bail;
+        }
+    }
+    /* because of removal order, should have 20 entries, 19 of them holes */
+    if (dvmIndirectRefTableEntries(&irt) != (size_t)kTableMax) {
+        LOGE("Expected %d entries (with holes), found %d\n",
+            kTableMax, dvmIndirectRefTableEntries(&irt));
+        goto bail;
+    }
+    if (!dvmRemoveFromIndirectRefTable(&irt, cookie, manyRefs[kTableMax-1])) {
+        LOGE("multi-remove final failed\n");
+        goto bail;
+    }
+    if (dvmIndirectRefTableEntries(&irt) != 0) {
+        LOGE("multi-del not empty\n");
+        goto bail;
+    }
+
+    DBUG_MSG("+++ basic test complete\n");
+    result = true;
+
+bail:
+    dvmClearIndirectRefTable(&irt);
+    return result;
+}
+
+/*
+ * Test operations on a segmented table.
+ */
+static bool segmentTest(void)
+{
+    static const int kTableMax = 20;
+    IndirectRefTable irt;
+    IndirectRef iref0, iref1, iref2, iref3;
+    ClassObject* clazz = dvmFindClass("Ljava/lang/Object;", NULL);
+    Object* obj0 = dvmAllocObject(clazz, ALLOC_DONT_TRACK);
+    Object* obj1 = dvmAllocObject(clazz, ALLOC_DONT_TRACK);
+    Object* obj2 = dvmAllocObject(clazz, ALLOC_DONT_TRACK);
+    Object* obj3 = dvmAllocObject(clazz, ALLOC_DONT_TRACK);
+    u4 cookie;
+    u4 segmentState[4];
+    bool result = false;
+
+    if (!dvmInitIndirectRefTable(&irt, kTableMax, kTableMax,
+            kIndirectKindLocal))
+    {
+        return false;
+    }
+    cookie = segmentState[0] = IRT_SEGMENT_INIT;
+    DBUG_MSG("+++ objs %p %p %p %p\n", obj0, obj1, obj2, obj3);
+
+    /*
+     * Push two, create new segment, push two more, try to get all four,
+     * try to delete all 4.  All four should be accessible, but only the
+     * last two should be deletable.
+     */
+    DBUG_MSG("+++ START basic segment\n");
+    iref0 = dvmAddToIndirectRefTable(&irt, cookie, obj0);
+    iref1 = dvmAddToIndirectRefTable(&irt, cookie, obj1);
+    cookie = segmentState[1] = dvmPushIndirectRefTableSegment(&irt);
+    DBUG_MSG("+++ pushed, cookie is 0x%08x\n", cookie);
+    iref2 = dvmAddToIndirectRefTable(&irt, cookie, obj2);
+    iref3 = dvmAddToIndirectRefTable(&irt, cookie, obj3);
+
+    if (dvmRemoveFromIndirectRefTable(&irt, cookie, iref0) ||
+        dvmRemoveFromIndirectRefTable(&irt, cookie, iref1))
+    {
+        LOGE("removed values from earlier segment\n");
+        goto bail;
+    }
+    if (!dvmRemoveFromIndirectRefTable(&irt, cookie, iref2) ||
+        !dvmRemoveFromIndirectRefTable(&irt, cookie, iref3))
+    {
+        LOGE("unable to remove values from current segment\n");
+        goto bail;
+    }
+    if (dvmIndirectRefTableEntries(&irt) != 2) {
+        LOGE("wrong total entries\n");
+        goto bail;
+    }
+    dvmPopIndirectRefTableSegment(&irt, segmentState[1]);
+    cookie = segmentState[0];
+    if (!dvmRemoveFromIndirectRefTable(&irt, cookie, iref0) ||
+        !dvmRemoveFromIndirectRefTable(&irt, cookie, iref1))
+    {
+        LOGE("unable to remove values from first segment\n");
+        goto bail;
+    }
+    if (dvmIndirectRefTableEntries(&irt) != 0) {
+        LOGE("basic push/pop not empty\n");
+        goto bail;
+    }
+
+    /*
+     * Push two, delete first, segment, push two more, pop segment, verify
+     * the last two are no longer present and hole count is right.  The
+     * adds after the segment pop should not be filling in the hole.
+     */
+    DBUG_MSG("+++ START segment pop\n");
+    iref0 = dvmAddToIndirectRefTable(&irt, cookie, obj0);
+    iref1 = dvmAddToIndirectRefTable(&irt, cookie, obj1);
+    dvmRemoveFromIndirectRefTable(&irt, cookie, iref0);
+    cookie = segmentState[1] = dvmPushIndirectRefTableSegment(&irt);
+    iref2 = dvmAddToIndirectRefTable(&irt, cookie, obj2);
+    iref3 = dvmAddToIndirectRefTable(&irt, cookie, obj3);
+    dvmPopIndirectRefTableSegment(&irt, segmentState[1]);
+    cookie = segmentState[0];
+    if (dvmIndirectRefTableEntries(&irt) != 2) {
+        LOGE("wrong total entries after pop\n");
+        goto bail;
+    }
+    dvmRemoveFromIndirectRefTable(&irt, cookie, iref1);
+    if (dvmIndirectRefTableEntries(&irt) != 0) {
+        LOGE("not back to zero after pop + del\n");
+        goto bail;
+    }
+
+    /*
+     * Multiple segments, some empty.
+     */
+    DBUG_MSG("+++ START multiseg\n");
+    iref0 = dvmAppendToIndirectRefTable(&irt, cookie, obj0);
+    iref1 = dvmAppendToIndirectRefTable(&irt, cookie, obj1);
+    cookie = segmentState[1] = dvmPushIndirectRefTableSegment(&irt);
+    cookie = segmentState[2] = dvmPushIndirectRefTableSegment(&irt);
+    iref3 = dvmAppendToIndirectRefTable(&irt, cookie, obj3);
+    iref2 = dvmAppendToIndirectRefTable(&irt, cookie, obj2);
+    dvmRemoveFromIndirectRefTable(&irt, cookie, iref3);
+    cookie = segmentState[3] = dvmPushIndirectRefTableSegment(&irt);
+    iref3 = dvmAppendToIndirectRefTable(&irt, cookie, obj3);
+
+    if (dvmGetFromIndirectRefTable(&irt, iref0) != obj0 ||
+        dvmGetFromIndirectRefTable(&irt, iref1) != obj1 ||
+        dvmGetFromIndirectRefTable(&irt, iref2) != obj2 ||
+        dvmGetFromIndirectRefTable(&irt, iref3) != obj3)
+    {
+        LOGE("Unable to retrieve all multiseg objects\n");
+        goto bail;
+    }
+
+    dvmDumpIndirectRefTable(&irt, "test");
+
+    //int i;
+    //for (i = 0; i < sizeof(segmentState) / sizeof(segmentState[0]); i++) {
+    //    DBUG_MSG("+++  segment %d = 0x%08x\n", i, segmentState[i]);
+    //}
+
+    dvmRemoveFromIndirectRefTable(&irt, cookie, iref3);
+    if (dvmRemoveFromIndirectRefTable(&irt, cookie, iref2)) {
+        LOGE("multiseg del2 worked\n");
+        goto bail;
+    }
+    dvmPopIndirectRefTableSegment(&irt, segmentState[3]);
+    cookie = segmentState[2];
+    if (!dvmRemoveFromIndirectRefTable(&irt, cookie, iref2)) {
+        LOGE("multiseg del2b failed (cookie=0x%08x ref=%p)\n", cookie, iref2);
+        goto bail;
+    }
+    iref2 = dvmAddToIndirectRefTable(&irt, cookie, obj2);
+
+    /* pop two off at once */
+    dvmPopIndirectRefTableSegment(&irt, segmentState[1]);
+    cookie = segmentState[0];
+
+    if (dvmIndirectRefTableEntries(&irt) != 2) {
+        LOGE("Unexpected entry count in multiseg\n");
+        goto bail;
+    }
+    dvmRemoveFromIndirectRefTable(&irt, cookie, iref0);
+    dvmRemoveFromIndirectRefTable(&irt, cookie, iref1);
+    if (dvmIndirectRefTableEntries(&irt) != 0) {
+        LOGE("Unexpected entry count at multiseg end\n");
+        goto bail;
+    }
+
+    DBUG_MSG("+++ segment test complete\n");
+    result = true;
+
+bail:
+    dvmClearIndirectRefTable(&irt);
+    return result;
+}
+
+
+/*
+ * Some quick tests.
+ */
+bool dvmTestIndirectRefTable(void)
+{
+    if (!basicTest()) {
+        LOGE("IRT basic test failed\n");
+        return false;
+    }
+    if (!segmentTest()) {
+        LOGE("IRT segment test failed\n");
+        return false;
+    }
+
+    return true;
+}
+
+#endif /*NDEBUG*/