feat: implement clock (second-chance) page eviction algorithm

src/Makefile.build

@@ -63,8 +63,8 @@ userprog_SRC += userprog/tss.c		# TSS management.
 
 # Virtual memory code.
 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/file.c			# Some other file.
 
 # Filesystem code.
 filesys_SRC  = filesys/filesys.c	# Filesystem core.

src/userprog/process.c

@@ -116,7 +116,7 @@ process_execute (const char *cmd)
   return tid;
 }
 
-static void *get_usr_kpage (enum palloc_flags flags);
+static void *get_usr_kpage (enum palloc_flags flags, void *upage);
 static void free_usr_kpage (void *kpage);
 static bool install_page (void *upage, void *kpage, bool writable);
 
@@ -257,12 +257,13 @@ process_init_stack (char *cmd_saveptr, void **esp, char *file_name)
         int pages_needed = DIV_CEIL (overflow_bytes, PGSIZE);
 
         /* Allocate the pages and map them to the user process. */
+        void *upage;
+        uint8_t *kpage;
         for (int i = 1; i < pages_needed + 1; i++)
           {
-            uint8_t *kpage = get_usr_kpage (PAL_ZERO);
-            if (!install_page (((uint8_t *) PHYS_BASE) - PGSIZE * (i + 1),
-                               kpage, true))
-              return false;
+            upage = ((uint8_t *) PHYS_BASE) - PGSIZE * (i + 1);
+            kpage = get_usr_kpage (PAL_ZERO, upage);
+            if (!install_page (upage, kpage, true)) return false;
           }
       }
 
