fix: remove stack fault checks for page faults outside user non-present addresses

Implement helper functions for managing the supplemental page table

See merge request lab2425_autumn/pintos_22!55

.gitlab-ci.yml

@@ -37,4 +37,4 @@ test_vm:
   extends: .pintos_tests
   variables:
     DIR: vm
-    IGNORE: (tests/vm/pt-grow-stack|tests/vm/pt-grow-pusha|tests/vm/pt-big-stk-obj|tests/vm/pt-overflowstk|tests/vm/pt-write-code2|tests/vm/pt-grow-stk-sc|tests/vm/page-linear|tests/vm/page-parallel|tests/vm/page-merge-seq|tests/vm/page-merge-par|tests/vm/page-merge-stk|tests/vm/page-merge-mm|tests/vm/mmap-read|tests/vm/mmap-close|tests/vm/mmap-overlap|tests/vm/mmap-twice|tests/vm/mmap-write|tests/vm/mmap-exit|tests/vm/mmap-shuffle|tests/vm/mmap-clean|tests/vm/mmap-inherit|tests/vm/mmap-misalign|tests/vm/mmap-null|tests/vm/mmap-over-code|tests/vm/mmap-over-data|tests/vm/mmap-over-stk|tests/vm/mmap-remove)
+    IGNORE: (tests/vm/pt-overflowstk|tests/vm/page-linear|tests/vm/page-parallel|tests/vm/page-merge-seq|tests/vm/page-merge-par|tests/vm/page-merge-stk|tests/vm/page-merge-mm|tests/vm/mmap-read|tests/vm/mmap-close|tests/vm/mmap-overlap|tests/vm/mmap-twice|tests/vm/mmap-write|tests/vm/mmap-exit|tests/vm/mmap-shuffle|tests/vm/mmap-clean|tests/vm/mmap-inherit|tests/vm/mmap-misalign|tests/vm/mmap-null|tests/vm/mmap-over-code|tests/vm/mmap-over-data|tests/vm/mmap-over-stk|tests/vm/mmap-remove)

src/Makefile.build

@@ -65,6 +65,7 @@ userprog_SRC += userprog/tss.c		# TSS management.
 vm_SRC += vm/frame.c                    # Frame table manager.
 vm_SRC += vm/page.c                     # Page table manager.
 vm_SRC += devices/swap.c		# Swap block manager.
+vm_SRC += vm/stackgrowth.c              # Stack growth functions.
 #vm_SRC = vm/file.c			# Some other file.
 
 # Filesystem code.

src/userprog/Make.vars

@@ -1,7 +1,7 @@
 # -*- makefile -*-
 
-kernel.bin: DEFINES = -DUSERPROG -DFILESYS -DVM
-KERNEL_SUBDIRS = threads devices lib lib/kernel userprog filesys vm
+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

src/userprog/exception.c

@@ -2,15 +2,9 @@
 #include <inttypes.h>
 #include <stdio.h>
 #include "userprog/gdt.h"
-#include "userprog/pagedir.h"
-#include "userprog/process.h"
 #include "threads/interrupt.h"
-#include "threads/palloc.h"
 #include "threads/thread.h"
-#include "threads/vaddr.h"
-
-#define MAX_STACK_SIZE (8 * 1024 * 1024) // 8MB
-#define MAX_STACK_OFFSET 32 // 32 bytes offset below stack pointer (ESP)
+#include "vm/stackgrowth.h"
 
 /* Number of page faults processed. */
 static long long page_fault_cnt;
@@ -18,9 +12,6 @@ static long long page_fault_cnt;
 static void kill (struct intr_frame *);
 static void page_fault (struct intr_frame *);
 
