From 420b9b42eb65db5b619efa79cb613f01fdc408cb Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Mon, 18 Oct 2004 22:22:42 +0000 Subject: [PATCH] Improve run-tests. Edit the grading result files. --- grading/threads/review.txt | 49 +++-- grading/threads/run-tests | 435 +++++++++++++++++++++---------------- grading/threads/tests.txt | 2 + 3 files changed, 280 insertions(+), 206 deletions(-) diff --git a/grading/threads/review.txt b/grading/threads/review.txt index 3c01e7a..62c5d81 100644 --- a/grading/threads/review.txt +++ b/grading/threads/review.txt @@ -1,5 +1,17 @@ -DESIGN [[/40] -------------- +TESTCASES [[/10]] +----------------- + -2 Problem 1-1: no test cases/no test output/no description in TESTCASES + -1 Problem 1-1: not enough testing/inconclusive test output + -2 Problem 1-2: no test cases/no test output/no description in TESTCASES + -1 Problem 1-2: not enough testing/inconclusive test output + -2 Problem 1-3: no test cases/no test output/no description in TESTCASES + -1 Problem 1-3: not enough testing/inconclusive test output + -2 Problem 1-4: no test cases/no test output/no description in TESTCASES + -1 Problem 1-4: not enough testing/inconclusive test output + + +DESIGN [[/40]] +-------------- -20 Missing or far too brief DESIGNDOC -2 Troublesome or unexplained dependencies @@ -10,15 +22,18 @@ DESIGNDOC (per problem): -2 Major details missing -5 Totally missing +Overall: + -1 Gratuitous use of malloc() (e.g. for allocating a list or a lock) + -1 Inappropriate use of ASSERT (e.g. to verify that malloc() succeeded) + Problem 1-1: Alarm Clock -1 Uses lock/interrupt disabling without justifying - -1 Uses a lock inside of CallBack + -1 Uses a lock within interrupt handler -3 Busy waiting -2 Wakes up too often, e.g. by using semaphores with negative values -1 Traverses entire list of sleeping threads every tick - -1 Put threads to sleep directly - -1 Doesn't protect data structure in CallBack - -1 Doesn't protect data structure in WaitUntil + -1 Doesn't protect data structure in timer_interrupt + -1 Doesn't protect data structure in timer_sleep -3 Bad design Problem 1-2: Join @@ -26,15 +41,15 @@ Problem 1-2: Join -3 A static list of all parent-child pairs is extremely wasteful -3 Obviously wasteful with memory (not deleting threads) -2 Finished parent deletes children which may still be running - -1 Enable/disable interrupts or put thread to sleep directly - -2 Joinable child lets its Thread object be deleted before parent dies + -1 Enable/disable interrupts + -2 Joinable child lets its struct thread be deleted before parent dies -1 Race condition between join and thread exit Problem 1-3: Priority Scheduler -3 Doesn't use sorted queue scheduler, and don't justify why they didn't - -1 Semaphores don't wake highest-priority thread first - -1 Condition variables don't wake highest-priority thread first + -2 sema_up() doesn't pick highest-priority waiting thread -1 Should use sorted queue in semaphores, unless explained in DESIGNDOC + -1 cond_signal() doesn't pick highest-priority waiting thread -1 Should use sorted queue in conditions, unless explained in DESIGNDOC -2 Yield should pick the highest-priority thread (including current) -3 Bad design @@ -45,21 +60,9 @@ Problem 1-4: Advanced Scheduler -5 Bad design -TESTCASES [[/10] ----------------- - -2 Problem 1-1: no test cases/no test output/no description in TESTCASES - -1 Problem 1-1: not enough testing/inconclusive test output - -2 Problem 1-2: no test cases/no test output/no description in TESTCASES - -1 Problem 1-2: not enough testing/inconclusive test output - -2 Problem 1-3: no test cases/no test output/no description in TESTCASES - -1 Problem 1-3: not enough testing/inconclusive test output - -2 Problem 1-4: no test cases/no test output/no description in TESTCASES - -1 Problem 1-4: not enough testing/inconclusive test output - - STYLE [[/10]] ------------- -Insert any comments here + -1 No attempt to conform to existing coding style COMMENTS diff --git a/grading/threads/run-tests b/grading/threads/run-tests index f40e0d8..7d64196 100755 --- a/grading/threads/run-tests +++ b/grading/threads/run-tests @@ -1,15 +1,96 @@ -#! /usr/bin/perl -w +#! /usr/bin/perl +use warnings; +use strict; use POSIX; -use Text::Diff; +use Algorithm::Diff; +use Getopt::Long; + +our ($VERBOSE) = 0; # Verbosity of output +our (@TESTS); # Tests to run. +my ($clean) = 0; + +GetOptions ("v|verbose+" => \$VERBOSE, + "h|help" => sub { usage (0) }, + "t|test=s" => \@TESTS, + "c|clean" => \$clean) + or die "Malformed command line; use --help for help.\n"; +die "Non-option argument not supported; use --help for help.\n" + if @ARGV > 0; + +sub usage { + my ($exitcode) = @_; + print "run-tests, for grading Pintos thread projects.\n\n"; + print "Invoke from a directory containing a student tarball named by\n"; + print "the submit script, e.g. username.Oct.12.04.20.04.09.tar.gz.\n"; + print "In normal usage, no options are needed.\n\n"; + print "Output is produced in tests.out and details.out.\n\n"; + print "Options:\n"; + print " -c, --clean Remove old output files before starting\n"; + print " -t, --test=TEST Execute TEST only (allowed multiple times)\n"; + print " -v, --verbose Print commands before executing them\n"; + print " -h, --help Print this help message\n"; + exit $exitcode; +} -$verbose = 0; +# Default set of tests. +@TESTS = ("alarm-single", "alarm-multiple", "alarm-zero", "alarm-negative", + "join-simple", + "join-quick", "join-multiple", "join-nested", + "join-dummy", "join-invalid", "join-no", + "priority-preempt", "priority-fifo", "priority-donate-one", + "priority-donate-multiple", "priority-donate-nest", + "mlfqs-on", "mlfqs-off") + unless @TESTS > 0; + +# Find the directory that contains the grading files. +our ($GRADES_DIR); ($GRADES_DIR = $0) =~ s#/[^/]+$##; -d $GRADES_DIR or die "$GRADES_DIR: stat: $!\n"; +if ($clean) { + # Verify that we're roughly in the correct directory + # before we go blasting away files. + choose_tarball (); + + xsystem ("rm -rf output pintos", VERBOSE => 1); + xsystem ("rm -f details.out tests.out", VERBOSE => 1); +} + +# Create output directory, if it doesn't already exist. -d ("output") || mkdir ("output") or die "output: mkdir: $!\n"; -if (! -d "pintos") { +# Extract submission. +extract_tarball () if ! -d "pintos"; + +# Verify that the proper directory was submitted. +-d "pintos/src/threads" or die "pintos/src/threads: stat: $!\n"; + +# Run and grade the tests. +our $test; +our %result; +our %details; +our %extra; +for $test (@TESTS) { + my ($result); + do { + print "$test: "; + $result = run_test ($test); + if ($result eq 'ok') { + $result = grade_test ($test); + $result =~ s/\n$//; + } + print "$result\n"; + } while ($result eq 'rerun'); + + $result{$test} = $result; +} + +# Write output. +write_grades (); +write_details (); + +sub choose_tarball { my (@tarballs) = grep (/^[a-z0-9]+\.[A-Za-z]+\.\d+\.\d+\.\d+\.\d+.\d+\.tar\.gz$/, glob ("*.tar.gz")); @@ -17,56 +98,80 @@ if (! -d "pintos") { # Sort tarballs in reverse order by time. @tarballs = sort { ext_mdyHMS ($b) cmp ext_mdyHMS ($a) } @tarballs; - - die "no pintos dir and multiple tarballs\n" if scalar (@tarballs) > 1; + + print "Multiple tarballs: choosing $tarballs[0]\n" + if scalar (@tarballs) > 1; + return $tarballs[0]; +} + +sub extract_tarball { + my ($tarball) = choose_tarball (); + mkdir "pintos" or die "pintos: mkdir: $!\n"; mkdir "pintos/src" or die "pintos: mkdir: $!\n"; - print "Extracting $tarballs[0]...\n"; - xsystem ("", "cd pintos/src && tar xzf ../../$tarballs[0]") - or die "extraction failed\n"; + print "Extracting $tarball...\n"; + xsystem ("cd pintos/src && tar xzf ../../$tarball", + DIE => "extraction failed\n"); print "Patching...\n"; - xsystem ("panic.diff", - "patch -fs pintos/src/lib/debug.c < $GRADES_DIR/panic.diff") - or die "patch failed\n"; + xsystem ("patch -fs pintos/src/lib/debug.c < $GRADES_DIR/panic.diff", + LOG => "patch", + DIE => "patch failed\n"); } --d "pintos/src/threads" or die "pintos/src/threads: stat: $!\n"; sub ext_mdyHMS { - my ($s) = $_; + my ($s) = @_; my ($ms, $d, $y, $H, $M, $S) = $s =~ /.([A-Za-z]+)\.(\d+)\.(\d+)\.(\d+)\.(\d+).(\d+)\.tar\.gz$/ or die; my ($m) = index ("janfebmaraprmayjunjulaugsepoctnovdec", lc $ms) / 3 or die; - return sprintf "%02d-%02d-%02d %02d:%02d:%02d", $m, $d, $y, $H, $M, $S; + return sprintf "%02d-%02d-%02d %02d:%02d:%02d", $y, $m, $d, $H, $M, $S; +} + +sub test_source { + my ($test) = @_; + my ($src) = "$GRADES_DIR/$test.c"; + $src = "$GRADES_DIR/mlfqs.c" if $test =~ /^mlfqs/; + -e $src or die "$src: stat: $!\n"; + return $src; } -@TESTS = ("alarm-single", "alarm-multiple", "alarm-zero", "alarm-negative", - "join-simple", - "join-quick", "join-multiple", "join-nested", - "join-dummy", "join-invalid", "join-no", - "priority-preempt", "priority-fifo", "priority-donate-one", - "priority-donate-multiple", "priority-donate-nest", - "mlfqs-on", "mlfqs-off"); +sub test_constants { + my ($defines) = ""; + $defines .= "#define MLFQS 1\n" if $test eq 'mlfqs-on'; + return $defines; + } -for $test (@TESTS) { - my ($result); - do { - print "$test: "; - $result = run_test ($test); - if ($result eq 'ok') { - $result = grade_test ($test); - $result =~ s/\n$//; - } - print "$result\n"; - } while ($result eq 'rerun'); - - $result{$test} = $result; -} +sub run_test { + my ($test) = @_; + return "ok" if -f "output/$test.run.out"; -make_summary (); + my ($defines) = test_constants ($test); + if ($defines ne snarf ("pintos/src/constants.h")) { + open (CONSTANTS, ">pintos/src/constants.h"); + print CONSTANTS $defines; + close (CONSTANTS); + } + + my ($src) = test_source ($test); + xsystem ("cp $src pintos/src/threads/test.c", DIE => "cp failed\n"); + unlink ("pintos/src/threads/build/threads/test.o"); + unlink ("pintos/src/threads/build/kernel.o"); + unlink ("pintos/src/threads/build/kernel.bin"); + unlink ("pintos/src/threads/build/os.dsk"); + xsystem ("cd pintos/src/threads && make", LOG => "$test.make") + or return "compile error"; + + my ($timeout) = 10; + $timeout = 600 if $test =~ /^mlfqs/; + xsystem ("cd pintos/src/threads/build && pintos -v run -q", + LOG => "$test.run", + TIMEOUT => $timeout) + or return "Bochs error"; + return "ok"; +} sub grade_test { my ($test) = @_; @@ -78,9 +183,10 @@ sub grade_test { verify_common (@output); compare_output ("$GRADES_DIR/$test.exp", @output); } - } else { + } else { + my ($grade_func); ($grade_func = $test) =~ s/-/_/g; - eval "grade_$grade_func(\@output)"; + eval "grade_$grade_func (\@output)"; } if ($@) { die $@ if $@ =~ /at \S+ line \d+$/; @@ -88,7 +194,7 @@ sub grade_test { } return "ok"; } - + sub grade_alarm_single { verify_alarm (1, @_); } @@ -97,6 +203,34 @@ sub grade_alarm_multiple { verify_alarm (7, @_); } +sub verify_alarm { + my ($iterations, @output) = @_; + + verify_common (@output); + + my (@products); + for (my ($i) = 0; $i < $iterations; $i++) { + for (my ($t) = 0; $t < 5; $t++) { + push (@products, ($i + 1) * ($t + 1) * 10); + } + } + @products = sort {$a <=> $b} @products; + + local ($_); + foreach (@output) { + die $_ if /Out of order/; + + my ($p) = /product=(\d+)$/; + next if !defined $p; + + my ($q) = shift (@products); + die "Too many wakeups.\n" if !defined $q; + die "Out of order wakeups ($p vs. $q).\n" if $p != $q; # FIXME + } + die scalar (@products) . " fewer wakeups than expected.\n" + if @products != 0; +} + sub grade_alarm_zero { my (@output) = @_; verify_common (@output); @@ -129,7 +263,8 @@ sub grade_join_multiple { verify_common (@output); my (@t); $t[4] = $t[5] = $t[6] = -1; - for $_ (@output) { + local ($_); + foreach (@output) { my ($idx) = /^Thread (\d+)/ or next; my ($iter) = /iteration (\d+)$/; $iter = 5 if /done!$/; @@ -165,7 +300,8 @@ sub grade_priority_fifo { my ($iter_cnt) = 5; my (@order); my (@t) = (-1) x $thread_cnt; - for $_ (@output) { + local ($_); + foreach (@output) { my ($idx) = /^Thread (\d+)/ or next; my ($iter) = /iteration (\d+)$/; $iter = $iter_cnt if /done!$/; @@ -213,7 +349,8 @@ sub mlfqs_stats { my (%map) = ("CPU intensive" => "cpu", "IO intensive" => "io", "Alternating IO/CPU" => "mix"); - for $_ (@output) { + local ($_); + foreach (@output) { my ($thread, $pri) = /^([A-Za-z\/ ]+): (\d+)$/ or next; my ($t) = $map{$thread} or next; @@ -224,22 +361,16 @@ sub mlfqs_stats { $$s{"min"} = $pri if !defined ($$s{"min"}) || $pri < $$s{"min"}; $$s{"max"} = $pri if !defined ($$s{"max"}) || $pri > $$s{"max"}; } + + my ($details) = ""; for my $t (keys %stats) { my ($s) = $stats{$t}; - print "$t: n=$$s{'n'}, min=$$s{'min'}, max=$$s{'max'}, avg=", int ($$s{'sum'} / $$s{'n'}), "\n"; - } -} - -sub get_binaries { - if (!files_equal ("pintos/src/threads/test.c", test_source ($test)) - || !file_contains ("pintos/src/constants.h", - test_constants ($test))) { - unlink ("output/$test.run.out") - or die "output/$test.run.out: unlink: $!\n"; - die "rerun\n"; + $details .= "$t: n=$$s{'n'}, min=$$s{'min'}, max=$$s{'max'}, avg=" . int ($$s{'sum'} / $$s{'n'}) . "\n"; } + $details{$test} = $details; + die "MLFQS\n"; } - + sub verify_common { my (@output) = @_; @@ -262,8 +393,8 @@ sub verify_common { $A2L = "i386-elf-addr2line"; } open (A2L, "$A2L -fe pintos/src/threads/build/kernel.o $addrs|"); - while ($function = ) { - $line = ; + while (my $function = ) { + my ($line) = ; chomp $function; chomp $line; $details .= " $function ($line)\n"; @@ -284,6 +415,16 @@ sub verify_common { if !grep (/Powering off/, @output); } +sub get_binaries { + if (!files_equal ("pintos/src/threads/test.c", test_source ($test)) + || !file_contains ("pintos/src/constants.h", + test_constants ($test))) { + unlink ("output/$test.run.out") + or die "output/$test.run.out: unlink: $!\n"; + die "rerun\n"; + } +} + sub compare_output { my ($exp_file, @actual) = @_; my (@expected) = snarf ($exp_file); @@ -351,138 +492,17 @@ sub compare_output { $details{$test} = $details; die "Output differs from expected. Details at end of file.\n"; } - -sub verify_alarm { - my ($iterations, @output) = @_; - - verify_common (@output); - - my (@products); - for (my ($i) = 0; $i < $iterations; $i++) { - for (my ($t) = 0; $t < 5; $t++) { - push (@products, ($i + 1) * ($t + 1) * 10); - } - } - @products = sort {$a <=> $b} @products; - - for $_ (@output) { - die $_ if /Out of order/; - - my ($p) = /product=(\d+)$/; - next if !defined $p; - - my ($q) = shift (@products); - die "Too many wakeups.\n" if !defined $q; - die "Out of order wakeups ($p vs. $q).\n" if $p != $q; # FIXME - } - die scalar (@products) . " fewer wakeups than expected.\n" - if @products != 0; -} - -sub test_source { - my ($test) = @_; - my ($src) = "$GRADES_DIR/$test.c"; - $src = "$GRADES_DIR/mlfqs.c" if $test =~ /^mlfqs/; - -e $src or die "$src: stat: $!\n"; - return $src; -} - -sub test_constants { - my ($defines) = ""; - $defines .= "#define MLFQS 1\n" if $test eq 'mlfqs-on'; - return $defines; - } - -sub run_test { - my ($test) = @_; - return "ok" if -f "output/$test.run.out"; - - my ($defines) = test_constants ($test); - if ($defines ne snarf ("pintos/src/constants.h")) { - open (CONSTANTS, ">pintos/src/constants.h"); - print CONSTANTS $defines; - close (CONSTANTS); - } - - $src = test_source ($test); - xsystem ("", "cp $src pintos/src/threads/test.c") or die; - unlink ("pintos/src/threads/build/threads/test.o"); - unlink ("pintos/src/threads/build/kernel.o"); - unlink ("pintos/src/threads/build/kernel.bin"); - unlink ("pintos/src/threads/build/os.dsk"); - xsystem ("$test.make", "cd pintos/src/threads && make") - or return "compile error"; - - my ($timeout) = 10; - $timeout = 600 if $test =~ /^mlfqs/; - xsystem ("$test.run", "cd pintos/src/threads/build && pintos -v run -q", - $timeout) - or return "Bochs error"; - return "ok"; -} - -sub xsystem { - my ($log, $command, $timeout) = @_; - print "$command\n" if $verbose; - - $timeout = 0 if !defined $timeout; - - my ($status); - if ($log ne '') { - $status = systimeout ("($command) >output/$log.out 2>output/$log.err", - $timeout); - unlink ("output/$log.err") unless $status != 0; - } else { - $status = systimeout ($command, $timeout); - } - - die "Interrupted\n" - if WIFSIGNALED ($status) && WTERMSIG ($status) == SIGINT; - - return $status == 0; -} - -sub systimeout { - my ($command, $timeout) = @_; - my ($pid, $status); - eval { - local $SIG{ALRM} = sub { die "alarm\n" }; - alarm $timeout; - $pid = fork; - die "fork: $!\n" if !defined $pid; - exec ($command), die "$command: exec: $!\n" if !$pid; - waitpid ($pid, 0); - $status = $?; - alarm 0; - }; - if ($@) { - die unless $@ eq "alarm\n"; # propagate unexpected errors - print "Timed out.\n"; - kill SIGTERM, $pid; - $status = 0; - } - return $status; -} - -sub snarf { - my ($file) = @_; - open (OUTPUT, $file) or die "$file: open: $!\n"; - my (@lines) = ; - chomp (@lines); - close (OUTPUT); - return wantarray ? @lines : join ('', map ("$_\n", @lines)); -} - -sub make_summary { - @summary = snarf ("$GRADES_DIR/tests.txt"); + +sub write_grades { + my (@summary) = snarf ("$GRADES_DIR/tests.txt"); my ($ploss) = 0; my ($tloss) = 0; my ($total) = 0; for (my ($i) = 0; $i <= $#summary; $i++) { - $_ = $summary[$i]; + local ($_) = $summary[$i]; if (my ($loss, $test) = /^ -(\d+) ([-a-zA-Z0-9]+):/) { - my ($result) = $result{$test} or die "missing results for $test\n"; + my ($result) = $result{$test} || "Not tested."; if ($result eq 'ok') { splice (@summary, $i, 1); @@ -507,7 +527,9 @@ sub make_summary { open (SUMMARY, ">tests.out"); print SUMMARY map ("$_\n", @summary); close (SUMMARY); +} +sub write_details { open (DETAILS, ">details.out"); my ($n) = 0; for my $test (@TESTS) { @@ -531,6 +553,53 @@ sub make_summary { close (DETAILS); } + +sub xsystem { + my ($command, %options) = @_; + print "$command\n" if $VERBOSE || $options{VERBOSE}; + + my ($log) = $options{LOG}; + if (defined ($log)) { + $command = "($command) >output/$log.out 2>output/$log.err"; + } + + my ($pid, $status); + eval { + local $SIG{ALRM} = sub { die "alarm\n" }; + alarm $options{TIMEOUT} if defined $options{TIMEOUT}; + $pid = fork; + die "fork: $!\n" if !defined $pid; + exec ($command), die "$command: exec: $!\n" if !$pid; + waitpid ($pid, 0); + $status = $?; + alarm 0; + }; + if ($@) { + die unless $@ eq "alarm\n"; # propagate unexpected errors + print "Timed out.\n"; + kill SIGTERM, $pid; + $status = 0; + } + + if (WIFSIGNALED ($status)) { + my ($signal) = WTERMSIG ($status); + die "Interrupted\n" if $signal == SIGINT; + print "Child terminated with signal $signal\n"; + } + + unlink ("output/$log.err") if defined ($log) && $status == 0; + + return $status == 0; +} + +sub snarf { + my ($file) = @_; + open (OUTPUT, $file) or die "$file: open: $!\n"; + my (@lines) = ; + chomp (@lines); + close (OUTPUT); + return wantarray ? @lines : join ('', map ("$_\n", @lines)); +} sub files_equal { my ($a, $b) = @_; diff --git a/grading/threads/tests.txt b/grading/threads/tests.txt index 3a37405..4c9e8de 100644 --- a/grading/threads/tests.txt +++ b/grading/threads/tests.txt @@ -30,6 +30,8 @@ Problem 1-3: Priority Scheduler Score: /10 Problem 1-4: Advanced Scheduler + -2 mlfqs-on: stats + -2 mlfqs-off: stats -2 Public testcase doesn't run faster with MLFQS -2 Group's own testcase doesn't run faster with MLFQS -4 Priorities don't change properly -- 2.30.2