add dynamic stack growing

9 files changed, 300 insertions, 98 deletions

diff --git a/proj2.txt b/proj2.txt
new file mode 100644
index 0000000..5405336
--- /dev/null
+++ b/proj2.txt
@@ -0,0 +1,137 @@
+                +---------------------------+
+                |         ProgOS            |
+                | PROJECT 2: VIRTUAL MEMORY |
+                |         DESIGN DOCUMENT   |
+                +---------------------------+
+
+---- GROUP ----
+
+>> Fill in the names and email addresses of your group members.
+
+Peter Ketscher <e9651415@mail.student.tuwien.ac.at>
+Karoline Knoth <e0326266@student.tuwien.ac.at>
+Manuel Mausz <manuel-uni@mausz.at>
+
+---- PRELIMINARIES ----
+
+>> If you have any preliminary comments on your submission, notes for the
+>> TAs, or extra credit, please give them here.
+
+>> Please cite any offline or online sources you consulted while
+>> preparing your submission, other than the Pintos documentation, course
+>> text, lecture notes, and course staff.
+
+                  PAGE TABLE MANAGEMENT
+                  =====================
+---- DATA STRUCTURES ----
+
+>> A1: Copy here the declaration of each new or changed `struct' or
+>> `struct' member, global or static variable, `typedef', or
+>> enumeration.  Identify the purpose of each in 25 words or less.
+
+struct thread:
+  struct hash page_table ...page table of thread
+
+struct page_table_entry:
+  void *upage             ...virtual address of page
+  bool loaded             ...indicates if page is loaded
+  enum type               ...type of page
+  union struct segment    ...structure needed for lazy loading of data segments
+  struct hash_elem elem   ...Hash element.
+
+---- IMPLEMENTATION ----
+>> A2: Describe how you implemented lazy page loading. How do you
+>> determine the file and file offset corresponding to a virtual
+>> address?
+
+TODO
+
+---- SYNCHRONIZATION ----
+>> A3: How do you deal with or prevent page faults in file system
+>> routines. Argue why your solution is deadlock free.
+
+TODO
+
+                      STACK GROWTH
+                      ============
+
+---- DATA STRUCTURES ----
+
+>> B1: Copy here the declaration of each new or changed `struct' or
+>> `struct' member, global or static variable, `typedef', or
+>> enumeration.  Identify the purpose of each in 25 words or less.
+
+extern void *syscall_sp   ...stored stack pointer for the "page fault inside
+                             syscall/kernel"-case
+
+---- IMPLEMENTATION ----
+>> B2: Describe how you integrated the (potentially growing) stack segment
+>> into your page table management implementation.
+
+TODO
+
+---- ALGORITHMS ----
+>> B3: Explain how you detect a page fault which should trigger a
+>> stack growth. What asssumptions are needed for your implementation
+>> to work?
+
+TODO
+
+                   MEMORY MAPPED FILES
+                   ===================
+
+---- DATA STRUCTURES ----
+
+>> C1: Copy here the declaration of each new or changed `struct' or
+>> `struct' member, global or static variable, `typedef', or
+>> enumeration.  Identify the purpose of each in 25 words or less.
+
+struct page_table_entry:
+  union struct TODO       ...structure needed for loading of memory mapped files
+
+---- ALGORITHMS ----
+
+>> C2: Describe how memory mapped files integrate into your virtual
+>> memory subsystem.
+
+TODO
+
+>> C3: Explain how you determine whether a new file mapping overlaps
+>> any existing segment.
+
+TODO
+
+---- RATIONALE ----
+
+>> C4: Mappings created with "mmap" have similar semantics to those of
+>> data demand-paged from executables, except that "mmap" mappings are
+>> written back to their original files, not to swap.  This implies
+>> that much of their implementation can be shared.  Explain why your
+>> implementation either does or does not share much of the code for
+>> the two situations.
+
+TODO
+
+                     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
+want--these questions are just to spur your thoughts.  You may also
+choose to respond anonymously in the course evaluations at the end of
+the quarter.
+
+>> In your opinion, was this assignment, or any one of the three problems
+>> in it, too easy or too hard?  Did it take too long or too little time?
+
+>> Did you find that working on a particular part of the assignment gave
+>> you greater insight into some aspect of OS design?
+
+>> Is there some particular fact or hint we should give students in
+>> future quarters to help them solve the problems?  Conversely, did you
+>> find any of our guidance to be misleading?
+
+>> Do you have any suggestions for the TAs to more effectively assist
+>> students, either for future quarters or the remaining projects?
+
+>> Any other comments?
diff --git a/threads/thread.h b/threads/thread.h
index 293d14f..ed591f4 100644
--- a/threads/thread.h
+++ b/threads/thread.h
@@ -114,7 +114,7 @@ struct thread
     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;