-static bool is_valid_stack_access (const void *fault_addr, const void *esp);
-static bool grow_stack (void *upage);
-
 /* Registers handlers for interrupts that can be caused by user
    programs.
 
@@ -155,26 +146,18 @@ page_fault (struct intr_frame *f)
   write = (f->error_code & PF_W) != 0;
   user = (f->error_code & PF_U) != 0;
 
-  if (!user || !not_present)
+#ifdef VM
+  if (user && not_present)
+    {
+      if (handle_stack_fault (fault_addr, f->esp)) return;
+    }
+  else
     {
       f->eip = (void *)f->eax;
       f->eax = 0xffffffff;
       return;
     }
-
-  /* If the fault address is in a user page that is not present, then it might
-   be just that the stack needs to grow. So we attempt to grow the stack. */
-  void *upage = pg_round_down (fault_addr);
-  if (not_present && is_user_vaddr (upage) && upage != NULL)
-    {
-      if (is_valid_stack_access (fault_addr, f->esp))
-        {
-          if (grow_stack (upage))
-            return;
-        }
-
-      /* TODO: Check SPT for the page. */
-    }
+#endif
 
   /* To implement virtual memory, delete the rest of the function
      body, and replace it with code that brings in the page to
@@ -187,50 +170,3 @@ page_fault (struct intr_frame *f)
   kill (f);
 }
 
-/* Validates whether the fault address is a valid stack access. Access is a
-   valid stack access under the following two conditions:
-     1. The fault address must be within MAX_STACK_OFFSET (32) bytes below
-      the current stack pointer. (Accounts for both PUSH and PUSHA instructions)
-     2. Growing this stack to this address does not cause it to exceed the
-      MAX_STACK_SIZE (8MB) limit.
-
-   Returns true if both conditions are met, false otherwise.
-
-   Pre: fault_addr is a valid user virtual address (so also not NULL). */
-static bool
-is_valid_stack_access (const void *fault_addr, const void *esp)
-{
-  uint32_t new_stack_size = PHYS_BASE - pg_round_down (fault_addr);
-
-  uint32_t *lowest_valid_push_addr = (uint32_t *)esp - MAX_STACK_OFFSET;
-  bool is_within_push_range = (uint32_t *)fault_addr >= lowest_valid_push_addr;
-
-  return is_within_push_range && new_stack_size <= MAX_STACK_SIZE;
-}
-
-/* Attempts to grow the stack by allocating and mapping a new page.
-  This involves:
-    1. Allocating a zeroed page from the user pool
-    2. Installing it into the page table with write permissions
-
-  Returns true if the stack was successfully grown, false if either
-  allocation or installation fails.
-
-  Pre: upage is a valid page-aligned address (so also not NULL). */
-static bool
-grow_stack (void *upage)
-{
-  /* Allocate new page for stack */
-  void *kpage = palloc_get_page (PAL_USER | PAL_ZERO);
-  if (kpage == NULL)
-    return false;
-
-  /* Install the page into user page table */
-  if (!install_page (upage, kpage, true))
-    {
-      palloc_free_page (kpage);
-      return false;
-    }
-
-  return true;
-}

src/userprog/pagedir.c

@@ -53,7 +53,7 @@ pagedir_destroy (uint32_t *pd)
    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 *
+uint32_t *
 lookup_page (uint32_t *pd, const void *vaddr, bool create)
 {
   uint32_t *pt, *pde;

src/userprog/pagedir.h

@@ -6,6 +6,7 @@
 
 uint32_t *pagedir_create (void);
 void pagedir_destroy (uint32_t *pd);
+uint32_t *lookup_page (uint32_t *pd, const void *vaddr, bool create);
 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);

src/userprog/process.c

@@ -118,7 +118,7 @@ process_execute (const char *cmd)
 
 static void *get_usr_kpage (enum palloc_flags flags, void *upage);
 static void free_usr_kpage (void *kpage);
-bool install_page (void *upage, void *kpage, bool writable);
+static bool install_page (void *upage, void *kpage, bool writable);
 
 static bool process_init_stack (char *cmd_saveptr, void **esp, char *file_name);
 static void *push_to_stack (void **esp, void *data, size_t data_size);
@@ -809,7 +809,7 @@ free_usr_kpage (void *kpage)
    with palloc_get_page().
    Returns true on success, false if UPAGE is already mapped or
    if memory allocation fails. */
