1// Copyright 2013 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "src/v8.h"
6
7#include "src/allocation-tracker.h"
8#include "src/frames-inl.h"
9#include "src/heap-snapshot-generator.h"
10
11namespace v8 {
12namespace internal {
13
14AllocationTraceNode::AllocationTraceNode(
15    AllocationTraceTree* tree, unsigned function_info_index)
16    : tree_(tree),
17      function_info_index_(function_info_index),
18      total_size_(0),
19      allocation_count_(0),
20      id_(tree->next_node_id()) {
21}
22
23
24AllocationTraceNode::~AllocationTraceNode() {
25  for (int i = 0; i < children_.length(); i++) delete children_[i];
26}
27
28
29AllocationTraceNode* AllocationTraceNode::FindChild(
30    unsigned function_info_index) {
31  for (int i = 0; i < children_.length(); i++) {
32    AllocationTraceNode* node = children_[i];
33    if (node->function_info_index() == function_info_index) return node;
34  }
35  return NULL;
36}
37
38
39AllocationTraceNode* AllocationTraceNode::FindOrAddChild(
40    unsigned function_info_index) {
41  AllocationTraceNode* child = FindChild(function_info_index);
42  if (child == NULL) {
43    child = new AllocationTraceNode(tree_, function_info_index);
44    children_.Add(child);
45  }
46  return child;
47}
48
49
50void AllocationTraceNode::AddAllocation(unsigned size) {
51  total_size_ += size;
52  ++allocation_count_;
53}
54
55
56void AllocationTraceNode::Print(int indent, AllocationTracker* tracker) {
57  base::OS::Print("%10u %10u %*c", total_size_, allocation_count_, indent, ' ');
58  if (tracker != NULL) {
59    AllocationTracker::FunctionInfo* info =
60        tracker->function_info_list()[function_info_index_];
61    base::OS::Print("%s #%u", info->name, id_);
62  } else {
63    base::OS::Print("%u #%u", function_info_index_, id_);
64  }
65  base::OS::Print("\n");
66  indent += 2;
67  for (int i = 0; i < children_.length(); i++) {
68    children_[i]->Print(indent, tracker);
69  }
70}
71
72
73AllocationTraceTree::AllocationTraceTree()
74    : next_node_id_(1),
75      root_(this, 0) {
76}
77
78
79AllocationTraceTree::~AllocationTraceTree() {
80}
81
82
83AllocationTraceNode* AllocationTraceTree::AddPathFromEnd(
84    const Vector<unsigned>& path) {
85  AllocationTraceNode* node = root();
86  for (unsigned* entry = path.start() + path.length() - 1;
87       entry != path.start() - 1;
88       --entry) {
89    node = node->FindOrAddChild(*entry);
90  }
91  return node;
92}
93
94
95void AllocationTraceTree::Print(AllocationTracker* tracker) {
96  base::OS::Print("[AllocationTraceTree:]\n");
97  base::OS::Print("Total size | Allocation count | Function id | id\n");
98  root()->Print(0, tracker);
99}
100
101
102void AllocationTracker::DeleteUnresolvedLocation(
103    UnresolvedLocation** location) {
104  delete *location;
105}
106
107
108AllocationTracker::FunctionInfo::FunctionInfo()
109    : name(""),
110      function_id(0),
111      script_name(""),
112      script_id(0),
113      line(-1),
114      column(-1) {
115}
116
117
118void AddressToTraceMap::AddRange(Address start, int size,
119                                 unsigned trace_node_id) {
120  Address end = start + size;
121  RemoveRange(start, end);
122
123  RangeStack new_range(start, trace_node_id);
124  ranges_.insert(RangeMap::value_type(end, new_range));
125}
126
127
128unsigned AddressToTraceMap::GetTraceNodeId(Address addr) {
129  RangeMap::const_iterator it = ranges_.upper_bound(addr);
130  if (it == ranges_.end()) return 0;
131  if (it->second.start <= addr) {
132    return it->second.trace_node_id;
133  }
134  return 0;
135}
136
137
138void AddressToTraceMap::MoveObject(Address from, Address to, int size) {
139  unsigned trace_node_id = GetTraceNodeId(from);
140  if (trace_node_id == 0) return;
141  RemoveRange(from, from + size);
142  AddRange(to, size, trace_node_id);
143}
144
145
146void AddressToTraceMap::Clear() {
147  ranges_.clear();
148}
149
150
151void AddressToTraceMap::Print() {
152  PrintF("[AddressToTraceMap (%" V8PRIuPTR "): \n", ranges_.size());
153  for (RangeMap::iterator it = ranges_.begin(); it != ranges_.end(); ++it) {
154    PrintF("[%p - %p] => %u\n", it->second.start, it->first,
155        it->second.trace_node_id);
156  }
157  PrintF("]\n");
158}
159
160
161void AddressToTraceMap::RemoveRange(Address start, Address end) {
162  RangeMap::iterator it = ranges_.upper_bound(start);
163  if (it == ranges_.end()) return;
164
165  RangeStack prev_range(0, 0);
166
167  RangeMap::iterator to_remove_begin = it;
168  if (it->second.start < start) {
169    prev_range = it->second;
170  }
171  do {
172    if (it->first > end) {
173      if (it->second.start < end) {
174        it->second.start = end;
175      }
176      break;
177    }
178    ++it;
179  }
180  while (it != ranges_.end());
181
182  ranges_.erase(to_remove_begin, it);
183
184  if (prev_range.start != 0) {
185    ranges_.insert(RangeMap::value_type(start, prev_range));
186  }
187}
188
189
190void AllocationTracker::DeleteFunctionInfo(FunctionInfo** info) {
191    delete *info;
192}
193
194
195AllocationTracker::AllocationTracker(
196    HeapObjectsMap* ids, StringsStorage* names)
197    : ids_(ids),
198      names_(names),
199      id_to_function_info_index_(HashMap::PointersMatch),
200      info_index_for_other_state_(0) {
201  FunctionInfo* info = new FunctionInfo();
202  info->name = "(root)";
203  function_info_list_.Add(info);
204}
205
206
207AllocationTracker::~AllocationTracker() {
208  unresolved_locations_.Iterate(DeleteUnresolvedLocation);
209  function_info_list_.Iterate(&DeleteFunctionInfo);
210}
211
212
213void AllocationTracker::PrepareForSerialization() {
214  List<UnresolvedLocation*> copy(unresolved_locations_.length());
215  copy.AddAll(unresolved_locations_);
216  unresolved_locations_.Clear();
217  for (int i = 0; i < copy.length(); i++) {
218    copy[i]->Resolve();
219    delete copy[i];
220  }
221}
222
223
224void AllocationTracker::AllocationEvent(Address addr, int size) {
225  DisallowHeapAllocation no_allocation;
226  Heap* heap = ids_->heap();
227
228  // Mark the new block as FreeSpace to make sure the heap is iterable
229  // while we are capturing stack trace.
230  FreeListNode::FromAddress(addr)->set_size(heap, size);
231  DCHECK_EQ(HeapObject::FromAddress(addr)->Size(), size);
232  DCHECK(FreeListNode::IsFreeListNode(HeapObject::FromAddress(addr)));
233
234  Isolate* isolate = heap->isolate();
235  int length = 0;
236  StackTraceFrameIterator it(isolate);
237  while (!it.done() && length < kMaxAllocationTraceLength) {
238    JavaScriptFrame* frame = it.frame();
239    SharedFunctionInfo* shared = frame->function()->shared();
240    SnapshotObjectId id = ids_->FindOrAddEntry(
241        shared->address(), shared->Size(), false);
242    allocation_trace_buffer_[length++] = AddFunctionInfo(shared, id);
243    it.Advance();
244  }
245  if (length == 0) {
246    unsigned index = functionInfoIndexForVMState(isolate->current_vm_state());
247    if (index != 0) {
248      allocation_trace_buffer_[length++] = index;
249    }
250  }
251  AllocationTraceNode* top_node = trace_tree_.AddPathFromEnd(
252      Vector<unsigned>(allocation_trace_buffer_, length));
253  top_node->AddAllocation(size);
254
255  address_to_trace_.AddRange(addr, size, top_node->id());
256}
257
258
259static uint32_t SnapshotObjectIdHash(SnapshotObjectId id) {
260  return ComputeIntegerHash(static_cast<uint32_t>(id),
261                            v8::internal::kZeroHashSeed);
262}
263
264
265unsigned AllocationTracker::AddFunctionInfo(SharedFunctionInfo* shared,
266                                            SnapshotObjectId id) {
267  HashMap::Entry* entry = id_to_function_info_index_.Lookup(
268      reinterpret_cast<void*>(id), SnapshotObjectIdHash(id), true);
269  if (entry->value == NULL) {
270    FunctionInfo* info = new FunctionInfo();
271    info->name = names_->GetFunctionName(shared->DebugName());
272    info->function_id = id;
273    if (shared->script()->IsScript()) {
274      Script* script = Script::cast(shared->script());
275      if (script->name()->IsName()) {
276        Name* name = Name::cast(script->name());
277        info->script_name = names_->GetName(name);
278      }
279      info->script_id = script->id()->value();
280      // Converting start offset into line and column may cause heap
281      // allocations so we postpone them until snapshot serialization.
282      unresolved_locations_.Add(new UnresolvedLocation(
283          script,
284          shared->start_position(),
285          info));
286    }
287    entry->value = reinterpret_cast<void*>(function_info_list_.length());
288    function_info_list_.Add(info);
289  }
290  return static_cast<unsigned>(reinterpret_cast<intptr_t>((entry->value)));
291}
292
293
294unsigned AllocationTracker::functionInfoIndexForVMState(StateTag state) {
295  if (state != OTHER) return 0;
296  if (info_index_for_other_state_ == 0) {
297    FunctionInfo* info = new FunctionInfo();
298    info->name = "(V8 API)";
299    info_index_for_other_state_ = function_info_list_.length();
300    function_info_list_.Add(info);
301  }
302  return info_index_for_other_state_;
303}
304
305
306AllocationTracker::UnresolvedLocation::UnresolvedLocation(
307    Script* script, int start, FunctionInfo* info)
308    : start_position_(start),
309      info_(info) {
310  script_ = Handle<Script>::cast(
311      script->GetIsolate()->global_handles()->Create(script));
312  GlobalHandles::MakeWeak(reinterpret_cast<Object**>(script_.location()),
313                          this,
314                          &HandleWeakScript);
315}
316
317
318AllocationTracker::UnresolvedLocation::~UnresolvedLocation() {
319  if (!script_.is_null()) {
320    GlobalHandles::Destroy(reinterpret_cast<Object**>(script_.location()));
321  }
322}
323
324
325void AllocationTracker::UnresolvedLocation::Resolve() {
326  if (script_.is_null()) return;
327  HandleScope scope(script_->GetIsolate());
328  info_->line = Script::GetLineNumber(script_, start_position_);
329  info_->column = Script::GetColumnNumber(script_, start_position_);
330}
331
332
333void AllocationTracker::UnresolvedLocation::HandleWeakScript(
334    const v8::WeakCallbackData<v8::Value, void>& data) {
335  UnresolvedLocation* loc =
336      reinterpret_cast<UnresolvedLocation*>(data.GetParameter());
337  GlobalHandles::Destroy(reinterpret_cast<Object**>(loc->script_.location()));
338  loc->script_ = Handle<Script>::null();
339}
340
341
342} }  // namespace v8::internal
343