diff options
| -rw-r--r-- | .gitignore | 2 | ||||
| -rw-r--r-- | Makefile | 13 | ||||
| -rw-r--r-- | conf/lab.mk | 2 | ||||
| -rwxr-xr-x | grade-lab-lock | 62 | ||||
| -rw-r--r-- | kernel/defs.h | 4 | ||||
| -rw-r--r-- | kernel/fs.c | 9 | ||||
| -rw-r--r-- | kernel/kcsan.c | 323 | ||||
| -rw-r--r-- | kernel/pipe.c | 3 | ||||
| -rw-r--r-- | kernel/riscv.h | 3 | ||||
| -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 | 66 | ||||
| -rw-r--r-- | kernel/virtio_disk.c | 26 | ||||
| -rw-r--r-- | user/bcachetest.c | 318 | ||||
| -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 | 4 |
20 files changed, 1126 insertions, 19 deletions
@@ -11,7 +11,7 @@ entryother initcode initcode.out kernelmemfs -mkfs +mkfs/mkfs kernel/kernel user/usys.S .gdbinit @@ -53,13 +53,11 @@ OBJS += \ 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- @@ -92,7 +90,7 @@ 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) -DLAB_PGTBL +XCFLAGS += -DSOL_$(LABUPPER) -DLAB_$(LABUPPER) -DLAB_PGTBL -DLAB_NET endif CFLAGS += $(XCFLAGS) @@ -102,9 +100,7 @@ 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 @@ -252,11 +248,8 @@ UPROGS += \ endif - -ifeq ($(LAB),net) UPROGS += \ $U/_nettests -endif UEXTRA= UEXTRA += user/xargstest.sh @@ -297,10 +290,8 @@ 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) @@ -312,7 +303,6 @@ 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) @@ -321,7 +311,6 @@ server: ping: python3 ping.py $(FWDPORT) -endif ## ## FOR testing lab grading script diff --git a/conf/lab.mk b/conf/lab.mk index 26dcd75..1e7f18d 100644 --- a/conf/lab.mk +++ b/conf/lab.mk @@ -1 +1 @@ -LAB=net +LAB=lock diff --git a/grade-lab-lock b/grade-lab-lock new file mode 100755 index 0000000..fa90fef --- /dev/null +++ b/grade-lab-lock @@ -0,0 +1,62 @@ +#!/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(10, "bcachetest: test2", parent=test_bcachetest) +def test_bcachetest_test2(): + r.match('^test2 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/kernel/defs.h b/kernel/defs.h index 02226b5..541c97e 100644 --- a/kernel/defs.h +++ b/kernel/defs.h @@ -1,3 +1,7 @@ +#ifdef LAB_MMAP +typedef unsigned long size_t; +typedef long int off_t; +#endif struct buf; struct context; struct file; 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/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 7d6eb6e..af18972 100644 --- a/kernel/riscv.h +++ b/kernel/riscv.h @@ -355,6 +355,9 @@ typedef uint64 *pagetable_t; // 512 PTEs #define PTE_A (1L << 6) // riscv access bit #define PTE_C (1L << 8) // RSW low bit, use it to mark whether a page is COW + + + // shift a physical address to the right place for a PTE. #define PA2PTE(pa) ((((uint64)pa) >> 12) << 10) 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..b7a8e5f --- /dev/null +++ b/kernel/stats.c @@ -0,0 +1,66 @@ +#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_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/kernel/virtio_disk.c b/kernel/virtio_disk.c index ae6c164..dfca2bc 100644 --- a/kernel/virtio_disk.c +++ b/kernel/virtio_disk.c @@ -212,6 +212,28 @@ alloc3_desc(int *idx) return 0; } +#ifdef LAB_LOCK +// +// check that there are at most NBUF distinct +// struct buf's, which the lock lab requires. +// +static struct buf *xbufs[NBUF]; +static void +checkbuf(struct buf *b) +{ + for(int i = 0; i < NBUF; i++){ + if(xbufs[i] == b){ + return; + } + if(xbufs[i] == 0){ + xbufs[i] = b; + return; + } + } + panic("more than NBUF bufs"); +} +#endif + void virtio_disk_rw(struct buf *b, int write) { @@ -219,6 +241,10 @@ virtio_disk_rw(struct buf *b, int write) acquire(&disk.vdisk_lock); +#ifdef LAB_LOCK + checkbuf(b); +#endif + // the spec's Section 5.2 says that legacy block operations use // three descriptors: one for type/reserved/sector, one for the // data, one for a 1-byte status result. diff --git a/user/bcachetest.c b/user/bcachetest.c new file mode 100644 index 0000000..ccf7516 --- /dev/null +++ b/user/bcachetest.c @@ -0,0 +1,318 @@ +#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(); +void test2(); + +#define SZ 4096 +char buf[SZ]; + +int +main(int argc, char *argv[]) +{ + test0(); + test1(); + test2(); + 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"); +} + +// +// test concurrent creates. +// +void +test2() +{ + int nc = 4; + char file[16]; + + printf("start test2\n"); + + mkdir("d2"); + + file[0] = 'd'; + file[1] = '2'; + file[2] = '/'; + + // remove any stale existing files. + for(int i = 0; i < 50; i++){ + for(int ci = 0; ci < nc; ci++){ + file[3] = 'a' + ci; + file[4] = '0' + i; + file[5] = '\0'; + unlink(file); + } + } + + int pids[nc]; + for(int ci = 0; ci < nc; ci++){ + pids[ci] = fork(); + if(pids[ci] < 0){ + printf("test2: fork failed\n"); + exit(1); + } + if(pids[ci] == 0){ + char me = "abcdefghijklmnop"[ci]; + int pid = getpid(); + int nf = (ci == 0 ? 10 : 15); + + // create nf files. + for(int i = 0; i < nf; i++){ + file[3] = me; + file[4] = '0' + i; + file[5] = '\0'; + // printf("w %s\n", file); + int fd = open(file, O_CREATE | O_RDWR); + if(fd < 0){ + printf("test2: create %s failed\n", file); + exit(1); + } + int xx = (pid << 16) | i; + for(int nw = 0; nw < 2; nw++){ + // the sleep() increases the chance of simultaneous + // calls to bget(). + sleep(1); + if(write(fd, &xx, sizeof(xx)) <= 0){ + printf("test2: write %s failed\n", file); + exit(1); + } + } + close(fd); + } + + // read back the nf files. + for(int i = 0; i < nf; i++){ + file[3] = me; + file[4] = '0' + i; + file[5] = '\0'; + // printf("r %s\n", file); + int fd = open(file, O_RDWR); + if(fd < 0){ + printf("test2: open %s failed\n", file); + exit(1); + } + int xx = (pid << 16) | i; + for(int nr = 0; nr < 2; nr++){ + int z = 0; + sleep(1); + int n = read(fd, &z, sizeof(z)); + if(n != sizeof(z)){ + printf("test2: read %s returned %d, expected %d\n", file, n, sizeof(z)); + exit(1); + } + if(z != xx){ + printf("test2: file %s contained %d, not %d\n", file, z, xx); + exit(1); + } + } + close(fd); + } + + // delete the nf files. + for(int i = 0; i < nf; i++){ + file[3] = me; + file[4] = '0' + i; + file[5] = '\0'; + //printf("u %s\n", file); + if(unlink(file) != 0){ + printf("test2: unlink %s failed\n", file); + exit(1); + } + } + + exit(0); + } + } + + int ok = 1; + + for(int ci = 0; ci < nc; ci++){ + int st = 0; + int ret = wait(&st); + if(ret <= 0){ + printf("test2: wait() failed\n"); + ok = 0; + } + if(st != 0) + ok = 0; + } + + if(ok){ + printf("test2 OK\n"); + } else { + printf("test2 failed\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 34591fd..31453f5 100644 --- a/user/user.h +++ b/user/user.h @@ -1,3 +1,7 @@ +#ifdef LAB_MMAP +typedef unsigned long size_t; +typedef long int off_t; +#endif struct stat; struct sysinfo; |