1 /* 2 * Copyright (C) 2009 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 * This code generate "register maps" for Dalvik bytecode. In a stack-based 19 * VM we might call these "stack maps". They are used to increase the 20 * precision in the garbage collector when scanning references in the 21 * interpreter thread stacks. 22 */ 23 #include "Dalvik.h" 24 #include "analysis/CodeVerify.h" 25 #include "analysis/RegisterMap.h" 26 #include "libdex/DexCatch.h" 27 #include "libdex/InstrUtils.h" 28 #include "libdex/Leb128.h" 29 30 #include <stddef.h> 31 32 /* double-check the compression */ 33 #define REGISTER_MAP_VERIFY false 34 35 /* verbose logging */ 36 #define REGISTER_MAP_VERBOSE false 37 38 //#define REGISTER_MAP_STATS 39 40 // fwd 41 static void outputTypeVector(const RegType* regs, int insnRegCount, u1* data); 42 static bool verifyMap(VerifierData* vdata, const RegisterMap* pMap); 43 static int compareMaps(const RegisterMap* pMap1, const RegisterMap* pMap2); 44 45 #ifdef REGISTER_MAP_STATS 46 static void computeMapStats(RegisterMap* pMap, const Method* method); 47 #endif 48 static RegisterMap* compressMapDifferential(const RegisterMap* pMap,\ 49 const Method* meth); 50 static RegisterMap* uncompressMapDifferential(const RegisterMap* pMap); 51 52 #ifdef REGISTER_MAP_STATS 53 /* 54 * Generate some statistics on the register maps we create and use. 55 */ 56 #define kMaxGcPointGap 50 57 #define kUpdatePosnMinRegs 24 58 #define kNumUpdatePosns 8 59 #define kMaxDiffBits 20 60 typedef struct MapStats { 61 /* 62 * Buckets measuring the distance between GC points. This tells us how 63 * many bits we need to encode the advancing program counter. We ignore 64 * some of the "long tail" entries. 65 */ 66 int gcPointGap[kMaxGcPointGap]; 67 68 /* 69 * Number of gaps. Equal to (number of gcPoints - number of methods), 70 * since the computation isn't including the initial gap. 71 */ 72 int gcGapCount; 73 74 /* 75 * Number of gaps. 76 */ 77 int totalGcPointCount; 78 79 /* 80 * For larger methods (>= 24 registers), measure in which octant register 81 * updates occur. This should help us understand whether register 82 * changes tend to cluster in the low regs even for large methods. 83 */ 84 int updatePosn[kNumUpdatePosns]; 85 86 /* 87 * For all methods, count up the number of changes to registers < 16 88 * and >= 16. 89 */ 90 int updateLT16; 91 int updateGE16; 92 93 /* 94 * Histogram of the number of bits that differ between adjacent entries. 95 */ 96 int numDiffBits[kMaxDiffBits]; 97 98 99 /* 100 * Track the number of expanded maps, and the heap space required to 101 * hold them. 102 */ 103 int numExpandedMaps; 104 int totalExpandedMapSize; 105 } MapStats; 106 #endif 107 108 /* 109 * Prepare some things. 110 */ 111 bool dvmRegisterMapStartup(void) 112 { 113 #ifdef REGISTER_MAP_STATS 114 MapStats* pStats = calloc(1, sizeof(MapStats)); 115 gDvm.registerMapStats = pStats; 116 #endif 117 return true; 118 } 119 120 /* 121 * Clean up. 122 */ 123 void dvmRegisterMapShutdown(void) 124 { 125 #ifdef REGISTER_MAP_STATS 126 free(gDvm.registerMapStats); 127 #endif 128 } 129 130 /* 131 * Write stats to log file. 132 */ 133 void dvmRegisterMapDumpStats(void) 134 { 135 #ifdef REGISTER_MAP_STATS 136 MapStats* pStats = (MapStats*) gDvm.registerMapStats; 137 int i, end; 138 139 for (end = kMaxGcPointGap-1; end >= 0; end--) { 140 if (pStats->gcPointGap[end] != 0) 141 break; 142 } 143 144 LOGI("Register Map gcPointGap stats (diff count=%d, total=%d):\n", 145 pStats->gcGapCount, pStats->totalGcPointCount); 146 assert(pStats->gcPointGap[0] == 0); 147 for (i = 1; i <= end; i++) { 148 LOGI(" %2d %d\n", i, pStats->gcPointGap[i]); 149 } 150 151 152 for (end = kMaxDiffBits-1; end >= 0; end--) { 153 if (pStats->numDiffBits[end] != 0) 154 break; 155 } 156 157 LOGI("Register Map bit difference stats:\n"); 158 for (i = 0; i <= end; i++) { 159 LOGI(" %2d %d\n", i, pStats->numDiffBits[i]); 160 } 161 162 163 LOGI("Register Map update position stats (lt16=%d ge16=%d):\n", 164 pStats->updateLT16, pStats->updateGE16); 165 for (i = 0; i < kNumUpdatePosns; i++) { 166 LOGI(" %2d %d\n", i, pStats->updatePosn[i]); 167 } 168 #endif 169 } 170 171 172 /* 173 * =========================================================================== 174 * Map generation 175 * =========================================================================== 176 */ 177 178 /* 179 * Generate the register map for a method that has just been verified 180 * (i.e. we're doing this as part of verification). 181 * 182 * For type-precise determination we have all the data we need, so we 183 * just need to encode it in some clever fashion. 184 * 185 * Returns a pointer to a newly-allocated RegisterMap, or NULL on failure. 186 */ 187 RegisterMap* dvmGenerateRegisterMapV(VerifierData* vdata) 188 { 189 static const int kHeaderSize = offsetof(RegisterMap, data); 190 RegisterMap* pMap = NULL; 191 RegisterMap* pResult = NULL; 192 RegisterMapFormat format; 193 u1 regWidth; 194 u1* mapData; 195 int i, bytesForAddr, gcPointCount; 196 int bufSize; 197 198 if (vdata->method->registersSize >= 2048) { 199 LOGE("ERROR: register map can't handle %d registers\n", 200 vdata->method->registersSize); 201 goto bail; 202 } 203 regWidth = (vdata->method->registersSize + 7) / 8; 204 205 /* 206 * Decide if we need 8 or 16 bits to hold the address. Strictly speaking 207 * we only need 16 bits if we actually encode an address >= 256 -- if 208 * the method has a section at the end without GC points (e.g. array 209 * data) we don't need to count it. The situation is unusual, and 210 * detecting it requires scanning the entire method, so we don't bother. 211 */ 212 if (vdata->insnsSize < 256) { 213 format = kRegMapFormatCompact8; 214 bytesForAddr = 1; 215 } else { 216 format = kRegMapFormatCompact16; 217 bytesForAddr = 2; 218 } 219 220 /* 221 * Count up the number of GC point instructions. 222 * 223 * NOTE: this does not automatically include the first instruction, 224 * since we don't count method entry as a GC point. 225 */ 226 gcPointCount = 0; 227 for (i = 0; i < (int) vdata->insnsSize; i++) { 228 if (dvmInsnIsGcPoint(vdata->insnFlags, i)) 229 gcPointCount++; 230 } 231 if (gcPointCount >= 65536) { 232 /* we could handle this, but in practice we don't get near this */ 233 LOGE("ERROR: register map can't handle %d gc points in one method\n", 234 gcPointCount); 235 goto bail; 236 } 237 238 /* 239 * Allocate a buffer to hold the map data. 240 */ 241 bufSize = kHeaderSize + gcPointCount * (bytesForAddr + regWidth); 242 243 LOGV("+++ grm: %s.%s (adr=%d gpc=%d rwd=%d bsz=%d)\n", 244 vdata->method->clazz->descriptor, vdata->method->name, 245 bytesForAddr, gcPointCount, regWidth, bufSize); 246 247 pMap = (RegisterMap*) malloc(bufSize); 248 dvmRegisterMapSetFormat(pMap, format); 249 dvmRegisterMapSetOnHeap(pMap, true); 250 dvmRegisterMapSetRegWidth(pMap, regWidth); 251 dvmRegisterMapSetNumEntries(pMap, gcPointCount); 252 253 /* 254 * Populate it. 255 */ 256 mapData = pMap->data; 257 for (i = 0; i < (int) vdata->insnsSize; i++) { 258 if (dvmInsnIsGcPoint(vdata->insnFlags, i)) { 259 assert(vdata->addrRegs[i] != NULL); 260 if (format == kRegMapFormatCompact8) { 261 *mapData++ = i; 262 } else /*kRegMapFormatCompact16*/ { 263 *mapData++ = i & 0xff; 264 *mapData++ = i >> 8; 265 } 266 outputTypeVector(vdata->addrRegs[i], vdata->insnRegCount, mapData); 267 mapData += regWidth; 268 } 269 } 270 271 LOGV("mapData=%p pMap=%p bufSize=%d\n", mapData, pMap, bufSize); 272 assert(mapData - (const u1*) pMap == bufSize); 273 274 if (REGISTER_MAP_VERIFY && !verifyMap(vdata, pMap)) 275 goto bail; 276 #ifdef REGISTER_MAP_STATS 277 computeMapStats(pMap, vdata->method); 278 #endif 279 280 /* 281 * Try to compress the map. 282 */ 283 RegisterMap* pCompMap; 284 285 pCompMap = compressMapDifferential(pMap, vdata->method); 286 if (pCompMap != NULL) { 287 if (REGISTER_MAP_VERIFY) { 288 /* 289 * Expand the compressed map we just created, and compare it 290 * to the original. Abort the VM if it doesn't match up. 291 */ 292 RegisterMap* pUncompMap; 293 pUncompMap = uncompressMapDifferential(pCompMap); 294 if (pUncompMap == NULL) { 295 LOGE("Map failed to uncompress - %s.%s\n", 296 vdata->method->clazz->descriptor, 297 vdata->method->name); 298 free(pCompMap); 299 /* bad - compression is broken or we're out of memory */ 300 dvmAbort(); 301 } else { 302 if (compareMaps(pMap, pUncompMap) != 0) { 303 LOGE("Map comparison failed - %s.%s\n", 304 vdata->method->clazz->descriptor, 305 vdata->method->name); 306 free(pCompMap); 307 /* bad - compression is broken */ 308 dvmAbort(); 309 } 310 311 /* verify succeeded */ 312 free(pUncompMap); 313 } 314 } 315 316 if (REGISTER_MAP_VERBOSE) { 317 LOGD("Good compress on %s.%s\n", 318 vdata->method->clazz->descriptor, 319 vdata->method->name); 320 } 321 free(pMap); 322 pMap = pCompMap; 323 } else { 324 if (REGISTER_MAP_VERBOSE) { 325 LOGD("Unable to compress %s.%s (ent=%d rw=%d)\n", 326 vdata->method->clazz->descriptor, 327 vdata->method->name, 328 dvmRegisterMapGetNumEntries(pMap), 329 dvmRegisterMapGetRegWidth(pMap)); 330 } 331 } 332 333 pResult = pMap; 334 335 bail: 336 return pResult; 337 } 338 339 /* 340 * Release the storage held by a RegisterMap. 341 */ 342 void dvmFreeRegisterMap(RegisterMap* pMap) 343 { 344 if (pMap == NULL) 345 return; 346 347 assert(dvmRegisterMapGetOnHeap(pMap)); 348 free(pMap); 349 } 350 351 /* 352 * Determine if the RegType value is a reference type. 353 * 354 * Ordinarily we include kRegTypeZero in the "is it a reference" 355 * check. There's no value in doing so here, because we know 356 * the register can't hold anything but zero. 357 */ 358 static inline bool isReferenceType(RegType type) 359 { 360 return (type > kRegTypeMAX || type == kRegTypeUninit); 361 } 362 363 /* 364 * Given a line of registers, output a bit vector that indicates whether 365 * or not the register holds a reference type (which could be null). 366 * 367 * We use '1' to indicate it's a reference, '0' for anything else (numeric 368 * value, uninitialized data, merge conflict). Register 0 will be found 369 * in the low bit of the first byte. 370 */ 371 static void outputTypeVector(const RegType* regs, int insnRegCount, u1* data) 372 { 373 u1 val = 0; 374 int i; 375 376 for (i = 0; i < insnRegCount; i++) { 377 RegType type = *regs++; 378 val >>= 1; 379 if (isReferenceType(type)) 380 val |= 0x80; /* set hi bit */ 381 382 if ((i & 0x07) == 7) 383 *data++ = val; 384 } 385 if ((i & 0x07) != 0) { 386 /* flush bits from last byte */ 387 val >>= 8 - (i & 0x07); 388 *data++ = val; 389 } 390 } 391 392 /* 393 * Print the map as a series of binary strings. 394 * 395 * Pass in method->registersSize if known, or -1 if not. 396 */ 397 static void dumpRegisterMap(const RegisterMap* pMap, int registersSize) 398 { 399 const u1* rawMap = pMap->data; 400 const RegisterMapFormat format = dvmRegisterMapGetFormat(pMap); 401 const int numEntries = dvmRegisterMapGetNumEntries(pMap); 402 const int regWidth = dvmRegisterMapGetRegWidth(pMap); 403 int addrWidth; 404 405 switch (format) { 406 case kRegMapFormatCompact8: 407 addrWidth = 1; 408 break; 409 case kRegMapFormatCompact16: 410 addrWidth = 2; 411 break; 412 default: 413 /* can't happen */ 414 LOGE("Can only dump Compact8 / Compact16 maps (not %d)\n", format); 415 return; 416 } 417 418 if (registersSize < 0) 419 registersSize = 8 * regWidth; 420 assert(registersSize <= regWidth * 8); 421 422 int ent; 423 for (ent = 0; ent < numEntries; ent++) { 424 int i, addr; 425 426 addr = *rawMap++; 427 if (addrWidth > 1) 428 addr |= (*rawMap++) << 8; 429 430 const u1* dataStart = rawMap; 431 u1 val = 0; 432 433 /* create binary string */ 434 char outBuf[registersSize +1]; 435 for (i = 0; i < registersSize; i++) { 436 val >>= 1; 437 if ((i & 0x07) == 0) 438 val = *rawMap++; 439 440 outBuf[i] = '0' + (val & 0x01); 441 } 442 outBuf[i] = '\0'; 443 444 /* back up and create hex dump */ 445 char hexBuf[regWidth * 3 +1]; 446 char* cp = hexBuf; 447 rawMap = dataStart; 448 for (i = 0; i < regWidth; i++) { 449 sprintf(cp, " %02x", *rawMap++); 450 cp += 3; 451 } 452 hexBuf[i * 3] = '\0'; 453 454 LOGD(" %04x %s %s\n", addr, outBuf, hexBuf); 455 } 456 } 457 458 /* 459 * Double-check the map. 460 * 461 * We run through all of the data in the map, and compare it to the original. 462 * Only works on uncompressed data. 463 */ 464 static bool verifyMap(VerifierData* vdata, const RegisterMap* pMap) 465 { 466 const u1* rawMap = pMap->data; 467 const RegisterMapFormat format = dvmRegisterMapGetFormat(pMap); 468 const int numEntries = dvmRegisterMapGetNumEntries(pMap); 469 int ent; 470 bool dumpMap = false; 471 472 if (false) { 473 const char* cd = "Landroid/net/http/Request;"; 474 const char* mn = "readResponse"; 475 if (strcmp(vdata->method->clazz->descriptor, cd) == 0 && 476 strcmp(vdata->method->name, mn) == 0) 477 { 478 char* desc; 479 desc = dexProtoCopyMethodDescriptor(&vdata->method->prototype); 480 LOGI("Map for %s.%s %s\n", vdata->method->clazz->descriptor, 481 vdata->method->name, desc); 482 free(desc); 483 484 dumpMap = true; 485 } 486 } 487 488 if ((vdata->method->registersSize + 7) / 8 != pMap->regWidth) { 489 LOGE("GLITCH: registersSize=%d, regWidth=%d\n", 490 vdata->method->registersSize, pMap->regWidth); 491 return false; 492 } 493 494 for (ent = 0; ent < numEntries; ent++) { 495 int addr; 496 497 switch (format) { 498 case kRegMapFormatCompact8: 499 addr = *rawMap++; 500 break; 501 case kRegMapFormatCompact16: 502 addr = *rawMap++; 503 addr |= (*rawMap++) << 8; 504 break; 505 default: 506 /* shouldn't happen */ 507 LOGE("GLITCH: bad format (%d)", format); 508 dvmAbort(); 509 } 510 511 const RegType* regs = vdata->addrRegs[addr]; 512 if (regs == NULL) { 513 LOGE("GLITCH: addr %d has no data\n", addr); 514 return false; 515 } 516 517 u1 val = 0; 518 int i; 519 520 for (i = 0; i < vdata->method->registersSize; i++) { 521 bool bitIsRef, regIsRef; 522 523 val >>= 1; 524 if ((i & 0x07) == 0) { 525 /* load next byte of data */ 526 val = *rawMap++; 527 } 528 529 bitIsRef = val & 0x01; 530 531 RegType type = regs[i]; 532 regIsRef = isReferenceType(type); 533 534 if (bitIsRef != regIsRef) { 535 LOGE("GLITCH: addr %d reg %d: bit=%d reg=%d(%d)\n", 536 addr, i, bitIsRef, regIsRef, type); 537 return false; 538 } 539 } 540 541 /* rawMap now points to the address field of the next entry */ 542 } 543 544 if (dumpMap) 545 dumpRegisterMap(pMap, vdata->method->registersSize); 546 547 return true; 548 } 549 550 551 /* 552 * =========================================================================== 553 * DEX generation & parsing 554 * =========================================================================== 555 */ 556 557 /* 558 * Advance "ptr" to ensure 32-bit alignment. 559 */ 560 static inline u1* align32(u1* ptr) 561 { 562 return (u1*) (((int) ptr + 3) & ~0x03); 563 } 564 565 /* 566 * Compute the size, in bytes, of a register map. 567 */ 568 static size_t computeRegisterMapSize(const RegisterMap* pMap) 569 { 570 static const int kHeaderSize = offsetof(RegisterMap, data); 571 u1 format = dvmRegisterMapGetFormat(pMap); 572 u2 numEntries = dvmRegisterMapGetNumEntries(pMap); 573 574 assert(pMap != NULL); 575 576 switch (format) { 577 case kRegMapFormatNone: 578 return 1; 579 case kRegMapFormatCompact8: 580 return kHeaderSize + (1 + pMap->regWidth) * numEntries; 581 case kRegMapFormatCompact16: 582 return kHeaderSize + (2 + pMap->regWidth) * numEntries; 583 case kRegMapFormatDifferential: 584 { 585 /* kHeaderSize + decoded ULEB128 length */ 586 const u1* ptr = pMap->data; 587 int len = readUnsignedLeb128(&ptr); 588 return len + (ptr - (u1*) pMap); 589 } 590 default: 591 LOGE("Bad register map format %d\n", format); 592 dvmAbort(); 593 return 0; 594 } 595 } 596 597 /* 598 * Output the map for a single method, if it has one. 599 * 600 * Abstract and native methods have no map. All others are expected to 601 * have one, since we know the class verified successfully. 602 * 603 * This strips the "allocated on heap" flag from the format byte, so that 604 * direct-mapped maps are correctly identified as such. 605 */ 606 static bool writeMapForMethod(const Method* meth, u1** pPtr) 607 { 608 if (meth->registerMap == NULL) { 609 if (!dvmIsAbstractMethod(meth) && !dvmIsNativeMethod(meth)) { 610 LOGW("Warning: no map available for %s.%s\n", 611 meth->clazz->descriptor, meth->name); 612 /* weird, but keep going */ 613 } 614 *(*pPtr)++ = kRegMapFormatNone; 615 return true; 616 } 617 618 /* serialize map into the buffer */ 619 size_t mapSize = computeRegisterMapSize(meth->registerMap); 620 memcpy(*pPtr, meth->registerMap, mapSize); 621 622 /* strip the "on heap" flag out of the format byte, which is always first */ 623 assert(**pPtr == meth->registerMap->format); 624 **pPtr &= ~(kRegMapFormatOnHeap); 625 626 *pPtr += mapSize; 627 628 return true; 629 } 630 631 /* 632 * Write maps for all methods in the specified class to the buffer, which 633 * can hold at most "length" bytes. "*pPtr" will be advanced past the end 634 * of the data we write. 635 */ 636 static bool writeMapsAllMethods(DvmDex* pDvmDex, const ClassObject* clazz, 637 u1** pPtr, size_t length) 638 { 639 RegisterMapMethodPool* pMethodPool; 640 u1* ptr = *pPtr; 641 int i, methodCount; 642 643 /* artificial limit */ 644 if (clazz->virtualMethodCount + clazz->directMethodCount >= 65536) { 645 LOGE("Too many methods in %s\n", clazz->descriptor); 646 return false; 647 } 648 649 pMethodPool = (RegisterMapMethodPool*) ptr; 650 ptr += offsetof(RegisterMapMethodPool, methodData); 651 methodCount = 0; 652 653 /* 654 * Run through all methods, direct then virtual. The class loader will 655 * traverse them in the same order. (We could split them into two 656 * distinct pieces, but there doesn't appear to be any value in doing 657 * so other than that it makes class loading slightly less fragile.) 658 * 659 * The class loader won't know about miranda methods at the point 660 * where it parses this, so we omit those. 661 * 662 * TODO: consider omitting all native/abstract definitions. Should be 663 * safe, though we lose the ability to sanity-check against the 664 * method counts in the DEX file. 665 */ 666 for (i = 0; i < clazz->directMethodCount; i++) { 667 const Method* meth = &clazz->directMethods[i]; 668 if (dvmIsMirandaMethod(meth)) 669 continue; 670 if (!writeMapForMethod(&clazz->directMethods[i], &ptr)) { 671 return false; 672 } 673 methodCount++; 674 //ptr = align32(ptr); 675 } 676 677 for (i = 0; i < clazz->virtualMethodCount; i++) { 678 const Method* meth = &clazz->virtualMethods[i]; 679 if (dvmIsMirandaMethod(meth)) 680 continue; 681 if (!writeMapForMethod(&clazz->virtualMethods[i], &ptr)) { 682 return false; 683 } 684 methodCount++; 685 //ptr = align32(ptr); 686 } 687 688 pMethodPool->methodCount = methodCount; 689 690 *pPtr = ptr; 691 return true; 692 } 693 694 /* 695 * Write maps for all classes to the specified buffer, which can hold at 696 * most "length" bytes. 697 * 698 * Returns the actual length used, or 0 on failure. 699 */ 700 static size_t writeMapsAllClasses(DvmDex* pDvmDex, u1* basePtr, size_t length) 701 { 702 DexFile* pDexFile = pDvmDex->pDexFile; 703 u4 count = pDexFile->pHeader->classDefsSize; 704 RegisterMapClassPool* pClassPool; 705 u4* offsetTable; 706 u1* ptr = basePtr; 707 u4 idx; 708 709 assert(gDvm.optimizing); 710 711 pClassPool = (RegisterMapClassPool*) ptr; 712 ptr += offsetof(RegisterMapClassPool, classDataOffset); 713 offsetTable = (u4*) ptr; 714 ptr += count * sizeof(u4); 715 716 pClassPool->numClasses = count; 717 718 /* 719 * We want an entry for every class, loaded or not. 720 */ 721 for (idx = 0; idx < count; idx++) { 722 const DexClassDef* pClassDef; 723 const char* classDescriptor; 724 ClassObject* clazz; 725 726 pClassDef = dexGetClassDef(pDexFile, idx); 727 classDescriptor = dexStringByTypeIdx(pDexFile, pClassDef->classIdx); 728 729 /* 730 * All classes have been loaded into the bootstrap class loader. 731 * If we can find it, and it was successfully pre-verified, we 732 * run through its methods and add the register maps. 733 * 734 * If it wasn't pre-verified then we know it can't have any 735 * register maps. Classes that can't be loaded or failed 736 * verification get an empty slot in the index. 737 */ 738 clazz = NULL; 739 if ((pClassDef->accessFlags & CLASS_ISPREVERIFIED) != 0) 740 clazz = dvmLookupClass(classDescriptor, NULL, false); 741 742 if (clazz != NULL) { 743 offsetTable[idx] = ptr - basePtr; 744 LOGVV("%d -> offset %d (%p-%p)\n", 745 idx, offsetTable[idx], ptr, basePtr); 746 747 if (!writeMapsAllMethods(pDvmDex, clazz, &ptr, 748 length - (ptr - basePtr))) 749 { 750 return 0; 751 } 752 753 ptr = align32(ptr); 754 LOGVV("Size %s (%d+%d methods): %d\n", clazz->descriptor, 755 clazz->directMethodCount, clazz->virtualMethodCount, 756 (ptr - basePtr) - offsetTable[idx]); 757 } else { 758 LOGV("%4d NOT mapadding '%s'\n", idx, classDescriptor); 759 assert(offsetTable[idx] == 0); 760 } 761 } 762 763 if (ptr - basePtr >= (int)length) { 764 /* a bit late */ 765 LOGE("Buffer overrun\n"); 766 dvmAbort(); 767 } 768 769 return ptr - basePtr; 770 } 771 772 /* 773 * Generate a register map set for all verified classes in "pDvmDex". 774 */ 775 RegisterMapBuilder* dvmGenerateRegisterMaps(DvmDex* pDvmDex) 776 { 777 RegisterMapBuilder* pBuilder; 778 779 pBuilder = (RegisterMapBuilder*) calloc(1, sizeof(RegisterMapBuilder)); 780 if (pBuilder == NULL) 781 return NULL; 782 783 /* 784 * We have a couple of options here: 785 * (1) Compute the size of the output, and malloc a buffer. 786 * (2) Create a "large-enough" anonymous mmap region. 787 * 788 * The nice thing about option #2 is that we don't have to traverse 789 * all of the classes and methods twice. The risk is that we might 790 * not make the region large enough. Since the pages aren't mapped 791 * until used we can allocate a semi-absurd amount of memory without 792 * worrying about the effect on the rest of the system. 793 * 794 * The basic encoding on the largest jar file requires about 1MB of 795 * storage. We map out 4MB here. (TODO: guarantee that the last 796 * page of the mapping is marked invalid, so we reliably fail if 797 * we overrun.) 798 */ 799 if (sysCreatePrivateMap(4 * 1024 * 1024, &pBuilder->memMap) != 0) { 800 free(pBuilder); 801 return NULL; 802 } 803 804 /* 805 * Create the maps. 806 */ 807 size_t actual = writeMapsAllClasses(pDvmDex, (u1*)pBuilder->memMap.addr, 808 pBuilder->memMap.length); 809 if (actual == 0) { 810 dvmFreeRegisterMapBuilder(pBuilder); 811 return NULL; 812 } 813 814 LOGV("TOTAL size of register maps: %d\n", actual); 815 816 pBuilder->data = pBuilder->memMap.addr; 817 pBuilder->size = actual; 818 return pBuilder; 819 } 820 821 /* 822 * Free the builder. 823 */ 824 void dvmFreeRegisterMapBuilder(RegisterMapBuilder* pBuilder) 825 { 826 if (pBuilder == NULL) 827 return; 828 829 sysReleaseShmem(&pBuilder->memMap); 830 free(pBuilder); 831 } 832 833 834 /* 835 * Find the data for the specified class. 836 * 837 * If there's no register map data, or none for this class, we return NULL. 838 */ 839 const void* dvmRegisterMapGetClassData(const DexFile* pDexFile, u4 classIdx, 840 u4* pNumMaps) 841 { 842 const RegisterMapClassPool* pClassPool; 843 const RegisterMapMethodPool* pMethodPool; 844 845 pClassPool = (const RegisterMapClassPool*) pDexFile->pRegisterMapPool; 846 if (pClassPool == NULL) 847 return NULL; 848 849 if (classIdx >= pClassPool->numClasses) { 850 LOGE("bad class index (%d vs %d)\n", classIdx, pClassPool->numClasses); 851 dvmAbort(); 852 } 853 854 u4 classOffset = pClassPool->classDataOffset[classIdx]; 855 if (classOffset == 0) { 856 LOGV("+++ no map for classIdx=%d\n", classIdx); 857 return NULL; 858 } 859 860 pMethodPool = 861 (const RegisterMapMethodPool*) (((u1*) pClassPool) + classOffset); 862 if (pNumMaps != NULL) 863 *pNumMaps = pMethodPool->methodCount; 864 return pMethodPool->methodData; 865 } 866 867 /* 868 * This advances "*pPtr" and returns its original value. 869 */ 870 const RegisterMap* dvmRegisterMapGetNext(const void** pPtr) 871 { 872 const RegisterMap* pMap = *pPtr; 873 874 *pPtr = /*align32*/(((u1*) pMap) + computeRegisterMapSize(pMap)); 875 LOGVV("getNext: %p -> %p (f=0x%x w=%d e=%d)\n", 876 pMap, *pPtr, pMap->format, pMap->regWidth, 877 dvmRegisterMapGetNumEntries(pMap)); 878 return pMap; 879 } 880 881 882 /* 883 * =========================================================================== 884 * Utility functions 885 * =========================================================================== 886 */ 887 888 /* 889 * Return the data for the specified address, or NULL if not found. 890 * 891 * The result must be released with dvmReleaseRegisterMapLine(). 892 */ 893 const u1* dvmRegisterMapGetLine(const RegisterMap* pMap, int addr) 894 { 895 int addrWidth, lineWidth; 896 u1 format = dvmRegisterMapGetFormat(pMap); 897 u2 numEntries = dvmRegisterMapGetNumEntries(pMap); 898 899 assert(numEntries > 0); 900 901 switch (format) { 902 case kRegMapFormatNone: 903 return NULL; 904 case kRegMapFormatCompact8: 905 addrWidth = 1; 906 break; 907 case kRegMapFormatCompact16: 908 addrWidth = 2; 909 break; 910 default: 911 LOGE("Unknown format %d\n", format); 912 dvmAbort(); 913 return NULL; 914 } 915 916 lineWidth = addrWidth + pMap->regWidth; 917 918 /* 919 * Find the appropriate entry. Many maps are very small, some are very 920 * large. 921 */ 922 static const int kSearchThreshold = 8; 923 const u1* data = NULL; 924 int lineAddr; 925 926 if (numEntries < kSearchThreshold) { 927 int i; 928 data = pMap->data; 929 for (i = numEntries; i > 0; i--) { 930 lineAddr = data[0]; 931 if (addrWidth > 1) 932 lineAddr |= data[1] << 8; 933 if (lineAddr == addr) 934 return data + addrWidth; 935 936 data += lineWidth; 937 } 938 assert(data == pMap->data + lineWidth * numEntries); 939 } else { 940 int hi, lo, mid; 941 942 lo = 0; 943 hi = numEntries -1; 944 945 while (hi >= lo) { 946 mid = (hi + lo) / 2; 947 data = pMap->data + lineWidth * mid; 948 949 lineAddr = data[0]; 950 if (addrWidth > 1) 951 lineAddr |= data[1] << 8; 952 953 if (addr > lineAddr) { 954 lo = mid + 1; 955 } else if (addr < lineAddr) { 956 hi = mid - 1; 957 } else { 958 return data + addrWidth; 959 } 960 } 961 } 962 963 return NULL; 964 } 965 966 /* 967 * Compare two register maps. 968 * 969 * Returns 0 if they're equal, nonzero if not. 970 */ 971 static int compareMaps(const RegisterMap* pMap1, const RegisterMap* pMap2) 972 { 973 size_t size1, size2; 974 975 size1 = computeRegisterMapSize(pMap1); 976 size2 = computeRegisterMapSize(pMap2); 977 if (size1 != size2) { 978 LOGI("compareMaps: size mismatch (%zd vs %zd)\n", size1, size2); 979 return -1; 980 } 981 982 if (memcmp(pMap1, pMap2, size1) != 0) { 983 LOGI("compareMaps: content mismatch\n"); 984 return -1; 985 } 986 987 return 0; 988 } 989 990 991 /* 992 * Get the expanded form of the register map associated with the method. 993 * 994 * If the map is already in one of the uncompressed formats, we return 995 * immediately. Otherwise, we expand the map and replace method's register 996 * map pointer, freeing it if it was allocated on the heap. 997 * 998 * NOTE: this function is not synchronized; external locking is mandatory 999 * (unless we're in the zygote, where single-threaded access is guaranteed). 1000 */ 1001 const RegisterMap* dvmGetExpandedRegisterMap0(Method* method) 1002 { 1003 const RegisterMap* curMap = method->registerMap; 1004 RegisterMap* newMap; 1005 1006 if (curMap == NULL) 1007 return NULL; 1008 1009 /* sanity check to ensure this isn't called w/o external locking */ 1010 /* (if we use this at a time other than during GC, fix/remove this test) */ 1011 if (true) { 1012 if (!gDvm.zygote && dvmTryLockMutex(&gDvm.gcHeapLock) == 0) { 1013 LOGE("GLITCH: dvmGetExpandedRegisterMap not called at GC time\n"); 1014 dvmAbort(); 1015 } 1016 } 1017 1018 RegisterMapFormat format = dvmRegisterMapGetFormat(curMap); 1019 switch (format) { 1020 case kRegMapFormatCompact8: 1021 case kRegMapFormatCompact16: 1022 if (REGISTER_MAP_VERBOSE) { 1023 if (dvmRegisterMapGetOnHeap(curMap)) { 1024 LOGD("RegMap: already expanded: %s.%s\n", 1025 method->clazz->descriptor, method->name); 1026 } else { 1027 LOGD("RegMap: stored w/o compression: %s.%s\n", 1028 method->clazz->descriptor, method->name); 1029 } 1030 } 1031 return curMap; 1032 case kRegMapFormatDifferential: 1033 newMap = uncompressMapDifferential(curMap); 1034 break; 1035 default: 1036 LOGE("Unknown format %d in dvmGetExpandedRegisterMap\n", format); 1037 dvmAbort(); 1038 newMap = NULL; // make gcc happy 1039 } 1040 1041 if (newMap == NULL) { 1042 LOGE("Map failed to uncompress (fmt=%d) %s.%s\n", 1043 format, method->clazz->descriptor, method->name); 1044 return NULL; 1045 } 1046 1047 #ifdef REGISTER_MAP_STATS 1048 /* 1049 * Gather and display some stats. 1050 */ 1051 { 1052 MapStats* pStats = (MapStats*) gDvm.registerMapStats; 1053 pStats->numExpandedMaps++; 1054 pStats->totalExpandedMapSize += computeRegisterMapSize(newMap); 1055 LOGD("RMAP: count=%d size=%d\n", 1056 pStats->numExpandedMaps, pStats->totalExpandedMapSize); 1057 } 1058 #endif 1059 1060 IF_LOGV() { 1061 char* desc = dexProtoCopyMethodDescriptor(&method->prototype); 1062 LOGV("Expanding map -> %s.%s:%s\n", 1063 method->clazz->descriptor, method->name, desc); 1064 free(desc); 1065 } 1066 1067 /* 1068 * Update method, and free compressed map if it was sitting on the heap. 1069 */ 1070 dvmSetRegisterMap(method, newMap); 1071 1072 if (dvmRegisterMapGetOnHeap(curMap)) 1073 dvmFreeRegisterMap((RegisterMap*) curMap); 1074 1075 return newMap; 1076 } 1077 1078 1079 /* 1080 * =========================================================================== 1081 * Map compression 1082 * =========================================================================== 1083 */ 1084 1085 /* 1086 Notes on map compression 1087 1088 The idea is to create a compressed form that will be uncompressed before 1089 use, with the output possibly saved in a cache. This means we can use an 1090 approach that is unsuited for random access if we choose. 1091 1092 In the event that a map simply does not work with our compression scheme, 1093 it's reasonable to store the map without compression. In the future we 1094 may want to have more than one compression scheme, and try each in turn, 1095 retaining the best. (We certainly want to keep the uncompressed form if it 1096 turns out to be smaller or even slightly larger than the compressed form.) 1097 1098 Each entry consists of an address and a bit vector. Adjacent entries are 1099 strongly correlated, suggesting differential encoding. 1100 1101 1102 Ideally we would avoid outputting adjacent entries with identical 1103 bit vectors. However, the register values at a given address do not 1104 imply anything about the set of valid registers at subsequent addresses. 1105 We therefore cannot omit an entry. 1106 1107 If the thread stack has a PC at an address without a corresponding 1108 entry in the register map, we must conservatively scan the registers in 1109 that thread. This can happen when single-stepping in the debugger, 1110 because the debugger is allowed to invoke arbitrary methods when 1111 a thread is stopped at a breakpoint. If we can guarantee that a GC 1112 thread scan will never happen while the debugger has that thread stopped, 1113 then we can lift this restriction and simply omit entries that don't 1114 change the bit vector from its previous state. 1115 1116 Each entry advances the address value by at least 1 (measured in 16-bit 1117 "code units"). Looking at the bootclasspath entries, advancing by 2 units 1118 is most common. Advances by 1 unit are far less common than advances by 1119 2 units, but more common than 5, and things fall off rapidly. Gaps of 1120 up to 220 code units appear in some computationally intensive bits of code, 1121 but are exceedingly rare. 1122 1123 If we sum up the number of transitions in a couple of ranges in framework.jar: 1124 [1,4]: 188998 of 218922 gaps (86.3%) 1125 [1,7]: 211647 of 218922 gaps (96.7%) 1126 Using a 3-bit delta, with one value reserved as an escape code, should 1127 yield good results for the address. 1128 1129 These results would change dramatically if we reduced the set of GC 1130 points by e.g. removing instructions like integer divide that are only 1131 present because they can throw and cause an allocation. 1132 1133 We also need to include an "initial gap", because the first few instructions 1134 in a method may not be GC points. 1135 1136 1137 By observation, many entries simply repeat the previous bit vector, or 1138 change only one or two bits. (This is with type-precise information; 1139 the rate of change of bits will be different if live-precise information 1140 is factored in). 1141 1142 Looking again at adjacent entries in framework.jar: 1143 0 bits changed: 63.0% 1144 1 bit changed: 32.2% 1145 After that it falls off rapidly, e.g. the number of entries with 2 bits 1146 changed is usually less than 1/10th of the number of entries with 1 bit 1147 changed. A solution that allows us to encode 0- or 1- bit changes 1148 efficiently will do well. 1149 1150 We still need to handle cases where a large number of bits change. We 1151 probably want a way to drop in a full copy of the bit vector when it's 1152 smaller than the representation of multiple bit changes. 1153 1154 1155 The bit-change information can be encoded as an index that tells the 1156 decoder to toggle the state. We want to encode the index in as few bits 1157 as possible, but we need to allow for fairly wide vectors (e.g. we have a 1158 method with 175 registers). We can deal with this in a couple of ways: 1159 (1) use an encoding that assumes few registers and has an escape code 1160 for larger numbers of registers; or (2) use different encodings based 1161 on how many total registers the method has. The choice depends to some 1162 extent on whether methods with large numbers of registers tend to modify 1163 the first 16 regs more often than the others. 1164 1165 The last N registers hold method arguments. If the bytecode is expected 1166 to be examined in a debugger, "dx" ensures that the contents of these 1167 registers won't change. Depending upon the encoding format, we may be 1168 able to take advantage of this. We still have to encode the initial 1169 state, but we know we'll never have to output a bit change for the last 1170 N registers. 1171 1172 Considering only methods with 16 or more registers, the "target octant" 1173 for register changes looks like this: 1174 [ 43.1%, 16.4%, 6.5%, 6.2%, 7.4%, 8.8%, 9.7%, 1.8% ] 1175 As expected, there are fewer changes at the end of the list where the 1176 arguments are kept, and more changes at the start of the list because 1177 register values smaller than 16 can be used in compact Dalvik instructions 1178 and hence are favored for frequently-used values. In general, the first 1179 octant is considerably more active than later entries, the last octant 1180 is much less active, and the rest are all about the same. 1181 1182 Looking at all bit changes in all methods, 94% are to registers 0-15. The 1183 encoding will benefit greatly by favoring the low-numbered registers. 1184 1185 1186 Some of the smaller methods have identical maps, and space could be 1187 saved by simply including a pointer to an earlier definition. This would 1188 be best accomplished by specifying a "pointer" format value, followed by 1189 a 3-byte (or ULEB128) offset. Implementing this would probably involve 1190 generating a hash value for each register map and maintaining a hash table. 1191 1192 In some cases there are repeating patterns in the bit vector that aren't 1193 adjacent. These could benefit from a dictionary encoding. This doesn't 1194 really become useful until the methods reach a certain size though, 1195 and managing the dictionary may incur more overhead than we want. 1196 1197 Large maps can be compressed significantly. The trouble is that, when 1198 we need to use them, we have to uncompress them onto the heap. We may 1199 get a better trade-off between storage size and heap usage by refusing to 1200 compress large maps, so that they can be memory mapped and used directly. 1201 (OTOH, only about 2% of the maps will ever actually be used.) 1202 1203 1204 ----- differential format ----- 1205 1206 // common header 1207 +00 1B format 1208 +01 1B regWidth 1209 +02 2B numEntries (little-endian) 1210 +04 nB length in bytes of the data that follows, in ULEB128 format 1211 (not strictly necessary; allows determination of size w/o full parse) 1212 +05+ 1B initial address (0-127), high bit set if max addr >= 256 1213 +06+ nB initial value for bit vector 1214 1215 // for each entry 1216 +00: CCCCBAAA 1217 1218 AAA: address difference. Values from 0 to 6 indicate an increment of 1 1219 to 7. A value of 7 indicates that the address difference is large, 1220 and the next byte is a ULEB128-encoded difference value. 1221 1222 B: determines the meaning of CCCC. 1223 1224 CCCC: if B is 0, this is the number of the bit to toggle (0-15). 1225 If B is 1, this is a count of the number of changed bits (1-14). A value 1226 of 0 means that no bits were changed, and a value of 15 indicates 1227 that enough bits were changed that it required less space to output 1228 the entire bit vector. 1229 1230 +01: (optional) ULEB128-encoded address difference 1231 1232 +01+: (optional) one or more ULEB128-encoded bit numbers, OR the entire 1233 bit vector. 1234 1235 The most common situation is an entry whose address has changed by 2-4 1236 code units, has no changes or just a single bit change, and the changed 1237 register is less than 16. We should therefore be able to encode a large 1238 number of entries with a single byte, which is half the size of the 1239 Compact8 encoding method. 1240 */ 1241 1242 /* 1243 * Compute some stats on an uncompressed register map. 1244 */ 1245 #ifdef REGISTER_MAP_STATS 1246 static void computeMapStats(RegisterMap* pMap, const Method* method) 1247 { 1248 MapStats* pStats = (MapStats*) gDvm.registerMapStats; 1249 const u1 format = dvmRegisterMapGetFormat(pMap); 1250 const u2 numEntries = dvmRegisterMapGetNumEntries(pMap); 1251 const u1* rawMap = pMap->data; 1252 const u1* prevData = NULL; 1253 int ent, addr, prevAddr = -1; 1254 1255 for (ent = 0; ent < numEntries; ent++) { 1256 switch (format) { 1257 case kRegMapFormatCompact8: 1258 addr = *rawMap++; 1259 break; 1260 case kRegMapFormatCompact16: 1261 addr = *rawMap++; 1262 addr |= (*rawMap++) << 8; 1263 break; 1264 default: 1265 /* shouldn't happen */ 1266 LOGE("GLITCH: bad format (%d)", format); 1267 dvmAbort(); 1268 } 1269 1270 const u1* dataStart = rawMap; 1271 1272 pStats->totalGcPointCount++; 1273 1274 /* 1275 * Gather "gap size" stats, i.e. the difference in addresses between 1276 * successive GC points. 1277 */ 1278 if (prevData != NULL) { 1279 assert(prevAddr >= 0); 1280 int addrDiff = addr - prevAddr; 1281 1282 if (addrDiff < 0) { 1283 LOGE("GLITCH: address went backward (0x%04x->0x%04x, %s.%s)\n", 1284 prevAddr, addr, method->clazz->descriptor, method->name); 1285 } else if (addrDiff > kMaxGcPointGap) { 1286 if (REGISTER_MAP_VERBOSE) { 1287 LOGI("HEY: addrDiff is %d, max %d (0x%04x->0x%04x %s.%s)\n", 1288 addrDiff, kMaxGcPointGap, prevAddr, addr, 1289 method->clazz->descriptor, method->name); 1290 } 1291 /* skip this one */ 1292 } else { 1293 pStats->gcPointGap[addrDiff]++; 1294 } 1295 pStats->gcGapCount++; 1296 1297 1298 /* 1299 * Compare bit vectors in adjacent entries. We want to count 1300 * up the number of bits that differ (to see if we frequently 1301 * change 0 or 1 bits) and get a sense for which part of the 1302 * vector changes the most often (near the start, middle, end). 1303 * 1304 * We only do the vector position quantization if we have at 1305 * least 16 registers in the method. 1306 */ 1307 int numDiff = 0; 1308 float div = (float) kNumUpdatePosns / method->registersSize; 1309 int regByte; 1310 for (regByte = 0; regByte < pMap->regWidth; regByte++) { 1311 int prev, cur, bit; 1312 1313 prev = prevData[regByte]; 1314 cur = dataStart[regByte]; 1315 1316 for (bit = 0; bit < 8; bit++) { 1317 if (((prev >> bit) & 1) != ((cur >> bit) & 1)) { 1318 numDiff++; 1319 1320 int bitNum = regByte * 8 + bit; 1321 1322 if (bitNum < 16) 1323 pStats->updateLT16++; 1324 else 1325 pStats->updateGE16++; 1326 1327 if (method->registersSize < 16) 1328 continue; 1329 1330 if (bitNum >= method->registersSize) { 1331 /* stuff off the end should be zero in both */ 1332 LOGE("WEIRD: bit=%d (%d/%d), prev=%02x cur=%02x\n", 1333 bit, regByte, method->registersSize, 1334 prev, cur); 1335 assert(false); 1336 } 1337 int idx = (int) (bitNum * div); 1338 if (!(idx >= 0 && idx < kNumUpdatePosns)) { 1339 LOGE("FAIL: bitNum=%d (of %d) div=%.3f idx=%d\n", 1340 bitNum, method->registersSize, div, idx); 1341 assert(false); 1342 } 1343 pStats->updatePosn[idx]++; 1344 } 1345 } 1346 } 1347 1348 if (numDiff > kMaxDiffBits) { 1349 if (REGISTER_MAP_VERBOSE) { 1350 LOGI("WOW: numDiff is %d, max %d\n", numDiff, kMaxDiffBits); 1351 } 1352 } else { 1353 pStats->numDiffBits[numDiff]++; 1354 } 1355 } 1356 1357 /* advance to start of next line */ 1358 rawMap += pMap->regWidth; 1359 1360 prevAddr = addr; 1361 prevData = dataStart; 1362 } 1363 } 1364 #endif 1365 1366 /* 1367 * Compute the difference between two bit vectors. 1368 * 1369 * If "lebOutBuf" is non-NULL, we output the bit indices in ULEB128 format 1370 * as we go. Otherwise, we just generate the various counts. 1371 * 1372 * The bit vectors are compared byte-by-byte, so any unused bits at the 1373 * end must be zero. 1374 * 1375 * Returns the number of bytes required to hold the ULEB128 output. 1376 * 1377 * If "pFirstBitChanged" or "pNumBitsChanged" are non-NULL, they will 1378 * receive the index of the first changed bit and the number of changed 1379 * bits, respectively. 1380 */ 1381 static int computeBitDiff(const u1* bits1, const u1* bits2, int byteWidth, 1382 int* pFirstBitChanged, int* pNumBitsChanged, u1* lebOutBuf) 1383 { 1384 int numBitsChanged = 0; 1385 int firstBitChanged = -1; 1386 int lebSize = 0; 1387 int byteNum; 1388 1389 /* 1390 * Run through the vectors, first comparing them at the byte level. This 1391 * will yield a fairly quick result if nothing has changed between them. 1392 */ 1393 for (byteNum = 0; byteNum < byteWidth; byteNum++) { 1394 u1 byte1 = *bits1++; 1395 u1 byte2 = *bits2++; 1396 if (byte1 != byte2) { 1397 /* 1398 * Walk through the byte, identifying the changed bits. 1399 */ 1400 int bitNum; 1401 for (bitNum = 0; bitNum < 8; bitNum++) { 1402 if (((byte1 >> bitNum) & 0x01) != ((byte2 >> bitNum) & 0x01)) { 1403 int bitOffset = (byteNum << 3) + bitNum; 1404 1405 if (firstBitChanged < 0) 1406 firstBitChanged = bitOffset; 1407 numBitsChanged++; 1408 1409 if (lebOutBuf == NULL) { 1410 lebSize += unsignedLeb128Size(bitOffset); 1411 } else { 1412 u1* curBuf = lebOutBuf; 1413 lebOutBuf = writeUnsignedLeb128(lebOutBuf, bitOffset); 1414 lebSize += lebOutBuf - curBuf; 1415 } 1416 } 1417 } 1418 } 1419 } 1420 1421 if (numBitsChanged > 0) 1422 assert(firstBitChanged >= 0); 1423 1424 if (pFirstBitChanged != NULL) 1425 *pFirstBitChanged = firstBitChanged; 1426 if (pNumBitsChanged != NULL) 1427 *pNumBitsChanged = numBitsChanged; 1428 1429 return lebSize; 1430 } 1431 1432 /* 1433 * Compress the register map with differential encoding. 1434 * 1435 * "meth" is only needed for debug output. 1436 * 1437 * On success, returns a newly-allocated RegisterMap. If the map is not 1438 * compatible for some reason, or fails to get smaller, this will return NULL. 1439 */ 1440 static RegisterMap* compressMapDifferential(const RegisterMap* pMap, 1441 const Method* meth) 1442 { 1443 RegisterMap* pNewMap = NULL; 1444 int origSize = computeRegisterMapSize(pMap); 1445 u1* tmpBuf = NULL; 1446 u1* tmpPtr; 1447 int addrWidth, regWidth, numEntries; 1448 bool debug = false; 1449 1450 if (false && 1451 strcmp(meth->clazz->descriptor, "Landroid/text/StaticLayout;") == 0 && 1452 strcmp(meth->name, "generate") == 0) 1453 { 1454 debug = true; 1455 } 1456 1457 u1 format = dvmRegisterMapGetFormat(pMap); 1458 switch (format) { 1459 case kRegMapFormatCompact8: 1460 addrWidth = 1; 1461 break; 1462 case kRegMapFormatCompact16: 1463 addrWidth = 2; 1464 break; 1465 default: 1466 LOGE("ERROR: can't compress map with format=%d\n", format); 1467 goto bail; 1468 } 1469 1470 regWidth = dvmRegisterMapGetRegWidth(pMap); 1471 numEntries = dvmRegisterMapGetNumEntries(pMap); 1472 1473 if (debug) { 1474 LOGI("COMPRESS: %s.%s aw=%d rw=%d ne=%d\n", 1475 meth->clazz->descriptor, meth->name, 1476 addrWidth, regWidth, numEntries); 1477 dumpRegisterMap(pMap, -1); 1478 } 1479 1480 if (numEntries <= 1) { 1481 LOGV("Can't compress map with 0 or 1 entries\n"); 1482 goto bail; 1483 } 1484 1485 /* 1486 * We don't know how large the compressed data will be. It's possible 1487 * for it to expand and become larger than the original. The header 1488 * itself is variable-sized, so we generate everything into a temporary 1489 * buffer and then copy it to form-fitting storage once we know how big 1490 * it will be (and that it's smaller than the original). 1491 * 1492 * If we use a size that is equal to the size of the input map plus 1493 * a value longer than a single entry can possibly expand to, we need 1494 * only check for overflow at the end of each entry. The worst case 1495 * for a single line is (1 + <ULEB8 address> + <full copy of vector>). 1496 * Addresses are 16 bits, so that's (1 + 3 + regWidth). 1497 * 1498 * The initial address offset and bit vector will take up less than 1499 * or equal to the amount of space required when uncompressed -- large 1500 * initial offsets are rejected. 1501 */ 1502 tmpBuf = (u1*) malloc(origSize + (1 + 3 + regWidth)); 1503 if (tmpBuf == NULL) 1504 goto bail; 1505 1506 tmpPtr = tmpBuf; 1507 1508 const u1* mapData = pMap->data; 1509 const u1* prevBits; 1510 u2 addr, prevAddr; 1511 1512 addr = *mapData++; 1513 if (addrWidth > 1) 1514 addr |= (*mapData++) << 8; 1515 1516 if (addr >= 128) { 1517 LOGV("Can't compress map with starting address >= 128\n"); 1518 goto bail; 1519 } 1520 1521 /* 1522 * Start by writing the initial address and bit vector data. The high 1523 * bit of the initial address is used to indicate the required address 1524 * width (which the decoder can't otherwise determine without parsing 1525 * the compressed data). 1526 */ 1527 *tmpPtr++ = addr | (addrWidth > 1 ? 0x80 : 0x00); 1528 memcpy(tmpPtr, mapData, regWidth); 1529 1530 prevBits = mapData; 1531 prevAddr = addr; 1532 1533 tmpPtr += regWidth; 1534 mapData += regWidth; 1535 1536 /* 1537 * Loop over all following entries. 1538 */ 1539 int entry; 1540 for (entry = 1; entry < numEntries; entry++) { 1541 int addrDiff; 1542 u1 key; 1543 1544 /* 1545 * Pull out the address and figure out how to encode it. 1546 */ 1547 addr = *mapData++; 1548 if (addrWidth > 1) 1549 addr |= (*mapData++) << 8; 1550 1551 if (debug) 1552 LOGI(" addr=0x%04x ent=%d (aw=%d)\n", addr, entry, addrWidth); 1553 1554 addrDiff = addr - prevAddr; 1555 assert(addrDiff > 0); 1556 if (addrDiff < 8) { 1557 /* small difference, encode in 3 bits */ 1558 key = addrDiff -1; /* set 00000AAA */ 1559 if (debug) 1560 LOGI(" : small %d, key=0x%02x\n", addrDiff, key); 1561 } else { 1562 /* large difference, output escape code */ 1563 key = 0x07; /* escape code for AAA */ 1564 if (debug) 1565 LOGI(" : large %d, key=0x%02x\n", addrDiff, key); 1566 } 1567 1568 int numBitsChanged, firstBitChanged, lebSize; 1569 1570 lebSize = computeBitDiff(prevBits, mapData, regWidth, 1571 &firstBitChanged, &numBitsChanged, NULL); 1572 1573 if (debug) { 1574 LOGI(" : diff fbc=%d nbc=%d ls=%d (rw=%d)\n", 1575 firstBitChanged, numBitsChanged, lebSize, regWidth); 1576 } 1577 1578 if (numBitsChanged == 0) { 1579 /* set B to 1 and CCCC to zero to indicate no bits were changed */ 1580 key |= 0x08; 1581 if (debug) LOGI(" : no bits changed\n"); 1582 } else if (numBitsChanged == 1 && firstBitChanged < 16) { 1583 /* set B to 0 and CCCC to the index of the changed bit */ 1584 key |= firstBitChanged << 4; 1585 if (debug) LOGI(" : 1 low bit changed\n"); 1586 } else if (numBitsChanged < 15 && lebSize < regWidth) { 1587 /* set B to 1 and CCCC to the number of bits */ 1588 key |= 0x08 | (numBitsChanged << 4); 1589 if (debug) LOGI(" : some bits changed\n"); 1590 } else { 1591 /* set B to 1 and CCCC to 0x0f so we store the entire vector */ 1592 key |= 0x08 | 0xf0; 1593 if (debug) LOGI(" : encode original\n"); 1594 } 1595 1596 /* 1597 * Encode output. Start with the key, follow with the address 1598 * diff (if it didn't fit in 3 bits), then the changed bit info. 1599 */ 1600 *tmpPtr++ = key; 1601 if ((key & 0x07) == 0x07) 1602 tmpPtr = writeUnsignedLeb128(tmpPtr, addrDiff); 1603 1604 if ((key & 0x08) != 0) { 1605 int bitCount = key >> 4; 1606 if (bitCount == 0) { 1607 /* nothing changed, no additional output required */ 1608 } else if (bitCount == 15) { 1609 /* full vector is most compact representation */ 1610 memcpy(tmpPtr, mapData, regWidth); 1611 tmpPtr += regWidth; 1612 } else { 1613 /* write bit indices in LEB128 format */ 1614 (void) computeBitDiff(prevBits, mapData, regWidth, 1615 NULL, NULL, tmpPtr); 1616 tmpPtr += lebSize; 1617 } 1618 } else { 1619 /* single-bit changed, value encoded in key byte */ 1620 } 1621 1622 prevBits = mapData; 1623 prevAddr = addr; 1624 mapData += regWidth; 1625 1626 /* 1627 * See if we've run past the original size. 1628 */ 1629 if (tmpPtr - tmpBuf >= origSize) { 1630 if (debug) { 1631 LOGD("Compressed size >= original (%d vs %d): %s.%s\n", 1632 tmpPtr - tmpBuf, origSize, 1633 meth->clazz->descriptor, meth->name); 1634 } 1635 goto bail; 1636 } 1637 } 1638 1639 /* 1640 * Create a RegisterMap with the contents. 1641 * 1642 * TODO: consider using a threshold other than merely ">=". We would 1643 * get poorer compression but potentially use less native heap space. 1644 */ 1645 static const int kHeaderSize = offsetof(RegisterMap, data); 1646 int newDataSize = tmpPtr - tmpBuf; 1647 int newMapSize; 1648 1649 newMapSize = kHeaderSize + unsignedLeb128Size(newDataSize) + newDataSize; 1650 if (newMapSize >= origSize) { 1651 if (debug) { 1652 LOGD("Final comp size >= original (%d vs %d): %s.%s\n", 1653 newMapSize, origSize, meth->clazz->descriptor, meth->name); 1654 } 1655 goto bail; 1656 } 1657 1658 pNewMap = (RegisterMap*) malloc(newMapSize); 1659 if (pNewMap == NULL) 1660 goto bail; 1661 dvmRegisterMapSetFormat(pNewMap, kRegMapFormatDifferential); 1662 dvmRegisterMapSetOnHeap(pNewMap, true); 1663 dvmRegisterMapSetRegWidth(pNewMap, regWidth); 1664 dvmRegisterMapSetNumEntries(pNewMap, numEntries); 1665 1666 tmpPtr = pNewMap->data; 1667 tmpPtr = writeUnsignedLeb128(tmpPtr, newDataSize); 1668 memcpy(tmpPtr, tmpBuf, newDataSize); 1669 1670 if (REGISTER_MAP_VERBOSE) { 1671 LOGD("Compression successful (%d -> %d) from aw=%d rw=%d ne=%d\n", 1672 computeRegisterMapSize(pMap), computeRegisterMapSize(pNewMap), 1673 addrWidth, regWidth, numEntries); 1674 } 1675 1676 bail: 1677 free(tmpBuf); 1678 return pNewMap; 1679 } 1680 1681 /* 1682 * Toggle the value of the "idx"th bit in "ptr". 1683 */ 1684 static inline void toggleBit(u1* ptr, int idx) 1685 { 1686 ptr[idx >> 3] ^= 1 << (idx & 0x07); 1687 } 1688 1689 /* 1690 * Expand a compressed map to an uncompressed form. 1691 * 1692 * Returns a newly-allocated RegisterMap on success, or NULL on failure. 1693 * 1694 * TODO: consider using the linear allocator or a custom allocator with 1695 * LRU replacement for these instead of the native heap. 1696 */ 1697 static RegisterMap* uncompressMapDifferential(const RegisterMap* pMap) 1698 { 1699 RegisterMap* pNewMap = NULL; 1700 static const int kHeaderSize = offsetof(RegisterMap, data); 1701 u1 format = dvmRegisterMapGetFormat(pMap); 1702 RegisterMapFormat newFormat; 1703 int regWidth, numEntries, newAddrWidth, newMapSize; 1704 1705 if (format != kRegMapFormatDifferential) { 1706 LOGE("Not differential (%d)\n", format); 1707 goto bail; 1708 } 1709 1710 regWidth = dvmRegisterMapGetRegWidth(pMap); 1711 numEntries = dvmRegisterMapGetNumEntries(pMap); 1712 1713 /* get the data size; we can check this at the end */ 1714 const u1* srcPtr = pMap->data; 1715 int expectedSrcLen = readUnsignedLeb128(&srcPtr); 1716 const u1* srcStart = srcPtr; 1717 1718 /* get the initial address and the 16-bit address flag */ 1719 int addr = *srcPtr & 0x7f; 1720 if ((*srcPtr & 0x80) == 0) { 1721 newFormat = kRegMapFormatCompact8; 1722 newAddrWidth = 1; 1723 } else { 1724 newFormat = kRegMapFormatCompact16; 1725 newAddrWidth = 2; 1726 } 1727 srcPtr++; 1728 1729 /* now we know enough to allocate the new map */ 1730 if (REGISTER_MAP_VERBOSE) { 1731 LOGI("Expanding to map aw=%d rw=%d ne=%d\n", 1732 newAddrWidth, regWidth, numEntries); 1733 } 1734 newMapSize = kHeaderSize + (newAddrWidth + regWidth) * numEntries; 1735 pNewMap = (RegisterMap*) malloc(newMapSize); 1736 if (pNewMap == NULL) 1737 goto bail; 1738 1739 dvmRegisterMapSetFormat(pNewMap, newFormat); 1740 dvmRegisterMapSetOnHeap(pNewMap, true); 1741 dvmRegisterMapSetRegWidth(pNewMap, regWidth); 1742 dvmRegisterMapSetNumEntries(pNewMap, numEntries); 1743 1744 /* 1745 * Write the start address and initial bits to the new map. 1746 */ 1747 u1* dstPtr = pNewMap->data; 1748 1749 *dstPtr++ = addr & 0xff; 1750 if (newAddrWidth > 1) 1751 *dstPtr++ = (u1) (addr >> 8); 1752 1753 memcpy(dstPtr, srcPtr, regWidth); 1754 1755 int prevAddr = addr; 1756 const u1* prevBits = dstPtr; /* point at uncompressed data */ 1757 1758 dstPtr += regWidth; 1759 srcPtr += regWidth; 1760 1761 /* 1762 * Walk through, uncompressing one line at a time. 1763 */ 1764 int entry; 1765 for (entry = 1; entry < numEntries; entry++) { 1766 int addrDiff; 1767 u1 key; 1768 1769 key = *srcPtr++; 1770 1771 /* get the address */ 1772 if ((key & 0x07) == 7) { 1773 /* address diff follows in ULEB128 */ 1774 addrDiff = readUnsignedLeb128(&srcPtr); 1775 } else { 1776 addrDiff = (key & 0x07) +1; 1777 } 1778 1779 addr = prevAddr + addrDiff; 1780 *dstPtr++ = addr & 0xff; 1781 if (newAddrWidth > 1) 1782 *dstPtr++ = (u1) (addr >> 8); 1783 1784 /* unpack the bits */ 1785 if ((key & 0x08) != 0) { 1786 int bitCount = (key >> 4); 1787 if (bitCount == 0) { 1788 /* no bits changed, just copy previous */ 1789 memcpy(dstPtr, prevBits, regWidth); 1790 } else if (bitCount == 15) { 1791 /* full copy of bit vector is present; ignore prevBits */ 1792 memcpy(dstPtr, srcPtr, regWidth); 1793 srcPtr += regWidth; 1794 } else { 1795 /* copy previous bits and modify listed indices */ 1796 memcpy(dstPtr, prevBits, regWidth); 1797 while (bitCount--) { 1798 int bitIndex = readUnsignedLeb128(&srcPtr); 1799 toggleBit(dstPtr, bitIndex); 1800 } 1801 } 1802 } else { 1803 /* copy previous bits and modify the specified one */ 1804 memcpy(dstPtr, prevBits, regWidth); 1805 1806 /* one bit, from 0-15 inclusive, was changed */ 1807 toggleBit(dstPtr, key >> 4); 1808 } 1809 1810 prevAddr = addr; 1811 prevBits = dstPtr; 1812 dstPtr += regWidth; 1813 } 1814 1815 if (dstPtr - (u1*) pNewMap != newMapSize) { 1816 LOGE("ERROR: output %d bytes, expected %d\n", 1817 dstPtr - (u1*) pNewMap, newMapSize); 1818 goto bail; 1819 } 1820 1821 if (srcPtr - srcStart != expectedSrcLen) { 1822 LOGE("ERROR: consumed %d bytes, expected %d\n", 1823 srcPtr - srcStart, expectedSrcLen); 1824 goto bail; 1825 } 1826 1827 if (REGISTER_MAP_VERBOSE) { 1828 LOGD("Expansion successful (%d -> %d)\n", 1829 computeRegisterMapSize(pMap), computeRegisterMapSize(pNewMap)); 1830 } 1831 1832 return pNewMap; 1833 1834 bail: 1835 free(pNewMap); 1836 return NULL; 1837 } 1838 1839 1840 /* 1841 * =========================================================================== 1842 * Just-in-time generation 1843 * =========================================================================== 1844 */ 1845 1846 #if 0 /* incomplete implementation; may be removed entirely in the future */ 1847 1848 /* 1849 Notes on just-in-time RegisterMap generation 1850 1851 Generating RegisterMap tables as part of verification is convenient because 1852 we generate most of what we need to know as part of doing the verify. 1853 The negative aspect of doing it this way is that we must store the 1854 result in the DEX file (if we're verifying ahead of time) or in memory 1855 (if verifying during class load) for every concrete non-native method, 1856 even if we never actually need the map during a GC. 1857 1858 A simple but compact encoding of register map data increases the size of 1859 optimized DEX files by about 25%, so size considerations are important. 1860 1861 We can instead generate the RegisterMap at the point where it is needed. 1862 In a typical application we only need to convert about 2% of the loaded 1863 methods, and we can generate type-precise roots reasonably quickly because 1864 (a) we know the method has already been verified and hence can make a 1865 lot of assumptions, and (b) we don't care what type of object a register 1866 holds, just whether or not it holds a reference, and hence can skip a 1867 lot of class resolution gymnastics. 1868 1869 There are a couple of problems with this approach however. First, to 1870 get good performance we really want an implementation that is largely 1871 independent from the verifier, which means some duplication of effort. 1872 Second, we're dealing with post-dexopt code, which contains "quickened" 1873 instructions. We can't process those without either tracking type 1874 information (which slows us down) or storing additional data in the DEX 1875 file that allows us to reconstruct the original instructions (adds ~5% 1876 to the size of the ODEX). 1877 1878 1879 Implementation notes... 1880 1881 Both type-precise and live-precise information can be generated knowing 1882 only whether or not a register holds a reference. We don't need to 1883 know what kind of reference or whether the object has been initialized. 1884 Not only can we skip many of the fancy steps in the verifier, we can 1885 initialize from simpler sources, e.g. the initial registers and return 1886 type are set from the "shorty" signature rather than the full signature. 1887 1888 The short-term storage needs for just-in-time register map generation can 1889 be much lower because we can use a 1-byte SRegType instead of a 4-byte 1890 RegType. On the other hand, if we're not doing type-precise analysis 1891 in the verifier we only need to store register contents at every branch 1892 target, rather than every GC point (which are much more frequent). 1893 1894 Whether it happens in the verifier or independently, because this is done 1895 with native heap allocations that may be difficult to return to the system, 1896 an effort should be made to minimize memory use. 1897 */ 1898 1899 /* 1900 * This is like RegType in the verifier, but simplified. It holds a value 1901 * from the reg type enum, or kRegTypeReference. 1902 */ 1903 typedef u1 SRegType; 1904 #define kRegTypeReference kRegTypeMAX 1905 1906 /* 1907 * We need an extra "pseudo register" to hold the return type briefly. It 1908 * can be category 1 or 2, so we need two slots. 1909 */ 1910 #define kExtraRegs 2 1911 #define RESULT_REGISTER(_insnRegCountPlus) (_insnRegCountPlus - kExtraRegs) 1912 1913 /* 1914 * Working state. 1915 */ 1916 typedef struct WorkState { 1917 /* 1918 * The method we're working on. 1919 */ 1920 const Method* method; 1921 1922 /* 1923 * Number of instructions in the method. 1924 */ 1925 int insnsSize; 1926 1927 /* 1928 * Number of registers we track for each instruction. This is equal 1929 * to the method's declared "registersSize" plus kExtraRegs. 1930 */ 1931 int insnRegCountPlus; 1932 1933 /* 1934 * Instruction widths and flags, one entry per code unit. 1935 */ 1936 InsnFlags* insnFlags; 1937 1938 /* 1939 * Array of SRegType arrays, one entry per code unit. We only need 1940 * to create an entry when an instruction starts at this address. 1941 * We can further reduce this to instructions that are GC points. 1942 * 1943 * We could just go ahead and allocate one per code unit, but for 1944 * larger methods that can represent a significant bit of short-term 1945 * storage. 1946 */ 1947 SRegType** addrRegs; 1948 1949 /* 1950 * A single large alloc, with all of the storage needed for addrRegs. 1951 */ 1952 SRegType* regAlloc; 1953 } WorkState; 1954 1955 // fwd 1956 static bool generateMap(WorkState* pState, RegisterMap* pMap); 1957 static bool analyzeMethod(WorkState* pState); 1958 static bool handleInstruction(WorkState* pState, SRegType* workRegs,\ 1959 int insnIdx, int* pStartGuess); 1960 static void updateRegisters(WorkState* pState, int nextInsn,\ 1961 const SRegType* workRegs); 1962 1963 1964 /* 1965 * Set instruction flags. 1966 */ 1967 static bool setInsnFlags(WorkState* pState, int* pGcPointCount) 1968 { 1969 const Method* meth = pState->method; 1970 InsnFlags* insnFlags = pState->insnFlags; 1971 int insnsSize = pState->insnsSize; 1972 const u2* insns = meth->insns; 1973 int gcPointCount = 0; 1974 int offset; 1975 1976 /* set the widths */ 1977 if (!dvmComputeCodeWidths(meth, pState->insnFlags, NULL)) 1978 return false; 1979 1980 /* mark "try" regions and exception handler branch targets */ 1981 if (!dvmSetTryFlags(meth, pState->insnFlags)) 1982 return false; 1983 1984 /* the start of the method is a "branch target" */ 1985 dvmInsnSetBranchTarget(insnFlags, 0, true); 1986 1987 /* 1988 * Run through the instructions, looking for switches and branches. 1989 * Mark their targets. 1990 * 1991 * We don't really need to "check" these instructions -- the verifier 1992 * already did that -- but the additional overhead isn't significant 1993 * enough to warrant making a second copy of the "Check" function. 1994 * 1995 * Mark and count GC points while we're at it. 1996 */ 1997 for (offset = 0; offset < insnsSize; offset++) { 1998 static int gcMask = kInstrCanBranch | kInstrCanSwitch | 1999 kInstrCanThrow | kInstrCanReturn; 2000 u1 opcode = insns[offset] & 0xff; 2001 InstructionFlags opFlags = dexGetInstrFlags(gDvm.instrFlags, opcode); 2002 2003 if (opFlags & kInstrCanBranch) { 2004 if (!dvmCheckBranchTarget(meth, insnFlags, offset, true)) 2005 return false; 2006 } 2007 if (opFlags & kInstrCanSwitch) { 2008 if (!dvmCheckSwitchTargets(meth, insnFlags, offset)) 2009 return false; 2010 } 2011 2012 if ((opFlags & gcMask) != 0) { 2013 dvmInsnSetGcPoint(pState->insnFlags, offset, true); 2014 gcPointCount++; 2015 } 2016 } 2017 2018 *pGcPointCount = gcPointCount; 2019 return true; 2020 } 2021 2022 /* 2023 * Generate the register map for a method. 2024 * 2025 * Returns a pointer to newly-allocated storage. 2026 */ 2027 RegisterMap* dvmGenerateRegisterMap(const Method* meth) 2028 { 2029 WorkState* pState = NULL; 2030 RegisterMap* pMap = NULL; 2031 RegisterMap* result = NULL; 2032 SRegType* regPtr; 2033 2034 pState = (WorkState*) calloc(1, sizeof(WorkState)); 2035 if (pState == NULL) 2036 goto bail; 2037 2038 pMap = (RegisterMap*) calloc(1, sizeof(RegisterMap)); 2039 if (pMap == NULL) 2040 goto bail; 2041 2042 pState->method = meth; 2043 pState->insnsSize = dvmGetMethodInsnsSize(meth); 2044 pState->insnRegCountPlus = meth->registersSize + kExtraRegs; 2045 2046 pState->insnFlags = calloc(sizeof(InsnFlags), pState->insnsSize); 2047 pState->addrRegs = calloc(sizeof(SRegType*), pState->insnsSize); 2048 2049 /* 2050 * Set flags on instructions, and calculate the number of code units 2051 * that happen to be GC points. 2052 */ 2053 int gcPointCount; 2054 if (!setInsnFlags(pState, &gcPointCount)) 2055 goto bail; 2056 2057 if (gcPointCount == 0) { 2058 /* the method doesn't allocate or call, and never returns? unlikely */ 2059 LOG_VFY_METH(meth, "Found do-nothing method\n"); 2060 goto bail; 2061 } 2062 2063 pState->regAlloc = (SRegType*) 2064 calloc(sizeof(SRegType), pState->insnsSize * gcPointCount); 2065 regPtr = pState->regAlloc; 2066 2067 /* 2068 * For each instruction that is a GC point, set a pointer into the 2069 * regAlloc buffer. 2070 */ 2071 int offset; 2072 for (offset = 0; offset < pState->insnsSize; offset++) { 2073 if (dvmInsnIsGcPoint(pState->insnFlags, offset)) { 2074 pState->addrRegs[offset] = regPtr; 2075 regPtr += pState->insnRegCountPlus; 2076 } 2077 } 2078 assert(regPtr - pState->regAlloc == pState->insnsSize * gcPointCount); 2079 assert(pState->addrRegs[0] != NULL); 2080 2081 /* 2082 * Compute the register map. 2083 */ 2084 if (!generateMap(pState, pMap)) 2085 goto bail; 2086 2087 /* success */ 2088 result = pMap; 2089 pMap = NULL; 2090 2091 bail: 2092 if (pState != NULL) { 2093 free(pState->insnFlags); 2094 free(pState->addrRegs); 2095 free(pState->regAlloc); 2096 free(pState); 2097 } 2098 if (pMap != NULL) 2099 dvmFreeRegisterMap(pMap); 2100 return result; 2101 } 2102 2103 /* 2104 * Release the storage associated with a RegisterMap. 2105 */ 2106 void dvmFreeRegisterMap(RegisterMap* pMap) 2107 { 2108 if (pMap == NULL) 2109 return; 2110 } 2111 2112 2113 /* 2114 * Create the RegisterMap using the provided state. 2115 */ 2116 static bool generateMap(WorkState* pState, RegisterMap* pMap) 2117 { 2118 bool result = false; 2119 2120 /* 2121 * Analyze the method and store the results in WorkState. 2122 */ 2123 if (!analyzeMethod(pState)) 2124 goto bail; 2125 2126 /* 2127 * Convert the analyzed data into a RegisterMap. 2128 */ 2129 // TODO 2130 2131 result = true; 2132 2133 bail: 2134 return result; 2135 } 2136 2137 /* 2138 * Set the register types for the method arguments. We can pull the values 2139 * out of the "shorty" signature. 2140 */ 2141 static bool setTypesFromSignature(WorkState* pState) 2142 { 2143 const Method* meth = pState->method; 2144 int argReg = meth->registersSize - meth->insSize; /* first arg */ 2145 SRegType* pRegs = pState->addrRegs[0]; 2146 SRegType* pCurReg = &pRegs[argReg]; 2147 const char* ccp; 2148 2149 /* 2150 * Include "this" pointer, if appropriate. 2151 */ 2152 if (!dvmIsStaticMethod(meth)) { 2153 *pCurReg++ = kRegTypeReference; 2154 } 2155 2156 ccp = meth->shorty +1; /* skip first byte, which holds return type */ 2157 while (*ccp != 0) { 2158 switch (*ccp) { 2159 case 'L': 2160 //case '[': 2161 *pCurReg++ = kRegTypeReference; 2162 break; 2163 case 'Z': 2164 *pCurReg++ = kRegTypeBoolean; 2165 break; 2166 case 'C': 2167 *pCurReg++ = kRegTypeChar; 2168 break; 2169 case 'B': 2170 *pCurReg++ = kRegTypeByte; 2171 break; 2172 case 'I': 2173 *pCurReg++ = kRegTypeInteger; 2174 break; 2175 case 'S': 2176 *pCurReg++ = kRegTypeShort; 2177 break; 2178 case 'F': 2179 *pCurReg++ = kRegTypeFloat; 2180 break; 2181 case 'D': 2182 *pCurReg++ = kRegTypeDoubleLo; 2183 *pCurReg++ = kRegTypeDoubleHi; 2184 break; 2185 case 'J': 2186 *pCurReg++ = kRegTypeLongLo; 2187 *pCurReg++ = kRegTypeLongHi; 2188 break; 2189 default: 2190 assert(false); 2191 return false; 2192 } 2193 } 2194 2195 assert(pCurReg - pRegs == meth->insSize); 2196 return true; 2197 } 2198 2199 /* 2200 * Find the start of the register set for the specified instruction in 2201 * the current method. 2202 */ 2203 static inline SRegType* getRegisterLine(const WorkState* pState, int insnIdx) 2204 { 2205 return pState->addrRegs[insnIdx]; 2206 } 2207 2208 /* 2209 * Copy a set of registers. 2210 */ 2211 static inline void copyRegisters(SRegType* dst, const SRegType* src, 2212 int numRegs) 2213 { 2214 memcpy(dst, src, numRegs * sizeof(SRegType)); 2215 } 2216 2217 /* 2218 * Compare a set of registers. Returns 0 if they match. 2219 */ 2220 static inline int compareRegisters(const SRegType* src1, const SRegType* src2, 2221 int numRegs) 2222 { 2223 return memcmp(src1, src2, numRegs * sizeof(SRegType)); 2224 } 2225 2226 /* 2227 * Run through the instructions repeatedly until we have exercised all 2228 * possible paths. 2229 */ 2230 static bool analyzeMethod(WorkState* pState) 2231 { 2232 const Method* meth = pState->method; 2233 SRegType workRegs[pState->insnRegCountPlus]; 2234 InsnFlags* insnFlags = pState->insnFlags; 2235 int insnsSize = pState->insnsSize; 2236 int insnIdx, startGuess; 2237 bool result = false; 2238 2239 /* 2240 * Initialize the types of the registers that correspond to method 2241 * arguments. 2242 */ 2243 if (!setTypesFromSignature(pState)) 2244 goto bail; 2245 2246 /* 2247 * Mark the first instruction as "changed". 2248 */ 2249 dvmInsnSetChanged(insnFlags, 0, true); 2250 startGuess = 0; 2251 2252 if (true) { 2253 IF_LOGI() { 2254 char* desc = dexProtoCopyMethodDescriptor(&meth->prototype); 2255 LOGI("Now mapping: %s.%s %s (ins=%d regs=%d)\n", 2256 meth->clazz->descriptor, meth->name, desc, 2257 meth->insSize, meth->registersSize); 2258 LOGI(" ------ [0 4 8 12 16 20 24 28 32 36\n"); 2259 free(desc); 2260 } 2261 } 2262 2263 /* 2264 * Continue until no instructions are marked "changed". 2265 */ 2266 while (true) { 2267 /* 2268 * Find the first marked one. Use "startGuess" as a way to find 2269 * one quickly. 2270 */ 2271 for (insnIdx = startGuess; insnIdx < insnsSize; insnIdx++) { 2272 if (dvmInsnIsChanged(insnFlags, insnIdx)) 2273 break; 2274 } 2275 2276 if (insnIdx == insnsSize) { 2277 if (startGuess != 0) { 2278 /* try again, starting from the top */ 2279 startGuess = 0; 2280 continue; 2281 } else { 2282 /* all flags are clear */ 2283 break; 2284 } 2285 } 2286 2287 /* 2288 * We carry the working set of registers from instruction to 2289 * instruction. If this address can be the target of a branch 2290 * (or throw) instruction, or if we're skipping around chasing 2291 * "changed" flags, we need to load the set of registers from 2292 * the table. 2293 * 2294 * Because we always prefer to continue on to the next instruction, 2295 * we should never have a situation where we have a stray 2296 * "changed" flag set on an instruction that isn't a branch target. 2297 */ 2298 if (dvmInsnIsBranchTarget(insnFlags, insnIdx)) { 2299 SRegType* insnRegs = getRegisterLine(pState, insnIdx); 2300 assert(insnRegs != NULL); 2301 copyRegisters(workRegs, insnRegs, pState->insnRegCountPlus); 2302 2303 } else { 2304 #ifndef NDEBUG 2305 /* 2306 * Sanity check: retrieve the stored register line (assuming 2307 * a full table) and make sure it actually matches. 2308 */ 2309 SRegType* insnRegs = getRegisterLine(pState, insnIdx); 2310 if (insnRegs != NULL && 2311 compareRegisters(workRegs, insnRegs, 2312 pState->insnRegCountPlus) != 0) 2313 { 2314 char* desc = dexProtoCopyMethodDescriptor(&meth->prototype); 2315 LOG_VFY("HUH? workRegs diverged in %s.%s %s\n", 2316 meth->clazz->descriptor, meth->name, desc); 2317 free(desc); 2318 } 2319 #endif 2320 } 2321 2322 /* 2323 * Update the register sets altered by this instruction. 2324 */ 2325 if (!handleInstruction(pState, workRegs, insnIdx, &startGuess)) { 2326 goto bail; 2327 } 2328 2329 dvmInsnSetVisited(insnFlags, insnIdx, true); 2330 dvmInsnSetChanged(insnFlags, insnIdx, false); 2331 } 2332 2333 // TODO - add dead code scan to help validate this code? 2334 2335 result = true; 2336 2337 bail: 2338 return result; 2339 } 2340 2341 /* 2342 * Get a pointer to the method being invoked. 2343 * 2344 * Returns NULL on failure. 2345 */ 2346 static Method* getInvokedMethod(const Method* meth, 2347 const DecodedInstruction* pDecInsn, MethodType methodType) 2348 { 2349 Method* resMethod; 2350 char* sigOriginal = NULL; 2351 2352 /* 2353 * Resolve the method. This could be an abstract or concrete method 2354 * depending on what sort of call we're making. 2355 */ 2356 if (methodType == METHOD_INTERFACE) { 2357 resMethod = dvmOptResolveInterfaceMethod(meth->clazz, pDecInsn->vB); 2358 } else { 2359 resMethod = dvmOptResolveMethod(meth->clazz, pDecInsn->vB, methodType); 2360 } 2361 if (resMethod == NULL) { 2362 /* failed; print a meaningful failure message */ 2363 DexFile* pDexFile = meth->clazz->pDvmDex->pDexFile; 2364 const DexMethodId* pMethodId; 2365 const char* methodName; 2366 char* methodDesc; 2367 const char* classDescriptor; 2368 2369 pMethodId = dexGetMethodId(pDexFile, pDecInsn->vB); 2370 methodName = dexStringById(pDexFile, pMethodId->nameIdx); 2371 methodDesc = dexCopyDescriptorFromMethodId(pDexFile, pMethodId); 2372 classDescriptor = dexStringByTypeIdx(pDexFile, pMethodId->classIdx); 2373 2374 LOG_VFY("VFY: unable to resolve %s method %u: %s.%s %s\n", 2375 dvmMethodTypeStr(methodType), pDecInsn->vB, 2376 classDescriptor, methodName, methodDesc); 2377 free(methodDesc); 2378 return NULL; 2379 } 2380 2381 return resMethod; 2382 } 2383 2384 /* 2385 * Return the register type for the method. Since we don't care about 2386 * the actual type, we can just look at the "shorty" signature. 2387 * 2388 * Returns kRegTypeUnknown for "void". 2389 */ 2390 static SRegType getMethodReturnType(const Method* meth) 2391 { 2392 SRegType type; 2393 2394 switch (meth->shorty[0]) { 2395 case 'I': 2396 type = kRegTypeInteger; 2397 break; 2398 case 'C': 2399 type = kRegTypeChar; 2400 break; 2401 case 'S': 2402 type = kRegTypeShort; 2403 break; 2404 case 'B': 2405 type = kRegTypeByte; 2406 break; 2407 case 'Z': 2408 type = kRegTypeBoolean; 2409 break; 2410 case 'V': 2411 type = kRegTypeUnknown; 2412 break; 2413 case 'F': 2414 type = kRegTypeFloat; 2415 break; 2416 case 'D': 2417 type = kRegTypeDoubleLo; 2418 break; 2419 case 'J': 2420 type = kRegTypeLongLo; 2421 break; 2422 case 'L': 2423 //case '[': 2424 type = kRegTypeReference; 2425 break; 2426 default: 2427 /* we verified signature return type earlier, so this is impossible */ 2428 assert(false); 2429 type = kRegTypeConflict; 2430 break; 2431 } 2432 2433 return type; 2434 } 2435 2436 /* 2437 * Copy a category 1 register. 2438 */ 2439 static inline void copyRegister1(SRegType* insnRegs, u4 vdst, u4 vsrc) 2440 { 2441 insnRegs[vdst] = insnRegs[vsrc]; 2442 } 2443 2444 /* 2445 * Copy a category 2 register. Note the source and destination may overlap. 2446 */ 2447 static inline void copyRegister2(SRegType* insnRegs, u4 vdst, u4 vsrc) 2448 { 2449 //memmove(&insnRegs[vdst], &insnRegs[vsrc], sizeof(SRegType) * 2); 2450 SRegType r1 = insnRegs[vsrc]; 2451 SRegType r2 = insnRegs[vsrc+1]; 2452 insnRegs[vdst] = r1; 2453 insnRegs[vdst+1] = r2; 2454 } 2455 2456 /* 2457 * Set the type of a category 1 register. 2458 */ 2459 static inline void setRegisterType(SRegType* insnRegs, u4 vdst, SRegType type) 2460 { 2461 insnRegs[vdst] = type; 2462 } 2463 2464 /* 2465 * Decode the specified instruction and update the register info. 2466 */ 2467 static bool handleInstruction(WorkState* pState, SRegType* workRegs, 2468 int insnIdx, int* pStartGuess) 2469 { 2470 const Method* meth = pState->method; 2471 const u2* insns = meth->insns + insnIdx; 2472 InsnFlags* insnFlags = pState->insnFlags; 2473 bool result = false; 2474 2475 /* 2476 * Once we finish decoding the instruction, we need to figure out where 2477 * we can go from here. There are three possible ways to transfer 2478 * control to another statement: 2479 * 2480 * (1) Continue to the next instruction. Applies to all but 2481 * unconditional branches, method returns, and exception throws. 2482 * (2) Branch to one or more possible locations. Applies to branches 2483 * and switch statements. 2484 * (3) Exception handlers. Applies to any instruction that can 2485 * throw an exception that is handled by an encompassing "try" 2486 * block. (We simplify this to be any instruction that can 2487 * throw any exception.) 2488 * 2489 * We can also return, in which case there is no successor instruction 2490 * from this point. 2491 * 2492 * The behavior can be determined from the InstrFlags. 2493 */ 2494 DecodedInstruction decInsn; 2495 SRegType entryRegs[pState->insnRegCountPlus]; 2496 const int insnRegCountPlus = pState->insnRegCountPlus; 2497 bool justSetResult = false; 2498 int branchTarget = 0; 2499 SRegType tmpType; 2500 2501 dexDecodeInstruction(gDvm.instrFormat, insns, &decInsn); 2502 const int nextFlags = dexGetInstrFlags(gDvm.instrFlags, decInsn.opCode); 2503 2504 /* 2505 * Make a copy of the previous register state. If the instruction 2506 * throws an exception, we merge *this* into the destination rather 2507 * than workRegs, because we don't want the result from the "successful" 2508 * code path (e.g. a check-cast that "improves" a type) to be visible 2509 * to the exception handler. 2510 */ 2511 if ((nextFlags & kInstrCanThrow) != 0 && dvmInsnIsInTry(insnFlags, insnIdx)) 2512 { 2513 copyRegisters(entryRegs, workRegs, insnRegCountPlus); 2514 } 2515 2516 switch (decInsn.opCode) { 2517 case OP_NOP: 2518 break; 2519 2520 case OP_MOVE: 2521 case OP_MOVE_FROM16: 2522 case OP_MOVE_16: 2523 case OP_MOVE_OBJECT: 2524 case OP_MOVE_OBJECT_FROM16: 2525 case OP_MOVE_OBJECT_16: 2526 copyRegister1(workRegs, decInsn.vA, decInsn.vB); 2527 break; 2528 case OP_MOVE_WIDE: 2529 case OP_MOVE_WIDE_FROM16: 2530 case OP_MOVE_WIDE_16: 2531 copyRegister2(workRegs, decInsn.vA, decInsn.vB); 2532 break; 2533 2534 /* 2535 * The move-result instructions copy data out of a "pseudo-register" 2536 * with the results from the last method invocation. In practice we 2537 * might want to hold the result in an actual CPU register, so the 2538 * Dalvik spec requires that these only appear immediately after an 2539 * invoke or filled-new-array. 2540 * 2541 * These calls invalidate the "result" register. (This is now 2542 * redundant with the reset done below, but it can make the debug info 2543 * easier to read in some cases.) 2544 */ 2545 case OP_MOVE_RESULT: 2546 case OP_MOVE_RESULT_OBJECT: 2547 copyRegister1(workRegs, decInsn.vA, RESULT_REGISTER(insnRegCountPlus)); 2548 break; 2549 case OP_MOVE_RESULT_WIDE: 2550 copyRegister2(workRegs, decInsn.vA, RESULT_REGISTER(insnRegCountPlus)); 2551 break; 2552 2553 case OP_MOVE_EXCEPTION: 2554 /* 2555 * This statement can only appear as the first instruction in an 2556 * exception handler (though not all exception handlers need to 2557 * have one of these). We verify that as part of extracting the 2558 * exception type from the catch block list. 2559 */ 2560 setRegisterType(workRegs, decInsn.vA, kRegTypeReference); 2561 break; 2562 2563 case OP_RETURN_VOID: 2564 case OP_RETURN: 2565 case OP_RETURN_WIDE: 2566 case OP_RETURN_OBJECT: 2567 break; 2568 2569 case OP_CONST_4: 2570 case OP_CONST_16: 2571 case OP_CONST: 2572 /* could be boolean, int, float, or a null reference */ 2573 setRegisterType(workRegs, decInsn.vA, 2574 dvmDetermineCat1Const((s4)decInsn.vB)); 2575 break; 2576 case OP_CONST_HIGH16: 2577 /* could be boolean, int, float, or a null reference */ 2578 setRegisterType(workRegs, decInsn.vA, 2579 dvmDetermineCat1Const((s4) decInsn.vB << 16)); 2580 break; 2581 case OP_CONST_WIDE_16: 2582 case OP_CONST_WIDE_32: 2583 case OP_CONST_WIDE: 2584 case OP_CONST_WIDE_HIGH16: 2585 /* could be long or double; default to long and allow conversion */ 2586 setRegisterType(workRegs, decInsn.vA, kRegTypeLongLo); 2587 break; 2588 case OP_CONST_STRING: 2589 case OP_CONST_STRING_JUMBO: 2590 case OP_CONST_CLASS: 2591 setRegisterType(workRegs, decInsn.vA, kRegTypeReference); 2592 break; 2593 2594 case OP_MONITOR_ENTER: 2595 case OP_MONITOR_EXIT: 2596 break; 2597 2598 case OP_CHECK_CAST: 2599 setRegisterType(workRegs, decInsn.vA, kRegTypeReference); 2600 break; 2601 case OP_INSTANCE_OF: 2602 /* result is boolean */ 2603 setRegisterType(workRegs, decInsn.vA, kRegTypeBoolean); 2604 break; 2605 2606 case OP_ARRAY_LENGTH: 2607 setRegisterType(workRegs, decInsn.vA, kRegTypeInteger); 2608 break; 2609 2610 case OP_NEW_INSTANCE: 2611 case OP_NEW_ARRAY: 2612 /* add the new uninitialized reference to the register ste */ 2613 setRegisterType(workRegs, decInsn.vA, kRegTypeReference); 2614 break; 2615 case OP_FILLED_NEW_ARRAY: 2616 case OP_FILLED_NEW_ARRAY_RANGE: 2617 setRegisterType(workRegs, RESULT_REGISTER(insnRegCountPlus), 2618 kRegTypeReference); 2619 justSetResult = true; 2620 break; 2621 2622 case OP_CMPL_FLOAT: 2623 case OP_CMPG_FLOAT: 2624 setRegisterType(workRegs, decInsn.vA, kRegTypeBoolean); 2625 break; 2626 case OP_CMPL_DOUBLE: 2627 case OP_CMPG_DOUBLE: 2628 setRegisterType(workRegs, decInsn.vA, kRegTypeBoolean); 2629 break; 2630 case OP_CMP_LONG: 2631 setRegisterType(workRegs, decInsn.vA, kRegTypeBoolean); 2632 break; 2633 2634 case OP_THROW: 2635 case OP_GOTO: 2636 case OP_GOTO_16: 2637 case OP_GOTO_32: 2638 case OP_PACKED_SWITCH: 2639 case OP_SPARSE_SWITCH: 2640 break; 2641 2642 case OP_FILL_ARRAY_DATA: 2643 break; 2644 2645 case OP_IF_EQ: 2646 case OP_IF_NE: 2647 case OP_IF_LT: 2648 case OP_IF_GE: 2649 case OP_IF_GT: 2650 case OP_IF_LE: 2651 case OP_IF_EQZ: 2652 case OP_IF_NEZ: 2653 case OP_IF_LTZ: 2654 case OP_IF_GEZ: 2655 case OP_IF_GTZ: 2656 case OP_IF_LEZ: 2657 break; 2658 2659 case OP_AGET: 2660 tmpType = kRegTypeInteger; 2661 goto aget_1nr_common; 2662 case OP_AGET_BOOLEAN: 2663 tmpType = kRegTypeBoolean; 2664 goto aget_1nr_common; 2665 case OP_AGET_BYTE: 2666 tmpType = kRegTypeByte; 2667 goto aget_1nr_common; 2668 case OP_AGET_CHAR: 2669 tmpType = kRegTypeChar; 2670 goto aget_1nr_common; 2671 case OP_AGET_SHORT: 2672 tmpType = kRegTypeShort; 2673 goto aget_1nr_common; 2674 aget_1nr_common: 2675 setRegisterType(workRegs, decInsn.vA, tmpType); 2676 break; 2677 2678 case OP_AGET_WIDE: 2679 /* 2680 * We know this is either long or double, and we don't really 2681 * discriminate between those during verification, so we 2682 * call it a long. 2683 */ 2684 setRegisterType(workRegs, decInsn.vA, kRegTypeLongLo); 2685 break; 2686 2687 case OP_AGET_OBJECT: 2688 setRegisterType(workRegs, decInsn.vA, kRegTypeReference); 2689 break; 2690 2691 case OP_APUT: 2692 case OP_APUT_BOOLEAN: 2693 case OP_APUT_BYTE: 2694 case OP_APUT_CHAR: 2695 case OP_APUT_SHORT: 2696 case OP_APUT_WIDE: 2697 case OP_APUT_OBJECT: 2698 break; 2699 2700 case OP_IGET: 2701 tmpType = kRegTypeInteger; 2702 goto iget_1nr_common; 2703 case OP_IGET_BOOLEAN: 2704 tmpType = kRegTypeBoolean; 2705 goto iget_1nr_common; 2706 case OP_IGET_BYTE: 2707 tmpType = kRegTypeByte; 2708 goto iget_1nr_common; 2709 case OP_IGET_CHAR: 2710 tmpType = kRegTypeChar; 2711 goto iget_1nr_common; 2712 case OP_IGET_SHORT: 2713 tmpType = kRegTypeShort; 2714 goto iget_1nr_common; 2715 iget_1nr_common: 2716 setRegisterType(workRegs, decInsn.vA, tmpType); 2717 break; 2718 2719 case OP_IGET_WIDE: 2720 setRegisterType(workRegs, decInsn.vA, kRegTypeLongLo); 2721 break; 2722 2723 case OP_IGET_OBJECT: 2724 setRegisterType(workRegs, decInsn.vA, kRegTypeReference); 2725 break; 2726 2727 case OP_IPUT: 2728 case OP_IPUT_BOOLEAN: 2729 case OP_IPUT_BYTE: 2730 case OP_IPUT_CHAR: 2731 case OP_IPUT_SHORT: 2732 case OP_IPUT_WIDE: 2733 case OP_IPUT_OBJECT: 2734 break; 2735 2736 case OP_SGET: 2737 tmpType = kRegTypeInteger; 2738 goto sget_1nr_common; 2739 case OP_SGET_BOOLEAN: 2740 tmpType = kRegTypeBoolean; 2741 goto sget_1nr_common; 2742 case OP_SGET_BYTE: 2743 tmpType = kRegTypeByte; 2744 goto sget_1nr_common; 2745 case OP_SGET_CHAR: 2746 tmpType = kRegTypeChar; 2747 goto sget_1nr_common; 2748 case OP_SGET_SHORT: 2749 tmpType = kRegTypeShort; 2750 goto sget_1nr_common; 2751 sget_1nr_common: 2752 setRegisterType(workRegs, decInsn.vA, tmpType); 2753 break; 2754 2755 case OP_SGET_WIDE: 2756 setRegisterType(workRegs, decInsn.vA, kRegTypeLongLo); 2757 break; 2758 2759 case OP_SGET_OBJECT: 2760 setRegisterType(workRegs, decInsn.vA, kRegTypeReference); 2761 break; 2762 2763 case OP_SPUT: 2764 case OP_SPUT_BOOLEAN: 2765 case OP_SPUT_BYTE: 2766 case OP_SPUT_CHAR: 2767 case OP_SPUT_SHORT: 2768 case OP_SPUT_WIDE: 2769 case OP_SPUT_OBJECT: 2770 break; 2771 2772 case OP_INVOKE_VIRTUAL: 2773 case OP_INVOKE_VIRTUAL_RANGE: 2774 case OP_INVOKE_SUPER: 2775 case OP_INVOKE_SUPER_RANGE: 2776 { 2777 Method* calledMethod; 2778 2779 calledMethod = getInvokedMethod(meth, &decInsn, METHOD_VIRTUAL); 2780 if (calledMethod == NULL) 2781 goto bail; 2782 setRegisterType(workRegs, RESULT_REGISTER(insnRegCountPlus), 2783 getMethodReturnType(calledMethod)); 2784 justSetResult = true; 2785 } 2786 break; 2787 case OP_INVOKE_DIRECT: 2788 case OP_INVOKE_DIRECT_RANGE: 2789 { 2790 Method* calledMethod; 2791 2792 calledMethod = getInvokedMethod(meth, &decInsn, METHOD_DIRECT); 2793 if (calledMethod == NULL) 2794 goto bail; 2795 setRegisterType(workRegs, RESULT_REGISTER(insnRegCountPlus), 2796 getMethodReturnType(calledMethod)); 2797 justSetResult = true; 2798 } 2799 break; 2800 case OP_INVOKE_STATIC: 2801 case OP_INVOKE_STATIC_RANGE: 2802 { 2803 Method* calledMethod; 2804 2805 calledMethod = getInvokedMethod(meth, &decInsn, METHOD_STATIC); 2806 if (calledMethod == NULL) 2807 goto bail; 2808 setRegisterType(workRegs, RESULT_REGISTER(insnRegCountPlus), 2809 getMethodReturnType(calledMethod)); 2810 justSetResult = true; 2811 } 2812 break; 2813 case OP_INVOKE_INTERFACE: 2814 case OP_INVOKE_INTERFACE_RANGE: 2815 { 2816 Method* absMethod; 2817 2818 absMethod = getInvokedMethod(meth, &decInsn, METHOD_INTERFACE); 2819 if (absMethod == NULL) 2820 goto bail; 2821 setRegisterType(workRegs, RESULT_REGISTER(insnRegCountPlus), 2822 getMethodReturnType(absMethod)); 2823 justSetResult = true; 2824 } 2825 break; 2826 2827 case OP_NEG_INT: 2828 case OP_NOT_INT: 2829 setRegisterType(workRegs, decInsn.vA, kRegTypeInteger); 2830 break; 2831 case OP_NEG_LONG: 2832 case OP_NOT_LONG: 2833 setRegisterType(workRegs, decInsn.vA, kRegTypeLongLo); 2834 break; 2835 case OP_NEG_FLOAT: 2836 setRegisterType(workRegs, decInsn.vA, kRegTypeFloat); 2837 break; 2838 case OP_NEG_DOUBLE: 2839 setRegisterType(workRegs, decInsn.vA, kRegTypeDoubleLo); 2840 break; 2841 case OP_INT_TO_LONG: 2842 setRegisterType(workRegs, decInsn.vA, kRegTypeLongLo); 2843 break; 2844 case OP_INT_TO_FLOAT: 2845 setRegisterType(workRegs, decInsn.vA, kRegTypeFloat); 2846 break; 2847 case OP_INT_TO_DOUBLE: 2848 setRegisterType(workRegs, decInsn.vA, kRegTypeDoubleLo); 2849 break; 2850 case OP_LONG_TO_INT: 2851 setRegisterType(workRegs, decInsn.vA, kRegTypeInteger); 2852 break; 2853 case OP_LONG_TO_FLOAT: 2854 setRegisterType(workRegs, decInsn.vA, kRegTypeFloat); 2855 break; 2856 case OP_LONG_TO_DOUBLE: 2857 setRegisterType(workRegs, decInsn.vA, kRegTypeDoubleLo); 2858 break; 2859 case OP_FLOAT_TO_INT: 2860 setRegisterType(workRegs, decInsn.vA, kRegTypeInteger); 2861 break; 2862 case OP_FLOAT_TO_LONG: 2863 setRegisterType(workRegs, decInsn.vA, kRegTypeLongLo); 2864 break; 2865 case OP_FLOAT_TO_DOUBLE: 2866 setRegisterType(workRegs, decInsn.vA, kRegTypeDoubleLo); 2867 break; 2868 case OP_DOUBLE_TO_INT: 2869 setRegisterType(workRegs, decInsn.vA, kRegTypeInteger); 2870 break; 2871 case OP_DOUBLE_TO_LONG: 2872 setRegisterType(workRegs, decInsn.vA, kRegTypeLongLo); 2873 break; 2874 case OP_DOUBLE_TO_FLOAT: 2875 setRegisterType(workRegs, decInsn.vA, kRegTypeFloat); 2876 break; 2877 case OP_INT_TO_BYTE: 2878 setRegisterType(workRegs, decInsn.vA, kRegTypeByte); 2879 break; 2880 case OP_INT_TO_CHAR: 2881 setRegisterType(workRegs, decInsn.vA, kRegTypeChar); 2882 break; 2883 case OP_INT_TO_SHORT: 2884 setRegisterType(workRegs, decInsn.vA, kRegTypeShort); 2885 break; 2886 2887 case OP_ADD_INT: 2888 case OP_SUB_INT: 2889 case OP_MUL_INT: 2890 case OP_REM_INT: 2891 case OP_DIV_INT: 2892 case OP_SHL_INT: 2893 case OP_SHR_INT: 2894 case OP_USHR_INT: 2895 case OP_AND_INT: 2896 case OP_OR_INT: 2897 case OP_XOR_INT: 2898 setRegisterType(workRegs, decInsn.vA, kRegTypeInteger); 2899 break; 2900 case OP_ADD_LONG: 2901 case OP_SUB_LONG: 2902 case OP_MUL_LONG: 2903 case OP_DIV_LONG: 2904 case OP_REM_LONG: 2905 case OP_AND_LONG: 2906 case OP_OR_LONG: 2907 case OP_XOR_LONG: 2908 case OP_SHL_LONG: 2909 case OP_SHR_LONG: 2910 case OP_USHR_LONG: 2911 setRegisterType(workRegs, decInsn.vA, kRegTypeLongLo); 2912 break; 2913 case OP_ADD_FLOAT: 2914 case OP_SUB_FLOAT: 2915 case OP_MUL_FLOAT: 2916 case OP_DIV_FLOAT: 2917 case OP_REM_FLOAT: 2918 setRegisterType(workRegs, decInsn.vA, kRegTypeFloat); 2919 break; 2920 case OP_ADD_DOUBLE: 2921 case OP_SUB_DOUBLE: 2922 case OP_MUL_DOUBLE: 2923 case OP_DIV_DOUBLE: 2924 case OP_REM_DOUBLE: 2925 setRegisterType(workRegs, decInsn.vA, kRegTypeDoubleLo); 2926 break; 2927 case OP_ADD_INT_2ADDR: 2928 case OP_SUB_INT_2ADDR: 2929 case OP_MUL_INT_2ADDR: 2930 case OP_REM_INT_2ADDR: 2931 case OP_SHL_INT_2ADDR: 2932 case OP_SHR_INT_2ADDR: 2933 case OP_USHR_INT_2ADDR: 2934 case OP_AND_INT_2ADDR: 2935 case OP_OR_INT_2ADDR: 2936 case OP_XOR_INT_2ADDR: 2937 case OP_DIV_INT_2ADDR: 2938 setRegisterType(workRegs, decInsn.vA, kRegTypeInteger); 2939 break; 2940 case OP_ADD_LONG_2ADDR: 2941 case OP_SUB_LONG_2ADDR: 2942 case OP_MUL_LONG_2ADDR: 2943 case OP_DIV_LONG_2ADDR: 2944 case OP_REM_LONG_2ADDR: 2945 case OP_AND_LONG_2ADDR: 2946 case OP_OR_LONG_2ADDR: 2947 case OP_XOR_LONG_2ADDR: 2948 case OP_SHL_LONG_2ADDR: 2949 case OP_SHR_LONG_2ADDR: 2950 case OP_USHR_LONG_2ADDR: 2951 setRegisterType(workRegs, decInsn.vA, kRegTypeLongLo); 2952 break; 2953 case OP_ADD_FLOAT_2ADDR: 2954 case OP_SUB_FLOAT_2ADDR: 2955 case OP_MUL_FLOAT_2ADDR: 2956 case OP_DIV_FLOAT_2ADDR: 2957 case OP_REM_FLOAT_2ADDR: 2958 setRegisterType(workRegs, decInsn.vA, kRegTypeFloat); 2959 break; 2960 case OP_ADD_DOUBLE_2ADDR: 2961 case OP_SUB_DOUBLE_2ADDR: 2962 case OP_MUL_DOUBLE_2ADDR: 2963 case OP_DIV_DOUBLE_2ADDR: 2964 case OP_REM_DOUBLE_2ADDR: 2965 setRegisterType(workRegs, decInsn.vA, kRegTypeDoubleLo); 2966 break; 2967 case OP_ADD_INT_LIT16: 2968 case OP_RSUB_INT: 2969 case OP_MUL_INT_LIT16: 2970 case OP_DIV_INT_LIT16: 2971 case OP_REM_INT_LIT16: 2972 case OP_AND_INT_LIT16: 2973 case OP_OR_INT_LIT16: 2974 case OP_XOR_INT_LIT16: 2975 case OP_ADD_INT_LIT8: 2976 case OP_RSUB_INT_LIT8: 2977 case OP_MUL_INT_LIT8: 2978 case OP_DIV_INT_LIT8: 2979 case OP_REM_INT_LIT8: 2980 case OP_SHL_INT_LIT8: 2981 case OP_SHR_INT_LIT8: 2982 case OP_USHR_INT_LIT8: 2983 case OP_AND_INT_LIT8: 2984 case OP_OR_INT_LIT8: 2985 case OP_XOR_INT_LIT8: 2986 setRegisterType(workRegs, decInsn.vA, kRegTypeInteger); 2987 break; 2988 2989 2990 /* 2991 * See comments in analysis/CodeVerify.c re: why some of these are 2992 * annoying to deal with. It's worse in this implementation, because 2993 * we're not keeping any information about the classes held in each 2994 * reference register. 2995 * 2996 * Handling most of these would require retaining the field/method 2997 * reference info that we discarded when the instructions were 2998 * quickened. This is feasible but not currently supported. 2999 */ 3000 case OP_EXECUTE_INLINE: 3001 case OP_EXECUTE_INLINE_RANGE: 3002 case OP_INVOKE_DIRECT_EMPTY: 3003 case OP_IGET_QUICK: 3004 case OP_IGET_WIDE_QUICK: 3005 case OP_IGET_OBJECT_QUICK: 3006 case OP_IPUT_QUICK: 3007 case OP_IPUT_WIDE_QUICK: 3008 case OP_IPUT_OBJECT_QUICK: 3009 case OP_IGET_WIDE_VOLATILE: 3010 case OP_IPUT_WIDE_VOLATILE: 3011 case OP_SGET_WIDE_VOLATILE: 3012 case OP_SPUT_WIDE_VOLATILE: 3013 case OP_INVOKE_VIRTUAL_QUICK: 3014 case OP_INVOKE_VIRTUAL_QUICK_RANGE: 3015 case OP_INVOKE_SUPER_QUICK: 3016 case OP_INVOKE_SUPER_QUICK_RANGE: 3017 dvmAbort(); // not implemented, shouldn't be here 3018 break; 3019 3020 3021 /* these should never appear */ 3022 case OP_UNUSED_3E: 3023 case OP_UNUSED_3F: 3024 case OP_UNUSED_40: 3025 case OP_UNUSED_41: 3026 case OP_UNUSED_42: 3027 case OP_UNUSED_43: 3028 case OP_UNUSED_73: 3029 case OP_UNUSED_79: 3030 case OP_UNUSED_7A: 3031 case OP_UNUSED_E3: 3032 case OP_UNUSED_E4: 3033 case OP_UNUSED_E5: 3034 case OP_UNUSED_E6: 3035 case OP_UNUSED_E7: 3036 case OP_BREAKPOINT: 3037 case OP_UNUSED_ED: 3038 case OP_UNUSED_F1: 3039 case OP_UNUSED_FC: 3040 case OP_UNUSED_FD: 3041 case OP_UNUSED_FE: 3042 case OP_UNUSED_FF: 3043 dvmAbort(); 3044 break; 3045 3046 /* 3047 * DO NOT add a "default" clause here. Without it the compiler will 3048 * complain if an instruction is missing (which is desirable). 3049 */ 3050 } 3051 3052 3053 /* 3054 * If we didn't just set the result register, clear it out. This 3055 * isn't so important here, but does help ensure that our output matches 3056 * the verifier. 3057 */ 3058 if (!justSetResult) { 3059 int reg = RESULT_REGISTER(pState->insnRegCountPlus); 3060 workRegs[reg] = workRegs[reg+1] = kRegTypeUnknown; 3061 } 3062 3063 /* 3064 * Handle "continue". Tag the next consecutive instruction. 3065 */ 3066 if ((nextFlags & kInstrCanContinue) != 0) { 3067 int insnWidth = dvmInsnGetWidth(insnFlags, insnIdx); 3068 3069 /* 3070 * We want to update the registers and set the "changed" flag on the 3071 * next instruction (if necessary). We aren't storing register 3072 * changes for all addresses, so for non-GC-point targets we just 3073 * compare "entry" vs. "work" to see if we've changed anything. 3074 */ 3075 if (getRegisterLine(pState, insnIdx+insnWidth) != NULL) { 3076 updateRegisters(pState, insnIdx+insnWidth, workRegs); 3077 } else { 3078 /* if not yet visited, or regs were updated, set "changed" */ 3079 if (!dvmInsnIsVisited(insnFlags, insnIdx+insnWidth) || 3080 compareRegisters(workRegs, entryRegs, 3081 pState->insnRegCountPlus) != 0) 3082 { 3083 dvmInsnSetChanged(insnFlags, insnIdx+insnWidth, true); 3084 } 3085 } 3086 } 3087 3088 /* 3089 * Handle "branch". Tag the branch target. 3090 */ 3091 if ((nextFlags & kInstrCanBranch) != 0) { 3092 bool isConditional; 3093 3094 dvmGetBranchTarget(meth, insnFlags, insnIdx, &branchTarget, 3095 &isConditional); 3096 assert(isConditional || (nextFlags & kInstrCanContinue) == 0); 3097 assert(!isConditional || (nextFlags & kInstrCanContinue) != 0); 3098 3099 updateRegisters(pState, insnIdx+branchTarget, workRegs); 3100 } 3101 3102 /* 3103 * Handle "switch". Tag all possible branch targets. 3104 */ 3105 if ((nextFlags & kInstrCanSwitch) != 0) { 3106 int offsetToSwitch = insns[1] | (((s4)insns[2]) << 16); 3107 const u2* switchInsns = insns + offsetToSwitch; 3108 int switchCount = switchInsns[1]; 3109 int offsetToTargets, targ; 3110 3111 if ((*insns & 0xff) == OP_PACKED_SWITCH) { 3112 /* 0=sig, 1=count, 2/3=firstKey */ 3113 offsetToTargets = 4; 3114 } else { 3115 /* 0=sig, 1=count, 2..count*2 = keys */ 3116 assert((*insns & 0xff) == OP_SPARSE_SWITCH); 3117 offsetToTargets = 2 + 2*switchCount; 3118 } 3119 3120 /* verify each switch target */ 3121 for (targ = 0; targ < switchCount; targ++) { 3122 int offset, absOffset; 3123 3124 /* offsets are 32-bit, and only partly endian-swapped */ 3125 offset = switchInsns[offsetToTargets + targ*2] | 3126 (((s4) switchInsns[offsetToTargets + targ*2 +1]) << 16); 3127 absOffset = insnIdx + offset; 3128 assert(absOffset >= 0 && absOffset < pState->insnsSize); 3129 3130 updateRegisters(pState, absOffset, workRegs); 3131 } 3132 } 3133 3134 /* 3135 * Handle instructions that can throw and that are sitting in a 3136 * "try" block. (If they're not in a "try" block when they throw, 3137 * control transfers out of the method.) 3138 */ 3139 if ((nextFlags & kInstrCanThrow) != 0 && dvmInsnIsInTry(insnFlags, insnIdx)) 3140 { 3141 DexFile* pDexFile = meth->clazz->pDvmDex->pDexFile; 3142 const DexCode* pCode = dvmGetMethodCode(meth); 3143 DexCatchIterator iterator; 3144 3145 if (dexFindCatchHandler(&iterator, pCode, insnIdx)) { 3146 while (true) { 3147 DexCatchHandler* handler = dexCatchIteratorNext(&iterator); 3148 if (handler == NULL) 3149 break; 3150 3151 /* note we use entryRegs, not workRegs */ 3152 updateRegisters(pState, handler->address, entryRegs); 3153 } 3154 } 3155 } 3156 3157 /* 3158 * Update startGuess. Advance to the next instruction of that's 3159 * possible, otherwise use the branch target if one was found. If 3160 * neither of those exists we're in a return or throw; leave startGuess 3161 * alone and let the caller sort it out. 3162 */ 3163 if ((nextFlags & kInstrCanContinue) != 0) { 3164 *pStartGuess = insnIdx + dvmInsnGetWidth(insnFlags, insnIdx); 3165 } else if ((nextFlags & kInstrCanBranch) != 0) { 3166 /* we're still okay if branchTarget is zero */ 3167 *pStartGuess = insnIdx + branchTarget; 3168 } 3169 3170 assert(*pStartGuess >= 0 && *pStartGuess < pState->insnsSize && 3171 dvmInsnGetWidth(insnFlags, *pStartGuess) != 0); 3172 3173 result = true; 3174 3175 bail: 3176 return result; 3177 } 3178 3179 3180 /* 3181 * Merge two SRegType values. 3182 * 3183 * Sets "*pChanged" to "true" if the result doesn't match "type1". 3184 */ 3185 static SRegType mergeTypes(SRegType type1, SRegType type2, bool* pChanged) 3186 { 3187 SRegType result; 3188 3189 /* 3190 * Check for trivial case so we don't have to hit memory. 3191 */ 3192 if (type1 == type2) 3193 return type1; 3194 3195 /* 3196 * Use the table if we can, and reject any attempts to merge something 3197 * from the table with a reference type. 3198 * 3199 * The uninitialized table entry at index zero *will* show up as a 3200 * simple kRegTypeUninit value. Since this cannot be merged with 3201 * anything but itself, the rules do the right thing. 3202 */ 3203 if (type1 < kRegTypeMAX) { 3204 if (type2 < kRegTypeMAX) { 3205 result = gDvmMergeTab[type1][type2]; 3206 } else { 3207 /* simple + reference == conflict, usually */ 3208 if (type1 == kRegTypeZero) 3209 result = type2; 3210 else 3211 result = kRegTypeConflict; 3212 } 3213 } else { 3214 if (type2 < kRegTypeMAX) { 3215 /* reference + simple == conflict, usually */ 3216 if (type2 == kRegTypeZero) 3217 result = type1; 3218 else 3219 result = kRegTypeConflict; 3220 } else { 3221 /* merging two references */ 3222 assert(type1 == type2); 3223 result = type1; 3224 } 3225 } 3226 3227 if (result != type1) 3228 *pChanged = true; 3229 return result; 3230 } 3231 3232 /* 3233 * Control can transfer to "nextInsn". 3234 * 3235 * Merge the registers from "workRegs" into "addrRegs" at "nextInsn", and 3236 * set the "changed" flag on the target address if the registers have changed. 3237 */ 3238 static void updateRegisters(WorkState* pState, int nextInsn, 3239 const SRegType* workRegs) 3240 { 3241 const Method* meth = pState->method; 3242 InsnFlags* insnFlags = pState->insnFlags; 3243 const int insnRegCountPlus = pState->insnRegCountPlus; 3244 SRegType* targetRegs = getRegisterLine(pState, nextInsn); 3245 3246 if (!dvmInsnIsVisitedOrChanged(insnFlags, nextInsn)) { 3247 /* 3248 * We haven't processed this instruction before, and we haven't 3249 * touched the registers here, so there's nothing to "merge". Copy 3250 * the registers over and mark it as changed. (This is the only 3251 * way a register can transition out of "unknown", so this is not 3252 * just an optimization.) 3253 */ 3254 LOGVV("COPY into 0x%04x\n", nextInsn); 3255 copyRegisters(targetRegs, workRegs, insnRegCountPlus); 3256 dvmInsnSetChanged(insnFlags, nextInsn, true); 3257 } else { 3258 /* merge registers, set Changed only if different */ 3259 LOGVV("MERGE into 0x%04x\n", nextInsn); 3260 bool changed = false; 3261 int i; 3262 3263 for (i = 0; i < insnRegCountPlus; i++) { 3264 targetRegs[i] = mergeTypes(targetRegs[i], workRegs[i], &changed); 3265 } 3266 3267 if (changed) 3268 dvmInsnSetChanged(insnFlags, nextInsn, true); 3269 } 3270 } 3271 3272 #endif /*#if 0*/ 3273