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