Home | History | Annotate | Download | only in trace_event 
      1 // Copyright 2015 The Chromium 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 BASE_TRACE_EVENT_HEAP_PROFILER_STACK_FRAME_DEDUPLICATOR_H_
      6 #define BASE_TRACE_EVENT_HEAP_PROFILER_STACK_FRAME_DEDUPLICATOR_H_
      7 
      8 #include <map>
      9 #include <string>
     10 #include <vector>
     11 
     12 #include "base/base_export.h"
     13 #include "base/macros.h"
     14 #include "base/trace_event/heap_profiler_allocation_context.h"
     15 #include "base/trace_event/trace_event_impl.h"
     16 
     17 namespace base {
     18 namespace trace_event {
     19 
     20 class TraceEventMemoryOverhead;
     21 
     22 // A data structure that allows grouping a set of backtraces in a space-
     23 // efficient manner by creating a call tree and writing it as a set of (node,
     24 // parent) pairs. The tree nodes reference both parent and children. The parent
     25 // is referenced by index into |frames_|. The children are referenced via a map
     26 // of |StackFrame|s to index into |frames_|. So there is a trie for bottum-up
     27 // lookup of a backtrace for deduplication, and a tree for compact storage in
     28 // the trace log.
     29 class BASE_EXPORT StackFrameDeduplicator : public ConvertableToTraceFormat {
     30  public:
     31   // A node in the call tree.
     32   struct FrameNode {
     33     FrameNode(StackFrame frame, int parent_frame_index);
     34     FrameNode(const FrameNode& other);
     35     ~FrameNode();
     36 
     37     size_t EstimateMemoryUsage() const;
     38 
     39     StackFrame frame;
     40 
     41     // The index of the parent stack frame in |frames_|, or -1 if there is no
     42     // parent frame (when it is at the bottom of the call stack).
     43     int parent_frame_index;
     44 
     45     // Indices into |frames_| of frames called from the current frame.
     46     std::map<StackFrame, int> children;
     47   };
     48 
     49   using ConstIterator = std::vector<FrameNode>::const_iterator;
     50 
     51   StackFrameDeduplicator();
     52   ~StackFrameDeduplicator() override;
     53 
     54   // Inserts a backtrace where |beginFrame| is a pointer to the bottom frame
     55   // (e.g. main) and |endFrame| is a pointer past the top frame (most recently
     56   // called function), and returns the index of its leaf node in |frames_|.
     57   // Returns -1 if the backtrace is empty.
     58   int Insert(const StackFrame* beginFrame, const StackFrame* endFrame);
     59 
     60   // Iterators over the frame nodes in the call tree.
     61   ConstIterator begin() const { return frames_.begin(); }
     62   ConstIterator end() const { return frames_.end(); }
     63 
     64   // Writes the |stackFrames| dictionary as defined in https://goo.gl/GerkV8 to
     65   // the trace log.
     66   void AppendAsTraceFormat(std::string* out) const override;
     67 
     68   // Estimates memory overhead including |sizeof(StackFrameDeduplicator)|.
     69   void EstimateTraceMemoryOverhead(TraceEventMemoryOverhead* overhead) override;
     70 
     71  private:
     72   std::map<StackFrame, int> roots_;
     73   std::vector<FrameNode> frames_;
     74 
     75   DISALLOW_COPY_AND_ASSIGN(StackFrameDeduplicator);
     76 };
     77 
     78 }  // namespace trace_event
     79 }  // namespace base
     80 
     81 #endif  // BASE_TRACE_EVENT_HEAP_PROFILER_STACK_FRAME_DEDUPLICATOR_H_
     82