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..fdb92e4596d4cea0862d53fb68255f05f3b58d67
--- /dev/null
+++ b/tools/binary_size/java/src/org/chromium/tools/binary_size/Addr2LineWorkerPool.java
@@ -0,0 +1,395 @@
+// 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.CountDownLatch;
+import java.util.concurrent.TimeUnit;
+import java.util.concurrent.atomic.AtomicInteger;
+import java.util.concurrent.atomic.AtomicReference;
+
+class Addr2LineWorkerPool {
+    private static final Charset ASCII = Charset.forName("US-ASCII");
+    private final Addr2LineWorker[] workers;
+    private final ArrayBlockingQueue<Record> recordsIn = new ArrayBlockingQueue<Record>(1000);
+    private final Queue<Record> recordsOut = new ConcurrentLinkedQueue<Record>();
+    private final CountDownLatch completionLatch;
+    private final String addr2linePath;
+    private final String libraryPath;
+    private final boolean disambiguate;
+    private final boolean dedupe;
+    private final String stripLocation;
+    private final ConcurrentHashMap<Integer, Record> addressesSeen =

[bulach, 2014/01/07 19:38:30]

nit: similar to 31, looks like this can be declared as just a "HashMap"?

also, to make it more generic, perhaps "Long" ?

[Andrew Hayden (chromium.org), 2014/01/08 00:56:45]

It needs to be concurrent because all the worker threads are able to modify it
in parallel, so I'm declaring as ConcurrentMap. I also fixed a race condition
that could have resulted in multiple workers inserting into the cache in
parallel.

+            new ConcurrentHashMap<Integer, Record>(100000, 0.75f, 32);
+    private volatile Map<String,String> fileLookupTable = null;
+    private final AtomicInteger mapLookupSuccessCount = new AtomicInteger(0);
+    private final AtomicInteger mapLookupFailureCount = new AtomicInteger(0);
+    private final AtomicInteger numDeduped = new AtomicInteger(0);
+
+    Addr2LineWorkerPool(final int size,
+            final String addr2linePath, final String libraryPath,
+            final boolean disambiguate, final boolean dedupe)
+                    throws IOException {
+        this.addr2linePath = addr2linePath;
+        this.libraryPath = libraryPath;
+        this.disambiguate = disambiguate;
+        this.dedupe = dedupe;
+
+        // Prepare disambiguation table if necessary. This must be done
+        // before launching the threads in the processing pool for visibility.
+        if (disambiguate) {
+            try {
+                createLookupTable();
+            } catch (IOException e) {
+                throw new RuntimeException("Can't create lookup table", e);
+            }
+        }
+
+        // library is in, e.g.: src/out/Release
+        // We want to convert all output paths to be relative to src,
+        // so what we'll strip is everything up to and including "src/".
+        try {
+            stripLocation = new File(libraryPath).getCanonicalFile()
+                .getParentFile().getParentFile().getParentFile()

[bulach, 2014/01/07 19:38:30]

nit: subtle family tree.. :) can we split the components and then rejoin up to
src/ ?

[Andrew Hayden (chromium.org), 2014/01/08 00:56:45]

How about we take everything up to and including the final instance of "/src/"?
I'll try that.

+                .getParentFile().getCanonicalPath() + "/";
+        } catch (IOException e) {
+            // Shouldn't happen if the library exists.
+            throw new RuntimeException("Bad library path: " + libraryPath
+                    + ". Library is expected to be within a build directory.", e);
+        }
+
+        workers = new Addr2LineWorker[size];
+        completionLatch = new CountDownLatch(size);
+        for (int x = 0; x < workers.length; x++) {
+            workers[x] = new Addr2LineWorker();
+        }
+    }
+
+    void submit(Record record) throws InterruptedException {
+        recordsIn.put(record);
+    }
+
+    void allRecordsSubmitted() {
+        for (Addr2LineWorker worker : workers) {
+            worker.stopIfQueueIsEmpty = true;
+        }
+    }
+
+    boolean await(int amount, TimeUnit unit) throws InterruptedException {
+        return completionLatch.await(amount, unit);
+    }
+
+    /**
+     * @param value the base value
+     * @param percent absolute percentage to jitter by (in the range [0,1])

[bulach, 2014/01/07 19:38:30]

nit: for the purpose here, could do all in integer space, i.e., [0,100], then
(r.nextInt() * percent) / 100 and avoid the cast..

[Andrew Hayden (chromium.org), 2014/01/08 00:56:45]

I changed the code to accept a value between 0 and 100 instead of 0 and 1, but
there's still a cast necessary.

+     * @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 float percent) {
+        Random r = new Random();
+        return (int) (value + ((r.nextBoolean() ? 1f : -1f) * (r.nextFloat() * percent)));
+    }
+
+
+    /**
+     * 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

[bulach, 2014/01/07 19:38:30]

nit: perhaps replace "approximately 2000" with:
... 2000+/-10% (so the process aren't recycled all at once) ...

[Andrew Hayden (chromium.org), 2014/01/08 00:56:45]

Done.

+         * on a modern machine; memory usage stays tolerable, and good
+         * throughput can be achieved.
+         */
+        private final int processRecycleThreshold = jitter(2000,.10f);

[bulach, 2014/01/07 19:38:30]

nit: space after ,
also, I think 10 would be simpler

[Andrew Hayden (chromium.org), 2014/01/08 00:56:45]

Done.

