blob: 6567dea65bf3ccaa4684a97d4abf85b6c44cdd32 [file] [log] [blame]
/*
* Copyright (C) 2008 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.
*/
/*
* Access the contents of a .dex file.
*/
#include "DexFile.h"
#include "DexOptData.h"
#include "DexProto.h"
#include "DexCatch.h"
#include "Leb128.h"
#include "sha1.h"
#include "ZipArchive.h"
#include <zlib.h>
#include <stdlib.h>
#include <stddef.h>
#include <string.h>
#include <fcntl.h>
#include <errno.h>
/*
* Verifying checksums is good, but it slows things down and causes us to
* touch every page. In the "optimized" world, it doesn't work at all,
* because we rewrite the contents.
*/
static const bool kVerifyChecksum = false;
static const bool kVerifySignature = false;
/* Return the UTF-8 encoded string with the specified string_id index,
* also filling in the UTF-16 size (number of 16-bit code points).*/
const char* dexStringAndSizeById(const DexFile* pDexFile, u4 idx,
u4* utf16Size) {
const DexStringId* pStringId = dexGetStringId(pDexFile, idx);
const u1* ptr = pDexFile->baseAddr + pStringId->stringDataOff;
*utf16Size = readUnsignedLeb128(&ptr);
return (const char*) ptr;
}
/*
* Format an SHA-1 digest for printing. tmpBuf must be able to hold at
* least kSHA1DigestOutputLen bytes.
*/
const char* dvmSHA1DigestToStr(const unsigned char digest[], char* tmpBuf);
/*
* Compute a SHA-1 digest on a range of bytes.
*/
static void dexComputeSHA1Digest(const unsigned char* data, size_t length,
unsigned char digest[])
{
SHA1_CTX context;
SHA1Init(&context);
SHA1Update(&context, data, length);
SHA1Final(digest, &context);
}
/*
* Format the SHA-1 digest into the buffer, which must be able to hold at
* least kSHA1DigestOutputLen bytes. Returns a pointer to the buffer,
*/
static const char* dexSHA1DigestToStr(const unsigned char digest[],char* tmpBuf)
{
static const char hexDigit[] = "0123456789abcdef";
char* cp;
int i;
cp = tmpBuf;
for (i = 0; i < kSHA1DigestLen; i++) {
*cp++ = hexDigit[digest[i] >> 4];
*cp++ = hexDigit[digest[i] & 0x0f];
}
*cp++ = '\0';
assert(cp == tmpBuf + kSHA1DigestOutputLen);
return tmpBuf;
}
/*
* Compute a hash code on a UTF-8 string, for use with internal hash tables.
*
* This may or may not be compatible with UTF-8 hash functions used inside
* the Dalvik VM.
*
* The basic "multiply by 31 and add" approach does better on class names
* than most other things tried (e.g. adler32).
*/
static u4 classDescriptorHash(const char* str)
{
u4 hash = 1;
while (*str != '\0')
hash = hash * 31 + *str++;
return hash;
}
/*
* Add an entry to the class lookup table. We hash the string and probe
* until we find an open slot.
*/
static void classLookupAdd(DexFile* pDexFile, DexClassLookup* pLookup,
int stringOff, int classDefOff, int* pNumProbes)
{
const char* classDescriptor =
(const char*) (pDexFile->baseAddr + stringOff);
const DexClassDef* pClassDef =
(const DexClassDef*) (pDexFile->baseAddr + classDefOff);
u4 hash = classDescriptorHash(classDescriptor);
int mask = pLookup->numEntries-1;
int idx = hash & mask;
/*
* Find the first empty slot. We oversized the table, so this is
* guaranteed to finish.
*/
int probes = 0;
while (pLookup->table[idx].classDescriptorOffset != 0) {
idx = (idx + 1) & mask;
probes++;
}
//if (probes > 1)
// LOGW("classLookupAdd: probes=%d\n", probes);
pLookup->table[idx].classDescriptorHash = hash;
pLookup->table[idx].classDescriptorOffset = stringOff;
pLookup->table[idx].classDefOffset = classDefOff;
*pNumProbes = probes;
}
/*
* Create the class lookup hash table.
*
* Returns newly-allocated storage.
*/
DexClassLookup* dexCreateClassLookup(DexFile* pDexFile)
{
DexClassLookup* pLookup;
int allocSize;
int i, numEntries;
int numProbes, totalProbes, maxProbes;
numProbes = totalProbes = maxProbes = 0;
assert(pDexFile != NULL);
/*
* Using a factor of 3 results in far less probing than a factor of 2,
* but almost doubles the flash storage requirements for the bootstrap
* DEX files. The overall impact on class loading performance seems
* to be minor. We could probably get some performance improvement by
* using a secondary hash.
*/
numEntries = dexRoundUpPower2(pDexFile->pHeader->classDefsSize * 2);
allocSize = offsetof(DexClassLookup, table)
+ numEntries * sizeof(pLookup->table[0]);
pLookup = (DexClassLookup*) calloc(1, allocSize);
if (pLookup == NULL)
return NULL;
pLookup->size = allocSize;
pLookup->numEntries = numEntries;
for (i = 0; i < (int)pDexFile->pHeader->classDefsSize; i++) {
const DexClassDef* pClassDef;
const char* pString;
pClassDef = dexGetClassDef(pDexFile, i);
pString = dexStringByTypeIdx(pDexFile, pClassDef->classIdx);
classLookupAdd(pDexFile, pLookup,
(u1*)pString - pDexFile->baseAddr,
(u1*)pClassDef - pDexFile->baseAddr, &numProbes);
if (numProbes > maxProbes)
maxProbes = numProbes;
totalProbes += numProbes;
}
LOGV("Class lookup: classes=%d slots=%d (%d%% occ) alloc=%d"
" total=%d max=%d\n",
pDexFile->pHeader->classDefsSize, numEntries,
(100 * pDexFile->pHeader->classDefsSize) / numEntries,
allocSize, totalProbes, maxProbes);
return pLookup;
}
/*
* Set up the basic raw data pointers of a DexFile. This function isn't
* meant for general use.
*/
void dexFileSetupBasicPointers(DexFile* pDexFile, const u1* data) {
DexHeader *pHeader = (DexHeader*) data;
pDexFile->baseAddr = data;
pDexFile->pHeader = pHeader;
pDexFile->pStringIds = (const DexStringId*) (data + pHeader->stringIdsOff);
pDexFile->pTypeIds = (const DexTypeId*) (data + pHeader->typeIdsOff);
pDexFile->pFieldIds = (const DexFieldId*) (data + pHeader->fieldIdsOff);
pDexFile->pMethodIds = (const DexMethodId*) (data + pHeader->methodIdsOff);
pDexFile->pProtoIds = (const DexProtoId*) (data + pHeader->protoIdsOff);
pDexFile->pClassDefs = (const DexClassDef*) (data + pHeader->classDefsOff);
pDexFile->pLinkData = (const DexLink*) (data + pHeader->linkOff);
}
/*
* Parse an optimized or unoptimized .dex file sitting in memory. This is
* called after the byte-ordering and structure alignment has been fixed up.
*
* On success, return a newly-allocated DexFile.
*/
DexFile* dexFileParse(const u1* data, size_t length, int flags)
{
DexFile* pDexFile = NULL;
const DexHeader* pHeader;
const u1* magic;
int result = -1;
if (length < sizeof(DexHeader)) {
LOGE("too short to be a valid .dex\n");
goto bail; /* bad file format */
}
pDexFile = (DexFile*) malloc(sizeof(DexFile));
if (pDexFile == NULL)
goto bail; /* alloc failure */
memset(pDexFile, 0, sizeof(DexFile));
/*
* Peel off the optimized header.
*/
if (memcmp(data, DEX_OPT_MAGIC, 4) == 0) {
magic = data;
if (memcmp(magic+4, DEX_OPT_MAGIC_VERS, 4) != 0) {
LOGE("bad opt version (0x%02x %02x %02x %02x)\n",
magic[4], magic[5], magic[6], magic[7]);
goto bail;
}
pDexFile->pOptHeader = (const DexOptHeader*) data;
LOGV("Good opt header, DEX offset is %d, flags=0x%02x\n",
pDexFile->pOptHeader->dexOffset, pDexFile->pOptHeader->flags);
/* parse the optimized dex file tables */
if (!dexParseOptData(data, length, pDexFile))
goto bail;
/* ignore the opt header and appended data from here on out */
data += pDexFile->pOptHeader->dexOffset;
length -= pDexFile->pOptHeader->dexOffset;
if (pDexFile->pOptHeader->dexLength > length) {
LOGE("File truncated? stored len=%d, rem len=%d\n",
pDexFile->pOptHeader->dexLength, (int) length);
goto bail;
}
length = pDexFile->pOptHeader->dexLength;
}
dexFileSetupBasicPointers(pDexFile, data);
pHeader = pDexFile->pHeader;
magic = pHeader->magic;
if (memcmp(magic, DEX_MAGIC, 4) != 0) {
/* not expected */
LOGE("bad magic number (0x%02x %02x %02x %02x)\n",
magic[0], magic[1], magic[2], magic[3]);
goto bail;
}
if (memcmp(magic+4, DEX_MAGIC_VERS, 4) != 0) {
LOGE("bad dex version (0x%02x %02x %02x %02x)\n",
magic[4], magic[5], magic[6], magic[7]);
goto bail;
}
/*
* Verify the checksum(s). This is reasonably quick, but does require
* touching every byte in the DEX file. The base checksum changes after
* byte-swapping and DEX optimization.
*/
if (flags & kDexParseVerifyChecksum) {
u4 adler = dexComputeChecksum(pHeader);
if (adler != pHeader->checksum) {
LOGE("ERROR: bad checksum (%08x vs %08x)\n",
adler, pHeader->checksum);
if (!(flags & kDexParseContinueOnError))
goto bail;
} else {
LOGV("+++ adler32 checksum (%08x) verified\n", adler);
}
const DexOptHeader* pOptHeader = pDexFile->pOptHeader;
if (pOptHeader != NULL) {
adler = dexComputeOptChecksum(pOptHeader);
if (adler != pOptHeader->checksum) {
LOGE("ERROR: bad opt checksum (%08x vs %08x)\n",
adler, pOptHeader->checksum);
if (!(flags & kDexParseContinueOnError))
goto bail;
} else {
LOGV("+++ adler32 opt checksum (%08x) verified\n", adler);
}
}
}
/*
* Verify the SHA-1 digest. (Normally we don't want to do this --
* the digest is used to uniquely identify the original DEX file, and
* can't be computed for verification after the DEX is byte-swapped
* and optimized.)
*/
if (kVerifySignature) {
unsigned char sha1Digest[kSHA1DigestLen];
const int nonSum = sizeof(pHeader->magic) + sizeof(pHeader->checksum) +
kSHA1DigestLen;
dexComputeSHA1Digest(data + nonSum, length - nonSum, sha1Digest);
if (memcmp(sha1Digest, pHeader->signature, kSHA1DigestLen) != 0) {
char tmpBuf1[kSHA1DigestOutputLen];
char tmpBuf2[kSHA1DigestOutputLen];
LOGE("ERROR: bad SHA1 digest (%s vs %s)\n",
dexSHA1DigestToStr(sha1Digest, tmpBuf1),
dexSHA1DigestToStr(pHeader->signature, tmpBuf2));
if (!(flags & kDexParseContinueOnError))
goto bail;
} else {
LOGV("+++ sha1 digest verified\n");
}
}
if (pHeader->fileSize != length) {
LOGE("ERROR: stored file size (%d) != expected (%d)\n",
(int) pHeader->fileSize, (int) length);
if (!(flags & kDexParseContinueOnError))
goto bail;
}
if (pHeader->classDefsSize == 0) {
LOGE("ERROR: DEX file has no classes in it, failing\n");
goto bail;
}
/*
* Success!
*/
result = 0;
bail:
if (result != 0 && pDexFile != NULL) {
dexFileFree(pDexFile);
pDexFile = NULL;
}
return pDexFile;
}
/*
* Free up the DexFile and any associated data structures.
*
* Note we may be called with a partially-initialized DexFile.
*/
void dexFileFree(DexFile* pDexFile)
{
if (pDexFile == NULL)
return;
free(pDexFile);
}
/*
* Look up a class definition entry by descriptor.
*
* "descriptor" should look like "Landroid/debug/Stuff;".
*/
const DexClassDef* dexFindClass(const DexFile* pDexFile,
const char* descriptor)
{
const DexClassLookup* pLookup = pDexFile->pClassLookup;
u4 hash;
int idx, mask;
hash = classDescriptorHash(descriptor);
mask = pLookup->numEntries - 1;
idx = hash & mask;
/*
* Search until we find a matching entry or an empty slot.
*/
while (true) {
int offset;
offset = pLookup->table[idx].classDescriptorOffset;
if (offset == 0)
return NULL;
if (pLookup->table[idx].classDescriptorHash == hash) {
const char* str;
str = (const char*) (pDexFile->baseAddr + offset);
if (strcmp(str, descriptor) == 0) {
return (const DexClassDef*)
(pDexFile->baseAddr + pLookup->table[idx].classDefOffset);
}
}
idx = (idx + 1) & mask;
}
}
/*
* Compute the DEX file checksum for a memory-mapped DEX file.
*/
u4 dexComputeChecksum(const DexHeader* pHeader)
{
const u1* start = (const u1*) pHeader;
uLong adler = adler32(0L, Z_NULL, 0);
const int nonSum = sizeof(pHeader->magic) + sizeof(pHeader->checksum);
return (u4) adler32(adler, start + nonSum, pHeader->fileSize - nonSum);
}
/*
* Compute the size, in bytes, of a DexCode.
*/
size_t dexGetDexCodeSize(const DexCode* pCode)
{
/*
* The catch handler data is the last entry. It has a variable number
* of variable-size pieces, so we need to create an iterator.
*/
u4 handlersSize;
u4 offset;
u4 ui;
if (pCode->triesSize != 0) {
handlersSize = dexGetHandlersSize(pCode);
offset = dexGetFirstHandlerOffset(pCode);
} else {
handlersSize = 0;
offset = 0;
}
for (ui = 0; ui < handlersSize; ui++) {
DexCatchIterator iterator;
dexCatchIteratorInit(&iterator, pCode, offset);
offset = dexCatchIteratorGetEndOffset(&iterator, pCode);
}
const u1* handlerData = dexGetCatchHandlerData(pCode);
//LOGD("+++ pCode=%p handlerData=%p last offset=%d\n",
// pCode, handlerData, offset);
/* return the size of the catch handler + everything before it */
return (handlerData - (u1*) pCode) + offset;
}
/*
* Round up to the next highest power of 2.
*
* Found on http://graphics.stanford.edu/~seander/bithacks.html.
*/
u4 dexRoundUpPower2(u4 val)
{
val--;
val |= val >> 1;
val |= val >> 2;
val |= val >> 4;
val |= val >> 8;
val |= val >> 16;
val++;
return val;
}