diff options
Diffstat (limited to 'kernel')
| -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 |
12 files changed, 687 insertions, 8 deletions
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; +} + |