profile-generator.cc 37.7 KB
Newer Older
1
// Copyright 2012 the V8 project authors. All rights reserved.
2 3
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
4

5
#include "src/profiler/profile-generator.h"
6

7 8
#include <algorithm>

9 10
#include "include/v8-profiler.h"
#include "src/base/lazy-instance.h"
11
#include "src/codegen/source-position.h"
12
#include "src/objects/shared-function-info-inl.h"
13
#include "src/profiler/cpu-profiler.h"
14
#include "src/profiler/profile-generator-inl.h"
15
#include "src/profiler/profiler-stats.h"
16 17
#include "src/tracing/trace-event.h"
#include "src/tracing/traced-value.h"
18 19 20 21

namespace v8 {
namespace internal {

22 23
void SourcePositionTable::SetPosition(int pc_offset, int line,
                                      int inlining_id) {
24 25
  DCHECK_GE(pc_offset, 0);
  DCHECK_GT(line, 0);  // The 1-based number of the source line.
26 27 28 29 30 31 32 33
  // It's possible that we map multiple source positions to a pc_offset in
  // optimized code. Usually these map to the same line, so there is no
  // difference here as we only store line number and not line/col in the form
  // of a script offset. Ignore any subsequent sets to the same offset.
  if (!pc_offsets_to_lines_.empty() &&
      pc_offsets_to_lines_.back().pc_offset == pc_offset) {
    return;
  }
34 35 36 37 38
  // Check that we are inserting in ascending order, so that the vector remains
  // sorted.
  DCHECK(pc_offsets_to_lines_.empty() ||
         pc_offsets_to_lines_.back().pc_offset < pc_offset);
  if (pc_offsets_to_lines_.empty() ||
39 40 41
      pc_offsets_to_lines_.back().line_number != line ||
      pc_offsets_to_lines_.back().inlining_id != inlining_id) {
    pc_offsets_to_lines_.push_back({pc_offset, line, inlining_id});
42 43 44
  }
}

45
int SourcePositionTable::GetSourceLineNumber(int pc_offset) const {
46
  if (pc_offsets_to_lines_.empty()) {
47 48
    return v8::CpuProfileNode::kNoLineNumberInfo;
  }
49 50 51
  auto it = std::lower_bound(
      pc_offsets_to_lines_.begin(), pc_offsets_to_lines_.end(),
      SourcePositionTuple{pc_offset, 0, SourcePosition::kNotInlined});
52 53
  if (it != pc_offsets_to_lines_.begin()) --it;
  return it->line_number;
54 55
}

56 57 58 59 60 61 62 63 64 65 66
int SourcePositionTable::GetInliningId(int pc_offset) const {
  if (pc_offsets_to_lines_.empty()) {
    return SourcePosition::kNotInlined;
  }
  auto it = std::lower_bound(
      pc_offsets_to_lines_.begin(), pc_offsets_to_lines_.end(),
      SourcePositionTuple{pc_offset, 0, SourcePosition::kNotInlined});
  if (it != pc_offsets_to_lines_.begin()) --it;
  return it->inlining_id;
}

67 68 69 70 71
size_t SourcePositionTable::Size() const {
  return sizeof(*this) + pc_offsets_to_lines_.capacity() *
                             sizeof(decltype(pc_offsets_to_lines_)::value_type);
}

72 73 74 75 76 77 78 79 80
void SourcePositionTable::print() const {
  base::OS::Print(" - source position table at %p\n", this);
  for (const SourcePositionTuple& pos_info : pc_offsets_to_lines_) {
    base::OS::Print("    %d --> line_number: %d inlining_id: %d\n",
                    pos_info.pc_offset, pos_info.line_number,
                    pos_info.inlining_id);
  }
}

81
const char* const CodeEntry::kEmptyResourceName = "";
82
const char* const CodeEntry::kEmptyBailoutReason = "";
83
const char* const CodeEntry::kNoDeoptReason = "";
84

lpy's avatar
lpy committed
85 86 87 88
const char* const CodeEntry::kProgramEntryName = "(program)";
const char* const CodeEntry::kIdleEntryName = "(idle)";
const char* const CodeEntry::kGarbageCollectorEntryName = "(garbage collector)";
const char* const CodeEntry::kUnresolvedFunctionName = "(unresolved function)";
89
const char* const CodeEntry::kRootEntryName = "(root)";
lpy's avatar
lpy committed
90

91 92 93
// static
CodeEntry* CodeEntry::program_entry() {
  static base::LeakyObject<CodeEntry> kProgramEntry(
94
      LogEventListener::CodeTag::kFunction, CodeEntry::kProgramEntryName,
95 96 97
      CodeEntry::kEmptyResourceName, v8::CpuProfileNode::kNoLineNumberInfo,
      v8::CpuProfileNode::kNoColumnNumberInfo, nullptr, false,
      CodeEntry::CodeType::OTHER);
98
  return kProgramEntry.get();
99 100
}

101 102 103
// static
CodeEntry* CodeEntry::idle_entry() {
  static base::LeakyObject<CodeEntry> kIdleEntry(
104
      LogEventListener::CodeTag::kFunction, CodeEntry::kIdleEntryName,
105 106 107 108
      CodeEntry::kEmptyResourceName, v8::CpuProfileNode::kNoLineNumberInfo,
      v8::CpuProfileNode::kNoColumnNumberInfo, nullptr, false,
      CodeEntry::CodeType::OTHER);
  return kIdleEntry.get();
109 110
}

111 112 113
// static
CodeEntry* CodeEntry::gc_entry() {
  static base::LeakyObject<CodeEntry> kGcEntry(
114 115 116
      LogEventListener::CodeTag::kBuiltin,
      CodeEntry::kGarbageCollectorEntryName, CodeEntry::kEmptyResourceName,
      v8::CpuProfileNode::kNoLineNumberInfo,
117 118
      v8::CpuProfileNode::kNoColumnNumberInfo, nullptr, false,
      CodeEntry::CodeType::OTHER);
119
  return kGcEntry.get();
120 121
}

122 123 124
// static
CodeEntry* CodeEntry::unresolved_entry() {
  static base::LeakyObject<CodeEntry> kUnresolvedEntry(
125
      LogEventListener::CodeTag::kFunction, CodeEntry::kUnresolvedFunctionName,
126 127 128
      CodeEntry::kEmptyResourceName, v8::CpuProfileNode::kNoLineNumberInfo,
      v8::CpuProfileNode::kNoColumnNumberInfo, nullptr, false,
      CodeEntry::CodeType::OTHER);
129
  return kUnresolvedEntry.get();
130 131
}

132 133 134
// static
CodeEntry* CodeEntry::root_entry() {
  static base::LeakyObject<CodeEntry> kRootEntry(
135
      LogEventListener::CodeTag::kFunction, CodeEntry::kRootEntryName,
136 137 138 139
      CodeEntry::kEmptyResourceName, v8::CpuProfileNode::kNoLineNumberInfo,
      v8::CpuProfileNode::kNoColumnNumberInfo, nullptr, false,
      CodeEntry::CodeType::OTHER);
  return kRootEntry.get();
140 141
}

142
uint32_t CodeEntry::GetHash() const {
143
  uint32_t hash = 0;
144
  if (script_id_ != v8::UnboundScript::kNoScriptId) {
145 146
    hash ^= ComputeUnseededHash(static_cast<uint32_t>(script_id_));
    hash ^= ComputeUnseededHash(static_cast<uint32_t>(position_));
147
  } else {
148
    hash ^= ComputeUnseededHash(
149
        static_cast<uint32_t>(reinterpret_cast<uintptr_t>(name_)));
150
    hash ^= ComputeUnseededHash(
151
        static_cast<uint32_t>(reinterpret_cast<uintptr_t>(resource_name_)));
152
    hash ^= ComputeUnseededHash(line_number_);
153
  }
154 155 156
  return hash;
}

157
bool CodeEntry::IsSameFunctionAs(const CodeEntry* entry) const {
158 159 160 161
  if (this == entry) return true;
  if (script_id_ != v8::UnboundScript::kNoScriptId) {
    return script_id_ == entry->script_id_ && position_ == entry->position_;
  }
162
  return name_ == entry->name_ && resource_name_ == entry->resource_name_ &&
163
         line_number_ == entry->line_number_;
164 165
}

166
void CodeEntry::SetBuiltinId(Builtin id) {
167 168
  bit_field_ =
      CodeTagField::update(bit_field_, LogEventListener::CodeTag::kBuiltin);
169
  bit_field_ = BuiltinField::update(bit_field_, id);
170 171
}

172
int CodeEntry::GetSourceLine(int pc_offset) const {
173
  if (line_info_) return line_info_->GetSourceLineNumber(pc_offset);
174 175 176
  return v8::CpuProfileNode::kNoLineNumberInfo;
}

177
void CodeEntry::SetInlineStacks(
178
    std::unordered_set<CodeEntry*, Hasher, Equals> inline_entries,
179 180 181 182
    std::unordered_map<int, std::vector<CodeEntryAndLineNumber>>
        inline_stacks) {
  EnsureRareData()->inline_entries_ = std::move(inline_entries);
  rare_data_->inline_stacks_ = std::move(inline_stacks);
183 184
}

185 186
const std::vector<CodeEntryAndLineNumber>* CodeEntry::GetInlineStack(
    int pc_offset) const {
187 188 189 190 191 192
  if (!line_info_) return nullptr;

  int inlining_id = line_info_->GetInliningId(pc_offset);
  if (inlining_id == SourcePosition::kNotInlined) return nullptr;
  DCHECK(rare_data_);

193 194
  auto it = rare_data_->inline_stacks_.find(inlining_id);
  return it != rare_data_->inline_stacks_.end() ? &it->second : nullptr;
195
}
196

197 198 199 200 201 202 203
void CodeEntry::set_deopt_info(
    const char* deopt_reason, int deopt_id,
    std::vector<CpuProfileDeoptFrame> inlined_frames) {
  RareData* rare_data = EnsureRareData();
  rare_data->deopt_reason_ = deopt_reason;
  rare_data->deopt_id_ = deopt_id;
  rare_data->deopt_inlined_frames_ = std::move(inlined_frames);
204 205
}

206
void CodeEntry::FillFunctionInfo(SharedFunctionInfo shared) {
207 208 209 210 211
  if (!shared.script().IsScript()) return;
  Script script = Script::cast(shared.script());
  set_script_id(script.id());
  set_position(shared.StartPosition());
  if (shared.optimization_disabled()) {
212
    set_bailout_reason(GetBailoutReason(shared.disabled_optimization_reason()));
213
  }
214 215
}

216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246
size_t CodeEntry::EstimatedSize() const {
  size_t estimated_size = 0;
  if (rare_data_) {
    estimated_size += sizeof(rare_data_.get());

    for (const auto& inline_entry : rare_data_->inline_entries_) {
      estimated_size += inline_entry->EstimatedSize();
    }
    estimated_size += rare_data_->inline_entries_.size() *
                      sizeof(decltype(rare_data_->inline_entries_)::value_type);

    for (const auto& inline_stack_pair : rare_data_->inline_stacks_) {
      estimated_size += inline_stack_pair.second.size() *
                        sizeof(decltype(inline_stack_pair.second)::value_type);
    }
    estimated_size +=
        rare_data_->inline_stacks_.size() *
        (sizeof(decltype(rare_data_->inline_stacks_)::key_type) +
         sizeof(decltype(rare_data_->inline_stacks_)::value_type));

    estimated_size +=
        rare_data_->deopt_inlined_frames_.capacity() *
        sizeof(decltype(rare_data_->deopt_inlined_frames_)::value_type);
  }

  if (line_info_) {
    estimated_size += line_info_.get()->Size();
  }
  return sizeof(*this) + estimated_size;
}

247
CpuProfileDeoptInfo CodeEntry::GetDeoptInfo() {
248 249
  DCHECK(has_deopt_info());

250
  CpuProfileDeoptInfo info;
251 252
  info.deopt_reason = rare_data_->deopt_reason_;
  DCHECK_NE(kNoDeoptimizationId, rare_data_->deopt_id_);
253
  if (rare_data_->deopt_inlined_frames_.empty()) {
254 255
    info.stack.push_back(CpuProfileDeoptFrame(
        {script_id_, static_cast<size_t>(std::max(0, position()))}));
256
  } else {
257
    info.stack = rare_data_->deopt_inlined_frames_;
258 259 260 261
  }
  return info;
}

262 263 264 265 266 267
CodeEntry::RareData* CodeEntry::EnsureRareData() {
  if (!rare_data_) {
    rare_data_.reset(new RareData());
  }
  return rare_data_.get();
}
268

269
void CodeEntry::ReleaseStrings(StringsStorage& strings) {
270 271
  DCHECK_EQ(ref_count_, 0UL);

272 273 274 275 276 277 278 279 280 281
  if (name_) {
    strings.Release(name_);
    name_ = nullptr;
  }
  if (resource_name_) {
    strings.Release(resource_name_);
    resource_name_ = nullptr;
  }
}

282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300
void CodeEntry::print() const {
  base::OS::Print("CodeEntry: at %p\n", this);

  base::OS::Print(" - name: %s\n", name_);
  base::OS::Print(" - resource_name: %s\n", resource_name_);
  base::OS::Print(" - line_number: %d\n", line_number_);
  base::OS::Print(" - column_number: %d\n", column_number_);
  base::OS::Print(" - script_id: %d\n", script_id_);
  base::OS::Print(" - position: %d\n", position_);

  if (line_info_) {
    line_info_->print();
  }

  if (rare_data_) {
    base::OS::Print(" - deopt_reason: %s\n", rare_data_->deopt_reason_);
    base::OS::Print(" - bailout_reason: %s\n", rare_data_->bailout_reason_);
    base::OS::Print(" - deopt_id: %d\n", rare_data_->deopt_id_);

301
    if (!rare_data_->inline_stacks_.empty()) {
302
      base::OS::Print(" - inline stacks:\n");
303 304
      for (auto it = rare_data_->inline_stacks_.begin();
           it != rare_data_->inline_stacks_.end(); it++) {
305 306 307
        base::OS::Print("    inlining_id: [%d]\n", it->first);
        for (const auto& e : it->second) {
          base::OS::Print("     %s --> %d\n", e.code_entry->name(),
308
                          e.line_number);
309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328
        }
      }
    } else {
      base::OS::Print(" - inline stacks: (empty)\n");
    }

    if (!rare_data_->deopt_inlined_frames_.empty()) {
      base::OS::Print(" - deopt inlined frames:\n");
      for (const CpuProfileDeoptFrame& frame :
           rare_data_->deopt_inlined_frames_) {
        base::OS::Print("script_id: %d position: %zu\n", frame.script_id,
                        frame.position);
      }
    } else {
      base::OS::Print(" - deopt inlined frames: (empty)\n");
    }
  }
  base::OS::Print("\n");
}

329 330 331 332
ProfileNode::~ProfileNode() {
  if (tree_->code_entries()) tree_->code_entries()->DecRef(entry_);
}

333 334 335 336 337 338 339 340 341 342 343
CpuProfileNode::SourceType ProfileNode::source_type() const {
  // Handle metadata and VM state code entry types.
  if (entry_ == CodeEntry::program_entry() ||
      entry_ == CodeEntry::idle_entry() || entry_ == CodeEntry::gc_entry() ||
      entry_ == CodeEntry::root_entry()) {
    return CpuProfileNode::kInternal;
  }
  if (entry_ == CodeEntry::unresolved_entry())
    return CpuProfileNode::kUnresolved;

  // Otherwise, resolve based on logger tag.
344 345 346 347
  switch (entry_->code_tag()) {
    case LogEventListener::CodeTag::kEval:
    case LogEventListener::CodeTag::kScript:
    case LogEventListener::CodeTag::kFunction:
348
      return CpuProfileNode::kScript;
349 350 351 352 353
    case LogEventListener::CodeTag::kBuiltin:
    case LogEventListener::CodeTag::kHandler:
    case LogEventListener::CodeTag::kBytecodeHandler:
    case LogEventListener::CodeTag::kNativeFunction:
    case LogEventListener::CodeTag::kNativeScript:
354
      return CpuProfileNode::kBuiltin;
355
    case LogEventListener::CodeTag::kCallback:
356
      return CpuProfileNode::kCallback;
357 358 359
    case LogEventListener::CodeTag::kRegExp:
    case LogEventListener::CodeTag::kStub:
    case LogEventListener::CodeTag::kLength:
360 361
      return CpuProfileNode::kInternal;
  }
362 363
  return CpuProfileNode::kInternal;
  UNREACHABLE();
364 365
}

366
void ProfileNode::CollectDeoptInfo(CodeEntry* entry) {
367
  deopt_infos_.push_back(entry->GetDeoptInfo());
368 369 370
  entry->clear_deopt_info();
}

371 372
ProfileNode* ProfileNode::FindChild(CodeEntry* entry, int line_number) {
  auto map_entry = children_.find({entry, line_number});
373
  return map_entry != children_.end() ? map_entry->second : nullptr;
374 375
}

376 377
ProfileNode* ProfileNode::FindOrAddChild(CodeEntry* entry, int line_number) {
  auto map_entry = children_.find({entry, line_number});
378
  if (map_entry == children_.end()) {
379 380
    ProfileNode* node = new ProfileNode(tree_, entry, this, line_number);
    children_[{entry, line_number}] = node;
381
    children_list_.push_back(node);
382 383 384
    return node;
  } else {
    return map_entry->second;
385 386 387 388
  }
}


389 390 391 392
void ProfileNode::IncrementLineTicks(int src_line) {
  if (src_line == v8::CpuProfileNode::kNoLineNumberInfo) return;
  // Increment a hit counter of a certain source line.
  // Add a new source line if not found.
393 394 395 396 397 398
  auto map_entry = line_ticks_.find(src_line);
  if (map_entry == line_ticks_.end()) {
    line_ticks_[src_line] = 1;
  } else {
    line_ticks_[src_line]++;
  }
399 400 401 402 403
}


bool ProfileNode::GetLineTicks(v8::CpuProfileNode::LineTick* entries,
                               unsigned int length) const {
404
  if (entries == nullptr || length == 0) return false;
405

406
  unsigned line_count = static_cast<unsigned>(line_ticks_.size());
407 408 409 410 411 412

  if (line_count == 0) return true;
  if (length < line_count) return false;

  v8::CpuProfileNode::LineTick* entry = entries;

413 414 415
  for (auto p = line_ticks_.begin(); p != line_ticks_.end(); p++, entry++) {
    entry->line = p->first;
    entry->hit_count = p->second;
416 417 418 419 420
  }

  return true;
}

421
void ProfileNode::Print(int indent) const {
422
  int line_number = line_number_ != 0 ? line_number_ : entry_->line_number();
423 424 425
  base::OS::Print("%5u %*s %s:%d %d %d #%d", self_ticks_, indent, "",
                  entry_->name(), line_number, source_type(),
                  entry_->script_id(), id());
426
  if (entry_->resource_name()[0] != '\0')
427 428
    base::OS::Print(" %s:%d", entry_->resource_name(), entry_->line_number());
  base::OS::Print("\n");
429
  for (const CpuProfileDeoptInfo& info : deopt_infos_) {
430 431 432 433
    base::OS::Print(
        "%*s;;; deopted at script_id: %d position: %zu with reason '%s'.\n",
        indent + 10, "", info.stack[0].script_id, info.stack[0].position,
        info.deopt_reason);
434
    for (size_t index = 1; index < info.stack.size(); ++index) {
435
      base::OS::Print("%*s;;;     Inline point: script_id %d position: %zu.\n",
436 437
                      indent + 10, "", info.stack[index].script_id,
                      info.stack[index].position);
438
    }
439 440 441 442 443 444 445
  }
  const char* bailout_reason = entry_->bailout_reason();
  if (bailout_reason != GetBailoutReason(BailoutReason::kNoReason) &&
      bailout_reason != CodeEntry::kEmptyBailoutReason) {
    base::OS::Print("%*s bailed out due to '%s'\n", indent + 10, "",
                    bailout_reason);
  }
446 447
  for (auto child : children_) {
    child.second->Print(indent + 2);
448 449 450 451 452
  }
}

class DeleteNodesCallback {
 public:
453 454
  void BeforeTraversingChild(ProfileNode*, ProfileNode*) { }

455
  void AfterAllChildrenTraversed(ProfileNode* node) { delete node; }
456 457 458 459

