| /* |
| * Copyright (C) 2009 The Android Open Source Project |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| /* |
| * This code generate "register maps" for Dalvik bytecode. In a stack-based |
| * VM we might call these "stack maps". They are used to increase the |
| * precision in the garbage collector when scanning references in the |
| * interpreter thread stacks. |
| */ |
| #include "Dalvik.h" |
| #include "analysis/CodeVerify.h" |
| #include "analysis/RegisterMap.h" |
| #include "libdex/DexCatch.h" |
| #include "libdex/InstrUtils.h" |
| #include "libdex/Leb128.h" |
| |
| #include <stddef.h> |
| |
| /* double-check the compression */ |
| #define REGISTER_MAP_VERIFY true |
| |
| /* verbose logging */ |
| #define REGISTER_MAP_VERBOSE false |
| |
| |
| // fwd |
| static void outputTypeVector(const RegType* regs, int insnRegCount, u1* data); |
| static bool verifyMap(VerifierData* vdata, const RegisterMap* pMap); |
| static int compareMaps(const RegisterMap* pMap1, const RegisterMap* pMap2); |
| |
| static void computeMapStats(RegisterMap* pMap, const Method* method); |
| static RegisterMap* compressMapDifferential(const RegisterMap* pMap,\ |
| const Method* meth); |
| static RegisterMap* uncompressMapDifferential(const RegisterMap* pMap); |
| |
| |
| //#define REGISTER_MAP_STATS |
| #ifdef REGISTER_MAP_STATS |
| /* |
| * Generate some statistics on the register maps we create and use. |
| */ |
| #define kMaxGcPointGap 50 |
| #define kUpdatePosnMinRegs 24 |
| #define kNumUpdatePosns 8 |
| #define kMaxDiffBits 20 |
| typedef struct MapStats { |
| /* |
| * Buckets measuring the distance between GC points. This tells us how |
| * many bits we need to encode the advancing program counter. We ignore |
| * some of the "long tail" entries. |
| */ |
| int gcPointGap[kMaxGcPointGap]; |
| |
| /* |
| * Number of gaps. Equal to (number of gcPoints - number of methods), |
| * since the computation isn't including the initial gap. |
| */ |
| int gcGapCount; |
| |
| /* |
| * Number of gaps. |
| */ |
| int totalGcPointCount; |
| |
| /* |
| * For larger methods (>= 24 registers), measure in which octant register |
| * updates occur. This should help us understand whether register |
| * changes tend to cluster in the low regs even for large methods. |
| */ |
| int updatePosn[kNumUpdatePosns]; |
| |
| /* |
| * For all methods, count up the number of changes to registers < 16 |
| * and >= 16. |
| */ |
| int updateLT16; |
| int updateGE16; |
| |
| /* |
| * Histogram of the number of bits that differ between adjacent entries. |
| */ |
| int numDiffBits[kMaxDiffBits]; |
| |
| |
| /* |
| * Track the number of expanded maps, and the heap space required to |
| * hold them. |
| */ |
| int numExpandedMaps; |
| int totalExpandedMapSize; |
| } MapStats; |
| #endif |
| |
| /* |
| * Prepare some things. |
| */ |
| bool dvmRegisterMapStartup(void) |
| { |
| #ifdef REGISTER_MAP_STATS |
| MapStats* pStats = calloc(1, sizeof(MapStats)); |
| gDvm.registerMapStats = pStats; |
| #endif |
| return true; |
| } |
| |
| /* |
| * Clean up. |
| */ |
| void dvmRegisterMapShutdown(void) |
| { |
| #ifdef REGISTER_MAP_STATS |
| free(gDvm.registerMapStats); |
| #endif |
| } |
| |
| /* |
| * Write stats to log file. |
| */ |
| void dvmRegisterMapDumpStats(void) |
| { |
| #ifdef REGISTER_MAP_STATS |
| MapStats* pStats = (MapStats*) gDvm.registerMapStats; |
| int i, end; |
| |
| for (end = kMaxGcPointGap-1; end >= 0; end--) { |
| if (pStats->gcPointGap[end] != 0) |
| break; |
| } |
| |
| LOGI("Register Map gcPointGap stats (diff count=%d, total=%d):\n", |
| pStats->gcGapCount, pStats->totalGcPointCount); |
| assert(pStats->gcPointGap[0] == 0); |
| for (i = 1; i <= end; i++) { |
| LOGI(" %2d %d\n", i, pStats->gcPointGap[i]); |
| } |
| |
| |
| for (end = kMaxDiffBits-1; end >= 0; end--) { |
| if (pStats->numDiffBits[end] != 0) |
| break; |
| } |
| |
| LOGI("Register Map bit difference stats:\n"); |
| for (i = 0; i <= end; i++) { |
| LOGI(" %2d %d\n", i, pStats->numDiffBits[i]); |
| } |
| |
| |
| LOGI("Register Map update position stats (lt16=%d ge16=%d):\n", |
| pStats->updateLT16, pStats->updateGE16); |
| for (i = 0; i < kNumUpdatePosns; i++) { |
| LOGI(" %2d %d\n", i, pStats->updatePosn[i]); |
| } |
| #endif |
| } |
| |
| |
| /* |
| * =========================================================================== |
| * Map generation |
| * =========================================================================== |
| */ |
| |
| /* |
| * Generate the register map for a method that has just been verified |
| * (i.e. we're doing this as part of verification). |
| * |
| * For type-precise determination we have all the data we need, so we |
| * just need to encode it in some clever fashion. |
| * |
| * Returns a pointer to a newly-allocated RegisterMap, or NULL on failure. |
| */ |
| RegisterMap* dvmGenerateRegisterMapV(VerifierData* vdata) |
| { |
| static const int kHeaderSize = offsetof(RegisterMap, data); |
| RegisterMap* pMap = NULL; |
| RegisterMap* pResult = NULL; |
| RegisterMapFormat format; |
| u1 regWidth; |
| u1* mapData; |
| int i, bytesForAddr, gcPointCount; |
| int bufSize; |
| |
| if (vdata->method->registersSize >= 2048) { |
| LOGE("ERROR: register map can't handle %d registers\n", |
| vdata->method->registersSize); |
| goto bail; |
| } |
| regWidth = (vdata->method->registersSize + 7) / 8; |
| |
| /* |
| * Decide if we need 8 or 16 bits to hold the address. Strictly speaking |
| * we only need 16 bits if we actually encode an address >= 256 -- if |
| * the method has a section at the end without GC points (e.g. array |
| * data) we don't need to count it. The situation is unusual, and |
| * detecting it requires scanning the entire method, so we don't bother. |
| */ |
| if (vdata->insnsSize < 256) { |
| format = kRegMapFormatCompact8; |
| bytesForAddr = 1; |
| } else { |
| format = kRegMapFormatCompact16; |
| bytesForAddr = 2; |
| } |
| |
| /* |
| * Count up the number of GC point instructions. |
| * |
| * NOTE: this does not automatically include the first instruction, |
| * since we don't count method entry as a GC point. |
| */ |
| gcPointCount = 0; |
| for (i = 0; i < vdata->insnsSize; i++) { |
| if (dvmInsnIsGcPoint(vdata->insnFlags, i)) |
| gcPointCount++; |
| } |
| if (gcPointCount >= 65536) { |
| /* we could handle this, but in practice we don't get near this */ |
| LOGE("ERROR: register map can't handle %d gc points in one method\n", |
| gcPointCount); |
| goto bail; |
| } |
| |
| /* |
| * Allocate a buffer to hold the map data. |
| */ |
| bufSize = kHeaderSize + gcPointCount * (bytesForAddr + regWidth); |
| |
| LOGV("+++ grm: %s.%s (adr=%d gpc=%d rwd=%d bsz=%d)\n", |
| vdata->method->clazz->descriptor, vdata->method->name, |
| bytesForAddr, gcPointCount, regWidth, bufSize); |
| |
| pMap = (RegisterMap*) malloc(bufSize); |
| dvmRegisterMapSetFormat(pMap, format); |
| dvmRegisterMapSetOnHeap(pMap, true); |
| dvmRegisterMapSetRegWidth(pMap, regWidth); |
| dvmRegisterMapSetNumEntries(pMap, gcPointCount); |
| |
| /* |
| * Populate it. |
| */ |
| mapData = pMap->data; |
| for (i = 0; i < vdata->insnsSize; i++) { |
| if (dvmInsnIsGcPoint(vdata->insnFlags, i)) { |
| assert(vdata->addrRegs[i] != NULL); |
| if (format == kRegMapFormatCompact8) { |
| *mapData++ = i; |
| } else /*kRegMapFormatCompact16*/ { |
| *mapData++ = i & 0xff; |
| *mapData++ = i >> 8; |
| } |
| outputTypeVector(vdata->addrRegs[i], vdata->insnRegCount, mapData); |
| mapData += regWidth; |
| } |
| } |
| |
| LOGV("mapData=%p pMap=%p bufSize=%d\n", mapData, pMap, bufSize); |
| assert(mapData - (const u1*) pMap == bufSize); |
| |
| #if 1 |
| if (!verifyMap(vdata, pMap)) |
| goto bail; |
| #endif |
| #ifdef REGISTER_MAP_STATS |
| computeMapStats(pMap, vdata->method); |
| #endif |
| |
| /* |
| * Try to compress the map. |
| */ |
| RegisterMap* pCompMap; |
| |
| pCompMap = compressMapDifferential(pMap, vdata->method); |
| if (pCompMap != NULL) { |
| if (REGISTER_MAP_VERIFY) { |
| /* |
| * Expand the compressed map we just created, and compare it |
| * to the original. Abort the VM if it doesn't match up. |
| */ |
| RegisterMap* pUncompMap; |
| pUncompMap = uncompressMapDifferential(pCompMap); |
| if (pUncompMap == NULL) { |
| LOGE("Map failed to uncompress - %s.%s\n", |
| vdata->method->clazz->descriptor, |
| vdata->method->name); |
| free(pCompMap); |
| /* bad - compression is broken or we're out of memory */ |
| dvmAbort(); |
| } else { |
| if (compareMaps(pMap, pUncompMap) != 0) { |
| LOGE("Map comparison failed - %s.%s\n", |
| vdata->method->clazz->descriptor, |
| vdata->method->name); |
| free(pCompMap); |
| /* bad - compression is broken */ |
| dvmAbort(); |
| } |
| |
| /* verify succeeded */ |
| free(pUncompMap); |
| } |
| } |
| |
| if (REGISTER_MAP_VERBOSE) { |
| LOGD("Good compress on %s.%s\n", |
| vdata->method->clazz->descriptor, |
| vdata->method->name); |
| } |
| free(pMap); |
| pMap = pCompMap; |
| } else { |
| if (REGISTER_MAP_VERBOSE) { |
| LOGD("Unable to compress %s.%s (ent=%d rw=%d)\n", |
| vdata->method->clazz->descriptor, |
| vdata->method->name, |
| dvmRegisterMapGetNumEntries(pMap), |
| dvmRegisterMapGetRegWidth(pMap)); |
| } |
| } |
| |
| pResult = pMap; |
| |
| bail: |
| return pResult; |
| } |
| |
| /* |
| * Release the storage held by a RegisterMap. |
| */ |
| void dvmFreeRegisterMap(RegisterMap* pMap) |
| { |
| if (pMap == NULL) |
| return; |
| |
| assert(dvmRegisterMapGetOnHeap(pMap)); |
| free(pMap); |
| } |
| |
| /* |
| * Determine if the RegType value is a reference type. |
| * |
| * Ordinarily we include kRegTypeZero in the "is it a reference" |
| * check. There's no value in doing so here, because we know |
| * the register can't hold anything but zero. |
| */ |
| static inline bool isReferenceType(RegType type) |
| { |
| return (type > kRegTypeMAX || type == kRegTypeUninit); |
| } |
| |
| /* |
| * Given a line of registers, output a bit vector that indicates whether |
| * or not the register holds a reference type (which could be null). |
| * |
| * We use '1' to indicate it's a reference, '0' for anything else (numeric |
| * value, uninitialized data, merge conflict). Register 0 will be found |
| * in the low bit of the first byte. |
| */ |
| static void outputTypeVector(const RegType* regs, int insnRegCount, u1* data) |
| { |
| u1 val = 0; |
| int i; |
| |
| for (i = 0; i < insnRegCount; i++) { |
| RegType type = *regs++; |
| val >>= 1; |
| if (isReferenceType(type)) |
| val |= 0x80; /* set hi bit */ |
| |
| if ((i & 0x07) == 7) |
| *data++ = val; |
| } |
| if ((i & 0x07) != 0) { |
| /* flush bits from last byte */ |
| val >>= 8 - (i & 0x07); |
| *data++ = val; |
| } |
| } |
| |
| /* |
| * Print the map as a series of binary strings. |
| * |
| * Pass in method->registersSize if known, or -1 if not. |
| */ |
| static void dumpRegisterMap(const RegisterMap* pMap, int registersSize) |
| { |
| const u1* rawMap = pMap->data; |
| const RegisterMapFormat format = dvmRegisterMapGetFormat(pMap); |
| const int numEntries = dvmRegisterMapGetNumEntries(pMap); |
| const int regWidth = dvmRegisterMapGetRegWidth(pMap); |
| int addrWidth; |
| |
| switch (format) { |
| case kRegMapFormatCompact8: |
| addrWidth = 1; |
| break; |
| case kRegMapFormatCompact16: |
| addrWidth = 2; |
| break; |
| default: |
| /* can't happen */ |
| LOGE("Can only dump Compact8 / Compact16 maps (not %d)\n", format); |
| return; |
| } |
| |
| if (registersSize < 0) |
| registersSize = 8 * regWidth; |
| assert(registersSize <= regWidth * 8); |
| |
| int ent; |
| for (ent = 0; ent < numEntries; ent++) { |
| int i, addr; |
| |
| addr = *rawMap++; |
| if (addrWidth > 1) |
| addr |= (*rawMap++) << 8; |
| |
| const u1* dataStart = rawMap; |
| u1 val = 0; |
| |
| /* create binary string */ |
| char outBuf[registersSize +1]; |
| for (i = 0; i < registersSize; i++) { |
| val >>= 1; |
| if ((i & 0x07) == 0) |
| val = *rawMap++; |
| |
| outBuf[i] = '0' + (val & 0x01); |
| } |
| outBuf[i] = '\0'; |
| |
| /* back up and create hex dump */ |
| char hexBuf[regWidth * 3 +1]; |
| char* cp = hexBuf; |
| rawMap = dataStart; |
| for (i = 0; i < regWidth; i++) { |
| sprintf(cp, " %02x", *rawMap++); |
| cp += 3; |
| } |
| hexBuf[i * 3] = '\0'; |
| |
| LOGD(" %04x %s %s\n", addr, outBuf, hexBuf); |
| } |
| } |
| |
| /* |
| * Double-check the map. |
| * |
| * We run through all of the data in the map, and compare it to the original. |
| * Only works on uncompressed data. |
| */ |
| static bool verifyMap(VerifierData* vdata, const RegisterMap* pMap) |
| { |
| const u1* rawMap = pMap->data; |
| const RegisterMapFormat format = dvmRegisterMapGetFormat(pMap); |
| const int numEntries = dvmRegisterMapGetNumEntries(pMap); |
| int ent; |
| bool dumpMap = false; |
| |
| if (false) { |
| const char* cd = "Landroid/net/http/Request;"; |
| const char* mn = "readResponse"; |
| const char* sg = "(Landroid/net/http/AndroidHttpClientConnection;)V"; |
| if (strcmp(vdata->method->clazz->descriptor, cd) == 0 && |
| strcmp(vdata->method->name, mn) == 0) |
| { |
| char* desc; |
| desc = dexProtoCopyMethodDescriptor(&vdata->method->prototype); |
| LOGI("Map for %s.%s %s\n", vdata->method->clazz->descriptor, |
| vdata->method->name, desc); |
| free(desc); |
| |
| dumpMap = true; |
| } |
| } |
| |
| if ((vdata->method->registersSize + 7) / 8 != pMap->regWidth) { |
| LOGE("GLITCH: registersSize=%d, regWidth=%d\n", |
| vdata->method->registersSize, pMap->regWidth); |
| return false; |
| } |
| |
| for (ent = 0; ent < numEntries; ent++) { |
| int addr; |
| |
| switch (format) { |
| case kRegMapFormatCompact8: |
| addr = *rawMap++; |
| break; |
| case kRegMapFormatCompact16: |
| addr = *rawMap++; |
| addr |= (*rawMap++) << 8; |
| break; |
| default: |
| /* shouldn't happen */ |
| LOGE("GLITCH: bad format (%d)", format); |
| dvmAbort(); |
| } |
| |
| const u1* dataStart = rawMap; |
| const RegType* regs = vdata->addrRegs[addr]; |
| if (regs == NULL) { |
| LOGE("GLITCH: addr %d has no data\n", addr); |
| return false; |
| } |
| |
| u1 val = 0; |
| int i; |
| |
| for (i = 0; i < vdata->method->registersSize; i++) { |
| bool bitIsRef, regIsRef; |
| |
| val >>= 1; |
| if ((i & 0x07) == 0) { |
| /* load next byte of data */ |
| val = *rawMap++; |
| } |
| |
| bitIsRef = val & 0x01; |
| |
| RegType type = regs[i]; |
| regIsRef = isReferenceType(type); |
| |
| if (bitIsRef != regIsRef) { |
| LOGE("GLITCH: addr %d reg %d: bit=%d reg=%d(%d)\n", |
| addr, i, bitIsRef, regIsRef, type); |
| return false; |
| } |
| } |
| |
| /* rawMap now points to the address field of the next entry */ |
| } |
| |
| if (dumpMap) |
| dumpRegisterMap(pMap, vdata->method->registersSize); |
| |
| return true; |
| } |
| |
| |
| /* |
| * =========================================================================== |
| * DEX generation & parsing |
| * =========================================================================== |
| */ |
| |
| /* |
| * Advance "ptr" to ensure 32-bit alignment. |
| */ |
| static inline u1* align32(u1* ptr) |
| { |
| return (u1*) (((int) ptr + 3) & ~0x03); |
| } |
| |
| /* |
| * Compute the size, in bytes, of a register map. |
| */ |
| static size_t computeRegisterMapSize(const RegisterMap* pMap) |
| { |
| static const int kHeaderSize = offsetof(RegisterMap, data); |
| u1 format = dvmRegisterMapGetFormat(pMap); |
| u2 numEntries = dvmRegisterMapGetNumEntries(pMap); |
| |
| assert(pMap != NULL); |
| |
| switch (format) { |
| case kRegMapFormatNone: |
| return 1; |
| case kRegMapFormatCompact8: |
| return kHeaderSize + (1 + pMap->regWidth) * numEntries; |
| case kRegMapFormatCompact16: |
| return kHeaderSize + (2 + pMap->regWidth) * numEntries; |
| case kRegMapFormatDifferential: |
| { |
| /* kHeaderSize + decoded ULEB128 length */ |
| const u1* ptr = pMap->data; |
| int len = readUnsignedLeb128(&ptr); |
| return len + (ptr - (u1*) pMap); |
| } |
| default: |
| LOGE("Bad register map format %d\n", format); |
| dvmAbort(); |
| return 0; |
| } |
| } |
| |
| /* |
| * Output the map for a single method, if it has one. |
| * |
| * Abstract and native methods have no map. All others are expected to |
| * have one, since we know the class verified successfully. |
| * |
| * This strips the "allocated on heap" flag from the format byte, so that |
| * direct-mapped maps are correctly identified as such. |
| */ |
| static bool writeMapForMethod(const Method* meth, u1** pPtr) |
| { |
| if (meth->registerMap == NULL) { |
| if (!dvmIsAbstractMethod(meth) && !dvmIsNativeMethod(meth)) { |
| LOGW("Warning: no map available for %s.%s\n", |
| meth->clazz->descriptor, meth->name); |
| /* weird, but keep going */ |
| } |
| *(*pPtr)++ = kRegMapFormatNone; |
| return true; |
| } |
| |
| /* serialize map into the buffer */ |
| size_t mapSize = computeRegisterMapSize(meth->registerMap); |
| memcpy(*pPtr, meth->registerMap, mapSize); |
| |
| /* strip the "on heap" flag out of the format byte, which is always first */ |
| assert(**pPtr == meth->registerMap->format); |
| **pPtr &= ~(kRegMapFormatOnHeap); |
| |
| *pPtr += mapSize; |
| |
| return true; |
| } |
| |
| /* |
| * Write maps for all methods in the specified class to the buffer, which |
| * can hold at most "length" bytes. "*pPtr" will be advanced past the end |
| * of the data we write. |
| */ |
| static bool writeMapsAllMethods(DvmDex* pDvmDex, const ClassObject* clazz, |
| u1** pPtr, size_t length) |
| { |
| RegisterMapMethodPool* pMethodPool; |
| u1* ptr = *pPtr; |
| int i, methodCount; |
| |
| /* artificial limit */ |
| if (clazz->virtualMethodCount + clazz->directMethodCount >= 65536) { |
| LOGE("Too many methods in %s\n", clazz->descriptor); |
| return false; |
| } |
| |
| pMethodPool = (RegisterMapMethodPool*) ptr; |
| ptr += offsetof(RegisterMapMethodPool, methodData); |
| methodCount = 0; |
| |
| /* |
| * Run through all methods, direct then virtual. The class loader will |
| * traverse them in the same order. (We could split them into two |
| * distinct pieces, but there doesn't appear to be any value in doing |
| * so other than that it makes class loading slightly less fragile.) |
| * |
| * The class loader won't know about miranda methods at the point |
| * where it parses this, so we omit those. |
| * |
| * TODO: consider omitting all native/abstract definitions. Should be |
| * safe, though we lose the ability to sanity-check against the |
| * method counts in the DEX file. |
| */ |
| for (i = 0; i < clazz->directMethodCount; i++) { |
| const Method* meth = &clazz->directMethods[i]; |
| if (dvmIsMirandaMethod(meth)) |
| continue; |
| if (!writeMapForMethod(&clazz->directMethods[i], &ptr)) { |
| return false; |
| } |
| methodCount++; |
| //ptr = align32(ptr); |
| } |
| |
| for (i = 0; i < clazz->virtualMethodCount; i++) { |
| const Method* meth = &clazz->virtualMethods[i]; |
| if (dvmIsMirandaMethod(meth)) |
| continue; |
| if (!writeMapForMethod(&clazz->virtualMethods[i], &ptr)) { |
| return false; |
| } |
| methodCount++; |
| //ptr = align32(ptr); |
| } |
| |
| pMethodPool->methodCount = methodCount; |
| |
| *pPtr = ptr; |
| return true; |
| } |
| |
| /* |
| * Write maps for all classes to the specified buffer, which can hold at |
| * most "length" bytes. |
| * |
| * Returns the actual length used, or 0 on failure. |
| */ |
| static size_t writeMapsAllClasses(DvmDex* pDvmDex, u1* basePtr, size_t length) |
| { |
| DexFile* pDexFile = pDvmDex->pDexFile; |
| u4 count = pDexFile->pHeader->classDefsSize; |
| RegisterMapClassPool* pClassPool; |
| u4* offsetTable; |
| u1* ptr = basePtr; |
| u4 idx; |
| |
| assert(gDvm.optimizing); |
| |
| pClassPool = (RegisterMapClassPool*) ptr; |
| ptr += offsetof(RegisterMapClassPool, classDataOffset); |
| offsetTable = (u4*) ptr; |
| ptr += count * sizeof(u4); |
| |
| pClassPool->numClasses = count; |
| |
| /* |
| * We want an entry for every class, loaded or not. |
| */ |
| for (idx = 0; idx < count; idx++) { |
| const DexClassDef* pClassDef; |
| const char* classDescriptor; |
| ClassObject* clazz; |
| |
| pClassDef = dexGetClassDef(pDexFile, idx); |
| classDescriptor = dexStringByTypeIdx(pDexFile, pClassDef->classIdx); |
| |
| /* |
| * All classes have been loaded into the bootstrap class loader. |
| * If we can find it, and it was successfully pre-verified, we |
| * run through its methods and add the register maps. |
| * |
| * If it wasn't pre-verified then we know it can't have any |
| * register maps. Classes that can't be loaded or failed |
| * verification get an empty slot in the index. |
| */ |
| clazz = NULL; |
| if ((pClassDef->accessFlags & CLASS_ISPREVERIFIED) != 0) |
| clazz = dvmLookupClass(classDescriptor, NULL, false); |
| |
| if (clazz != NULL) { |
| offsetTable[idx] = ptr - basePtr; |
| LOGVV("%d -> offset %d (%p-%p)\n", |
| idx, offsetTable[idx], ptr, basePtr); |
| |
| if (!writeMapsAllMethods(pDvmDex, clazz, &ptr, |
| length - (ptr - basePtr))) |
| { |
| return 0; |
| } |
| |
| ptr = align32(ptr); |
| LOGVV("Size %s (%d+%d methods): %d\n", clazz->descriptor, |
| clazz->directMethodCount, clazz->virtualMethodCount, |
| (ptr - basePtr) - offsetTable[idx]); |
| } else { |
| LOGV("%4d NOT mapadding '%s'\n", idx, classDescriptor); |
| assert(offsetTable[idx] == 0); |
| } |
| } |
| |
| if (ptr - basePtr >= (int)length) { |
| /* a bit late */ |
| LOGE("Buffer overrun\n"); |
| dvmAbort(); |
| } |
| |
| return ptr - basePtr; |
| } |
| |
| /* |
| * Generate a register map set for all verified classes in "pDvmDex". |
| */ |
| RegisterMapBuilder* dvmGenerateRegisterMaps(DvmDex* pDvmDex) |
| { |
| RegisterMapBuilder* pBuilder; |
| |
| pBuilder = (RegisterMapBuilder*) calloc(1, sizeof(RegisterMapBuilder)); |
| if (pBuilder == NULL) |
| return NULL; |
| |
| /* |
| * We have a couple of options here: |
| * (1) Compute the size of the output, and malloc a buffer. |
| * (2) Create a "large-enough" anonymous mmap region. |
| * |
| * The nice thing about option #2 is that we don't have to traverse |
| * all of the classes and methods twice. The risk is that we might |
| * not make the region large enough. Since the pages aren't mapped |
| * until used we can allocate a semi-absurd amount of memory without |
| * worrying about the effect on the rest of the system. |
| * |
| * The basic encoding on the largest jar file requires about 1MB of |
| * storage. We map out 4MB here. (TODO: guarantee that the last |
| * page of the mapping is marked invalid, so we reliably fail if |
| * we overrun.) |
| */ |
| if (sysCreatePrivateMap(4 * 1024 * 1024, &pBuilder->memMap) != 0) { |
| free(pBuilder); |
| return NULL; |
| } |
| |
| /* |
| * Create the maps. |
| */ |
| size_t actual = writeMapsAllClasses(pDvmDex, (u1*)pBuilder->memMap.addr, |
| pBuilder->memMap.length); |
| if (actual == 0) { |
| dvmFreeRegisterMapBuilder(pBuilder); |
| return NULL; |
| } |
| |
| LOGV("TOTAL size of register maps: %d\n", actual); |
| |
| pBuilder->data = pBuilder->memMap.addr; |
| pBuilder->size = actual; |
| return pBuilder; |
| } |
| |
| /* |
| * Free the builder. |
| */ |
| void dvmFreeRegisterMapBuilder(RegisterMapBuilder* pBuilder) |
| { |
| if (pBuilder == NULL) |
| return; |
| |
| sysReleaseShmem(&pBuilder->memMap); |
| free(pBuilder); |
| } |
| |
| |
| /* |
| * Find the data for the specified class. |
| * |
| * If there's no register map data, or none for this class, we return NULL. |
| */ |
| const void* dvmRegisterMapGetClassData(const DexFile* pDexFile, u4 classIdx, |
| u4* pNumMaps) |
| { |
| const RegisterMapClassPool* pClassPool; |
| const RegisterMapMethodPool* pMethodPool; |
| |
| pClassPool = (const RegisterMapClassPool*) pDexFile->pRegisterMapPool; |
| if (pClassPool == NULL) |
| return NULL; |
| |
| if (classIdx >= pClassPool->numClasses) { |
| LOGE("bad class index (%d vs %d)\n", classIdx, pClassPool->numClasses); |
| dvmAbort(); |
| } |
| |
| u4 classOffset = pClassPool->classDataOffset[classIdx]; |
| if (classOffset == 0) { |
| LOGV("+++ no map for classIdx=%d\n", classIdx); |
| return NULL; |
| } |
| |
| pMethodPool = |
| (const RegisterMapMethodPool*) (((u1*) pClassPool) + classOffset); |
| if (pNumMaps != NULL) |
| *pNumMaps = pMethodPool->methodCount; |
| return pMethodPool->methodData; |
| } |
| |
| /* |
| * This advances "*pPtr" and returns its original value. |
| */ |
| const RegisterMap* dvmRegisterMapGetNext(const void** pPtr) |
| { |
| const RegisterMap* pMap = *pPtr; |
| |
| *pPtr = /*align32*/(((u1*) pMap) + computeRegisterMapSize(pMap)); |
| LOGVV("getNext: %p -> %p (f=0x%x w=%d e=%d)\n", |
| pMap, *pPtr, pMap->format, pMap->regWidth, |
| dvmRegisterMapGetNumEntries(pMap)); |
| return pMap; |
| } |
| |
| |
| /* |
| * =========================================================================== |
| * Utility functions |
| * =========================================================================== |
| */ |
| |
| /* |
| * Return the data for the specified address, or NULL if not found. |
| * |
| * The result must be released with dvmReleaseRegisterMapLine(). |
| */ |
| const u1* dvmRegisterMapGetLine(const RegisterMap* pMap, int addr) |
| { |
| int addrWidth, lineWidth; |
| u1 format = dvmRegisterMapGetFormat(pMap); |
| u2 numEntries = dvmRegisterMapGetNumEntries(pMap); |
| |
| assert(numEntries > 0); |
| |
| switch (format) { |
| case kRegMapFormatNone: |
| return NULL; |
| case kRegMapFormatCompact8: |
| addrWidth = 1; |
| break; |
| case kRegMapFormatCompact16: |
| addrWidth = 2; |
| break; |
| default: |
| LOGE("Unknown format %d\n", format); |
| dvmAbort(); |
| return NULL; |
| } |
| |
| lineWidth = addrWidth + pMap->regWidth; |
| |
| /* |
| * Find the appropriate entry. Many maps are very small, some are very |
| * large. |
| */ |
| static const int kSearchThreshold = 8; |
| const u1* data; |
| int lineAddr; |
| |
| if (numEntries < kSearchThreshold) { |
| int i; |
| data = pMap->data; |
| for (i = numEntries; i > 0; i--) { |
| lineAddr = data[0]; |
| if (addrWidth > 1) |
| lineAddr |= data[1] << 8; |
| if (lineAddr == addr) |
| return data + addrWidth; |
| |
| data += lineWidth; |
| } |
| } else { |
| int hi, lo, mid; |
| |
| lo = 0; |
| hi = numEntries -1; |
| |
| while (hi >= lo) { |
| mid = (hi + lo) / 2; |
| data = pMap->data + lineWidth * mid; |
| |
| lineAddr = data[0]; |
| if (addrWidth > 1) |
| lineAddr |= data[1] << 8; |
| |
| if (addr > lineAddr) { |
| lo = mid + 1; |
| } else if (addr < lineAddr) { |
| hi = mid - 1; |
| } else { |
| return data + addrWidth; |
| } |
| } |
| } |
| |
| assert(data == pMap->data + lineWidth * numEntries); |
| return NULL; |
| } |
| |
| /* |
| * Compare two register maps. |
| * |
| * Returns 0 if they're equal, nonzero if not. |
| */ |
| static int compareMaps(const RegisterMap* pMap1, const RegisterMap* pMap2) |
| { |
| size_t size1, size2; |
| |
| size1 = computeRegisterMapSize(pMap1); |
| size2 = computeRegisterMapSize(pMap2); |
| if (size1 != size2) { |
| LOGI("compareMaps: size mismatch (%zd vs %zd)\n", size1, size2); |
| return -1; |
| } |
| |
| if (memcmp(pMap1, pMap2, size1) != 0) { |
| LOGI("compareMaps: content mismatch\n"); |
| return -1; |
| } |
| |
| return 0; |
| } |
| |
| |
| /* |
| * Get the expanded form of the register map associated with the method. |
| * |
| * If the map is already in one of the uncompressed formats, we return |
| * immediately. Otherwise, we expand the map and replace method's register |
| * map pointer, freeing it if it was allocated on the heap. |
| * |
| * NOTE: this function is not synchronized; external locking is mandatory |
| * (unless we're in the zygote, where single-threaded access is guaranteed). |
| */ |
| const RegisterMap* dvmGetExpandedRegisterMap0(Method* method) |
| { |
| const RegisterMap* curMap = method->registerMap; |
| RegisterMap* newMap; |
| |
| if (curMap == NULL) |
| return NULL; |
| |
| /* sanity check to ensure this isn't called w/o external locking */ |
| /* (if we use this at a time other than during GC, fix/remove this test) */ |
| if (true) { |
| if (!gDvm.zygote && pthread_mutex_trylock(&gDvm.gcHeapLock) == 0) { |
| LOGE("GLITCH: dvmGetExpandedRegisterMap not called at GC time\n"); |
| dvmAbort(); |
| } |
| } |
| |
| RegisterMapFormat format = dvmRegisterMapGetFormat(curMap); |
| switch (format) { |
| case kRegMapFormatCompact8: |
| case kRegMapFormatCompact16: |
| if (REGISTER_MAP_VERBOSE) { |
| if (dvmRegisterMapGetOnHeap(curMap)) { |
| LOGD("RegMap: already expanded: %s.%s\n", |
| method->clazz->descriptor, method->name); |
| } else { |
| LOGD("RegMap: stored w/o compression: %s.%s\n", |
| method->clazz->descriptor, method->name); |
| } |
| } |
| return curMap; |
| case kRegMapFormatDifferential: |
| newMap = uncompressMapDifferential(curMap); |
| break; |
| default: |
| LOGE("Unknown format %d in dvmGetExpandedRegisterMap\n", format); |
| dvmAbort(); |
| } |
| |
| if (newMap == NULL) { |
| LOGE("Map failed to uncompress (fmt=%d) %s.%s\n", |
| format, method->clazz->descriptor, method->name); |
| return NULL; |
| } |
| |
| #ifdef REGISTER_MAP_STATS |
| /* |
| * Gather and display some stats. |
| */ |
| { |
| MapStats* pStats = (MapStats*) gDvm.registerMapStats; |
| pStats->numExpandedMaps++; |
| pStats->totalExpandedMapSize += computeRegisterMapSize(newMap); |
| LOGD("RMAP: count=%d size=%d\n", |
| pStats->numExpandedMaps, pStats->totalExpandedMapSize); |
| } |
| #endif |
| |
| IF_LOGV() { |
| char* desc = dexProtoCopyMethodDescriptor(&method->prototype); |
| LOGV("Expanding map -> %s.%s:%s\n", |
| method->clazz->descriptor, method->name, desc); |
| free(desc); |
| } |
| |
| /* |
| * Update method, and free compressed map if it was sitting on the heap. |
| */ |
| dvmSetRegisterMap(method, newMap); |
| |
| if (dvmRegisterMapGetOnHeap(curMap)) |
| dvmFreeRegisterMap((RegisterMap*) curMap); |
| |
| return newMap; |
| } |
| |
| |
| /* |
| * =========================================================================== |
| * Map compression |
| * =========================================================================== |
| */ |
| |
| /* |
| Notes on map compression |
| |
| The idea is to create a compressed form that will be uncompressed before |
| use, with the output possibly saved in a cache. This means we can use an |
| approach that is unsuited for random access if we choose. |
| |
| In the event that a map simply does not work with our compression scheme, |
| it's reasonable to store the map without compression. In the future we |
| may want to have more than one compression scheme, and try each in turn, |
| retaining the best. (We certainly want to keep the uncompressed form if it |
| turns out to be smaller or even slightly larger than the compressed form.) |
| |
| Each entry consists of an address and a bit vector. Adjacent entries are |
| strongly correlated, suggesting differential encoding. |
| |
| |
| Ideally we would avoid outputting adjacent entries with identical |
| bit vectors. However, the register values at a given address do not |
| imply anything about the set of valid registers at subsequent addresses. |
| We therefore cannot omit an entry. |
| |
| If the thread stack has a PC at an address without a corresponding |
| entry in the register map, we must conservatively scan the registers in |
| that thread. This can happen when single-stepping in the debugger, |
| because the debugger is allowed to invoke arbitrary methods when |
| a thread is stopped at a breakpoint. If we can guarantee that a GC |
| thread scan will never happen while the debugger has that thread stopped, |
| then we can lift this restriction and simply omit entries that don't |
| change the bit vector from its previous state. |
| |
| Each entry advances the address value by at least 1 (measured in 16-bit |
| "code units"). Looking at the bootclasspath entries, advancing by 2 units |
| is most common. Advances by 1 unit are far less common than advances by |
| 2 units, but more common than 5, and things fall off rapidly. Gaps of |
| up to 220 code units appear in some computationally intensive bits of code, |
| but are exceedingly rare. |
| |
| If we sum up the number of transitions in a couple of ranges in framework.jar: |
| [1,4]: 188998 of 218922 gaps (86.3%) |
| [1,7]: 211647 of 218922 gaps (96.7%) |
| Using a 3-bit delta, with one value reserved as an escape code, should |
| yield good results for the address. |
| |
| These results would change dramatically if we reduced the set of GC |
| points by e.g. removing instructions like integer divide that are only |
| present because they can throw and cause an allocation. |
| |
| We also need to include an "initial gap", because the first few instructions |
| in a method may not be GC points. |
| |
| |
| By observation, many entries simply repeat the previous bit vector, or |
| change only one or two bits. (This is with type-precise information; |
| the rate of change of bits will be different if live-precise information |
| is factored in). |
| |
| Looking again at adjacent entries in framework.jar: |
| 0 bits changed: 63.0% |
| 1 bit changed: 32.2% |
| After that it falls off rapidly, e.g. the number of entries with 2 bits |
| changed is usually less than 1/10th of the number of entries with 1 bit |
| changed. A solution that allows us to encode 0- or 1- bit changes |
| efficiently will do well. |
| |
| We still need to handle cases where a large number of bits change. We |
| probably want a way to drop in a full copy of the bit vector when it's |
| smaller than the representation of multiple bit changes. |
| |
| |
| The bit-change information can be encoded as an index that tells the |
| decoder to toggle the state. We want to encode the index in as few bits |
| as possible, but we need to allow for fairly wide vectors (e.g. we have a |
| method with 175 registers). We can deal with this in a couple of ways: |
| (1) use an encoding that assumes few registers and has an escape code |
| for larger numbers of registers; or (2) use different encodings based |
| on how many total registers the method has. The choice depends to some |
| extent on whether methods with large numbers of registers tend to modify |
| the first 16 regs more often than the others. |
| |
| The last N registers hold method arguments. If the bytecode is expected |
| to be examined in a debugger, "dx" ensures that the contents of these |
| registers won't change. Depending upon the encoding format, we may be |
| able to take advantage of this. We still have to encode the initial |
| state, but we know we'll never have to output a bit change for the last |
| N registers. |
| |
| Considering only methods with 16 or more registers, the "target octant" |
| for register changes looks like this: |
| [ 43.1%, 16.4%, 6.5%, 6.2%, 7.4%, 8.8%, 9.7%, 1.8% ] |
| As expected, there are fewer changes at the end of the list where the |
| arguments are kept, and more changes at the start of the list because |
| register values smaller than 16 can be used in compact Dalvik instructions |
| and hence are favored for frequently-used values. In general, the first |
| octant is considerably more active than later entries, the last octant |
| is much less active, and the rest are all about the same. |
| |
| Looking at all bit changes in all methods, 94% are to registers 0-15. The |
| encoding will benefit greatly by favoring the low-numbered registers. |
| |
| |
| Some of the smaller methods have identical maps, and space could be |
| saved by simply including a pointer to an earlier definition. This would |
| be best accomplished by specifying a "pointer" format value, followed by |
| a 3-byte (or ULEB128) offset. Implementing this would probably involve |
| generating a hash value for each register map and maintaining a hash table. |
| |
| In some cases there are repeating patterns in the bit vector that aren't |
| adjacent. These could benefit from a dictionary encoding. This doesn't |
| really become useful until the methods reach a certain size though, |
| and managing the dictionary may incur more overhead than we want. |
| |
| Large maps can be compressed significantly. The trouble is that, when |
| we need to use them, we have to uncompress them onto the heap. We may |
| get a better trade-off between storage size and heap usage by refusing to |
| compress large maps, so that they can be memory mapped and used directly. |
| (OTOH, only about 2% of the maps will ever actually be used.) |
| |
| |
| ----- differential format ----- |
| |
| // common header |
| +00 1B format |
| +01 1B regWidth |
| +02 2B numEntries (little-endian) |
| +04 nB length in bytes of the data that follows, in ULEB128 format |
| (not strictly necessary; allows determination of size w/o full parse) |
| +05+ 1B initial address (0-127), high bit set if max addr >= 256 |
| +06+ nB initial value for bit vector |
| |
| // for each entry |
| +00: CCCCBAAA |
| |
| AAA: address difference. Values from 0 to 6 indicate an increment of 1 |
| to 7. A value of 7 indicates that the address difference is large, |
| and the next byte is a ULEB128-encoded difference value. |
| |
| B: determines the meaning of CCCC. |
| |
| CCCC: if B is 0, this is the number of the bit to toggle (0-15). |
| If B is 1, this is a count of the number of changed bits (1-14). A value |
| of 0 means that no bits were changed, and a value of 15 indicates |
| that enough bits were changed that it required less space to output |
| the entire bit vector. |
| |
| +01: (optional) ULEB128-encoded address difference |
| |
| +01+: (optional) one or more ULEB128-encoded bit numbers, OR the entire |
| bit vector. |
| |
| The most common situation is an entry whose address has changed by 2-4 |
| code units, has no changes or just a single bit change, and the changed |
| register is less than 16. We should therefore be able to encode a large |
| number of entries with a single byte, which is half the size of the |
| Compact8 encoding method. |
| */ |
| |
| /* |
| * Compute some stats on an uncompressed register map. |
| */ |
| static void computeMapStats(RegisterMap* pMap, const Method* method) |
| { |
| #ifdef REGISTER_MAP_STATS |
| MapStats* pStats = (MapStats*) gDvm.registerMapStats; |
| const u1 format = dvmRegisterMapGetFormat(pMap); |
| const u2 numEntries = dvmRegisterMapGetNumEntries(pMap); |
| const u1* rawMap = pMap->data; |
| const u1* prevData = NULL; |
| int ent, addr, prevAddr = -1; |
| |
| for (ent = 0; ent < numEntries; ent++) { |
| switch (format) { |
| case kRegMapFormatCompact8: |
| addr = *rawMap++; |
| break; |
| case kRegMapFormatCompact16: |
| addr = *rawMap++; |
| addr |= (*rawMap++) << 8; |
| break; |
| default: |
| /* shouldn't happen */ |
| LOGE("GLITCH: bad format (%d)", format); |
| dvmAbort(); |
| } |
| |
| const u1* dataStart = rawMap; |
| |
| pStats->totalGcPointCount++; |
| |
| /* |
| * Gather "gap size" stats, i.e. the difference in addresses between |
| * successive GC points. |
| */ |
| if (prevData != NULL) { |
| assert(prevAddr >= 0); |
| int addrDiff = addr - prevAddr; |
| |
| if (addrDiff < 0) { |
| LOGE("GLITCH: address went backward (0x%04x->0x%04x, %s.%s)\n", |
| prevAddr, addr, method->clazz->descriptor, method->name); |
| } else if (addrDiff > kMaxGcPointGap) { |
| if (REGISTER_MAP_VERBOSE) { |
| LOGI("HEY: addrDiff is %d, max %d (0x%04x->0x%04x %s.%s)\n", |
| addrDiff, kMaxGcPointGap, prevAddr, addr, |
| method->clazz->descriptor, method->name); |
| } |
| /* skip this one */ |
| } else { |
| pStats->gcPointGap[addrDiff]++; |
| } |
| pStats->gcGapCount++; |
| |
| |
| /* |
| * Compare bit vectors in adjacent entries. We want to count |
| * up the number of bits that differ (to see if we frequently |
| * change 0 or 1 bits) and get a sense for which part of the |
| * vector changes the most often (near the start, middle, end). |
| * |
| * We only do the vector position quantization if we have at |
| * least 16 registers in the method. |
| */ |
| int numDiff = 0; |
| float div = (float) kNumUpdatePosns / method->registersSize; |
| int regByte; |
| for (regByte = 0; regByte < pMap->regWidth; regByte++) { |
| int prev, cur, bit; |
| |
| prev = prevData[regByte]; |
| cur = dataStart[regByte]; |
| |
| for (bit = 0; bit < 8; bit++) { |
| if (((prev >> bit) & 1) != ((cur >> bit) & 1)) { |
| numDiff++; |
| |
| int bitNum = regByte * 8 + bit; |
| |
| if (bitNum < 16) |
| pStats->updateLT16++; |
| else |
| pStats->updateGE16++; |
| |
| if (method->registersSize < 16) |
| continue; |
| |
| if (bitNum >= method->registersSize) { |
| /* stuff off the end should be zero in both */ |
| LOGE("WEIRD: bit=%d (%d/%d), prev=%02x cur=%02x\n", |
| bit, regByte, method->registersSize, |
| prev, cur); |
| assert(false); |
| } |
| int idx = (int) (bitNum * div); |
| if (!(idx >= 0 && idx < kNumUpdatePosns)) { |
| LOGE("FAIL: bitNum=%d (of %d) div=%.3f idx=%d\n", |
| bitNum, method->registersSize, div, idx); |
| assert(false); |
| } |
| pStats->updatePosn[idx]++; |
| } |
| } |
| } |
| |
| if (numDiff > kMaxDiffBits) { |
| if (REGISTER_MAP_VERBOSE) { |
| LOGI("WOW: numDiff is %d, max %d\n", numDiff, kMaxDiffBits); |
| } |
| } else { |
| pStats->numDiffBits[numDiff]++; |
| } |
| } |
| |
| /* advance to start of next line */ |
| rawMap += pMap->regWidth; |
| |
| prevAddr = addr; |
| prevData = dataStart; |
| } |
| #endif |
| } |
| |
| |
| /* |
| * Compute the difference between two bit vectors. |
| * |
| * If "lebOutBuf" is non-NULL, we output the bit indices in ULEB128 format |
| * as we go. Otherwise, we just generate the various counts. |
| * |
| * The bit vectors are compared byte-by-byte, so any unused bits at the |
| * end must be zero. |
| * |
| * Returns the number of bytes required to hold the ULEB128 output. |
| * |
| * If "pFirstBitChanged" or "pNumBitsChanged" are non-NULL, they will |
| * receive the index of the first changed bit and the number of changed |
| * bits, respectively. |
| */ |
| static int computeBitDiff(const u1* bits1, const u1* bits2, int byteWidth, |
| int* pFirstBitChanged, int* pNumBitsChanged, u1* lebOutBuf) |
| { |
| int numBitsChanged = 0; |
| int firstBitChanged = -1; |
| int lebSize = 0; |
| int byteNum; |
| |
| /* |
| * Run through the vectors, first comparing them at the byte level. This |
| * will yield a fairly quick result if nothing has changed between them. |
| */ |
| for (byteNum = 0; byteNum < byteWidth; byteNum++) { |
| u1 byte1 = *bits1++; |
| u1 byte2 = *bits2++; |
| if (byte1 != byte2) { |
| /* |
| * Walk through the byte, identifying the changed bits. |
| */ |
| int bitNum; |
| for (bitNum = 0; bitNum < 8; bitNum++) { |
| if (((byte1 >> bitNum) & 0x01) != ((byte2 >> bitNum) & 0x01)) { |
| int bitOffset = (byteNum << 3) + bitNum; |
| |
| if (firstBitChanged < 0) |
| firstBitChanged = bitOffset; |
| numBitsChanged++; |
| |
| if (lebOutBuf == NULL) { |
| lebSize += unsignedLeb128Size(bitOffset); |
| } else { |
| u1* curBuf = lebOutBuf; |
| lebOutBuf = writeUnsignedLeb128(lebOutBuf, bitOffset); |
| lebSize += lebOutBuf - curBuf; |
| } |
| } |
| } |
| } |
| } |
| |
| if (numBitsChanged > 0) |
| assert(firstBitChanged >= 0); |
| |
| if (pFirstBitChanged != NULL) |
| *pFirstBitChanged = firstBitChanged; |
| if (pNumBitsChanged != NULL) |
| *pNumBitsChanged = numBitsChanged; |
| |
| return lebSize; |
| } |
| |
| /* |
| * Compress the register map with differential encoding. |
| * |
| * "meth" is only needed for debug output. |
| * |
| * On success, returns a newly-allocated RegisterMap. If the map is not |
| * compatible for some reason, or fails to get smaller, this will return NULL. |
| */ |
| static RegisterMap* compressMapDifferential(const RegisterMap* pMap, |
| const Method* meth) |
| { |
| RegisterMap* pNewMap = NULL; |
| int origSize = computeRegisterMapSize(pMap); |
| u1* tmpBuf = NULL; |
| u1* tmpPtr; |
| int addrWidth, regWidth, numEntries; |
| bool debug = false; |
| |
| if (false && |
| strcmp(meth->clazz->descriptor, "Landroid/text/StaticLayout;") == 0 && |
| strcmp(meth->name, "generate") == 0) |
| { |
| debug = true; |
| } |
| |
| u1 format = dvmRegisterMapGetFormat(pMap); |
| switch (format) { |
| case kRegMapFormatCompact8: |
| addrWidth = 1; |
| break; |
| case kRegMapFormatCompact16: |
| addrWidth = 2; |
| break; |
| default: |
| LOGE("ERROR: can't compress map with format=%d\n", format); |
| goto bail; |
| } |
| |
| regWidth = dvmRegisterMapGetRegWidth(pMap); |
| numEntries = dvmRegisterMapGetNumEntries(pMap); |
| |
| if (debug) { |
| LOGI("COMPRESS: %s.%s aw=%d rw=%d ne=%d\n", |
| meth->clazz->descriptor, meth->name, |
| addrWidth, regWidth, numEntries); |
| dumpRegisterMap(pMap, -1); |
| } |
| |
| if (numEntries <= 1) { |
| LOGV("Can't compress map with 0 or 1 entries\n"); |
| goto bail; |
| } |
| |
| /* |
| * We don't know how large the compressed data will be. It's possible |
| * for it to expand and become larger than the original. The header |
| * itself is variable-sized, so we generate everything into a temporary |
| * buffer and then copy it to form-fitting storage once we know how big |
| * it will be (and that it's smaller than the original). |
| * |
| * If we use a size that is equal to the size of the input map plus |
| * a value longer than a single entry can possibly expand to, we need |
| * only check for overflow at the end of each entry. The worst case |
| * for a single line is (1 + <ULEB8 address> + <full copy of vector>). |
| * Addresses are 16 bits, so that's (1 + 3 + regWidth). |
| * |
| * The initial address offset and bit vector will take up less than |
| * or equal to the amount of space required when uncompressed -- large |
| * initial offsets are rejected. |
| */ |
| tmpBuf = (u1*) malloc(origSize + (1 + 3 + regWidth)); |
| if (tmpBuf == NULL) |
| goto bail; |
| |
| tmpPtr = tmpBuf; |
| |
| const u1* mapData = pMap->data; |
| const u1* prevBits; |
| u2 addr, prevAddr; |
| |
| addr = *mapData++; |
| if (addrWidth > 1) |
| addr |= (*mapData++) << 8; |
| |
| if (addr >= 128) { |
| LOGV("Can't compress map with starting address >= 128\n"); |
| goto bail; |
| } |
| |
| /* |
| * Start by writing the initial address and bit vector data. The high |
| * bit of the initial address is used to indicate the required address |
| * width (which the decoder can't otherwise determine without parsing |
| * the compressed data). |
| */ |
| *tmpPtr++ = addr | (addrWidth > 1 ? 0x80 : 0x00); |
| memcpy(tmpPtr, mapData, regWidth); |
| |
| prevBits = mapData; |
| prevAddr = addr; |
| |
| tmpPtr += regWidth; |
| mapData += regWidth; |
| |
| /* |
| * Loop over all following entries. |
| */ |
| int entry; |
| for (entry = 1; entry < numEntries; entry++) { |
| int addrDiff; |
| u1 key; |
| |
| /* |
| * Pull out the address and figure out how to encode it. |
| */ |
| addr = *mapData++; |
| if (addrWidth > 1) |
| addr |= (*mapData++) << 8; |
| |
| if (debug) |
| LOGI(" addr=0x%04x ent=%d (aw=%d)\n", addr, entry, addrWidth); |
| |
| addrDiff = addr - prevAddr; |
| assert(addrDiff > 0); |
| if (addrDiff < 8) { |
| /* small difference, encode in 3 bits */ |
| key = addrDiff -1; /* set 00000AAA */ |
| if (debug) |
| LOGI(" : small %d, key=0x%02x\n", addrDiff, key); |
| } else { |
| /* large difference, output escape code */ |
| key = 0x07; /* escape code for AAA */ |
| if (debug) |
| LOGI(" : large %d, key=0x%02x\n", addrDiff, key); |
| } |
| |
| int numBitsChanged, firstBitChanged, lebSize; |
| |
| lebSize = computeBitDiff(prevBits, mapData, regWidth, |
| &firstBitChanged, &numBitsChanged, NULL); |
| |
| if (debug) { |
| LOGI(" : diff fbc=%d nbc=%d ls=%d (rw=%d)\n", |
| firstBitChanged, numBitsChanged, lebSize, regWidth); |
| } |
| |
| if (numBitsChanged == 0) { |
| /* set B to 1 and CCCC to zero to indicate no bits were changed */ |
| key |= 0x08; |
| if (debug) LOGI(" : no bits changed\n"); |
| } else if (numBitsChanged == 1 && firstBitChanged < 16) { |
| /* set B to 0 and CCCC to the index of the changed bit */ |
| key |= firstBitChanged << 4; |
| if (debug) LOGI(" : 1 low bit changed\n"); |
| } else if (numBitsChanged < 15 && lebSize < regWidth) { |
| /* set B to 1 and CCCC to the number of bits */ |
| key |= 0x08 | (numBitsChanged << 4); |
| if (debug) LOGI(" : some bits changed\n"); |
| } else { |
| /* set B to 1 and CCCC to 0x0f so we store the entire vector */ |
| key |= 0x08 | 0xf0; |
| if (debug) LOGI(" : encode original\n"); |
| } |
| |
| /* |
| * Encode output. Start with the key, follow with the address |
| * diff (if it didn't fit in 3 bits), then the changed bit info. |
| */ |
| *tmpPtr++ = key; |
| if ((key & 0x07) == 0x07) |
| tmpPtr = writeUnsignedLeb128(tmpPtr, addrDiff); |
| |
| if ((key & 0x08) != 0) { |
| int bitCount = key >> 4; |
| if (bitCount == 0) { |
| /* nothing changed, no additional output required */ |
| } else if (bitCount == 15) { |
| /* full vector is most compact representation */ |
| memcpy(tmpPtr, mapData, regWidth); |
| tmpPtr += regWidth; |
| } else { |
| /* write bit indices in LEB128 format */ |
| (void) computeBitDiff(prevBits, mapData, regWidth, |
| NULL, NULL, tmpPtr); |
| tmpPtr += lebSize; |
| } |
| } else { |
| /* single-bit changed, value encoded in key byte */ |
| } |
| |
| prevBits = mapData; |
| prevAddr = addr; |
| mapData += regWidth; |
| |
| /* |
| * See if we've run past the original size. |
| */ |
| if (tmpPtr - tmpBuf >= origSize) { |
| if (debug) { |
| LOGD("Compressed size >= original (%d vs %d): %s.%s\n", |
| tmpPtr - tmpBuf, origSize, |
| meth->clazz->descriptor, meth->name); |
| } |
| goto bail; |
| } |
| } |
| |
| /* |
| * Create a RegisterMap with the contents. |
| * |
| * TODO: consider using a threshold other than merely ">=". We would |
| * get poorer compression but potentially use less native heap space. |
| */ |
| static const int kHeaderSize = offsetof(RegisterMap, data); |
| int newDataSize = tmpPtr - tmpBuf; |
| int newMapSize; |
| |
| newMapSize = kHeaderSize + unsignedLeb128Size(newDataSize) + newDataSize; |
| if (newMapSize >= origSize) { |
| if (debug) { |
| LOGD("Final comp size >= original (%d vs %d): %s.%s\n", |
| newMapSize, origSize, meth->clazz->descriptor, meth->name); |
| } |
| goto bail; |
| } |
| |
| pNewMap = (RegisterMap*) malloc(newMapSize); |
| if (pNewMap == NULL) |
| goto bail; |
| dvmRegisterMapSetFormat(pNewMap, kRegMapFormatDifferential); |
| dvmRegisterMapSetOnHeap(pNewMap, true); |
| dvmRegisterMapSetRegWidth(pNewMap, regWidth); |
| dvmRegisterMapSetNumEntries(pNewMap, numEntries); |
| |
| tmpPtr = pNewMap->data; |
| tmpPtr = writeUnsignedLeb128(tmpPtr, newDataSize); |
| memcpy(tmpPtr, tmpBuf, newDataSize); |
| |
| if (REGISTER_MAP_VERBOSE) { |
| LOGD("Compression successful (%d -> %d) from aw=%d rw=%d ne=%d\n", |
| computeRegisterMapSize(pMap), computeRegisterMapSize(pNewMap), |
| addrWidth, regWidth, numEntries); |
| } |
| |
| bail: |
| free(tmpBuf); |
| return pNewMap; |
| } |
| |
| /* |
| * Toggle the value of the "idx"th bit in "ptr". |
| */ |
| static inline void toggleBit(u1* ptr, int idx) |
| { |
| ptr[idx >> 3] ^= 1 << (idx & 0x07); |
| } |
| |
| /* |
| * Expand a compressed map to an uncompressed form. |
| * |
| * Returns a newly-allocated RegisterMap on success, or NULL on failure. |
| * |
| * TODO: consider using the linear allocator or a custom allocator with |
| * LRU replacement for these instead of the native heap. |
| */ |
| static RegisterMap* uncompressMapDifferential(const RegisterMap* pMap) |
| { |
| RegisterMap* pNewMap = NULL; |
| static const int kHeaderSize = offsetof(RegisterMap, data); |
| u1 format = dvmRegisterMapGetFormat(pMap); |
| RegisterMapFormat newFormat; |
| int regWidth, numEntries, newAddrWidth, newMapSize; |
| |
| if (format != kRegMapFormatDifferential) { |
| LOGE("Not differential (%d)\n", format); |
| goto bail; |
| } |
| |
| regWidth = dvmRegisterMapGetRegWidth(pMap); |
| numEntries = dvmRegisterMapGetNumEntries(pMap); |
| |
| /* get the data size; we can check this at the end */ |
| const u1* srcPtr = pMap->data; |
| int expectedSrcLen = readUnsignedLeb128(&srcPtr); |
| const u1* srcStart = srcPtr; |
| |
| /* get the initial address and the 16-bit address flag */ |
| int addr = *srcPtr & 0x7f; |
| if ((*srcPtr & 0x80) == 0) { |
| newFormat = kRegMapFormatCompact8; |
| newAddrWidth = 1; |
| } else { |
| newFormat = kRegMapFormatCompact16; |
| newAddrWidth = 2; |
| } |
| srcPtr++; |
| |
| /* now we know enough to allocate the new map */ |
| if (REGISTER_MAP_VERBOSE) { |
| LOGI("Expanding to map aw=%d rw=%d ne=%d\n", |
| newAddrWidth, regWidth, numEntries); |
| } |
| newMapSize = kHeaderSize + (newAddrWidth + regWidth) * numEntries; |
| pNewMap = (RegisterMap*) malloc(newMapSize); |
| if (pNewMap == NULL) |
| goto bail; |
| |
| dvmRegisterMapSetFormat(pNewMap, newFormat); |
| dvmRegisterMapSetOnHeap(pNewMap, true); |
| dvmRegisterMapSetRegWidth(pNewMap, regWidth); |
| dvmRegisterMapSetNumEntries(pNewMap, numEntries); |
| |
| /* |
| * Write the start address and initial bits to the new map. |
| */ |
| u1* dstPtr = pNewMap->data; |
| |
| *dstPtr++ = addr & 0xff; |
| if (newAddrWidth > 1) |
| *dstPtr++ = (u1) (addr >> 8); |
| |
| memcpy(dstPtr, srcPtr, regWidth); |
| |
| int prevAddr = addr; |
| const u1* prevBits = dstPtr; /* point at uncompressed data */ |
| |
| dstPtr += regWidth; |
| srcPtr += regWidth; |
| |
| /* |
| * Walk through, uncompressing one line at a time. |
| */ |
| int entry; |
| for (entry = 1; entry < numEntries; entry++) { |
| int addrDiff; |
| u1 key; |
| |
| key = *srcPtr++; |
| |
| /* get the address */ |
| if ((key & 0x07) == 7) { |
| /* address diff follows in ULEB128 */ |
| addrDiff = readUnsignedLeb128(&srcPtr); |
| } else { |
| addrDiff = (key & 0x07) +1; |
| } |
| |
| addr = prevAddr + addrDiff; |
| *dstPtr++ = addr & 0xff; |
| if (newAddrWidth > 1) |
| *dstPtr++ = (u1) (addr >> 8); |
| |
| /* unpack the bits */ |
| if ((key & 0x08) != 0) { |
| int bitCount = (key >> 4); |
| if (bitCount == 0) { |
| /* no bits changed, just copy previous */ |
| memcpy(dstPtr, prevBits, regWidth); |
| } else if (bitCount == 15) { |
| /* full copy of bit vector is present; ignore prevBits */ |
| memcpy(dstPtr, srcPtr, regWidth); |
| srcPtr += regWidth; |
| } else { |
| /* copy previous bits and modify listed indices */ |
| memcpy(dstPtr, prevBits, regWidth); |
| while (bitCount--) { |
| int bitIndex = readUnsignedLeb128(&srcPtr); |
| toggleBit(dstPtr, bitIndex); |
| } |
| } |
| } else { |
| /* copy previous bits and modify the specified one */ |
| memcpy(dstPtr, prevBits, regWidth); |
| |
| /* one bit, from 0-15 inclusive, was changed */ |
| toggleBit(dstPtr, key >> 4); |
| } |
| |
| prevAddr = addr; |
| prevBits = dstPtr; |
| dstPtr += regWidth; |
| } |
| |
| if (dstPtr - (u1*) pNewMap != newMapSize) { |
| LOGE("ERROR: output %d bytes, expected %d\n", |
| dstPtr - (u1*) pNewMap, newMapSize); |
| goto bail; |
| } |
| |
| if (srcPtr - srcStart != expectedSrcLen) { |
| LOGE("ERROR: consumed %d bytes, expected %d\n", |
| srcPtr - srcStart, expectedSrcLen); |
| goto bail; |
| } |
| |
| if (REGISTER_MAP_VERBOSE) { |
| LOGD("Expansion successful (%d -> %d)\n", |
| computeRegisterMapSize(pMap), computeRegisterMapSize(pNewMap)); |
| } |
| |
| return pNewMap; |
| |
| bail: |
| free(pNewMap); |
| return NULL; |
| } |
| |
| |
| /* |
| * =========================================================================== |
| * Just-in-time generation |
| * =========================================================================== |
| */ |
| |
| #if 0 /* incomplete implementation; may be removed entirely in the future */ |
| |
| /* |
| Notes on just-in-time RegisterMap generation |
| |
| Generating RegisterMap tables as part of verification is convenient because |
| we generate most of what we need to know as part of doing the verify. |
| The negative aspect of doing it this way is that we must store the |
| result in the DEX file (if we're verifying ahead of time) or in memory |
| (if verifying during class load) for every concrete non-native method, |
| even if we never actually need the map during a GC. |
| |
| A simple but compact encoding of register map data increases the size of |
| optimized DEX files by about 25%, so size considerations are important. |
| |
| We can instead generate the RegisterMap at the point where it is needed. |
| In a typical application we only need to convert about 2% of the loaded |
| methods, and we can generate type-precise roots reasonably quickly because |
| (a) we know the method has already been verified and hence can make a |
| lot of assumptions, and (b) we don't care what type of object a register |
| holds, just whether or not it holds a reference, and hence can skip a |
| lot of class resolution gymnastics. |
| |
| There are a couple of problems with this approach however. First, to |
| get good performance we really want an implementation that is largely |
| independent from the verifier, which means some duplication of effort. |
| Second, we're dealing with post-dexopt code, which contains "quickened" |
| instructions. We can't process those without either tracking type |
| information (which slows us down) or storing additional data in the DEX |
| file that allows us to reconstruct the original instructions (adds ~5% |
| to the size of the ODEX). |
| |
| |
| Implementation notes... |
| |
| Both type-precise and live-precise information can be generated knowing |
| only whether or not a register holds a reference. We don't need to |
| know what kind of reference or whether the object has been initialized. |
| Not only can we skip many of the fancy steps in the verifier, we can |
| initialize from simpler sources, e.g. the initial registers and return |
| type are set from the "shorty" signature rather than the full signature. |
| |
| The short-term storage needs for just-in-time register map generation can |
| be much lower because we can use a 1-byte SRegType instead of a 4-byte |
| RegType. On the other hand, if we're not doing type-precise analysis |
| in the verifier we only need to store register contents at every branch |
| target, rather than every GC point (which are much more frequent). |
| |
| Whether it happens in the verifier or independently, because this is done |
| with native heap allocations that may be difficult to return to the system, |
| an effort should be made to minimize memory use. |
| */ |
| |
| /* |
| * This is like RegType in the verifier, but simplified. It holds a value |
| * from the reg type enum, or kRegTypeReference. |
| */ |
| typedef u1 SRegType; |
| #define kRegTypeReference kRegTypeMAX |
| |
| /* |
| * We need an extra "pseudo register" to hold the return type briefly. It |
| * can be category 1 or 2, so we need two slots. |
| */ |
| #define kExtraRegs 2 |
| #define RESULT_REGISTER(_insnRegCountPlus) (_insnRegCountPlus - kExtraRegs) |
| |
| /* |
| * Working state. |
| */ |
| typedef struct WorkState { |
| /* |
| * The method we're working on. |
| */ |
| const Method* method; |
| |
| /* |
| * Number of instructions in the method. |
| */ |
| int insnsSize; |
| |
| /* |
| * Number of registers we track for each instruction. This is equal |
| * to the method's declared "registersSize" plus kExtraRegs. |
| */ |
| int insnRegCountPlus; |
| |
| /* |
| * Instruction widths and flags, one entry per code unit. |
| */ |
| InsnFlags* insnFlags; |
| |
| /* |
| * Array of SRegType arrays, one entry per code unit. We only need |
| * to create an entry when an instruction starts at this address. |
| * We can further reduce this to instructions that are GC points. |
| * |
| * We could just go ahead and allocate one per code unit, but for |
| * larger methods that can represent a significant bit of short-term |
| * storage. |
| */ |
| SRegType** addrRegs; |
| |
| /* |
| * A single large alloc, with all of the storage needed for addrRegs. |
| */ |
| SRegType* regAlloc; |
| } WorkState; |
| |
| // fwd |
| static bool generateMap(WorkState* pState, RegisterMap* pMap); |
| static bool analyzeMethod(WorkState* pState); |
| static bool handleInstruction(WorkState* pState, SRegType* workRegs,\ |
| int insnIdx, int* pStartGuess); |
| static void updateRegisters(WorkState* pState, int nextInsn,\ |
| const SRegType* workRegs); |
| |
| |
| /* |
| * Set instruction flags. |
| */ |
| static bool setInsnFlags(WorkState* pState, int* pGcPointCount) |
| { |
| const Method* meth = pState->method; |
| InsnFlags* insnFlags = pState->insnFlags; |
| int insnsSize = pState->insnsSize; |
| const u2* insns = meth->insns; |
| int gcPointCount = 0; |
| int offset; |
| |
| /* set the widths */ |
| if (!dvmComputeCodeWidths(meth, pState->insnFlags, NULL)) |
| return false; |
| |
| /* mark "try" regions and exception handler branch targets */ |
| if (!dvmSetTryFlags(meth, pState->insnFlags)) |
| return false; |
| |
| /* the start of the method is a "branch target" */ |
| dvmInsnSetBranchTarget(insnFlags, 0, true); |
| |
| /* |
| * Run through the instructions, looking for switches and branches. |
| * Mark their targets. |
| * |
| * We don't really need to "check" these instructions -- the verifier |
| * already did that -- but the additional overhead isn't significant |
| * enough to warrant making a second copy of the "Check" function. |
| * |
| * Mark and count GC points while we're at it. |
| */ |
| for (offset = 0; offset < insnsSize; offset++) { |
| static int gcMask = kInstrCanBranch | kInstrCanSwitch | |
| kInstrCanThrow | kInstrCanReturn; |
| u1 opcode = insns[offset] & 0xff; |
| InstructionFlags opFlags = dexGetInstrFlags(gDvm.instrFlags, opcode); |
| |
| if (opFlags & kInstrCanBranch) { |
| if (!dvmCheckBranchTarget(meth, insnFlags, offset, true)) |
| return false; |
| } |
| if (opFlags & kInstrCanSwitch) { |
| if (!dvmCheckSwitchTargets(meth, insnFlags, offset)) |
| return false; |
| } |
| |
| if ((opFlags & gcMask) != 0) { |
| dvmInsnSetGcPoint(pState->insnFlags, offset, true); |
| gcPointCount++; |
| } |
| } |
| |
| *pGcPointCount = gcPointCount; |
| return true; |
| } |
| |
| /* |
| * Generate the register map for a method. |
| * |
| * Returns a pointer to newly-allocated storage. |
| */ |
| RegisterMap* dvmGenerateRegisterMap(const Method* meth) |
| { |
| WorkState* pState = NULL; |
| RegisterMap* pMap = NULL; |
| RegisterMap* result = NULL; |
| SRegType* regPtr; |
| |
| pState = (WorkState*) calloc(1, sizeof(WorkState)); |
| if (pState == NULL) |
| goto bail; |
| |
| pMap = (RegisterMap*) calloc(1, sizeof(RegisterMap)); |
| if (pMap == NULL) |
| goto bail; |
| |
| pState->method = meth; |
| pState->insnsSize = dvmGetMethodInsnsSize(meth); |
| pState->insnRegCountPlus = meth->registersSize + kExtraRegs; |
| |
| pState->insnFlags = calloc(sizeof(InsnFlags), pState->insnsSize); |
| pState->addrRegs = calloc(sizeof(SRegType*), pState->insnsSize); |
| |
| /* |
| * Set flags on instructions, and calculate the number of code units |
| * that happen to be GC points. |
| */ |
| int gcPointCount; |
| if (!setInsnFlags(pState, &gcPointCount)) |
| goto bail; |
| |
| if (gcPointCount == 0) { |
| /* the method doesn't allocate or call, and never returns? unlikely */ |
| LOG_VFY_METH(meth, "Found do-nothing method\n"); |
| goto bail; |
| } |
| |
| pState->regAlloc = (SRegType*) |
| calloc(sizeof(SRegType), pState->insnsSize * gcPointCount); |
| regPtr = pState->regAlloc; |
| |
| /* |
| * For each instruction that is a GC point, set a pointer into the |
| * regAlloc buffer. |
| */ |
| int offset; |
| for (offset = 0; offset < pState->insnsSize; offset++) { |
| if (dvmInsnIsGcPoint(pState->insnFlags, offset)) { |
| pState->addrRegs[offset] = regPtr; |
| regPtr += pState->insnRegCountPlus; |
| } |
| } |
| assert(regPtr - pState->regAlloc == pState->insnsSize * gcPointCount); |
| assert(pState->addrRegs[0] != NULL); |
| |
| /* |
| * Compute the register map. |
| */ |
| if (!generateMap(pState, pMap)) |
| goto bail; |
| |
| /* success */ |
| result = pMap; |
| pMap = NULL; |
| |
| bail: |
| if (pState != NULL) { |
| free(pState->insnFlags); |
| free(pState->addrRegs); |
| free(pState->regAlloc); |
| free(pState); |
| } |
| if (pMap != NULL) |
| dvmFreeRegisterMap(pMap); |
| return result; |
| } |
| |
| /* |
| * Release the storage associated with a RegisterMap. |
| */ |
| void dvmFreeRegisterMap(RegisterMap* pMap) |
| { |
| if (pMap == NULL) |
| return; |
| } |
| |
| |
| /* |
| * Create the RegisterMap using the provided state. |
| */ |
| static bool generateMap(WorkState* pState, RegisterMap* pMap) |
| { |
| bool result = false; |
| |
| /* |
| * Analyze the method and store the results in WorkState. |
| */ |
| if (!analyzeMethod(pState)) |
| goto bail; |
| |
| /* |
| * Convert the analyzed data into a RegisterMap. |
| */ |
| // TODO |
| |
| result = true; |
| |
| bail: |
| return result; |
| } |
| |
| /* |
| * Set the register types for the method arguments. We can pull the values |
| * out of the "shorty" signature. |
| */ |
| static bool setTypesFromSignature(WorkState* pState) |
| { |
| const Method* meth = pState->method; |
| int argReg = meth->registersSize - meth->insSize; /* first arg */ |
| SRegType* pRegs = pState->addrRegs[0]; |
| SRegType* pCurReg = &pRegs[argReg]; |
| const char* ccp; |
| |
| /* |
| * Include "this" pointer, if appropriate. |
| */ |
| if (!dvmIsStaticMethod(meth)) { |
| *pCurReg++ = kRegTypeReference; |
| } |
| |
| ccp = meth->shorty +1; /* skip first byte, which holds return type */ |
| while (*ccp != 0) { |
| switch (*ccp) { |
| case 'L': |
| //case '[': |
| *pCurReg++ = kRegTypeReference; |
| break; |
| case 'Z': |
| *pCurReg++ = kRegTypeBoolean; |
| break; |
| case 'C': |
| *pCurReg++ = kRegTypeChar; |
| break; |
| case 'B': |
| *pCurReg++ = kRegTypeByte; |
| break; |
| case 'I': |
| *pCurReg++ = kRegTypeInteger; |
| break; |
| case 'S': |
| *pCurReg++ = kRegTypeShort; |
| break; |
| case 'F': |
| *pCurReg++ = kRegTypeFloat; |
| break; |
| case 'D': |
| *pCurReg++ = kRegTypeDoubleLo; |
| *pCurReg++ = kRegTypeDoubleHi; |
| break; |
| case 'J': |
| *pCurReg++ = kRegTypeLongLo; |
| *pCurReg++ = kRegTypeLongHi; |
| break; |
| default: |
| assert(false); |
| return false; |
| } |
| } |
| |
| assert(pCurReg - pRegs == meth->insSize); |
| return true; |
| } |
| |
| /* |
| * Find the start of the register set for the specified instruction in |
| * the current method. |
| */ |
| static inline SRegType* getRegisterLine(const WorkState* pState, int insnIdx) |
| { |
| return pState->addrRegs[insnIdx]; |
| } |
| |
| /* |
| * Copy a set of registers. |
| */ |
| static inline void copyRegisters(SRegType* dst, const SRegType* src, |
| int numRegs) |
| { |
| memcpy(dst, src, numRegs * sizeof(SRegType)); |
| } |
| |
| /* |
| * Compare a set of registers. Returns 0 if they match. |
| */ |
| static inline int compareRegisters(const SRegType* src1, const SRegType* src2, |
| int numRegs) |
| { |
| return memcmp(src1, src2, numRegs * sizeof(SRegType)); |
| } |
| |
| /* |
| * Run through the instructions repeatedly until we have exercised all |
| * possible paths. |
| */ |
| static bool analyzeMethod(WorkState* pState) |
| { |
| const Method* meth = pState->method; |
| SRegType workRegs[pState->insnRegCountPlus]; |
| InsnFlags* insnFlags = pState->insnFlags; |
| int insnsSize = pState->insnsSize; |
| int insnIdx, startGuess; |
| bool result = false; |
| |
| /* |
| * Initialize the types of the registers that correspond to method |
| * arguments. |
| */ |
| if (!setTypesFromSignature(pState)) |
| goto bail; |
| |
| /* |
| * Mark the first instruction as "changed". |
| */ |
| dvmInsnSetChanged(insnFlags, 0, true); |
| startGuess = 0; |
| |
| if (true) { |
| IF_LOGI() { |
| char* desc = dexProtoCopyMethodDescriptor(&meth->prototype); |
| LOGI("Now mapping: %s.%s %s (ins=%d regs=%d)\n", |
| meth->clazz->descriptor, meth->name, desc, |
| meth->insSize, meth->registersSize); |
| LOGI(" ------ [0 4 8 12 16 20 24 28 32 36\n"); |
| free(desc); |
| } |
| } |
| |
| /* |
| * Continue until no instructions are marked "changed". |
| */ |
| while (true) { |
| /* |
| * Find the first marked one. Use "startGuess" as a way to find |
| * one quickly. |
| */ |
| for (insnIdx = startGuess; insnIdx < insnsSize; insnIdx++) { |
| if (dvmInsnIsChanged(insnFlags, insnIdx)) |
| break; |
| } |
| |
| if (insnIdx == insnsSize) { |
| if (startGuess != 0) { |
| /* try again, starting from the top */ |
| startGuess = 0; |
| continue; |
| } else { |
| /* all flags are clear */ |
| break; |
| } |
| } |
| |
| /* |
| * We carry the working set of registers from instruction to |
| * instruction. If this address can be the target of a branch |
| * (or throw) instruction, or if we're skipping around chasing |
| * "changed" flags, we need to load the set of registers from |
| * the table. |
| * |
| * Because we always prefer to continue on to the next instruction, |
| * we should never have a situation where we have a stray |
| * "changed" flag set on an instruction that isn't a branch target. |
| */ |
| if (dvmInsnIsBranchTarget(insnFlags, insnIdx)) { |
| SRegType* insnRegs = getRegisterLine(pState, insnIdx); |
| assert(insnRegs != NULL); |
| copyRegisters(workRegs, insnRegs, pState->insnRegCountPlus); |
| |
| } else { |
| #ifndef NDEBUG |
| /* |
| * Sanity check: retrieve the stored register line (assuming |
| * a full table) and make sure it actually matches. |
| */ |
| SRegType* insnRegs = getRegisterLine(pState, insnIdx); |
| if (insnRegs != NULL && |
| compareRegisters(workRegs, insnRegs, |
| pState->insnRegCountPlus) != 0) |
| { |
| char* desc = dexProtoCopyMethodDescriptor(&meth->prototype); |
| LOG_VFY("HUH? workRegs diverged in %s.%s %s\n", |
| meth->clazz->descriptor, meth->name, desc); |
| free(desc); |
| } |
| #endif |
| } |
| |
| /* |
| * Update the register sets altered by this instruction. |
| */ |
| if (!handleInstruction(pState, workRegs, insnIdx, &startGuess)) { |
| goto bail; |
| } |
| |
| dvmInsnSetVisited(insnFlags, insnIdx, true); |
| dvmInsnSetChanged(insnFlags, insnIdx, false); |
| } |
| |
| // TODO - add dead code scan to help validate this code? |
| |
| result = true; |
| |
| bail: |
| return result; |
| } |
| |
| /* |
| * Get a pointer to the method being invoked. |
| * |
| * Returns NULL on failure. |
| */ |
| static Method* getInvokedMethod(const Method* meth, |
| const DecodedInstruction* pDecInsn, MethodType methodType) |
| { |
| Method* resMethod; |
| char* sigOriginal = NULL; |
| |
| /* |
| * Resolve the method. This could be an abstract or concrete method |
| * depending on what sort of call we're making. |
| */ |
| if (methodType == METHOD_INTERFACE) { |
| resMethod = dvmOptResolveInterfaceMethod(meth->clazz, pDecInsn->vB); |
| } else { |
| resMethod = dvmOptResolveMethod(meth->clazz, pDecInsn->vB, methodType); |
| } |
| if (resMethod == NULL) { |
| /* failed; print a meaningful failure message */ |
| DexFile* pDexFile = meth->clazz->pDvmDex->pDexFile; |
| const DexMethodId* pMethodId; |
| const char* methodName; |
| char* methodDesc; |
| const char* classDescriptor; |
| |
| pMethodId = dexGetMethodId(pDexFile, pDecInsn->vB); |
| methodName = dexStringById(pDexFile, pMethodId->nameIdx); |
| methodDesc = dexCopyDescriptorFromMethodId(pDexFile, pMethodId); |
| classDescriptor = dexStringByTypeIdx(pDexFile, pMethodId->classIdx); |
| |
| LOG_VFY("VFY: unable to resolve %s method %u: %s.%s %s\n", |
| dvmMethodTypeStr(methodType), pDecInsn->vB, |
| classDescriptor, methodName, methodDesc); |
| free(methodDesc); |
| return NULL; |
| } |
| |
| return resMethod; |
| } |
| |
| /* |
| * Return the register type for the method. Since we don't care about |
| * the actual type, we can just look at the "shorty" signature. |
| * |
| * Returns kRegTypeUnknown for "void". |
| */ |
| static SRegType getMethodReturnType(const Method* meth) |
| { |
| SRegType type; |
| |
| switch (meth->shorty[0]) { |
| case 'I': |
| type = kRegTypeInteger; |
| break; |
| case 'C': |
| type = kRegTypeChar; |
| break; |
| case 'S': |
| type = kRegTypeShort; |
| break; |
| case 'B': |
| type = kRegTypeByte; |
| break; |
| case 'Z': |
| type = kRegTypeBoolean; |
| break; |
| case 'V': |
| type = kRegTypeUnknown; |
| break; |
| case 'F': |
| type = kRegTypeFloat; |
| break; |
| case 'D': |
| type = kRegTypeDoubleLo; |
| break; |
| case 'J': |
| type = kRegTypeLongLo; |
| break; |
| case 'L': |
| //case '[': |
| type = kRegTypeReference; |
| break; |
| default: |
| /* we verified signature return type earlier, so this is impossible */ |
| assert(false); |
| type = kRegTypeConflict; |
| break; |
| } |
| |
| return type; |
| } |
| |
| /* |
| * Copy a category 1 register. |
| */ |
| static inline void copyRegister1(SRegType* insnRegs, u4 vdst, u4 vsrc) |
| { |
| insnRegs[vdst] = insnRegs[vsrc]; |
| } |
| |
| /* |
| * Copy a category 2 register. Note the source and destination may overlap. |
| */ |
| static inline void copyRegister2(SRegType* insnRegs, u4 vdst, u4 vsrc) |
| { |
| //memmove(&insnRegs[vdst], &insnRegs[vsrc], sizeof(SRegType) * 2); |
| SRegType r1 = insnRegs[vsrc]; |
| SRegType r2 = insnRegs[vsrc+1]; |
| insnRegs[vdst] = r1; |
| insnRegs[vdst+1] = r2; |
| } |
| |
| /* |
| * Set the type of a category 1 register. |
| */ |
| static inline void setRegisterType(SRegType* insnRegs, u4 vdst, SRegType type) |
| { |
| insnRegs[vdst] = type; |
| } |
| |
| /* |
| * Decode the specified instruction and update the register info. |
| */ |
| static bool handleInstruction(WorkState* pState, SRegType* workRegs, |
| int insnIdx, int* pStartGuess) |
| { |
| const Method* meth = pState->method; |
| const u2* insns = meth->insns + insnIdx; |
| InsnFlags* insnFlags = pState->insnFlags; |
| bool result = false; |
| |
| /* |
| * Once we finish decoding the instruction, we need to figure out where |
| * we can go from here. There are three possible ways to transfer |
| * control to another statement: |
| * |
| * (1) Continue to the next instruction. Applies to all but |
| * unconditional branches, method returns, and exception throws. |
| * (2) Branch to one or more possible locations. Applies to branches |
| * and switch statements. |
| * (3) Exception handlers. Applies to any instruction that can |
| * throw an exception that is handled by an encompassing "try" |
| * block. (We simplify this to be any instruction that can |
| * throw any exception.) |
| * |
| * We can also return, in which case there is no successor instruction |
| * from this point. |
| * |
| * The behavior can be determined from the InstrFlags. |
| */ |
| DecodedInstruction decInsn; |
| SRegType entryRegs[pState->insnRegCountPlus]; |
| const int insnRegCountPlus = pState->insnRegCountPlus; |
| bool justSetResult = false; |
| int branchTarget = 0; |
| SRegType tmpType; |
| |
| dexDecodeInstruction(gDvm.instrFormat, insns, &decInsn); |
| const int nextFlags = dexGetInstrFlags(gDvm.instrFlags, decInsn.opCode); |
| |
| /* |
| * Make a copy of the previous register state. If the instruction |
| * throws an exception, we merge *this* into the destination rather |
| * than workRegs, because we don't want the result from the "successful" |
| * code path (e.g. a check-cast that "improves" a type) to be visible |
| * to the exception handler. |
| */ |
| if ((nextFlags & kInstrCanThrow) != 0 && dvmInsnIsInTry(insnFlags, insnIdx)) |
| { |
| copyRegisters(entryRegs, workRegs, insnRegCountPlus); |
| } |
| |
| switch (decInsn.opCode) { |
| case OP_NOP: |
| break; |
| |
| case OP_MOVE: |
| case OP_MOVE_FROM16: |
| case OP_MOVE_16: |
| case OP_MOVE_OBJECT: |
| case OP_MOVE_OBJECT_FROM16: |
| case OP_MOVE_OBJECT_16: |
| copyRegister1(workRegs, decInsn.vA, decInsn.vB); |
| break; |
| case OP_MOVE_WIDE: |
| case OP_MOVE_WIDE_FROM16: |
| case OP_MOVE_WIDE_16: |
| copyRegister2(workRegs, decInsn.vA, decInsn.vB); |
| break; |
| |
| /* |
| * The move-result instructions copy data out of a "pseudo-register" |
| * with the results from the last method invocation. In practice we |
| * might want to hold the result in an actual CPU register, so the |
| * Dalvik spec requires that these only appear immediately after an |
| * invoke or filled-new-array. |
| * |
| * These calls invalidate the "result" register. (This is now |
| * redundant with the reset done below, but it can make the debug info |
| * easier to read in some cases.) |
| */ |
| case OP_MOVE_RESULT: |
| case OP_MOVE_RESULT_OBJECT: |
| copyRegister1(workRegs, decInsn.vA, RESULT_REGISTER(insnRegCountPlus)); |
| break; |
| case OP_MOVE_RESULT_WIDE: |
| copyRegister2(workRegs, decInsn.vA, RESULT_REGISTER(insnRegCountPlus)); |
| break; |
| |
| case OP_MOVE_EXCEPTION: |
| /* |
| * This statement can only appear as the first instruction in an |
| * exception handler (though not all exception handlers need to |
| * have one of these). We verify that as part of extracting the |
| * exception type from the catch block list. |
| */ |
| setRegisterType(workRegs, decInsn.vA, kRegTypeReference); |
| break; |
| |
| case OP_RETURN_VOID: |
| case OP_RETURN: |
| case OP_RETURN_WIDE: |
| case OP_RETURN_OBJECT: |
| break; |
| |
| case OP_CONST_4: |
| case OP_CONST_16: |
| case OP_CONST: |
| /* could be boolean, int, float, or a null reference */ |
| setRegisterType(workRegs, decInsn.vA, |
| dvmDetermineCat1Const((s4)decInsn.vB)); |
| break; |
| case OP_CONST_HIGH16: |
| /* could be boolean, int, float, or a null reference */ |
| setRegisterType(workRegs, decInsn.vA, |
| dvmDetermineCat1Const((s4) decInsn.vB << 16)); |
| break; |
| case OP_CONST_WIDE_16: |
| case OP_CONST_WIDE_32: |
| case OP_CONST_WIDE: |
| case OP_CONST_WIDE_HIGH16: |
| /* could be long or double; default to long and allow conversion */ |
| setRegisterType(workRegs, decInsn.vA, kRegTypeLongLo); |
| break; |
| case OP_CONST_STRING: |
| case OP_CONST_STRING_JUMBO: |
| case OP_CONST_CLASS: |
| setRegisterType(workRegs, decInsn.vA, kRegTypeReference); |
| break; |
| |
| case OP_MONITOR_ENTER: |
| case OP_MONITOR_EXIT: |
| break; |
| |
| case OP_CHECK_CAST: |
| setRegisterType(workRegs, decInsn.vA, kRegTypeReference); |
| break; |
| case OP_INSTANCE_OF: |
| /* result is boolean */ |
| setRegisterType(workRegs, decInsn.vA, kRegTypeBoolean); |
| break; |
| |
| case OP_ARRAY_LENGTH: |
| setRegisterType(workRegs, decInsn.vA, kRegTypeInteger); |
| break; |
| |
| case OP_NEW_INSTANCE: |
| case OP_NEW_ARRAY: |
| /* add the new uninitialized reference to the register ste */ |
| setRegisterType(workRegs, decInsn.vA, kRegTypeReference); |
| break; |
| case OP_FILLED_NEW_ARRAY: |
| case OP_FILLED_NEW_ARRAY_RANGE: |
| setRegisterType(workRegs, RESULT_REGISTER(insnRegCountPlus), |
| kRegTypeReference); |
| justSetResult = true; |
| break; |
| |
| case OP_CMPL_FLOAT: |
| case OP_CMPG_FLOAT: |
| setRegisterType(workRegs, decInsn.vA, kRegTypeBoolean); |
| break; |
| case OP_CMPL_DOUBLE: |
| case OP_CMPG_DOUBLE: |
| setRegisterType(workRegs, decInsn.vA, kRegTypeBoolean); |
| break; |
| case OP_CMP_LONG: |
| setRegisterType(workRegs, decInsn.vA, kRegTypeBoolean); |
| break; |
| |
| case OP_THROW: |
| case OP_GOTO: |
| case OP_GOTO_16: |
| case OP_GOTO_32: |
| case OP_PACKED_SWITCH: |
| case OP_SPARSE_SWITCH: |
| break; |
| |
| case OP_FILL_ARRAY_DATA: |
| break; |
| |
| case OP_IF_EQ: |
| case OP_IF_NE: |
| case OP_IF_LT: |
| case OP_IF_GE: |
| case OP_IF_GT: |
| case OP_IF_LE: |
| case OP_IF_EQZ: |
| case OP_IF_NEZ: |
| case OP_IF_LTZ: |
| case OP_IF_GEZ: |
| case OP_IF_GTZ: |
| case OP_IF_LEZ: |
| break; |
| |
| case OP_AGET: |
| tmpType = kRegTypeInteger; |
| goto aget_1nr_common; |
| case OP_AGET_BOOLEAN: |
| tmpType = kRegTypeBoolean; |
| goto aget_1nr_common; |
| case OP_AGET_BYTE: |
| tmpType = kRegTypeByte; |
| goto aget_1nr_common; |
| case OP_AGET_CHAR: |
| tmpType = kRegTypeChar; |
| goto aget_1nr_common; |
| case OP_AGET_SHORT: |
| tmpType = kRegTypeShort; |
| goto aget_1nr_common; |
| aget_1nr_common: |
| setRegisterType(workRegs, decInsn.vA, tmpType); |
| break; |
| |
| case OP_AGET_WIDE: |
| /* |
| * We know this is either long or double, and we don't really |
| * discriminate between those during verification, so we |
| * call it a long. |
| */ |
| setRegisterType(workRegs, decInsn.vA, kRegTypeLongLo); |
| break; |
| |
| case OP_AGET_OBJECT: |
| setRegisterType(workRegs, decInsn.vA, kRegTypeReference); |
| break; |
| |
| case OP_APUT: |
| case OP_APUT_BOOLEAN: |
| case OP_APUT_BYTE: |
| case OP_APUT_CHAR: |
| case OP_APUT_SHORT: |
| case OP_APUT_WIDE: |
| case OP_APUT_OBJECT: |
| break; |
| |
| case OP_IGET: |
| tmpType = kRegTypeInteger; |
| goto iget_1nr_common; |
| case OP_IGET_BOOLEAN: |
| tmpType = kRegTypeBoolean; |
| goto iget_1nr_common; |
| case OP_IGET_BYTE: |
| tmpType = kRegTypeByte; |
| goto iget_1nr_common; |
| case OP_IGET_CHAR: |
| tmpType = kRegTypeChar; |
| goto iget_1nr_common; |
| case OP_IGET_SHORT: |
| tmpType = kRegTypeShort; |
| goto iget_1nr_common; |
| iget_1nr_common: |
| setRegisterType(workRegs, decInsn.vA, tmpType); |
| break; |
| |
| case OP_IGET_WIDE: |
| setRegisterType(workRegs, decInsn.vA, kRegTypeLongLo); |
| break; |
| |
| case OP_IGET_OBJECT: |
| setRegisterType(workRegs, decInsn.vA, kRegTypeReference); |
| break; |
| |
| case OP_IPUT: |
| case OP_IPUT_BOOLEAN: |
| case OP_IPUT_BYTE: |
| case OP_IPUT_CHAR: |
| case OP_IPUT_SHORT: |
| case OP_IPUT_WIDE: |
| case OP_IPUT_OBJECT: |
| break; |
| |
| case OP_SGET: |
| tmpType = kRegTypeInteger; |
| goto sget_1nr_common; |
| case OP_SGET_BOOLEAN: |
| tmpType = kRegTypeBoolean; |
| goto sget_1nr_common; |
| case OP_SGET_BYTE: |
| tmpType = kRegTypeByte; |
| goto sget_1nr_common; |
| case OP_SGET_CHAR: |
| tmpType = kRegTypeChar; |
| goto sget_1nr_common; |
| case OP_SGET_SHORT: |
| tmpType = kRegTypeShort; |
| goto sget_1nr_common; |
| sget_1nr_common: |
| setRegisterType(workRegs, decInsn.vA, tmpType); |
| break; |
| |
| case OP_SGET_WIDE: |
| setRegisterType(workRegs, decInsn.vA, kRegTypeLongLo); |
| break; |
| |
| case OP_SGET_OBJECT: |
| setRegisterType(workRegs, decInsn.vA, kRegTypeReference); |
| break; |
| |
| case OP_SPUT: |
| case OP_SPUT_BOOLEAN: |
| case OP_SPUT_BYTE: |
| case OP_SPUT_CHAR: |
| case OP_SPUT_SHORT: |
| case OP_SPUT_WIDE: |
| case OP_SPUT_OBJECT: |
| break; |
| |
| case OP_INVOKE_VIRTUAL: |
| case OP_INVOKE_VIRTUAL_RANGE: |
| case OP_INVOKE_SUPER: |
| case OP_INVOKE_SUPER_RANGE: |
| { |
| Method* calledMethod; |
| |
| calledMethod = getInvokedMethod(meth, &decInsn, METHOD_VIRTUAL); |
| if (calledMethod == NULL) |
| goto bail; |
| setRegisterType(workRegs, RESULT_REGISTER(insnRegCountPlus), |
| getMethodReturnType(calledMethod)); |
| justSetResult = true; |
| } |
| break; |
| case OP_INVOKE_DIRECT: |
| case OP_INVOKE_DIRECT_RANGE: |
| { |
| Method* calledMethod; |
| |
| calledMethod = getInvokedMethod(meth, &decInsn, METHOD_DIRECT); |
| if (calledMethod == NULL) |
| goto bail; |
| setRegisterType(workRegs, RESULT_REGISTER(insnRegCountPlus), |
| getMethodReturnType(calledMethod)); |
| justSetResult = true; |
| } |
| break; |
| case OP_INVOKE_STATIC: |
| case OP_INVOKE_STATIC_RANGE: |
| { |
| Method* calledMethod; |
| |
| calledMethod = getInvokedMethod(meth, &decInsn, METHOD_STATIC); |
| if (calledMethod == NULL) |
| goto bail; |
| setRegisterType(workRegs, RESULT_REGISTER(insnRegCountPlus), |
| getMethodReturnType(calledMethod)); |
| justSetResult = true; |
| } |
| break; |
| case OP_INVOKE_INTERFACE: |
| case OP_INVOKE_INTERFACE_RANGE: |
| { |
| Method* absMethod; |
| |
| absMethod = getInvokedMethod(meth, &decInsn, METHOD_INTERFACE); |
| if (absMethod == NULL) |
| goto bail; |
| setRegisterType(workRegs, RESULT_REGISTER(insnRegCountPlus), |
| getMethodReturnType(absMethod)); |
| justSetResult = true; |
| } |
| break; |
| |
| case OP_NEG_INT: |
| case OP_NOT_INT: |
| setRegisterType(workRegs, decInsn.vA, kRegTypeInteger); |
| break; |
| case OP_NEG_LONG: |
| case OP_NOT_LONG: |
| setRegisterType(workRegs, decInsn.vA, kRegTypeLongLo); |
| break; |
| case OP_NEG_FLOAT: |
| setRegisterType(workRegs, decInsn.vA, kRegTypeFloat); |
| break; |
| case OP_NEG_DOUBLE: |
| setRegisterType(workRegs, decInsn.vA, kRegTypeDoubleLo); |
| break; |
| case OP_INT_TO_LONG: |
| setRegisterType(workRegs, decInsn.vA, kRegTypeLongLo); |
| break; |
| case OP_INT_TO_FLOAT: |
| setRegisterType(workRegs, decInsn.vA, kRegTypeFloat); |
| break; |
| case OP_INT_TO_DOUBLE: |
| setRegisterType(workRegs, decInsn.vA, kRegTypeDoubleLo); |
| break; |
| case OP_LONG_TO_INT: |
| setRegisterType(workRegs, decInsn.vA, kRegTypeInteger); |
| break; |
| case OP_LONG_TO_FLOAT: |
| setRegisterType(workRegs, decInsn.vA, kRegTypeFloat); |
| break; |
| case OP_LONG_TO_DOUBLE: |
| setRegisterType(workRegs, decInsn.vA, kRegTypeDoubleLo); |
| break; |
| case OP_FLOAT_TO_INT: |
| setRegisterType(workRegs, decInsn.vA, kRegTypeInteger); |
| break; |
| case OP_FLOAT_TO_LONG: |
| setRegisterType(workRegs, decInsn.vA, kRegTypeLongLo); |
| break; |
| case OP_FLOAT_TO_DOUBLE: |
| setRegisterType(workRegs, decInsn.vA, kRegTypeDoubleLo); |
| break; |
| case OP_DOUBLE_TO_INT: |
| setRegisterType(workRegs, decInsn.vA, kRegTypeInteger); |
| break; |
| case OP_DOUBLE_TO_LONG: |
| setRegisterType(workRegs, decInsn.vA, kRegTypeLongLo); |
| break; |
| case OP_DOUBLE_TO_FLOAT: |
| setRegisterType(workRegs, decInsn.vA, kRegTypeFloat); |
| break; |
| case OP_INT_TO_BYTE: |
| setRegisterType(workRegs, decInsn.vA, kRegTypeByte); |
| break; |
| case OP_INT_TO_CHAR: |
| setRegisterType(workRegs, decInsn.vA, kRegTypeChar); |
| break; |
| case OP_INT_TO_SHORT: |
| setRegisterType(workRegs, decInsn.vA, kRegTypeShort); |
| break; |
| |
| case OP_ADD_INT: |
| case OP_SUB_INT: |
| case OP_MUL_INT: |
| case OP_REM_INT: |
| case OP_DIV_INT: |
| case OP_SHL_INT: |
| case OP_SHR_INT: |
| case OP_USHR_INT: |
| case OP_AND_INT: |
| case OP_OR_INT: |
| case OP_XOR_INT: |
| setRegisterType(workRegs, decInsn.vA, kRegTypeInteger); |
| break; |
| case OP_ADD_LONG: |
| case OP_SUB_LONG: |
| case OP_MUL_LONG: |
| case OP_DIV_LONG: |
| case OP_REM_LONG: |
| case OP_AND_LONG: |
| case OP_OR_LONG: |
| case OP_XOR_LONG: |
| case OP_SHL_LONG: |
| case OP_SHR_LONG: |
| case OP_USHR_LONG: |
| setRegisterType(workRegs, decInsn.vA, kRegTypeLongLo); |
| break; |
| case OP_ADD_FLOAT: |
| case OP_SUB_FLOAT: |
| case OP_MUL_FLOAT: |
| case OP_DIV_FLOAT: |
| case OP_REM_FLOAT: |
| setRegisterType(workRegs, decInsn.vA, kRegTypeFloat); |
| break; |
| case OP_ADD_DOUBLE: |
| case OP_SUB_DOUBLE: |
| case OP_MUL_DOUBLE: |
| case OP_DIV_DOUBLE: |
| case OP_REM_DOUBLE: |
| setRegisterType(workRegs, decInsn.vA, kRegTypeDoubleLo); |
| break; |
| case OP_ADD_INT_2ADDR: |
| case OP_SUB_INT_2ADDR: |
| case OP_MUL_INT_2ADDR: |
| case OP_REM_INT_2ADDR: |
| case OP_SHL_INT_2ADDR: |
| case OP_SHR_INT_2ADDR: |
| case OP_USHR_INT_2ADDR: |
| case OP_AND_INT_2ADDR: |
| case OP_OR_INT_2ADDR: |
| case OP_XOR_INT_2ADDR: |
| case OP_DIV_INT_2ADDR: |
| setRegisterType(workRegs, decInsn.vA, kRegTypeInteger); |
| break; |
| case OP_ADD_LONG_2ADDR: |
| case OP_SUB_LONG_2ADDR: |
| case OP_MUL_LONG_2ADDR: |
| case OP_DIV_LONG_2ADDR: |
| case OP_REM_LONG_2ADDR: |
| case OP_AND_LONG_2ADDR: |
| case OP_OR_LONG_2ADDR: |
| case OP_XOR_LONG_2ADDR: |
| case OP_SHL_LONG_2ADDR: |
| case OP_SHR_LONG_2ADDR: |
| case OP_USHR_LONG_2ADDR: |
| setRegisterType(workRegs, decInsn.vA, kRegTypeLongLo); |
| break; |
| case OP_ADD_FLOAT_2ADDR: |
| case OP_SUB_FLOAT_2ADDR: |
| case OP_MUL_FLOAT_2ADDR: |
| case OP_DIV_FLOAT_2ADDR: |
| case OP_REM_FLOAT_2ADDR: |
| setRegisterType(workRegs, decInsn.vA, kRegTypeFloat); |
| break; |
| case OP_ADD_DOUBLE_2ADDR: |
| case OP_SUB_DOUBLE_2ADDR: |
| case OP_MUL_DOUBLE_2ADDR: |
| case OP_DIV_DOUBLE_2ADDR: |
| case OP_REM_DOUBLE_2ADDR: |
| setRegisterType(workRegs, decInsn.vA, kRegTypeDoubleLo); |
| break; |
| case OP_ADD_INT_LIT16: |
| case OP_RSUB_INT: |
| case OP_MUL_INT_LIT16: |
| case OP_DIV_INT_LIT16: |
| case OP_REM_INT_LIT16: |
| case OP_AND_INT_LIT16: |
| case OP_OR_INT_LIT16: |
| case OP_XOR_INT_LIT16: |
| case OP_ADD_INT_LIT8: |
| case OP_RSUB_INT_LIT8: |
| case OP_MUL_INT_LIT8: |
| case OP_DIV_INT_LIT8: |
| case OP_REM_INT_LIT8: |
| case OP_SHL_INT_LIT8: |
| case OP_SHR_INT_LIT8: |
| case OP_USHR_INT_LIT8: |
| case OP_AND_INT_LIT8: |
| case OP_OR_INT_LIT8: |
| case OP_XOR_INT_LIT8: |
| setRegisterType(workRegs, decInsn.vA, kRegTypeInteger); |
| break; |
| |
| |
| /* |
| * See comments in analysis/CodeVerify.c re: why some of these are |
| * annoying to deal with. It's worse in this implementation, because |
| * we're not keeping any information about the classes held in each |
| * reference register. |
| * |
| * Handling most of these would require retaining the field/method |
| * reference info that we discarded when the instructions were |
| * quickened. This is feasible but not currently supported. |
| */ |
| case OP_EXECUTE_INLINE: |
| case OP_INVOKE_DIRECT_EMPTY: |
| case OP_IGET_QUICK: |
| case OP_IGET_WIDE_QUICK: |
| case OP_IGET_OBJECT_QUICK: |
| case OP_IPUT_QUICK: |
| case OP_IPUT_WIDE_QUICK: |
| case OP_IPUT_OBJECT_QUICK: |
| case OP_INVOKE_VIRTUAL_QUICK: |
| case OP_INVOKE_VIRTUAL_QUICK_RANGE: |
| case OP_INVOKE_SUPER_QUICK: |
| case OP_INVOKE_SUPER_QUICK_RANGE: |
| dvmAbort(); // not implemented, shouldn't be here |
| break; |
| |
| |
| /* these should never appear */ |
| case OP_UNUSED_3E: |
| case OP_UNUSED_3F: |
| case OP_UNUSED_40: |
| case OP_UNUSED_41: |
| case OP_UNUSED_42: |
| case OP_UNUSED_43: |
| case OP_UNUSED_73: |
| case OP_UNUSED_79: |
| case OP_UNUSED_7A: |
| case OP_UNUSED_E3: |
| case OP_UNUSED_E4: |
| case OP_UNUSED_E5: |
| case OP_UNUSED_E6: |
| case OP_UNUSED_E7: |
| case OP_UNUSED_E8: |
| case OP_UNUSED_E9: |
| case OP_UNUSED_EA: |
| case OP_UNUSED_EB: |
| case OP_UNUSED_EC: |
| case OP_UNUSED_ED: |
| case OP_UNUSED_EF: |
| case OP_UNUSED_F1: |
| case OP_UNUSED_FC: |
| case OP_UNUSED_FD: |
| case OP_UNUSED_FE: |
| case OP_UNUSED_FF: |
| dvmAbort(); |
| break; |
| |
| /* |
| * DO NOT add a "default" clause here. Without it the compiler will |
| * complain if an instruction is missing (which is desirable). |
| */ |
| } |
| |
| |
| /* |
| * If we didn't just set the result register, clear it out. This |
| * isn't so important here, but does help ensure that our output matches |
| * the verifier. |
| */ |
| if (!justSetResult) { |
| int reg = RESULT_REGISTER(pState->insnRegCountPlus); |
| workRegs[reg] = workRegs[reg+1] = kRegTypeUnknown; |
| } |
| |
| /* |
| * Handle "continue". Tag the next consecutive instruction. |
| */ |
| if ((nextFlags & kInstrCanContinue) != 0) { |
| int insnWidth = dvmInsnGetWidth(insnFlags, insnIdx); |
| |
| /* |
| * We want to update the registers and set the "changed" flag on the |
| * next instruction (if necessary). We aren't storing register |
| * changes for all addresses, so for non-GC-point targets we just |
| * compare "entry" vs. "work" to see if we've changed anything. |
| */ |
| if (getRegisterLine(pState, insnIdx+insnWidth) != NULL) { |
| updateRegisters(pState, insnIdx+insnWidth, workRegs); |
| } else { |
| /* if not yet visited, or regs were updated, set "changed" */ |
| if (!dvmInsnIsVisited(insnFlags, insnIdx+insnWidth) || |
| compareRegisters(workRegs, entryRegs, |
| pState->insnRegCountPlus) != 0) |
| { |
| dvmInsnSetChanged(insnFlags, insnIdx+insnWidth, true); |
| } |
| } |
| } |
| |
| /* |
| * Handle "branch". Tag the branch target. |
| */ |
| if ((nextFlags & kInstrCanBranch) != 0) { |
| bool isConditional; |
| |
| dvmGetBranchTarget(meth, insnFlags, insnIdx, &branchTarget, |
| &isConditional); |
| assert(isConditional || (nextFlags & kInstrCanContinue) == 0); |
| assert(!isConditional || (nextFlags & kInstrCanContinue) != 0); |
| |
| updateRegisters(pState, insnIdx+branchTarget, workRegs); |
| } |
| |
| /* |
| * Handle "switch". Tag all possible branch targets. |
| */ |
| if ((nextFlags & kInstrCanSwitch) != 0) { |
| int offsetToSwitch = insns[1] | (((s4)insns[2]) << 16); |
| const u2* switchInsns = insns + offsetToSwitch; |
| int switchCount = switchInsns[1]; |
| int offsetToTargets, targ; |
| |
| if ((*insns & 0xff) == OP_PACKED_SWITCH) { |
| /* 0=sig, 1=count, 2/3=firstKey */ |
| offsetToTargets = 4; |
| } else { |
| /* 0=sig, 1=count, 2..count*2 = keys */ |
| assert((*insns & 0xff) == OP_SPARSE_SWITCH); |
| offsetToTargets = 2 + 2*switchCount; |
| } |
| |
| /* verify each switch target */ |
| for (targ = 0; targ < switchCount; targ++) { |
| int offset, absOffset; |
| |
| /* offsets are 32-bit, and only partly endian-swapped */ |
| offset = switchInsns[offsetToTargets + targ*2] | |
| (((s4) switchInsns[offsetToTargets + targ*2 +1]) << 16); |
| absOffset = insnIdx + offset; |
| assert(absOffset >= 0 && absOffset < pState->insnsSize); |
| |
| updateRegisters(pState, absOffset, workRegs); |
| } |
| } |
| |
| /* |
| * Handle instructions that can throw and that are sitting in a |
| * "try" block. (If they're not in a "try" block when they throw, |
| * control transfers out of the method.) |
| */ |
| if ((nextFlags & kInstrCanThrow) != 0 && dvmInsnIsInTry(insnFlags, insnIdx)) |
| { |
| DexFile* pDexFile = meth->clazz->pDvmDex->pDexFile; |
| const DexCode* pCode = dvmGetMethodCode(meth); |
| DexCatchIterator iterator; |
| |
| if (dexFindCatchHandler(&iterator, pCode, insnIdx)) { |
| while (true) { |
| DexCatchHandler* handler = dexCatchIteratorNext(&iterator); |
| if (handler == NULL) |
| break; |
| |
| /* note we use entryRegs, not workRegs */ |
| updateRegisters(pState, handler->address, entryRegs); |
| } |
| } |
| } |
| |
| /* |
| * Update startGuess. Advance to the next instruction of that's |
| * possible, otherwise use the branch target if one was found. If |
| * neither of those exists we're in a return or throw; leave startGuess |
| * alone and let the caller sort it out. |
| */ |
| if ((nextFlags & kInstrCanContinue) != 0) { |
| *pStartGuess = insnIdx + dvmInsnGetWidth(insnFlags, insnIdx); |
| } else if ((nextFlags & kInstrCanBranch) != 0) { |
| /* we're still okay if branchTarget is zero */ |
| *pStartGuess = insnIdx + branchTarget; |
| } |
| |
| assert(*pStartGuess >= 0 && *pStartGuess < pState->insnsSize && |
| dvmInsnGetWidth(insnFlags, *pStartGuess) != 0); |
| |
| result = true; |
| |
| bail: |
| return result; |
| } |
| |
| |
| /* |
| * Merge two SRegType values. |
| * |
| * Sets "*pChanged" to "true" if the result doesn't match "type1". |
| */ |
| static SRegType mergeTypes(SRegType type1, SRegType type2, bool* pChanged) |
| { |
| SRegType result; |
| |
| /* |
| * Check for trivial case so we don't have to hit memory. |
| */ |
| if (type1 == type2) |
| return type1; |
| |
| /* |
| * Use the table if we can, and reject any attempts to merge something |
| * from the table with a reference type. |
| * |
| * The uninitialized table entry at index zero *will* show up as a |
| * simple kRegTypeUninit value. Since this cannot be merged with |
| * anything but itself, the rules do the right thing. |
| */ |
| if (type1 < kRegTypeMAX) { |
| if (type2 < kRegTypeMAX) { |
| result = gDvmMergeTab[type1][type2]; |
| } else { |
| /* simple + reference == conflict, usually */ |
| if (type1 == kRegTypeZero) |
| result = type2; |
| else |
| result = kRegTypeConflict; |
| } |
| } else { |
| if (type2 < kRegTypeMAX) { |
| /* reference + simple == conflict, usually */ |
| if (type2 == kRegTypeZero) |
| result = type1; |
| else |
| result = kRegTypeConflict; |
| } else { |
| /* merging two references */ |
| assert(type1 == type2); |
| result = type1; |
| } |
| } |
| |
| if (result != type1) |
| *pChanged = true; |
| return result; |
| } |
| |
| /* |
| * Control can transfer to "nextInsn". |
| * |
| * Merge the registers from "workRegs" into "addrRegs" at "nextInsn", and |
| * set the "changed" flag on the target address if the registers have changed. |
| */ |
| static void updateRegisters(WorkState* pState, int nextInsn, |
| const SRegType* workRegs) |
| { |
| const Method* meth = pState->method; |
| InsnFlags* insnFlags = pState->insnFlags; |
| const int insnRegCountPlus = pState->insnRegCountPlus; |
| SRegType* targetRegs = getRegisterLine(pState, nextInsn); |
| |
| if (!dvmInsnIsVisitedOrChanged(insnFlags, nextInsn)) { |
| /* |
| * We haven't processed this instruction before, and we haven't |
| * touched the registers here, so there's nothing to "merge". Copy |
| * the registers over and mark it as changed. (This is the only |
| * way a register can transition out of "unknown", so this is not |
| * just an optimization.) |
| */ |
| LOGVV("COPY into 0x%04x\n", nextInsn); |
| copyRegisters(targetRegs, workRegs, insnRegCountPlus); |
| dvmInsnSetChanged(insnFlags, nextInsn, true); |
| } else { |
| /* merge registers, set Changed only if different */ |
| LOGVV("MERGE into 0x%04x\n", nextInsn); |
| bool changed = false; |
| int i; |
| |
| for (i = 0; i < insnRegCountPlus; i++) { |
| targetRegs[i] = mergeTypes(targetRegs[i], workRegs[i], &changed); |
| } |
| |
| if (changed) |
| dvmInsnSetChanged(insnFlags, nextInsn, true); |
| } |
| } |
| |
| #endif /*#if 0*/ |
| |