tos-ramsize

tinyos-2.x.rar

	($res, $stack, $size) = match_constant_push_1 ($addr);
	if ($res) {
	    replace_insn ($addr, $size, $stack, "constant_push");
	}

	($res, $stack, $size) = match_constant_push_2 ($addr);
	if ($res) {
	    replace_insn ($addr, $size, $stack, "constant_push");
	}

	($res, $stack, $size) = match_constant_push_3 ($addr);
	if ($res) {
	    replace_insn ($addr, $size, $stack, "constant_push");
	}

	($res, $stack, $size) = match_constant_pop_1($addr);
	if ($res) {
	    replace_insn ($addr, $size, $stack, "constant_pop");
	}

	($res, $stack, $size) = match_constant_pop_2($addr);
	if ($res) {
	    replace_insn ($addr, $size, $stack, "constant_pop");
	}

	($res, $stack, $size) = match_constant_stack_op($addr);
	if ($res) {
	    if ($size > 0) {
		replace_insn ($addr, $size, $stack, "constant_push");
	    } else {
		replace_insn ($addr, $size, $stack, "constant_pop");
	    }
	}

	($res, $stack, $size) = match_constant_pop_4 ($addr);
	if ($res) {
	    replace_insn ($addr, $size, $stack, "constant_pop");
	}

	($res, $stack, $size) = match_prologue_saves($addr);
	if ($res) {
	    replace_insn ($addr, $size, $stack, "prologue_saves");
	}

	($res, $stack, $size) = match_epilogue_restores($addr);
	if ($res) {
	    # here we ignore the stack effect of epilogue_restores
	    # since the code includes a "ret" that terminates a thread
	    # of the analysis
	    replace_insn ($addr, $size, $stack, "ret");
	}
    }
}

sub make_fine_grain_cfg () {
    my $last_label;
    foreach my $addr (sort bynum keys %insns) {
	my $insn = $insns{$addr};
	my $hex_addr = sprintf "%x", $addr;
	my @succ = ();
	my @callees = ();

	# hack-- we're going to assume this is the name of the
	# function to which this instruction belongs
	if (defined($addr_to_label{$addr})) {
	    $last_label = $addr_to_label{$addr};
	}

	if ($insn eq "ijmp") {
	    $diehere{$addr} = "cannot process raw indirect jump at $hex_addr";
	} elsif ($insn eq "ret" || $insn eq "reti") {
	    # no control flow from here in our model
	} elsif (is_branch ($addr) || is_skip ($addr) || is_jmp ($addr)) {
	    if (is_jmp ($addr) && get_target ($addr) == $ORIGIN) {
		# jump to origin-- nothing to do since this resets the stack
	    } else {
		push @succ, get_target ($addr);
		if (!is_jmp($addr)) {
		    push @succ, ($addr + $insn_size{$addr});
		}
	    }
	} elsif ($insn eq "jump_table") {
	    my $listref = $jump_lists{$addr};
	    die "tos-ramsize FAIL" if (!defined($listref));
	    @succ = @{$listref};
	} elsif (is_fallthrough ($addr)) {
	    push @succ, ($addr + $insn_size{$addr});
	    if ($insn eq "out") {
		(my $immed, my $reg) = parse_pair ($args{$addr});
		if ($immed eq "0x3d" || $immed eq "0x3e") {
		    $diehere{$addr} = "cannot process raw store to SP at $hex_addr";
		}
	    }
	} elsif (is_direct_call ($addr) || $insn eq "icall") {
	    my $target;
	    if (is_direct_call ($addr)) {
		$target = get_target ($addr);
		die "tos-ramsize FAIL" if (!defined($target));
	    } else {
		my $target_func = $ICALL_TARGETS{$last_label};
		if (defined($target_func)) {
		    $target = $label_to_addr{$target_func};
		    die "tos-ramsize FAIL" if (!defined($target));
		} else {
		    $diehere{$addr} = "cannot process raw indirect call at $hex_addr";
		}
	    }
	    if (defined($target)) {
		push @callees, $target;
		my $l = $addr_to_label{$target};
		if (!defined($l) || !$NORETURN{$addr_to_label{$target}}) {
		    push @succ, ($addr + $insn_size{$addr});
		}
	    }
	} else {
	    # data interpreted as instruction; this happens sometimes
	    delete ($insns{$addr})
	}
	
	$successors{$addr} = \@succ;
	$call_targets{$addr}= \@callees;
    }
}

