Add statistics about free space to microdump format.

src/client/linux/microdump_writer/microdump_writer.cc

 // Copyright (c) 2014, Google Inc.
 // All rights reserved.
 //
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 // notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
@@ skipping 16 matching lines @@
 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
 // This translation unit generates microdumps into the console (logcat on
 // Android). See crbug.com/410294 for more info and design docs.
 
 #include "client/linux/microdump_writer/microdump_writer.h"
 
 #include <sys/utsname.h>
 
-#include <algorithm>
-
 #include "client/linux/dump_writer_common/thread_info.h"
 #include "client/linux/dump_writer_common/ucontext_reader.h"
 #include "client/linux/handler/exception_handler.h"
 #include "client/linux/handler/microdump_extra_info.h"
 #include "client/linux/log/log.h"
 #include "client/linux/minidump_writer/linux_ptrace_dumper.h"
 #include "common/linux/file_id.h"
 #include "common/linux/linux_libc_support.h"
+#include "common/memory.h"
 
 namespace {
 
 using google_breakpad::auto_wasteful_vector;
 using google_breakpad::ExceptionHandler;
 using google_breakpad::kDefaultBuildIdSize;
 using google_breakpad::LinuxDumper;
 using google_breakpad::LinuxPtraceDumper;
 using google_breakpad::MappingInfo;
 using google_breakpad::MappingList;
 using google_breakpad::MicrodumpExtraInfo;
 using google_breakpad::RawContextCPU;
 using google_breakpad::ThreadInfo;
 using google_breakpad::UContextReader;
 
 const size_t kLineBufferSize = 2048;
 
+int Log2Floor(uint64_t n) {
+  // Copied from chromium src/base/bits.h
+  if (n == 0)
+    return -1;
+  int log = 0;
+  uint64_t value = n;
+  for (int i = 5; i >= 0; --i) {
+    int shift = (1 << i);
+    uint64_t x = value >> shift;
+    if (x != 0) {
+      value = x;
+      log += shift;
+    }
+  }
+  assert(value == 1u);
+  return log;
+}
+
+bool MappingsAreAdjacent(const MappingInfo* a, const MappingInfo* b) {
+  // Because of load biasing, we can end up with a situation where two
+  // mappings actually overlap. So we will define adjacency to also include a
+  // b start address that lies within a's address range (including starting
+  // immediately after a).
+  // Because load biasing only ever moves the start address backwards, the end
+  // address should still increase.
+  return a->start_addr <= b->start_addr &&
+         a->start_addr + a->size >= b->start_addr;
+}
+
+size_t NextOrderedMapping(
+    const google_breakpad::wasteful_vector<MappingInfo*>& mappings,
+    size_t curr) {
+  size_t best = curr;
+  for (size_t next = 0; next < mappings.size(); ++next) {
+    if (mappings[next]->start_addr > mappings[curr]->start_addr &&
+        mappings[next]->start_addr < mappings[best]->start_addr) {

[Tobias Sargeant, 2016/05/13 16:16:54]

Testing showed this is wrong. I rewrote it (actually reverted it back to
basically what I started with), but tried to make it more readable. Hopefully
you feel the final result is more readable.

+      best = next;
+    }
+  }
+  return best;
+}
+
 class MicrodumpWriter {
  public:
   MicrodumpWriter(const ExceptionHandler::CrashContext* context,
                   const MappingList& mappings,
                   const MicrodumpExtraInfo& microdump_extra_info,
                   LinuxDumper* dumper)
       : ucontext_(context ? &context->context : NULL),
 #if !defined(__ARM_EABI__) && !defined(__mips__)
         float_state_(context ? &context->float_state : NULL),
 #endif
@@ skipping 17 matching lines @@
       return false;
     return dumper_->ThreadsSuspend() && dumper_->LateInit();
   }
 
   bool Dump() {
     bool success;
     LogLine("-----BEGIN BREAKPAD MICRODUMP-----");
     DumpProductInformation();
     DumpOSInformation();
     DumpGPUInformation();
+#if !defined(__LP64__)
+    DumpFreeSpace();
+#endif
     success = DumpCrashingThread();
     if (success)
       success = DumpMappings();
     LogLine("-----END BREAKPAD MICRODUMP-----");
     dumper_->ThreadsResume();
     return success;
   }
 
  private:
   // Writes one line to the system log.
@@ skipping 10 matching lines @@
   void LogAppend(const char* str) {
     my_strlcat(log_line_, str, kLineBufferSize);
   }
 
   // As above (required to take precedence over template specialization below).
   void LogAppend(char* str) {
     LogAppend(const_cast<const char*>(str));
   }
 
   // Stages the hex repr. of the given int type in the current line buffer.
-  template<typename T>
-  void LogAppend(T value) {
+  enum LeadingZeros { kKeepLeadingZeros, kDiscardLeadingZeros };

[Primiano Tucci (use gerrit), 2016/05/10 16:20:49]

can we avoid complicating this logic? I don't think a bunch of leading zeros is
going to make such a great difference.
Just cast to the right type to minimize the number of zeros.
Sorry but this is breakpad and my overall rule of thumb for reviewing changes
here is: minimize the numbers of line changed, don't change something unless
strictly necessary.
Unfortunately breakpad has a sad story w.r.t. test coverage. The good news is
that it is going to change in crashpad. The bad new is that this is still
breakpad :)

[Tobias Sargeant, 2016/05/13 16:16:54]

Done. I made the keys and values in the histogram uint8_t, and the counts
saturate at 0xff. The count of all holes is a uint16_t now. It seemed
unnecessary to saturate that, but maybe it should be?

+  template <typename T>
+  void LogAppend(T value, const LeadingZeros leading_zeros =
+                              LeadingZeros::kKeepLeadingZeros) {
     // Make enough room to hex encode the largest int type + NUL.
     static const char HEX[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
                                'A', 'B', 'C', 'D', 'E', 'F'};
     char hexstr[sizeof(T) * 2 + 1];
-    for (int i = sizeof(T) * 2 - 1; i >= 0; --i, value >>= 4)
-      hexstr[i] = HEX[static_cast<uint8_t>(value) & 0x0F];
-    hexstr[sizeof(T) * 2] = '\0';
-    LogAppend(hexstr);
+    int i = sizeof(T) * 2;
+    hexstr[i] = '\0';
+    do {
+      hexstr[--i] = HEX[static_cast<uint8_t>(value) & 0x0F];
+      value >>= 4;
+    } while (value || leading_zeros == kKeepLeadingZeros && i > 0);
+    LogAppend(hexstr + i);
   }
 
   // Stages the buffer content hex-encoded in the current line buffer.
   void LogAppend(const void* buf, size_t length) {
     const uint8_t* ptr = reinterpret_cast<const uint8_t*>(buf);
     for (size_t i = 0; i < length; ++i, ++ptr)
       LogAppend(*ptr);
   }
 
   // Writes out the current line buffer on the system log.
@@ skipping 233 matching lines @@
     LogAppend(module_identifier.data4[3]);
     LogAppend(module_identifier.data4[4]);
     LogAppend(module_identifier.data4[5]);
     LogAppend(module_identifier.data4[6]);
     LogAppend(module_identifier.data4[7]);
     LogAppend("0 ");  // Age is always 0 on Linux.
     LogAppend(file_name);
     LogCommitLine();
   }
 
