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..03d6e5886031917f4e71af6df3eea7a889f86cff
--- /dev/null
+++ b/tools/binary_size/java/src/org/chromium/tools/binary_size/Addr2LineWorkerPool.java
@@ -0,0 +1,419 @@
+// 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;
+
+class Addr2LineWorkerPool {
+    private static final Charset ASCII = Charset.forName("US-ASCII");
+    private final Addr2LineWorker[] workers;

[Peter Beverloo, 2014/01/08 16:06:23]

nit: Java files in Chromium follow the Android coding style guidelines, which
state that private fields need to start with an m (mWorkers). Elsewhere too.

http://source.android.com/source/code-style.html#follow-field-naming-conventions

[Andrew Hayden (chromium.org), 2014/01/08 21:04:10]

I'll refactor at the same time that I fix the python style, in the commit after
your other ctructural/functional comments are addressed.

+    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 ConcurrentMap<Long, Record> addressesSeen =
+            new ConcurrentHashMap<Long, Record>(100000, 0.75f, 32);
+    private volatile Map<String,String> fileLookupTable = null;
+    private final AtomicInteger disambiguationSuccessCount = new AtomicInteger(0);
+    private final AtomicInteger disambiguationFailureCount = new AtomicInteger(0);
+    private final AtomicInteger numDeduped = new AtomicInteger(0);

[Peter Beverloo, 2014/01/08 16:06:23]

s/numDeduped/dedupeCount/ for consistency (most notably with the getter).

[Andrew Hayden (chromium.org), 2014/01/08 21:04:10]

Done.

+
+    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,

[bulach, 2014/01/08 15:04:00]

nit: I had reviewers asking to not use pronouns.. their point is that it's
simpler as:
// Convert all output paths to be relative to src,
// so strip everything up to and including "src/".

[Andrew Hayden (chromium.org), 2014/01/08 21:04:10]

Done.

+        // so what we'll strip is 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.");

[bulach, 2014/01/08 15:04:00]

nit: + operator in the previous line 

[Andrew Hayden (chromium.org), 2014/01/08 21:04:10]

Done.

+        }
+        stripLocation = canonical.substring(0, end + "/src/".length());
+
+        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,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 float percent) {

[bulach, 2014/01/08 15:04:00]

nit: s/float/int/

+        Random r = new Random();
+        int delta = (r.nextBoolean() ? 1 : -1) * r.nextInt((int) (percent / 100f * value));

[bulach, 2014/01/08 15:04:00]

nit: isn't the cast equivalent to just do it in int space?
 ((value * percent) / 100)

[Andrew Hayden (chromium.org), 2014/01/08 21:04:10]

Done.

+        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. We jitter this value by +/- 10% so that

[bulach, 2014/01/08 15:04:00]

nit: ditto about "we".
// Jitter this value by +/-10% so that processes are not restarted all at once.

[Andrew Hayden (chromium.org), 2014/01/08 21:04:10]

Done.

+         * we don't end up with all the processes restarting at once.
+         */
+        private final int processRecycleThreshold = jitter(2000, 10f);
+
+        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 final Process createAddr2LineProcess()

[Peter Beverloo, 2014/01/08 16:06:23]

The "final" here declares that subclasses of Addr2LineWorker can't override this
method, instead of indicating that it returns a "final Process" which I think
you may have meant?  Since there are no subclasses, it doesn't serve any
purpose.

[Andrew Hayden (chromium.org), 2014/01/08 21:04:10]

Old habit. I tend to make things final and open them up as necessary, since it's
always safe to remove the final keyword. I think there used to be (may not be
any longer, I don't know...) performance improvements that the compiler would
make if things were final, since final methods were always safe to inline. But
it doesn't matter here, and I'll remove it.

+                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

[Peter Beverloo, 2014/01/08 16:06:23]

nit: inconsistent "cache" vs. "dedupe" terminology. Also formulate this as a
sentence please :-).

[Andrew Hayden (chromium.org), 2014/01/08 21:04:10]

Done.

+                        if (dedupe) {
+                            long addressLong = Long.parseLong(record.address, 16);
+                            Record existing = addressesSeen.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);
+                                }
+                                numDeduped.incrementAndGet();
+                                continue;
+                            } else {

[bulach, 2014/01/08 15:04:00]

nit: the previous "if" will always continue, so can remove this else and
unindent the following block.

[Andrew Hayden (chromium.org), 2014/01/08 21:04:10]

Done.

+                                if (addressesSeen.putIfAbsent(addressLong, record) != null) {

[Peter Beverloo, 2014/01/08 16:06:23]

Am I missing some subtlety of putIfAbsent here, or can we avoid the lookup by
just using put?  We check that |record| isn't null on line 169, and the if
clause on line 183 would return true of |addressLong| already had a record.  It
should therefore always be absent here.

[Andrew Hayden (chromium.org), 2014/01/08 21:04:10]

We could but the dedupe count could then be incorrect. It's a race on the first
time we insert into the deduplication cache: if two workers both add it with
put, neither will count the dedupe when in reality one of them should (even
though it may have done extraneous work).

Since this is non-obvious I'll add a comment to this effect. This was a bug I
fixed due to marcus' previous comments...

+                                    numDeduped.incrementAndGet();
+                                    continue;
+                                }
+                            }
+                        }
+
+                        // If the addr2line process is new (or recycled),

[Peter Beverloo, 2014/01/08 16:06:23]

nit: Why the odd character offset for line breaks in this comment?  Also modify
this given Marcus' pronouns comment.

"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."

[Andrew Hayden (chromium.org), 2014/01/08 21:04:10]

