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