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(1U, block_->alignment());
200 E : ASSERT_EQ(0, block_->alignment_offset());
201 E : ASSERT_EQ(0U, block_->padding_before());
202 E : ASSERT_STREQ(kBlockName, block_->name().c_str());
203 E : ASSERT_EQ(RelativeAddress::kInvalidAddress, block_->addr());
204 E : ASSERT_EQ(BlockGraph::kInvalidSectionId, block_->section());
205 E : ASSERT_EQ(0U, block_->attributes());
206 E : ASSERT_EQ(NULL, block_->data());
207 E : ASSERT_EQ(0U, block_->data_size());
208 E : ASSERT_FALSE(block_->owns_data());
209 E : }
210 :
211 E : TEST_F(BlockTest, Accessors) {
212 E : ASSERT_NE(BlockGraph::DATA_BLOCK, block_->type());
213 E : block_->set_type(BlockGraph::DATA_BLOCK);
214 E : ASSERT_EQ(BlockGraph::DATA_BLOCK, block_->type());
215 :
216 E : ASSERT_NE(0x10U, block_->size());
217 E : block_->set_size(0x10);
218 E : ASSERT_EQ(0x10U, block_->size());
219 :
220 E : ASSERT_STRNE("foo", block_->name().c_str());
221 E : block_->set_name("foo");
222 E : ASSERT_STREQ("foo", block_->name().c_str());
223 :
224 E : ASSERT_STRNE("foo.o", block_->compiland_name().c_str());
225 E : block_->set_compiland_name("foo.o");
226 E : ASSERT_STREQ("foo.o", block_->compiland_name().c_str());
227 :
228 E : ASSERT_NE(16U, block_->alignment());
229 E : block_->set_alignment(16);
230 E : ASSERT_EQ(16U, block_->alignment());
231 :
232 E : ASSERT_NE(2, block_->alignment_offset());
233 E : block_->set_alignment_offset(2);
234 E : ASSERT_EQ(2, block_->alignment_offset());
235 :
236 E : ASSERT_NE(15U, block_->padding_before());
237 E : block_->set_padding_before(15U);
238 E : ASSERT_EQ(15U, block_->padding_before());
239 :
240 : // Test accessors.
241 E : block_->set_attribute(0x20);
242 E : ASSERT_EQ(0x20, block_->attributes());
243 E : block_->set_attribute(0x10);
244 E : ASSERT_EQ(0x30, block_->attributes());
245 E : block_->clear_attribute(0x20);
246 E : ASSERT_EQ(0x10, block_->attributes());
247 :
248 E : block_->set_size(sizeof(kTestData));
249 E : block_->SetData(kTestData, sizeof(kTestData));
250 E : ASSERT_EQ(kTestData, block_->data());
251 E : ASSERT_EQ(sizeof(kTestData), block_->data_size());
252 E : ASSERT_FALSE(block_->owns_data());
253 E : }
254 :
255 E : TEST_F(BlockTest, AllocateData) {
256 : // Test AllocateData.
257 E : uint8* data = block_->AllocateData(block_->size());
258 E : ASSERT_TRUE(block_->owns_data());
259 E : ASSERT_EQ(block_->size(), block_->data_size());
260 E : ASSERT_EQ(data, block_->data());
261 :
262 : static const uint8 zeros[kBlockSize] = {};
263 E : ASSERT_EQ(0, memcmp(&zeros[0], data, block_->size()));
264 E : }
265 :
266 E : TEST_F(BlockTest, CopyData) {
267 : // Test CopyData.
268 E : uint8* data = block_->CopyData(sizeof(kTestData), kTestData);
269 E : ASSERT_TRUE(block_->owns_data());
270 E : ASSERT_EQ(sizeof(kTestData), block_->data_size());
271 E : ASSERT_EQ(data, block_->data());
272 E : ASSERT_EQ(0, memcmp(kTestData, data, block_->data_size()));
273 E : }
274 :
275 E : TEST_F(BlockTest, ResizeData) {
276 : // Set the block's data.
277 E : block_->SetData(kTestData, sizeof(kTestData));
278 :
279 : // Shrinking the data should not take ownership.
280 E : const uint8* data = block_->ResizeData(sizeof(kTestData) / 2);
281 E : ASSERT_TRUE(data != NULL);
282 E : ASSERT_TRUE(data == kTestData);
283 E : ASSERT_FALSE(block_->owns_data());
284 :
285 : // Growing the data must always take ownership.
286 E : data = block_->ResizeData(sizeof(kTestData));
287 E : ASSERT_TRUE(data != NULL);
288 E : ASSERT_TRUE(data != kTestData);
289 E : ASSERT_TRUE(block_->owns_data());
290 : // The head of the data should be identical to the input.
291 E : ASSERT_EQ(0, memcmp(data, kTestData, sizeof(kTestData) / 2));
292 : // And the tail should be zeros.
293 : static const uint8 kZeros[sizeof(kTestData) - sizeof(kTestData) / 2] = {};
294 E : ASSERT_EQ(0, memcmp(data + sizeof(kTestData) / 2, kZeros, sizeof(kZeros)));
295 :
296 : // Now grow it from non-owned.
297 E : block_->SetData(kTestData, sizeof(kTestData));
298 E : data = block_->ResizeData(sizeof(kTestData) + sizeof(kZeros));
299 E : ASSERT_TRUE(data != NULL);
300 E : ASSERT_TRUE(data != kTestData);
301 E : ASSERT_TRUE(block_->owns_data());
302 :
303 : // The head of the data should be identical to the input.
304 E : ASSERT_EQ(0, memcmp(data, kTestData, sizeof(kTestData)));
305 : // And the tail should be zeros.
306 E : ASSERT_EQ(0, memcmp(data + sizeof(kTestData), kZeros, sizeof(kZeros)));
307 E : }
308 :
309 E : TEST_F(BlockTest, GetMutableData) {
310 : // Set the block's data.
311 E : block_->SetData(kTestData, sizeof(kTestData));
312 :
313 : // Getting a mutable pointer should copy the data to heap.
314 E : uint8* data = block_->GetMutableData();
315 E : ASSERT_TRUE(data != NULL);
316 E : ASSERT_TRUE(data != kTestData);
317 E : ASSERT_TRUE(block_->owns_data());
318 E : ASSERT_EQ(sizeof(kTestData), block_->data_size());
319 E : ASSERT_EQ(data, block_->data());
320 E : ASSERT_EQ(0, memcmp(kTestData, data, block_->data_size()));
321 :
322 : // Getting the data a second time should return the same pointer.
323 E : ASSERT_EQ(data, block_->GetMutableData());
324 E : }
325 :
326 E : TEST_F(BlockTest, InsertData) {
327 : // Create a block with a labelled array of pointers. Explicitly initialize
328 : // the last one with some data and let the block be longer than its
329 : // explicitly initialized length.
330 : BlockGraph::Block* block1 = image_.AddBlock(
331 E : BlockGraph::CODE_BLOCK, 4 * kPtrSize, "Block1");
332 E : block1->AllocateData(3 * kPtrSize);
333 : block1->source_ranges().Push(BlockGraph::Block::DataRange(0, 4 * kPtrSize),
334 : BlockGraph::Block::SourceRange(
335 E : core::RelativeAddress(0), 4 * kPtrSize));
336 : BlockGraph::Reference outgoing_ref(BlockGraph::RELATIVE_REF,
337 : kPtrSize,
338 : block_,
339 E : 0, 0);
340 E : block1->SetReference(0, outgoing_ref);
341 E : block1->SetReference(kPtrSize, outgoing_ref);
342 E : block1->SetLabel(0, "Pointer1", BlockGraph::DATA_LABEL);
343 E : block1->SetLabel(kPtrSize, "Pointer2", BlockGraph::DATA_LABEL);
344 E : block1->SetLabel(2 * kPtrSize, "Pointer3", BlockGraph::DATA_LABEL);
345 E : TypedBlock<uint32> data1;
346 E : ASSERT_TRUE(data1.Init(0, block1));
347 E : data1[0] = 0xAAAAAAAA;
348 E : data1[1] = 0xBBBBBBBB;
349 E : data1[2] = 0xCCCCCCCC;
350 :
351 : // Create a block with a pointer to the first entry of block1.
352 : BlockGraph::Block* block2 = image_.AddBlock(
353 E : BlockGraph::CODE_BLOCK, kPtrSize, "Block2");
354 : block2->SetReference(0, BlockGraph::Reference(BlockGraph::RELATIVE_REF,
355 : kPtrSize,
356 : block1,
357 E : 0, 0));
358 :
359 : // Create a block with a pointer to the second entry of block1.
360 : BlockGraph::Block* block3 = image_.AddBlock(
361 E : BlockGraph::CODE_BLOCK, kPtrSize, "Block3");
362 : block3->SetReference(0, BlockGraph::Reference(BlockGraph::RELATIVE_REF,
363 : kPtrSize,
364 : block1,
365 E : kPtrSize, kPtrSize));
366 :
367 : // Insert a new pointer entry in between the first and second entries.
368 E : block1->InsertData(kPtrSize, kPtrSize, false);
369 :
370 : // Ensure the data_size and block size are as expected.
371 E : EXPECT_EQ(5 * kPtrSize, block1->size());
372 E : EXPECT_EQ(4 * kPtrSize, block1->data_size());
373 :
374 : // Ensure the source ranges are as expected.
375 E : BlockGraph::Block::SourceRanges expected_src_ranges;
376 : expected_src_ranges.Push(
377 : BlockGraph::Block::DataRange(0, kPtrSize),
378 E : BlockGraph::Block::SourceRange(core::RelativeAddress(0), kPtrSize));
379 : expected_src_ranges.Push(
380 : BlockGraph::Block::DataRange(2 * kPtrSize, 3 * kPtrSize),
381 : BlockGraph::Block::SourceRange(core::RelativeAddress(kPtrSize),
382 E : 3 * kPtrSize));
383 : EXPECT_THAT(expected_src_ranges.range_pairs(),
384 E : testing::ContainerEq(block1->source_ranges().range_pairs()));
385 :
386 : // Ensure that the contents of the block's data are as expected.
387 E : EXPECT_EQ(0xAAAAAAAAu, data1[0]);
388 E : EXPECT_EQ(0x00000000u, data1[1]);
389 E : EXPECT_EQ(0xBBBBBBBBu, data1[2]);
390 E : EXPECT_EQ(0xCCCCCCCCu, data1[3]);
391 :
392 : // Ensure that the labels have been shifted appropriately.
393 E : BlockGraph::Block::LabelMap expected_labels;
394 : expected_labels.insert(std::make_pair(
395 : 0 * kPtrSize,
396 E : BlockGraph::Label("Pointer1", BlockGraph::DATA_LABEL)));
397 : expected_labels.insert(std::make_pair(
398 : 2 * kPtrSize,
399 E : BlockGraph::Label("Pointer2", BlockGraph::DATA_LABEL)));
400 : expected_labels.insert(std::make_pair(
401 : 3 * kPtrSize,
402 E : BlockGraph::Label("Pointer3", BlockGraph::DATA_LABEL)));
403 E : EXPECT_THAT(expected_labels, testing::ContainerEq(block1->labels()));
404 :
405 : // Ensure that the referrers are as expected.
406 E : BlockGraph::Block::ReferrerSet expected_referrers;
407 E : expected_referrers.insert(std::make_pair(block2, 0));
408 E : expected_referrers.insert(std::make_pair(block3, 0));
409 E : EXPECT_THAT(expected_referrers, testing::ContainerEq(block1->referrers()));
410 :
411 : BlockGraph::Reference expected_ref(BlockGraph::RELATIVE_REF,
412 : kPtrSize,
413 : block1,
414 E : 0, 0);
415 E : BlockGraph::Reference actual_ref;
416 E : EXPECT_TRUE(block2->GetReference(0, &actual_ref));
417 E : EXPECT_EQ(expected_ref, actual_ref);
418 :
419 : expected_ref = BlockGraph::Reference(BlockGraph::RELATIVE_REF,
420 : kPtrSize,
421 : block1,
422 E : 2 * kPtrSize, 2 * kPtrSize);
423 E : EXPECT_TRUE(block3->GetReference(0, &actual_ref));
424 E : EXPECT_EQ(expected_ref, actual_ref);
425 :
426 : // Ensure that the references have been shifted appropriately.
427 E : BlockGraph::Block::ReferenceMap expected_references;
428 E : expected_references.insert(std::make_pair(0, outgoing_ref));
429 E : expected_references.insert(std::make_pair(2 * kPtrSize, outgoing_ref));
430 E : EXPECT_EQ(expected_references, block1->references());
431 E : }
432 :
433 E : TEST_F(BlockTest, InsertDataAtEndOfBlock) {
434 : // Create a block.
435 : BlockGraph::Block* block1 = image_.AddBlock(
436 E : BlockGraph::CODE_BLOCK, 4 * kPtrSize, "Block1");
437 E : block1->AllocateData(3 * kPtrSize);
438 E : EXPECT_EQ(4 * kPtrSize, block1->size());
439 :
440 : // Create a block with a pointer to the end of block1.
441 : BlockGraph::Block* block2 = image_.AddBlock(
442 E : BlockGraph::CODE_BLOCK, kPtrSize, "Block2");
443 : block2->SetReference(0, BlockGraph::Reference(BlockGraph::RELATIVE_REF,
444 : kPtrSize,
445 : block1,
446 : block1->size(),
447 E : block1->size()));
448 :
449 : // Shift block1 in the middle.
450 E : block1->InsertData(kPtrSize, kPtrSize, false);
451 :
452 : // Ensure the data_size and block size are as expected.
453 E : EXPECT_EQ(5 * kPtrSize, block1->size());
454 E : EXPECT_EQ(4 * kPtrSize, block1->data_size());
455 :
456 : // Ensure that the end reference has moved along.
457 : BlockGraph::Reference expected_ref(BlockGraph::RELATIVE_REF,
458 : kPtrSize,
459 : block1,
460 : block1->size(),
461 E : block1->size());
462 :
463 E : BlockGraph::Reference actual_ref;
464 E : EXPECT_TRUE(block2->GetReference(0, &actual_ref));
465 E : EXPECT_EQ(expected_ref, actual_ref);
466 :
467 : // Shift block1 at the end.
468 E : block1->InsertData(block1->size(), kPtrSize, false);
469 :
470 : // Ensure the data_size and block size are as expected.
471 E : EXPECT_EQ(6 * kPtrSize, block1->size());
472 E : EXPECT_EQ(4 * kPtrSize, block1->data_size());
473 :
474 : // Ensure that the end reference has moved along.
475 : expected_ref = BlockGraph::Reference(BlockGraph::RELATIVE_REF,
476 : kPtrSize,
477 : block1,
478 : block1->size(),
479 E : block1->size());
480 :
481 E : EXPECT_TRUE(block2->GetReference(0, &actual_ref));
482 E : EXPECT_EQ(expected_ref, actual_ref);
483 E : }
484 :
485 E : TEST_F(BlockTest, InsertDataImplicit) {
486 : BlockGraph::Block* block1 = image_.AddBlock(
487 E : BlockGraph::CODE_BLOCK, 40, "Block1");
488 E : block1->AllocateData(30);
489 :
490 : // Do an insert data in the implicitly initialized portion of the block.
491 E : block1->InsertData(30, 10, false);
492 :
493 : // We expect the block to have grown, but the data size should still be the
494 : // same.
495 E : EXPECT_EQ(50u, block1->size());
496 E : EXPECT_EQ(30u, block1->data_size());
497 E : }
498 :
499 E : TEST_F(BlockTest, InsertDataImplicitForceAllocation) {
500 : BlockGraph::Block* block1 = image_.AddBlock(
501 E : BlockGraph::CODE_BLOCK, 40, "Block1");
502 E : block1->AllocateData(30);
503 :
504 : // Do an insert data in the implicitly initialized portion of the block, but
505 : // force data to be allocated.
506 E : block1->InsertData(30, 10, true);
507 :
508 : // We expect the block to have grown, as well as the data size.
509 E : EXPECT_EQ(50u, block1->size());
510 E : EXPECT_EQ(40u, block1->data_size());
511 E : }
512 :
513 E : TEST_F(BlockTest, InsertDataForceAllocateDoesNotShorten) {
514 : BlockGraph::Block* block1 = image_.AddBlock(
515 E : BlockGraph::CODE_BLOCK, 40, "Block1");
516 E : block1->AllocateData(30);
517 :
518 : // Insert data in the allocated region, but request allocation to be forced.
519 E : block1->InsertData(0, 10, true);
520 :
521 E : EXPECT_EQ(50u, block1->size());
522 E : EXPECT_EQ(40u, block1->data_size());
523 E : }
524 :
525 E : TEST_F(BlockTest, InsertDataWithSelfReference) {
526 : BlockGraph::Block* block1 = image_.AddBlock(
527 E : BlockGraph::CODE_BLOCK, 40, "Block1");
528 :
529 E : BlockGraph::Reference ref(BlockGraph::ABSOLUTE_REF, kPtrSize, block1, 0, 0);
530 : // Insert a self-reference to the block.
531 E : block1->SetReference(20, ref);
532 :
533 : // Insert some data before the reference.
534 E : block1->InsertData(10, 10, false);
535 :
536 E : BlockGraph::Reference moved_ref;
537 E : ASSERT_TRUE(block1->GetReference(30, &moved_ref));
538 E : ASSERT_EQ(ref, moved_ref);
539 :
540 E : BlockGraph::Block::ReferrerSet expected;
541 E : expected.insert(std::make_pair(block1, 30));
542 E : ASSERT_EQ(block1->referrers(), expected);
543 E : }
544 :
545 E : TEST_F(BlockTest, RemoveData) {
546 : // Create a block with a labelled array of pointers. Explicitly initialize
547 : // the last one with some data and let the block be longer than its
548 : // explicitly initialized length.
549 : BlockGraph::Block* block1 = image_.AddBlock(
550 E : BlockGraph::CODE_BLOCK, 6 * kPtrSize, "Block1");
551 E : block1->AllocateData(3 * kPtrSize);
552 : block1->source_ranges().Push(BlockGraph::Block::DataRange(0, 6 * kPtrSize),
553 : BlockGraph::Block::SourceRange(
554 E : core::RelativeAddress(0), 6 * kPtrSize));
555 : BlockGraph::Reference outgoing_ref(BlockGraph::RELATIVE_REF,
556 : kPtrSize,
557 : block_,
558 E : 0, 0);
559 E : block1->SetReference(0, outgoing_ref);
560 E : block1->SetReference(2 * kPtrSize, outgoing_ref);
561 E : block1->SetReference(5 * kPtrSize, outgoing_ref);
562 E : block1->SetLabel(0, "Pointer1", BlockGraph::DATA_LABEL);
563 E : block1->SetLabel(2 * kPtrSize, "Pointer3", BlockGraph::DATA_LABEL);
564 E : block1->SetLabel(3 * kPtrSize, "EndOfPointers", BlockGraph::DATA_LABEL);
565 E : TypedBlock<uint32> data1;
566 E : ASSERT_TRUE(data1.Init(0, block1));
567 E : data1[0] = 0xAAAAAAAA;
568 E : data1[1] = 0xBBBBBBBB;
569 E : data1[2] = 0xCCCCCCCC;
570 :
571 : // Create a block with a pointer to the first entry of block1.
572 : BlockGraph::Block* block2 = image_.AddBlock(
573 E : BlockGraph::CODE_BLOCK, kPtrSize, "Block2");
574 : block2->SetReference(0, BlockGraph::Reference(BlockGraph::RELATIVE_REF,
575 : kPtrSize,
576 : block1,
577 E : 0, 0));
578 :
579 : // Create a block with a pointer to the third entry of block1.
580 : BlockGraph::Block* block3 = image_.AddBlock(
581 E : BlockGraph::CODE_BLOCK, kPtrSize, "Block4");
582 : block3->SetReference(0, BlockGraph::Reference(BlockGraph::RELATIVE_REF,
583 : kPtrSize,
584 : block1,
585 E : 2 * kPtrSize, 2 * kPtrSize));
586 :
587 : // Create a block with a pointer to the fifth entry of block1.
588 : BlockGraph::Block* block4 = image_.AddBlock(
589 E : BlockGraph::CODE_BLOCK, kPtrSize, "Block3");
590 : block4->SetReference(0, BlockGraph::Reference(BlockGraph::RELATIVE_REF,
591 : kPtrSize,
592 : block1,
593 E : 4 * kPtrSize, 4 * kPtrSize));
594 :
595 : // Trying to remove the fourth entry should fail because it contains a label.
596 E : EXPECT_FALSE(block1->RemoveData(3 * kPtrSize, kPtrSize));
597 :
598 : // Trying to remove the fifth entry should fail because there is a referrer
599 : // pointing to it.
600 E : EXPECT_FALSE(block1->RemoveData(4 * kPtrSize, kPtrSize));
601 :
602 : // Trying to remove the sixth entry should fail because it contains a
603 : // reference.
604 E : EXPECT_FALSE(block1->RemoveData(5 * kPtrSize, kPtrSize));
605 :
606 : // Finally, we should be able to delete the second entry.
607 E : EXPECT_TRUE(block1->RemoveData(kPtrSize, kPtrSize));
608 :
609 : // Ensure the data_size and block size are as expected.
610 E : EXPECT_EQ(5 * kPtrSize, block1->size());
611 E : EXPECT_EQ(2 * kPtrSize, block1->data_size());
612 :
613 : // Ensure the source ranges are as expected.
614 E : BlockGraph::Block::SourceRanges expected_src_ranges;
615 : expected_src_ranges.Push(
616 : BlockGraph::Block::DataRange(0, kPtrSize),
617 E : BlockGraph::Block::SourceRange(core::RelativeAddress(0), kPtrSize));
618 : expected_src_ranges.Push(
619 : BlockGraph::Block::DataRange(kPtrSize, 4 * kPtrSize),
620 : BlockGraph::Block::SourceRange(core::RelativeAddress(2 * kPtrSize),
621 E : 4 * kPtrSize));
622 : EXPECT_THAT(expected_src_ranges.range_pairs(),
623 E : testing::ContainerEq(block1->source_ranges().range_pairs()));
624 :
625 : // Ensure that the contents of the block's data are as expected.
626 E : EXPECT_EQ(0xAAAAAAAAu, data1[0]);
627 E : EXPECT_EQ(0xCCCCCCCCu, data1[1]);
628 :
629 : // Ensure that the labels have been shifted appropriately.
630 E : BlockGraph::Block::LabelMap expected_labels;
631 : expected_labels.insert(std::make_pair(
632 : 0 * kPtrSize,
633 E : BlockGraph::Label("Pointer1", BlockGraph::DATA_LABEL)));
634 : expected_labels.insert(std::make_pair(
635 : 1 * kPtrSize,
636 E : BlockGraph::Label("Pointer3", BlockGraph::DATA_LABEL)));
637 : expected_labels.insert(std::make_pair(
638 : 2 * kPtrSize,
639 E : BlockGraph::Label("EndOfPointers", BlockGraph::DATA_LABEL)));
640 E : EXPECT_THAT(expected_labels, testing::ContainerEq(block1->labels()));
641 :
642 : // Ensure that the referrers are as expected.
643 E : BlockGraph::Block::ReferrerSet expected_referrers;
644 E : expected_referrers.insert(std::make_pair(block2, 0));
645 E : expected_referrers.insert(std::make_pair(block3, 0));
646 E : expected_referrers.insert(std::make_pair(block4, 0));
647 E : EXPECT_THAT(expected_referrers, testing::ContainerEq(block1->referrers()));
648 :
649 : BlockGraph::Reference expected_ref(BlockGraph::RELATIVE_REF,
650 : kPtrSize,
651 : block1,
652 E : 0, 0);
653 E : BlockGraph::Reference actual_ref;
654 E : EXPECT_TRUE(block2->GetReference(0, &actual_ref));
655 E : EXPECT_EQ(expected_ref, actual_ref);
656 :
657 : expected_ref = BlockGraph::Reference(BlockGraph::RELATIVE_REF,
658 : kPtrSize,
659 : block1,
660 E : kPtrSize, kPtrSize);
661 E : EXPECT_TRUE(block3->GetReference(0, &actual_ref));
662 E : EXPECT_EQ(expected_ref, actual_ref);
663 :
664 : expected_ref = BlockGraph::Reference(BlockGraph::RELATIVE_REF,
665 : kPtrSize,
666 : block1,
667 E : 3 * kPtrSize, 3 * kPtrSize);
668 E : EXPECT_TRUE(block4->GetReference(0, &actual_ref));
669 E : EXPECT_EQ(expected_ref, actual_ref);
670 :
671 : // Ensure that the references have been shifted appropriately.
672 E : BlockGraph::Block::ReferenceMap expected_references;
673 E : expected_references.insert(std::make_pair(0, outgoing_ref));
674 E : expected_references.insert(std::make_pair(kPtrSize, outgoing_ref));
675 E : expected_references.insert(std::make_pair(4 * kPtrSize, outgoing_ref));
676 E : EXPECT_EQ(expected_references, block1->references());
677 E : }
678 :
679 E : TEST_F(BlockTest, RemoveDataPartlyImplicit) {
680 : BlockGraph::Block* block1 = image_.AddBlock(
681 E : BlockGraph::CODE_BLOCK, 40, "Block1");
682 E : block1->AllocateData(30);
683 :
684 : // Remove data that spans both the initialized and implicit parts of the
685 : // block.
686 E : EXPECT_TRUE(block1->RemoveData(25, 10));
687 :
688 : // We expect both the block and the data size to have shrunk.
689 E : EXPECT_EQ(30u, block1->size());
690 E : EXPECT_EQ(25u, block1->data_size());
691 E : }
692 :
693 E : TEST_F(BlockTest, RemoveDataImplicit) {
694 : BlockGraph::Block* block1 = image_.AddBlock(
695 E : BlockGraph::CODE_BLOCK, 40, "Block1");
696 E : block1->AllocateData(30);
697 :
698 : // Do an remove data in the implicitly initialized portion of the block.
699 E : EXPECT_TRUE(block1->RemoveData(30, 5));
700 :
701 : // We expect the block to have shrunk, but the data size should still be the
702 : // same.
703 E : EXPECT_EQ(35u, block1->size());
704 E : EXPECT_EQ(30u, block1->data_size());
705 E : }
706 :
707 E : TEST_F(BlockTest, RemoveDataWithSelfReference) {
708 : BlockGraph::Block* block1 = image_.AddBlock(
709 E : BlockGraph::CODE_BLOCK, 50, "Block1");
710 :
711 E : BlockGraph::Reference ref(BlockGraph::ABSOLUTE_REF, kPtrSize, block1, 0, 0);
712 : // Insert a self-reference to the block.
713 E : block1->SetReference(40, ref);
714 :
715 : // Remove some data before the reference.
716 E : block1->RemoveData(10, 10);
717 :
718 E : BlockGraph::Reference moved_ref;
719 E : ASSERT_TRUE(block1->GetReference(30, &moved_ref));
720 E : ASSERT_EQ(ref, moved_ref);
721 :
722 E : BlockGraph::Block::ReferrerSet expected;
723 E : expected.insert(std::make_pair(block1, 30));
724 E : ASSERT_EQ(block1->referrers(), expected);
725 E : }
726 :
727 E : TEST_F(BlockTest, InsertOrRemoveDataSameSizeNoAllocate) {
728 : BlockGraph::Block* block1 = image_.AddBlock(
729 E : BlockGraph::DATA_BLOCK, 40, "Block1");
730 :
731 E : EXPECT_TRUE(block1->InsertOrRemoveData(0, 20, 20, false));
732 E : EXPECT_EQ(40u, block1->size());
733 E : EXPECT_EQ(0u, block1->data_size());
734 E : }
735 :
736 E : TEST_F(BlockTest, InsertOrRemoveDataSameSizeAllocate) {
737 : BlockGraph::Block* block1 = image_.AddBlock(
738 E : BlockGraph::DATA_BLOCK, 40, "Block1");
739 :
740 E : EXPECT_TRUE(block1->InsertOrRemoveData(0, 20, 20, true));
741 E : EXPECT_EQ(40u, block1->size());
742 E : EXPECT_EQ(20u, block1->data_size());
743 E : }
744 :
745 E : TEST_F(BlockTest, InsertOrRemoveGrowNoAllocate) {
746 : BlockGraph::Block* block1 = image_.AddBlock(
747 E : BlockGraph::DATA_BLOCK, 40, "Block1");
748 :
749 E : EXPECT_TRUE(block1->InsertOrRemoveData(0, 10, 20, false));
750 E : EXPECT_EQ(50u, block1->size());
751 E : EXPECT_EQ(0u, block1->data_size());
752 E : }
753 :
754 E : TEST_F(BlockTest, InsertOrRemoveGrowAllocate) {
755 : BlockGraph::Block* block1 = image_.AddBlock(
756 E : BlockGraph::DATA_BLOCK, 40, "Block1");
757 :
758 E : EXPECT_TRUE(block1->InsertOrRemoveData(0, 10, 20, true));
759 E : EXPECT_EQ(50u, block1->size());
760 E : EXPECT_EQ(20u, block1->data_size());
761 E : }
762 :
763 E : TEST_F(BlockTest, InsertOrRemoveShrinkNoAllocate) {
764 : BlockGraph::Block* block1 = image_.AddBlock(
765 E : BlockGraph::DATA_BLOCK, 40, "Block1");
766 E : block1->AllocateData(15);
767 :
768 E : EXPECT_TRUE(block1->InsertOrRemoveData(0, 20, 10, false));
769 E : EXPECT_EQ(30u, block1->size());
770 E : EXPECT_EQ(10u, block1->data_size());
771 E : }
772 :
773 E : TEST_F(BlockTest, InsertOrRemoveShrinkAllocate) {
774 : BlockGraph::Block* block1 = image_.AddBlock(
775 E : BlockGraph::DATA_BLOCK, 40, "Block1");
776 :
777 E : EXPECT_TRUE(block1->InsertOrRemoveData(0, 20, 10, true));
778 E : EXPECT_EQ(30u, block1->size());
779 E : EXPECT_EQ(10u, block1->data_size());
780 E : }
781 :
782 E : TEST_F(BlockTest, HasExternalReferrers) {
783 : // Create block1 that refers to itself. It has no external referrers.
784 : BlockGraph::Block* block1 = image_.AddBlock(
785 E : BlockGraph::DATA_BLOCK, 40, "Block1");
786 E : ASSERT_TRUE(block1 != NULL);
787 : EXPECT_TRUE(block1->SetReference(
788 E : 0, BlockGraph::Reference(BlockGraph::ABSOLUTE_REF, 4, block1, 0, 0)));
789 E : EXPECT_FALSE(block1->HasExternalReferrers());
790 :
791 : // Create a second block that refers to block1.
792 : BlockGraph::Block* block2 = image_.AddBlock(
793 E : BlockGraph::DATA_BLOCK, 40, "Block2");
794 E : ASSERT_TRUE(block2 != NULL);
795 : EXPECT_TRUE(block2->SetReference(
796 E : 0, BlockGraph::Reference(BlockGraph::ABSOLUTE_REF, 4, block1, 0, 0)));
797 :
798 : // There should now be an external referrer to block1.
799 E : EXPECT_TRUE(block1->HasExternalReferrers());
800 E : }
801 :
802 E : TEST_F(BlockTest, RemoveAllReferences) {
803 : // Create block1 that refers to itself. It has no external referrers.
804 : BlockGraph::Block* block1 = image_.AddBlock(
805 E : BlockGraph::DATA_BLOCK, 40, "Block1");
806 E : ASSERT_TRUE(block1 != NULL);
807 : EXPECT_TRUE(block1->SetReference(
808 E : 0, BlockGraph::Reference(BlockGraph::ABSOLUTE_REF, 4, block1, 0, 0)));
809 :
810 : // Create a second block for block1 to refer to.
811 : BlockGraph::Block* block2 = image_.AddBlock(
812 E : BlockGraph::DATA_BLOCK, 40, "Block2");
813 E : ASSERT_TRUE(block2 != NULL);
814 : EXPECT_TRUE(block1->SetReference(
815 E : 4, BlockGraph::Reference(BlockGraph::ABSOLUTE_REF, 4, block2, 0, 0)));
816 :
817 : // Verify that the references are as expected.
818 E : EXPECT_EQ(2U, block1->references().size());
819 E : EXPECT_EQ(1U, block1->referrers().size());
820 E : EXPECT_EQ(1U, block2->referrers().size());
821 :
822 : // Remove all references from block1.
823 E : EXPECT_TRUE(block1->RemoveAllReferences());
824 :
825 : // Verify that the references are as expected.
826 E : EXPECT_EQ(0U, block1->references().size());
827 E : EXPECT_EQ(0U, block1->referrers().size());
828 E : EXPECT_EQ(0U, block2->referrers().size());
829 E : }
830 :
831 E : TEST(BlockGraphTest, BlockTypeToString) {
832 E : for (int type = 0; type < BlockGraph::BLOCK_TYPE_MAX; ++type) {
833 : BlockGraph::BlockType block_type =
834 E : static_cast<BlockGraph::BlockType>(type);
835 E : EXPECT_TRUE(BlockGraph::BlockTypeToString(block_type) != NULL);
836 E : }
837 E : }
838 :
839 E : TEST(BlockGraphTest, LabelAttributesToString) {
840 E : BlockGraph::LabelAttributes label_attr = 1;
841 E : for (; label_attr != BlockGraph::LABEL_ATTRIBUTES_MAX; label_attr <<= 1) {
842 E : std::string s = BlockGraph::LabelAttributesToString(label_attr);
843 E : EXPECT_FALSE(s.empty());
844 E : }
845 :
846 E : label_attr = BlockGraph::LABEL_ATTRIBUTES_MAX - 1;
847 E : std::string s = BlockGraph::LabelAttributesToString(label_attr);
848 E : EXPECT_FALSE(s.empty());
849 E : }
850 :
851 E : TEST(BlockGraphTest, AddSections) {
852 E : BlockGraph image;
853 E : ASSERT_EQ(0u, image.sections().size());
854 :
855 E : BlockGraph::Section* section0 = image.AddSection("foo", 0);
856 E : ASSERT_TRUE(section0 != NULL);
857 E : ASSERT_EQ("foo", section0->name());
858 E : ASSERT_EQ(0u, section0->characteristics());
859 E : ASSERT_EQ(1u, image.sections().size());
860 :
861 E : BlockGraph::Section* section1 = image.AddSection("foo", 0);
862 E : ASSERT_TRUE(section1 != NULL);
863 E : ASSERT_EQ("foo", section1->name());
864 E : ASSERT_EQ(0u, section1->characteristics());
865 E : ASSERT_EQ(2u, image.sections().size());
866 :
867 : // This section has the same name and characteristics, but it should not be
868 : // the same section as section0.
869 E : EXPECT_TRUE(section0 != section1);
870 E : EXPECT_NE(section0->id(), section1->id());
871 :
872 E : BlockGraph::Section* section2 = image.FindOrAddSection("foo", 1);
873 E : ASSERT_TRUE(section2 != NULL);
874 E : ASSERT_EQ("foo", section2->name());
875 E : ASSERT_EQ(1u, section2->characteristics());
876 E : ASSERT_EQ(2u, image.sections().size());
877 :
878 : // This should be the same as section0, the first instance of a section
879 : // with name 'foo'.
880 E : EXPECT_EQ(section0, section2);
881 :
882 E : BlockGraph::Section* section3 = image.FindOrAddSection("bar", 1);
883 E : ASSERT_TRUE(section3 != NULL);
884 E : ASSERT_EQ("bar", section3->name());
885 E : ASSERT_EQ(1u, section3->characteristics());
886 E : ASSERT_EQ(3u, image.sections().size());
887 :
888 : // Test out FindSection.
889 E : EXPECT_EQ(section0, image.FindSection("foo"));
890 E : EXPECT_EQ(section3, image.FindSection("bar"));
891 E : EXPECT_TRUE(image.FindSection("baz") == NULL);
892 E : }
893 :
894 E : TEST(BlockGraphTest, RemoveSection) {
895 E : BlockGraph image;
896 E : ASSERT_EQ(0u, image.sections().size());
897 :
898 E : BlockGraph::Section* section0 = image.AddSection("foo", 0);
899 E : ASSERT_TRUE(section0 != NULL);
900 E : ASSERT_EQ(1u, image.sections().size());
901 :
902 E : BlockGraph::Section* section1 = image.AddSection("bar", 0);
903 E : ASSERT_TRUE(section1 != NULL);
904 E : ASSERT_EQ(2u, image.sections().size());
905 :
906 : // We should not be able to delete a non-existent section.
907 E : EXPECT_FALSE(image.RemoveSectionById(BlockGraph::kInvalidSectionId));
908 E : ASSERT_EQ(2u, image.sections().size());
909 :
910 : // Deleting normal sections should work just fine.
911 :
912 E : EXPECT_TRUE(image.RemoveSectionById(section0->id()));
913 E : ASSERT_EQ(1u, image.sections().size());
914 :
915 E : EXPECT_TRUE(image.RemoveSection(section1));
916 E : ASSERT_EQ(0u, image.sections().size());
917 E : }
918 :
919 E : TEST(BlockGraphTest, CopyBlock) {
920 E : BlockGraph image;
921 E : uint8 kTestData[] = {3, 1, 4, 1, 5, 9};
922 :
923 : // Add some blocks to the image.
924 E : BlockGraph::Block* b1 = image.AddBlock(BlockGraph::CODE_BLOCK, 0x20, "b1");
925 E : BlockGraph::Block* b2 = image.AddBlock(BlockGraph::CODE_BLOCK, 0x20, "b2");
926 E : BlockGraph::Block* b3 = image.AddBlock(BlockGraph::CODE_BLOCK, 0x20, "b3");
927 E : BlockGraph::Block* b4 = image.AddBlock(BlockGraph::CODE_BLOCK, 0x20, "b4");
928 E : BlockGraph::Block* b5 = image.AddBlock(BlockGraph::DATA_BLOCK, 0x20, "b5");
929 E : ASSERT_TRUE(b1 != nullptr);
930 E : ASSERT_TRUE(b2 != nullptr);
931 E : ASSERT_TRUE(b3 != nullptr);
932 E : ASSERT_TRUE(b4 != nullptr);
933 E : ASSERT_TRUE(b5 != nullptr);
934 E : EXPECT_EQ(5u, image.blocks().size());
935 :
936 E : b2->SetLabel(6, "foo", BlockGraph::CODE_LABEL);
937 E : b2->SetLabel(17, "bar", BlockGraph::DATA_LABEL);
938 E : b2->AllocateData(12);
939 E : ASSERT_TRUE(b2->owns_data());
940 :
941 E : b5->SetData(kTestData, sizeof(kTestData));
942 E : ASSERT_FALSE(b5->owns_data());
943 E : ASSERT_EQ(arraysize(kTestData), b5->data_size());
944 E : ASSERT_EQ(kTestData, b5->data());
945 :
946 : // Add a reference from block 1 to block 2.
947 E : BlockGraph::Reference ref12(BlockGraph::PC_RELATIVE_REF, 1, b2, 9, 1);
948 E : ASSERT_TRUE(b1->SetReference(0, ref12));
949 E : EXPECT_THAT(b1->references(), testing::Contains(std::make_pair(0, ref12)));
950 E : EXPECT_THAT(b2->referrers(), testing::Contains(std::make_pair(b1, 0)));
951 :
952 : // Add a self-reference inside block 2.
953 E : BlockGraph::Reference ref22(BlockGraph::PC_RELATIVE_REF, 1, b2, 5, 1);
954 E : ASSERT_TRUE(b2->SetReference(7, ref22));
955 E : EXPECT_THAT(b2->references(), testing::Contains(std::make_pair(7, ref22)));
956 E : EXPECT_THAT(b2->referrers(), testing::Contains(std::make_pair(b2, 7)));
957 :
958 : // Add a reference from block 2 to block 3.
959 E : BlockGraph::Reference ref23(BlockGraph::PC_RELATIVE_REF, 1, b3, 11, 1);
960 E : ASSERT_TRUE(b2->SetReference(0, ref23));
961 E : EXPECT_THAT(b2->references(), testing::Contains(std::make_pair(0, ref23)));
962 E : EXPECT_THAT(b3->referrers(), testing::Contains(std::make_pair(b2, 0)));
963 :
964 E : EXPECT_EQ(1u, b1->references().size());
965 E : EXPECT_EQ(2u, b2->referrers().size());
966 E : EXPECT_EQ(2u, b2->references().size());
967 E : EXPECT_EQ(1u, b3->referrers().size());
968 :
969 : // Copy block 2.
970 E : BlockGraph::Block* b2copy = image.CopyBlock(b2, "b2_copy");
971 E : ASSERT_TRUE(b2copy != nullptr);
972 E : EXPECT_EQ(6u, image.blocks().size());
973 :
974 E : EXPECT_EQ(b2->type(), b2copy->type());
975 E : EXPECT_EQ(b2->size(), b2copy->size());
976 E : EXPECT_EQ("b2_copy", b2copy->name());
977 E : EXPECT_EQ(b2->alignment(), b2copy->alignment());
978 E : EXPECT_EQ(b2->alignment_offset(), b2copy->alignment_offset());
979 E : EXPECT_EQ(b2->padding_before(), b2copy->padding_before());
980 E : EXPECT_EQ(b2->compiland_name(), b2copy->compiland_name());
981 E : EXPECT_EQ(b2->attributes(), b2copy->attributes());
982 E : EXPECT_EQ(b2->section(), b2copy->section());
983 E : EXPECT_EQ(b2->source_ranges(), b2copy->source_ranges());
984 E : EXPECT_TRUE(b2copy->owns_data());
985 E : EXPECT_EQ(b2->data_size(), b2copy->data_size());
986 :
987 : // Expect that we copied references 2->2 and 2->3, but not 1->2.
988 E : EXPECT_EQ(1u, b1->references().size());
989 E : EXPECT_EQ(2u, b2->referrers().size());
990 E : EXPECT_EQ(2u, b2->references().size());
991 E : EXPECT_EQ(1u, b2copy->referrers().size());
992 E : EXPECT_EQ(2u, b2copy->references().size());
993 : EXPECT_THAT(b2copy->references(),
994 E : testing::Contains(std::make_pair(0, ref23)));
995 E : EXPECT_EQ(2u, b3->referrers().size());
996 :
997 : // Expect labels to be copied.
998 E : BlockGraph::Label b2label_foo;
999 E : EXPECT_TRUE(b2copy->HasLabel(6));
1000 E : EXPECT_TRUE(b2copy->GetLabel(6, &b2label_foo));
1001 E : EXPECT_EQ("foo", b2label_foo.name());
1002 E : EXPECT_TRUE(b2label_foo.has_attributes(BlockGraph::CODE_LABEL));
1003 E : EXPECT_FALSE(b2label_foo.has_attributes(BlockGraph::DATA_LABEL));
1004 :
1005 E : BlockGraph::Label b2label_bar;
1006 E : EXPECT_TRUE(b2copy->HasLabel(17));
1007 E : EXPECT_TRUE(b2copy->GetLabel(17, &b2label_bar));
1008 E : EXPECT_EQ("bar", b2label_bar.name());
1009 E : EXPECT_FALSE(b2label_bar.has_attributes(BlockGraph::CODE_LABEL));
1010 E : EXPECT_TRUE(b2label_bar.has_attributes(BlockGraph::DATA_LABEL));
1011 :
1012 : // Copy block 5.
1013 E : BlockGraph::Block* b5copy = image.CopyBlock(b5, "b5_copy");
1014 E : ASSERT_TRUE(b5copy != nullptr);
1015 E : EXPECT_EQ(7u, image.blocks().size());
1016 :
1017 E : EXPECT_EQ(b5->type(), b5copy->type());
1018 E : EXPECT_EQ(b5->size(), b5copy->size());
1019 E : EXPECT_EQ("b5_copy", b5copy->name());
1020 E : EXPECT_EQ(b5->alignment(), b5copy->alignment());
1021 E : EXPECT_EQ(b5->alignment_offset(), b5copy->alignment_offset());
1022 E : EXPECT_EQ(b5->padding_before(), b5copy->padding_before());
1023 E : EXPECT_EQ(b5->compiland_name(), b5copy->compiland_name());
1024 E : EXPECT_EQ(b5->attributes(), b5copy->attributes());
1025 E : EXPECT_EQ(b5->section(), b5copy->section());
1026 E : EXPECT_EQ(b5->source_ranges(), b5copy->source_ranges());
1027 E : EXPECT_FALSE(b5copy->owns_data());
1028 E : EXPECT_EQ(b5->data_size(), b5copy->data_size());
1029 :
1030 : // Expect data pointer to be copied (don't own data).
1031 E : EXPECT_EQ(b5->data_size(), b5copy->data_size());
1032 E : EXPECT_EQ(b5->data(), b5copy->data());
1033 E : }
1034 :
1035 E : TEST(BlockGraphTest, RemoveBlock) {
1036 E : BlockGraph image;
1037 :
1038 : // Add some blocks to the image.
1039 E : BlockGraph::Block* b1 = image.AddBlock(BlockGraph::CODE_BLOCK, 0x20, "b1");
1040 E : BlockGraph::Block* b2 = image.AddBlock(BlockGraph::CODE_BLOCK, 0x20, "b2");
1041 E : BlockGraph::Block* b3 = image.AddBlock(BlockGraph::CODE_BLOCK, 0x20, "b3");
1042 E : BlockGraph::Block* b4 = image.AddBlock(BlockGraph::CODE_BLOCK, 0x20, "b4");
1043 E : ASSERT_TRUE(b1 != NULL);
1044 E : ASSERT_TRUE(b2 != NULL);
1045 E : ASSERT_TRUE(b3 != NULL);
1046 E : ASSERT_TRUE(b4 != NULL);
1047 E : EXPECT_EQ(4u, image.blocks().size());
1048 :
1049 : // Add a reference from block 1 to block 2.
1050 E : BlockGraph::Reference ref12(BlockGraph::PC_RELATIVE_REF, 1, b2, 9, 9);
1051 E : ASSERT_TRUE(b1->SetReference(0, ref12));
1052 E : EXPECT_THAT(b1->references(), testing::Contains(std::make_pair(0, ref12)));
1053 E : EXPECT_THAT(b2->referrers(), testing::Contains(std::make_pair(b1, 0)));
1054 E : EXPECT_EQ(1u, b1->references().size());
1055 E : EXPECT_EQ(1u, b2->referrers().size());
1056 :
1057 : // Try to delete Block 1. This should fail because it has references.
1058 E : ASSERT_FALSE(image.RemoveBlock(b1));
1059 E : EXPECT_EQ(4u, image.blocks().size());
1060 :
1061 : // Try to delete Block 2. This should fail because it has referrers.
1062 E : ASSERT_FALSE(image.RemoveBlockById(b2->id()));
1063 E : EXPECT_EQ(4u, image.blocks().size());
1064 :
1065 : // Try to delete a block that doesn't belong to the block graph. This
1066 : // should fail.
1067 E : BlockGraph other_image;
1068 : BlockGraph::Block* other_block =
1069 E : other_image.AddBlock(BlockGraph::CODE_BLOCK, 0x20, "other_block");
1070 E : ASSERT_FALSE(image.RemoveBlock(other_block));
1071 E : EXPECT_EQ(4u, image.blocks().size());
1072 :
1073 : // Try to delete a block with an invalid ID. This should fail.
1074 E : ASSERT_FALSE(image.RemoveBlockById(15));
1075 E : EXPECT_EQ(4u, image.blocks().size());
1076 :
1077 : // Delete block 3.
1078 E : ASSERT_TRUE(image.RemoveBlock(b3));
1079 E : EXPECT_EQ(3u, image.blocks().size());
1080 :
1081 : // Delete block 4.
1082 E : ASSERT_TRUE(image.RemoveBlockById(b4->id()));
1083 E : EXPECT_EQ(2u, image.blocks().size());
1084 E : }
1085 :
1086 E : TEST(BlockGraphTest, References) {
1087 E : BlockGraph image;
1088 :
1089 E : BlockGraph::Block* b1 = image.AddBlock(BlockGraph::CODE_BLOCK, 0x20, "b1");
1090 E : BlockGraph::Block* b2 = image.AddBlock(BlockGraph::CODE_BLOCK, 0x20, "b2");
1091 E : BlockGraph::Block* b3 = image.AddBlock(BlockGraph::CODE_BLOCK, 0x20, "b3");
1092 E : ASSERT_TRUE(b1 != NULL);
1093 E : ASSERT_TRUE(b2 != NULL);
1094 E : ASSERT_TRUE(b3 != NULL);
1095 :
1096 E : ASSERT_TRUE(b1->references().empty());
1097 E : ASSERT_TRUE(b1->referrers().empty());
1098 E : ASSERT_TRUE(b2->references().empty());
1099 E : ASSERT_TRUE(b2->referrers().empty());
1100 E : ASSERT_TRUE(b3->references().empty());
1101 E : ASSERT_TRUE(b3->referrers().empty());
1102 :
1103 E : BlockGraph::Reference dummy;
1104 E : ASSERT_FALSE(dummy.IsValid());
1105 :
1106 : // Add the first reference, and test that we get a backref.
1107 E : BlockGraph::Reference r_pc(BlockGraph::PC_RELATIVE_REF, 1, b2, 9, 9);
1108 E : ASSERT_TRUE(r_pc.IsValid());
1109 E : ASSERT_EQ(BlockGraph::PC_RELATIVE_REF, r_pc.type());
1110 E : ASSERT_EQ(1, r_pc.size());
1111 E : ASSERT_EQ(b2, r_pc.referenced());
1112 E : ASSERT_EQ(9, r_pc.offset());
1113 :
1114 E : ASSERT_TRUE(b1->SetReference(0, r_pc));
1115 E : EXPECT_THAT(b2->referrers(), testing::Contains(std::make_pair(b1, 0)));
1116 :
1117 E : ASSERT_TRUE(b1->SetReference(1, r_pc));
1118 E : EXPECT_THAT(b2->referrers(), testing::Contains(std::make_pair(b1, 1)));
1119 :
1120 E : BlockGraph::Reference r_abs(BlockGraph::ABSOLUTE_REF, 4, b2, 13, 13);
1121 E : ASSERT_FALSE(b1->SetReference(1, r_abs));
1122 E : BlockGraph::Reference r_rel(BlockGraph::RELATIVE_REF, 4, b2, 17, 17);
1123 E : ASSERT_TRUE(b1->SetReference(5, r_rel));
1124 E : BlockGraph::Reference r_file(BlockGraph::FILE_OFFSET_REF, 4, b2, 23, 23);
1125 E : ASSERT_TRUE(b1->SetReference(9, r_file));
1126 :
1127 E : BlockGraph::Reference r_sect(BlockGraph::SECTION_REF, 2, b2, 0, 0);
1128 E : ASSERT_TRUE(b1->SetReference(13, r_sect));
1129 : BlockGraph::Reference r_sect_off(BlockGraph::SECTION_OFFSET_REF, 4,
1130 E : b2, 27, 27);
1131 E : ASSERT_TRUE(b1->SetReference(15, r_sect_off));
1132 :
1133 : // Test that the reference map is as expected.
1134 E : BlockGraph::Block::ReferenceMap expected;
1135 E : expected.insert(std::make_pair(0, r_pc));
1136 E : expected.insert(std::make_pair(1, r_abs));
1137 E : expected.insert(std::make_pair(5, r_rel));
1138 E : expected.insert(std::make_pair(9, r_file));
1139 E : expected.insert(std::make_pair(13, r_sect));
1140 E : expected.insert(std::make_pair(15, r_sect_off));
1141 E : EXPECT_THAT(b1->references(), testing::ContainerEq(expected));
1142 :
1143 : // Test reference transfer.
1144 : // This should fail, as all the references will fall outside b3.
1145 : // TODO(chrisha): We need to create a logging MessageHandler that we can
1146 : // put test expectations on. This test is meant to fail, but we don't
1147 : // want to see the error message it would produce! Ideally, this should
1148 : // live in 'syzygy/testing' or something of the like, as it could be
1149 : // used across many unittests. For now, we simply disable logging for
1150 : // this test.
1151 E : int old_level = logging::GetMinLogLevel();
1152 E : logging::SetMinLogLevel(logging::LOG_FATAL);
1153 : ASSERT_FALSE(b2->TransferReferrers(b3->size(),
1154 E : b3, BlockGraph::Block::kTransferInternalReferences));
1155 E : logging::SetMinLogLevel(old_level);
1156 :
1157 : // Now move the references from b2 to b3
1158 : ASSERT_TRUE(b2->TransferReferrers(0,
1159 E : b3, BlockGraph::Block::kTransferInternalReferences));
1160 : // Test that b2 no longer has referrers.
1161 E : EXPECT_THAT(b2->referrers(), BlockGraph::Block::ReferrerSet());
1162 :
1163 : // Test that the references transferred as expected.
1164 E : expected.clear();
1165 : expected.insert(std::make_pair(0,
1166 E : BlockGraph::Reference(BlockGraph::PC_RELATIVE_REF, 1, b3, 9, 9)));
1167 : expected.insert(std::make_pair(1,
1168 E : BlockGraph::Reference(BlockGraph::ABSOLUTE_REF, 4, b3, 13, 13)));
1169 : expected.insert(std::make_pair(5,
1170 E : BlockGraph::Reference(BlockGraph::RELATIVE_REF, 4, b3, 17, 17)));
1171 : expected.insert(std::make_pair(9,
1172 E : BlockGraph::Reference(BlockGraph::FILE_OFFSET_REF, 4, b3, 23, 23)));
1173 : expected.insert(std::make_pair(13,
1174 E : BlockGraph::Reference(BlockGraph::SECTION_REF, 2, b3, 0, 0)));
1175 : expected.insert(std::make_pair(15,
1176 E : BlockGraph::Reference(BlockGraph::SECTION_OFFSET_REF, 4, b3, 27, 27)));
1177 E : EXPECT_THAT(b1->references(), testing::ContainerEq(expected));
1178 :
1179 : // Remove the references.
1180 E : ASSERT_TRUE(b1->RemoveReference(0));
1181 E : ASSERT_TRUE(b1->RemoveReference(1));
1182 E : ASSERT_TRUE(b1->RemoveReference(5));
1183 E : ASSERT_TRUE(b1->RemoveReference(9));
1184 E : ASSERT_TRUE(b1->RemoveReference(13));
1185 E : ASSERT_TRUE(b1->RemoveReference(15));
1186 E : EXPECT_THAT(b1->references(), BlockGraph::Block::ReferenceMap());
1187 :
1188 E : EXPECT_THAT(b2->referrers(), BlockGraph::Block::ReferrerSet());
1189 E : }
1190 :
1191 E : TEST(BlockGraphTest, Labels) {
1192 E : BlockGraph image;
1193 :
1194 : BlockGraph::Block* block =
1195 E : image.AddBlock(BlockGraph::CODE_BLOCK, 0x20, "labeled");
1196 E : ASSERT_TRUE(block->labels().empty());
1197 E : for (int i = 0; i < 0x20; ++i) {
1198 E : BlockGraph::Label label;
1199 E : ASSERT_FALSE(block->HasLabel(i));
1200 E : EXPECT_FALSE(block->GetLabel(i, &label));
1201 E : EXPECT_FALSE(block->RemoveLabel(i));
1202 E : }
1203 :
1204 E : EXPECT_TRUE(block->SetLabel(13, "foo", BlockGraph::DATA_LABEL));
1205 E : EXPECT_FALSE(block->SetLabel(13, "foo2", BlockGraph::DATA_LABEL));
1206 :
1207 E : EXPECT_TRUE(block->SetLabel(17, "bar", BlockGraph::CODE_LABEL));
1208 E : EXPECT_FALSE(block->SetLabel(17, "bar2", BlockGraph::CODE_LABEL));
1209 :
1210 E : EXPECT_TRUE(block->SetLabel(15, "baz", BlockGraph::CODE_LABEL));
1211 E : EXPECT_TRUE(block->HasLabel(15));
1212 E : EXPECT_TRUE(block->RemoveLabel(15));
1213 E : EXPECT_FALSE(block->HasLabel(15));
1214 :
1215 E : for (int i = 0; i < 0x20; ++i) {
1216 E : BlockGraph::Label label;
1217 E : if (i == 13 || i == 17) {
1218 E : ASSERT_TRUE(block->HasLabel(i));
1219 E : EXPECT_TRUE(block->GetLabel(i, &label));
1220 E : EXPECT_EQ(std::string(i == 13 ? "foo" : "bar"), label.name());
1221 : EXPECT_EQ(i == 13 ? BlockGraph::DATA_LABEL :
1222 : BlockGraph::CODE_LABEL,
1223 E : label.attributes());
1224 E : } else {
1225 E : ASSERT_FALSE(block->HasLabel(i));
1226 E : EXPECT_FALSE(block->GetLabel(i, &label));
1227 : }
1228 E : }
1229 :
1230 E : BlockGraph::Block::LabelMap expected;
1231 : expected.insert(std::make_pair(
1232 E : 13, BlockGraph::Label("foo", BlockGraph::DATA_LABEL)));
1233 : expected.insert(std::make_pair(
1234 E : 17, BlockGraph::Label("bar", BlockGraph::CODE_LABEL)));
1235 E : EXPECT_THAT(block->labels(), testing::ContainerEq(expected));
1236 E : }
1237 :
1238 E : TEST(BlockGraphTest, StringTable) {
1239 E : std::string str1 = "Dummy";
1240 E : std::string str2 = "Foo";
1241 E : std::string str3 = "Bar";
1242 E : std::string str4 = "Foo";
1243 :
1244 : // Validate that string are interned correctly.
1245 E : BlockGraph block_graph;
1246 E : core::StringTable& strtab = block_graph.string_table();
1247 E : const std::string& interned_str1 = strtab.InternString(str1);
1248 E : const std::string& interned_str2 = strtab.InternString(str2);
1249 E : const std::string& interned_str3 = strtab.InternString(str3);
1250 E : const std::string& interned_str4 = strtab.InternString(str4);
1251 :
1252 E : EXPECT_NE(&interned_str1, &interned_str2);
1253 E : EXPECT_NE(&interned_str1, &interned_str3);
1254 E : EXPECT_NE(&interned_str1, &interned_str4);
1255 E : EXPECT_NE(&interned_str2, &interned_str3);
1256 E : EXPECT_EQ(&interned_str2, &interned_str4);
1257 E : EXPECT_NE(&interned_str3, &interned_str4);
1258 E : }
1259 :
1260 : namespace {
1261 :
1262 : class BlockGraphSerializationTest : public testing::Test {
1263 : public:
1264 : virtual void SetUp() {
1265 : ASSERT_TRUE(testing::GenerateTestBlockGraph(&image_));
1266 : }
1267 :
1268 : protected:
1269 : BlockGraph image_;
1270 : };
1271 :
1272 : } // namespace
1273 :
1274 E : TEST(BlockGraphAddressSpaceTest, AddBlock) {
1275 E : BlockGraph image;
1276 E : BlockGraph::AddressSpace address_space(&image);
1277 :
1278 : // We should be able to insert this block.
1279 : BlockGraph::Block* block = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1280 : RelativeAddress(0x1000),
1281 : 0x20,
1282 E : "code");
1283 E : ASSERT_TRUE(block != NULL);
1284 E : EXPECT_EQ(0x1000, block->addr().value());
1285 :
1286 : // But inserting anything that intersects with it should fail.
1287 : EXPECT_EQ(NULL, address_space.AddBlock(BlockGraph::CODE_BLOCK,
1288 : RelativeAddress(0x1000),
1289 : 0x20,
1290 E : "code"));
1291 :
1292 : // Overlapping from below.
1293 : EXPECT_EQ(NULL, address_space.AddBlock(BlockGraph::CODE_BLOCK,
1294 : RelativeAddress(0xFF0),
1295 : 0x20,
1296 E : "code"));
1297 : // Enclosing.
1298 : EXPECT_EQ(NULL, address_space.AddBlock(BlockGraph::CODE_BLOCK,
1299 : RelativeAddress(0xFF0),
1300 : 0x30,
1301 E : "code"));
1302 : // Itersecting to end.
1303 : EXPECT_EQ(NULL, address_space.AddBlock(BlockGraph::CODE_BLOCK,
1304 : RelativeAddress(0x1010),
1305 : 0x10,
1306 E : "code"));
1307 : // Intersecting, overlapping the back.
1308 : EXPECT_EQ(NULL, address_space.AddBlock(BlockGraph::CODE_BLOCK,
1309 : RelativeAddress(0x1010),
1310 : 0x20,
1311 E : "code"));
1312 :
1313 : // We should be able to insert blocks above and below the one above.
1314 : EXPECT_TRUE(address_space.AddBlock(BlockGraph::CODE_BLOCK,
1315 : RelativeAddress(0xFF0),
1316 : 0x10,
1317 E : "code") != NULL);
1318 : EXPECT_TRUE(address_space.AddBlock(BlockGraph::CODE_BLOCK,
1319 : RelativeAddress(0x1020),
1320 : 0x10,
1321 E : "code") != NULL);
1322 :
1323 : // We should be able to add arbitrary many zero-sized blocks at any address.
1324 : EXPECT_TRUE(address_space.AddBlock(BlockGraph::CODE_BLOCK,
1325 : RelativeAddress(0x1020),
1326 : 0,
1327 E : "zerocode1") != NULL);
1328 : EXPECT_EQ(address_space.address_space_impl().size() + 1,
1329 E : address_space.block_addresses().size());
1330 : EXPECT_TRUE(address_space.AddBlock(BlockGraph::CODE_BLOCK,
1331 : RelativeAddress(0x1020),
1332 : 0,
1333 E : "zerocode2") != NULL);
1334 : EXPECT_EQ(address_space.address_space_impl().size() + 2,
1335 E : address_space.block_addresses().size());
1336 E : }
1337 :
1338 E : TEST(BlockGraphAddressSpaceTest, ResizeBlock) {
1339 E : BlockGraph image;
1340 E : BlockGraph::AddressSpace address_space(&image);
1341 E : EXPECT_EQ(0u, address_space.size());
1342 :
1343 : BlockGraph::Block* b1 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1344 : RelativeAddress(0x1000),
1345 : 0x20,
1346 E : "code");
1347 : BlockGraph::Block* b2 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1348 : RelativeAddress(0x1030),
1349 : 0x20,
1350 E : "code");
1351 E : EXPECT_EQ(2u, address_space.size());
1352 :
1353 E : const size_t kNewSizes[] = { 0x28, 0x32, 0x20, 0x20 };
1354 E : const size_t kExpectedSizes[] = { 0x28, 0x28, 0x20, 0x20 };
1355 : static_assert(sizeof(kNewSizes) == sizeof(kExpectedSizes),
1356 : "The size of the arrays should match.");
1357 :
1358 : // Grow successfully first. Then grow, but expect failure. Then shrink.
1359 : // Finally, stay the same size.
1360 E : for (size_t i = 0; i < arraysize(kNewSizes); ++i) {
1361 E : bool expected_result = kNewSizes[i] == kExpectedSizes[i];
1362 E : EXPECT_EQ(expected_result, address_space.ResizeBlock(b1, kNewSizes[i]));
1363 :
1364 E : EXPECT_EQ(2u, address_space.size());
1365 E : EXPECT_TRUE(address_space.ContainsBlock(b1));
1366 E : EXPECT_TRUE(address_space.ContainsBlock(b2));
1367 E : EXPECT_EQ(kExpectedSizes[i], b1->size());
1368 : BlockGraph::AddressSpace::RangeMapConstIter block_it =
1369 : address_space.address_space_impl().FindContaining(
1370 E : BlockGraph::AddressSpace::Range(RelativeAddress(0x1000), 1));
1371 E : EXPECT_TRUE(block_it != address_space.address_space_impl().end());
1372 E : EXPECT_EQ(RelativeAddress(0x1000), block_it->first.start());
1373 E : EXPECT_EQ(kExpectedSizes[i], block_it->first.size());
1374 E : EXPECT_EQ(b1, block_it->second);
1375 E : }
1376 :
1377 : // Shrink to size zero. The block should be in the list of blocks by address,
1378 : // but not in the actual address space itself.
1379 E : EXPECT_TRUE(address_space.ResizeBlock(b1, 0));
1380 E : EXPECT_EQ(2u, address_space.size());
1381 E : EXPECT_EQ(1u, address_space.address_space_impl().size());
1382 E : EXPECT_TRUE(address_space.ContainsBlock(b1));
1383 E : EXPECT_TRUE(address_space.ContainsBlock(b2));
1384 E : EXPECT_EQ(0u, b1->size());
1385 : BlockGraph::AddressSpace::RangeMapConstIter block_it =
1386 : address_space.address_space_impl().FindContaining(
1387 E : BlockGraph::AddressSpace::Range(RelativeAddress(0x1000), 1));
1388 E : EXPECT_TRUE(block_it == address_space.address_space_impl().end());
1389 : BlockGraph::AddressSpace::BlockAddressMap::const_iterator addr_it =
1390 E : address_space.block_addresses().find(b1);
1391 E : EXPECT_TRUE(addr_it != address_space.block_addresses().end());
1392 E : EXPECT_EQ(RelativeAddress(0x1000), addr_it->second);
1393 :
1394 : // Finally, trying to resize a block that's not in the address space
1395 : // should fail.
1396 E : BlockGraph::Block* b3 = image.AddBlock(BlockGraph::CODE_BLOCK, 1, "c");
1397 E : EXPECT_FALSE(address_space.ResizeBlock(b3, 1));
1398 E : }
1399 :
1400 E : TEST(BlockGraphAddressSpaceTest, InsertBlock) {
1401 E : BlockGraph image;
1402 E : BlockGraph::AddressSpace address_space(&image);
1403 :
1404 : BlockGraph::Block* block1 =
1405 E : image.AddBlock(BlockGraph::CODE_BLOCK, 0x10, "code");
1406 : BlockGraph::Block* block2 =
1407 E : image.AddBlock(BlockGraph::CODE_BLOCK, 0x10, "code");
1408 : BlockGraph::Block* block3 =
1409 E : image.AddBlock(BlockGraph::CODE_BLOCK, 0x10, "code");
1410 : BlockGraph::Block* block4 =
1411 E : image.AddBlock(BlockGraph::CODE_BLOCK, 0, "code");
1412 :
1413 E : ASSERT_TRUE(address_space.InsertBlock(RelativeAddress(0x1000), block1));
1414 E : ASSERT_FALSE(address_space.InsertBlock(RelativeAddress(0x1000), block2));
1415 E : ASSERT_TRUE(address_space.InsertBlock(RelativeAddress(0x1010), block2));
1416 E : ASSERT_FALSE(address_space.InsertBlock(RelativeAddress(0x1018), block3));
1417 E : ASSERT_TRUE(address_space.InsertBlock(RelativeAddress(0x1030), block3));
1418 E : ASSERT_TRUE(address_space.InsertBlock(RelativeAddress(0x1030), block4));
1419 E : EXPECT_EQ(4u, address_space.size());
1420 E : EXPECT_EQ(3u, address_space.address_space_impl().size());
1421 :
1422 E : RelativeAddress addr;
1423 E : EXPECT_TRUE(address_space.GetAddressOf(block1, &addr));
1424 E : EXPECT_EQ(0x1000, addr.value());
1425 E : EXPECT_EQ(0x1000, block1->addr().value());
1426 :
1427 E : EXPECT_TRUE(address_space.GetAddressOf(block2, &addr));
1428 E : EXPECT_EQ(0x1010, addr.value());
1429 E : EXPECT_EQ(0x1010, block2->addr().value());
1430 :
1431 E : EXPECT_TRUE(address_space.GetAddressOf(block3, &addr));
1432 E : EXPECT_EQ(0x1030, addr.value());
1433 E : EXPECT_EQ(0x1030, block3->addr().value());
1434 :
1435 E : EXPECT_TRUE(address_space.GetAddressOf(block4, &addr));
1436 E : EXPECT_EQ(0x1030, addr.value());
1437 E : EXPECT_EQ(0x1030, block4->addr().value());
1438 :
1439 : // Insert a block into a second address space.
1440 E : BlockGraph::AddressSpace address_space2(&image);
1441 E : EXPECT_TRUE(address_space2.InsertBlock(RelativeAddress(0x2000), block1));
1442 E : EXPECT_TRUE(address_space.GetAddressOf(block1, &addr));
1443 E : EXPECT_EQ(0x1000, addr.value());
1444 :
1445 E : EXPECT_TRUE(address_space2.GetAddressOf(block1, &addr));
1446 E : EXPECT_EQ(0x2000, addr.value());
1447 :
1448 E : EXPECT_EQ(0x2000, block1->addr().value());
1449 E : }
1450 :
1451 E : TEST(BlockGraphAddressSpaceTest, GetBlockByAddress) {
1452 E : BlockGraph image;
1453 E : BlockGraph::AddressSpace address_space(&image);
1454 :
1455 : BlockGraph::Block* block1 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1456 : RelativeAddress(0x1000),
1457 : 0x10,
1458 E : "code");
1459 : BlockGraph::Block* block2 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1460 : RelativeAddress(0x1010),
1461 : 0x10,
1462 E : "code");
1463 : BlockGraph::Block* block3 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1464 : RelativeAddress(0x1030),
1465 : 0x10,
1466 E : "code");
1467 :
1468 E : EXPECT_EQ(NULL, address_space.GetBlockByAddress(RelativeAddress(0xFFF)));
1469 :
1470 E : EXPECT_EQ(block1, address_space.GetBlockByAddress(RelativeAddress(0x1000)));
1471 E : EXPECT_EQ(block1, address_space.GetBlockByAddress(RelativeAddress(0x100F)));
1472 :
1473 E : EXPECT_EQ(block2, address_space.GetBlockByAddress(RelativeAddress(0x1010)));
1474 E : EXPECT_EQ(block2, address_space.GetBlockByAddress(RelativeAddress(0x101F)));
1475 :
1476 E : EXPECT_EQ(NULL, address_space.GetBlockByAddress(RelativeAddress(0x1020)));
1477 E : EXPECT_EQ(NULL, address_space.GetBlockByAddress(RelativeAddress(0x102F)));
1478 :
1479 E : EXPECT_EQ(block3, address_space.GetBlockByAddress(RelativeAddress(0x1030)));
1480 E : EXPECT_EQ(block3, address_space.GetBlockByAddress(RelativeAddress(0x103F)));
1481 :
1482 E : EXPECT_EQ(NULL, address_space.GetBlockByAddress(RelativeAddress(0x1040)));
1483 E : }
1484 :
1485 E : TEST(BlockGraphAddressSpaceTest, GetFirstIntersectingBlock) {
1486 E : BlockGraph image;
1487 E : BlockGraph::AddressSpace address_space(&image);
1488 :
1489 : BlockGraph::Block* block1 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1490 : RelativeAddress(0x1000),
1491 : 0x10,
1492 E : "code");
1493 : BlockGraph::Block* block2 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1494 : RelativeAddress(0x1010),
1495 : 0x10,
1496 E : "code");
1497 :
1498 : EXPECT_EQ(NULL,
1499 E : address_space.GetFirstIntersectingBlock(RelativeAddress(0xFFF), 0x1));
1500 : EXPECT_EQ(block1,
1501 E : address_space.GetFirstIntersectingBlock(RelativeAddress(0xFFF), 0x2));
1502 : EXPECT_EQ(block1,
1503 E : address_space.GetFirstIntersectingBlock(RelativeAddress(0x100F), 0x1));
1504 : EXPECT_EQ(block1,
1505 E : address_space.GetFirstIntersectingBlock(RelativeAddress(0x100F), 0x2));
1506 :
1507 : EXPECT_EQ(block2,
1508 E : address_space.GetFirstIntersectingBlock(RelativeAddress(0x1010), 0x40));
1509 E : }
1510 :
1511 E : TEST(BlockGraphAddressSpaceTest, GetContainingBlock) {
1512 E : BlockGraph image;
1513 E : BlockGraph::AddressSpace address_space(&image);
1514 :
1515 : BlockGraph::Block* block1 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1516 : RelativeAddress(0x1000),
1517 : 0x10,
1518 E : "code");
1519 : BlockGraph::Block* block2 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1520 : RelativeAddress(0x1010),
1521 : 0x10,
1522 E : "code");
1523 :
1524 : // Fully contained in block1
1525 : EXPECT_EQ(block1,
1526 E : address_space.GetContainingBlock(RelativeAddress(0x1004), 8));
1527 :
1528 : // Fully contained in block2
1529 : EXPECT_EQ(block2,
1530 E : address_space.GetContainingBlock(RelativeAddress(0x1014), 8));
1531 :
1532 : // Starts before but intersects with block1.
1533 E : EXPECT_EQ(NULL, address_space.GetContainingBlock(RelativeAddress(0x099E), 8));
1534 :
1535 : // Starts in the middle of block1 and overlaps into block2.
1536 E : EXPECT_EQ(NULL, address_space.GetContainingBlock(RelativeAddress(0x100a), 8));
1537 E : }
1538 :
1539 E : TEST(BlockGraphAddressSpaceTest, GetBlockAddress) {
1540 E : BlockGraph image;
1541 E : BlockGraph::AddressSpace address_space(&image);
1542 :
1543 : BlockGraph::Block* block1 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1544 : RelativeAddress(0x1000),
1545 : 0x10,
1546 E : "code");
1547 : BlockGraph::Block* block2 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1548 : RelativeAddress(0x1010),
1549 : 0x10,
1550 E : "code");
1551 : BlockGraph::Block* block3 =
1552 E : image.AddBlock(BlockGraph::CODE_BLOCK, 0x10, "code");
1553 :
1554 E : RelativeAddress addr;
1555 E : EXPECT_TRUE(address_space.GetAddressOf(block1, &addr));
1556 E : EXPECT_EQ(0x1000, addr.value());
1557 :
1558 E : EXPECT_TRUE(address_space.GetAddressOf(block2, &addr));
1559 E : EXPECT_EQ(0x1010, addr.value());
1560 :
1561 E : EXPECT_FALSE(address_space.GetAddressOf(block3, &addr));
1562 E : }
1563 :
1564 E : TEST(BlockGraphAddressSpaceTest, MergeIntersectingBlocks) {
1565 E : BlockGraph image;
1566 E : BlockGraph::AddressSpace address_space(&image);
1567 E : RelativeAddress addr1(0x1000);
1568 E : RelativeAddress addr2(0x1010);
1569 E : RelativeAddress addr3(0x1030);
1570 : BlockGraph::Block* block1 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1571 : addr1,
1572 : 0x10,
1573 E : "block1");
1574 : BlockGraph::Block* block2 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1575 : addr2,
1576 : 0x10,
1577 E : "block2");
1578 : BlockGraph::Block* block3 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1579 : addr3,
1580 : 0x10,
1581 E : "block3");
1582 E : ASSERT_TRUE(block2->SetLabel(0, "0x1010", BlockGraph::CODE_LABEL));
1583 E : ASSERT_TRUE(block2->SetLabel(4, "0x1014", BlockGraph::CODE_LABEL));
1584 E : ASSERT_TRUE(block3->SetLabel(0, "0x1030", BlockGraph::CODE_LABEL));
1585 E : ASSERT_TRUE(block3->SetLabel(4, "0x1034", BlockGraph::CODE_LABEL));
1586 :
1587 : block1->source_ranges().Push(BlockGraph::Block::DataRange(0, 0x10),
1588 E : BlockGraph::Block::SourceRange(addr1, 0x10));
1589 : block2->source_ranges().Push(BlockGraph::Block::DataRange(0, 0x10),
1590 E : BlockGraph::Block::SourceRange(addr2, 0x10));
1591 : block3->source_ranges().Push(BlockGraph::Block::DataRange(0, 0x10),
1592 E : BlockGraph::Block::SourceRange(addr3, 0x10));
1593 :
1594 : ASSERT_TRUE(block1->SetReference(0x1,
1595 E : BlockGraph::Reference(BlockGraph::ABSOLUTE_REF, 4, block2, 0x0, 0x0)));
1596 : ASSERT_TRUE(block1->SetReference(0x6,
1597 E : BlockGraph::Reference(BlockGraph::ABSOLUTE_REF, 4, block3, 0x0, 0x0)));
1598 : ASSERT_TRUE(block2->SetReference(0x1,
1599 E : BlockGraph::Reference(BlockGraph::PC_RELATIVE_REF, 1, block1, 0x4, 0x4)));
1600 : ASSERT_TRUE(block2->SetReference(0x6,
1601 E : BlockGraph::Reference(BlockGraph::PC_RELATIVE_REF, 4, block3, 0x4, 0x4)));
1602 : ASSERT_TRUE(block3->SetReference(0x1,
1603 E : BlockGraph::Reference(BlockGraph::PC_RELATIVE_REF, 4, block2, 0x4, 0x4)));
1604 :
1605 : // Set some attributes that should trivially propagate to the merged block.
1606 E : block2->set_attribute(BlockGraph::PE_PARSED);
1607 :
1608 : // Set an attribute that only propagates because it is present in both blocks.
1609 E : block2->set_attribute(BlockGraph::GAP_BLOCK);
1610 E : block3->set_attribute(BlockGraph::GAP_BLOCK);
1611 :
1612 : // Set an attribute that doesn't propagate because it is not present in both
1613 : // blocks.
1614 E : block2->set_attribute(BlockGraph::PADDING_BLOCK);
1615 :
1616 : // Blocks 2 and 3 will be merged.
1617 : BlockGraph::Block* merged = address_space.MergeIntersectingBlocks(
1618 E : BlockGraph::AddressSpace::Range(RelativeAddress(0x1014), 0x30));
1619 :
1620 E : ASSERT_TRUE(merged != NULL);
1621 E : ASSERT_EQ(RelativeAddress(0x1010), merged->addr());
1622 E : ASSERT_EQ(0x34, merged->size());
1623 :
1624 : // Expect the merged block to have meaningful source ranges.
1625 E : BlockGraph::Block::SourceRanges::RangePairs expected_source_ranges;
1626 : expected_source_ranges.push_back(
1627 : std::make_pair(BlockGraph::Block::DataRange(0, 0x10),
1628 E : BlockGraph::Block::SourceRange(addr2, 0x10)));
1629 : expected_source_ranges.push_back(
1630 : std::make_pair(BlockGraph::Block::DataRange(0x20, 0x10),
1631 E : BlockGraph::Block::SourceRange(addr3, 0x10)));
1632 : EXPECT_THAT(merged->source_ranges().range_pairs(),
1633 E : testing::ContainerEq(expected_source_ranges));
1634 :
1635 E : BlockGraph::Block::LabelMap expected_labels;
1636 : expected_labels.insert(std::make_pair(
1637 E : 0x00, BlockGraph::Label("0x1010", BlockGraph::CODE_LABEL)));
1638 : expected_labels.insert(std::make_pair(
1639 E : 0x04, BlockGraph::Label("0x1014", BlockGraph::CODE_LABEL)));
1640 : expected_labels.insert(std::make_pair(
1641 E : 0x20, BlockGraph::Label("0x1030", BlockGraph::CODE_LABEL)));
1642 : expected_labels.insert(std::make_pair(
1643 E : 0x24, BlockGraph::Label("0x1034", BlockGraph::CODE_LABEL)));
1644 E : EXPECT_THAT(merged->labels(), testing::ContainerEq(expected_labels));
1645 :
1646 E : BlockGraph::Block::ReferenceMap expected_refs;
1647 : expected_refs.insert(std::make_pair(0x1,
1648 E : BlockGraph::Reference(BlockGraph::PC_RELATIVE_REF, 1, block1, 0x4, 0x4)));
1649 : expected_refs.insert(std::make_pair(0x6,
1650 : BlockGraph::Reference(BlockGraph::PC_RELATIVE_REF, 4, merged, 0x24,
1651 E : 0x24)));
1652 : expected_refs.insert(std::make_pair(0x21,
1653 E : BlockGraph::Reference(BlockGraph::PC_RELATIVE_REF, 4, merged, 0x4, 0x4)));
1654 E : EXPECT_THAT(merged->references(), testing::ContainerEq(expected_refs));
1655 :
1656 E : expected_refs.clear();
1657 : expected_refs.insert(std::make_pair(0x1,
1658 E : BlockGraph::Reference(BlockGraph::ABSOLUTE_REF, 4, merged, 0x0, 0x0)));
1659 : expected_refs.insert(std::make_pair(0x6,
1660 E : BlockGraph::Reference(BlockGraph::ABSOLUTE_REF, 4, merged, 0x20, 0x20)));
1661 E : EXPECT_THAT(block1->references(), testing::ContainerEq(expected_refs));
1662 :
1663 : // Expect the attributes to have been propagated properly.
1664 : EXPECT_EQ(BlockGraph::PE_PARSED | BlockGraph::GAP_BLOCK,
1665 E : merged->attributes());
1666 :
1667 : // We expect that the block graph and the address space have the same size,
1668 : // as MergeIntersectingBlocks deletes the old blocks from the BlockGraph.
1669 E : EXPECT_EQ(image.blocks().size(), address_space.address_space_impl().size());
1670 E : }
1671 :
1672 E : TEST(BlockGraphAddressSpaceTest, ContainsBlock) {
1673 E : BlockGraph image;
1674 E : BlockGraph::AddressSpace address_space(&image);
1675 : BlockGraph::Block* block =
1676 E : image.AddBlock(BlockGraph::CODE_BLOCK, 0x10, "code");
1677 :
1678 E : ASSERT_FALSE(address_space.ContainsBlock(block));
1679 E : EXPECT_TRUE(address_space.InsertBlock(RelativeAddress(0x1000), block));
1680 E : ASSERT_TRUE(address_space.ContainsBlock(block));
1681 E : }
1682 :
1683 : } // namespace block_graph
|