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