Code drop from //branches/cupcake/...@124589
diff --git a/vm/analysis/CodeVerify.c b/vm/analysis/CodeVerify.c
index fd4c75b..b4fde5a 100644
--- a/vm/analysis/CodeVerify.c
+++ b/vm/analysis/CodeVerify.c
@@ -13,6 +13,7 @@
* See the License for the specific language governing permissions and
* limitations under the License.
*/
+
/*
* Dalvik bytecode structural verifier. The only public entry point
* (except for a few shared utility functions) is dvmVerifyCodeFlow().
@@ -184,6 +185,8 @@
/* fwd */
static void checkMergeTab(void);
static bool isInitMethod(const Method* meth);
+static void logUnableToResolveClass(const char* missingClassDescr,\
+ const Method* meth);
static RegType getInvocationThis(const RegType* insnRegs,\
const int insnRegCount, const DecodedInstruction* pDecInsn, bool* pOkay);
static void verifyRegisterType(const RegType* insnRegs, const int insnRegCount,\
@@ -360,6 +363,40 @@
}
/*
+ * Determine whether or not "srcType" and "checkType" have the same width.
+ * The idea is to determine whether or not it's okay to use a sub-integer
+ * instruction (say, sget-short) with a primitive field of a specific type.
+ *
+ * We should always be passed "definite" types here; pseudo-types like
+ * kRegTypeZero are not expected. We could get kRegTypeUnknown if a type
+ * lookup failed.
+ */
+static bool isTypeWidthEqual1nr(RegType type1, RegType type2)
+{
+ /* primitive sizes; we use zero for boolean so it's not equal to others */
+ static const char sizeTab[kRegType1nrEND-kRegType1nrSTART+1] = {
+ /* F 0 1 Z b B s S C I */
+ 4, 8, 9, 0, 1, 1, 2, 2, 2, 4
+ };
+
+ assert(type1 != kRegTypeZero && type1 != kRegTypeOne &&
+ type1 != kRegTypePosByte && type1 != kRegTypePosShort);
+ assert(type2 != kRegTypeZero && type2 != kRegTypeOne &&
+ type2 != kRegTypePosByte && type2 != kRegTypePosShort);
+
+ if (type1 == type2)
+ return true; /* quick positive; most common case */
+
+ /* might be able to eliminate one of these by narrowly defining our args? */
+ if (type1 < kRegType1nrSTART || type1 > kRegType1nrEND)
+ return false;
+ if (type2 < kRegType1nrSTART || type2 > kRegType1nrEND)
+ return false;
+
+ return sizeTab[type1-kRegType1nrSTART] == sizeTab[type2-kRegType1nrSTART];
+}
+
+/*
* Given a 32-bit constant, return the most-restricted RegType that can hold
* the value.
*/
@@ -599,6 +636,14 @@
}
/*
+ * Is this method a class initializer?
+ */
+static bool isClassInitMethod(const Method* meth)
+{
+ return (*meth->name == '<' && strcmp(meth->name+1, "clinit>") == 0);
+}
+
+/*
* Look up a class reference given as a simple string descriptor.
*/
static ClassObject* lookupClassByDescriptor(const Method* meth,
@@ -624,18 +669,18 @@
if (clazz == NULL) {
dvmClearOptException(dvmThreadSelf());
if (strchr(pDescriptor, '$') != NULL) {
- LOGV("VFY: unable to find class referenced in "
- "signature (%s)\n", pDescriptor);
+ LOGV("VFY: unable to find class referenced in signature (%s)\n",
+ pDescriptor);
} else {
- LOG_VFY("VFY: unable to find class referenced in "
- "signature (%s)\n", pDescriptor);
+ LOG_VFY("VFY: unable to find class referenced in signature (%s)\n",
+ pDescriptor);
}
if (pDescriptor[0] == '[') {
/* We are looking at an array descriptor. */
/*
- * There should never be a problem loading primitive arrays.
+ * There should never be a problem loading primitive arrays.
*/
if (pDescriptor[1] != 'L' && pDescriptor[1] != '[') {
LOG_VFY("VFY: invalid char in signature in '%s'\n",
@@ -775,6 +820,8 @@
expectedArgs = meth->insSize; /* long/double count as two */
actualArgs = 0;
+ assert(argStart >= 0); /* should have been verified earlier */
+
/*
* Include the "this" pointer.
*/
@@ -948,7 +995,7 @@
RegType type;
bool okay = true;
const char* descriptor = dexProtoGetReturnType(&meth->prototype);
-
+
switch (*descriptor) {
case 'I':
type = kRegTypeInteger;
@@ -1098,6 +1145,22 @@
methodDesc = dexCopyDescriptorFromMethodId(pDexFile, pMethodId);
classDescriptor = dexStringByTypeIdx(pDexFile, pMethodId->classIdx);
+ if (!gDvm.optimizing) {
+ char* dotMissingClass = dvmDescriptorToDot(classDescriptor);
+ char* dotMethClass = dvmDescriptorToDot(meth->clazz->descriptor);
+ //char* curMethodDesc =
+ // dexProtoCopyMethodDescriptor(&meth->prototype);
+
+ LOGE("Could not find method %s.%s, referenced from "
+ "method %s.%s\n",
+ dotMissingClass, methodName/*, methodDesc*/,
+ dotMethClass, meth->name/*, curMethodDesc*/);
+
+ free(dotMissingClass);
+ free(dotMethClass);
+ //free(curMethodDesc);
+ }
+
LOG_VFY("VFY: unable to resolve %s method %u: %s.%s %s\n",
dvmMethodTypeStr(methodType), pDecInsn->vB,
classDescriptor, methodName, methodDesc);
@@ -1629,7 +1692,7 @@
* See comments above findCommonSuperclass.
*/
/*
- if (srcClass != checkClass &&
+ if (srcClass != checkClass &&
!dvmImplements(srcClass, checkClass))
{
LOG_VFY("VFY: %s does not implement %s\n",
@@ -1887,7 +1950,7 @@
{
RegType type;
u4 vsrc;
-
+
vsrc = RESULT_REGISTER(insnRegCount);
type = getRegisterType(insnRegs, insnRegCount + kExtraRegs, vsrc, pOkay);
if (*pOkay)
@@ -1915,7 +1978,7 @@
{
RegType typel, typeh;
u4 vsrc;
-
+
vsrc = RESULT_REGISTER(insnRegCount);
typel = getRegisterType(insnRegs, insnRegCount + kExtraRegs, vsrc, pOkay);
typeh = getRegisterType(insnRegs, insnRegCount + kExtraRegs, vsrc+1, pOkay);
@@ -2350,10 +2413,12 @@
va_list ap;
int logLevel;
- if (gDvm.optimizing)
- return; /* logLevel = ANDROID_LOG_DEBUG; */
- else
+ if (gDvm.optimizing) {
+ return;
+ //logLevel = ANDROID_LOG_DEBUG;
+ } else {
logLevel = ANDROID_LOG_WARN;
+ }
va_start(ap, format);
LOG_PRI_VA(logLevel, LOG_TAG, format, ap);
@@ -2366,6 +2431,28 @@
}
/*
+ * Show a relatively human-readable message describing the failure to
+ * resolve a class.
+ */
+static void logUnableToResolveClass(const char* missingClassDescr,
+ const Method* meth)
+{
+ if (gDvm.optimizing)
+ return;
+
+ char* dotMissingClass = dvmDescriptorToDot(missingClassDescr);
+ char* dotFromClass = dvmDescriptorToDot(meth->clazz->descriptor);
+ //char* methodDescr = dexProtoCopyMethodDescriptor(&meth->prototype);
+
+ LOGE("Could not find class '%s', referenced from method %s.%s\n",
+ dotMissingClass, dotFromClass, meth->name/*, methodDescr*/);
+
+ free(dotMissingClass);
+ free(dotFromClass);
+ //free(methodDescr);
+}
+
+/*
* Extract the relative offset from a branch instruction.
*
* Returns "false" on failure (e.g. this isn't a branch instruction).
@@ -2518,6 +2605,64 @@
}
/*
+ * If "field" is marked "final", make sure this is the either <clinit>
+ * or <init> as appropriate.
+ *
+ * Sets "*pOkay" to false on failure.
+ */
+static void checkFinalFieldAccess(const Method* meth, const Field* field,
+ bool* pOkay)
+{
+ if (!dvmIsFinalField(field))
+ return;
+
+ /* make sure we're in the same class */
+ if (meth->clazz != field->clazz) {
+ LOG_VFY_METH(meth, "VFY: can't modify final field %s.%\n",
+ field->clazz->descriptor, field->name);
+ *pOkay = false;
+ return;
+ }
+
+ /* make sure we're in the right kind of constructor */
+ if (dvmIsStaticField(field)) {
+ if (!isClassInitMethod(meth)) {
+ LOG_VFY_METH(meth,
+ "VFY: can't modify final static field outside <clinit>\n");
+ *pOkay = false;
+ }
+ } else {
+ if (!isInitMethod(meth)) {
+ LOG_VFY_METH(meth,
+ "VFY: can't modify final field outside <init>\n");
+ *pOkay = false;
+ }
+ }
+}
+
+/*
+ * Make sure that the register type is suitable for use as an array index.
+ *
+ * Sets "*pOkay" to false if not.
+ */
+static void checkArrayIndexType(const Method* meth, RegType regType,
+ bool* pOkay)
+{
+ if (*pOkay) {
+ /*
+ * The 1nr types are interchangeable at this level. We could
+ * do something special if we can definitively identify it as a
+ * float, but there's no real value in doing so.
+ */
+ checkTypeCategory(regType, kTypeCategory1nr, pOkay);
+ if (!*pOkay) {
+ LOG_VFY_METH(meth, "Invalid reg type for array index (%d)\n",
+ regType);
+ }
+ }
+}
+
+/*
* Check constraints on constructor return. Specifically, make sure that
* the "this" argument got initialized.
*
@@ -2608,7 +2753,7 @@
if (handler == NULL) {
break;
}
-
+
if (handler->address == (u4) insnIdx) {
ClassObject* clazz;
@@ -2618,8 +2763,9 @@
clazz = dvmOptResolveClass(meth->clazz, handler->typeIdx);
if (clazz == NULL) {
- LOGD("VFY: unable to resolve exceptionIdx=%u\n",
- handler->typeIdx);
+ LOG_VFY("VFY: unable to resolve exception class %u (%s)\n",
+ handler->typeIdx,
+ dexStringByTypeIdx(pDexFile, handler->typeIdx));
} else {
if (commonSuper == NULL)
commonSuper = clazz;
@@ -3020,7 +3166,7 @@
meth->clazz->descriptor, meth->name, desc);
free(desc);
}
-
+
deadStart = -1;
}
}
@@ -3118,7 +3264,15 @@
switch (decInsn.opCode) {
case OP_NOP:
- /* no effect on anything */
+ /*
+ * A "pure" NOP has no effect on anything. Data tables start with
+ * a signature that looks like a NOP; if we see one of these in
+ * the course of executing code then we have a problem.
+ */
+ if (decInsn.vA != 0) {
+ LOG_VFY("VFY: encountered data table in instruction stream\n");
+ okay = false;
+ }
break;
case OP_MOVE:
@@ -3256,7 +3410,7 @@
* returned.
*/
ClassObject* declClass;
-
+
declClass = regTypeInitializedReferenceToClass(returnType);
resClass = getClassFromRegister(workRegs, insnRegCount,
decInsn.vA, &okay);
@@ -3298,23 +3452,13 @@
case OP_CONST_STRING:
case OP_CONST_STRING_JUMBO:
assert(gDvm.classJavaLangString != NULL);
- if (decInsn.vB >= pDexFile->pHeader->stringIdsSize) {
- LOG_VFY("VFY: invalid string pool index %u\n", decInsn.vB);
- okay = false;
- } else {
- setRegisterType(workRegs, insnRegCount, decInsn.vA,
- regTypeFromClass(gDvm.classJavaLangString), &okay);
- }
+ setRegisterType(workRegs, insnRegCount, decInsn.vA,
+ regTypeFromClass(gDvm.classJavaLangString), &okay);
break;
case OP_CONST_CLASS:
assert(gDvm.classJavaLangClass != NULL);
- if (decInsn.vB >= pDexFile->pHeader->typeIdsSize) {
- LOG_VFY("VFY: invalid class pool index %u\n", decInsn.vB);
- okay = false;
- } else {
- setRegisterType(workRegs, insnRegCount, decInsn.vA,
- regTypeFromClass(gDvm.classJavaLangClass), &okay);
- }
+ setRegisterType(workRegs, insnRegCount, decInsn.vA,
+ regTypeFromClass(gDvm.classJavaLangClass), &okay);
break;
case OP_MONITOR_ENTER:
@@ -3337,9 +3481,10 @@
*/
resClass = dvmOptResolveClass(meth->clazz, decInsn.vB);
if (resClass == NULL) {
+ const char* badClassDesc = dexStringByTypeIdx(pDexFile, decInsn.vB);
+ logUnableToResolveClass(badClassDesc, meth);
LOG_VFY("VFY: unable to resolve check-cast %d (%s) in %s\n",
- decInsn.vB, dexStringByTypeIdx(pDexFile, decInsn.vB),
- meth->clazz->descriptor);
+ decInsn.vB, badClassDesc, meth->clazz->descriptor);
okay = false;
} else {
RegType origType;
@@ -3358,11 +3503,6 @@
}
break;
case OP_INSTANCE_OF:
- if (decInsn.vC >= pDexFile->pHeader->typeIdsSize) {
- LOG_VFY("VFY: invalid class pool index %u\n", decInsn.vC);
- okay = false;
- break;
- }
tmpType = getRegisterType(workRegs, insnRegCount, decInsn.vB, &okay);
if (!okay)
break;
@@ -3399,9 +3539,10 @@
*/
resClass = dvmOptResolveClass(meth->clazz, decInsn.vB);
if (resClass == NULL) {
+ const char* badClassDesc = dexStringByTypeIdx(pDexFile, decInsn.vB);
+ logUnableToResolveClass(badClassDesc, meth);
LOG_VFY("VFY: unable to resolve new-instance %d (%s) in %s\n",
- decInsn.vB, dexStringByTypeIdx(pDexFile, decInsn.vB),
- meth->clazz->descriptor);
+ decInsn.vB, badClassDesc, meth->clazz->descriptor);
okay = false;
} else {
RegType uninitType;
@@ -3426,9 +3567,10 @@
case OP_NEW_ARRAY:
resClass = dvmOptResolveClass(meth->clazz, decInsn.vC);
if (resClass == NULL) {
+ const char* badClassDesc = dexStringByTypeIdx(pDexFile, decInsn.vB);
+ logUnableToResolveClass(badClassDesc, meth);
LOG_VFY("VFY: unable to resolve new-array %d (%s) in %s\n",
- decInsn.vC, dexStringByTypeIdx(pDexFile, decInsn.vB),
- meth->clazz->descriptor);
+ decInsn.vC, badClassDesc, meth->clazz->descriptor);
okay = false;
} else if (!dvmIsArrayClass(resClass)) {
LOG_VFY("VFY: new-array on non-array class\n");
@@ -3444,15 +3586,17 @@
/* (decInsn.vA == 0) is silly, but not illegal */
resClass = dvmOptResolveClass(meth->clazz, decInsn.vB);
if (resClass == NULL) {
+ const char* badClassDesc = dexStringByTypeIdx(pDexFile, decInsn.vB);
+ logUnableToResolveClass(badClassDesc, meth);
LOG_VFY("VFY: unable to resolve filled-array %d (%s) in %s\n",
- decInsn.vB, dexStringByTypeIdx(pDexFile, decInsn.vB),
- meth->clazz->descriptor);
+ decInsn.vB, badClassDesc, meth->clazz->descriptor);
okay = false;
} else if (!dvmIsArrayClass(resClass)) {
LOG_VFY("VFY: filled-new-array on non-array class\n");
okay = false;
} else {
/*
+ * TODO: verify decInsn.vA range
* TODO: if resClass is array of references, verify the registers
* in the argument list against the array type.
* TODO: if resClass is array of primitives, verify that the
@@ -3537,7 +3681,7 @@
resClass->elementClass->primitiveType == PRIM_NOT ||
resClass->elementClass->primitiveType == PRIM_VOID)
{
- LOG_VFY("VFY: invalid fill-array-data on %s\n",
+ LOG_VFY("VFY: invalid fill-array-data on %s\n",
resClass->descriptor);
okay = false;
break;
@@ -3547,17 +3691,17 @@
resClass->elementClass->primitiveType);
assert(valueType != kRegTypeUnknown);
- /*
+ /*
* Now verify if the element width in the table matches the element
* width declared in the array
*/
arrayData = insns + (insns[1] | (((s4)insns[2]) << 16));
if (arrayData[0] != kArrayDataSignature) {
- LOG_VFY("VFY: invalid magic for array-data\n");
+ LOG_VFY("VFY: invalid magic for array-data\n");
okay = false;
break;
}
-
+
switch (resClass->elementClass->primitiveType) {
case PRIM_BOOLEAN:
case PRIM_BYTE:
@@ -3580,14 +3724,14 @@
break;
}
- /*
+ /*
* Since we don't compress the data in Dex, expect to see equal
* width of data stored in the table and expected from the array
* class.
*/
if (arrayData[1] != elemWidth) {
- LOG_VFY("VFY: array-data size mismatch (%d vs %d)\n",
- arrayData[1], elemWidth);
+ LOG_VFY("VFY: array-data size mismatch (%d vs %d)\n",
+ arrayData[1], elemWidth);
okay = false;
}
}
@@ -3678,30 +3822,37 @@
goto aget_1nr_common;
aget_1nr_common:
{
- RegType srcType;
+ RegType srcType, indexType;
+
+ indexType = getRegisterType(workRegs, insnRegCount, decInsn.vC,
+ &okay);
+ checkArrayIndexType(meth, indexType, &okay);
+ if (!okay)
+ break;
resClass = getClassFromRegister(workRegs, insnRegCount,
decInsn.vB, &okay);
if (!okay)
break;
if (resClass != NULL) {
- /* verify the class and check "tmpType" */
+ /* verify the class */
if (!dvmIsArrayClass(resClass) || resClass->arrayDim != 1 ||
resClass->elementClass->primitiveType == PRIM_NOT)
{
- LOG_VFY("VFY: invalid aget-1nr on %s\n",
- resClass->descriptor);
+ LOG_VFY("VFY: invalid aget-1nr target %s\n",
+ resClass->descriptor);
okay = false;
break;
}
+ /* make sure array type matches instruction */
srcType = primitiveTypeToRegType(
resClass->elementClass->primitiveType);
- if (!canConvertTo1nr(srcType, tmpType)) {
- LOG_VFY("VFY: unable to aget array type=%d into local type=%d"
- " (on %s)\n",
- srcType, tmpType, resClass->descriptor);
+ if (!isTypeWidthEqual1nr(tmpType, srcType)) {
+ LOG_VFY("VFY: invalid aget-1nr, array type=%d with"
+ " inst type=%d (on %s)\n",
+ srcType, tmpType, resClass->descriptor);
okay = false;
break;
}
@@ -3714,23 +3865,30 @@
case OP_AGET_WIDE:
{
- RegType dstType = kRegTypeUnknown;
+ RegType dstType, indexType;
+
+ indexType = getRegisterType(workRegs, insnRegCount, decInsn.vC,
+ &okay);
+ checkArrayIndexType(meth, indexType, &okay);
+ if (!okay)
+ break;
resClass = getClassFromRegister(workRegs, insnRegCount,
decInsn.vB, &okay);
if (!okay)
break;
if (resClass != NULL) {
- /* verify the class and try to refine "dstType" */
+ /* verify the class */
if (!dvmIsArrayClass(resClass) || resClass->arrayDim != 1 ||
resClass->elementClass->primitiveType == PRIM_NOT)
{
- LOG_VFY("VFY: invalid aget-wide on %s\n",
- resClass->descriptor);
+ LOG_VFY("VFY: invalid aget-wide target %s\n",
+ resClass->descriptor);
okay = false;
break;
}
+ /* try to refine "dstType" */
switch (resClass->elementClass->primitiveType) {
case PRIM_LONG:
dstType = kRegTypeLongLo;
@@ -3740,11 +3898,19 @@
break;
default:
LOG_VFY("VFY: invalid aget-wide on %s\n",
- resClass->descriptor);
+ resClass->descriptor);
dstType = kRegTypeUnknown;
okay = false;
break;
}
+ } else {
+ /*
+ * Null array ref; this code path will fail at runtime. We
+ * know this is either long or double, and we don't really
+ * discriminate between those during verification, so we
+ * call it a long.
+ */
+ dstType = kRegTypeLongLo;
}
setRegisterType(workRegs, insnRegCount, decInsn.vA,
dstType, &okay);
@@ -3753,7 +3919,13 @@
case OP_AGET_OBJECT:
{
- RegType dstType;
+ RegType dstType, indexType;
+
+ indexType = getRegisterType(workRegs, insnRegCount, decInsn.vC,
+ &okay);
+ checkArrayIndexType(meth, indexType, &okay);
+ if (!okay)
+ break;
resClass = getClassFromRegister(workRegs, insnRegCount,
decInsn.vB, &okay);
@@ -3816,7 +3988,13 @@
goto aput_1nr_common;
aput_1nr_common:
{
- RegType srcType, dstType;
+ RegType srcType, dstType, indexType;
+
+ indexType = getRegisterType(workRegs, insnRegCount, decInsn.vC,
+ &okay);
+ checkArrayIndexType(meth, indexType, &okay);
+ if (!okay)
+ break;
/* make sure the source register has the correct type */
srcType = getRegisterType(workRegs, insnRegCount, decInsn.vA,
@@ -3845,22 +4023,29 @@
break;
}
+ /* verify that instruction matches array */
dstType = primitiveTypeToRegType(
resClass->elementClass->primitiveType);
assert(dstType != kRegTypeUnknown);
- if (!canConvertTo1nr(srcType, dstType)) {
- LOG_VFY("VFY: invalid aput-1nr on %s (src=%d dst=%d)\n",
- resClass->descriptor, srcType, dstType);
+ if (!isTypeWidthEqual1nr(tmpType, dstType)) {
+ LOG_VFY("VFY: invalid aput-1nr on %s (inst=%d dst=%d)\n",
+ resClass->descriptor, tmpType, dstType);
okay = false;
break;
}
}
break;
case OP_APUT_WIDE:
+ tmpType = getRegisterType(workRegs, insnRegCount, decInsn.vC,
+ &okay);
+ checkArrayIndexType(meth, tmpType, &okay);
+ if (!okay)
+ break;
+
tmpType = getRegisterType(workRegs, insnRegCount, decInsn.vA, &okay);
if (okay) {
- RegType typeHi =
+ RegType typeHi =
getRegisterType(workRegs, insnRegCount, decInsn.vA+1, &okay);
checkTypeCategory(tmpType, kTypeCategory2, &okay);
checkWidePair(tmpType, typeHi, &okay);
@@ -3897,6 +4082,12 @@
}
break;
case OP_APUT_OBJECT:
+ tmpType = getRegisterType(workRegs, insnRegCount, decInsn.vC,
+ &okay);
+ checkArrayIndexType(meth, tmpType, &okay);
+ if (!okay)
+ break;
+
/* get the ref we're storing; Zero is okay, Uninit is not */
resClass = getClassFromRegister(workRegs, insnRegCount,
decInsn.vA, &okay);
@@ -3984,9 +4175,9 @@
/* make sure the field's type is compatible with expectation */
fieldType = primSigCharToRegType(instField->field.signature[0]);
if (fieldType == kRegTypeUnknown ||
- !canConvertTo1nr(fieldType, tmpType))
+ !isTypeWidthEqual1nr(tmpType, fieldType))
{
- LOG_VFY("VFY: invalid iget-1nr of %s.%s (req=%d actual=%d)\n",
+ LOG_VFY("VFY: invalid iget-1nr of %s.%s (inst=%d field=%d)\n",
instField->field.clazz->descriptor,
instField->field.name, tmpType, fieldType);
okay = false;
@@ -4082,7 +4273,7 @@
RegType srcType, fieldType, objType;
ClassObject* fieldClass;
InstField* instField;
-
+
/* make sure the source register has the correct type */
srcType = getRegisterType(workRegs, insnRegCount, decInsn.vA,
&okay);
@@ -4101,15 +4292,18 @@
&okay);
if (!okay)
break;
+ checkFinalFieldAccess(meth, &instField->field, &okay);
+ if (!okay)
+ break;
/* get type of field we're storing into */
fieldType = primSigCharToRegType(instField->field.signature[0]);
if (fieldType == kRegTypeUnknown ||
- !canConvertTo1nr(srcType, fieldType))
+ !isTypeWidthEqual1nr(tmpType, fieldType))
{
- LOG_VFY("VFY: invalid iput-1nr of %s.%s (src=%d dst=%d)\n",
+ LOG_VFY("VFY: invalid iput-1nr of %s.%s (inst=%d field=%d)\n",
instField->field.clazz->descriptor,
- instField->field.name, srcType, fieldType);
+ instField->field.name, tmpType, fieldType);
okay = false;
break;
}
@@ -4118,7 +4312,7 @@
case OP_IPUT_WIDE:
tmpType = getRegisterType(workRegs, insnRegCount, decInsn.vA, &okay);
if (okay) {
- RegType typeHi =
+ RegType typeHi =
getRegisterType(workRegs, insnRegCount, decInsn.vA+1, &okay);
checkTypeCategory(tmpType, kTypeCategory2, &okay);
checkWidePair(tmpType, typeHi, &okay);
@@ -4136,6 +4330,10 @@
&okay);
if (!okay)
break;
+ checkFinalFieldAccess(meth, &instField->field, &okay);
+ if (!okay)
+ break;
+
/* check the type, which should be prim */
switch (instField->field.signature[0]) {
case 'D':
@@ -4166,6 +4364,10 @@
&okay);
if (!okay)
break;
+ checkFinalFieldAccess(meth, &instField->field, &okay);
+ if (!okay)
+ break;
+
fieldClass = getFieldClass(meth, &instField->field);
if (fieldClass == NULL) {
LOG_VFY("VFY: unable to recover field class from '%s'\n",
@@ -4232,14 +4434,19 @@
if (!okay)
break;
- /* make sure the field's type is compatible with expectation */
+ /*
+ * Make sure the field's type is compatible with expectation.
+ * We can get ourselves into trouble if we mix & match loads
+ * and stores with different widths, so rather than just checking
+ * "canConvertTo1nr" we require that the field types have equal
+ * widths. (We can't generally require an exact type match,
+ * because e.g. "int" and "float" are interchangeable.)
+ */
fieldType = primSigCharToRegType(staticField->field.signature[0]);
- if (fieldType == kRegTypeUnknown ||
- !canConvertTo1nr(fieldType, tmpType))
- {
- LOG_VFY("VFY: invalid sget-1nr of %s.%s (req=%d actual=%d)\n",
- staticField->field.clazz->descriptor,
- staticField->field.name, tmpType, fieldType);
+ if (!isTypeWidthEqual1nr(tmpType, fieldType)) {
+ LOG_VFY("VFY: invalid sget-1nr of %s.%s (inst=%d actual=%d)\n",
+ staticField->field.clazz->descriptor,
+ staticField->field.name, tmpType, fieldType);
okay = false;
break;
}
@@ -4320,7 +4527,7 @@
{
RegType srcType, fieldType;
StaticField* staticField;
-
+
/* make sure the source register has the correct type */
srcType = getRegisterType(workRegs, insnRegCount, decInsn.vA,
&okay);
@@ -4334,15 +4541,22 @@
staticField = getStaticField(meth, decInsn.vB, &okay);
if (!okay)
break;
+ checkFinalFieldAccess(meth, &staticField->field, &okay);
+ if (!okay)
+ break;
- /* get type of field we're storing into */
+ /*
+ * Get type of field we're storing into. We know that the
+ * contents of the register match the instruction, but we also
+ * need to ensure that the instruction matches the field type.
+ * Using e.g. sput-short to write into a 32-bit integer field
+ * can lead to trouble if we do 16-bit writes.
+ */
fieldType = primSigCharToRegType(staticField->field.signature[0]);
- if (fieldType == kRegTypeUnknown ||
- !canConvertTo1nr(srcType, fieldType))
- {
- LOG_VFY("VFY: invalid sput-1nr of %s.%s (req=%d actual=%d)\n",
- staticField->field.clazz->descriptor,
- staticField->field.name, tmpType, fieldType);
+ if (!isTypeWidthEqual1nr(tmpType, fieldType)) {
+ LOG_VFY("VFY: invalid sput-1nr of %s.%s (inst=%d actual=%d)\n",
+ staticField->field.clazz->descriptor,
+ staticField->field.name, tmpType, fieldType);
okay = false;
break;
}
@@ -4351,7 +4565,7 @@
case OP_SPUT_WIDE:
tmpType = getRegisterType(workRegs, insnRegCount, decInsn.vA, &okay);
if (okay) {
- RegType typeHi =
+ RegType typeHi =
getRegisterType(workRegs, insnRegCount, decInsn.vA+1, &okay);
checkTypeCategory(tmpType, kTypeCategory2, &okay);
checkWidePair(tmpType, typeHi, &okay);
@@ -4362,6 +4576,10 @@
staticField = getStaticField(meth, decInsn.vB, &okay);
if (!okay)
break;
+ checkFinalFieldAccess(meth, &staticField->field, &okay);
+ if (!okay)
+ break;
+
/* check the type, which should be prim */
switch (staticField->field.signature[0]) {
case 'D':
@@ -4387,6 +4605,10 @@
staticField = getStaticField(meth, decInsn.vB, &okay);
if (!okay)
break;
+ checkFinalFieldAccess(meth, &staticField->field, &okay);
+ if (!okay)
+ break;
+
fieldClass = getFieldClass(meth, &staticField->field);
if (fieldClass == NULL) {
LOG_VFY("VFY: unable to recover field class from '%s'\n",
@@ -4492,7 +4714,7 @@
}
ClassObject* thisClass;
-
+
thisClass = regTypeReferenceToClass(thisType, uninitMap);
assert(thisClass != NULL);
@@ -4947,6 +5169,13 @@
/*
* Handle "branch". Tag the branch target.
+ *
+ * NOTE: instructions like OP_EQZ provide information about the state
+ * of the register when the branch is taken or not taken. For example,
+ * somebody could get a reference field, check it for zero, and if the
+ * branch is taken immediately store that register in a boolean field
+ * since the value is known to be zero. We do not currently account for
+ * that, and will reject the code.
*/
if ((nextFlags & kInstrCanBranch) != 0) {
bool isConditional;
@@ -5058,7 +5287,7 @@
/*
* callback function used in dumpRegTypes to print local vars
* valid at a given address.
- */
+ */
static void logLocalsCb(void *cnxt, u2 reg, u4 startAddress, u4 endAddress,
const char *name, const char *descriptor,
const char *signature)
@@ -5146,7 +5375,7 @@
if (regTypeIsReference(addrRegs[i]) && addrRegs[i] != kRegTypeZero)
{
ClassObject* clazz;
-
+
clazz = regTypeReferenceToClass(addrRegs[i], uninitMap);
assert(dvmValidateObject((Object*)clazz));
if (i < regCount) {
@@ -5172,3 +5401,4 @@
NULL, logLocalsCb, &addr);
}
}
+
diff --git a/vm/analysis/DexOptimize.c b/vm/analysis/DexOptimize.c
index a726bf9..90e4c6f 100644
--- a/vm/analysis/DexOptimize.c
+++ b/vm/analysis/DexOptimize.c
@@ -13,6 +13,7 @@
* See the License for the specific language governing permissions and
* limitations under the License.
*/
+
/*
* Convert the output from "dx" into a locally-optimized DEX file.
*
@@ -45,14 +46,17 @@
int inlineIdx;
} InlineSub;
+
/* fwd */
static int writeDependencies(int fd, u4 modWhen, u4 crc);
-static bool writeAuxData(int fd, const DexClassLookup* pClassLookup);
+static bool writeAuxData(int fd, const DexClassLookup* pClassLookup,\
+ const IndexMapSet* pIndexMapSet);
static void logFailedWrite(size_t expected, ssize_t actual, const char* msg,
int err);
static bool rewriteDex(u1* addr, int len, bool doVerify, bool doOpt,\
u4* pHeaderFlags, DexClassLookup** ppClassLookup);
+static void updateChecksum(u1* addr, int len, DexHeader* pHeader);
static bool loadAllClasses(DvmDex* pDvmDex);
static void optimizeLoadedClasses(DexFile* pDexFile);
static void optimizeClass(ClassObject* clazz, const InlineSub* inlineSubs);
@@ -87,21 +91,15 @@
* file header, and will be locked with flock. "*pCachedName" will point
* to newly-allocated storage.
*/
-int dvmOpenCachedDexFile(const char* fileName, const char* subFileName,
- u4 modWhen, u4 crc, bool isBootstrap, char** pCachedName, bool* pNewFile,
- bool createIfMissing)
+int dvmOpenCachedDexFile(const char* fileName, const char* cacheFileName,
+ u4 modWhen, u4 crc, bool isBootstrap, bool* pNewFile, bool createIfMissing)
{
- char cacheFileName[512];
int fd, cc;
struct stat fdStat, fileStat;
bool readOnly = false;
*pNewFile = false;
- if (!dexOptGenerateCacheFileName(fileName, subFileName, cacheFileName,
- sizeof(cacheFileName)))
- return -1;
-
retry:
/*
* Try to open the cache file. If we've been asked to,
@@ -156,7 +154,7 @@
goto close_fail;
}
cc = stat(cacheFileName, &fileStat);
- if (cc != 0 ||
+ if (cc != 0 ||
fdStat.st_dev != fileStat.st_dev || fdStat.st_ino != fileStat.st_ino)
{
LOGD("DexOpt: our open cache file is stale; sleeping and retrying\n");
@@ -262,8 +260,6 @@
}
}
- *pCachedName = strdup(cacheFileName);
-
assert(fd >= 0);
return fd;
@@ -316,7 +312,7 @@
if (lastPart != NULL)
lastPart++;
else
- lastPart = "";
+ lastPart = fileName;
/*
* For basic optimizations (byte-swapping and structure aligning) we
@@ -487,8 +483,8 @@
}
/*
- * Do the actual optimization. This is called directly, for "minimal"
- * optimization, or from a newly-created process.
+ * Do the actual optimization. This is called directly for "minimal"
+ * optimization, or from a newly-created process for "full" optimization.
*
* For best use of disk/memory, we want to extract once and perform
* optimizations in place. If the file has to expand or contract
@@ -504,6 +500,7 @@
const char* fileName, u4 modWhen, u4 crc, bool isBootstrap)
{
DexClassLookup* pClassLookup = NULL;
+ IndexMapSet* pIndexMapSet = NULL;
bool doVerify, doOpt;
u4 headerFlags = 0;
@@ -531,6 +528,10 @@
LOGE("too small to be DEX\n");
return false;
}
+ if (dexOffset < (int) sizeof(DexOptHeader)) {
+ LOGE("not enough room for opt header\n");
+ return false;
+ }
bool result = false;
@@ -543,9 +544,9 @@
{
/*
- * Map the entire file (so we don't have to worry about page alignment).
- * The expectation is that the output file contains our DEX data plus
- * a small header.
+ * Map the entire file (so we don't have to worry about page
+ * alignment). The expectation is that the output file contains
+ * our DEX data plus room for a small header.
*/
bool success;
void* mapAddr;
@@ -564,6 +565,29 @@
success = rewriteDex(((u1*) mapAddr) + dexOffset, dexLength,
doVerify, doOpt, &headerFlags, &pClassLookup);
+ if (success) {
+ DvmDex* pDvmDex = NULL;
+ u1* dexAddr = ((u1*) mapAddr) + dexOffset;
+
+ if (dvmDexFileOpenPartial(dexAddr, dexLength, &pDvmDex) != 0) {
+ LOGE("Unable to create DexFile\n");
+ } else {
+ /*
+ * If configured to do so, scan the instructions, looking
+ * for ways to reduce the size of the resolved-constant table.
+ * This is done post-optimization, across the instructions
+ * in all methods in all classes (even the ones that failed
+ * to load).
+ */
+ pIndexMapSet = dvmRewriteConstants(pDvmDex);
+
+ updateChecksum(dexAddr, dexLength,
+ (DexHeader*) pDvmDex->pHeader);
+
+ dvmDexFileFree(pDvmDex);
+ }
+ }
+
/* unmap the read-write version, forcing writes to disk */
if (msync(mapAddr, dexOffset + dexLength, MS_SYNC) != 0) {
LOGW("msync failed: %s\n", strerror(errno));
@@ -627,7 +651,7 @@
/*
* Append any auxillary pre-computed data structures.
*/
- if (!writeAuxData(fd, pClassLookup)) {
+ if (!writeAuxData(fd, pClassLookup, pIndexMapSet)) {
LOGW("Failed writing aux data\n");
goto bail;
}
@@ -664,6 +688,7 @@
result = true;
bail:
+ dvmFreeIndexMapSet(pIndexMapSet);
free(pClassLookup);
return result;
}
@@ -995,30 +1020,85 @@
return result;
}
-/*
- * Write aux data.
- *
- * At the moment this is just the DexClassLookup structure. In theory we
- * will tuck other stuff in here. When theory becomes reality, we will need
- * to stow a TOC in here (or use a "chunk" format). Until then we just
- * write a zero into the first 4 bytes so future generations have something
- * to test for.
- */
-static bool writeAuxData(int fd, const DexClassLookup* pClassLookup)
-{
- DexFile* pDexFile;
- ssize_t actual;
- int zero = 0;
- actual = write(fd, &zero, sizeof(zero));
- if (actual != sizeof(zero)) {
- logFailedWrite(sizeof(zero), actual, "aux header", errno);
+/*
+ * Write a block of data in "chunk" format.
+ *
+ * The chunk header fields are always in "native" byte order. If "size"
+ * is not a multiple of 8 bytes, the data area is padded out.
+ */
+static bool writeChunk(int fd, u4 type, const void* data, size_t size)
+{
+ ssize_t actual;
+ union { /* save a syscall by grouping these together */
+ char raw[8];
+ struct {
+ u4 type;
+ u4 size;
+ } ts;
+ } header;
+
+ assert(sizeof(header) == 8);
+
+ LOGV("Writing chunk, type=%.4s size=%d\n", (char*) &type, size);
+
+ header.ts.type = type;
+ header.ts.size = (u4) size;
+ actual = write(fd, &header, sizeof(header));
+ if (actual != sizeof(header)) {
+ logFailedWrite(size, actual, "aux chunk header write", errno);
return false;
}
- actual = write(fd, pClassLookup, pClassLookup->size);
- if (actual != pClassLookup->size) {
- logFailedWrite(pClassLookup->size, actual, "class lookup table", errno);
+ if (size > 0) {
+ actual = write(fd, data, size);
+ if (actual != (ssize_t) size) {
+ logFailedWrite(size, actual, "aux chunk write", errno);
+ return false;
+ }
+ }
+
+ /* if necessary, pad to 64-bit alignment */
+ if ((size & 7) != 0) {
+ int padSize = 8 - (size & 7);
+ LOGV("size was %d, inserting %d pad bytes\n", size, padSize);
+ lseek(fd, padSize, SEEK_CUR);
+ }
+
+ assert( ((int)lseek(fd, 0, SEEK_CUR) & 7) == 0);
+
+ return true;
+}
+
+/*
+ * Write aux data.
+ *
+ * We have different pieces, some of which may be optional. To make the
+ * most effective use of space, we use a "chunk" format, with a 4-byte
+ * type and a 4-byte length. We guarantee 64-bit alignment for the data,
+ * so it can be used directly when the file is mapped for reading.
+ */
+static bool writeAuxData(int fd, const DexClassLookup* pClassLookup,
+ const IndexMapSet* pIndexMapSet)
+{
+ /* pre-computed class lookup hash table */
+ if (!writeChunk(fd, (u4) kDexChunkClassLookup, pClassLookup,
+ pClassLookup->size))
+ {
+ return false;
+ }
+
+ /* remapped constants (optional) */
+ if (pIndexMapSet != NULL) {
+ if (!writeChunk(fd, pIndexMapSet->chunkType, pIndexMapSet->chunkData,
+ pIndexMapSet->chunkDataLen))
+ {
+ return false;
+ }
+ }
+
+ /* write the end marker */
+ if (!writeChunk(fd, (u4) kDexChunkEnd, NULL, 0)) {
return false;
}
@@ -1134,15 +1214,30 @@
result = true;
bail:
- /*
- * Free up storage.
- */
+ /* free up storage */
dvmDexFileFree(pDvmDex);
return result;
}
/*
+ * Update the Adler-32 checksum stored in the DEX file. This covers the
+ * swapped and optimized DEX data, but does not include the opt header
+ * or auxillary data.
+ */
+static void updateChecksum(u1* addr, int len, DexHeader* pHeader)
+{
+ /*
+ * Rewrite the checksum. We leave the SHA-1 signature alone.
+ */
+ uLong adler = adler32(0L, Z_NULL, 0);
+ const int nonSum = sizeof(pHeader->magic) + sizeof(pHeader->checksum);
+
+ adler = adler32(adler, addr + nonSum, len - nonSum);
+ pHeader->checksum = adler;
+}
+
+/*
* Try to load all classes in the specified DEX. If they have some sort
* of broken dependency, e.g. their superclass lives in a different DEX
* that wasn't previously loaded into the bootstrap class path, loading
@@ -1187,7 +1282,7 @@
const DexClassDef* pClassDef;
const char* classDescriptor;
ClassObject* newClass;
-
+
pClassDef = dexGetClassDef(pDvmDex->pDexFile, idx);
classDescriptor =
dexStringByTypeIdx(pDvmDex->pDexFile, pClassDef->classIdx);
@@ -1251,12 +1346,6 @@
* Method could be virtual or direct. Try both. Don't use
* the "hier" versions.
*/
- if (!dvmIsFinalClass(clazz)) {
- LOGW("DexOpt: WARNING: inline op on non-final class '%s'\n",
- clazz->descriptor);
- // TODO: final methods in non-final classes are okay too
- /* keep going, I guess */
- }
method = dvmFindDirectMethodByDescriptor(clazz, ops[i].methodName,
ops[i].methodSignature);
if (method == NULL)
@@ -1267,6 +1356,21 @@
ops[i].classDescriptor, ops[i].methodName,
ops[i].methodSignature);
} else {
+ if (!dvmIsFinalClass(clazz) && !dvmIsFinalMethod(method)) {
+ LOGW("DexOpt: WARNING: inline op on non-final class/method "
+ "%s.%s\n",
+ clazz->descriptor, method->name);
+ /* fail? */
+ }
+ if (dvmIsSynchronizedMethod(method) ||
+ dvmIsDeclaredSynchronizedMethod(method))
+ {
+ LOGW("DexOpt: WARNING: inline op on synchronized method "
+ "%s.%s\n",
+ clazz->descriptor, method->name);
+ /* fail? */
+ }
+
table[tableIndex].method = method;
table[tableIndex].inlineIdx = i;
tableIndex++;
@@ -1304,9 +1408,9 @@
const DexClassDef* pClassDef;
const char* classDescriptor;
ClassObject* clazz;
-
+
pClassDef = dexGetClassDef(pDexFile, idx);
- classDescriptor= dexStringByTypeIdx(pDexFile, pClassDef->classIdx);
+ classDescriptor = dexStringByTypeIdx(pDexFile, pClassDef->classIdx);
/* all classes are loaded into the bootstrap class loader */
clazz = dvmLookupClass(classDescriptor, NULL, false);
@@ -1332,7 +1436,7 @@
classDescriptor);
}
}
-
+
free(inlineSubs);
}
diff --git a/vm/analysis/DexOptimize.h b/vm/analysis/DexOptimize.h
index 207140b..ecb71d3 100644
--- a/vm/analysis/DexOptimize.h
+++ b/vm/analysis/DexOptimize.h
@@ -39,9 +39,8 @@
*
* Returns the file descriptor, locked and seeked past the "opt" header.
*/
-int dvmOpenCachedDexFile(const char* fileName, const char* subFileName,
- u4 modWhen, u4 crc, bool isBootstrap, char** pCachedName, bool* pNewFile,
- bool createIfMissing);
+int dvmOpenCachedDexFile(const char* fileName, const char* cachedFile,
+ u4 modWhen, u4 crc, bool isBootstrap, bool* pNewFile, bool createIfMissing);
/*
* Unlock the specified file descriptor. Use in conjunction with
diff --git a/vm/analysis/DexVerify.c b/vm/analysis/DexVerify.c
index ab1e50b..3b69e83 100644
--- a/vm/analysis/DexVerify.c
+++ b/vm/analysis/DexVerify.c
@@ -13,6 +13,7 @@
* See the License for the specific language governing permissions and
* limitations under the License.
*/
+
/*
* Dalvik classfile verification. This file contains the verifier entry
* points and the static constraint checks.
@@ -36,8 +37,6 @@
static bool verifyMethod(Method* meth, int verifyFlags);
static bool verifyInstructions(const Method* meth, InsnFlags* insnFlags,
int verifyFlags);
-static bool checkNewInstance(const Method* meth, int insnIdx);
-static bool checkNewArray(const Method* meth, int insnIdx);
/*
@@ -90,7 +89,7 @@
const DexClassDef* pClassDef;
const char* classDescriptor;
ClassObject* clazz;
-
+
pClassDef = dexGetClassDef(pDexFile, idx);
classDescriptor = dexStringByTypeIdx(pDexFile, pClassDef->classIdx);
@@ -197,7 +196,17 @@
goto success;
}
-
+
+ /*
+ * Sanity-check the register counts. ins + locals = registers, so make
+ * sure that ins <= registers.
+ */
+ if (meth->insSize > meth->registersSize) {
+ LOG_VFY_METH(meth, "VFY: bad register counts (ins=%d regs=%d)\n",
+ meth->insSize, meth->registersSize);
+ goto bail;
+ }
+
/*
* Allocate and populate an array to hold instruction data.
*
@@ -281,16 +290,14 @@
int width;
/*
- * Switch tables are identified with "extended NOP" opcodes. They
- * contain no executable code, so we can just skip past them.
+ * Switch tables and array data tables are identified with
+ * "extended NOP" opcodes. They contain no executable code,
+ * so we can just skip past them.
*/
if (*insns == kPackedSwitchSignature) {
width = 4 + insns[1] * 2;
} else if (*insns == kSparseSwitchSignature) {
width = 2 + insns[1] * 4;
- /*
- * Array data table is identified with similar extended NOP opcode.
- */
} else if (*insns == kArrayDataSignature) {
u4 size = insns[2] | (((u4)insns[3]) << 16);
width = 4 + (insns[1] * size + 1) / 2;
@@ -396,7 +403,7 @@
for (;;) {
DexCatchHandler* handler = dexCatchIteratorNext(&iterator);
u4 addr;
-
+
if (handler == NULL) {
break;
}
@@ -408,7 +415,7 @@
addr);
return false;
}
-
+
dvmInsnSetBranchTarget(insnFlags, addr, true);
}
@@ -481,7 +488,7 @@
/* for a sparse switch, verify the keys are in ascending order */
if (offsetToKeys > 0 && switchCount > 1) {
s4 lastKey;
-
+
lastKey = switchInsns[offsetToKeys] |
(switchInsns[offsetToKeys+1] << 16);
for (targ = 1; targ < switchCount; targ++) {
@@ -625,6 +632,162 @@
return true;
}
+
+/*
+ * Decode the current instruction.
+ */
+static void decodeInstruction(const Method* meth, int insnIdx,
+ DecodedInstruction* pDecInsn)
+{
+ dexDecodeInstruction(gDvm.instrFormat, meth->insns + insnIdx, pDecInsn);
+}
+
+
+/*
+ * Perform static checks on a "new-instance" instruction. Specifically,
+ * make sure the class reference isn't for an array class.
+ *
+ * We don't need the actual class, just a pointer to the class name.
+ */
+static bool checkNewInstance(const Method* meth, int insnIdx)
+{
+ DexFile* pDexFile = meth->clazz->pDvmDex->pDexFile;
+ DecodedInstruction decInsn;
+ const char* classDescriptor;
+
+ decodeInstruction(meth, insnIdx, &decInsn);
+ classDescriptor = dexStringByTypeIdx(pDexFile, decInsn.vB); // 2nd item
+
+ if (classDescriptor[0] != 'L') {
+ LOG_VFY_METH(meth, "VFY: can't call new-instance on type '%s'\n",
+ classDescriptor);
+ return false;
+ }
+
+ return true;
+}
+
+/*
+ * Perform static checks on a "new-array" instruction. Specifically, make
+ * sure they aren't creating an array of arrays that causes the number of
+ * dimensions to exceed 255.
+ */
+static bool checkNewArray(const Method* meth, int insnIdx)
+{
+ DexFile* pDexFile = meth->clazz->pDvmDex->pDexFile;
+ DecodedInstruction decInsn;
+ const char* classDescriptor;
+
+ decodeInstruction(meth, insnIdx, &decInsn);
+ classDescriptor = dexStringByTypeIdx(pDexFile, decInsn.vC); // 3rd item
+
+ int bracketCount = 0;
+ const char* cp = classDescriptor;
+ while (*cp++ == '[')
+ bracketCount++;
+
+ if (bracketCount == 0) {
+ /* The given class must be an array type. */
+ LOG_VFY_METH(meth, "VFY: can't new-array class '%s' (not an array)\n",
+ classDescriptor);
+ return false;
+ } else if (bracketCount > 255) {
+ /* It is illegal to create an array of more than 255 dimensions. */
+ LOG_VFY_METH(meth, "VFY: can't new-array class '%s' (exceeds limit)\n",
+ classDescriptor);
+ return false;
+ }
+
+ return true;
+}
+
+/*
+ * Perform static checks on an instruction that takes a class constant.
+ * Ensure that the class index is in the valid range.
+ */
+static bool checkTypeIndex(const Method* meth, int insnIdx, bool useB)
+{
+ DvmDex* pDvmDex = meth->clazz->pDvmDex;
+ DecodedInstruction decInsn;
+ u4 idx;
+
+ decodeInstruction(meth, insnIdx, &decInsn);
+ if (useB)
+ idx = decInsn.vB;
+ else
+ idx = decInsn.vC;
+ if (idx >= pDvmDex->pHeader->typeIdsSize) {
+ LOG_VFY_METH(meth, "VFY: bad type index %d (max %d)\n",
+ idx, pDvmDex->pHeader->typeIdsSize);
+ return false;
+ }
+
+ return true;
+}
+
+/*
+ * Perform static checks on a field get or set instruction. All we do
+ * here is ensure that the field index is in the valid range.
+ */
+static bool checkFieldIndex(const Method* meth, int insnIdx, bool useB)
+{
+ DvmDex* pDvmDex = meth->clazz->pDvmDex;
+ DecodedInstruction decInsn;
+ u4 idx;
+
+ decodeInstruction(meth, insnIdx, &decInsn);
+ if (useB)
+ idx = decInsn.vB;
+ else
+ idx = decInsn.vC;
+ if (idx >= pDvmDex->pHeader->fieldIdsSize) {
+ LOG_VFY_METH(meth,
+ "VFY: bad field index %d (max %d) at offset 0x%04x\n",
+ idx, pDvmDex->pHeader->fieldIdsSize, insnIdx);
+ return false;
+ }
+
+ return true;
+}
+
+/*
+ * Perform static checks on a method invocation instruction. All we do
+ * here is ensure that the method index is in the valid range.
+ */
+static bool checkMethodIndex(const Method* meth, int insnIdx)
+{
+ DvmDex* pDvmDex = meth->clazz->pDvmDex;
+ DecodedInstruction decInsn;
+
+ decodeInstruction(meth, insnIdx, &decInsn);
+ if (decInsn.vB >= pDvmDex->pHeader->methodIdsSize) {
+ LOG_VFY_METH(meth, "VFY: bad method index %d (max %d)\n",
+ decInsn.vB, pDvmDex->pHeader->methodIdsSize);
+ return false;
+ }
+
+ return true;
+}
+
+/*
+ * Perform static checks on a string constant instruction. All we do
+ * here is ensure that the string index is in the valid range.
+ */
+static bool checkStringIndex(const Method* meth, int insnIdx)
+{
+ DvmDex* pDvmDex = meth->clazz->pDvmDex;
+ DecodedInstruction decInsn;
+
+ decodeInstruction(meth, insnIdx, &decInsn);
+ if (decInsn.vB >= pDvmDex->pHeader->stringIdsSize) {
+ LOG_VFY_METH(meth, "VFY: bad string index %d (max %d)\n",
+ decInsn.vB, pDvmDex->pHeader->stringIdsSize);
+ return false;
+ }
+
+ return true;
+}
+
/*
* Perform static verification on instructions.
*
@@ -659,6 +822,10 @@
* end at the start of an instruction (end can be at the end of the code)
* - (earlier) for each exception handler, the handler must start at a valid
* instruction
+ *
+ * TODO: move some of the "CF" items in here for better performance (the
+ * code-flow analysis sometimes has to process the same instruction several
+ * times).
*/
static bool verifyInstructions(const Method* meth, InsnFlags* insnFlags,
int verifyFlags)
@@ -678,6 +845,22 @@
/* plain no-op or switch table data; nothing to do here */
break;
+ case OP_CONST_STRING:
+ case OP_CONST_STRING_JUMBO:
+ if (!checkStringIndex(meth, i))
+ return false;
+ break;
+
+ case OP_CONST_CLASS:
+ case OP_CHECK_CAST:
+ if (!checkTypeIndex(meth, i, true))
+ return false;
+ break;
+ case OP_INSTANCE_OF:
+ if (!checkTypeIndex(meth, i, false))
+ return false;
+ break;
+
case OP_PACKED_SWITCH:
case OP_SPARSE_SWITCH:
/* verify the associated table */
@@ -690,7 +873,7 @@
if (!checkArrayData(meth, i))
return false;
break;
-
+
case OP_GOTO:
case OP_GOTO_16:
case OP_IF_EQ:
@@ -725,6 +908,67 @@
return false;
break;
+ case OP_FILLED_NEW_ARRAY:
+ if (!checkTypeIndex(meth, i, false))
+ return false;
+ break;
+ case OP_FILLED_NEW_ARRAY_RANGE:
+ if (!checkTypeIndex(meth, i, true))
+ return false;
+ break;
+
+ case OP_IGET:
+ case OP_IGET_WIDE:
+ case OP_IGET_OBJECT:
+ case OP_IGET_BOOLEAN:
+ case OP_IGET_BYTE:
+ case OP_IGET_CHAR:
+ case OP_IGET_SHORT:
+ case OP_IPUT:
+ case OP_IPUT_WIDE:
+ case OP_IPUT_OBJECT:
+ case OP_IPUT_BOOLEAN:
+ case OP_IPUT_BYTE:
+ case OP_IPUT_CHAR:
+ case OP_IPUT_SHORT:
+ /* check the field index */
+ if (!checkFieldIndex(meth, i, false))
+ return false;
+ break;
+ case OP_SGET:
+ case OP_SGET_WIDE:
+ case OP_SGET_OBJECT:
+ case OP_SGET_BOOLEAN:
+ case OP_SGET_BYTE:
+ case OP_SGET_CHAR:
+ case OP_SGET_SHORT:
+ case OP_SPUT:
+ case OP_SPUT_WIDE:
+ case OP_SPUT_OBJECT:
+ case OP_SPUT_BOOLEAN:
+ case OP_SPUT_BYTE:
+ case OP_SPUT_CHAR:
+ case OP_SPUT_SHORT:
+ /* check the field index */
+ if (!checkFieldIndex(meth, i, true))
+ return false;
+ break;
+
+ case OP_INVOKE_VIRTUAL:
+ case OP_INVOKE_SUPER:
+ case OP_INVOKE_DIRECT:
+ case OP_INVOKE_STATIC:
+ case OP_INVOKE_INTERFACE:
+ case OP_INVOKE_VIRTUAL_RANGE:
+ case OP_INVOKE_SUPER_RANGE:
+ case OP_INVOKE_DIRECT_RANGE:
+ case OP_INVOKE_STATIC_RANGE:
+ case OP_INVOKE_INTERFACE_RANGE:
+ /* check the method index */
+ if (!checkMethodIndex(meth, i))
+ return false;
+ break;
+
case OP_EXECUTE_INLINE:
case OP_INVOKE_DIRECT_EMPTY:
case OP_IGET_QUICK:
@@ -763,61 +1007,3 @@
return true;
}
-
-/*
- * Perform static checks on a "new-instance" instruction. Specifically,
- * make sure the class reference isn't for an array class.
- *
- * We don't need the actual class, just a pointer to the class name.
- */
-static bool checkNewInstance(const Method* meth, int insnIdx)
-{
- DexFile* pDexFile = meth->clazz->pDvmDex->pDexFile;
- DecodedInstruction decInsn;
- const char* classDescriptor;
-
- dexDecodeInstruction(gDvm.instrFormat, meth->insns + insnIdx, &decInsn);
- classDescriptor = dexStringByTypeIdx(pDexFile, decInsn.vB); // 2nd item
-
- if (classDescriptor[0] != 'L') {
- LOG_VFY_METH(meth, "VFY: can't call new-instance on type '%s'\n",
- classDescriptor);
- return false;
- }
-
- return true;
-}
-
-/*
- * Perform static checks on a "new-array" instruction. Specifically, make
- * sure they aren't creating an array of arrays that causes the number of
- * dimensions to exceed 255.
- */
-static bool checkNewArray(const Method* meth, int insnIdx)
-{
- DexFile* pDexFile = meth->clazz->pDvmDex->pDexFile;
- DecodedInstruction decInsn;
- const char* classDescriptor;
-
- dexDecodeInstruction(gDvm.instrFormat, meth->insns + insnIdx, &decInsn);
- classDescriptor = dexStringByTypeIdx(pDexFile, decInsn.vC); // 3rd item
-
- int bracketCount = 0;
- const char* cp = classDescriptor;
- while (*cp++ == '[')
- bracketCount++;
-
- if (bracketCount == 0) {
- /* The given class must be an array type. */
- LOG_VFY_METH(meth, "VFY: can't new-array class '%s' (not an array)\n",
- classDescriptor);
- return false;
- } else if (bracketCount > 255) {
- /* It is illegal to create an array of more than 255 dimensions. */
- LOG_VFY_METH(meth, "VFY: can't new-array class '%s' (exceeds limit)\n",
- classDescriptor);
- return false;
- }
-
- return true;
-}
diff --git a/vm/analysis/ReduceConstants.c b/vm/analysis/ReduceConstants.c
new file mode 100644
index 0000000..ec7ba0f
--- /dev/null
+++ b/vm/analysis/ReduceConstants.c
@@ -0,0 +1,1057 @@
+/*
+ * Copyright (C) 2008 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.
+ */
+
+/*
+ * Compress the range of "constant pool" indexes in instructions and
+ * annotations to lower runtime RAM footprint.
+ *
+ * NOTE: this is an incomplete experimental feature. Do not try to use it.
+ */
+#include "Dalvik.h"
+#include "libdex/InstrUtils.h"
+#include "libdex/OptInvocation.h"
+#include "libdex/DexClass.h"
+
+/*
+Overview
+
+When a class, method, field, or string constant is referred to from
+Dalvik bytecode, the reference takes the form of an integer index value.
+This value indexes into an array of type_id_item, method_id_item,
+field_id_item, or string_id_item in the DEX file. The first three
+themselves contain (directly or indirectly) indexes to strings that the
+resolver uses to convert the instruction stream index into a pointer to
+the appropriate object or struct.
+
+For example, an invoke-virtual instruction needs to specify which method
+is to be invoked. The method constant indexes into the method_id_item
+array, each entry of which has indexes that specify the defining class
+(type_id_item), method name (string_id_item), and method prototype
+(proto_id_item). The type_id_item just holds an index to a string_id_item,
+which holds the file offset to the string with the class name. The VM
+finds the class by name, then searches through the class' table of virtual
+methods to find one with a matching name and prototype.
+
+This process is fairly expensive, so after the first time it completes
+successfully, the VM records that the method index resolved to a specific
+Method struct. On subsequent execution, the VM just pulls the Method ptr
+out of the resolved-methods array. A similar approach is used with
+the indexes for classes, fields, and string constants.
+
+The problem with this approach is that we need to have a "resolved" entry
+for every possible class, method, field, and string constant in every
+DEX file, even if some of those aren't used from code. The DEX string
+constant table has entries for method prototypes and class names that are
+never used by the code, and "public static final" fields often turn into
+immediate constants. The resolution table entries are only 4 bytes each,
+but there are roughly 200,000 of them in the bootstrap classes alone.
+
+DEX optimization removes many index references by replacing virtual method
+indexes with vtable offsets and instance field indexes with byte offsets.
+In the earlier example, the method would be resolved at "dexopt" time, and
+the instruction rewritten as invoke-virtual-quick with the vtable offset.
+
+(There are comparatively few classes compared to other constant pool
+entries, and a much higher percentage (typically 60-70%) are used. The
+biggest gains come from the string pool.)
+
+Using the resolved-entity tables provides a substantial performance
+improvement, but results in applications allocating 1MB+ of tables that
+are 70% unused. The used and unused entries are freely intermixed,
+preventing effective sharing with the zygote process, and resulting in
+large numbers of private/dirty pages on the native heap as the tables
+populate on first use.
+
+The trick is to reduce the memory usage without decreasing performance.
+Using smaller resolved-entity tables can actually give us a speed boost,
+because we'll have a smaller "live" set of pages and make more effective
+use of the data cache.
+
+
+The approach we're going to use is to determine the set of indexes that
+could potentially be resolved, generate a mapping from the minimal set to
+the full set, and append the mapping to the DEX file. This is done at
+"dexopt" time, because we need to keep the changes in shared/read-only
+pages or we'll lose the benefits of doing the work.
+
+There are two ways to create and use the new mapping:
+
+ (1) Write the entire full->minimal mapping to the ".odex" file. On every
+ instruction that uses an index, use the mapping to determine the
+ "compressed" constant value, and then use that to index into the
+ resolved-entity tables on the heap. The instruction stream is unchanged,
+ and the resolver can easily tell if a given index is cacheable.
+
+ (2) Write the inverse miminal->full mapping to the ".odex" file, and
+ rewrite the constants in the instruction stream. The interpreter is
+ unchanged, and the resolver code uses the mapping to find the original
+ data in the DEX.
+
+Approach #1 is easier and safer to implement, but it requires a table
+lookup every time we execute an instruction that includes a constant
+pool reference. This causes an unacceptable performance hit, chiefly
+because we're hitting semi-random memory pages and hosing the data cache.
+This is mitigated somewhat by DEX optimizations that replace the constant
+with a vtable index or field byte offset. Approach #1 also requires
+a larger map table, increasing the size of the DEX on disk. One nice
+property of approach #1 is that most of the DEX file is unmodified,
+so use of the mapping is a runtime decision.
+
+Approach #2 is preferred for performance reasons.
+
+
+The class/method/field/string resolver code has to handle indices from
+three sources: interpreted instructions, annotations, and exception
+"catch" lists. Sometimes these occur indirectly, e.g. we need to resolve
+the declaring class associated with fields and methods when the latter
+two are themselves resolved. Parsing and rewriting instructions is fairly
+straightforward, but annotations use a complex format with variable-width
+index values.
+
+We can safely rewrite index values in annotations if we guarantee that the
+new value is smaller than the original. This implies a two-pass approach:
+the first determines the set of indexes actually used, the second does the
+rewrite. Doing the rewrite in a single pass would be much harder.
+
+Instances of the "original" indices will still be found in the file; if
+we try to be all-inclusive we will include some stuff that doesn't need
+to be there (e.g. we don't generally need to cache the class name string
+index result, since once we have the class resolved we don't need to look
+it up by name through the resolver again). There is some potential for
+performance improvement by caching more than we strictly need, but we can
+afford to give up a little performance during class loading if it allows
+us to regain some memory.
+
+For safety and debugging, it's useful to distinguish the "compressed"
+constants in some way, e.g. setting the high bit when we rewrite them.
+In practice we don't have any free bits: indexes are usually 16-bit
+values, and we have more than 32,767 string constants in at least one of
+our core DEX files. Also, this does not work with constants embedded in
+annotations, because of the variable-width encoding.
+
+We should be safe if we can establish a clear distinction between sources
+of "original" and "compressed" indices. If the values get crossed up we
+can end up with elusive bugs. The easiest approach is to declare that
+only indices pulled from certain locations (the instruction stream and/or
+annotations) are compressed. This prevents us from adding indices in
+arbitrary locations to the compressed set, but should allow a reasonably
+robust implementation.
+
+
+Further implementation thoughts:
+
+ - We don't have to do annotations in the first pass. At heart the
+ resolved entity cache is a performance optimization, not necessary for
+ correctness, and we're not making annotation performance a priority
+ at this stage.
+ - The most important "fast path" is instruction processing. Everything
+ else can do additional work without having a measurable impact.
+ However...
+ - We need to keep an eye on uncached resolves to ensure that we haven't
+ introduced noticeable performance losses. In particular, the use of
+ runtime annotations with string constants may suffer if we don't include
+ annotation rewriting in the solution.
+ - We can have separate resolver functions for "original" and "compressed"
+ indices. This way we don't have to add a flag argument to the resolver
+ functions (which would require passing an additional parameter in from
+ the interpreter).
+ - The VM spec has some specific things to say about string constant
+ equality and interning. Index compression should have no effect on
+ that; we just change how long it takes to find the interned string in
+ certain circumstances. The impact can be mitigated somewhat by
+ improving the performance of the interned string table code.
+ - This can make e.g. method resolution slower. The method_id_item has
+ an index to a method name string, and we will no longer cache the
+ result of resolving that string. This impacts resolution of any method
+ with the same name as a previously-resolved method.
+ - We may need to tweak the tools, particularly "dexdump", to show the
+ translated values.
+ - We can use 16-bit values in the mapping table, since we should have
+ fewer than 2^16 remapped entries. If we overflow we can skip the remap
+ for that table or for the entire DEX file. The resolver will need to
+ check for the existence of the table to determine whether or not entries
+ must be remapped. The cost of the extra check is acceptable for
+ approach #2, since it's only at resolve time, but may be undesirable
+ for approach #1.
+*/
+/*
+Output Formats
+
+There are two possible output formats, from which we choose based on how
+we plan to take advantage of the remapped constants. At most one of these
+will appear in the DEX.
+
+NOTE: if EIXM appears in the DEX, the VM *must* be configured with
+DVM_RESOLVER_CACHE=DVM_RC_EXPANDING (2). Otherwise the constants we
+pull from the instruction stream will be wrong and we will fail quickly.
+
+For approach #1: map from original indices to the reduced set.
+
+ This includes the four "mapToNew" tables.
+
+ Format (RIXM):
+ u4 classCount // #of entries in classMap[]; == typeIdsSize
+ u4 reducedClassCount // #of entries in remapped table (for alloc)
+ u2 classMap[]
+ u4 methodCount
+ u4 reducedMethodCount
+ u2 methodMap[]
+ u4 fieldCount
+ u4 reducedFieldCount
+ u2 fieldMap[]
+ u4 stringCount
+ u4 reducedStringCount
+ u2 stringMap[]
+
+For approach #2: map from the reduced set back to the originals.
+
+ This includes the four "mapToOld" tables.
+
+ Format (EIXM):
+ u4 classCount // #of entries in classMap[]; post-reduction
+ u2 classMap[]
+ u4 methodCount
+ u2 methodMap[]
+ u4 fieldCount
+ u2 fieldMap[]
+ u4 stringCount
+ u2 stringMap[]
+
+The arrays are padded so that the "count" values are always aligned on
+32-bit boundaries. All multi-byte values are in native host order.
+*/
+
+
+/*
+ * Gather results from the post-optimization instruction scan.
+ */
+typedef struct ScanResults {
+ /* output */
+ BitVector* usedClasses;
+ BitVector* usedMethods;
+ BitVector* usedFields;
+ BitVector* usedStrings;
+} ScanResults;
+
+/* prototype for the for-all-methods function */
+typedef void (AllMethodsFunc)(DexFile* pDexFile, const char* classDescriptor,
+ DexMethod* pDexMethod, void* arg);
+
+
+/*
+ * Free scan results.
+ */
+static void freeScanResults(ScanResults* pResults)
+{
+ if (pResults == NULL)
+ return;
+
+ dvmFreeBitVector(pResults->usedClasses);
+ dvmFreeBitVector(pResults->usedMethods);
+ dvmFreeBitVector(pResults->usedFields);
+ dvmFreeBitVector(pResults->usedStrings);
+ free(pResults);
+}
+
+/*
+ * Allocate storage for the results of the instruction scan.
+ */
+static ScanResults* allocScanResults(const DexFile* pDexFile)
+{
+ ScanResults* pResults;
+ const DexHeader* pHeader = pDexFile->pHeader;
+
+ pResults = (ScanResults*) calloc(1, sizeof(ScanResults));
+ if (pResults == NULL)
+ return NULL;
+
+ pResults->usedClasses = dvmAllocBitVector(pHeader->typeIdsSize, false);
+ pResults->usedMethods = dvmAllocBitVector(pHeader->methodIdsSize, false);
+ pResults->usedFields = dvmAllocBitVector(pHeader->fieldIdsSize, false);
+ pResults->usedStrings = dvmAllocBitVector(pHeader->stringIdsSize, false);
+
+ if (pResults->usedClasses == NULL ||
+ pResults->usedMethods == NULL ||
+ pResults->usedFields == NULL ||
+ pResults->usedStrings == NULL)
+ {
+ freeScanResults(pResults);
+ return NULL;
+ }
+
+ return pResults;
+}
+
+/*
+ * Call "func(method, arg)" on all methods in the specified class.
+ *
+ * Pass in a pointer to the class_data_item, positioned at the start of
+ * the field data (i.e. just past the class data header).
+ *
+ * "classDescriptor" is for debug messages.
+ */
+static void forAllMethodsInClass(DexFile* pDexFile, const u1** ppEncodedData,
+ const DexClassDataHeader* pHeader, const char* classDescriptor,
+ AllMethodsFunc func, void* arg)
+{
+ int i;
+
+ /*
+ * Consume field data.
+ */
+ if (pHeader->staticFieldsSize != 0) {
+ int count = (int) pHeader->staticFieldsSize;
+ u4 lastIndex = 0;
+ DexField field;
+ for (i = 0; i < count; i++) {
+ dexReadClassDataField(ppEncodedData, &field, &lastIndex);
+ }
+ }
+ if (pHeader->instanceFieldsSize != 0) {
+ int count = (int) pHeader->instanceFieldsSize;
+ u4 lastIndex = 0;
+ DexField field;
+ for (i = 0; i < count; i++) {
+ dexReadClassDataField(ppEncodedData, &field, &lastIndex);
+ }
+ }
+
+ /*
+ * Run through all methods.
+ */
+ if (pHeader->directMethodsSize != 0) {
+ int count = (int) pHeader->directMethodsSize;
+ u4 lastIndex = 0;
+ DexMethod method;
+
+ for (i = 0; i < count; i++) {
+ dexReadClassDataMethod(ppEncodedData, &method, &lastIndex);
+ (func)(pDexFile, classDescriptor, &method, arg);
+ }
+ }
+ if (pHeader->virtualMethodsSize != 0) {
+ int count = (int) pHeader->virtualMethodsSize;
+ u4 lastIndex = 0;
+ DexMethod method;
+
+ for (i = 0; i < count; i++) {
+ dexReadClassDataMethod(ppEncodedData, &method, &lastIndex);
+ (func)(pDexFile, classDescriptor, &method, arg);
+ }
+ }
+}
+
+/*
+ * Call "func(method, arg)" on all methods in all classes in DexFile.
+ */
+static void forAllMethods(DexFile* pDexFile, AllMethodsFunc func, void* arg)
+{
+ u4 count = pDexFile->pHeader->classDefsSize;
+ u4 idx;
+
+ for (idx = 0; idx < count; idx++) {
+ const DexClassDef* pClassDef;
+ DexClassDataHeader header;
+ const u1* pEncodedData;
+
+ pClassDef = dexGetClassDef(pDexFile, idx);
+ pEncodedData = dexGetClassData(pDexFile, pClassDef);
+
+ const char* classDescriptor;
+ classDescriptor = dexStringByTypeIdx(pDexFile, pClassDef->classIdx);
+
+ if (pEncodedData != NULL) {
+ dexReadClassDataHeader(&pEncodedData, &header);
+
+ forAllMethodsInClass(pDexFile, &pEncodedData, &header,
+ classDescriptor, func, arg);
+ } else {
+ //printf("%s: no class data\n", classDescriptor);
+ /* no class data, e.g. "marker interface" */
+ }
+ }
+}
+
+/*
+ * Mark a class ID as referenced.
+ */
+static void markClass(const u2* ptr, ScanResults* pResults)
+{
+ u2 classIdx = *ptr;
+ if (!dvmSetBit(pResults->usedClasses, classIdx)) {
+ LOGE("Unable to mark class %d as in-use\n", classIdx);
+ }
+}
+
+/*
+ * Mark a method ID as referenced.
+ */
+static void markMethod(const u2* ptr, ScanResults* pResults)
+{
+ u2 methodIdx = *ptr;
+ if (!dvmSetBit(pResults->usedMethods, methodIdx)) {
+ LOGE("Unable to mark method %d as in-use\n", methodIdx);
+ }
+}
+
+/*
+ * Mark a field ID as referenced.
+ */
+static void markField(const u2* ptr, ScanResults* pResults)
+{
+ u2 fieldIdx = *ptr;
+ if (!dvmSetBit(pResults->usedFields, fieldIdx)) {
+ LOGE("Unable to mark field %d as in-use\n", fieldIdx);
+ }
+}
+
+/*
+ * Mark a string constant as referenced.
+ */
+static void markString(const u2* ptr, ScanResults* pResults)
+{
+ u2 stringIdx = *ptr;
+ if (!dvmSetBit(pResults->usedStrings, stringIdx)) {
+ LOGE("Unable to mark string %d as in-use\n", stringIdx);
+ }
+}
+
+/*
+ * Mark a "jumbo" string constant as referenced.
+ */
+static void markJumboString(u2* ptr, ScanResults* pResults)
+{
+ u4 stringIdx;
+
+ /* it's in native byte order, but might not be 32-bit aligned */
+ memcpy(&stringIdx, ptr, sizeof(u4));
+ if (!dvmSetBit(pResults->usedStrings, stringIdx)) {
+ LOGE("Unable to mark string %d as in-use\n", stringIdx);
+ }
+}
+
+/*
+ * Remap a value in the instruction stream.
+ */
+static inline void updateValue(u2* ptr, const IndexMapSet* pIndexMapSet,
+ int whichMap)
+{
+ const IndexMap* pMap = &pIndexMapSet->map[whichMap];
+ if (pMap != NULL) {
+ u2 newIdx = pMap->mapToNew[*ptr];
+ assert(newIdx != kNoIndexMapping);
+ *ptr = newIdx;
+ }
+}
+static void updateClass(u2* ptr, const IndexMapSet* pIndexMapSet)
+{
+ updateValue(ptr, pIndexMapSet, kMapClasses);
+}
+static void updateMethod(u2* ptr, const IndexMapSet* pIndexMapSet)
+{
+ updateValue(ptr, pIndexMapSet, kMapMethods);
+}
+static void updateField(u2* ptr, const IndexMapSet* pIndexMapSet)
+{
+ updateValue(ptr, pIndexMapSet, kMapFields);
+}
+static void updateString(u2* ptr, const IndexMapSet* pIndexMapSet)
+{
+ updateValue(ptr, pIndexMapSet, kMapStrings);
+}
+static void updateJumboString(u2* ptr, const IndexMapSet* pIndexMapSet)
+{
+ u4 stringIdx;
+ u4 newIdx;
+
+ /* it's in native byte order, but might not be 32-bit aligned */
+ memcpy(&stringIdx, ptr, sizeof(stringIdx));
+
+ /* get new value */
+ newIdx = pIndexMapSet->map[kMapStrings].mapToNew[*ptr];
+ assert(newIdx != kNoIndexMapping);
+
+ /* copy it out */
+ memcpy(ptr, &newIdx, sizeof(newIdx));
+}
+
+/*
+ * Run through an instructions stream, marking constants as we see them.
+ *
+ * If "pResults" is non-NULL, we populate "pResults" with what we find,
+ * making no changes to the instruction stream.
+ *
+ * If "pIndexMapSet" is non-NULL, we rewrite the constants in the
+ * instruction stream.
+ */
+static void markUsedConstantsFromInsns(u2* insns, u4 insnsSize,
+ ScanResults* pResults, const IndexMapSet* pIndexMapSet)
+{
+ //printf(" %p %u units\n", insns, insnsSize);
+
+ while (insnsSize > 0) {
+ int width;
+ u2* pConst = insns + 1;
+
+ switch (*insns & 0xff) {
+ case OP_IGET:
+ case OP_IGET_WIDE:
+ case OP_IGET_OBJECT:
+ case OP_IGET_BOOLEAN:
+ case OP_IGET_BYTE:
+ case OP_IGET_CHAR:
+ case OP_IGET_SHORT:
+ case OP_IPUT:
+ case OP_IPUT_WIDE:
+ case OP_IPUT_OBJECT:
+ case OP_IPUT_BOOLEAN:
+ case OP_IPUT_BYTE:
+ case OP_IPUT_CHAR:
+ case OP_IPUT_SHORT:
+ case OP_SGET:
+ case OP_SGET_WIDE:
+ case OP_SGET_OBJECT:
+ case OP_SGET_BOOLEAN:
+ case OP_SGET_BYTE:
+ case OP_SGET_CHAR:
+ case OP_SGET_SHORT:
+ case OP_SPUT:
+ case OP_SPUT_WIDE:
+ case OP_SPUT_OBJECT:
+ case OP_SPUT_BOOLEAN:
+ case OP_SPUT_BYTE:
+ case OP_SPUT_CHAR:
+ case OP_SPUT_SHORT:
+ /* instanceop vA, vB, field@CCCC */
+ /* staticop vAA, field@BBBB */
+ if (pResults != NULL)
+ markField(pConst, pResults);
+ else
+ updateField(pConst, pIndexMapSet);
+ break;
+
+ case OP_CONST_STRING:
+ /* const-string vAA, string@BBBB */
+ if (pResults != NULL)
+ markString(pConst, pResults);
+ else
+ updateString(pConst, pIndexMapSet);
+ break;
+
+ case OP_CONST_STRING_JUMBO:
+ /* const-string/jumbo vAA, string@BBBBBBBB */
+ if (pResults != NULL)
+ markJumboString(pConst, pResults);
+ else
+ updateJumboString(pConst, pIndexMapSet);
+ break;
+
+ case OP_CONST_CLASS:
+ case OP_CHECK_CAST:
+ case OP_NEW_INSTANCE:
+ case OP_FILLED_NEW_ARRAY_RANGE:
+ case OP_INSTANCE_OF:
+ case OP_NEW_ARRAY:
+ case OP_FILLED_NEW_ARRAY:
+ /* const-class vAA, type@BBBB */
+ /* check-cast vAA, type@BBBB */
+ /* new-instance vAA, type@BBBB */
+ /* filled-new-array/range {vCCCC .. vNNNN}, type@BBBB */
+ /* instance-of vA, vB, type@CCCC */
+ /* new-array vA, vB, type@CCCC */
+ /* filled-new-array {vD, vE, vF, vG, vA}, type@CCCC */
+ if (pResults != NULL)
+ markClass(pConst, pResults);
+ else
+ updateClass(pConst, pIndexMapSet);
+ break;
+
+ case OP_INVOKE_VIRTUAL:
+ case OP_INVOKE_SUPER:
+ case OP_INVOKE_DIRECT:
+ case OP_INVOKE_STATIC:
+ case OP_INVOKE_INTERFACE:
+ case OP_INVOKE_VIRTUAL_RANGE:
+ case OP_INVOKE_SUPER_RANGE:
+ case OP_INVOKE_DIRECT_RANGE:
+ case OP_INVOKE_STATIC_RANGE:
+ case OP_INVOKE_INTERFACE_RANGE:
+ /* invoke-kind {vD, vE, vF, vG, vA}, meth@CCCC */
+ /* invoke-kind/range {vCCCC .. vNNNN}, meth@BBBB */
+ if (pResults != NULL)
+ markMethod(pConst, pResults);
+ else
+ updateMethod(pConst, pIndexMapSet);
+ break;
+
+ default:
+ // ignore this instruction
+ ;
+ }
+
+ width = dexGetInstrOrTableWidthAbs(gDvm.instrWidth, insns);
+ assert(width > 0 && width <= (int)insnsSize);
+
+ insns += width;
+ insnsSize -= width;
+ }
+}
+
+/*
+ * This is an AllMethodsFunc implementation.
+ *
+ * Run through the instructions in this method, setting bits in the "pResults"
+ * struct as we locate constants.
+ */
+static void markUsedConstants(DexFile* pDexFile, const char* classDescriptor,
+ DexMethod* pDexMethod, void* arg)
+{
+ ScanResults* pResults = (ScanResults*) arg;
+ const DexCode* pDexCode = dexGetCode(pDexFile, pDexMethod);
+
+ if (false) {
+ const DexMethodId* pMethodId;
+ const char* methodName;
+ pMethodId = dexGetMethodId(pDexFile, pDexMethod->methodIdx);
+ methodName = dexStringById(pDexFile, pMethodId->nameIdx);
+ printf(" %s.%s\n", classDescriptor, methodName);
+ }
+
+ if (pDexCode != NULL) {
+ u2* insns = (u2*) pDexCode->insns;
+ u4 insnsSize = pDexCode->insnsSize;
+ markUsedConstantsFromInsns(insns, insnsSize, pResults, NULL);
+ } else {
+ //printf(" (no code)\n");
+ }
+}
+
+/*
+ * This is an AllMethodsFunc implementation.
+ *
+ * Run through the instructions in this method, altering the constants used.
+ */
+static void updateUsedConstants(DexFile* pDexFile, const char* classDescriptor,
+ DexMethod* pDexMethod, void* arg)
+{
+ const IndexMapSet* pIndexMapSet = (const IndexMapSet*) arg;
+ const DexCode* pDexCode = dexGetCode(pDexFile, pDexMethod);
+
+ if (false) {
+ const DexMethodId* pMethodId;
+ const char* methodName;
+ pMethodId = dexGetMethodId(pDexFile, pDexMethod->methodIdx);
+ methodName = dexStringById(pDexFile, pMethodId->nameIdx);
+ printf(" %s.%s\n", classDescriptor, methodName);
+ }
+
+ if (pDexCode != NULL) {
+ u2* insns = (u2*) pDexCode->insns;
+ u4 insnsSize = pDexCode->insnsSize;
+ markUsedConstantsFromInsns(insns, insnsSize, NULL, pIndexMapSet);
+ } else {
+ //printf(" (no code)\n");
+ }
+}
+
+/*
+ * Count up the bits and show a count.
+ */
+static void showBitCount(const char* label, int setCount, int maxCount)
+{
+ printf("%s: %d of %d (%.1f%% unused)\n", label, setCount, maxCount,
+ ((maxCount - setCount) * 100.0f) / maxCount);
+}
+
+/*
+ * Print some debug info.
+ */
+static void summarizeResults(DvmDex* pDvmDex, ScanResults* pResults)
+{
+ DexFile* pDexFile = pDvmDex->pDexFile;
+ int i;
+
+#if 0
+ for (i = 0; i < (int) pDvmDex->pDexFile->pHeader->typeIdsSize; i++) {
+ const DexTypeId* pDexTypeId;
+ const char* classDescr;
+
+ pDexTypeId = dexGetTypeId(pDexFile, i);
+ classDescr = dexStringById(pDexFile, pDexTypeId->descriptorIdx);
+
+ if (dvmIsBitSet(pResults->usedStrings, i))
+ printf("used : %04x '%s'\n", i, classDescr);
+ else
+ printf("unused: %04x '%s'\n", i, classDescr);
+ }
+#endif
+#if 0
+ for (i = 0; i < (int) pDvmDex->pDexFile->pHeader->methodIdsSize; i++) {
+ const DexMethodId* pDexMethodId;
+ const DexTypeId* pDexTypeId;
+ const char* classDescr;
+ const char* methodName;
+
+ pDexMethodId = dexGetMethodId(pDexFile, i);
+ methodName = dexStringById(pDexFile, pDexMethodId->nameIdx);
+
+ pDexTypeId = dexGetTypeId(pDexFile, pDexMethodId->classIdx);
+ classDescr = dexStringById(pDexFile, pDexTypeId->descriptorIdx);
+ if (dvmIsBitSet(pResults->usedMethods, i))
+ printf("used : %s.%s\n", classDescr, methodName);
+ else
+ printf("unused: %s.%s\n", classDescr, methodName);
+ }
+#endif
+#if 0
+ for (i = 0; i < (int) pDvmDex->pDexFile->pHeader->fieldIdsSize; i++) {
+ const DexFieldId* pDexFieldId;
+ const DexTypeId* pDexTypeId;
+ const char* classDescr;
+ const char* fieldName;
+
+ pDexFieldId = dexGetFieldId(pDexFile, i);
+ fieldName = dexStringById(pDexFile, pDexFieldId->nameIdx);
+
+ pDexTypeId = dexGetTypeId(pDexFile, pDexFieldId->classIdx);
+ classDescr = dexStringById(pDexFile, pDexTypeId->descriptorIdx);
+ if (dvmIsBitSet(pResults->usedFields, i))
+ printf("used : %s.%s\n", classDescr, fieldName);
+ else
+ printf("unused: %s.%s\n", classDescr, fieldName);
+ }
+#endif
+#if 0
+ for (i = 0; i < (int) pDvmDex->pDexFile->pHeader->stringIdsSize; i++) {
+ const char* str;
+
+ str = dexStringById(pDexFile, i);
+
+ if (dvmIsBitSet(pResults->usedStrings, i))
+ printf("used : %04x '%s'\n", i, str);
+ else
+ printf("unused: %04x '%s'\n", i, str);
+ }
+#endif
+
+ int totalMax, totalSet;
+ int setCount;
+
+ totalMax = totalSet = 0;
+
+ setCount = dvmCountSetBits(pResults->usedClasses);
+ showBitCount("classes", setCount, pDexFile->pHeader->typeIdsSize);
+ totalSet += setCount;
+ totalMax += pDexFile->pHeader->typeIdsSize;
+
+ setCount = dvmCountSetBits(pResults->usedMethods);
+ showBitCount("methods", setCount, pDexFile->pHeader->methodIdsSize);
+ totalSet += setCount;
+ totalMax += pDexFile->pHeader->methodIdsSize;
+
+ setCount = dvmCountSetBits(pResults->usedFields);
+ showBitCount("fields", setCount, pDexFile->pHeader->fieldIdsSize);
+ totalSet += setCount;
+ totalMax += pDexFile->pHeader->fieldIdsSize;
+
+ setCount = dvmCountSetBits(pResults->usedStrings);
+ showBitCount("strings", setCount, pDexFile->pHeader->stringIdsSize);
+ totalSet += setCount;
+ totalMax += pDexFile->pHeader->stringIdsSize;
+
+ printf("TOTAL %d of %d (%.1f%% unused -- %.1fK)\n", totalSet, totalMax,
+ ((totalMax - totalSet) * 100.0f) / totalMax,
+ (totalMax - totalSet) / 256.0f);
+}
+
+/*
+ * Fill out an index map set entry.
+ *
+ * If we can't fit the map into our base type, we don't create the map.
+ *
+ * Returns "false" if allocation fails.
+ */
+static bool constructIndexMap(int totalCount, const BitVector* pBits,
+ IndexMap* pMap)
+{
+ const int kMaxIndex = 65534; // 65535, a/k/a -1, is special
+ int setCount;
+
+ setCount = dvmCountSetBits(pBits);
+ if (setCount < 0 || setCount > kMaxIndex)
+ return true;
+
+ u2* mapToOld = (u2*) malloc(setCount * sizeof(u2));
+ u2* mapToNew = (u2*) malloc(totalCount * sizeof(u2));
+ if (mapToOld == NULL || mapToNew == NULL) {
+ free(mapToOld);
+ free(mapToNew);
+ return false;
+ }
+
+ /* fill in both arrays */
+ int entry, idx = 0;
+ for (entry = 0; entry < totalCount; entry++) {
+ if (dvmIsBitSet(pBits, entry)) {
+ mapToNew[entry] = idx;
+ mapToOld[idx] = entry;
+ idx++;
+ } else {
+ mapToNew[entry] = kNoIndexMapping;
+ }
+ }
+
+ if (idx != setCount) {
+ LOGE("GLITCH: idx=%d setCount=%d\n", idx, setCount);
+ dvmAbort();
+ }
+
+ /* success */
+ pMap->mapToOld = mapToOld;
+ pMap->mapToNew = mapToNew;
+ pMap->origCount = totalCount;
+ pMap->newCount = setCount;
+
+ return true;
+}
+
+/*
+ * Construct a "reducing" chunk, with maps that convert the constants in
+ * instructions to their reduced value for the cache lookup.
+ */
+static bool constructReducingDataChunk(IndexMapSet* pIndexMapSet)
+{
+ int chunkLen = 0;
+ int i;
+
+ pIndexMapSet->chunkType = kDexChunkReducingIndexMap;
+
+ /*
+ * Compute space requirements and allocate storage.
+ */
+ for (i = 0; i < kNumIndexMaps; i++) {
+ /* space for the "original" count */
+ chunkLen += sizeof(u4);
+
+ /* space for the "reduced" count */
+ chunkLen += sizeof(u4);
+
+ /* add data length, round up to 32-bit boundary */
+ chunkLen += pIndexMapSet->map[i].origCount * sizeof(u2);
+ chunkLen = (chunkLen + 3) & ~3;
+ }
+
+ pIndexMapSet->chunkDataLen = chunkLen;
+ pIndexMapSet->chunkData = (u1*) calloc(1, chunkLen);
+ if (pIndexMapSet->chunkData == NULL)
+ return false;
+
+ /*
+ * Copy the data in.
+ */
+ u1* ptr = pIndexMapSet->chunkData;
+ for (i = 0; i < kNumIndexMaps; i++) {
+ u4* wordPtr = (u4*) ptr;
+ int dataLen = pIndexMapSet->map[i].origCount * sizeof(u2);
+
+ *wordPtr++ = pIndexMapSet->map[i].origCount;
+ *wordPtr++ = pIndexMapSet->map[i].newCount;
+ if (dataLen != 0)
+ memcpy(wordPtr, pIndexMapSet->map[i].mapToNew, dataLen);
+
+ /* advance pointer, maintaining 32-bit alignment */
+ ptr = ((u1*) wordPtr) + dataLen;
+ ptr = (u1*) (((int) ptr + 3) & ~3);
+ }
+
+ if (ptr - (u1*) pIndexMapSet->chunkData != chunkLen) {
+ LOGE("GLITCH: expected len=%d, actual=%d\n",
+ chunkLen, ptr - (u1*) pIndexMapSet->chunkData);
+ dvmAbort();
+ }
+
+ return true;
+}
+
+/*
+ * Construct an "expanding" chunk, with maps that convert instructions
+ * with reduced constants back to their full original values.
+ */
+static bool constructExpandingDataChunk(IndexMapSet* pIndexMapSet)
+{
+ int chunkLen = 0;
+ int i;
+
+ pIndexMapSet->chunkType = kDexChunkExpandingIndexMap;
+
+ /*
+ * Compute space requirements and allocate storage.
+ */
+ for (i = 0; i < kNumIndexMaps; i++) {
+ /* space for the length word */
+ chunkLen += sizeof(u4);
+
+ /* add data length, round up to 32-bit boundary */
+ chunkLen += pIndexMapSet->map[i].newCount * sizeof(u2);
+ chunkLen = (chunkLen + 3) & ~3;
+ }
+
+ pIndexMapSet->chunkDataLen = chunkLen;
+ pIndexMapSet->chunkData = (u1*) calloc(1, chunkLen);
+ if (pIndexMapSet->chunkData == NULL)
+ return false;
+
+ /*
+ * Copy the data in.
+ */
+ u1* ptr = pIndexMapSet->chunkData;
+ for (i = 0; i < kNumIndexMaps; i++) {
+ u4* wordPtr = (u4*) ptr;
+ int dataLen = pIndexMapSet->map[i].newCount * sizeof(u2);
+
+ *wordPtr++ = pIndexMapSet->map[i].newCount;
+ if (dataLen != 0)
+ memcpy(wordPtr, pIndexMapSet->map[i].mapToOld, dataLen);
+
+ /* advance pointer, maintaining 32-bit alignment */
+ ptr = ((u1*) wordPtr) + dataLen;
+ ptr = (u1*) (((int) ptr + 3) & ~3);
+ }
+
+ if (ptr - (u1*) pIndexMapSet->chunkData != chunkLen) {
+ LOGE("GLITCH: expected len=%d, actual=%d\n",
+ chunkLen, ptr - (u1*) pIndexMapSet->chunkData);
+ dvmAbort();
+ }
+
+ return true;
+}
+
+/*
+ * Construct the "chunk" of data that will be appended to the optimized DEX
+ * file.
+ */
+static bool constructDataChunk(IndexMapSet* pIndexMapSet)
+{
+ assert(sizeof(pIndexMapSet->map[0].mapToOld[0]) == sizeof(u2));
+ assert(sizeof(pIndexMapSet->map[0].mapToNew[0]) == sizeof(u2));
+
+#if DVM_RESOLVER_CACHE == DVM_RC_EXPANDING
+ return constructExpandingDataChunk(pIndexMapSet);
+#else
+ return constructReducingDataChunk(pIndexMapSet);
+#endif
+}
+
+/*
+ * Allocate storage to hold the maps.
+ */
+static IndexMapSet* createIndexMapSet(const DexFile* pDexFile,
+ ScanResults* pResults)
+{
+ IndexMapSet* pIndexMapSet;
+ int setCount;
+ bool okay = true;
+
+ pIndexMapSet = calloc(1, sizeof(*pIndexMapSet));
+ if (pIndexMapSet == NULL)
+ return NULL;
+
+ okay = okay && constructIndexMap(pDexFile->pHeader->typeIdsSize,
+ pResults->usedClasses, &pIndexMapSet->map[kMapClasses]);
+ okay = okay && constructIndexMap(pDexFile->pHeader->methodIdsSize,
+ pResults->usedMethods, &pIndexMapSet->map[kMapMethods]);
+ okay = okay && constructIndexMap(pDexFile->pHeader->fieldIdsSize,
+ pResults->usedFields, &pIndexMapSet->map[kMapFields]);
+ okay = okay && constructIndexMap(pDexFile->pHeader->stringIdsSize,
+ pResults->usedStrings, &pIndexMapSet->map[kMapStrings]);
+
+ LOGVV("Constr: %d %d %d %d\n",
+ pIndexMapSet->map[kMapClasses].mapToOld[0],
+ pIndexMapSet->map[kMapMethods].mapToOld[0],
+ pIndexMapSet->map[kMapFields].mapToOld[0],
+ pIndexMapSet->map[kMapStrings].mapToOld[0]);
+
+ okay = okay && constructDataChunk(pIndexMapSet);
+
+ if (!okay) {
+ dvmFreeIndexMapSet(pIndexMapSet);
+ return NULL;
+ }
+
+ return pIndexMapSet;
+}
+
+/*
+ * Free map storage.
+ *
+ * "pIndexMapSet" may be incomplete.
+ */
+void dvmFreeIndexMapSet(IndexMapSet* pIndexMapSet)
+{
+ int i;
+
+ if (pIndexMapSet == NULL)
+ return;
+
+ for (i = 0; i < kNumIndexMaps; i++) {
+ free(pIndexMapSet->map[i].mapToOld);
+ free(pIndexMapSet->map[i].mapToNew);
+ }
+ free(pIndexMapSet->chunkData);
+ free(pIndexMapSet);
+}
+
+/*
+ * Rewrite constant indexes to reduce heap requirements.
+ */
+IndexMapSet* dvmRewriteConstants(DvmDex* pDvmDex)
+{
+#if (DVM_RESOLVER_CACHE != DVM_RC_REDUCING) && \
+ (DVM_RESOLVER_CACHE != DVM_RC_EXPANDING)
+ /* nothing to do */
+ return NULL;
+#endif
+
+ /*
+ * We're looking for instructions that use "constant pool" entries for
+ * classes, methods, fields, and strings. Many field and method entries
+ * are optimized away, and many string constants are never accessed from
+ * code or annotations.
+ */
+ ScanResults* pResults = allocScanResults(pDvmDex->pDexFile);
+ forAllMethods(pDvmDex->pDexFile, markUsedConstants, pResults);
+
+ summarizeResults(pDvmDex, pResults);
+
+ /*
+ * Allocate and populate the index maps.
+ */
+ IndexMapSet* pIndexMapSet = createIndexMapSet(pDvmDex->pDexFile, pResults);
+#if DVM_RESOLVER_CACHE == DVM_RC_EXPANDING
+ if (pIndexMapSet != NULL) {
+ /*
+ * Rewrite the constants to use the reduced set.
+ */
+ forAllMethods(pDvmDex->pDexFile, updateUsedConstants, pIndexMapSet);
+ }
+#endif
+
+ freeScanResults(pResults);
+
+ return pIndexMapSet;
+}
+
diff --git a/vm/analysis/ReduceConstants.h b/vm/analysis/ReduceConstants.h
new file mode 100644
index 0000000..342e125
--- /dev/null
+++ b/vm/analysis/ReduceConstants.h
@@ -0,0 +1,71 @@
+/*
+ * Copyright (C) 2008 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.
+ */
+
+/*
+ * DEX constant-reduction declarations.
+ */
+#ifndef _DALVIK_REDUCECONSTANTS
+#define _DALVIK_REDUCECONSTANTS
+
+#define DVM_RC_DISABLED 0 /* no reduction, 1:1 map */
+#define DVM_RC_REDUCING 1 /* normal constants, reduced lookup table */
+#define DVM_RC_EXPANDING 2 /* reduced constants, expanded on resolve */
+#define DVM_RC_NO_CACHE 3 /* disable the cache (reduce to zero) */
+
+enum {
+ kMapClasses = 0,
+ kMapMethods = 1,
+ kMapFields = 2,
+ kMapStrings = 3,
+
+ kNumIndexMaps
+};
+
+struct DvmDex;
+
+#define kNoIndexMapping ((u2) -1)
+
+/*
+ * Map indices back to the original.
+ */
+typedef struct IndexMap {
+ int origCount; /* original size; describes range of entries in map */
+ int newCount; /* reduced size */
+ u2* mapToNew; /* sparse map, from "orig" to "new" */
+ u2* mapToOld; /* dense map, from "new" back to "orig" */
+} IndexMap;
+typedef struct IndexMapSet {
+ /* maps for the different sections */
+ IndexMap map[kNumIndexMaps];
+
+ /* data stream that gets appended to the optimized DEX file */
+ u4 chunkType;
+ int chunkDataLen;
+ u1* chunkData;
+} IndexMapSet;
+
+/*
+ * Constant pool compaction.
+ *
+ * The caller is responsible for freeing the returned structure by
+ * calling dvmFreeIndexMap().
+ */
+IndexMapSet* dvmRewriteConstants(struct DvmDex* pDvmDex);
+
+/* free an index map set */
+void dvmFreeIndexMapSet(IndexMapSet* indexMapSet);
+
+#endif /*_DALVIK_REDUCECONSTANTS*/