/* * 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. */ /** * Native support for dalvik.system.SamplingProfiler */ #define LOG_TAG "SamplingProfiler" #include <cutils/log.h> #include "Dalvik.h" #include "native/InternalNativePriv.h" #include "native/SystemThread.h" // ~20k #define INITIAL_CAPACITY 1024 // ~80k #define MAX_CAPACITY 4096 typedef enum { /** The "event thread". */ EVENT_THREAD, /** Not the "event thread". */ OTHER_THREAD } ThreadType; #define THREAD_TYPE_SIZE (OTHER_THREAD + 1) typedef enum { /** Executing bytecode. */ RUNNING_THREAD, /** Waiting on a lock or VM resource. */ SUSPENDED_THREAD } ThreadState; #define THREAD_STATE_SIZE (SUSPENDED_THREAD + 1) typedef enum { /** This method is in the call stack. */ CALLING_METHOD, /** VM is in this method. */ LEAF_METHOD } MethodState; #define METHOD_STATE_SIZE (LEAF_METHOD + 1) /** SampleSet entry. */ typedef struct { /** Entry key. */ const Method* method; // 4 bytes /** Sample counts for method divided by thread type and state. */ u2 counts[THREAD_TYPE_SIZE][THREAD_STATE_SIZE][METHOD_STATE_SIZE]; // 16B } MethodCount; /** * Set of MethodCount entries. * * Note: If we ever support class unloading, we'll need to make this a GC root * so the methods don't get reclaimed. */ typedef struct { /** Hash collisions. */ int collisions; /** Number of entries in set. */ int size; /** Number of slots. */ int capacity; /** Maximum number of entries this set can hold. 3/4 capacity. */ int maxSize; /** Used to convert a hash to an entry index. */ int mask; /** Entry table. */ MethodCount* entries; /** The event thread. */ Thread* eventThread; } SampleSet; /** * Initializes an empty set with the given capacity (which must be a power of * two). Allocates memory for the entry array which must be freed. */ static SampleSet newSampleSet(int capacity) { SampleSet set; set.collisions = 0; set.size = 0; set.capacity = capacity; set.maxSize = (capacity >> 2) * 3; // 3/4 capacity set.mask = capacity - 1; set.entries = (MethodCount*) calloc(sizeof(MethodCount), capacity); set.eventThread = NULL; return set; } /** Hashes the given pointer. */ static u4 hash(const void* p) { u4 h = (u4) p; // This function treats its argument as seed for a Marsaglia // xorshift random number generator, and produces the next // value. The particular xorshift parameters used here tend to // spread bits downward, to better cope with keys that differ // only in upper bits, which otherwise excessively collide in // small tables. h ^= h >> 11; h ^= h << 7; return h ^ (h >> 16); } /** Doubles capacity of SampleSet. */ static void expand(SampleSet* oldSet) { // TODO: Handle newSet.entries == NULL SampleSet newSet = newSampleSet(oldSet->capacity << 1); LOGI("Expanding sample set capacity to %d.", newSet.capacity); int oldIndex; MethodCount* oldEntries = oldSet->entries; for (oldIndex = 0; oldIndex < oldSet->size; oldIndex++) { MethodCount oldEntry = oldEntries[oldIndex]; if (oldEntry.method != NULL) { // Find the first empty slot. int start = hash(oldEntry.method) & newSet.mask; int i = start; while (newSet.entries[i].method != NULL) { i = (i + 1) & newSet.mask; } // Copy the entry into the empty slot. newSet.entries[i] = oldEntry; newSet.collisions += (i != start); } } free(oldEntries); newSet.size = oldSet->size; newSet.eventThread = oldSet->eventThread; *oldSet = newSet; } /** Increments counter for method in set. */ static void countMethod(SampleSet* set, const Method* method, ThreadType threadType, ThreadState threadState, MethodState methodState) { MethodCount* entries = set->entries; int start = hash(method) & set->mask; int i; for (i = start;; i = (i + 1) & set->mask) { MethodCount* entry = &entries[i]; if (entry->method == method) { // We found an existing entry. entry->counts[threadType][threadState][methodState]++; return; } if (entry->method == NULL) { // Add a new entry. if (set->size < set->maxSize) { entry->method = method; entry->counts[threadType][threadState][methodState] = 1; set->collisions += (i != start); set->size++; } else { if (set->capacity < MAX_CAPACITY) { // The set is 3/4 full. Expand it, and then add the entry. expand(set); countMethod(set, method, threadType, threadState, methodState); } else { // Don't add any more entries. // TODO: Should we replace the LRU entry? } } return; } } } /** Clears all entries from sample set. */ static void clearSampleSet(SampleSet* set) { set->collisions = 0; set->size = 0; memset(set->entries, 0, set->capacity * sizeof(MethodCount)); } /** * Collects a sample from a single, possibly running thread. */ static void sample(SampleSet* set, Thread* thread) { ThreadType threadType = thread == set->eventThread ? EVENT_THREAD : OTHER_THREAD; ThreadState threadState; switch (dvmGetSystemThreadStatus(thread)) { case THREAD_RUNNING: threadState = RUNNING_THREAD; break; case THREAD_NATIVE: return; // Something went wrong. Skip this thread. default: threadState = SUSPENDED_THREAD; // includes PAGING } /* * This code reads the stack concurrently, so it needs to defend against * garbage data that will certainly result from the stack changing out * from under us. */ // Top of the stack. void* stackTop = thread->interpStackStart; void* currentFrame = thread->curFrame; if (currentFrame == NULL) { return; } MethodState methodState = LEAF_METHOD; while (true) { StackSaveArea* saveArea = SAVEAREA_FROM_FP(currentFrame); const Method* method = saveArea->method; // Count the method now. We'll validate later that it's a real Method*. if (method != NULL) { countMethod(set, method, threadType, threadState, methodState); methodState = CALLING_METHOD; } void* callerFrame = saveArea->prevFrame; if (callerFrame == NULL // No more callers. || callerFrame > stackTop // Stack underflow! || callerFrame < currentFrame // Wrong way! ) { break; } currentFrame = callerFrame; } } /** * Collects samples. */ static void Dalvik_dalvik_system_SamplingProfiler_sample(const u4* args, JValue* pResult) { SampleSet* set = (SampleSet*) args[0]; dvmLockThreadList(dvmThreadSelf()); Thread* thread = gDvm.threadList; int sampledThreads = 0; Thread* self = dvmThreadSelf(); while (thread != NULL) { if (thread != self) { sample(set, thread); sampledThreads++; } thread = thread->next; } dvmUnlockThreadList(); RETURN_INT(sampledThreads); } /** * Gets the number of methods in the sample set. */ static void Dalvik_dalvik_system_SamplingProfiler_size(const u4* args, JValue* pResult) { SampleSet* set = (SampleSet*) args[0]; RETURN_INT(set->size); } /** * Gets the number of collisions in the sample set. */ static void Dalvik_dalvik_system_SamplingProfiler_collisions(const u4* args, JValue* pResult) { SampleSet* set = (SampleSet*) args[0]; RETURN_INT(set->collisions); } /** * Returns true if the method is in the given table. */ static bool inTable(const Method* method, const Method* table, int tableLength) { if (tableLength < 1) { return false; } const Method* last = table + (tableLength - 1); // Cast to char* to handle misaligned pointers. return (char*) method >= (char*) table && (char*) method <= (char*) last; } /** Entry in a hash of method counts by class. */ typedef struct mcw { /** Decorated method count. */ MethodCount* methodCount; /** Shortcut to methodCount->method->clazz. */ ClassObject* clazz; /** Pointer to class name that enables us to chop off the first char. */ const char* className; /** Cached string lengths. */ u2 classNameLength; u2 methodNameLength; /** Next method in the same class. */ struct mcw* next; } MethodCountWrapper; /** Returns true if we can trim the first and last chars in the class name. */ static bool isNormalClassName(const char* clazzName, int length) { return (length >= 2) && (clazzName[0] == 'L') && (clazzName[length - 1] == ';'); } /** * Heurtistically guesses whether or not 'method' actually points to a Method * struct. */ static bool isValidMethod(const Method* method) { if (!dvmLinearAllocContains(method, sizeof(Method))) { LOGW("Method* is not in linear allocation table."); return false; } ClassObject* clazz = method->clazz; if (!dvmIsValidObject((Object*) clazz)) { LOGW("method->clazz doesn't point to an object at all."); return false; } if (clazz->obj.clazz != gDvm.classJavaLangClass) { LOGW("method->clazz doesn't point to a ClassObject."); return false; } // No need to validate the tables because we don't actually read them. if (!inTable(method, clazz->directMethods, clazz->directMethodCount) && !inTable(method, clazz->virtualMethods, clazz->virtualMethodCount)) { LOGW("Method not found in associated ClassObject."); return false; } // We're pretty sure at this point that we're looking at a real Method*. // The only alternative is that 'method' points to the middle of a Method // struct and whatever ->clazz resolves to relative to that random // address happens to point to the right ClassObject*. We could mod // the address to ensure that the Method* is aligned as expected, but it's // probably not worth the overhead. return true; } /** Converts slashes to dots in the given class name. */ static void slashesToDots(char* s, int length) { int i; for (i = 0; i < length; i++) { if (s[i] == '/') { s[i] = '.'; } } } /** * Compares class pointers from two method count wrappers. Used in the by-class * hash table. */ static int compareMethodCountClasses(const void* tableItem, const void* looseItem) { const MethodCountWrapper* a = (MethodCountWrapper*) tableItem; const MethodCountWrapper* b = (MethodCountWrapper*) looseItem; u4 serialA = a->clazz->serialNumber; u4 serialB = b->clazz->serialNumber; return serialA == serialB ? 0 : (serialA < serialB ? -1 : 1); } /** * Calculates amount of memory needed for the given class in the final * snapshot and adds the result to arg. */ static int calculateSnapshotEntrySize(void* data, void* arg) { MethodCountWrapper* wrapper = (MethodCountWrapper*) data; const char* className = wrapper->clazz->descriptor; wrapper->classNameLength = strlen(className); if (isNormalClassName(className, wrapper->classNameLength)) { // Trim first & last chars. wrapper->className = className + 1; wrapper->classNameLength -= 2; } else { wrapper->className = className; } // Size of this class entry. int size = 2; // class name size size += wrapper->classNameLength; size += 2; // number of methods in this class do { wrapper->methodNameLength = strlen(wrapper->methodCount->method->name); size += 2; // method name size size += wrapper->methodNameLength; // sample counts size += THREAD_TYPE_SIZE * THREAD_STATE_SIZE * METHOD_STATE_SIZE * 2; wrapper = wrapper->next; } while (wrapper != NULL); int* total = (int*) arg; *total += size; return 0; } /** Writes 2 bytes and increments dest pointer. */ #define writeShort(dest, value) \ do { \ u2 _value = (value); \ *dest++ = (char) (_value >> 8); \ *dest++ = (char) _value; \ } while (0); /** Writes length in 2 bytes and then string, increments dest. */ #define writeString(dest, s, length) \ do { \ u2 _length = (length); \ writeShort(dest, _length); \ memcpy(dest, s, _length); \ dest += _length; \ } while (0); /** * Writes the entry data and advances the pointer (in arg). */ static int writeSnapshotEntry(void* data, void* arg) { MethodCountWrapper* wrapper = (MethodCountWrapper*) data; // We'll copy offset back into offsetPointer at the end. char** offsetPointer = (char**) arg; char* offset = *offsetPointer; // Class name. writeString(offset, wrapper->className, wrapper->classNameLength); slashesToDots(offset - wrapper->classNameLength, wrapper->classNameLength); // Method count. char* methodCountPointer = offset; u2 methodCount = 0; offset += 2; // Method entries. do { // Method name. writeString(offset, wrapper->methodCount->method->name, wrapper->methodNameLength); // Sample counts. u2 (*counts)[THREAD_STATE_SIZE][METHOD_STATE_SIZE] = wrapper->methodCount->counts; int type, threadState, methodState; for (type = 0; type < THREAD_TYPE_SIZE; type++) for (threadState = 0; threadState < THREAD_STATE_SIZE; threadState++) for (methodState = 0; methodState < METHOD_STATE_SIZE; methodState++) writeShort(offset, counts[type][threadState][methodState]); methodCount++; wrapper = wrapper->next; } while (wrapper != NULL); // Go back and write method count. writeShort(methodCountPointer, methodCount); // Increment original pointer. *offsetPointer = offset; return 0; } /** * Captures the collected samples and clears the sample set. */ static void Dalvik_dalvik_system_SamplingProfiler_snapshot(const u4* args, JValue* pResult) { /* * Format: * version # (2 bytes) * # of class entries (2 bytes) * ClassEntry... * * ClassEntry: * class name length (2 bytes) * UTF-8 class name * # of method entries (2 bytes) * MethodEntry... * * MethodEntry: * method name length (2 bytes) * UTF-8 method name * CountsByThreadState (for event thread) * CountsByThreadState (for other threads) * * CountsByThreadState: * CountsByMethodState (for running threads) * CountsByMethodState (for suspended threads) * * CountsByMethodState: * as calling method (2 bytes) * as leaf method (2 bytes) */ SampleSet* set = (SampleSet*) args[0]; if (set->size == 0) { // No data has been captured. RETURN_PTR(NULL); } MethodCountWrapper* wrappers = (MethodCountWrapper*) calloc(set->size, sizeof(MethodCountWrapper)); if (wrappers == NULL) { LOGW("Out of memory."); RETURN_PTR(NULL); } // Method count wrappers by class. HashTable* byClass = dvmHashTableCreate(set->size, NULL); if (byClass == NULL) { free(wrappers); LOGW("Out of memory."); RETURN_PTR(NULL); } // Validate method pointers and index by class. int setIndex; int wrapperIndex; for (setIndex = set->capacity - 1, wrapperIndex = 0; setIndex >= 0 && wrapperIndex < set->size; setIndex--) { MethodCount* mc = &set->entries[setIndex]; const Method* method = mc->method; if (method != NULL && isValidMethod(method)) { MethodCountWrapper* wrapper = &wrappers[wrapperIndex]; wrapper->methodCount = mc; wrapper->clazz = mc->method->clazz; u4 h = hash(wrapper->clazz); MethodCountWrapper* fromTable = dvmHashTableLookup(byClass, h, wrapper, compareMethodCountClasses, true); if (fromTable != wrapper) { // We already have an entry for this class. Link the new entry. wrapper->next = fromTable->next; fromTable->next = wrapper; } wrapperIndex++; } } // Calculate size of snapshot in bytes. int totalSize = 4; // version, # of classes dvmHashForeach(byClass, calculateSnapshotEntrySize, &totalSize); // Write snapshot. ArrayObject* snapshot = dvmAllocPrimitiveArray('B', totalSize, ALLOC_DEFAULT); if (snapshot == NULL) { // Not enough memory to hold snapshot. // TODO: Still clear the set or leave it to try again later? LOGW("Out of memory."); free(wrappers); dvmHashTableFree(byClass); RETURN_PTR(NULL); } char* offset = (char*) snapshot->contents; writeShort(offset, 1); // version writeShort(offset, dvmHashTableNumEntries(byClass)); // class count dvmHashForeach(byClass, writeSnapshotEntry, &offset); // Verify that our size calculation was correct. int actualSize = offset - (char*) snapshot->contents; if (actualSize != totalSize) { LOGE("expected: %d, actual: %d", totalSize, actualSize); abort(); } dvmHashTableFree(byClass); free(wrappers); clearSampleSet(set); dvmReleaseTrackedAlloc((Object*) snapshot, NULL); RETURN_PTR(snapshot); } /** * Allocates native memory. */ static void Dalvik_dalvik_system_SamplingProfiler_allocate(const u4* args, JValue* pResult) { SampleSet* set = (SampleSet*) malloc(sizeof(SampleSet)); *set = newSampleSet(INITIAL_CAPACITY); RETURN_INT((jint) set); } /** * Frees native memory. */ static void Dalvik_dalvik_system_SamplingProfiler_free(const u4* args, JValue* pResult) { SampleSet* set = (SampleSet*) args[0]; free(set->entries); free(set); RETURN_VOID(); } /** * Identifies the event thread. */ static void Dalvik_dalvik_system_SamplingProfiler_setEventThread(const u4* args, JValue* pResult) { SampleSet* set = (SampleSet*) args[0]; Object* eventThread = (Object*) args[1]; // java.lang.Thread Object* vmThread = dvmGetFieldObject(eventThread, gDvm.offJavaLangThread_vmThread); // java.lang.VMThread set->eventThread = dvmGetThreadFromThreadObject(vmThread); RETURN_VOID(); } const DalvikNativeMethod dvm_dalvik_system_SamplingProfiler[] = { { "collisions", "(I)I", Dalvik_dalvik_system_SamplingProfiler_collisions }, { "size", "(I)I", Dalvik_dalvik_system_SamplingProfiler_size }, { "sample", "(I)I", Dalvik_dalvik_system_SamplingProfiler_sample }, { "snapshot", "(I)[B", Dalvik_dalvik_system_SamplingProfiler_snapshot }, { "free", "(I)V", Dalvik_dalvik_system_SamplingProfiler_free }, { "allocate", "()I", Dalvik_dalvik_system_SamplingProfiler_allocate }, { "setEventThread", "(ILjava/lang/Thread;)V", Dalvik_dalvik_system_SamplingProfiler_setEventThread }, { NULL, NULL, NULL }, };