Stack Size Estimator Documentation

Overview

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.

Usage

The script accepts two positional arguments: the path to the configuration JSON, and the path to the call graph JSON. The call graph JSON is the output of llvm-readelf --call-graph-info --stack-sizes --elf-output-style=JSON for a single linked ELF file.

python3 scripts/clang/stack_size_estimator/stack_estimator.py config.json callgraph.json

Configuration

The stack_estimator.py expects a configuration JSON file. The schema of config.json is as follows:

{
  "entry_functions": ["main", {"name": "task_entry", "address": 4096}],
  "exclude_functions": ["panic"]
}

• entry_functions: (Optional) A list of entry point functions to analyze. Defaults to ["main"] if not specified. Each is a function name, or a dictionary with a name and an address. Local functions in different translation units can have the same name; such functions must be given by address.
• 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.

Output

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,
      "is_lower_bound": false,
      "has_cycles": false,
      "uninstrumented_callees": []
    }
  ],
  "nodes": {
    "12345": {
      "name": "main",
      "stack": 64,
      "max_cumulative_stack": 1024,
      "sccId": 0,
      "direct": [12350, 12400],
      "indirect": [],
      "uninstrumented": []
    }
  },
  "cycles": [
    {
      "id": 1,
      "max_stack": 128,
      "nodes": [12350, 12360]
    }
  ]
}

is_lower_bound is true if the stack usage could be higher than max_stack_usage because a function reachable from the entry function:

• calls a function that has no call graph information (uninstrumented_callees). Calls to functions in other modules have callee address 0.

Architecture & Core Concepts

• Call Graph (CG): A directed graph where nodes represent functions and edges represent function calls (direct or indirect).
• Stack Usage: The amount of stack memory (in bytes) reserved by a function's stack frame.
• Strongly Connected Component (SCC): A subgraph where every vertex is reachable from every other vertex. In a call graph, SCCs represent recursive cycles.
• Condensation Graph: A Directed Acyclic Graph (DAG) derived by contracting each SCC into a single node.

The tool operates in three main phases:

1. Input Parsing & Graph Construction: Reads JSON input containing call graph info and stack sizes to build an in-memory graph.
2. Analysis: Calculates the maximum cumulative stack usage starting from configured entry points.
3. Reporting: Outputs the results as a structured JSON object to stdout.

1. Input Parsing

• Input Format: Expects a configuration JSON and a call graph JSON output from llvm-readelf --call-graph-info --stack-sizes --elf-output-style=JSON.
• Graph Construction:
  • Nodes are created for each function address.
  • Edges are added for direct calls and resolved indirect calls (using type ID mappings).
  • Stack sizes are associated with each node from the llvm-readelf data.

2. Analysis

The estimator calculates stack usage by handling recursion conservatively via Strongly Connected Components.

1. SCC Identification: Uses Tarjan's algorithm to identify all Strongly Connected Components (SCCs) in the call graph.
2. Condensation Graph: Builds a DAG where each node is an SCC.
3. Local Max: For each SCC, calculates the sum of stack usages of all functions within it (conservative maximum, except if SCC has cycles i.e. recurses, then the worst-case usage can't be bounded).
4. Path Calculation: Performs a bottom-up traversal (reverse topological sort) of the Condensation DAG.
   • MaxStack(SCC) = LocalStack(SCC) + Max(MaxStack(SuccessorSCCs))
5. Result: The path logic dictates the max stack usage reachable from the entry point's SCC.

3. Reporting

• JSON Output: Generates a structured JSON object containing a consolidated map of all analyzed nodes, a list of identified cycles, and summarized stack metrics for each configured entry function. This output is printed to stdout.

Data Structures

Internal Graph

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]]

Output Structure

The JSON output contains the following three main sections that provide the results of the analysis:

1. 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.
2. cycles: An array of objects detailing any detected strongly connected components (recursive cycles) reachable in the parsed call graph.
3. 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.

Key Algorithms

• Tarjan's Algorithm: For finding SCCs in $O(V+E)$. The depth-first search is iterative, so arbitrarily deep call chains are supported.
• Topological Sort: For processing the Condensation DAG in dependency order.