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 : // Declares a data structure that can be used to impose an order on a block
16 : // graph. This is an 'elastic' data structure in that its intent is to make
17 : // reordering blocks cheap and efficient. It is to be used as an intermediate
18 : // representation prior to image-format-specific layout generation.
19 : //
20 : // The structure maintains all sections in a list, and for each section
21 : // maintains a list of blocks within that section. Utility functions are
22 : // provided that allow for sections and blocks to be moved individually, or for
23 : // all sections/all blocks in a section to be sorted wholesale.
24 : //
25 : // In general, it is intended to be used as follows:
26 : //
27 : // OrderedBlockGraph ordered(some_block_graph);
28 : //
29 : // // Ensure that .rsrc and .reloc are the last two sections.
30 : // ordered.PlaceAtTail(some_block_graph->FindSection(".rsrc"));
31 : // ordered.PlaceAtTail(some_block_graph->FindSection(".reloc"));
32 : //
33 : // // Make sure that .text comes first.
34 : // ordered.PlaceAtHead(some_block_graph->FindSection(".text"));
35 : //
36 : // // Sort the text blocks according to some functor.
37 : // ordered.Sort(some_block_graph->FindSection(".text"),
38 : // some_sort_functor);
39 : //
40 : // ... etc ...
41 : //
42 : // // Dump the contents of the ordered block-graph.
43 : // OrderedBlockGraph::SectionList::const_iterator section_it =
44 : // ordered.begin();
45 : // for (; section_it != ordered.end(); ++section_it) {
46 : // const BlockGraph::Section* section = *section_it;
47 : // ... do something with section ...
48 : // OrderedBlockGraph::BlockList::const_iterator block_it =
49 : // ordered.begin(section);
50 : // for (; block_it != ordered.end(section); ++block_it) {
51 : // const BlockGraph::Block* block = *block_it;
52 : // ... do something with block ...
53 : // }
54 : // }
55 :
56 : #ifndef SYZYGY_BLOCK_GRAPH_ORDERED_BLOCK_GRAPH_H_
57 : #define SYZYGY_BLOCK_GRAPH_ORDERED_BLOCK_GRAPH_H_
58 :
59 : #include <list>
60 : #include <vector>
61 :
62 : #include "syzygy/block_graph/block_graph.h"
63 :
64 : namespace block_graph {
65 :
66 : // An ordered block-graph is a thin layer on top of a BlockGraph that imposes
67 : // a complete ordering on it. A few notes on working with OrderedBlockGraphs:
68 : //
69 : // - A BlockGraph is only intended to be used by a single OrderedBlockGraph at a
70 : // time as the OrderedBlockGraph makes changes to the underlying BlockGraph to
71 : // ensure consistency.
72 : // - It is invalid to add or delete blocks from a BlockGraph while it is being
73 : // referenced by an OrderedBlockGraph. This can cause NULL dereferences.
74 : class OrderedBlockGraph {
75 : public:
76 : class OrderedSection;
77 :
78 : // For convenience.
79 : typedef BlockGraph::Block Block;
80 : typedef BlockGraph::Section Section;
81 :
82 : // The type of the ordered list of blocks that is maintained for each section.
83 : typedef std::list<Block*> BlockList;
84 : // The type of the ordered list of sections that is maintained for the whole
85 : // block graph.
86 : typedef std::list<OrderedSection*> SectionList;
87 :
88 : // Constructs an OrderedBlockGraph over the provided BlockGraph. The sections
89 : // are initially ordered by increasing ID, with a special section (not ordered
90 : // in the list of sections) housing all of the blocks that are not associated
91 : // a particular section (section_id == kInvalidSectionId). Within each section
92 : // the blocks are initially ordered by increasing block ID.
93 : //
94 : // @param block_graph the BlockGraph to be ordered. This must outlive the
95 : // OrderedBlockGraph.
96 : explicit OrderedBlockGraph(BlockGraph* block_graph);
97 :
98 : // @{
99 : // Accesses the BlockGraph that we are ordering.
100 : // @returns a pointer to underlying BlockGraph.
101 E : BlockGraph* block_graph() { return block_graph_; }
102 E : const BlockGraph* block_graph() const { return block_graph_; }
103 : // @}
104 :
105 : // @returns the ordered list of sections. May be used for traversing the
106 : // order.
107 E : const SectionList& ordered_sections() const { return ordered_sections_; }
108 :
109 : // Looks up an ordered section.
110 : //
111 : // @param section the section to lookup. This may be NULL to get a list of the
112 : // blocks that are not in any explicit section.
113 : // @returns the ordered section for the given section.
114 : const OrderedSection& ordered_section(const Section* section) const;
115 :
116 : // @{
117 : // Iterator access for SectionList.
118 : SectionList::const_iterator begin() const {
119 : return ordered_sections_.begin();
120 : }
121 : SectionList::const_iterator end() const { return ordered_sections_.end(); }
122 : // @}
123 :
124 : // @{
125 : // Iterator access for BlockLists.
126 : // @param section the section to whose BlockList is to be returned. This may
127 : // be NULL to iterate over those blocks not in any explicit section.
128 : BlockList::const_iterator begin(const Section* section) const;
129 : BlockList::const_iterator end(const Section* section) const;
130 : // @}
131 :
132 : // Moves the given section to the head of the list of sections.
133 : //
134 : // @param section the section to be moved to the head.
135 : void PlaceAtHead(const Section* section);
136 :
137 : // Moves the given section to the tail of the list of sections.
138 : //
139 : // @param section the section to be moved to the tail.
140 : void PlaceAtTail(const Section* section);
141 :
142 : // Moves a section immediately before another section.
143 : //
144 : // @param anchored_section the section to be used as a reference.
145 : // @param moved_section the section to be moved.
146 : // @pre anchored_section != moved_section.
147 : void PlaceBefore(const Section* anchored_section,
148 : const Section* moved_section);
149 :
150 : // Moves a section immediately after another section.
151 : //
152 : // @param anchored_section the section to be used as a reference.
153 : // @param moved_section the section to be moved.
154 : // @pre anchored_section != moved_section.
155 : void PlaceAfter(const Section* anchored_section,
156 : const Section* moved_section);
157 :
158 : // Allows for a direct sorting of all sections using a provided comparison
159 : // functor. The comparison functor must have a function with the following
160 : // signature:
161 : //
162 : // bool operator()(const BlockGraph::Section*,
163 : // const BlockGraph::Section*) const;
164 : //
165 : // @param section_compare_functor the compare functor to use.
166 : template<typename SectionCompareFunctor>
167 : void Sort(SectionCompareFunctor section_compare_functor);
168 :
169 : // Moves the given block to the head of the given section. If the block does
170 : // not belong to that section it will have its section_id updated.
171 : //
172 : // @param section the section into which the block should be placed. May be
173 : // NULL, indicating that the block lies outside of all known sections.
174 : // @param block the block to be moved.
175 : void PlaceAtHead(const Section* section, Block* block);
176 :
177 : // Moves the given block to the tail of the given section. If the block does
178 : // not belong to that section it will have its section_id updated.
179 : //
180 : // @param section the section into which the block should be placed. May be
181 : // NULL, indicating that the block lies outside of all known sections.
182 : // @param block the block to be moved.
183 : void PlaceAtTail(const Section* section, Block* block);
184 :
185 : // Moves @p moved_block so that it lies immediately before @p anchored_block.
186 : // If @p moved_block does not belong to the same section it will have its
187 : // section attribute updated.
188 : //
189 : // @param anchored_block the block to be used as a reference point.
190 : // @param moved_block the block to be moved.
191 : // @pre anchored_block != moved_block.
192 : void PlaceBefore(const Block* anchored_block, Block* moved_block);
193 :
194 : // Moves @p moved_block so that it lies immediately after @p anchored_block.
195 : // If @p moved_block does not belong to the same section it will have its
196 : // section attribute updated.
197 : //
198 : // @param anchored_block the block to be used as a reference point.
199 : // @param moved_block the block to be moved.
200 : // @pre anchored_block != moved_block.
201 : void PlaceAfter(const Block* anchored_block, Block* moved_block);
202 :
203 : // Allows for a direct sorting of the blocks in a section using the provided
204 : // comparison functor. The comparison functor must have a function with the
205 : // following signature:
206 : //
207 : // bool operator()(const BlockGraph::Block*,
208 : // const BlockGraph::Block*) const;
209 : //
210 : // @param block_compare_functor the compare functor to use.
211 : template<typename BlockCompareFunctor>
212 : void Sort(const Section* section, BlockCompareFunctor block_compare_functor);
213 :
214 : protected:
215 : // Forward declarations.
216 : struct SectionInfo;
217 : struct BlockInfo;
218 : struct CompareSectionInfo;
219 : struct CompareBlockInfo;
220 :
221 : // @{
222 : // @returns the SectionInfo representing the given Section*.
223 : const SectionInfo* GetSectionInfo(const Section* section) const;
224 : SectionInfo* GetSectionInfo(const Section* section);
225 : // @}
226 :
227 : // @{
228 : // @returns the BlockInfo representing the given Block*.
229 : const BlockInfo* GetBlockInfo(const Block* block) const;
230 : BlockInfo* GetBlockInfo(const Block* block);
231 : // @}
232 :
233 : // Rebuilds the section iterator index.
234 : void RebuildSectionIndex();
235 :
236 : // The block graph on which we impose an order.
237 : BlockGraph* block_graph_;
238 :
239 : // Stores the ordered list of sections.
240 : SectionList ordered_sections_;
241 : // Stores the ordered sections themselves. This is sorted based on the
242 : // underlying Section* so that we can quickly map from a Section* to the
243 : // OrderedSection and its entry in the SectionList.
244 : std::vector<SectionInfo> section_infos_;
245 : // Stores a full set of iterators pointing to all of the blocks in the various
246 : // OrderedSection BlockLists. This is allocated once and reused. The entries
247 : // are sorted based on the block pointers referred to by the iterators. In
248 : // this way we can do a fast lookup from Block* to the BlockList containing
249 : // it, as well as the iterator to it.
250 : std::vector<BlockInfo> block_infos_;
251 :
252 : DISALLOW_COPY_AND_ASSIGN(OrderedBlockGraph);
253 : };
254 :
255 : // The ordered block graph consists of an ordered list of sections. Each
256 : // section is itself an ordered list of blocks. This object is exposed to the
257 : // user, hence the private data members. OrderedBlockGraph is made a friend
258 : // so as to be able to manage it directly.
259 : class OrderedBlockGraph::OrderedSection {
260 : public:
261 : // @returns the section represented by this ordered section.
262 E : Section* section() const { return section_; }
263 :
264 : // @returns the id associated with this section.
265 : BlockGraph::SectionId id() const;
266 :
267 : // @returns the ordered list of blocks belonging to this section.
268 E : const BlockList& ordered_blocks() const { return ordered_blocks_; }
269 :
270 : private:
271 : friend OrderedBlockGraph;
272 :
273 : // The section itself.
274 : Section* section_;
275 : // The blocks belonging to this section, in order.
276 : BlockList ordered_blocks_;
277 : };
278 :
279 : } // namespace block_graph
280 :
281 : #include "syzygy/block_graph/ordered_block_graph_internal.h"
282 :
283 : #endif // SYZYGY_BLOCK_GRAPH_ORDERED_BLOCK_GRAPH_H_
|