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/transforms/basic_block_layout_transform.h"
16 :
17 : #include "gmock/gmock.h"
18 : #include "gtest/gtest.h"
19 : #include "syzygy/block_graph/basic_block_test_util.h"
20 :
21 : namespace reorder {
22 : namespace transforms {
23 :
24 : namespace {
25 :
26 : typedef BasicBlockSubGraphLayoutTransform::BasicBlockMap BasicBlockMap;
27 :
28 : using testing::BasicBlockTest;
29 : using testing::ContainerEq;
30 :
31 : class BasicBlockSubGraphLayoutTransformTest : public BasicBlockTest {
32 : public:
33 E : virtual void SetUp() override {
34 E : BasicBlockTest::SetUp();
35 E : ASSERT_NO_FATAL_FAILURE(InitBlockGraph());
36 E : ASSERT_NO_FATAL_FAILURE(InitBasicBlockSubGraph());
37 E : }
38 :
39 E : bool Insert(size_t offset, size_t block_index, size_t bb_index) {
40 : return bb_map_.insert(std::make_pair(
41 : offset,
42 E : std::make_pair(block_index, bb_index))).second;
43 E : }
44 :
45 E : void LayoutIsAsExpected() {
46 E : BasicBlockMap bb_map;
47 :
48 E : size_t bd_idx = 0;
49 : BasicBlockSubGraph::BlockDescriptionList::const_iterator bd_it =
50 E : subgraph_.block_descriptions().begin();
51 E : for (; bd_it != subgraph_.block_descriptions().end(); ++bd_it, ++bd_idx) {
52 E : size_t bb_idx = 0;
53 : BasicBlockSubGraph::BasicBlockOrdering::const_iterator bb_it =
54 E : bd_it->basic_block_order.begin();
55 E : for (; bb_it != bd_it->basic_block_order.end(); ++bb_it, ++bb_idx) {
56 E : size_t bb_offset = (*bb_it)->offset();
57 E : ASSERT_TRUE(bb_map.insert(std::make_pair(
58 : bb_offset, std::make_pair(bd_idx, bb_idx))).second);
59 E : }
60 E : }
61 E : EXPECT_THAT(bb_map, ContainerEq(bb_map_));
62 E : }
63 :
64 : BasicBlockMap bb_map_;
65 : };
66 :
67 : } // namespace
68 :
69 E : TEST_F(BasicBlockSubGraphLayoutTransformTest, NonContiguousBlockIndicesFails) {
70 : // This is a valid map, but we use block indices of 0 and 2 rather than 0 and
71 : // 1.
72 E : ASSERT_TRUE(Insert(0, 0, 0));
73 E : ASSERT_TRUE(Insert(23, 0, 1));
74 E : ASSERT_TRUE(Insert(24, 0, 2));
75 E : ASSERT_TRUE(Insert(31, 0, 3));
76 E : ASSERT_TRUE(Insert(36, 0, 4));
77 E : ASSERT_TRUE(Insert(37, 2, 0));
78 E : ASSERT_TRUE(Insert(42, 2, 1));
79 E : ASSERT_TRUE(Insert(49, 2, 2));
80 E : ASSERT_TRUE(Insert(52, 2, 3));
81 E : ASSERT_TRUE(Insert(64, 2, 4));
82 E : BasicBlockSubGraphLayoutTransform tx(bb_map_);
83 : EXPECT_FALSE(tx.TransformBasicBlockSubGraph(
84 E : &policy_, &block_graph_, &subgraph_));
85 E : }
86 :
87 : TEST_F(BasicBlockSubGraphLayoutTransformTest,
88 E : NonContiguousBasicBlockPositionsFails) {
89 : // This is a valid map, but we use non-contiguous basic block positions.
90 E : ASSERT_TRUE(Insert(0, 0, 0));
91 E : ASSERT_TRUE(Insert(23, 0, 1));
92 E : ASSERT_TRUE(Insert(24, 0, 2));
93 E : ASSERT_TRUE(Insert(31, 0, 3));
94 E : ASSERT_TRUE(Insert(36, 0, 4));
95 E : ASSERT_TRUE(Insert(37, 0, 5));
96 E : ASSERT_TRUE(Insert(42, 0, 6));
97 E : ASSERT_TRUE(Insert(49, 0, 7));
98 E : ASSERT_TRUE(Insert(52, 0, 8));
99 E : ASSERT_TRUE(Insert(64, 0, 10));
100 E : BasicBlockSubGraphLayoutTransform tx(bb_map_);
101 : EXPECT_FALSE(tx.TransformBasicBlockSubGraph(
102 E : &policy_, &block_graph_, &subgraph_));
103 E : }
104 :
105 E : TEST_F(BasicBlockSubGraphLayoutTransformTest, Identity) {
106 E : ASSERT_TRUE(Insert(0, 0, 0));
107 E : ASSERT_TRUE(Insert(23, 0, 1));
108 E : ASSERT_TRUE(Insert(24, 0, 2));
109 E : ASSERT_TRUE(Insert(31, 0, 3));
110 E : ASSERT_TRUE(Insert(36, 0, 4));
111 E : ASSERT_TRUE(Insert(37, 0, 5));
112 E : ASSERT_TRUE(Insert(42, 0, 6));
113 E : ASSERT_TRUE(Insert(49, 0, 7));
114 E : ASSERT_TRUE(Insert(52, 0, 8));
115 E : ASSERT_TRUE(Insert(64, 0, 9));
116 :
117 E : BasicBlockSubGraphLayoutTransform tx(bb_map_);
118 : EXPECT_TRUE(tx.TransformBasicBlockSubGraph(
119 E : &policy_, &block_graph_, &subgraph_));
120 E : LayoutIsAsExpected();
121 E : }
122 :
123 E : TEST_F(BasicBlockSubGraphLayoutTransformTest, CodeAndDataSplit) {
124 : // Code blocks.
125 E : ASSERT_TRUE(Insert(0, 0, 0));
126 E : ASSERT_TRUE(Insert(24, 0, 1));
127 E : ASSERT_TRUE(Insert(31, 0, 2));
128 E : ASSERT_TRUE(Insert(36, 0, 3));
129 E : ASSERT_TRUE(Insert(37, 0, 4));
130 E : ASSERT_TRUE(Insert(42, 0, 5));
131 E : ASSERT_TRUE(Insert(49, 0, 6));
132 :
133 : // Data blocks.
134 E : ASSERT_TRUE(Insert(52, 1, 0));
135 E : ASSERT_TRUE(Insert(64, 1, 1));
136 :
137 : // We explicitly do not specify the BB at offset 23, which consists of
138 : // padding that can be deleted.
139 :
140 E : BasicBlockSubGraphLayoutTransform tx(bb_map_);
141 : EXPECT_TRUE(tx.TransformBasicBlockSubGraph(
142 E : &policy_, &block_graph_, &subgraph_));
143 E : LayoutIsAsExpected();
144 E : }
145 :
146 : namespace {
147 :
148 : class BasicBlockLayoutTransformTest : public BasicBlockTest {
149 : public:
150 : typedef BasicBlockLayoutTransform::Order Order;
151 :
152 E : virtual void SetUp() override {
153 E : BasicBlockTest::SetUp();
154 : header_block_ = block_graph_.AddBlock(BlockGraph::DATA_BLOCK,
155 E : 10, "Dummy Header Block");
156 E : ASSERT_TRUE(header_block_ != NULL);
157 E : ASSERT_NO_FATAL_FAILURE(InitBlockGraph());
158 E : }
159 :
160 : BlockGraph::Block* header_block_;
161 : };
162 :
163 : } // namespace
164 :
165 E : TEST_F(BasicBlockLayoutTransformTest, NewSectionNoBlocksFails) {
166 E : Order order;
167 E : order.sections.resize(1);
168 E : order.sections[0].id = Order::SectionSpec::kNewSectionId;
169 E : order.sections[0].name = ".text.new";
170 E : order.sections[0].characteristics = text_section_->characteristics();
171 E : order.sections[0].blocks.resize(0);
172 :
173 E : BasicBlockLayoutTransform tx(&order);
174 : EXPECT_FALSE(tx.TransformBlockGraph(
175 E : &policy_, &block_graph_, header_block_));
176 E : }
177 :
178 E : TEST_F(BasicBlockLayoutTransformTest, InvalidExistingSectionFails) {
179 E : Order order;
180 E : order.sections.resize(1);
181 E : order.sections[0].id = 47;
182 E : order.sections[0].name = "foobar";
183 : // Leave characteristics initialized to the default value.
184 E : order.sections[0].blocks.resize(1);
185 E : order.sections[0].blocks[0].block = assembly_func_;
186 :
187 E : BasicBlockLayoutTransform tx(&order);
188 : EXPECT_FALSE(tx.TransformBlockGraph(
189 E : &policy_, &block_graph_, header_block_));
190 E : }
191 :
192 E : TEST_F(BasicBlockLayoutTransformTest, ReorderSection) {
193 E : Order order;
194 E : order.sections.resize(1);
195 :
196 E : order.sections[0].id = text_section_->id();
197 E : order.sections[0].name = text_section_->name();
198 E : order.sections[0].blocks.resize(3);
199 E : order.sections[0].blocks[0].block = func2_;
200 E : order.sections[0].blocks[1].block = assembly_func_;
201 E : order.sections[0].blocks[2].block = func1_;
202 :
203 E : BasicBlockLayoutTransform tx(&order);
204 : EXPECT_TRUE(tx.TransformBlockGraph(
205 E : &policy_, &block_graph_, header_block_));
206 :
207 : // No new blocks or sections were created.
208 E : EXPECT_EQ(5u, block_graph_.blocks().size());
209 E : EXPECT_EQ(2u, block_graph_.sections().size());
210 E : }
211 :
212 E : TEST_F(BasicBlockLayoutTransformTest, CreateNewSection) {
213 E : Order order;
214 E : order.sections.resize(2);
215 :
216 E : order.sections[0].id = text_section_->id();
217 E : order.sections[0].name = ".text.hot";
218 E : order.sections[0].characteristics = text_section_->characteristics();
219 E : order.sections[0].blocks.resize(1);
220 E : order.sections[0].blocks[0].block = assembly_func_;
221 :
222 E : order.sections[1].id = Order::SectionSpec::kNewSectionId;
223 E : order.sections[1].name = ".text.cold";
224 E : order.sections[1].characteristics = text_section_->characteristics();
225 E : order.sections[1].blocks.resize(2);
226 E : order.sections[1].blocks[0].block = func1_;
227 E : order.sections[1].blocks[1].block = func2_;
228 :
229 : // Remember these for validation post-transform.
230 E : DWORD text_section_characteristics = text_section_->characteristics();
231 :
232 E : BasicBlockLayoutTransform tx(&order);
233 : EXPECT_TRUE(tx.TransformBlockGraph(
234 E : &policy_, &block_graph_, header_block_));
235 :
236 : // No new blocks were created, but one new section was.
237 E : EXPECT_EQ(5u, block_graph_.blocks().size());
238 E : EXPECT_EQ(3u, block_graph_.sections().size());
239 :
240 : // The .text section has been renamed but the characteristics are the same.
241 E : EXPECT_EQ(order.sections[0].name, text_section_->name());
242 E : EXPECT_EQ(text_section_characteristics, text_section_->characteristics());
243 E : EXPECT_EQ(text_section_->id(), assembly_func_->section());
244 :
245 : // The new section is as expected.
246 : BlockGraph::Section* new_section =
247 E : &(block_graph_.sections_mutable().rbegin()->second);
248 E : EXPECT_EQ(order.sections[1].id, new_section->id());
249 E : EXPECT_EQ(order.sections[1].name, new_section->name());
250 E : EXPECT_EQ(order.sections[1].characteristics, new_section->characteristics());
251 E : EXPECT_EQ(new_section->id(), func1_->section());
252 E : EXPECT_EQ(new_section->id(), func2_->section());
253 E : }
254 :
255 E : TEST_F(BasicBlockLayoutTransformTest, SplitBlock) {
256 E : Order order;
257 E : order.sections.resize(2);
258 :
259 E : Order::OffsetVector assembly_func_code_bbs;
260 E : assembly_func_code_bbs.push_back(0);
261 E : assembly_func_code_bbs.push_back(24);
262 E : assembly_func_code_bbs.push_back(31);
263 E : assembly_func_code_bbs.push_back(36);
264 E : assembly_func_code_bbs.push_back(37);
265 E : assembly_func_code_bbs.push_back(42);
266 E : assembly_func_code_bbs.push_back(49);
267 :
268 E : Order::OffsetVector assembly_func_data_bbs;
269 E : assembly_func_data_bbs.push_back(52);
270 E : assembly_func_data_bbs.push_back(64);
271 :
272 E : order.sections[0].id = text_section_->id();
273 E : order.sections[0].name = text_section_->name();
274 E : order.sections[0].characteristics = text_section_->characteristics();
275 E : order.sections[0].blocks.resize(3);
276 E : order.sections[0].blocks[0].block = func1_;
277 E : order.sections[0].blocks[1].block = func2_;
278 E : order.sections[0].blocks[2].block = assembly_func_;
279 E : order.sections[0].blocks[2].basic_block_offsets = assembly_func_code_bbs;
280 :
281 E : order.sections[1].id = data_section_->id();
282 E : order.sections[1].name = data_section_->name();
283 E : order.sections[1].characteristics = data_section_->characteristics();
284 E : order.sections[1].blocks.resize(2);
285 E : order.sections[1].blocks[0].block = data_;
286 E : order.sections[1].blocks[1].block = assembly_func_;
287 E : order.sections[1].blocks[1].basic_block_offsets = assembly_func_data_bbs;
288 :
289 E : BlockGraph::BlockId old_assembly_func_id = assembly_func_->id();
290 :
291 E : BasicBlockLayoutTransform tx(&order);
292 : EXPECT_TRUE(tx.TransformBlockGraph(
293 E : &policy_, &block_graph_, header_block_));
294 :
295 : // One new block has been created and no new sections.
296 E : EXPECT_EQ(6u, block_graph_.blocks().size());
297 E : EXPECT_EQ(2u, block_graph_.sections().size());
298 :
299 : // The assembly func block no longer exists.
300 E : EXPECT_TRUE(block_graph_.GetBlockById(old_assembly_func_id) == NULL);
301 :
302 : // Get the 2 new blocks that replaced the assembly func.
303 : BlockGraph::BlockMap::reverse_iterator block_it =
304 E : block_graph_.blocks_mutable().rbegin();
305 E : BlockGraph::Block* new_block2 = &((block_it++)->second);
306 E : BlockGraph::Block* new_block1 = &(block_it->second);
307 :
308 : // We expect these blocks to be in the appropriate sections, and the order to
309 : // have been updated.
310 E : EXPECT_EQ(text_section_->id(), new_block1->section());
311 E : EXPECT_EQ(data_section_->id(), new_block2->section());
312 E : EXPECT_EQ(order.sections[0].blocks[2].block, new_block1);
313 E : EXPECT_EQ(order.sections[1].blocks[1].block, new_block2);
314 E : }
315 :
316 : } // namespace transforms
317 : } // namespace reorder
|