1 // Copyright 2015 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/profiler/sampling-heap-profiler.h" 6 7 #include <stdint.h> 8 #include <memory> 9 #include "src/api.h" 10 #include "src/base/ieee754.h" 11 #include "src/base/utils/random-number-generator.h" 12 #include "src/frames-inl.h" 13 #include "src/heap/heap.h" 14 #include "src/isolate.h" 15 #include "src/profiler/strings-storage.h" 16 17 namespace v8 { 18 namespace internal { 19 20 // We sample with a Poisson process, with constant average sampling interval. 21 // This follows the exponential probability distribution with parameter 22 // = 1/rate where rate is the average number of bytes between samples. 23 // 24 // Let u be a uniformly distributed random number between 0 and 1, then 25 // next_sample = (- ln u) / 26 intptr_t SamplingAllocationObserver::GetNextSampleInterval(uint64_t rate) { 27 if (FLAG_sampling_heap_profiler_suppress_randomness) { 28 return static_cast<intptr_t>(rate); 29 } 30 double u = random_->NextDouble(); 31 double next = (-base::ieee754::log(u)) * rate; 32 return next < kPointerSize 33 ? kPointerSize 34 : (next > INT_MAX ? INT_MAX : static_cast<intptr_t>(next)); 35 } 36 37 // Samples were collected according to a poisson process. Since we have not 38 // recorded all allocations, we must approximate the shape of the underlying 39 // space of allocations based on the samples we have collected. Given that 40 // we sample at rate R, the probability that an allocation of size S will be 41 // sampled is 1-exp(-S/R). This function uses the above probability to 42 // approximate the true number of allocations with size *size* given that 43 // *count* samples were observed. 44 v8::AllocationProfile::Allocation SamplingHeapProfiler::ScaleSample( 45 size_t size, unsigned int count) { 46 double scale = 1.0 / (1.0 - std::exp(-static_cast<double>(size) / rate_)); 47 // Round count instead of truncating. 48 return {size, static_cast<unsigned int>(count * scale + 0.5)}; 49 } 50 51 SamplingHeapProfiler::SamplingHeapProfiler( 52 Heap* heap, StringsStorage* names, uint64_t rate, int stack_depth, 53 v8::HeapProfiler::SamplingFlags flags) 54 : isolate_(heap->isolate()), 55 heap_(heap), 56 new_space_observer_(new SamplingAllocationObserver( 57 heap_, static_cast<intptr_t>(rate), rate, this, 58 heap->isolate()->random_number_generator())), 59 other_spaces_observer_(new SamplingAllocationObserver( 60 heap_, static_cast<intptr_t>(rate), rate, this, 61 heap->isolate()->random_number_generator())), 62 names_(names), 63 profile_root_(nullptr, "(root)", v8::UnboundScript::kNoScriptId, 0), 64 samples_(), 65 stack_depth_(stack_depth), 66 rate_(rate), 67 flags_(flags) { 68 CHECK_GT(rate_, 0u); 69 heap->new_space()->AddAllocationObserver(new_space_observer_.get()); 70 AllSpaces spaces(heap); 71 for (Space* space = spaces.next(); space != nullptr; space = spaces.next()) { 72 if (space != heap->new_space()) { 73 space->AddAllocationObserver(other_spaces_observer_.get()); 74 } 75 } 76 } 77 78 79 SamplingHeapProfiler::~SamplingHeapProfiler() { 80 heap_->new_space()->RemoveAllocationObserver(new_space_observer_.get()); 81 AllSpaces spaces(heap_); 82 for (Space* space = spaces.next(); space != nullptr; space = spaces.next()) { 83 if (space != heap_->new_space()) { 84 space->RemoveAllocationObserver(other_spaces_observer_.get()); 85 } 86 } 87 88 for (auto sample : samples_) { 89 delete sample; 90 } 91 std::set<Sample*> empty; 92 samples_.swap(empty); 93 } 94 95 96 void SamplingHeapProfiler::SampleObject(Address soon_object, size_t size) { 97 DisallowHeapAllocation no_allocation; 98 99 HandleScope scope(isolate_); 100 HeapObject* heap_object = HeapObject::FromAddress(soon_object); 101 Handle<Object> obj(heap_object, isolate_); 102 103 // Mark the new block as FreeSpace to make sure the heap is iterable while we 104 // are taking the sample. 105 heap()->CreateFillerObjectAt(soon_object, static_cast<int>(size), 106 ClearRecordedSlots::kNo); 107 108 Local<v8::Value> loc = v8::Utils::ToLocal(obj); 109 110 AllocationNode* node = AddStack(); 111 node->allocations_[size]++; 112 Sample* sample = new Sample(size, node, loc, this); 113 samples_.insert(sample); 114 sample->global.SetWeak(sample, OnWeakCallback, WeakCallbackType::kParameter); 115 sample->global.MarkIndependent(); 116 } 117 118 void SamplingHeapProfiler::OnWeakCallback( 119 const WeakCallbackInfo<Sample>& data) { 120 Sample* sample = data.GetParameter(); 121 AllocationNode* node = sample->owner; 122 DCHECK(node->allocations_[sample->size] > 0); 123 node->allocations_[sample->size]--; 124 if (node->allocations_[sample->size] == 0) { 125 node->allocations_.erase(sample->size); 126 while (node->allocations_.empty() && node->children_.empty() && 127 node->parent_ && !node->parent_->pinned_) { 128 AllocationNode* parent = node->parent_; 129 AllocationNode::FunctionId id = AllocationNode::function_id( 130 node->script_id_, node->script_position_, node->name_); 131 parent->children_.erase(id); 132 delete node; 133 node = parent; 134 } 135 } 136 sample->profiler->samples_.erase(sample); 137 delete sample; 138 } 139 140 SamplingHeapProfiler::AllocationNode* 141 SamplingHeapProfiler::AllocationNode::FindOrAddChildNode(const char* name, 142 int script_id, 143 int start_position) { 144 FunctionId id = function_id(script_id, start_position, name); 145 auto it = children_.find(id); 146 if (it != children_.end()) { 147 DCHECK(strcmp(it->second->name_, name) == 0); 148 return it->second; 149 } 150 auto child = new AllocationNode(this, name, script_id, start_position); 151 children_.insert(std::make_pair(id, child)); 152 return child; 153 } 154 155 SamplingHeapProfiler::AllocationNode* SamplingHeapProfiler::AddStack() { 156 AllocationNode* node = &profile_root_; 157 158 std::vector<SharedFunctionInfo*> stack; 159 JavaScriptFrameIterator it(isolate_); 160 int frames_captured = 0; 161 while (!it.done() && frames_captured < stack_depth_) { 162 JavaScriptFrame* frame = it.frame(); 163 SharedFunctionInfo* shared = frame->function()->shared(); 164 stack.push_back(shared); 165 166 frames_captured++; 167 it.Advance(); 168 } 169 170 if (frames_captured == 0) { 171 const char* name = nullptr; 172 switch (isolate_->current_vm_state()) { 173 case GC: 174 name = "(GC)"; 175 break; 176 case COMPILER: 177 name = "(COMPILER)"; 178 break; 179 case OTHER: 180 name = "(V8 API)"; 181 break; 182 case EXTERNAL: 183 name = "(EXTERNAL)"; 184 break; 185 case IDLE: 186 name = "(IDLE)"; 187 break; 188 case JS: 189 name = "(JS)"; 190 break; 191 } 192 return node->FindOrAddChildNode(name, v8::UnboundScript::kNoScriptId, 0); 193 } 194 195 // We need to process the stack in reverse order as the top of the stack is 196 // the first element in the list. 197 for (auto it = stack.rbegin(); it != stack.rend(); ++it) { 198 SharedFunctionInfo* shared = *it; 199 const char* name = this->names()->GetFunctionName(shared->DebugName()); 200 int script_id = v8::UnboundScript::kNoScriptId; 201 if (shared->script()->IsScript()) { 202 Script* script = Script::cast(shared->script()); 203 script_id = script->id(); 204 } 205 node = node->FindOrAddChildNode(name, script_id, shared->start_position()); 206 } 207 return node; 208 } 209 210 v8::AllocationProfile::Node* SamplingHeapProfiler::TranslateAllocationNode( 211 AllocationProfile* profile, SamplingHeapProfiler::AllocationNode* node, 212 const std::map<int, Handle<Script>>& scripts) { 213 // By pinning the node we make sure its children won't get disposed if 214 // a GC kicks in during the tree retrieval. 215 node->pinned_ = true; 216 Local<v8::String> script_name = 217 ToApiHandle<v8::String>(isolate_->factory()->InternalizeUtf8String("")); 218 int line = v8::AllocationProfile::kNoLineNumberInfo; 219 int column = v8::AllocationProfile::kNoColumnNumberInfo; 220 std::vector<v8::AllocationProfile::Allocation> allocations; 221 allocations.reserve(node->allocations_.size()); 222 if (node->script_id_ != v8::UnboundScript::kNoScriptId && 223 scripts.find(node->script_id_) != scripts.end()) { 224 // Cannot use std::map<T>::at because it is not available on android. 225 auto non_const_scripts = 226 const_cast<std::map<int, Handle<Script>>&>(scripts); 227 Handle<Script> script = non_const_scripts[node->script_id_]; 228 if (!script.is_null()) { 229 if (script->name()->IsName()) { 230 Name* name = Name::cast(script->name()); 231 script_name = ToApiHandle<v8::String>( 232 isolate_->factory()->InternalizeUtf8String(names_->GetName(name))); 233 } 234 line = 1 + Script::GetLineNumber(script, node->script_position_); 235 column = 1 + Script::GetColumnNumber(script, node->script_position_); 236 } 237 } 238 for (auto alloc : node->allocations_) { 239 allocations.push_back(ScaleSample(alloc.first, alloc.second)); 240 } 241 242 profile->nodes().push_back(v8::AllocationProfile::Node( 243 {ToApiHandle<v8::String>( 244 isolate_->factory()->InternalizeUtf8String(node->name_)), 245 script_name, node->script_id_, node->script_position_, line, column, 246 std::vector<v8::AllocationProfile::Node*>(), allocations})); 247 v8::AllocationProfile::Node* current = &profile->nodes().back(); 248 // The children map may have nodes inserted into it during translation 249 // because the translation may allocate strings on the JS heap that have 250 // the potential to be sampled. That's ok since map iterators are not 251 // invalidated upon std::map insertion. 252 for (auto it : node->children_) { 253 current->children.push_back( 254 TranslateAllocationNode(profile, it.second, scripts)); 255 } 256 node->pinned_ = false; 257 return current; 258 } 259 260 v8::AllocationProfile* SamplingHeapProfiler::GetAllocationProfile() { 261 if (flags_ & v8::HeapProfiler::kSamplingForceGC) { 262 isolate_->heap()->CollectAllGarbage( 263 Heap::kNoGCFlags, GarbageCollectionReason::kSamplingProfiler); 264 } 265 // To resolve positions to line/column numbers, we will need to look up 266 // scripts. Build a map to allow fast mapping from script id to script. 267 std::map<int, Handle<Script>> scripts; 268 { 269 Script::Iterator iterator(isolate_); 270 while (Script* script = iterator.Next()) { 271 scripts[script->id()] = handle(script); 272 } 273 } 274 auto profile = new v8::internal::AllocationProfile(); 275 TranslateAllocationNode(profile, &profile_root_, scripts); 276 return profile; 277 } 278 279 280 } // namespace internal 281 } // namespace v8 282
