vm/native/dalvik_system_SamplingProfiler.c - platform/dalvik - Git at Google

 /*
  * 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 },
 };
	/*
	* 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 },
	};