vm/analysis/CodeVerify.h

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