toolchainguru

I've revised my "C Calltrees in Bash" tool, primarily to make it more efficient at discovering the call associations between many functions. ("call graph" (i.e. "relate N functions") used to be based on an O(N^2) application of "call_tree" (i.e. "relate 2 functions"); I realized there was a simple way to make "call_graph" O(N) and eliminate the need for "call_tree" at the same time.)

Passing args vs. piping to the shell functions is handled more consistently now.

There's a new "upndown" wrapper to generate a graph of all of a function's callers AND callees...

And there's an experimental method for generating a subgraph of all C functions that refer to a particular variable. (Not particularly useful for a variable with a name like "i".) For a certain class of globals, it might be a little useful.

Here 'tis:

#!/bin/bash

echo calltree.sh

#use cscope to build reference files (./cscope.out by default, use set_graphdb to override name or location)
set_graphdb(){exportGRAPHDB=1ドル; }
unset_graphdb(){unsetGRAPHDB; }
build_graphdb(){ cscope -bkRu ${GRAPHDB:+-f $GRAPHDB}&&echo Created ${GRAPHDB:-cscope.out}...; }

# cscope queries
lsyms(){ cscope ${GRAPHDB:+-f $GRAPHDB} -L0 1ドル|grep -v "<global>"|grep"="; }
fdefine(){ cscope ${GRAPHDB:+-f $GRAPHDB} -L1 1ドル; }
callees(){ cscope ${GRAPHDB:+-f $GRAPHDB} -L2 1ドル; }
callers(){ cscope ${GRAPHDB:+-f $GRAPHDB} -L3 1ドル; }

# show which functions refer to a set of symbols
filter_syms(){localsymcscope_line
whileread -a sym; do
 lsyms $sym|whileread -a cscope_line; do
printf"${cscope_line[1]}\n"
done
done
}

# given a set of function names, find out how they're related
filter_edges(){localsymcscope_line
whileread -a sym; do
 fdefine $sym|whileread -a cscope_line; do
grep -wq ${cscope_line[1]}${1:-<(echo)}&&
printf"${cscope_line[1]}\t[href=\"${cscope_line[0]}:${cscope_line[2]}\"]\t/*fdefine*/\n"
done
 callees $sym|whileread -a cscope_line; do
grep -wq ${cscope_line[1]}${1:-<(echo)}&&
printf"$sym->${cscope_line[1]}\t[label=\"${cscope_line[0]}:${cscope_line[2]}\"]\t/*callee*/\n"
done
 callers $sym|whileread -a cscope_line; do
grep -wq ${cscope_line[1]}${1:-<(echo)}&&
printf"${cscope_line[1]}->$sym\t[label=\"${cscope_line[0]}:${cscope_line[2]}\"]\t/*caller*/\n"
done
done
}

# dump args one-per-line
largs(){for a; doecho$a; done; }
toargs(){localsymbol
whileread -a symbol; do
printf"%s "$symbol
done
echo
}

# present list of symbols to filter_syms properly
refs(){localtfile=/tmp/refs.$RANDOM
cat${1:+<(largs $@)}>$tfile
 filter_syms $tfile<$tfile|sort -u
rm$tfile
}

# present list of function names to filter_edges properly
edges(){localtfile=/tmp/edges.$RANDOM
cat${1:+<(largs $@)}>$tfile
 filter_edges $tfile<$tfile
rm$tfile
}

# append unknown symbol names out of lines of cscope output
filter_cscope_lines(){localcscope_line
whileread -a cscope_line; do
grep -wq ${cscope_line[1]}${1:-/dev/null}||echo${cscope_line[1]}
done
}

# given a set of function names piped in, help spit out all their callers or callees that aren't already in the set
descend(){localsymbol
whileread -a symbol; do
1ドル$symbol| filter_cscope_lines 2ドル
done
}

# discover functions upstream of initial set
all_callers(){localtfile=/tmp/all_callers.$RANDOM
cat${1:+<(largs $@)}>$tfile
 descend callers $tfile<$tfile>>$tfile
cat$tfile; rm$tfile
}

# discover functions downstream of initial set
all_callees(){localtfile=/tmp/all_callees.$RANDOM
cat${1:+<(largs $@)}>$tfile
 descend callees $tfile<$tfile>>$tfile
cat$tfile; rm$tfile
}

# all the ways to get from (a,b,...z) to (a,b,...z), i.e. intersect all_callers and all_callees of initial set
call_graph(){localtfile=/tmp/subgraph.$RANDOM; localargs=/tmp/subgraph_args.$RANDOM
cat${1:+<(largs $@)}>$args
cat$args| all_callers |sort -u >$tfile
comm -12 $tfile<(cat$args| all_callees |sort -u)
rm$tfile$args
}

