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 : #include "syzygy/reorder/reorderer.h"
16 :
17 : #include "base/file_util.h"
18 : #include "base/stringprintf.h"
19 : #include "base/utf_string_conversions.h"
20 : #include "base/values.h"
21 : #include "base/json/json_reader.h"
22 : #include "base/json/string_escape.h"
23 : #include "syzygy/common/defs.h"
24 : #include "syzygy/common/syzygy_version.h"
25 : #include "syzygy/core/json_file_writer.h"
26 : #include "syzygy/core/serialization.h"
27 : #include "syzygy/pdb/omap.h"
28 : #include "syzygy/pe/find.h"
29 : #include "syzygy/pe/metadata.h"
30 : #include "syzygy/pe/pe_file.h"
31 :
32 : namespace reorder {
33 :
34 : using block_graph::BlockGraph;
35 : using trace::parser::Parser;
36 :
37 : namespace {
38 :
39 : // Serializes a block list to JSON.
40 : bool OutputBlockList(size_t section_id,
41 : const Reorderer::Order::BlockList& blocks,
42 E : core::JSONFileWriter* json_file) {
43 E : DCHECK(json_file != NULL);
44 :
45 : if (!json_file->OpenDict() ||
46 : !json_file->OutputKey("section_id") ||
47 : !json_file->OutputInteger(section_id) ||
48 : !json_file->OutputKey("blocks") ||
49 E : !json_file->OpenList()) {
50 i : return false;
51 : }
52 :
53 E : for (size_t i = 0; i < blocks.size(); ++i) {
54 : // Output the block address.
55 E : if (!json_file->OutputInteger(blocks[i]->addr().value()))
56 i : return false;
57 :
58 : // If we're pretty printing, output a comment with some detail about the
59 : // block.
60 E : if (json_file->pretty_print()) {
61 : std::string comment = base::StringPrintf(
62 : "%s(%s)",
63 : BlockGraph::BlockTypeToString(blocks[i]->type()),
64 E : blocks[i]->name().c_str());
65 E : if (!json_file->OutputTrailingComment(comment.c_str()))
66 i : return false;
67 E : }
68 E : }
69 :
70 E : return json_file->CloseList() && json_file->CloseDict();
71 E : }
72 :
73 : } // namespace
74 :
75 : Reorderer::Reorderer(const FilePath& module_path,
76 : const FilePath& instrumented_path,
77 : const TraceFileList& trace_files,
78 : Flags flags)
79 : : playback_(module_path, instrumented_path, trace_files),
80 : flags_(flags),
81 : code_block_entry_events_(0),
82 E : order_generator_(NULL) {
83 E : }
84 :
85 E : Reorderer::~Reorderer() {
86 E : }
87 :
88 : bool Reorderer::Reorder(OrderGenerator* order_generator,
89 : Order* order,
90 : PEFile* pe_file,
91 E : ImageLayout* image) {
92 E : DCHECK(order_generator != NULL);
93 E : DCHECK(order != NULL);
94 :
95 E : DCHECK(order_generator_ == NULL);
96 E : order_generator_ = order_generator;
97 :
98 E : bool success = ReorderImpl(order, pe_file, image);
99 :
100 E : order_generator_ = NULL;
101 :
102 E : return success;
103 E : }
104 :
105 : bool Reorderer::ReorderImpl(Order* order,
106 : PEFile* pe_file,
107 E : ImageLayout* image) {
108 E : DCHECK(order != NULL);
109 E : DCHECK(order_generator_ != NULL);
110 :
111 E : if (!parser_.Init(this)) {
112 i : LOG(ERROR) << "Failed to initialize call trace parser.";
113 :
114 i : return false;
115 : }
116 :
117 E : if (!playback_.Init(pe_file, image, &parser_))
118 i : return false;
119 :
120 E : if (playback_.trace_files().size() > 0) {
121 E : LOG(INFO) << "Processing trace events.";
122 E : if (!parser_.Consume())
123 i : return false;
124 :
125 E : if (code_block_entry_events_ == 0) {
126 i : LOG(ERROR) << "No events originated from the given instrumented DLL.";
127 i : return false;
128 : }
129 : }
130 :
131 E : if (!CalculateReordering(order))
132 i : return false;
133 :
134 E : return true;
135 E : }
136 :
137 E : bool Reorderer::CalculateReordering(Order* order) {
138 E : DCHECK(order != NULL);
139 E : DCHECK(order_generator_ != NULL);
140 :
141 E : LOG(INFO) << "Calculating new order.";
142 : if (!order_generator_->CalculateReordering(*playback_.pe_file(),
143 : *playback_.image(),
144 : (flags_ & kFlagReorderCode) != 0,
145 : (flags_ & kFlagReorderData) != 0,
146 E : order))
147 i : return false;
148 :
149 : order->comment = base::StringPrintf("Generated using the %s.",
150 E : order_generator_->name().c_str());
151 :
152 E : return true;
153 E : }
154 :
155 E : void Reorderer::OnProcessEnded(base::Time time, DWORD process_id) {
156 : // Notify the order generator.
157 E : if (!order_generator_->OnProcessEnded(process_id, UniqueTime(time))) {
158 i : parser_.set_error_occurred(true);
159 i : return;
160 : }
161 :
162 : // Cleanup the local record for process_id.
163 E : ignore_result(matching_process_ids_.erase(process_id));
164 E : }
165 :
166 : // CallTraceEvents implementation.
167 : void Reorderer::OnFunctionEntry(base::Time time,
168 : DWORD process_id,
169 : DWORD thread_id,
170 E : const TraceEnterExitEventData* data) {
171 E : DCHECK(data != NULL);
172 :
173 : const BlockGraph::Block* block = playback_.FindFunctionBlock(process_id,
174 E : data->function);
175 :
176 E : if (block == NULL) {
177 i : parser_.set_error_occurred(true);
178 i : return;
179 : }
180 :
181 : // Get the actual time of the call. We ignore ticks_ago for now, as the
182 : // low-resolution and rounding can cause inaccurate relative timings. We
183 : // simply rely on the buffer ordering (via UniqueTime's internal counter)
184 : // to maintain relative ordering. For future reference, ticks_ago are in
185 : // milliseconds, according to MSDN.
186 E : UniqueTime entry_time(time);
187 :
188 : // If this is the first call of interest by a given process, send an
189 : // OnProcessStarted event.
190 E : if (matching_process_ids_.insert(process_id).second) {
191 E : if (!order_generator_->OnProcessStarted(process_id, entry_time)) {
192 i : parser_.set_error_occurred(true);
193 i : return;
194 : }
195 : }
196 :
197 E : ++code_block_entry_events_;
198 : if (!order_generator_->OnCodeBlockEntry(block,
199 : block->addr(),
200 : process_id,
201 : thread_id,
202 E : entry_time)) {
203 i : parser_.set_error_occurred(true);
204 : return;
205 : }
206 E : }
207 :
208 : void Reorderer::OnBatchFunctionEntry(base::Time time,
209 : DWORD process_id,
210 : DWORD thread_id,
211 E : const TraceBatchEnterData* data) {
212 : // Explode the batch event into individual function entry events.
213 E : TraceEnterExitEventData new_data = {};
214 E : for (size_t i = 0; i < data->num_calls; ++i) {
215 E : new_data.function = data->calls[i].function;
216 E : OnFunctionEntry(time, process_id, thread_id, &new_data);
217 : }
218 E : }
219 :
220 : bool Reorderer::Order::SerializeToJSON(const PEFile& pe,
221 : const FilePath &path,
222 E : bool pretty_print) const {
223 E : file_util::ScopedFILE file(file_util::OpenFile(path, "wb"));
224 E : if (file.get() == NULL)
225 i : return false;
226 E : core::JSONFileWriter json_file(file.get(), pretty_print);
227 E : return SerializeToJSON(pe, &json_file);
228 E : }
229 :
230 : bool Reorderer::Order::SerializeToJSON(const PEFile& pe,
231 E : core::JSONFileWriter* json_file) const {
232 E : DCHECK(json_file != NULL);
233 :
234 : // Open the main dictionary and the metadata dictionary.
235 : if (!json_file->OutputComment(comment.c_str()) ||
236 : !json_file->OpenDict() ||
237 E : !json_file->OutputKey("metadata")) {
238 i : return false;
239 : }
240 :
241 : // Output metadata.
242 E : PEFile::Signature orig_sig;
243 E : pe.GetSignature(&orig_sig);
244 E : pe::Metadata metadata;
245 : if (!metadata.Init(orig_sig) ||
246 E : !metadata.SaveToJSON(json_file)) {
247 i : return false;
248 : }
249 :
250 : // Open list of sections.
251 : if (!json_file->OutputKey("sections") ||
252 E : !json_file->OpenList()) {
253 i : return false;
254 : }
255 :
256 : // Output the individual block lists.
257 E : BlockListMap::const_iterator it = section_block_lists.begin();
258 E : for (; it != section_block_lists.end(); ++it) {
259 E : if (it->second.size() == 0)
260 i : continue;
261 :
262 : // Output a comment with the section name, and output the section
263 : // order info.
264 E : std::string comment = pe.GetSectionName(it->first);
265 E : comment = StringPrintf("section_name = \"%s\".", comment.c_str());
266 : if (!json_file->OutputComment(comment.c_str()) ||
267 E : !OutputBlockList(it->first, it->second, json_file)) {
268 i : return false;
269 : }
270 E : }
271 :
272 : // Close the list of sections and the outermost dictionary.
273 E : return json_file->CloseList() && json_file->CloseDict();
274 E : }
275 :
276 : bool Reorderer::Order::LoadFromJSON(const PEFile& pe,
277 : const ImageLayout& image,
278 E : const FilePath& path) {
279 E : std::string file_string;
280 E : if (!file_util::ReadFileToString(path, &file_string)) {
281 i : LOG(ERROR) << "Unable to read order file to string";
282 i : return false;
283 : }
284 :
285 E : scoped_ptr<Value> value(base::JSONReader::Read(file_string, false));
286 E : if (value.get() == NULL || value->GetType() != Value::TYPE_DICTIONARY) {
287 i : LOG(ERROR) << "Order file does not contain a valid JSON dictionary.";
288 : }
289 : const DictionaryValue* outer_dict =
290 E : reinterpret_cast<const DictionaryValue*>(value.get());
291 :
292 E : std::string metadata_key("metadata");
293 E : std::string sections_key("sections");
294 E : DictionaryValue* metadata_dict = NULL;
295 E : ListValue* order = NULL;
296 : if (!outer_dict->GetDictionary(metadata_key, &metadata_dict) ||
297 E : !outer_dict->GetList(sections_key, &order)) {
298 i : LOG(ERROR) << "Order dictionary must contain 'metadata' and 'sections'.";
299 i : return false;
300 : }
301 :
302 : // Load the metadata from the order file, and ensure it is consistent with
303 : // the signature of the module the ordering is being applied to.
304 E : pe::Metadata metadata;
305 E : PEFile::Signature pe_sig;
306 E : pe.GetSignature(&pe_sig);
307 : if (!metadata.LoadFromJSON(*metadata_dict) ||
308 E : !metadata.IsConsistent(pe_sig))
309 i : return false;
310 :
311 E : section_block_lists.clear();
312 :
313 : // Iterate through the elements of the list. They should each be dictionaries
314 : // representing a single section.
315 E : ListValue::iterator section_it = order->begin();
316 E : for (; section_it != order->end(); ++section_it) {
317 : if ((*section_it) == NULL ||
318 E : (*section_it)->GetType() != Value::TYPE_DICTIONARY) {
319 i : LOG(ERROR) << "Order file list does not contain dictionaries.";
320 i : return false;
321 : }
322 : const DictionaryValue* section =
323 E : reinterpret_cast<const DictionaryValue*>(*section_it);
324 :
325 E : std::string section_id_key("section_id");
326 E : std::string blocks_key("blocks");
327 E : int section_id_int = 0;
328 E : ListValue* blocks = NULL;
329 : if (!section->GetInteger(section_id_key, §ion_id_int) ||
330 E : !section->GetList(blocks_key, &blocks)) {
331 i : LOG(ERROR) << "Section dictionary must contain integer 'section_id' and "
332 : << "list 'blocks'.";
333 i : return false;
334 : }
335 E : size_t section_id = section_id_int;
336 E : DCHECK(blocks != NULL);
337 :
338 E : if (section_block_lists.find(section_id) != section_block_lists.end()) {
339 i : LOG(ERROR) << "Section " << section_id << " redefined.";
340 i : return false;
341 : }
342 :
343 E : if (blocks->GetSize() == 0)
344 i : continue;
345 :
346 E : BlockList& block_list = section_block_lists[section_id];
347 E : ListValue::iterator block_it = blocks->begin();
348 E : for (; block_it != blocks->end(); ++block_it) {
349 E : int address = 0;
350 E : if ((*block_it) == NULL || !(*block_it)->GetAsInteger(&address)) {
351 i : LOG(ERROR) << "'blocks' must be a list of integers.";
352 i : return false;
353 : }
354 E : RelativeAddress rva(address);
355 :
356 E : const BlockGraph::Block* block = image.blocks.GetBlockByAddress(rva);
357 E : if (block == NULL) {
358 i : LOG(ERROR) << "Block address not found in decomposed image: "
359 : << address;
360 i : return false;
361 : }
362 E : if (block->section() != section_id) {
363 i : LOG(ERROR) << "Block at address " << address << " belongs to section "
364 : << block->section() << " and not section " << section_id;
365 i : return false;
366 : }
367 E : block_list.push_back(block);
368 E : }
369 E : }
370 :
371 E : return true;
372 E : }
373 :
374 : bool Reorderer::Order::GetOriginalModulePath(const FilePath& path,
375 E : FilePath* module) {
376 E : std::string file_string;
377 E : if (!file_util::ReadFileToString(path, &file_string)) {
378 E : LOG(ERROR) << "Unable to read order file to string.";
379 E : return false;
380 : }
381 :
382 E : scoped_ptr<Value> value(base::JSONReader::Read(file_string, false));
383 E : if (value.get() == NULL || value->GetType() != Value::TYPE_DICTIONARY) {
384 i : LOG(ERROR) << "Order file does not contain a valid JSON dictionary.";
385 i : return false;
386 : }
387 : const DictionaryValue* outer_dict =
388 E : reinterpret_cast<const DictionaryValue*>(value.get());
389 :
390 E : std::string metadata_key("metadata");
391 E : DictionaryValue* metadata_dict = NULL;
392 E : if (!outer_dict->GetDictionary(metadata_key, &metadata_dict)) {
393 i : LOG(ERROR) << "Order dictionary must contain 'metadata'.";
394 i : return false;
395 : }
396 :
397 E : pe::Metadata metadata;
398 E : if (!metadata.LoadFromJSON(*metadata_dict))
399 i : return false;
400 :
401 E : *module = FilePath(metadata.module_signature().path);
402 :
403 E : return true;
404 E : }
405 :
406 : Reorderer::UniqueTime::UniqueTime()
407 : : time_(),
408 : id_(0) {
409 : }
410 :
411 : Reorderer::UniqueTime::UniqueTime(const UniqueTime& other)
412 : : time_(other.time_),
413 E : id_(other.id_) {
414 E : }
415 :
416 : Reorderer::UniqueTime::UniqueTime(const base::Time& time)
417 : : time_(time),
418 E : id_(next_id_++) {
419 E : }
420 :
421 E : Reorderer::UniqueTime& Reorderer::UniqueTime::operator=(const UniqueTime& rhs) {
422 E : time_ = rhs.time_;
423 E : id_ = rhs.id_;
424 E : return *this;
425 E : }
426 :
427 E : int Reorderer::UniqueTime::compare(const UniqueTime& rhs) const {
428 E : if (time_ < rhs.time_)
429 i : return -1;
430 E : if (time_ > rhs.time_)
431 i : return 1;
432 E : if (id_ < rhs.id_)
433 E : return -1;
434 E : if (id_ > rhs.id_)
435 E : return 1;
436 E : return 0;
437 E : }
438 :
439 : size_t Reorderer::UniqueTime::next_id_ = 0;
440 :
441 : } // namespace reorder
|