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 11 namespace v8 { 12 namespace internal { 13 14 AllocationTraceNode::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 24 AllocationTraceNode::~AllocationTraceNode() { 25 for (int i = 0; i < children_.length(); i++) delete children_[i]; 26 } 27 28 29 AllocationTraceNode* 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 39 AllocationTraceNode* 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 50 void AllocationTraceNode::AddAllocation(unsigned size) { 51 total_size_ += size; 52 ++allocation_count_; 53 } 54 55 56 void 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 73 AllocationTraceTree::AllocationTraceTree() 74 : next_node_id_(1), 75 root_(this, 0) { 76 } 77 78 79 AllocationTraceTree::~AllocationTraceTree() { 80 } 81 82 83 AllocationTraceNode* 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 95 void 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 102 void AllocationTracker::DeleteUnresolvedLocation( 103 UnresolvedLocation** location) { 104 delete *location; 105 } 106 107 108 AllocationTracker::FunctionInfo::FunctionInfo() 109 : name(""), 110 function_id(0), 111 script_name(""), 112 script_id(0), 113 line(-1), 114 column(-1) { 115 } 116 117 118 void 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 128 unsigned 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 138 void 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 146 void AddressToTraceMap::Clear() { 147 ranges_.clear(); 148 } 149 150 151 void 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 161 void 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 190 void AllocationTracker::DeleteFunctionInfo(FunctionInfo** info) { 191 delete *info; 192 } 193 194 195 AllocationTracker::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 207 AllocationTracker::~AllocationTracker() { 208 unresolved_locations_.Iterate(DeleteUnresolvedLocation); 209 function_info_list_.Iterate(&DeleteFunctionInfo); 210 } 211 212 213 void 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 224 void 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 259 static uint32_t SnapshotObjectIdHash(SnapshotObjectId id) { 260 return ComputeIntegerHash(static_cast<uint32_t>(id), 261 v8::internal::kZeroHashSeed); 262 } 263 264 265 unsigned 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 294 unsigned 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 306 AllocationTracker::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 318 AllocationTracker::UnresolvedLocation::~UnresolvedLocation() { 319 if (!script_.is_null()) { 320 GlobalHandles::Destroy(reinterpret_cast<Object**>(script_.location())); 321 } 322 } 323 324 325 void 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 333 void 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