1 : // Copyright 2012 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 : // 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 "syzygy/pe/decomposer.h"
33 : #include "syzygy/pe/image_layout.h"
34 : #include "syzygy/playback/playback.h"
35 : #include "syzygy/trace/parse/parser.h"
36 :
37 : // Forward declaration.
38 : namespace core {
39 : class JSONFileWriter;
40 : } // namespace core
41 :
42 : namespace reorder {
43 :
44 : typedef uint64 AbsoluteAddress64;
45 : typedef uint64 Size64;
46 :
47 : // This class can consume a set of call-trace logs captured for a PE image
48 : // while driving an OrderGenerator instance to produce an ordering file.
49 : class Reorderer : public trace::parser::ParseEventHandlerImpl {
50 : public:
51 : typedef trace::parser::Parser Parser;
52 : typedef pe::ImageLayout ImageLayout;
53 : typedef pe::PEFile PEFile;
54 : typedef std::vector<base::FilePath> TraceFileList;
55 :
56 : struct Order;
57 : class OrderGenerator;
58 : class UniqueTime;
59 :
60 : // A bit flag of directives that the derived reorderer should attempt
61 : // to satisfy.
62 : // TODO(chrisha): Basic block reordering.
63 : enum FlagsEnum {
64 : kFlagReorderCode = 1 << 0,
65 : kFlagReorderData = 1 << 1,
66 : };
67 : typedef uint32 Flags;
68 :
69 : // Construct a new reorder instance.
70 : // @param module_path The path of the module dll.
71 : // @param instrumented_path The path of the instrumented dll.
72 : // @param trace_files A list of trace files to analyze.
73 : // @param flags Flags passed to Reorderer.
74 : Reorderer(const base::FilePath& module_path,
75 : const base::FilePath& instrumented_path,
76 : const TraceFileList& trace_files,
77 : Flags flags);
78 :
79 : virtual ~Reorderer();
80 :
81 : // Runs the reorderer, parsing the call-trace logs and generating an
82 : // ordering using the given order generation strategy.
83 : //
84 : // @note This function cannot be called concurrently across Reorderer
85 : // instances because the ETW parser must be a singleton due to the
86 : // way the Windows ETW API is structured. This is enforced in debug
87 : // builds.
88 : //
89 : // @returns true on success, false otherwise.
90 : // @pre order must not be NULL.
91 : bool Reorder(OrderGenerator* order_generator,
92 : Order* order,
93 : PEFile* pe_file,
94 : ImageLayout* image);
95 :
96 : // @name Accessors
97 : // @{
98 : Flags flags() const { return flags_; }
99 : const Parser& parser() const { return parser_; }
100 : // @}
101 :
102 : protected:
103 : typedef block_graph::BlockGraph BlockGraph;
104 : typedef core::RelativeAddress RelativeAddress;
105 : typedef playback::Playback Playback;
106 : typedef std::set<uint32> ProcessSet;
107 : typedef trace::parser::ModuleInformation ModuleInformation;
108 : typedef TraceFileList::iterator TraceFileIter;
109 :
110 : // The implementation of Reorder.
111 : bool ReorderImpl(Order* order, PEFile* pe_file, ImageLayout* image);
112 :
113 : // Calculates the actual reordering.
114 : bool CalculateReordering(Order* order);
115 :
116 : // @name ParseEventHandler overrides.
117 : // @{
118 : virtual void OnProcessStarted(base::Time time,
119 : DWORD process_id,
120 : const TraceSystemInfo* data) override;
121 : virtual void OnProcessEnded(base::Time time, DWORD process_id) override;
122 : virtual void OnFunctionEntry(base::Time time,
123 : DWORD process_id,
124 : DWORD thread_id,
125 : const TraceEnterExitEventData* data) override;
126 : virtual void OnBatchFunctionEntry(base::Time time,
127 : DWORD process_id,
128 : DWORD thread_id,
129 : const TraceBatchEnterData* data) override;
130 : // @}
131 :
132 : // A playback, which will decompose the image for us.
133 : Playback playback_;
134 :
135 : // A set of flags controlling the reorderer's behaviour.
136 : Flags flags_;
137 :
138 : // Number of CodeBlockEntry events processed.
139 : size_t code_block_entry_events_;
140 :
141 : // The following three variables are only valid while Reorder is executing.
142 : // A pointer to our order generator delegate.
143 : OrderGenerator* order_generator_;
144 :
145 : // The call-trace log file parser. It is used in conjunction with Playback
146 : // to trace the log file and capture events.
147 : Parser parser_;
148 :
149 : // A cache for whether or not to reorder each section.
150 : typedef std::vector<bool> SectionReorderabilityCache;
151 : SectionReorderabilityCache section_reorderability_cache_;
152 :
153 : DISALLOW_COPY_AND_ASSIGN(Reorderer);
154 : };
155 :
156 : // An ordering consists of a series of section specifications, where each
157 : // section specification describes the section (allowing it to be identified
158 : // in the original image or created it it does not already exist) and the
159 : // list of blocks that go into that section.
160 : //
161 : // Each block denotes the source block plus an optional ordered set of RVAs
162 : // falling within said block which denotes the basic blocks to include.
163 : //
164 : // TODO(rogerm): Flesh out support for synthesized blocks. In this scenario,
165 : // the referenced source block would be NULL and the basic-blocks RVAs
166 : // included in the synthesized block would be allowed to come from anywhere
167 : // in the image.
168 : //
169 : // An order may be serialized to and from JSON, in the following format:
170 : //
171 : // {
172 : // 'metadata': {
173 : // // This contains tool-chain information, command-line info, etc.
174 : // },
175 : // 'sections': [
176 : // {
177 : // "id": 1,
178 : // "name": ".foo",
179 : // "characteristics": 11111,
180 : // "blocks": [
181 : // 22222, # Use this block in it's entirety.
182 : // 33333, # Ditto.
183 : // [ 44444, [ 44444, 44448, .... ]], // Use selected basic-blocks.
184 : // ...
185 : // ]
186 : // },
187 : // ...
188 : // ]
189 : // }
190 : //
191 : // A section may be given either by its id (zero-based index) in the original
192 : // image layout and/or by name and characteristics. If given by id, the name
193 : // and characteristics are optional. These values will be populated from the
194 : // corresponding section in the original image. If the name and characteristics
195 : // are also specified in addition to the id, they will over-ride the values in
196 : // the original image. If the id is not specified, then name and characteristics
197 : // are required and denote a newly created section.
198 : struct Reorderer::Order {
199 : typedef BlockGraph::Block Block;
200 : typedef BlockGraph::Offset Offset;
201 : typedef std::vector<Offset> OffsetVector;
202 :
203 : // The structure describing a block in the ordering.
204 : struct BlockSpec {
205 E : BlockSpec() : block(NULL) {}
206 E : explicit BlockSpec(const Block* b) : block(b) { DCHECK(b != NULL); }
207 :
208 : // The source block.
209 : const Block* block;
210 :
211 : // The offsets of block's basic-blocks to include when placing this block
212 : // in the reordered image.
213 : OffsetVector basic_block_offsets;
214 : };
215 :
216 : // A type denoting an ordered collection of BlockSpec objects.
217 : typedef std::vector<BlockSpec> BlockSpecVector;
218 :
219 : // The structure describing a section in the ordering.
220 : struct SectionSpec {
221 E : SectionSpec() : id(kNewSectionId), characteristics(0) {
222 E : }
223 :
224 : // A sentinel section id denoting that a new section should be created.
225 : static const BlockGraph::SectionId kNewSectionId;
226 :
227 : // Section ID. If this is kNewSectionId then this specification describes a
228 : // new section to be added to the image. Otherwise, it refers to an existing
229 : // section in the original image. If this is not explicitly specified in the
230 : // JSON file, it defaults to kNewSectionId.
231 : BlockGraph::SectionId id;
232 :
233 : // The name this section should have in the final image. If id refers to
234 : // an existing section and the name does not match, then the section will
235 : // be renamed. If this is not explicitly set in the JSON file then the the
236 : // ID must be specified and this well be populated with the section name of
237 : // the original section in the original image layout.
238 : std::string name;
239 :
240 : // The characteristics this section should have in the final image. If id
241 : // refers to an existing section and the characteristics do not match, then
242 : // they will be changed. If this is not explicitly set in the JSON file then
243 : // the id must be specified and this will be populated with the section
244 : // characteristics of the original section in in the original image layout.
245 : DWORD characteristics;
246 :
247 : // The ordered collection of blocks in this section.
248 : BlockSpecVector blocks;
249 : };
250 :
251 : // An ordered collection of section specifications. The order in which the
252 : // section specifications occur in the collection will be the order in
253 : // which the orderer will attempt to construct the output image. Note that
254 : // not all orders may be valid. Each orderer is free to define whether or
255 : // not it will honor the section ordering on a best-effort basis, or will
256 : // reject outright an invalid ordering.
257 : typedef std::vector<SectionSpec> SectionSpecVector;
258 :
259 E : Order() {}
260 :
261 : // A comment describing the ordering.
262 : std::string comment;
263 :
264 : // The ordered collection of section specifications.
265 : SectionSpecVector sections;
266 :
267 : // Serializes the order to JSON. Returns true on success, false otherwise.
268 : // The serialization simply consists of the start addresses of each block
269 : // in a JSON list. Pretty-printing adds further information from the
270 : // BlockGraph via inline comments.
271 : // @{
272 : bool SerializeToJSON(const PEFile& pe,
273 : const base::FilePath& path,
274 : bool pretty_print) const;
275 : bool SerializeToJSON(const PEFile& pe,
276 : core::JSONFileWriter* json_file) const;
277 : // @}
278 :
279 : // Loads an ordering from a JSON file.
280 : // @note @p pe and @p image must already be populated prior to calling this.
281 : bool LoadFromJSON(const PEFile& pe,
282 : const ImageLayout& image,
283 : const base::FilePath& path);
284 :
285 : // Extracts the name of the original module from an order file. This is
286 : // used to guess the value of --input-image.
287 : static bool GetOriginalModulePath(const base::FilePath& path,
288 : base::FilePath* module);
289 :
290 : private:
291 : DISALLOW_COPY_AND_ASSIGN(Order);
292 : };
293 :
294 : // The actual class that does the work, an order generator. It receives
295 : // call trace events (already mapped to blocks in a disassembled image),
296 : // and is asked to build an ordering.
297 : class Reorderer::OrderGenerator {
298 : public:
299 : typedef block_graph::BlockGraph BlockGraph;
300 : typedef BlockGraph::AddressSpace AddressSpace;
301 : typedef core::RelativeAddress RelativeAddress;
302 : typedef pe::ImageLayout ImageLayout;
303 : typedef pe::PEFile PEFile;
304 : typedef Reorderer::Order Order;
305 : typedef Reorderer::UniqueTime UniqueTime;
306 :
307 E : explicit OrderGenerator(const char* name) : name_(name) {}
308 E : virtual ~OrderGenerator() {}
309 :
310 : // Accessor.
311 E : const std::string& name() const { return name_; }
312 :
313 : // The derived class may implement this callback, which indicates when a
314 : // process invoking the instrumented module was started.
315 : virtual bool OnProcessStarted(uint32 process_id,
316 E : const UniqueTime& time) { return true; }
317 :
318 : // The derived class may implement this callback, which provides
319 : // information on the end of processes invoking the instrumented module.
320 : // Processes whose lifespan exceed the logging period will not receive
321 : // OnProcessEnded events.
322 : virtual bool OnProcessEnded(uint32 process_id,
323 E : const UniqueTime& time) { return true; }
324 :
325 : // The derived class shall implement this callback, which receives
326 : // TRACE_ENTRY events for the module that is being reordered. Returns true
327 : // on success, false on error. If this returns false, no further callbacks
328 : // will be processed.
329 : virtual bool OnCodeBlockEntry(const BlockGraph::Block* block,
330 : RelativeAddress address,
331 : uint32 process_id,
332 : uint32 thread_id,
333 : const UniqueTime& time) = 0;
334 :
335 : // The derived class shall implement this function, which actually produces
336 : // the reordering. When this is called, the callee can be assured that the
337 : // ImageLayout is populated and all traces have been parsed. This must
338 : // return true on success, false otherwise.
339 : virtual bool CalculateReordering(const PEFile& pe_file,
340 : const ImageLayout& image,
341 : bool reorder_code,
342 : bool reorder_data,
343 : Order* order) = 0;
344 :
345 : private:
346 : const std::string name_;
347 :
348 : DISALLOW_COPY_AND_ASSIGN(OrderGenerator);
349 : };
350 :
351 : // A unique time class. No two instances of this class will ever be equal
352 : // This allows events that map to the same time (down to the resolution reported
353 : // to us) to still maintain a unique temporal ordering. This is done by using
354 : // a secondary counter value. It is necessary because we often get buffers full
355 : // of events that have the same time indicated, but that we know to be in the
356 : // temporal order in which they are stored in the buffer.
357 : class Reorderer::UniqueTime {
358 : public:
359 : // This class has a copy-constructor and is assignable in order to be STL
360 : // container compatible.
361 : UniqueTime();
362 : UniqueTime(const UniqueTime& other);
363 : explicit UniqueTime(const base::Time& time);
364 :
365 : UniqueTime& operator=(const UniqueTime& rhs);
366 :
367 : const base::Time& time() const { return time_; }
368 : size_t id() const { return id_; }
369 :
370 : // Compares two UniqueTime objects, returning a value from the set {-1, 0, 1}.
371 : int compare(const UniqueTime& rhs) const;
372 :
373 : // Standard comparison operators.
374 E : bool operator<(const UniqueTime& rhs) const { return compare(rhs) < 0; }
375 : bool operator>(const UniqueTime& rhs) const { return compare(rhs) > 0; }
376 : bool operator<=(const UniqueTime& rhs) const { return compare(rhs) <= 0; }
377 : bool operator>=(const UniqueTime& rhs) const { return compare(rhs) >= 0; }
378 : bool operator==(const UniqueTime& rhs) const { return compare(rhs) == 0; }
379 : bool operator!=(const UniqueTime& rhs) const { return compare(rhs) != 0; }
380 :
381 : private:
382 : base::Time time_;
383 : size_t id_;
384 :
385 : // Stores the next id that will be used in constructing a unique time object.
386 : static size_t next_id_;
387 : };
388 :
389 : } // namespace reorder
390 :
391 : #endif // SYZYGY_REORDER_REORDERER_H_
|