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