libpp/callgraph_container.cpp

/**
 * @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 "callgraph_container.h"
#include "cverb.h"
#include "parse_filename.h"
#include "profile_container.h"
#include "arrange_profiles.h" 
#include "populate.h"
#include "string_filter.h"
#include "op_bfd.h"
#include "op_sample_file.h"
#include "locate_images.h"

using namespace std;

namespace {

bool operator==(cg_symbol const & lhs, cg_symbol const & rhs)
{
	less_symbol cmp_symb;
	return !cmp_symb(lhs, rhs) && !cmp_symb(rhs, lhs);
}


// we store {caller,callee} inside a single u64
odb_key_t caller_to_key(u32 value)
{
	return odb_key_t(value) << 32;
}


u32 key_to_callee(odb_key_t key)
{
	return key & 0xffffffff;
}


bool compare_by_callee_vma(pair<odb_key_t, odb_value_t> const & lhs,
                           pair<odb_key_t, odb_value_t> const & rhs)
{
	return (key_to_callee(lhs.first)) < (key_to_callee(rhs.first));
}


/*
 * We need 2 comparators for callgraph to get the desired output:
 *
 *	caller_with_few_samples
 *	caller_with_many_samples
 * function_with_many_samples
 *	callee_with_many_samples
 *	callee_with_few_samples
 */

bool
compare_arc_count(symbol_entry const & lhs, symbol_entry const & rhs)
{
	return lhs.sample.counts[0] < rhs.sample.counts[0];
}


bool
compare_arc_count_reverse(symbol_entry const & lhs, symbol_entry const & rhs)
{
	return rhs.sample.counts[0] < lhs.sample.counts[0];
}


// find the nearest bfd symbol for the given file offset and check it's
// in range
op_bfd_symbol const *
get_symbol_by_filepos(op_bfd const & bfd, u32 bfd_offset,
                      vma_t offset, symbol_index_t & i)
{
	offset += bfd_offset;
	op_bfd_symbol tmpsym(offset, 0, string());

	// sorted by filepos so this will find the nearest
	vector<op_bfd_symbol>::const_iterator it =
		upper_bound(bfd.syms.begin(), bfd.syms.end(), tmpsym);

	if (it != bfd.syms.begin())
		--it;

	if (it == bfd.syms.end()) {
		cerr << "get_symbol_by_filepos: no symbols at all?" << endl;
		abort();
	}

	// if the offset is past the end of the symbol, we didn't find one
	u32 const end_offset = it->size() + it->filepos();

	if (offset >= end_offset) {
		// let's be verbose for now
		cerr << "warning: dropping hyperspace sample at offset "
		     << hex << offset << " >= " << end_offset
		     << " for binary " << bfd.get_filename() << dec << endl;
		return NULL;
	}

	i = distance(bfd.syms.begin(), it);
	return &(*it);
}


/// temporary caller and callee data held during processing
class call_data {
public:
	call_data(profile_container const & p, profile_t const & pr,
	          op_bfd const & bfd, u32 boff, image_name_id iid,
	          image_name_id aid, bool debug_info)
		: pc(p), profile(pr), b(bfd), boffset(boff), image(iid),
		  app(aid), debug(debug_info) {}

	/// point to a caller symbol
	void caller_sym(symbol_index_t i) {
		sym = symbol_entry();

		unsigned long start;
		unsigned long end;
		b.get_symbol_range(i, start, end);

		samples.clear();

		// see profile_t::samples_range() for why we need this check
		if (start > boffset) {
			profile_t::iterator_pair p_it = profile.samples_range(
				caller_to_key(start - boffset),
				caller_to_key(end - boffset));

			// Our odb_key_t contain (from_eip << 32 | to_eip),
			// the range of keys we selected above contains one
			// caller but different callees, and due to the
			// ordering callee offsets are not consecutive: so
			// we must sort them first.

			for (; p_it.first != p_it.second; ++p_it.first) {
				samples.push_back(make_pair(p_it.first.vma(),
					p_it.first.count()));
			}

			sort(samples.begin(), samples.end(),
			     compare_by_callee_vma);
		}

		sym.size = end - start;
		sym.name = symbol_names.create(b.syms[i].name());
		sym.sample.vma = b.sym_offset(i, start) + b.syms[i].vma();

		finish_sym(i, start);

		if (cverb << vdebug) {
			cverb << vdebug << hex << "Caller sym: "
			      << b.syms[i].name() << " filepos " << start
			      << "-" << end << dec << endl;
		}
	}