sub compute_global_size($) {
    (my $fn) = @_;
    open INF, "avr-objdump -h $fn |" or die "tos-ramsize FAIL: can't open input file $fn";
    my $data_size = 0;
    my $bss_size = 0;

    while (my $line = <INF>) {
        chomp $line;
        if ($line =~ /^\s+[0-9]\s.([a-z]+)\s+([0-9a-f]+)/) {
            if ($1 eq "bss") {
                $bss_size = hex($2);
            }
            if ($1 eq "data") {
                $data_size = hex($2);
            }
        }
    }
    close INF;
    return ($data_size, $bss_size);
}

sub max ($$) {
    (my $a, my $b) = @_;
    if ($a > $b) {
	return $a;
    } else {
	return $b;
    }
}

sub min ($$) {
    (my $a, my $b) = @_;
    if ($a < $b) {
	return $a;
    } else {
	return $b;
    }
}

# $addr is the address of the current instruction
# $vec is the name of the interrupt vector we're currently looking at
# $old_depth is the stack depth before executing this instruction

my %stack_map;
my %max_stack;
my %visited;
my %enables_ints;

sub compute_function_stack ($$) {
    (my $start_addr, my $vec_type) = @_;
    
    my $func_name = $addr_to_label{$start_addr};
    my @worklist = ();
    my $start_stack;
    if ($vec_type eq "intr" || $vec_type eq "func") {
	$start_stack = $PC_SIZE{$platform};
    } else {
	die if ($vec_type ne "main");
	$start_stack = 0;
    }
    my @tmpl = ($start_addr, $start_stack);
    push @worklist, \@tmpl;
    my %depths;
    my %callees;

    while (scalar(@worklist) > 0) {
	my $lref = pop (@worklist);
	(my $addr, my $old_depth) = @{$lref};

	die "tos-ramsize FAIL" if (!defined $addr);
	my $hex_addr = sprintf "%x", $addr;

	if (!defined($insns{$addr})) {
	    die "tos-ramsize FAIL: no instruction at address $hex_addr";
	}

	my $insn = $insns{$addr};	
	my $xxx = $diehere{$addr};
	if (defined ($xxx)) {
	    die "tos-ramsize FAIL: $xxx";
	}

	$visited{$addr} = 1;

	# FIXME: nonportable AVR
	if ($insns{$addr} eq "sei") {
	    $enables_ints{$start_addr} = 1;
	}

	my $se = $stack_effect{$addr};
	die "tos-ramsize FAIL: no stack effect for $insn" if (!defined($se));
	my $new_depth;
	if ($se == $ZERO_STACK) {
	    $new_depth = 0;
	} else {
	    $new_depth = $old_depth + $se;
	}

	if ($verbosity > 5) {
	    print "  $hex_addr $insn $new_depth\n";
	}
	
	# something is very wrong
	if ($new_depth > $RAM_SIZE{$platform}) {
	    printf "tos-ramsize FAIL: stack depth exceeds RAM size at %x\n", $hex_addr;
	    die;
	}

	# require balanced stack #1
	if ($insn eq "reti") {
	    die "tos-ramsize FAIL" if ($vec_type ne "intr");
	    die "tos-ramsize FAIL" if ($new_depth != 0);
	    next;
	}

	# require balanced stack #2
	if ($insn eq "ret") {
	    die "tos-ramsize FAIL" if ($vec_type ne "func");
	    die "tos-ramsize FAIL -- unbalanced stack on return from $func_name" if ($new_depth != 0);
	    next;
	}

	# terminate if we're not learning something new about this address
	next if (defined($depths{$addr}) && $depths{$addr} >= $new_depth);

	# record new depth
	$depths{$addr} = $new_depth;
	if (defined($max_stack{$start_addr})) {
	    $max_stack{$start_addr} = 
		max ($new_depth, $max_stack{$start_addr});
	} else {
	    $max_stack{$start_addr} = $new_depth;
	}

	# handle control flow except function calls
	my $succ_ref = $successors{$addr};
	my @succ = @{$succ_ref};
	foreach my $succ_addr (@succ) {
	    my @ll = ($succ_addr, $new_depth);
	    push @worklist, \@ll;
	}

	# handle function calls
	my $callee_ref = $call_targets{$addr};
	my @callees = @{$callee_ref};
	foreach my $callee_addr (@callees) {
	    $callees{$callee_addr} = 1;
	    my $my_max;
	    if (defined($stack_map{$start_addr}{$callee_addr})) {
		$my_max = max ($stack_map{$start_addr}{$callee_addr}, $new_depth);
	    } else {
		$my_max = $new_depth;
	    }
	    $stack_map{$start_addr}{$callee_addr} = $my_max;
	}
    }

    my @callee_list = keys %callees;

    if ($verbosity > 2) {
	print "$func_name (max = $max_stack{$start_addr})\n";
	foreach my $callee (@callee_list) {
	    print "  -> $addr_to_label{$callee} ";
	    print "depth $stack_map{$start_addr}{$callee}\n";
	}
    }
    
    return \@callee_list;
}

