1// Copyright 2011 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#ifndef V8_PROFILER_PROFILE_GENERATOR_H_
6#define V8_PROFILER_PROFILE_GENERATOR_H_
7
8#include <atomic>
9#include <deque>
10#include <limits>
11#include <map>
12#include <memory>
13#include <unordered_map>
14#include <utility>
15#include <vector>
16
17#include "include/v8-profiler.h"
18#include "src/base/platform/time.h"
19#include "src/builtins/builtins.h"
20#include "src/execution/vm-state.h"
21#include "src/logging/code-events.h"
22#include "src/profiler/output-stream-writer.h"
23#include "src/profiler/strings-storage.h"
24#include "src/utils/allocation.h"
25
26namespace v8 {
27namespace internal {
28
29struct TickSample;
30
31// Provides a mapping from the offsets within generated code or a bytecode array
32// to the source line and inlining id.
33class V8_EXPORT_PRIVATE SourcePositionTable : public Malloced {
34 public:
35  SourcePositionTable() = default;
36  SourcePositionTable(const SourcePositionTable&) = delete;
37  SourcePositionTable& operator=(const SourcePositionTable&) = delete;
38
39  void SetPosition(int pc_offset, int line, int inlining_id);
40  int GetSourceLineNumber(int pc_offset) const;
41  int GetInliningId(int pc_offset) const;
42
43  size_t Size() const;
44  void print() const;
45
46 private:
47  struct SourcePositionTuple {
48    bool operator<(const SourcePositionTuple& other) const {
49      return pc_offset < other.pc_offset;
50    }
51    int pc_offset;
52    int line_number;
53    int inlining_id;
54  };
55  // This is logically a map, but we store it as a vector of tuples, sorted by
56  // the pc offset, so that we can save space and look up items using binary
57  // search.
58  std::vector<SourcePositionTuple> pc_offsets_to_lines_;
59};
60
61struct CodeEntryAndLineNumber;
62
63class CodeEntry {
64 public:
65  enum class CodeType { JS, WASM, OTHER };
66
67  // CodeEntry may reference strings (|name|, |resource_name|) managed by a
68  // StringsStorage instance. These must be freed via ReleaseStrings.
69  inline CodeEntry(CodeEventListener::LogEventsAndTags tag, const char* name,
70                   const char* resource_name = CodeEntry::kEmptyResourceName,
71                   int line_number = v8::CpuProfileNode::kNoLineNumberInfo,
72                   int column_number = v8::CpuProfileNode::kNoColumnNumberInfo,
73                   std::unique_ptr<SourcePositionTable> line_info = nullptr,
74                   bool is_shared_cross_origin = false,
75                   CodeType code_type = CodeType::JS);
76  CodeEntry(const CodeEntry&) = delete;
77  CodeEntry& operator=(const CodeEntry&) = delete;
78  ~CodeEntry() {
79    // No alive handles should be associated with the CodeEntry at time of
80    // destruction.
81    DCHECK(!heap_object_location_);
82    DCHECK_EQ(ref_count_, 0UL);
83  }
84
85  const char* name() const { return name_; }
86  const char* resource_name() const { return resource_name_; }
87  int line_number() const { return line_number_; }
88  int column_number() const { return column_number_; }
89  const SourcePositionTable* line_info() const { return line_info_.get(); }
90  int script_id() const { return script_id_; }
91  void set_script_id(int script_id) { script_id_ = script_id; }
92  int position() const { return position_; }
93  void set_position(int position) { position_ = position; }
94  void set_bailout_reason(const char* bailout_reason) {
95    EnsureRareData()->bailout_reason_ = bailout_reason;
96  }
97  const char* bailout_reason() const {
98    return rare_data_ ? rare_data_->bailout_reason_ : kEmptyBailoutReason;
99  }
100
101  void set_deopt_info(const char* deopt_reason, int deopt_id,
102                      std::vector<CpuProfileDeoptFrame> inlined_frames);
103
104  size_t EstimatedSize() const;
105  CpuProfileDeoptInfo GetDeoptInfo();
106  bool has_deopt_info() const {
107    return rare_data_ && rare_data_->deopt_id_ != kNoDeoptimizationId;
108  }
109  void clear_deopt_info() {
110    if (!rare_data_) return;
111    // TODO(alph): Clear rare_data_ if that was the only field in use.
112    rare_data_->deopt_reason_ = kNoDeoptReason;
113    rare_data_->deopt_id_ = kNoDeoptimizationId;
114  }
115
116  const char* code_type_string() const {
117    switch (CodeTypeField::decode(bit_field_)) {
118      case CodeType::JS:
119        return "JS";
120      case CodeType::WASM:
121        return "wasm";
122      case CodeType::OTHER:
123        return "other";
124    }
125  }
126
127  // Returns the start address of the instruction segment represented by this
128  // CodeEntry. Used as a key in the containing CodeMap.
129  Address instruction_start() const { return instruction_start_; }
130  void set_instruction_start(Address address) { instruction_start_ = address; }
131
132  Address** heap_object_location_address() { return &heap_object_location_; }
133
134  void FillFunctionInfo(SharedFunctionInfo shared);
135
136  void SetBuiltinId(Builtin id);
137  Builtin builtin() const { return BuiltinField::decode(bit_field_); }
138
139  bool is_shared_cross_origin() const {
140    return SharedCrossOriginField::decode(bit_field_);
141  }
142
143  // Returns whether or not the lifetime of this CodeEntry is reference
144  // counted, and managed by a CodeMap.
145  bool is_ref_counted() const { return RefCountedField::decode(bit_field_); }
146
147  uint32_t GetHash() const;
148  bool IsSameFunctionAs(const CodeEntry* entry) const;
149
150  int GetSourceLine(int pc_offset) const;
151
152  struct Equals {
153    bool operator()(const CodeEntry* lhs, const CodeEntry* rhs) const {
154      return lhs->IsSameFunctionAs(rhs);
155    }
156  };
157  struct Hasher {
158    std::size_t operator()(CodeEntry* e) const { return e->GetHash(); }
159  };
160
161  void SetInlineStacks(
162      std::unordered_set<CodeEntry*, Hasher, Equals> inline_entries,
163      std::unordered_map<int, std::vector<CodeEntryAndLineNumber>>
164          inline_stacks);
165  const std::vector<CodeEntryAndLineNumber>* GetInlineStack(
166      int pc_offset) const;
167
168  CodeEventListener::LogEventsAndTags tag() const {
169    return TagField::decode(bit_field_);
170  }
171
172  V8_EXPORT_PRIVATE static const char* const kEmptyResourceName;
173  static const char* const kEmptyBailoutReason;
174  static const char* const kNoDeoptReason;
175
176  V8_EXPORT_PRIVATE static const char* const kProgramEntryName;
177  V8_EXPORT_PRIVATE static const char* const kIdleEntryName;
178  V8_EXPORT_PRIVATE static const char* const kGarbageCollectorEntryName;
179  // Used to represent frames for which we have no reliable way to
180  // detect function.
181  V8_EXPORT_PRIVATE static const char* const kUnresolvedFunctionName;
182  V8_EXPORT_PRIVATE static const char* const kRootEntryName;
183
184  V8_EXPORT_PRIVATE static CodeEntry* program_entry();
185  V8_EXPORT_PRIVATE static CodeEntry* idle_entry();
186  V8_EXPORT_PRIVATE static CodeEntry* gc_entry();
187  V8_EXPORT_PRIVATE static CodeEntry* unresolved_entry();
188  V8_EXPORT_PRIVATE static CodeEntry* root_entry();
189
190  // Releases strings owned by this CodeEntry, which may be allocated in the
191  // provided StringsStorage instance. This instance is not stored directly
192  // with the CodeEntry in order to reduce memory footprint.
193  // Called before every destruction.
194  void ReleaseStrings(StringsStorage& strings);
195
196  void print() const;
197
198 private:
199  friend class CodeEntryStorage;
200
201  struct RareData {
202    const char* deopt_reason_ = kNoDeoptReason;
203    const char* bailout_reason_ = kEmptyBailoutReason;
204    int deopt_id_ = kNoDeoptimizationId;
205    std::unordered_map<int, std::vector<CodeEntryAndLineNumber>> inline_stacks_;
206    std::unordered_set<CodeEntry*, Hasher, Equals> inline_entries_;
207    std::vector<CpuProfileDeoptFrame> deopt_inlined_frames_;
208  };
209
210  RareData* EnsureRareData();
211
212  void mark_ref_counted() {
213    bit_field_ = RefCountedField::update(bit_field_, true);
214    ref_count_ = 1;
215  }
216
217  size_t AddRef() {
218    DCHECK(is_ref_counted());
219    DCHECK_LT(ref_count_, std::numeric_limits<size_t>::max());
220    ref_count_++;
221    return ref_count_;
222  }
223
224  size_t DecRef() {
225    DCHECK(is_ref_counted());
226    DCHECK_GT(ref_count_, 0UL);
227    ref_count_--;
228    return ref_count_;
229  }
230
231  using TagField = base::BitField<CodeEventListener::LogEventsAndTags, 0, 8>;
232  using BuiltinField = base::BitField<Builtin, 8, 20>;
233  static_assert(Builtins::kBuiltinCount <= BuiltinField::kNumValues,
234                "builtin_count exceeds size of bitfield");
235  using RefCountedField = base::BitField<bool, 28, 1>;
236  using CodeTypeField = base::BitField<CodeType, 29, 2>;
237  using SharedCrossOriginField = base::BitField<bool, 31, 1>;
238
239  std::uint32_t bit_field_;
240  std::atomic<std::size_t> ref_count_ = {0};
241  const char* name_;
242  const char* resource_name_;
243  int line_number_;
244  int column_number_;
245  int script_id_;
246  int position_;
247  std::unique_ptr<SourcePositionTable> line_info_;
248  std::unique_ptr<RareData> rare_data_;
249  Address instruction_start_ = kNullAddress;
250  Address* heap_object_location_ = nullptr;
251};
252
253struct CodeEntryAndLineNumber {
254  CodeEntry* code_entry;
255  int line_number;
256};
257
258using ProfileStackTrace = std::vector<CodeEntryAndLineNumber>;
259
260// Filters stack frames from sources other than a target native context.
261class ContextFilter {
262 public:
263  explicit ContextFilter(Address native_context_address = kNullAddress)
264      : native_context_address_(native_context_address) {}
265
266  // Invoked when a native context has changed address.
267  void OnMoveEvent(Address from_address, Address to_address);
268
269  bool Accept(Address native_context_address) const {
270    if (native_context_address_ == kNullAddress) return true;
271    return (native_context_address & ~kHeapObjectTag) ==
272           native_context_address_;
273  }
274
275  // Update the context's tracked address based on VM-thread events.
276  void set_native_context_address(Address address) {
277    native_context_address_ = address;
278  }
279  Address native_context_address() const { return native_context_address_; }
280
281 private:
282  Address native_context_address_;
283};
284
285class ProfileTree;
286
287class V8_EXPORT_PRIVATE ProfileNode {
288 public:
289  inline ProfileNode(ProfileTree* tree, CodeEntry* entry, ProfileNode* parent,
290                     int line_number = 0);
291  ~ProfileNode();
292  ProfileNode(const ProfileNode&) = delete;
293  ProfileNode& operator=(const ProfileNode&) = delete;
294
295  ProfileNode* FindChild(
296      CodeEntry* entry,
297      int line_number = v8::CpuProfileNode::kNoLineNumberInfo);
298  ProfileNode* FindOrAddChild(CodeEntry* entry, int line_number = 0);
299  void IncrementSelfTicks() { ++self_ticks_; }
300  void IncreaseSelfTicks(unsigned amount) { self_ticks_ += amount; }
301  void IncrementLineTicks(int src_line);
302
303  CodeEntry* entry() const { return entry_; }
304  unsigned self_ticks() const { return self_ticks_; }
305  const std::vector<ProfileNode*>* children() const { return &children_list_; }
306  unsigned id() const { return id_; }
307  ProfileNode* parent() const { return parent_; }
308  int line_number() const {
309    return line_number_ != 0 ? line_number_ : entry_->line_number();
310  }
311  CpuProfileNode::SourceType source_type() const;
312
313  unsigned int GetHitLineCount() const {
314    return static_cast<unsigned int>(line_ticks_.size());
315  }
316  bool GetLineTicks(v8::CpuProfileNode::LineTick* entries,
317                    unsigned int length) const;
318  void CollectDeoptInfo(CodeEntry* entry);
319  const std::vector<CpuProfileDeoptInfo>& deopt_infos() const {
320    return deopt_infos_;
321  }
322  Isolate* isolate() const;
323
324  void Print(int indent) const;
325
326 private:
327  struct Equals {
328    bool operator()(CodeEntryAndLineNumber lhs,
329                    CodeEntryAndLineNumber rhs) const {
330      return lhs.code_entry->IsSameFunctionAs(rhs.code_entry) &&
331             lhs.line_number == rhs.line_number;
332    }
333  };
334  struct Hasher {
335    std::size_t operator()(CodeEntryAndLineNumber pair) const {
336      return pair.code_entry->GetHash() ^ ComputeUnseededHash(pair.line_number);
337    }
338  };
339
340  ProfileTree* tree_;
341  CodeEntry* entry_;
342  unsigned self_ticks_;
343  std::unordered_map<CodeEntryAndLineNumber, ProfileNode*, Hasher, Equals>
344      children_;
345  int line_number_;
346  std::vector<ProfileNode*> children_list_;
347  ProfileNode* parent_;
348  unsigned id_;
349  // maps line number --> number of ticks
350  std::unordered_map<int, int> line_ticks_;
351
352  std::vector<CpuProfileDeoptInfo> deopt_infos_;
353};
354
355class CodeEntryStorage;
356
357class V8_EXPORT_PRIVATE ProfileTree {
358 public:
359  explicit ProfileTree(Isolate* isolate, CodeEntryStorage* storage = nullptr);
360  ~ProfileTree();
361  ProfileTree(const ProfileTree&) = delete;
362  ProfileTree& operator=(const ProfileTree&) = delete;
363
364  using ProfilingMode = v8::CpuProfilingMode;
365
366  ProfileNode* AddPathFromEnd(
367      const std::vector<CodeEntry*>& path,
368      int src_line = v8::CpuProfileNode::kNoLineNumberInfo,
369      bool update_stats = true);
370  ProfileNode* AddPathFromEnd(
371      const ProfileStackTrace& path,
372      int src_line = v8::CpuProfileNode::kNoLineNumberInfo,
373      bool update_stats = true,
374      ProfilingMode mode = ProfilingMode::kLeafNodeLineNumbers);
375  ProfileNode* root() const { return root_; }
376  unsigned next_node_id() { return next_node_id_++; }
377
378  void Print() const { root_->Print(0); }
379
380  Isolate* isolate() const { return isolate_; }
381
382  void EnqueueNode(const ProfileNode* node) { pending_nodes_.push_back(node); }
383  size_t pending_nodes_count() const { return pending_nodes_.size(); }
384  std::vector<const ProfileNode*> TakePendingNodes() {
385    return std::move(pending_nodes_);
386  }
387
388  CodeEntryStorage* code_entries() { return code_entries_; }
389
390 private:
391  template <typename Callback>
392  void TraverseDepthFirst(Callback* callback);
393
394  std::vector<const ProfileNode*> pending_nodes_;
395
396  unsigned next_node_id_;
397  Isolate* isolate_;
398  CodeEntryStorage* const code_entries_;
399  ProfileNode* root_;
400};
401
402class CpuProfiler;
403
404class CpuProfile {
405 public:
406  struct SampleInfo {
407    ProfileNode* node;
408    base::TimeTicks timestamp;
409    int line;
410    StateTag state_tag;
411    EmbedderStateTag embedder_state_tag;
412  };
413
414  V8_EXPORT_PRIVATE CpuProfile(
415      CpuProfiler* profiler, ProfilerId id, const char* title,
416      CpuProfilingOptions options,
417      std::unique_ptr<DiscardedSamplesDelegate> delegate = nullptr);
418  CpuProfile(const CpuProfile&) = delete;
419  CpuProfile& operator=(const CpuProfile&) = delete;
420
421  // Checks whether or not the given TickSample should be (sub)sampled, given
422  // the sampling interval of the profiler that recorded it (in microseconds).
423  V8_EXPORT_PRIVATE bool CheckSubsample(base::TimeDelta sampling_interval);
424  // Add pc -> ... -> main() call path to the profile.
425  void AddPath(base::TimeTicks timestamp, const ProfileStackTrace& path,
426               int src_line, bool update_stats,
427               base::TimeDelta sampling_interval, StateTag state,
428               EmbedderStateTag embedder_state);
429  void FinishProfile();
430
431  const char* title() const { return title_; }
432  const ProfileTree* top_down() const { return &top_down_; }
433
434  int samples_count() const { return static_cast<int>(samples_.size()); }
435  const SampleInfo& sample(int index) const { return samples_[index]; }
436
437  int64_t sampling_interval_us() const {
438    return options_.sampling_interval_us();
439  }
440
441  base::TimeTicks start_time() const { return start_time_; }
442  base::TimeTicks end_time() const { return end_time_; }
443  CpuProfiler* cpu_profiler() const { return profiler_; }
444  ContextFilter& context_filter() { return context_filter_; }
445  ProfilerId id() const { return id_; }
446
447  void UpdateTicksScale();
448
449  V8_EXPORT_PRIVATE void Print() const;
450
451 private:
452  void StreamPendingTraceEvents();
453
454  const char* title_;
455  const CpuProfilingOptions options_;
456  std::unique_ptr<DiscardedSamplesDelegate> delegate_;
457  ContextFilter context_filter_;
458  base::TimeTicks start_time_;
459  base::TimeTicks end_time_;
460  std::deque<SampleInfo> samples_;
461  ProfileTree top_down_;
462  CpuProfiler* const profiler_;
463  size_t streaming_next_sample_;
464  const ProfilerId id_;
465  // Number of microseconds worth of profiler ticks that should elapse before
466  // the next sample is recorded.
467  base::TimeDelta next_sample_delta_;
468};
469
470class CpuProfileMaxSamplesCallbackTask : public v8::Task {
471 public:
472  explicit CpuProfileMaxSamplesCallbackTask(
473      std::unique_ptr<DiscardedSamplesDelegate> delegate)
474      : delegate_(std::move(delegate)) {}
475
476  void Run() override { delegate_->Notify(); }
477
478 private:
479  std::unique_ptr<DiscardedSamplesDelegate> delegate_;
480};
481
482class V8_EXPORT_PRIVATE CodeMap {
483 public:
484  explicit CodeMap(CodeEntryStorage& storage);
485  ~CodeMap();
486  CodeMap(const CodeMap&) = delete;
487  CodeMap& operator=(const CodeMap&) = delete;
488
489  // Adds the given CodeEntry to the CodeMap. The CodeMap takes ownership of
490  // the CodeEntry.
491  void AddCode(Address addr, CodeEntry* entry, unsigned size);
492  void MoveCode(Address from, Address to);
493  // Attempts to remove the given CodeEntry from the CodeMap.
494  // Returns true iff the entry was found and removed.
495  bool RemoveCode(CodeEntry*);
496  void ClearCodesInRange(Address start, Address end);
497  CodeEntry* FindEntry(Address addr, Address* out_instruction_start = nullptr);
498  void Print();
499  size_t size() const { return code_map_.size(); }
500
501  size_t GetEstimatedMemoryUsage() const;
502
503  CodeEntryStorage& code_entries() { return code_entries_; }
504
505  void Clear();
506
507 private:
508  struct CodeEntryMapInfo {
509    CodeEntry* entry;
510    unsigned size;
511  };
512
513  std::multimap<Address, CodeEntryMapInfo> code_map_;
514  CodeEntryStorage& code_entries_;
515};
516
517// Manages the lifetime of CodeEntry objects, and stores shared resources
518// between them.
519class V8_EXPORT_PRIVATE CodeEntryStorage {
520 public:
521  template <typename... Args>
522  static CodeEntry* Create(Args&&... args) {
523    CodeEntry* const entry = new CodeEntry(std::forward<Args>(args)...);
524    entry->mark_ref_counted();
525    return entry;
526  }
527
528  void AddRef(CodeEntry*);
529  void DecRef(CodeEntry*);
530
531  StringsStorage& strings() { return function_and_resource_names_; }
532
533 private:
534  StringsStorage function_and_resource_names_;
535};
536
537class V8_EXPORT_PRIVATE CpuProfilesCollection {
538 public:
539  explicit CpuProfilesCollection(Isolate* isolate);
540  CpuProfilesCollection(const CpuProfilesCollection&) = delete;
541  CpuProfilesCollection& operator=(const CpuProfilesCollection&) = delete;
542
543  void set_cpu_profiler(CpuProfiler* profiler) { profiler_ = profiler; }
544  CpuProfilingResult StartProfiling(
545      const char* title = nullptr, CpuProfilingOptions options = {},
546      std::unique_ptr<DiscardedSamplesDelegate> delegate = nullptr);
547
548  // This Method is only visible for testing
549  CpuProfilingResult StartProfilingForTesting(ProfilerId id);
550  CpuProfile* StopProfiling(ProfilerId id);
551  bool IsLastProfileLeft(ProfilerId id);
552  CpuProfile* Lookup(const char* title);
553
554  std::vector<std::unique_ptr<CpuProfile>>* profiles() {
555    return &finished_profiles_;
556  }
557  const char* GetName(Name name) { return resource_names_.GetName(name); }
558  void RemoveProfile(CpuProfile* profile);
559
560  // Finds a common sampling interval dividing each CpuProfile's interval,
561  // rounded up to the nearest multiple of the CpuProfiler's sampling interval.
562  // Returns 0 if no profiles are attached.
563  base::TimeDelta GetCommonSamplingInterval() const;
564
565  // Called from profile generator thread.
566  void AddPathToCurrentProfiles(
567      base::TimeTicks timestamp, const ProfileStackTrace& path, int src_line,
568      bool update_stats, base::TimeDelta sampling_interval, StateTag state,
569      EmbedderStateTag embedder_state_tag,
570      Address native_context_address = kNullAddress,
571      Address native_embedder_context_address = kNullAddress);
572
573  // Called from profile generator thread.
574  void UpdateNativeContextAddressForCurrentProfiles(Address from, Address to);
575
576  // Limits the number of profiles that can be simultaneously collected.
577  static const int kMaxSimultaneousProfiles = 100;
578
579 private:
580  CpuProfilingResult StartProfiling(
581      ProfilerId id, const char* title = nullptr,
582      CpuProfilingOptions options = {},
583      std::unique_ptr<DiscardedSamplesDelegate> delegate = nullptr);
584  StringsStorage resource_names_;
585  std::vector<std::unique_ptr<CpuProfile>> finished_profiles_;
586  CpuProfiler* profiler_;
587
588  // Accessed by VM thread and profile generator thread.
589  std::vector<std::unique_ptr<CpuProfile>> current_profiles_;
590  base::Semaphore current_profiles_semaphore_;
591  static std::atomic<ProfilerId> last_id_;
592  Isolate* isolate_;
593};
594
595class CpuProfileJSONSerializer {
596 public:
597  explicit CpuProfileJSONSerializer(CpuProfile* profile)
598      : profile_(profile), writer_(nullptr) {}
599  CpuProfileJSONSerializer(const CpuProfileJSONSerializer&) = delete;
600  CpuProfileJSONSerializer& operator=(const CpuProfileJSONSerializer&) = delete;
601  void Serialize(v8::OutputStream* stream);
602
603 private:
604  void SerializePositionTicks(const v8::CpuProfileNode* node, int lineCount);
605  void SerializeCallFrame(const v8::CpuProfileNode* node);
606  void SerializeChildren(const v8::CpuProfileNode* node, int childrenCount);
607  void SerializeNode(const v8::CpuProfileNode* node);
608  void SerializeNodes();
609  void SerializeSamples();
610  void SerializeTimeDeltas();
611  void SerializeImpl();
612
613  static const int kEdgeFieldsCount;
614  static const int kNodeFieldsCount;
615
616  CpuProfile* profile_;
617  OutputStreamWriter* writer_;
618};
619
620}  // namespace internal
621}  // namespace v8
622
623#endif  // V8_PROFILER_PROFILE_GENERATOR_H_
624