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;
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 return result;
277 }
278
279
280 /*
281 * Add a register to the LIVE set.
282 */
GEN(BitVector * workBits,u4 regIndex)283 static inline void GEN(BitVector* workBits, u4 regIndex)
284 {
285 dvmSetBit(workBits, regIndex);
286 }
287
288 /*
289 * Add a register pair to the LIVE set.
290 */
GENW(BitVector * workBits,u4 regIndex)291 static inline void GENW(BitVector* workBits, u4 regIndex)
292 {
293 dvmSetBit(workBits, regIndex);
294 dvmSetBit(workBits, regIndex+1);
295 }
296
297 /*
298 * Remove a register from the LIVE set.
299 */
KILL(BitVector * workBits,u4 regIndex)300 static inline void KILL(BitVector* workBits, u4 regIndex)
301 {
302 dvmClearBit(workBits, regIndex);
303 }
304
305 /*
306 * Remove a register pair from the LIVE set.
307 */
KILLW(BitVector * workBits,u4 regIndex)308 static inline void KILLW(BitVector* workBits, u4 regIndex)
309 {
310 dvmClearBit(workBits, regIndex);
311 dvmClearBit(workBits, regIndex+1);
312 }
313
314 /*
315 * Process a single instruction.
316 *
317 * Returns "false" if something goes fatally wrong.
318 */
processInstruction(VerifierData * vdata,u4 insnIdx,BitVector * workBits)319 static bool processInstruction(VerifierData* vdata, u4 insnIdx,
320 BitVector* workBits)
321 {
322 const Method* meth = vdata->method;
323 const u2* insns = meth->insns + insnIdx;
324 DecodedInstruction decInsn;
325
326 dexDecodeInstruction(insns, &decInsn);
327
328 /*
329 * Add registers to the "GEN" or "KILL" sets. We want to do KILL
330 * before GEN to handle cases where the source and destination
331 * register is the same.
332 */
333 switch (decInsn.opcode) {
334 case OP_NOP:
335 case OP_RETURN_VOID:
336 case OP_GOTO:
337 case OP_GOTO_16:
338 case OP_GOTO_32:
339 /* no registers are used */
340 break;
341
342 case OP_RETURN:
343 case OP_RETURN_OBJECT:
344 case OP_MONITOR_ENTER:
345 case OP_MONITOR_EXIT:
346 case OP_CHECK_CAST:
347 case OP_THROW:
348 case OP_PACKED_SWITCH:
349 case OP_SPARSE_SWITCH:
350 case OP_FILL_ARRAY_DATA:
351 case OP_IF_EQZ:
352 case OP_IF_NEZ:
353 case OP_IF_LTZ:
354 case OP_IF_GEZ:
355 case OP_IF_GTZ:
356 case OP_IF_LEZ:
357 case OP_SPUT:
358 case OP_SPUT_BOOLEAN:
359 case OP_SPUT_BYTE:
360 case OP_SPUT_CHAR:
361 case OP_SPUT_SHORT:
362 case OP_SPUT_OBJECT:
363 /* action <- vA */
364 GEN(workBits, decInsn.vA);
365 break;
366
367 case OP_RETURN_WIDE:
368 case OP_SPUT_WIDE:
369 /* action <- vA(wide) */
370 GENW(workBits, decInsn.vA);
371 break;
372
373 case OP_IF_EQ:
374 case OP_IF_NE:
375 case OP_IF_LT:
376 case OP_IF_GE:
377 case OP_IF_GT:
378 case OP_IF_LE:
379 case OP_IPUT:
380 case OP_IPUT_BOOLEAN:
381 case OP_IPUT_BYTE:
382 case OP_IPUT_CHAR:
383 case OP_IPUT_SHORT:
384 case OP_IPUT_OBJECT:
385 /* action <- vA, vB */
386 GEN(workBits, decInsn.vA);
387 GEN(workBits, decInsn.vB);
388 break;
389
390 case OP_IPUT_WIDE:
391 /* action <- vA(wide), vB */
392 GENW(workBits, decInsn.vA);
393 GEN(workBits, decInsn.vB);
394 break;
395
396 case OP_APUT:
397 case OP_APUT_BOOLEAN:
398 case OP_APUT_BYTE:
399 case OP_APUT_CHAR:
400 case OP_APUT_SHORT:
401 case OP_APUT_OBJECT:
402 /* action <- vA, vB, vC */
403 GEN(workBits, decInsn.vA);
404 GEN(workBits, decInsn.vB);
405 GEN(workBits, decInsn.vC);
406 break;
407
408 case OP_APUT_WIDE:
409 /* action <- vA(wide), vB, vC */
410 GENW(workBits, decInsn.vA);
411 GEN(workBits, decInsn.vB);
412 GEN(workBits, decInsn.vC);
413 break;
414
415 case OP_FILLED_NEW_ARRAY:
416 case OP_INVOKE_VIRTUAL:
417 case OP_INVOKE_SUPER:
418 case OP_INVOKE_DIRECT:
419 case OP_INVOKE_STATIC:
420 case OP_INVOKE_INTERFACE:
421 /* action <- vararg */
422 {
423 unsigned int idx;
424 for (idx = 0; idx < decInsn.vA; idx++) {
425 GEN(workBits, decInsn.arg[idx]);
426 }
427 }
428 break;
429
430 case OP_FILLED_NEW_ARRAY_RANGE:
431 case OP_INVOKE_VIRTUAL_RANGE:
432 case OP_INVOKE_SUPER_RANGE:
433 case OP_INVOKE_DIRECT_RANGE:
434 case OP_INVOKE_STATIC_RANGE:
435 case OP_INVOKE_INTERFACE_RANGE:
436 /* action <- vararg/range */
437 {
438 unsigned int idx;
439 for (idx = 0; idx < decInsn.vA; idx++) {
440 GEN(workBits, decInsn.vC + idx);
441 }
442 }
443 break;
444
445 case OP_MOVE_RESULT:
446 case OP_MOVE_RESULT_WIDE:
447 case OP_MOVE_RESULT_OBJECT:
448 case OP_MOVE_EXCEPTION:
449 case OP_CONST_4:
450 case OP_CONST_16:
451 case OP_CONST:
452 case OP_CONST_HIGH16:
453 case OP_CONST_STRING:
454 case OP_CONST_STRING_JUMBO:
455 case OP_CONST_CLASS:
456 case OP_NEW_INSTANCE:
457 case OP_SGET:
458 case OP_SGET_BOOLEAN:
459 case OP_SGET_BYTE:
460 case OP_SGET_CHAR:
461 case OP_SGET_SHORT:
462 case OP_SGET_OBJECT:
463 /* vA <- value */
464 KILL(workBits, decInsn.vA);
465 break;
466
467 case OP_CONST_WIDE_16:
468 case OP_CONST_WIDE_32:
469 case OP_CONST_WIDE:
470 case OP_CONST_WIDE_HIGH16:
471 case OP_SGET_WIDE:
472 /* vA(wide) <- value */
473 KILLW(workBits, decInsn.vA);
474 break;
475
476 case OP_MOVE:
477 case OP_MOVE_FROM16:
478 case OP_MOVE_16:
479 case OP_MOVE_OBJECT:
480 case OP_MOVE_OBJECT_FROM16:
481 case OP_MOVE_OBJECT_16:
482 case OP_INSTANCE_OF:
483 case OP_ARRAY_LENGTH:
484 case OP_NEW_ARRAY:
485 case OP_IGET:
486 case OP_IGET_BOOLEAN:
487 case OP_IGET_BYTE:
488 case OP_IGET_CHAR:
489 case OP_IGET_SHORT:
490 case OP_IGET_OBJECT:
491 case OP_NEG_INT:
492 case OP_NOT_INT:
493 case OP_NEG_FLOAT:
494 case OP_INT_TO_FLOAT:
495 case OP_FLOAT_TO_INT:
496 case OP_INT_TO_BYTE:
497 case OP_INT_TO_CHAR:
498 case OP_INT_TO_SHORT:
499 case OP_ADD_INT_LIT16:
500 case OP_RSUB_INT:
501 case OP_MUL_INT_LIT16:
502 case OP_DIV_INT_LIT16:
503 case OP_REM_INT_LIT16:
504 case OP_AND_INT_LIT16:
505 case OP_OR_INT_LIT16:
506 case OP_XOR_INT_LIT16:
507 case OP_ADD_INT_LIT8:
508 case OP_RSUB_INT_LIT8:
509 case OP_MUL_INT_LIT8:
510 case OP_DIV_INT_LIT8:
511 case OP_REM_INT_LIT8:
512 case OP_SHL_INT_LIT8:
513 case OP_SHR_INT_LIT8:
514 case OP_USHR_INT_LIT8:
515 case OP_AND_INT_LIT8:
516 case OP_OR_INT_LIT8:
517 case OP_XOR_INT_LIT8:
518 /* vA <- vB */
519 KILL(workBits, decInsn.vA);
520 GEN(workBits, decInsn.vB);
521 break;
522
523 case OP_IGET_WIDE:
524 case OP_INT_TO_LONG:
525 case OP_INT_TO_DOUBLE:
526 case OP_FLOAT_TO_LONG:
527 case OP_FLOAT_TO_DOUBLE:
528 /* vA(wide) <- vB */
529 KILLW(workBits, decInsn.vA);
530 GEN(workBits, decInsn.vB);
531 break;
532
533 case OP_LONG_TO_INT:
534 case OP_LONG_TO_FLOAT:
535 case OP_DOUBLE_TO_INT:
536 case OP_DOUBLE_TO_FLOAT:
537 /* vA <- vB(wide) */
538 KILL(workBits, decInsn.vA);
539 GENW(workBits, decInsn.vB);
540 break;
541
542 case OP_MOVE_WIDE:
543 case OP_MOVE_WIDE_FROM16:
544 case OP_MOVE_WIDE_16:
545 case OP_NEG_LONG:
546 case OP_NOT_LONG:
547 case OP_NEG_DOUBLE:
548 case OP_LONG_TO_DOUBLE:
549 case OP_DOUBLE_TO_LONG:
550 /* vA(wide) <- vB(wide) */
551 KILLW(workBits, decInsn.vA);
552 GENW(workBits, decInsn.vB);
553 break;
554
555 case OP_CMPL_FLOAT:
556 case OP_CMPG_FLOAT:
557 case OP_AGET:
558 case OP_AGET_BOOLEAN:
559 case OP_AGET_BYTE:
560 case OP_AGET_CHAR:
561 case OP_AGET_SHORT:
562 case OP_AGET_OBJECT:
563 case OP_ADD_INT:
564 case OP_SUB_INT:
565 case OP_MUL_INT:
566 case OP_REM_INT:
567 case OP_DIV_INT:
568 case OP_AND_INT:
569 case OP_OR_INT:
570 case OP_XOR_INT:
571 case OP_SHL_INT:
572 case OP_SHR_INT:
573 case OP_USHR_INT:
574 case OP_ADD_FLOAT:
575 case OP_SUB_FLOAT:
576 case OP_MUL_FLOAT:
577 case OP_DIV_FLOAT:
578 case OP_REM_FLOAT:
579 /* vA <- vB, vC */
580 KILL(workBits, decInsn.vA);
581 GEN(workBits, decInsn.vB);
582 GEN(workBits, decInsn.vC);
583 break;
584
585 case OP_AGET_WIDE:
586 /* vA(wide) <- vB, vC */
587 KILLW(workBits, decInsn.vA);
588 GEN(workBits, decInsn.vB);
589 GEN(workBits, decInsn.vC);
590 break;
591
592 case OP_CMPL_DOUBLE:
593 case OP_CMPG_DOUBLE:
594 case OP_CMP_LONG:
595 /* vA <- vB(wide), vC(wide) */
596 KILL(workBits, decInsn.vA);
597 GENW(workBits, decInsn.vB);
598 GENW(workBits, decInsn.vC);
599 break;
600
601 case OP_SHL_LONG:
602 case OP_SHR_LONG:
603 case OP_USHR_LONG:
604 /* vA(wide) <- vB(wide), vC */
605 KILLW(workBits, decInsn.vA);
606 GENW(workBits, decInsn.vB);
607 GEN(workBits, decInsn.vC);
608 break;
609
610 case OP_ADD_LONG:
611 case OP_SUB_LONG:
612 case OP_MUL_LONG:
613 case OP_DIV_LONG:
614 case OP_REM_LONG:
615 case OP_AND_LONG:
616 case OP_OR_LONG:
617 case OP_XOR_LONG:
618 case OP_ADD_DOUBLE:
619 case OP_SUB_DOUBLE:
620 case OP_MUL_DOUBLE:
621 case OP_DIV_DOUBLE:
622 case OP_REM_DOUBLE:
623 /* vA(wide) <- vB(wide), vC(wide) */
624 KILLW(workBits, decInsn.vA);
625 GENW(workBits, decInsn.vB);
626 GENW(workBits, decInsn.vC);
627 break;
628
629 case OP_ADD_INT_2ADDR:
630 case OP_SUB_INT_2ADDR:
631 case OP_MUL_INT_2ADDR:
632 case OP_REM_INT_2ADDR:
633 case OP_SHL_INT_2ADDR:
634 case OP_SHR_INT_2ADDR:
635 case OP_USHR_INT_2ADDR:
636 case OP_AND_INT_2ADDR:
637 case OP_OR_INT_2ADDR:
638 case OP_XOR_INT_2ADDR:
639 case OP_DIV_INT_2ADDR:
640 /* vA <- vA, vB */
641 /* KILL(workBits, decInsn.vA); */
642 GEN(workBits, decInsn.vA);
643 GEN(workBits, decInsn.vB);
644 break;
645
646 case OP_SHL_LONG_2ADDR:
647 case OP_SHR_LONG_2ADDR:
648 case OP_USHR_LONG_2ADDR:
649 /* vA(wide) <- vA(wide), vB */
650 /* KILLW(workBits, decInsn.vA); */
651 GENW(workBits, decInsn.vA);
652 GEN(workBits, decInsn.vB);
653 break;
654
655 case OP_ADD_LONG_2ADDR:
656 case OP_SUB_LONG_2ADDR:
657 case OP_MUL_LONG_2ADDR:
658 case OP_DIV_LONG_2ADDR:
659 case OP_REM_LONG_2ADDR:
660 case OP_AND_LONG_2ADDR:
661 case OP_OR_LONG_2ADDR:
662 case OP_XOR_LONG_2ADDR:
663 case OP_ADD_FLOAT_2ADDR:
664 case OP_SUB_FLOAT_2ADDR:
665 case OP_MUL_FLOAT_2ADDR:
666 case OP_DIV_FLOAT_2ADDR:
667 case OP_REM_FLOAT_2ADDR:
668 case OP_ADD_DOUBLE_2ADDR:
669 case OP_SUB_DOUBLE_2ADDR:
670 case OP_MUL_DOUBLE_2ADDR:
671 case OP_DIV_DOUBLE_2ADDR:
672 case OP_REM_DOUBLE_2ADDR:
673 /* vA(wide) <- vA(wide), vB(wide) */
674 /* KILLW(workBits, decInsn.vA); */
675 GENW(workBits, decInsn.vA);
676 GENW(workBits, decInsn.vB);
677 break;
678
679 /* we will only see this if liveness analysis is done after general vfy */
680 case OP_THROW_VERIFICATION_ERROR:
681 /* no registers used */
682 break;
683
684 /* quickened instructions, not expected to appear */
685 case OP_EXECUTE_INLINE:
686 case OP_EXECUTE_INLINE_RANGE:
687 case OP_IGET_QUICK:
688 case OP_IGET_WIDE_QUICK:
689 case OP_IGET_OBJECT_QUICK:
690 case OP_IPUT_QUICK:
691 case OP_IPUT_WIDE_QUICK:
692 case OP_IPUT_OBJECT_QUICK:
693 case OP_INVOKE_VIRTUAL_QUICK:
694 case OP_INVOKE_VIRTUAL_QUICK_RANGE:
695 case OP_INVOKE_SUPER_QUICK:
696 case OP_INVOKE_SUPER_QUICK_RANGE:
697 /* fall through to failure */
698
699 /* correctness fixes, not expected to appear */
700 case OP_INVOKE_OBJECT_INIT_RANGE:
701 case OP_RETURN_VOID_BARRIER:
702 case OP_SPUT_VOLATILE:
703 case OP_SPUT_OBJECT_VOLATILE:
704 case OP_SPUT_WIDE_VOLATILE:
705 case OP_IPUT_VOLATILE:
706 case OP_IPUT_OBJECT_VOLATILE:
707 case OP_IPUT_WIDE_VOLATILE:
708 case OP_SGET_VOLATILE:
709 case OP_SGET_OBJECT_VOLATILE:
710 case OP_SGET_WIDE_VOLATILE:
711 case OP_IGET_VOLATILE:
712 case OP_IGET_OBJECT_VOLATILE:
713 case OP_IGET_WIDE_VOLATILE:
714 /* fall through to failure */
715
716 /* these should never appear during verification */
717 case OP_UNUSED_3E:
718 case OP_UNUSED_3F:
719 case OP_UNUSED_40:
720 case OP_UNUSED_41:
721 case OP_UNUSED_42:
722 case OP_UNUSED_43:
723 case OP_UNUSED_73:
724 case OP_UNUSED_79:
725 case OP_UNUSED_7A:
726 case OP_BREAKPOINT:
727 case OP_UNUSED_FF:
728 return false;
729 }
730
731 return true;
732 }
733
734 /*
735 * This is a dexDecodeDebugInfo callback, used by markDebugLocals().
736 */
markLocalsCb(void * ctxt,u2 reg,u4 startAddress,u4 endAddress,const char * name,const char * descriptor,const char * signature)737 static void markLocalsCb(void* ctxt, u2 reg, u4 startAddress, u4 endAddress,
738 const char* name, const char* descriptor, const char* signature)
739 {
740 VerifierData* vdata = (VerifierData*) ctxt;
741 bool verbose = dvmWantVerboseVerification(vdata->method);
742
743 if (verbose) {
744 ALOGI("%04x-%04x %2d (%s %s)",
745 startAddress, endAddress, reg, name, descriptor);
746 }
747
748 bool wide = (descriptor[0] == 'D' || descriptor[0] == 'J');
749 assert(reg <= vdata->insnRegCount + (wide ? 1 : 0));
750
751 /*
752 * Set the bit in all GC point instructions in the range
753 * [startAddress, endAddress).
754 */
755 unsigned int idx;
756 for (idx = startAddress; idx < endAddress; idx++) {
757 BitVector* liveRegs = vdata->registerLines[idx].liveRegs;
758 if (liveRegs != NULL) {
759 if (wide) {
760 GENW(liveRegs, reg);
761 } else {
762 GEN(liveRegs, reg);
763 }
764 }
765 }
766 }
767
768 /*
769 * Mark all debugger-visible locals as live.
770 *
771 * The "locals" table describes the positions of the various locals in the
772 * stack frame based on the current execution address. If the debugger
773 * wants to display one, it issues a request by "slot number". We need
774 * to ensure that references in stack slots that might be queried by the
775 * debugger aren't GCed.
776 *
777 * (If the GC had some way to mark the slot as invalid we wouldn't have
778 * to do this. We could also have the debugger interface check the
779 * register map and simply refuse to return a "dead" value, but that's
780 * potentially confusing since the referred-to object might actually be
781 * alive, and being able to see it without having to hunt around for a
782 * "live" stack frame is useful.)
783 */
markDebugLocals(VerifierData * vdata)784 static bool markDebugLocals(VerifierData* vdata)
785 {
786 const Method* meth = vdata->method;
787
788 dexDecodeDebugInfo(meth->clazz->pDvmDex->pDexFile, dvmGetMethodCode(meth),
789 meth->clazz->descriptor, meth->prototype.protoIdx, meth->accessFlags,
790 NULL, markLocalsCb, vdata);
791
792 return true;
793 }
794
795
796 /*
797 * Dump the liveness bits to the log.
798 *
799 * "curIdx" is for display only.
800 */
dumpLiveState(const VerifierData * vdata,u4 curIdx,const BitVector * workBits)801 static void dumpLiveState(const VerifierData* vdata, u4 curIdx,
802 const BitVector* workBits)
803 {
804 u4 insnRegCount = vdata->insnRegCount;
805 size_t regCharSize = insnRegCount + (insnRegCount-1)/4 + 2 +1;
806 char regChars[regCharSize +1];
807 unsigned int idx;
808
809 memset(regChars, ' ', regCharSize);
810 regChars[0] = '[';
811 if (insnRegCount == 0)
812 regChars[1] = ']';
813 else
814 regChars[1 + (insnRegCount-1) + (insnRegCount-1)/4 +1] = ']';
815 regChars[regCharSize] = '\0';
816
817 for (idx = 0; idx < insnRegCount; idx++) {
818 char ch = dvmIsBitSet(workBits, idx) ? '+' : '-';
819 regChars[1 + idx + (idx/4)] = ch;
820 }
821
822 ALOGI("0x%04x %s", curIdx, regChars);
823 }
824