lock: release lab

23 files changed, 2003 insertions, 24 deletions

diff --git a/.gitignore b/.gitignore
index 07216f3..d036a8b 100644
--- a/.gitignore
+++ b/.gitignore
@@ -15,3 +15,13 @@ mkfs
 kernel/kernel
 user/usys.S
 .gdbinit
+*.zip
+xv6.out*
+.vagrant/
+submissions/
+ph
+barrier
+/lab-*.json
+.DS_Store
+*.dSYM
+*.pcap
diff --git a/Makefile b/Makefile
index 39a99d7..8e74f52 100644
--- a/Makefile
+++ b/Makefile
@@ -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);