Merge branch 'thread' into fs

Conflicts:
	.gitignore
	Makefile
	conf/lab.mk
    kernel/param.h

25 files changed, 2048 insertions, 0 deletions

diff --git a/user/alarmtest.c b/user/alarmtest.c
new file mode 100644
index 0000000..b8d85f7
--- /dev/null
+++ b/user/alarmtest.c
@@ -0,0 +1,193 @@
+//
+// test program for the alarm lab.
+// you can modify this file for testing,
+// but please make sure your kernel
+// modifications pass the original
+// versions of these tests.
+//
+
+#include "kernel/param.h"
+#include "kernel/types.h"
+#include "kernel/stat.h"
+#include "kernel/riscv.h"
+#include "user/user.h"
+
+void test0();
+void test1();
+void test2();
+void test3();
+void periodic();
+void slow_handler();
+void dummy_handler();
+
+int
+main(int argc, char *argv[])
+{
+  test0();
+  test1();
+  test2();
+  test3();
+  exit(0);
+}
+
+volatile static int count;
+
+void
+periodic()
+{
+  count = count + 1;
+  printf("alarm!\n");
+  sigreturn();
+}
+
+// tests whether the kernel calls
+// the alarm handler even a single time.
+void
+test0()
+{
+  int i;
+  printf("test0 start\n");
+  count = 0;
+  sigalarm(2, periodic);
+  for(i = 0; i < 1000*500000; i++){
+    if((i % 1000000) == 0)
+      write(2, ".", 1);
+    if(count > 0)
+      break;
+  }
+  sigalarm(0, 0);
+  if(count > 0){
+    printf("test0 passed\n");
+  } else {
+    printf("\ntest0 failed: the kernel never called the alarm handler\n");
+  }
+}
+
+void __attribute__ ((noinline)) foo(int i, int *j) {
+  if((i % 2500000) == 0) {
+    write(2, ".", 1);
+  }
+  *j += 1;
+}
+
+//
+// tests that the kernel calls the handler multiple times.
+//
+// tests that, when the handler returns, it returns to
+// the point in the program where the timer interrupt
+// occurred, with all registers holding the same values they
+// held when the interrupt occurred.
+//
+void
+test1()
+{
+  int i;
+  int j;
+
+  printf("test1 start\n");
+  count = 0;
+  j = 0;
+  sigalarm(2, periodic);
+  for(i = 0; i < 500000000; i++){
+    if(count >= 10)
+      break;
+    foo(i, &j);
+  }
+  if(count < 10){
+    printf("\ntest1 failed: too few calls to the handler\n");
+  } else if(i != j){
+    // the loop should have called foo() i times, and foo() should
+    // have incremented j once per call, so j should equal i.
+    // once possible source of errors is that the handler may
+    // return somewhere other than where the timer interrupt
+    // occurred; another is that that registers may not be
+    // restored correctly, causing i or j or the address ofj
+    // to get an incorrect value.
+    printf("\ntest1 failed: foo() executed fewer times than it was called\n");
+  } else {
+    printf("test1 passed\n");
+  }
+}
+
+//
+// tests that kernel does not allow reentrant alarm calls.
+void
+test2()
+{
+  int i;
+  int pid;
+  int status;
+
+  printf("test2 start\n");
+  if ((pid = fork()) < 0) {
+    printf("test2: fork failed\n");
+  }
+  if (pid == 0) {
+    count = 0;
+    sigalarm(2, slow_handler);
+    for(i = 0; i < 1000*500000; i++){
+      if((i % 1000000) == 0)
+        write(2, ".", 1);
+      if(count > 0)
+        break;
+    }
+    if (count == 0) {
+      printf("\ntest2 failed: alarm not called\n");
+      exit(1);
+    }
+    exit(0);
+  }
+  wait(&status);
+  if (status == 0) {
+    printf("test2 passed\n");
+  }
+}
+
+void
+slow_handler()
+{
+  count++;
+  printf("alarm!\n");
+  if (count > 1) {
+    printf("test2 failed: alarm handler called more than once\n");
+    exit(1);
+  }
+  for (int i = 0; i < 1000*500000; i++) {
+    asm volatile("nop"); // avoid compiler optimizing away loop
+  }
+  sigalarm(0, 0);
+  sigreturn();
+}
+
+//
+// dummy alarm handler; after running immediately uninstall
+// itself and finish signal handling
+void
+dummy_handler()
+{
+  sigalarm(0, 0);
+  sigreturn();
+}
+
+//
+// tests that the return from sys_sigreturn() does not
+// modify the a0 register
+void
+test3()
+{
+  uint64 a0;
+
+  sigalarm(1, dummy_handler);
+  printf("test3 start\n");
+
+  asm volatile("lui a5, 0");
+  asm volatile("addi a0, a5, 0xac" : : : "a0");
+  for(int i = 0; i < 500000000; i++)
+    ;
+  asm volatile("mv %0, a0" : "=r" (a0) );
+
+  if(a0 != 0xac)
+    printf("test3 failed: register a0 changed\n");
+  else
+    printf("test3 passed\n");
+}
diff --git a/user/bcachetest.c b/user/bcachetest.c
new file mode 100644
index 0000000..ccf7516
--- /dev/null
+++ b/user/bcachetest.c
@@ -0,0 +1,318 @@
+#include "kernel/fcntl.h"
+#include "kernel/param.h"
+#include "kernel/types.h"
+#include "kernel/stat.h"
+#include "kernel/riscv.h"
+#include "kernel/fs.h"
+#include "user/user.h"
+
+void test0();
+void test1();
+void test2();
+
+#define SZ 4096
+char buf[SZ];
+
+int
+main(int argc, char *argv[])
+{
+  test0();
+  test1();
+  test2();
+  exit(0);
+}
+
+void
+createfile(char *file, int nblock)
+{
+  int fd;
+  char buf[BSIZE];
+  int i;
+  
+  fd = open(file, O_CREATE | O_RDWR);
+  if(fd < 0){
+    printf("createfile %s failed\n", file);
+    exit(-1);
+  }
+  for(i = 0; i < nblock; i++) {
+    if(write(fd, buf, sizeof(buf)) != sizeof(buf)) {
+      printf("write %s failed\n", file);
+      exit(-1);
+    }
+  }
+  close(fd);
+}
+
+void
+readfile(char *file, int nbytes, int inc)
+{
+  char buf[BSIZE];
+  int fd;
+  int i;
+
+  if(inc > BSIZE) {
+    printf("readfile: inc too large\n");
+    exit(-1);
+  }
+  if ((fd = open(file, O_RDONLY)) < 0) {
+    printf("readfile open %s failed\n", file);
+    exit(-1);
+  }
+  for (i = 0; i < nbytes; i += inc) {
+    if(read(fd, buf, inc) != inc) {
+      printf("read %s failed for block %d (%d)\n", file, i, nbytes);
+      exit(-1);
+    }
+  }
+  close(fd);
+}
+
+int ntas(int print)
+{
+  int n;
+  char *c;
+
+  if (statistics(buf, SZ) <= 0) {
+    fprintf(2, "ntas: no stats\n");
+  }
+  c = strchr(buf, '=');
+  n = atoi(c+2);
+  if(print)
+    printf("%s", buf);
+  return n;
+}
+
+// Test reading small files concurrently
+void
+test0()
+{
+  char file[2];
+  char dir[2];
+  enum { N = 10, NCHILD = 3 };
+  int m, n;
+
+  dir[0] = '0';
+  dir[1] = '\0';
+  file[0] = 'F';
+  file[1] = '\0';
+
+  printf("start test0\n");
+  for(int i = 0; i < NCHILD; i++){
+    dir[0] = '0' + i;
+    mkdir(dir);
+    if (chdir(dir) < 0) {
+      printf("chdir failed\n");
+      exit(1);
+    }
+    unlink(file);
+    createfile(file, N);
+    if (chdir("..") < 0) {
+      printf("chdir failed\n");
+      exit(1);
+    }
+  }
+  m = ntas(0);
+  for(int i = 0; i < NCHILD; i++){
+    dir[0] = '0' + i;
+    int pid = fork();
+    if(pid < 0){
+      printf("fork failed");
+      exit(-1);
+    }
+    if(pid == 0){
+      if (chdir(dir) < 0) {
+        printf("chdir failed\n");
+        exit(1);
+      }
+
+      readfile(file, N*BSIZE, 1);
+
+      exit(0);
+    }
+  }
+
+  for(int i = 0; i < NCHILD; i++){
+    wait(0);
+  }
+  printf("test0 results:\n");
+  n = ntas(1);
+  if (n-m < 500)
+    printf("test0: OK\n");
+  else
+    printf("test0: FAIL\n");
+}
+
+// Test bcache evictions by reading a large file concurrently
+void test1()
+{
+  char file[3];
+  enum { N = 200, BIG=100, NCHILD=2 };
+  
+  printf("start test1\n");
+  file[0] = 'B';
+  file[2] = '\0';
+  for(int i = 0; i < NCHILD; i++){
+    file[1] = '0' + i;
+    unlink(file);
+    if (i == 0) {
+      createfile(file, BIG);
+    } else {
+      createfile(file, 1);
+    }
+  }
+  for(int i = 0; i < NCHILD; i++){
+    file[1] = '0' + i;
+    int pid = fork();
+    if(pid < 0){
+      printf("fork failed");
+      exit(-1);
+    }
+    if(pid == 0){
+      if (i==0) {
+        for (i = 0; i < N; i++) {
+          readfile(file, BIG*BSIZE, BSIZE);
+        }
+        unlink(file);
+        exit(0);
+      } else {
+        for (i = 0; i < N*20; i++) {
+          readfile(file, 1, BSIZE);
+        }
+        unlink(file);
+      }
+      exit(0);
+    }
+  }
+
+  for(int i = 0; i < NCHILD; i++){
+    wait(0);
+  }
+  printf("test1 OK\n");
+}
+
+//
+// test concurrent creates.
+//
+void
+test2()
+{
+  int nc = 4;
+  char file[16];
+
+  printf("start test2\n");
+  
+  mkdir("d2");
+
+  file[0] = 'd';
+  file[1] = '2';
+  file[2] = '/';
+
+  // remove any stale existing files.
+  for(int i = 0; i < 50; i++){
+    for(int ci = 0; ci < nc; ci++){
+      file[3] = 'a' + ci;
+      file[4] = '0' + i;
+      file[5] = '\0';
+      unlink(file);
+    }
+  }
+
+  int pids[nc];
+  for(int ci = 0; ci < nc; ci++){
+    pids[ci] = fork();
+    if(pids[ci] < 0){
+      printf("test2: fork failed\n");
+      exit(1);
+    }
+    if(pids[ci] == 0){
+      char me = "abcdefghijklmnop"[ci];
+      int pid = getpid();
+      int nf = (ci == 0 ? 10 : 15);
+
+      // create nf files.
+      for(int i = 0; i < nf; i++){
+        file[3] = me;
+        file[4] = '0' + i;
+        file[5] = '\0';
+        // printf("w %s\n", file);
+        int fd = open(file, O_CREATE | O_RDWR);
+        if(fd < 0){
+          printf("test2: create %s failed\n", file);
+          exit(1);
+        }
+        int xx = (pid << 16) | i;
+        for(int nw = 0; nw < 2; nw++){
+          // the sleep() increases the chance of simultaneous
+          // calls to bget().
+          sleep(1);
+          if(write(fd, &xx, sizeof(xx)) <= 0){
+            printf("test2: write %s failed\n", file);
+            exit(1);
+          }
+        }
+        close(fd);
+      }
+
+      // read back the nf files.
+      for(int i = 0; i < nf; i++){
+        file[3] = me;
+        file[4] = '0' + i;
+        file[5] = '\0';
+        // printf("r %s\n", file);
+        int fd = open(file, O_RDWR);
+        if(fd < 0){
+          printf("test2: open %s failed\n", file);
+          exit(1);
+        }
+        int xx = (pid << 16) | i;
+        for(int nr = 0; nr < 2; nr++){
+          int z = 0;
+          sleep(1);
+          int n = read(fd, &z, sizeof(z));
+          if(n != sizeof(z)){
+            printf("test2: read %s returned %d, expected %d\n", file, n, sizeof(z));
+            exit(1);
+          }
+          if(z != xx){
+            printf("test2: file %s contained %d, not %d\n", file, z, xx);
+            exit(1);
+          }
+        }
+        close(fd);
+      }
+
+      // delete the nf files.
+      for(int i = 0; i < nf; i++){
+        file[3] = me;
+        file[4] = '0' + i;
+        file[5] = '\0';
+        //printf("u %s\n", file);
+        if(unlink(file) != 0){
+          printf("test2: unlink %s failed\n", file);
+          exit(1);
+        }
+      }
+
+      exit(0);
+    }
+  }
+
+  int ok = 1;
+
+  for(int ci = 0; ci < nc; ci++){
+    int st = 0;
+    int ret = wait(&st);
+    if(ret <= 0){
+      printf("test2: wait() failed\n");
+      ok = 0;
+    }
+    if(st != 0)
+      ok = 0;
+  }
+  
+  if(ok){
+    printf("test2 OK\n");
+  } else {
+    printf("test2 failed\n");
+  }
+}
diff --git a/user/bttest.c b/user/bttest.c
new file mode 100644
index 0000000..05405f9
--- /dev/null
+++ b/user/bttest.c
@@ -0,0 +1,10 @@
+#include "kernel/types.h"
+#include "kernel/stat.h"
+#include "user/user.h"
+
+int
+main(int argc, char *argv[])
+{
+  sleep(1);
+  exit(0);
+}
diff --git a/user/call.c b/user/call.c
new file mode 100644
index 0000000..f725dcb
--- /dev/null
+++ b/user/call.c
@@ -0,0 +1,17 @@
+#include "kernel/param.h"
+#include "kernel/types.h"
+#include "kernel/stat.h"
+#include "user/user.h"
+
+int g(int x) {
+  return x+3;
+}
+
+int f(int x) {
+  return g(x);
+}
+
+void main(void) {
+  printf("%d %d\n", f(8)+1, 13);
+  exit(0);
+}
diff --git a/user/cowtest.c b/user/cowtest.c
new file mode 100644
index 0000000..29b918f
--- /dev/null
+++ b/user/cowtest.c
@@ -0,0 +1,197 @@
+//
+// tests for copy-on-write fork() assignment.
+//
+
+#include "kernel/types.h"
+#include "kernel/memlayout.h"
+#include "user/user.h"
+
+// allocate more than half of physical memory,
+// then fork. this will fail in the default
+// kernel, which does not support copy-on-write.
+void
+simpletest()
+{
+  uint64 phys_size = PHYSTOP - KERNBASE;
+  int sz = (phys_size / 3) * 2;
+
+  printf("simple: ");
+  
+  char *p = sbrk(sz);
+  if(p == (char*)0xffffffffffffffffL){
+    printf("sbrk(%d) failed\n", sz);
+    exit(-1);
+  }
+
+  for(char *q = p; q < p + sz; q += 4096){
+    *(int*)q = getpid();
+  }
+
+  int pid = fork();
+  if(pid < 0){
+    printf("fork() failed\n");
+    exit(-1);
+  }
+
+  if(pid == 0)
+    exit(0);
+
+  wait(0);
+
+  if(sbrk(-sz) == (char*)0xffffffffffffffffL){
+    printf("sbrk(-%d) failed\n", sz);
+    exit(-1);
+  }
+
+  printf("ok\n");
+}
+
+// three processes all write COW memory.
+// this causes more than half of physical memory
+// to be allocated, so it also checks whether
+// copied pages are freed.
+void
+threetest()
+{
+  uint64 phys_size = PHYSTOP - KERNBASE;
+  int sz = phys_size / 4;
+  int pid1, pid2;
+
+  printf("three: ");
+  
+  char *p = sbrk(sz);
+  if(p == (char*)0xffffffffffffffffL){
+    printf("sbrk(%d) failed\n", sz);
+    exit(-1);
+  }
+
+  pid1 = fork();
+  if(pid1 < 0){
+    printf("fork failed\n");
+    exit(-1);
+  }
+  if(pid1 == 0){
+    pid2 = fork();
+    if(pid2 < 0){
+      printf("fork failed");
+      exit(-1);
+    }
+    if(pid2 == 0){
+      for(char *q = p; q < p + (sz/5)*4; q += 4096){
+        *(int*)q = getpid();
+      }
+      for(char *q = p; q < p + (sz/5)*4; q += 4096){
+        if(*(int*)q != getpid()){
+          printf("wrong content\n");
+          exit(-1);
+        }
+      }
+      exit(-1);
+    }
+    for(char *q = p; q < p + (sz/2); q += 4096){
+      *(int*)q = 9999;
+    }
+    exit(0);
+  }
+
+  for(char *q = p; q < p + sz; q += 4096){
+    *(int*)q = getpid();
+  }
+
+  wait(0);
+
+  sleep(1);
+
+  for(char *q = p; q < p + sz; q += 4096){
+    if(*(int*)q != getpid()){
+      printf("wrong content\n");
+      exit(-1);
+    }
+  }
+
+  if(sbrk(-sz) == (char*)0xffffffffffffffffL){
+    printf("sbrk(-%d) failed\n", sz);
+    exit(-1);
+  }
+
+  printf("ok\n");
+}
+
+char junk1[4096];
+int fds[2];
+char junk2[4096];
+char buf[4096];
+char junk3[4096];
+
+// test whether copyout() simulates COW faults.
+void
+filetest()
+{
+  printf("file: ");
+  
+  buf[0] = 99;
+
+  for(int i = 0; i < 4; i++){
+    if(pipe(fds) != 0){
+      printf("pipe() failed\n");
+      exit(-1);
+    }
+    int pid = fork();
+    if(pid < 0){
+      printf("fork failed\n");
+      exit(-1);
+    }
+    if(pid == 0){
+      sleep(1);
+      if(read(fds[0], buf, sizeof(i)) != sizeof(i)){
+        printf("error: read failed\n");
+        exit(1);
+      }
+      sleep(1);
+      int j = *(int*)buf;
+      if(j != i){
+        printf("error: read the wrong value\n");
+        exit(1);
+      }
+      exit(0);
+    }
+    if(write(fds[1], &i, sizeof(i)) != sizeof(i)){
+      printf("error: write failed\n");
+      exit(-1);
+    }
+  }
+
+  int xstatus = 0;
+  for(int i = 0; i < 4; i++) {
+    wait(&xstatus);
+    if(xstatus != 0) {
+      exit(1);
+    }
+  }
+
+  if(buf[0] != 99){
+    printf("error: child overwrote parent\n");
+    exit(1);
+  }
+
+  printf("ok\n");
+}
+
+int
+main(int argc, char *argv[])
+{
+  simpletest();
+
+  // check that the first simpletest() freed the physical memory.
+  simpletest();
+
+  threetest();
+  threetest();
+  threetest();
+
+  filetest();
+
+  printf("ALL COW TESTS PASSED\n");
+
+  exit(0);
+}
diff --git a/user/find.c b/user/find.c
new file mode 100644
index 0000000..e185e9d
--- /dev/null
+++ b/user/find.c
@@ -0,0 +1,84 @@
+#include "kernel/types.h"
+
+#include "kernel/fcntl.h"
+#include "kernel/fs.h"
+#include "kernel/stat.h"
+#include "user/user.h"
+
+char*
+fmtname(char* path)
+{
+  char* p;
+
+  // Find first character after last slash.
+  for (p = path + strlen(path); p >= path && *p != '/'; p--)
+    ;
+  p++;
+  return p;
+}
+
+void
+find(char* root_path, char* filename)
+{
+  static char buf[512];
+  char* p;
+  int fd;
+  struct dirent de;
+  struct stat st;
+
+  if ((fd = open(root_path, O_RDONLY)) < 0) {
+    fprintf(2, "find: cannot open %s\n", root_path);
+    return;
+  }
+  if (fstat(fd, &st) < 0) {
+    fprintf(2, "find: cannot stat %s\n", root_path);
+    close(fd);
+    return;
+  }
+
+  switch (st.type) {
+    case T_FILE:
+      if (!strcmp(fmtname(root_path), filename)) {
+        printf("%s\n", root_path);
+      }
+      break;
+    case T_DIR:
+      if (strlen(root_path) + 1 + DIRSIZ + 1 > sizeof(buf)) {
+        printf("find: path too long\n");
+        break;
+      }
+
+      strcpy(buf, root_path);
+
+      p = buf + strlen(buf);
+      *p++ = '/';
+      while (read(fd, &de, sizeof(de)) == sizeof(de)) {
+        if (de.inum == 0)
+          continue;
+        memmove(p, de.name, DIRSIZ);
+        p[DIRSIZ] = '\0';
+
+        // printf("i'm finding %s!\n", fmtname(buf));
+
+        if (!strcmp(fmtname(buf), ".") || !strcmp(fmtname(buf), "..")) {
+          continue;
+        }
+
+        find(buf, filename);
+      }
+  }
+  close(fd);
+}
+
+int
+main(int argc, char* argv[])
+{
+  if (argc < 3) {
+    fprintf(2, "usage: find [root_path] filename...\n");
+    exit(1);
+  }
+
+  for (int i = 2; i < argc; i++) {
+    find(argv[1], argv[i]);
+  }
+}
diff --git a/user/init.c b/user/init.c
index e0a5689..fc1c3db 100644
--- a/user/init.c
+++ b/user/init.c
@@ -18,6 +18,7 @@ main(void)
 
   if(open("console", O_RDWR) < 0){
     mknod("console", CONSOLE, 0);
+    mknod("statistics", STATS, 0);
     open("console", O_RDWR);
   }
   dup(0);  // stdout
