blob: 8b1f4503c789c677a51083b92cf7b41a5bba271b [file] [log] [blame]
// Copyright 2011 Google Inc. All Rights Reserved.
#ifndef ART_SRC_DEX_VERIFY_H_
#define ART_SRC_DEX_VERIFY_H_
#include "dex_file.h"
#include "dex_instruction.h"
#include "macros.h"
#include "object.h"
#include "UniquePtr.h"
namespace art {
#define kMaxMonitorStackDepth (sizeof(MonitorEntries) * 8)
/*
* 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). 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
/*
* 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)
class DexVerifier {
public:
/*
* RegType holds information about the type of data held in a register.
* For most types it's a simple enum. For reference types it holds a
* pointer to the ClassObject, and for uninitialized references it holds
* an index into the UninitInstanceMap.
*/
typedef uint32_t RegType;
/*
* A bit vector indicating which entries in the monitor stack are
* associated with this register. The low bit corresponds to the stack's
* bottom-most entry.
*/
typedef uint32_t MonitorEntries;
/*
* 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-31 single bit flags:
* InTry: in "try" block; exceptions thrown here may be caught locally
* BranchTarget: other instructions can branch to this instruction
* GcPoint: this instruction is a GC safe point
* Visited: verifier has examined this instruction at least once
* Changed: set/cleared as bytecode verifier runs
*/
typedef uint32_t InsnFlags;
enum InsnFlag {
kInsnFlagWidthMask = 0x0000ffff,
kInsnFlagInTry = (1 << 16),
kInsnFlagBranchTarget = (1 << 17),
kInsnFlagGcPoint = (1 << 18),
kInsnFlagVisited = (1 << 30),
kInsnFlagChanged = (1 << 31),
};
/*
* "Direct" and "virtual" methods are stored independently. The type of call
* used to invoke the method determines which list we search, and whether
* we travel up into superclasses.
*
* (<clinit>, <init>, and methods declared "private" or "static" are stored
* in the "direct" list. All others are stored in the "virtual" list.)
*/
enum MethodType {
METHOD_UNKNOWN = 0,
METHOD_DIRECT, // <init>, private
METHOD_STATIC, // static
METHOD_VIRTUAL, // virtual, super
METHOD_INTERFACE // interface
};
/*
* 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,
};
/*
* 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.
*/
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 kRegTypeZero
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 */
kRegTypeConstPosByte, /* const derived byte, known positive */
kRegTypeConstByte, /* const derived byte */
kRegTypeConstPosShort, /* const derived short, known positive */
kRegTypeConstShort, /* const derived short */
kRegTypeConstChar, /* const derived char */
kRegTypeConstInteger, /* const derived integer */
kRegTypePosByte, /* byte, known positive (can become char) */
kRegTypeByte,
kRegTypePosShort, /* short, known positive (can become char) */
kRegTypeShort,
kRegTypeChar,
kRegTypeInteger,
kRegTypeFloat,
#define kRegType1nrEND kRegTypeFloat
kRegTypeConstLo, /* const derived wide, lower half */
kRegTypeConstHi, /* const derived wide, upper half */
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
/*
* 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 = 1, // boolean, byte, char, short, int, float
kTypeCategory2 = 2, // long, double
kTypeCategoryRef = 3, // object reference
};
/* An enumeration of problems that can turn up during verification. */
enum VerifyError {
VERIFY_ERROR_NONE = 0, /* no error; must be zero */
VERIFY_ERROR_GENERIC, /* VerifyError */
VERIFY_ERROR_NO_CLASS, /* NoClassDefFoundError */
VERIFY_ERROR_NO_FIELD, /* NoSuchFieldError */
VERIFY_ERROR_NO_METHOD, /* NoSuchMethodError */
VERIFY_ERROR_ACCESS_CLASS, /* IllegalAccessError */
VERIFY_ERROR_ACCESS_FIELD, /* IllegalAccessError */
VERIFY_ERROR_ACCESS_METHOD, /* IllegalAccessError */
VERIFY_ERROR_CLASS_CHANGE, /* IncompatibleClassChangeError */
VERIFY_ERROR_INSTANTIATION, /* InstantiationError */
};
/*
* Identifies the type of reference in the instruction that generated the
* verify error (e.g. VERIFY_ERROR_ACCESS_CLASS could come from a method,
* field, or class reference).
*
* This must fit in two bits.
*/
enum VerifyErrorRefType {
VERIFY_ERROR_REF_CLASS = 0,
VERIFY_ERROR_REF_FIELD = 1,
VERIFY_ERROR_REF_METHOD = 2,
};
#define kVerifyErrorRefTypeShift 6
/*
* Format enumeration for RegisterMap data area.
*/
enum RegisterMapFormat {
kRegMapFormatUnknown = 0,
kRegMapFormatNone, /* indicates no map data follows */
kRegMapFormatCompact8, /* compact layout, 8-bit addresses */
kRegMapFormatCompact16, /* compact layout, 16-bit addresses */
kRegMapFormatDifferential, /* compressed, differential encoding */
};
/*
* During verification, we associate one of these with every "interesting"
* instruction. We track the status of all registers, and (if the method
* has any monitor-enter instructions) maintain a stack of entered monitors
* (identified by code unit offset).
*
* If live-precise register maps are enabled, the "liveRegs" vector will
* be populated. Unlike the other lists of registers here, we do not
* track the liveness of the method result register (which is not visible
* to the GC).
*/
struct RegisterLine {
UniquePtr<RegType[]> reg_types_;
UniquePtr<MonitorEntries[]> monitor_entries_;
UniquePtr<uint32_t[]> monitor_stack_;
uint32_t monitor_stack_top_;
RegisterLine()
: reg_types_(NULL), monitor_entries_(NULL), monitor_stack_(NULL),
monitor_stack_top_(0) {
}
/* Allocate space for the fields. */
void Alloc(size_t size, bool track_monitors) {
reg_types_.reset(new RegType[size]());
if (track_monitors) {
monitor_entries_.reset(new MonitorEntries[size]);
monitor_stack_.reset(new uint32_t[kMaxMonitorStackDepth]);
}
}
};
/* Big fat collection of register data. */
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.
*/
UniquePtr<RegisterLine[]> register_lines_;
/*
* Number of registers we track for each instruction. This is equal
* to the method's declared "registersSize" plus kExtraRegs (2).
*/
size_t insn_reg_count_plus_;
/* Storage for a register line we're currently working on. */
RegisterLine work_line_;
/* Storage for a register line we're saving for later. */
RegisterLine saved_line_;
RegisterTable() : register_lines_(NULL), insn_reg_count_plus_(0) {
}
};
/* Entries in the UninitInstanceMap. */
struct UninitInstanceMapEntry {
/* Code offset, or -1 for method arg ("this"). */
int addr_;
/* Class created at this address. */
Class* klass_;
};
/*
* Table that maps uninitialized instances to classes, based on the
* address of the new-instance instruction. One per method.
*/
struct UninitInstanceMap {
int num_entries_;
UniquePtr<UninitInstanceMapEntry[]> map_;
UninitInstanceMap(int num_entries)
: num_entries_(num_entries),
map_(new UninitInstanceMapEntry[num_entries]()) {
}
};
#define kUninitThisArgAddr (-1)
#define kUninitThisArgSlot 0
/* Various bits of data used by the verifier and register map generator. */
struct VerifierData {
/* The method we're working on. */
Method* method_;
/* The dex file containing the method. */
const DexFile* dex_file_;
/* The code item containing the code for the method. */
const DexFile::CodeItem* code_item_;
/* Instruction widths and flags, one entry per code unit. */
UniquePtr<InsnFlags[]> insn_flags_;
/*
* Uninitialized instance map, used for tracking the movement of
* objects that have been allocated but not initialized.
*/
UniquePtr<UninitInstanceMap> uninit_map_;
/*
* Array of RegisterLine structs, one entry per code unit. We only need
* entries for code units that hold the start of an "interesting"
* instruction. For register map generation, we're only interested
* in GC points.
*/
RegisterLine* register_lines_;
/* The number of occurrences of specific opcodes. */
size_t new_instance_count_;
size_t monitor_enter_count_;
VerifierData(Method* method, const DexFile* dex_file,
const DexFile::CodeItem* code_item)
: method_(method), dex_file_(dex_file), code_item_(code_item),
insn_flags_(NULL), uninit_map_(NULL), register_lines_(NULL),
new_instance_count_(0), monitor_enter_count_(0) {
}
};
/* Header for RegisterMap */
struct RegisterMapHeader {
uint8_t format_; /* enum RegisterMapFormat; MUST be first entry */
uint8_t reg_width_; /* bytes per register line, 1+ */
uint16_t num_entries_; /* number of entries */
RegisterMapHeader(uint8_t format, uint8_t reg_width, uint16_t num_entries)
: format_(format), reg_width_(reg_width), num_entries_(num_entries) {
}
};
/*
* This is a single variable-size structure. It may be allocated on the
* heap or mapped out of a (post-dexopt) DEX file.
*
* 32-bit alignment of the structure is NOT guaranteed. This makes it a
* little awkward to deal with as a structure; to avoid accidents we use
* only byte types. Multi-byte values are little-endian.
*
* Size of (format==FormatNone): 1 byte
* Size of (format==FormatCompact8): 4 + (1 + reg_width) * num_entries
* Size of (format==FormatCompact16): 4 + (2 + reg_width) * num_entries
*/
struct RegisterMap {
RegisterMapHeader* header_;
uint8_t* data_;
bool needs_free_;
RegisterMap(ByteArray* header, ByteArray* data) {
header_ = (RegisterMapHeader*) header->GetData();
data_ = (uint8_t*) data->GetData();
needs_free_ = false;
}
RegisterMap(uint8_t format, uint8_t reg_width, uint16_t num_entries,
uint32_t data_size) {
header_ = new RegisterMapHeader(format, reg_width, num_entries);
data_ = new uint8_t[data_size]();
needs_free_ = true;
}
~RegisterMap() {
if (needs_free_) {
delete header_;
delete [] data_;
}
}
};
/*
* 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.
*/
static const char merge_table_[kRegTypeMAX][kRegTypeMAX];
/*
* Returns "true" if the flags indicate that this address holds the start
* of an instruction.
*/
static inline bool InsnIsOpcode(const InsnFlags insn_flags[], int addr) {
return (insn_flags[addr] & kInsnFlagWidthMask) != 0;
}
/* Extract the unsigned 16-bit instruction width from "flags". */
static inline int InsnGetWidth(const InsnFlags insn_flags[], int addr) {
return insn_flags[addr] & kInsnFlagWidthMask;
}
/* Utilities to check and set kInsnFlagChanged. */
static inline bool InsnIsChanged(const InsnFlags insn_flags[], int addr) {
return (insn_flags[addr] & kInsnFlagChanged) != 0;
}
static inline void InsnSetChanged(InsnFlags insn_flags[], int addr,
bool changed) {
if (changed)
insn_flags[addr] |= kInsnFlagChanged;
else
insn_flags[addr] &= ~kInsnFlagChanged;
}
/* Utilities to check and set kInsnFlagVisited. */
static inline bool InsnIsVisited(const InsnFlags insn_flags[], int addr) {
return (insn_flags[addr] & kInsnFlagVisited) != 0;
}
static inline void InsnSetVisited(InsnFlags insn_flags[], int addr,
bool visited) {
if (visited)
insn_flags[addr] |= kInsnFlagVisited;
else
insn_flags[addr] &= ~kInsnFlagVisited;
}
static inline bool InsnIsVisitedOrChanged(const InsnFlags insn_flags[],
int addr) {
return (insn_flags[addr] & (kInsnFlagVisited |
kInsnFlagChanged)) != 0;
}
/* Utilities to check and set kInsnFlagInTry. */
static inline bool InsnIsInTry(const InsnFlags insn_flags[], int addr) {
return (insn_flags[addr] & kInsnFlagInTry) != 0;
}
static inline void InsnSetInTry(InsnFlags insn_flags[], int addr) {
insn_flags[addr] |= kInsnFlagInTry;
}
/* Utilities to check and set kInsnFlagBranchTarget. */
static inline bool InsnIsBranchTarget(const InsnFlags insn_flags[], int addr)
{
return (insn_flags[addr] & kInsnFlagBranchTarget) != 0;
}
static inline void InsnSetBranchTarget(InsnFlags insn_flags[], int addr) {
insn_flags[addr] |= kInsnFlagBranchTarget;
}
/* Utilities to check and set kInsnFlagGcPoint. */
static inline bool InsnIsGcPoint(const InsnFlags insn_flags[], int addr) {
return (insn_flags[addr] & kInsnFlagGcPoint) != 0;
}
static inline void InsnSetGcPoint(InsnFlags insn_flags[], int addr) {
insn_flags[addr] |= kInsnFlagGcPoint;
}
/* Get the class object at the specified index. */
static inline Class* GetUninitInstance(const UninitInstanceMap* uninit_map, int idx) {
DCHECK_GE(idx, 0);
DCHECK_LT(idx, uninit_map->num_entries_);
return uninit_map->map_[idx].klass_;
}
/* 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 Class pointer
* (does not expect uninit ref types or "zero").
*/
static Class* RegTypeInitializedReferenceToClass(RegType type) {
DCHECK(RegTypeIsReference(type) && type != kRegTypeZero);
if ((type & 0x01) == 0) {
return (Class*) type;
} else {
LOG(ERROR) << "VFY: attempted to use uninitialized reference";
return NULL;
}
}
/* Extract the index into the uninitialized instance map table. */
static inline int RegTypeToUninitIndex(RegType type) {
DCHECK(RegTypeIsUninitReference(type));
return (type & ~kRegTypeUninitMask) >> kRegTypeUninitShift;
}
/* Convert the reference "type" to a Class pointer. */
static Class* RegTypeReferenceToClass(RegType type,
const UninitInstanceMap* uninit_map) {
DCHECK(RegTypeIsReference(type) && type != kRegTypeZero);
if (RegTypeIsUninitReference(type)) {
DCHECK(uninit_map != NULL);
return GetUninitInstance(uninit_map, RegTypeToUninitIndex(type));
} else {
return (Class*) type;
}
}
/* Convert the ClassObject pointer to an (initialized) register type. */
static inline RegType RegTypeFromClass(Class* klass) {
return (uint32_t) klass;
}
/* Return the RegType for the uninitialized reference in slot "uidx". */
static inline RegType RegTypeFromUninitIndex(int uidx) {
return (uint32_t) (kRegTypeUninit | (uidx << kRegTypeUninitShift));
}
/*
* Generate the register map for a method that has just been verified
* (i.e. we're doing this as part of verification).
*
* For type-precise determination we have all the data we need, so we
* just need to encode it in some clever fashion.
*
* Returns a pointer to a newly-allocated RegisterMap, or NULL on failure.
*/
static RegisterMap* GenerateRegisterMapV(VerifierData* vdata);
/*
* Get the expanded form of the register map associated with the specified
* method. May update the RegisterMap, possibly freeing the previous map.
*
* Returns NULL on failure (e.g. unable to expand map).
*
* NOTE: this function is not synchronized; external locking is mandatory.
* (This is expected to be called at GC time.)
*/
static inline RegisterMap* GetExpandedRegisterMap(Method* method) {
if (method->GetRegisterMapHeader() == NULL ||
method->GetRegisterMapData() == NULL) {
return NULL;
}
RegisterMap* cur_map = new RegisterMap(method->GetRegisterMapHeader(),
method->GetRegisterMapData());
uint8_t format = cur_map->header_->format_;
if (format == kRegMapFormatCompact8 || format == kRegMapFormatCompact16) {
return cur_map;
} else {
return GetExpandedRegisterMapHelper(method, cur_map);
}
}
/*
* Get the expanded form of the register map associated with the method.
*
* If the map is already in one of the uncompressed formats, we return
* immediately. Otherwise, we expand the map and replace method's register
* map pointer, freeing it if it was allocated on the heap.
*
* NOTE: this function is not synchronized; external locking is mandatory
* (unless we're in the zygote, where single-threaded access is guaranteed).
*/
static RegisterMap* GetExpandedRegisterMapHelper(Method* method,
RegisterMap* map);
/* Return the data for the specified address, or NULL if not found. */
static const uint8_t* RegisterMapGetLine(const RegisterMap* map, int addr);
/*
* Determine if the RegType value is a reference type.
*
* Ordinarily we include kRegTypeZero in the "is it a reference"
* check. There's no value in doing so here, because we know
* the register can't hold anything but zero.
*/
static inline bool IsReferenceType(RegType type) {
return (type > kRegTypeMAX || type == kRegTypeUninit);
}
/* Toggle the value of the "idx"th bit in "ptr". */
static inline void ToggleBit(uint8_t* ptr, int idx) {
ptr[idx >> 3] ^= 1 << (idx & 0x07);
}
/*
* Given a line of registers, output a bit vector that indicates whether
* or not the register holds a reference type (which could be null).
*
* We use '1' to indicate it's a reference, '0' for anything else (numeric
* value, uninitialized data, merge conflict). Register 0 will be found
* in the low bit of the first byte.
*/
static void OutputTypeVector(const RegType* regs, int insn_reg_count,
uint8_t* data);
/*
* Double-check the map.
*
* We run through all of the data in the map, and compare it to the original.
* Only works on uncompressed data.
*/
static bool VerifyMap(VerifierData* vdata, const RegisterMap* map);
/* Compare two register maps. Returns true if they're equal, false if not. */
static bool CompareMaps(const RegisterMap* map1, const RegisterMap* map2);
/* Compute the size, in bytes, of a register map. */
static size_t ComputeRegisterMapSize(const RegisterMap* map);
/*
* Compute the difference between two bit vectors.
*
* If "leb_out_buf" is non-NULL, we output the bit indices in ULEB128 format
* as we go. Otherwise, we just generate the various counts.
*
* The bit vectors are compared byte-by-byte, so any unused bits at the
* end must be zero.
*
* Returns the number of bytes required to hold the ULEB128 output.
*
* If "first_bit_changed_ptr" or "num_bits_changed_ptr" are non-NULL, they
* will receive the index of the first changed bit and the number of changed
* bits, respectively.
*/
static int ComputeBitDiff(const uint8_t* bits1, const uint8_t* bits2,
int byte_width, int* first_bit_changed_ptr, int* num_bits_changed_ptr,
uint8_t* leb_out_buf);
/*
* Compress the register map with differential encoding.
*
* On success, returns a newly-allocated RegisterMap. If the map is not
* compatible for some reason, or fails to get smaller, this will return NULL.
*/
static RegisterMap* CompressMapDifferential(const RegisterMap* map);
/*
* Expand a compressed map to an uncompressed form.
*
* Returns a newly-allocated RegisterMap on success, or NULL on failure.
*
* TODO: consider using the linear allocator or a custom allocator with
* LRU replacement for these instead of the native heap.
*/
static RegisterMap* UncompressMapDifferential(const RegisterMap* map);
/* Verify a class. Returns "true" on success. */
static bool VerifyClass(Class* klass);
private:
/*
* Perform verification on a single method.
*
* We do this in three passes:
* (1) Walk through all code units, determining instruction locations,
* widths, and other characteristics.
* (2) Walk through all code units, performing static checks on
* operands.
* (3) Iterate through the method, checking type safety and looking
* for code flow problems.
*
* Some checks may be bypassed depending on the verification mode. We can't
* turn this stuff off completely if we want to do "exact" GC.
*
* Confirmed here:
* - code array must not be empty
* Confirmed by ComputeWidthsAndCountOps():
* - opcode of first instruction begins at index 0
* - only documented instructions may appear
* - each instruction follows the last
* - last byte of last instruction is at (code_length-1)
*/
static bool VerifyMethod(Method* method);
/*
* Perform static verification on all instructions in a method.
*
* Walks through instructions in a method calling VerifyInstruction on each.
*/
static bool VerifyInstructions(VerifierData* vdata);
/*
* Perform static verification on an instruction.
*
* As a side effect, this sets the "branch target" flags in InsnFlags.
*
* "(CF)" items are handled during code-flow analysis.
*
* v3 4.10.1
* - target of each jump and branch instruction must be valid
* - targets of switch statements must be valid
* - operands referencing constant pool entries must be valid
* - (CF) operands of getfield, putfield, getstatic, putstatic must be valid
* - (CF) operands of method invocation instructions must be valid
* - (CF) only invoke-direct can call a method starting with '<'
* - (CF) <clinit> must never be called explicitly
* - operands of instanceof, checkcast, new (and variants) must be valid
* - new-array[-type] limited to 255 dimensions
* - can't use "new" on an array class
* - (?) limit dimensions in multi-array creation
* - local variable load/store register values must be in valid range
*
* v3 4.11.1.2
* - branches must be within the bounds of the code array
* - targets of all control-flow instructions are the start of an instruction
* - register accesses fall within range of allocated registers
* - (N/A) access to constant pool must be of appropriate type
* - code does not end in the middle of an instruction
* - execution cannot fall off the end of the code
* - (earlier) for each exception handler, the "try" area must begin and
* end at the start of an instruction (end can be at the end of the code)
* - (earlier) for each exception handler, the handler must start at a valid
* instruction
*/
static bool VerifyInstruction(VerifierData* vdata,
const Instruction* inst, uint32_t code_offset);
/* Perform detailed code-flow analysis on a single method. */
static bool VerifyCodeFlow(VerifierData* vdata);
/*
* Compute the width of the instruction at each address in the instruction
* stream, and store it in vdata->insn_flags. Addresses that are in the
* middle of an instruction, or that are part of switch table data, are not
* touched (so the caller should probably initialize "insn_flags" to zero).
*
* The "new_instance_count_" and "monitor_enter_count_" fields in vdata are
* also set.
*
* Performs some static checks, notably:
* - opcode of first instruction begins at index 0
* - only documented instructions may appear
* - each instruction follows the last
* - last byte of last instruction is at (code_length-1)
*
* Logs an error and returns "false" on failure.
*/
static bool ComputeWidthsAndCountOps(VerifierData* vdata);
/*
* 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 "insn_flags".
*
* Returns "false" if something in the exception table looks fishy, but
* we're expecting the exception table to be somewhat sane.
*/
static bool ScanTryCatchBlocks(VerifierData* vdata);
/*
* Extract the relative offset from a branch instruction.
*
* Returns "false" on failure (e.g. this isn't a branch instruction).
*/
static bool GetBranchOffset(const DexFile::CodeItem* code_item,
const InsnFlags insn_flags[], uint32_t cur_offset, int32_t* pOffset,
bool* pConditional, bool* selfOkay);
/*
* Verify an array data table. "cur_offset" is the offset of the
* fill-array-data instruction.
*/
static bool CheckArrayData(const DexFile::CodeItem* code_item,
uint32_t cur_offset);
/*
* Perform static checks on a "new-instance" instruction. Specifically,
* make sure the class reference isn't for an array class.
*
* We don't need the actual class, just a pointer to the class name.
*/
static bool CheckNewInstance(const DexFile* dex_file, uint32_t idx);
/*
* Perform static checks on a "new-array" instruction. Specifically, make
* sure they aren't creating an array of arrays that causes the number of
* dimensions to exceed 255.
*/
static bool CheckNewArray(const DexFile* dex_file, uint32_t idx);
/*
* Perform static checks on an instruction that takes a class constant.
* Ensure that the class index is in the valid range.
*/
static bool CheckTypeIndex(const DexFile* dex_file, uint32_t idx);
/*
* Perform static checks on a field get or set instruction. All we do
* here is ensure that the field index is in the valid range.
*/
static bool CheckFieldIndex(const DexFile* dex_file, uint32_t idx);
/*
* Perform static checks on a method invocation instruction. All we do
* here is ensure that the method index is in the valid range.
*/
static bool CheckMethodIndex(const DexFile* dex_file, uint32_t idx);
/* Ensure that the string index is in the valid range. */
static bool CheckStringIndex(const DexFile* dex_file, uint32_t idx);
/* Ensure that the register index is valid for this code item. */
static bool CheckRegisterIndex(const DexFile::CodeItem* code_item,
uint32_t idx);
/* Ensure that the wide register index is valid for this code item. */
static bool CheckWideRegisterIndex(const DexFile::CodeItem* code_item,
uint32_t idx);
/*
* Check the register indices used in a "vararg" instruction, such as
* invoke-virtual or filled-new-array.
*
* vA holds word count (0-5), args[] have values.
*
* There are some tests we don't do here, e.g. we don't try to verify
* that invoking a method that takes a double is done with consecutive
* registers. This requires parsing the target method signature, which
* we will be doing later on during the code flow analysis.
*/
static bool CheckVarArgRegs(const DexFile::CodeItem* code_item, uint32_t vA,
uint32_t arg[]);
/*
* Check the register indices used in a "vararg/range" instruction, such as
* invoke-virtual/range or filled-new-array/range.
*
* vA holds word count, vC holds index of first reg.
*/
static bool CheckVarArgRangeRegs(const DexFile::CodeItem* code_item,
uint32_t vA, uint32_t vC);
/*
* Verify a switch table. "cur_offset" is the offset of the switch
* instruction.
*
* Updates "insnFlags", setting the "branch target" flag.
*/
static bool CheckSwitchTargets(const DexFile::CodeItem* code_item,
InsnFlags insn_flags[], uint32_t cur_offset);
/*
* 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 dex format forbids certain instructions from branching to itself.
*
* Updates "insnFlags", setting the "branch target" flag.
*/
static bool CheckBranchTarget(const DexFile::CodeItem* code_item,
InsnFlags insn_flags[], uint32_t cur_offset);
/*
* Initialize the RegisterTable.
*
* Every instruction address can have a different set of information about
* what's in which register, but for verification purposes we only need to
* store it at branch target addresses (because we merge into that).
*
* By zeroing out the regType storage we are effectively initializing the
* register information to kRegTypeUnknown.
*
* We jump through some hoops here to minimize the total number of
* allocations we have to perform per method verified.
*/
static bool InitRegisterTable(VerifierData* vdata, RegisterTable* reg_table,
RegisterTrackingMode track_regs_for);
/* Get the register line for the given instruction in the current method. */
static inline RegisterLine* GetRegisterLine(const RegisterTable* reg_table,
int insn_idx) {
return &reg_table->register_lines_[insn_idx];
}
/* Copy a register line. */
static inline void CopyRegisterLine(RegisterLine* dst,
const RegisterLine* src, size_t num_regs) {
memcpy(dst->reg_types_.get(), src->reg_types_.get(), num_regs * sizeof(RegType));
DCHECK((src->monitor_entries_.get() == NULL && dst->monitor_entries_.get() == NULL) ||
(src->monitor_entries_.get() != NULL && dst->monitor_entries_.get() != NULL));
if (dst->monitor_entries_.get() != NULL) {
DCHECK(dst->monitor_stack_.get() != NULL);
memcpy(dst->monitor_entries_.get(), src->monitor_entries_.get(),
num_regs * sizeof(MonitorEntries));
memcpy(dst->monitor_stack_.get(), src->monitor_stack_.get(),
kMaxMonitorStackDepth * sizeof(uint32_t));
dst->monitor_stack_top_ = src->monitor_stack_top_;
}
}
/* Copy a register line into the table. */
static inline void CopyLineToTable(RegisterTable* reg_table, int insn_idx,
const RegisterLine* src) {
RegisterLine* dst = GetRegisterLine(reg_table, insn_idx);
DCHECK(dst->reg_types_.get() != NULL);
CopyRegisterLine(dst, src, reg_table->insn_reg_count_plus_);
}
/* Copy a register line out of the table. */
static inline void CopyLineFromTable(RegisterLine* dst,
const RegisterTable* reg_table, int insn_idx) {
RegisterLine* src = GetRegisterLine(reg_table, insn_idx);
DCHECK(src->reg_types_.get() != NULL);
CopyRegisterLine(dst, src, reg_table->insn_reg_count_plus_);
}
#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* reg_table,
int insn_idx, const RegisterLine* line2) {
const RegisterLine* line1 = GetRegisterLine(reg_table, insn_idx);
if (line1->monitor_entries_.get() != NULL) {
int result;
if (line2->monitor_entries_.get() == NULL)
return 1;
result = memcmp(line1->monitor_entries_.get(), line2->monitor_entries_.get(),
reg_table->insn_reg_count_plus_ * sizeof(MonitorEntries));
if (result != 0) {
LOG(ERROR) << "monitor_entries_ mismatch";
return result;
}
result = line1->monitor_stack_top_ - line2->monitor_stack_top_;
if (result != 0) {
LOG(ERROR) << "monitor_stack_top_ mismatch";
return result;
}
result = memcmp(line1->monitor_stack_.get(), line2->monitor_stack_.get(),
line1->monitor_stack_top_);
if (result != 0) {
LOG(ERROR) << "monitor_stack_ mismatch";
return result;
}
}
return memcmp(line1->reg_types_.get(), line2->reg_types_.get(),
reg_table->insn_reg_count_plus_ * sizeof(RegType));
}
#endif
/*
* 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
*/
static UninitInstanceMap* CreateUninitInstanceMap(VerifierData* vdata);
/* Returns true if this method is a constructor. */
static bool IsInitMethod(const Method* method);
/*
* Look up a class reference given as a simple string descriptor.
*
* If we can't find it, return a generic substitute when possible.
*/
static Class* LookupClassByDescriptor(const Method* method,
const char* descriptor, VerifyError* failure);
/*
* Look up a class reference in a signature. Could be an arg or the
* return value.
*
* Advances "*sig" to the last character in the signature (that is, to
* the ';').
*
* NOTE: this is also expected to verify the signature.
*/
static Class* LookupSignatureClass(const Method* method, std::string sig,
VerifyError* failure);
/*
* Look up an array class reference in a signature. Could be an arg or the
* return value.
*
* Advances "*sig" to the last character in the signature.
*
* NOTE: this is also expected to verify the signature.
*/
static Class* LookupSignatureArrayClass(const Method* method,
std::string sig, VerifyError* failure);
/*
* 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(VerifierData* vdata, RegType* reg_types);
/*
* 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* uninit_map, int addr,
Class* klass);
/*
* Perform code flow on a method.
*
* The basic strategy is as outlined in v3 4.11.1.2: set the "changed" bit
* on the first instruction, process it (setting additional "changed" bits),
* and repeat until there are no more.
*
* v3 4.11.1.1
* - (N/A) operand stack is always the same size
* - operand stack [registers] contain the correct types of values
* - local variables [registers] contain the correct types of values
* - methods are invoked with the appropriate arguments
* - fields are assigned using values of appropriate types
* - opcodes have the correct type values in operand registers
* - there is never an uninitialized class instance in a local variable in
* code protected by an exception handler (operand stack is okay, because
* the operand stack is discarded when an exception is thrown) [can't
* know what's a local var w/o the debug info -- should fall out of
* register typing]
*
* v3 4.11.1.2
* - execution cannot fall off the end of the code
*
* (We also do many of the items described in the "static checks" sections,
* because it's easier to do them here.)
*
* We need an array of RegType values, one per register, for every
* instruction. If the method uses monitor-enter, we need extra data
* for every register, and a stack for every "interesting" instruction.
* In theory this could become quite large -- up to several megabytes for
* a monster function.
*
* NOTE:
* The spec forbids backward branches when there's an uninitialized reference
* in a register. The idea is to prevent something like this:
* loop:
* move r1, r0
* new-instance r0, MyClass
* ...
* if-eq rN, loop // once
* initialize r0
*
* This leaves us with two different instances, both allocated by the
* same instruction, but only one is initialized. The scheme outlined in
* v3 4.11.1.4 wouldn't catch this, so they work around it by preventing
* backward branches. We achieve identical results without restricting
* code reordering by specifying that you can't execute the new-instance
* instruction if a register contains an uninitialized instance created
* by that same instrutcion.
*/
static bool CodeFlowVerifyMethod(VerifierData* vdata,
RegisterTable* reg_table);
/*
* Perform verification for a single instruction.
*
* This requires fully decoding the instruction to determine the effect
* it has on registers.
*
* Finds zero or more following instructions and sets the "changed" flag
* if execution at that point needs to be (re-)evaluated. Register changes
* are merged into "reg_types_" at the target addresses. Does not set or
* clear any other flags in "insn_flags".
*/
static bool CodeFlowVerifyInstruction(VerifierData* vdata,
RegisterTable* reg_table, uint32_t insn_idx, size_t* start_guess);
/*
* Replace an instruction with "throw-verification-error". This allows us to
* defer error reporting until the code path is first used.
*
* This is expected to be called during "just in time" verification, not
* from within dexopt. (Verification failures in dexopt will result in
* postponement of verification to first use of the class.)
*
* The throw-verification-error instruction requires two code units. Some
* of the replaced instructions require three; the third code unit will
* receive a "nop". The instruction's length will be left unchanged
* in "insn_flags".
*
* The VM postpones setting of debugger breakpoints in unverified classes,
* so there should be no clashes with the debugger.
*
* Returns "true" on success.
*/
static bool ReplaceFailingInstruction(const DexFile::CodeItem* code_item,
int insn_idx, VerifyError failure);
/* Update a 16-bit opcode in a dex file. */
static void UpdateCodeUnit(const uint16_t* ptr, uint16_t new_val);
/* Handle a monitor-enter instruction. */
static void HandleMonitorEnter(RegisterLine* work_line, uint32_t reg_idx,
uint32_t insn_idx, VerifyError* failure);
/* Handle a monitor-exit instruction. */
static void HandleMonitorExit(RegisterLine* work_line, uint32_t reg_idx,
uint32_t insn_idx, VerifyError* failure);
/*
* Look up an instance field, specified by "field_idx", that is going to be
* accessed in object "obj_type". This resolves the field and then verifies
* that the class containing the field is an instance of the reference in
* "obj_type".
*
* It is possible for "obj_type" 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, "obj_type" 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 "obj_type" class.
*
* Returns a Field on success, returns NULL and sets "*failure" on failure.
*/
static Field* GetInstField(VerifierData* vdata, RegType obj_type,
int field_idx, VerifyError* failure);
/*
* Look up a static field.
*
* Returns a StaticField on success, returns NULL and sets "*failure"
* on failure.
*/
static Field* GetStaticField(VerifierData* vdata, int field_idx,
VerifyError* failure);
/*
* For the "move-exception" instruction at "insn_idx", which must be at an
* exception handler address, determine the first common superclass of
* all exceptions that can land here. (For javac output, we're probably
* looking at multiple spans of bytecode covered by one "try" that lands
* at an exception-specific "catch", but in general the handler could be
* shared for multiple exceptions.)
*
* Returns NULL if no matching exception handler can be found, or if the
* exception is not a subclass of Throwable.
*/
static Class* GetCaughtExceptionType(VerifierData* vdata, int insn_idx,
VerifyError* failure);
/*
* 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* register_line,
uint32_t vsrc) {
return register_line->reg_types_[vsrc];
}
/*
* 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 DexFile* dex_file,
const Method* method);
/*
* Get the value from a register, and cast it to a Class. Sets
* "*failure" if something fails.
*
* This fails if the register holds an uninitialized class.
*
* If the register holds kRegTypeZero, this returns a NULL pointer.
*/
static Class* GetClassFromRegister(const RegisterLine* register_line,
uint32_t vsrc, VerifyError* failure);
/*
* 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* register_line,
const Instruction::DecodedInstruction* dec_insn, VerifyError* failure);
/*
* Set the type of register N, verifying that the register is valid. If
* "new_type" is the "Lo" part of a 64-bit value, register N+1 will be
* set to "new_type+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* register_line, uint32_t vdst,
RegType new_type);
/*
* 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 check_type, or if check_type is an
* interface, verify that the register implements check_type.
*/
static void VerifyRegisterType(RegisterLine* register_line, uint32_t vsrc,
RegType check_type, VerifyError* failure);
/* Set the type of the "result" register. */
static void SetResultRegisterType(RegisterLine* register_line,
const int insn_reg_count, RegType new_type);
/*
* Update all registers holding "uninit_type" 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* register_line,
int insn_reg_count, UninitInstanceMap* uninit_map, RegType uninit_type,
VerifyError* failure);
/*
* Implement category-1 "move" instructions. Copy a 32-bit value from
* "vsrc" to "vdst".
*/
static void CopyRegister1(RegisterLine* register_line, uint32_t vdst,
uint32_t vsrc, TypeCategory cat, VerifyError* failure);
/*
* 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* register_line, uint32_t vdst,
uint32_t vsrc, VerifyError* failure);
/*
* Implement "move-result". Copy the category-1 value from the result
* register to another register, and reset the result register.
*/
static void CopyResultRegister1(RegisterLine* register_line,
const int insn_reg_count, uint32_t vdst, TypeCategory cat,
VerifyError* failure);
/*
* 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* register_line,
const int insn_reg_count, uint32_t vdst, VerifyError* failure);
/*
* 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(Class* klass);
/*
* 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 Class* DigForSuperclass(Class* c1, Class* c2);
/*
* 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 Class* FindCommonArraySuperclass(Class* c1, Class* c2);
/*
* 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 Class* FindCommonSuperclass(Class* c1, Class* c2);
/*
* Resolves a class based on an index and performs access checks to ensure
* the referrer can access the resolved class.
*
* Exceptions caused by failures are cleared before returning.
*
* Sets "*failure" on failure.
*/
static Class* ResolveClassAndCheckAccess(const DexFile* dex_file,
uint32_t class_idx, const Class* referrer, VerifyError* failure);
/*
* Resolves a method based on an index and performs access checks to ensure
* the referrer can access the resolved method.
*
* Does not throw exceptions.
*
* Sets "*failure" on failure.
*/
static Method* ResolveMethodAndCheckAccess(const DexFile* dex_file,
uint32_t method_idx, const Class* referrer, VerifyError* failure,
bool is_direct);
/*
* Resolves a field based on an index and performs access checks to ensure
* the referrer can access the resolved field.
*
* Exceptions caused by failures are cleared before returning.
*
* Sets "*failure" on failure.
*/
static Field* ResolveFieldAndCheckAccess(const DexFile* dex_file,
uint32_t class_idx, const Class* referrer, VerifyError* failure,
bool is_static);
/*
* Merge two RegType values.
*
* Sets "*changed" to "true" if the result doesn't match "type1".
*/
static RegType MergeTypes(RegType type1, RegType type2, bool* changed);
/*
* 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 "*changed" to "true" if the result doesn't match "ents1".
*/
static MonitorEntries MergeMonitorEntries(MonitorEntries ents1,
MonitorEntries ents2, bool* changed);
/*
* 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* register_line,
int insn_reg_count, UninitInstanceMap* uninit_map, RegType uninit_type);
/*
* Control can transfer to "next_insn".
*
* Merge the registers from "work_line" into "reg_table" at "next_insn", and
* set the "changed" flag on the target address if any of the registers
* has changed.
*
* Returns "false" if we detect mismatched monitor stacks.
*/
static bool UpdateRegisters(InsnFlags* insn_flags, RegisterTable* reg_table,
int next_insn, const RegisterLine* work_line);
/*
* Determine whether we can convert "src_type" to "check_type", where
* "check_type" is one of the category-1 non-reference types.
*
* Constant derived types may become floats, but other values may not.
*/
static bool CanConvertTo1nr(RegType src_type, RegType check_type);
/* Determine whether the category-2 types are compatible. */
static bool CanConvertTo2(RegType src_type, RegType check_type);
/* Convert a VM PrimitiveType enum value to the equivalent RegType value. */
static RegType PrimitiveTypeToRegType(Class::PrimitiveType prim_type);
/*
* 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 const_type);
/*
* 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(int32_t value);
/*
* If "field" is marked "final", make sure this is the either <clinit>
* or <init> as appropriate.
*
* Sets "*failure" on failure.
*/
static void CheckFinalFieldAccess(const Method* method, const Field* field,
VerifyError* failure);
/*
* Make sure that the register type is suitable for use as an array index.
*
* Sets "*failure" if not.
*/
static void CheckArrayIndexType(const Method* method, RegType reg_type,
VerifyError* failure);
/*
* Check constraints on constructor return. Specifically, make sure that
* the "this" argument got initialized.
*
* The "this" argument to <init> uses code offset kUninitThisArgAddr, which
* puts it at the start of the list in slot 0. If we see a register with
* an uninitialized slot 0 reference, we know it somehow didn't get
* initialized.
*
* Returns "true" if all is well.
*/
static bool CheckConstructorReturn(const Method* method,
const RegisterLine* register_line, const int insn_reg_count);
/*
* Verify that the target instruction is not "move-exception". It's important
* that the only way to execute a move-exception is as the first instruction
* of an exception handler.
*
* Returns "true" if all is well, "false" if the target instruction is
* move-exception.
*/
static bool CheckMoveException(const uint16_t* insns, int insn_idx);
/*
* 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 "*failure" if something looks wrong.
*/
static void CheckTypeCategory(RegType type, TypeCategory cat,
VerifyError* failure);
/*
* For a category 2 register pair, verify that "type_h" is the appropriate
* high part for "type_l".
*
* Does not verify that "type_l" is in fact the low part of a 64-bit
* register pair.
*/
static void CheckWidePair(RegType type_l, RegType type_h,
VerifyError* failure);
/*
* Verify types for a simple two-register instruction (e.g. "neg-int").
* "dst_type" is stored into vA, and "src_type" is verified against vB.
*/
static void CheckUnop(RegisterLine* register_line,
Instruction::DecodedInstruction* dec_insn, RegType dst_type,
RegType src_type, VerifyError* failure);
/*
* Verify types for a simple three-register instruction (e.g. "add-int").
* "dst_type" is stored into vA, and "src_type1"/"src_type2" are verified
* against vB/vC.
*/
static void CheckBinop(RegisterLine* register_line,
Instruction::DecodedInstruction* dec_insn, RegType dst_type,
RegType src_type1, RegType src_type2, bool check_boolean_op,
VerifyError* failure);
/*
* Verify types for a binary "2addr" operation. "src_type1"/"src_type2"
* are verified against vA/vB, then "dst_type" is stored into vA.
*/
static void CheckBinop2addr(RegisterLine* register_line,
Instruction::DecodedInstruction* dec_insn, RegType dst_type,
RegType src_type1, RegType src_type2, bool check_boolean_op,
VerifyError* failure);
/*
* 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* register_line, int reg,
unsigned int shift_count, bool is_unsigned_shift);
/*
* 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* register_line, uint32_t reg1,
uint32_t reg2);
/*
* Verify types for A two-register instruction with a literal constant
* (e.g. "add-int/lit8"). "dst_type" is stored into vA, and "src_type" is
* verified against vB.
*
* If "check_boolean_op" is set, we use the constant value in vC.
*/
static void CheckLitop(RegisterLine* register_line,
Instruction::DecodedInstruction* dec_insn, RegType dst_type,
RegType src_type, bool check_boolean_op, VerifyError* failure);
/*
* Verify that the arguments in a filled-new-array instruction are valid.
*
* "res_class" is the class refered to by dec_insn->vB_.
*/
static void VerifyFilledNewArrayRegs(const Method* method,
RegisterLine* register_line,
const Instruction::DecodedInstruction* dec_insn, Class* res_class,
bool is_range, VerifyError* failure);
/* See if the method matches the MethodType. */
static bool IsCorrectInvokeKind(MethodType method_type, Method* res_method);
/*
* 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 "is_range" 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 *failure
* set appropriately).
*/
static Method* VerifyInvocationArgs(VerifierData* vdata,
RegisterLine* register_line, const int insn_reg_count,
const Instruction::DecodedInstruction* dec_insn, MethodType method_type,
bool is_range, bool is_super, VerifyError* failure);
DISALLOW_COPY_AND_ASSIGN(DexVerifier);
};
} // namespace art
#endif // ART_SRC_DEX_VERIFY_H_