CodeVerify.h revision d862faa2ceae186da5518607505eb942d634ced9
1/* 2 * Copyright (C) 2008 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17/* 18 * Dalvik bytecode verifier. 19 */ 20#ifndef _DALVIK_CODEVERIFY 21#define _DALVIK_CODEVERIFY 22 23#include "analysis/VerifySubs.h" 24#include "analysis/VfyBasicBlock.h" 25 26/* 27 * Enumeration for register type values. The "hi" piece of a 64-bit value 28 * MUST immediately follow the "lo" piece in the enumeration, so we can check 29 * that hi==lo+1. 30 * 31 * Assignment of constants: 32 * [-MAXINT,-32768) : integer 33 * [-32768,-128) : short 34 * [-128,0) : byte 35 * 0 : zero 36 * 1 : one 37 * [2,128) : posbyte 38 * [128,32768) : posshort 39 * [32768,65536) : char 40 * [65536,MAXINT] : integer 41 * 42 * Allowed "implicit" widening conversions: 43 * zero -> boolean, posbyte, byte, posshort, short, char, integer, ref (null) 44 * one -> boolean, posbyte, byte, posshort, short, char, integer 45 * boolean -> posbyte, byte, posshort, short, char, integer 46 * posbyte -> posshort, short, integer, char 47 * byte -> short, integer 48 * posshort -> integer, char 49 * short -> integer 50 * char -> integer 51 * 52 * In addition, all of the above can convert to "float". 53 * 54 * We're more careful with integer values than the spec requires. The 55 * motivation is to restrict byte/char/short to the correct range of values. 56 * For example, if a method takes a byte argument, we don't want to allow 57 * the code to load the constant "1024" and pass it in. 58 */ 59enum { 60 kRegTypeUnknown = 0, /* initial state; use value=0 so calloc works */ 61 kRegTypeUninit = 1, /* MUST be odd to distinguish from pointer */ 62 kRegTypeConflict, /* merge clash makes this reg's type unknowable */ 63 64 /* 65 * Category-1nr types. The order of these is chiseled into a couple 66 * of tables, so don't add, remove, or reorder if you can avoid it. 67 */ 68#define kRegType1nrSTART kRegTypeFloat 69 kRegTypeFloat, 70 kRegTypeZero, /* 32-bit 0, could be Boolean, Int, Float, or Ref */ 71 kRegTypeOne, /* 32-bit 1, could be Boolean, Int, Float */ 72 kRegTypeBoolean, /* must be 0 or 1 */ 73 kRegTypePosByte, /* byte, known positive (can become char) */ 74 kRegTypeByte, 75 kRegTypePosShort, /* short, known positive (can become char) */ 76 kRegTypeShort, 77 kRegTypeChar, 78 kRegTypeInteger, 79#define kRegType1nrEND kRegTypeInteger 80 81 kRegTypeLongLo, /* lower-numbered register; endian-independent */ 82 kRegTypeLongHi, 83 kRegTypeDoubleLo, 84 kRegTypeDoubleHi, 85 86 /* 87 * Enumeration max; this is used with "full" (32-bit) RegType values. 88 * 89 * Anything larger than this is a ClassObject or uninit ref. Mask off 90 * all but the low 8 bits; if you're left with kRegTypeUninit, pull 91 * the uninit index out of the high 24. Because kRegTypeUninit has an 92 * odd value, there is no risk of a particular ClassObject pointer bit 93 * pattern being confused for it (assuming our class object allocator 94 * uses word alignment). 95 */ 96 kRegTypeMAX 97}; 98#define kRegTypeUninitMask 0xff 99#define kRegTypeUninitShift 8 100 101/* 102 * RegType holds information about the type of data held in a register. 103 * For most types it's a simple enum. For reference types it holds a 104 * pointer to the ClassObject, and for uninitialized references it holds 105 * an index into the UninitInstanceMap. 106 */ 107typedef u4 RegType; 108 109/* 110 * A bit vector indicating which entries in the monitor stack are 111 * associated with this register. The low bit corresponds to the stack's 112 * bottom-most entry. 113 */ 114typedef u4 MonitorEntries; 115#define kMaxMonitorStackDepth (sizeof(MonitorEntries) * 8) 116 117/* 118 * During verification, we associate one of these with every "interesting" 119 * instruction. We track the status of all registers, and (if the method 120 * has any monitor-enter instructions) maintain a stack of entered monitors 121 * (identified by code unit offset). 122 * 123 * If live-precise register maps are enabled, the "liveRegs" vector will 124 * be populated. Unlike the other lists of registers here, we do not 125 * track the liveness of the method result register (which is not visible 126 * to the GC). 127 */ 128struct RegisterLine { 129 RegType* regTypes; 130 MonitorEntries* monitorEntries; 131 u4* monitorStack; 132 unsigned int monitorStackTop; 133 BitVector* liveRegs; 134}; 135 136/* 137 * Table that maps uninitialized instances to classes, based on the 138 * address of the new-instance instruction. One per method. 139 */ 140struct UninitInstanceMap { 141 int numEntries; 142 struct { 143 int addr; /* code offset, or -1 for method arg ("this") */ 144 ClassObject* clazz; /* class created at this address */ 145 } map[1]; 146}; 147#define kUninitThisArgAddr (-1) 148#define kUninitThisArgSlot 0 149 150/* 151 * Various bits of data used by the verifier and register map generator. 152 */ 153struct VerifierData { 154 /* 155 * The method we're working on. 156 */ 157 const Method* method; 158 159 /* 160 * Number of code units of instructions in the method. A cache of the 161 * value calculated by dvmGetMethodInsnsSize(). 162 */ 163 u4 insnsSize; 164 165 /* 166 * Number of registers we track for each instruction. This is equal 167 * to the method's declared "registersSize". (Does not include the 168 * pending return value.) 169 */ 170 u4 insnRegCount; 171 172 /* 173 * Instruction widths and flags, one entry per code unit. 174 */ 175 InsnFlags* insnFlags; 176 177 /* 178 * Uninitialized instance map, used for tracking the movement of 179 * objects that have been allocated but not initialized. 180 */ 181 UninitInstanceMap* uninitMap; 182 183 /* 184 * Array of RegisterLine structs, one entry per code unit. We only need 185 * entries for code units that hold the start of an "interesting" 186 * instruction. For register map generation, we're only interested 187 * in GC points. 188 */ 189 RegisterLine* registerLines; 190 191 /* 192 * The number of occurrences of specific opcodes. 193 */ 194 size_t newInstanceCount; 195 size_t monitorEnterCount; 196 197 /* 198 * Array of pointers to basic blocks, one entry per code unit. Used 199 * for liveness analysis. 200 */ 201 VfyBasicBlock** basicBlocks; 202}; 203 204 205/* table with static merge logic for primitive types */ 206extern const char gDvmMergeTab[kRegTypeMAX][kRegTypeMAX]; 207 208 209/* 210 * Returns "true" if the flags indicate that this address holds the start 211 * of an instruction. 212 */ 213INLINE bool dvmInsnIsOpcode(const InsnFlags* insnFlags, int addr) { 214 return (insnFlags[addr] & kInsnFlagWidthMask) != 0; 215} 216 217/* 218 * Extract the unsigned 16-bit instruction width from "flags". 219 */ 220INLINE int dvmInsnGetWidth(const InsnFlags* insnFlags, int addr) { 221 return insnFlags[addr] & kInsnFlagWidthMask; 222} 223 224/* 225 * Changed? 226 */ 227INLINE bool dvmInsnIsChanged(const InsnFlags* insnFlags, int addr) { 228 return (insnFlags[addr] & kInsnFlagChanged) != 0; 229} 230INLINE void dvmInsnSetChanged(InsnFlags* insnFlags, int addr, bool changed) 231{ 232 if (changed) 233 insnFlags[addr] |= kInsnFlagChanged; 234 else 235 insnFlags[addr] &= ~kInsnFlagChanged; 236} 237 238/* 239 * Visited? 240 */ 241INLINE bool dvmInsnIsVisited(const InsnFlags* insnFlags, int addr) { 242 return (insnFlags[addr] & kInsnFlagVisited) != 0; 243} 244INLINE void dvmInsnSetVisited(InsnFlags* insnFlags, int addr, bool changed) 245{ 246 if (changed) 247 insnFlags[addr] |= kInsnFlagVisited; 248 else 249 insnFlags[addr] &= ~kInsnFlagVisited; 250} 251 252/* 253 * Visited or changed? 254 */ 255INLINE bool dvmInsnIsVisitedOrChanged(const InsnFlags* insnFlags, int addr) { 256 return (insnFlags[addr] & (kInsnFlagVisited|kInsnFlagChanged)) != 0; 257} 258 259/* 260 * In a "try" block? 261 */ 262INLINE bool dvmInsnIsInTry(const InsnFlags* insnFlags, int addr) { 263 return (insnFlags[addr] & kInsnFlagInTry) != 0; 264} 265INLINE void dvmInsnSetInTry(InsnFlags* insnFlags, int addr, bool inTry) 266{ 267 assert(inTry); 268 //if (inTry) 269 insnFlags[addr] |= kInsnFlagInTry; 270 //else 271 // insnFlags[addr] &= ~kInsnFlagInTry; 272} 273 274/* 275 * Instruction is a branch target or exception handler? 276 */ 277INLINE bool dvmInsnIsBranchTarget(const InsnFlags* insnFlags, int addr) { 278 return (insnFlags[addr] & kInsnFlagBranchTarget) != 0; 279} 280INLINE void dvmInsnSetBranchTarget(InsnFlags* insnFlags, int addr, 281 bool isBranch) 282{ 283 assert(isBranch); 284 //if (isBranch) 285 insnFlags[addr] |= kInsnFlagBranchTarget; 286 //else 287 // insnFlags[addr] &= ~kInsnFlagBranchTarget; 288} 289 290/* 291 * Instruction is a GC point? 292 */ 293INLINE bool dvmInsnIsGcPoint(const InsnFlags* insnFlags, int addr) { 294 return (insnFlags[addr] & kInsnFlagGcPoint) != 0; 295} 296INLINE void dvmInsnSetGcPoint(InsnFlags* insnFlags, int addr, 297 bool isGcPoint) 298{ 299 assert(isGcPoint); 300 //if (isGcPoint) 301 insnFlags[addr] |= kInsnFlagGcPoint; 302 //else 303 // insnFlags[addr] &= ~kInsnFlagGcPoint; 304} 305 306 307/* 308 * Create a new UninitInstanceMap. 309 */ 310UninitInstanceMap* dvmCreateUninitInstanceMap(const Method* meth, 311 const InsnFlags* insnFlags, int newInstanceCount); 312 313/* 314 * Release the storage associated with an UninitInstanceMap. 315 */ 316void dvmFreeUninitInstanceMap(UninitInstanceMap* uninitMap); 317 318/* 319 * Verify bytecode in "meth". "insnFlags" should be populated with 320 * instruction widths and "in try" flags. 321 */ 322bool dvmVerifyCodeFlow(VerifierData* vdata); 323 324#endif /*_DALVIK_CODEVERIFY*/ 325