diff --git a/user/kalloctest.c b/user/kalloctest.c
new file mode 100644
index 0000000..a82f1d5
--- /dev/null
+++ b/user/kalloctest.c
@@ -0,0 +1,161 @@
+#include "kernel/param.h"
+#include "kernel/types.h"
+#include "kernel/stat.h"
+#include "kernel/riscv.h"
+#include "kernel/memlayout.h"
+#include "kernel/fcntl.h"
+#include "user/user.h"
+
+#define NCHILD 2
+#define N 100000
+#define SZ 4096
+
+void test1(void);
+void test2(void);
+void test3(void);
+char buf[SZ];
+
+int
+main(int argc, char *argv[])
+{
+  test1();
+  test2();
+  test3();
+  exit(0);
+}
+
+int ntas(int print)
+{
+  int n;
+  char *c;
+
+  if (statistics(buf, SZ) <= 0) {
+    fprintf(2, "ntas: no stats\n");
+  }
+  c = strchr(buf, '=');
+  n = atoi(c+2);
+  if(print)
+    printf("%s", buf);
+  return n;
+}
+
+// Test concurrent kallocs and kfrees
+void test1(void)
+{
+  void *a, *a1;
+  int n, m;
+  printf("start test1\n");  
+  m = ntas(0);
+  for(int i = 0; i < NCHILD; i++){
+    int pid = fork();
+    if(pid < 0){
+      printf("fork failed");
+      exit(-1);
+    }
+    if(pid == 0){
+      for(i = 0; i < N; i++) {
+        a = sbrk(4096);
+        *(int *)(a+4) = 1;
+        a1 = sbrk(-4096);
+        if (a1 != a + 4096) {
+          printf("wrong sbrk\n");
+          exit(-1);
+        }
+      }
+      exit(-1);
+    }
+  }
+
+  for(int i = 0; i < NCHILD; i++){
+    wait(0);
+  }
+  printf("test1 results:\n");
+  n = ntas(1);
+  if(n-m < 10) 
+    printf("test1 OK\n");
+  else
+    printf("test1 FAIL\n");
+}
+
+//
+// countfree() from usertests.c
+//
+int
+countfree()
+{
+  uint64 sz0 = (uint64)sbrk(0);
+  int n = 0;
+
+  while(1){
+    uint64 a = (uint64) sbrk(4096);
+    if(a == 0xffffffffffffffff){
+      break;
+    }
+    // modify the memory to make sure it's really allocated.
+    *(char *)(a + 4096 - 1) = 1;
+    n += 1;
+  }
+  sbrk(-((uint64)sbrk(0) - sz0));
+  return n;
+}
+
+// Test stealing
+void test2() {
+  int free0 = countfree();
+  int free1;
+  int n = (PHYSTOP-KERNBASE)/PGSIZE;
+  printf("start test2\n");  
+  printf("total free number of pages: %d (out of %d)\n", free0, n);
+  if(n - free0 > 1000) {
+    printf("test2 FAILED: cannot allocate enough memory");
+    exit(-1);
+  }
+  for (int i = 0; i < 50; i++) {
+    free1 = countfree();
+    if(i % 10 == 9)
+      printf(".");
+    if(free1 != free0) {
+      printf("test2 FAIL: losing pages\n");
+      exit(-1);
+    }
+  }
+  printf("\ntest2 OK\n");  
+}
+
+// Test concurrent kalloc/kfree and stealing
+void test3(void)
+{
+  void *a, *a1;
+  printf("start test3\n");  
+  for(int i = 0; i < NCHILD; i++){
+    int pid = fork();
+    if(pid < 0){
+      printf("fork failed");
+      exit(-1);
+    }
+    if(pid == 0){
+      if (i == 0) {
+        for(i = 0; i < N; i++) {
+          a = sbrk(4096);
+          *(int *)(a+4) = 1;
+          a1 = sbrk(-4096);
+          if (a1 != a + 4096) {
+            printf("wrong sbrk\n");
+            exit(-1);
+          }
+        }
+        printf("child done %d\n", i);
+        exit(0);
+      } else {
+        countfree();
+        printf("child done %d\n", i);
+        exit(0);
+      }
+    }
+  }
+
+  for(int i = 0; i < NCHILD; i++){
+    wait(0);
+  }
+  printf("test3 OK\n");
+}
diff --git a/user/nettests.c b/user/nettests.c
new file mode 100644
index 0000000..2f7d6cd
--- /dev/null
+++ b/user/nettests.c
@@ -0,0 +1,297 @@
+#include "kernel/types.h"
+#include "kernel/net.h"
+#include "kernel/stat.h"
+#include "user/user.h"
+
+//
+// send a UDP packet to the localhost (outside of qemu),
+// and receive a response.
+//
+static void
+ping(uint16 sport, uint16 dport, int attempts)
+{
+  int fd;
+  char *obuf = "a message from xv6!";
+  uint32 dst;
+
+  // 10.0.2.2, which qemu remaps to the external host,
+  // i.e. the machine you're running qemu on.
+  dst = (10 << 24) | (0 << 16) | (2 << 8) | (2 << 0);
+
+  // you can send a UDP packet to any Internet address
+  // by using a different dst.
+  
+  if((fd = connect(dst, sport, dport)) < 0){
+    fprintf(2, "ping: connect() failed\n");
+    exit(1);
+  }
+
+  for(int i = 0; i < attempts; i++) {
+    if(write(fd, obuf, strlen(obuf)) < 0){
+      fprintf(2, "ping: send() failed\n");
+      exit(1);
+    }
+  }
+
+  char ibuf[128];
+  int cc = read(fd, ibuf, sizeof(ibuf)-1);
+  if(cc < 0){
+    fprintf(2, "ping: recv() failed\n");
+    exit(1);
+  }
+
+  close(fd);
+  ibuf[cc] = '\0';
+  if(strcmp(ibuf, "this is the host!") != 0){
+    fprintf(2, "ping didn't receive correct payload\n");
+    exit(1);
+  }
+}
+
+// Encode a DNS name
+static void
+encode_qname(char *qn, char *host)
+{
+  char *l = host; 
+  
+  for(char *c = host; c < host+strlen(host)+1; c++) {
+    if(*c == '.') {
+      *qn++ = (char) (c-l);
+      for(char *d = l; d < c; d++) {
+        *qn++ = *d;
+      }
+      l = c+1; // skip .
+    }
+  }
+  *qn = '\0';
+}
+
+// Decode a DNS name
+static void
+decode_qname(char *qn, int max)
+{
+  char *qnMax = qn + max;
+  while(1){
+    if(qn >= qnMax){
+      printf("invalid DNS reply\n");
+      exit(1);
+    }
+    int l = *qn;
+    if(l == 0)
+      break;
+    for(int i = 0; i < l; i++) {
+      *qn = *(qn+1);
+      qn++;
+    }
+    *qn++ = '.';
+  }
+}
+
+// Make a DNS request
+static int
+dns_req(uint8 *obuf)
+{
+  int len = 0;
+  
+  struct dns *hdr = (struct dns *) obuf;
+  hdr->id = htons(6828);
+  hdr->rd = 1;
+  hdr->qdcount = htons(1);
+  
+  len += sizeof(struct dns);
+  
+  // qname part of question
+  char *qname = (char *) (obuf + sizeof(struct dns));
+  char *s = "pdos.csail.mit.edu.";
+  encode_qname(qname, s);
+  len += strlen(qname) + 1;
+
+  // constants part of question
+  struct dns_question *h = (struct dns_question *) (qname+strlen(qname)+1);
+  h->qtype = htons(0x1);
+  h->qclass = htons(0x1);
+
+  len += sizeof(struct dns_question);
+  return len;
+}
+
+// Process DNS response
+static void
+dns_rep(uint8 *ibuf, int cc)
+{
+  struct dns *hdr = (struct dns *) ibuf;
+  int len;
+  char *qname = 0;
+  int record = 0;
+
+  if(cc < sizeof(struct dns)){
+    printf("DNS reply too short\n");
+    exit(1);
+  }
+
+  if(!hdr->qr) {
+    printf("Not a DNS reply for %d\n", ntohs(hdr->id));
+    exit(1);
+  }
+
+  if(hdr->id != htons(6828)){
+    printf("DNS wrong id: %d\n", ntohs(hdr->id));
+    exit(1);
+  }
+  
+  if(hdr->rcode != 0) {
+    printf("DNS rcode error: %x\n", hdr->rcode);
+    exit(1);
+  }
+  
+  //printf("qdcount: %x\n", ntohs(hdr->qdcount));
+  //printf("ancount: %x\n", ntohs(hdr->ancount));
+  //printf("nscount: %x\n", ntohs(hdr->nscount));
+  //printf("arcount: %x\n", ntohs(hdr->arcount));
+  
+  len = sizeof(struct dns);
+
+  for(int i =0; i < ntohs(hdr->qdcount); i++) {
+    char *qn = (char *) (ibuf+len);
+    qname = qn;
+    decode_qname(qn, cc - len);
+    len += strlen(qn)+1;
+    len += sizeof(struct dns_question);
+  }
+
+  for(int i = 0; i < ntohs(hdr->ancount); i++) {
+    if(len >= cc){
+      printf("invalid DNS reply\n");
+      exit(1);
+    }
+    
+    char *qn = (char *) (ibuf+len);
+
+    if((int) qn[0] > 63) {  // compression?
+      qn = (char *)(ibuf+qn[1]);
+      len += 2;
+    } else {
+      decode_qname(qn, cc - len);
+      len += strlen(qn)+1;
+    }
+      
+    struct dns_data *d = (struct dns_data *) (ibuf+len);
+    len += sizeof(struct dns_data);
+    //printf("type %d ttl %d len %d\n", ntohs(d->type), ntohl(d->ttl), ntohs(d->len));
+    if(ntohs(d->type) == ARECORD && ntohs(d->len) == 4) {
+      record = 1;
+      printf("DNS arecord for %s is ", qname ? qname : "" );
+      uint8 *ip = (ibuf+len);
+      printf("%d.%d.%d.%d\n", ip[0], ip[1], ip[2], ip[3]);
+      if(ip[0] != 128 || ip[1] != 52 || ip[2] != 129 || ip[3] != 126) {
+        printf("wrong ip address");
+        exit(1);
+      }
+      len += 4;
+    }
+  }
+
+  // needed for DNS servers with EDNS support
+  for(int i = 0; i < ntohs(hdr->arcount); i++) {
+    char *qn = (char *) (ibuf+len);
+    if(*qn != 0) {
+      printf("invalid name for EDNS\n");
+      exit(1);
+    }
+    len += 1;
+
+    struct dns_data *d = (struct dns_data *) (ibuf+len);
+    len += sizeof(struct dns_data);
+    if(ntohs(d->type) != 41) {
+      printf("invalid type for EDNS\n");
+      exit(1);
+    }
+    len += ntohs(d->len);
+  }
+
+  if(len != cc) {
+    printf("Processed %d data bytes but received %d\n", len, cc);
+    exit(1);
+  }
+  if(!record) {
+    printf("Didn't receive an arecord\n");
+    exit(1);
+  }
+}
+
+static void
+dns()
+{
+  #define N 1000
+  uint8 obuf[N];
+  uint8 ibuf[N];
+  uint32 dst;
+  int fd;
+  int len;
+
+  memset(obuf, 0, N);
+  memset(ibuf, 0, N);
+  
+  // 8.8.8.8: google's name server
+  dst = (8 << 24) | (8 << 16) | (8 << 8) | (8 << 0);
+
+  if((fd = connect(dst, 10000, 53)) < 0){
+    fprintf(2, "ping: connect() failed\n");
+    exit(1);
+  }
+
+  len = dns_req(obuf);
+  
+  if(write(fd, obuf, len) < 0){
+    fprintf(2, "dns: send() failed\n");
+    exit(1);
+  }
+  int cc = read(fd, ibuf, sizeof(ibuf));
+  if(cc < 0){
+    fprintf(2, "dns: recv() failed\n");
+    exit(1);
+  }
+  dns_rep(ibuf, cc);
+
+  close(fd);
+}  
+
+int
+main(int argc, char *argv[])
+{
+  int i, ret;
+  uint16 dport = NET_TESTS_PORT;
+
+  printf("nettests running on port %d\n", dport);
+  
+  printf("testing ping: ");
+  ping(2000, dport, 1);
+  printf("OK\n");
+  
+  printf("testing single-process pings: ");
+  for (i = 0; i < 100; i++)
+    ping(2000, dport, 1);
+  printf("OK\n");
+  
+  printf("testing multi-process pings: ");
+  for (i = 0; i < 10; i++){
+    int pid = fork();
+    if (pid == 0){
+      ping(2000 + i + 1, dport, 1);
+      exit(0);
+    }
+  }
+  for (i = 0; i < 10; i++){
+    wait(&ret);
+    if (ret != 0)
+      exit(1);
+  }
+  printf("OK\n");
+  
+  printf("testing DNS\n");
+  dns();
+  printf("DNS OK\n");
+  
+  printf("all tests passed.\n");
+  exit(0);
+}
diff --git a/user/pgtbltest.c b/user/pgtbltest.c
new file mode 100644
index 0000000..bce158a
--- /dev/null
+++ b/user/pgtbltest.c
@@ -0,0 +1,70 @@
+#include "kernel/param.h"
+#include "kernel/fcntl.h"
+#include "kernel/types.h"
+#include "kernel/riscv.h"
+#include "user/user.h"
+
+void ugetpid_test();
+void pgaccess_test();
+
+int
+main(int argc, char *argv[])
+{
+  ugetpid_test();
+  pgaccess_test();
+  printf("pgtbltest: all tests succeeded\n");
+  exit(0);
+}
+
+char *testname = "???";
+
+void
+err(char *why)
+{
+  printf("pgtbltest: %s failed: %s, pid=%d\n", testname, why, getpid());
+  exit(1);
+}
+
+void
+ugetpid_test()
+{
+  int i;
+
+  printf("ugetpid_test starting\n");
+  testname = "ugetpid_test";
+
+  for (i = 0; i < 64; i++) {
+    int ret = fork();
+    if (ret != 0) {
+      wait(&ret);
+      if (ret != 0)
+        exit(1);
+      continue;
+    }
+    if (getpid() != ugetpid())
+      err("missmatched PID");
+    exit(0);
+  }
+  printf("ugetpid_test: OK\n");
+}
+
+void
+pgaccess_test()
+{
+  char *buf;
+  unsigned int abits;
+  printf("pgaccess_test starting\n");
+  testname = "pgaccess_test";
+  buf = malloc(32 * PGSIZE);
+  if (pgaccess(buf, 32, &abits) < 0)
+    err("pgaccess failed");
+  buf[PGSIZE * 1] += 1;
+  buf[PGSIZE * 2] += 1;
+  buf[PGSIZE * 30] += 1;
+  if (pgaccess(buf, 32, &abits) < 0)
+    err("pgaccess failed");
+  if (abits != ((1 << 1) | (1 << 2) | (1 << 30)))
+    err("incorrect access bits set");
+  free(buf);
+  printf("pgaccess_test: OK\n");
+}
diff --git a/user/pingpong.c b/user/pingpong.c
new file mode 100644
index 0000000..7b03a76
--- /dev/null
+++ b/user/pingpong.c
@@ -0,0 +1,44 @@
+#include "kernel/types.h"
+#include "user/user.h"
+
+int
+main(int argc, char* argv[])
+{
+  int p[2];
+
+  if (argc > 1) {
+    fprintf(2, "usage: pingpong\n");
+    exit(1);
+  }
+
+  pipe(p);
+
+  int pid = fork();
+
+  if (pid == 0) {
+    short n;
+    read(p[0], &n, sizeof(n));
+    if (n == 42) {
+      fprintf(1, "%d: received ping\n", getpid());
+    }
+    n++;
+    write(p[1], &n, sizeof(n));
+    close(p[0]);
+    close(p[1]);
+    exit(0);
+  }
+
+  short n = 42;
+
+  write(p[1], &n, sizeof(n));
+  read(p[0], &n, sizeof(n));
+  if (n == 43) {
+    fprintf(1, "%d: received pong\n", getpid());
+  }
+  close(p[0]);
+  close(p[1]);
+
+  wait(0);
+
+  exit(0);
+}
diff --git a/user/primes.c b/user/primes.c
new file mode 100644
index 0000000..b359524
--- /dev/null
+++ b/user/primes.c
@@ -0,0 +1,74 @@
+#include "kernel/types.h"
+#include "user/user.h"
+
+#define MAX 36
+#define FIRST_PRIME 2
+
+int
+generate_natural(); // -> out_fd
+int
+prime_filter(int in_fd, int prime); // -> out_fd
+
+int
+main(int argc, char* argv[])
+{
+  int prime;
+
+  int in = generate_natural();
+  while (read(in, &prime, sizeof(int))) {
+    // printf("prime %d: in_fd: %d\n", prime, in);  // debug
+    printf("prime %d\n", prime);
+    in = prime_filter(in, prime);
+  }
+
+  close(in);
+
+  exit(0);
+}
+
+int
+generate_natural()
+{
+  int out_pipe[2];
+
+  pipe(out_pipe);
+
+  if (!fork()) {
+    for (int i = FIRST_PRIME; i < MAX; i++) {
+      write(out_pipe[1], &i, sizeof(int));
+    }
+    close(out_pipe[1]);
+
+    exit(0);
+  }
+
+  close(out_pipe[1]);
+
+  return out_pipe[0];
+}
+
+int
+prime_filter(int in_fd, int prime)
+{
+  int num;
+  int out_pipe[2];
+
+  pipe(out_pipe);
+
+  if (!fork()) {
+    while (read(in_fd, &num, sizeof(int))) {
+      if (num % prime) {
+        write(out_pipe[1], &num, sizeof(int));
+      }
+    }
+    close(in_fd);
+    close(out_pipe[1]);
+
+    exit(0);
+  }
+
+  close(in_fd);
+  close(out_pipe[1]);
+
+  return out_pipe[0];
+}
diff --git a/user/sh.c b/user/sh.c
index 836ebcb..5eceda0 100644
--- a/user/sh.c
+++ b/user/sh.c
@@ -165,6 +165,9 @@ main(void)
         fprintf(2, "cannot cd %s\n", buf+3);
       continue;
     }
