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 : #include "syzygy/block_graph/basic_block_test_util.h"
16 :
17 : #include "gtest/gtest.h"
18 : #include "syzygy/block_graph/basic_block_decomposer.h"
19 : #include "syzygy/block_graph/basic_block_subgraph.h"
20 :
21 : extern "C" {
22 :
23 : // Functions invoked or referred by the .asm test stub.
24 i : int func1() {
25 i : return 1;
26 i : }
27 :
28 i : int func2() {
29 i : return 2;
30 i : }
31 :
32 : } // extern "C"
33 :
34 : namespace testing {
35 :
36 : namespace {
37 :
38 : using block_graph::BlockGraph;
39 :
40 : #define POINTER_DIFF(x, y) \
41 : (reinterpret_cast<const uint8*>(x) - reinterpret_cast<const uint8*>(y))
42 E : const int32 kAssemblyFuncSize = POINTER_DIFF(assembly_func_end, assembly_func);
43 E : const int32 kCaseTableOffset = POINTER_DIFF(case_table, assembly_func);
44 E : const int32 kJumpTableOffset = POINTER_DIFF(jump_table, assembly_func);
45 E : const int32 kCase0Offset = POINTER_DIFF(case_0, assembly_func);
46 E : const int32 kCase1Offset = POINTER_DIFF(case_1, assembly_func);
47 E : const int32 kCaseDefaultOffset = POINTER_DIFF(case_default, assembly_func);
48 E : const int32 kInterruptOffset = POINTER_DIFF(interrupt_label, assembly_func);
49 : const int32 kUnreachableOffset = POINTER_DIFF(unreachable_label,
50 E : assembly_func);
51 : #undef POINTER_DIFF
52 :
53 : const BlockGraph::LabelAttributes kCaseTableAttributes =
54 : BlockGraph::DATA_LABEL | BlockGraph::CASE_TABLE_LABEL;
55 :
56 : const BlockGraph::LabelAttributes kJumpTableAttributes =
57 : BlockGraph::DATA_LABEL | BlockGraph::JUMP_TABLE_LABEL;
58 :
59 : } // namespace
60 :
61 : BasicBlockTest::BasicBlockTest()
62 : : text_section_(NULL), data_section_(NULL), assembly_func_(NULL),
63 E : func1_(NULL), func2_(NULL), data_(NULL) {
64 E : }
65 :
66 E : void BasicBlockTest::InitBlockGraph() {
67 E : start_addr_ = RelativeAddress(0xF00D);
68 :
69 : text_section_ = block_graph_.AddSection(
70 E : ".text", IMAGE_SCN_MEM_READ | IMAGE_SCN_MEM_EXECUTE);
71 E : ASSERT_TRUE(text_section_ != NULL);
72 :
73 : data_section_ = block_graph_.AddSection(
74 : ".data",
75 : IMAGE_SCN_CNT_INITIALIZED_DATA | IMAGE_SCN_MEM_READ |
76 E : IMAGE_SCN_MEM_WRITE);
77 E : ASSERT_TRUE(data_section_ != NULL);
78 :
79 : // Create func1, which will be called from assembly_func.
80 E : func1_ = block_graph_.AddBlock(BlockGraph::CODE_BLOCK, 1, "func1");
81 E : ASSERT_TRUE(func1_ != NULL);
82 E : func1_->set_section(text_section_->id());
83 :
84 : // Create func2, a non-returning function called from assembly_func.
85 E : func2_ = block_graph_.AddBlock(BlockGraph::CODE_BLOCK, 1, "func2");
86 E : ASSERT_TRUE(func2_ != NULL);
87 E : func2_->set_attributes(BlockGraph::NON_RETURN_FUNCTION);
88 E : func2_->set_section(text_section_->id());
89 :
90 : // Create a data block to refer to assembly_func.
91 E : data_ = block_graph_.AddBlock(BlockGraph::DATA_BLOCK, 4, "data");
92 E : ASSERT_TRUE(data_ != NULL);
93 E : data_->set_section(data_section_->id());
94 :
95 : // Create assembly_func, and mark it as BUILT_BY_SYZYGY so the basic-block
96 : // decomposer is willing to process it.
97 : assembly_func_ = block_graph_.AddBlock(BlockGraph::CODE_BLOCK,
98 : kAssemblyFuncSize,
99 E : "assembly_func_");
100 E : ASSERT_TRUE(assembly_func_ != NULL);
101 : assembly_func_->SetData(reinterpret_cast<const uint8*>(assembly_func),
102 E : kAssemblyFuncSize);
103 E : assembly_func_->set_attributes(BlockGraph::BUILT_BY_SYZYGY);
104 E : assembly_func_->set_section(text_section_->id());
105 : assembly_func_->
106 : source_ranges().Push(Block::DataRange(0, kAssemblyFuncSize),
107 E : Block::SourceRange(start_addr_, kAssemblyFuncSize));
108 :
109 : // This block contains aligned case and jump tables, so the decomposer would
110 : // give it pointer alignment.
111 E : assembly_func_->set_alignment(4);
112 :
113 : // Add the data labels.
114 : ASSERT_TRUE(assembly_func_->SetLabel(
115 E : kCaseTableOffset, "case_table", kCaseTableAttributes));
116 : ASSERT_TRUE(assembly_func_->SetLabel(
117 E : kJumpTableOffset, "jump_table", kJumpTableAttributes));
118 :
119 : // Add the instruction references to the jump and case tables. Note that
120 : // the jump table reference is at the end of the indirect jmp instruction
121 : // (7-bytes) that immediately precedes the unreachable label and that the
122 : // case table reference is at the end of the movzx instruction which
123 : // immediately preceeds the jmp.
124 : ASSERT_TRUE(assembly_func_->SetReference(
125 : kUnreachableOffset - (Reference::kMaximumSize + 7),
126 : Reference(BlockGraph::RELATIVE_REF, Reference::kMaximumSize,
127 E : assembly_func_, kCaseTableOffset, kCaseTableOffset)));
128 : ASSERT_TRUE(assembly_func_->SetReference(
129 : kUnreachableOffset - Reference::kMaximumSize,
130 : Reference(BlockGraph::RELATIVE_REF, Reference::kMaximumSize,
131 E : assembly_func_, kJumpTableOffset, kJumpTableOffset)));
132 : // Add the jump table references to the cases.
133 : ASSERT_TRUE(assembly_func_->SetReference(
134 : kJumpTableOffset + (Reference::kMaximumSize * 0),
135 : Reference(BlockGraph::RELATIVE_REF, Reference::kMaximumSize,
136 E : assembly_func_, kCase0Offset, kCase0Offset)));
137 : ASSERT_TRUE(assembly_func_->SetReference(
138 : kJumpTableOffset + (Reference::kMaximumSize * 1),
139 : Reference(BlockGraph::RELATIVE_REF, Reference::kMaximumSize,
140 E : assembly_func_, kCase1Offset, kCase1Offset)));
141 : ASSERT_TRUE(assembly_func_->SetReference(
142 : kJumpTableOffset + (Reference::kMaximumSize * 2),
143 : Reference(BlockGraph::RELATIVE_REF, Reference::kMaximumSize,
144 E : assembly_func_, kCaseDefaultOffset, kCaseDefaultOffset)));
145 :
146 : // Add the external outbound references.
147 : ASSERT_TRUE(assembly_func_->SetReference(
148 : kCase1Offset + 1,
149 : Reference(BlockGraph::RELATIVE_REF, Reference::kMaximumSize,
150 E : func1_, 0, 0)));
151 : ASSERT_TRUE(assembly_func_->SetReference(
152 : kInterruptOffset - Reference::kMaximumSize,
153 : Reference(BlockGraph::RELATIVE_REF, Reference::kMaximumSize,
154 E : func2_, 0, 0)));
155 :
156 : // Add an inbound reference to the top of the function.
157 : ASSERT_TRUE(data_->SetReference(
158 : 0,
159 : Reference(BlockGraph::RELATIVE_REF, Reference::kMaximumSize,
160 E : assembly_func_, 0, 0)));
161 E : }
162 :
163 E : void BasicBlockTest::InitBasicBlockSubGraph() {
164 E : BasicBlockDecomposer bb_decomposer(assembly_func_, &subgraph_);
165 E : logging::SetMinLogLevel(logging::LOG_ERROR);
166 E : ASSERT_TRUE(bb_decomposer.Decompose());
167 E : ASSERT_TRUE(subgraph_.IsValid());
168 :
169 E : ASSERT_EQ(1u, subgraph_.block_descriptions().size());
170 E : bds_.reserve(subgraph_.block_descriptions().size());
171 : BasicBlockSubGraph::BlockDescriptionList::iterator bd_it =
172 E : subgraph_.block_descriptions().begin();
173 E : for (; bd_it != subgraph_.block_descriptions().end(); ++bd_it)
174 E : bds_.push_back(&(*bd_it));
175 E : ASSERT_EQ(subgraph_.block_descriptions().size(), bds_.size());
176 :
177 E : ASSERT_EQ(kNumBasicBlocks, bds_[0]->basic_block_order.size());
178 E : bbs_.reserve(bds_[0]->basic_block_order.size());
179 : bbs_.assign(bds_[0]->basic_block_order.begin(),
180 E : bds_[0]->basic_block_order.end());
181 E : ASSERT_EQ(bds_[0]->basic_block_order.size(), bbs_.size());
182 E : }
183 :
184 E : void BasicBlockTest::InitBasicBlockSubGraphWithLabelPastEnd() {
185 : // We create a simple block-graph containing two blocks. One of them is a
186 : // simple function that contains a single int3 instruction. The second block
187 : // contains a call to the first block. The second block has no epilog (given
188 : // that it calls a non-returning function) and has a debug-end label past the
189 : // end of the block.
190 E : ASSERT_TRUE(block_graph_.sections().empty());
191 E : ASSERT_TRUE(block_graph_.blocks().empty());
192 :
193 : text_section_ = block_graph_.AddSection(
194 E : ".text", IMAGE_SCN_MEM_READ | IMAGE_SCN_MEM_EXECUTE);
195 E : ASSERT_TRUE(text_section_ != NULL);
196 :
197 E : func1_ = block_graph_.AddBlock(BlockGraph::CODE_BLOCK, 1, "noret");
198 E : ASSERT_TRUE(func1_ != NULL);
199 E : func1_->ResizeData(1);
200 E : func1_->GetMutableData()[0] = 0xCC; // int3.
201 E : func1_->SetLabel(0, "noret", BlockGraph::CODE_LABEL);
202 :
203 E : func2_ = block_graph_.AddBlock(BlockGraph::CODE_BLOCK, 6, "no_epilog");
204 E : ASSERT_TRUE(func2_ != NULL);
205 E : func2_->ResizeData(6);
206 E : func2_->GetMutableData()[0] = 0xE8; // call 0x00000000 (non returning).
207 E : func2_->GetMutableData()[5] = 0xCC; // int3.
208 :
209 : func2_->SetLabel(0, "no_epilog, debug-start",
210 E : BlockGraph::CODE_LABEL | BlockGraph::DEBUG_START_LABEL);
211 E : func2_->SetLabel(6, "debug-end", BlockGraph::DEBUG_END_LABEL);
212 :
213 : func2_->SetReference(1, BlockGraph::Reference(BlockGraph::ABSOLUTE_REF,
214 : 4,
215 : func1_,
216 : 0,
217 E : 0));
218 :
219 : // Decompose the second function.
220 E : BasicBlockDecomposer bb_decomposer(func2_, &subgraph_);
221 :
222 E : ASSERT_TRUE(bb_decomposer.Decompose());
223 E : ASSERT_TRUE(subgraph_.IsValid());
224 :
225 E : ASSERT_EQ(1u, subgraph_.block_descriptions().size());
226 E : ASSERT_EQ(2u, subgraph_.basic_blocks().size());
227 :
228 : BasicBlockSubGraph::BlockDescriptionList::const_iterator bd_it =
229 E : subgraph_.block_descriptions().begin();
230 E : ASSERT_EQ(2u, bd_it->basic_block_order.size());
231 :
232 : BasicBlockSubGraph::BBCollection::const_iterator bb_it =
233 E : subgraph_.basic_blocks().begin();
234 :
235 E : const block_graph::BasicBlock* bb = *bb_it;
236 : const block_graph::BasicCodeBlock* bcb =
237 E : block_graph::BasicCodeBlock::Cast(bb);
238 E : ASSERT_TRUE(bcb != NULL);
239 :
240 E : ASSERT_EQ(2u, bcb->instructions().size());
241 E : ASSERT_EQ(1u, bcb->instructions().begin()->references().size());
242 E : ASSERT_TRUE(bcb->instructions().begin()->has_label());
243 : ASSERT_EQ(BlockGraph::CODE_LABEL | BlockGraph::DEBUG_START_LABEL,
244 E : bcb->instructions().begin()->label().attributes());
245 :
246 E : ++bb_it;
247 E : bb = *bb_it;
248 : const block_graph::BasicEndBlock* beb =
249 E : block_graph::BasicEndBlock::Cast(bb);
250 E : ASSERT_TRUE(beb != NULL);
251 :
252 E : BlockGraph::Label expected_label("debug-end", BlockGraph::DEBUG_END_LABEL);
253 E : ASSERT_TRUE(beb->has_label());
254 E : ASSERT_EQ(expected_label, beb->label());
255 :
256 E : ++bb_it;
257 E : ASSERT_TRUE(bb_it == subgraph_.basic_blocks().end());
258 E : }
259 :
260 : } // namespace testing
|