+    struct hash page_table;             /* page table of thread */
   };
 
 /* If false (default), use round-robin scheduler.
diff --git a/userprog/exception.c b/userprog/exception.c
index 54621fa..debe7f0 100644
--- a/userprog/exception.c
+++ b/userprog/exception.c
@@ -2,6 +2,8 @@
 #include <inttypes.h>
 #include <stdio.h>
 #include "userprog/gdt.h"
+#include "userprog/process.h"
+#include "userprog/syscall.h"
 #include "threads/interrupt.h"
 #include "threads/thread.h"
 #include "threads/vaddr.h"
@@ -128,7 +130,8 @@ page_fault (struct intr_frame *f)
   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;
+  void *sp;          /* Stack pointer. */
+  struct page_table_entry *pte; /* Page table entry. */
 
   /* Obtain faulting address, the virtual address that was
      accessed to cause the fault.  It may point to code or to
@@ -151,38 +154,57 @@ page_fault (struct intr_frame *f)
   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)) {
-    pte = page_table_fetch (&thread_current ()->page_table, pg_round_down (fault_addr));
-    if (pte != NULL)
-      page_load (pte);
-    else
+  /* accessing r/o page is always wrong */
+  if (!not_present)
+    thread_exit ();
+
+  if (is_user_vaddr (fault_addr))
     {
-      printf ("Page fault %p\n", pte);
-      kill (f);
-    }
+      /* if page fault occurs during syscall, use saved stack pointer */
+      sp = (!user) ? syscall_sp : f->esp;
+
+      /* try to fetch page entry */
+      pte = page_table_fetch (&thread_current ()->page_table,
+          pg_round_down (fault_addr));
+
+      /* we got a page entry so try to load the page */
+      if (pte != NULL)
+        {
+          if (page_load (pte))
+            return;
+          printf ("Unable to load page at %p in %s context.\n",
+            fault_addr, user ? "user" : "kernel");
+        }
+      /* there's no page in our page table but we might still have an valid
+         stack access and need to expand our stack. so just check for that.
+         the maxium offset we consider as a valid access is caused by the PUSHA
+         instruction. it's 32 bytes below the current stack pointer */
+      else if (fault_addr >= (sp - 32) && (PHYS_BASE - fault_addr) <= STACK_SIZE)
+        {
+          if (process_grow_stack (pg_round_down (fault_addr)))
+            return;
+          printf ("Unable to grow stack %p in %s context.\n",
+            fault_addr, user ? "user" : "kernel");
+        }
 
-    //TODO
-#if 0
-    if (! user) {
       /* syscall exception; set eax and eip */
-      f->eip = (void*)f->eax;
-      f->eax = 0xFFFFFFFF;
-      return;
-    } else {
+      if (!user)
+        {
+          f->eip = (void*)f->eax;
+          f->eax = 0xFFFFFFFF;
+          return;
+        }
+
       /* user process access violation */
-      thread_exit();
+      thread_exit ();
+      return;
     }
-#endif
-  } 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);
-  }
+
+  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/process.c b/userprog/process.c
index 15883d9..2771e76 100644
--- a/userprog/process.c
+++ b/userprog/process.c
@@ -552,24 +552,24 @@ load_segment (struct file *file, off_t ofs, uint8_t *upage,
 
   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;
-
-    /* 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;
-
-    /* Advance. */
-    read_bytes -= page_read_bytes;
-    zero_bytes -= page_zero_bytes;
-    ofs += page_read_bytes;
-    upage += PGSIZE;
-  }
+    {
+      /* 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;
+
+      /* 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;
+
+      /* Advance. */
+      read_bytes -= page_read_bytes;
+      zero_bytes -= page_zero_bytes;
+      ofs += page_read_bytes;
+      upage += PGSIZE;
+    }
   return true;
 }
 
