[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(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;
 }
 
 
 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