Call graph generation

Call graphs are very useful in understanding how a program works. Here are two ways to generate them.

Approach 1: Cygwin profiling interface

This approach assumes you have the source files and you use GCC.

GCC supports the Cygwin profiling interface. Put it simply, first, implement two functions

void __cyg_profile_func_enter(void *this_fn, void *call_site)

void __cyg_profile_func_exit(void *this_fn, void *call_site)

Then compile everything with -finstrument-functions compiler command-line options.

As an example, see N. Devillard's etrace on how to generate call graphs.

More examples: here and here

Approach 2: GDB break points

This approach does not need the source files because it works directly on executable binaries, and it works best when the binaries are not stripped. The idea comes from here.

The only issue with this approach is many functions could have been inlined during compilation and thus their information (symbolic references) will be missing.

This approach runs a GDB script which sets a break point at each function and parses the result to generate call graphs.

The first script genCallgraph.sh (adapted from Juan M. Bello Rivas's code) takes an executable binary and generates a series of caller-callee pairs. Then one can send this output to an awk script cg2dot.awk to generate a dot file which can be plotted using Graphviz.

The second script genCallgraphLocal.sh is a small variant of the first one. It only traces function calls within your executable binaries (because you are not interested in what's going on inside the dynamic libraries) as well as all system calls.

The third script genCallgraphLDSO.sh is designed to trace what's going on inside the runtime linker ld.so. It takes a dynamic executable binary and generates a series of caller-callee pairs within ld.so.

There are several showcases. The compile and runtime environment is Linux kernel version 2.6.34 (x86_64), GDB version 7.1, GCC version 4.5.0, unstrippped Glibc version 2.11.1 (some Linux distributions, such as Ubuntu version 10, ship stripped libc.so), GNU Binutils version 2.20.1.

Also make sure your GCC does not enable PIC by default. If so, please disable it by -no-pie. See this article for more details.

Showcase #1: Hello, World. Call graph and the dot file. Here one can see GCC's optimization of printf: It uses puts instead. More details here.
Some leaf nodes in the call graph have function names like syscall:foo, and this means the system call foo. This is to distinguish a function named foo and a bona fide system call foo. (GDB is capable of setting catch points on system calls.)
Showcase #2: If Hello, World's call graph is messy, we can look at a bare minimum program, i.e.
```
int main() {}
```
Its call graph and the dot file.
Showcase #3: Compile the bare minimum program using static linkage (-static compiler option) Its call graph and the dot file. Here one can see __libc_start_main will also call __libc_init_first to do additional initialization work.
One should also note that __do_global_ctors_aux will call init_cacheinfo defined in sysdeps/x86_64/cacheinfo.c. What it does is to obtain L1, L2, and L3 cache information.
Showcase #4: Hello, World in C++, i.e.
```
#include <iostream>

int main() {
  std::cout << "Hello, World" << std::endl;
}
```
For this one, we only want to trace the local function calls, otherwise, don't say I haven't warned you.
Using genCallgraphLocal.sh and a modified awk script cg2dotDemangle.awk which will demangle (the GCC-style) C++ names, the call graph and the dot file.
(GCC does its name mangling in gcc/cp/mangle.c)
In this call graph, one can see some dangling system calls, and this is because the genCallgraphLocal.sh script traces system calls as well, and these system calls are emitted from within the dynamic libraries, which genCallgraphLocal.sh ignore.
Showcase #5: The runtime linker ld.so. This is generated using the genCallgraphLDSO.sh script. Its call graph and the dot file. The output from genCallgraphLDSO.sh is first trimmed using the following command
```
egrep -v "(strchr|strcmp|strlen|strsep|malloc|calloc|memcpy|memmove|mempcpy|memalign|memset|free)"
```
beforing being sent to the awk script cg2dot.awk