/*
* Copyright (C) 2010 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.
*/
/*
* Verifier basic block functions.
*/
#include "Dalvik.h"
#include "analysis/VfyBasicBlock.h"
#include "analysis/CodeVerify.h"
#include "analysis/VerifySubs.h"
#include "libdex/DexCatch.h"
#include "libdex/InstrUtils.h"
/*
* Extract the list of catch handlers from "pTry" into "addrBuf".
*
* Returns the size of the catch handler list. If the return value
* exceeds "addrBufSize", the items at the end of the list will not be
* represented in the output array, and this function should be called
* again with a larger buffer.
*/
static u4 extractCatchHandlers(const DexCode* pCode, const DexTry* pTry,
u4* addrBuf, size_t addrBufSize)
{
DexCatchIterator iterator;
unsigned int idx = 0;
dexCatchIteratorInit(&iterator, pCode, pTry->handlerOff);
while (true) {
DexCatchHandler* handler = dexCatchIteratorNext(&iterator);
if (handler == NULL)
break;
if (idx < addrBufSize) {
addrBuf[idx] = handler->address;
}
idx++;
}
return idx;
}
/*
* Returns "true" if the instruction represents a data chunk, such as a
* switch statement block.
*/
static bool isDataChunk(u2 insn)
{
return (insn == kPackedSwitchSignature ||
insn == kSparseSwitchSignature ||
insn == kArrayDataSignature);
}
/*
* Alloc a basic block in the specified slot. The storage will be
* initialized.
*/
static VfyBasicBlock* allocVfyBasicBlock(VerifierData* vdata, u4 idx)
{
VfyBasicBlock* newBlock = (VfyBasicBlock*) calloc(1, sizeof(VfyBasicBlock));
if (newBlock == NULL)
return NULL;
/*
* TODO: there is no good default size here -- the problem is that most
* addresses will only have one predecessor, but a fair number will
* have 10+, and a few will have 100+ (e.g. the synthetic "finally"
* in a large synchronized method). We probably want to use a small
* base allocation (perhaps two) and then have the first overflow
* allocation jump dramatically (to 32 or thereabouts).
*/
newBlock->predecessors = dvmPointerSetAlloc(32);
if (newBlock->predecessors == NULL) {
free(newBlock);
return NULL;
}
newBlock->firstAddr = (u4) -1; // DEBUG
newBlock->liveRegs = dvmAllocBitVector(vdata->insnRegCount, false);
if (newBlock->liveRegs == NULL) {
dvmPointerSetFree(newBlock->predecessors);
free(newBlock);
return NULL;
}
return newBlock;
}
/*
* Add "curBlock" to the predecessor list in "targetIdx".
*/
static bool addToPredecessor(VerifierData* vdata, VfyBasicBlock* curBlock,
u4 targetIdx)
{
assert(targetIdx < vdata->insnsSize);
/*
* Allocate the target basic block if necessary. This will happen
* on e.g. forward branches.
*
* We can't fill in all the fields, but that will happen automatically
* when we get to that part of the code.
*/
VfyBasicBlock* targetBlock = vdata->basicBlocks[targetIdx];
if (targetBlock == NULL) {
targetBlock = allocVfyBasicBlock(vdata, targetIdx);
if (targetBlock == NULL)
return false;
vdata->basicBlocks[targetIdx] = targetBlock;
}
PointerSet* preds = targetBlock->predecessors;
bool added = dvmPointerSetAddEntry(preds, curBlock);
if (!added) {
/*
* This happens sometimes for packed-switch instructions, where
* the same target address appears more than once. Also, a
* (pointless) conditional branch to the next instruction will
* trip over this.
*/
ALOGV("ODD: point set for targ=0x%04x (%p) already had block "
"fir=0x%04x (%p)",
targetIdx, targetBlock, curBlock->firstAddr, curBlock);
}
return true;
}
/*
* Add ourselves to the predecessor list in all blocks we might transfer
* control to.
*
* There are four ways to proceed to a new instruction:
* (1) continue to the following instruction
* (2) [un]conditionally branch to a specific location
* (3) conditionally branch through a "switch" statement
* (4) throw an exception
*
* Returning from the method (via a return statement or an uncaught
* exception) are not interesting for liveness analysis.
*/
static bool setPredecessors(VerifierData* vdata, VfyBasicBlock* curBlock,
u4 curIdx, OpcodeFlags opFlags, u4 nextIdx, u4* handlerList,
size_t numHandlers)
{
const InsnFlags* insnFlags = vdata->insnFlags;
const Method* meth = vdata->method;
unsigned int handlerIdx;
for (handlerIdx = 0; handlerIdx < numHandlers; handlerIdx++) {
if (!addToPredecessor(vdata, curBlock, handlerList[handlerIdx]))
return false;
}
if ((opFlags & kInstrCanContinue) != 0) {
if (!addToPredecessor(vdata, curBlock, nextIdx))
return false;
}
if ((opFlags & kInstrCanBranch) != 0) {
bool unused, gotBranch;
s4 branchOffset, absOffset;
gotBranch = dvmGetBranchOffset(meth, insnFlags, curIdx,
&branchOffset, &unused);
assert(gotBranch);
absOffset = curIdx + branchOffset;
assert(absOffset >= 0 && (u4) absOffset < vdata->insnsSize);
if (!addToPredecessor(vdata, curBlock, absOffset))
return false;
}
if ((opFlags & kInstrCanSwitch) != 0) {
const u2* curInsn = &meth->insns[curIdx];
const u2* dataPtr;
/* these values have already been verified, so we can trust them */
s4 offsetToData = curInsn[1] | ((s4) curInsn[2]) << 16;
dataPtr = curInsn + offsetToData;
/*
* dataPtr points to the start of the switch data. The first
* item is the NOP+magic, the second is the number of entries in
* the switch table.
*/
u2 switchCount = dataPtr[1];
/*
* Skip past the ident field, size field, and the first_key field
* (for packed) or the key list (for sparse).
*/
if (dexOpcodeFromCodeUnit(meth->insns[curIdx]) == OP_PACKED_SWITCH) {
dataPtr += 4;
} else {
assert(dexOpcodeFromCodeUnit(meth->insns[curIdx]) ==
OP_SPARSE_SWITCH);
dataPtr += 2 + 2 * switchCount;
}
u4 switchIdx;
for (switchIdx = 0; switchIdx < switchCount; switchIdx++) {
s4 offset, absOffset;
offset = (s4) dataPtr[switchIdx*2] |
(s4) (dataPtr[switchIdx*2 +1] << 16);
absOffset = curIdx + offset;
assert(absOffset >= 0 && (u4) absOffset < vdata->insnsSize);
if (!addToPredecessor(vdata, curBlock, absOffset))
return false;
}
}
if (false) {
if (dvmPointerSetGetCount(curBlock->predecessors) > 256) {
ALOGI("Lots of preds at 0x%04x in %s.%s:%s", curIdx,
meth->clazz->descriptor, meth->name, meth->shorty);
}
}
return true;
}
/*
* Dump the contents of the basic blocks.
*/
static void dumpBasicBlocks(const VerifierData* vdata)
{
char printBuf[256];
unsigned int idx;
int count;
ALOGI("Basic blocks for %s.%s:%s", vdata->method->clazz->descriptor,
vdata->method->name, vdata->method->shorty);
for (idx = 0; idx < vdata->insnsSize; idx++) {
VfyBasicBlock* block = vdata->basicBlocks[idx];
if (block == NULL)
continue;
assert(block->firstAddr == idx);
count = snprintf(printBuf, sizeof(printBuf), " %04x-%04x ",
block->firstAddr, block->lastAddr);
PointerSet* preds = block->predecessors;
size_t numPreds = dvmPointerSetGetCount(preds);
if (numPreds > 0) {
count += snprintf(printBuf + count, sizeof(printBuf) - count,
"preds:");
unsigned int predIdx;
for (predIdx = 0; predIdx < numPreds; predIdx++) {
if (count >= (int) sizeof(printBuf))
break;
const VfyBasicBlock* pred =
(const VfyBasicBlock*) dvmPointerSetGetEntry(preds, predIdx);
count += snprintf(printBuf + count, sizeof(printBuf) - count,
"%04x(%p),", pred->firstAddr, pred);
}
} else {
count += snprintf(printBuf + count, sizeof(printBuf) - count,
"(no preds)");
}
printBuf[sizeof(printBuf)-2] = '!';
printBuf[sizeof(printBuf)-1] = '\0';
ALOGI("%s", printBuf);
}
usleep(100 * 1000); /* ugh...let logcat catch up */
}
/*
* Generate a list of basic blocks and related information.
*
* On success, returns "true" with vdata->basicBlocks initialized.
*/
bool dvmComputeVfyBasicBlocks(VerifierData* vdata)
{
const InsnFlags* insnFlags = vdata->insnFlags;
const Method* meth = vdata->method;
const u4 insnsSize = vdata->insnsSize;
const DexCode* pCode = dvmGetMethodCode(meth);
const DexTry* pTries = NULL;
const size_t kHandlerStackAllocSize = 16; /* max seen so far is 7 */
u4 handlerAddrs[kHandlerStackAllocSize];
u4* handlerListAlloc = NULL;
u4* handlerList = NULL;
size_t numHandlers = 0;
u4 idx, blockStartAddr;
bool result = false;
bool verbose = false; //dvmWantVerboseVerification(meth);
if (verbose) {
ALOGI("Basic blocks for %s.%s:%s",
meth->clazz->descriptor, meth->name, meth->shorty);
}
/*
* Allocate a data structure that allows us to map from an address to
* the corresponding basic block. Initially all pointers are NULL.
* They are populated on demand as we proceed (either when we reach a
* new BB, or when we need to add an item to the predecessor list in
* a not-yet-reached BB).
*
* Only the first instruction in the block points to the BB structure;
* the rest remain NULL.
*/
vdata->basicBlocks =
(VfyBasicBlock**) calloc(insnsSize, sizeof(VfyBasicBlock*));
if (vdata->basicBlocks == NULL)
return false;
/*
* The "tries" list is a series of non-overlapping regions with a list
* of "catch" handlers. Rather than do the "find a matching try block"
* computation at each step, we just walk the "try" list in parallel.
*
* Not all methods have "try" blocks. If this one does, we init tryEnd
* to zero, so that the (exclusive bound) range check trips immediately.
*/
u4 tryIndex = 0, tryStart = 0, tryEnd = 0;
if (pCode->triesSize != 0) {
pTries = dexGetTries(pCode);
}
u4 debugBBIndex = 0;
/*
* The address associated with a basic block is the start address.
*/
blockStartAddr = 0;
for (idx = 0; idx < insnsSize; ) {
/*
* Make sure we're pointing at the right "try" block. It should
* not be possible to "jump over" a block, so if we're no longer
* in the correct one we can just advance to the next.
*/
if (pTries != NULL && idx >= tryEnd) {
if (tryIndex == pCode->triesSize) {
/* no more try blocks in this method */
pTries = NULL;
numHandlers = 0;
} else {
/*
* Extract the set of handlers. We want to avoid doing
* this for each block, so we copy them to local storage.
* If it doesn't fit in the small stack area, we'll use
* the heap instead.
*
* It's rare to encounter a method with more than half a
* dozen possible handlers.
*/
tryStart = pTries[tryIndex].startAddr;
tryEnd = tryStart + pTries[tryIndex].insnCount;
if (handlerListAlloc != NULL) {
free(handlerListAlloc);
handlerListAlloc = NULL;
}
numHandlers = extractCatchHandlers(pCode, &pTries[tryIndex],
handlerAddrs, kHandlerStackAllocSize);
assert(numHandlers > 0); // TODO make sure this is verified
if (numHandlers <= kHandlerStackAllocSize) {
handlerList = handlerAddrs;
} else {
ALOGD("overflow, numHandlers=%d", numHandlers);
handlerListAlloc = (u4*) malloc(sizeof(u4) * numHandlers);
if (handlerListAlloc == NULL)
return false;
extractCatchHandlers(pCode, &pTries[tryIndex],
handlerListAlloc, numHandlers);
handlerList = handlerListAlloc;
}
ALOGV("+++ start=%x end=%x numHan=%d",
tryStart, tryEnd, numHandlers);
tryIndex++;
}
}
/*
* Check the current instruction, and possibly aspects of the
* next instruction, to see if this instruction ends the current
* basic block.
*
* Instructions that can throw only end the block if there is the
* possibility of a local handler catching the exception.
*/
Opcode opcode = dexOpcodeFromCodeUnit(meth->insns[idx]);
OpcodeFlags opFlags = dexGetFlagsFromOpcode(opcode);
size_t nextIdx = idx + dexGetWidthFromInstruction(&meth->insns[idx]);
bool endBB = false;
bool ignoreInstr = false;
if ((opFlags & kInstrCanContinue) == 0) {
/* does not continue */
endBB = true;
} else if ((opFlags & (kInstrCanBranch | kInstrCanSwitch)) != 0) {
/* conditionally branches elsewhere */
endBB = true;
} else if ((opFlags & kInstrCanThrow) != 0 &&
dvmInsnIsInTry(insnFlags, idx))
{
/* throws an exception that might be caught locally */
endBB = true;
} else if (isDataChunk(meth->insns[idx])) {
/*
* If this is a data chunk (e.g. switch data) we want to skip
* over it entirely. Set endBB so we don't carry this along as
* the start of a block, and ignoreInstr so we don't try to
* open a basic block for this instruction.
*/
endBB = ignoreInstr = true;
} else if (dvmInsnIsBranchTarget(insnFlags, nextIdx)) {
/*
* We also need to end it if the next instruction is a branch
* target. Note we've tagged exception catch blocks as such.
*
* If we're this far along in the "else" chain, we know that
* this isn't a data-chunk NOP, and control can continue to
* the next instruction, so we're okay examining "nextIdx".
*/
assert(nextIdx < insnsSize);
endBB = true;
} else if (opcode == OP_NOP && isDataChunk(meth->insns[nextIdx])) {
/*
* Handle an odd special case: if this is NOP padding before a
* data chunk, also treat it as "ignore". Otherwise it'll look
* like a block that starts and doesn't end.
*/
endBB = ignoreInstr = true;
} else {
/* check: return ops should be caught by absence of can-continue */
assert((opFlags & kInstrCanReturn) == 0);
}
if (verbose) {
char btc = dvmInsnIsBranchTarget(insnFlags, idx) ? '>' : ' ';
char tryc =
(pTries != NULL && idx >= tryStart && idx < tryEnd) ? 't' : ' ';
bool startBB = (idx == blockStartAddr);
const char* startEnd;
if (ignoreInstr)
startEnd = "IGNORE";
else if (startBB && endBB)
startEnd = "START/END";
else if (startBB)
startEnd = "START";
else if (endBB)
startEnd = "END";
else
startEnd = "-";
ALOGI("%04x: %c%c%s #%d", idx, tryc, btc, startEnd, debugBBIndex);
if (pTries != NULL && idx == tryStart) {
assert(numHandlers > 0);
ALOGI(" EXC block: [%04x, %04x) %d:(%04x...)",
tryStart, tryEnd, numHandlers, handlerList[0]);
}
}
if (idx != blockStartAddr) {
/* should not be a basic block struct associated with this addr */
assert(vdata->basicBlocks[idx] == NULL);
}
if (endBB) {
if (!ignoreInstr) {
/*
* Create a new BB if one doesn't already exist.
*/
VfyBasicBlock* curBlock = vdata->basicBlocks[blockStartAddr];
if (curBlock == NULL) {
curBlock = allocVfyBasicBlock(vdata, blockStartAddr);
if (curBlock == NULL)
return false;
vdata->basicBlocks[blockStartAddr] = curBlock;
}
curBlock->firstAddr = blockStartAddr;
curBlock->lastAddr = idx;
if (!setPredecessors(vdata, curBlock, idx, opFlags, nextIdx,
handlerList, numHandlers))
{
goto bail;
}
}
blockStartAddr = nextIdx;
debugBBIndex++;
}
idx = nextIdx;
}
assert(idx == insnsSize);
result = true;
if (verbose)
dumpBasicBlocks(vdata);
bail:
free(handlerListAlloc);
return result;
}
/*
* Free the storage used by basic blocks.
*/
void dvmFreeVfyBasicBlocks(VerifierData* vdata)
{
unsigned int idx;
if (vdata->basicBlocks == NULL)
return;
for (idx = 0; idx < vdata->insnsSize; idx++) {
VfyBasicBlock* block = vdata->basicBlocks[idx];
if (block == NULL)
continue;
dvmPointerSetFree(block->predecessors);
dvmFreeBitVector(block->liveRegs);
free(block);
}
free(vdata->basicBlocks);
}