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 : // Parses a module and ETW trace files, generating an ordering of the
16 : // blocks in the decomposed image.
17 :
18 : #include "syzygy/reorder/reorder_app.h"
19 :
20 : #include <objbase.h>
21 :
22 : #include "base/strings/string_number_conversions.h"
23 : #include "base/strings/string_split.h"
24 : #include "base/strings/stringprintf.h"
25 : #include "syzygy/grinder/basic_block_util.h"
26 : #include "syzygy/grinder/indexed_frequency_data_serializer.h"
27 : #include "syzygy/pe/find.h"
28 : #include "syzygy/reorder/basic_block_optimizer.h"
29 : #include "syzygy/reorder/dead_code_finder.h"
30 : #include "syzygy/reorder/linear_order_generator.h"
31 : #include "syzygy/reorder/random_order_generator.h"
32 :
33 : namespace reorder {
34 :
35 : namespace {
36 :
37 : using grinder::basic_block_util::IndexedFrequencyMap;
38 : using grinder::basic_block_util::IndexedFrequencyInformation;
39 : using grinder::basic_block_util::ModuleIndexedFrequencyMap;
40 : using grinder::basic_block_util::LoadBasicBlockRanges;
41 : using grinder::basic_block_util::FindIndexedFrequencyInfo;
42 : using grinder::basic_block_util::RelativeAddressRangeVector;
43 : using grinder::IndexedFrequencyDataSerializer;
44 :
45 : static const char kUsageFormatStr[] =
46 : "Usage: %ls [options] [log files ...]\n"
47 : " Required Options:\n"
48 : " --instrumented-image=<path> the path to the instrumented image file.\n"
49 : " --output-file=<path> the output file.\n"
50 : " Optional Options:\n"
51 : " --input-image=<path> the input image file to reorder. If this is not\n"
52 : " specified it will be inferred from the instrumented image's\n"
53 : " metadata.\n"
54 : " --basic-block-entry-counts=PATH the path to the JSON file containing\n"
55 : " the summary basic-block entry counts for the image. If this is\n"
56 : " given then the input image is also required.\n"
57 : " --seed=INT generates a random ordering; don't specify ETW log files.\n"
58 : " --list-dead-code instead of an ordering, output the set of functions\n"
59 : " not visited during the trace.\n"
60 : " --pretty-print enables pretty printing of the JSON output file.\n"
61 : " --reorderer-flags=<comma separated reorderer flags>\n"
62 : " Reorderer Flags:\n"
63 : " no-code: Do not reorder code sections.\n"
64 : " no-data: Do not reorder data sections.\n"
65 : " Deprecated Options:\n"
66 : " --instrumented-dll=<path> aliases to --instrumented-image.\n"
67 : " --input-dll=<path> aliases to --input-image.\n";
68 :
69 : // Parses reorderer flags. Returns true on success, false otherwise. On
70 : // failure, also outputs Usage with an error message.
71 E : bool ParseFlags(const std::string& flags_str, Reorderer::Flags* flags) {
72 E : DCHECK(flags != NULL);
73 :
74 : // Set the default flags value.
75 : Reorderer::Flags out_flags =
76 E : Reorderer::kFlagReorderData | Reorderer::kFlagReorderCode;
77 :
78 : // If there is a string to process then extract its flags.
79 E : if (!flags_str.empty()) {
80 : typedef std::vector<std::string> StringVector;
81 E : StringVector text_flags = base::SplitString(
82 : flags_str, ",", base::TRIM_WHITESPACE, base::SPLIT_WANT_ALL);
83 E : StringVector::const_iterator flag_iter = text_flags.begin();
84 E : for (; flag_iter != text_flags.end(); ++flag_iter) {
85 E : if (*flag_iter == "no-data") {
86 E : out_flags &= ~Reorderer::kFlagReorderData;
87 E : } else if (*flag_iter == "no-code") {
88 E : out_flags &= ~Reorderer::kFlagReorderCode;
89 E : } else if (!flag_iter->empty()) {
90 E : LOG(ERROR) << "Unknown reorderer flag: " << *flag_iter << ".";
91 E : return false;
92 : }
93 E : }
94 E : }
95 :
96 : // Set the return value.
97 E : *flags = out_flags;
98 :
99 E : return true;
100 E : }
101 :
102 : } // namespace
103 :
104 : const char ReorderApp::kInstrumentedImage[] = "instrumented-image";
105 : const char ReorderApp::kOutputFile[] = "output-file";
106 : const char ReorderApp::kInputImage[] = "input-image";
107 : const char ReorderApp::kBasicBlockEntryCounts[] = "basic-block-entry-counts";
108 : const char ReorderApp::kSeed[] = "seed";
109 : const char ReorderApp::kListDeadCode[] = "list-dead-code";
110 : const char ReorderApp::kPrettyPrint[] = "pretty-print";
111 : const char ReorderApp::kReordererFlags[] = "reorderer-flags";
112 : const char ReorderApp::kInstrumentedDll[] = "instrumented-dll";
113 : const char ReorderApp::kInputDll[] = "input-dll";
114 :
115 : ReorderApp::ReorderApp()
116 E : : AppImplBase("Reorder"),
117 E : mode_(kInvalidMode),
118 E : seed_(0),
119 E : pretty_print_(false),
120 E : flags_(0) {
121 E : }
122 :
123 E : bool ReorderApp::ParseCommandLine(const base::CommandLine* command_line) {
124 E : DCHECK(command_line != NULL);
125 E : DCHECK_EQ(kInvalidMode, mode_);
126 :
127 : // Parse the instrumented image path.
128 : if (!GetDeprecatedSwitch(command_line, kInstrumentedImage, kInstrumentedDll,
129 : &base::CommandLine::GetSwitchValuePath,
130 E : &instrumented_image_path_) ||
131 : instrumented_image_path_.empty()) {
132 E : return Usage(command_line, "Invalid or missing instrumented image path.");
133 : }
134 :
135 : // Parse the output file path.
136 E : output_file_path_ = command_line->GetSwitchValuePath(kOutputFile);
137 E : if (output_file_path_.empty()) {
138 i : return Usage(command_line, "Invalid or missing output file path.");
139 : }
140 :
141 : // Parse the (optional) input image path.
142 E : if (!GetDeprecatedSwitch(command_line, kInputImage, kInputDll,
143 : &base::CommandLine::GetSwitchValuePath,
144 : &input_image_path_)) {
145 i : return Usage(command_line, "Invalid input image path.");
146 : }
147 :
148 E : bb_entry_count_file_path_ =
149 : command_line->GetSwitchValuePath(kBasicBlockEntryCounts);
150 :
151 : // Parse the reorderer flags.
152 E : std::string flags_str(command_line->GetSwitchValueASCII(kReordererFlags));
153 E : if (!ParseFlags(flags_str, &flags_)) {
154 E : return Usage(command_line, "Invalid reorderer flags");
155 : }
156 :
157 : // Parse the pretty-print switch.
158 E : pretty_print_ = command_line->HasSwitch(kPrettyPrint);
159 :
160 : // Make all of the input paths absolute.
161 E : input_image_path_ = AbsolutePath(input_image_path_);
162 E : instrumented_image_path_ = AbsolutePath(instrumented_image_path_);
163 E : output_file_path_ = AbsolutePath(output_file_path_);
164 E : bb_entry_count_file_path_ = AbsolutePath(bb_entry_count_file_path_);
165 :
166 : // Capture the (possibly empty) set of trace files to read.
167 E : for (size_t i = 0; i < command_line->GetArgs().size(); ++i) {
168 E : const base::FilePath pattern(command_line->GetArgs()[i]);
169 E : if (!AppendMatchingPaths(pattern, &trace_file_paths_)) {
170 i : LOG(ERROR) << "Found no files matching '" << pattern.value() << "'.";
171 i : return Usage(command_line, "");
172 : }
173 E : }
174 :
175 : // Check if we are in random order mode. Look for and parse --seed.
176 E : if (command_line->HasSwitch(kSeed)) {
177 E : if (!trace_file_paths_.empty()) {
178 E : return Usage(command_line,
179 : "Trace files are not accepted in random order mode.");
180 : }
181 E : std::string seed_str(command_line->GetSwitchValueASCII(kSeed));
182 E : int tmp_seed = 0;
183 E : if (seed_str.empty() || !base::StringToInt(seed_str, &tmp_seed)) {
184 E : return Usage(command_line, "Invalid seed value.");
185 : }
186 E : seed_ = tmp_seed;
187 E : mode_ = kRandomOrderMode;
188 E : }
189 :
190 : // Parse the list-dead-code switch.
191 E : if (command_line->HasSwitch(kListDeadCode)) {
192 E : if (mode_ != kInvalidMode) {
193 E : LOG(ERROR) << "--" << kListDeadCode << " and --" << kSeed << "=N are "
194 : << "mutually exclusive.";
195 E : return false;
196 : }
197 E : mode_ = kDeadCodeFinderMode;
198 : }
199 :
200 : // If we haven't found anything to over-ride the default mode (linear order),
201 : // then the default it is.
202 E : if (mode_ == kInvalidMode)
203 E : mode_ = kLinearOrderMode;
204 :
205 : // We do not accept trace file paths in random order mode.
206 E : if (mode_ == kRandomOrderMode && !trace_file_paths_.empty()) {
207 i : return Usage(command_line,
208 : "Trace files are not accepted in random order mode.");
209 : }
210 :
211 : // We only accept a basic-block entry count file in linear order mode, and
212 : // we require the input image path when we do so.
213 E : if (!bb_entry_count_file_path_.empty()) {
214 E : if (mode_ != kLinearOrderMode) {
215 i : return Usage(command_line,
216 : "A basic-block entry counts file is only accepted in linear "
217 : "order mode.");
218 : }
219 E : if (input_image_path_.empty()) {
220 i : return Usage(command_line,
221 : "The input image is required for basic-block level "
222 : "optimization.");
223 : }
224 : }
225 :
226 : // If we get here then the command-line switches were valid.
227 E : return true;
228 E : }
229 :
230 E : bool ReorderApp::SetUp() {
231 E : switch (mode_) {
232 : case kLinearOrderMode:
233 E : order_generator_.reset(new LinearOrderGenerator());
234 E : return true;
235 :
236 : case kRandomOrderMode:
237 E : order_generator_.reset(new RandomOrderGenerator(seed_));
238 E : return true;
239 :
240 : case kDeadCodeFinderMode:
241 E : order_generator_.reset(new DeadCodeFinder());
242 E : return true;
243 : }
244 :
245 i : NOTREACHED();
246 i : return false;
247 E : }
248 :
249 E : int ReorderApp::Run() {
250 E : pe::PEFile input_image;
251 E : block_graph::BlockGraph block_graph;
252 E : pe::ImageLayout image_layout(&block_graph);
253 E : Reorderer::Order order;
254 E : Reorderer reorderer(input_image_path_,
255 : instrumented_image_path_,
256 : trace_file_paths_,
257 : flags_);
258 :
259 : // Generate a block-level ordering.
260 E : if (!reorderer.Reorder(order_generator_.get(),
261 : &order,
262 : &input_image,
263 : &image_layout)) {
264 i : LOG(ERROR) << "Reorder failed.";
265 i : return 1;
266 : }
267 :
268 : // Basic-block optimize the resulting order if there is an entry count file.
269 E : if (mode_ == kLinearOrderMode && !bb_entry_count_file_path_.empty()) {
270 E : pe::PEFile::Signature signature;
271 E : input_image.GetSignature(&signature);
272 E : if (!OptimizeBasicBlocks(signature, image_layout, &order)) {
273 i : LOG(ERROR) << "Basic-block optimization failed.";
274 i : return 1;
275 : }
276 E : }
277 :
278 : // Serialize the order to JSON.
279 E : if (!order.SerializeToJSON(input_image, output_file_path_, pretty_print_)) {
280 i : LOG(ERROR) << "Unable to output order.";
281 i : return 1;
282 : }
283 :
284 : // We were successful.
285 E : return 0;
286 E : }
287 :
288 : bool ReorderApp::Usage(const base::CommandLine* cmd_line,
289 E : const base::StringPiece& message) const {
290 E : if (!message.empty()) {
291 E : ::fwrite(message.data(), 1, message.length(), err());
292 E : ::fprintf(err(), "\n\n");
293 : }
294 :
295 E : ::fprintf(err(),
296 : kUsageFormatStr,
297 : cmd_line->GetProgram().BaseName().value().c_str());
298 :
299 E : return false;
300 E : }
301 :
302 : bool ReorderApp::OptimizeBasicBlocks(const pe::PEFile::Signature& signature,
303 : const pe::ImageLayout& image_layout,
304 E : Reorderer::Order* order) {
305 E : DCHECK(order != NULL);
306 :
307 E : LOG(INFO) << "Performing basic block ordering.";
308 :
309 : // Load the basic-block entry count data.
310 E : ModuleIndexedFrequencyMap module_entry_count_map;
311 E : IndexedFrequencyDataSerializer serializer;
312 E : if (!serializer.LoadFromJson(bb_entry_count_file_path_,
313 : &module_entry_count_map)) {
314 i : LOG(ERROR) << "Failed to load basic-block entry count data";
315 i : return false;
316 : }
317 :
318 E : const IndexedFrequencyInformation* entry_counts = NULL;
319 E : if (!FindIndexedFrequencyInfo(signature,
320 : module_entry_count_map,
321 : &entry_counts)) {
322 i : LOG(ERROR) << "Failed to find entry count vector for '"
323 : << signature.path << "'.";
324 i : return false;
325 : }
326 :
327 : // Optimize the ordering at the basic-block level.
328 E : BasicBlockOptimizer optimizer;
329 E : if (!optimizer.Optimize(image_layout, *entry_counts, order)) {
330 i : LOG(ERROR) << "Failed to optimize basic-block ordering.";
331 i : return false;
332 : }
333 :
334 E : return true;
335 E : }
336 :
337 : } // namespace reorder
|