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/block_graph.h"
16 :
17 : #include "gmock/gmock.h"
18 : #include "gtest/gtest.h"
19 : #include "syzygy/block_graph/typed_block.h"
20 : #include "syzygy/block_graph/unittest_util.h"
21 : #include "syzygy/core/unittest_util.h"
22 :
23 : namespace block_graph {
24 :
25 : using core::ByteVector;
26 : using core::CreateByteInStream;
27 : using core::CreateByteOutStream;
28 : using core::NativeBinaryInArchive;
29 : using core::NativeBinaryOutArchive;
30 : using core::RelativeAddress;
31 : using core::ScopedInStreamPtr;
32 : using core::ScopedOutStreamPtr;
33 :
34 : const size_t kPtrSize = sizeof(core::RelativeAddress);
35 :
36 E : TEST(SectionTest, CreationAndProperties) {
37 E : BlockGraph::Section section(0, "foo", 1);
38 E : ASSERT_EQ(0, section.id());
39 E : ASSERT_EQ("foo", section.name());
40 E : ASSERT_EQ(1u, section.characteristics());
41 :
42 E : section.set_name("bar");
43 E : ASSERT_EQ("bar", section.name());
44 :
45 E : section.set_characteristic((1 << 5) | (1 << 6));
46 E : ASSERT_EQ((1u | (1 << 5) | (1 << 6)), section.characteristics());
47 :
48 E : section.clear_characteristic(1 | (1<<5));
49 E : ASSERT_EQ(1u << 6, section.characteristics());
50 :
51 E : section.set_characteristics(0);
52 E : ASSERT_EQ(0u, section.characteristics());
53 E : }
54 :
55 E : TEST(SectionTest, Comparison) {
56 E : BlockGraph::Section section0(0, "foo", 0);
57 E : BlockGraph::Section section1(0, "foo", 0);
58 E : BlockGraph::Section section2(1, "bar", 1);
59 :
60 E : EXPECT_EQ(section0, section1);
61 E : EXPECT_NE(section0, section2);
62 E : }
63 :
64 E : TEST(SectionTest, Serialization) {
65 E : BlockGraph::Section section0(0, "foo", 0);
66 E : EXPECT_TRUE(testing::TestSerialization(section0));
67 E : }
68 :
69 : class BlockTest: public testing::Test {
70 : public:
71 E : virtual void SetUp() {
72 E : block_ = image_.AddBlock(kBlockType, kBlockSize, kBlockName);
73 E : ASSERT_TRUE(block_ != NULL);
74 E : }
75 :
76 : protected:
77 : static const BlockGraph::BlockType kBlockType = BlockGraph::CODE_BLOCK;
78 : static const size_t kBlockSize = 0x20;
79 : static const char* kBlockName;
80 : static const uint8 kTestData[];
81 :
82 : BlockGraph image_;
83 : BlockGraph::Block* block_;
84 : };
85 :
86 : const char* BlockTest::kBlockName = "block";
87 : const uint8 BlockTest::kTestData[] = "who's your daddy?";
88 :
89 E : TEST(ReferenceTest, Initialization) {
90 E : BlockGraph block_graph;
91 : BlockGraph::Block* block =
92 E : block_graph.AddBlock(BlockGraph::CODE_BLOCK, 10, "foo");
93 E : BlockGraph::Reference ref(BlockGraph::RELATIVE_REF, 4, block, 0, 0);
94 E : ASSERT_EQ(BlockGraph::RELATIVE_REF, ref.type());
95 E : ASSERT_EQ(4u, ref.size());
96 E : ASSERT_EQ(block, ref.referenced());
97 E : ASSERT_EQ(0, ref.offset());
98 E : ASSERT_EQ(0, ref.base());
99 E : ASSERT_TRUE(ref.IsValid());
100 E : ASSERT_TRUE(ref.IsDirect());
101 E : }
102 :
103 E : TEST(ReferenceTest, IndirectReference) {
104 E : BlockGraph block_graph;
105 : BlockGraph::Block* block =
106 E : block_graph.AddBlock(BlockGraph::CODE_BLOCK, 10, "foo");
107 E : BlockGraph::Reference ref(BlockGraph::RELATIVE_REF, 4, block, -8, 4);
108 E : ASSERT_TRUE(ref.IsValid());
109 E : ASSERT_FALSE(ref.IsDirect());
110 E : }
111 :
112 E : TEST(LabelTest, Initialization) {
113 E : BlockGraph::Label label;
114 E : ASSERT_TRUE(label.name().empty());
115 E : ASSERT_EQ(0u, label.attributes());
116 E : }
117 :
118 E : TEST(LabelTest, InitializationFullConstructor) {
119 E : BlockGraph::Label label("foo", BlockGraph::CODE_LABEL);
120 E : ASSERT_EQ(std::string("foo"), label.name());
121 E : ASSERT_EQ(BlockGraph::CODE_LABEL, label.attributes());
122 E : }
123 :
124 E : TEST(LabelTest, Attributes) {
125 E : BlockGraph::Label label;
126 E : ASSERT_EQ(0u, label.attributes());
127 :
128 E : label.set_attribute(BlockGraph::CODE_LABEL);
129 E : ASSERT_EQ(BlockGraph::CODE_LABEL, label.attributes());
130 :
131 E : label.set_attribute(BlockGraph::JUMP_TABLE_LABEL);
132 : ASSERT_EQ(BlockGraph::CODE_LABEL | BlockGraph::JUMP_TABLE_LABEL,
133 E : label.attributes());
134 :
135 : ASSERT_TRUE(label.has_attributes(
136 E : BlockGraph::CODE_LABEL | BlockGraph::JUMP_TABLE_LABEL));
137 E : ASSERT_TRUE(label.has_attributes(BlockGraph::CODE_LABEL));
138 E : ASSERT_TRUE(label.has_attributes(BlockGraph::JUMP_TABLE_LABEL));
139 E : ASSERT_FALSE(label.has_attributes(BlockGraph::DATA_LABEL));
140 :
141 : ASSERT_TRUE(label.has_any_attributes(
142 E : BlockGraph::CODE_LABEL | BlockGraph::DATA_LABEL));
143 :
144 E : label.set_attributes(BlockGraph::CASE_TABLE_LABEL);
145 E : ASSERT_EQ(BlockGraph::CASE_TABLE_LABEL, label.attributes());
146 :
147 E : label.clear_attribute(BlockGraph::CASE_TABLE_LABEL);
148 E : ASSERT_EQ(0u, label.attributes());
149 E : }
150 :
151 E : TEST(LabelTest, IsValid) {
152 E : BlockGraph::Label label;
153 :
154 : // A label must have some attributes.
155 E : ASSERT_FALSE(label.IsValid());
156 :
157 : // A code label is fine on its own and also with debug and scope labels, but
158 : // not with anything else.
159 E : label.set_attribute(BlockGraph::CODE_LABEL);
160 E : ASSERT_TRUE(label.IsValid());
161 E : label.set_attribute(BlockGraph::DEBUG_START_LABEL);
162 E : ASSERT_TRUE(label.IsValid());
163 E : label.set_attribute(BlockGraph::DEBUG_END_LABEL);
164 E : ASSERT_TRUE(label.IsValid());
165 E : label.set_attribute(BlockGraph::SCOPE_START_LABEL);
166 E : ASSERT_TRUE(label.IsValid());
167 E : label.set_attribute(BlockGraph::SCOPE_END_LABEL);
168 E : ASSERT_TRUE(label.IsValid());
169 E : label.set_attribute(BlockGraph::JUMP_TABLE_LABEL);
170 E : ASSERT_FALSE(label.IsValid());
171 :
172 : // A jump table must be with a data label and nothing else.
173 E : label.set_attributes(BlockGraph::JUMP_TABLE_LABEL);
174 E : ASSERT_FALSE(label.IsValid());
175 E : label.set_attribute(BlockGraph::DATA_LABEL);
176 E : ASSERT_TRUE(label.IsValid());
177 E : label.set_attribute(BlockGraph::CODE_LABEL);
178 E : ASSERT_FALSE(label.IsValid());
179 :
180 : // A case table must be with a data label and nothing else.
181 E : label.set_attributes(BlockGraph::CASE_TABLE_LABEL);
182 E : ASSERT_FALSE(label.IsValid());
183 E : label.set_attribute(BlockGraph::DATA_LABEL);
184 E : ASSERT_TRUE(label.IsValid());
185 E : label.set_attribute(BlockGraph::CODE_LABEL);
186 E : ASSERT_FALSE(label.IsValid());
187 :
188 : // A data label with no case or jump table must be on its own.
189 E : label.set_attributes(BlockGraph::DATA_LABEL);
190 E : ASSERT_TRUE(label.IsValid());
191 E : label.set_attribute(BlockGraph::CODE_LABEL);
192 E : ASSERT_FALSE(label.IsValid());
193 E : }
194 :
195 E : TEST_F(BlockTest, Initialization) {
196 : // Test initialization.
197 E : ASSERT_EQ(kBlockType, block_->type());
198 E : ASSERT_EQ(kBlockSize, block_->size());
199 E : ASSERT_EQ(1, block_->alignment());
200 E : ASSERT_STREQ(kBlockName, block_->name().c_str());
201 E : ASSERT_EQ(kInvalidAddress, block_->addr());
202 E : ASSERT_EQ(BlockGraph::kInvalidSectionId, block_->section());
203 E : ASSERT_EQ(0, block_->attributes());
204 E : ASSERT_EQ(NULL, block_->data());
205 E : ASSERT_EQ(0, block_->data_size());
206 E : ASSERT_FALSE(block_->owns_data());
207 E : }
208 :
209 E : TEST_F(BlockTest, Accessors) {
210 E : ASSERT_NE(BlockGraph::DATA_BLOCK, block_->type());
211 E : block_->set_type(BlockGraph::DATA_BLOCK);
212 E : ASSERT_EQ(BlockGraph::DATA_BLOCK, block_->type());
213 :
214 E : ASSERT_NE(0x10U, block_->size());
215 E : block_->set_size(0x10);
216 E : ASSERT_EQ(0x10U, block_->size());
217 :
218 E : ASSERT_STRNE("foo", block_->name().c_str());
219 E : block_->set_name("foo");
220 E : ASSERT_STREQ("foo", block_->name().c_str());
221 :
222 E : ASSERT_NE(16U, block_->alignment());
223 E : block_->set_alignment(16);
224 E : ASSERT_EQ(16U, block_->alignment());
225 :
226 : // Test accessors.
227 E : block_->set_attribute(0x20);
228 E : ASSERT_EQ(0x20, block_->attributes());
229 E : block_->set_attribute(0x10);
230 E : ASSERT_EQ(0x30, block_->attributes());
231 E : block_->clear_attribute(0x20);
232 E : ASSERT_EQ(0x10, block_->attributes());
233 :
234 E : block_->set_size(sizeof(kTestData));
235 E : block_->SetData(kTestData, sizeof(kTestData));
236 E : ASSERT_EQ(kTestData, block_->data());
237 E : ASSERT_EQ(sizeof(kTestData), block_->data_size());
238 E : ASSERT_FALSE(block_->owns_data());
239 E : }
240 :
241 E : TEST_F(BlockTest, AllocateData) {
242 : // Test AllocateData.
243 E : const size_t kBlockSize = 0x20;
244 E : uint8* data = block_->AllocateData(block_->size());
245 E : ASSERT_TRUE(block_->owns_data());
246 E : ASSERT_EQ(block_->size(), block_->data_size());
247 E : ASSERT_EQ(data, block_->data());
248 :
249 : static const uint8 zeros[kBlockSize] = {};
250 E : ASSERT_EQ(0, memcmp(&zeros[0], data, block_->size()));
251 E : }
252 :
253 E : TEST_F(BlockTest, CopyData) {
254 : // Test CopyData.
255 E : uint8* data = block_->CopyData(sizeof(kTestData), kTestData);
256 E : ASSERT_TRUE(block_->owns_data());
257 E : ASSERT_EQ(sizeof(kTestData), block_->data_size());
258 E : ASSERT_EQ(data, block_->data());
259 E : ASSERT_EQ(0, memcmp(kTestData, data, block_->data_size()));
260 E : }
261 :
262 E : TEST_F(BlockTest, ResizeData) {
263 : // Set the block's data.
264 E : block_->SetData(kTestData, sizeof(kTestData));
265 :
266 : // Shrinking the data should not take ownership.
267 E : const uint8* data = block_->ResizeData(sizeof(kTestData) / 2);
268 E : ASSERT_TRUE(data != NULL);
269 E : ASSERT_TRUE(data == kTestData);
270 E : ASSERT_FALSE(block_->owns_data());
271 :
272 : // Growing the data must always take ownership.
273 E : data = block_->ResizeData(sizeof(kTestData));
274 E : ASSERT_TRUE(data != NULL);
275 E : ASSERT_TRUE(data != kTestData);
276 E : ASSERT_TRUE(block_->owns_data());
277 : // The head of the data should be identical to the input.
278 E : ASSERT_EQ(0, memcmp(data, kTestData, sizeof(kTestData) / 2));
279 : // And the tail should be zeros.
280 : static const uint8 kZeros[sizeof(kTestData) - sizeof(kTestData) / 2] = {};
281 E : ASSERT_EQ(0, memcmp(data + sizeof(kTestData) / 2, kZeros, sizeof(kZeros)));
282 :
283 : // Now grow it from non-owned.
284 E : block_->SetData(kTestData, sizeof(kTestData));
285 E : data = block_->ResizeData(sizeof(kTestData) + sizeof(kZeros));
286 E : ASSERT_TRUE(data != NULL);
287 E : ASSERT_TRUE(data != kTestData);
288 E : ASSERT_TRUE(block_->owns_data());
289 :
290 : // The head of the data should be identical to the input.
291 E : ASSERT_EQ(0, memcmp(data, kTestData, sizeof(kTestData)));
292 : // And the tail should be zeros.
293 E : ASSERT_EQ(0, memcmp(data + sizeof(kTestData), kZeros, sizeof(kZeros)));
294 E : }
295 :
296 E : TEST_F(BlockTest, GetMutableData) {
297 : // Set the block's data.
298 E : block_->SetData(kTestData, sizeof(kTestData));
299 :
300 : // Getting a mutable pointer should copy the data to heap.
301 E : uint8* data = block_->GetMutableData();
302 E : ASSERT_TRUE(data != NULL);
303 E : ASSERT_TRUE(data != kTestData);
304 E : ASSERT_TRUE(block_->owns_data());
305 E : ASSERT_EQ(sizeof(kTestData), block_->data_size());
306 E : ASSERT_EQ(data, block_->data());
307 E : ASSERT_EQ(0, memcmp(kTestData, data, block_->data_size()));
308 :
309 : // Getting the data a second time should return the same pointer.
310 E : ASSERT_EQ(data, block_->GetMutableData());
311 E : }
312 :
313 E : TEST_F(BlockTest, InsertData) {
314 : // Create a block with a labelled array of pointers. Explicitly initialize
315 : // the last one with some data and let the block be longer than its
316 : // explicitly initialized length.
317 : BlockGraph::Block* block1 = image_.AddBlock(
318 E : BlockGraph::CODE_BLOCK, 4 * kPtrSize, "Block1");
319 E : block1->AllocateData(3 * kPtrSize);
320 : block1->source_ranges().Push(BlockGraph::Block::DataRange(0, 4 * kPtrSize),
321 : BlockGraph::Block::SourceRange(
322 E : core::RelativeAddress(0), 4 * kPtrSize));
323 : BlockGraph::Reference outgoing_ref(BlockGraph::RELATIVE_REF,
324 : kPtrSize,
325 : block_,
326 E : 0, 0);
327 E : block1->SetReference(0, outgoing_ref);
328 E : block1->SetReference(kPtrSize, outgoing_ref);
329 E : block1->SetLabel(0, "Pointer1", BlockGraph::DATA_LABEL);
330 E : block1->SetLabel(kPtrSize, "Pointer2", BlockGraph::DATA_LABEL);
331 E : block1->SetLabel(2 * kPtrSize, "Pointer3", BlockGraph::DATA_LABEL);
332 E : TypedBlock<uint32> data1;
333 E : ASSERT_TRUE(data1.Init(0, block1));
334 E : data1[0] = 0xAAAAAAAA;
335 E : data1[1] = 0xBBBBBBBB;
336 E : data1[2] = 0xCCCCCCCC;
337 :
338 : // Create a block with a pointer to the first entry of block1.
339 : BlockGraph::Block* block2 = image_.AddBlock(
340 E : BlockGraph::CODE_BLOCK, kPtrSize, "Block2");
341 : block2->SetReference(0, BlockGraph::Reference(BlockGraph::RELATIVE_REF,
342 : kPtrSize,
343 : block1,
344 E : 0, 0));
345 :
346 : // Create a block with a pointer to the second entry of block1.
347 : BlockGraph::Block* block3 = image_.AddBlock(
348 E : BlockGraph::CODE_BLOCK, kPtrSize, "Block3");
349 : block3->SetReference(0, BlockGraph::Reference(BlockGraph::RELATIVE_REF,
350 : kPtrSize,
351 : block1,
352 E : kPtrSize, kPtrSize));
353 :
354 : // Insert a new pointer entry in between the first and second entries.
355 E : block1->InsertData(kPtrSize, kPtrSize, false);
356 :
357 : // Ensure the data_size and block size are as expected.
358 E : EXPECT_EQ(5 * kPtrSize, block1->size());
359 E : EXPECT_EQ(4 * kPtrSize, block1->data_size());
360 :
361 : // Ensure the source ranges are as expected.
362 E : BlockGraph::Block::SourceRanges expected_src_ranges;
363 : expected_src_ranges.Push(
364 : BlockGraph::Block::DataRange(0, kPtrSize),
365 E : BlockGraph::Block::SourceRange(core::RelativeAddress(0), kPtrSize));
366 : expected_src_ranges.Push(
367 : BlockGraph::Block::DataRange(2 * kPtrSize, 3 * kPtrSize),
368 : BlockGraph::Block::SourceRange(core::RelativeAddress(kPtrSize),
369 E : 3 * kPtrSize));
370 : EXPECT_THAT(expected_src_ranges.range_pairs(),
371 E : testing::ContainerEq(block1->source_ranges().range_pairs()));
372 :
373 : // Ensure that the contents of the block's data are as expected.
374 E : EXPECT_EQ(0xAAAAAAAAu, data1[0]);
375 E : EXPECT_EQ(0x00000000u, data1[1]);
376 E : EXPECT_EQ(0xBBBBBBBBu, data1[2]);
377 E : EXPECT_EQ(0xCCCCCCCCu, data1[3]);
378 :
379 : // Ensure that the labels have been shifted appropriately.
380 E : BlockGraph::Block::LabelMap expected_labels;
381 : expected_labels.insert(std::make_pair(
382 : 0 * kPtrSize,
383 E : BlockGraph::Label("Pointer1", BlockGraph::DATA_LABEL)));
384 : expected_labels.insert(std::make_pair(
385 : 2 * kPtrSize,
386 E : BlockGraph::Label("Pointer2", BlockGraph::DATA_LABEL)));
387 : expected_labels.insert(std::make_pair(
388 : 3 * kPtrSize,
389 E : BlockGraph::Label("Pointer3", BlockGraph::DATA_LABEL)));
390 E : EXPECT_THAT(expected_labels, testing::ContainerEq(block1->labels()));
391 :
392 : // Ensure that the referrers are as expected.
393 E : BlockGraph::Block::ReferrerSet expected_referrers;
394 E : expected_referrers.insert(std::make_pair(block2, 0));
395 E : expected_referrers.insert(std::make_pair(block3, 0));
396 E : EXPECT_THAT(expected_referrers, testing::ContainerEq(block1->referrers()));
397 :
398 : BlockGraph::Reference expected_ref(BlockGraph::RELATIVE_REF,
399 : kPtrSize,
400 : block1,
401 E : 0, 0);
402 E : BlockGraph::Reference actual_ref;
403 E : EXPECT_TRUE(block2->GetReference(0, &actual_ref));
404 E : EXPECT_EQ(expected_ref, actual_ref);
405 :
406 : expected_ref = BlockGraph::Reference(BlockGraph::RELATIVE_REF,
407 : kPtrSize,
408 : block1,
409 E : 2 * kPtrSize, 2 * kPtrSize);
410 E : EXPECT_TRUE(block3->GetReference(0, &actual_ref));
411 E : EXPECT_EQ(expected_ref, actual_ref);
412 :
413 : // Ensure that the references have been shifted appropriately.
414 E : BlockGraph::Block::ReferenceMap expected_references;
415 E : expected_references.insert(std::make_pair(0, outgoing_ref));
416 E : expected_references.insert(std::make_pair(2 * kPtrSize, outgoing_ref));
417 E : EXPECT_EQ(expected_references, block1->references());
418 E : }
419 :
420 E : TEST_F(BlockTest, InsertDataImplicit) {
421 : BlockGraph::Block* block1 = image_.AddBlock(
422 E : BlockGraph::CODE_BLOCK, 40, "Block1");
423 E : block1->AllocateData(30);
424 :
425 : // Do an insert data in the implicitly initialized portion of the block.
426 E : block1->InsertData(30, 10, false);
427 :
428 : // We expect the block to have grown, but the data size should still be the
429 : // same.
430 E : EXPECT_EQ(50u, block1->size());
431 E : EXPECT_EQ(30u, block1->data_size());
432 E : }
433 :
434 E : TEST_F(BlockTest, InsertDataImplicitForceAllocation) {
435 : BlockGraph::Block* block1 = image_.AddBlock(
436 E : BlockGraph::CODE_BLOCK, 40, "Block1");
437 E : block1->AllocateData(30);
438 :
439 : // Do an insert data in the implicitly initialized portion of the block, but
440 : // force data to be allocated.
441 E : block1->InsertData(30, 10, true);
442 :
443 : // We expect the block to have grown, as well as the data size.
444 E : EXPECT_EQ(50u, block1->size());
445 E : EXPECT_EQ(40u, block1->data_size());
446 E : }
447 :
448 E : TEST_F(BlockTest, InsertDataForceAllocateDoesNotShorten) {
449 : BlockGraph::Block* block1 = image_.AddBlock(
450 E : BlockGraph::CODE_BLOCK, 40, "Block1");
451 E : block1->AllocateData(30);
452 :
453 : // Insert data in the allocated region, but request allocation to be forced.
454 E : block1->InsertData(0, 10, true);
455 :
456 E : EXPECT_EQ(50u, block1->size());
457 E : EXPECT_EQ(40u, block1->data_size());
458 E : }
459 :
460 E : TEST_F(BlockTest, InsertDataWithSelfReference) {
461 : BlockGraph::Block* block1 = image_.AddBlock(
462 E : BlockGraph::CODE_BLOCK, 40, "Block1");
463 :
464 E : BlockGraph::Reference ref(BlockGraph::ABSOLUTE_REF, kPtrSize, block1, 0, 0);
465 : // Insert a self-reference to the block.
466 E : block1->SetReference(20, ref);
467 :
468 : // Insert some data before the reference.
469 E : block1->InsertData(10, 10, false);
470 :
471 E : BlockGraph::Reference moved_ref;
472 E : ASSERT_TRUE(block1->GetReference(30, &moved_ref));
473 E : ASSERT_EQ(ref, moved_ref);
474 :
475 E : BlockGraph::Block::ReferrerSet expected;
476 E : expected.insert(std::make_pair(block1, 30));
477 E : ASSERT_EQ(block1->referrers(), expected);
478 E : }
479 :
480 E : TEST_F(BlockTest, RemoveData) {
481 : // Create a block with a labelled array of pointers. Explicitly initialize
482 : // the last one with some data and let the block be longer than its
483 : // explicitly initialized length.
484 : BlockGraph::Block* block1 = image_.AddBlock(
485 E : BlockGraph::CODE_BLOCK, 6 * kPtrSize, "Block1");
486 E : block1->AllocateData(3 * kPtrSize);
487 : block1->source_ranges().Push(BlockGraph::Block::DataRange(0, 6 * kPtrSize),
488 : BlockGraph::Block::SourceRange(
489 E : core::RelativeAddress(0), 6 * kPtrSize));
490 : BlockGraph::Reference outgoing_ref(BlockGraph::RELATIVE_REF,
491 : kPtrSize,
492 : block_,
493 E : 0, 0);
494 E : block1->SetReference(0, outgoing_ref);
495 E : block1->SetReference(2 * kPtrSize, outgoing_ref);
496 E : block1->SetReference(5 * kPtrSize, outgoing_ref);
497 E : block1->SetLabel(0, "Pointer1", BlockGraph::DATA_LABEL);
498 E : block1->SetLabel(2 * kPtrSize, "Pointer3", BlockGraph::DATA_LABEL);
499 E : block1->SetLabel(3 * kPtrSize, "EndOfPointers", BlockGraph::DATA_LABEL);
500 E : TypedBlock<uint32> data1;
501 E : ASSERT_TRUE(data1.Init(0, block1));
502 E : data1[0] = 0xAAAAAAAA;
503 E : data1[1] = 0xBBBBBBBB;
504 E : data1[2] = 0xCCCCCCCC;
505 :
506 : // Create a block with a pointer to the first entry of block1.
507 : BlockGraph::Block* block2 = image_.AddBlock(
508 E : BlockGraph::CODE_BLOCK, kPtrSize, "Block2");
509 : block2->SetReference(0, BlockGraph::Reference(BlockGraph::RELATIVE_REF,
510 : kPtrSize,
511 : block1,
512 E : 0, 0));
513 :
514 : // Create a block with a pointer to the third entry of block1.
515 : BlockGraph::Block* block3 = image_.AddBlock(
516 E : BlockGraph::CODE_BLOCK, kPtrSize, "Block4");
517 : block3->SetReference(0, BlockGraph::Reference(BlockGraph::RELATIVE_REF,
518 : kPtrSize,
519 : block1,
520 E : 2 * kPtrSize, 2 * kPtrSize));
521 :
522 : // Create a block with a pointer to the fifth entry of block1.
523 : BlockGraph::Block* block4 = image_.AddBlock(
524 E : BlockGraph::CODE_BLOCK, kPtrSize, "Block3");
525 : block4->SetReference(0, BlockGraph::Reference(BlockGraph::RELATIVE_REF,
526 : kPtrSize,
527 : block1,
528 E : 4 * kPtrSize, 4 * kPtrSize));
529 :
530 : // Trying to remove the fourth entry should fail because it contains a label.
531 E : EXPECT_FALSE(block1->RemoveData(3 * kPtrSize, kPtrSize));
532 :
533 : // Trying to remove the fifth entry should fail because there is a referrer
534 : // pointing to it.
535 E : EXPECT_FALSE(block1->RemoveData(4 * kPtrSize, kPtrSize));
536 :
537 : // Trying to remove the sixth entry should fail because it contains a
538 : // reference.
539 E : EXPECT_FALSE(block1->RemoveData(5 * kPtrSize, kPtrSize));
540 :
541 : // Finally, we should be able to delete the second entry.
542 E : EXPECT_TRUE(block1->RemoveData(kPtrSize, kPtrSize));
543 :
544 : // Ensure the data_size and block size are as expected.
545 E : EXPECT_EQ(5 * kPtrSize, block1->size());
546 E : EXPECT_EQ(2 * kPtrSize, block1->data_size());
547 :
548 : // Ensure the source ranges are as expected.
549 E : BlockGraph::Block::SourceRanges expected_src_ranges;
550 : expected_src_ranges.Push(
551 : BlockGraph::Block::DataRange(0, kPtrSize),
552 E : BlockGraph::Block::SourceRange(core::RelativeAddress(0), kPtrSize));
553 : expected_src_ranges.Push(
554 : BlockGraph::Block::DataRange(kPtrSize, 4 * kPtrSize),
555 : BlockGraph::Block::SourceRange(core::RelativeAddress(2 * kPtrSize),
556 E : 4 * kPtrSize));
557 : EXPECT_THAT(expected_src_ranges.range_pairs(),
558 E : testing::ContainerEq(block1->source_ranges().range_pairs()));
559 :
560 : // Ensure that the contents of the block's data are as expected.
561 E : EXPECT_EQ(0xAAAAAAAAu, data1[0]);
562 E : EXPECT_EQ(0xCCCCCCCCu, data1[1]);
563 :
564 : // Ensure that the labels have been shifted appropriately.
565 E : BlockGraph::Block::LabelMap expected_labels;
566 : expected_labels.insert(std::make_pair(
567 : 0 * kPtrSize,
568 E : BlockGraph::Label("Pointer1", BlockGraph::DATA_LABEL)));
569 : expected_labels.insert(std::make_pair(
570 : 1 * kPtrSize,
571 E : BlockGraph::Label("Pointer3", BlockGraph::DATA_LABEL)));
572 : expected_labels.insert(std::make_pair(
573 : 2 * kPtrSize,
574 E : BlockGraph::Label("EndOfPointers", BlockGraph::DATA_LABEL)));
575 E : EXPECT_THAT(expected_labels, testing::ContainerEq(block1->labels()));
576 :
577 : // Ensure that the referrers are as expected.
578 E : BlockGraph::Block::ReferrerSet expected_referrers;
579 E : expected_referrers.insert(std::make_pair(block2, 0));
580 E : expected_referrers.insert(std::make_pair(block3, 0));
581 E : expected_referrers.insert(std::make_pair(block4, 0));
582 E : EXPECT_THAT(expected_referrers, testing::ContainerEq(block1->referrers()));
583 :
584 : BlockGraph::Reference expected_ref(BlockGraph::RELATIVE_REF,
585 : kPtrSize,
586 : block1,
587 E : 0, 0);
588 E : BlockGraph::Reference actual_ref;
589 E : EXPECT_TRUE(block2->GetReference(0, &actual_ref));
590 E : EXPECT_EQ(expected_ref, actual_ref);
591 :
592 : expected_ref = BlockGraph::Reference(BlockGraph::RELATIVE_REF,
593 : kPtrSize,
594 : block1,
595 E : kPtrSize, kPtrSize);
596 E : EXPECT_TRUE(block3->GetReference(0, &actual_ref));
597 E : EXPECT_EQ(expected_ref, actual_ref);
598 :
599 : expected_ref = BlockGraph::Reference(BlockGraph::RELATIVE_REF,
600 : kPtrSize,
601 : block1,
602 E : 3 * kPtrSize, 3 * kPtrSize);
603 E : EXPECT_TRUE(block4->GetReference(0, &actual_ref));
604 E : EXPECT_EQ(expected_ref, actual_ref);
605 :
606 : // Ensure that the references have been shifted appropriately.
607 E : BlockGraph::Block::ReferenceMap expected_references;
608 E : expected_references.insert(std::make_pair(0, outgoing_ref));
609 E : expected_references.insert(std::make_pair(kPtrSize, outgoing_ref));
610 E : expected_references.insert(std::make_pair(4 * kPtrSize, outgoing_ref));
611 E : EXPECT_EQ(expected_references, block1->references());
612 E : }
613 :
614 E : TEST_F(BlockTest, RemoveDataPartlyImplicit) {
615 : BlockGraph::Block* block1 = image_.AddBlock(
616 E : BlockGraph::CODE_BLOCK, 40, "Block1");
617 E : block1->AllocateData(30);
618 :
619 : // Remove data that spans both the initialized and implicit parts of the
620 : // block.
621 E : EXPECT_TRUE(block1->RemoveData(25, 10));
622 :
623 : // We expect both the block and the data size to have shrunk.
624 E : EXPECT_EQ(30u, block1->size());
625 E : EXPECT_EQ(25u, block1->data_size());
626 E : }
627 :
628 E : TEST_F(BlockTest, RemoveDataImplicit) {
629 : BlockGraph::Block* block1 = image_.AddBlock(
630 E : BlockGraph::CODE_BLOCK, 40, "Block1");
631 E : block1->AllocateData(30);
632 :
633 : // Do an remove data in the implicitly initialized portion of the block.
634 E : EXPECT_TRUE(block1->RemoveData(30, 5));
635 :
636 : // We expect the block to have shrunk, but the data size should still be the
637 : // same.
638 E : EXPECT_EQ(35u, block1->size());
639 E : EXPECT_EQ(30u, block1->data_size());
640 E : }
641 :
642 E : TEST_F(BlockTest, RemoveDataWithSelfReference) {
643 : BlockGraph::Block* block1 = image_.AddBlock(
644 E : BlockGraph::CODE_BLOCK, 50, "Block1");
645 :
646 E : BlockGraph::Reference ref(BlockGraph::ABSOLUTE_REF, kPtrSize, block1, 0, 0);
647 : // Insert a self-reference to the block.
648 E : block1->SetReference(40, ref);
649 :
650 : // Remove some data before the reference.
651 E : block1->RemoveData(10, 10);
652 :
653 E : BlockGraph::Reference moved_ref;
654 E : ASSERT_TRUE(block1->GetReference(30, &moved_ref));
655 E : ASSERT_EQ(ref, moved_ref);
656 :
657 E : BlockGraph::Block::ReferrerSet expected;
658 E : expected.insert(std::make_pair(block1, 30));
659 E : ASSERT_EQ(block1->referrers(), expected);
660 E : }
661 :
662 E : TEST_F(BlockTest, InsertOrRemoveDataSameSizeNoAllocate) {
663 : BlockGraph::Block* block1 = image_.AddBlock(
664 E : BlockGraph::DATA_BLOCK, 40, "Block1");
665 :
666 E : EXPECT_TRUE(block1->InsertOrRemoveData(0, 20, 20, false));
667 E : EXPECT_EQ(40u, block1->size());
668 E : EXPECT_EQ(0u, block1->data_size());
669 E : }
670 :
671 E : TEST_F(BlockTest, InsertOrRemoveDataSameSizeAllocate) {
672 : BlockGraph::Block* block1 = image_.AddBlock(
673 E : BlockGraph::DATA_BLOCK, 40, "Block1");
674 :
675 E : EXPECT_TRUE(block1->InsertOrRemoveData(0, 20, 20, true));
676 E : EXPECT_EQ(40u, block1->size());
677 E : EXPECT_EQ(20u, block1->data_size());
678 E : }
679 :
680 E : TEST_F(BlockTest, InsertOrRemoveGrowNoAllocate) {
681 : BlockGraph::Block* block1 = image_.AddBlock(
682 E : BlockGraph::DATA_BLOCK, 40, "Block1");
683 :
684 E : EXPECT_TRUE(block1->InsertOrRemoveData(0, 10, 20, false));
685 E : EXPECT_EQ(50u, block1->size());
686 E : EXPECT_EQ(0u, block1->data_size());
687 E : }
688 :
689 E : TEST_F(BlockTest, InsertOrRemoveGrowAllocate) {
690 : BlockGraph::Block* block1 = image_.AddBlock(
691 E : BlockGraph::DATA_BLOCK, 40, "Block1");
692 :
693 E : EXPECT_TRUE(block1->InsertOrRemoveData(0, 10, 20, true));
694 E : EXPECT_EQ(50u, block1->size());
695 E : EXPECT_EQ(20u, block1->data_size());
696 E : }
697 :
698 E : TEST_F(BlockTest, InsertOrRemoveShrinkNoAllocate) {
699 : BlockGraph::Block* block1 = image_.AddBlock(
700 E : BlockGraph::DATA_BLOCK, 40, "Block1");
701 E : block1->AllocateData(15);
702 :
703 E : EXPECT_TRUE(block1->InsertOrRemoveData(0, 20, 10, false));
704 E : EXPECT_EQ(30u, block1->size());
705 E : EXPECT_EQ(10u, block1->data_size());
706 E : }
707 :
708 E : TEST_F(BlockTest, InsertOrRemoveShrinkAllocate) {
709 : BlockGraph::Block* block1 = image_.AddBlock(
710 E : BlockGraph::DATA_BLOCK, 40, "Block1");
711 :
712 E : EXPECT_TRUE(block1->InsertOrRemoveData(0, 20, 10, true));
713 E : EXPECT_EQ(30u, block1->size());
714 E : EXPECT_EQ(10u, block1->data_size());
715 E : }
716 :
717 E : TEST_F(BlockTest, HasExternalReferrers) {
718 : // Create block1 that refers to itself. It has no external referrers.
719 : BlockGraph::Block* block1 = image_.AddBlock(
720 E : BlockGraph::DATA_BLOCK, 40, "Block1");
721 E : ASSERT_TRUE(block1 != NULL);
722 : EXPECT_TRUE(block1->SetReference(
723 E : 0, BlockGraph::Reference(BlockGraph::ABSOLUTE_REF, 4, block1, 0, 0)));
724 E : EXPECT_FALSE(block1->HasExternalReferrers());
725 :
726 : // Create a second block that refers to block1.
727 : BlockGraph::Block* block2 = image_.AddBlock(
728 E : BlockGraph::DATA_BLOCK, 40, "Block2");
729 E : ASSERT_TRUE(block2 != NULL);
730 : EXPECT_TRUE(block2->SetReference(
731 E : 0, BlockGraph::Reference(BlockGraph::ABSOLUTE_REF, 4, block1, 0, 0)));
732 :
733 : // There should now be an external referrer to block1.
734 E : EXPECT_TRUE(block1->HasExternalReferrers());
735 E : }
736 :
737 E : TEST_F(BlockTest, RemoveAllReferences) {
738 : // Create block1 that refers to itself. It has no external referrers.
739 : BlockGraph::Block* block1 = image_.AddBlock(
740 E : BlockGraph::DATA_BLOCK, 40, "Block1");
741 E : ASSERT_TRUE(block1 != NULL);
742 : EXPECT_TRUE(block1->SetReference(
743 E : 0, BlockGraph::Reference(BlockGraph::ABSOLUTE_REF, 4, block1, 0, 0)));
744 :
745 : // Create a second block for block1 to refer to.
746 : BlockGraph::Block* block2 = image_.AddBlock(
747 E : BlockGraph::DATA_BLOCK, 40, "Block2");
748 E : ASSERT_TRUE(block2 != NULL);
749 : EXPECT_TRUE(block1->SetReference(
750 E : 4, BlockGraph::Reference(BlockGraph::ABSOLUTE_REF, 4, block2, 0, 0)));
751 :
752 : // Verify that the references are as expected.
753 E : EXPECT_EQ(2U, block1->references().size());
754 E : EXPECT_EQ(1U, block1->referrers().size());
755 E : EXPECT_EQ(1U, block2->referrers().size());
756 :
757 : // Remove all references from block1.
758 E : EXPECT_TRUE(block1->RemoveAllReferences());
759 :
760 : // Verify that the references are as expected.
761 E : EXPECT_EQ(0U, block1->references().size());
762 E : EXPECT_EQ(0U, block1->referrers().size());
763 E : EXPECT_EQ(0U, block2->referrers().size());
764 E : }
765 :
766 E : TEST(BlockGraphTest, BlockTypeToString) {
767 E : for (int type = 0; type < BlockGraph::BLOCK_TYPE_MAX; ++type) {
768 : BlockGraph::BlockType block_type =
769 E : static_cast<BlockGraph::BlockType>(type);
770 E : EXPECT_TRUE(BlockGraph::BlockTypeToString(block_type) != NULL);
771 E : }
772 E : }
773 :
774 E : TEST(BlockGraphTest, LabelAttributesToString) {
775 E : BlockGraph::LabelAttributes label_attr = 1;
776 E : for (; label_attr != BlockGraph::LABEL_ATTRIBUTES_MAX; label_attr <<= 1) {
777 E : std::string s = BlockGraph::LabelAttributesToString(label_attr);
778 E : EXPECT_FALSE(s.empty());
779 E : }
780 :
781 E : label_attr = BlockGraph::LABEL_ATTRIBUTES_MAX - 1;
782 E : std::string s = BlockGraph::LabelAttributesToString(label_attr);
783 E : EXPECT_FALSE(s.empty());
784 E : }
785 :
786 E : TEST(BlockGraphTest, AddSections) {
787 E : BlockGraph image;
788 E : ASSERT_EQ(0u, image.sections().size());
789 :
790 E : BlockGraph::Section* section0 = image.AddSection("foo", 0);
791 E : ASSERT_TRUE(section0 != NULL);
792 E : ASSERT_EQ("foo", section0->name());
793 E : ASSERT_EQ(0u, section0->characteristics());
794 E : ASSERT_EQ(1u, image.sections().size());
795 :
796 E : BlockGraph::Section* section1 = image.AddSection("foo", 0);
797 E : ASSERT_TRUE(section1 != NULL);
798 E : ASSERT_EQ("foo", section1->name());
799 E : ASSERT_EQ(0u, section1->characteristics());
800 E : ASSERT_EQ(2u, image.sections().size());
801 :
802 : // This section has the same name and characteristics, but it should not be
803 : // the same section as section0.
804 E : EXPECT_TRUE(section0 != section1);
805 E : EXPECT_NE(section0->id(), section1->id());
806 :
807 E : BlockGraph::Section* section2 = image.FindOrAddSection("foo", 1);
808 E : ASSERT_TRUE(section2 != NULL);
809 E : ASSERT_EQ("foo", section2->name());
810 E : ASSERT_EQ(1u, section2->characteristics());
811 E : ASSERT_EQ(2u, image.sections().size());
812 :
813 : // This should be the same as section0, the first instance of a section
814 : // with name 'foo'.
815 E : EXPECT_EQ(section0, section2);
816 :
817 E : BlockGraph::Section* section3 = image.FindOrAddSection("bar", 1);
818 E : ASSERT_TRUE(section3 != NULL);
819 E : ASSERT_EQ("bar", section3->name());
820 E : ASSERT_EQ(1u, section3->characteristics());
821 E : ASSERT_EQ(3u, image.sections().size());
822 :
823 : // Test out FindSection.
824 E : EXPECT_EQ(section0, image.FindSection("foo"));
825 E : EXPECT_EQ(section3, image.FindSection("bar"));
826 E : EXPECT_TRUE(image.FindSection("baz") == NULL);
827 E : }
828 :
829 E : TEST(BlockGraphTest, RemoveSection) {
830 E : BlockGraph image;
831 E : ASSERT_EQ(0u, image.sections().size());
832 :
833 E : BlockGraph::Section* section0 = image.AddSection("foo", 0);
834 E : ASSERT_TRUE(section0 != NULL);
835 E : ASSERT_EQ(1u, image.sections().size());
836 :
837 E : BlockGraph::Section* section1 = image.AddSection("bar", 0);
838 E : ASSERT_TRUE(section1 != NULL);
839 E : ASSERT_EQ(2u, image.sections().size());
840 :
841 : // We should not be able to delete a non-existent section.
842 E : EXPECT_FALSE(image.RemoveSectionById(BlockGraph::kInvalidSectionId));
843 E : ASSERT_EQ(2u, image.sections().size());
844 :
845 : // Deleting normal sections should work just fine.
846 :
847 E : EXPECT_TRUE(image.RemoveSectionById(section0->id()));
848 E : ASSERT_EQ(1u, image.sections().size());
849 :
850 E : EXPECT_TRUE(image.RemoveSection(section1));
851 E : ASSERT_EQ(0u, image.sections().size());
852 E : }
853 :
854 E : TEST(BlockGraphTest, RemoveBlock) {
855 E : BlockGraph image;
856 :
857 : // Add some blocks to the image.
858 E : BlockGraph::Block* b1 = image.AddBlock(BlockGraph::CODE_BLOCK, 0x20, "b1");
859 E : BlockGraph::Block* b2 = image.AddBlock(BlockGraph::CODE_BLOCK, 0x20, "b2");
860 E : BlockGraph::Block* b3 = image.AddBlock(BlockGraph::CODE_BLOCK, 0x20, "b3");
861 E : BlockGraph::Block* b4 = image.AddBlock(BlockGraph::CODE_BLOCK, 0x20, "b4");
862 E : ASSERT_TRUE(b1 != NULL);
863 E : ASSERT_TRUE(b2 != NULL);
864 E : ASSERT_TRUE(b3 != NULL);
865 E : ASSERT_TRUE(b4 != NULL);
866 E : EXPECT_EQ(4u, image.blocks().size());
867 :
868 : // Add a reference from block 1 to block 2.
869 E : BlockGraph::Reference ref12(BlockGraph::PC_RELATIVE_REF, 1, b2, 9, 9);
870 E : ASSERT_TRUE(b1->SetReference(0, ref12));
871 E : EXPECT_THAT(b1->references(), testing::Contains(std::make_pair(0, ref12)));
872 E : EXPECT_THAT(b2->referrers(), testing::Contains(std::make_pair(b1, 0)));
873 E : EXPECT_EQ(1u, b1->references().size());
874 E : EXPECT_EQ(1u, b2->referrers().size());
875 :
876 : // Try to delete Block 1. This should fail because it has references.
877 E : ASSERT_FALSE(image.RemoveBlock(b1));
878 E : EXPECT_EQ(4u, image.blocks().size());
879 :
880 : // Try to delete Block 2. This should fail because it has referrers.
881 E : ASSERT_FALSE(image.RemoveBlockById(b2->id()));
882 E : EXPECT_EQ(4u, image.blocks().size());
883 :
884 : // Try to delete a block that doesn't belong to the block graph. This
885 : // should fail.
886 E : BlockGraph other_image;
887 : BlockGraph::Block* other_block =
888 E : other_image.AddBlock(BlockGraph::CODE_BLOCK, 0x20, "other_block");
889 E : ASSERT_FALSE(image.RemoveBlock(other_block));
890 E : EXPECT_EQ(4u, image.blocks().size());
891 :
892 : // Try to delete a block with an invalid ID. This should fail.
893 E : ASSERT_FALSE(image.RemoveBlockById(15));
894 E : EXPECT_EQ(4u, image.blocks().size());
895 :
896 : // Delete block 3.
897 E : ASSERT_TRUE(image.RemoveBlock(b3));
898 E : EXPECT_EQ(3u, image.blocks().size());
899 :
900 : // Delete block 4.
901 E : ASSERT_TRUE(image.RemoveBlockById(b4->id()));
902 E : EXPECT_EQ(2u, image.blocks().size());
903 E : }
904 :
905 E : TEST(BlockGraphTest, References) {
906 E : BlockGraph image;
907 :
908 E : BlockGraph::Block* b1 = image.AddBlock(BlockGraph::CODE_BLOCK, 0x20, "b1");
909 E : BlockGraph::Block* b2 = image.AddBlock(BlockGraph::CODE_BLOCK, 0x20, "b2");
910 E : BlockGraph::Block* b3 = image.AddBlock(BlockGraph::CODE_BLOCK, 0x20, "b3");
911 E : ASSERT_TRUE(b1 != NULL);
912 E : ASSERT_TRUE(b2 != NULL);
913 E : ASSERT_TRUE(b3 != NULL);
914 :
915 E : ASSERT_TRUE(b1->references().empty());
916 E : ASSERT_TRUE(b1->referrers().empty());
917 E : ASSERT_TRUE(b2->references().empty());
918 E : ASSERT_TRUE(b2->referrers().empty());
919 E : ASSERT_TRUE(b3->references().empty());
920 E : ASSERT_TRUE(b3->referrers().empty());
921 :
922 E : BlockGraph::Reference dummy;
923 E : ASSERT_FALSE(dummy.IsValid());
924 :
925 : // Add the first reference, and test that we get a backref.
926 E : BlockGraph::Reference r_pc(BlockGraph::PC_RELATIVE_REF, 1, b2, 9, 9);
927 E : ASSERT_TRUE(r_pc.IsValid());
928 E : ASSERT_EQ(BlockGraph::PC_RELATIVE_REF, r_pc.type());
929 E : ASSERT_EQ(1, r_pc.size());
930 E : ASSERT_EQ(b2, r_pc.referenced());
931 E : ASSERT_EQ(9, r_pc.offset());
932 :
933 E : ASSERT_TRUE(b1->SetReference(0, r_pc));
934 E : EXPECT_THAT(b2->referrers(), testing::Contains(std::make_pair(b1, 0)));
935 :
936 E : ASSERT_TRUE(b1->SetReference(1, r_pc));
937 E : EXPECT_THAT(b2->referrers(), testing::Contains(std::make_pair(b1, 1)));
938 :
939 E : BlockGraph::Reference r_abs(BlockGraph::ABSOLUTE_REF, 4, b2, 13, 13);
940 E : ASSERT_FALSE(b1->SetReference(1, r_abs));
941 E : BlockGraph::Reference r_rel(BlockGraph::RELATIVE_REF, 4, b2, 17, 17);
942 E : ASSERT_TRUE(b1->SetReference(5, r_rel));
943 E : BlockGraph::Reference r_file(BlockGraph::FILE_OFFSET_REF, 4, b2, 23, 23);
944 E : ASSERT_TRUE(b1->SetReference(9, r_file));
945 :
946 : // Test that the reference map is as expected.
947 E : BlockGraph::Block::ReferenceMap expected;
948 E : expected.insert(std::make_pair(0, r_pc));
949 E : expected.insert(std::make_pair(1, r_abs));
950 E : expected.insert(std::make_pair(5, r_rel));
951 E : expected.insert(std::make_pair(9, r_file));
952 E : EXPECT_THAT(b1->references(), testing::ContainerEq(expected));
953 :
954 : // Test reference transfer.
955 : // This should fail, as all the references will fall outside b3.
956 : // TODO(chrisha): We need to create a logging MessageHandler that we can
957 : // put test expectations on. This test is meant to fail, but we don't
958 : // want to see the error message it would produce! Ideally, this should
959 : // live in 'syzygy/testing' or something of the like, as it could be
960 : // used across many unittests. For now, we simply disable logging for
961 : // this test.
962 E : int old_level = logging::GetMinLogLevel();
963 E : logging::SetMinLogLevel(logging::LOG_FATAL);
964 E : ASSERT_FALSE(b2->TransferReferrers(b3->size(), b3));
965 E : logging::SetMinLogLevel(old_level);
966 :
967 : // Now move the references from b2 to b3
968 E : ASSERT_TRUE(b2->TransferReferrers(0, b3));
969 : // Test that b2 no longer has referrers.
970 E : EXPECT_THAT(b2->referrers(), BlockGraph::Block::ReferrerSet());
971 :
972 : // Test that the references transferred as expected.
973 E : expected.clear();
974 : expected.insert(std::make_pair(0,
975 E : BlockGraph::Reference(BlockGraph::PC_RELATIVE_REF, 1, b3, 9, 9)));
976 : expected.insert(std::make_pair(1,
977 E : BlockGraph::Reference(BlockGraph::ABSOLUTE_REF, 4, b3, 13, 13)));
978 : expected.insert(std::make_pair(5,
979 E : BlockGraph::Reference(BlockGraph::RELATIVE_REF, 4, b3, 17, 17)));
980 : expected.insert(std::make_pair(9,
981 E : BlockGraph::Reference(BlockGraph::FILE_OFFSET_REF, 4, b3, 23, 23)));
982 E : EXPECT_THAT(b1->references(), testing::ContainerEq(expected));
983 :
984 : // Remove the references.
985 E : ASSERT_TRUE(b1->RemoveReference(0));
986 E : ASSERT_TRUE(b1->RemoveReference(1));
987 E : ASSERT_TRUE(b1->RemoveReference(5));
988 E : ASSERT_TRUE(b1->RemoveReference(9));
989 E : EXPECT_THAT(b1->references(), BlockGraph::Block::ReferenceMap());
990 :
991 E : EXPECT_THAT(b2->referrers(), BlockGraph::Block::ReferrerSet());
992 E : }
993 :
994 E : TEST(BlockGraphTest, Labels) {
995 E : BlockGraph image;
996 :
997 : BlockGraph::Block* block =
998 E : image.AddBlock(BlockGraph::CODE_BLOCK, 0x20, "labeled");
999 E : ASSERT_TRUE(block->labels().empty());
1000 E : for (int i = 0; i < 0x20; ++i) {
1001 E : BlockGraph::Label label;
1002 E : ASSERT_FALSE(block->HasLabel(i));
1003 E : EXPECT_FALSE(block->GetLabel(i, &label));
1004 E : EXPECT_FALSE(block->RemoveLabel(i));
1005 E : }
1006 :
1007 E : EXPECT_TRUE(block->SetLabel(13, "foo", BlockGraph::DATA_LABEL));
1008 E : EXPECT_FALSE(block->SetLabel(13, "foo2", BlockGraph::DATA_LABEL));
1009 :
1010 E : EXPECT_TRUE(block->SetLabel(17, "bar", BlockGraph::CODE_LABEL));
1011 E : EXPECT_FALSE(block->SetLabel(17, "bar2", BlockGraph::CODE_LABEL));
1012 :
1013 E : EXPECT_TRUE(block->SetLabel(15, "baz", BlockGraph::CODE_LABEL));
1014 E : EXPECT_TRUE(block->HasLabel(15));
1015 E : EXPECT_TRUE(block->RemoveLabel(15));
1016 E : EXPECT_FALSE(block->HasLabel(15));
1017 :
1018 E : for (int i = 0; i < 0x20; ++i) {
1019 E : BlockGraph::Label label;
1020 E : if (i == 13 || i == 17) {
1021 E : ASSERT_TRUE(block->HasLabel(i));
1022 E : EXPECT_TRUE(block->GetLabel(i, &label));
1023 E : EXPECT_EQ(std::string(i == 13 ? "foo" : "bar"), label.name());
1024 : EXPECT_EQ(i == 13 ? BlockGraph::DATA_LABEL :
1025 : BlockGraph::CODE_LABEL,
1026 E : label.attributes());
1027 E : } else {
1028 E : ASSERT_FALSE(block->HasLabel(i));
1029 E : EXPECT_FALSE(block->GetLabel(i, &label));
1030 : }
1031 E : }
1032 :
1033 E : BlockGraph::Block::LabelMap expected;
1034 : expected.insert(std::make_pair(
1035 E : 13, BlockGraph::Label("foo", BlockGraph::DATA_LABEL)));
1036 : expected.insert(std::make_pair(
1037 E : 17, BlockGraph::Label("bar", BlockGraph::CODE_LABEL)));
1038 E : EXPECT_THAT(block->labels(), testing::ContainerEq(expected));
1039 E : }
1040 :
1041 E : TEST(BlockGraphTest, InternStrings) {
1042 E : std::string str1 = "Dummy";
1043 E : std::string str2 = "Foo";
1044 E : std::string str3 = "Bar";
1045 E : std::string str4 = "Foo";
1046 :
1047 : // Validate that string are interned correctly.
1048 E : BlockGraph block_graph;
1049 E : const std::string& interned_str1 = block_graph.InternString(str1);
1050 E : const std::string& interned_str2 = block_graph.InternString(str2);
1051 E : const std::string& interned_str3 = block_graph.InternString(str3);
1052 E : const std::string& interned_str4 = block_graph.InternString(str4);
1053 :
1054 E : EXPECT_NE(&interned_str1, &interned_str2);
1055 E : EXPECT_NE(&interned_str1, &interned_str3);
1056 E : EXPECT_NE(&interned_str1, &interned_str4);
1057 E : EXPECT_NE(&interned_str2, &interned_str3);
1058 E : EXPECT_EQ(&interned_str2, &interned_str4);
1059 E : EXPECT_NE(&interned_str3, &interned_str4);
1060 E : }
1061 :
1062 : namespace {
1063 :
1064 : class BlockGraphSerializationTest : public testing::Test {
1065 : public:
1066 : virtual void SetUp() {
1067 : ASSERT_TRUE(testing::GenerateTestBlockGraph(&image_));
1068 : }
1069 :
1070 : protected:
1071 : BlockGraph image_;
1072 : };
1073 :
1074 : } // namespace
1075 :
1076 E : TEST(BlockGraphAddressSpaceTest, AddBlock) {
1077 E : BlockGraph image;
1078 E : BlockGraph::AddressSpace address_space(&image);
1079 :
1080 : // We should be able to insert this block.
1081 : BlockGraph::Block* block = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1082 : RelativeAddress(0x1000),
1083 : 0x20,
1084 E : "code");
1085 E : ASSERT_TRUE(block != NULL);
1086 E : EXPECT_EQ(0x1000, block->addr().value());
1087 :
1088 : // But inserting anything that intersects with it should fail.
1089 : EXPECT_EQ(NULL, address_space.AddBlock(BlockGraph::CODE_BLOCK,
1090 : RelativeAddress(0x1000),
1091 : 0x20,
1092 E : "code"));
1093 :
1094 : // Overlapping from below.
1095 : EXPECT_EQ(NULL, address_space.AddBlock(BlockGraph::CODE_BLOCK,
1096 : RelativeAddress(0xFF0),
1097 : 0x20,
1098 E : "code"));
1099 : // Enclosing.
1100 : EXPECT_EQ(NULL, address_space.AddBlock(BlockGraph::CODE_BLOCK,
1101 : RelativeAddress(0xFF0),
1102 : 0x30,
1103 E : "code"));
1104 : // Itersecting to end.
1105 : EXPECT_EQ(NULL, address_space.AddBlock(BlockGraph::CODE_BLOCK,
1106 : RelativeAddress(0x1010),
1107 : 0x10,
1108 E : "code"));
1109 : // Intersecting, overlapping the back.
1110 : EXPECT_EQ(NULL, address_space.AddBlock(BlockGraph::CODE_BLOCK,
1111 : RelativeAddress(0x1010),
1112 : 0x20,
1113 E : "code"));
1114 :
1115 : // We should be able to insert blocks above and below the one above.
1116 : EXPECT_TRUE(address_space.AddBlock(BlockGraph::CODE_BLOCK,
1117 : RelativeAddress(0xFF0),
1118 : 0x10,
1119 E : "code") != NULL);
1120 : EXPECT_TRUE(address_space.AddBlock(BlockGraph::CODE_BLOCK,
1121 : RelativeAddress(0x1020),
1122 : 0x10,
1123 E : "code") != NULL);
1124 E : }
1125 :
1126 E : TEST(BlockGraphAddressSpaceTest, InsertBlock) {
1127 E : BlockGraph image;
1128 E : BlockGraph::AddressSpace address_space(&image);
1129 :
1130 : BlockGraph::Block* block1 =
1131 E : image.AddBlock(BlockGraph::CODE_BLOCK, 0x10, "code");
1132 : BlockGraph::Block* block2 =
1133 E : image.AddBlock(BlockGraph::CODE_BLOCK, 0x10, "code");
1134 : BlockGraph::Block* block3 =
1135 E : image.AddBlock(BlockGraph::CODE_BLOCK, 0x10, "code");
1136 :
1137 E : ASSERT_TRUE(address_space.InsertBlock(RelativeAddress(0x1000), block1));
1138 E : ASSERT_FALSE(address_space.InsertBlock(RelativeAddress(0x1000), block2));
1139 E : ASSERT_TRUE(address_space.InsertBlock(RelativeAddress(0x1010), block2));
1140 E : ASSERT_FALSE(address_space.InsertBlock(RelativeAddress(0x1018), block3));
1141 E : ASSERT_TRUE(address_space.InsertBlock(RelativeAddress(0x1030), block3));
1142 :
1143 E : RelativeAddress addr;
1144 E : EXPECT_TRUE(address_space.GetAddressOf(block1, &addr));
1145 E : EXPECT_EQ(0x1000, addr.value());
1146 E : EXPECT_EQ(0x1000, block1->addr().value());
1147 :
1148 E : EXPECT_TRUE(address_space.GetAddressOf(block2, &addr));
1149 E : EXPECT_EQ(0x1010, addr.value());
1150 E : EXPECT_EQ(0x1010, block2->addr().value());
1151 :
1152 E : EXPECT_TRUE(address_space.GetAddressOf(block3, &addr));
1153 E : EXPECT_EQ(0x1030, addr.value());
1154 E : EXPECT_EQ(0x1030, block3->addr().value());
1155 :
1156 : // Insert a block into a second address space.
1157 E : BlockGraph::AddressSpace address_space2(&image);
1158 E : EXPECT_TRUE(address_space2.InsertBlock(RelativeAddress(0x2000), block1));
1159 E : EXPECT_TRUE(address_space.GetAddressOf(block1, &addr));
1160 E : EXPECT_EQ(0x1000, addr.value());
1161 :
1162 E : EXPECT_TRUE(address_space2.GetAddressOf(block1, &addr));
1163 E : EXPECT_EQ(0x2000, addr.value());
1164 :
1165 E : EXPECT_EQ(0x2000, block1->addr().value());
1166 E : }
1167 :
1168 E : TEST(BlockGraphAddressSpaceTest, GetBlockByAddress) {
1169 E : BlockGraph image;
1170 E : BlockGraph::AddressSpace address_space(&image);
1171 :
1172 : BlockGraph::Block* block1 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1173 : RelativeAddress(0x1000),
1174 : 0x10,
1175 E : "code");
1176 : BlockGraph::Block* block2 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1177 : RelativeAddress(0x1010),
1178 : 0x10,
1179 E : "code");
1180 : BlockGraph::Block* block3 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1181 : RelativeAddress(0x1030),
1182 : 0x10,
1183 E : "code");
1184 :
1185 E : EXPECT_EQ(NULL, address_space.GetBlockByAddress(RelativeAddress(0xFFF)));
1186 :
1187 E : EXPECT_EQ(block1, address_space.GetBlockByAddress(RelativeAddress(0x1000)));
1188 E : EXPECT_EQ(block1, address_space.GetBlockByAddress(RelativeAddress(0x100F)));
1189 :
1190 E : EXPECT_EQ(block2, address_space.GetBlockByAddress(RelativeAddress(0x1010)));
1191 E : EXPECT_EQ(block2, address_space.GetBlockByAddress(RelativeAddress(0x101F)));
1192 :
1193 E : EXPECT_EQ(NULL, address_space.GetBlockByAddress(RelativeAddress(0x1020)));
1194 E : EXPECT_EQ(NULL, address_space.GetBlockByAddress(RelativeAddress(0x102F)));
1195 :
1196 E : EXPECT_EQ(block3, address_space.GetBlockByAddress(RelativeAddress(0x1030)));
1197 E : EXPECT_EQ(block3, address_space.GetBlockByAddress(RelativeAddress(0x103F)));
1198 :
1199 E : EXPECT_EQ(NULL, address_space.GetBlockByAddress(RelativeAddress(0x1040)));
1200 E : }
1201 :
1202 E : TEST(BlockGraphAddressSpaceTest, GetFirstIntersectingBlock) {
1203 E : BlockGraph image;
1204 E : BlockGraph::AddressSpace address_space(&image);
1205 :
1206 : BlockGraph::Block* block1 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1207 : RelativeAddress(0x1000),
1208 : 0x10,
1209 E : "code");
1210 : BlockGraph::Block* block2 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1211 : RelativeAddress(0x1010),
1212 : 0x10,
1213 E : "code");
1214 : BlockGraph::Block* block3 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1215 : RelativeAddress(0x1030),
1216 : 0x10,
1217 E : "code");
1218 :
1219 : EXPECT_EQ(NULL,
1220 E : address_space.GetFirstIntersectingBlock(RelativeAddress(0xFFF), 0x1));
1221 : EXPECT_EQ(block1,
1222 E : address_space.GetFirstIntersectingBlock(RelativeAddress(0xFFF), 0x2));
1223 : EXPECT_EQ(block1,
1224 E : address_space.GetFirstIntersectingBlock(RelativeAddress(0x100F), 0x1));
1225 : EXPECT_EQ(block1,
1226 E : address_space.GetFirstIntersectingBlock(RelativeAddress(0x100F), 0x2));
1227 :
1228 : EXPECT_EQ(block2,
1229 E : address_space.GetFirstIntersectingBlock(RelativeAddress(0x1010), 0x40));
1230 E : }
1231 :
1232 E : TEST(BlockGraphAddressSpaceTest, GetContainingBlock) {
1233 E : BlockGraph image;
1234 E : BlockGraph::AddressSpace address_space(&image);
1235 E : BlockGraph::Block* found_block = NULL;
1236 :
1237 : BlockGraph::Block* block1 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1238 : RelativeAddress(0x1000),
1239 : 0x10,
1240 E : "code");
1241 : BlockGraph::Block* block2 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1242 : RelativeAddress(0x1010),
1243 : 0x10,
1244 E : "code");
1245 :
1246 : // Fully contained in block1
1247 : EXPECT_EQ(block1,
1248 E : address_space.GetContainingBlock(RelativeAddress(0x1004), 8));
1249 :
1250 : // Fully contained in block2
1251 : EXPECT_EQ(block2,
1252 E : address_space.GetContainingBlock(RelativeAddress(0x1014), 8));
1253 :
1254 : // Starts before but intersects with block1.
1255 E : EXPECT_EQ(NULL, address_space.GetContainingBlock(RelativeAddress(0x099E), 8));
1256 :
1257 : // Starts in the middle of block1 and overlaps into block2.
1258 E : EXPECT_EQ(NULL, address_space.GetContainingBlock(RelativeAddress(0x100a), 8));
1259 E : }
1260 :
1261 E : TEST(BlockGraphAddressSpaceTest, GetBlockAddress) {
1262 E : BlockGraph image;
1263 E : BlockGraph::AddressSpace address_space(&image);
1264 :
1265 : BlockGraph::Block* block1 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1266 : RelativeAddress(0x1000),
1267 : 0x10,
1268 E : "code");
1269 : BlockGraph::Block* block2 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1270 : RelativeAddress(0x1010),
1271 : 0x10,
1272 E : "code");
1273 : BlockGraph::Block* block3 =
1274 E : image.AddBlock(BlockGraph::CODE_BLOCK, 0x10, "code");
1275 :
1276 E : RelativeAddress addr;
1277 E : EXPECT_TRUE(address_space.GetAddressOf(block1, &addr));
1278 E : EXPECT_EQ(0x1000, addr.value());
1279 :
1280 E : EXPECT_TRUE(address_space.GetAddressOf(block2, &addr));
1281 E : EXPECT_EQ(0x1010, addr.value());
1282 :
1283 E : EXPECT_FALSE(address_space.GetAddressOf(block3, &addr));
1284 E : }
1285 :
1286 E : TEST(BlockGraphAddressSpaceTest, MergeIntersectingBlocks) {
1287 E : BlockGraph image;
1288 E : BlockGraph::AddressSpace address_space(&image);
1289 E : RelativeAddress addr1(0x1000);
1290 E : RelativeAddress addr2(0x1010);
1291 E : RelativeAddress addr3(0x1030);
1292 : BlockGraph::Block* block1 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1293 : addr1,
1294 : 0x10,
1295 E : "block1");
1296 : BlockGraph::Block* block2 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1297 : addr2,
1298 : 0x10,
1299 E : "block2");
1300 : BlockGraph::Block* block3 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1301 : addr3,
1302 : 0x10,
1303 E : "block3");
1304 E : ASSERT_TRUE(block2->SetLabel(0, "0x1010", BlockGraph::CODE_LABEL));
1305 E : ASSERT_TRUE(block2->SetLabel(4, "0x1014", BlockGraph::CODE_LABEL));
1306 E : ASSERT_TRUE(block3->SetLabel(0, "0x1030", BlockGraph::CODE_LABEL));
1307 E : ASSERT_TRUE(block3->SetLabel(4, "0x1034", BlockGraph::CODE_LABEL));
1308 :
1309 : block1->source_ranges().Push(BlockGraph::Block::DataRange(0, 0x10),
1310 E : BlockGraph::Block::SourceRange(addr1, 0x10));
1311 : block2->source_ranges().Push(BlockGraph::Block::DataRange(0, 0x10),
1312 E : BlockGraph::Block::SourceRange(addr2, 0x10));
1313 : block3->source_ranges().Push(BlockGraph::Block::DataRange(0, 0x10),
1314 E : BlockGraph::Block::SourceRange(addr3, 0x10));
1315 :
1316 : ASSERT_TRUE(block1->SetReference(0x1,
1317 E : BlockGraph::Reference(BlockGraph::ABSOLUTE_REF, 4, block2, 0x0, 0x0)));
1318 : ASSERT_TRUE(block1->SetReference(0x6,
1319 E : BlockGraph::Reference(BlockGraph::ABSOLUTE_REF, 4, block3, 0x0, 0x0)));
1320 : ASSERT_TRUE(block2->SetReference(0x1,
1321 E : BlockGraph::Reference(BlockGraph::PC_RELATIVE_REF, 1, block1, 0x4, 0x4)));
1322 : ASSERT_TRUE(block2->SetReference(0x6,
1323 E : BlockGraph::Reference(BlockGraph::PC_RELATIVE_REF, 4, block3, 0x4, 0x4)));
1324 : ASSERT_TRUE(block3->SetReference(0x1,
1325 E : BlockGraph::Reference(BlockGraph::PC_RELATIVE_REF, 4, block2, 0x4, 0x4)));
1326 :
1327 : BlockGraph::Block* merged = address_space.MergeIntersectingBlocks(
1328 E : BlockGraph::AddressSpace::Range(RelativeAddress(0x1014), 0x30));
1329 :
1330 E : ASSERT_TRUE(merged != NULL);
1331 E : ASSERT_EQ(RelativeAddress(0x1010), merged->addr());
1332 E : ASSERT_EQ(0x34, merged->size());
1333 :
1334 : // Expect the merged block to have meaningful source ranges.
1335 E : BlockGraph::Block::SourceRanges::RangePairs expected_source_ranges;
1336 : expected_source_ranges.push_back(
1337 : std::make_pair(BlockGraph::Block::DataRange(0, 0x10),
1338 E : BlockGraph::Block::SourceRange(addr2, 0x10)));
1339 : expected_source_ranges.push_back(
1340 : std::make_pair(BlockGraph::Block::DataRange(0x20, 0x10),
1341 E : BlockGraph::Block::SourceRange(addr3, 0x10)));
1342 : EXPECT_THAT(merged->source_ranges().range_pairs(),
1343 E : testing::ContainerEq(expected_source_ranges));
1344 :
1345 E : BlockGraph::Block::LabelMap expected_labels;
1346 : expected_labels.insert(std::make_pair(
1347 E : 0x00, BlockGraph::Label("0x1010", BlockGraph::CODE_LABEL)));
1348 : expected_labels.insert(std::make_pair(
1349 E : 0x04, BlockGraph::Label("0x1014", BlockGraph::CODE_LABEL)));
1350 : expected_labels.insert(std::make_pair(
1351 E : 0x20, BlockGraph::Label("0x1030", BlockGraph::CODE_LABEL)));
1352 : expected_labels.insert(std::make_pair(
1353 E : 0x24, BlockGraph::Label("0x1034", BlockGraph::CODE_LABEL)));
1354 E : EXPECT_THAT(merged->labels(), testing::ContainerEq(expected_labels));
1355 :
1356 E : BlockGraph::Block::ReferenceMap expected_refs;
1357 : expected_refs.insert(std::make_pair(0x1,
1358 E : BlockGraph::Reference(BlockGraph::PC_RELATIVE_REF, 1, block1, 0x4, 0x4)));
1359 : expected_refs.insert(std::make_pair(0x6,
1360 : BlockGraph::Reference(BlockGraph::PC_RELATIVE_REF, 4, merged, 0x24,
1361 E : 0x24)));
1362 : expected_refs.insert(std::make_pair(0x21,
1363 E : BlockGraph::Reference(BlockGraph::PC_RELATIVE_REF, 4, merged, 0x4, 0x4)));
1364 E : EXPECT_THAT(merged->references(), testing::ContainerEq(expected_refs));
1365 :
1366 E : expected_refs.clear();
1367 : expected_refs.insert(std::make_pair(0x1,
1368 E : BlockGraph::Reference(BlockGraph::ABSOLUTE_REF, 4, merged, 0x0, 0x0)));
1369 : expected_refs.insert(std::make_pair(0x6,
1370 E : BlockGraph::Reference(BlockGraph::ABSOLUTE_REF, 4, merged, 0x20, 0x20)));
1371 E : EXPECT_THAT(block1->references(), testing::ContainerEq(expected_refs));
1372 :
1373 : // We expect that the block graph and the address space have the same size,
1374 : // as MergeIntersectingBlocks deletes the old blocks from the BlockGraph.
1375 E : EXPECT_EQ(image.blocks().size(), address_space.address_space_impl().size());
1376 E : }
1377 :
1378 E : TEST(BlockGraphAddressSpaceTest, ContainsBlock) {
1379 E : BlockGraph image;
1380 E : BlockGraph::AddressSpace address_space(&image);
1381 : BlockGraph::Block* block =
1382 E : image.AddBlock(BlockGraph::CODE_BLOCK, 0x10, "code");
1383 :
1384 E : ASSERT_FALSE(address_space.ContainsBlock(block));
1385 E : EXPECT_TRUE(address_space.InsertBlock(RelativeAddress(0x1000), block));
1386 E : ASSERT_TRUE(address_space.ContainsBlock(block));
1387 E : }
1388 :
1389 : } // namespace block_graph
|