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