1 : // Copyright 2012 Google Inc.
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 : // This defines the pure virtual Reorderer base class. This class abstracts
16 : // away the ETW log parsing, decomposition, Block lookup, etc, that is a routine
17 : // part of producing a new ordering. Derived classes are to implement actual
18 : // order generation.
19 :
20 : #ifndef SYZYGY_REORDER_REORDERER_H_
21 : #define SYZYGY_REORDER_REORDERER_H_
22 :
23 : #include <windows.h> // NOLINT
24 : #include <dbghelp.h>
25 :
26 : #include <map>
27 : #include <set>
28 : #include <string>
29 : #include <vector>
30 :
31 : #include "base/win/event_trace_consumer.h"
32 : #include "sawbuck/log_lib/kernel_log_consumer.h"
33 : #include "syzygy/pe/decomposer.h"
34 : #include "syzygy/pe/image_layout.h"
35 : #include "syzygy/playback/playback.h"
36 : #include "syzygy/trace/parse/parser.h"
37 :
38 : // Forward declaration.
39 : namespace core {
40 : class JSONFileWriter;
41 : } // namespace core
42 :
43 : namespace reorder {
44 :
45 : typedef uint64 AbsoluteAddress64;
46 : typedef uint64 Size64;
47 :
48 : // This class can consume a set of call-trace logs captured for a PE image
49 : // while driving an OrderGenerator instance to produce an ordering file.
50 : class Reorderer : public trace::parser::ParseEventHandlerImpl {
51 : public:
52 : typedef trace::parser::Parser Parser;
53 : typedef pe::ImageLayout ImageLayout;
54 : typedef pe::PEFile PEFile;
55 : typedef std::vector<FilePath> TraceFileList;
56 :
57 : struct Order;
58 : class OrderGenerator;
59 : class UniqueTime;
60 :
61 : // A bit flag of directives that the derived reorderer should attempt
62 : // to satisfy.
63 : // TODO(chrisha): Basic block reordering.
64 : enum FlagsEnum {
65 : kFlagReorderCode = 1 << 0,
66 : kFlagReorderData = 1 << 1,
67 : };
68 : typedef uint32 Flags;
69 :
70 : // Construct a new reorder instance.
71 : // @param module_path The path of the module dll.
72 : // @param instrumented_path The path of the instrumented dll.
73 : // @param trace_files A list of trace files to analyze.
74 : // @param flags Flags passed to Reorderer.
75 : Reorderer(const FilePath& module_path,
76 : const FilePath& instrumented_path,
77 : const TraceFileList& trace_files,
78 : Flags flags);
79 :
80 : virtual ~Reorderer();
81 :
82 : // Runs the reorderer, parsing the call-trace logs and generating an
83 : // ordering using the given order generation strategy.
84 : //
85 : // @note This function cannot be called concurrently across Reorderer
86 : // instances because the ETW parser must be a singleton due to the
87 : // way the Windows ETW API is structured. This is enforced in debug
88 : // builds.
89 : //
90 : // @returns true on success, false otherwise.
91 : // @pre order must not be NULL.
92 : bool Reorder(OrderGenerator* order_generator,
93 : Order* order,
94 : PEFile* pe_file,
95 : ImageLayout* image);
96 :
97 : // @name Accessors
98 : // @{
99 : Flags flags() const { return flags_; }
100 : const Parser& parser() const { return parser_; }
101 : // @}
102 :
103 : protected:
104 : typedef block_graph::BlockGraph BlockGraph;
105 : typedef core::RelativeAddress RelativeAddress;
106 : typedef playback::Playback Playback;
107 : typedef std::set<uint32> ProcessSet;
108 : typedef trace::parser::ModuleInformation ModuleInformation;
109 : typedef TraceFileList::iterator TraceFileIter;
110 :
111 : // The implementation of Reorder.
112 : bool ReorderImpl(Order* order, PEFile* pe_file, ImageLayout* image);
113 :
114 : // Calculates the actual reordering.
115 : bool CalculateReordering(Order* order);
116 :
117 : // @name ParseEventHandler overrides.
118 : // @{
119 : virtual void OnProcessEnded(base::Time time, DWORD process_id) OVERRIDE;
120 : virtual void OnFunctionEntry(base::Time time,
121 : DWORD process_id,
122 : DWORD thread_id,
123 : const TraceEnterExitEventData* data) OVERRIDE;
124 : virtual void OnBatchFunctionEntry(base::Time time,
125 : DWORD process_id,
126 : DWORD thread_id,
127 : const TraceBatchEnterData* data) OVERRIDE;
128 : // @}
129 :
130 : // A playback, which will decompose the image for us.
131 : Playback playback_;
132 :
133 : // A set of flags controlling the reorderer behaviour.
134 : Flags flags_;
135 :
136 : // Number of CodeBlockEntry events processed.
137 : size_t code_block_entry_events_;
138 :
139 : // The following three variables are only valid while Reorder is executing.
140 : // A pointer to our order generator delegate.
141 : OrderGenerator* order_generator_;
142 :
143 : // The call-trace log file parser. It is used in conjunction with Playback
144 : // to trace the log file and capture events.
145 : Parser parser_;
146 :
147 : // The set of processes of interest. That is, those that have had code
148 : // run in the instrumented module. These are the only processes for which
149 : // we are interested in OnProcessEnded events.
150 : ProcessSet matching_process_ids_;
151 :
152 : // A cache for whether or not to reorder each section.
153 : typedef std::vector<bool> SectionReorderabilityCache;
154 : SectionReorderabilityCache section_reorderability_cache_;
155 :
156 : DISALLOW_COPY_AND_ASSIGN(Reorderer);
157 : };
158 :
159 : // Stores order information. An order may be serialized to and from JSON,
160 : // in the following format:
161 : //
162 : // {
163 : // 'metadata': {
164 : // this contains toolchain information, command-line info, etc
165 : // },
166 : // 'sections': {
167 : // 'section_id': <INTEGER SECTION ID>,
168 : // 'blocks': [
169 : // list of integer block addresses
170 : // ]
171 : // ]
172 : // }
173 : struct Reorderer::Order {
174 E : Order() {}
175 :
176 : // A comment describing the ordering.
177 : std::string comment;
178 :
179 : // An ordering of blocks. This list need not be exhaustive, but each
180 : // block should only appear once within it. We currently constrain ourselves
181 : // to keep blocks in the same section from which they originate. Thus, we
182 : // separate the order information per section, with the section IDs coming
183 : // from the ImageLayout of the original module.
184 : // TODO(rogerm): Fix the BlockList references to refer to ConstBlockVector.
185 : typedef block_graph::ConstBlockVector BlockList;
186 : typedef std::map<size_t, BlockList> BlockListMap;
187 : BlockListMap section_block_lists;
188 :
189 : // Serializes the order to JSON. Returns true on success, false otherwise.
190 : // The serialization simply consists of the start addresses of each block
191 : // in a JSON list. Pretty-printing adds further information from the
192 : // BlockGraph via inline comments.
193 : bool SerializeToJSON(const PEFile& pe,
194 : const FilePath& path,
195 : bool pretty_print) const;
196 : bool SerializeToJSON(const PEFile& pe,
197 : core::JSONFileWriter* json_file) const;
198 :
199 : // Loads an ordering from a JSON file. 'pe' and 'image' must already be
200 : // populated prior to calling this.
201 : bool LoadFromJSON(const PEFile& pe,
202 : const ImageLayout& image,
203 : const FilePath& path);
204 :
205 : // Extracts the name of the original module from an order file. This is
206 : // used to guess the value of --input-dll.
207 : static bool GetOriginalModulePath(const FilePath& path, FilePath* module);
208 :
209 : private:
210 : DISALLOW_COPY_AND_ASSIGN(Order);
211 : };
212 :
213 : // The actual class that does the work, an order generator. It receives
214 : // call trace events (already mapped to blocks in a disassembled image),
215 : // and is asked to build an ordering.
216 : class Reorderer::OrderGenerator {
217 : public:
218 : typedef block_graph::BlockGraph BlockGraph;
219 : typedef BlockGraph::AddressSpace AddressSpace;
220 : typedef core::RelativeAddress RelativeAddress;
221 : typedef pe::ImageLayout ImageLayout;
222 : typedef pe::PEFile PEFile;
223 : typedef Reorderer::Order Order;
224 : typedef Reorderer::UniqueTime UniqueTime;
225 :
226 E : explicit OrderGenerator(const char* name) : name_(name) {}
227 E : virtual ~OrderGenerator() {}
228 :
229 : // Accessor.
230 E : const std::string& name() const { return name_; }
231 :
232 : // The derived class may implement this callback, which indicates when a
233 : // process invoking the instrumented module was started.
234 : virtual bool OnProcessStarted(uint32 process_id,
235 E : const UniqueTime& time) { return true; }
236 :
237 : // The derived class may implement this callback, which provides
238 : // information on the end of processes invoking the instrumented module.
239 : // Processes whose lifespan exceed the logging period will not receive
240 : // OnProcessEnded events.
241 : virtual bool OnProcessEnded(uint32 process_id,
242 E : const UniqueTime& time) { return true; }
243 :
244 : // The derived class shall implement this callback, which receives
245 : // TRACE_ENTRY events for the module that is being reordered. Returns true
246 : // on success, false on error. If this returns false, no further callbacks
247 : // will be processed.
248 : virtual bool OnCodeBlockEntry(const BlockGraph::Block* block,
249 : RelativeAddress address,
250 : uint32 process_id,
251 : uint32 thread_id,
252 : const UniqueTime& time) = 0;
253 :
254 : // The derived class shall implement this function, which actually produces
255 : // the reordering. When this is called, the callee can be assured that the
256 : // ImageLayout is populated and all traces have been parsed. This must
257 : // return true on success, false otherwise.
258 : virtual bool CalculateReordering(const PEFile& pe_file,
259 : const ImageLayout& image,
260 : bool reorder_code,
261 : bool reorder_data,
262 : Order* order) = 0;
263 :
264 : private:
265 : const std::string name_;
266 :
267 : DISALLOW_COPY_AND_ASSIGN(OrderGenerator);
268 : };
269 :
270 : // A unique time class. No two instances of this class will ever be equal
271 : // This allows events that map to the same time (down to the resolution reported
272 : // to us) to still maintain a unique temporal ordering. This is done by using
273 : // a secondary counter value. It is necessary because we often get buffers full
274 : // of events that have the same time indicated, but that we know to be in the
275 : // temporal order in which they are stored in the buffer.
276 : class Reorderer::UniqueTime {
277 : public:
278 : // This class has a copy-constructor and is assignable in order to be STL
279 : // container compatible.
280 : UniqueTime();
281 : UniqueTime(const UniqueTime& other);
282 : explicit UniqueTime(const base::Time& time);
283 :
284 : UniqueTime& operator=(const UniqueTime& rhs);
285 :
286 : const base::Time& time() const { return time_; }
287 : size_t id() const { return id_; }
288 :
289 : // Compares two UniqueTime objects, returning a value from the set {-1, 0, 1}.
290 : int compare(const UniqueTime& rhs) const;
291 :
292 : // Standard comparison operators.
293 E : bool operator<(const UniqueTime& rhs) const { return compare(rhs) < 0; }
294 : bool operator>(const UniqueTime& rhs) const { return compare(rhs) > 0; }
295 : bool operator<=(const UniqueTime& rhs) const { return compare(rhs) <= 0; }
296 : bool operator>=(const UniqueTime& rhs) const { return compare(rhs) >= 0; }
297 : bool operator==(const UniqueTime& rhs) const { return compare(rhs) == 0; }
298 : bool operator!=(const UniqueTime& rhs) const { return compare(rhs) != 0; }
299 :
300 : private:
301 : base::Time time_;
302 : size_t id_;
303 :
304 : // Stores the next id that will be used in constructing a unique time object.
305 : static size_t next_id_;
306 : };
307 :
308 : } // namespace reorder
309 :
310 : #endif // SYZYGY_REORDER_REORDERER_H_
|