implement page table and use it for lazy loading of segments

11 files changed, 239 insertions, 46 deletions

diff --git a/Makefile.build b/Makefile.build
index e997d27..e68e721 100644
--- a/Makefile.build
+++ b/Makefile.build
@@ -62,7 +62,7 @@ userprog_SRC += userprog/gdt.c		# GDT initialization.
 userprog_SRC += userprog/tss.c          # TSS management.
 
 # No virtual memory code yet.
-#vm_SRC = vm/file.c                     # Some file.
+vm_SRC = vm/page.c
 
 # Filesystem code.
 filesys_SRC  = filesys/filesys.c        # Filesystem core.
diff --git a/proj0.txt b/proj0.txt
index 24ea011..59a0d3c 100644
--- a/proj0.txt
+++ b/proj0.txt
@@ -35,9 +35,8 @@ Stallings, W. - Operating Systems
 struct thread:
 int64_t wakeup_tick  ...absolute tick when to wake up the thread
 
-
 timer.c:
-static struct list wakeup_list  ...list of processes waiting for an 
+static struct list wakeup_list      ...list of processes waiting for an
 wakeup event and currently put to sleep
 
 ---- ALGORITHMS ----
@@ -62,7 +61,7 @@ Thus we can return as soon as the first thread doesn't need to get unblocked.
 >> A4: How are race conditions avoided when multiple threads call
 >> timer_sleep() simultaneously?
 
-Each thread has its own variable for saving its sleep period 
+Each thread has its own variable for saving its sleep period
 therefore no race conditions arise while setting the latter. Furthermore
 during the access to the static wakup_list, interrupts are disabled to prevent
 thread preemption.
@@ -131,12 +130,11 @@ strtok() uses global data, so it is unsafe in threaded programs such as kernels.
   execution with user privileges. Otherwise this could lead to a kernel oops
   or even worse code execution within the kernel.
 
-* Outsourcing command separation from the kernel leads to a leaner 
+* Outsourcing command separation from the kernel leads to a leaner
   less complex kernel implementation and reduces the kernel workload
-  because tasks like searching for a command name in file system 
+  because tasks like searching for a command name in file system
   can be delegated to the shell.
 
-
                            SURVEY QUESTIONS
                            ================
 
@@ -161,4 +159,4 @@ the quarter.
 
 >> Any other comments?
 
-It took us about 25 hours to complete this assignment.
\ No newline at end of file
+It took us about 25 hours to complete this assignment.
diff --git a/proj1.txt b/proj1.txt
index 03c61f0..2eab2fa 100644
--- a/proj1.txt
+++ b/proj1.txt
@@ -1,8 +1,8 @@
-                        +--------------------+
-                        |        CS 140      |
-                        | PROJECT 1: THREADS |
-                        |   DESIGN DOCUMENT  |
-                        +--------------------+
+                  +--------------------+
+                  |        CS 140      |
+                  | PROJECT 1: THREADS |
+                  |   DESIGN DOCUMENT  |
+                  +--------------------+
 
 ---- GROUP ----
 
@@ -25,8 +25,8 @@ Stallings, W. - Operating Systems
 http://en.wikipedia.org/wiki/Priority_inversion
 http://hynek.me/studies/sched_ausarbeitung.pdf
 
-                         PRIORITY SCHEDULING
-                         ===================
+                   PRIORITY SCHEDULING
+                   ===================
 
 ---- DATA STRUCTURES ----
 
@@ -214,8 +214,8 @@ and we don't have any reference to currently used semaphores/conditions inside
 the thread structure. Thus we simply sort the whole list inside sema_up()/
 cond_signal() before unblocking the next thread.
 
-                           SURVEY QUESTIONS
-                           ================
+                     SURVEY QUESTIONS
+                     ================
 
 Answering these questions is optional, but it will help us improve the
 course in future quarters.  Feel free to tell us anything you
diff --git a/threads/synch.c b/threads/synch.c
index a1b7549..a520f61 100644
--- a/threads/synch.c
+++ b/threads/synch.c
@@ -32,9 +32,9 @@
 #include "threads/interrupt.h"
 #include "threads/thread.h"
 
