Whole program static stack analysis
cargo-call-stackStatic, whole program stack usage analyzer
Other examples: Embedded CoAP / IPv4 server (source) "Hello, world!"
HEADS UP: This tool relies on an experimental feature (-Z stack-sizes)
and implementation details of rustc (like symbol mangling) and could stop
working with a nightly toolchain at any time. You have been warned! Last tested nightly: 2023-11-13.
NOTE: This tool main use case are embedded (microcontroller) programs that lack, or have very
little, indirect function calls and recursion. This tool is of very limited use -- specially its
stack usage analysis -- on programs that link to the standard library as even the smallest program
that links to the standard library will contain a large number of indirect function calls (like
trait object dynamic dispatch specially in core::fmt) and potential recursion (specially in
panicking branches).
A start point can be specified to analyze only the call graph that begins at that function.
Each node (function) in the call graph includes the local stack usage of the
function, if available (see -Z emit-stack-sizes).
The maximum stack usage of each function is also computed, or at least a lower bound is provided. Maximum stack usage of a function here refers to the stack usage that includes the stack used by functions that the function may invoke.
The tool has imperfect support for calls through function pointers (fn())
and dynamic dispatch (dyn Trait). You will get a call graph from programs
that do indirect calls but it will likely be missing edges or contain
incorrect edges. It's best to use this tool on programs that only do direct
function calls.
$ # NOTE always use the latest stable release
$ cargo +stable install cargo-call-stack
$ rustup +nightly component add rust-srcNOTE this tool requires that your Cargo project is configured to use fat LTO when Cargo uses the release profile. This is not the default configuration (as of Rust 1.63) so you'll need to add this to your
Cargo.toml:
[profile.release]
# `lto = true` should also work
lto = 'fat'The tool builds your program in release mode with LTO enabled, analyses it and
then prints a dot file to stdout. See cargo call-stack -h for a list of build
options (e.g. --features).
NOTE if you have not set a compilation target in e.g.
.cargo/config.tomlthen you'll need to pass the--targetflag tocargo-call-stackeven if you are not cross compiling
NOTE the analysis corresponds to the newly produced binary, which won't be the same as the binary produced by
cargo +nightly build --release
$ cargo +nightly call-stack --example app > cg.dot
warning: assuming that llvm_asm!("") does *not* use the stack
warning: assuming that llvm_asm!("") does *not* use the stackGraphviz's dot can then be used to generate an image from this dot file.
$ dot -Tsvg cg.dot > cg.svgEach node in this graph represents a function, which could be a free function,
an inherent method or a trait method. Each directed edge indicates a "calls"
relationship. For example, in the above graph Reset calls both main and
DefaultPreInit.
Each node also contains its local stack usage in bytes and its max-imum
stack usage, also in bytes. The maximum stack usage includes the stack usage of
all the other functions that the function could invoke.
This is the no_std program used to generate the call graph shown above.
…In the previous example the call graph contained disconnected subgraphs. The reason for that is exceptions (also known as interrupts).
SysTick, for example, is an exception handler that can preempt any function called fromReset. This exception handler is never called from software but can be invoked by the hardware at any time. These exception handlers can appear as the roots of disconnected subgraphs.
In some cases you may be interested in the maximum stack usage of a particular function. The tool lets you specify a start point which will be used to filter the call graph to only include nodes reachable from that function.
If we invoke the tool on the previous program but select main as the start
point we get this call graph:
$ cargo +nightly call-stack --example app main > cg.dot
warning: assuming that llvm_asm!("") does *not* use the stack
warning: assuming that llvm_asm!("") does *not* use the stackNotice that SysTick and baz don't appear in this call graph since they are
not reachable from main.
The tool can, in some cases, compute the maximum stack usage of programs that involve recursion. Recursion appears as cycles in the call graph. Consider the following example:
…It produces the following call graph:
The functions foo, bar and baz use zero stack space thus the cycle formed
by them also uses zero stack space. In this particular case the maximum stack
usage of main can be computed.
For the curious this is the disassembly of the "cyclic" program:
…And yes, the estimated maximum stack usage is correct as shown in this debug session:
…NOTE as of ~nightly-2022-09-20 there's no distinction between function pointers and trait objects at the llvm-ir so the analysis can insert an edge from a dynamic dispatch call site (caller) to a regular function (callee)
In some cases the tool can produce correct call graphs for programs that use trait objects -- more details about where and how it fails in the "Known limitations" section. Here's an example:
…The tool produces the following call graph:
Here i1 ({}*) denotes dynamic dispatch of a method with (Rust) signature
fn(&[mut] self) -> bool. The dynamic dispatch can invoke either Bar.foo,
which boils down to the default method implementation (app::Foo::foo in the
graph), or Baz.foo (::foo in the graph). In this case
the tool does not a draw an edge between i1 ({}*) and Quux::foo, whose
signature is also fn(&self) -> bool, so the call graph is accurate.
If you are wondering why we use LLVM notation for the function signature of the
trait method: that's because the tool operates on LLVM-IR where there's no
bool primitive and most of Rust's type information has been erased.
NOTE as of ~nightly-2022-09-20 llvm discards type information associated to pointers and uses opaque pointers in llvm-ir so functions whose signature include references (and raw pointers) will include more callee edges that will never occur in practice.
In some cases the tool can produce correct call graphs for programs that
invoke functions via pointers (e.g. fn()). Here's an example:
…The tool produces the following call graph:
The node i1 ()* represents a call via function pointer -- the LLVM type i1 ()* is equivalent to Rust's fn() -> bool. This indirect call could invoke
foo or bar, the only functions with signature fn() -> bool.
To reason about indirect function calls the tool uses the type information available in the LLVM-IR of the program. This information does not exactly match Rust's type information and leads to mislabeling of functions. For example, consider this program:
…The tool produces the following call graph:
Note that the node that represents the indirect function call has type i32 ()*
(fn() -> i32), not u32 ()*. The reason is that there's no u32 type in
LLVM, there are only signed integers. This leads the tool to wrongly add an edge
between i32 ()* and baz. If the tool had Rust's type information then this
edge would have not been added.
As of ~nightly-2022-09-20 llvm is discarding type information associated to pointers and instead
using opaque pointers (ptr) in llvm-ir.
This results in even greater loss of type information, for example:
fn f(x: &i32) -> bool becomes fn(ptr) -> i1 in llvm-irimpl Foo { fn f(&self) -> bool } also becomes fn(ptr) -> i1 in llvm-irso the two are callee candidates for both a function pointer call with signature fn(&T) -> bool
and for dynamic dispatch of a method with signature fn(&self) -> bool
Inline assembly breaks LLVM's stack usage analysis.
LLVM does not consider inline assembly in its analysis and reports an incorrect number.
In this case, cargo-call-stack will use its own stack usage analysis based on machine code, which only supports the ARM Cortex-M architecture.
Hardware exceptions, like SysTick on Cortex-M devices, appear as disconnected nodes in the call graph.
At the moment, cargo-call-stack cannot compute the whole program maximum stack usage when exceptions are present.
The tool only supports ELF binaries because -Z emit-stack-sizes only supports the ELF format.
Licensed under either of
at your option.
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.
No open issues yet, or sync has not completed.