[Heap profiler] Add construction stack trace to heap object

src/allocation-tracker.cc

Index: src/allocation-tracker.cc
diff --git a/src/allocation-tracker.cc b/src/allocation-tracker.cc
index ecc7a4ca4d25e8d3660538a47c85394e117550d3..3637719e095985213a119fbc04009be80d2650ff 100644
--- a/src/allocation-tracker.cc
+++ b/src/allocation-tracker.cc
@@ -139,6 +139,99 @@ AllocationTracker::FunctionInfo::FunctionInfo()
 }
 
 
+void AddressToTraceMap::AddRange(Address start, int size,
+                                 unsigned trace_node_id) {
+  Address end = start + size;
+  RemoveRange(start, end);
+
+  RangeStack new_range(end, trace_node_id);
+  ranges_.insert(RangeMap::value_type(start, new_range));

[alph, 2014/03/06 14:43:18]

I have a feeling that using the 'end' address as a key might simplify the lookup
algorithm.

[yurys, 2014/03/06 15:38:49]

Good point, thank you! I rewrote this part to use interval end as key.

+}
+
+
+unsigned AddressToTraceMap::GetTraceNodeId(Address addr) {
+  RangeMap::const_iterator it = ranges_.lower_bound(addr);
+  if (it == ranges_.end()) {
+    if (it == ranges_.begin()) return 0;
+    --it;
+    if (it->first <= addr && addr < it->second.end) {

[alph, 2014/03/06 14:43:18]

it->first <= addr seems to be always true.

[yurys, 2014/03/06 15:38:49]

This code is gone.

+      return it->second.trace_node_id;
+    }
+    return 0;
+  }
+
+  if (it->first == addr) return it->second.trace_node_id;

[alph, 2014/03/06 14:43:18]

if you use upper_bound instead you won't need to do this check.

[yurys, 2014/03/06 15:38:49]

Done.

+  if (it == ranges_.begin()) return 0;
+  --it;
+  if (it->first <= addr && addr < it->second.end) {

[alph, 2014/03/06 14:43:18]

ditto for it->first <= addr

[yurys, 2014/03/06 15:38:49]

Done.

+    return it->second.trace_node_id;
+  }
+  return 0;
+}
+
+
+void AddressToTraceMap::MoveObject(Address from, Address to, int size) {
+  unsigned trace_node_id = GetTraceNodeId(from);
+  if (trace_node_id == 0) return;
+  RemoveRange(from, from + size);
+  AddRange(to, size, trace_node_id);
+}
+
+
+void AddressToTraceMap::Clear() {
+  ranges_.clear();
+}
+
+
+void AddressToTraceMap::Print() {
+  PrintF("[AddressToTraceMap (%lu): \n", ranges_.size());
+  for (RangeMap::iterator it = ranges_.begin(); it != ranges_.end(); ++it) {
+    PrintF("[%p - %p] => %u\n", it->first, it->second.end,
+        it->second.trace_node_id);
+  }
+  PrintF("]\n");
+}
+
+
+void AddressToTraceMap::RemoveRange(Address start, Address end) {
+  RangeMap::iterator it = ranges_.upper_bound(start);
+
+  Address next_range_start = 0;
+  RangeStack next_range(0, 0);
+
+  RangeMap::iterator to_remove_begin = it;
+  if (it != ranges_.begin()) {
+    --it;
+    RangeStack& value = it->second;
+    if (value.end > start) {
+      if (value.end > end) {
+        next_range_start = end;
+        next_range = value;
+      }
+      if (it->first == start) {
+        to_remove_begin = it;
+      } else {
+        value.end = start;
+      }
+    }
+    ++it;
+  }
+
+  while (it != ranges_.end() &&  it->first < end) {

[alph, 2014/03/06 14:43:18]

extra space

[yurys, 2014/03/06 15:38:49]

Done.

+    if (it->second.end > end) {
+      next_range_start = end;
+      next_range = it->second;
+    }
+    ++it;
+  }
+  ranges_.erase(to_remove_begin, it);
+
+  if (next_range_start != 0) {
+    ranges_.insert(RangeMap::value_type(next_range_start, next_range));
+  }
+}
+
+
 static bool AddressesMatch(void* key1, void* key2) {
   return key1 == key2;
 }
@@ -208,6 +301,8 @@ void AllocationTracker::AllocationEvent(Address addr, int size) {
   AllocationTraceNode* top_node = trace_tree_.AddPathFromEnd(
       Vector<unsigned>(allocation_trace_buffer_, length));
   top_node->AddAllocation(size);
+
+  address_to_trace_.AddRange(addr, size, top_node->id());
 }