	/// point to a callee symbol
	bool callee_sym(u32 off) {
		sym = symbol_entry();

		symbol_index_t i;
		op_bfd_symbol const * bfdsym =
			get_symbol_by_filepos(b, boffset, off, i);

		if (!bfdsym)
			return false;

		callee_end = bfdsym->size() + bfdsym->filepos() - boffset;

		sym.size = bfdsym->size();
		sym.name = symbol_names.create(bfdsym->name());
		sym.sample.vma = bfdsym->vma();

		finish_sym(i, bfdsym->filepos());

		if (cverb << vdebug) {
			cverb << vdebug << hex << "Callee sym: "
			      << bfdsym->name() << " filepos "
			      << bfdsym->filepos() << "-"
			      << (bfdsym->filepos() + bfdsym->size())
			      << dec << endl;
		}
		return true;
	}

	void verbose_bfd(string const & prefix) const {
		cverb << vdebug << prefix << " " << b.get_filename()
		      << " offset " << boffset << " app "
		      << image_names.name(app) << endl;
	}

	typedef vector<pair<odb_key_t, odb_value_t> > samples_t;

	typedef samples_t::const_iterator const_iterator;

	samples_t samples;
	symbol_entry sym;
	u32 callee_end;

private:
	/// fill in the rest of the sym
	void finish_sym(symbol_index_t i, unsigned long start) {
		sym.image_name = image;
		sym.app_name = app;
		symbol_entry const * self = pc.find(sym);
		if (self)
			sym.sample.counts = self->sample.counts;

		if (debug) {
			string filename;
			file_location & loc = sym.sample.file_loc;
			if (b.get_linenr(i, start, filename, loc.linenr))
				loc.filename = debug_names.create(filename);
		}
	}

	profile_container const & pc;
	profile_t const & profile;
	op_bfd const & b;
	u32 boffset;
	image_name_id image;
	image_name_id app;
	bool debug;
};


/// accumulate all samples for a given caller/callee pair
u32
accumulate_callee(call_data::const_iterator & it, call_data::const_iterator end,
                  u32 callee_end)
{
	u32 count = 0;
	call_data::const_iterator const start = it;

	while (it != end) {
		u32 offset = key_to_callee(it->first);

		if (cverb << (vdebug & vlevel1)) {
			cverb << (vdebug & vlevel1) << hex << "offset: "
			      << offset << dec << endl;
		}

		// stop if we pass the end of the callee
		if (offset >= callee_end)
			break;

		count += it->second;
		++it;
	}

	// If we haven't advanced at all, then we'll get
	// an infinite loop, so we must abort.
	if (it == start) {
		cerr << "failure to advance iterator\n";
		abort();
	}

	return count;
}


} // anonymous namespace


void arc_recorder::
add(symbol_entry const & caller, symbol_entry const * callee,
    count_array_t const & arc_count)
{
	cg_data & data = sym_map[caller];

	// If we have a callee, add it to the caller's list, then
	// add the caller to the callee's list.
	if (callee) {
		data.callees[*callee] += arc_count;

		cg_data & callee_data = sym_map[*callee];

		callee_data.callers[caller] += arc_count;
	}
}


