1/*
2 * Copyright (C) 2010 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 * Verifier basic block functions.
19 */
20#include "Dalvik.h"
21#include "analysis/VfyBasicBlock.h"
22#include "analysis/CodeVerify.h"
23#include "analysis/VerifySubs.h"
24#include "libdex/DexCatch.h"
25#include "libdex/InstrUtils.h"
26
27
28/*
29 * Extract the list of catch handlers from "pTry" into "addrBuf".
30 *
31 * Returns the size of the catch handler list.  If the return value
32 * exceeds "addrBufSize", the items at the end of the list will not be
33 * represented in the output array, and this function should be called
34 * again with a larger buffer.
35 */
36static u4 extractCatchHandlers(const DexCode* pCode, const DexTry* pTry,
37    u4* addrBuf, size_t addrBufSize)
38{
39    DexCatchIterator iterator;
40    unsigned int idx = 0;
41
42    dexCatchIteratorInit(&iterator, pCode, pTry->handlerOff);
43    while (true) {
44        DexCatchHandler* handler = dexCatchIteratorNext(&iterator);
45        if (handler == NULL)
46            break;
47
48        if (idx < addrBufSize) {
49            addrBuf[idx] = handler->address;
50        }
51        idx++;
52    }
53
54    return idx;
55}
56
57/*
58 * Returns "true" if the instruction represents a data chunk, such as a
59 * switch statement block.
60 */
61static bool isDataChunk(u2 insn)
62{
63    return (insn == kPackedSwitchSignature ||
64            insn == kSparseSwitchSignature ||
65            insn == kArrayDataSignature);
66}
67
68/*
69 * Alloc a basic block in the specified slot.  The storage will be
70 * initialized.
71 */
72static VfyBasicBlock* allocVfyBasicBlock(VerifierData* vdata, u4 idx)
73{
74    VfyBasicBlock* newBlock = (VfyBasicBlock*) calloc(1, sizeof(VfyBasicBlock));
75    if (newBlock == NULL)
76        return NULL;
77
78    /*
79     * TODO: there is no good default size here -- the problem is that most
80     * addresses will only have one predecessor, but a fair number will
81     * have 10+, and a few will have 100+ (e.g. the synthetic "finally"
82     * in a large synchronized method).  We probably want to use a small
83     * base allocation (perhaps two) and then have the first overflow
84     * allocation jump dramatically (to 32 or thereabouts).
85     */
86    newBlock->predecessors = dvmPointerSetAlloc(32);
87    if (newBlock->predecessors == NULL) {
88        free(newBlock);
89        return NULL;
90    }
91
92    newBlock->firstAddr = (u4) -1;      // DEBUG
93
94    newBlock->liveRegs = dvmAllocBitVector(vdata->insnRegCount, false);
95    if (newBlock->liveRegs == NULL) {
96        dvmPointerSetFree(newBlock->predecessors);
97        free(newBlock);
98        return NULL;
99    }
100
101    return newBlock;
102}
103
104/*
105 * Add "curBlock" to the predecessor list in "targetIdx".
106 */
107static bool addToPredecessor(VerifierData* vdata, VfyBasicBlock* curBlock,
108    u4 targetIdx)
109{
110    assert(targetIdx < vdata->insnsSize);
111
112    /*
113     * Allocate the target basic block if necessary.  This will happen
114     * on e.g. forward branches.
115     *
116     * We can't fill in all the fields, but that will happen automatically
117     * when we get to that part of the code.
118     */
119    VfyBasicBlock* targetBlock = vdata->basicBlocks[targetIdx];
120    if (targetBlock == NULL) {
121        targetBlock = allocVfyBasicBlock(vdata, targetIdx);
122        if (targetBlock == NULL)
123            return false;
124        vdata->basicBlocks[targetIdx] = targetBlock;
125    }
126
127    PointerSet* preds = targetBlock->predecessors;
128    bool added = dvmPointerSetAddEntry(preds, curBlock);
129    if (!added) {
130        /*
131         * This happens sometimes for packed-switch instructions, where
132         * the same target address appears more than once.  Also, a
133         * (pointless) conditional branch to the next instruction will
134         * trip over this.
135         */
136        ALOGV("ODD: point set for targ=0x%04x (%p) already had block "
137             "fir=0x%04x (%p)",
138            targetIdx, targetBlock, curBlock->firstAddr, curBlock);
139    }
140
141    return true;
142}
143
144/*
145 * Add ourselves to the predecessor list in all blocks we might transfer
146 * control to.
147 *
148 * There are four ways to proceed to a new instruction:
149 *  (1) continue to the following instruction
150 *  (2) [un]conditionally branch to a specific location
151 *  (3) conditionally branch through a "switch" statement
152 *  (4) throw an exception
153 *
154 * Returning from the method (via a return statement or an uncaught
155 * exception) are not interesting for liveness analysis.
156 */
157static bool setPredecessors(VerifierData* vdata, VfyBasicBlock* curBlock,
158    u4 curIdx, OpcodeFlags opFlags, u4 nextIdx, u4* handlerList,
159    size_t numHandlers)
160{
161    const InsnFlags* insnFlags = vdata->insnFlags;
162    const Method* meth = vdata->method;
163
164    unsigned int handlerIdx;
165    for (handlerIdx = 0; handlerIdx < numHandlers; handlerIdx++) {
166        if (!addToPredecessor(vdata, curBlock, handlerList[handlerIdx]))
167            return false;
168    }
169
170    if ((opFlags & kInstrCanContinue) != 0) {
171        if (!addToPredecessor(vdata, curBlock, nextIdx))
172            return false;
173    }
174    if ((opFlags & kInstrCanBranch) != 0) {
175        bool unused, gotBranch;
176        s4 branchOffset, absOffset;
177
178        gotBranch = dvmGetBranchOffset(meth, insnFlags, curIdx,
179                &branchOffset, &unused);
180        assert(gotBranch);
181        absOffset = curIdx + branchOffset;
182        assert(absOffset >= 0 && (u4) absOffset < vdata->insnsSize);
183
184        if (!addToPredecessor(vdata, curBlock, absOffset))
185            return false;
186    }
187
188    if ((opFlags & kInstrCanSwitch) != 0) {
189        const u2* curInsn = &meth->insns[curIdx];
190        const u2* dataPtr;
191
192        /* these values have already been verified, so we can trust them */
193        s4 offsetToData = curInsn[1] | ((s4) curInsn[2]) << 16;
194        dataPtr = curInsn + offsetToData;
195
196        /*
197         * dataPtr points to the start of the switch data.  The first
198         * item is the NOP+magic, the second is the number of entries in
199         * the switch table.
200         */
201        u2 switchCount = dataPtr[1];
202
203        /*
204         * Skip past the ident field, size field, and the first_key field
205         * (for packed) or the key list (for sparse).
206         */
207        if (dexOpcodeFromCodeUnit(meth->insns[curIdx]) == OP_PACKED_SWITCH) {
208            dataPtr += 4;
209        } else {
210            assert(dexOpcodeFromCodeUnit(meth->insns[curIdx]) ==
211                    OP_SPARSE_SWITCH);
212            dataPtr += 2 + 2 * switchCount;
213        }
214
215        u4 switchIdx;
216        for (switchIdx = 0; switchIdx < switchCount; switchIdx++) {
217            s4 offset, absOffset;
218
219            offset = (s4) dataPtr[switchIdx*2] |
220                     (s4) (dataPtr[switchIdx*2 +1] << 16);
221            absOffset = curIdx + offset;
222            assert(absOffset >= 0 && (u4) absOffset < vdata->insnsSize);
223
224            if (!addToPredecessor(vdata, curBlock, absOffset))
225                return false;
226        }
227    }
228
229    if (false) {
230        if (dvmPointerSetGetCount(curBlock->predecessors) > 256) {
231            ALOGI("Lots of preds at 0x%04x in %s.%s:%s", curIdx,
232                meth->clazz->descriptor, meth->name, meth->shorty);
233        }
234    }
235
236    return true;
237}
238
239/*
240 * Dump the contents of the basic blocks.
241 */
242static void dumpBasicBlocks(const VerifierData* vdata)
243{
244    char printBuf[256];
245    unsigned int idx;
246    int count;
247
248    ALOGI("Basic blocks for %s.%s:%s", vdata->method->clazz->descriptor,
249        vdata->method->name, vdata->method->shorty);
250    for (idx = 0; idx < vdata->insnsSize; idx++) {
251        VfyBasicBlock* block = vdata->basicBlocks[idx];
252        if (block == NULL)
253            continue;
254
255        assert(block->firstAddr == idx);
256        count = snprintf(printBuf, sizeof(printBuf), " %04x-%04x ",
257            block->firstAddr, block->lastAddr);
258
259        PointerSet* preds = block->predecessors;
260        size_t numPreds = dvmPointerSetGetCount(preds);
261
262        if (numPreds > 0) {
263            count += snprintf(printBuf + count, sizeof(printBuf) - count,
264                    "preds:");
265
266            unsigned int predIdx;
267            for (predIdx = 0; predIdx < numPreds; predIdx++) {
268                if (count >= (int) sizeof(printBuf))
269                    break;
270                const VfyBasicBlock* pred =
271                    (const VfyBasicBlock*) dvmPointerSetGetEntry(preds, predIdx);
272                count += snprintf(printBuf + count, sizeof(printBuf) - count,
273                        "%04x(%p),", pred->firstAddr, pred);
274            }
275        } else {
276            count += snprintf(printBuf + count, sizeof(printBuf) - count,
277                    "(no preds)");
278        }
279
280        printBuf[sizeof(printBuf)-2] = '!';
281        printBuf[sizeof(printBuf)-1] = '\0';
282
283        ALOGI("%s", printBuf);
284    }
285
286    usleep(100 * 1000);      /* ugh...let logcat catch up */
287}
288
289
290/*
291 * Generate a list of basic blocks and related information.
292 *
293 * On success, returns "true" with vdata->basicBlocks initialized.
294 */
295bool dvmComputeVfyBasicBlocks(VerifierData* vdata)
296{
297    const InsnFlags* insnFlags = vdata->insnFlags;
298    const Method* meth = vdata->method;
299    const u4 insnsSize = vdata->insnsSize;
300    const DexCode* pCode = dvmGetMethodCode(meth);
301    const DexTry* pTries = NULL;
302    const size_t kHandlerStackAllocSize = 16;   /* max seen so far is 7 */
303    u4 handlerAddrs[kHandlerStackAllocSize];
304    u4* handlerListAlloc = NULL;
305    u4* handlerList = NULL;
306    size_t numHandlers = 0;
307    u4 idx, blockStartAddr;
308    bool result = false;
309
310    bool verbose = false; //dvmWantVerboseVerification(meth);
311    if (verbose) {
312        ALOGI("Basic blocks for %s.%s:%s",
313            meth->clazz->descriptor, meth->name, meth->shorty);
314    }
315
316    /*
317     * Allocate a data structure that allows us to map from an address to
318     * the corresponding basic block.  Initially all pointers are NULL.
319     * They are populated on demand as we proceed (either when we reach a
320     * new BB, or when we need to add an item to the predecessor list in
321     * a not-yet-reached BB).
322     *
323     * Only the first instruction in the block points to the BB structure;
324     * the rest remain NULL.
325     */
326    vdata->basicBlocks =
327        (VfyBasicBlock**) calloc(insnsSize, sizeof(VfyBasicBlock*));
328    if (vdata->basicBlocks == NULL)
329      return false;
330
331    /*
332     * The "tries" list is a series of non-overlapping regions with a list
333     * of "catch" handlers.  Rather than do the "find a matching try block"
334     * computation at each step, we just walk the "try" list in parallel.
335     *
336     * Not all methods have "try" blocks.  If this one does, we init tryEnd
337     * to zero, so that the (exclusive bound) range check trips immediately.
338     */
339    u4 tryIndex = 0, tryStart = 0, tryEnd = 0;
340    if (pCode->triesSize != 0) {
341        pTries = dexGetTries(pCode);
342    }
343
344    u4 debugBBIndex = 0;
345
346    /*
347     * The address associated with a basic block is the start address.
348     */
349    blockStartAddr = 0;
350
351    for (idx = 0; idx < insnsSize; ) {
352        /*
353         * Make sure we're pointing at the right "try" block.  It should
354         * not be possible to "jump over" a block, so if we're no longer
355         * in the correct one we can just advance to the next.
356         */
357        if (pTries != NULL && idx >= tryEnd) {
358            if (tryIndex == pCode->triesSize) {
359                /* no more try blocks in this method */
360                pTries = NULL;
361                numHandlers = 0;
362            } else {
363                /*
364                 * Extract the set of handlers.  We want to avoid doing
365                 * this for each block, so we copy them to local storage.
366                 * If it doesn't fit in the small stack area, we'll use
367                 * the heap instead.
368                 *
369                 * It's rare to encounter a method with more than half a
370                 * dozen possible handlers.
371                 */
372                tryStart = pTries[tryIndex].startAddr;
373                tryEnd = tryStart + pTries[tryIndex].insnCount;
374
375                if (handlerListAlloc != NULL) {
376                    free(handlerListAlloc);
377                    handlerListAlloc = NULL;
378                }
379                numHandlers = extractCatchHandlers(pCode, &pTries[tryIndex],
380                    handlerAddrs, kHandlerStackAllocSize);
381                assert(numHandlers > 0);    // TODO make sure this is verified
382                if (numHandlers <= kHandlerStackAllocSize) {
383                    handlerList = handlerAddrs;
384                } else {
385                    ALOGD("overflow, numHandlers=%d", numHandlers);
386                    handlerListAlloc = (u4*) malloc(sizeof(u4) * numHandlers);
387                    if (handlerListAlloc == NULL)
388                        return false;
389                    extractCatchHandlers(pCode, &pTries[tryIndex],
390                        handlerListAlloc, numHandlers);
391                    handlerList = handlerListAlloc;
392                }
393
394                ALOGV("+++ start=%x end=%x numHan=%d",
395                    tryStart, tryEnd, numHandlers);
396
397                tryIndex++;
398            }
399        }
400
401        /*
402         * Check the current instruction, and possibly aspects of the
403         * next instruction, to see if this instruction ends the current
404         * basic block.
405         *
406         * Instructions that can throw only end the block if there is the
407         * possibility of a local handler catching the exception.
408         */
409        Opcode opcode = dexOpcodeFromCodeUnit(meth->insns[idx]);
410        OpcodeFlags opFlags = dexGetFlagsFromOpcode(opcode);
411        size_t nextIdx = idx + dexGetWidthFromInstruction(&meth->insns[idx]);
412        bool endBB = false;
413        bool ignoreInstr = false;
414
415        if ((opFlags & kInstrCanContinue) == 0) {
416            /* does not continue */
417            endBB = true;
418        } else if ((opFlags & (kInstrCanBranch | kInstrCanSwitch)) != 0) {
419            /* conditionally branches elsewhere */
420            endBB = true;
421        } else if ((opFlags & kInstrCanThrow) != 0 &&
422                dvmInsnIsInTry(insnFlags, idx))
423        {
424            /* throws an exception that might be caught locally */
425            endBB = true;
426        } else if (isDataChunk(meth->insns[idx])) {
427            /*
428             * If this is a data chunk (e.g. switch data) we want to skip
429             * over it entirely.  Set endBB so we don't carry this along as
430             * the start of a block, and ignoreInstr so we don't try to
431             * open a basic block for this instruction.
432             */
433            endBB = ignoreInstr = true;
434        } else if (dvmInsnIsBranchTarget(insnFlags, nextIdx)) {
435            /*
436             * We also need to end it if the next instruction is a branch
437             * target.  Note we've tagged exception catch blocks as such.
438             *
439             * If we're this far along in the "else" chain, we know that
440             * this isn't a data-chunk NOP, and control can continue to
441             * the next instruction, so we're okay examining "nextIdx".
442             */
443            assert(nextIdx < insnsSize);
444            endBB = true;
445        } else if (opcode == OP_NOP && isDataChunk(meth->insns[nextIdx])) {
446            /*
447             * Handle an odd special case: if this is NOP padding before a
448             * data chunk, also treat it as "ignore".  Otherwise it'll look
449             * like a block that starts and doesn't end.
450             */
451            endBB = ignoreInstr = true;
452        } else {
453            /* check: return ops should be caught by absence of can-continue */
454            assert((opFlags & kInstrCanReturn) == 0);
455        }
456
457        if (verbose) {
458            char btc = dvmInsnIsBranchTarget(insnFlags, idx) ? '>' : ' ';
459            char tryc =
460                (pTries != NULL && idx >= tryStart && idx < tryEnd) ? 't' : ' ';
461            bool startBB = (idx == blockStartAddr);
462            const char* startEnd;
463
464
465            if (ignoreInstr)
466                startEnd = "IGNORE";
467            else if (startBB && endBB)
468                startEnd = "START/END";
469            else if (startBB)
470                startEnd = "START";
471            else if (endBB)
472                startEnd = "END";
473            else
474                startEnd = "-";
475
476            ALOGI("%04x: %c%c%s #%d", idx, tryc, btc, startEnd, debugBBIndex);
477
478            if (pTries != NULL && idx == tryStart) {
479                assert(numHandlers > 0);
480                ALOGI("  EXC block: [%04x, %04x) %d:(%04x...)",
481                    tryStart, tryEnd, numHandlers, handlerList[0]);
482            }
483        }
484
485        if (idx != blockStartAddr) {
486            /* should not be a basic block struct associated with this addr */
487            assert(vdata->basicBlocks[idx] == NULL);
488        }
489        if (endBB) {
490            if (!ignoreInstr) {
491                /*
492                 * Create a new BB if one doesn't already exist.
493                 */
494                VfyBasicBlock* curBlock = vdata->basicBlocks[blockStartAddr];
495                if (curBlock == NULL) {
496                    curBlock = allocVfyBasicBlock(vdata, blockStartAddr);
497                    if (curBlock == NULL)
498                        return false;
499                    vdata->basicBlocks[blockStartAddr] = curBlock;
500                }
501
502                curBlock->firstAddr = blockStartAddr;
503                curBlock->lastAddr = idx;
504
505                if (!setPredecessors(vdata, curBlock, idx, opFlags, nextIdx,
506                        handlerList, numHandlers))
507                {
508                    goto bail;
509                }
510            }
511
512            blockStartAddr = nextIdx;
513            debugBBIndex++;
514        }
515
516        idx = nextIdx;
517    }
518
519    assert(idx == insnsSize);
520
521    result = true;
522
523    if (verbose)
524        dumpBasicBlocks(vdata);
525
526bail:
527    free(handlerListAlloc);
528    return result;
529}
530
531/*
532 * Free the storage used by basic blocks.
533 */
534void dvmFreeVfyBasicBlocks(VerifierData* vdata)
535{
536    unsigned int idx;
537
538    if (vdata->basicBlocks == NULL)
539        return;
540
541    for (idx = 0; idx < vdata->insnsSize; idx++) {
542        VfyBasicBlock* block = vdata->basicBlocks[idx];
543        if (block == NULL)
544            continue;
545
546        dvmPointerSetFree(block->predecessors);
547        free(block);
548    }
549}
550