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.addr() != b2.addr() || b1.section() != b2.section() ||
151 : b1.attributes() != b2.attributes() ||
152 : b1.source_ranges() != b2.source_ranges() ||
153 E : b1.data_size() != b2.data_size()) {
154 i : return false;
155 : }
156 :
157 E : if (!MaybeCompareStrings(b1.name(), b2.name(), bgs))
158 i : return false;
159 :
160 E : if (!MaybeCompareStrings(b1.compiland_name(), b2.compiland_name(), bgs))
161 i : return false;
162 :
163 : // Compare the labels.
164 E : if (!bgs.has_attributes(BlockGraphSerializer::OMIT_LABELS)) {
165 E : if (b1.labels().size() != b2.labels().size())
166 i : return false;
167 : BlockGraph::Block::LabelMap::const_iterator it1 =
168 E : b1.labels().begin();
169 : BlockGraph::Block::LabelMap::const_iterator it2 =
170 E : b2.labels().begin();
171 E : for (; it1 != b1.labels().end(); ++it1, ++it2) {
172 : if (it1->first != it2->first ||
173 : it1->second.attributes() != it2->second.attributes() ||
174 : !MaybeCompareStrings(it1->second.name(),
175 : it2->second.name(),
176 E : bgs)) {
177 i : return false;
178 : }
179 E : }
180 : }
181 :
182 : // Compare the data and the references.
183 E : if (!DataAndReferencesEqual(b1, b2))
184 i : return false;
185 :
186 : // Compare the referrers.
187 E : if (!ReferrersEqual(b1, b2))
188 i : return false;
189 :
190 E : return true;
191 E : }
192 :
193 : // Compares two BlockGraphs to each other.
194 : bool BlockGraphsEqual(const BlockGraph& b1,
195 : const BlockGraph& b2,
196 E : const BlockGraphSerializer& bgs) {
197 : if (b1.sections() != b2.sections() ||
198 E : b1.blocks().size() != b2.blocks().size()) {
199 i : return false;
200 : }
201 :
202 : // We manually iterate through the blocks and use BlocksEqual,
203 : // because they don't otherwise have a comparison operator.
204 E : BlockGraph::BlockMap::const_iterator it1 = b1.blocks().begin();
205 E : for (; it1 != b1.blocks().end(); ++it1) {
206 E : BlockGraph::BlockMap::const_iterator it2 = b2.blocks().find(it1->first);
207 E : if (it2 == b2.blocks().end())
208 i : return false;
209 :
210 E : if (!BlocksEqual(it1->second, it2->second, bgs))
211 i : return false;
212 E : }
213 :
214 E : return true;
215 E : }
216 :
217 : bool GenerateTestBlockGraph(block_graph::BlockGraph* image) {
218 : DCHECK(image != NULL);
219 :
220 : BlockGraph::Section* s1 = image->AddSection("s1", 0);
221 : BlockGraph::Section* s2 = image->AddSection("s2", 0);
222 : if (s1 == NULL || s2 == NULL)
223 : return false;
224 :
225 : BlockGraph::Block* b1 = image->AddBlock(BlockGraph::CODE_BLOCK, 0x20, "b1");
226 : BlockGraph::Block* b2 = image->AddBlock(BlockGraph::CODE_BLOCK, 0x20, "b2");
227 : BlockGraph::Block* b3 = image->AddBlock(BlockGraph::CODE_BLOCK, 0x20, "b3");
228 : if (b1 == NULL || b2 == NULL || b3 == NULL)
229 : return false;
230 :
231 : b1->set_section(s1->id());
232 : b2->set_section(s1->id());
233 : b3->set_section(s2->id());
234 : if (b1->section() != s1->id() ||
235 : b2->section() != s1->id() ||
236 : b3->section() != s2->id())
237 : return false;
238 :
239 : b1->SetLabel(0x04, "label1", BlockGraph::CODE_LABEL);
240 : b2->SetLabel(0x08, "label2", BlockGraph::DATA_LABEL);
241 : b3->SetLabel(0x0C, "label3", BlockGraph::CODE_LABEL);
242 : b3->SetLabel(0x10, "label4", BlockGraph::DATA_LABEL);
243 :
244 : uint8* b1_data = b1->AllocateData(b1->size());
245 : for (size_t i = 0; i < b1->size(); ++i) {
246 : b1_data[i] = 0;
247 : }
248 :
249 : if (!b1->references().empty() ||
250 : !b1->referrers().empty() ||
251 : !b2->references().empty() ||
252 : !b2->referrers().empty() ||
253 : !b3->references().empty() ||
254 : !b3->referrers().empty())
255 : return false;
256 :
257 : BlockGraph::Reference r_pc(BlockGraph::PC_RELATIVE_REF, 1, b2, 9, 9);
258 : if (!b1->SetReference(0, r_pc) || !b1->SetReference(1, r_pc))
259 : return false;
260 :
261 : BlockGraph::Reference r_abs(BlockGraph::ABSOLUTE_REF, 4, b2, 13, 13);
262 : if (b1->SetReference(1, r_abs))
263 : return false;
264 :
265 : BlockGraph::Reference r_rel(BlockGraph::RELATIVE_REF, 4, b2, 17, 17);
266 : if (!b1->SetReference(5, r_rel))
267 : return false;
268 :
269 : BlockGraph::Reference r_file(BlockGraph::FILE_OFFSET_REF, 4, b2, 23, 23);
270 : if (!b1->SetReference(9, r_file))
271 : return false;
272 :
273 : return true;
274 : }
275 :
276 : bool DummyTransformPolicy::BlockIsSafeToBasicBlockDecompose(
277 E : const BlockGraph::Block* block) const {
278 E : DCHECK_NE(reinterpret_cast<BlockGraph::Block*>(NULL), block);
279 E : if (block->type() != BlockGraph::CODE_BLOCK)
280 E : return false;
281 E : return true;
282 E : }
283 :
284 : bool DummyTransformPolicy::ReferenceIsSafeToRedirect(
285 : const BlockGraph::Block* referrer,
286 i : const BlockGraph::Reference& reference) const {
287 i : DCHECK_NE(reinterpret_cast<BlockGraph::Block*>(NULL), referrer);
288 i : return true;
289 i : }
290 :
291 : } // namespace testing
|