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