summaryrefslogtreecommitdiff
path: root/kernel
diff options
context:
space:
mode:
Diffstat (limited to 'kernel')
-rw-r--r--kernel/defs.h49
-rw-r--r--kernel/file.h8
-rw-r--r--kernel/fs.c9
-rw-r--r--kernel/kcsan.c323
-rw-r--r--kernel/main.c12
-rw-r--r--kernel/pipe.c3
-rw-r--r--kernel/riscv.h11
-rw-r--r--kernel/spinlock.c111
-rw-r--r--kernel/spinlock.h4
-rw-r--r--kernel/sprintf.c91
-rw-r--r--kernel/start.c5
-rw-r--r--kernel/stats.c69
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;
+}
+