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(implicit_cast<BasicBlock*>(bb1), implicit_cast<BasicBlock*>(bb2));
110 E : EXPECT_NE(implicit_cast<BasicBlock*>(bb1), implicit_cast<BasicBlock*>(bb3));
111 E : EXPECT_NE(implicit_cast<BasicBlock*>(bb1), implicit_cast<BasicBlock*>(bb4));
112 E : EXPECT_NE(implicit_cast<BasicBlock*>(bb2), implicit_cast<BasicBlock*>(bb3));
113 E : EXPECT_NE(implicit_cast<BasicBlock*>(bb2), implicit_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 E : uint8 data[32] = {0};
142 :
143 : // Add three basic code blocks.
144 E : BasicBlock* bb1 = subgraph.AddBasicCodeBlock("bb1");
145 E : ASSERT_FALSE(bb1 == NULL);
146 E : BasicBlock* bb2 = subgraph.AddBasicCodeBlock("bb2");
147 E : ASSERT_FALSE(bb2 == NULL);
148 E : BasicBlock* bb3 = subgraph.AddBasicCodeBlock("bb3");
149 E : ASSERT_FALSE(bb3 == NULL);
150 :
151 : // They should all be different blocks.
152 E : ASSERT_FALSE(bb1 == bb2);
153 E : ASSERT_FALSE(bb2 == bb3);
154 E : ASSERT_FALSE(bb1 == bb3);
155 :
156 : // Add a block description for a mythical b1.
157 : BlockDescription* b1 = subgraph.AddBlockDescription(
158 E : "b1", "b1.obj", BlockGraph::CODE_BLOCK, 0, 1, 0);
159 E : ASSERT_FALSE(b1 == NULL);
160 :
161 : // Add a block description for a mythical b2.
162 : BlockDescription* b2 = subgraph.AddBlockDescription(
163 E : "b2", "b2.obj", BlockGraph::CODE_BLOCK, 0, 1, 0);
164 E : ASSERT_FALSE(b2 == NULL);
165 :
166 : // There are no blocks assigned twice (bb1 and bb2 are in separate blocks).
167 E : ASSERT_TRUE(subgraph.MapsBasicBlocksToAtMostOneDescription());
168 :
169 : // Adding bb3 to b1 is still valid.
170 E : b1->basic_block_order.push_back(bb3);
171 E : ASSERT_TRUE(subgraph.MapsBasicBlocksToAtMostOneDescription());
172 :
173 : // But adding bb3 to b2, as well, is no longer valid.
174 E : b2->basic_block_order.push_back(bb3);
175 E : ASSERT_FALSE(subgraph.MapsBasicBlocksToAtMostOneDescription());
176 E : }
177 :
178 E : TEST(BasicBlockSubGraphTest, GetReachabilityMap) {
179 E : BlockGraph block_graph;
180 : BlockGraph::Block* external_block =
181 E : block_graph.AddBlock(BlockGraph::CODE_BLOCK, 0, "dummy");
182 E : BasicBlockSubGraph subgraph;
183 : static const uint8 kData[Reference::kMaximumSize] = { 0 };
184 :
185 : // Create basic-blocks.
186 E : BasicCodeBlock* bb1 = subgraph.AddBasicCodeBlock("bb1");
187 E : ASSERT_FALSE(bb1 == NULL);
188 E : BasicCodeBlock* bb2 = subgraph.AddBasicCodeBlock("bb2");
189 E : ASSERT_FALSE(bb2 == NULL);
190 E : BasicCodeBlock* bb3 = subgraph.AddBasicCodeBlock("bb3");
191 E : ASSERT_FALSE(bb3 == NULL);
192 E : BasicCodeBlock* bb4 = subgraph.AddBasicCodeBlock("bb4");
193 E : ASSERT_FALSE(bb4 == NULL);
194 : BasicDataBlock* data = subgraph.AddBasicDataBlock(
195 E : "data", sizeof(kData), kData);
196 E : ASSERT_FALSE(data == NULL);
197 :
198 : // Setup references.
199 : static const uint8 kJmp[] = { 0xFF, 0x24, 0x8D, 0xCA, 0xFE, 0xBA, 0xBE };
200 : static const uint8 kRet[] = { 0xC3 };
201 E : Instruction jmp;
202 E : ASSERT_TRUE(Instruction::FromBuffer(kJmp, sizeof(kJmp), &jmp));
203 E : Instruction ret;
204 E : ASSERT_TRUE(Instruction::FromBuffer(kRet, sizeof(kRet), &ret));
205 E : bb1->referrers().insert(BasicBlockReferrer(external_block, 0));
206 E : bb1->instructions().push_back(jmp);
207 : bb1->instructions().back().SetReference(
208 : 3, BasicBlockReference(BlockGraph::RELATIVE_REF,
209 : BlockGraph::Reference::kMaximumSize,
210 E : data));
211 : data->SetReference(0, BasicBlockReference(BlockGraph::RELATIVE_REF,
212 : BlockGraph::Reference::kMaximumSize,
213 E : bb2));
214 : bb2->successors().push_back(
215 : Successor(Successor::kConditionTrue,
216 : BasicBlockReference(BlockGraph::RELATIVE_REF,
217 : BlockGraph::Reference::kMaximumSize,
218 : bb3),
219 E : 0));
220 E : bb3->instructions().push_back(ret);
221 :
222 : // Check reachability.
223 E : BasicBlockSubGraph::ReachabilityMap expected_rm;
224 E : expected_rm.insert(std::make_pair(bb1, true));
225 E : expected_rm.insert(std::make_pair(bb2, true));
226 E : expected_rm.insert(std::make_pair(bb3, true));
227 E : expected_rm.insert(std::make_pair(bb4, false));
228 E : expected_rm.insert(std::make_pair(data, true));
229 :
230 E : BasicBlockSubGraph::ReachabilityMap actual_rm;
231 E : subgraph.GetReachabilityMap(&actual_rm);
232 E : EXPECT_THAT(actual_rm, testing::ContainerEq(expected_rm));
233 E : }
234 :
235 E : TEST(BasicBlockSubGraphTest, HasValidSuccessors) {
236 E : BlockGraph block_graph;
237 : BlockGraph::Block* external_block =
238 E : block_graph.AddBlock(BlockGraph::CODE_BLOCK, 0, "dummy");
239 E : TestBasicBlockSubGraph subgraph;
240 :
241 E : BasicCodeBlock* bb1 = subgraph.AddBasicCodeBlock("bb1");
242 E : ASSERT_FALSE(bb1 == NULL);
243 E : bb1->referrers().insert(BasicBlockReferrer(external_block, 0));
244 :
245 E : BasicCodeBlock* bb2 = subgraph.AddBasicCodeBlock("bb2");
246 E : ASSERT_FALSE(bb2 == NULL);
247 :
248 : // Add a block description for a mythical b1.
249 : BlockDescription* b1 = subgraph.AddBlockDescription(
250 E : "b1", "b1.obj", BlockGraph::CODE_BLOCK, 0, 1, 0);
251 E : ASSERT_FALSE(b1 == NULL);
252 E : b1->basic_block_order.push_back(bb1);
253 :
254 : // Add a block description for a mythical b2.
255 : BlockDescription* b2 = subgraph.AddBlockDescription(
256 E : "b2", "b2.obj", BlockGraph::CODE_BLOCK, 0, 1, 0);
257 E : ASSERT_FALSE(b2 == NULL);
258 E : b2->basic_block_order.push_back(bb2);
259 :
260 : // Successors are not valid yet.
261 E : EXPECT_FALSE(subgraph.HasValidSuccessors());
262 :
263 : // Add an unconditional succession from bb1 to bb2.
264 : bb1->successors().push_back(
265 : Successor(Successor::kConditionTrue,
266 : BasicBlockReference(BlockGraph::RELATIVE_REF, 4, bb2),
267 E : 0));
268 :
269 : // Successors are still not valid.
270 E : EXPECT_FALSE(subgraph.HasValidSuccessors());
271 :
272 : // Add half of a conditional succession from bb2 to bb1.
273 : bb2->successors().push_back(
274 : Successor(Successor::kConditionAbove,
275 : BasicBlockReference(BlockGraph::RELATIVE_REF, 4, bb1),
276 E : 0));
277 :
278 : // Successors are still not valid.
279 E : EXPECT_FALSE(subgraph.HasValidSuccessors());
280 :
281 : // Add second conditional succession from bb2 to bb1, but not the inverse
282 : // of the first condition.
283 : bb2->successors().push_back(
284 : Successor(Successor::kConditionAboveOrEqual,
285 : BasicBlockReference(BlockGraph::RELATIVE_REF, 4, bb1),
286 E : 0));
287 :
288 : // Successors are still not valid because the conditions are not inverses.
289 E : EXPECT_FALSE(subgraph.HasValidSuccessors());
290 :
291 : // Remove the bad successor and add a correct secondary successor.
292 E : bb2->successors().pop_back();
293 : bb2->successors().push_back(
294 : Successor(Successor::kConditionBelowOrEqual,
295 : BasicBlockReference(BlockGraph::RELATIVE_REF, 4, bb1),
296 E : 0));
297 :
298 : // Successors are now valid.
299 E : EXPECT_TRUE(subgraph.HasValidSuccessors());
300 E : }
301 :
302 E : TEST(BasicBlockSubGraphTest, HasValidReferrers) {
303 E : BlockGraph block_graph;
304 E : BlockGraph::Block* b1 = block_graph.AddBlock(BlockGraph::DATA_BLOCK, 4, "b1");
305 E : BlockGraph::Block* b2 = block_graph.AddBlock(BlockGraph::DATA_BLOCK, 4, "b2");
306 :
307 E : Reference ref(BlockGraph::ABSOLUTE_REF, 4, b1, 0, 0);
308 E : ASSERT_TRUE(b2->SetReference(0, ref));
309 E : ASSERT_FALSE(b1->referrers().empty());
310 :
311 E : TestBasicBlockSubGraph subgraph;
312 E : subgraph.set_original_block(b1);
313 :
314 E : ASSERT_FALSE(subgraph.HasValidReferrers());
315 :
316 E : BasicDataBlock* bb1 = subgraph.AddBasicDataBlock("bb1", kDataSize, kData);
317 E : ASSERT_FALSE(bb1 == NULL);
318 :
319 : BlockDescription* b1_desc = subgraph.AddBlockDescription(
320 E : "b1_desc", "b1_desc.obj", BlockGraph::DATA_BLOCK, 0, 1, 0);
321 E : ASSERT_FALSE(b1_desc == NULL);
322 E : b1_desc->basic_block_order.push_back(bb1);
323 :
324 E : ASSERT_FALSE(subgraph.HasValidReferrers());
325 :
326 E : bb1->referrers().insert(BasicBlockReferrer(b2, 0));
327 E : ASSERT_TRUE(subgraph.HasValidReferrers());
328 E : }
329 :
330 E : TEST(BasicBlockSubGraphTest, ToString) {
331 E : BlockGraph block_graph;
332 : BlockGraph::Block* block =
333 E : block_graph.AddBlock(BlockGraph::CODE_BLOCK, 0, "dummy");
334 E : BasicBlockSubGraph subgraph;
335 E : subgraph.set_original_block(block);
336 :
337 : BlockDescription* b1 = subgraph.AddBlockDescription(
338 E : "b1", "b1.obj", BlockGraph::CODE_BLOCK, 7, 2, 42);
339 :
340 E : BasicCodeBlock* bb = subgraph.AddBasicCodeBlock("BB");
341 E : b1->basic_block_order.push_back(bb);
342 E : BasicBlockAssembler assm(bb->instructions().begin(), &bb->instructions());
343 E : assm.ret();
344 :
345 E : std::string result;
346 E : bool valid = subgraph.ToString(&result);
347 E : EXPECT_TRUE(valid);
348 E : EXPECT_FALSE(result.empty());
349 E : }
350 :
351 : } // namespace block_graph
|