void arc_recorder::process_children(cg_symbol & sym, double threshold)
{
	// generate the synthetic self entry for the symbol
	symbol_entry self = sym;

	self.name = symbol_names.create(symbol_names.demangle(self.name)
	                                + " [self]");

	sym.total_callee_count += self.sample.counts;
	sym.callees.push_back(self);

	sort(sym.callers.begin(), sym.callers.end(), compare_arc_count);
	sort(sym.callees.begin(), sym.callees.end(), compare_arc_count_reverse);

	// FIXME: this relies on sort always being sample count

	cg_symbol::children::iterator cit = sym.callers.begin();
	cg_symbol::children::iterator cend = sym.callers.end();

	while (cit != cend && op_ratio(cit->sample.counts[0],
	       sym.total_caller_count[0]) < threshold)
		++cit;

	if (cit != cend)
		sym.callers.erase(sym.callers.begin(), cit);

	cit = sym.callees.begin();
	cend = sym.callees.end();

	while (cit != cend && op_ratio(cit->sample.counts[0],
	       sym.total_callee_count[0]) >= threshold)
		++cit;

	if (cit != cend)
		sym.callees.erase(cit, sym.callees.end());
}


void arc_recorder::
process(count_array_t total, double threshold,
        string_filter const & sym_filter)
{
	map_t::const_iterator it;
	map_t::const_iterator end = sym_map.end();

	for (it = sym_map.begin(); it != end; ++it) {
		cg_symbol sym((*it).first);
		cg_data const & data = (*it).second;

		// threshold out the main symbol if needed
		if (op_ratio(sym.sample.counts[0], total[0]) < threshold)
			continue;

		// FIXME: slow?
		if (!sym_filter.match(symbol_names.demangle(sym.name)))
			continue;

		cg_data::children::const_iterator cit;
		cg_data::children::const_iterator cend = data.callers.end();

		for (cit = data.callers.begin(); cit != cend; ++cit) {
			symbol_entry csym = cit->first;
			csym.sample.counts = cit->second;
			sym.callers.push_back(csym);
			sym.total_caller_count += cit->second;
		}

		cend = data.callees.end();

		for (cit = data.callees.begin(); cit != cend; ++cit) {
			symbol_entry csym = cit->first;
			csym.sample.counts = cit->second;
			sym.callees.push_back(csym);
			sym.total_callee_count += cit->second;
		}

		process_children(sym, threshold);

		cg_syms.push_back(sym);
	}
}


cg_collection arc_recorder::get_symbols() const
{
	return cg_syms;
}


void callgraph_container::populate(string const & archive_path, 
   list<inverted_profile> const & iprofiles,
   extra_images const & extra, bool debug_info, double threshold,
   bool merge_lib, string_filter const & sym_filter)
{
	// non callgraph samples container, we record sample at symbol level
	// not at vma level.
	profile_container pc(debug_info, 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(archive_path, pc, *it, sym_filter, 0);
	}

	add_symbols(pc);

	total_count = pc.samples_count();

	for (it = iprofiles.begin(); it != end; ++it) {
		for (size_t i = 0; i < it->groups.size(); ++i) {
			populate(archive_path, it->groups[i], it->image, extra,
				i, pc, debug_info, merge_lib);
		}
	}

	recorder.process(total_count, threshold / 100.0, sym_filter);
}


void callgraph_container::populate(string const & archive_path,
	list<image_set> const & lset,
	string const & app_image, extra_images const & extra, size_t pclass,
	profile_container const & pc, bool debug_info, bool merge_lib)
{
	list<image_set>::const_iterator lit;
	list<image_set>::const_iterator const lend = lset.end();
	for (lit = lset.begin(); lit != lend; ++lit) {
		list<profile_sample_files>::const_iterator pit;
		list<profile_sample_files>::const_iterator pend
			= lit->files.end();
		for (pit = lit->files.begin(); pit != pend; ++pit) {
			populate(archive_path, pit->cg_files, app_image,
				 extra, pclass, pc, debug_info, merge_lib);
		}
	}
}


