Add tool to help analyze binary size

tools/binary_size/java/src/org/chromium/tools/binary_size/Addr2LineWorkerPool.java

Index: tools/binary_size/java/src/org/chromium/tools/binary_size/Addr2LineWorkerPool.java
diff --git a/tools/binary_size/java/src/org/chromium/tools/binary_size/Addr2LineWorkerPool.java b/tools/binary_size/java/src/org/chromium/tools/binary_size/Addr2LineWorkerPool.java
new file mode 100644
index 0000000000000000000000000000000000000000..4f0e517c79fbfb5a4c1d7c205607af2adac8d3f3
--- /dev/null
+++ b/tools/binary_size/java/src/org/chromium/tools/binary_size/Addr2LineWorkerPool.java
@@ -0,0 +1,467 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+package org.chromium.tools.binary_size;
+
+import java.io.BufferedReader;
+import java.io.File;
+import java.io.IOException;
+import java.io.InputStream;
+import java.io.InputStreamReader;
+import java.io.Reader;
+import java.nio.charset.Charset;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Queue;
+import java.util.Random;
+import java.util.Set;
+import java.util.concurrent.ArrayBlockingQueue;
+import java.util.concurrent.ConcurrentHashMap;
+import java.util.concurrent.ConcurrentLinkedQueue;
+import java.util.concurrent.ConcurrentMap;
+import java.util.concurrent.CountDownLatch;
+import java.util.concurrent.TimeUnit;
+import java.util.concurrent.atomic.AtomicInteger;
+import java.util.concurrent.atomic.AtomicReference;
+
+/**
+ * A pool of workers that run 'addr2line', looking up source locations for
+ * addresses that are fed into the pool via a queue. As address lookups
+ * complete, records are placed onto an output queue.
+ */
+class Addr2LineWorkerPool {
+    private static final Charset sAscii = Charset.forName("US-ASCII");
+    private final Addr2LineWorker[] mWorkers;
+    private final ArrayBlockingQueue<Record> mRecordsIn = new ArrayBlockingQueue<Record>(1000);
+    private final Queue<Record> mRecordsOut = new ConcurrentLinkedQueue<Record>();
+    private final CountDownLatch mCompletionLatch;
+    private final String mAddr2linePath;
+    private final String mLibraryPath;
+    private final boolean mDisambiguate;
+    private final boolean mDedupe;
+    private final String stripLocation;
+    private final ConcurrentMap<Long, Record> mAddressesSeen =
+            new ConcurrentHashMap<Long, Record>(100000, 0.75f, 32);
+    private volatile Map<String,String> mFileLookupTable = null;
+    private final AtomicInteger mDisambiguationSuccessCount = new AtomicInteger(0);
+    private final AtomicInteger mDisambiguationFailureCount = new AtomicInteger(0);
+    private final AtomicInteger mDedupeCount = new AtomicInteger(0);
+
+    /**
+     * These are the suffixes of files that we are potentially interested in
+     * searching during symbol lookups when disambiguation is enabled. Anything
+     * that could theoretically end up being linked into the library file
+     * should be listed here.
+     * <p>
+     * IMPORTANT: All of these should be lowercase. When doing comparisons,
+     * always lowercase the file name before attempting the match.
+     */
+    private static final String[] INTERESTING_FILE_ENDINGS = new String[]{
+            ".c", ".cc", ".h", ".cp", ".cpp", ".cxx", ".c++", ".asm", ".inc", ".s", ".hxx"
+    };
+
+
+    Addr2LineWorkerPool(final int size,
+            final String addr2linePath, final String libraryPath,
+            final boolean disambiguate, final boolean dedupe)
+                    throws IOException {
+        this.mAddr2linePath = addr2linePath;
+        this.mLibraryPath = libraryPath;
+        this.mDisambiguate = disambiguate;
+        this.mDedupe = dedupe;
+
+        // Prepare disambiguation table if necessary. This must be done
+        // before launching the threads in the processing pool for visibility.
+        if (disambiguate) {
+            try {
+                createDisambiguationTable();
+            } catch (IOException e) {
+                throw new RuntimeException("Can't create lookup table", e);
+            }
+        }
+
+        // The library is in, e.g.: src/out/Release
+        // Convert all output paths to be relative to src.
+        // Strip everything up to and including "src/".
+        String canonical = new File(libraryPath).getCanonicalPath();
+        int end = canonical.lastIndexOf("/src/");
+        if (end < 0) {
+            // Shouldn't happen if the library exists.
+            throw new RuntimeException("Bad library path: " + libraryPath +
+                    ". Library is expected to be within a build directory.");
+        }
+        stripLocation = canonical.substring(0, end + "/src/".length());
+
+        mWorkers = new Addr2LineWorker[size];
+        mCompletionLatch = new CountDownLatch(size);
+        for (int x = 0; x < mWorkers.length; x++) {
+            mWorkers[x] = new Addr2LineWorker();
+        }
+    }
+
+    void submit(Record record) throws InterruptedException {
+        mRecordsIn.put(record);
+    }
+
+    void allRecordsSubmitted() {
+        for (Addr2LineWorker worker : mWorkers) {
+            worker.stopIfQueueIsEmpty = true;
+        }
+    }
+
+    boolean await(int amount, TimeUnit unit) throws InterruptedException {
+        return mCompletionLatch.await(amount, unit);
+    }
+
+    /**
+     * @param value the base value
+     * @param percent absolute percentage to jitter by (in the range [0,100])
+     * @return a value that is on average uniformly distributed within
+     * plus or minus <em>percent</em> of the base value.
+     */
+    private static int jitter(final int value, final int percent) {
+        Random r = new Random();
+        int delta = (r.nextBoolean() ? 1 : -1) * r.nextInt((percent * value) / 100);
+        return value + delta;
+    }
+
+
+    /**
+     * A class that encapsulates an addr2line process and the work that it
+     * needs to do.
+     */
+    private class Addr2LineWorker {
+        // Our work queues
+        private final AtomicReference<Process> processRef = new AtomicReference<Process>();
+        private final Thread workerThread;
+        private volatile boolean stopIfQueueIsEmpty = false;
+
+        /**
+         * After this many addresses have been processed, the addr2line process
+         * itself will be recycled. This prevents the addr2line process from
+         * getting too huge, which in turn allows more parallel addr2line
+         * processes to run. There is a balance to be achieved here, as
+         * creating a new addr2line process is very costly. A value of
+         * approximately 2000 appears, empirically, to be a good tradeoff
+         * on a modern machine; memory usage stays tolerable, and good
+         * throughput can be achieved. The value is jittered by +/- 10% so that
+         * the processes don't all restart at once.
+         */
+        private final int processRecycleThreshold = jitter(2000, 10);
+
+        private Addr2LineWorker() throws IOException {
+            this.processRef.set(createAddr2LineProcess());
+            workerThread = new Thread(new Addr2LineTask(), "Addr2Line Worker");
+            workerThread.setDaemon(true);
+            workerThread.start();
+        }
+
+        /**
+         * Builds a new addr2line process for use in this worker.
+         * @return the process
+         * @throws IOException if unable to create the process for any reason
+         */
+        private Process createAddr2LineProcess()
+                throws IOException {
+            ProcessBuilder builder = new ProcessBuilder(mAddr2linePath, "-e", mLibraryPath, "-f");
+            Process process = builder.start();
+            return process;
+        }
+
+        /**
+         * Reads records from the input queue and pipes addresses into
+         * addr2line, using the output to complete the record and pushing
+         * the record into the output queue.
+         */
+        private class Addr2LineTask implements Runnable {
+            @Override
+            public void run() {
+                int processTaskCounter = 0;
+                InputStream inStream = processRef.get().getInputStream();
+                Reader isr = new InputStreamReader(inStream);
+                BufferedReader reader = new BufferedReader(isr);
+                try {
+                    while (true) {
+                        // Check for a task.
+                        final Record record = mRecordsIn.poll(1, TimeUnit.SECONDS);
+                        if (record == null) {
+                            if (stopIfQueueIsEmpty) {
+                                // All tasks have been submitted, so if the
+                                // queue is empty then there is nothing left
+                                // to do and it's ready to shut down
+                                return;
+                            }
+                            continue; // else, queue starvation. Try again.
+                        }
+
+                        // Avoid reprocessing previously-seen symbols if
+                        // deduping is enabled
+                        if (tryDedupe(record)) continue;
+
+                        // Create a new reader if the addr2line process is new
+                        // or has been recycled. A single reader will be used
+                        // for the entirety of the addr2line process' lifetime.
+                        final Process process = processRef.get();
+                        if (inStream == null) {
+                            inStream = process.getInputStream();
+                            isr = new InputStreamReader(inStream);
+                            reader = new BufferedReader(isr);
+                        }
+
+                        // Write the address to stdin of addr2line
+                        process.getOutputStream().write(record.address.getBytes(sAscii));
+                        process.getOutputStream().write('\n');
+                        process.getOutputStream().flush();
+
+                        // Read the answer from addr2line. Example:
+                        // ABGRToYRow_C
+                        // /src/out/Release/../../third_party/libyuv/source/row_common.cc:293
+                        final String name = reader.readLine();
+                        if (name == null || name.isEmpty()) {
+                            stopIfQueueIsEmpty = true;
+                            continue;
+                        }
+
+                        String location = reader.readLine();
+                        if (location == null || location.isEmpty()) {
+                            stopIfQueueIsEmpty = true;
+                            continue;
+                        }
+
+                        record.resolvedSuccessfully = !(
+                                name.equals("??") && location.equals("??:0"));
+
+                        if (record.resolvedSuccessfully) {
+                            // Keep the name from the initial NM dump.
+                            // Some addr2line impls, such as the one for Android
+                            // on ARM, seem to lose data here.
+                            // Note that the location may also include a line
+                            // discriminator, which maps to a part of a line.
+                            // Not currently used.
+                            record.location = processLocation(location);;
+                        }
+
+                        // Check if there is more input on the stream.
+                        // If there is then it is a serious processing
+                        // error, and reading anything else would de-sync
+                        // the input queue from the results being read.
+                        if (inStream.available() > 0) {
+                            throw new IllegalStateException(
+                                    "Alignment mismatch in output from address " + record.address);
+                        }
+
+                        // Track stats and move record to output queue
+                        processTaskCounter++;
+                        mRecordsOut.add(record);
+
+                        // If the addr2line process has done too much work,
+                        // kill it and start a new one to reduce memory
+                        // pressure created by the pool.
+                        if (processTaskCounter >= processRecycleThreshold) {
+                            // Out with the old...
+                            try {
+                                processRef.get().destroy();
+                            } catch (Exception e) {
+                                System.err.println("WARNING: zombie process");
+                                e.printStackTrace();
+                            }
+                            // ... and in with the new!
+                            try {
+                                processRef.set(createAddr2LineProcess());
+                            } catch (IOException e) {
+                                e.printStackTrace();
+                            }
+                            processTaskCounter = 0;
+                            inStream = null; // New readers need to be created next iteration
+                        }
+                    }
+                } catch (Exception e) {
+                    e.printStackTrace();
+                } finally {
+                    try {
+                        // Make an attempt to clean up. If we fail, there is
+                        // nothing we can do beyond this.
+                        processRef.get().destroy();
+                    } catch (Exception e) {
+                        // There's nothing more we can do here.
+                    }
+                    mCompletionLatch.countDown();
+                }
+            }
+        }
+
+        /**
+         * Examines the location from a record and attempts to canonicalize
+         * it and strip off the common source root.
+         * @param location the location to process
+         * @return the canonicalized, stripped location or the original input
+         * string if the location cannot be canonicalized
+         */
+        private String processLocation(String location) {
+            if (location.startsWith("/")) {
+                try {
+                    location = new File(location).getCanonicalPath();
+                } catch (IOException e) {
+                    System.err.println("Unable to canonicalize path: " + location);
+                }
+            } else if (mDisambiguate) {
+                // Ambiguous path (only has the file name)
+                // Try dictionary lookup if that's enabled
+                final int indexOfColon = location.lastIndexOf(':');
+                final String key;
+                final String line;
+                if (indexOfColon != -1) {
+                    key = location.substring(0, indexOfColon);
+                    line = location.substring(indexOfColon + 1);
+                } else {
+                    key = location;
+                    line = null;
+                }
+                final String found = mFileLookupTable.get(key);
+                if (found != null) {
+                    mDisambiguationSuccessCount.incrementAndGet();
+                    location = found;
+                    if (line != null) location = location + ":" + line;
+                } else {
+                    mDisambiguationFailureCount.incrementAndGet();
+                }
+            }
+            if (location.startsWith(stripLocation)) {
+                location = location.substring(stripLocation.length());
+            }
+            return location;
+        }
+
+        /**
+         * Attempts to dedupe a record using a cache of previously-seen
+         * addresses if and only if deduping is enabled.
+         * @param record the record to attempt deduping
+         * @return true if deduplication is enabled and the record references
+         * an address that has already been seen; otherwise false
+         */
+        private boolean tryDedupe(Record record) {
+            if (mDedupe) {
+                long addressLong = Long.parseLong(record.address, 16);
+                Record existing = mAddressesSeen.get(addressLong);
+                if (existing != null) {
+                    if (!existing.size.equals(record.size)) {
+                        System.err.println("WARNING: Deduped address " +
+                                record.address + " has a size mismatch, " +
+                                existing.size + " != " + record.size);
+                    }
+                    mDedupeCount.incrementAndGet();
+                    return true;
+                }
+                if (mAddressesSeen.putIfAbsent(addressLong, record) != null) {
+                    // putIfAbsent is used to ensure that we have
+                    // an accurate dedupeCount; otherwise, two
+                    // workers could insert the same record in
+                    // parallel without realizing that one of them
+                    // was actually a duplicate.
+                    mDedupeCount.incrementAndGet();
+                    return true;
+                }
+            }
+            return false;
+        }
+    }
+
+    // TODO(andrewhayden): Make this less Android-specific
+    private void createDisambiguationTable() throws IOException {
+        // Convert /src/out/Release/lib/*.so -> /src/out/Release
+        final File libraryOutputDirectory = new File(mLibraryPath)
+            .getParentFile().getParentFile().getCanonicalFile();
+
+        // Convert /src/out/Release -> /src
+        final File root = libraryOutputDirectory
+                .getParentFile().getParentFile().getCanonicalFile();
+
+        // There is no code at the root of Chromium.
+        // Ignore all the 'out' directories.
+        mFileLookupTable = new HashMap<String, String>();
+        Set<String> dupes = new HashSet<String>();
+        for (File file : root.listFiles()) {
+            if (file.isDirectory()) {
+                String name = file.getName();
+                if (name.startsWith("out")) {
+                    if (new File(file, "Release").exists() || new File(file, "Debug").exists()) {
+                        // It's an output directory, skip it - except for the
+                        // 'obj' and 'gen' subdirectories that are siblings
+                        // to the library file's parent dir, which is needed.
+                        // Include those at the very end, since they are known.
+                        continue;
+                    }
+                } else if (name.startsWith(".")) {
+                    // Skip dot directories: .git, .svn, etcetera.
+                    continue;
+                }
+                findInterestingFiles(file, dupes);
+            }
+        }
+
+        // Include directories that contain generated resources we are likely
+        // to encounter in the symbol table.
+        findInterestingFiles(new File(libraryOutputDirectory, "gen"), dupes);
+        findInterestingFiles(new File(libraryOutputDirectory, "obj"), dupes);
+
+        // Any duplicates in the filesystem can't be used for disambiguation
+        // because it is not obvious which of the duplicates is the true source.
+        // Therefore, discard all files that have duplicate names.
+        for (String dupe : dupes) {
+            mFileLookupTable.remove(dupe);
+        }
+    }
+
+    // TODO(andrewhayden): Could integrate with build system to know EXACTLY
+    // what is out there. This would avoid the need for the dupes set, which
+    // would make it possible to do much better deduping.
+    private void findInterestingFiles(File directory, Set<String> dupes) {
+        for (File file : directory.listFiles()) {
+            if (file.isDirectory() && file.canRead()) {
+                if (!file.getName().startsWith(".")) {
+                    findInterestingFiles(file, dupes);
+                }
+            } else {
+                String name = file.getName();
+                String normalized = name.toLowerCase();
+                for (String ending : INTERESTING_FILE_ENDINGS) {
+                    if (normalized.endsWith(ending)) {
+                        String other = mFileLookupTable.put(
+                                name, file.getAbsolutePath());
+                        if (other != null) dupes.add(name);
+                    }
+                }
+            }
+        }
+    }
+
+    /**
+     * Polls the output queue for the next record.
+     * @return the next record
+     */
+    Record poll() {
+        return mRecordsOut.poll();
+    }
+
+    /**
+     * @return the number of ambiguous paths successfully disambiguated
+     */
+    int getDisambiguationSuccessCount() {
+        return mDisambiguationSuccessCount.get();
+    }
+
+    /**
+     * @return the number of ambiguous paths that couldn't be disambiguated
+     */
+    int getDisambiguationFailureCount() {
+        return mDisambiguationFailureCount.get();
+    }
+
+    /**
+     * @return the number of symbols deduped
+     */
+    int getDedupeCount() {
+        return mDedupeCount.get();
+    }
+}