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 : // Tests for the basic block classes.
16 :
17 : #include "syzygy/block_graph/block_builder.h"
18 :
19 : #include "gmock/gmock.h"
20 : #include "gtest/gtest.h"
21 : #include "syzygy/block_graph/basic_block.h"
22 : #include "syzygy/block_graph/basic_block_subgraph.h"
23 : #include "syzygy/block_graph/basic_block_test_util.h"
24 : #include "syzygy/block_graph/block_graph.h"
25 :
26 : namespace block_graph {
27 :
28 : namespace {
29 :
30 : typedef BlockGraph::Block Block;
31 : typedef BlockGraph::Label Label;
32 : typedef BlockGraph::Reference Reference;
33 : typedef Block::Referrer Referrer;
34 :
35 : const uint8 kEmptyData[32] = { 0 };
36 :
37 : // Instructions we'll need in order to build the test subgraph.
38 : // TODO(rogerm): Share these definitions from a central location for all the
39 : // basic-block, builder and assembler/decomposer unit-tests.
40 : const uint8 kCall[5] = { 0xE8, 0x00, 0x00, 0x00, 0x00 };
41 : const uint8 kNop1[1] = { 0x90 };
42 : const uint8 kNop2[2] = { 0x66, 0x90 };
43 : const uint8 kNop3[3] = { 0x66, 0x66, 0x90 };
44 : const uint8 kNop7[7] = { 0x0F, 0x1F, 0x80, 0x00, 0x00, 0x00, 0x00 };
45 : const uint8 kNop9[9] = { 0x66, 0x0F, 0x1F, 0x84, 0x00, 0x00, 0x00, 0x00, 0x00 };
46 :
47 : class BlockBuilderTest : public testing::BasicBlockTest {
48 : public:
49 : static Instruction* AddInstruction(BasicCodeBlock* bb,
50 : const uint8* buf,
51 E : size_t len) {
52 E : CHECK(bb != NULL);
53 E : Instruction tmp;
54 E : EXPECT_TRUE(Instruction::FromBuffer(buf, len, &tmp));
55 E : EXPECT_EQ(len, tmp.size());
56 :
57 E : bb->instructions().push_back(tmp);
58 E : return &bb->instructions().back();
59 E : }
60 :
61 : BasicCodeBlock* CreateCodeBB(const base::StringPiece& name,
62 E : size_t len) {
63 E : Instruction nop;
64 E : EXPECT_EQ(1U, nop.size());
65 E : BasicCodeBlock* bb = subgraph_.AddBasicCodeBlock(name);
66 E : EXPECT_TRUE(bb != NULL);
67 E : for (size_t i = 0; i < len; ++i)
68 E : bb->instructions().push_back(nop);
69 E : return bb;
70 E : }
71 :
72 E : Block* CreateLayout(size_t size1, size_t size2, size_t size3, size_t size4) {
73 : // Generate a set of puzzle blocks.
74 E : BasicCodeBlock* bb1 = CreateCodeBB("bb1", size1);
75 E : BasicCodeBlock* bb2 = CreateCodeBB("bb2", size2);
76 E : BasicCodeBlock* bb3 = CreateCodeBB("bb3", size3);
77 E : BasicCodeBlock* bb4 = CreateCodeBB("bb3", size4);
78 :
79 : // BB1 has BB4 and BB2 as successors.
80 : bb1->successors().push_back(
81 : Successor(Successor::kConditionEqual,
82 : BasicBlockReference(BlockGraph::RELATIVE_REF, 4, bb4),
83 E : 0));
84 : bb1->successors().push_back(
85 : Successor(Successor::kConditionNotEqual,
86 : BasicBlockReference(BlockGraph::RELATIVE_REF, 4, bb2),
87 E : 0));
88 :
89 : // BB2 has BB1 as successor.
90 : bb2->successors().push_back(
91 : Successor(Successor::kConditionTrue,
92 : BasicBlockReference(BlockGraph::RELATIVE_REF, 4, bb1),
93 E : 0));
94 :
95 : // BB3 has BB4 as successor.
96 : bb3->successors().push_back(
97 : Successor(Successor::kConditionTrue,
98 : BasicBlockReference(BlockGraph::RELATIVE_REF, 4, bb4),
99 E : 0));
100 :
101 : BasicBlockSubGraph::BlockDescription* d1 = subgraph_.AddBlockDescription(
102 E : "new_block", BlockGraph::CODE_BLOCK, 0, 1, 0);
103 E : d1->basic_block_order.push_back(bb1);
104 E : d1->basic_block_order.push_back(bb2);
105 E : d1->basic_block_order.push_back(bb3);
106 E : d1->basic_block_order.push_back(bb4);
107 :
108 E : BlockBuilder builder(&block_graph_);
109 E : EXPECT_TRUE(builder.Merge(&subgraph_));
110 E : EXPECT_EQ(1, builder.new_blocks().size());
111 :
112 E : Block* new_block = builder.new_blocks()[0];
113 E : EXPECT_TRUE(new_block != NULL);
114 E : return new_block;
115 E : }
116 : };
117 :
118 : } // namespace
119 :
120 : // This test constructs the following subgraph then merges it into block graph.
121 : //
122 : // +-------+
123 : // | Data |
124 : // +---+---+
125 : // |
126 : // +--> +---------+
127 : // bb1 0 | 5 bytes | Ref: 4-byte ref to code block @ 1, Label1 (code+call)
128 : // +---------+
129 : // | 2 bytes | Successor: 1-byte ref to bb1 @ 6
130 : // +---------+
131 : // | 2 bytes | Successor: 1-byte ref to bb3 @ 8
132 : // +---------+
133 : // bb2 9 | 2 bytes | Label2 (code)
134 : // +---------+
135 : // | 3 bytes |
136 : // +---------+
137 : // bb3 14 | 2 bytes | Label3 (code).
138 : // +---------+
139 : // | 1 bytes |
140 : // +---------+ Successor: elided here. Label4
141 : // bb4 17 | 7 bytes |
142 : // +---------+
143 : // | 9 bytes |
144 : // +---------+
145 : // | 2 bytes | Successor: 1-byte ref to bb2 @ 34
146 : // data 35 +---------+ Label5 (data).
147 : // | 4 bytes | Ref: 4-byte ref to bb1 @ 35
148 : // +---------+
149 : // | 4 bytes | Ref: 4-byte ref to bb2 @ 39
150 : // +---------+
151 : // | 4 bytes | Ref: 4-byte ref to bb3 @ 43
152 : // 47 +---------+
153 : //
154 E : TEST_F(BlockBuilderTest, Merge) {
155 : // Setup a code block which is referenced from a data block and references
156 : // another code block.
157 : BlockGraph::Block* original =
158 E : block_graph_.AddBlock(BlockGraph::CODE_BLOCK, 32, "original");
159 E : ASSERT_TRUE(original != NULL);
160 E : BlockGraph::BlockId original_id = original->id();
161 : BlockGraph::Block* other =
162 E : block_graph_.AddBlock(BlockGraph::DATA_BLOCK, 4, "other");
163 E : ASSERT_TRUE(other != NULL);
164 E : BlockGraph::BlockId other_id = other->id();
165 : ASSERT_TRUE(other->SetReference(
166 E : 0, BlockGraph::Reference(BlockGraph::ABSOLUTE_REF, 4, original, 0, 0)));
167 :
168 : // Verify some expectations.
169 E : ASSERT_EQ(2, block_graph_.blocks().size());
170 E : ASSERT_EQ(1, original->referrers().size());
171 :
172 : // Generate a mock decomposition of the original block.
173 E : subgraph_.set_original_block(original);
174 E : BasicCodeBlock* bb1 = subgraph_.AddBasicCodeBlock("bb1");
175 E : ASSERT_TRUE(bb1 != NULL);
176 E : BasicCodeBlock* bb2 = subgraph_.AddBasicCodeBlock("bb2");
177 E : ASSERT_TRUE(bb2 != NULL);
178 E : BasicCodeBlock* bb3 = subgraph_.AddBasicCodeBlock("bb3");
179 E : ASSERT_TRUE(bb3 != NULL);
180 E : BasicCodeBlock* bb4 = subgraph_.AddBasicCodeBlock("bb4");
181 E : ASSERT_TRUE(bb4 != NULL);
182 E : BasicDataBlock* table = subgraph_.AddBasicDataBlock("table", 12, kEmptyData);
183 E : ASSERT_TRUE(table != NULL);
184 :
185 : // Flesh out bb1 with an instruction having a reference and 2 successors.
186 E : Instruction* inst = AddInstruction(bb1, kCall, sizeof(kCall));
187 E : Label label_1("1", BlockGraph::CODE_LABEL | BlockGraph::CALL_SITE_LABEL);
188 E : inst->set_label(label_1);
189 E : ASSERT_TRUE(inst != NULL);
190 : ASSERT_TRUE(inst->references().insert(
191 : std::make_pair(1, BasicBlockReference(BlockGraph::ABSOLUTE_REF, 4,
192 E : other, 0, 0))).second);
193 : bb1->successors().push_back(
194 : Successor(Successor::kConditionEqual,
195 : BasicBlockReference(BlockGraph::RELATIVE_REF, 4, bb1),
196 E : 0));
197 : bb1->successors().push_back(
198 : Successor(Successor::kConditionNotEqual,
199 : BasicBlockReference(BlockGraph::RELATIVE_REF, 4, bb3),
200 E : 0));
201 E : ASSERT_TRUE(bb1->referrers().insert(BasicBlockReferrer(other, 0)).second);
202 :
203 : // Flesh out bb2 with some instructions and no successor.
204 E : inst = AddInstruction(bb2, kNop2, sizeof(kNop2));
205 E : Label label_2("2", BlockGraph::CODE_LABEL);
206 E : inst->set_label(label_2);
207 E : ASSERT_TRUE(inst != NULL);
208 E : ASSERT_TRUE(AddInstruction(bb2, kNop3, sizeof(kNop3)) != NULL);
209 :
210 : // Flesh out bb3 with some instructions and a single successor.
211 E : inst = AddInstruction(bb3, kNop2, sizeof(kNop2));
212 E : Label label_3("3", BlockGraph::CODE_LABEL);
213 E : inst->set_label(label_3);
214 E : ASSERT_TRUE(inst != NULL);
215 E : ASSERT_TRUE(AddInstruction(bb3, kNop1, sizeof(kNop1)) != NULL);
216 : bb3->successors().push_back(
217 : Successor(Successor::kConditionTrue,
218 : BasicBlockReference(BlockGraph::RELATIVE_REF, 4, bb4),
219 E : 0));
220 E : Label label_4("4", BlockGraph::CODE_LABEL);
221 E : bb3->successors().back().set_label(label_4);
222 :
223 : // Flesh out bb4 with some instructions and a single successor.
224 E : ASSERT_TRUE(AddInstruction(bb4, kNop7, sizeof(kNop7)) != NULL);
225 E : ASSERT_TRUE(AddInstruction(bb4, kNop9, sizeof(kNop9)) != NULL);
226 : bb4->successors().push_back(
227 : Successor(Successor::kConditionTrue,
228 : BasicBlockReference(BlockGraph::RELATIVE_REF, 4, bb2),
229 E : 0));
230 :
231 : // Flesh out table with references. Make the table aligned so that we test
232 : // our NOP insertion code.
233 E : Label label_5("5", BlockGraph::DATA_LABEL | BlockGraph::JUMP_TABLE_LABEL);
234 E : table->set_label(label_5);
235 E : table->set_alignment(4);
236 : ASSERT_TRUE(table->references().insert(std::make_pair(
237 E : 0, BasicBlockReference(BlockGraph::ABSOLUTE_REF, 4, bb1))).second);
238 : ASSERT_TRUE(table->references().insert(std::make_pair(
239 E : 4, BasicBlockReference(BlockGraph::ABSOLUTE_REF, 4, bb2))).second);
240 : ASSERT_TRUE(table->references().insert(std::make_pair(
241 E : 8, BasicBlockReference(BlockGraph::ABSOLUTE_REF, 4, bb3))).second);
242 :
243 : BasicBlockSubGraph::BlockDescription* d1 = subgraph_.AddBlockDescription(
244 E : "new_block", BlockGraph::CODE_BLOCK, 0, 1, 0);
245 E : d1->basic_block_order.push_back(bb1);
246 E : d1->basic_block_order.push_back(bb2);
247 E : d1->basic_block_order.push_back(bb3);
248 E : d1->basic_block_order.push_back(bb4);
249 E : d1->basic_block_order.push_back(table);
250 :
251 E : BlockBuilder builder(&block_graph_);
252 E : ASSERT_TRUE(builder.Merge(&subgraph_));
253 E : EXPECT_EQ(NULL, block_graph_.GetBlockById(original_id));
254 E : EXPECT_EQ(other, block_graph_.GetBlockById(other_id));
255 E : EXPECT_EQ(2, block_graph_.blocks().size());
256 E : ASSERT_EQ(1, builder.new_blocks().size());
257 E : BlockGraph::Block* new_block = builder.new_blocks().front();
258 E : EXPECT_EQ(new_block, block_graph_.GetBlockById(new_block->id()));
259 E : EXPECT_EQ(48U, new_block->size());
260 E : EXPECT_EQ(new_block->data_size(), new_block->size());
261 E : EXPECT_EQ(table->alignment(), new_block->alignment());
262 :
263 : // Validate the new block's references.
264 E : Block::ReferenceMap expected_references;
265 : expected_references[1] = Reference(
266 E : BlockGraph::ABSOLUTE_REF, 4, other, 0, 0);
267 : expected_references[6] = Reference(
268 E : BlockGraph::PC_RELATIVE_REF, 1, new_block, 0, 0);
269 : expected_references[8] = Reference(
270 E : BlockGraph::PC_RELATIVE_REF, 1, new_block, 14, 14);
271 : expected_references[34] = Reference(
272 E : BlockGraph::PC_RELATIVE_REF, 1, new_block, 9, 9);
273 : expected_references[36] = Reference(
274 E : BlockGraph::ABSOLUTE_REF, 4, new_block, 0, 0);
275 : expected_references[40] = Reference(
276 E : BlockGraph::ABSOLUTE_REF, 4, new_block, 9, 9);
277 : expected_references[44] = Reference(
278 E : BlockGraph::ABSOLUTE_REF, 4, new_block, 14, 14);
279 E : EXPECT_EQ(expected_references, new_block->references());
280 :
281 : // Validate the new block's referrers.
282 E : Block::ReferrerSet expected_referrers;
283 E : expected_referrers.insert(Referrer(other, 0));
284 E : expected_referrers.insert(Referrer(new_block, 6));
285 E : expected_referrers.insert(Referrer(new_block, 8));
286 E : expected_referrers.insert(Referrer(new_block, 34));
287 E : expected_referrers.insert(Referrer(new_block, 36));
288 E : expected_referrers.insert(Referrer(new_block, 40));
289 E : expected_referrers.insert(Referrer(new_block, 44));
290 E : EXPECT_EQ(expected_referrers, new_block->referrers());
291 :
292 : // Validate the references of the other block.
293 E : Block::ReferenceMap expected_other_references;
294 : expected_other_references[0] = Reference(
295 E : BlockGraph::ABSOLUTE_REF, 4, new_block, 0, 0);
296 E : EXPECT_EQ(expected_other_references, other->references());
297 :
298 : // Validate the referrers of the other block.
299 E : Block::ReferrerSet expected_other_referrers;
300 E : expected_other_referrers.insert(Referrer(new_block, 1));
301 E : EXPECT_EQ(expected_other_referrers, other->referrers());
302 :
303 : // Validate the labels.
304 E : BlockGraph::Block::LabelMap expected_labels;
305 E : expected_labels.insert(std::make_pair(0, label_1));
306 E : expected_labels.insert(std::make_pair(9, label_2));
307 E : expected_labels.insert(std::make_pair(14, label_3));
308 E : expected_labels.insert(std::make_pair(17, label_4));
309 E : expected_labels.insert(std::make_pair(36, label_5));
310 E : EXPECT_EQ(expected_labels, new_block->labels());
311 :
312 : // Validate that there is a single byte NOP at position 35, just prior to the
313 : // table.
314 E : EXPECT_EQ(0x90, new_block->data()[35]);
315 E : }
316 :
317 E : TEST_F(BlockBuilderTest, ShortLayout) {
318 : // This is the block structure we construct. If either of BB1 or BB2's
319 : // successors is manifested too long, they will both have to grow.
320 : // 0 [BB1] 62 bytes
321 : // 62 jeq BB4 (+127 bytes).
322 : // 64 [BB2] 62 bytes
323 : // 126 jmp BB1 (-128 bytes).
324 : // 128 [BB3] 63 bytes.
325 : // 191 [BB4] 1 byte.
326 E : Block* new_block = CreateLayout(62, 62, 63, 1);
327 E : ASSERT_TRUE(new_block != NULL);
328 :
329 E : EXPECT_EQ(192, new_block->size());
330 E : Block::ReferenceMap expected_refs;
331 : expected_refs.insert(
332 : std::make_pair(63,
333 : Reference(BlockGraph::PC_RELATIVE_REF,
334 E : 1, new_block, 191, 191)));
335 : expected_refs.insert(
336 : std::make_pair(127,
337 : Reference(BlockGraph::PC_RELATIVE_REF,
338 E : 1, new_block, 0, 0)));
339 E : EXPECT_EQ(expected_refs, new_block->references());
340 E : }
341 :
342 E : TEST_F(BlockBuilderTest, OutofReachBranchLayout) {
343 : // 54 + 72 + 2 = 128 - the BB1->BB4 branch is just out of reach.
344 E : Block* new_block = CreateLayout(62, 54, 72, 1);
345 E : ASSERT_TRUE(new_block != NULL);
346 :
347 : size_t expected_size = 62 +
348 : core::AssemblerImpl::kLongBranchSize +
349 : 54 +
350 : core::AssemblerImpl::kShortJumpSize +
351 : 72 +
352 E : 1;
353 E : EXPECT_EQ(expected_size, new_block->size());
354 E : Block::ReferenceMap expected_refs;
355 : expected_refs.insert(
356 : std::make_pair(62 + core::AssemblerImpl::kLongBranchOpcodeSize,
357 : Reference(BlockGraph::PC_RELATIVE_REF,
358 : 4,
359 : new_block,
360 : expected_size - 1,
361 E : expected_size - 1)));
362 : size_t succ_location = 62 +
363 : core::AssemblerImpl::kLongBranchSize +
364 : 54 +
365 E : core::AssemblerImpl::kShortJumpOpcodeSize;
366 : expected_refs.insert(
367 : std::make_pair(succ_location,
368 : Reference(BlockGraph::PC_RELATIVE_REF,
369 E : 1, new_block, 0, 0)));
370 E : EXPECT_EQ(expected_refs, new_block->references());
371 E : }
372 :
373 E : TEST_F(BlockBuilderTest, OutofReachJmpLayout) {
374 : // 0 - (62 + 2 + 63 + 2) = -129, the jump from BB2->BB1 is just out of reach.
375 E : Block* new_block = CreateLayout(62, 63, 55, 1);
376 E : ASSERT_TRUE(new_block != NULL);
377 :
378 : size_t expected_size = 62 +
379 : core::AssemblerImpl::kShortBranchSize+
380 : 63 +
381 : core::AssemblerImpl::kLongJumpSize+
382 : 55 +
383 E : 1;
384 E : EXPECT_EQ(expected_size, new_block->size());
385 E : Block::ReferenceMap expected_refs;
386 : expected_refs.insert(
387 : std::make_pair(62 + core::AssemblerImpl::kShortBranchOpcodeSize,
388 : Reference(BlockGraph::PC_RELATIVE_REF,
389 : 1,
390 : new_block,
391 : expected_size - 1,
392 E : expected_size - 1)));
393 : size_t succ_location = 62 +
394 : core::AssemblerImpl::kShortBranchSize +
395 : 63 +
396 E : core::AssemblerImpl::kLongJumpOpcodeSize;
397 : expected_refs.insert(
398 : std::make_pair(succ_location,
399 : Reference(BlockGraph::PC_RELATIVE_REF,
400 E : 4, new_block, 0, 0)));
401 E : EXPECT_EQ(expected_refs, new_block->references());
402 E : }
403 :
404 E : TEST_F(BlockBuilderTest, MergeAssemblesSourceRangesCorrectly) {
405 E : ASSERT_NO_FATAL_FAILURE(InitBlockGraph());
406 E : ASSERT_NO_FATAL_FAILURE(InitBasicBlockSubGraph());
407 :
408 : // Test that re-assembling this decomposition produces an unbroken,
409 : // identical source range as the original block had.
410 : BlockGraph::Block::SourceRanges expected_source_ranges(
411 E : assembly_func_->source_ranges());
412 :
413 E : BlockBuilder builder(&block_graph_);
414 E : ASSERT_TRUE(builder.Merge(&subgraph_));
415 :
416 E : ASSERT_EQ(1, builder.new_blocks().size());
417 :
418 E : BlockGraph::Block* new_block = builder.new_blocks()[0];
419 E : ASSERT_EQ(expected_source_ranges, new_block->source_ranges());
420 E : }
421 :
422 E : TEST_F(BlockBuilderTest, LabelsPastEndAreDropped) {
423 E : ASSERT_NO_FATAL_FAILURE(InitBasicBlockSubGraphWithLabelPastEnd());
424 :
425 E : BlockBuilder builder(&block_graph_);
426 E : ASSERT_TRUE(builder.Merge(&subgraph_));
427 :
428 E : ASSERT_EQ(1u, builder.new_blocks().size());
429 :
430 E : BlockGraph::Block* new_block = builder.new_blocks()[0];
431 E : ASSERT_EQ(1u, new_block->labels().size());
432 E : ASSERT_EQ(0, new_block->labels().begin()->first);
433 : ASSERT_EQ(BlockGraph::CODE_LABEL | BlockGraph::DEBUG_START_LABEL,
434 E : new_block->labels().begin()->second.attributes());
435 :
436 : // TODO(chrisha): When we properly handle labels of this type, ensure that
437 : // they make it through the block building process. For now we simply
438 : // ensure that it *doesn't* exist.
439 E : }
440 :
441 : } // namespace block_graph
|