fix: invalidate PTEs of evicted pages before eviction occurs to prevent modificationof pages mid-eviction

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.bin: DEFINES = -DUSERPROG -DFILESYS
-KERNEL_SUBDIRS = threads devices lib lib/kernel userprog filesys vm
+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

@@ -1,16 +1,18 @@
 #include "userprog/exception.h"
 #include <inttypes.h>
 #include <stdio.h>
+#include "stdbool.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 "userprog/pagedir.h"
+#ifdef VM
+#include "vm/stackgrowth.h"
+#include "vm/frame.h"
+#include "vm/page.h"
+#include "devices/swap.h"
 #include "threads/vaddr.h"
-
+#endif
-#define MAX_STACK_SIZE (8 * 1024 * 1024) // 8MB
-#define MAX_STACK_OFFSET 32 // 32 bytes offset below stack pointer (ESP)
 
 /* Number of page faults processed. */
 static long long page_fault_cnt;
@@ -18,9 +20,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 +154,45 @@ 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
-  {
+  struct thread *t = thread_current ();
-    f->eip = (void *)f->eax;
+  if (user)
-    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 (not_present)
         {
-          if (grow_stack (upage))
+          /* Check if the non-present user page is in the swap partition.
-            return;
+             If so, swap it back into main memory, updating the PTE for
-        }
+             the faulted virtual address to point to the newly allocated
+             frame. */
+          if (page_in_swap (t, fault_addr))
+            {
+              size_t swap_slot = page_get_swap (t, fault_addr);
+              void *upage = pg_round_down (fault_addr);
+              void *kpage = frame_alloc (0, upage, t);
+              swap_in (kpage, swap_slot);
 
-      /* TODO: Check SPT for the page. */
+              bool writeable = pagedir_is_writable (t->pagedir, upage);
+              if (pagedir_set_page (t->pagedir, upage, kpage, writeable)) return;
+            }
+
+          /* Handle user page faults that need to be resolved by dynamic
+             stack growth by checking if this is such a fault and responding
+             accordingly. */
+          if (handle_stack_fault (fault_addr, f->esp)) return;
+        }
     }
+  else
+    { 
+      /* Handle kernel page faults that need to be resolved by dynamic stack
+         growth by checking if this is such a fault and responding
+         accordingly. */
+      if (not_present && handle_stack_fault (fault_addr, t->curr_esp)) return;
+
+      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
@@ -187,50 +205,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

@@ -7,7 +7,6 @@
 #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.
@@ -53,7 +52,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;
@@ -278,7 +277,7 @@ active_pd (void)
    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
+void
 invalidate_pagedir (uint32_t *pd) 
 {
   if (active_pd () == pd) 

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);
@@ -16,5 +17,6 @@ void pagedir_set_accessed (uint32_t *pd, const void *upage, bool accessed);
 bool pagedir_is_writable (uint32_t *pd, const void *upage);
 void pagedir_set_writable (uint32_t *pd, const void *upage, bool writable);
 void pagedir_activate (uint32_t *pd);
+void invalidate_pagedir (uint32_t *pd);
 
 #endif /* userprog/pagedir.h */

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

@@ -93,6 +93,13 @@ frame_alloc (enum palloc_flags flags, void *upage, struct thread *owner)
       ASSERT (victim != NULL); /* get_victim () should never return null. */
 
       /* 2. Swap out victim into disk. */
+      /* Mark page as 'not present' and flag the page directory as having
+         been modified *before* eviction begins to prevent the owner of the
+         victim page from accessing/modifying it mid-eviction. */
+      pagedir_clear_page (owner->pagedir, upage);
+
+      // TODO: Lock PTE of victim page for victim process.
+
       size_t swap_slot = swap_out (victim->frame);
       page_set_swap (victim->owner, victim->upage, swap_slot);
 

src/vm/page.c

@@ -1,12 +1,35 @@
 #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
+   to flag the page as being stored in swap, and stores the specified swap slot
-   entry for later retrieval from disk. */
+   value in the entry at the address bits for later retrieval from disk. */
 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;
+
+   invalidate_pagedir (owner->pagedir);
+}
+
+/* Returns true iff the page with user address 'upage' owned by 'owner' 
+   is flagged to be in the swap disk via the owner's page table. */
+bool
+page_in_swap (struct thread *owner, void *upage)
+{
+   uint32_t *pte = lookup_page (owner->pagedir, upage, false);
+   return pte != NULL &&
+          (*pte & (1 << SWAP_FLAG_BIT)) != 0;
 }
 
 /* Given that the page with user address 'upage' owned by 'owner' is flagged
@@ -15,6 +38,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 != NULL);
+   ASSERT ((*pte & PTE_P) == 0);
+
+   /* Masks the address bits and returns truncated value. */
+   return ((*pte & PTE_ADDR) >> ADDR_START_BIT);
 }
 

src/vm/page.h

@@ -4,6 +4,7 @@
 #include "threads/thread.h"
 
 void page_set_swap (struct thread *, void *, size_t);
+bool page_in_swap (struct thread *, void *);
 size_t page_get_swap (struct thread *, void *);
 
 #endif /* vm/frame.h */

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