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/reorder/linear_order_generator.h"
16 :
17 : #include "base/time.h"
18 : #include "base/memory/scoped_ptr.h"
19 : #include "gtest/gtest.h"
20 : #include "syzygy/block_graph/block_graph.h"
21 : #include "syzygy/core/address.h"
22 : #include "syzygy/core/random_number_generator.h"
23 : #include "syzygy/reorder/order_generator_test.h"
24 :
25 : namespace reorder {
26 :
27 : class LinearOrderGeneratorTest : public testing::OrderGeneratorTest {
28 : protected:
29 : void ExpectLinearOrdering(
30 : Reorderer::Order::BlockList::const_iterator it,
31 E : Reorderer::Order::BlockList::const_iterator end) {
32 : // Verifies that the given block list appears in a linear order in the
33 : // original image.
34 E : core::RelativeAddress cur_addr;
35 E : for (; it != end; it++) {
36 E : core::RelativeAddress addr;
37 E : EXPECT_TRUE(image_layout_.blocks.GetAddressOf(*it, &addr));
38 E : EXPECT_LT(cur_addr, addr);
39 E : cur_addr = addr;
40 E : }
41 E : }
42 :
43 : LinearOrderGenerator order_generator_;
44 : };
45 :
46 E : TEST_F(LinearOrderGeneratorTest, DoNotReorder) {
47 : EXPECT_TRUE(order_generator_.CalculateReordering(input_dll_,
48 : image_layout_,
49 : false,
50 : false,
51 E : &order_));
52 :
53 E : ExpectNoDuplicateBlocks();
54 :
55 : // Verify that the order found in order_ matches the original decomposed
56 : // image.
57 : Reorderer::Order::BlockListMap::const_iterator it =
58 E : order_.section_block_lists.begin();
59 E : for (; it != order_.section_block_lists.end(); ++it) {
60 E : const IMAGE_SECTION_HEADER* section = input_dll_.section_header(it->first);
61 E : ExpectNoReorder(section, it->second);
62 E : }
63 E : }
64 :
65 E : TEST_F(LinearOrderGeneratorTest, ReorderCode) {
66 E : core::RandomNumberGenerator random(12345);
67 :
68 : // Get the .text code section.
69 E : size_t section_index = input_dll_.GetSectionIndex(".text");
70 : const IMAGE_SECTION_HEADER* section =
71 E : input_dll_.section_header(section_index);
72 E : ASSERT_TRUE(section != NULL);
73 :
74 : // Get 5 random blocks.
75 E : std::vector<core::RelativeAddress> addrs;
76 E : block_graph::ConstBlockVector blocks;
77 E : std::set<const block_graph::BlockGraph::Block*> block_set;
78 E : while (blocks.size() < 5) {
79 : core::RelativeAddress addr(
80 E : section->VirtualAddress + random(section->Misc.VirtualSize));
81 E : addrs.push_back(addr);
82 : const block_graph::BlockGraph::Block* block =
83 E : image_layout_.blocks.GetBlockByAddress(addr);
84 E : if (!block_set.insert(block).second)
85 E : continue;
86 E : blocks.push_back(block);
87 E : }
88 :
89 : // Test multiple calls to the same block in a process group.
90 : // Expected process group 1 calls: block1, block0, block3.
91 E : order_generator_.OnProcessStarted(1, GetSystemTime());
92 E : order_generator_.OnCodeBlockEntry(blocks[1], addrs[1], 1, 1, GetSystemTime());
93 E : order_generator_.OnCodeBlockEntry(blocks[0], addrs[0], 1, 1, GetSystemTime());
94 E : order_generator_.OnCodeBlockEntry(blocks[1], addrs[1], 1, 1, GetSystemTime());
95 E : order_generator_.OnCodeBlockEntry(blocks[3], addrs[3], 1, 1, GetSystemTime());
96 E : order_generator_.OnProcessEnded(1, GetSystemTime());
97 :
98 : // Test out of order time calls to different blocks.
99 : // Expected process group 2 calls: block0, block2, block4.
100 E : order_generator_.OnProcessStarted(2, GetSystemTime());
101 E : Reorderer::UniqueTime time = GetSystemTime();
102 E : order_generator_.OnCodeBlockEntry(blocks[2], addrs[2], 2, 1, GetSystemTime());
103 E : order_generator_.OnCodeBlockEntry(blocks[0], addrs[0], 2, 1, time);
104 E : order_generator_.OnCodeBlockEntry(blocks[4], addrs[4], 2, 1, time);
105 E : order_generator_.OnProcessEnded(2, GetSystemTime());
106 :
107 : // Test nested processes.
108 : // Expected process group 3 calls: block0, block1, block2.
109 E : order_generator_.OnProcessStarted(3, GetSystemTime());
110 E : order_generator_.OnCodeBlockEntry(blocks[0], addrs[0], 3, 1, GetSystemTime());
111 E : order_generator_.OnProcessStarted(4, GetSystemTime());
112 E : order_generator_.OnCodeBlockEntry(blocks[1], addrs[1], 4, 1, GetSystemTime());
113 E : order_generator_.OnCodeBlockEntry(blocks[2], addrs[2], 4, 1, GetSystemTime());
114 E : order_generator_.OnProcessEnded(4, GetSystemTime());
115 E : order_generator_.OnProcessEnded(3, GetSystemTime());
116 :
117 : // Expected ordering:
118 : // - block0 (highest call count).
119 : // - block1, block2 (second highest call count, block2 has smaller average).
120 : // - block3, block4 (single call count, order by process group id).
121 :
122 : // Do the reordering.
123 : EXPECT_TRUE(order_generator_.CalculateReordering(input_dll_,
124 : image_layout_,
125 : true,
126 : false,
127 E : &order_));
128 :
129 E : ExpectNoDuplicateBlocks();
130 :
131 : // Verify that code blocks have been reordered and that data blocks have not.
132 : Reorderer::Order::BlockListMap::const_iterator it =
133 E : order_.section_block_lists.begin();
134 E : for (; it != order_.section_block_lists.end(); ++it) {
135 E : const IMAGE_SECTION_HEADER* section = input_dll_.section_header(it->first);
136 E : if (input_dll_.GetSectionName(*section) == ".text") {
137 : // Compare the first 5 elements.
138 E : EXPECT_TRUE(std::equal(blocks.begin(), blocks.end(), it->second.begin()));
139 : // Expect a linear ordering in the rest.
140 E : ExpectLinearOrdering(it->second.begin() + 5, it->second.end());
141 E : } else {
142 E : ExpectNoReorder(section, it->second);
143 : }
144 E : }
145 E : }
146 :
147 : } // namespace reorder
|