OSDN Git Service

A sampling profiler for Dalvik.
authorBob Lee <crazybob@google.com>
Fri, 31 Jul 2009 01:17:37 +0000 (18:17 -0700)
committerBob Lee <crazybob@google.com>
Thu, 6 Aug 2009 18:22:32 +0000 (11:22 -0700)
libcore/dalvik/src/main/java/dalvik/system/SamplingProfiler.java [new file with mode: 0644]
vm/Android.mk
vm/LinearAlloc.c
vm/LinearAlloc.h
vm/native/InternalNative.c
vm/native/InternalNativePriv.h
vm/native/dalvik_system_SamplingProfiler.c [new file with mode: 0644]

diff --git a/libcore/dalvik/src/main/java/dalvik/system/SamplingProfiler.java b/libcore/dalvik/src/main/java/dalvik/system/SamplingProfiler.java
new file mode 100644 (file)
index 0000000..694df38
--- /dev/null
@@ -0,0 +1,229 @@
+package dalvik.system;
+
+import java.util.logging.Logger;
+import java.io.DataInputStream;
+import java.io.ByteArrayInputStream;
+import java.io.IOException;
+
+/**
+ * A sampling profiler.
+ *
+ * @hide
+ */
+public class SamplingProfiler {
+
+    private static final Logger logger = Logger.getLogger(
+            SamplingProfiler.class.getName());
+
+    /** Pointer to native state. */
+    int pointer = 0;
+
+    /** The thread that collects samples. */
+    Thread samplingThread;
+
+    /** Whether or not the profiler is running. */
+    boolean running = false;
+    int delayPerThread; // ms
+
+    /** Number of samples taken. */
+    int sampleCount = 0;
+
+    /** Total time spent collecting samples. */
+    long totalSampleTime = 0;
+
+    private SamplingProfiler() {}
+
+    /**
+     * Returns true if the profiler is running.
+     */
+    public boolean isRunning() {
+        return running;
+    }
+
+    /**
+     * Starts collecting samples.
+     *
+     * @param threadsPerSecond number of threads to sample per second
+     */
+    public synchronized void start(int threadsPerSecond) {
+        if (threadsPerSecond < 1) {
+            throw new IllegalArgumentException("threadsPerSecond < 1");
+        }
+        if (!running) {
+            logger.info("Starting profiler.");
+            running = true;
+            if (samplingThread == null) {
+                // TODO: Priority?
+                samplingThread = new Thread(new Sampler());
+                samplingThread.setDaemon(true);
+                samplingThread.start();
+            } else {
+                notifyAll();
+            }
+        }
+        delayPerThread = 1000 / threadsPerSecond;
+    }
+
+    /**
+     * Stops sample collection.
+     */
+    public synchronized void stop() {
+        if (running) {
+            logger.info("Stopping profiler.");
+            running = false;
+        }
+    }
+
+    /**
+     * Captures collected samples and clears the sample set. Returns null
+     * if no data has been captured.
+     *
+     * <p>Note: The exact format is not documented because it's not set in
+     * stone yet.
+     */
+    public synchronized byte[] snapshot() {
+        if (pointer == 0 || sampleCount == 0) {
+            return null;
+        }
+
+        int size = size(pointer);
+        int collisions = collisions(pointer);
+
+        long start = System.nanoTime();
+        byte[] bytes = snapshot(pointer);
+        long elapsed = System.nanoTime() - start;
+
+        logger.info("Grabbed snapshot in " + (elapsed / 1000) + "us."
+                + " Samples collected: " + sampleCount
+                + ", Average sample time (per thread): "
+                    + (((totalSampleTime / sampleCount) << 10) / 1000) + "us"
+                + ", Set size: " + size
+                + ", Collisions: " + collisions);
+        sampleCount = 0;
+        totalSampleTime = 0;
+
+        return bytes;
+    }
+
+    /**
+     * Identifies the "event thread". For a user-facing application, this
+     * might be the UI thread. For a background process, this might be the
+     * thread that processes incoming requests.
+     */
+    public synchronized void setEventThread(Thread eventThread) {
+        if (pointer == 0) {
+            pointer = allocate();
+        }
+        setEventThread(pointer, eventThread);
+    }
+
+    /** Collects some data. Returns number of threads sampled. */
+    private static native int sample(int pointer);
+
+    /** Allocates native state. */
+    private static native int allocate();
+
+    /** Gets the number of methods in the sample set. */
+    private static native int size(int pointer);
+
+    /** Gets the number of collisions in the sample set. */
+    private static native int collisions(int pointer);
+
+    /** Captures data. */
+    private static native byte[] snapshot(int pointer);
+
+    /** Identifies the "event thread". */
+    private static native void setEventThread(int pointer, Thread thread);
+
+    /**
+     * Background thread that collects samples.
+     */
+    class Sampler implements Runnable {
+        public void run() {
+            boolean firstSample = true;
+            while (true) {
+                int threadsSampled;
+                synchronized (SamplingProfiler.this) {
+                    if (!running) {
+                        logger.info("Stopped profiler.");
+                        while (!running) {
+                            try {
+                                SamplingProfiler.this.wait();
+                            } catch (InterruptedException e) { /* ignore */ }
+                        }
+                        firstSample = true;
+                    }
+
+                    if (pointer == 0) {
+                        pointer = allocate();
+                    }
+
+                    if (firstSample) {
+                        logger.info("Started profiler.");
+                        firstSample = false;
+                    }
+
+                    long start = System.nanoTime();
+                    threadsSampled = sample(pointer);
+                    long elapsed = System.nanoTime() - start;
+
+                    sampleCount += threadsSampled;
+                    totalSampleTime += elapsed >> 10; // shift avoids overflow.
+                }
+
+                try {
+                    Thread.sleep(delayPerThread * threadsSampled);
+                } catch (InterruptedException e) { /* ignore */ }
+            }
+        }
+    }
+
+    /**
+     * Dumps a snapshot to the log. Useful for debugging.
+     */
+    public static void logSnapshot(byte[] snapshot) {
+        DataInputStream in = new DataInputStream(
+                new ByteArrayInputStream(snapshot));
+        try {
+            int version = in.readUnsignedShort();
+            int classCount = in.readUnsignedShort();
+            StringBuilder sb = new StringBuilder();
+            sb.append("version=").append(version).append(' ')
+                    .append("classes=").append(classCount).append('\n');
+            logger.info(sb.toString());
+            for (int i = 0; i < classCount; i++) {
+                sb = new StringBuilder();
+                sb.append("class ").append(in.readUTF()).append('\n');
+                int methodCount = in.readUnsignedShort();
+                for (int m = 0; m < methodCount; m++) {
+                    sb.append("  ").append(in.readUTF()).append(":\n");
+                    sb.append("    event:\n");
+                    appendCounts(in, sb);
+                    sb.append("    other:\n");
+                    appendCounts(in, sb);
+                }
+                logger.info(sb.toString());
+            }
+        } catch (IOException e) {
+            logger.warning(e.toString());
+        }
+    }
+
+    private static void appendCounts(DataInputStream in, StringBuilder sb)
+            throws IOException {
+        sb.append("      running: ").append(in.readShort()).append('\n');
+        sb.append("      native: ").append(in.readShort()).append('\n');
+        sb.append("      suspended: ").append(in.readShort()).append('\n');
+    }
+
+    /** This will be allocated when the user calls getInstance(). */
+    private static final SamplingProfiler instance = new SamplingProfiler();
+
+    /**
+     * Gets the profiler. The profiler is not running by default. Start it
+     * with {@link #start(int)}.
+     */
+    public static synchronized SamplingProfiler getInstance() {
+        return instance;
+    }
+}
index 48b53af..713c781 100644 (file)
@@ -150,6 +150,7 @@ LOCAL_SRC_FILES := \
        mterp/out/InterpC-portdbg.c.arm \
        native/InternalNative.c \
        native/dalvik_system_DexFile.c \