# all functions downstream of callers of argument
all_callerees(){ callers 1ドル| filter_cscope_lines | all_callees; }

# odd experimental set of calls that might help spot potential memory leaks
call_leaks(){localtfile=/tmp/graph_filter.$RANDOM
 all_callerees 1ドル|sort -u >$tfile
comm -2 $tfile<(all_callers 2ドル|sort -u)
rm$tfile
}

# wrap dot-format node and edge info with dot-format whole-graph description
graph(){printf"digraph iftree {\ngraph [rankdir=LR, ratio=compress, concentrate=true];\nnode [shape=record, style=filled]\nedge [color="navy"];\n"; cat|sort -u; printf"}\n"; }

# filter out unwanted (as specified in “~/calltree.deny”) and/or unnecessary edges
graph_filter(){localtfile=/tmp/graph_filter.$RANDOM
cat>$tfile
grep fdefine $tfile
grep1ドル$tfile|grep -vf ~/calltree.deny |cut -f1,3
rm$tfile
}

# how to invoke zgrviewer as a viewer
zgrviewer(){ ~/bin/zgrviewer -Pdot $@; }
# how to invoke xfig as a viewer
figviewer(){ xfig <(dot -Tfig $@); }
# how to create and view a png image
pngviewer(){ dot -Tpng $@ -o /tmp/ct.png && gqview -t /tmp/ct.png; }

# specify a viewer
ctviewer(){ pngviewer $@; }

# add color to specified nodes
colornodes(){(cat; for x in$@; doecho"$x [color=red]"; done;)}

# generate dot files
_upstream(){ all_callers 1ドル| edges | graph_filter ${2:-caller}| colornodes 1ドル| graph; }
_downstream(){ all_callees 1ドル| edges | graph_filter ${2:-callee}| colornodes 1ドル| graph; }
_upndown(){(all_callers 1ドル; all_callees 1ドル)| edges | graph_filter ${2:-callee}| colornodes 1ドル| graph; }
_relate(){ call_graph $@| edges | graph_filter callee | colornodes $@| graph; }
_leaks(){ call_leaks 1ドル2ドル| edges | graph_filter ${3:-callee}| colornodes 1ドル2ドル| graph; }

# generate dot files and invoke ctviewer
upstream(){ _upstream $@> /tmp/tfile; ctviewer /tmp/tfile; rm -f /tmp/tfile; }
downstream(){ _downstream $@> /tmp/tfile; ctviewer /tmp/tfile; rm -f /tmp/tfile; }
upndown(){ _upndown $@> /tmp/tfile; ctviewer /tmp/tfile; rm -f /tmp/tfile; }
relate(){ _relate $@> /tmp/tfile; ctviewer /tmp/tfile; rm -f /tmp/tfile; }
leaks(){ _leaks $@> /tmp/tfile; ctviewer /tmp/tfile; rm -f /tmp/tfile; }

# dot file conversions
dot2png(){ dot -s36 -Tpng -o 1ドル; }
dot2jpg(){ dot -Tjpg -o 1ドル; }
dot2html(){ dot -Tpng -o 1ドル.png -Tcmapx -o 1ドル.map; (echo"<IMG SRC="1ドル.png" USEMAP="#iftree" />"; cat1ドル.map)>1ドル.html; }

(Note to self: Code formatted via kdevelop, "File" -> "export to html")

Ahmed Aldebrn Fasih said...

Mac OS X users: first "touch ~/calltree.deny" and then change "grep -vf ~/calltree.deny" to "grep -v ~/calltree.deny" (remove the "f" flag). Both cscope and graphviz were easily installed using Homebrew. Downloaded the 3.9 Linux kernel, and after running cscope in the kernel/ directory, the following command produces a nice PNG:

_upstream relay_free_page_array | tee graph.dot | dot2png graph.png

May 10, 2013 at 10:25 PM

Ahmed Aldebrn Fasih said...

Jason, what's the license on this code? I've made some extensions and would like to throw it up on public version control.

May 13, 2013 at 9:32 AM

Julien Lamarche said...

Which function do you actually call to get this thing going? I only see an echo and then function definitions.

August 16, 2016 at 8:15 PM

Anonymous said...

Very useful script, thanks for sharing
Lorenzo

January 18, 2017 at 5:21 AM

Lorena said...

Thank yyou for writing this

June 25, 2024 at 2:52 AM