1 : // Copyright 2015 Google Inc. All Rights Reserved.
2 : //
3 : // Licensed under the Apache License, Version 2.0 (the "License");
4 : // you may not use this file except in compliance with the License.
5 : // You may obtain a copy of the License at
6 : //
7 : // http://www.apache.org/licenses/LICENSE-2.0
8 : //
9 : // Unless required by applicable law or agreed to in writing, software
10 : // distributed under the License is distributed on an "AS IS" BASIS,
11 : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 : // See the License for the specific language governing permissions and
13 : // limitations under the License.
14 : //
15 : // Declares the MemReplayGrinder class, which processes trace files
16 : // containing the list of heap accesses and outputs a test scenario
17 : // for replay.
18 : #ifndef SYZYGY_GRINDER_GRINDERS_MEM_REPLAY_GRINDER_H_
19 : #define SYZYGY_GRINDER_GRINDERS_MEM_REPLAY_GRINDER_H_
20 :
21 : #include <deque>
22 : #include <map>
23 : #include <set>
24 : #include <string>
25 : #include <unordered_map>
26 : #include <unordered_set>
27 : #include <utility>
28 : #include <vector>
29 :
30 : #include "base/memory/scoped_ptr.h"
31 : #include "syzygy/bard/event.h"
32 : #include "syzygy/bard/story.h"
33 : #include "syzygy/bard/events/linked_event.h"
34 : #include "syzygy/grinder/grinder.h"
35 :
36 : namespace grinder {
37 : namespace grinders {
38 :
39 : // This class processes trace files containing the raw history of
40 : // of heap allocations and deallocations, and generates a reduced
41 : // trace file to be used as a test scenario.
42 : class MemReplayGrinder : public GrinderInterface {
43 : public:
44 : MemReplayGrinder();
45 E : ~MemReplayGrinder() override {}
46 :
47 : // @name GrinderInterface implementation.
48 : // @{
49 : bool ParseCommandLine(const base::CommandLine* command_line) override;
50 : void SetParser(Parser* parser) override;
51 : bool Grind() override;
52 : bool OutputData(FILE* file) override;
53 : // @}
54 :
55 : // @name ParserEventHandler implementation.
56 : // @{
57 : void OnFunctionNameTableEntry(
58 : base::Time time,
59 : DWORD process_id,
60 : const TraceFunctionNameTableEntry* data) override;
61 : void OnDetailedFunctionCall(base::Time time,
62 : DWORD process_id,
63 : DWORD thread_id,
64 : const TraceDetailedFunctionCall* data) override;
65 : void OnProcessHeap(base::Time time,
66 : DWORD process_id,
67 : const TraceProcessHeap* data) override;
68 : // @}
69 :
70 : // Protected for unittesting.
71 : protected:
72 : using EventInterface = bard::EventInterface;
73 : using EventType = EventInterface::EventType;
74 :
75 : // See below for comments and definitions.
76 : class PendingDetailedFunctionCall;
77 : struct ThreadData;
78 : struct ProcessData;
79 : struct ThreadDataIterator;
80 :
81 : using PendingDetailedFunctionCalls = std::deque<PendingDetailedFunctionCall>;
82 : // Associates objects by addresses in the trace file to the event in which
83 : // they are created. The event is encoded by the ThreadDataIterator
84 : // referring to it.
85 : using ObjectMap = std::unordered_map<const void*, ThreadDataIterator>;
86 : // A collection of objects describing a dependency.
87 : using Deps = std::unordered_set<const void*>;
88 : // Tracks dependencies that have already been explicitly encoded. A thread
89 : // |i| that has already waited on a thread |j| will store the most recent
90 : // event waited on in the map associated with key (i, j).
91 : using PlotLinePair =
92 : std::pair<const bard::Story::PlotLine*, const bard::Story::PlotLine*>;
93 : using WaitedMap = std::map<PlotLinePair, ThreadDataIterator>;
94 :
95 : // Loads the function_enum_map_ with SyzyASan function names.
96 : void LoadAsanFunctionNames();
97 : // Parses a detailed function call record.
98 : bool ParseDetailedFunctionCall(base::Time time,
99 : DWORD thread_id,
100 : const TraceDetailedFunctionCall* data,
101 : ProcessData* proc_data);
102 : // Sets parse_error_ to true.
103 : void SetParseError();
104 : // Finds or creates the process data for a given process.
105 : ProcessData* FindOrCreateProcessData(DWORD process_id);
106 : // Finds or creates the thread data in the provided process data, for the
107 : // provided thread.
108 : ThreadData* FindOrCreateThreadData(ProcessData* proc_data, DWORD thread_id);
109 :
110 : // Ensures that the given event is a LinkedEvent, and thus able to support
111 : // dependencies.
112 : void EnsureLinkedEvent(const ThreadDataIterator& iter);
113 : // Gets the set of dependencies for the given event from the given object
114 : // map.
115 : bool GetDeps(const ThreadDataIterator& iter, Deps* deps);
116 : // Applies the given set of dependencies to provided event, updating the
117 : // @p waited_map.
118 : bool ApplyDeps(const ThreadDataIterator& iter,
119 : const ObjectMap& object_map,
120 : const Deps& deps,
121 : WaitedMap* waited_map);
122 : // Updates the provided @p object_map with information from the event pointed
123 : // to by @p iter.
124 : bool UpdateObjectMap(const ThreadDataIterator& iter, ObjectMap* object_map);
125 :
126 : // A map of recognized function names to EventType. If it's name isn't
127 : // in this map before grinding starts then the function will not be parsed.
128 : std::map<std::string, EventType> function_enum_map_;
129 : // The set of unrecognized function names. Any functions that are encountered
130 : // but not found in |function_enum_map_| will be recorded here for logging
131 : // purposes.
132 : std::set<std::string> missing_events_;
133 :
134 : // Storage for stories and plotlines. Stories are kept separate from the
135 : // ProcessData that indexes them so that the ProcessData can remain easily
136 : // copyable and compatible with STL containers.
137 : ScopedVector<bard::Story> stories_;
138 : std::map<DWORD, ProcessData> process_data_map_;
139 :
140 : // Set to true if a parse error occurs.
141 : bool parse_error_;
142 :
143 : private:
144 : DISALLOW_COPY_AND_ASSIGN(MemReplayGrinder);
145 : };
146 :
147 : // DetailedFunctionCall records can only be parsed if the required
148 : // FunctionNameTable record has already been parsed. Unfortunately, these can
149 : // arrive out of order so sometimes the function call parsing needs to be
150 : // deferred. This structure houses the necessary information (effectively the
151 : // input arguments to OnDetailedFunctionCall).
152 : class MemReplayGrinder::PendingDetailedFunctionCall {
153 : public:
154 : PendingDetailedFunctionCall(base::Time time,
155 : DWORD thread_id,
156 : const TraceDetailedFunctionCall* data);
157 :
158 E : const base::Time& time() const { return time_; }
159 E : DWORD thread_id() const { return thread_id_; }
160 E : const TraceDetailedFunctionCall* data() const {
161 E : return reinterpret_cast<const TraceDetailedFunctionCall*>(data_.data());
162 E : }
163 :
164 : private:
165 : base::Time time_;
166 : DWORD thread_id_;
167 : std::vector<uint8> data_;
168 : };
169 :
170 : // Houses timestamps and PlotLine data associated with a thread ID. This is
171 : // indexed by thread ID in a containing ProcessData.
172 : struct MemReplayGrinder::ThreadData {
173 E : ThreadData() : plot_line(nullptr) {}
174 :
175 : // The timestamps associated with the events in the plot line.
176 : std::vector<uint64> timestamps;
177 : // The PlotLine representing the events in this thread.
178 : bard::Story::PlotLine* plot_line;
179 : };
180 :
181 : // Houses all data associated with a single process during grinding. This is
182 : // indexed in a map by |process_id|.
183 : struct MemReplayGrinder::ProcessData {
184 E : ProcessData() : process_id(0), story(nullptr) {}
185 :
186 : // The process ID.
187 : DWORD process_id;
188 : // All pre-existing heaps. The first is the process heap.
189 : std::vector<const void*> existing_heaps;
190 : // Map from trace file function ID to EventType enumeration.
191 : std::map<uint32_t, EventType> function_id_map;
192 : // The set of function IDs for which definitions have not yet been seen.
193 : // When this set is drained all the pending_calls can be processed.
194 : std::unordered_set<uint32_t> pending_function_ids;
195 : // The list of detailed function calls that is pending processing.
196 : PendingDetailedFunctionCalls pending_calls;
197 : // The story holding events for this process. Ownership is external
198 : // to this object.
199 : bard::Story* story;
200 : // A map of thread ID to the associated thread data.
201 : std::map<DWORD, ThreadData> thread_data_map;
202 : };
203 :
204 : // An iterator-like object for events in a story, sorted by their associated
205 : // timestamp.
206 : struct MemReplayGrinder::ThreadDataIterator {
207 E : uint64_t timestamp() const { return thread_data->timestamps[index]; }
208 :
209 E : bard::Story::PlotLine* plot_line() const { return thread_data->plot_line; }
210 :
211 E : bard::EventInterface* event() const {
212 E : return (*thread_data->plot_line)[index];
213 E : }
214 :
215 E : const bard::EventInterface* inner_event() const {
216 E : auto evt = event();
217 E : if (evt->type() != EventInterface::kLinkedEvent)
218 E : return evt;
219 E : auto e = reinterpret_cast<const bard::events::LinkedEvent*>(evt);
220 E : return e->event();
221 E : }
222 :
223 : // STL heaps are max heaps, so the comparison operator is reversed to create
224 : // a min heap.
225 E : bool operator<(const ThreadDataIterator& rhs) const {
226 E : return timestamp() > rhs.timestamp();
227 E : }
228 :
229 : // Increments this iterator. Returns true if there are events remaining
230 : // in the associated plot line.
231 E : bool increment() {
232 E : ++index;
233 E : return index < thread_data->timestamps.size();
234 E : }
235 :
236 : ThreadData* thread_data;
237 : size_t index;
238 : };
239 :
240 : } // namespace grinders
241 : } // namespace grinder
242 :
243 : #endif // SYZYGY_GRINDER_GRINDERS_MEM_REPLAY_GRINDER_H_
|