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