1 /** 2 * @file callgraph_container.cpp 3 * Container associating symbols and caller/caller symbols 4 * 5 * @remark Copyright 2004 OProfile authors 6 * @remark Read the file COPYING 7 * 8 * @author Philippe Elie 9 * @author John Levon 10 */ 11 12 #include <cstdlib> 13 14 #include <map> 15 #include <set> 16 #include <algorithm> 17 #include <iterator> 18 #include <string> 19 #include <iostream> 20 #include <numeric> 21 22 #include "callgraph_container.h" 23 #include "cverb.h" 24 #include "parse_filename.h" 25 #include "profile_container.h" 26 #include "arrange_profiles.h" 27 #include "populate.h" 28 #include "string_filter.h" 29 #include "op_bfd.h" 30 #include "op_sample_file.h" 31 #include "locate_images.h" 32 33 using namespace std; 34 35 namespace { 36 37 bool operator==(cg_symbol const & lhs, cg_symbol const & rhs) 38 { 39 less_symbol cmp_symb; 40 return !cmp_symb(lhs, rhs) && !cmp_symb(rhs, lhs); 41 } 42 43 44 // we store {caller,callee} inside a single u64 45 odb_key_t caller_to_key(u32 value) 46 { 47 return odb_key_t(value) << 32; 48 } 49 50 51 u32 key_to_callee(odb_key_t key) 52 { 53 return key & 0xffffffff; 54 } 55 56 57 bool compare_by_callee_vma(pair<odb_key_t, count_type> const & lhs, 58 pair<odb_key_t, count_type> const & rhs) 59 { 60 return (key_to_callee(lhs.first)) < (key_to_callee(rhs.first)); 61 } 62 63 64 /* 65 * We need 2 comparators for callgraph to get the desired output: 66 * 67 * caller_with_few_samples 68 * caller_with_many_samples 69 * function_with_many_samples 70 * callee_with_many_samples 71 * callee_with_few_samples 72 */ 73 74 bool 75 compare_arc_count(symbol_entry const & lhs, symbol_entry const & rhs) 76 { 77 return lhs.sample.counts[0] < rhs.sample.counts[0]; 78 } 79 80 81 bool 82 compare_arc_count_reverse(symbol_entry const & lhs, symbol_entry const & rhs) 83 { 84 return rhs.sample.counts[0] < lhs.sample.counts[0]; 85 } 86 87 88 // find the nearest bfd symbol for the given file offset and check it's 89 // in range 90 op_bfd_symbol const * 91 get_symbol_by_filepos(op_bfd const & bfd, u32 bfd_offset, 92 vma_t offset, symbol_index_t & i) 93 { 94 offset += bfd_offset; 95 op_bfd_symbol tmpsym(offset, 0, string()); 96 97 // sorted by filepos so this will find the nearest 98 vector<op_bfd_symbol>::const_iterator it = 99 upper_bound(bfd.syms.begin(), bfd.syms.end(), tmpsym); 100 101 if (it != bfd.syms.begin()) 102 --it; 103 104 if (it == bfd.syms.end()) { 105 cerr << "get_symbol_by_filepos: no symbols at all?" << endl; 106 abort(); 107 } 108 109 // if the offset is past the end of the symbol, we didn't find one 110 u32 const end_offset = it->size() + it->filepos(); 111 112 if (offset >= end_offset) { 113 // let's be verbose for now 114 cerr << "warning: dropping hyperspace sample at offset " 115 << hex << offset << " >= " << end_offset 116 << " for binary " << bfd.get_filename() << dec << endl; 117 return NULL; 118 } 119 120 i = distance(bfd.syms.begin(), it); 121 return &(*it); 122 } 123 124 125 /// temporary caller and callee data held during processing 126 class call_data { 127 public: 128 call_data(profile_container const & p, profile_t const & pr, 129 op_bfd const & bfd, u32 boff, image_name_id iid, 130 image_name_id aid, bool debug_info) 131 : pc(p), profile(pr), b(bfd), boffset(boff), image(iid), 132 app(aid), debug(debug_info) {} 133 134 /// point to a caller symbol 135 void caller_sym(symbol_index_t i) { 136 sym = symbol_entry(); 137 138 unsigned long long start; 139 unsigned long long end; 140 b.get_symbol_range(i, start, end); 141 142 samples.clear(); 143 144 // see profile_t::samples_range() for why we need this check 145 if (start > boffset) { 146 profile_t::iterator_pair p_it = profile.samples_range( 147 caller_to_key(start - boffset), 148 caller_to_key(end - boffset)); 149 150 // Our odb_key_t contain (from_eip << 32 | to_eip), 151 // the range of keys we selected above contains one 152 // caller but different callees, and due to the 153 // ordering callee offsets are not consecutive: so 154 // we must sort them first. 155 156 for (; p_it.first != p_it.second; ++p_it.first) { 157 samples.push_back(make_pair(p_it.first.vma(), 158 p_it.first.count())); 159 } 160 161 sort(samples.begin(), samples.end(), 162 compare_by_callee_vma); 163 } 164 165 sym.size = end - start; 166 sym.name = symbol_names.create(b.syms[i].name()); 167 sym.sample.vma = b.syms[i].vma(); 168 169 finish_sym(i, start); 170 171 if (cverb << vdebug) { 172 cverb << vdebug << hex << "Caller sym: " 173 << b.syms[i].name() << " filepos " << start 174 << "-" << end << dec << endl; 175 } 176 } 177 178 /// point to a callee symbol 179 bool callee_sym(u32 off) { 180 sym = symbol_entry(); 181 182 symbol_index_t i = 0; 183 op_bfd_symbol const * bfdsym = 184 get_symbol_by_filepos(b, boffset, off, i); 185 186 if (!bfdsym) 187 return false; 188 189 callee_end = bfdsym->size() + bfdsym->filepos() - boffset; 190 191 sym.size = bfdsym->size(); 192 sym.name = symbol_names.create(bfdsym->name()); 193 sym.sample.vma = bfdsym->vma(); 194 195 finish_sym(i, bfdsym->filepos()); 196 197 if (cverb << vdebug) { 198 cverb << vdebug << hex << "Callee sym: " 199 << bfdsym->name() << " filepos " 200 << bfdsym->filepos() << "-" 201 << (bfdsym->filepos() + bfdsym->size()) 202 << dec << endl; 203 } 204 return true; 205 } 206 207 void verbose_bfd(string const & prefix) const { 208 cverb << vdebug << prefix << " " << b.get_filename() 209 << " offset " << boffset << " app " 210 << image_names.name(app) << endl; 211 } 212 213 typedef vector<pair<odb_key_t, count_type> > samples_t; 214 215 typedef samples_t::const_iterator const_iterator; 216 217 samples_t samples; 218 symbol_entry sym; 219 u32 callee_end; 220 221 private: 222 /// fill in the rest of the sym 223 void finish_sym(symbol_index_t i, unsigned long start) { 224 sym.image_name = image; 225 sym.app_name = app; 226 symbol_entry const * self = pc.find(sym); 227 if (self) 228 sym.sample.counts = self->sample.counts; 229 230 if (debug) { 231 string filename; 232 file_location & loc = sym.sample.file_loc; 233 if (b.get_linenr(i, start, filename, loc.linenr)) 234 loc.filename = debug_names.create(filename); 235 } 236 } 237 238 profile_container const & pc; 239 profile_t const & profile; 240 op_bfd const & b; 241 u32 boffset; 242 image_name_id image; 243 image_name_id app; 244 bool debug; 245 }; 246 247 248 /// accumulate all samples for a given caller/callee pair 249 count_type 250 accumulate_callee(call_data::const_iterator & it, call_data::const_iterator end, 251 u32 callee_end) 252 { 253 count_type count = 0; 254 call_data::const_iterator const start = it; 255 256 while (it != end) { 257 u32 offset = key_to_callee(it->first); 258 259 if (cverb << (vdebug & vlevel1)) { 260 cverb << (vdebug & vlevel1) << hex << "offset: " 261 << offset << dec << endl; 262 } 263 264 // stop if we pass the end of the callee 265 if (offset >= callee_end) 266 break; 267 268 count += it->second; 269 ++it; 270 } 271 272 // If we haven't advanced at all, then we'll get 273 // an infinite loop, so we must abort. 274 if (it == start) { 275 cerr << "failure to advance iterator\n"; 276 abort(); 277 } 278 279 return count; 280 } 281 282 283 } // anonymous namespace 284 285 286 void arc_recorder:: 287 add(symbol_entry const & caller, symbol_entry const * callee, 288 count_array_t const & arc_count) 289 { 290 cg_data & data = sym_map[caller]; 291 292 // If we have a callee, add it to the caller's list, then 293 // add the caller to the callee's list. 294 if (callee) { 295 data.callees[*callee] += arc_count; 296 297 cg_data & callee_data = sym_map[*callee]; 298 299 callee_data.callers[caller] += arc_count; 300 } 301 } 302 303 304 void arc_recorder::process_children(cg_symbol & sym, double threshold) 305 { 306 // generate the synthetic self entry for the symbol 307 symbol_entry self = sym; 308 309 self.name = symbol_names.create(symbol_names.demangle(self.name) 310 + " [self]"); 311 312 sym.total_callee_count += self.sample.counts; 313 sym.callees.push_back(self); 314 315 sort(sym.callers.begin(), sym.callers.end(), compare_arc_count); 316 sort(sym.callees.begin(), sym.callees.end(), compare_arc_count_reverse); 317 318 // FIXME: this relies on sort always being sample count 319 320 cg_symbol::children::iterator cit = sym.callers.begin(); 321 cg_symbol::children::iterator cend = sym.callers.end(); 322 323 while (cit != cend && op_ratio(cit->sample.counts[0], 324 sym.total_caller_count[0]) < threshold) 325 ++cit; 326 327 if (cit != cend) 328 sym.callers.erase(sym.callers.begin(), cit); 329 330 cit = sym.callees.begin(); 331 cend = sym.callees.end(); 332 333 while (cit != cend && op_ratio(cit->sample.counts[0], 334 sym.total_callee_count[0]) >= threshold) 335 ++cit; 336 337 if (cit != cend) 338 sym.callees.erase(cit, sym.callees.end()); 339 } 340 341 342 void arc_recorder:: 343 process(count_array_t total, double threshold, 344 string_filter const & sym_filter) 345 { 346 map_t::const_iterator it; 347 map_t::const_iterator end = sym_map.end(); 348 349 for (it = sym_map.begin(); it != end; ++it) { 350 cg_symbol sym((*it).first); 351 cg_data const & data = (*it).second; 352 353 // threshold out the main symbol if needed 354 if (op_ratio(sym.sample.counts[0], total[0]) < threshold) 355 continue; 356 357 // FIXME: slow? 358 if (!sym_filter.match(symbol_names.demangle(sym.name))) 359 continue; 360 361 cg_data::children::const_iterator cit; 362 cg_data::children::const_iterator cend = data.callers.end(); 363 364 for (cit = data.callers.begin(); cit != cend; ++cit) { 365 symbol_entry csym = cit->first; 366 csym.sample.counts = cit->second; 367 sym.callers.push_back(csym); 368 sym.total_caller_count += cit->second; 369 } 370 371 cend = data.callees.end(); 372 373 for (cit = data.callees.begin(); cit != cend; ++cit) { 374 symbol_entry csym = cit->first; 375 csym.sample.counts = cit->second; 376 sym.callees.push_back(csym); 377 sym.total_callee_count += cit->second; 378 } 379 380 process_children(sym, threshold); 381 382 // insert sym into cg_syms_objs 383 // then store pointer to sym in cg_syms 384 cg_syms.push_back(&(*cg_syms_objs.insert(cg_syms_objs.end(), sym))); 385 } 386 } 387 388 389 symbol_collection const & arc_recorder::get_symbols() const 390 { 391 return cg_syms; 392 } 393 394 395 void callgraph_container::populate(list<inverted_profile> const & iprofiles, 396 extra_images const & extra, bool debug_info, double threshold, 397 bool merge_lib, string_filter const & sym_filter) 398 { 399 this->extra_found_images = extra; 400 // non callgraph samples container, we record sample at symbol level 401 // not at vma level. 402 profile_container pc(debug_info, false, extra_found_images); 403 404 list<inverted_profile>::const_iterator it; 405 list<inverted_profile>::const_iterator const end = iprofiles.end(); 406 for (it = iprofiles.begin(); it != end; ++it) { 407 // populate_caller_image take care about empty sample filename 408 populate_for_image(pc, *it, sym_filter, 0); 409 } 410 411 add_symbols(pc); 412 413 total_count = pc.samples_count(); 414 415 for (it = iprofiles.begin(); it != end; ++it) { 416 for (size_t i = 0; i < it->groups.size(); ++i) { 417 populate(it->groups[i], it->image, 418 i, pc, debug_info, merge_lib); 419 } 420 } 421 422 recorder.process(total_count, threshold / 100.0, sym_filter); 423 } 424 425 426 void callgraph_container::populate(list<image_set> const & lset, 427 string const & app_image, size_t pclass, 428 profile_container const & pc, bool debug_info, bool merge_lib) 429 { 430 list<image_set>::const_iterator lit; 431 list<image_set>::const_iterator const lend = lset.end(); 432 for (lit = lset.begin(); lit != lend; ++lit) { 433 list<profile_sample_files>::const_iterator pit; 434 list<profile_sample_files>::const_iterator pend 435 = lit->files.end(); 436 for (pit = lit->files.begin(); pit != pend; ++pit) { 437 populate(pit->cg_files, app_image, 438 pclass, pc, debug_info, merge_lib); 439 } 440 } 441 } 442 443 444 void callgraph_container::populate(list<string> const & cg_files, 445 string const & app_image, size_t pclass, 446 profile_container const & pc, bool debug_info, bool merge_lib) 447 { 448 list<string>::const_iterator it; 449 list<string>::const_iterator const end = cg_files.end(); 450 for (it = cg_files.begin(); it != end; ++it) { 451 cverb << vdebug << "samples file : " << *it << endl; 452 453 parsed_filename caller_file = 454 parse_filename(*it, extra_found_images); 455 string const app_name = caller_file.image; 456 457 image_error error; 458 extra_found_images.find_image_path(caller_file.lib_image, 459 error, false); 460 461 if (error != image_ok) 462 report_image_error(caller_file.lib_image, 463 error, false, extra_found_images); 464 465 bool caller_bfd_ok = true; 466 op_bfd caller_bfd(caller_file.lib_image, 467 string_filter(), extra_found_images, caller_bfd_ok); 468 if (!caller_bfd_ok) 469 report_image_error(caller_file.lib_image, 470 image_format_failure, false, 471 extra_found_images); 472 473 parsed_filename callee_file = 474 parse_filename(*it, extra_found_images); 475 476 extra_found_images.find_image_path(callee_file.cg_image, 477 error, false); 478 if (error != image_ok) 479 report_image_error(callee_file.cg_image, 480 error, false, extra_found_images); 481 482 bool callee_bfd_ok = true; 483 op_bfd callee_bfd(callee_file.cg_image, 484 string_filter(), extra_found_images, callee_bfd_ok); 485 if (!callee_bfd_ok) 486 report_image_error(callee_file.cg_image, 487 image_format_failure, false, 488 extra_found_images); 489 490 profile_t profile; 491 // We can't use start_offset support in profile_t, give 492 // it a zero offset and we will fix that in add() 493 profile.add_sample_file(*it); 494 add(profile, caller_bfd, caller_bfd_ok, callee_bfd, 495 merge_lib ? app_image : app_name, pc, 496 debug_info, pclass); 497 } 498 } 499 500 501 void callgraph_container:: 502 add(profile_t const & profile, op_bfd const & caller_bfd, bool caller_bfd_ok, 503 op_bfd const & callee_bfd, string const & app_name, 504 profile_container const & pc, bool debug_info, size_t pclass) 505 { 506 string const image_name = caller_bfd.get_filename(); 507 508 opd_header const & header = profile.get_header(); 509 510 // We can't use kernel sample file w/o the binary else we will 511 // use it with a zero offset, the code below will abort because 512 // we will get incorrect callee sub-range and out of range 513 // callee vma. FIXME 514 if (header.is_kernel && !caller_bfd_ok) 515 return; 516 517 // We must handle start_offset, this offset can be different for the 518 // caller and the callee: kernel sample traversing the syscall barrier. 519 u32 caller_offset; 520 if (header.is_kernel) 521 caller_offset = caller_bfd.get_start_offset(0); 522 else 523 caller_offset = header.anon_start; 524 525 u32 callee_offset; 526 if (header.cg_to_is_kernel) 527 callee_offset = callee_bfd.get_start_offset(0); 528 else 529 callee_offset = header.cg_to_anon_start; 530 531 image_name_id image_id = image_names.create(image_name); 532 image_name_id callee_image_id = image_names.create(callee_bfd.get_filename()); 533 image_name_id app_id = image_names.create(app_name); 534 535 call_data caller(pc, profile, caller_bfd, caller_offset, image_id, 536 app_id, debug_info); 537 call_data callee(pc, profile, callee_bfd, callee_offset, 538 callee_image_id, app_id, debug_info); 539 540 if (cverb << vdebug) { 541 caller.verbose_bfd("Caller:"); 542 callee.verbose_bfd("Callee:"); 543 } 544 545 // For each symbol in the caller bfd, process all arcs to 546 // callee bfd symbols 547 548 for (symbol_index_t i = 0; i < caller_bfd.syms.size(); ++i) { 549 550 caller.caller_sym(i); 551 552 call_data::const_iterator dit = caller.samples.begin(); 553 call_data::const_iterator dend = caller.samples.end(); 554 while (dit != dend) { 555 // if we can't find the callee, skip an arc 556 if (!callee.callee_sym(key_to_callee(dit->first))) { 557 ++dit; 558 continue; 559 } 560 561 count_array_t arc_count; 562 arc_count[pclass] = 563 accumulate_callee(dit, dend, callee.callee_end); 564 565 recorder.add(caller.sym, &callee.sym, arc_count); 566 } 567 } 568 } 569 570 571 void callgraph_container::add_symbols(profile_container const & pc) 572 { 573 symbol_container::symbols_t::iterator it; 574 symbol_container::symbols_t::iterator const end = pc.end_symbol(); 575 576 for (it = pc.begin_symbol(); it != end; ++it) 577 recorder.add(*it, 0, count_array_t()); 578 } 579 580 581 column_flags callgraph_container::output_hint() const 582 { 583 column_flags output_hints = cf_none; 584 585 // FIXME: costly: must we access directly recorder map ? 586 symbol_collection syms = recorder.get_symbols(); 587 588 symbol_collection::iterator it; 589 symbol_collection::iterator const end = syms.end(); 590 for (it = syms.begin(); it != end; ++it) 591 output_hints = (*it)->output_hint(output_hints); 592 593 return output_hints; 594 } 595 596 597 count_array_t callgraph_container::samples_count() const 598 { 599 return total_count; 600 } 601 602 603 symbol_collection const & callgraph_container::get_symbols() const 604 { 605 return recorder.get_symbols(); 606 } 607
