diff options
| -rw-r--r-- | .gitignore | 10 | ||||
| -rw-r--r-- | Makefile | 227 | ||||
| -rw-r--r-- | conf/lab.mk | 1 | ||||
| -rwxr-xr-x | grade-lab-lock | 58 | ||||
| -rw-r--r-- | gradelib.py | 628 | ||||
| -rw-r--r-- | kernel/defs.h | 49 | ||||
| -rw-r--r-- | kernel/file.h | 8 | ||||
| -rw-r--r-- | kernel/fs.c | 9 | ||||
| -rw-r--r-- | kernel/kcsan.c | 323 | ||||
| -rw-r--r-- | kernel/main.c | 12 | ||||
| -rw-r--r-- | kernel/pipe.c | 3 | ||||
| -rw-r--r-- | kernel/riscv.h | 11 | ||||
| -rw-r--r-- | kernel/spinlock.c | 111 | ||||
| -rw-r--r-- | kernel/spinlock.h | 4 | ||||
| -rw-r--r-- | kernel/sprintf.c | 91 | ||||
| -rw-r--r-- | kernel/start.c | 5 | ||||
| -rw-r--r-- | kernel/stats.c | 69 | ||||
| -rw-r--r-- | user/bcachetest.c | 189 | ||||
| -rw-r--r-- | user/init.c | 1 | ||||
| -rw-r--r-- | user/kalloctest.c | 161 | ||||
| -rw-r--r-- | user/statistics.c | 24 | ||||
| -rw-r--r-- | user/stats.c | 24 | ||||
| -rw-r--r-- | user/user.h | 9 |
23 files changed, 2003 insertions, 24 deletions
@@ -15,3 +15,13 @@ mkfs kernel/kernel user/usys.S .gdbinit +*.zip +xv6.out* +.vagrant/ +submissions/ +ph +barrier +/lab-*.json +.DS_Store +*.dSYM +*.pcap @@ -1,14 +1,16 @@ + +# To compile and run with a lab solution, set the lab name in conf/lab.mk +# (e.g., LAB=util). Run make grade to test solution with the lab's +# grade script (e.g., grade-lab-util). + +-include conf/lab.mk + K=kernel U=user OBJS = \ $K/entry.o \ - $K/start.o \ - $K/console.o \ - $K/printf.o \ - $K/uart.o \ $K/kalloc.o \ - $K/spinlock.o \ $K/string.o \ $K/main.o \ $K/vm.o \ @@ -30,6 +32,34 @@ OBJS = \ $K/plic.o \ $K/virtio_disk.o +OBJS_KCSAN = \ + $K/start.o \ + $K/console.o \ + $K/printf.o \ + $K/uart.o \ + $K/spinlock.o + +ifdef KCSAN +OBJS_KCSAN += \ + $K/kcsan.o +endif + +ifeq ($(LAB),lock) +OBJS += \ + $K/stats.o\ + $K/sprintf.o +endif + + +ifeq ($(LAB),net) +OBJS += \ + $K/e1000.o \ + $K/net.o \ + $K/sysnet.o \ + $K/pci.o +endif + + # riscv64-unknown-elf- or riscv64-linux-gnu- # perhaps in /opt/riscv/bin #TOOLPREFIX = @@ -57,12 +87,28 @@ OBJCOPY = $(TOOLPREFIX)objcopy OBJDUMP = $(TOOLPREFIX)objdump CFLAGS = -Wall -Werror -O -fno-omit-frame-pointer -ggdb -gdwarf-2 + +ifdef LAB +LABUPPER = $(shell echo $(LAB) | tr a-z A-Z) +XCFLAGS += -DSOL_$(LABUPPER) -DLAB_$(LABUPPER) +endif + +CFLAGS += $(XCFLAGS) CFLAGS += -MD CFLAGS += -mcmodel=medany CFLAGS += -ffreestanding -fno-common -nostdlib -mno-relax CFLAGS += -I. CFLAGS += $(shell $(CC) -fno-stack-protector -E -x c /dev/null >/dev/null 2>&1 && echo -fno-stack-protector) +ifeq ($(LAB),net) +CFLAGS += -DNET_TESTS_PORT=$(SERVERPORT) +endif + +ifdef KCSAN +CFLAGS += -DKCSAN +KCSANFLAG = -fsanitize=thread -fno-inline +endif + # Disable PIE when possible (for Ubuntu 16.10 toolchain) ifneq ($(shell $(CC) -dumpspecs 2>/dev/null | grep -e '[^f]no-pie'),) CFLAGS += -fno-pie -no-pie @@ -73,11 +119,17 @@ endif LDFLAGS = -z max-page-size=4096 -$K/kernel: $(OBJS) $K/kernel.ld $U/initcode - $(LD) $(LDFLAGS) -T $K/kernel.ld -o $K/kernel $(OBJS) +$K/kernel: $(OBJS) $(OBJS_KCSAN) $K/kernel.ld $U/initcode + $(LD) $(LDFLAGS) -T $K/kernel.ld -o $K/kernel $(OBJS) $(OBJS_KCSAN) $(OBJDUMP) -S $K/kernel > $K/kernel.asm $(OBJDUMP) -t $K/kernel | sed '1,/SYMBOL TABLE/d; s/ .* / /; /^$$/d' > $K/kernel.sym +$(OBJS): EXTRAFLAG := $(KCSANFLAG) + +$K/%.o: $K/%.c + $(CC) $(CFLAGS) $(EXTRAFLAG) -c -o $@ $< + + $U/initcode: $U/initcode.S $(CC) $(CFLAGS) -march=rv64g -nostdinc -I. -Ikernel -c $U/initcode.S -o $U/initcode.o $(LD) $(LDFLAGS) -N -e start -Ttext 0 -o $U/initcode.out $U/initcode.o @@ -89,6 +141,10 @@ tags: $(OBJS) _init ULIB = $U/ulib.o $U/usys.o $U/printf.o $U/umalloc.o +ifeq ($(LAB),lock) +ULIB += $U/statistics.o +endif + _%: %.o $(ULIB) $(LD) $(LDFLAGS) -T $U/user.ld -o $@ $^ $(OBJDUMP) -S $@ > $*.asm @@ -107,7 +163,7 @@ $U/_forktest: $U/forktest.o $(ULIB) $(OBJDUMP) -S $U/_forktest > $U/forktest.asm mkfs/mkfs: mkfs/mkfs.c $K/fs.h $K/param.h - gcc -Werror -Wall -I. -o mkfs/mkfs mkfs/mkfs.c + gcc $(XCFLAGS) -Werror -Wall -I. -o mkfs/mkfs mkfs/mkfs.c # Prevent deletion of intermediate files, e.g. cat.o, after first build, so # that disk image changes after first build are persistent until clean. More @@ -133,18 +189,89 @@ UPROGS=\ $U/_wc\ $U/_zombie\ -fs.img: mkfs/mkfs README $(UPROGS) - mkfs/mkfs fs.img README $(UPROGS) + + + +ifeq ($(LAB),lock) +UPROGS += \ + $U/_stats +endif + +ifeq ($(LAB),traps) +UPROGS += \ + $U/_call\ + $U/_bttest +endif + +ifeq ($(LAB),lazy) +UPROGS += \ + $U/_lazytests +endif + +ifeq ($(LAB),cow) +UPROGS += \ + $U/_cowtest +endif + +ifeq ($(LAB),thread) +UPROGS += \ + $U/_uthread + +$U/uthread_switch.o : $U/uthread_switch.S + $(CC) $(CFLAGS) -c -o $U/uthread_switch.o $U/uthread_switch.S + +$U/_uthread: $U/uthread.o $U/uthread_switch.o $(ULIB) + $(LD) $(LDFLAGS) -N -e main -Ttext 0 -o $U/_uthread $U/uthread.o $U/uthread_switch.o $(ULIB) + $(OBJDUMP) -S $U/_uthread > $U/uthread.asm + +ph: notxv6/ph.c + gcc -o ph -g -O2 $(XCFLAGS) notxv6/ph.c -pthread + +barrier: notxv6/barrier.c + gcc -o barrier -g -O2 $(XCFLAGS) notxv6/barrier.c -pthread +endif + +ifeq ($(LAB),pgtbl) +UPROGS += \ + $U/_pgtbltest +endif + +ifeq ($(LAB),lock) +UPROGS += \ + $U/_kalloctest\ + $U/_bcachetest +endif + +ifeq ($(LAB),fs) +UPROGS += \ + $U/_bigfile +endif + + + +ifeq ($(LAB),net) +UPROGS += \ + $U/_nettests +endif + +UEXTRA= +ifeq ($(LAB),util) + UEXTRA += user/xargstest.sh +endif + + +fs.img: mkfs/mkfs README $(UEXTRA) $(UPROGS) + mkfs/mkfs fs.img README $(UEXTRA) $(UPROGS) -include kernel/*.d user/*.d -clean: - rm -f *.tex *.dvi *.idx *.aux *.log *.ind *.ilg \ +clean: + rm -rf *.tex *.dvi *.idx *.aux *.log *.ind *.ilg *.dSYM *.zip *.pcap \ */*.o */*.d */*.asm */*.sym \ - $U/initcode $U/initcode.out $K/kernel fs.img \ - mkfs/mkfs .gdbinit \ - $U/usys.S \ - $(UPROGS) + $U/initcode $U/initcode.out $U/usys.S $U/_* \ + $K/kernel \ + mkfs/mkfs fs.img .gdbinit __pycache__ xv6.out* \ + ph barrier # try to generate a unique GDB port GDBPORT = $(shell expr `id -u` % 5000 + 25000) @@ -155,12 +282,22 @@ QEMUGDB = $(shell if $(QEMU) -help | grep -q '^-gdb'; \ ifndef CPUS CPUS := 3 endif +ifeq ($(LAB),fs) +CPUS := 1 +endif + +FWDPORT = $(shell expr `id -u` % 5000 + 25999) QEMUOPTS = -machine virt -bios none -kernel $K/kernel -m 128M -smp $(CPUS) -nographic QEMUOPTS += -global virtio-mmio.force-legacy=false QEMUOPTS += -drive file=fs.img,if=none,format=raw,id=x0 QEMUOPTS += -device virtio-blk-device,drive=x0,bus=virtio-mmio-bus.0 +ifeq ($(LAB),net) +QEMUOPTS += -netdev user,id=net0,hostfwd=udp::$(FWDPORT)-:2000 -object filter-dump,id=net0,netdev=net0,file=packets.pcap +QEMUOPTS += -device e1000,netdev=net0,bus=pcie.0 +endif + qemu: $K/kernel fs.img $(QEMU) $(QEMUOPTS) @@ -171,3 +308,61 @@ qemu-gdb: $K/kernel .gdbinit fs.img @echo "*** Now run 'gdb' in another window." 1>&2 $(QEMU) $(QEMUOPTS) -S $(QEMUGDB) +ifeq ($(LAB),net) +# try to generate a unique port for the echo server +SERVERPORT = $(shell expr `id -u` % 5000 + 25099) + +server: + python3 server.py $(SERVERPORT) + +ping: + python3 ping.py $(FWDPORT) +endif + +## +## FOR testing lab grading script +## + +ifneq ($(V),@) +GRADEFLAGS += -v +endif + +print-gdbport: + @echo $(GDBPORT) + +grade: + @echo $(MAKE) clean + @$(MAKE) clean || \ + (echo "'make clean' failed. HINT: Do you have another running instance of xv6?" && exit 1) + ./grade-lab-$(LAB) $(GRADEFLAGS) + +## +## FOR submissions +## + +submit-check: + @if ! test -d .git; then \ + echo No .git directory, is this a git repository?; \ + false; \ + fi + @if test "$$(git symbolic-ref HEAD)" != refs/heads/$(LAB); then \ + git branch; \ + read -p "You are not on the $(LAB) branch. Hand-in the current branch? [y/N] " r; \ + test "$$r" = y; \ + fi + @if ! git diff-files --quiet || ! git diff-index --quiet --cached HEAD; then \ + git status -s; \ + echo; \ + echo "You have uncomitted changes. Please commit or stash them."; \ + false; \ + fi + @if test -n "`git status -s`"; then \ + git status -s; \ + read -p "Untracked files will not be handed in. Continue? [y/N] " r; \ + test "$$r" = y; \ + fi + +zipball: clean submit-check + git archive --verbose --format zip --output lab.zip HEAD + +.PHONY: zipball clean grade submit-check diff --git a/conf/lab.mk b/conf/lab.mk new file mode 100644 index 0000000..1e7f18d --- /dev/null +++ b/conf/lab.mk @@ -0,0 +1 @@ +LAB=lock diff --git a/grade-lab-lock b/grade-lab-lock new file mode 100755 index 0000000..770d676 --- /dev/null +++ b/grade-lab-lock @@ -0,0 +1,58 @@ +#!/usr/bin/env python3 + +import re +from gradelib import * + +r = Runner(save("xv6.out")) + +@test(0, "running kalloctest") +def test_kalloctest(): + r.run_qemu(shell_script([ + 'kalloctest' + ]), timeout=200) + +@test(10, "kalloctest: test1", parent=test_kalloctest) +def test_kalloctest_test1(): + r.match('^test1 OK$') + +@test(10, "kalloctest: test2", parent=test_kalloctest) +def test_kalloctest_test2(): + r.match('^test2 OK$') + +@test(10, "kalloctest: test3", parent=test_kalloctest) +def test_kalloctest_test3(): + r.match('^test3 OK$') + +@test(10, "kalloctest: sbrkmuch") +def test_sbrkmuch(): + r.run_qemu(shell_script([ + 'usertests sbrkmuch' + ]), timeout=90) + r.match('^ALL TESTS PASSED$') + +@test(0, "running bcachetest") +def test_bcachetest(): + r.run_qemu(shell_script([ + 'bcachetest' + ]), timeout=90) + +@test(10, "bcachetest: test0", parent=test_bcachetest) +def test_bcachetest_test0(): + r.match('^test0: OK$') + +@test(10, "bcachetest: test1", parent=test_bcachetest) +def test_bcachetest_test1(): + r.match('^test1 OK$') + +@test(19, "usertests") +def test_usertests(): + r.run_qemu(shell_script([ + 'usertests -q' + ]), timeout=300) + r.match('^ALL TESTS PASSED$') + +@test(1, "time") +def test_time(): + check_time() + +run_tests() diff --git a/gradelib.py b/gradelib.py new file mode 100644 index 0000000..f0d4934 --- /dev/null +++ b/gradelib.py @@ -0,0 +1,628 @@ +from __future__ import print_function + +import sys, os, re, time, socket, select, subprocess, errno, shutil, random, string, json +from subprocess import check_call, Popen +from optparse import OptionParser + +__all__ = [] + +################################################################## +# Test structure +# + +__all__ += ["test", "end_part", "run_tests", "get_current_test"] + +TESTS = [] +TOTAL = POSSIBLE = 0 +PART_TOTAL = PART_POSSIBLE = 0 +CURRENT_TEST = None +GRADES = {} + +def test(points, title=None, parent=None): + """Decorator for declaring test functions. If title is None, the + title of the test will be derived from the function name by + stripping the leading "test_" and replacing underscores with + spaces.""" + + def register_test(fn, title=title): + if not title: + assert fn.__name__.startswith("test_") + title = fn.__name__[5:].replace("_", " ") + if parent: + title = " " + title + + def run_test(): + global TOTAL, POSSIBLE, CURRENT_TEST, GRADES + + # Handle test dependencies + if run_test.complete: + return run_test.ok + run_test.complete = True + parent_failed = False + if parent: + parent_failed = not parent() + + # Run the test + fail = None + start = time.time() + CURRENT_TEST = run_test + sys.stdout.write("== Test %s == " % title) + if parent: + sys.stdout.write("\n") + sys.stdout.flush() + try: + if parent_failed: + raise AssertionError('Parent failed: %s' % parent.__name__) + fn() + except AssertionError as e: + fail = str(e) + + # Display and handle test result + POSSIBLE += points + if points: + print("%s: %s" % (title, \ + (color("red", "FAIL") if fail else color("green", "OK"))), end=' ') + if time.time() - start > 0.1: + print("(%.1fs)" % (time.time() - start), end=' ') + print() + if fail: + print(" %s" % fail.replace("\n", "\n ")) + else: + TOTAL += points + if points: + GRADES[title] = 0 if fail else points + + for callback in run_test.on_finish: + callback(fail) + CURRENT_TEST = None + + run_test.ok = not fail + return run_test.ok + + # Record test metadata on the test wrapper function + run_test.__name__ = fn.__name__ + run_test.title = title + run_test.complete = False + run_test.ok = False + run_test.on_finish = [] + TESTS.append(run_test) + return run_test + return register_test + +def end_part(name): + def show_part(): + global PART_TOTAL, PART_POSSIBLE + print("Part %s score: %d/%d" % \ + (name, TOTAL - PART_TOTAL, POSSIBLE - PART_POSSIBLE)) + print() + PART_TOTAL, PART_POSSIBLE = TOTAL, POSSIBLE + show_part.title = "" + TESTS.append(show_part) + +def write_results(): + global options + if not options.results: + return + try: + with open(options.results, "w") as f: + f.write(json.dumps(GRADES)) + except OSError as e: + print("Provided a bad results path. Error:", e) + +def run_tests(): + """Set up for testing and run the registered test functions.""" + + # Handle command line + global options + parser = OptionParser(usage="usage: %prog [-v] [filters...]") + parser.add_option("-v", "--verbose", action="store_true", + help="print commands") + parser.add_option("--color", choices=["never", "always", "auto"], + default="auto", help="never, always, or auto") + parser.add_option("--results", help="results file path") + (options, args) = parser.parse_args() + + # Start with a full build to catch build errors + make() + + # Clean the file system if there is one + reset_fs() + + # Run tests + limit = list(map(str.lower, args)) + try: + for test in TESTS: + if not limit or any(l in test.title.lower() for l in limit): + test() + if not limit: + write_results() + print("Score: %d/%d" % (TOTAL, POSSIBLE)) + except KeyboardInterrupt: + pass + if TOTAL < POSSIBLE: + sys.exit(1) + +def get_current_test(): + if not CURRENT_TEST: + raise RuntimeError("No test is running") + return CURRENT_TEST + +################################################################## +# Assertions +# + +__all__ += ["assert_equal", "assert_lines_match"] + +def assert_equal(got, expect, msg=""): + if got == expect: + return + if msg: + msg += "\n" + raise AssertionError("%sgot:\n %s\nexpected:\n %s" % + (msg, str(got).replace("\n", "\n "), + str(expect).replace("\n", "\n "))) + +def assert_lines_match(text, *regexps, **kw): + """Assert that all of regexps match some line in text. If a 'no' + keyword argument is given, it must be a list of regexps that must + *not* match any line in text.""" + + def assert_lines_match_kw(no=[]): + return no + no = assert_lines_match_kw(**kw) + + # Check text against regexps + lines = text.splitlines() + good = set() + bad = set() + for i, line in enumerate(lines): + if any(re.match(r, line) for r in regexps): + good.add(i) + regexps = [r for r in regexps if not re.match(r, line)] + if any(re.match(r, line) for r in no): + bad.add(i) + + if not regexps and not bad: + return + + # We failed; construct an informative failure message + show = set() + for lineno in good.union(bad): + for offset in range(-2, 3): + show.add(lineno + offset) + if regexps: + show.update(n for n in range(len(lines) - 5, len(lines))) + + msg = [] + last = -1 + for lineno in sorted(show): + if 0 <= lineno < len(lines): + if lineno != last + 1: + msg.append("...") + last = lineno + msg.append("%s %s" % (color("red", "BAD ") if lineno in bad else + color("green", "GOOD") if lineno in good + else " ", + lines[lineno])) + if last != len(lines) - 1: + msg.append("...") + if bad: + msg.append("unexpected lines in output") + for r in regexps: + msg.append(color("red", "MISSING") + " '%s'" % r) + raise AssertionError("\n".join(msg)) + +################################################################## +# Utilities +# + +__all__ += ["make", "maybe_unlink", "reset_fs", "color", "random_str", "check_time", "check_answers"] + +MAKE_TIMESTAMP = 0 + +def pre_make(): + """Delay prior to running make to ensure file mtimes change.""" + while int(time.time()) == MAKE_TIMESTAMP: + time.sleep(0.1) + +def post_make(): + """Record the time after make completes so that the next run of + make can be delayed if needed.""" + global MAKE_TIMESTAMP + MAKE_TIMESTAMP = int(time.time()) + +def make(*target): + pre_make() + if Popen(("make",) + target).wait(): + sys.exit(1) + post_make() + +def show_command(cmd): + from pipes import quote + print("\n$", " ".join(map(quote, cmd))) + +def maybe_unlink(*paths): + for path in paths: + try: + os.unlink(path) + except EnvironmentError as e: + if e.errno != errno.ENOENT: + raise + +COLORS = {"default": "\033[0m", "red": "\033[31m", "green": "\033[32m"} + +def color(name, text): + if options.color == "always" or (options.color == "auto" and os.isatty(1)): + return COLORS[name] + text + COLORS["default"] + return text + +def reset_fs(): + if os.path.exists("obj/fs/clean-fs.img"): + shutil.copyfile("obj/fs/clean-fs.img", "obj/fs/fs.img") + +def random_str(n=8): + letters = string.ascii_letters + string.digits + return ''.join(random.choice(letters) for _ in range(n)) + +def check_time(): + try: + print("") + with open('time.txt') as f: + d = f.read().strip() + if not re.match(r'^\d+$', d): + raise AssertionError('time.txt does not contain a single integer (number of hours spent on the lab)') + except IOError: + raise AssertionError('Cannot read time.txt') + +def check_answers(file, n=10): + try: + print("") + with open(file) as f: + d = f.read().strip() + if len(d) < n: + raise AssertionError('%s does not seem to contain enough text' % file) + except IOError: + raise AssertionError('Cannot read %s' % file) + + +################################################################## +# Controllers +# + +__all__ += ["QEMU", "GDBClient"] + +class QEMU(object): + _GDBPORT = None + + def __init__(self, *make_args): + # Check that QEMU is not currently running + try: + GDBClient(self.get_gdb_port(), timeout=0).close() + except socket.error: + pass + else: + print("""\ +GDB stub found on port %d. +QEMU appears to already be running. Please exit it if possible or use +'killall qemu' or 'killall qemu.real'.""" % self.get_gdb_port(), file=sys.stderr) + sys.exit(1) + + if options.verbose: + show_command(("make",) + make_args) + cmd = ("make", "-s", "--no-print-directory") + make_args + self.proc = Popen(cmd, stdout=subprocess.PIPE, + stderr=subprocess.STDOUT, + stdin=subprocess.PIPE) + # Accumulated output as a string + self.output = "" + # Accumulated output as a bytearray + self.outbytes = bytearray() + self.on_output = [] + + @staticmethod + def get_gdb_port(): + if QEMU._GDBPORT is None: + p = Popen(["make", "-s", "--no-print-directory", "print-gdbport"], + stdout=subprocess.PIPE) + (out, _) = p.communicate() + if p.returncode: + raise RuntimeError( + "Failed to get gdbport: make exited with %d" % + p.returncode) + QEMU._GDBPORT = int(out) + return QEMU._GDBPORT + + def fileno(self): + if self.proc: + return self.proc.stdout.fileno() + + def handle_read(self): + buf = os.read(self.proc.stdout.fileno(), 4096) + self.outbytes.extend(buf) + self.output = self.outbytes.decode("utf-8", "replace") + for callback in self.on_output: + callback(buf) + if buf == b"": + self.wait() + return + + def write(self, buf): + if isinstance(buf, str): + buf = buf.encode('utf-8') + self.proc.stdin.write(buf) + self.proc.stdin.flush() + + def wait(self): + if self.proc: + self.proc.wait() + self.proc = None + + def kill(self): + if self.proc: + self.proc.terminate() + +class GDBClient(object): + def __init__(self, port, timeout=15): + start = time.time() + while True: + self.sock = socket.socket() + try: + self.sock.settimeout(1) + self.sock.connect(("localhost", port)) + break + except socket.error: + if time.time() >= start + timeout: + raise + self.__buf = "" + + def fileno(self): + if self.sock: + return self.sock.fileno() + + def handle_read(self): + try: + data = self.sock.recv(4096).decode("ascii", "replace") + except socket.error: + data = "" + if data == "": + self.sock.close() + self.sock = None + return + self.__buf += data + + while True: + m = re.search(r"\$([^#]*)#[0-9a-zA-Z]{2}", self.__buf) + if not m: + break + pkt = m.group(1) + self.__buf = self.__buf[m.end():] + + if pkt.startswith("T05"): + # Breakpoint + raise TerminateTest + + def __send(self, cmd): + packet = "$%s#%02x" % (cmd, sum(map(ord, cmd)) % 256) + self.sock.sendall(packet.encode("ascii")) + + def __send_break(self): + self.sock.sendall(b"\x03") + + def close(self): + if self.sock: + self.sock.close() + self.sock = None + + def cont(self): + self.__send("c") + + def breakpoint(self, addr): + self.__send("Z1,%x,1" % addr) + + +################################################################## +# QEMU test runner +# + +__all__ += ["TerminateTest", "Runner"] + +class TerminateTest(Exception): + pass + +class Runner(): + def __init__(self, *default_monitors): + self.__default_monitors = default_monitors + + def run_qemu(self, *monitors, **kw): + """Run a QEMU-based test. monitors should functions that will + be called with this Runner instance once QEMU and GDB are + started. Typically, they should register callbacks that throw + TerminateTest when stop events occur. The target_base + argument gives the make target to run. The make_args argument + should be a list of additional arguments to pass to make. The + timeout argument bounds how long to run before returning.""" + + def run_qemu_kw(target_base="qemu", make_args=[], timeout=30): + return target_base, make_args, timeout + target_base, make_args, timeout = run_qemu_kw(**kw) + + # Start QEMU + pre_make() + self.qemu = QEMU(target_base + "-gdb", *make_args) + self.gdb = None + + try: + # Wait for QEMU to start or make to fail. This will set + # self.gdb if QEMU starts. + self.qemu.on_output = [self.__monitor_start] + self.__react([self.qemu], timeout=90) + self.qemu.on_output = [] + if self.gdb is None: + print("Failed to connect to QEMU; output:") + print(self.qemu.output) + sys.exit(1) + post_make() + + # QEMU and GDB are up + self.reactors = [self.qemu, self.gdb] + + # Start monitoring + for m in self.__default_monitors + monitors: + m(self) + + # Run and react + self.gdb.cont() + self.__react(self.reactors, timeout) + finally: + # Shutdown QEMU + try: + if self.gdb is None: + sys.exit(1) + self.qemu.kill() + self.__react(self.reactors, 5) + self.gdb.close() + self.qemu.wait() + except: + print("""\ +Failed to shutdown QEMU. You might need to 'killall qemu' or +'killall qemu.real'. +""") + raise + + def __monitor_start(self, output): + if b"\n" in output: + try: + self.gdb = GDBClient(self.qemu.get_gdb_port(), timeout=2) + raise TerminateTest + except socket.error: + pass + if not len(output): + raise TerminateTest + + def __react(self, reactors, timeout): + deadline = time.time() + timeout + try: + while True: + timeleft = deadline - time.time() + if timeleft < 0: + sys.stdout.write("Timeout! ") + sys.stdout.flush() + return + + rset = [r for r in reactors if r.fileno() is not None] + if not rset: + return + + rset, _, _ = select.select(rset, [], [], timeleft) + for reactor in rset: + reactor.handle_read() + except TerminateTest: + pass + + def user_test(self, binary, *monitors, **kw): + """Run a user test using the specified binary. Monitors and + keyword arguments are as for run_qemu. This runs on a disk + snapshot unless the keyword argument 'snapshot' is False.""" + + maybe_unlink("obj/kern/init.o", "obj/kern/kernel") + if kw.pop("snapshot", True): + kw.setdefault("make_args", []).append("QEMUEXTRA+=-snapshot") + self.run_qemu(target_base="run-%s" % binary, *monitors, **kw) + + def match(self, *args, **kwargs): + """Shortcut to call assert_lines_match on the most recent QEMU + output.""" + + assert_lines_match(self.qemu.output, *args, **kwargs) + +################################################################## +# Monitors +# + +__all__ += ["save", "stop_breakpoint", "call_on_line", "stop_on_line", "shell_script"] + +def save(path): + """Return a monitor that writes QEMU's output to path. If the + test fails, copy the output to path.test-name.""" + + def setup_save(runner): + f.seek(0) + f.truncate() + runner.qemu.on_output.append(f.write) + get_current_test().on_finish.append(save_on_finish) + + def save_on_finish(fail): + f.flush() + save_path = path + "." + get_current_test().__name__[5:] + if fail: + shutil.copyfile(path, save_path) + print(" QEMU output saved to %s" % save_path) + elif os.path.exists(save_path): + os.unlink(save_path) + print(" (Old %s failure log removed)" % save_path) + + f = open(path, "wb") + return setup_save + +def stop_breakpoint(addr): + """Returns a monitor that stops when addr is reached. addr may be + a number or the name of a symbol.""" + + def setup_breakpoint(runner): + if isinstance(addr, str): + addrs = [int(sym[:16], 16) for sym in open("kernel/kernel.sym") + if sym[17:].strip() == addr] + assert len(addrs), "Symbol %s not found" % addr + runner.gdb.breakpoint(addrs[0]) + else: + runner.gdb.breakpoint(addr) + return setup_breakpoint + +def call_on_line(regexp, callback): + """Returns a monitor that calls 'callback' when QEMU prints a line + matching 'regexp'.""" + + def setup_call_on_line(runner): + buf = bytearray() + def handle_output(output): + buf.extend(output) + while b"\n" in buf: + line, buf[:] = buf.split(b"\n", 1) + line = line.decode("utf-8", "replace") + if re.match(regexp, line): + callback(line) + runner.qemu.on_output.append(handle_output) + return setup_call_on_line + +def stop_on_line(regexp): + """Returns a monitor that stops when QEMU prints a line matching + 'regexp'.""" + + def stop(line): + raise TerminateTest + return call_on_line(regexp, stop) + +def shell_script(script, terminate_match=None): + """Returns a monitor that plays the script, and stops when the script is + done executing.""" + + def setup_call_on_line(runner): + class context: + n = 0 + buf = bytearray() + def handle_output(output): + context.buf.extend(output) + if terminate_match is not None: + if re.match(terminate_match, context.buf.decode('utf-8', 'replace')): + raise TerminateTest + if b'$ ' in context.buf: + context.buf = bytearray() + if context.n < len(script): + runner.qemu.write(script[context.n]) + runner.qemu.write('\n') + context.n += 1 + else: + if terminate_match is None: + raise TerminateTest + runner.qemu.on_output.append(handle_output) + return setup_call_on_line diff --git a/kernel/defs.h b/kernel/defs.h index a3c962b..c6fef8c 100644 --- a/kernel/defs.h +++ b/kernel/defs.h @@ -8,6 +8,10 @@ struct spinlock; struct sleeplock; struct stat; struct superblock; +#ifdef LAB_NET +struct mbuf; +struct sock; +#endif // bio.c void binit(void); @@ -117,6 +121,10 @@ void initlock(struct spinlock*, char*); void release(struct spinlock*); void push_off(void); void pop_off(void); +int atomic_read4(int *addr); +#ifdef LAB_LOCK +void freelock(struct spinlock*); +#endif // sleeplock.c void acquiresleep(struct sleeplock*); @@ -187,3 +195,44 @@ void virtio_disk_intr(void); // number of elements in fixed-size array #define NELEM(x) (sizeof(x)/sizeof((x)[0])) + + + +#ifdef LAB_PGTBL +// vmcopyin.c +int copyin_new(pagetable_t, char *, uint64, uint64); +int copyinstr_new(pagetable_t, char *, uint64, uint64); +#endif + +// stats.c +void statsinit(void); +void statsinc(void); + +// sprintf.c +int snprintf(char*, int, char*, ...); + +#ifdef KCSAN +void kcsaninit(); +#endif + +#ifdef LAB_NET +// pci.c +void pci_init(); + +// e1000.c +void e1000_init(uint32 *); +void e1000_intr(void); +int e1000_transmit(struct mbuf*); + +// net.c +void net_rx(struct mbuf*); +void net_tx_udp(struct mbuf*, uint32, uint16, uint16); + +// sysnet.c +void sockinit(void); +int sockalloc(struct file **, uint32, uint16, uint16); +void sockclose(struct sock *); +int sockread(struct sock *, uint64, int); +int sockwrite(struct sock *, uint64, int); +void sockrecvudp(struct mbuf*, uint32, uint16, uint16); +#endif diff --git a/kernel/file.h b/kernel/file.h index b076d1d..1eb5107 100644 --- a/kernel/file.h +++ b/kernel/file.h @@ -1,10 +1,17 @@ struct file { +#ifdef LAB_NET + enum { FD_NONE, FD_PIPE, FD_INODE, FD_DEVICE, FD_SOCK } type; +#else enum { FD_NONE, FD_PIPE, FD_INODE, FD_DEVICE } type; +#endif int ref; // reference count char readable; char writable; struct pipe *pipe; // FD_PIPE struct inode *ip; // FD_INODE and FD_DEVICE +#ifdef LAB_NET + struct sock *sock; // FD_SOCK +#endif uint off; // FD_INODE short major; // FD_DEVICE }; @@ -38,3 +45,4 @@ struct devsw { extern struct devsw devsw[]; #define CONSOLE 1 +#define STATS 2 diff --git a/kernel/fs.c b/kernel/fs.c index c6bab15..6c4079e 100644 --- a/kernel/fs.c +++ b/kernel/fs.c @@ -295,11 +295,11 @@ ilock(struct inode *ip) struct buf *bp; struct dinode *dip; - if(ip == 0 || ip->ref < 1) + if(ip == 0 || atomic_read4(&ip->ref) < 1) panic("ilock"); acquiresleep(&ip->lock); - + if(ip->valid == 0){ bp = bread(ip->dev, IBLOCK(ip->inum, sb)); dip = (struct dinode*)bp->data + ip->inum%IPB; @@ -320,7 +320,7 @@ ilock(struct inode *ip) void iunlock(struct inode *ip) { - if(ip == 0 || !holdingsleep(&ip->lock) || ip->ref < 1) + if(ip == 0 || !holdingsleep(&ip->lock) || atomic_read4(&ip->ref) < 1) panic("iunlock"); releasesleep(&ip->lock); @@ -416,7 +416,6 @@ bmap(struct inode *ip, uint bn) brelse(bp); return addr; } - panic("bmap: out of range"); } @@ -447,7 +446,7 @@ itrunc(struct inode *ip) bfree(ip->dev, ip->addrs[NDIRECT]); ip->addrs[NDIRECT] = 0; } - + ip->size = 0; iupdate(ip); } diff --git a/kernel/kcsan.c b/kernel/kcsan.c new file mode 100644 index 0000000..90861ba --- /dev/null +++ b/kernel/kcsan.c @@ -0,0 +1,323 @@ +#include "types.h" +#include "param.h" +#include "memlayout.h" +#include "spinlock.h" +#include "riscv.h" +#include "proc.h" +#include "defs.h" + +// +// Race detector using gcc's thread sanitizer. It delays all stores +// and loads and monitors if any other CPU is using the same address. +// If so, we have a race and print out the backtrace of the thread +// that raced and the thread that set the watchpoint. +// + +// +// To run with kcsan: +// make clean +// make KCSAN=1 qemu +// + +// The number of watch points. +#define NWATCH (NCPU) + +// The number of cycles to delay stores, whatever that means on qemu. +//#define DELAY_CYCLES 20000 +#define DELAY_CYCLES 200000 + +#define MAXTRACE 20 + +int +trace(uint64 *trace, int maxtrace) +{ + uint64 i = 0; + + push_off(); + + uint64 fp = r_fp(); + uint64 ra, low = PGROUNDDOWN(fp) + 16, high = PGROUNDUP(fp); + + while(!(fp & 7) && fp >= low && fp < high){ + ra = *(uint64*)(fp - 8); + fp = *(uint64*)(fp - 16); + trace[i++] = ra; + if(i >= maxtrace) + break; + } + + pop_off(); + + return i; +} + +struct watch { + uint64 addr; + int write; + int race; + uint64 trace[MAXTRACE]; + int tracesz; +}; + +struct { + struct spinlock lock; + struct watch points[NWATCH]; + int on; +} tsan; + +static struct watch* +wp_lookup(uint64 addr) +{ + for(struct watch *w = &tsan.points[0]; w < &tsan.points[NWATCH]; w++) { + if(w->addr == addr) { + return w; + } + } + return 0; +} + +static int +wp_install(uint64 addr, int write) +{ + for(struct watch *w = &tsan.points[0]; w < &tsan.points[NWATCH]; w++) { + if(w->addr == 0) { + w->addr = addr; + w->write = write; + w->tracesz = trace(w->trace, MAXTRACE); + return 1; + } + } + panic("wp_install"); + return 0; +} + +static void +wp_remove(uint64 addr) +{ + for(struct watch *w = &tsan.points[0]; w < &tsan.points[NWATCH]; w++) { + if(w->addr == addr) { + w->addr = 0; + w->tracesz = 0; + return; + } + } + panic("remove"); +} + +static void +printtrace(uint64 *t, int n) +{ + int i; + + for(i = 0; i < n; i++) { + printf("%p\n", t[i]); + } +} + +static void +race(char *s, struct watch *w) { + uint64 t[MAXTRACE]; + int n; + + n = trace(t, MAXTRACE); + printf("== race detected ==\n"); + printf("backtrace for racing %s\n", s); + printtrace(t, n); + printf("backtrace for watchpoint:\n"); + printtrace(w->trace, w->tracesz); + printf("==========\n"); +} + +// cycle counter +static inline uint64 +r_cycle() +{ + uint64 x; + asm volatile("rdcycle %0" : "=r" (x) ); + return x; +} + +static void delay(void) __attribute__((noinline)); +static void delay() { + uint64 stop = r_cycle() + DELAY_CYCLES; + uint64 c = r_cycle(); + while(c < stop) { + c = r_cycle(); + } +} + +static void +kcsan_read(uint64 addr, int sz) +{ + struct watch *w; + + acquire(&tsan.lock); + if((w = wp_lookup(addr)) != 0) { + if(w->write) { + race("load", w); + } + release(&tsan.lock); + return; + } + release(&tsan.lock); +} + +static void +kcsan_write(uint64 addr, int sz) +{ + struct watch *w; + + acquire(&tsan.lock); + if((w = wp_lookup(addr)) != 0) { + race("store", w); + release(&tsan.lock); + } + + // no watchpoint; try to install one + if(wp_install(addr, 1)) { + + release(&tsan.lock); + + // XXX maybe read value at addr before and after delay to catch + // races of unknown origins (e.g., device). + + delay(); + + acquire(&tsan.lock); + + wp_remove(addr); + } + release(&tsan.lock); +} + +// tsan.on will only have effect with "make KCSAN=1" +void +kcsaninit(void) +{ + initlock(&tsan.lock, "tsan"); + tsan.on = 1; + __sync_synchronize(); +} + +// +// Calls inserted by compiler into kernel binary, except for this file. +// + +void +__tsan_init(void) +{ +} + +void +__tsan_read1(uint64 addr) +{ + if(!tsan.on) + return; + // kcsan_read(addr, 1); +} + +void +__tsan_read2(uint64 addr) +{ + if(!tsan.on) + return; + kcsan_read(addr, 2); +} + +void +__tsan_read4(uint64 addr) +{ + if(!tsan.on) + return; + kcsan_read(addr, 4); +} + +void +__tsan_read8(uint64 addr) +{ + if(!tsan.on) + return; + kcsan_read(addr, 8); +} + +void +__tsan_read_range(uint64 addr, uint64 size) +{ + if(!tsan.on) + return; + kcsan_read(addr, size); +} + +void +__tsan_write1(uint64 addr) +{ + if(!tsan.on) + return; + // kcsan_write(addr, 1); +} + +void +__tsan_write2(uint64 addr) +{ + if(!tsan.on) + return; + kcsan_write(addr, 2); +} + +void +__tsan_write4(uint64 addr) +{ + if(!tsan.on) + return; + kcsan_write(addr, 4); +} + +void +__tsan_write8(uint64 addr) +{ + if(!tsan.on) + return; + kcsan_write(addr, 8); +} + +void +__tsan_write_range(uint64 addr, uint64 size) +{ + if(!tsan.on) + return; + kcsan_write(addr, size); +} + +void +__tsan_atomic_thread_fence(int order) +{ + __sync_synchronize(); +} + +uint32 +__tsan_atomic32_load(uint *ptr, uint *val, int order) +{ + uint t; + __atomic_load(ptr, &t, __ATOMIC_SEQ_CST); + return t; +} + +void +__tsan_atomic32_store(uint *ptr, uint val, int order) +{ + __atomic_store(ptr, &val, __ATOMIC_SEQ_CST); +} + +// We don't use this +void +__tsan_func_entry(uint64 pc) +{ +} + +// We don't use this +void +__tsan_func_exit(void) +{ +} + + diff --git a/kernel/main.c b/kernel/main.c index f0d3171..48c9555 100644 --- a/kernel/main.c +++ b/kernel/main.c @@ -12,6 +12,9 @@ main() { if(cpuid() == 0){ consoleinit(); +#if defined(LAB_LOCK) + statsinit(); +#endif printfinit(); printf("\n"); printf("xv6 kernel is booting\n"); @@ -28,11 +31,18 @@ main() iinit(); // inode table fileinit(); // file table virtio_disk_init(); // emulated hard disk +#ifdef LAB_NET + pci_init(); + sockinit(); +#endif userinit(); // first user process +#ifdef KCSAN + kcsaninit(); +#endif __sync_synchronize(); started = 1; } else { - while(started == 0) + while(atomic_read4((int *) &started) == 0) ; __sync_synchronize(); printf("hart %d starting\n", cpuid()); diff --git a/kernel/pipe.c b/kernel/pipe.c index f6b501a..41a9c5e 100644 --- a/kernel/pipe.c +++ b/kernel/pipe.c @@ -68,6 +68,9 @@ pipeclose(struct pipe *pi, int writable) } if(pi->readopen == 0 && pi->writeopen == 0){ release(&pi->lock); +#ifdef LAB_LOCK + freelock(&pi->lock); +#endif kfree((char*)pi); } else release(&pi->lock); diff --git a/kernel/riscv.h b/kernel/riscv.h index 20a01db..adc3e38 100644 --- a/kernel/riscv.h +++ b/kernel/riscv.h @@ -295,6 +295,14 @@ r_sp() return x; } +static inline uint64 +r_fp() +{ + uint64 x; + asm volatile("mv %0, s0" : "=r" (x) ); + return x; +} + // read and write tp, the thread pointer, which xv6 uses to hold // this core's hartid (core number), the index into cpus[]. static inline uint64 @@ -344,6 +352,9 @@ typedef uint64 *pagetable_t; // 512 PTEs #define PTE_X (1L << 3) #define PTE_U (1L << 4) // user can access + + + // shift a physical address to the right place for a PTE. #define PA2PTE(pa) ((((uint64)pa) >> 12) << 10) diff --git a/kernel/spinlock.c b/kernel/spinlock.c index 9840302..266a698 100644 --- a/kernel/spinlock.c +++ b/kernel/spinlock.c @@ -8,12 +8,52 @@ #include "proc.h" #include "defs.h" +#ifdef LAB_LOCK +#define NLOCK 500 + +static struct spinlock *locks[NLOCK]; +struct spinlock lock_locks; + +void +freelock(struct spinlock *lk) +{ + acquire(&lock_locks); + int i; + for (i = 0; i < NLOCK; i++) { + if(locks[i] == lk) { + locks[i] = 0; + break; + } + } + release(&lock_locks); +} + +static void +findslot(struct spinlock *lk) { + acquire(&lock_locks); + int i; + for (i = 0; i < NLOCK; i++) { + if(locks[i] == 0) { + locks[i] = lk; + release(&lock_locks); + return; + } + } + panic("findslot"); +} +#endif + void initlock(struct spinlock *lk, char *name) { lk->name = name; lk->locked = 0; lk->cpu = 0; +#ifdef LAB_LOCK + lk->nts = 0; + lk->n = 0; + findslot(lk); +#endif } // Acquire the lock. @@ -25,12 +65,21 @@ acquire(struct spinlock *lk) if(holding(lk)) panic("acquire"); +#ifdef LAB_LOCK + __sync_fetch_and_add(&(lk->n), 1); +#endif + // On RISC-V, sync_lock_test_and_set turns into an atomic swap: // a5 = 1 // s1 = &lk->locked // amoswap.w.aq a5, a5, (s1) - while(__sync_lock_test_and_set(&lk->locked, 1) != 0) - ; + while(__sync_lock_test_and_set(&lk->locked, 1) != 0) { +#ifdef LAB_LOCK + __sync_fetch_and_add(&(lk->nts), 1); +#else + ; +#endif + } // Tell the C compiler and the processor to not move loads or stores // past this point, to ensure that the critical section's memory @@ -108,3 +157,61 @@ pop_off(void) if(c->noff == 0 && c->intena) intr_on(); } + +// Read a shared 32-bit value without holding a lock +int +atomic_read4(int *addr) { + uint32 val; + __atomic_load(addr, &val, __ATOMIC_SEQ_CST); + return val; +} + +#ifdef LAB_LOCK +int +snprint_lock(char *buf, int sz, struct spinlock *lk) +{ + int n = 0; + if(lk->n > 0) { + n = snprintf(buf, sz, "lock: %s: #test-and-set %d #acquire() %d\n", + lk->name, lk->nts, lk->n); + } + return n; +} + +int +statslock(char *buf, int sz) { + int n; + int tot = 0; + + acquire(&lock_locks); + n = snprintf(buf, sz, "--- lock kmem/bcache stats\n"); + for(int i = 0; i < NLOCK; i++) { + if(locks[i] == 0) + break; + if(strncmp(locks[i]->name, "bcache", strlen("bcache")) == 0 || + strncmp(locks[i]->name, "kmem", strlen("kmem")) == 0) { + tot += locks[i]->nts; + n += snprint_lock(buf +n, sz-n, locks[i]); + } + } + + n += snprintf(buf+n, sz-n, "--- top 5 contended locks:\n"); + int last = 100000000; + // stupid way to compute top 5 contended locks + for(int t = 0; t < 5; t++) { + int top = 0; + for(int i = 0; i < NLOCK; i++) { + if(locks[i] == 0) + break; + if(locks[i]->nts > locks[top]->nts && locks[i]->nts < last) { + top = i; + } + } + n += snprint_lock(buf+n, sz-n, locks[top]); + last = locks[top]->nts; + } + n += snprintf(buf+n, sz-n, "tot= %d\n", tot); + release(&lock_locks); + return n; +} +#endif diff --git a/kernel/spinlock.h b/kernel/spinlock.h index 4392820..9bac216 100644 --- a/kernel/spinlock.h +++ b/kernel/spinlock.h @@ -5,5 +5,9 @@ struct spinlock { // For debugging: char *name; // Name of lock. struct cpu *cpu; // The cpu holding the lock. +#ifdef LAB_LOCK + int nts; + int n; +#endif }; diff --git a/kernel/sprintf.c b/kernel/sprintf.c new file mode 100644 index 0000000..050eb85 --- /dev/null +++ b/kernel/sprintf.c @@ -0,0 +1,91 @@ +#include <stdarg.h> + +#include "types.h" +#include "param.h" +#include "spinlock.h" +#include "sleeplock.h" +#include "fs.h" +#include "file.h" +#include "riscv.h" +#include "defs.h" + +static char digits[] = "0123456789abcdef"; + +static int +sputc(char *s, char c) +{ + *s = c; + return 1; +} + +static int +sprintint(char *s, int xx, int base, int sign) +{ + char buf[16]; + int i, n; + uint x; + + if(sign && (sign = xx < 0)) + x = -xx; + else + x = xx; + + i = 0; + do { + buf[i++] = digits[x % base]; + } while((x /= base) != 0); + + if(sign) + buf[i++] = '-'; + + n = 0; + while(--i >= 0) + n += sputc(s+n, buf[i]); + return n; +} + +int +snprintf(char *buf, int sz, char *fmt, ...) +{ + va_list ap; + int i, c; + int off = 0; + char *s; + + if (fmt == 0) + panic("null fmt"); + + va_start(ap, fmt); + for(i = 0; off < sz && (c = fmt[i] & 0xff) != 0; i++){ + if(c != '%'){ + off += sputc(buf+off, c); + continue; + } + c = fmt[++i] & 0xff; + if(c == 0) + break; + switch(c){ + case 'd': + off += sprintint(buf+off, va_arg(ap, int), 10, 1); + break; + case 'x': + off += sprintint(buf+off, va_arg(ap, int), 16, 1); + break; + case 's': + if((s = va_arg(ap, char*)) == 0) + s = "(null)"; + for(; *s && off < sz; s++) + off += sputc(buf+off, *s); + break; + case '%': + off += sputc(buf+off, '%'); + break; + default: + // Print unknown % sequence to draw attention. + off += sputc(buf+off, '%'); + off += sputc(buf+off, c); + break; + } + } + return off; +} diff --git a/kernel/start.c b/kernel/start.c index e16f18a..bf03bc0 100644 --- a/kernel/start.c +++ b/kernel/start.c @@ -38,6 +38,11 @@ start() w_mideleg(0xffff); w_sie(r_sie() | SIE_SEIE | SIE_STIE | SIE_SSIE); +#ifdef KCSAN + // allow supervisor to read cycle counter register + w_mcounteren(r_mcounteren()|0x3); +#endif + // configure Physical Memory Protection to give supervisor mode // access to all of physical memory. w_pmpaddr0(0x3fffffffffffffull); diff --git a/kernel/stats.c b/kernel/stats.c new file mode 100644 index 0000000..9659bb9 --- /dev/null +++ b/kernel/stats.c @@ -0,0 +1,69 @@ +#include <stdarg.h> + +#include "types.h" +#include "param.h" +#include "spinlock.h" +#include "sleeplock.h" +#include "fs.h" +#include "file.h" +#include "riscv.h" +#include "defs.h" + +#define BUFSZ 4096 +static struct { + struct spinlock lock; + char buf[BUFSZ]; + int sz; + int off; +} stats; + +int statscopyin(char*, int); +int statslock(char*, int); + +int +statswrite(int user_src, uint64 src, int n) +{ + return -1; +} + +int +statsread(int user_dst, uint64 dst, int n) +{ + int m; + + acquire(&stats.lock); + + if(stats.sz == 0) { +#ifdef LAB_PGTBL + stats.sz = statscopyin(stats.buf, BUFSZ); +#endif +#ifdef LAB_LOCK + stats.sz = statslock(stats.buf, BUFSZ); +#endif + } + m = stats.sz - stats.off; + + if (m > 0) { + if(m > n) + m = n; + if(either_copyout(user_dst, dst, stats.buf+stats.off, m) != -1) { + stats.off += m; + } + } else { + m = -1; + stats.sz = 0; + stats.off = 0; + } + release(&stats.lock); + return m; +} + +void +statsinit(void) +{ + initlock(&stats.lock, "stats"); + + devsw[STATS].read = statsread; + devsw[STATS].write = statswrite; +} + diff --git a/user/bcachetest.c b/user/bcachetest.c new file mode 100644 index 0000000..5dc46ef --- /dev/null +++ b/user/bcachetest.c @@ -0,0 +1,189 @@ +#include "kernel/fcntl.h" +#include "kernel/param.h" +#include "kernel/types.h" +#include "kernel/stat.h" +#include "kernel/riscv.h" +#include "kernel/fs.h" +#include "user/user.h" + +void test0(); +void test1(); + +#define SZ 4096 +char buf[SZ]; + +int +main(int argc, char *argv[]) +{ + test0(); + test1(); + exit(0); +} + +void +createfile(char *file, int nblock) +{ + int fd; + char buf[BSIZE]; + int i; + + fd = open(file, O_CREATE | O_RDWR); + if(fd < 0){ + printf("createfile %s failed\n", file); + exit(-1); + } + for(i = 0; i < nblock; i++) { + if(write(fd, buf, sizeof(buf)) != sizeof(buf)) { + printf("write %s failed\n", file); + exit(-1); + } + } + close(fd); +} + +void +readfile(char *file, int nbytes, int inc) +{ + char buf[BSIZE]; + int fd; + int i; + + if(inc > BSIZE) { + printf("readfile: inc too large\n"); + exit(-1); + } + if ((fd = open(file, O_RDONLY)) < 0) { + printf("readfile open %s failed\n", file); + exit(-1); + } + for (i = 0; i < nbytes; i += inc) { + if(read(fd, buf, inc) != inc) { + printf("read %s failed for block %d (%d)\n", file, i, nbytes); + exit(-1); + } + } + close(fd); +} + +int ntas(int print) +{ + int n; + char *c; + + if (statistics(buf, SZ) <= 0) { + fprintf(2, "ntas: no stats\n"); + } + c = strchr(buf, '='); + n = atoi(c+2); + if(print) + printf("%s", buf); + return n; +} + +// Test reading small files concurrently +void +test0() +{ + char file[2]; + char dir[2]; + enum { N = 10, NCHILD = 3 }; + int m, n; + + dir[0] = '0'; + dir[1] = '\0'; + file[0] = 'F'; + file[1] = '\0'; + + printf("start test0\n"); + for(int i = 0; i < NCHILD; i++){ + dir[0] = '0' + i; + mkdir(dir); + if (chdir(dir) < 0) { + printf("chdir failed\n"); + exit(1); + } + unlink(file); + createfile(file, N); + if (chdir("..") < 0) { + printf("chdir failed\n"); + exit(1); + } + } + m = ntas(0); + for(int i = 0; i < NCHILD; i++){ + dir[0] = '0' + i; + int pid = fork(); + if(pid < 0){ + printf("fork failed"); + exit(-1); + } + if(pid == 0){ + if (chdir(dir) < 0) { + printf("chdir failed\n"); + exit(1); + } + + readfile(file, N*BSIZE, 1); + + exit(0); + } + } + + for(int i = 0; i < NCHILD; i++){ + wait(0); + } + printf("test0 results:\n"); + n = ntas(1); + if (n-m < 500) + printf("test0: OK\n"); + else + printf("test0: FAIL\n"); +} + +// Test bcache evictions by reading a large file concurrently +void test1() +{ + char file[3]; + enum { N = 200, BIG=100, NCHILD=2 }; + + printf("start test1\n"); + file[0] = 'B'; + file[2] = '\0'; + for(int i = 0; i < NCHILD; i++){ + file[1] = '0' + i; + unlink(file); + if (i == 0) { + createfile(file, BIG); + } else { + createfile(file, 1); + } + } + for(int i = 0; i < NCHILD; i++){ + file[1] = '0' + i; + int pid = fork(); + if(pid < 0){ + printf("fork failed"); + exit(-1); + } + if(pid == 0){ + if (i==0) { + for (i = 0; i < N; i++) { + readfile(file, BIG*BSIZE, BSIZE); + } + unlink(file); + exit(0); + } else { + for (i = 0; i < N*20; i++) { + readfile(file, 1, BSIZE); + } + unlink(file); + } + exit(0); + } + } + + for(int i = 0; i < NCHILD; i++){ + wait(0); + } + printf("test1 OK\n"); +} diff --git a/user/init.c b/user/init.c index e0a5689..fc1c3db 100644 --- a/user/init.c +++ b/user/init.c @@ -18,6 +18,7 @@ main(void) if(open("console", O_RDWR) < 0){ mknod("console", CONSOLE, 0); + mknod("statistics", STATS, 0); open("console", O_RDWR); } dup(0); // stdout diff --git a/user/kalloctest.c b/user/kalloctest.c new file mode 100644 index 0000000..a82f1d5 --- /dev/null +++ b/user/kalloctest.c @@ -0,0 +1,161 @@ +#include "kernel/param.h" +#include "kernel/types.h" +#include "kernel/stat.h" +#include "kernel/riscv.h" +#include "kernel/memlayout.h" +#include "kernel/fcntl.h" +#include "user/user.h" + +#define NCHILD 2 +#define N 100000 +#define SZ 4096 + +void test1(void); +void test2(void); +void test3(void); +char buf[SZ]; + +int +main(int argc, char *argv[]) +{ + test1(); + test2(); + test3(); + exit(0); +} + +int ntas(int print) +{ + int n; + char *c; + + if (statistics(buf, SZ) <= 0) { + fprintf(2, "ntas: no stats\n"); + } + c = strchr(buf, '='); + n = atoi(c+2); + if(print) + printf("%s", buf); + return n; +} + +// Test concurrent kallocs and kfrees +void test1(void) +{ + void *a, *a1; + int n, m; + printf("start test1\n"); + m = ntas(0); + for(int i = 0; i < NCHILD; i++){ + int pid = fork(); + if(pid < 0){ + printf("fork failed"); + exit(-1); + } + if(pid == 0){ + for(i = 0; i < N; i++) { + a = sbrk(4096); + *(int *)(a+4) = 1; + a1 = sbrk(-4096); + if (a1 != a + 4096) { + printf("wrong sbrk\n"); + exit(-1); + } + } + exit(-1); + } + } + + for(int i = 0; i < NCHILD; i++){ + wait(0); + } + printf("test1 results:\n"); + n = ntas(1); + if(n-m < 10) + printf("test1 OK\n"); + else + printf("test1 FAIL\n"); +} + +// +// countfree() from usertests.c +// +int +countfree() +{ + uint64 sz0 = (uint64)sbrk(0); + int n = 0; + + while(1){ + uint64 a = (uint64) sbrk(4096); + if(a == 0xffffffffffffffff){ + break; + } + // modify the memory to make sure it's really allocated. + *(char *)(a + 4096 - 1) = 1; + n += 1; + } + sbrk(-((uint64)sbrk(0) - sz0)); + return n; +} + +// Test stealing +void test2() { + int free0 = countfree(); + int free1; + int n = (PHYSTOP-KERNBASE)/PGSIZE; + printf("start test2\n"); + printf("total free number of pages: %d (out of %d)\n", free0, n); + if(n - free0 > 1000) { + printf("test2 FAILED: cannot allocate enough memory"); + exit(-1); + } + for (int i = 0; i < 50; i++) { + free1 = countfree(); + if(i % 10 == 9) + printf("."); + if(free1 != free0) { + printf("test2 FAIL: losing pages\n"); + exit(-1); + } + } + printf("\ntest2 OK\n"); +} + +// Test concurrent kalloc/kfree and stealing +void test3(void) +{ + void *a, *a1; + printf("start test3\n"); + for(int i = 0; i < NCHILD; i++){ + int pid = fork(); + if(pid < 0){ + printf("fork failed"); + exit(-1); + } + if(pid == 0){ + if (i == 0) { + for(i = 0; i < N; i++) { + a = sbrk(4096); + *(int *)(a+4) = 1; + a1 = sbrk(-4096); + if (a1 != a + 4096) { + printf("wrong sbrk\n"); + exit(-1); + } + } + printf("child done %d\n", i); + exit(0); + } else { + countfree(); + printf("child done %d\n", i); + exit(0); + } + } + } + + for(int i = 0; i < NCHILD; i++){ + wait(0); + } + printf("test3 OK\n"); +} diff --git a/user/statistics.c b/user/statistics.c new file mode 100644 index 0000000..e22681a --- /dev/null +++ b/user/statistics.c @@ -0,0 +1,24 @@ +#include "kernel/types.h" +#include "kernel/stat.h" +#include "kernel/fcntl.h" +#include "user/user.h" + +int +statistics(void *buf, int sz) +{ + int fd, i, n; + + fd = open("statistics", O_RDONLY); + if(fd < 0) { + fprintf(2, "stats: open failed\n"); + exit(1); + } + for (i = 0; i < sz; ) { + if ((n = read(fd, buf+i, sz-i)) < 0) { + break; + } + i += n; + } + close(fd); + return i; +} diff --git a/user/stats.c b/user/stats.c new file mode 100644 index 0000000..f8c9138 --- /dev/null +++ b/user/stats.c @@ -0,0 +1,24 @@ +#include "kernel/types.h" +#include "kernel/stat.h" +#include "kernel/fcntl.h" +#include "user/user.h" + +#define SZ 4096 +char buf[SZ]; + +int +main(void) +{ + int i, n; + + while (1) { + n = statistics(buf, SZ); + for (i = 0; i < n; i++) { + write(1, buf+i, 1); + } + if (n != SZ) + break; + } + + exit(0); +} diff --git a/user/user.h b/user/user.h index 4d398d5..16cf173 100644 --- a/user/user.h +++ b/user/user.h @@ -22,6 +22,14 @@ int getpid(void); char* sbrk(int); int sleep(int); int uptime(void); +#ifdef LAB_NET +int connect(uint32, uint16, uint16); +#endif +#ifdef LAB_PGTBL +int pgaccess(void *base, int len, void *mask); +// usyscall region +int ugetpid(void); +#endif // ulib.c int stat(const char*, struct stat*); @@ -39,3 +47,4 @@ void free(void*); int atoi(const char*); int memcmp(const void *, const void *, uint); void *memcpy(void *, const void *, uint); +int statistics(void*, int); |