1 /* 2 * Copyright (C) 2007 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 package com.android.dx.cf.code; 18 19 import com.android.dx.rop.cst.Constant; 20 import com.android.dx.rop.cst.CstFieldRef; 21 import com.android.dx.rop.cst.CstInteger; 22 import com.android.dx.rop.cst.CstInterfaceMethodRef; 23 import com.android.dx.rop.cst.CstMethodRef; 24 import com.android.dx.rop.cst.CstType; 25 import com.android.dx.rop.type.Prototype; 26 import com.android.dx.rop.type.Type; 27 import com.android.dx.rop.code.LocalItem; 28 import com.android.dx.util.Hex; 29 30 import java.util.ArrayList; 31 32 /** 33 * Class which knows how to simulate the effects of executing bytecode. 34 * 35 * <p><b>Note:</b> This class is not thread-safe. If multiple threads 36 * need to use a single instance, they must synchronize access explicitly 37 * between themselves.</p> 38 */ 39 public class Simulator { 40 /** 41 * {@code non-null;} canned error message for local variable 42 * table mismatches 43 */ 44 private static final String LOCAL_MISMATCH_ERROR = 45 "This is symptomatic of .class transformation tools that ignore " + 46 "local variable information."; 47 48 /** {@code non-null;} machine to use when simulating */ 49 private final Machine machine; 50 51 /** {@code non-null;} array of bytecode */ 52 private final BytecodeArray code; 53 54 /** {@code non-null;} local variable information */ 55 private final LocalVariableList localVariables; 56 57 /** {@code non-null;} visitor instance to use */ 58 private final SimVisitor visitor; 59 60 /** 61 * Constructs an instance. 62 * 63 * @param machine {@code non-null;} machine to use when simulating 64 * @param method {@code non-null;} method data to use 65 */ 66 public Simulator(Machine machine, ConcreteMethod method) { 67 if (machine == null) { 68 throw new NullPointerException("machine == null"); 69 } 70 71 if (method == null) { 72 throw new NullPointerException("method == null"); 73 } 74 75 this.machine = machine; 76 this.code = method.getCode(); 77 this.localVariables = method.getLocalVariables(); 78 this.visitor = new SimVisitor(); 79 } 80 81 /** 82 * Simulates the effect of executing the given basic block. This modifies 83 * the passed-in frame to represent the end result. 84 * 85 * @param bb {@code non-null;} the basic block 86 * @param frame {@code non-null;} frame to operate on 87 */ 88 public void simulate(ByteBlock bb, Frame frame) { 89 int end = bb.getEnd(); 90 91 visitor.setFrame(frame); 92 93 try { 94 for (int off = bb.getStart(); off < end; /*off*/) { 95 int length = code.parseInstruction(off, visitor); 96 visitor.setPreviousOffset(off); 97 off += length; 98 } 99 } catch (SimException ex) { 100 frame.annotate(ex); 101 throw ex; 102 } 103 } 104 105 /** 106 * Simulates the effect of the instruction at the given offset, by 107 * making appropriate calls on the given frame. 108 * 109 * @param offset {@code >= 0;} offset of the instruction to simulate 110 * @param frame {@code non-null;} frame to operate on 111 * @return the length of the instruction, in bytes 112 */ 113 public int simulate(int offset, Frame frame) { 114 visitor.setFrame(frame); 115 return code.parseInstruction(offset, visitor); 116 } 117 118 /** 119 * Constructs an "illegal top-of-stack" exception, for the stack 120 * manipulation opcodes. 121 */ 122 private static SimException illegalTos() { 123 return new SimException("stack mismatch: illegal " + 124 "top-of-stack for opcode"); 125 } 126 127 /** 128 * Returns the required array type for an array load or store 129 * instruction, based on a given implied type and an observed 130 * actual array type. 131 * 132 * <p>The interesting cases here have to do with object arrays, 133 * <code>byte[]</code>s, <code>boolean[]</code>s, and 134 * known-nulls.</p> 135 * 136 * <p>In the case of arrays of objects, we want to narrow the type 137 * to the actual array present on the stack, as long as what is 138 * present is an object type. Similarly, due to a quirk of the 139 * original bytecode representation, the instructions for dealing 140 * with <code>byte[]</code> and <code>boolean[]</code> are 141 * undifferentiated, and we aim here to return whichever one was 142 * actually present on the stack.</p> 143 * 144 * <p>In the case where there is a known-null on the stack where 145 * an array is expected, we just fall back to the implied type of 146 * the instruction. Due to the quirk described above, this means 147 * that source code that uses <code>boolean[]</code> might get 148 * translated surprisingly -- but correctly -- into an instruction 149 * that specifies a <code>byte[]</code>. It will be correct, 150 * because should the code actually execute, it will necessarily 151 * throw a <code>NullPointerException</code>, and it won't matter 152 * what opcode variant is used to achieve that result.</p> 153 * 154 * @param impliedType {@code non-null;} type implied by the 155 * instruction; is <i>not</i> an array type 156 * @param foundArrayType {@code non-null;} type found on the 157 * stack; is either an array type or a known-null 158 * @return {@code non-null;} the array type that should be 159 * required in this context 160 */ 161 private static Type requiredArrayTypeFor(Type impliedType, 162 Type foundArrayType) { 163 if (foundArrayType == Type.KNOWN_NULL) { 164 return impliedType.getArrayType(); 165 } 166 167 if ((impliedType == Type.OBJECT) 168 && foundArrayType.isArray() 169 && foundArrayType.getComponentType().isReference()) { 170 return foundArrayType; 171 } 172 173 if ((impliedType == Type.BYTE) 174 && (foundArrayType == Type.BOOLEAN_ARRAY)) { 175 /* 176 * Per above, an instruction with implied byte[] is also 177 * allowed to be used on boolean[]. 178 */ 179 return Type.BOOLEAN_ARRAY; 180 } 181 182 return impliedType.getArrayType(); 183 } 184 185 /** 186 * Bytecode visitor used during simulation. 187 */ 188 private class SimVisitor implements BytecodeArray.Visitor { 189 /** 190 * {@code non-null;} machine instance to use (just to avoid excessive 191 * cross-object field access) 192 */ 193 private final Machine machine; 194 195 /** 196 * {@code null-ok;} frame to use; set with each call to 197 * {@link Simulator#simulate} 198 */ 199 private Frame frame; 200 201 /** offset of the previous bytecode */ 202 private int previousOffset; 203 204 /** 205 * Constructs an instance. 206 */ 207 public SimVisitor() { 208 this.machine = Simulator.this.machine; 209 this.frame = null; 210 } 211 212 /** 213 * Sets the frame to act on. 214 * 215 * @param frame {@code non-null;} the frame 216 */ 217 public void setFrame(Frame frame) { 218 if (frame == null) { 219 throw new NullPointerException("frame == null"); 220 } 221 222 this.frame = frame; 223 } 224 225 /** {@inheritDoc} */ 226 public void visitInvalid(int opcode, int offset, int length) { 227 throw new SimException("invalid opcode " + Hex.u1(opcode)); 228 } 229 230 /** {@inheritDoc} */ 231 public void visitNoArgs(int opcode, int offset, int length, 232 Type type) { 233 switch (opcode) { 234 case ByteOps.NOP: { 235 machine.clearArgs(); 236 break; 237 } 238 case ByteOps.INEG: { 239 machine.popArgs(frame, type); 240 break; 241 } 242 case ByteOps.I2L: 243 case ByteOps.I2F: 244 case ByteOps.I2D: 245 case ByteOps.I2B: 246 case ByteOps.I2C: 247 case ByteOps.I2S: { 248 machine.popArgs(frame, Type.INT); 249 break; 250 } 251 case ByteOps.L2I: 252 case ByteOps.L2F: 253 case ByteOps.L2D: { 254 machine.popArgs(frame, Type.LONG); 255 break; 256 } 257 case ByteOps.F2I: 258 case ByteOps.F2L: 259 case ByteOps.F2D: { 260 machine.popArgs(frame, Type.FLOAT); 261 break; 262 } 263 case ByteOps.D2I: 264 case ByteOps.D2L: 265 case ByteOps.D2F: { 266 machine.popArgs(frame, Type.DOUBLE); 267 break; 268 } 269 case ByteOps.RETURN: { 270 machine.clearArgs(); 271 checkReturnType(Type.VOID); 272 break; 273 } 274 case ByteOps.IRETURN: { 275 Type checkType = type; 276 if (type == Type.OBJECT) { 277 /* 278 * For an object return, use the best-known 279 * type of the popped value. 280 */ 281 checkType = frame.getStack().peekType(0); 282 } 283 machine.popArgs(frame, type); 284 checkReturnType(checkType); 285 break; 286 } 287 case ByteOps.POP: { 288 Type peekType = frame.getStack().peekType(0); 289 if (peekType.isCategory2()) { 290 throw illegalTos(); 291 } 292 machine.popArgs(frame, 1); 293 break; 294 } 295 case ByteOps.ARRAYLENGTH: { 296 Type arrayType = frame.getStack().peekType(0); 297 if (!arrayType.isArrayOrKnownNull()) { 298 throw new SimException("type mismatch: expected " + 299 "array type but encountered " + 300 arrayType.toHuman()); 301 } 302 machine.popArgs(frame, Type.OBJECT); 303 break; 304 } 305 case ByteOps.ATHROW: 306 case ByteOps.MONITORENTER: 307 case ByteOps.MONITOREXIT: { 308 machine.popArgs(frame, Type.OBJECT); 309 break; 310 } 311 case ByteOps.IALOAD: { 312 /* 313 * See comment on requiredArrayTypeFor() for explanation 314 * about what's going on here. 315 */ 316 Type foundArrayType = frame.getStack().peekType(1); 317 Type requiredArrayType = 318 requiredArrayTypeFor(type, foundArrayType); 319 320 // Make type agree with the discovered requiredArrayType. 321 type = requiredArrayType.getComponentType(); 322 323 machine.popArgs(frame, requiredArrayType, Type.INT); 324 break; 325 } 326 case ByteOps.IADD: 327 case ByteOps.ISUB: 328 case ByteOps.IMUL: 329 case ByteOps.IDIV: 330 case ByteOps.IREM: 331 case ByteOps.IAND: 332 case ByteOps.IOR: 333 case ByteOps.IXOR: { 334 machine.popArgs(frame, type, type); 335 break; 336 } 337 case ByteOps.ISHL: 338 case ByteOps.ISHR: 339 case ByteOps.IUSHR: { 340 machine.popArgs(frame, type, Type.INT); 341 break; 342 } 343 case ByteOps.LCMP: { 344 machine.popArgs(frame, Type.LONG, Type.LONG); 345 break; 346 } 347 case ByteOps.FCMPL: 348 case ByteOps.FCMPG: { 349 machine.popArgs(frame, Type.FLOAT, Type.FLOAT); 350 break; 351 } 352 case ByteOps.DCMPL: 353 case ByteOps.DCMPG: { 354 machine.popArgs(frame, Type.DOUBLE, Type.DOUBLE); 355 break; 356 } 357 case ByteOps.IASTORE: { 358 /* 359 * See comment on requiredArrayTypeFor() for 360 * explanation about what's going on here. In 361 * addition to that, the category 1 vs. 2 thing 362 * below is to deal with the fact that, if the 363 * element type is category 2, we have to skip 364 * over one extra stack slot to find the array. 365 */ 366 ExecutionStack stack = frame.getStack(); 367 int peekDepth = type.isCategory1() ? 2 : 3; 368 Type foundArrayType = stack.peekType(peekDepth); 369 boolean foundArrayLocal = stack.peekLocal(peekDepth); 370 371 Type requiredArrayType = 372 requiredArrayTypeFor(type, foundArrayType); 373 374 /* 375 * Make type agree with the discovered requiredArrayType 376 * if it has local info. 377 */ 378 if (foundArrayLocal) { 379 type = requiredArrayType.getComponentType(); 380 } 381 382 machine.popArgs(frame, requiredArrayType, Type.INT, type); 383 break; 384 } 385 case ByteOps.POP2: 386 case ByteOps.DUP2: { 387 ExecutionStack stack = frame.getStack(); 388 int pattern; 389 390 if (stack.peekType(0).isCategory2()) { 391 // "form 2" in vmspec-2 392 machine.popArgs(frame, 1); 393 pattern = 0x11; 394 } else if (stack.peekType(1).isCategory1()) { 395 // "form 1" 396 machine.popArgs(frame, 2); 397 pattern = 0x2121; 398 } else { 399 throw illegalTos(); 400 } 401 402 if (opcode == ByteOps.DUP2) { 403 machine.auxIntArg(pattern); 404 } 405 break; 406 } 407 case ByteOps.DUP: { 408 Type peekType = frame.getStack().peekType(0); 409 410 if (peekType.isCategory2()) { 411 throw illegalTos(); 412 } 413 414 machine.popArgs(frame, 1); 415 machine.auxIntArg(0x11); 416 break; 417 } 418 case ByteOps.DUP_X1: { 419 ExecutionStack stack = frame.getStack(); 420 421 if (!(stack.peekType(0).isCategory1() && 422 stack.peekType(1).isCategory1())) { 423 throw illegalTos(); 424 } 425 426 machine.popArgs(frame, 2); 427 machine.auxIntArg(0x212); 428 break; 429 } 430 case ByteOps.DUP_X2: { 431 ExecutionStack stack = frame.getStack(); 432 433 if (stack.peekType(0).isCategory2()) { 434 throw illegalTos(); 435 } 436 437 if (stack.peekType(1).isCategory2()) { 438 // "form 2" in vmspec-2 439 machine.popArgs(frame, 2); 440 machine.auxIntArg(0x212); 441 } else if (stack.peekType(2).isCategory1()) { 442 // "form 1" 443 machine.popArgs(frame, 3); 444 machine.auxIntArg(0x3213); 445 } else { 446 throw illegalTos(); 447 } 448 break; 449 } 450 case ByteOps.DUP2_X1: { 451 ExecutionStack stack = frame.getStack(); 452 453 if (stack.peekType(0).isCategory2()) { 454 // "form 2" in vmspec-2 455 if (stack.peekType(2).isCategory2()) { 456 throw illegalTos(); 457 } 458 machine.popArgs(frame, 2); 459 machine.auxIntArg(0x212); 460 } else { 461 // "form 1" 462 if (stack.peekType(1).isCategory2() || 463 stack.peekType(2).isCategory2()) { 464 throw illegalTos(); 465 } 466 machine.popArgs(frame, 3); 467 machine.auxIntArg(0x32132); 468 } 469 break; 470 } 471 case ByteOps.DUP2_X2: { 472 ExecutionStack stack = frame.getStack(); 473 474 if (stack.peekType(0).isCategory2()) { 475 if (stack.peekType(2).isCategory2()) { 476 // "form 4" in vmspec-2 477 machine.popArgs(frame, 2); 478 machine.auxIntArg(0x212); 479 } else if (stack.peekType(3).isCategory1()) { 480 // "form 2" 481 machine.popArgs(frame, 3); 482 machine.auxIntArg(0x3213); 483 } else { 484 throw illegalTos(); 485 } 486 } else if (stack.peekType(1).isCategory1()) { 487 if (stack.peekType(2).isCategory2()) { 488 // "form 3" 489 machine.popArgs(frame, 3); 490 machine.auxIntArg(0x32132); 491 } else if (stack.peekType(3).isCategory1()) { 492 // "form 1" 493 machine.popArgs(frame, 4); 494 machine.auxIntArg(0x432143); 495 } else { 496 throw illegalTos(); 497 } 498 } else { 499 throw illegalTos(); 500 } 501 break; 502 } 503 case ByteOps.SWAP: { 504 ExecutionStack stack = frame.getStack(); 505 506 if (!(stack.peekType(0).isCategory1() && 507 stack.peekType(1).isCategory1())) { 508 throw illegalTos(); 509 } 510 511 machine.popArgs(frame, 2); 512 machine.auxIntArg(0x12); 513 break; 514 } 515 default: { 516 visitInvalid(opcode, offset, length); 517 return; 518 } 519 } 520 521 machine.auxType(type); 522 machine.run(frame, offset, opcode); 523 } 524 525 /** 526 * Checks whether the prototype is compatible with returning the 527 * given type, and throws if not. 528 * 529 * @param encountered {@code non-null;} the encountered return type 530 */ 531 private void checkReturnType(Type encountered) { 532 Type returnType = machine.getPrototype().getReturnType(); 533 534 /* 535 * Check to see if the prototype's return type is 536 * possibly assignable from the type we encountered. This 537 * takes care of all the salient cases (types are the same, 538 * they're compatible primitive types, etc.). 539 */ 540 if (!Merger.isPossiblyAssignableFrom(returnType, encountered)) { 541 throw new SimException("return type mismatch: prototype " + 542 "indicates " + returnType.toHuman() + 543 ", but encountered type " + encountered.toHuman()); 544 } 545 } 546 547 /** {@inheritDoc} */ 548 public void visitLocal(int opcode, int offset, int length, 549 int idx, Type type, int value) { 550 /* 551 * Note that the "type" parameter is always the simplest 552 * type based on the original opcode, e.g., "int" for 553 * "iload" (per se) and "Object" for "aload". So, when 554 * possible, we replace the type with the one indicated in 555 * the local variable table, though we still need to check 556 * to make sure it's valid for the opcode. 557 * 558 * The reason we use (offset + length) for the localOffset 559 * for a store is because it is only after the store that 560 * the local type becomes valid. On the other hand, the 561 * type associated with a load is valid at the start of 562 * the instruction. 563 */ 564 int localOffset = 565 (opcode == ByteOps.ISTORE) ? (offset + length) : offset; 566 LocalVariableList.Item local = 567 localVariables.pcAndIndexToLocal(localOffset, idx); 568 Type localType; 569 570 if (local != null) { 571 localType = local.getType(); 572 if (localType.getBasicFrameType() != 573 type.getBasicFrameType()) { 574 BaseMachine.throwLocalMismatch(type, localType); 575 return; 576 } 577 } else { 578 localType = type; 579 } 580 581 switch (opcode) { 582 case ByteOps.ILOAD: 583 case ByteOps.RET: { 584 machine.localArg(frame, idx); 585 machine.localInfo(local != null); 586 machine.auxType(type); 587 break; 588 } 589 case ByteOps.ISTORE: { 590 LocalItem item 591 = (local == null) ? null : local.getLocalItem(); 592 machine.popArgs(frame, type); 593 machine.auxType(type); 594 machine.localTarget(idx, localType, item); 595 break; 596 } 597 case ByteOps.IINC: { 598 LocalItem item 599 = (local == null) ? null : local.getLocalItem(); 600 machine.localArg(frame, idx); 601 machine.localTarget(idx, localType, item); 602 machine.auxType(type); 603 machine.auxIntArg(value); 604 machine.auxCstArg(CstInteger.make(value)); 605 break; 606 } 607 default: { 608 visitInvalid(opcode, offset, length); 609 return; 610 } 611 } 612 613 machine.run(frame, offset, opcode); 614 } 615 616 /** {@inheritDoc} */ 617 public void visitConstant(int opcode, int offset, int length, 618 Constant cst, int value) { 619 switch (opcode) { 620 case ByteOps.ANEWARRAY: { 621 machine.popArgs(frame, Type.INT); 622 break; 623 } 624 case ByteOps.PUTSTATIC: { 625 Type fieldType = ((CstFieldRef) cst).getType(); 626 machine.popArgs(frame, fieldType); 627 break; 628 } 629 case ByteOps.GETFIELD: 630 case ByteOps.CHECKCAST: 631 case ByteOps.INSTANCEOF: { 632 machine.popArgs(frame, Type.OBJECT); 633 break; 634 } 635 case ByteOps.PUTFIELD: { 636 Type fieldType = ((CstFieldRef) cst).getType(); 637 machine.popArgs(frame, Type.OBJECT, fieldType); 638 break; 639 } 640 case ByteOps.INVOKEINTERFACE: { 641 /* 642 * Convert the interface method ref into a normal 643 * method ref. 644 */ 645 cst = ((CstInterfaceMethodRef) cst).toMethodRef(); 646 // and fall through... 647 } 648 case ByteOps.INVOKEVIRTUAL: 649 case ByteOps.INVOKESPECIAL: { 650 /* 651 * Get the instance prototype, and use it to direct 652 * the machine. 653 */ 654 Prototype prototype = 655 ((CstMethodRef) cst).getPrototype(false); 656 machine.popArgs(frame, prototype); 657 break; 658 } 659 case ByteOps.INVOKESTATIC: { 660 /* 661 * Get the static prototype, and use it to direct 662 * the machine. 663 */ 664 Prototype prototype = 665 ((CstMethodRef) cst).getPrototype(true); 666 machine.popArgs(frame, prototype); 667 break; 668 } 669 case ByteOps.MULTIANEWARRAY: { 670 /* 671 * The "value" here is the count of dimensions to 672 * create. Make a prototype of that many "int" 673 * types, and tell the machine to pop them. This 674 * isn't the most efficient way in the world to do 675 * this, but then again, multianewarray is pretty 676 * darn rare and so not worth much effort 677 * optimizing for. 678 */ 679 Prototype prototype = 680 Prototype.internInts(Type.VOID, value); 681 machine.popArgs(frame, prototype); 682 break; 683 } 684 default: { 685 machine.clearArgs(); 686 break; 687 } 688 } 689 690 machine.auxIntArg(value); 691 machine.auxCstArg(cst); 692 machine.run(frame, offset, opcode); 693 } 694 695 /** {@inheritDoc} */ 696 public void visitBranch(int opcode, int offset, int length, 697 int target) { 698 switch (opcode) { 699 case ByteOps.IFEQ: 700 case ByteOps.IFNE: 701 case ByteOps.IFLT: 702 case ByteOps.IFGE: 703 case ByteOps.IFGT: 704 case ByteOps.IFLE: { 705 machine.popArgs(frame, Type.INT); 706 break; 707 } 708 case ByteOps.IFNULL: 709 case ByteOps.IFNONNULL: { 710 machine.popArgs(frame, Type.OBJECT); 711 break; 712 } 713 case ByteOps.IF_ICMPEQ: 714 case ByteOps.IF_ICMPNE: 715 case ByteOps.IF_ICMPLT: 716 case ByteOps.IF_ICMPGE: 717 case ByteOps.IF_ICMPGT: 718 case ByteOps.IF_ICMPLE: { 719 machine.popArgs(frame, Type.INT, Type.INT); 720 break; 721 } 722 case ByteOps.IF_ACMPEQ: 723 case ByteOps.IF_ACMPNE: { 724 machine.popArgs(frame, Type.OBJECT, Type.OBJECT); 725 break; 726 } 727 case ByteOps.GOTO: 728 case ByteOps.JSR: 729 case ByteOps.GOTO_W: 730 case ByteOps.JSR_W: { 731 machine.clearArgs(); 732 break; 733 } 734 default: { 735 visitInvalid(opcode, offset, length); 736 return; 737 } 738 } 739 740 machine.auxTargetArg(target); 741 machine.run(frame, offset, opcode); 742 } 743 744 /** {@inheritDoc} */ 745 public void visitSwitch(int opcode, int offset, int length, 746 SwitchList cases, int padding) { 747 machine.popArgs(frame, Type.INT); 748 machine.auxIntArg(padding); 749 machine.auxSwitchArg(cases); 750 machine.run(frame, offset, opcode); 751 } 752 753 /** {@inheritDoc} */ 754 public void visitNewarray(int offset, int length, CstType type, 755 ArrayList<Constant> initValues) { 756 machine.popArgs(frame, Type.INT); 757 machine.auxInitValues(initValues); 758 machine.auxCstArg(type); 759 machine.run(frame, offset, ByteOps.NEWARRAY); 760 } 761 762 /** {@inheritDoc} */ 763 public void setPreviousOffset(int offset) { 764 previousOffset = offset; 765 } 766 767 /** {@inheritDoc} */ 768 public int getPreviousOffset() { 769 return previousOffset; 770 } 771 } 772 } 773
