initial commit

36 files changed, 5889 insertions, 0 deletions

diff --git a/kern/asm_instr.S b/kern/asm_instr.S
new file mode 100644
index 0000000..e096302
--- /dev/null
+++ b/kern/asm_instr.S
@@ -0,0 +1,22 @@
+/** @file asm_instr.c
+ *
+ *  @brief assembly stubs.
+ *
+ *  @author Hanjie Wu (hanjiew)
+ *  @bug No functional bugs
+ */
+
+.text
+
+.global invlpg
+.type invlpg, %function
+invlpg:
+    mov 0x4(%esp), %eax
+    invlpg (%eax)
+    ret
+
+.global hlt
+.type hlt, %function
+hlt:
+    hlt
+    ret /* keep it for other platforms that do not respond to hlt */
diff --git a/kern/common.c b/kern/common.c
new file mode 100644
index 0000000..93edb3d
--- /dev/null
+++ b/kern/common.c
@@ -0,0 +1,472 @@
+/** @file common.c
+ *
+ *  @brief common data structures.
+ *
+ *  @author Hanjie Wu (hanjiew)
+ *  @bug No functional bugs
+ */
+#include <common.h>
+
+#include <string.h>
+
+void queue_insert_head(queue_t** queue, queue_t* t) {
+    if (*queue == NULL) {
+        t->next = t->prev = t;
+    } else {
+        t->next = *queue;
+        t->prev = (*queue)->prev;
+        (*queue)->prev->next = t;
+        (*queue)->prev = t;
+    }
+    *queue = t;
+}
+
+void queue_insert_tail(queue_t** queue, queue_t* t) {
+    if (*queue == NULL) {
+        t->next = t->prev = t;
+        *queue = t;
+    } else {
+        t->next = *queue;
+        t->prev = (*queue)->prev;
+        (*queue)->prev->next = t;
+        (*queue)->prev = t;
+    }
+}
+
+queue_t* queue_remove_head(queue_t** queue) {
+    queue_t* t = *queue;
+    if (t->next == t) {
+        *queue = NULL;
+    } else {
+        t->next->prev = t->prev;
+        t->prev->next = t->next;
+        *queue = t->next;
+    }
+    return t;
+}
+
+queue_t* queue_remove_tail(queue_t** queue) {
+    queue_t* t = (*queue)->prev;
+    if (t->next == t) {
+        *queue = NULL;
+    } else {
+        t->next->prev = t->prev;
+        t->prev->next = t->next;
+    }
+    return t;
+}
+
+void queue_detach(queue_t** queue, queue_t* t) {
+    if (*queue == t) {
+        if (t->next == t) {
+            *queue = NULL;
+        } else {
+            *queue = t->next;
+        }
+    }
+    t->next->prev = t->prev;
+    t->prev->next = t->next;
+}
+
+int heap_init(heap_t* heap) {
+    return vector_init(heap, sizeof(heap_node_t), INITIAL_HEAP_SIZE);
+}
+
+int heap_insert(heap_t* heap, heap_node_t* node) {
+    if (vector_push(heap, node) != 0) {
+        return -1;
+    }
+    int cur = vector_size(heap) - 1;
+    while (cur != 0) {
+        int parent = ((cur - 1) >> 1);
+        heap_node_t* cn = (heap_node_t*)vector_at(heap, cur);
+        heap_node_t* pn = (heap_node_t*)vector_at(heap, parent);
+        if (cn->key >= pn->key) {
+            break;
+        }
+        heap_node_t t = *pn;
+        *pn = *cn;
+        *cn = t;
+        cur = parent;
+    }
+    return 0;
+}
+
+heap_node_t* heap_peak(heap_t* heap) {
+    return (vector_size(heap) == 0 ? NULL : (heap_node_t*)vector_at(heap, 0));
+}
+
+void heap_pop(heap_t* heap) {
+    int size = vector_size(heap);
+    if (size == 0) {
+        return;
+    }
+    *(heap_node_t*)vector_at(heap, 0) =
+        *(heap_node_t*)vector_at(heap, size - 1);
+    vector_pop(heap);
+    size--;
+    int cur = 0;
+    while (1) {
+        int lc = cur * 2 + 1;
+        int rc = lc + 1;
+        int small = cur;
+        heap_node_t* cn = (heap_node_t*)vector_at(heap, cur);
+        heap_node_t *ln, *rn, *sn = cn;
+        if (lc < size) {
+            ln = (heap_node_t*)vector_at(heap, lc);
+            if (ln->key < sn->key) {
+                small = lc;
+                sn = ln;
+            }
+        }
+        if (rc < size) {
+            rn = (heap_node_t*)vector_at(heap, rc);
+            if (rn->key < sn->key) {
+                small = rc;
+                sn = rn;
+            }
+        }
+        if (small == cur) {
+            break;
+        }
+        if (small == lc) {
+            heap_node_t t = *ln;
+            *ln = *cn;
+            *cn = t;
+            cur = lc;
+        } else {
+            heap_node_t t = *rn;
+            *rn = *cn;
+            *cn = t;
+            cur = rc;
+        }
+    }
+}
+
+rb_t rb_nil = {
+    .color = RB_BLACK,
+    .parent = &rb_nil,
+    .left = &rb_nil,
+    .right = &rb_nil,
+};
+
+rb_t* rb_find(rb_t* root, int key) {
+    rb_t* p = root;
+    while (p != &rb_nil) {
+        if (key == p->key) {
+            return p;
+        }
+        p = (key > p->key) ? p->right : p->left;
+    }
+    return NULL;
+}
+
+/**
+ * @brief left rotate on a node
+ * @param root rbtree root
+ * @param node node
+ */
+static void rb_rotate_left(rb_t** root, rb_t* node) {
+    rb_t* r = node->right;
+    node->right = r->left;
+    if (r->left != &rb_nil) {
+        r->left->parent = node;
+    }
+    r->parent = node->parent;
+    if (node->parent == &rb_nil) {
+        *root = r;
+    } else if (node == node->parent->left) {
+        node->parent->left = r;
+    } else {
+        node->parent->right = r;
+    }
+    r->left = node;
+    node->parent = r;
+}
+
+/**
+ * @brief right rotate on a node
+ * @param root rbtree root
+ * @param node node
+ */
+static void rb_rotate_right(rb_t** root, rb_t* node) {
+    rb_t* l = node->left;
+    node->left = l->right;
+    if (l->right != &rb_nil) {
+        l->right->parent = node;
+    }
+    l->parent = node->parent;
+    if (node->parent == &rb_nil) {
+        *root = l;
+    } else if (node == node->parent->left) {
+        node->parent->left = l;
+    } else {
+        node->parent->right = l;
+    }
+    l->right = node;
+    node->parent = l;
+}
+
+/**
+ * @brief fixup after insertion
+ * @param root rbtree root
+ * @param node node
+ */
+static void rb_fixup(rb_t** root, rb_t* node) {
+    while (node->parent->color == RB_RED) {
+        rb_t* grand = node->parent->parent;
+        if (node->parent == grand->left) {
+            rb_t* uncle = grand->right;
+            if (uncle->color == RB_RED) {
+                node->parent->color = RB_BLACK;
+                uncle->color = RB_BLACK;
+                node->parent->parent->color = RB_RED;
+                node = node->parent->parent;
+            } else {
+                if (node == node->parent->right) {
+                    node = node->parent;
+                    rb_rotate_left(root, node);
+                }
+                node->parent->color = RB_BLACK;
+                grand->color = RB_RED;
+                rb_rotate_right(root, grand);
+            }
+        } else {
+            rb_t* uncle = grand->left;
+            if (uncle->color == RB_RED) {
+                node->parent->color = RB_BLACK;
+                uncle->color = RB_BLACK;
+                node->parent->parent->color = RB_RED;
+                node = node->parent->parent;
+            } else {
+                if (node == node->parent->left) {
+                    node = node->parent;
+                    rb_rotate_right(root, node);
+                }
+                node->parent->color = RB_BLACK;
+                grand->color = RB_RED;
+                rb_rotate_left(root, grand);
+            }
+        }
+    }
+    (*root)->color = RB_BLACK;
+}
+
+void rb_insert(rb_t** root, rb_t* node) {
+    rb_t *p = *root, *parent = &rb_nil;
+    while (p != &rb_nil) {
+        parent = p;
+        p = (node->key > p->key) ? p->right : p->left;
+    }
+    node->parent = parent;
+    if (parent == &rb_nil) {
+        *root = node;
+    } else if (node->key > parent->key) {
+        parent->right = node;
+    } else {
+        parent->left = node;
+    }
+    node->left = node->right = &rb_nil;
+    node->color = RB_RED;
+    rb_fixup(root, node);
+}
+
+/**
+ * @brief move v to u's position
+ * @param root rbtree root
+ * @param u u
+ * @param v v
+ */
+static void rb_transplant(rb_t** root, rb_t* u, rb_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;
+}
+
+rb_t* rb_min(rb_t* root) {
+    while (root->left != &rb_nil) {
+        root = root->left;
+    }
+    return root;
+}
+
+rb_t* rb_next(rb_t* node) {
+    if (node->right != &rb_nil) {
+        return rb_min(node->right);
+    }
+    rb_t* parent = node->parent;
+    while (parent != &rb_nil && node == parent->right) {
+        node = parent;
+        parent = parent->parent;
+    }
+    return parent;
+}
+
+/**
+ * @brief fixup after deletion
+ * @param root rbtree root
+ * @param node node
+ */
+static void rb_delete_fixup(rb_t** root, rb_t* node) {
+    while (node != *root && node->color == RB_BLACK) {
+        if (node == node->parent->left) {
+            rb_t* r = node->parent->right;
+            if (r->color == RB_RED) {
+                r->color = RB_BLACK;
+                node->parent->color = RB_RED;
+                rb_rotate_left(root, node->parent);
+                r = node->parent->right;
+            }
+            if (r->left->color == RB_BLACK && r->right->color == RB_BLACK) {
+                r->color = RB_RED;
+                node = node->parent;
+            } else {
+                if (r->right->color == RB_BLACK) {
+                    r->left->color = RB_BLACK;
+                    r->color = RB_RED;
+                    rb_rotate_right(root, r);
+                    r = node->parent->right;
+                }
+                r->color = node->parent->color;
+                node->parent->color = RB_BLACK;
+                r->right->color = RB_BLACK;
+                rb_rotate_left(root, node->parent);
+                node = *root;
+            }
+        } else {
+            rb_t* l = node->parent->left;
+            if (l->color == RB_RED) {
+                l->color = RB_BLACK;
+                node->parent->color = RB_RED;
+                rb_rotate_right(root, node->parent);
+                l = node->parent->left;
+            }
+            if (l->right->color == RB_BLACK && l->left->color == RB_BLACK) {
+                l->color = RB_RED;
+                node = node->parent;
+            } else {
+                if (l->left->color == RB_BLACK) {
+                    l->right->color = RB_BLACK;
+                    l->color = RB_RED;
+                    rb_rotate_left(root, l);
+                    l = node->parent->left;
+                }
+                l->color = node->parent->color;
+                node->parent->color = RB_BLACK;
+                l->left->color = RB_BLACK;
+                rb_rotate_right(root, node->parent);
+                node = *root;
+            }
+        }
+    }
+    node->color = RB_BLACK;
+}
+
+void rb_delete(rb_t** root, rb_t* node) {
+    rb_t *x, *y = node;
+    int orig_color = y->color;
+    if (node->left == &rb_nil) {
+        x = node->right;
+        rb_transplant(root, node, x);
+    } else if (node->right == &rb_nil) {
+        x = node->left;
+        rb_transplant(root, node, x);
+    } else {
+        y = rb_min(node->right);
+        orig_color = y->color;
+        x = y->right;
+        if (y->parent == node) {
+            x->parent = y;
+        } else {
+            rb_transplant(root, y, y->right);
+            y->right = node->right;
+            y->right->parent = y;
+        }
+        rb_transplant(root, node, y);
+        y->left = node->left;
+        y->left->parent = y;
+        y->color = node->color;
+    }
+    if (orig_color == RB_BLACK) {
+        rb_delete_fixup(root, x);
+    }
+}
+
+/** do not shink small vectors as this do not bring big benefit */
+#define VECTOR_MINIMUM_SIZE 8
+/** don't shink too fast so we divide by 3 */
+#define VECTOR_SHINK_RATIO 3
+
+int vector_init(vector_t* v, int elem_size, int init_size) {
+    v->elem_size = elem_size;
+    v->size = init_size;
+    v->array = (char*)smalloc(init_size * elem_size);
+    v->current = 0;
+    return (v->array == NULL ? -1 : 0);
+}
+
+int vector_size(vector_t* v) {
+    return v->current;
+}
+
+int vector_push(vector_t* v, void* elem) {
+    if (v->current == v->size) {
+        char* result = (char*)smalloc(v->size * v->elem_size * 2);
+        if (result == NULL) {
+            return -1;
+        }
+        memcpy(result, v->array, v->current * v->elem_size);
+        sfree(v->array, v->size * v->elem_size);
+        v->size <<= 1;
+        v->array = result;
+    }
+    memcpy(v->array + v->current * v->elem_size, elem, v->elem_size);
+    v->current++;
+    return 0;
+}
+
+/**
+ * @brief check if a vector should shrink
+ * @param v vector
+ */
+static void vector_try_shink(vector_t* v) {
+    if (v->current < v->size / VECTOR_SHINK_RATIO) {
+        if ((v->size / 2) < VECTOR_MINIMUM_SIZE) {
+            return;
+        }
+        char* result = (char*)smalloc((v->size / 2) * v->elem_size);
+        if (result == NULL) {
+            return;
+        }
+        memcpy(result, v->array, v->current * v->elem_size);
+        sfree(v->array, v->size * v->elem_size);
+        v->size >>= 1;
+        v->array = result;
+    }
+}
+
+void vector_pop(vector_t* v) {
+    v->current--;
+    vector_try_shink(v);
+}
+
+void vector_remove(vector_t* v, int index) {
+    memmove(v->array + index * v->elem_size,
+            v->array + (index + 1) * v->elem_size,
+            (v->current - index - 1) * v->elem_size);
+    v->current--;
+    vector_try_shink(v);
+}
+
+void* vector_at(vector_t* v, int index) {
+    return (void*)(v->array + index * v->elem_size);
+}
+
+void vector_free(vector_t* v) {
+    sfree(v->array, v->size * v->elem_size);
+}
diff --git a/kern/console.c b/kern/console.c
new file mode 100644
index 0000000..2b25fcc
--- /dev/null
+++ b/kern/console.c
@@ -0,0 +1,212 @@
+/** @file console.c
+ *
+ *  @brief Console driver implementation.
+ *
+ *  @author Hanjie Wu (hanjiew)
+ *  @bug No functional bugs
+ */
+
+#include <stdbool.h>
+#include <stddef.h>
+#include <stdint.h>
+#include <string.h>
+
+#include <x86/asm.h>
+#include <x86/video_defines.h>
+
+#include <console.h>
+
+/** how many bits in a x86 byte */
+#define NUM_OF_BITS_X86 8
+/** Mask bits for a 8-bit byte */
+#define BYTE_MASK_X86 0xFF
+
+/** index of the register to start displaying cursor */
+#define CRTC_CURSOR_START 10
+/** bit to start displaying cursor */
+#define CURSOR_ENABLE_BIT 0x20
+
+/**
+ * Someone is not satisfied with the type name char_t so we use this
+ * to reperesent a char on screen so that nobody will mistake it with 'char'
+ */
+typedef struct a_char_on_screen_s {
+    uint8_t ch;    /** char */
+    uint8_t color; /** color */
+} a_char_on_screen_t;
+
+/** pointer to the viedo memory at B800h */
+a_char_on_screen_t (*console_mem)[CONSOLE_WIDTH] =
+    (a_char_on_screen_t(*)[CONSOLE_WIDTH])CONSOLE_MEM_BASE;
+
+/** the char used to produce blank */
+#define BLANK_CH ' '
+/** initial color of the cursor */
+#define DEFAULT_COLOR (FGND_WHITE | BGND_BLACK)
+
+/** x position of the cursor */
+static int cur_x = 0;
+/** y position of the cursor */
+static int cur_y = 0;
+/** current color of the cursor */
+static char cur_color = DEFAULT_COLOR;
+/** should the cursor be displayed? */
+static int cur_shown = true;
+
+/** mutex for console operations */
+mutex_t console_lock = MUTEX_INIT;
+
+/**
+ * @brief Move the cursor to a position. Position is checked before calling this
+ * function
+ * @param x x
+ * @param y y
+ */
+static void move_cursor(int x, int y) {
+    cur_x = x;
+    cur_y = y;
+    int pos = y * CONSOLE_WIDTH + x;
+    outb(CRTC_IDX_REG, CRTC_CURSOR_LSB_IDX);
+    outb(CRTC_DATA_REG, pos & BYTE_MASK_X86);
+    outb(CRTC_IDX_REG, CRTC_CURSOR_MSB_IDX);
+    outb(CRTC_DATA_REG, pos >> NUM_OF_BITS_X86);
+}
+
+/**
+ * @brief Scroll the console by one line and clean the last line
+ */
+static void scroll_page() {
+    /* move all but last line forward */
+    memmove(console_mem[0], console_mem[1],
+            sizeof(a_char_on_screen_t) * CONSOLE_WIDTH * (CONSOLE_HEIGHT - 1));
+    int i;
+    for (i = 0; i < CONSOLE_WIDTH; i++) {
+        console_mem[CONSOLE_HEIGHT - 1][i] =
+            (a_char_on_screen_t){BLANK_CH, cur_color};
+    }
+}
+
+int putbyte(char ch) {
+    if (ch == '\n') {
+        if (cur_y < CONSOLE_HEIGHT - 1) {
+            move_cursor(0, cur_y + 1);
+        } else {
+            scroll_page();
+            move_cursor(0, cur_y);
+        }
+        return ch;
+    }
+    if (ch == '\r') {
+        move_cursor(0, cur_y);
+        return ch;
+    }
+    if (ch == '\b') {
+        if (cur_x > 0) {
+            move_cursor(cur_x - 1, cur_y);
+
+        } else if (cur_y > 0) {
+            move_cursor(CONSOLE_WIDTH - 1, cur_y - 1);
+        }
+        console_mem[cur_y][cur_x] = (a_char_on_screen_t){BLANK_CH, cur_color};
+        return ch;
+    }
+    /* save the position where we should show the char */
+    int prev_x = cur_x, prev_y = cur_y;
+    if (cur_x < CONSOLE_WIDTH - 1) {
+        /* move forward */
+        move_cursor(cur_x + 1, cur_y);
+    } else if (cur_y < CONSOLE_HEIGHT - 1) {
+        /* go to next line */
+        move_cursor(0, cur_y + 1);
+    } else {
+        /* scroll and go to beginning of the line */
+        scroll_page();
+        move_cursor(0, cur_y);
+        prev_y -= 1;
+    }
+    console_mem[prev_y][prev_x] = (a_char_on_screen_t){ch, cur_color};
+    return ch;
+}
+
+void putbytes(const char* s, int len) {
+    if (s == NULL || len <= 0) {
+        return;
+    }
+    int i;
+    for (i = 0; i < len; i++) {
+        putbyte(s[i]);
+    }
+}
+
+void draw_char(int row, int col, int ch, int color) {
+    if (row >= CONSOLE_HEIGHT || row < 0) {
+        return;
+    }
+    if (col >= CONSOLE_WIDTH || col < 0) {
+        return;
+    }
+    if (color > BYTE_MASK_X86 || color < 0) {
+        return;
+    }
+    console_mem[row][col] = (a_char_on_screen_t){ch, color};
+}
+
+int set_term_color(int color) {
+    if (color > BYTE_MASK_X86 || color < 0) {
+        return -1;
+    }
+    cur_color = (char)color;
+    return 0;
+}
+
+void get_term_color(int* color) {
+    *color = cur_color;
+}
+
+int set_cursor(int row, int col) {
+    if (row >= CONSOLE_HEIGHT || row < 0) {
+        return -1;
+    }
+    if (col >= CONSOLE_WIDTH || col < 0) {
+        return -1;
+    }
+    move_cursor(col, row);
+    return 0;
+}
+
+void get_cursor(int* row, int* col) {
+    *row = cur_y;
+    *col = cur_x;
+}
+
+void hide_cursor(void) {
+    cur_shown = 0;
+    outb(CRTC_IDX_REG, CRTC_CURSOR_START);
+    outb(CRTC_DATA_REG, inb(CRTC_DATA_REG) | CURSOR_ENABLE_BIT);
+}
+
+void show_cursor(void) {
+    cur_shown = 1;
+    outb(CRTC_IDX_REG, CRTC_CURSOR_START);
+    outb(CRTC_DATA_REG, inb(CRTC_DATA_REG) & ~CURSOR_ENABLE_BIT);
+}
+
+void clear_console(void) {
+    move_cursor(0, 0);
+    int i, j;
+    for (i = 0; i < CONSOLE_HEIGHT - 1; i++) {
+        for (j = 0; j < CONSOLE_WIDTH - 1; j++) {
+            console_mem[i][j] = (a_char_on_screen_t){BLANK_CH, cur_color};
+        }
+    }
+}
+
+char get_char(int row, int col) {
+    if (row >= CONSOLE_HEIGHT || row < 0) {
+        return BLANK_CH;
+    }
+    if (col >= CONSOLE_WIDTH || col < 0) {
+        return BLANK_CH;
+    }
+    return console_mem[row][col].ch;
+}
diff --git a/kern/inc/asm_instr.h b/kern/inc/asm_instr.h
new file mode 100644
index 0000000..f323b81
--- /dev/null
+++ b/kern/inc/asm_instr.h
@@ -0,0 +1,25 @@
+/** @file asm_instr.h
+ *
+ *  @brief assembly stubs.
+ *
+ *  @author Hanjie Wu (hanjiew)
+ *  @bug No functional bugs
+ */
+
+#ifndef _ASM_INSTR_H_
+#define _ASM_INSTR_H_
+
+#include <paging.h>
+
+/**
+ * @brief runs invlpg on an address
+ * @param va addr to invalidate
+ */
+void invlpg(va_t va);
+
+/**
+ * @brief runs hlt
+ */
+void hlt();
+
+#endif
diff --git a/kern/inc/common.h b/kern/inc/common.h
new file mode 100644
index 0000000..dad473b
--- /dev/null
+++ b/kern/inc/common.h
@@ -0,0 +1,228 @@
+/** @file common.h
+ *
+ *  @brief common data structure
+ *
+ *  @author Hanjie Wu (hanjiew)
+ *  @bug No functional bugs
+ */
+
+#ifndef _COMMON_H_
+#define _COMMON_H_
+
+#include <stdlib.h>
+
+/**
+ * a queue node
+ */
+typedef struct queue_s {
+    struct queue_s* next;
+    struct queue_s* prev;
+} queue_t;
+
+/**
+ * @brief insert a node to the head of a queue
+ * @param queue queue
+ * @param t the node
+ */
+void queue_insert_head(queue_t** queue, queue_t* t);
+
+/**
+ * @brief insert a node to the tail of a queue
+ * @param queue queue
+ * @param t the node
+ */
+void queue_insert_tail(queue_t** queue, queue_t* t);
+
+/**
+ * @brief remove a node from the head of a queue
+ * @param queue queue
+ * @return the node removed
+ */
+queue_t* queue_remove_head(queue_t** queue);
+
+/**
+ * @brief remove a node from the tail of a queue
+ * @param queue queue
+ * @return the node removed
+ */
+queue_t* queue_remove_tail(queue_t** queue);
+
+/**
+ * @brief detach a node from the a queue
+ * @param queue queue
+ * @param t the node to be detached
+ */
+void queue_detach(queue_t** queue, queue_t* t);
+
+/** get the enclose object of a queue node */
+#define queue_data(queue, type, member) \
+    (type*)((char*)queue - offsetof(type, member))
+
+/**
+ * a rbtree node
+ */
+typedef struct rb_s {
+    int key;
+    int color;
+    struct rb_s* parent;
+    struct rb_s* left;
+    struct rb_s* right;
+} rb_t;
+
+/** this color can have childs of any color */
+#define RB_BLACK 0
+/** this color can only have childs of the color mentioned above */
+#define RB_RED 1
+
+/** used to represent NULL in rbtrees */
+extern rb_t rb_nil;
+
+/**
+ * @brief find a node with key
+ * @param root rbtree root
+ * @param key key to find
+ * @return rb_nil if not found, else the node
+ */
+rb_t* rb_find(rb_t* root, int key);
+
+/**
+ * @brief insert a node to rbtree
+ * @param root rbtree root
+ * @param node the node to insert
+ */
+void rb_insert(rb_t** root, rb_t* node);
+
+/**
+ * @brief delete a node from rbtree
+ * @param root rbtree root
+ * @param node the node to delete
+ */
+void rb_delete(rb_t** root, rb_t* node);
+
+/**
+ * @brief find the node with minimum key in rbtree
+ * @param root rbtree root
+ * @return rb_nil if rbtree is empty, otherwise the node
+ */
+rb_t* rb_min(rb_t* root);
+
+/**
+ * @brief find the node with the samllest key which is greater than node's key
+ * @param root rbtree root
+ * @param node the node to compare
+ * @return rb_nil if no such node exist, otherwise the node
+ */
+rb_t* rb_next(rb_t* node);
+
+/** get the enclose object of a rbtree node */
+#define rb_data(rb, type, member) (type*)((char*)rb - offsetof(type, member))
+
+/**
+ * a vector
+ */
+typedef struct vector_s {
+    int current;
+    int size;
+    int elem_size;
+    char* array;
+} vector_t;
+
+/**
+ * @brief initializa a vector
+ * @param v the vector
+ * @param elem_size size of element
+ * @param init_size initial size of vector
+ * @return -1 on failure, 0 on success
+ */
+int vector_init(vector_t* v, int elem_size, int init_size);
+
+/**
+ * @brief get the size of a vector
+ * @param v the vector
+ * @return size
+ */
+int vector_size(vector_t* v);
+
+/**
+ * @brief push an element to the back of v
+ * @param v vector
+ * @param elem element
+ * @return -1 on failure, 0 on success
+ */
+int vector_push(vector_t* v, void* elem);
+
+/**
+ * @brief remove an element from the back of v
+ * @param v vector
+ */
+void vector_pop(vector_t* v);
+
+/**
+ * @brief remove an element at index index
+ * @param v vector
+ * @param index index
+ */
+void vector_remove(vector_t* v, int index);
+
+/**
+ * @brief return a pointer to the element at index in v
+ * @param v vector
+ * @param index index
+ * @return the element
+ */
+void* vector_at(vector_t* v, int index);
+
+/**
+ * @brief free a vector's resource
+ * @param v vector
+ */
+void vector_free(vector_t* v);
+
+/**
+ * a node in heap
+ */
+typedef struct heap_node_s {
+    int key;
+    void* value;
+} heap_node_t;
+
+/**
+ * a minimum heap
+ */
+typedef vector_t heap_t;
+
+/**
+ * heap is only used for timer and we choose this size because 8 is a common
+ * number in computer science and no other size make more sense than this one
+ */
+#define INITIAL_HEAP_SIZE (8)
+
+/**
+ * @brief initializa a heap
+ * @param heap the heap
+ * @return -1 on failure, 0 on success
+ */
+int heap_init(heap_t* heap);
+
+/**
+ * @brief insert a node into heap
+ * @param heap the heap
+ * @param node the node
+ * @return -1 on failure, 0 on success
+ */
+int heap_insert(heap_t* heap, heap_node_t* node);
+
+/**
+ * @brief peak the top of a heap
+ * @param heap the heap
+ * @return top node of the heap or NULL if heap is empty
+ */
+heap_node_t* heap_peak(heap_t* heap);
+
+/**
+ * @brief remove the top node from heap
+ * @param heap the heap
+ */
+void heap_pop(heap_t* heap);
+
+#endif
diff --git a/kern/inc/console.h b/kern/inc/console.h
new file mode 100644
index 0000000..a3649de
--- /dev/null
+++ b/kern/inc/console.h
@@ -0,0 +1,162 @@
+/*
+ *
+ *  #     #
+ *  ##    #   ####    #####     #     ####   ######
+ *  # #   #  #    #     #       #    #    #  #
+ *  #  #  #  #    #     #       #    #       #####
+ *  #   # #  #    #     #       #    #       #
+ *  #    ##  #    #     #       #    #    #  #
+ *  #     #   ####      #       #     ####   ######
+ *
+ * Now that it's P3 instead of P1 you are allowed
+ * to edit this file if it suits you.
+ *
+ * Please delete this notice.
+ *
+ */
+
+/** @file console.h
+ *
+ *  @brief console functions.
+ *
+ *  @author Hanjie Wu (hanjiew)
+ *  @bug No functional bugs
+ */
+
+#ifndef _CONSOLE_H
+#define _CONSOLE_H
+
+#include <video_defines.h>
+
+#include <sync.h>
+
+/** mutex for console operations */
+extern mutex_t console_lock;
+
+/** @brief Prints character ch at the current location
+ *         of the cursor.
+ *
+ *  If the character is a newline ('\n'), the cursor is
+ *  be moved to the beginning of the next line (scrolling if necessary).  If
+ *  the character is a carriage return ('\r'), the cursor
+ *  is immediately reset to the beginning of the current
+ *  line, causing any future output to overwrite any existing
+ *  output on the line.  If backsapce ('\b') is encountered,
+ *  the previous character is erased.  See the main console.c description
+ *  for more backspace behavior.
+ *
+ *  @param ch the character to print
+ *  @return The input character
+ */
+int putbyte(char ch);
+
+/** @brief Prints the string s, starting at the current
+ *         location of the cursor.
+ *
+ *  If the string is longer than the current line, the
+ *  string fills up the current line and then
+ *  continues on the next line. If the string exceeds
+ *  available space on the entire console, the screen
+ *  scrolls up one line, and then the string
+ *  continues on the new line.  If '\n', '\r', and '\b' are
+ *  encountered within the string, they are handled
+ *  as per putbyte. If len is not a positive integer or s
+ *  is null, the function has no effect.
+ *
+ *  @param s The string to be printed.
+ *  @param len The length of the string s.
+ *  @return Void.
+ */
+void putbytes(const char* s, int len);
+
+/** @brief Changes the foreground and background color
+ *         of future characters printed on the console.
+ *
+ *  If the color code is invalid, the function has no effect.
+ *
+ *  @param color The new color code.
+ *  @return 0 on success or integer error code less than 0 if
+ *          color code is invalid.
+ */
+int set_term_color(int color);
+
+/** @brief Writes the current foreground and background
+ *         color of characters printed on the console
+ *         into the argument color.
+ *  @param color The address to which the current color
+ *         information will be written.
+ *  @return Void.
+ */
+void get_term_color(int* color);
+
+/** @brief Sets the position of the cursor to the
+ *         position (row, col).
+ *
+ *  Subsequent calls to putbytes should cause the console
+ *  output to begin at the new position. If the cursor is
+ *  currently hidden, a call to set_cursor() does not show
+ *  the cursor.
+ *
+ *  @param row The new row for the cursor.
+ *  @param col The new column for the cursor.
+ *  @return 0 on success or integer error code less than 0 if
+ *          cursor location is invalid.
+ */
+int set_cursor(int row, int col);
+
+/** @brief Writes the current position of the cursor
+ *         into the arguments row and col.
+ *  @param row The address to which the current cursor
+ *         row will be written.
+ *  @param col The address to which the current cursor
+ *         column will be written.
+ *  @return Void.
+ */
+void get_cursor(int* row, int* col);
+
+/** @brief Hides the cursor.
+ *
+ *  Subsequent calls to putbytes do not cause the
+ *  cursor to show again.
+ *
+ *  @return Void.
+ */
+void hide_cursor(void);
+
+/** @brief Shows the cursor.
+ *
+ *  If the cursor is already shown, the function has no effect.
+ *
+ *  @return Void.
+ */
+void show_cursor(void);
+
+/** @brief Clears the entire console.
+ *
+ * The cursor is reset to the first row and column
+ *
+ *  @return Void.
+ */
+void clear_console(void);
+
+/** @brief Prints character ch with the specified color
+ *         at position (row, col).
+ *
+ *  If any argument is invalid, the function has no effect.
+ *
+ *  @param row The row in which to display the character.
+ *  @param col The column in which to display the character.
+ *  @param ch The character to display.
+ *  @param color The color to use to display the character.
+ *  @return Void.
+ */
+void draw_char(int row, int col, int ch, int color);
+
+/** @brief Returns the character displayed at position (row, col).
+ *  @param row Row of the character.
+ *  @param col Column of the character.
+ *  @return The character at (row, col).
+ */
+char get_char(int row, int col);
+
+#endif /* _CONSOLE_H */
diff --git a/kern/inc/interrupt.h b/kern/inc/interrupt.h
new file mode 100644
index 0000000..7c15ccd
--- /dev/null
+++ b/kern/inc/interrupt.h
@@ -0,0 +1,27 @@
+/** @file interrupt.h
+ *
+ *  @brief idt initializer.
+ *
+ *  @author Hanjie Wu (hanjiew)
+ *  @bug No functional bugs
+ */
+
+#ifndef _INTERRUPT_H_
+#define _INTERRUPT_H_
+
+/**
+ * IRQ # of timer
+ */
+#define TIMER_IRQ 0
+
+/**
+ * IRQ # of keyboard
+ */
+#define KBD_IRQ 1
+
+/**
+ * @brief initialize idt
+ */
+void idt_init();
+
+#endif
diff --git a/kern/inc/kbd.h b/kern/inc/kbd.h
new file mode 100644
index 0000000..a7350b6
--- /dev/null
+++ b/kern/inc/kbd.h
@@ -0,0 +1,30 @@
+/** @file kbd.h
+ *
+ *  @brief keyboard functions.
+ *
+ *  @author Hanjie Wu (hanjiew)
+ *  @bug No functional bugs
+ */
+
+#ifndef _KBD_H_
+#define _KBD_H_
+
+#include <common.h>
+#include <sched.h>
+#include <sync.h>
+
+/**
+ * @brief read a line to userspace
+ * @param len max length to read
+ * @param buf buffer
+ * @return size on success, -1 on failure
+ */
+int do_readline(int len, va_t buf);
+
+/**
+ * @brief read a char
+ * @return char read
+ */
+int do_getchar();
+
+#endif
diff --git a/kern/inc/loader.h b/kern/inc/loader.h
new file mode 100644
index 0000000..504a29a
--- /dev/null
+++ b/kern/inc/loader.h
@@ -0,0 +1,46 @@
+/* The 15-410 kernel project
+ *
+ *     loader.h
+ *
+ * Structure definitions, #defines, and function prototypes
+ * for the user process loader.
+ */
+
+#ifndef _LOADER_H
+#define _LOADER_H
+
+#include <exec2obj.h>
+
+/* --- Prototypes --- */
+
+/**
+ * @brief read size bytes from offset of filename to buf
+ * @param filename filename
+ * @param offser offset in file
+ * @param size size to read
+ * @param buf buffer
+ * @return returns the number of bytes copied on succes; -1 on failure
+ */
+int getbytes(const char* filename, int offset, int size, char* buf);
+
+/** shorter name for file entry */
+typedef const exec2obj_userapp_TOC_entry file_t;
+
+/**
+ * @brief read size bytes from offset of f to buf
+ * @param f file entry
+ * @param offser offset in file
+ * @param size size to read
+ * @param buf buffer
+ * @return returns the number of bytes copied on succes; -1 on failure
+ */
+int read_file(file_t* f, int offset, int size, char* buf);
+
+/**
+ * @brief find a file entry
+ * @param filename filename
+ * @return the file entry, NULL if not found
+ */
+file_t* find_file(const char* name);
+
+#endif /* _LOADER_H */
diff --git a/kern/inc/mm.h b/kern/inc/mm.h
new file mode 100644
index 0000000..64499d0
--- /dev/null
+++ b/kern/inc/mm.h
@@ -0,0 +1,55 @@
+/** @file mm.h
+ *
+ *  @brief memory management functions.
+ *
+ *  @author Hanjie Wu (hanjiew)
+ *  @bug No functional bugs
+ */
+
+#ifndef _MM_H_
+#define _MM_H_
+
+#include <syscall_int.h>
+
+#include <paging.h>
+#include <sync.h>
+
+/** a invalid physical address when managing user memory */
+#define BAD_PA 0
+
+/** lock for kernel memory allocation */
+extern mutex_t malloc_lock;
+
+/** lock for user memory management */
+extern mutex_t mm_lock;
+
+/**
+ * @brief initialize user memory system
+ */
+void mm_init();
+
+/**
+ * @brief allocate physical pages
+ * @param num_pages number of pages to allocate
+ * @return physical address of pages, or BAD_PA on failure
+ */
+pa_t alloc_user_pages(int num_pages);
+
+/**
+ * @brief free physical pages
+ * @param pa physcial address of pages
+ * @param num_pages number of pages to allocate
+ */
+void free_user_pages(pa_t pa, int num_pages);
+
+/**
+ * @brief map a physical page to kernel memory, the mapping area will be reused
+ * after subsequent map_phys_page() calls
+ * @param pa physcial address of the page
+ * @param old_pa output argument to save old mapped page, can be NULL if no need
+ * to save
+ * @return virtual address of mapped page
+ */
+va_t map_phys_page(pa_t pa, pa_t* old_pa);
+
+#endif
diff --git a/kern/inc/paging.h b/kern/inc/paging.h
new file mode 100644
index 0000000..182f50f
--- /dev/null
+++ b/kern/inc/paging.h
@@ -0,0 +1,155 @@
+/** @file paging.h
+ *
+ *  @brief paging management functions.
+ *
+ *  @author Hanjie Wu (hanjiew)
+ *  @bug No functional bugs
+ */
+
+#ifndef _PAGING_H_
+#define _PAGING_H_
+
+#include <x86/page.h>
+
+/* SOMEONE SUGGESTED THAT I SHOULD USE UINTPTR_T FOR PORTABILITY BUT I DON'T SEE
+ * ANY USE OF IT IN ANY PROVIDED CODE AND THIS COURSE HAVE ALREADY SAY WE ARE
+ * TARGETING X86 ARCHTECTURE SO I JUST USE A 'NON-PORTABLE' INT TYPE */
+
+/** an entry in page table */
+typedef unsigned long pte_t;
+/** an entry in page directory */
+typedef unsigned long pde_t;
+
+/** virtual address */
+typedef unsigned long va_t;
+
+/** physical address */
+typedef unsigned long pa_t;
+
+/** size of memory */
+typedef unsigned long va_size_t;
+
+/** a register */
+typedef unsigned int reg_t;
+
+#ifndef PAGE_OFFSET_MASK
+/** mask of page offset bits */
+#define PAGE_OFFSET_MASK (PAGE_SIZE - 1)
+#endif
+
+#ifndef PAGE_BASE_MASK
+/** mask of page base bits */
+#define PAGE_BASE_MASK (~PAGE_OFFSET_MASK)
+#endif
+
+/** index of entry in page directory where user memory starts */
+#define USER_PD_START (USER_MEM_START / PAGE_SIZE / NUM_PAGE_ENTRY)
+
+/** means a page is present */
+#define PTE_PRESENT 1
+/** means a page is writeable */
+#define PTE_RW 1
+/** means a page is not writeable */
+#define PTE_RO 0
+/** means a page can be accessed in ring 3 */
+#define PTE_USER 1
+/** means a page can only be accessed in ring 0 */
+#define PTE_SUPERVISOR 0
+#define PTE_PCD 1
+/** means a page's TLB entry should not be flushed on switching cr3 */
+#define PTE_G 1
+
+/** P bit's position */
+#define PTE_P_SHIFT 0
+/** RW/RO bit's position */
+#define PTE_RW_SHIFT 1
+/** USER/SUPERVISOR bit's position */
+#define PTE_US_SHIFT 2
+/** PCD bit's position */
+#define PTE_PCD_SHIFT 4
+/** G bit's position */
+#define PTE_G_SHIFT 8
+
+/** an invalid page directory entry */
+#define BAD_PDE ((pde_t)0)
+/** an invalid page table entry */
+#define BAD_PTE ((pte_t)0)
+
+/**
+ * @brief create a page table entry
+ * @param base address of the page
+ * @param g g bit
+ * @param us user/supervisor bit
+ * @param rw rw/ro bit
+ * @param p present bit
+ * @return the page table entry
+ */
+static inline pte_t make_pte(pa_t base, int g, int us, int rw, int p) {
+    return ((base & PAGE_BASE_MASK) | (g << PTE_G_SHIFT) |
+            (us << PTE_US_SHIFT) | (rw << PTE_RW_SHIFT) | (p << PTE_P_SHIFT));
+}
+
+/**
+ * @brief create a page directory entry
+ * @param base address of the page
+ * @param us user/supervisor bit
+ * @param rw rw/ro bit
+ * @param p present bit
+ * @return the page directory entry
+ */
+static inline pde_t make_pde(pa_t base, int us, int rw, int p) {
+    return ((base & PAGE_BASE_MASK) | (us << PTE_US_SHIFT) |
+            (rw << PTE_RW_SHIFT) | (p << PTE_P_SHIFT));
+}
+
+#ifndef NUM_PAGE_ENTRY
+/** number of entries in a page table */
+#define NUM_PAGE_ENTRY (PAGE_SIZE / sizeof(pte_t))
+#endif
+
+/** size of memory a page table can manage */
+#define PT_SIZE (PAGE_SIZE * NUM_PAGE_ENTRY)
+
+/** page directory type */
+typedef pde_t page_directory_t[PAGE_SIZE / sizeof(pde_t)];
+/** page table type */
+typedef pte_t page_table_t[PAGE_SIZE / sizeof(pde_t)];
+
+/** get page table address from a pde */
+static inline pa_t get_page_table(pde_t pde) {
+    return (pa_t)(pde & PAGE_BASE_MASK);
+}
+
+/** get page base address from a pte */
+static inline pa_t get_page_base(pte_t pte) {
+    return (pa_t)(pte & PAGE_BASE_MASK);
+}
+
+/** get index in page directory of an address */
+static inline int get_pd_index(va_t va) {
+    return va / PAGE_SIZE / NUM_PAGE_ENTRY;
+}
+
+/** get index in page table of an address */
+static inline int get_pt_index(va_t va) {
+    return (va / PAGE_SIZE) % NUM_PAGE_ENTRY;
+}
+
+/** kernel's page directory which directly maps all kernel memory */
+extern page_directory_t* kernel_pd;
+/** area for mapping physical pages */
+extern va_t mapped_phys_pages;
+/** location of the page table entry of the mapping area */
+extern pte_t* mapped_phys_page_ptes;
+
+/**
+ * @brief initialize and enable paging
+ */
+void paging_init();
+
+/**
+ * @brief enable paging
+ */
+void paging_enable();
+
+#endif
diff --git a/kern/inc/sched.h b/kern/inc/sched.h
new file mode 100644
index 0000000..335f648
--- /dev/null
+++ b/kern/inc/sched.h
@@ -0,0 +1,361 @@
+/** @file sched.h
+ *
+ *  @brief scheduling functions.
+ *
+ *  @author Hanjie Wu (hanjiew)
+ *  @bug No functional bugs
+ */
+
+#ifndef _SCHED_H_
+#define _SCHED_H_
+
+#include <common_kern.h>
+#include <elf/elf_410.h>
+
+#include <x86/eflags.h>
+#include <x86/seg.h>
+
+#include <common.h>
+#include <paging.h>
+#include <sync.h>
+
+/** name of idle process */
+#define IDLE_NAME "idle"
+/** name of init process */
+#define INIT_NAME "init"
+
+/** we use fs to find percpu area */
+#define SEGSEL_KERNEL_FS SEGSEL_SPARE0
+/** index of fs in gdt */
+#define SEGSEL_KERNEL_FS_IDX SEGSEL_SPARE0_IDX
+
+/** an allocated memory of a process */
+typedef struct region_s {
+    va_t addr;
+    va_size_t size; /* size in bytes */
+    pa_t paddr;
+    int is_rw;
+} region_t;
+
+/**
+ * default size for kernel thread, as long as kernel does not contain recursion
+ * and do not allocate big local variable, the kernel stack pointer will never
+ * overflow
+ */
+#define K_STACK_SIZE PAGE_SIZE
+
+/** initial eflags, interrupt enabled and IOPL=0 */
+#define DEFAULT_EFLAGS (EFL_IF | EFL_IOPL_RING0 | EFL_RESV1)
+
+/** frame used for kernel context switching */
+typedef struct yield_frame_s {
+    reg_t ebp;
+    reg_t ebx;
+    reg_t eflags;
+    reg_t raddr;
+} yield_frame_t;
+
+/** frame used for syscall and interrupts (not faults) */
+typedef struct stack_frame_s {
+    reg_t gs;
+    reg_t fs;
+    reg_t es;
+    reg_t ds;
+    reg_t edi;
+    reg_t esi;
+    reg_t ebp;
+    reg_t dummy_esp; /* gap of pusha */
+    reg_t ebx;
+    reg_t edx;
+    reg_t ecx;
+    reg_t eax;
+    reg_t eip;
+    reg_t cs;
+    reg_t eflags;
+    reg_t esp; /* not present if interrupted in kernel mode */
+    reg_t ss;  /* not present if interrupted in kernel mode */
+} stack_frame_t;
+
+/** process control block */
+typedef struct process_s {
+    int pid;
+    int exit_value;
+    struct process_s* parent;
+    queue_t sible_link; /* in parent process' child queue */
+
+    mutex_t refcount_lock;
+    int refcount;
+    queue_t* threads;
+
+    int nchilds; /* live and dead but unclaimed childs */
+    queue_t* live_childs;
+    queue_t* dead_childs;
+
+    int nwaiters; /* number of threads calling wait() */
+    mutex_t wait_lock;
+    cv_t wait_cv;
+
+    pa_t cr3;
+    vector_t regions; /* record the vitural memories the user has mapped */
+    mutex_t mm_lock;  /* lock when operating VM */
+} process_t;
+
+/** status of the thread, must lock ready_lock to change it, otherwise may be
+ * changed back to READY by timer interrupt */
+typedef enum thr_stat_e {
+    THREAD_RUNNING,
+    THREAD_READY,
+    THREAD_BLOCKED, /* blocked on a mutex/cv */
+    THREAD_SLEEPING,
+    THREAD_DESCHEDULED,
+    THREAD_DEAD
+} thr_stat_t;
+
+/** thread control block */
+typedef struct thread_s {
+    rb_t rb_node; /* rbtree node, key is tid */
+    thr_stat_t status;
+    spl_t status_lock;
+    queue_t sched_link; /* in ready queue or other queue */
+    int pending_exit;   /* if a task_vanish is pending */
+
+    queue_t process_link; /* in process_t's threads queue */
+
+    process_t* process;
+
+    reg_t esp3;
+    reg_t eip3;
+    reg_t swexn_arg;
+    int df3; /* is a fault is currently being handled by swexn handler */
+
+    reg_t esp0; /* esp to use when switching from ring3 to ring0
+                   (fault/interrupt) */
+    reg_t eip0; /* handler for faults happen in ring0 */
+
+    reg_t kernel_esp; /* saved kernel esp when swapped out */
+    char* stack;      /* kernel stack */
+} thread_t;
+
+/**
+ * @brief get next available tid
+ * @return tid
+ */
+int alloc_tid();
+
+/** initial stack size for user program, 16 pages is a middle size that do not
+ * waste too much and big enough for arguments  */
+#define DEFAULT_STACK_SIZE (65536)
+/** initial stack end for user program, skip the last page as it would cause
+ * round bugs */
+#define DEFAULT_STACK_END (0xffffe000)
+/** inital stack area start */
+#define DEFAULT_STACK_POS (DEFAULT_STACK_END - DEFAULT_STACK_SIZE)
+
+/** maximum arg length for exec(), a middle size */
+#define MAX_ARG_LEN 4096
+/** maximum number of args for exec(), a middle size */
+#define MAX_NUM_ARG 256
+/** maximum total arg length for exec(), save last page for argc, argv, stack_hi
+ * and stack_lo */
+#define MAX_TOTAL_ARG_LEN (DEFAULT_STACK_SIZE - PAGE_SIZE)
+
+/**
+ * @brief create an empty process with one thread and no user memory
+ * @return the thread created or NULL on failure
+ */
+thread_t* create_empty_process();
+
+/**
+ * @brief create a process and load the executable and push the arguments
+ * @param tid tid to use, or 0 if we want to allocate a new one
+ * @param exec name of executable to load
+ * @param argc number of arguments
+ * @param argv array of arguments
+ * @return the thread created or NULL on failure
+ */
+thread_t* create_process(int tid, char* exe, int argc, const char** argv);
+
+/**
+ * @brief destroy a thread which is never run
+ * @param t the thread to destroy
+ */
+void destroy_thread(thread_t* t);
+
+/**
+ * @brief add a memory region to a process
+ * @param p the process
+ * @param addr virtual address
+ * @param n_pages number of pages in this region
+ * @param pa physical address
+ * @param is_rw is this region writeable
+ * @return 0 for success, -1 for failure
+ */
+int add_region(process_t* p, va_t vaddr, int n_pages, pa_t pa, int is_rw);
+
+/**
+ * @brief find the page table for addr, or allocate one if not present
+ * @param p the process
+ * @param addr virtual address
+ * @return physical address of page table or BAD_PA on failure
+ */
+pa_t find_or_create_pt(process_t* p, va_t vaddr);
+
+/** CPU specific varibles */
+typedef struct percpu_s {
+    thread_t* current;           /* current running thread */
+    thread_t* idle;              /* idle thread */
+    thread_t* kthread;           /* original kernel thread */
+    va_t mapped_phys_page;       /* physical page mapping area */
+    pte_t* mapped_phys_page_pte; /* pte for the mapping area */
+} percpu_t;
+
+/**
+ * @brief initialize fs segment's base to percpu structure
+ * @param percpu address of percpu structure
+ */
+void setup_percpu(percpu_t* percpu);
+
+/**
+ * @brief setup the kernel thread's control structure, which needed when
+ * switching to othre processes when startup
+ * @param kthread kernel thread's thread control structure
+ * @param kprocess  kernel thread's process control structure
+ */
+void setup_kth(thread_t* kthread, process_t* kprocess);
+
+/**
+ * @brief get current running thread
+ * @return current running thread
+ */
+thread_t* get_current();
+/**
+ * @brief set current running thread
+ * @param t current running thread
+ */
+void set_current(thread_t* t);
+/**
+ * @brief get idle thread
+ * @return idle thread
+ */
+thread_t* get_idle();
+/**
+ * @brief set idle thread
+ * @param t idle thread
+ */
+void set_idle(thread_t* t);
+/**
+ * @brief get kernel thread
+ * @return kernel thread
+ */
+thread_t* get_kthread();
+/**
+ * @brief set kernel thread
+ * @param t kernel thread
+ */
+void set_kthread(thread_t* t);
+/**
+ * @brief get physical page mapping area
+ * @return physical page mapping area
+ */
+va_t get_mapped_phys_page();
+/**
+ * @brief set physical page mapping area
+ * @param va physical page mapping area
+ */
+void set_mapped_phys_page(va_t va);
+/**
+ * @brief get pte for physical page mapping area
+ * @return pte for physical page mapping area
+ */
+pte_t* get_mapped_phys_page_pte();
+/**
+ * @brief set pte for physical page mapping area
+ * @param pte pte for physical page mapping area
+ */
+void set_mapped_phys_page_pte(pte_t* pte);
+
+/**
+ * @brief swap current thread's process and newt's process, newt must be a new
+ * thread with new process, current thread must be the only thread in a process
+ * @param newt thread to swap
+ */
+void swap_process_inplace(thread_t* newt);
+
+/** init process */
+extern process_t* init_process;
+
+/** lock for ready queue */
+extern spl_t ready_lock;
+/** queue of ready threads */
+extern queue_t* ready;
+
+/** rbtree of all threads */
+extern rb_t* threads;
+/** mutex for rbtree */
+extern mutex_t threads_lock;
+
+/**
+ * @brief insert a thread to the tail of ready queue, must lock ready_lock
+ * before calling this function
+ * @param t thread to insert
+ */
+void insert_ready_tail(thread_t* t);
+
+/**
+ * @brief insert a thread to the head of ready queue, must lock ready_lock
+ * before calling this function
+ * @param t thread to insert
+ */
+void insert_ready_head(thread_t* t);
+
+/**
+ * @brief select next ready thread
+ * @return the thread
+ */
+thread_t* select_next();
+
+/**
+ * @brief save current esp, load t's cr3, esp0 and return t's esp, must disable
+ * interrupt before calling
+ * @param t thread to load
+ * @param esp current esp
+ * @return new esp
+ */
+reg_t save_and_setup_env(thread_t* t, reg_t esp);
+
+/**
+ * @brief let current thread vanish
+ */
+void kill_current();
+
+/**
+ * @brief switch to another stack and cleanup t's thread control block and stack
+ */
+void switch_stack_cleanup(reg_t esp, thread_t* t);
+
+/**
+ * @brief check pending exit request and pop saved user registers and return to
+ * ring 3
+ */
+void return_to_user();
+
+/**
+ * @brief find a thread from rbtree, must lock threads_lock before calling
+ * @param tid tid of thread
+ * @return the thread or NULL if not found
+ */
+thread_t* find_thread(int tid);
+
+/**
+ * @brief add a thread to rbtree, will automatically lock threads_lock
+ * @param t thread to add
+ */
+void add_thread(thread_t* t);
+
+/**
+ * @brief remove a thread from rbtree, will automatically lock threads_lock
+ * @param t thread to remove
+ */
+void remove_thread(thread_t* t);
+
+#endif
diff --git a/kern/inc/sync.h b/kern/inc/sync.h
new file mode 100644
index 0000000..9bc53c8
--- /dev/null
+++ b/kern/inc/sync.h
@@ -0,0 +1,102 @@
+/** @file sync.h
+ *
+ *  @brief locks.
+ *
+ *  @author Hanjie Wu (hanjiew)
+ *  @bug No functional bugs
+ */
+
+#ifndef _SYNC_H_
+#define _SYNC_H_
+
+#include <common.h>
+
+/** declaration of thread control block */
+struct thread_s;
+/** declaration of thread control block */
+typedef struct thread_s thread_t;
+
+/**
+ * @brief save eflags and disable interrupt
+ * @return eflags
+ */
+int save_clear_if();
+/**
+ * @brief restore eflags
+ * @param old_if eflags
+ */
+void restore_if(int old_if);
+
+/** spinlock structure, only needed for SMP */
+typedef struct spl_s {
+    int locked;
+} spl_t;
+
+/** initial value for spinlock */
+#define SPL_INIT (spl_t){.locked = 0};
+
+/**
+ * @brief lock the spinlock and disable interrupts
+ * @return original eflags
+ */
+int spl_lock(spl_t* spl);
+/**
+ * @brief unlock the spinlock and restore eflags
+ * @param old_if eflags
+ */
+void spl_unlock(spl_t* spl, int old_if);
+
+/**
+ * @brief atomically yield to another thread and unlock the spinlock, eflags
+ * will be restored when current thread become running again
+ * @param t thread to yield to
+ * @param spl spinlock
+ * @param old_if eflags
+ */
+void yield_to_spl_unlock(thread_t* t, spl_t* spl, int old_if);
+
+/** mutex structure */
+typedef struct mutex_s {
+    spl_t guard;
+    int locked;
+    queue_t* waiters;
+} mutex_t;
+
+/** initial value for mutex */
+#define MUTEX_INIT \
+    (mutex_t){.guard = {.locked = 0}, .locked = 0, .waiters = NULL};
+
+/**
+ * @brief lock the mutex, will be blocked if lock is held by other thread
+ * @param m mutex
+ */
+void mutex_lock(mutex_t* m);
+/**
+ * @brief unlock the mutex, will wake up one blocked thread if there is one
+ * @param m mutex
+ */
+void mutex_unlock(mutex_t* m);
+
+/** cv structure */
+typedef struct cv_s {
+    spl_t guard;
+    queue_t* waiters;
+} cv_t;
+
+/** initial value for cv */
+#define CV_INIT \
+    (cv_t) { .guard = {.locked = 0}, .waiters = NULL }
+
+/**
+ * @brief unlock the mutex m and wait for other threads to call cv_signal on cv
+ * @param cv cv
+ * @param m mutex
+ */
+void cv_wait(cv_t* cv, mutex_t* m);
+/**
+ * @brief signal a cv, will wake up one blocked thread if there is one
+ * @param cv cv
+ */
+void cv_signal(cv_t* cv);
+
+#endif
diff --git a/kern/inc/timer.h b/kern/inc/timer.h
new file mode 100644
index 0000000..8d6368e
--- /dev/null
+++ b/kern/inc/timer.h
@@ -0,0 +1,24 @@
+/** @file timer.h
+ *
+ *  @brief timer functions.
+ *
+ *  @author Hanjie Wu (hanjiew)
+ *  @bug No functional bugs
+ */
+
+#ifndef _TIMER_H_
+#define _TIMER_H_
+
+/** ticks passed */
+extern unsigned int ticks;
+/** timer heap lock */
+extern spl_t timer_lock;
+/** timers of sleeping threads */
+extern heap_t timers;
+
+/**
+ * @brief initialize the timer
+ */
+void timer_init();
+
+#endif
diff --git a/kern/inc/usermem.h b/kern/inc/usermem.h
new file mode 100644
index 0000000..c5622e8
--- /dev/null
+++ b/kern/inc/usermem.h
@@ -0,0 +1,50 @@
+/** @file usermem.h
+ *
+ *  @brief userspace r/w functions.
+ *
+ *  @author Hanjie Wu (hanjiew)
+ *  @bug No functional bugs
+ */
+
+#ifndef _USERMEM_H_
+#define _USERMEM_H_
+
+#include <stdint.h>
+
+#include <common_kern.h>
+
+#include <paging.h>
+
+/**
+ * @brief copy bytes from userspace
+ * @param addr address of user memory
+ * @param size number of bytes
+ * @param buf buffer
+ * @return 0 on success, -1 on failure
+ */
+int copy_from_user(va_t addr, int size, void* buf);
+/**
+ * @brief copy bytes to userspace
+ * @param addr address of user memory
+ * @param size number of bytes
+ * @param buf buffer
+ * @return 0 on success, -1 on failure
+ */
+int copy_to_user(va_t addr, int size, void* buf);
+
+/**
+ * @brief try to copy a string from userspace
+ * @param addr address of user memory
+ * @param maxlen maximum length of the string including the null byte
+ * @return NULL on failure, a string allocated by malloc() on success
+ */
+char* copy_string_from_user(va_t addr, int maxlen);
+/**
+ * @brief try to print a buffer from userspace
+ * @param addr address of user memory
+ * @param maxlen maximum length of to print
+ * @return 0 on success, -1 on failure
+ */
+int print_buf_from_user(va_t addr, int maxlen);
+
+#endif
diff --git a/kern/interrupt.c b/kern/interrupt.c
new file mode 100644
index 0000000..ad48e5f
--- /dev/null
+++ b/kern/interrupt.c
@@ -0,0 +1,502 @@
+/** @file interrupt.c
+ *
+ *  @brief idt initializer and fault/interrupt handlers.
+ *
+ *  @author Hanjie Wu (hanjiew)
+ *  @bug No functional bugs
+ */
+
+#include <x86/asm.h>
+#include <x86/eflags.h>
+#include <x86/idt.h>
+#include <x86/interrupt_defines.h>
+#include <x86/seg.h>
+#include <x86/timer_defines.h>
+
+#include <keyhelp.h>
+#include <simics.h>
+#include <stdio.h>
+#include <string.h>
+#include <syscall_int.h>
+#include <ureg.h>
+
+#include <asm_instr.h>
+#include <interrupt.h>
+#include <mm.h>
+#include <paging.h>
+#include <sched.h>
+#include <sync.h>
+#include <timer.h>
+#include <usermem.h>
+
+/** means this entry requires ring 0 privilige */
+#define IDT_DPL_KERNEL 0
+/** means this entry requires ring 3 privilige */
+#define IDT_DPL_USER 3
+/** means this entry is valid */
+#define IDT_P 1
+/** means this entry is a 32 bit interrupt */
+#define IDT_TYPE_I32 0xe
+/** means this entry is a 32 bit trap */
+#define IDT_TYPE_T32 0xf
+
+/** P bit's position */
+#define IDT_P_SHIFT (47 - 32)
+/** DPL's position */
+#define IDT_DPL_SHIFT (45 - 32)
+/** TYPE's position */
+#define IDT_TYPE_SHIFT (40 - 32)
+/** CS's position */
+#define IDT_CS_SHIFT 16
+
+/** EIP's high part's bits */
+#define IDT_EIP_HI_MASK 0xffff0000
+/** EIP's low part's bits */
+#define IDT_EIP_LO_MASK 0x0000ffff
+
+/**
+ * @brief an idt entry
+ */
+typedef struct idt_s {
+    unsigned long lo;
+    unsigned long hi;
+} idt_t;
+
+/**
+ * @brief create an idt entry
+ * @param eip eip
+ * @param type type
+ * @param dpl dpl
+ * @return the idt entry
+ */
+static inline idt_t make_idt(va_t eip, int type, int dpl) {
+    idt_t idt;
+    idt.hi = ((eip & IDT_EIP_HI_MASK) | (IDT_P << IDT_P_SHIFT) |
+              (dpl << IDT_DPL_SHIFT) | (type << IDT_TYPE_SHIFT));
+    idt.lo = ((SEGSEL_KERNEL_CS << IDT_CS_SHIFT) | (eip & IDT_EIP_LO_MASK));
+    return idt;
+}
+
+/**
+ * @brief DE handler entry
+ */
+int de_handler();
+/**
+ * @brief DB handler entry
+ */
+int db_handler();
+/**
+ * @brief NMI handler entry
+ */
+int nmi_handler();
+/**
+ * @brief BP handler entry
+ */
+int bp_handler();
+/**
+ * @brief OF handler entry
+ */
+int of_handler();
+/**
+ * @brief BR handler entry
+ */
+int br_handler();
+/**
+ * @brief UD handler entry
+ */
+int ud_handler();
+/**
+ * @brief NM handler entry
+ */
+int nm_handler();
+/**
+ * @brief DF handler entry
+ */
+int df_handler();
+/**
+ * @brief CSO handler entry
+ */
+int cso_handler();
+/**
+ * @brief TS handler entry
+ */
+int ts_handler();
+/**
+ * @brief NP handler entry
+ */
+int np_handler();
+/**
+ * @brief SS handler entry
+ */
+int ss_handler();
+/**
+ * @brief GP handler entry
+ */
+int gp_handler();
+/**
+ * @brief PF handler entry
+ */
+int pf_handler();
+/**
+ * @brief MF handler entry
+ */
+int mf_handler();
+/**
+ * @brief AC handler entry
+ */
+int ac_handler();
+/**
+ * @brief MC handler entry
+ */
+int mc_handler();
+/**
+ * @brief XF handler entry
+ */
+int xf_handler();
+
+/**
+ * @brief default handler entry
+ */
+int default_handler();
+
+/**
+ * @brief timer handler entry
+ */
+void timer_handler();
+/**
+ * @brief keyboard handler entry
+ */
+void kbd_handler();
+
+/**
+ * @brief fork() syscall entry
+ */
+void sys_fork();
+/**
+ * @brief exec() syscall entry
+ */
+void sys_exec();
+/**
+ * @brief wait() syscall entry
+ */
+void sys_wait();
+/**
+ * @brief yield() syscall entry
+ */
+void sys_yield();
+/**
+ * @brief deschedule() syscall entry
+ */
+void sys_deschedule();
+/**
+ * @brief make_runnable() syscall entry
+ */
+void sys_make_runnable();
+/**
+ * @brief gettid() syscall entry
+ */
+void sys_gettid();
+/**
+ * @brief new_pages() syscall entry
+ */
+void sys_new_pages();
+/**
+ * @brief remove_pages() syscall entry
+ */
+void sys_remove_pages();
+/**
+ * @brief sleep() syscall entry
+ */
+void sys_sleep();
+/**
+ * @brief getchar() syscall entry
+ */
+void sys_getchar();
+/**
+ * @brief readline() syscall entry
+ */
+void sys_readline();
+/**
+ * @brief print() syscall entry
+ */
+void sys_print();
+/**
+ * @brief set_term_color() syscall entry
+ */
+void sys_set_term_color();
+/**
+ * @brief set_cursor_pos() syscall entry
+ */
+void sys_set_cursor_pos();
+/**
+ * @brief get_cursor() syscall entry
+ */
+void sys_get_cursor_pos();
+/**
+ * @brief thread() syscall entry
+ */
+void sys_thread_fork();
+/**
+ * @brief get_ticks() syscall entry
+ */
+void sys_get_ticks();
+/**
+ * @brief misbehave() syscall entry
+ */
+void sys_misbehave();
+/**
+ * @brief halt() syscall entry
+ */
+void sys_halt();
+/**
+ * @brief task_vanish() syscall entry
+ */
+void sys_task_vanish();
+/**
+ * @brief set_status() syscall entry
+ */
+void sys_set_status();
+/**
+ * @brief vanish() syscall entry
+ */
+void sys_vanish();
+/**
+ * @brief readfile() syscall entry
+ */
+void sys_readfile();
+/**
+ * @brief swexn() syscall entry
+ */
+void sys_swexn();
+
+/**
+ * @brief all other syscall entries
+ */
+void sys_enosys();
+
+/** index of first syscall */
+#define IDT_SYSCALL_START (X86_PIC_MASTER_IRQ_BASE + 16)
+
+void idt_init() {
+    idt_t* idt = (idt_t*)idt_base();
+
+    int i;
+    for (i = 0; i < IDT_SYSCALL_START; i++) {
+        idt[i] = make_idt((va_t)default_handler, IDT_TYPE_I32, IDT_DPL_KERNEL);
+    }
+
+    idt[IDT_DE] = make_idt((va_t)de_handler, IDT_TYPE_I32, IDT_DPL_KERNEL);
+    idt[IDT_DB] = make_idt((va_t)db_handler, IDT_TYPE_I32, IDT_DPL_KERNEL);
+    idt[IDT_NMI] = make_idt((va_t)nmi_handler, IDT_TYPE_I32, IDT_DPL_KERNEL);
+    idt[IDT_BP] = make_idt((va_t)bp_handler, IDT_TYPE_I32, IDT_DPL_KERNEL);
+    idt[IDT_OF] = make_idt((va_t)of_handler, IDT_TYPE_I32, IDT_DPL_KERNEL);
+    idt[IDT_BR] = make_idt((va_t)br_handler, IDT_TYPE_I32, IDT_DPL_KERNEL);
+    idt[IDT_UD] = make_idt((va_t)ud_handler, IDT_TYPE_I32, IDT_DPL_KERNEL);
+    idt[IDT_NM] = make_idt((va_t)nm_handler, IDT_TYPE_I32, IDT_DPL_KERNEL);
+    idt[IDT_DF] = make_idt((va_t)df_handler, IDT_TYPE_I32, IDT_DPL_KERNEL);
+    idt[IDT_CSO] = make_idt((va_t)cso_handler, IDT_TYPE_I32, IDT_DPL_KERNEL);
+    idt[IDT_TS] = make_idt((va_t)ts_handler, IDT_TYPE_I32, IDT_DPL_KERNEL);
+    idt[IDT_NP] = make_idt((va_t)np_handler, IDT_TYPE_I32, IDT_DPL_KERNEL);
+    idt[IDT_SS] = make_idt((va_t)ss_handler, IDT_TYPE_I32, IDT_DPL_KERNEL);
+    idt[IDT_GP] = make_idt((va_t)gp_handler, IDT_TYPE_I32, IDT_DPL_KERNEL);
+    idt[IDT_PF] = make_idt((va_t)pf_handler, IDT_TYPE_I32, IDT_DPL_KERNEL);
+    idt[IDT_MF] = make_idt((va_t)mf_handler, IDT_TYPE_I32, IDT_DPL_KERNEL);
+    idt[IDT_AC] = make_idt((va_t)ac_handler, IDT_TYPE_I32, IDT_DPL_KERNEL);
+    idt[IDT_MC] = make_idt((va_t)mc_handler, IDT_TYPE_I32, IDT_DPL_KERNEL);
+    idt[IDT_XF] = make_idt((va_t)xf_handler, IDT_TYPE_I32, IDT_DPL_KERNEL);
+
+    idt[TIMER_IDT_ENTRY] =
+        make_idt((va_t)timer_handler, IDT_TYPE_I32, IDT_DPL_KERNEL);
+    idt[KEY_IDT_ENTRY] =
+        make_idt((va_t)kbd_handler, IDT_TYPE_I32, IDT_DPL_KERNEL);
+
+    for (i = IDT_SYSCALL_START; i < IDT_ENTS; i++) {
+        idt[i] = make_idt((va_t)sys_enosys, IDT_TYPE_T32, IDT_DPL_USER);
+    }
+
+    idt[FORK_INT] = make_idt((va_t)sys_fork, IDT_TYPE_T32, IDT_DPL_USER);
+    idt[EXEC_INT] = make_idt((va_t)sys_exec, IDT_TYPE_T32, IDT_DPL_USER);
+    idt[WAIT_INT] = make_idt((va_t)sys_wait, IDT_TYPE_T32, IDT_DPL_USER);
+    idt[YIELD_INT] = make_idt((va_t)sys_yield, IDT_TYPE_T32, IDT_DPL_USER);
+    idt[DESCHEDULE_INT] =
+        make_idt((va_t)sys_deschedule, IDT_TYPE_T32, IDT_DPL_USER);
+    idt[MAKE_RUNNABLE_INT] =
+        make_idt((va_t)sys_make_runnable, IDT_TYPE_T32, IDT_DPL_USER);
+    idt[GETTID_INT] = make_idt((va_t)sys_gettid, IDT_TYPE_T32, IDT_DPL_USER);
+    idt[NEW_PAGES_INT] =
+        make_idt((va_t)sys_new_pages, IDT_TYPE_T32, IDT_DPL_USER);
+    idt[REMOVE_PAGES_INT] =
+        make_idt((va_t)sys_remove_pages, IDT_TYPE_T32, IDT_DPL_USER);
+    idt[SLEEP_INT] = make_idt((va_t)sys_sleep, IDT_TYPE_T32, IDT_DPL_USER);
+    idt[GETCHAR_INT] = make_idt((va_t)sys_getchar, IDT_TYPE_T32, IDT_DPL_USER);
+    idt[READLINE_INT] =
+        make_idt((va_t)sys_readline, IDT_TYPE_T32, IDT_DPL_USER);
+    idt[PRINT_INT] = make_idt((va_t)sys_print, IDT_TYPE_T32, IDT_DPL_USER);
+    idt[SET_TERM_COLOR_INT] =
+        make_idt((va_t)sys_set_term_color, IDT_TYPE_T32, IDT_DPL_USER);
+    idt[SET_CURSOR_POS_INT] =
+        make_idt((va_t)sys_set_cursor_pos, IDT_TYPE_T32, IDT_DPL_USER);
+    idt[GET_CURSOR_POS_INT] =
+        make_idt((va_t)sys_get_cursor_pos, IDT_TYPE_T32, IDT_DPL_USER);
+    idt[THREAD_FORK_INT] =
+        make_idt((va_t)sys_thread_fork, IDT_TYPE_T32, IDT_DPL_USER);
+    idt[GET_TICKS_INT] =
+        make_idt((va_t)sys_get_ticks, IDT_TYPE_T32, IDT_DPL_USER);
+    idt[MISBEHAVE_INT] =
+        make_idt((va_t)sys_misbehave, IDT_TYPE_T32, IDT_DPL_USER);
+    idt[HALT_INT] = make_idt((va_t)sys_halt, IDT_TYPE_T32, IDT_DPL_USER);
+    idt[TASK_VANISH_INT] =
+        make_idt((va_t)sys_task_vanish, IDT_TYPE_T32, IDT_DPL_USER);
+    idt[SET_STATUS_INT] =
+        make_idt((va_t)sys_set_status, IDT_TYPE_T32, IDT_DPL_USER);
+    idt[VANISH_INT] = make_idt((va_t)sys_vanish, IDT_TYPE_T32, IDT_DPL_USER);
+    idt[READFILE_INT] =
+        make_idt((va_t)sys_readfile, IDT_TYPE_T32, IDT_DPL_USER);
+    idt[SWEXN_INT] = make_idt((va_t)sys_swexn, IDT_TYPE_T32, IDT_DPL_USER);
+}
+
+/** string explanation of fault */
+const static char* reasons[] = {"Division Error",
+                                "Debug",
+                                "Non-maskable Interrupt",
+                                "Breakpoint",
+                                "Overflow",
+                                "Bound Range Exceeded",
+                                "Invalid Opcode",
+                                "Device Not Available",
+                                "Double Fault",
+                                "Coprocessor Segment Overrun",
+                                "Invalid TSS",
+                                "Segment Not Present",
+                                "Stack-Segment Fault",
+                                "General Protection Fault",
+                                "Page Fault",
+                                "Reserved",
+                                "x87 Floating-Point Exception",
+                                "Alignment Check",
+                                "Machine Check",
+                                "SIMD Floating-Point Exception",
+                                "Virtualization Exception",
+                                "Control Protection Exception",
+                                "Reserved",
+                                "Reserved",
+                                "Reserved",
+                                "Reserved",
+                                "Reserved",
+                                "Reserved",
+                                "Hypervisor Injection Exception",
+                                "VMM Communication Exception",
+                                "Security Exception",
+                                "Reserved"};
+
+/**
+ * @brief dump register information
+ * @param frame ureg registers
+ */
+static void dump_fault(ureg_t* frame);
+
+/**
+ * @brief handle a fault
+ * @param frame ureg registers
+ */
+void handle_fault(ureg_t* frame) {
+    thread_t* current = get_current();
+    if (frame->cause == SWEXN_CAUSE_PAGEFAULT && frame->cr2 >= USER_MEM_START) {
+        /* check ZFOD */
+        pa_t old_pa;
+        page_directory_t* pd =
+            (page_directory_t*)map_phys_page(current->process->cr3, &old_pa);
+        pde_t* pde = &(*pd)[get_pd_index(frame->cr2)];
+        if (*pde != BAD_PDE) {
+            pa_t pt_pa = get_page_table(*pde);
+            page_table_t* pt = (page_table_t*)map_phys_page(pt_pa, NULL);
+            pte_t* pte = &(*pt)[get_pt_index(frame->cr2)];
+            if (*pte != BAD_PTE &&
+                ((*pte & (PTE_PRESENT << PTE_P_SHIFT)) == 0)) {
+                *pte = (*pte | (PTE_PRESENT << PTE_P_SHIFT));
+                invlpg(frame->cr2);
+                memset((void*)(frame->cr2 & PAGE_BASE_MASK), 0, PAGE_SIZE);
+                map_phys_page(old_pa, NULL);
+                return;
+            }
+        }
+        map_phys_page(old_pa, NULL);
+    }
+    if (frame->cs == SEGSEL_KERNEL_CS) {
+        /* recover from accessing user memory */
+        if ((frame->cause == SWEXN_CAUSE_PAGEFAULT ||
+             frame->cause == SWEXN_CAUSE_PROTFAULT) &&
+            current->eip0 != 0) {
+            frame->eip = current->eip0;
+            return;
+        }
+        /* all other non recoverable fault */
+        dump_fault(frame);
+        while (1) {
+        }
+    }
+    /* send to user swexn */
+    if (current->eip3 != 0 && current->df3 == 0) {
+        va_t esp3 = (va_t)current->esp3;
+        esp3 -= sizeof(ureg_t);
+        esp3 = (esp3 & (~(sizeof(va_t) - 1)));
+        /* push ureg */
+        if (copy_to_user(esp3, sizeof(ureg_t), frame) != 0) {
+            goto kill_thread;
+        }
+        /* push swexn args (return address, swexn arg, ureg)
+         * swexn handler must call swexn to jump back, we use 0 address to cause
+         * a GP on function return
+         */
+        unsigned long stack[3] = {0, current->swexn_arg, (unsigned long)esp3};
+        unsigned long* new_esp = (unsigned long*)esp3;
+        new_esp -= 3;
+        if (copy_to_user((va_t)new_esp, 3 * sizeof(unsigned long), stack) !=
+            0) {
+            goto kill_thread;
+        }
+        frame->edi = 0;
+        frame->esi = 0;
+        frame->ebp = 0;
+        frame->zero = 0;
+        frame->ebx = 0;
+        frame->edx = 0;
+        frame->ecx = 0;
+        frame->eax = 0;
+        frame->eip = current->eip3;
+        frame->eflags = DEFAULT_EFLAGS;
+        frame->esp = (unsigned int)new_esp;
+        current->df3 = 1;
+        current->eip3 = 0;
+        return;
+    }
+    /* no swexn handler or fault inside swexn */
+kill_thread:
+    sim_printf("LWP %d killed: %s", current->rb_node.key,
+               reasons[frame->cause]);
+    printf("LWP %d killed: %s\n", current->rb_node.key, reasons[frame->cause]);
+    if (current->process->refcount == 1) {
+        current->process->exit_value = -2;
+    }
+    kill_current();
+}
+
+static void dump_fault(ureg_t* frame) {
+    sim_printf("Fault: %s  Error Code: %08x", reasons[frame->cause],
+               frame->error_code);
+    sim_printf("CS:EIP=%04x:%08x  EFLAGS=%08x", frame->cs, frame->eip,
+               frame->eflags);
+    sim_printf("EAX=%08x  EBX=%08x  ECX=%08x  EDX=%08x", frame->eax, frame->ebx,
+               frame->ecx, frame->edx);
+    sim_printf("ESI=%08x  EDI=%08x  ESP=%08x  EBP=%08x", frame->esi, frame->edi,
+               frame->esp, frame->ebp);
+    printf("=========================\n");
+    printf("Fault: %s  Error Code: %08x\n", reasons[frame->cause],
+           frame->error_code);
+    printf("CS:EIP=%04x:%08x  EFLAGS=%08x\n", frame->cs, frame->eip,
+           frame->eflags);
+    printf("EAX=%08x  EBX=%08x  ECX=%08x  EDX=%08x\n", frame->eax, frame->ebx,
+           frame->ecx, frame->edx);
+    printf("ESI=%08x  EDI=%08x  ESP=%08x  EBP=%08x\n", frame->esi, frame->edi,
+           frame->esp, frame->ebp);
+}
diff --git a/kern/interrupt_asm.S b/kern/interrupt_asm.S
new file mode 100644
index 0000000..99176e4
--- /dev/null
+++ b/kern/interrupt_asm.S
@@ -0,0 +1,134 @@
+/** @file interrupt_asm.S
+ *
+ *  @brief fault and interrupt handlers.
+ *
+ *  @author Hanjie Wu (hanjiew)
+ *  @bug No functional bugs
+ */
+
+#include <x86/seg.h>
+#include <x86/interrupt_defines.h>
+
+#define SEGSEL_KERNEL_FS SEGSEL_SPARE0
+
+.global default_handler
+default_handler:
+    iret
+
+.macro  FAULT_HANDLER_ERR name cause
+.global \name\()_handler
+.type \name\()_handler, %function
+\name\()_handler:
+    pusha /* save a ureg_t structure */
+    push %gs
+    push %fs
+    push %es
+    push %ds
+    mov %cr2, %eax
+    push %eax
+    push $\cause
+    mov $SEGSEL_KERNEL_DS, %eax
+    mov %ax, %ds
+    mov %ax, %es
+    mov $SEGSEL_KERNEL_FS, %eax
+    mov %ax, %fs
+    cld
+    push %esp
+    call handle_fault
+    add $0xc, %esp /* skip cr2, cause and argument */
+    pop %ds
+    pop %es
+    pop %fs
+    pop %gs
+    popa
+    add $0x4, %esp /* skip error code */
+    iret
+.endm
+
+.macro  FAULT_HANDLER_NOERR name cause
+.global \name\()_handler
+.type \name\()_handler, %function
+\name\()_handler:
+    sub $0x4, %esp /* dummy error code */
+    pusha
+    push %gs
+    push %fs
+    push %es
+    push %ds
+    mov %cr2, %eax
+    push %eax
+    push $\cause
+    mov $SEGSEL_KERNEL_DS, %eax
+    mov %ax, %ds
+    mov %ax, %es
+    mov $SEGSEL_KERNEL_FS, %eax
+    mov %ax, %fs
+    cld
+    push %esp
+    call handle_fault
+    add $0xc, %esp /* skip cr2, cause and argument */
+    pop %ds
+    pop %es
+    pop %fs
+    pop %gs
+    popa
+    add $0x4, %esp /* skip error code */
+    iret
+.endm
+
+FAULT_HANDLER_NOERR de 0x0
+FAULT_HANDLER_NOERR db 0x1
+FAULT_HANDLER_NOERR nmi 0x2
+FAULT_HANDLER_NOERR bp 0x3
+FAULT_HANDLER_NOERR of 0x4
+FAULT_HANDLER_NOERR br 0x5
+FAULT_HANDLER_NOERR ud 0x6
+FAULT_HANDLER_NOERR nm 0x7
+FAULT_HANDLER_ERR df 0x8
+FAULT_HANDLER_NOERR cso 0x9
+FAULT_HANDLER_ERR ts 0xa
+FAULT_HANDLER_ERR np 0xb
+FAULT_HANDLER_ERR ss 0xc
+FAULT_HANDLER_ERR gp 0xd
+FAULT_HANDLER_ERR pf 0xe
+FAULT_HANDLER_NOERR mf 0x10
+FAULT_HANDLER_ERR ac 0x11
+FAULT_HANDLER_NOERR mc 0x12
+FAULT_HANDLER_NOERR xf 0x13
+
+#define SEGSEL_KERNEL_FS SEGSEL_SPARE0
+
+.global timer_handler
+.type timer_handler, %function
+timer_handler:
+    pusha /* save a stack_frame_t structure */
+    push %ds
+    push %es
+    push %fs
+    push %gs
+    mov $SEGSEL_KERNEL_DS, %eax
+    mov %ax, %ds
+    mov %ax, %es
+    mov $SEGSEL_KERNEL_FS, %eax
+    mov %ax, %fs
+    cld
+    call timer_handler_real
+    jmp return_to_user /* check pending exit before iret */
+
+
+.global kbd_handler
+.type kbd_handler, %function
+kbd_handler:
+    pusha /* save a stack_frame_t structure */
+    push %ds
+    push %es
+    push %fs
+    push %gs
+    mov $SEGSEL_KERNEL_DS, %eax
+    mov %ax, %ds
+    mov %ax, %es
+    mov $SEGSEL_KERNEL_FS, %eax
+    mov %ax, %fs
+    cld
+    call kbd_handler_real
+    jmp return_to_user /* check pending exit before iret */
diff --git a/kern/kbd.c b/kern/kbd.c
new file mode 100644
index 0000000..5ba1bcb
--- /dev/null
+++ b/kern/kbd.c
@@ -0,0 +1,218 @@
+/** @file kbd.c
+ *
+ *  @brief Keyboard handler implementation.
+ *
+ *  @author Hanjie Wu (hanjiew)
+ *  @bug No functional bugs.
+ */
+
+#include <stdbool.h>
+#include <stddef.h>
+#include <stdint.h>
+#include <string.h>
+
+#include <x86/asm.h>
+#include <x86/interrupt_defines.h>
+#include <x86/keyhelp.h>
+
+#include <console.h>
+#include <interrupt.h>
+#include <kbd.h>
+#include <paging.h>
+#include <sync.h>
+#include <usermem.h>
+
+/** a node in queue of threads requesting keyboard access */
+typedef struct kbd_request_s {
+    thread_t* t;
+    queue_t node;
+} kbd_request_t;
+
+/** size of scancode ring buffer, a big buffer enough for someone pressing
+ * keyboard fast */
+#define SC_RING_SIZE PAGE_SIZE
+/** size of character ring buffer, a big buffer enough for someone pressing
+ * keyboard fast */
+#define CHR_RING_SIZE PAGE_SIZE
+/** maximum readline size */
+#define MAX_READLINE (CHR_RING_SIZE - 1)
+
+/** queue of threads requesting keyboard access */
+static queue_t* inputs = NULL;
+
+/** mutex for keyboard request queue */
+static mutex_t kbd_request_lock = MUTEX_INIT;
+/** signal for a thread leaving request queue */
+static cv_t kbd_request_cv = CV_INIT;
+
+/** mutex for new scancode input */
+static mutex_t input_lock = MUTEX_INIT;
+/** signal for new scancode input */
+static cv_t input_cv = CV_INIT;
+/** need pic acknowlege */
+static int need_ack = 0;
+
+/** scancode ring buffer */
+static unsigned char sc_ring[SC_RING_SIZE];
+/** read pointer of scancode ring buffer */
+static int sc_r_pos = 0;
+/** write pointer of scancode ring buffer */
+static int sc_w_pos = 0;
+
+/** character ring buffer */
+static char chr_ring[CHR_RING_SIZE];
+/** read pointer of character ring buffer */
+static int chr_r_pos = 0;
+/** write pointer of character ring buffer */
+static int chr_w_pos = 0;
+
+/**
+ * @brief keyboard inturrupt handler
+ */
+void kbd_handler_real() {
+    unsigned char sc = inb(KEYBOARD_PORT);
+    int next_w_pos = (sc_w_pos + 1) % SC_RING_SIZE;
+    if (next_w_pos != sc_r_pos) {
+        sc_ring[sc_w_pos] = sc;
+        sc_w_pos = next_w_pos;
+        pic_acknowledge(KBD_IRQ);
+    } else {
+        /* let processing thread ack after processing scancode */
+        need_ack = 1;
+    }
+    cv_signal(&input_cv);
+}
+
+/**
+ * @brief process scancode until a char is produced
+ * @return char produced
+ */
+static int sc_process();
+
+/**
+ * @brief flush a line to user buffer
+ * @param len length of buffer
+ * @param buf buffer
+ * @return size of chars flushed, -1: buf invalid
+ */
+static int flush_line(int len, va_t buf);
+
+int do_readline(int len, va_t buf) {
+    if (len < 0 || len > MAX_READLINE) {
+        return -1;
+    }
+    if (len == 0) {
+        return 0;
+    }
+    kbd_request_t req;
+    req.t = get_current();
+    /* wait until our turn */
+    mutex_lock(&kbd_request_lock);
+    queue_insert_tail(&inputs, &req.node);
+    while (inputs != &req.node) {
+        cv_wait(&kbd_request_cv, &kbd_request_lock);
+    }
+    mutex_unlock(&kbd_request_lock);
+    int should_flush = 0;
+    if (chr_r_pos != chr_w_pos) {
+        int i;
+        for (i = chr_r_pos; i != chr_w_pos; i = (i + 1) % CHR_RING_SIZE) {
+            if (chr_ring[i] == '\n') {
+                should_flush = 1;
+                break;
+            }
+        }
+        /* check if ring is full */
+        if (chr_r_pos == (chr_w_pos + 1) % CHR_RING_SIZE) {
+            should_flush = 1;
+        }
+    }
+    while (should_flush == 0) {
+        /* wait for more chars */
+        char c = sc_process();
+        if (c == '\b') {
+            if (chr_w_pos != chr_r_pos) {
+                putbyte(c);
+                chr_w_pos = (chr_w_pos + CHR_RING_SIZE - 1) % CHR_RING_SIZE;
+            }
+        } else {
+            chr_ring[chr_w_pos] = c;
+            chr_w_pos = (chr_w_pos + 1) % CHR_RING_SIZE;
+            putbyte(c);
+            should_flush =
+                (c == '\n') || (chr_r_pos == (chr_w_pos + 1) % CHR_RING_SIZE);
+        }
+    }
+    int result = flush_line(len, buf);
+    mutex_lock(&kbd_request_lock);
+    queue_detach(&inputs, &req.node);
+    cv_signal(&kbd_request_cv);
+    mutex_unlock(&kbd_request_lock);
+    return result;
+}
+
+int do_getchar() {
+    kbd_request_t req;
+    req.t = get_current();
+    mutex_lock(&kbd_request_lock);
+    queue_insert_tail(&inputs, &req.node);
+    while (inputs != &req.node) {
+        cv_wait(&kbd_request_cv, &kbd_request_lock);
+    }
+    mutex_unlock(&kbd_request_lock);
+    int result;
+    if (chr_r_pos != chr_w_pos) {
+        result = chr_ring[chr_r_pos];
+        chr_r_pos = (chr_r_pos + 1) % CHR_RING_SIZE;
+    } else {
+        result = sc_process();
+    }
+    mutex_lock(&kbd_request_lock);
+    queue_detach(&inputs, &req.node);
+    cv_signal(&kbd_request_cv);
+    mutex_unlock(&kbd_request_lock);
+    return result;
+}
+
+static int flush_line(int len, va_t buf) {
+    int size = 0, i;
+    for (i = chr_r_pos; i != chr_w_pos; i = (i + 1) % CHR_RING_SIZE) {
+        size++;
+        if (chr_ring[i] == '\n') {
+            break;
+        }
+    }
+    if (size > len) {
+        size = len;
+    }
+    for (i = 0; i < size; i++) {
+        if (copy_to_user(buf + i, 1,
+                         &chr_ring[(chr_r_pos + i) % CHR_RING_SIZE]) != 0) {
+            /* failed to flush, do not discard anything */
+            return -1;
+        }
+    }
+    chr_r_pos = (chr_r_pos + i) % CHR_RING_SIZE;
+    return size;
+}
+
+static int sc_process() {
+    while (1) {
+        /* wait for more scancode */
+        mutex_lock(&input_lock);
+        while (sc_r_pos == sc_w_pos) {
+            cv_wait(&input_cv, &input_lock);
+        }
+        int sc = sc_ring[sc_r_pos];
+        sc_r_pos = (sc_r_pos + 1) % SC_RING_SIZE;
+        mutex_unlock(&input_lock);
+        if (need_ack == 1) {
+            need_ack = 0;
+            pic_acknowledge(KBD_IRQ);
+        }
+        kh_type kh = process_scancode(sc);
+        if (KH_HASDATA(kh) && KH_ISMAKE(kh)) {
+            return KH_GETCHAR(kh);
+        }
+    }
+}
diff --git a/kern/kernel.c b/kern/kernel.c
new file mode 100644
index 0000000..e473022
--- /dev/null
+++ b/kern/kernel.c
@@ -0,0 +1,109 @@
+/** @file kernel.c
+ *
+ *  @brief kernel entry.
+ *
+ *  @author Hanjie Wu (hanjiew)
+ *  @bug No functional bugs
+ */
+
+#include <common_kern.h>
+
+/* libc includes. */
+#include <simics.h> /* lprintf() */
+#include <stdio.h>
+#include <string.h>
+
+/* multiboot header file */
+#include <mptable.h>
+#include <multiboot.h> /* boot_info */
+#include <smp.h>
+
+/* x86 specific includes */
+#include <x86/asm.h> /* enable_interrupts() */
+#include <x86/cr.h>
+
+#include <assert.h>
+#include <common.h>
+#include <console.h>
+#include <interrupt.h>
+#include <mm.h>
+#include <paging.h>
+#include <sched.h>
+#include <timer.h>
+
+/**
+ * @brief entry for a cpu core
+ * @param cpuid cpuid
+ */
+static void kernel_smp_entry(int cpuid);
+
+/**
+ * @brief main function for a cpu core
+ */
+static void kernel_smp_main();
+
+/** @brief Kernel entrypoint.
+ *
+ *  This is the entrypoint for the kernel.
+ *
+ * @return Does not return
+ */
+int kernel_main(mbinfo_t* mbinfo, int argc, char** argv, char** envp) {
+    int smp_good = (smp_init(mbinfo) == 0);
+    paging_init();
+    percpu_t percpu;
+    setup_percpu(&percpu);
+    thread_t kthread;
+    process_t kprocess;
+    setup_kth(&kthread, &kprocess);
+    set_mapped_phys_page(mapped_phys_pages);
+    set_mapped_phys_page_pte(mapped_phys_page_ptes);
+
+    idt_init();
+    mm_init();
+    timer_init();
+    clear_console();
+
+    const char* init_args[] = {INIT_NAME};
+    thread_t* init = create_process(0, INIT_NAME, 1, init_args);
+    init_process = init->process;
+    add_thread(init);
+    insert_ready_tail(init);
+
+    if (smp_good && smp_num_cpus() > 1 && 0) {
+        /* SMP not enabled */
+        smp_boot(kernel_smp_entry);
+    }
+
+    kernel_smp_main();
+    return -1;
+}
+
+static void kernel_smp_entry(int cpuid) {
+    paging_enable();
+    percpu_t percpu;
+    setup_percpu(&percpu);
+    thread_t kthread;
+    process_t kprocess;
+    setup_kth(&kthread, &kprocess);
+    set_mapped_phys_page(mapped_phys_pages + cpuid * PAGE_SIZE);
+    set_mapped_phys_page_pte(mapped_phys_page_ptes + cpuid);
+    kernel_smp_main();
+}
+
+static void kernel_smp_main() {
+    const char* idle_args[] = {IDLE_NAME};
+    thread_t* idle = create_process(0, IDLE_NAME, 1, idle_args);
+    add_thread(idle);
+    set_idle(idle);
+
+    while (1) {
+        int old_if = spl_lock(&ready_lock);
+        thread_t* t = select_next();
+        yield_to_spl_unlock(t, &ready_lock, old_if);
+        /* when a thread borrow kthread's stack and free itself, it will return
+         * here and we continue yielding
+         */
+    }
+    panic("kthread should not return");
+}
diff --git a/kern/loader.c b/kern/loader.c
new file mode 100644
index 0000000..2dfd8e3
--- /dev/null
+++ b/kern/loader.c
@@ -0,0 +1,58 @@
+/**
+ * The 15-410 kernel project.
+ * @name loader.c
+ *
+ * Functions for the loading
+ * of user programs from binary
+ * files should be written in
+ * this file. The function
+ * elf_load_helper() is provided
+ * for your use.
+ */
+
+/* --- Includes --- */
+#include <elf_410.h>
+#include <exec2obj.h>
+#include <loader.h>
+#include <malloc.h>
+#include <stdio.h>
+#include <string.h>
+
+/* --- Local function prototypes --- */
+
+/**
+ * Copies data from a file into a buffer.
+ *
+ * @param filename   the name of the file to copy data from
+ * @param offset     the location in the file to begin copying from
+ * @param size       the number of bytes to be copied
+ * @param buf        the buffer to copy the data into
+ *
+ * @return returns the number of bytes copied on succes; -1 on failure
+ */
+int getbytes(const char* filename, int offset, int size, char* buf) {
+    file_t* f = find_file(filename);
+    if (f == NULL || offset > f->execlen) {
+        return -1;
+    }
+    return read_file(f, offset, size, buf);
+}
+
+int read_file(file_t* f, int offset, int size, char* buf) {
+    int src_size = size;
+    if (f->execlen - offset < size) {
+        src_size = f->execlen - offset;
+    }
+    memcpy(buf, f->execbytes + offset, src_size);
+    return src_size;
+}
+
+file_t* find_file(const char* name) {
+    int i;
+    for (i = 0; i < exec2obj_userapp_count; i++) {
+        if (strcmp(name, exec2obj_userapp_TOC[i].execname) == 0) {
+            return &exec2obj_userapp_TOC[i];
+        }
+    }
+    return NULL;
+}
diff --git a/kern/malloc_wrappers.c b/kern/malloc_wrappers.c
new file mode 100644
index 0000000..6b4d525
--- /dev/null
+++ b/kern/malloc_wrappers.c
@@ -0,0 +1,70 @@
+/** @file malloc_wrappers.c
+ *
+ *  @brief locked malloc functions.
+ *
+ *  @author Hanjie Wu (hanjiew)
+ *  @bug No functional bugs
+ */
+
+#include <malloc.h>
+#include <malloc_internal.h>
+#include <stddef.h>
+
+#include <sync.h>
+
+mutex_t malloc_lock = MUTEX_INIT;
+
+/* safe versions of malloc functions */
+void* malloc(size_t size) {
+    mutex_lock(&malloc_lock);
+    void* mem = _malloc(size);
+    mutex_unlock(&malloc_lock);
+    return mem;
+}
+
+void* memalign(size_t alignment, size_t size) {
+    mutex_lock(&malloc_lock);
+    void* mem = _memalign(alignment, size);
+    mutex_unlock(&malloc_lock);
+    return mem;
+}
+
+void* calloc(size_t nelt, size_t eltsize) {
+    mutex_lock(&malloc_lock);
+    void* mem = _calloc(nelt, eltsize);
+    mutex_unlock(&malloc_lock);
+    return mem;
+}
+
+void* realloc(void* buf, size_t new_size) {
+    mutex_lock(&malloc_lock);
+    void* mem = _realloc(buf, new_size);
+    mutex_unlock(&malloc_lock);
+    return mem;
+}
+
+void free(void* buf) {
+    mutex_lock(&malloc_lock);
+    _free(buf);
+    mutex_unlock(&malloc_lock);
+}
+
+void* smalloc(size_t size) {
+    mutex_lock(&malloc_lock);
+    void* mem = _smalloc(size);
+    mutex_unlock(&malloc_lock);
+    return mem;
+}
+
+void* smemalign(size_t alignment, size_t size) {
+    mutex_lock(&malloc_lock);
+    void* mem = _smemalign(alignment, size);
+    mutex_unlock(&malloc_lock);
+    return mem;
+}
+
+void sfree(void* buf, size_t size) {
+    mutex_lock(&malloc_lock);
+    _sfree(buf, size);
+    mutex_unlock(&malloc_lock);
+}
diff --git a/kern/mm.c b/kern/mm.c
new file mode 100644
index 0000000..2c40af8
--- /dev/null
+++ b/kern/mm.c
@@ -0,0 +1,318 @@
+/** @file mm.c
+ *
+ *  @brief memory management functions.
+ *
+ *  @author Hanjie Wu (hanjiew)
+ *  @bug No functional bugs
+ */
+
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include <assert.h>
+#include <common_kern.h>
+#include <x86/asm.h>
+
+#include <asm_instr.h>
+#include <common.h>
+#include <mm.h>
+#include <paging.h>
+#include <sched.h>
+#include <sync.h>
+
+/** header of a free page */
+typedef struct page_head_s {
+    int size;
+    pa_t prev;
+    pa_t next;
+} page_head_t;
+
+/** footer of a free page */
+typedef struct page_foot_s {
+    char padding[PAGE_SIZE - sizeof(int)];
+    int size;
+} page_foot_t;
+
+/** total user pages */
+static int num_user_pages;
+
+/** bitmap to track page usage */
+static unsigned char* user_page_bitmap;
+
+/** bins from 4k to 1m, which is normal request size */
+#define NUM_BINS 9
+/** minimum size of last bin */
+#define LAST_BIN_SIZE (1 << (NUM_BINS - 1))
+/** bins for free chunks */
+static pa_t bins[9];
+
+mutex_t mm_lock = MUTEX_INIT;
+
+/**
+ * @brief is a page inuse
+ * @param pn physical page number
+ * @return 1 inuse, 0 free
+ */
+static int is_page_inuse(int pn) {
+    return (user_page_bitmap[(pn + 1) / 8] & (1 << ((pn + 1) % 8))) != 0;
+}
+
+/**
+ * @brief mark a page inuse
+ * @param pn physical page number
+ */
+static void set_page_inuse(int pn) {
+    user_page_bitmap[(pn + 1) / 8] |= (1 << ((pn + 1) % 8));
+}
+
+/**
+ * @brief mark a page free
+ * @param pn physical page number
+ */
+static void set_page_free(int pn) {
+    user_page_bitmap[(pn + 1) / 8] &= (~(1 << ((pn + 1) % 8)));
+}
+
+/**
+ * @brief convert physical address to page number
+ * @param pa physical address
+ * @return physical page number
+ */
+static int pa_to_pn(pa_t pa) {
+    return (pa - USER_MEM_START) / PAGE_SIZE;
+}
+
+/**
+ * @brief convert page number to physical address
+ * @param pn physical page number
+ * @return physical address
+ */
+static int pn_to_pa(int pn) {
+    return pn * PAGE_SIZE + USER_MEM_START;
+}
+
+/**
+ * @brief find which bin a free chunk belongs to
+ * @param size size of chunk
+ * @return bin
+ */
+static int find_bin(int size) {
+    if (size >= LAST_BIN_SIZE) {
+        return NUM_BINS - 1;
+    }
+    int i;
+    for (i = NUM_BINS - 2; i > 0; i--) {
+        if ((size & (1 << i)) != 0) {
+            return i;
+        }
+    }
+    return 0;
+}
+
+/**
+ * @brief add a chunk to bins
+ * @param pn physical page number
+ * @param size size of chunk
+ */
+static void add_to_bins(int pn, int size);
+
+/**
+ * @brief remove a chunk from bins
+ * @param pn physical page number
+ */
+static void remove_from_bins(int pn);
+
+/**
+ * @brief allocate a memory from a bin
+ * @param bin bin
+ * @param size size of chunk
+ * @return address of chunk, BAD_PA on failure
+ */
+static pa_t alloc_from_bin(pa_t* bin, int size);
+
+void mm_init() {
+    num_user_pages = machine_phys_frames() - (USER_MEM_START / PAGE_SIZE);
+    assert(num_user_pages > 0);
+    user_page_bitmap = smalloc((num_user_pages + 2) / 8);
+    assert(user_page_bitmap != NULL);
+    memset(user_page_bitmap, 0, (num_user_pages + 2) / 8);
+    memset(bins, 0, sizeof(bins));
+
+    set_page_inuse(-1);
+    set_page_inuse(num_user_pages);
+    add_to_bins(pa_to_pn(USER_MEM_START), num_user_pages);
+}
+
+pa_t alloc_user_pages(int num_pages) {
+    mutex_lock(&mm_lock);
+    int bn = find_bin(num_pages);
+    while (bn < NUM_BINS) {
+        pa_t result = alloc_from_bin(&bins[bn], num_pages);
+        if (result != BAD_PA) {
+            mutex_unlock(&mm_lock);
+            return result;
+        }
+        bn++;
+    }
+    mutex_unlock(&mm_lock);
+    return BAD_PA;
+}
+
+void free_user_pages(pa_t pa, int num_pages) {
+    mutex_lock(&mm_lock);
+    int pn = pa_to_pn(pa);
+    int final_pn = pn, final_size = num_pages;
+
+    /* merge with prev */
+    int prev_inuse = is_page_inuse(pn - 1);
+    if (prev_inuse == 0) {
+        int old_if = save_clear_if();
+        page_foot_t* prev_foot =
+            (page_foot_t*)map_phys_page(pn_to_pa(pn - 1), NULL);
+        int prev_size = prev_foot->size;
+        restore_if(old_if);
+        int prev_pn = pn - prev_size;
+        remove_from_bins(prev_pn);
+        final_pn = prev_pn;
+        final_size += prev_size;
+    }
+
+    /* merge with next */
+    int next_pn = pn + num_pages;
+    int next_inuse = is_page_inuse(next_pn);
+    if (next_inuse == 0) {
+        int old_if = save_clear_if();
+        page_head_t* next_head =
+            (page_head_t*)map_phys_page(pn_to_pa(next_pn), NULL);
+        int next_size = next_head->size;
+        restore_if(old_if);
+        remove_from_bins(next_pn);
+        final_size += next_size;
+    }
+
+    add_to_bins(final_pn, final_size);
+    mutex_unlock(&mm_lock);
+}
+
+va_t map_phys_page(pa_t pa, pa_t* old_pa) {
+    pte_t* pte = get_mapped_phys_page_pte();
+    if (old_pa != NULL) {
+        *old_pa = get_page_base(*pte);
+    }
+    *pte = make_pte(pa, 0, PTE_SUPERVISOR, PTE_RW, PTE_PRESENT);
+    va_t va = get_mapped_phys_page();
+    invlpg(va);
+    return va;
+}
+
+/**
+ * @brief insert a chunk to a bin
+ * @param bin bin
+ * @param this_chunk chunk
+ * @param size size of chunk
+ */
+static void bin_insert(pa_t* bin, pa_t this_chunk, int size) {
+    int old_if = save_clear_if();
+    if (*bin == BAD_PA) {
+        page_head_t* this_head = (page_head_t*)map_phys_page(this_chunk, NULL);
+        this_head->next = this_head->prev = this_chunk;
+        this_head->size = size;
+    } else {
+        pa_t head_chunk = *bin;
+        page_head_t* head_head = (page_head_t*)map_phys_page(head_chunk, NULL);
+        pa_t tail_chunk = head_head->prev;
+        head_head->prev = this_chunk;
+        page_head_t* this_head = (page_head_t*)map_phys_page(this_chunk, NULL);
+        this_head->next = head_chunk;
+        this_head->prev = tail_chunk;
+        this_head->size = size;
+        page_head_t* tail_head = (page_head_t*)map_phys_page(tail_chunk, NULL);
+        tail_head->next = this_chunk;
+    }
+    restore_if(old_if);
+    *bin = this_chunk;
+}
+
+/**
+ * @brief remove a chunk from a bin
+ * @param bin bin
+ * @param this_chunk chunk
+ */
+static void bin_delete(pa_t* bin, pa_t this_chunk) {
+    int old_if = save_clear_if();
+    page_head_t* this_head = (page_head_t*)map_phys_page(this_chunk, NULL);
+    pa_t next_chunk = this_head->next;
+    if (*bin == this_chunk) {
+        *bin = (next_chunk == this_chunk ? BAD_PA : next_chunk);
+    }
+    if (next_chunk != this_chunk) {
+        pa_t prev_chunk = this_head->prev;
+        page_head_t* next_head = (page_head_t*)map_phys_page(next_chunk, NULL);
+        next_head->prev = prev_chunk;
+        page_head_t* prev_head = (page_head_t*)map_phys_page(prev_chunk, NULL);
+        prev_head->next = next_chunk;
+    }
+    restore_if(old_if);
+}
+
+static void add_to_bins(int pn, int size) {
+    set_page_free(pn);
+    set_page_free(pn + (size - 1));
+    pa_t this_chunk = pn_to_pa(pn);
+    pa_t* bin = &bins[find_bin(size)];
+
+    bin_insert(bin, this_chunk, size);
+
+    int old_if = save_clear_if();
+    page_foot_t* this_foot =
+        (page_foot_t*)map_phys_page(pn_to_pa(pn + (size - 1)), NULL);
+    this_foot->size = size;
+    restore_if(old_if);
+}
+
+static void remove_from_bins(int pn) {
+    pa_t this_chunk = pn_to_pa(pn);
+    int old_if = save_clear_if();
+    page_head_t* this_head = (page_head_t*)map_phys_page(this_chunk, NULL);
+    int size = this_head->size;
+    restore_if(old_if);
+    pa_t* bin = &bins[find_bin(size)];
+    bin_delete(bin, this_chunk);
+}
+
+static pa_t alloc_from_bin(pa_t* bin, int size) {
+    if (*bin == BAD_PA) {
+        return BAD_PA;
+    }
+    pa_t r_pa = BAD_PA;
+    pa_t r_pn = 0;
+    pa_t this_chunk = *bin, end = *bin;
+    do {
+        int old_if = save_clear_if();
+        page_head_t* this_head = (page_head_t*)map_phys_page(this_chunk, NULL);
+        int this_size = this_head->size;
+        pa_t next_chunk = this_head->next;
+        restore_if(old_if);
+        if (this_size > size) {
+            bin_delete(bin, this_chunk);
+            r_pa = this_chunk;
+            r_pn = pa_to_pn(r_pa);
+            add_to_bins(r_pn + size, this_size - size);
+            break;
+        } else if (this_size == size) {
+            bin_delete(bin, this_chunk);
+            r_pa = this_chunk;
+            r_pn = pa_to_pn(r_pa);
+            break;
+        }
+        this_chunk = next_chunk;
+    } while (this_chunk != end);
+    if (r_pa == BAD_PA) {
+        return BAD_PA;
+    }
+    set_page_inuse(r_pn);
+    set_page_inuse(r_pn + (size - 1));
+    return r_pa;
+}
diff --git a/kern/paging.c b/kern/paging.c
new file mode 100644
index 0000000..568db84
--- /dev/null
+++ b/kern/paging.c
@@ -0,0 +1,76 @@
+/** @file paging.c
+ *
+ *  @brief paging management functions.
+ *
+ *  @author Hanjie Wu (hanjiew)
+ *  @bug No functional bugs
+ */
+
+#include <common_kern.h>
+#include <malloc_internal.h>
+#include <stdio.h>
+#include <string.h>
+
+#include <apic.h>
+#include <mptable.h>
+#include <smp.h>
+#include <x86/asm.h>
+#include <x86/cr.h>
+
+#include <asm_instr.h>
+#include <paging.h>
+#include <sched.h>
+
+/** number of page tables for kernel memory */
+#define NUM_KERNEL_PT (USER_MEM_START / PAGE_SIZE / NUM_PAGE_ENTRY)
+
+page_directory_t* kernel_pd;
+/** page tables for kernel memory */
+static page_table_t* kernel_pt;
+
+va_t mapped_phys_pages;
+pte_t* mapped_phys_page_ptes;
+
+void paging_init() {
+    kernel_pd = (page_directory_t*)_smemalign(PAGE_SIZE, PAGE_SIZE);
+    kernel_pt = (page_table_t*)_smemalign(PAGE_SIZE, PAGE_SIZE * NUM_KERNEL_PT);
+
+    int num_cpus = smp_num_cpus();
+    mapped_phys_pages = (va_t)_smemalign(PAGE_SIZE, num_cpus * PAGE_SIZE);
+    mapped_phys_page_ptes = (pte_t*)kernel_pt + (mapped_phys_pages / PAGE_SIZE);
+
+    if (kernel_pd == NULL || kernel_pt == NULL || mapped_phys_pages == 0 ||
+        mapped_phys_page_ptes == NULL) {
+        panic("no space for kernel page table");
+    }
+
+    int i, j;
+    pa_t base = 0;
+    memset(kernel_pd, 0, sizeof(page_directory_t));
+    for (i = 0; i < (USER_MEM_START / PT_SIZE); i++) {
+        (*kernel_pd)[i] =
+            make_pde((pa_t)&kernel_pt[i], PTE_SUPERVISOR, PTE_RW, PTE_PRESENT);
+        for (j = 0; j < NUM_PAGE_ENTRY; j++) {
+            kernel_pt[i][j] =
+                make_pte(base, PTE_G, PTE_SUPERVISOR, PTE_RW, PTE_PRESENT);
+            base += PAGE_SIZE;
+        }
+    }
+
+    pa_t lapic_pa = (pa_t)smp_lapic_base();
+    pte_t* lapic_pte = (pte_t*)kernel_pt + (LAPIC_VIRT_BASE / PAGE_SIZE);
+    *lapic_pte =
+        (make_pte(lapic_pa, PTE_G, PTE_SUPERVISOR, PTE_RW, PTE_PRESENT) |
+         (PTE_PCD << PTE_PCD_SHIFT));
+    invlpg(LAPIC_VIRT_BASE);
+
+    set_cr4(get_cr4() | CR4_PSE | CR4_PGE);
+    set_cr3((uint32_t)kernel_pd);
+    set_cr0(get_cr0() | CR0_PE | CR0_PG);
+}
+
+void paging_enable() {
+    set_cr4(get_cr4() | CR4_PSE | CR4_PGE);
+    set_cr3((uint32_t)kernel_pd);
+    set_cr0(get_cr0() | CR0_PE | CR0_PG);
+}
diff --git a/kern/sched.c b/kern/sched.c
new file mode 100644
index 0000000..eb8d334
--- /dev/null
+++ b/kern/sched.c
@@ -0,0 +1,762 @@
+/** @file sched.c
+ *
+ *  @brief scheduling functions.
+ *
+ *  @author Hanjie Wu (hanjiew)
+ *  @bug No functional bugs
+ */
+
+#include <malloc_internal.h>
+#include <string.h>
+#include <x86/asm.h>
+#include <x86/cr.h>
+#include <x86/eflags.h>
+#include <x86/seg.h>
+
+#include <asm_instr.h>
+#include <loader.h>
+#include <malloc.h>
+#include <mm.h>
+#include <paging.h>
+#include <sched.h>
+#include <sync.h>
+
+/* .text, .rodata, .data+bss, stack and a heap and one for future new_pages */
+#define INIT_NUM_REGIONS 6
+
+/**
+ * @brief load a elf to memory space
+ * @param p process
+ * @param elf elf header
+ * @param exe elf file name
+ * @return 0 on success, -1 on failure
+ */
+static int process_load_elf(process_t* p, simple_elf_t* elf, char* exe);
+/**
+ * @brief load a elf segment to memory space
+ * @param p process
+ * @param f elf file entry, NULL for empty segments
+ * @param offset offset in elf file
+ * @param f_len length of data in elf file
+ * @param vaddr addr to load to
+ * @param m_len length of segment
+ * @param is_rw is segment writable
+ * @return 0 on success, -1 on failure
+ */
+static int load_segment(process_t* p,
+                        file_t* f,
+                        int offset,
+                        int f_len,
+                        va_t vaddr,
+                        int m_len,
+                        int is_rw);
+
+process_t* init_process;
+
+spl_t ready_lock = SPL_INIT;
+queue_t* ready = NULL;
+
+rb_t* threads = &rb_nil;
+mutex_t threads_lock = MUTEX_INIT;
+
+/* G means global segment */
+#define GDT_G_BIT 0x0080000000000000ull
+/* FLAG is control flags for segment */
+#define GDT_FLAG_MASK 0x00f0ff0000000000ull
+/* high part of base address */
+#define GDT_BASE_MASK_HI 0xff000000ull
+/* low part of base address */
+#define GDT_BASE_MASK_LO 0x00ffffffull
+/* position of high part of base address */
+#define GDT_BASE_SHIFT_HI (64 - 32)
+/* position of low part of base address */
+#define GDT_BASE_SHIFT_LO (40 - 24)
+/* high part of limit */
+#define GDT_LIMIT_MASK_HI 0xf0000ull
+/* low part of limit */
+#define GDT_LIMIT_MASK_LO 0x0ffffull
+/* position of high part of limit */
+#define GDT_LIMIT_SHIFT_HI (52 - 20)
+/* position of low part of limit */
+#define GDT_LIMIT_SHIFT_LO (16 - 16)
+
+/**
+ * @brief set fs
+ * @param fs fs
+ */
+void set_fs(reg_t fs);
+
+void setup_percpu(percpu_t* percpu) {
+    uint64_t* gdt = (uint64_t*)gdt_base();
+    uint64_t ds = gdt[SEGSEL_KERNEL_DS_IDX];
+    /* copy ds's flags so we do not need to create one */
+    uint64_t ds_flags = (ds & GDT_FLAG_MASK);
+    uint64_t base = (uint64_t)(uint32_t)percpu;
+    uint64_t limit = base + sizeof(percpu_t) - 1;
+    uint64_t fs = (((base & GDT_BASE_MASK_HI) << GDT_BASE_SHIFT_HI) |
+                   ((base & GDT_BASE_MASK_LO) << GDT_BASE_SHIFT_LO) |
+                   ((limit & GDT_LIMIT_MASK_HI) << GDT_LIMIT_SHIFT_HI) |
+                   ((limit & GDT_LIMIT_MASK_LO) << GDT_LIMIT_SHIFT_LO) |
+                   (ds_flags & (~GDT_G_BIT)));
+    gdt[SEGSEL_KERNEL_FS_IDX] = fs;
+    lgdt(gdt, GDT_SEGS * sizeof(uint64_t) - 1);
+    set_fs(SEGSEL_KERNEL_FS);
+}
+
+void setup_kth(thread_t* kthread, process_t* kprocess) {
+    memset(kthread, 0, sizeof(thread_t));
+    memset(kprocess, 0, sizeof(process_t));
+    kprocess->refcount = 1;
+    kprocess->cr3 = (pa_t)kernel_pd;
+    kthread->process = kprocess;
+    set_current(kthread);
+    set_kthread(kthread);
+}
+
+/* exit value when all tasks vanish and status is never set, no religious
+ * meaning
+ */
+#define DEFAULT_EXIT_VALUE 666
+
+thread_t* create_empty_process() {
+    process_t* p = smalloc(sizeof(process_t));
+    if (p == NULL) {
+        goto alloc_pcb_fail;
+    }
+    thread_t* t = smalloc(sizeof(thread_t));
+    if (t == NULL) {
+        goto alloc_tcb_fail;
+    }
+    t->stack = smalloc(K_STACK_SIZE);
+    if (t->stack == NULL) {
+        goto alloc_thread_stack_fail;
+    }
+    p->exit_value = DEFAULT_EXIT_VALUE;
+    p->parent = NULL;
+    p->refcount_lock = MUTEX_INIT;
+    p->refcount = 1;
+    p->threads = NULL;
+    p->nchilds = 0;
+    p->live_childs = NULL;
+    p->dead_childs = NULL;
+    p->nwaiters = 0;
+    p->wait_lock = MUTEX_INIT;
+    p->wait_cv = CV_INIT;
+    if (vector_init(&p->regions, sizeof(region_t), INIT_NUM_REGIONS) != 0) {
+        goto alloc_region_fail;
+    }
+
+    p->cr3 = alloc_user_pages(1);
+    if (p->cr3 == 0) {
+        goto alloc_pd_fail;
+    }
+    int old_if = save_clear_if();
+    page_directory_t* pd = (page_directory_t*)map_phys_page(p->cr3, NULL);
+    memset(pd, 0, PAGE_SIZE);
+    int i;
+    /* copy kernel direct mapping */
+    for (i = 0; i < USER_PD_START; i++) {
+        (*pd)[i] = (*kernel_pd)[i];
+    }
+    restore_if(old_if);
+    p->mm_lock = MUTEX_INIT;
+
+    t->status = THREAD_DEAD;
+    t->status_lock = SPL_INIT;
+    t->pending_exit = 0;
+    queue_insert_head(&p->threads, &t->process_link);
+    t->rb_node.parent = NULL; /* mark that the thread is not added to rbtree */
+    t->process = p;
+    t->eip3 = 0;
+    t->esp0 = t->kernel_esp = (reg_t)&t->stack[K_STACK_SIZE];
+    t->eip0 = 0;
+    t->df3 = 0;
+    return t;
+
+alloc_pd_fail:
+    vector_free(&p->regions);
+alloc_region_fail:
+    sfree(t->stack, K_STACK_SIZE);
+alloc_thread_stack_fail:
+    sfree(t, sizeof(thread_t));
+alloc_tcb_fail:
+    sfree(p, sizeof(process_t));
+alloc_pcb_fail:
+    return NULL;
+}
+
+static int process_load_elf(process_t* p, simple_elf_t* elf, char* exe) {
+    file_t* f = find_file(exe);
+
+    if (elf->e_txtlen != 0 &&
+        load_segment(p, f, elf->e_txtoff, elf->e_txtlen, elf->e_txtstart,
+                     elf->e_txtlen, 0) != 0) {
+        goto load_segment_fail;
+    }
+    if (elf->e_rodatlen != 0 &&
+        load_segment(p, f, elf->e_rodatoff, elf->e_rodatlen, elf->e_rodatstart,
+                     elf->e_rodatlen, 0) != 0) {
+        goto load_segment_fail;
+    }
+    if (elf->e_datlen != 0 &&
+        load_segment(p, f, elf->e_datoff, elf->e_datlen, elf->e_datstart,
+                     elf->e_datlen, 1) != 0) {
+        goto load_segment_fail;
+    }
+    /* if data segment is loaded, try to load bss after data */
+    if (elf->e_datlen != 0) {
+        if (elf->e_bsslen != 0) {
+            /* allow bss to start from unaligned/overlapped address */
+            va_t bss_start = (elf->e_bssstart & PAGE_BASE_MASK);
+            va_t bss_end = ((elf->e_bssstart + elf->e_bsslen + PAGE_SIZE) &
+                            PAGE_BASE_MASK);
+            va_t data_start = (elf->e_datstart & PAGE_BASE_MASK);
+            va_t data_end = ((elf->e_datstart + elf->e_datlen + PAGE_SIZE) &
+                             PAGE_BASE_MASK);
+            if (bss_start >= data_start && bss_start < data_end) {
+                /* append bss after data */
+                bss_start = data_end;
+            }
+            /* let add_region handle overlap/overflow problem */
+            if ((bss_end > bss_start) &&
+                load_segment(p, NULL, 0, 0, bss_start, bss_end - bss_start,
+                             1) != 0) {
+                goto load_segment_fail;
+            };
+        }
+    } else {
+        if (elf->e_bsslen != 0 && load_segment(p, NULL, 0, 0, elf->e_bssstart,
+                                               elf->e_bsslen, 1) != 0) {
+            goto load_segment_fail;
+        }
+    }
+
+    if (load_segment(p, NULL, 0, 0, DEFAULT_STACK_POS, DEFAULT_STACK_SIZE, 1)) {
+        goto load_segment_fail;
+    }
+    return 0;
+
+load_segment_fail:
+    return -1;
+}
+
+thread_t* create_process(int tid, char* exe, int argc, const char** argv) {
+    thread_t* t = create_empty_process();
+    if (t == NULL) {
+        goto alloc_tcb_fail;
+    }
+    t->process->pid = t->rb_node.key = ((tid == 0) ? alloc_tid() : tid);
+
+    /* temporarily use new process's cr3 to load elf */
+    reg_t old_cr3 = get_current()->process->cr3;
+    get_current()->process->cr3 = t->process->cr3;
+    set_cr3(t->process->cr3);
+
+    simple_elf_t elf;
+    if (elf_load_helper(&elf, exe) != ELF_SUCCESS ||
+        process_load_elf(t->process, &elf, exe) != 0) {
+        goto load_elf_fail;
+    }
+
+    unsigned long* argv_addrs = smalloc(argc * sizeof(unsigned long));
+    if (argv_addrs == NULL) {
+        goto alloc_argc_addr_fail;
+    }
+    char* esp = (char*)(DEFAULT_STACK_END);
+    int i, len, total = 0;
+    for (i = argc - 1; i >= 0; i--) {
+        len = strlen(argv[i]);
+        if (len + total > MAX_TOTAL_ARG_LEN) {
+            goto load_elf_fail;
+        }
+        esp -= (len + 1);
+        memcpy(esp, argv[i], len + 1);
+        argv_addrs[i] = (unsigned long)esp;
+    }
+    unsigned long* new_esp =
+        (unsigned long*)(((va_t)esp) & (~(sizeof(va_t) - 1)));
+    --new_esp;
+    *new_esp = 0;
+    for (i = argc - 1; i >= 0; i--) {
+        --new_esp;
+        *new_esp = argv_addrs[i];
+    }
+    unsigned long new_argv = (unsigned long)new_esp;
+    sfree(argv_addrs, argc * sizeof(unsigned long));
+
+    new_esp -= 5;
+    new_esp[0] = 0;                 /* return address */
+    new_esp[1] = argc;              /* argc */
+    new_esp[2] = new_argv;          /* argv */
+    new_esp[3] = DEFAULT_STACK_END; /* stack_hi */
+    new_esp[4] = DEFAULT_STACK_POS; /* stack_lo */
+
+    get_current()->process->cr3 = old_cr3;
+    set_cr3(old_cr3);
+
+    t->kernel_esp -= sizeof(stack_frame_t);
+    stack_frame_t* frame = (stack_frame_t*)t->kernel_esp;
+    frame->eip = (reg_t)elf.e_entry;
+    frame->cs = SEGSEL_USER_CS;
+    frame->eflags = DEFAULT_EFLAGS;
+    frame->esp = (reg_t)new_esp;
+    frame->ss = SEGSEL_USER_DS;
+    frame->eax = 0;
+    frame->ecx = 0;
+    frame->edx = 0;
+    frame->ebx = 0;
+    frame->ebp = 0;
+    frame->esi = 0;
+    frame->edi = 0;
+    frame->ds = SEGSEL_USER_DS;
+    frame->es = SEGSEL_USER_DS;
+    frame->fs = SEGSEL_USER_DS;
+    frame->gs = SEGSEL_USER_DS;
+
+    t->kernel_esp -= sizeof(yield_frame_t);
+    yield_frame_t* yf = (yield_frame_t*)t->kernel_esp;
+    yf->eflags = DEFAULT_EFLAGS;
+    yf->raddr = (reg_t)return_to_user;
+    return t;
+
+alloc_argc_addr_fail:
+load_elf_fail:
+    get_current()->process->cr3 = old_cr3;
+    set_cr3(old_cr3);
+    destroy_thread(t);
+alloc_tcb_fail:
+    return NULL;
+}
+
+void destroy_thread(thread_t* t) {
+    process_t* p = t->process;
+    sfree(t->stack, K_STACK_SIZE);
+    sfree(t, sizeof(thread_t));
+    mutex_lock(&p->refcount_lock);
+    queue_detach(&p->threads, &t->process_link);
+    p->refcount--;
+    if (p->refcount != 0) {
+        mutex_unlock(&p->refcount_lock);
+        return;
+    }
+    mutex_unlock(&p->refcount_lock);
+    int i, n = vector_size(&p->regions);
+    for (i = 0; i < n; i++) {
+        region_t* r = (region_t*)vector_at(&p->regions, i);
+        free_user_pages(r->paddr, r->size / PAGE_SIZE);
+    }
+    vector_free(&p->regions);
+
+    int old_if = save_clear_if();
+    for (i = USER_PD_START; i < NUM_PAGE_ENTRY; i++) {
+        page_directory_t* pd = (page_directory_t*)map_phys_page(p->cr3, NULL);
+        if ((*pd)[i] != BAD_PDE) {
+            pa_t pt = get_page_table((*pd)[i]);
+            free_user_pages(pt, 1);
+        }
+    }
+    restore_if(old_if);
+    free_user_pages(p->cr3, 1);
+    sfree(p, sizeof(process_t));
+}
+
+int alloc_tid() {
+    static int tid = 1;
+    static int next_check = (1 << 31);
+    if (tid == next_check) {
+        /* allocated all pids */
+        mutex_lock(&threads_lock);
+        rb_t *p, *q;
+        p = rb_min(threads);
+        if (p == &rb_nil) {
+            /* no pid inuse */
+            tid = 1;
+            next_check = (1 << 31);
+        } else {
+            while (1) {
+                q = rb_next(p);
+                if (q == &rb_nil) {
+                    /* available tids are p+1 ~ 0x7fffffff */
+                    if (p->key + 1 == (1 << 31)) {
+                        /* all pids inuse */
+                        panic("too many threads");
+                    }
+                    tid = p->key + 1;
+                    next_check = (1 << 31);
+                    break;
+                }
+                /* check until q-p>1, which gives us some free tids */
+                if (q->key == p->key + 1) {
+                    p = q;
+                    continue;
+                }
+                tid = p->key + 1;
+                next_check = q->key;
+                break;
+            }
+        }
+        mutex_unlock(&threads_lock);
+    }
+    return tid++;
+}
+
+static int load_segment(process_t* p,
+                        file_t* f,
+                        int f_off,
+                        int f_len,
+                        va_t m_off,
+                        int m_len,
+                        int is_rw) {
+    va_t m_start = (m_off & PAGE_BASE_MASK);
+    va_t m_end = ((m_off + m_len + (PAGE_SIZE - 1)) & PAGE_BASE_MASK);
+    int n_pages = (m_end - m_start) / PAGE_SIZE;
+    pa_t paddr = alloc_user_pages(n_pages);
+    if (paddr == 0) {
+        goto alloc_segment_fail;
+    }
+    /* handle address check and overlapping issues */
+    if (add_region(p, m_start, n_pages, paddr, is_rw) != 0) {
+        goto add_region_fail;
+    }
+
+    int rw = (is_rw ? PTE_RW : PTE_RO);
+    int i = 0;
+    int offset = 0;
+    /* file page table one entry per loop */
+    pa_t pt_pa = find_or_create_pt(p, m_start);
+    if (pt_pa == BAD_PA) {
+        goto add_pt_fail;
+    }
+    do {
+        offset = i * PAGE_SIZE;
+        int pt_index = get_pt_index(m_start + offset);
+        if (pt_index == 0) {
+            /* step to next page table */
+            pt_pa = find_or_create_pt(p, m_start + offset);
+            if (pt_pa == BAD_PA) {
+                goto add_pt_fail;
+            }
+        }
+
+        int old_if = save_clear_if();
+        page_table_t* pt = (page_table_t*)map_phys_page(pt_pa, NULL);
+        /* do not set P bit for ZFOD */
+        (*pt)[pt_index] = make_pte(paddr + offset, 0, PTE_USER, rw, 0);
+        restore_if(old_if);
+        invlpg(m_start + offset);
+    } while (++i < n_pages);
+
+    if (f != NULL) {
+        read_file(f, f_off, f_len, (char*)m_off);
+    }
+    return 0;
+
+add_pt_fail:
+    /* page tables are reachable from page directory so no need to free them */
+    vector_pop(&p->regions);
+add_region_fail:
+    free_user_pages(paddr, n_pages);
+alloc_segment_fail:
+    return -1;
+}
+
+pa_t find_or_create_pt(process_t* p, va_t vaddr) {
+    int old_if = save_clear_if();
+    page_directory_t* pd = (page_directory_t*)map_phys_page(p->cr3, NULL);
+    pde_t* pde = &(*pd)[get_pd_index(vaddr)];
+    if (*pde == BAD_PDE) {
+        /* add a page table */
+        pa_t pt = alloc_user_pages(1);
+        if (pt == 0) {
+            return 0;
+        }
+        va_t pt_addr = map_phys_page(pt, NULL);
+        memset((void*)pt_addr, 0, PAGE_SIZE);
+
+        map_phys_page(p->cr3, NULL);
+        *pde = make_pde(pt, PTE_USER, PTE_RW, PTE_PRESENT);
+        invlpg(vaddr);
+        restore_if(old_if);
+        return pt;
+    }
+    pa_t result = get_page_table(*pde);
+    restore_if(old_if);
+    return result;
+}
+
+int add_region(process_t* p, va_t start, int n_pages, pa_t pa, int is_rw) {
+    if (start > DEFAULT_STACK_END || start < USER_MEM_START) {
+        return -1;
+    }
+    va_t end = start + n_pages * PAGE_SIZE;
+    if (end < start) {
+        return -1;
+    }
+    int i, n = vector_size(&p->regions);
+    for (i = 0; i < n; i++) {
+        /* check overlapping */
+        region_t* r = (region_t*)vector_at(&p->regions, i);
+        va_t this_start = r->addr;
+        va_t this_end = this_start + r->size;
+        if (start >= this_start && start < this_end) {
+            return -1;
+        }
+        if (end > this_start && end <= this_end) {
+            return -1;
+        }
+        if (this_start >= start && this_start < end) {
+            return -1;
+        }
+        if (this_end > start && this_end <= end) {
+            return -1;
+        }
+    }
+    region_t newr;
+    newr.addr = start;
+    newr.size = n_pages * PAGE_SIZE;
+    newr.paddr = pa;
+    newr.is_rw = is_rw;
+    return vector_push(&p->regions, &newr);
+}
+
+thread_t* select_next() {
+    thread_t* t;
+    if (ready != NULL) {
+        t = queue_data(queue_remove_head(&ready), thread_t, sched_link);
+    } else {
+        t = get_idle();
+    }
+    return t;
+}
+
+void insert_ready_tail(thread_t* t) {
+    t->status = THREAD_READY;
+    queue_insert_tail(&ready, &t->sched_link);
+}
+
+void insert_ready_head(thread_t* t) {
+    t->status = THREAD_READY;
+    queue_insert_head(&ready, &t->sched_link);
+}
+
+reg_t save_and_setup_env(thread_t* t, reg_t esp) {
+    get_current()->kernel_esp = esp;
+    set_current(t);
+    t->status = THREAD_RUNNING;
+    set_esp0(t->esp0);
+    set_cr3(t->process->cr3);
+    return t->kernel_esp;
+}
+
+void swap_process_inplace(thread_t* newt) {
+    disable_interrupts();
+    thread_t* oldt = get_current();
+    process_t* oldp = oldt->process;
+    process_t* newp = newt->process;
+    pa_t cr3 = oldp->cr3;
+    vector_t regions = oldp->regions;
+    queue_t* p_threads = oldp->threads;
+    oldp->cr3 = newp->cr3;
+    oldp->regions = newp->regions;
+    oldp->threads = newp->threads;
+    newp->cr3 = cr3;
+    newp->regions = regions;
+    newp->threads = p_threads;
+    newt->process = oldp;
+    oldt->process = newp;
+    set_cr3(newp->cr3);
+    mutex_lock(&threads_lock);
+    /* move oldt's rbtree node to newt */
+    newt->rb_node = oldt->rb_node;
+    if (threads == &oldt->rb_node) {
+        threads = &newt->rb_node;
+    };
+    if (newt->rb_node.left != &rb_nil) {
+        newt->rb_node.left->parent = &newt->rb_node;
+    }
+    if (newt->rb_node.right != &rb_nil) {
+        newt->rb_node.right->parent = &newt->rb_node;
+    }
+    if (newt->rb_node.parent != &rb_nil) {
+        if (newt->rb_node.parent->left == &oldt->rb_node) {
+            newt->rb_node.parent->left = &newt->rb_node;
+        } else {
+            newt->rb_node.parent->right = &newt->rb_node;
+        }
+    }
+    oldt->rb_node.parent = NULL;
+    mutex_unlock(&threads_lock);
+    enable_interrupts();
+}
+
+void kill_current() {
+    thread_t* current = get_current();
+    process_t* p = current->process;
+    /* respawn important process */
+    if (current == get_idle()) {
+        if (p->refcount == 1) {
+            const char* idle_args[] = {IDLE_NAME};
+            thread_t* new_idle =
+                create_process(current->rb_node.key, IDLE_NAME, 1, idle_args);
+            if (new_idle == NULL) {
+                panic("no space to allocate idle process");
+            }
+            swap_process_inplace(new_idle);
+            set_idle(new_idle);
+        }
+    } else if (p == init_process) {
+        if (p->refcount == 1) {
+            mutex_lock(&p->wait_lock);
+            /* reclaim dead childs */
+            while (p->dead_childs != NULL) {
+                queue_t* node = p->dead_childs;
+                queue_detach(&p->dead_childs, node);
+                process_t* child_process =
+                    queue_data(node, process_t, sible_link);
+                sfree(child_process, sizeof(process_t));
+                p->nchilds--;
+            }
+            mutex_unlock(&p->wait_lock);
+            const char* init_args[] = {INIT_NAME};
+            thread_t* new_init =
+                create_process(current->rb_node.key, INIT_NAME, 1, init_args);
+            if (new_init == NULL) {
+                panic("no space to allocate init process");
+            }
+            swap_process_inplace(new_init);
+            int old_if = spl_lock(&ready_lock);
+            insert_ready_tail(new_init);
+            spl_unlock(&ready_lock, old_if);
+        }
+    }
+
+    if (current->rb_node.parent != NULL) {
+        remove_thread(current);
+    }
+
+    p = current->process;
+    mutex_lock(&p->refcount_lock);
+    p->refcount--;
+    queue_detach(&p->threads, &current->process_link);
+    int is_last = (p->refcount == 0);
+    mutex_unlock(&p->refcount_lock);
+    if (is_last != 0) {
+        /* move childs to init process */
+        mutex_lock(&p->wait_lock);
+        mutex_lock(&init_process->wait_lock);
+        while (p->live_childs != NULL) {
+            queue_t* node = p->live_childs;
+            queue_detach(&p->live_childs, node);
+            queue_insert_tail(&init_process->live_childs, node);
+            process_t* child_process = queue_data(node, process_t, sible_link);
+            child_process->parent = init_process;
+            init_process->nchilds++;
+        }
+        while (p->dead_childs != NULL) {
+            queue_t* node = p->dead_childs;
+            queue_detach(&p->dead_childs, node);
+            queue_insert_tail(&init_process->dead_childs, node);
+            process_t* child_process = queue_data(node, process_t, sible_link);
+            child_process->parent = init_process;
+            init_process->nchilds++;
+            cv_signal(&init_process->wait_cv);
+        }
+        mutex_unlock(&init_process->wait_lock);
+        mutex_unlock(&p->wait_lock);
+
+        /* free userspace memory */
+        pa_t old_cr3 = p->cr3;
+        p->cr3 = (pa_t)kernel_pd;
+        set_cr3((pa_t)kernel_pd);
+        int i, n = vector_size(&p->regions);
+        for (i = 0; i < n; i++) {
+            region_t* r = (region_t*)vector_at(&p->regions, i);
+            free_user_pages(r->paddr, r->size / PAGE_SIZE);
+        }
+        vector_free(&p->regions);
+
+        int old_if = save_clear_if();
+        for (i = USER_PD_START; i < NUM_PAGE_ENTRY; i++) {
+            page_directory_t* pd =
+                (page_directory_t*)map_phys_page(old_cr3, NULL);
+            if ((*pd)[i] != BAD_PDE) {
+                pa_t pt = get_page_table((*pd)[i]);
+                free_user_pages(pt, 1);
+            }
+        }
+        restore_if(old_if);
+        free_user_pages(old_cr3, 1);
+    }
+
+    /* make sure we do not get swapped out before borrowing kthread's stack */
+    mutex_lock(&malloc_lock);
+    disable_interrupts();
+    current->status = THREAD_DEAD;
+    if (is_last != 0) {
+        /* we cannot switch back after p is reclaimed so we must put cv_signal
+         * after disable_interrupts
+         */
+        if (p->parent != NULL) {
+            mutex_lock(&p->parent->wait_lock);
+            queue_detach(&p->parent->live_childs, &p->sible_link);
+            queue_insert_tail(&p->parent->dead_childs, &p->sible_link);
+            cv_signal(&p->parent->wait_cv);
+            mutex_unlock(&p->parent->wait_lock);
+        } else {
+            _sfree(p, sizeof(process_t));
+        }
+    }
+    /* borrow kth's stack for freeing thread control block
+     * we can make sure kthread is not running since we are the running thread
+     * and kthread's IF is cleared so it will not be interrupted
+     */
+    thread_t* kth = get_kthread();
+    set_current(kth);
+    switch_stack_cleanup(kth->kernel_esp, current);
+}
+
+/**
+ * @brief clean thread control block and its stack
+ * @param t thread
+ */
+void cleanup_dead_thread(thread_t* t) {
+    _sfree(t->stack, K_STACK_SIZE);
+    _sfree(t, sizeof(thread_t));
+    mutex_unlock(&malloc_lock);
+    /* we will return to kthread's loop and it will yield
+     * cannot do yield here since it increases stack
+     */
+}
+
+/**
+ * @brief check if a task_vanish is pending and if so, do vanish
+ * @param f saved regs
+ */
+void check_pending_exit(stack_frame_t* f) {
+    /* only vanish before returning to userspace, otherwise some kernel
+     * structure may be jammed
+     */
+    if (get_current()->pending_exit != 0 && f->cs == SEGSEL_USER_CS) {
+        kill_current();
+    }
+}
+
+thread_t* find_thread(int tid) {
+    rb_t* result = rb_find(threads, tid);
+    if (result == NULL) {
+        return NULL;
+    }
+    return rb_data(result, thread_t, rb_node);
+}
+
+void add_thread(thread_t* t) {
+    mutex_lock(&threads_lock);
+    rb_insert(&threads, &t->rb_node);
+    mutex_unlock(&threads_lock);
+}
+
+void remove_thread(thread_t* t) {
+    mutex_lock(&threads_lock);
+    rb_delete(&threads, &t->rb_node);
+    mutex_unlock(&threads_lock);
+}
diff --git a/kern/sched_asm.S b/kern/sched_asm.S
new file mode 100644
index 0000000..747598e
--- /dev/null
+++ b/kern/sched_asm.S
@@ -0,0 +1,67 @@
+/** @file sched_asm.S
+ *
+ *  @brief scheduling functions.
+ *
+ *  @author Hanjie Wu (hanjiew)
+ *  @bug No functional bugs
+ */
+
+#include <x86/seg.h>
+
+.text
+
+.global set_fs
+.type set_fs, %function
+set_fs:
+    push 0x4(%esp)
+    pop %fs
+    ret
+
+.macro PERCPU_GETSET name offset
+.global get_\name
+.type get_\name, %function
+get_\name:
+    xor %eax, %eax
+    mov %fs:\offset(%eax), %eax
+    ret
+
+.global set_\name
+.type set_\name, %function
+set_\name:
+    xor %esi, %esi
+    mov 0x4(%esp), %eax
+    mov %eax, %fs:\offset(%esi)
+    ret
+.endm
+
+PERCPU_GETSET current 0x0
+PERCPU_GETSET idle 0x4
+PERCPU_GETSET kthread 0x8
+PERCPU_GETSET mapped_phys_page 0xc
+PERCPU_GETSET mapped_phys_page_pte 0x10
+
+.global return_to_user
+.type return_to_user, %function
+return_to_user:
+    push %esp
+    call check_pending_exit
+    add $0x4, %esp
+    pop %gs /* restore from stack_frame_t structure */
+    pop %fs
+    pop %es
+    pop %ds
+    popa
+    iret
+
+.global switch_stack_cleanup
+.type switch_stack_cleanup, %function
+switch_stack_cleanup:
+    mov 0x8(%esp), %eax
+    mov 0x4(%esp), %esp
+    push %eax
+    call cleanup_dead_thread
+    add $0x4, %esp
+    pop %ebp
+    pop %ebx
+    popf
+    ret
diff --git a/kern/sync.c b/kern/sync.c
new file mode 100644
index 0000000..4e4e6de
--- /dev/null
+++ b/kern/sync.c
@@ -0,0 +1,78 @@
+/** @file sync.c
+ *
+ *  @brief locks.
+ *
+ *  @author Hanjie Wu (hanjiew)
+ *  @bug No functional bugs
+ */
+
+#include <x86/asm.h>
+
+#include <interrupt.h>
+#include <sched.h>
+#include <sync.h>
+
+void mutex_lock(mutex_t* m) {
+    thread_t* current = get_current();
+    int old_if = spl_lock(&m->guard);
+    if (m->locked == 0) {
+        m->locked = 1;
+        spl_unlock(&m->guard, old_if);
+        return;
+    }
+    queue_insert_tail(&m->waiters, &current->sched_link);
+    current->status = THREAD_BLOCKED;
+    int old_if2 = spl_lock(&ready_lock);
+    thread_t* t = select_next();
+    spl_unlock(&ready_lock, old_if2);
+    /* release m->gaurd last, otherwise other thread may switch to us before
+     * yielding
+     */
+    yield_to_spl_unlock(t, &m->guard, old_if);
+}
+
+void mutex_unlock(mutex_t* m) {
+    int old_if = spl_lock(&m->guard);
+    if (m->waiters == NULL) {
+        m->locked = 0;
+        spl_unlock(&m->guard, old_if);
+        return;
+    }
+    /* transfer lock ownership to t */
+    thread_t* t =
+        queue_data(queue_remove_head(&m->waiters), thread_t, sched_link);
+    int old_if2 = spl_lock(&ready_lock);
+    insert_ready_head(t);
+    spl_unlock(&ready_lock, old_if2);
+    spl_unlock(&m->guard, old_if);
+}
+
+void cv_wait(cv_t* cv, mutex_t* m) {
+    thread_t* current = get_current();
+    int old_if = spl_lock(&cv->guard);
+    queue_insert_tail(&cv->waiters, &current->sched_link);
+    current->status = THREAD_BLOCKED;
+    mutex_unlock(m);
+    int old_if2 = spl_lock(&ready_lock);
+    thread_t* t = select_next();
+    spl_unlock(&ready_lock, old_if2);
+    yield_to_spl_unlock(t, &cv->guard, old_if);
+    /* some threads may jump in so a condition check in a while loop is required
+     * outside
+     */
+    mutex_lock(m);
+}
+
+void cv_signal(cv_t* cv) {
+    int old_if = spl_lock(&cv->guard);
+    if (cv->waiters == NULL) {
+        spl_unlock(&cv->guard, old_if);
+        return;
+    }
+    thread_t* t =
+        queue_data(queue_remove_head(&cv->waiters), thread_t, sched_link);
+    int old_if2 = spl_lock(&ready_lock);
+    insert_ready_head(t);
+    spl_unlock(&ready_lock, old_if2);
+    spl_unlock(&cv->guard, old_if);
+}
diff --git a/kern/sync_asm.S b/kern/sync_asm.S
new file mode 100644
index 0000000..b3fc852
--- /dev/null
+++ b/kern/sync_asm.S
@@ -0,0 +1,75 @@
+/** @file sync_asm.S
+ *
+ *  @brief locks.
+ *
+ *  @author Hanjie Wu (hanjiew)
+ *  @bug No functional bugs
+ */
+
+.text
+
+#define EFL_IF 0x00000200
+
+.global save_clear_if
+.type save_clear_if, %function
+save_clear_if:
+    pushf
+    pop %eax
+    cli
+    ret
+
+.global restore_if
+.type restore_if, %function
+restore_if:
+    mov 0x4(%esp), %eax
+    push %eax
+    popf
+    ret
+
+.global spl_lock
+.type spl_lock, %function
+spl_lock:
+    pushf
+    pop %edx
+    cli
+    mov 0x4(%esp), %esi
+    mov $1, %edi
+.spl_lock_try:
+    xor %eax, %eax
+    lock cmpxchg %edi, (%esi)
+    test %eax, %eax
+    jnz .spl_lock_try
+    mov %edx, %eax
+    ret
+
+.global spl_unlock
+.type spl_unlock, %function
+spl_unlock:
+    mov 0x8(%esp), %eax
+    mov 0x4(%esp), %esi
+    xor %edx, %edx
+    mov %edx, (%esi)
+    push %eax
+    popf
+    ret
+
+.global yield_to_spl_unlock
+.type yield_to_spl_unlock, %function
+yield_to_spl_unlock:
+    mov 0xc(%esp), %edi
+    mov 0x8(%esp), %esi
+    mov 0x4(%esp), %eax
+    push %edi /* old_if, will be restored when switching back */
+    push %ebx
+    push %ebp
+    mov %esi, %ebx
+    push %esp
+    push %eax
+    call save_and_setup_env
+    mov %eax, %esp
+    xor %eax, %eax
+    mov %eax, (%ebx)
+    pop %ebp
+    pop %ebx
+    popf
+    ret
diff --git a/kern/syscall_asm.S b/kern/syscall_asm.S
new file mode 100644
index 0000000..050788a
--- /dev/null
+++ b/kern/syscall_asm.S
@@ -0,0 +1,61 @@
+/** @file syscall_asm.S
+ *
+ *  @brief syscall entries.
+ *
+ *  @author Hanjie Wu (hanjiew)
+ *  @bug No functional bugs
+ */
+
+#include <simics.h>
+#include <x86/seg.h>
+
+#define SEGSEL_KERNEL_FS SEGSEL_SPARE0
+
+.macro SYSCALL name
+.global sys_\name
+.type sys_\name, %function
+sys_\name:
+    pusha /* save a stack_frame_t structure */
+    push %ds
+    push %es
+    push %fs
+    push %gs
+    mov $SEGSEL_KERNEL_DS, %eax
+    mov %ax, %ds
+    mov %ax, %es
+    mov $SEGSEL_KERNEL_FS, %eax
+    mov %ax, %fs
+    cld
+    push %esp
+    call sys_\name\()_real
+    add $0x4, %esp
+    jmp return_to_user /* check pending exit before iret */
+.endm
+
+SYSCALL fork
+SYSCALL exec
+SYSCALL wait
+SYSCALL yield
+SYSCALL deschedule
+SYSCALL make_runnable
+SYSCALL gettid
+SYSCALL new_pages
+SYSCALL remove_pages
+SYSCALL sleep
+SYSCALL getchar
+SYSCALL readline
+SYSCALL print
+SYSCALL set_term_color
+SYSCALL set_cursor_pos
+SYSCALL get_cursor_pos
+SYSCALL thread_fork
+SYSCALL get_ticks
+SYSCALL misbehave
+SYSCALL halt
+SYSCALL task_vanish
+SYSCALL set_status
+SYSCALL vanish
+SYSCALL readfile
+SYSCALL swexn
+
+SYSCALL enosys
diff --git a/kern/syscall_io.c b/kern/syscall_io.c
new file mode 100644
index 0000000..3a9dc99
--- /dev/null
+++ b/kern/syscall_io.c
@@ -0,0 +1,151 @@
+/** @file syscall_io.c
+ *
+ *  @brief IO syscalls.
+ *
+ *  @author Hanjie Wu (hanjiew)
+ *  @bug No functional bugs
+ */
+
+#include <common_kern.h>
+#include <elf/elf_410.h>
+#include <string.h>
+#include <ureg.h>
+
+#include <x86/asm.h>
+#include <x86/cr.h>
+#include <x86/eflags.h>
+#include <x86/seg.h>
+
+#include <console.h>
+#include <kbd.h>
+#include <malloc.h>
+#include <mm.h>
+#include <paging.h>
+#include <sched.h>
+#include <usermem.h>
+
+/**
+ * @brief print() syscall handler
+ * @param f saved regs
+ */
+void sys_print_real(stack_frame_t* f) {
+    reg_t esi = f->esi;
+    int len;
+    if (copy_from_user((va_t)esi, sizeof(int), &len) != 0) {
+        goto read_fail;
+    }
+    if (len < 0) {
+        goto bad_length;
+    }
+    va_t base;
+    if (copy_from_user((va_t)esi + sizeof(va_t), sizeof(va_t), &base) != 0) {
+        goto read_fail;
+    }
+    mutex_lock(&console_lock);
+    f->eax = (reg_t)print_buf_from_user(base, len);
+    mutex_unlock(&console_lock);
+    return;
+
+read_fail:
+    f->eax = (reg_t)-1;
+    return;
+
+bad_length:
+    f->eax = (reg_t)-2;
+}
+
+/**
+ * @brief set_term_color() syscall handler
+ * @param f saved regs
+ */
+void sys_set_term_color_real(stack_frame_t* f) {
+    reg_t esi = f->esi;
+    mutex_lock(&console_lock);
+    f->eax = (reg_t)set_term_color((int)esi);
+    mutex_unlock(&console_lock);
+}
+
+/**
+ * @brief set_cursor_pos() syscall handler
+ * @param f saved regs
+ */
+void sys_set_cursor_pos_real(stack_frame_t* f) {
+    reg_t esi = f->esi;
+    int row, col;
+    if (copy_from_user((va_t)esi, sizeof(int), &row) != 0) {
+        goto read_arg_fail;
+    }
+    if (copy_from_user((va_t)(esi + sizeof(va_t)), sizeof(int), &col) != 0) {
+        goto read_arg_fail;
+    }
+    mutex_lock(&console_lock);
+    f->eax = (reg_t)set_cursor(row, col);
+    mutex_unlock(&console_lock);
+    return;
+
+read_arg_fail:
+    f->eax = (reg_t)-1;
+    return;
+}
+
+/**
+ * @brief get_cursor_pos() syscall handler
+ * @param f saved regs
+ */
+void sys_get_cursor_pos_real(stack_frame_t* f) {
+    reg_t esi = f->esi;
+    va_t prow, pcol;
+    if (copy_from_user((va_t)esi, sizeof(va_t), &prow) != 0) {
+        goto read_arg_fail;
+    }
+    if (copy_from_user((va_t)(esi + sizeof(va_t)), sizeof(va_t), &pcol) != 0) {
+        goto read_arg_fail;
+    }
+    int row, col;
+    mutex_lock(&console_lock);
+    get_cursor(&row, &col);
+    mutex_unlock(&console_lock);
+    if (copy_to_user(prow, sizeof(int), &row) != 0) {
+        goto bad_arg;
+    }
+    if (copy_to_user(pcol, sizeof(int), &col) != 0) {
+        goto bad_arg;
+    }
+    f->eax = 0;
+    return;
+
+bad_arg:
+read_arg_fail:
+    f->eax = (reg_t)-1;
+    return;
+}
+
+/**
+ * @brief getchar() syscall handler
+ * @param f saved regs
+ */
+void sys_getchar_real(stack_frame_t* f) {
+    f->eax = (reg_t)do_getchar();
+}
+
+/**
+ * @brief readline() syscall handler
+ * @param f saved regs
+ */
+void sys_readline_real(stack_frame_t* f) {
+    int len;
+    va_t buf;
+    reg_t esi = f->esi;
+    if (copy_from_user((va_t)esi, sizeof(int), &len) != 0) {
+        goto read_arg_fail;
+    }
+    if (copy_from_user((va_t)(esi + sizeof(va_t)), sizeof(va_t), &buf) != 0) {
+        goto read_arg_fail;
+    }
+    f->eax = (reg_t)do_readline(len, buf);
+    return;
+
+read_arg_fail:
+    f->eax = (reg_t)-1;
+    return;
+}
diff --git a/kern/syscall_memory.c b/kern/syscall_memory.c
new file mode 100644
index 0000000..288d6df
--- /dev/null
+++ b/kern/syscall_memory.c
@@ -0,0 +1,137 @@
+/** @file syscall_memory.c
+ *
+ *  @brief memory syscalls.
+ *
+ *  @author Hanjie Wu (hanjiew)
+ *  @bug No functional bugs
+ */
+
+#include <string.h>
+#include <common_kern.h>
+#include <elf/elf_410.h>
+#include <ureg.h>
+
+#include <x86/asm.h>
+#include <x86/cr.h>
+#include <x86/eflags.h>
+#include <x86/seg.h>
+
+#include <asm_instr.h>
+#include <malloc.h>
+#include <mm.h>
+#include <paging.h>
+#include <sched.h>
+#include <usermem.h>
+
+/**
+ * @brief new_pages() syscall handler
+ * @param f saved regs
+ */
+void sys_new_pages_real(stack_frame_t* f) {
+    reg_t esi = f->esi;
+    va_t base;
+    if (copy_from_user((va_t)esi, sizeof(va_t), &base) != 0) {
+        goto read_fail;
+    }
+    if ((base & PAGE_OFFSET_MASK) != 0) {
+        goto read_fail;
+    }
+    int len;
+    if (copy_from_user((va_t)esi + sizeof(va_t), sizeof(int), &len) != 0) {
+        goto read_fail;
+    }
+    if ((len & PAGE_OFFSET_MASK) != 0) {
+        goto read_fail;
+    }
+
+    process_t* p = get_current()->process;
+    mutex_lock(&p->mm_lock);
+    int n_pages = len / PAGE_SIZE;
+    pa_t paddr = alloc_user_pages(n_pages);
+    if (paddr == 0) {
+        goto alloc_segment_fail;
+    }
+    if (add_region(p, base, n_pages, paddr, 1) != 0) {
+        goto add_region_fail;
+    }
+
+    int i = 0;
+    int offset = 0;
+    /* file page table one entry per loop */
+    pa_t pt_pa = find_or_create_pt(p, base);
+    if (pt_pa == BAD_PA) {
+        goto add_pt_fail;
+    }
+    do {
+        offset = i * PAGE_SIZE;
+        /* step to next page table */
+        int pt_index = get_pt_index(base + offset);
+        if (pt_index == 0) {
+            pt_pa = find_or_create_pt(p, base + offset);
+            if (pt_pa == BAD_PA) {
+                goto add_pt_fail;
+            }
+        }
+
+        int old_if = save_clear_if();
+        page_table_t* pt = (page_table_t*)map_phys_page(pt_pa, NULL);
+        (*pt)[pt_index] = make_pte(paddr + offset, 0, PTE_USER, PTE_RW, 0);
+        restore_if(old_if);
+        invlpg(base + offset);
+    } while (++i < n_pages);
+    mutex_unlock(&p->mm_lock);
+    f->eax = 0;
+    return;
+
+add_pt_fail:
+    /* page tables are reachable from page directory so no need to free them */
+    vector_pop(&p->regions);
+add_region_fail:
+    free_user_pages(paddr, n_pages);
+alloc_segment_fail:
+    mutex_unlock(&p->mm_lock);
+read_fail:
+    f->eax = (reg_t)-1;
+}
+
+/**
+ * @brief remove_pages() syscall handler
+ * @param f saved regs
+ */
+void sys_remove_pages_real(stack_frame_t* f) {
+    process_t* p = get_current()->process;
+    mutex_lock(&p->mm_lock);
+    va_t base = (va_t)f->esi;
+    int i, j, n = vector_size(&p->regions);
+    for (i = 0; i < n; i++) {
+        region_t* r = (region_t*)vector_at(&p->regions, i);
+        if (base == r->addr) {
+            int n_pages = r->size / PAGE_SIZE;
+            j = 0;
+            int offset = 0;
+            pa_t pt_pa = find_or_create_pt(p, base);
+            do {
+                offset = j * PAGE_SIZE;
+                int pt_index = get_pt_index(base + offset);
+                if (pt_index == 0) {
+                    pt_pa = find_or_create_pt(p, base + offset);
+                }
+
+                int old_if = save_clear_if();
+                page_table_t* pt = (page_table_t*)map_phys_page(pt_pa, NULL);
+                (*pt)[pt_index] = BAD_PDE;
+                restore_if(old_if);
+                invlpg(base + offset);
+            } while (++j < n_pages);
+
+            free_user_pages(r->paddr, r->size / PAGE_SIZE);
+            vector_remove(&p->regions, i);
+            mutex_unlock(&p->mm_lock);
+            f->eax = 0;
+            return;
+        }
+    }
+    /* no such region */
+    mutex_unlock(&p->mm_lock);
+    f->eax = (reg_t)-1;
+}
diff --git a/kern/syscall_misc.c b/kern/syscall_misc.c
new file mode 100644
index 0000000..4c94513
--- /dev/null
+++ b/kern/syscall_misc.c
@@ -0,0 +1,169 @@
+/** @file syscall_misc.c
+ *
+ *  @brief miscellaneous syscalls.
+ *
+ *  @author Hanjie Wu (hanjiew)
+ *  @bug No functional bugs
+ */
+
+#include <simics.h>
+#include <stdio.h>
+#include <string.h>
+
+#include <common_kern.h>
+#include <elf/elf_410.h>
+#include <malloc_internal.h>
+#include <ureg.h>
+
+#include <x86/asm.h>
+#include <x86/cr.h>
+#include <x86/eflags.h>
+#include <x86/seg.h>
+
+#include <asm_instr.h>
+#include <assert.h>
+#include <loader.h>
+#include <malloc.h>
+#include <mm.h>
+#include <paging.h>
+#include <sched.h>
+#include <sync.h>
+#include <timer.h>
+#include <usermem.h>
+
+/**
+ * @brief misbehave() syscall handler
+ * @param f saved regs
+ */
+void sys_misbehave_real(stack_frame_t* f) {
+    f->eax = 0;
+}
+
+/**
+ * @brief all other syscalls handler
+ * @param f saved regs
+ */
+void sys_enosys_real(stack_frame_t* f) {
+    f->eax = (reg_t)-1;
+}
+
+/**
+ * @brief halt() syscall handler
+ * @param f saved regs
+ */
+void sys_halt_real(stack_frame_t* f) {
+    sim_halt();
+    hlt();
+}
+
+/**
+ * @brief read the "." file to user buf
+ * @param buf buffer
+ * @param count size
+ * @param offset offset
+ * @return number of bytes read, or -1 on failure
+ */
+static reg_t read_dot_file(va_t buf, int count, int offset);
+
+/**
+ * @brief readfile() syscall handler
+ * @param f saved regs
+ */
+void sys_readfile_real(stack_frame_t* f) {
+    reg_t esi = f->esi;
+    va_t pfilename, buf;
+    int count, offset;
+    if (copy_from_user((va_t)esi, sizeof(va_t), &pfilename) != 0) {
+        goto read_arg_fail;
+    }
+    if (copy_from_user((va_t)(esi + sizeof(va_t)), sizeof(va_t), &buf) != 0) {
+        goto read_arg_fail;
+    }
+    if (copy_from_user((va_t)(esi + 2 * sizeof(va_t)), sizeof(int), &count) !=
+        0) {
+        goto read_arg_fail;
+    }
+    if (copy_from_user((va_t)(esi + 3 * sizeof(va_t)), sizeof(int), &offset) !=
+        0) {
+        goto read_arg_fail;
+    }
+    if (count < 0 || offset < 0) {
+        goto read_arg_fail;
+    }
+    char* filename = copy_string_from_user(pfilename, MAX_EXECNAME_LEN);
+    if (filename == NULL) {
+        goto read_arg_fail;
+    }
+    if (strcmp(filename, ".") == 0) {
+        free(filename);
+        f->eax = read_dot_file(buf, count, offset);
+        return;
+    }
+    file_t* fp = find_file(filename);
+    if (fp == NULL) {
+        goto no_such_file;
+    }
+    if (offset > fp->execlen) {
+        goto offset_too_big;
+    }
+    int size = fp->execlen - offset;
+    if (count < size) {
+        size = count;
+    }
+    if (copy_to_user(buf, size, (void*)(fp->execbytes + offset)) != 0) {
+        goto bad_buffer;
+    }
+    f->eax = (reg_t)size;
+    return;
+
+bad_buffer:
+offset_too_big:
+no_such_file:
+    free(filename);
+read_arg_fail:
+    f->eax = (reg_t)-1;
+    return;
+}
+
+static reg_t read_dot_file(va_t buf, int count, int offset) {
+    file_t* fp;
+    int i = 0;
+    int cur = 0;
+    int written = 0, left = count;
+    while (i < exec2obj_userapp_count && left > 0) {
+        fp = &exec2obj_userapp_TOC[i];
+        int len = strlen(fp->execname) + 1;
+        if (cur + len <= offset) {
+            /* before offset */
+            cur += len;
+            i++;
+            continue;
+        }
+        int size = len;
+        const char* start = fp->execname;
+        /* write this entry to buffer */
+        if (cur < offset) {
+            size -= (offset - cur);
+            start += (offset - cur);
+        }
+        if (left < size) {
+            size = left;
+        }
+        if (copy_to_user((va_t)buf + written, size, (void*)start) != 0) {
+            return (reg_t)-1;
+        }
+        cur += len;
+        written += size;
+        left -= size;
+        i++;
+    }
+    /* write extra null byte */
+    if (left != 0) {
+        char nul = '\0';
+        if (copy_to_user((va_t)buf + written, 1, &nul) != 0) {
+            return (reg_t)-1;
+        }
+        written++;
+    }
+    return (reg_t)written;
+}
diff --git a/kern/syscall_process.c b/kern/syscall_process.c
new file mode 100644
index 0000000..6007bcd
--- /dev/null
+++ b/kern/syscall_process.c
@@ -0,0 +1,397 @@
+/** @file syscall_process.c
+ *
+ *  @brief process management syscalls.
+ *
+ *  @author Hanjie Wu (hanjiew)
+ *  @bug No functional bugs
+ */
+
+#include <simics.h>
+#include <stdio.h>
+#include <string.h>
+
+#include <common_kern.h>
+#include <elf/elf_410.h>
+#include <ureg.h>
+
+#include <x86/asm.h>
+#include <x86/cr.h>
+#include <x86/eflags.h>
+#include <x86/seg.h>
+
+#include <asm_instr.h>
+#include <assert.h>
+#include <loader.h>
+#include <malloc.h>
+#include <mm.h>
+#include <paging.h>
+#include <sched.h>
+#include <sync.h>
+#include <timer.h>
+#include <usermem.h>
+
+/**
+ * @brief gettid() syscall handler
+ * @param f saved regs
+ */
+void sys_gettid_real(stack_frame_t* f) {
+    f->eax = (reg_t)get_current()->rb_node.key;
+}
+
+/**
+ * @brief copy a region of current process to a process
+ * @param p target process
+ * @param src source region
+ * @return 0 on success, or -1 on failure
+ */
+static int copy_region(process_t* p, region_t* src);
+
+/**
+ * @brief fork() syscall handler
+ * @param f saved regs
+ */
+void sys_fork_real(stack_frame_t* f) {
+    thread_t* current = get_current();
+    process_t* p = current->process;
+    mutex_lock(&p->refcount_lock);
+    if (p->refcount != 1) {
+        /* reject multithread fork() */
+        mutex_unlock(&p->refcount_lock);
+        goto fork_multiple_threads;
+    }
+    mutex_unlock(&p->refcount_lock);
+    thread_t* t = create_empty_process();
+    if (t == NULL) {
+        goto create_thread_fail;
+    }
+    int tid = alloc_tid();
+    t->process->pid = t->rb_node.key = tid;
+    int i, n = vector_size(&p->regions);
+    for (i = 0; i < n; i++) {
+        int result =
+            copy_region(t->process, (region_t*)vector_at(&p->regions, i));
+        if (result != 0) {
+            goto copy_region_fail;
+        }
+    }
+    t->esp3 = current->esp3;
+    t->eip3 = current->eip3;
+    t->swexn_arg = current->swexn_arg;
+    t->eip0 = current->eip0;
+
+    t->kernel_esp -= sizeof(stack_frame_t);
+    stack_frame_t* frame = (stack_frame_t*)t->kernel_esp;
+    *frame = *f;
+    frame->eax = 0; /* child process will get 0 from fork() */
+
+    t->kernel_esp -= sizeof(yield_frame_t);
+    yield_frame_t* yf = (yield_frame_t*)t->kernel_esp;
+    yf->eflags = DEFAULT_EFLAGS;
+    yf->raddr = (reg_t)return_to_user;
+
+    t->process->parent = p;
+    mutex_lock(&p->wait_lock);
+    queue_insert_head(&p->live_childs, &t->process->sible_link);
+    p->nchilds++;
+    mutex_unlock(&p->wait_lock);
+    add_thread(t);
+    int old_if = spl_lock(&ready_lock);
+    insert_ready_tail(t);
+    spl_unlock(&ready_lock, old_if);
+    f->eax = (reg_t)tid;
+    return;
+
+copy_region_fail:
+    destroy_thread(t);
+create_thread_fail:
+    f->eax = (reg_t)-1;
+    return;
+
+fork_multiple_threads:
+    f->eax = (reg_t)-2;
+    return;
+}
+
+static int copy_region(process_t* p, region_t* src) {
+    process_t* cur_p = get_current()->process;
+    int n_pages = src->size / PAGE_SIZE;
+    pa_t paddr = alloc_user_pages(n_pages);
+    if (paddr == 0) {
+        goto alloc_segment_fail;
+    }
+    if (add_region(p, src->addr, n_pages, paddr, src->is_rw) != 0) {
+        goto add_region_fail;
+    }
+
+    int rw = (src->is_rw ? PTE_RW : PTE_RO);
+    int i = 0;
+    int offset = 0;
+    /* file page table one entry per loop */
+    pa_t dst_pt_pa = find_or_create_pt(p, src->addr);
+    if (dst_pt_pa == BAD_PA) {
+        goto add_pt_fail;
+    }
+    pa_t src_pt_pa = find_or_create_pt(cur_p, src->addr);
+    do {
+        offset = i * PAGE_SIZE;
+        /* step to next page table */
+        int pt_index = get_pt_index(src->addr + offset);
+        if (pt_index == 0) {
+            dst_pt_pa = find_or_create_pt(p, src->addr + offset);
+            if (dst_pt_pa == BAD_PA) {
+                goto add_pt_fail;
+            }
+            src_pt_pa = find_or_create_pt(cur_p, src->addr);
+        }
+
+        int old_if = save_clear_if();
+        /* check if source page is never accessed */
+        page_table_t* src_pt = (page_table_t*)map_phys_page(src_pt_pa, NULL);
+        if (((*src_pt)[pt_index] & (PTE_PRESENT << PTE_P_SHIFT)) != 0) {
+            /* need to copy non zero page */
+            page_table_t* dst_pt =
+                (page_table_t*)map_phys_page(dst_pt_pa, NULL);
+            (*dst_pt)[pt_index] =
+                make_pte(paddr + offset, 0, PTE_USER, rw, PTE_PRESENT);
+            char* page = (char*)map_phys_page(paddr + offset, NULL);
+            memcpy(page, (char*)(src->addr + offset), PAGE_SIZE);
+        } else {
+            /* source page is waiting for ZFOD, so dest page will also ZFOD */
+            page_table_t* dst_pt =
+                (page_table_t*)map_phys_page(dst_pt_pa, NULL);
+            (*dst_pt)[pt_index] = make_pte(paddr + offset, 0, PTE_USER, rw, 0);
+        }
+        restore_if(old_if);
+    } while (++i < n_pages);
+    return 0;
+
+add_pt_fail:
+    /* page tables are reachable from page directory so no need to free them */
+    vector_pop(&p->regions);
+add_region_fail:
+    free_user_pages(paddr, n_pages);
+alloc_segment_fail:
+    return -1;
+}
+
+/**
+ * @brief task_vanish() syscall handler
+ * @param f saved regs
+ */
+void sys_task_vanish_real(stack_frame_t* f) {
+    process_t* p = get_current()->process;
+    p->exit_value = (int)f->esi;
+    mutex_lock(&p->refcount_lock);
+    queue_t *node = p->threads, *end = p->threads;
+    do {
+        /* send a pending exit to all other threads,
+         * blocked threads will exit when the thread blocking it exits
+         * sleeping threads will exit when timer is reached
+         * threads waiting for input will exit after getting input
+         */
+        thread_t* t = queue_data(node, thread_t, process_link);
+        t->pending_exit = 1;
+        int old_if = spl_lock(&t->status_lock);
+        /* wakeup descheduled threads */
+        if (t->status == THREAD_DESCHEDULED) {
+            int old_if2 = spl_lock(&ready_lock);
+            insert_ready_tail(t);
+            spl_unlock(&ready_lock, old_if2);
+        }
+        spl_unlock(&t->status_lock, old_if);
+        node = node->next;
+    } while (node != end);
+    mutex_unlock(&p->refcount_lock);
+    kill_current();
+}
+
+/**
+ * @brief set_status() syscall handler
+ * @param f saved regs
+ */
+void sys_set_status_real(stack_frame_t* f) {
+    get_current()->process->exit_value = (int)f->esi;
+}
+
+/**
+ * @brief exec() syscall handler
+ * @param f saved regs
+ */
+void sys_exec_real(stack_frame_t* f) {
+    thread_t* current = get_current();
+    process_t* p = current->process;
+    mutex_unlock(&p->refcount_lock);
+    if (p->refcount != 1) {
+        /* reject multithread exec() */
+        mutex_unlock(&p->refcount_lock);
+        goto exec_multiple_threads;
+    }
+    mutex_unlock(&p->refcount_lock);
+    reg_t esi = f->esi;
+    va_t pexe;
+    if (copy_from_user((va_t)esi, sizeof(va_t), &pexe) != 0) {
+        goto read_exe_fail;
+    }
+    char* exe = copy_string_from_user(pexe, MAX_EXECNAME_LEN);
+    if (exe == NULL) {
+        goto read_exe_fail;
+    }
+    va_t pargv;
+    if (copy_from_user((va_t)esi + sizeof(va_t), sizeof(va_t), &pargv) != 0) {
+        goto read_argv_fail;
+    }
+    int argc = 0;
+    while (1) {
+        if (argc > MAX_NUM_ARG) {
+            goto read_argv_fail;
+        }
+        va_t argv;
+        if (copy_from_user(pargv + argc * sizeof(va_t), sizeof(va_t), &argv) !=
+            0) {
+            goto read_argv_fail;
+        }
+        if (argv == 0) {
+            break;
+        }
+        argc++;
+    }
+    char** argv_buf = smalloc(argc * sizeof(char*));
+    if (argv_buf == NULL) {
+        goto read_argv_fail;
+    }
+    int i;
+    for (i = 0; i < argc; i++) {
+        argv_buf[i] = copy_string_from_user(((va_t*)pargv)[i], MAX_ARG_LEN);
+        if (argv_buf[i] == NULL) {
+            goto read_argv_buf_fail;
+        }
+    }
+
+    /* we create a new process and swap to it so we can recover if process
+     * creation fails
+     */
+    thread_t* t =
+        create_process(current->rb_node.key, exe, argc, (const char**)argv_buf);
+    if (t == NULL) {
+        goto create_process_fail;
+    }
+    for (i = argc - 1; i >= 0; i--) {
+        free(argv_buf[i]);
+    }
+    sfree(argv_buf, argc * sizeof(char*));
+    free(exe);
+    swap_process_inplace(t);
+    int old_if = spl_lock(&ready_lock);
+    insert_ready_tail(t);
+    spl_unlock(&ready_lock, old_if);
+    kill_current();
+
+create_process_fail:
+read_argv_buf_fail:
+    for (i--; i >= 0; i--) {
+        free(argv_buf[i]);
+    }
+    sfree(argv_buf, argc * sizeof(char*));
+read_argv_fail:
+    free(exe);
+read_exe_fail:
+    f->eax = (reg_t)-1;
+    return;
+
+exec_multiple_threads:
+    f->eax = (reg_t)-2;
+    return;
+}
+
+/**
+ * @brief wait() syscall handler
+ * @param f saved regs
+ */
+void sys_wait_real(stack_frame_t* f) {
+    /* it may be possible that pstatus is not valid when calling wait() and then
+     * become valid after other thread allocates pages so we do not do check
+     * now
+     */
+    va_t pstatus = f->esi;
+    thread_t* current = get_current();
+    process_t* p = current->process;
+    /* it is possible that a process create multiple child processes and then
+     * create multiple threads and then call wait() in these threads, so we need
+     * to handle this case and count the waiting threads
+     */
+    mutex_lock(&p->wait_lock);
+    if (p->nchilds <= p->nwaiters) {
+        /* Pigeonhole principle prevents us to get a child in future even if
+         * there are some childs
+         */
+        mutex_unlock(&p->wait_lock);
+        goto no_child_to_wait;
+    }
+    p->nwaiters++;
+    while (p->dead_childs == NULL) {
+        cv_wait(&p->wait_cv, &p->wait_lock);
+    }
+    process_t* child = queue_data(p->dead_childs, process_t, sible_link);
+    /* copy the exit status first so we do not need to put the child back to the
+     * queue if copy fails
+     */
+    if (pstatus != 0 &&
+        copy_to_user(pstatus, sizeof(int), &child->exit_value) != 0) {
+        p->nwaiters--;
+        mutex_unlock(&p->wait_lock);
+        goto bad_pstatus;
+    }
+    queue_remove_head(&p->dead_childs);
+    p->nchilds--;
+    p->nwaiters--;
+    mutex_unlock(&p->wait_lock);
+    f->eax = (reg_t)child->pid;
+    sfree(child, sizeof(process_t));
+    return;
+
+bad_pstatus:
+    f->eax = (reg_t)-1;
+    return;
+
+no_child_to_wait:
+    f->eax = (reg_t)-2;
+    return;
+}
+
+/**
+ * @brief sleep() syscall handler
+ * @param f saved regs
+ */
+void sys_sleep_real(stack_frame_t* f) {
+    int dt = (int)f->esi;
+    if (dt <= 0) {
+        f->eax = (reg_t)dt;
+        return;
+    }
+    thread_t* current = get_current();
+    heap_node_t node;
+    node.key = ticks + dt;
+    node.value = (void*)current;
+    int old_if = spl_lock(&timer_lock);
+    if (heap_insert(&timers, &node) != 0) {
+        spl_unlock(&timer_lock, old_if);
+        f->eax = (reg_t)-2;
+        return;
+    }
+    int old_if2 = spl_lock(&ready_lock);
+    current->status = THREAD_SLEEPING;
+    thread_t* t = select_next();
+    spl_unlock(&ready_lock, old_if2);
+    yield_to_spl_unlock(t, &timer_lock, old_if);
+    f->eax = 0;
+    return;
+}
+
+/**
+ * @brief get_ticks() syscall handler
+ * @param f saved regs
+ */
+void sys_get_ticks_real(stack_frame_t* f) {
+    f->eax = (reg_t)ticks;
+    return;
+}
diff --git a/kern/syscall_thread.c b/kern/syscall_thread.c
new file mode 100644
index 0000000..d8984b0
--- /dev/null
+++ b/kern/syscall_thread.c
@@ -0,0 +1,274 @@
+/** @file syscall_thread.c
+ *
+ *  @brief thread management syscalls.
+ *
+ *  @author Hanjie Wu (hanjiew)
+ *  @bug No functional bugs
+ */
+
+#include <string.h>
+
+#include <common_kern.h>
+#include <elf/elf_410.h>
+#include <simics.h>
+#include <ureg.h>
+
+#include <x86/asm.h>
+#include <x86/cr.h>
+#include <x86/eflags.h>
+#include <x86/seg.h>
+
+#include <asm_instr.h>
+#include <assert.h>
+#include <malloc.h>
+#include <mm.h>
+#include <paging.h>
+#include <sched.h>
+#include <usermem.h>
+
+/**
+ * @brief thread_fork() syscall handler
+ * @param f saved regs
+ */
+void sys_thread_fork_real(stack_frame_t* f) {
+    thread_t* current = get_current();
+    process_t* p = current->process;
+    thread_t* t = smalloc(sizeof(thread_t));
+    if (t == NULL) {
+        goto alloc_tcb_fail;
+    }
+    t->stack = smemalign(PAGE_SIZE, K_STACK_SIZE);
+    if (t->stack == NULL) {
+        goto alloc_thread_stack_fail;
+    }
+    int tid = alloc_tid();
+    t->rb_node.key = tid;
+    t->status = THREAD_DEAD;
+    t->status_lock = SPL_INIT;
+    t->pending_exit = current->pending_exit;
+    t->esp3 = current->esp3;
+    t->eip3 = current->eip3;
+    t->df3 = current->df3;
+    t->swexn_arg = current->swexn_arg;
+    t->esp0 = t->kernel_esp = (reg_t)&t->stack[K_STACK_SIZE];
+    t->eip0 = current->eip0;
+
+    t->kernel_esp -= sizeof(stack_frame_t);
+    stack_frame_t* frame = (stack_frame_t*)t->kernel_esp;
+    *frame = *f;
+    frame->eax = 0;
+
+    t->kernel_esp -= sizeof(yield_frame_t);
+    yield_frame_t* yf = (yield_frame_t*)t->kernel_esp;
+    yf->eflags = DEFAULT_EFLAGS;
+    yf->raddr = (reg_t)return_to_user;
+
+    t->process = p;
+    mutex_lock(&p->refcount_lock);
+    p->refcount++;
+    queue_insert_tail(&p->threads, &t->process_link);
+    mutex_unlock(&p->refcount_lock);
+    add_thread(t);
+    int old_if = spl_lock(&ready_lock);
+    insert_ready_tail(t);
+    spl_unlock(&ready_lock, old_if);
+    f->eax = (reg_t)tid;
+    return;
+
+alloc_thread_stack_fail:
+    sfree(t, sizeof(thread_t));
+alloc_tcb_fail:
+    f->eax = (reg_t)-1;
+}
+
+/**
+ * @brief deschedule() syscall handler
+ * @param f saved regs
+ */
+void sys_deschedule_real(stack_frame_t* f) {
+    va_t preject = (va_t)f->esi;
+    int reject;
+    thread_t* current = get_current();
+    int old_if = spl_lock(&current->status_lock);
+    if (copy_from_user(preject, sizeof(int), &reject) != 0) {
+        spl_unlock(&current->status_lock, old_if);
+        f->eax = (reg_t)-1;
+        return;
+    }
+    if (reject != 0 || current->pending_exit != 0) {
+        spl_unlock(&current->status_lock, old_if);
+        f->eax = (reg_t)0;
+        return;
+    }
+    int old_if2 = spl_lock(&ready_lock);
+    current->status = THREAD_DESCHEDULED;
+    thread_t* t = select_next();
+    spl_unlock(&ready_lock, old_if2);
+    /* release status_lock last to make sure nobody make us runnable before
+     * deschedule
+     */
+    yield_to_spl_unlock(t, &current->status_lock, old_if);
+    f->eax = (reg_t)0;
+    return;
+}
+
+/**
+ * @brief make_runnable() syscall handler
+ * @param f saved regs
+ */
+void sys_make_runnable_real(stack_frame_t* f) {
+    int tid = (int)f->esi;
+    mutex_lock(&threads_lock);
+    thread_t* t = find_thread(tid);
+    if (t == NULL) {
+        mutex_unlock(&threads_lock);
+        f->eax = (reg_t)-2;
+        return;
+    }
+    int old_if = spl_lock(&t->status_lock);
+    /* we must hold threads_lock before making sure t is descheduled, otherwise
+     * if t is running/ready, t can be freed at any time
+     */
+    if (t->status != THREAD_DESCHEDULED) {
+        spl_unlock(&t->status_lock, old_if);
+        mutex_unlock(&threads_lock);
+        f->eax = (reg_t)-3;
+        return;
+    }
+    mutex_unlock(&threads_lock);
+    /* must lock ready lock before setting status to READY otherwise yield() may
+     * yield to it before we insert it into ready queue
+     */
+    int old_if2 = spl_lock(&ready_lock);
+    t->status = THREAD_READY;
+    insert_ready_tail(t);
+    spl_unlock(&ready_lock, old_if2);
+    spl_unlock(&t->status_lock, old_if);
+    f->eax = (reg_t)0;
+    return;
+}
+
+/**
+ * @brief vanish() syscall handler
+ * @param f saved regs
+ */
+void sys_vanish_real(stack_frame_t* f) {
+    kill_current();
+}
+
+/**
+ * @brief yield() syscall handler
+ * @param f saved regs
+ */
+void sys_yield_real(stack_frame_t* f) {
+    int tid = (int)f->esi;
+    if (tid == -1) {
+        int old_if = spl_lock(&ready_lock);
+        insert_ready_tail(get_current());
+        thread_t* t = select_next();
+        yield_to_spl_unlock(t, &ready_lock, old_if);
+        f->eax = (reg_t)0;
+        return;
+    }
+    mutex_lock(&threads_lock);
+    thread_t* t = find_thread(tid);
+    if (t == NULL) {
+        mutex_unlock(&threads_lock);
+        f->eax = (reg_t)-2;
+        return;
+    }
+    /* we must hold threads_lock and ready_lock before making sure t is ready
+     * if we do not have threads_lock, t may be freed
+     * if we do not have ready_lock, t may be turned from ready to running by
+     * other processors
+     */
+    int old_if = spl_lock(&ready_lock);
+    if (t->status == THREAD_RUNNING) {
+        /* t is running or other processor, no need to yield */
+        t = select_next();
+    } else if (t->status == THREAD_READY) {
+        queue_detach(&ready, &t->sched_link);
+    } else {
+        spl_unlock(&ready_lock, old_if);
+        mutex_unlock(&threads_lock);
+        f->eax = (reg_t)-1;
+        return;
+    }
+    /* if we are sure t is ready and remove it from ready queue, it will not
+     * suddenly run so we can make sure t will not be freed
+     */
+    mutex_unlock(&threads_lock);
+    insert_ready_tail(get_current());
+    yield_to_spl_unlock(t, &ready_lock, old_if);
+    f->eax = (reg_t)0;
+    return;
+}
+
+/* eflags fields that are allowed to be changed by user */
+#define EFLAGS_USER_MASK                                                     \
+    (EFL_CF | EFL_PF | EFL_AF | EFL_ZF | EFL_SF | EFL_TF | EFL_DF | EFL_OF | \
+     EFL_RF)
+
+/**
+ * @brief swexn() syscall handler
+ * @param f saved regs
+ */
+void sys_swexn_real(stack_frame_t* f) {
+    thread_t* current = get_current();
+    reg_t args[4]; /* esp3, eip3, arg, ureg */
+    reg_t esi = f->esi;
+    if (copy_from_user(esi, 4 * sizeof(reg_t), args) != 0) {
+        goto read_arg_fail;
+    }
+    reg_t esp3 = args[0], eip3 = args[1], pureg = args[3];
+    if (esp3 != 0 && eip3 != 0) {
+        /* for unlcear "stack end" definition */
+        esp3 = (esp3 & (~(sizeof(va_t) - 1)));
+        /* check first, will register after successful ureg copy */
+        if (eip3 < USER_MEM_START || eip3 >= DEFAULT_STACK_END ||
+            esp3 < USER_MEM_START || esp3 >= DEFAULT_STACK_END) {
+            goto bad_user_entry;
+        }
+    }
+    if (pureg != 0) {
+        ureg_t ureg;
+        if (copy_from_user((va_t)pureg, sizeof(ureg_t), &ureg) != 0) {
+            goto bad_user_entry;
+        }
+        /* segment regs are ignored since they cannot be changed */
+        /* only user fields in eflags are allowed to be changed */
+        if ((ureg.eflags & (~EFLAGS_USER_MASK)) != DEFAULT_EFLAGS) {
+            goto bad_user_entry;
+        }
+        f->eip = ureg.eip;
+        f->eflags = ureg.eflags;
+        f->esp = ureg.esp;
+        f->eax = ureg.eax;
+        f->ecx = ureg.ecx;
+        f->edx = ureg.edx;
+        f->ebx = ureg.ebx;
+        f->ebp = ureg.ebp;
+        f->esi = ureg.esi;
+        f->edi = ureg.edi;
+    } else {
+        f->eax = 0;
+    }
+    if (esp3 != 0 && eip3 != 0) {
+        current->esp3 = esp3;
+        current->eip3 = eip3;
+        current->swexn_arg = args[2];
+    } else {
+        current->eip3 = 0;
+    }
+    /* clear swexn flag after success swexn call */
+    current->df3 = 0;
+    return;
+
+bad_user_entry:
+    f->eax = (reg_t)-2;
+    return;
+
+read_arg_fail:
+    f->eax = (reg_t)-1;
+    return;
+}
diff --git a/kern/timer.c b/kern/timer.c
new file mode 100644
index 0000000..7f39f06
--- /dev/null
+++ b/kern/timer.c
@@ -0,0 +1,74 @@
+/** @file timer.c
+ *
+ *  @brief timer functions.
+ *
+ *  @author Hanjie Wu (hanjiew)
+ *  @bug No functional bugs
+ */
+
+#include <common_kern.h>
+#include <stdio.h>
+#include <string.h>
+
+#include <assert.h>
+#include <x86/asm.h>
+#include <x86/interrupt_defines.h>
+#include <x86/timer_defines.h>
+
+#include <interrupt.h>
+#include <sched.h>
+#include <sync.h>
+#include <timer.h>
+
+unsigned int ticks = 0;
+
+spl_t timer_lock = SPL_INIT;
+
+heap_t timers;
+
+/* we want a 2ms thread switch but since sometimes interrupts are disabled, we
+ * set a higher rate to compensate this
+ */
+#define TIMER_FREQ 1000
+
+void timer_init() {
+    int counter = TIMER_RATE / TIMER_FREQ;
+    outb(TIMER_MODE_IO_PORT, TIMER_SQUARE_WAVE);
+    outb(TIMER_PERIOD_IO_PORT, counter & 0xFF);
+    outb(TIMER_PERIOD_IO_PORT, (counter >> 8) & 0xFF);
+    if (heap_init(&timers) != 0) {
+        panic("no space to initialize timer heap");
+    }
+}
+
+/**
+ * @brief check expired timers
+ */
+static void check_timers() {
+    int old_if = spl_lock(&timer_lock);
+    heap_node_t* node;
+    while ((node = heap_peak(&timers)) != NULL) {
+        if (node->key > ticks) {
+            break;
+        }
+        thread_t* t = (thread_t*)node->value;
+        heap_pop(&timers);
+        int old_if2 = spl_lock(&ready_lock);
+        insert_ready_tail(t);
+        spl_unlock(&ready_lock, old_if2);
+    }
+    spl_unlock(&timer_lock, old_if);
+}
+
+void timer_handler_real() {
+    pic_acknowledge(TIMER_IRQ);
+    ticks++;
+    check_timers();
+    int old_if = spl_lock(&ready_lock);
+    thread_t* current = get_current();
+    if (current != get_idle()) {
+        insert_ready_tail(current);
+    }
+    thread_t* t = select_next();
+    yield_to_spl_unlock(t, &ready_lock, old_if);
+}
diff --git a/kern/usermem.c b/kern/usermem.c
new file mode 100644
index 0000000..717cdbe
--- /dev/null
+++ b/kern/usermem.c
@@ -0,0 +1,153 @@
+/** @file usermem.c
+ *
+ *  @brief userspace r/w functions.
+ *
+ *  @author Hanjie Wu (hanjiew)
+ *  @bug No functional bugs
+ */
+
+#include <stdlib.h>
+#include <string.h>
+
+#include <common_kern.h>
+#include <x86/asm.h>
+
+#include <console.h>
+#include <mm.h>
+#include <paging.h>
+#include <sched.h>
+
+/**
+ * @brief try to read a byte from userspace
+ * @param addr address
+ * @param output output byte if successful
+ * @return 0 on success, jump to usermem_fail on failure
+ */
+int try_read(va_t addr, char* output);
+/**
+ * @brief try to write a byte to userspace
+ * @param addr address
+ * @param c byte to write
+ * @return 0 on success, jump to usermem_fail on failure
+ */
+int try_write(va_t addr, char c);
+
+/**
+ * @brief tell the calling function the r/w failed
+ * @return -1
+ */
+int usermem_fail();
+
+/**
+ * @brief setup fault handler before r/w
+ * @return old fault handler
+ */
+static reg_t usermem_setup() {
+    thread_t* current = get_current();
+    reg_t old_eip0 = current->eip0;
+    current->eip0 = (reg_t)usermem_fail;
+    return old_eip0;
+}
+
+/**
+ * @brief restore old fault handler
+ * @param old_eip0 old fault handler
+ */
+static void usermem_finish(reg_t old_eip0) {
+    get_current()->eip0 = old_eip0;
+}
+
+int copy_from_user(va_t addr, int size, void* buf) {
+    va_t end = addr + size;
+    if (addr < USER_MEM_START || end < addr || end >= DEFAULT_STACK_END) {
+        return -1;
+    }
+    reg_t old_eip0 = usermem_setup();
+    int i, result = 0;
+    for (i = 0; i < size; i++) {
+        if (try_read(addr + i, (char*)buf + i) != 0) {
+            result = -1;
+            break;
+        }
+    }
+    usermem_finish(old_eip0);
+    return result;
+}
+
+int copy_to_user(va_t addr, int size, void* buf) {
+    va_t end = addr + size;
+    if (addr < USER_MEM_START || end < addr || end >= DEFAULT_STACK_END) {
+        return -1;
+    }
+    reg_t old_eip0 = usermem_setup();
+    int i, result = 0;
+    for (i = 0; i < size; i++) {
+        if (try_write(addr + i, *((char*)buf + i)) != 0) {
+            result = -1;
+            break;
+        }
+    }
+    usermem_finish(old_eip0);
+    return result;
+}
+
+char* copy_string_from_user(va_t addr, int maxlen) {
+    if (addr < USER_MEM_START || addr >= DEFAULT_STACK_END) {
+        return NULL;
+    }
+    if (DEFAULT_STACK_END - addr < maxlen) {
+        maxlen = DEFAULT_STACK_END - addr;
+    }
+    reg_t old_eip0 = usermem_setup();
+    int len = 0, buflen = 3 * sizeof(int);
+    char* buf = malloc(buflen);
+    char c;
+    if (buf == NULL) {
+        goto read_string_finished;
+    }
+    while (1) {
+        if (len >= maxlen || try_read(addr + len, &c) != 0) {
+            free(buf);
+            buf = NULL;
+            break;
+        }
+
+        buf[len++] = c;
+        if (c == '\0') {
+            break;
+        }
+
+        if (len >= buflen) {
+            buflen <<= 1;
+            char* result = realloc(buf, buflen);
+            if (result == NULL) {
+                free(buf);
+                buf = NULL;
+                break;
+            }
+            buf = result;
+        }
+    }
+read_string_finished:
+    usermem_finish(old_eip0);
+    return buf;
+}
+
+int print_buf_from_user(va_t addr, int len) {
+    va_t end = addr + len;
+    if (addr < USER_MEM_START || end < addr || end >= DEFAULT_STACK_END) {
+        return -1;
+    }
+    reg_t old_eip0 = usermem_setup();
+    int i, result = 0;
+    char c;
+    for (i = 0; i < len; i++) {
+        if (try_read(addr + i, &c) != 0) {
+            result = -1;
+            break;
+        }
+        putbyte(c);
+    }
+    usermem_finish(old_eip0);
+    return result;
+}
diff --git a/kern/usermem_asm.S b/kern/usermem_asm.S
new file mode 100644
index 0000000..0eee6f8
--- /dev/null
+++ b/kern/usermem_asm.S
@@ -0,0 +1,35 @@
+/** @file usermem_asm.S
+ *
+ *  @brief userspace r/w functions.
+ *
+ *  @author Hanjie Wu (hanjiew)
+ *  @bug No functional bugs
+ */
+
+.text
+
+.global try_read
+.type try_read, %function
+try_read:
+    mov 0x4(%esp), %eax
+    mov 0x8(%esp), %esi
+    mov (%eax), %al
+    mov %al, (%esi)
+    xor %eax, %eax
+    ret
+
+.global try_write
+.type try_write, %function
+try_write:
+    mov 0x4(%esp), %eax
+    mov 0x8(%esp), %edx
+    mov %dl, (%eax)
+    xor %eax, %eax
+    ret
+
+/* unsuccessful r/w will jump to this function and we return 1 */
+.global usermem_fail
+.type usermem_fail, %function
+usermem_fail:
+    mov $0xffffffff, %eax
+    ret