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