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