sub analyze_functions () {
    my @worklist = ();
    my %seen = ();
    for (my $vec = 0; $vec < $NUM_VECTORS{$platform}; $vec++) {
	my $addr = $vec * $VEC_SIZE{$platform};
	my $label = "vector_$vec";
	$addr_to_label{$addr} = $label;
	$label_to_addr{$label} = $addr;
	my $vec_type;
	if ($vec == 0) {
	    $vec_type = "main";
	} else {
	    $vec_type = "intr";
	}
	my @ll = ($addr, $vec_type);
	push @worklist, \@ll;
    }
    while (scalar(@worklist) > 0) {
	my $lref = pop @worklist;
	(my $addr, my $vec_type) = @{$lref};
	my $hex_addr = sprintf "%x", $addr;
	next if ($seen{$addr});
	my $label = $addr_to_label{$addr};
	if (defined($label) && defined($SPECIAL{$label})) {
	    $max_stack{$addr} = $SPECIAL{$label};
	    next;
	}
	$seen{$addr} = 1;
	my $l;
	my $lab = $addr_to_label{$addr};
	if (defined($lab)) {
	    $l = $lab;
	} else {
	    $l = "[no label]";
	}

	my $xlref = compute_function_stack ($addr, $vec_type);
	my @l = @{$xlref};
	foreach $addr (@l) {
	    my @ll = ($addr, "func");
	    push @worklist, \@ll;
	}
    }
}

# floyd
sub find_cycles() {
    my @func_list = keys %max_stack;
    my %path;
    my $INFINITY = 9999999;
    foreach my $x (@func_list) {
	foreach my $y (@func_list) {
	    if (defined($stack_map{$x}{$y})) {
		$path{$x}{$y} = 1;
	    } else {
		$path{$x}{$y} = $INFINITY;
	    }
	}
    }
    foreach my $k (@func_list) {
	foreach my $i (@func_list) {
	    foreach my $j(@func_list) {
		$path{$i}{$j} = 
		    min ($path{$i}{$j},$path{$i}{$k}+$path{$k}{$j});
	    }
	}
    }
    my $min_path = $INFINITY;
    my $min_func;
    if ($verbosity > 2) {
	print "self-path lengths in the callgraph:\n";
    }
    foreach my $z (@func_list) {
	my $len = $path{$z}{$z};
	if ($verbosity > 2) {
	    print "  $addr_to_label{$z} $len\n";
	}
	if ($len < $min_path) {
	    $min_path = $len;
	    $min_func = $z;
	}
    }
    if ($min_path != $INFINITY) {
	print "cannot estimate stack depth due to recursive loop of length $min_path:\n";
	my $f = $min_func;
	for (my $i=$min_path-1; $i>0; $i--) {
	    my @next_list = keys (%{$path{$f}});
	    my $found;
	    foreach my $n (@next_list) {
		if ($path{$n}{$min_func} == $i &&
		    $path{$n}{$n} == $min_path) {
		    $found = $n;
		}
	    }
	    die "tos-ramsize FAIL graph algo bug" if (!$found);
	    printf "  %s @ %x -> %s @ %x\n", $addr_to_label{$f}, $f, $addr_to_label{$found}, $found;
	    $f = $found;
	}
	printf "  %s @ %x -> %s @ %x\n", $addr_to_label{$f}, $f, $addr_to_label{$min_func}, $min_func;

	die "tos-ramsize FAIL";
    }
}

my %reachable;

sub find_reachable {
    (my $addr) = @_;
    $reachable{$addr} = 1;
    foreach my $callee (keys (%{$stack_map{$addr}})) {
	find_reachable($callee);
    }
}

my %vector_depth = ();
my %atomic_vector = ();

