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 basic block disassembler.
16 :
17 : #include "syzygy/block_graph/basic_block_decomposer.h"
18 :
19 : #include <algorithm>
20 : #include <vector>
21 :
22 : #include "base/bind.h"
23 : #include "base/command_line.h"
24 : #include "base/file_util.h"
25 : #include "base/memory/scoped_ptr.h"
26 : #include "gmock/gmock.h"
27 : #include "gtest/gtest.h"
28 : #include "syzygy/block_graph/basic_block_test_util.h"
29 : #include "syzygy/core/address.h"
30 : #include "syzygy/core/unittest_util.h"
31 :
32 : #include "mnemonics.h" // NOLINT
33 :
34 : namespace block_graph {
35 :
36 : namespace {
37 :
38 : using block_graph::BasicBlock;
39 : using block_graph::BasicBlockSubGraph;
40 : using block_graph::BlockGraph;
41 : using block_graph::BlockGraphSerializer;
42 : using block_graph::Successor;
43 : using core::AbsoluteAddress;
44 : using core::Disassembler;
45 : using testing::_;
46 : using testing::BasicBlockTest;
47 : using testing::Return;
48 :
49 : typedef BlockGraph::Block Block;
50 : typedef BlockGraph::Offset Offset;
51 : typedef BlockGraph::Reference Reference;
52 : typedef BlockGraph::Size Size;
53 :
54 : // A helper to count basic blocks of a given type.
55 : size_t CountBasicBlocks(const BasicBlockSubGraph& subgraph,
56 E : BasicBlock::BasicBlockType type) {
57 E : size_t counter = 0;
58 : BasicBlockSubGraph::BBCollection::const_iterator bb_it =
59 E : subgraph.basic_blocks().begin();
60 E : for (; bb_it != subgraph.basic_blocks().end(); ++bb_it) {
61 E : if ((*bb_it)->type() == type)
62 E : ++counter;
63 E : }
64 :
65 E : return counter;
66 E : }
67 :
68 : // A helper to count padding basic blocks of a given type.
69 : size_t CountPaddingBasicBlocks(const BasicBlockSubGraph& subgraph,
70 E : BasicBlock::BasicBlockType type) {
71 E : size_t counter = 0;
72 : BasicBlockSubGraph::BBCollection::const_iterator bb_it =
73 E : subgraph.basic_blocks().begin();
74 E : for (; bb_it != subgraph.basic_blocks().end(); ++bb_it) {
75 E : if ((*bb_it)->type() == type && (*bb_it)->is_padding())
76 E : ++counter;
77 E : }
78 :
79 E : return counter;
80 E : }
81 :
82 : // A helper comparator to that returns true if lhs and rhs are not adjacent
83 : // and in order.
84 E : bool HasGapOrIsOutOfOrder(const BasicBlock* lhs, const BasicBlock* rhs) {
85 : typedef BasicBlock::Size Size;
86 :
87 E : Offset lhs_end = lhs->offset();
88 :
89 E : const BasicCodeBlock* lhs_code = BasicCodeBlock::Cast(lhs);
90 E : if (lhs_code != NULL) {
91 E : lhs_end += lhs_code->GetInstructionSize();
92 :
93 E : BasicBlock::Successors::const_iterator it(lhs_code->successors().begin());
94 E : for (; it != lhs_code->successors().end(); ++it) {
95 E : lhs_end += it->instruction_size();
96 E : }
97 : }
98 E : const BasicDataBlock* lhs_data = BasicDataBlock::Cast(lhs);
99 E : if (lhs_data != NULL)
100 E : lhs_end += lhs_data->size();
101 :
102 E : return lhs_end != rhs->offset();
103 E : }
104 :
105 : // A test fixture which generates a block-graph to use for basic-block
106 : // related testing.
107 : // See: basic_block_assembly_func.asm
108 : class BasicBlockDecomposerTest : public BasicBlockTest {
109 : public:
110 E : virtual void SetUp() OVERRIDE {
111 E : BasicBlockTest::SetUp();
112 E : ASSERT_NO_FATAL_FAILURE(InitBlockGraph());
113 E : }
114 : };
115 :
116 : }
117 :
118 E : TEST_F(BasicBlockDecomposerTest, Decompose) {
119 E : ASSERT_NO_FATAL_FAILURE(InitBasicBlockSubGraph());
120 :
121 : // Ensure we have the expected number and types of blocks.
122 E : ASSERT_EQ(kNumBasicBlocks, subgraph_.basic_blocks().size());
123 : ASSERT_EQ(kNumCodeBasicBlocks,
124 E : CountBasicBlocks(subgraph_, BasicBlock::BASIC_CODE_BLOCK));
125 : ASSERT_EQ(kNumDataBasicBlocks,
126 E : CountBasicBlocks(subgraph_, BasicBlock::BASIC_DATA_BLOCK));
127 : ASSERT_EQ(kNumCodePaddingBasicBlocks,
128 E : CountPaddingBasicBlocks(subgraph_, BasicBlock::BASIC_CODE_BLOCK));
129 : ASSERT_EQ(kNumDataPaddingBasicBlocks,
130 E : CountPaddingBasicBlocks(subgraph_, BasicBlock::BASIC_DATA_BLOCK));
131 :
132 : // There should be no gaps and all of the blocks should be used.
133 E : ASSERT_EQ(1U, subgraph_.block_descriptions().size());
134 : const BasicBlockSubGraph::BlockDescription& desc =
135 E : subgraph_.block_descriptions().back();
136 E : EXPECT_EQ(kNumBasicBlocks, desc.basic_block_order.size());
137 : EXPECT_TRUE(
138 : std::adjacent_find(
139 : desc.basic_block_order.begin(),
140 : desc.basic_block_order.end(),
141 E : &HasGapOrIsOutOfOrder) == desc.basic_block_order.end());
142 :
143 E : BasicBlockSubGraph::ReachabilityMap rm;
144 E : subgraph_.GetReachabilityMap(&rm);
145 :
146 : // Basic-block 0 - assembly_func.
147 E : ASSERT_TRUE(BasicBlockSubGraph::IsReachable(rm, bbs_[0]));
148 E : ASSERT_FALSE(bbs_[0]->is_padding());
149 E : ASSERT_EQ(BasicBlock::BASIC_CODE_BLOCK, bbs_[0]->type());
150 E : BasicCodeBlock* bb0 = BasicCodeBlock::Cast(bbs_[0]);
151 E : ASSERT_TRUE(bb0 != NULL);
152 E : ASSERT_EQ(4u, bb0->instructions().size());
153 E : ASSERT_EQ(0u, bb0->successors().size());
154 : BasicBlock::Instructions::const_iterator inst_iter =
155 E : bb0->instructions().begin();
156 E : std::advance(inst_iter, 2);
157 E : ASSERT_EQ(1u, inst_iter->references().size());
158 E : ASSERT_EQ(bbs_[9], inst_iter->references().begin()->second.basic_block());
159 E : std::advance(inst_iter, 1);
160 E : ASSERT_EQ(1u, inst_iter->references().size());
161 E : ASSERT_EQ(bbs_[8], inst_iter->references().begin()->second.basic_block());
162 E : ASSERT_EQ(1u, bbs_[0]->alignment());
163 :
164 : // Basic-block 1 - unreachable-label.
165 E : ASSERT_FALSE(BasicBlockSubGraph::IsReachable(rm, bbs_[1]));
166 E : ASSERT_TRUE(bbs_[1]->is_padding());
167 E : ASSERT_EQ(BasicBlock::BASIC_CODE_BLOCK, bbs_[1]->type());
168 E : BasicCodeBlock* bb1 = BasicCodeBlock::Cast(bbs_[1]);
169 E : ASSERT_EQ(1u, bb1->instructions().size());
170 E : ASSERT_EQ(1u, bb1->successors().size());;
171 : ASSERT_EQ(bbs_[2],
172 E : bb1->successors().front().reference().basic_block());
173 E : ASSERT_EQ(1u, bb1->alignment());
174 :
175 : // Basic-block 2 - case_0.
176 E : ASSERT_TRUE(BasicBlockSubGraph::IsReachable(rm, bbs_[2]));
177 E : ASSERT_FALSE(bbs_[2]->is_padding());
178 E : ASSERT_EQ(BasicBlock::BASIC_CODE_BLOCK, bbs_[2]->type());
179 E : BasicCodeBlock* bb2 = BasicCodeBlock::Cast(bbs_[2]);
180 E : ASSERT_TRUE(bb2 != NULL);
181 E : ASSERT_EQ(2u, bb2->instructions().size());
182 E : ASSERT_EQ(1u, bb2->successors().size());;
183 E : ASSERT_EQ(bbs_[3], bb2->successors().front().reference().basic_block());
184 E : ASSERT_EQ(1u, bbs_[2]->alignment());
185 :
186 : // Basic-block 3 - sub eax to jnz.
187 E : ASSERT_TRUE(BasicBlockSubGraph::IsReachable(rm, bbs_[3]));
188 E : ASSERT_FALSE(bbs_[3]->is_padding());
189 E : ASSERT_EQ(BasicBlock::BASIC_CODE_BLOCK, bbs_[3]->type());
190 E : BasicCodeBlock* bb3 = BasicCodeBlock::Cast(bbs_[3]);
191 E : ASSERT_TRUE(bb3 != NULL);
192 E : ASSERT_EQ(1u, bb3->instructions().size());
193 E : ASSERT_EQ(2u, bb3->successors().size());;
194 E : ASSERT_EQ(bb3, bb3->successors().front().reference().basic_block());
195 E : ASSERT_EQ(bbs_[4], bb3->successors().back().reference().basic_block());
196 E : ASSERT_EQ(1u, bbs_[3]->alignment());
197 :
198 : // Basic-block 4 - ret.
199 E : ASSERT_TRUE(BasicBlockSubGraph::IsReachable(rm, bbs_[4]));
200 E : ASSERT_FALSE(bbs_[4]->is_padding());
201 E : ASSERT_EQ(BasicBlock::BASIC_CODE_BLOCK, bbs_[4]->type());
202 E : BasicCodeBlock* bb4 = BasicCodeBlock::Cast(bbs_[4]);
203 E : ASSERT_TRUE(bb4 != NULL);
204 E : ASSERT_EQ(1u, bb4->instructions().size());
205 E : ASSERT_EQ(0u, bb4->successors().size());;
206 E : ASSERT_EQ(1u, bbs_[4]->alignment());
207 :
208 : // Basic-block 5 - case_1.
209 E : ASSERT_TRUE(BasicBlockSubGraph::IsReachable(rm, bbs_[5]));
210 E : ASSERT_FALSE(bbs_[5]->is_padding());
211 E : ASSERT_EQ(BasicBlock::BASIC_CODE_BLOCK, bbs_[5]->type());
212 E : BasicCodeBlock* bb5 = BasicCodeBlock::Cast(bbs_[5]);
213 E : ASSERT_TRUE(bb5 != NULL);
214 E : ASSERT_EQ(1u, bb5->instructions().size());
215 : ASSERT_EQ(
216 : func1_,
217 E : bb5->instructions().front().references().begin()->second.block());
218 E : ASSERT_EQ(1u, bb5->successors().size());
219 E : ASSERT_EQ(bbs_[6], bb5->successors().front().reference().basic_block());
220 E : ASSERT_EQ(1u, bbs_[5]->alignment());
221 :
222 : // Basic-block 6 - case_default.
223 E : ASSERT_TRUE(BasicBlockSubGraph::IsReachable(rm, bbs_[6]));
224 E : ASSERT_FALSE(bbs_[6]->is_padding());
225 E : ASSERT_EQ(BasicBlock::BASIC_CODE_BLOCK, bbs_[6]->type());
226 E : BasicCodeBlock* bb6 = BasicCodeBlock::Cast(bbs_[6]);
227 E : ASSERT_TRUE(bb6 != NULL);
228 E : ASSERT_EQ(2u, bb6->instructions().size());
229 : ASSERT_EQ(
230 : func2_,
231 E : bb6->instructions().back().references().begin()->second.block());
232 E : ASSERT_EQ(0u, bb6->successors().size());
233 E : ASSERT_EQ(1u, bbs_[6]->alignment());
234 :
235 : // Basic-block 7 - interrupt_label.
236 E : ASSERT_FALSE(BasicBlockSubGraph::IsReachable(rm, bbs_[7]));
237 E : ASSERT_TRUE(bbs_[7]->is_padding());
238 E : ASSERT_EQ(BasicBlock::BASIC_CODE_BLOCK, bbs_[7]->type());
239 E : BasicCodeBlock* bb7 = BasicCodeBlock::Cast(bbs_[7]);
240 E : ASSERT_TRUE(bb7 != NULL);
241 E : ASSERT_EQ(3u, bb7->instructions().size());
242 E : ASSERT_EQ(0u, bb7->successors().size());
243 E : ASSERT_EQ(1u, bbs_[7]->alignment());
244 :
245 : // Basic-block 8 - jump_table.
246 E : ASSERT_TRUE(BasicBlockSubGraph::IsReachable(rm, bbs_[8]));
247 E : ASSERT_FALSE(bbs_[8]->is_padding());
248 E : ASSERT_EQ(BasicBlock::BASIC_DATA_BLOCK, bbs_[8]->type());
249 E : BasicDataBlock* bb8 = BasicDataBlock::Cast(bbs_[8]);
250 E : ASSERT_TRUE(bb8 != NULL);
251 E : ASSERT_EQ(3 * Reference::kMaximumSize, bb8->size());
252 E : ASSERT_EQ(3u, bb8->references().size());
253 E : ASSERT_EQ(4u, bbs_[8]->alignment());
254 :
255 : // Basic-block 9 - case_table.
256 E : ASSERT_TRUE(BasicBlockSubGraph::IsReachable(rm, bbs_[9]));
257 E : ASSERT_FALSE(bbs_[9]->is_padding());
258 E : ASSERT_EQ(BasicBlock::BASIC_DATA_BLOCK, bbs_[9]->type());
259 E : BasicDataBlock* bb9 = BasicDataBlock::Cast(bbs_[9]);
260 E : ASSERT_TRUE(bb9 != NULL);
261 E : ASSERT_EQ(256, bb9->size());
262 E : ASSERT_EQ(0u, bb9->references().size());
263 E : ASSERT_EQ(4u, bbs_[9]->alignment());
264 :
265 : // Validate all source ranges.
266 E : core::RelativeAddress next_addr(start_addr_);
267 E : for (size_t i = 0; i < bbs_.size(); ++i) {
268 E : const BasicCodeBlock* code_block = BasicCodeBlock::Cast(bbs_[i]);
269 E : const BasicDataBlock* data_block = BasicDataBlock::Cast(bbs_[i]);
270 :
271 E : if (code_block != NULL) {
272 E : ASSERT_TRUE(data_block == NULL);
273 :
274 : BasicBlock::Instructions::const_iterator instr_it =
275 E : code_block->instructions().begin();
276 E : for (; instr_it != code_block->instructions().end(); ++instr_it) {
277 E : const Instruction& instr = *instr_it;
278 E : ASSERT_EQ(next_addr, instr.source_range().start());
279 E : ASSERT_EQ(instr.size(), instr.source_range().size());
280 :
281 E : next_addr += instr.size();
282 E : }
283 :
284 : BasicBlock::Successors::const_iterator succ_it =
285 E : code_block->successors().begin();
286 E : for (; succ_it != code_block->successors().end(); ++succ_it) {
287 E : const Successor& succ = *succ_it;
288 E : if (succ.source_range().size() != 0) {
289 E : ASSERT_EQ(next_addr, succ.source_range().start());
290 E : ASSERT_EQ(succ.instruction_size(), succ.source_range().size());
291 E : } else {
292 E : ASSERT_EQ(0, succ.instruction_size());
293 : }
294 :
295 E : next_addr += succ.instruction_size();
296 E : }
297 : }
298 :
299 E : if (data_block != NULL) {
300 E : ASSERT_TRUE(code_block == NULL);
301 E : ASSERT_TRUE(data_block->type() == BasicBlock::BASIC_DATA_BLOCK);
302 E : ASSERT_EQ(next_addr, data_block->source_range().start());
303 E : ASSERT_EQ(data_block->size(), data_block->source_range().size());
304 :
305 E : next_addr += data_block->size();
306 : }
307 E : }
308 E : }
309 :
310 : } // namespace block_graph
|