+    if(buf[0] == 'e' && buf[1] == 'x' && buf[2] == 'i' && buf[3] == 't'){
+      exit(0);
+    }
     if(fork1() == 0)
       runcmd(parsecmd(buf));
     wait(0);
diff --git a/user/sleep.c b/user/sleep.c
new file mode 100644
index 0000000..961f558
--- /dev/null
+++ b/user/sleep.c
@@ -0,0 +1,22 @@
+#include "kernel/types.h"
+#include "user/user.h"
+
+int
+main(int argc, char* argv[])
+{
+  uint sec = 0;
+
+  if (argc <= 1) {
+    fprintf(2, "usage: sleep [time (ticks)]\n");
+    exit(1);
+  }
+  sec = atoi(argv[1]);
+
+  sleep(sec);
+
+  if (argc <= 2) {
+    exit(0);
+  }
+
+  exit(0);
+}
diff --git a/user/statistics.c b/user/statistics.c
new file mode 100644
index 0000000..e22681a
--- /dev/null
+++ b/user/statistics.c
@@ -0,0 +1,24 @@
+#include "kernel/types.h"
+#include "kernel/stat.h"
+#include "kernel/fcntl.h"
+#include "user/user.h"
+
+int
+statistics(void *buf, int sz)
+{
+  int fd, i, n;
+  
+  fd = open("statistics", O_RDONLY);
+  if(fd < 0) {
+      fprintf(2, "stats: open failed\n");
+      exit(1);
+  }
+  for (i = 0; i < sz; ) {
+    if ((n = read(fd, buf+i, sz-i)) < 0) {
+      break;
+    }
+    i += n;
+  }
+  close(fd);
+  return i;
+}
diff --git a/user/stats.c b/user/stats.c
new file mode 100644
index 0000000..f8c9138
--- /dev/null
+++ b/user/stats.c
@@ -0,0 +1,24 @@
+#include "kernel/types.h"
+#include "kernel/stat.h"
+#include "kernel/fcntl.h"
+#include "user/user.h"
+
+#define SZ 4096
+char buf[SZ];
+
+int
+main(void)
+{
+  int i, n;
+  
+  while (1) {
+    n = statistics(buf, SZ);
+    for (i = 0; i < n; i++) {
+      write(1, buf+i, 1);
+    }
+    if (n != SZ)
+      break;
+  }
+
+  exit(0);
+}
diff --git a/user/sysinfotest.c b/user/sysinfotest.c
new file mode 100644
index 0000000..8a648a6
--- /dev/null
+++ b/user/sysinfotest.c
@@ -0,0 +1,153 @@
+#include "kernel/types.h"
+#include "kernel/riscv.h"
+#include "kernel/sysinfo.h"
+#include "user/user.h"
+
+
+void
+sinfo(struct sysinfo *info) {
+  if (sysinfo(info) < 0) {
+    printf("FAIL: sysinfo failed");
+    exit(1);
+  }
+}
+
+//
+// use sbrk() to count how many free physical memory pages there are.
+//
+int
+countfree()
+{
+  uint64 sz0 = (uint64)sbrk(0);
+  struct sysinfo info;
+  int n = 0;
+
+  while(1){
+    if((uint64)sbrk(PGSIZE) == 0xffffffffffffffff){
+      break;
+    }
+    n += PGSIZE;
+  }
+  sinfo(&info);
+  if (info.freemem != 0) {
+    printf("FAIL: there is no free mem, but sysinfo.freemem=%d\n",
+      info.freemem);
+    exit(1);
+  }
+  sbrk(-((uint64)sbrk(0) - sz0));
+  return n;
+}
+
+void
+testmem() {
+  struct sysinfo info;
+  uint64 n = countfree();
+  
+  sinfo(&info);
+
+  if (info.freemem!= n) {
+    printf("FAIL: free mem %d (bytes) instead of %d\n", info.freemem, n);
+    exit(1);
+  }
+  
+  if((uint64)sbrk(PGSIZE) == 0xffffffffffffffff){
+    printf("sbrk failed");
+    exit(1);
+  }
+
+  sinfo(&info);
+    
+  if (info.freemem != n-PGSIZE) {
+    printf("FAIL: free mem %d (bytes) instead of %d\n", n-PGSIZE, info.freemem);
+    exit(1);
+  }
+  
+  if((uint64)sbrk(-PGSIZE) == 0xffffffffffffffff){
+    printf("sbrk failed");
+    exit(1);
+  }
+
+  sinfo(&info);
+    
+  if (info.freemem != n) {
+    printf("FAIL: free mem %d (bytes) instead of %d\n", n, info.freemem);
+    exit(1);
+  }
+}
+
+void
+testcall() {
+  struct sysinfo info;
+  
+  if (sysinfo(&info) < 0) {
+    printf("FAIL: sysinfo failed\n");
+    exit(1);
+  }
+
+  if (sysinfo((struct sysinfo *) 0xeaeb0b5b00002f5e) !=  0xffffffffffffffff) {
+    printf("FAIL: sysinfo succeeded with bad argument\n");
+    exit(1);
+  }
+}
+
+void testproc() {
+  struct sysinfo info;
+  uint64 nproc;
+  int status;
+  int pid;
+  
+  sinfo(&info);
+  nproc = info.nproc;
+
+  pid = fork();
+  if(pid < 0){
+    printf("sysinfotest: fork failed\n");
+    exit(1);
+  }
+  if(pid == 0){
+    sinfo(&info);
+    if(info.nproc != nproc+1) {
+      printf("sysinfotest: FAIL nproc is %d instead of %d\n", info.nproc, nproc+1);
+      exit(1);
+    }
+    exit(0);
+  }
+  wait(&status);
+  sinfo(&info);
+  if(info.nproc != nproc) {
+      printf("sysinfotest: FAIL nproc is %d instead of %d\n", info.nproc, nproc);
+      exit(1);
+  }
+}
+
+void testbad() {
+  int pid = fork();
+  int xstatus;
+  
+  if(pid < 0){
+    printf("sysinfotest: fork failed\n");
+    exit(1);
+  }
+  if(pid == 0){
+      sinfo(0x0);
+      exit(0);
+  }
+  wait(&xstatus);
+  if(xstatus == -1)  // kernel killed child?
+    exit(0);
+  else {
+    printf("sysinfotest: testbad succeeded %d\n", xstatus);
+    exit(xstatus);
+  }
+}
+
+int
+main(int argc, char *argv[])
+{
+  printf("sysinfotest: start\n");
+  testcall();
+  testmem();
+  testproc();
+  printf("sysinfotest: OK\n");
+  exit(0);
+}
diff --git a/user/trace.c b/user/trace.c
new file mode 100644
index 0000000..dd77760
--- /dev/null
+++ b/user/trace.c
@@ -0,0 +1,27 @@
+#include "kernel/param.h"
+#include "kernel/types.h"
+#include "kernel/stat.h"
+#include "user/user.h"
+
+int
+main(int argc, char *argv[])
+{
+  int i;
+  char *nargv[MAXARG];
+
+  if(argc < 3 || (argv[1][0] < '0' || argv[1][0] > '9')){
+    fprintf(2, "Usage: %s mask command\n", argv[0]);
+    exit(1);
+  }
+
+  if (trace(atoi(argv[1])) < 0) {
+    fprintf(2, "%s: trace failed\n", argv[0]);
+    exit(1);
+  }
+  
+  for(i = 2; i < argc && i < MAXARG; i++){
+    nargv[i-2] = argv[i];
+  }
+  exec(nargv[0], nargv);
+  exit(0);
+}
diff --git a/user/ulib.c b/user/ulib.c
index c7b66c4..871adc9 100644
--- a/user/ulib.c
+++ b/user/ulib.c
@@ -1,8 +1,13 @@
 #include "kernel/types.h"
 #include "kernel/stat.h"
 #include "kernel/fcntl.h"
