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