VEX/switchback/binary_switchback.pl

#!/usr/bin/env perl
use strict;
use warnings;

######################################################
# Binary search script for switchback
# Finds bad basic block for seg faults and bad output.
#
# To test output, you need to create test_ref
# test_ref should hold the correct output for running the test_xxx program:
#  - Everything between (not including) /^---START---$/ and /^---STOP---$/
#  - But NOT including output from /^---begin SWITCHBACK/
#    to /^---  end SWITCHBACK/ inclusive
#
# This script can't handle other vex output,
# so e.g switchback.c::DEBUG_TRACE_FLAGS should be 0
#

######################################################
# Global consts, vars
use constant DEBUG => 0;
use constant CONST_N_MAX => 10000000000;
use constant CONST_N_MUL => 2;

my $SWITCHBACK = "./switchback";
my $N_START = 0;
my $N_LAST_GOOD = 0;
my $N_LAST_BAD = -1;
my $GIVEN_LAST_GOOD = -1;
my $GIVEN_LAST_BAD = -1;
my $TEST_REF;



######################################################
# Helper functions

sub Exit {
    exit $_[0];
}

sub Usage {
    print "Usage: binary_switchback.pl test_ref [last_good [last_bad]]\n";
    print "where:\n";
    print "   test_ref  = reference output from test_xxx\n";
    print "   last_good = last known good bb (search space minimum)\n";
    print "   last_bad  = last known bad bb (search space maximum)\n";
    print "\n";
}

sub QuitUsage {
    print $_[0]."\n";
    Usage();
    Exit 1;
}


######################################################
# Get & check cmdline args
# - if given, override global vars.

if (@ARGV < 1 || @ARGV > 3) {
    QuitUsage "Error: Bad num args\n";
}

$TEST_REF = $ARGV[0];

if ( ! -x "$SWITCHBACK" ) {
    QuitUsage "File doesn't exist | not executable: '$SWITCHBACK'\n";
}

if (@ARGV >1) {
    $N_LAST_GOOD = $ARGV[1];
    $GIVEN_LAST_GOOD = $N_LAST_GOOD;
    if (! ($N_LAST_GOOD =~ /^\d*$/)) {
	QuitUsage "Error: bad arg for #last_good\n";
    }
    if ($N_LAST_GOOD >= CONST_N_MAX) {
	QuitUsage "Error: #last_good >= N_MAX(".CONST_N_MAX.")\n";
    }
}
if (@ARGV >2) {
    $N_LAST_BAD = $ARGV[2];
    $GIVEN_LAST_BAD = $N_LAST_BAD;
    if (! ($N_LAST_BAD =~ /^\d*$/)) {
	QuitUsage "Error: bad arg for 'last_bad'\n";
    }
}

# Setup N_START
if ($N_LAST_BAD != -1) {
    # Start halfway:
    my $diff = $N_LAST_BAD - $N_LAST_GOOD;
    $N_START = $N_LAST_GOOD + ($diff - ($diff % 2)) / 2;
} else {
    # No known end: Start at beginning:
    if ($N_LAST_GOOD > 0) {   # User-given last_good
	$N_START = $N_LAST_GOOD;
    } else {
	$N_START = 100;       # Some reasonable number.
    }
}

######################################################
# Sanity checks (shouldn't ever happen)

if ($N_START < $N_LAST_GOOD) {
    print "Program Error: start < last_good\n";
    exit 1;
}
if ($N_LAST_BAD != -1 && $N_START >= $N_LAST_BAD) {
    print "Program Error: start >= last_bad\n";
    exit 1;
}
if ($N_START < 1 || $N_START > CONST_N_MAX) {
    print "Program Error: Bad N_START: '$N_START'\n";
    exit 1;
}
if ($N_LAST_GOOD < 0 || $N_LAST_GOOD > CONST_N_MAX) {
    print "Program Error: Bad N_LAST_GOOD: '$N_LAST_GOOD'\n";
    exit 1;
}
if ($N_LAST_BAD < -1 || $N_LAST_BAD > CONST_N_MAX) {
    print "Program Error: Bad N_LAST_BAD: '$N_LAST_BAD'\n";
    exit 1;
}






######################################################
# Helper functions

