VEX/switchback/binary_switchback.pl

   1 #!/usr/bin/env perl
   2 use strict;
   3 use warnings;
   4
   5 ######################################################
   6 # Binary search script for switchback
   7 # Finds bad basic block for seg faults and bad output.
   8 #
   9 # To test output, you need to create test_ref
  10 # test_ref should hold the correct output for running the test_xxx program:
  11 #  - Everything between (not including) /^---START---$/ and /^---STOP---$/
  12 #  - But NOT including output from /^---begin SWITCHBACK/
  13 #    to /^---  end SWITCHBACK/ inclusive
  14 #
  15 # This script can't handle other vex output,
  16 # so e.g switchback.c::DEBUG_TRACE_FLAGS should be 0
  17 #
  18
  19 ######################################################
  20 # Global consts, vars
  21 use constant DEBUG => 0;
  22 use constant CONST_N_MAX => 10000000000;
  23 use constant CONST_N_MUL => 2;
  24
  25 my $SWITCHBACK = "./switchback";
  26 my $N_START = 0;
  27 my $N_LAST_GOOD = 0;
  28 my $N_LAST_BAD = -1;
  29 my $GIVEN_LAST_GOOD = -1;
  30 my $GIVEN_LAST_BAD = -1;
  31 my $TEST_REF;
  32
  33
  34
  35 ######################################################
  36 # Helper functions
  37
  38 sub Exit {
  39     exit $_[0];
  40 }
  41
  42 sub Usage {
  43     print "Usage: binary_switchback.pl test_ref [last_good [last_bad]]\n";
  44     print "where:\n";
  45     print "   test_ref  = reference output from test_xxx\n";
  46     print "   last_good = last known good bb (search space minimum)\n";
  47     print "   last_bad  = last known bad bb (search space maximum)\n";
  48     print "\n";
  49 }
  50
  51 sub QuitUsage {
  52     print $_[0]."\n";
  53     Usage();
  54     Exit 1;
  55 }
  56
  57
  58 ######################################################
  59 # Get & check cmdline args
  60 # - if given, override global vars.
  61
  62 if (@ARGV < 1 || @ARGV > 3) {
  63     QuitUsage "Error: Bad num args\n";
  64 }
  65
  66 $TEST_REF = $ARGV[0];
  67
  68 if ( ! -x "$SWITCHBACK" ) {
  69     QuitUsage "File doesn't exist | not executable: '$SWITCHBACK'\n";
  70 }
  71
  72 if (@ARGV >1) {
  73     $N_LAST_GOOD = $ARGV[1];
  74     $GIVEN_LAST_GOOD = $N_LAST_GOOD;
  75     if (! ($N_LAST_GOOD =~ /^\d*$/)) {
  76         QuitUsage "Error: bad arg for #last_good\n";
  77     }
  78     if ($N_LAST_GOOD >= CONST_N_MAX) {
  79         QuitUsage "Error: #last_good >= N_MAX(".CONST_N_MAX.")\n";
  80     }
  81 }
  82 if (@ARGV >2) {
  83     $N_LAST_BAD = $ARGV[2];
  84     $GIVEN_LAST_BAD = $N_LAST_BAD;
  85     if (! ($N_LAST_BAD =~ /^\d*$/)) {
  86         QuitUsage "Error: bad arg for 'last_bad'\n";
  87     }
  88 }
  89
  90 # Setup N_START
  91 if ($N_LAST_BAD != -1) {
  92     # Start halfway:
  93     my $diff = $N_LAST_BAD - $N_LAST_GOOD;
  94     $N_START = $N_LAST_GOOD + ($diff - ($diff % 2)) / 2;
  95 } else {
  96     # No known end: Start at beginning:
  97     if ($N_LAST_GOOD > 0) {   # User-given last_good
  98         $N_START = $N_LAST_GOOD;
  99     } else {
 100         $N_START = 100;       # Some reasonable number.
 101     }
 102 }
 103
 104 ######################################################
 105 # Sanity checks (shouldn't ever happen)
 106
 107 if ($N_START < $N_LAST_GOOD) {
 108     print "Program Error: start < last_good\n";
 109     exit 1;
 110 }
 111 if ($N_LAST_BAD != -1 && $N_START >= $N_LAST_BAD) {
 112     print "Program Error: start >= last_bad\n";
 113     exit 1;
 114 }
 115 if ($N_START < 1 || $N_START > CONST_N_MAX) {
 116     print "Program Error: Bad N_START: '$N_START'\n";
 117     exit 1;
 118 }
 119 if ($N_LAST_GOOD < 0 || $N_LAST_GOOD > CONST_N_MAX) {
 120     print "Program Error: Bad N_LAST_GOOD: '$N_LAST_GOOD'\n";
 121     exit 1;
 122 }
 123 if ($N_LAST_BAD < -1 || $N_LAST_BAD > CONST_N_MAX) {
 124     print "Program Error: Bad N_LAST_BAD: '$N_LAST_BAD'\n";
 125     exit 1;
 126 }
 127
 128
 129
 130
 131
 132
 133 ######################################################
 134 # Helper functions
 135
 136 # Run switchback for test, for N bbs
 137 # returns output results
 138 sub SwitchBack {
 139     my $n = $_[0];
 140     if ($n < 0 || $n > CONST_N_MAX) {
 141         print "Error SwitchBack: Bad N: '$n'\n";
 142         Exit 1;
 143     }
 144     my $TMPFILE = ".switchback_output.$n";
 145
 146     print "=== Calling switchback for bb $n ===\n";
 147
 148     system("$SWITCHBACK $n >& $TMPFILE");
 149     my $ret = $?;
 150
 151     if ($ret == 256) {
 152         print "Error running switchback - Quitting...\n---\n";
 153         open(INFILE, "$TMPFILE");
 154         print <INFILE>;
 155         close(INFILE);
 156
 157         unlink($TMPFILE) if (! DEBUG);
 158         exit 0;
 159     }
 160
 161     if ($ret & 127) {
 162         print "Ctrl-C pressed - Quitting...\n";
 163         unlink($TMPFILE) if (! DEBUG);
 164         exit 0;
 165     }
 166
 167     if (DEBUG) {
 168         if ($ret == -1) {
 169             print "failed to execute: $!\n";
 170         }
 171         elsif ($ret & 127) {
 172             printf "child died with signal %d, %s coredump\n",
 173             ($ret & 127),  ($ret & 128) ? 'with' : 'without';
 174         }
 175         else {
 176             printf "child exited with value %d\n", $ret >> 8;
 177         }
 178     }
 179     if ($ret != 0) { # Err: maybe seg fault
 180         open(INFILE, "$TMPFILE");
 181         my @results = <INFILE>;
 182         close(INFILE);
 183
 184         while (@results && !((shift @results) =~ /^---START---/)) {}
 185         print @results;
 186
 187         unlink($TMPFILE) if (! DEBUG);
 188         return;
 189     }
 190
 191     open(INFILE, "$TMPFILE");
 192     my @results = <INFILE>;
 193     close(INFILE);
 194
 195     unlink($TMPFILE) if (! DEBUG);
 196     return @results;
 197 }
 198
 199 # Returns N simulated bbs from output lines
 200 sub get_N_simulated {
 201     my @lines = @{$_[0]};
 202     pop @lines;             # not the first...
 203     my $line = pop @lines;  # ...but the second line.
 204
 205     chomp $line;
 206     my $n;
 207     if (($n) = ($line =~ /^(\d*) bbs simulated$/)) {
 208         return $n;
 209     }
 210     print "Error: Didn't find N bbs simultated, from output lines\n";
 211     Exit 1;
 212 }
 213
 214 # Calls test script to compare current output lines with a reference.
 215 # Returns 1 on success, 0 on failure
 216 sub TestOutput {
 217     my @lines = @{$_[0]};
 218     my $n = $_[1];
 219     my $ref_output = "$TEST_REF";
 220
 221     # Get the current section we want to compare:
 222     my @newlines;
 223     my $ok=0;
 224     my $halfline = "";
 225     foreach my $line(@lines) {
 226         chomp $line;
 227         if ($line =~ /^---STOP---$/) { last; }     # we're done
 228
 229         # output might be messed up here...
 230         if ($line =~ /^.*---begin SWITCHBACK/) {
 231             ($halfline) = ($line =~ /^(.*)---begin SWITCHBACK/);
 232             $ok = 0;  # stop on prev line
 233         }
 234
 235         # A valid line:
 236         if ($ok) {
 237             if ($halfline ne "") {   # Fix broken line
 238                 $line = $halfline.$line;
 239                 $halfline = "";
 240             }
 241
 242             # Ignore Vex output
 243             if ($line =~ /^vex /) { next; }
 244
 245             push(@newlines, $line);
 246         }
 247
 248         if ($line =~ /^---START---$/) {            # start on next line
 249             $ok = 1;
 250         }
 251
 252         if ($line =~ /^---  end SWITCHBACK/) {     # start on next line
 253             $ok = 1;
 254
 255         }
 256     }
 257
 258     if (DEBUG) {
 259         open(OUTFILE, ">.filtered_output.$n");
 260         print OUTFILE join("\n",@newlines);
 261         close(OUTFILE);
 262     }
 263
 264     # Read in reference lines
 265     open(REFERENCE, "$ref_output") || die "Error: Couldn't open $ref_output\n";
 266     my @ref_lines = <REFERENCE>;
 267     close(REFERENCE);
 268
 269     # Compare reference lines with current:
 270     my $match = 1;
 271     my $i = 0;
 272     foreach my $ref_line(@ref_lines) {
 273         chomp $ref_line;
 274         my $line = $newlines[$i++];
 275         chomp $line;
 276         if ($ref_line ne $line) {
 277             print "\nMismatch on output:\n";
 278             print "ref: '$ref_line'\n";
 279             print "new: '$line'\n\n";
 280             $match = 0;
 281             last;
 282         }
 283     }
 284     return $match;
 285 }
 286
 287
 288
 289
 290
 291
 292 ######################################################
 293 # Do the search
 294
 295 if (DEBUG) {
 296     print "\n------------\n";
 297     print "START:  N=$N_START\n";
 298     print "START: lg=$N_LAST_GOOD\n";
 299     print "START: lb=$N_LAST_BAD\n";
 300     print "START: GIVEN_LAST_GOOD=$GIVEN_LAST_GOOD\n";
 301     print "START: GIVEN_LAST_BAD =$GIVEN_LAST_BAD\n";
 302     print "\n";
 303 }
 304
 305 my $N = $N_START;
 306 my $success = 0;
 307 my @sb_output;
 308 while (1) {
 309     if (DEBUG) {
 310         print "\n------------\n";
 311         print "SOL: lg=$N_LAST_GOOD\n";
 312         print "SOL: lb=$N_LAST_BAD\n";
 313         print "SOL:  N=$N\n";
 314     }
 315     if ($N < 0) {
 316         print "Error: $N<0\n";
 317         Exit 1;
 318     }
 319
 320     my $ok = 1;
 321     # Run switchback:
 322     @sb_output = SwitchBack($N);
 323
 324     if (@sb_output == 0) { # Switchback failed - maybe seg fault
 325         $ok = 0;
 326     }
 327
 328     if (DEBUG) {
 329         open(fileOUT, ">.retrieved_output.$N") or die("Can't open file for writing: $!");
 330         print fileOUT @sb_output;
 331         close(fileOUT);
 332     }
 333
 334     # If we're ok so far (no seg faults) then test for correct output
 335     if ($ok) {
 336         $ok = TestOutput( \@sb_output, $N );
 337     }
 338
 339     if ($ok) {
 340         if (get_N_simulated(\@sb_output) < $N) { # Done: No bad bbs
 341             $success = 1;
 342             last;
 343         }
 344         if ($N_LAST_BAD == -1) {
 345             # No upper bound for search space
 346             # Try again with a bigger N
 347
 348             $N_LAST_GOOD = $N;
 349             $N *= CONST_N_MUL;
 350             if ($N > CONST_N_MAX) {
 351                 print "\nError: Maxed out N($N): N_MAX=".CONST_N_MAX."\n";
 352                 print "\nWe're either in a loop, or this is a big test program (increase N_MAX)\n\n";
 353                 Exit 1;
 354             }
 355             if (DEBUG) {
 356                 print "Looks good so far: Trying bigger N...\n\n";
 357             }
 358             next;
 359         }
 360     }
 361
 362     # Narrow the search space:
 363     if ($ok) { $N_LAST_GOOD = $N; }
 364     else {     $N_LAST_BAD  = $N;  }
 365
 366     # Calculate next step:
 367     my $diff = $N_LAST_BAD - $N_LAST_GOOD;
 368     $diff = $diff - ($diff % 2);
 369     my $step = $diff / 2;
 370
 371     if ($step < 0) {
 372         print "Error: step = $step\n";
 373         Exit 1;
 374     }
 375
 376     # This our last run-through?
 377     if ($step!=0) {
 378         $N = $N_LAST_GOOD + $step;   # Keep on going...
 379     } else {
 380         last;                        # Get outta here
 381     }
 382
 383     if (DEBUG) {
 384         print "\nEOL: ok=$ok\n";
 385         print "EOL: lg=$N_LAST_GOOD\n";
 386         print "EOL: lb=$N_LAST_BAD\n";
 387         print "EOL:  s=$step\n";
 388         print "EOL:  N=$N\n";
 389     }
 390 }
 391
 392
 393
 394 ######################################################
 395 # Done: Report results
 396
 397 print "\n============================================\n";
 398 print "Done searching.\n\n";
 399
 400 if ($N_LAST_BAD != -1 && $N != $N_LAST_BAD) {
 401     print "Getting output for last bad bb:\n";
 402     @sb_output = SwitchBack($N_LAST_BAD);
 403 }
 404
 405 print @sb_output;
 406 print "\n\n";
 407 if ($success) {
 408     print "*** Success!  No bad bbs found. ***\n";
 409 } else {
 410     if ($N_LAST_BAD == $GIVEN_LAST_BAD) {
 411         print "*** No failures detected within given bb range ***\n";
 412         print " - check given 'last_bad' argument\n";
 413     } else {
 414         if ($N_LAST_BAD == $GIVEN_LAST_GOOD) {
 415             print "*** Failed on bb given as last_good ***\n";
 416             print " - decrease the 'last_good' argument\n";
 417         } else {
 418             print "*** Failure: Last failed switchback bb: $N_LAST_BAD ***\n";
 419             print "Hence bad bb: ". ($N_LAST_BAD - 1) ."\n";
 420         }
 421     }
 422 }
 423 print "\n";
 424 if (DEBUG) {
 425     print "END:  N=$N\n";
 426     print "END: lg=$N_LAST_GOOD\n";
 427     print "END: lb=$N_LAST_BAD\n";
 428     print "END: GIVEN_LAST_BAD=$GIVEN_LAST_BAD\n";
 429     print "\n";
 430 }
 431 Exit 0;