auto import from //branches/cupcake/...@125939
diff --git a/vm/analysis/CodeVerify.c b/vm/analysis/CodeVerify.c
index b4fde5a..0b8a94d 100644
--- a/vm/analysis/CodeVerify.c
+++ b/vm/analysis/CodeVerify.c
@@ -51,6 +51,13 @@
static bool gDebugVerbose = false; // TODO: remove this
+#if 0
+int gDvm__totalInstr = 0;
+int gDvm__gcInstr = 0;
+int gDvm__gcData = 0;
+int gDvm__gcSimpleData = 0;
+#endif
+
/*
* Selectively enable verbose debug logging -- use this to activate
* dumpRegTypes() calls for all instructions in the specified method.
@@ -67,10 +74,6 @@
#define SHOW_REG_DETAILS (0 /*| DRT_SHOW_REF_TYPES | DRT_SHOW_LOCALS*/)
-/* verification failure reporting */
-#define LOG_VFY(...) dvmLogVerifyFailure(NULL, __VA_ARGS__)
-#define LOG_VFY_METH(_meth, ...) dvmLogVerifyFailure(_meth, __VA_ARGS__)
-
/*
* We need an extra "pseudo register" to hold the return type briefly. It
* can be category 1 or 2, so we need two slots.
@@ -87,85 +90,13 @@
typedef u4 RegType;
/*
- * Enumeration for RegType values. The "hi" piece of a 64-bit value MUST
- * immediately follow the "lo" piece in the enumeration, so we can check
- * that hi==lo+1.
- *
- * Assignment of constants:
- * [-MAXINT,-32768) : integer
- * [-32768,-128) : short
- * [-128,0) : byte
- * 0 : zero
- * 1 : one
- * [2,128) : posbyte
- * [128,32768) : posshort
- * [32768,65536) : char
- * [65536,MAXINT] : integer
- *
- * Allowed "implicit" widening conversions:
- * zero -> boolean, posbyte, byte, posshort, short, char, integer, ref (null)
- * one -> boolean, posbyte, byte, posshort, short, char, integer
- * boolean -> posbyte, byte, posshort, short, char, integer
- * posbyte -> posshort, short, integer, char
- * byte -> short, integer
- * posshort -> integer, char
- * short -> integer
- * char -> integer
- *
- * In addition, all of the above can convert to "float".
- *
- * We're more careful with integer values than the spec requires. The
- * motivation is to restrict byte/char/short to the correct range of values.
- * For example, if a method takes a byte argument, we don't want to allow
- * the code to load the constant "1024" and pass it in.
- */
-enum {
- kRegTypeUnknown = 0, /* initial state; use value=0 so calloc works */
- kRegTypeUninit = 1, /* MUST be odd to distinguish from pointer */
- kRegTypeConflict, /* merge clash makes this reg's type unknowable */
-
- /*
- * Category-1nr types. The order of these is chiseled into a couple
- * of tables, so don't add, remove, or reorder if you can avoid it.
- */
-#define kRegType1nrSTART kRegTypeFloat
- kRegTypeFloat,
- kRegTypeZero, /* 32-bit 0, could be Boolean, Int, Float, or Ref */
- kRegTypeOne, /* 32-bit 1, could be Boolean, Int, Float */
- kRegTypeBoolean, /* must be 0 or 1 */
- kRegTypePosByte, /* byte, known positive (can become char) */
- kRegTypeByte,
- kRegTypePosShort, /* short, known positive (can become char) */
- kRegTypeShort,
- kRegTypeChar,
- kRegTypeInteger,
-#define kRegType1nrEND kRegTypeInteger
-
- kRegTypeLongLo, /* lower-numbered register; endian-independent */
- kRegTypeLongHi,
- kRegTypeDoubleLo,
- kRegTypeDoubleHi,
-
- /*
- * Anything larger than this is a ClassObject or uninit ref. Mask off
- * all but the low 8 bits; if you're left with kRegTypeUninit, pull
- * the uninit index out of the high 24. Because kRegTypeUninit has an
- * odd value, there is no risk of a particular ClassObject pointer bit
- * pattern being confused for it (assuming our class object allocator
- * uses word alignment).
- */
- kRegTypeMAX
-};
-#define kRegTypeUninitMask 0xff
-#define kRegTypeUninitShift 8
-
-/*
* Big fat collection of registers.
*/
typedef struct RegisterTable {
/*
- * Array of RegType pointers, one per address in the method. We only
- * set the pointers for addresses that are branch targets.
+ * Array of RegType arrays, one per address in the method. We only
+ * set the pointers for addresses that are branch targets unless
+ * USE_FULL_TABLE is true.
*/
RegType** addrRegs;
@@ -176,7 +107,7 @@
int insnRegCount;
/*
- * A single large alloc, with all of the storage needed for insnRegs.
+ * A single large alloc, with all of the storage needed for addrRegs.
*/
RegType* regAlloc;
} RegisterTable;
@@ -185,8 +116,6 @@
/* 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,\
@@ -234,7 +163,8 @@
#define _d kRegTypeDoubleHi
/*
- * Merge result table. The table is symmetric along the diagonal.
+ * Merge result table for primitive values. The table is symmetric along
+ * the diagonal.
*
* Note that 32-bit int/float do not merge into 64-bit long/double. This
* is a register merge, not a widening conversion. Only the "implicit"
@@ -252,7 +182,7 @@
* transitions from "unknown" to "known" is when we're executing code
* for the first time, and we handle that with a simple copy.
*/
-static const /*RegType*/ char gMergeTab[kRegTypeMAX][kRegTypeMAX] =
+const char gDvmMergeTab[kRegTypeMAX][kRegTypeMAX] =
{
/* chk: _ U X F 0 1 Z b B s S C I J j D d */
{ /*_*/ __,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X },
@@ -302,7 +232,7 @@
for (i = 0; i < kRegTypeMAX; i++) {
for (j = i; j < kRegTypeMAX; j++) {
- if (gMergeTab[i][j] != gMergeTab[j][i]) {
+ if (gDvmMergeTab[i][j] != gDvmMergeTab[j][i]) {
LOGE("Symmetry violation: %d,%d vs %d,%d\n", i, j, j, i);
dvmAbort();
}
@@ -1787,7 +1717,8 @@
* Find the start of the register set for the specified instruction in
* the current method.
*/
-static RegType* getRegisterLine(const RegisterTable* regTable, int insnIdx)
+static inline RegType* getRegisterLine(const RegisterTable* regTable,
+ int insnIdx)
{
return regTable->addrRegs[insnIdx];
}
@@ -1803,6 +1734,9 @@
/*
* Compare a bunch of registers.
+ *
+ * Returns 0 if they match. Using this for a sort is unwise, since the
+ * value can change based on machine endianness.
*/
static inline int compareRegisters(const RegType* src1, const RegType* src2,
int numRegs)
@@ -2279,7 +2213,7 @@
/*
* Merge two RegType values.
*
- * Sets "pChanged" to "true" if the result doesn't match "type1".
+ * Sets "*pChanged" to "true" if the result doesn't match "type1".
*/
static RegType mergeTypes(RegType type1, RegType type2, bool* pChanged)
{
@@ -2301,7 +2235,7 @@
*/
if (type1 < kRegTypeMAX) {
if (type2 < kRegTypeMAX) {
- result = gMergeTab[type1][type2];
+ result = gDvmMergeTab[type1][type2];
} else {
/* simple + reference == conflict, usually */
if (type1 == kRegTypeZero)
@@ -2344,7 +2278,7 @@
* Control can transfer to "nextInsn".
*
* Merge the registers from "workRegs" into "regTypes" at "nextInsn", and
- * set the "changed" flag if the registers have changed.
+ * set the "changed" flag on the target address if the registers have changed.
*/
static void updateRegisters(const Method* meth, InsnFlags* insnFlags,
RegisterTable* regTable, int nextInsn, const RegType* workRegs)
@@ -2404,103 +2338,6 @@
*/
/*
- * Output a code verifier warning message. For the pre-verifier it's not
- * a big deal if something fails (and it may even be expected), but if
- * we're doing just-in-time verification it's significant.
- */
-void dvmLogVerifyFailure(const Method* meth, const char* format, ...)
-{
- va_list ap;
- int logLevel;
-
- 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);
- if (meth != NULL) {
- char* desc = dexProtoCopyMethodDescriptor(&meth->prototype);
- LOG_PRI(logLevel, LOG_TAG, "VFY: rejected %s.%s %s\n",
- meth->clazz->descriptor, meth->name, desc);
- free(desc);
- }
-}
-
-/*
- * 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).
- */
-bool dvmGetBranchTarget(const Method* meth, InsnFlags* insnFlags,
- int curOffset, int* pOffset, bool* pConditional)
-{
- const u2* insns = meth->insns + curOffset;
- int tmp;
-
- switch (*insns & 0xff) {
- case OP_GOTO:
- *pOffset = ((s2) *insns) >> 8;
- *pConditional = false;
- break;
- case OP_GOTO_32:
- *pOffset = insns[1] | (((u4) insns[2]) << 16);
- *pConditional = false;
- break;
- case OP_GOTO_16:
- *pOffset = (s2) insns[1];
- *pConditional = false;
- break;
- case OP_IF_EQ:
- case OP_IF_NE:
- case OP_IF_LT:
- case OP_IF_GE:
- case OP_IF_GT:
- case OP_IF_LE:
- case OP_IF_EQZ:
- case OP_IF_NEZ:
- case OP_IF_LTZ:
- case OP_IF_GEZ:
- case OP_IF_GTZ:
- case OP_IF_LEZ:
- *pOffset = (s2) insns[1];
- *pConditional = true;
- break;
- default:
- return false;
- break;
- }
-
- return true;
-}
-
-
-/*
* Look up an instance field, specified by "fieldIdx", that is going to be
* accessed in object "objType". This resolves the field and then verifies
* that the class containing the field is an instance of the reference in
@@ -2626,7 +2463,18 @@
/* make sure we're in the right kind of constructor */
if (dvmIsStaticField(field)) {
- if (!isClassInitMethod(meth)) {
+ /*
+ * The EMMA code coverage tool generates a static method that
+ * modifies a private static final field. The method is only
+ * called by <clinit>, so the code is reasonable if not quite
+ * kosher. (Attempting to *compile* code that does something
+ * like that will earn you a quick thumbs-down from javac.)
+ *
+ * The verifier in another popular VM doesn't complain about this,
+ * so we're going to allow classes to modify their own static
+ * final fields outside of class initializers.
+ */
+ if (false && !isClassInitMethod(meth)) {
LOG_VFY_METH(meth,
"VFY: can't modify final static field outside <clinit>\n");
*pOkay = false;
@@ -2793,9 +2641,6 @@
* what's in which register, but for verification purposes we only need to
* store it at branch target addresses (because we merge into that).
*
- * If we need to generate tables describing reference type usage for
- * "exact gc", we will need to save the complete set.
- *
* By zeroing out the storage we are effectively initializing the register
* information to kRegTypeUnknown.
*/
@@ -2940,14 +2785,8 @@
goto bail;
/*
- * Success. Reduce regTypes to a compact bitmap representation for the
- * benefit of exact GC.
- *
- * (copy to LinearAlloc area? after verify, DexOpt gathers up all the
- * successful ones and generates a new section in the DEX file so we
- * can see who got verified)
+ * Success.
*/
-
result = true;
bail:
@@ -3100,7 +2939,6 @@
compareRegisters(workRegs, insnRegs,
meth->registersSize + kExtraRegs) != 0)
{
- int ii;
char* desc = dexProtoCopyMethodDescriptor(&meth->prototype);
LOG_VFY("HUH? workRegs diverged in %s.%s %s\n",
meth->clazz->descriptor, meth->name, desc);
@@ -3122,6 +2960,43 @@
goto bail;
}
+#if 0
+ {
+ static const int gcMask = kInstrCanBranch | kInstrCanSwitch |
+ kInstrCanThrow | kInstrCanReturn;
+ OpCode opCode = *(meth->insns + insnIdx) & 0xff;
+ int flags = dexGetInstrFlags(gDvm.instrFlags, opCode);
+
+ /* 8, 16, 32, or 32*n -bit regs */
+ int regWidth = (meth->registersSize + 7) / 8;
+ if (regWidth == 3)
+ regWidth = 4;
+ if (regWidth > 4) {
+ regWidth = ((regWidth + 3) / 4) * 4;
+ if (false) {
+ LOGW("WOW: %d regs -> %d %s.%s\n",
+ meth->registersSize, regWidth,
+ meth->clazz->descriptor, meth->name);
+ //x = true;
+ }
+ }
+
+ if ((flags & gcMask) != 0) {
+ /* this is a potential GC point */
+ gDvm__gcInstr++;
+
+ if (insnsSize < 256)
+ gDvm__gcData += 1;
+ else
+ gDvm__gcData += 2;
+ gDvm__gcData += regWidth;
+ }
+ gDvm__gcSimpleData += regWidth;
+
+ gDvm__totalInstr++;
+ }
+#endif
+
/*
* Clear "changed" and mark as visited.
*/
@@ -3224,7 +3099,7 @@
* We can also return, in which case there is no successor instruction
* from this point.
*
- * The behavior is determined by the InstrFlags.
+ * The behavior can be determined from the InstrFlags.
*/
const DexFile* pDexFile = meth->clazz->pDvmDex->pDexFile;
@@ -3482,7 +3357,7 @@
resClass = dvmOptResolveClass(meth->clazz, decInsn.vB);
if (resClass == NULL) {
const char* badClassDesc = dexStringByTypeIdx(pDexFile, decInsn.vB);
- logUnableToResolveClass(badClassDesc, meth);
+ dvmLogUnableToResolveClass(badClassDesc, meth);
LOG_VFY("VFY: unable to resolve check-cast %d (%s) in %s\n",
decInsn.vB, badClassDesc, meth->clazz->descriptor);
okay = false;
@@ -3540,7 +3415,7 @@
resClass = dvmOptResolveClass(meth->clazz, decInsn.vB);
if (resClass == NULL) {
const char* badClassDesc = dexStringByTypeIdx(pDexFile, decInsn.vB);
- logUnableToResolveClass(badClassDesc, meth);
+ dvmLogUnableToResolveClass(badClassDesc, meth);
LOG_VFY("VFY: unable to resolve new-instance %d (%s) in %s\n",
decInsn.vB, badClassDesc, meth->clazz->descriptor);
okay = false;
@@ -3568,7 +3443,7 @@
resClass = dvmOptResolveClass(meth->clazz, decInsn.vC);
if (resClass == NULL) {
const char* badClassDesc = dexStringByTypeIdx(pDexFile, decInsn.vB);
- logUnableToResolveClass(badClassDesc, meth);
+ dvmLogUnableToResolveClass(badClassDesc, meth);
LOG_VFY("VFY: unable to resolve new-array %d (%s) in %s\n",
decInsn.vC, badClassDesc, meth->clazz->descriptor);
okay = false;
@@ -3587,7 +3462,7 @@
resClass = dvmOptResolveClass(meth->clazz, decInsn.vB);
if (resClass == NULL) {
const char* badClassDesc = dexStringByTypeIdx(pDexFile, decInsn.vB);
- logUnableToResolveClass(badClassDesc, meth);
+ dvmLogUnableToResolveClass(badClassDesc, meth);
LOG_VFY("VFY: unable to resolve filled-array %d (%s) in %s\n",
decInsn.vB, badClassDesc, meth->clazz->descriptor);
okay = false;
@@ -5271,7 +5146,7 @@
if ((nextFlags & kInstrCanContinue) != 0) {
*pStartGuess = insnIdx + dvmInsnGetWidth(insnFlags, insnIdx);
} else if ((nextFlags & kInstrCanBranch) != 0) {
- /* okay if branchTarget is zero */
+ /* we're still okay if branchTarget is zero */
*pStartGuess = insnIdx + branchTarget;
}
diff --git a/vm/analysis/CodeVerify.h b/vm/analysis/CodeVerify.h
index ad93897..487acfb 100644
--- a/vm/analysis/CodeVerify.h
+++ b/vm/analysis/CodeVerify.h
@@ -13,28 +13,93 @@
* See the License for the specific language governing permissions and
* limitations under the License.
*/
+
/*
* Dalvik bytecode verifier.
*/
#ifndef _DALVIK_CODEVERIFY
#define _DALVIK_CODEVERIFY
+#include "analysis/VerifySubs.h"
+
/*
- * InsnFlags is a 32-bit integer with the following layout:
- * 0-15 instruction length (or 0 if this address doesn't hold an opcode)
- * 16 opcode flag (indicating this address holds an opcode)
- * 17 try block (indicating exceptions thrown here may be caught locally)
- * 30 visited (verifier has examined this instruction at least once)
- * 31 changed (set/cleared as bytecode verifier runs)
+ * Enumeration for register type values. The "hi" piece of a 64-bit value
+ * MUST immediately follow the "lo" piece in the enumeration, so we can check
+ * that hi==lo+1.
+ *
+ * Assignment of constants:
+ * [-MAXINT,-32768) : integer
+ * [-32768,-128) : short
+ * [-128,0) : byte
+ * 0 : zero
+ * 1 : one
+ * [2,128) : posbyte
+ * [128,32768) : posshort
+ * [32768,65536) : char
+ * [65536,MAXINT] : integer
+ *
+ * Allowed "implicit" widening conversions:
+ * zero -> boolean, posbyte, byte, posshort, short, char, integer, ref (null)
+ * one -> boolean, posbyte, byte, posshort, short, char, integer
+ * boolean -> posbyte, byte, posshort, short, char, integer
+ * posbyte -> posshort, short, integer, char
+ * byte -> short, integer
+ * posshort -> integer, char
+ * short -> integer
+ * char -> integer
+ *
+ * In addition, all of the above can convert to "float".
+ *
+ * We're more careful with integer values than the spec requires. The
+ * motivation is to restrict byte/char/short to the correct range of values.
+ * For example, if a method takes a byte argument, we don't want to allow
+ * the code to load the constant "1024" and pass it in.
*/
-typedef u4 InsnFlags;
+enum {
+ kRegTypeUnknown = 0, /* initial state; use value=0 so calloc works */
+ kRegTypeUninit = 1, /* MUST be odd to distinguish from pointer */
+ kRegTypeConflict, /* merge clash makes this reg's type unknowable */
-#define kInsnFlagWidthMask 0x0000ffff
-#define kInsnFlagInTry (1 << 16)
-#define kInsnFlagBranchTarget (1 << 17)
-#define kInsnFlagVisited (1 << 30)
-#define kInsnFlagChanged (1 << 31)
+ /*
+ * Category-1nr types. The order of these is chiseled into a couple
+ * of tables, so don't add, remove, or reorder if you can avoid it.
+ */
+#define kRegType1nrSTART kRegTypeFloat
+ kRegTypeFloat,
+ kRegTypeZero, /* 32-bit 0, could be Boolean, Int, Float, or Ref */
+ kRegTypeOne, /* 32-bit 1, could be Boolean, Int, Float */
+ kRegTypeBoolean, /* must be 0 or 1 */
+ kRegTypePosByte, /* byte, known positive (can become char) */
+ kRegTypeByte,
+ kRegTypePosShort, /* short, known positive (can become char) */
+ kRegTypeShort,
+ kRegTypeChar,
+ kRegTypeInteger,
+#define kRegType1nrEND kRegTypeInteger
+
+ kRegTypeLongLo, /* lower-numbered register; endian-independent */
+ kRegTypeLongHi,
+ kRegTypeDoubleLo,
+ kRegTypeDoubleHi,
+
+ /*
+ * Enumeration max; this is used with "full" (32-bit) RegType values.
+ *
+ * Anything larger than this is a ClassObject or uninit ref. Mask off
+ * all but the low 8 bits; if you're left with kRegTypeUninit, pull
+ * the uninit index out of the high 24. Because kRegTypeUninit has an
+ * odd value, there is no risk of a particular ClassObject pointer bit
+ * pattern being confused for it (assuming our class object allocator
+ * uses word alignment).
+ */
+ kRegTypeMAX
+};
+#define kRegTypeUninitMask 0xff
+#define kRegTypeUninitShift 8
+
+extern const char gDvmMergeTab[kRegTypeMAX][kRegTypeMAX];
+
/*
* Returns "true" if the flags indicate that this address holds the start
@@ -117,6 +182,22 @@
// insnFlags[addr] &= ~kInsnFlagBranchTarget;
}
+/*
+ * Instruction is a GC point?
+ */
+INLINE bool dvmInsnIsGcPoint(const InsnFlags* insnFlags, int addr) {
+ return (insnFlags[addr] & kInsnFlagGcPoint) != 0;
+}
+INLINE void dvmInsnSetGcPoint(InsnFlags* insnFlags, int addr,
+ bool isBranch)
+{
+ assert(isBranch);
+ //if (isBranch)
+ insnFlags[addr] |= kInsnFlagGcPoint;
+ //else
+ // insnFlags[addr] &= ~kInsnFlagGcPoint;
+}
+
/*
* Table that maps uninitialized instances to classes, based on the
@@ -149,14 +230,14 @@
* different class is already associated with the address (shouldn't
* happen either).
*/
-int dvmSetUninitInstance(UninitInstanceMap* uninitMap, int addr,
- ClassObject* clazz);
+//int dvmSetUninitInstance(UninitInstanceMap* uninitMap, int addr,
+// ClassObject* clazz);
/*
* Return the class associated with an uninitialized reference. Pass in
* the map index.
*/
-ClassObject* dvmGetUninitInstance(const UninitInstanceMap* uninitMap, int idx);
+//ClassObject* dvmGetUninitInstance(const UninitInstanceMap* uninitMap, int idx);
/*
* Clear the class associated with an uninitialized reference. Pass in
@@ -172,15 +253,4 @@
bool dvmVerifyCodeFlow(const Method* meth, InsnFlags* insnFlags,
UninitInstanceMap* uninitMap);
-/*
- * Log standard method info for rejection message.
- */
-void dvmLogVerifyFailure(const Method* meth, const char* format, ...);
-
-/*
- * Extract the relative branch target from a branch instruction.
- */
-bool dvmGetBranchTarget(const Method* meth, InsnFlags* insnFlags,
- int curOffset, int* pOffset, bool* pConditional);
-
#endif /*_DALVIK_CODEVERIFY*/
diff --git a/vm/analysis/DexVerify.c b/vm/analysis/DexVerify.c
index 3b69e83..f78133b 100644
--- a/vm/analysis/DexVerify.c
+++ b/vm/analysis/DexVerify.c
@@ -20,20 +20,9 @@
*/
#include "Dalvik.h"
#include "analysis/CodeVerify.h"
-#include "libdex/DexCatch.h"
-#include "libdex/InstrUtils.h"
-
-//#define static
-
-/* verification failure reporting */
-#define LOG_VFY(...) dvmLogVerifyFailure(NULL, __VA_ARGS__);
-#define LOG_VFY_METH(_meth, ...) dvmLogVerifyFailure(_meth, __VA_ARGS__);
/* fwd */
-static bool computeCodeWidths(const Method* meth, InsnFlags* insnFlags,\
- int* pNewInstanceCount);
-static bool setTryFlags(const Method* meth, InsnFlags* insnFlags);
static bool verifyMethod(Method* meth, int verifyFlags);
static bool verifyInstructions(const Method* meth, InsnFlags* insnFlags,
int verifyFlags);
@@ -223,7 +212,7 @@
* Count up the #of occurrences of new-instance instructions while we're
* at it.
*/
- if (!computeCodeWidths(meth, insnFlags, &newInstanceCount))
+ if (!dvmComputeCodeWidths(meth, insnFlags, &newInstanceCount))
goto bail;
/*
@@ -236,7 +225,7 @@
/*
* Set the "in try" flags for all instructions guarded by a "try" block.
*/
- if (!setTryFlags(meth, insnFlags))
+ if (!dvmSetTryFlags(meth, insnFlags))
goto bail;
/*
@@ -269,263 +258,6 @@
/*
- * Compute the width of the instruction at each address in the instruction
- * stream. Addresses that are in the middle of an instruction, or that
- * are part of switch table data, are not set (so the caller should probably
- * initialize "insnFlags" to zero).
- *
- * Logs an error and returns "false" on failure.
- */
-static bool computeCodeWidths(const Method* meth, InsnFlags* insnFlags,
- int* pNewInstanceCount)
-{
- const int insnCount = dvmGetMethodInsnsSize(meth);
- const u2* insns = meth->insns;
- bool result = false;
- int i;
-
- *pNewInstanceCount = 0;
-
- for (i = 0; i < insnCount; /**/) {
- int width;
-
- /*
- * 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;
- } else if (*insns == kArrayDataSignature) {
- u4 size = insns[2] | (((u4)insns[3]) << 16);
- width = 4 + (insns[1] * size + 1) / 2;
- } else {
- int instr = *insns & 0xff;
- width = dexGetInstrWidthAbs(gDvm.instrWidth, instr);
- if (width == 0) {
- LOG_VFY_METH(meth,
- "VFY: invalid post-opt instruction (0x%x)\n", instr);
- goto bail;
- }
- if (width < 0 || width > 5) {
- LOGE("VFY: bizarre width value %d\n", width);
- dvmAbort();
- }
-
- if (instr == OP_NEW_INSTANCE)
- (*pNewInstanceCount)++;
- }
-
- if (width > 65535) {
- LOG_VFY_METH(meth, "VFY: insane width %d\n", width);
- goto bail;
- }
-
- insnFlags[i] |= width;
- i += width;
- insns += width;
- }
- if (i != (int) dvmGetMethodInsnsSize(meth)) {
- LOG_VFY_METH(meth, "VFY: code did not end where expected (%d vs. %d)\n",
- i, dvmGetMethodInsnsSize(meth));
- goto bail;
- }
-
- result = true;
-
-bail:
- return result;
-}
-
-/*
- * Set the "in try" flags for all instructions protected by "try" statements.
- * Also sets the "branch target" flags for exception handlers.
- *
- * Call this after widths have been set in "insnFlags".
- *
- * Returns "false" if something in the exception table looks fishy, but
- * we're expecting the exception table to be somewhat sane.
- */
-static bool setTryFlags(const Method* meth, InsnFlags* insnFlags)
-{
- u4 insnsSize = dvmGetMethodInsnsSize(meth);
- DexFile* pDexFile = meth->clazz->pDvmDex->pDexFile;
- const DexCode* pCode = dvmGetMethodCode(meth);
- u4 triesSize = pCode->triesSize;
- const DexTry* pTries;
- u4 handlersSize;
- u4 offset;
- u4 i;
-
- if (triesSize == 0) {
- return true;
- }
-
- pTries = dexGetTries(pCode);
- handlersSize = dexGetHandlersSize(pCode);
-
- for (i = 0; i < triesSize; i++) {
- const DexTry* pTry = &pTries[i];
- u4 start = pTry->startAddr;
- u4 end = start + pTry->insnCount;
- u4 addr;
-
- if ((start >= end) || (start >= insnsSize) || (end > insnsSize)) {
- LOG_VFY_METH(meth,
- "VFY: bad exception entry: startAddr=%d endAddr=%d (size=%d)\n",
- start, end, insnsSize);
- return false;
- }
-
- if (dvmInsnGetWidth(insnFlags, start) == 0) {
- LOG_VFY_METH(meth,
- "VFY: 'try' block starts inside an instruction (%d)\n",
- start);
- return false;
- }
-
- for (addr = start; addr < end;
- addr += dvmInsnGetWidth(insnFlags, addr))
- {
- assert(dvmInsnGetWidth(insnFlags, addr) != 0);
- dvmInsnSetInTry(insnFlags, addr, true);
- }
- }
-
- /* Iterate over each of the handlers to verify target addresses. */
- offset = dexGetFirstHandlerOffset(pCode);
- for (i = 0; i < handlersSize; i++) {
- DexCatchIterator iterator;
- dexCatchIteratorInit(&iterator, pCode, offset);
-
- for (;;) {
- DexCatchHandler* handler = dexCatchIteratorNext(&iterator);
- u4 addr;
-
- if (handler == NULL) {
- break;
- }
-
- addr = handler->address;
- if (dvmInsnGetWidth(insnFlags, addr) == 0) {
- LOG_VFY_METH(meth,
- "VFY: exception handler starts at bad address (%d)\n",
- addr);
- return false;
- }
-
- dvmInsnSetBranchTarget(insnFlags, addr, true);
- }
-
- offset = dexCatchIteratorGetEndOffset(&iterator, pCode);
- }
-
- return true;
-}
-
-/*
- * Verify a switch table. "curOffset" is the offset of the switch
- * instruction.
- */
-static bool checkSwitchTargets(const Method* meth, InsnFlags* insnFlags,
- int curOffset)
-{
- const int insnCount = dvmGetMethodInsnsSize(meth);
- const u2* insns = meth->insns + curOffset;
- const u2* switchInsns;
- int switchCount, tableSize;
- int offsetToSwitch, offsetToKeys, offsetToTargets, targ;
- int offset, absOffset;
-
- assert(curOffset >= 0 && curOffset < insnCount);
-
- /* make sure the start of the switch is in range */
- offsetToSwitch = (s2) insns[1];
- if (curOffset + offsetToSwitch < 0 ||
- curOffset + offsetToSwitch + 2 >= insnCount)
- {
- LOG_VFY_METH(meth,
- "VFY: invalid switch start: at %d, switch offset %d, count %d\n",
- curOffset, offsetToSwitch, insnCount);
- return false;
- }
-
- /* offset to switch table is a relative branch-style offset */
- switchInsns = insns + offsetToSwitch;
-
- /* make sure the table is 32-bit aligned */
- if ((((u4) switchInsns) & 0x03) != 0) {
- LOG_VFY_METH(meth,
- "VFY: unaligned switch table: at %d, switch offset %d\n",
- curOffset, offsetToSwitch);
- return false;
- }
-
- switchCount = switchInsns[1];
-
- if ((*insns & 0xff) == OP_PACKED_SWITCH) {
- /* 0=sig, 1=count, 2/3=firstKey */
- offsetToTargets = 4;
- offsetToKeys = -1;
- } else {
- /* 0=sig, 1=count, 2..count*2 = keys */
- offsetToKeys = 2;
- offsetToTargets = 2 + 2*switchCount;
- }
- tableSize = offsetToTargets + switchCount*2;
-
- /* make sure the end of the switch is in range */
- if (curOffset + offsetToSwitch + tableSize > insnCount) {
- LOG_VFY_METH(meth,
- "VFY: invalid switch end: at %d, switch offset %d, end %d, count %d\n",
- curOffset, offsetToSwitch, curOffset + offsetToSwitch + tableSize,
- insnCount);
- return false;
- }
-
- /* 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++) {
- s4 key = (s4) switchInsns[offsetToKeys + targ*2] |
- (s4) (switchInsns[offsetToKeys + targ*2 +1] << 16);
- if (key <= lastKey) {
- LOG_VFY_METH(meth,
- "VFY: invalid packed switch: last key=%d, this=%d\n",
- lastKey, key);
- return false;
- }
-
- lastKey = key;
- }
- }
-
- /* verify each switch target */
- for (targ = 0; targ < switchCount; targ++) {
- offset = (s4) switchInsns[offsetToTargets + targ*2] |
- (s4) (switchInsns[offsetToTargets + targ*2 +1] << 16);
- absOffset = curOffset + offset;
-
- if (absOffset < 0 || absOffset >= insnCount ||
- !dvmInsnIsOpcode(insnFlags, absOffset))
- {
- LOG_VFY_METH(meth,
- "VFY: invalid switch target %d (-> 0x%x) at 0x%x[%d]\n",
- offset, absOffset, curOffset, targ);
- return false;
- }
- dvmInsnSetBranchTarget(insnFlags, absOffset, true);
- }
-
- return true;
-}
-
-/*
* Verify an array data table. "curOffset" is the offset of the fill-array-data
* instruction.
*/
@@ -580,58 +312,6 @@
return true;
}
-/*
- * Verify that the target of a branch instruction is valid.
- *
- * We don't expect code to jump directly into an exception handler, but
- * it's valid to do so as long as the target isn't a "move-exception"
- * instruction. We verify that in a later stage.
- *
- * The VM spec doesn't forbid an instruction from branching to itself,
- * but the Dalvik spec declares that only certain instructions can do so.
- */
-static bool checkBranchTarget(const Method* meth, InsnFlags* insnFlags,
- int curOffset, bool selfOkay)
-{
- const int insnCount = dvmGetMethodInsnsSize(meth);
- const u2* insns = meth->insns + curOffset;
- int offset, absOffset;
- bool isConditional;
-
- if (!dvmGetBranchTarget(meth, insnFlags, curOffset, &offset,
- &isConditional))
- return false;
-
- if (!selfOkay && offset == 0) {
- LOG_VFY_METH(meth, "VFY: branch offset of zero not allowed at 0x%x\n",
- curOffset);
- return false;
- }
-
- /*
- * Check for 32-bit overflow. This isn't strictly necessary if we can
- * depend on the VM to have identical "wrap-around" behavior, but
- * it's unwise to depend on that.
- */
- if (((s8) curOffset + (s8) offset) != (s8)(curOffset + offset)) {
- LOG_VFY_METH(meth, "VFY: branch target overflow 0x%x +%d\n",
- curOffset, offset);
- return false;
- }
- absOffset = curOffset + offset;
- if (absOffset < 0 || absOffset >= insnCount ||
- !dvmInsnIsOpcode(insnFlags, absOffset))
- {
- LOG_VFY_METH(meth,
- "VFY: invalid branch target %d (-> 0x%x) at 0x%x\n",
- offset, absOffset, curOffset);
- return false;
- }
- dvmInsnSetBranchTarget(insnFlags, absOffset, true);
-
- return true;
-}
-
/*
* Decode the current instruction.
@@ -864,7 +544,7 @@
case OP_PACKED_SWITCH:
case OP_SPARSE_SWITCH:
/* verify the associated table */
- if (!checkSwitchTargets(meth, insnFlags, i))
+ if (!dvmCheckSwitchTargets(meth, insnFlags, i))
return false;
break;
@@ -889,12 +569,12 @@
case OP_IF_GTZ:
case OP_IF_LEZ:
/* check the destination */
- if (!checkBranchTarget(meth, insnFlags, i, false))
+ if (!dvmCheckBranchTarget(meth, insnFlags, i, false))
return false;
break;
case OP_GOTO_32:
/* check the destination; self-branch is okay */
- if (!checkBranchTarget(meth, insnFlags, i, true))
+ if (!dvmCheckBranchTarget(meth, insnFlags, i, true))
return false;
break;
@@ -1007,3 +687,4 @@
return true;
}
+
diff --git a/vm/analysis/DexVerify.h b/vm/analysis/DexVerify.h
index ceaf6e0..4b0d693 100644
--- a/vm/analysis/DexVerify.h
+++ b/vm/analysis/DexVerify.h
@@ -13,6 +13,7 @@
* See the License for the specific language governing permissions and
* limitations under the License.
*/
+
/*
* Dalvik classfile verification.
*/
diff --git a/vm/analysis/RegisterMap.c b/vm/analysis/RegisterMap.c
new file mode 100644
index 0000000..8e0054e
--- /dev/null
+++ b/vm/analysis/RegisterMap.c
@@ -0,0 +1,778 @@
+/*
+ * 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.
+ */
+
+/*
+ * This code generate "register maps" for Dalvik bytecode. In a stack-based
+ * VM we would call these "stack maps". They are used to increase the
+ * precision in the garbage collector when finding references in the
+ * interpreter call stack.
+ */
+#include "Dalvik.h"
+#include "analysis/CodeVerify.h"
+#include "analysis/RegisterMap.h"
+#include "libdex/DexCatch.h"
+#include "libdex/InstrUtils.h"
+
+
+/*
+Notes on RegisterMap vs. verification
+
+Much of this is redundant with the bytecode verifier. Unfortunately we
+can't do this at verification time unless we're willing to store the
+results in the optimized DEX file, which increases their size by about 25%
+unless we use compression, and for performance reasons we don't want to
+just re-run the verifier.
+
+Both type-precise and live-precise information can be generated knowing
+only whether or not a register holds a reference. We don't need to
+know what kind of reference or whether the object has been initialized.
+Not only can we skip many of the fancy steps in the verifier, we can
+initialize from simpler sources, e.g. the initial registers and return
+type are set from the "shorty" signature rather than the full signature.
+
+The short-term storage needs are different; for example, the verifier
+stores 4-byte RegType values for every address that can be a branch
+target, while we store 1-byte SRegType values for every address that
+can be a GC point. There are many more GC points than branch targets.
+We could use a common data type here, but for larger methods it can mean
+the difference between 300KB and 1.2MB.
+
+*/
+
+/*
+ * This is like RegType in the verifier, but simplified. It holds a value
+ * from the reg type enum, or kRegTypeReference.
+ */
+typedef u1 SRegType;
+#define kRegTypeReference kRegTypeMAX
+
+/*
+ * We need an extra "pseudo register" to hold the return type briefly. It
+ * can be category 1 or 2, so we need two slots.
+ */
+#define kExtraRegs 2
+#define RESULT_REGISTER(_insnRegCount) (_insnRegCount)
+
+/*
+ * Working state.
+ */
+typedef struct WorkState {
+ /*
+ * The method we're working on.
+ */
+ const Method* method;
+
+ /*
+ * Number of instructions in the method.
+ */
+ int insnsSize;
+
+ /*
+ * Number of registers we track for each instruction. This is equal
+ * to the method's declared "registersSize" plus kExtraRegs.
+ */
+ int insnRegCount;
+
+ /*
+ * Instruction widths and flags, one entry per code unit.
+ */
+ InsnFlags* insnFlags;
+
+ /*
+ * Array of SRegType arrays, one entry per code unit. We only need
+ * to create an entry when an instruction starts at this address.
+ * We can further reduce this to instructions that are GC points.
+ *
+ * We could just go ahead and allocate one per code unit, but for
+ * larger methods that can represent a significant bit of short-term
+ * storage.
+ */
+ SRegType** addrRegs;
+
+ /*
+ * A single large alloc, with all of the storage needed for addrRegs.
+ */
+ SRegType* regAlloc;
+} WorkState;
+
+// fwd
+static bool generateMap(WorkState* pState, RegisterMap* pMap);
+static bool analyzeMethod(WorkState* pState);
+static bool handleInstruction(WorkState* pState, SRegType* workRegs,\
+ int insnIdx, int* pStartGuess);
+static void updateRegisters(WorkState* pState, int nextInsn,\
+ const SRegType* workRegs);
+
+
+/*
+ * Set instruction flags.
+ */
+static bool setInsnFlags(WorkState* pState, int* pGcPointCount)
+{
+ const Method* meth = pState->method;
+ InsnFlags* insnFlags = pState->insnFlags;
+ int insnsSize = pState->insnsSize;
+ const u2* insns = meth->insns;
+ int gcPointCount = 0;
+ int offset;
+
+ /* set the widths */
+ if (!dvmComputeCodeWidths(meth, pState->insnFlags, NULL))
+ return false;
+
+ /* mark "try" regions and exception handler branch targets */
+ if (!dvmSetTryFlags(meth, pState->insnFlags))
+ return false;
+
+ /* the start of the method is a "branch target" */
+ dvmInsnSetBranchTarget(insnFlags, 0, true);
+
+ /*
+ * Run through the instructions, looking for switches and branches.
+ * Mark their targets.
+ *
+ * We don't really need to "check" these instructions -- the verifier
+ * already did that -- but the additional overhead isn't significant
+ * enough to warrant making a second copy of the "Check" function.
+ *
+ * Mark and count GC points while we're at it.
+ */
+ for (offset = 0; offset < insnsSize; offset++) {
+ static int gcMask = kInstrCanBranch | kInstrCanSwitch |
+ kInstrCanThrow | kInstrCanReturn;
+ u1 opcode = insns[offset] & 0xff;
+ InstructionFlags opFlags = dexGetInstrFlags(gDvm.instrFlags, opcode);
+
+ if (opFlags & kInstrCanBranch) {
+ if (!dvmCheckBranchTarget(meth, insnFlags, offset, true))
+ return false;
+ }
+ if (opFlags & kInstrCanSwitch) {
+ if (!dvmCheckSwitchTargets(meth, insnFlags, offset))
+ return false;
+ }
+
+ if ((opFlags & gcMask) != 0) {
+ dvmInsnSetGcPoint(pState->insnFlags, offset, true);
+ gcPointCount++;
+ }
+ }
+
+ *pGcPointCount = gcPointCount;
+ return true;
+}
+
+/*
+ * Generate the register map for a method.
+ *
+ * Returns a pointer to newly-allocated storage.
+ */
+RegisterMap* dvmGenerateRegisterMap(const Method* meth)
+{
+ WorkState* pState = NULL;
+ RegisterMap* pMap = NULL;
+ RegisterMap* result = NULL;
+ SRegType* regPtr;
+
+ pState = (WorkState*) calloc(1, sizeof(WorkState));
+ if (pState == NULL)
+ goto bail;
+
+ pMap = (RegisterMap*) calloc(1, sizeof(RegisterMap));
+ if (pMap == NULL)
+ goto bail;
+
+ pState->method = meth;
+ pState->insnsSize = dvmGetMethodInsnsSize(meth);
+ pState->insnRegCount = meth->registersSize + kExtraRegs;
+
+ pState->insnFlags = calloc(sizeof(InsnFlags), pState->insnsSize);
+ pState->addrRegs = calloc(sizeof(SRegType*), pState->insnsSize);
+
+ /*
+ * Set flags on instructions, and calculate the number of code units
+ * that happen to be GC points.
+ */
+ int gcPointCount;
+ if (!setInsnFlags(pState, &gcPointCount))
+ goto bail;
+
+ if (gcPointCount == 0) {
+ /* the method doesn't allocate or call, and never returns? unlikely */
+ LOG_VFY_METH(meth, "Found do-nothing method\n");
+ goto bail;
+ }
+
+ pState->regAlloc = (SRegType*)
+ calloc(sizeof(SRegType), pState->insnsSize * gcPointCount);
+ regPtr = pState->regAlloc;
+
+ /*
+ * For each instruction that is a GC point, set a pointer into the
+ * regAlloc buffer.
+ */
+ int offset;
+ for (offset = 0; offset < pState->insnsSize; offset++) {
+ if (dvmInsnIsGcPoint(pState->insnFlags, offset)) {
+ pState->addrRegs[offset] = regPtr;
+ regPtr += pState->insnRegCount;
+ }
+ }
+ assert(regPtr - pState->regAlloc == pState->insnsSize * gcPointCount);
+ assert(pState->addrRegs[0] != NULL);
+
+ /*
+ * Compute the register map.
+ */
+ if (!generateMap(pState, pMap))
+ goto bail;
+
+ /* success */
+ result = pMap;
+ pMap = NULL;
+
+bail:
+ if (pState != NULL) {
+ free(pState->insnFlags);
+ free(pState->addrRegs);
+ free(pState->regAlloc);
+ free(pState);
+ }
+ if (pMap != NULL)
+ dvmFreeRegisterMap(pMap);
+ return result;
+}
+
+/*
+ * Release the storage associated with a RegisterMap.
+ */
+void dvmFreeRegisterMap(RegisterMap* pMap)
+{
+ if (pMap == NULL)
+ return;
+}
+
+
+/*
+ * Create the RegisterMap using the provided state.
+ */
+static bool generateMap(WorkState* pState, RegisterMap* pMap)
+{
+ bool result = false;
+
+ /*
+ * Analyze the method and store the results in WorkState.
+ */
+ if (!analyzeMethod(pState))
+ goto bail;
+
+ /*
+ * Convert the analyzed data into a RegisterMap.
+ */
+ // TODO
+
+ result = true;
+
+bail:
+ return result;
+}
+
+/*
+ * Set the register types for the method arguments. We can pull the values
+ * out of the "shorty" signature.
+ */
+static bool setTypesFromSignature(WorkState* pState)
+{
+ const Method* meth = pState->method;
+ int argReg = meth->registersSize - meth->insSize; /* first arg */
+ SRegType* pRegs = pState->addrRegs[0];
+ SRegType* pCurReg = &pRegs[argReg];
+ const char* ccp;
+
+ /*
+ * Include "this" pointer, if appropriate.
+ */
+ if (!dvmIsStaticMethod(meth)) {
+ *pCurReg++ = kRegTypeReference;
+ }
+
+ ccp = meth->shorty +1; /* skip first byte, which holds return type */
+ while (*ccp != 0) {
+ switch (*ccp) {
+ case 'L':
+ case '[':
+ *pCurReg++ = kRegTypeReference;
+ break;
+ case 'Z':
+ *pCurReg++ = kRegTypeBoolean;
+ break;
+ case 'C':
+ *pCurReg++ = kRegTypeChar;
+ break;
+ case 'B':
+ *pCurReg++ = kRegTypeByte;
+ break;
+ case 'I':
+ *pCurReg++ = kRegTypeInteger;
+ break;
+ case 'S':
+ *pCurReg++ = kRegTypeShort;
+ break;
+ case 'F':
+ *pCurReg++ = kRegTypeFloat;
+ break;
+ case 'D':
+ *pCurReg++ = kRegTypeDoubleLo;
+ *pCurReg++ = kRegTypeDoubleHi;
+ break;
+ case 'J':
+ *pCurReg++ = kRegTypeLongLo;
+ *pCurReg++ = kRegTypeLongHi;
+ break;
+ default:
+ assert(false);
+ return false;
+ }
+ }
+
+ assert(pCurReg - pRegs == meth->insSize);
+ return true;
+}
+
+/*
+ * Find the start of the register set for the specified instruction in
+ * the current method.
+ */
+static inline SRegType* getRegisterLine(const WorkState* pState, int insnIdx)
+{
+ return pState->addrRegs[insnIdx];
+}
+
+/*
+ * Copy a set of registers.
+ */
+static inline void copyRegisters(SRegType* dst, const SRegType* src,
+ int numRegs)
+{
+ memcpy(dst, src, numRegs * sizeof(SRegType));
+}
+
+/*
+ * Compare a set of registers. Returns 0 if they match.
+ */
+static inline int compareRegisters(const SRegType* src1, const SRegType* src2,
+ int numRegs)
+{
+ return memcmp(src1, src2, numRegs * sizeof(SRegType));
+}
+
+/*
+ * Run through the instructions repeatedly until we have exercised all
+ * possible paths.
+ */
+static bool analyzeMethod(WorkState* pState)
+{
+ const Method* meth = pState->method;
+ SRegType workRegs[pState->insnRegCount];
+ InsnFlags* insnFlags = pState->insnFlags;
+ int insnsSize = pState->insnsSize;
+ int insnIdx, startGuess;
+ bool result = false;
+
+ /*
+ * Initialize the types of the registers that correspond to method
+ * arguments.
+ */
+ if (!setTypesFromSignature(pState))
+ goto bail;
+
+ /*
+ * Mark the first instruction as "changed".
+ */
+ dvmInsnSetChanged(insnFlags, 0, true);
+ startGuess = 0;
+
+ if (true) {
+ IF_LOGI() {
+ char* desc = dexProtoCopyMethodDescriptor(&meth->prototype);
+ LOGI("Now mapping: %s.%s %s (ins=%d regs=%d)\n",
+ meth->clazz->descriptor, meth->name, desc,
+ meth->insSize, meth->registersSize);
+ LOGI(" ------ [0 4 8 12 16 20 24 28 32 36\n");
+ free(desc);
+ }
+ }
+
+ /*
+ * Continue until no instructions are marked "changed".
+ */
+ while (true) {
+ /*
+ * Find the first marked one. Use "startGuess" as a way to find
+ * one quickly.
+ */
+ for (insnIdx = startGuess; insnIdx < insnsSize; insnIdx++) {
+ if (dvmInsnIsChanged(insnFlags, insnIdx))
+ break;
+ }
+
+ if (insnIdx == insnsSize) {
+ if (startGuess != 0) {
+ /* try again, starting from the top */
+ startGuess = 0;
+ continue;
+ } else {
+ /* all flags are clear */
+ break;
+ }
+ }
+
+ /*
+ * We carry the working set of registers from instruction to
+ * instruction. If this address can be the target of a branch
+ * (or throw) instruction, or if we're skipping around chasing
+ * "changed" flags, we need to load the set of registers from
+ * the table.
+ *
+ * Because we always prefer to continue on to the next instruction,
+ * we should never have a situation where we have a stray
+ * "changed" flag set on an instruction that isn't a branch target.
+ */
+ if (dvmInsnIsBranchTarget(insnFlags, insnIdx)) {
+ SRegType* insnRegs = getRegisterLine(pState, insnIdx);
+ assert(insnRegs != NULL);
+ copyRegisters(workRegs, insnRegs, pState->insnRegCount);
+
+ } else {
+#ifndef NDEBUG
+ /*
+ * Sanity check: retrieve the stored register line (assuming
+ * a full table) and make sure it actually matches.
+ */
+ SRegType* insnRegs = getRegisterLine(pState, insnIdx);
+ if (insnRegs != NULL &&
+ compareRegisters(workRegs, insnRegs, pState->insnRegCount) != 0)
+ {
+ char* desc = dexProtoCopyMethodDescriptor(&meth->prototype);
+ LOG_VFY("HUH? workRegs diverged in %s.%s %s\n",
+ meth->clazz->descriptor, meth->name, desc);
+ free(desc);
+ }
+#endif
+ }
+
+ /*
+ * Update the register sets altered by this instruction.
+ */
+ if (!handleInstruction(pState, workRegs, insnIdx, &startGuess)) {
+ goto bail;
+ }
+
+ dvmInsnSetVisited(insnFlags, insnIdx, true);
+ dvmInsnSetChanged(insnFlags, insnIdx, false);
+ }
+
+ // TODO - add dead code scan to help validate this code?
+
+ result = true;
+
+bail:
+ return result;
+}
+
+/*
+ * Decode the specified instruction and update the register info.
+ */
+static bool handleInstruction(WorkState* pState, SRegType* workRegs,
+ int insnIdx, int* pStartGuess)
+{
+ const Method* meth = pState->method;
+ const u2* insns = meth->insns + insnIdx;
+ InsnFlags* insnFlags = pState->insnFlags;
+ bool result = false;
+
+ /*
+ * Once we finish decoding the instruction, we need to figure out where
+ * we can go from here. There are three possible ways to transfer
+ * control to another statement:
+ *
+ * (1) Continue to the next instruction. Applies to all but
+ * unconditional branches, method returns, and exception throws.
+ * (2) Branch to one or more possible locations. Applies to branches
+ * and switch statements.
+ * (3) Exception handlers. Applies to any instruction that can
+ * throw an exception that is handled by an encompassing "try"
+ * block. (We simplify this to be any instruction that can
+ * throw any exception.)
+ *
+ * We can also return, in which case there is no successor instruction
+ * from this point.
+ *
+ * The behavior can be determined from the InstrFlags.
+ */
+ DecodedInstruction decInsn;
+ SRegType entryRegs[pState->insnRegCount];
+ bool justSetResult = false;
+ int branchTarget = 0;
+
+ dexDecodeInstruction(gDvm.instrFormat, insns, &decInsn);
+ const int nextFlags = dexGetInstrFlags(gDvm.instrFlags, decInsn.opCode);
+
+
+ /*
+ * Make a copy of the previous register state. If the instruction
+ * throws an exception, we merge *this* into the destination rather
+ * than workRegs, because we don't want the result from the "successful"
+ * code path (e.g. a check-cast that "improves" a type) to be visible
+ * to the exception handler.
+ */
+ if ((nextFlags & kInstrCanThrow) != 0 && dvmInsnIsInTry(insnFlags, insnIdx))
+ {
+ copyRegisters(entryRegs, workRegs, pState->insnRegCount);
+ }
+
+ switch (decInsn.opCode) {
+ case OP_NOP:
+ break;
+
+ default: break; // TODO: fill this in
+
+ /*
+ * DO NOT add a "default" clause here. Without it the compiler will
+ * complain if an instruction is missing (which is desirable).
+ */
+ }
+
+
+ /*
+ * If we didn't just set the result register, clear it out. This
+ * isn't so important here, but does help ensure that our output matches
+ * the verifier.
+ */
+ if (!justSetResult) {
+ int reg = RESULT_REGISTER(pState->insnRegCount);
+ workRegs[reg] = workRegs[reg+1] = kRegTypeUnknown;
+ }
+
+ /*
+ * Handle "continue". Tag the next consecutive instruction.
+ */
+ if ((nextFlags & kInstrCanContinue) != 0) {
+ int insnWidth = dvmInsnGetWidth(insnFlags, insnIdx);
+
+ /*
+ * We want to update the registers and set the "changed" flag on the
+ * next instruction (if necessary). We aren't storing register
+ * changes for all addresses, so for non-GC-point targets we just
+ * compare "entry" vs. "work" to see if we've changed anything.
+ */
+ if (getRegisterLine(pState, insnIdx+insnWidth) != NULL) {
+ updateRegisters(pState, insnIdx+insnWidth, workRegs);
+ } else {
+ /* if not yet visited, or regs were updated, set "changed" */
+ if (!dvmInsnIsVisited(insnFlags, insnIdx+insnWidth) ||
+ compareRegisters(workRegs, entryRegs,
+ pState->insnRegCount) != 0)
+ {
+ dvmInsnSetChanged(insnFlags, insnIdx+insnWidth, true);
+ }
+ }
+ }
+
+ /*
+ * Handle "branch". Tag the branch target.
+ */
+ if ((nextFlags & kInstrCanBranch) != 0) {
+ bool isConditional;
+
+ dvmGetBranchTarget(meth, insnFlags, insnIdx, &branchTarget,
+ &isConditional);
+ assert(isConditional || (nextFlags & kInstrCanContinue) == 0);
+ assert(!isConditional || (nextFlags & kInstrCanContinue) != 0);
+
+ updateRegisters(pState, insnIdx+branchTarget, workRegs);
+ }
+
+ /*
+ * Handle "switch". Tag all possible branch targets.
+ */
+ if ((nextFlags & kInstrCanSwitch) != 0) {
+ int offsetToSwitch = insns[1] | (((s4)insns[2]) << 16);
+ const u2* switchInsns = insns + offsetToSwitch;
+ int switchCount = switchInsns[1];
+ int offsetToTargets, targ;
+
+ if ((*insns & 0xff) == OP_PACKED_SWITCH) {
+ /* 0=sig, 1=count, 2/3=firstKey */
+ offsetToTargets = 4;
+ } else {
+ /* 0=sig, 1=count, 2..count*2 = keys */
+ assert((*insns & 0xff) == OP_SPARSE_SWITCH);
+ offsetToTargets = 2 + 2*switchCount;
+ }
+
+ /* verify each switch target */
+ for (targ = 0; targ < switchCount; targ++) {
+ int offset, absOffset;
+
+ /* offsets are 32-bit, and only partly endian-swapped */
+ offset = switchInsns[offsetToTargets + targ*2] |
+ (((s4) switchInsns[offsetToTargets + targ*2 +1]) << 16);
+ absOffset = insnIdx + offset;
+ assert(absOffset >= 0 && absOffset < pState->insnsSize);
+
+ updateRegisters(pState, absOffset, workRegs);
+ }
+ }
+
+ /*
+ * Handle instructions that can throw and that are sitting in a
+ * "try" block. (If they're not in a "try" block when they throw,
+ * control transfers out of the method.)
+ */
+ if ((nextFlags & kInstrCanThrow) != 0 && dvmInsnIsInTry(insnFlags, insnIdx))
+ {
+ DexFile* pDexFile = meth->clazz->pDvmDex->pDexFile;
+ const DexCode* pCode = dvmGetMethodCode(meth);
+ DexCatchIterator iterator;
+
+ if (dexFindCatchHandler(&iterator, pCode, insnIdx)) {
+ while (true) {
+ DexCatchHandler* handler = dexCatchIteratorNext(&iterator);
+ if (handler == NULL)
+ break;
+
+ /* note we use entryRegs, not workRegs */
+ updateRegisters(pState, handler->address, entryRegs);
+ }
+ }
+ }
+
+ /*
+ * Update startGuess. Advance to the next instruction of that's
+ * possible, otherwise use the branch target if one was found. If
+ * neither of those exists we're in a return or throw; leave startGuess
+ * alone and let the caller sort it out.
+ */
+ if ((nextFlags & kInstrCanContinue) != 0) {
+ *pStartGuess = insnIdx + dvmInsnGetWidth(insnFlags, insnIdx);
+ } else if ((nextFlags & kInstrCanBranch) != 0) {
+ /* we're still okay if branchTarget is zero */
+ *pStartGuess = insnIdx + branchTarget;
+ }
+
+ assert(*pStartGuess >= 0 && *pStartGuess < pState->insnsSize &&
+ dvmInsnGetWidth(insnFlags, *pStartGuess) != 0);
+
+ result = true;
+
+bail:
+ return result;
+}
+
+
+/*
+ * Merge two SRegType values.
+ *
+ * Sets "*pChanged" to "true" if the result doesn't match "type1".
+ */
+static SRegType mergeTypes(SRegType type1, SRegType type2, bool* pChanged)
+{
+ SRegType result;
+
+ /*
+ * Check for trivial case so we don't have to hit memory.
+ */
+ if (type1 == type2)
+ return type1;
+
+ /*
+ * Use the table if we can, and reject any attempts to merge something
+ * from the table with a reference type.
+ *
+ * The uninitialized table entry at index zero *will* show up as a
+ * simple kRegTypeUninit value. Since this cannot be merged with
+ * anything but itself, the rules do the right thing.
+ */
+ if (type1 < kRegTypeMAX) {
+ if (type2 < kRegTypeMAX) {
+ result = gDvmMergeTab[type1][type2];
+ } else {
+ /* simple + reference == conflict, usually */
+ if (type1 == kRegTypeZero)
+ result = type2;
+ else
+ result = kRegTypeConflict;
+ }
+ } else {
+ if (type2 < kRegTypeMAX) {
+ /* reference + simple == conflict, usually */
+ if (type2 == kRegTypeZero)
+ result = type1;
+ else
+ result = kRegTypeConflict;
+ } else {
+ /* merging two references */
+ assert(type1 == type2);
+ result = type1;
+ }
+ }
+
+ if (result != type1)
+ *pChanged = true;
+ return result;
+}
+
+/*
+ * Control can transfer to "nextInsn".
+ *
+ * Merge the registers from "workRegs" into "addrRegs" at "nextInsn", and
+ * set the "changed" flag on the target address if the registers have changed.
+ */
+static void updateRegisters(WorkState* pState, int nextInsn,
+ const SRegType* workRegs)
+{
+ const Method* meth = pState->method;
+ InsnFlags* insnFlags = pState->insnFlags;
+ const int insnRegCount = pState->insnRegCount;
+ SRegType* targetRegs = getRegisterLine(pState, nextInsn);
+
+ if (!dvmInsnIsVisitedOrChanged(insnFlags, nextInsn)) {
+ /*
+ * We haven't processed this instruction before, and we haven't
+ * touched the registers here, so there's nothing to "merge". Copy
+ * the registers over and mark it as changed. (This is the only
+ * way a register can transition out of "unknown", so this is not
+ * just an optimization.)
+ */
+ LOGVV("COPY into 0x%04x\n", nextInsn);
+ copyRegisters(targetRegs, workRegs, insnRegCount);
+ dvmInsnSetChanged(insnFlags, nextInsn, true);
+ } else {
+ /* merge registers, set Changed only if different */
+ LOGVV("MERGE into 0x%04x\n", nextInsn);
+ bool changed = false;
+ int i;
+
+ for (i = 0; i < insnRegCount; i++) {
+ targetRegs[i] = mergeTypes(targetRegs[i], workRegs[i], &changed);
+ }
+
+ if (changed)
+ dvmInsnSetChanged(insnFlags, nextInsn, true);
+ }
+}
+
diff --git a/vm/analysis/RegisterMap.h b/vm/analysis/RegisterMap.h
new file mode 100644
index 0000000..d431aa7
--- /dev/null
+++ b/vm/analysis/RegisterMap.h
@@ -0,0 +1,46 @@
+/*
+ * 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.
+ */
+
+/*
+ * Register map declaration.
+ */
+#ifndef _DALVIK_REGISTERMAP
+#define _DALVIK_REGISTERMAP
+
+typedef struct RegisterMap {
+ /* header */
+ char addrWidth; /* bytes per address, 1 or 2 */
+ char regWidth; /* bytes per register line, 1+ */
+ char pad0;
+ char pad1;
+
+ /* entries start here; 32-bit align guaranteed */
+ u4 entries[1];
+} RegisterMap;
+
+/*
+ * Generate the register map for a method.
+ *
+ * Returns a pointer to newly-allocated storage.
+ */
+RegisterMap* dvmGenerateRegisterMap(const Method* meth);
+
+/*
+ * Release the storage associated with a RegisterMap.
+ */
+void dvmFreeRegisterMap(RegisterMap* pMap);
+
+#endif /*_DALVIK_REGISTERMAP*/
diff --git a/vm/analysis/VerifySubs.c b/vm/analysis/VerifySubs.c
new file mode 100644
index 0000000..77134a7
--- /dev/null
+++ b/vm/analysis/VerifySubs.c
@@ -0,0 +1,437 @@
+/*
+ * 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.
+ */
+
+/*
+ * Dalvik verification subroutines.
+ */
+#include "Dalvik.h"
+#include "analysis/CodeVerify.h"
+#include "libdex/DexCatch.h"
+#include "libdex/InstrUtils.h"
+
+
+/*
+ * Compute the width of the instruction at each address in the instruction
+ * stream. Addresses that are in the middle of an instruction, or that
+ * are part of switch table data, are not set (so the caller should probably
+ * initialize "insnFlags" to zero).
+ *
+ * If "pNewInstanceCount" is not NULL, it will be set to the number of
+ * new-instance instructions in the method.
+ *
+ * Logs an error and returns "false" on failure.
+ */
+bool dvmComputeCodeWidths(const Method* meth, InsnFlags* insnFlags,
+ int* pNewInstanceCount)
+{
+ const int insnCount = dvmGetMethodInsnsSize(meth);
+ const u2* insns = meth->insns;
+ bool result = false;
+ int newInstanceCount = 0;
+ int i;
+
+
+ for (i = 0; i < insnCount; /**/) {
+ int width;
+
+ /*
+ * 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;
+ } else if (*insns == kArrayDataSignature) {
+ u4 size = insns[2] | (((u4)insns[3]) << 16);
+ width = 4 + (insns[1] * size + 1) / 2;
+ } else {
+ int instr = *insns & 0xff;
+ width = dexGetInstrWidthAbs(gDvm.instrWidth, instr);
+ if (width == 0) {
+ LOG_VFY_METH(meth,
+ "VFY: invalid post-opt instruction (0x%x)\n", instr);
+ goto bail;
+ }
+ if (width < 0 || width > 5) {
+ LOGE("VFY: bizarre width value %d\n", width);
+ dvmAbort();
+ }
+
+ if (instr == OP_NEW_INSTANCE)
+ newInstanceCount++;
+ }
+
+ if (width > 65535) {
+ LOG_VFY_METH(meth, "VFY: insane width %d\n", width);
+ goto bail;
+ }
+
+ insnFlags[i] |= width;
+ i += width;
+ insns += width;
+ }
+ if (i != (int) dvmGetMethodInsnsSize(meth)) {
+ LOG_VFY_METH(meth, "VFY: code did not end where expected (%d vs. %d)\n",
+ i, dvmGetMethodInsnsSize(meth));
+ goto bail;
+ }
+
+ result = true;
+ if (pNewInstanceCount != NULL)
+ *pNewInstanceCount = newInstanceCount;
+
+bail:
+ return result;
+}
+
+/*
+ * Set the "in try" flags for all instructions protected by "try" statements.
+ * Also sets the "branch target" flags for exception handlers.
+ *
+ * Call this after widths have been set in "insnFlags".
+ *
+ * Returns "false" if something in the exception table looks fishy, but
+ * we're expecting the exception table to be somewhat sane.
+ */
+bool dvmSetTryFlags(const Method* meth, InsnFlags* insnFlags)
+{
+ u4 insnsSize = dvmGetMethodInsnsSize(meth);
+ DexFile* pDexFile = meth->clazz->pDvmDex->pDexFile;
+ const DexCode* pCode = dvmGetMethodCode(meth);
+ u4 triesSize = pCode->triesSize;
+ const DexTry* pTries;
+ u4 handlersSize;
+ u4 offset;
+ u4 i;
+
+ if (triesSize == 0) {
+ return true;
+ }
+
+ pTries = dexGetTries(pCode);
+ handlersSize = dexGetHandlersSize(pCode);
+
+ for (i = 0; i < triesSize; i++) {
+ const DexTry* pTry = &pTries[i];
+ u4 start = pTry->startAddr;
+ u4 end = start + pTry->insnCount;
+ u4 addr;
+
+ if ((start >= end) || (start >= insnsSize) || (end > insnsSize)) {
+ LOG_VFY_METH(meth,
+ "VFY: bad exception entry: startAddr=%d endAddr=%d (size=%d)\n",
+ start, end, insnsSize);
+ return false;
+ }
+
+ if (dvmInsnGetWidth(insnFlags, start) == 0) {
+ LOG_VFY_METH(meth,
+ "VFY: 'try' block starts inside an instruction (%d)\n",
+ start);
+ return false;
+ }
+
+ for (addr = start; addr < end;
+ addr += dvmInsnGetWidth(insnFlags, addr))
+ {
+ assert(dvmInsnGetWidth(insnFlags, addr) != 0);
+ dvmInsnSetInTry(insnFlags, addr, true);
+ }
+ }
+
+ /* Iterate over each of the handlers to verify target addresses. */
+ offset = dexGetFirstHandlerOffset(pCode);
+ for (i = 0; i < handlersSize; i++) {
+ DexCatchIterator iterator;
+ dexCatchIteratorInit(&iterator, pCode, offset);
+
+ for (;;) {
+ DexCatchHandler* handler = dexCatchIteratorNext(&iterator);
+ u4 addr;
+
+ if (handler == NULL) {
+ break;
+ }
+
+ addr = handler->address;
+ if (dvmInsnGetWidth(insnFlags, addr) == 0) {
+ LOG_VFY_METH(meth,
+ "VFY: exception handler starts at bad address (%d)\n",
+ addr);
+ return false;
+ }
+
+ dvmInsnSetBranchTarget(insnFlags, addr, true);
+ }
+
+ offset = dexCatchIteratorGetEndOffset(&iterator, pCode);
+ }
+
+ return true;
+}
+
+/*
+ * Verify a switch table. "curOffset" is the offset of the switch
+ * instruction.
+ */
+bool dvmCheckSwitchTargets(const Method* meth, InsnFlags* insnFlags,
+ int curOffset)
+{
+ const int insnCount = dvmGetMethodInsnsSize(meth);
+ const u2* insns = meth->insns + curOffset;
+ const u2* switchInsns;
+ int switchCount, tableSize;
+ int offsetToSwitch, offsetToKeys, offsetToTargets, targ;
+ int offset, absOffset;
+
+ assert(curOffset >= 0 && curOffset < insnCount);
+
+ /* make sure the start of the switch is in range */
+ offsetToSwitch = (s2) insns[1];
+ if (curOffset + offsetToSwitch < 0 ||
+ curOffset + offsetToSwitch + 2 >= insnCount)
+ {
+ LOG_VFY_METH(meth,
+ "VFY: invalid switch start: at %d, switch offset %d, count %d\n",
+ curOffset, offsetToSwitch, insnCount);
+ return false;
+ }
+
+ /* offset to switch table is a relative branch-style offset */
+ switchInsns = insns + offsetToSwitch;
+
+ /* make sure the table is 32-bit aligned */
+ if ((((u4) switchInsns) & 0x03) != 0) {
+ LOG_VFY_METH(meth,
+ "VFY: unaligned switch table: at %d, switch offset %d\n",
+ curOffset, offsetToSwitch);
+ return false;
+ }
+
+ switchCount = switchInsns[1];
+
+ if ((*insns & 0xff) == OP_PACKED_SWITCH) {
+ /* 0=sig, 1=count, 2/3=firstKey */
+ offsetToTargets = 4;
+ offsetToKeys = -1;
+ } else {
+ /* 0=sig, 1=count, 2..count*2 = keys */
+ offsetToKeys = 2;
+ offsetToTargets = 2 + 2*switchCount;
+ }
+ tableSize = offsetToTargets + switchCount*2;
+
+ /* make sure the end of the switch is in range */
+ if (curOffset + offsetToSwitch + tableSize > insnCount) {
+ LOG_VFY_METH(meth,
+ "VFY: invalid switch end: at %d, switch offset %d, end %d, count %d\n",
+ curOffset, offsetToSwitch, curOffset + offsetToSwitch + tableSize,
+ insnCount);
+ return false;
+ }
+
+ /* 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++) {
+ s4 key = (s4) switchInsns[offsetToKeys + targ*2] |
+ (s4) (switchInsns[offsetToKeys + targ*2 +1] << 16);
+ if (key <= lastKey) {
+ LOG_VFY_METH(meth,
+ "VFY: invalid packed switch: last key=%d, this=%d\n",
+ lastKey, key);
+ return false;
+ }
+
+ lastKey = key;
+ }
+ }
+
+ /* verify each switch target */
+ for (targ = 0; targ < switchCount; targ++) {
+ offset = (s4) switchInsns[offsetToTargets + targ*2] |
+ (s4) (switchInsns[offsetToTargets + targ*2 +1] << 16);
+ absOffset = curOffset + offset;
+
+ if (absOffset < 0 || absOffset >= insnCount ||
+ !dvmInsnIsOpcode(insnFlags, absOffset))
+ {
+ LOG_VFY_METH(meth,
+ "VFY: invalid switch target %d (-> 0x%x) at 0x%x[%d]\n",
+ offset, absOffset, curOffset, targ);
+ return false;
+ }
+ dvmInsnSetBranchTarget(insnFlags, absOffset, true);
+ }
+
+ return true;
+}
+
+/*
+ * Verify that the target of a branch instruction is valid.
+ *
+ * We don't expect code to jump directly into an exception handler, but
+ * it's valid to do so as long as the target isn't a "move-exception"
+ * instruction. We verify that in a later stage.
+ *
+ * The VM spec doesn't forbid an instruction from branching to itself,
+ * but the Dalvik spec declares that only certain instructions can do so.
+ */
+bool dvmCheckBranchTarget(const Method* meth, InsnFlags* insnFlags,
+ int curOffset, bool selfOkay)
+{
+ const int insnCount = dvmGetMethodInsnsSize(meth);
+ const u2* insns = meth->insns + curOffset;
+ int offset, absOffset;
+ bool isConditional;
+
+ if (!dvmGetBranchTarget(meth, insnFlags, curOffset, &offset,
+ &isConditional))
+ return false;
+
+ if (!selfOkay && offset == 0) {
+ LOG_VFY_METH(meth, "VFY: branch offset of zero not allowed at 0x%x\n",
+ curOffset);
+ return false;
+ }
+
+ /*
+ * Check for 32-bit overflow. This isn't strictly necessary if we can
+ * depend on the VM to have identical "wrap-around" behavior, but
+ * it's unwise to depend on that.
+ */
+ if (((s8) curOffset + (s8) offset) != (s8)(curOffset + offset)) {
+ LOG_VFY_METH(meth, "VFY: branch target overflow 0x%x +%d\n",
+ curOffset, offset);
+ return false;
+ }
+ absOffset = curOffset + offset;
+ if (absOffset < 0 || absOffset >= insnCount ||
+ !dvmInsnIsOpcode(insnFlags, absOffset))
+ {
+ LOG_VFY_METH(meth,
+ "VFY: invalid branch target %d (-> 0x%x) at 0x%x\n",
+ offset, absOffset, curOffset);
+ return false;
+ }
+ dvmInsnSetBranchTarget(insnFlags, absOffset, true);
+
+ return true;
+}
+
+
+/*
+ * Output a code verifier warning message. For the pre-verifier it's not
+ * a big deal if something fails (and it may even be expected), but if
+ * we're doing just-in-time verification it's significant.
+ */
+void dvmLogVerifyFailure(const Method* meth, const char* format, ...)
+{
+ va_list ap;
+ int logLevel;
+
+ 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);
+ if (meth != NULL) {
+ char* desc = dexProtoCopyMethodDescriptor(&meth->prototype);
+ LOG_PRI(logLevel, LOG_TAG, "VFY: rejected %s.%s %s\n",
+ meth->clazz->descriptor, meth->name, desc);
+ free(desc);
+ }
+}
+
+/*
+ * Show a relatively human-readable message describing the failure to
+ * resolve a class.
+ */
+void dvmLogUnableToResolveClass(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).
+ */
+bool dvmGetBranchTarget(const Method* meth, InsnFlags* insnFlags,
+ int curOffset, int* pOffset, bool* pConditional)
+{
+ const u2* insns = meth->insns + curOffset;
+ int tmp;
+
+ switch (*insns & 0xff) {
+ case OP_GOTO:
+ *pOffset = ((s2) *insns) >> 8;
+ *pConditional = false;
+ break;
+ case OP_GOTO_32:
+ *pOffset = insns[1] | (((u4) insns[2]) << 16);
+ *pConditional = false;
+ break;
+ case OP_GOTO_16:
+ *pOffset = (s2) insns[1];
+ *pConditional = false;
+ break;
+ case OP_IF_EQ:
+ case OP_IF_NE:
+ case OP_IF_LT:
+ case OP_IF_GE:
+ case OP_IF_GT:
+ case OP_IF_LE:
+ case OP_IF_EQZ:
+ case OP_IF_NEZ:
+ case OP_IF_LTZ:
+ case OP_IF_GEZ:
+ case OP_IF_GTZ:
+ case OP_IF_LEZ:
+ *pOffset = (s2) insns[1];
+ *pConditional = true;
+ break;
+ default:
+ return false;
+ break;
+ }
+
+ return true;
+}
+
+
diff --git a/vm/analysis/VerifySubs.h b/vm/analysis/VerifySubs.h
new file mode 100644
index 0000000..4a317d4
--- /dev/null
+++ b/vm/analysis/VerifySubs.h
@@ -0,0 +1,70 @@
+/*
+ * 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.
+ */
+
+/*
+ * Dalvik bytecode verification subroutines.
+ */
+#ifndef _DALVIK_VERIFYSUBS
+#define _DALVIK_VERIFYSUBS
+
+/*
+ * InsnFlags is a 32-bit integer with the following layout:
+ * 0-15 instruction length (or 0 if this address doesn't hold an opcode)
+ * 16 opcode flag (indicating this address holds an opcode)
+ * 17 try block (indicating exceptions thrown here may be caught locally)
+ * 30 visited (verifier has examined this instruction at least once)
+ * 31 changed (set/cleared as bytecode verifier runs)
+ */
+typedef u4 InsnFlags;
+
+#define kInsnFlagWidthMask 0x0000ffff
+#define kInsnFlagInTry (1 << 16)
+#define kInsnFlagBranchTarget (1 << 17)
+#define kInsnFlagGcPoint (1 << 18)
+#define kInsnFlagVisited (1 << 30)
+#define kInsnFlagChanged (1 << 31)
+
+/* add opcode widths to InsnFlags */
+bool dvmComputeCodeWidths(const Method* meth, InsnFlags* insnFlags,
+ int* pNewInstanceCount);
+
+/* set the "in try" flag for sections of code wrapped with a "try" block */
+bool dvmSetTryFlags(const Method* meth, InsnFlags* insnFlags);
+
+/* check switch targets and set the "branch target" flag for destinations */
+bool dvmCheckSwitchTargets(const Method* meth, InsnFlags* insnFlags,
+ int curOffset);
+
+/* verify branch target and set "branch target" flag on the destination */
+bool dvmCheckBranchTarget(const Method* meth, InsnFlags* insnFlags,
+ int curOffset, bool selfOkay);
+
+/* verification failure reporting */
+#define LOG_VFY(...) dvmLogVerifyFailure(NULL, __VA_ARGS__)
+#define LOG_VFY_METH(_meth, ...) dvmLogVerifyFailure(_meth, __VA_ARGS__)
+
+/* log verification failure with optional method info */
+void dvmLogVerifyFailure(const Method* meth, const char* format, ...);
+
+/* log verification failure due to resolution trouble */
+void dvmLogUnableToResolveClass(const char* missingClassDescr,
+ const Method* meth);
+
+/* extract the relative branch target from a branch instruction */
+bool dvmGetBranchTarget(const Method* meth, InsnFlags* insnFlags,
+ int curOffset, int* pOffset, bool* pConditional);
+
+#endif /*_DALVIK_VERIFYSUBS*/