// Copyright 2015 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "base/trace_event/heap_profiler_stack_frame_deduplicator.h"

#include <inttypes.h>
#include <stddef.h>

#include <algorithm>
#include <string>
#include <utility>

#include "base/hash.h"
#include "base/strings/stringprintf.h"
#include "base/trace_event/memory_usage_estimator.h"
#include "base/trace_event/trace_event.h"
#include "base/trace_event/trace_event_argument.h"
#include "base/trace_event/trace_event_memory_overhead.h"

namespace base {
namespace trace_event {

namespace {

// Dumb hash function that nevertheless works surprisingly well and
// produces ~0 collisions on real backtraces.
size_t HashBacktrace(const StackFrame* begin, const StackFrame* end) {
  size_t hash = 0;
  for (; begin != end; begin++) {
    hash += reinterpret_cast<uintptr_t>(begin->value);
  }
  return hash;
}

}  // namespace

StackFrameDeduplicator::FrameNode::FrameNode(StackFrame frame,
                                             int parent_frame_index)
    : frame(frame), parent_frame_index(parent_frame_index) {}
StackFrameDeduplicator::FrameNode::FrameNode(const FrameNode& other) = default;
StackFrameDeduplicator::FrameNode::~FrameNode() = default;

size_t StackFrameDeduplicator::FrameNode::EstimateMemoryUsage() const {
  return base::trace_event::EstimateMemoryUsage(children);
}

StackFrameDeduplicator::StackFrameDeduplicator() = default;
StackFrameDeduplicator::~StackFrameDeduplicator() = default;

bool StackFrameDeduplicator::Match(int frame_index,
                                   const StackFrame* begin_frame,
                                   const StackFrame* end_frame) const {
  // |frame_index| identifies the bottom frame, i.e. we need to walk
  // backtrace backwards.
  const StackFrame* current_frame = end_frame - 1;
  for (; current_frame >= begin_frame; --current_frame) {
    const FrameNode& node = frames_[frame_index];
    if (node.frame != *current_frame) {
      break;
    }

    frame_index = node.parent_frame_index;
    if (frame_index == FrameNode::kInvalidFrameIndex) {
      if (current_frame == begin_frame) {
        // We're at the top node and we matched all backtrace frames,
        // i.e. we successfully matched the backtrace.
        return true;
      }
      break;
    }
  }

  return false;
}

int StackFrameDeduplicator::Insert(const StackFrame* begin_frame,
                                   const StackFrame* end_frame) {
  if (begin_frame == end_frame) {
    return FrameNode::kInvalidFrameIndex;
  }

  size_t backtrace_hash = HashBacktrace(begin_frame, end_frame);

  // Check if we know about this backtrace.
  auto backtrace_it = backtrace_lookup_table_.find(backtrace_hash);
  if (backtrace_it != backtrace_lookup_table_.end()) {
    int backtrace_index = backtrace_it->second;
    if (Match(backtrace_index, begin_frame, end_frame)) {
      return backtrace_index;
    }
  }

  int frame_index = FrameNode::kInvalidFrameIndex;
  base::flat_map<StackFrame, int>* nodes = &roots_;

  // Loop through the frames, early out when a frame is null.
  for (const StackFrame* it = begin_frame; it != end_frame; it++) {
    StackFrame frame = *it;

    auto node = nodes->find(frame);
    if (node == nodes->end()) {
      // There is no tree node for this frame yet, create it. The parent node
      // is the node associated with the previous frame.
      FrameNode frame_node(frame, frame_index);

      // The new frame node will be appended, so its index is the current size
      // of the vector.
      frame_index = static_cast<int>(frames_.size());

      // Add the node to the trie so it will be found next time.
      nodes->insert(std::make_pair(frame, frame_index));

      // Append the node after modifying |nodes|, because the |frames_| vector
      // might need to resize, and this invalidates the |nodes| pointer.
      frames_.push_back(frame_node);
    } else {
      // A tree node for this frame exists. Look for the next one.
      frame_index = node->second;
    }

    nodes = &frames_[frame_index].children;
  }

  // Remember the backtrace.
  backtrace_lookup_table_[backtrace_hash] = frame_index;

  return frame_index;
}

void StackFrameDeduplicator::AppendAsTraceFormat(std::string* out) const {
  TRACE_EVENT0(TRACE_DISABLED_BY_DEFAULT("memory-infra"),
               "StackFrameDeduplicator::AppendAsTraceFormat");
  out->append("{");  // Begin the |stackFrames| dictionary.

  int i = 0;
  auto frame_node = begin();
  auto it_end = end();
  std::string stringify_buffer;

  while (frame_node != it_end) {
    // The |stackFrames| format is a dictionary, not an array, so the
    // keys are stringified indices. Write the index manually, then use
    // |TracedValue| to format the object. This is to avoid building the
    // entire dictionary as a |TracedValue| in memory.
    SStringPrintf(&stringify_buffer, "\"%d\":", i);
    out->append(stringify_buffer);

    std::unique_ptr<TracedValue> frame_node_value(new TracedValue);
    const StackFrame& frame = frame_node->frame;
    switch (frame.type) {
      case StackFrame::Type::TRACE_EVENT_NAME:
        frame_node_value->SetString("name",
                                    static_cast<const char*>(frame.value));
        break;
      case StackFrame::Type::THREAD_NAME:
        SStringPrintf(&stringify_buffer,
                      "[Thread: %s]",
                      static_cast<const char*>(frame.value));
        frame_node_value->SetString("name", stringify_buffer);
        break;
      case StackFrame::Type::PROGRAM_COUNTER:
        SStringPrintf(&stringify_buffer,
                      "pc:%" PRIxPTR,
                      reinterpret_cast<uintptr_t>(frame.value));
        frame_node_value->SetString("name", stringify_buffer);
        break;
    }
    if (frame_node->parent_frame_index != FrameNode::kInvalidFrameIndex) {
      SStringPrintf(&stringify_buffer, "%d", frame_node->parent_frame_index);
      frame_node_value->SetString("parent", stringify_buffer);
    }
    frame_node_value->AppendAsTraceFormat(out);

    i++;
    frame_node++;

    if (frame_node != it_end)
      out->append(",");
  }

  out->append("}");  // End the |stackFrames| dictionary.
}

void StackFrameDeduplicator::EstimateTraceMemoryOverhead(
    TraceEventMemoryOverhead* overhead) {
  size_t memory_usage = EstimateMemoryUsage(frames_) +
                        EstimateMemoryUsage(roots_) +
                        EstimateMemoryUsage(backtrace_lookup_table_);
  overhead->Add(TraceEventMemoryOverhead::kHeapProfilerStackFrameDeduplicator,
                sizeof(StackFrameDeduplicator) + memory_usage);
}

}  // namespace trace_event
}  // namespace base