summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--Makefile5
-rwxr-xr-xavstack.pl271
-rwxr-xr-xscript/static-stack-analyze.pl303
3 files changed, 306 insertions, 273 deletions
diff --git a/Makefile b/Makefile
index 201820c..f21f9b9 100644
--- a/Makefile
+++ b/Makefile
@@ -139,12 +139,12 @@ endif
stack: default
${QUIET}test -n "${OBJDUMP}"
${QUIET}test -n "${ARCH_SHORTNAME}"
- ${QUIET}./static-stack-analyze.pl ${OBJDUMP} ${ARCH_SHORTNAME} ${OBJECTS}
+ ${QUIET}script/static-stack-analyze.pl ${OBJDUMP} ${ARCH_SHORTNAME} ${OBJECTS}
stackm: default
${QUIET}test -n "${OBJDUMP}"
${QUIET}test -n "${ARCH_SHORTNAME}"
- ${QUIET}./static-stack-analyze.pl --machine-readable ${OBJDUMP} ${ARCH_SHORTNAME} ${OBJECTS}
+ ${QUIET}script/static-stack-analyze.pl --machine-readable ${OBJDUMP} ${ARCH_SHORTNAME} ${OBJECTS}
clean: arch_clean
rm -f build/system.elf
@@ -166,6 +166,7 @@ help: arch_help
@echo " kout_nop -- Do not write output to stdout / serial console"
@echo " ostream -- include C++ ostream standard library"
@echo " trace_malloc -- trace mpmalloc/mpcalloc/mprealloc calls on stdout"
+ @echo " stack_usage -- Generate .su files for stack usage estimation (-> make stack)"
@echo
@echo "${arch} drivers:"
@ls -1 src/arch/${arch}/driver | fgrep .c | cut -d . -f 1 | sed 's/^/ /'
diff --git a/avstack.pl b/avstack.pl
deleted file mode 100755
index 11328e7..0000000
--- a/avstack.pl
+++ /dev/null
@@ -1,271 +0,0 @@
-#!/usr/bin/perl -w
-# avstack.pl: AVR stack checker
-# Copyright (C) 2013 Daniel Beer <dlbeer@gmail.com>
-# Copyright (C) 2018 Daniel Friesel <daniel.friesel@uni-osnabrueck.de>
-#
-# Permission to use, copy, modify, and/or distribute this software for
-# any purpose with or without fee is hereby granted, provided that the
-# above copyright notice and this permission notice appear in all
-# copies.
-#
-# THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL
-# WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED
-# WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE
-# AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL
-# DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
-# PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
-# TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
-# PERFORMANCE OF THIS SOFTWARE.
-#
-# Usage
-# -----
-#
-# This script requires that you compile your code with -fstack-usage.
-# This results in GCC/G++ generating a .su file for each .o file. Once you
-# have these, do:
-#
-# ./avstack.pl <objdump binary> <call cost> <object files ...>
-#
-# This will disassemble .o files to construct a call graph, and read
-# frame size information from .su. The call graph is traced to find, for
-# each function:
-#
-# - Call height: the maximum call height of any callee, plus 1
-# (defined to be 1 for any function which has no callees).
-#
-# - Inherited frame: the maximum *inherited* frame of any callee, plus
-# the GCC-calculated frame size of the function in question.
-#
-# Using these two pieces of information, we calculate a cost (estimated
-# peak stack usage) for calling the function. Functions are then listed
-# on stdout in decreasing order of cost.
-#
-# Functions which are recursive are marked with an 'R' to the left of
-# them. Their cost is calculated for a single level of recursion.
-#
-# The peak stack usage of your entire program can usually be estimated
-# as the stack cost of "main", plus the maximum stack cost of any
-# interrupt handler which might execute.
-
-use strict;
-use warnings;
-use 5.010;
-
-# Configuration: set these as appropriate for your architecture/project.
-
-my $objdump = shift;
-my $call_cost = shift;
-
-# First, we need to read all object and corresponding .su files. We're
-# gathering a mapping of functions to callees and functions to frame
-# sizes. We're just parsing at this stage -- callee name resolution
-# comes later.
-
-my %frame_size; # "func@file" -> size
-my %call_graph; # "func@file" -> {callees}
-my %addresses; # "addr@file" -> "func@file"
-
-my %global_name; # "func" -> "func@file"
-my %ambiguous; # "func" -> 1
-
-foreach (@ARGV) {
-
- # Disassemble this object file to obtain a callees. Sources in the
- # call graph are named "func@file". Targets in the call graph are
- # named either "offset@file" or "funcname". We also keep a list of
- # the addresses and names of each function we encounter.
- my $objfile = $_;
- my $source;
-
- open( DISASSEMBLY, "$objdump -Cdr $objfile|" )
- || die "Can't disassemble $objfile";
- while (<DISASSEMBLY>) {
- chomp;
-
- if (/^([0-9a-fA-F]+) <(.*)>:/) {
- my $a = $1;
- my $name = $2;
-
- $source = "$name\@$objfile";
- $call_graph{$source} = {};
- $ambiguous{$name} = 1 if defined( $global_name{$name} );
- $global_name{$name} = "$name\@$objfile";
-
- $a =~ s/^0*//;
- $addresses{"$a\@$objfile"} = "$name\@$objfile";
- }
-
- if (/: R_[A-Za-z0-9_]+_(?:CALL|PLT32|ABS16)[ \t]+(.*)/) {
- my $t = $1;
-
- if ( $t eq ".text" ) {
- $t = "\@$objfile";
- }
- elsif ( $t =~ /^\.text\+0x(.*)$/ ) {
- $t = "$1\@$objfile";
- }
-
- $t =~ s{-0x4$}{};
-
- $call_graph{$source}->{$t} = 1;
- }
- }
- close(DISASSEMBLY);
-
- # Extract frame sizes from the corresponding .su file.
- if ( $objfile =~ /^(.*).o$/ ) {
- my $sufile = "$1.su";
-
- open( SUFILE, "<$sufile" ) || die "Can't open $sufile";
- while (<SUFILE>) {
- if (
- m{ ^ [^:]+ : \d+ : \d+ : [^\t]+? \s (?<name> \S+ ) \( .*? \)
- (?: \s* \[with [^]]*\])?
- \t
- (?<size> \d+ )}x
- )
- {
- $frame_size{"$+{name}\@$objfile"} = $+{size} + $call_cost;
- }
- else {
- say "No match $_";
- }
- }
- close(SUFILE);
- }
-}
-
-# In this step, we enumerate each list of callees in the call graph and
-# try to resolve the symbols. We omit ones we can't resolve, but keep a
-# set of them anyway.
-
-my %unresolved;
-
-foreach ( keys %call_graph ) {
- my $from = $_;
- my $callees = $call_graph{$from};
- my %resolved;
-
- foreach ( keys %$callees ) {
- my $t = $_;
-
- if ( defined( $addresses{$t} ) ) {
- $resolved{ $addresses{$t} } = 1;
- }
- elsif ( defined( $global_name{$t} ) ) {
- $resolved{ $global_name{$t} } = 1;
- warn "Ambiguous resolution: $t" if defined( $ambiguous{$t} );
- }
- elsif ( defined( $call_graph{$t} ) ) {
- $resolved{$t} = 1;
- }
- else {
- $unresolved{$t} = 1;
- }
- }
-
- $call_graph{$from} = \%resolved;
-}
-
-# Create fake edges and nodes to account for dynamic behaviour.
-$call_graph{"INTERRUPT"} = {};
-
-foreach ( keys %call_graph ) {
- $call_graph{"INTERRUPT"}->{$_} = 1 if /^__vector_/;
-}
-
-# Trace the call graph and calculate, for each function:
-#
-# - inherited frames: maximum inherited frame of callees, plus own
-# frame size.
-# - height: maximum height of callees, plus one.
-# - recursion: is the function called recursively (including indirect
-# recursion)?
-
-my %has_caller;
-my %visited;
-my %total_cost;
-my %call_depth;
-
-sub trace {
- my $f = shift;
-
- if ( $visited{$f} ) {
- $visited{$f} = "R" if $visited{$f} eq "?";
- return;
- }
-
- $visited{$f} = "?";
-
- my $max_depth = 0;
- my $max_frame = 0;
-
- my $targets = $call_graph{$f} || die "Unknown function: $f";
- if ( defined($targets) ) {
- foreach ( keys %$targets ) {
- my $t = $_;
-
- $has_caller{$t} = 1;
- trace($t);
-
- my $is = $total_cost{$t};
- my $d = $call_depth{$t};
-
- $max_frame = $is if $is > $max_frame;
- $max_depth = $d if $d > $max_depth;
- }
- }
-
- $call_depth{$f} = $max_depth + 1;
- $total_cost{$f} = $max_frame + ( $frame_size{$f} || 0 );
- $visited{$f} = " " if $visited{$f} eq "?";
-}
-
-foreach ( keys %call_graph ) { trace $_; }
-
-# Now, print results in a nice table.
-printf " %-30s %8s %8s %8s\n", "Func", "Cost", "Frame", "Height";
-print "------------------------------------";
-print "------------------------------------\n";
-
-my $max_iv = 0;
-my $main = 0;
-
-foreach ( sort { $total_cost{$b} <=> $total_cost{$a} } keys %visited ) {
- my $name = $_;
-
- if (/^(.*)@(.*)$/) {
- $name = $1 unless $ambiguous{$name};
- }
-
- my $tag = $visited{$_};
- my $cost = $total_cost{$_};
-
- $name = $_ if $ambiguous{$name};
- $tag = ">" unless $has_caller{$_};
-
- if (/^__vector_/) {
- $max_iv = $cost if $cost > $max_iv;
- }
- elsif (/^main@/) {
- $main = $cost;
- }
-
- if ( $ambiguous{$name} ) { $name = $_; }
-
- printf "%s %-30s %8d %8d %8d\n", $tag, $name, $cost,
- $frame_size{$_} || 0, $call_depth{$_};
-}
-
-print "\n";
-
-print "Peak execution estimate (main + worst-case IV):\n";
-printf " main = %d, worst IV = %d, total = %d\n",
- $total_cost{ $global_name{"main"} },
- $total_cost{"INTERRUPT"},
- $total_cost{ $global_name{"main"} } + $total_cost{"INTERRUPT"};
-
-print "\n";
-
-print "The following functions were not resolved:\n";
-foreach ( keys %unresolved ) { print " $_\n"; }
diff --git a/script/static-stack-analyze.pl b/script/static-stack-analyze.pl
new file mode 100755
index 0000000..3089d3d
--- /dev/null
+++ b/script/static-stack-analyze.pl
@@ -0,0 +1,303 @@
+#!/usr/bin/env perl
+
+use strict;
+use warnings;
+use 5.010;
+
+use File::Slurp qw(read_file);
+use Getopt::Long;
+use List::Util qw(uniq);
+
+our $VERSION = '0.00';
+my $machine_readable = 0;
+
+GetOptions(
+ 'm|machine-readable!' => \$machine_readable,
+);
+
+if (@ARGV < 3) {
+ die("Usage: $0 <objdump binary> <architecture> <oject files ...>\n");
+}
+
+my %arch_data = (
+ x64 => {
+ # For each function call, the 8-Byte return address is pushed onto the stack.
+ call_cost => 8,
+ call_relocation => 'R_X86_64_PLT32',
+ },
+ avr => {
+ # On each function call, the 2-Byte return address is pushed onto the stack.
+ # (unhandled exception: ATTiny2313 and other devices with <= 256 Bytes of RAM)
+ call_cost => 2,
+ call_relocation => 'R_AVR_CALL',
+ },
+ msp430 => {
+ # For each function call, the 4-Byte (20 bits at 2-Byte alignment) return
+ # address is pushed onto the stack.
+ call_cost => 4,
+ call_relocation => 'R_MSP430X_ABS16',
+ },
+ msp430large => {
+ # For each function call, the 4-Byte (20 bits at 2-Byte alignment) return
+ # address is pushed onto the stack.
+ call_cost => 4,
+ call_relocation => 'R_MSP430X_ABS20_ADR_DST',
+ },
+);
+
+my %addresses;
+my %call_graph;
+my %frame_size;
+
+my ($objdump_path, $arch, @object_files) = @ARGV;
+
+sub add_call {
+ my ($parent, $child) = @_;
+
+ push(@{$call_graph{$parent}{children}}, $child);
+ push(@{$call_graph{$child}{parents}}, $parent);
+
+ #say "$parent -> $child;";
+
+ if ($parent =~ m{ ^ __vector_ }x) {
+ push(@{$call_graph{INTERRUPT}{children}}, $parent);
+ push(@{$call_graph{$parent}{parents}}, 'INTERRUPT');
+ }
+}
+
+sub trace {
+ my ($function) = @_;
+
+ my $node = $call_graph{$function};
+
+ if ($node->{visited}) {
+ $node->{recursive} = 1;
+ return;
+ }
+
+ $node->{visited} = 1;
+ $node->{max_depth} //= 1;
+ $node->{max_cost} //= $frame_size{$function}{size} // 0;
+
+ for my $child (@{$node->{children} // []}) {
+ trace($child);
+ my $child_node = $call_graph{$child};
+ if ($child_node->{max_depth} + 1 > $node->{max_depth}) {
+ $node->{max_depth} = $child_node->{max_depth} + 1;
+ }
+ if (defined $frame_size{$function}{size}) {
+ my $call_cost = $child_node->{max_cost} + $arch_data{$arch}{call_cost} + $frame_size{$function}{size};
+ if ($call_cost > $node->{max_cost}) {
+ $node->{max_cost} = $call_cost;
+ }
+ }
+ else {
+ say "Frame size of $function is unknown!";
+ $node->{unknown_child} = 1;
+ my $call_cost = $child_node->{max_cost} + $arch_data{$arch}{call_cost};
+ if ($call_cost > $node->{max_cost}) {
+ $node->{max_cost} = $call_cost;
+ }
+ }
+ if ($child_node->{unknown_child}) {
+ $node->{unknown_child} = 1;
+ }
+ }
+
+ $node->{visited} = 0;
+}
+
+sub check_recursive {
+ my ($function) = @_;
+ my $node = $call_graph{$function};
+
+ if ($node->{visited}) {
+ return;
+ }
+
+ $node->{visited} = 1;
+
+ for my $child (@{$node->{children} // []}) {
+ if ($call_graph{$child}{recursive} or $call_graph{$child}{calls_recursive}) {
+ $node->{calls_recursive} = 1;
+ }
+ }
+
+ if ($node->{recursive} or $node->{calls_recursive}) {
+ for my $parent (@{$node->{parents} // []}) {
+ check_recursive($parent);
+ }
+ }
+
+ $node->{visited} = 0;
+}
+
+for my $file (@object_files) {
+ my $dump = qx{$objdump_path -Cdr $file};
+ my $current_function = 'NONE';
+ my $call_reloc = $arch_data{$arch}{call_relocation};
+
+ my %address;
+
+ for my $line (split(qr{\n}, $dump)) {
+ if ($line =~ m{ ^ (?<address> [0-9a-fA-Z]+ ) \s+ < (?<function> .* ) > : $}x) {
+ $current_function = $+{function};
+ my $addr = $+{address};
+
+ $current_function =~ s{ \s \[ clone \s \S+ \] $ }{}x;
+ $addr =~ s{ ^ 0* }{}x;
+
+ $address{$addr} = $current_function;
+ }
+ elsif ($line =~ m{ : \s+ ${call_reloc} \s+ (?<function> .+ ) }x) {
+ my $function = $+{function};
+
+ if ($function =~ m{ ^ [.] L \d+ $ }x) {
+ # MSP430, doesn't seem related to function calls
+ next;
+ }
+
+ # x64 fixup. TODO what's the meaning of this? Edge cases to consider?
+ $function =~ s{ -0x4 $ }{}x;
+
+ if ($function =~ m{ ^ [.] text [+] 0x (?<addr> [0-9a-fA-F]+ ) }x) {
+ $function = $address{$+{addr}} // 'UNRESOLVED';
+ }
+ add_call($current_function, $function);
+ }
+ }
+
+ my $su_file = $file;
+ $su_file =~ s{[.]o$}{.su};
+
+ for my $line (read_file($su_file)) {
+ if ($line =~ m{ ^ (?<file> [^:]+ ) : (?<line> [^:]+ ) : (?<column> [^:]+ )
+ : (?: const \s+ )? (?: virtual \s+ )?
+ (?<return_type> \S+ ) (?: \s (?<function> [^\t]+ ))?
+ \t (?<size> [^\t]+ ) \t (?<estimate> .+ ) $ }x) {
+
+ my $function = $+{function} // $+{return_type};
+ my $size = $+{size};
+ my $estimate = $+{estimate};
+
+ $frame_size{$function} = {
+ size => $size,
+ estimate => $estimate,
+ };
+
+ # For C(-ish) functions, objdump does not give the function signature,
+ # whereas .su does. Therefore, for each demangled function with
+ # signature, we create a duplicate entry without it.
+ if ($function =~ s{ \( .* \) $ }{}x) {
+ $frame_size{$function} = {
+ size => $size,
+ estimate => $estimate,
+ duplicate => 1,
+ };
+ }
+
+ # There's also some disagreement about "short" vs. "short int" and
+ # "long" vs. "long int"...
+ }
+ else {
+ say "$su_file: Cannot parse $line";
+ }
+ }
+}
+
+for my $function (keys %call_graph) {
+ @{$call_graph{$function}{children}} = uniq @{$call_graph{$function}{children}};
+ @{$call_graph{$function}{parents}} = uniq @{$call_graph{$function}{parents}};
+}
+
+for my $function (keys %call_graph) {
+ trace($function);
+}
+
+for my $function (keys %call_graph) {
+ check_recursive($function);
+}
+
+if (not $machine_readable) {
+ printf("%2s %40s %10s%1s %10s%1s %10s\n", q{}, 'Function', 'Inclusive', '', 'Exclusive', '', 'Height');
+}
+
+for my $function (reverse sort { ($call_graph{$a}{max_cost} <=> $call_graph{$b}{max_cost}) || ($a cmp $b) } keys %call_graph) {
+
+ my $node = $call_graph{$function};
+ my $info = '';
+
+ if ($node->{recursive}) {
+ $info .= 'R';
+ }
+ elsif ($node->{calls_recursive}) {
+ $info .= 'r';
+ }
+ else {
+ $info .= ' ';
+ }
+
+ if (@{$node->{parents} // []} == 0) {
+ $info .= '>';
+ }
+ if ($machine_readable) {
+ printf("%s!%d!%d!%d!%d!%d!%d!%d!%d\n",
+ $function,
+ $call_graph{$function}{max_cost},
+ $frame_size{$function}{size} // 0,
+ $call_graph{$function}{max_depth},
+ $node->{recursive} || 0,
+ $node->{calls_recursive} || 0,
+ $node->{parents} || 0,
+ $call_graph{$function}{unknown_child} ? 1 : 0,
+ defined $frame_size{$function}{size} ? 1 : 0,
+ );
+ }
+ else {
+ printf("%2s %40s %10d%1s %10d%1s %10d\n",
+ $info, substr($function, 0, 40),
+ $call_graph{$function}{max_cost},
+ $call_graph{$function}{unknown_child} ? '+' : ' ',
+ $frame_size{$function}{size} // 0,
+ defined $frame_size{$function}{size} ? ' ' : '?',
+ $call_graph{$function}{max_depth});
+ }
+}
+
+__END__
+
+=head1 NAME
+
+=head1 SYNOPSIS
+
+=head1 VERSION
+
+=head1 DESCRIPTION
+
+=head1 OPTIONS
+
+=over
+
+=back
+
+=head1 EXIT STATUS
+
+=head1 CONFIGURATION
+
+None.
+
+=head1 DEPENDENCIES
+
+=over
+
+=back
+
+=head1 BUGS AND LIMITATIONS
+
+=head1 AUTHOR
+
+Copyright (C) 2018 by Daniel Friesel E<lt>derf@finalrewind.orgE<gt>
+
+=head1 LICENSE
+
+ 0. You just DO WHAT THE FUCK YOU WANT TO.