Home | History | Annotate | Download | only in analysis
      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 structural verifier.  The only public entry point
     19  * (except for a few shared utility functions) is dvmVerifyCodeFlow().
     20  *
     21  * TODO: might benefit from a signature-->class lookup cache.  Could avoid
     22  * some string-peeling and wouldn't need to compute hashes.
     23  */
     24 #include "Dalvik.h"
     25 #include "analysis/Liveness.h"
     26 #include "analysis/CodeVerify.h"
     27 #include "analysis/Optimize.h"
     28 #include "analysis/RegisterMap.h"
     29 #include "libdex/DexCatch.h"
     30 #include "libdex/InstrUtils.h"
     31 
     32 #include <stddef.h>
     33 
     34 
     35 /*
     36  * We don't need to store the register data for many instructions, because
     37  * we either only need it at branch points (for verification) or GC points
     38  * and branches (for verification + type-precise register analysis).
     39  */
     40 enum RegisterTrackingMode {
     41     kTrackRegsBranches,
     42     kTrackRegsGcPoints,
     43     kTrackRegsAll
     44 };
     45 
     46 /*
     47  * Set this to enable dead code scanning.  This is not required, but it's
     48  * very useful when testing changes to the verifier (to make sure we're not
     49  * skipping over stuff) and for checking the optimized output from "dx".
     50  * The only reason not to do it is that it slightly increases the time
     51  * required to perform verification.
     52  */
     53 #ifndef NDEBUG
     54 # define DEAD_CODE_SCAN  true
     55 #else
     56 # define DEAD_CODE_SCAN  false
     57 #endif
     58 
     59 static bool gDebugVerbose = false;
     60 
     61 #define SHOW_REG_DETAILS \
     62     (0 | DRT_SHOW_LIVENESS /*| DRT_SHOW_REF_TYPES | DRT_SHOW_LOCALS*/)
     63 
     64 /*
     65  * We need an extra "pseudo register" to hold the return type briefly.  It
     66  * can be category 1 or 2, so we need two slots.
     67  */
     68 #define kExtraRegs  2
     69 #define RESULT_REGISTER(_insnRegCount)  (_insnRegCount)
     70 
     71 /*
     72  * Big fat collection of register data.
     73  */
     74 typedef struct RegisterTable {
     75     /*
     76      * Array of RegisterLine structs, one per address in the method.  We only
     77      * set the pointers for certain addresses, based on instruction widths
     78      * and what we're trying to accomplish.
     79      */
     80     RegisterLine* registerLines;
     81 
     82     /*
     83      * Number of registers we track for each instruction.  This is equal
     84      * to the method's declared "registersSize" plus kExtraRegs.
     85      */
     86     size_t      insnRegCountPlus;
     87 
     88     /*
     89      * Storage for a register line we're currently working on.
     90      */
     91     RegisterLine workLine;
     92 
     93     /*
     94      * Storage for a register line we're saving for later.
     95      */
     96     RegisterLine savedLine;
     97 
     98     /*
     99      * A single large alloc, with all of the storage needed for RegisterLine
    100      * data (RegType array, MonitorEntries array, monitor stack).
    101      */
    102     void*       lineAlloc;
    103 } RegisterTable;
    104 
    105 
    106 /* fwd */
    107 #ifndef NDEBUG
    108 static void checkMergeTab();
    109 #endif
    110 static bool isInitMethod(const Method* meth);
    111 static RegType getInvocationThis(const RegisterLine* registerLine,\
    112     const DecodedInstruction* pDecInsn, VerifyError* pFailure);
    113 static void verifyRegisterType(RegisterLine* registerLine, \
    114     u4 vsrc, RegType checkType, VerifyError* pFailure);
    115 static bool doCodeVerification(VerifierData* vdata, RegisterTable* regTable);
    116 static bool verifyInstruction(const Method* meth, InsnFlags* insnFlags,\
    117     RegisterTable* regTable, int insnIdx, UninitInstanceMap* uninitMap,
    118     int* pStartGuess);
    119 static ClassObject* findCommonSuperclass(ClassObject* c1, ClassObject* c2);
    120 static void dumpRegTypes(const VerifierData* vdata, \
    121     const RegisterLine* registerLine, int addr, const char* addrName,
    122     const UninitInstanceMap* uninitMap, int displayFlags);
    123 
    124 /* bit values for dumpRegTypes() "displayFlags" */
    125 enum {
    126     DRT_SIMPLE          = 0,
    127     DRT_SHOW_REF_TYPES  = 0x01,
    128     DRT_SHOW_LOCALS     = 0x02,
    129     DRT_SHOW_LIVENESS   = 0x04,
    130 };
    131 
    132 
    133 /*
    134  * ===========================================================================
    135  *      RegType and UninitInstanceMap utility functions
    136  * ===========================================================================
    137  */
    138 
    139 #define __  kRegTypeUnknown
    140 #define _U  kRegTypeUninit
    141 #define _X  kRegTypeConflict
    142 #define _0  kRegTypeZero
    143 #define _1  kRegTypeOne
    144 #define _Z  kRegTypeBoolean
    145 #define _y  kRegTypeConstPosByte
    146 #define _Y  kRegTypeConstByte
    147 #define _h  kRegTypeConstPosShort
    148 #define _H  kRegTypeConstShort
    149 #define _c  kRegTypeConstChar
    150 #define _i  kRegTypeConstInteger
    151 #define _b  kRegTypePosByte
    152 #define _B  kRegTypeByte
    153 #define _s  kRegTypePosShort
    154 #define _S  kRegTypeShort
    155 #define _C  kRegTypeChar
    156 #define _I  kRegTypeInteger
    157 #define _F  kRegTypeFloat
    158 #define _N  kRegTypeConstLo
    159 #define _n  kRegTypeConstHi
    160 #define _J  kRegTypeLongLo
    161 #define _j  kRegTypeLongHi
    162 #define _D  kRegTypeDoubleLo
    163 #define _d  kRegTypeDoubleHi
    164 
    165 /*
    166  * Merge result table for primitive values.  The table is symmetric along
    167  * the diagonal.
    168  *
    169  * Note that 32-bit int/float do not merge into 64-bit long/double.  This
    170  * is a register merge, not a widening conversion.  Only the "implicit"
    171  * widening within a category, e.g. byte to short, is allowed.
    172  *
    173  * Dalvik does not draw a distinction between int and float, but we enforce
    174  * that once a value is used as int, it can't be used as float, and vice
    175  * versa. We do not allow free exchange between 32-bit int/float and 64-bit
    176  * long/double.
    177  *
    178  * Note that Uninit+Uninit=Uninit.  This holds true because we only
    179  * use this when the RegType value is exactly equal to kRegTypeUninit, which
    180  * can only happen for the zeroeth entry in the table.
    181  *
    182  * "Unknown" never merges with anything known.  The only time a register
    183  * transitions from "unknown" to "known" is when we're executing code
    184  * for the first time, and we handle that with a simple copy.
    185  */
    186 const char gDvmMergeTab[kRegTypeMAX][kRegTypeMAX] =
    187 {
    188     /* 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 */
    189     { /*_*/ __,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X,_X },
    190     { /*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 },
    191     { /*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 },
    192     { /*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 },
    193     { /*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 },
    194     { /*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 },
    195     { /*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 },
    196     { /*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 },
    197     { /*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 },
    198     { /*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 },
    199     { /*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 },
    200     { /*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 },
    201     { /*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 },
    202     { /*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 },
    203     { /*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 },
    204     { /*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 },
    205     { /*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 },
    206     { /*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 },
    207     { /*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 },
    208     { /*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 },
    209     { /*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 },
    210     { /*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 },
    211     { /*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 },
    212     { /*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 },
    213     { /*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 },
    214 };
    215 
    216 #undef __
    217 #undef _U
    218 #undef _X
    219 #undef _0
    220 #undef _1
    221 #undef _Z
    222 #undef _y
    223 #undef _Y
    224 #undef _h
    225 #undef _H
    226 #undef _c
    227 #undef _i
    228 #undef _b
    229 #undef _B
    230 #undef _s
    231 #undef _S
    232 #undef _C
    233 #undef _I
    234 #undef _F
    235 #undef _N
    236 #undef _n
    237 #undef _J
    238 #undef _j
    239 #undef _D
    240 #undef _d
    241 
    242 #ifndef NDEBUG
    243 /*
    244  * Verify symmetry in the conversion table.
    245  */
    246 static void checkMergeTab()
    247 {
    248     int i, j;
    249 
    250     for (i = 0; i < kRegTypeMAX; i++) {
    251         for (j = i; j < kRegTypeMAX; j++) {
    252             if (gDvmMergeTab[i][j] != gDvmMergeTab[j][i]) {
    253                 ALOGE("Symmetry violation: %d,%d vs %d,%d", i, j, j, i);
    254                 dvmAbort();
    255             }
    256         }
    257     }
    258 }
    259 #endif
    260 
    261 /*
    262  * Determine whether we can convert "srcType" to "checkType", where
    263  * "checkType" is one of the category-1 non-reference types.
    264  *
    265  * Constant derived types may become floats, but other values may not.
    266  */
    267 static bool canConvertTo1nr(RegType srcType, RegType checkType)
    268 {
    269     static const char convTab
    270         [kRegType1nrEND-kRegType1nrSTART+1][kRegType1nrEND-kRegType1nrSTART+1] =
    271     {
    272         /* chk: 0  1  Z  y  Y  h  H  c  i  b  B  s  S  C  I  F */
    273         { /*0*/ 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
    274         { /*1*/ 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
    275         { /*Z*/ 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
    276         { /*y*/ 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
    277         { /*Y*/ 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1 },
    278         { /*h*/ 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1 },
    279         { /*H*/ 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1 },
    280         { /*c*/ 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1 },
    281         { /*i*/ 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1 },
    282         { /*b*/ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0 },
    283         { /*B*/ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0 },
    284         { /*s*/ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0 },
    285         { /*S*/ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0 },
    286         { /*C*/ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0 },
    287         { /*I*/ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 },
    288         { /*F*/ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
    289     };
    290 
    291     assert(checkType >= kRegType1nrSTART && checkType <= kRegType1nrEND);
    292 #if 0
    293     if (checkType < kRegType1nrSTART || checkType > kRegType1nrEND) {
    294         LOG_VFY("Unexpected checkType %d (srcType=%d)", checkType, srcType);
    295         assert(false);
    296         return false;
    297     }
    298 #endif
    299 
    300     //printf("convTab[%d][%d] = %d\n", srcType, checkType,
    301     //    convTab[srcType-kRegType1nrSTART][checkType-kRegType1nrSTART]);
    302     if (srcType >= kRegType1nrSTART && srcType <= kRegType1nrEND)
    303         return (bool) convTab[srcType-kRegType1nrSTART][checkType-kRegType1nrSTART];
    304 
    305     return false;
    306 }
    307 
    308 /*
    309  * Determine whether the category-2 types are compatible.
    310  */
    311 static bool canConvertTo2(RegType srcType, RegType checkType)
    312 {
    313     return ((srcType == kRegTypeConstLo || srcType == checkType) &&
    314             (checkType == kRegTypeLongLo || checkType == kRegTypeDoubleLo));
    315 }
    316 
    317 /*
    318  * Determine whether or not "instrType" and "targetType" are compatible,
    319  * for purposes of getting or setting a value in a field or array.  The
    320  * idea is that an instruction with a category 1nr type (say, aget-short
    321  * or iput-boolean) is accessing a static field, instance field, or array
    322  * entry, and we want to make sure sure that the operation is legal.
    323  *
    324  * At a minimum, source and destination must have the same width.  We
    325  * further refine this to assert that "short" and "char" are not
    326  * compatible, because the sign-extension is different on the "get"
    327  * operations.
    328  *
    329  * We're not considering the actual contents of the register, so we'll
    330  * never get "pseudo-types" like kRegTypeZero or kRegTypePosShort.  We
    331  * could get kRegTypeUnknown in "targetType" if a field or array class
    332  * lookup failed.  Category 2 types and references are checked elsewhere.
    333  */
    334 static bool checkFieldArrayStore1nr(RegType instrType, RegType targetType)
    335 {
    336     return (instrType == targetType);
    337 }
    338 
    339 /*
    340  * Convert a VM PrimitiveType enum value to the equivalent RegType value.
    341  */
    342 static RegType primitiveTypeToRegType(PrimitiveType primType)
    343 {
    344     switch (primType) {
    345         case PRIM_BOOLEAN: return kRegTypeBoolean;
    346         case PRIM_BYTE:    return kRegTypeByte;
    347         case PRIM_SHORT:   return kRegTypeShort;
    348         case PRIM_CHAR:    return kRegTypeChar;
    349         case PRIM_INT:     return kRegTypeInteger;
    350         case PRIM_LONG:    return kRegTypeLongLo;
    351         case PRIM_FLOAT:   return kRegTypeFloat;
    352         case PRIM_DOUBLE:  return kRegTypeDoubleLo;
    353         case PRIM_VOID:
    354         default: {
    355             assert(false);
    356             return kRegTypeUnknown;
    357         }
    358     }
    359 }
    360 
    361 /*
    362  * Convert a const derived RegType to the equivalent non-const RegType value.
    363  * Does nothing if the argument type isn't const derived.
    364  */
    365 static RegType constTypeToRegType(RegType constType)
    366 {
    367     switch (constType) {
    368         case kRegTypeConstPosByte: return kRegTypePosByte;
    369         case kRegTypeConstByte: return kRegTypeByte;
    370         case kRegTypeConstPosShort: return kRegTypePosShort;
    371         case kRegTypeConstShort: return kRegTypeShort;
    372         case kRegTypeConstChar: return kRegTypeChar;
    373         case kRegTypeConstInteger: return kRegTypeInteger;
    374         default: {
    375             return constType;
    376         }
    377     }
    378 }
    379 
    380 /*
    381  * Given a 32-bit constant, return the most-restricted RegType enum entry
    382  * that can hold the value. The types used here indicate the value came
    383  * from a const instruction, and may not correctly represent the real type
    384  * of the value. Upon use, a constant derived type is updated with the
    385  * type from the use, which will be unambiguous.
    386  */
    387 static char determineCat1Const(s4 value)
    388 {
    389     if (value < -32768)
    390         return kRegTypeConstInteger;
    391     else if (value < -128)
    392         return kRegTypeConstShort;
    393     else if (value < 0)
    394         return kRegTypeConstByte;
    395     else if (value == 0)
    396         return kRegTypeZero;
    397     else if (value == 1)
    398         return kRegTypeOne;
    399     else if (value < 128)
    400         return kRegTypeConstPosByte;
    401     else if (value < 32768)
    402         return kRegTypeConstPosShort;
    403     else if (value < 65536)
    404         return kRegTypeConstChar;
    405     else
    406         return kRegTypeConstInteger;
    407 }
    408 
    409 /*
    410  * Create a new uninitialized instance map.
    411  *
    412  * The map is allocated and populated with address entries.  The addresses
    413  * appear in ascending order to allow binary searching.
    414  *
    415  * Very few methods have 10 or more new-instance instructions; the
    416  * majority have 0 or 1.  Occasionally a static initializer will have 200+.
    417  *
    418  * TODO: merge this into the static pass or initRegisterTable; want to
    419  * avoid walking through the instructions yet again just to set up this table
    420  */
    421 UninitInstanceMap* dvmCreateUninitInstanceMap(const Method* meth,
    422     const InsnFlags* insnFlags, int newInstanceCount)
    423 {
    424     const int insnsSize = dvmGetMethodInsnsSize(meth);
    425     const u2* insns = meth->insns;
    426     UninitInstanceMap* uninitMap;
    427     bool isInit = false;
    428     int idx, addr;
    429 
    430     if (isInitMethod(meth)) {
    431         newInstanceCount++;
    432         isInit = true;
    433     }
    434 
    435     /*
    436      * Allocate the header and map as a single unit.
    437      *
    438      * TODO: consider having a static instance so we can avoid allocations.
    439      * I don't think the verifier is guaranteed to be single-threaded when
    440      * running in the VM (rather than dexopt), so that must be taken into
    441      * account.
    442      */
    443     int size = offsetof(UninitInstanceMap, map) +
    444                 newInstanceCount * sizeof(uninitMap->map[0]);
    445     uninitMap = (UninitInstanceMap*)calloc(1, size);
    446     if (uninitMap == NULL)
    447         return NULL;
    448     uninitMap->numEntries = newInstanceCount;
    449 
    450     idx = 0;
    451     if (isInit) {
    452         uninitMap->map[idx++].addr = kUninitThisArgAddr;
    453     }
    454 
    455     /*
    456      * Run through and find the new-instance instructions.
    457      */
    458     for (addr = 0; addr < insnsSize; /**/) {
    459         int width = dvmInsnGetWidth(insnFlags, addr);
    460 
    461         Opcode opcode = dexOpcodeFromCodeUnit(*insns);
    462         if (opcode == OP_NEW_INSTANCE)
    463             uninitMap->map[idx++].addr = addr;
    464 
    465         addr += width;
    466         insns += width;
    467     }
    468 
    469     assert(idx == newInstanceCount);
    470     return uninitMap;
    471 }
    472 
    473 /*
    474  * Free the map.
    475  */
    476 void dvmFreeUninitInstanceMap(UninitInstanceMap* uninitMap)
    477 {
    478     free(uninitMap);
    479 }
    480 
    481 /*
    482  * Set the class object associated with the instruction at "addr".
    483  *
    484  * Returns the map slot index, or -1 if the address isn't listed in the map
    485  * (shouldn't happen) or if a class is already associated with the address
    486  * (bad bytecode).
    487  *
    488  * Entries, once set, do not change -- a given address can only allocate
    489  * one type of object.
    490  */
    491 static int setUninitInstance(UninitInstanceMap* uninitMap, int addr,
    492     ClassObject* clazz)
    493 {
    494     int idx;
    495 
    496     assert(clazz != NULL);
    497 
    498 #ifdef VERIFIER_STATS
    499     gDvm.verifierStats.uninitSearches++;
    500 #endif
    501 
    502     /* TODO: binary search when numEntries > 8 */
    503     for (idx = uninitMap->numEntries - 1; idx >= 0; idx--) {
    504         if (uninitMap->map[idx].addr == addr) {
    505             if (uninitMap->map[idx].clazz != NULL &&
    506                 uninitMap->map[idx].clazz != clazz)
    507             {
    508                 LOG_VFY("VFY: addr %d already set to %p, not setting to %p",
    509                     addr, uninitMap->map[idx].clazz, clazz);
    510                 return -1;          // already set to something else??
    511             }
    512             uninitMap->map[idx].clazz = clazz;
    513             return idx;
    514         }
    515     }
    516 
    517     LOG_VFY("VFY: addr %d not found in uninit map", addr);
    518     assert(false);      // shouldn't happen
    519     return -1;
    520 }
    521 
    522 /*
    523  * Get the class object at the specified index.
    524  */
    525 static ClassObject* getUninitInstance(const UninitInstanceMap* uninitMap,
    526     int idx)
    527 {
    528     assert(idx >= 0 && idx < uninitMap->numEntries);
    529     return uninitMap->map[idx].clazz;
    530 }
    531 
    532 /* determine if "type" is actually an object reference (init/uninit/zero) */
    533 static inline bool regTypeIsReference(RegType type) {
    534     return (type > kRegTypeMAX || type == kRegTypeUninit ||
    535             type == kRegTypeZero);
    536 }
    537 
    538 /* determine if "type" is an uninitialized object reference */
    539 static inline bool regTypeIsUninitReference(RegType type) {
    540     return ((type & kRegTypeUninitMask) == kRegTypeUninit);
    541 }
    542 
    543 /* convert the initialized reference "type" to a ClassObject pointer */
    544 /* (does not expect uninit ref types or "zero") */
    545 static ClassObject* regTypeInitializedReferenceToClass(RegType type)
    546 {
    547     assert(regTypeIsReference(type) && type != kRegTypeZero);
    548     if ((type & 0x01) == 0) {
    549         return (ClassObject*) type;
    550     } else {
    551         //LOG_VFY("VFY: attempted to use uninitialized reference");
    552         return NULL;
    553     }
    554 }
    555 
    556 /* extract the index into the uninitialized instance map table */
    557 static inline int regTypeToUninitIndex(RegType type) {
    558     assert(regTypeIsUninitReference(type));
    559     return (type & ~kRegTypeUninitMask) >> kRegTypeUninitShift;
    560 }
    561 
    562 /* convert the reference "type" to a ClassObject pointer */
    563 static ClassObject* regTypeReferenceToClass(RegType type,
    564     const UninitInstanceMap* uninitMap)
    565 {
    566     assert(regTypeIsReference(type) && type != kRegTypeZero);
    567     if (regTypeIsUninitReference(type)) {
    568         assert(uninitMap != NULL);
    569         return getUninitInstance(uninitMap, regTypeToUninitIndex(type));
    570     } else {
    571         return (ClassObject*) type;
    572     }
    573 }
    574 
    575 /* convert the ClassObject pointer to an (initialized) register type */
    576 static inline RegType regTypeFromClass(ClassObject* clazz) {
    577     return (u4) clazz;
    578 }
    579 
    580 /* return the RegType for the uninitialized reference in slot "uidx" */
    581 static RegType regTypeFromUninitIndex(int uidx) {
    582     return (u4) (kRegTypeUninit | (uidx << kRegTypeUninitShift));
    583 }
    584 
    585 
    586 /*
    587  * ===========================================================================
    588  *      Signature operations
    589  * ===========================================================================
    590  */
    591 
    592 /*
    593  * Is this method a constructor?
    594  */
    595 static bool isInitMethod(const Method* meth)
    596 {
    597     return (*meth->name == '<' && strcmp(meth->name+1, "init>") == 0);
    598 }
    599 
    600 /*
    601  * Is this method a class initializer?
    602  */
    603 #if 0
    604 static bool isClassInitMethod(const Method* meth)
    605 {
    606     return (*meth->name == '<' && strcmp(meth->name+1, "clinit>") == 0);
    607 }
    608 #endif
    609 
    610 /*
    611  * Look up a class reference given as a simple string descriptor.
    612  *
    613  * If we can't find it, return a generic substitute when possible.
    614  */
    615 static ClassObject* lookupClassByDescriptor(const Method* meth,
    616     const char* pDescriptor, VerifyError* pFailure)
    617 {
    618     /*
    619      * The javac compiler occasionally puts references to nonexistent
    620      * classes in signatures.  For example, if you have a non-static
    621      * inner class with no constructor, the compiler provides
    622      * a private <init> for you.  Constructing the class
    623      * requires <init>(parent), but the outer class can't call
    624      * that because the method is private.  So the compiler
    625      * generates a package-scope <init>(parent,bogus) method that
    626      * just calls the regular <init> (the "bogus" part being necessary
    627      * to distinguish the signature of the synthetic method).
    628      * Treating the bogus class as an instance of java.lang.Object
    629      * allows the verifier to process the class successfully.
    630      */
    631 
    632     //ALOGI("Looking up '%s'", typeStr);
    633     ClassObject* clazz;
    634     clazz = dvmFindClassNoInit(pDescriptor, meth->clazz->classLoader);
    635     if (clazz == NULL) {
    636         dvmClearOptException(dvmThreadSelf());
    637         if (strchr(pDescriptor, '$') != NULL) {
    638             ALOGV("VFY: unable to find class referenced in signature (%s)",
    639                 pDescriptor);
    640         } else {
    641             LOG_VFY("VFY: unable to find class referenced in signature (%s)",
    642                 pDescriptor);
    643         }
    644 
    645         if (pDescriptor[0] == '[') {
    646             /* We are looking at an array descriptor. */
    647 
    648             /*
    649              * There should never be a problem loading primitive arrays.
    650              */
    651             if (pDescriptor[1] != 'L' && pDescriptor[1] != '[') {
    652                 LOG_VFY("VFY: invalid char in signature in '%s'",
    653                     pDescriptor);
    654                 *pFailure = VERIFY_ERROR_GENERIC;
    655             }
    656 
    657             /*
    658              * Try to continue with base array type.  This will let
    659              * us pass basic stuff (e.g. get array len) that wouldn't
    660              * fly with an Object.  This is NOT correct if the
    661              * missing type is a primitive array, but we should never
    662              * have a problem loading those.  (I'm not convinced this
    663              * is correct or even useful.  Just use Object here?)
    664              */
    665             clazz = dvmFindClassNoInit("[Ljava/lang/Object;",
    666                 meth->clazz->classLoader);
    667         } else if (pDescriptor[0] == 'L') {
    668             /*
    669              * We are looking at a non-array reference descriptor;
    670              * try to continue with base reference type.
    671              */
    672             clazz = gDvm.classJavaLangObject;
    673         } else {
    674             /* We are looking at a primitive type. */
    675             LOG_VFY("VFY: invalid char in signature in '%s'", pDescriptor);
    676             *pFailure = VERIFY_ERROR_GENERIC;
    677         }
    678 
    679         if (clazz == NULL) {
    680             *pFailure = VERIFY_ERROR_GENERIC;
    681         }
    682     }
    683 
    684     if (dvmIsPrimitiveClass(clazz)) {
    685         LOG_VFY("VFY: invalid use of primitive type '%s'", pDescriptor);
    686         *pFailure = VERIFY_ERROR_GENERIC;
    687         clazz = NULL;
    688     }
    689 
    690     return clazz;
    691 }
    692 
    693 /*
    694  * Look up a class reference in a signature.  Could be an arg or the
    695  * return value.
    696  *
    697  * Advances "*pSig" to the last character in the signature (that is, to
    698  * the ';').
    699  *
    700  * NOTE: this is also expected to verify the signature.
    701  */
    702 static ClassObject* lookupSignatureClass(const Method* meth, const char** pSig,
    703     VerifyError* pFailure)
    704 {
    705     const char* sig = *pSig;
    706     const char* endp = sig;
    707 
    708     assert(sig != NULL && *sig == 'L');
    709 
    710     while (*++endp != ';' && *endp != '\0')
    711         ;
    712     if (*endp != ';') {
    713         LOG_VFY("VFY: bad signature component '%s' (missing ';')", sig);
    714         *pFailure = VERIFY_ERROR_GENERIC;
    715         return NULL;
    716     }
    717 
    718     endp++;    /* Advance past the ';'. */
    719     int typeLen = endp - sig;
    720     char typeStr[typeLen+1]; /* +1 for the '\0' */
    721     memcpy(typeStr, sig, typeLen);
    722     typeStr[typeLen] = '\0';
    723 
    724     *pSig = endp - 1; /* - 1 so that *pSig points at, not past, the ';' */
    725 
    726     return lookupClassByDescriptor(meth, typeStr, pFailure);
    727 }
    728 
    729 /*
    730  * Look up an array class reference in a signature.  Could be an arg or the
    731  * return value.
    732  *
    733  * Advances "*pSig" to the last character in the signature.
    734  *
    735  * NOTE: this is also expected to verify the signature.
    736  */
    737 static ClassObject* lookupSignatureArrayClass(const Method* meth,
    738     const char** pSig, VerifyError* pFailure)
    739 {
    740     const char* sig = *pSig;
    741     const char* endp = sig;
    742 
    743     assert(sig != NULL && *sig == '[');
    744 
    745     /* find the end */
    746     while (*++endp == '[' && *endp != '\0')
    747         ;
    748 
    749     if (*endp == 'L') {
    750         while (*++endp != ';' && *endp != '\0')
    751             ;
    752         if (*endp != ';') {
    753             LOG_VFY("VFY: bad signature component '%s' (missing ';')", sig);
    754             *pFailure = VERIFY_ERROR_GENERIC;
    755             return NULL;
    756         }
    757     }
    758 
    759     int typeLen = endp - sig +1;
    760     char typeStr[typeLen+1];
    761     memcpy(typeStr, sig, typeLen);
    762     typeStr[typeLen] = '\0';
    763 
    764     *pSig = endp;
    765 
    766     return lookupClassByDescriptor(meth, typeStr, pFailure);
    767 }
    768 
    769 /*
    770  * Set the register types for the first instruction in the method based on
    771  * the method signature.
    772  *
    773  * This has the side-effect of validating the signature.
    774  *
    775  * Returns "true" on success.
    776  */
    777 static bool setTypesFromSignature(const Method* meth, RegType* regTypes,
    778     UninitInstanceMap* uninitMap)
    779 {
    780     DexParameterIterator iterator;
    781     int actualArgs, expectedArgs, argStart;
    782     VerifyError failure = VERIFY_ERROR_NONE;
    783     const char* descriptor;
    784 
    785     dexParameterIteratorInit(&iterator, &meth->prototype);
    786     argStart = meth->registersSize - meth->insSize;
    787     expectedArgs = meth->insSize;     /* long/double count as two */
    788     actualArgs = 0;
    789 
    790     assert(argStart >= 0);      /* should have been verified earlier */
    791 
    792     /*
    793      * Include the "this" pointer.
    794      */
    795     if (!dvmIsStaticMethod(meth)) {
    796         /*
    797          * If this is a constructor for a class other than java.lang.Object,
    798          * mark the first ("this") argument as uninitialized.  This restricts
    799          * field access until the superclass constructor is called.
    800          */
    801         if (isInitMethod(meth) && meth->clazz != gDvm.classJavaLangObject) {
    802             int uidx = setUninitInstance(uninitMap, kUninitThisArgAddr,
    803                             meth->clazz);
    804             assert(uidx == 0);
    805             regTypes[argStart + actualArgs] = regTypeFromUninitIndex(uidx);
    806         } else {
    807             regTypes[argStart + actualArgs] = regTypeFromClass(meth->clazz);
    808         }
    809         actualArgs++;
    810     }
    811 
    812     for (;;) {
    813         descriptor = dexParameterIteratorNextDescriptor(&iterator);
    814 
    815         if (descriptor == NULL) {
    816             break;
    817         }
    818 
    819         if (actualArgs >= expectedArgs) {
    820             LOG_VFY("VFY: expected %d args, found more (%s)",
    821                 expectedArgs, descriptor);
    822             goto bad_sig;
    823         }
    824 
    825         switch (*descriptor) {
    826         case 'L':
    827         case '[':
    828             /*
    829              * We assume that reference arguments are initialized.  The
    830              * only way it could be otherwise (assuming the caller was
    831              * verified) is if the current method is <init>, but in that
    832              * case it's effectively considered initialized the instant
    833              * we reach here (in the sense that we can return without
    834              * doing anything or call virtual methods).
    835              */
    836             {
    837                 ClassObject* clazz =
    838                     lookupClassByDescriptor(meth, descriptor, &failure);
    839                 if (!VERIFY_OK(failure))
    840                     goto bad_sig;
    841                 regTypes[argStart + actualArgs] = regTypeFromClass(clazz);
    842             }
    843             actualArgs++;
    844             break;
    845         case 'Z':
    846             regTypes[argStart + actualArgs] = kRegTypeBoolean;
    847             actualArgs++;
    848             break;
    849         case 'C':
    850             regTypes[argStart + actualArgs] = kRegTypeChar;
    851             actualArgs++;
    852             break;
    853         case 'B':
    854             regTypes[argStart + actualArgs] = kRegTypeByte;
    855             actualArgs++;
    856             break;
    857         case 'I':
    858             regTypes[argStart + actualArgs] = kRegTypeInteger;
    859             actualArgs++;
    860             break;
    861         case 'S':
    862             regTypes[argStart + actualArgs] = kRegTypeShort;
    863             actualArgs++;
    864             break;
    865         case 'F':
    866             regTypes[argStart + actualArgs] = kRegTypeFloat;
    867             actualArgs++;
    868             break;
    869         case 'D':
    870             regTypes[argStart + actualArgs] = kRegTypeDoubleLo;
    871             regTypes[argStart + actualArgs +1] = kRegTypeDoubleHi;
    872             actualArgs += 2;
    873             break;
    874         case 'J':
    875             regTypes[argStart + actualArgs] = kRegTypeLongLo;
    876             regTypes[argStart + actualArgs +1] = kRegTypeLongHi;
    877             actualArgs += 2;
    878             break;
    879         default:
    880             LOG_VFY("VFY: unexpected signature type char '%c'", *descriptor);
    881             goto bad_sig;
    882         }
    883     }
    884 
    885     if (actualArgs != expectedArgs) {
    886         LOG_VFY("VFY: expected %d args, found %d", expectedArgs, actualArgs);
    887         goto bad_sig;
    888     }
    889 
    890     descriptor = dexProtoGetReturnType(&meth->prototype);
    891 
    892     /*
    893      * Validate return type.  We don't do the type lookup; just want to make
    894      * sure that it has the right format.  Only major difference from the
    895      * method argument format is that 'V' is supported.
    896      */
    897     switch (*descriptor) {
    898     case 'I':
    899     case 'C':
    900     case 'S':
    901     case 'B':
    902     case 'Z':
    903     case 'V':
    904     case 'F':
    905     case 'D':
    906     case 'J':
    907         if (*(descriptor+1) != '\0')
    908             goto bad_sig;
    909         break;
    910     case '[':
    911         /* single/multi, object/primitive */
    912         while (*++descriptor == '[')
    913             ;
    914         if (*descriptor == 'L') {
    915             while (*++descriptor != ';' && *descriptor != '\0')
    916                 ;
    917             if (*descriptor != ';')
    918                 goto bad_sig;
    919         } else {
    920             if (*(descriptor+1) != '\0')
    921                 goto bad_sig;
    922         }
    923         break;
    924     case 'L':
    925         /* could be more thorough here, but shouldn't be required */
    926         while (*++descriptor != ';' && *descriptor != '\0')
    927             ;
    928         if (*descriptor != ';')
    929             goto bad_sig;
    930         break;
    931     default:
    932         goto bad_sig;
    933     }
    934 
    935     return true;
    936 
    937 //fail:
    938 //    LOG_VFY_METH(meth, "VFY:  bad sig");
    939 //    return false;
    940 
    941 bad_sig:
    942     {
    943         char* desc = dexProtoCopyMethodDescriptor(&meth->prototype);
    944         LOG_VFY("VFY: bad signature '%s' for %s.%s",
    945             desc, meth->clazz->descriptor, meth->name);
    946         free(desc);
    947     }
    948     return false;
    949 }
    950 
    951 /*
    952  * Return the register type for the method.  We can't just use the
    953  * already-computed DalvikJniReturnType, because if it's a reference type
    954  * we need to do the class lookup.
    955  *
    956  * Returned references are assumed to be initialized.
    957  *
    958  * Returns kRegTypeUnknown for "void".
    959  */
    960 static RegType getMethodReturnType(const Method* meth)
    961 {
    962     RegType type;
    963     const char* descriptor = dexProtoGetReturnType(&meth->prototype);
    964 
    965     switch (*descriptor) {
    966     case 'I':
    967         type = kRegTypeInteger;
    968         break;
    969     case 'C':
    970         type = kRegTypeChar;
    971         break;
    972     case 'S':
    973         type = kRegTypeShort;
    974         break;
    975     case 'B':
    976         type = kRegTypeByte;
    977         break;
    978     case 'Z':
    979         type = kRegTypeBoolean;
    980         break;
    981     case 'V':
    982         type = kRegTypeUnknown;
    983         break;
    984     case 'F':
    985         type = kRegTypeFloat;
    986         break;
    987     case 'D':
    988         type = kRegTypeDoubleLo;
    989         break;
    990     case 'J':
    991         type = kRegTypeLongLo;
    992         break;
    993     case 'L':
    994     case '[':
    995         {
    996             VerifyError failure = VERIFY_ERROR_NONE;
    997             ClassObject* clazz =
    998                 lookupClassByDescriptor(meth, descriptor, &failure);
    999             assert(VERIFY_OK(failure));
   1000             type = regTypeFromClass(clazz);
   1001         }
   1002         break;
   1003     default:
   1004         /* we verified signature return type earlier, so this is impossible */
   1005         assert(false);
   1006         type = kRegTypeConflict;
   1007         break;
   1008     }
   1009 
   1010     return type;
   1011 }
   1012 
   1013 /*
   1014  * Convert a single-character signature value (i.e. a primitive type) to
   1015  * the corresponding RegType.  This is intended for access to object fields
   1016  * holding primitive types.
   1017  *
   1018  * Returns kRegTypeUnknown for objects, arrays, and void.
   1019  */
   1020 static RegType primSigCharToRegType(char sigChar)
   1021 {
   1022     RegType type;
   1023 
   1024     switch (sigChar) {
   1025     case 'I':
   1026         type = kRegTypeInteger;
   1027         break;
   1028     case 'C':
   1029         type = kRegTypeChar;
   1030         break;
   1031     case 'S':
   1032         type = kRegTypeShort;
   1033         break;
   1034     case 'B':
   1035         type = kRegTypeByte;
   1036         break;
   1037     case 'Z':
   1038         type = kRegTypeBoolean;
   1039         break;
   1040     case 'F':
   1041         type = kRegTypeFloat;
   1042         break;
   1043     case 'D':
   1044         type = kRegTypeDoubleLo;
   1045         break;
   1046     case 'J':
   1047         type = kRegTypeLongLo;
   1048         break;
   1049     case 'V':
   1050     case 'L':
   1051     case '[':
   1052         type = kRegTypeUnknown;
   1053         break;
   1054     default:
   1055         assert(false);
   1056         type = kRegTypeUnknown;
   1057         break;
   1058     }
   1059 
   1060     return type;
   1061 }
   1062 
   1063 /*
   1064  * See if the method matches the MethodType.
   1065  */
   1066 static bool isCorrectInvokeKind(MethodType methodType, Method* resMethod)
   1067 {
   1068     switch (methodType) {
   1069     case METHOD_DIRECT:
   1070         return dvmIsDirectMethod(resMethod);
   1071     case METHOD_STATIC:
   1072         return dvmIsStaticMethod(resMethod);
   1073     case METHOD_VIRTUAL:
   1074     case METHOD_INTERFACE:
   1075         return !dvmIsDirectMethod(resMethod);
   1076     default:
   1077         return false;
   1078     }
   1079 }
   1080 
   1081 /*
   1082  * Verify the arguments to a method.  We're executing in "method", making
   1083  * a call to the method reference in vB.
   1084  *
   1085  * If this is a "direct" invoke, we allow calls to <init>.  For calls to
   1086  * <init>, the first argument may be an uninitialized reference.  Otherwise,
   1087  * calls to anything starting with '<' will be rejected, as will any
   1088  * uninitialized reference arguments.
   1089  *
   1090  * For non-static method calls, this will verify that the method call is
   1091  * appropriate for the "this" argument.
   1092  *
   1093  * The method reference is in vBBBB.  The "isRange" parameter determines
   1094  * whether we use 0-4 "args" values or a range of registers defined by
   1095  * vAA and vCCCC.
   1096  *
   1097  * Widening conversions on integers and references are allowed, but
   1098  * narrowing conversions are not.
   1099  *
   1100  * Returns the resolved method on success, NULL on failure (with *pFailure
   1101  * set appropriately).
   1102  */
   1103 static Method* verifyInvocationArgs(const Method* meth,
   1104     RegisterLine* registerLine, const int insnRegCount,
   1105     const DecodedInstruction* pDecInsn, UninitInstanceMap* uninitMap,
   1106     MethodType methodType, bool isRange, bool isSuper, VerifyError* pFailure)
   1107 {
   1108     Method* resMethod;
   1109     char* sigOriginal = NULL;
   1110     const char* sig;
   1111     int expectedArgs;
   1112     int actualArgs;
   1113 
   1114     /*
   1115      * Resolve the method.  This could be an abstract or concrete method
   1116      * depending on what sort of call we're making.
   1117      */
   1118     if (methodType == METHOD_INTERFACE) {
   1119         resMethod = dvmOptResolveInterfaceMethod(meth->clazz, pDecInsn->vB);
   1120     } else {
   1121         resMethod = dvmOptResolveMethod(meth->clazz, pDecInsn->vB, methodType,
   1122             pFailure);
   1123     }
   1124     if (resMethod == NULL) {
   1125         /* failed; print a meaningful failure message */
   1126         DexFile* pDexFile = meth->clazz->pDvmDex->pDexFile;
   1127 
   1128         const DexMethodId* pMethodId = dexGetMethodId(pDexFile, pDecInsn->vB);
   1129         const char* methodName = dexStringById(pDexFile, pMethodId->nameIdx);
   1130         char* methodDesc = dexCopyDescriptorFromMethodId(pDexFile, pMethodId);
   1131         const char* classDescriptor = dexStringByTypeIdx(pDexFile, pMethodId->classIdx);
   1132 
   1133         if (!gDvm.optimizing) {
   1134             std::string dotMissingClass =
   1135                 dvmHumanReadableDescriptor(classDescriptor);
   1136             std::string dotMethClass =
   1137                 dvmHumanReadableDescriptor(meth->clazz->descriptor);
   1138 
   1139             ALOGI("Could not find method %s.%s, referenced from method %s.%s",
   1140                     dotMissingClass.c_str(), methodName,
   1141                     dotMethClass.c_str(), meth->name);
   1142         }
   1143 
   1144         LOG_VFY("VFY: unable to resolve %s method %u: %s.%s %s",
   1145             dvmMethodTypeStr(methodType), pDecInsn->vB,
   1146             classDescriptor, methodName, methodDesc);
   1147         free(methodDesc);
   1148         if (VERIFY_OK(*pFailure))       /* not set for interface resolve */
   1149             *pFailure = VERIFY_ERROR_NO_METHOD;
   1150         goto fail;
   1151     }
   1152 
   1153     /*
   1154      * Only time you can explicitly call a method starting with '<' is when
   1155      * making a "direct" invocation on "<init>".  There are additional
   1156      * restrictions but we don't enforce them here.
   1157      */
   1158     if (resMethod->name[0] == '<') {
   1159         if (methodType != METHOD_DIRECT || !isInitMethod(resMethod)) {
   1160             LOG_VFY("VFY: invalid call to %s.%s",
   1161                     resMethod->clazz->descriptor, resMethod->name);
   1162             goto bad_sig;
   1163         }
   1164     }
   1165 
   1166     /*
   1167      * See if the method type implied by the invoke instruction matches the
   1168      * access flags for the target method.
   1169      */
   1170     if (!isCorrectInvokeKind(methodType, resMethod)) {
   1171         LOG_VFY("VFY: invoke type does not match method type of %s.%s",
   1172             resMethod->clazz->descriptor, resMethod->name);
   1173         goto fail;
   1174     }
   1175 
   1176     /*
   1177      * If we're using invoke-super(method), make sure that the executing
   1178      * method's class' superclass has a vtable entry for the target method.
   1179      */
   1180     if (isSuper) {
   1181         assert(methodType == METHOD_VIRTUAL);
   1182         ClassObject* super = meth->clazz->super;
   1183         if (super == NULL || resMethod->methodIndex > super->vtableCount) {
   1184             char* desc = dexProtoCopyMethodDescriptor(&resMethod->prototype);
   1185             LOG_VFY("VFY: invalid invoke-super from %s.%s to super %s.%s %s",
   1186                     meth->clazz->descriptor, meth->name,
   1187                     (super == NULL) ? "-" : super->descriptor,
   1188                     resMethod->name, desc);
   1189             free(desc);
   1190             *pFailure = VERIFY_ERROR_NO_METHOD;
   1191             goto fail;
   1192         }
   1193     }
   1194 
   1195     /*
   1196      * We use vAA as our expected arg count, rather than resMethod->insSize,
   1197      * because we need to match the call to the signature.  Also, we might
   1198      * might be calling through an abstract method definition (which doesn't
   1199      * have register count values).
   1200      */
   1201     sigOriginal = dexProtoCopyMethodDescriptor(&resMethod->prototype);
   1202     sig = sigOriginal;
   1203     expectedArgs = pDecInsn->vA;
   1204     actualArgs = 0;
   1205 
   1206     /* caught by static verifier */
   1207     assert(isRange || expectedArgs <= 5);
   1208 
   1209     if (expectedArgs > meth->outsSize) {
   1210         LOG_VFY("VFY: invalid arg count (%d) exceeds outsSize (%d)",
   1211             expectedArgs, meth->outsSize);
   1212         goto fail;
   1213     }
   1214 
   1215     if (*sig++ != '(')
   1216         goto bad_sig;
   1217 
   1218     /*
   1219      * Check the "this" argument, which must be an instance of the class
   1220      * that declared the method.  For an interface class, we don't do the
   1221      * full interface merge, so we can't do a rigorous check here (which
   1222      * is okay since we have to do it at runtime).
   1223      */
   1224     if (!dvmIsStaticMethod(resMethod)) {
   1225         ClassObject* actualThisRef;
   1226         RegType actualArgType;
   1227 
   1228         actualArgType = getInvocationThis(registerLine, pDecInsn, pFailure);
   1229         if (!VERIFY_OK(*pFailure))
   1230             goto fail;
   1231 
   1232         if (regTypeIsUninitReference(actualArgType) && resMethod->name[0] != '<')
   1233         {
   1234             LOG_VFY("VFY: 'this' arg must be initialized");
   1235             goto fail;
   1236         }
   1237         if (methodType != METHOD_INTERFACE && actualArgType != kRegTypeZero) {
   1238             actualThisRef = regTypeReferenceToClass(actualArgType, uninitMap);
   1239             if (!dvmInstanceof(actualThisRef, resMethod->clazz)) {
   1240                 LOG_VFY("VFY: 'this' arg '%s' not instance of '%s'",
   1241                         actualThisRef->descriptor,
   1242                         resMethod->clazz->descriptor);
   1243                 goto fail;
   1244             }
   1245         }
   1246         actualArgs++;
   1247     }
   1248 
   1249     /*
   1250      * Process the target method's signature.  This signature may or may not
   1251      * have been verified, so we can't assume it's properly formed.
   1252      */
   1253     while (*sig != '\0' && *sig != ')') {
   1254         if (actualArgs >= expectedArgs) {
   1255             LOG_VFY("VFY: expected %d args, found more (%c)",
   1256                 expectedArgs, *sig);
   1257             goto bad_sig;
   1258         }
   1259 
   1260         u4 getReg;
   1261         if (isRange)
   1262             getReg = pDecInsn->vC + actualArgs;
   1263         else
   1264             getReg = pDecInsn->arg[actualArgs];
   1265 
   1266         switch (*sig) {
   1267         case 'L':
   1268             {
   1269                 ClassObject* clazz = lookupSignatureClass(meth, &sig, pFailure);
   1270                 if (!VERIFY_OK(*pFailure))
   1271                     goto bad_sig;
   1272                 verifyRegisterType(registerLine, getReg,
   1273                     regTypeFromClass(clazz), pFailure);
   1274                 if (!VERIFY_OK(*pFailure)) {
   1275                     LOG_VFY("VFY: bad arg %d (into %s)",
   1276                             actualArgs, clazz->descriptor);
   1277                     goto bad_sig;
   1278                 }
   1279             }
   1280             actualArgs++;
   1281             break;
   1282         case '[':
   1283             {
   1284                 ClassObject* clazz =
   1285                     lookupSignatureArrayClass(meth, &sig, pFailure);
   1286                 if (!VERIFY_OK(*pFailure))
   1287                     goto bad_sig;
   1288                 verifyRegisterType(registerLine, getReg,
   1289                     regTypeFromClass(clazz), pFailure);
   1290                 if (!VERIFY_OK(*pFailure)) {
   1291                     LOG_VFY("VFY: bad arg %d (into %s)",
   1292                             actualArgs, clazz->descriptor);
   1293                     goto bad_sig;
   1294                 }
   1295             }
   1296             actualArgs++;
   1297             break;
   1298         case 'Z':
   1299             verifyRegisterType(registerLine, getReg, kRegTypeBoolean, pFailure);
   1300             actualArgs++;
   1301             break;
   1302         case 'C':
   1303             verifyRegisterType(registerLine, getReg, kRegTypeChar, pFailure);
   1304             actualArgs++;
   1305             break;
   1306         case 'B':
   1307             verifyRegisterType(registerLine, getReg, kRegTypeByte, pFailure);
   1308             actualArgs++;
   1309             break;
   1310         case 'I':
   1311             verifyRegisterType(registerLine, getReg, kRegTypeInteger, pFailure);
   1312             actualArgs++;
   1313             break;
   1314         case 'S':
   1315             verifyRegisterType(registerLine, getReg, kRegTypeShort, pFailure);
   1316             actualArgs++;
   1317             break;
   1318         case 'F':
   1319             verifyRegisterType(registerLine, getReg, kRegTypeFloat, pFailure);
   1320             actualArgs++;
   1321             break;
   1322         case 'D':
   1323             verifyRegisterType(registerLine, getReg, kRegTypeDoubleLo, pFailure);
   1324             actualArgs += 2;
   1325             break;
   1326         case 'J':
   1327             verifyRegisterType(registerLine, getReg, kRegTypeLongLo, pFailure);
   1328             actualArgs += 2;
   1329             break;
   1330         default:
   1331             LOG_VFY("VFY: invocation target: bad signature type char '%c'",
   1332                 *sig);
   1333             goto bad_sig;
   1334         }
   1335 
   1336         sig++;
   1337     }
   1338     if (*sig != ')') {
   1339         char* desc = dexProtoCopyMethodDescriptor(&resMethod->prototype);
   1340         LOG_VFY("VFY: invocation target: bad signature '%s'", desc);
   1341         free(desc);
   1342         goto bad_sig;
   1343     }
   1344 
   1345     if (actualArgs != expectedArgs) {
   1346         LOG_VFY("VFY: expected %d args, found %d", expectedArgs, actualArgs);
   1347         goto bad_sig;
   1348     }
   1349 
   1350     free(sigOriginal);
   1351     return resMethod;
   1352 
   1353 bad_sig:
   1354     if (resMethod != NULL) {
   1355         char* desc = dexProtoCopyMethodDescriptor(&resMethod->prototype);
   1356         LOG_VFY("VFY:  rejecting call to %s.%s %s",
   1357             resMethod->clazz->descriptor, resMethod->name, desc);
   1358         free(desc);
   1359     }
   1360 
   1361 fail:
   1362     free(sigOriginal);
   1363     if (*pFailure == VERIFY_ERROR_NONE)
   1364         *pFailure = VERIFY_ERROR_GENERIC;
   1365     return NULL;
   1366 }
   1367 
   1368 /*
   1369  * Get the class object for the type of data stored in a field.  This isn't
   1370  * stored in the Field struct, so we have to recover it from the signature.
   1371  *
   1372  * This only works for reference types.  Don't call this for primitive types.
   1373  *
   1374  * If we can't find the class, we return java.lang.Object, so that
   1375  * verification can continue if a field is only accessed in trivial ways.
   1376  */
   1377 static ClassObject* getFieldClass(const Method* meth, const Field* field)
   1378 {
   1379     ClassObject* fieldClass;
   1380     const char* signature = field->signature;
   1381 
   1382     if ((*signature == 'L') || (*signature == '[')) {
   1383         fieldClass = dvmFindClassNoInit(signature,
   1384                 meth->clazz->classLoader);
   1385     } else {
   1386         return NULL;
   1387     }
   1388 
   1389     if (fieldClass == NULL) {
   1390         dvmClearOptException(dvmThreadSelf());
   1391         ALOGV("VFY: unable to find class '%s' for field %s.%s, trying Object",
   1392             field->signature, meth->clazz->descriptor, field->name);
   1393         fieldClass = gDvm.classJavaLangObject;
   1394     } else {
   1395         assert(!dvmIsPrimitiveClass(fieldClass));
   1396     }
   1397     return fieldClass;
   1398 }
   1399 
   1400 
   1401 /*
   1402  * ===========================================================================
   1403  *      Register operations
   1404  * ===========================================================================
   1405  */
   1406 
   1407 /*
   1408  * Get the type of register N.
   1409  *
   1410  * The register index was validated during the static pass, so we don't
   1411  * need to check it here.
   1412  */
   1413 static inline RegType getRegisterType(const RegisterLine* registerLine, u4 vsrc)
   1414 {
   1415     return registerLine->regTypes[vsrc];
   1416 }
   1417 
   1418 /*
   1419  * Get the value from a register, and cast it to a ClassObject.  Sets
   1420  * "*pFailure" if something fails.
   1421  *
   1422  * This fails if the register holds an uninitialized class.
   1423  *
   1424  * If the register holds kRegTypeZero, this returns a NULL pointer.
   1425  */
   1426 static ClassObject* getClassFromRegister(const RegisterLine* registerLine,
   1427     u4 vsrc, VerifyError* pFailure)
   1428 {
   1429     ClassObject* clazz = NULL;
   1430     RegType type;
   1431 
   1432     /* get the element type of the array held in vsrc */
   1433     type = getRegisterType(registerLine, vsrc);
   1434 
   1435     /* if "always zero", we allow it to fail at runtime */
   1436     if (type == kRegTypeZero)
   1437         goto bail;
   1438 
   1439     if (!regTypeIsReference(type)) {
   1440         LOG_VFY("VFY: tried to get class from non-ref register v%d (type=%d)",
   1441             vsrc, type);
   1442         *pFailure = VERIFY_ERROR_GENERIC;
   1443         goto bail;
   1444     }
   1445     if (regTypeIsUninitReference(type)) {
   1446         LOG_VFY("VFY: register %u holds uninitialized reference", vsrc);
   1447         *pFailure = VERIFY_ERROR_GENERIC;
   1448         goto bail;
   1449     }
   1450 
   1451     clazz = regTypeInitializedReferenceToClass(type);
   1452 
   1453 bail:
   1454     return clazz;
   1455 }
   1456 
   1457 /*
   1458  * Get the "this" pointer from a non-static method invocation.  This
   1459  * returns the RegType so the caller can decide whether it needs the
   1460  * reference to be initialized or not.  (Can also return kRegTypeZero
   1461  * if the reference can only be zero at this point.)
   1462  *
   1463  * The argument count is in vA, and the first argument is in vC, for both
   1464  * "simple" and "range" versions.  We just need to make sure vA is >= 1
   1465  * and then return vC.
   1466  */
   1467 static RegType getInvocationThis(const RegisterLine* registerLine,
   1468     const DecodedInstruction* pDecInsn, VerifyError* pFailure)
   1469 {
   1470     RegType thisType = kRegTypeUnknown;
   1471 
   1472     if (pDecInsn->vA < 1) {
   1473         LOG_VFY("VFY: invoke lacks 'this'");
   1474         *pFailure = VERIFY_ERROR_GENERIC;
   1475         goto bail;
   1476     }
   1477 
   1478     /* get the element type of the array held in vsrc */
   1479     thisType = getRegisterType(registerLine, pDecInsn->vC);
   1480     if (!regTypeIsReference(thisType)) {
   1481         LOG_VFY("VFY: tried to get class from non-ref register v%d (type=%d)",
   1482             pDecInsn->vC, thisType);
   1483         *pFailure = VERIFY_ERROR_GENERIC;
   1484         goto bail;
   1485     }
   1486 
   1487 bail:
   1488     return thisType;
   1489 }
   1490 
   1491 /*
   1492  * Set the type of register N, verifying that the register is valid.  If
   1493  * "newType" is the "Lo" part of a 64-bit value, register N+1 will be
   1494  * set to "newType+1".
   1495  *
   1496  * The register index was validated during the static pass, so we don't
   1497  * need to check it here.
   1498  *
   1499  * TODO: clear mon stack bits
   1500  */
   1501 static void setRegisterType(RegisterLine* registerLine, u4 vdst,
   1502     RegType newType)
   1503 {
   1504     RegType* insnRegs = registerLine->regTypes;
   1505 
   1506     switch (newType) {
   1507     case kRegTypeUnknown:
   1508     case kRegTypeBoolean:
   1509     case kRegTypeOne:
   1510     case kRegTypeConstByte:
   1511     case kRegTypeConstPosByte:
   1512     case kRegTypeConstShort:
   1513     case kRegTypeConstPosShort:
   1514     case kRegTypeConstChar:
   1515     case kRegTypeConstInteger:
   1516     case kRegTypeByte:
   1517     case kRegTypePosByte:
   1518     case kRegTypeShort:
   1519     case kRegTypePosShort:
   1520     case kRegTypeChar:
   1521     case kRegTypeInteger:
   1522     case kRegTypeFloat:
   1523     case kRegTypeZero:
   1524     case kRegTypeUninit:
   1525         insnRegs[vdst] = newType;
   1526         break;
   1527     case kRegTypeConstLo:
   1528     case kRegTypeLongLo:
   1529     case kRegTypeDoubleLo:
   1530         insnRegs[vdst] = newType;
   1531         insnRegs[vdst+1] = newType+1;
   1532         break;
   1533     case kRegTypeConstHi:
   1534     case kRegTypeLongHi:
   1535     case kRegTypeDoubleHi:
   1536         /* should never set these explicitly */
   1537         ALOGE("BUG: explicit set of high register type");
   1538         dvmAbort();
   1539         break;
   1540 
   1541     default:
   1542         /* can't switch for ref types, so we check explicitly */
   1543         if (regTypeIsReference(newType)) {
   1544             insnRegs[vdst] = newType;
   1545 
   1546             /*
   1547              * In most circumstances we won't see a reference to a primitive
   1548              * class here (e.g. "D"), since that would mean the object in the
   1549              * register is actually a primitive type.  It can happen as the
   1550              * result of an assumed-successful check-cast instruction in
   1551              * which the second argument refers to a primitive class.  (In
   1552              * practice, such an instruction will always throw an exception.)
   1553              *
   1554              * This is not an issue for instructions like const-class, where
   1555              * the object in the register is a java.lang.Class instance.
   1556              */
   1557             break;
   1558         }
   1559         /* bad type - fall through */
   1560 
   1561     case kRegTypeConflict:      // should only be set during a merge
   1562         ALOGE("BUG: set register to unknown type %d", newType);
   1563         dvmAbort();
   1564         break;
   1565     }
   1566 
   1567     /*
   1568      * Clear the monitor entry bits for this register.
   1569      */
   1570     if (registerLine->monitorEntries != NULL)
   1571         registerLine->monitorEntries[vdst] = 0;
   1572 }
   1573 
   1574 /*
   1575  * Verify that the contents of the specified register have the specified
   1576  * type (or can be converted to it through an implicit widening conversion).
   1577  *
   1578  * This will modify the type of the source register if it was originally
   1579  * derived from a constant to prevent mixing of int/float and long/double.
   1580  *
   1581  * If "vsrc" is a reference, both it and the "vsrc" register must be
   1582  * initialized ("vsrc" may be Zero).  This will verify that the value in
   1583  * the register is an instance of checkType, or if checkType is an
   1584  * interface, verify that the register implements checkType.
   1585  */
   1586 static void verifyRegisterType(RegisterLine* registerLine, u4 vsrc,
   1587     RegType checkType, VerifyError* pFailure)
   1588 {
   1589     const RegType* insnRegs = registerLine->regTypes;
   1590     RegType srcType = insnRegs[vsrc];
   1591 
   1592     //ALOGD("check-reg v%u = %d", vsrc, checkType);
   1593     switch (checkType) {
   1594     case kRegTypeFloat:
   1595     case kRegTypeBoolean:
   1596     case kRegTypePosByte:
   1597     case kRegTypeByte:
   1598     case kRegTypePosShort:
   1599     case kRegTypeShort:
   1600     case kRegTypeChar:
   1601     case kRegTypeInteger:
   1602         if (!canConvertTo1nr(srcType, checkType)) {
   1603             LOG_VFY("VFY: register1 v%u type %d, wanted %d",
   1604                 vsrc, srcType, checkType);
   1605             *pFailure = VERIFY_ERROR_GENERIC;
   1606             break;
   1607         }
   1608         /* Update type if result is float */
   1609         if (checkType == kRegTypeFloat) {
   1610             setRegisterType(registerLine, vsrc, checkType);
   1611         } else {
   1612             /* Update const type to actual type after use */
   1613             setRegisterType(registerLine, vsrc, constTypeToRegType(srcType));
   1614         }
   1615         break;
   1616     case kRegTypeLongLo:
   1617     case kRegTypeDoubleLo:
   1618         if (insnRegs[vsrc+1] != srcType+1) {
   1619             LOG_VFY("VFY: register2 v%u-%u values %d,%d",
   1620                 vsrc, vsrc+1, insnRegs[vsrc], insnRegs[vsrc+1]);
   1621             *pFailure = VERIFY_ERROR_GENERIC;
   1622             break;
   1623         } else if (!canConvertTo2(srcType, checkType)) {
   1624             LOG_VFY("VFY: register2 v%u type %d, wanted %d",
   1625                 vsrc, srcType, checkType);
   1626             *pFailure = VERIFY_ERROR_GENERIC;
   1627             break;
   1628         }
   1629         /* Update type if source is from const */
   1630         if (srcType == kRegTypeConstLo) {
   1631             setRegisterType(registerLine, vsrc, checkType);
   1632         }
   1633         break;
   1634     case kRegTypeConstLo:
   1635     case kRegTypeConstHi:
   1636     case kRegTypeLongHi:
   1637     case kRegTypeDoubleHi:
   1638     case kRegTypeZero:
   1639     case kRegTypeOne:
   1640     case kRegTypeUnknown:
   1641     case kRegTypeConflict:
   1642         /* should never be checking for these explicitly */
   1643         assert(false);
   1644         *pFailure = VERIFY_ERROR_GENERIC;
   1645         return;
   1646     case kRegTypeUninit:
   1647     default:
   1648         /* make sure checkType is initialized reference */
   1649         if (!regTypeIsReference(checkType)) {
   1650             LOG_VFY("VFY: unexpected check type %d", checkType);
   1651             assert(false);
   1652             *pFailure = VERIFY_ERROR_GENERIC;
   1653             break;
   1654         }
   1655         if (regTypeIsUninitReference(checkType)) {
   1656             LOG_VFY("VFY: uninitialized ref not expected as reg check");
   1657             *pFailure = VERIFY_ERROR_GENERIC;
   1658             break;
   1659         }
   1660         /* make sure srcType is initialized reference or always-NULL */
   1661         if (!regTypeIsReference(srcType)) {
   1662             LOG_VFY("VFY: register1 v%u type %d, wanted ref", vsrc, srcType);
   1663             *pFailure = VERIFY_ERROR_GENERIC;
   1664             break;
   1665         }
   1666         if (regTypeIsUninitReference(srcType)) {
   1667             LOG_VFY("VFY: register1 v%u holds uninitialized ref", vsrc);
   1668             *pFailure = VERIFY_ERROR_GENERIC;
   1669             break;
   1670         }
   1671         /* if the register isn't Zero, make sure it's an instance of check */
   1672         if (srcType != kRegTypeZero) {
   1673             ClassObject* srcClass = regTypeInitializedReferenceToClass(srcType);
   1674             ClassObject* checkClass = regTypeInitializedReferenceToClass(checkType);
   1675             assert(srcClass != NULL);
   1676             assert(checkClass != NULL);
   1677 
   1678             if (dvmIsInterfaceClass(checkClass)) {
   1679                 /*
   1680                  * All objects implement all interfaces as far as the
   1681                  * verifier is concerned.  The runtime has to sort it out.
   1682                  * See comments above findCommonSuperclass.
   1683                  */
   1684                 /*
   1685                 if (srcClass != checkClass &&
   1686                     !dvmImplements(srcClass, checkClass))
   1687                 {
   1688                     LOG_VFY("VFY: %s does not implement %s",
   1689                             srcClass->descriptor, checkClass->descriptor);
   1690                     *pFailure = VERIFY_ERROR_GENERIC;
   1691                 }
   1692                 */
   1693             } else {
   1694                 if (!dvmInstanceof(srcClass, checkClass)) {
   1695                     LOG_VFY("VFY: %s is not instance of %s",
   1696                             srcClass->descriptor, checkClass->descriptor);
   1697                     *pFailure = VERIFY_ERROR_GENERIC;
   1698                 }
   1699             }
   1700         }
   1701         break;
   1702     }
   1703 }
   1704 
   1705 /*
   1706  * Set the type of the "result" register.
   1707  */
   1708 static void setResultRegisterType(RegisterLine* registerLine,
   1709     const int insnRegCount, RegType newType)
   1710 {
   1711     setRegisterType(registerLine, RESULT_REGISTER(insnRegCount), newType);
   1712 }
   1713 
   1714 
   1715 /*
   1716  * Update all registers holding "uninitType" to instead hold the
   1717  * corresponding initialized reference type.  This is called when an
   1718  * appropriate <init> method is invoked -- all copies of the reference
   1719  * must be marked as initialized.
   1720  */
   1721 static void markRefsAsInitialized(RegisterLine* registerLine, int insnRegCount,
   1722     UninitInstanceMap* uninitMap, RegType uninitType, VerifyError* pFailure)
   1723 {
   1724     RegType* insnRegs = registerLine->regTypes;
   1725     ClassObject* clazz;
   1726     RegType initType;
   1727     int i, changed;
   1728 
   1729     clazz = getUninitInstance(uninitMap, regTypeToUninitIndex(uninitType));
   1730     if (clazz == NULL) {
   1731         ALOGE("VFY: unable to find type=%#x (idx=%d)",
   1732             uninitType, regTypeToUninitIndex(uninitType));
   1733         *pFailure = VERIFY_ERROR_GENERIC;
   1734         return;
   1735     }
   1736     initType = regTypeFromClass(clazz);
   1737 
   1738     changed = 0;
   1739     for (i = 0; i < insnRegCount; i++) {
   1740         if (insnRegs[i] == uninitType) {
   1741             insnRegs[i] = initType;
   1742             changed++;
   1743         }
   1744     }
   1745     //ALOGD("VFY: marked %d registers as initialized", changed);
   1746     assert(changed > 0);
   1747 
   1748     return;
   1749 }
   1750 
   1751 /*
   1752  * We're creating a new instance of class C at address A.  Any registers
   1753  * holding instances previously created at address A must be initialized
   1754  * by now.  If not, we mark them as "conflict" to prevent them from being
   1755  * used (otherwise, markRefsAsInitialized would mark the old ones and the
   1756  * new ones at the same time).
   1757  */
   1758 static void markUninitRefsAsInvalid(RegisterLine* registerLine,
   1759     int insnRegCount, UninitInstanceMap* uninitMap, RegType uninitType)
   1760 {
   1761     RegType* insnRegs = registerLine->regTypes;
   1762     int i, changed;
   1763 
   1764     changed = 0;
   1765     for (i = 0; i < insnRegCount; i++) {
   1766         if (insnRegs[i] == uninitType) {
   1767             insnRegs[i] = kRegTypeConflict;
   1768             if (registerLine->monitorEntries != NULL)
   1769                 registerLine->monitorEntries[i] = 0;
   1770             changed++;
   1771         }
   1772     }
   1773 
   1774     //if (changed)
   1775     //    ALOGD("VFY: marked %d uninitialized registers as invalid", changed);
   1776 }
   1777 
   1778 /*
   1779  * Find the register line for the specified instruction in the current method.
   1780  */
   1781 static inline RegisterLine* getRegisterLine(const RegisterTable* regTable,
   1782     int insnIdx)
   1783 {
   1784     return &regTable->registerLines[insnIdx];
   1785 }
   1786 
   1787 /*
   1788  * Copy a register line.
   1789  */
   1790 static inline void copyRegisterLine(RegisterLine* dst, const RegisterLine* src,
   1791     size_t numRegs)
   1792 {
   1793     memcpy(dst->regTypes, src->regTypes, numRegs * sizeof(RegType));
   1794 
   1795     assert((src->monitorEntries == NULL && dst->monitorEntries == NULL) ||
   1796            (src->monitorEntries != NULL && dst->monitorEntries != NULL));
   1797     if (dst->monitorEntries != NULL) {
   1798         assert(dst->monitorStack != NULL);
   1799         memcpy(dst->monitorEntries, src->monitorEntries,
   1800             numRegs * sizeof(MonitorEntries));
   1801         memcpy(dst->monitorStack, src->monitorStack,
   1802             kMaxMonitorStackDepth * sizeof(u4));
   1803         dst->monitorStackTop = src->monitorStackTop;
   1804     }
   1805 }
   1806 
   1807 /*
   1808  * Copy a register line into the table.
   1809  */
   1810 static inline void copyLineToTable(RegisterTable* regTable, int insnIdx,
   1811     const RegisterLine* src)
   1812 {
   1813     RegisterLine* dst = getRegisterLine(regTable, insnIdx);
   1814     assert(dst->regTypes != NULL);
   1815     copyRegisterLine(dst, src, regTable->insnRegCountPlus);
   1816 }
   1817 
   1818 /*
   1819  * Copy a register line out of the table.
   1820  */
   1821 static inline void copyLineFromTable(RegisterLine* dst,
   1822     const RegisterTable* regTable, int insnIdx)
   1823 {
   1824     RegisterLine* src = getRegisterLine(regTable, insnIdx);
   1825     assert(src->regTypes != NULL);
   1826     copyRegisterLine(dst, src, regTable->insnRegCountPlus);
   1827 }
   1828 
   1829 
   1830 #ifndef NDEBUG
   1831 /*
   1832  * Compare two register lines.  Returns 0 if they match.
   1833  *
   1834  * Using this for a sort is unwise, since the value can change based on
   1835  * machine endianness.
   1836  */
   1837 static inline int compareLineToTable(const RegisterTable* regTable,
   1838     int insnIdx, const RegisterLine* line2)
   1839 {
   1840     const RegisterLine* line1 = getRegisterLine(regTable, insnIdx);
   1841     if (line1->monitorEntries != NULL) {
   1842         int result;
   1843 
   1844         if (line2->monitorEntries == NULL)
   1845             return 1;
   1846         result = memcmp(line1->monitorEntries, line2->monitorEntries,
   1847             regTable->insnRegCountPlus * sizeof(MonitorEntries));
   1848         if (result != 0) {
   1849             LOG_VFY("monitorEntries mismatch");
   1850             return result;
   1851         }
   1852         result = line1->monitorStackTop - line2->monitorStackTop;
   1853         if (result != 0) {
   1854             LOG_VFY("monitorStackTop mismatch");
   1855             return result;
   1856         }
   1857         result = memcmp(line1->monitorStack, line2->monitorStack,
   1858             line1->monitorStackTop);
   1859         if (result != 0) {
   1860             LOG_VFY("monitorStack mismatch");
   1861             return result;
   1862         }
   1863     }
   1864     return memcmp(line1->regTypes, line2->regTypes,
   1865             regTable->insnRegCountPlus * sizeof(RegType));
   1866 }
   1867 #endif
   1868 
   1869 /*
   1870  * Register type categories, for type checking.
   1871  *
   1872  * The spec says category 1 includes boolean, byte, char, short, int, float,
   1873  * reference, and returnAddress.  Category 2 includes long and double.
   1874  *
   1875  * We treat object references separately, so we have "category1nr".  We
   1876  * don't support jsr/ret, so there is no "returnAddress" type.
   1877  */
   1878 enum TypeCategory {
   1879     kTypeCategoryUnknown = 0,
   1880     kTypeCategory1nr,           // boolean, byte, char, short, int, float
   1881     kTypeCategory2,             // long, double
   1882     kTypeCategoryRef,           // object reference
   1883 };
   1884 
   1885 /*
   1886  * See if "type" matches "cat".  All we're really looking for here is that
   1887  * we're not mixing and matching 32-bit and 64-bit quantities, and we're
   1888  * not mixing references with numerics.  (For example, the arguments to
   1889  * "a < b" could be integers of different sizes, but they must both be
   1890  * integers.  Dalvik is less specific about int vs. float, so we treat them
   1891  * as equivalent here.)
   1892  *
   1893  * For category 2 values, "type" must be the "low" half of the value.
   1894  *
   1895  * Sets "*pFailure" if something looks wrong.
   1896  */
   1897 static void checkTypeCategory(RegType type, TypeCategory cat,
   1898     VerifyError* pFailure)
   1899 {
   1900     switch (cat) {
   1901     case kTypeCategory1nr:
   1902         switch (type) {
   1903         case kRegTypeZero:
   1904         case kRegTypeOne:
   1905         case kRegTypeBoolean:
   1906         case kRegTypeConstPosByte:
   1907         case kRegTypeConstByte:
   1908         case kRegTypeConstPosShort:
   1909         case kRegTypeConstShort:
   1910         case kRegTypeConstChar:
   1911         case kRegTypeConstInteger:
   1912         case kRegTypePosByte:
   1913         case kRegTypeByte:
   1914         case kRegTypePosShort:
   1915         case kRegTypeShort:
   1916         case kRegTypeChar:
   1917         case kRegTypeInteger:
   1918         case kRegTypeFloat:
   1919             break;
   1920         default:
   1921             *pFailure = VERIFY_ERROR_GENERIC;
   1922             break;
   1923         }
   1924         break;
   1925 
   1926     case kTypeCategory2:
   1927         switch (type) {
   1928         case kRegTypeConstLo:
   1929         case kRegTypeLongLo:
   1930         case kRegTypeDoubleLo:
   1931             break;
   1932         default:
   1933             *pFailure = VERIFY_ERROR_GENERIC;
   1934             break;
   1935         }
   1936         break;
   1937 
   1938     case kTypeCategoryRef:
   1939         if (type != kRegTypeZero && !regTypeIsReference(type))
   1940             *pFailure = VERIFY_ERROR_GENERIC;
   1941         break;
   1942 
   1943     default:
   1944         assert(false);
   1945         *pFailure = VERIFY_ERROR_GENERIC;
   1946         break;
   1947     }
   1948 }
   1949 
   1950 /*
   1951  * For a category 2 register pair, verify that "typeh" is the appropriate
   1952  * high part for "typel".
   1953  *
   1954  * Does not verify that "typel" is in fact the low part of a 64-bit
   1955  * register pair.
   1956  */
   1957 static void checkWidePair(RegType typel, RegType typeh, VerifyError* pFailure)
   1958 {
   1959     if ((typeh != typel+1))
   1960         *pFailure = VERIFY_ERROR_GENERIC;
   1961 }
   1962 
   1963 /*
   1964  * Implement category-1 "move" instructions.  Copy a 32-bit value from
   1965  * "vsrc" to "vdst".
   1966  */
   1967 static void copyRegister1(RegisterLine* registerLine, u4 vdst, u4 vsrc,
   1968     TypeCategory cat, VerifyError* pFailure)
   1969 {
   1970     assert(cat == kTypeCategory1nr || cat == kTypeCategoryRef);
   1971     RegType type = getRegisterType(registerLine, vsrc);
   1972     checkTypeCategory(type, cat, pFailure);
   1973     if (!VERIFY_OK(*pFailure)) {
   1974         LOG_VFY("VFY: copy1 v%u<-v%u type=%d cat=%d", vdst, vsrc, type, cat);
   1975     } else {
   1976         setRegisterType(registerLine, vdst, type);
   1977         if (cat == kTypeCategoryRef && registerLine->monitorEntries != NULL) {
   1978             registerLine->monitorEntries[vdst] =
   1979                 registerLine->monitorEntries[vsrc];
   1980         }
   1981     }
   1982 }
   1983 
   1984 /*
   1985  * Implement category-2 "move" instructions.  Copy a 64-bit value from
   1986  * "vsrc" to "vdst".  This copies both halves of the register.
   1987  */
   1988 static void copyRegister2(RegisterLine* registerLine, u4 vdst, u4 vsrc,
   1989     VerifyError* pFailure)
   1990 {
   1991     RegType typel = getRegisterType(registerLine, vsrc);
   1992     RegType typeh = getRegisterType(registerLine, vsrc+1);
   1993 
   1994     checkTypeCategory(typel, kTypeCategory2, pFailure);
   1995     checkWidePair(typel, typeh, pFailure);
   1996     if (!VERIFY_OK(*pFailure)) {
   1997         LOG_VFY("VFY: copy2 v%u<-v%u type=%d/%d", vdst, vsrc, typel, typeh);
   1998     } else {
   1999         setRegisterType(registerLine, vdst, typel);
   2000         /* target monitor stack bits will be cleared */
   2001     }
   2002 }
   2003 
   2004 /*
   2005  * Implement "move-result".  Copy the category-1 value from the result
   2006  * register to another register, and reset the result register.
   2007  */
   2008 static void copyResultRegister1(RegisterLine* registerLine,
   2009     const int insnRegCount, u4 vdst, TypeCategory cat, VerifyError* pFailure)
   2010 {
   2011     RegType type;
   2012     u4 vsrc;
   2013 
   2014     assert(vdst < (u4) insnRegCount);
   2015 
   2016     vsrc = RESULT_REGISTER(insnRegCount);
   2017     type = getRegisterType(registerLine, vsrc);
   2018     checkTypeCategory(type, cat, pFailure);
   2019     if (!VERIFY_OK(*pFailure)) {
   2020         LOG_VFY("VFY: copyRes1 v%u<-v%u cat=%d type=%d",
   2021             vdst, vsrc, cat, type);
   2022     } else {
   2023         setRegisterType(registerLine, vdst, type);
   2024         setRegisterType(registerLine, vsrc, kRegTypeUnknown);
   2025         /* target monitor stack bits will be cleared */
   2026     }
   2027 }
   2028 
   2029 /*
   2030  * Implement "move-result-wide".  Copy the category-2 value from the result
   2031  * register to another register, and reset the result register.
   2032  */
   2033 static void copyResultRegister2(RegisterLine* registerLine,
   2034     const int insnRegCount, u4 vdst, VerifyError* pFailure)
   2035 {
   2036     RegType typel, typeh;
   2037     u4 vsrc;
   2038 
   2039     assert(vdst < (u4) insnRegCount);
   2040 
   2041     vsrc = RESULT_REGISTER(insnRegCount);
   2042     typel = getRegisterType(registerLine, vsrc);
   2043     typeh = getRegisterType(registerLine, vsrc+1);
   2044     checkTypeCategory(typel, kTypeCategory2, pFailure);
   2045     checkWidePair(typel, typeh, pFailure);
   2046     if (!VERIFY_OK(*pFailure)) {
   2047         LOG_VFY("VFY: copyRes2 v%u<-v%u type=%d/%d",
   2048             vdst, vsrc, typel, typeh);
   2049     } else {
   2050         setRegisterType(registerLine, vdst, typel);
   2051         setRegisterType(registerLine, vsrc, kRegTypeUnknown);
   2052         setRegisterType(registerLine, vsrc+1, kRegTypeUnknown);
   2053         /* target monitor stack bits will be cleared */
   2054     }
   2055 }
   2056 
   2057 /*
   2058  * Verify types for a simple two-register instruction (e.g. "neg-int").
   2059  * "dstType" is stored into vA, and "srcType" is verified against vB.
   2060  */
   2061 static void checkUnop(RegisterLine* registerLine, DecodedInstruction* pDecInsn,
   2062     RegType dstType, RegType srcType, VerifyError* pFailure)
   2063 {
   2064     verifyRegisterType(registerLine, pDecInsn->vB, srcType, pFailure);
   2065     setRegisterType(registerLine, pDecInsn->vA, dstType);
   2066 }
   2067 
   2068 /*
   2069  * We're performing an operation like "and-int/2addr" that can be
   2070  * performed on booleans as well as integers.  We get no indication of
   2071  * boolean-ness, but we can infer it from the types of the arguments.
   2072  *
   2073  * Assumes we've already validated reg1/reg2.
   2074  *
   2075  * TODO: consider generalizing this.  The key principle is that the
   2076  * result of a bitwise operation can only be as wide as the widest of
   2077  * the operands.  You can safely AND/OR/XOR two chars together and know
   2078  * you still have a char, so it's reasonable for the compiler or "dx"
   2079  * to skip the int-to-char instruction.  (We need to do this for boolean
   2080  * because there is no int-to-boolean operation.)
   2081  *
   2082  * Returns true if both args are Boolean, Zero, or One.
   2083  */
   2084 static bool upcastBooleanOp(RegisterLine* registerLine, u4 reg1, u4 reg2)
   2085 {
   2086     RegType type1, type2;
   2087 
   2088     type1 = getRegisterType(registerLine, reg1);
   2089     type2 = getRegisterType(registerLine, reg2);
   2090 
   2091     if ((type1 == kRegTypeBoolean || type1 == kRegTypeZero ||
   2092             type1 == kRegTypeOne) &&
   2093         (type2 == kRegTypeBoolean || type2 == kRegTypeZero ||
   2094             type2 == kRegTypeOne))
   2095     {
   2096         return true;
   2097     }
   2098     return false;
   2099 }
   2100 
   2101 /*
   2102  * Verify types for A two-register instruction with a literal constant
   2103  * (e.g. "add-int/lit8").  "dstType" is stored into vA, and "srcType" is
   2104  * verified against vB.
   2105  *
   2106  * If "checkBooleanOp" is set, we use the constant value in vC.
   2107  */
   2108 static void checkLitop(RegisterLine* registerLine, DecodedInstruction* pDecInsn,
   2109     RegType dstType, RegType srcType, bool checkBooleanOp,
   2110     VerifyError* pFailure)
   2111 {
   2112     verifyRegisterType(registerLine, pDecInsn->vB, srcType, pFailure);
   2113     if (VERIFY_OK(*pFailure) && checkBooleanOp) {
   2114         assert(dstType == kRegTypeInteger);
   2115         /* check vB with the call, then check the constant manually */
   2116         if (upcastBooleanOp(registerLine, pDecInsn->vB, pDecInsn->vB)
   2117             && (pDecInsn->vC == 0 || pDecInsn->vC == 1))
   2118         {
   2119             dstType = kRegTypeBoolean;
   2120         }
   2121     }
   2122     setRegisterType(registerLine, pDecInsn->vA, dstType);
   2123 }
   2124 
   2125 /*
   2126  * Verify types for a simple three-register instruction (e.g. "add-int").
   2127  * "dstType" is stored into vA, and "srcType1"/"srcType2" are verified
   2128  * against vB/vC.
   2129  */
   2130 static void checkBinop(RegisterLine* registerLine, DecodedInstruction* pDecInsn,
   2131     RegType dstType, RegType srcType1, RegType srcType2, bool checkBooleanOp,
   2132     VerifyError* pFailure)
   2133 {
   2134     verifyRegisterType(registerLine, pDecInsn->vB, srcType1, pFailure);
   2135     verifyRegisterType(registerLine, pDecInsn->vC, srcType2, pFailure);
   2136     if (VERIFY_OK(*pFailure) && checkBooleanOp) {
   2137         assert(dstType == kRegTypeInteger);
   2138         if (upcastBooleanOp(registerLine, pDecInsn->vB, pDecInsn->vC))
   2139             dstType = kRegTypeBoolean;
   2140     }
   2141     setRegisterType(registerLine, pDecInsn->vA, dstType);
   2142 }
   2143 
   2144 /*
   2145  * Verify types for a binary "2addr" operation.  "srcType1"/"srcType2"
   2146  * are verified against vA/vB, then "dstType" is stored into vA.
   2147  */
   2148 static void checkBinop2addr(RegisterLine* registerLine,
   2149     DecodedInstruction* pDecInsn, RegType dstType, RegType srcType1,
   2150     RegType srcType2, bool checkBooleanOp, VerifyError* pFailure)
   2151 {
   2152     verifyRegisterType(registerLine, pDecInsn->vA, srcType1, pFailure);
   2153     verifyRegisterType(registerLine, pDecInsn->vB, srcType2, pFailure);
   2154     if (VERIFY_OK(*pFailure) && checkBooleanOp) {
   2155         assert(dstType == kRegTypeInteger);
   2156         if (upcastBooleanOp(registerLine, pDecInsn->vA, pDecInsn->vB))
   2157             dstType = kRegTypeBoolean;
   2158     }
   2159     setRegisterType(registerLine, pDecInsn->vA, dstType);
   2160 }
   2161 
   2162 /*
   2163  * Treat right-shifting as a narrowing conversion when possible.
   2164  *
   2165  * For example, right-shifting an int 24 times results in a value that can
   2166  * be treated as a byte.
   2167  *
   2168  * Things get interesting when contemplating sign extension.  Right-
   2169  * shifting an integer by 16 yields a value that can be represented in a
   2170  * "short" but not a "char", but an unsigned right shift by 16 yields a
   2171  * value that belongs in a char rather than a short.  (Consider what would
   2172  * happen if the result of the shift were cast to a char or short and then
   2173  * cast back to an int.  If sign extension, or the lack thereof, causes
   2174  * a change in the 32-bit representation, then the conversion was lossy.)
   2175  *
   2176  * A signed right shift by 17 on an integer results in a short.  An unsigned
   2177  * right shfit by 17 on an integer results in a posshort, which can be
   2178  * assigned to a short or a char.
   2179  *
   2180  * An unsigned right shift on a short can actually expand the result into
   2181  * a 32-bit integer.  For example, 0xfffff123 >>> 8 becomes 0x00fffff1,
   2182  * which can't be represented in anything smaller than an int.
   2183  *
   2184  * javac does not generate code that takes advantage of this, but some
   2185  * of the code optimizers do.  It's generally a peephole optimization
   2186  * that replaces a particular sequence, e.g. (bipush 24, ishr, i2b) is
   2187  * replaced by (bipush 24, ishr).  Knowing that shifting a short 8 times
   2188  * to the right yields a byte is really more than we need to handle the
   2189  * code that's out there, but support is not much more complex than just
   2190  * handling integer.
   2191  *
   2192  * Right-shifting never yields a boolean value.
   2193  *
   2194  * Returns the new register type.
   2195  */
   2196 static RegType adjustForRightShift(RegisterLine* registerLine, int reg,
   2197     unsigned int shiftCount, bool isUnsignedShift, VerifyError* pFailure)
   2198 {
   2199     RegType srcType = getRegisterType(registerLine, reg);
   2200     RegType newType;
   2201 
   2202     /* convert const derived types to their actual types */
   2203     srcType = constTypeToRegType(srcType);
   2204 
   2205     /* no-op */
   2206     if (shiftCount == 0)
   2207         return srcType;
   2208 
   2209     /* safe defaults */
   2210     if (isUnsignedShift)
   2211         newType = kRegTypeInteger;
   2212     else
   2213         newType = srcType;
   2214 
   2215     if (shiftCount >= 32) {
   2216         LOG_VFY("Got unexpectedly large shift count %u", shiftCount);
   2217         /* fail? */
   2218         return newType;
   2219     }
   2220 
   2221     switch (srcType) {
   2222     case kRegTypeInteger:               /* 32-bit signed value */
   2223         if (isUnsignedShift) {
   2224             if (shiftCount > 24)
   2225                 newType = kRegTypePosByte;
   2226             else if (shiftCount >= 16)
   2227                 newType = kRegTypeChar;
   2228         } else {
   2229             if (shiftCount >= 24)
   2230                 newType = kRegTypeByte;
   2231             else if (shiftCount >= 16)
   2232                 newType = kRegTypeShort;
   2233         }
   2234         break;
   2235     case kRegTypeShort:                 /* 16-bit signed value */
   2236         if (isUnsignedShift) {
   2237             /* default (kRegTypeInteger) is correct */
   2238         } else {
   2239             if (shiftCount >= 8)
   2240                 newType = kRegTypeByte;
   2241         }
   2242         break;
   2243     case kRegTypePosShort:              /* 15-bit unsigned value */
   2244         if (shiftCount >= 8)
   2245             newType = kRegTypePosByte;
   2246         break;
   2247     case kRegTypeChar:                  /* 16-bit unsigned value */
   2248         if (shiftCount > 8)
   2249             newType = kRegTypePosByte;
   2250         break;
   2251     case kRegTypeByte:                  /* 8-bit signed value */
   2252         /* defaults (u=kRegTypeInteger / s=srcType) are correct */
   2253         break;
   2254     case kRegTypePosByte:               /* 7-bit unsigned value */
   2255         /* always use newType=srcType */
   2256         newType = srcType;
   2257         break;
   2258     case kRegTypeZero:                  /* 1-bit unsigned value */
   2259     case kRegTypeOne:
   2260     case kRegTypeBoolean:
   2261         /* unnecessary? */
   2262         newType = kRegTypeZero;
   2263         break;
   2264     default:
   2265         /* long, double, references; shouldn't be here! */
   2266         assert(false);
   2267         break;
   2268     }
   2269 
   2270     if (newType != srcType) {
   2271         LOGVV("narrowing: %d(%d) --> %d to %d",
   2272             shiftCount, isUnsignedShift, srcType, newType);
   2273     } else {
   2274         LOGVV("not narrowed: %d(%d) --> %d",
   2275             shiftCount, isUnsignedShift, srcType);
   2276     }
   2277     return newType;
   2278 }
   2279 
   2280 
   2281 /*
   2282  * ===========================================================================
   2283  *      Register merge
   2284  * ===========================================================================
   2285  */
   2286 
   2287 /*
   2288  * Compute the "class depth" of a class.  This is the distance from the
   2289  * class to the top of the tree, chasing superclass links.  java.lang.Object
   2290  * has a class depth of 0.
   2291  */
   2292 static int getClassDepth(ClassObject* clazz)
   2293 {
   2294     int depth = 0;
   2295 
   2296     while (clazz->super != NULL) {
   2297         clazz = clazz->super;
   2298         depth++;
   2299     }
   2300     return depth;
   2301 }
   2302 
   2303 /*
   2304  * Given two classes, walk up the superclass tree to find a common
   2305  * ancestor.  (Called from findCommonSuperclass().)
   2306  *
   2307  * TODO: consider caching the class depth in the class object so we don't
   2308  * have to search for it here.
   2309  */
   2310 static ClassObject* digForSuperclass(ClassObject* c1, ClassObject* c2)
   2311 {
   2312     int depth1, depth2;
   2313 
   2314     depth1 = getClassDepth(c1);
   2315     depth2 = getClassDepth(c2);
   2316 
   2317     if (gDebugVerbose) {
   2318         LOGVV("COMMON: %s(%d) + %s(%d)",
   2319             c1->descriptor, depth1, c2->descriptor, depth2);
   2320     }
   2321 
   2322     /* pull the deepest one up */
   2323     if (depth1 > depth2) {
   2324         while (depth1 > depth2) {
   2325             c1 = c1->super;
   2326             depth1--;
   2327         }
   2328     } else {
   2329         while (depth2 > depth1) {
   2330             c2 = c2->super;
   2331             depth2--;
   2332         }
   2333     }
   2334 
   2335     /* walk up in lock-step */
   2336     while (c1 != c2) {
   2337         c1 = c1->super;
   2338         c2 = c2->super;
   2339 
   2340         assert(c1 != NULL && c2 != NULL);
   2341     }
   2342 
   2343     if (gDebugVerbose) {
   2344         LOGVV("      : --> %s", c1->descriptor);
   2345     }
   2346     return c1;
   2347 }
   2348 
   2349 /*
   2350  * Merge two array classes.  We can't use the general "walk up to the
   2351  * superclass" merge because the superclass of an array is always Object.
   2352  * We want String[] + Integer[] = Object[].  This works for higher dimensions
   2353  * as well, e.g. String[][] + Integer[][] = Object[][].
   2354  *
   2355  * If Foo1 and Foo2 are subclasses of Foo, Foo1[] + Foo2[] = Foo[].
   2356  *
   2357  * If Class implements Type, Class[] + Type[] = Type[].
   2358  *
   2359  * If the dimensions don't match, we want to convert to an array of Object
   2360  * with the least dimension, e.g. String[][] + String[][][][] = Object[][].
   2361  *
   2362  * Arrays of primitive types effectively have one less dimension when
   2363  * merging.  int[] + float[] = Object, int[] + String[] = Object,
   2364  * int[][] + float[][] = Object[], int[][] + String[] = Object[].  (The
   2365  * only time this function doesn't return an array class is when one of
   2366  * the arguments is a 1-dimensional primitive array.)
   2367  *
   2368  * This gets a little awkward because we may have to ask the VM to create
   2369  * a new array type with the appropriate element and dimensions.  However, we
   2370  * shouldn't be doing this often.
   2371  */
   2372 static ClassObject* findCommonArraySuperclass(ClassObject* c1, ClassObject* c2)
   2373 {
   2374     ClassObject* arrayClass = NULL;
   2375     ClassObject* commonElem;
   2376     int arrayDim1, arrayDim2;
   2377     int i, numDims;
   2378     bool hasPrimitive = false;
   2379 
   2380     arrayDim1 = c1->arrayDim;
   2381     arrayDim2 = c2->arrayDim;
   2382     assert(c1->arrayDim > 0);
   2383     assert(c2->arrayDim > 0);
   2384 
   2385     if (dvmIsPrimitiveClass(c1->elementClass)) {
   2386         arrayDim1--;
   2387         hasPrimitive = true;
   2388     }
   2389     if (dvmIsPrimitiveClass(c2->elementClass)) {
   2390         arrayDim2--;
   2391         hasPrimitive = true;
   2392     }
   2393 
   2394     if (!hasPrimitive && arrayDim1 == arrayDim2) {
   2395         /*
   2396          * Two arrays of reference types with equal dimensions.  Try to
   2397          * find a good match.
   2398          */
   2399         commonElem = findCommonSuperclass(c1->elementClass, c2->elementClass);
   2400         numDims = arrayDim1;
   2401     } else {
   2402         /*
   2403          * Mismatched array depths and/or array(s) of primitives.  We want
   2404          * Object, or an Object array with appropriate dimensions.
   2405          *
   2406          * We initialize arrayClass to Object here, because it's possible
   2407          * for us to set numDims=0.
   2408          */
   2409         if (arrayDim1 < arrayDim2)
   2410             numDims = arrayDim1;
   2411         else
   2412             numDims = arrayDim2;
   2413         arrayClass = commonElem = c1->super;     // == java.lang.Object
   2414     }
   2415 
   2416     /*
   2417      * Find an appropriately-dimensioned array class.  This is easiest
   2418      * to do iteratively, using the array class found by the current round
   2419      * as the element type for the next round.
   2420      */
   2421     for (i = 0; i < numDims; i++) {
   2422         arrayClass = dvmFindArrayClassForElement(commonElem);
   2423         commonElem = arrayClass;
   2424     }
   2425     assert(arrayClass != NULL);
   2426 
   2427     LOGVV("ArrayMerge '%s' + '%s' --> '%s'",
   2428         c1->descriptor, c2->descriptor, arrayClass->descriptor);
   2429     return arrayClass;
   2430 }
   2431 
   2432 /*
   2433  * Find the first common superclass of the two classes.  We're not
   2434  * interested in common interfaces.
   2435  *
   2436  * The easiest way to do this for concrete classes is to compute the "class
   2437  * depth" of each, move up toward the root of the deepest one until they're
   2438  * at the same depth, then walk both up to the root until they match.
   2439  *
   2440  * If both classes are arrays, we need to merge based on array depth and
   2441  * element type.
   2442  *
   2443  * If one class is an interface, we check to see if the other class/interface
   2444  * (or one of its predecessors) implements the interface.  If so, we return
   2445  * the interface; otherwise, we return Object.
   2446  *
   2447  * NOTE: we continue the tradition of "lazy interface handling".  To wit,
   2448  * suppose we have three classes:
   2449  *   One implements Fancy, Free
   2450  *   Two implements Fancy, Free
   2451  *   Three implements Free
   2452  * where Fancy and Free are unrelated interfaces.  The code requires us
   2453  * to merge One into Two.  Ideally we'd use a common interface, which
   2454  * gives us a choice between Fancy and Free, and no guidance on which to
   2455  * use.  If we use Free, we'll be okay when Three gets merged in, but if
   2456  * we choose Fancy, we're hosed.  The "ideal" solution is to create a
   2457  * set of common interfaces and carry that around, merging further references
   2458  * into it.  This is a pain.  The easy solution is to simply boil them
   2459  * down to Objects and let the runtime invokeinterface call fail, which
   2460  * is what we do.
   2461  */
   2462 static ClassObject* findCommonSuperclass(ClassObject* c1, ClassObject* c2)
   2463 {
   2464     assert(!dvmIsPrimitiveClass(c1) && !dvmIsPrimitiveClass(c2));
   2465 
   2466     if (c1 == c2)
   2467         return c1;
   2468 
   2469     if (dvmIsInterfaceClass(c1) && dvmImplements(c2, c1)) {
   2470         if (gDebugVerbose)
   2471             LOGVV("COMMON/I1: %s + %s --> %s",
   2472                 c1->descriptor, c2->descriptor, c1->descriptor);
   2473         return c1;
   2474     }
   2475     if (dvmIsInterfaceClass(c2) && dvmImplements(c1, c2)) {
   2476         if (gDebugVerbose)
   2477             LOGVV("COMMON/I2: %s + %s --> %s",
   2478                 c1->descriptor, c2->descriptor, c2->descriptor);
   2479         return c2;
   2480     }
   2481 
   2482     if (dvmIsArrayClass(c1) && dvmIsArrayClass(c2)) {
   2483         return findCommonArraySuperclass(c1, c2);
   2484     }
   2485 
   2486     return digForSuperclass(c1, c2);
   2487 }
   2488 
   2489 /*
   2490  * Merge two RegType values.
   2491  *
   2492  * Sets "*pChanged" to "true" if the result doesn't match "type1".
   2493  */
   2494 static RegType mergeTypes(RegType type1, RegType type2, bool* pChanged)
   2495 {
   2496     RegType result;
   2497 
   2498     /*
   2499      * Check for trivial case so we don't have to hit memory.
   2500      */
   2501     if (type1 == type2)
   2502         return type1;
   2503 
   2504     /*
   2505      * Use the table if we can, and reject any attempts to merge something
   2506      * from the table with a reference type.
   2507      *
   2508      * Uninitialized references are composed of the enum ORed with an
   2509      * index value.  The uninitialized table entry at index zero *will*
   2510      * show up as a simple kRegTypeUninit value.  Since this cannot be
   2511      * merged with anything but itself, the rules do the right thing.
   2512      */
   2513     if (type1 < kRegTypeMAX) {
   2514         if (type2 < kRegTypeMAX) {
   2515             result = gDvmMergeTab[type1][type2];
   2516         } else {
   2517             /* simple + reference == conflict, usually */
   2518             if (type1 == kRegTypeZero)
   2519                 result = type2;
   2520             else
   2521                 result = kRegTypeConflict;
   2522         }
   2523     } else {
   2524         if (type2 < kRegTypeMAX) {
   2525             /* reference + simple == conflict, usually */
   2526             if (type2 == kRegTypeZero)
   2527                 result = type1;
   2528             else
   2529                 result = kRegTypeConflict;
   2530         } else {
   2531             /* merging two references */
   2532             if (regTypeIsUninitReference(type1) ||
   2533                 regTypeIsUninitReference(type2))
   2534             {
   2535                 /* can't merge uninit with anything but self */
   2536                 result = kRegTypeConflict;
   2537             } else {
   2538                 ClassObject* clazz1 = regTypeInitializedReferenceToClass(type1);
   2539                 ClassObject* clazz2 = regTypeInitializedReferenceToClass(type2);
   2540                 ClassObject* mergedClass;
   2541 
   2542                 mergedClass = findCommonSuperclass(clazz1, clazz2);
   2543                 assert(mergedClass != NULL);
   2544                 result = regTypeFromClass(mergedClass);
   2545             }
   2546         }
   2547     }
   2548 
   2549     if (result != type1)
   2550         *pChanged = true;
   2551     return result;
   2552 }
   2553 
   2554 /*
   2555  * Merge the bits that indicate which monitor entry addresses on the stack
   2556  * are associated with this register.
   2557  *
   2558  * The merge is a simple bitwise AND.
   2559  *
   2560  * Sets "*pChanged" to "true" if the result doesn't match "ents1".
   2561  */
   2562 static MonitorEntries mergeMonitorEntries(MonitorEntries ents1,
   2563     MonitorEntries ents2, bool* pChanged)
   2564 {
   2565     MonitorEntries result = ents1 & ents2;
   2566     if (result != ents1)
   2567         *pChanged = true;
   2568     return result;
   2569 }
   2570 
   2571 /*
   2572  * Control can transfer to "nextInsn".
   2573  *
   2574  * Merge the registers from "workLine" into "regTable" at "nextInsn", and
   2575  * set the "changed" flag on the target address if any of the registers
   2576  * has changed.
   2577  *
   2578  * Returns "false" if we detect mis-matched monitor stacks.
   2579  */
   2580 static bool updateRegisters(const Method* meth, InsnFlags* insnFlags,
   2581     RegisterTable* regTable, int nextInsn, const RegisterLine* workLine)
   2582 {
   2583     const size_t insnRegCountPlus = regTable->insnRegCountPlus;
   2584     assert(workLine != NULL);
   2585     const RegType* workRegs = workLine->regTypes;
   2586 
   2587     if (!dvmInsnIsVisitedOrChanged(insnFlags, nextInsn)) {
   2588         /*
   2589          * We haven't processed this instruction before, and we haven't
   2590          * touched the registers here, so there's nothing to "merge".  Copy
   2591          * the registers over and mark it as changed.  (This is the only
   2592          * way a register can transition out of "unknown", so this is not
   2593          * just an optimization.)
   2594          */
   2595         LOGVV("COPY into 0x%04x", nextInsn);
   2596         copyLineToTable(regTable, nextInsn, workLine);
   2597         dvmInsnSetChanged(insnFlags, nextInsn, true);
   2598 #ifdef VERIFIER_STATS
   2599         gDvm.verifierStats.copyRegCount++;
   2600 #endif
   2601     } else {
   2602         if (gDebugVerbose) {
   2603             LOGVV("MERGE into 0x%04x", nextInsn);
   2604             //dumpRegTypes(vdata, targetRegs, 0, "targ", NULL, 0);
   2605             //dumpRegTypes(vdata, workRegs, 0, "work", NULL, 0);
   2606         }
   2607         /* merge registers, set Changed only if different */
   2608         RegisterLine* targetLine = getRegisterLine(regTable, nextInsn);
   2609         RegType* targetRegs = targetLine->regTypes;
   2610         MonitorEntries* workMonEnts = workLine->monitorEntries;
   2611         MonitorEntries* targetMonEnts = targetLine->monitorEntries;
   2612         bool changed = false;
   2613         unsigned int idx;
   2614 
   2615         assert(targetRegs != NULL);
   2616 
   2617         if (targetMonEnts != NULL) {
   2618             /*
   2619              * Monitor stacks must be identical.
   2620              */
   2621             if (targetLine->monitorStackTop != workLine->monitorStackTop) {
   2622                 LOG_VFY_METH(meth,
   2623                     "VFY: mismatched stack depth %d vs. %d at 0x%04x",
   2624                     targetLine->monitorStackTop, workLine->monitorStackTop,
   2625                     nextInsn);
   2626                 return false;
   2627             }
   2628             if (memcmp(targetLine->monitorStack, workLine->monitorStack,
   2629                     targetLine->monitorStackTop * sizeof(u4)) != 0)
   2630             {
   2631                 LOG_VFY_METH(meth, "VFY: mismatched monitor stacks at 0x%04x",
   2632                     nextInsn);
   2633                 return false;
   2634             }
   2635         }
   2636 
   2637         for (idx = 0; idx < insnRegCountPlus; idx++) {
   2638             targetRegs[idx] =
   2639                     mergeTypes(targetRegs[idx], workRegs[idx], &changed);
   2640 
   2641             if (targetMonEnts != NULL) {
   2642                 targetMonEnts[idx] = mergeMonitorEntries(targetMonEnts[idx],
   2643                     workMonEnts[idx], &changed);
   2644             }
   2645         }
   2646 
   2647         if (gDebugVerbose) {
   2648             //ALOGI(" RESULT (changed=%d)", changed);
   2649             //dumpRegTypes(vdata, targetRegs, 0, "rslt", NULL, 0);
   2650         }
   2651 #ifdef VERIFIER_STATS
   2652         gDvm.verifierStats.mergeRegCount++;
   2653         if (changed)
   2654             gDvm.verifierStats.mergeRegChanged++;
   2655 #endif
   2656 
   2657         if (changed)
   2658             dvmInsnSetChanged(insnFlags, nextInsn, true);
   2659     }
   2660 
   2661     return true;
   2662 }
   2663 
   2664 
   2665 /*
   2666  * ===========================================================================
   2667  *      Utility functions
   2668  * ===========================================================================
   2669  */
   2670 
   2671 /*
   2672  * Look up an instance field, specified by "fieldIdx", that is going to be
   2673  * accessed in object "objType".  This resolves the field and then verifies
   2674  * that the class containing the field is an instance of the reference in
   2675  * "objType".
   2676  *
   2677  * It is possible for "objType" to be kRegTypeZero, meaning that we might
   2678  * have a null reference.  This is a runtime problem, so we allow it,
   2679  * skipping some of the type checks.
   2680  *
   2681  * In general, "objType" must be an initialized reference.  However, we
   2682  * allow it to be uninitialized if this is an "<init>" method and the field
   2683  * is declared within the "objType" class.
   2684  *
   2685  * Returns an InstField on success, returns NULL and sets "*pFailure"
   2686  * on failure.
   2687  */
   2688 static InstField* getInstField(const Method* meth,
   2689     const UninitInstanceMap* uninitMap, RegType objType, int fieldIdx,
   2690     VerifyError* pFailure)
   2691 {
   2692     InstField* instField = NULL;
   2693     ClassObject* objClass;
   2694     bool mustBeLocal = false;
   2695 
   2696     if (!regTypeIsReference(objType)) {
   2697         LOG_VFY("VFY: attempt to access field in non-reference type %d",
   2698             objType);
   2699         *pFailure = VERIFY_ERROR_GENERIC;
   2700         goto bail;
   2701     }
   2702 
   2703     instField = dvmOptResolveInstField(meth->clazz, fieldIdx, pFailure);
   2704     if (instField == NULL) {
   2705         LOG_VFY("VFY: unable to resolve instance field %u", fieldIdx);
   2706         assert(!VERIFY_OK(*pFailure));
   2707         goto bail;
   2708     }
   2709 
   2710     if (objType == kRegTypeZero)
   2711         goto bail;
   2712 
   2713     /*
   2714      * Access to fields in uninitialized objects is allowed if this is
   2715      * the <init> method for the object and the field in question is
   2716      * declared by this class.
   2717      */
   2718     objClass = regTypeReferenceToClass(objType, uninitMap);
   2719     assert(objClass != NULL);
   2720     if (regTypeIsUninitReference(objType)) {
   2721         if (!isInitMethod(meth) || meth->clazz != objClass) {
   2722             LOG_VFY("VFY: attempt to access field via uninitialized ref");
   2723             *pFailure = VERIFY_ERROR_GENERIC;
   2724             goto bail;
   2725         }
   2726         mustBeLocal = true;
   2727     }
   2728 
   2729     if (!dvmInstanceof(objClass, instField->clazz)) {
   2730         LOG_VFY("VFY: invalid field access (field %s.%s, through %s ref)",
   2731                 instField->clazz->descriptor, instField->name,
   2732                 objClass->descriptor);
   2733         *pFailure = VERIFY_ERROR_NO_FIELD;
   2734         goto bail;
   2735     }
   2736 
   2737     if (mustBeLocal) {
   2738         /* for uninit ref, make sure it's defined by this class, not super */
   2739         if (instField < objClass->ifields ||
   2740             instField >= objClass->ifields + objClass->ifieldCount)
   2741         {
   2742             LOG_VFY("VFY: invalid constructor field access (field %s in %s)",
   2743                     instField->name, objClass->descriptor);
   2744             *pFailure = VERIFY_ERROR_GENERIC;
   2745             goto bail;
   2746         }
   2747     }
   2748 
   2749 bail:
   2750     return instField;
   2751 }
   2752 
   2753 /*
   2754  * Look up a static field.
   2755  *
   2756  * Returns a StaticField on success, returns NULL and sets "*pFailure"
   2757  * on failure.
   2758  */
   2759 static StaticField* getStaticField(const Method* meth, int fieldIdx,
   2760     VerifyError* pFailure)
   2761 {
   2762     StaticField* staticField;
   2763 
   2764     staticField = dvmOptResolveStaticField(meth->clazz, fieldIdx, pFailure);
   2765     if (staticField == NULL) {
   2766         DexFile* pDexFile = meth->clazz->pDvmDex->pDexFile;
   2767         const DexFieldId* pFieldId;
   2768 
   2769         pFieldId = dexGetFieldId(pDexFile, fieldIdx);
   2770 
   2771         LOG_VFY("VFY: unable to resolve static field %u (%s) in %s", fieldIdx,
   2772             dexStringById(pDexFile, pFieldId->nameIdx),
   2773             dexStringByTypeIdx(pDexFile, pFieldId->classIdx));
   2774         assert(!VERIFY_OK(*pFailure));
   2775         goto bail;
   2776     }
   2777 
   2778 bail:
   2779     return staticField;
   2780 }
   2781 
   2782 /*
   2783  * If "field" is marked "final", make sure this is the either <clinit>
   2784  * or <init> as appropriate.
   2785  *
   2786  * Sets "*pFailure" on failure.
   2787  */
   2788 static void checkFinalFieldAccess(const Method* meth, const Field* field,
   2789     VerifyError* pFailure)
   2790 {
   2791     if (!dvmIsFinalField(field))
   2792         return;
   2793 
   2794     /* make sure we're in the same class */
   2795     if (meth->clazz != field->clazz) {
   2796         LOG_VFY_METH(meth, "VFY: can't modify final field %s.%s",
   2797             field->clazz->descriptor, field->name);
   2798         *pFailure = VERIFY_ERROR_ACCESS_FIELD;
   2799         return;
   2800     }
   2801 
   2802     /*
   2803      * The VM spec descriptions of putfield and putstatic say that
   2804      * IllegalAccessError is only thrown when the instructions appear
   2805      * outside the declaring class.  Our earlier attempts to restrict
   2806      * final field modification to constructors are, therefore, wrong.
   2807      */
   2808 #if 0
   2809     /* make sure we're in the right kind of constructor */
   2810     if (dvmIsStaticField(field)) {
   2811         if (!isClassInitMethod(meth)) {
   2812             LOG_VFY_METH(meth,
   2813                 "VFY: can't modify final static field outside <clinit>");
   2814             *pFailure = VERIFY_ERROR_GENERIC;
   2815         }
   2816     } else {
   2817         if (!isInitMethod(meth)) {
   2818             LOG_VFY_METH(meth,
   2819                 "VFY: can't modify final field outside <init>");
   2820             *pFailure = VERIFY_ERROR_GENERIC;
   2821         }
   2822     }
   2823 #endif
   2824 }
   2825 
   2826 /*
   2827  * Make sure that the register type is suitable for use as an array index.
   2828  *
   2829  * Sets "*pFailure" if not.
   2830  */
   2831 static void checkArrayIndexType(const Method* meth, RegType regType,
   2832     VerifyError* pFailure)
   2833 {
   2834     if (VERIFY_OK(*pFailure)) {
   2835         /*
   2836          * The 1nr types are interchangeable at this level. However,
   2837          * check that a float is not used as the index.
   2838          */
   2839         checkTypeCategory(regType, kTypeCategory1nr, pFailure);
   2840         if (regType == kRegTypeFloat) {
   2841           *pFailure = VERIFY_ERROR_GENERIC;
   2842         }
   2843         if (!VERIFY_OK(*pFailure)) {
   2844             LOG_VFY_METH(meth, "Invalid reg type for array index (%d)",
   2845                 regType);
   2846         }
   2847     }
   2848 }
   2849 
   2850 /*
   2851  * Check constraints on constructor return.  Specifically, make sure that
   2852  * the "this" argument got initialized.
   2853  *
   2854  * The "this" argument to <init> uses code offset kUninitThisArgAddr, which
   2855  * puts it at the start of the list in slot 0.  If we see a register with
   2856  * an uninitialized slot 0 reference, we know it somehow didn't get
   2857  * initialized.
   2858  *
   2859  * Returns "true" if all is well.
   2860  */
   2861 static bool checkConstructorReturn(const Method* meth,
   2862     const RegisterLine* registerLine, const int insnRegCount)
   2863 {
   2864     const RegType* insnRegs = registerLine->regTypes;
   2865     int i;
   2866 
   2867     if (!isInitMethod(meth))
   2868         return true;
   2869 
   2870     RegType uninitThis = regTypeFromUninitIndex(kUninitThisArgSlot);
   2871 
   2872     for (i = 0; i < insnRegCount; i++) {
   2873         if (insnRegs[i] == uninitThis) {
   2874             LOG_VFY("VFY: <init> returning without calling superclass init");
   2875             return false;
   2876         }
   2877     }
   2878     return true;
   2879 }
   2880 
   2881 /*
   2882  * Verify that the target instruction is not "move-exception".  It's important
   2883  * that the only way to execute a move-exception is as the first instruction
   2884  * of an exception handler.
   2885  *
   2886  * Returns "true" if all is well, "false" if the target instruction is
   2887  * move-exception.
   2888  */
   2889 static bool checkMoveException(const Method* meth, int insnIdx,
   2890     const char* logNote)
   2891 {
   2892     assert(insnIdx >= 0 && insnIdx < (int)dvmGetMethodInsnsSize(meth));
   2893 
   2894     if ((meth->insns[insnIdx] & 0xff) == OP_MOVE_EXCEPTION) {
   2895         LOG_VFY("VFY: invalid use of move-exception");
   2896         return false;
   2897     }
   2898     return true;
   2899 }
   2900 
   2901 /*
   2902  * For the "move-exception" instruction at "insnIdx", which must be at an
   2903  * exception handler address, determine the first common superclass of
   2904  * all exceptions that can land here.  (For javac output, we're probably
   2905  * looking at multiple spans of bytecode covered by one "try" that lands
   2906  * at an exception-specific "catch", but in general the handler could be
   2907  * shared for multiple exceptions.)
   2908  *
   2909  * Returns NULL if no matching exception handler can be found, or if the
   2910  * exception is not a subclass of Throwable.
   2911  */
   2912 static ClassObject* getCaughtExceptionType(const Method* meth, int insnIdx,
   2913     VerifyError* pFailure)
   2914 {
   2915     VerifyError localFailure;
   2916     const DexCode* pCode;
   2917     DexFile* pDexFile;
   2918     ClassObject* commonSuper = NULL;
   2919     u4 handlersSize;
   2920     u4 offset;
   2921     u4 i;
   2922 
   2923     pDexFile = meth->clazz->pDvmDex->pDexFile;
   2924     pCode = dvmGetMethodCode(meth);
   2925 
   2926     if (pCode->triesSize != 0) {
   2927         handlersSize = dexGetHandlersSize(pCode);
   2928         offset = dexGetFirstHandlerOffset(pCode);
   2929     } else {
   2930         handlersSize = 0;
   2931         offset = 0;
   2932     }
   2933 
   2934     for (i = 0; i < handlersSize; i++) {
   2935         DexCatchIterator iterator;
   2936         dexCatchIteratorInit(&iterator, pCode, offset);
   2937 
   2938         for (;;) {
   2939             const DexCatchHandler* handler = dexCatchIteratorNext(&iterator);
   2940 
   2941             if (handler == NULL) {
   2942                 break;
   2943             }
   2944 
   2945             if (handler->address == (u4) insnIdx) {
   2946                 ClassObject* clazz;
   2947 
   2948                 if (handler->typeIdx == kDexNoIndex)
   2949                     clazz = gDvm.exThrowable;
   2950                 else
   2951                     clazz = dvmOptResolveClass(meth->clazz, handler->typeIdx,
   2952                                 &localFailure);
   2953 
   2954                 if (clazz == NULL) {
   2955                     LOG_VFY("VFY: unable to resolve exception class %u (%s)",
   2956                         handler->typeIdx,
   2957                         dexStringByTypeIdx(pDexFile, handler->typeIdx));
   2958                     /* TODO: do we want to keep going?  If we don't fail
   2959                      * this we run the risk of having a non-Throwable
   2960                      * introduced at runtime.  However, that won't pass
   2961                      * an instanceof test, so is essentially harmless. */
   2962                 } else {
   2963                     if (commonSuper == NULL)
   2964                         commonSuper = clazz;
   2965                     else
   2966                         commonSuper = findCommonSuperclass(clazz, commonSuper);
   2967                 }
   2968             }
   2969         }
   2970 
   2971         offset = dexCatchIteratorGetEndOffset(&iterator, pCode);
   2972     }
   2973 
   2974     if (commonSuper == NULL) {
   2975         /* no catch blocks, or no catches with classes we can find */
   2976         LOG_VFY_METH(meth,
   2977             "VFY: unable to find exception handler at addr %#x", insnIdx);
   2978         *pFailure = VERIFY_ERROR_GENERIC;
   2979     } else {
   2980         // TODO: verify the class is an instance of Throwable?
   2981     }
   2982 
   2983     return commonSuper;
   2984 }
   2985 
   2986 /*
   2987  * Helper for initRegisterTable.
   2988  *
   2989  * Returns an updated copy of "storage".
   2990  */
   2991 static u1* assignLineStorage(u1* storage, RegisterLine* line,
   2992     bool trackMonitors, size_t regTypeSize, size_t monEntSize, size_t stackSize)
   2993 {
   2994     line->regTypes = (RegType*) storage;
   2995     storage += regTypeSize;
   2996 
   2997     if (trackMonitors) {
   2998         line->monitorEntries = (MonitorEntries*) storage;
   2999         storage += monEntSize;
   3000         line->monitorStack = (u4*) storage;
   3001         storage += stackSize;
   3002 
   3003         assert(line->monitorStackTop == 0);
   3004     }
   3005 
   3006     return storage;
   3007 }
   3008 
   3009 /*
   3010  * Initialize the RegisterTable.
   3011  *
   3012  * Every instruction address can have a different set of information about
   3013  * what's in which register, but for verification purposes we only need to
   3014  * store it at branch target addresses (because we merge into that).
   3015  *
   3016  * By zeroing out the regType storage we are effectively initializing the
   3017  * register information to kRegTypeUnknown.
   3018  *
   3019  * We jump through some hoops here to minimize the total number of
   3020  * allocations we have to perform per method verified.
   3021  */
   3022 static bool initRegisterTable(const VerifierData* vdata,
   3023     RegisterTable* regTable, RegisterTrackingMode trackRegsFor)
   3024 {
   3025     const Method* meth = vdata->method;
   3026     const int insnsSize = vdata->insnsSize;
   3027     const InsnFlags* insnFlags = vdata->insnFlags;
   3028     const int kExtraLines = 2;  /* workLine, savedLine */
   3029     int i;
   3030 
   3031     /*
   3032      * Every address gets a RegisterLine struct.  This is wasteful, but
   3033      * not so much that it's worth chasing through an extra level of
   3034      * indirection.
   3035      */
   3036     regTable->insnRegCountPlus = meth->registersSize + kExtraRegs;
   3037     regTable->registerLines =
   3038         (RegisterLine*) calloc(insnsSize, sizeof(RegisterLine));
   3039     if (regTable->registerLines == NULL)
   3040         return false;
   3041 
   3042     assert(insnsSize > 0);
   3043 
   3044     /*
   3045      * Count up the number of "interesting" instructions.
   3046      *
   3047      * "All" means "every address that holds the start of an instruction".
   3048      * "Branches" and "GcPoints" mean just those addresses.
   3049      *
   3050      * "GcPoints" fills about half the addresses, "Branches" about 15%.
   3051      */
   3052     int interestingCount = kExtraLines;
   3053 
   3054     for (i = 0; i < insnsSize; i++) {
   3055         bool interesting;
   3056 
   3057         switch (trackRegsFor) {
   3058         case kTrackRegsAll:
   3059             interesting = dvmInsnIsOpcode(insnFlags, i);
   3060             break;
   3061         case kTrackRegsGcPoints:
   3062             interesting = dvmInsnIsGcPoint(insnFlags, i) ||
   3063                           dvmInsnIsBranchTarget(insnFlags, i);
   3064             break;
   3065         case kTrackRegsBranches:
   3066             interesting = dvmInsnIsBranchTarget(insnFlags, i);
   3067             break;
   3068         default:
   3069             dvmAbort();
   3070             return false;
   3071         }
   3072 
   3073         if (interesting)
   3074             interestingCount++;
   3075 
   3076         /* count instructions, for display only */
   3077         //if (dvmInsnIsOpcode(insnFlags, i))
   3078         //    insnCount++;
   3079     }
   3080 
   3081     /*
   3082      * Allocate storage for the register type arrays.
   3083      * TODO: set trackMonitors based on global config option
   3084      */
   3085     size_t regTypeSize = regTable->insnRegCountPlus * sizeof(RegType);
   3086     size_t monEntSize = regTable->insnRegCountPlus * sizeof(MonitorEntries);
   3087     size_t stackSize = kMaxMonitorStackDepth * sizeof(u4);
   3088     bool trackMonitors;
   3089 
   3090     if (gDvm.monitorVerification) {
   3091         trackMonitors = (vdata->monitorEnterCount != 0);
   3092     } else {
   3093         trackMonitors = false;
   3094     }
   3095 
   3096     size_t spacePerEntry = regTypeSize +
   3097         (trackMonitors ? monEntSize + stackSize : 0);
   3098     regTable->lineAlloc = calloc(interestingCount, spacePerEntry);
   3099     if (regTable->lineAlloc == NULL)
   3100         return false;
   3101 
   3102 #ifdef VERIFIER_STATS
   3103     size_t totalSpace = interestingCount * spacePerEntry +
   3104         insnsSize * sizeof(RegisterLine);
   3105     if (gDvm.verifierStats.biggestAlloc < totalSpace)
   3106         gDvm.verifierStats.biggestAlloc = totalSpace;
   3107 #endif
   3108 
   3109     /*
   3110      * Populate the sparse register line table.
   3111      *
   3112      * There is a RegisterLine associated with every address, but not
   3113      * every RegisterLine has non-NULL pointers to storage for its fields.
   3114      */
   3115     u1* storage = (u1*)regTable->lineAlloc;
   3116     for (i = 0; i < insnsSize; i++) {
   3117         bool interesting;
   3118 
   3119         switch (trackRegsFor) {
   3120         case kTrackRegsAll:
   3121             interesting = dvmInsnIsOpcode(insnFlags, i);
   3122             break;
   3123         case kTrackRegsGcPoints:
   3124             interesting = dvmInsnIsGcPoint(insnFlags, i) ||
   3125                           dvmInsnIsBranchTarget(insnFlags, i);
   3126             break;
   3127         case kTrackRegsBranches:
   3128             interesting = dvmInsnIsBranchTarget(insnFlags, i);
   3129             break;
   3130         default:
   3131             dvmAbort();
   3132             return false;
   3133         }
   3134 
   3135         if (interesting) {
   3136             storage = assignLineStorage(storage, &regTable->registerLines[i],
   3137                 trackMonitors, regTypeSize, monEntSize, stackSize);
   3138         }
   3139     }
   3140 
   3141     /*
   3142      * Grab storage for our "temporary" register lines.
   3143      */
   3144     storage = assignLineStorage(storage, &regTable->workLine,
   3145         trackMonitors, regTypeSize, monEntSize, stackSize);
   3146     storage = assignLineStorage(storage, &regTable->savedLine,
   3147         trackMonitors, regTypeSize, monEntSize, stackSize);
   3148 
   3149     //ALOGD("Tracking registers for [%d], total %d in %d units",
   3150     //    trackRegsFor, interestingCount-kExtraLines, insnsSize);
   3151 
   3152     assert(storage - (u1*)regTable->lineAlloc ==
   3153         (int) (interestingCount * spacePerEntry));
   3154     assert(regTable->registerLines[0].regTypes != NULL);
   3155     return true;
   3156 }
   3157 
   3158 /*
   3159  * Free up any "hairy" structures associated with register lines.
   3160  */
   3161 static void freeRegisterLineInnards(VerifierData* vdata)
   3162 {
   3163     unsigned int idx;
   3164 
   3165     if (vdata->registerLines == NULL)
   3166         return;
   3167 
   3168     for (idx = 0; idx < vdata->insnsSize; idx++) {
   3169         BitVector* liveRegs = vdata->registerLines[idx].liveRegs;
   3170         if (liveRegs != NULL)
   3171             dvmFreeBitVector(liveRegs);
   3172     }
   3173 }
   3174 
   3175 
   3176 /*
   3177  * Verify that the arguments in a filled-new-array instruction are valid.
   3178  *
   3179  * "resClass" is the class refered to by pDecInsn->vB.
   3180  */
   3181 static void verifyFilledNewArrayRegs(const Method* meth,
   3182     RegisterLine* registerLine, const DecodedInstruction* pDecInsn,
   3183     ClassObject* resClass, bool isRange, VerifyError* pFailure)
   3184 {
   3185     u4 argCount = pDecInsn->vA;
   3186     RegType expectedType;
   3187     PrimitiveType elemType;
   3188     unsigned int ui;
   3189 
   3190     assert(dvmIsArrayClass(resClass));
   3191     elemType = resClass->elementClass->primitiveType;
   3192     if (elemType == PRIM_NOT) {
   3193         expectedType = regTypeFromClass(resClass->elementClass);
   3194     } else {
   3195         expectedType = primitiveTypeToRegType(elemType);
   3196     }
   3197     //ALOGI("filled-new-array: %s -> %d", resClass->descriptor, expectedType);
   3198 
   3199     /*
   3200      * Verify each register.  If "argCount" is bad, verifyRegisterType()
   3201      * will run off the end of the list and fail.  It's legal, if silly,
   3202      * for argCount to be zero.
   3203      */
   3204     for (ui = 0; ui < argCount; ui++) {
   3205         u4 getReg;
   3206 
   3207         if (isRange)
   3208             getReg = pDecInsn->vC + ui;
   3209         else
   3210             getReg = pDecInsn->arg[ui];
   3211 
   3212         verifyRegisterType(registerLine, getReg, expectedType, pFailure);
   3213         if (!VERIFY_OK(*pFailure)) {
   3214             LOG_VFY("VFY: filled-new-array arg %u(%u) not valid", ui, getReg);
   3215             return;
   3216         }
   3217     }
   3218 }
   3219 
   3220 
   3221 /*
   3222  * Replace an instruction with "throw-verification-error".  This allows us to
   3223  * defer error reporting until the code path is first used.
   3224  *
   3225  * This is expected to be called during "just in time" verification, not
   3226  * from within dexopt.  (Verification failures in dexopt will result in
   3227  * postponement of verification to first use of the class.)
   3228  *
   3229  * The throw-verification-error instruction requires two code units.  Some
   3230  * of the replaced instructions require three; the third code unit will
   3231  * receive a "nop".  The instruction's length will be left unchanged
   3232  * in "insnFlags".
   3233  *
   3234  * The VM postpones setting of debugger breakpoints in unverified classes,
   3235  * so there should be no clashes with the debugger.
   3236  *
   3237  * Returns "true" on success.
   3238  */
   3239 static bool replaceFailingInstruction(const Method* meth, InsnFlags* insnFlags,
   3240     int insnIdx, VerifyError failure)
   3241 {
   3242     VerifyErrorRefType refType;
   3243     u2* oldInsns = (u2*) meth->insns + insnIdx;
   3244     int width;
   3245 
   3246     if (gDvm.optimizing)
   3247         ALOGD("Weird: RFI during dexopt?");
   3248 
   3249     /*
   3250      * Generate the new instruction out of the old.
   3251      *
   3252      * First, make sure this is an instruction we're expecting to stomp on.
   3253      */
   3254     Opcode opcode = dexOpcodeFromCodeUnit(*oldInsns);
   3255     switch (opcode) {
   3256     case OP_CONST_CLASS:                // insn[1] == class ref, 2 bytes
   3257     case OP_CHECK_CAST:
   3258     case OP_INSTANCE_OF:
   3259     case OP_NEW_INSTANCE:
   3260     case OP_NEW_ARRAY:
   3261     case OP_FILLED_NEW_ARRAY:           // insn[1] == class ref, 3 bytes
   3262     case OP_FILLED_NEW_ARRAY_RANGE:
   3263         refType = VERIFY_ERROR_REF_CLASS;
   3264         break;
   3265 
   3266     case OP_IGET:                       // insn[1] == field ref, 2 bytes
   3267     case OP_IGET_BOOLEAN:
   3268     case OP_IGET_BYTE:
   3269     case OP_IGET_CHAR:
   3270     case OP_IGET_SHORT:
   3271     case OP_IGET_WIDE:
   3272     case OP_IGET_OBJECT:
   3273     case OP_IPUT:
   3274     case OP_IPUT_BOOLEAN:
   3275     case OP_IPUT_BYTE:
   3276     case OP_IPUT_CHAR:
   3277     case OP_IPUT_SHORT:
   3278     case OP_IPUT_WIDE:
   3279     case OP_IPUT_OBJECT:
   3280     case OP_SGET:
   3281     case OP_SGET_BOOLEAN:
   3282     case OP_SGET_BYTE:
   3283     case OP_SGET_CHAR:
   3284     case OP_SGET_SHORT:
   3285     case OP_SGET_WIDE:
   3286     case OP_SGET_OBJECT:
   3287     case OP_SPUT:
   3288     case OP_SPUT_BOOLEAN:
   3289     case OP_SPUT_BYTE:
   3290     case OP_SPUT_CHAR:
   3291     case OP_SPUT_SHORT:
   3292     case OP_SPUT_WIDE:
   3293     case OP_SPUT_OBJECT:
   3294         refType = VERIFY_ERROR_REF_FIELD;
   3295         break;
   3296 
   3297     case OP_INVOKE_VIRTUAL:             // insn[1] == method ref, 3 bytes
   3298     case OP_INVOKE_VIRTUAL_RANGE:
   3299     case OP_INVOKE_SUPER:
   3300     case OP_INVOKE_SUPER_RANGE:
   3301     case OP_INVOKE_DIRECT:
   3302     case OP_INVOKE_DIRECT_RANGE:
   3303     case OP_INVOKE_STATIC:
   3304     case OP_INVOKE_STATIC_RANGE:
   3305     case OP_INVOKE_INTERFACE:
   3306     case OP_INVOKE_INTERFACE_RANGE:
   3307         refType = VERIFY_ERROR_REF_METHOD;
   3308         break;
   3309 
   3310     default:
   3311         /* could handle this in a generic way, but this is probably safer */
   3312         LOG_VFY("GLITCH: verifier asked to replace opcode 0x%02x", opcode);
   3313         return false;
   3314     }
   3315 
   3316     assert((dexGetFlagsFromOpcode(opcode) & kInstrCanThrow) != 0);
   3317 
   3318     /* write a NOP over the third code unit, if necessary */
   3319     width = dvmInsnGetWidth(insnFlags, insnIdx);
   3320     switch (width) {
   3321     case 2:
   3322     case 4:
   3323         /* nothing to do */
   3324         break;
   3325     case 3:
   3326         dvmUpdateCodeUnit(meth, oldInsns+2, OP_NOP);
   3327         break;
   3328     default:
   3329         /* whoops */
   3330         ALOGE("ERROR: stomped a %d-unit instruction with a verifier error",
   3331             width);
   3332         dvmAbort();
   3333     }
   3334 
   3335     /* encode the opcode, with the failure code in the high byte */
   3336     assert(width == 2 || width == 3);
   3337     u2 newVal = OP_THROW_VERIFICATION_ERROR |
   3338         (failure << 8) | (refType << (8 + kVerifyErrorRefTypeShift));
   3339     dvmUpdateCodeUnit(meth, oldInsns, newVal);
   3340 
   3341     return true;
   3342 }
   3343 
   3344 /*
   3345  * Handle a monitor-enter instruction.
   3346  */
   3347 void handleMonitorEnter(RegisterLine* workLine, u4 regIdx, u4 insnIdx,
   3348     VerifyError* pFailure)
   3349 {
   3350     if (!regTypeIsReference(getRegisterType(workLine, regIdx))) {
   3351         LOG_VFY("VFY: monitor-enter on non-object");
   3352         *pFailure = VERIFY_ERROR_GENERIC;
   3353         return;
   3354     }
   3355 
   3356     if (workLine->monitorEntries == NULL) {
   3357         /* should only be true if monitor verification is disabled */
   3358         assert(!gDvm.monitorVerification);
   3359         return;
   3360     }
   3361 
   3362     if (workLine->monitorStackTop == kMaxMonitorStackDepth) {
   3363         LOG_VFY("VFY: monitor-enter stack overflow (%d)",
   3364             kMaxMonitorStackDepth);
   3365         *pFailure = VERIFY_ERROR_GENERIC;
   3366         return;
   3367     }
   3368 
   3369     /*
   3370      * Push an entry on the stack, and set a bit in the register flags to
   3371      * indicate that it's associated with this register.
   3372      */
   3373     workLine->monitorEntries[regIdx] |= 1 << workLine->monitorStackTop;
   3374     workLine->monitorStack[workLine->monitorStackTop++] = insnIdx;
   3375 }
   3376 
   3377 /*
   3378  * Handle a monitor-exit instruction.
   3379  */
   3380 void handleMonitorExit(RegisterLine* workLine, u4 regIdx, u4 insnIdx,
   3381     VerifyError* pFailure)
   3382 {
   3383     if (!regTypeIsReference(getRegisterType(workLine, regIdx))) {
   3384         LOG_VFY("VFY: monitor-exit on non-object");
   3385         *pFailure = VERIFY_ERROR_GENERIC;
   3386         return;
   3387     }
   3388 
   3389     if (workLine->monitorEntries == NULL) {
   3390         /* should only be true if monitor verification is disabled */
   3391         assert(!gDvm.monitorVerification);
   3392         return;
   3393     }
   3394 
   3395     if (workLine->monitorStackTop == 0) {
   3396         LOG_VFY("VFY: monitor-exit stack underflow");
   3397         *pFailure = VERIFY_ERROR_GENERIC;
   3398         return;
   3399     }
   3400 
   3401     /*
   3402      * Confirm that the entry at the top of the stack is associated with
   3403      * the register.  Pop the top entry off.
   3404      */
   3405     workLine->monitorStackTop--;
   3406 #ifdef BUG_3215458_FIXED
   3407     /*
   3408      * TODO: This code can safely be enabled if know we are working on
   3409      * a dex file of format version 036 or later. (That is, we'll need to
   3410      * add a check for the version number.)
   3411      */
   3412     if ((workLine->monitorEntries[regIdx] & (1 << workLine->monitorStackTop))
   3413             == 0)
   3414     {
   3415         LOG_VFY("VFY: monitor-exit bit %d not set: addr=0x%04x (bits[%d]=%#x)",
   3416             workLine->monitorStackTop, insnIdx, regIdx,
   3417             workLine->monitorEntries[regIdx]);
   3418         *pFailure = VERIFY_ERROR_GENERIC;
   3419         return;
   3420     }
   3421 #endif
   3422     workLine->monitorStack[workLine->monitorStackTop] = 0;
   3423 
   3424     /*
   3425      * Clear the bit from the register flags.
   3426      */
   3427     workLine->monitorEntries[regIdx] &= ~(1 << workLine->monitorStackTop);
   3428 }
   3429 
   3430 
   3431 /*
   3432  * ===========================================================================
   3433  *      Entry point and driver loop
   3434  * ===========================================================================
   3435  */
   3436 
   3437 /*
   3438  * One-time preparation.
   3439  */
   3440 static void verifyPrep()
   3441 {
   3442 #ifndef NDEBUG
   3443     /* only need to do this if the table was updated */
   3444     checkMergeTab();
   3445 #endif
   3446 }
   3447 
   3448 /*
   3449  * Entry point for the detailed code-flow analysis of a single method.
   3450  */
   3451 bool dvmVerifyCodeFlow(VerifierData* vdata)
   3452 {
   3453     bool result = false;
   3454     const Method* meth = vdata->method;
   3455     const int insnsSize = vdata->insnsSize;
   3456     const bool generateRegisterMap = gDvm.generateRegisterMaps;
   3457     RegisterTable regTable;
   3458 
   3459     memset(&regTable, 0, sizeof(regTable));
   3460 
   3461 #ifdef VERIFIER_STATS
   3462     gDvm.verifierStats.methodsExamined++;
   3463     if (vdata->monitorEnterCount)
   3464         gDvm.verifierStats.monEnterMethods++;
   3465 #endif
   3466 
   3467     /* TODO: move this elsewhere -- we don't need to do this for every method */
   3468     verifyPrep();
   3469 
   3470     if (meth->registersSize * insnsSize > 4*1024*1024) {
   3471         LOG_VFY_METH(meth,
   3472             "VFY: warning: method is huge (regs=%d insnsSize=%d)",
   3473             meth->registersSize, insnsSize);
   3474         /* might be bogus data, might be some huge generated method */
   3475     }
   3476 
   3477     /*
   3478      * Create register lists, and initialize them to "Unknown".  If we're
   3479      * also going to create the register map, we need to retain the
   3480      * register lists for a larger set of addresses.
   3481      */
   3482     if (!initRegisterTable(vdata, &regTable,
   3483             generateRegisterMap ? kTrackRegsGcPoints : kTrackRegsBranches))
   3484         goto bail;
   3485 
   3486     vdata->registerLines = regTable.registerLines;
   3487 
   3488     /*
   3489      * Perform liveness analysis.
   3490      *
   3491      * We can do this before or after the main verifier pass.  The choice
   3492      * affects whether or not we see the effects of verifier instruction
   3493      * changes, i.e. substitution of throw-verification-error.
   3494      *
   3495      * In practice the ordering doesn't really matter, because T-V-E
   3496      * just prunes "can continue", creating regions of dead code (with
   3497      * corresponding register map data that will never be used).
   3498      */
   3499     if (generateRegisterMap &&
   3500         gDvm.registerMapMode == kRegisterMapModeLivePrecise)
   3501     {
   3502         /*
   3503          * Compute basic blocks and predecessor lists.
   3504          */
   3505         if (!dvmComputeVfyBasicBlocks(vdata))
   3506             goto bail;
   3507 
   3508         /*
   3509          * Compute liveness.
   3510          */
   3511         if (!dvmComputeLiveness(vdata))
   3512             goto bail;
   3513     }
   3514 
   3515     /*
   3516      * Initialize the types of the registers that correspond to the
   3517      * method arguments.  We can determine this from the method signature.
   3518      */
   3519     if (!setTypesFromSignature(meth, regTable.registerLines[0].regTypes,
   3520             vdata->uninitMap))
   3521         goto bail;
   3522 
   3523     /*
   3524      * Run the verifier.
   3525      */
   3526     if (!doCodeVerification(vdata, &regTable))
   3527         goto bail;
   3528 
   3529     /*
   3530      * Generate a register map.
   3531      */
   3532     if (generateRegisterMap) {
   3533         RegisterMap* pMap = dvmGenerateRegisterMapV(vdata);
   3534         if (pMap != NULL) {
   3535             /*
   3536              * Tuck it into the Method struct.  It will either get used
   3537              * directly or, if we're in dexopt, will be packed up and
   3538              * appended to the DEX file.
   3539              */
   3540             dvmSetRegisterMap((Method*)meth, pMap);
   3541         }
   3542     }
   3543 
   3544     /*
   3545      * Success.
   3546      */
   3547     result = true;
   3548 
   3549 bail:
   3550     freeRegisterLineInnards(vdata);
   3551     free(regTable.registerLines);
   3552     free(regTable.lineAlloc);
   3553     return result;
   3554 }
   3555 
   3556 /*
   3557  * Grind through the instructions.
   3558  *
   3559  * The basic strategy is as outlined in v3 4.11.1.2: set the "changed" bit
   3560  * on the first instruction, process it (setting additional "changed" bits),
   3561  * and repeat until there are no more.
   3562  *
   3563  * v3 4.11.1.1
   3564  * - (N/A) operand stack is always the same size
   3565  * - operand stack [registers] contain the correct types of values
   3566  * - local variables [registers] contain the correct types of values
   3567  * - methods are invoked with the appropriate arguments
   3568  * - fields are assigned using values of appropriate types
   3569  * - opcodes have the correct type values in operand registers
   3570  * - there is never an uninitialized class instance in a local variable in
   3571  *   code protected by an exception handler (operand stack is okay, because
   3572  *   the operand stack is discarded when an exception is thrown) [can't
   3573  *   know what's a local var w/o the debug info -- should fall out of
   3574  *   register typing]
   3575  *
   3576  * v3 4.11.1.2
   3577  * - execution cannot fall off the end of the code
   3578  *
   3579  * (We also do many of the items described in the "static checks" sections,
   3580  * because it's easier to do them here.)
   3581  *
   3582  * We need an array of RegType values, one per register, for every
   3583  * instruction.  If the method uses monitor-enter, we need extra data
   3584  * for every register, and a stack for every "interesting" instruction.
   3585  * In theory this could become quite large -- up to several megabytes for
   3586  * a monster function.
   3587  *
   3588  * NOTE:
   3589  * The spec forbids backward branches when there's an uninitialized reference
   3590  * in a register.  The idea is to prevent something like this:
   3591  *   loop:
   3592  *     move r1, r0
   3593  *     new-instance r0, MyClass
   3594  *     ...
   3595  *     if-eq rN, loop  // once
   3596  *   initialize r0
   3597  *
   3598  * This leaves us with two different instances, both allocated by the
   3599  * same instruction, but only one is initialized.  The scheme outlined in
   3600  * v3 4.11.1.4 wouldn't catch this, so they work around it by preventing
   3601  * backward branches.  We achieve identical results without restricting
   3602  * code reordering by specifying that you can't execute the new-instance
   3603  * instruction if a register contains an uninitialized instance created
   3604  * by that same instrutcion.
   3605  */
   3606 static bool doCodeVerification(VerifierData* vdata, RegisterTable* regTable)
   3607 {
   3608     const Method* meth = vdata->method;
   3609     InsnFlags* insnFlags = vdata->insnFlags;
   3610     UninitInstanceMap* uninitMap = vdata->uninitMap;
   3611     const int insnsSize = dvmGetMethodInsnsSize(meth);
   3612     bool result = false;
   3613     bool debugVerbose = false;
   3614     int insnIdx, startGuess;
   3615 
   3616     /*
   3617      * Begin by marking the first instruction as "changed".
   3618      */
   3619     dvmInsnSetChanged(insnFlags, 0, true);
   3620 
   3621     if (dvmWantVerboseVerification(meth)) {
   3622         IF_ALOGI() {
   3623             char* desc = dexProtoCopyMethodDescriptor(&meth->prototype);
   3624             ALOGI("Now verifying: %s.%s %s (ins=%d regs=%d)",
   3625                 meth->clazz->descriptor, meth->name, desc,
   3626                 meth->insSize, meth->registersSize);
   3627             ALOGI(" ------ [0    4    8    12   16   20   24   28   32   36");
   3628             free(desc);
   3629         }
   3630         debugVerbose = true;
   3631         gDebugVerbose = true;
   3632     } else {
   3633         gDebugVerbose = false;
   3634     }
   3635 
   3636     startGuess = 0;
   3637 
   3638     /*
   3639      * Continue until no instructions are marked "changed".
   3640      */
   3641     while (true) {
   3642         /*
   3643          * Find the first marked one.  Use "startGuess" as a way to find
   3644          * one quickly.
   3645          */
   3646         for (insnIdx = startGuess; insnIdx < insnsSize; insnIdx++) {
   3647             if (dvmInsnIsChanged(insnFlags, insnIdx))
   3648                 break;
   3649         }
   3650 
   3651         if (insnIdx == insnsSize) {
   3652             if (startGuess != 0) {
   3653                 /* try again, starting from the top */
   3654                 startGuess = 0;
   3655                 continue;
   3656             } else {
   3657                 /* all flags are clear */
   3658                 break;
   3659             }
   3660         }
   3661 
   3662         /*
   3663          * We carry the working set of registers from instruction to
   3664          * instruction.  If this address can be the target of a branch
   3665          * (or throw) instruction, or if we're skipping around chasing
   3666          * "changed" flags, we need to load the set of registers from
   3667          * the table.
   3668          *
   3669          * Because we always prefer to continue on to the next instruction,
   3670          * we should never have a situation where we have a stray
   3671          * "changed" flag set on an instruction that isn't a branch target.
   3672          */
   3673         if (dvmInsnIsBranchTarget(insnFlags, insnIdx)) {
   3674             RegisterLine* workLine = &regTable->workLine;
   3675 
   3676             copyLineFromTable(workLine, regTable, insnIdx);
   3677         } else {
   3678 #ifndef NDEBUG
   3679             /*
   3680              * Sanity check: retrieve the stored register line (assuming
   3681              * a full table) and make sure it actually matches.
   3682              */
   3683             RegisterLine* registerLine = getRegisterLine(regTable, insnIdx);
   3684             if (registerLine->regTypes != NULL &&
   3685                 compareLineToTable(regTable, insnIdx, &regTable->workLine) != 0)
   3686             {
   3687                 char* desc = dexProtoCopyMethodDescriptor(&meth->prototype);
   3688                 LOG_VFY("HUH? workLine diverged in %s.%s %s",
   3689                         meth->clazz->descriptor, meth->name, desc);
   3690                 free(desc);
   3691                 dumpRegTypes(vdata, registerLine, 0, "work",
   3692                     uninitMap, DRT_SHOW_REF_TYPES | DRT_SHOW_LOCALS);
   3693                 dumpRegTypes(vdata, registerLine, 0, "insn",
   3694                     uninitMap, DRT_SHOW_REF_TYPES | DRT_SHOW_LOCALS);
   3695             }
   3696 #endif
   3697         }
   3698         if (debugVerbose) {
   3699             dumpRegTypes(vdata, &regTable->workLine, insnIdx,
   3700                 NULL, uninitMap, SHOW_REG_DETAILS);
   3701         }
   3702 
   3703         //ALOGI("process %s.%s %s %d",
   3704         //    meth->clazz->descriptor, meth->name, meth->descriptor, insnIdx);
   3705         if (!verifyInstruction(meth, insnFlags, regTable, insnIdx,
   3706                 uninitMap, &startGuess))
   3707         {
   3708             //ALOGD("+++ %s bailing at %d", meth->name, insnIdx);
   3709             goto bail;
   3710         }
   3711 
   3712         /*
   3713          * Clear "changed" and mark as visited.
   3714          */
   3715         dvmInsnSetVisited(insnFlags, insnIdx, true);
   3716         dvmInsnSetChanged(insnFlags, insnIdx, false);
   3717     }
   3718 
   3719     if (DEAD_CODE_SCAN && !IS_METHOD_FLAG_SET(meth, METHOD_ISWRITABLE)) {
   3720         /*
   3721          * Scan for dead code.  There's nothing "evil" about dead code
   3722          * (besides the wasted space), but it indicates a flaw somewhere
   3723          * down the line, possibly in the verifier.
   3724          *
   3725          * If we've substituted "always throw" instructions into the stream,
   3726          * we are almost certainly going to have some dead code.
   3727          */
   3728         int deadStart = -1;
   3729         for (insnIdx = 0; insnIdx < insnsSize;
   3730             insnIdx += dvmInsnGetWidth(insnFlags, insnIdx))
   3731         {
   3732             /*
   3733              * Switch-statement data doesn't get "visited" by scanner.  It
   3734              * may or may not be preceded by a padding NOP (for alignment).
   3735              */
   3736             int instr = meth->insns[insnIdx];
   3737             if (instr == kPackedSwitchSignature ||
   3738                 instr == kSparseSwitchSignature ||
   3739                 instr == kArrayDataSignature ||
   3740                 (instr == OP_NOP && (insnIdx + 1 < insnsSize) &&
   3741                  (meth->insns[insnIdx+1] == kPackedSwitchSignature ||
   3742                   meth->insns[insnIdx+1] == kSparseSwitchSignature ||
   3743                   meth->insns[insnIdx+1] == kArrayDataSignature)))
   3744             {
   3745                 dvmInsnSetVisited(insnFlags, insnIdx, true);
   3746             }
   3747 
   3748             if (!dvmInsnIsVisited(insnFlags, insnIdx)) {
   3749                 if (deadStart < 0)
   3750                     deadStart = insnIdx;
   3751             } else if (deadStart >= 0) {
   3752                 IF_ALOGD() {
   3753                     char* desc =
   3754                         dexProtoCopyMethodDescriptor(&meth->prototype);
   3755                     ALOGD("VFY: dead code 0x%04x-%04x in %s.%s %s",
   3756                         deadStart, insnIdx-1,
   3757                         meth->clazz->descriptor, meth->name, desc);
   3758                     free(desc);
   3759                 }
   3760 
   3761                 deadStart = -1;
   3762             }
   3763         }
   3764         if (deadStart >= 0) {
   3765             IF_ALOGD() {
   3766                 char* desc = dexProtoCopyMethodDescriptor(&meth->prototype);
   3767                 ALOGD("VFY: dead code 0x%04x-%04x in %s.%s %s",
   3768                     deadStart, insnIdx-1,
   3769                     meth->clazz->descriptor, meth->name, desc);
   3770                 free(desc);
   3771             }
   3772         }
   3773     }
   3774 
   3775     result = true;
   3776 
   3777 bail:
   3778     return result;
   3779 }
   3780 
   3781 
   3782 /*
   3783  * Perform verification for a single instruction.
   3784  *
   3785  * This requires fully decoding the instruction to determine the effect
   3786  * it has on registers.
   3787  *
   3788  * Finds zero or more following instructions and sets the "changed" flag
   3789  * if execution at that point needs to be (re-)evaluated.  Register changes
   3790  * are merged into "regTypes" at the target addresses.  Does not set or
   3791  * clear any other flags in "insnFlags".
   3792  *
   3793  * This may alter meth->insns if we need to replace an instruction with
   3794  * throw-verification-error.
   3795  */
   3796 static bool verifyInstruction(const Method* meth, InsnFlags* insnFlags,
   3797     RegisterTable* regTable, int insnIdx, UninitInstanceMap* uninitMap,
   3798     int* pStartGuess)
   3799 {
   3800     const int insnsSize = dvmGetMethodInsnsSize(meth);
   3801     const u2* insns = meth->insns + insnIdx;
   3802     bool result = false;
   3803 
   3804 #ifdef VERIFIER_STATS
   3805     if (dvmInsnIsVisited(insnFlags, insnIdx)) {
   3806         gDvm.verifierStats.instrsReexamined++;
   3807     } else {
   3808         gDvm.verifierStats.instrsExamined++;
   3809     }
   3810 #endif
   3811 
   3812     /*
   3813      * Once we finish decoding the instruction, we need to figure out where
   3814      * we can go from here.  There are three possible ways to transfer
   3815      * control to another statement:
   3816      *
   3817      * (1) Continue to the next instruction.  Applies to all but
   3818      *     unconditional branches, method returns, and exception throws.
   3819      * (2) Branch to one or more possible locations.  Applies to branches
   3820      *     and switch statements.
   3821      * (3) Exception handlers.  Applies to any instruction that can
   3822      *     throw an exception that is handled by an encompassing "try"
   3823      *     block.
   3824      *
   3825      * We can also return, in which case there is no successor instruction
   3826      * from this point.
   3827      *
   3828      * The behavior can be determined from the OpcodeFlags.
   3829      */
   3830 
   3831     RegisterLine* workLine = &regTable->workLine;
   3832     const DexFile* pDexFile = meth->clazz->pDvmDex->pDexFile;
   3833     ClassObject* resClass;
   3834     s4 branchTarget = 0;
   3835     const int insnRegCount = meth->registersSize;
   3836     RegType tmpType;
   3837     DecodedInstruction decInsn;
   3838     bool justSetResult = false;
   3839     VerifyError failure = VERIFY_ERROR_NONE;
   3840 
   3841 #ifndef NDEBUG
   3842     memset(&decInsn, 0x81, sizeof(decInsn));
   3843 #endif
   3844     dexDecodeInstruction(insns, &decInsn);
   3845 
   3846     int nextFlags = dexGetFlagsFromOpcode(decInsn.opcode);
   3847 
   3848     /*
   3849      * Make a copy of the previous register state.  If the instruction
   3850      * can throw an exception, we will copy/merge this into the "catch"
   3851      * address rather than workLine, because we don't want the result
   3852      * from the "successful" code path (e.g. a check-cast that "improves"
   3853      * a type) to be visible to the exception handler.
   3854      */
   3855     if ((nextFlags & kInstrCanThrow) != 0 && dvmInsnIsInTry(insnFlags, insnIdx))
   3856     {
   3857         copyRegisterLine(&regTable->savedLine, workLine,
   3858             regTable->insnRegCountPlus);
   3859     } else {
   3860 #ifndef NDEBUG
   3861         memset(regTable->savedLine.regTypes, 0xdd,
   3862             regTable->insnRegCountPlus * sizeof(RegType));
   3863 #endif
   3864     }
   3865 
   3866     switch (decInsn.opcode) {
   3867     case OP_NOP:
   3868         /*
   3869          * A "pure" NOP has no effect on anything.  Data tables start with
   3870          * a signature that looks like a NOP; if we see one of these in
   3871          * the course of executing code then we have a problem.
   3872          */
   3873         if (decInsn.vA != 0) {
   3874             LOG_VFY("VFY: encountered data table in instruction stream");
   3875             failure = VERIFY_ERROR_GENERIC;
   3876         }
   3877         break;
   3878 
   3879     case OP_MOVE:
   3880     case OP_MOVE_FROM16:
   3881     case OP_MOVE_16:
   3882         copyRegister1(workLine, decInsn.vA, decInsn.vB, kTypeCategory1nr,
   3883             &failure);
   3884         break;
   3885     case OP_MOVE_WIDE:
   3886     case OP_MOVE_WIDE_FROM16:
   3887     case OP_MOVE_WIDE_16:
   3888         copyRegister2(workLine, decInsn.vA, decInsn.vB, &failure);
   3889         break;
   3890     case OP_MOVE_OBJECT:
   3891     case OP_MOVE_OBJECT_FROM16:
   3892     case OP_MOVE_OBJECT_16:
   3893         copyRegister1(workLine, decInsn.vA, decInsn.vB, kTypeCategoryRef,
   3894             &failure);
   3895         break;
   3896 
   3897     /*
   3898      * The move-result instructions copy data out of a "pseudo-register"
   3899      * with the results from the last method invocation.  In practice we
   3900      * might want to hold the result in an actual CPU register, so the
   3901      * Dalvik spec requires that these only appear immediately after an
   3902      * invoke or filled-new-array.
   3903      *
   3904      * These calls invalidate the "result" register.  (This is now
   3905      * redundant with the reset done below, but it can make the debug info
   3906      * easier to read in some cases.)
   3907      */
   3908     case OP_MOVE_RESULT:
   3909         copyResultRegister1(workLine, insnRegCount, decInsn.vA,
   3910             kTypeCategory1nr, &failure);
   3911         break;
   3912     case OP_MOVE_RESULT_WIDE:
   3913         copyResultRegister2(workLine, insnRegCount, decInsn.vA, &failure);
   3914         break;
   3915     case OP_MOVE_RESULT_OBJECT:
   3916         copyResultRegister1(workLine, insnRegCount, decInsn.vA,
   3917             kTypeCategoryRef, &failure);
   3918         break;
   3919 
   3920     case OP_MOVE_EXCEPTION:
   3921         /*
   3922          * This statement can only appear as the first instruction in an
   3923          * exception handler (though not all exception handlers need to
   3924          * have one of these).  We verify that as part of extracting the
   3925          * exception type from the catch block list.
   3926          *
   3927          * "resClass" will hold the closest common superclass of all
   3928          * exceptions that can be handled here.
   3929          */
   3930         resClass = getCaughtExceptionType(meth, insnIdx, &failure);
   3931         if (resClass == NULL) {
   3932             assert(!VERIFY_OK(failure));
   3933         } else {
   3934             setRegisterType(workLine, decInsn.vA, regTypeFromClass(resClass));
   3935         }
   3936         break;
   3937 
   3938     case OP_RETURN_VOID:
   3939         if (!checkConstructorReturn(meth, workLine, insnRegCount)) {
   3940             failure = VERIFY_ERROR_GENERIC;
   3941         } else if (getMethodReturnType(meth) != kRegTypeUnknown) {
   3942             LOG_VFY("VFY: return-void not expected");
   3943             failure = VERIFY_ERROR_GENERIC;
   3944         }
   3945         break;
   3946     case OP_RETURN:
   3947         if (!checkConstructorReturn(meth, workLine, insnRegCount)) {
   3948             failure = VERIFY_ERROR_GENERIC;
   3949         } else {
   3950             /* check the method signature */
   3951             RegType returnType = getMethodReturnType(meth);
   3952             checkTypeCategory(returnType, kTypeCategory1nr, &failure);
   3953             if (!VERIFY_OK(failure))
   3954                 LOG_VFY("VFY: return-1nr not expected");
   3955 
   3956             /*
   3957              * javac generates synthetic functions that write byte values
   3958              * into boolean fields. Also, it may use integer values for
   3959              * boolean, byte, short, and character return types.
   3960              */
   3961             RegType srcType = getRegisterType(workLine, decInsn.vA);
   3962             if ((returnType == kRegTypeBoolean && srcType == kRegTypeByte) ||
   3963                 ((returnType == kRegTypeBoolean || returnType == kRegTypeByte ||
   3964                   returnType == kRegTypeShort || returnType == kRegTypeChar) &&
   3965                  srcType == kRegTypeInteger))
   3966                 returnType = srcType;
   3967 
   3968             /* check the register contents */
   3969             verifyRegisterType(workLine, decInsn.vA, returnType, &failure);
   3970             if (!VERIFY_OK(failure)) {
   3971                 LOG_VFY("VFY: return-1nr on invalid register v%d",
   3972                     decInsn.vA);
   3973             }
   3974         }
   3975         break;
   3976     case OP_RETURN_WIDE:
   3977         if (!checkConstructorReturn(meth, workLine, insnRegCount)) {
   3978             failure = VERIFY_ERROR_GENERIC;
   3979         } else {
   3980             RegType returnType;
   3981 
   3982             /* check the method signature */
   3983             returnType = getMethodReturnType(meth);
   3984             checkTypeCategory(returnType, kTypeCategory2, &failure);
   3985             if (!VERIFY_OK(failure))
   3986                 LOG_VFY("VFY: return-wide not expected");
   3987 
   3988             /* check the register contents */
   3989             verifyRegisterType(workLine, decInsn.vA, returnType, &failure);
   3990             if (!VERIFY_OK(failure)) {
   3991                 LOG_VFY("VFY: return-wide on invalid register pair v%d",
   3992                     decInsn.vA);
   3993             }
   3994         }
   3995         break;
   3996     case OP_RETURN_OBJECT:
   3997         if (!checkConstructorReturn(meth, workLine, insnRegCount)) {
   3998             failure = VERIFY_ERROR_GENERIC;
   3999         } else {
   4000             RegType returnType = getMethodReturnType(meth);
   4001             checkTypeCategory(returnType, kTypeCategoryRef, &failure);
   4002             if (!VERIFY_OK(failure)) {
   4003                 LOG_VFY("VFY: return-object not expected");
   4004                 break;
   4005             }
   4006 
   4007             /* returnType is the *expected* return type, not register value */
   4008             assert(returnType != kRegTypeZero);
   4009             assert(!regTypeIsUninitReference(returnType));
   4010 
   4011             /*
   4012              * Verify that the reference in vAA is an instance of the type
   4013              * in "returnType".  The Zero type is allowed here.  If the
   4014              * method is declared to return an interface, then any
   4015              * initialized reference is acceptable.
   4016              *
   4017              * Note getClassFromRegister fails if the register holds an
   4018              * uninitialized reference, so we do not allow them to be
   4019              * returned.
   4020              */
   4021             ClassObject* declClass;
   4022 
   4023             declClass = regTypeInitializedReferenceToClass(returnType);
   4024             resClass = getClassFromRegister(workLine, decInsn.vA, &failure);
   4025             if (!VERIFY_OK(failure))
   4026                 break;
   4027             if (resClass != NULL) {
   4028                 if (!dvmIsInterfaceClass(declClass) &&
   4029                     !dvmInstanceof(resClass, declClass))
   4030                 {
   4031                     LOG_VFY("VFY: returning %s (cl=%p), declared %s (cl=%p)",
   4032                             resClass->descriptor, resClass->classLoader,
   4033                             declClass->descriptor, declClass->classLoader);
   4034                     failure = VERIFY_ERROR_GENERIC;
   4035                     break;
   4036                 }
   4037             }
   4038         }
   4039         break;
   4040 
   4041     case OP_CONST_4:
   4042     case OP_CONST_16:
   4043     case OP_CONST:
   4044         /* could be boolean, int, float, or a null reference */
   4045         setRegisterType(workLine, decInsn.vA,
   4046             determineCat1Const((s4)decInsn.vB));
   4047         break;
   4048     case OP_CONST_HIGH16:
   4049         /* could be boolean, int, float, or a null reference */
   4050         setRegisterType(workLine, decInsn.vA,
   4051             determineCat1Const((s4) decInsn.vB << 16));
   4052         break;
   4053     case OP_CONST_WIDE_16:
   4054     case OP_CONST_WIDE_32:
   4055     case OP_CONST_WIDE:
   4056     case OP_CONST_WIDE_HIGH16:
   4057         /* could be long or double; resolved upon use */
   4058         setRegisterType(workLine, decInsn.vA, kRegTypeConstLo);
   4059         break;
   4060     case OP_CONST_STRING:
   4061     case OP_CONST_STRING_JUMBO:
   4062         assert(gDvm.classJavaLangString != NULL);
   4063         setRegisterType(workLine, decInsn.vA,
   4064             regTypeFromClass(gDvm.classJavaLangString));
   4065         break;
   4066     case OP_CONST_CLASS:
   4067         assert(gDvm.classJavaLangClass != NULL);
   4068         /* make sure we can resolve the class; access check is important */
   4069         resClass = dvmOptResolveClass(meth->clazz, decInsn.vB, &failure);
   4070         if (resClass == NULL) {
   4071             const char* badClassDesc = dexStringByTypeIdx(pDexFile, decInsn.vB);
   4072             dvmLogUnableToResolveClass(badClassDesc, meth);
   4073             LOG_VFY("VFY: unable to resolve const-class %d (%s) in %s",
   4074                 decInsn.vB, badClassDesc, meth->clazz->descriptor);
   4075             assert(failure != VERIFY_ERROR_GENERIC);
   4076         } else {
   4077             setRegisterType(workLine, decInsn.vA,
   4078                 regTypeFromClass(gDvm.classJavaLangClass));
   4079         }
   4080         break;
   4081 
   4082     case OP_MONITOR_ENTER:
   4083         handleMonitorEnter(workLine, decInsn.vA, insnIdx, &failure);
   4084         break;
   4085     case OP_MONITOR_EXIT:
   4086         /*
   4087          * monitor-exit instructions are odd.  They can throw exceptions,
   4088          * but when they do they act as if they succeeded and the PC is
   4089          * pointing to the following instruction.  (This behavior goes back
   4090          * to the need to handle asynchronous exceptions, a now-deprecated
   4091          * feature that Dalvik doesn't support.)
   4092          *
   4093          * In practice we don't need to worry about this.  The only
   4094          * exceptions that can be thrown from monitor-exit are for a
   4095          * null reference and -exit without a matching -enter.  If the
   4096          * structured locking checks are working, the former would have
   4097          * failed on the -enter instruction, and the latter is impossible.
   4098          *
   4099          * This is fortunate, because issue 3221411 prevents us from
   4100          * chasing the "can throw" path when monitor verification is
   4101          * enabled.  If we can fully verify the locking we can ignore
   4102          * some catch blocks (which will show up as "dead" code when
   4103          * we skip them here); if we can't, then the code path could be
   4104          * "live" so we still need to check it.
   4105          */
   4106         if (workLine->monitorEntries != NULL)
   4107             nextFlags &= ~kInstrCanThrow;
   4108         handleMonitorExit(workLine, decInsn.vA, insnIdx, &failure);
   4109         break;
   4110 
   4111     case OP_CHECK_CAST:
   4112         /*
   4113          * If this instruction succeeds, we will promote register vA to
   4114          * the type in vB.  (This could be a demotion -- not expected, so
   4115          * we don't try to address it.)
   4116          *
   4117          * If it fails, an exception is thrown, which we deal with later
   4118          * by ignoring the update to decInsn.vA when branching to a handler.
   4119          */
   4120         resClass = dvmOptResolveClass(meth->clazz, decInsn.vB, &failure);
   4121         if (resClass == NULL) {
   4122             const char* badClassDesc = dexStringByTypeIdx(pDexFile, decInsn.vB);
   4123             dvmLogUnableToResolveClass(badClassDesc, meth);
   4124             LOG_VFY("VFY: unable to resolve check-cast %d (%s) in %s",
   4125                 decInsn.vB, badClassDesc, meth->clazz->descriptor);
   4126             assert(failure != VERIFY_ERROR_GENERIC);
   4127         } else {
   4128             RegType origType;
   4129 
   4130             origType = getRegisterType(workLine, decInsn.vA);
   4131             if (!regTypeIsReference(origType)) {
   4132                 LOG_VFY("VFY: check-cast on non-reference in v%u",decInsn.vA);
   4133                 failure = VERIFY_ERROR_GENERIC;
   4134                 break;
   4135             }
   4136             setRegisterType(workLine, decInsn.vA, regTypeFromClass(resClass));
   4137         }
   4138         break;
   4139     case OP_INSTANCE_OF:
   4140         /* make sure we're checking a reference type */
   4141         tmpType = getRegisterType(workLine, decInsn.vB);
   4142         if (!regTypeIsReference(tmpType)) {
   4143             LOG_VFY("VFY: vB not a reference (%d)", tmpType);
   4144             failure = VERIFY_ERROR_GENERIC;
   4145             break;
   4146         }
   4147 
   4148         /* make sure we can resolve the class; access check is important */
   4149         resClass = dvmOptResolveClass(meth->clazz, decInsn.vC, &failure);
   4150         if (resClass == NULL) {
   4151             const char* badClassDesc = dexStringByTypeIdx(pDexFile, decInsn.vC);
   4152             dvmLogUnableToResolveClass(badClassDesc, meth);
   4153             LOG_VFY("VFY: unable to resolve instanceof %d (%s) in %s",
   4154                 decInsn.vC, badClassDesc, meth->clazz->descriptor);
   4155             assert(failure != VERIFY_ERROR_GENERIC);
   4156         } else {
   4157             /* result is boolean */
   4158             setRegisterType(workLine, decInsn.vA, kRegTypeBoolean);
   4159         }
   4160         break;
   4161 
   4162     case OP_ARRAY_LENGTH:
   4163         resClass = getClassFromRegister(workLine, decInsn.vB, &failure);
   4164         if (!VERIFY_OK(failure))
   4165             break;
   4166         if (resClass != NULL && !dvmIsArrayClass(resClass)) {
   4167             LOG_VFY("VFY: array-length on non-array");
   4168             failure = VERIFY_ERROR_GENERIC;
   4169             break;
   4170         }
   4171         setRegisterType(workLine, decInsn.vA, kRegTypeInteger);
   4172         break;
   4173 
   4174     case OP_NEW_INSTANCE:
   4175         resClass = dvmOptResolveClass(meth->clazz, decInsn.vB, &failure);
   4176         if (resClass == NULL) {
   4177             const char* badClassDesc = dexStringByTypeIdx(pDexFile, decInsn.vB);
   4178             dvmLogUnableToResolveClass(badClassDesc, meth);
   4179             LOG_VFY("VFY: unable to resolve new-instance %d (%s) in %s",
   4180                 decInsn.vB, badClassDesc, meth->clazz->descriptor);
   4181             assert(failure != VERIFY_ERROR_GENERIC);
   4182         } else {
   4183             RegType uninitType;
   4184 
   4185             /* can't create an instance of an interface or abstract class */
   4186             if (dvmIsAbstractClass(resClass) || dvmIsInterfaceClass(resClass)) {
   4187                 LOG_VFY("VFY: new-instance on interface or abstract class %s",
   4188                     resClass->descriptor);
   4189                 failure = VERIFY_ERROR_INSTANTIATION;
   4190                 break;
   4191             }
   4192 
   4193             /* add resolved class to uninit map if not already there */
   4194             int uidx = setUninitInstance(uninitMap, insnIdx, resClass);
   4195             assert(uidx >= 0);
   4196             uninitType = regTypeFromUninitIndex(uidx);
   4197 
   4198             /*
   4199              * Any registers holding previous allocations from this address
   4200              * that have not yet been initialized must be marked invalid.
   4201              */
   4202             markUninitRefsAsInvalid(workLine, insnRegCount, uninitMap,
   4203                 uninitType);
   4204 
   4205             /* add the new uninitialized reference to the register ste */
   4206             setRegisterType(workLine, decInsn.vA, uninitType);
   4207         }
   4208         break;
   4209     case OP_NEW_ARRAY:
   4210         resClass = dvmOptResolveClass(meth->clazz, decInsn.vC, &failure);
   4211         if (resClass == NULL) {
   4212             const char* badClassDesc = dexStringByTypeIdx(pDexFile, decInsn.vC);
   4213             dvmLogUnableToResolveClass(badClassDesc, meth);
   4214             LOG_VFY("VFY: unable to resolve new-array %d (%s) in %s",
   4215                 decInsn.vC, badClassDesc, meth->clazz->descriptor);
   4216             assert(failure != VERIFY_ERROR_GENERIC);
   4217         } else if (!dvmIsArrayClass(resClass)) {
   4218             LOG_VFY("VFY: new-array on non-array class");
   4219             failure = VERIFY_ERROR_GENERIC;
   4220         } else {
   4221             /* make sure "size" register is valid type */
   4222             verifyRegisterType(workLine, decInsn.vB, kRegTypeInteger, &failure);
   4223             /* set register type to array class */
   4224             setRegisterType(workLine, decInsn.vA, regTypeFromClass(resClass));
   4225         }
   4226         break;
   4227     case OP_FILLED_NEW_ARRAY:
   4228     case OP_FILLED_NEW_ARRAY_RANGE:
   4229         resClass = dvmOptResolveClass(meth->clazz, decInsn.vB, &failure);
   4230         if (resClass == NULL) {
   4231             const char* badClassDesc = dexStringByTypeIdx(pDexFile, decInsn.vB);
   4232             dvmLogUnableToResolveClass(badClassDesc, meth);
   4233             LOG_VFY("VFY: unable to resolve filled-array %d (%s) in %s",
   4234                 decInsn.vB, badClassDesc, meth->clazz->descriptor);
   4235             assert(failure != VERIFY_ERROR_GENERIC);
   4236         } else if (!dvmIsArrayClass(resClass)) {
   4237             LOG_VFY("VFY: filled-new-array on non-array class");
   4238             failure = VERIFY_ERROR_GENERIC;
   4239         } else {
   4240             bool isRange = (decInsn.opcode == OP_FILLED_NEW_ARRAY_RANGE);
   4241 
   4242             /* check the arguments to the instruction */
   4243             verifyFilledNewArrayRegs(meth, workLine, &decInsn,
   4244                 resClass, isRange, &failure);
   4245             /* filled-array result goes into "result" register */
   4246             setResultRegisterType(workLine, insnRegCount,
   4247                 regTypeFromClass(resClass));
   4248             justSetResult = true;
   4249         }
   4250         break;
   4251 
   4252     case OP_CMPL_FLOAT:
   4253     case OP_CMPG_FLOAT:
   4254         verifyRegisterType(workLine, decInsn.vB, kRegTypeFloat, &failure);
   4255         verifyRegisterType(workLine, decInsn.vC, kRegTypeFloat, &failure);
   4256         setRegisterType(workLine, decInsn.vA, kRegTypeBoolean);
   4257         break;
   4258     case OP_CMPL_DOUBLE:
   4259     case OP_CMPG_DOUBLE:
   4260         verifyRegisterType(workLine, decInsn.vB, kRegTypeDoubleLo, &failure);
   4261         verifyRegisterType(workLine, decInsn.vC, kRegTypeDoubleLo, &failure);
   4262         setRegisterType(workLine, decInsn.vA, kRegTypeBoolean);
   4263         break;
   4264     case OP_CMP_LONG:
   4265         verifyRegisterType(workLine, decInsn.vB, kRegTypeLongLo, &failure);
   4266         verifyRegisterType(workLine, decInsn.vC, kRegTypeLongLo, &failure);
   4267         setRegisterType(workLine, decInsn.vA, kRegTypeBoolean);
   4268         break;
   4269 
   4270     case OP_THROW:
   4271         resClass = getClassFromRegister(workLine, decInsn.vA, &failure);
   4272         if (VERIFY_OK(failure) && resClass != NULL) {
   4273             if (!dvmInstanceof(resClass, gDvm.exThrowable)) {
   4274                 LOG_VFY("VFY: thrown class %s not instanceof Throwable",
   4275                         resClass->descriptor);
   4276                 failure = VERIFY_ERROR_GENERIC;
   4277             }
   4278         }
   4279         break;
   4280 
   4281     case OP_GOTO:
   4282     case OP_GOTO_16:
   4283     case OP_GOTO_32:
   4284         /* no effect on or use of registers */
   4285         break;
   4286 
   4287     case OP_PACKED_SWITCH:
   4288     case OP_SPARSE_SWITCH:
   4289         /* verify that vAA is an integer, or can be converted to one */
   4290         verifyRegisterType(workLine, decInsn.vA, kRegTypeInteger, &failure);
   4291         break;
   4292 
   4293     case OP_FILL_ARRAY_DATA:
   4294         {
   4295             RegType valueType;
   4296             const u2 *arrayData;
   4297             u2 elemWidth;
   4298 
   4299             /* Similar to the verification done for APUT */
   4300             resClass = getClassFromRegister(workLine, decInsn.vA, &failure);
   4301             if (!VERIFY_OK(failure))
   4302                 break;
   4303 
   4304             /* resClass can be null if the reg type is Zero */
   4305             if (resClass == NULL)
   4306                 break;
   4307 
   4308             if (!dvmIsArrayClass(resClass) || resClass->arrayDim != 1 ||
   4309                 resClass->elementClass->primitiveType == PRIM_NOT ||
   4310                 resClass->elementClass->primitiveType == PRIM_VOID)
   4311             {
   4312                 LOG_VFY("VFY: invalid fill-array-data on %s",
   4313                         resClass->descriptor);
   4314                 failure = VERIFY_ERROR_GENERIC;
   4315                 break;
   4316             }
   4317 
   4318             valueType = primitiveTypeToRegType(
   4319                                     resClass->elementClass->primitiveType);
   4320             assert(valueType != kRegTypeUnknown);
   4321 
   4322             /*
   4323              * Now verify if the element width in the table matches the element
   4324              * width declared in the array
   4325              */
   4326             arrayData = insns + (insns[1] | (((s4)insns[2]) << 16));
   4327             if (arrayData[0] != kArrayDataSignature) {
   4328                 LOG_VFY("VFY: invalid magic for array-data");
   4329                 failure = VERIFY_ERROR_GENERIC;
   4330                 break;
   4331             }
   4332 
   4333             switch (resClass->elementClass->primitiveType) {
   4334                 case PRIM_BOOLEAN:
   4335                 case PRIM_BYTE:
   4336                      elemWidth = 1;
   4337                      break;
   4338                 case PRIM_CHAR:
   4339                 case PRIM_SHORT:
   4340                      elemWidth = 2;
   4341                      break;
   4342                 case PRIM_FLOAT:
   4343                 case PRIM_INT:
   4344                      elemWidth = 4;
   4345                      break;
   4346                 case PRIM_DOUBLE:
   4347                 case PRIM_LONG:
   4348                      elemWidth = 8;
   4349                      break;
   4350                 default:
   4351                      elemWidth = 0;
   4352                      break;
   4353             }
   4354 
   4355             /*
   4356              * Since we don't compress the data in Dex, expect to see equal
   4357              * width of data stored in the table and expected from the array
   4358              * class.
   4359              */
   4360             if (arrayData[1] != elemWidth) {
   4361                 LOG_VFY("VFY: array-data size mismatch (%d vs %d)",
   4362                         arrayData[1], elemWidth);
   4363                 failure = VERIFY_ERROR_GENERIC;
   4364             }
   4365         }
   4366         break;
   4367 
   4368     case OP_IF_EQ:
   4369     case OP_IF_NE:
   4370         {
   4371             RegType type1, type2;
   4372 
   4373             type1 = getRegisterType(workLine, decInsn.vA);
   4374             type2 = getRegisterType(workLine, decInsn.vB);
   4375 
   4376             /* both references? */
   4377             if (regTypeIsReference(type1) && regTypeIsReference(type2))
   4378                 break;
   4379 
   4380             /* both category-1nr? */
   4381             checkTypeCategory(type1, kTypeCategory1nr, &failure);
   4382             checkTypeCategory(type2, kTypeCategory1nr, &failure);
   4383             if (type1 == kRegTypeFloat || type2 == kRegTypeFloat) {
   4384               failure = VERIFY_ERROR_GENERIC;
   4385             }
   4386             if (!VERIFY_OK(failure)) {
   4387                 LOG_VFY("VFY: args to if-eq/if-ne must both be refs or cat1");
   4388                 break;
   4389             }
   4390         }
   4391         break;
   4392     case OP_IF_LT:
   4393     case OP_IF_GE:
   4394     case OP_IF_GT:
   4395     case OP_IF_LE:
   4396         tmpType = getRegisterType(workLine, decInsn.vA);
   4397         checkTypeCategory(tmpType, kTypeCategory1nr, &failure);
   4398         if (tmpType == kRegTypeFloat) {
   4399           failure = VERIFY_ERROR_GENERIC;
   4400         }
   4401         if (!VERIFY_OK(failure)) {
   4402             LOG_VFY("VFY: args to 'if' must be cat-1nr and not float");
   4403             break;
   4404         }
   4405         tmpType = getRegisterType(workLine, decInsn.vB);
   4406         checkTypeCategory(tmpType, kTypeCategory1nr, &failure);
   4407         if (tmpType == kRegTypeFloat) {
   4408           failure = VERIFY_ERROR_GENERIC;
   4409         }
   4410         if (!VERIFY_OK(failure)) {
   4411             LOG_VFY("VFY: args to 'if' must be cat-1nr and not float");
   4412             break;
   4413         }
   4414         break;
   4415     case OP_IF_EQZ:
   4416     case OP_IF_NEZ:
   4417         tmpType = getRegisterType(workLine, decInsn.vA);
   4418         if (regTypeIsReference(tmpType))
   4419             break;
   4420         checkTypeCategory(tmpType, kTypeCategory1nr, &failure);
   4421         if (tmpType == kRegTypeFloat) {
   4422           failure = VERIFY_ERROR_GENERIC;
   4423         }
   4424         if (!VERIFY_OK(failure))
   4425             LOG_VFY("VFY: expected non-float cat-1 arg to if");
   4426         break;
   4427     case OP_IF_LTZ:
   4428     case OP_IF_GEZ:
   4429     case OP_IF_GTZ:
   4430     case OP_IF_LEZ:
   4431         tmpType = getRegisterType(workLine, decInsn.vA);
   4432         checkTypeCategory(tmpType, kTypeCategory1nr, &failure);
   4433         if (tmpType == kRegTypeFloat) {
   4434           failure = VERIFY_ERROR_GENERIC;
   4435         }
   4436         if (!VERIFY_OK(failure))
   4437             LOG_VFY("VFY: expected non-float cat-1 arg to if");
   4438         break;
   4439 
   4440     case OP_AGET:
   4441         tmpType = kRegTypeInteger;
   4442         goto aget_1nr_common;
   4443     case OP_AGET_BOOLEAN:
   4444         tmpType = kRegTypeBoolean;
   4445         goto aget_1nr_common;
   4446     case OP_AGET_BYTE:
   4447         tmpType = kRegTypeByte;
   4448         goto aget_1nr_common;
   4449     case OP_AGET_CHAR:
   4450         tmpType = kRegTypeChar;
   4451         goto aget_1nr_common;
   4452     case OP_AGET_SHORT:
   4453         tmpType = kRegTypeShort;
   4454         goto aget_1nr_common;
   4455 aget_1nr_common:
   4456         {
   4457             RegType srcType, indexType;
   4458 
   4459             indexType = getRegisterType(workLine, decInsn.vC);
   4460             checkArrayIndexType(meth, indexType, &failure);
   4461             if (!VERIFY_OK(failure))
   4462                 break;
   4463 
   4464             resClass = getClassFromRegister(workLine, decInsn.vB, &failure);
   4465             if (!VERIFY_OK(failure))
   4466                 break;
   4467             if (resClass != NULL) {
   4468                 /* verify the class */
   4469                 if (!dvmIsArrayClass(resClass) || resClass->arrayDim != 1 ||
   4470                     resClass->elementClass->primitiveType == PRIM_NOT)
   4471                 {
   4472                     LOG_VFY("VFY: invalid aget-1nr target %s",
   4473                         resClass->descriptor);
   4474                     failure = VERIFY_ERROR_GENERIC;
   4475                     break;
   4476                 }
   4477 
   4478                 /* make sure array type matches instruction */
   4479                 srcType = primitiveTypeToRegType(
   4480                                         resClass->elementClass->primitiveType);
   4481 
   4482                 /* correct if float */
   4483                 if (srcType == kRegTypeFloat && tmpType == kRegTypeInteger)
   4484                     tmpType = kRegTypeFloat;
   4485 
   4486                 if (!checkFieldArrayStore1nr(tmpType, srcType)) {
   4487                     LOG_VFY("VFY: invalid aget-1nr, array type=%d with"
   4488                             " inst type=%d (on %s)",
   4489                         srcType, tmpType, resClass->descriptor);
   4490                     failure = VERIFY_ERROR_GENERIC;
   4491                     break;
   4492                 }
   4493             } else {
   4494                 /*
   4495                  * Null array ref; this code path will fail at runtime. Label
   4496                  * result as zero to allow it to remain mergeable.
   4497                  */
   4498                 tmpType = kRegTypeZero;
   4499             }
   4500             setRegisterType(workLine, decInsn.vA, tmpType);
   4501         }
   4502         break;
   4503 
   4504     case OP_AGET_WIDE:
   4505         {
   4506             RegType dstType, indexType;
   4507 
   4508             indexType = getRegisterType(workLine, decInsn.vC);
   4509             checkArrayIndexType(meth, indexType, &failure);
   4510             if (!VERIFY_OK(failure))
   4511                 break;
   4512 
   4513             resClass = getClassFromRegister(workLine, decInsn.vB, &failure);
   4514             if (!VERIFY_OK(failure))
   4515                 break;
   4516             if (resClass != NULL) {
   4517                 /* verify the class */
   4518                 if (!dvmIsArrayClass(resClass) || resClass->arrayDim != 1 ||
   4519                     resClass->elementClass->primitiveType == PRIM_NOT)
   4520                 {
   4521                     LOG_VFY("VFY: invalid aget-wide target %s",
   4522                         resClass->descriptor);
   4523                     failure = VERIFY_ERROR_GENERIC;
   4524                     break;
   4525                 }
   4526 
   4527                 /* try to refine "dstType" */
   4528                 switch (resClass->elementClass->primitiveType) {
   4529                 case PRIM_LONG:
   4530                     dstType = kRegTypeLongLo;
   4531                     break;
   4532                 case PRIM_DOUBLE:
   4533                     dstType = kRegTypeDoubleLo;
   4534                     break;
   4535                 default:
   4536                     LOG_VFY("VFY: invalid aget-wide on %s",
   4537                         resClass->descriptor);
   4538                     dstType = kRegTypeUnknown;
   4539                     failure = VERIFY_ERROR_GENERIC;
   4540                     break;
   4541                 }
   4542             } else {
   4543                 /*
   4544                  * Null array ref; this code path will fail at runtime.  We
   4545                  * know this is either long or double, so label it const.
   4546                  */
   4547                 dstType = kRegTypeConstLo;
   4548             }
   4549             setRegisterType(workLine, decInsn.vA, dstType);
   4550         }
   4551         break;
   4552 
   4553     case OP_AGET_OBJECT:
   4554         {
   4555             RegType dstType, indexType;
   4556 
   4557             indexType = getRegisterType(workLine, decInsn.vC);
   4558             checkArrayIndexType(meth, indexType, &failure);
   4559             if (!VERIFY_OK(failure))
   4560                 break;
   4561 
   4562             /* get the class of the array we're pulling an object from */
   4563             resClass = getClassFromRegister(workLine, decInsn.vB, &failure);
   4564             if (!VERIFY_OK(failure))
   4565                 break;
   4566             if (resClass != NULL) {
   4567                 ClassObject* elementClass;
   4568 
   4569                 assert(resClass != NULL);
   4570                 if (!dvmIsArrayClass(resClass)) {
   4571                     LOG_VFY("VFY: aget-object on non-array class");
   4572                     failure = VERIFY_ERROR_GENERIC;
   4573                     break;
   4574                 }
   4575                 assert(resClass->elementClass != NULL);
   4576 
   4577                 /*
   4578                  * Find the element class.  resClass->elementClass indicates
   4579                  * the basic type, which won't be what we want for a
   4580                  * multi-dimensional array.
   4581                  */
   4582                 if (resClass->descriptor[1] == '[') {
   4583                     assert(resClass->arrayDim > 1);
   4584                     elementClass = dvmFindArrayClass(&resClass->descriptor[1],
   4585                                         resClass->classLoader);
   4586                 } else if (resClass->descriptor[1] == 'L') {
   4587                     assert(resClass->arrayDim == 1);
   4588                     elementClass = resClass->elementClass;
   4589                 } else {
   4590                     LOG_VFY("VFY: aget-object on non-ref array class (%s)",
   4591                         resClass->descriptor);
   4592                     failure = VERIFY_ERROR_GENERIC;
   4593                     break;
   4594                 }
   4595 
   4596                 dstType = regTypeFromClass(elementClass);
   4597             } else {
   4598                 /*
   4599                  * The array reference is NULL, so the current code path will
   4600                  * throw an exception.  For proper merging with later code
   4601                  * paths, and correct handling of "if-eqz" tests on the
   4602                  * result of the array get, we want to treat this as a null
   4603                  * reference.
   4604                  */
   4605                 dstType = kRegTypeZero;
   4606             }
   4607             setRegisterType(workLine, decInsn.vA, dstType);
   4608         }
   4609         break;
   4610     case OP_APUT:
   4611         tmpType = kRegTypeInteger;
   4612         goto aput_1nr_common;
   4613     case OP_APUT_BOOLEAN:
   4614         tmpType = kRegTypeBoolean;
   4615         goto aput_1nr_common;
   4616     case OP_APUT_BYTE:
   4617         tmpType = kRegTypeByte;
   4618         goto aput_1nr_common;
   4619     case OP_APUT_CHAR:
   4620         tmpType = kRegTypeChar;
   4621         goto aput_1nr_common;
   4622     case OP_APUT_SHORT:
   4623         tmpType = kRegTypeShort;
   4624         goto aput_1nr_common;
   4625 aput_1nr_common:
   4626         {
   4627             RegType srcType, dstType, indexType;
   4628 
   4629             indexType = getRegisterType(workLine, decInsn.vC);
   4630             checkArrayIndexType(meth, indexType, &failure);
   4631             if (!VERIFY_OK(failure))
   4632                 break;
   4633 
   4634             srcType = getRegisterType(workLine, decInsn.vA);
   4635 
   4636             /* correct if float */
   4637             if (srcType == kRegTypeFloat && tmpType == kRegTypeInteger)
   4638                 tmpType = kRegTypeFloat;
   4639 
   4640             /* make sure the source register has the correct type */
   4641             if (!canConvertTo1nr(srcType, tmpType)) {
   4642                 LOG_VFY("VFY: invalid reg type %d on aput instr (need %d)",
   4643                     srcType, tmpType);
   4644                 failure = VERIFY_ERROR_GENERIC;
   4645                 break;
   4646             }
   4647 
   4648             resClass = getClassFromRegister(workLine, decInsn.vB, &failure);
   4649             if (!VERIFY_OK(failure))
   4650                 break;
   4651 
   4652             /* resClass can be null if the reg type is Zero */
   4653             if (resClass == NULL)
   4654                 break;
   4655 
   4656             if (!dvmIsArrayClass(resClass) || resClass->arrayDim != 1 ||
   4657                 resClass->elementClass->primitiveType == PRIM_NOT)
   4658             {
   4659                 LOG_VFY("VFY: invalid aput-1nr on %s", resClass->descriptor);
   4660                 failure = VERIFY_ERROR_GENERIC;
   4661                 break;
   4662             }
   4663 
   4664             /* verify that instruction matches array */
   4665             dstType = primitiveTypeToRegType(
   4666                                     resClass->elementClass->primitiveType);
   4667 
   4668             /* correct if float */
   4669             if (dstType == kRegTypeFloat && tmpType == kRegTypeInteger)
   4670                 tmpType = kRegTypeFloat;
   4671 
   4672             verifyRegisterType(workLine, decInsn.vA, dstType, &failure);
   4673 
   4674             if (dstType == kRegTypeUnknown ||
   4675                 !checkFieldArrayStore1nr(tmpType, dstType)) {
   4676                 LOG_VFY("VFY: invalid aput-1nr on %s (inst=%d dst=%d)",
   4677                         resClass->descriptor, tmpType, dstType);
   4678                 failure = VERIFY_ERROR_GENERIC;
   4679                 break;
   4680             }
   4681         }
   4682         break;
   4683     case OP_APUT_WIDE:
   4684         tmpType = getRegisterType(workLine, decInsn.vC);
   4685         checkArrayIndexType(meth, tmpType, &failure);
   4686         if (!VERIFY_OK(failure))
   4687             break;
   4688 
   4689         resClass = getClassFromRegister(workLine, decInsn.vB, &failure);
   4690         if (!VERIFY_OK(failure))
   4691             break;
   4692         if (resClass != NULL) {
   4693             /* verify the class and try to refine "dstType" */
   4694             if (!dvmIsArrayClass(resClass) || resClass->arrayDim != 1 ||
   4695                 resClass->elementClass->primitiveType == PRIM_NOT)
   4696             {
   4697                 LOG_VFY("VFY: invalid aput-wide on %s",
   4698                         resClass->descriptor);
   4699                 failure = VERIFY_ERROR_GENERIC;
   4700                 break;
   4701             }
   4702 
   4703             switch (resClass->elementClass->primitiveType) {
   4704             case PRIM_LONG:
   4705                 verifyRegisterType(workLine, decInsn.vA, kRegTypeLongLo, &failure);
   4706                 break;
   4707             case PRIM_DOUBLE:
   4708                 verifyRegisterType(workLine, decInsn.vA, kRegTypeDoubleLo, &failure);
   4709                 break;
   4710             default:
   4711                 LOG_VFY("VFY: invalid aput-wide on %s",
   4712                         resClass->descriptor);
   4713                 failure = VERIFY_ERROR_GENERIC;
   4714                 break;
   4715             }
   4716         }
   4717         break;
   4718     case OP_APUT_OBJECT:
   4719         tmpType = getRegisterType(workLine, decInsn.vC);
   4720         checkArrayIndexType(meth, tmpType, &failure);
   4721         if (!VERIFY_OK(failure))
   4722             break;
   4723 
   4724         /* get the ref we're storing; Zero is okay, Uninit is not */
   4725         resClass = getClassFromRegister(workLine, decInsn.vA, &failure);
   4726         if (!VERIFY_OK(failure))
   4727             break;
   4728         if (resClass != NULL) {
   4729             ClassObject* arrayClass;
   4730             ClassObject* elementClass;
   4731 
   4732             /*
   4733              * Get the array class.  If the array ref is null, we won't
   4734              * have type information (and we'll crash at runtime with a
   4735              * null pointer exception).
   4736              */
   4737             arrayClass = getClassFromRegister(workLine, decInsn.vB, &failure);
   4738 
   4739             if (arrayClass != NULL) {
   4740                 /* see if the array holds a compatible type */
   4741                 if (!dvmIsArrayClass(arrayClass)) {
   4742                     LOG_VFY("VFY: invalid aput-object on %s",
   4743                             arrayClass->descriptor);
   4744                     failure = VERIFY_ERROR_GENERIC;
   4745                     break;
   4746                 }
   4747 
   4748                 /*
   4749                  * Find the element class.  resClass->elementClass indicates
   4750                  * the basic type, which won't be what we want for a
   4751                  * multi-dimensional array.
   4752                  *
   4753                  * All we want to check here is that the element type is a
   4754                  * reference class.  We *don't* check instanceof here, because
   4755                  * you can still put a String into a String[] after the latter
   4756                  * has been cast to an Object[].
   4757                  */
   4758                 if (arrayClass->descriptor[1] == '[') {
   4759                     assert(arrayClass->arrayDim > 1);
   4760                     elementClass = dvmFindArrayClass(&arrayClass->descriptor[1],
   4761                                         arrayClass->classLoader);
   4762                 } else {
   4763                     assert(arrayClass->arrayDim == 1);
   4764                     elementClass = arrayClass->elementClass;
   4765                 }
   4766                 if (elementClass->primitiveType != PRIM_NOT) {
   4767                     LOG_VFY("VFY: invalid aput-object of %s into %s",
   4768                             resClass->descriptor, arrayClass->descriptor);
   4769                     failure = VERIFY_ERROR_GENERIC;
   4770                     break;
   4771                 }
   4772             }
   4773         }
   4774         break;
   4775 
   4776     case OP_IGET:
   4777         tmpType = kRegTypeInteger;
   4778         goto iget_1nr_common;
   4779     case OP_IGET_BOOLEAN:
   4780         tmpType = kRegTypeBoolean;
   4781         goto iget_1nr_common;
   4782     case OP_IGET_BYTE:
   4783         tmpType = kRegTypeByte;
   4784         goto iget_1nr_common;
   4785     case OP_IGET_CHAR:
   4786         tmpType = kRegTypeChar;
   4787         goto iget_1nr_common;
   4788     case OP_IGET_SHORT:
   4789         tmpType = kRegTypeShort;
   4790         goto iget_1nr_common;
   4791 iget_1nr_common:
   4792         {
   4793             InstField* instField;
   4794             RegType objType, fieldType;
   4795 
   4796             objType = getRegisterType(workLine, decInsn.vB);
   4797             instField = getInstField(meth, uninitMap, objType, decInsn.vC,
   4798                             &failure);
   4799             if (!VERIFY_OK(failure))
   4800                 break;
   4801 
   4802             /* make sure the field's type is compatible with expectation */
   4803             fieldType = primSigCharToRegType(instField->signature[0]);
   4804 
   4805             /* correct if float */
   4806             if (fieldType == kRegTypeFloat && tmpType == kRegTypeInteger)
   4807                 tmpType = kRegTypeFloat;
   4808 
   4809             if (fieldType == kRegTypeUnknown ||
   4810                 !checkFieldArrayStore1nr(tmpType, fieldType))
   4811             {
   4812                 LOG_VFY("VFY: invalid iget-1nr of %s.%s (inst=%d field=%d)",
   4813                         instField->clazz->descriptor,
   4814                         instField->name, tmpType, fieldType);
   4815                 failure = VERIFY_ERROR_GENERIC;
   4816                 break;
   4817             }
   4818 
   4819             setRegisterType(workLine, decInsn.vA, tmpType);
   4820         }
   4821         break;
   4822     case OP_IGET_WIDE:
   4823         {
   4824             RegType dstType;
   4825             InstField* instField;
   4826             RegType objType;
   4827 
   4828             objType = getRegisterType(workLine, decInsn.vB);
   4829             instField = getInstField(meth, uninitMap, objType, decInsn.vC,
   4830                             &failure);
   4831             if (!VERIFY_OK(failure))
   4832                 break;
   4833             /* check the type, which should be prim */
   4834             switch (instField->signature[0]) {
   4835             case 'D':
   4836                 dstType = kRegTypeDoubleLo;
   4837                 break;
   4838             case 'J':
   4839                 dstType = kRegTypeLongLo;
   4840                 break;
   4841             default:
   4842                 LOG_VFY("VFY: invalid iget-wide of %s.%s",
   4843                         instField->clazz->descriptor,
   4844                         instField->name);
   4845                 dstType = kRegTypeUnknown;
   4846                 failure = VERIFY_ERROR_GENERIC;
   4847                 break;
   4848             }
   4849             if (VERIFY_OK(failure)) {
   4850                 setRegisterType(workLine, decInsn.vA, dstType);
   4851             }
   4852         }
   4853         break;
   4854     case OP_IGET_OBJECT:
   4855         {
   4856             ClassObject* fieldClass;
   4857             InstField* instField;
   4858             RegType objType;
   4859 
   4860             objType = getRegisterType(workLine, decInsn.vB);
   4861             instField = getInstField(meth, uninitMap, objType, decInsn.vC,
   4862                             &failure);
   4863             if (!VERIFY_OK(failure))
   4864                 break;
   4865             fieldClass = getFieldClass(meth, instField);
   4866             if (fieldClass == NULL) {
   4867                 /* class not found or primitive type */
   4868                 LOG_VFY("VFY: unable to recover field class from '%s'",
   4869                     instField->signature);
   4870                 failure = VERIFY_ERROR_GENERIC;
   4871                 break;
   4872             }
   4873             if (VERIFY_OK(failure)) {
   4874                 assert(!dvmIsPrimitiveClass(fieldClass));
   4875                 setRegisterType(workLine, decInsn.vA,
   4876                     regTypeFromClass(fieldClass));
   4877             }
   4878         }
   4879         break;
   4880     case OP_IPUT:
   4881         tmpType = kRegTypeInteger;
   4882         goto iput_1nr_common;
   4883     case OP_IPUT_BOOLEAN:
   4884         tmpType = kRegTypeBoolean;
   4885         goto iput_1nr_common;
   4886     case OP_IPUT_BYTE:
   4887         tmpType = kRegTypeByte;
   4888         goto iput_1nr_common;
   4889     case OP_IPUT_CHAR:
   4890         tmpType = kRegTypeChar;
   4891         goto iput_1nr_common;
   4892     case OP_IPUT_SHORT:
   4893         tmpType = kRegTypeShort;
   4894         goto iput_1nr_common;
   4895 iput_1nr_common:
   4896         {
   4897             RegType srcType, fieldType, objType;
   4898             InstField* instField;
   4899 
   4900             srcType = getRegisterType(workLine, decInsn.vA);
   4901 
   4902             /*
   4903              * javac generates synthetic functions that write byte values
   4904              * into boolean fields.
   4905              */
   4906             if (tmpType == kRegTypeBoolean && srcType == kRegTypeByte)
   4907                 tmpType = kRegTypeByte;
   4908 
   4909             /* correct if float */
   4910             if (srcType == kRegTypeFloat && tmpType == kRegTypeInteger)
   4911               tmpType = kRegTypeFloat;
   4912 
   4913             /* make sure the source register has the correct type */
   4914             if (!canConvertTo1nr(srcType, tmpType)) {
   4915                 LOG_VFY("VFY: invalid reg type %d on iput instr (need %d)",
   4916                     srcType, tmpType);
   4917                 failure = VERIFY_ERROR_GENERIC;
   4918                 break;
   4919             }
   4920 
   4921             objType = getRegisterType(workLine, decInsn.vB);
   4922             instField = getInstField(meth, uninitMap, objType, decInsn.vC,
   4923                             &failure);
   4924             if (!VERIFY_OK(failure))
   4925                 break;
   4926             checkFinalFieldAccess(meth, instField, &failure);
   4927             if (!VERIFY_OK(failure))
   4928                 break;
   4929 
   4930             /* get type of field we're storing into */
   4931             fieldType = primSigCharToRegType(instField->signature[0]);
   4932 
   4933             /* correct if float */
   4934             if (fieldType == kRegTypeFloat && tmpType == kRegTypeInteger)
   4935                 tmpType = kRegTypeFloat;
   4936 
   4937             if (fieldType == kRegTypeBoolean && srcType == kRegTypeByte)
   4938                 fieldType = kRegTypeByte;
   4939 
   4940             verifyRegisterType(workLine, decInsn.vA, fieldType, &failure);
   4941 
   4942             if (fieldType == kRegTypeUnknown ||
   4943                 !checkFieldArrayStore1nr(tmpType, fieldType))
   4944             {
   4945                 LOG_VFY("VFY: invalid iput-1nr of %s.%s (inst=%d field=%d)",
   4946                         instField->clazz->descriptor,
   4947                         instField->name, tmpType, fieldType);
   4948                 failure = VERIFY_ERROR_GENERIC;
   4949                 break;
   4950             }
   4951         }
   4952         break;
   4953     case OP_IPUT_WIDE:
   4954         tmpType = getRegisterType(workLine, decInsn.vA);
   4955         {
   4956             RegType typeHi = getRegisterType(workLine, decInsn.vA + 1);
   4957             checkTypeCategory(tmpType, kTypeCategory2, &failure);
   4958             checkWidePair(tmpType, typeHi, &failure);
   4959         }
   4960         if (!VERIFY_OK(failure))
   4961             break;
   4962 
   4963         InstField* instField;
   4964         RegType objType;
   4965 
   4966         objType = getRegisterType(workLine, decInsn.vB);
   4967         instField = getInstField(meth, uninitMap, objType, decInsn.vC,
   4968                         &failure);
   4969         if (!VERIFY_OK(failure))
   4970             break;
   4971         checkFinalFieldAccess(meth, instField, &failure);
   4972         if (!VERIFY_OK(failure))
   4973             break;
   4974 
   4975         /* check the type, which should be prim */
   4976         switch (instField->signature[0]) {
   4977         case 'D':
   4978             verifyRegisterType(workLine, decInsn.vA, kRegTypeDoubleLo, &failure);
   4979             break;
   4980         case 'J':
   4981             verifyRegisterType(workLine, decInsn.vA, kRegTypeLongLo, &failure);
   4982             break;
   4983         default:
   4984             LOG_VFY("VFY: invalid iput-wide of %s.%s",
   4985                     instField->clazz->descriptor,
   4986                     instField->name);
   4987             failure = VERIFY_ERROR_GENERIC;
   4988             break;
   4989         }
   4990         break;
   4991     case OP_IPUT_OBJECT:
   4992         {
   4993             ClassObject* fieldClass;
   4994             ClassObject* valueClass;
   4995             InstField* instField;
   4996             RegType objType, valueType;
   4997 
   4998             objType = getRegisterType(workLine, decInsn.vB);
   4999             instField = getInstField(meth, uninitMap, objType, decInsn.vC,
   5000                             &failure);
   5001             if (!VERIFY_OK(failure))
   5002                 break;
   5003             checkFinalFieldAccess(meth, instField, &failure);
   5004             if (!VERIFY_OK(failure))
   5005                 break;
   5006 
   5007             fieldClass = getFieldClass(meth, instField);
   5008             if (fieldClass == NULL) {
   5009                 LOG_VFY("VFY: unable to recover field class from '%s'",
   5010                     instField->signature);
   5011                 failure = VERIFY_ERROR_GENERIC;
   5012                 break;
   5013             }
   5014 
   5015             valueType = getRegisterType(workLine, decInsn.vA);
   5016             if (!regTypeIsReference(valueType)) {
   5017                 LOG_VFY("VFY: storing non-ref v%d into ref field '%s' (%s)",
   5018                         decInsn.vA, instField->name,
   5019                         fieldClass->descriptor);
   5020                 failure = VERIFY_ERROR_GENERIC;
   5021                 break;
   5022             }
   5023             if (valueType != kRegTypeZero) {
   5024                 valueClass = regTypeInitializedReferenceToClass(valueType);
   5025                 if (valueClass == NULL) {
   5026                     LOG_VFY("VFY: storing uninit ref v%d into ref field",
   5027                         decInsn.vA);
   5028                     failure = VERIFY_ERROR_GENERIC;
   5029                     break;
   5030                 }
   5031                 /* allow if field is any interface or field is base class */
   5032                 if (!dvmIsInterfaceClass(fieldClass) &&
   5033                     !dvmInstanceof(valueClass, fieldClass))
   5034                 {
   5035                     LOG_VFY("VFY: storing type '%s' into field type '%s' (%s.%s)",
   5036                             valueClass->descriptor, fieldClass->descriptor,
   5037                             instField->clazz->descriptor,
   5038                             instField->name);
   5039                     failure = VERIFY_ERROR_GENERIC;
   5040                     break;
   5041                 }
   5042             }
   5043         }
   5044         break;
   5045 
   5046     case OP_SGET:
   5047         tmpType = kRegTypeInteger;
   5048         goto sget_1nr_common;
   5049     case OP_SGET_BOOLEAN:
   5050         tmpType = kRegTypeBoolean;
   5051         goto sget_1nr_common;
   5052     case OP_SGET_BYTE:
   5053         tmpType = kRegTypeByte;
   5054         goto sget_1nr_common;
   5055     case OP_SGET_CHAR:
   5056         tmpType = kRegTypeChar;
   5057         goto sget_1nr_common;
   5058     case OP_SGET_SHORT:
   5059         tmpType = kRegTypeShort;
   5060         goto sget_1nr_common;
   5061 sget_1nr_common:
   5062         {
   5063             StaticField* staticField;
   5064             RegType fieldType;
   5065 
   5066             staticField = getStaticField(meth, decInsn.vB, &failure);
   5067             if (!VERIFY_OK(failure))
   5068                 break;
   5069 
   5070             /*
   5071              * Make sure the field's type is compatible with expectation.
   5072              * We can get ourselves into trouble if we mix & match loads
   5073              * and stores with different widths, so rather than just checking
   5074              * "canConvertTo1nr" we require that the field types have equal
   5075              * widths.
   5076              */
   5077             fieldType = primSigCharToRegType(staticField->signature[0]);
   5078 
   5079             /* correct if float */
   5080             if (fieldType == kRegTypeFloat && tmpType == kRegTypeInteger)
   5081                 tmpType = kRegTypeFloat;
   5082 
   5083             if (!checkFieldArrayStore1nr(tmpType, fieldType)) {
   5084                 LOG_VFY("VFY: invalid sget-1nr of %s.%s (inst=%d actual=%d)",
   5085                     staticField->clazz->descriptor,
   5086                     staticField->name, tmpType, fieldType);
   5087                 failure = VERIFY_ERROR_GENERIC;
   5088                 break;
   5089             }
   5090 
   5091             setRegisterType(workLine, decInsn.vA, tmpType);
   5092         }
   5093         break;
   5094     case OP_SGET_WIDE:
   5095         {
   5096             StaticField* staticField;
   5097             RegType dstType;
   5098 
   5099             staticField = getStaticField(meth, decInsn.vB, &failure);
   5100             if (!VERIFY_OK(failure))
   5101                 break;
   5102             /* check the type, which should be prim */
   5103             switch (staticField->signature[0]) {
   5104             case 'D':
   5105                 dstType = kRegTypeDoubleLo;
   5106                 break;
   5107             case 'J':
   5108                 dstType = kRegTypeLongLo;
   5109                 break;
   5110             default:
   5111                 LOG_VFY("VFY: invalid sget-wide of %s.%s",
   5112                         staticField->clazz->descriptor,
   5113                         staticField->name);
   5114                 dstType = kRegTypeUnknown;
   5115                 failure = VERIFY_ERROR_GENERIC;
   5116                 break;
   5117             }
   5118             if (VERIFY_OK(failure)) {
   5119                 setRegisterType(workLine, decInsn.vA, dstType);
   5120             }
   5121         }
   5122         break;
   5123     case OP_SGET_OBJECT:
   5124         {
   5125             StaticField* staticField;
   5126             ClassObject* fieldClass;
   5127 
   5128             staticField = getStaticField(meth, decInsn.vB, &failure);
   5129             if (!VERIFY_OK(failure))
   5130                 break;
   5131             fieldClass = getFieldClass(meth, staticField);
   5132             if (fieldClass == NULL) {
   5133                 LOG_VFY("VFY: unable to recover field class from '%s'",
   5134                     staticField->signature);
   5135                 failure = VERIFY_ERROR_GENERIC;
   5136                 break;
   5137             }
   5138             if (dvmIsPrimitiveClass(fieldClass)) {
   5139                 LOG_VFY("VFY: attempt to get prim field with sget-object");
   5140                 failure = VERIFY_ERROR_GENERIC;
   5141                 break;
   5142             }
   5143             setRegisterType(workLine, decInsn.vA, regTypeFromClass(fieldClass));
   5144         }
   5145         break;
   5146     case OP_SPUT:
   5147         tmpType = kRegTypeInteger;
   5148         goto sput_1nr_common;
   5149     case OP_SPUT_BOOLEAN:
   5150         tmpType = kRegTypeBoolean;
   5151         goto sput_1nr_common;
   5152     case OP_SPUT_BYTE:
   5153         tmpType = kRegTypeByte;
   5154         goto sput_1nr_common;
   5155     case OP_SPUT_CHAR:
   5156         tmpType = kRegTypeChar;
   5157         goto sput_1nr_common;
   5158     case OP_SPUT_SHORT:
   5159         tmpType = kRegTypeShort;
   5160         goto sput_1nr_common;
   5161 sput_1nr_common:
   5162         {
   5163             RegType srcType, fieldType;
   5164             StaticField* staticField;
   5165 
   5166             srcType = getRegisterType(workLine, decInsn.vA);
   5167 
   5168             /*
   5169              * javac generates synthetic functions that write byte values
   5170              * into boolean fields.
   5171              */
   5172             if (tmpType == kRegTypeBoolean && srcType == kRegTypeByte)
   5173                 tmpType = kRegTypeByte;
   5174 
   5175             /* correct if float */
   5176             if (srcType == kRegTypeFloat && tmpType == kRegTypeInteger)
   5177               tmpType = kRegTypeFloat;
   5178 
   5179             /* make sure the source register has the correct type */
   5180             if (!canConvertTo1nr(srcType, tmpType)) {
   5181                 LOG_VFY("VFY: invalid reg type %d on sput instr (need %d)",
   5182                     srcType, tmpType);
   5183                 failure = VERIFY_ERROR_GENERIC;
   5184                 break;
   5185             }
   5186 
   5187             staticField = getStaticField(meth, decInsn.vB, &failure);
   5188             if (!VERIFY_OK(failure))
   5189                 break;
   5190             checkFinalFieldAccess(meth, staticField, &failure);
   5191             if (!VERIFY_OK(failure))
   5192                 break;
   5193 
   5194             /*
   5195              * Get type of field we're storing into.  We know that the
   5196              * contents of the register match the instruction, but we also
   5197              * need to ensure that the instruction matches the field type.
   5198              * Using e.g. sput-short to write into a 32-bit integer field
   5199              * can lead to trouble if we do 16-bit writes.
   5200              */
   5201             fieldType = primSigCharToRegType(staticField->signature[0]);
   5202 
   5203             /* correct if float */
   5204             if (fieldType == kRegTypeFloat && tmpType == kRegTypeInteger)
   5205                 tmpType = kRegTypeFloat;
   5206 
   5207             if (fieldType == kRegTypeBoolean && srcType == kRegTypeByte)
   5208                 fieldType = kRegTypeByte;
   5209 
   5210             verifyRegisterType(workLine, decInsn.vA, fieldType, &failure);
   5211 
   5212             if (fieldType == kRegTypeUnknown ||
   5213                 !checkFieldArrayStore1nr(tmpType, fieldType)) {
   5214                 LOG_VFY("VFY: invalid sput-1nr of %s.%s (inst=%d actual=%d)",
   5215                     staticField->clazz->descriptor,
   5216                     staticField->name, tmpType, fieldType);
   5217                 failure = VERIFY_ERROR_GENERIC;
   5218                 break;
   5219             }
   5220         }
   5221         break;
   5222     case OP_SPUT_WIDE:
   5223         tmpType = getRegisterType(workLine, decInsn.vA);
   5224         {
   5225             RegType typeHi = getRegisterType(workLine, decInsn.vA + 1);
   5226             checkTypeCategory(tmpType, kTypeCategory2, &failure);
   5227             checkWidePair(tmpType, typeHi, &failure);
   5228         }
   5229         if (!VERIFY_OK(failure))
   5230             break;
   5231 
   5232         StaticField* staticField;
   5233 
   5234         staticField = getStaticField(meth, decInsn.vB, &failure);
   5235         if (!VERIFY_OK(failure))
   5236             break;
   5237         checkFinalFieldAccess(meth, staticField, &failure);
   5238         if (!VERIFY_OK(failure))
   5239             break;
   5240 
   5241         /* check the type, which should be prim */
   5242         switch (staticField->signature[0]) {
   5243         case 'D':
   5244             verifyRegisterType(workLine, decInsn.vA, kRegTypeDoubleLo, &failure);
   5245             break;
   5246         case 'J':
   5247             verifyRegisterType(workLine, decInsn.vA, kRegTypeLongLo, &failure);
   5248             break;
   5249         default:
   5250             LOG_VFY("VFY: invalid sput-wide of %s.%s",
   5251                     staticField->clazz->descriptor,
   5252                     staticField->name);
   5253             failure = VERIFY_ERROR_GENERIC;
   5254             break;
   5255         }
   5256         break;
   5257     case OP_SPUT_OBJECT:
   5258         {
   5259             ClassObject* fieldClass;
   5260             ClassObject* valueClass;
   5261             StaticField* staticField;
   5262             RegType valueType;
   5263 
   5264             staticField = getStaticField(meth, decInsn.vB, &failure);
   5265             if (!VERIFY_OK(failure))
   5266                 break;
   5267             checkFinalFieldAccess(meth, staticField, &failure);
   5268             if (!VERIFY_OK(failure))
   5269                 break;
   5270 
   5271             fieldClass = getFieldClass(meth, staticField);
   5272             if (fieldClass == NULL) {
   5273                 LOG_VFY("VFY: unable to recover field class from '%s'",
   5274                     staticField->signature);
   5275                 failure = VERIFY_ERROR_GENERIC;
   5276                 break;
   5277             }
   5278 
   5279             valueType = getRegisterType(workLine, decInsn.vA);
   5280             if (!regTypeIsReference(valueType)) {
   5281                 LOG_VFY("VFY: storing non-ref v%d into ref field '%s' (%s)",
   5282                         decInsn.vA, staticField->name,
   5283                         fieldClass->descriptor);
   5284                 failure = VERIFY_ERROR_GENERIC;
   5285                 break;
   5286             }
   5287             if (valueType != kRegTypeZero) {
   5288                 valueClass = regTypeInitializedReferenceToClass(valueType);
   5289                 if (valueClass == NULL) {
   5290                     LOG_VFY("VFY: storing uninit ref v%d into ref field",
   5291                         decInsn.vA);
   5292                     failure = VERIFY_ERROR_GENERIC;
   5293                     break;
   5294                 }
   5295                 /* allow if field is any interface or field is base class */
   5296                 if (!dvmIsInterfaceClass(fieldClass) &&
   5297                     !dvmInstanceof(valueClass, fieldClass))
   5298                 {
   5299                     LOG_VFY("VFY: storing type '%s' into field type '%s' (%s.%s)",
   5300                             valueClass->descriptor, fieldClass->descriptor,
   5301                             staticField->clazz->descriptor,
   5302                             staticField->name);
   5303                     failure = VERIFY_ERROR_GENERIC;
   5304                     break;
   5305                 }
   5306             }
   5307         }
   5308         break;
   5309 
   5310     case OP_INVOKE_VIRTUAL:
   5311     case OP_INVOKE_VIRTUAL_RANGE:
   5312     case OP_INVOKE_SUPER:
   5313     case OP_INVOKE_SUPER_RANGE:
   5314         {
   5315             Method* calledMethod;
   5316             RegType returnType;
   5317             bool isRange;
   5318             bool isSuper;
   5319 
   5320             isRange =  (decInsn.opcode == OP_INVOKE_VIRTUAL_RANGE ||
   5321                         decInsn.opcode == OP_INVOKE_SUPER_RANGE);
   5322             isSuper =  (decInsn.opcode == OP_INVOKE_SUPER ||
   5323                         decInsn.opcode == OP_INVOKE_SUPER_RANGE);
   5324 
   5325             calledMethod = verifyInvocationArgs(meth, workLine, insnRegCount,
   5326                             &decInsn, uninitMap, METHOD_VIRTUAL, isRange,
   5327                             isSuper, &failure);
   5328             if (!VERIFY_OK(failure))
   5329                 break;
   5330             returnType = getMethodReturnType(calledMethod);
   5331             setResultRegisterType(workLine, insnRegCount, returnType);
   5332             justSetResult = true;
   5333         }
   5334         break;
   5335     case OP_INVOKE_DIRECT:
   5336     case OP_INVOKE_DIRECT_RANGE:
   5337         {
   5338             RegType returnType;
   5339             Method* calledMethod;
   5340             bool isRange;
   5341 
   5342             isRange =  (decInsn.opcode == OP_INVOKE_DIRECT_RANGE);
   5343             calledMethod = verifyInvocationArgs(meth, workLine, insnRegCount,
   5344                             &decInsn, uninitMap, METHOD_DIRECT, isRange,
   5345                             false, &failure);
   5346             if (!VERIFY_OK(failure))
   5347                 break;
   5348 
   5349             /*
   5350              * Some additional checks when calling <init>.  We know from
   5351              * the invocation arg check that the "this" argument is an
   5352              * instance of calledMethod->clazz.  Now we further restrict
   5353              * that to require that calledMethod->clazz is the same as
   5354              * this->clazz or this->super, allowing the latter only if
   5355              * the "this" argument is the same as the "this" argument to
   5356              * this method (which implies that we're in <init> ourselves).
   5357              */
   5358             if (isInitMethod(calledMethod)) {
   5359                 RegType thisType;
   5360                 thisType = getInvocationThis(workLine, &decInsn, &failure);
   5361                 if (!VERIFY_OK(failure))
   5362                     break;
   5363 
   5364                 /* no null refs allowed (?) */
   5365                 if (thisType == kRegTypeZero) {
   5366                     LOG_VFY("VFY: unable to initialize null ref");
   5367                     failure = VERIFY_ERROR_GENERIC;
   5368                     break;
   5369                 }
   5370 
   5371                 ClassObject* thisClass;
   5372 
   5373                 thisClass = regTypeReferenceToClass(thisType, uninitMap);
   5374                 assert(thisClass != NULL);
   5375 
   5376                 /* must be in same class or in superclass */
   5377                 if (calledMethod->clazz == thisClass->super) {
   5378                     if (thisClass != meth->clazz) {
   5379                         LOG_VFY("VFY: invoke-direct <init> on super only "
   5380                             "allowed for 'this' in <init>");
   5381                         failure = VERIFY_ERROR_GENERIC;
   5382                         break;
   5383                     }
   5384                 }  else if (calledMethod->clazz != thisClass) {
   5385                     LOG_VFY("VFY: invoke-direct <init> must be on current "
   5386                             "class or super");
   5387                     failure = VERIFY_ERROR_GENERIC;
   5388                     break;
   5389                 }
   5390 
   5391                 /* arg must be an uninitialized reference */
   5392                 if (!regTypeIsUninitReference(thisType)) {
   5393                     LOG_VFY("VFY: can only initialize the uninitialized");
   5394                     failure = VERIFY_ERROR_GENERIC;
   5395                     break;
   5396                 }
   5397 
   5398                 /*
   5399                  * Replace the uninitialized reference with an initialized
   5400                  * one, and clear the entry in the uninit map.  We need to
   5401                  * do this for all registers that have the same object
   5402                  * instance in them, not just the "this" register.
   5403                  */
   5404                 markRefsAsInitialized(workLine, insnRegCount, uninitMap,
   5405                     thisType, &failure);
   5406                 if (!VERIFY_OK(failure))
   5407                     break;
   5408             }
   5409             returnType = getMethodReturnType(calledMethod);
   5410             setResultRegisterType(workLine, insnRegCount, returnType);
   5411             justSetResult = true;
   5412         }
   5413         break;
   5414     case OP_INVOKE_STATIC:
   5415     case OP_INVOKE_STATIC_RANGE:
   5416         {
   5417             RegType returnType;
   5418             Method* calledMethod;
   5419             bool isRange;
   5420 
   5421             isRange =  (decInsn.opcode == OP_INVOKE_STATIC_RANGE);
   5422             calledMethod = verifyInvocationArgs(meth, workLine, insnRegCount,
   5423                             &decInsn, uninitMap, METHOD_STATIC, isRange,
   5424                             false, &failure);
   5425             if (!VERIFY_OK(failure))
   5426                 break;
   5427 
   5428             returnType = getMethodReturnType(calledMethod);
   5429             setResultRegisterType(workLine, insnRegCount, returnType);
   5430             justSetResult = true;
   5431         }
   5432         break;
   5433     case OP_INVOKE_INTERFACE:
   5434     case OP_INVOKE_INTERFACE_RANGE:
   5435         {
   5436             RegType /*thisType,*/ returnType;
   5437             Method* absMethod;
   5438             bool isRange;
   5439 
   5440             isRange =  (decInsn.opcode == OP_INVOKE_INTERFACE_RANGE);
   5441             absMethod = verifyInvocationArgs(meth, workLine, insnRegCount,
   5442                             &decInsn, uninitMap, METHOD_INTERFACE, isRange,
   5443                             false, &failure);
   5444             if (!VERIFY_OK(failure))
   5445                 break;
   5446 
   5447 #if 0       /* can't do this here, fails on dalvik test 052-verifier-fun */
   5448             /*
   5449              * Get the type of the "this" arg, which should always be an
   5450              * interface class.  Because we don't do a full merge on
   5451              * interface classes, this might have reduced to Object.
   5452              */
   5453             thisType = getInvocationThis(workLine, &decInsn, &failure);
   5454             if (!VERIFY_OK(failure))
   5455                 break;
   5456 
   5457             if (thisType == kRegTypeZero) {
   5458                 /* null pointer always passes (and always fails at runtime) */
   5459             } else {
   5460                 ClassObject* thisClass;
   5461 
   5462                 thisClass = regTypeInitializedReferenceToClass(thisType);
   5463                 if (thisClass == NULL) {
   5464                     LOG_VFY("VFY: interface call on uninitialized");
   5465                     failure = VERIFY_ERROR_GENERIC;
   5466                     break;
   5467                 }
   5468 
   5469                 /*
   5470                  * Either "thisClass" needs to be the interface class that
   5471                  * defined absMethod, or absMethod's class needs to be one
   5472                  * of the interfaces implemented by "thisClass".  (Or, if
   5473                  * we couldn't complete the merge, this will be Object.)
   5474                  */
   5475                 if (thisClass != absMethod->clazz &&
   5476                     thisClass != gDvm.classJavaLangObject &&
   5477                     !dvmImplements(thisClass, absMethod->clazz))
   5478                 {
   5479                     LOG_VFY("VFY: unable to match absMethod '%s' with %s interfaces",
   5480                             absMethod->name, thisClass->descriptor);
   5481                     failure = VERIFY_ERROR_GENERIC;
   5482                     break;
   5483                 }
   5484             }
   5485 #endif
   5486 
   5487             /*
   5488              * We don't have an object instance, so we can't find the
   5489              * concrete method.  However, all of the type information is
   5490              * in the abstract method, so we're good.
   5491              */
   5492             returnType = getMethodReturnType(absMethod);
   5493             setResultRegisterType(workLine, insnRegCount, returnType);
   5494             justSetResult = true;
   5495         }
   5496         break;
   5497 
   5498     case OP_NEG_INT:
   5499     case OP_NOT_INT:
   5500         checkUnop(workLine, &decInsn,
   5501             kRegTypeInteger, kRegTypeInteger, &failure);
   5502         break;
   5503     case OP_NEG_LONG:
   5504     case OP_NOT_LONG:
   5505         checkUnop(workLine, &decInsn,
   5506             kRegTypeLongLo, kRegTypeLongLo, &failure);
   5507         break;
   5508     case OP_NEG_FLOAT:
   5509         checkUnop(workLine, &decInsn,
   5510             kRegTypeFloat, kRegTypeFloat, &failure);
   5511         break;
   5512     case OP_NEG_DOUBLE:
   5513         checkUnop(workLine, &decInsn,
   5514             kRegTypeDoubleLo, kRegTypeDoubleLo, &failure);
   5515         break;
   5516     case OP_INT_TO_LONG:
   5517         checkUnop(workLine, &decInsn,
   5518             kRegTypeLongLo, kRegTypeInteger, &failure);
   5519         break;
   5520     case OP_INT_TO_FLOAT:
   5521         checkUnop(workLine, &decInsn,
   5522             kRegTypeFloat, kRegTypeInteger, &failure);
   5523         break;
   5524     case OP_INT_TO_DOUBLE:
   5525         checkUnop(workLine, &decInsn,
   5526             kRegTypeDoubleLo, kRegTypeInteger, &failure);
   5527         break;
   5528     case OP_LONG_TO_INT:
   5529         checkUnop(workLine, &decInsn,
   5530             kRegTypeInteger, kRegTypeLongLo, &failure);
   5531         break;
   5532     case OP_LONG_TO_FLOAT:
   5533         checkUnop(workLine, &decInsn,
   5534             kRegTypeFloat, kRegTypeLongLo, &failure);
   5535         break;
   5536     case OP_LONG_TO_DOUBLE:
   5537         checkUnop(workLine, &decInsn,
   5538             kRegTypeDoubleLo, kRegTypeLongLo, &failure);
   5539         break;
   5540     case OP_FLOAT_TO_INT:
   5541         checkUnop(workLine, &decInsn,
   5542             kRegTypeInteger, kRegTypeFloat, &failure);
   5543         break;
   5544     case OP_FLOAT_TO_LONG:
   5545         checkUnop(workLine, &decInsn,
   5546             kRegTypeLongLo, kRegTypeFloat, &failure);
   5547         break;
   5548     case OP_FLOAT_TO_DOUBLE:
   5549         checkUnop(workLine, &decInsn,
   5550             kRegTypeDoubleLo, kRegTypeFloat, &failure);
   5551         break;
   5552     case OP_DOUBLE_TO_INT:
   5553         checkUnop(workLine, &decInsn,
   5554             kRegTypeInteger, kRegTypeDoubleLo, &failure);
   5555         break;
   5556     case OP_DOUBLE_TO_LONG:
   5557         checkUnop(workLine, &decInsn,
   5558             kRegTypeLongLo, kRegTypeDoubleLo, &failure);
   5559         break;
   5560     case OP_DOUBLE_TO_FLOAT:
   5561         checkUnop(workLine, &decInsn,
   5562             kRegTypeFloat, kRegTypeDoubleLo, &failure);
   5563         break;
   5564     case OP_INT_TO_BYTE:
   5565         checkUnop(workLine, &decInsn,
   5566             kRegTypeByte, kRegTypeInteger, &failure);
   5567         break;
   5568     case OP_INT_TO_CHAR:
   5569         checkUnop(workLine, &decInsn,
   5570             kRegTypeChar, kRegTypeInteger, &failure);
   5571         break;
   5572     case OP_INT_TO_SHORT:
   5573         checkUnop(workLine, &decInsn,
   5574             kRegTypeShort, kRegTypeInteger, &failure);
   5575         break;
   5576 
   5577     case OP_ADD_INT:
   5578     case OP_SUB_INT:
   5579     case OP_MUL_INT:
   5580     case OP_REM_INT:
   5581     case OP_DIV_INT:
   5582     case OP_SHL_INT:
   5583     case OP_SHR_INT:
   5584     case OP_USHR_INT:
   5585         checkBinop(workLine, &decInsn,
   5586             kRegTypeInteger, kRegTypeInteger, kRegTypeInteger, false, &failure);
   5587         break;
   5588     case OP_AND_INT:
   5589     case OP_OR_INT:
   5590     case OP_XOR_INT:
   5591         checkBinop(workLine, &decInsn,
   5592             kRegTypeInteger, kRegTypeInteger, kRegTypeInteger, true, &failure);
   5593         break;
   5594     case OP_ADD_LONG:
   5595     case OP_SUB_LONG:
   5596     case OP_MUL_LONG:
   5597     case OP_DIV_LONG:
   5598     case OP_REM_LONG:
   5599     case OP_AND_LONG:
   5600     case OP_OR_LONG:
   5601     case OP_XOR_LONG:
   5602         checkBinop(workLine, &decInsn,
   5603             kRegTypeLongLo, kRegTypeLongLo, kRegTypeLongLo, false, &failure);
   5604         break;
   5605     case OP_SHL_LONG:
   5606     case OP_SHR_LONG:
   5607     case OP_USHR_LONG:
   5608         /* shift distance is Int, making these different from other binops */
   5609         checkBinop(workLine, &decInsn,
   5610             kRegTypeLongLo, kRegTypeLongLo, kRegTypeInteger, false, &failure);
   5611         break;
   5612     case OP_ADD_FLOAT:
   5613     case OP_SUB_FLOAT:
   5614     case OP_MUL_FLOAT:
   5615     case OP_DIV_FLOAT:
   5616     case OP_REM_FLOAT:
   5617         checkBinop(workLine, &decInsn,
   5618             kRegTypeFloat, kRegTypeFloat, kRegTypeFloat, false, &failure);
   5619         break;
   5620     case OP_ADD_DOUBLE:
   5621     case OP_SUB_DOUBLE:
   5622     case OP_MUL_DOUBLE:
   5623     case OP_DIV_DOUBLE:
   5624     case OP_REM_DOUBLE:
   5625         checkBinop(workLine, &decInsn,
   5626             kRegTypeDoubleLo, kRegTypeDoubleLo, kRegTypeDoubleLo, false,
   5627             &failure);
   5628         break;
   5629     case OP_ADD_INT_2ADDR:
   5630     case OP_SUB_INT_2ADDR:
   5631     case OP_MUL_INT_2ADDR:
   5632     case OP_REM_INT_2ADDR:
   5633     case OP_SHL_INT_2ADDR:
   5634     case OP_SHR_INT_2ADDR:
   5635     case OP_USHR_INT_2ADDR:
   5636         checkBinop2addr(workLine, &decInsn,
   5637             kRegTypeInteger, kRegTypeInteger, kRegTypeInteger, false, &failure);
   5638         break;
   5639     case OP_AND_INT_2ADDR:
   5640     case OP_OR_INT_2ADDR:
   5641     case OP_XOR_INT_2ADDR:
   5642         checkBinop2addr(workLine, &decInsn,
   5643             kRegTypeInteger, kRegTypeInteger, kRegTypeInteger, true, &failure);
   5644         break;
   5645     case OP_DIV_INT_2ADDR:
   5646         checkBinop2addr(workLine, &decInsn,
   5647             kRegTypeInteger, kRegTypeInteger, kRegTypeInteger, false, &failure);
   5648         break;
   5649     case OP_ADD_LONG_2ADDR:
   5650     case OP_SUB_LONG_2ADDR:
   5651     case OP_MUL_LONG_2ADDR:
   5652     case OP_DIV_LONG_2ADDR:
   5653     case OP_REM_LONG_2ADDR:
   5654     case OP_AND_LONG_2ADDR:
   5655     case OP_OR_LONG_2ADDR:
   5656     case OP_XOR_LONG_2ADDR:
   5657         checkBinop2addr(workLine, &decInsn,
   5658             kRegTypeLongLo, kRegTypeLongLo, kRegTypeLongLo, false, &failure);
   5659         break;
   5660     case OP_SHL_LONG_2ADDR:
   5661     case OP_SHR_LONG_2ADDR:
   5662     case OP_USHR_LONG_2ADDR:
   5663         checkBinop2addr(workLine, &decInsn,
   5664             kRegTypeLongLo, kRegTypeLongLo, kRegTypeInteger, false, &failure);
   5665         break;
   5666     case OP_ADD_FLOAT_2ADDR:
   5667     case OP_SUB_FLOAT_2ADDR:
   5668     case OP_MUL_FLOAT_2ADDR:
   5669     case OP_DIV_FLOAT_2ADDR:
   5670     case OP_REM_FLOAT_2ADDR:
   5671         checkBinop2addr(workLine, &decInsn,
   5672             kRegTypeFloat, kRegTypeFloat, kRegTypeFloat, false, &failure);
   5673         break;
   5674     case OP_ADD_DOUBLE_2ADDR:
   5675     case OP_SUB_DOUBLE_2ADDR:
   5676     case OP_MUL_DOUBLE_2ADDR:
   5677     case OP_DIV_DOUBLE_2ADDR:
   5678     case OP_REM_DOUBLE_2ADDR:
   5679         checkBinop2addr(workLine, &decInsn,
   5680             kRegTypeDoubleLo, kRegTypeDoubleLo, kRegTypeDoubleLo, false,
   5681             &failure);
   5682         break;
   5683     case OP_ADD_INT_LIT16:
   5684     case OP_RSUB_INT:
   5685     case OP_MUL_INT_LIT16:
   5686     case OP_DIV_INT_LIT16:
   5687     case OP_REM_INT_LIT16:
   5688         checkLitop(workLine, &decInsn,
   5689             kRegTypeInteger, kRegTypeInteger, false, &failure);
   5690         break;
   5691     case OP_AND_INT_LIT16:
   5692     case OP_OR_INT_LIT16:
   5693     case OP_XOR_INT_LIT16:
   5694         checkLitop(workLine, &decInsn,
   5695             kRegTypeInteger, kRegTypeInteger, true, &failure);
   5696         break;
   5697     case OP_ADD_INT_LIT8:
   5698     case OP_RSUB_INT_LIT8:
   5699     case OP_MUL_INT_LIT8:
   5700     case OP_DIV_INT_LIT8:
   5701     case OP_REM_INT_LIT8:
   5702     case OP_SHL_INT_LIT8:
   5703         checkLitop(workLine, &decInsn,
   5704             kRegTypeInteger, kRegTypeInteger, false, &failure);
   5705         break;
   5706     case OP_SHR_INT_LIT8:
   5707         tmpType = adjustForRightShift(workLine,
   5708             decInsn.vB, decInsn.vC, false, &failure);
   5709         checkLitop(workLine, &decInsn,
   5710             tmpType, kRegTypeInteger, false, &failure);
   5711         break;
   5712     case OP_USHR_INT_LIT8:
   5713         tmpType = adjustForRightShift(workLine,
   5714             decInsn.vB, decInsn.vC, true, &failure);
   5715         checkLitop(workLine, &decInsn,
   5716             tmpType, kRegTypeInteger, false, &failure);
   5717         break;
   5718     case OP_AND_INT_LIT8:
   5719     case OP_OR_INT_LIT8:
   5720     case OP_XOR_INT_LIT8:
   5721         checkLitop(workLine, &decInsn,
   5722             kRegTypeInteger, kRegTypeInteger, true, &failure);
   5723         break;
   5724 
   5725     /*
   5726      * This falls into the general category of "optimized" instructions,
   5727      * which don't generally appear during verification.  Because it's
   5728      * inserted in the course of verification, we can expect to see it here.
   5729      */
   5730     case OP_THROW_VERIFICATION_ERROR:
   5731         break;
   5732 
   5733     /*
   5734      * Verifying "quickened" instructions is tricky, because we have
   5735      * discarded the original field/method information.  The byte offsets
   5736      * and vtable indices only have meaning in the context of an object
   5737      * instance.
   5738      *
   5739      * If a piece of code declares a local reference variable, assigns
   5740      * null to it, and then issues a virtual method call on it, we
   5741      * cannot evaluate the method call during verification.  This situation
   5742      * isn't hard to handle, since we know the call will always result in an
   5743      * NPE, and the arguments and return value don't matter.  Any code that
   5744      * depends on the result of the method call is inaccessible, so the
   5745      * fact that we can't fully verify anything that comes after the bad
   5746      * call is not a problem.
   5747      *
   5748      * We must also consider the case of multiple code paths, only some of
   5749      * which involve a null reference.  We can completely verify the method
   5750      * if we sidestep the results of executing with a null reference.
   5751      * For example, if on the first pass through the code we try to do a
   5752      * virtual method invocation through a null ref, we have to skip the
   5753      * method checks and have the method return a "wildcard" type (which
   5754      * merges with anything to become that other thing).  The move-result
   5755      * will tell us if it's a reference, single-word numeric, or double-word
   5756      * value.  We continue to perform the verification, and at the end of
   5757      * the function any invocations that were never fully exercised are
   5758      * marked as null-only.
   5759      *
   5760      * We would do something similar for the field accesses.  The field's
   5761      * type, once known, can be used to recover the width of short integers.
   5762      * If the object reference was null, the field-get returns the "wildcard"
   5763      * type, which is acceptable for any operation.
   5764      */
   5765     case OP_EXECUTE_INLINE:
   5766     case OP_EXECUTE_INLINE_RANGE:
   5767     case OP_IGET_QUICK:
   5768     case OP_IGET_WIDE_QUICK:
   5769     case OP_IGET_OBJECT_QUICK:
   5770     case OP_IPUT_QUICK:
   5771     case OP_IPUT_WIDE_QUICK:
   5772     case OP_IPUT_OBJECT_QUICK:
   5773     case OP_INVOKE_VIRTUAL_QUICK:
   5774     case OP_INVOKE_VIRTUAL_QUICK_RANGE:
   5775     case OP_INVOKE_SUPER_QUICK:
   5776     case OP_INVOKE_SUPER_QUICK_RANGE:
   5777         /* fall through to failure */
   5778 
   5779     /*
   5780      * These instructions are equivalent (from the verifier's point of view)
   5781      * to the original form.  The change was made for correctness rather
   5782      * than improved performance (except for invoke-object-init, which
   5783      * provides both).  The substitution takes place after verification
   5784      * completes, though, so we don't expect to see them here.
   5785      */
   5786     case OP_INVOKE_OBJECT_INIT_RANGE:
   5787     case OP_RETURN_VOID_BARRIER:
   5788     case OP_IGET_VOLATILE:
   5789     case OP_IGET_WIDE_VOLATILE:
   5790     case OP_IGET_OBJECT_VOLATILE:
   5791     case OP_IPUT_VOLATILE:
   5792     case OP_IPUT_WIDE_VOLATILE:
   5793     case OP_IPUT_OBJECT_VOLATILE:
   5794     case OP_SGET_VOLATILE:
   5795     case OP_SGET_WIDE_VOLATILE:
   5796     case OP_SGET_OBJECT_VOLATILE:
   5797     case OP_SPUT_VOLATILE:
   5798     case OP_SPUT_WIDE_VOLATILE:
   5799     case OP_SPUT_OBJECT_VOLATILE:
   5800         /* fall through to failure */
   5801 
   5802     /* these should never appear during verification */
   5803     case OP_UNUSED_3E:
   5804     case OP_UNUSED_3F:
   5805     case OP_UNUSED_40:
   5806     case OP_UNUSED_41:
   5807     case OP_UNUSED_42:
   5808     case OP_UNUSED_43:
   5809     case OP_UNUSED_73:
   5810     case OP_UNUSED_79:
   5811     case OP_UNUSED_7A:
   5812     case OP_BREAKPOINT:
   5813     case OP_UNUSED_FF:
   5814         failure = VERIFY_ERROR_GENERIC;
   5815         break;
   5816 
   5817     /*
   5818      * DO NOT add a "default" clause here.  Without it the compiler will
   5819      * complain if an instruction is missing (which is desirable).
   5820      */
   5821     }
   5822 
   5823     if (!VERIFY_OK(failure)) {
   5824         if (failure == VERIFY_ERROR_GENERIC || gDvm.optimizing) {
   5825             /* immediate failure, reject class */
   5826             LOG_VFY_METH(meth, "VFY:  rejecting opcode 0x%02x at 0x%04x",
   5827                 decInsn.opcode, insnIdx);
   5828             goto bail;
   5829         } else {
   5830             /* replace opcode and continue on */
   5831             ALOGD("VFY: replacing opcode 0x%02x at 0x%04x",
   5832                 decInsn.opcode, insnIdx);
   5833             if (!replaceFailingInstruction(meth, insnFlags, insnIdx, failure)) {
   5834                 LOG_VFY_METH(meth, "VFY:  rejecting opcode 0x%02x at 0x%04x",
   5835                     decInsn.opcode, insnIdx);
   5836                 goto bail;
   5837             }
   5838             /* IMPORTANT: meth->insns may have been changed */
   5839             insns = meth->insns + insnIdx;
   5840 
   5841             /* continue on as if we just handled a throw-verification-error */
   5842             failure = VERIFY_ERROR_NONE;
   5843             nextFlags = kInstrCanThrow;
   5844         }
   5845     }
   5846 
   5847     /*
   5848      * If we didn't just set the result register, clear it out.  This
   5849      * ensures that you can only use "move-result" immediately after the
   5850      * result is set.  (We could check this statically, but it's not
   5851      * expensive and it makes our debugging output cleaner.)
   5852      */
   5853     if (!justSetResult) {
   5854         int reg = RESULT_REGISTER(insnRegCount);
   5855         setRegisterType(workLine, reg, kRegTypeUnknown);
   5856         setRegisterType(workLine, reg+1, kRegTypeUnknown);
   5857     }
   5858 
   5859     /*
   5860      * Handle "continue".  Tag the next consecutive instruction.
   5861      */
   5862     if ((nextFlags & kInstrCanContinue) != 0) {
   5863         int insnWidth = dvmInsnGetWidth(insnFlags, insnIdx);
   5864         if (insnIdx+insnWidth >= insnsSize) {
   5865             LOG_VFY_METH(meth,
   5866                 "VFY: execution can walk off end of code area (from %#x)",
   5867                 insnIdx);
   5868             goto bail;
   5869         }
   5870 
   5871         /*
   5872          * The only way to get to a move-exception instruction is to get
   5873          * thrown there.  Make sure the next instruction isn't one.
   5874          */
   5875         if (!checkMoveException(meth, insnIdx+insnWidth, "next"))
   5876             goto bail;
   5877 
   5878         if (getRegisterLine(regTable, insnIdx+insnWidth)->regTypes != NULL) {
   5879             /*
   5880              * Merge registers into what we have for the next instruction,
   5881              * and set the "changed" flag if needed.
   5882              */
   5883             if (!updateRegisters(meth, insnFlags, regTable, insnIdx+insnWidth,
   5884                     workLine))
   5885                 goto bail;
   5886         } else {
   5887             /*
   5888              * We're not recording register data for the next instruction,
   5889              * so we don't know what the prior state was.  We have to
   5890              * assume that something has changed and re-evaluate it.
   5891              */
   5892             dvmInsnSetChanged(insnFlags, insnIdx+insnWidth, true);
   5893         }
   5894     }
   5895 
   5896     /*
   5897      * Handle "branch".  Tag the branch target.
   5898      *
   5899      * NOTE: instructions like OP_EQZ provide information about the state
   5900      * of the register when the branch is taken or not taken.  For example,
   5901      * somebody could get a reference field, check it for zero, and if the
   5902      * branch is taken immediately store that register in a boolean field
   5903      * since the value is known to be zero.  We do not currently account for
   5904      * that, and will reject the code.
   5905      *
   5906      * TODO: avoid re-fetching the branch target
   5907      */
   5908     if ((nextFlags & kInstrCanBranch) != 0) {
   5909         bool isConditional;
   5910 
   5911         if (!dvmGetBranchOffset(meth, insnFlags, insnIdx, &branchTarget,
   5912                 &isConditional))
   5913         {
   5914             /* should never happen after static verification */
   5915             LOG_VFY_METH(meth, "VFY: bad branch at %d", insnIdx);
   5916             goto bail;
   5917         }
   5918         assert(isConditional || (nextFlags & kInstrCanContinue) == 0);
   5919         assert(!isConditional || (nextFlags & kInstrCanContinue) != 0);
   5920 
   5921         if (!checkMoveException(meth, insnIdx+branchTarget, "branch"))
   5922             goto bail;
   5923 
   5924         /* update branch target, set "changed" if appropriate */
   5925         if (!updateRegisters(meth, insnFlags, regTable, insnIdx+branchTarget,
   5926                 workLine))
   5927             goto bail;
   5928     }
   5929 
   5930     /*
   5931      * Handle "switch".  Tag all possible branch targets.
   5932      *
   5933      * We've already verified that the table is structurally sound, so we
   5934      * just need to walk through and tag the targets.
   5935      */
   5936     if ((nextFlags & kInstrCanSwitch) != 0) {
   5937         int offsetToSwitch = insns[1] | (((s4)insns[2]) << 16);
   5938         const u2* switchInsns = insns + offsetToSwitch;
   5939         int switchCount = switchInsns[1];
   5940         int offsetToTargets, targ;
   5941 
   5942         if ((*insns & 0xff) == OP_PACKED_SWITCH) {
   5943             /* 0=sig, 1=count, 2/3=firstKey */
   5944             offsetToTargets = 4;
   5945         } else {
   5946             /* 0=sig, 1=count, 2..count*2 = keys */
   5947             assert((*insns & 0xff) == OP_SPARSE_SWITCH);
   5948             offsetToTargets = 2 + 2*switchCount;
   5949         }
   5950 
   5951         /* verify each switch target */
   5952         for (targ = 0; targ < switchCount; targ++) {
   5953             int offset, absOffset;
   5954 
   5955             /* offsets are 32-bit, and only partly endian-swapped */
   5956             offset = switchInsns[offsetToTargets + targ*2] |
   5957                      (((s4) switchInsns[offsetToTargets + targ*2 +1]) << 16);
   5958             absOffset = insnIdx + offset;
   5959 
   5960             assert(absOffset >= 0 && absOffset < insnsSize);
   5961 
   5962             if (!checkMoveException(meth, absOffset, "switch"))
   5963                 goto bail;
   5964 
   5965             if (!updateRegisters(meth, insnFlags, regTable, absOffset,
   5966                     workLine))
   5967                 goto bail;
   5968         }
   5969     }
   5970 
   5971     /*
   5972      * Handle instructions that can throw and that are sitting in a
   5973      * "try" block.  (If they're not in a "try" block when they throw,
   5974      * control transfers out of the method.)
   5975      */
   5976     if ((nextFlags & kInstrCanThrow) != 0 && dvmInsnIsInTry(insnFlags, insnIdx))
   5977     {
   5978         const DexCode* pCode = dvmGetMethodCode(meth);
   5979         DexCatchIterator iterator;
   5980         bool hasCatchAll = false;
   5981 
   5982         if (dexFindCatchHandler(&iterator, pCode, insnIdx)) {
   5983             for (;;) {
   5984                 DexCatchHandler* handler = dexCatchIteratorNext(&iterator);
   5985 
   5986                 if (handler == NULL) {
   5987                     break;
   5988                 }
   5989 
   5990                 if (handler->typeIdx == kDexNoIndex)
   5991                     hasCatchAll = true;
   5992 
   5993                 /*
   5994                  * Merge registers into the "catch" block.  We want to
   5995                  * use the "savedRegs" rather than "workRegs", because
   5996                  * at runtime the exception will be thrown before the
   5997                  * instruction modifies any registers.
   5998                  */
   5999                 if (!updateRegisters(meth, insnFlags, regTable,
   6000                         handler->address, &regTable->savedLine))
   6001                     goto bail;
   6002             }
   6003         }
   6004 
   6005         /*
   6006          * If the monitor stack depth is nonzero, there must be a "catch all"
   6007          * handler for this instruction.  This does apply to monitor-exit
   6008          * because of async exception handling.
   6009          */
   6010         if (workLine->monitorStackTop != 0 && !hasCatchAll) {
   6011             /*
   6012              * The state in workLine reflects the post-execution state.
   6013              * If the current instruction is a monitor-enter and the monitor
   6014              * stack was empty, we don't need a catch-all (if it throws,
   6015              * it will do so before grabbing the lock).
   6016              */
   6017             if (!(decInsn.opcode == OP_MONITOR_ENTER &&
   6018                   workLine->monitorStackTop == 1))
   6019             {
   6020                 LOG_VFY_METH(meth,
   6021                     "VFY: no catch-all for instruction at 0x%04x", insnIdx);
   6022                 goto bail;
   6023             }
   6024         }
   6025     }
   6026 
   6027     /*
   6028      * If we're returning from the method, make sure our monitor stack
   6029      * is empty.
   6030      */
   6031     if ((nextFlags & kInstrCanReturn) != 0 && workLine->monitorStackTop != 0) {
   6032         LOG_VFY_METH(meth, "VFY: return with stack depth=%d at 0x%04x",
   6033             workLine->monitorStackTop, insnIdx);
   6034         goto bail;
   6035     }
   6036 
   6037     /*
   6038      * Update startGuess.  Advance to the next instruction of that's
   6039      * possible, otherwise use the branch target if one was found.  If
   6040      * neither of those exists we're in a return or throw; leave startGuess
   6041      * alone and let the caller sort it out.
   6042      */
   6043     if ((nextFlags & kInstrCanContinue) != 0) {
   6044         *pStartGuess = insnIdx + dvmInsnGetWidth(insnFlags, insnIdx);
   6045     } else if ((nextFlags & kInstrCanBranch) != 0) {
   6046         /* we're still okay if branchTarget is zero */
   6047         *pStartGuess = insnIdx + branchTarget;
   6048     }
   6049 
   6050     assert(*pStartGuess >= 0 && *pStartGuess < insnsSize &&
   6051         dvmInsnGetWidth(insnFlags, *pStartGuess) != 0);
   6052 
   6053     result = true;
   6054 
   6055 bail:
   6056     return result;
   6057 }
   6058 
   6059 
   6060 /*
   6061  * callback function used in dumpRegTypes to print local vars
   6062  * valid at a given address.
   6063  */
   6064 static void logLocalsCb(void *cnxt, u2 reg, u4 startAddress, u4 endAddress,
   6065         const char *name, const char *descriptor,
   6066         const char *signature)
   6067 {
   6068     int addr = *((int *)cnxt);
   6069 
   6070     if (addr >= (int) startAddress && addr < (int) endAddress)
   6071     {
   6072         ALOGI("        %2d: '%s' %s", reg, name, descriptor);
   6073     }
   6074 }
   6075 
   6076 /*
   6077  * Dump the register types for the specifed address to the log file.
   6078  */
   6079 static void dumpRegTypes(const VerifierData* vdata,
   6080     const RegisterLine* registerLine, int addr, const char* addrName,
   6081     const UninitInstanceMap* uninitMap, int displayFlags)
   6082 {
   6083     const Method* meth = vdata->method;
   6084     const InsnFlags* insnFlags = vdata->insnFlags;
   6085     const RegType* addrRegs = registerLine->regTypes;
   6086     int regCount = meth->registersSize;
   6087     int fullRegCount = regCount + kExtraRegs;
   6088     bool branchTarget = dvmInsnIsBranchTarget(insnFlags, addr);
   6089     int i;
   6090 
   6091     assert(addr >= 0 && addr < (int) dvmGetMethodInsnsSize(meth));
   6092 
   6093     int regCharSize = fullRegCount + (fullRegCount-1)/4 + 2 +1;
   6094     char regChars[regCharSize +1];
   6095     memset(regChars, ' ', regCharSize);
   6096     regChars[0] = '[';
   6097     if (regCount == 0)
   6098         regChars[1] = ']';
   6099     else
   6100         regChars[1 + (regCount-1) + (regCount-1)/4 +1] = ']';
   6101     regChars[regCharSize] = '\0';
   6102 
   6103     for (i = 0; i < regCount + kExtraRegs; i++) {
   6104         char tch;
   6105 
   6106         switch (addrRegs[i]) {
   6107         case kRegTypeUnknown:       tch = '.';  break;
   6108         case kRegTypeConflict:      tch = 'X';  break;
   6109         case kRegTypeZero:          tch = '0';  break;
   6110         case kRegTypeOne:           tch = '1';  break;
   6111         case kRegTypeBoolean:       tch = 'Z';  break;
   6112         case kRegTypeConstPosByte:  tch = 'y';  break;
   6113         case kRegTypeConstByte:     tch = 'Y';  break;
   6114         case kRegTypeConstPosShort: tch = 'h';  break;
   6115         case kRegTypeConstShort:    tch = 'H';  break;
   6116         case kRegTypeConstChar:     tch = 'c';  break;
   6117         case kRegTypeConstInteger:  tch = 'i';  break;
   6118         case kRegTypePosByte:       tch = 'b';  break;
   6119         case kRegTypeByte:          tch = 'B';  break;
   6120         case kRegTypePosShort:      tch = 's';  break;
   6121         case kRegTypeShort:         tch = 'S';  break;
   6122         case kRegTypeChar:          tch = 'C';  break;
   6123         case kRegTypeInteger:       tch = 'I';  break;
   6124         case kRegTypeFloat:         tch = 'F';  break;
   6125         case kRegTypeConstLo:       tch = 'N';  break;
   6126         case kRegTypeConstHi:       tch = 'n';  break;
   6127         case kRegTypeLongLo:        tch = 'J';  break;
   6128         case kRegTypeLongHi:        tch = 'j';  break;
   6129         case kRegTypeDoubleLo:      tch = 'D';  break;
   6130         case kRegTypeDoubleHi:      tch = 'd';  break;
   6131         default:
   6132             if (regTypeIsReference(addrRegs[i])) {
   6133                 if (regTypeIsUninitReference(addrRegs[i]))
   6134                     tch = 'U';
   6135                 else
   6136                     tch = 'L';
   6137             } else {
   6138                 tch = '*';
   6139                 assert(false);
   6140             }
   6141             break;
   6142         }
   6143 
   6144         if (i < regCount)
   6145             regChars[1 + i + (i/4)] = tch;
   6146         else
   6147             regChars[1 + i + (i/4) + 2] = tch;
   6148     }
   6149 
   6150     if (addr == 0 && addrName != NULL) {
   6151         ALOGI("%c%s %s mst=%d", branchTarget ? '>' : ' ',
   6152             addrName, regChars, registerLine->monitorStackTop);
   6153     } else {
   6154         ALOGI("%c0x%04x %s mst=%d", branchTarget ? '>' : ' ',
   6155             addr, regChars, registerLine->monitorStackTop);
   6156     }
   6157     if (displayFlags & DRT_SHOW_LIVENESS) {
   6158         /*
   6159          * We can't use registerLine->liveRegs because it might be the
   6160          * "work line" rather than the copy from RegisterTable.
   6161          */
   6162         BitVector* liveRegs = vdata->registerLines[addr].liveRegs;
   6163         if (liveRegs != NULL)  {
   6164             char liveChars[regCharSize + 1];
   6165             memset(liveChars, ' ', regCharSize);
   6166             liveChars[regCharSize] = '\0';
   6167 
   6168             for (i = 0; i < regCount; i++) {
   6169                 bool isLive = dvmIsBitSet(liveRegs, i);
   6170                 liveChars[i + 1 + (i / 4)] = isLive ? '+' : '-';
   6171             }
   6172             ALOGI("        %s", liveChars);
   6173         } else {
   6174             ALOGI("        %c", '#');
   6175         }
   6176     }
   6177 
   6178     if (displayFlags & DRT_SHOW_REF_TYPES) {
   6179         for (i = 0; i < regCount + kExtraRegs; i++) {
   6180             if (regTypeIsReference(addrRegs[i]) && addrRegs[i] != kRegTypeZero)
   6181             {
   6182                 ClassObject* clazz = regTypeReferenceToClass(addrRegs[i], uninitMap);
   6183                 assert(dvmIsHeapAddress((Object*)clazz));
   6184                 if (i < regCount) {
   6185                     ALOGI("        %2d: 0x%08x %s%s",
   6186                         i, addrRegs[i],
   6187                         regTypeIsUninitReference(addrRegs[i]) ? "[U]" : "",
   6188                         clazz->descriptor);
   6189                 } else {
   6190                     ALOGI("        RS: 0x%08x %s%s",
   6191                         addrRegs[i],
   6192                         regTypeIsUninitReference(addrRegs[i]) ? "[U]" : "",
   6193                         clazz->descriptor);
   6194                 }
   6195             }
   6196         }
   6197     }
   6198     if (displayFlags & DRT_SHOW_LOCALS) {
   6199         dexDecodeDebugInfo(meth->clazz->pDvmDex->pDexFile,
   6200                 dvmGetMethodCode(meth),
   6201                 meth->clazz->descriptor,
   6202                 meth->prototype.protoIdx,
   6203                 meth->accessFlags,
   6204                 NULL, logLocalsCb, &addr);
   6205     }
   6206 }
   6207