void callgraph_container::populate(string const & archive_path,
	list<string> const & cg_files,
	string const & app_image, extra_images const & extra, size_t pclass,
	profile_container const & pc, bool debug_info, bool merge_lib)
{
	list<string>::const_iterator it;
	list<string>::const_iterator const end = cg_files.end();
	for (it = cg_files.begin(); it != end; ++it) {
		cverb << vdebug << "samples file : " << *it << endl;

		parsed_filename caller_file = parse_filename(*it);
		string const app_name = caller_file.image;

		image_error error;
		string caller_binary =
			find_image_path(archive_path, caller_file.lib_image,
					extra, error);

		if (error != image_ok)
			report_image_error(archive_path + caller_file.lib_image,
					   error, false);

		bool caller_bfd_ok = true;
		op_bfd caller_bfd(archive_path, caller_binary,
				  string_filter(), caller_bfd_ok);
		if (!caller_bfd_ok)
			report_image_error(caller_binary,
			                   image_format_failure, false);

		parsed_filename callee_file = parse_filename(*it);

		string callee_binary =
			find_image_path(archive_path, callee_file.cg_image,
			                extra, error);
		if (error != image_ok)
			report_image_error(callee_file.cg_image, error, false);

		bool callee_bfd_ok = true;
		op_bfd callee_bfd(archive_path, callee_binary,
				  string_filter(), callee_bfd_ok);
		if (!callee_bfd_ok)
			report_image_error(callee_binary,
		                           image_format_failure, false);

		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(*it);
		add(profile, caller_bfd, caller_bfd_ok, callee_bfd,
		    merge_lib ? app_image : app_name, pc,
		    debug_info, pclass);
	}
}


void callgraph_container::
add(profile_t const & profile, op_bfd const & caller_bfd, bool caller_bfd_ok,
   op_bfd const & callee_bfd, string const & app_name,
   profile_container const & pc, bool debug_info, size_t pclass)
{
	string const image_name = caller_bfd.get_filename();

	opd_header const & header = profile.get_header();

	// We can't use kernel sample file w/o the binary else we will
	// use it with a zero offset, the code below will abort because
	// we will get incorrect callee sub-range and out of range
	// callee vma. FIXME
	if (header.is_kernel && !caller_bfd_ok)
		return;

	// 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 (header.is_kernel || header.anon_start) {
		caller_offset = caller_bfd.get_start_offset(header.anon_start);
	}

	u32 callee_offset = 0;

	if (header.cg_to_is_kernel || header.cg_to_anon_start) {
		callee_offset =
			callee_bfd.get_start_offset(header.cg_to_anon_start);
	}

	image_name_id image_id = image_names.create(image_name);
	image_name_id callee_image_id = image_names.create(callee_bfd.get_filename());
	image_name_id app_id = image_names.create(app_name);

	call_data caller(pc, profile, caller_bfd, caller_offset, image_id,
	                   app_id, debug_info);
	call_data callee(pc, profile, callee_bfd, callee_offset,
	                   callee_image_id, app_id, debug_info);

	if (cverb << vdebug) {
		caller.verbose_bfd("Caller:");
		callee.verbose_bfd("Callee:");
	}

	// For each symbol in the caller bfd, process all arcs to
	// callee bfd symbols

	for (symbol_index_t i = 0; i < caller_bfd.syms.size(); ++i) {

		caller.caller_sym(i);

		call_data::const_iterator dit = caller.samples.begin();
		call_data::const_iterator dend = caller.samples.end();
		while (dit != dend) {
			// if we can't find the callee, skip an arc
			if (!callee.callee_sym(key_to_callee(dit->first))) {
				++dit;
				continue;
			}

			count_array_t arc_count;
			arc_count[pclass] =
				accumulate_callee(dit, dend, callee.callee_end);

			recorder.add(caller.sym, &callee.sym, arc_count);
		}
	}
}


void callgraph_container::add_symbols(profile_container const & pc)
{
	symbol_container::symbols_t::iterator it;
	symbol_container::symbols_t::iterator const end = pc.end_symbol();

	for (it = pc.begin_symbol(); it != end; ++it)
		recorder.add(*it, 0, count_array_t());
}


column_flags callgraph_container::output_hint() const
{
	column_flags output_hints = cf_none;

	// FIXME: costly: must we access directly recorder map ?
	cg_collection syms = recorder.get_symbols();

	cg_collection::const_iterator it;
	cg_collection::const_iterator const end = syms.end();
	for (it = syms.begin(); it != end; ++it)
		output_hints = it->output_hint(output_hints);

	return output_hints;
}


count_array_t callgraph_container::samples_count() const
{
	return total_count;
}


cg_collection callgraph_container::get_symbols() const
{
	return recorder.get_symbols();
}