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 : // Implements utility functions useful to grinders that process basic-block
16 : // frequency data.
17 :
18 : #include "syzygy/grinder/basic_block_util.h"
19 :
20 : #include <algorithm>
21 : #include <functional>
22 :
23 : #include "syzygy/common/indexed_frequency_data.h"
24 : #include "syzygy/grinder/indexed_frequency_data_serializer.h"
25 : #include "syzygy/pdb/pdb_reader.h"
26 : #include "syzygy/pdb/pdb_util.h"
27 : #include "syzygy/pe/find.h"
28 :
29 : namespace grinder {
30 : namespace basic_block_util {
31 :
32 : bool ModuleIdentityComparator::operator()(
33 E : const ModuleInformation& lhs, const ModuleInformation& rhs) {
34 E : if (lhs.module_size < rhs.module_size)
35 E : return true;
36 E : if (lhs.module_size > rhs.module_size)
37 E : return false;
38 :
39 E : if (lhs.time_date_stamp < rhs.time_date_stamp)
40 E : return true;
41 E : if (lhs.time_date_stamp > rhs.time_date_stamp)
42 E : return false;
43 :
44 E : return lhs.image_file_name < rhs.image_file_name;
45 E : }
46 :
47 : bool operator==(const IndexedFrequencyInformation& lhs,
48 E : const IndexedFrequencyInformation& rhs) {
49 : return lhs.num_entries == rhs.num_entries &&
50 : lhs.num_columns == rhs.num_columns &&
51 : lhs.data_type == rhs.data_type &&
52 E : lhs.frequency_map == rhs.frequency_map;
53 E : }
54 :
55 : void InitModuleInfo(const pe::PEFile::Signature& signature,
56 E : ModuleInformation* module_info) {
57 E : DCHECK(module_info != NULL);
58 E : module_info->base_address = signature.base_address.value();
59 E : module_info->image_checksum = signature.module_checksum;
60 E : module_info->image_file_name = signature.path;
61 E : module_info->module_size = signature.module_size;
62 E : module_info->time_date_stamp = signature.module_time_date_stamp;
63 E : }
64 :
65 : bool FindIndexedFrequencyInfo(
66 : const pe::PEFile::Signature& signature,
67 : const ModuleIndexedFrequencyMap& module_entry_map,
68 E : const IndexedFrequencyInformation** information) {
69 E : DCHECK(information != NULL);
70 E : *information = NULL;
71 :
72 : // Find exactly one consistent entry count vector in the map.
73 E : const IndexedFrequencyInformation* result = NULL;
74 E : ModuleIndexedFrequencyMap::const_iterator it = module_entry_map.begin();
75 E : for (; it != module_entry_map.end(); ++it) {
76 E : const pe::PEFile::Signature candidate(it->first);
77 E : if (candidate.IsConsistent(signature)) {
78 E : if (result != NULL) {
79 E : LOG(ERROR) << "Found multiple module instances in the "
80 : << "indexed frequency map.";
81 E : return false;
82 : }
83 E : result = &it->second;
84 : }
85 E : }
86 :
87 : // Handle the case where there is no consistent module found.
88 E : if (result == NULL) {
89 E : LOG(ERROR) << "Did not find module in the entry count map.";
90 E : return false;
91 : }
92 :
93 : // Return the entry counts that were found.
94 E : *information = result;
95 E : return true;
96 E : }
97 :
98 : bool LoadBranchStatisticsFromFile(const base::FilePath& file,
99 : const pe::PEFile::Signature& signature,
100 E : IndexedFrequencyMap* frequencies) {
101 E : DCHECK(!file.empty());
102 E : DCHECK_NE(reinterpret_cast<IndexedFrequencyMap*>(NULL), frequencies);
103 :
104 : // Load profile information from JSON file.
105 E : ModuleIndexedFrequencyMap module_entry_count_map;
106 E : IndexedFrequencyDataSerializer serializer;
107 E : if (!serializer.LoadFromJson(file, &module_entry_count_map)) {
108 E : LOG(ERROR) << "Failed to load profile information.";
109 E : return false;
110 : }
111 :
112 : // Retrieve the module with the right signature.
113 E : const IndexedFrequencyInformation* branch_statistics = NULL;
114 : if (!FindIndexedFrequencyInfo(signature,
115 : module_entry_count_map,
116 E : &branch_statistics)) {
117 E : LOG(ERROR) << "Failed to find module for '"
118 : << signature.path << "'.";
119 E : return false;
120 : }
121 : DCHECK_NE(reinterpret_cast<const IndexedFrequencyInformation*>(NULL),
122 E : branch_statistics);
123 :
124 : // Validate that the data is in the expected format.
125 E : DCHECK_EQ(3U, branch_statistics->num_columns);
126 E : DCHECK_EQ(common::IndexedFrequencyData::BRANCH, branch_statistics->data_type);
127 E : DCHECK_EQ(4U, branch_statistics->frequency_size);
128 :
129 E : *frequencies = branch_statistics->frequency_map;
130 E : return true;
131 E : }
132 :
133 : bool LoadBasicBlockRanges(const base::FilePath& pdb_path,
134 E : RelativeAddressRangeVector* bb_ranges) {
135 E : DCHECK(!pdb_path.empty());
136 E : DCHECK(bb_ranges != NULL);
137 :
138 : // Read the PDB file.
139 E : pdb::PdbReader pdb_reader;
140 E : pdb::PdbFile pdb_file;
141 E : if (!pdb_reader.Read(pdb_path, &pdb_file)) {
142 E : LOG(ERROR) << "Failed to read PDB: " << pdb_path.value();
143 E : return false;
144 : }
145 :
146 : // Get the name-stream map from the PDB.
147 E : pdb::PdbInfoHeader70 pdb_header = {};
148 E : pdb::NameStreamMap name_stream_map;
149 E : if (!pdb::ReadHeaderInfoStream(pdb_file, &pdb_header, &name_stream_map)) {
150 i : LOG(ERROR) << "Failed to read PDB header info stream: " << pdb_path.value();
151 i : return false;
152 : }
153 :
154 : // Get the basic block addresses from the PDB file.
155 : pdb::NameStreamMap::const_iterator name_it = name_stream_map.find(
156 E : common::kBasicBlockRangesStreamName);
157 E : if (name_it == name_stream_map.end()) {
158 E : LOG(ERROR) << "PDB does not contain basic block ranges stream: "
159 : << pdb_path.value();
160 E : return false;
161 : }
162 E : scoped_refptr<pdb::PdbStream> bb_ranges_stream;
163 E : bb_ranges_stream = pdb_file.GetStream(name_it->second);
164 E : if (bb_ranges_stream.get() == NULL) {
165 i : LOG(ERROR) << "PDB basic block ranges stream has invalid index: "
166 : << name_it->second;
167 i : return false;
168 : }
169 :
170 : // Read the basic block range stream.
171 : if (!bb_ranges_stream->Seek(0) ||
172 E : !bb_ranges_stream->Read(bb_ranges)) {
173 i : LOG(ERROR) << "Failed to read basic block range stream from PDB: "
174 : << pdb_path.value();
175 i : return false;
176 : }
177 :
178 E : return true;
179 E : }
180 :
181 : bool LoadPdbInfo(PdbInfoMap* pdb_info_cache,
182 : const ModuleInformation& module_info,
183 E : PdbInfo** pdb_info) {
184 E : DCHECK(pdb_info_cache != NULL);
185 E : DCHECK(pdb_info != NULL);
186 :
187 E : *pdb_info = NULL;
188 :
189 : // Look for a cached entry first. If the cached entry is found but has no
190 : // pdb_path then it is a cached failure.
191 E : PdbInfoMap::iterator it = pdb_info_cache->find(module_info);
192 E : if (it != pdb_info_cache->end()) {
193 E : *pdb_info = &(it->second);
194 E : bool is_valid = !it->second.pdb_path.empty();
195 E : return is_valid;
196 : }
197 :
198 : // Insert a new (empty) PdbInfo for module_info and keep a reference to it.
199 : // If any of the operations below fail, the pdb_path in the PdbInfo structure
200 : // will not have been populated.
201 E : PdbInfo& pdb_info_ref = (*pdb_info_cache)[module_info];
202 :
203 : // Find the PDB file for the module.
204 E : base::FilePath pdb_path;
205 E : base::FilePath module_path(module_info.image_file_name);
206 E : if (!pe::FindPdbForModule(module_path, &pdb_path) || pdb_path.empty()) {
207 i : LOG(ERROR) << "Failed to find PDB for module: " << module_path.value();
208 i : return false;
209 : }
210 :
211 : // Load the line information from the PDB.
212 E : if (!pdb_info_ref.line_info.Init(pdb_path)) {
213 i : LOG(ERROR) << "Failed to extract line information from PDB file: "
214 : << pdb_path.value();
215 i : return false;
216 : }
217 :
218 : // This logs verbosely for us.
219 E : if (!LoadBasicBlockRanges(pdb_path, &pdb_info_ref.bb_ranges)) {
220 i : return false;
221 : }
222 :
223 : // Populate the pdb_path field of pdb_info_ref, which marks the cached
224 : // entry as valid.
225 E : pdb_info_ref.pdb_path = pdb_path;
226 :
227 : // Return a pointer to the pdb_info entry.
228 E : *pdb_info = &pdb_info_ref;
229 :
230 E : return true;
231 E : }
232 :
233 E : bool IsValidFrequencySize(size_t size) {
234 E : return size == 1 || size == 2 || size == 4;
235 E : }
236 :
237 : // TODO(sebmarchand): Move this to indexed_frequency_util.
238 : uint32 GetFrequency(const TraceIndexedFrequencyData* data,
239 : size_t bb_id,
240 E : size_t column) {
241 E : DCHECK(data != NULL);
242 E : DCHECK(IsValidFrequencySize(data->frequency_size));
243 E : DCHECK_LT(bb_id, data->num_entries);
244 E : DCHECK_LT(column, data->num_columns);
245 :
246 : DCHECK(data->data_type == common::IndexedFrequencyData::BASIC_BLOCK_ENTRY ||
247 : data->data_type == common::IndexedFrequencyData::BRANCH ||
248 E : data->data_type == common::IndexedFrequencyData::COVERAGE);
249 :
250 E : size_t offset = bb_id * data->num_columns + column;
251 E : switch (data->frequency_size) {
252 : case 1:
253 E : return data->frequency_data[offset];
254 : case 2:
255 E : return reinterpret_cast<const uint16*>(data->frequency_data)[offset];
256 : case 4:
257 E : return reinterpret_cast<const uint32*>(data->frequency_data)[offset];
258 : }
259 :
260 i : NOTREACHED();
261 i : return 0;
262 E : }
263 :
264 : } // namespace basic_block_util
265 : } // namespace grinder
|