The stack_estimator.py tool estimates the maximum stack usage of a program by analyzing its call graph and the stack frame size of individual functions.
The script accepts an optional --text flag (to print a human-readable summary instead of JSON), an optional path to the configuration JSON, and the path to the call graph JSON. The call graph JSON is the output of llvm-readelf --file-headers --dyn-symbols --notes --program-headers --call-graph-info --stack-sizes --elf-output-style=JSON for a single linked ELF file (--file-headers and --dyn-symbols are only needed when the configuration doesn't list entry_functions; --notes and --program-headers only for the symbolizer markup of --text). A relocatable object file is currently not supported by the analysis.
python3 scripts/clang/stack_size_estimator/stack_estimator.py [--text] [config.json] callgraph.json
The --text report names functions and gives their addresses as symbolizer markup ({{{pc:0x...}}}), preceded by the module's build ID and load segments. Pipe it through a markup filter, such as ffx debug symbolize in a Fuchsia checkout or llvm-symbolizer --filter-markup, to get source locations with full detail, including inlined frames.
Other tools can run the analysis without writing files: stack_estimator.estimate(config, data) takes the parsed configuration (or None for defaults) and llvm-readelf JSON, and returns the same dictionary that the script outputs as JSON. It raises ValueError for unsupported input, such as the call graph of a relocatable object file.
The stack_estimator.py accepts an optional configuration JSON file. The schema of config.json is as follows:
{ "entry_functions": ["main", {"name": "task_entry", "address": 4096}], "exclude_functions": ["panic"], "call_frame_overhead": 8 }
entry_functions: (Optional) A list of entry point functions to analyze. Each is a function name, or a dictionary with an address (and optional name). Local functions in different translation units can have the same name; such functions must be given by address. If omitted, the entry points are the ones the linked file declares itself: the ELF header entry point (ElfHeader.Entry) if it is non-zero, and the defined function symbols of the dynamic symbol table (DynamicSymbols), e.g. the functions that a shared library exports. It is an error if that set is empty.exclude_functions: (Optional) A list of functions to leave out of the analysis, each a function name, or a dictionary with an address (and a name, for the reader), as for entry_functions; a local function whose name is not unique is given by address. An excluded function is treated as using no stack, and calls to it are ignored, so excluding a function asserts that it is never reached in this configuration, for example a panic handler that never returns.call_frame_overhead: (Optional) The number of bytes that a call instruction pushes onto the stack, which is not included in the .stack_sizes frame size. Defaults to 8 for x86_64, 4 for i386, and 0 for other architectures, which pass the return address in a register.The standard output will be a JSON object containing the global graph nodes, detected recursive cycles, and a summary for each defined entry function:
{ // entry_functions is the main output of the analysis which provides the stack usage // data for each entry point provided by the config.json entry_functions list. "entry_functions": [ { "entry_function": "main", "scc_id": 0, "address": 12345, "max_stack_usage": 1024, "stack_usage_expression": "1024", "max_stack_path": [ {"address": 12345, "name": "main", "stack": 64}, {"address": 12400, "name": "process", "stack": 944} ], "is_lower_bound": false, "has_cycles": false, "cycles": [], "unknown_stack_sizes": [], "uninstrumented_callees": [], "unmatched_indirect_calls": [], "untyped_indirect_calls": [] } ], "nodes": { "12345": { "name": "main", "stack": 64, "max_cumulative_stack": 1024, "sccId": 0, "direct": [12350, 12400], "indirect": [], "uninstrumented": [], "unmatched_indirect": [], "untyped_indirect": 0 } }, "cycles": [ { "id": 1, "max_stack": 128, "nodes": [12350, 12360] } ], "call_frame_overhead": 8 }
max_stack_usage includes call_frame_overhead for each function on the path. On x86_64, the stack size of a function that makes no calls includes the 128-byte red zone below the stack pointer, which such a function may use without moving the stack pointer, and which .stack_sizes leaves out; the file doesn't say whether the function does, so the worst case is assumed. stack_usage_expression gives the maximum stack usage as an algebraic expression over the condensation DAG, keeping symbolic terms (frame(<name>) for functions with unknown frame size such as VLAs, calls(<name>) for uninstrumented callees, cycle(<members>) for recursive cycles, and indirect(<function>) for the indirect calls of a function whose targets are not all known) and pruning dominated path terms. max_stack_path lists the functions on the path with the maximum stack usage, in call order, with their stack sizes; all functions of a recursive cycle on the path are listed, since all of their stack sizes are counted. is_lower_bound is true if the stack usage could be higher than max_stack_usage because a function reachable from the entry function:
cycles, has_cycles). Each function of a recursive cycle is counted once.unknown_stack_sizes), and is counted as 0. Clang omits stack sizes for functions with dynamically sized stack objects. A function's entry is the one at its address.uninstrumented_callees). Calls to functions in other modules have callee address 0.unmatched_indirect_calls, each with the caller and the type_id). Unless the call graph is incomplete, such a call is dead code that the compiler could not fold away, for example a call through a function pointer that is always null behind a runtime check. dead_unmatched_indirect_calls in the configuration declares such calls dead, so that they count as no call: true for the whole file, or a list of functions in the form of exclude_functions for the unmatched indirect calls of those functions only.untyped_indirect_calls, the callers), or makes an indirect call while there are potential indirect call targets of unknown type (unknown_type_indirect_targets), which any indirect call might reach.The tool operates in three main phases:
llvm-readelf --call-graph-info --stack-sizes --elf-output-style=JSON.llvm-readelf data. On x86_64, a function that makes no calls gets the 128-byte red zone added, since .stack_sizes doesn't count it.The estimator calculates stack usage by handling recursion conservatively via Strongly Connected Components.
MaxStack(SCC) = LocalStack(SCC) + Max(MaxStack(SuccessorSCCs))stdout.The Graph class (in graph.py) uses an adjacency list representation, which keeps the vertices in insertion order so that the results are reproducible:
class Graph: graph: Dict[Address, List[Address]]
The JSON output contains the following three main sections that provide the results of the analysis:
entry_functions: An array containing max stack usage metrics and cycle detection flags for each entry point defined in config.json. This is the primary result of the tool to consult for a program's overall stack usage.cycles: An array of objects detailing any detected strongly connected components (recursive cycles) reachable in the parsed call graph.nodes: A dictionary containing structural call graph info directly (direct and indirect calls) along with the calculated max cumulative stack metric per function in the graph. Functions are identified by address and name; a consumer that wants source locations can symbolize the addresses.