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