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 * Liveness analysis for Dalvik bytecode.
19 */
20 #include "Dalvik.h"
21 #include "analysis/Liveness.h"
22 #include "analysis/CodeVerify.h"
23
24 static bool processInstruction(VerifierData* vdata, u4 curIdx,
25 BitVector* workBits);
26 static bool markDebugLocals(VerifierData* vdata);
27 static void dumpLiveState(const VerifierData* vdata, u4 curIdx,
28 const BitVector* workBits);
29
30
31 /*
32 * Create a table of instruction widths that indicate the width of the
33 * *previous* instruction. The values are copied from the width table
34 * in "vdata", not derived from the instruction stream.
35 *
36 * Caller must free the return value.
37 */
createBackwardWidthTable(VerifierData * vdata)38 static InstructionWidth* createBackwardWidthTable(VerifierData* vdata)
39 {
40 InstructionWidth* widths;
41
42 widths = (InstructionWidth*)
43 calloc(vdata->insnsSize, sizeof(InstructionWidth));
44 if (widths == NULL)
45 return NULL;
46
47 u4 insnWidth = 0;
48 for (u4 idx = 0; idx < vdata->insnsSize; ) {
49 widths[idx] = insnWidth;
50 insnWidth = dvmInsnGetWidth(vdata->insnFlags, idx);
51 idx += insnWidth;
52 }
53
54 return widths;
55 }
56
57 /*
58 * Compute the "liveness" of every register at all GC points.
59 */
dvmComputeLiveness(VerifierData * vdata)60 bool dvmComputeLiveness(VerifierData* vdata)
61 {
62 const InsnFlags* insnFlags = vdata->insnFlags;
63 InstructionWidth* backwardWidth;
64 VfyBasicBlock* startGuess = NULL;
65 BitVector* workBits = NULL;
66 bool result = false;
67
68 bool verbose = false; //= dvmWantVerboseVerification(vdata->method);
69 if (verbose) {
70 const Method* meth = vdata->method;
71 ALOGI("Computing liveness for %s.%s:%s",
72 meth->clazz->descriptor, meth->name, meth->shorty);
73 }
74
75 assert(vdata->registerLines != NULL);
76
77 backwardWidth = createBackwardWidthTable(vdata);
78 if (backwardWidth == NULL)
79 goto bail;
80
81 /*
82 * Allocate space for intra-block work set. Does not include space
83 * for method result "registers", which aren't visible to the GC.
84 * (They would be made live by move-result and then die on the
85 * instruction immediately before it.)
86 */
87 workBits = dvmAllocBitVector(vdata->insnRegCount, false);
88 if (workBits == NULL)
89 goto bail;
90
91 /*
92 * We continue until all blocks have been visited, and no block
93 * requires further attention ("visited" is set and "changed" is
94 * clear).
95 *
96 * TODO: consider creating a "dense" array of basic blocks to make
97 * the walking faster.
98 */
99 for (int iter = 0;;) {
100 VfyBasicBlock* workBlock = NULL;
101
102 if (iter++ > 100000) {
103 LOG_VFY_METH(vdata->method, "oh dear");
104 dvmAbort();
105 }
106
107 /*
108 * If a block is marked "changed", we stop and handle it. If it
109 * just hasn't been visited yet, we remember it but keep searching
110 * for one that has been changed.
111 *
112 * The thought here is that this is more likely to let us work
113 * from end to start, which reduces the amount of re-evaluation
114 * required (both by using "changed" as a work list, and by picking
115 * un-visited blocks from the tail end of the method).
116 */
117 if (startGuess != NULL) {
118 assert(startGuess->changed);
119 workBlock = startGuess;
120 } else {
121 for (u4 idx = 0; idx < vdata->insnsSize; idx++) {
122 VfyBasicBlock* block = vdata->basicBlocks[idx];
123 if (block == NULL)
124 continue;
125
126 if (block->changed) {
127 workBlock = block;
128 break;
129 } else if (!block->visited) {
130 workBlock = block;
131 }
132 }
133 }
134
135 if (workBlock == NULL) {
136 /* all done */
137 break;
138 }
139
140 assert(workBlock->changed || !workBlock->visited);
141 startGuess = NULL;
142
143 /*
144 * Load work bits. These represent the liveness of registers
145 * after the last instruction in the block has finished executing.
146 */
147 assert(workBlock->liveRegs != NULL);
148 dvmCopyBitVector(workBits, workBlock->liveRegs);
149 if (verbose) {
150 ALOGI("Loaded work bits from last=0x%04x", workBlock->lastAddr);
151 dumpLiveState(vdata, 0xfffd, workBlock->liveRegs);
152 dumpLiveState(vdata, 0xffff, workBits);
153 }
154
155 /*
156 * Process a single basic block.
157 *
158 * If this instruction is a GC point, we want to save the result
159 * in the RegisterLine.
160 *
161 * We don't break basic blocks on every GC point -- in particular,
162 * instructions that might throw but have no "try" block don't
163 * end a basic block -- so there could be more than one GC point
164 * in a given basic block.
165 *
166 * We could change this, but it turns out to be not all that useful.
167 * At first glance it appears that we could share the liveness bit
168 * vector between the basic block struct and the register line,
169 * but the basic block needs to reflect the state *after* the
170 * instruction has finished, while the GC points need to describe
171 * the state before the instruction starts.
172 */
173 u4 curIdx = workBlock->lastAddr;
174 while (true) {
175 if (!processInstruction(vdata, curIdx, workBits))
176 goto bail;
177
178 if (verbose) {
179 dumpLiveState(vdata, curIdx + 0x8000, workBits);
180 }
181
182 if (dvmInsnIsGcPoint(insnFlags, curIdx)) {
183 BitVector* lineBits = vdata->registerLines[curIdx].liveRegs;
184 if (lineBits == NULL) {
185 lineBits = vdata->registerLines[curIdx].liveRegs =
186 dvmAllocBitVector(vdata->insnRegCount, false);
187 }
188 dvmCopyBitVector(lineBits, workBits);
189 }
190
191 if (curIdx == workBlock->firstAddr)
192 break;
193 assert(curIdx >= backwardWidth[curIdx]);
194 curIdx -= backwardWidth[curIdx];
195 }
196
197 workBlock->visited = true;
198 workBlock->changed = false;
199
200 if (verbose) {
201 dumpLiveState(vdata, curIdx, workBits);
202 }
203
204 /*
205 * Merge changes to all predecessors. If the new bits don't match
206 * the old bits, set the "changed" flag.
207 */
208 PointerSet* preds = workBlock->predecessors;
209 size_t numPreds = dvmPointerSetGetCount(preds);
210 unsigned int predIdx;
211
212 for (predIdx = 0; predIdx < numPreds; predIdx++) {
213 VfyBasicBlock* pred =
214 (VfyBasicBlock*) dvmPointerSetGetEntry(preds, predIdx);
215
216 pred->changed = dvmCheckMergeBitVectors(pred->liveRegs, workBits);
217 if (verbose) {
218 ALOGI("merging cur=%04x into pred last=%04x (ch=%d)",
219 curIdx, pred->lastAddr, pred->changed);
220 dumpLiveState(vdata, 0xfffa, pred->liveRegs);
221 dumpLiveState(vdata, 0xfffb, workBits);
222 }
223
224 /*
225 * We want to set the "changed" flag on unvisited predecessors
226 * as a way of guiding the verifier through basic blocks in
227 * a reasonable order. We can't count on variable liveness
228 * changing, so we force "changed" to true even if it hasn't.
229 */
230 if (!pred->visited)
231 pred->changed = true;
232
233 /*
234 * Keep track of one of the changed blocks so we can start
235 * there instead of having to scan through the list.
236 */
237 if (pred->changed)
238 startGuess = pred;
239 }
240 }
241
242 #ifndef NDEBUG
243 /*
244 * Sanity check: verify that all GC point register lines have a
245 * liveness bit vector allocated. Also, we're not expecting non-GC
246 * points to have them.
247 */
248 u4 checkIdx;
249 for (checkIdx = 0; checkIdx < vdata->insnsSize; ) {
250 if (dvmInsnIsGcPoint(insnFlags, checkIdx)) {
251 if (vdata->registerLines[checkIdx].liveRegs == NULL) {
252 LOG_VFY_METH(vdata->method,
253 "GLITCH: no liveRegs for GC point 0x%04x", checkIdx);
254 dvmAbort();
255 }
256 } else if (vdata->registerLines[checkIdx].liveRegs != NULL) {
257 LOG_VFY_METH(vdata->method,
258 "GLITCH: liveRegs for non-GC point 0x%04x", checkIdx);
259 dvmAbort();
260 }
261 u4 insnWidth = dvmInsnGetWidth(insnFlags, checkIdx);
262 checkIdx += insnWidth;
263 }
264 #endif
265
266 /*
267 * Factor in the debug info, if any.
268 */
269 if (!markDebugLocals(vdata))
270 goto bail;
271
272 result = true;
273
274 bail:
275 free(backwardWidth);
276 dvmFreeBitVector(workBits);
277 return result;
278 }
279
280
281 /*
282 * Add a register to the LIVE set.
283 */
GEN(BitVector * workBits,u4 regIndex)284 static inline void GEN(BitVector* workBits, u4 regIndex)
285 {
286 dvmSetBit(workBits, regIndex);
287 }
288
289 /*
290 * Add a register pair to the LIVE set.
291 */
GENW(BitVector * workBits,u4 regIndex)292 static inline void GENW(BitVector* workBits, u4 regIndex)
293 {
294 dvmSetBit(workBits, regIndex);
295 dvmSetBit(workBits, regIndex+1);
296 }
297
298 /*
299 * Remove a register from the LIVE set.
300 */
KILL(BitVector * workBits,u4 regIndex)301 static inline void KILL(BitVector* workBits, u4 regIndex)
302 {
303 dvmClearBit(workBits, regIndex);
304 }
305
306 /*
307 * Remove a register pair from the LIVE set.
308 */
KILLW(BitVector * workBits,u4 regIndex)309 static inline void KILLW(BitVector* workBits, u4 regIndex)
310 {
311 dvmClearBit(workBits, regIndex);
312 dvmClearBit(workBits, regIndex+1);
313 }
314
315 /*
316 * Process a single instruction.
317 *
318 * Returns "false" if something goes fatally wrong.
319 */
processInstruction(VerifierData * vdata,u4 insnIdx,BitVector * workBits)320 static bool processInstruction(VerifierData* vdata, u4 insnIdx,
321 BitVector* workBits)
322 {
323 const Method* meth = vdata->method;
324 const u2* insns = meth->insns + insnIdx;
325 DecodedInstruction decInsn;
326
327 dexDecodeInstruction(insns, &decInsn);
328
329 /*
330 * Add registers to the "GEN" or "KILL" sets. We want to do KILL
331 * before GEN to handle cases where the source and destination
332 * register is the same.
333 */
334 switch (decInsn.opcode) {
335 case OP_NOP:
336 case OP_RETURN_VOID:
337 case OP_GOTO:
338 case OP_GOTO_16:
339 case OP_GOTO_32:
340 /* no registers are used */
341 break;
342
343 case OP_RETURN:
344 case OP_RETURN_OBJECT:
345 case OP_MONITOR_ENTER:
346 case OP_MONITOR_EXIT:
347 case OP_CHECK_CAST:
348 case OP_THROW:
349 case OP_PACKED_SWITCH:
350 case OP_SPARSE_SWITCH:
351 case OP_FILL_ARRAY_DATA:
352 case OP_IF_EQZ:
353 case OP_IF_NEZ:
354 case OP_IF_LTZ:
355 case OP_IF_GEZ:
356 case OP_IF_GTZ:
357 case OP_IF_LEZ:
358 case OP_SPUT:
359 case OP_SPUT_BOOLEAN:
360 case OP_SPUT_BYTE:
361 case OP_SPUT_CHAR:
362 case OP_SPUT_SHORT:
363 case OP_SPUT_OBJECT:
364 /* action <- vA */
365 GEN(workBits, decInsn.vA);
366 break;
367
368 case OP_RETURN_WIDE:
369 case OP_SPUT_WIDE:
370 /* action <- vA(wide) */
371 GENW(workBits, decInsn.vA);
372 break;
373
374 case OP_IF_EQ:
375 case OP_IF_NE:
376 case OP_IF_LT:
377 case OP_IF_GE:
378 case OP_IF_GT:
379 case OP_IF_LE:
380 case OP_IPUT:
381 case OP_IPUT_BOOLEAN:
382 case OP_IPUT_BYTE:
383 case OP_IPUT_CHAR:
384 case OP_IPUT_SHORT:
385 case OP_IPUT_OBJECT:
386 /* action <- vA, vB */
387 GEN(workBits, decInsn.vA);
388 GEN(workBits, decInsn.vB);
389 break;
390
391 case OP_IPUT_WIDE:
392 /* action <- vA(wide), vB */
393 GENW(workBits, decInsn.vA);
394 GEN(workBits, decInsn.vB);
395 break;
396
397 case OP_APUT:
398 case OP_APUT_BOOLEAN:
399 case OP_APUT_BYTE:
400 case OP_APUT_CHAR:
401 case OP_APUT_SHORT:
402 case OP_APUT_OBJECT:
403 /* action <- vA, vB, vC */
404 GEN(workBits, decInsn.vA);
405 GEN(workBits, decInsn.vB);
406 GEN(workBits, decInsn.vC);
407 break;
408
409 case OP_APUT_WIDE:
410 /* action <- vA(wide), vB, vC */
411 GENW(workBits, decInsn.vA);
412 GEN(workBits, decInsn.vB);
413 GEN(workBits, decInsn.vC);
414 break;
415
416 case OP_FILLED_NEW_ARRAY:
417 case OP_INVOKE_VIRTUAL:
418 case OP_INVOKE_SUPER:
419 case OP_INVOKE_DIRECT:
420 case OP_INVOKE_STATIC:
421 case OP_INVOKE_INTERFACE:
422 /* action <- vararg */
423 {
424 unsigned int idx;
425 for (idx = 0; idx < decInsn.vA; idx++) {
426 GEN(workBits, decInsn.arg[idx]);
427 }
428 }
429 break;
430
431 case OP_FILLED_NEW_ARRAY_RANGE:
432 case OP_INVOKE_VIRTUAL_RANGE:
433 case OP_INVOKE_SUPER_RANGE:
434 case OP_INVOKE_DIRECT_RANGE:
435 case OP_INVOKE_STATIC_RANGE:
436 case OP_INVOKE_INTERFACE_RANGE:
437 /* action <- vararg/range */
438 {
439 unsigned int idx;
440 for (idx = 0; idx < decInsn.vA; idx++) {
441 GEN(workBits, decInsn.vC + idx);
442 }
443 }
444 break;
445
446 case OP_MOVE_RESULT:
447 case OP_MOVE_RESULT_WIDE:
448 case OP_MOVE_RESULT_OBJECT:
449 case OP_MOVE_EXCEPTION:
450 case OP_CONST_4:
451 case OP_CONST_16:
452 case OP_CONST:
453 case OP_CONST_HIGH16:
454 case OP_CONST_STRING:
455 case OP_CONST_STRING_JUMBO:
456 case OP_CONST_CLASS:
457 case OP_NEW_INSTANCE:
458 case OP_SGET:
459 case OP_SGET_BOOLEAN:
460 case OP_SGET_BYTE:
461 case OP_SGET_CHAR:
462 case OP_SGET_SHORT:
463 case OP_SGET_OBJECT:
464 /* vA <- value */
465 KILL(workBits, decInsn.vA);
466 break;
467
468 case OP_CONST_WIDE_16:
469 case OP_CONST_WIDE_32:
470 case OP_CONST_WIDE:
471 case OP_CONST_WIDE_HIGH16:
472 case OP_SGET_WIDE:
473 /* vA(wide) <- value */
474 KILLW(workBits, decInsn.vA);
475 break;
476
477 case OP_MOVE:
478 case OP_MOVE_FROM16:
479 case OP_MOVE_16:
480 case OP_MOVE_OBJECT:
481 case OP_MOVE_OBJECT_FROM16:
482 case OP_MOVE_OBJECT_16:
483 case OP_INSTANCE_OF:
484 case OP_ARRAY_LENGTH:
485 case OP_NEW_ARRAY:
486 case OP_IGET:
487 case OP_IGET_BOOLEAN:
488 case OP_IGET_BYTE:
489 case OP_IGET_CHAR:
490 case OP_IGET_SHORT:
491 case OP_IGET_OBJECT:
492 case OP_NEG_INT:
493 case OP_NOT_INT:
494 case OP_NEG_FLOAT:
495 case OP_INT_TO_FLOAT:
496 case OP_FLOAT_TO_INT:
497 case OP_INT_TO_BYTE:
498 case OP_INT_TO_CHAR:
499 case OP_INT_TO_SHORT:
500 case OP_ADD_INT_LIT16:
501 case OP_RSUB_INT:
502 case OP_MUL_INT_LIT16:
503 case OP_DIV_INT_LIT16:
504 case OP_REM_INT_LIT16:
505 case OP_AND_INT_LIT16:
506 case OP_OR_INT_LIT16:
507 case OP_XOR_INT_LIT16:
508 case OP_ADD_INT_LIT8:
509 case OP_RSUB_INT_LIT8:
510 case OP_MUL_INT_LIT8:
511 case OP_DIV_INT_LIT8:
512 case OP_REM_INT_LIT8:
513 case OP_SHL_INT_LIT8:
514 case OP_SHR_INT_LIT8:
515 case OP_USHR_INT_LIT8:
516 case OP_AND_INT_LIT8:
517 case OP_OR_INT_LIT8:
518 case OP_XOR_INT_LIT8:
519 /* vA <- vB */
520 KILL(workBits, decInsn.vA);
521 GEN(workBits, decInsn.vB);
522 break;
523
524 case OP_IGET_WIDE:
525 case OP_INT_TO_LONG:
526 case OP_INT_TO_DOUBLE:
527 case OP_FLOAT_TO_LONG:
528 case OP_FLOAT_TO_DOUBLE:
529 /* vA(wide) <- vB */
530 KILLW(workBits, decInsn.vA);
531 GEN(workBits, decInsn.vB);
532 break;
533
534 case OP_LONG_TO_INT:
535 case OP_LONG_TO_FLOAT:
536 case OP_DOUBLE_TO_INT:
537 case OP_DOUBLE_TO_FLOAT:
538 /* vA <- vB(wide) */
539 KILL(workBits, decInsn.vA);
540 GENW(workBits, decInsn.vB);
541 break;
542
543 case OP_MOVE_WIDE:
544 case OP_MOVE_WIDE_FROM16:
545 case OP_MOVE_WIDE_16:
546 case OP_NEG_LONG:
547 case OP_NOT_LONG:
548 case OP_NEG_DOUBLE:
549 case OP_LONG_TO_DOUBLE:
550 case OP_DOUBLE_TO_LONG:
551 /* vA(wide) <- vB(wide) */
552 KILLW(workBits, decInsn.vA);
553 GENW(workBits, decInsn.vB);
554 break;
555
556 case OP_CMPL_FLOAT:
557 case OP_CMPG_FLOAT:
558 case OP_AGET:
559 case OP_AGET_BOOLEAN:
560 case OP_AGET_BYTE:
561 case OP_AGET_CHAR:
562 case OP_AGET_SHORT:
563 case OP_AGET_OBJECT:
564 case OP_ADD_INT:
565 case OP_SUB_INT:
566 case OP_MUL_INT:
567 case OP_REM_INT:
568 case OP_DIV_INT:
569 case OP_AND_INT:
570 case OP_OR_INT:
571 case OP_XOR_INT:
572 case OP_SHL_INT:
573 case OP_SHR_INT:
574 case OP_USHR_INT:
575 case OP_ADD_FLOAT:
576 case OP_SUB_FLOAT:
577 case OP_MUL_FLOAT:
578 case OP_DIV_FLOAT:
579 case OP_REM_FLOAT:
580 /* vA <- vB, vC */
581 KILL(workBits, decInsn.vA);
582 GEN(workBits, decInsn.vB);
583 GEN(workBits, decInsn.vC);
584 break;
585
586 case OP_AGET_WIDE:
587 /* vA(wide) <- vB, vC */
588 KILLW(workBits, decInsn.vA);
589 GEN(workBits, decInsn.vB);
590 GEN(workBits, decInsn.vC);
591 break;
592
593 case OP_CMPL_DOUBLE:
594 case OP_CMPG_DOUBLE:
595 case OP_CMP_LONG:
596 /* vA <- vB(wide), vC(wide) */
597 KILL(workBits, decInsn.vA);
598 GENW(workBits, decInsn.vB);
599 GENW(workBits, decInsn.vC);
600 break;
601
602 case OP_SHL_LONG:
603 case OP_SHR_LONG:
604 case OP_USHR_LONG:
605 /* vA(wide) <- vB(wide), vC */
606 KILLW(workBits, decInsn.vA);
607 GENW(workBits, decInsn.vB);
608 GEN(workBits, decInsn.vC);
609 break;
610
611 case OP_ADD_LONG:
612 case OP_SUB_LONG:
613 case OP_MUL_LONG:
614 case OP_DIV_LONG:
615 case OP_REM_LONG:
616 case OP_AND_LONG:
617 case OP_OR_LONG:
618 case OP_XOR_LONG:
619 case OP_ADD_DOUBLE:
620 case OP_SUB_DOUBLE:
621 case OP_MUL_DOUBLE:
622 case OP_DIV_DOUBLE:
623 case OP_REM_DOUBLE:
624 /* vA(wide) <- vB(wide), vC(wide) */
625 KILLW(workBits, decInsn.vA);
626 GENW(workBits, decInsn.vB);
627 GENW(workBits, decInsn.vC);
628 break;
629
630 case OP_ADD_INT_2ADDR:
631 case OP_SUB_INT_2ADDR:
632 case OP_MUL_INT_2ADDR:
633 case OP_REM_INT_2ADDR:
634 case OP_SHL_INT_2ADDR:
635 case OP_SHR_INT_2ADDR:
636 case OP_USHR_INT_2ADDR:
637 case OP_AND_INT_2ADDR:
638 case OP_OR_INT_2ADDR:
639 case OP_XOR_INT_2ADDR:
640 case OP_DIV_INT_2ADDR:
641 /* vA <- vA, vB */
642 /* KILL(workBits, decInsn.vA); */
643 GEN(workBits, decInsn.vA);
644 GEN(workBits, decInsn.vB);
645 break;
646
647 case OP_SHL_LONG_2ADDR:
648 case OP_SHR_LONG_2ADDR:
649 case OP_USHR_LONG_2ADDR:
650 /* vA(wide) <- vA(wide), vB */
651 /* KILLW(workBits, decInsn.vA); */
652 GENW(workBits, decInsn.vA);
653 GEN(workBits, decInsn.vB);
654 break;
655
656 case OP_ADD_LONG_2ADDR:
657 case OP_SUB_LONG_2ADDR:
658 case OP_MUL_LONG_2ADDR:
659 case OP_DIV_LONG_2ADDR:
660 case OP_REM_LONG_2ADDR:
661 case OP_AND_LONG_2ADDR:
662 case OP_OR_LONG_2ADDR:
663 case OP_XOR_LONG_2ADDR:
664 case OP_ADD_FLOAT_2ADDR:
665 case OP_SUB_FLOAT_2ADDR:
666 case OP_MUL_FLOAT_2ADDR:
667 case OP_DIV_FLOAT_2ADDR:
668 case OP_REM_FLOAT_2ADDR:
669 case OP_ADD_DOUBLE_2ADDR:
670 case OP_SUB_DOUBLE_2ADDR:
671 case OP_MUL_DOUBLE_2ADDR:
672 case OP_DIV_DOUBLE_2ADDR:
673 case OP_REM_DOUBLE_2ADDR:
674 /* vA(wide) <- vA(wide), vB(wide) */
675 /* KILLW(workBits, decInsn.vA); */
676 GENW(workBits, decInsn.vA);
677 GENW(workBits, decInsn.vB);
678 break;
679
680 /* we will only see this if liveness analysis is done after general vfy */
681 case OP_THROW_VERIFICATION_ERROR:
682 /* no registers used */
683 break;
684
685 /* quickened instructions, not expected to appear */
686 case OP_EXECUTE_INLINE:
687 case OP_EXECUTE_INLINE_RANGE:
688 case OP_IGET_QUICK:
689 case OP_IGET_WIDE_QUICK:
690 case OP_IGET_OBJECT_QUICK:
691 case OP_IPUT_QUICK:
692 case OP_IPUT_WIDE_QUICK:
693 case OP_IPUT_OBJECT_QUICK:
694 case OP_INVOKE_VIRTUAL_QUICK:
695 case OP_INVOKE_VIRTUAL_QUICK_RANGE:
696 case OP_INVOKE_SUPER_QUICK:
697 case OP_INVOKE_SUPER_QUICK_RANGE:
698 /* fall through to failure */
699
700 /* correctness fixes, not expected to appear */
701 case OP_INVOKE_OBJECT_INIT_RANGE:
702 case OP_RETURN_VOID_BARRIER:
703 case OP_SPUT_VOLATILE:
704 case OP_SPUT_OBJECT_VOLATILE:
705 case OP_SPUT_WIDE_VOLATILE:
706 case OP_IPUT_VOLATILE:
707 case OP_IPUT_OBJECT_VOLATILE:
708 case OP_IPUT_WIDE_VOLATILE:
709 case OP_SGET_VOLATILE:
710 case OP_SGET_OBJECT_VOLATILE:
711 case OP_SGET_WIDE_VOLATILE:
712 case OP_IGET_VOLATILE:
713 case OP_IGET_OBJECT_VOLATILE:
714 case OP_IGET_WIDE_VOLATILE:
715 /* fall through to failure */
716
717 /* these should never appear during verification */
718 case OP_UNUSED_3E:
719 case OP_UNUSED_3F:
720 case OP_UNUSED_40:
721 case OP_UNUSED_41:
722 case OP_UNUSED_42:
723 case OP_UNUSED_43:
724 case OP_UNUSED_73:
725 case OP_UNUSED_79:
726 case OP_UNUSED_7A:
727 case OP_BREAKPOINT:
728 case OP_UNUSED_FF:
729 return false;
730 }
731
732 return true;
733 }
734
735 /*
736 * This is a dexDecodeDebugInfo callback, used by markDebugLocals().
737 */
markLocalsCb(void * ctxt,u2 reg,u4 startAddress,u4 endAddress,const char * name,const char * descriptor,const char * signature)738 static void markLocalsCb(void* ctxt, u2 reg, u4 startAddress, u4 endAddress,
739 const char* name, const char* descriptor, const char* signature)
740 {
741 VerifierData* vdata = (VerifierData*) ctxt;
742 bool verbose = dvmWantVerboseVerification(vdata->method);
743
744 if (verbose) {
745 ALOGI("%04x-%04x %2d (%s %s)",
746 startAddress, endAddress, reg, name, descriptor);
747 }
748
749 bool wide = (descriptor[0] == 'D' || descriptor[0] == 'J');
750 assert(reg <= vdata->insnRegCount + (wide ? 1 : 0));
751
752 /*
753 * Set the bit in all GC point instructions in the range
754 * [startAddress, endAddress).
755 */
756 unsigned int idx;
757 for (idx = startAddress; idx < endAddress; idx++) {
758 BitVector* liveRegs = vdata->registerLines[idx].liveRegs;
759 if (liveRegs != NULL) {
760 if (wide) {
761 GENW(liveRegs, reg);
762 } else {
763 GEN(liveRegs, reg);
764 }
765 }
766 }
767 }
768
769 /*
770 * Mark all debugger-visible locals as live.
771 *
772 * The "locals" table describes the positions of the various locals in the
773 * stack frame based on the current execution address. If the debugger
774 * wants to display one, it issues a request by "slot number". We need
775 * to ensure that references in stack slots that might be queried by the
776 * debugger aren't GCed.
777 *
778 * (If the GC had some way to mark the slot as invalid we wouldn't have
779 * to do this. We could also have the debugger interface check the
780 * register map and simply refuse to return a "dead" value, but that's
781 * potentially confusing since the referred-to object might actually be
782 * alive, and being able to see it without having to hunt around for a
783 * "live" stack frame is useful.)
784 */
markDebugLocals(VerifierData * vdata)785 static bool markDebugLocals(VerifierData* vdata)
786 {
787 const Method* meth = vdata->method;
788
789 dexDecodeDebugInfo(meth->clazz->pDvmDex->pDexFile, dvmGetMethodCode(meth),
790 meth->clazz->descriptor, meth->prototype.protoIdx, meth->accessFlags,
791 NULL, markLocalsCb, vdata);
792
793 return true;
794 }
795
796
797 /*
798 * Dump the liveness bits to the log.
799 *
800 * "curIdx" is for display only.
801 */
dumpLiveState(const VerifierData * vdata,u4 curIdx,const BitVector * workBits)802 static void dumpLiveState(const VerifierData* vdata, u4 curIdx,
803 const BitVector* workBits)
804 {
805 u4 insnRegCount = vdata->insnRegCount;
806 size_t regCharSize = insnRegCount + (insnRegCount-1)/4 + 2 +1;
807 char regChars[regCharSize +1];
808 unsigned int idx;
809
810 memset(regChars, ' ', regCharSize);
811 regChars[0] = '[';
812 if (insnRegCount == 0)
813 regChars[1] = ']';
814 else
815 regChars[1 + (insnRegCount-1) + (insnRegCount-1)/4 +1] = ']';
816 regChars[regCharSize] = '\0';
817
818 for (idx = 0; idx < insnRegCount; idx++) {
819 char ch = dvmIsBitSet(workBits, idx) ? '+' : '-';
820 regChars[1 + idx + (idx/4)] = ch;
821 }
822
823 ALOGI("0x%04x %s", curIdx, regChars);
824 }
825