Add a bit-map encoding of Object-reference field offsets to ClassObject.

Class.c populates a new field with a bit for each of the first 32 instance
fields, to show if it is a reference or not, and an escape value if there is a
reference field beyond 32.

The GC uses the encoded bitmap -- if available -- to extract Object refererences
from DataObjects.

diff --git a/vm/alloc/MarkSweep.c b/vm/alloc/MarkSweep.c
index 556763e..9bfae91 100644 (file)
--- a/vm/alloc/MarkSweep.c
+++ b/vm/alloc/MarkSweep.c
@@ -15,6 +15,7 @@
  */
 
 #include "Dalvik.h"
+#include "alloc/clz.h"
 #include "alloc/HeapBitmap.h"
 #include "alloc/HeapInternal.h"
 #include "alloc/HeapSource.h"
@@ -430,30 +431,39 @@ static void scanStaticFields(const ClassObject *clazz, GcMarkContext *ctx)
 static void scanInstanceFields(const DataObject *obj, ClassObject *clazz,
         GcMarkContext *ctx)
 {
-//TODO: Optimize this by avoiding walking the superclass chain
-    while (clazz != NULL) {
-        InstField *f;
-        int i;
+    if (clazz->refOffsets != CLASS_WALK_SUPER) {
+        unsigned int refOffsets = clazz->refOffsets;
+        while (refOffsets != 0) {
+            const int rshift = CLZ(refOffsets);
+            refOffsets &= ~(CLASS_HIGH_BIT >> rshift);
+            markObject(dvmGetFieldObject((Object*)obj,
+                                         CLASS_OFFSET_FROM_CLZ(rshift)), ctx);
+        }
+    } else {
+        while (clazz != NULL) {
+            InstField *f;
+            int i;
 
-        /* All of the fields that contain object references
-         * are guaranteed to be at the beginning of the ifields list.
-         */
-        f = clazz->ifields;
-        for (i = 0; i < clazz->ifieldRefCount; i++) {
-            /* Mark the array or object reference.
-             * May be NULL.
-             *
-             * Note that, per the comment on struct InstField,
-             * f->byteOffset is the offset from the beginning of
-             * obj, not the offset into obj->instanceData.
+            /* All of the fields that contain object references
+             * are guaranteed to be at the beginning of the ifields list.
              */
-            markObject(dvmGetFieldObject((Object*)obj, f->byteOffset), ctx);
-            f++;
-        }
+            f = clazz->ifields;
+            for (i = 0; i < clazz->ifieldRefCount; i++) {
+                /* Mark the array or object reference.
+                 * May be NULL.
+                 *
+                 * Note that, per the comment on struct InstField,
+                 * f->byteOffset is the offset from the beginning of
+                 * obj, not the offset into obj->instanceData.
+                 */
+                markObject(dvmGetFieldObject((Object*)obj, f->byteOffset), ctx);
+                f++;
+            }
 
-        /* This will be NULL when we hit java.lang.Object
-         */
-        clazz = clazz->super;
+            /* This will be NULL when we hit java.lang.Object
+             */
+            clazz = clazz->super;
+        }
     }
 }
 

diff --git a/vm/oo/Class.c b/vm/oo/Class.c
index 47e2a87..b42d860 100644 (file)
--- a/vm/oo/Class.c
+++ b/vm/oo/Class.c
@@ -4238,6 +4238,44 @@ noverify:
         dvmCallMethod(self, method, NULL, &unused);
     }
 
+    /* Set the bitmap of reference offsets. Except for class Object,
+     * start with the superclass offsets.
+     */
+    if (clazz->super != NULL) {
+        clazz->refOffsets = clazz->super->refOffsets;
+    } else {
+        clazz->refOffsets = 0;
+    }
+    /*
+     * If our superclass overflowed, we don't stand a chance.
+     */
+    if (clazz->refOffsets != CLASS_WALK_SUPER) {
+        InstField *f;
+        int i;
+
+        /* All of the fields that contain object references
+         * are guaranteed to be at the beginning of the ifields list.
+         */
+        f = clazz->ifields;
+        for (i = 0; i < clazz->ifieldRefCount; i++) {
+            /*
+             * Note that, per the comment on struct InstField,
+             * f->byteOffset is the offset from the beginning of
+             * obj, not the offset into obj->instanceData.
+             */
+            assert(f->byteOffset >= CLASS_SMALLEST_OFFSET);
+            assert((f->btyeOffset & (CLASS_OFFSET_ALIGNMENT - 1)) == 0);
+            u4 newBit = CLASS_BIT_FROM_OFFSET(f->byteOffset);
+            if (newBit != 0) {
+                clazz->refOffsets |= newBit;
+            } else {
+                clazz->refOffsets = CLASS_WALK_SUPER;
+                break;
+            }
+            f++;
+        }
+    }
+
     if (dvmCheckException(self)) {
         /*
          * We've had an exception thrown during static initialization.  We

diff --git a/vm/oo/Object.h b/vm/oo/Object.h
index 18fbb36..8c2f251 100644 (file)
--- a/vm/oo/Object.h
+++ b/vm/oo/Object.h
@@ -134,6 +134,33 @@ typedef enum PrimitiveType {
 #define PRIM_TYPE_TO_LETTER "ZCFDBSIJV"     /* must match order in enum */
 
 /*
+ * Definitions for packing refOffsets in ClassObject.
+ */
+/*
+ * A magic value for refOffsets. Ignore the bits and walk the super
+ * chain when this is the value.
+ * [This is an unlikely "natural" value, since it would be 30 non-ref instance
+ * fields followed by 2 ref instance fields.]
+ */
+#define CLASS_WALK_SUPER ((unsigned int)(3))
+#define CLASS_SMALLEST_OFFSET (sizeof(struct Object))
+#define CLASS_BITS_PER_WORD (sizeof(unsigned long int) * 8)
+#define CLASS_OFFSET_ALIGNMENT 4
+#define CLASS_HIGH_BIT ((unsigned int)1 << (CLASS_BITS_PER_WORD - 1))
+/*
+ * Return a single bit, or zero if the encoding can't encode the offset.
+ */
+#define CLASS_BIT_FROM_OFFSET(byteOffset) \
+    (CLASS_HIGH_BIT >> \
+      (((unsigned int)(byteOffset) - CLASS_SMALLEST_OFFSET) / \
+       CLASS_OFFSET_ALIGNMENT))
+/*
+ * Return an offset, given a bit number as returned from CLZ.
+ */
+#define CLASS_OFFSET_FROM_CLZ(rshift) \
+    (((int)(rshift) * CLASS_OFFSET_ALIGNMENT) + CLASS_SMALLEST_OFFSET)
+
+/*
  * This defines the amount of space we leave for field slots in the
  * java.lang.Class definition.  If we alter the class to have more than
  * this many fields, the VM will abort at startup.
@@ -400,6 +427,9 @@ struct ClassObject {
     int             ifieldRefCount; // number of fields that are object refs
     InstField*      ifields;
 
+    /* bitmap of offsets of ifields */
+    u4 refOffsets;
+
     /* source file name, if known */
     const char*     sourceFile;
 };