+
+        private Addr2LineWorker() throws IOException {
+            this.processRef.set(createAddr2LineProcess());
+            workerThread = new Thread(new Addr2LineTask(), "read thread");

[bulach, 2014/01/07 19:38:30]

nit: Addr2Line reader thread

[Andrew Hayden (chromium.org), 2014/01/08 00:56:45]

Done.

+            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 final Process createAddr2LineProcess()
+                throws IOException {
+            ProcessBuilder builder = new ProcessBuilder(addr2linePath, "-e", libraryPath, "-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 = recordsIn.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 we are ready to shut down
+                                return;
+                            }
+                            continue; // else, we are just starving. Try again.
+                        }
+
+                        // Check cache
+                        if (dedupe) {
+                            int addressInt = Integer.parseInt(record.address, 16);
+                            Record existing = addressesSeen.get(addressInt);
+                            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);
+                                }
+                                numDeduped.incrementAndGet();
+                                continue;
+                            } else {
+                                addressesSeen.put(addressInt, record);
+                            }
+                        }
+
+                        // If the addr2line process is new (or recycled),
+                        // we have to create new readers.
+                        // We cache these for the lifetime of the addr2line
+                        // process.
+                        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(ASCII));
+                        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 (location.startsWith("/")) {
+                            try {
+                                location = new File(location).getCanonicalPath();
+                            } catch (IOException e) {
+                                System.err.println("Unable to canonicalize path: " + location);
+                            }
+                        } else if (disambiguate) {
+                            // 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 = fileLookupTable.get(key);
+                            if (found != null) {
+                                mapLookupSuccessCount.incrementAndGet();
+                                location = found;
+                                if (line != null) location = location + ":" + line;
+                            } else {
+                                mapLookupFailureCount.incrementAndGet();
+                            }
+                        }
+                        if (location.startsWith(stripLocation)) {
+                            location = location.substring(stripLocation.length());
+                        }
+
+                        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.
+                            // We don't currently care about this.
+                            record.location = location;
+                        }
+
+                        // Check if there is more input on the stream.
+                        // If there is we have made 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++;
+                        recordsOut.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(System.err);
+                            }
+                            // ... 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 {
+                        // ensure process is dead
+                        processRef.get().destroy();
+                    } catch (Exception e) {
+                        // ignore
+                    }
+                    completionLatch.countDown();
+                }
+            }
+        }
+    }
+
+    private void createLookupTable() throws IOException {
+        // Convert /src/out/Release/lib/libchromeview.so -> /src/out/Release
+        final File libraryOutputDirectory = new File(libraryPath)
+            .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.
+        fileLookupTable = new HashMap<String, String>();
+        Set<String> dupes = new HashSet<String>();
+        for (File file : root.listFiles()) {
+            if (file.isDirectory()) {
+                boolean skip = false;
+                if (file.getName().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 we need.
+                        // We'll include those at the very end, since we know
+                        // exactly what they are.
+                        skip = true;
+                    }
+                }

[bulach, 2014/01/07 19:38:30]

nit: perhaps skip everything starting with . as well, like .git, or .svn?

[Andrew Hayden (chromium.org), 2014/01/08 00:56:45]

Done.

+                if (!skip) {
+                    findSourceFiles(file, dupes);
+                }
+            }
+        }
+
+        // Include magic directories.
+        findSourceFiles(new File(libraryOutputDirectory, "gen"), dupes);
+        findSourceFiles(new File(libraryOutputDirectory, "obj"), dupes);
+
+        // Any duplicates in the filesystem can't be used for disambiguation
+        // because we don't know which of them is the true source.
+        // Thus we must discard all duplicates.
+        if (dupes.size() > 0) {

[bulach, 2014/01/07 19:38:30]

nit: could remove this check

[Andrew Hayden (chromium.org), 2014/01/08 00:56:45]

Ha. Yeah I thought dupe removal was going to be fairly evil, then realized it
was just remove. Done :)

+            for (String dupe : dupes) {
+                fileLookupTable.remove(dupe);
+            }
+        }
+    }
+
+    // TODO: Could integrate with build system to know EXACTLY what is out there

[bulach, 2014/01/07 19:38:30]

nit: TODO(andrewhayden)

[Andrew Hayden (chromium.org), 2014/01/08 00:56:45]

Done.

+    // This would avoid the need for the dupes set, which would make it
+    // possible to do much better deduping.
+    private final void findSourceFiles(File directory, Set<String> dupes) {
+        for (File file : directory.listFiles()) {
+            if (file.isDirectory() && file.canRead()) {

[bulach, 2014/01/07 19:38:30]

ditto, exclude anything starting with a .

[Andrew Hayden (chromium.org), 2014/01/08 00:56:45]

Done.

+                findSourceFiles(file, dupes);
+            } else {
+                String name = file.getName();
+                if (name.endsWith(".c") || name.endsWith(".cc")
+                        || name.endsWith(".h") || name.endsWith(".cpp")) {
+                    if (fileLookupTable.put(name, file.getAbsolutePath()) != null) dupes.add(name);
+                }
+            }
+        }
+    }
+
+    Record poll() {
+        return recordsOut.poll();
+    }
+
+    int getMapLookupSuccessCount() {
+        return mapLookupSuccessCount.get();
+    }

[bulach, 2014/01/07 19:38:30]

nit: for consistency, add a \n here and 391 below

[Andrew Hayden (chromium.org), 2014/01/08 00:56:45]

Done.

+    int getMapLookupFailureCount() {
+        return mapLookupFailureCount.get();
+    }
+    int getDedupeCount() {
+        return numDeduped.get();
+    }
+}