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 BasicBlockSubGraph.
16 :
17 : #include "syzygy/block_graph/basic_block_subgraph.h"
18 :
19 : #include "gmock/gmock.h"
20 : #include "gtest/gtest.h"
21 : #include "syzygy/assm/assembler.h"
22 : #include "syzygy/block_graph/basic_block.h"
23 : #include "syzygy/block_graph/basic_block_assembler.h"
24 : #include "syzygy/block_graph/block_graph.h"
25 :
26 : namespace block_graph {
27 :
28 : namespace {
29 :
30 : using block_graph::BasicBlock;
31 : using block_graph::BasicBlockReference;
32 : using block_graph::BasicBlockReferrer;
33 : using block_graph::BlockGraph;
34 : using block_graph::Instruction;
35 : using block_graph::Successor;
36 :
37 : typedef BasicBlockSubGraph::BlockDescription BlockDescription;
38 : typedef BlockGraph::Reference Reference;
39 :
40 : // Some handy constants.
41 : const size_t kDataSize = 32;
42 : const uint8 kData[kDataSize] = {0};
43 :
44 : // A derived class to expose protected members for unit-testing.
45 : class TestBasicBlockSubGraph : public BasicBlockSubGraph {
46 : public:
47 : using BasicBlockSubGraph::HasValidReferrers;
48 : using BasicBlockSubGraph::HasValidSuccessors;
49 : using BasicBlockSubGraph::MapsBasicBlocksToAtMostOneDescription;
50 : };
51 :
52 : } // namespace
53 :
54 E : TEST(BasicBlockSubGraphTest, AddBasicBlock) {
55 E : BlockGraph block_graph;
56 : BlockGraph::Block* block =
57 E : block_graph.AddBlock(BlockGraph::CODE_BLOCK, 0, "dummy");
58 E : BasicBlockSubGraph subgraph;
59 E : subgraph.set_original_block(block);
60 E : block->set_size(kDataSize);
61 E : block->SetData(kData, kDataSize);
62 :
63 : // Add a basic data block.
64 E : BasicDataBlock* bb1 = subgraph.AddBasicDataBlock("bb1", kDataSize, kData);
65 E : ASSERT_FALSE(bb1 == NULL);
66 E : EXPECT_EQ(0U, bb1->id());
67 E : EXPECT_EQ("bb1", bb1->name());
68 E : EXPECT_EQ(BasicBlock::BASIC_DATA_BLOCK, bb1->type());
69 E : EXPECT_EQ(kDataSize, bb1->size());
70 E : EXPECT_EQ(kData, bb1->data());
71 E : EXPECT_EQ(BasicBlock::kNoOffset, bb1->offset());
72 E : EXPECT_TRUE(BasicCodeBlock::Cast(bb1) == NULL);
73 E : EXPECT_EQ(bb1, BasicDataBlock::Cast(bb1));
74 E : EXPECT_TRUE(BasicEndBlock::Cast(bb1) == NULL);
75 :
76 : // Add one that overlaps.
77 : BasicDataBlock* bb2 =
78 E : subgraph.AddBasicDataBlock("bb2", kDataSize / 2, kData + kDataSize / 2);
79 E : ASSERT_FALSE(bb2 == NULL);
80 E : EXPECT_EQ(1U, bb2->id());
81 E : EXPECT_EQ("bb2", bb2->name());
82 E : EXPECT_EQ(BasicBlock::BASIC_DATA_BLOCK, bb2->type());
83 E : EXPECT_EQ(kDataSize / 2, bb2->size());
84 E : EXPECT_EQ(kData + kDataSize / 2, bb2->data());
85 E : EXPECT_EQ(BasicBlock::kNoOffset, bb2->offset());
86 E : EXPECT_TRUE(BasicCodeBlock::Cast(bb2) == NULL);
87 E : EXPECT_EQ(bb2, BasicDataBlock::Cast(bb2));
88 E : EXPECT_TRUE(BasicEndBlock::Cast(bb2) == NULL);
89 :
90 : // Add a code block.
91 E : BasicCodeBlock* bb3 = subgraph.AddBasicCodeBlock("bb3");
92 E : ASSERT_FALSE(bb3 == NULL);
93 E : EXPECT_EQ(2U, bb3->id());
94 E : EXPECT_EQ("bb3", bb3->name());
95 E : EXPECT_EQ(bb3, BasicCodeBlock::Cast(bb3));
96 E : EXPECT_TRUE(BasicDataBlock::Cast(bb3) == NULL);
97 E : EXPECT_TRUE(BasicEndBlock::Cast(bb3) == NULL);
98 :
99 : // Add an end block.
100 E : BasicEndBlock* bb4 = subgraph.AddBasicEndBlock();
101 E : ASSERT_FALSE(bb4 == NULL);
102 E : EXPECT_EQ(3u, bb4->id());
103 E : EXPECT_EQ(0u, bb4->size());
104 E : EXPECT_TRUE(BasicCodeBlock::Cast(bb4) == NULL);
105 E : EXPECT_TRUE(BasicDataBlock::Cast(bb4) == NULL);
106 E : ASSERT_EQ(bb4, BasicEndBlock::Cast(bb4));
107 :
108 : // And they are not the same basic-block.
109 E : EXPECT_NE(static_cast<BasicBlock*>(bb1), static_cast<BasicBlock*>(bb2));
110 E : EXPECT_NE(static_cast<BasicBlock*>(bb1), static_cast<BasicBlock*>(bb3));
111 E : EXPECT_NE(static_cast<BasicBlock*>(bb1), static_cast<BasicBlock*>(bb4));
112 E : EXPECT_NE(static_cast<BasicBlock*>(bb2), static_cast<BasicBlock*>(bb3));
113 E : EXPECT_NE(static_cast<BasicBlock*>(bb2), static_cast<BasicBlock*>(bb4));
114 :
115 : // Check BBCollection ordering.
116 E : const BasicBlockSubGraph::BBCollection& blocks = subgraph.basic_blocks();
117 E : BasicBlockSubGraph::BBCollection::const_iterator it = blocks.begin();
118 E : BasicBlockSubGraph::BlockId current_id = (*it)->id();
119 E : ++it;
120 E : for (; it != blocks.end(); ++it) {
121 E : EXPECT_LT(current_id, (*it)->id());
122 E : current_id = (*it)->id();
123 E : }
124 E : }
125 :
126 E : TEST(BasicBlockSubGraphTest, AddBlockDescription) {
127 E : TestBasicBlockSubGraph subgraph;
128 : BlockDescription* b1 = subgraph.AddBlockDescription(
129 E : "b1", "b1.obj", BlockGraph::CODE_BLOCK, 7, 2, 42);
130 E : ASSERT_FALSE(b1 == NULL);
131 E : EXPECT_EQ("b1", b1->name);
132 E : EXPECT_EQ(BlockGraph::CODE_BLOCK, b1->type);
133 E : EXPECT_EQ(7, b1->section);
134 E : EXPECT_EQ(2, b1->alignment);
135 E : EXPECT_EQ(42, b1->attributes);
136 E : EXPECT_TRUE(b1->basic_block_order.empty());
137 E : }
138 :
139 E : TEST(BasicBlockSubGraphTest, MapsBasicBlocksToAtMostOneDescription) {
140 E : TestBasicBlockSubGraph subgraph;
141 :
142 : // Add three basic code blocks.
143 E : BasicBlock* bb1 = subgraph.AddBasicCodeBlock("bb1");
144 E : ASSERT_FALSE(bb1 == NULL);
145 E : BasicBlock* bb2 = subgraph.AddBasicCodeBlock("bb2");
146 E : ASSERT_FALSE(bb2 == NULL);
147 E : BasicBlock* bb3 = subgraph.AddBasicCodeBlock("bb3");
148 E : ASSERT_FALSE(bb3 == NULL);
149 :
150 : // They should all be different blocks.
151 E : ASSERT_FALSE(bb1 == bb2);
152 E : ASSERT_FALSE(bb2 == bb3);
153 E : ASSERT_FALSE(bb1 == bb3);
154 :
155 : // Add a block description for a mythical b1.
156 : BlockDescription* b1 = subgraph.AddBlockDescription(
157 E : "b1", "b1.obj", BlockGraph::CODE_BLOCK, 0, 1, 0);
158 E : ASSERT_FALSE(b1 == NULL);
159 :
160 : // Add a block description for a mythical b2.
161 : BlockDescription* b2 = subgraph.AddBlockDescription(
162 E : "b2", "b2.obj", BlockGraph::CODE_BLOCK, 0, 1, 0);
163 E : ASSERT_FALSE(b2 == NULL);
164 :
165 : // There are no blocks assigned twice (bb1 and bb2 are in separate blocks).
166 E : ASSERT_TRUE(subgraph.MapsBasicBlocksToAtMostOneDescription());
167 :
168 : // Adding bb3 to b1 is still valid.
169 E : b1->basic_block_order.push_back(bb3);
170 E : ASSERT_TRUE(subgraph.MapsBasicBlocksToAtMostOneDescription());
171 :
172 : // But adding bb3 to b2, as well, is no longer valid.
173 E : b2->basic_block_order.push_back(bb3);
174 E : ASSERT_FALSE(subgraph.MapsBasicBlocksToAtMostOneDescription());
175 E : }
176 :
177 E : TEST(BasicBlockSubGraphTest, GetReachabilityMap) {
178 E : BlockGraph block_graph;
179 : BlockGraph::Block* external_block =
180 E : block_graph.AddBlock(BlockGraph::CODE_BLOCK, 0, "dummy");
181 E : BasicBlockSubGraph subgraph;
182 : static const uint8 kData[Reference::kMaximumSize] = { 0 };
183 :
184 : // Create basic-blocks.
185 E : BasicCodeBlock* bb1 = subgraph.AddBasicCodeBlock("bb1");
186 E : ASSERT_FALSE(bb1 == NULL);
187 E : BasicCodeBlock* bb2 = subgraph.AddBasicCodeBlock("bb2");
188 E : ASSERT_FALSE(bb2 == NULL);
189 E : BasicCodeBlock* bb3 = subgraph.AddBasicCodeBlock("bb3");
190 E : ASSERT_FALSE(bb3 == NULL);
191 E : BasicCodeBlock* bb4 = subgraph.AddBasicCodeBlock("bb4");
192 E : ASSERT_FALSE(bb4 == NULL);
193 : BasicDataBlock* data = subgraph.AddBasicDataBlock(
194 E : "data", sizeof(kData), kData);
195 E : ASSERT_FALSE(data == NULL);
196 :
197 : // Setup references.
198 : static const uint8 kJmp[] = { 0xFF, 0x24, 0x8D, 0xCA, 0xFE, 0xBA, 0xBE };
199 : static const uint8 kRet[] = { 0xC3 };
200 E : Instruction jmp;
201 E : ASSERT_TRUE(Instruction::FromBuffer(kJmp, sizeof(kJmp), &jmp));
202 E : Instruction ret;
203 E : ASSERT_TRUE(Instruction::FromBuffer(kRet, sizeof(kRet), &ret));
204 E : bb1->referrers().insert(BasicBlockReferrer(external_block, 0));
205 E : bb1->instructions().push_back(jmp);
206 : bb1->instructions().back().SetReference(
207 : 3, BasicBlockReference(BlockGraph::RELATIVE_REF,
208 : BlockGraph::Reference::kMaximumSize,
209 E : data));
210 : data->SetReference(0, BasicBlockReference(BlockGraph::RELATIVE_REF,
211 : BlockGraph::Reference::kMaximumSize,
212 E : bb2));
213 : bb2->successors().push_back(
214 : Successor(Successor::kConditionTrue,
215 : BasicBlockReference(BlockGraph::RELATIVE_REF,
216 : BlockGraph::Reference::kMaximumSize,
217 : bb3),
218 E : 0));
219 E : bb3->instructions().push_back(ret);
220 :
221 : // Check reachability.
222 E : BasicBlockSubGraph::ReachabilityMap expected_rm;
223 E : expected_rm.insert(std::make_pair(bb1, true));
224 E : expected_rm.insert(std::make_pair(bb2, true));
225 E : expected_rm.insert(std::make_pair(bb3, true));
226 E : expected_rm.insert(std::make_pair(bb4, false));
227 E : expected_rm.insert(std::make_pair(data, true));
228 :
229 E : BasicBlockSubGraph::ReachabilityMap actual_rm;
230 E : subgraph.GetReachabilityMap(&actual_rm);
231 E : EXPECT_THAT(actual_rm, testing::ContainerEq(expected_rm));
232 E : }
233 :
234 E : TEST(BasicBlockSubGraphTest, HasValidSuccessors) {
235 E : BlockGraph block_graph;
236 : BlockGraph::Block* external_block =
237 E : block_graph.AddBlock(BlockGraph::CODE_BLOCK, 0, "dummy");
238 E : TestBasicBlockSubGraph subgraph;
239 :
240 E : BasicCodeBlock* bb1 = subgraph.AddBasicCodeBlock("bb1");
241 E : ASSERT_FALSE(bb1 == NULL);
242 E : bb1->referrers().insert(BasicBlockReferrer(external_block, 0));
243 :
244 E : BasicCodeBlock* bb2 = subgraph.AddBasicCodeBlock("bb2");
245 E : ASSERT_FALSE(bb2 == NULL);
246 :
247 : // Add a block description for a mythical b1.
248 : BlockDescription* b1 = subgraph.AddBlockDescription(
249 E : "b1", "b1.obj", BlockGraph::CODE_BLOCK, 0, 1, 0);
250 E : ASSERT_FALSE(b1 == NULL);
251 E : b1->basic_block_order.push_back(bb1);
252 :
253 : // Add a block description for a mythical b2.
254 : BlockDescription* b2 = subgraph.AddBlockDescription(
255 E : "b2", "b2.obj", BlockGraph::CODE_BLOCK, 0, 1, 0);
256 E : ASSERT_FALSE(b2 == NULL);
257 E : b2->basic_block_order.push_back(bb2);
258 :
259 : // Successors are not valid yet.
260 E : EXPECT_FALSE(subgraph.HasValidSuccessors());
261 :
262 : // Add an unconditional succession from bb1 to bb2.
263 : bb1->successors().push_back(
264 : Successor(Successor::kConditionTrue,
265 : BasicBlockReference(BlockGraph::RELATIVE_REF, 4, bb2),
266 E : 0));
267 :
268 : // Successors are still not valid.
269 E : EXPECT_FALSE(subgraph.HasValidSuccessors());
270 :
271 : // Add half of a conditional succession from bb2 to bb1.
272 : bb2->successors().push_back(
273 : Successor(Successor::kConditionAbove,
274 : BasicBlockReference(BlockGraph::RELATIVE_REF, 4, bb1),
275 E : 0));
276 :
277 : // Successors are still not valid.
278 E : EXPECT_FALSE(subgraph.HasValidSuccessors());
279 :
280 : // Add second conditional succession from bb2 to bb1, but not the inverse
281 : // of the first condition.
282 : bb2->successors().push_back(
283 : Successor(Successor::kConditionAboveOrEqual,
284 : BasicBlockReference(BlockGraph::RELATIVE_REF, 4, bb1),
285 E : 0));
286 :
287 : // Successors are still not valid because the conditions are not inverses.
288 E : EXPECT_FALSE(subgraph.HasValidSuccessors());
289 :
290 : // Remove the bad successor and add a correct secondary successor.
291 E : bb2->successors().pop_back();
292 : bb2->successors().push_back(
293 : Successor(Successor::kConditionBelowOrEqual,
294 : BasicBlockReference(BlockGraph::RELATIVE_REF, 4, bb1),
295 E : 0));
296 :
297 : // Successors are now valid.
298 E : EXPECT_TRUE(subgraph.HasValidSuccessors());
299 E : }
300 :
301 E : TEST(BasicBlockSubGraphTest, HasValidReferrers) {
302 E : BlockGraph block_graph;
303 E : BlockGraph::Block* b1 = block_graph.AddBlock(BlockGraph::DATA_BLOCK, 4, "b1");
304 E : BlockGraph::Block* b2 = block_graph.AddBlock(BlockGraph::DATA_BLOCK, 4, "b2");
305 :
306 E : Reference ref(BlockGraph::ABSOLUTE_REF, 4, b1, 0, 0);
307 E : ASSERT_TRUE(b2->SetReference(0, ref));
308 E : ASSERT_FALSE(b1->referrers().empty());
309 :
310 E : TestBasicBlockSubGraph subgraph;
311 E : subgraph.set_original_block(b1);
312 :
313 E : ASSERT_FALSE(subgraph.HasValidReferrers());
314 :
315 E : BasicDataBlock* bb1 = subgraph.AddBasicDataBlock("bb1", kDataSize, kData);
316 E : ASSERT_FALSE(bb1 == NULL);
317 :
318 : BlockDescription* b1_desc = subgraph.AddBlockDescription(
319 E : "b1_desc", "b1_desc.obj", BlockGraph::DATA_BLOCK, 0, 1, 0);
320 E : ASSERT_FALSE(b1_desc == NULL);
321 E : b1_desc->basic_block_order.push_back(bb1);
322 :
323 E : ASSERT_FALSE(subgraph.HasValidReferrers());
324 :
325 E : bb1->referrers().insert(BasicBlockReferrer(b2, 0));
326 E : ASSERT_TRUE(subgraph.HasValidReferrers());
327 E : }
328 :
329 E : TEST(BasicBlockSubGraphTest, ToString) {
330 E : BlockGraph block_graph;
331 : BlockGraph::Block* block =
332 E : block_graph.AddBlock(BlockGraph::CODE_BLOCK, 0, "dummy");
333 E : BasicBlockSubGraph subgraph;
334 E : subgraph.set_original_block(block);
335 :
336 : BlockDescription* b1 = subgraph.AddBlockDescription(
337 E : "b1", "b1.obj", BlockGraph::CODE_BLOCK, 7, 2, 42);
338 :
339 E : BasicCodeBlock* bb = subgraph.AddBasicCodeBlock("BB");
340 E : b1->basic_block_order.push_back(bb);
341 E : BasicBlockAssembler assm(bb->instructions().begin(), &bb->instructions());
342 E : assm.ret();
343 :
344 E : std::string result;
345 E : bool valid = subgraph.ToString(&result);
346 E : EXPECT_TRUE(valid);
347 E : EXPECT_FALSE(result.empty());
348 E : }
349 :
350 : } // namespace block_graph
|