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/reorder/linear_order_generator.h"
16 :
17 : #include <algorithm>
18 :
19 : namespace reorder {
20 :
21 : namespace {
22 :
23 : // This is effectively arbitrarily chosen for now. Higher is better from
24 : // benchmarked reorderings. This value is effectively 'infinite' as far as the
25 : // chrome data goes.
26 : const size_t kDataRecursionDepth = 100;
27 :
28 : typedef LinearOrderGenerator::BlockCall BlockCall;
29 :
30 : // Comparator for sorting BlockCalls by increasing time.
31 : struct BlockCallSortIncrTime {
32 E : bool operator()(const BlockCall& bc1, const BlockCall& bc2) {
33 E : return bc1.time < bc2.time;
34 E : }
35 : };
36 :
37 : // Used for aggregating block call information across multiple runs.
38 : struct AverageBlockCall {
39 : const block_graph::BlockGraph::Block* block;
40 : size_t sum_order;
41 : // The number of runs of the instrumented binary in which this block was
42 : // seen, NOT the number of times it was seen called in aggregate.
43 : size_t call_count;
44 : // This is only meaningful if call_count == 1.
45 : uint32 process_group_id;
46 :
47 E : double AverageOrder() const {
48 E : DCHECK_LT(0U, call_count);
49 E : return static_cast<double>(sum_order) / call_count;
50 E : }
51 : };
52 :
53 : // Sorts by decreasing call count. Anything with more than one call count
54 : // is sorted with a secondary key of increasing order. Anything with a single
55 : // call count has a secondary key of process_group_id, and a tertiary key of
56 : // increasing order.
57 : struct AverageBlockCallSort {
58 E : bool operator()(const AverageBlockCall& abc1, const AverageBlockCall& abc2) {
59 E : if (abc1.call_count != abc2.call_count)
60 E : return abc1.call_count > abc2.call_count;
61 :
62 E : if (abc1.call_count > 1 || abc1.process_group_id == abc2.process_group_id)
63 E : return abc1.AverageOrder() < abc2.AverageOrder();
64 :
65 E : return abc1.process_group_id < abc2.process_group_id;
66 E : }
67 : };
68 :
69 : // Extract the values of a map to a vector.
70 : template<typename K, typename V> void MapToVector(const std::map<K, V>& map,
71 E : std::vector<V>* vector) {
72 E : DCHECK(vector != NULL);
73 :
74 E : vector->clear();
75 E : std::map<K, V>::const_iterator it = map.begin();
76 E : for (; it != map.end(); ++it)
77 E : vector->push_back(it->second);
78 E : }
79 :
80 : } // namespace
81 :
82 : LinearOrderGenerator::LinearOrderGenerator()
83 : : Reorderer::OrderGenerator("Linear Order Generator"),
84 : active_process_count_(0),
85 E : next_process_group_id_(0) {
86 E : }
87 :
88 E : LinearOrderGenerator::~LinearOrderGenerator() {
89 E : }
90 :
91 : bool LinearOrderGenerator::OnProcessStarted(uint32 process_id,
92 E : const UniqueTime& time) {
93 E : if (active_process_count_ == 0) {
94 E : if (!CloseProcessGroup())
95 i : return false;
96 : }
97 :
98 E : ++active_process_count_;
99 :
100 E : return true;
101 E : }
102 :
103 : bool LinearOrderGenerator::OnProcessEnded(uint32 process_id,
104 E : const UniqueTime& time) {
105 E : DCHECK_LT(0U, active_process_count_);
106 E : --active_process_count_;
107 E : return true;
108 E : }
109 :
110 : bool LinearOrderGenerator::OnCodeBlockEntry(const BlockGraph::Block* block,
111 : RelativeAddress address,
112 : uint32 process_id,
113 : uint32 thread_id,
114 E : const UniqueTime& time) {
115 E : return TouchBlock(BlockCall(block, process_id, thread_id, time));
116 E : }
117 :
118 : bool LinearOrderGenerator::CalculateReordering(const PEFile& pe_file,
119 : const ImageLayout& image,
120 : bool reorder_code,
121 : bool reorder_data,
122 E : Order* order) {
123 E : DCHECK(order != NULL);
124 :
125 : // Ensure the last running process group is closed.
126 E : if (!CloseProcessGroup())
127 i : return false;
128 :
129 E : LOG(INFO) << "Encountered " << process_group_calls_.size()
130 : << " process groups.";
131 :
132 : // Aggregate the block calls.
133 E : std::map<const BlockGraph::Block*, AverageBlockCall> average_block_call_map;
134 E : ProcessGroupBlockCalls::const_iterator it = process_group_calls_.begin();
135 E : for (; it != process_group_calls_.end(); ++it) {
136 E : for (size_t i = 0; i < it->second.size(); ++i) {
137 E : const BlockCall& block_call = it->second[i];
138 : AverageBlockCall& average_block_call =
139 E : average_block_call_map[block_call.block];
140 E : average_block_call.block = block_call.block;
141 E : average_block_call.sum_order += i;
142 E : ++average_block_call.call_count;
143 E : average_block_call.process_group_id = it->first;
144 E : }
145 E : }
146 :
147 : // Now create a sorted list.
148 E : std::vector<AverageBlockCall> average_block_calls;
149 E : MapToVector(average_block_call_map, &average_block_calls);
150 E : average_block_call_map.clear();
151 : std::sort(average_block_calls.begin(), average_block_calls.end(),
152 E : AverageBlockCallSort());
153 :
154 : // TODO(chrisha): Create an option to evenly distribute the common startup
155 : // blocks (those with call_count == process_group_calls_.size()) among
156 : // the remaining blocks.
157 :
158 : // Initialize the section list and ordering meta data.
159 E : order->comment = "Linear ordering by earliest appearance";
160 E : order->sections.clear();
161 E : order->sections.resize(image.sections.size());
162 E : for (size_t i = 0; i < image.sections.size(); ++i) {
163 E : order->sections[i].id = i;
164 E : order->sections[i].name = image.sections[i].name;
165 E : order->sections[i].characteristics = image.sections[i].characteristics;
166 E : }
167 :
168 : // Create the ordering from this list.
169 E : BlockSet inserted_blocks;
170 E : for (size_t i = 0; i < average_block_calls.size(); ++i) {
171 E : const BlockGraph::Block* code_block = average_block_calls[i].block;
172 :
173 E : if (reorder_code) {
174 : order->sections[code_block->section()].blocks.push_back(
175 E : Order::BlockSpec(code_block));
176 E : inserted_blocks.insert(code_block);
177 : }
178 :
179 : // Create an analogous data ordering if we were asked to.
180 E : if (reorder_data) {
181 : if (!InsertDataBlocks(kDataRecursionDepth, code_block, order,
182 E : &inserted_blocks))
183 i : return false;
184 : }
185 E : }
186 :
187 : // Add the remaining blocks in each section to the order.
188 E : for (size_t section_index = 0; ; ++section_index) {
189 : const IMAGE_SECTION_HEADER* section =
190 E : pe_file.section_header(section_index);
191 E : if (section == NULL)
192 E : break;
193 :
194 E : RelativeAddress section_start = RelativeAddress(section->VirtualAddress);
195 : AddressSpace::RangeMapConstIterPair section_blocks =
196 : image.blocks.GetIntersectingBlocks(
197 E : section_start, section->Misc.VirtualSize);
198 E : AddressSpace::RangeMapConstIter& section_it = section_blocks.first;
199 E : const AddressSpace::RangeMapConstIter& section_end = section_blocks.second;
200 E : for (; section_it != section_end; ++section_it) {
201 E : BlockGraph::Block* block = section_it->second;
202 E : if (inserted_blocks.count(block) > 0)
203 E : continue;
204 E : order->sections[section_index].blocks.push_back(Order::BlockSpec(block));
205 E : }
206 E : }
207 :
208 E : return true;
209 E : }
210 :
211 E : bool LinearOrderGenerator::TouchBlock(const BlockCall& block_call) {
212 E : DCHECK(block_call.block != NULL);
213 : // All code blocks should belong to a defined section.
214 E : DCHECK_NE(pe::kInvalidSection, block_call.block->section());
215 :
216 : // Store the block along with the earliest time it was called.
217 E : BlockCallMap::iterator it = block_call_map_.find(block_call.block);
218 E : if (it == block_call_map_.end()) {
219 E : std::pair<BlockCallMap::iterator, bool> insert_return;
220 : insert_return = block_call_map_.insert(
221 E : std::make_pair(block_call.block, block_call));
222 E : it = insert_return.first;
223 E : DCHECK(insert_return.second);
224 E : DCHECK(it != block_call_map_.end());
225 E : } else {
226 : // Keep around the earliest call to this block only.
227 E : if (block_call.time < it->second.time)
228 i : it->second = block_call;
229 : }
230 E : return true;
231 E : }
232 :
233 : bool LinearOrderGenerator::InsertDataBlocks(size_t max_recursion_depth,
234 : const BlockGraph::Block* block,
235 : Order* order,
236 E : BlockSet* inserted_blocks) {
237 E : DCHECK(block != NULL);
238 E : DCHECK(order != NULL);
239 :
240 : // Stop the recursion.
241 E : if (max_recursion_depth == 0)
242 i : return true;
243 :
244 E : block_graph::ConstBlockVector data_blocks;
245 :
246 : // Iterate through any data blocks that are referenced by this
247 : // block, and also store them with the same time. This is a pessimistic
248 : // optimization, and assumes that all data linked to a code block will
249 : // be touched by that code block (and all data linked to by that data block,
250 : // and so on, up to 'max_recursion_depth').
251 : BlockGraph::Block::ReferenceMap::const_iterator ref_it =
252 E : block->references().begin();
253 E : for (; ref_it != block->references().end(); ++ref_it) {
254 E : const BlockGraph::Block* ref = ref_it->second.referenced();
255 E : DCHECK(ref != NULL);
256 : // We only touch data blocks with a valid section id.
257 : if (ref->type() != BlockGraph::DATA_BLOCK ||
258 E : ref->section() == pe::kInvalidSection)
259 E : continue;
260 :
261 : // Only insert data blocks that have not yet been seen.
262 E : if (!inserted_blocks->insert(ref).second)
263 E : continue;
264 :
265 : // Finally, insert this block to the appropriate section ordering.
266 E : order->sections[ref->section()].blocks.push_back(Order::BlockSpec(ref));
267 :
268 E : data_blocks.push_back(ref);
269 E : }
270 :
271 : // Recurse on the data blocks we just added.
272 E : if (max_recursion_depth > 1) {
273 E : for (size_t i = 0; i < data_blocks.size(); ++i) {
274 : if (!InsertDataBlocks(max_recursion_depth - 1, data_blocks[i], order,
275 E : inserted_blocks))
276 i : return false;
277 E : }
278 : }
279 :
280 E : return true;
281 E : }
282 :
283 E : bool LinearOrderGenerator::CloseProcessGroup() {
284 E : if (block_call_map_.empty())
285 E : return true;
286 :
287 E : BlockCalls& block_calls = process_group_calls_[next_process_group_id_];
288 E : ++next_process_group_id_;
289 :
290 E : MapToVector(block_call_map_, &block_calls);
291 E : block_call_map_.clear();
292 :
293 E : std::sort(block_calls.begin(), block_calls.end(), BlockCallSortIncrTime());
294 :
295 E : return true;
296 E : }
297 :
298 : } // namespace reorder
|