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 17package com.android.dexgen.dex.file; 18 19import com.android.dexgen.dex.code.DalvCode; 20import com.android.dexgen.dex.code.DalvInsnList; 21import com.android.dexgen.dex.code.LocalList; 22import com.android.dexgen.dex.code.PositionList; 23import com.android.dexgen.rop.cst.CstMethodRef; 24import com.android.dexgen.rop.cst.CstUtf8; 25import com.android.dexgen.rop.type.Prototype; 26import com.android.dexgen.rop.type.StdTypeList; 27import com.android.dexgen.rop.type.Type; 28import com.android.dexgen.util.ExceptionWithContext; 29 30import java.io.ByteArrayInputStream; 31import java.io.IOException; 32import java.io.InputStream; 33import java.util.ArrayList; 34import java.util.List; 35 36import static com.android.dexgen.dex.file.DebugInfoConstants.*; 37 38/** 39 * A decoder for the dex debug info state machine format. 40 * This code exists mostly as a reference implementation and test for 41 * for the {@code DebugInfoEncoder} 42 */ 43public class DebugInfoDecoder { 44 /** encoded debug info */ 45 private final byte[] encoded; 46 47 /** positions decoded */ 48 private final ArrayList<PositionEntry> positions; 49 50 /** locals decoded */ 51 private final ArrayList<LocalEntry> locals; 52 53 /** size of code block in code units */ 54 private final int codesize; 55 56 /** indexed by register, the last local variable live in a reg */ 57 private final LocalEntry[] lastEntryForReg; 58 59 /** method descriptor of method this debug info is for */ 60 private final Prototype desc; 61 62 /** true if method is static */ 63 private final boolean isStatic; 64 65 /** dex file this debug info will be stored in */ 66 private final DexFile file; 67 68 /** 69 * register size, in register units, of the register space 70 * used by this method 71 */ 72 private final int regSize; 73 74 /** current decoding state: line number */ 75 private int line = 1; 76 77 /** current decoding state: bytecode address */ 78 private int address = 0; 79 80 /** string index of the string "this" */ 81 private final int thisStringIdx; 82 83 /** 84 * Constructs an instance. 85 * 86 * @param encoded encoded debug info 87 * @param codesize size of code block in code units 88 * @param regSize register size, in register units, of the register space 89 * used by this method 90 * @param isStatic true if method is static 91 * @param ref method descriptor of method this debug info is for 92 * @param file dex file this debug info will be stored in 93 */ 94 DebugInfoDecoder(byte[] encoded, int codesize, int regSize, 95 boolean isStatic, CstMethodRef ref, DexFile file) { 96 if (encoded == null) { 97 throw new NullPointerException("encoded == null"); 98 } 99 100 this.encoded = encoded; 101 this.isStatic = isStatic; 102 this.desc = ref.getPrototype(); 103 this.file = file; 104 this.regSize = regSize; 105 106 positions = new ArrayList<PositionEntry>(); 107 locals = new ArrayList<LocalEntry>(); 108 this.codesize = codesize; 109 lastEntryForReg = new LocalEntry[regSize]; 110 111 int idx = -1; 112 113 try { 114 idx = file.getStringIds().indexOf(new CstUtf8("this")); 115 } catch (IllegalArgumentException ex) { 116 /* 117 * Silently tolerate not finding "this". It just means that 118 * no method has local variable info that looks like 119 * a standard instance method. 120 */ 121 } 122 123 thisStringIdx = idx; 124 } 125 126 /** 127 * An entry in the resulting postions table 128 */ 129 static private class PositionEntry { 130 /** bytecode address */ 131 public int address; 132 133 /** line number */ 134 public int line; 135 136 public PositionEntry(int address, int line) { 137 this.address = address; 138 this.line = line; 139 } 140 } 141 142 /** 143 * An entry in the resulting locals table 144 */ 145 static private class LocalEntry { 146 /** address of event */ 147 public int address; 148 149 /** {@code true} iff it's a local start */ 150 public boolean isStart; 151 152 /** register number */ 153 public int reg; 154 155 /** index of name in strings table */ 156 public int nameIndex; 157 158 /** index of type in types table */ 159 public int typeIndex; 160 161 /** index of type signature in strings table */ 162 public int signatureIndex; 163 164 public LocalEntry(int address, boolean isStart, int reg, int nameIndex, 165 int typeIndex, int signatureIndex) { 166 this.address = address; 167 this.isStart = isStart; 168 this.reg = reg; 169 this.nameIndex = nameIndex; 170 this.typeIndex = typeIndex; 171 this.signatureIndex = signatureIndex; 172 } 173 174 public String toString() { 175 return String.format("[%x %s v%d %04x %04x %04x]", 176 address, isStart ? "start" : "end", reg, 177 nameIndex, typeIndex, signatureIndex); 178 } 179 } 180 181 /** 182 * Gets the decoded positions list. 183 * Valid after calling {@code decode}. 184 * 185 * @return positions list in ascending address order. 186 */ 187 public List<PositionEntry> getPositionList() { 188 return positions; 189 } 190 191 /** 192 * Gets the decoded locals list, in ascending start-address order. 193 * Valid after calling {@code decode}. 194 * 195 * @return locals list in ascending address order. 196 */ 197 public List<LocalEntry> getLocals() { 198 return locals; 199 } 200 201 /** 202 * Decodes the debug info sequence. 203 */ 204 public void decode() { 205 try { 206 decode0(); 207 } catch (Exception ex) { 208 throw ExceptionWithContext.withContext(ex, 209 "...while decoding debug info"); 210 } 211 } 212 213 /** 214 * Reads a string index. String indicies are offset by 1, and a 0 value 215 * in the stream (-1 as returned by this method) means "null" 216 * 217 * @param bs 218 * @return index into file's string ids table, -1 means null 219 * @throws IOException 220 */ 221 private int readStringIndex(InputStream bs) throws IOException { 222 int offsetIndex = readUnsignedLeb128(bs); 223 224 return offsetIndex - 1; 225 } 226 227 /** 228 * Gets the register that begins the method's parameter range (including 229 * the 'this' parameter for non-static methods). The range continues until 230 * {@code regSize} 231 * 232 * @return register as noted above. 233 */ 234 private int getParamBase() { 235 return regSize 236 - desc.getParameterTypes().getWordCount() - (isStatic? 0 : 1); 237 } 238 239 private void decode0() throws IOException { 240 ByteArrayInputStream bs = new ByteArrayInputStream(encoded); 241 242 line = readUnsignedLeb128(bs); 243 int szParams = readUnsignedLeb128(bs); 244 StdTypeList params = desc.getParameterTypes(); 245 int curReg = getParamBase(); 246 247 if (szParams != params.size()) { 248 throw new RuntimeException( 249 "Mismatch between parameters_size and prototype"); 250 } 251 252 if (!isStatic) { 253 // Start off with implicit 'this' entry 254 LocalEntry thisEntry = 255 new LocalEntry(0, true, curReg, thisStringIdx, 0, 0); 256 locals.add(thisEntry); 257 lastEntryForReg[curReg] = thisEntry; 258 curReg++; 259 } 260 261 for (int i = 0; i < szParams; i++) { 262 Type paramType = params.getType(i); 263 LocalEntry le; 264 265 int nameIdx = readStringIndex(bs); 266 267 if (nameIdx == -1) { 268 /* 269 * Unnamed parameter; often but not always filled in by an 270 * extended start op after the prologue 271 */ 272 le = new LocalEntry(0, true, curReg, -1, 0, 0); 273 } else { 274 // TODO: Final 0 should be idx of paramType.getDescriptor(). 275 le = new LocalEntry(0, true, curReg, nameIdx, 0, 0); 276 } 277 278 locals.add(le); 279 lastEntryForReg[curReg] = le; 280 curReg += paramType.getCategory(); 281 } 282 283 for (;;) { 284 int opcode = bs.read(); 285 286 if (opcode < 0) { 287 throw new RuntimeException 288 ("Reached end of debug stream without " 289 + "encountering end marker"); 290 } 291 292 switch (opcode) { 293 case DBG_START_LOCAL: { 294 int reg = readUnsignedLeb128(bs); 295 int nameIdx = readStringIndex(bs); 296 int typeIdx = readStringIndex(bs); 297 LocalEntry le = new LocalEntry( 298 address, true, reg, nameIdx, typeIdx, 0); 299 300 locals.add(le); 301 lastEntryForReg[reg] = le; 302 } 303 break; 304 305 case DBG_START_LOCAL_EXTENDED: { 306 int reg = readUnsignedLeb128(bs); 307 int nameIdx = readStringIndex(bs); 308 int typeIdx = readStringIndex(bs); 309 int sigIdx = readStringIndex(bs); 310 LocalEntry le = new LocalEntry( 311 address, true, reg, nameIdx, typeIdx, sigIdx); 312 313 locals.add(le); 314 lastEntryForReg[reg] = le; 315 } 316 break; 317 318 case DBG_RESTART_LOCAL: { 319 int reg = readUnsignedLeb128(bs); 320 LocalEntry prevle; 321 LocalEntry le; 322 323 try { 324 prevle = lastEntryForReg[reg]; 325 326 if (prevle.isStart) { 327 throw new RuntimeException("nonsensical " 328 + "RESTART_LOCAL on live register v" 329 + reg); 330 } 331 332 le = new LocalEntry(address, true, reg, 333 prevle.nameIndex, prevle.typeIndex, 0); 334 } catch (NullPointerException ex) { 335 throw new RuntimeException( 336 "Encountered RESTART_LOCAL on new v" + reg); 337 } 338 339 locals.add(le); 340 lastEntryForReg[reg] = le; 341 } 342 break; 343 344 case DBG_END_LOCAL: { 345 int reg = readUnsignedLeb128(bs); 346 LocalEntry prevle; 347 LocalEntry le; 348 349 try { 350 prevle = lastEntryForReg[reg]; 351 352 if (!prevle.isStart) { 353 throw new RuntimeException("nonsensical " 354 + "END_LOCAL on dead register v" + reg); 355 } 356 357 le = new LocalEntry(address, false, reg, 358 prevle.nameIndex, prevle.typeIndex, 359 prevle.signatureIndex); 360 } catch (NullPointerException ex) { 361 throw new RuntimeException( 362 "Encountered END_LOCAL on new v" + reg); 363 } 364 365 locals.add(le); 366 lastEntryForReg[reg] = le; 367 } 368 break; 369 370 case DBG_END_SEQUENCE: 371 // all done 372 return; 373 374 case DBG_ADVANCE_PC: 375 address += readUnsignedLeb128(bs); 376 break; 377 378 case DBG_ADVANCE_LINE: 379 line += readSignedLeb128(bs); 380 break; 381 382 case DBG_SET_PROLOGUE_END: 383 //TODO do something with this. 384 break; 385 386 case DBG_SET_EPILOGUE_BEGIN: 387 //TODO do something with this. 388 break; 389 390 case DBG_SET_FILE: 391 //TODO do something with this. 392 break; 393 394 default: 395 if (opcode < DBG_FIRST_SPECIAL) { 396 throw new RuntimeException( 397 "Invalid extended opcode encountered " 398 + opcode); 399 } 400 401 int adjopcode = opcode - DBG_FIRST_SPECIAL; 402 403 address += adjopcode / DBG_LINE_RANGE; 404 line += DBG_LINE_BASE + (adjopcode % DBG_LINE_RANGE); 405 406 positions.add(new PositionEntry(address, line)); 407 break; 408 409 } 410 } 411 } 412 413 /** 414 * Validates an encoded debug info stream against data used to encode it, 415 * throwing an exception if they do not match. Used to validate the 416 * encoder. 417 * 418 * @param info encoded debug info 419 * @param file {@code non-null;} file to refer to during decoding 420 * @param ref {@code non-null;} method whose info is being decoded 421 * @param code {@code non-null;} original code object that was encoded 422 * @param isStatic whether the method is static 423 */ 424 public static void validateEncode(byte[] info, DexFile file, 425 CstMethodRef ref, DalvCode code, boolean isStatic) { 426 PositionList pl = code.getPositions(); 427 LocalList ll = code.getLocals(); 428 DalvInsnList insns = code.getInsns(); 429 int codeSize = insns.codeSize(); 430 int countRegisters = insns.getRegistersSize(); 431 432 try { 433 validateEncode0(info, codeSize, countRegisters, 434 isStatic, ref, file, pl, ll); 435 } catch (RuntimeException ex) { 436 System.err.println("instructions:"); 437 insns.debugPrint(System.err, " ", true); 438 System.err.println("local list:"); 439 ll.debugPrint(System.err, " "); 440 throw ExceptionWithContext.withContext(ex, 441 "while processing " + ref.toHuman()); 442 } 443 } 444 445 private static void validateEncode0(byte[] info, int codeSize, 446 int countRegisters, boolean isStatic, CstMethodRef ref, 447 DexFile file, PositionList pl, LocalList ll) { 448 DebugInfoDecoder decoder 449 = new DebugInfoDecoder(info, codeSize, countRegisters, 450 isStatic, ref, file); 451 452 decoder.decode(); 453 454 /* 455 * Go through the decoded position entries, matching up 456 * with original entries. 457 */ 458 459 List<PositionEntry> decodedEntries = decoder.getPositionList(); 460 461 if (decodedEntries.size() != pl.size()) { 462 throw new RuntimeException( 463 "Decoded positions table not same size was " 464 + decodedEntries.size() + " expected " + pl.size()); 465 } 466 467 for (PositionEntry entry : decodedEntries) { 468 boolean found = false; 469 for (int i = pl.size() - 1; i >= 0; i--) { 470 PositionList.Entry ple = pl.get(i); 471 472 if (entry.line == ple.getPosition().getLine() 473 && entry.address == ple.getAddress()) { 474 found = true; 475 break; 476 } 477 } 478 479 if (!found) { 480 throw new RuntimeException ("Could not match position entry: " 481 + entry.address + ", " + entry.line); 482 } 483 } 484 485 /* 486 * Go through the original local list, in order, matching up 487 * with decoded entries. 488 */ 489 490 List<LocalEntry> decodedLocals = decoder.getLocals(); 491 int thisStringIdx = decoder.thisStringIdx; 492 int decodedSz = decodedLocals.size(); 493 int paramBase = decoder.getParamBase(); 494 495 /* 496 * Preflight to fill in any parameters that were skipped in 497 * the prologue (including an implied "this") but then 498 * identified by full signature. 499 */ 500 for (int i = 0; i < decodedSz; i++) { 501 LocalEntry entry = decodedLocals.get(i); 502 int idx = entry.nameIndex; 503 504 if ((idx < 0) || (idx == thisStringIdx)) { 505 for (int j = i + 1; j < decodedSz; j++) { 506 LocalEntry e2 = decodedLocals.get(j); 507 if (e2.address != 0) { 508 break; 509 } 510 if ((entry.reg == e2.reg) && e2.isStart) { 511 decodedLocals.set(i, e2); 512 decodedLocals.remove(j); 513 decodedSz--; 514 break; 515 } 516 } 517 } 518 } 519 520 int origSz = ll.size(); 521 int decodeAt = 0; 522 boolean problem = false; 523 524 for (int i = 0; i < origSz; i++) { 525 LocalList.Entry origEntry = ll.get(i); 526 527 if (origEntry.getDisposition() 528 == LocalList.Disposition.END_REPLACED) { 529 /* 530 * The encoded list doesn't represent replacements, so 531 * ignore them for the sake of comparison. 532 */ 533 continue; 534 } 535 536 LocalEntry decodedEntry; 537 538 do { 539 decodedEntry = decodedLocals.get(decodeAt); 540 if (decodedEntry.nameIndex >= 0) { 541 break; 542 } 543 /* 544 * A negative name index means this is an anonymous 545 * parameter, and we shouldn't expect to see it in the 546 * original list. So, skip it. 547 */ 548 decodeAt++; 549 } while (decodeAt < decodedSz); 550 551 int decodedAddress = decodedEntry.address; 552 553 if (decodedEntry.reg != origEntry.getRegister()) { 554 System.err.println("local register mismatch at orig " + i + 555 " / decoded " + decodeAt); 556 problem = true; 557 break; 558 } 559 560 if (decodedEntry.isStart != origEntry.isStart()) { 561 System.err.println("local start/end mismatch at orig " + i + 562 " / decoded " + decodeAt); 563 problem = true; 564 break; 565 } 566 567 /* 568 * The secondary check here accounts for the fact that a 569 * parameter might not be marked as starting at 0 in the 570 * original list. 571 */ 572 if ((decodedAddress != origEntry.getAddress()) 573 && !((decodedAddress == 0) 574 && (decodedEntry.reg >= paramBase))) { 575 System.err.println("local address mismatch at orig " + i + 576 " / decoded " + decodeAt); 577 problem = true; 578 break; 579 } 580 581 decodeAt++; 582 } 583 584 if (problem) { 585 System.err.println("decoded locals:"); 586 for (LocalEntry e : decodedLocals) { 587 System.err.println(" " + e); 588 } 589 throw new RuntimeException("local table problem"); 590 } 591 } 592 593 /** 594 * Reads a DWARFv3-style signed LEB128 integer to the specified stream. 595 * See DWARF v3 section 7.6. An invalid sequence produces an IOException. 596 * 597 * @param bs stream to input from 598 * @return read value 599 * @throws IOException on invalid sequence in addition to 600 * those caused by the InputStream 601 */ 602 public static int readSignedLeb128(InputStream bs) throws IOException { 603 int result = 0; 604 int cur; 605 int count = 0; 606 int signBits = -1; 607 608 do { 609 cur = bs.read(); 610 result |= (cur & 0x7f) << (count * 7); 611 signBits <<= 7; 612 count++; 613 } while (((cur & 0x80) == 0x80) && count < 5); 614 615 if ((cur & 0x80) == 0x80) { 616 throw new IOException ("invalid LEB128 sequence"); 617 } 618 619 // Sign extend if appropriate 620 if (((signBits >> 1) & result) != 0 ) { 621 result |= signBits; 622 } 623 624 return result; 625 } 626 627 /** 628 * Reads a DWARFv3-style unsigned LEB128 integer to the specified stream. 629 * See DWARF v3 section 7.6. An invalid sequence produces an IOException. 630 * 631 * @param bs stream to input from 632 * @return read value, which should be treated as an unsigned value. 633 * @throws IOException on invalid sequence in addition to 634 * those caused by the InputStream 635 */ 636 public static int readUnsignedLeb128(InputStream bs) throws IOException { 637 int result = 0; 638 int cur; 639 int count = 0; 640 641 do { 642 cur = bs.read(); 643 result |= (cur & 0x7f) << (count * 7); 644 count++; 645 } while (((cur & 0x80) == 0x80) && count < 5); 646 647 if ((cur & 0x80) == 0x80) { 648 throw new IOException ("invalid LEB128 sequence"); 649 } 650 651 return result; 652 } 653} 654