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/heat_map_simulation.h"
16 :
17 : #include <map>
18 : #include <vector>
19 :
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::Time;
31 : using block_graph::BlockGraph;
32 :
33 : // Compare two pairs of memory slice ids and memory slices.
34 : // @tparam CompareFunctions true to compare each separate function in the
35 : // memory slices, false otherwise.
36 : template <bool CompareFunctions>
37 : struct CompareMemorySlices {
38 : typedef std::pair<HeatMapSimulation::MemorySliceId,
39 : HeatMapSimulation::TimeSlice::MemorySlice> Slice;
40 :
41 E : bool operator()(const Slice &x, const Slice &y) {
42 E : if (x.first != y.first || x.second.total != y.second.total)
43 i : return false;
44 :
45 E : if (CompareFunctions && x.second.functions != y.second.functions)
46 i : return false;
47 :
48 E : return true;
49 E : }
50 : };
51 :
52 : class HeatMapSimulationTest : public testing::PELibUnitTest {
53 : public:
54 : typedef HeatMapSimulation::TimeSlice TimeSlice;
55 :
56 : struct MockBlockInfo {
57 : time_t time;
58 : uint32_t start;
59 : size_t size;
60 : std::string name;
61 : BlockGraph::Block* block;
62 :
63 E : MockBlockInfo(time_t time_,
64 : uint32_t start_,
65 : size_t size_,
66 : BlockGraph* block_graph)
67 E : : time(time_), start(start_), size(size_), name(""), block(NULL) {
68 E : DCHECK(block_graph != NULL);
69 E : block = block_graph->AddBlock(BlockGraph::CODE_BLOCK, size_, "block");
70 E : block->set_addr(core::RelativeAddress(start));
71 E : block->set_size(size);
72 E : block->set_name(name);
73 E : }
74 :
75 E : MockBlockInfo(time_t time_,
76 : uint32_t start_,
77 : size_t size_,
78 : std::string name_,
79 : BlockGraph* block_graph)
80 E : : time(time_), start(start_), size(size_), name(name_), block(NULL) {
81 E : DCHECK(block_graph != NULL);
82 E : block = block_graph->AddBlock(BlockGraph::CODE_BLOCK, size_, name_);
83 E : block->set_addr(core::RelativeAddress(start));
84 E : block->set_size(size);
85 E : block->set_name(name);
86 E : }
87 :
88 E : MockBlockInfo() {
89 E : }
90 : };
91 : typedef std::vector<MockBlockInfo> MockBlockInfoList;
92 :
93 E : HeatMapSimulationTest() : random_(55) {
94 E : }
95 :
96 E : void SetUp() {
97 E : simulation_.reset(new HeatMapSimulation());
98 E : blocks_[0] = MockBlockInfo(20, 0, 3, "A", &block_graph_);
99 E : blocks_[1] = MockBlockInfo(20, 0, 3, "A", &block_graph_);
100 E : blocks_[2] = MockBlockInfo(20, 2, 4, "C", &block_graph_);
101 E : blocks_[3] = MockBlockInfo(20, 2, 1, "B", &block_graph_);
102 E : blocks_[4] = MockBlockInfo(20, 10, 3, "B", &block_graph_);
103 E : blocks_[5] = MockBlockInfo(20, 10, 3, "A", &block_graph_);
104 E : blocks_[6] = MockBlockInfo(20, 10, 4, "B", &block_graph_);
105 E : blocks_[7] = MockBlockInfo(20, 10, 1, "A", &block_graph_);
106 E : blocks_[8] = MockBlockInfo(40, 2, 5, "B", &block_graph_);
107 :
108 E : time = Time::FromTimeT(10);
109 E : }
110 :
111 : // Simulates the current simulation with the function blocks given
112 : // in blocks_ with given parameters, and compares the result to certain
113 : // expected value.
114 : // @param expected_size The expected output size.
115 : // @param expected_times An expected_size sized array with the expected
116 : // time of entry of each time slice.
117 : // @param expected_totals An expected_size sized array with the expected
118 : // totals in each time slice.
119 : // @param expected_slices An expected_size sized array with the expected
120 : // memory slices in each time slice.
121 : void CheckSimulationResult(uint32_t expected_size,
122 : const uint32_t expected_times[],
123 E : TimeSlice::MemorySliceMap expected_slices[]) {
124 E : std::vector<uint32_t> expected_totals(expected_size, 0);
125 :
126 : // Loop through all the functions and add the number of times they were
127 : // called to their respective MemorySlice and TimeSlice totals.
128 E : for (uint32_t i = 0; i < expected_size; ++i) {
129 E : TimeSlice::MemorySliceMap::iterator u = expected_slices[i].begin();
130 E : for (; u != expected_slices[i].end(); ++u) {
131 E : u->second.total = 0;
132 :
133 : TimeSlice::FunctionMap::const_iterator functions_iter =
134 E : u->second.functions.begin();
135 E : for (; functions_iter != u->second.functions.end(); ++functions_iter) {
136 E : u->second.total += functions_iter->second;
137 E : expected_totals[i] += functions_iter->second;
138 E : }
139 E : }
140 E : }
141 :
142 E : simulation_->OnProcessStarted(time, 1);
143 :
144 E : for (uint32_t i = 0; i < arraysize(blocks_); i++) {
145 E : simulation_->OnFunctionEntry(Time::FromTimeT(blocks_[i].time),
146 : blocks_[i].block);
147 E : }
148 :
149 E : EXPECT_EQ(simulation_->time_memory_map().size(), expected_size);
150 :
151 E : for (uint32_t i = 0; i < expected_size; i++) {
152 : HeatMapSimulation::TimeMemoryMap::const_iterator current_slice =
153 E : simulation_->time_memory_map().find(expected_times[i]);
154 :
155 E : ASSERT_NE(current_slice, simulation_->time_memory_map().end());
156 E : EXPECT_EQ(current_slice->second.total(), expected_totals[i]);
157 :
158 E : ASSERT_TRUE(current_slice->second.slices().size() ==
159 : expected_slices[i].size());
160 :
161 E : EXPECT_TRUE(std::equal(current_slice->second.slices().begin(),
162 : current_slice->second.slices().end(),
163 : expected_slices[i].begin(),
164 : CompareMemorySlices<true>()));
165 E : }
166 E : }
167 :
168 : // Turn a MockBlockInfoList into a vector.
169 : // @param input The MockBlockInfoList to be transformed.
170 : // @param size The size of the latest byte pointed by the MockBlockInfoList.
171 : // @returns A vector of size size where every element is equal to the number
172 : // of different MockBlockInfos in input that cover to that position.
173 E : std::vector<uint32_t> Vectorize(const MockBlockInfoList& input, size_t size) {
174 E : std::vector<uint32_t> vector_input(size, 0);
175 E : for (uint32_t i = 0; i < input.size(); i++) {
176 E : for (uint32_t u = 0; u < input[i].size; u++)
177 E : vector_input[input[i].start + u - input[0].start]++;
178 E : }
179 :
180 E : return vector_input;
181 E : }
182 :
183 : // Takes a MockBlockInfoList where all the MockBlockInfos have the same time
184 : // value and returns another one that should generate the same output.
185 : // The algorithm consists of repeatly getting MockBlockInfos with start
186 : // address equal to the first element that isn't full yet, and size equal
187 : // to some random number from 1 to the distance between our element and
188 : // the next element that doesn't need more blocks to be full.
189 : // @param input A MockBlockInfoList where each element has the same size.
190 : // @returns Another MockBlockInfoList whose output is the same as the
191 : // parameter.
192 E : MockBlockInfoList RandomizeTimeBlocks(const MockBlockInfoList &input) {
193 E : MockBlockInfoList random_input;
194 :
195 E : if (input.size() == 0) {
196 : // This should never be reached
197 i : ADD_FAILURE();
198 i : return random_input;
199 : }
200 :
201 : // Get the time of the blocks, the address of the first block, and the
202 : // size of all them.
203 E : time_t time = input[0].time;
204 E : uint32_t start = input[0].start;
205 E : size_t size = input[0].start + input[0].size;
206 :
207 E : for (uint32_t i = 0; i < input.size(); i++) {
208 E : if (input[i].time != time) {
209 : // This should never be reached
210 i : ADD_FAILURE();
211 i : return random_input;
212 : }
213 E : start = std::min(start, input[i].start);
214 E : size = std::max(size, input[i].start + input[i].size);
215 E : }
216 E : size -= start;
217 :
218 E : std::vector<uint32_t> slices = Vectorize(input, size);
219 :
220 E : uint32_t slice = 0;
221 E : while (slice < slices.size()) {
222 E : if (slices[slice] == 0) {
223 E : slice++;
224 E : continue;
225 : }
226 :
227 E : size_t max_size = slice;
228 E : for (; max_size < slices.size(); max_size++) {
229 E : if (slices[max_size] == 0)
230 E : break;
231 E : }
232 :
233 E : uint32_t block_size = 0;
234 E : block_size = random_(max_size - slice) + 1;
235 :
236 E : for (uint32_t i = 0; i < block_size; i++) {
237 E : if (slices[slice + i] > 0)
238 E : slices[slice + i]--;
239 E : }
240 :
241 E : random_input.push_back(
242 : MockBlockInfo(time, slice + start, block_size, &block_graph_));
243 E : }
244 :
245 E : return random_input;
246 E : }
247 :
248 : // Takes a MockBlockInfoList and returns another at random that should
249 : // generate the same output.
250 : // @param input The MockBlockInfoList to be transformed.
251 : // @returns A random MockBlockInfoList that should generate the same output
252 : // as input.
253 E : MockBlockInfoList GenerateRandomInput() {
254 E : MockBlockInfoList random_input;
255 :
256 E : MockBlockInfoList time_input;
257 E : time_t last_time = blocks_[0].time;
258 :
259 E : for (uint32_t i = 0; i <= arraysize(blocks_); i++) {
260 E : if (i == arraysize(blocks_) || last_time != blocks_[i].time) {
261 E : MockBlockInfoList random_time_input = RandomizeTimeBlocks(time_input);
262 :
263 E : random_input.insert(random_input.end(),
264 : random_time_input.begin(),
265 : random_time_input.end());
266 :
267 E : time_input.clear();
268 E : }
269 :
270 E : if (i != arraysize(blocks_)) {
271 E : time_input.push_back(blocks_[i]);
272 E : last_time = blocks_[i].time;
273 : }
274 E : }
275 :
276 E : std::random_shuffle(random_input.begin(), random_input.end(), random_);
277 E : return random_input;
278 E : }
279 :
280 : std::unique_ptr<HeatMapSimulation> simulation_;
281 :
282 : Time time;
283 : MockBlockInfo blocks_[9];
284 : core::RandomNumberGenerator random_;
285 : BlockGraph block_graph_;
286 : };
287 :
288 : } // namespace
289 :
290 E : TEST_F(HeatMapSimulationTest, CorrectHeatMap) {
291 : static const uint32_t expected_size = 2;
292 : static const uint32_t expected_times[expected_size] = {10000000, 30000000};
293 :
294 E : TimeSlice::MemorySliceMap expected_slices[expected_size];
295 E : expected_slices[0][0].functions["A"] = 10;
296 E : expected_slices[0][0].functions["B"] = 8;
297 E : expected_slices[0][0].functions["C"] = 4;
298 E : expected_slices[1][0].functions["B"] = 5;
299 :
300 E : ASSERT_EQ(arraysize(expected_times), expected_size);
301 E : ASSERT_EQ(arraysize(expected_slices), expected_size);
302 :
303 E : simulation_->set_output_individual_functions(true);
304 :
305 E : CheckSimulationResult(expected_size, expected_times, expected_slices);
306 :
307 E : EXPECT_EQ(simulation_->max_time_slice_usecs(), 30000000);
308 E : EXPECT_EQ(simulation_->max_memory_slice_bytes(), 0);
309 E : }
310 :
311 E : TEST_F(HeatMapSimulationTest, SmallMemorySliceSize) {
312 : static const uint32_t expected_size = 2;
313 : static const uint32_t expected_times[expected_size] = {10000000, 30000000};
314 :
315 E : TimeSlice::MemorySliceMap expected_slices[expected_size];
316 E : expected_slices[0][0].functions["A"] = 2;
317 E : expected_slices[0][1].functions["A"] = 2;
318 E : expected_slices[0][2].functions["A"] = 2;
319 E : expected_slices[0][2].functions["B"] = 1;
320 E : expected_slices[0][2].functions["C"] = 1;
321 E : expected_slices[0][3].functions["C"] = 1;
322 E : expected_slices[0][4].functions["C"] = 1;
323 E : expected_slices[0][5].functions["C"] = 1;
324 E : expected_slices[0][10].functions["A"] = 2;
325 E : expected_slices[0][10].functions["B"] = 2;
326 E : expected_slices[0][11].functions["A"] = 1;
327 E : expected_slices[0][11].functions["B"] = 2;
328 E : expected_slices[0][12].functions["A"] = 1;
329 E : expected_slices[0][12].functions["B"] = 2;
330 E : expected_slices[0][13].functions["B"] = 1;
331 E : expected_slices[1][2].functions["B"] = 1;
332 E : expected_slices[1][3].functions["B"] = 1;
333 E : expected_slices[1][4].functions["B"] = 1;
334 E : expected_slices[1][5].functions["B"] = 1;
335 E : expected_slices[1][6].functions["B"] = 1;
336 :
337 E : ASSERT_EQ(arraysize(expected_times), expected_size);
338 E : ASSERT_EQ(arraysize(expected_slices), expected_size);
339 :
340 E : simulation_->set_output_individual_functions(true);
341 E : simulation_->set_memory_slice_bytes(1);
342 :
343 E : CheckSimulationResult(expected_size, expected_times, expected_slices);
344 :
345 E : EXPECT_EQ(simulation_->max_time_slice_usecs(), 30000000);
346 E : EXPECT_EQ(simulation_->max_memory_slice_bytes(), 13);
347 E : }
348 :
349 E : TEST_F(HeatMapSimulationTest, BigTimeSliceSize) {
350 : static const uint32_t expected_size = 1;
351 : static const uint32_t expected_times[expected_size] = {0};
352 :
353 E : TimeSlice::MemorySliceMap expected_slices[expected_size];
354 E : expected_slices[0][0].functions["A"] = 10;
355 E : expected_slices[0][0].functions["B"] = 13;
356 E : expected_slices[0][0].functions["C"] = 4;
357 :
358 E : ASSERT_EQ(arraysize(expected_times), expected_size);
359 E : ASSERT_EQ(arraysize(expected_slices), expected_size);
360 :
361 E : simulation_->set_output_individual_functions(true);
362 E : simulation_->set_time_slice_usecs(40000000);
363 :
364 E : CheckSimulationResult(expected_size, expected_times, expected_slices);
365 :
366 E : EXPECT_EQ(simulation_->max_time_slice_usecs(), 0);
367 E : EXPECT_EQ(simulation_->max_memory_slice_bytes(), 0);
368 E : }
369 :
370 E : TEST_F(HeatMapSimulationTest, BigTimeSliceSizeSmallMemorySliceSize) {
371 : static const uint32_t expected_size = 1;
372 : static const uint32_t expected_times[expected_size] = {0};
373 :
374 E : TimeSlice::MemorySliceMap expected_slices[expected_size];
375 E : expected_slices[0][0].functions["A"] = 2;
376 E : expected_slices[0][1].functions["A"] = 2;
377 E : expected_slices[0][2].functions["A"] = 2;
378 E : expected_slices[0][2].functions["B"] = 2;
379 E : expected_slices[0][2].functions["C"] = 1;
380 E : expected_slices[0][3].functions["B"] = 1;
381 E : expected_slices[0][3].functions["C"] = 1;
382 E : expected_slices[0][4].functions["B"] = 1;
383 E : expected_slices[0][4].functions["C"] = 1;
384 E : expected_slices[0][5].functions["B"] = 1;
385 E : expected_slices[0][5].functions["C"] = 1;
386 E : expected_slices[0][6].functions["B"] = 1;
387 E : expected_slices[0][10].functions["A"] = 2;
388 E : expected_slices[0][10].functions["B"] = 2;
389 E : expected_slices[0][11].functions["A"] = 1;
390 E : expected_slices[0][11].functions["B"] = 2;
391 E : expected_slices[0][12].functions["A"] = 1;
392 E : expected_slices[0][12].functions["B"] = 2;
393 E : expected_slices[0][13].functions["B"] = 1;
394 :
395 E : ASSERT_EQ(arraysize(expected_times), expected_size);
396 E : ASSERT_EQ(arraysize(expected_slices), expected_size);
397 :
398 E : simulation_->set_output_individual_functions(true);
399 E : simulation_->set_memory_slice_bytes(1);
400 E : simulation_->set_time_slice_usecs(40000000);
401 :
402 E : CheckSimulationResult(expected_size, expected_times, expected_slices);
403 :
404 E : EXPECT_EQ(simulation_->max_time_slice_usecs(), 0);
405 E : EXPECT_EQ(simulation_->max_memory_slice_bytes(), 13);
406 E : }
407 :
408 E : TEST_F(HeatMapSimulationTest, RandomInput) {
409 : // Using a blocks_ and its respective output,
410 : // generate several other random inputs that should result in the
411 : // same output and test HeatMapSimulation with them.
412 : static const uint32_t expected_size = 2;
413 : static const uint32_t expected_times[expected_size] = {10000000, 30000000};
414 :
415 E : TimeSlice::MemorySliceMap expected_slices[expected_size];
416 E : expected_slices[0][0].total = 2;
417 E : expected_slices[0][1].total = 2;
418 E : expected_slices[0][2].total = 4;
419 E : expected_slices[0][3].total = 1;
420 E : expected_slices[0][4].total = 1;
421 E : expected_slices[0][5].total = 1;
422 E : expected_slices[0][10].total = 4;
423 E : expected_slices[0][11].total = 3;
424 E : expected_slices[0][12].total = 3;
425 E : expected_slices[0][13].total = 1;
426 E : expected_slices[1][2].total = 1;
427 E : expected_slices[1][3].total = 1;
428 E : expected_slices[1][4].total = 1;
429 E : expected_slices[1][5].total = 1;
430 E : expected_slices[1][6].total = 1;
431 :
432 E : ASSERT_EQ(arraysize(expected_times), expected_size);
433 E : ASSERT_EQ(arraysize(expected_slices), expected_size);
434 :
435 E : for (uint32_t i = 0; i < 100; i++) {
436 : // Generate a random input that should have the same output than blocks_.
437 E : MockBlockInfoList random_input = GenerateRandomInput();
438 :
439 E : std::stringstream s;
440 E : s << "Failed with input: ";
441 E : for (uint32_t i = 0; i < random_input.size(); i++) {
442 E : s << '(' << random_input[i].time << ", " << random_input[i].start;
443 E : s << ", " << random_input[i].size << "), ";
444 E : }
445 :
446 : // Test simulation_ with this input.
447 E : simulation_.reset(new HeatMapSimulation());
448 E : ASSERT_TRUE(simulation_ != NULL);
449 :
450 E : simulation_->OnProcessStarted(time, 0);
451 E : simulation_->set_memory_slice_bytes(1);
452 E : simulation_->set_time_slice_usecs(1);
453 :
454 E : for (uint32_t i = 0; i < random_input.size(); i++) {
455 E : simulation_->OnFunctionEntry(Time::FromTimeT(random_input[i].time),
456 : random_input[i].block);
457 E : }
458 :
459 E : for (uint32_t i = 0; i < expected_size; i++) {
460 : HeatMapSimulation::TimeMemoryMap::const_iterator current_slice =
461 E : simulation_->time_memory_map().find(expected_times[i]);
462 :
463 E : ASSERT_NE(current_slice, simulation_->time_memory_map().end());
464 E : ASSERT_TRUE(current_slice->second.slices().size() ==
465 E : expected_slices[i].size());
466 :
467 E : EXPECT_TRUE(std::equal(current_slice->second.slices().begin(),
468 : current_slice->second.slices().end(),
469 : expected_slices[i].begin(),
470 E : CompareMemorySlices<false>()));
471 E : }
472 :
473 E : ASSERT_FALSE(testing::Test::HasNonfatalFailure()) << s.str();
474 E : }
475 E : }
476 :
477 : } // namespace simulate
|