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