Improve run-tests to accept more output code formats.
[pintos-anon] / grading / userprog / run-tests
1 #! /usr/bin/perl
2
3 use warnings;
4 use strict;
5 use POSIX;
6 use Algorithm::Diff;
7 use Getopt::Long;
8
9 our ($VERBOSE) = 0;     # Verbosity of output
10 our (@TESTS);           # Tests to run.
11 my ($clean) = 0;
12 my ($grade) = 0;
13
14 GetOptions ("v|verbose+" => \$VERBOSE,
15             "h|help" => sub { usage (0) },
16             "t|test=s" => \@TESTS,
17             "c|clean" => \$clean,
18             "g|grade" => \$grade)
19     or die "Malformed command line; use --help for help.\n";
20 die "Non-option argument not supported; use --help for help.\n"
21     if @ARGV > 0;
22
23 sub usage {
24     my ($exitcode) = @_;
25     print "run-tests, for grading Pintos multiprogramming projects.\n\n";
26     print "Invoke from a directory containing a student tarball named by\n";
27     print "the submit script, e.g. username.Oct.12.04.20.04.09.tar.gz.\n";
28     print "In normal usage, no options are needed.\n\n";
29     print "Output is produced in tests.out and details.out.\n\n";
30     print "Options:\n";
31     print "  -c, --clean     Remove old output files before starting\n";
32     print "  -t, --test=TEST Execute TEST only (allowed multiple times)\n";
33     print "  -g, --grade     Instead of running tests, compose grade.out\n";
34     print "  -v, --verbose   Print commands before executing them\n";
35     print "  -h, --help      Print this help message\n";
36     exit $exitcode;
37 }
38
39 # Default set of tests.
40 @TESTS = qw (args-argc args-argv0 args-argvn args-single args-multiple
41              args-dbl-space
42              sc-bad-sp sc-bad-arg sc-boundary
43              halt exit
44              create-normal create-empty create-null create-bad-ptr 
45              create-long create-exists create-bound
46              open-normal open-missing open-boundary open-empty open-null
47              open-bad-ptr open-twice
48              close-normal close-twice close-stdin close-stdout close-bad-fd
49              read-normal read-bad-ptr read-boundary read-zero read-stdout
50              read-bad-fd
51              write-normal write-bad-ptr write-boundary write-zero write-stdin
52              write-bad-fd
53              exec-once exec-arg exec-multiple exec-missing exec-bad-ptr
54              join-simple join-twice join-killed join-bad-pid
55              multi-recurse multi-oom multi-child-fd
56              ) unless @TESTS > 0;
57
58 our (%args);
59 for my $key ('args-argc', 'args-argv0', 'args-argvn', 'args-multiple') {
60     $args{$key} = "some arguments for you!";
61 }
62 $args{'args-single'} = "onearg";
63 $args{'args-dbl-space'} = "two  args";
64 $args{'multi-recurse'} = "15";
65 $args{'multi-oom'} = "0";
66
67 # Handle final grade mode.
68 if ($grade) {
69     open (OUT, ">grade.out") or die "grade.out: create: $!\n";
70
71     open (GRADE, "<grade.txt") or die "grade.txt: open: $!\n";
72     while (<GRADE>) {
73         last if /^\s*$/;
74         print OUT;
75     }
76     close (GRADE);
77     
78     my (@tests) = snarf ("tests.out");
79     my ($p_got, $p_pos) = $tests[0] =~ m%\((\d+)/(\d+)\)% or die;
80
81     my (@review) = snarf ("review.txt");
82     my ($part_lost) = (0, 0);
83     for (my ($i) = $#review; $i >= 0; $i--) {
84         local ($_) = $review[$i];
85         if (my ($loss) = /^\s*([-+]\d+)/) {
86             $part_lost += $loss;
87         } elsif (my ($out_of) = m%\[\[/(\d+)\]\]%) {
88             my ($got) = $out_of + $part_lost;
89             $got = 0 if $got < 0;
90             $review[$i] =~ s%\[\[/\d+\]\]%($got/$out_of)% or die;
91             $part_lost = 0;
92
93             $p_got += $got;
94             $p_pos += $out_of;
95         }
96     }
97     die "Lost points outside a section\n" if $part_lost;
98
99     for (my ($i) = 1; $i <= $#review; $i++) {
100         if ($review[$i] =~ /^-{3,}\s*$/ && $review[$i - 1] !~ /^\s*$/) {
101             $review[$i] = '-' x (length ($review[$i - 1]));
102         }
103     }
104
105     print OUT "\nOVERALL SCORE\n";
106     print OUT "-------------\n";
107     print OUT "$p_got points out of $p_pos total\n\n";
108
109     print OUT map ("$_\n", @tests), "\n";
110     print OUT map ("$_\n", @review), "\n";
111
112     print OUT "DETAILS\n";
113     print OUT "-------\n\n";
114     print OUT map ("$_\n", snarf ("details.out"));
115
116     exit 0;
117 }
118
119 # Find the directory that contains the grading files.
120 our ($GRADES_DIR);
121 ($GRADES_DIR = $0) =~ s#/[^/]+$##;
122 -d $GRADES_DIR or die "$GRADES_DIR: stat: $!\n";
123
124 if ($clean) {
125     # Verify that we're roughly in the correct directory
126     # before we go blasting away files.
127     choose_tarball ();
128
129     xsystem ("rm -rf output pintos", VERBOSE => 1);
130     xsystem ("rm -f details.out tests.out", VERBOSE => 1);
131 }
132
133 # Create output directory, if it doesn't already exist.
134 -d ("output") || mkdir ("output") or die "output: mkdir: $!\n";
135
136 # Extract submission.
137 extract_tarball () if ! -d "pintos";
138
139 # Compile submission.
140 compile ();
141
142 # Verify that the proper directory was submitted.
143 -d "pintos/src/threads" or die "pintos/src/threads: stat: $!\n";
144
145 # Run and grade the tests.
146 our $test;
147 our %result;
148 our %details;
149 our %extra;
150 for $test (@TESTS) {
151     print "$test: ";
152     my ($result) = run_test ($test);
153     if ($result eq 'ok') {
154         $result = grade_test ($test);
155         $result =~ s/\n$//;
156     }
157     print "$result";
158     print " - with warnings" if $result eq 'ok' && defined $details{$test};
159     print "\n";
160     
161     $result{$test} = $result;
162 }
163
164 # Write output.
165 write_grades ();
166 write_details ();
167 \f
168 sub choose_tarball {
169     my (@tarballs)
170         = grep (/^[a-z0-9]+\.[A-Za-z]+\.\d+\.\d+\.\d+\.\d+.\d+\.tar\.gz$/,
171                 glob ("*.tar.gz"));
172     die "no pintos dir and no source tarball\n" if scalar (@tarballs) == 0;
173
174     # Sort tarballs in reverse order by time.
175     @tarballs = sort { ext_mdyHMS ($b) cmp ext_mdyHMS ($a) } @tarballs;
176
177     print "Multiple tarballs: choosing $tarballs[0]\n"
178         if scalar (@tarballs) > 1;
179     return $tarballs[0];
180 }
181
182 sub extract_tarball {
183     my ($tarball) = choose_tarball ();
184
185     mkdir "pintos" or die "pintos: mkdir: $!\n";
186     mkdir "pintos/src" or die "pintos: mkdir: $!\n";
187
188     print "Extracting $tarball...\n";
189     xsystem ("cd pintos/src && tar xzf ../../$tarball",
190              DIE => "extraction failed\n");
191
192     print "Patching...\n";
193     xsystem ("patch -fs pintos/src/lib/debug.c < $GRADES_DIR/panic.diff",
194              LOG => "patch",
195              DIE => "patch failed\n");
196     xsystem ("patch -fs pintos/src/lib/kernel/bitmap.c "
197              . "< $GRADES_DIR/random.diff",
198              LOG => "patch",
199              DIE => "patch failed\n");
200
201     open (CONSTANTS, ">pintos/src/constants.h")
202         or die "constants.h: create: $!\n";
203     print CONSTANTS "#define THREAD_JOIN_IMPLEMENTED 1\n";
204     close CONSTANTS;
205 }
206
207 sub ext_mdyHMS {
208     my ($s) = @_;
209     my ($ms, $d, $y, $H, $M, $S) =
210         $s =~ /.([A-Za-z]+)\.(\d+)\.(\d+)\.(\d+)\.(\d+).(\d+)\.tar\.gz$/
211         or die;
212     my ($m) = index ("janfebmaraprmayjunjulaugsepoctnovdec", lc $ms) / 3
213         or die;
214     return sprintf "%02d-%02d-%02d %02d:%02d:%02d", $y, $m, $d, $H, $M, $S;
215 }
216 \f
217 sub test_source {
218     my ($test) = @_;
219     my ($src) = "$GRADES_DIR/$test.c";
220     -e $src or die "$src: stat: $!\n";
221     return $src;
222 }
223
224 sub test_constants {
225    my ($defines) = "";
226    return $defines;
227  }
228
229 sub run_test {
230     my ($test) = @_;
231
232     # Reuse older results if any.
233     if (open (DONE, "<output/$test/done")) {
234         my ($status);
235         $status = <DONE>;
236         chomp $status;
237         close (DONE);
238         return $status;
239     }
240
241     # Really run the test.
242     my ($status) = really_run_test ($test);
243
244     # Save the results for later.
245     open (DONE, ">output/$test/done") or die "output/$test/done: create: $!\n";
246     print DONE "$status\n";
247     close (DONE);
248
249     return $status;
250 }
251
252 sub compile {
253     print "Compiling...\n";
254     xsystem ("cd pintos/src/userprog && make", LOG => "make")
255         or return "compile error";
256 }
257
258 sub really_run_test {
259     # Need to run it.
260     # If there's residue from an earlier test, move it to .old.
261     # If there's already a .old, delete it.
262     xsystem ("rm -rf output/$test.old", VERBOSE => 1) if -d "output/$test.old";
263     rename "output/$test", "output/$test.old" or die "rename: $!\n"
264         if -d "output/$test";
265
266     # Make output directory.
267     mkdir "output/$test";
268     xsystem ("cp $GRADES_DIR/$test.dsk output/$test/fs.dsk",
269              DIE => "cp failed\n");
270
271     # Run.
272     my ($timeout) = 10;
273     $timeout = 60 if $test eq 'multi-oom';
274     my ($testargs) = defined ($args{$test}) ? " $args{$test}" : "";
275     xsystem ("pintos "
276              . "--os-disk=pintos/src/userprog/build/os.dsk "
277              . "--fs-disk=output/$test/fs.dsk "
278              . "-v run -q -ex \"$test$testargs\"",
279              LOG => "$test/run",
280              TIMEOUT => $timeout)
281         or return "Bochs error";
282     
283     return "ok";
284 }
285
286 sub grade_test {
287     my ($test) = @_;
288
289     my (@output) = snarf ("output/$test/run.out");
290
291     my ($grade_func) = "grade_$test";
292     $grade_func =~ s/-/_/g;
293     if (-e "$GRADES_DIR/$test.exp" && !defined (&$grade_func)) {
294         eval {
295             verify_common (@output);
296             compare_output ("$GRADES_DIR/$test.exp", @output);
297         }
298     } else {
299         eval "$grade_func (\@output)";
300     }
301     if ($@) {
302         die $@ if $@ =~ /at \S+ line \d+$/;
303         return $@;
304     }
305     return "ok";
306 }
307 \f
308 sub grade_write_normal {
309     my (@output) = @_;
310     verify_common (@output);
311     compare_output ("$GRADES_DIR/write-normal.exp", @output);
312     my ($test_txt) = "output/$test/test.txt";
313     get_file ("test.txt", $test_txt) if ! -e $test_txt;
314
315     my (@actual) = snarf ($test_txt);
316     my (@expected) = snarf ("$GRADES_DIR/sample.txt");
317
318     my ($eq);
319     if ($#actual == $#expected) {
320         $eq = 1;
321         for my $i (0...$#actual) {
322             $eq = 0 if $actual[$i] ne $expected[$i];
323         }
324     } else {
325         $eq = 0;
326     }
327     if (!$eq) {
328         my ($details);
329         $details = "Expected file content:\n";
330         $details .= join ('', map ("  $_\n", @expected));
331         $details .= "Actual file content:\n";
332         $details .= join ('', map ("  $_\n", @actual));
333         $extra{$test} = $details;
334
335         die "File written didn't have expected content.\n";
336     }
337 }
338
339 sub grade_multi_oom {
340     my (@output) = @_;
341     verify_common (@output);
342
343     @output = fix_exit_codes (get_core_output (@output));
344     my ($n) = 0;
345     while (my ($m) = $output[0] =~ /^\(multi-oom\) begin (\d+)$/) {
346         die "Child process $m started out of order.\n" if $m != $n;
347         $n = $m + 1;
348         shift @output;
349     }
350     die "Only $n child processes started.\n" if $n < 15;
351
352     # There could be a death notice for a process that didn't get
353     # fully loaded, and/or notices from the loader.
354     while (@output > 0
355            && ($output[0] =~ /^\(multi-oom\) end $n$/
356                || $output[0] =~ /^load: /)) {
357         shift @output;
358     }
359
360     while (--$n >= 0) {
361         die "Output ended unexpectedly before process $n finished.\n"
362             if @output < 2;
363
364         local ($_);
365         chomp ($_ = shift @output);
366         die "Found '$_' expecting 'end' message.\n" if !/^\(multi-oom\) end/;
367         die "Child process $n ended out of order.\n"
368             if !/^\(multi-oom\) end $n$/;
369
370         chomp ($_ = shift @output);
371         die "Kernel didn't print proper exit message for process $n.\n"
372             if !/^multi-oom: exit\($n\)$/;
373     }
374     die "Spurious output at end: '$output[0]'.\n" if @output;
375 }
376
377 sub get_file {
378     my ($guest_fn, $host_fn) = @_;
379     xsystem ("pintos "
380              . "--os-disk=pintos/src/userprog/build/os.dsk "
381              . "--fs-disk=output/$test/fs.dsk "
382              . "-v get $guest_fn $host_fn",
383              LOG => "$test/get-$guest_fn",
384              TIMEOUT => 10)
385         or die "get $guest_fn failed\n";
386 }
387
388 \f
389 sub verify_common {
390     my (@output) = @_;
391
392     my (@assertion) = grep (/PANIC/, @output);
393     if (@assertion != 0) {
394         my ($details) = "Kernel panic:\n  $assertion[0]\n";
395
396         my (@stack_line) = grep (/Call stack:/, @output);
397         if (@stack_line != 0) {
398             $details .= "  $stack_line[0]\n\n";
399             $details .= "Translation of backtrace:\n";
400             my (@addrs) = $stack_line[0] =~ /Call stack:((?: 0x[0-9a-f]+)+)/;
401
402             my ($A2L);
403             if (`uname -m`
404                 =~ /i.86|pentium.*|[pk][56]|nexgen|viac3|6x86|athlon.*/) {
405                 $A2L = "addr2line";
406             } else {
407                 $A2L = "i386-elf-addr2line";
408             }
409             open (A2L, "$A2L -fe pintos/src/userprog/build/kernel.o @addrs|");
410             for (;;) {
411                 my ($function, $line);
412                 last unless defined ($function = <A2L>);
413                 $line = <A2L>;
414                 chomp $function;
415                 chomp $line;
416                 $details .= "  $function ($line)\n";
417             }
418         }
419         $extra{$test} = $details;
420         die "Kernel panic.  Details at end of file.\n"
421     }
422
423     die "No output at all\n" if @output == 0;
424     die "Didn't start up properly: no \"Pintos booting\" startup message\n"
425         if !grep (/Pintos booting with.*kB RAM\.\.\./, @output);
426     die "Didn't start up properly: no \"Boot complete\" startup message\n"
427         if !grep (/Boot complete/, @output);
428     die "Didn't shut down properly: no \"Timer: # ticks\" shutdown message\n"
429         if !grep (/Timer: \d+ ticks/, @output);
430     die "Didn't shut down properly: no \"Powering off\" shutdown message\n"
431         if !grep (/Powering off/, @output);
432 }
433
434 # Get @output without header or trailer.
435 sub get_core_output {
436     my (@output) = @_;
437
438     our ($test);
439     my ($first);
440     for ($first = 0; $first <= $#output; $first++) {
441         $first++, last if $output[$first] =~ /^Executing '$test.*':$/;
442     }
443
444     my ($last);
445     for ($last = $#output; $last >= 0; $last--) {
446         $last--, last if $output[$last] =~ /^Timer: \d+ ticks$/;
447     }
448
449     if ($last < $first) {
450         my ($no_first) = $first > $#output;
451         my ($no_last) = $last < $#output;
452         die "Couldn't locate output.\n";
453     }
454
455     return @output[$first ... $last];
456 }
457
458 sub fix_exit_codes {
459     my (@output) = @_;
460
461     # Fix up lines that look like exit codes.
462     # Exit codes are supposed to be printed in the form "process: exit(code)"
463     # but people get unfortunately creative with it.
464     for my $i (0...$#output) {
465         local ($_) = $output[$i];
466         
467         my ($process, $code);
468         if ((($process, $code) = /^([-a-zA-Z0-9 ]+):.*[ \(](-?\d+)\b\)?$/)
469             || (($process, $code) = /^([-a-zA-Z0-9 ]+) exit\((-?\d+)\)$/)
470             || (($process, $code)
471                 = /^([-a-zA-Z0-9 ]+) \(.*\): exit\((-?\d+)\)$/)
472             || (($process, $code) = /^([-a-zA-Z0-9 ]+):\( (-?\d+) \) $/)
473 ) {
474             $process = substr ($process, 0, 15);
475             $process =~ s/\s.*//;
476             $output[$i] = "$process: exit($code)\n";
477         }
478     }
479
480     return @output;
481 }
482
483 sub compare_output {
484     my ($exp, @actual) = @_;
485     @actual = fix_exit_codes (get_core_output (map ("$_\n", @actual)));
486
487     my ($details) = "";
488     $details .= "$test actual output:\n";
489     $details .= join ('', map ("  $_", @actual));
490
491     my (@exp) = map ("$_\n", snarf ($exp));
492
493     my ($fuzzy_match) = 0;
494     while (@exp != 0) {
495         my (@expected);
496         while (@exp != 0) {
497             my ($s) = shift (@exp);
498             last if $s eq "--OR--\n";
499             push (@expected, $s);
500         }
501
502         $details .= "\n$test acceptable output:\n";
503         $details .= join ('', map ("  $_", @expected));
504
505         # Check whether they're the same.
506         if ($#actual == $#expected) {
507             my ($eq) = 1;
508             for (my ($i) = 0; $i <= $#expected; $i++) {
509                 $eq = 0 if $actual[$i] ne $expected[$i];
510             }
511             return if $eq;
512         }
513
514         # They differ.  Output a diff.
515         my (@diff) = "";
516         my ($d) = Algorithm::Diff->new (\@expected, \@actual);
517         my ($not_fuzzy_match) = 0;
518         while ($d->Next ()) {
519             my ($ef, $el, $af, $al) = $d->Get (qw (min1 max1 min2 max2));
520             if ($d->Same ()) {
521                 push (@diff, map ("  $_", $d->Items (1)));
522             } else {
523                 push (@diff, map ("- $_", $d->Items (1))) if $d->Items (1);
524                 push (@diff, map ("+ $_", $d->Items (2))) if $d->Items (2);
525                 if ($d->Items (1)
526                     || grep (/\($test\)|exit\(-?\d+\)/, $d->Items (2))) {
527                     $not_fuzzy_match = 1;
528                 }
529             }
530         }
531         $fuzzy_match = 1 if !$not_fuzzy_match;
532
533         $details .= "Differences in `diff -u' format:\n";
534         $details .= join ('', @diff);
535         $details .= "(This is considered a `fuzzy match'.)\n"
536             if !$not_fuzzy_match;
537     }
538
539     $details{$test} = $details;
540     die "Output differs from expected.  Details at end of file.\n"
541         unless $fuzzy_match;
542 }
543 \f
544 sub write_grades {
545     my (@summary) = snarf ("$GRADES_DIR/tests.txt");
546
547     my ($ploss) = 0;
548     my ($tloss) = 0;
549     my ($total) = 0;
550     for (my ($i) = 0; $i <= $#summary; $i++) {
551         local ($_) = $summary[$i];
552         if (my ($loss, $test) = /^  -(\d+) ([-a-zA-Z0-9]+):/) {
553             my ($result) = $result{$test} || "Not tested.";
554
555             if ($result eq 'ok') {
556                 splice (@summary, $i, 1);
557                 $i--;
558             } else {
559                 $ploss += $loss;
560                 $tloss += $loss;
561                 splice (@summary, $i + 1, 0,
562                         map ("     $_", split ("\n", $result)));
563             }
564         } elsif (my ($ptotal) = /^Score: \/(\d+)$/) {
565             $total += $ptotal;
566             $summary[$i] = "Score: " . ($ptotal - $ploss) . "/$ptotal";
567             splice (@summary, $i, 0, "  All tests passed.") if $ploss == 0;
568             $ploss = 0;
569             $i++;
570         }
571     }
572     my ($ts) = "(" . ($total - $tloss) . "/" . $total . ")";
573     $summary[0] =~ s/\[\[total\]\]/$ts/;
574
575     open (SUMMARY, ">tests.out");
576     print SUMMARY map ("$_\n", @summary);
577     close (SUMMARY);
578 }
579
580 sub write_details {
581     open (DETAILS, ">details.out");
582     my ($n) = 0;
583     for my $test (@TESTS) {
584         next if $result{$test} eq 'ok' && !defined $details{$test};
585         
586         my ($details) = $details{$test};
587         next if !defined ($details) && ! -e "output/$test/run.out";
588
589         print DETAILS "\n" if $n++;
590         print DETAILS "--- $test details ", '-' x (50 - length ($test));
591         print DETAILS "\n\n";
592
593         if (!defined $details) {
594             $details = "Output:\n\n" . snarf ("output/$test/run.out");
595         }
596         print DETAILS $details;
597
598         print DETAILS "\n", "-" x 10, "\n\n$extra{$test}"
599             if defined $extra{$test};
600     }
601     close (DETAILS);
602
603 }
604 \f
605 sub xsystem {
606     my ($command, %options) = @_;
607     print "$command\n" if $VERBOSE || $options{VERBOSE};
608
609     my ($log) = $options{LOG};
610     if (defined ($log)) {
611         $command = "($command) >output/$log.out 2>output/$log.err";
612     }
613
614     my ($pid, $status);
615     eval {
616         local $SIG{ALRM} = sub { die "alarm\n" };
617         alarm $options{TIMEOUT} if defined $options{TIMEOUT};
618         $pid = fork;
619         die "fork: $!\n" if !defined $pid;
620         exec ($command), die "$command: exec: $!\n" if !$pid;
621         waitpid ($pid, 0);
622         $status = $?;
623         alarm 0;
624     };
625     if ($@) {
626         die unless $@ eq "alarm\n";   # propagate unexpected errors
627         print "Timed out.\n";
628         kill SIGTERM, $pid;
629         $status = 0;
630     }
631
632     if (WIFSIGNALED ($status)) {
633         my ($signal) = WTERMSIG ($status);
634         die "Interrupted\n" if $signal == SIGINT;
635         print "Child terminated with signal $signal\n";
636     }
637
638     unlink ("output/$log.err") if defined ($log) && $status == 0;
639
640     die $options{DIE} if $status != 0 && defined $options{DIE};
641
642     return $status == 0;
643 }
644
645 sub snarf {
646     my ($file) = @_;
647     open (OUTPUT, $file) or die "$file: open: $!\n";
648     my (@lines) = <OUTPUT>;
649     chomp (@lines);
650     close (OUTPUT);
651     return wantarray ? @lines : join ('', map ("$_\n", @lines));
652 }
653
654 sub files_equal {
655     my ($a, $b) = @_;
656     my ($equal);
657     open (A, "<$a") or die "$a: open: $!\n";
658     open (B, "<$b") or die "$b: open: $!\n";
659     if (-s A != -s B) {
660         $equal = 0;
661     } else {
662         my ($sa, $sb);
663         for (;;) {
664             sysread (A, $sa, 1024);
665             sysread (B, $sb, 1024);
666             $equal = 0, last if $sa ne $sb;
667             $equal = 1, last if $sa eq '';
668         }
669     }
670     close (A);
671     close (B);
672     return $equal;
673 }
674
675 sub file_contains {
676     my ($file, $expected) = @_;
677     open (FILE, "<$file") or die "$file: open: $!\n";
678     my ($actual);
679     sysread (FILE, $actual, -s FILE);
680     my ($equal) = $actual eq $expected;
681     close (FILE);
682     return $equal;
683 }
684
685 sub number_lines {
686     my ($ln, $lines) = @_;
687     my ($out);
688     for my $line (@$lines) {
689         chomp $line;
690         $out .= sprintf "%4d  %s\n", $ln++, $line;
691     }
692     return $out;
693 }