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