-bool
+static bool
 install_page (void *upage, void *kpage, bool writable)
 {
   struct thread *t = thread_current ();

src/userprog/process.h

@@ -8,6 +8,4 @@ int process_wait (tid_t);
 void process_exit (void);
 void process_activate (void);
 
-bool install_page (void *upage, void *kpage, bool writable);
-
 #endif /* userprog/process.h */

src/vm/page.c

@@ -1,4 +1,9 @@
 #include "page.h"
+#include "userprog/pagedir.h"
+#include "threads/pte.h"
+
+#define SWAP_FLAG_BIT 9
+#define ADDR_START_BIT 12
 
 /* Updates the 'owner' thread's page table entry for virtual address 'upage'
    to have a present bit of 0 and stores the specified swap slot value in the
@@ -6,7 +11,17 @@
 void
 page_set_swap (struct thread *owner, void *upage, size_t swap_slot)
 {
+   uint32_t *pte = lookup_page (owner->pagedir, upage, false);
 
+   /* Store the provided swap slot in the address bits of the page table
+      entry, truncating excess bits. */
+   *pte |= (1 << SWAP_FLAG_BIT);
+   uint32_t swap_slot_bits = (swap_slot << ADDR_START_BIT) & PTE_ADDR;
+   *pte = (*pte & PTE_FLAGS) | swap_slot_bits;
+
+   /* Mark page as 'not present' and flag the page directory as having
+      been modified. */
+   pagedir_clear_page (owner->pagedir, upage);
 }
 
 /* Given that the page with user address 'upage' owned by 'owner' is flagged
@@ -15,6 +30,12 @@ page_set_swap (struct thread *owner, void *upage, size_t swap_slot)
 size_t
 page_get_swap (struct thread *owner, void *upage)
 {
+   uint32_t *pte = lookup_page (owner->pagedir, upage, false);
 
+   ASSERT ((*pte & PTE_P) == 0);
+   ASSERT ((*pte & (1 << SWAP_FLAG_BIT)) != 0);
+
+   /* Masks the address bits and returns truncated value. */
+   return ((*pte & PTE_ADDR) >> ADDR_START_BIT);
 }
 

src/vm/stackgrowth.c

@@ -0,0 +1,59 @@
+#include <stdio.h>
+#include "stackgrowth.h"
+#include "frame.h"
+#include "threads/palloc.h"
+#include "threads/thread.h"
+#include "threads/vaddr.h"
+#include "userprog/pagedir.h"
+
+#define MAX_STACK_ACCESS_DIST 32
+
+static bool is_stack_fault (const void *addr, const void *esp);
+static bool grow_stack (const void *addr);
+
+/* Determine whether a particular page fault occured due to a stack
+   access below the stack pointer that should induce stack growth, and
+   if so grow the stack by a single page (capped at MAX_STACK_SIZE). */
+bool
+handle_stack_fault (const void *ptr, const void *esp)
+{
+  return is_stack_fault (ptr, esp) && grow_stack (ptr);
+}
+
+/* Determines whether a particular page fault appears to be caused by
+   a stack access that should induce dynamic stack growth. Stack size
+   is capped at MAX_STACK_SIZE. */
+static bool
+is_stack_fault (const void *addr, const void *esp)
+{
+  return ((uint32_t*)addr >= ((uint32_t*)esp - MAX_STACK_ACCESS_DIST) &&
+          ((PHYS_BASE - pg_round_down (addr)) <= MAX_STACK_SIZE));
+}
+
+/* Grows the stack of the process running inside the current thread by a single
+   page given a user virtual address inside of the page wherein the new section
+   of the stack should be allocated. */
+static bool
+grow_stack (const void *addr)
+{
+  struct thread *t = thread_current ();
+  void *last_page = pg_round_down (addr);
+
+  /* This function should only be called when dealing with a faulting stack
+     access that induces stack growth, so the provided address shouldn't be
+     present in a page within the current thread's page directory. */
+  ASSERT (pagedir_get_page (t->pagedir, last_page) == NULL);
+
+  uint8_t *new_page = frame_alloc (PAL_ZERO, last_page, t);
+  if (new_page == NULL)
+    return false;
+
+  if (!pagedir_set_page (t->pagedir, last_page, new_page, true))
+  {
+    frame_free (new_page);
+    return false;
+  }
+
+  return true;
+}
+

src/vm/stackgrowth.h

@@ -0,0 +1,10 @@
+#ifndef VM_GROWSTACK_H
+#define VM_GROWSTACK_H
+
+#include <stdio.h>
+
+#define MAX_STACK_SIZE 8388608 // (8MB)
+
+bool handle_stack_fault (const void *ptr, const void *esp);
+
+#endif /* vm/frame.h */