design_doc.txt

            +--------------------------+
            |          OS 211          |
            |  TASK 3: VIRTUAL MEMORY  |
            |      DESIGN DOCUMENT     |
            +--------------------------+

---- GROUP ----

>> Fill in the names and email addresses of your group members.

Ruoyu   Hu    rh4618@ic.ac.uk
Siyuan  Shen  ss16118@ic.ac.uk
Hantang Sun   hs5718@ic.ac.uk
Yifei   Zhang yz31218@ic.ac.uk

---- PRELIMINARIES ----

>> If you have any preliminary comments on your submission, or notes for the
>> markers, 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/FRAME MANAGEMENT
            =====================

---- DATA STRUCTURES ----

>> A1: (2 marks)
>> Copy here the declaration of each new or changed `struct' or `struct' member,
>> global or static variable, `typedef', or enumeration that relates to your 
>> supplemental page table and frame table. 
>> Identify the purpose of each in roughly 25 words.

struct spage_table_entry
{
  void *uaddr;      /* User virtual address corresponding to the entry */

  bool writable;    /* Whether the page denoted by uaddr is writable */
  
  bool is_installed;  /* Whether the page denoted by uaddr is installed in the
                         current process's page directory */

  bool is_swapped;  /* Whether the frame which uaddr maps to is swapped out of
                       the main memory */

  char file_name[MAX_FILENAME_LEN]; /* Name of the file whose data is contained
                                       by the page denoted by uaddr */

  off_t ofs;        /* The offset in the file that contains the data to be read
                       into the page denoted by uaddr */

  size_t page_read_byte;   /* The number of bytes to be read from the file */

  swap_index swap_slot;    /* The index in the swap table that contains the data
                              corresponding to the frame that is mapped to by
                              the page uaddr */

  struct hash_elem hash_elem; /* The hash_elem struct that is used to store this
                                 spage_table_entry in the hash table */
};

Struct spage_table_entry represents a single entry in a supplemental page table.
It stores all the information relevant to a user page.

struct thread
{
    ...
    struct hash spage_table;  /* Supplemental page table*/
    struct spage_lock;        /* A lock that ensures all operations in a
                                 supplemental page table are synchronized */
    ...
};

Since each process has its own user stack, it is only reasonable for one thread
to have its own supplemental page table in order to keep track of all of its
user pages. Hence, struct thread contains a hash table which is the data
structure that represents the supplemental page table. The lock spage_lock is
used to synchronise supplemental page table operations on this process's
spage_table across multiple processes.


struct frame_table_entry
{
   void *kpage_addr;    /* The kernel virtual address of a frame */
   
   void *uaddr;         /* The user virtual address which maps to the frame
                           denoted by kpage_addr. This is stored so that when we
                           evict the frame, we can dissociate the user page from
                           this kernel page */

   bool second_chance;  /* A boolean which indicates whether this frame should
                           be given a second chance while choosing a frame to
                           evict */

   bool pinned;       /* A boolean that indicates if the frame can be evicted */

   struct list owners;  /* A list of page_owner struct that stores processes
                           that are sharing the frame*/
   
   struct list_elem elem;   /* The list_elem struct that is used to store this
                               frame_table_entry in the frame table */
};

The frame table keeps supplemental information of each allocated frame.

static struct list frame_table;   /* Struct representing the frame table
                                     implementation, which is a global variable
                                     in the file frame.c */

static struct lock frame_table_lock;  /* Lock for synchronisation across frame
                                         table operations */

static struct list read_only_pages;   /* A list that stores all pages which are
                                         read-only */

struct read_only_page
{
  char file_name[MAX_FILENAME_LEN]; /* Name of the file whose data is saved in
                                       this read only page */

  off_t ofs;        /* The offset in the file that contains the data to be read
                       into this read only page */

  struct frame_table_entry *fte;  /* A pointer to the frame_table_entry struct
                                     that contains the actual data of this read
                                     only page */

  struct list_elem elem;  /* The list_elem struct that is used when storing this
                             read_only_page in the list called read_only_pages
                             mentioned above */
};

Struct read_only_page stores the meta data associated with read only pages. With
the help of a list of read_only_pages, we are able to locate and share read only
pages much more efficiently.

struct page_owner
{
   struct thread *owner;    /* The thread which is a owner of a particular
                               read only page*/
   void *uaddr;   /* The user virtual address of the thread denoted by owner */
   
   struct list_elem elem;   /* The list_elem struct that is used when storing
                               this page_owner in the list of owners in a
                               frame_table_entry */
};

Struct page_owner serves as a wrapper of the thread struct so that each frame
can record which processes have their user virtual address mapped to it.

---- ALGORITHMS ----

>> A2: (2 marks) 
>> Describe your code for finding the frame (if any) or other location that 
>> contains the data of a given page.

Given a page address, the process will first look for a corresponding mapping
within its pagedir. If a mapping is found, the frame is obtained and the process
continues execution as expected.

If a page-frame mapping is not found within the pagedir, a page fault is
triggered via a call to page_fault(). The page fault handler first determines if
the faulting address is an invalid address, or if the address's corresponding
page simply hasn't been loaded in. First, the process attempts to find if the
faulting address has a corresponding page entry within the supplemental page
table, i.e. if the faulting address is meant to have a frame, but does not at
the moment. This is done by rounding the faulting address down to its nearest
page address, and making a call to spage_get_entry(). If the faulting address
has an corresponding entry within the supplemental page table, then we simply
allocate it a frame by calling frame_add_entry().

Within frame_add_entry() we deal with the possibility that the given faulting
address used to have a frame but due to a shortage of frame-available memory, it
had been swapped out at some point in the past, indicated by the is_installed
and is_swapped booleans within the spage_entry struct. In this event we will
have to swap the frame back into the frame table. As the required information is
stored within the supplemental page table entry, the process has what it needs
to find the swapped frame, using the frame slot index store in the spage_entry,
it can find the swap slot which the frame was swapped to. We then allocate a
free frame from the pool, evicting another frame if necessary, and copy the
frame content back from the swap slot.

If an entry for the faulting address is not found within the supplemental page
table, we then check if the faulting address is the result of a stack growth
operation, this is only valid if the faulting address is within a PGSIZE of the
stack pointer. In this case, we add a new entry to the supplemental page table
and allocate it a new frame before continuing with process operations.

If none of the above conditions are satisfied, the faulting address is regarded
as erroneous and the process exits with exit(SYSCALL_ERROR).

>> A3: (2 marks)
>> How have you implemented sharing of read only pages?

A page is indicated as writable by the writable parameter passed to the
load_segment function and stored within the supplemental page table entry
created for the code segment page. This variable is accessed when the process
causes a page fault when it attempts to access the code segment page which has
not yet been loaded in, this behaviour is expected due to the nature of lazy
loading of pages.

Within the frame_add_entry() function, the process checks firstly if the given
page has been loaded, by making a call to rpage_lookup(), this checks through
the list read_only_pages, checking if any of the existing read_only_page
structs point towards a frame that loaded in the content of the same file at the
same offset as the current faulting page.

If an entry is found within read_only_pages, a mapping is created within the
process's pagedir between the faulting page and the frame contained within the
read_only_page entry. A new page_owner struct is created and inserted into the
frame's frame_table_entry's owners list. This allows for the different processes
that are using a frame to be recorded, the process can then read from the frame
freely, since it is read-only, it will not be edited.

Otherwise, the process goes through the normal procedure flow of allocating
(evicting if necessary) a frame for the new page, loading the code segment from
filesys and installing the page. The process then calls rpage_add to create a
new read_only_page entry within the list read_only_files. This process then
proceeds as normal, when another process requires the code segment page, it will
go through the above procedure to use the frame allocated in this instance.

When a process exits, it calls frame_free_entries() to free all the memory
allocated to structs used during the frame operations of this process. The
function iterates through all of the frames owned by the current process through
an existing mapping within the process's pagedir, for writable pages it removes
and frees the frame_table_directly. For non-readable, and thus shareable pages,
we determine if the frame is owned by any other processes, if so, we remove and
free all instances of page_owner corresponding to the current process from the
frame_table_entry but do not free it. The page-frame mapping is removed entirely
if the frame is shared to avoid the frame being deallocated within
pagedir_destroy().


---- SYNCHRONIZATION ----

>> A4: (2 marks) 
>> When two user processes both need a new frame at the same time, how are 
>> races avoided? 
>> You should consider both when there are and are not free frames 
>> available in memory.

When a process requires a new frame, the function frame_add_entry() is called,
the first thing the process does within this function is to acquire the lock
frame_table_lock, if it was not previously acquired. This ensures
synchronisation of frame table operations across processes, as no other process
can edit the frame table whilst the current process is acquiring a new frame.
The process will retain frame_table_lock until it completes its operation within
frame_add_entry().

If there are free frames in memory, the frame allocation control flow exists
entirely within frame_add_entry(), which, as mentioned above, is synchronised by
the acquisition of frame_table_lock at the start and releasing it only when the
required operation is complete.

If there are no free frames, evict_frame() is called to remove a frame using a
second chance eviction algorithm. This function selects and removes a frame
table entry and frees its corresponding frame, to allow the frame to be used
elsewhere. This is only called within frame_add_entry(), during the period where
the function is synchronised, as such no race conditions can occur between
different processes.


---- RATIONALE ----

>> A5: (2 marks)
>> Why did you choose the data structure(s) that you did for representing the
>> supplemental page table and frame table?

We implemented the supplemental page table and the frame table using a hash
table and linked-list structure respectively.

For the supplemental page table, a hash table was chosen for the quicker access
time, as each supplemental page table entry is hash inserted, the retrieval
time is effectively O(1), given an element of equivalent hash value. Whereas
retrieving an element from a linked-list has time complexity O(n).

We chose to implement the frame table using a linked-list structure for several
reasons. When allocating, installing a new frame, we create a new supplemental
page table entry, and push it to the end of the linked-list structure, this
operation is of time complexity O(1), as the start and end of a linked-list
structure can be accessed in constant time, and we do not need to hash the
element. In addition, our eviction policy is the second chance policy, which
needs to preserve the order in which the entries were inserted, a task  that the
hash table is unsuited for.


               PAGING TO AND FROM DISK
               =======================

---- DATA STRUCTURES ----

>> B1: (1 mark)
>> Copy here the declaration of each new or changed `struct' or `struct' member,
>> global or static variable, `typedef', or enumeration that relates to your 
>> swap table.  
>> Identify the purpose of each in roughly 25 words.


  typedef size_t swap_index;

A new type declared to refer to the index of swap slots. The pre-existing
block_sector_t was not appropriate in this case as swap_index does not directly
refer to a sector.


  static struct bitmap *swap_table;

The bitmap structure is our implementation of the swap table, keeps track of
which swap slots are free or in use.


  static struct block *swap_blocks;

The block of memory available for use as swap slots.


  static struct lock swap_lock;

Lock used for synchronisation across different processes for swap table
operations.

---- ALGORITHMS ----

>> B2: (2 marks)
>> When a frame is required but none is free, some frame must be evicted.
>> Describe your code for choosing a frame to evict.

When a frame needs to be evicted, function evict_frame() is called.
In the evict_frame() function, we use a second chance eviction policy to select 
the frame to evict. A static variable "frame_table_index" is stored locally
within frame.c, this variable is the pointer to the frame that will be
considered first for eviction under the eviction policy. This relates to our
choice to implement the frame table using a list structure, as the order in
which elements are inserted is significant here.

The process first iterates through the frame table until it finds the frame
referred to by frame_table_index. The eviction policy then checks if the frame
has a second chance/is_pinned, pinned frames cannot be evicted, and second
chance frames will be given a 'second chance' before it is evicted, setting the
frame's second_chance member to false and continuing onto the next frame. The
eviction policy continues to iterate through the frame table until a frame is
found where it is neither pinned or has a second chance. This frame is selected
for eviction and the frame_table_index is set to the index of the current frame,
as the frame that next occupies this slot is the next frame to be first
considered for eviction.

If the iteration through the frame table reaches the end of the list, we iterate
again from the beginning of the list. If a frame is accessed, its second_chance
member is set to true, which allows it a 'second chance' when selecting a frame
to evict.


>> B3: (2 marks)
>> When a process P obtains a frame that was previously used by a process Q,
>> how do you adjust the page directory of process Q (and any other data 
>> structures) to reflect the frame Q no longer has?

Assuming process P has called frame_add_entry() and, that no free frames are
available, as such evict_frame() is called.

When a frame is evicted in the evict_frame() function, the previous owner of the
frame is found through the 'owners' member of the frame_table_entry struct
associated with the frame. The corresponding spage_table_entry to the frame is
then fetched from the frame-owner's supplemental page table. The
spage_table_entry 'spte' contains a member is_installed, which, as the frame is
about to be evicted, is set to false. It is then determined if the soon-to-be
evicted frame is a part of a mmap, mmap frames are written back to the file
system if dirty, else disposed. Otherwise the selected frame is swapped into a
free swap slot, for this design we do not deal with situations where there is
insufficient swap memory, as specified by the project specifications.

Before evict_frame() returns, that is, before a frame is available to use for
process P, the frame's association to Q is removed. The function
pagedir_clear_page() is called to set the user page previously mapped to the
selected frame as unmapped within process Q's pagedir. The member 'is_installed'
within spte is set to false, and the 'is_swapped' member is set to whether the
frame was swapped. This is so that the next time process Q attempts to access
its data, it would page fault, but be aware of where to retrieve the frame from,
whether a swap slot, if the frame was swapped out, or to read from the filesys.

The memory previously allocated to the selected frame_table_entry is freed and
the frame is returned to the pool. A fresh page is allocated and returned from
evict_frame(). Process P, which is at this point inside frame_add_entry(),
receives the free frame and can continue execution as expected.

It is ensured that the frame which is swapped out cannot have multiple owners.
That is because in our frame table, only writable frames can be swapped out, and
no sharing is permitted for frames which may be evicted.

---- SYNCHRONIZATION ----

>> B4: (2 marks)
>> Explain how your synchronization design prevents deadlock.  
>> (You may want to refer to the necessary conditions for deadlock.)

Necessary conditions for deadlock:
1. Each recourse is only available to one process
2. A process can attempt to obtain a new resource while holding
  a previous resource.
3. Resources cannot be revoked from a process.
4. Processes form a circular chain, each holds the resource required by
the next process.

When we are managing the pages to and from the disk, we use only two locks for
synchronisation, one in the frame table and one in the swap table. The
swap table lock is only acquired in function "swap_slot_to_frame" and
"swap_frame_to_slot". These two functions are only called inside
"frame_add_entry" and "evict_frame", both of which starts with acquiring the
frame table lock. We can see that a process always acquire the frame table lock
before acquiring the swap table lock. Therefore, the fourth condition for a
deadlock is never true. So deadlock will not happen.

>> B5: (2 marks)
>> A page fault in process P can cause another process Q's frame to be evicted.
>> How do you ensure that Q cannot access or modify the page during the 
>> eviction process?

In order for process P to resolve its page fault through the allocation of a new
frame, it must first acquire the frame_table_lock. It will hold onto the lock
for the entire duration of the function frame_add_entry(), which includes the
call to evict_frame(). During this period, since P currently holds the
frame_table_lock, Q cannot make any edits to the frame table until P receives
the frame and releases the frame_table_lock. Additionally, Q cannot make any
changes to its supplemental page table entry either as evict_frame() requires P
to acquire both the frame_table_lock and Q's spage_lock, since it will be making
changes to Q's supplemental page table entry and clearing the page from Q's
pagedir.

>> B6: (2 marks)
>> A page fault in process P can cause another process Q's frame to be evicted.
>> How do you avoid a race between P evicting Q's frame and Q faulting the page
>> back in?

As mentioned in response to question B5, P evicts Q's frame as it attempts to
obtain a free frame during a page fault, more specifically in a call to
frame_add_entry(), the first and last actions a process undertakes within this
function is to acquire and release the lock frame_table_lock, respectively.

During this period, if Q page faults, and attempts to retrieve the page, it must
go through frame_add_entry(), which would require it to acquire
frame_table_lock, which it would be unable to do until P finishes acquiring the
frame and installing it to its own page.

Thus no race conditions can occur here as the frame_add_entry parts of each page
fault must occur sequentially to each other.

>> B7: (2 marks)
>> Explain how you handle access to user pages that are not present when a
>> system call is made.

When an attempt is made to access user pages that are not present when a system
call is made, a page fault is triggered. The page fault handler first checks if
the faulting address has a corresponding page entry within the supplemental page
table, this indicates that the fault is a result of an access to a page whose
frame is being loaded lazily. If this is the case, frame_add_entry() is called
to allocate and install a free frame to the page, after which upon returning
from the page fault the page can be accessed as normal.

If the page does not have a page entry within the supplemental page table, we
then check if the page fault is the result of stack grow, this is indicated by
whether the faulting address is within 1 PGSIZE of the stack pointer, and
whether the faulting address is within the maximum stack size, defined as 8MB
below PHYS_BASE. In this case we also call frame_add_entry() to allocate a free
frame and continues from there same as above.

If none of the above conditions are satisfied, then the faulting address was
truly caused by an invalid access to a page and the process terminates with the
exit status SYSCALL_ERROR.


---- RATIONALE ----

>> B8: (2 marks)
>> There is an obvious trade-off between parallelism and the complexity of your
>> synchronisation methods. 
>> Explain where your design falls along this continuum and why you chose to 
>> design it this way.

Our design leans further towards complexity than parallelism. We selected this
design as our focus was that no other process could make changes to the frame
whilst another process is allocating a frame. This is primarily due to the fact
in the event of a frame eviction, the calling process will have to evict a frame
which may be required by another currently running process, as such, we wanted
to ensure that there was no way that a frame eviction would affect the execution
of another running process.

Another consideration was that if multiple processes are handling page faults
simultaneously, a considerable amount of time would be spent context switching
between the different processes, which would increase the total amount of time
all of the processes spend attempting to allocate and install a free frame.

The swap table is currently only accessed from within frame_add_entry(), which
as discussed previously has already been synchronised, as such there is no
requirement for more sophisticated synchronisation methods within the swap
table.

The supplemental page table is process specific, as such there are no problems
when a process accesses its own supplemental page table, the only possible
race condition is when another process is evicting a frame owned by the current
process, this is avoided by requiring the evicting process to acquire the
process's spage_lock before it can make any changes to another process. Apart
from this instance, there is no other requirement for more sophisticated
synchronisation to avoid race conditions.

             MEMORY MAPPED FILES
             ===================

---- DATA STRUCTURES ----

>> C1: (1 mark)
>> Copy here the declaration of each new or changed `struct' or `struct' member,
>> global or static variable, `typedef', or enumeration that relates to your 
>> file mapping table.  
>> Identify the purpose of each in roughly 25 words.

static struct list file_mappings;     /* A list to store all the meta data
                                         related to memory-mapped files. This is
                                         located in syscall.c */

struct file_mmap
{
  mapid_t map_id;       /* An id that is used to identify a specific mmapped
                           file */

  char file_name[MAX_FILENAME_LEN];   /* Name of the file that is mmapped */
  struct thread *owner;               /* A pointer to the thread struct that
                                         belongs to the process that has mmapped
                                         the file */
  size_t file_size;                   /* The size of the mmapped file */
  void *uaddr;                        /* The user virtual address to where the
                                         file has been mapped */
  struct list_elem elem;              /* A list_elem struct so that this
                                         file_mmap can be stored in the list
                                         file_mappings */
};

The data structure stores an user address and an opened file.
When the mapped file needs to be used, the corresponding address can be found

---- ALGORITHMS ----

>> C2: (3 marks)
>> Explain how you determine whether a new file mapping overlaps with any 
>> existing segment and how you handle such a case. 
>> Additionally, how might this interact with stack growth?

When a new mapping is about to be created, we are given the file descriptor and
the starting address of the memory map. Using the file descriptor we are able to
obtain the size of the file that is to be mapped, which can be used to compute
the number of pages needed to map the file.

A for-loop is used to check the address of each page. If any of them is already
present in the supplemental page table, it indicates that the new file mapping
will overlap with an existing segment. In this case, the mmap function will
return -1 immediately.

If the new file mapping is close to the current position of the stack pointer,
it is likely that the pages added onto the stack in the future will overlap
with the file mapping. To prevent this, we introduce an additional condition
that checks whether the given user virtual address is within the reach of the
future growth of the stack. To be more specific, the address that the file maps
to is only valid if it is at least 8MB below PHYS_BASE, which is the maximum
size of the user stack.

---- RATIONALE ----

>> C3: (1 mark)
>> Mappings created with "mmap" have similar semantics to those of data 
>> demand-paged from executables. 
>> How does your code-base take advantage of this?

When we load in the executable file in load_segment(), we simply add a
supplemental page table entry for each page. When a page fault occurs, we use
palloc_get_page() to acquire a kernel page to which the data in the executable
will be copied onto, install the kernel page with the user page, and add a new
frame table entry for the corresponding kernel page, thus achieving lazy
loading. We take full advantage of the lazy-loading code-base for  mmap in a
sense that we only create the supplemental page table entries for the pages in
the virtual address space, so that when it page faults all the pages containing
memory-mapped files will be treated essentially the same as the data pages from
executables in the frame_add_entry().