+#ifdef LAB_PGTBL
+#include "kernel/riscv.h"
+#include "kernel/memlayout.h"
+#endif
 #include "user/user.h"
 
+
 //
 // wrapper so that it's OK if main() does not call exit().
 //
@@ -145,3 +150,12 @@ memcpy(void *dst, const void *src, uint n)
 {
   return memmove(dst, src, n);
 }
+
+#ifdef LAB_PGTBL
+int
+ugetpid(void)
+{
+  struct usyscall *u = (struct usyscall *)USYSCALL;
+  return u->pid;
+}
+#endif
diff --git a/user/user.h b/user/user.h
index 4d398d5..3544ac4 100644
--- a/user/user.h
+++ b/user/user.h
@@ -1,4 +1,9 @@
+#ifdef LAB_MMAP
+typedef unsigned long size_t;
+typedef long int off_t;
+#endif
 struct stat;
+struct sysinfo;
 
 // system calls
 int fork(void);
@@ -22,6 +27,18 @@ int getpid(void);
 char* sbrk(int);
 int sleep(int);
 int uptime(void);
+#ifdef LAB_NET
+int connect(uint32, uint16, uint16);
+#endif
+#ifdef LAB_PGTBL
+int pgaccess(void *base, int len, void *mask);
+// usyscall region
+int ugetpid(void);
+#endif
+int trace(int);
+int sysinfo(struct sysinfo*);
+int sigalarm(int ticks, void (*handler)());
+int sigreturn(void);
 
 // ulib.c
 int stat(const char*, struct stat*);