  void AfterChildTraversed(ProfileNode*, ProfileNode*) { }
};

460 461
ProfileTree::ProfileTree(Isolate* isolate, CodeEntryStorage* storage)
    : next_node_id_(1),
462 463
      isolate_(isolate),
      code_entries_(storage),
464
      root_(new ProfileNode(this, CodeEntry::root_entry(), nullptr)) {}
465

466 467
ProfileTree::~ProfileTree() {
  DeleteNodesCallback cb;
468
  TraverseDepthFirst(&cb);
469 470
}

471
ProfileNode* ProfileTree::AddPathFromEnd(const std::vector<CodeEntry*>& path,
472
                                         int src_line, bool update_stats) {
473
  ProfileNode* node = root_;
474
  CodeEntry* last_entry = nullptr;
475
  for (auto it = path.rbegin(); it != path.rend(); ++it) {
476
    if (*it == nullptr) continue;
477
    last_entry = *it;
478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493
    node = node->FindOrAddChild(*it, v8::CpuProfileNode::kNoLineNumberInfo);
  }
  if (last_entry && last_entry->has_deopt_info()) {
    node->CollectDeoptInfo(last_entry);
  }
  if (update_stats) {
    node->IncrementSelfTicks();
    if (src_line != v8::CpuProfileNode::kNoLineNumberInfo) {
      node->IncrementLineTicks(src_line);
    }
  }
  return node;
}

ProfileNode* ProfileTree::AddPathFromEnd(const ProfileStackTrace& path,
                                         int src_line, bool update_stats,
494
                                         ProfilingMode mode) {
495 496 497 498
  ProfileNode* node = root_;
  CodeEntry* last_entry = nullptr;
  int parent_line_number = v8::CpuProfileNode::kNoLineNumberInfo;
  for (auto it = path.rbegin(); it != path.rend(); ++it) {
499 500 501
    if (it->code_entry == nullptr) continue;
    last_entry = it->code_entry;
    node = node->FindOrAddChild(it->code_entry, parent_line_number);
502
    parent_line_number = mode == ProfilingMode::kCallerLineNumbers
503
                             ? it->line_number
504
                             : v8::CpuProfileNode::kNoLineNumberInfo;
505
  }
506 507 508
  if (last_entry && last_entry->has_deopt_info()) {
    node->CollectDeoptInfo(last_entry);
  }
509 510 511 512 513
  if (update_stats) {
    node->IncrementSelfTicks();
    if (src_line != v8::CpuProfileNode::kNoLineNumberInfo) {
      node->IncrementLineTicks(src_line);
    }
514
  }
515
  return node;
516 517
}

518 519 520 521
class Position {
 public:
  explicit Position(ProfileNode* node)
      : node(node), child_idx_(0) { }
522
  V8_INLINE ProfileNode* current_child() {
523
    return node->children()->at(child_idx_);
524
  }
525
  V8_INLINE bool has_current_child() {
526
    return child_idx_ < static_cast<int>(node->children()->size());
527
  }
528
  V8_INLINE void next_child() { ++child_idx_; }
529

530
  ProfileNode* node;
531 532
 private:
  int child_idx_;
533 534 535
};


536
// Non-recursive implementation of a depth-first post-order tree traversal.
537
template <typename Callback>
538
void ProfileTree::TraverseDepthFirst(Callback* callback) {
539 540 541 542
  std::vector<Position> stack;
  stack.emplace_back(root_);
  while (stack.size() > 0) {
    Position& current = stack.back();
543
    if (current.has_current_child()) {
544
      callback->BeforeTraversingChild(current.node, current.current_child());
545
      stack.emplace_back(current.current_child());
546 547
    } else {
      callback->AfterAllChildrenTraversed(current.node);
548 549
      if (stack.size() > 1) {
        Position& parent = stack[stack.size() - 2];
550
        callback->AfterChildTraversed(parent.node, current.node);
551
        parent.next_child();
552
      }
553
      // Remove child from the stack.
554
      stack.pop_back();
555
    }
556
  }
557 558
}

559 560 561 562 563 564
void ContextFilter::OnMoveEvent(Address from_address, Address to_address) {
  if (native_context_address() != from_address) return;

  set_native_context_address(to_address);
}

565 566
using v8::tracing::TracedValue;

567 568
std::atomic<ProfilerId> CpuProfilesCollection::last_id_{0};

569
CpuProfile::CpuProfile(CpuProfiler* profiler, ProfilerId id, const char* title,
570 571
                       CpuProfilingOptions options,
                       std::unique_ptr<DiscardedSamplesDelegate> delegate)
572
    : title_(title),
573
      options_(std::move(options)),
574
      delegate_(std::move(delegate)),
575
      start_time_(base::TimeTicks::Now()),
576
      top_down_(profiler->isolate(), profiler->code_entries()),
577
      profiler_(profiler),
578
      streaming_next_sample_(0),
579
      id_(id) {
580 581 582 583 584 585 586 587 588
  // The startTime timestamp is not converted to Perfetto's clock domain and
  // will get out of sync with other timestamps Perfetto knows about, including
  // the automatic trace event "ts" timestamp. startTime is included for
  // backward compatibility with the tracing protocol but the value of "ts"
  // should be used instead (it is recorded nearly immediately after).
  auto value = TracedValue::Create();
  value->SetDouble("startTime", start_time_.since_origin().InMicroseconds());
  TRACE_EVENT_SAMPLE_WITH_ID1(TRACE_DISABLED_BY_DEFAULT("v8.cpu_profiler"),
                              "Profile", id_, "data", std::move(value));
589 590

  DisallowHeapAllocation no_gc;
591 592 593
  if (delegate_) {
    delegate_->SetId(id_);
  }
594 595 596 597 598
  if (options_.has_filter_context()) {
    i::Address raw_filter_context =
        reinterpret_cast<i::Address>(options_.raw_filter_context());
    context_filter_.set_native_context_address(raw_filter_context);
  }
599
}
600

601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617
bool CpuProfile::CheckSubsample(base::TimeDelta source_sampling_interval) {
  DCHECK_GE(source_sampling_interval, base::TimeDelta());

  // If the sampling source's sampling interval is 0, record as many samples
  // are possible irrespective of the profile's sampling interval. Manually
  // taken samples (via CollectSample) fall into this case as well.
  if (source_sampling_interval.IsZero()) return true;

  next_sample_delta_ -= source_sampling_interval;
  if (next_sample_delta_ <= base::TimeDelta()) {
    next_sample_delta_ =
        base::TimeDelta::FromMicroseconds(options_.sampling_interval_us());
    return true;
  }
  return false;
}

618
void CpuProfile::AddPath(base::TimeTicks timestamp,
619
                         const ProfileStackTrace& path, int src_line,
620 621 622
                         bool update_stats, base::TimeDelta sampling_interval,
                         StateTag state_tag,
                         EmbedderStateTag embedder_state_tag) {
623 624
  if (!CheckSubsample(sampling_interval)) return;

625 626
  ProfileNode* top_frame_node =
      top_down_.AddPathFromEnd(path, src_line, update_stats, options_.mode());
627

628
  bool should_record_sample =
629
      !timestamp.IsNull() && timestamp >= start_time_ &&
630 631
      (options_.max_samples() == CpuProfilingOptions::kNoSampleLimit ||
       samples_.size() < options_.max_samples());
632

633
  if (should_record_sample) {
634 635
    samples_.push_back(
        {top_frame_node, timestamp, src_line, state_tag, embedder_state_tag});
636 637 638 639 640 641 642 643 644 645 646
  }

  if (!should_record_sample && delegate_ != nullptr) {
    const auto task_runner = V8::GetCurrentPlatform()->GetForegroundTaskRunner(
        reinterpret_cast<v8::Isolate*>(profiler_->isolate()));

    task_runner->PostTask(std::make_unique<CpuProfileMaxSamplesCallbackTask>(
        std::move(delegate_)));
    // std::move ensures that the delegate_ will be null on the next sample,
    // so we don't post a task multiple times.
  }
647

648 649
  const int kSamplesFlushCount = 100;
  const int kNodesFlushCount = 10;
650
  if (samples_.size() - streaming_next_sample_ >= kSamplesFlushCount ||
651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671
      top_down_.pending_nodes_count() >= kNodesFlushCount) {
    StreamPendingTraceEvents();
  }
}

namespace {

void BuildNodeValue(const ProfileNode* node, TracedValue* value) {
  const CodeEntry* entry = node->entry();
  value->BeginDictionary("callFrame");
  value->SetString("functionName", entry->name());
  if (*entry->resource_name()) {
    value->SetString("url", entry->resource_name());
  }
  value->SetInteger("scriptId", entry->script_id());
  if (entry->line_number()) {
    value->SetInteger("lineNumber", entry->line_number() - 1);
  }
  if (entry->column_number()) {
    value->SetInteger("columnNumber", entry->column_number() - 1);
  }
672
  value->SetString("codeType", entry->code_type_string());
673 674 675 676 677 678 679 680 681 682 683 684 685 686 687
  value->EndDictionary();
  value->SetInteger("id", node->id());
  if (node->parent()) {
    value->SetInteger("parent", node->parent()->id());
  }
  const char* deopt_reason = entry->bailout_reason();
  if (deopt_reason && deopt_reason[0] && strcmp(deopt_reason, "no reason")) {
    value->SetString("deoptReason", deopt_reason);
  }
}

}  // namespace

void CpuProfile::StreamPendingTraceEvents() {
  std::vector<const ProfileNode*> pending_nodes = top_down_.TakePendingNodes();
688
  if (pending_nodes.empty() && samples_.empty()) return;
689 690
  auto value = TracedValue::Create();

691
  if (!pending_nodes.empty() || streaming_next_sample_ != samples_.size()) {
692 693 694 695 696 697 698 699 700
    value->BeginDictionary("cpuProfile");
    if (!pending_nodes.empty()) {
      value->BeginArray("nodes");
      for (auto node : pending_nodes) {
        value->BeginDictionary();
        BuildNodeValue(node, value.get());
        value->EndDictionary();
      }
      value->EndArray();
701
    }
702
    if (streaming_next_sample_ != samples_.size()) {
703
      value->BeginArray("samples");
704
      for (size_t i = streaming_next_sample_; i < samples_.size(); ++i) {
705
        value->AppendInteger(samples_[i].node->id());
706 707 708 709
      }
      value->EndArray();
    }
    value->EndDictionary();
710
  }
711
  if (streaming_next_sample_ != samples_.size()) {
712 713 714 715 716 717 718 719 720 721
    // timeDeltas are computed within CLOCK_MONOTONIC. However, trace event
    // "ts" timestamps are converted to CLOCK_BOOTTIME by Perfetto. To get
    // absolute timestamps in CLOCK_BOOTTIME from timeDeltas, add them to
    // the "ts" timestamp from the initial "Profile" trace event sent by
    // CpuProfile::CpuProfile().
    //
    // Note that if the system is suspended and resumed while samples_ is
    // captured, timeDeltas derived after resume will not be convertible to
    // correct CLOCK_BOOTTIME time values (for instance, producing
    // CLOCK_BOOTTIME time values in the middle of the suspended period).
722 723
    value->BeginArray("timeDeltas");
    base::TimeTicks lastTimestamp =
724
        streaming_next_sample_ ? samples_[streaming_next_sample_ - 1].timestamp
725
                               : start_time();
726 727 728 729
    for (size_t i = streaming_next_sample_; i < samples_.size(); ++i) {
      value->AppendInteger(static_cast<int>(
          (samples_[i].timestamp - lastTimestamp).InMicroseconds()));
      lastTimestamp = samples_[i].timestamp;
730 731
    }
    value->EndArray();
732 733 734 735 736 737 738 739 740 741
    bool has_non_zero_lines =
        std::any_of(samples_.begin() + streaming_next_sample_, samples_.end(),
                    [](const SampleInfo& sample) { return sample.line != 0; });
    if (has_non_zero_lines) {
      value->BeginArray("lines");
      for (size_t i = streaming_next_sample_; i < samples_.size(); ++i) {
        value->AppendInteger(samples_[i].line);
      }
      value->EndArray();
    }
742
    streaming_next_sample_ = samples_.size();
743 744 745
  }

  TRACE_EVENT_SAMPLE_WITH_ID1(TRACE_DISABLED_BY_DEFAULT("v8.cpu_profiler"),
746
                              "ProfileChunk", id_, "data", std::move(value));
747 748
}

749
void CpuProfile::FinishProfile() {
750
  end_time_ = base::TimeTicks::Now();
751 752
  // Stop tracking context movements after profiling stops.
  context_filter_.set_native_context_address(kNullAddress);
753 754 755 756 757 758 759 760 761 762 763
  StreamPendingTraceEvents();
  auto value = TracedValue::Create();
  // The endTime timestamp is not converted to Perfetto's clock domain and will
  // get out of sync with other timestamps Perfetto knows about, including the
  // automatic trace event "ts" timestamp. endTime is included for backward
  // compatibility with the tracing protocol: its presence in "data" is used by
  // devtools to identify the last ProfileChunk but the value of "ts" should be
  // used instead (it is recorded nearly immediately after).
  value->SetDouble("endTime", end_time_.since_origin().InMicroseconds());
  TRACE_EVENT_SAMPLE_WITH_ID1(TRACE_DISABLED_BY_DEFAULT("v8.cpu_profiler"),
                              "ProfileChunk", id_, "data", std::move(value));
764 765
}

766
void CpuProfile::Print() const {
767
  base::OS::Print("[Top down]:\n");
768
  top_down_.Print();
769 770
  ProfilerStats::Instance()->Print();
  ProfilerStats::Instance()->Clear();
771 772
}

773 774 775 776 777 778
void CodeEntryStorage::AddRef(CodeEntry* entry) {
  if (entry->is_ref_counted()) entry->AddRef();
}

void CodeEntryStorage::DecRef(CodeEntry* entry) {
  if (entry->is_ref_counted() && entry->DecRef() == 0) {
779 780 781 782 783
    if (entry->rare_data_) {
      for (auto* inline_entry : entry->rare_data_->inline_entries_) {
        DecRef(inline_entry);
      }
    }
784 785 786 787 788 789
    entry->ReleaseStrings(function_and_resource_names_);
    delete entry;
  }
}

CodeMap::CodeMap(CodeEntryStorage& storage) : code_entries_(storage) {}
790

791 792 793
CodeMap::~CodeMap() { Clear(); }

void CodeMap::Clear() {
794 795
  for (auto& slot : code_map_) {
    if (CodeEntry* entry = slot.second.entry) {
796
      code_entries_.DecRef(entry);
797 798 799
    } else {
      // We expect all entries in the code mapping to contain a CodeEntry.
      UNREACHABLE();
800 801
    }
  }
802 803

  code_map_.clear();
804
}
805

806
void CodeMap::AddCode(Address addr, CodeEntry* entry, unsigned size) {
807
  code_map_.emplace(addr, CodeEntryMapInfo{entry, size});
808 809 810 811 812 813 814
  entry->set_instruction_start(addr);
}

bool CodeMap::RemoveCode(CodeEntry* entry) {
  auto range = code_map_.equal_range(entry->instruction_start());
  for (auto i = range.first; i != range.second; ++i) {
    if (i->second.entry == entry) {
815
      code_entries_.DecRef(entry);
816 817 818 819 820
      code_map_.erase(i);
      return true;
    }
  }
  return false;
821 822
}

823
void CodeMap::ClearCodesInRange(Address start, Address end) {
824 825 826 827
  auto left = code_map_.upper_bound(start);
  if (left != code_map_.begin()) {
    --left;
    if (left->first + left->second.size <= start) ++left;
828
  }
829
  auto right = left;
830
  for (; right != code_map_.end() && right->first < end; ++right) {
831
    code_entries_.DecRef(right->second.entry);
832
  }
833
  code_map_.erase(left, right);
834 835
}

836
CodeEntry* CodeMap::FindEntry(Address addr, Address* out_instruction_start) {
837 838 839
  // Note that an address may correspond to multiple CodeEntry objects. An
  // arbitrary selection is made (as per multimap spec) in the event of a
  // collision.
840 841 842
  auto it = code_map_.upper_bound(addr);
  if (it == code_map_.begin()) return nullptr;
  --it;
843 844
  Address start_address = it->first;
  Address end_address = start_address + it->second.size;
845
  CodeEntry* ret = addr < end_address ? it->second.entry : nullptr;
846 847
  DCHECK(!ret || (addr >= start_address && addr < end_address));
  if (ret && out_instruction_start) *out_instruction_start = start_address;
848
  return ret;
849 850
}

851 852
void CodeMap::MoveCode(Address from, Address to) {
  if (from == to) return;
853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871

  auto range = code_map_.equal_range(from);
  // Instead of iterating until |range.second|, iterate the number of elements.
  // This is because the |range.second| may no longer be the element past the
  // end of the equal elements range after insertions.
  size_t distance = std::distance(range.first, range.second);
  auto it = range.first;
  while (distance--) {
    CodeEntryMapInfo& info = it->second;
    DCHECK(info.entry);
    DCHECK_EQ(info.entry->instruction_start(), from);
    info.entry->set_instruction_start(to);

    DCHECK(from + info.size <= to || to + info.size <= from);
    code_map_.emplace(to, info);
    it++;
  }

  code_map_.erase(range.first, it);
872 873
}

874
void CodeMap::Print() {
875
  for (const auto& pair : code_map_) {
876
    base::OS::Print("%p %5d %s\n", reinterpret_cast<void*>(pair.first),
877
                    pair.second.size, pair.second.entry->name());
878
  }
879 880
}

881 882 883 884 885 886 887 888 889
size_t CodeMap::GetEstimatedMemoryUsage() const {
  size_t map_size = 0;
  for (const auto& pair : code_map_) {
    map_size += sizeof(pair.first) + sizeof(pair.second) +
                pair.second.entry->EstimatedSize();
  }
  return sizeof(*this) + map_size;
}

890
CpuProfilesCollection::CpuProfilesCollection(Isolate* isolate)
891
    : profiler_(nullptr), current_profiles_semaphore_(1), isolate_(isolate) {
892 893
  USE(isolate_);
}
894

895 896 897 898 899
CpuProfilingResult CpuProfilesCollection::StartProfilingForTesting(
    ProfilerId id) {
  return StartProfiling(id);
}

900
CpuProfilingResult CpuProfilesCollection::StartProfiling(
901 902
    const char* title, CpuProfilingOptions options,
    std::unique_ptr<DiscardedSamplesDelegate> delegate) {
903 904
  return StartProfiling(++last_id_, title, std::move(options),
                        std::move(delegate));
905 906 907 908 909
}

CpuProfilingResult CpuProfilesCollection::StartProfiling(
    ProfilerId id, const char* title, CpuProfilingOptions options,
    std::unique_ptr<DiscardedSamplesDelegate> delegate) {
910
  current_profiles_semaphore_.Wait();
911

912
  if (static_cast<int>(current_profiles_.size()) >= kMaxSimultaneousProfiles) {
913
    current_profiles_semaphore_.Signal();
914 915 916 917 918 919
    return {
        0,
        CpuProfilingStatus::kErrorTooManyProfilers,
    };
  }

920 921 922 923 924 925 926 927 928 929 930
  for (const std::unique_ptr<CpuProfile>& profile : current_profiles_) {
    if ((profile->title() != nullptr && title != nullptr &&
         strcmp(profile->title(), title) == 0) ||
        profile->id() == id) {
      // Ignore attempts to start profile with the same title or id
      current_profiles_semaphore_.Signal();
      // ... though return kAlreadyStarted to force it collect a sample.
      return {
          profile->id(),
          CpuProfilingStatus::kAlreadyStarted,
      };
931 932
    }
  }
933

934 935
  CpuProfile* profile = new CpuProfile(profiler_, id, title, std::move(options),
                                       std::move(delegate));
936
  current_profiles_.emplace_back(profile);
937
  current_profiles_semaphore_.Signal();
938 939 940 941 942

  return {
      profile->id(),
      CpuProfilingStatus::kStarted,
  };
943 944
}

945
CpuProfile* CpuProfilesCollection::StopProfiling(ProfilerId id) {
946
  current_profiles_semaphore_.Wait();
947
  CpuProfile* profile = nullptr;
948

949 950 951
  auto it = std::find_if(
      current_profiles_.rbegin(), current_profiles_.rend(),
      [=](const std::unique_ptr<CpuProfile>& p) { return id == p->id(); });
952 953 954 955 956 957 958

  if (it != current_profiles_.rend()) {
    (*it)->FinishProfile();
    profile = it->get();
    finished_profiles_.push_back(std::move(*it));
    // Convert reverse iterator to matching forward iterator.
    current_profiles_.erase(--(it.base()));
959
  }
960
  current_profiles_semaphore_.Signal();
961
  return profile;
962 963
}

964
CpuProfile* CpuProfilesCollection::Lookup(const char* title) {
965 966
  // Called from VM thread, and only it can mutate the list,
  // so no locking is needed here.
967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984
  DCHECK_EQ(ThreadId::Current(), isolate_->thread_id());
  if (title == nullptr) {
    return nullptr;
  }
  // http://crbug/51594, edge case console.profile may provide an empty title
  // and must not crash
  const bool empty_title = title[0] == '\0';
  auto it = std::find_if(
      current_profiles_.rbegin(), current_profiles_.rend(),
      [&](const std::unique_ptr<CpuProfile>& p) {
        return (empty_title ||
                (p->title() != nullptr && strcmp(p->title(), title) == 0));
      });
  if (it != current_profiles_.rend()) {
    return it->get();
  }

  return nullptr;
985 986
}

987 988 989 990 991 992 993
bool CpuProfilesCollection::IsLastProfileLeft(ProfilerId id) {
  // Called from VM thread, and only it can mutate the list,
  // so no locking is needed here.
  DCHECK_EQ(ThreadId::Current(), isolate_->thread_id());
  if (current_profiles_.size() != 1) return false;
  return id == current_profiles_[0]->id();
}
994

995 996
void CpuProfilesCollection::RemoveProfile(CpuProfile* profile) {
  // Called from VM thread for a completed profile.
997
  DCHECK_EQ(ThreadId::Current(), isolate_->thread_id());
998
  auto pos =
999 1000 1001 1002
      std::find_if(finished_profiles_.begin(), finished_profiles_.end(),
                   [&](const std::unique_ptr<CpuProfile>& finished_profile) {
                     return finished_profile.get() == profile;
                   });
1003 1004
  DCHECK(pos != finished_profiles_.end());
  finished_profiles_.erase(pos);
1005 1006
}

1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036
namespace {

int64_t GreatestCommonDivisor(int64_t a, int64_t b) {
  return b ? GreatestCommonDivisor(b, a % b) : a;
}

}  // namespace

base::TimeDelta CpuProfilesCollection::GetCommonSamplingInterval() const {
  DCHECK(profiler_);

  int64_t base_sampling_interval_us =
      profiler_->sampling_interval().InMicroseconds();
  if (base_sampling_interval_us == 0) return base::TimeDelta();

  int64_t interval_us = 0;
  for (const auto& profile : current_profiles_) {
    // Snap the profile's requested sampling interval to the next multiple of
    // the base sampling interval.
    int64_t profile_interval_us =
        std::max<int64_t>(
            (profile->sampling_interval_us() + base_sampling_interval_us - 1) /
                base_sampling_interval_us,
            1) *
        base_sampling_interval_us;
    interval_us = GreatestCommonDivisor(interval_us, profile_interval_us);
  }
  return base::TimeDelta::FromMicroseconds(interval_us);
}

1037
void CpuProfilesCollection::AddPathToCurrentProfiles(
1038
    base::TimeTicks timestamp, const ProfileStackTrace& path, int src_line,
1039 1040 1041
    bool update_stats, base::TimeDelta sampling_interval, StateTag state,
    EmbedderStateTag embedder_state_tag, Address native_context_address,
    Address embedder_native_context_address) {
1042 1043 1044
  // As starting / stopping profiles is rare relatively to this
  // method, we don't bother minimizing the duration of lock holding,
  // e.g. copying contents of the list to a local vector.
1045
  current_profiles_semaphore_.Wait();
1046
  const ProfileStackTrace empty_path;
1047
  for (const std::unique_ptr<CpuProfile>& profile : current_profiles_) {
1048
    ContextFilter& context_filter = profile->context_filter();
1049
    // If the context filter check failed, omit the contents of the stack.
1050 1051 1052
    bool accepts_context = context_filter.Accept(native_context_address);
    bool accepts_embedder_context =
        context_filter.Accept(embedder_native_context_address);
1053 1054 1055 1056 1057 1058 1059

    // if FilterContext is set, do not propagate StateTag if not accepted.
    // GC is exception because native context address is guaranteed to be empty.
    DCHECK(state != StateTag::GC || native_context_address == kNullAddress);
    if (!accepts_context && state != StateTag::GC) {
      state = StateTag::IDLE;
    }
1060
    profile->AddPath(timestamp, accepts_context ? path : empty_path, src_line,
1061 1062 1063
                     update_stats, sampling_interval, state,
                     accepts_embedder_context ? embedder_state_tag
                                              : EmbedderStateTag::EMPTY);
1064 1065 1066 1067 1068 1069 1070 1071 1072
  }
  current_profiles_semaphore_.Signal();
}

void CpuProfilesCollection::UpdateNativeContextAddressForCurrentProfiles(
    Address from, Address to) {
  current_profiles_semaphore_.Wait();
  for (const std::unique_ptr<CpuProfile>& profile : current_profiles_) {
    profile->context_filter().OnMoveEvent(from, to);
1073
  }
1074
  current_profiles_semaphore_.Signal();
1075 1076
}

1077 1078
}  // namespace internal
}  // namespace v8