Call graphs provide a nice simple tool for introducing a code base and provide basic data useful for directing efforts in revising software. Call graphs simply show the calling relation of a program. An edged from node foo to node bar represents a call to bar within the body of foo.

This document introduces a basic call graph generator, its use with standard C programs, and how it can be used to generate call graphs for TinyOS applications written in nesC.

Obtaining the Code

Call graphs are generated in two steps using a call_graph to extract raw call data from a C program and calls2dot.py to convert this call data into a dot formatted graph.

Software to Download
Building CIL

The call_graph uses CIL as a library to examine the program of interest. Download and build CIL 1.3.6 from the main CIL website as described on their "Installation" page. This is typically as easy as expanding the archive and then executing:

./configure
make
Building call_graph

Building the call_graph program requires updating CILPATH and INCDIRS in the call_graph project's Makefile to point to your CIL installation. The values of these will probably be similar to:

CILPATH = /home/username/cil
export LIBS = unix str cil
export INCDIRS = $(CILPATH)/obj/x86_LINUX

with CILPATH revised to reflect where you built CIL. The project can then be built using make.

Building calls2dot.py

This script is included in the call_graph.tgz tarball listed above and requires no configuration.

Basic Call Graph Generation

This call graph generator takes as input one or more preprocessed C programs and returns a dot file that can be converted into a graph using the Graphviz suite of tools.

Generating Preprocessed Code

Preprocessed output is generated from C source by passing the -E flag to gcc. Preprocessed files often use the dot i suffix. For example, the preprocessed version of a program that is normally compiled using:

gcc -c -Wall -pedantic foo.c -o foo.o
gcc -c -Wall -pedantic bar.c -o bar.o
gcc -c -Wall -pedantic foobar.c -o foobar.o
gcc -Wall -pedantic foo.o bar.o foobar.o -o foobar

can be generated with -E as follows:

gcc -E -Wall -pedantic foo.c -o foo.i
gcc -E -Wall -pedantic bar.c -o bar.i
gcc -E -Wall -pedantic foobar.c -o foobar.i

A make system can be revised to include a preprocessed target using a rule similar to:

preprocessed: $(SRCS:.c=.i)

%.i : %.c
    $(CC) -E $(CFLAGS) $(INCDIRS) $< -o $@

Generating a Call Graph

Call graph generation is accomplished in two steps. Raw call data is gathered using the call_graph utility. Raw call data is converted into the dot format using the calls2dot.py utility.

The call_graph program takes as input one or more preprocessed C files and for each call encountered in the program produces a line of output recording: if the call is made from an inlined function (true if the caller is inlined), the name of the calling function, and the name of the called function.

The calls2dot.py program takes as input a file consisting of lines in the format output by call_graph and generates as output a dot formatted representation of the call graph. The dot program included in Graphviz can then be used to generate the call graph:

gcc -E -Wall -pedantic foo.c -o foo.i
gcc -E -Wall -pedantic bar.c -o bar.i
gcc -E -Wall -pedantic foobar.c -o foobar.i
call_graph foo.i bar.i foobar.i > foobar_raw_calls.txt
calls2dot.py raw_calls.txt > foobar.dot
dot -Tps foobar.dot > foobar_callgraph.ps

TinyOS Call Graph Generation

The tools I use in my research were designed specifically for standard C source code. I also enjoy being able to easily peer into the internals of a system to understand that which I'm working with and to aid general hacking. I am fortunate in that many embedded systems are written using C and are implemented in a direct manner that aids understanding their internals.

TinyOS is not written in standard C and, in part due to nesting of configurations, hides some details that I wanted to understand for the hacking I had in mind. This document describes the procedure that I currently use to manipulate and understand TinyOS programs by bringing them back into standard C that can then be visualized using the call graph generation described above and manipulated using other C based tools.

Converting TinyOS Programs into Standard C

Moving to standard C is pretty easy if you're willing to take a few extra steps: - Compile the TinyOS project for the platform of you choice - Go look for the app.c file located in build/<platform> - Finish the preprocessing (at times nesC does not complete this) using the platform specific cpp command such as:

avr-cpp app.c app.i

Now we've got (ugly) C code with a few nesC specific (go go dollar sign separator power!) nuances. We can clean this up a fair bit using sed to remove line number information that the preprocessor included and replacing the rampaging dollar signs with an underscore:

sed -e '/^#.*/ d' -e 's/\$/_/g' < app.i > app.clean.i

Hope that you didn't have any valid dollar signs in your program before this point! Finish up by running your code through your favorite auto formatter. I'm a fan of the formatting performed by vi, although indent works okay if you find the correct combination of command line arguments.

At this point the program can be compiled using:

avr-gcc -mmcu=atmega128 -o app.clean.exe -Os <project specific includes or other directives> app.clean.i

Visualizing Call Graphs of TinyOS Programs

With the first hurtle behind us we can look ahead to the second challenge of understanding the program at hand. A look through the resulting app.clean.i produced above provides a lot of insight into how the nesC wiring language is implemented and exploited to produce efficient code. More detailed understanding of the resulting C code remains elusive.

One problem with TinyOS is understanding what is pulled into a program through different configurations. One great tool for visualizing this is the TinyOS plug-in for Eclipse. But formal program analysis often requires working directly with the C code, rather than the nesC used by Eclipse. And real coders use real editors like vi or, even better, ed. That writes Eclipse out of the solution.

TinyOS supports efficient nesting of configurations by aggressive inlining of wrapper functions. This allows an abstract interface to pass through multiple levels of wiring down to the real implementation, without needing to pay the cost of a function call for each traversal of a wiring level. Further, these hides many details that most users of TinyOS need not worry about. Unfortunately, for my research I often wish to see the subsystems that a high level call effects. Multiple layers of inlined function calls hinder quickly understanding this directly from the source code.

To this end I've threw together a call graph visualizer. This provides developers with an easy to understand call graph visualization of a program. A TinyOS specific mode collapses nodes of inlined functions to produce a much compressed visualization of the non-inlined function call graph of a program. The values of this latter view may be debated. The collapsed view obfuscates the significance of some inlined functions with large bodies, but the view also removes the "clutter" resulting from many inlined functions that simply wrap an underlying function call. I've found a combination of the collapsed view for high level understanding and the full view for detailed investigations helps me quickly isolate low layer TinyOS subsystems of interest to my work.

Call graphs for TinyOS programs are generated from the app.clean.i described in "Converting TinyOS Programs into Standard C". This preprocessed file can be passed directly to call_graph as described in "Generating a Call Graph".

The calls2dot.py program includes a TinyOS motivated —noinlines mode that replaces inlined function calls with any non-inlined function calls directly reachable from the inlined function or transitively reachable from a chain or inlined function calls originating from the inlined function.

Closing Notes

Please let me know if any requests for features, discovered rough edges, or flames.