reorganize file structure to match the upstream requirements

15 files changed, 2092 insertions, 0 deletions

diff --git a/userprog/.gitignore b/userprog/.gitignore
new file mode 100644
index 0000000..6d5357c
--- /dev/null
+++ b/userprog/.gitignore
@@ -0,0 +1,3 @@
+build
+bochsrc.txt
+bochsout.txt
diff --git a/userprog/Make.vars b/userprog/Make.vars
new file mode 100644
index 0000000..e4dbb08
--- /dev/null
+++ b/userprog/Make.vars
@@ -0,0 +1,7 @@
+# -*- makefile -*-
+
+kernel.bin: DEFINES = -DUSERPROG -DFILESYS
+KERNEL_SUBDIRS = threads devices lib lib/kernel userprog filesys
+TEST_SUBDIRS = tests/userprog tests/userprog/no-vm tests/filesys/base
+GRADING_FILE = $(SRCDIR)/tests/userprog/Grading
+SIMULATOR = --qemu
diff --git a/userprog/Makefile b/userprog/Makefile
new file mode 100644
index 0000000..34c10aa
--- /dev/null
+++ b/userprog/Makefile
@@ -0,0 +1 @@
+include ../Makefile.kernel
diff --git a/userprog/exception.c b/userprog/exception.c
new file mode 100644
index 0000000..17620ad
--- /dev/null
+++ b/userprog/exception.c
@@ -0,0 +1,174 @@
+#include "userprog/exception.h"
+#include <inttypes.h>
+#include <stdio.h>
+#include "userprog/gdt.h"
+#include "threads/interrupt.h"
+#include "threads/thread.h"
+#include "threads/vaddr.h"
+
+/* Number of page faults processed. */
+static long long page_fault_cnt;
+
+static void kill (struct intr_frame *);
+static void page_fault (struct intr_frame *);
+
+/* Registers handlers for interrupts that can be caused by user
+   programs.
+
+   In a real Unix-like OS, most of these interrupts would be
+   passed along to the user process in the form of signals, as
+   described in [SV-386] 3-24 and 3-25, but we don't implement
+   signals.  Instead, we'll make them simply kill the user
+   process.
+
+   Page faults are an exception.  Here they are treated the same
+   way as other exceptions, but this will need to change to
+   implement virtual memory.
+
+   Refer to [IA32-v3a] section 5.15 "Exception and Interrupt
+   Reference" for a description of each of these exceptions. */
+void
+exception_init (void) 
+{
+  /* These exceptions can be raised explicitly by a user program,
+     e.g. via the INT, INT3, INTO, and BOUND instructions.  Thus,
+     we set DPL==3, meaning that user programs are allowed to
+     invoke them via these instructions. */
+  intr_register_int (3, 3, INTR_ON, kill, "#BP Breakpoint Exception");
+  intr_register_int (4, 3, INTR_ON, kill, "#OF Overflow Exception");
+  intr_register_int (5, 3, INTR_ON, kill,
+                     "#BR BOUND Range Exceeded Exception");
+
+  /* These exceptions have DPL==0, preventing user processes from
+     invoking them via the INT instruction.  They can still be
+     caused indirectly, e.g. #DE can be caused by dividing by
+     0.  */
+  intr_register_int (0, 0, INTR_ON, kill, "#DE Divide Error");
+  intr_register_int (1, 0, INTR_ON, kill, "#DB Debug Exception");
+  intr_register_int (6, 0, INTR_ON, kill, "#UD Invalid Opcode Exception");
+  intr_register_int (7, 0, INTR_ON, kill,
+                     "#NM Device Not Available Exception");
+  intr_register_int (11, 0, INTR_ON, kill, "#NP Segment Not Present");
+  intr_register_int (12, 0, INTR_ON, kill, "#SS Stack Fault Exception");
+  intr_register_int (13, 0, INTR_ON, kill, "#GP General Protection Exception");
+  intr_register_int (16, 0, INTR_ON, kill, "#MF x87 FPU Floating-Point Error");
+  intr_register_int (19, 0, INTR_ON, kill,
+                     "#XF SIMD Floating-Point Exception");
+
+  /* Most exceptions can be handled with interrupts turned on.
+     We need to disable interrupts for page faults because the
+     fault address is stored in CR2 and needs to be preserved. */
+  intr_register_int (14, 0, INTR_OFF, page_fault, "#PF Page-Fault Exception");
+}
+
+/* Prints exception statistics. */
+void
+exception_print_stats (void) 
+{
+  printf ("Exception: %lld page faults\n", page_fault_cnt);
+}
+
+/* Handler for an exception (probably) caused by a user process. */
+static void
+kill (struct intr_frame *f) 
+{
+  /* This interrupt is one (probably) caused by a user process.
+     For example, the process might have tried to access unmapped
+     virtual memory (a page fault).  For now, we simply kill the
+     user process.  Later, we'll want to handle page faults in
+     the kernel.  Real Unix-like operating systems pass most
+     exceptions back to the process via signals, but we don't
+     implement them. */
+     
+  /* The interrupt frame's code segment value tells us where the
+     exception originated. */
+  switch (f->cs)
+    {
+    case SEL_UCSEG:
+      /* User's code segment, so it's a user exception, as we
+         expected.  Kill the user process.  */
+      printf ("%s: dying due to interrupt %#04x (%s).\n",
+              thread_name (), f->vec_no, intr_name (f->vec_no));
+      intr_dump_frame (f);
+      thread_exit (); 
+
+    case SEL_KCSEG:
+      /* Kernel's code segment, which indicates a kernel bug.
+         Kernel code shouldn't throw exceptions.  (Page faults
+         may cause kernel exceptions--but they shouldn't arrive
+         here.)  Panic the kernel to make the point.  */
+      intr_dump_frame (f);
+      PANIC ("Kernel bug - unexpected interrupt in kernel"); 
+
+    default:
+      /* Some other code segment?  Shouldn't happen.  Panic the
+         kernel. */
+      printf ("Interrupt %#04x (%s) in unknown segment %04x\n",
+             f->vec_no, intr_name (f->vec_no), f->cs);
+      thread_exit ();
+    }
+}
+
+/* Page fault handler.  This is a skeleton that must be filled in
+   to implement virtual memory.  Some solutions to project 2 may
+   also require modifying this code.
+
+   At entry, the address that faulted is in CR2 (Control Register
+   2) and information about the fault, formatted as described in
+   the PF_* macros in exception.h, is in F's error_code member.  The
+   example code here shows how to parse that information.  You
+   can find more information about both of these in the
+   description of "Interrupt 14--Page Fault Exception (#PF)" in
+   [IA32-v3a] section 5.15 "Exception and Interrupt Reference". */
+static void
+page_fault (struct intr_frame *f) 
+{
+  bool not_present;  /* True: not-present page, false: writing r/o page. */
+  bool write;        /* True: access was write, false: access was read. */
+  bool user;         /* True: access by user, false: access by kernel. */
+  void *fault_addr;  /* Fault address. */
+
+  /* Obtain faulting address, the virtual address that was
+     accessed to cause the fault.  It may point to code or to
+     data.  It is not necessarily the address of the instruction
+     that caused the fault (that's f->eip).
+     See [IA32-v2a] "MOV--Move to/from Control Registers" and
+     [IA32-v3a] 5.15 "Interrupt 14--Page Fault Exception
+     (#PF)". */
+  asm ("movl %%cr2, %0" : "=r" (fault_addr));
+
+  /* Turn interrupts back on (they were only off so that we could
+     be assured of reading CR2 before it changed). */
+  intr_enable ();
+
+  /* Count page faults. */
+  page_fault_cnt++;
+
+  /* Determine cause. */
+  not_present = (f->error_code & PF_P) == 0;
+  write = (f->error_code & PF_W) != 0;
+  user = (f->error_code & PF_U) != 0;
+
+  /* To implement virtual memory, adapt the rest of the function
+     body, adding code that brings in the page to
+     which fault_addr refers. */
+  if (is_user_vaddr(fault_addr)) {
+    if (! user) {
+      /* syscall exception; set eax and eip */
+      f->eip = (void*)f->eax;
+      f->eax = 0xFFFFFFFF;
+      return;
+    } else {
+      /* user process access violation */
+      thread_exit();
+    }
+  } else {
+    printf ("Page fault at %p: %s error %s page in %s context.\n",
+            fault_addr,
+            not_present ? "not present" : "rights violation",
+            write ? "writing" : "reading",
+            user ? "user" : "kernel");
+    kill (f);
+  }
+}
+
diff --git a/userprog/exception.h b/userprog/exception.h
new file mode 100644
index 0000000..f83e615
--- /dev/null
+++ b/userprog/exception.h
@@ -0,0 +1,12 @@
+#ifndef USERPROG_EXCEPTION_H
+#define USERPROG_EXCEPTION_H
+
+/* Page fault error code bits that describe the cause of the exception.  */
+#define PF_P 0x1    /* 0: not-present page. 1: access rights violation. */
+#define PF_W 0x2    /* 0: read, 1: write. */
+#define PF_U 0x4    /* 0: kernel, 1: user process. */
+
+void exception_init (void);
+void exception_print_stats (void);
+
+#endif /* userprog/exception.h */
diff --git a/userprog/gdt.c b/userprog/gdt.c
new file mode 100644
index 0000000..e866037
--- /dev/null
+++ b/userprog/gdt.c
@@ -0,0 +1,146 @@
+#include "userprog/gdt.h"
+#include <debug.h>
+#include "userprog/tss.h"
+#include "threads/palloc.h"
+#include "threads/vaddr.h"
+
+/* The Global Descriptor Table (GDT).
+
+   The GDT, an x86-specific structure, defines segments that can
+   potentially be used by all processes in a system, subject to
+   their permissions.  There is also a per-process Local
+   Descriptor Table (LDT) but that is not used by modern
+   operating systems.
+
+   Each entry in the GDT, which is known by its byte offset in
+   the table, identifies a segment.  For our purposes only three
+   types of segments are of interest: code, data, and TSS or
+   Task-State Segment descriptors.  The former two types are
+   exactly what they sound like.  The TSS is used primarily for
+   stack switching on interrupts.
+
+   For more information on the GDT as used here, refer to
+   [IA32-v3a] 3.2 "Using Segments" through 3.5 "System Descriptor
+   Types". */
+static uint64_t gdt[SEL_CNT];
+
+/* GDT helpers. */
+static uint64_t make_code_desc (int dpl);
+static uint64_t make_data_desc (int dpl);
+static uint64_t make_tss_desc (void *laddr);
+static uint64_t make_gdtr_operand (uint16_t limit, void *base);
+
+/* Sets up a proper GDT.  The bootstrap loader's GDT didn't
+   include user-mode selectors or a TSS, but we need both now. */
+void
+gdt_init (void)
+{
+  uint64_t gdtr_operand;
+
+  /* Initialize GDT. */
+  gdt[SEL_NULL / sizeof *gdt] = 0;
+  gdt[SEL_KCSEG / sizeof *gdt] = make_code_desc (0);
+  gdt[SEL_KDSEG / sizeof *gdt] = make_data_desc (0);
+  gdt[SEL_UCSEG / sizeof *gdt] = make_code_desc (3);
+  gdt[SEL_UDSEG / sizeof *gdt] = make_data_desc (3);
+  gdt[SEL_TSS / sizeof *gdt] = make_tss_desc (tss_get ());
+
+  /* Load GDTR, TR.  See [IA32-v3a] 2.4.1 "Global Descriptor
+     Table Register (GDTR)", 2.4.4 "Task Register (TR)", and
+     6.2.4 "Task Register".  */
+  gdtr_operand = make_gdtr_operand (sizeof gdt - 1, gdt);
+  asm volatile ("lgdt %0" : : "m" (gdtr_operand));
+  asm volatile ("ltr %w0" : : "q" (SEL_TSS));
+}
+
+/* System segment or code/data segment? */
+enum seg_class
+  {
+    CLS_SYSTEM = 0,             /* System segment. */
+    CLS_CODE_DATA = 1           /* Code or data segment. */
+  };
+
+/* Limit has byte or 4 kB page granularity? */
+enum seg_granularity
+  {
+    GRAN_BYTE = 0,              /* Limit has 1-byte granularity. */
+    GRAN_PAGE = 1               /* Limit has 4 kB granularity. */
+  };
+
+/* Returns a segment descriptor with the given 32-bit BASE and
+   20-bit LIMIT (whose interpretation depends on GRANULARITY).
+   The descriptor represents a system or code/data segment
+   according to CLASS, and TYPE is its type (whose interpretation
+   depends on the class).
+
+   The segment has descriptor privilege level DPL, meaning that
+   it can be used in rings numbered DPL or lower.  In practice,
+   DPL==3 means that user processes can use the segment and
+   DPL==0 means that only the kernel can use the segment.  See
+   [IA32-v3a] 4.5 "Privilege Levels" for further discussion. */
+static uint64_t
+make_seg_desc (uint32_t base,
+               uint32_t limit,
+               enum seg_class class,
+               int type,
+               int dpl,
+               enum seg_granularity granularity)
+{
+  uint32_t e0, e1;
+
+  ASSERT (limit <= 0xfffff);
+  ASSERT (class == CLS_SYSTEM || class == CLS_CODE_DATA);
+  ASSERT (type >= 0 && type <= 15);
+  ASSERT (dpl >= 0 && dpl <= 3);
+  ASSERT (granularity == GRAN_BYTE || granularity == GRAN_PAGE);
+
+  e0 = ((limit & 0xffff)             /* Limit 15:0. */
+        | (base << 16));             /* Base 15:0. */
+
+  e1 = (((base >> 16) & 0xff)        /* Base 23:16. */
+        | (type << 8)                /* Segment type. */
+        | (class << 12)              /* 0=system, 1=code/data. */
+        | (dpl << 13)                /* Descriptor privilege. */
+        | (1 << 15)                  /* Present. */
+        | (limit & 0xf0000)          /* Limit 16:19. */
+        | (1 << 22)                  /* 32-bit segment. */
+        | (granularity << 23)        /* Byte/page granularity. */
+        | (base & 0xff000000));      /* Base 31:24. */
+
+  return e0 | ((uint64_t) e1 << 32);
+}
+
+/* Returns a descriptor for a readable code segment with base at
+   0, a limit of 4 GB, and the given DPL. */
+static uint64_t
+make_code_desc (int dpl)
+{
+  return make_seg_desc (0, 0xfffff, CLS_CODE_DATA, 10, dpl, GRAN_PAGE);
+}
+
+/* Returns a descriptor for a writable data segment with base at
+   0, a limit of 4 GB, and the given DPL. */
+static uint64_t
+make_data_desc (int dpl)
+{
+  return make_seg_desc (0, 0xfffff, CLS_CODE_DATA, 2, dpl, GRAN_PAGE);
+}
+
+/* Returns a descriptor for an "available" 32-bit Task-State
+   Segment with its base at the given linear address, a limit of
+   0x67 bytes (the size of a 32-bit TSS), and a DPL of 0.
+   See [IA32-v3a] 6.2.2 "TSS Descriptor". */
+static uint64_t
+make_tss_desc (void *laddr)
+{
+  return make_seg_desc ((uint32_t) laddr, 0x67, CLS_SYSTEM, 9, 0, GRAN_BYTE);
+}
+
+
+/* Returns a descriptor that yields the given LIMIT and BASE when
+   used as an operand for the LGDT instruction. */
+static uint64_t
+make_gdtr_operand (uint16_t limit, void *base)
+{
+  return limit | ((uint64_t) (uint32_t) base << 16);
+}
diff --git a/userprog/gdt.h b/userprog/gdt.h
new file mode 100644
index 0000000..81fe50c
--- /dev/null
+++ b/userprog/gdt.h
@@ -0,0 +1,15 @@
+#ifndef USERPROG_GDT_H
+#define USERPROG_GDT_H
+
+#include "threads/loader.h"
+
+/* Segment selectors.
+   More selectors are defined by the loader in loader.h. */
+#define SEL_UCSEG       0x1B    /* User code selector. */
+#define SEL_UDSEG       0x23    /* User data selector. */
+#define SEL_TSS         0x28    /* Task-state segment. */
+#define SEL_CNT         6       /* Number of segments. */
+
+void gdt_init (void);
+
+#endif /* userprog/gdt.h */
diff --git a/userprog/pagedir.c b/userprog/pagedir.c
new file mode 100644
index 0000000..a6a87b8
--- /dev/null
+++ b/userprog/pagedir.c
@@ -0,0 +1,263 @@
+#include "userprog/pagedir.h"
+#include <stdbool.h>
+#include <stddef.h>
+#include <string.h>
+#include "threads/init.h"
+#include "threads/pte.h"
+#include "threads/palloc.h"
+
+static uint32_t *active_pd (void);
+static void invalidate_pagedir (uint32_t *);
+
+/* Creates a new page directory that has mappings for kernel
+   virtual addresses, but none for user virtual addresses.
+   Returns the new page directory, or a null pointer if memory
+   allocation fails. */
+uint32_t *
+pagedir_create (void) 
+{
+  uint32_t *pd = palloc_get_page (0);
+  if (pd != NULL)
+    memcpy (pd, init_page_dir, PGSIZE);
+  return pd;
+}
+
+/* Destroys page directory PD, freeing all the pages it
+   references. */
+void
+pagedir_destroy (uint32_t *pd) 
+{
+  uint32_t *pde;
+
+  if (pd == NULL)
+    return;
+
+  ASSERT (pd != init_page_dir);
+  for (pde = pd; pde < pd + pd_no (PHYS_BASE); pde++)
+    if (*pde & PTE_P) 
+      {
+        uint32_t *pt = pde_get_pt (*pde);
+        uint32_t *pte;
+        
+        for (pte = pt; pte < pt + PGSIZE / sizeof *pte; pte++)
+          if (*pte & PTE_P) 
+            palloc_free_page (pte_get_page (*pte));
+        palloc_free_page (pt);
+      }
+  palloc_free_page (pd);
+}
+
+/* Returns the address of the page table entry for virtual
+   address VADDR in page directory PD.
+   If PD does not have a page table for VADDR, behavior depends
+   on CREATE.  If CREATE is true, then a new page table is
+   created and a pointer into it is returned.  Otherwise, a null
+   pointer is returned. */
+static uint32_t *
+lookup_page (uint32_t *pd, const void *vaddr, bool create)
+{
+  uint32_t *pt, *pde;
+
+  ASSERT (pd != NULL);
+
+  /* Shouldn't create new kernel virtual mappings. */
+  ASSERT (!create || is_user_vaddr (vaddr));
+
+  /* Check for a page table for VADDR.
+     If one is missing, create one if requested. */
+  pde = pd + pd_no (vaddr);
+  if (*pde == 0) 
+    {
+      if (create)
+        {
+          pt = palloc_get_page (PAL_ZERO);
+          if (pt == NULL) 
+            return NULL; 
+      
+          *pde = pde_create (pt);
+        }
+      else
+        return NULL;
+    }
+
+  /* Return the page table entry. */
+  pt = pde_get_pt (*pde);
+  return &pt[pt_no (vaddr)];
+}
+
+/* Adds a mapping in page directory PD from user virtual page
+   UPAGE to the physical frame identified by kernel virtual
+   address KPAGE.
+   UPAGE must not already be mapped.
+   KPAGE should probably be a page obtained from the user pool
+   with palloc_get_page().
+   If WRITABLE is true, the new page is read/write;
+   otherwise it is read-only.
+   Returns true if successful, false if memory allocation
+   failed. */
+bool
+pagedir_set_page (uint32_t *pd, void *upage, void *kpage, bool writable)
+{
+  uint32_t *pte;
+
+  ASSERT (pg_ofs (upage) == 0);
+  ASSERT (pg_ofs (kpage) == 0);
+  ASSERT (is_user_vaddr (upage));
+  ASSERT (vtop (kpage) >> PTSHIFT < init_ram_pages);
+  ASSERT (pd != init_page_dir);
+
+  pte = lookup_page (pd, upage, true);
+
+  if (pte != NULL) 
+    {
+      ASSERT ((*pte & PTE_P) == 0);
+      *pte = pte_create_user (kpage, writable);
+      return true;
+    }
+  else
+    return false;
+}
+
+/* Looks up the physical address that corresponds to user virtual
+   address UADDR in PD.  Returns the kernel virtual address
+   corresponding to that physical address, or a null pointer if
+   UADDR is unmapped. */
+void *
+pagedir_get_page (uint32_t *pd, const void *uaddr) 
+{
+  uint32_t *pte;
+
+  ASSERT (is_user_vaddr (uaddr));
+  
+  pte = lookup_page (pd, uaddr, false);
+  if (pte != NULL && (*pte & PTE_P) != 0)
+    return pte_get_page (*pte) + pg_ofs (uaddr);
+  else
+    return NULL;
+}
+
+/* Marks user virtual page UPAGE "not present" in page
+   directory PD.  Later accesses to the page will fault.  Other
+   bits in the page table entry are preserved.
+   UPAGE need not be mapped. */
+void
+pagedir_clear_page (uint32_t *pd, void *upage) 
+{
+  uint32_t *pte;
+
+  ASSERT (pg_ofs (upage) == 0);
+  ASSERT (is_user_vaddr (upage));
+
+  pte = lookup_page (pd, upage, false);
+  if (pte != NULL && (*pte & PTE_P) != 0)
+    {
+      *pte &= ~PTE_P;
+      invalidate_pagedir (pd);
+    }
+}
+
+/* Returns true if the PTE for virtual page VPAGE in PD is dirty,
+   that is, if the page has been modified since the PTE was
+   installed.
+   Returns false if PD contains no PTE for VPAGE. */
+bool
+pagedir_is_dirty (uint32_t *pd, const void *vpage) 
+{
+  uint32_t *pte = lookup_page (pd, vpage, false);
+  return pte != NULL && (*pte & PTE_D) != 0;
+}
+
+/* Set the dirty bit to DIRTY in the PTE for virtual page VPAGE
+   in PD. */
+void
+pagedir_set_dirty (uint32_t *pd, const void *vpage, bool dirty) 
+{
+  uint32_t *pte = lookup_page (pd, vpage, false);
+  if (pte != NULL) 
+    {
+      if (dirty)
+        *pte |= PTE_D;
+      else 
+        {
+          *pte &= ~(uint32_t) PTE_D;
+          invalidate_pagedir (pd);
+        }
+    }
+}
+
+/* Returns true if the PTE for virtual page VPAGE in PD has been
+   accessed recently, that is, between the time the PTE was
+   installed and the last time it was cleared.  Returns false if
+   PD contains no PTE for VPAGE. */
+bool
+pagedir_is_accessed (uint32_t *pd, const void *vpage) 
+{
+  uint32_t *pte = lookup_page (pd, vpage, false);
+  return pte != NULL && (*pte & PTE_A) != 0;
+}
+
+/* Sets the accessed bit to ACCESSED in the PTE for virtual page
+   VPAGE in PD. */
+void
+pagedir_set_accessed (uint32_t *pd, const void *vpage, bool accessed) 
+{
+  uint32_t *pte = lookup_page (pd, vpage, false);
+  if (pte != NULL) 
+    {
+      if (accessed)
+        *pte |= PTE_A;
+      else 
+        {
+          *pte &= ~(uint32_t) PTE_A; 
+          invalidate_pagedir (pd);
+        }
+    }
+}
+
+/* Loads page directory PD into the CPU's page directory base
+   register. */
+void
+pagedir_activate (uint32_t *pd) 
+{
+  if (pd == NULL)
+    pd = init_page_dir;
+
+  /* Store the physical address of the page directory into CR3
+     aka PDBR (page directory base register).  This activates our
+     new page tables immediately.  See [IA32-v2a] "MOV--Move
+     to/from Control Registers" and [IA32-v3a] 3.7.5 "Base
+     Address of the Page Directory". */
+  asm volatile ("movl %0, %%cr3" : : "r" (vtop (pd)) : "memory");
+}
+
+/* Returns the currently active page directory. */
+static uint32_t *
+active_pd (void) 
+{
+  /* Copy CR3, the page directory base register (PDBR), into
+     `pd'.
+     See [IA32-v2a] "MOV--Move to/from Control Registers" and
+     [IA32-v3a] 3.7.5 "Base Address of the Page Directory". */
+  uintptr_t pd;
+  asm volatile ("movl %%cr3, %0" : "=r" (pd));
+  return ptov (pd);
+}
+
+/* Seom page table changes can cause the CPU's translation
+   lookaside buffer (TLB) to become out-of-sync with the page
+   table.  When this happens, we have to "invalidate" the TLB by
+   re-activating it.
+
+   This function invalidates the TLB if PD is the active page
+   directory.  (If PD is not active then its entries are not in
+   the TLB, so there is no need to invalidate anything.) */
+static void
+invalidate_pagedir (uint32_t *pd) 
+{
+  if (active_pd () == pd) 
+    {
+      /* Re-activating PD clears the TLB.  See [IA32-v3a] 3.12
+         "Translation Lookaside Buffers (TLBs)". */
+      pagedir_activate (pd);
+    } 
+}
diff --git a/userprog/pagedir.h b/userprog/pagedir.h
new file mode 100644
index 0000000..cd92447
--- /dev/null
+++ b/userprog/pagedir.h
@@ -0,0 +1,18 @@
+#ifndef USERPROG_PAGEDIR_H
+#define USERPROG_PAGEDIR_H
+
+#include <stdbool.h>
+#include <stdint.h>
+
+uint32_t *pagedir_create (void);
+void pagedir_destroy (uint32_t *pd);
+bool pagedir_set_page (uint32_t *pd, void *upage, void *kpage, bool rw);
+void *pagedir_get_page (uint32_t *pd, const void *upage);
+void pagedir_clear_page (uint32_t *pd, void *upage);
+bool pagedir_is_dirty (uint32_t *pd, const void *upage);
+void pagedir_set_dirty (uint32_t *pd, const void *upage, bool dirty);
+bool pagedir_is_accessed (uint32_t *pd, const void *upage);
+void pagedir_set_accessed (uint32_t *pd, const void *upage, bool accessed);
+void pagedir_activate (uint32_t *pd);
+
+#endif /* userprog/pagedir.h */
diff --git a/userprog/process.c b/userprog/process.c
new file mode 100644
index 0000000..adb6b66
--- /dev/null
+++ b/userprog/process.c
@@ -0,0 +1,721 @@
+#include "userprog/process.h"
+#include <debug.h>
+#include <inttypes.h>
+#include <round.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include "userprog/gdt.h"
+#include "userprog/pagedir.h"
+#include "userprog/tss.h"
+#include "filesys/directory.h"
+#include "filesys/file.h"
+#include "filesys/filesys.h"
+#include "threads/flags.h"
+#include "threads/init.h"
+#include "threads/interrupt.h"
+#include "threads/palloc.h"
+#include "threads/synch.h"
+#include "threads/thread.h"
+#include "threads/vaddr.h"
+
+/* data structure to communicate with the thread initializing a new process */
+struct start_aux_data {
+  char *filename;
+  struct semaphore startup_sem;
+  struct thread *parent_thread;
+  struct process *new_process;
+};
+
+/* filesystem lock */
+struct lock filesys_lock;
+
+/* prototypes */
+static thread_func start_process NO_RETURN;
+static bool load (char *filename, void (**eip) (void), void **esp);
+static bool setup_stack (void **esp);
+static bool init_fd_table (struct fd_table * table);
+
+/* Initialize the filesystem lock */
+void
+process_init ()
+{
+  lock_init (&filesys_lock);
+}
+
+/* Get current process (only valid for processes) */
+struct process*
+process_current ()
+{
+    ASSERT (thread_current()->process != NULL);
+    return thread_current()->process;
+}
+
+/* Starts a new thread running a user program loaded from
+   `filename`.
+   The new thread may be scheduled (and may even exit)
+   before process_execute() returns.  Returns the new process's
+   thread id, or TID_ERROR if the thread cannot be created.
+
+   In the first assignment, you should change this to function to
+
+     process_execute (const char *cmd)
+
+   and support command strings such as "echo A B C". You
+   will also need to change `load` and `setup_stack`. */
+tid_t
+process_execute (const char *filename)
+{
+  tid_t tid = TID_ERROR;
+  char *fn_copy = NULL;
+  struct start_aux_data *aux_data = NULL;
+
+  /* Setup the auxiliary data for starting up the new process */
+  fn_copy = palloc_get_page (0);
+  aux_data = palloc_get_page (0);
+  if (aux_data == NULL || fn_copy == NULL)
+    goto done;
+  strlcpy (fn_copy, filename, PGSIZE);
+  aux_data->filename = fn_copy;
+  aux_data->parent_thread = thread_current ();
+  aux_data->new_process = NULL;
+  sema_init (&aux_data->startup_sem, 0);
+
+  /* Create a new thread to execute FILE_NAME. */
+  tid = thread_create (fn_copy, PRI_DEFAULT, start_process, aux_data);
+  if (tid == TID_ERROR)
+    goto done;
+
+  /* wait for startup */
+  sema_down (&aux_data->startup_sem);
+  if (aux_data->new_process == NULL) {
+    tid = TID_ERROR;
+    goto done;
+  }
+  /* register child process */
+  list_push_back (&thread_current()->children, 
+                  &aux_data->new_process->parentelem);
+
+ done:
+  palloc_free_page (fn_copy);
+  palloc_free_page (aux_data);
+  return tid;
+}
+
+/* A thread function that loads a user process and starts it
+   running. */
+static void
+start_process (void *aux)
+{
+  struct intr_frame if_;
+  struct start_aux_data *aux_data = (struct start_aux_data*) aux;
+  struct thread *thread = thread_current ();
+
+  /* Initialize Process */
+  struct process *process = palloc_get_page (PAL_ZERO);
+  if (process == NULL)
+    goto signal;
+  sema_init (&process->exit_sem, 0);
+  lock_init (&process->exit_lock);
+  process->exit_status = -1;
+  if (! init_fd_table (&process->fd_table))
+    goto signal;
+
+  /* register process */
+  process->thread_id  = thread->tid;
+  process->parent_tid = aux_data->parent_thread->tid;
+  thread->process = process;
+
+  /* Initialize interrupt frame and load executable. */
+  memset (&if_, 0, sizeof if_);
+  if_.gs = if_.fs = if_.es = if_.ds = if_.ss = SEL_UDSEG;
+  if_.cs = SEL_UCSEG;
+  if_.eflags = FLAG_IF | FLAG_MBS;
+  if (! load (aux_data->filename, &if_.eip, &if_.esp)) {
+    thread->process = NULL;
+  } else {
+    aux_data->new_process = thread->process;
+  }
+
+  signal:
+  /* Signal the parent process that loading is finished */
+  sema_up (&aux_data->startup_sem); /* transfer ownership of aux_data */
+
+  /* If process startup failed, quit. */
+  if (thread->process == NULL)  {
+    if (process != NULL) {
+      if (process->fd_table.fds != NULL)
+        palloc_free_page (process->fd_table.fds);
+      palloc_free_page (process);
+    }
+    thread_exit ();
+  }
+
+  /* Start the user process by simulating a return from an
+     interrupt, implemented by intr_exit (in
+     threads/intr-stubs.S).  Because intr_exit takes all of its
+     arguments on the stack in the form of a `struct intr_frame',
+     we just point the stack pointer (%esp) to our stack frame
+     and jump to it. */
+  asm volatile ("movl %0, %%esp; jmp intr_exit" : : "g" (&if_) : "memory");
+  NOT_REACHED ();
+}
+
+/* Waits for thread TID to die and returns its exit status.  If
+   it was terminated by the kernel (i.e. killed due to an
+   exception), returns -1.  If TID is invalid or if it was not a
+   child of the calling process, or if process_wait() has already
+   been successfully called for the given TID, returns -1
+   immediately, without waiting. */
+int
+process_wait (tid_t child_tid)
+{
+  struct thread *cur = thread_current ();
+  struct process *child = NULL;
+
+  /* iterate over child processes */
+  struct list_elem *e = list_head (&cur->children);
+  while ((e = list_next (e)) != list_end (&cur->children)) {
+    struct process* t = list_entry (e, struct process, parentelem);
+    if (t->thread_id == child_tid) {
+      list_remove (e);
+      child = t;
+      break;
+    }
+  }
+  if (child == NULL) {
+    return -1;
+  }
+  sema_down (&child->exit_sem);
+  int exit_status = child->exit_status;
+  palloc_free_page (child);
+  return exit_status;
+}
+
+/* Free the current process's resources. */
+void
+process_exit (void)
+{
+  struct thread *thread = thread_current ();
+  ASSERT (thread != NULL);
+
+  /* remove (and if necessary clean up) child processes */
+  struct list_elem *e = list_head (&thread->children);
+  while ((e = list_next (e)) != list_end (&thread->children)) {
+    struct process *p = list_entry (e, struct process, parentelem);
+    bool process_dying;
+    lock_acquire (&p->exit_lock);
+    process_dying = p->parent_tid < 0;
+    p->parent_tid = -1;
+    lock_release (&p->exit_lock);
+    if (process_dying)
+      palloc_free_page (p);
+  }
+
+  if (thread->process == NULL)
+    return; /* not a process, nothing else left to do */
+
+  struct process *proc = thread->process;
+  uint32_t *pd;
+
+  printf ("%s: exit(%d)\n", thread->name, proc->exit_status);
+
+  /* close executable, allow write */
+  if (proc->executable != NULL) {
+    lock_acquire (&filesys_lock);
+    file_close (proc->executable);
+    lock_release (&filesys_lock);
+  }
+
+  int fd;
+  for (fd = 2; fd <= proc->fd_table.fd_max; fd++) {
+    process_close_file (fd);
+  }
+  palloc_free_page (proc->fd_table.fds);
+
+  /* Destroy the current process's page directory and switch back
+     to the kernel-only page directory. */
+  pd = thread->pagedir;
+  if (pd != NULL) {
+    /* Correct ordering here is crucial.  We must set
+         cur->pagedir to NULL before switching page directories,
+         so that a timer interrupt can't switch back to the
+         process page directory.  We must activate the base page
+         directory before destroying the process's page
+         directory, or our active page directory will be one
+         that's been freed (and cleared). */
+    thread->pagedir = NULL;
+    pagedir_activate (NULL);
+    pagedir_destroy (pd);
+  }
+
+  /* Destroy the process structure if the parent is not alive
+   * any more. Atomic test and set would be sufficient here.
+   */
+  bool parent_dead = false;
+  lock_acquire (&proc->exit_lock);
+  parent_dead = proc->parent_tid < 0;
+  proc->parent_tid = -1;
+  lock_release (&proc->exit_lock);
+  if (parent_dead) {
+    palloc_free_page (proc);
+  } else {
+    sema_up (&proc->exit_sem);
+  }
+}
+
+/* Sets up the CPU for running user code in the current
+   thread.
+   This function is called on every context switch. */
+void
+process_activate (void)
+{
+  struct thread *t = thread_current ();
+  /* Activate thread's page tables. */
+  pagedir_activate (t->pagedir);
+
+  /* Set thread's kernel stack for use in processing
+     interrupts. */
+  tss_update ();
+}
+
+/* We load ELF binaries.  The following definitions are taken
+   from the ELF specification, [ELF1], more-or-less verbatim.  */
+
+/* ELF types.  See [ELF1] 1-2. */
+typedef uint32_t Elf32_Word, Elf32_Addr, Elf32_Off;
+typedef uint16_t Elf32_Half;
+
+/* For use with ELF types in printf(). */
+#define PE32Wx PRIx32   /* Print Elf32_Word in hexadecimal. */
+#define PE32Ax PRIx32   /* Print Elf32_Addr in hexadecimal. */
+#define PE32Ox PRIx32   /* Print Elf32_Off in hexadecimal. */
+#define PE32Hx PRIx16   /* Print Elf32_Half in hexadecimal. */
+
+/* Executable header.  See [ELF1] 1-4 to 1-8.
+   This appears at the very beginning of an ELF binary. */
+struct Elf32_Ehdr
+{
+  unsigned char e_ident[16];
+  Elf32_Half    e_type;
+  Elf32_Half    e_machine;
+  Elf32_Word    e_version;
+  Elf32_Addr    e_entry;
+  Elf32_Off     e_phoff;
+  Elf32_Off     e_shoff;
+  Elf32_Word    e_flags;
+  Elf32_Half    e_ehsize;
+  Elf32_Half    e_phentsize;
+  Elf32_Half    e_phnum;
+  Elf32_Half    e_shentsize;
+  Elf32_Half    e_shnum;
+  Elf32_Half    e_shstrndx;
+};
+
+/* Program header.  See [ELF1] 2-2 to 2-4.
+   There are e_phnum of these, starting at file offset e_phoff
+   (see [ELF1] 1-6). */
+struct Elf32_Phdr
+{
+  Elf32_Word p_type;
+  Elf32_Off  p_offset;
+  Elf32_Addr p_vaddr;
+  Elf32_Addr p_paddr;
+  Elf32_Word p_filesz;
+  Elf32_Word p_memsz;
+  Elf32_Word p_flags;
+  Elf32_Word p_align;
+};
+
+/* Values for p_type.  See [ELF1] 2-3. */
+#define PT_NULL    0            /* Ignore. */
+#define PT_LOAD    1            /* Loadable segment. */
+#define PT_DYNAMIC 2            /* Dynamic linking info. */
+#define PT_INTERP  3            /* Name of dynamic loader. */
+#define PT_NOTE    4            /* Auxiliary info. */
+#define PT_SHLIB   5            /* Reserved. */
+#define PT_PHDR    6            /* Program header table. */
+#define PT_STACK   0x6474e551   /* Stack segment. */
+
+/* Flags for p_flags.  See [ELF3] 2-3 and 2-4. */
+#define PF_X 1          /* Executable. */
+#define PF_W 2          /* Writable. */
+#define PF_R 4          /* Readable. */
+
+static bool validate_segment (const struct Elf32_Phdr *, struct file *);
+static bool load_segment (struct file *file, off_t ofs, uint8_t *upage,
+    uint32_t read_bytes, uint32_t zero_bytes,
+    bool writable);
+
+/* Loads an ELF executable from file_name (the first word of
+   cmd) into the current thread.
+   Stores the executable's entry point into *EIP
+   and its initial stack pointer into *ESP.
+   Returns true if successful, false otherwise. */
+bool
+load (char *file_name, void (**eip) (void), void **esp)
+{
+  struct thread *t = thread_current ();
+  struct Elf32_Ehdr ehdr;
+  struct file *file = NULL;
+  off_t file_ofs;
+  bool success = false;
+  int i;
+
+  /* Allocate and activate page directory. */
+  t->pagedir = pagedir_create ();
+  if (t->pagedir == NULL)
+    return false;
+  process_activate ();
+
+  /* Coarse grained filesystem lock for loading */
+  lock_acquire (&filesys_lock);
+
+  /* Open executable file. */
+  file = filesys_open (file_name);
+  if (file == NULL)
+    goto done;
+
+  /* Deny writes to the file during loading */
+  file_deny_write (file);
+
+  /* Read and verify executable header. */
+  if (file_read (file, &ehdr, sizeof ehdr) != sizeof ehdr
+      || memcmp (ehdr.e_ident, "\177ELF\1\1\1", 7)
+      || ehdr.e_type != 2
+      || ehdr.e_machine != 3
+      || ehdr.e_version != 1
+      || ehdr.e_phentsize != sizeof (struct Elf32_Phdr)
+      || ehdr.e_phnum > 1024)
+  {
+    printf ("load: %s: error loading executable\n", file_name);
+    goto done;
+  }
+
+  /* Read program headers. */
+  file_ofs = ehdr.e_phoff;
+  for (i = 0; i < ehdr.e_phnum; i++)
+  {
+    struct Elf32_Phdr phdr;
+
+    if (file_ofs < 0 || file_ofs > file_length (file))
+      goto done;
+    file_seek (file, file_ofs);
+
+    if (file_read (file, &phdr, sizeof phdr) != sizeof phdr)
+      goto done;
+    file_ofs += sizeof phdr;
+    if (phdr.p_vaddr < PGSIZE)
+      continue; /* Ignore build-id segment */
+    switch (phdr.p_type)
+    {
+    case PT_NULL:
+    case PT_NOTE:
+    case PT_PHDR:
+    case PT_STACK:
+    default:
+      /* Ignore this segment. */
+      break;
+    case PT_DYNAMIC:
+    case PT_INTERP:
+    case PT_SHLIB:
+      goto done;
+    case PT_LOAD:
+      if (phdr.p_vaddr == 0)
+        break; // Ignore the .note.gnu.build-i segment
+      if (validate_segment (&phdr, file))
+      {
+        bool writable = (phdr.p_flags & PF_W) != 0;
+        uint32_t file_page = phdr.p_offset & ~PGMASK;
+        uint32_t mem_page = phdr.p_vaddr & ~PGMASK;
+        uint32_t page_offset = phdr.p_vaddr & PGMASK;
+        uint32_t read_bytes, zero_bytes;
+        if (phdr.p_filesz > 0)
+        {
+          /* Normal segment.
+                     Read initial part from disk and zero the rest. */
+          read_bytes = page_offset + phdr.p_filesz;
+          zero_bytes = (ROUND_UP (page_offset + phdr.p_memsz, PGSIZE)
+              - read_bytes);
+        }
+        else
+        {
+          /* Entirely zero.
+                     Don't read anything from disk. */
+          read_bytes = 0;
+          zero_bytes = ROUND_UP (page_offset + phdr.p_memsz, PGSIZE);
+        }
+        if (!load_segment (file, file_page, (void *) mem_page,
+            read_bytes, zero_bytes, writable))
+          goto done;
+      }
+      else
+        goto done;
+      break;
+    }
+  }
+
+  /* Set up stack. */
+  if (!setup_stack (esp))
+    goto done;
+
+  /* Start address. */
+  *eip = (void (*) (void)) ehdr.e_entry;
+
+  success = true;
+
+  done:
+  /* We arrive here whether the load is successful or not. */
+  if (success) {
+    process_current()->executable = file;
+  } else {
+    file_close (file);
+  }
+  lock_release (&filesys_lock);
+  return success;
+}
+
+/* load() helpers. */
+
+static bool install_page (void *upage, void *kpage, bool writable);
+
+/* Checks whether PHDR describes a valid, loadable segment in
+   FILE and returns true if so, false otherwise. */
+static bool
+validate_segment (const struct Elf32_Phdr *phdr, struct file *file)
+{
+  /* p_offset and p_vaddr must have the same page offset. */
+  if ((phdr->p_offset & PGMASK) != (phdr->p_vaddr & PGMASK))
+    return false;
+
+  /* p_offset must point within FILE. */
+  if (phdr->p_offset > (Elf32_Off) file_length (file))
+    return false;
+
+  /* p_memsz must be at least as big as p_filesz. */
+  if (phdr->p_memsz < phdr->p_filesz)
+    return false;
+
+  /* The segment must not be empty. */
+  if (phdr->p_memsz == 0)
+    return false;
+
+  /* The virtual memory region must both start and end within the
+     user address space range. */
+  if (!is_user_vaddr ((void *) phdr->p_vaddr))
+    return false;
+  if (!is_user_vaddr ((void *) (phdr->p_vaddr + phdr->p_memsz)))
+    return false;
+
+  /* The region cannot "wrap around" across the kernel virtual
+     address space. */
+  if (phdr->p_vaddr + phdr->p_memsz < phdr->p_vaddr)
+    return false;
+
+  /* Disallow mapping page 0.
+     Not only is it a bad idea to map page 0, but if we allowed
+     it then user code that passed a null pointer to system calls
+     could quite likely panic the kernel by way of null pointer
+     assertions in memcpy(), etc. */
+  if (phdr->p_vaddr < PGSIZE)
+    return false;
+
+  /* It's okay. */
+  return true;
+}
+
+/* Loads a segment starting at offset OFS in FILE at address
+   UPAGE.  In total, READ_BYTES + ZERO_BYTES bytes of virtual
+   memory are initialized, as follows:
+
+        - READ_BYTES bytes at UPAGE must be read from FILE
+          starting at offset OFS.
+
+        - ZERO_BYTES bytes at UPAGE + READ_BYTES must be zeroed.
+
+   The pages initialized by this function must be writable by the
+   user process if WRITABLE is true, read-only otherwise.
+
+   Return true if successful, false if a memory allocation error
+   or disk read error occurs. */
+static bool
+load_segment (struct file *file, off_t ofs, uint8_t *upage,
+    uint32_t read_bytes, uint32_t zero_bytes, bool writable)
+{
+  ASSERT ((read_bytes + zero_bytes) % PGSIZE == 0);
+  ASSERT (pg_ofs (upage) == 0);
+  ASSERT (ofs % PGSIZE == 0);
+
+  file_seek (file, ofs);
+  while (read_bytes > 0 || zero_bytes > 0)
+  {
+    /* Calculate how to fill this page.
+         We will read PAGE_READ_BYTES bytes from FILE
+         and zero the final PAGE_ZERO_BYTES bytes. */
+    size_t page_read_bytes = read_bytes < PGSIZE ? read_bytes : PGSIZE;
+    size_t page_zero_bytes = PGSIZE - page_read_bytes;
+
+    /* Get a page of memory. */
+    uint8_t *kpage = palloc_get_page (PAL_USER);
+    if (kpage == NULL)
+      return false;
+
+    /* Load this page. */
+    if (file_read (file, kpage, page_read_bytes) != (int) page_read_bytes)
+    {
+      palloc_free_page (kpage);
+      return false;
+    }
+    memset (kpage + page_read_bytes, 0, page_zero_bytes);
+
+    /* Add the page to the process's address space. */
+    if (!install_page (upage, kpage, writable))
+    {
+      palloc_free_page (kpage);
+      return false;
+    }
+
+    /* Advance. */
+    read_bytes -= page_read_bytes;
+    zero_bytes -= page_zero_bytes;
+    upage += PGSIZE;
+  }
+  return true;
+}
+
+/* Create a minimal stack by mapping a zeroed page at the top of
+   user virtual memory.
+   You will implement this function in the Project 0.
+   Consider using `hex_dump` for debugging purposes */
+static bool
+setup_stack (void **esp)
+{
+  uint8_t *kpage = NULL;
+
+  kpage = palloc_get_page (PAL_USER | PAL_ZERO);
+  if (kpage == NULL)
+      return false;
+
+  if (! install_page (((uint8_t *) PHYS_BASE) - PGSIZE, kpage, true)) {
+      palloc_free_page (kpage);
+      return false;
+  }
+
+  /* Currently we assume that 'argc = 0' */
+  *esp = PHYS_BASE - 12;
+
+  return true;
+}
+
+/* Adds a mapping from user virtual address UPAGE to kernel
+   virtual address KPAGE to the page table.
+   If WRITABLE is true, the user process may modify the page;
+   otherwise, it is read-only.
+   UPAGE must not already be mapped.
+   KPAGE should probably be a page obtained from the user pool
+   with palloc_get_page().
+   Returns true on success, false if UPAGE is already mapped or
+   if memory allocation fails. */
+static bool
+install_page (void *upage, void *kpage, bool writable)
+{
+  struct thread *t = thread_current ();
+
+  /* Verify that there's not already a page at that virtual
+     address, then map our page there. */
+  return (pagedir_get_page (t->pagedir, upage) == NULL
+      && pagedir_set_page (t->pagedir, upage, kpage, writable));
+}
+
+static
+bool
+init_fd_table (struct fd_table *table)
+{
+  table->fds = palloc_get_page (PAL_ZERO);
+  if (table->fds == NULL)
+    return false;
+  table->fd_cap = PGSIZE / sizeof (table->fds[0]);
+  table->fd_free = 2;
+  table->fd_max  = 1;
+  return true;
+}
+
+/* Open the file with the given name; returns
+   a file descriptor for this file if successful,
+   and a negative value otherwise */
+int
+process_open_file (const char* fname)
+{
+  struct fd_table *fdt = &process_current()->fd_table;
+  if (fdt->fd_free >= fdt->fd_cap)
+    return -1;
+
+  lock_acquire (&filesys_lock);
+  struct file *f = filesys_open (fname);
+  lock_release (&filesys_lock);
+
+  if (f == NULL)
+    return -1;
+
+  int fd = fdt->fd_free++;
+  fdt->fds[fd] = f;
+
+  /* update index of free/max file descriptor index*/
+  if (fd > fdt->fd_max) fdt->fd_max = fd;
+  while (fdt->fds[fdt->fd_free] != NULL) {
+    fdt->fd_free++;
+    if (fdt->fd_free >= fdt->fd_cap)
+      break;
+  }
+  return fd;
+}
+
+/* Get the file associated with the given file
+   descriptor; return NULL if no file is associated
+   with the given descriptor */
+struct file*
+process_get_file (int fd)
+{
+  struct fd_table *fdt = &process_current()->fd_table;
+  if (fd < 2 || fd >= fdt->fd_cap || ! fdt->fds[fd])
+    return NULL;
+  return fdt->fds[fd];
+}
+
+/* Acquire global lock for the filesystem */
+void process_lock_filesys (void)
+{
+  lock_acquire (&filesys_lock);
+}
+
+/* Release global filesystem lock */
+void process_unlock_filesys (void)
+{
+  lock_release (&filesys_lock);
+}
+
+/* Close the file associated with the given file
+   descriptor; returns true if close was successful */
+bool
+process_close_file (int fd)
+{
+  struct file *file = process_get_file (fd);
+  if (file == NULL)
+    return false;
+
+  lock_acquire (&filesys_lock);
+  file_close (file);
+  lock_release (&filesys_lock);
+
+  struct fd_table *fdt = &process_current()->fd_table;
+  fdt->fds[fd] = NULL;
+
+  /* update index of free/max file descriptor index*/
+  if (fd < fdt->fd_free) fdt->fd_free = fd;
+  while (fdt->fds[fdt->fd_max] == NULL) {
+    fdt->fd_max--;
+    if (fdt->fd_max < 2)
+      break;
+  }
+  return true;
+}
diff --git a/userprog/process.h b/userprog/process.h
new file mode 100644
index 0000000..1609801
--- /dev/null
+++ b/userprog/process.h
@@ -0,0 +1,47 @@
+#ifndef USERPROG_PROCESS_H
+#define USERPROG_PROCESS_H
+
+#include "threads/thread.h"
+
+/* In the current implementation, the capacity is fixed to 1024 (PGSIZE/4) */
+struct fd_table {
+    struct file** fds;
+    int fd_free;    /* lowest-index free FD table entry */
+    int fd_max;     /* highest-index used FD table entry */
+    int fd_cap;     /* FD table capacity */
+};
+
+struct process {
+    /* process tree */
+    tid_t thread_id;
+    tid_t parent_tid;
+    struct list_elem parentelem;       /* Owned by parent */
+
+    /* communication with parent process */
+    struct semaphore exit_sem;
+    struct lock exit_lock;
+    int exit_status;
+
+    /* files */
+    struct file *executable;           /* Loaded executable, if any. */
+    struct fd_table fd_table;          /* File descriptor table */
+
+    /* Owned by syscall.c */
+    void* syscall_buffer;
+    size_t syscall_buffer_page_cnt;
+};
+
+void process_init (void);
+struct process* process_current (void);
+tid_t process_execute (const char *file_name);
+int process_wait (tid_t);
+void process_exit (void);
+void process_activate (void);
+
+int process_open_file(const char* fname);
+struct file* process_get_file(int fd);
+void process_lock_filesys (void);
+void process_unlock_filesys (void);
+bool process_close_file(int fd);
+
+#endif /* userprog/process.h */
diff --git a/userprog/syscall.c b/userprog/syscall.c
new file mode 100644
index 0000000..f8e0197
--- /dev/null
+++ b/userprog/syscall.c
@@ -0,0 +1,563 @@
+#include <stdio.h>
+#include <syscall-nr.h>
+#include "devices/input.h"
+#include "devices/shutdown.h"
+#include "filesys/file.h"
+#include "filesys/filesys.h"
+#include "filesys/inode.h"
+#include "lib/string.h"
+#include "threads/interrupt.h"
+#include "threads/palloc.h"
+#include "threads/synch.h"
+#include "threads/thread.h"
+#include "threads/vaddr.h"
+#include "userprog/pagedir.h"
+#include "userprog/process.h"
+#include "userprog/syscall.h"
+
+#define STACK_SLOT_SIZE sizeof(int)
+
+/* Prototypes for Utilities */
+static int get_user (const uint8_t *uaddr);
+static bool put_user (uint8_t *udst, uint8_t byte);
+static void* memcpy_from_user (void *kaddr, void *uaddr, size_t bytes);
+static void* memcpy_to_user (void *kaddr, void *addr, size_t bytes);
+static void* copy_string_arg  (void *usp, bool *segfault);
+static void free_string_arg_buf (void *kbuf);
+
+/* Reads a byte at user virtual address UADDR.
+   UADDR must be below PHYS_BASE.
+   Returns the byte value if successful, -1 if a segfault
+   occurred. */
+static int
+get_user (const uint8_t *uaddr)
+{
+  int result;
+  asm ("movl $1f, %0; "  /* save eip in eax */
+       "movzbl %1, %0; " /* read byte from user memory into eax */
+       "1:"              /* continue here on page fault, with eax set to -1 */
+       : "=&a" (result) : "m" (*uaddr));
+  return result;
+}
+
+/* Writes BYTE to user address UDST.
+   UDST must be below PHYS_BASE.
+   Returns true if successful, false if a segfault occurred. */
+static bool
+put_user (uint8_t *udst, uint8_t byte)
+{
+  int error_code;
+  asm ("movl $1f, %0;" /* save EIP in EAX */
+       "movb %b2, %1;" /* write byte to user memory  */
+       "1:"            /* continue here on page fault, with eax set to -1 */
+       : "=&a" (error_code), "=m" (*udst) : "q" (byte));
+  return error_code != -1;
+}
+
+/* Copy bytes from user space; returns NULL if a segfault
+   occured, and kaddr otherwise */
+static void*
+memcpy_from_user (void *kaddr, void *uaddr, size_t bytes)
+{
+  uint8_t* kp = kaddr;
+  size_t i;
+  if (! is_user_vaddr (uaddr) ||
+      ! is_user_vaddr (uaddr + bytes - 1))
+    return false;
+  for (i=0;i<bytes;i++) {
+    int b = get_user (uaddr+i);
+    if (b < 0)
+      break; /* segfault */
+    else
+      kp[i] = b;
+  }
+  if (i != bytes)
+    return NULL; /* segfault */
+  return kaddr;
+}
+
+/* Copy bytes to user space; returns NULL if a segfault
+   occured, and uaddr otherwise */
+static void*
+memcpy_to_user (void *uaddr, void *kaddr, size_t bytes)
+{
+  uint8_t* kp = kaddr;
+  size_t i;
+  if (! is_user_vaddr (uaddr) ||
+      ! is_user_vaddr (uaddr + bytes - 1))
+    return false;
+  for (i=0;i<bytes;i++) {
+    if (! put_user (uaddr+i, kp[i]))
+      break; /* segfault */
+  }
+  if (i != bytes)
+    return NULL; /* segfault */
+  return uaddr;
+}
+
+/* Copy string (at most cnt bytes) from user memory to the kernel address
+   `kaddr`. The number of bytes copied is returned; 0 indicates a segfault. */
+static size_t
+strncpy_from_user (void *kaddr, void *uaddr, size_t cnt)
+{  
+  uint8_t *kp = (uint8_t*) kaddr;
+  size_t i; 
+  int c = 1;
+  for (i = 0; i < cnt && c; i++) {
+    if (! is_user_vaddr (uaddr+i))
+      return 0; /* sefault */
+    c = get_user (uaddr+i);
+    if (c < 0)
+      return 0; /* segfault */
+    kp[i] = c;
+  }
+  return i;
+}
+
+/* Copy a value of scalar type `typeof(*kdst)` from user space pointer 
+  `usrc` to kernel space variable pointed to by `kdst`. Returns
+  false on segfault, and true otherwise. */
+#define copy_from_user(kdst, usrc) \
+    (memcpy_from_user (kdst, usrc, sizeof (*kdst)) != NULL)
+
+/* Takes user space stack pointer, which points to a string
+   in user space. Copies that string (at most PGSIZE bytes)
+   to a freshly allocated buffer in kernel space. Reurns NULL on
+   error; on a segfault, additionally sets `segfault` to true */
+static void*
+copy_string_arg (void *usp, bool *segfault)
+{
+  size_t bytes_copied;
+  char *uptr;
+  char *kpage;
+  if (! copy_from_user (&uptr, usp)) {
+    *segfault = true;
+    return NULL;
+  }
+  kpage = palloc_get_page (PAL_ZERO);
+  if (kpage == NULL)
+    return NULL;
+  bytes_copied = strncpy_from_user (kpage, uptr, PGSIZE);
+  if (bytes_copied == 0) {
+    *segfault = true;
+    palloc_free_page (kpage);
+    return NULL;
+  }
+  if (kpage[bytes_copied-1] != '\0') {
+    palloc_free_page (kpage);
+    return NULL;
+  };
+  return kpage;
+}
+
+/* free buffer allocated by `copy_string_arg` */
+static void free_string_arg_buf (void *kbuf)
+{
+  palloc_free_page (kbuf);
+}
+
+/* Stack slot address */
+#define STACK_ADDR(sp, slot) (sp + STACK_SLOT_SIZE*slot)
+
+/* syscall handler prototype */
+static void syscall_handler (struct intr_frame *);
+
+typedef int (handler)(void *sp, bool *segfault);
+
+/* Prototypes for syscall handlers */
+static handler
+  syscall_halt, 
+  syscall_exit,
+  syscall_write,
+  syscall_wait ,
+  syscall_exec,
+  syscall_create,
+  syscall_remove,
+  syscall_open,
+  syscall_filesize,
+  syscall_read,
+  syscall_seek,
+  syscall_tell,
+  syscall_close;
+
+/* Register syscall_handler for interrupt 0x30 */
+void
+syscall_init (void)
+{
+  intr_register_int (0x30, 3, INTR_ON, syscall_handler, "syscall");
+}
+
+/* Syscall handler, delegating known syscalls to the respective implementations */
+static void
+syscall_handler (struct intr_frame *f)
+{
+  int syscall_nr;
+  handler* fp;
+  bool segfault = false;
+  int result;
+  void *sp = f->esp;
+
+  /* The system call number and the arguments are on the stack */
+  if (! copy_from_user (&syscall_nr,sp))
+    goto fail;
+  switch (syscall_nr) {
+  case SYS_HALT: fp = syscall_halt; break;
+  case SYS_EXIT: fp = syscall_exit; break;
+  case SYS_EXEC: fp = syscall_exec; break;
+  case SYS_WAIT: fp = syscall_wait; break;
+  case SYS_CREATE: fp = syscall_create; break;
+  case SYS_REMOVE: fp = syscall_remove; break;
+  case SYS_OPEN: fp = syscall_open; break;
+  case SYS_FILESIZE: fp = syscall_filesize; break;
+  case SYS_READ: fp = syscall_read; break;
+  case SYS_WRITE: fp = syscall_write; break;
+  case SYS_SEEK: fp = syscall_seek; break;
+  case SYS_TELL: fp = syscall_tell; break;
+  case SYS_CLOSE: fp = syscall_close; break;
+  default:
+    goto fail;
+  }
+  result = fp (sp, &segfault);
+  if (segfault)
+    goto fail;
+  f->eax = result;
+  return;
+
+  fail:
+  process_current()->exit_status = -1;
+  thread_exit ();
+}
+
+/* Shutdown machine */
+static int
+syscall_halt (void *sp UNUSED, bool *segfault UNUSED)
+{
+  shutdown ();
+  NOT_REACHED ();
+}
+
+/* Exit current process with given exit code */
+static int
+syscall_exit (void *sp, bool *segfault)
+{
+  int exit_status;
+  if (! copy_from_user (&exit_status, STACK_ADDR (sp,1))) {
+    *segfault = true;
+    return -1;
+  }
+  process_current()->exit_status = exit_status;
+  thread_exit ();
+  NOT_REACHED ();
+}
+
+/* Spawn new process executing the supplied command */
+static int
+syscall_exec (void *sp, bool *segfault)
+{
+  char *kbuf;
+  int result = TID_ERROR;
+  if ((kbuf = copy_string_arg (STACK_ADDR (sp, 1), segfault)) != NULL) {
+    result = process_execute (kbuf);
+    free_string_arg_buf (kbuf);
+  }
+  return result;
+}
+
+/* Wait until specified process exits */
+static int
+syscall_wait (void *sp, bool *segfault)
+{
+  tid_t arg;
+  if (! copy_from_user (&arg, STACK_ADDR (sp,1))) {
+    *segfault = true;
+    return 0;
+  }
+  return process_wait (arg);
+}
+
+/* Create a new file with given initial size */
+static int
+syscall_create (void *sp, bool *segfault)
+{
+  bool success = false;
+  char *fname;
+  int initial_size;
+
+  if (! copy_from_user (&initial_size, STACK_ADDR (sp,2))) {
+    *segfault = true;
+    return false;
+  }
+  if ((fname = copy_string_arg (STACK_ADDR (sp, 1), segfault)) == NULL)
+    return false;
+
+  process_lock_filesys ();
+  success = filesys_create (fname, initial_size);
+  process_unlock_filesys ();
+  free_string_arg_buf (fname);
+  return success;
+}
+
+/* Remove name file, returns true if successful */
+static int
+syscall_remove (void *sp, bool *segfault)
+{
+  bool success;
+  char *fname;
+
+  if ((fname = copy_string_arg (STACK_ADDR (sp, 1), segfault)) == NULL)
+    return false;  
+  process_lock_filesys ();
+  success = filesys_remove (fname);
+  process_unlock_filesys ();
+  free_string_arg_buf (fname);
+  return (int)success;
+}
+
+/* Open file, returning non-negative file descriptor if successful */
+static int
+syscall_open (void *sp, bool *segfault)
+{
+  char *fname;
+  int fd;
+  if ((fname = copy_string_arg (STACK_ADDR (sp, 1), segfault)) == NULL)
+    return false;  
+  fd = process_open_file (fname);
+  free_string_arg_buf (fname);
+  return fd;
+}
+
+/* Return size of file described by file descriptor */
+static int
+syscall_filesize (void *sp, bool *segfault)
+{
+  int fd;
+  struct file *f;
+  int size;
+
+  if (! copy_from_user (&fd, STACK_ADDR (sp,1))) {
+    *segfault = true;
+    return -1;
+  }
+  if ((f = process_get_file (fd)) == NULL)
+    return -1;
+  process_lock_filesys ();
+  size = inode_length (file_get_inode (f));
+  process_unlock_filesys ();
+  return size;
+}
+
+/* Read bytes from the file referenced by the given file
+   descriptor into the supplied user space buffer, returning
+   number of bytes read. */
+static int
+syscall_read (void *sp, bool *segfault)
+{
+  int fd;
+  uint8_t *user_buffer;
+  size_t size, bytes_to_read;
+
+  /* get arguments */
+  if (! copy_from_user (&fd, STACK_ADDR (sp,1)) ||
+      ! copy_from_user (&user_buffer, STACK_ADDR (sp, 2)) ||
+      ! copy_from_user (&size, STACK_ADDR (sp,3))) {
+    *segfault = true;
+    return -1;
+  }
+
+  /* ensure buffer is in user space */
+  if (! is_user_vaddr (user_buffer) ||
+      ! is_user_vaddr (user_buffer + size - 1)) {
+    *segfault = true;
+    return -1;
+  }
+
+  bytes_to_read = size;
+  /* handle stdin */
+  if (fd == STDIN_FILENO) {
+    char c;
+    while (bytes_to_read--) {
+      c = input_getc ();
+      if (! put_user (user_buffer++, c)) {
+        *segfault = true;
+        return -1;
+      }
+    }
+    return size;
+  }
+  /* get file */
+  struct file *file = process_get_file (fd);
+  if (file == NULL)
+    return -1;
+
+  char *kbuf = palloc_get_page (0);
+  if (kbuf == NULL)
+    return -1;
+
+  /* read loop */
+  do {
+    int bytes_read;
+    int blocksize = bytes_to_read;
+    if (bytes_to_read > PGSIZE)
+      blocksize = PGSIZE;
+
+    /* read bytes */
+    process_lock_filesys ();
+    bytes_read = file_read (file, kbuf, blocksize);
+    process_unlock_filesys ();
+
+    /* Stop when EOF has been reached */
+    if (bytes_read == 0)
+      break;
+    bytes_to_read -= bytes_read;
+    if (! memcpy_to_user (user_buffer, kbuf, bytes_read)) {
+      *segfault = true;
+      break;
+    }
+    user_buffer += bytes_read;
+  } while (bytes_to_read > 0);
+
+  palloc_free_page (kbuf);
+  return size - bytes_to_read;
+}
+
+/* Write bytes from user buffer into the specified
+   file, returning number of bytes written. */
+static int
+syscall_write (void *sp, bool *segfault)
+{
+  int fd;
+  size_t size, bytes_to_write;
+  char *user_buffer;
+
+  /* get arguments */
+  if (! copy_from_user (&fd, STACK_ADDR (sp,1)) ||
+      ! copy_from_user (&user_buffer, STACK_ADDR (sp, 2)) ||
+      ! copy_from_user (&size, STACK_ADDR (sp,3))) {
+    *segfault = true;
+    return -1;
+  }
+
+  /* ensure buffer is in user space */
+  if (! is_user_vaddr (user_buffer) ||
+      ! is_user_vaddr (user_buffer + size - 1)) {
+    *segfault = true;
+    return -1;
+  }
+
+  /* get file handle */
+  struct file *file = NULL;
+  if (fd != STDOUT_FILENO) {
+    file = process_get_file (fd);
+    if (file == NULL)
+      return -1;
+  }
+
+  /* allocate kernel buffer */
+  char *kbuf = palloc_get_page (0);
+  if (kbuf == NULL)
+    return -1;
+
+  /* write loop */
+  bytes_to_write = size;
+  do {
+    int blocksize = bytes_to_write;
+    if (bytes_to_write > PGSIZE)
+      blocksize = PGSIZE;
+    if (memcpy_from_user (kbuf, user_buffer, blocksize) == NULL) {
+      *segfault = true;
+      break;
+    }
+    if (fd == STDOUT_FILENO) {
+      putbuf (kbuf, blocksize);
+      bytes_to_write -= blocksize;
+    } else {
+      int bytes_written = 0;
+      int bytes_left_filesys = blocksize;
+
+      process_lock_filesys ();
+      while (bytes_left_filesys > 0) {
+        bytes_written = file_write (file, kbuf, bytes_left_filesys);
+        if (bytes_written <= 0) {
+          break;
+        }
+        bytes_left_filesys -= bytes_written;
+      }
+      process_unlock_filesys ();
+
+      if (bytes_written <= 0)
+        break;
+      bytes_to_write -= blocksize;
+    }
+    user_buffer += blocksize;
+  } while (bytes_to_write > 0);
+
+  /* return bytes written */
+  palloc_free_page (kbuf);
+  return size - bytes_to_write;
+}
+
+/* Change the position where the next byte will be read or written */
+static int
+syscall_seek (void *sp, bool *segfault)
+{
+  int fd;
+  off_t new_pos;
+
+  /* get arguments */
+  if (! copy_from_user (&fd, STACK_ADDR (sp,1)) ||
+      ! copy_from_user (&new_pos, STACK_ADDR (sp, 2))) {
+    *segfault = true;
+    return 0;
+  }
+
+  /* no way to return something sensible (void function) */
+  struct file *file = process_get_file (fd);
+  if (file == NULL)
+    return 0;
+
+  process_lock_filesys ();
+  file_seek (file, new_pos);
+  process_unlock_filesys ();
+  return 0;
+}
+
+/* Returns the position of the next byte to be read or written */
+static int
+syscall_tell (void *sp, bool *segfault)
+{
+  int fd;
+  unsigned r = 0;
+
+  /* get arguments */
+  if (! copy_from_user (&fd, STACK_ADDR (sp,1))) {
+    *segfault = true;
+    return 0;
+  }
+
+  /* no way to return something sensible function */
+  struct file *file = process_get_file (fd);
+  if (file == NULL)
+    return 0;
+
+  process_lock_filesys ();
+  r = file_tell (file);
+  process_unlock_filesys ();
+  return r;
+}
+
+/* Close the given file */
+static int
+syscall_close (void *sp, bool *segfault)
+{
+  int fd;
+
+  /* get arguments */
+  if (! copy_from_user (&fd, STACK_ADDR (sp,1))) {
+    *segfault = true;
+    return 0;
+  }
+
+  /* no way to return something sensible function (void) */
+  (void) process_close_file (fd);
+  return 0;
+}
diff --git a/userprog/syscall.h b/userprog/syscall.h
new file mode 100644
index 0000000..f7ab2f3
--- /dev/null
+++ b/userprog/syscall.h
@@ -0,0 +1,5 @@
+#ifndef USERPROG_SYSCALL_H
+#define USERPROG_SYSCALL_H
+
+void syscall_init (void);
+#endif /* userprog/syscall.h */
diff --git a/userprog/tss.c b/userprog/tss.c
new file mode 100644
index 0000000..f8ed9a9
--- /dev/null
+++ b/userprog/tss.c
@@ -0,0 +1,106 @@
+#include "userprog/tss.h"
+#include <debug.h>
+#include <stddef.h>
+#include "userprog/gdt.h"
+#include "threads/thread.h"
+#include "threads/palloc.h"
+#include "threads/vaddr.h"
+
+/* The Task-State Segment (TSS).
+
+   Instances of the TSS, an x86-specific structure, are used to
+   define "tasks", a form of support for multitasking built right
+   into the processor.  However, for various reasons including
+   portability, speed, and flexibility, most x86 OSes almost
+   completely ignore the TSS.  We are no exception.
+
+   Unfortunately, there is one thing that can only be done using
+   a TSS: stack switching for interrupts that occur in user mode.
+   When an interrupt occurs in user mode (ring 3), the processor
+   consults the ss0 and esp0 members of the current TSS to
+   determine the stack to use for handling the interrupt.  Thus,
+   we must create a TSS and initialize at least these fields, and
+   this is precisely what this file does.
+
+   When an interrupt is handled by an interrupt or trap gate
+   (which applies to all interrupts we handle), an x86 processor
+   works like this:
+
+     - If the code interrupted by the interrupt is in the same
+       ring as the interrupt handler, then no stack switch takes
+       place.  This is the case for interrupts that happen when
+       we're running in the kernel.  The contents of the TSS are
+       irrelevant for this case.
+
+     - If the interrupted code is in a different ring from the
+       handler, then the processor switches to the stack
+       specified in the TSS for the new ring.  This is the case
+       for interrupts that happen when we're in user space.  It's
+       important that we switch to a stack that's not already in
+       use, to avoid corruption.  Because we're running in user
+       space, we know that the current process's kernel stack is
+       not in use, so we can always use that.  Thus, when the
+       scheduler switches threads, it also changes the TSS's
+       stack pointer to point to the new thread's kernel stack.
+       (The call is in thread_schedule_tail() in thread.c.)
+
+   See [IA32-v3a] 6.2.1 "Task-State Segment (TSS)" for a
+   description of the TSS.  See [IA32-v3a] 5.12.1 "Exception- or
+   Interrupt-Handler Procedures" for a description of when and
+   how stack switching occurs during an interrupt. */
+struct tss
+  {
+    uint16_t back_link, :16;
+    void *esp0;                         /* Ring 0 stack virtual address. */
+    uint16_t ss0, :16;                  /* Ring 0 stack segment selector. */
+    void *esp1;
+    uint16_t ss1, :16;
+    void *esp2;
+    uint16_t ss2, :16;
+    uint32_t cr3;
+    void (*eip) (void);
+    uint32_t eflags;
+    uint32_t eax, ecx, edx, ebx;
+    uint32_t esp, ebp, esi, edi;
+    uint16_t es, :16;
+    uint16_t cs, :16;
+    uint16_t ss, :16;
+    uint16_t ds, :16;
+    uint16_t fs, :16;
+    uint16_t gs, :16;
+    uint16_t ldt, :16;
+    uint16_t trace, bitmap;
+  };
+
+/* Kernel TSS. */
+static struct tss *tss;
+
+/* Initializes the kernel TSS. */
+void
+tss_init (void) 
+{
+  /* Our TSS is never used in a call gate or task gate, so only a
+     few fields of it are ever referenced, and those are the only
+     ones we initialize. */
+  tss = palloc_get_page (PAL_ASSERT | PAL_ZERO);
+  tss->ss0 = SEL_KDSEG;
+  tss->bitmap = 0xdfff;
+  tss_update ();
+}
+
+/* Returns the kernel TSS. */
+struct tss *
+tss_get (void) 
+{
+  ASSERT (tss != NULL);
+  return tss;
+}
+
+/* Sets the ring 0 stack pointer in the TSS to point to the end
+   of the thread stack. */
+void
+tss_update (void) 
+{
+  ASSERT (tss != NULL);
+  tss->esp0 = (uint8_t *) thread_current () + PGSIZE;
+}
diff --git a/userprog/tss.h b/userprog/tss.h
new file mode 100644
index 0000000..467bd19
--- /dev/null
+++ b/userprog/tss.h
@@ -0,0 +1,11 @@
+#ifndef USERPROG_TSS_H
+#define USERPROG_TSS_H
+
+#include <stdint.h>
+
+struct tss;
+void tss_init (void);
+struct tss *tss_get (void);
+void tss_update (void);
+
+#endif /* userprog/tss.h */