@@ -39,3 +56,6 @@ void free(void*);
 int atoi(const char*);
 int memcmp(const void *, const void *, uint);
 void *memcpy(void *, const void *, uint);
+
+// statistics.c
+int statistics(void*, int);
diff --git a/user/usys.pl b/user/usys.pl
index 01e426e..33af0ad 100755
--- a/user/usys.pl
+++ b/user/usys.pl
@@ -36,3 +36,9 @@ entry("getpid");
 entry("sbrk");
 entry("sleep");
 entry("uptime");
+entry("trace");
+entry("sysinfo");
+entry("connect");
+entry("pgaccess");
+entry("sigalarm");
+entry("sigreturn");
diff --git a/user/uthread.c b/user/uthread.c
new file mode 100644
index 0000000..7641d77
--- /dev/null
+++ b/user/uthread.c
@@ -0,0 +1,184 @@
+#include "kernel/types.h"
+#include "kernel/stat.h"
+#include "user/user.h"
+
+/* Possible states of a thread: */
+#define FREE        0x0
+#define RUNNING     0x1
+#define RUNNABLE    0x2
+
+#define STACK_SIZE  8192
+#define MAX_THREAD  4
+
+
+// Saved registers for kernel context switches.
+struct context {
+  uint64 ra;
+  uint64 sp;
+
+  // callee-saved
+  uint64 s0;
+  uint64 s1;
+  uint64 s2;
+  uint64 s3;
+  uint64 s4;
+  uint64 s5;
+  uint64 s6;
+  uint64 s7;
+  uint64 s8;
+  uint64 s9;
+  uint64 s10;
+  uint64 s11;
+};
+
+struct thread {
+  char       stack[STACK_SIZE]; /* the thread's stack */
+  int        state;             /* FREE, RUNNING, RUNNABLE */
+  struct context context;       /* saved registers to switch thru threads */
+};
+struct thread all_thread[MAX_THREAD];
+struct thread *current_thread;
+extern void thread_switch(uint64, uint64);
+              
+void 
+thread_init(void)
+{
+  // main() is thread 0, which will make the first invocation to
+  // thread_schedule(). It needs a stack so that the first thread_switch() can
+  // save thread 0's state.
+  current_thread = &all_thread[0];
+  current_thread->state = RUNNING;
+}
+
+void 
+thread_schedule(void)
+{
+  struct thread *t, *next_thread;
+
+  /* Find another runnable thread. */
+  next_thread = 0;
+  t = current_thread + 1;
+  for(int i = 0; i < MAX_THREAD; i++){
+    if(t >= all_thread + MAX_THREAD)
+      t = all_thread;
+    if(t->state == RUNNABLE) {
+      next_thread = t;
+      break;
+    }
+    t = t + 1;
+  }
+
+  if (next_thread == 0) {
+    printf("thread_schedule: no runnable threads\n");
+    exit(-1);
+  }
+
+  if (current_thread != next_thread) {         /* switch threads?  */
+    next_thread->state = RUNNING;
+    t = current_thread;
+    current_thread = next_thread;
+     // Invoke thread_switch to switch from t to next_thread:
+    thread_switch((uint64)&t->context, (uint64)&next_thread->context);
+  } else
+    next_thread = 0;
+}
+
+void 
+thread_create(void (*func)())
+{
+  struct thread *t;
+
+  for (t = all_thread; t < all_thread + MAX_THREAD; t++) {
+    if (t->state == FREE) break;
+  }
+  t->state = RUNNABLE;
+  // Set up new context to start executing at func
+  memset(&t->context, 0, sizeof(struct context));
+  t->context.ra = (uint64)func;
+  // stack grows downward, set sp at the highest stack address in out thread
+  t->context.sp = (uint64)t->stack + STACK_SIZE;
+}
+
+void 
+thread_yield(void)
+{
+  current_thread->state = RUNNABLE;
+  thread_schedule();
+}
+
+volatile int a_started, b_started, c_started;
+volatile int a_n, b_n, c_n;
+
+void 
+thread_a(void)
+{
+  int i;
+  printf("thread_a started\n");
+  a_started = 1;
+  while(b_started == 0 || c_started == 0)
+    thread_yield();
+  
+  for (i = 0; i < 100; i++) {
+    printf("thread_a %d\n", i);
+    a_n += 1;
+    thread_yield();
+  }
+  printf("thread_a: exit after %d\n", a_n);
+
+  current_thread->state = FREE;
+  thread_schedule();
+}
+
+void 
+thread_b(void)
+{
+  int i;
+  printf("thread_b started\n");
+  b_started = 1;
+  while(a_started == 0 || c_started == 0)
+    thread_yield();
+  
+  for (i = 0; i < 100; i++) {
+    printf("thread_b %d\n", i);
+    b_n += 1;
+    thread_yield();
+  }
+  printf("thread_b: exit after %d\n", b_n);
+
+  current_thread->state = FREE;
+  thread_schedule();
+}
+
+void 
+thread_c(void)
+{
+  int i;
+  printf("thread_c started\n");
+  c_started = 1;
+  while(a_started == 0 || b_started == 0)
+    thread_yield();
+  
+  for (i = 0; i < 100; i++) {
+    printf("thread_c %d\n", i);
+    c_n += 1;
+    thread_yield();
+  }
+  printf("thread_c: exit after %d\n", c_n);
+
+  current_thread->state = FREE;
+  thread_schedule();
+}
+
+int 
+main(int argc, char *argv[]) 
+{
+  a_started = b_started = c_started = 0;
+  a_n = b_n = c_n = 0;
+  thread_init();
+  thread_create(thread_a);
+  thread_create(thread_b);
+  thread_create(thread_c);
+  current_thread->state = FREE;
+  thread_schedule();
+  exit(0);
+}
diff --git a/user/uthread_switch.S b/user/uthread_switch.S
new file mode 100644
index 0000000..19cc400
--- /dev/null
+++ b/user/uthread_switch.S
@@ -0,0 +1,39 @@
+	.text
+
+	/*
+         * save the old thread's registers,
+         * restore the new thread's registers.
+         */
+
+	.globl thread_switch
+thread_switch:
+        sd ra, 0(a0)
+        sd sp, 8(a0)
+        sd s0, 16(a0)
+        sd s1, 24(a0)
+        sd s2, 32(a0)
+        sd s3, 40(a0)
+        sd s4, 48(a0)
+        sd s5, 56(a0)
+        sd s6, 64(a0)
+        sd s7, 72(a0)
+        sd s8, 80(a0)
+        sd s9, 88(a0)
+        sd s10, 96(a0)
+        sd s11, 104(a0)
+
+        ld ra, 0(a1)
+        ld sp, 8(a1)
+        ld s0, 16(a1)
+        ld s1, 24(a1)
+        ld s2, 32(a1)
+        ld s3, 40(a1)
+        ld s4, 48(a1)
+        ld s5, 56(a1)
+        ld s6, 64(a1)
+        ld s7, 72(a1)
+        ld s8, 80(a1)
+        ld s9, 88(a1)
+        ld s10, 96(a1)
+        ld s11, 104(a1)
+	ret    /* return to ra */
diff --git a/user/xargs.c b/user/xargs.c
new file mode 100644
index 0000000..b5b9bee
--- /dev/null
+++ b/user/xargs.c
@@ -0,0 +1,60 @@
+#include "kernel/types.h"
+
+#include "kernel/param.h"
+#include "kernel/stat.h"
+#include "user/user.h"
+
+#define is_blank(chr) (chr == ' ' || chr == '\t')
+
+int
+main(int argc, char* argv[])
+{
+  char buf[2048], ch;
+  char* p = buf;
+  char* v[MAXARG];
+  int c;
+  int blanks = 0;
+  int offset = 0;
+
+  if (argc <= 1) {
+    fprintf(2, "usage: xargs <command> [argv...]\n");
+    exit(1);
+  }
+
+  for (c = 1; c < argc; c++) {
+    v[c - 1] = argv[c];
+  }
+  --c;
+
+  while (read(0, &ch, 1) > 0) {
+    if (is_blank(ch)) {
+      blanks++;
+      continue;
+    }
+
+    if (blanks) {
+      buf[offset++] = 0;
+
+      v[c++] = p;
+      p = buf + offset;
+
+      blanks = 0;
+    }
+
+    if (ch != '\n') {
+      buf[offset++] = ch;
+    } else {
+      v[c++] = p;
+      p = buf + offset;
+
+      if (!fork()) {
+        exit(exec(v[0], v));
+      }
+      wait(0);
+
+      c = argc - 1;
+    }
+  }
+
+  exit(0);
+}
diff --git a/user/xargstest.sh b/user/xargstest.sh
new file mode 100644
index 0000000..4362589
--- /dev/null
+++ b/user/xargstest.sh
@@ -0,0 +1,6 @@
+mkdir a
+echo hello > a/b
+mkdir c
+echo hello > c/b
+echo hello > b
+find . b | xargs grep hello