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 StackFrame frame; 38 39 // The index of the parent stack frame in |frames_|, or -1 if there is no 40 // parent frame (when it is at the bottom of the call stack). 41 int parent_frame_index; 42 43 // Indices into |frames_| of frames called from the current frame. 44 std::map<StackFrame, int> children; 45 }; 46 47 using ConstIterator = std::vector<FrameNode>::const_iterator; 48 49 StackFrameDeduplicator(); 50 ~StackFrameDeduplicator() override; 51 52 // Inserts a backtrace where |beginFrame| is a pointer to the bottom frame 53 // (e.g. main) and |endFrame| is a pointer past the top frame (most recently 54 // called function), and returns the index of its leaf node in |frames_|. 55 // Returns -1 if the backtrace is empty. 56 int Insert(const StackFrame* beginFrame, const StackFrame* endFrame); 57 58 // Iterators over the frame nodes in the call tree. begin()59 ConstIterator begin() const { return frames_.begin(); } end()60 ConstIterator end() const { return frames_.end(); } 61 62 // Writes the |stackFrames| dictionary as defined in https://goo.gl/GerkV8 to 63 // the trace log. 64 void AppendAsTraceFormat(std::string* out) const override; 65 66 // Estimates memory overhead including |sizeof(StackFrameDeduplicator)|. 67 void EstimateTraceMemoryOverhead(TraceEventMemoryOverhead* overhead) override; 68 69 private: 70 std::map<StackFrame, int> roots_; 71 std::vector<FrameNode> frames_; 72 73 DISALLOW_COPY_AND_ASSIGN(StackFrameDeduplicator); 74 }; 75 76 } // namespace trace_event 77 } // namespace base 78 79 #endif // BASE_TRACE_EVENT_HEAP_PROFILER_STACK_FRAME_DEDUPLICATOR_H_ 80