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.