diff options
Diffstat (limited to 'build-aux')
| -rwxr-xr-x | build-aux/embed-sources.h.gen | 8 | ||||
| -rwxr-xr-x | build-aux/gcov-prune | 33 | ||||
| -rwxr-xr-x | build-aux/lint-bin | 149 | ||||
| -rwxr-xr-x | build-aux/lint-src | 160 | ||||
| -rwxr-xr-x | build-aux/linux-errno.txt.gen | 17 | ||||
| -rw-r--r-- | build-aux/measurestack/__init__.py | 38 | ||||
| -rw-r--r-- | build-aux/measurestack/analyze.py | 605 | ||||
| -rw-r--r-- | build-aux/measurestack/app_main.py | 129 | ||||
| -rw-r--r-- | build-aux/measurestack/app_output.py | 157 | ||||
| -rw-r--r-- | build-aux/measurestack/app_plugins.py | 915 | ||||
| -rw-r--r-- | build-aux/measurestack/test_analyze.py | 81 | ||||
| -rw-r--r-- | build-aux/measurestack/test_app_output.py | 52 | ||||
| -rw-r--r-- | build-aux/measurestack/testutil.py | 134 | ||||
| -rw-r--r-- | build-aux/measurestack/util.py | 133 | ||||
| -rw-r--r-- | build-aux/measurestack/vcg.py | 97 | ||||
| -rw-r--r-- | build-aux/requirements.txt | 11 | ||||
| -rwxr-xr-x | build-aux/stack.c.gen | 17 | ||||
| -rw-r--r-- | build-aux/stack.py | 184 | ||||
| -rwxr-xr-x | build-aux/stack.sh | 2 | ||||
| -rwxr-xr-x | build-aux/tent-graph | 180 | ||||
| -rwxr-xr-x | build-aux/valgrind | 16 |
21 files changed, 2905 insertions, 213 deletions
diff --git a/build-aux/embed-sources.h.gen b/build-aux/embed-sources.h.gen index 0ba6457..ee9eb42 100755 --- a/build-aux/embed-sources.h.gen +++ b/build-aux/embed-sources.h.gen @@ -1,10 +1,10 @@ #!/bin/sh -# embed-sources.h.gen - Generate C definitions for GNU `ld -r -b binary` files +# build-aux/embed-sources.h.gen - Generate C definitions for GNU `ld -r -b binary` files # -# Copyright (C) 2024 Luke T. Shumaker <lukeshu@lukeshu.com> +# Copyright (C) 2024-2025 Luke T. Shumaker <lukeshu@lukeshu.com> # SPDX-License-Identifier: AGPL-3.0-or-later nm --format=posix "$@" | sed -n -E \ - -e 's/(.*_(end|start)) D .*/extern char \1[];/p' \ - -e 's/(.*_size) A .*/extern size_t \1;/p' + -e 's/(.*_(end|start)) [DR] .*/extern char \1[];/p' \ + -e 's/(.*_size) A .*/extern size_t \1;/p' diff --git a/build-aux/gcov-prune b/build-aux/gcov-prune new file mode 100755 index 0000000..dc190a9 --- /dev/null +++ b/build-aux/gcov-prune @@ -0,0 +1,33 @@ +#!/usr/bin/env bash +# build-aux/gcov-prune - Prune old GCC coverage files +# +# Copyright (C) 2025 Luke T. Shumaker <lukeshu@lukeshu.com> +# SPDX-License-Identifier: AGPL-3.0-or-later + +set -e + +[[ $# == 1 ]] + +sourcedir="$(realpath -- .)" +builddir="$(realpath -- "$1")" + +# `gcc` writes .gcno +# Running the program writes .gcda (updates existing files, concurrent-safe) +# GCC `gcov` post-processes .gcno+.gcda to .gcov +# `gcovr` is a Python script that calls `gcov` and merges and post-processes the .gcov files to other formats + +# Prune orphaned .gcno files. +find "$builddir" -name '*.gcno' -printf '%P\0' | while read -d '' -r gcno_file; do + rel_base="${gcno_file%/CMakeFiles/*}" + src_file="$gcno_file" + src_file="${src_file#*/CMakeFiles/*.dir/}" + src_file="${src_file%.gcno}" + src_file="${src_file//__/..}" + src_file="$rel_base/$src_file" + if [[ ! -e "$sourcedir/$src_file" || "$sourcedir/$src_file" -nt "$builddir/$gcno_file" ]]; then + rm -fv -- "$builddir/$gcno_file" + fi +done + +# Prune all .gcda files. +find "$builddir" -name '*.gcda' -delete diff --git a/build-aux/lint-bin b/build-aux/lint-bin new file mode 100755 index 0000000..3b9eb4b --- /dev/null +++ b/build-aux/lint-bin @@ -0,0 +1,149 @@ +#!/usr/bin/env bash +# build-aux/lint-bin - Lint final binary images +# +# Copyright (C) 2025 Luke T. Shumaker <lukeshu@lukeshu.com> +# SPDX-License-Identifier: AGPL-3.0-or-later + +set -euE -o pipefail +shopt -s extglob + +# There are several exisi files we can use: +# +# Binaries: +# - ${elf} : firmware image with debug symbols and relocationd data +# - ${elf%.elf}.bin : raw firmware image +# - ${elf%.elf}.hex : .bin as Intel HEX +# - ${elf%.elf}.uf2 : .bin as USB Flashing Format (UF2) +# +# Textual info: +# - ${elf%.elf}.dis : `objdump --section-headers ${elf}; objdump --disassemble ${elf}; picotool coprodis --quiet ${elf}` +# - ${elf}.map : `ld --print-map` info +# - stack.c : `stack.c.gen` + +RED=$(tput setaf 1) +RESET=$(tput sgr0) + +err() { + printf "${RED}%s${RESET}: %s\n" "$1" "$2" >&2 + r=1 +} + +# Input is `ld --print-map` format. +# +# Output is a series of lines in the format "symbol location size +# source". Whitespace may seem silly. +objdump_globals() { + sed -E -n '/^ \.t?(data|bss)\./{ / 0x/{ p; D; }; N; s/\n/ /; p; }' <"$1" +} + +readelf_funcs() { + local in_elffile + in_elffile=$1 + + readelf --syms --wide -- "$in_elffile" | + awk '$4 == "FUNC" { print $8 }' +} + +lint_globals() { + local in_mapfile + in_mapfile=$1 + + local rel_base + rel_base=${in_mapfile#build/*/} + rel_base=${rel_base%/*} + + local topdir + topdir=$PWD + + { + echo 'Source Symbol Size' + objdump_globals "$in_mapfile" | + { + cd "$rel_base" + total=0 + while read -r symbol addr size source; do + if ((addr == 0)); then + continue + fi + case "$source" in + /*) + # libg.a(whatever.o) -> libg.a + source="${source%(*)}" + # resolve `..` components + source="$(realpath --canonicalize-missing --no-symlinks -- "$source")" + ;; + CMakeFiles/*.dir/*.@(obj|o)) + # CMakeFiles/sbc_harnes_objs.dir/... + source="${source#CMakeFiles/*.dir/}" + source="${source%.@(obj|o)}" + source="${source//__/..}" + source="$(realpath --canonicalize-missing --no-symlinks --relative-to="$topdir" -- "$source")" + ;; + esac + printf "%s %s 0x%04x (%'d)\n" "$source" "$symbol" "$size" "$size" + total=$((total + size)) + done + printf "~ Total 0x%04x (%'d)\n" "$total" "$total" + } | + LC_COLLATE=C sort + } | column -t +} + +lint_stack() { + local in_elffile + in_elffile=$1 + + IFS='' + while read -r line; do + func=${line#$'\t'} + if [[ $line == $'\t'* ]]; then + err "$in_elffile" "function in binary but not stack.c: ${func}" + else + err "$in_elffile" "function in stack.c but not binary: ${func}" + fi + done < <( + comm -3 \ + <(sed -En 's/^included: (.*:)?//p' "${in_elffile%/*}/stack.c" | sort -u) \ + <(readelf_funcs "$in_elffile" | sed -E -e 's/\.part\.[0-9]*$//' -e 's/^__(.*)_veneer$/\1/' | sort -u) + ) +} + +lint_func_blocklist() { + local in_elffile + in_elffile=$1 + + local blocklist=( + gpio_default_irq_handler + {,__wrap,weak_raw_,stdio_,_}{,v}{,sn}printf + ) + + while read -r func; do + err "$in_elffile" "Contains blocklisted function: ${func}" + done < <(readelf --syms --wide -- "$in_elffile" | + awk '$4 == "FUNC" { print $8 }' | + grep -Fx "${blocklist[@]/#/-e}") +} + +main() { + r=0 + + local elf + for elf in "$@"; do + { + echo 'Global variables:' + lint_globals "${elf}.map" | sed 's/^/ /' + echo + heap=$(grep -B1 'HeapLimit =' -- "${elf}.map" | + sed -E -e 's/^\s*(\.heap\s*)?0x/0x/' -e 's/\s.*//' | + sed -E -e '1{N;s/(.*)\n(.*)/\2-\1/;}' -e 's/.*/print(&)/' | + python) + printf "Left for heap: 0x%04x (%'d)\n" "$heap" "$heap" + } >"${elf%.elf}.lint.globals" + (lint_stack "$elf") &>"${elf%.elf}.lint.stack" + lint_func_blocklist "$elf" + done + + return $r +} + +main "$@" diff --git a/build-aux/lint-src b/build-aux/lint-src new file mode 100755 index 0000000..d536631 --- /dev/null +++ b/build-aux/lint-src @@ -0,0 +1,160 @@ +#!/usr/bin/env bash +# build-aux/lint-src - Lint checks for source files +# +# Copyright (C) 2024-2025 Luke T. Shumaker <lukeshu@lukeshu.com> +# SPDX-License-Identifier: AGPL-3.0-or-later + +RED=$(tput setaf 1) +RESET=$(tput sgr0) + +err() { + printf "${RED}%s${RESET}: %s\n" "$1" "$2" >&2 + r=1 +} + +# `get-dscname FILENAME` reads FILENAME and prints the name that the +# comment at the top of the file self-identifies the file as. +get-dscname() { + if [[ $1 == */Documentation/* && "$(sed 1q -- "$1")" == 'NAME' ]]; then + sed -n ' + 2{ + s,/,_,g; + s,^\s*_,Documentation/,; + s,$,.txt,; + + p; + q; + } + ' -- "$1" + else + sed -n ' + 1,3{ + /^\#!/d; + /^<!--$/d; + /-\*- .* -\*-/d; + s,[/*\# ]*,,; + s/ - .*//; + + p; + q; + } + ' -- "$1" + fi +} + +{ + filetype=$1 + filenames=("${@:2}") + + r=0 + for filename in "${filenames[@]}"; do + # File header ########################################################## + + shebang="$(sed -n '1{/^#!/p;}' "$filename")" + if [[ -x $filename && (-z $shebang || $shebang == '#!/hint/'*) ]]; then + err "$filename" 'is executable but does not have a shebang' + elif [[ (-n $shebang && $shebang != '#!/hint/'*) && ! -x $filename ]]; then + err "$filename" 'has a shebang but is not executable' + fi + case "$shebang" in + '') : ;; + '#!/bin/sh') : ;; + '#!/usr/bin/env bash') : ;; + '#!/usr/bin/env python3') : ;; + *) err "$filename" 'has an unrecognized shebang' ;; + esac + if [[ -n $shebang && $shebang != */"$filetype" && $shebang != *' '"$filetype" ]]; then + err "$filename" "wrong shebang for $filetype" + fi + + if ! grep -E -q 'Copyright \(C\) 202[4-9]((-|, )202[5-9])* Luke T. Shumaker' "$filename"; then + err "$filename" 'is missing a copyright statement' + fi + if test -e .git && ! git diff --quiet milestone/2025-01-01 HEAD -- "$filename"; then + if ! grep -E -q 'Copyright \(C\) .*2025 Luke T. Shumaker' "$filename"; then + err "$filename" 'has an outdated copyright statement' + fi + fi + if ! grep -q '\sSPDX-License-Identifier[:] ' "$filename"; then + err "$filename" 'is missing an SPDX-License-Identifier' + fi + + dscname_act=$(get-dscname "$filename") + dscname_exp=$(echo "$filename" | sed \ + -e 's,.*include/,,' \ + -e 's,.*static/,,' \ + -e 's/\.wip$//') + if [[ $dscname_act != "$dscname_exp" ]]; then + err "$filename" "self-identifies as $dscname_act (expected $dscname_exp)" + fi + + # File body ############################################################ + + if grep -n --color=auto $'\\S\t' "$filename"; then + err "$filename" 'uses tabs for alignment' + fi + done + case "$filetype" in + unknown) + for filename in "${filenames[@]}"; do + err "$filename" 'cannot lint unknown file type' + done + ;; + c) + for filename in "${filenames[@]}"; do + if [[ $filename == *.h ]]; then + dscname=$(get-dscname "$filename") + guard=$dscname + guard=${guard#*/config/} + if [[ $guard == */config.h ]]; then + guard=config.h + fi + guard=${guard//'/'/'_'} + guard=${guard//'.'/'_'} + guard="_${guard^^}_" + if ! { grep -Fxq "#ifndef ${guard}" "$filename" && + grep -Fxq "#define ${guard}" "$filename" && + grep -Fxq "#endif /* ${guard} */" "$filename"; }; then + err "$filename" "does not have ${guard} guard" + fi + if [[ $filename != libmisc/include/libmisc/obj.h ]] && + grep -Fn --color=auto -e LO_IMPLEMENTATION_C -e LO_IMPLEMENTATION_STATIC "$filename"; then + err "$filename" "contains LO_IMPLEMENTATION_C and/or LO_IMPLEMENTATION_STATIC" + fi + fi + if [[ $filename == *.c ]]; then + if [[ $filename != libmisc/tests/test_obj.c ]] && + grep -Fn --color=auto L_IMPLEMENTATION_H "$filename"; then + err "$filename" "contains LO_IMPLEMENTATION_H" + fi + fi + done + ;; + sh | bash) + shellcheck "${filenames[@]}" || exit $? + shfmt --diff --case-indent --simplify "${filenames[@]}" || exit $? + ;; + python3) + ./build-aux/venv/bin/mypy --strict --scripts-are-modules "${filenames[@]}" || exit $? + ./build-aux/venv/bin/black --check "${filenames[@]}" || exit $? + ./build-aux/venv/bin/isort --check "${filenames[@]}" || exit $? + ./build-aux/venv/bin/pylint "${filenames[@]}" || exit $? + if grep -nh 'SPECIAL$$' -- lib9p/core.gen lib9p/core_gen/*.py; then exit 1; fi + testfiles=() + for filename in "${filenames[@]}"; do + if [[ ${filename##*/} == test_*.py ]]; then + testfiles+=("$filename") + fi + done + ./build-aux/venv/bin/pytest "${testfiles[@]}" || exit $? + ;; + make | cmake | gitignore | ini | 9p-idl | 9p-log | markdown | pip | man-cat) + # TODO: Write/adopt linters for these file types + : + ;; + *) + err "$0" "unknown filetype: ${filetype}" + ;; + esac + exit $r +} diff --git a/build-aux/linux-errno.txt.gen b/build-aux/linux-errno.txt.gen deleted file mode 100755 index f94178f..0000000 --- a/build-aux/linux-errno.txt.gen +++ /dev/null @@ -1,17 +0,0 @@ -#!/usr/bin/env bash -# build-aux/linux-errno.txt.gen - Generate a listing of Linux kernel errnos -# -# Copyright (C) 2024 Luke T. Shumaker <lukeshu@lukeshu.com> -# SPDX-License-Identifier: AGPL-3.0-or-later - -set -e -linux_git=${1:?} -outfile=${2:?} - -( - cd "${linux_git}" - echo "# ${outfile} - Generated from $0 and linux.git $(git describe). DO NOT EDIT!" - git ls-files include/uapi/ | grep errno | - xargs sed -nE 's,#\s*define\s+(E[A-Z0-9]+)\s+([0-9]+)\s+/\* (.*) \*/,\2 \1 \3,p' | - sort --numeric-sort -) >"${outfile}" diff --git a/build-aux/measurestack/__init__.py b/build-aux/measurestack/__init__.py new file mode 100644 index 0000000..c1b9d7f --- /dev/null +++ b/build-aux/measurestack/__init__.py @@ -0,0 +1,38 @@ +# build-aux/measurestack/__init__.py - Analyze stack sizes for compiled objects +# +# Copyright (C) 2024-2025 Luke T. Shumaker <lukeshu@lukeshu.com> +# SPDX-License-Identifier: AGPL-3.0-or-later + +import re +import sys + +from . import app_main + +# pylint: disable=unused-variable +__all__ = [ + "main", +] + + +re_c_obj_suffix = re.compile(r"\.c\.(?:o|obj)$") + + +def main() -> None: + pico_platform = sys.argv[1] + base_dir = sys.argv[2] + obj_fnames = set(sys.argv[3:]) + + c_fnames: set[str] = set() + ci_fnames: set[str] = set() + for obj_fname in obj_fnames: + if re_c_obj_suffix.search(obj_fname): + ci_fnames.add(re_c_obj_suffix.sub(".c.ci", obj_fname)) + with open(obj_fname + ".d", "r", encoding="utf-8") as fh: + c_fnames.update(fh.read().replace("\\\n", " ").split(":")[-1].split()) + + app_main.main( + arg_pico_platform=pico_platform, + arg_base_dir=base_dir, + arg_ci_fnames=ci_fnames, + arg_c_fnames=c_fnames, + ) diff --git a/build-aux/measurestack/analyze.py b/build-aux/measurestack/analyze.py new file mode 100644 index 0000000..f151642 --- /dev/null +++ b/build-aux/measurestack/analyze.py @@ -0,0 +1,605 @@ +# build-aux/measurestack/analyze.py - Analyze stack sizes for compiled objects +# +# Copyright (C) 2024-2025 Luke T. Shumaker <lukeshu@lukeshu.com> +# SPDX-License-Identifier: AGPL-3.0-or-later + +import random +import re +import sys +import typing + +from . import vcg + +# Whether to print "//dbg-cache:" on cache writes +dbg_cache = False +# Whether to print the graph in a /* comment */ before processing it +dbg_dumpgraph = False +# Whether to print "//dbg-nstatic:" lines that trace nstatic() execution +dbg_nstatic = False +# Whether to disable nstatic() caching (but does NOT disable any cache-related debug logging) +dbg_nocache = False +# Whether to sort things for consistently-ordered execution, or shuffle things to detect bugs +dbg_sort: typing.Literal["unsorted", "sorted", "shuffled"] = "unsorted" + +# pylint: disable=unused-variable +__all__ = [ + "BaseName", + "QName", + "UsageKind", + "Node", + "maybe_sorted", + "AnalyzeResultVal", + "AnalyzeResultGroup", + "AnalyzeResult", + "analyze", +] + + +def dumps(x: typing.Any, depth: int = 0, compact: bool = False) -> str: + match x: + case int() | str() | None: + return repr(x) + case dict(): + if len(x) == 0: + return "{}" + ret = "{" + if not compact: + ret += "\n" + for k, v in x.items(): + if not compact: + ret += "\t" * (depth + 1) + ret += dumps(k, depth + 1, True) + ret += ":" + if not compact: + ret += " " + ret += dumps(v, depth + 1, compact) + ret += "," + if not compact: + ret += "\n" + if not compact: + ret += "\t" * depth + ret += "}" + return ret + case list(): + if len(x) == 0: + return "[]" + ret = "[" + if not compact: + ret += "\n" + for v in x: + if not compact: + ret += "\t" * (depth + 1) + ret += dumps(v, depth + 1, compact) + ret += "," + if not compact: + ret += "\n" + if not compact: + ret += "\t" * depth + ret += "]" + return ret + case set(): + if len(x) == 0: + return "set()" + ret = "{" + if not compact: + ret += "\n" + for v in x: + if not compact: + ret += "\t" * (depth + 1) + ret += dumps(v, depth + 1, compact) + ret += "," + if not compact: + ret += "\n" + if not compact: + ret += "\t" * depth + ret += "}" + return ret + case _: + if hasattr(x, "__dict__"): + return f"{x.__class__.__name__}(*{dumps(x.__dict__, depth, compact)})" + return f"TODO({x.__class__.__name__})" + + +# types ######################################################################## + + +class BaseName: + # class ########################################################## + + _interned: dict[str, "BaseName"] = {} + + def __new__(cls, content: str) -> "BaseName": + if ":" in content: + raise ValueError(f"invalid non-qualified name: {content!r}") + content = sys.intern(content) + if content not in cls._interned: + self = super().__new__(cls) + self._content = content + cls._interned[content] = self + return cls._interned[content] + + # instance ####################################################### + + _content: str + + def __str__(self) -> str: + return self._content + + def __repr__(self) -> str: + return f"BaseName({self._content!r})" + + def __format__(self, fmt_spec: str, /) -> str: + return repr(self) + + def __eq__(self, other: typing.Any) -> bool: + assert isinstance( + other, BaseName + ), f"comparing BaseName with {other.__class__.__name__}" + return self._content == other._content + + def __lt__(self, other: "BaseName") -> bool: + return self._content < other._content + + def __hash__(self) -> int: + return self._content.__hash__() + + def as_qname(self) -> "QName": + return QName(self._content) + + +class QName: + # class ########################################################## + + _interned: dict[str, "QName"] = {} + + def __new__(cls, content: str) -> "QName": + content = sys.intern(content) + if content not in cls._interned: + self = super().__new__(cls) + self._content = content + self._base = None + cls._interned[content] = self + return cls._interned[content] + + # instance ####################################################### + + _content: str + _base: BaseName | None + + def __str__(self) -> str: + return self._content + + def __repr__(self) -> str: + return f"QName({self._content!r})" + + def __format__(self, fmt_spec: str, /) -> str: + return repr(self) + + def __eq__(self, other: typing.Any) -> bool: + assert isinstance( + other, QName + ), f"comparing QName with {other.__class__.__name__}" + return self._content == other._content + + def __lt__(self, other: "QName") -> bool: + return self._content < other._content + + def __hash__(self) -> int: + return self._content.__hash__() + + def base(self) -> BaseName: + if self._base is None: + self._base = BaseName(self._content.rsplit(":", 1)[-1].split(".", 1)[0]) + return self._base + + +UsageKind: typing.TypeAlias = typing.Literal["static", "dynamic", "dynamic,bounded"] + + +class Node: + # from .title (`static` and `__weak` functions are prefixed with + # the compilation unit .c file. For static functions that's fine, + # but we'll have to handle it specially for __weak.). + funcname: QName + # .label is "{funcname}\n{location}\n{nstatic} bytes (static}\n{ndynamic} dynamic objects" + location: str + usage_kind: UsageKind + nstatic: int + ndynamic: int + + # edges with .sourcename set to this node, val is if it's + # OK/expected that the function be missing. + calls: dict[QName, bool] + + +class AnalyzeResultVal(typing.NamedTuple): + nstatic: int + cnt: int + + +class AnalyzeResultGroup(typing.NamedTuple): + rows: dict[QName, AnalyzeResultVal] + + +class AnalyzeResult(typing.NamedTuple): + groups: dict[str, AnalyzeResultGroup] + missing: set[QName] + dynamic: set[QName] + + included_funcs: set[QName] + + +class SkipModel(typing.NamedTuple): + """Running the skipmodel calls `.fn(chain, ...)` with the chain + consisting of the last few items of the input chain. + + If `.nchain` is an int: + + - the chain is the last `.nchain` items or the input chain. If + the input chain is not that long, then `.fn` is not called and + the call is *not* skipped. + + If `.nchain` is a collection: + + - the chain starts with the *last* occurance of `.nchain` in the + input chain. If the input chain does not contain a member of + the collection, then .fn is called with an empty chain. + """ + + nchain: int | typing.Collection[BaseName] + fn: typing.Callable[[typing.Sequence[QName], Node, QName], bool] + + def __call__( + self, chain: typing.Sequence[QName], node: Node, call: QName + ) -> tuple[bool, int]: + match self.nchain: + case int(): + if len(chain) >= self.nchain: + _chain = chain[-self.nchain :] + return self.fn(_chain, node, call), len(_chain) + 1 + return False, 0 + case _: + for i in reversed(range(len(chain))): + if chain[i].base() in self.nchain: + _chain = chain[i:] + return self.fn(_chain, node, call), len(_chain) + 1 + return self.fn([], node, call), 1 + + +class Application(typing.Protocol): + def extra_nodes(self) -> typing.Collection[Node]: ... + def mutate_node(self, node: Node) -> None: ... + def indirect_callees( + self, elem: vcg.VCGElem + ) -> tuple[typing.Collection[QName], bool]: ... + def skipmodels(self) -> dict[BaseName, SkipModel]: ... + + +# code ######################################################################### + +re_node_normal_label = re.compile( + r"(?P<funcname>[^\n]+)\n" + + r"(?P<location>[^\n]+:[0-9]+:[0-9]+)\n" + + r"(?P<nstatic>[0-9]+) bytes \((?P<usage_kind>static|dynamic|dynamic,bounded)\)\n" + + r"(?P<ndynamic>[0-9]+) dynamic objects" + + r"(?:\n.*)*", + flags=re.MULTILINE, +) +re_node_alias_label = re.compile( + r"(?P<funcname>[^\n]+)\n" + r"(?P<location>[^\n]+:[0-9]+:[0-9]+)", + flags=re.MULTILINE, +) + + +class _Graph: + graph: dict[QName, Node] + qualified: dict[BaseName, QName] + + _resolve_cache: dict[QName, QName | None] + + def __init__(self) -> None: + self._resolve_cache = {} + + def _resolve_funcname(self, funcname: QName) -> QName | None: + s = str(funcname) + is_qualified = ":" in s + + # Handle `ld --wrap` functions + if not is_qualified: + with_wrap = QName(f"__wrap_{s}") + if with_wrap in self.graph: + return with_wrap + if s.startswith("__real_"): + without_real = QName(s[len("__real_") :]) + if without_real in self.graph: + funcname = without_real + + # Usual case + if funcname in self.graph: + return funcname + + # Handle `__weak`/`[[gnu::weak]]` functions + if not is_qualified: + return self.qualified.get(BaseName(s)) + + return None + + def resolve_funcname(self, funcname: QName) -> QName | None: + if funcname not in self._resolve_cache: + self._resolve_cache[funcname] = self._resolve_funcname(funcname) + return self._resolve_cache[funcname] + + +if typing.TYPE_CHECKING: + from _typeshed import SupportsRichComparisonT as _T_sortable + +_T = typing.TypeVar("_T") + + +@typing.overload +def maybe_sorted( + unsorted: typing.Iterable["_T_sortable"], /, *, key: None = None +) -> typing.Iterable["_T_sortable"]: ... +@typing.overload +def maybe_sorted( + unsorted: typing.Iterable[_T], /, *, key: typing.Callable[[_T], "_T_sortable"] +) -> typing.Iterable[_T]: ... + + +def maybe_sorted( + unsorted: typing.Iterable[_T], + /, + *, + key: typing.Callable[[_T], "_T_sortable"] | None = None, +) -> typing.Iterable[_T]: + match dbg_sort: + case "unsorted": + return unsorted + case "sorted": + return sorted(unsorted, key=key) # type: ignore + case "shuffled": + ret = [*unsorted] + random.shuffle(ret) + return ret + + +def _make_graph( + ci_fnames: typing.Collection[str], + app: Application, +) -> _Graph: + graph: dict[QName, Node] = {} + qualified: dict[BaseName, set[QName]] = {} + + def handle_elem(elem: vcg.VCGElem) -> None: + match elem.typ: + case "node": + node = Node() + node.calls = {} + skip = False + for k, v in elem.attrs.items(): + match k: + case "title": + node.funcname = QName(v) + case "label": + shape: str | None = elem.attrs.get("shape", None) + match shape: + case "ellipse": # external + pass + case "triangle": # alias (since GCC 15) + m = re_node_alias_label.fullmatch(v) + if not m: + raise ValueError( + f"unexpected label value {v!r}" + ) + node.location = m.group("location") + node.usage_kind = "static" + node.nstatic = 0 + node.ndynamic = 0 + case None: # normal + m = re_node_normal_label.fullmatch(v) + if not m: + raise ValueError( + f"unexpected label value {v!r}" + ) + node.location = m.group("location") + node.usage_kind = typing.cast( + UsageKind, m.group("usage_kind") + ) + node.nstatic = int(m.group("nstatic")) + node.ndynamic = int(m.group("ndynamic")) + case _: + raise ValueError( + f"unexpected shape value {shape!r}" + ) + case "shape": + match v: + case "ellipse": # external + skip = True + case "triangle": # alias (since GCC 15) + pass + case _: + raise ValueError(f"unexpected shape value {v!r}") + case _: + raise ValueError(f"unknown edge key {k!r}") + if not skip: + if node.funcname in graph: + raise ValueError(f"duplicate node {node.funcname}") + graph[node.funcname] = node + if ":" in str(node.funcname): + basename = node.funcname.base() + if basename not in qualified: + qualified[basename] = set() + qualified[basename].add(node.funcname) + case "edge": + caller: QName | None = None + callee: QName | None = None + for k, v in elem.attrs.items(): + match k: + case "sourcename": + caller = QName(v) + case "targetname": + callee = QName(v) + case "label": + pass + case _: + raise ValueError(f"unknown edge key {k!r}") + if caller is None or callee is None: + raise ValueError(f"incomplete edge: {elem.attrs!r}") + if caller not in graph: + raise ValueError(f"unknown caller: {caller}") + if callee == QName("__indirect_call"): + callees, missing_ok = app.indirect_callees(elem) + assert ( + len(callees) > 0 + ), f"app returning 0 callees for {elem.attrs.get('label')} indicates the code would crash" + for callee in maybe_sorted(callees): + if callee not in graph[caller].calls: + graph[caller].calls[callee] = missing_ok + else: + graph[caller].calls[callee] = False + case _: + raise ValueError(f"unknown elem type {elem.typ!r}") + + for ci_fname in maybe_sorted(ci_fnames): + with open(ci_fname, "r", encoding="utf-8") as fh: + for elem in vcg.parse_vcg(fh): + handle_elem(elem) + + def sort_key(node: Node) -> QName: + return node.funcname + + for node in maybe_sorted(app.extra_nodes(), key=sort_key): + if node.funcname in graph: + raise ValueError(f"duplicate node {node.funcname}") + graph[node.funcname] = node + + for node in graph.values(): + app.mutate_node(node) + + ret = _Graph() + ret.graph = graph + ret.qualified = {} + for bname, qnames in qualified.items(): + if len(qnames) == 1: + ret.qualified[bname] = next(name for name in qnames) + return ret + + +def analyze( + *, + ci_fnames: typing.Collection[str], + app_func_filters: dict[str, typing.Callable[[QName], tuple[int, bool]]], + app: Application, + cfg_max_call_depth: int, +) -> AnalyzeResult: + graphdata = _make_graph(ci_fnames, app) + if dbg_dumpgraph: + print(f"/* {dumps(graphdata)} */") + + missing: set[QName] = set() + dynamic: set[QName] = set() + included_funcs: set[QName] = set() + + track_inclusion: bool = True + + skipmodels = app.skipmodels() + for name, model in skipmodels.items(): + if not isinstance(model.nchain, int): + assert len(model.nchain) > 0 + + _nstatic_cache: dict[QName, int] = {} + + def _nstatic(chain: list[QName], funcname: QName) -> tuple[int, int]: + nonlocal track_inclusion + + assert funcname in graphdata.graph + + def putdbg(msg: str) -> None: + print(f"//dbg-nstatic: {'- '*len(chain)}{msg}") + + node = graphdata.graph[funcname] + if dbg_nstatic: + putdbg(f"{funcname}\t{node.nstatic}") + if node.usage_kind == "dynamic" or node.ndynamic > 0: + dynamic.add(funcname) + if track_inclusion: + included_funcs.add(funcname) + + max_call_nstatic = 0 + max_call_nchain = 0 + + if node.calls: + skipmodel = skipmodels.get(funcname.base()) + chain.append(funcname) + if len(chain) == cfg_max_call_depth: + raise ValueError(f"max call depth exceeded: {chain}") + for call_orig_qname, call_missing_ok in node.calls.items(): + skip_nchain = 0 + # 1. Resolve + call_qname = graphdata.resolve_funcname(call_orig_qname) + if not call_qname: + if skipmodel: + skip, _ = skipmodel(chain[:-1], node, call_orig_qname) + if skip: + if dbg_nstatic: + putdbg(f"{call_orig_qname}\tskip missing") + continue + if not call_missing_ok: + missing.add(call_orig_qname) + if dbg_nstatic: + putdbg(f"{call_orig_qname}\tmissing") + continue + + # 2. Skip + if skipmodel: + skip, skip_nchain = skipmodel(chain[:-1], node, call_qname) + max_call_nchain = max(max_call_nchain, skip_nchain) + if skip: + if dbg_nstatic: + putdbg(f"{call_qname}\tskip") + continue + + # 3. Call + if ( + (not dbg_nocache) + and skip_nchain == 0 + and call_qname in _nstatic_cache + ): + call_nstatic = _nstatic_cache[call_qname] + if dbg_nstatic: + putdbg(f"{call_qname}\ttotal={call_nstatic} (cache-read)") + max_call_nstatic = max(max_call_nstatic, call_nstatic) + else: + call_nstatic, call_nchain = _nstatic(chain, call_qname) + max_call_nstatic = max(max_call_nstatic, call_nstatic) + max_call_nchain = max(max_call_nchain, call_nchain) + if skip_nchain == 0 and call_nchain == 0: + if dbg_nstatic: + putdbg(f"{call_qname}\ttotal={call_nstatic} (cache-write)") + if call_qname not in _nstatic_cache: + if dbg_cache: + print(f"//dbg-cache: {call_qname} = {call_nstatic}") + _nstatic_cache[call_qname] = call_nstatic + else: + assert dbg_nocache + assert _nstatic_cache[call_qname] == call_nstatic + elif dbg_nstatic: + putdbg(f"{call_qname}\ttotal={call_nstatic} (do-not-cache)") + chain.pop() + return node.nstatic + max_call_nstatic, max(0, max_call_nchain - 1) + + def nstatic(funcname: QName) -> int: + return _nstatic([], funcname)[0] + + groups: dict[str, AnalyzeResultGroup] = {} + for grp_name, grp_filter in app_func_filters.items(): + rows: dict[QName, AnalyzeResultVal] = {} + for funcname in graphdata.graph: + cnt, track_inclusion = grp_filter(funcname) + if cnt: + rows[funcname] = AnalyzeResultVal(nstatic=nstatic(funcname), cnt=cnt) + groups[grp_name] = AnalyzeResultGroup(rows=rows) + + return AnalyzeResult( + groups=groups, missing=missing, dynamic=dynamic, included_funcs=included_funcs + ) diff --git a/build-aux/measurestack/app_main.py b/build-aux/measurestack/app_main.py new file mode 100644 index 0000000..884aeee --- /dev/null +++ b/build-aux/measurestack/app_main.py @@ -0,0 +1,129 @@ +# build-aux/measurestack/app_main.py - Application-specific wrapper around analyze.py +# +# Copyright (C) 2024-2025 Luke T. Shumaker <lukeshu@lukeshu.com> +# SPDX-License-Identifier: AGPL-3.0-or-later + +import os.path +import typing + +from . import analyze, app_output, app_plugins, util +from .analyze import BaseName, QName + +# pylint: disable=unused-variable +__all__ = [ + "main", +] + + +def main( + *, + arg_pico_platform: str, + arg_base_dir: str, + arg_ci_fnames: typing.Collection[str], + arg_c_fnames: typing.Collection[str], +) -> None: + + plugins: list[util.Plugin] = [] + + # sbc-harness #################################################### + + libmisc_plugin = app_plugins.LibMiscPlugin(arg_c_fnames) + lib9p_plugin = app_plugins.Lib9PPlugin(arg_base_dir, arg_c_fnames) + + def sbc_is_thread(name: QName) -> int: + if str(name).endswith("_cr") and name.base() != BaseName("lib9p_srv_read_cr"): + if "9p" in str(name.base()) or "lib9p/tests/test_server/main.c:" in str( + name + ): + return lib9p_plugin.thread_count(name) + return 1 + if name.base() == ( + BaseName("_entry_point") + if arg_pico_platform == "rp2040" + else BaseName("main") + ): + return 1 + return 0 + + plugins += [ + app_plugins.CmdPlugin(), + libmisc_plugin, + app_plugins.LibHWPlugin(arg_pico_platform, libmisc_plugin), + app_plugins.LibCRPlugin(), + app_plugins.LibCRIPCPlugin(), + lib9p_plugin, + ] + + # pico-sdk ####################################################### + + if arg_pico_platform == "rp2040": + + def get_init_array() -> typing.Collection[QName]: + ret: list[QName] = [] + for plugin in plugins: + ret.extend(plugin.init_array()) + return ret + + plugins += [ + app_plugins.PicoSDKPlugin( + get_init_array=get_init_array, + PICO_PANIC_FUNCTION="assert_panic", + ), + app_plugins.TinyUSBDevicePlugin(arg_c_fnames), + app_plugins.NewlibPlugin(), + app_plugins.LibGCCPlugin(), + ] + + # Tie it all together ############################################ + + def thread_filter(name: QName) -> tuple[int, bool]: + return sbc_is_thread(name), True + + def intrhandler_filter(name: QName) -> tuple[int, bool]: + for plugin in plugins: + if plugin.is_intrhandler(name): + return 1, True + return 0, False + + def misc_filter(name: QName) -> tuple[int, bool]: + if name in [ + QName("__assert_msg_fail"), + ]: + return 1, False + if str(name.base()).endswith("_putb"): + return 1, False + return 0, False + + extra_includes: list[BaseName] = [] + for plugin in plugins: + extra_includes.extend(plugin.extra_includes()) + + def extra_filter(name: QName) -> tuple[int, bool]: + nonlocal extra_includes + if name.base() in extra_includes: + return 1, True + return 0, False + + def _str_location_xform(loc: str) -> str: + if not loc.startswith("/"): + return loc + parts = loc.split(":", 1) + parts[0] = "./" + os.path.relpath(parts[0], arg_base_dir) + return ":".join(parts) + + def location_xform(_loc: QName) -> str: + return _str_location_xform(str(_loc)) + + result = analyze.analyze( + ci_fnames=arg_ci_fnames, + app_func_filters={ + "Threads": thread_filter, + "Interrupt handlers": intrhandler_filter, + "Misc": misc_filter, + "Extra": extra_filter, + }, + app=util.PluginApplication(_str_location_xform, plugins), + cfg_max_call_depth=100, + ) + + app_output.print_c(result, location_xform) diff --git a/build-aux/measurestack/app_output.py b/build-aux/measurestack/app_output.py new file mode 100644 index 0000000..5cf7d17 --- /dev/null +++ b/build-aux/measurestack/app_output.py @@ -0,0 +1,157 @@ +# build-aux/measurestack/app_output.py - Generate `stack.c` files +# +# Copyright (C) 2024-2025 Luke T. Shumaker <lukeshu@lukeshu.com> +# SPDX-License-Identifier: AGPL-3.0-or-later + +import typing + +from . import analyze +from .analyze import QName + +# pylint: disable=unused-variable +__all__ = [ + "print_c", +] + + +def print_group( + result: analyze.AnalyzeResult, + location_xform: typing.Callable[[QName], str], + grp_name: str, +) -> None: + grp = result.groups[grp_name] + if not grp.rows: + print(f"= {grp_name} (empty) =") + return + + nsum = sum(v.nstatic * v.cnt for v in grp.rows.values()) + nmax = max(v.nstatic for v in grp.rows.values()) + + # Figure sizes. + namelen = max( + [len(location_xform(k)) for k in grp.rows.keys()] + [len(grp_name) + 4] + ) + numlen = len(str(nsum)) + sep1 = ("=" * namelen) + " " + "=" * numlen + sep2 = ("-" * namelen) + " " + "-" * numlen + + # Print. + print("= " + grp_name + " " + sep1[len(grp_name) + 3 :]) + for qname, val in sorted(grp.rows.items()): + name = location_xform(qname) + if val.nstatic == 0: + continue + print( + f"{name:<{namelen}} {val.nstatic:>{numlen}}" + + (f" * {val.cnt}" if val.cnt != 1 else "") + ) + print(sep2) + print(f"{'Total':<{namelen}} {nsum:>{numlen}}") + print(f"{'Maximum':<{namelen}} {nmax:>{numlen}}") + print(sep1) + + +def lm_round_up(n: int, d: int) -> int: + return ((n + d - 1) // d) * d + + +def print_c( + result: analyze.AnalyzeResult, location_xform: typing.Callable[[QName], str] +) -> None: + print('#include "config.h" /* for COROUTINE_STACK_* extern declarations */') + print() + print("/*") + print_group(result, location_xform, "Threads") + print_group(result, location_xform, "Interrupt handlers") + print("*/") + intrstack = max( + v.nstatic for v in result.groups["Interrupt handlers"].rows.values() + ) + stack_guard_size = 16 * 2 + + class CrRow(typing.NamedTuple): + name: str + cnt: int + base: int + size: int + + print("[[gnu::aligned]] void _bogus_aligned_fn(void) {};") + print("#define STACK_ALIGNED [[gnu::aligned(__alignof__(_bogus_aligned_fn))]]") + + rows: list[CrRow] = [] + mainrow: CrRow | None = None + for funcname, val in result.groups["Threads"].rows.items(): + name = str(funcname.base()) + base = val.nstatic + size = base + intrstack + if name in ["main", "_entry_point"]: + mainrow = CrRow(name=name, cnt=1, base=base, size=size) + else: + size = lm_round_up(size + stack_guard_size, 512) + rows.append(CrRow(name=name, cnt=val.cnt, base=base, size=size)) + namelen = max(len(f"{r.name}{r.cnt}" if r.cnt > 1 else r.name) for r in rows) + baselen = max(len(str(r.base)) for r in rows) + sizesum = sum(r.cnt * (r.size + stack_guard_size) for r in rows) + sizelen = len(str(max(sizesum, mainrow.size if mainrow else 0))) + + def print_row(comment: bool, name: str, size: int, eqn: str | None = None) -> None: + prefix = "STACK_ALIGNED char COROUTINE_STACK_" + if comment: + print(f"/* {name}".ljust(len(prefix) + namelen), end="") + else: + print(f"{prefix}{name:<{namelen}}", end="") + print(f"[{size:>{sizelen}}];", end="") + if comment: + print(" */", end="") + elif eqn: + print(" ", end="") + if eqn: + print(f" /* {eqn} */", end="") + print() + + for row in sorted(rows): + comment = ( + f"LM_ROUND_UP({row.base:>{baselen}}+{intrstack}+{stack_guard_size}, 512)" + ) + if row.cnt > 1: + for i in range(row.cnt): + print_row(False, f"{row.name}{i}", row.size, comment) + else: + print_row(False, row.name, row.size, comment) + print_row(True, "TOTAL", sizesum) + if mainrow: + print_row( + True, + "MAIN/KERNEL", + mainrow.size, + f" {mainrow.base:>{baselen}}+{intrstack}", + ) + print() + for row in sorted(rows): + name = row.name + if row.cnt > 1: + name += "0" + print(f"char *const COROUTINE_STACK_{row.name}[{row.cnt}] = {{") + for i in range(row.cnt): + print(f"\tCOROUTINE_STACK_{row.name}{i},") + print("};") + print( + f"const size_t COROUTINE_STACK_{row.name}_len = sizeof(COROUTINE_STACK_{name});" + ) + + print() + print("/*") + print_group(result, location_xform, "Misc") + + for funcname in sorted(result.missing): + print(f"warning: missing: {location_xform(funcname)}") + for funcname in sorted(result.dynamic): + print(f"warning: dynamic-stack-usage: {location_xform(funcname)}") + + print("*/") + print("") + print("/*") + print_group(result, location_xform, "Extra") + for funcname in sorted(result.included_funcs): + print(f"included: {location_xform(funcname)}") + print("*/") diff --git a/build-aux/measurestack/app_plugins.py b/build-aux/measurestack/app_plugins.py new file mode 100644 index 0000000..a921407 --- /dev/null +++ b/build-aux/measurestack/app_plugins.py @@ -0,0 +1,915 @@ +# build-aux/measurestack/app_plugins.py - Application-specific plugins for analyze.py +# +# Copyright (C) 2024-2025 Luke T. Shumaker <lukeshu@lukeshu.com> +# SPDX-License-Identifier: AGPL-3.0-or-later + +import re +import subprocess +import typing + +from . import analyze, util +from .analyze import BaseName, Node, QName +from .util import synthetic_node + +# pylint: disable=unused-variable +__all__ = [ + "CmdPlugin", + "LibHWPlugin", + "LibCRPlugin", + "LibCRIPCPlugin", + "Lib9PPlugin", + "LibMiscPlugin", + "PicoSDKPlugin", + "TinyUSBDevicePlugin", + "NewlibPlugin", + "LibGCCPlugin", +] + + +class CmdPlugin: + def is_intrhandler(self, name: QName) -> bool: + return False + + def init_array(self) -> typing.Collection[QName]: + return [] + + def extra_includes(self) -> typing.Collection[BaseName]: + return [] + + def extra_nodes(self) -> typing.Collection[Node]: + return [] + + def mutate_node(self, node: Node) -> None: + pass + + def indirect_callees( + self, loc: str, line: str + ) -> tuple[typing.Collection[QName], bool] | None: + if "/3rd-party/" in loc: + return None + if "srv->auth" in line: + return [QName("__indirect_call_with_null_check:srv->auth")], False + if "srv->rootdir" in line: + return [QName("get_root")], False + if "/ihex.c" in loc: + if "self->handle_data" in line: + return [QName("flash_handle_ihex_data")], False + if "self->handle_eof" in line: + return [QName("flash_handle_ihex_eof")], False + if "self->handle_set_exec_start_lin" in line: + return [ + QName( + "__indirect_call_with_null_check:self->handle_set_exec_start_lin" + ) + ], False + if "self->handle_set_exec_start_seg" in line: + return [ + QName( + "__indirect_call_with_null_check:self->handle_set_exec_start_seg" + ) + ], False + return None + + def skipmodels(self) -> dict[BaseName, analyze.SkipModel]: + return {} + + +class LibMiscPlugin: + re_comment = re.compile(r"/\*.*?\*/") + re_ws = re.compile(r"\s+") + re_lo_iface = re.compile(r"^\s*#\s*define\s+(?P<name>\S+)_LO_IFACE") + re_lo_func = re.compile(r"LO_FUNC *\([^,]*, *(?P<name>[^,) ]+) *[,)]") + re_lo_implementation = re.compile( + r"^LO_IMPLEMENTATION_(?P<vis>H|C|STATIC)\s*\(" + r"\s*(?P<iface>[^, ]+)\s*," + r"\s*(?P<impl_typ>[^,]+)\s*," + r"\s*(?P<impl_name>[^, ]+)\s*\)" + ) + re_lo_call = re.compile(r".*\bLO_CALL\((?P<obj>[^,]+), (?P<meth>[^,)]+)[,)].*") + + objcalls: dict[str, set[QName]] # method_name => {method_impls} + + def __init__(self, arg_c_fnames: typing.Collection[str]) -> None: + ifaces: dict[str, set[str]] = {} # iface_name => {method_names} + for fname in arg_c_fnames: + with open(fname, "r", encoding="utf-8") as fh: + while line := fh.readline(): + if m := self.re_lo_iface.match(line): + iface_name = m.group("name") + if iface_name not in ifaces: + ifaces[iface_name] = set() + while line.endswith("\\\n"): + line += fh.readline() + line = line.replace("\\\n", " ") + line = self.re_comment.sub(" ", line) + line = self.re_ws.sub(" ", line) + for m2 in self.re_lo_func.finditer(line): + ifaces[iface_name].add(m2.group("name")) + + implementations: dict[str, set[str]] = {} # iface_name => {impl_names} + for iface_name in ifaces: + implementations[iface_name] = set() + for fname in arg_c_fnames: + with open(fname, "r", encoding="utf-8") as fh: + for line in fh: + line = line.strip() + if m := self.re_lo_implementation.match(line): + implementations[m.group("iface")].add(m.group("impl_name")) + + objcalls: dict[str, set[QName]] = {} # method_name => {method_impls} + for iface_name, iface in ifaces.items(): + for method_name in iface: + if method_name not in objcalls: + objcalls[method_name] = set() + for impl_name in implementations[iface_name]: + objcalls[method_name].add(QName(impl_name + "_" + method_name)) + self.objcalls = objcalls + + def is_intrhandler(self, name: QName) -> bool: + return False + + def init_array(self) -> typing.Collection[QName]: + return [] + + def extra_includes(self) -> typing.Collection[BaseName]: + return [] + + def extra_nodes(self) -> typing.Collection[Node]: + return [] + + def mutate_node(self, node: Node) -> None: + pass + + def indirect_callees( + self, loc: str, line: str + ) -> tuple[typing.Collection[QName], bool] | None: + if "/3rd-party/" in loc: + return None + if m := self.re_lo_call.fullmatch(line): + meth = m.group("meth") + if meth in self.objcalls: + callees: typing.Collection[QName] = self.objcalls[meth] + if len(callees) == 0: + raise ValueError(f"{loc}: no implementors of {meth}") + if meth == "writev" and "lib9p/srv.c" in loc: # KLUDGE + callees = [ + c for c in callees if c.base() != BaseName("rread_writev") + ] + return callees, False + return [ + QName(f"__indirect_call:{m.group('obj')}.vtable->{m.group('meth')}") + ], False + return None + + def skipmodels(self) -> dict[BaseName, analyze.SkipModel]: + return {} + + +class LibHWPlugin: + pico_platform: str + libmisc: LibMiscPlugin + + def __init__(self, arg_pico_platform: str, libmisc: LibMiscPlugin) -> None: + self.pico_platform = arg_pico_platform + self.libmisc = libmisc + + def is_intrhandler(self, name: QName) -> bool: + return name.base() in [ + BaseName("rp2040_hwtimer_intrhandler"), + BaseName("hostclock_handle_sig_alarm"), + BaseName("hostnet_handle_sig_io"), + BaseName("gpioirq_handler"), + BaseName("dmairq_handler"), + ] + + def init_array(self) -> typing.Collection[QName]: + return [] + + def extra_includes(self) -> typing.Collection[BaseName]: + return [] + + def extra_nodes(self) -> typing.Collection[Node]: + return [] + + def mutate_node(self, node: Node) -> None: + pass + + def indirect_callees( + self, loc: str, line: str + ) -> tuple[typing.Collection[QName], bool] | None: + if "/3rd-party/" in loc: + return None + for fn in [ + "io_readv", + "io_writev", + "io_close", + "io_close_read", + "io_close_write", + "io_readwritev", + ]: + if f"{fn}(" in line: + return self.libmisc.indirect_callees(loc, f"LO_CALL(x, {fn[3:]})") + for fn in [ + "io_read", + "io_write", + ]: + if f"{fn}(" in line: + # Like above, but add a "v" to the end. + return self.libmisc.indirect_callees(loc, f"LO_CALL(x, {fn[3:]}v)") + if "trigger->cb(trigger->cb_arg)" in line: + ret = [ + QName("alarmclock_sleep_intrhandler"), + ] + if self.pico_platform == "rp2040": + ret += [ + QName("w5500_tcp_alarm_handler"), + QName("w5500_udp_alarm_handler"), + ] + return ret, False + if "/rp2040_gpioirq.c:" in loc and "handler->fn" in line: + return [ + QName("w5500_intrhandler"), + ], False + if "/rp2040_dma.c:" in loc and "handler->fn" in line: + return [ + QName("rp2040_hwspi_intrhandler"), + ], False + return None + + def skipmodels(self) -> dict[BaseName, analyze.SkipModel]: + return {} + + +class LibCRPlugin: + def is_intrhandler(self, name: QName) -> bool: + return name.base() in [ + BaseName("_cr_gdb_intrhandler"), + ] + + def init_array(self) -> typing.Collection[QName]: + return [] + + def extra_includes(self) -> typing.Collection[BaseName]: + return [] + + def extra_nodes(self) -> typing.Collection[Node]: + return [] + + def mutate_node(self, node: Node) -> None: + pass + + def indirect_callees( + self, loc: str, line: str + ) -> tuple[typing.Collection[QName], bool] | None: + return None + + def skipmodels(self) -> dict[BaseName, analyze.SkipModel]: + return {} + + +class LibCRIPCPlugin: + def is_intrhandler(self, name: QName) -> bool: + return False + + def init_array(self) -> typing.Collection[QName]: + return [] + + def extra_includes(self) -> typing.Collection[BaseName]: + return [] + + def extra_nodes(self) -> typing.Collection[Node]: + return [] + + def mutate_node(self, node: Node) -> None: + pass + + def indirect_callees( + self, loc: str, line: str + ) -> tuple[typing.Collection[QName], bool] | None: + if "/3rd-party/" in loc: + return None + if "/chan.c:" in loc and "front->dequeue(" in line: + return [ + QName("cr_chan_dequeue"), + QName("cr_select_dequeue"), + ], False + return None + + def skipmodels(self) -> dict[BaseName, analyze.SkipModel]: + return {} + + +class Lib9PPlugin: + re_lib9p_msg_entry = re.compile(r"^\s*_MSG\((?P<typ>\S+)\),$") + + lib9p_msgs: set[str] + _CONFIG_9P_MAX_CONNS: int | None + _CONFIG_9P_MAX_REQS: int | None + + def __init__( + self, + arg_base_dir: str, + arg_c_fnames: typing.Collection[str], + ) -> None: + # Find filenames ####################################################### + + def _is_config_h(fname: str) -> bool: + if not fname.startswith(arg_base_dir + "/"): + return False + suffix = fname[len(arg_base_dir) + 1 :] + if suffix.startswith("3rd-party/"): + return False + return suffix.endswith("/config.h") + + config_h_fname = util.get_zero_or_one(_is_config_h, arg_c_fnames) + + lib9p_srv_c_fname = util.get_zero_or_one( + lambda fname: fname.endswith("lib9p/srv.c"), arg_c_fnames + ) + + lib9p_generated_c_fname = util.get_zero_or_one( + lambda fname: fname.endswith("lib9p/core_generated.c"), arg_c_fnames + ) + + # Read config ########################################################## + + def config_h_get(varname: str) -> int | None: + if config_h_fname: + line = subprocess.run( + ["cpp"], + input=f'#include "{config_h_fname}"\n{varname}\n', + check=True, + capture_output=True, + encoding="utf-8", + ).stdout.split("\n")[-2] + return int(eval(line)) # pylint: disable=eval-used + return None + + self._CONFIG_9P_MAX_CONNS = config_h_get("_CONFIG_9P_MAX_CONNS") + self._CONFIG_9P_MAX_REQS = config_h_get("_CONFIG_9P_MAX_REQS") + + # Read sources ######################################################### + + lib9p_msgs: set[str] = set() + if lib9p_generated_c_fname: + with open(lib9p_generated_c_fname, "r", encoding="utf-8") as fh: + for line in fh: + line = line.rstrip() + if m := self.re_lib9p_msg_entry.fullmatch(line): + typ = m.group("typ") + lib9p_msgs.add(typ) + self.lib9p_msgs = lib9p_msgs + + def thread_count(self, name: QName) -> int: + assert self._CONFIG_9P_MAX_CONNS + assert self._CONFIG_9P_MAX_REQS + if "read" in str(name.base()): + return self._CONFIG_9P_MAX_CONNS + if "write" in str(name.base()): + return self._CONFIG_9P_MAX_REQS + return 1 + + def is_intrhandler(self, name: QName) -> bool: + return False + + def init_array(self) -> typing.Collection[QName]: + return [] + + def extra_includes(self) -> typing.Collection[BaseName]: + return [] + + def extra_nodes(self) -> typing.Collection[Node]: + return [] + + def mutate_node(self, node: Node) -> None: + pass + + re_table_call = re.compile( + r"\s*_lib9p_(?P<meth>validate|unmarshal|marshal)\(.*(?P<grp>[RT])msg.*\);\s*" + ) + re_print_call = re.compile(r".*lib9p_table_msg.*\.print\(.*") + + def indirect_callees( + self, loc: str, line: str + ) -> tuple[typing.Collection[QName], bool] | None: + if "/3rd-party/" in loc: + return None + if self.lib9p_msgs and "lib9p/core.c:" in loc: + if m := self.re_table_call.fullmatch(line): + meth = m.group("meth") + grp = m.group("grp") + # Functions for disabled protocol extensions will be missing. + return [ + QName(f"{meth}_{msg}") + for msg in self.lib9p_msgs + if msg.startswith(grp) + ], True + if self.re_print_call.fullmatch(line): + # Functions for disabled protocol extensions will be missing. + return [QName(f"fmt_print_{msg}") for msg in self.lib9p_msgs], True + if "lib9p/srv.c:" in loc: + if "srv->msglog(" in line: + # Actual ROMs shouldn't set this, and so will be missing on rp2040 builds. + return [QName("log_msg")], True + return None + + def skipmodels(self) -> dict[BaseName, analyze.SkipModel]: + return {} + + +class PicoSDKPlugin: + get_init_array: typing.Callable[[], typing.Collection[QName]] + app_init_array: typing.Collection[QName] | None + app_preinit_array: typing.Collection[QName] + _PICO_PANIC_FUNCTION: str | None + + def __init__( + self, + *, + get_init_array: typing.Callable[[], typing.Collection[QName]], + PICO_PANIC_FUNCTION: str | None, + ) -> None: + # grep for '__attribute__((constructor))' / '[[gnu::constructor]]'. + self.get_init_array = get_init_array + self.app_init_array = None + + # git grep '^PICO_RUNTIME_INIT_FUNC\S*(' + self.app_preinit_array = [ + # QName("runtime_init_mutex"), # pico_mutex + # QName("runtime_init_default_alarm_pool"), # pico_time + # QName("runtime_init_boot_locks_reset"), # hardware_boot_lock + QName("runtime_init_per_core_irq_priorities"), # hardware_irq + # QName("spinlock_set_extexclall"), # hardware_sync_spin_lock + QName("__aeabi_bits_init"), # pico_bit_ops + # QName("runtime_init_bootrom_locking_enable"), # pico_bootrom, rp2350-only + # QName("runtime_init_pre_core_tls_setup"), # pico_clib_interface, picolibc-only + # QName("__aeabi_double_init"), # pico_double + # QName("__aeabi_float_init"), # pico_float + QName("__aeabi_mem_init"), # pico_mem_ops + QName("first_per_core_initializer"), # pico_runtime + # pico_runtime_init + # QName("runtime_init_bootrom_reset"), # rp2350-only + # QName("runtime_init_per_core_bootrom_reset"), # rp2350-only + # QName("runtime_init_per_core_h3_irq_registers"), # rp2350-only + QName("runtime_init_early_resets"), + QName("runtime_init_usb_power_down"), + # QName("runtime_init_per_core_enable_coprocessors"), # PICO_RUNTIME_SKIP_INIT_PER_CORE_ENABLE_COPROCESSORS + QName("runtime_init_clocks"), + QName("runtime_init_post_clock_resets"), + QName("runtime_init_rp2040_gpio_ie_disable"), + QName("runtime_init_spin_locks_reset"), + QName("runtime_init_install_ram_vector_table"), + ] + + self._PICO_PANIC_FUNCTION = PICO_PANIC_FUNCTION + + def is_intrhandler(self, name: QName) -> bool: + return name.base() in [ + BaseName("isr_invalid"), + BaseName("isr_nmi"), + BaseName("isr_hardfault"), + BaseName("isr_svcall"), + BaseName("isr_pendsv"), + BaseName("isr_systick"), + *[BaseName(f"isr_irq{n}") for n in range(32)], + ] + + def init_array(self) -> typing.Collection[QName]: + return [] + + def extra_includes(self) -> typing.Collection[BaseName]: + return [] + + def indirect_callees( + self, loc: str, line: str + ) -> tuple[typing.Collection[QName], bool] | None: + if "/3rd-party/pico-sdk/" not in loc or "/3rd-party/pico-sdk/lib/" in loc: + return None + m = util.re_call_other.fullmatch(line) + call: str | None = m.group("func") if m else None + + match call: + case "connect_internal_flash_func": + return [ + QName("rom_func_lookup(ROM_FUNC_CONNECT_INTERNAL_FLASH)") + ], False + case "flash_exit_xip_func": + return [QName("rom_func_lookup(ROM_FUNC_FLASH_EXIT_XIP)")], False + case "flash_range_erase_func": + return [QName("rom_func_lookup(ROM_FUNC_FLASH_RANGE_ERASE)")], False + case "flash_flush_cache_func": + return [QName("rom_func_lookup(ROM_FUNC_FLASH_FLUSH_CACHE)")], False + case "flash_range_program_func": + return [QName("rom_func_lookup(ROM_FUNC_FLASH_RANGE_PROGRAM)")], False + case "rom_table_lookup": + return [QName("rom_hword_as_ptr(BOOTROM_TABLE_LOOKUP_OFFSET)")], False + if "/flash.c:" in loc and "boot2_copyout" in line: + return [QName("_stage2_boot")], False + if "/stdio.c:" in loc: + if call == "out_func": + return [ + QName("stdio_out_chars_crlf"), + QName("stdio_out_chars_no_crlf"), + ], False + if call and (call.startswith("d->") or call.startswith("driver->")): + _, meth = call.split("->", 1) + match meth: + case "out_chars": + return [QName("stdio_uart_out_chars")], False + case "out_flush": + return [QName("stdio_uart_out_flush")], False + case "in_chars": + return [QName("stdio_uart_in_chars")], False + if "/newlib_interface.c:" in loc: + if line == "(*p)();": + if self.app_init_array is None: + self.app_init_array = self.get_init_array() + return self.app_init_array, False + if "/pico_runtime/runtime.c:" in loc: + return self.app_preinit_array, False + return None + + def skipmodels(self) -> dict[BaseName, analyze.SkipModel]: + return {} + + def extra_nodes(self) -> typing.Collection[Node]: + ret = [] + + # src/src/rp2_common/pico_crt0/crt0.S + for n in range(32): + ret += [synthetic_node(f"isr_irq{n}", 0, {"__unhandled_user_irq"})] + ret += [ + synthetic_node("isr_invalid", 0, {"__unhandled_user_irq"}), + synthetic_node("isr_nmi", 0, {"__unhandled_user_irq"}), + synthetic_node("isr_hardfault", 0, {"__unhandled_user_irq"}), + synthetic_node("isr_svcall", 0, {"__unhandled_user_irq"}), + synthetic_node("isr_pendsv", 0, {"__unhandled_user_irq"}), + synthetic_node("isr_systick", 0, {"__unhandled_user_irq"}), + synthetic_node("__unhandled_user_irq", 0), + synthetic_node("_entry_point", 0, {"_reset_handler"}), + synthetic_node("_reset_handler", 0, {"runtime_init", "main", "exit"}), + ] + + # src/rp2_common/pico_int64_ops/pico_int64_ops_aeabi.S + ret += [ + synthetic_node("__wrap___aeabi_lmul", 4), + ] + + # src/rp2_common/hardware_divider/include/hardware/divider_helper.S + save_div_state_and_lr = 5 * 4 + # src/rp2_common/pico_divider/divider_hardware.S + save_div_state_and_lr_64 = 5 * 4 + ret += [ + # s32 aliases + synthetic_node("div_s32s32", 0, {"divmod_s32s32"}), + synthetic_node("__wrap___aeabi_idiv", 0, {"divmod_s32s32"}), + synthetic_node("__wrap___aeabi_idivmod", 0, {"divmod_s32s32"}), + # s32 impl + synthetic_node("divmod_s32s32", 0, {"divmod_s32s32_savestate"}), + synthetic_node( + "divmod_s32s32_savestate", + save_div_state_and_lr, + {"divmod_s32s32_unsafe"}, + ), + synthetic_node("divmod_s32s32_unsafe", 2 * 4, {"__aeabi_idiv0"}), + # u32 aliases + synthetic_node("div_u32u32", 0, {"divmod_u32u32"}), + synthetic_node("__wrap___aeabi_uidiv", 0, {"divmod_u32u32"}), + synthetic_node("__wrap___aeabi_uidivmod", 0, {"divmod_u32u32"}), + # u32 impl + synthetic_node("divmod_u32u32", 0, {"divmod_u32u32_savestate"}), + synthetic_node( + "divmod_u32u32_savestate", + save_div_state_and_lr, + {"divmod_u32u32_unsafe"}, + ), + synthetic_node("divmod_u32u32_unsafe", 2 * 4, {"__aeabi_idiv0"}), + # s64 aliases + synthetic_node("div_s64s64", 0, {"divmod_s64s64"}), + synthetic_node("__wrap___aeabi_ldiv", 0, {"divmod_s64s64"}), + synthetic_node("__wrap___aeabi_ldivmod", 0, {"divmod_s64s64"}), + # s64 impl + synthetic_node("divmod_s64s64", 0, {"divmod_s64s64_savestate"}), + synthetic_node( + "divmod_s64s64_savestate", + save_div_state_and_lr_64 + (2 * 4), + {"divmod_s64s64_unsafe"}, + ), + synthetic_node( + "divmod_s64s64_unsafe", 4, {"divmod_u64u64_unsafe", "__aeabi_ldiv0"} + ), + # u64 aliases + synthetic_node("div_u64u64", 0, {"divmod_u64u64"}), + synthetic_node("__wrap___aeabi_uldivmod", 0, {"divmod_u64u64"}), + # u64 impl + synthetic_node("divmod_u64u64", 0, {"divmod_u64u64_savestate"}), + synthetic_node( + "divmod_u64u64_savestate", + save_div_state_and_lr_64 + (2 * 4), + {"divmod_u64u64_unsafe"}, + ), + synthetic_node( + "divmod_u64u64_unsafe", (1 + 1 + 2 + 5 + 5 + 2) * 4, {"__aeabi_ldiv0"} + ), + # *_rem + synthetic_node("divod_s64s64_rem", 2 * 4, {"divmod_s64s64"}), + synthetic_node("divod_u64u64_rem", 2 * 4, {"divmod_u64u64"}), + ] + + # src/rp2_common/pico_mem_ops/mem_ops_aeabi.S + ret += [ + synthetic_node("__aeabi_mem_init", 0, {"rom_funcs_lookup"}), + synthetic_node( + "__wrap___aeabi_memset", 0, {"rom_func_lookup(ROM_FUNC_MEMSET)"} + ), + synthetic_node("__wrap___aeabi_memset4", 0, {"__wrap___aeabi_memset8"}), + synthetic_node( + "__wrap___aeabi_memset8", 0, {"rom_func_lookup(ROM_FUNC_MEMSET4)"} + ), + synthetic_node("__wrap___aeabi_memcpy4", 0, {"__wrap___aeabi_memcpy8"}), + synthetic_node( + "__wrap___aeabi_memcpy7", 0, {"rom_func_lookup(ROM_FUNC_MEMCPY4)"} + ), + synthetic_node("__wrap_memset", 0, {"rom_func_lookup(ROM_FUNC_MEMSET)"}), + synthetic_node("__wrap___aeabi_memcpy", 0, {"__wrap_memcpy"}), + synthetic_node("__wrap_memcpy", 0, {"rom_func_lookup(ROM_FUNC_MEMCPY)"}), + ] + + # src/rp2_common/pico_bit_ops/bit_ops_aeabi.S + ret += [ + synthetic_node("__aeabi_bits_init", 0, {"rom_funcs_lookup"}), + synthetic_node("__wrap___clz", 0, {"__wrap___clzsi2"}), + synthetic_node("__wrap___clzl", 0, {"__wrap___clzsi2"}), + synthetic_node("__wrap___clzsi2", 0, {"rom_func_lookup(ROM_FUNC_CLZ32)"}), + synthetic_node("__wrap___ctzsi2", 0, {"rom_func_lookup(ROM_FUNC_CTZ32)"}), + synthetic_node( + "__wrap___popcountsi2", 0, {"rom_func_lookup(ROM_FUNC_POPCOUNT32)"} + ), + synthetic_node("__wrap___clzll", 0, {"__wrap___clzdi2"}), + synthetic_node("__wrap___clzdi2", 4, {"rom_func_lookup(ROM_FUNC_CLZ32)"}), + synthetic_node("__wrap___ctzdi2", 4, {"rom_func_lookup(ROM_FUNC_CTZ32)"}), + synthetic_node( + "__wrap___popcountdi2", 3 * 4, {"rom_func_lookup(ROM_FUNC_POPCOUNT32)"} + ), + synthetic_node("__rev", 0, {"reverse32"}), + synthetic_node("__revl", 0, {"reverse32"}), + synthetic_node("reverse32", 0, {"rom_func_lookup(ROM_FUNC_REVERSE32)"}), + synthetic_node("__revll", 0, {"reverse64"}), + synthetic_node("reverse64", 3 * 4, {"rom_func_lookup(ROM_FUNC_REVERSE32)"}), + ] + + # src/rp2040/boot_stage2/boot2_${name,,}.S for name=W25Q080, + # controlled by `#define PICO_BOOT_STAGE2_{name} 1` in + # src/boards/include/boards/pico.h + ret += [ + # synthetic_node("_stage2_boot", 0), # TODO + ] + + # https://github.com/raspberrypi/pico-bootrom-rp2040 + ret += [ + # synthetic_node("rom_func_lookup(ROM_FUNC_CONNECT_INTERNAL_FLASH)", 0), # TODO + # synthetic_node("rom_func_lookup(ROM_FUNC_FLASH_EXIT_XIP)", 0), # TODO + # synthetic_node("rom_func_lookup(ROM_FUNC_FLASH_FLUSH_CACHE)", 0), # TODO + # synthetic_node("rom_hword_as_ptr(BOOTROM_TABLE_LOOKUP_OFFSET)", 0), # TODO + ] + + return ret + + def mutate_node(self, node: Node) -> None: + if self._PICO_PANIC_FUNCTION and node.funcname.base() == BaseName("panic"): + # inline assembly from src/rp2_common/pico_platform_panic/panic.c + assert node.nstatic == 0 + assert node.ndynamic == 0 + assert len(node.calls) == 0 + node.nstatic += 4 + node.calls[QName(self._PICO_PANIC_FUNCTION)] = False + + +class TinyUSBDevicePlugin: + re_tud_class = re.compile( + r"^\s*#\s*define\s+(?P<k>CFG_TUD_(?:\S{3}|AUDIO|VIDEO|MIDI|VENDOR|USBTMC|DFU_RUNTIME|ECM_RNDIS))\s+(?P<v>\S+).*" + ) + re_tud_entry = re.compile( + r"^\s+\.(?P<meth>\S+)\s*=\s*(?P<impl>[a-zA-Z0-9_]+)(?:,.*)?" + ) + re_tud_if1 = re.compile(r"^\s*#\s*if (\S+)\s*") + re_tud_if2 = re.compile(r"^\s*#\s*if (\S+)\s*\|\|\s*(\S+)\s*") + re_tud_endif = re.compile(r"^\s*#\s*endif\s*") + + tud_drivers: dict[str, set[QName]] # method_name => {method_impls} + + def __init__(self, arg_c_fnames: typing.Collection[str]) -> None: + usbd_c_fname = util.get_zero_or_one( + lambda fname: fname.endswith("/tinyusb/src/device/usbd.c"), arg_c_fnames + ) + + tusb_config_h_fname = util.get_zero_or_one( + lambda fname: fname.endswith("/tusb_config.h"), arg_c_fnames + ) + + if not usbd_c_fname: + self.tud_drivers = {} + return + + assert tusb_config_h_fname + tusb_config: dict[str, bool] = {} + with open(tusb_config_h_fname, "r", encoding="utf-8") as fh: + in_table = False + for line in fh: + line = line.rstrip() + if m := self.re_tud_class.fullmatch(line): + k = m.group("k") + v = m.group("v") + tusb_config[k] = bool(int(v)) + + tud_drivers: dict[str, set[QName]] = {} + with open(usbd_c_fname, "r", encoding="utf-8") as fh: + in_table = False + enabled = True + for line in fh: + line = line.rstrip() + if in_table: + if m := self.re_tud_if1.fullmatch(line): + enabled = tusb_config[m.group(1)] + elif m := self.re_tud_if2.fullmatch(line): + enabled = tusb_config[m.group(1)] or tusb_config[m.group(2)] + elif self.re_tud_endif.fullmatch(line): + enabled = True + if m := self.re_tud_entry.fullmatch(line): + meth = m.group("meth") + impl = m.group("impl") + if meth == "name" or not enabled: + continue + if meth not in tud_drivers: + tud_drivers[meth] = set() + if impl != "NULL": + tud_drivers[meth].add(QName(impl)) + if line.startswith("}"): + in_table = False + elif " _usbd_driver[] = {" in line: + in_table = True + self.tud_drivers = tud_drivers + + def is_intrhandler(self, name: QName) -> bool: + return False + + def init_array(self) -> typing.Collection[QName]: + return [] + + def extra_includes(self) -> typing.Collection[BaseName]: + return [] + + def extra_nodes(self) -> typing.Collection[Node]: + return [] + + def mutate_node(self, node: Node) -> None: + pass + + def indirect_callees( + self, loc: str, line: str + ) -> tuple[typing.Collection[QName], bool] | None: + if "/tinyusb/" not in loc or "/tinyusb/src/host/" in loc or "_host.c:" in loc: + return None + m = util.re_call_other.fullmatch(line) + assert m + call = m.group("func") + if call == "_ctrl_xfer.complete_cb": + ret = { + # QName("process_test_mode_cb"), + QName("tud_vendor_control_xfer_cb"), + } + ret.update(self.tud_drivers["control_xfer_cb"]) + return ret, False + if call.startswith("driver->"): + meth = call[len("driver->") :] + callees = self.tud_drivers[meth] + if len(callees) == 0: + if meth == "sof": + return [QName(f"__indirect_call_with_null_check:{call}")], False + raise ValueError(f"{loc}: no implementors of {meth}") + return callees, False + if call == "event.func_call.func": + # callback from usb_defer_func() + return [ + QName("__indirect_call_with_null_check:event.func_call.func") + ], False + + return None + + def skipmodels(self) -> dict[BaseName, analyze.SkipModel]: + return {} + + +class NewlibPlugin: + def is_intrhandler(self, name: QName) -> bool: + return False + + def init_array(self) -> typing.Collection[QName]: + return [QName("register_fini")] + + def extra_includes(self) -> typing.Collection[BaseName]: + return [ + # register_fini() calls atexit(__libc_fini_array) + BaseName("__libc_fini_array"), + ] + + def extra_nodes(self) -> typing.Collection[Node]: + ret = [] + + # This is accurate to + # /usr/arm-none-eabi/lib/thumb/v6-m/nofp/libg.a as of + # Parabola's arm-none-eabi-newlib 4.5.0.20241231-1. + + # malloc + ret += [ + synthetic_node("free", 8, {"_free_r"}), + synthetic_node("malloc", 8, {"_malloc_r"}), + synthetic_node("realloc", 8, {"_realloc_r"}), + synthetic_node("aligned_alloc", 8, {"_memalign_r"}), + synthetic_node("reallocarray", 24, {"realloc", "__errno"}), + # synthetic_node("_free_r", 0), # TODO + # synthetic_node("_malloc_r", 0), # TODO + # synthetic_node("_realloc_r", 0), # TODO + # synthetic_node("_memalign_r", 0), # TODO + ] + + # execution + ret += [ + synthetic_node("raise", 16, {"_getpid_r"}), + synthetic_node("abort", 8, {"raise", "_exit"}), + synthetic_node("longjmp", 0), + synthetic_node("setjmp", 0), + ] + + # <strings.h> + ret += [ + synthetic_node("memcmp", 12), + synthetic_node("strcmp", 16), + synthetic_node("strlen", 8), + synthetic_node("strncpy", 16), + synthetic_node("strnlen", 8), + ] + + # other + ret += [ + synthetic_node("__errno", 0), + synthetic_node("_getpid_r", 8, {"_getpid"}), + synthetic_node("random", 8), + synthetic_node("register_fini", 8, {"atexit"}), + synthetic_node("atexit", 8, {"__register_exitproc"}), + synthetic_node( + "__register_exitproc", + 32, + { + "__retarget_lock_acquire_recursive", + "__retarget_lock_release_recursive", + }, + ), + synthetic_node("__libc_fini_array", 16, {"_fini"}), + ] + + return ret + + def mutate_node(self, node: Node) -> None: + pass + + def indirect_callees( + self, loc: str, line: str + ) -> tuple[typing.Collection[QName], bool] | None: + return None + + def skipmodels(self) -> dict[BaseName, analyze.SkipModel]: + return {} + + +class LibGCCPlugin: + def is_intrhandler(self, name: QName) -> bool: + return False + + def init_array(self) -> typing.Collection[QName]: + return [] + + def extra_includes(self) -> typing.Collection[BaseName]: + return [] + + def extra_nodes(self) -> typing.Collection[Node]: + # This is accurate to Parabola's arm-none-eabi-gcc 14.2.0-1. + return [ + # /usr/lib/gcc/arm-none-eabi/14.2.0/thumb/v6-m/nofp/libgcc.a + synthetic_node("__aeabi_idiv0", 0), + synthetic_node("__aeabi_ldiv0", 0), + synthetic_node("__aeabi_llsr", 0), + # /usr/lib/gcc/arm-none-eabi/14.2.0/thumb/v6-m/nofp/crti.o + synthetic_node("_fini", 24), + ] + + def mutate_node(self, node: Node) -> None: + pass + + def indirect_callees( + self, loc: str, line: str + ) -> tuple[typing.Collection[QName], bool] | None: + return None + + def skipmodels(self) -> dict[BaseName, analyze.SkipModel]: + return {} diff --git a/build-aux/measurestack/test_analyze.py b/build-aux/measurestack/test_analyze.py new file mode 100644 index 0000000..df205e8 --- /dev/null +++ b/build-aux/measurestack/test_analyze.py @@ -0,0 +1,81 @@ +# build-aux/measurestack/test_analyze.py - Tests for analyze.py +# +# Copyright (C) 2025 Luke T. Shumaker <lukeshu@lukeshu.com> +# SPDX-License-Identifier: AGPL-3.0-or-later + +# pylint: disable=unused-variable + +import re +import typing + +import pytest + +from . import analyze, testutil, util + + +def test_name_base() -> None: + assert analyze.QName("foo.c:bar.1").base() == analyze.BaseName("bar") + + +def test_name_pretty() -> None: + name = analyze.QName("foo.c:bar.1") + assert f"{name}" == "QName('foo.c:bar.1')" + assert f"{name.base()}" == "BaseName('bar')" + assert f"{[name]}" == "[QName('foo.c:bar.1')]" + assert f"{[name.base()]}" == "[BaseName('bar')]" + + +def test_name_eq() -> None: + name = analyze.QName("foo.c:bar.1") + with pytest.raises(AssertionError) as e: + if name == "foo": + pass + assert "comparing QName with str" in str(e) + with pytest.raises(AssertionError) as e: + if name.base() == "foo": + pass + assert "comparing BaseName with str" in str(e) + + +def test_max_call_depth() -> None: + graph: typing.Sequence[tuple[str, typing.Collection[str]]] = [ + ("a", {"b"}), # 1 + ("b", {"c"}), # 2 + ("c", {"d"}), # 3 + ("d", {"e"}), # 4 + ("e", {}), # 5 + ] + + testcases: dict[int, bool] = { + 1: True, + 2: True, + 3: True, + 4: True, + 5: False, + 6: False, + 7: False, + } + + def test_filter(name: analyze.QName) -> tuple[int, bool]: + if str(name.base()) in ["a"]: + return 1, True + return 0, False + + def doit(depth: int, graph_plugin: util.Plugin) -> None: + analyze.analyze( + ci_fnames=[], + app_func_filters={"Main": test_filter}, + app=util.PluginApplication(testutil.nop_location_xform, [graph_plugin]), + cfg_max_call_depth=depth, + ) + + pat = re.compile("^max call depth exceeded: ") + + for depth, should_fail in testcases.items(): + graph_plugin = testutil.GraphProviderPlugin(depth, graph) + + if should_fail: + with pytest.raises(ValueError, match=pat): + doit(depth, graph_plugin) + else: + doit(depth, graph_plugin) diff --git a/build-aux/measurestack/test_app_output.py b/build-aux/measurestack/test_app_output.py new file mode 100644 index 0000000..4653d4e --- /dev/null +++ b/build-aux/measurestack/test_app_output.py @@ -0,0 +1,52 @@ +# build-aux/measurestack/test_app_output.py - Tests for app_output.py +# +# Copyright (C) 2025 Luke T. Shumaker <lukeshu@lukeshu.com> +# SPDX-License-Identifier: AGPL-3.0-or-later + +# pylint: disable=unused-variable + +import contextlib +import io + +from . import analyze, app_output + + +def test_print_group() -> None: + result = analyze.AnalyzeResult( + groups={ + "A": analyze.AnalyzeResultGroup( + rows={ + analyze.QName("short"): analyze.AnalyzeResultVal(nstatic=8, cnt=1), + analyze.QName( + "anamethatisnttoolongbutisnttooshort" + ): analyze.AnalyzeResultVal(nstatic=9, cnt=2), + } + ), + "B": analyze.AnalyzeResultGroup(rows={}), + }, + missing=set(), + dynamic=set(), + included_funcs=set(), + ) + + def location_xform(loc: analyze.QName) -> str: + return str(loc) + + stdout = io.StringIO() + with contextlib.redirect_stdout(stdout): + print() + app_output.print_group(result, location_xform, "A") + app_output.print_group(result, location_xform, "B") + assert ( + stdout.getvalue() + == """ += A =============================== == +anamethatisnttoolongbutisnttooshort 9 * 2 +short 8 +----------------------------------- -- +Total 26 +Maximum 9 +=================================== == += B (empty) = +""" + ) diff --git a/build-aux/measurestack/testutil.py b/build-aux/measurestack/testutil.py new file mode 100644 index 0000000..3c32134 --- /dev/null +++ b/build-aux/measurestack/testutil.py @@ -0,0 +1,134 @@ +# build-aux/measurestack/testutil.py - Utilities for writing tests +# +# Copyright (C) 2025 Luke T. Shumaker <lukeshu@lukeshu.com> +# SPDX-License-Identifier: AGPL-3.0-or-later + +import typing + +from . import analyze, util + +# pylint: disable=unused-variable +__all__ = [ + "aprime_gen", + "aprime_decompose", + "NopPlugin", + "GraphProviderPlugin", + "nop_location_xform", +] + + +def aprime_gen(l: int, n: int) -> typing.Sequence[int]: + """Return an `l`-length sequence of nonnegative + integers such that any `n`-length-or-shorter combination of + members with repeats allowed can be uniquely identified by its + sum. + + (If that were "product" instead of "sum", the obvious solution + would be the first `l` primes.) + + """ + seq = [1] + while len(seq) < l: + x = seq[-1] * n + 1 + seq.append(x) + return seq + + +def aprime_decompose( + aprimes: typing.Sequence[int], tot: int +) -> tuple[typing.Collection[int], typing.Collection[int]]: + ret_idx = [] + ret_val = [] + while tot: + idx = max(i for i in range(len(aprimes)) if aprimes[i] <= tot) + val = aprimes[idx] + ret_idx.append(idx) + ret_val.append(val) + tot -= val + return ret_idx, ret_val + + +class NopPlugin: + def is_intrhandler(self, name: analyze.QName) -> bool: + return False + + def init_array(self) -> typing.Collection[analyze.QName]: + return [] + + def extra_includes(self) -> typing.Collection[analyze.BaseName]: + return [] + + def indirect_callees( + self, loc: str, line: str + ) -> tuple[typing.Collection[analyze.QName], bool] | None: + return None + + def skipmodels(self) -> dict[analyze.BaseName, analyze.SkipModel]: + return {} + + def extra_nodes(self) -> typing.Collection[analyze.Node]: + return [] + + def mutate_node(self, node: analyze.Node) -> None: + pass + + +class GraphProviderPlugin(NopPlugin): + _nodes: typing.Sequence[analyze.Node] + + def __init__( + self, + max_call_depth: int, + graph: typing.Sequence[tuple[str, typing.Collection[str]]], + ) -> None: + seq = aprime_gen(len(graph), max_call_depth) + nodes: list[analyze.Node] = [] + for i, (name, calls) in enumerate(graph): + nodes.append(util.synthetic_node(name, seq[i], calls)) + assert ( + len(graph) + == len(nodes) + == len(set(n.nstatic for n in nodes)) + == len(set(str(n.funcname.base()) for n in nodes)) + ) + self._nodes = nodes + + def extra_nodes(self) -> typing.Collection[analyze.Node]: + return self._nodes + + def decode_nstatic(self, tot: int) -> typing.Collection[str]: + idxs, _ = aprime_decompose([n.nstatic for n in self._nodes], tot) + return [str(self._nodes[i].funcname.base()) for i in idxs] + + def encode_nstatic(self, calls: typing.Collection[str]) -> int: + tot = 0 + d: dict[str, int] = {} + for node in self._nodes: + d[str(node.funcname.base())] = node.nstatic + print(d) + for call in calls: + tot += d[call] + return tot + + def sorted_calls(self, calls: typing.Collection[str]) -> typing.Sequence[str]: + d: dict[str, int] = {} + for node in self._nodes: + d[str(node.funcname.base())] = node.nstatic + + def k(call: str) -> int: + return d[call] + + return sorted(calls, key=k) + + def assert_nstatic(self, act_tot: int, exp_calls: typing.Collection[str]) -> None: + exp_tot = self.encode_nstatic(exp_calls) + if act_tot != exp_tot: + act_str = f"{act_tot}: {self.sorted_calls(self.decode_nstatic(act_tot))}" + exp_str = f"{exp_tot}: {self.sorted_calls(exp_calls)}" + assert ( + False + ), f"act:{act_tot} != exp:{exp_tot}\n\t-exp = {exp_str}\n\t+act = {act_str}" + + +def nop_location_xform(loc: str) -> str: + return loc diff --git a/build-aux/measurestack/util.py b/build-aux/measurestack/util.py new file mode 100644 index 0000000..c94ce07 --- /dev/null +++ b/build-aux/measurestack/util.py @@ -0,0 +1,133 @@ +# build-aux/measurestack/util.py - Analyze stack sizes for compiled objects +# +# Copyright (C) 2024-2025 Luke T. Shumaker <lukeshu@lukeshu.com> +# SPDX-License-Identifier: AGPL-3.0-or-later + +import re +import typing + +from . import analyze, vcg +from .analyze import BaseName, Node, QName, maybe_sorted + +# pylint: disable=unused-variable +__all__ = [ + "synthetic_node", + "read_source", + "get_zero_or_one", + "re_call_other", + "Plugin", + "PluginApplication", +] + + +def synthetic_node( + name: str, nstatic: int, calls: typing.Collection[str] = frozenset() +) -> Node: + n = Node() + + n.funcname = QName(name) + + n.location = "<synthetic>" + n.usage_kind = "static" + n.nstatic = nstatic + n.ndynamic = 0 + + n.calls = dict((QName(c), False) for c in maybe_sorted(calls)) + + return n + + +re_location = re.compile(r"(?P<filename>.+):(?P<row>[0-9]+):(?P<col>[0-9]+)") + + +def read_source(location: str) -> str: + m = re_location.fullmatch(location) + if not m: + raise ValueError(f"unexpected label value {location!r}") + filename = m.group("filename") + row = int(m.group("row")) - 1 + # col = int(m.group("col")) - 1 + with open(filename, "r", encoding="utf-8") as fh: + return fh.readlines()[row].strip() + + +def get_zero_or_one( + pred: typing.Callable[[str], bool], fnames: typing.Collection[str] +) -> str | None: + count = sum(1 for fname in fnames if pred(fname)) + assert count < 2 + if count: + return next(fname for fname in fnames if pred(fname)) + return None + + +re_call_other = re.compile(r".*?\b(?P<func>(?!if\b)[->.a-zA-Z0-9_]+)\(.*") + + +class Plugin(typing.Protocol): + def is_intrhandler(self, name: QName) -> bool: ... + + # init_array returns a list of functions that are placed in the + # `.init_array.*` section; AKA functions marked with + # `__attribute__((constructor))`. + def init_array(self) -> typing.Collection[QName]: ... + + # extra_includes returns a list of functions that are never + # called, but are included in the binary anyway. This may because + # it is an unused method in a used vtable. This may be because it + # is an atexit() callback (we never exit). + def extra_includes(self) -> typing.Collection[BaseName]: ... + + def extra_nodes(self) -> typing.Collection[Node]: ... + def mutate_node(self, node: Node) -> None: ... + def indirect_callees( + self, loc: str, line: str + ) -> tuple[typing.Collection[QName], bool] | None: ... + def skipmodels(self) -> dict[BaseName, analyze.SkipModel]: ... + + +class PluginApplication: + _location_xform: typing.Callable[[str], str] + _plugins: list[Plugin] + + def __init__( + self, location_xform: typing.Callable[[str], str], plugins: list[Plugin] + ) -> None: + self._location_xform = location_xform + self._plugins = plugins + + def extra_nodes(self) -> typing.Collection[Node]: + ret: list[Node] = [] + for plugin in self._plugins: + ret.extend(plugin.extra_nodes()) + return ret + + def mutate_node(self, node: Node) -> None: + for plugin in self._plugins: + plugin.mutate_node(node) + + def indirect_callees( + self, elem: vcg.VCGElem + ) -> tuple[typing.Collection[QName], bool]: + loc = elem.attrs.get("label", "") + line = read_source(loc) + + for plugin in self._plugins: + ret = plugin.indirect_callees(loc, line) + if ret is not None: + assert ( + len(ret[0]) > 0 + ), f"{plugin.__class__.__name__} returning 0 calles for {loc} indicates the code would crash" + return ret + + placeholder = "__indirect_call" + if m := re_call_other.fullmatch(line): + placeholder += ":" + m.group("func") + placeholder += " at " + self._location_xform(elem.attrs.get("label", "")) + return [QName(placeholder)], False + + def skipmodels(self) -> dict[BaseName, analyze.SkipModel]: + ret: dict[BaseName, analyze.SkipModel] = {} + for plugin in self._plugins: + ret.update(plugin.skipmodels()) + return ret diff --git a/build-aux/measurestack/vcg.py b/build-aux/measurestack/vcg.py new file mode 100644 index 0000000..39755e9 --- /dev/null +++ b/build-aux/measurestack/vcg.py @@ -0,0 +1,97 @@ +# build-aux/measurestack/vcg.py - Parse the "VCG" language +# +# Copyright (C) 2024-2025 Luke T. Shumaker <lukeshu@lukeshu.com> +# SPDX-License-Identifier: AGPL-3.0-or-later + +import re +import typing + +# pylint: disable=unused-variable +__all__ = [ + "VCGElem", + "parse_vcg", +] + +# Parse the "VCG" language +# +# https://www.rw.cdl.uni-saarland.de/people/sander/private/html/gsvcg1.html +# +# The formal syntax is found at +# ftp://ftp.cs.uni-sb.de/pub/graphics/vcg/vcg.tgz `doc/grammar.txt`. + + +class VCGElem: + typ: str + lineno: int + attrs: dict[str, str] + + +re_beg = re.compile(r"(edge|node):\s*\{\s*") +_re_tok = r"[a-zA-Z_][a-zA-Z0-9_]*" +_re_str = r'"(?:[^\"]|\\.)*"' +re_attr = re.compile("(" + _re_tok + r")\s*:\s*(" + _re_tok + "|" + _re_str + r")\s*") +re_end = re.compile(r"\}\s*$") +re_skip = re.compile(r"(graph:\s*\{\s*title\s*:\s*" + _re_str + r"\s*|\})\s*") +re_esc = re.compile(r"\\.") + + +def parse_vcg(reader: typing.TextIO) -> typing.Iterator[VCGElem]: + + for lineno, line in enumerate(reader): + pos = 0 + + def _raise(msg: str) -> typing.NoReturn: + nonlocal lineno + nonlocal line + nonlocal pos + e = SyntaxError(msg) + e.lineno = lineno + e.offset = pos + e.text = line + raise e + + if re_skip.fullmatch(line): + continue + + elem = VCGElem() + elem.lineno = lineno + + m = re_beg.match(line, pos=pos) + if not m: + _raise("does not look like a VCG line") + elem.typ = m.group(1) + pos = m.end() + + elem.attrs = {} + while True: + if re_end.match(line, pos=pos): + break + m = re_attr.match(line, pos=pos) + if not m: + _raise("unexpected character") + k = m.group(1) + v = m.group(2) + if k in elem.attrs: + _raise(f"duplicate key: {k!r}") + if v.startswith('"'): + + def unesc(esc: re.Match[str]) -> str: + match esc.group(0)[1:]: + case "n": + return "\n" + case '"': + return '"' + case "\\": + return "\\" + case _: + _raise(f"invalid escape code {esc.group(0)!r}") + + v = re_esc.sub(unesc, v[1:-1]) + elem.attrs[k] = v + pos = m.end() + + del _raise + del pos + del line + del lineno + yield elem diff --git a/build-aux/requirements.txt b/build-aux/requirements.txt new file mode 100644 index 0000000..e6044e0 --- /dev/null +++ b/build-aux/requirements.txt @@ -0,0 +1,11 @@ +# build-aux/requirements.txt - List of Python dev requirements +# +# Copyright (C) 2024-2025 Luke T. Shumaker <lukeshu@lukeshu.com> +# SPDX-License-Identifier: AGPL-3.0-or-later + +mypy +types-gdb>=15.0.0.20241204 # https://github.com/python/typeshed/pull/13169 +black +isort +pylint +pytest diff --git a/build-aux/stack.c.gen b/build-aux/stack.c.gen index 9325791..713630a 100755 --- a/build-aux/stack.c.gen +++ b/build-aux/stack.c.gen @@ -1,9 +1,14 @@ -#!/usr/bin/env bash -# stack.c.gen - Analyze stack sizes for compiled objects +#!/usr/bin/env python3 +# build-aux/stack.c.gen - Analyze stack sizes for compiled objects # -# Copyright (C) 2024 Luke T. Shumaker <lukeshu@lukeshu.com> +# Copyright (C) 2024-2025 Luke T. Shumaker <lukeshu@lukeshu.com> # SPDX-License-Identifier: AGPL-3.0-or-later -for obj in "$@"; do - echo "// $obj" -done +import os.path +import sys + +sys.path.insert(0, os.path.normpath(os.path.join(__file__, ".."))) +import measurestack # pylint: disable=wrong-import-position + +if __name__ == "__main__": + measurestack.main() diff --git a/build-aux/stack.py b/build-aux/stack.py deleted file mode 100644 index c1e36d3..0000000 --- a/build-aux/stack.py +++ /dev/null @@ -1,184 +0,0 @@ -#!/usr/bin/env python3 -import re -import sys -import typing - -# Parse the "VCG" language -# -# https://www.rw.cdl.uni-saarland.de/people/sander/private/html/gsvcg1.html -# -# The formal syntax is found at -# ftp://ftp.cs.uni-sb.de/pub/graphics/vcg/vcg.tgz `doc/grammar.txt`. - - -class VCGElem: - typ: str - lineno: int - attrs: dict[str, str] - - -def parse_vcg(reader: typing.TextIO) -> typing.Iterator[VCGElem]: - re_beg = re.compile(r"(edge|node):\s*\{\s*") - _re_tok = r"[a-zA-Z_][a-zA-Z0-9_]*" - _re_str = r'"(?:[^\"]|\\.)*"' - re_attr = re.compile( - "(" + _re_tok + r")\s*:\s*(" + _re_tok + "|" + _re_str + r")\s*" - ) - re_end = re.compile(r"\}\s*$") - re_skip = re.compile(r"(graph:\s*\{\s*title\s*:\s*" + _re_str + r"\s*|\})\s*") - re_esc = re.compile(r"\\.") - - for lineno, line in enumerate(reader): - pos = 0 - - def _raise(msg: str) -> typing.NoReturn: - nonlocal lineno - nonlocal line - nonlocal pos - e = SyntaxError(msg) - e.lineno = lineno - e.offset = pos - e.text = line - raise e - - if re_skip.fullmatch(line): - continue - - elem = VCGElem() - elem.lineno = lineno - - m = re_beg.match(line, pos=pos) - if not m: - _raise("does not look like a VCG line") - elem.typ = m.group(1) - pos = m.end() - - elem.attrs = {} - while True: - if re_end.match(line, pos=pos): - break - m = re_attr.match(line, pos=pos) - if not m: - _raise("unexpected character") - k = m.group(1) - v = m.group(2) - if k in elem.attrs: - _raise(f"duplicate key: {repr(k)}") - if v.startswith('"'): - - def unesc(esc: re.Match[str]) -> str: - match esc.group(0)[1:]: - case "n": - return "\n" - case '"': - return '"' - case "\\": - return "\\" - case _: - _raise(f"invalid escape code {repr(esc.group(0))}") - - v = re_esc.sub(unesc, v[1:-1]) - elem.attrs[k] = v - pos = m.end() - - yield elem - - -class Node: - # from .title (`static` functions are prefixed with the - # compilation unit .c file, which is fine, we'll just leave it). - funcname: str - # .label is "{funcname}\n{location}\n{nstatic} bytes (static}\n{ndynamic} dynamic objects" - location: str - nstatic: int - ndynamic: int - - # edges with .sourcename set to this node - calls: set[str] - -def main() -> None: - re_label = re.compile( - r"(?P<funcname>[^\n]+)\n" - + r"(?P<location>[^\n]+:[0-9]+:[0-9]+)\n" - + r"(?P<nstatic>[0-9]+) bytes \(static\)\n" - + r"(?P<ndynamic>[0-9]+) dynamic objects", - flags=re.MULTILINE, - ) - - graph: dict[str, Node] = dict() - - for elem in parse_vcg(sys.stdin): - match elem.typ: - case "node": - node = Node() - node.calls = set() - skip = False - for k, v in elem.attrs.items(): - match k: - case "title": - node.funcname = v - case "label": - if elem.attrs.get("shape", "") != "ellipse": - m = re_label.fullmatch(v) - if not m: - raise ValueError( - f"unexpected label value {repr(v)}" - ) - node.location = m.group("location") - node.nstatic = int(m.group("nstatic")) - node.ndynamic = int(m.group("ndynamic")) - case "shape": - if v != "ellipse": - raise ValueError(f"unexpected shape value {repr(v)}") - skip = True - case _: - raise ValueError(f"unknown edge key {repr(k)}") - if not skip: - if node.funcname in graph: - raise ValueError(f"duplicate node {repr(node.funcname)}") - graph[node.funcname] = node - case "edge": - caller: str | None = None - callee: str | None = None - for k, v in elem.attrs.items(): - match k: - case "sourcename": - caller = v - case "targetname": - callee = v - case "label": - pass - case _: - raise ValueError(f"unknown edge key {repr(k)}") - if caller is None or callee is None: - raise ValueError(f"incomplete edge: {repr(elem.attrs)}") - if caller not in graph: - raise ValueError(f"unknown caller: {caller}") - graph[caller].calls.add(callee) - case _: - raise ValueError(f"unknown elem type {repr(elem.typ)}") - - # x - - missing: set[str] = set() - def nstatic(funcname: str) -> int: - if funcname not in graph: - missing.add(funcname) - return 0 - node = graph[funcname] - return node.nstatic + max([0, *[nstatic(call) for call in node.calls]]) - - namelen = max(len(name) for name in graph if name.endswith("_cr")) - print(("="*namelen)+" =======") - - for funcname in graph: - if funcname.endswith("_cr"): - print(f"{funcname}\t{nstatic(funcname)}") - - print(("="*namelen)+" =======") - - for funcname in sorted(missing): - print(f"{funcname}\tmissing") - -if __name__ == "__main__": - main() diff --git a/build-aux/stack.sh b/build-aux/stack.sh deleted file mode 100755 index 4a8a12e..0000000 --- a/build-aux/stack.sh +++ /dev/null @@ -1,2 +0,0 @@ -#!/bin/sh -make >&2 && find build -name '*.ci' -exec cat -- {} + | python ./stack.py diff --git a/build-aux/tent-graph b/build-aux/tent-graph new file mode 100755 index 0000000..25c58c5 --- /dev/null +++ b/build-aux/tent-graph @@ -0,0 +1,180 @@ +#!/usr/bin/env python3 +# build-aux/tent-graph - Take dbg_noncache=True dbg_nstatic=True stack.c on stdin, and produce a tent graph SVG on stdout +# +# Copyright (C) 2025 Luke T. Shumaker <lukeshu@lukeshu.com> +# SPDX-License-Identifier: AGPL-3.0-or-later + +import ast +import re +import sys + + +class Block: + title: str + parent: "Block|None" + children: list["Block"] + nbytes: int + + def __init__(self, *, title: str, nbytes: int, parent: "Block|None") -> None: + self.title = title + self.parent = parent + self.children = [] + self.nbytes = nbytes + + @property + def rows(self) -> int: + if not self.children: + return 1 + return sum(c.rows for c in self.children) + + @property + def sum_nbytes(self) -> int: + if not self.children: + return self.nbytes + return self.nbytes + max(c.sum_nbytes for c in self.children) + + def prune(self) -> None: + tgt = self.sum_nbytes - self.nbytes + self.children = [c for c in self.children if c.sum_nbytes == tgt] + + +re_line = re.compile( + r"^//dbg-nstatic:(?P<indent>(?: -)*) QName\((?P<func>.*)\)\t(?P<size>[0-9]+)$" +) + + +def parse() -> list[Block]: + roots: list[Block] = [] + + stack: list[Block] = [] + for line in sys.stdin: + m = re_line.fullmatch(line.strip()) + if not m: + continue + + depth = len(m.group("indent")) // 2 + func = ast.literal_eval(m.group("func")) + size = int(m.group("size"), 10) + + stack = stack[:depth] + + block = Block( + title=func, + nbytes=size, + parent=stack[-1] if stack else None, + ) + if block.parent: + block.parent.children.append(block) + else: + roots.append(block) + stack.append(block) + + return roots + + +def render(roots: list[Block]) -> None: + total_nbytes = max(r.sum_nbytes for r in roots) + total_rows = sum(r.rows for r in roots) + + img_w = 1920 + img_h = 948 + + details_h = 16 + text_yoff = 12 + text_xoff = 3 + + main_h = img_h - details_h + nbyte_h = main_h / total_nbytes + row_w = img_w / total_rows + + print( + f"""<?xml version="1.0" standalone="no"?> +<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> +<svg version="1.1" width="{img_w}" height="{img_h}" onload="init(evt)" viewBox="0 0 {img_w} {img_h}" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"> +<style type="text/css"> + .func_g:hover {{ stroke:black; stroke-width:0.5; }} + .func_g rect {{ rx: 2px; ry: 2px; }} + rect#background {{ fill: #EEEEEE; }} + text {{ font-size: 12px; font-family: Verdana; fill: rgb(0,0,0); }} +</style> +<script type="text/ecmascript"> +<![CDATA[ + var details; + function init(evt) {{ details = document.getElementById("details").firstChild; }} + function s(info) {{ details.nodeValue = "Function: " + info; }} + function c() {{ details.nodeValue = ' '; }} +]]> +</script> +<rect id="background" x="0" y="0" width="{img_w}" height="{img_h}" /> +<text text-anchor="" x="{text_xoff}" y="{img_h-details_h+text_yoff}" id="details"> </text>""" + ) + + min_nbytes = roots[0].nbytes + max_nbytes = 0 + + def visit(b: Block) -> None: + nonlocal min_nbytes + nonlocal max_nbytes + min_nbytes = min(min_nbytes, b.nbytes) + max_nbytes = max(max_nbytes, b.nbytes) + for c in b.children: + visit(c) + + for r in roots: + visit(r) + + def print_block(block: Block, nbyte: int, row: int) -> None: + nonlocal min_nbytes + nonlocal max_nbytes + + if block.nbytes: + hue = 100 - int( + ((block.nbytes - min_nbytes) / (max_nbytes - min_nbytes)) * 100 + ) + + x = row * row_w + y = nbyte * nbyte_h + w = max(1, block.rows * row_w - 1) + h = block.nbytes * nbyte_h + title = f"{block.title} = {block.nbytes} / {block.sum_nbytes} bytes" + + nonlocal main_h + print(f'<g class="func_g" onmouseover="s(\'{title}\')" onmouseout="c()">') + print(f"\t<title>{title}</title>") + print( + f'\t<rect x="{x}" y="{main_h-y-h}" width="{w}" height="{h}" fill="hsl({hue} 60% 60%)" />' + ) + + short_title = title.rsplit(":", 1)[-1] + if h > details_h and w > len(short_title) * 10: + print( + f'\t<text x="{x+text_xoff}" y="{main_h-y-h+text_yoff}">{short_title}</text>' + ) + print("</g>") + + def sort_key(c: Block) -> int: + return c.sum_nbytes + + for c in sorted(block.children, key=sort_key, reverse=True): + print_block(c, nbyte + block.nbytes, row) + row += c.rows + + row = 0 + for r in roots: + print_block(r, 0, row) + row += r.rows + + print("</svg>") + + +def main() -> None: + roots = parse() + + # tgt = max(r.sum_nbytes for r in roots) + # roots = [r for r in roots if r.sum_nbytes == tgt] + + render(roots) + + +if __name__ == "__main__": + main() diff --git a/build-aux/valgrind b/build-aux/valgrind new file mode 100755 index 0000000..0700e4d --- /dev/null +++ b/build-aux/valgrind @@ -0,0 +1,16 @@ +#!/bin/sh +# build-aux/valgrind - Wrapper around valgrind to keep flags consistent +# +# Copyright (C) 2025 Luke T. Shumaker <lukeshu@lukeshu.com> +# SPDX-License-Identifier: AGPL-3.0-or-later + +exec \ + valgrind \ + --fair-sched=yes \ + --error-exitcode=2 \ + --leak-check=full \ + --show-leak-kinds=all \ + --errors-for-leak-kinds=all \ + --show-error-list=all \ + -- \ + "$@" |