+       native/dalvik_system_SamplingProfiler.c \
        native/dalvik_system_VMDebug.c \
        native/dalvik_system_VMRuntime.c \
        native/dalvik_system_VMStack.c \
index 5863fb0..8a18af3 100644 (file)
@@ -138,7 +138,7 @@ LinearAllocHdr* dvmLinearAllocCreate(Object* classLoader)
 
     fd = ashmem_create_region("dalvik-LinearAlloc", DEFAULT_MAX_LENGTH);
     if (fd < 0) {
-        LOGE("ashmem LinearAlloc failed %s", strerror(errno)); 
+        LOGE("ashmem LinearAlloc failed %s", strerror(errno));
         free(pHdr);
         return NULL;
     }
@@ -155,7 +155,7 @@ LinearAllocHdr* dvmLinearAllocCreate(Object* classLoader)
 
     close(fd);
 #else /*USE_ASHMEM*/
-    // MAP_ANON is listed as "deprecated" on Linux, 
+    // MAP_ANON is listed as "deprecated" on Linux,
     // but MAP_ANONYMOUS is not defined under Mac OS X.
     pHdr->mapAddr = mmap(NULL, pHdr->mapLength, PROT_READ | PROT_WRITE,
         MAP_PRIVATE | MAP_ANON, -1, 0);
