blob: 4a0d3d71d71865d931b0b8561d4eeaf32445e95b [file] [log] [blame]
/*
* 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 structural verifier. The only public entry point
* (except for a few shared utility functions) is dvmVerifyCodeFlow().
*
* TODO: might benefit from a signature-->class lookup cache. Could avoid
* some string-peeling and wouldn't need to compute hashes.
*/
#include "Dalvik.h"
#include "analysis/Liveness.h"
#include "analysis/CodeVerify.h"
#include "analysis/Optimize.h"
#include "analysis/RegisterMap.h"
#include "libdex/DexCatch.h"
#include "libdex/InstrUtils.h"
#include <stddef.h>
/*
* We don't need to store the register data for many instructions, because
* we either only need it at branch points (for verification) or GC points
* and branches (for verification + type-precise register analysis).
*/
enum RegisterTrackingMode {
kTrackRegsBranches,
kTrackRegsGcPoints,
kTrackRegsAll
};
/*
* Set this to enable dead code scanning. This is not required, but it's
* very useful when testing changes to the verifier (to make sure we're not
* skipping over stuff) and for checking the optimized output from "dx".
* The only reason not to do it is that it slightly increases the time
* required to perform verification.
*/
#ifndef NDEBUG
# define DEAD_CODE_SCAN true
#else
# define DEAD_CODE_SCAN false
#endif
static bool gDebugVerbose = false;
#define SHOW_REG_DETAILS \
(0 | DRT_SHOW_LIVENESS /*| DRT_SHOW_REF_TYPES | DRT_SHOW_LOCALS*/)
/*
* 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)
/*
* Big fat collection of register data.
*/
typedef struct RegisterTable {
/*
* Array of RegisterLine structs, one per address in the method. We only
* set the pointers for certain addresses, based on instruction widths
* and what we're trying to accomplish.
*/
RegisterLine* registerLines;
/*
* Number of registers we track for each instruction. This is equal
* to the method's declared "registersSize" plus kExtraRegs.
*/
size_t insnRegCountPlus;
/*
* Storage for a register line we're currently working on.
*/
RegisterLine workLine;
/*
* Storage for a register line we're saving for later.
*/
RegisterLine savedLine;
/*
* A single large alloc, with all of the storage needed for RegisterLine
* data (RegType array, MonitorEntries array, monitor stack).
*/
void* lineAlloc;
} RegisterTable;
/* fwd */
#ifndef NDEBUG
static void checkMergeTab();
#endif
static bool isInitMethod(const Method* meth);
static RegType getInvocationThis(const RegisterLine* registerLine,\
const DecodedInstruction* pDecInsn, VerifyError* pFailure);
static void verifyRegisterType(RegisterLine* registerLine, \
u4 vsrc, RegType checkType, VerifyError* pFailure);
static bool doCodeVerification(VerifierData* vdata, RegisterTable* regTable);
static bool verifyInstruction(const Method* meth, InsnFlags* insnFlags,\
RegisterTable* regTable, int insnIdx, UninitInstanceMap* uninitMap,
int* pStartGuess);
static ClassObject* findCommonSuperclass(ClassObject* c1, ClassObject* c2);
static void dumpRegTypes(const VerifierData* vdata, \
const RegisterLine* registerLine, int addr, const char* addrName,
const UninitInstanceMap* uninitMap, int displayFlags);
/* bit values for dumpRegTypes() "displayFlags" */
enum {
DRT_SIMPLE = 0,
DRT_SHOW_REF_TYPES = 0x01,
DRT_SHOW_LOCALS = 0x02,
DRT_SHOW_LIVENESS = 0x04,
};
/*
* ===========================================================================
* RegType and UninitInstanceMap utility functions
* ===========================================================================
*/
#define __ kRegTypeUnknown
#define _U kRegTypeUninit
#define _X kRegTypeConflict
#define _0 kRegTypeZero
#define _1 kRegTypeOne
#define _Z kRegTypeBoolean
#define _y kRegTypeConstPosByte
#define _Y kRegTypeConstByte
#define _h kRegTypeConstPosShort
#define _H kRegTypeConstShort
#define _c kRegTypeConstChar
#define _i kRegTypeConstInteger
#define _b kRegTypePosByte
#define _B kRegTypeByte
#define _s kRegTypePosShort
#define _S kRegTypeShort
#define _C kRegTypeChar
#define _I kRegTypeInteger
#define _F kRegTypeFloat
#define _N kRegTypeConstLo
#define _n kRegTypeConstHi
#define _J kRegTypeLongLo
#define _j kRegTypeLongHi
#define _D kRegTypeDoubleLo
#define _d kRegTypeDoubleHi
/*
* 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"
* widening within a category, e.g. byte to short, is allowed.
*
* Dalvik does not draw a distinction between int and float, but we enforce
* that once a value is used as int, it can't be used as float, and vice
* versa. We do not allow free exchange between 32-bit int/float and 64-bit
* long/double.
*
* Note that Uninit+Uninit=Uninit. This holds true because we only
* use this when the RegType value is exactly equal to kRegTypeUninit, which
* can only happen for the zeroeth entry in the table.
*
* "Unknown" never merges with anything known. The only time a register
* transitions from "unknown" to "known" is when we're executing code
* for the first time, and we handle that with a simple copy.
*/
const char gDvmMergeTab[kRegTypeMAX][kRegTypeMAX] =
{
/* chk: _ U X 0 1 Z y Y h H c i b B s S C I F N n J j D d */
{ /*_*/ __,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X },
{ /*U*/ _X,_U,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X },
{ /*X*/ _X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X },
{ /*0*/ _X,_X,_X,_0,_Z,_Z,_y,_Y,_h,_H,_c,_i,_b,_B,_s,_S,_C,_I,_F,_X,_X,_X,_X,_X,_X },
{ /*1*/ _X,_X,_X,_Z,_1,_Z,_y,_Y,_h,_H,_c,_i,_b,_B,_s,_S,_C,_I,_F,_X,_X,_X,_X,_X,_X },
{ /*Z*/ _X,_X,_X,_Z,_Z,_Z,_y,_Y,_h,_H,_c,_i,_b,_B,_s,_S,_C,_I,_F,_X,_X,_X,_X,_X,_X },
{ /*y*/ _X,_X,_X,_y,_y,_y,_y,_Y,_h,_H,_c,_i,_b,_B,_s,_S,_C,_I,_F,_X,_X,_X,_X,_X,_X },
{ /*Y*/ _X,_X,_X,_Y,_Y,_Y,_Y,_Y,_h,_H,_c,_i,_B,_B,_S,_S,_I,_I,_F,_X,_X,_X,_X,_X,_X },
{ /*h*/ _X,_X,_X,_h,_h,_h,_h,_h,_h,_H,_c,_i,_s,_S,_s,_S,_C,_I,_F,_X,_X,_X,_X,_X,_X },
{ /*H*/ _X,_X,_X,_H,_H,_H,_H,_H,_H,_H,_c,_i,_S,_S,_S,_S,_I,_I,_F,_X,_X,_X,_X,_X,_X },
{ /*c*/ _X,_X,_X,_c,_c,_c,_c,_c,_c,_c,_c,_i,_C,_I,_C,_I,_C,_I,_F,_X,_X,_X,_X,_X,_X },
{ /*i*/ _X,_X,_X,_i,_i,_i,_i,_i,_i,_i,_i,_i,_I,_I,_I,_I,_I,_I,_F,_X,_X,_X,_X,_X,_X },
{ /*b*/ _X,_X,_X,_b,_b,_b,_b,_B,_s,_S,_C,_I,_b,_B,_s,_S,_C,_I,_X,_X,_X,_X,_X,_X,_X },
{ /*B*/ _X,_X,_X,_B,_B,_B,_B,_B,_S,_S,_I,_I,_B,_B,_S,_S,_I,_I,_X,_X,_X,_X,_X,_X,_X },
{ /*s*/ _X,_X,_X,_s,_s,_s,_s,_S,_s,_S,_C,_I,_s,_S,_s,_S,_C,_I,_X,_X,_X,_X,_X,_X,_X },
{ /*S*/ _X,_X,_X,_S,_S,_S,_S,_S,_S,_S,_I,_I,_S,_S,_S,_S,_I,_I,_X,_X,_X,_X,_X,_X,_X },
{ /*C*/ _X,_X,_X,_C,_C,_C,_C,_I,_C,_I,_C,_I,_C,_I,_C,_I,_C,_I,_X,_X,_X,_X,_X,_X,_X },
{ /*I*/ _X,_X,_X,_I,_I,_I,_I,_I,_I,_I,_I,_I,_I,_I,_I,_I,_I,_I,_X,_X,_X,_X,_X,_X,_X },
{ /*F*/ _X,_X,_X,_F,_F,_F,_F,_F,_F,_F,_F,_F,_X,_X,_X,_X,_X,_X,_F,_X,_X,_X,_X,_X,_X },
{ /*N*/ _X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_N,_X,_J,_X,_D,_X },
{ /*n*/ _X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_n,_X,_j,_X,_d },
{ /*J*/ _X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_J,_X,_J,_X,_X,_X },
{ /*j*/ _X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_j,_X,_j,_X,_X },
{ /*D*/ _X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_D,_X,_X,_X,_D,_X },
{ /*d*/ _X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_d,_X,_X,_X,_d },
};
#undef __
#undef _U
#undef _X
#undef _0
#undef _1
#undef _Z
#undef _y
#undef _Y
#undef _h
#undef _H
#undef _c
#undef _i
#undef _b
#undef _B
#undef _s
#undef _S
#undef _C
#undef _I
#undef _F
#undef _N
#undef _n
#undef _J
#undef _j
#undef _D
#undef _d
#ifndef NDEBUG
/*
* Verify symmetry in the conversion table.
*/
static void checkMergeTab()
{
int i, j;
for (i = 0; i < kRegTypeMAX; i++) {
for (j = i; j < kRegTypeMAX; j++) {
if (gDvmMergeTab[i][j] != gDvmMergeTab[j][i]) {
ALOGE("Symmetry violation: %d,%d vs %d,%d", i, j, j, i);
dvmAbort();
}
}
}
}
#endif
/*
* Determine whether we can convert "srcType" to "checkType", where
* "checkType" is one of the category-1 non-reference types.
*
* Constant derived types may become floats, but other values may not.
*/
static bool canConvertTo1nr(RegType srcType, RegType checkType)
{
static const char convTab
[kRegType1nrEND-kRegType1nrSTART+1][kRegType1nrEND-kRegType1nrSTART+1] =
{
/* chk: 0 1 Z y Y h H c i b B s S C I F */
{ /*0*/ 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ /*1*/ 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ /*Z*/ 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ /*y*/ 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ /*Y*/ 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1 },
{ /*h*/ 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1 },
{ /*H*/ 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1 },
{ /*c*/ 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1 },
{ /*i*/ 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1 },
{ /*b*/ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0 },
{ /*B*/ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0 },
{ /*s*/ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0 },
{ /*S*/ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0 },
{ /*C*/ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0 },
{ /*I*/ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 },
{ /*F*/ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
};
assert(checkType >= kRegType1nrSTART && checkType <= kRegType1nrEND);
#if 0
if (checkType < kRegType1nrSTART || checkType > kRegType1nrEND) {
LOG_VFY("Unexpected checkType %d (srcType=%d)", checkType, srcType);
assert(false);
return false;
}
#endif
//printf("convTab[%d][%d] = %d\n", srcType, checkType,
// convTab[srcType-kRegType1nrSTART][checkType-kRegType1nrSTART]);
if (srcType >= kRegType1nrSTART && srcType <= kRegType1nrEND)
return (bool) convTab[srcType-kRegType1nrSTART][checkType-kRegType1nrSTART];
return false;
}
/*
* Determine whether the category-2 types are compatible.
*/
static bool canConvertTo2(RegType srcType, RegType checkType)
{
return ((srcType == kRegTypeConstLo || srcType == checkType) &&
(checkType == kRegTypeLongLo || checkType == kRegTypeDoubleLo));
}
/*
* Determine whether or not "instrType" and "targetType" are compatible,
* for purposes of getting or setting a value in a field or array. The
* idea is that an instruction with a category 1nr type (say, aget-short
* or iput-boolean) is accessing a static field, instance field, or array
* entry, and we want to make sure sure that the operation is legal.
*
* At a minimum, source and destination must have the same width. We
* further refine this to assert that "short" and "char" are not
* compatible, because the sign-extension is different on the "get"
* operations.
*
* We're not considering the actual contents of the register, so we'll
* never get "pseudo-types" like kRegTypeZero or kRegTypePosShort. We
* could get kRegTypeUnknown in "targetType" if a field or array class
* lookup failed. Category 2 types and references are checked elsewhere.
*/
static bool checkFieldArrayStore1nr(RegType instrType, RegType targetType)
{
return (instrType == targetType);
}
/*
* Convert a VM PrimitiveType enum value to the equivalent RegType value.
*/
static RegType primitiveTypeToRegType(PrimitiveType primType)
{
switch (primType) {
case PRIM_BOOLEAN: return kRegTypeBoolean;
case PRIM_BYTE: return kRegTypeByte;
case PRIM_SHORT: return kRegTypeShort;
case PRIM_CHAR: return kRegTypeChar;
case PRIM_INT: return kRegTypeInteger;
case PRIM_LONG: return kRegTypeLongLo;
case PRIM_FLOAT: return kRegTypeFloat;
case PRIM_DOUBLE: return kRegTypeDoubleLo;
case PRIM_VOID:
default: {
assert(false);
return kRegTypeUnknown;
}
}
}
/*
* Convert a const derived RegType to the equivalent non-const RegType value.
* Does nothing if the argument type isn't const derived.
*/
static RegType constTypeToRegType(RegType constType)
{
switch (constType) {
case kRegTypeConstPosByte: return kRegTypePosByte;
case kRegTypeConstByte: return kRegTypeByte;
case kRegTypeConstPosShort: return kRegTypePosShort;
case kRegTypeConstShort: return kRegTypeShort;
case kRegTypeConstChar: return kRegTypeChar;
case kRegTypeConstInteger: return kRegTypeInteger;
default: {
return constType;
}
}
}
/*
* Given a 32-bit constant, return the most-restricted RegType enum entry
* that can hold the value. The types used here indicate the value came
* from a const instruction, and may not correctly represent the real type
* of the value. Upon use, a constant derived type is updated with the
* type from the use, which will be unambiguous.
*/
static char determineCat1Const(s4 value)
{
if (value < -32768)
return kRegTypeConstInteger;
else if (value < -128)
return kRegTypeConstShort;
else if (value < 0)
return kRegTypeConstByte;
else if (value == 0)
return kRegTypeZero;
else if (value == 1)
return kRegTypeOne;
else if (value < 128)
return kRegTypeConstPosByte;
else if (value < 32768)
return kRegTypeConstPosShort;
else if (value < 65536)
return kRegTypeConstChar;
else
return kRegTypeConstInteger;
}
/*
* Create a new uninitialized instance map.
*
* The map is allocated and populated with address entries. The addresses
* appear in ascending order to allow binary searching.
*
* Very few methods have 10 or more new-instance instructions; the
* majority have 0 or 1. Occasionally a static initializer will have 200+.
*
* TODO: merge this into the static pass or initRegisterTable; want to
* avoid walking through the instructions yet again just to set up this table
*/
UninitInstanceMap* dvmCreateUninitInstanceMap(const Method* meth,
const InsnFlags* insnFlags, int newInstanceCount)
{
const int insnsSize = dvmGetMethodInsnsSize(meth);
const u2* insns = meth->insns;
UninitInstanceMap* uninitMap;
bool isInit = false;
int idx, addr;
if (isInitMethod(meth)) {
newInstanceCount++;
isInit = true;
}
/*
* Allocate the header and map as a single unit.
*
* TODO: consider having a static instance so we can avoid allocations.
* I don't think the verifier is guaranteed to be single-threaded when
* running in the VM (rather than dexopt), so that must be taken into
* account.
*/
int size = offsetof(UninitInstanceMap, map) +
newInstanceCount * sizeof(uninitMap->map[0]);
uninitMap = (UninitInstanceMap*)calloc(1, size);
if (uninitMap == NULL)
return NULL;
uninitMap->numEntries = newInstanceCount;
idx = 0;
if (isInit) {
uninitMap->map[idx++].addr = kUninitThisArgAddr;
}
/*
* Run through and find the new-instance instructions.
*/
for (addr = 0; addr < insnsSize; /**/) {
int width = dvmInsnGetWidth(insnFlags, addr);
Opcode opcode = dexOpcodeFromCodeUnit(*insns);
if (opcode == OP_NEW_INSTANCE)
uninitMap->map[idx++].addr = addr;
addr += width;
insns += width;
}
assert(idx == newInstanceCount);
return uninitMap;
}
/*
* Free the map.
*/
void dvmFreeUninitInstanceMap(UninitInstanceMap* uninitMap)
{
free(uninitMap);
}
/*
* Set the class object associated with the instruction at "addr".
*
* Returns the map slot index, or -1 if the address isn't listed in the map
* (shouldn't happen) or if a class is already associated with the address
* (bad bytecode).
*
* Entries, once set, do not change -- a given address can only allocate
* one type of object.
*/
static int setUninitInstance(UninitInstanceMap* uninitMap, int addr,
ClassObject* clazz)
{
int idx;
assert(clazz != NULL);
#ifdef VERIFIER_STATS
gDvm.verifierStats.uninitSearches++;
#endif
/* TODO: binary search when numEntries > 8 */
for (idx = uninitMap->numEntries - 1; idx >= 0; idx--) {
if (uninitMap->map[idx].addr == addr) {
if (uninitMap->map[idx].clazz != NULL &&
uninitMap->map[idx].clazz != clazz)
{
LOG_VFY("VFY: addr %d already set to %p, not setting to %p",
addr, uninitMap->map[idx].clazz, clazz);
return -1; // already set to something else??
}
uninitMap->map[idx].clazz = clazz;
return idx;
}
}
LOG_VFY("VFY: addr %d not found in uninit map", addr);
assert(false); // shouldn't happen
return -1;
}
/*
* Get the class object at the specified index.
*/
static ClassObject* getUninitInstance(const UninitInstanceMap* uninitMap,
int idx)
{
assert(idx >= 0 && idx < uninitMap->numEntries);
return uninitMap->map[idx].clazz;
}
/* determine if "type" is actually an object reference (init/uninit/zero) */
static inline bool regTypeIsReference(RegType type) {
return (type > kRegTypeMAX || type == kRegTypeUninit ||
type == kRegTypeZero);
}
/* determine if "type" is an uninitialized object reference */
static inline bool regTypeIsUninitReference(RegType type) {
return ((type & kRegTypeUninitMask) == kRegTypeUninit);
}
/* convert the initialized reference "type" to a ClassObject pointer */
/* (does not expect uninit ref types or "zero") */
static ClassObject* regTypeInitializedReferenceToClass(RegType type)
{
assert(regTypeIsReference(type) && type != kRegTypeZero);
if ((type & 0x01) == 0) {
return (ClassObject*) type;
} else {
//LOG_VFY("VFY: attempted to use uninitialized reference");
return NULL;
}
}
/* extract the index into the uninitialized instance map table */
static inline int regTypeToUninitIndex(RegType type) {
assert(regTypeIsUninitReference(type));
return (type & ~kRegTypeUninitMask) >> kRegTypeUninitShift;
}
/* convert the reference "type" to a ClassObject pointer */
static ClassObject* regTypeReferenceToClass(RegType type,
const UninitInstanceMap* uninitMap)
{
assert(regTypeIsReference(type) && type != kRegTypeZero);
if (regTypeIsUninitReference(type)) {
assert(uninitMap != NULL);
return getUninitInstance(uninitMap, regTypeToUninitIndex(type));
} else {
return (ClassObject*) type;
}
}
/* convert the ClassObject pointer to an (initialized) register type */
static inline RegType regTypeFromClass(ClassObject* clazz) {
return (u4) clazz;
}
/* return the RegType for the uninitialized reference in slot "uidx" */
static RegType regTypeFromUninitIndex(int uidx) {
return (u4) (kRegTypeUninit | (uidx << kRegTypeUninitShift));
}
/*
* ===========================================================================
* Signature operations
* ===========================================================================
*/
/*
* Is this method a constructor?
*/
static bool isInitMethod(const Method* meth)
{
return (*meth->name == '<' && strcmp(meth->name+1, "init>") == 0);
}
/*
* Is this method a class initializer?
*/
#if 0
static bool isClassInitMethod(const Method* meth)
{
return (*meth->name == '<' && strcmp(meth->name+1, "clinit>") == 0);
}
#endif
/*
* Look up a class reference given as a simple string descriptor.
*
* If we can't find it, return a generic substitute when possible.
*/
static ClassObject* lookupClassByDescriptor(const Method* meth,
const char* pDescriptor, VerifyError* pFailure)
{
/*
* The javac compiler occasionally puts references to nonexistent
* classes in signatures. For example, if you have a non-static
* inner class with no constructor, the compiler provides
* a private <init> for you. Constructing the class
* requires <init>(parent), but the outer class can't call
* that because the method is private. So the compiler
* generates a package-scope <init>(parent,bogus) method that
* just calls the regular <init> (the "bogus" part being necessary
* to distinguish the signature of the synthetic method).
* Treating the bogus class as an instance of java.lang.Object
* allows the verifier to process the class successfully.
*/
//ALOGI("Looking up '%s'", typeStr);
ClassObject* clazz;
clazz = dvmFindClassNoInit(pDescriptor, meth->clazz->classLoader);
if (clazz == NULL) {
dvmClearOptException(dvmThreadSelf());
if (strchr(pDescriptor, '$') != NULL) {
ALOGV("VFY: unable to find class referenced in signature (%s)",
pDescriptor);
} else {
LOG_VFY("VFY: unable to find class referenced in signature (%s)",
pDescriptor);
}
if (pDescriptor[0] == '[') {
/* We are looking at an array descriptor. */
/*
* There should never be a problem loading primitive arrays.
*/
if (pDescriptor[1] != 'L' && pDescriptor[1] != '[') {
LOG_VFY("VFY: invalid char in signature in '%s'",
pDescriptor);
*pFailure = VERIFY_ERROR_GENERIC;
}
/*
* Try to continue with base array type. This will let
* us pass basic stuff (e.g. get array len) that wouldn't
* fly with an Object. This is NOT correct if the
* missing type is a primitive array, but we should never
* have a problem loading those. (I'm not convinced this
* is correct or even useful. Just use Object here?)
*/
clazz = dvmFindClassNoInit("[Ljava/lang/Object;",
meth->clazz->classLoader);
} else if (pDescriptor[0] == 'L') {
/*
* We are looking at a non-array reference descriptor;
* try to continue with base reference type.
*/
clazz = gDvm.classJavaLangObject;
} else {
/* We are looking at a primitive type. */
LOG_VFY("VFY: invalid char in signature in '%s'", pDescriptor);
*pFailure = VERIFY_ERROR_GENERIC;
}
if (clazz == NULL) {
*pFailure = VERIFY_ERROR_GENERIC;
}
}
if (dvmIsPrimitiveClass(clazz)) {
LOG_VFY("VFY: invalid use of primitive type '%s'", pDescriptor);
*pFailure = VERIFY_ERROR_GENERIC;
clazz = NULL;
}
return clazz;
}
/*
* Look up a class reference in a signature. Could be an arg or the
* return value.
*
* Advances "*pSig" to the last character in the signature (that is, to
* the ';').
*
* NOTE: this is also expected to verify the signature.
*/
static ClassObject* lookupSignatureClass(const Method* meth, const char** pSig,
VerifyError* pFailure)
{
const char* sig = *pSig;
const char* endp = sig;
assert(sig != NULL && *sig == 'L');
while (*++endp != ';' && *endp != '\0')
;
if (*endp != ';') {
LOG_VFY("VFY: bad signature component '%s' (missing ';')", sig);
*pFailure = VERIFY_ERROR_GENERIC;
return NULL;
}
endp++; /* Advance past the ';'. */
int typeLen = endp - sig;
char typeStr[typeLen+1]; /* +1 for the '\0' */
memcpy(typeStr, sig, typeLen);
typeStr[typeLen] = '\0';
*pSig = endp - 1; /* - 1 so that *pSig points at, not past, the ';' */
return lookupClassByDescriptor(meth, typeStr, pFailure);
}
/*
* Look up an array class reference in a signature. Could be an arg or the
* return value.
*
* Advances "*pSig" to the last character in the signature.
*
* NOTE: this is also expected to verify the signature.
*/
static ClassObject* lookupSignatureArrayClass(const Method* meth,
const char** pSig, VerifyError* pFailure)
{
const char* sig = *pSig;
const char* endp = sig;
assert(sig != NULL && *sig == '[');
/* find the end */
while (*++endp == '[' && *endp != '\0')
;
if (*endp == 'L') {
while (*++endp != ';' && *endp != '\0')
;
if (*endp != ';') {
LOG_VFY("VFY: bad signature component '%s' (missing ';')", sig);
*pFailure = VERIFY_ERROR_GENERIC;
return NULL;
}
}
int typeLen = endp - sig +1;
char typeStr[typeLen+1];
memcpy(typeStr, sig, typeLen);
typeStr[typeLen] = '\0';
*pSig = endp;
return lookupClassByDescriptor(meth, typeStr, pFailure);
}
/*
* Set the register types for the first instruction in the method based on
* the method signature.
*
* This has the side-effect of validating the signature.
*
* Returns "true" on success.
*/
static bool setTypesFromSignature(const Method* meth, RegType* regTypes,
UninitInstanceMap* uninitMap)
{
DexParameterIterator iterator;
int actualArgs, expectedArgs, argStart;
VerifyError failure = VERIFY_ERROR_NONE;
const char* descriptor;
dexParameterIteratorInit(&iterator, &meth->prototype);
argStart = meth->registersSize - meth->insSize;
expectedArgs = meth->insSize; /* long/double count as two */
actualArgs = 0;
assert(argStart >= 0); /* should have been verified earlier */
/*
* Include the "this" pointer.
*/
if (!dvmIsStaticMethod(meth)) {
/*
* If this is a constructor for a class other than java.lang.Object,
* mark the first ("this") argument as uninitialized. This restricts
* field access until the superclass constructor is called.
*/
if (isInitMethod(meth) && meth->clazz != gDvm.classJavaLangObject) {
int uidx = setUninitInstance(uninitMap, kUninitThisArgAddr,
meth->clazz);
assert(uidx == 0);
regTypes[argStart + actualArgs] = regTypeFromUninitIndex(uidx);
} else {
regTypes[argStart + actualArgs] = regTypeFromClass(meth->clazz);
}
actualArgs++;
}
for (;;) {
descriptor = dexParameterIteratorNextDescriptor(&iterator);
if (descriptor == NULL) {
break;
}
if (actualArgs >= expectedArgs) {
LOG_VFY("VFY: expected %d args, found more (%s)",
expectedArgs, descriptor);
goto bad_sig;
}
switch (*descriptor) {
case 'L':
case '[':
/*
* We assume that reference arguments are initialized. The
* only way it could be otherwise (assuming the caller was
* verified) is if the current method is <init>, but in that
* case it's effectively considered initialized the instant
* we reach here (in the sense that we can return without
* doing anything or call virtual methods).
*/
{
ClassObject* clazz =
lookupClassByDescriptor(meth, descriptor, &failure);
if (!VERIFY_OK(failure))
goto bad_sig;
regTypes[argStart + actualArgs] = regTypeFromClass(clazz);
}
actualArgs++;
break;
case 'Z':
regTypes[argStart + actualArgs] = kRegTypeBoolean;
actualArgs++;
break;
case 'C':
regTypes[argStart + actualArgs] = kRegTypeChar;
actualArgs++;
break;
case 'B':
regTypes[argStart + actualArgs] = kRegTypeByte;
actualArgs++;
break;
case 'I':
regTypes[argStart + actualArgs] = kRegTypeInteger;
actualArgs++;
break;
case 'S':
regTypes[argStart + actualArgs] = kRegTypeShort;
actualArgs++;
break;
case 'F':
regTypes[argStart + actualArgs] = kRegTypeFloat;
actualArgs++;
break;
case 'D':
regTypes[argStart + actualArgs] = kRegTypeDoubleLo;
regTypes[argStart + actualArgs +1] = kRegTypeDoubleHi;
actualArgs += 2;
break;
case 'J':
regTypes[argStart + actualArgs] = kRegTypeLongLo;
regTypes[argStart + actualArgs +1] = kRegTypeLongHi;
actualArgs += 2;
break;
default:
LOG_VFY("VFY: unexpected signature type char '%c'", *descriptor);
goto bad_sig;
}
}
if (actualArgs != expectedArgs) {
LOG_VFY("VFY: expected %d args, found %d", expectedArgs, actualArgs);
goto bad_sig;
}
descriptor = dexProtoGetReturnType(&meth->prototype);
/*
* Validate return type. We don't do the type lookup; just want to make
* sure that it has the right format. Only major difference from the
* method argument format is that 'V' is supported.
*/
switch (*descriptor) {
case 'I':
case 'C':
case 'S':
case 'B':
case 'Z':
case 'V':
case 'F':
case 'D':
case 'J':
if (*(descriptor+1) != '\0')
goto bad_sig;
break;
case '[':
/* single/multi, object/primitive */
while (*++descriptor == '[')
;
if (*descriptor == 'L') {
while (*++descriptor != ';' && *descriptor != '\0')
;
if (*descriptor != ';')
goto bad_sig;
} else {
if (*(descriptor+1) != '\0')
goto bad_sig;
}
break;
case 'L':
/* could be more thorough here, but shouldn't be required */
while (*++descriptor != ';' && *descriptor != '\0')
;
if (*descriptor != ';')
goto bad_sig;
break;
default:
goto bad_sig;
}
return true;
//fail:
// LOG_VFY_METH(meth, "VFY: bad sig");
// return false;
bad_sig:
{
char* desc = dexProtoCopyMethodDescriptor(&meth->prototype);
LOG_VFY("VFY: bad signature '%s' for %s.%s",
desc, meth->clazz->descriptor, meth->name);
free(desc);
}
return false;
}
/*
* Return the register type for the method. We can't just use the
* already-computed DalvikJniReturnType, because if it's a reference type
* we need to do the class lookup.
*
* Returned references are assumed to be initialized.
*
* Returns kRegTypeUnknown for "void".
*/
static RegType getMethodReturnType(const Method* meth)
{
RegType type;
const char* descriptor = dexProtoGetReturnType(&meth->prototype);
switch (*descriptor) {
case 'I':
type = kRegTypeInteger;
break;
case 'C':
type = kRegTypeChar;
break;
case 'S':
type = kRegTypeShort;
break;
case 'B':
type = kRegTypeByte;
break;
case 'Z':
type = kRegTypeBoolean;
break;
case 'V':
type = kRegTypeUnknown;
break;
case 'F':
type = kRegTypeFloat;
break;
case 'D':
type = kRegTypeDoubleLo;
break;
case 'J':
type = kRegTypeLongLo;
break;
case 'L':
case '[':
{
VerifyError failure = VERIFY_ERROR_NONE;
ClassObject* clazz =
lookupClassByDescriptor(meth, descriptor, &failure);
assert(VERIFY_OK(failure));
type = regTypeFromClass(clazz);
}
break;
default:
/* we verified signature return type earlier, so this is impossible */
assert(false);
type = kRegTypeConflict;
break;
}
return type;
}
/*
* Convert a single-character signature value (i.e. a primitive type) to
* the corresponding RegType. This is intended for access to object fields
* holding primitive types.
*
* Returns kRegTypeUnknown for objects, arrays, and void.
*/
static RegType primSigCharToRegType(char sigChar)
{
RegType type;
switch (sigChar) {
case 'I':
type = kRegTypeInteger;
break;
case 'C':
type = kRegTypeChar;
break;
case 'S':
type = kRegTypeShort;
break;
case 'B':
type = kRegTypeByte;
break;
case 'Z':
type = kRegTypeBoolean;
break;
case 'F':
type = kRegTypeFloat;
break;
case 'D':
type = kRegTypeDoubleLo;
break;
case 'J':
type = kRegTypeLongLo;
break;
case 'V':
case 'L':
case '[':
type = kRegTypeUnknown;
break;
default:
assert(false);
type = kRegTypeUnknown;
break;
}
return type;
}
/*
* See if the method matches the MethodType.
*/
static bool isCorrectInvokeKind(MethodType methodType, Method* resMethod)
{
switch (methodType) {
case METHOD_DIRECT:
return dvmIsDirectMethod(resMethod);
case METHOD_STATIC:
return dvmIsStaticMethod(resMethod);
case METHOD_VIRTUAL:
case METHOD_INTERFACE:
return !dvmIsDirectMethod(resMethod);
default:
return false;
}
}
/*
* Verify the arguments to a method. We're executing in "method", making
* a call to the method reference in vB.
*
* If this is a "direct" invoke, we allow calls to <init>. For calls to
* <init>, the first argument may be an uninitialized reference. Otherwise,
* calls to anything starting with '<' will be rejected, as will any
* uninitialized reference arguments.
*
* For non-static method calls, this will verify that the method call is
* appropriate for the "this" argument.
*
* The method reference is in vBBBB. The "isRange" parameter determines
* whether we use 0-4 "args" values or a range of registers defined by
* vAA and vCCCC.
*
* Widening conversions on integers and references are allowed, but
* narrowing conversions are not.
*
* Returns the resolved method on success, NULL on failure (with *pFailure
* set appropriately).
*/
static Method* verifyInvocationArgs(const Method* meth,
RegisterLine* registerLine, const int insnRegCount,
const DecodedInstruction* pDecInsn, UninitInstanceMap* uninitMap,
MethodType methodType, bool isRange, bool isSuper, VerifyError* pFailure)
{
Method* resMethod;
char* sigOriginal = NULL;
const char* sig;
int expectedArgs;
int actualArgs;
/*
* Resolve the method. This could be an abstract or concrete method
* depending on what sort of call we're making.
*/
if (methodType == METHOD_INTERFACE) {
resMethod = dvmOptResolveInterfaceMethod(meth->clazz, pDecInsn->vB);
} else {
resMethod = dvmOptResolveMethod(meth->clazz, pDecInsn->vB, methodType,
pFailure);
}
if (resMethod == NULL) {
/* failed; print a meaningful failure message */
DexFile* pDexFile = meth->clazz->pDvmDex->pDexFile;
const DexMethodId* pMethodId = dexGetMethodId(pDexFile, pDecInsn->vB);
const char* methodName = dexStringById(pDexFile, pMethodId->nameIdx);
char* methodDesc = dexCopyDescriptorFromMethodId(pDexFile, pMethodId);
const char* classDescriptor = dexStringByTypeIdx(pDexFile, pMethodId->classIdx);
if (!gDvm.optimizing) {
std::string dotMissingClass =
dvmHumanReadableDescriptor(classDescriptor);
std::string dotMethClass =
dvmHumanReadableDescriptor(meth->clazz->descriptor);
ALOGI("Could not find method %s.%s, referenced from method %s.%s",
dotMissingClass.c_str(), methodName,
dotMethClass.c_str(), meth->name);
}
LOG_VFY("VFY: unable to resolve %s method %u: %s.%s %s",
dvmMethodTypeStr(methodType), pDecInsn->vB,
classDescriptor, methodName, methodDesc);
free(methodDesc);
if (VERIFY_OK(*pFailure)) /* not set for interface resolve */
*pFailure = VERIFY_ERROR_NO_METHOD;
goto fail;
}
/*
* Only time you can explicitly call a method starting with '<' is when
* making a "direct" invocation on "<init>". There are additional
* restrictions but we don't enforce them here.
*/
if (resMethod->name[0] == '<') {
if (methodType != METHOD_DIRECT || !isInitMethod(resMethod)) {
LOG_VFY("VFY: invalid call to %s.%s",
resMethod->clazz->descriptor, resMethod->name);
goto bad_sig;
}
}
/*
* See if the method type implied by the invoke instruction matches the
* access flags for the target method.
*/
if (!isCorrectInvokeKind(methodType, resMethod)) {
LOG_VFY("VFY: invoke type does not match method type of %s.%s",
resMethod->clazz->descriptor, resMethod->name);
goto fail;
}
/*
* If we're using invoke-super(method), make sure that the executing
* method's class' superclass has a vtable entry for the target method.
*/
if (isSuper) {
assert(methodType == METHOD_VIRTUAL);
ClassObject* super = meth->clazz->super;
if (super == NULL || resMethod->methodIndex > super->vtableCount) {
char* desc = dexProtoCopyMethodDescriptor(&resMethod->prototype);
LOG_VFY("VFY: invalid invoke-super from %s.%s to super %s.%s %s",
meth->clazz->descriptor, meth->name,
(super == NULL) ? "-" : super->descriptor,
resMethod->name, desc);
free(desc);
*pFailure = VERIFY_ERROR_NO_METHOD;
goto fail;
}
}
/*
* We use vAA as our expected arg count, rather than resMethod->insSize,
* because we need to match the call to the signature. Also, we might
* might be calling through an abstract method definition (which doesn't
* have register count values).
*/
sigOriginal = dexProtoCopyMethodDescriptor(&resMethod->prototype);
sig = sigOriginal;
expectedArgs = pDecInsn->vA;
actualArgs = 0;
/* caught by static verifier */
assert(isRange || expectedArgs <= 5);
if (expectedArgs > meth->outsSize) {
LOG_VFY("VFY: invalid arg count (%d) exceeds outsSize (%d)",
expectedArgs, meth->outsSize);
goto fail;
}
if (*sig++ != '(')
goto bad_sig;
/*
* Check the "this" argument, which must be an instance of the class
* that declared the method. For an interface class, we don't do the
* full interface merge, so we can't do a rigorous check here (which
* is okay since we have to do it at runtime).
*/
if (!dvmIsStaticMethod(resMethod)) {
ClassObject* actualThisRef;
RegType actualArgType;
actualArgType = getInvocationThis(registerLine, pDecInsn, pFailure);
if (!VERIFY_OK(*pFailure))
goto fail;
if (regTypeIsUninitReference(actualArgType) && resMethod->name[0] != '<')
{
LOG_VFY("VFY: 'this' arg must be initialized");
goto fail;
}
if (methodType != METHOD_INTERFACE && actualArgType != kRegTypeZero) {
actualThisRef = regTypeReferenceToClass(actualArgType, uninitMap);
if (!dvmInstanceof(actualThisRef, resMethod->clazz)) {
LOG_VFY("VFY: 'this' arg '%s' not instance of '%s'",
actualThisRef->descriptor,
resMethod->clazz->descriptor);
goto fail;
}
}
actualArgs++;
}
/*
* Process the target method's signature. This signature may or may not
* have been verified, so we can't assume it's properly formed.
*/
while (*sig != '\0' && *sig != ')') {
if (actualArgs >= expectedArgs) {
LOG_VFY("VFY: expected %d args, found more (%c)",
expectedArgs, *sig);
goto bad_sig;
}
u4 getReg;
if (isRange)
getReg = pDecInsn->vC + actualArgs;
else
getReg = pDecInsn->arg[actualArgs];
switch (*sig) {
case 'L':
{
ClassObject* clazz = lookupSignatureClass(meth, &sig, pFailure);
if (!VERIFY_OK(*pFailure))
goto bad_sig;
verifyRegisterType(registerLine, getReg,
regTypeFromClass(clazz), pFailure);
if (!VERIFY_OK(*pFailure)) {
LOG_VFY("VFY: bad arg %d (into %s)",
actualArgs, clazz->descriptor);
goto bad_sig;
}
}
actualArgs++;
break;
case '[':
{
ClassObject* clazz =
lookupSignatureArrayClass(meth, &sig, pFailure);
if (!VERIFY_OK(*pFailure))
goto bad_sig;
verifyRegisterType(registerLine, getReg,
regTypeFromClass(clazz), pFailure);
if (!VERIFY_OK(*pFailure)) {
LOG_VFY("VFY: bad arg %d (into %s)",
actualArgs, clazz->descriptor);
goto bad_sig;
}
}
actualArgs++;
break;
case 'Z':
verifyRegisterType(registerLine, getReg, kRegTypeBoolean, pFailure);
actualArgs++;
break;
case 'C':
verifyRegisterType(registerLine, getReg, kRegTypeChar, pFailure);
actualArgs++;
break;
case 'B':
verifyRegisterType(registerLine, getReg, kRegTypeByte, pFailure);
actualArgs++;
break;
case 'I':
verifyRegisterType(registerLine, getReg, kRegTypeInteger, pFailure);
actualArgs++;
break;
case 'S':
verifyRegisterType(registerLine, getReg, kRegTypeShort, pFailure);
actualArgs++;
break;
case 'F':
verifyRegisterType(registerLine, getReg, kRegTypeFloat, pFailure);
actualArgs++;
break;
case 'D':
verifyRegisterType(registerLine, getReg, kRegTypeDoubleLo, pFailure);
actualArgs += 2;
break;
case 'J':
verifyRegisterType(registerLine, getReg, kRegTypeLongLo, pFailure);
actualArgs += 2;
break;
default:
LOG_VFY("VFY: invocation target: bad signature type char '%c'",
*sig);
goto bad_sig;
}
sig++;
}
if (*sig != ')') {
char* desc = dexProtoCopyMethodDescriptor(&resMethod->prototype);
LOG_VFY("VFY: invocation target: bad signature '%s'", desc);
free(desc);
goto bad_sig;
}
if (actualArgs != expectedArgs) {
LOG_VFY("VFY: expected %d args, found %d", expectedArgs, actualArgs);
goto bad_sig;
}
free(sigOriginal);
return resMethod;
bad_sig:
if (resMethod != NULL) {
char* desc = dexProtoCopyMethodDescriptor(&resMethod->prototype);
LOG_VFY("VFY: rejecting call to %s.%s %s",
resMethod->clazz->descriptor, resMethod->name, desc);
free(desc);
}
fail:
free(sigOriginal);
if (*pFailure == VERIFY_ERROR_NONE)
*pFailure = VERIFY_ERROR_GENERIC;
return NULL;
}
/*
* Get the class object for the type of data stored in a field. This isn't
* stored in the Field struct, so we have to recover it from the signature.
*
* This only works for reference types. Don't call this for primitive types.
*
* If we can't find the class, we return java.lang.Object, so that
* verification can continue if a field is only accessed in trivial ways.
*/
static ClassObject* getFieldClass(const Method* meth, const Field* field)
{
ClassObject* fieldClass;
const char* signature = field->signature;
if ((*signature == 'L') || (*signature == '[')) {
fieldClass = dvmFindClassNoInit(signature,
meth->clazz->classLoader);
} else {
return NULL;
}
if (fieldClass == NULL) {
dvmClearOptException(dvmThreadSelf());
ALOGV("VFY: unable to find class '%s' for field %s.%s, trying Object",
field->signature, meth->clazz->descriptor, field->name);
fieldClass = gDvm.classJavaLangObject;
} else {
assert(!dvmIsPrimitiveClass(fieldClass));
}
return fieldClass;
}
/*
* ===========================================================================
* Register operations
* ===========================================================================
*/
/*
* Get the type of register N.
*
* The register index was validated during the static pass, so we don't
* need to check it here.
*/
static inline RegType getRegisterType(const RegisterLine* registerLine, u4 vsrc)
{
return registerLine->regTypes[vsrc];
}
/*
* Get the value from a register, and cast it to a ClassObject. Sets
* "*pFailure" if something fails.
*
* This fails if the register holds an uninitialized class.
*
* If the register holds kRegTypeZero, this returns a NULL pointer.
*/
static ClassObject* getClassFromRegister(const RegisterLine* registerLine,
u4 vsrc, VerifyError* pFailure)
{
ClassObject* clazz = NULL;
RegType type;
/* get the element type of the array held in vsrc */
type = getRegisterType(registerLine, vsrc);
/* if "always zero", we allow it to fail at runtime */
if (type == kRegTypeZero)
goto bail;
if (!regTypeIsReference(type)) {
LOG_VFY("VFY: tried to get class from non-ref register v%d (type=%d)",
vsrc, type);
*pFailure = VERIFY_ERROR_GENERIC;
goto bail;
}
if (regTypeIsUninitReference(type)) {
LOG_VFY("VFY: register %u holds uninitialized reference", vsrc);
*pFailure = VERIFY_ERROR_GENERIC;
goto bail;
}
clazz = regTypeInitializedReferenceToClass(type);
bail:
return clazz;
}
/*
* Get the "this" pointer from a non-static method invocation. This
* returns the RegType so the caller can decide whether it needs the
* reference to be initialized or not. (Can also return kRegTypeZero
* if the reference can only be zero at this point.)
*
* The argument count is in vA, and the first argument is in vC, for both
* "simple" and "range" versions. We just need to make sure vA is >= 1
* and then return vC.
*/
static RegType getInvocationThis(const RegisterLine* registerLine,
const DecodedInstruction* pDecInsn, VerifyError* pFailure)
{
RegType thisType = kRegTypeUnknown;
if (pDecInsn->vA < 1) {
LOG_VFY("VFY: invoke lacks 'this'");
*pFailure = VERIFY_ERROR_GENERIC;
goto bail;
}
/* get the element type of the array held in vsrc */
thisType = getRegisterType(registerLine, pDecInsn->vC);
if (!regTypeIsReference(thisType)) {
LOG_VFY("VFY: tried to get class from non-ref register v%d (type=%d)",
pDecInsn->vC, thisType);
*pFailure = VERIFY_ERROR_GENERIC;
goto bail;
}
bail:
return thisType;
}
/*
* Set the type of register N, verifying that the register is valid. If
* "newType" is the "Lo" part of a 64-bit value, register N+1 will be
* set to "newType+1".
*
* The register index was validated during the static pass, so we don't
* need to check it here.
*
* TODO: clear mon stack bits
*/
static void setRegisterType(RegisterLine* registerLine, u4 vdst,
RegType newType)
{
RegType* insnRegs = registerLine->regTypes;
switch (newType) {
case kRegTypeUnknown:
case kRegTypeBoolean:
case kRegTypeOne:
case kRegTypeConstByte:
case kRegTypeConstPosByte:
case kRegTypeConstShort:
case kRegTypeConstPosShort:
case kRegTypeConstChar:
case kRegTypeConstInteger:
case kRegTypeByte:
case kRegTypePosByte:
case kRegTypeShort:
case kRegTypePosShort:
case kRegTypeChar:
case kRegTypeInteger:
case kRegTypeFloat:
case kRegTypeZero:
case kRegTypeUninit:
insnRegs[vdst] = newType;
break;
case kRegTypeConstLo:
case kRegTypeLongLo:
case kRegTypeDoubleLo:
insnRegs[vdst] = newType;
insnRegs[vdst+1] = newType+1;
break;
case kRegTypeConstHi:
case kRegTypeLongHi:
case kRegTypeDoubleHi:
/* should never set these explicitly */
ALOGE("BUG: explicit set of high register type");
dvmAbort();
break;
default:
/* can't switch for ref types, so we check explicitly */
if (regTypeIsReference(newType)) {
insnRegs[vdst] = newType;
/*
* In most circumstances we won't see a reference to a primitive
* class here (e.g. "D"), since that would mean the object in the
* register is actually a primitive type. It can happen as the
* result of an assumed-successful check-cast instruction in
* which the second argument refers to a primitive class. (In
* practice, such an instruction will always throw an exception.)
*
* This is not an issue for instructions like const-class, where
* the object in the register is a java.lang.Class instance.
*/
break;
}
/* bad type - fall through */
case kRegTypeConflict: // should only be set during a merge
ALOGE("BUG: set register to unknown type %d", newType);
dvmAbort();
break;
}
/*
* Clear the monitor entry bits for this register.
*/
if (registerLine->monitorEntries != NULL)
registerLine->monitorEntries[vdst] = 0;
}
/*
* Verify that the contents of the specified register have the specified
* type (or can be converted to it through an implicit widening conversion).
*
* This will modify the type of the source register if it was originally
* derived from a constant to prevent mixing of int/float and long/double.
*
* If "vsrc" is a reference, both it and the "vsrc" register must be
* initialized ("vsrc" may be Zero). This will verify that the value in
* the register is an instance of checkType, or if checkType is an
* interface, verify that the register implements checkType.
*/
static void verifyRegisterType(RegisterLine* registerLine, u4 vsrc,
RegType checkType, VerifyError* pFailure)
{
const RegType* insnRegs = registerLine->regTypes;
RegType srcType = insnRegs[vsrc];
//ALOGD("check-reg v%u = %d", vsrc, checkType);
switch (checkType) {
case kRegTypeFloat:
case kRegTypeBoolean:
case kRegTypePosByte:
case kRegTypeByte:
case kRegTypePosShort:
case kRegTypeShort:
case kRegTypeChar:
case kRegTypeInteger:
if (!canConvertTo1nr(srcType, checkType)) {
LOG_VFY("VFY: register1 v%u type %d, wanted %d",
vsrc, srcType, checkType);
*pFailure = VERIFY_ERROR_GENERIC;
break;
}
/* Update type if result is float */
if (checkType == kRegTypeFloat) {
setRegisterType(registerLine, vsrc, checkType);
} else {
/* Update const type to actual type after use */
setRegisterType(registerLine, vsrc, constTypeToRegType(srcType));
}
break;
case kRegTypeLongLo:
case kRegTypeDoubleLo:
if (insnRegs[vsrc+1] != srcType+1) {
LOG_VFY("VFY: register2 v%u-%u values %d,%d",
vsrc, vsrc+1, insnRegs[vsrc], insnRegs[vsrc+1]);
*pFailure = VERIFY_ERROR_GENERIC;
break;
} else if (!canConvertTo2(srcType, checkType)) {
LOG_VFY("VFY: register2 v%u type %d, wanted %d",
vsrc, srcType, checkType);
*pFailure = VERIFY_ERROR_GENERIC;
break;
}
/* Update type if source is from const */
if (srcType == kRegTypeConstLo) {
setRegisterType(registerLine, vsrc, checkType);
}
break;
case kRegTypeConstLo:
case kRegTypeConstHi:
case kRegTypeLongHi:
case kRegTypeDoubleHi:
case kRegTypeZero:
case kRegTypeOne:
case kRegTypeUnknown:
case kRegTypeConflict:
/* should never be checking for these explicitly */
assert(false);
*pFailure = VERIFY_ERROR_GENERIC;
return;
case kRegTypeUninit:
default:
/* make sure checkType is initialized reference */
if (!regTypeIsReference(checkType)) {
LOG_VFY("VFY: unexpected check type %d", checkType);
assert(false);
*pFailure = VERIFY_ERROR_GENERIC;
break;
}
if (regTypeIsUninitReference(checkType)) {
LOG_VFY("VFY: uninitialized ref not expected as reg check");
*pFailure = VERIFY_ERROR_GENERIC;
break;
}
/* make sure srcType is initialized reference or always-NULL */
if (!regTypeIsReference(srcType)) {
LOG_VFY("VFY: register1 v%u type %d, wanted ref", vsrc, srcType);
*pFailure = VERIFY_ERROR_GENERIC;
break;
}
if (regTypeIsUninitReference(srcType)) {
LOG_VFY("VFY: register1 v%u holds uninitialized ref", vsrc);
*pFailure = VERIFY_ERROR_GENERIC;
break;
}
/* if the register isn't Zero, make sure it's an instance of check */
if (srcType != kRegTypeZero) {
ClassObject* srcClass = regTypeInitializedReferenceToClass(srcType);
ClassObject* checkClass = regTypeInitializedReferenceToClass(checkType);
assert(srcClass != NULL);
assert(checkClass != NULL);
if (dvmIsInterfaceClass(checkClass)) {
/*
* All objects implement all interfaces as far as the
* verifier is concerned. The runtime has to sort it out.
* See comments above findCommonSuperclass.
*/
/*
if (srcClass != checkClass &&
!dvmImplements(srcClass, checkClass))
{
LOG_VFY("VFY: %s does not implement %s",
srcClass->descriptor, checkClass->descriptor);
*pFailure = VERIFY_ERROR_GENERIC;
}
*/
} else {
if (!dvmInstanceof(srcClass, checkClass)) {
LOG_VFY("VFY: %s is not instance of %s",
srcClass->descriptor, checkClass->descriptor);
*pFailure = VERIFY_ERROR_GENERIC;
}
}
}
break;
}
}
/*
* Set the type of the "result" register.
*/
static void setResultRegisterType(RegisterLine* registerLine,
const int insnRegCount, RegType newType)
{
setRegisterType(registerLine, RESULT_REGISTER(insnRegCount), newType);
}
/*
* Update all registers holding "uninitType" to instead hold the
* corresponding initialized reference type. This is called when an
* appropriate <init> method is invoked -- all copies of the reference
* must be marked as initialized.
*/
static void markRefsAsInitialized(RegisterLine* registerLine, int insnRegCount,
UninitInstanceMap* uninitMap, RegType uninitType, VerifyError* pFailure)
{
RegType* insnRegs = registerLine->regTypes;
ClassObject* clazz;
RegType initType;
int i, changed;
clazz = getUninitInstance(uninitMap, regTypeToUninitIndex(uninitType));
if (clazz == NULL) {
ALOGE("VFY: unable to find type=%#x (idx=%d)",
uninitType, regTypeToUninitIndex(uninitType));
*pFailure = VERIFY_ERROR_GENERIC;
return;
}
initType = regTypeFromClass(clazz);
changed = 0;
for (i = 0; i < insnRegCount; i++) {
if (insnRegs[i] == uninitType) {
insnRegs[i] = initType;
changed++;
}
}
//ALOGD("VFY: marked %d registers as initialized", changed);
assert(changed > 0);
return;
}
/*
* We're creating a new instance of class C at address A. Any registers
* holding instances previously created at address A must be initialized
* by now. If not, we mark them as "conflict" to prevent them from being
* used (otherwise, markRefsAsInitialized would mark the old ones and the
* new ones at the same time).
*/
static void markUninitRefsAsInvalid(RegisterLine* registerLine,
int insnRegCount, UninitInstanceMap* uninitMap, RegType uninitType)
{
RegType* insnRegs = registerLine->regTypes;
int i, changed;
changed = 0;
for (i = 0; i < insnRegCount; i++) {
if (insnRegs[i] == uninitType) {
insnRegs[i] = kRegTypeConflict;
if (registerLine->monitorEntries != NULL)
registerLine->monitorEntries[i] = 0;
changed++;
}
}
//if (changed)
// ALOGD("VFY: marked %d uninitialized registers as invalid", changed);
}
/*
* Find the register line for the specified instruction in the current method.
*/
static inline RegisterLine* getRegisterLine(const RegisterTable* regTable,
int insnIdx)
{
return &regTable->registerLines[insnIdx];
}
/*
* Copy a register line.
*/
static inline void copyRegisterLine(RegisterLine* dst, const RegisterLine* src,
size_t numRegs)
{
memcpy(dst->regTypes, src->regTypes, numRegs * sizeof(RegType));
assert((src->monitorEntries == NULL && dst->monitorEntries == NULL) ||
(src->monitorEntries != NULL && dst->monitorEntries != NULL));
if (dst->monitorEntries != NULL) {
assert(dst->monitorStack != NULL);
memcpy(dst->monitorEntries, src->monitorEntries,
numRegs * sizeof(MonitorEntries));
memcpy(dst->monitorStack, src->monitorStack,
kMaxMonitorStackDepth * sizeof(u4));
dst->monitorStackTop = src->monitorStackTop;
}
}
/*
* Copy a register line into the table.
*/
static inline void copyLineToTable(RegisterTable* regTable, int insnIdx,
const RegisterLine* src)
{
RegisterLine* dst = getRegisterLine(regTable, insnIdx);
assert(dst->regTypes != NULL);
copyRegisterLine(dst, src, regTable->insnRegCountPlus);
}
/*
* Copy a register line out of the table.
*/
static inline void copyLineFromTable(RegisterLine* dst,
const RegisterTable* regTable, int insnIdx)
{
RegisterLine* src = getRegisterLine(regTable, insnIdx);
assert(src->regTypes != NULL);
copyRegisterLine(dst, src, regTable->insnRegCountPlus);
}
#ifndef NDEBUG
/*
* Compare two register lines. Returns 0 if they match.
*
* Using this for a sort is unwise, since the value can change based on
* machine endianness.
*/
static inline int compareLineToTable(const RegisterTable* regTable,
int insnIdx, const RegisterLine* line2)
{
const RegisterLine* line1 = getRegisterLine(regTable, insnIdx);
if (line1->monitorEntries != NULL) {
int result;
if (line2->monitorEntries == NULL)
return 1;
result = memcmp(line1->monitorEntries, line2->monitorEntries,
regTable->insnRegCountPlus * sizeof(MonitorEntries));
if (result != 0) {
LOG_VFY("monitorEntries mismatch");
return result;
}
result = line1->monitorStackTop - line2->monitorStackTop;
if (result != 0) {
LOG_VFY("monitorStackTop mismatch");
return result;
}
result = memcmp(line1->monitorStack, line2->monitorStack,
line1->monitorStackTop);
if (result != 0) {
LOG_VFY("monitorStack mismatch");
return result;
}
}
return memcmp(line1->regTypes, line2->regTypes,
regTable->insnRegCountPlus * sizeof(RegType));
}
#endif
/*
* Register type categories, for type checking.
*
* The spec says category 1 includes boolean, byte, char, short, int, float,
* reference, and returnAddress. Category 2 includes long and double.
*
* We treat object references separately, so we have "category1nr". We
* don't support jsr/ret, so there is no "returnAddress" type.
*/
enum TypeCategory {
kTypeCategoryUnknown = 0,
kTypeCategory1nr, // boolean, byte, char, short, int, float
kTypeCategory2, // long, double
kTypeCategoryRef, // object reference
};
/*
* See if "type" matches "cat". All we're really looking for here is that
* we're not mixing and matching 32-bit and 64-bit quantities, and we're
* not mixing references with numerics. (For example, the arguments to
* "a < b" could be integers of different sizes, but they must both be
* integers. Dalvik is less specific about int vs. float, so we treat them
* as equivalent here.)
*
* For category 2 values, "type" must be the "low" half of the value.
*
* Sets "*pFailure" if something looks wrong.
*/
static void checkTypeCategory(RegType type, TypeCategory cat,
VerifyError* pFailure)
{
switch (cat) {
case kTypeCategory1nr:
switch (type) {
case kRegTypeZero:
case kRegTypeOne:
case kRegTypeBoolean:
case kRegTypeConstPosByte:
case kRegTypeConstByte:
case kRegTypeConstPosShort:
case kRegTypeConstShort:
case kRegTypeConstChar:
case kRegTypeConstInteger:
case kRegTypePosByte:
case kRegTypeByte:
case kRegTypePosShort:
case kRegTypeShort:
case kRegTypeChar:
case kRegTypeInteger:
case kRegTypeFloat:
break;
default:
*pFailure = VERIFY_ERROR_GENERIC;
break;
}
break;
case kTypeCategory2:
switch (type) {
case kRegTypeConstLo:
case kRegTypeLongLo:
case kRegTypeDoubleLo:
break;
default:
*pFailure = VERIFY_ERROR_GENERIC;
break;
}
break;
case kTypeCategoryRef:
if (type != kRegTypeZero && !regTypeIsReference(type))
*pFailure = VERIFY_ERROR_GENERIC;
break;
default:
assert(false);
*pFailure = VERIFY_ERROR_GENERIC;
break;
}
}
/*
* For a category 2 register pair, verify that "typeh" is the appropriate
* high part for "typel".
*
* Does not verify that "typel" is in fact the low part of a 64-bit
* register pair.
*/
static void checkWidePair(RegType typel, RegType typeh, VerifyError* pFailure)
{
if ((typeh != typel+1))
*pFailure = VERIFY_ERROR_GENERIC;
}
/*
* Implement category-1 "move" instructions. Copy a 32-bit value from
* "vsrc" to "vdst".
*/
static void copyRegister1(RegisterLine* registerLine, u4 vdst, u4 vsrc,
TypeCategory cat, VerifyError* pFailure)
{
assert(cat == kTypeCategory1nr || cat == kTypeCategoryRef);
RegType type = getRegisterType(registerLine, vsrc);
checkTypeCategory(type, cat, pFailure);
if (!VERIFY_OK(*pFailure)) {
LOG_VFY("VFY: copy1 v%u<-v%u type=%d cat=%d", vdst, vsrc, type, cat);
} else {
setRegisterType(registerLine, vdst, type);
if (cat == kTypeCategoryRef && registerLine->monitorEntries != NULL) {
registerLine->monitorEntries[vdst] =
registerLine->monitorEntries[vsrc];
}
}
}
/*
* Implement category-2 "move" instructions. Copy a 64-bit value from
* "vsrc" to "vdst". This copies both halves of the register.
*/
static void copyRegister2(RegisterLine* registerLine, u4 vdst, u4 vsrc,
VerifyError* pFailure)
{
RegType typel = getRegisterType(registerLine, vsrc);
RegType typeh = getRegisterType(registerLine, vsrc+1);
checkTypeCategory(typel, kTypeCategory2, pFailure);
checkWidePair(typel, typeh, pFailure);
if (!VERIFY_OK(*pFailure)) {
LOG_VFY("VFY: copy2 v%u<-v%u type=%d/%d", vdst, vsrc, typel, typeh);
} else {
setRegisterType(registerLine, vdst, typel);
/* target monitor stack bits will be cleared */
}
}
/*
* Implement "move-result". Copy the category-1 value from the result
* register to another register, and reset the result register.
*/
static void copyResultRegister1(RegisterLine* registerLine,
const int insnRegCount, u4 vdst, TypeCategory cat, VerifyError* pFailure)
{
RegType type;
u4 vsrc;
assert(vdst < (u4) insnRegCount);
vsrc = RESULT_REGISTER(insnRegCount);
type = getRegisterType(registerLine, vsrc);
checkTypeCategory(type, cat, pFailure);
if (!VERIFY_OK(*pFailure)) {
LOG_VFY("VFY: copyRes1 v%u<-v%u cat=%d type=%d",
vdst, vsrc, cat, type);
} else {
setRegisterType(registerLine, vdst, type);
setRegisterType(registerLine, vsrc, kRegTypeUnknown);
/* target monitor stack bits will be cleared */
}
}
/*
* Implement "move-result-wide". Copy the category-2 value from the result
* register to another register, and reset the result register.
*/
static void copyResultRegister2(RegisterLine* registerLine,
const int insnRegCount, u4 vdst, VerifyError* pFailure)
{
RegType typel, typeh;
u4 vsrc;
assert(vdst < (u4) insnRegCount);
vsrc = RESULT_REGISTER(insnRegCount);
typel = getRegisterType(registerLine, vsrc);
typeh = getRegisterType(registerLine, vsrc+1);
checkTypeCategory(typel, kTypeCategory2, pFailure);
checkWidePair(typel, typeh, pFailure);
if (!VERIFY_OK(*pFailure)) {
LOG_VFY("VFY: copyRes2 v%u<-v%u type=%d/%d",
vdst, vsrc, typel, typeh);
} else {
setRegisterType(registerLine, vdst, typel);
setRegisterType(registerLine, vsrc, kRegTypeUnknown);
setRegisterType(registerLine, vsrc+1, kRegTypeUnknown);
/* target monitor stack bits will be cleared */
}
}
/*
* Verify types for a simple two-register instruction (e.g. "neg-int").
* "dstType" is stored into vA, and "srcType" is verified against vB.
*/
static void checkUnop(RegisterLine* registerLine, DecodedInstruction* pDecInsn,
RegType dstType, RegType srcType, VerifyError* pFailure)
{
verifyRegisterType(registerLine, pDecInsn->vB, srcType, pFailure);
setRegisterType(registerLine, pDecInsn->vA, dstType);
}
/*
* We're performing an operation like "and-int/2addr" that can be
* performed on booleans as well as integers. We get no indication of
* boolean-ness, but we can infer it from the types of the arguments.
*
* Assumes we've already validated reg1/reg2.
*
* TODO: consider generalizing this. The key principle is that the
* result of a bitwise operation can only be as wide as the widest of
* the operands. You can safely AND/OR/XOR two chars together and know
* you still have a char, so it's reasonable for the compiler or "dx"
* to skip the int-to-char instruction. (We need to do this for boolean
* because there is no int-to-boolean operation.)
*
* Returns true if both args are Boolean, Zero, or One.
*/
static bool upcastBooleanOp(RegisterLine* registerLine, u4 reg1, u4 reg2)
{
RegType type1, type2;
type1 = getRegisterType(registerLine, reg1);
type2 = getRegisterType(registerLine, reg2);
if ((type1 == kRegTypeBoolean || type1 == kRegTypeZero ||
type1 == kRegTypeOne) &&
(type2 == kRegTypeBoolean || type2 == kRegTypeZero ||
type2 == kRegTypeOne))
{
return true;
}
return false;
}
/*
* Verify types for A two-register instruction with a literal constant
* (e.g. "add-int/lit8"). "dstType" is stored into vA, and "srcType" is
* verified against vB.
*
* If "checkBooleanOp" is set, we use the constant value in vC.
*/
static void checkLitop(RegisterLine* registerLine, DecodedInstruction* pDecInsn,
RegType dstType, RegType srcType, bool checkBooleanOp,
VerifyError* pFailure)
{
verifyRegisterType(registerLine, pDecInsn->vB, srcType, pFailure);
if (VERIFY_OK(*pFailure) && checkBooleanOp) {
assert(dstType == kRegTypeInteger);
/* check vB with the call, then check the constant manually */
if (upcastBooleanOp(registerLine, pDecInsn->vB, pDecInsn->vB)
&& (pDecInsn->vC == 0 || pDecInsn->vC == 1))
{
dstType = kRegTypeBoolean;
}
}
setRegisterType(registerLine, pDecInsn->vA, dstType);
}
/*
* Verify types for a simple three-register instruction (e.g. "add-int").
* "dstType" is stored into vA, and "srcType1"/"srcType2" are verified
* against vB/vC.
*/
static void checkBinop(RegisterLine* registerLine, DecodedInstruction* pDecInsn,
RegType dstType, RegType srcType1, RegType srcType2, bool checkBooleanOp,
VerifyError* pFailure)
{
verifyRegisterType(registerLine, pDecInsn->vB, srcType1, pFailure);
verifyRegisterType(registerLine, pDecInsn->vC, srcType2, pFailure);
if (VERIFY_OK(*pFailure) && checkBooleanOp) {
assert(dstType == kRegTypeInteger);
if (upcastBooleanOp(registerLine, pDecInsn->vB, pDecInsn->vC))
dstType = kRegTypeBoolean;
}
setRegisterType(registerLine, pDecInsn->vA, dstType);
}
/*
* Verify types for a binary "2addr" operation. "srcType1"/"srcType2"
* are verified against vA/vB, then "dstType" is stored into vA.
*/
static void checkBinop2addr(RegisterLine* registerLine,
DecodedInstruction* pDecInsn, RegType dstType, RegType srcType1,
RegType srcType2, bool checkBooleanOp, VerifyError* pFailure)
{
verifyRegisterType(registerLine, pDecInsn->vA, srcType1, pFailure);
verifyRegisterType(registerLine, pDecInsn->vB, srcType2, pFailure);
if (VERIFY_OK(*pFailure) && checkBooleanOp) {
assert(dstType == kRegTypeInteger);
if (upcastBooleanOp(registerLine, pDecInsn->vA, pDecInsn->vB))
dstType = kRegTypeBoolean;
}
setRegisterType(registerLine, pDecInsn->vA, dstType);
}
/*
* Treat right-shifting as a narrowing conversion when possible.
*
* For example, right-shifting an int 24 times results in a value that can
* be treated as a byte.
*
* Things get interesting when contemplating sign extension. Right-
* shifting an integer by 16 yields a value that can be represented in a
* "short" but not a "char", but an unsigned right shift by 16 yields a
* value that belongs in a char rather than a short. (Consider what would
* happen if the result of the shift were cast to a char or short and then
* cast back to an int. If sign extension, or the lack thereof, causes
* a change in the 32-bit representation, then the conversion was lossy.)
*
* A signed right shift by 17 on an integer results in a short. An unsigned
* right shfit by 17 on an integer results in a posshort, which can be
* assigned to a short or a char.
*
* An unsigned right shift on a short can actually expand the result into
* a 32-bit integer. For example, 0xfffff123 >>> 8 becomes 0x00fffff1,
* which can't be represented in anything smaller than an int.
*
* javac does not generate code that takes advantage of this, but some
* of the code optimizers do. It's generally a peephole optimization
* that replaces a particular sequence, e.g. (bipush 24, ishr, i2b) is
* replaced by (bipush 24, ishr). Knowing that shifting a short 8 times
* to the right yields a byte is really more than we need to handle the
* code that's out there, but support is not much more complex than just
* handling integer.
*
* Right-shifting never yields a boolean value.
*
* Returns the new register type.
*/
static RegType adjustForRightShift(RegisterLine* registerLine, int reg,
unsigned int shiftCount, bool isUnsignedShift, VerifyError* pFailure)
{
RegType srcType = getRegisterType(registerLine, reg);
RegType newType;
/* convert const derived types to their actual types */
srcType = constTypeToRegType(srcType);
/* no-op */
if (shiftCount == 0)
return srcType;
/* safe defaults */
if (isUnsignedShift)
newType = kRegTypeInteger;
else
newType = srcType;
if (shiftCount >= 32) {
LOG_VFY("Got unexpectedly large shift count %u", shiftCount);
/* fail? */
return newType;
}
switch (srcType) {
case kRegTypeInteger: /* 32-bit signed value */
if (isUnsignedShift) {
if (shiftCount > 24)
newType = kRegTypePosByte;
else if (shiftCount >= 16)
newType = kRegTypeChar;
} else {
if (shiftCount >= 24)
newType = kRegTypeByte;
else if (shiftCount >= 16)
newType = kRegTypeShort;
}
break;
case kRegTypeShort: /* 16-bit signed value */
if (isUnsignedShift) {
/* default (kRegTypeInteger) is correct */
} else {
if (shiftCount >= 8)
newType = kRegTypeByte;
}
break;
case kRegTypePosShort: /* 15-bit unsigned value */
if (shiftCount >= 8)
newType = kRegTypePosByte;
break;
case kRegTypeChar: /* 16-bit unsigned value */
if (shiftCount > 8)
newType = kRegTypePosByte;
break;
case kRegTypeByte: /* 8-bit signed value */
/* defaults (u=kRegTypeInteger / s=srcType) are correct */
break;
case kRegTypePosByte: /* 7-bit unsigned value */
/* always use newType=srcType */
newType = srcType;
break;
case kRegTypeZero: /* 1-bit unsigned value */
case kRegTypeOne:
case kRegTypeBoolean:
/* unnecessary? */
newType = kRegTypeZero;
break;
default:
/* long, double, references; shouldn't be here! */
assert(false);
break;
}
if (newType != srcType) {
LOGVV("narrowing: %d(%d) --> %d to %d",
shiftCount, isUnsignedShift, srcType, newType);
} else {
LOGVV("not narrowed: %d(%d) --> %d",
shiftCount, isUnsignedShift, srcType);
}
return newType;
}
/*
* ===========================================================================
* Register merge
* ===========================================================================
*/
/*
* Compute the "class depth" of a class. This is the distance from the
* class to the top of the tree, chasing superclass links. java.lang.Object
* has a class depth of 0.
*/
static int getClassDepth(ClassObject* clazz)
{
int depth = 0;
while (clazz->super != NULL) {
clazz = clazz->super;
depth++;
}
return depth;
}
/*
* Given two classes, walk up the superclass tree to find a common
* ancestor. (Called from findCommonSuperclass().)
*
* TODO: consider caching the class depth in the class object so we don't
* have to search for it here.
*/
static ClassObject* digForSuperclass(ClassObject* c1, ClassObject* c2)
{
int depth1, depth2;
depth1 = getClassDepth(c1);
depth2 = getClassDepth(c2);
if (gDebugVerbose) {
LOGVV("COMMON: %s(%d) + %s(%d)",
c1->descriptor, depth1, c2->descriptor, depth2);
}
/* pull the deepest one up */
if (depth1 > depth2) {
while (depth1 > depth2) {
c1 = c1->super;
depth1--;
}
} else {
while (depth2 > depth1) {
c2 = c2->super;
depth2--;
}
}
/* walk up in lock-step */
while (c1 != c2) {
c1 = c1->super;
c2 = c2->super;
assert(c1 != NULL && c2 != NULL);
}
if (gDebugVerbose) {
LOGVV(" : --> %s", c1->descriptor);
}
return c1;
}
/*
* Merge two array classes. We can't use the general "walk up to the
* superclass" merge because the superclass of an array is always Object.
* We want String[] + Integer[] = Object[]. This works for higher dimensions
* as well, e.g. String[][] + Integer[][] = Object[][].
*
* If Foo1 and Foo2 are subclasses of Foo, Foo1[] + Foo2[] = Foo[].
*
* If Class implements Type, Class[] + Type[] = Type[].
*
* If the dimensions don't match, we want to convert to an array of Object
* with the least dimension, e.g. String[][] + String[][][][] = Object[][].
*
* Arrays of primitive types effectively have one less dimension when
* merging. int[] + float[] = Object, int[] + String[] = Object,
* int[][] + float[][] = Object[], int[][] + String[] = Object[]. (The
* only time this function doesn't return an array class is when one of
* the arguments is a 1-dimensional primitive array.)
*
* This gets a little awkward because we may have to ask the VM to create
* a new array type with the appropriate element and dimensions. However, we
* shouldn't be doing this often.
*/
static ClassObject* findCommonArraySuperclass(ClassObject* c1, ClassObject* c2)
{
ClassObject* arrayClass = NULL;
ClassObject* commonElem;
int arrayDim1, arrayDim2;
int i, numDims;
bool hasPrimitive = false;
arrayDim1 = c1->arrayDim;
arrayDim2 = c2->arrayDim;
assert(c1->arrayDim > 0);
assert(c2->arrayDim > 0);
if (dvmIsPrimitiveClass(c1->elementClass)) {
arrayDim1--;
hasPrimitive = true;
}
if (dvmIsPrimitiveClass(c2->elementClass)) {
arrayDim2--;
hasPrimitive = true;
}
if (!hasPrimitive && arrayDim1 == arrayDim2) {
/*
* Two arrays of reference types with equal dimensions. Try to
* find a good match.
*/
commonElem = findCommonSuperclass(c1->elementClass, c2->elementClass);
numDims = arrayDim1;
} else {
/*
* Mismatched array depths and/or array(s) of primitives. We want
* Object, or an Object array with appropriate dimensions.
*
* We initialize arrayClass to Object here, because it's possible
* for us to set numDims=0.
*/
if (arrayDim1 < arrayDim2)
numDims = arrayDim1;
else
numDims = arrayDim2;
arrayClass = commonElem = c1->super; // == java.lang.Object
}
/*
* Find an appropriately-dimensioned array class. This is easiest
* to do iteratively, using the array class found by the current round
* as the element type for the next round.
*/
for (i = 0; i < numDims; i++) {
arrayClass = dvmFindArrayClassForElement(commonElem);
commonElem = arrayClass;
}
assert(arrayClass != NULL);
LOGVV("ArrayMerge '%s' + '%s' --> '%s'",
c1->descriptor, c2->descriptor, arrayClass->descriptor);
return arrayClass;
}
/*
* Find the first common superclass of the two classes. We're not
* interested in common interfaces.
*
* The easiest way to do this for concrete classes is to compute the "class
* depth" of each, move up toward the root of the deepest one until they're
* at the same depth, then walk both up to the root until they match.
*
* If both classes are arrays, we need to merge based on array depth and
* element type.
*
* If one class is an interface, we check to see if the other class/interface
* (or one of its predecessors) implements the interface. If so, we return
* the interface; otherwise, we return Object.
*
* NOTE: we continue the tradition of "lazy interface handling". To wit,
* suppose we have three classes:
* One implements Fancy, Free
* Two implements Fancy, Free
* Three implements Free
* where Fancy and Free are unrelated interfaces. The code requires us
* to merge One into Two. Ideally we'd use a common interface, which
* gives us a choice between Fancy and Free, and no guidance on which to
* use. If we use Free, we'll be okay when Three gets merged in, but if
* we choose Fancy, we're hosed. The "ideal" solution is to create a
* set of common interfaces and carry that around, merging further references
* into it. This is a pain. The easy solution is to simply boil them
* down to Objects and let the runtime invokeinterface call fail, which
* is what we do.
*/
static ClassObject* findCommonSuperclass(ClassObject* c1, ClassObject* c2)
{
assert(!dvmIsPrimitiveClass(c1) && !dvmIsPrimitiveClass(c2));
if (c1 == c2)
return c1;
if (dvmIsInterfaceClass(c1) && dvmImplements(c2, c1)) {
if (gDebugVerbose)
LOGVV("COMMON/I1: %s + %s --> %s",
c1->descriptor, c2->descriptor, c1->descriptor);
return c1;
}
if (dvmIsInterfaceClass(c2) && dvmImplements(c1, c2)) {
if (gDebugVerbose)
LOGVV("COMMON/I2: %s + %s --> %s",
c1->descriptor, c2->descriptor, c2->descriptor);
return c2;
}
if (dvmIsArrayClass(c1) && dvmIsArrayClass(c2)) {
return findCommonArraySuperclass(c1, c2);
}
return digForSuperclass(c1, c2);
}
/*
* Merge two RegType values.
*
* Sets "*pChanged" to "true" if the result doesn't match "type1".
*/
static RegType mergeTypes(RegType type1, RegType type2, bool* pChanged)
{
RegType 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.
*
* Uninitialized references are composed of the enum ORed with an
* index value. 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 */
if (regTypeIsUninitReference(type1) ||
regTypeIsUninitReference(type2))
{
/* can't merge uninit with anything but self */
result = kRegTypeConflict;
} else {
ClassObject* clazz1 = regTypeInitializedReferenceToClass(type1);
ClassObject* clazz2 = regTypeInitializedReferenceToClass(type2);
ClassObject* mergedClass;
mergedClass = findCommonSuperclass(clazz1, clazz2);
assert(mergedClass != NULL);
result = regTypeFromClass(mergedClass);
}
}
}
if (result != type1)
*pChanged = true;
return result;
}
/*
* Merge the bits that indicate which monitor entry addresses on the stack
* are associated with this register.
*
* The merge is a simple bitwise AND.
*
* Sets "*pChanged" to "true" if the result doesn't match "ents1".
*/
static MonitorEntries mergeMonitorEntries(MonitorEntries ents1,
MonitorEntries ents2, bool* pChanged)
{
MonitorEntries result = ents1 & ents2;
if (result != ents1)
*pChanged = true;
return result;
}
/*
* Control can transfer to "nextInsn".
*
* Merge the registers from "workLine" into "regTable" at "nextInsn", and
* set the "changed" flag on the target address if any of the registers
* has changed.
*
* Returns "false" if we detect mis-matched monitor stacks.
*/
static bool updateRegisters(const Method* meth, InsnFlags* insnFlags,
RegisterTable* regTable, int nextInsn, const RegisterLine* workLine)
{
const size_t insnRegCountPlus = regTable->insnRegCountPlus;
assert(workLine != NULL);
const RegType* workRegs = workLine->regTypes;
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", nextInsn);
copyLineToTable(regTable, nextInsn, workLine);
dvmInsnSetChanged(insnFlags, nextInsn, true);
#ifdef VERIFIER_STATS
gDvm.verifierStats.copyRegCount++;
#endif
} else {
if (gDebugVerbose) {
LOGVV("MERGE into 0x%04x", nextInsn);
//dumpRegTypes(vdata, targetRegs, 0, "targ", NULL, 0);
//dumpRegTypes(vdata, workRegs, 0, "work", NULL, 0);
}
/* merge registers, set Changed only if different */
RegisterLine* targetLine = getRegisterLine(regTable, nextInsn);
RegType* targetRegs = targetLine->regTypes;
MonitorEntries* workMonEnts = workLine->monitorEntries;
MonitorEntries* targetMonEnts = targetLine->monitorEntries;
bool changed = false;
unsigned int idx;
assert(targetRegs != NULL);
if (targetMonEnts != NULL) {
/*
* Monitor stacks must be identical.
*/
if (targetLine->monitorStackTop != workLine->monitorStackTop) {
LOG_VFY_METH(meth,
"VFY: mismatched stack depth %d vs. %d at 0x%04x",
targetLine->monitorStackTop, workLine->monitorStackTop,
nextInsn);
return false;
}
if (memcmp(targetLine->monitorStack, workLine->monitorStack,
targetLine->monitorStackTop * sizeof(u4)) != 0)
{
LOG_VFY_METH(meth, "VFY: mismatched monitor stacks at 0x%04x",
nextInsn);
return false;
}
}
for (idx = 0; idx < insnRegCountPlus; idx++) {
targetRegs[idx] =
mergeTypes(targetRegs[idx], workRegs[idx], &changed);
if (targetMonEnts != NULL) {
targetMonEnts[idx] = mergeMonitorEntries(targetMonEnts[idx],
workMonEnts[idx], &changed);
}
}
if (gDebugVerbose) {
//ALOGI(" RESULT (changed=%d)", changed);
//dumpRegTypes(vdata, targetRegs, 0, "rslt", NULL, 0);
}
#ifdef VERIFIER_STATS
gDvm.verifierStats.mergeRegCount++;
if (changed)
gDvm.verifierStats.mergeRegChanged++;
#endif
if (changed)
dvmInsnSetChanged(insnFlags, nextInsn, true);
}
return true;
}
/*
* ===========================================================================
* Utility functions
* ===========================================================================
*/
/*
* 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
* "objType".
*
* It is possible for "objType" to be kRegTypeZero, meaning that we might
* have a null reference. This is a runtime problem, so we allow it,
* skipping some of the type checks.
*
* In general, "objType" must be an initialized reference. However, we
* allow it to be uninitialized if this is an "<init>" method and the field
* is declared within the "objType" class.
*
* Returns an InstField on success, returns NULL and sets "*pFailure"
* on failure.
*/
static InstField* getInstField(const Method* meth,
const UninitInstanceMap* uninitMap, RegType objType, int fieldIdx,
VerifyError* pFailure)
{
InstField* instField = NULL;
ClassObject* objClass;
bool mustBeLocal = false;
if (!regTypeIsReference(objType)) {
LOG_VFY("VFY: attempt to access field in non-reference type %d",
objType);
*pFailure = VERIFY_ERROR_GENERIC;
goto bail;
}
instField = dvmOptResolveInstField(meth->clazz, fieldIdx, pFailure);
if (instField == NULL) {
LOG_VFY("VFY: unable to resolve instance field %u", fieldIdx);
assert(!VERIFY_OK(*pFailure));
goto bail;
}
if (objType == kRegTypeZero)
goto bail;
/*
* Access to fields in uninitialized objects is allowed if this is
* the <init> method for the object and the field in question is
* declared by this class.
*/
objClass = regTypeReferenceToClass(objType, uninitMap);
assert(objClass != NULL);
if (regTypeIsUninitReference(objType)) {
if (!isInitMethod(meth) || meth->clazz != objClass) {
LOG_VFY("VFY: attempt to access field via uninitialized ref");
*pFailure = VERIFY_ERROR_GENERIC;
goto bail;
}
mustBeLocal = true;
}
if (!dvmInstanceof(objClass, instField->clazz)) {
LOG_VFY("VFY: invalid field access (field %s.%s, through %s ref)",
instField->clazz->descriptor, instField->name,
objClass->descriptor);
*pFailure = VERIFY_ERROR_NO_FIELD;
goto bail;
}
if (mustBeLocal) {
/* for uninit ref, make sure it's defined by this class, not super */
if (instField < objClass->ifields ||
instField >= objClass->ifields + objClass->ifieldCount)
{
LOG_VFY("VFY: invalid constructor field access (field %s in %s)",
instField->name, objClass->descriptor);
*pFailure = VERIFY_ERROR_GENERIC;
goto bail;
}
}
bail:
return instField;
}
/*
* Look up a static field.
*