[Heap profiler] Add construction stack trace to heap object

src/allocation-tracker.cc

 // Copyright 2013 the V8 project authors. 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
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 121 matching lines @@
 AllocationTracker::FunctionInfo::FunctionInfo()
     : name(""),
       function_id(0),
       script_name(""),
       script_id(0),
       line(-1),
       column(-1) {
 }
 
 
+void AddressToTraceMap::AddRange(Address start, int size,
+                                 unsigned trace_node_id) {
+  Address end = start + size;
+  RemoveRange(start, end);
+
+  RangeStack new_range(start, trace_node_id);
+  ranges_.insert(RangeMap::value_type(end, new_range));
+}
+
+
+unsigned AddressToTraceMap::GetTraceNodeId(Address addr) {
+  RangeMap::const_iterator it = ranges_.upper_bound(addr);
+  if (it == ranges_.end()) return 0;
+  if (it->second.start <= addr) {
+    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->second.start, it->first,
+        it->second.trace_node_id);
+  }
+  PrintF("]\n");
+}
+
+
+void AddressToTraceMap::RemoveRange(Address start, Address end) {
+  RangeMap::iterator it = ranges_.upper_bound(start);
+  if (it == ranges_.end()) return;
+
+  RangeStack prev_range(0, 0);
+
+  RangeMap::iterator to_remove_begin = it;
+  if (it->second.start < start) {
+    prev_range = it->second;
+  }
+  do {

[alph, 2014/03/06 16:11:01]

Could you please rewrite do-while to something like:

for (; it != ranges_.end() && it->first <= end; ++it) { }
if (it->second.start < end) {
  it->second.start = end;
}

[yurys, 2014/03/06 16:25:36]

I started with that but it was one unnecessary check it != ranges_.end(). Also
your code misses it != ranges_.end() check in the if. So I'd leave it as is.

+    if (it->first > end) {
+      if (it->second.start < end) {
+        it->second.start = end;
+      }
+      break;
+    }
+    ++it;
+  }
+  while (it != ranges_.end());
+
+  ranges_.erase(to_remove_begin, it);
+
+  if (prev_range.start != 0) {
+    ranges_.insert(RangeMap::value_type(start, prev_range));
+  }
+}
+
+
 static bool AddressesMatch(void* key1, void* key2) {
   return key1 == key2;
 }
 
 
 void AllocationTracker::DeleteFunctionInfo(FunctionInfo** info) {
     delete *info;
 }
 
 
@@ skipping 49 matching lines @@
   }
   if (length == 0) {
     unsigned index = functionInfoIndexForVMState(isolate->current_vm_state());
     if (index != 0) {
       allocation_trace_buffer_[length++] = index;
     }
   }
   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());
 }
 
 
 static uint32_t SnapshotObjectIdHash(SnapshotObjectId id) {
   return ComputeIntegerHash(static_cast<uint32_t>(id),
                             v8::internal::kZeroHashSeed);
 }
 
 
 unsigned AllocationTracker::AddFunctionInfo(SharedFunctionInfo* shared,
@@ skipping 67 matching lines @@
 void AllocationTracker::UnresolvedLocation::HandleWeakScript(
     const v8::WeakCallbackData<v8::Value, void>& data) {
   UnresolvedLocation* loc =
       reinterpret_cast<UnresolvedLocation*>(data.GetParameter());
   GlobalHandles::Destroy(reinterpret_cast<Object**>(loc->script_.location()));
   loc->script_ = Handle<Script>::null();
 }
 
 
 } }  // namespace v8::internal