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