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 : // Unittests for BlockGraph::Orderers::OriginalOrderer.
16 :
17 : #include "syzygy/block_graph/orderers/original_orderer.h"
18 :
19 : #include <algorithm>
20 :
21 : #include "base/strings/stringprintf.h"
22 : #include "gmock/gmock.h"
23 : #include "gtest/gtest.h"
24 : #include "syzygy/block_graph/unittest_util.h"
25 :
26 : namespace block_graph {
27 : namespace orderers {
28 :
29 : namespace {
30 :
31 : using testing::Pointwise;
32 :
33 : // Declares a tuple matcher that gets the section() property of the first
34 : // value, and compares it to the second value. It would be nice to do
35 : // this with Pointwise(Property(§ion, Eq())), but Property can't
36 : // handle tuple matchers.
37 : MATCHER(SectionEq, std::string("has section() ") +
38 E : std::string(negation ? "not " : "") + std::string("equal to")) {
39 E : return ::std::tr1::get<0>(arg)->section() == ::std::tr1::get<1>(arg);
40 E : }
41 :
42 : // Adds a block to the given block-graph with the provided properties.
43 : BlockGraph::Block* AddBlock(BlockGraph* bg,
44 : BlockGraph::Section* section,
45 : size_t number,
46 : size_t src_addr,
47 E : bool initialized) {
48 E : DCHECK(bg != NULL);
49 E : DCHECK(section != NULL);
50 :
51 E : std::string name = base::StringPrintf("block%d", number);
52 : BlockGraph::Block* block = bg->AddBlock(
53 E : BlockGraph::DATA_BLOCK, 10, name);
54 E : DCHECK(block != NULL);
55 :
56 E : if (src_addr != 0)
57 : block->source_ranges().Push(
58 : BlockGraph::Block::DataRange(0, block->size()),
59 : BlockGraph::Block::SourceRange(BlockGraph::RelativeAddress(src_addr),
60 E : block->size()));
61 :
62 E : block->set_section(section->id());
63 E : if (initialized) {
64 E : uint8* data = block->AllocateData(block->size());
65 : // Make some non-zero data so that this block can not be implicitly
66 : // initialized.
67 E : data[0] = 1;
68 : }
69 :
70 E : return block;
71 E : }
72 :
73 : } // namespace
74 :
75 E : TEST(OriginalOrdererTest, OrderIsAsExpected) {
76 E : BlockGraph bg;
77 E : BlockGraph::Section* section1 = bg.AddSection("section1", 0);
78 E : BlockGraph::Section* section2 = bg.AddSection("section2", 0);
79 E : BlockGraph::Section* section3 = bg.AddSection("section3", 0);
80 :
81 : // Blocks 2 and 3 have the same source range but 3 is not initialized,
82 : // testing criteria 1.
83 : // Blocks 1-3 have source range data, block 4-5 do not. This tests criteria 2.
84 : // Blocks 1 and 2 have differing source ranges, testing criteria 3.
85 : // Blocks 4 and 5 are identical except block 5 has a higher block ID, testing
86 : // criteria 4.
87 :
88 : // These blocks are scrambled so that ordering them by ID is not correct.
89 E : BlockGraph::Block* block1 = AddBlock(&bg, section1, 3, 30, false);
90 E : BlockGraph::Block* block2 = AddBlock(&bg, section1, 2, 30, true);
91 E : BlockGraph::Block* block3 = AddBlock(&bg, section1, 4, 0, false);
92 E : BlockGraph::Block* block4 = AddBlock(&bg, section1, 1, 10, true);
93 :
94 : // Needs to be created last so that the ID is the greatest.
95 E : BlockGraph::Block* block5 = AddBlock(&bg, section1, 5, 0, false);
96 :
97 E : OrderedBlockGraph obg(&bg);
98 :
99 : // Shuffle the sections.
100 E : std::vector<BlockGraph::Section*> sections, shuffled_sections;
101 E : sections.push_back(section1);
102 E : sections.push_back(section2);
103 E : sections.push_back(section3);
104 E : shuffled_sections = sections;
105 E : std::random_shuffle(shuffled_sections.begin(), shuffled_sections.end());
106 E : for (size_t i = 0; i < shuffled_sections.size(); ++i)
107 E : obg.PlaceAtTail(shuffled_sections[i]);
108 :
109 : // Shuffle the blocks in section1.
110 E : BlockVector blocks, shuffled_blocks;
111 E : blocks.push_back(block4);
112 E : blocks.push_back(block2);
113 E : blocks.push_back(block1);
114 E : blocks.push_back(block3);
115 E : blocks.push_back(block5);
116 E : shuffled_blocks = blocks;
117 E : std::random_shuffle(shuffled_blocks.begin(), shuffled_blocks.end());
118 E : for (size_t i = 0; i < shuffled_blocks.size(); ++i)
119 E : obg.PlaceAtTail(section1, shuffled_blocks[i]);
120 :
121 : // Run the default orderer.
122 E : OriginalOrderer orderer;
123 E : EXPECT_TRUE(orderer.OrderBlockGraph(&obg, block1));
124 :
125 : EXPECT_THAT(obg.ordered_sections(),
126 E : Pointwise(SectionEq(), sections));
127 :
128 : EXPECT_THAT(obg.ordered_section(section1).ordered_blocks(),
129 E : Pointwise(testing::Eq(), blocks));
130 E : }
131 :
132 : } // namespace orderers
133 : } // namespace block_graph
|