-static bool lock_priority_cmp_greater(const struct list_elem *a, const struct list_elem *b,
+static bool lock_priority_cmp_greater (const struct list_elem *a, const struct list_elem *b,
     void *AUX UNUSED);
-static bool semaphore_priority_cmp_greater(const struct list_elem *a, const struct list_elem *b,
+static bool semaphore_priority_cmp_greater (const struct list_elem *a, const struct list_elem *b,
     void *aux UNUSED);
 
 /* Initializes semaphore SEMA to VALUE.  A semaphore is a
@@ -202,7 +202,7 @@ lock_init (struct lock *lock)
 
 /* comparison function for our descending ordered lock list. */
 static bool
-lock_priority_cmp_greater(const struct list_elem *a, const struct list_elem *b,
+lock_priority_cmp_greater (const struct list_elem *a, const struct list_elem *b,
     void *AUX UNUSED)
 {
   const struct lock *l1 = list_entry (a, struct lock, elem);
@@ -355,7 +355,7 @@ cond_init (struct condition *cond)
 
 /* comparison function for our descending ordered condition waiters list. */
 static bool
-semaphore_priority_cmp_greater(const struct list_elem *a, const struct list_elem *b,
+semaphore_priority_cmp_greater (const struct list_elem *a, const struct list_elem *b,
     void *aux UNUSED)
 {
   const struct semaphore_elem *s1 = list_entry (a, struct semaphore_elem, elem);
diff --git a/threads/thread.c b/threads/thread.c
index cf404b6..14889ca 100644
--- a/threads/thread.c
+++ b/threads/thread.c
@@ -73,7 +73,7 @@ static tid_t allocate_tid (void);
 
 /* comparison function for our descending ordered ready list. */
 bool
-thread_priority_cmp_greater(const struct list_elem *a, const struct list_elem *b,
+thread_priority_cmp_greater (const struct list_elem *a, const struct list_elem *b,
   void *AUX UNUSED)
 {
   const struct thread *t1 = list_entry (a, struct thread, elem);
diff --git a/threads/thread.h b/threads/thread.h
index 9125937..293d14f 100644
--- a/threads/thread.h
+++ b/threads/thread.h
@@ -3,6 +3,7 @@
 
 #include <debug.h>
 #include <list.h>
+#include <hash.h>
 #include <stdint.h>
 #include "threads/synch.h"
 
@@ -112,6 +113,8 @@ struct thread
     int saved_priority;                 /* saved base priority in case of priority dontation */
     struct list locks;                  /* list of locks the thread currently holds */
     struct lock *blocked_lock;          /* the lock the thread currently tries to acquire (but hasn't yet) */
+
+    struct hash page_table;
   };
 
 /* If false (default), use round-robin scheduler.
diff --git a/userprog/exception.c b/userprog/exception.c
index 17620ad..54621fa 100644
--- a/userprog/exception.c
+++ b/userprog/exception.c
@@ -5,6 +5,7 @@
 #include "threads/interrupt.h"
 #include "threads/thread.h"
 #include "threads/vaddr.h"
+#include "vm/page.h"
 
 /* Number of page faults processed. */
 static long long page_fault_cnt;
@@ -121,12 +122,13 @@ kill (struct intr_frame *f)
    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) 
+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. */
+  struct page_table_entry *pte;
 
   /* Obtain faulting address, the virtual address that was
      accessed to cause the fault.  It may point to code or to
@@ -153,6 +155,17 @@ page_fault (struct intr_frame *f)
      body, adding code that brings in the page to
      which fault_addr refers. */
   if (is_user_vaddr(fault_addr)) {
+    pte = page_table_fetch (&thread_current ()->page_table, pg_round_down (fault_addr));
+    if (pte != NULL)
+      page_load (pte);
+    else
+    {
+      printf ("Page fault %p\n", pte);
+      kill (f);
+    }
+
+    //TODO
+#if 0
     if (! user) {
       /* syscall exception; set eax and eip */
       f->eip = (void*)f->eax;
@@ -162,6 +175,7 @@ page_fault (struct intr_frame *f)
       /* user process access violation */
       thread_exit();
     }
+#endif
   } else {
     printf ("Page fault at %p: %s error %s page in %s context.\n",
             fault_addr,
diff --git a/userprog/process.c b/userprog/process.c
index c13c051..15883d9 100644
--- a/userprog/process.c
+++ b/userprog/process.c
@@ -18,6 +18,7 @@
 #include "threads/synch.h"
 #include "threads/thread.h"
 #include "threads/vaddr.h"
+#include "vm/page.h"
 
 /* data structure to communicate with the thread initializing a new process */
 struct start_aux_data {
@@ -128,6 +129,8 @@ start_process (void *aux)
   process->parent_tid = aux_data->parent_thread->tid;
   thread->process = process;
 
+  page_table_init (&thread->page_table);
+
   /* Initialize interrupt frame and load executable. */
   memset (&if_, 0, sizeof if_);
   if_.gs = if_.fs = if_.es = if_.ds = if_.ss = SEL_UDSEG;
@@ -251,6 +254,8 @@ process_exit (void)
     pagedir_destroy (pd);
   }
 
+  page_table_free (&thread->page_table);
+
   /* Destroy the process structure if the parent is not alive
    * any more. Atomic test and set would be sufficient here.
    */
@@ -478,8 +483,6 @@ load (const char *args, void (**eip) (void), void **esp)
 
 /* 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
@@ -556,29 +559,15 @@ load_segment (struct file *file, off_t ofs, uint8_t *upage,
     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);
+    /* add segment to page table for on demand loading */
+    if (!page_table_insert_segment (file, ofs, upage, page_read_bytes,
+          page_zero_bytes, writable))
       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;
+    ofs += page_read_bytes;
     upage += PGSIZE;
   }
   return true;
@@ -602,7 +591,7 @@ setup_stack (uint32_t **esp, const char *args)
   if (kpage == NULL)
       return false;
 
-  if (! install_page (((uint8_t *) PHYS_BASE) - PGSIZE, kpage, true)) {
+  if (! process_install_page (((uint8_t *) PHYS_BASE) - PGSIZE, kpage, true)) {
       palloc_free_page (kpage);
       return false;
   }
@@ -706,8 +695,8 @@ setup_stack (uint32_t **esp, const char *args)
    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)
+bool
+process_install_page (void *upage, void *kpage, bool writable)
 {
   struct thread *t = thread_current ();
 
diff --git a/userprog/process.h b/userprog/process.h
index 1609801..b7bca5d 100644
--- a/userprog/process.h
+++ b/userprog/process.h
@@ -37,6 +37,7 @@ tid_t process_execute (const char *file_name);
 int process_wait (tid_t);
 void process_exit (void);
 void process_activate (void);
+bool process_install_page (void *upage, void *kpage, bool writable);
 
 int process_open_file(const char* fname);
 struct file* process_get_file(int fd);
diff --git a/vm/page.c b/vm/page.c
new file mode 100644
index 0000000..fa2433d
--- /dev/null
+++ b/vm/page.c
@@ -0,0 +1,147 @@
+#include <string.h>
+#include "filesys/file.h"
+#include "userprog/process.h"
+#include "threads/thread.h"
+#include "threads/malloc.h"
+#include "threads/palloc.h"
+#include "vm/page.h"
+
+static void page_table_entry_free (struct hash_elem *e, void *aux UNUSED);
+static unsigned page_table_hash (const struct hash_elem *e, void *aux UNUSED);
+static bool page_table_cmp_less (const struct hash_elem *a, const struct hash_elem *b,
+    void *aux UNUSED);
+static bool page_table_insert (struct hash *ht, struct page_table_entry *pte);
+static bool page_load_segment (struct page_table_entry *pte);
+static bool page_load_mmf (struct page_table_entry *pte);
+
+void
+page_table_init (struct hash *ht)
+{
+  hash_init (ht, page_table_hash, page_table_cmp_less, NULL);
+}
+
+unsigned
+page_table_hash (const struct hash_elem *e, void *aux UNUSED)
+{
+  const struct page_table_entry *pte = hash_entry (e, struct page_table_entry, elem);
+  return hash_bytes (&pte->uvaddr, sizeof pte->uvaddr);
+}
+
+bool
+page_table_cmp_less (const struct hash_elem *a, const struct hash_elem *b,
+    void *aux UNUSED)
+{
+  const struct page_table_entry *pte1 = hash_entry (a, struct page_table_entry, elem);
+  const struct page_table_entry *pte2 = hash_entry (b, struct page_table_entry, elem);
+  return (pte1->uvaddr < pte2->uvaddr);
+}
+
+void
+page_table_free (struct hash *ht)
+{
+  hash_destroy (ht, page_table_entry_free);
+}
+
+void
+page_table_entry_free (struct hash_elem *e, void *aux UNUSED)
+{
+  struct page_table_entry *pte = hash_entry (e, struct page_table_entry, elem);
+  free (pte);
+}
+
+bool
+page_table_insert (struct hash *ht, struct page_table_entry *pte)
+{
+  if (pte == NULL)
+    return false;
+  return (hash_insert (ht, &pte->elem) == NULL);
+}
+
+bool
+page_table_insert_segment (struct file *file, off_t ofs, uint8_t *upage,
+    uint32_t read_bytes, uint32_t zero_bytes, bool writable)
+{
+  struct page_table_entry *pte = malloc (sizeof *pte);
+  if (pte == NULL)
+    return false;
+
+  pte->uvaddr = upage;
+  pte->type   = PAGE_SEGMENT;
+  pte->loaded = false;
+  pte->segment.file       = file;
+  pte->segment.ofs        = ofs;
+  pte->segment.read_bytes = read_bytes;
+  pte->segment.zero_bytes = zero_bytes;
+  pte->segment.writable   = writable;
+
+  return page_table_insert (&thread_current ()->page_table, pte);
+}
+
+struct page_table_entry *
+page_table_fetch (struct hash *ht, void *uvaddr)
+{
+  struct page_table_entry pte;
+  struct hash_elem *e;
+
+  pte.uvaddr = uvaddr;
+  e = hash_find (ht, &pte.elem);
+  return ((e != NULL) ? hash_entry (e, struct page_table_entry, elem) : NULL);
+}
+
+bool
+page_load (struct page_table_entry *pte)
+{
+  if (pte->loaded)
+    return true;
+
+  switch (pte->type)
+  {
+    case PAGE_SEGMENT:
+      return page_load_segment (pte);
+    case PAGE_MEMORY_MAPPED_FILE:
+      return page_load_mmf (pte);
+    default:
+      ASSERT (false);
+      break;
+  }
+  return false;
+}
+
+bool
+page_load_segment (struct page_table_entry *pte)
+{
+  struct segment *data = &pte->segment;
+
+  file_seek (data->file, data->ofs);
+
+  /* Get a page of memory. */
+  uint8_t *kpage = palloc_get_page (PAL_USER);
+  if (kpage == NULL)
+    return false;
+
+  /* Load this page. */
+  if (file_read (data->file, kpage, data->read_bytes)
+      != (int) data->read_bytes)
+  {
+    palloc_free_page (kpage);
+    return false;
+  }
+  memset (kpage + data->read_bytes, 0, data->zero_bytes);
+
+  /* Add the page to the process's address space. */
+  if (!process_install_page (pte->uvaddr, kpage, data->writable))
+  {
+    palloc_free_page (kpage);
+    return false;
+  }
+
+  pte->loaded = true;
+  return true;
+}
+
+bool
+page_load_mmf (struct page_table_entry *pte)
+{
+  //TODO: implement
+  return false;
+}
diff --git a/vm/page.h b/vm/page.h
new file mode 100644
index 0000000..29159fb
--- /dev/null
+++ b/vm/page.h
@@ -0,0 +1,41 @@
+#ifndef VM_PAGE_H
+#define VM_PAGE_H
+
+#include <debug.h>
+#include "hash.h"
+#include "filesys/off_t.h"
+
+/* supplemental page table entry */
+struct page_table_entry
+{
+  void *uvaddr;
+  bool loaded;
+  enum
+  {
+    PAGE_SEGMENT,
+    PAGE_MEMORY_MAPPED_FILE,
+  } type;
+
+  union
+  {
+    struct segment
+    {
+      struct file *file;
+      off_t ofs;
+      uint32_t read_bytes;
+      uint32_t zero_bytes;
+      bool writable;
+    } segment;
+  };
+
+  struct hash_elem elem;
+};
+
+void page_table_init (struct hash *ht);
+void page_table_free (struct hash *ht);
+struct page_table_entry *page_table_fetch (struct hash *ht, void *uvaddr);
+bool page_table_insert_segment (struct file *file, off_t ofs, uint8_t *upage,
+    uint32_t read_bytes, uint32_t zero_bytes, bool writable);
+bool page_load (struct page_table_entry *pte);
+
+#endif