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..230ef2292ec0a416d4c3d5f9538fb5621946107c 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,31 @@ using google_breakpad::UContextReader;
 
 const size_t kLineBufferSize = 2048;
 
+bool MappingsAreAdjacent(const MappingInfo* a, const MappingInfo* b) {
+  // Because of load biasing, we can end up with a situation where two

[Primiano Tucci (use gerrit), 2016/05/06 11:07:56]

Hmm I thought that after the latest linker changes, mappings can not overlap
because of the zero guard regions.
When does this happen?

[Tobias Sargeant, 2016/05/06 13:29:31]

It definitely came up during writing this CL. When were these linker changes?
Will zero guard regions appear as mappings themselves?

[Primiano Tucci (use gerrit), 2016/05/06 13:58:38]

https://codereview.chromium.org/1218493004
And there should be an equivalent in the Android system linker in M
Yes (and you should count them as NON-holes as they steal address space). But
breakpad should never see overlapping regions ever (this CL was to fix the bug).

Curious to see if you have any instance of mmaps that overlap.
I wonder if you did just hit
https://bugs.chromium.org/p/chromium/issues/detail?id=499747#c24
that petrcermak fixed very recently (last week)

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

[Primiano Tucci (use gerrit), 2016/05/06 11:07:56]

Not sure I get the full logic here. Why is not enough just getting the next by
start-address? (in other words: why are you looking at the size at all here?)

[Tobias Sargeant, 2016/05/06 11:33:45]

size here is mappings array length, not the size of one mapping. This is finding
the entry with the lowest start address greater than mappings[curr]->start_addr.

[Primiano Tucci (use gerrit), 2016/05/06 13:29:23]

Oh ok I misread it. This seems overly complicated. I am probably still missing
something. Why this is not just:

best = it.back()
for (it = mappings.begin(); it != mappings.end(); ++it) {
  if (it->start_addr > curr && it->start_addr < best)
    best = it;
}

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

Could do this, although you'd have to set best = curr, not back, so that you
could distinguish the case where curr is actually the highest address mapping.

+    const google_breakpad::wasteful_vector<MappingInfo*>& mappings,
+    size_t curr) {
+  size_t best = mappings.size();
+  for (size_t next = 0; next < mappings.size(); ++next) {
+    if (mappings[curr]->start_addr < mappings[next]->start_addr &&
+        (best == mappings.size() ||
+         mappings[next]->start_addr < mappings[best]->start_addr)) {
+      best = next;
+    }
+  }
+  return best;
+}
+
 class MicrodumpWriter {
  public:
   MicrodumpWriter(const ExceptionHandler::CrashContext* context,
@@ -98,6 +122,7 @@ class MicrodumpWriter {
     DumpProductInformation();
     DumpOSInformation();
     DumpGPUInformation();
+    DumpFreeSpace();
     success = DumpCrashingThread();
     if (success)
       success = DumpMappings();
@@ -140,6 +165,23 @@ class MicrodumpWriter {
     LogAppend(hexstr);
   }
 
+  void LogAppendDecimal(unsigned int value) {
+    const int SZ = sizeof(unsigned int) * 3;

[Primiano Tucci (use gerrit), 2016/05/06 11:07:56]

can we just use hex for everything, for consistency with the current format
(where even the cpu count is hex). Will make the processor part also easier

[Tobias Sargeant, 2016/05/06 11:33:45]

Can do, but would still need to trim leading zeros, to be more succinct.

[Primiano Tucci (use gerrit), 2016/05/06 13:29:23]

LogAppend<T> will emit leading zeros only to pad the actual T size.
So if you use a unsigned char will be at most one zero, not bad.
As long as we stay in the line length (can't remember, it's somewhere, somewehat
between 500 and 1k chars) it's ok

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

I modified LogAppend<T> to optionally strip leading zeros. Is that ok? I don't
think I can cast hole_cnt or the histogram counts to anything less than
uint16_t, and that probably means wasting 2-3 characters per entry, whereas
stripping leading zeros doesn't seem too hard.

+    if (!value) {
+      LogAppend("0");
+      return;
+    }
+    char decstr[SZ + 1];
+    decstr[SZ] = '\0';
+    int i;
+    for (i = SZ - 1; i >= 0; --i) {
+      decstr[i] = '0' + value % 10;
+      value /= 10;
+      if (!value) break;
+    }
+    LogAppend(decstr+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);
@@ -391,6 +433,81 @@ class MicrodumpWriter {
     LogCommitLine();
   }
 
+  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_hist[HBITS];

[Primiano Tucci (use gerrit), 2016/05/06 11:07:56]

can you call this hole_histogram? For a long while (until I saw the code below)
I thought this was going to be some kind of history :)

[Tobias Sargeant, 2016/05/06 13:29:31]

Done.

+    my_memset(hole_hist, 0, sizeof(hole_hist));
+
+    // 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_tot = 0;

[Primiano Tucci (use gerrit), 2016/05/06 11:07:56]

I'd probably rename this to hole_sum (or unmapped_total). I figured out only
down below what this really was :)

[Tobias Sargeant, 2016/05/06 13:29:31]

Done.

+
+    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]))
+        ++curr;
+
+      size_t next = NextOrderedMapping(mappings, curr);
+      if (next == mappings.size())
+        break;