# Run switchback for test, for N bbs
# returns output results
sub SwitchBack {
    my $n = $_[0];
    if ($n < 0 || $n > CONST_N_MAX) {
	print "Error SwitchBack: Bad N: '$n'\n";
	Exit 1;
    }
    my $TMPFILE = ".switchback_output.$n";

    print "=== Calling switchback for bb $n ===\n";

    system("$SWITCHBACK $n >& $TMPFILE");
    my $ret = $?;

    if ($ret == 256) {
	print "Error running switchback - Quitting...\n---\n";
	open(INFILE, "$TMPFILE");
	print <INFILE>;
	close(INFILE);

	unlink($TMPFILE) if (! DEBUG);
	exit 0;	
    } 

    if ($ret & 127) {
	print "Ctrl-C pressed - Quitting...\n";
	unlink($TMPFILE) if (! DEBUG);
	exit 0;
    }

    if (DEBUG) {
	if ($ret == -1) {
	    print "failed to execute: $!\n";
	}
	elsif ($ret & 127) {
	    printf "child died with signal %d, %s coredump\n",
            ($ret & 127),  ($ret & 128) ? 'with' : 'without';
	}
	else {
	    printf "child exited with value %d\n", $ret >> 8;
	}
    }
    if ($ret != 0) { # Err: maybe seg fault
	open(INFILE, "$TMPFILE");
	my @results = <INFILE>;
	close(INFILE);

	while (@results && !((shift @results) =~ /^---START---/)) {}
	print @results;

	unlink($TMPFILE) if (! DEBUG);
	return;
    }

    open(INFILE, "$TMPFILE");
    my @results = <INFILE>;
    close(INFILE);

    unlink($TMPFILE) if (! DEBUG);
    return @results;
}

# Returns N simulated bbs from output lines
sub get_N_simulated {
    my @lines = @{$_[0]};
    pop @lines;             # not the first...
    my $line = pop @lines;  # ...but the second line.

    chomp $line;
    my $n;
    if (($n) = ($line =~ /^(\d*) bbs simulated$/)) {
	return $n;
    }
    print "Error: Didn't find N bbs simultated, from output lines\n";
    Exit 1;
}

# Calls test script to compare current output lines with a reference.
# Returns 1 on success, 0 on failure
sub TestOutput {
    my @lines = @{$_[0]};
    my $n = $_[1];
    my $ref_output = "$TEST_REF";

    # Get the current section we want to compare:
    my @newlines;
    my $ok=0;
    my $halfline = "";
    foreach my $line(@lines) {
	chomp $line;
	if ($line =~ /^---STOP---$/) { last; }     # we're done

	# output might be messed up here...
	if ($line =~ /^.*---begin SWITCHBACK/) {
	    ($halfline) = ($line =~ /^(.*)---begin SWITCHBACK/);
	    $ok = 0;  # stop on prev line
	}

	# A valid line:
	if ($ok) {
	    if ($halfline ne "") {   # Fix broken line
		$line = $halfline.$line;
		$halfline = "";
	    }

	    # Ignore Vex output
	    if ($line =~ /^vex /) { next; }

	    push(@newlines, $line);
	}

	if ($line =~ /^---START---$/) {            # start on next line
	    $ok = 1;
	}

	if ($line =~ /^---  end SWITCHBACK/) {     # start on next line
	    $ok = 1;
	    
	}
    }

    if (DEBUG) {
	open(OUTFILE, ">.filtered_output.$n");
	print OUTFILE join("\n",@newlines);
	close(OUTFILE);
    }

    # Read in reference lines
    open(REFERENCE, "$ref_output") || die "Error: Couldn't open $ref_output\n";
    my @ref_lines = <REFERENCE>;
    close(REFERENCE);

    # Compare reference lines with current:
    my $match = 1;
    my $i = 0;
    foreach my $ref_line(@ref_lines) {
	chomp $ref_line;
	my $line = $newlines[$i++];
	chomp $line;
	if ($ref_line ne $line) {
	    print "\nMismatch on output:\n";
	    print "ref: '$ref_line'\n";
	    print "new: '$line'\n\n";
	    $match = 0;
	    last;
	}
    }
    return $match;
}






######################################################
# Do the search

