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/unittest_util.h"
16 :
17 : namespace testing {
18 :
19 : namespace {
20 :
21 : // TODO(chrisha): Break up the functions below into smaller reusable
22 : // components.
23 :
24 : using block_graph::BlockGraph;
25 : using block_graph::BlockGraphSerializer;
26 :
27 : // Compare two strings to each others if the OMIT_STRINGS flag isn't set.
28 : bool MaybeCompareStrings(const std::string& string1,
29 : const std::string& string2,
30 E : const BlockGraphSerializer& bgs) {
31 E : if (bgs.has_attributes(BlockGraphSerializer::OMIT_STRINGS)) {
32 E : if (!string1.empty() && !string2.empty())
33 i : return false;
34 E : return true;
35 : }
36 E : if (string1 != string2)
37 i : return false;
38 E : return true;
39 E : }
40 :
41 : bool ReferencesEqual(const BlockGraph::Reference& ref1,
42 E : const BlockGraph::Reference& ref2) {
43 : if (ref1.base() != ref2.base() || ref1.offset() != ref2.offset() ||
44 : ref1.size() != ref2.size() || ref1.type() != ref2.type() ||
45 E : ref1.referenced()->id() != ref2.referenced()->id()) {
46 i : return false;
47 : }
48 E : return true;
49 E : }
50 :
51 : // Determines if the data in two blocks are equivalent, including the
52 : // references. We do both at the same time so as to not check the actual data
53 : // where references lie, which may be different post- and pre- image writing.
54 : bool DataAndReferencesEqual(const BlockGraph::Block& b1,
55 E : const BlockGraph::Block& b2) {
56 : // The data and references need to be the same size.
57 : if (b1.data_size() != b2.data_size() ||
58 E : b1.references().size() != b2.references().size()) {
59 i : return false;
60 : }
61 :
62 : // Both data pointers should be null or non-null. We can't say anything
63 : // about data ownership, as this doesn't affect block equality.
64 E : if ((b1.data() == NULL) != (b2.data() == NULL))
65 i : return false;
66 :
67 : typedef BlockGraph::Block::ReferenceMap::const_iterator Iterator;
68 E : Iterator it1 = b1.references().begin();
69 E : Iterator it2 = b2.references().begin();
70 E : Iterator end1 = b1.references().lower_bound(b1.data_size());
71 :
72 E : const uint8* d1 = b1.data();
73 E : const uint8* d2 = b2.data();
74 E : BlockGraph::Offset i = 0;
75 E : BlockGraph::Offset data_size = b1.data_size();
76 :
77 : // If either of the blocks don't have data, then the data-size should be 0.
78 E : if (d1 == NULL || d2 == NULL)
79 E : DCHECK_EQ(0, data_size);
80 :
81 : // Check the portion of data with embedded references.
82 E : while (i < data_size && it1 != end1) {
83 : // Check the reference.
84 : if (it1->first != it2->first ||
85 E : !ReferencesEqual(it1->second, it2->second)) {
86 i : return false;
87 : }
88 :
89 : // Before the next reference? Then check the data is the same.
90 E : if (i < it1->first) {
91 E : if (::memcmp(d1 + i, d2 + i, it1->first - i) != 0)
92 i : return false;
93 : }
94 :
95 : // Step past the reference.
96 E : i = it1->first + it1->second.size();
97 E : ++it1;
98 E : ++it2;
99 E : }
100 :
101 : // Check any remaining data.
102 E : if (i < data_size && ::memcmp(d1 + i, d2 + i, data_size - i) != 0)
103 i : return false;
104 :
105 : // Check the remaining references.
106 E : end1 = b1.references().end();
107 E : for (; it1 != end1; ++it1, ++it2) {
108 : if (it1->first != it2->first ||
109 i : !ReferencesEqual(it1->second, it2->second)) {
110 i : return false;
111 : }
112 i : }
113 :
114 E : return true;
115 E : }
116 :
117 : bool ReferrersEqual(const BlockGraph::Block& b1,
118 E : const BlockGraph::Block& b2) {
119 E : if (b1.referrers().size() != b2.referrers().size())
120 i : return false;
121 :
122 : // Compare the referrers. They should point to blocks with the same id.
123 : // We store a list of unique referrer id/offset pairs. This allows us to
124 : // efficiently search for an equivalent referrer.
125 : typedef std::set<std::pair<size_t, size_t> > IdOffsetSet;
126 E : IdOffsetSet id_offset_set;
127 E : BlockGraph::Block::ReferrerSet::const_iterator it = b1.referrers().begin();
128 E : for (; it != b1.referrers().end(); ++it)
129 E : id_offset_set.insert(std::make_pair(it->first->id(), it->second));
130 :
131 E : for (it = b2.referrers().begin(); it != b2.referrers().end(); ++it) {
132 : IdOffsetSet::const_iterator set_it = id_offset_set.find(
133 E : std::make_pair(it->first->id(), it->second));
134 E : if (set_it == id_offset_set.end())
135 i : return false;
136 E : }
137 :
138 E : return true;
139 E : }
140 :
141 : } // namespace
142 :
143 : // Compares two Blocks to each other.
144 : bool BlocksEqual(const BlockGraph::Block& b1,
145 : const BlockGraph::Block& b2,
146 E : const BlockGraphSerializer& bgs) {
147 : // Compare the basic block properties.
148 : if (b1.id() != b2.id() || b1.type() != b2.type() ||
149 : b1.size() != b2.size() || b1.alignment() != b2.alignment() ||
150 : b1.alignment_offset() != b2.alignment_offset() ||
151 : b1.padding_before() != b2.padding_before() ||
152 : b1.addr() != b2.addr() || b1.section() != b2.section() ||
153 : b1.attributes() != b2.attributes() ||
154 : b1.source_ranges() != b2.source_ranges() ||
155 E : b1.data_size() != b2.data_size()) {
156 i : return false;
157 : }
158 :
159 E : if (!MaybeCompareStrings(b1.name(), b2.name(), bgs))
160 i : return false;
161 :
162 E : if (!MaybeCompareStrings(b1.compiland_name(), b2.compiland_name(), bgs))
163 i : return false;
164 :
165 : // Compare the labels.
166 E : if (!bgs.has_attributes(BlockGraphSerializer::OMIT_LABELS)) {
167 E : if (b1.labels().size() != b2.labels().size())
168 i : return false;
169 : BlockGraph::Block::LabelMap::const_iterator it1 =
170 E : b1.labels().begin();
171 : BlockGraph::Block::LabelMap::const_iterator it2 =
172 E : b2.labels().begin();
173 E : for (; it1 != b1.labels().end(); ++it1, ++it2) {
174 : if (it1->first != it2->first ||
175 : it1->second.attributes() != it2->second.attributes() ||
176 : !MaybeCompareStrings(it1->second.name(),
177 : it2->second.name(),
178 E : bgs)) {
179 i : return false;
180 : }
181 E : }
182 : }
183 :
184 : // Compare the data and the references.
185 E : if (!DataAndReferencesEqual(b1, b2))
186 i : return false;
187 :
188 : // Compare the referrers.
189 E : if (!ReferrersEqual(b1, b2))
190 i : return false;
191 :
192 E : return true;
193 E : }
194 :
195 : // Compares two BlockGraphs to each other.
196 : bool BlockGraphsEqual(const BlockGraph& b1,
197 : const BlockGraph& b2,
198 E : const BlockGraphSerializer& bgs) {
199 : if (b1.sections() != b2.sections() ||
200 E : b1.blocks().size() != b2.blocks().size()) {
201 i : return false;
202 : }
203 :
204 : // We manually iterate through the blocks and use BlocksEqual,
205 : // because they don't otherwise have a comparison operator.
206 E : BlockGraph::BlockMap::const_iterator it1 = b1.blocks().begin();
207 E : for (; it1 != b1.blocks().end(); ++it1) {
208 E : BlockGraph::BlockMap::const_iterator it2 = b2.blocks().find(it1->first);
209 E : if (it2 == b2.blocks().end())
210 i : return false;
211 :
212 E : if (!BlocksEqual(it1->second, it2->second, bgs))
213 i : return false;
214 E : }
215 :
216 E : return true;
217 E : }
218 :
219 : bool GenerateTestBlockGraph(block_graph::BlockGraph* image) {
220 : DCHECK(image != NULL);
221 :
222 : BlockGraph::Section* s1 = image->AddSection("s1", 0);
223 : BlockGraph::Section* s2 = image->AddSection("s2", 0);
224 : if (s1 == NULL || s2 == NULL)
225 : return false;
226 :
227 : BlockGraph::Block* b1 = image->AddBlock(BlockGraph::CODE_BLOCK, 0x20, "b1");
228 : BlockGraph::Block* b2 = image->AddBlock(BlockGraph::CODE_BLOCK, 0x20, "b2");
229 : BlockGraph::Block* b3 = image->AddBlock(BlockGraph::CODE_BLOCK, 0x20, "b3");
230 : if (b1 == NULL || b2 == NULL || b3 == NULL)
231 : return false;
232 :
233 : b1->set_section(s1->id());
234 : b2->set_section(s1->id());
235 : b3->set_section(s2->id());
236 : if (b1->section() != s1->id() ||
237 : b2->section() != s1->id() ||
238 : b3->section() != s2->id())
239 : return false;
240 :
241 : b1->SetLabel(0x04, "label1", BlockGraph::CODE_LABEL);
242 : b2->SetLabel(0x08, "label2", BlockGraph::DATA_LABEL);
243 : b3->SetLabel(0x0C, "label3", BlockGraph::CODE_LABEL);
244 : b3->SetLabel(0x10, "label4", BlockGraph::DATA_LABEL);
245 :
246 : uint8* b1_data = b1->AllocateData(b1->size());
247 : for (size_t i = 0; i < b1->size(); ++i) {
248 : b1_data[i] = 0;
249 : }
250 :
251 : if (!b1->references().empty() ||
252 : !b1->referrers().empty() ||
253 : !b2->references().empty() ||
254 : !b2->referrers().empty() ||
255 : !b3->references().empty() ||
256 : !b3->referrers().empty())
257 : return false;
258 :
259 : BlockGraph::Reference r_pc(BlockGraph::PC_RELATIVE_REF, 1, b2, 9, 9);
260 : if (!b1->SetReference(0, r_pc) || !b1->SetReference(1, r_pc))
261 : return false;
262 :
263 : BlockGraph::Reference r_abs(BlockGraph::ABSOLUTE_REF, 4, b2, 13, 13);
264 : if (b1->SetReference(1, r_abs))
265 : return false;
266 :
267 : BlockGraph::Reference r_rel(BlockGraph::RELATIVE_REF, 4, b2, 17, 17);
268 : if (!b1->SetReference(5, r_rel))
269 : return false;
270 :
271 : BlockGraph::Reference r_file(BlockGraph::FILE_OFFSET_REF, 4, b2, 23, 23);
272 : if (!b1->SetReference(9, r_file))
273 : return false;
274 :
275 : return true;
276 : }
277 :
278 : bool DummyTransformPolicy::BlockIsSafeToBasicBlockDecompose(
279 E : const BlockGraph::Block* block) const {
280 E : DCHECK_NE(reinterpret_cast<BlockGraph::Block*>(NULL), block);
281 E : if (block->type() != BlockGraph::CODE_BLOCK)
282 E : return false;
283 E : return true;
284 E : }
285 :
286 : bool DummyTransformPolicy::ReferenceIsSafeToRedirect(
287 : const BlockGraph::Block* referrer,
288 i : const BlockGraph::Reference& reference) const {
289 i : DCHECK_NE(reinterpret_cast<BlockGraph::Block*>(NULL), referrer);
290 i : return true;
291 i : }
292 :
293 : } // namespace testing
|