sub analyze_vector($$$) {
    (my $addr, my $vec, my $lref) = @_;
    my @topo = @{$lref};
    %reachable = ();
    $atomic_vector{$vec} = 1;
    find_reachable ($addr);
    my %depth = ();
    my $maxd = 0;
    my $FAKE = -999;
    foreach my $v (@topo) {
	next if (!defined($reachable{$v}));
	my @edge_list = keys %{$stack_map{$v}};
	# if any reachable function enables interrupts, the whole vector
	# in non-atomic
	if (defined($enables_ints{$v}) && $enables_ints{$v}) {
	    $atomic_vector{$vec} = 0;
	}
	push @edge_list, $FAKE;
	foreach my $w (@edge_list) {
	    my $d = $depth{$w};
	    $d = 0 if (!defined($d));
	    my $d2 = $depth{$v};
	    $d2 = 0 if (!defined($d2));
	    my $edge_weight;
	    if ($w eq $FAKE) {
		$edge_weight = $max_stack{$v};
	    } else {
		$edge_weight = $stack_map{$v}{$w};
	    }
	    $d = max ($d, $d2 + $edge_weight);
	    $depth{$w} = $d;
	    $maxd = max ($maxd, $d);
	}
	
    }
    $vector_depth{$vec} = $maxd;
}

sub analyze_vectors() {
    my @topo = ();
    my %stack_map2 = %stack_map;
    my @func_list = keys %stack_map2;
    do {
        foreach my $f (keys %stack_map2) {
	    my $in_edges = 0;
	    foreach my $f2 (keys %stack_map2) {
		if (defined($stack_map2{$f2}{$f})) {
		    $in_edges++;
		}
	    }
	    if ($in_edges == 0) {
		push @topo, $f;
		delete ($stack_map2{$f});
	    }
	}
    } while (scalar(keys %stack_map2) > 0);

    if ($verbosity > 3) {
	foreach my $f (@topo) {
	    my $hex = sprintf "%x", $f;
	    my $s = $addr_to_label{$f};
	    print "  $s $hex\n";
	}
    }
    for (my $vec = 0; $vec < $NUM_VECTORS{$platform}; $vec++) {
	my $addr = $vec * $VEC_SIZE{$platform};
	analyze_vector ($addr, $vec, \@topo);
    }
}

sub analyze_global_stack_usage() {
    my $max_atomic = 0;
    my $total_nonatomic = 0;
    if ($verbosity > 1) {
	print "\n";
	print "per-vector results:\n";
    }
    for (my $vec = 0; $vec < $NUM_VECTORS{$platform}; $vec++) {
	my $addr = $vec * $VEC_SIZE{$platform};
	my $maxd = $vector_depth{$vec};
	my $s = "";
	$s .= sprintf "  vector %d max depth = %d", $vec, $maxd;
	my $atom = $atomic_vector{$vec};
	if (defined($atom) && $atom) {
	    $s .= " (atomic)";
	    $max_atomic = max ($max_atomic, $maxd);
	} else {
	    $s .= " (not atomic)";
	    $total_nonatomic += $maxd;
	}
	if ($verbosity > 1 && $maxd != $PC_SIZE{$platform}) {
	    print "$s\n";
	}
    }
    
    my $depth = $total_nonatomic + $max_atomic;
    return $depth;
}

##########################################################################
################################ MAIN ####################################
##########################################################################

# redirect stderr to stdout, don't buffer stdout
open(STDERR,'>&', STDOUT);
$|=1;

my $result = GetOptions ("verbosity=i" => \$verbosity);
die "tos-ramsize FAIL" if (!$result);

if (scalar(@ARGV) != 2) {
    die "usage: ramsize.pl [-verbosity 0-9] mica2|micaz|iris avr_file.elf";
}

$platform = $ARGV[0];
die "tos-ramsize FAIL: unknown platform '$platform'" if (!defined($RAM_SIZE{$platform}));

my $file = $ARGV[1];
die "tos-ramsize FAIL: '$file' not found" if (!(-f $file));

if ($verbosity > 1) {
    print "analyzing elf file '$file' for platform '$platform'\n";
}

disassemble ($file);
insn_stack_effects();
make_macro_insns();
make_fine_grain_cfg();
analyze_functions();
find_cycles();
analyze_vectors();
my $total_depth = analyze_global_stack_usage();

(my $data_size, my $bss_size) = compute_global_size($file);
my $ramused = $data_size + $bss_size + $total_depth;
my $free_mem = $RAM_SIZE{$platform} - $ramused;

if ($verbosity > 2) {
    foreach my $addr (sort bynum keys %insns) {
	if (!$visited{$addr}) {
	    my $l = $addr_to_label{$addr};
	    if (defined($l) && !defined($SPECIAL{$l})) {
		printf "unreachable label: %x %s\n", $addr, $l;
	    }
	}
    }
}

if ($verbosity > 0) {
    print "BSS segment size is ${bss_size}, data segment size is ${data_size}\n";
}
print "The upper bound on stack size is ${total_depth}\n";
print "The upper bound on RAM usage is $ramused\n";
print "There are $free_mem unused bytes of RAM\n";

##########################################################################