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