OLD | NEW |
1 // Copyright 2015 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #ifndef BASE_TRACE_EVENT_HEAP_PROFILER_STACK_FRAME_DEDUPLICATOR_H_ | 5 #ifndef BASE_TRACE_EVENT_HEAP_PROFILER_STACK_FRAME_DEDUPLICATOR_H_ |
6 #define BASE_TRACE_EVENT_HEAP_PROFILER_STACK_FRAME_DEDUPLICATOR_H_ | 6 #define BASE_TRACE_EVENT_HEAP_PROFILER_STACK_FRAME_DEDUPLICATOR_H_ |
7 | 7 |
8 #include <map> | 8 #include <map> |
9 #include <string> | 9 #include <string> |
10 #include <vector> | 10 #include <vector> |
11 | 11 |
12 #include "base/base_export.h" | 12 #include "base/base_export.h" |
13 #include "base/macros.h" | 13 #include "base/macros.h" |
14 #include "base/trace_event/heap_profiler_allocation_context.h" | 14 #include "base/trace_event/heap_profiler_allocation_context.h" |
15 #include "base/trace_event/trace_event_impl.h" | |
16 | 15 |
17 namespace base { | 16 namespace base { |
18 namespace trace_event { | 17 namespace trace_event { |
19 | 18 |
| 19 class StringDeduplicator; |
20 class TraceEventMemoryOverhead; | 20 class TraceEventMemoryOverhead; |
| 21 class TracedValue; |
21 | 22 |
22 // A data structure that allows grouping a set of backtraces in a space- | 23 // 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 // 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 // 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 // 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 // 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 // lookup of a backtrace for deduplication, and a tree for compact storage in |
28 // the trace log. | 29 // the trace log. |
29 class BASE_EXPORT StackFrameDeduplicator : public ConvertableToTraceFormat { | 30 class BASE_EXPORT StackFrameDeduplicator { |
30 public: | 31 public: |
31 // A node in the call tree. | 32 // A node in the call tree. |
32 struct FrameNode { | 33 struct FrameNode { |
33 FrameNode(StackFrame frame, int parent_frame_index); | 34 FrameNode(StackFrame frame, int parent_frame_index); |
34 FrameNode(const FrameNode& other); | 35 FrameNode(const FrameNode& other); |
35 ~FrameNode(); | 36 ~FrameNode(); |
36 | 37 |
37 size_t EstimateMemoryUsage() const; | 38 size_t EstimateMemoryUsage() const; |
38 | 39 |
39 StackFrame frame; | 40 StackFrame frame; |
40 | 41 |
41 // The index of the parent stack frame in |frames_|, or -1 if there is no | 42 // The index of the parent stack frame in |frames_|, or kInvalidFrameIndex |
42 // parent frame (when it is at the bottom of the call stack). | 43 // if there is no parent frame (when it is at the bottom of the call stack). |
43 int parent_frame_index; | 44 int parent_frame_index; |
| 45 constexpr static int kInvalidFrameIndex = -1; |
44 | 46 |
45 // Indices into |frames_| of frames called from the current frame. | 47 // Indices into |frames_| of frames called from the current frame. |
46 std::map<StackFrame, int> children; | 48 std::map<StackFrame, int> children; |
47 }; | 49 }; |
48 | 50 |
49 using ConstIterator = std::vector<FrameNode>::const_iterator; | 51 using ConstIterator = std::vector<FrameNode>::const_iterator; |
50 | 52 |
51 StackFrameDeduplicator(); | 53 // |string_deduplication| is used during serialization, and is expected |
52 ~StackFrameDeduplicator() override; | 54 // to outlive instances of this class. |
| 55 explicit StackFrameDeduplicator(StringDeduplicator* string_deduplicator); |
| 56 ~StackFrameDeduplicator(); |
53 | 57 |
54 // Inserts a backtrace where |beginFrame| is a pointer to the bottom frame | 58 // 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 | 59 // (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_|. | 60 // called function), and returns the index of its leaf node in |frames_|. |
57 // Returns -1 if the backtrace is empty. | 61 // Returns -1 if the backtrace is empty. |
58 int Insert(const StackFrame* beginFrame, const StackFrame* endFrame); | 62 int Insert(const StackFrame* beginFrame, const StackFrame* endFrame); |
59 | 63 |
60 // Iterators over the frame nodes in the call tree. | 64 // Iterators over the frame nodes in the call tree. |
61 ConstIterator begin() const { return frames_.begin(); } | 65 ConstIterator begin() const { return frames_.begin(); } |
62 ConstIterator end() const { return frames_.end(); } | 66 ConstIterator end() const { return frames_.end(); } |
63 | 67 |
64 // Writes the |stackFrames| dictionary as defined in https://goo.gl/GerkV8 to | 68 // Appends new |stackFrames| dictionary items that were added after the |
65 // the trace log. | 69 // last call to this function. |
66 void AppendAsTraceFormat(std::string* out) const override; | 70 void SerializeIncrementally(TracedValue* traced_value); |
67 | 71 |
68 // Estimates memory overhead including |sizeof(StackFrameDeduplicator)|. | 72 // Estimates memory overhead including |sizeof(StackFrameDeduplicator)|. |
69 void EstimateTraceMemoryOverhead(TraceEventMemoryOverhead* overhead) override; | 73 void EstimateTraceMemoryOverhead(TraceEventMemoryOverhead* overhead); |
70 | 74 |
71 private: | 75 private: |
| 76 StringDeduplicator* string_deduplicator_; |
| 77 |
72 std::map<StackFrame, int> roots_; | 78 std::map<StackFrame, int> roots_; |
73 std::vector<FrameNode> frames_; | 79 std::vector<FrameNode> frames_; |
| 80 size_t last_exported_index_; |
74 | 81 |
75 DISALLOW_COPY_AND_ASSIGN(StackFrameDeduplicator); | 82 DISALLOW_COPY_AND_ASSIGN(StackFrameDeduplicator); |
76 }; | 83 }; |
77 | 84 |
78 } // namespace trace_event | 85 } // namespace trace_event |
79 } // namespace base | 86 } // namespace base |
80 | 87 |
81 #endif // BASE_TRACE_EVENT_HEAP_PROFILER_STACK_FRAME_DEDUPLICATOR_H_ | 88 #endif // BASE_TRACE_EVENT_HEAP_PROFILER_STACK_FRAME_DEDUPLICATOR_H_ |
OLD | NEW |