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,8 @@ 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.
 filesys_SRC  = filesys/filesys.c	# Filesystem core.

src/threads/thread.h

@@ -143,6 +143,8 @@ struct thread
     struct hash open_files;             /* Hash Table of FD -> Struct File. */
 #endif
 
+    void *curr_esp;
+
     /* Owned by thread.c. */
     unsigned magic;                     /* Detects stack overflow. */
   };

src/userprog/exception.c

@@ -4,6 +4,7 @@
 #include "userprog/gdt.h"
 #include "threads/interrupt.h"
 #include "threads/thread.h"
+#include "vm/stackgrowth.h"
 
 /* Number of page faults processed. */
 static long long page_fault_cnt;
@@ -145,6 +146,19 @@ page_fault (struct intr_frame *f)
   write = (f->error_code & PF_W) != 0;
   user = (f->error_code & PF_U) != 0;
 
+#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;
+    }
+#endif
+
   /* To implement virtual memory, delete the rest of the function
      body, and replace it with code that brings in the page to
      which fault_addr refers. */

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/syscall.c

@@ -11,6 +11,7 @@
 #include "userprog/process.h"
 #include "userprog/pagedir.h"
 #include <stdio.h>
+#include <stdbool.h>
 #include <syscall-nr.h>
 
 #define MAX_SYSCALL_ARGS 3
@@ -46,8 +47,11 @@ static unsigned syscall_tell (int fd);
 static void syscall_close (int fd);
 
 static struct open_file *fd_get_file (int fd);
-static void validate_user_pointer (const void *start, size_t size);
-static void validate_user_string (const char *str);
+static void validate_user_pointer (const void *ptr, size_t size,
+                                   bool check_write);
+static void validate_user_string (const char *str, bool check_write);
+static int get_user (const uint8_t *);
+static bool put_user (uint8_t *, uint8_t);
 
 /* A struct defining a syscall_function pointer along with its arity. */
 struct syscall_arguments
@@ -96,8 +100,9 @@ static void
 syscall_handler (struct intr_frame *f)
 {
   /* First, read the system call number from the stack. */
-  validate_user_pointer (f->esp, sizeof (uintptr_t));
-  uintptr_t syscall_number = *(int *) f->esp;
+  validate_user_pointer (f->esp, sizeof (uintptr_t), false);
+  uintptr_t syscall_number = *(int *)f->esp;
+  thread_current ()->curr_esp = f->esp;
 
   /* Ensures the number corresponds to a system call that can be handled. */
   if (syscall_number >= LOOKUP_SIZE)
@@ -107,11 +112,10 @@ syscall_handler (struct intr_frame *f)
 
   /* Next, read and copy the arguments from the stack pointer. */
   validate_user_pointer (f->esp + sizeof (uintptr_t),
-                         syscall.arity * sizeof (uintptr_t));
-
-  uintptr_t args[MAX_SYSCALL_ARGS] = {0};
+                         syscall.arity * sizeof (uintptr_t), false);
+  uintptr_t args[MAX_SYSCALL_ARGS] = { 0 };
   for (int i = 0; i < syscall.arity && i < MAX_SYSCALL_ARGS; i++)
-    args[i] = *(uintptr_t *) (f->esp + sizeof (uintptr_t) * (i + 1));
+    args[i] = *(uintptr_t *)(f->esp + sizeof (uintptr_t) * (i + 1));
 
   /* Call the function that handles this system call with the arguments. When
      there is a return value it is stored in f->eax. */
@@ -140,8 +144,7 @@ syscall_exit (int status)
 static pid_t
 syscall_exec (const char *cmd_line)
 {
-  /* Validate the user string before executing the process. */
-  validate_user_string (cmd_line);
+  validate_user_string (cmd_line, false);
 
   return process_execute (cmd_line); /* Returns the PID of the new process */
 }
