path: root/base/trace_event/memory_profiler_allocation_context.h

// 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.

#ifndef BASE_TRACE_EVENT_MEMORY_PROFILER_ALLOCATION_CONTEXT_H_
#define BASE_TRACE_EVENT_MEMORY_PROFILER_ALLOCATION_CONTEXT_H_

#include <map>
#include <string>
#include <vector>

#include "base/atomicops.h"
#include "base/base_export.h"
#include "base/trace_event/trace_event_impl.h"

namespace base {
namespace trace_event {

// When heap profiling is enabled, tracing keeps track of the allocation
// context for each allocation intercepted. It is generated by the
// |AllocationContextTracker| which keeps stacks of context in TLS.
// The tracker is initialized lazily.

using StackFrame = const char*;

// A simple stack of |StackFrame| that unlike |std::stack| allows iterating
// the stack and guards for underflow.
class BASE_EXPORT AllocationStack {
 public:
  // Incrementing the iterator iterates up the stack, from bottom (least recent
  // call) to top (most recent call).
  using ConstIterator = std::vector<StackFrame>::const_iterator;

  AllocationStack();
  ~AllocationStack();

  inline ConstIterator bottom() const { return stack_.begin(); }
  inline ConstIterator top() const { return stack_.end(); }

  inline void push(StackFrame frame) {
    // Impose a limit on the height to verify that every push is popped, because
    // in practice the pseudo stack never grows higher than ~20 frames.
    DCHECK_LT(stack_.size(), 128u);
    stack_.push_back(frame);
  }

  inline void pop(StackFrame frame) {
    if (stack_.empty())
      return;

    // Assert that pushes and pops are nested correctly.
    // This DCHECK can be hit if some TRACE_EVENT macro is unbalanced
    // (a TRACE_EVENT_END* call without a corresponding TRACE_EVENT_BEGIN).
    DCHECK_EQ(frame, stack_.back())
        << "Encountered an unmatched TRACE_EVENT_END";

    stack_.pop_back();
  }

 private:
  std::vector<StackFrame> stack_;

  DISALLOW_COPY_AND_ASSIGN(AllocationStack);
};

// The backtrace in the allocation context is a snapshot of the stack. For now,
// this is the pseudo stack where frames are created by trace event macros. In
// the future, we might add the option to use the native call stack. In that
// case, |Backtrace| and |AllocationContextTracker::GetContextSnapshot| might
// have different implementations that can be selected by a compile time flag.

// The number of stack frames stored in the backtrace is a trade off between
// memory used for tracing and accuracy. Measurements done on a prototype
// revealed that:
//
// - In 60 percent of the cases, stack depth <= 7.
// - In 87 percent of the cases, stack depth <= 9.
// - In 95 percent of the cases, stack depth <= 11.
//
// See the design doc (https://goo.gl/4s7v7b) for more details.

struct BASE_EXPORT Backtrace {
  // Unused backtrace frames are filled with nullptr frames. If the stack is
  // higher than what can be stored here, the bottom frames are stored. Based
  // on the data above, a depth of 12 captures the full stack in the vast
  // majority of the cases.
  StackFrame frames[12];
};

bool BASE_EXPORT operator==(const Backtrace& lhs, const Backtrace& rhs);

// A data structure that allows grouping a set of backtraces in a space-
// efficient manner by creating a call tree and writing it as a set of (node,
// parent) pairs. The tree nodes reference both parent and children. The parent
// is referenced by index into |frames_|. The children are referenced via a map
// of |StackFrame|s to index into |frames_|. So there is a trie for bottum-up
// lookup of a backtrace for deduplication, and a tree for compact storage in
// the trace log.
class BASE_EXPORT StackFrameDeduplicator : public ConvertableToTraceFormat {
 public:
  // A node in the call tree.
  struct FrameNode {
    FrameNode(StackFrame frame, int parent_frame_index);
    ~FrameNode();

    StackFrame frame;

    // The index of the parent stack frame in |frames_|, or -1 if there is no
    // parent frame (when it is at the bottom of the call stack).
    int parent_frame_index;

    // Indices into |frames_| of frames called from the current frame.
    std::map<StackFrame, int> children;
  };

  using ConstIterator = std::vector<FrameNode>::const_iterator;

  StackFrameDeduplicator();

  // Inserts a backtrace and returns the index of its leaf node in |frames_|.
  // Returns -1 if the backtrace is empty.
  int Insert(const Backtrace& bt);

  // Iterators over the frame nodes in the call tree.
  ConstIterator begin() const { return frames_.begin(); }
  ConstIterator end() const { return frames_.end(); }

  // Writes the |stackFrames| dictionary as defined in https://goo.gl/GerkV8 to
  // the trace log.
  void AppendAsTraceFormat(std::string* out) const override;

 private:
  ~StackFrameDeduplicator() override;

  std::map<StackFrame, int> roots_;
  std::vector<FrameNode> frames_;

  DISALLOW_COPY_AND_ASSIGN(StackFrameDeduplicator);
};

// The |AllocationContext| is context metadata that is kept for every allocation
// when heap profiling is enabled. To simplify memory management for
// bookkeeping, this struct has a fixed size. All |const char*|s here
// must have static lifetime.
struct BASE_EXPORT AllocationContext {
  Backtrace backtrace;
};

// The allocation context tracker keeps track of thread-local context for heap
// profiling. It includes a pseudo stack of trace events. On every allocation
// the tracker provides a snapshot of its context in the form of an
// |AllocationContext| that is to be stored together with the allocation
// details.
class BASE_EXPORT AllocationContextTracker {
 public:
  // Globally enables capturing allocation context.
  // TODO(ruuda): Should this be replaced by |EnableCapturing| in the future?
  // Or at least have something that guards agains enable -> disable -> enable?
  static void SetCaptureEnabled(bool enabled);

  // Returns whether capturing allocation context is enabled globally.
  inline static bool capture_enabled() {
    // A little lag after heap profiling is enabled or disabled is fine, it is
    // more important that the check is as cheap as possible when capturing is
    // not enabled, so do not issue a memory barrier in the fast path.
    if (subtle::NoBarrier_Load(&capture_enabled_) == 0)
        return false;

    // In the slow path, an acquire load is required to pair with the release
    // store in |SetCaptureEnabled|. This is to ensure that the TLS slot for
    // the thread-local allocation context tracker has been initialized if
    // |capture_enabled| returns true.
    return subtle::Acquire_Load(&capture_enabled_) != 0;
  }

  // Pushes a frame onto the thread-local pseudo stack.
  static void PushPseudoStackFrame(StackFrame frame);

  // Pops a frame from the thread-local pseudo stack.
  static void PopPseudoStackFrame(StackFrame frame);

  // Returns a snapshot of the current thread-local context.
  static AllocationContext GetContextSnapshot();

  ~AllocationContextTracker();

 private:
  AllocationContextTracker();

  static AllocationContextTracker* GetThreadLocalTracker();

  static subtle::Atomic32 capture_enabled_;

  // The pseudo stack where frames are |TRACE_EVENT| names.
  AllocationStack pseudo_stack_;

  DISALLOW_COPY_AND_ASSIGN(AllocationContextTracker);
};

}  // namespace trace_event
}  // namespace base

namespace BASE_HASH_NAMESPACE {

template <>
struct hash<base::trace_event::Backtrace> {
  size_t operator()(const base::trace_event::Backtrace& backtrace) const;
};

}  // BASE_HASH_NAMESPACE

#endif  // BASE_TRACE_EVENT_MEMORY_PROFILER_ALLOCATION_CONTEXT_H_