@@ -695,7 +695,7 @@ static void checkAllFree(Object* classLoader)
  * [ Since we currently only have one region, this is pretty simple.  In
  * the future we'll need to traverse a table of class loaders. ]
  */
-bool dvmLinearAllocContains(void* start, size_t length)
+bool dvmLinearAllocContains(const void* start, size_t length)
 {
     LinearAllocHdr* pHdr = getHeader(NULL);
 
index c9a5c08..a390ee3 100644 (file)
@@ -116,6 +116,6 @@ void dvmLinearAllocDump(Object* classLoader);
  * Determine if [start, start+length) is contained in the in-use area of
  * a single LinearAlloc.  The full set of linear allocators is scanned.
  */
-bool dvmLinearAllocContains(void* start, size_t length);
+bool dvmLinearAllocContains(const void* start, size_t length);
 
 #endif /*_DALVIK_LINEARALLOC*/
index 2cad260..735cf96 100644 (file)
@@ -47,6 +47,8 @@ static DalvikNativeClass gDvmNativeMethodSet[] = {
             dvm_java_security_AccessController, 0 },
     { "Ljava/util/concurrent/atomic/AtomicLong;",
             dvm_java_util_concurrent_atomic_AtomicLong, 0 },
+    { "Ldalvik/system/SamplingProfiler;",
+            dvm_dalvik_system_SamplingProfiler, 0 },
     { "Ldalvik/system/VMDebug;",          dvm_dalvik_system_VMDebug, 0 },
     { "Ldalvik/system/DexFile;",          dvm_dalvik_system_DexFile, 0 },
     { "Ldalvik/system/VMRuntime;",        dvm_dalvik_system_VMRuntime, 0 },
index 5e08bf9..abfda6c 100644 (file)
@@ -103,6 +103,7 @@ extern const DalvikNativeMethod dvm_java_lang_reflect_Method[];
 extern const DalvikNativeMethod dvm_java_lang_reflect_Proxy[];
 extern const DalvikNativeMethod dvm_java_security_AccessController[];
 extern const DalvikNativeMethod dvm_java_util_concurrent_atomic_AtomicLong[];
+extern const DalvikNativeMethod dvm_dalvik_system_SamplingProfiler[];
 extern const DalvikNativeMethod dvm_dalvik_system_VMDebug[];
 extern const DalvikNativeMethod dvm_dalvik_system_DexFile[];
 extern const DalvikNativeMethod dvm_dalvik_system_VMRuntime[];
diff --git a/vm/native/dalvik_system_SamplingProfiler.c b/vm/native/dalvik_system_SamplingProfiler.c
new file mode 100644 (file)
index 0000000..13f4f46
--- /dev/null
@@ -0,0 +1,615 @@
+/*
+ * 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"
+
+// ~16k
+#define INITIAL_CAPACITY 1024
+
+// ~64k
+#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,
+    /** In a native method. */
+    NATIVE_THREAD,
+    /** Waiting on a lock or VM resource. */
+    SUSPENDED_THREAD
+} ThreadState;
+
+#define THREAD_STATE_SIZE (SUSPENDED_THREAD + 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]; // 12 bytes
+} 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) {
+    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]++;
+            return;
+        }
+
+        if (entry->method == NULL) {
+            // Add a new entry.
+            if (set->size < set->maxSize) {
+                entry->method = method;
+                entry->counts[threadType][threadState] = 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);
+                } 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 (thread->status) {
+        case THREAD_RUNNING: threadState = RUNNING_THREAD; break;
+        case THREAD_NATIVE: threadState = NATIVE_THREAD; break;
+        default: threadState = SUSPENDED_THREAD;
+    }
+
+    /*
+     * 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;
+    }
+
+    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);
+        }
+
+        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(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;
+        size += THREAD_TYPE_SIZE * THREAD_STATE_SIZE * 2; // sample counts
+        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] = wrapper->methodCount->counts;
+        int type, state;
+        for (type = 0; type < THREAD_TYPE_SIZE; type++)
+            for (state = 0; state < THREAD_STATE_SIZE; state++)
+                writeShort(offset, counts[type][state]);
+
+        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
+     *    Counts (for event thread)
+     *    Counts (for other threads)
+     *
+     *  Counts:
+     *    running count (2 bytes)
+     *    native count (2 bytes)
+     *    suspended count (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];
+        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);
+}
+
+/**
+ * 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 },
+    { "allocate", "()I", Dalvik_dalvik_system_SamplingProfiler_allocate },
+    { "setEventThread", "(ILjava/lang/Thread;)V",
+            Dalvik_dalvik_system_SamplingProfiler_setEventThread },
+    { NULL, NULL, NULL },
+};
\ No newline at end of file