@@ -160,8 +163,7 @@ syscall_wait (pid_t pid)
 static bool
 syscall_create (const char *file, unsigned initial_size)
 {
-  /* Validate the user string before creating the file. */
-  validate_user_string (file);
+  validate_user_string (file, false);
 
   /* Acquire the file system lock to prevent race conditions. */
   lock_acquire (&filesys_lock);
@@ -178,8 +180,7 @@ syscall_create (const char *file, unsigned initial_size)
 static bool
 syscall_remove (const char *file)
 {
-  /* Validate the user string before removing the file. */
-  validate_user_string (file);
+  validate_user_string (file, false);
 
   /* Acquire the file system lock to prevent race conditions. */
   lock_acquire (&filesys_lock);
@@ -197,8 +198,7 @@ syscall_remove (const char *file)
 static int
 syscall_open (const char *file)
 {
-  /* Validate the user string before opening the file. */
-  validate_user_string (file);
+  validate_user_string (file, false);
 
   /* Acquire the file system lock to prevent race conditions. */
   lock_acquire (&filesys_lock);
@@ -264,8 +264,7 @@ syscall_read (int fd, void *buffer, unsigned size)
   if (fd < STDIN_FILENO || fd == STDOUT_FILENO)
     return EXIT_FAILURE;
 
-  /* Validate the user buffer for the provided size before reading. */
-  validate_user_pointer (buffer, size);
+  validate_user_pointer (buffer, size, true);
 
   if (fd == STDIN_FILENO)
     {
@@ -308,8 +307,7 @@ syscall_write (int fd, const void *buffer, unsigned size)
   if (fd <= 0)
     return 0;
 
-  /* Validate the user buffer for the provided size before writing. */
-  validate_user_pointer (buffer, size);
+  validate_user_pointer (buffer, size, false);
 
   if (fd == STDOUT_FILENO)
     {
@@ -451,63 +449,91 @@ fd_get_file (int fd)
   return hash_entry (e, struct open_file, elem);
 }
 
-/* Validates if a block of memory starting at START and of size SIZE bytes is
-   fully contained within user virtual memory. Kills the thread (by exiting with
-   failure) if the memory is invalid. Otherwise, returns (nothing) normally.
-   If the size is 0, the function does no checks and returns the given ptr. */
+/* Validates if a block of memory starting at PTR and of size SIZE bytes is
+   fully contained within valid user virtual memory. thread_exit () if the
+   memory is invalid.
+   If the size is 0, the function does no checks and returns PTR. */
 static void
-validate_user_pointer (const void *start, size_t size)
+validate_user_pointer (const void *ptr, size_t size, bool check_write)
 {
-  /* If the size is 0, we do not need to check anything. */
   if (size == 0)
     return;
-
-  const void *end = start + size - 1;
-
-  /* Check if the start and end pointers are valid user virtual addresses. */
-  if (start == NULL || !is_user_vaddr (start) || !is_user_vaddr (end))
+  /* ptr < ptr + size - 1, so sufficient to check that (ptr + size -1) is a
+     valid user virtual memory address. */
+  void *last = ptr + size - 1;
+  if (!is_user_vaddr (last))
     syscall_exit (EXIT_FAILURE);
-
-  /* We now need to check if the entire memory block is mapped to physical
-     memory by the page table. */
-  for (const void *ptr = pg_round_down (start); ptr <= end; ptr += PGSIZE)
-    if (pagedir_get_page (thread_current ()->pagedir, ptr) == NULL)
-      syscall_exit (EXIT_FAILURE);
+  ptr = pg_round_down (ptr);
+  while (ptr <= last)
+    {
+      int result;
+      /* Check read access to pointer. */
+      if ((result = get_user (ptr)) == -1)
+        syscall_exit (EXIT_FAILURE);
+      /* Check write access to pointer (if required). */
+      if (check_write && !put_user (ptr, result))
+        syscall_exit (EXIT_FAILURE);
+      ptr += PGSIZE;
+    }
 }
 
-/* Validates if a string is fully contained within user virtual memory. Kills
-   the thread (by exiting with failure) if the memory is invalid. Otherwise,
-   returns (nothing) normally. */
+/* Validates of a C-string starting at ptr is fully contained within valid
+   user virtual memory. thread_exit () if the memory is invalid. */
 static void
-validate_user_string (const char *str)
+validate_user_string (const char *ptr, bool check_write)
 {
-  /* Check if the string pointer is a valid user virtual address. */
-  if (str == NULL || !is_user_vaddr (str))
-    syscall_exit (EXIT_FAILURE);
+  size_t offset = (uintptr_t) ptr % PGSIZE;
 
-  /* Calculate the offset of the string within the (first) page. */
-  size_t offset = (uintptr_t) str % PGSIZE;
-
-  /* We move page by page, checking if the page is mapped to physical memory. */
   for (;;)
-  {
-    void *page = pg_round_down (str);
+    {
+      void *page = pg_round_down (ptr);
 
-    /* If we reach addresses that are not mapped to physical memory before the
-       end of the string, the thread is terminated. */
-    if (!is_user_vaddr(page) ||
-        pagedir_get_page (thread_current ()->pagedir, page) == NULL)
-      syscall_exit (EXIT_FAILURE);
+      if (!is_user_vaddr (page))
+        syscall_exit (EXIT_FAILURE);
+      if (!is_user_vaddr (ptr))
+        syscall_exit (EXIT_FAILURE);
+      int result;
+      if ((result = get_user ((const uint8_t *)ptr)) == -1)
+        syscall_exit (EXIT_FAILURE);
+      if (check_write && !put_user ((uint8_t *)ptr, result))
+        syscall_exit (EXIT_FAILURE);
 
-    while (offset < PGSIZE)
+      while (offset < PGSIZE)
       {
-        if (*str == '\0')
+        if (*ptr == '\0')
           return; /* We reached the end of the string without issues. */
 
-        str++;
+        ptr++;
         offset++;
       }
 
-    offset = 0; /* Next page will start at the beginning. */
-  }
+      offset = 0;
+
+    }
+}
+
+/* PROVIDED BY SPEC.
+   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; movzbl %1, %0; 1:" : "=&a"(result) : "m"(*uaddr));
+  return result;
+}
+
+/* PROVIDED BY SPEC.
+   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; movb %b2, %1; 1:"
+       : "=&a"(error_code), "=m"(*udst)
+       : "q"(byte));
+  return error_code != -1;
 }

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 */