initial commit

23 files changed, 2824 insertions, 0 deletions

diff --git a/user/files/README b/user/files/README
new file mode 100644
index 0000000..325c8fa
--- /dev/null
+++ b/user/files/README
@@ -0,0 +1,5 @@
+It is possible to build non-executable files from 410user/files into the
+"RAM disk" by listing them in 410FILES in your config.mk.
+
+It is possible to build non-executable files from user/files into the
+"RAM disk" by listing them in STUDENTFILES in your config.mk.
diff --git a/user/inc/README.userinc b/user/inc/README.userinc
new file mode 100644
index 0000000..3f2d0b9
--- /dev/null
+++ b/user/inc/README.userinc
@@ -0,0 +1,2 @@
+This directory exists for you to store header files that are not
+private to your libraries; those can go in user/libfoo/.
diff --git a/user/inc/cond_type.h b/user/inc/cond_type.h
new file mode 100644
index 0000000..41e56f4
--- /dev/null
+++ b/user/inc/cond_type.h
@@ -0,0 +1,32 @@
+/**
+ * @file cond_type.h
+ * @author Hanjie Wu (hanjiew)
+ * @author Devang Acharya (devanga)
+ * @brief cv structure
+ * @date 2023-02-22
+ *
+ */
+#ifndef COND_TYPE_H
+#define COND_TYPE_H
+
+#include <mutex.h>
+
+/**
+ * @brief a node in condition vairable wait queue
+ */
+typedef struct cond_node_s {
+    int tid;
+    int signaled; /* is this thread signaled by othres */
+    struct cond_node_s* next;
+    struct cond_node_s* prev;
+} cond_node_t;
+
+/**
+ * @brief condition vairable
+ */
+typedef struct cond_s {
+    mutex_t lock;
+    cond_node_t* queue; /* waiters on this cv */
+} cond_t;
+
+#endif
diff --git a/user/inc/mutex_type.h b/user/inc/mutex_type.h
new file mode 100644
index 0000000..0d46d71
--- /dev/null
+++ b/user/inc/mutex_type.h
@@ -0,0 +1,38 @@
+/**
+ * @file mutex_type.h
+ * @author Hanjie Wu (hanjiew)
+ * @author Devang Acharya (devanga)
+ * @brief mutex structure
+ * @date 2023-02-22
+ *
+ */
+#ifndef MUTEX_TYPE_H
+#define MUTEX_TYPE_H
+
+#include <stdint.h>
+#include <stdlib.h>
+
+/* decleration of thread control block */
+struct tcb_s;
+
+/**
+ * @brief mutex structure
+ */
+typedef struct mutex_s {
+    uint32_t locked;      /* status of the mutex */
+    uint32_t w_lock;      /* lock for the waiter list below */
+    struct tcb_s* w_list; /* waiter list */
+} mutex_t;
+
+/**
+ * @brief static mutex initialization
+ */
+#define MUTEX_INIT \
+    { .locked = 0, .w_lock = 0, .w_list = NULL }
+
+/**
+ * @brief unlock the mutex and call vanish without using stack
+ */
+void mutex_unlock_vanish(mutex_t* mp);
+
+#endif
diff --git a/user/inc/rwlock_type.h b/user/inc/rwlock_type.h
new file mode 100644
index 0000000..ca5b7e8
--- /dev/null
+++ b/user/inc/rwlock_type.h
@@ -0,0 +1,41 @@
+/**
+ * @file rwlock_type.h
+ * @author Hanjie Wu (hanjiew)
+ * @author Devang Acharya (devanga)
+ * @brief rwlock structure
+ * @date 2023-02-22
+ *
+ */
+#ifndef RWLOCK_TYPE_H
+#define RWLOCK_TYPE_H
+
+#include <cond.h>
+#include <mutex.h>
+
+/**
+ * @brief indicates that the rwlock is unlocked
+ */
+#define RWLOCK_STATUS_UNLOCK 0
+
+/**
+ * @brief indicates that the rwlock is locked by at least 1 reader
+ */
+#define RWLOCK_STATUS_READ 1
+
+/**
+ * @brief indicates that the rwlock is locked by a writer
+ */
+#define RWLOCK_STATUS_WRITE 2
+
+/**
+ * @brief rwlock structure
+ */
+typedef struct rwlock_s {
+    mutex_t status_lock; /* mutex to protect other structures */
+    int num_reader;      /* number of readers holding this rwlock */
+    cond_t reader_cv;    /* cv to wait for read availability */
+    cond_t writer_cv;    /* cv to wait for write availability */
+    int status;          /* status of this rwlock */
+} rwlock_t;
+
+#endif
diff --git a/user/inc/sem_type.h b/user/inc/sem_type.h
new file mode 100644
index 0000000..c0bdf56
--- /dev/null
+++ b/user/inc/sem_type.h
@@ -0,0 +1,24 @@
+/**
+ * @file sem.h
+ * @author Hanjie Wu (hanjiew)
+ * @author Devang Acharya (devanga)
+ * @brief semaphore structure
+ * @date 2023-02-22
+ *
+ */
+#ifndef SEM_TYPE_H
+#define SEM_TYPE_H
+
+#include <cond.h>
+#include <mutex.h>
+
+/**
+ * @brief semaphore structure
+ */
+typedef struct sem_s {
+    int value;
+    mutex_t value_lock; /* mutex to protect the value */
+    cond_t value_cv;    /* cv to wait for value increment */
+} sem_t;
+
+#endif
diff --git a/user/inc/thr_internals.h b/user/inc/thr_internals.h
new file mode 100644
index 0000000..e0ad52e
--- /dev/null
+++ b/user/inc/thr_internals.h
@@ -0,0 +1,74 @@
+/**
+ * @file thr_internals.h
+ * @author Hanjie Wu (hanjiew)
+ * @author Devang Acharya (devanga)
+ * @brief tcb structure and management functions and excpetion stack
+ * @date 2023-02-22
+ *
+ */
+
+#ifndef THR_INTERNALS_H
+#define THR_INTERNALS_H
+
+#include <stdint.h>
+
+#include <cond.h>
+#include <mutex.h>
+#include <syscall.h>
+
+/**
+ * @brief stack for excpetion handler
+ */
+extern char ex_stack[];
+
+/**
+ * @brief pointer to the highest address of exception stack
+ */
+extern void* ex_stack_end;
+
+/**
+ * @brief thread control block structure
+ */
+typedef struct tcb_s {
+    int tid;            /* thread id */
+    uintptr_t stack_lo; /* low limit of stack */
+    uintptr_t stack_hi; /* high limit of stack */
+    int is_main;        /* is main thread */
+
+    int color;            /* rbtree color */
+    struct tcb_s* parent; /* rbtree parent */
+    struct tcb_s* left;   /* rbtree left node */
+    struct tcb_s* right;  /* rbtree right node */
+
+    struct tcb_s* mutex_next; /* queue for block on mutex */
+    struct tcb_s* mutex_prev; /* queue for block on mutex */
+    int mutex_resume; /* flag to show is other thread is going to resume this
+                         thread */
+
+    int waiter;       /* tid of other thread that called thr_join on it */
+    int exited;       /* is exited */
+    void* exit_value; /* return value */
+    cond_t wait_cv;   /* cv to wait for thread exit */
+} tcb_t;
+
+/**
+ * @brief tcb for main thread
+ */
+extern tcb_t main_tcb;
+
+/**
+ * @brief find tcb by thread id
+ */
+tcb_t* rb_find_tcb(int tid);
+/**
+ * @brief insert tcb into rbtree
+ */
+void rb_insert_tcb(tcb_t* tcb);
+/**
+ * @brief delete tcb from rbtree
+ */
+void rb_delete_tcb(tcb_t* tcb);
+
+#define PAGE_ALIGN_MASK ((uintptr_t) ~((uintptr_t)(PAGE_SIZE - 1)))
+
+#endif
diff --git a/user/libautostack/autostack.c b/user/libautostack/autostack.c
new file mode 100644
index 0000000..d0bea43
--- /dev/null
+++ b/user/libautostack/autostack.c
@@ -0,0 +1,71 @@
+/**
+ * @file autostack.c
+ * @author Hanjie Wu (hanjiew)
+ * @brief autostack implementation
+ * @date 2023-02-22
+ *
+ */
+
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#include <simics.h>
+#include <syscall.h>
+#include <thr_internals.h>
+#include <ureg.h>
+
+/**
+ * @brief test if the page fault is caused by page not present
+ */
+#define IS_PF_NP(error_code) (((error_code)&0x1) == 0)
+
+/**
+ * @brief a stack size which is enough for our swexn handlers
+ */
+#define EX_STACK_SIZE (1 << 14)
+
+char ex_stack[EX_STACK_SIZE];
+void* ex_stack_end = &ex_stack[sizeof(ex_stack)];
+/**
+ * @brief a stack size which is enough for common programs
+ */
+#define AUTOSYACK_SIZE (1 << 24)
+/**
+ * @brief size limit of autostack growth
+ */
+const static unsigned int stack_limit = AUTOSYACK_SIZE;
+
+/**
+ * @brief autostack swexn handler
+ */
+static void swexn_handler(void* arg, ureg_t* reg) {
+    /* check cause */
+    if (reg->cause == SWEXN_CAUSE_PAGEFAULT && IS_PF_NP(reg->error_code)) {
+        /* check stack limit */
+        if (reg->cr2 < main_tcb.stack_lo &&
+            reg->cr2 > main_tcb.stack_lo - stack_limit) {
+            uintptr_t aligned = reg->cr2 & PAGE_ALIGN_MASK;
+            if (new_pages((void*)aligned, (int)(main_tcb.stack_lo - aligned)) !=
+                0) {
+                task_vanish(-2);
+            }
+            main_tcb.stack_lo = aligned;
+            swexn(ex_stack_end, swexn_handler, NULL, reg);
+        }
+    }
+    task_vanish(-2);
+}
+
+/**
+ * @brief install autostack handler
+ */
+void install_autostack(void* stack_high, void* stack_low) {
+    /* use main_tcb to record stack limits */
+    main_tcb.stack_hi = (unsigned int)stack_high;
+    main_tcb.stack_lo = (unsigned int)stack_low;
+    main_tcb.tid = gettid();
+    main_tcb.is_main = 1;
+    rb_insert_tcb(&main_tcb);
+    swexn(ex_stack_end, swexn_handler, NULL, NULL);
+}
diff --git a/user/libsyscall/syscall.S b/user/libsyscall/syscall.S
new file mode 100644
index 0000000..d661cf8
--- /dev/null
+++ b/user/libsyscall/syscall.S
@@ -0,0 +1,218 @@
+#include <syscall_int.h>
+
+.global deschedule
+
+# int deschedule(int *flag);
+deschedule:
+    mov 0x4(%esp), %esi
+    int $DESCHEDULE_INT
+    ret
+
+.global exec
+
+# int exec(char *execname, char *argvec[]);
+exec:
+    mov 0x8(%esp), %esi
+    push %esi
+    mov 0x8(%esp), %esi
+    push %esi
+    mov %esp, %esi
+    int $EXEC_INT
+    add $0x8, %esp
+    ret
+
+.global fork
+
+# int fork(void);
+fork:
+    int $FORK_INT
+    ret
+
+.global getchar
+
+getchar:
+    int $GETCHAR_INT
+    ret
+
+.global get_cursor_pos
+
+get_cursor_pos:
+    mov 0x8(%esp), %esi
+    push %esi
+    mov 0x8(%esp), %esi
+    push %esi
+    mov %esp, %esi
+    int $GET_CURSOR_POS_INT
+    add $0x8, %esp
+    ret
+
+.global get_ticks
+
+get_ticks:
+    int $GET_TICKS_INT
+    ret
+
+.global gettid
+
+# int gettid(void);
+gettid:
+    int $GETTID_INT
+    ret
+
+.global halt
+
+halt:
+    int $HALT_INT
+    ret
+
+.global make_runnable
+
+make_runnable:
+    mov 0x4(%esp), %esi
+    int $MAKE_RUNNABLE_INT
+    ret
+
+.global misbehave
+
+misbehave:
+    mov 0x4(%esp), %esi
+    int $MISBEHAVE_INT
+    ret
+
+.global new_pages
+
+new_pages:
+    mov 0x8(%esp), %esi
+    push %esi
+    mov 0x8(%esp), %esi
+    push %esi
+    mov %esp, %esi
+    int $NEW_PAGES_INT
+    add $0x8, %esp
+    ret
+
+.global print
+
+print:
+    mov 0x8(%esp), %esi
+    push %esi
+    mov 0x8(%esp), %esi
+    push %esi
+    mov %esp, %esi
+    int $PRINT_INT
+    add $0x8, %esp
+    ret
+
+.global readfile
+
+readfile:
+    mov 0x10(%esp), %esi
+    push %esi
+    mov 0x10(%esp), %esi
+    push %esi
+    mov 0x10(%esp), %esi
+    push %esi
+    mov 0x10(%esp), %esi
+    push %esi
+    mov %esp, %esi
+    int $READFILE_INT
+    add $0x10, %esp
+    ret
+
+.global readline
+
+readline:
+    mov 0x8(%esp), %esi
+    push %esi
+    mov 0x8(%esp), %esi
+    push %esi
+    mov %esp, %esi
+    int $READLINE_INT
+    add $0x8, %esp
+    ret
+
+.global remove_pages
+
+remove_pages:
+    mov 0x4(%esp), %esi
+    int $REMOVE_PAGES_INT
+    ret
+
+.global set_cursor_pos
+
+set_cursor_pos:
+    mov 0x8(%esp), %esi
+    push %esi
+    mov 0x8(%esp), %esi
+    push %esi
+    mov %esp, %esi
+    int $SET_CURSOR_POS_INT
+    add $0x8, %esp
+    ret
+
+.global set_status
+
+# void set_status(int status);
+set_status:
+    mov 0x4(%esp), %esi
+    int $SET_STATUS_INT
+    ret
+
+.global set_term_color
+
+set_term_color:
+    mov 0x4(%esp), %esi
+    int $SET_TERM_COLOR_INT
+    ret
+
+.global sleep
+
+sleep:
+    mov 0x4(%esp), %esi
+    int $SLEEP_INT
+    ret
+
+.global swexn
+
+swexn:
+    mov 0x10(%esp), %esi
+    push %esi
+    mov 0x10(%esp), %esi
+    push %esi
+    mov 0x10(%esp), %esi
+    push %esi
+    mov 0x10(%esp), %esi
+    push %esi
+    mov %esp, %esi
+    int $SWEXN_INT
+    add $0x10, %esp
+    ret
+
+.global task_vanish
+
+# void task_vanish(int status) NORETURN;
+task_vanish:
+    mov 0x4(%esp), %esi
+    int $TASK_VANISH_INT
+
+.global vanish
+
+# void vanish(void) NORETURN;
+vanish:
+    int $VANISH_INT
+
+.global wait
+
+# int wait(int *status_ptr);
+wait:
+    mov 0x4(%esp), %esi
+    int $WAIT_INT
+    ret
+
+.global yield
+
+# int yield(int pid);
+yield:
+    mov 0x4(%esp), %esi
+    int $YIELD_INT
+    ret
diff --git a/user/libthread/cond.c b/user/libthread/cond.c
new file mode 100644
index 0000000..ccc7767
--- /dev/null
+++ b/user/libthread/cond.c
@@ -0,0 +1,108 @@
+/**
+ * @file cond.c
+ * @author Hanjie Wu (hanjiew)
+ * @author Devang Acharya (devanga)
+ * @brief
+ * @date 2023-02-22
+ *
+ */
+
+#include <assert.h>
+#include <cond.h>
+#include <stdlib.h>
+#include <syscall.h>
+
+/**
+ * @brief initialize the condition variable pointed by cv
+ *
+ * @param cv
+ * @return 0
+ */
+int cond_init(cond_t* cv) {
+    mutex_init(&cv->lock);
+    cv->queue = NULL;
+    return 0;
+}
+
+/**
+ * @brief destroy the condition variable pointed by cv.
+ *
+ * @param cv
+ */
+void cond_destroy(cond_t* cv) {
+    affirm(cv->queue == NULL);
+    mutex_destroy(&cv->lock);
+}
+
+/**
+ * @brief wait on a cv until signaled and lock mp
+ *
+ * @param cv
+ */
+void cond_wait(cond_t* cv, mutex_t* mp) {
+    cond_node_t self;
+    mutex_lock(&cv->lock);
+    self.tid = gettid();
+    self.signaled = 0;
+    if (cv->queue == NULL) { /* add self node to wait list */
+        cv->queue = &self;
+        self.next = self.prev = &self;
+    } else {
+        self.next = cv->queue;
+        self.prev = cv->queue->prev;
+        cv->queue->prev->next = &self;
+        cv->queue->prev = &self;
+    }
+    mutex_unlock(mp);
+    mutex_unlock(&cv->lock);
+    while (self.signaled != 1) {
+        deschedule(&self.signaled); /* will be set to 1 after other thread
+                                       signal the cv */
+    }
+    mutex_lock(mp);
+}
+
+/**
+ * @brief signal a cv and wake up one thread
+ *
+ * @param cv
+ */
+void cond_signal(cond_t* cv) {
+    mutex_lock(&cv->lock);
+    if (cv->queue != NULL) { /* remove a waiter from the list */
+        cond_node_t* p = cv->queue;
+        if (p->next == p) {
+            cv->queue = NULL;
+        } else {
+            cv->queue = p->next;
+            p->next->prev = p->prev;
+            p->prev->next = p->next;
+        }
+        int tid = p->tid;
+        p->signaled = 1;
+        make_runnable(tid);
+    }
+    mutex_unlock(&cv->lock);
+}
+
+/**
+ * @brief signal a cv and wake up all threads
+ *
+ * @param cv
+ */
+void cond_broadcast(cond_t* cv) {
+    mutex_lock(&cv->lock);
+    cond_node_t* p = cv->queue;
+    if (p != NULL) {
+        cond_node_t* end = p;
+        do {
+            cond_node_t* q = p->next;
+            int tid = p->tid;
+            p->signaled = 1;
+            make_runnable(tid);
+            p = q;
+        } while (p != end);
+        cv->queue = NULL;
+    }
+    mutex_unlock(&cv->lock);
+}
diff --git a/user/libthread/malloc.c b/user/libthread/malloc.c
new file mode 100644
index 0000000..8be6683
--- /dev/null
+++ b/user/libthread/malloc.c
@@ -0,0 +1,40 @@
+/**
+ * @file malloc.c
+ * @author Hanjie Wu (hanjiew)
+ * @author Devang Acharya (devanga)
+ * @brief Thread safe wrappers for malloc and family
+ * @date 2023-02-22
+ *
+ */
+
+#include <malloc.h>
+#include <mutex.h>
+
+mutex_t malloc_lock = MUTEX_INIT;
+
+void* malloc(size_t size) {
+    mutex_lock(&malloc_lock);
+    void* result = _malloc(size);
+    mutex_unlock(&malloc_lock);
+    return result;
+}
+
+void* calloc(size_t nelt, size_t eltsize) {
+    mutex_lock(&malloc_lock);
+    void* result = _calloc(nelt, eltsize);
+    mutex_unlock(&malloc_lock);
+    return result;
+}
+
+void* realloc(void* buf, size_t new_size) {
+    mutex_lock(&malloc_lock);
+    void* result = _realloc(buf, new_size);
+    mutex_unlock(&malloc_lock);
+    return result;
+}
+
+void free(void* buf) {
+    mutex_lock(&malloc_lock);
+    _free(buf);
+    mutex_unlock(&malloc_lock);
+}
diff --git a/user/libthread/mutex.c b/user/libthread/mutex.c
new file mode 100644
index 0000000..f78a6e8
--- /dev/null
+++ b/user/libthread/mutex.c
@@ -0,0 +1,35 @@
+/**
+ * @file mutex.c
+ * @author Hanjie Wu (hanjiew)
+ * @author Devang Acharya (devanga)
+ * @brief Mutex implementation
+ * @date 2023-02-22
+ *
+ */
+
+#include <stdint.h>
+
+#include <assert.h>
+#include <mutex.h>
+
+/**
+ * @brief initialize the mutex pointed by mp
+ *
+ * @param mp mutex
+ * @return 0
+ */
+int mutex_init(mutex_t* mp) {
+    mp->locked = 0;
+    mp->w_lock = 0;
+    mp->w_list = NULL;
+    return 0;
+}
+
+/**
+ * @brief deactivate the mutex pointed by mp
+ *
+ * @param mp mutex
+ */
+void mutex_destroy(mutex_t* mp) {
+    affirm(mp->locked == 0);
+}
diff --git a/user/libthread/mutex_lock.S b/user/libthread/mutex_lock.S
new file mode 100644
index 0000000..731ab59
--- /dev/null
+++ b/user/libthread/mutex_lock.S
@@ -0,0 +1,114 @@
+#include <syscall_int.h>
+
+// it is impossible to implement mutex_unlock_vanish without stack in c
+// so we implement all lock functions in assembly and mutex_unlock can
+// share function body with mutex_unlock_vanish
+
+.mutex_unlock_body:
+    xor %eax, %eax                 //
+    lock xchg %eax, (%ebp)         // mp->locked = 0;
+.mutex_unlock_try:                 // while(true) {
+    xor %eax, %eax                 //
+    mov $1, %edi                   //
+    lock cmpxchg %edi, 0x4(%ebp)   //    eax = compare_and_set(&mp->w_lock, 1);
+    test %eax, %eax                //    if(eax == 0) {break;}
+    jnz .mutex_unlock_try          // }
+    mov 0x8(%ebp), %edi            // edi = mp->w_list;
+    test %edi, %edi                //
+    jz .mutex_unlock_w_empty       // if(edi != NULL) {
+    mov $1, %edx                   //
+    mov %edx, 0x28(%edi)           //    edi->mutex_resume = 1;
+    mov (%edi), %esi               //
+    int $MAKE_RUNNABLE_INT         //    make_runnable(edi->tid);
+.mutex_unlock_w_empty:             // }
+    xor %eax, %eax                 //
+    lock xchg %eax, 0x4(%ebp)      // mp->w_lock = 0;
+    jmp *%ebx
+
+.global mutex_unlock
+.type mutex_unlock, %function
+mutex_unlock:
+    push %ebx
+    push %ebp
+    mov 0xc(%esp), %ebp            // ebp = mp
+    lea .mutex_unlock_done, %ebx   // ebx will be used by mutex_unlock_body as return address
+    jmp .mutex_unlock_body
+.mutex_unlock_done:
+    pop %ebp
+    pop %ebx
+    ret
+
+.global mutex_unlock_vanish
+.type mutex_unlock_vanish, %function
+mutex_unlock_vanish:
+    mov 0x4(%esp), %ebp
+    lea .mutex_unlock_do_vanish, %ebx
+    jmp .mutex_unlock_body
+.mutex_unlock_do_vanish:
+    int $VANISH_INT
+
+.global mutex_lock
+.type mutex_lock, %function
+mutex_lock:
+    push %ebx                      //
+    push %ebp                      //
+    call get_self_tcb              //
+    mov %eax, %ebx                 // ebx = get_self_tcb();
+    xor %eax, %eax                 //
+    mov %eax, 0x28(%ebx)           // ebx->mutex_resume = 0;
+    mov 0xc(%esp), %ebp            // ebp = mp;
+.mutex_lock_w_lock:                // while(true) {
+    xor %eax, %eax                 //
+    mov $1, %edi                   //
+    lock cmpxchg %edi, 0x4(%ebp)   //    eax = compare_and_set(&mp->w_lock, 1);
+    test %eax, %eax                //    if(eax == 0) {break;}
+    jnz .mutex_lock_w_lock         // }
+    mov 0x8(%ebp), %edi            // edi = mp->w_list;
+    test %edi, %edi                //
+    jz .mutex_lock_w_empty         // if(edi != NULL) {
+    mov %edi, 0x20(%ebx)           //    ebx->mutex_next = edi;
+    mov 0x24(%edi), %edx           //    edx = edi->mutex_prev;
+    mov %edx, 0x24(%ebx)           //    ebx->mutex_prev = edx;
+    mov %ebx, 0x20(%edx)           //    edx->mutex_next = ebx;
+    mov %ebx, 0x24(%edi)           //    edi->mutex_prev = ebx;
+    jmp .mutex_lock_w_done         // }
+.mutex_lock_w_empty:               // else {
+    mov %ebx, 0x8(%ebp)            //    mp->w_list = ebx;
+    mov %ebx, 0x20(%ebx)           //    ebx->mutex_next = ebx;
+    mov %ebx, 0x24(%ebx)           //    ebx->mutex_prev = ebx;
+.mutex_lock_w_done:                // }
+    lock xchg %eax, 0x4(%ebp)      // mp->w_lock = 0;
+.mutex_lock_try:                   //
+    xor %eax, %eax                 // while(true) {
+    mov $1, %edi                   //
+    lock cmpxchg %edi, (%ebp)      //    eax = compare_and_set(&mp->locked, 1);
+    test %eax, %eax                //
+    jz .mutex_lock_success         //    if(eax == 0) {break;}
+    lea 0x28(%ebx), %eax           //
+    push %eax                      //
+    call deschedule                //    deschedule(&ebx->mutex_resume);
+    add $0x4, %esp                 //
+    jmp .mutex_lock_try            // }
+.mutex_lock_success:               // while(true) {
+    xor %eax, %eax                 //
+    mov $1, %edi                   //
+    lock cmpxchg %edi, 0x4(%ebp)   //    eax = compare_and_set(&mp->w_lock, 1);
+    test %eax, %eax                //    if(eax == 0) {break;}
+    jnz .mutex_lock_success        // }
+    mov 0x20(%ebx), %edi           // edi = ebx->mutex_next;
+    mov 0x24(%ebx), %edx           // edx = ebx->mutex_prev;
+    cmp %edi, %ebx                 //
+    je .mutex_lock_w_last          // if(edi != ebx) {
+    mov %edx, 0x24(%edi)           //    edi->mutex_prev = edx;
+    mov %edi, 0x20(%edx)           //    edx->mutex_next = edi;
+    cmp %ebx, 0x8(%ebp)            //
+    jne .mutex_lock_w_end          //    if(ebx == mp->w_list)
+    mov %edi, 0x8(%ebp)            //       mp->w_list = edi;
+    jmp .mutex_lock_w_end          // }
+.mutex_lock_w_last:                // else {
+    mov %eax, 0x8(%ebp)            //    mp->w_list = NULL;
+.mutex_lock_w_end:                 // }
+    lock xchg %eax, 0x4(%ebp)      // mp->w_lock = 0;
+    pop %ebp
+    pop %ebx
+    ret
diff --git a/user/libthread/panic.c b/user/libthread/panic.c
new file mode 100644
index 0000000..7e9be35
--- /dev/null
+++ b/user/libthread/panic.c
@@ -0,0 +1,25 @@
+/**
+ * @file panic.c
+ * @author Hanjie Wu (hanjiew)
+ * @author Devang Acharya (devanga)
+ * @brief panic implementation
+ * @date 2023-02-22
+ *
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+
+/**
+ * @brief print msg and die
+ */
+void panic(const char* fmt, ...) {
+    va_list va;
+    va_start(va, fmt);
+
+    vprintf(fmt, va);
+
+    va_end(va);
+    
+    exit(-1);
+}
diff --git a/user/libthread/rb_tcb.c b/user/libthread/rb_tcb.c
new file mode 100644
index 0000000..40eac5b
--- /dev/null
+++ b/user/libthread/rb_tcb.c
@@ -0,0 +1,283 @@
+/**
+ * @file rb_tcb.c
+ * @author Hanjie Wu (hanjiew)
+ * @brief rbtree for tcbs
+ * @date 2023-02-22
+ *
+ */
+
+#include <stdbool.h>
+#include <stdlib.h>
+
+#include <thr_internals.h>
+
+/**
+ * @brief rbtree color
+ */
+#define RB_BLACK 0
+#define RB_RED 1
+
+/**
+ * @brief sentinel node
+ */
+static tcb_t rb_nil = {
+    .color = RB_BLACK,
+    .parent = &rb_nil,
+    .left = &rb_nil,
+    .right = &rb_nil,
+};
+
+/**
+ * @brief rbtree root
+ */
+static tcb_t* root = &rb_nil;
+
+/**
+ * @brief find a tcb by tid
+ */
+tcb_t* rb_find_tcb(int tid) {
+    tcb_t* p = root;
+    while (p != &rb_nil) {
+        if (tid == p->tid) {
+            return p;
+        }
+        p = (tid > p->tid) ? p->right : p->left;
+    }
+    return NULL;
+}
+
+/**
+ * @brief left rotate on a node
+ */
+static void rb_rotate_left(tcb_t** root, tcb_t* block) {
+    tcb_t* r = block->right;
+    block->right = r->left;
+    if (r->left != &rb_nil) {
+        r->left->parent = block;
+    }
+    r->parent = block->parent;
+    if (block->parent == &rb_nil) {
+        *root = r;
+    } else if (block == block->parent->left) {
+        block->parent->left = r;
+    } else {
+        block->parent->right = r;
+    }
+    r->left = block;
+    block->parent = r;
+}
+
+/**
+ * @brief right rotate on a node
+ */
+static void rb_rotate_right(tcb_t** root, tcb_t* block) {
+    tcb_t* l = block->left;
+    block->left = l->right;
+    if (l->right != &rb_nil) {
+        l->right->parent = block;
+    }
+    l->parent = block->parent;
+    if (block->parent == &rb_nil) {
+        *root = l;
+    } else if (block == block->parent->left) {
+        block->parent->left = l;
+    } else {
+        block->parent->right = l;
+    }
+    l->right = block;
+    block->parent = l;
+}
+
+/**
+ * @brief fixup after insertion
+ */
+static void rb_fixup(tcb_t** root, tcb_t* block) {
+    while (block->parent->color == RB_RED) {
+        tcb_t* grand = block->parent->parent;
+        if (block->parent == grand->left) {
+            tcb_t* uncle = grand->right;
+            if (uncle->color == RB_RED) {
+                block->parent->color = RB_BLACK;
+                uncle->color = RB_BLACK;
+                block->parent->parent->color = RB_RED;
+                block = block->parent->parent;
+            } else {
+                if (block == block->parent->right) {
+                    block = block->parent;
+                    rb_rotate_left(root, block);
+                }
+                block->parent->color = RB_BLACK;
+                grand->color = RB_RED;
+                rb_rotate_right(root, grand);
+            }
+        } else {
+            tcb_t* uncle = grand->left;
+            if (uncle->color == RB_RED) {
+                block->parent->color = RB_BLACK;
+                uncle->color = RB_BLACK;
+                block->parent->parent->color = RB_RED;
+                block = block->parent->parent;
+            } else {
+                if (block == block->parent->left) {
+                    block = block->parent;
+                    rb_rotate_right(root, block);
+                }
+                block->parent->color = RB_BLACK;
+                grand->color = RB_RED;
+                rb_rotate_left(root, grand);
+            }
+        }
+    }
+    (*root)->color = RB_BLACK;
+}
+
+/**
+ * @brief insert a node
+ */
+static void rb_insert(tcb_t** root, tcb_t* block) {
+    tcb_t *p = *root, *parent = &rb_nil;
+    while (p != &rb_nil) {
+        parent = p;
+        p = (block->tid > p->tid) ? p->right : p->left;
+    }
+    block->parent = parent;
+    if (parent == &rb_nil) {
+        *root = block;
+    } else if (block->tid > parent->tid) {
+        parent->right = block;
+    } else {
+        parent->left = block;
+    }
+    block->left = block->right = &rb_nil;
+    block->color = RB_RED;
+    rb_fixup(root, block);
+}
+
+/**
+ * @brief move node v to u
+ */
+static void rb_transplant(tcb_t** root, tcb_t* u, tcb_t* v) {
+    if (u->parent == &rb_nil) {
+        *root = v;
+    } else if (u == u->parent->left) {
+        u->parent->left = v;
+    } else {
+        u->parent->right = v;
+    }
+    v->parent = u->parent;
+}
+
+/**
+ * @brief find minimum node
+ */
+static tcb_t* rb_min(tcb_t* block) {
+    while (block->left != &rb_nil) {
+        block = block->left;
+    }
+    return block;
+}
+
+/**
+ * @brief fixup after deletion
+ */
+static void rb_delete_fixup(tcb_t** root, tcb_t* block) {
+    while (block != *root && block->color == RB_BLACK) {
+        if (block == block->parent->left) {
+            tcb_t* r = block->parent->right;
+            if (r->color == RB_RED) {
+                r->color = RB_BLACK;
+                block->parent->color = RB_RED;
+                rb_rotate_left(root, block->parent);
+                r = block->parent->right;
+            }
+            if (r->left->color == RB_BLACK && r->right->color == RB_BLACK) {
+                r->color = RB_RED;
+                block = block->parent;
+            } else {
+                if (r->right->color == RB_BLACK) {
+                    r->left->color = RB_BLACK;
+                    r->color = RB_RED;
+                    rb_rotate_right(root, r);
+                    r = block->parent->right;
+                }
+                r->color = block->parent->color;
+                block->parent->color = RB_BLACK;
+                r->right->color = RB_BLACK;
+                rb_rotate_left(root, block->parent);
+                block = *root;
+            }
+        } else {
+            tcb_t* l = block->parent->left;
+            if (l->color == RB_RED) {
+                l->color = RB_BLACK;
+                block->parent->color = RB_RED;
+                rb_rotate_right(root, block->parent);
+                l = block->parent->left;
+            }
+            if (l->right->color == RB_BLACK && l->left->color == RB_BLACK) {
+                l->color = RB_RED;
+                block = block->parent;
+            } else {
+                if (l->left->color == RB_BLACK) {
+                    l->right->color = RB_BLACK;
+                    l->color = RB_RED;
+                    rb_rotate_left(root, l);
+                    l = block->parent->left;
+                }
+                l->color = block->parent->color;
+                block->parent->color = RB_BLACK;
+                l->left->color = RB_BLACK;
+                rb_rotate_right(root, block->parent);
+                block = *root;
+            }
+        }
+    }
+    block->color = RB_BLACK;
+}
+
+/**
+ * @brief delete a node
+ */
+static void rb_delete(tcb_t** root, tcb_t* block) {
+    tcb_t *x, *y = block;
+    int orig_color = y->color;
+    if (block->left == &rb_nil) {
+        x = block->right;
+        rb_transplant(root, block, x);
+    } else if (block->right == &rb_nil) {
+        x = block->left;
+        rb_transplant(root, block, x);
+    } else {
+        y = rb_min(block->right);
+        orig_color = y->color;
+        x = y->right;
+        if (y->parent == block) {
+            x->parent = y;
+        } else {
+            rb_transplant(root, y, y->right);
+            y->right = block->right;
+            y->right->parent = y;
+        }
+        rb_transplant(root, block, y);
+        y->left = block->left;
+        y->left->parent = y;
+        y->color = block->color;
+    }
+    if (orig_color == RB_BLACK) {
+        rb_delete_fixup(root, x);
+    }
+}
+
+/**
+ * @brief add a tcb to rbtree
+ */
+void rb_insert_tcb(tcb_t* tcb) {
+    rb_insert(&root, tcb);
+}
+
+/**
+ * @brief remove a tcb from rbtree
+ */
+void rb_delete_tcb(tcb_t* tcb) {
+    rb_delete(&root, tcb);
+}
diff --git a/user/libthread/rwlock.c b/user/libthread/rwlock.c
new file mode 100644
index 0000000..4535d9b
--- /dev/null
+++ b/user/libthread/rwlock.c
@@ -0,0 +1,89 @@
+/**
+ * @file rwlock.c
+ * @author Hanjie Wu (hanjiew)
+ * @author Devang Acharya (devanga)
+ * @brief RW Lock implementation
+ * @date 2023-02-22
+ *
+ */
+
+#include <assert.h>
+#include <rwlock.h>
+
+/**
+ * @brief initialize the lock pointed to by rwlock
+ *
+ * @param rwlock
+ * @return int
+ */
+int rwlock_init(rwlock_t* rwlock) {
+    rwlock->status = RWLOCK_STATUS_UNLOCK;
+    rwlock->num_reader = 0;
+    mutex_init(&rwlock->status_lock);
+    cond_init(&rwlock->reader_cv);
+    cond_init(&rwlock->writer_cv);
+    return 0;
+}
+
+/**
+ * @brief lock a rwlock
+ */
+void rwlock_lock(rwlock_t* rwlock, int type) {
+    mutex_lock(&rwlock->status_lock);
+    if (type == RWLOCK_READ) {
+        while (rwlock->status == RWLOCK_STATUS_WRITE) {
+            /* wait for the write to release */
+            cond_wait(&rwlock->reader_cv, &rwlock->status_lock);
+        }
+        rwlock->status = RWLOCK_STATUS_READ;
+        rwlock->num_reader++;
+    } else {
+        while (rwlock->status != RWLOCK_STATUS_UNLOCK) {
+            affirm(rwlock->status == RWLOCK_STATUS_WRITE);
+            /* wait for readers to release */
+            cond_wait(&rwlock->writer_cv, &rwlock->status_lock);
+        }
+        rwlock->status = RWLOCK_STATUS_WRITE;
+    }
+    mutex_unlock(&rwlock->status_lock);
+}
+
+/**
+ * @brief unlock a rwlock
+ */
+void rwlock_unlock(rwlock_t* rwlock) {
+    mutex_lock(&rwlock->status_lock);
+    if (rwlock->status == RWLOCK_STATUS_READ) {
+        rwlock->num_reader--;
+        /* the last reader should notify the writers */
+        if (rwlock->num_reader == 0) {
+            rwlock->status = RWLOCK_STATUS_UNLOCK;
+            cond_broadcast(&rwlock->writer_cv);
+        }
+    } else {
+        affirm(rwlock->status == RWLOCK_STATUS_WRITE);
+        rwlock->status = RWLOCK_STATUS_UNLOCK;
+        /* notify all readers */
+        cond_broadcast(&rwlock->reader_cv);
+    }
+    mutex_unlock(&rwlock->status_lock);
+}
+
+/**
+ * @brief destroy a rwlock
+ */
+void rwlock_destroy(rwlock_t* rwlock) {
+    affirm(rwlock->status == RWLOCK_STATUS_UNLOCK);
+    mutex_destroy(&rwlock->status_lock);
+    cond_destroy(&rwlock->reader_cv);
+    cond_destroy(&rwlock->writer_cv);
+}
+
+/**
+ * @brief downgrade a rwlock
+ */
+void rwlock_downgrade(rwlock_t* rwlock) {
+    affirm(rwlock->status == RWLOCK_STATUS_WRITE);
+    rwlock->status = RWLOCK_STATUS_READ;
+    cond_broadcast(&rwlock->reader_cv);
+}
diff --git a/user/libthread/sem.c b/user/libthread/sem.c
new file mode 100644
index 0000000..d4d723e
--- /dev/null
+++ b/user/libthread/sem.c
@@ -0,0 +1,71 @@
+/**
+ * @file sem.c
+ * @author Hanjie Wu (hanjiew)
+ * @author Devang Acharya (devanga)
+ * @brief Semaphore implementation
+ * @date 2023-02-22
+ * 
+ */
+
+
+#include <sem.h>
+
+/**
+ * @brief Initializes the semaphore pointed to by 'sem' tp value 'count'
+ *
+ * @param sem semaphore
+ * @param count count
+ * @return int
+ */
+int sem_init(sem_t* sem, int count) {
+    sem->value = count;
+
+    mutex_init(&sem->value_lock);
+    cond_init(&sem->value_cv);
+
+    return 0;
+}
+
+/**
+ * @brief Decrement sem value, may block until it is possible to do so
+ *
+ * @param sem semaphore
+ */
+void sem_wait(sem_t* sem) {
+    mutex_lock(&sem->value_lock);
+
+    while (sem->value <= 0) {
+        /* wait until value goes up */
+        cond_wait(&sem->value_cv, &sem->value_lock);
+    }
+    sem->value -= 1;
+    mutex_unlock(&sem->value_lock);
+}
+
+/**
+ * @brief  wake up a thread waiting on the semaphore pointed to by sem
+ *
+ * @param sem semaphore
+ */
+void sem_signal(sem_t* sem) {
+    mutex_lock(&sem->value_lock);
+
+    sem->value += 1;
+
+    if (sem->value == 1) {
+        /* notify when value goes up from zero */
+        cond_signal(&sem->value_cv);
+    }
+    mutex_unlock(&sem->value_lock);
+}
+
+/**
+ * @brief deactivate semaphore. Must not be called on semaphores bwing waited
+ *        upon
+ *
+ * @param sem semaphore
+ */
+void sem_destroy(sem_t* sem) {
+    mutex_destroy(&sem->value_lock);
+    cond_destroy(&sem->value_cv);
+}
diff --git a/user/libthread/thread.c b/user/libthread/thread.c
new file mode 100644
index 0000000..56f6ac0
--- /dev/null
+++ b/user/libthread/thread.c
@@ -0,0 +1,325 @@
+/**
+ * @file thread.c
+ * @author Hanjie Wu (hanjiew)
+ * @author Devang Acharya (devanga)
+ * @brief Implementation of main thread functions
+ * @date 2023-02-22
+ *
+ */
+
+#include <stdbool.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#include <mutex.h>
+#include <simics.h>
+#include <syscall.h>
+#include <thr_internals.h>
+#include <thread.h>
+#include <ureg.h>
+
+/* return value for thread swexn */
+#define THREAD_EXIT_SWEXN -2
+
+/**
+ * @brief stack size requested
+ */
+static uintptr_t thr_stack_size;
+/**
+ * @brief stack size aligned
+ */
+static uintptr_t thr_stack_alloc_size;
+/**
+ * @brief highest address of thread stacks
+ */
+static uintptr_t thr_stack_begin;
+/**
+ * @brief lowest address of thread stacks
+ */
+static uintptr_t thr_stack_end;
+
+/**
+ * @brief tcb for main thread
+ */
+tcb_t main_tcb;
+
+/**
+ * @brief global lock for tcb operations
+ */
+mutex_t tcb_lock;
+
+/**
+ * @brief list of unused tcbs
+ */
+tcb_t* free_tcbs = NULL;
+
+/**
+ * @brief get esp register
+ */
+uintptr_t get_esp();
+/**
+ * @brief swexn handler for multithread programs
+ */
+static void thr_swexn_handler(void* arg, ureg_t* reg);
+/**
+ * @brief wrapper function for thread_fork syscall
+ * @param tcb tcb for new thread
+ * @param f user thread entry point
+ * @param args user arg for f
+ */
+int thread_fork(tcb_t* tcb, void* (*f)(void*), void* args);
+
+/**
+ * @brief Get the tcb of the thread this function is called form
+ *
+ * @return tcb_t*   pointer to current thread's TCB
+ */
+tcb_t* get_self_tcb() {
+    uintptr_t esp = get_esp();
+
+    /* check esp in main thread area */
+    if (esp > main_tcb.stack_lo) {
+        return &main_tcb;
+    }
+
+    /* calculate stack area from esp */
+    uintptr_t stack_end = esp + (thr_stack_begin - esp) % thr_stack_alloc_size;
+    /* pointer to tcb is at highest address in current thread stack */
+    return *(tcb_t**)(stack_end - sizeof(tcb_t*));
+}
+
+/**
+ * @brief Initialize thread library. Must be called once before using any thread
+ *        functions.
+ *
+ * Thread stack structure:
+ * +-------------------------+-----+---------------+
+ * | thread stack                  |address of tcb |
+ * +-------------------------+-----+---------------+
+ *
+ *
+ * @param size  the amount of stack space available for each thread
+ *
+ * @return int  0 on success, -1 on faliure
+ */
+int thr_init(uintptr_t size) {
+    /* set globals */
+    thr_stack_size = size;
+    thr_stack_alloc_size = ((size + PAGE_SIZE - 1) & PAGE_ALIGN_MASK);
+    thr_stack_begin = ((main_tcb.stack_lo) & PAGE_ALIGN_MASK);
+    thr_stack_end = thr_stack_begin;
+
+    /* initialize global lock - will never fail */
+    mutex_init(&tcb_lock);
+
+    if (swexn(ex_stack_end, thr_swexn_handler, NULL, NULL) < 0)
+        return -1;
+
+    return 0;
+}
+
+/**
+ * @brief Create a new thread with the entry point 'func', and arguments 'args'
+ *
+ * @param func  thread entry point
+ * @param args  thread entry function arguments
+ *
+ * @return -1 on failure, 0 on success
+ */
+int thr_create(void* (*func)(void*), void* args) {
+    /* holds return values for error checking and the TID to be returned */
+    int result;
+
+    /* holds pointer tcb for new thread */
+    tcb_t* thread_tcb;
+
+    mutex_lock(&tcb_lock);
+
+    /* find tcb from free list */
+    if (free_tcbs != NULL) {
+        thread_tcb = free_tcbs;
+        /* reuse stack area */
+        result = new_pages((void*)thread_tcb->stack_lo, thr_stack_alloc_size);
+
+        if (result != 0) {
+            mutex_unlock(&tcb_lock);
+            return -1;
+        }
+
+        /* remove from list (use tcb->right as link list) */
+        free_tcbs = free_tcbs->right;
+    }
+
+    else {
+        /* allocate new tcb */
+        thread_tcb = malloc(sizeof(tcb_t));
+
+        if (thread_tcb == NULL) {
+            mutex_unlock(&tcb_lock);
+            return -1;
+        }
+
+        thr_stack_end -= thr_stack_alloc_size;
+        result = new_pages((void*)thr_stack_end, thr_stack_alloc_size);
+
+        /* if new_pages unsuccessful */
+        if (result != 0) {
+            thr_stack_end += thr_stack_alloc_size;
+            free(thread_tcb);
+            mutex_unlock(&tcb_lock);
+            return -1;
+        }
+
+        /* set tcb stack boundaries */
+        thread_tcb->stack_lo = thr_stack_end;
+        thread_tcb->stack_hi =
+            thr_stack_end + thr_stack_alloc_size - sizeof(tcb_t*);
+    }
+
+    /* put pointer to tcb at the top of stack for get_self_tcb() use */
+    *(tcb_t**)(thread_tcb->stack_lo + thr_stack_alloc_size - sizeof(tcb_t*)) =
+        thread_tcb;
+
+    thread_tcb->waiter = 0;
+    thread_tcb->exited = 0;
+    thread_tcb->is_main = 0;
+
+    cond_init(&thread_tcb->wait_cv);
+
+    thread_tcb->mutex_next = NULL;
+    thread_tcb->mutex_resume = 0;
+
+    /* create new thread */
+    result = thread_fork(thread_tcb, func, args);
+
+    /* if thread_fork failed */
+    if (result < 0) {
+        cond_destroy(&thread_tcb->wait_cv);
+        remove_pages((void*)thread_tcb->stack_lo);
+
+        thread_tcb->right = free_tcbs;
+        free_tcbs = thread_tcb;
+
+        mutex_unlock(&tcb_lock);
+
+        return -1;
+    }
+
+    /* thread successfully created, return tid */
+
+    thread_tcb->tid = result;
+    rb_insert_tcb(thread_tcb);
+
+    mutex_unlock(&tcb_lock);
+
+    return result;
+}
+
+/**
+ * @brief wait thread tid to exit and get exit status
+ *
+ * @param tid thread to wait
+ * @param statusp output pointer for exit status
+ * @return int      0 on success, -1 on error
+ */
+int thr_join(int tid, void** statusp) {
+    mutex_lock(&tcb_lock);
+
+    tcb_t* tcb = rb_find_tcb(tid);
+
+    if (tcb == NULL) {
+        mutex_unlock(&tcb_lock);
+        return -1;
+    }
+
+    /* other thread is waiting for the thread */
+    if (tcb->waiter != 0) {
+        mutex_unlock(&tcb_lock);
+        return -1;
+    }
+
+    /* make sure others will not wait on this thread */
+    tcb->waiter = 1;
+
+    /* wait until thread exits */
+    if (tcb->exited != 1) {
+        cond_wait(&tcb->wait_cv, &tcb_lock);
+    }
+
+    /* return exited thread status if user wants it */
+    if (statusp != NULL) {
+        *statusp = tcb->exit_value;
+    }
+
+    /* cleanup and return */
+    rb_delete_tcb(tcb);
+    cond_destroy(&tcb->wait_cv);
+
+    if (tcb->is_main == 0) {
+        remove_pages((void*)tcb->stack_lo);
+        tcb->right = free_tcbs;
+        free_tcbs = tcb;
+    }
+
+    mutex_unlock(&tcb_lock);
+    return 0;
+}
+
+/**
+ * @brief exit from thread with given status
+ *
+ * @param status
+ */
+void thr_exit(void* status) {
+    tcb_t* tcb = get_self_tcb();
+    mutex_lock(&tcb_lock);
+
+    tcb->exit_value = (void*)status;
+    tcb->exited = 1;
+
+    cond_signal(&tcb->wait_cv);
+    /* call vanish after unlock and do not use stack becuase the stack may have
+     * been freed by other threads */
+    mutex_unlock_vanish(&tcb_lock);
+}
+
+/**
+ * @brief return the ID of the current thread
+ *
+ * @return int  - ID of the current thread
+ */
+int thr_getid(void) {
+    return get_self_tcb()->tid;
+}
+
+/**
+ * @brief Defers execution of involing thread
+ *
+ * @param tid
+ * @return int
+ */
+int thr_yield(int tid) {
+    return yield(tid);
+}
+
+/**
+ * @brief thread entrypoint wrapper
+ * @param f user func
+ * @param arg user argument
+ */
+void thr_begin(void* (*f)(void*), void* arg) {
+    mutex_lock(&tcb_lock);
+    mutex_unlock(&tcb_lock);
+    thr_exit(f(arg));
+}
+
+/**
+ * @brief swexn handler
+ *
+ * @param arg
+ * @param reg
+ */
+static void thr_swexn_handler(void* arg, ureg_t* reg) {
+    task_vanish(THREAD_EXIT_SWEXN);
+}
diff --git a/user/libthread/thread_fork.S b/user/libthread/thread_fork.S
new file mode 100644
index 0000000..143f17b
--- /dev/null
+++ b/user/libthread/thread_fork.S
@@ -0,0 +1,26 @@
+#include <syscall_int.h>
+
+// int thread_fork(tcb_t* tcb,
+//                 void* (*f)(void*),
+//                 void* args);
+.global thread_fork
+.type thread_fork, %function
+thread_fork:
+    mov 0x4(%esp), %edi   // tcb
+    mov 0x8(%esp), %esi   // f
+    mov 0xc(%esp), %edx   // arg
+    int $THREAD_FORK_INT
+    cmp $0, %eax
+    jne .parent           // both failure and success returns non-zero for parent
+    mov 0x8(%edi), %esp   // read tcb.stack_hi and set stack
+    push %edx
+    push %esi
+    call thr_begin        // thread entry point and this will not return
+.parent:
+    ret
+
+.global get_esp
+.type get_esp, %function
+get_esp:
+    lea -0x4(%esp), %eax
+    ret
diff --git a/user/progs/README.userprogs b/user/progs/README.userprogs
new file mode 100644
index 0000000..d8c7ab0
--- /dev/null
+++ b/user/progs/README.userprogs
@@ -0,0 +1 @@
+Your own test programs go in this directory.
diff --git a/user/progs/mandelbrot.c b/user/progs/mandelbrot.c
new file mode 100644
index 0000000..957d513
--- /dev/null
+++ b/user/progs/mandelbrot.c
@@ -0,0 +1,533 @@
+/*!
+ * @file mandelbrot.c
+ *
+ * @brief A very cool, fractal test.
+ *
+ * Written by Keith Bare sometime aeons ago, improved by sully
+ * to support panning and zooming in Spring 2014.
+ *
+ * This version compromises on some of the original behaviors of
+ * mandelbrot in order to get panning/zooming to perform better
+ * in Simics.  Both versions run beautifully in QEMU, though.
+ *
+ * In particular, we skip displaying a blue + in squares about to be
+ * updated and we only update squares that don't need it with
+ * probability 1/REDO_FACTOR.
+ *
+ * Setting TRADITIONAL to 1 recovers the old behaviors.
+ *
+ * @author Keith Bare
+ * @author Michael Sullivan (mjsulliv@)
+ */
+
+/* Whether to do certain traditional mandelbrot behaviors or to skip them
+ * in favor of being faster. */
+#define TRADITIONAL 0
+
+#include <assert.h>
+#include <stdio.h>
+#include <stddef.h>
+#include <syscall.h>
+#include <simics.h>
+#include <stdlib.h>
+
+#include <malloc.h>
+#include <thread.h>
+#include <cond.h>
+#include <mutex.h>
+#include <thrgrp.h>
+
+// We define this as assert for convenience, but it isn't really intended
+// to be the same. We use expect to check for fatal errors that require
+// us to abort the program.
+#define expect assert
+
+/* Not all kernels support getchar(). Try to use it, but if it doesn't work,
+ * fall back to readline. */
+static int fallback_getchar(void)
+{
+    char buf[2];
+    readline(2, buf);
+    return (unsigned char)buf[0]; // cast prevents sign extension
+}
+static int try_getchar(void)
+{
+	static int no_getchar = 0;
+	int c;
+	if (no_getchar || (c = getchar()) < 0) {
+		no_getchar = 1;
+		return fallback_getchar();
+	}
+	return c;
+}
+#define getchar try_getchar
+
+
+// Filled in by find_console_size
+int console_width;  /*!<@brief Height of the console */
+int console_height; /*!<@brief Width of the console */
+
+// Some tunables
+#define YIELD_FACTOR 8 /*!<@brief Higher => thread is less likely to yield */
+#define REDO_FACTOR 4 /*!<@brief Higher => thread is less likely to redo */
+
+#define MAX_TRAPS 30   /*!<@brief Maximum number of support traps */
+
+// Fixed point stuff
+typedef int fixed_t;
+
+#define FRACTIONAL_BITS 24 /*!<@brief Number of fixed point fractional bits */
+
+// A bunch of macros for constructing fixed point numbers.
+#define SIGN(n) ((n) < 0 ? -1 : 1)
+#define INT_TO_FIXED(n) ((n) << FRACTIONAL_BITS)
+#define FRAC_TO_FIXED(n, d) ((fixed_t)(INT_TO_FIXED((long long)n) / d))
+#define IMPROPER_TO_FIXED(i, n, d) FRAC_TO_FIXED(i*d + SIGN(i)*n, d)
+#define DEC3_TO_FIXED(i, dec) IMPROPER_TO_FIXED(i, dec, 1000)
+
+#define INITIAL_COL_BASE DEC3_TO_FIXED(-2,500)
+#define INITIAL_COL_LAST DEC3_TO_FIXED( 1,450)
+#define INITIAL_ROW_BASE DEC3_TO_FIXED(-1,500)
+#define INITIAL_ROW_LAST DEC3_TO_FIXED( 1,375)
+
+
+/*!<@brief The real coordinates for the left and right edges of the screen */
+fixed_t col_base = INITIAL_COL_BASE;
+fixed_t col_last = INITIAL_COL_LAST;
+/*!<@brief The imaginary coordinates for the top and bottom edges */
+fixed_t row_base = INITIAL_ROW_BASE;
+fixed_t row_last = INITIAL_ROW_LAST;
+
+// These get set by recompute_steps()
+fixed_t col_step;
+fixed_t row_step;
+
+int cur_generation = 0;
+
+/*!
+ * @brief Type for state that the threads modify
+ */
+typedef struct mandelbrot_state {
+    mutex_t cell_mutex; /*!< Mutex protecting this cell */
+    int count;          /*!< Number of threads that have visited this cell */
+    int trap_num;       /*!< -1, or the index of the condition variable in
+                             which visited threads are trapped */
+    int trapped_threads;/*!< Number of threads trapped at this cell */
+    int exiting;        /*!< Indicates that the program is terminating */
+    int generation;     /*!< What generation the cell was last updated at */
+    int color;
+} mandelbrot_state_t;
+
+
+mutex_t console_lock;    /*!<@brief Mutex protecting the console */
+
+cond_t traps[MAX_TRAPS]; /*!<@brief Array of condition variables in which
+                              threads can get &quot;stuck&quot; */
+
+int exiting = 0;         /*!<@brief Flag the indicates the test is exiting */
+
+int wakeup_threshold = 1;/*!<@brief Maximum number of waiting threads */
+
+/*!
+ * @brief Shared state that the threads modify.
+ */
+mandelbrot_state_t *state;
+
+unsigned long getrand(void) {
+    // FIXME: XXX: rand is not threadsafe!
+    return rand();
+}
+
+/*!
+ * @brief Fixed point multiplication.
+ *
+ * This is so I can do cool things, even though Pebbles doesn't allow programs
+ * to use the FPU.
+ */
+fixed_t fixed_mult(fixed_t a, fixed_t b)
+{
+    // Multiply the numbers, getting a result with FRACTIONAL_BITS*2
+    // fractional bits.
+    long long mult_result = (long long)a * (long long)b;
+    // Round off
+    mult_result += (1 << (FRACTIONAL_BITS-1));
+    return (fixed_t)(mult_result >> FRACTIONAL_BITS);
+}
+
+/*! @brief Compute the squared magnitude of a complex number. */
+fixed_t mag2(fixed_t r, fixed_t i) {
+    return fixed_mult(r, r) + fixed_mult(i, i);
+}
+
+/*!
+ * @brief Calculates the color that a (row, column) pair of the
+ * mandelbrot set should be.
+ *
+ * Returns the number of iterations of the Mandelbrot equation, Z =
+ * (Z_{n - 1})^2 + Z_0, occur before Z is more than a distance of one
+ * from the complex origin.
+ */
+int mandelbrot_calc(int row, int col)
+{
+    int i;
+
+    fixed_t imag_coord_init = row_base + row*row_step;
+    fixed_t real_coord_init = col_base + col*col_step;
+    fixed_t imag_coord = imag_coord_init;
+    fixed_t real_coord = real_coord_init;
+
+    for (i = 0; i < 14 && mag2(real_coord,imag_coord) < INT_TO_FIXED(4); i++) {
+        int tmp_imag_coord = 2*fixed_mult(real_coord, imag_coord) +
+                             imag_coord_init;
+        real_coord = fixed_mult(real_coord, real_coord) -
+                     fixed_mult(imag_coord, imag_coord) +
+                     real_coord_init;
+        imag_coord = tmp_imag_coord;
+    }
+
+    return i;
+}
+
+/*!
+ * @brief Processes and draws a "pixel".
+ *
+ * Assumes that the caller has console_lock.
+ *
+ * @param row row of the pixel to draw
+ * @param col column of the pixel to draw
+ */
+int process_pixel(int row, int col)
+{
+    mandelbrot_state_t *st = &state[row*console_width + col];
+    int wokeup = 0;
+
+    mutex_lock(&st->cell_mutex);
+
+    if (st->exiting) {
+        mutex_unlock(&st->cell_mutex);
+        return -1;
+    }
+
+    // Do wakeups before considering whether to bail on this location.
+    if (st->trapped_threads >= wakeup_threshold) {
+        cond_broadcast(&traps[st->trap_num]);
+        wokeup = 1;
+    }
+
+    // Compute the color if it is out of date. If it isn't,
+    // skip the rest of the processing "most of the time".
+    if (st->generation < cur_generation) {
+        st->color = mandelbrot_calc(row, col);
+        st->generation = cur_generation;
+    } else if (!TRADITIONAL && getrand() % REDO_FACTOR != 0) {
+        mutex_unlock(&st->cell_mutex);
+        return -1;
+    }
+
+    // If there is a trap, get caught in it. (Unless we freed threads from it.)
+    if (!wokeup && st->trap_num >= 0) {
+        st->trapped_threads++;
+
+        mutex_lock(&console_lock);
+        set_cursor_pos(row, col);
+        set_term_color((15 - st->color) | BGND_RED);
+        putchar('0' + st->trapped_threads % 10);
+        mutex_unlock(&console_lock);
+
+        cond_wait(&traps[st->trap_num],
+                  &st->cell_mutex);
+
+        st->trapped_threads--;
+    }
+
+    st->count++;
+
+    mutex_lock(&console_lock);
+    set_cursor_pos(row, col);
+    set_term_color((15 - st->color) | BGND_BLACK);
+    putchar('a' + st->count % 26);
+    mutex_unlock(&console_lock);
+
+    mutex_unlock(&st->cell_mutex);
+
+    return 0;
+}
+
+/*!
+ * @brief Main function for wanderer_threads.
+ *
+ * @param arg
+ */
+void *wanderer_main(void *arg)
+{
+    int row, col;
+
+    row = getrand() % (console_height - 1);
+    col = getrand() % console_width;
+
+    while (!exiting) {
+        process_pixel(row, col);
+
+        row = getrand() % (console_height - 1);
+        col = getrand() % console_width;
+
+        if (getrand() % YIELD_FACTOR == 0) {
+            yield(-1);
+        }
+
+#if TRADITIONAL
+        mutex_lock(&console_lock);
+        set_cursor_pos(row, col);
+        set_term_color(FGND_BLACK | BGND_BLUE);
+        printf("%c", '+');
+        mutex_unlock(&console_lock);
+
+        if (getrand() % YIELD_FACTOR == 0) {
+            yield(-1);
+        }
+#endif
+    }
+
+    return NULL;
+}
+
+/*!
+ * @brief Prints a usage message.
+ */
+void usage() {
+    printf("mandelbrot [num_threads] [num_traps] [wakeup_threshold]\n\n");
+    printf("num_traps must be <= %d\n", MAX_TRAPS);
+    printf("if num_traps * (wakeup_threshold - 1) >= num_threads "
+           "deadlock may result\n");
+}
+
+// Dynamically determine the console size. Most Pebbles implementations
+// are 80x25, but there have been students who handed in window managers,
+// and there exist at least two projects that attempt to run Pebbles
+// binaries on Linux.
+static void find_console_size() {
+    int orig_row, orig_col;
+    get_cursor_pos(&orig_row, &orig_col);
+
+    /* determine the height of the console */
+    console_height = 0;
+    while (set_cursor_pos(console_height, 0) == 0) {
+        console_height++;
+    }
+    /* determine the width of the console */
+    console_width = 0;
+    while (set_cursor_pos(0, console_width) == 0) {
+        console_width++;
+    }
+
+    set_cursor_pos(orig_row, orig_col);
+}
+
+// Recompute the step amounts after something changes.
+void recompute_steps(void) {
+    col_step = ((col_last-col_base)/(console_width-1));
+    row_step = ((row_last-row_base)/(console_height-2));
+}
+
+// When we pan around, we update the parameters without synchronizing
+// with computation threads at all. This is sort of hokey but ultimately
+// we don't care. The worst that can happen is some pixels are the
+// wrong color for a bit.
+void input_loop(void) {
+    fixed_t row_move;
+    fixed_t col_move;
+
+    while (1) {
+        char c = getchar();
+        switch (c) {
+        case 'q':
+            return;
+        case 'w':
+            row_base -= row_step;
+            row_last -= row_step;
+            break;
+        case 's':
+            row_base += row_step;
+            row_last += row_step;
+            break;
+        case 'a':
+            col_base -= col_step;
+            col_last -= col_step;
+            break;
+        case 'd':
+            col_base += col_step;
+            col_last += col_step;
+            break;
+        case 'i':
+            // We want to cut the distance between the edges by a factor
+            // of 2, which means moving each edge
+            // current_distance/4.
+            row_move = (row_last-row_base)/4;
+            row_base += row_move;
+            row_last -= row_move;
+            col_move = (col_last-col_base)/4;
+            col_base += col_move;
+            col_last -= col_move;
+
+            recompute_steps();
+
+            break;
+
+        case 'o':
+            // We want to increase the distance between the edges by a factor
+            // of 2, which means moving each edge
+            // current_distance/2?
+            row_move = (row_last-row_base)/2;
+            row_base -= row_move;
+            row_last += row_move;
+            col_move = (col_last-col_base)/2;
+            col_base -= col_move;
+            col_last += col_move;
+
+            recompute_steps();
+
+            break;
+
+        case 'r':
+            col_base = INITIAL_COL_BASE;
+            col_last = INITIAL_COL_LAST;
+            row_base = INITIAL_ROW_BASE;
+            row_last = INITIAL_ROW_LAST;
+
+            recompute_steps();
+
+            break;
+        default:
+            break;
+        }
+
+        cur_generation++;
+    }
+}
+
+
+/*!
+ * @brief Code entry-point.
+ *
+ * @param argc
+ * @param argv
+ */
+int main(int argc, char *argv[])
+{
+    thrgrp_group_t thread_group;
+    int num_threads = 15;
+    int num_traps = 8;
+    void *status;
+
+    int i;
+
+    if (argc >= 2) {
+        if (sscanf(argv[1], "%d", &num_threads) < 1 || num_threads <= 0) {
+            usage();
+            return 0;
+        }
+    }
+    if (argc >= 3) {
+        if (sscanf(argv[2], "%d", &num_traps) < 1 || num_traps < 0 ||
+            num_traps > MAX_TRAPS) {
+            usage();
+            return 0;
+        }
+    }
+    if (argc >= 4) {
+        if (sscanf(argv[3], "%d", &wakeup_threshold) < 1) {
+            usage();
+            return 0;
+        }
+    }
+
+    srand(get_ticks());
+
+    lprintf("Initializing thread library...");
+    expect(thr_init(PAGE_SIZE * 10) >= 0);
+
+    lprintf("Initializing console lock...");
+    expect(mutex_init(&console_lock) >= 0);
+
+    lprintf("Finding console size...");
+    find_console_size();
+
+    lprintf("Initializing state...");
+    int num_spots = console_width*(console_height-1);
+    state = malloc(num_spots*sizeof(*state));
+    expect(state != NULL);
+
+    for (i = 0; i < num_spots; i++) {
+        expect(mutex_init(&state[i].cell_mutex) >= 0);
+        state[i].count = -1;
+        state[i].trap_num = -1;
+        state[i].trapped_threads = 0;
+        state[i].exiting = 0;
+        state[i].generation = -1;
+    }
+
+    lprintf("Initializing traps...");
+    /* May not assign all the traps, but it doesn't matter. */
+    for (i = 0; i < num_traps; i++) {
+        expect(cond_init(&traps[i]) >= 0);
+        state[getrand() % num_spots].trap_num = i;
+    }
+
+    // Set up the values
+    recompute_steps();
+
+    lprintf("Clearing console...");
+    for (i = 0; i < console_height; i++) {
+        printf("\n");
+    }
+
+    set_cursor_pos(console_height-1, 0);
+    printf("wasd to pan, i = zoom in, o = zoom out, r = reset, q = quit");
+
+    lprintf("Initializing thread group...");
+    expect(thrgrp_init_group(&thread_group) >= 0);
+
+    lprintf("Creating wanderer threads...");
+    for (i = 0; i < num_threads; i++) {
+        thrgrp_create(&thread_group, &wanderer_main, NULL);
+    }
+
+    lprintf("Waiting for input...");
+    input_loop();
+
+    exiting = 1;
+
+    for (i = 0; i < num_spots; i++) {
+        mutex_lock(&state[i].cell_mutex);
+        state[i].exiting = 1;
+        mutex_unlock(&state[i].cell_mutex);
+    }
+
+    for (i = 0; i < num_traps; i++) {
+        cond_broadcast(&traps[i]);
+    }
+
+    lprintf("Joining with wanderer threads...");
+    for (i = 0; i < num_threads; i++) {
+        thrgrp_join(&thread_group, &status);
+    }
+
+    lprintf("Destroying thread group...");
+    thrgrp_destroy_group(&thread_group);
+
+    for (i = 0; i < num_spots; i++) {
+        mutex_destroy(&state[i].cell_mutex);
+    }
+
+    for (i = 0; i < num_traps; i++) {
+        cond_destroy(&traps[i]);
+    }
+
+    mutex_destroy(&console_lock);
+
+    set_cursor_pos(console_height - 1, 0);
+    set_term_color(FGND_CYAN | BGND_BLACK);
+
+    thr_exit(NULL);
+    return 0;
+}
diff --git a/user/progs/nibbles.c b/user/progs/nibbles.c
new file mode 100644
index 0000000..31de3a5
--- /dev/null
+++ b/user/progs/nibbles.c
@@ -0,0 +1,462 @@
+/*
+ * Test program for the Spring 2004 15-410 Kernel project
+ * Clone of the nibbles/snake game
+ *
+ * by Michael Ashley-Rollman (mpa)
+ * tweaked by Dave Eckhardt (de0u) for Fall 2011 P4
+ */
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <syscall.h>
+#include <syscall_int.h>
+#include <rand.h>
+#include <assert.h>
+
+#define SLEEP_TICKS 75
+
+#define SNAKE_COLOR 0x60
+#define SNAKE_CHAR " "
+
+#define APPLE_COLOR 0x4
+#define APPLE_CHAR "@"
+
+#define BORDER_COLOR 0x30
+#define BORDER_CHAR ' '
+
+#define BLANK_COLOR 0x0
+#define TEXT_COLOR 0x2
+
+/* Maximum possible console width */
+#define MAX_POS_WIDTH 128
+
+/* Maximum snake length */
+#define SNAKE_MAX_LENGTH 100
+
+/* Minimum snake length */
+#define SNAKE_MIN_LENGTH 10
+
+#define SNAKE_UP 'w'
+#define SNAKE_DOWN 's'
+#define SNAKE_LEFT 'a'
+#define SNAKE_RIGHT 'd'
+
+#define SNAKE_START_ROW 10
+#define SNAKE_START_COL 10
+#define SNAKE_START_DIR SNAKE_RIGHT
+
+#define APPLE_MIN_WAIT 20
+#define APPLE_MAX_WAIT 40
+
+#define APPLE_MAX_NUM 10
+#define APPLE_SCORE 10
+
+/* The snake */
+typedef struct {
+  int length;
+  int start;
+  int spot[SNAKE_MAX_LENGTH][2];
+  char direction;
+} snake_t;
+
+/* The Apples */
+typedef struct {
+  int x;
+  int y;
+  int valid;
+} apple_t;
+
+/* inter-move delay
+ * (adjustable for simulation vs. hardware)
+ * (could be adjusted downward as play progresses)
+ */
+int sleep_ticks = SLEEP_TICKS;
+
+/* width of the console */
+int con_width;
+
+/* height of the console */
+int con_height;
+
+/* the current score */
+int score;
+
+/* the last key pressed */
+volatile int last_key;
+
+int spawn_key_grabber(void);
+
+/* prints out the play instructions */
+void print_directions()
+{
+  printf("Move the snake using the controls listed below.\n");
+  printf("Eat the apples to get points, but don't hit the\n");
+  printf("wall or let the snake bite himself.\n");
+  printf("UP - w\n");
+  printf("DOWN - s\n");
+  printf("LEFT - a\n");
+  printf("RIGHT - d\n");
+  printf("\n\n");
+};
+
+/* draws the border around the edge of the screen and blanks the middle */
+void draw_border()
+{
+  int i;
+  char buf[MAX_POS_WIDTH];
+
+  for (i = 0; i < con_width; i++) {
+    buf[i] = BORDER_CHAR;
+  }
+
+  set_term_color(BLANK_COLOR);
+  set_cursor_pos(con_height-1,0);
+  print(con_width, buf);
+
+  set_term_color(BORDER_COLOR);
+  set_cursor_pos(0,0);
+  print(con_width, buf); 
+
+  for (i = 1; i < con_height - 2; i++) {
+    set_term_color(BLANK_COLOR);
+    set_cursor_pos(i,0);
+    print(con_width, buf);
+
+    set_term_color(BORDER_COLOR);
+    set_cursor_pos(i, 0);
+    print(1, buf);
+
+    set_cursor_pos(i, con_width-1);
+    print(1, buf);
+  }
+
+  set_cursor_pos(con_height - 2,0);
+  print(con_width, buf); 
+
+  score = 0;
+  set_cursor_pos(con_height - 1, 0);
+  set_term_color(TEXT_COLOR);
+  printf("score: %d", score);
+}
+
+/* initializes a snake to the starting size and location */
+void init_snake(snake_t *snake) {
+  int i;
+
+  snake->length = SNAKE_MIN_LENGTH;
+  snake->start = SNAKE_MIN_LENGTH - 1;
+
+  for (i = 0; i < SNAKE_MIN_LENGTH; i++) {
+    snake->spot[i][0] = SNAKE_START_COL;
+    snake->spot[i][1] = SNAKE_START_ROW;
+  }
+
+  snake->direction = SNAKE_START_DIR;
+}
+
+/* checks to see if the snake has killed itself
+ *
+ * returns 0 if the snake is still alive and -1 on death
+ */
+int snake_disaster(snake_t *snake)
+{
+  int i, stop;
+  int snake_x = snake->spot[snake->start][0];
+  int snake_y = snake->spot[snake->start][1];
+
+  /* check to see if the snake is within bounds */
+  if (snake_x <= 0 ||
+      snake_x >= con_width - 1 ||
+      snake_y <= 0 ||
+      snake_y >= con_height - 2)
+    return -1;
+
+  /* check to see if the snake is biting itself */
+  stop = (snake->start - snake->length + SNAKE_MAX_LENGTH) % SNAKE_MAX_LENGTH;
+
+  for (i = (snake->start - 1 + SNAKE_MAX_LENGTH) % SNAKE_MAX_LENGTH;
+       i != stop;
+       i = (i-1 + SNAKE_MAX_LENGTH) % SNAKE_MAX_LENGTH)
+    if (snake->spot[i][0] == snake_x &&
+	snake->spot[i][1] == snake_y)
+      return -1;
+
+  return 0;
+}
+
+/* moves the snake forward a space, eating any apples there */
+void move_snake(snake_t *snake, apple_t *apples)
+{
+  int old_x, old_y;
+  int new_x, new_y;
+  int remove_x, remove_y;
+
+  int i;
+  
+  /* get the position of the head of the snake */
+  old_x = snake->spot[snake->start][0];
+  old_y = snake->spot[snake->start][1];
+
+  snake->start = (snake->start + 1) % SNAKE_MAX_LENGTH;
+
+  /* get the position of the tail of the snake */
+  remove_x = snake->spot[(snake->start -
+			  snake->length +
+			  SNAKE_MAX_LENGTH) %
+			 SNAKE_MAX_LENGTH][0];
+  remove_y = snake->spot[(snake->start -
+			  snake->length +
+			  SNAKE_MAX_LENGTH) %
+			 SNAKE_MAX_LENGTH][1];
+
+  /* find where the head of the snake has slithered to */
+  switch (snake->direction) {
+  case SNAKE_UP:
+    new_x = old_x;
+    new_y = old_y - 1;
+    break;
+
+  case SNAKE_DOWN:
+    new_x = old_x;
+    new_y = old_y + 1;
+    break;
+
+  case SNAKE_LEFT:
+    new_x = old_x - 1;
+    new_y = old_y;
+    break;
+
+  case SNAKE_RIGHT:
+    new_x = old_x + 1;
+    new_y = old_y;
+    break;
+
+  default:
+    panic("Impossible direction %d", snake->direction);
+    return;
+  }
+
+  /* fill int he new head */
+  snake->spot[snake->start][0] = new_x;
+  snake->spot[snake->start][1] = new_y;
+  
+  /* delete the old tail */
+  if (!set_cursor_pos(remove_y, remove_x)) {
+    set_term_color(BLANK_COLOR);
+    print(1, " ");
+  }
+
+  /* display the head */
+  if (!set_cursor_pos(new_y, new_x)) {
+    set_term_color(SNAKE_COLOR);
+    print(1, SNAKE_CHAR);
+  }
+
+  /* ate any apples that the snake has hit */
+  for (i = 0; i < APPLE_MAX_NUM; i++)
+    if (apples[i].valid == 1 &&
+	apples[i].x == new_x &&
+	apples[i].y == new_y) {
+      score += APPLE_SCORE;
+      apples[i].valid = 0;
+      snake->length++;
+      if (snake->length > SNAKE_MAX_LENGTH)
+	snake->length = SNAKE_MAX_LENGTH;
+    }      
+}
+
+/* randomly place a new apple on the screen */
+void new_apple(snake_t *snake, apple_t *apple)
+{
+  int spot;
+  int x,y;
+
+  /* find a spot for an apple in the array */
+  for (spot = 0; spot < APPLE_MAX_NUM; spot++)
+    if (!apple[spot].valid) break;
+
+  if (spot == APPLE_MAX_NUM) return;
+
+  /* pick a place on the screen */
+  x = genrand() / ((unsigned int)(-1) / (con_width - 2)) + 1;
+  y = genrand() / ((unsigned int)(-1) / (con_height - 3)) + 1;
+
+  /* set the apple */
+  apple[spot].valid = 1;
+  apple[spot].x = x;
+  apple[spot].y = y;
+
+  /* draw the apple */
+  set_term_color(APPLE_COLOR);
+  set_cursor_pos(y, x);
+  print(1, APPLE_CHAR);
+}
+
+/* plays through the game once */
+void play_game(snake_t *snake)
+{
+  int next_apple = 0;
+  int i;
+
+  /* initialize the apples */
+  apple_t apples[APPLE_MAX_NUM];
+
+  for (i = 0; i < APPLE_MAX_NUM; i++)
+    apples[i].valid = 0;
+
+  do {
+    /* change the snake direction if appropriate */
+    switch (last_key) {
+    case SNAKE_UP:
+      if (snake->direction != SNAKE_DOWN)
+	snake->direction = SNAKE_UP;
+      break;
+
+    case SNAKE_DOWN:
+      if (snake->direction != SNAKE_UP)
+	snake->direction = SNAKE_DOWN;
+      break;
+
+    case SNAKE_LEFT:
+      if (snake->direction != SNAKE_RIGHT)
+	snake->direction = SNAKE_LEFT;
+      break;
+
+    case SNAKE_RIGHT:
+      if (snake->direction != SNAKE_LEFT)
+	snake->direction = SNAKE_RIGHT;
+      break;
+
+    default:
+      break;
+    }
+
+    /* add a new apple if it's time */
+    if (next_apple == 0) {
+      new_apple(snake, apples);
+      next_apple = genrand() /
+	(((unsigned int)-1) / (APPLE_MAX_WAIT - APPLE_MIN_WAIT))
+	+ APPLE_MIN_WAIT;
+    }
+
+    /* move the snake */
+    move_snake(snake, apples);
+
+    /* update the score */
+    set_cursor_pos(con_height - 1, 7);
+    set_term_color(TEXT_COLOR);
+    printf("%d", score);
+
+    /* nap for a bit to prevent the game from going too fast */
+    sleep(sleep_ticks);
+    next_apple--;
+  }
+  /* loop until the snake kills itself */
+  while(!snake_disaster(snake));
+}
+
+/* the game nibbles */
+void nibbles()
+{
+  
+  char again;
+  snake_t snake;
+
+  do {
+    /* do the initial set up */
+    draw_border();
+    init_snake(&snake);
+    last_key = -1;
+    
+    /* play the game */
+    play_game(&snake);
+
+    /* query to play again */
+    set_term_color(TEXT_COLOR);
+    set_cursor_pos(con_height / 2, (con_width - 11) / 2);
+
+    last_key = -1;
+    print(11, "Play again?");
+
+    while ((again = last_key) != 'y' &&
+	   again != 'Y' &&
+	   again != 'n' &&
+	   again != 'N');
+
+  } while (again == 'y' || again == 'Y');
+
+  task_vanish(0);
+}
+
+int main(int argc, char *argv[])
+{
+  int rand_seed, child_tid;
+
+  if (argc > 1) {
+    sleep_ticks = atoi(argv[1]);
+  }
+
+  /* find the width of the console */
+  for(con_width = 0; !set_cursor_pos(0, con_width); con_width++)
+    continue;
+
+  /* find the height of the console */
+  for(con_height = 0; !set_cursor_pos(con_height, 0); con_height++)
+    continue;
+
+  /* spawn key_scanner */
+  child_tid = spawn_key_grabber();
+
+  if (child_tid < 0) {
+    printf("Cannot launch \"thread\" (%d)\n", child_tid);
+    task_vanish(child_tid);
+  }
+
+  /* print out the directions */
+  print_directions();
+
+  /* get random number */
+  printf("Press any key to begin nibbles\n");
+  for (rand_seed = 0; last_key == -1; rand_seed++)
+    sleep(1);
+  sgenrand(rand_seed);
+
+  /* start game */
+  nibbles();
+
+  return 0;
+}
+
+/*****************************************************************
+ *  ____    _____    ___    ____  
+ * / ___|  |_   _|  / _ \  |  _ \ 
+ * \___ \    | |   | | | | | |_) |
+ *  ___) |   | |   | |_| | |  __/ 
+ * |____/    |_|    \___/  |_|    
+ *
+ * You may NOT write code this way.
+ *
+ * This code was written this way so it doesn't need to depend
+ * on your thread library, and then because the build framework
+ * requires each test program to be built from just one source
+ * file.
+ *
+ *****************************************************************/
+
+void foobar() {
+asm(".global spawn_key_grabber\n"
+	
+"spawn_key_grabber:\n"
+"       movl    $-1,last_key\n"         /* set the last key pressed to none*/
+"	int	%0\n"           	/* Fork a clone */
+"	cmpl	$0,%%eax\n"
+"	je	key_grab\n"		/* Child starts grabbing keys */
+"	ret\n"				/* Parent returns child tid */
+	
+"key_grab:\n"
+"	int	%1\n"       	        /* Get a new character */
+"	movl	%%eax,last_key\n"	/* Save it */
+"	jmp	key_grab\n"	        /* Do it again =) */
+    :: "i" (THREAD_FORK_INT)
+    , "i" (GETCHAR_INT)); 
+}
diff --git a/user/progs/racer.c b/user/progs/racer.c
new file mode 100644
index 0000000..1d633de
--- /dev/null
+++ b/user/progs/racer.c
@@ -0,0 +1,207 @@
+/**
+ * @file racer.c
+ *
+ * @brief a very strenuous test of mutexes, condition variables, and semaphores
+ *
+ * @author Peter Nelson <pnelson>
+ *
+ * This creates <threads> number of threads.  Each thread gets 1 line of the
+ * terminal.  Every thread attempts to aquire the semaphore which was
+ * initialized with a value of <semaphores>.  When a thread aquires the sem
+ * it prints out <runlength> number of characters, one at a time.
+ *
+ * There is an additional <pausetime> that can be used to cause each thread
+ * to call sleep of that value.  Finally there is a "bad" thread that
+ * cycles misbehave states and then sleeps for <misbehavetime>.
+ * 
+ * The expected default result is seeing a group of 12 threads run out for 5
+ * characters.  Then the next group of 12 threades will run out for 5 characters.
+ * The bottom-right corner shows the current number of threads that are active
+ * (should always be <=12) and the current misbehave state.
+ * 
+ * threads and semaphores should be set to 24 and 12 for best effect
+ * runlength should be set to 5-10 to be able to see how many are active,
+ * or set to 1 for the most strenuous
+ *
+ * Colors are pseudo-randomly rotated by continuously adding get_ticks() to
+ * the color value.  No real point other than to be trippy.
+ * 
+ * Arguments: program threads runlength semaphores pausetime misbehavetime
+ */
+
+#include <thread.h>
+#include <syscall.h>
+#include <simics.h>
+#include <stdio.h>
+#include <sem.h>
+#include <mutex.h>
+#include <stdlib.h>
+
+#define STACK_SIZE 4096
+#define MAX_MISBEHAVE 64
+
+// Uses my static initializer, you might have to change this
+mutex_t lock_print;
+
+// Default values
+int threads = 24;
+int run = 5;
+int sems = 12;
+sem_t sem;
+int pause = 0;
+int bad_sleep = 50;
+
+char alphabet[] = "abcdefghijklmnopqrstuvwxyz";
+char empty[81];
+mutex_t lock_running;
+int running = 0;
+
+char color = 0;
+
+#define expect(exp) \
+    { \
+        err = exp; \
+        if(err < 0) \
+            lprintf("%s:%u: returned %d", \
+                    __FILE__, __LINE__, err); \
+    }
+
+void *race(void *arg)
+{
+    int err;
+    int col = -1;
+    int i;
+    int row = (int)arg;
+    
+    mutex_lock(&lock_print);
+    color += get_ticks();
+    set_term_color(color);
+    expect(set_cursor_pos(row, 0));
+    printf("%s", &empty[0]);
+    mutex_unlock(&lock_print);
+
+    while(1)
+    {
+        sem_wait(&sem);
+
+        mutex_lock(&lock_running);
+        int r = ++running;
+        mutex_unlock(&lock_running);
+        if(r > sems)
+            lprintf("BAD! I have %d > %d threads running", r, sems);
+        
+        mutex_lock(&lock_print);
+        expect(set_cursor_pos(24, 77));
+        printf("%.2d", running);
+        mutex_unlock(&lock_print);
+        
+        for(i = 0; i < run; i++)
+        {
+            col++;
+            if(80 == col)
+            {
+                mutex_lock(&lock_print);
+                color += get_ticks();
+                set_term_color(color);
+                expect(set_cursor_pos(row, 0));
+                printf("%s", &empty[0]);
+                mutex_unlock(&lock_print);
+                col = 0;
+            }
+            
+            mutex_lock(&lock_print);
+            color += get_ticks();
+            set_term_color(color);
+            expect(set_cursor_pos(row, col));
+            printf("%c", alphabet[i]);
+            mutex_unlock(&lock_print);
+
+            if(pause)
+                expect(sleep(pause));
+            thr_yield(-1);
+        }
+
+        mutex_lock(&lock_running);
+        running--;
+        mutex_unlock(&lock_running);
+        
+        sem_signal(&sem);
+    }
+}
+
+void *bad(void *arg)
+{
+    while(1)
+    {
+        int err;
+        int i = (int)arg;
+
+        for(i=-1; i<MAX_MISBEHAVE; i++)
+        {
+            lprintf("calling misbehave(%d)", i);
+        
+            mutex_lock(&lock_print);
+            expect(set_cursor_pos(24, 73));
+            printf("% .2d", i);
+            mutex_unlock(&lock_print);
+
+            misbehave(i);
+            sleep(bad_sleep);
+        }
+    }
+    return arg;
+}
+
+int main( int argc, char *argv[] )
+{
+    int i, err;
+
+    switch(argc) {
+        case 6:
+            i = atoi(argv[5]);
+            if(i >= 0)
+                bad_sleep = i;
+            /* FALLTHROUGH */
+        case 5:
+            i = atoi(argv[4]);
+            if(i >= 0)
+                pause = i;
+            /* FALLTHROUGH */
+        case 4:
+            i = atoi(argv[3]);
+            if(i > 0)
+                sems = i;
+            /* FALLTHROUGH */
+        case 3:
+            i = atoi(argv[2]);
+            if(i <= 26 && i > 0)
+                run = i;
+            /* FALLTHROUGH */
+        case 2:
+            i = atoi(argv[1]);
+            if(i > 1 && i <= 24)
+                threads = i;
+            /* FALLTHROUGH */
+        default:
+            break;
+    }
+
+    expect(thr_init(STACK_SIZE));
+    expect(mutex_init(&lock_print));
+    expect(mutex_init(&lock_running));
+    expect(sem_init(&sem, sems));
+
+    for(i=0; i<80; i++)
+        empty[i] = ' ';
+    empty[80] = '\0';
+   
+    expect(thr_create(bad, (void*)i) >= 0);
+    
+    for(i=0; i<threads; i++)
+        expect(thr_create(race, (void*)i) >= 0);
+    
+    getchar();
+    expect(set_cursor_pos(24,0));
+    
+    task_vanish(0);
+}