@@ -686,6 +686,24 @@ setup_stack (uint32_t **esp, const char *args)
   return true;
 }
 
+/* expand the stack of the process by one new page
+   which will be installed at the address of UPAGE */
+bool
+process_grow_stack (void *upage)
+{
+  uint8_t *kpage = palloc_get_page (PAL_USER | PAL_ZERO);
+  if (kpage == NULL)
+      return false;
+
+  if (!process_install_page (upage, kpage, true))
+    {
+      palloc_free_page (kpage);
+      return false;
+    }
+
+  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;
diff --git a/userprog/process.h b/userprog/process.h
index b7bca5d..ccb94cb 100644
--- a/userprog/process.h
+++ b/userprog/process.h
@@ -3,6 +3,8 @@
 
 #include "threads/thread.h"
 
+#define STACK_SIZE (1 << 23) /* 8MB maxiumum stack size */
+
 /* In the current implementation, the capacity is fixed to 1024 (PGSIZE/4) */
 struct fd_table {
     struct file** fds;
@@ -37,6 +39,7 @@ tid_t process_execute (const char *file_name);
 int process_wait (tid_t);
 void process_exit (void);
 void process_activate (void);
+bool process_grow_stack (void *upage);
 bool process_install_page (void *upage, void *kpage, bool writable);
 
 int process_open_file(const char* fname);
diff --git a/userprog/syscall.c b/userprog/syscall.c
index f8e0197..541668d 100644
--- a/userprog/syscall.c
+++ b/userprog/syscall.c
@@ -17,6 +17,9 @@
 
 #define STACK_SLOT_SIZE sizeof(int)
 
+/* stored stack pointer for the "page fault inside syscall/kernel"-case */
+void *syscall_sp;
+
 /* Prototypes for Utilities */
 static int get_user (const uint8_t *uaddr);
 static bool put_user (uint8_t *udst, uint8_t byte);
@@ -195,10 +198,10 @@ syscall_handler (struct intr_frame *f)
   handler* fp;
   bool segfault = false;
   int result;
-  void *sp = f->esp;
+  syscall_sp = f->esp;
 
   /* The system call number and the arguments are on the stack */
-  if (! copy_from_user (&syscall_nr,sp))
+  if (! copy_from_user (&syscall_nr,syscall_sp))
     goto fail;
   switch (syscall_nr) {
   case SYS_HALT: fp = syscall_halt; break;
@@ -217,7 +220,7 @@ syscall_handler (struct intr_frame *f)
   default:
     goto fail;
   }
-  result = fp (sp, &segfault);
+  result = fp (syscall_sp, &segfault);
   if (segfault)
     goto fail;
   f->eax = result;
diff --git a/userprog/syscall.h b/userprog/syscall.h
index f7ab2f3..987ceaa 100644
--- a/userprog/syscall.h
+++ b/userprog/syscall.h
@@ -2,4 +2,6 @@
 #define USERPROG_SYSCALL_H
 
 void syscall_init (void);
+extern void *syscall_sp;
+
 #endif /* userprog/syscall.h */
diff --git a/vm/page.c b/vm/page.c
index fa2433d..336353e 100644
--- a/vm/page.c
+++ b/vm/page.c
@@ -6,50 +6,59 @@
 #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 void page_table_entry_free (struct hash_elem *e, 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);
 
+/* initialize page table structure */
 void
 page_table_init (struct hash *ht)
 {
   hash_init (ht, page_table_hash, page_table_cmp_less, NULL);
 }
 
-unsigned
+/* calulcates and returns the hash used as key of the hash/page table */
+static 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);
+  return hash_bytes (&pte->upage, sizeof pte->upage);
 }
 
-bool
+/* page table comperator needed by the hash table implementation
+   returns true if A is less than B, or false if A is greater than
+   or equal to B */
+static 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);
+  return (pte1->upage < pte2->upage);
 }
 
+/* frees the content of page table */
 void
 page_table_free (struct hash *ht)
 {
   hash_destroy (ht, page_table_entry_free);
 }
 