if (DEBUG) {
    print "\n------------\n";
    print "START:  N=$N_START\n";
    print "START: lg=$N_LAST_GOOD\n";
    print "START: lb=$N_LAST_BAD\n";
    print "START: GIVEN_LAST_GOOD=$GIVEN_LAST_GOOD\n";
    print "START: GIVEN_LAST_BAD =$GIVEN_LAST_BAD\n";
    print "\n";
}

my $N = $N_START;
my $success = 0;
my @sb_output;
while (1) {
    if (DEBUG) {
	print "\n------------\n";
	print "SOL: lg=$N_LAST_GOOD\n";
	print "SOL: lb=$N_LAST_BAD\n";
	print "SOL:  N=$N\n";
    }
    if ($N < 0) {
	print "Error: $N<0\n";
	Exit 1;
    }

    my $ok = 1;
    # Run switchback:
    @sb_output = SwitchBack($N);

    if (@sb_output == 0) { # Switchback failed - maybe seg fault
	$ok = 0;
    }

    if (DEBUG) {
	open(fileOUT, ">.retrieved_output.$N") or die("Can't open file for writing: $!");
	print fileOUT @sb_output;
	close(fileOUT);
    }

    # If we're ok so far (no seg faults) then test for correct output
    if ($ok) {
	$ok = TestOutput( \@sb_output, $N );
    }

    if ($ok) {
	if (get_N_simulated(\@sb_output) < $N) { # Done: No bad bbs
	    $success = 1;
	    last;
	}
	if ($N_LAST_BAD == -1) {
	    # No upper bound for search space
	    # Try again with a bigger N

	    $N_LAST_GOOD = $N;
	    $N *= CONST_N_MUL;
	    if ($N > CONST_N_MAX) {
		print "\nError: Maxed out N($N): N_MAX=".CONST_N_MAX."\n";
		print "\nWe're either in a loop, or this is a big test program (increase N_MAX)\n\n";
		Exit 1;
	    }
	    if (DEBUG) {
		print "Looks good so far: Trying bigger N...\n\n";
	    }
	    next;
	}
    }

    # Narrow the search space:
    if ($ok) { $N_LAST_GOOD = $N; }
    else {     $N_LAST_BAD  = $N;  }

    # Calculate next step:
    my $diff = $N_LAST_BAD - $N_LAST_GOOD;
    $diff = $diff - ($diff % 2);
    my $step = $diff / 2;

    if ($step < 0) {
	print "Error: step = $step\n";
	Exit 1;
    }

    # This our last run-through?
    if ($step!=0) {
	$N = $N_LAST_GOOD + $step;   # Keep on going...
    } else {
	last;                        # Get outta here
    }

    if (DEBUG) {
	print "\nEOL: ok=$ok\n";
	print "EOL: lg=$N_LAST_GOOD\n";
	print "EOL: lb=$N_LAST_BAD\n";
	print "EOL:  s=$step\n";
	print "EOL:  N=$N\n";
    }
}



######################################################
# Done: Report results

print "\n============================================\n";
print "Done searching.\n\n";

if ($N_LAST_BAD != -1 && $N != $N_LAST_BAD) {
    print "Getting output for last bad bb:\n";
    @sb_output = SwitchBack($N_LAST_BAD);
}

print @sb_output;
print "\n\n";
if ($success) {
    print "*** Success!  No bad bbs found. ***\n";
} else {
    if ($N_LAST_BAD == $GIVEN_LAST_BAD) {
	print "*** No failures detected within given bb range ***\n";
	print " - check given 'last_bad' argument\n";
    } else {
	if ($N_LAST_BAD == $GIVEN_LAST_GOOD) {
	    print "*** Failed on bb given as last_good ***\n";
	    print " - decrease the 'last_good' argument\n";
	} else {
	    print "*** Failure: Last failed switchback bb: $N_LAST_BAD ***\n";
	    print "Hence bad bb: ". ($N_LAST_BAD - 1) ."\n";
	}
    }
}
print "\n";
if (DEBUG) {
    print "END:  N=$N\n";
    print "END: lg=$N_LAST_GOOD\n";
    print "END: lb=$N_LAST_BAD\n";
    print "END: GIVEN_LAST_BAD=$GIVEN_LAST_BAD\n";
    print "\n";
}
Exit 0;