@@ -710,7 +711,7 @@ load_segment (struct file *file, off_t ofs, uint8_t *upage,
       if (kpage == NULL){
         
         /* Get a new page of memory. */
-        kpage = get_usr_kpage (0);
+        kpage = get_usr_kpage (0, upage);
         if (kpage == NULL){
           return false;
         }
@@ -752,11 +753,13 @@ setup_stack (void **esp)
 {
   uint8_t *kpage;
   bool success = false;
-
-  kpage = get_usr_kpage (PAL_ZERO);
+  
+  void *upage = ((uint8_t *) PHYS_BASE) - PGSIZE;
+  
+  kpage = get_usr_kpage (PAL_ZERO, upage);
   if (kpage != NULL) 
     {
-      success = install_page (((uint8_t *) PHYS_BASE) - PGSIZE, kpage, true);
+      success = install_page (upage, kpage, true);
       if (success)
         *esp = PHYS_BASE;
       else
@@ -765,14 +768,20 @@ setup_stack (void **esp)
   return success;
 }
 
-/* Claims a page from the user pool and returns its kernel address,
-   updating the frame table if VM is enabled. */
+/* Claims a page from the user pool for ownership by the current thread
+   and returns its kernel address, updating the frame table if VM
+   is enabled. Requires the intended virtual address for where the page
+   will be installed. */
 static void *
-get_usr_kpage (enum palloc_flags flags)
+get_usr_kpage (enum palloc_flags flags, void *upage)
 {
   void *page;
 #ifdef VM
-  page = frame_alloc (flags);
+  struct thread *t = thread_current ();
+  if (pagedir_get_page (t->pagedir, upage) != NULL)
+    return NULL;
+  else
+    page = frame_alloc (flags, upage, t);
 #else
   page = palloc_get_page (flags | PAL_USER);
 #endif

src/vm/frame.c

@@ -1,34 +1,42 @@
 #include <debug.h>
 #include <hash.h>
 #include <list.h>
+#include <string.h>
 
 #include "frame.h"
+#include "page.h"
 #include "threads/malloc.h"
+#include "threads/vaddr.h"
+#include "userprog/pagedir.h"
 #include "threads/synch.h"
+#include "devices/swap.h"
 
 /* Hash table that maps every active frame's kernel virtual address
    to its corresponding 'frame_metadata'.*/
 struct hash frame_table;
 
-/* Linked list of frame_metadata whose pages are predicted to currently
-   be in the working set of a process. They are not considered for
-   eviction, but are considered for demotion to the 'inactive' list. */
-struct list active_list;
+/* Linked list used to represent the circular queue in the 'clock'
+   algorithm for page eviction. Iterating from the element that is
+   currently pointed at by 'next_victim' yields an ordering of the entries
+   from oldest to newest (in terms of when they were added or checked
+   for having been referenced by a process). */
+struct list lru_list;
 
-/* Linked list of frame_metadata whose pages are predicted to leave the
-   working set of their processes soon, so are considered for eviction.
-   Pages are considered for eviction from the tail end, and are initially
-   demoted to 'inactive' at the head. */
-struct list inactive_list;
+/* The next element in lru_list to be considered for eviction (oldest added
+   or referenced page in the circular queue). If this page has has an
+   'accessed' bit of 0 when considering eviction, then it will be the next
+   victim. Otherwise, the next element in the queue is similarly considered. */
+struct list_elem *next_victim = NULL;
 
 /* Synchronisation variables. */
-/* Ensures mutual exclusion to accessing the 'head' and first element of
-   'inactive_list', which is accessed every time a frame is allocated. */
-struct lock inactive_head_lock;
+/* Protects access to 'lru_list'. */
+struct lock lru_lock;
 
 struct frame_metadata
   {
      void *frame;  /* The kernel virtual address holding the frame. */
+     void *upage; /* The user virtual address pointing to the frame. */
+     struct thread *owner; /* Pointer to the thread that owns the frame. */
      struct hash_elem hash_elem;  /* Tracks the position of the frame metadata
                                      within 'frame_table', whose key is the 
                                      kernel virtual address of the frame. */
@@ -40,56 +48,102 @@ struct frame_metadata
 hash_hash_func frame_metadata_hash;
 hash_less_func frame_metadata_less;
 
+static struct list_elem *lru_next (struct list_elem *e);
+static struct list_elem *lru_prev (struct list_elem *e);
+static struct frame_metadata *get_victim (void);
+
 /* Initialize the frame system by initializing the frame (hash) table with
    the frame_metadata hashing and comparison functions, as well as initializing
-   the active & inactive lists. Also initializes the system's synchronisation
-   primitives. */
+   'lru_list' and its associated synchronisation primitives. */
 void
 frame_init (void)
 {
   hash_init (&frame_table, frame_metadata_hash, frame_metadata_less, NULL);
-  list_init (&active_list);
-  list_init (&inactive_list);
 
-  lock_init (&inactive_head_lock);
+  list_init (&lru_list);
+  lock_init (&lru_lock);
 }
 
+/* TODO: Consider synchronisation more closely (i.e. just for hash
+         table). */
 /* Attempt to allocate a frame for a user process, either by direct
    allocation of a user page if there is sufficient RAM, or by
    evicting a currently active page if memory allocated for user
    processes is fulled and storing it in swap. If swap is full in
    the former case, panic the kernel. */
 void *
-frame_alloc (enum palloc_flags flags)
+frame_alloc (enum palloc_flags flags, void *upage, struct thread *owner)
 {
+  struct frame_metadata *frame_metadata;
   flags |= PAL_USER;
-
+  
+  lock_acquire (&lru_lock);
   void *frame = palloc_get_page (flags);
+
+  /* If a frame couldn't be allocated we must be out of main memory. Thus,
+     obtain a victim page to replace with our page, and swap the victim
+     into disk. */
   if (frame == NULL)
     {
-      /* TODO: Find victim page to replace, and swap it with this new page. */
-      return NULL;
+      /* 1. Obtain victim. */
+      if (next_victim == NULL)
+        PANIC ("Couldn't allocate a single page to main memory!\n");
+
+      struct frame_metadata *victim = get_victim ();
+      ASSERT (victim != NULL); /* get_victim () should never return null. */
+
+      /* 2. Swap out victim into disk. */
+      size_t swap_slot = swap_out (victim->frame);
+      page_set_swap (victim->owner, victim->upage, swap_slot);
+
+      /* If zero flag is set, zero out the victim page. */
+      if (flags & PAL_ZERO)
+        memset (victim->frame, 0, PGSIZE);
+
+      /* 3. Indicate that the new frame's metadata will be stored
+            inside the same structure that stored the victim's metadata.
+            As both the new frame and the victim frame share the same kernel
+            virtual address, the hash map need not be updated, and neither
+            the list_elem value as both share the same lru_list position. */
+      frame_metadata = victim;
     }
 
-  struct frame_metadata *frame_metadata =
-    malloc (sizeof (struct frame_metadata));
-  frame_metadata->frame = frame;
+  /* If sufficient main memory allows the frame to be directly allocated,
+     we must update the frame table with a new entry, and grow lru_list. */
+  else
+    {
+      /* Must own lru_lock here, as otherwise there is a race condition
+         with next_victim either being NULL or uninitialized. */
+      frame_metadata = malloc (sizeof (struct frame_metadata));
+      frame_metadata->frame = frame;
 
-  /* Newly faulted pages begin at the head of the inactive list. */
-  lock_acquire (&inactive_head_lock);
-  list_push_front (&inactive_list, &frame_metadata->list_elem);
-  lock_release (&inactive_head_lock);
+      /* Newly allocated frames are pushed to the back of the circular queue
+         represented by lru_list. Must explicitly handle the case where the
+         circular queue is empty (when next_victim == NULL). */
+      if (next_victim == NULL)
+        {
+          list_push_back (&lru_list, &frame_metadata->list_elem);
+          next_victim = &frame_metadata->list_elem;
+        }
+      else
+        {
+          struct list_elem *lru_tail = lru_prev (next_victim);
+          list_insert (lru_tail, &frame_metadata->list_elem);
+        }
 
-  /* Finally, insert frame metadata within the frame table, with the key as its
-     allocated kernel address. */
-  hash_replace (&frame_table, &frame_metadata->hash_elem);
+      hash_insert (&frame_table, &frame_metadata->hash_elem);
+    }
 
-  return frame;
+  frame_metadata->upage = upage;
+  frame_metadata->owner = owner;
+  lock_release (&lru_lock);
+
+  return frame_metadata->frame;
 }
 
 /* Attempt to deallocate a frame for a user process by removing it from the
-   frame table as well as active/inactive list, and freeing the underlying
-   page memory. Panics if the frame isn't active in memory. */
+   frame table as well as lru_list, and freeing the underlying page
+   memory & metadata struct. Panics if the frame isn't active in memory. */
 void
 frame_free (void *frame)
   {
@@ -98,17 +152,58 @@ frame_free (void *frame)
 
     struct hash_elem *e =
       hash_delete (&frame_table, &key_metadata.hash_elem);
-    if (e == NULL) PANIC ("Attempted to free a frame without a corresponding "
-                          "kernel address!\n");
+    if (e == NULL) PANIC ("Attempted to free a frame at kernel address %p, "
+                          "but this address is not allocated!\n", frame);
 
     struct frame_metadata *frame_metadata =
       hash_entry (e, struct frame_metadata, hash_elem);
     
+    lock_acquire (&lru_lock);
     list_remove (&frame_metadata->list_elem);
+
+    /* If we're freeing the frame marked as the next victim, update
+       next_victim to either be the next least recently used page, or NULL
+       if no pages are loaded in main memory. */
+    if (&frame_metadata->list_elem == next_victim)
+      {
+        if (list_empty (&lru_list))
+          next_victim = NULL;
+        else
+          next_victim = lru_next (next_victim);
+      }
+    lock_release (&lru_lock);
+
     free (frame_metadata);
     palloc_free_page (frame);
   }
 
+/* TODO: Account for page aliases when checking accessed bit. */
+/* A pre-condition for calling this function is that the calling thread
+   owns lru_lock and that lru_list is non-empty. */
+static struct frame_metadata *
+get_victim (void)
+  {
+    struct list_elem *e = next_victim;
+    struct frame_metadata *frame_metadata;
+    uint32_t *pd;
+    void *upage;
+    for (;;)
+      {
+        frame_metadata = list_entry (e, struct frame_metadata, list_elem);
+        pd = frame_metadata->owner->pagedir;
+        upage = frame_metadata->upage;
+        e = lru_next (e);
+
+        if (!pagedir_is_accessed (pd, upage))
+          break;
+
+        pagedir_set_accessed (pd, upage, false);
+      }
+
+    next_victim = e;
+    return frame_metadata;
+  }
+
 /* Hash function for frame metadata, used for storing entries in the
    frame table. */
 unsigned
@@ -135,3 +230,27 @@ frame_metadata_less (const struct hash_elem *a_, const struct hash_elem *b_,
     return a->frame < b->frame;
   }
 
+/* Returns the next recently used element after the one provided, which
+   is achieved by iterating through lru_list like a circular queue
+   (wrapping around the list at the tail). */
+static struct list_elem *
+lru_next (struct list_elem *e)
+{
+  if (!list_empty (&lru_list) && e == list_back (&lru_list))
+    return list_front (&lru_list);
+
+  return list_next (e);
+}
+
+/* Returns the previous recently used element after the one provided, which
+   is achieved by iterating through lru_list like a circular queue
+   (wrapping around the list at the head). */
+static struct list_elem *
+lru_prev (struct list_elem *e)
+{
+  if (!list_empty (&lru_list) && e == list_front (&lru_list))
+    return list_back (&lru_list);
+
+  return list_prev (e);
+}
+

src/vm/frame.h

@@ -1,10 +1,11 @@
 #ifndef VM_FRAME_H
 #define VM_FRAME_H
 
+#include "threads/thread.h"
 #include "threads/palloc.h"
 
 void frame_init (void);
-void *frame_alloc (enum palloc_flags);
+void *frame_alloc (enum palloc_flags, void *, struct thread *);
 void frame_free (void *frame);
 
 #endif /* vm/frame.h */

src/vm/page.c

@@ -0,0 +1,20 @@
+#include "page.h"
+
+/* 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
+   entry for later retrieval from disk. */
+void
+page_set_swap (struct thread *owner, void *upage, size_t swap_slot)
+{
+
+}
+
+/* Given that the page with user address 'upage' owned by 'owner' is flagged
+   to be in the swap disk via the owner's page table, returns its stored
+   swap slot. Otherwise panics the kernel. */
+size_t
+page_get_swap (struct thread *owner, void *upage)
+{
+
+}
+

src/vm/page.h

@@ -0,0 +1,9 @@
+#ifndef VM_PAGE_H
+#define VM_PAGE_H
+
+#include "threads/thread.h"
+
+void page_set_swap (struct thread *, void *, size_t);
+size_t page_get_swap (struct thread *, void *);
+
+#endif /* vm/frame.h */