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, RemoveBlock) {
920 E : BlockGraph image;
921 :
922 : // Add some blocks to the image.
923 E : BlockGraph::Block* b1 = image.AddBlock(BlockGraph::CODE_BLOCK, 0x20, "b1");
924 E : BlockGraph::Block* b2 = image.AddBlock(BlockGraph::CODE_BLOCK, 0x20, "b2");
925 E : BlockGraph::Block* b3 = image.AddBlock(BlockGraph::CODE_BLOCK, 0x20, "b3");
926 E : BlockGraph::Block* b4 = image.AddBlock(BlockGraph::CODE_BLOCK, 0x20, "b4");
927 E : ASSERT_TRUE(b1 != NULL);
928 E : ASSERT_TRUE(b2 != NULL);
929 E : ASSERT_TRUE(b3 != NULL);
930 E : ASSERT_TRUE(b4 != NULL);
931 E : EXPECT_EQ(4u, image.blocks().size());
932 :
933 : // Add a reference from block 1 to block 2.
934 E : BlockGraph::Reference ref12(BlockGraph::PC_RELATIVE_REF, 1, b2, 9, 9);
935 E : ASSERT_TRUE(b1->SetReference(0, ref12));
936 E : EXPECT_THAT(b1->references(), testing::Contains(std::make_pair(0, ref12)));
937 E : EXPECT_THAT(b2->referrers(), testing::Contains(std::make_pair(b1, 0)));
938 E : EXPECT_EQ(1u, b1->references().size());
939 E : EXPECT_EQ(1u, b2->referrers().size());
940 :
941 : // Try to delete Block 1. This should fail because it has references.
942 E : ASSERT_FALSE(image.RemoveBlock(b1));
943 E : EXPECT_EQ(4u, image.blocks().size());
944 :
945 : // Try to delete Block 2. This should fail because it has referrers.
946 E : ASSERT_FALSE(image.RemoveBlockById(b2->id()));
947 E : EXPECT_EQ(4u, image.blocks().size());
948 :
949 : // Try to delete a block that doesn't belong to the block graph. This
950 : // should fail.
951 E : BlockGraph other_image;
952 : BlockGraph::Block* other_block =
953 E : other_image.AddBlock(BlockGraph::CODE_BLOCK, 0x20, "other_block");
954 E : ASSERT_FALSE(image.RemoveBlock(other_block));
955 E : EXPECT_EQ(4u, image.blocks().size());
956 :
957 : // Try to delete a block with an invalid ID. This should fail.
958 E : ASSERT_FALSE(image.RemoveBlockById(15));
959 E : EXPECT_EQ(4u, image.blocks().size());
960 :
961 : // Delete block 3.
962 E : ASSERT_TRUE(image.RemoveBlock(b3));
963 E : EXPECT_EQ(3u, image.blocks().size());
964 :
965 : // Delete block 4.
966 E : ASSERT_TRUE(image.RemoveBlockById(b4->id()));
967 E : EXPECT_EQ(2u, image.blocks().size());
968 E : }
969 :
970 E : TEST(BlockGraphTest, References) {
971 E : BlockGraph image;
972 :
973 E : BlockGraph::Block* b1 = image.AddBlock(BlockGraph::CODE_BLOCK, 0x20, "b1");
974 E : BlockGraph::Block* b2 = image.AddBlock(BlockGraph::CODE_BLOCK, 0x20, "b2");
975 E : BlockGraph::Block* b3 = image.AddBlock(BlockGraph::CODE_BLOCK, 0x20, "b3");
976 E : ASSERT_TRUE(b1 != NULL);
977 E : ASSERT_TRUE(b2 != NULL);
978 E : ASSERT_TRUE(b3 != NULL);
979 :
980 E : ASSERT_TRUE(b1->references().empty());
981 E : ASSERT_TRUE(b1->referrers().empty());
982 E : ASSERT_TRUE(b2->references().empty());
983 E : ASSERT_TRUE(b2->referrers().empty());
984 E : ASSERT_TRUE(b3->references().empty());
985 E : ASSERT_TRUE(b3->referrers().empty());
986 :
987 E : BlockGraph::Reference dummy;
988 E : ASSERT_FALSE(dummy.IsValid());
989 :
990 : // Add the first reference, and test that we get a backref.
991 E : BlockGraph::Reference r_pc(BlockGraph::PC_RELATIVE_REF, 1, b2, 9, 9);
992 E : ASSERT_TRUE(r_pc.IsValid());
993 E : ASSERT_EQ(BlockGraph::PC_RELATIVE_REF, r_pc.type());
994 E : ASSERT_EQ(1, r_pc.size());
995 E : ASSERT_EQ(b2, r_pc.referenced());
996 E : ASSERT_EQ(9, r_pc.offset());
997 :
998 E : ASSERT_TRUE(b1->SetReference(0, r_pc));
999 E : EXPECT_THAT(b2->referrers(), testing::Contains(std::make_pair(b1, 0)));
1000 :
1001 E : ASSERT_TRUE(b1->SetReference(1, r_pc));
1002 E : EXPECT_THAT(b2->referrers(), testing::Contains(std::make_pair(b1, 1)));
1003 :
1004 E : BlockGraph::Reference r_abs(BlockGraph::ABSOLUTE_REF, 4, b2, 13, 13);
1005 E : ASSERT_FALSE(b1->SetReference(1, r_abs));
1006 E : BlockGraph::Reference r_rel(BlockGraph::RELATIVE_REF, 4, b2, 17, 17);
1007 E : ASSERT_TRUE(b1->SetReference(5, r_rel));
1008 E : BlockGraph::Reference r_file(BlockGraph::FILE_OFFSET_REF, 4, b2, 23, 23);
1009 E : ASSERT_TRUE(b1->SetReference(9, r_file));
1010 :
1011 E : BlockGraph::Reference r_sect(BlockGraph::SECTION_REF, 2, b2, 0, 0);
1012 E : ASSERT_TRUE(b1->SetReference(13, r_sect));
1013 : BlockGraph::Reference r_sect_off(BlockGraph::SECTION_OFFSET_REF, 4,
1014 E : b2, 27, 27);
1015 E : ASSERT_TRUE(b1->SetReference(15, r_sect_off));
1016 :
1017 : // Test that the reference map is as expected.
1018 E : BlockGraph::Block::ReferenceMap expected;
1019 E : expected.insert(std::make_pair(0, r_pc));
1020 E : expected.insert(std::make_pair(1, r_abs));
1021 E : expected.insert(std::make_pair(5, r_rel));
1022 E : expected.insert(std::make_pair(9, r_file));
1023 E : expected.insert(std::make_pair(13, r_sect));
1024 E : expected.insert(std::make_pair(15, r_sect_off));
1025 E : EXPECT_THAT(b1->references(), testing::ContainerEq(expected));
1026 :
1027 : // Test reference transfer.
1028 : // This should fail, as all the references will fall outside b3.
1029 : // TODO(chrisha): We need to create a logging MessageHandler that we can
1030 : // put test expectations on. This test is meant to fail, but we don't
1031 : // want to see the error message it would produce! Ideally, this should
1032 : // live in 'syzygy/testing' or something of the like, as it could be
1033 : // used across many unittests. For now, we simply disable logging for
1034 : // this test.
1035 E : int old_level = logging::GetMinLogLevel();
1036 E : logging::SetMinLogLevel(logging::LOG_FATAL);
1037 : ASSERT_FALSE(b2->TransferReferrers(b3->size(),
1038 E : b3, BlockGraph::Block::kTransferInternalReferences));
1039 E : logging::SetMinLogLevel(old_level);
1040 :
1041 : // Now move the references from b2 to b3
1042 : ASSERT_TRUE(b2->TransferReferrers(0,
1043 E : b3, BlockGraph::Block::kTransferInternalReferences));
1044 : // Test that b2 no longer has referrers.
1045 E : EXPECT_THAT(b2->referrers(), BlockGraph::Block::ReferrerSet());
1046 :
1047 : // Test that the references transferred as expected.
1048 E : expected.clear();
1049 : expected.insert(std::make_pair(0,
1050 E : BlockGraph::Reference(BlockGraph::PC_RELATIVE_REF, 1, b3, 9, 9)));
1051 : expected.insert(std::make_pair(1,
1052 E : BlockGraph::Reference(BlockGraph::ABSOLUTE_REF, 4, b3, 13, 13)));
1053 : expected.insert(std::make_pair(5,
1054 E : BlockGraph::Reference(BlockGraph::RELATIVE_REF, 4, b3, 17, 17)));
1055 : expected.insert(std::make_pair(9,
1056 E : BlockGraph::Reference(BlockGraph::FILE_OFFSET_REF, 4, b3, 23, 23)));
1057 : expected.insert(std::make_pair(13,
1058 E : BlockGraph::Reference(BlockGraph::SECTION_REF, 2, b3, 0, 0)));
1059 : expected.insert(std::make_pair(15,
1060 E : BlockGraph::Reference(BlockGraph::SECTION_OFFSET_REF, 4, b3, 27, 27)));
1061 E : EXPECT_THAT(b1->references(), testing::ContainerEq(expected));
1062 :
1063 : // Remove the references.
1064 E : ASSERT_TRUE(b1->RemoveReference(0));
1065 E : ASSERT_TRUE(b1->RemoveReference(1));
1066 E : ASSERT_TRUE(b1->RemoveReference(5));
1067 E : ASSERT_TRUE(b1->RemoveReference(9));
1068 E : ASSERT_TRUE(b1->RemoveReference(13));
1069 E : ASSERT_TRUE(b1->RemoveReference(15));
1070 E : EXPECT_THAT(b1->references(), BlockGraph::Block::ReferenceMap());
1071 :
1072 E : EXPECT_THAT(b2->referrers(), BlockGraph::Block::ReferrerSet());
1073 E : }
1074 :
1075 E : TEST(BlockGraphTest, Labels) {
1076 E : BlockGraph image;
1077 :
1078 : BlockGraph::Block* block =
1079 E : image.AddBlock(BlockGraph::CODE_BLOCK, 0x20, "labeled");
1080 E : ASSERT_TRUE(block->labels().empty());
1081 E : for (int i = 0; i < 0x20; ++i) {
1082 E : BlockGraph::Label label;
1083 E : ASSERT_FALSE(block->HasLabel(i));
1084 E : EXPECT_FALSE(block->GetLabel(i, &label));
1085 E : EXPECT_FALSE(block->RemoveLabel(i));
1086 E : }
1087 :
1088 E : EXPECT_TRUE(block->SetLabel(13, "foo", BlockGraph::DATA_LABEL));
1089 E : EXPECT_FALSE(block->SetLabel(13, "foo2", BlockGraph::DATA_LABEL));
1090 :
1091 E : EXPECT_TRUE(block->SetLabel(17, "bar", BlockGraph::CODE_LABEL));
1092 E : EXPECT_FALSE(block->SetLabel(17, "bar2", BlockGraph::CODE_LABEL));
1093 :
1094 E : EXPECT_TRUE(block->SetLabel(15, "baz", BlockGraph::CODE_LABEL));
1095 E : EXPECT_TRUE(block->HasLabel(15));
1096 E : EXPECT_TRUE(block->RemoveLabel(15));
1097 E : EXPECT_FALSE(block->HasLabel(15));
1098 :
1099 E : for (int i = 0; i < 0x20; ++i) {
1100 E : BlockGraph::Label label;
1101 E : if (i == 13 || i == 17) {
1102 E : ASSERT_TRUE(block->HasLabel(i));
1103 E : EXPECT_TRUE(block->GetLabel(i, &label));
1104 E : EXPECT_EQ(std::string(i == 13 ? "foo" : "bar"), label.name());
1105 : EXPECT_EQ(i == 13 ? BlockGraph::DATA_LABEL :
1106 : BlockGraph::CODE_LABEL,
1107 E : label.attributes());
1108 E : } else {
1109 E : ASSERT_FALSE(block->HasLabel(i));
1110 E : EXPECT_FALSE(block->GetLabel(i, &label));
1111 : }
1112 E : }
1113 :
1114 E : BlockGraph::Block::LabelMap expected;
1115 : expected.insert(std::make_pair(
1116 E : 13, BlockGraph::Label("foo", BlockGraph::DATA_LABEL)));
1117 : expected.insert(std::make_pair(
1118 E : 17, BlockGraph::Label("bar", BlockGraph::CODE_LABEL)));
1119 E : EXPECT_THAT(block->labels(), testing::ContainerEq(expected));
1120 E : }
1121 :
1122 E : TEST(BlockGraphTest, StringTable) {
1123 E : std::string str1 = "Dummy";
1124 E : std::string str2 = "Foo";
1125 E : std::string str3 = "Bar";
1126 E : std::string str4 = "Foo";
1127 :
1128 : // Validate that string are interned correctly.
1129 E : BlockGraph block_graph;
1130 E : core::StringTable& strtab = block_graph.string_table();
1131 E : const std::string& interned_str1 = strtab.InternString(str1);
1132 E : const std::string& interned_str2 = strtab.InternString(str2);
1133 E : const std::string& interned_str3 = strtab.InternString(str3);
1134 E : const std::string& interned_str4 = strtab.InternString(str4);
1135 :
1136 E : EXPECT_NE(&interned_str1, &interned_str2);
1137 E : EXPECT_NE(&interned_str1, &interned_str3);
1138 E : EXPECT_NE(&interned_str1, &interned_str4);
1139 E : EXPECT_NE(&interned_str2, &interned_str3);
1140 E : EXPECT_EQ(&interned_str2, &interned_str4);
1141 E : EXPECT_NE(&interned_str3, &interned_str4);
1142 E : }
1143 :
1144 : namespace {
1145 :
1146 : class BlockGraphSerializationTest : public testing::Test {
1147 : public:
1148 : virtual void SetUp() {
1149 : ASSERT_TRUE(testing::GenerateTestBlockGraph(&image_));
1150 : }
1151 :
1152 : protected:
1153 : BlockGraph image_;
1154 : };
1155 :
1156 : } // namespace
1157 :
1158 E : TEST(BlockGraphAddressSpaceTest, AddBlock) {
1159 E : BlockGraph image;
1160 E : BlockGraph::AddressSpace address_space(&image);
1161 :
1162 : // We should be able to insert this block.
1163 : BlockGraph::Block* block = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1164 : RelativeAddress(0x1000),
1165 : 0x20,
1166 E : "code");
1167 E : ASSERT_TRUE(block != NULL);
1168 E : EXPECT_EQ(0x1000, block->addr().value());
1169 :
1170 : // But inserting anything that intersects with it should fail.
1171 : EXPECT_EQ(NULL, address_space.AddBlock(BlockGraph::CODE_BLOCK,
1172 : RelativeAddress(0x1000),
1173 : 0x20,
1174 E : "code"));
1175 :
1176 : // Overlapping from below.
1177 : EXPECT_EQ(NULL, address_space.AddBlock(BlockGraph::CODE_BLOCK,
1178 : RelativeAddress(0xFF0),
1179 : 0x20,
1180 E : "code"));
1181 : // Enclosing.
1182 : EXPECT_EQ(NULL, address_space.AddBlock(BlockGraph::CODE_BLOCK,
1183 : RelativeAddress(0xFF0),
1184 : 0x30,
1185 E : "code"));
1186 : // Itersecting to end.
1187 : EXPECT_EQ(NULL, address_space.AddBlock(BlockGraph::CODE_BLOCK,
1188 : RelativeAddress(0x1010),
1189 : 0x10,
1190 E : "code"));
1191 : // Intersecting, overlapping the back.
1192 : EXPECT_EQ(NULL, address_space.AddBlock(BlockGraph::CODE_BLOCK,
1193 : RelativeAddress(0x1010),
1194 : 0x20,
1195 E : "code"));
1196 :
1197 : // We should be able to insert blocks above and below the one above.
1198 : EXPECT_TRUE(address_space.AddBlock(BlockGraph::CODE_BLOCK,
1199 : RelativeAddress(0xFF0),
1200 : 0x10,
1201 E : "code") != NULL);
1202 : EXPECT_TRUE(address_space.AddBlock(BlockGraph::CODE_BLOCK,
1203 : RelativeAddress(0x1020),
1204 : 0x10,
1205 E : "code") != NULL);
1206 :
1207 : // We should be able to add arbitrary many zero-sized blocks at any address.
1208 : EXPECT_TRUE(address_space.AddBlock(BlockGraph::CODE_BLOCK,
1209 : RelativeAddress(0x1020),
1210 : 0,
1211 E : "zerocode1") != NULL);
1212 : EXPECT_EQ(address_space.address_space_impl().size() + 1,
1213 E : address_space.block_addresses().size());
1214 : EXPECT_TRUE(address_space.AddBlock(BlockGraph::CODE_BLOCK,
1215 : RelativeAddress(0x1020),
1216 : 0,
1217 E : "zerocode2") != NULL);
1218 : EXPECT_EQ(address_space.address_space_impl().size() + 2,
1219 E : address_space.block_addresses().size());
1220 E : }
1221 :
1222 E : TEST(BlockGraphAddressSpaceTest, ResizeBlock) {
1223 E : BlockGraph image;
1224 E : BlockGraph::AddressSpace address_space(&image);
1225 E : EXPECT_EQ(0u, address_space.size());
1226 :
1227 : BlockGraph::Block* b1 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1228 : RelativeAddress(0x1000),
1229 : 0x20,
1230 E : "code");
1231 : BlockGraph::Block* b2 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1232 : RelativeAddress(0x1030),
1233 : 0x20,
1234 E : "code");
1235 E : EXPECT_EQ(2u, address_space.size());
1236 :
1237 E : const size_t kNewSizes[] = { 0x28, 0x32, 0x20, 0x20 };
1238 E : const size_t kExpectedSizes[] = { 0x28, 0x28, 0x20, 0x20 };
1239 : COMPILE_ASSERT(sizeof(kNewSizes) == sizeof(kExpectedSizes),
1240 : size_arrays_must_match);
1241 :
1242 : // Grow successfully first. Then grow, but expect failure. Then shrink.
1243 : // Finally, stay the same size.
1244 E : for (size_t i = 0; i < arraysize(kNewSizes); ++i) {
1245 E : bool expected_result = kNewSizes[i] == kExpectedSizes[i];
1246 E : EXPECT_EQ(expected_result, address_space.ResizeBlock(b1, kNewSizes[i]));
1247 :
1248 E : EXPECT_EQ(2u, address_space.size());
1249 E : EXPECT_TRUE(address_space.ContainsBlock(b1));
1250 E : EXPECT_TRUE(address_space.ContainsBlock(b2));
1251 E : EXPECT_EQ(kExpectedSizes[i], b1->size());
1252 : BlockGraph::AddressSpace::RangeMapConstIter block_it =
1253 : address_space.address_space_impl().FindContaining(
1254 E : BlockGraph::AddressSpace::Range(RelativeAddress(0x1000), 1));
1255 E : EXPECT_TRUE(block_it != address_space.address_space_impl().end());
1256 E : EXPECT_EQ(RelativeAddress(0x1000), block_it->first.start());
1257 E : EXPECT_EQ(kExpectedSizes[i], block_it->first.size());
1258 E : EXPECT_EQ(b1, block_it->second);
1259 E : }
1260 :
1261 : // Shrink to size zero. The block should be in the list of blocks by address,
1262 : // but not in the actual address space itself.
1263 E : EXPECT_TRUE(address_space.ResizeBlock(b1, 0));
1264 E : EXPECT_EQ(2u, address_space.size());
1265 E : EXPECT_EQ(1u, address_space.address_space_impl().size());
1266 E : EXPECT_TRUE(address_space.ContainsBlock(b1));
1267 E : EXPECT_TRUE(address_space.ContainsBlock(b2));
1268 E : EXPECT_EQ(0u, b1->size());
1269 : BlockGraph::AddressSpace::RangeMapConstIter block_it =
1270 : address_space.address_space_impl().FindContaining(
1271 E : BlockGraph::AddressSpace::Range(RelativeAddress(0x1000), 1));
1272 E : EXPECT_TRUE(block_it == address_space.address_space_impl().end());
1273 : BlockGraph::AddressSpace::BlockAddressMap::const_iterator addr_it =
1274 E : address_space.block_addresses().find(b1);
1275 E : EXPECT_TRUE(addr_it != address_space.block_addresses().end());
1276 E : EXPECT_EQ(RelativeAddress(0x1000), addr_it->second);
1277 :
1278 : // Finally, trying to resize a block that's not in the address space
1279 : // should fail.
1280 E : BlockGraph::Block* b3 = image.AddBlock(BlockGraph::CODE_BLOCK, 1, "c");
1281 E : EXPECT_FALSE(address_space.ResizeBlock(b3, 1));
1282 E : }
1283 :
1284 E : TEST(BlockGraphAddressSpaceTest, InsertBlock) {
1285 E : BlockGraph image;
1286 E : BlockGraph::AddressSpace address_space(&image);
1287 :
1288 : BlockGraph::Block* block1 =
1289 E : image.AddBlock(BlockGraph::CODE_BLOCK, 0x10, "code");
1290 : BlockGraph::Block* block2 =
1291 E : image.AddBlock(BlockGraph::CODE_BLOCK, 0x10, "code");
1292 : BlockGraph::Block* block3 =
1293 E : image.AddBlock(BlockGraph::CODE_BLOCK, 0x10, "code");
1294 : BlockGraph::Block* block4 =
1295 E : image.AddBlock(BlockGraph::CODE_BLOCK, 0, "code");
1296 :
1297 E : ASSERT_TRUE(address_space.InsertBlock(RelativeAddress(0x1000), block1));
1298 E : ASSERT_FALSE(address_space.InsertBlock(RelativeAddress(0x1000), block2));
1299 E : ASSERT_TRUE(address_space.InsertBlock(RelativeAddress(0x1010), block2));
1300 E : ASSERT_FALSE(address_space.InsertBlock(RelativeAddress(0x1018), block3));
1301 E : ASSERT_TRUE(address_space.InsertBlock(RelativeAddress(0x1030), block3));
1302 E : ASSERT_TRUE(address_space.InsertBlock(RelativeAddress(0x1030), block4));
1303 E : EXPECT_EQ(4u, address_space.size());
1304 E : EXPECT_EQ(3u, address_space.address_space_impl().size());
1305 :
1306 E : RelativeAddress addr;
1307 E : EXPECT_TRUE(address_space.GetAddressOf(block1, &addr));
1308 E : EXPECT_EQ(0x1000, addr.value());
1309 E : EXPECT_EQ(0x1000, block1->addr().value());
1310 :
1311 E : EXPECT_TRUE(address_space.GetAddressOf(block2, &addr));
1312 E : EXPECT_EQ(0x1010, addr.value());
1313 E : EXPECT_EQ(0x1010, block2->addr().value());
1314 :
1315 E : EXPECT_TRUE(address_space.GetAddressOf(block3, &addr));
1316 E : EXPECT_EQ(0x1030, addr.value());
1317 E : EXPECT_EQ(0x1030, block3->addr().value());
1318 :
1319 E : EXPECT_TRUE(address_space.GetAddressOf(block4, &addr));
1320 E : EXPECT_EQ(0x1030, addr.value());
1321 E : EXPECT_EQ(0x1030, block4->addr().value());
1322 :
1323 : // Insert a block into a second address space.
1324 E : BlockGraph::AddressSpace address_space2(&image);
1325 E : EXPECT_TRUE(address_space2.InsertBlock(RelativeAddress(0x2000), block1));
1326 E : EXPECT_TRUE(address_space.GetAddressOf(block1, &addr));
1327 E : EXPECT_EQ(0x1000, addr.value());
1328 :
1329 E : EXPECT_TRUE(address_space2.GetAddressOf(block1, &addr));
1330 E : EXPECT_EQ(0x2000, addr.value());
1331 :
1332 E : EXPECT_EQ(0x2000, block1->addr().value());
1333 E : }
1334 :
1335 E : TEST(BlockGraphAddressSpaceTest, GetBlockByAddress) {
1336 E : BlockGraph image;
1337 E : BlockGraph::AddressSpace address_space(&image);
1338 :
1339 : BlockGraph::Block* block1 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1340 : RelativeAddress(0x1000),
1341 : 0x10,
1342 E : "code");
1343 : BlockGraph::Block* block2 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1344 : RelativeAddress(0x1010),
1345 : 0x10,
1346 E : "code");
1347 : BlockGraph::Block* block3 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1348 : RelativeAddress(0x1030),
1349 : 0x10,
1350 E : "code");
1351 :
1352 E : EXPECT_EQ(NULL, address_space.GetBlockByAddress(RelativeAddress(0xFFF)));
1353 :
1354 E : EXPECT_EQ(block1, address_space.GetBlockByAddress(RelativeAddress(0x1000)));
1355 E : EXPECT_EQ(block1, address_space.GetBlockByAddress(RelativeAddress(0x100F)));
1356 :
1357 E : EXPECT_EQ(block2, address_space.GetBlockByAddress(RelativeAddress(0x1010)));
1358 E : EXPECT_EQ(block2, address_space.GetBlockByAddress(RelativeAddress(0x101F)));
1359 :
1360 E : EXPECT_EQ(NULL, address_space.GetBlockByAddress(RelativeAddress(0x1020)));
1361 E : EXPECT_EQ(NULL, address_space.GetBlockByAddress(RelativeAddress(0x102F)));
1362 :
1363 E : EXPECT_EQ(block3, address_space.GetBlockByAddress(RelativeAddress(0x1030)));
1364 E : EXPECT_EQ(block3, address_space.GetBlockByAddress(RelativeAddress(0x103F)));
1365 :
1366 E : EXPECT_EQ(NULL, address_space.GetBlockByAddress(RelativeAddress(0x1040)));
1367 E : }
1368 :
1369 E : TEST(BlockGraphAddressSpaceTest, GetFirstIntersectingBlock) {
1370 E : BlockGraph image;
1371 E : BlockGraph::AddressSpace address_space(&image);
1372 :
1373 : BlockGraph::Block* block1 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1374 : RelativeAddress(0x1000),
1375 : 0x10,
1376 E : "code");
1377 : BlockGraph::Block* block2 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1378 : RelativeAddress(0x1010),
1379 : 0x10,
1380 E : "code");
1381 : BlockGraph::Block* block3 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1382 : RelativeAddress(0x1030),
1383 : 0x10,
1384 E : "code");
1385 :
1386 : EXPECT_EQ(NULL,
1387 E : address_space.GetFirstIntersectingBlock(RelativeAddress(0xFFF), 0x1));
1388 : EXPECT_EQ(block1,
1389 E : address_space.GetFirstIntersectingBlock(RelativeAddress(0xFFF), 0x2));
1390 : EXPECT_EQ(block1,
1391 E : address_space.GetFirstIntersectingBlock(RelativeAddress(0x100F), 0x1));
1392 : EXPECT_EQ(block1,
1393 E : address_space.GetFirstIntersectingBlock(RelativeAddress(0x100F), 0x2));
1394 :
1395 : EXPECT_EQ(block2,
1396 E : address_space.GetFirstIntersectingBlock(RelativeAddress(0x1010), 0x40));
1397 E : }
1398 :
1399 E : TEST(BlockGraphAddressSpaceTest, GetContainingBlock) {
1400 E : BlockGraph image;
1401 E : BlockGraph::AddressSpace address_space(&image);
1402 :
1403 : BlockGraph::Block* block1 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1404 : RelativeAddress(0x1000),
1405 : 0x10,
1406 E : "code");
1407 : BlockGraph::Block* block2 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1408 : RelativeAddress(0x1010),
1409 : 0x10,
1410 E : "code");
1411 :
1412 : // Fully contained in block1
1413 : EXPECT_EQ(block1,
1414 E : address_space.GetContainingBlock(RelativeAddress(0x1004), 8));
1415 :
1416 : // Fully contained in block2
1417 : EXPECT_EQ(block2,
1418 E : address_space.GetContainingBlock(RelativeAddress(0x1014), 8));
1419 :
1420 : // Starts before but intersects with block1.
1421 E : EXPECT_EQ(NULL, address_space.GetContainingBlock(RelativeAddress(0x099E), 8));
1422 :
1423 : // Starts in the middle of block1 and overlaps into block2.
1424 E : EXPECT_EQ(NULL, address_space.GetContainingBlock(RelativeAddress(0x100a), 8));
1425 E : }
1426 :
1427 E : TEST(BlockGraphAddressSpaceTest, GetBlockAddress) {
1428 E : BlockGraph image;
1429 E : BlockGraph::AddressSpace address_space(&image);
1430 :
1431 : BlockGraph::Block* block1 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1432 : RelativeAddress(0x1000),
1433 : 0x10,
1434 E : "code");
1435 : BlockGraph::Block* block2 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1436 : RelativeAddress(0x1010),
1437 : 0x10,
1438 E : "code");
1439 : BlockGraph::Block* block3 =
1440 E : image.AddBlock(BlockGraph::CODE_BLOCK, 0x10, "code");
1441 :
1442 E : RelativeAddress addr;
1443 E : EXPECT_TRUE(address_space.GetAddressOf(block1, &addr));
1444 E : EXPECT_EQ(0x1000, addr.value());
1445 :
1446 E : EXPECT_TRUE(address_space.GetAddressOf(block2, &addr));
1447 E : EXPECT_EQ(0x1010, addr.value());
1448 :
1449 E : EXPECT_FALSE(address_space.GetAddressOf(block3, &addr));
1450 E : }
1451 :
1452 E : TEST(BlockGraphAddressSpaceTest, MergeIntersectingBlocks) {
1453 E : BlockGraph image;
1454 E : BlockGraph::AddressSpace address_space(&image);
1455 E : RelativeAddress addr1(0x1000);
1456 E : RelativeAddress addr2(0x1010);
1457 E : RelativeAddress addr3(0x1030);
1458 : BlockGraph::Block* block1 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1459 : addr1,
1460 : 0x10,
1461 E : "block1");
1462 : BlockGraph::Block* block2 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1463 : addr2,
1464 : 0x10,
1465 E : "block2");
1466 : BlockGraph::Block* block3 = address_space.AddBlock(BlockGraph::CODE_BLOCK,
1467 : addr3,
1468 : 0x10,
1469 E : "block3");
1470 E : ASSERT_TRUE(block2->SetLabel(0, "0x1010", BlockGraph::CODE_LABEL));
1471 E : ASSERT_TRUE(block2->SetLabel(4, "0x1014", BlockGraph::CODE_LABEL));
1472 E : ASSERT_TRUE(block3->SetLabel(0, "0x1030", BlockGraph::CODE_LABEL));
1473 E : ASSERT_TRUE(block3->SetLabel(4, "0x1034", BlockGraph::CODE_LABEL));
1474 :
1475 : block1->source_ranges().Push(BlockGraph::Block::DataRange(0, 0x10),
1476 E : BlockGraph::Block::SourceRange(addr1, 0x10));
1477 : block2->source_ranges().Push(BlockGraph::Block::DataRange(0, 0x10),
1478 E : BlockGraph::Block::SourceRange(addr2, 0x10));
1479 : block3->source_ranges().Push(BlockGraph::Block::DataRange(0, 0x10),
1480 E : BlockGraph::Block::SourceRange(addr3, 0x10));
1481 :
1482 : ASSERT_TRUE(block1->SetReference(0x1,
1483 E : BlockGraph::Reference(BlockGraph::ABSOLUTE_REF, 4, block2, 0x0, 0x0)));
1484 : ASSERT_TRUE(block1->SetReference(0x6,
1485 E : BlockGraph::Reference(BlockGraph::ABSOLUTE_REF, 4, block3, 0x0, 0x0)));
1486 : ASSERT_TRUE(block2->SetReference(0x1,
1487 E : BlockGraph::Reference(BlockGraph::PC_RELATIVE_REF, 1, block1, 0x4, 0x4)));
1488 : ASSERT_TRUE(block2->SetReference(0x6,
1489 E : BlockGraph::Reference(BlockGraph::PC_RELATIVE_REF, 4, block3, 0x4, 0x4)));
1490 : ASSERT_TRUE(block3->SetReference(0x1,
1491 E : BlockGraph::Reference(BlockGraph::PC_RELATIVE_REF, 4, block2, 0x4, 0x4)));
1492 :
1493 : // Set some attributes that should trivially propagate to the merged block.
1494 E : block2->set_attribute(BlockGraph::PE_PARSED);
1495 :
1496 : // Set an attribute that only propagates because it is present in both blocks.
1497 E : block2->set_attribute(BlockGraph::GAP_BLOCK);
1498 E : block3->set_attribute(BlockGraph::GAP_BLOCK);
1499 :
1500 : // Set an attribute that doesn't propagate because it is not present in both
1501 : // blocks.
1502 E : block2->set_attribute(BlockGraph::PADDING_BLOCK);
1503 :
1504 : // Blocks 2 and 3 will be merged.
1505 : BlockGraph::Block* merged = address_space.MergeIntersectingBlocks(
1506 E : BlockGraph::AddressSpace::Range(RelativeAddress(0x1014), 0x30));
1507 :
1508 E : ASSERT_TRUE(merged != NULL);
1509 E : ASSERT_EQ(RelativeAddress(0x1010), merged->addr());
1510 E : ASSERT_EQ(0x34, merged->size());
1511 :
1512 : // Expect the merged block to have meaningful source ranges.
1513 E : BlockGraph::Block::SourceRanges::RangePairs expected_source_ranges;
1514 : expected_source_ranges.push_back(
1515 : std::make_pair(BlockGraph::Block::DataRange(0, 0x10),
1516 E : BlockGraph::Block::SourceRange(addr2, 0x10)));
1517 : expected_source_ranges.push_back(
1518 : std::make_pair(BlockGraph::Block::DataRange(0x20, 0x10),
1519 E : BlockGraph::Block::SourceRange(addr3, 0x10)));
1520 : EXPECT_THAT(merged->source_ranges().range_pairs(),
1521 E : testing::ContainerEq(expected_source_ranges));
1522 :
1523 E : BlockGraph::Block::LabelMap expected_labels;
1524 : expected_labels.insert(std::make_pair(
1525 E : 0x00, BlockGraph::Label("0x1010", BlockGraph::CODE_LABEL)));
1526 : expected_labels.insert(std::make_pair(
1527 E : 0x04, BlockGraph::Label("0x1014", BlockGraph::CODE_LABEL)));
1528 : expected_labels.insert(std::make_pair(
1529 E : 0x20, BlockGraph::Label("0x1030", BlockGraph::CODE_LABEL)));
1530 : expected_labels.insert(std::make_pair(
1531 E : 0x24, BlockGraph::Label("0x1034", BlockGraph::CODE_LABEL)));
1532 E : EXPECT_THAT(merged->labels(), testing::ContainerEq(expected_labels));
1533 :
1534 E : BlockGraph::Block::ReferenceMap expected_refs;
1535 : expected_refs.insert(std::make_pair(0x1,
1536 E : BlockGraph::Reference(BlockGraph::PC_RELATIVE_REF, 1, block1, 0x4, 0x4)));
1537 : expected_refs.insert(std::make_pair(0x6,
1538 : BlockGraph::Reference(BlockGraph::PC_RELATIVE_REF, 4, merged, 0x24,
1539 E : 0x24)));
1540 : expected_refs.insert(std::make_pair(0x21,
1541 E : BlockGraph::Reference(BlockGraph::PC_RELATIVE_REF, 4, merged, 0x4, 0x4)));
1542 E : EXPECT_THAT(merged->references(), testing::ContainerEq(expected_refs));
1543 :
1544 E : expected_refs.clear();
1545 : expected_refs.insert(std::make_pair(0x1,
1546 E : BlockGraph::Reference(BlockGraph::ABSOLUTE_REF, 4, merged, 0x0, 0x0)));
1547 : expected_refs.insert(std::make_pair(0x6,
1548 E : BlockGraph::Reference(BlockGraph::ABSOLUTE_REF, 4, merged, 0x20, 0x20)));
1549 E : EXPECT_THAT(block1->references(), testing::ContainerEq(expected_refs));
1550 :
1551 : // Expect the attributes to have been propagated properly.
1552 : EXPECT_EQ(BlockGraph::PE_PARSED | BlockGraph::GAP_BLOCK,
1553 E : merged->attributes());
1554 :
1555 : // We expect that the block graph and the address space have the same size,
1556 : // as MergeIntersectingBlocks deletes the old blocks from the BlockGraph.
1557 E : EXPECT_EQ(image.blocks().size(), address_space.address_space_impl().size());
1558 E : }
1559 :
1560 E : TEST(BlockGraphAddressSpaceTest, ContainsBlock) {
1561 E : BlockGraph image;
1562 E : BlockGraph::AddressSpace address_space(&image);
1563 : BlockGraph::Block* block =
1564 E : image.AddBlock(BlockGraph::CODE_BLOCK, 0x10, "code");
1565 :
1566 E : ASSERT_FALSE(address_space.ContainsBlock(block));
1567 E : EXPECT_TRUE(address_space.InsertBlock(RelativeAddress(0x1000), block));
1568 E : ASSERT_TRUE(address_space.ContainsBlock(block));
1569 E : }
1570 :
1571 : } // namespace block_graph
|