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

   1 // Copyright 2014 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4 package org.chromium.tools.binary_size;
   5
   6 import java.io.BufferedReader;
   7 import java.io.File;
   8 import java.io.IOException;
   9 import java.io.InputStream;
  10 import java.io.InputStreamReader;
  11 import java.io.Reader;
  12 import java.nio.charset.Charset;
  13 import java.util.HashMap;
  14 import java.util.HashSet;
  15 import java.util.Map;
  16 import java.util.Queue;
  17 import java.util.Random;
  18 import java.util.Set;
  19 import java.util.concurrent.ArrayBlockingQueue;
  20 import java.util.concurrent.ConcurrentHashMap;
  21 import java.util.concurrent.ConcurrentLinkedQueue;
  22 import java.util.concurrent.ConcurrentMap;
  23 import java.util.concurrent.CountDownLatch;
  24 import java.util.concurrent.TimeUnit;
  25 import java.util.concurrent.atomic.AtomicInteger;
  26 import java.util.concurrent.atomic.AtomicReference;
  27
  28 /**
  29  * A pool of workers that run 'addr2line', looking up source locations for
  30  * addresses that are fed into the pool via a queue. As address lookups
  31  * complete, records are placed onto an output queue.
  32  */
  33 class Addr2LineWorkerPool {
  34     private static final Charset sAscii = Charset.forName("US-ASCII");
  35     private final Addr2LineWorker[] mWorkers;
  36     private final ArrayBlockingQueue<Record> mRecordsIn = new ArrayBlockingQueue<Record>(1000);
  37     private final Queue<Record> mRecordsOut = new ConcurrentLinkedQueue<Record>();
  38     private final CountDownLatch mCompletionLatch;
  39     private final String mAddr2linePath;
  40     private final String mLibraryPath;
  41     private final boolean mDisambiguate;
  42     private final boolean mDedupe;
  43     private final String stripLocation;
  44     private final ConcurrentMap<Long, Record> mAddressesSeen =
  45             new ConcurrentHashMap<Long, Record>(100000, 0.75f, 32);
  46     private volatile Map<String,String> mFileLookupTable = null;
  47     private final AtomicInteger mDisambiguationSuccessCount = new AtomicInteger(0);
  48     private final AtomicInteger mDisambiguationFailureCount = new AtomicInteger(0);
  49     private final AtomicInteger mDedupeCount = new AtomicInteger(0);
  50
  51     /**
  52      * These are the suffixes of files that we are potentially interested in
  53      * searching during symbol lookups when disambiguation is enabled. Anything
  54      * that could theoretically end up being linked into the library file
  55      * should be listed here.
  56      * <p>
  57      * IMPORTANT: All of these should be lowercase. When doing comparisons,
  58      * always lowercase the file name before attempting the match.
  59      */
  60     private static final String[] INTERESTING_FILE_ENDINGS = new String[]{
  61             ".c", ".cc", ".h", ".cp", ".cpp", ".cxx", ".c++", ".asm", ".inc", ".s", ".hxx"
  62     };
  63
  64
  65     Addr2LineWorkerPool(final int size,
  66             final String addr2linePath, final String libraryPath,
  67             final boolean disambiguate, final boolean dedupe)
  68                     throws IOException {
  69         this.mAddr2linePath = addr2linePath;
  70         this.mLibraryPath = libraryPath;
  71         this.mDisambiguate = disambiguate;
  72         this.mDedupe = dedupe;
  73
  74         // Prepare disambiguation table if necessary. This must be done
  75         // before launching the threads in the processing pool for visibility.
  76         if (disambiguate) {
  77             try {
  78                 createDisambiguationTable();
  79             } catch (IOException e) {
  80                 throw new RuntimeException("Can't create lookup table", e);
  81             }
  82         }
  83
  84         // The library is in, e.g.: src/out/Release
  85         // Convert all output paths to be relative to src.
  86         // Strip everything up to and including "src/".
  87         String canonical = new File(libraryPath).getCanonicalPath();
  88         int end = canonical.lastIndexOf("/src/");
  89         if (end < 0) {
  90             // Shouldn't happen if the library exists.
  91             throw new RuntimeException("Bad library path: " + libraryPath +
  92                     ". Library is expected to be within a build directory.");
  93         }
  94         stripLocation = canonical.substring(0, end + "/src/".length());
  95
  96         mWorkers = new Addr2LineWorker[size];
  97         mCompletionLatch = new CountDownLatch(size);
  98         for (int x = 0; x < mWorkers.length; x++) {
  99             mWorkers[x] = new Addr2LineWorker();
 100         }
 101     }
 102
 103     void submit(Record record) throws InterruptedException {
 104         mRecordsIn.put(record);
 105     }
 106
 107     void allRecordsSubmitted() {
 108         for (Addr2LineWorker worker : mWorkers) {
 109             worker.stopIfQueueIsEmpty = true;
 110         }
 111     }
 112
 113     boolean await(int amount, TimeUnit unit) throws InterruptedException {
 114         return mCompletionLatch.await(amount, unit);
 115     }
 116
 117     /**
 118      * @param value the base value
 119      * @param percent absolute percentage to jitter by (in the range [0,100])
 120      * @return a value that is on average uniformly distributed within
 121      * plus or minus <em>percent</em> of the base value.
 122      */
 123     private static int jitter(final int value, final int percent) {
 124         Random r = new Random();
 125         int delta = (r.nextBoolean() ? 1 : -1) * r.nextInt((percent * value) / 100);
 126         return value + delta;
 127     }
 128
 129
 130     /**
 131      * A class that encapsulates an addr2line process and the work that it
 132      * needs to do.
 133      */
 134     private class Addr2LineWorker {
 135         // Our work queues
 136         private final AtomicReference<Process> processRef = new AtomicReference<Process>();
 137         private final Thread workerThread;
 138         private volatile boolean stopIfQueueIsEmpty = false;
 139
 140         /**
 141          * After this many addresses have been processed, the addr2line process
 142          * itself will be recycled. This prevents the addr2line process from
 143          * getting too huge, which in turn allows more parallel addr2line
 144          * processes to run. There is a balance to be achieved here, as
 145          * creating a new addr2line process is very costly. A value of
 146          * approximately 2000 appears, empirically, to be a good tradeoff
 147          * on a modern machine; memory usage stays tolerable, and good
 148          * throughput can be achieved. The value is jittered by +/- 10% so that
 149          * the processes don't all restart at once.
 150          */
 151         private final int processRecycleThreshold = jitter(2000, 10);
 152
 153         private Addr2LineWorker() throws IOException {
 154             this.processRef.set(createAddr2LineProcess());
 155             workerThread = new Thread(new Addr2LineTask(), "Addr2Line Worker");
 156             workerThread.setDaemon(true);
 157             workerThread.start();
 158         }
 159
 160         /**
 161          * Builds a new addr2line process for use in this worker.
 162          * @return the process
 163          * @throws IOException if unable to create the process for any reason
 164          */
 165         private Process createAddr2LineProcess()
 166                 throws IOException {
 167             ProcessBuilder builder = new ProcessBuilder(mAddr2linePath, "-e", mLibraryPath, "-f");
 168             Process process = builder.start();
 169             return process;
 170         }
 171
 172         /**
 173          * Reads records from the input queue and pipes addresses into
 174          * addr2line, using the output to complete the record and pushing
 175          * the record into the output queue.
 176          */
 177         private class Addr2LineTask implements Runnable {
 178             @Override
 179             public void run() {
 180                 int processTaskCounter = 0;
 181                 InputStream inStream = processRef.get().getInputStream();
 182                 Reader isr = new InputStreamReader(inStream);
 183                 BufferedReader reader = new BufferedReader(isr);
 184                 try {
 185                     while (true) {
 186                         // Check for a task.
 187                         final Record record = mRecordsIn.poll(1, TimeUnit.SECONDS);
 188                         if (record == null) {
 189                             if (stopIfQueueIsEmpty) {
 190                                 // All tasks have been submitted, so if the
 191                                 // queue is empty then there is nothing left
 192                                 // to do and it's ready to shut down
 193                                 return;
 194                             }
 195                             continue; // else, queue starvation. Try again.
 196                         }
 197
 198                         // Avoid reprocessing previously-seen symbols if
 199                         // deduping is enabled
 200                         if (tryDedupe(record)) continue;
 201
 202                         // Create a new reader if the addr2line process is new
 203                         // or has been recycled. A single reader will be used
 204                         // for the entirety of the addr2line process' lifetime.
 205                         final Process process = processRef.get();
 206                         if (inStream == null) {
 207                             inStream = process.getInputStream();
 208                             isr = new InputStreamReader(inStream);
 209                             reader = new BufferedReader(isr);
 210                         }
 211
 212                         // Write the address to stdin of addr2line
 213                         process.getOutputStream().write(record.address.getBytes(sAscii));
 214                         process.getOutputStream().write('\n');
 215                         process.getOutputStream().flush();
 216
 217                         // Read the answer from addr2line. Example:
 218                         // ABGRToYRow_C
 219                         // /src/out/Release/../../third_party/libyuv/source/row_common.cc:293
 220                         final String name = reader.readLine();
 221                         if (name == null || name.isEmpty()) {
 222                             stopIfQueueIsEmpty = true;
 223                             continue;
 224                         }
 225
 226                         String location = reader.readLine();
 227                         if (location == null || location.isEmpty()) {
 228                             stopIfQueueIsEmpty = true;
 229                             continue;
 230                         }
 231
 232                         record.resolvedSuccessfully = !(
 233                                 name.equals("??") && location.equals("??:0"));
 234
 235                         if (record.resolvedSuccessfully) {
 236                             // Keep the name from the initial NM dump.
 237                             // Some addr2line impls, such as the one for Android
 238                             // on ARM, seem to lose data here.
 239                             // Note that the location may also include a line
 240                             // discriminator, which maps to a part of a line.
 241                             // Not currently used.
 242                             record.location = processLocation(location);;
 243                         }
 244
 245                         // Check if there is more input on the stream.
 246                         // If there is then it is a serious processing
 247                         // error, and reading anything else would de-sync
 248                         // the input queue from the results being read.
 249                         if (inStream.available() > 0) {
 250                             throw new IllegalStateException(
 251                                     "Alignment mismatch in output from address " + record.address);
 252                         }
 253
 254                         // Track stats and move record to output queue
 255                         processTaskCounter++;
 256                         mRecordsOut.add(record);
 257
 258                         // If the addr2line process has done too much work,
 259                         // kill it and start a new one to reduce memory
 260                         // pressure created by the pool.
 261                         if (processTaskCounter >= processRecycleThreshold) {
 262                             // Out with the old...
 263                             try {
 264                                 processRef.get().destroy();
 265                             } catch (Exception e) {
 266                                 System.err.println("WARNING: zombie process");
 267                                 e.printStackTrace();
 268                             }
 269                             // ... and in with the new!
 270                             try {
 271                                 processRef.set(createAddr2LineProcess());
 272                             } catch (IOException e) {
 273                                 e.printStackTrace();
 274                             }
 275                             processTaskCounter = 0;
 276                             inStream = null; // New readers need to be created next iteration
 277                         }
 278                     }
 279                 } catch (RuntimeException e) {
 280                     throw e;
 281                 } catch (Exception e) {
 282                     e.printStackTrace();
 283                 } finally {
 284                     try {
 285                         // Make an attempt to clean up. If we fail, there is
 286                         // nothing we can do beyond this.
 287                         processRef.get().destroy();
 288                     } catch (Exception e) {
 289                         // There's nothing more we can do here.
 290                     }
 291                     mCompletionLatch.countDown();
 292                 }
 293             }
 294         }
 295
 296         /**
 297          * Examines the location from a record and attempts to canonicalize
 298          * it and strip off the common source root.
 299          * @param location the location to process
 300          * @return the canonicalized, stripped location or the original input
 301          * string if the location cannot be canonicalized
 302          */
 303         private String processLocation(String location) {
 304             if (location.startsWith("/")) {
 305                 try {
 306                     location = new File(location).getCanonicalPath();
 307                 } catch (IOException e) {
 308                     System.err.println("Unable to canonicalize path: " + location);
 309                 }
 310             } else if (mDisambiguate) {
 311                 // Ambiguous path (only has the file name)
 312                 // Try dictionary lookup if that's enabled
 313                 final int indexOfColon = location.lastIndexOf(':');
 314                 final String key;
 315                 final String line;
 316                 if (indexOfColon != -1) {
 317                     key = location.substring(0, indexOfColon);
 318                     line = location.substring(indexOfColon + 1);
 319                 } else {
 320                     key = location;
 321                     line = null;
 322                 }
 323                 final String found = mFileLookupTable.get(key);
 324                 if (found != null) {
 325                     mDisambiguationSuccessCount.incrementAndGet();
 326                     location = found;
 327                     if (line != null) location = location + ":" + line;
 328                 } else {
 329                     mDisambiguationFailureCount.incrementAndGet();
 330                 }
 331             }
 332             if (location.startsWith(stripLocation)) {
 333                 location = location.substring(stripLocation.length());
 334             }
 335             return location;
 336         }
 337
 338         /**
 339          * Attempts to dedupe a record using a cache of previously-seen
 340          * addresses if and only if deduping is enabled.
 341          * @param record the record to attempt deduping
 342          * @return true if deduplication is enabled and the record references
 343          * an address that has already been seen; otherwise false
 344          */
 345         private boolean tryDedupe(Record record) {
 346             if (mDedupe) {
 347                 long addressLong = Long.parseLong(record.address, 16);
 348                 Record existing = mAddressesSeen.get(addressLong);
 349                 if (existing != null) {
 350                     if (!existing.size.equals(record.size)) {
 351                         System.err.println("WARNING: Deduped address " +
 352                                 record.address + " has a size mismatch, " +
 353                                 existing.size + " != " + record.size);
 354                     }
 355                     mDedupeCount.incrementAndGet();
 356                     return true;
 357                 }
 358                 if (mAddressesSeen.putIfAbsent(addressLong, record) != null) {
 359                     // putIfAbsent is used to ensure that we have
 360                     // an accurate dedupeCount; otherwise, two
 361                     // workers could insert the same record in
 362                     // parallel without realizing that one of them
 363                     // was actually a duplicate.
 364                     mDedupeCount.incrementAndGet();
 365                     return true;
 366                 }
 367             }
 368             return false;
 369         }
 370     }
 371
 372     // TODO(andrewhayden): Make this less Android-specific
 373     private void createDisambiguationTable() throws IOException {
 374         // Convert /src/out/Release/lib/*.so -> /src/out/Release
 375         final File libraryOutputDirectory = new File(mLibraryPath)
 376             .getParentFile().getParentFile().getCanonicalFile();
 377
 378         // Convert /src/out/Release -> /src
 379         final File root = libraryOutputDirectory
 380                 .getParentFile().getParentFile().getCanonicalFile();
 381
 382         // There is no code at the root of Chromium.
 383         // Ignore all the 'out' directories.
 384         mFileLookupTable = new HashMap<String, String>();
 385         Set<String> dupes = new HashSet<String>();
 386         for (File file : root.listFiles()) {
 387             if (file.isDirectory()) {
 388                 String name = file.getName();
 389                 if (name.startsWith("out")) {
 390                     if (new File(file, "Release").exists() || new File(file, "Debug").exists()) {
 391                         // It's an output directory, skip it - except for the
 392                         // 'obj' and 'gen' subdirectories that are siblings
 393                         // to the library file's parent dir, which is needed.
 394                         // Include those at the very end, since they are known.
 395                         continue;
 396                     }
 397                 } else if (name.startsWith(".")) {
 398                     // Skip dot directories: .git, .svn, etcetera.
 399                     continue;
 400                 }
 401                 findInterestingFiles(file, dupes);
 402             }
 403         }
 404
 405         // Include directories that contain generated resources we are likely
 406         // to encounter in the symbol table.
 407         findInterestingFiles(new File(libraryOutputDirectory, "gen"), dupes);
 408         findInterestingFiles(new File(libraryOutputDirectory, "obj"), dupes);
 409
 410         // Any duplicates in the filesystem can't be used for disambiguation
 411         // because it is not obvious which of the duplicates is the true source.
 412         // Therefore, discard all files that have duplicate names.
 413         for (String dupe : dupes) {
 414             mFileLookupTable.remove(dupe);
 415         }
 416     }
 417
 418     // TODO(andrewhayden): Could integrate with build system to know EXACTLY
 419     // what is out there. This would avoid the need for the dupes set, which
 420     // would make it possible to do much better deduping.
 421     private void findInterestingFiles(File directory, Set<String> dupes) {
 422         for (File file : directory.listFiles()) {
 423             if (file.isDirectory() && file.canRead()) {
 424                 if (!file.getName().startsWith(".")) {
 425                     findInterestingFiles(file, dupes);
 426                 }
 427             } else {
 428                 String name = file.getName();
 429                 String normalized = name.toLowerCase();
 430                 for (String ending : INTERESTING_FILE_ENDINGS) {
 431                     if (normalized.endsWith(ending)) {
 432                         String other = mFileLookupTable.put(
 433                                 name, file.getAbsolutePath());
 434                         if (other != null) dupes.add(name);
 435                     }
 436                 }
 437             }
 438         }
 439     }
 440
 441     /**
 442      * Polls the output queue for the next record.
 443      * @return the next record
 444      */
 445     Record poll() {
 446         return mRecordsOut.poll();
 447     }
 448
 449     /**
 450      * @return the number of ambiguous paths successfully disambiguated
 451      */
 452     int getDisambiguationSuccessCount() {
 453         return mDisambiguationSuccessCount.get();
 454     }
 455
 456     /**
 457      * @return the number of ambiguous paths that couldn't be disambiguated
 458      */
 459     int getDisambiguationFailureCount() {
 460         return mDisambiguationFailureCount.get();
 461     }
 462
 463     /**
 464      * @return the number of symbols deduped
 465      */
 466     int getDedupeCount() {
 467         return mDedupeCount.get();
 468     }
 469 }