[Primiano Tucci (use gerrit), 2016/05/06 11:07:57]

isn't this going to ignore the big hole that you can fave between the last
mapping and the end of the address space?

[Tobias Sargeant, 2016/05/06 11:33:45]

It is, but we don't know exactly how big that hole is, because we don't know
where the end of the allocatable address space is. Same with space before the
first mapping. That's why we log the lowest and highest mapped addresses, and
the histogram of holes. That way we can work out what to do later.

[Primiano Tucci (use gerrit), 2016/05/06 13:29:23]

Hmm but then you will never know if that hole is the largest one or not.
Say that you have only two mappings:
1:[0x1000, 0x2000],
2: [0x3000, 0x4000]
You will conclude that your largest available hole is 0x1000 (0x3000 - 0x2000).
The reality instead is there was a huge gap after 2.

At this point probably the best thing to do is:
keep the hole logic as it is
dump also the lowest and highest mapped address. So we can work out the boundary
cases after the fact.

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

This is what happens. The log line is:

H lo_addr hi_addr hole_cnt hole_max hole sum [bucket:count]*

+
+      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_tot += hole_sz;
+        hole_max = std::max(hole_sz, hole_max);
+        ++hole_cnt;
+        size_t h = 0;
+        while (hole_sz) {

[Primiano Tucci (use gerrit), 2016/05/06 11:07:56]

Can we just copy chrome base::Log2Floor(uint32_t n) and use it here?
This is going to loop x32 on every mapping.

[Tobias Sargeant, 2016/05/06 13:29:31]

Done.

+          ++h;
+          hole_sz >>= 1;
+        }
+        ++hole_hist[h];
+      }
+      curr = next;
+    }
+
+    uintptr_t hi_addr = mappings[curr]->start_addr + mappings[curr]->size;
+
+    LogAppend("H ");
+    LogAppend(lo_addr);
+    LogAppend(" ");
+    LogAppend(hi_addr);
+
+    LogAppend(" "); LogAppendDecimal(hole_cnt);

[Primiano Tucci (use gerrit), 2016/05/06 11:07:56]

are you appending the count three times here? 
I suppose you meant to append tot, cnt and sum?

[Tobias Sargeant, 2016/05/06 13:29:31]

Certainly did!

+    LogAppend(" "); LogAppend(hole_cnt);

[Primiano Tucci (use gerrit), 2016/05/06 11:07:56]

Also plz newlines after each statement

[Tobias Sargeant, 2016/05/06 13:29:31]

Done.

+    LogAppend(" "); LogAppend(hole_cnt);
+    for (unsigned int i = 0; i < HBITS; ++i) {

[Primiano Tucci (use gerrit), 2016/05/06 11:07:57]

can we saturate this up and down?
First of all, all your holes will be at least 4k big. So the buckets 0-11 should
always be zero.
Also I think we want to cap up at ~1GB. Not sure we (chrome) should rely on
having more thatn 1GB of contiguous address space.
Also for 64bit this line is going to be loooooooooooooooooong and perhaps
overflow the logcat limit.

[Torne, 2016/05/06 11:13:36]

We should probably just not do this at all on 64bit, there's no point.

[Tobias Sargeant, 2016/05/06 11:33:45]

I'm not sure we want to cap at 1GB. On 32 bit that really only saves one extra
bucket, and on 64 bit I'd guess that there aren't going to be many address
ranges in the tail (and we could also just skip this entirely for 64 bit as
torne suggested).

I didn't want to make any assumptions about page size, so I figured the easiest
approach was just to skip zero entries in the histogram, which would have the
effect of not outputting anything for values smaller than the page size
(whatever that happened to be).

[Primiano Tucci (use gerrit), 2016/05/06 13:29:23]

ok sorry I completely missed the if (!hole_hist[i]) continue; statement.
Makes sense to keep this as it as long as we omit zeros.

[Primiano Tucci (use gerrit), 2016/05/06 13:29:23]

SGTM but nothing in this CL is preventing this to happen on 64 bit

+      if (!hole_hist[i]) continue;
+      LogAppend(" ");
+      LogAppendDecimal(i);
+      LogAppend(":");
+      LogAppendDecimal(hole_hist[i]);
+    }
+    LogCommitLine();
+    return true;
+  }
+
   // Write information about the mappings in effect.
   bool DumpMappings() {
     // First write all the mappings from the dumper