From e23c0d5dc156a42b3f5169cbac692cfc4fb6394d Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Sat, 20 Nov 2004 00:21:29 +0000 Subject: [PATCH] More VM tests. --- grading/vm/.cvsignore | 20 ++++ grading/vm/Make.progs | 27 +++++ grading/vm/Makefile | 23 +++++ grading/vm/Makefile.posix | 40 ++++++++ grading/vm/child-linear.c | 3 +- grading/vm/child-mm-wrt.c | 32 ++++++ grading/vm/child-sort.c | 19 +--- grading/vm/lib/.cvsignore | 1 + grading/vm/lib/user/.cvsignore | 1 + grading/vm/mmap-close.c | 47 +++++++++ grading/vm/mmap-exit.c | 58 +++++++++++ grading/vm/mmap-overlap.c | 46 +++++++++ grading/vm/mmap-read.c | 50 +++++++++ grading/vm/mmap-shuffle.c | 94 +++++++++++++++++ grading/vm/mmap-twice.c | 45 +++++++++ grading/vm/mmap-unmap.c | 41 ++++++++ grading/vm/mmap-write.c | 55 ++++++++++ grading/vm/page-linear.exp | 1 - grading/vm/page-merge-par.c | 167 ++++++++++++++++++++++++++++++ grading/vm/page-merge-seq.c | 20 +--- grading/vm/page-parallel.c | 7 +- grading/vm/page-parallel.exp | 1 - grading/vm/page-shuffle.c | 69 +++++++++++++ grading/vm/page-shuffle.exp | 13 +++ grading/vm/posix-compat.c | 180 +++++++++++++++++++++++++++++++++ grading/vm/posix-compat.h | 83 +++++++++++++++ grading/vm/prep-disk | 47 +++++++++ grading/vm/pt-bad-addr.exp | 1 - grading/vm/pt-big-stk-obj.exp | 1 - grading/vm/pt-grow-stack.exp | 1 - grading/vm/pt-write-code.exp | 1 - grading/vm/sample.inc | 19 ++++ grading/vm/sample.txt | 17 ++++ 33 files changed, 1191 insertions(+), 39 deletions(-) create mode 100644 grading/vm/.cvsignore create mode 100644 grading/vm/Make.progs create mode 100644 grading/vm/Makefile create mode 100644 grading/vm/Makefile.posix create mode 100644 grading/vm/child-mm-wrt.c create mode 100644 grading/vm/lib/.cvsignore create mode 100644 grading/vm/lib/user/.cvsignore create mode 100644 grading/vm/mmap-close.c create mode 100644 grading/vm/mmap-exit.c create mode 100644 grading/vm/mmap-overlap.c create mode 100644 grading/vm/mmap-read.c create mode 100644 grading/vm/mmap-shuffle.c create mode 100644 grading/vm/mmap-twice.c create mode 100644 grading/vm/mmap-unmap.c create mode 100644 grading/vm/mmap-write.c create mode 100644 grading/vm/page-merge-par.c create mode 100644 grading/vm/page-shuffle.c create mode 100644 grading/vm/page-shuffle.exp create mode 100644 grading/vm/posix-compat.c create mode 100644 grading/vm/posix-compat.h create mode 100755 grading/vm/prep-disk create mode 100644 grading/vm/sample.inc create mode 100644 grading/vm/sample.txt diff --git a/grading/vm/.cvsignore b/grading/vm/.cvsignore new file mode 100644 index 0000000..a535667 --- /dev/null +++ b/grading/vm/.cvsignore @@ -0,0 +1,20 @@ +*.d +*.dsk +*.o +pt-grow-stack +pt-big-stk-obj +pt-bad-addr +pt-write-code +page-linear +page-parallel +page-merge-seq +page-merge-par +page-shuffle +mmap-read +mmap-close +mmap-unmap +mmap-overlap +mmap-twice +mmap-write +mmap-exit +mmap-shuffle diff --git a/grading/vm/Make.progs b/grading/vm/Make.progs new file mode 100644 index 0000000..7c18d95 --- /dev/null +++ b/grading/vm/Make.progs @@ -0,0 +1,27 @@ +TESTS = \ + pt-grow-stack pt-big-stk-obj pt-bad-addr pt-write-code \ + page-linear page-parallel page-merge-seq page-merge-par \ + page-shuffle mmap-read mmap-close mmap-unmap mmap-overlap \ + mmap-twice mmap-write mmap-exit mmap-shuffle +pt_grow_stack_SRC = pt-grow-stack.c arc4.c cksum.c +pt_big_stk_obj_SRC = pt-big-stk-obj.c arc4.c cksum.c +pt_bad_addr_SRC = pt-bad-addr.c +pt_write_code_SRC = pt-write-code.c +page_linear_SRC = page-linear.c arc4.c +page_parallel_SRC = page-parallel.c +page_merge_seq_SRC = page-merge-seq.c arc4.c +page_merge_par_SRC = page-merge-par.c arc4.c +page_shuffle_SRC = page-shuffle.c arc4.c cksum.c +mmap_read_SRC = mmap-read.c +mmap_close_SRC = mmap-close.c +mmap_unmap_SRC = mmap-unmap.c +mmap_overlap_SRC = mmap-overlap.c +mmap_twice_SRC = mmap-twice.c +mmap_write_SRC = mmap-write.c +mmap_exit_SRC = mmap-exit.c +mmap_shuffle_SRC = mmap-shuffle.c arc4.c cksum.c + +PROGS = $(TESTS) child-linear child-sort +child_linear_SRC = child-linear.c arc4.c +child_sort_SRC = child-sort.c + diff --git a/grading/vm/Makefile b/grading/vm/Makefile new file mode 100644 index 0000000..47f010e --- /dev/null +++ b/grading/vm/Makefile @@ -0,0 +1,23 @@ +include Make.progs + +SRCDIR = ../../src + +DISKS = $(patsubst %,%.dsk,$(TESTS)) + +disks: $(DISKS) + +mmap-close.dsk mmap-exit.dsk mmap-read.dsk mmap-unmap.dsk: sample.txt +mmap-overlap.dsk: zeros + +zeros: + dd if=/dev/zero of=$@ bs=1024 count=6 + +%.dsk: % + ./prep-disk --fs-disk=$@ $^ + +clean:: + rm -f $(DISKS) + +include $(SRCDIR)/Makefile.userprog + +CFLAGS += -Werror diff --git a/grading/vm/Makefile.posix b/grading/vm/Makefile.posix new file mode 100644 index 0000000..ce25626 --- /dev/null +++ b/grading/vm/Makefile.posix @@ -0,0 +1,40 @@ +SRCDIR = ../../src + +include $(SRCDIR)/Make.config +include Make.progs + +VPATH = $(SRCDIR) + +DEFINES = +CPPFLAGS = -I. +CFLAGS = -Wall -W -Wstrict-prototypes -Wmissing-prototypes + +PROGS_SRC = $(foreach prog,$(PROGS),$($(subst -,_,$(prog))_SRC)) +PROGS_OBJ = $(patsubst %.c,%.o,$(patsubst %.S,%.o,$(PROGS_SRC))) +PROGS_DEP = $(patsubst %.o,%.d,$(PROGS_OBJ)) + +all: $(PROGS) + +define TEMPLATE +$(2)_OBJ = $(patsubst %.c,%.o,$(patsubst %.S,%.o,$($(2)_SRC))) +$(1): $$($(2)_OBJ) posix-compat.o + $$(CC) $$(LDFLAGS) $$^ $$(LDLIBS) -o $$@ +endef + +$(foreach prog,$(PROGS),$(eval $(call TEMPLATE,$(prog),$(subst -,_,$(prog))))) + +$(PROGS): $(LIB) + +libc.a: $(LIB_OBJ) + rm -f $@ + ar r $@ $^ + ranlib $@ + +clean:: + rm -f $(PROGS) $(PROGS_OBJ) $(PROGS_DEP) + rm -f $(LIB_DEP) $(LIB_OBJ) lib/user/entry.[do] libc.a + +.PHONY: all clean + +-include $(LIB_DEP) $(PROGS_DEP) + diff --git a/grading/vm/child-linear.c b/grading/vm/child-linear.c index 1b22b49..e0cf2f1 100644 --- a/grading/vm/child-linear.c +++ b/grading/vm/child-linear.c @@ -1,4 +1,5 @@ #include +#include #include "arc4.h" #define SIZE (128 * 1024) @@ -17,7 +18,7 @@ main (int argc, char *argv[]) arc4_crypt (&arc4, buf, SIZE); /* Decrypt back to zeros. */ - arc4_init (&arc4, key, strlen (key))); + arc4_init (&arc4, key, strlen (key)); arc4_crypt (&arc4, buf, SIZE); /* Check that it's all zeros. */ diff --git a/grading/vm/child-mm-wrt.c b/grading/vm/child-mm-wrt.c new file mode 100644 index 0000000..9dbbee8 --- /dev/null +++ b/grading/vm/child-mm-wrt.c @@ -0,0 +1,32 @@ +#define ACTUAL ((void *) 0x10000000) + +int +main (void) +{ + int fd; + + printf ("(mmap-write) begin\n"); + + /* Write file via mmap. */ + if (!create ("sample.txt", strlen (sample))) + { + printf ("(mmap-write) create() failed\n"); + return 1; + } + + fd = open ("sample.txt"); + if (fd < 0) + { + printf ("(mmap-write) open() failed\n"); + return 1; + } + + if (!mmap (fd, ACTUAL, strlen (sample))) + { + printf ("(mmap-write) mmap() failed\n"); + return 1; + } + memcpy (ACTUAL, sample, strlen (sample)); + return 234; +} + diff --git a/grading/vm/child-sort.c b/grading/vm/child-sort.c index 5ce8da4..56161b9 100644 --- a/grading/vm/child-sort.c +++ b/grading/vm/child-sort.c @@ -2,26 +2,21 @@ #ifdef PINTOS #include #else -#include -#include +#include "posix-compat.h" #endif unsigned char buf[65536]; size_t histogram[256]; int -main (void) +main (int argc __attribute__ ((unused)), char *argv[]) { int fd; unsigned char *p; size_t size; size_t i; - -#ifdef PINTOS - fd = open ("buffer"); -#else - fd = open ("buffer", O_RDWR); -#endif + + fd = open (argv[1]); if (fd < 0) { printf ("(child-sort) open() failed\n"); @@ -38,13 +33,9 @@ main (void) while (j-- > 0) *p++ = i; } -#ifdef PINTOS seek (fd, 0); -#else - lseek (fd, 0, SEEK_SET); -#endif write (fd, buf, size); close (fd); - return 0x123; + return 123; } diff --git a/grading/vm/lib/.cvsignore b/grading/vm/lib/.cvsignore new file mode 100644 index 0000000..a438335 --- /dev/null +++ b/grading/vm/lib/.cvsignore @@ -0,0 +1 @@ +*.d diff --git a/grading/vm/lib/user/.cvsignore b/grading/vm/lib/user/.cvsignore new file mode 100644 index 0000000..a438335 --- /dev/null +++ b/grading/vm/lib/user/.cvsignore @@ -0,0 +1 @@ +*.d diff --git a/grading/vm/mmap-close.c b/grading/vm/mmap-close.c new file mode 100644 index 0000000..54668b8 --- /dev/null +++ b/grading/vm/mmap-close.c @@ -0,0 +1,47 @@ +#include +#include +#include "arc4.h" +#include "sample.inc" +#ifdef PINTOS +#include +#else +#include "posix-compat.h" +#endif + +#define ACTUAL ((void *) 0x10000000) + +int +main (void) +{ + int fd; + + printf ("(mmap-close) begin\n"); + + fd = open ("sample.txt"); + if (fd < 0) + { + printf ("(mmap-close) open() failed\n"); + return 1; + } + + if (!mmap (fd, ACTUAL, strlen (sample))) + { + printf ("(mmap-close) mmap() failed\n"); + return 1; + } + + close (fd); + + if (memcmp (ACTUAL, sample, strlen (sample))) + { + printf ("(mmap-close) read of mmap'd file reported bad data\n"); + return 1; + } + + munmap (ACTUAL, strlen (sample)); + + /* Done. */ + printf ("(mmap-close) end\n"); + + return 0; +} diff --git a/grading/vm/mmap-exit.c b/grading/vm/mmap-exit.c new file mode 100644 index 0000000..87c2565 --- /dev/null +++ b/grading/vm/mmap-exit.c @@ -0,0 +1,58 @@ +#include +#include +#ifdef PINTOS +#include +#else +#include "posix-compat.h" +#endif +#include "sample.inc" + +#define ACTUAL ((void *) 0x10000000) + +int +main (void) +{ + pid_t child; + int code; + int fd; + char buf[1024]; + + printf ("(mmap-exit) begin\n"); + + /* Make child write file. */ + printf ("(mmap-exit) run child\n"); + child = exec ("child-mm-wrt"); + if (child == -1) + { + printf ("(mmap-exit) exec() failed\n"); + return 1; + } + code = join (child); + if (code != 234) + { + printf ("(mmap-exit) join() returned bad exit code: %d\n", code); + return 1; + } + printf ("(mmap-exit) child finished\n"); + + /* Read back via read(). */ + fd = open ("sample.txt"); + if (fd < 0) + { + printf ("(mmap-exit) open() failed\n"); + return 1; + } + + read (fd, buf, strlen (sample)); + if (memcmp (ACTUAL, sample, strlen (sample))) + { + printf ("(mmap-exit) read of mmap-written file reported bad data\n"); + return 1; + } + close (fd); + + /* Done. */ + printf ("(mmap-exit) end\n"); + + return 0; +} diff --git a/grading/vm/mmap-overlap.c b/grading/vm/mmap-overlap.c new file mode 100644 index 0000000..c4a06e6 --- /dev/null +++ b/grading/vm/mmap-overlap.c @@ -0,0 +1,46 @@ +#include +#include +#ifdef PINTOS +#include +#else +#include "posix-compat.h" +#endif +#include "sample.inc" + +int +main (void) +{ + char *start = (char *) 0x10000000; + size_t i; + int fd[2]; + + printf ("(mmap-overlap) begin\n"); + + for (i = 0; i < 2; i++) + { + fd[i] = open ("zeros"); + if (fd[i] < 0) + { + printf ("(mmap-overlap) open() failed\n"); + return 1; + } + if (!mmap (fd[i], start, 8192)) + { + if (i == 1) + return 0; + else + { + printf ("(mmap-overlap) mmap() failed\n"); + return 1; + } + } + start += 4096; + } + + printf ("(mmap-overlap) fail: mmap of overlapped blocks succeeded\n"); + + /* Done. */ + printf ("(mmap-overlap) end\n"); + + return 0; +} diff --git a/grading/vm/mmap-read.c b/grading/vm/mmap-read.c new file mode 100644 index 0000000..b763ddd --- /dev/null +++ b/grading/vm/mmap-read.c @@ -0,0 +1,50 @@ +#include +#include +#ifdef PINTOS +#include +#else +#include "posix-compat.h" +#endif +#include "sample.inc" + +#define ACTUAL ((void *) 0x10000000) + +int +main (void) +{ + int fd; + + printf ("(mmap-read) begin\n"); + + fd = open ("sample.txt"); + if (fd < 0) + { + printf ("(mmap-read) open() failed\n"); + return 1; + } + + if (!mmap (fd, ACTUAL, strlen (sample))) + { + printf ("(mmap-read) mmap() failed\n"); + return 1; + } + + if (memcmp (ACTUAL, sample, strlen (sample))) + { + printf ("(mmap-read) read of mmap'd file reported bad data\n"); + return 1; + } + + if (!munmap (ACTUAL, strlen (sample))) + { + printf ("(mmap-read) munmap() failed\n"); + return 1; + } + + close (fd); + + /* Done. */ + printf ("(mmap-read) end\n"); + + return 0; +} diff --git a/grading/vm/mmap-shuffle.c b/grading/vm/mmap-shuffle.c new file mode 100644 index 0000000..273bb4e --- /dev/null +++ b/grading/vm/mmap-shuffle.c @@ -0,0 +1,94 @@ +#include +#include +#ifdef PINTOS +#include +#else +#include "posix-compat.h" +#endif +#include "arc4.h" +#include "cksum.h" + +#define SIZE (63 * 1024) /* Max file size. */ +static char *buf = (char *) 0x10000000; + +static struct arc4 * +get_key (void) +{ + static struct arc4 arc4; + static bool inited = false; + if (!inited) + { + arc4_init (&arc4, "quux", 4); + inited = true; + } + return &arc4; +} + +static unsigned long +random_ulong (void) +{ + static unsigned long x; + arc4_crypt (get_key (), &x, sizeof x); + return x; +} + +static void +shuffle (void) +{ + size_t i; + + for (i = 0; i < SIZE; i++) + { + size_t j = i + random_ulong () % (SIZE - i); + char t = buf[i]; + buf[i] = buf[j]; + buf[j] = t; + } +} + +int +main (void) +{ + size_t i; + int fd; + + printf ("(mmap-shuffle) begin\n"); + + /* Create file, mmap. */ + if (!create ("buffer", SIZE)) + { + printf ("(mmap-shuffle) create() failed\n"); + return 1; + } + + fd = open ("buffer"); + if (fd < 0) + { + printf ("(mmap-shuffle) open() failed\n"); + return 1; + } + + if (!mmap (fd, buf, SIZE)) + { + printf ("(mmap-shuffle) mmap() failed\n"); + return 1; + } + + /* Initialize. */ + for (i = 0; i < SIZE; i++) + buf[i] = i * 257; + printf ("(mmap-shuffle) init: cksum=%lu\n", cksum (buf, SIZE)); + + /* Shuffle repeatedly. */ + for (i = 0; i < 10; i++) + { + shuffle (); + printf ("(mmap-shuffle) shuffle %d: cksum=%lu\n", + i, cksum (buf, SIZE)); + } + + /* Done. */ + printf ("(mmap-shuffle) end\n"); + + return 0; +} diff --git a/grading/vm/mmap-twice.c b/grading/vm/mmap-twice.c new file mode 100644 index 0000000..b3b06d9 --- /dev/null +++ b/grading/vm/mmap-twice.c @@ -0,0 +1,45 @@ +#include +#include +#ifdef PINTOS +#include +#else +#include "posix-compat.h" +#endif +#include "sample.inc" + +int +main (void) +{ + char *actual[2] = {(char *) 0x10000000, (char *) 0x20000000}; + size_t i; + int fd[2]; + + printf ("(mmap-twice) begin\n"); + + for (i = 0; i < 2; i++) + { + fd[i] = open ("sample"); + if (fd[i] < 0) + { + printf ("(mmap-twice) open() %zu failed\n", i); + return 1; + } + if (!mmap (fd[i], actual[i], 8192)) + { + printf ("(mmap-twice) mmap() %zu failed\n", i); + return 1; + } + } + + for (i = 0; i < 2; i++) + if (memcmp (actual[i], sample, strlen (sample))) + { + printf ("(mmap-twice) read of mmap'd file %zu reported bad data\n", + i); + return 1; + } + + printf ("(mmap-twice) end\n"); + + return 0; +} diff --git a/grading/vm/mmap-unmap.c b/grading/vm/mmap-unmap.c new file mode 100644 index 0000000..fcdff70 --- /dev/null +++ b/grading/vm/mmap-unmap.c @@ -0,0 +1,41 @@ +#include +#include +#ifdef PINTOS +#include +#else +#include "posix-compat.h" +#endif +#include "sample.inc" + +#define ACTUAL ((void *) 0x10000000) + +int +main (void) +{ + int fd; + + printf ("(mmap-unmap) begin\n"); + + fd = open ("sample.txt"); + if (fd < 0) + { + printf ("(mmap-unmap) open() failed\n"); + return 1; + } + + if (!mmap (fd, ACTUAL, strlen (sample))) + { + printf ("(mmap-unmap) mmap() failed\n"); + return 1; + } + + munmap (ACTUAL, strlen (sample)); + + printf ("(mmap-unmap) fail: unmapped memory is readable (%d)\n", + *(int *) ACTUAL); + + /* Done. */ + printf ("(mmap-unmap) end\n"); + + return 0; +} diff --git a/grading/vm/mmap-write.c b/grading/vm/mmap-write.c new file mode 100644 index 0000000..183c822 --- /dev/null +++ b/grading/vm/mmap-write.c @@ -0,0 +1,55 @@ +#include +#include +#ifdef PINTOS +#include +#else +#include "posix-compat.h" +#endif +#include "sample.inc" + +#define ACTUAL ((void *) 0x10000000) + +int +main (void) +{ + int fd; + char buf[1024]; + + printf ("(mmap-write) begin\n"); + + /* Write file via mmap. */ + if (!create ("sample.txt", strlen (sample))) + { + printf ("(mmap-write) create() failed\n"); + return 1; + } + + fd = open ("sample.txt"); + if (fd < 0) + { + printf ("(mmap-write) open() failed\n"); + return 1; + } + + if (!mmap (fd, ACTUAL, strlen (sample))) + { + printf ("(mmap-write) mmap() failed\n"); + return 1; + } + memcpy (ACTUAL, sample, strlen (sample)); + munmap (ACTUAL, strlen (sample)); + + /* Read back via read(). */ + read (fd, buf, strlen (sample)); + if (memcmp (ACTUAL, sample, strlen (sample))) + { + printf ("(mmap-write) read of mmap-written file reported bad data\n"); + return 1; + } + close (fd); + + /* Done. */ + printf ("(mmap-write) end\n"); + + return 0; +} diff --git a/grading/vm/page-linear.exp b/grading/vm/page-linear.exp index 291183b..4125d13 100644 --- a/grading/vm/page-linear.exp +++ b/grading/vm/page-linear.exp @@ -3,4 +3,3 @@ (page-linear) read/modify/write pass two (page-linear) read pass (page-linear) end -page-linear: exit(0) diff --git a/grading/vm/page-merge-par.c b/grading/vm/page-merge-par.c new file mode 100644 index 0000000..93ceb24 --- /dev/null +++ b/grading/vm/page-merge-par.c @@ -0,0 +1,167 @@ +#include +#include +#ifdef PINTOS +#include +#else +#include "posix-compat.h" +#endif +#include "arc4.h" + +#define CHUNK_SIZE (63 * 1024) /* Max file size. */ +#define CHUNK_CNT 8 /* Number of chunks. */ +#define DATA_SIZE (CHUNK_CNT * CHUNK_SIZE) /* Buffer size. */ + +unsigned char buf1[DATA_SIZE], buf2[DATA_SIZE]; +size_t histogram[256]; + +/* Initialize buf1 with random data, + then count the number of instances of each value within it. */ +static void +init (void) +{ + struct arc4 arc4; + size_t i; + + printf ("page-merge-par) init\n"); + + arc4_init (&arc4, "foobar", 6); + arc4_crypt (&arc4, buf1, sizeof buf1); + for (i = 0; i < sizeof buf1; i++) + histogram[buf1[i]]++; +} + +/* Sort each chunk of buf1 using a subprocess. */ +static void +sort (void) +{ + pid_t children[CHUNK_CNT]; + size_t i; + + for (i = 0; i < CHUNK_CNT; i++) + { + char fn[128]; + char cmd[128]; + int fd; + + printf ("(page-merge-par) sort chunk %zu\n", i); + + /* Write this chunk to a file. */ + snprintf (fn, sizeof fn, "buf%d", i); + create (fn, CHUNK_SIZE); + fd = open (fn); + if (fd < 0) + { + printf ("(page-merge-par) open() failed\n"); + exit (1); + } + write (fd, buf1 + CHUNK_SIZE * i, CHUNK_SIZE); + close (fd); + + /* Sort with subprocess. */ + snprintf (cmd, sizeof cmd, "child-sort %s", fn); + children[i] = exec (cmd); + if (children[i] == -1) + { + printf ("(page-merge-par) exec() failed\n"); + exit (1); + } + } + + for (i = 0; i < CHUNK_CNT; i++) + { + char fn[128]; + int fd; + + if (join (children[i]) != 123) + { + printf ("(page-merge-par) join(exec()) returned bad value\n"); + exit (1); + } + + /* Read chunk back from file. */ + snprintf (fn, sizeof fn, "buf%d", i); + fd = open (fn); + if (fd < 0) + { + printf ("(page-merge-par) open() failed\n"); + exit (1); + } + read (fd, buf1 + CHUNK_SIZE * i, CHUNK_SIZE); + close (fd); + } +} + +/* Merge the sorted chunks in buf1 into a fully sorted buf2. */ +static void +merge (void) +{ + unsigned char *mp[CHUNK_CNT]; + size_t mp_left; + unsigned char *op; + size_t i; + + printf ("(page-merge-par) merge\n"); + + /* Initialize merge pointers. */ + mp_left = CHUNK_CNT; + for (i = 0; i < CHUNK_CNT; i++) + mp[i] = buf1 + CHUNK_SIZE * i; + + /* Merge. */ + op = buf2; + while (mp_left > 0) + { + /* Find smallest value. */ + size_t min = 0; + for (i = 1; i < mp_left; i++) + if (*mp[i] < *mp[min]) + min = i; + + /* Append value to buf2. */ + *op++ = *mp[min]; + + /* Advance merge pointer. + Delete this chunk from the set if it's emptied. */ + if ((++mp[min] - buf1) % CHUNK_SIZE == 0) + mp[min] = mp[--mp_left]; + } +} + +static void +verify (void) +{ + size_t buf_idx; + size_t hist_idx; + + printf ("(page-merge-par) verify\n"); + + buf_idx = 0; + for (hist_idx = 0; hist_idx < sizeof histogram / sizeof *histogram; + hist_idx++) + { + while (histogram[hist_idx]-- > 0) + { + if (buf2[buf_idx] != hist_idx) + { + printf ("(page-merge-par) bad value %d in byte %zu\n", + buf2[buf_idx], buf_idx); + exit (1); + } + buf_idx++; + } + } + + printf ("(page-merge-par) success, buf_idx=%zu\n", buf_idx); +} + +int +main (void) +{ + printf ("(page-merge-par) begin\n"); + init (); + sort (); + merge (); + verify (); + printf ("(page-merge-par) end\n"); + return 0; +} diff --git a/grading/vm/page-merge-seq.c b/grading/vm/page-merge-seq.c index 3abe9e2..b451306 100644 --- a/grading/vm/page-merge-seq.c +++ b/grading/vm/page-merge-seq.c @@ -3,8 +3,7 @@ #ifdef PINTOS #include #else -#include -#include +#include "posix-compat.h" #endif #include "arc4.h" @@ -37,9 +36,7 @@ sort (void) { size_t i; -#ifdef PINTOS create ("buffer", CHUNK_SIZE); -#endif for (i = 0; i < CHUNK_CNT; i++) { int fd; @@ -47,11 +44,8 @@ sort (void) printf ("(page-merge-seq) sort chunk %zu\n", i); /* Write this chunk to a file. */ -#ifdef PINTOS fd = open ("buffer"); -#else - fd = open ("buffer", O_WRONLY | O_CREAT, 0660); -#endif + if (fd < 0) { printf ("(page-merge-seq) open() failed\n"); @@ -61,28 +55,20 @@ sort (void) close (fd); /* Sort with subprocess. */ -#ifdef PINTOS pid_t child = exec ("child-sort"); if (child == -1) { printf ("(page-merge-seq) exec() failed\n"); exit (1); } - if (join (child) != 0x123) + if (join (child) != 123) { printf ("(page-merge-seq) join(exec()) returned bad value\n"); exit (1); } -#else - system ("./child-sort"); -#endif /* Read chunk back from file. */ -#ifdef PINTOS fd = open ("buffer"); -#else - fd = open ("buffer", O_RDONLY); -#endif if (fd < 0) { printf ("(page-merge-seq) open() failed\n"); diff --git a/grading/vm/page-parallel.c b/grading/vm/page-parallel.c index c2d8eb3..f1c3ce0 100644 --- a/grading/vm/page-parallel.c +++ b/grading/vm/page-parallel.c @@ -1,4 +1,9 @@ +#include +#ifdef PINTOS #include +#else +#include "posix-compat.h" +#endif #define CHILD_CNT 3 @@ -15,7 +20,7 @@ main (void) children[i] = exec ("child-linear"); if (children[i] == -1) { - printf ("(page-parallel) exec() returned pid -1\n", children[i]); + printf ("(page-parallel) exec() returned pid -1\n"); return 1; } } diff --git a/grading/vm/page-parallel.exp b/grading/vm/page-parallel.exp index bc914e6..a3ac6c3 100644 --- a/grading/vm/page-parallel.exp +++ b/grading/vm/page-parallel.exp @@ -6,4 +6,3 @@ (page-parallel) join child 1 (page-parallel) join child 2 (page-parallel) end -page-parallel: exit(0) diff --git a/grading/vm/page-shuffle.c b/grading/vm/page-shuffle.c new file mode 100644 index 0000000..aadcb10 --- /dev/null +++ b/grading/vm/page-shuffle.c @@ -0,0 +1,69 @@ +#include +#include +#include "arc4.h" +#include "cksum.h" + +#define SIZE (128 * 1024) + +static char buf[SIZE]; + +static struct arc4 * +get_key (void) +{ + static struct arc4 arc4; + static bool inited = false; + if (!inited) + { + arc4_init (&arc4, "quux", 4); + inited = true; + } + return &arc4; +} + +static unsigned long +random_ulong (void) +{ + static unsigned long x; + arc4_crypt (get_key (), &x, sizeof x); + return x; +} + +static void +shuffle (void) +{ + size_t i; + + for (i = 0; i < sizeof buf; i++) + { + size_t j = i + random_ulong () % (sizeof buf - i); + char t = buf[i]; + buf[i] = buf[j]; + buf[j] = t; + } +} + +int +main (void) +{ + size_t i; + + printf ("(page-shuffle) begin\n"); + + /* Initialize. */ + for (i = 0; i < sizeof buf; i++) + buf[i] = i * 257; + printf ("(page-shuffle) init: cksum=%lu\n", cksum (buf, sizeof buf)); + + /* Shuffle repeatedly. */ + for (i = 0; i < 10; i++) + { + shuffle (); + printf ("(page-shuffle) shuffle %d: cksum=%lu\n", + i, cksum (buf, sizeof buf)); + } + + /* Done. */ + printf ("(page-shuffle) end\n"); + + return 0; +} diff --git a/grading/vm/page-shuffle.exp b/grading/vm/page-shuffle.exp new file mode 100644 index 0000000..5870dab --- /dev/null +++ b/grading/vm/page-shuffle.exp @@ -0,0 +1,13 @@ +(page-linear) begin +(page-linear) init: cksum=3115322833 +(page-linear) shuffle 0: cksum=1691062564 +(page-linear) shuffle 1: cksum=1973575879 +(page-linear) shuffle 2: cksum=1647619479 +(page-linear) shuffle 3: cksum=96566261 +(page-linear) shuffle 4: cksum=3885786467 +(page-linear) shuffle 5: cksum=3022003332 +(page-linear) shuffle 6: cksum=3614934266 +(page-linear) shuffle 7: cksum=2704001777 +(page-linear) shuffle 8: cksum=735775156 +(page-linear) shuffle 9: cksum=1864109763 +(page-linear) end diff --git a/grading/vm/posix-compat.c b/grading/vm/posix-compat.c new file mode 100644 index 0000000..dc5b5ab --- /dev/null +++ b/grading/vm/posix-compat.c @@ -0,0 +1,180 @@ +#include +#include +#include +#include +#include +#include +#include +#include "posix-compat.h" + +#undef halt +#undef exit +#undef exec +#undef join +#undef create +#undef remove +#undef open +#undef filesize +#undef read +#undef write +#undef seek +#undef tell +#undef close +#undef mmap +#undef munmap +#undef chdir +#undef mkdir +#undef lsdir + +void +pintos_halt (void) +{ + exit (-1); +} + +void +pintos_exit (int status) +{ + if (status < -127 || status > 255) + printf ("warning: non-POSIX exit code %d\n", status); + exit (status); +} + +pid_t +pintos_exec (const char *cmd_line) +{ + pid_t child = fork (); + if (child == -1) + return child; + else if (child == 0) + { + char copy[1024]; + char *args[128]; + char **argp; + + strcpy (copy, cmd_line); + + argp = args; + *argp = strtok (copy, " "); + while (*argp++ != NULL) + *argp = strtok (NULL, " "); + + execv (args[0], args); + abort (); + } + else + return child; +} + +int +pintos_join (pid_t child) +{ + int status = 0; + waitpid (child, &status, 0); + return WIFEXITED (status) ? WEXITSTATUS (status) : -1; +} + +bool +pintos_create (const char *file, unsigned initial_size) +{ + int fd = open (file, O_RDWR | O_CREAT | O_EXCL, 0666); + if (fd < 0) + return false; + ftruncate (fd, initial_size); + close (fd); + return true; +} + +bool +pintos_remove (const char *file) +{ + return unlink (file) == 0; +} + +int +pintos_open (const char *file) +{ + return open (file, O_RDWR); +} + +int +pintos_filesize (int fd) +{ + off_t old = lseek (fd, 0, SEEK_CUR); + off_t size = lseek (fd, 0, SEEK_END); + lseek (fd, old, SEEK_SET); + return size; +} + +int +pintos_read (int fd, void *buffer, unsigned length) +{ + return read (fd, buffer, length); +} + +int +pintos_write (int fd, const void *buffer, unsigned length) +{ + return write (fd, buffer, length); +} + +void +pintos_seek (int fd, unsigned position) +{ + lseek (fd, position, SEEK_SET); +} + + +unsigned +pintos_tell (int fd) +{ + return lseek (fd, 0, SEEK_CUR); +} + +void +pintos_close (int fd) +{ + close (fd); +} + +bool +pintos_mmap (int fd, void *addr, unsigned length) +{ + return mmap (addr, length, PROT_READ | PROT_WRITE, + MAP_SHARED | MAP_FIXED, fd, 0) == addr; +} + +bool +pintos_munmap (void *addr, unsigned length) +{ + return munmap (addr, length) == 0; +} + +bool +pintos_chdir (const char *dir) +{ + return chdir (dir) == 0; +} + +bool +pintos_mkdir (const char *dir) +{ + return mkdir (dir, 0777) == 0; +} + +void +pintos_lsdir (void) +{ + DIR *dir = opendir ("."); + if (dir != NULL) + { + struct dirent *de; + while ((de = readdir (dir)) != NULL) + { + if (!strcmp (de->d_name, ".") || !strcmp (de->d_name, "..")) + continue; + printf ("%s\n", de->d_name); + } + } + closedir (dir); +} diff --git a/grading/vm/posix-compat.h b/grading/vm/posix-compat.h new file mode 100644 index 0000000..df77e43 --- /dev/null +++ b/grading/vm/posix-compat.h @@ -0,0 +1,83 @@ +#ifndef POSIX_COMPAT_H +#define POSIX_COMPAT_H + +#include +#include +#include +#include + +#define NO_RETURN __attribute__ ((noreturn)) + +#undef halt +#define halt pintos_halt +void pintos_halt (void) NO_RETURN; + +#undef exit +#define exit pintos_exit +void pintos_exit (int status) NO_RETURN; + +#undef exec +#define exec pintos_exec +pid_t pintos_exec (const char *file); + +#undef join +#define join pintos_join +int pintos_join (pid_t); + +#undef create +#define create pintos_create +bool pintos_create (const char *file, unsigned initial_size); + +#undef remove +#define remove pintos_remove +bool pintos_remove (const char *file); + +#undef open +#define open pintos_open +int pintos_open (const char *file); + +#undef filesize +#define filesize pintos_filesize +int pintos_filesize (int fd); + +#undef read +#define read pintos_read +int pintos_read (int fd, void *buffer, unsigned length); + +#undef write +#define write pintos_write +int pintos_write (int fd, const void *buffer, unsigned length); + +#undef seek +#define seek pintos_seek +void pintos_seek (int fd, unsigned position); + +#undef tell +#define tell pintos_tell +unsigned pintos_tell (int fd); + +#undef close +#define close pintos_close +void pintos_close (int fd); + +#undef mmap +#define mmap pintos_mmap +bool pintos_mmap (int fd, void *addr, unsigned length); + +#undef munmap +#define munmap pintos_munmap +bool pintos_munmap (void *addr, unsigned length); + +#undef chdir +#define chdir pintos_chdir +bool pintos_chdir (const char *dir); + +#undef mkdir +#define mkdir pintos_mkdir +bool pintos_mkdir (const char *dir); + +#undef lsdir +#define lsdir pintos_lsdir +void pintos_lsdir (void); + +#endif /* posix-compat.h */ diff --git a/grading/vm/prep-disk b/grading/vm/prep-disk new file mode 100755 index 0000000..10afa8f --- /dev/null +++ b/grading/vm/prep-disk @@ -0,0 +1,47 @@ +#! /usr/bin/perl -w + +use strict; +use Getopt::Long; + +my ($pintos) = "pintos"; +my ($os_disk) = "../../src/userprog/build/os.dsk"; +my ($fs_disk); + +GetOptions ("os-disk=s" => \$os_disk, + "fs-disk=s" => \$fs_disk, + "help" => sub { usage (0) }) + or die "option parsing failed; use --help for help\n"; + +if (!defined $fs_disk) { + die "output disk name expected; use --help for help\n" + if @ARGV < 1; + $fs_disk = shift @ARGV; +} + +if (! -e $os_disk) { + print STDERR "$os_disk: stat: $!\n"; + print STDERR "perhaps you should `make' in ../../src/userprog?\n"; + exit 1; +} + +our ($formatted) = 0; + +unlink $fs_disk; +xsystem ("$pintos make-disk '$fs_disk' 2"); +while (@ARGV) { + put_file (shift (@ARGV)); +} + +sub put_file { + my ($fn) = @_; + my ($cmd) = "$pintos -v --os-disk='$os_disk' --fs-disk='$fs_disk' put"; + $cmd .= " -f", $formatted = 1 if !$formatted; + $cmd .= " '$fn'"; + xsystem ($cmd); +} + +sub xsystem { + my ($cmd) = @_; + print "$cmd\n"; + system ($cmd) == 0 || die "command failed\n"; +} diff --git a/grading/vm/pt-bad-addr.exp b/grading/vm/pt-bad-addr.exp index ac1492d..593835e 100644 --- a/grading/vm/pt-bad-addr.exp +++ b/grading/vm/pt-bad-addr.exp @@ -1,2 +1 @@ (pt-bad-addr) begin -pt-bad-addr: exit(-1) diff --git a/grading/vm/pt-big-stk-obj.exp b/grading/vm/pt-big-stk-obj.exp index 0919025..3b962e1 100644 --- a/grading/vm/pt-big-stk-obj.exp +++ b/grading/vm/pt-big-stk-obj.exp @@ -1,4 +1,3 @@ (pt-big-stk-obj) begin (pt-big-stk-obj) cksum: 3256410166 (pt-big-stk-obj) end -pt-big-stk-obj: exit(0) diff --git a/grading/vm/pt-grow-stack.exp b/grading/vm/pt-grow-stack.exp index 2caafcf..4ea0331 100644 --- a/grading/vm/pt-grow-stack.exp +++ b/grading/vm/pt-grow-stack.exp @@ -1,4 +1,3 @@ (pt-grow-stack) begin (pt-grow-stack) cksum: 3424492700 (pt-grow-stack) end -pt-grow-stack: exit(0) diff --git a/grading/vm/pt-write-code.exp b/grading/vm/pt-write-code.exp index 5844146..f048fc6 100644 --- a/grading/vm/pt-write-code.exp +++ b/grading/vm/pt-write-code.exp @@ -1,2 +1 @@ (pt-write-code) begin -pt-write-code: exit(-1) diff --git a/grading/vm/sample.inc b/grading/vm/sample.inc new file mode 100644 index 0000000..a60a139 --- /dev/null +++ b/grading/vm/sample.inc @@ -0,0 +1,19 @@ +char sample[] = { + "=== ALL USERS PLEASE NOTE ========================\n" + "\n" + "CAR and CDR now return extra values.\n" + "\n" + "The function CAR now returns two values. Since it has to go to the\n" + "trouble to figure out if the object is carcdr-able anyway, we figured\n" + "you might as well get both halves at once. For example, the following\n" + "code shows how to destructure a cons (SOME-CONS) into its two slots\n" + "(THE-CAR and THE-CDR):\n" + "\n" + " (MULTIPLE-VALUE-BIND (THE-CAR THE-CDR) (CAR SOME-CONS) ...)\n" + "\n" + "For symmetry with CAR, CDR returns a second value which is the CAR of\n" + "the object. In a related change, the functions MAKE-ARRAY and CONS\n" + "have been fixed so they don't allocate any storage except on the\n" + "stack. This should hopefully help people who don't like using the\n" + "garbage collector because it cold boots the machine so often.\n" +}; diff --git a/grading/vm/sample.txt b/grading/vm/sample.txt new file mode 100644 index 0000000..c446830 --- /dev/null +++ b/grading/vm/sample.txt @@ -0,0 +1,17 @@ +=== ALL USERS PLEASE NOTE ======================== + +CAR and CDR now return extra values. + +The function CAR now returns two values. Since it has to go to the +trouble to figure out if the object is carcdr-able anyway, we figured +you might as well get both halves at once. For example, the following +code shows how to destructure a cons (SOME-CONS) into its two slots +(THE-CAR and THE-CDR): + + (MULTIPLE-VALUE-BIND (THE-CAR THE-CDR) (CAR SOME-CONS) ...) + +For symmetry with CAR, CDR returns a second value which is the CAR of +the object. In a related change, the functions MAKE-ARRAY and CONS +have been fixed so they don't allocate any storage except on the +stack. This should hopefully help people who don't like using the +garbage collector because it cold boots the machine so often. -- 2.30.2