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