+#if !defined(__LP64__)
+  bool DumpFreeSpace() {
+    const google_breakpad::wasteful_vector<MappingInfo*>& mappings =
+        dumper_->mappings();
+    if (mappings.size() == 0) return false;
+
+    // This is complicated by the fact that mappings is not in order. It should
+    // be mostly in order, however the mapping that contains the entry point for
+    // the process is always at the front of the vector.
+
+    static const int HBITS = sizeof(size_t) * 8;
+    unsigned int hole_histogram[HBITS];
+    my_memset(hole_histogram, 0, sizeof(hole_histogram));
+
+    // Find the lowest address mapping.
+    size_t curr = 0;
+    for (size_t i = 1; i < mappings.size(); ++i) {
+      if (mappings[i]->start_addr < mappings[curr]->start_addr) curr = i;
+    }
+
+    uintptr_t lo_addr = mappings[curr]->start_addr;
+
+    unsigned int hole_cnt = 0;
+    size_t hole_max = 0;
+    size_t hole_sum = 0;
+
+    while (true) {
+      // Skip to the end of an adjacent run of mappings. This is an optimization
+      // for the fact that mappings is mostly sorted.
+      while (curr != mappings.size() - 1 &&
+             MappingsAreAdjacent(mappings[curr], mappings[curr + 1]))

[Primiano Tucci (use gerrit), 2016/05/10 16:20:49]

add curly braces around this loop (the while is multiline)

[Tobias Sargeant, 2016/05/13 16:16:54]

Done.

+        ++curr;
+
+      size_t next = NextOrderedMapping(mappings, curr);
+      if (next == curr)
+        break;
+
+      uintptr_t hole_lo = mappings[curr]->start_addr + mappings[curr]->size;
+      uintptr_t hole_hi = mappings[next]->start_addr;
+
+      if (hole_hi > hole_lo) {
+        size_t hole_sz = hole_hi - hole_lo;
+        hole_sum += hole_sz;
+        hole_max = std::max(hole_sz, hole_max);
+        ++hole_cnt;
+        ++hole_histogram[Log2Floor(hole_sz)];
+      }
+      curr = next;
+    }
+
+    uintptr_t hi_addr = mappings[curr]->start_addr + mappings[curr]->size;
+
+    LogAppend("H ");
+    LogAppend(lo_addr);
+    LogAppend(" ");
+    LogAppend(hi_addr);
+    LogAppend(" ");
+    LogAppend(hole_cnt, kDiscardLeadingZeros);
+    LogAppend(" ");
+    LogAppend(hole_max, kDiscardLeadingZeros);
+    LogAppend(" ");
+    LogAppend(hole_sum, kDiscardLeadingZeros);
+    for (unsigned int i = 0; i < HBITS; ++i) {
+      if (!hole_histogram[i]) continue;
+      LogAppend(" ");
+      LogAppend(i, kDiscardLeadingZeros);
+      LogAppend(":");
+      LogAppend(hole_histogram[i], kDiscardLeadingZeros);
+    }
+    LogCommitLine();
+    return true;
+  }
+#endif
+
   // Write information about the mappings in effect.
   bool DumpMappings() {
     // First write all the mappings from the dumper
     for (unsigned i = 0; i < dumper_->mappings().size(); ++i) {
       const MappingInfo& mapping = *dumper_->mappings()[i];
       if (mapping.name[0] == 0 ||  // only want modules with filenames.
           !mapping.exec ||  // only want executable mappings.
           mapping.size < 4096 || // too small to get a signature for.
           HaveMappingInfo(mapping)) {
         continue;
@@ skipping 41 matching lines @@
     dumper.set_crash_signal(context->siginfo.si_signo);
     dumper.set_crash_thread(context->tid);
   }
   MicrodumpWriter writer(context, mappings, microdump_extra_info, &dumper);
   if (!writer.Init())
     return false;
   return writer.Dump();
 }
 
 }  // namespace google_breakpad