-void
+/* frees a single page table entry */
+static 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
+/* inserts a new entry into the page table
+   returns false if entry is invalid or already in the table */
+static bool
 page_table_insert (struct hash *ht, struct page_table_entry *pte)
 {
   if (pte == NULL)
@@ -57,6 +66,8 @@ page_table_insert (struct hash *ht, struct page_table_entry *pte)
   return (hash_insert (ht, &pte->elem) == NULL);
 }
 
+/* inserts a new entry of type segment into the page table
+   returns false if entry is invalid or already in the table */
 bool
 page_table_insert_segment (struct file *file, off_t ofs, uint8_t *upage,
     uint32_t read_bytes, uint32_t zero_bytes, bool writable)
@@ -65,7 +76,7 @@ page_table_insert_segment (struct file *file, off_t ofs, uint8_t *upage,
   if (pte == NULL)
     return false;
 
-  pte->uvaddr = upage;
+  pte->upage  = upage;
   pte->type   = PAGE_SEGMENT;
   pte->loaded = false;
   pte->segment.file       = file;
@@ -77,17 +88,20 @@ page_table_insert_segment (struct file *file, off_t ofs, uint8_t *upage,
   return page_table_insert (&thread_current ()->page_table, pte);
 }
 
+/* fetch an entry from the page table. returns NULL if not found */
 struct page_table_entry *
-page_table_fetch (struct hash *ht, void *uvaddr)
+page_table_fetch (struct hash *ht, void *upage)
 {
   struct page_table_entry pte;
   struct hash_elem *e;
 
-  pte.uvaddr = uvaddr;
+  pte.upage = upage;
   e = hash_find (ht, &pte.elem);
   return ((e != NULL) ? hash_entry (e, struct page_table_entry, elem) : NULL);
 }
 
+/* load the page referenced by the page table entry
+   returns true on success or already loaded, false otherwise */
 bool
 page_load (struct page_table_entry *pte)
 {
@@ -95,19 +109,20 @@ page_load (struct page_table_entry *pte)
     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;
-  }
+    {
+      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
+/* load the segment data page */
+static bool
 page_load_segment (struct page_table_entry *pte)
 {
   struct segment *data = &pte->segment;
@@ -122,24 +137,25 @@ page_load_segment (struct page_table_entry *pte)
   /* Load this page. */
   if (file_read (data->file, kpage, data->read_bytes)
       != (int) data->read_bytes)
-  {
-    palloc_free_page (kpage);
-    return false;
-  }
+    {
+      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;
-  }
+  if (!process_install_page (pte->upage, kpage, data->writable))
+    {
+      palloc_free_page (kpage);
+      return false;
+    }
 
   pte->loaded = true;
   return true;
 }
 
-bool
+/* load the memory mappged file page */
+static bool
 page_load_mmf (struct page_table_entry *pte)
 {
   //TODO: implement
diff --git a/vm/page.h b/vm/page.h
index 29159fb..9cea048 100644
--- a/vm/page.h
+++ b/vm/page.h
@@ -8,32 +8,33 @@
 /* supplemental page table entry */
 struct page_table_entry
 {
-  void *uvaddr;
-  bool loaded;
+  void *upage;            /* virtual address of page */
+  bool loaded;            /* indicates if page is loaded */
   enum
-  {
-    PAGE_SEGMENT,
-    PAGE_MEMORY_MAPPED_FILE,
-  } type;
+    {
+      PAGE_SEGMENT,
+      PAGE_MEMORY_MAPPED_FILE,
+    } type;               /* type of page */
 
   union
-  {
-    struct segment
     {
-      struct file *file;
-      off_t ofs;
-      uint32_t read_bytes;
-      uint32_t zero_bytes;
-      bool writable;
-    } segment;
-  };
+      /* structure needed for lazy loading of data segments */
+      struct segment
+        {
+          struct file *file;
+          off_t ofs;
+          uint32_t read_bytes;
+          uint32_t zero_bytes;
+          bool writable;
+        } segment;
+    };
 
-  struct hash_elem elem;
+  struct hash_elem elem;  /* Hash element. */
 };
 
 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);
+struct page_table_entry *page_table_fetch (struct hash *ht, void *upage);
 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);