gprof: Internals
9.3 'gprof''s Internal Operation
================================
Like most programs, 'gprof' begins by processing its options. During
this stage, it may building its symspec list ('sym_ids.c:sym_id_add'),
if options are specified which use symspecs. 'gprof' maintains a single
linked list of symspecs, which will eventually get turned into 12 symbol
tables, organized into six include/exclude pairs--one pair each for the
flat profile (INCL_FLAT/EXCL_FLAT), the call graph arcs
(INCL_ARCS/EXCL_ARCS), printing in the call graph
(INCL_GRAPH/EXCL_GRAPH), timing propagation in the call graph
(INCL_TIME/EXCL_TIME), the annotated source listing
(INCL_ANNO/EXCL_ANNO), and the execution count listing
(INCL_EXEC/EXCL_EXEC).
After option processing, 'gprof' finishes building the symspec list
by adding all the symspecs in 'default_excluded_list' to the exclude
lists EXCL_TIME and EXCL_GRAPH, and if line-by-line profiling is
specified, EXCL_FLAT as well. These default excludes are not added to
EXCL_ANNO, EXCL_ARCS, and EXCL_EXEC.
Next, the BFD library is called to open the object file, verify that
it is an object file, and read its symbol table ('core.c:core_init'),
using 'bfd_canonicalize_symtab' after mallocing an appropriately sized
array of symbols. At this point, function mappings are read (if the
'--file-ordering' option has been specified), and the core text space is
read into memory (if the '-c' option was given).
'gprof''s own symbol table, an array of Sym structures, is now built.
This is done in one of two ways, by one of two routines, depending on
whether line-by-line profiling ('-l' option) has been enabled. For
normal profiling, the BFD canonical symbol table is scanned. For
line-by-line profiling, every text space address is examined, and a new
symbol table entry gets created every time the line number changes. In
either case, two passes are made through the symbol table--one to count
the size of the symbol table required, and the other to actually read
the symbols. In between the two passes, a single array of type 'Sym' is
created of the appropriate length. Finally, 'symtab.c:symtab_finalize'
is called to sort the symbol table and remove duplicate entries (entries
with the same memory address).
The symbol table must be a contiguous array for two reasons. First,
the 'qsort' library function (which sorts an array) will be used to sort
the symbol table. Also, the symbol lookup routine
('symtab.c:sym_lookup'), which finds symbols based on memory address,
uses a binary search algorithm which requires the symbol table to be a
sorted array. Function symbols are indicated with an 'is_func' flag.
Line number symbols have no special flags set. Additionally, a symbol
can have an 'is_static' flag to indicate that it is a local symbol.
With the symbol table read, the symspecs can now be translated into
Syms ('sym_ids.c:sym_id_parse'). Remember that a single symspec can
match multiple symbols. An array of symbol tables ('syms') is created,
each entry of which is a symbol table of Syms to be included or excluded
from a particular listing. The master symbol table and the symspecs are
examined by nested loops, and every symbol that matches a symspec is
inserted into the appropriate syms table. This is done twice, once to
count the size of each required symbol table, and again to build the
tables, which have been malloced between passes. From now on, to
determine whether a symbol is on an include or exclude symspec list,
'gprof' simply uses its standard symbol lookup routine on the
appropriate table in the 'syms' array.
Now the profile data file(s) themselves are read
('gmon_io.c:gmon_out_read'), first by checking for a new-style
'gmon.out' header, then assuming this is an old-style BSD 'gmon.out' if
the magic number test failed.
New-style histogram records are read by 'hist.c:hist_read_rec'. For
the first histogram record, allocate a memory array to hold all the
bins, and read them in. When multiple profile data files (or files with
multiple histogram records) are read, the memory ranges of each pair of
histogram records must be either equal, or non-overlapping. For each
pair of histogram records, the resolution (memory region size divided by
the number of bins) must be the same. The time unit must be the same
for all histogram records. If the above containts are met, all
histograms for the same memory range are merged.
As each call graph record is read ('call_graph.c:cg_read_rec'), the
parent and child addresses are matched to symbol table entries, and a
call graph arc is created by 'cg_arcs.c:arc_add', unless the arc fails a
symspec check against INCL_ARCS/EXCL_ARCS. As each arc is added, a
linked list is maintained of the parent's child arcs, and of the child's
parent arcs. Both the child's call count and the arc's call count are
incremented by the record's call count.
Basic-block records are read ('basic_blocks.c:bb_read_rec'), but only
if line-by-line profiling has been selected. Each basic-block address
is matched to a corresponding line symbol in the symbol table, and an
entry made in the symbol's bb_addr and bb_calls arrays. Again, if
multiple basic-block records are present for the same address, the call
counts are cumulative.
A gmon.sum file is dumped, if requested ('gmon_io.c:gmon_out_write').
If histograms were present in the data files, assign them to symbols
('hist.c:hist_assign_samples') by iterating over all the sample bins and
assigning them to symbols. Since the symbol table is sorted in order of
ascending memory addresses, we can simple follow along in the symbol
table as we make our pass over the sample bins. This step includes a
symspec check against INCL_FLAT/EXCL_FLAT. Depending on the histogram
scale factor, a sample bin may span multiple symbols, in which case a
fraction of the sample count is allocated to each symbol, proportional
to the degree of overlap. This effect is rare for normal profiling, but
overlaps are more common during line-by-line profiling, and can cause
each of two adjacent lines to be credited with half a hit, for example.
If call graph data is present, 'cg_arcs.c:cg_assemble' is called.
First, if '-c' was specified, a machine-dependent routine ('find_call')
scans through each symbol's machine code, looking for subroutine call
instructions, and adding them to the call graph with a zero call count.
A topological sort is performed by depth-first numbering all the symbols
('cg_dfn.c:cg_dfn'), so that children are always numbered less than
their parents, then making a array of pointers into the symbol table and
sorting it into numerical order, which is reverse topological order
(children appear before parents). Cycles are also detected at this
point, all members of which are assigned the same topological number.
Two passes are now made through this sorted array of symbol pointers.
The first pass, from end to beginning (parents to children), computes
the fraction of child time to propagate to each parent and a print flag.
The print flag reflects symspec handling of INCL_GRAPH/EXCL_GRAPH, with
a parent's include or exclude (print or no print) property being
propagated to its children, unless they themselves explicitly appear in
INCL_GRAPH or EXCL_GRAPH. A second pass, from beginning to end (children
to parents) actually propagates the timings along the call graph,
subject to a check against INCL_TIME/EXCL_TIME. With the print flag,
fractions, and timings now stored in the symbol structures, the
topological sort array is now discarded, and a new array of pointers is
assembled, this time sorted by propagated time.
Finally, print the various outputs the user requested, which is now
fairly straightforward. The call graph ('cg_print.c:cg_print') and flat
profile ('hist.c:hist_print') are regurgitations of values already
computed. The annotated source listing
('basic_blocks.c:print_annotated_source') uses basic-block information,
if present, to label each line of code with call counts, otherwise only
the function call counts are presented.
The function ordering code is marginally well documented in the
source code itself ('cg_print.c'). Basically, the functions with the
most use and the most parents are placed first, followed by other
functions with the most use, followed by lower use functions, followed
by unused functions at the end.
Info Catalog
gprof: File Format
gprof: Details
gprof: Debugging