[0d0e60]: libpp / callgraph_container.cpp  Maximize  Restore  History

Download this file

425 lines (348 with data), 12.2 kB

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
/**
* @file callgraph_container.cpp
* Container associating symbols and caller/caller symbols
*
* @remark Copyright 2004 OProfile authors
* @remark Read the file COPYING
*
* @author Philippe Elie
* @author John Levon
*/
#include <cstdlib>
#include <map>
#include <set>
#include <algorithm>
#include <iterator>
#include <string>
#include <iostream>
#include <numeric>
#include "cverb.h"
#include "parse_filename.h"
#include "callgraph_container.h"
#include "arrange_profiles.h"
#include "populate.h"
#include "string_filter.h"
#include "op_bfd.h"
#include "op_sample_file.h"
using namespace std;
namespace {
/// this comparator is used to partition cg filename by identical caller
/// allowing to avoid (partially) some redudant bfd open
/// \sa callgrap_container::populate()
struct compare_cg_filename {
bool operator()(string const & lhs, string const & rhs) const;
};
bool
compare_cg_filename::operator()(string const & lhs, string const & rhs) const
{
parsed_filename plhs = parse_filename(lhs);
parsed_filename prhs = parse_filename(rhs);
return plhs.lib_image < prhs.lib_image;
}
/**
* We need 3 comparator for callgraph, the arc are sorted by self_count,
* the caller are sorted by callee_counts in reverse order, the callee
* by callee_counts in "direct" order, these comparator are used by
* caller_callee_recorder::get_arc(), get_caller(), get_callee().
* These various order are used to order in this way:
*
* caller_with_few_callee_samples
* caller_with_many_callee_samples
* function_with_many_samples
* callee_with_many_callee_samples
* callee_with_few_callee_samples
*
* FIXME: not obvious if a mixed comparator will give more readable output.
*/
bool
compare_cg_symbol_by_self_count(cg_symbol const & lhs, cg_symbol const & rhs)
{
return lhs.self_counts[0] < rhs.self_counts[0];
}
struct compare_cg_symbol_by_callee_count
: public binary_function<cg_symbol, cg_symbol, bool> {
bool operator()(cg_symbol const & lhs, cg_symbol const & rhs) const {
return lhs.callee_counts[0] < rhs.callee_counts[0];
}
};
} // anonymous namespace
caller_callee_recorder::~caller_callee_recorder()
{
map_t::iterator end = caller_callee.end();
for (map_t::iterator it = caller_callee.begin(); it != end; ++it) {
delete it->second;
}
end = callee_caller.end();
for (iterator it = callee_caller.begin(); it != end; ++it) {
delete it->second;
}
}
void caller_callee_recorder::fixup_callee_counts()
{
// FIXME: can be optimized easily
iterator end = caller_callee.end();
for (iterator it = caller_callee.begin(); it != end; ++it) {
pair<iterator, iterator> p_it =
caller_callee.equal_range(it->first);
count_array_t counts;
for (; p_it.first != p_it.second; ++p_it.first) {
counts += p_it.first->first.sample.counts;
}
cg_symbol & symbol = const_cast<cg_symbol&>(it->first);
symbol.callee_counts = counts;
}
}
void caller_callee_recorder::
add_arc(cg_symbol const & caller, cg_symbol const * callee)
{
if (callee)
callee = new cg_symbol(*callee);
caller_callee.insert(map_t::value_type(caller, callee));
if (callee) {
callee_caller.insert(map_t::value_type(*callee,
new cg_symbol(caller)));
}
}
vector<cg_symbol> caller_callee_recorder::get_arc() const
{
vector<cg_symbol> result;
iterator const end = caller_callee.end();
for (iterator it = caller_callee.begin(); it != end; ) {
result.push_back(it->first);
it = caller_callee.upper_bound(it->first);
}
sort(result.begin(), result.end(), compare_cg_symbol_by_self_count);
return result;
}
vector<cg_symbol> caller_callee_recorder::
get_callee(cg_symbol const & symbol) const
{
vector<cg_symbol> result;
pair<iterator, iterator> p_it = callee_caller.equal_range(symbol);
for (; p_it.first != p_it.second; ++p_it.first) {
if (p_it.first->second) {
// the reverse map doesn't contain correct information
// about callee_counts, retrieve them.
cg_symbol symbol = *p_it.first->second;
cg_symbol const * symb = find_caller(symbol);
if (symb)
symbol.callee_counts = symb->callee_counts;
result.push_back(symbol);
}
}
sort(result.begin(), result.end(),
compare_cg_symbol_by_callee_count());
return result;
}
vector<cg_symbol> caller_callee_recorder::
get_caller(cg_symbol const & symbol) const
{
vector<cg_symbol> result;
pair<iterator, iterator> p_it = caller_callee.equal_range(symbol);
for (; p_it.first != p_it.second; ++p_it.first) {
if (p_it.first->second) {
// the direct map second member doesn't contain correct
// information about callee_counts, retrieve them.
cg_symbol symbol = *p_it.first->second;
cg_symbol const * symb = find_caller(symbol);
if (symb)
symbol.callee_counts = symb->callee_counts;
result.push_back(symbol);
}
}
sort(result.begin(), result.end(),
not2(compare_cg_symbol_by_callee_count()));
return result;
}
cg_symbol const * caller_callee_recorder::
find_caller(cg_symbol const & symbol) const
{
map_t::const_iterator it = caller_callee.find(symbol);
return it == caller_callee.end() ? 0 : &it->first;
}
void callgraph_container::
populate(list<inverted_profile> const & iprofiles)
{
/// Normal (i.e non callgraph) samples container, we record sample
/// at symbol level, not at vma level.
profile_container symbols(false, false);
list<inverted_profile>::const_iterator it;
list<inverted_profile>::const_iterator const end = iprofiles.end();
for (it = iprofiles.begin(); it != end; ++it) {
// populate_caller_image take care about empty sample filename
populate_for_image(symbols, *it, string_filter());
}
// partition identical lib_image (e.g identical caller) to avoid
// some redundant bfd_open but it's difficult to avoid more.
// FIXME: must we try harder to avoid bfd open ?
typedef multiset<string, compare_cg_filename> cg_fileset;
cg_fileset fset;
for (it = iprofiles.begin(); it != end; ++it) {
for (size_t i = 0; i < it->groups.size(); ++i) {
list<image_set>::const_iterator lit;
list<image_set>::const_iterator const lend
= it->groups[i].end();
for (lit = it->groups[i].begin(); lit != lend; ++lit) {
list<profile_sample_files>::const_iterator pit
= lit->files.begin();
list<profile_sample_files>::const_iterator pend
= lit->files.end();
for (; pit != pend; ++pit) {
copy(pit->cg_files.begin(),
pit->cg_files.end(),
inserter(fset, fset.begin()));
}
}
}
}
// now iterate over our partition, equivalence class get the same bfd,
// the caller.
cg_fileset::const_iterator cit;
for (cit = fset.begin(); cit != fset.end(); ) {
parsed_filename caller_file = parse_filename(*cit);
string const app_name = caller_file.image;
// FIXME: there is some error checking needed here.
bool ok = true;
op_bfd bfd_caller(caller_file.lib_image, string_filter(), ok);
cverb << "cg subset caller: "
<< caller_file.lib_image << "\n";
cg_fileset::const_iterator last;
for (last = fset.upper_bound(*cit); cit != last; ++cit) {
parsed_filename callee_file = parse_filename(*cit);
cverb << "adding: " << callee_file.cg_image << endl;
// FIXME: there is some error checking needed here.
op_bfd bfd_callee(callee_file.cg_image,
string_filter(), ok);
profile_t profile;
// We can't use start_offset support in profile_t, give
// it a zero offset and we will fix that in add()
profile.add_sample_file(*cit, 0);
add(profile, bfd_caller, bfd_callee,
app_name, symbols);
}
}
add_leaf_arc(symbols);
recorder.fixup_callee_counts();
}
void callgraph_container::
add(profile_t const & profile, op_bfd const & caller, op_bfd const & callee,
string const & app_name, profile_container const & symbols)
{
string const image_name = caller.get_filename();
// We must handle start_offset, this offset can be different for the
// caller and the callee: kernel sample traversing the syscall barrier.
u32 caller_offset = 0;
if (profile.get_header().is_kernel)
caller_offset = caller.get_start_offset();
u32 callee_offset = 0;
if (profile.get_header().cg_to_is_kernel)
callee_offset = callee.get_start_offset();
cverb << hex << "caller_offset: " << caller_offset << dec << endl;
cverb << hex << "callee_offset: " << callee_offset << dec << endl;
for (symbol_index_t i = 0; i < caller.syms.size(); ++i) {
u32 start, end;
caller.get_symbol_range(i, start, end);
profile_t::iterator_pair p_it =
profile.samples_range(odb_key_t(start - caller_offset) << 32,
odb_key_t(end - caller_offset) << 32);
cg_symbol symb_caller;
symb_caller.sample.counts[0] = 0;
symb_caller.size = end - start;
symb_caller.name = symbol_names.create(caller.syms[i].name());
symb_caller.sample.file_loc.linenr = 0;
symb_caller.image_name = image_names.create(image_name);
symb_caller.app_name = image_names.create(app_name);
symb_caller.sample.vma = caller.sym_offset(i, start) +
caller.syms[i].vma();
symbol_entry const * self = symbols.find(symb_caller);
if (self)
symb_caller.self_counts = self->sample.counts;
// Our odb_key_t contain (from_eip << 32 | to_eip), the range
// of key we slected above can contain different callee but
// due to the ordering this callee are consecutive so we
// iterate over the range, then iterate over the sub-range
// for each distinct callee symbol.
while (p_it.first != p_it.second) {
// find the callee.
profile_t::const_iterator it = p_it.first;
bfd_vma callee_vma = (it.vma() & 0xffffffff) +
callee_offset;
cverb << "offset caller: " << hex
<< (p_it.first.vma() >> 32) << " callee: "
<< callee_vma << dec << endl;
op_bfd_symbol symb(callee_vma, 0, string());
vector<op_bfd_symbol>::const_iterator bfd_symb_callee =
upper_bound(callee.syms.begin(),
callee.syms.end(), symb);
// ugly but upper_bound() work in this way.
if (bfd_symb_callee != callee.syms.begin())
--bfd_symb_callee;
if (bfd_symb_callee == callee.syms.end()) {
// FIXME: not clear if we need to abort,
// recover or an exception, for now I need a
// a core dump
cerr << "Unable to retrieve callee symbol\n";
abort();
}
u32 upper_bound = bfd_symb_callee->size() +
bfd_symb_callee->filepos();
cverb << "upper bound: " << hex << upper_bound
<< dec << endl;
// Process all arc from this caller to this callee
u32 caller_callee_count = 0;
for (; it != p_it.second &&
(it.vma() & 0xffffffff) + callee_offset < upper_bound;
++it) {
caller_callee_count += it.count();
}
if (it == p_it.first) {
// This is impossible, we need a core dump else
// we enter in an infinite loop
cerr << "failure to advance iterator\n";
abort();
}
symb_caller.sample.counts[0] = caller_callee_count;
cverb << caller.syms[i].name() << " "
<< bfd_symb_callee->name() << " "
<< caller_callee_count << endl;
cg_symbol symb_callee;
symb_callee.sample.counts[0] = 0;
symb_callee.size = bfd_symb_callee->size();
symb_callee.name =
symbol_names.create(bfd_symb_callee->name());
symb_callee.sample.file_loc.linenr = 0;
symb_callee.image_name =
image_names.create(callee.get_filename());
symb_callee.app_name = image_names.create(app_name);
symb_callee.sample.vma = bfd_symb_callee->vma();
symbol_entry const * self = symbols.find(symb_callee);
if (self)
symb_callee.self_counts = self->sample.counts;
recorder.add_arc(symb_caller, &symb_callee);
// next callee symbol
p_it.first = it;
}
}
}
void callgraph_container::add_leaf_arc(profile_container const & symbols)
{
symbol_container::symbols_t::iterator it;
symbol_container::symbols_t::iterator const end = symbols.end_symbol();
for (it = symbols.begin_symbol(); it != end; ++it) {
cg_symbol symbol(*it);
symbol.self_counts = it->sample.counts;
recorder.add_arc(symbol, 0);
}
}
vector<cg_symbol> callgraph_container::get_arc() const
{
return recorder.get_arc();
}
vector<cg_symbol> callgraph_container::get_callee(cg_symbol const & s) const
{
return recorder.get_callee(s);
}
vector<cg_symbol> callgraph_container::get_caller(cg_symbol const & s) const
{
return recorder.get_caller(s);
}

Get latest updates about Open Source Projects, Conferences and News.

Sign up for the SourceForge newsletter:

JavaScript is required for this form.





No, thanks