1 : // Copyright 2012 Google Inc.
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/block_graph_serializer.h"
29 : #include "syzygy/block_graph/block_util.h"
30 : #include "syzygy/block_graph/unittest_util.h"
31 : #include "syzygy/core/address.h"
32 : #include "syzygy/core/unittest_util.h"
33 :
34 : #include "mnemonics.h" // NOLINT
35 :
36 : extern "C" {
37 :
38 : // Functions and labels exposed from our .asm test stub.
39 : extern int assembly_func();
40 : extern int unreachable_label();
41 : extern int interrupt_label();
42 : extern int assembly_func_end();
43 :
44 : extern int case_0();
45 : extern int case_1();
46 : extern int case_default();
47 : extern int jump_table();
48 : extern int case_table();
49 :
50 : // Functions invoked or referred by the .asm test stub.
51 i : int func1() {
52 i : return 1;
53 i : }
54 :
55 i : int func2() {
56 i : return 2;
57 i : }
58 :
59 : } // extern "C"
60 :
61 :
62 : namespace block_graph {
63 :
64 : namespace {
65 :
66 : using block_graph::BasicBlock;
67 : using block_graph::BasicBlockSubGraph;
68 : using block_graph::BlockGraph;
69 : using block_graph::BlockGraphSerializer;
70 : using block_graph::Successor;
71 : using core::AbsoluteAddress;
72 : using core::Disassembler;
73 : using testing::_;
74 : using testing::Return;
75 :
76 : typedef BasicBlockSubGraph::BBAddressSpace BBAddressSpace;
77 : typedef BlockGraph::Block Block;
78 : typedef BlockGraph::Offset Offset;
79 : typedef BlockGraph::Reference Reference;
80 : typedef BlockGraph::Size Size;
81 :
82 : #define POINTER_DIFF(x, y) \
83 : (reinterpret_cast<const uint8*>(x) - reinterpret_cast<const uint8*>(y))
84 E : const Size kAssemblyFuncSize = POINTER_DIFF(assembly_func_end, assembly_func);
85 E : const Offset kCaseTableOffset = POINTER_DIFF(case_table, assembly_func);
86 E : const Offset kJumpTableOffset = POINTER_DIFF(jump_table, assembly_func);
87 E : const Offset kCase0Offset = POINTER_DIFF(case_0, assembly_func);
88 E : const Offset kCase1Offset = POINTER_DIFF(case_1, assembly_func);
89 E : const Offset kCaseDefaultOffset = POINTER_DIFF(case_default, assembly_func);
90 E : const Offset kInterruptOffset = POINTER_DIFF(interrupt_label, assembly_func);
91 : const Offset kUnreachableOffset = POINTER_DIFF(unreachable_label,
92 E : assembly_func);
93 : #undef POINTER_DIFF
94 :
95 : // The number and type of basic blocks.
96 : // TODO(rogerm): The padding block will go away once the decomposer switches
97 : // to doing a straight disassembly of the entire code region.
98 : const size_t kNumCodeBasicBlocks = 7;
99 : const size_t kNumDataBasicBlocks = 2;
100 : const size_t kNumPaddingBasicBlocks = 1;
101 : const size_t kNumBasicBlocks =
102 : kNumCodeBasicBlocks + kNumDataBasicBlocks + kNumPaddingBasicBlocks;
103 :
104 : const BlockGraph::LabelAttributes kCaseTableAttributes =
105 : BlockGraph::DATA_LABEL | BlockGraph::CASE_TABLE_LABEL;
106 :
107 : const BlockGraph::LabelAttributes kJumpTableAttributes =
108 : BlockGraph::DATA_LABEL | BlockGraph::JUMP_TABLE_LABEL;
109 :
110 : // A helper to count basic blocks of a given type.
111 : size_t CountBasicBlocks(const BasicBlockSubGraph& subgraph,
112 E : BasicBlock::BasicBlockType type) {
113 E : size_t counter = 0;
114 : BasicBlockSubGraph::BBCollection::const_iterator it =
115 E : subgraph.basic_blocks().begin();
116 E : for (; it != subgraph.basic_blocks().end(); ++it) {
117 E : if (it->second.type() == type)
118 E : ++counter;
119 E : }
120 E : return counter;
121 E : }
122 :
123 :
124 : // A helper comparator to that returns true if lhs and rhs are not adjacent
125 : // and in order.
126 E : bool HasGapOrIsOutOfOrder(const BasicBlock* lhs, const BasicBlock* rhs) {
127 : typedef BasicBlock::Size Size;
128 E : return lhs->offset() + lhs->size() != static_cast<Size>(rhs->offset());
129 E : }
130 :
131 : // A test fixture which generates a block-graph to use for basic-block
132 : // related testing.
133 : // See: basic_block_assembly_func.asm
134 : class BasicBlockDecomposerTest : public ::testing::Test {
135 : public:
136 E : virtual void SetUp() OVERRIDE {
137 E : testing::Test::SetUp();
138 :
139 : // Create func1, which will be called from assembly_func.
140 E : func1_ = block_graph_.AddBlock(BlockGraph::CODE_BLOCK, 1, "func1");
141 E : ASSERT_TRUE(func1_ != NULL);
142 :
143 : // Create func2, a non-returning function called from assembly_func.
144 E : func2_ = block_graph_.AddBlock(BlockGraph::CODE_BLOCK, 1, "func2");
145 E : ASSERT_TRUE(func2_ != NULL);
146 E : func2_->set_attributes(BlockGraph::NON_RETURN_FUNCTION);
147 :
148 : // Create a data block to refer to assembly_func.
149 E : data_ = block_graph_.AddBlock(BlockGraph::DATA_BLOCK, 4, "data");
150 E : ASSERT_TRUE(data_ != NULL);
151 :
152 : // Create assembly_func, and mark it as BUILT_BY_SYZYGY so the basic-block
153 : // decomposer is willing to process it.
154 : assembly_func_ = block_graph_.AddBlock(BlockGraph::CODE_BLOCK,
155 : kAssemblyFuncSize,
156 E : "assembly_func_");
157 E : ASSERT_TRUE(assembly_func_ != NULL);
158 : assembly_func_->SetData(reinterpret_cast<const uint8*>(assembly_func),
159 E : kAssemblyFuncSize);
160 E : assembly_func_->set_attributes(BlockGraph::BUILT_BY_SYZYGY);
161 :
162 : // Add the data labels.
163 E : ASSERT_TRUE(assembly_func_->SetLabel(
164 : kCaseTableOffset, "case_table", kCaseTableAttributes));
165 E : ASSERT_TRUE(assembly_func_->SetLabel(
166 : kJumpTableOffset, "jump_table", kCaseTableAttributes));
167 :
168 : // Add the instruction references to the jump and case tables. Note that
169 : // the jump table reference is at the end of the indirect jmp instruction
170 : // (7-bytes) that immediately precedes the unreachable label and that the
171 : // case table reference is at the end of the movzx instruction which
172 : // immediately preceeds the jmp.
173 E : ASSERT_TRUE(assembly_func_->SetReference(
174 : kUnreachableOffset - (Reference::kMaximumSize + 7),
175 : Reference(BlockGraph::RELATIVE_REF, Reference::kMaximumSize,
176 : assembly_func_, kCaseTableOffset, kCaseTableOffset)));
177 E : ASSERT_TRUE(assembly_func_->SetReference(
178 : kUnreachableOffset - Reference::kMaximumSize,
179 : Reference(BlockGraph::RELATIVE_REF, Reference::kMaximumSize,
180 : assembly_func_, kJumpTableOffset, kJumpTableOffset)));
181 : // Add the jump table references to the cases.
182 E : ASSERT_TRUE(assembly_func_->SetReference(
183 : kJumpTableOffset + (Reference::kMaximumSize * 0),
184 : Reference(BlockGraph::RELATIVE_REF, Reference::kMaximumSize,
185 : assembly_func_, kCase0Offset, kCase0Offset)));
186 E : ASSERT_TRUE(assembly_func_->SetReference(
187 : kJumpTableOffset + (Reference::kMaximumSize * 1),
188 : Reference(BlockGraph::RELATIVE_REF, Reference::kMaximumSize,
189 : assembly_func_, kCase1Offset, kCase1Offset)));
190 E : ASSERT_TRUE(assembly_func_->SetReference(
191 : kJumpTableOffset + (Reference::kMaximumSize * 2),
192 : Reference(BlockGraph::RELATIVE_REF, Reference::kMaximumSize,
193 : assembly_func_, kCaseDefaultOffset, kCaseDefaultOffset)));
194 :
195 : // Add the external outbound references.
196 E : ASSERT_TRUE(assembly_func_->SetReference(
197 : kCase1Offset + 1,
198 : Reference(BlockGraph::RELATIVE_REF, Reference::kMaximumSize,
199 : func1_, 0, 0)));
200 E : ASSERT_TRUE(assembly_func_->SetReference(
201 : kInterruptOffset - Reference::kMaximumSize,
202 : Reference(BlockGraph::RELATIVE_REF, Reference::kMaximumSize,
203 : func2_, 0, 0)));
204 :
205 : // Add an inbound reference to the top of the function.
206 E : ASSERT_TRUE(data_->SetReference(
207 : 0,
208 : Reference(BlockGraph::RELATIVE_REF, Reference::kMaximumSize,
209 : assembly_func_, 0, 0)));
210 E : }
211 :
212 : protected:
213 : BlockGraph block_graph_;
214 : BlockGraph::Block* assembly_func_;
215 : BlockGraph::Block* func1_;
216 : BlockGraph::Block* func2_;
217 : BlockGraph::Block* data_;
218 : };
219 :
220 : }
221 :
222 E : TEST_F(BasicBlockDecomposerTest, Decompose) {
223 E : BasicBlockSubGraph subgraph;
224 E : BasicBlockDecomposer bb_decomposer(assembly_func_, &subgraph);
225 E : logging::SetMinLogLevel(3);
226 E : ASSERT_TRUE(bb_decomposer.Decompose());
227 E : ASSERT_TRUE(subgraph.IsValid());
228 :
229 : // Ensure we have the expected number and types of blocks.
230 E : ASSERT_EQ(kNumBasicBlocks, subgraph.basic_blocks().size());
231 E : ASSERT_EQ(kNumBasicBlocks, subgraph.original_address_space().size());
232 : ASSERT_EQ(kNumCodeBasicBlocks,
233 E : CountBasicBlocks(subgraph, BasicBlock::BASIC_CODE_BLOCK));
234 : ASSERT_EQ(kNumDataBasicBlocks,
235 E : CountBasicBlocks(subgraph, BasicBlock::BASIC_DATA_BLOCK));
236 : ASSERT_EQ(kNumPaddingBasicBlocks,
237 E : CountBasicBlocks(subgraph, BasicBlock::BASIC_PADDING_BLOCK));
238 :
239 : // There should be no gaps and all of the blocks should be used.
240 E : ASSERT_EQ(1U, subgraph.block_descriptions().size());
241 : const BasicBlockSubGraph::BlockDescription& desc =
242 E : subgraph.block_descriptions().back();
243 E : EXPECT_EQ(kNumBasicBlocks, desc.basic_block_order.size());
244 : EXPECT_TRUE(
245 : std::adjacent_find(
246 : desc.basic_block_order.begin(),
247 : desc.basic_block_order.end(),
248 E : &HasGapOrIsOutOfOrder) == desc.basic_block_order.end());
249 :
250 : // Let's validate the contents of the basic blocks.
251 E : std::vector<BasicBlock*> bb;
252 E : bb.reserve(desc.basic_block_order.size());
253 E : bb.assign(desc.basic_block_order.begin(), desc.basic_block_order.end());
254 :
255 E : BasicBlockSubGraph::ReachabilityMap rm;
256 E : subgraph.GetReachabilityMap(&rm);
257 :
258 : // Basic-block 0 - assembly_func.
259 E : ASSERT_TRUE(BasicBlockSubGraph::IsReachable(rm, bb[0]));
260 E : ASSERT_EQ(BasicBlock::BASIC_CODE_BLOCK, bb[0]->type());
261 E : ASSERT_EQ(4u, bb[0]->instructions().size());
262 E : ASSERT_EQ(0u, bb[0]->successors().size());;
263 : BasicBlock::Instructions::const_iterator inst_iter =
264 E : bb[0]->instructions().begin();
265 E : std::advance(inst_iter, 2);
266 E : ASSERT_EQ(1u, inst_iter->references().size());
267 E : ASSERT_EQ(bb[9], inst_iter->references().begin()->second.basic_block());
268 E : std::advance(inst_iter, 1);
269 E : ASSERT_EQ(1u, inst_iter->references().size());
270 E : ASSERT_EQ(bb[8], inst_iter->references().begin()->second.basic_block());
271 :
272 : // Basic-block 1 - unreachable-label.
273 : // TODO(rogerm): This is classified as padding for now, it will become code
274 : // once the decomposer switches to just doing a straight disassembly of
275 : // the entire code region.
276 E : ASSERT_FALSE(BasicBlockSubGraph::IsReachable(rm, bb[1]));
277 E : ASSERT_EQ(BasicBlock::BASIC_PADDING_BLOCK, bb[1]->type());
278 : // ASSERT_EQ(1u, bb[1]->instructions().size());
279 : // ASSERT_EQ(1u, bb[1]->successors().size());;
280 : // ASSERT_EQ(bb[2], bb[1]->successors().front().reference().basic_block());
281 :
282 : // Basic-block 2 - case_0.
283 E : ASSERT_TRUE(BasicBlockSubGraph::IsReachable(rm, bb[2]));
284 E : ASSERT_EQ(BasicBlock::BASIC_CODE_BLOCK, bb[2]->type());
285 E : ASSERT_EQ(2u, bb[2]->instructions().size());
286 E : ASSERT_EQ(1u, bb[2]->successors().size());;
287 E : ASSERT_EQ(bb[3], bb[2]->successors().front().reference().basic_block());
288 :
289 : // Basic-block 3 - sub eax to jnz.
290 E : ASSERT_TRUE(BasicBlockSubGraph::IsReachable(rm, bb[3]));
291 E : ASSERT_EQ(BasicBlock::BASIC_CODE_BLOCK, bb[3]->type());
292 E : ASSERT_EQ(1u, bb[3]->instructions().size());
293 E : ASSERT_EQ(2u, bb[3]->successors().size());;
294 E : ASSERT_EQ(bb[3], bb[3]->successors().front().reference().basic_block());
295 E : ASSERT_EQ(bb[4], bb[3]->successors().back().reference().basic_block());
296 :
297 : // Basic-block 4 - ret.
298 E : ASSERT_TRUE(BasicBlockSubGraph::IsReachable(rm, bb[4]));
299 E : ASSERT_EQ(BasicBlock::BASIC_CODE_BLOCK, bb[4]->type());
300 E : ASSERT_EQ(1u, bb[4]->instructions().size());
301 E : ASSERT_EQ(0u, bb[4]->successors().size());;
302 :
303 : // Basic-block 5 - case_1.
304 E : ASSERT_TRUE(BasicBlockSubGraph::IsReachable(rm, bb[5]));
305 E : ASSERT_EQ(BasicBlock::BASIC_CODE_BLOCK, bb[5]->type());
306 E : ASSERT_EQ(1u, bb[5]->instructions().size());
307 : ASSERT_EQ(func1_,
308 E : bb[5]->instructions().front().references().begin()->second.block());
309 E : ASSERT_EQ(1u, bb[5]->successors().size());
310 E : ASSERT_EQ(bb[6], bb[5]->successors().front().reference().basic_block());
311 :
312 : // Basic-block 6 - case_default.
313 E : ASSERT_TRUE(BasicBlockSubGraph::IsReachable(rm, bb[6]));
314 E : ASSERT_EQ(BasicBlock::BASIC_CODE_BLOCK, bb[6]->type());
315 E : ASSERT_EQ(2u, bb[6]->instructions().size());
316 : ASSERT_EQ(func2_,
317 E : bb[6]->instructions().back().references().begin()->second.block());
318 E : ASSERT_EQ(0u, bb[6]->successors().size());
319 :
320 : // Basic-block 7 - interrupt_label.
321 E : ASSERT_FALSE(BasicBlockSubGraph::IsReachable(rm, bb[7]));
322 E : ASSERT_EQ(BasicBlock::BASIC_CODE_BLOCK, bb[7]->type());
323 E : ASSERT_EQ(1u, bb[7]->instructions().size());
324 E : ASSERT_EQ(0u, bb[7]->successors().size());
325 :
326 : // Basic-block 8 - jump_table.
327 E : ASSERT_TRUE(BasicBlockSubGraph::IsReachable(rm, bb[8]));
328 E : ASSERT_EQ(BasicBlock::BASIC_DATA_BLOCK, bb[8]->type());
329 E : ASSERT_EQ(3 * Reference::kMaximumSize, bb[8]->size());
330 E : ASSERT_EQ(3u, bb[8]->references().size());
331 :
332 : // Basic-block 9 - case_table.
333 E : ASSERT_TRUE(BasicBlockSubGraph::IsReachable(rm, bb[9]));
334 E : ASSERT_EQ(BasicBlock::BASIC_DATA_BLOCK, bb[9]->type());
335 E : ASSERT_EQ(256, bb[9]->size());
336 E : ASSERT_EQ(0u, bb[9]->references().size());
337 E : }
338 :
339 : } // namespace block_graph
|