| /* |
| * 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 false |
| |
| /* verbose logging */ |
| #define REGISTER_MAP_VERBOSE false |
| |
| //#define REGISTER_MAP_STATS |
| |
| // 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); |
| |
| #ifdef REGISTER_MAP_STATS |
| static void computeMapStats(RegisterMap* pMap, const Method* method); |
| #endif |
| static RegisterMap* compressMapDifferential(const RegisterMap* pMap,\ |
| const Method* meth); |
| static RegisterMap* uncompressMapDifferential(const RegisterMap* pMap); |
| |
| #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 < (int) 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 < (int) vdata->insnsSize; i++) { |
| if (dvmInsnIsGcPoint(vdata->insnFlags, i)) { |
| assert(vdata->registerLines[i].regTypes != NULL); |
| if (format == kRegMapFormatCompact8) { |
| *mapData++ = i; |
| } else /*kRegMapFormatCompact16*/ { |
| *mapData++ = i & 0xff; |
| *mapData++ = i >> 8; |
| } |
| outputTypeVector(vdata->registerLines[i].regTypes, |
| vdata->insnRegCount, mapData); |
| mapData += regWidth; |
| } |
| } |
| |
| LOGV("mapData=%p pMap=%p bufSize=%d\n", mapData, pMap, bufSize); |
| assert(mapData - (const u1*) pMap == bufSize); |
| |
| if (REGISTER_MAP_VERIFY && !verifyMap(vdata, pMap)) |
| goto bail; |
| #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"; |
| 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 RegType* regs = vdata->registerLines[addr].regTypes; |
| 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 = NULL; |
| 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; |
| } |
| assert(data == pMap->data + lineWidth * numEntries); |
| } 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; |
| } |
| } |
| } |
| |
| 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 && dvmTryLockMutex(&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(); |
| newMap = NULL; // make gcc happy |
| } |
| |
| 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. |
| */ |
| #ifdef REGISTER_MAP_STATS |
| static void computeMapStats(RegisterMap* pMap, const Method* method) |
| { |
| 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; |
| } |