text: /*
   * Copyright (C) 2008 The Android Open Source Project
   *
   * Licensed under the Apache License, Version 2.0 (the "License");
   * you may not use this file except in compliance with the License.
   * You may obtain a copy of the License at
   *
   *      http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  
  /*
   * Dalvik classfile verification.  This file contains the verifier entry
   * points and the static constraint checks.
   */
  #include "Dalvik.h"
  #include "analysis/CodeVerify.h"
  
  
  /* fwd */
  static bool verifyMethod(Method* meth, int verifyFlags);
  static bool verifyInstructions(const Method* meth, InsnFlags* insnFlags,
      int verifyFlags);
  
  
  /*
   * Initialize some things we need for verification.
   */
  bool dvmVerificationStartup(void)
  {
      gDvm.instrWidth = dexCreateInstrWidthTable();
      gDvm.instrFormat = dexCreateInstrFormatTable();
      gDvm.instrFlags = dexCreateInstrFlagsTable();
      return (gDvm.instrWidth != NULL && gDvm.instrFormat!= NULL);
  }
  
  /*
   * Initialize some things we need for verification.
   */
  void dvmVerificationShutdown(void)
  {
      free(gDvm.instrWidth);
      free(gDvm.instrFormat);
      free(gDvm.instrFlags);
  }
  
  /*
   * Induce verification on all classes loaded from this DEX file as part
   * of pre-verification and optimization.  This is never called from a
   * normally running VM.
   *
   * Returns "true" when all classes have been processed.
   */
  bool dvmVerifyAllClasses(DexFile* pDexFile)
  {
      u4 count = pDexFile->pHeader->classDefsSize;
      u4 idx;
  
      assert(gDvm.optimizing);
  
      if (gDvm.classVerifyMode == VERIFY_MODE_NONE) {
          LOGV("+++ verification is disabled, skipping all classes\n");
          return true;
      }
      if (gDvm.classVerifyMode == VERIFY_MODE_REMOTE &&
          gDvm.optimizingBootstrapClass)
      {
          LOGV("+++ verification disabled for bootstrap classes\n");
          return true;
      }
  
      for (idx = 0; idx < count; idx++) {
          const DexClassDef* pClassDef;
          const char* classDescriptor;
          ClassObject* clazz;
  
          pClassDef = dexGetClassDef(pDexFile, idx);
          classDescriptor = dexStringByTypeIdx(pDexFile, pClassDef->classIdx);
  
          /* all classes are loaded into the bootstrap class loader */
          clazz = dvmLookupClass(classDescriptor, NULL, false);
          if (clazz != NULL) {
              if (clazz->pDvmDex->pDexFile != pDexFile) {
                  LOGD("DexOpt: not verifying '%s': multiple definitions\n",
                      classDescriptor);
              } else {
                  if (dvmVerifyClass(clazz, VERIFY_DEFAULT)) {
                      assert((clazz->accessFlags & JAVA_FLAGS_MASK) ==
                          pClassDef->accessFlags);
                      ((DexClassDef*)pClassDef)->accessFlags |=
                          CLASS_ISPREVERIFIED;
                  }
                  /* keep going even if one fails */
              }
          } else {
              LOGV("DexOpt: +++  not verifying '%s'\n", classDescriptor);
          }
      }
  
      return true;
  }
  
  /*
   * Verify a class.
   *
   * By the time we get here, the value of gDvm.classVerifyMode should already
   * have been factored in.  If you want to call into the verifier even
   * though verification is disabled, that's your business.
   *
   * Returns "true" on success.
   */
  bool dvmVerifyClass(ClassObject* clazz, int verifyFlags)
  {
      int i;
  
      if (dvmIsClassVerified(clazz)) {
          LOGD("Ignoring duplicate verify attempt on %s\n", clazz->descriptor);
          return true;
      }
  
      //LOGI("Verify1 '%s'\n", clazz->descriptor);
  
      // TODO - verify class structure in DEX?
  
      for (i = 0; i < clazz->directMethodCount; i++) {
          if (!verifyMethod(&clazz->directMethods[i], verifyFlags)) {
              LOG_VFY("Verifier rejected class %s\n", clazz->descriptor);
              return false;
          }
      }
      for (i = 0; i < clazz->virtualMethodCount; i++) {
          if (!verifyMethod(&clazz->virtualMethods[i], verifyFlags)) {
              LOG_VFY("Verifier rejected class %s\n", clazz->descriptor);
              return false;
          }
      }
  
      return true;
  }
  
  /*
   * Perform verification on a single method.
   *
   * We do this in three passes:
   *  (1) Walk through all code units, determining instruction lengths.
   *  (2) Do static checks, including branch target and operand validation.
   *  (3) Do structural checks, including data-flow analysis.
   *
   * Some checks may be bypassed depending on the verification mode.  We can't
   * turn this stuff off completely if we want to do "exact" GC.
   *
   * - operands of getfield, putfield, getstatic, putstatic must be valid
   * - operands of method invocation instructions must be valid
   *
   * - code array must not be empty
   * - (N/A) code_length must be less than 65536
   * - opcode of first instruction begins at index 0
   * - only documented instructions may appear
   * - each instruction follows the last
   * - (below) last byte of last instruction is at (code_length-1)
   */
  static bool verifyMethod(Method* meth, int verifyFlags)
  {
      bool result = false;
      UninitInstanceMap* uninitMap = NULL;
      InsnFlags* insnFlags = NULL;
      int i, newInstanceCount;
  
      /*
       * If there aren't any instructions, make sure that's expected, then
       * exit successfully. Note: meth->insns gets set to a native function
       * pointer on first call.
       */
      if (dvmGetMethodInsnsSize(meth) == 0) {
          if (!dvmIsNativeMethod(meth) && !dvmIsAbstractMethod(meth)) {
              LOG_VFY_METH(meth,
                  "VFY: zero-length code in concrete non-native method\n");
              goto bail;
          }
  
          goto success;
      }
  
      /*
       * Sanity-check the register counts.  ins + locals = registers, so make
       * sure that ins <= registers.
       */
      if (meth->insSize > meth->registersSize) {
          LOG_VFY_METH(meth, "VFY: bad register counts (ins=%d regs=%d)\n",
              meth->insSize, meth->registersSize);
          goto bail;
      }
  
      /*
       * Allocate and populate an array to hold instruction data.
       *
       * TODO: Consider keeping a reusable pre-allocated array sitting
       * around for smaller methods.
       */
      insnFlags = (InsnFlags*)
          calloc(dvmGetMethodInsnsSize(meth), sizeof(InsnFlags));
      if (insnFlags == NULL)
          goto bail;
  
      /*
       * Compute the width of each instruction and store the result in insnFlags.
       * Count up the #of occurrences of new-instance instructions while we're
       * at it.
       */
      if (!dvmComputeCodeWidths(meth, insnFlags, &newInstanceCount))
          goto bail;
  
      /*
       * Allocate a map to hold the classes of uninitialized instances.
       */
      uninitMap = dvmCreateUninitInstanceMap(meth, insnFlags, newInstanceCount);
      if (uninitMap == NULL)
          goto bail;
  
      /*
       * Set the "in try" flags for all instructions guarded by a "try" block.
       */
      if (!dvmSetTryFlags(meth, insnFlags))
          goto bail;
  
      /*
       * Perform static instruction verification.
       */
      if (!verifyInstructions(meth, insnFlags, verifyFlags))
          goto bail;
  
      /*
       * Do code-flow analysis.  Do this after verifying the branch targets
       * so we don't need to worry about it here.
       *
       * If there are no registers, we don't need to do much in the way of
       * analysis, but we still need to verify that nothing actually tries
       * to use a register.
       */
      if (!dvmVerifyCodeFlow(meth, insnFlags, uninitMap)) {
          //LOGD("+++ %s failed code flow\n", meth->name);
          goto bail;
      }
  
  success:
      result = true;
  
  bail:
      dvmFreeUninitInstanceMap(uninitMap);
      free(insnFlags);
      return result;
  }
  
  
  /*
   * Verify an array data table.  "curOffset" is the offset of the fill-array-data
   * instruction.
   */
  static bool checkArrayData(const Method* meth, int curOffset)
  {
      const int insnCount = dvmGetMethodInsnsSize(meth);
      const u2* insns = meth->insns + curOffset;
      const u2* arrayData;
      int valueCount, valueWidth, tableSize;
      int offsetToArrayData;
  
      assert(curOffset >= 0 && curOffset < insnCount);
  
      /* make sure the start of the array data table is in range */
      offsetToArrayData = insns[1] | (((s4)insns[2]) << 16);
      if (curOffset + offsetToArrayData < 0 ||
          curOffset + offsetToArrayData + 2 >= insnCount)
      {
          LOG_VFY_METH(meth,
              "VFY: invalid array data start: at %d, data offset %d, count %d\n",
              curOffset, offsetToArrayData, insnCount);
          return false;
      }
  
      /* offset to array data table is a relative branch-style offset */
      arrayData = insns + offsetToArrayData;
  
      /* make sure the table is 32-bit aligned */
      if ((((u4) arrayData) & 0x03) != 0) {
          LOG_VFY_METH(meth,
              "VFY: unaligned array data table: at %d, data offset %d\n",
              curOffset, offsetToArrayData);
          return false;
      }
  
      valueWidth = arrayData[1];
      valueCount = *(u4*)(&arrayData[2]);
  
      tableSize = 4 + (valueWidth * valueCount + 1) / 2;
  
      /* make sure the end of the switch is in range */
      if (curOffset + offsetToArrayData + tableSize > insnCount) {
          LOG_VFY_METH(meth,
              "VFY: invalid array data end: at %d, data offset %d, end %d, "
              "count %d\n",
              curOffset, offsetToArrayData, 
              curOffset + offsetToArrayData + tableSize,
              insnCount);
          return false;
      }
  
      return true;
  }
  
  
  /*
   * Decode the current instruction.
   */
  static void decodeInstruction(const Method* meth, int insnIdx,
      DecodedInstruction* pDecInsn)
  {
      dexDecodeInstruction(gDvm.instrFormat, meth->insns + insnIdx, pDecInsn);
  }
  
  
  /*
   * Perform static checks on a "new-instance" instruction.  Specifically,
   * make sure the class reference isn't for an array class.
   *
   * We don't need the actual class, just a pointer to the class name.
   */
  static bool checkNewInstance(const Method* meth, int insnIdx)
  {
      DvmDex* pDvmDex = meth->clazz->pDvmDex;
      DecodedInstruction decInsn;
      const char* classDescriptor;
      u4 idx;
  
      decodeInstruction(meth, insnIdx, &decInsn);
      idx = decInsn.vB;       // 2nd item
      if (idx >= pDvmDex->pHeader->typeIdsSize) {
          LOG_VFY_METH(meth, "VFY: bad type index %d (max %d)\n",
              idx, pDvmDex->pHeader->typeIdsSize);
          return false;
      }
  
      classDescriptor = dexStringByTypeIdx(pDvmDex->pDexFile, idx);
      if (classDescriptor[0] != 'L') {
          LOG_VFY_METH(meth, "VFY: can't call new-instance on type '%s'\n",
              classDescriptor);
          return false;
      }
  
      return true;
  }
  
  /*
   * Perform static checks on a "new-array" instruction.  Specifically, make
   * sure they aren't creating an array of arrays that causes the number of
   * dimensions to exceed 255.
   */
  static bool checkNewArray(const Method* meth, int insnIdx)
  {
      DvmDex* pDvmDex = meth->clazz->pDvmDex;
      DecodedInstruction decInsn;
      const char* classDescriptor;
      u4 idx;
  
      decodeInstruction(meth, insnIdx, &decInsn);
      idx = decInsn.vC;       // 3rd item
      if (idx >= pDvmDex->pHeader->typeIdsSize) {
          LOG_VFY_METH(meth, "VFY: bad type index %d (max %d)\n",
              idx, pDvmDex->pHeader->typeIdsSize);
          return false;
      }
  
      classDescriptor = dexStringByTypeIdx(pDvmDex->pDexFile, idx);
  
      int bracketCount = 0;
      const char* cp = classDescriptor;
      while (*cp++ == '[')
          bracketCount++;
  
      if (bracketCount == 0) {
          /* The given class must be an array type. */
          LOG_VFY_METH(meth, "VFY: can't new-array class '%s' (not an array)\n",
              classDescriptor);
          return false;
      } else if (bracketCount > 255) {
          /* It is illegal to create an array of more than 255 dimensions. */
          LOG_VFY_METH(meth, "VFY: can't new-array class '%s' (exceeds limit)\n",
              classDescriptor);
          return false;
      }
  
      return true;
  }
  
  /*
   * Perform static checks on an instruction that takes a class constant.
   * Ensure that the class index is in the valid range.
   */
  static bool checkTypeIndex(const Method* meth, int insnIdx, bool useB)
  {
      DvmDex* pDvmDex = meth->clazz->pDvmDex;
      DecodedInstruction decInsn;
      u4 idx;
  
      decodeInstruction(meth, insnIdx, &decInsn);
      if (useB)
          idx = decInsn.vB;
      else
          idx = decInsn.vC;
      if (idx >= pDvmDex->pHeader->typeIdsSize) {
          LOG_VFY_METH(meth, "VFY: bad type index %d (max %d)\n",
              idx, pDvmDex->pHeader->typeIdsSize);
          return false;
      }
  
      return true;
  }
  
  /*
   * Perform static checks on a field get or set instruction.  All we do
   * here is ensure that the field index is in the valid range.
   */
  static bool checkFieldIndex(const Method* meth, int insnIdx, bool useB)
  {
      DvmDex* pDvmDex = meth->clazz->pDvmDex;
      DecodedInstruction decInsn;
      u4 idx;
  
      decodeInstruction(meth, insnIdx, &decInsn);
      if (useB)
          idx = decInsn.vB;
      else
          idx = decInsn.vC;
      if (idx >= pDvmDex->pHeader->fieldIdsSize) {
          LOG_VFY_METH(meth,
              "VFY: bad field index %d (max %d) at offset 0x%04x\n",
              idx, pDvmDex->pHeader->fieldIdsSize, insnIdx);
          return false;
      }
  
      return true;
  }
  
  /*
   * Perform static checks on a method invocation instruction.  All we do
   * here is ensure that the method index is in the valid range.
   */
  static bool checkMethodIndex(const Method* meth, int insnIdx)
  {
      DvmDex* pDvmDex = meth->clazz->pDvmDex;
      DecodedInstruction decInsn;
  
      decodeInstruction(meth, insnIdx, &decInsn);
      if (decInsn.vB >= pDvmDex->pHeader->methodIdsSize) {
          LOG_VFY_METH(meth, "VFY: bad method index %d (max %d)\n",
              decInsn.vB, pDvmDex->pHeader->methodIdsSize);
          return false;
      }
  
      return true;
  }
  
  /*
   * Perform static checks on a string constant instruction.  All we do
   * here is ensure that the string index is in the valid range.
   */
  static bool checkStringIndex(const Method* meth, int insnIdx)
  {
      DvmDex* pDvmDex = meth->clazz->pDvmDex;
      DecodedInstruction decInsn;
  
      decodeInstruction(meth, insnIdx, &decInsn);
      if (decInsn.vB >= pDvmDex->pHeader->stringIdsSize) {
          LOG_VFY_METH(meth, "VFY: bad string index %d (max %d)\n",
              decInsn.vB, pDvmDex->pHeader->stringIdsSize);
          return false;
      }
  
      return true;
  }
  
  /*
   * Perform static verification on instructions.
   *
   * As a side effect, this sets the "branch target" flags in InsnFlags.
   *
   * "(CF)" items are handled during code-flow analysis.
   *
   * v3 4.10.1
   * - target of each jump and branch instruction must be valid
   * - targets of switch statements must be valid
   * - (CF) operands referencing constant pool entries must be valid
   * - (CF) operands of getfield, putfield, getstatic, putstatic must be valid
   * - (new) verify operands of "quick" field ops
   * - (CF) operands of method invocation instructions must be valid
   * - (new) verify operands of "quick" method invoke ops
   * - (CF) only invoke-direct can call a method starting with '<'
   * - (CF) <clinit> must never be called explicitly
   * - (CF) operands of instanceof, checkcast, new (and variants) must be valid
   * - new-array[-type] limited to 255 dimensions
   * - can't use "new" on an array class
   * - (?) limit dimensions in multi-array creation
   * - (CF) local variable load/store register values must be in valid range
   *
   * v3 4.11.1.2
   * - branches must be within the bounds of the code array
   * - targets of all control-flow instructions are the start of an instruction
   * - (CF) register accesses fall within range of allocated registers
   * - (N/A) access to constant pool must be of appropriate type
   * - (CF) code does not end in the middle of an instruction
   * - (CF) execution cannot fall off the end of the code
   * - (earlier) for each exception handler, the "try" area must begin and
   *   end at the start of an instruction (end can be at the end of the code)
   * - (earlier) for each exception handler, the handler must start at a valid
   *   instruction
   *
   * TODO: move some of the "CF" items in here for better performance (the
   * code-flow analysis sometimes has to process the same instruction several
   * times).
   */
  static bool verifyInstructions(const Method* meth, InsnFlags* insnFlags,
      int verifyFlags)
  {
      const int insnCount = dvmGetMethodInsnsSize(meth);
      const u2* insns = meth->insns;
      int i;
  
      /* the start of the method is a "branch target" */
      dvmInsnSetBranchTarget(insnFlags, 0, true);
  
      for (i = 0; i < insnCount; /**/) {
          static int gcMask = kInstrCanBranch | kInstrCanSwitch |
              kInstrCanThrow | kInstrCanReturn;
          int width = dvmInsnGetWidth(insnFlags, i);
          OpCode opcode = *insns & 0xff;
          InstructionFlags opFlags = dexGetInstrFlags(gDvm.instrFlags, opcode);
          int offset, absOffset;
  
          if ((opFlags & gcMask) != 0)
              dvmInsnSetGcPoint(insnFlags, i, true);
  
          switch (opcode) {
          case OP_NOP:
              /* plain no-op or switch table data; nothing to do here */
              break;
  
          case OP_CONST_STRING:
          case OP_CONST_STRING_JUMBO:
              if (!checkStringIndex(meth, i))
                  return false;
              break;
  
          case OP_CONST_CLASS:
          case OP_CHECK_CAST:
              if (!checkTypeIndex(meth, i, true))
                  return false;
              break;
          case OP_INSTANCE_OF:
              if (!checkTypeIndex(meth, i, false))
                  return false;
              break;
  
          case OP_PACKED_SWITCH:
          case OP_SPARSE_SWITCH:
              /* verify the associated table */
              if (!dvmCheckSwitchTargets(meth, insnFlags, i))
                  return false;
              break;
  
          case OP_FILL_ARRAY_DATA:
              /* verify the associated table */
              if (!checkArrayData(meth, i))
                  return false;
              break;
  
          case OP_GOTO:
          case OP_GOTO_16:
          case OP_IF_EQ:
          case OP_IF_NE:
          case OP_IF_LT:
          case OP_IF_GE:
          case OP_IF_GT:
          case OP_IF_LE:
          case OP_IF_EQZ:
          case OP_IF_NEZ:
          case OP_IF_LTZ:
          case OP_IF_GEZ:
          case OP_IF_GTZ:
          case OP_IF_LEZ:
              /* check the destination */
              if (!dvmCheckBranchTarget(meth, insnFlags, i, false))
                  return false;
              break;
          case OP_GOTO_32:
              /* check the destination; self-branch is okay */
              if (!dvmCheckBranchTarget(meth, insnFlags, i, true))
                  return false;
              break;
  
          case OP_NEW_INSTANCE:
              if (!checkNewInstance(meth, i))
                  return false;
              break;
  
          case OP_NEW_ARRAY:
              if (!checkNewArray(meth, i))
                  return false;
              break;
  
          case OP_FILLED_NEW_ARRAY:
              if (!checkTypeIndex(meth, i, true))
                  return false;
              break;
          case OP_FILLED_NEW_ARRAY_RANGE:
              if (!checkTypeIndex(meth, i, true))
                  return false;
              break;
  
          case OP_IGET:
          case OP_IGET_WIDE:
          case OP_IGET_OBJECT:
          case OP_IGET_BOOLEAN:
          case OP_IGET_BYTE:
          case OP_IGET_CHAR:
          case OP_IGET_SHORT:
          case OP_IPUT:
          case OP_IPUT_WIDE:
          case OP_IPUT_OBJECT:
          case OP_IPUT_BOOLEAN:
          case OP_IPUT_BYTE:
          case OP_IPUT_CHAR:
          case OP_IPUT_SHORT:
              /* check the field index */
              if (!checkFieldIndex(meth, i, false))
                  return false;
              break;
          case OP_SGET:
          case OP_SGET_WIDE:
          case OP_SGET_OBJECT:
          case OP_SGET_BOOLEAN:
          case OP_SGET_BYTE:
          case OP_SGET_CHAR:
          case OP_SGET_SHORT:
          case OP_SPUT:
          case OP_SPUT_WIDE:
          case OP_SPUT_OBJECT:
          case OP_SPUT_BOOLEAN:
          case OP_SPUT_BYTE:
          case OP_SPUT_CHAR:
          case OP_SPUT_SHORT:
              /* check the field index */
              if (!checkFieldIndex(meth, i, true))
                  return false;
              break;
  
          case OP_INVOKE_VIRTUAL:
          case OP_INVOKE_SUPER:
          case OP_INVOKE_DIRECT:
          case OP_INVOKE_STATIC:
          case OP_INVOKE_INTERFACE:
          case OP_INVOKE_VIRTUAL_RANGE:
          case OP_INVOKE_SUPER_RANGE:
          case OP_INVOKE_DIRECT_RANGE:
          case OP_INVOKE_STATIC_RANGE:
          case OP_INVOKE_INTERFACE_RANGE:
              /* check the method index */
              if (!checkMethodIndex(meth, i))
                  return false;
              break;
  
          case OP_EXECUTE_INLINE:
          case OP_INVOKE_DIRECT_EMPTY:
          case OP_IGET_QUICK:
          case OP_IGET_WIDE_QUICK:
          case OP_IGET_OBJECT_QUICK:
          case OP_IPUT_QUICK:
          case OP_IPUT_WIDE_QUICK:
          case OP_IPUT_OBJECT_QUICK:
          case OP_INVOKE_VIRTUAL_QUICK:
          case OP_INVOKE_VIRTUAL_QUICK_RANGE:
          case OP_INVOKE_SUPER_QUICK:
          case OP_INVOKE_SUPER_QUICK_RANGE:
              if ((verifyFlags & VERIFY_ALLOW_OPT_INSTRS) == 0) {
                  LOG_VFY("VFY: not expecting optimized instructions\n");
                  return false;
              }
              break;
  
          default:
              /* nothing to do */
              break;
          }
  
          assert(width > 0);
          i += width;
          insns += width;
      }
  
      /* make sure the last instruction ends at the end of the insn area */
      if (i != insnCount) {
          LOG_VFY_METH(meth,
              "VFY: code did not end when expected (end at %d, count %d)\n",
              i, insnCount);
          return false;
      }
  
      return true;
  }
  
  