1701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden/* 2701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * Copyright (C) 2010 The Android Open Source Project 3701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * 4701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * Licensed under the Apache License, Version 2.0 (the "License"); 5701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * you may not use this file except in compliance with the License. 6701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * You may obtain a copy of the License at 7701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * 8701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * http://www.apache.org/licenses/LICENSE-2.0 9701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * 10701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * Unless required by applicable law or agreed to in writing, software 11701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * distributed under the License is distributed on an "AS IS" BASIS, 12701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * See the License for the specific language governing permissions and 14701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * limitations under the License. 15701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden */ 16701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 17701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden/* 18701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * Verifier basic block functions. 19701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden */ 20701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden#include "Dalvik.h" 21701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden#include "analysis/VfyBasicBlock.h" 22701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden#include "analysis/CodeVerify.h" 23701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden#include "analysis/VerifySubs.h" 24701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden#include "libdex/DexCatch.h" 25701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden#include "libdex/InstrUtils.h" 26701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 27701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 28701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden/* 29701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * Extract the list of catch handlers from "pTry" into "addrBuf". 30701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * 31701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * Returns the size of the catch handler list. If the return value 32701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * exceeds "addrBufSize", the items at the end of the list will not be 33701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * represented in the output array, and this function should be called 34701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * again with a larger buffer. 35701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden */ 36701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFaddenstatic u4 extractCatchHandlers(const DexCode* pCode, const DexTry* pTry, 37701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden u4* addrBuf, size_t addrBufSize) 38701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden{ 39701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden DexCatchIterator iterator; 40701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden unsigned int idx = 0; 41701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 42701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden dexCatchIteratorInit(&iterator, pCode, pTry->handlerOff); 43701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden while (true) { 44701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden DexCatchHandler* handler = dexCatchIteratorNext(&iterator); 45701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden if (handler == NULL) 46701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden break; 47701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 48701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden if (idx < addrBufSize) { 49701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden addrBuf[idx] = handler->address; 50701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden } 51701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden idx++; 52701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden } 53701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 54701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden return idx; 55701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden} 56701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 57701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden/* 58701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * Returns "true" if the instruction represents a data chunk, such as a 59701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * switch statement block. 60701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden */ 61701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFaddenstatic bool isDataChunk(u2 insn) 62701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden{ 63701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden return (insn == kPackedSwitchSignature || 64701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden insn == kSparseSwitchSignature || 65701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden insn == kArrayDataSignature); 66701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden} 67701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 68701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden/* 69701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * Alloc a basic block in the specified slot. The storage will be 70701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * initialized. 71701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden */ 72701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFaddenstatic VfyBasicBlock* allocVfyBasicBlock(VerifierData* vdata, u4 idx) 73701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden{ 74701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden VfyBasicBlock* newBlock = (VfyBasicBlock*) calloc(1, sizeof(VfyBasicBlock)); 75701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden if (newBlock == NULL) 76701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden return NULL; 77701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 789fd527f3258381b33365cb18fd37c7864e2bbb40Andy McFadden /* 799fd527f3258381b33365cb18fd37c7864e2bbb40Andy McFadden * TODO: there is no good default size here -- the problem is that most 809fd527f3258381b33365cb18fd37c7864e2bbb40Andy McFadden * addresses will only have one predecessor, but a fair number will 819fd527f3258381b33365cb18fd37c7864e2bbb40Andy McFadden * have 10+, and a few will have 100+ (e.g. the synthetic "finally" 829fd527f3258381b33365cb18fd37c7864e2bbb40Andy McFadden * in a large synchronized method). We probably want to use a small 839fd527f3258381b33365cb18fd37c7864e2bbb40Andy McFadden * base allocation (perhaps two) and then have the first overflow 849fd527f3258381b33365cb18fd37c7864e2bbb40Andy McFadden * allocation jump dramatically (to 32 or thereabouts). 859fd527f3258381b33365cb18fd37c7864e2bbb40Andy McFadden */ 869fd527f3258381b33365cb18fd37c7864e2bbb40Andy McFadden newBlock->predecessors = dvmPointerSetAlloc(32); 87701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden if (newBlock->predecessors == NULL) { 88701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden free(newBlock); 89701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden return NULL; 90701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden } 91701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 92701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden newBlock->firstAddr = (u4) -1; // DEBUG 93701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 949fd527f3258381b33365cb18fd37c7864e2bbb40Andy McFadden newBlock->liveRegs = dvmAllocBitVector(vdata->insnRegCount, false); 959fd527f3258381b33365cb18fd37c7864e2bbb40Andy McFadden if (newBlock->liveRegs == NULL) { 969fd527f3258381b33365cb18fd37c7864e2bbb40Andy McFadden dvmPointerSetFree(newBlock->predecessors); 979fd527f3258381b33365cb18fd37c7864e2bbb40Andy McFadden free(newBlock); 989fd527f3258381b33365cb18fd37c7864e2bbb40Andy McFadden return NULL; 999fd527f3258381b33365cb18fd37c7864e2bbb40Andy McFadden } 1009fd527f3258381b33365cb18fd37c7864e2bbb40Andy McFadden 101701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden return newBlock; 102701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden} 103701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 104701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden/* 105701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * Add "curBlock" to the predecessor list in "targetIdx". 106701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden */ 107701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFaddenstatic bool addToPredecessor(VerifierData* vdata, VfyBasicBlock* curBlock, 108701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden u4 targetIdx) 109701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden{ 110701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden assert(targetIdx < vdata->insnsSize); 111701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 112701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden /* 113701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * Allocate the target basic block if necessary. This will happen 114701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * on e.g. forward branches. 115701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * 116701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * We can't fill in all the fields, but that will happen automatically 117701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * when we get to that part of the code. 118701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden */ 119701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden VfyBasicBlock* targetBlock = vdata->basicBlocks[targetIdx]; 120701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden if (targetBlock == NULL) { 121701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden targetBlock = allocVfyBasicBlock(vdata, targetIdx); 122701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden if (targetBlock == NULL) 123701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden return false; 124701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden vdata->basicBlocks[targetIdx] = targetBlock; 125701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden } 126701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 127701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden PointerSet* preds = targetBlock->predecessors; 128701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden bool added = dvmPointerSetAddEntry(preds, curBlock); 129701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden if (!added) { 130701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden /* 131701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * This happens sometimes for packed-switch instructions, where 132701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * the same target address appears more than once. Also, a 133701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * (pointless) conditional branch to the next instruction will 134701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * trip over this. 135701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden */ 13692c1f6f1b4249e4e379452ee7b49f027052bf4ceSteve Block ALOGV("ODD: point set for targ=0x%04x (%p) already had block " 1376f3c21fb026d9489e5046416bcd5a84fa8e4615bDan Bornstein "fir=0x%04x (%p)", 138701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden targetIdx, targetBlock, curBlock->firstAddr, curBlock); 139701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden } 140701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 141701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden return true; 142701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden} 143701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 144701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden/* 145701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * Add ourselves to the predecessor list in all blocks we might transfer 146701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * control to. 147701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * 148701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * There are four ways to proceed to a new instruction: 149701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * (1) continue to the following instruction 150701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * (2) [un]conditionally branch to a specific location 151701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * (3) conditionally branch through a "switch" statement 152701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * (4) throw an exception 153701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * 154701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * Returning from the method (via a return statement or an uncaught 155701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * exception) are not interesting for liveness analysis. 156701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden */ 157701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFaddenstatic bool setPredecessors(VerifierData* vdata, VfyBasicBlock* curBlock, 158701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden u4 curIdx, OpcodeFlags opFlags, u4 nextIdx, u4* handlerList, 159701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden size_t numHandlers) 160701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden{ 161701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden const InsnFlags* insnFlags = vdata->insnFlags; 162701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden const Method* meth = vdata->method; 163701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 164701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden unsigned int handlerIdx; 165701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden for (handlerIdx = 0; handlerIdx < numHandlers; handlerIdx++) { 166701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden if (!addToPredecessor(vdata, curBlock, handlerList[handlerIdx])) 167701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden return false; 168701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden } 169701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 170701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden if ((opFlags & kInstrCanContinue) != 0) { 171701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden if (!addToPredecessor(vdata, curBlock, nextIdx)) 172701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden return false; 173701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden } 174701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden if ((opFlags & kInstrCanBranch) != 0) { 175701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden bool unused, gotBranch; 176701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden s4 branchOffset, absOffset; 177701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 178701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden gotBranch = dvmGetBranchOffset(meth, insnFlags, curIdx, 179701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden &branchOffset, &unused); 180701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden assert(gotBranch); 181701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden absOffset = curIdx + branchOffset; 182701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden assert(absOffset >= 0 && (u4) absOffset < vdata->insnsSize); 183701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 184701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden if (!addToPredecessor(vdata, curBlock, absOffset)) 185701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden return false; 186701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden } 187701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 188701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden if ((opFlags & kInstrCanSwitch) != 0) { 189701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden const u2* curInsn = &meth->insns[curIdx]; 190701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden const u2* dataPtr; 191701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 192701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden /* these values have already been verified, so we can trust them */ 193701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden s4 offsetToData = curInsn[1] | ((s4) curInsn[2]) << 16; 194701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden dataPtr = curInsn + offsetToData; 195701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 196701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden /* 197701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * dataPtr points to the start of the switch data. The first 198701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * item is the NOP+magic, the second is the number of entries in 199701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * the switch table. 200701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden */ 201701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden u2 switchCount = dataPtr[1]; 202701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 203701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden /* 204701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * Skip past the ident field, size field, and the first_key field 205701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * (for packed) or the key list (for sparse). 206701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden */ 207701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden if (dexOpcodeFromCodeUnit(meth->insns[curIdx]) == OP_PACKED_SWITCH) { 208701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden dataPtr += 4; 209701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden } else { 210701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden assert(dexOpcodeFromCodeUnit(meth->insns[curIdx]) == 211701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden OP_SPARSE_SWITCH); 212701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden dataPtr += 2 + 2 * switchCount; 213701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden } 214701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 215701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden u4 switchIdx; 216701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden for (switchIdx = 0; switchIdx < switchCount; switchIdx++) { 217701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden s4 offset, absOffset; 218701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 219701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden offset = (s4) dataPtr[switchIdx*2] | 220701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden (s4) (dataPtr[switchIdx*2 +1] << 16); 221701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden absOffset = curIdx + offset; 222701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden assert(absOffset >= 0 && (u4) absOffset < vdata->insnsSize); 223701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 224701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden if (!addToPredecessor(vdata, curBlock, absOffset)) 225701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden return false; 226701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden } 227701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden } 228701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 2299fd527f3258381b33365cb18fd37c7864e2bbb40Andy McFadden if (false) { 2309fd527f3258381b33365cb18fd37c7864e2bbb40Andy McFadden if (dvmPointerSetGetCount(curBlock->predecessors) > 256) { 2314308417beec548c2b2c06ecec4f7f4a965b09fb2Steve Block ALOGI("Lots of preds at 0x%04x in %s.%s:%s", curIdx, 2329fd527f3258381b33365cb18fd37c7864e2bbb40Andy McFadden meth->clazz->descriptor, meth->name, meth->shorty); 2339fd527f3258381b33365cb18fd37c7864e2bbb40Andy McFadden } 2349fd527f3258381b33365cb18fd37c7864e2bbb40Andy McFadden } 2359fd527f3258381b33365cb18fd37c7864e2bbb40Andy McFadden 236701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden return true; 237701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden} 238701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 239701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden/* 240701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * Dump the contents of the basic blocks. 241701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden */ 242701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFaddenstatic void dumpBasicBlocks(const VerifierData* vdata) 243701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden{ 244701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden char printBuf[256]; 245701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden unsigned int idx; 246701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden int count; 247701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 2484308417beec548c2b2c06ecec4f7f4a965b09fb2Steve Block ALOGI("Basic blocks for %s.%s:%s", vdata->method->clazz->descriptor, 249701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden vdata->method->name, vdata->method->shorty); 250701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden for (idx = 0; idx < vdata->insnsSize; idx++) { 251701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden VfyBasicBlock* block = vdata->basicBlocks[idx]; 252701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden if (block == NULL) 253701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden continue; 254701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 255701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden assert(block->firstAddr == idx); 256701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden count = snprintf(printBuf, sizeof(printBuf), " %04x-%04x ", 257701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden block->firstAddr, block->lastAddr); 258701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 259701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden PointerSet* preds = block->predecessors; 2609fd527f3258381b33365cb18fd37c7864e2bbb40Andy McFadden size_t numPreds = dvmPointerSetGetCount(preds); 261701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 2629fd527f3258381b33365cb18fd37c7864e2bbb40Andy McFadden if (numPreds > 0) { 263701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden count += snprintf(printBuf + count, sizeof(printBuf) - count, 264701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden "preds:"); 265701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 266701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden unsigned int predIdx; 2679fd527f3258381b33365cb18fd37c7864e2bbb40Andy McFadden for (predIdx = 0; predIdx < numPreds; predIdx++) { 268701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden if (count >= (int) sizeof(printBuf)) 269701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden break; 270701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden const VfyBasicBlock* pred = 271701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden (const VfyBasicBlock*) dvmPointerSetGetEntry(preds, predIdx); 272701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden count += snprintf(printBuf + count, sizeof(printBuf) - count, 273701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden "%04x(%p),", pred->firstAddr, pred); 274701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden } 275701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden } else { 276701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden count += snprintf(printBuf + count, sizeof(printBuf) - count, 277701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden "(no preds)"); 278701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden } 279701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 2809fd527f3258381b33365cb18fd37c7864e2bbb40Andy McFadden printBuf[sizeof(printBuf)-2] = '!'; 2819fd527f3258381b33365cb18fd37c7864e2bbb40Andy McFadden printBuf[sizeof(printBuf)-1] = '\0'; 2829fd527f3258381b33365cb18fd37c7864e2bbb40Andy McFadden 2834308417beec548c2b2c06ecec4f7f4a965b09fb2Steve Block ALOGI("%s", printBuf); 284701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden } 2859fd527f3258381b33365cb18fd37c7864e2bbb40Andy McFadden 2869fd527f3258381b33365cb18fd37c7864e2bbb40Andy McFadden usleep(100 * 1000); /* ugh...let logcat catch up */ 287701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden} 288701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 289701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 290701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden/* 291701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * Generate a list of basic blocks and related information. 292701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * 293701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * On success, returns "true" with vdata->basicBlocks initialized. 294701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden */ 295701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFaddenbool dvmComputeVfyBasicBlocks(VerifierData* vdata) 296701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden{ 297701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden const InsnFlags* insnFlags = vdata->insnFlags; 298701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden const Method* meth = vdata->method; 299701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden const u4 insnsSize = vdata->insnsSize; 300701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden const DexCode* pCode = dvmGetMethodCode(meth); 301701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden const DexTry* pTries = NULL; 302701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden const size_t kHandlerStackAllocSize = 16; /* max seen so far is 7 */ 303701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden u4 handlerAddrs[kHandlerStackAllocSize]; 304701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden u4* handlerListAlloc = NULL; 305701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden u4* handlerList = NULL; 306701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden size_t numHandlers = 0; 307701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden u4 idx, blockStartAddr; 308701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden bool result = false; 309701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 3109fd527f3258381b33365cb18fd37c7864e2bbb40Andy McFadden bool verbose = false; //dvmWantVerboseVerification(meth); 311701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden if (verbose) { 3124308417beec548c2b2c06ecec4f7f4a965b09fb2Steve Block ALOGI("Basic blocks for %s.%s:%s", 313701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden meth->clazz->descriptor, meth->name, meth->shorty); 314701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden } 315701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 316701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden /* 317701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * Allocate a data structure that allows us to map from an address to 318701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * the corresponding basic block. Initially all pointers are NULL. 319701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * They are populated on demand as we proceed (either when we reach a 320701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * new BB, or when we need to add an item to the predecessor list in 321701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * a not-yet-reached BB). 322701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * 323701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * Only the first instruction in the block points to the BB structure; 324701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * the rest remain NULL. 325701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden */ 326701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden vdata->basicBlocks = 327701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden (VfyBasicBlock**) calloc(insnsSize, sizeof(VfyBasicBlock*)); 328701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden if (vdata->basicBlocks == NULL) 3291813ab265f691e93401c7307c0b34247842ab35eCarl Shapiro return false; 330701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 331701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden /* 332701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * The "tries" list is a series of non-overlapping regions with a list 333701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * of "catch" handlers. Rather than do the "find a matching try block" 334701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * computation at each step, we just walk the "try" list in parallel. 335701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * 336701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * Not all methods have "try" blocks. If this one does, we init tryEnd 337701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * to zero, so that the (exclusive bound) range check trips immediately. 338701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden */ 339701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden u4 tryIndex = 0, tryStart = 0, tryEnd = 0; 340701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden if (pCode->triesSize != 0) { 341701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden pTries = dexGetTries(pCode); 342701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden } 343701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 344701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden u4 debugBBIndex = 0; 345701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 346701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden /* 347701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * The address associated with a basic block is the start address. 348701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden */ 349701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden blockStartAddr = 0; 350701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 351701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden for (idx = 0; idx < insnsSize; ) { 352701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden /* 353701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * Make sure we're pointing at the right "try" block. It should 354701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * not be possible to "jump over" a block, so if we're no longer 355701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * in the correct one we can just advance to the next. 356701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden */ 357701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden if (pTries != NULL && idx >= tryEnd) { 358701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden if (tryIndex == pCode->triesSize) { 359701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden /* no more try blocks in this method */ 360701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden pTries = NULL; 361701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden numHandlers = 0; 362701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden } else { 363701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden /* 364701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * Extract the set of handlers. We want to avoid doing 365701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * this for each block, so we copy them to local storage. 366701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * If it doesn't fit in the small stack area, we'll use 367701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * the heap instead. 368701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * 369701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * It's rare to encounter a method with more than half a 370701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * dozen possible handlers. 371701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden */ 372701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden tryStart = pTries[tryIndex].startAddr; 373701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden tryEnd = tryStart + pTries[tryIndex].insnCount; 374701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 375701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden if (handlerListAlloc != NULL) { 376701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden free(handlerListAlloc); 377701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden handlerListAlloc = NULL; 378701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden } 379701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden numHandlers = extractCatchHandlers(pCode, &pTries[tryIndex], 380701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden handlerAddrs, kHandlerStackAllocSize); 381701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden assert(numHandlers > 0); // TODO make sure this is verified 382701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden if (numHandlers <= kHandlerStackAllocSize) { 383701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden handlerList = handlerAddrs; 384701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden } else { 385062bf509a77fce9dfcb7e7b2e401cf2a124d83d5Steve Block ALOGD("overflow, numHandlers=%d", numHandlers); 386701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden handlerListAlloc = (u4*) malloc(sizeof(u4) * numHandlers); 387701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden if (handlerListAlloc == NULL) 388701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden return false; 389701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden extractCatchHandlers(pCode, &pTries[tryIndex], 390701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden handlerListAlloc, numHandlers); 391701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden handlerList = handlerListAlloc; 392701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden } 393701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 39492c1f6f1b4249e4e379452ee7b49f027052bf4ceSteve Block ALOGV("+++ start=%x end=%x numHan=%d", 395701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden tryStart, tryEnd, numHandlers); 396701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 397701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden tryIndex++; 398701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden } 399701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden } 400701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 401701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden /* 402701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * Check the current instruction, and possibly aspects of the 403701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * next instruction, to see if this instruction ends the current 404701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * basic block. 405701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * 406701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * Instructions that can throw only end the block if there is the 407701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * possibility of a local handler catching the exception. 408701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden */ 409701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden Opcode opcode = dexOpcodeFromCodeUnit(meth->insns[idx]); 410701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden OpcodeFlags opFlags = dexGetFlagsFromOpcode(opcode); 411701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden size_t nextIdx = idx + dexGetWidthFromInstruction(&meth->insns[idx]); 412701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden bool endBB = false; 413701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden bool ignoreInstr = false; 414701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 415701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden if ((opFlags & kInstrCanContinue) == 0) { 416701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden /* does not continue */ 417701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden endBB = true; 418701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden } else if ((opFlags & (kInstrCanBranch | kInstrCanSwitch)) != 0) { 419701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden /* conditionally branches elsewhere */ 420701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden endBB = true; 421701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden } else if ((opFlags & kInstrCanThrow) != 0 && 422701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden dvmInsnIsInTry(insnFlags, idx)) 423701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden { 424701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden /* throws an exception that might be caught locally */ 425701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden endBB = true; 426701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden } else if (isDataChunk(meth->insns[idx])) { 427701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden /* 428701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * If this is a data chunk (e.g. switch data) we want to skip 429701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * over it entirely. Set endBB so we don't carry this along as 430701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * the start of a block, and ignoreInstr so we don't try to 431701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * open a basic block for this instruction. 432701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden */ 433701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden endBB = ignoreInstr = true; 434701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden } else if (dvmInsnIsBranchTarget(insnFlags, nextIdx)) { 435701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden /* 436701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * We also need to end it if the next instruction is a branch 437701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * target. Note we've tagged exception catch blocks as such. 438701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * 439701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * If we're this far along in the "else" chain, we know that 440701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * this isn't a data-chunk NOP, and control can continue to 441701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * the next instruction, so we're okay examining "nextIdx". 442701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden */ 443701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden assert(nextIdx < insnsSize); 444701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden endBB = true; 445701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden } else if (opcode == OP_NOP && isDataChunk(meth->insns[nextIdx])) { 446701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden /* 447701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * Handle an odd special case: if this is NOP padding before a 448701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * data chunk, also treat it as "ignore". Otherwise it'll look 449701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * like a block that starts and doesn't end. 450701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden */ 451701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden endBB = ignoreInstr = true; 452701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden } else { 453701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden /* check: return ops should be caught by absence of can-continue */ 454701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden assert((opFlags & kInstrCanReturn) == 0); 455701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden } 456701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 457701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden if (verbose) { 458701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden char btc = dvmInsnIsBranchTarget(insnFlags, idx) ? '>' : ' '; 459701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden char tryc = 460701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden (pTries != NULL && idx >= tryStart && idx < tryEnd) ? 't' : ' '; 461701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden bool startBB = (idx == blockStartAddr); 462701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden const char* startEnd; 463701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 464701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 465701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden if (ignoreInstr) 466701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden startEnd = "IGNORE"; 467701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden else if (startBB && endBB) 468701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden startEnd = "START/END"; 469701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden else if (startBB) 470701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden startEnd = "START"; 471701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden else if (endBB) 472701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden startEnd = "END"; 473701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden else 474701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden startEnd = "-"; 475701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 4764308417beec548c2b2c06ecec4f7f4a965b09fb2Steve Block ALOGI("%04x: %c%c%s #%d", idx, tryc, btc, startEnd, debugBBIndex); 477701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 478701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden if (pTries != NULL && idx == tryStart) { 479701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden assert(numHandlers > 0); 4804308417beec548c2b2c06ecec4f7f4a965b09fb2Steve Block ALOGI(" EXC block: [%04x, %04x) %d:(%04x...)", 481701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden tryStart, tryEnd, numHandlers, handlerList[0]); 482701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden } 483701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden } 484701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 485701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden if (idx != blockStartAddr) { 486701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden /* should not be a basic block struct associated with this addr */ 487701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden assert(vdata->basicBlocks[idx] == NULL); 488701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden } 489701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden if (endBB) { 490701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden if (!ignoreInstr) { 491701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden /* 492701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * Create a new BB if one doesn't already exist. 493701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden */ 494701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden VfyBasicBlock* curBlock = vdata->basicBlocks[blockStartAddr]; 495701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden if (curBlock == NULL) { 496701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden curBlock = allocVfyBasicBlock(vdata, blockStartAddr); 497701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden if (curBlock == NULL) 498701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden return false; 499701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden vdata->basicBlocks[blockStartAddr] = curBlock; 500701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden } 501701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 502701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden curBlock->firstAddr = blockStartAddr; 503701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden curBlock->lastAddr = idx; 504701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 505701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden if (!setPredecessors(vdata, curBlock, idx, opFlags, nextIdx, 506701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden handlerList, numHandlers)) 507701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden { 508701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden goto bail; 509701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden } 510701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden } 511701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 512701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden blockStartAddr = nextIdx; 513701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden debugBBIndex++; 514701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden } 515701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 516701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden idx = nextIdx; 517701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden } 518701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 519701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden assert(idx == insnsSize); 520701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 521701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden result = true; 522701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 523701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden if (verbose) 524701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden dumpBasicBlocks(vdata); 525701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 526701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFaddenbail: 527701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden free(handlerListAlloc); 528701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden return result; 529701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden} 530701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 531701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden/* 532701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden * Free the storage used by basic blocks. 533701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden */ 534701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFaddenvoid dvmFreeVfyBasicBlocks(VerifierData* vdata) 535701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden{ 536701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden unsigned int idx; 537701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 538701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden if (vdata->basicBlocks == NULL) 539701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden return; 540701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 541701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden for (idx = 0; idx < vdata->insnsSize; idx++) { 542701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden VfyBasicBlock* block = vdata->basicBlocks[idx]; 543701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden if (block == NULL) 544701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden continue; 545701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden 546701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden dvmPointerSetFree(block->predecessors); 547701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden free(block); 548701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden } 549701d2720fa693621a3c0c4d0bdf9e32e3eb8e731Andy McFadden} 550