I ocassionally start new sentences on their own lines. Anyhow, changed. I also
nuked the pronoun "we" from this entire file.

+                        // 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;
+                        }

[Peter Beverloo, 2014/01/08 16:06:23]

This method is very long, we should try to split it up.  Can we perhaps extract
lines 210-228 (perhaps even 199-228) to a separate method which deals with
communicating with the process?

[Andrew Hayden (chromium.org), 2014/01/08 21:04:10]

I have pulled out two chunks: deduplication and location processing. This cuts
about half the method away.

+
+                        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) {
+                                disambiguationSuccessCount.incrementAndGet();
+                                location = found;
+                                if (line != null) location = location + ":" + line;
+                            } else {
+                                disambiguationFailureCount.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");

[Peter Beverloo, 2014/01/08 16:06:23]

s/warning/WARNING/ to match line 185.

+                                e.printStackTrace(System.err);
+                            }
+                            // ... and in with the new!
+                            try {
+                                processRef.set(createAddr2LineProcess());
+                            } catch (IOException e) {
+                                e.printStackTrace();

[Peter Beverloo, 2014/01/08 16:06:23]

Why do we write the Exception above (line 297) to STDERR, but the ones on lines
303 and 310 to STDOUT?

[Andrew Hayden (chromium.org), 2014/01/08 21:04:10]

Whoops. Actually, the default with no argument passed is stderr, so I removed to
unnecessary passing of System.err. They all should go to System.err

+                            }
+                            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

[Peter Beverloo, 2014/01/08 16:06:23]

nit: Clarify why it's ok to ignore this. An empty catch {} statement already
implies that we're ignoring it.

[Andrew Hayden (chromium.org), 2014/01/08 21:04:10]

Added comments.

+                    }
+                    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();

[Peter Beverloo, 2014/01/08 16:06:23]

This is rather hard-coded for usage on Android. Are the libraries we're
interested in *always* in src/out/{Debug,Release}/lib/?

[Andrew Hayden (chromium.org), 2014/01/08 21:04:10]

Added TODO. It's not clear to me how else to do this without a fair bit of work
to add a command line parameter used specifically to set the directory to be
processed as part of deduplication.

+
+        // 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.

[Peter Beverloo, 2014/01/08 16:06:23]

nit: Sentences start with capitals.

[Andrew Hayden (chromium.org), 2014/01/08 21:04:10]

Done.

+        fileLookupTable = new HashMap<String, String>();
+        Set<String> dupes = new HashSet<String>();
+        for (File file : root.listFiles()) {
+            if (file.isDirectory()) {
+                boolean skip = false;
+                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 we need.
+                        // We'll include those at the very end, since we know
+                        // exactly what they are.
+                        skip = true;

[Peter Beverloo, 2014/01/08 16:06:23]

Rather than using |skip| here, you can just use the continue statement.  That
would also allow you to get rid of one level of nesting (the if-clause on line
338).

[Andrew Hayden (chromium.org), 2014/01/08 21:04:10]

Done.

+                    }
+                } else if (name.startsWith(".")) {
+                    // Skip things like .git, .svn, ...

[Peter Beverloo, 2014/01/08 16:06:23]

micro nit: "Skip directories such as .git, .svn, etcetera." feels a bit less
informal.

[Andrew Hayden (chromium.org), 2014/01/08 21:04:10]

Done.

+                    skip = true;
+                }
+                if (!skip) {
+                    findSourceFiles(file, dupes);
+                }
+            }
+        }
+
+        // Include magic directories.

[Peter Beverloo, 2014/01/08 16:06:23]

nit: "Include directories which are likely to contain generated source files."?

[Andrew Hayden (chromium.org), 2014/01/08 21:04:10]

Done.

+        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.
+        for (String dupe : dupes) {
+            fileLookupTable.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 final void findSourceFiles(File directory, Set<String> dupes) {
+        for (File file : directory.listFiles()) {
+            if (file.isDirectory() && file.canRead()) {
+                if (!file.getName().startsWith(".")) {
+                    findSourceFiles(file, dupes);
+                }
+            } else {
+                String name = file.getName();
+                if (name.endsWith(".c") || name.endsWith(".cc")
+                        || name.endsWith(".h") || name.endsWith(".cpp")) {

[Peter Beverloo, 2014/01/08 16:06:23]

Does it help to include assembly files here (.asm and .S), a few of which are
scattered throughout the source code?

[Andrew Hayden (chromium.org), 2014/01/08 21:04:10]

I don't know, but I'm not opposed. A bit of grepping and googling has yielded a
few more likely candidates that I've added:

private static final String[] INTERESTING_FILE_ENDINGS = new String[]{
    ".c", ".cc", ".h", ".cp", ".cpp", ".cxx", ".c++", ".asm", ".inc", ".s",
".hxx"
};

Sadly this didn't make any difference as far as I can tell.

+                    if (fileLookupTable.put(name, file.getAbsolutePath()) != null) dupes.add(name);
+                }
+            }
+        }
+    }
+
+    /**
+     * Polls the output queue for the next record.
+     * @return the next record
+     */
+    Record poll() {
+        return recordsOut.poll();
+    }
+
+    /**
+     * @return the number of ambiguous paths successfully disambiguated
+     */
+    int getDisambiguationSuccessCount() {
+        return disambiguationSuccessCount.get();
+    }
+
+    /**
+     * @return the number of ambiguous paths that couldn't be disambiguated
+     */
+    int getDisambiguationFailureCount() {
+        return disambiguationFailureCount.get();
+    }
+
+    /**
+     * @return the number of symbols deduped
+     */
+    int getDedupeCount() {
+        return numDeduped.get();
+    }
+}