Add statistics about free space to microdump format.

src/client/linux/microdump_writer/microdump_writer.cc

Index: src/client/linux/microdump_writer/microdump_writer.cc
diff --git a/src/client/linux/microdump_writer/microdump_writer.cc b/src/client/linux/microdump_writer/microdump_writer.cc
index d459d9ec441370c2e06e2e2f9a365bedf10e6353..ee089c9510014a191bb9a735e799a4a3afe84f9e 100644
--- a/src/client/linux/microdump_writer/microdump_writer.cc
+++ b/src/client/linux/microdump_writer/microdump_writer.cc
@@ -34,8 +34,6 @@
 
 #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"
@@ -44,6 +42,7 @@
 #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 {
 
@@ -61,6 +60,58 @@ 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) {

[Primiano Tucci (use gerrit), 2016/05/20 15:18:22]

nit: just for consistency (with your own code below) these (and below on line
92) should be const& not const*.
In general IIRC the guideline is to use const& for input arguments, (unless you
need nullptr) to distinguish from output arguments.

[Tobias Sargeant, 2016/05/23 10:51:59]

Done.

+  // 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;
+}
+
+bool MappingLessThan(const MappingInfo* a, const MappingInfo* b) {
+  // Return true if mapping a is before mapping b.
+  // For the same reason (load biasing) we compare end addresses, which - unlike
+  // start addresses - will not have been modified.
+  return a->start_addr + a->size < b->start_addr + b->size;
+}
+
+size_t NextOrderedMapping(
+    const google_breakpad::wasteful_vector<MappingInfo*>& mappings,
+    size_t curr) {
+  // Find the mapping that directly follows mappings[curr].
+  // If no such mapping exists, return mappings.size() to indicate this.
+  const size_t invalid = mappings.size();

[Primiano Tucci (use gerrit), 2016/05/20 15:18:22]

not a huge difference but I typically see this as -1 or
std::numeric_limits<size_t>::max().
Not a huge deal but .size() is a totally useless op here :)

Also this should allow some smaller compiler optimiazion below in the if, as the
-1 be const propagated as it's known at compile time.

[Tobias Sargeant, 2016/05/23 10:51:59]

Done.

+  size_t best = invalid;
+  for (size_t next = 0; next < mappings.size(); ++next) {
+    if (MappingLessThan(mappings[curr], mappings[next]) &&
+        (best == invalid || MappingLessThan(mappings[next], mappings[best]))) {
+      best = next;
+    }
+  }
+  return best;
+}
+
 class MicrodumpWriter {
  public:
   MicrodumpWriter(const ExceptionHandler::CrashContext* context,
@@ -98,6 +149,9 @@ class MicrodumpWriter {
     DumpProductInformation();
     DumpOSInformation();
     DumpGPUInformation();
+#if !defined(__LP64__)
+    DumpFreeSpace();
+#endif
     success = DumpCrashingThread();
     if (success)
       success = DumpMappings();
@@ -391,6 +445,84 @@ class MicrodumpWriter {
     LogCommitLine();
   }
 
+#if !defined(__LP64__)
+  bool DumpFreeSpace() {

[Primiano Tucci (use gerrit), 2016/05/20 15:18:22]

make this void. You never seeem to sue the return value (which is fine).

[Tobias Sargeant, 2016/05/23 10:51:59]

Done.

+    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;
+    uint8_t 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;

[Primiano Tucci (use gerrit), 2016/05/20 15:18:22]

why not making this also a size_t? you are going to cast it anyways

[Tobias Sargeant, 2016/05/23 10:51:59]

Done.

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

[Primiano Tucci (use gerrit), 2016/05/20 15:18:22]

shouldn't this be s/-1/-2/, as below you access mappings[curr + 1].
If you have 4 mappings in the vector, you are still looping if curr = (4-1)=3
but then you'll try to dereference mapping[4] which is out of bound

[Tobias Sargeant, 2016/05/20 15:32:54]

It might be better to write curr < mappings.size() - 1, rather than !=, but it's
otherwise correct.

[Primiano Tucci (use gerrit), 2016/05/20 17:52:48]

oh ok forget my comment, I am just wrong. If size=4 you are going to loop only
in 0 1 2, which is fine.

+             MappingsAreAdjacent(mappings[curr], mappings[curr + 1])) {
+        ++curr;
+      }
+
+      size_t next = NextOrderedMapping(mappings, curr);
+      if (next == mappings.size())
+        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;
+        int log2_hole_sz = Log2Floor(hole_sz);
+        hole_sum += hole_sz;
+        hole_max = std::max(hole_sz, hole_max);
+        ++hole_cnt;
+        if (hole_histogram[log2_hole_sz] != 0xff) {
+          ++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(static_cast<uint16_t>(hole_cnt));

[Primiano Tucci (use gerrit), 2016/05/20 15:18:22]

maybe you could do a saturated cast (stick at UINT16_MAX if cnt > that)

[Tobias Sargeant, 2016/05/20 15:32:55]

Can you use base::saturated_cast here, or is there some other way of spelling
it?

[Primiano Tucci (use gerrit), 2016/05/20 17:52:48]

unfortunately there is no fancy chromium base here
I suppose you could do something like

template<typename T> T saturated_cast(uint32_t value) {
  return value > std::numeric_limits<T>::max() ? std::numeric_limits<T>::max() ?
static_cast<T>(value);
}

[Tobias Sargeant, 2016/05/23 10:51:59]

Done.

+    LogAppend(" ");
+    LogAppend(hole_max);
+    LogAppend(" ");
+    LogAppend(hole_sum);
+    for (unsigned int i = 0; i < HBITS; ++i) {
+      if (!hole_histogram[i]) continue;
+      LogAppend(" ");
+      LogAppend(static_cast<uint8_t>(i));

[Primiano Tucci (use gerrit), 2016/05/20 15:18:22]

ditto hjere about saturation

[Tobias Sargeant, 2016/05/23 10:51:59]

Done.

+      LogAppend(":");
+      LogAppend(hole_histogram[i]);
+    }
+    LogCommitLine();
+    return true;
+  }
+#endif
+
   // Write information about the mappings in effect.
   bool DumpMappings() {
     // First write all the mappings from the dumper