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 : #include "syzygy/simulate/page_fault_simulation.h"
16 :
17 : #include "base/values.h"
18 : #include "base/files/scoped_temp_dir.h"
19 : #include "base/json/json_reader.h"
20 : #include "syzygy/common/syzygy_version.h"
21 : #include "syzygy/core/random_number_generator.h"
22 : #include "syzygy/core/unittest_util.h"
23 : #include "syzygy/pdb/omap.h"
24 : #include "syzygy/pe/unittest_util.h"
25 :
26 : namespace simulate {
27 :
28 : namespace {
29 :
30 : using block_graph::BlockGraph;
31 :
32 : class PageFaultSimulatorTest : public testing::PELibUnitTest {
33 : public:
34 : typedef PageFaultSimulation::PageSet PageSet;
35 :
36 : struct MockBlockInfo {
37 : uint32 start;
38 : size_t size;
39 : BlockGraph::Block* block;
40 :
41 E : MockBlockInfo(uint32 start_, size_t size_, BlockGraph* block_graph)
42 : : start(start_), size(size_), block(NULL) {
43 E : DCHECK(block_graph != NULL);
44 E : block = block_graph->AddBlock(BlockGraph::CODE_BLOCK, size_, "block");
45 E : block->set_addr(core::RelativeAddress(start));
46 E : block->set_size(size);
47 E : }
48 :
49 E : MockBlockInfo()
50 : : start(0U), size(0U), block(NULL) {
51 E : }
52 : };
53 : typedef std::vector<MockBlockInfo> MockBlockInfoList;
54 :
55 E : PageFaultSimulatorTest() : random_(123) {
56 E : }
57 :
58 E : void SetUp() {
59 E : ASSERT_NO_FATAL_FAILURE(CreateTemporaryDir(&temp_dir_));
60 :
61 E : simulation_.reset(new PageFaultSimulation());
62 E : ASSERT_TRUE(simulation_ != NULL);
63 :
64 E : blocks_[0] = MockBlockInfo(0x0, 0x50, &block_graph_);
65 E : blocks_[1] = MockBlockInfo(0x0, 0x100, &block_graph_);
66 E : blocks_[2] = MockBlockInfo(0x350, 0x100, &block_graph_);
67 E : blocks_[3] = MockBlockInfo(0x1000, 0x50, &block_graph_);
68 E : }
69 :
70 : // Checks if the given address is on one of our mock blocks.
71 : // @param addr The address to check.
72 : // @returns true if a block that contains the given address exists,
73 : // false on otherwise.
74 E : bool AddressInBlocks(size_t addr) {
75 E : for (size_t i = 0; i < arraysize(blocks_); i++) {
76 : if (blocks_[i].start <= addr &&
77 E : blocks_[i].start + blocks_[i].size > addr)
78 E : return true;
79 E : }
80 :
81 E : return false;
82 E : }
83 :
84 : // Check whether all the pages loaded in simulator correspond to one of our
85 : // blocks, given the current page_size and pages_per_code_fault parameters.
86 : // @returns true if all the pages are contained in our mock blocks,
87 : // false on otherwise.
88 E : bool CorrectPageFaults() {
89 E : PageSet::const_iterator iter = simulation_->pages().begin();
90 E : for (; iter != simulation_->pages().end(); iter++) {
91 E : bool block_found = false;
92 :
93 : // If this address was loaded, then some address between this one and
94 : // the one pages_per_code_fault pages before should have triggered
95 : // a page fault.
96 E : for (uint32 j = 0;
97 : j <= *iter && j < simulation_->pages_per_code_fault();
98 E : j++) {
99 E : if (AddressInBlocks((*iter - j) * simulation_->page_size())) {
100 E : block_found = true;
101 E : break;
102 : }
103 E : }
104 :
105 E : if (!block_found)
106 i : return false;
107 E : }
108 :
109 E : return true;
110 E : }
111 :
112 : // Gives a random number in the range [from, to), or 0 if the range is empty.
113 : // @param from The lowest possible return value.
114 : // @param to The number after the highest possible return value.
115 E : uint32 Random(uint32 from, uint32 to) {
116 E : int size = to - from;
117 E : if (from > to) {
118 : // This should never be reached.
119 i : ADD_FAILURE();
120 i : return 0;
121 : }
122 :
123 E : if (size == 0)
124 E : return 0;
125 :
126 E : return random_(size) + from;
127 E : }
128 :
129 : // Add 5 random blocks that won't generate any page fault.
130 : // @param mock_block_list The MockBlockInfoList where the blocks will
131 : // be appended. This list should already generate page faults covering
132 : // the range [start, start + size).
133 : // @param start The start of the output sequence.
134 : // @param size The size of the output sequence.
135 : void AddRandomBlocks(
136 E : MockBlockInfoList &mock_block_list, uint32 start, size_t size) {
137 E : for (uint32 i = 0; i < 5; i++) {
138 E : uint32 block_start = Random(start, start + size);
139 E : size_t block_size = Random(1, start + size - block_start);
140 : mock_block_list.push_back(
141 E : MockBlockInfo(block_start, block_size, &block_graph_));
142 E : }
143 E : }
144 :
145 : // Generate a random MockBlockInfoList that should make PageFaultSimulation
146 : // output the sequence [start, start + size).
147 : // @param start The start of the output sequence.
148 : // @param size The size of the output sequence.
149 : // @param avg_length The average length of each page fault generated by the
150 : // resulting input data.
151 : MockBlockInfoList GeneratePartRandomInput(uint32 start,
152 : size_t size,
153 E : size_t avg_length) {
154 E : MockBlockInfoList input;
155 :
156 E : if (size == 0)
157 i : return input;
158 :
159 : uint32 page_fault_size = simulation_->pages_per_code_fault() *
160 E : simulation_->page_size();
161 :
162 E : if (size < page_fault_size) {
163 : // If the size of this part is smaller than the number of bytes loaded
164 : // into memory in each page fault, then the given output was impossible,
165 : // so this should never be reached.
166 i : ADD_FAILURE();
167 i : return input;
168 : }
169 :
170 E : int fault = start + size - page_fault_size;
171 E : uint32 current_size = 0;
172 :
173 : // The block page_fault_size bytes from the end of each sequence should
174 : // always be loaded.
175 : input.push_back(
176 E : MockBlockInfo(fault, Random(1, page_fault_size), &block_graph_));
177 :
178 E : fault--;
179 E : for (; fault >= static_cast<int>(start); fault--) {
180 i : current_size++;
181 :
182 : // Randomly choose with 1 / avg_length probability whether to add blocks
183 : // that would raise a page fault in the current byte.
184 i : if (random_(avg_length) == 0) {
185 : input.push_back(MockBlockInfo(fault,
186 : Random(page_fault_size * (current_size / page_fault_size) + 1,
187 : start + size - fault),
188 i : &block_graph_));
189 :
190 i : current_size = 0;
191 : }
192 i : }
193 : // Add the bytes that weren't pagefaulted in a single big block.
194 E : if (current_size > 0)
195 : input.push_back(MockBlockInfo(start,
196 : Random(page_fault_size * (current_size / page_fault_size) + 1,
197 : size),
198 i : &block_graph_));
199 :
200 : // Add several random blocks at the end of the input that won't
201 : // have any effect on the output.
202 E : AddRandomBlocks(input, start, size);
203 E : return input;
204 E : }
205 :
206 : // Generate a random MockBlockInfoList that outputs output.
207 : // This function separates output into blocks of contiguous sequences,
208 : // creates a block that should raise a pagefault in the position
209 : // size - cluster_size, and for every element before that creates a
210 : // block that should raise another one with 1 / avg_length probability.
211 : // It also adds a few bogus blocks that shouldn't change the output, and
212 : // shuffles the list of inputs for contiguous sequences on the output.
213 : // @param output The output that should come from the returned input.
214 : // @param avg_length The average length of each page fault generated by the
215 : // resulting input data.
216 E : MockBlockInfoList GenerateRandomInput(PageSet output, size_t avg_length) {
217 : // A list with different "groups" of mock blocks.
218 E : std::vector<MockBlockInfoList> input_list;
219 E : uint32 last = 0;
220 E : uint32 size = 0;
221 :
222 : // Search through the output for groups of adjacent numbers, and add a
223 : // MockBlockInfoList that would generate these numbers to input_list.
224 E : PageSet::iterator iter = output.begin();
225 E : for (; iter != output.end(); iter++) {
226 E : if (last != 0 && *iter - last > 1) {
227 : input_list.push_back(
228 i : GeneratePartRandomInput(last - size + 1, size, avg_length));
229 i : size = 0;
230 : }
231 :
232 E : size++;
233 E : last = *iter;
234 E : }
235 : input_list.push_back(
236 E : GeneratePartRandomInput(last - size + 1, size, avg_length));
237 :
238 : // Shuffle the groups of adjacent numbers.
239 E : std::random_shuffle(input_list.begin(), input_list.end(), random_);
240 :
241 : // Append all the elements of each element of input_list to a single
242 : // MockBlockInfoList and return it.
243 E : MockBlockInfoList input;
244 E : for (size_t i = 0; i < input_list.size(); i++)
245 E : input.insert(input.end(), input_list[i].begin(), input_list[i].end());
246 :
247 E : return input;
248 E : }
249 :
250 : protected:
251 : scoped_ptr<PageFaultSimulation> simulation_;
252 :
253 : base::FilePath temp_dir_;
254 : MockBlockInfo blocks_[4];
255 : core::RandomNumberGenerator random_;
256 : const base::Time time_;
257 :
258 : BlockGraph block_graph_;
259 : };
260 :
261 : } // namespace
262 :
263 E : TEST_F(PageFaultSimulatorTest, RandomInput) {
264 : static const int output1[] = {1, 2, 3, 4};
265 : static const int output2[] = {1, 2, 3, 4, 5, 6, 12, 13, 14, 15, 16, 20, 21,
266 : 22, 23, 100, 101, 102, 103, 104, 105};
267 : static const int output3[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
268 : 15, 16, 17, 18, 19, 20, 21, 22, 23};
269 : static const int output4[] = {1, 2, 3, 4, 100, 101, 102, 103, 200, 201, 202,
270 : 203};
271 :
272 : const PageSet outputs[] = {
273 E : PageSet(output1, output1 + arraysize(output1)),
274 E : PageSet(output2, output2 + arraysize(output2)),
275 E : PageSet(output3, output3 + arraysize(output3)),
276 : PageSet(output4, output4 + arraysize(output4))
277 E : };
278 :
279 E : for (uint32 i = 0; i < 1000; i++) {
280 : // Make simulation_ a new instance of PageFaultSimulator.
281 E : simulation_.reset(new PageFaultSimulation());
282 E : ASSERT_TRUE(simulation_ != NULL);
283 :
284 E : simulation_->OnProcessStarted(time_, 1);
285 E : simulation_->set_pages_per_code_fault(4);
286 :
287 : // Choose a random output, create an input with it,
288 : // and simulate that input.
289 E : PageSet output = outputs[random_(arraysize(outputs))];
290 : MockBlockInfoList input =
291 E : GenerateRandomInput(output, random_(output.size()) + 1);
292 :
293 E : for (size_t i = 0; i < input.size(); i++)
294 E : simulation_->OnFunctionEntry(time_, input[i].block);
295 :
296 E : std::stringstream input_string;
297 E : input_string << '{';
298 E : for (size_t i = 0; i < input.size(); i++) {
299 E : input_string << '(' << input[i].start << ", ";
300 E : input_string << input[i].size << "), ";
301 E : }
302 E : input_string << '}';
303 :
304 E : ASSERT_EQ(simulation_->pages(), output) <<
305 E : "Failed with input " << input_string.str();
306 E : }
307 E : }
308 :
309 E : TEST_F(PageFaultSimulatorTest, ExactPageFaults) {
310 E : simulation_->OnProcessStarted(time_, 1);
311 E : simulation_->set_page_size(1);
312 E : simulation_->set_pages_per_code_fault(4);
313 :
314 : MockBlockInfo blocks[] = {
315 E : MockBlockInfo(0, 3, &block_graph_),
316 E : MockBlockInfo(2, 2, &block_graph_),
317 : MockBlockInfo(5, 5, &block_graph_)
318 E : };
319 :
320 E : for (uint32 i = 0; i < arraysize(blocks); i++) {
321 E : simulation_->OnFunctionEntry(time_, blocks[i].block);
322 E : }
323 :
324 E : PageSet::key_type expected_pages[] = {0, 1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12};
325 E : EXPECT_EQ(simulation_->fault_count(), 3);
326 : EXPECT_EQ(simulation_->pages(), PageSet(expected_pages, expected_pages +
327 E : arraysize(expected_pages)));
328 E : }
329 :
330 E : TEST_F(PageFaultSimulatorTest, CorrectPageFaults) {
331 E : simulation_->OnProcessStarted(time_, 1);
332 :
333 E : for (int i = 0; i < arraysize(blocks_); i++) {
334 E : simulation_->OnFunctionEntry(time_, blocks_[i].block);
335 E : }
336 :
337 E : EXPECT_EQ(simulation_->fault_count(), 74);
338 E : EXPECT_TRUE(CorrectPageFaults());
339 E : }
340 :
341 E : TEST_F(PageFaultSimulatorTest, CorrectPageFaultsWithBigPages) {
342 E : simulation_->OnProcessStarted(time_, 1);
343 E : simulation_->set_page_size(0x8000);
344 :
345 E : for (int i = 0; i < arraysize(blocks_); i++) {
346 E : simulation_->OnFunctionEntry(time_, blocks_[i].block);
347 E : }
348 :
349 E : EXPECT_EQ(simulation_->fault_count(), 1);
350 E : EXPECT_TRUE(CorrectPageFaults());
351 E : }
352 :
353 E : TEST_F(PageFaultSimulatorTest, CorrectPageFaultsWithFewPagesPerCodeFault) {
354 E : simulation_->OnProcessStarted(time_, 1);
355 E : simulation_->set_pages_per_code_fault(3);
356 :
357 E : for (int i = 0; i < arraysize(blocks_); i++) {
358 E : simulation_->OnFunctionEntry(time_, blocks_[i].block);
359 E : }
360 :
361 E : EXPECT_EQ(simulation_->fault_count(), 199);
362 E : EXPECT_TRUE(CorrectPageFaults());
363 E : }
364 :
365 E : TEST_F(PageFaultSimulatorTest, JSONSucceeds) {
366 E : simulation_->OnProcessStarted(time_, 1);
367 :
368 E : for (int i = 0; i < arraysize(blocks_); i++) {
369 E : simulation_->OnFunctionEntry(time_, blocks_[i].block);
370 E : }
371 :
372 : // Output JSON data to a file.
373 E : base::FilePath path;
374 E : file_util::ScopedFILE temp_file;
375 : temp_file.reset(file_util::CreateAndOpenTemporaryFileInDir(
376 E : temp_dir_, &path));
377 :
378 E : ASSERT_TRUE(temp_file.get() != NULL);
379 E : ASSERT_TRUE(simulation_->SerializeToJSON(temp_file.get(), false));
380 E : temp_file.reset();
381 :
382 : // Read the JSON file we just wrote.
383 E : std::string file_string;
384 E : ASSERT_TRUE(file_util::ReadFileToString(path, &file_string));
385 :
386 E : scoped_ptr<Value> value(base::JSONReader::Read(file_string));
387 E : ASSERT_TRUE(value.get() != NULL);
388 E : ASSERT_TRUE(value->IsType(Value::TYPE_DICTIONARY));
389 :
390 : const DictionaryValue* outer_dict =
391 E : static_cast<const DictionaryValue*>(value.get());
392 :
393 : static const char page_size_key[] = "page_size";
394 : static const char pages_per_code_fault_key[] = "pages_per_code_fault";
395 : static const char fault_count_key[] = "fault_count";
396 : static const char loaded_pages_key[] = "loaded_pages";
397 :
398 E : int page_size = 0, pages_per_code_fault = 0, fault_count = 0;
399 E : const base::ListValue* loaded_pages = NULL;
400 :
401 E : outer_dict->GetInteger(page_size_key, &page_size);
402 E : outer_dict->GetInteger(pages_per_code_fault_key, &pages_per_code_fault);
403 E : outer_dict->GetInteger(fault_count_key, &fault_count);
404 E : outer_dict->GetList(loaded_pages_key, &loaded_pages);
405 :
406 E : EXPECT_EQ(page_size, 1);
407 E : EXPECT_EQ(pages_per_code_fault, 8);
408 E : EXPECT_EQ(fault_count, 74);
409 :
410 E : ASSERT_TRUE(loaded_pages != NULL);
411 :
412 : // Compare it to our own data.
413 E : PageSet expected_pages = simulation_->pages();
414 E : ASSERT_EQ(expected_pages.size(), loaded_pages->GetSize());
415 :
416 E : PageSet::iterator expected_pages_iter = expected_pages.begin();
417 E : base::ListValue::const_iterator loaded_pages_iter = loaded_pages->begin();
418 :
419 E : for (; expected_pages_iter != expected_pages.end();
420 E : expected_pages_iter++, loaded_pages_iter++) {
421 E : int page = 0;
422 E : ASSERT_EQ((*loaded_pages_iter)->GetType(), Value::TYPE_INTEGER);
423 E : ASSERT_TRUE((*loaded_pages_iter)->GetAsInteger(&page));
424 :
425 E : EXPECT_EQ(*expected_pages_iter, implicit_cast<uint32>(page));
426 E : }
427 E : }
428 :
429 : } // namespace simulate
|