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 : typedef BasicBlockTest BasicBlockDecomposerTest;
109 :
110 : }
111 :
112 E : TEST_F(BasicBlockDecomposerTest, Decompose) {
113 E : ASSERT_NO_FATAL_FAILURE(InitBlockGraph());
114 E : ASSERT_NO_FATAL_FAILURE(InitBasicBlockSubGraph());
115 :
116 : // Ensure we have the expected number and types of blocks.
117 E : ASSERT_EQ(kNumBasicBlocks, subgraph_.basic_blocks().size());
118 : ASSERT_EQ(kNumCodeBasicBlocks,
119 E : CountBasicBlocks(subgraph_, BasicBlock::BASIC_CODE_BLOCK));
120 : ASSERT_EQ(kNumDataBasicBlocks,
121 E : CountBasicBlocks(subgraph_, BasicBlock::BASIC_DATA_BLOCK));
122 : ASSERT_EQ(kNumCodePaddingBasicBlocks,
123 E : CountPaddingBasicBlocks(subgraph_, BasicBlock::BASIC_CODE_BLOCK));
124 : ASSERT_EQ(kNumDataPaddingBasicBlocks,
125 E : CountPaddingBasicBlocks(subgraph_, BasicBlock::BASIC_DATA_BLOCK));
126 :
127 : // There should be no gaps and all of the blocks should be used.
128 E : ASSERT_EQ(1U, subgraph_.block_descriptions().size());
129 : const BasicBlockSubGraph::BlockDescription& desc =
130 E : subgraph_.block_descriptions().back();
131 E : EXPECT_EQ(kNumBasicBlocks, desc.basic_block_order.size());
132 : EXPECT_TRUE(
133 : std::adjacent_find(
134 : desc.basic_block_order.begin(),
135 : desc.basic_block_order.end(),
136 E : &HasGapOrIsOutOfOrder) == desc.basic_block_order.end());
137 :
138 E : BasicBlockSubGraph::ReachabilityMap rm;
139 E : subgraph_.GetReachabilityMap(&rm);
140 :
141 : // Basic-block 0 - assembly_func.
142 E : ASSERT_TRUE(BasicBlockSubGraph::IsReachable(rm, bbs_[0]));
143 E : ASSERT_FALSE(bbs_[0]->is_padding());
144 E : ASSERT_EQ(BasicBlock::BASIC_CODE_BLOCK, bbs_[0]->type());
145 E : BasicCodeBlock* bb0 = BasicCodeBlock::Cast(bbs_[0]);
146 E : ASSERT_TRUE(bb0 != NULL);
147 E : ASSERT_EQ(4u, bb0->instructions().size());
148 E : ASSERT_EQ(0u, bb0->successors().size());
149 : BasicBlock::Instructions::const_iterator inst_iter =
150 E : bb0->instructions().begin();
151 E : std::advance(inst_iter, 2);
152 E : ASSERT_EQ(1u, inst_iter->references().size());
153 E : ASSERT_EQ(bbs_[9], inst_iter->references().begin()->second.basic_block());
154 E : std::advance(inst_iter, 1);
155 E : ASSERT_EQ(1u, inst_iter->references().size());
156 E : ASSERT_EQ(bbs_[8], inst_iter->references().begin()->second.basic_block());
157 E : ASSERT_EQ(1u, bbs_[0]->alignment());
158 :
159 : // Basic-block 1 - unreachable-label.
160 E : ASSERT_FALSE(BasicBlockSubGraph::IsReachable(rm, bbs_[1]));
161 E : ASSERT_TRUE(bbs_[1]->is_padding());
162 E : ASSERT_EQ(BasicBlock::BASIC_CODE_BLOCK, bbs_[1]->type());
163 E : BasicCodeBlock* bb1 = BasicCodeBlock::Cast(bbs_[1]);
164 E : ASSERT_EQ(1u, bb1->instructions().size());
165 E : ASSERT_EQ(1u, bb1->successors().size());;
166 : ASSERT_EQ(bbs_[2],
167 E : bb1->successors().front().reference().basic_block());
168 E : ASSERT_EQ(1u, bb1->alignment());
169 :
170 : // Basic-block 2 - case_0.
171 E : ASSERT_TRUE(BasicBlockSubGraph::IsReachable(rm, bbs_[2]));
172 E : ASSERT_FALSE(bbs_[2]->is_padding());
173 E : ASSERT_EQ(BasicBlock::BASIC_CODE_BLOCK, bbs_[2]->type());
174 E : BasicCodeBlock* bb2 = BasicCodeBlock::Cast(bbs_[2]);
175 E : ASSERT_TRUE(bb2 != NULL);
176 E : ASSERT_EQ(2u, bb2->instructions().size());
177 E : ASSERT_EQ(1u, bb2->successors().size());;
178 E : ASSERT_EQ(bbs_[3], bb2->successors().front().reference().basic_block());
179 E : ASSERT_EQ(1u, bbs_[2]->alignment());
180 :
181 : // Basic-block 3 - sub eax to jnz.
182 E : ASSERT_TRUE(BasicBlockSubGraph::IsReachable(rm, bbs_[3]));
183 E : ASSERT_FALSE(bbs_[3]->is_padding());
184 E : ASSERT_EQ(BasicBlock::BASIC_CODE_BLOCK, bbs_[3]->type());
185 E : BasicCodeBlock* bb3 = BasicCodeBlock::Cast(bbs_[3]);
186 E : ASSERT_TRUE(bb3 != NULL);
187 E : ASSERT_EQ(1u, bb3->instructions().size());
188 E : ASSERT_EQ(2u, bb3->successors().size());;
189 E : ASSERT_EQ(bb3, bb3->successors().front().reference().basic_block());
190 E : ASSERT_EQ(bbs_[4], bb3->successors().back().reference().basic_block());
191 E : ASSERT_EQ(1u, bbs_[3]->alignment());
192 :
193 : // Basic-block 4 - ret.
194 E : ASSERT_TRUE(BasicBlockSubGraph::IsReachable(rm, bbs_[4]));
195 E : ASSERT_FALSE(bbs_[4]->is_padding());
196 E : ASSERT_EQ(BasicBlock::BASIC_CODE_BLOCK, bbs_[4]->type());
197 E : BasicCodeBlock* bb4 = BasicCodeBlock::Cast(bbs_[4]);
198 E : ASSERT_TRUE(bb4 != NULL);
199 E : ASSERT_EQ(1u, bb4->instructions().size());
200 E : ASSERT_EQ(0u, bb4->successors().size());;
201 E : ASSERT_EQ(1u, bbs_[4]->alignment());
202 :
203 : // Basic-block 5 - case_1.
204 E : ASSERT_TRUE(BasicBlockSubGraph::IsReachable(rm, bbs_[5]));
205 E : ASSERT_FALSE(bbs_[5]->is_padding());
206 E : ASSERT_EQ(BasicBlock::BASIC_CODE_BLOCK, bbs_[5]->type());
207 E : BasicCodeBlock* bb5 = BasicCodeBlock::Cast(bbs_[5]);
208 E : ASSERT_TRUE(bb5 != NULL);
209 E : ASSERT_EQ(1u, bb5->instructions().size());
210 : ASSERT_EQ(
211 : func1_,
212 E : bb5->instructions().front().references().begin()->second.block());
213 E : ASSERT_EQ(1u, bb5->successors().size());
214 E : ASSERT_EQ(bbs_[6], bb5->successors().front().reference().basic_block());
215 E : ASSERT_EQ(1u, bbs_[5]->alignment());
216 :
217 : // Basic-block 6 - case_default.
218 E : ASSERT_TRUE(BasicBlockSubGraph::IsReachable(rm, bbs_[6]));
219 E : ASSERT_FALSE(bbs_[6]->is_padding());
220 E : ASSERT_EQ(BasicBlock::BASIC_CODE_BLOCK, bbs_[6]->type());
221 E : BasicCodeBlock* bb6 = BasicCodeBlock::Cast(bbs_[6]);
222 E : ASSERT_TRUE(bb6 != NULL);
223 E : ASSERT_EQ(2u, bb6->instructions().size());
224 : ASSERT_EQ(
225 : func2_,
226 E : bb6->instructions().back().references().begin()->second.block());
227 E : ASSERT_EQ(0u, bb6->successors().size());
228 E : ASSERT_EQ(1u, bbs_[6]->alignment());
229 :
230 : // Basic-block 7 - interrupt_label.
231 E : ASSERT_FALSE(BasicBlockSubGraph::IsReachable(rm, bbs_[7]));
232 E : ASSERT_TRUE(bbs_[7]->is_padding());
233 E : ASSERT_EQ(BasicBlock::BASIC_CODE_BLOCK, bbs_[7]->type());
234 E : BasicCodeBlock* bb7 = BasicCodeBlock::Cast(bbs_[7]);
235 E : ASSERT_TRUE(bb7 != NULL);
236 E : ASSERT_EQ(3u, bb7->instructions().size());
237 E : ASSERT_EQ(0u, bb7->successors().size());
238 E : ASSERT_EQ(1u, bbs_[7]->alignment());
239 :
240 : // Basic-block 8 - jump_table.
241 E : ASSERT_TRUE(BasicBlockSubGraph::IsReachable(rm, bbs_[8]));
242 E : ASSERT_FALSE(bbs_[8]->is_padding());
243 E : ASSERT_EQ(BasicBlock::BASIC_DATA_BLOCK, bbs_[8]->type());
244 E : BasicDataBlock* bb8 = BasicDataBlock::Cast(bbs_[8]);
245 E : ASSERT_TRUE(bb8 != NULL);
246 E : ASSERT_EQ(3 * Reference::kMaximumSize, bb8->size());
247 E : ASSERT_EQ(3u, bb8->references().size());
248 E : ASSERT_EQ(4u, bbs_[8]->alignment());
249 :
250 : // Basic-block 9 - case_table.
251 E : ASSERT_TRUE(BasicBlockSubGraph::IsReachable(rm, bbs_[9]));
252 E : ASSERT_FALSE(bbs_[9]->is_padding());
253 E : ASSERT_EQ(BasicBlock::BASIC_DATA_BLOCK, bbs_[9]->type());
254 E : BasicDataBlock* bb9 = BasicDataBlock::Cast(bbs_[9]);
255 E : ASSERT_TRUE(bb9 != NULL);
256 E : ASSERT_EQ(256, bb9->size());
257 E : ASSERT_EQ(0u, bb9->references().size());
258 E : ASSERT_EQ(4u, bbs_[9]->alignment());
259 :
260 : // Validate all source ranges.
261 E : core::RelativeAddress next_addr(start_addr_);
262 E : for (size_t i = 0; i < bbs_.size(); ++i) {
263 E : const BasicCodeBlock* code_block = BasicCodeBlock::Cast(bbs_[i]);
264 E : const BasicDataBlock* data_block = BasicDataBlock::Cast(bbs_[i]);
265 :
266 E : if (code_block != NULL) {
267 E : ASSERT_TRUE(data_block == NULL);
268 :
269 : BasicBlock::Instructions::const_iterator instr_it =
270 E : code_block->instructions().begin();
271 E : for (; instr_it != code_block->instructions().end(); ++instr_it) {
272 E : const Instruction& instr = *instr_it;
273 E : ASSERT_EQ(next_addr, instr.source_range().start());
274 E : ASSERT_EQ(instr.size(), instr.source_range().size());
275 :
276 E : next_addr += instr.size();
277 E : }
278 :
279 : BasicBlock::Successors::const_iterator succ_it =
280 E : code_block->successors().begin();
281 E : for (; succ_it != code_block->successors().end(); ++succ_it) {
282 E : const Successor& succ = *succ_it;
283 E : if (succ.source_range().size() != 0) {
284 E : ASSERT_EQ(next_addr, succ.source_range().start());
285 E : ASSERT_EQ(succ.instruction_size(), succ.source_range().size());
286 E : } else {
287 E : ASSERT_EQ(0, succ.instruction_size());
288 : }
289 :
290 E : next_addr += succ.instruction_size();
291 E : }
292 : }
293 :
294 E : if (data_block != NULL) {
295 E : ASSERT_TRUE(code_block == NULL);
296 E : ASSERT_TRUE(data_block->type() == BasicBlock::BASIC_DATA_BLOCK);
297 E : ASSERT_EQ(next_addr, data_block->source_range().start());
298 E : ASSERT_EQ(data_block->size(), data_block->source_range().size());
299 :
300 E : next_addr += data_block->size();
301 : }
302 E : }
303 E : }
304 :
305 E : TEST_F(BasicBlockDecomposerTest, DecomposeBlockWithLabelPastData) {
306 E : ASSERT_NO_FATAL_FAILURE(InitBasicBlockSubGraphWithLabelPastEnd());
307 E : }
308 :
309 : } // namespace block_graph
|