Project OS161: C1 - paging

Introduction

The project concerns the realisation of a virtual memory manager, which exploits demand paging and dynamic loading; its name is pagevm, as can be seen from one of the files in the project.

The files added to the DUMBVM configuration follow the instructions given in the project outline, to which is added the pagevm.c file (and its header file), containing basic memory management functions (detailed later).

The project was carried out in the variant called C1.1, with independent page tables for each process (further details are provided in the following sections).

Composition and division of workloads

The workload was divided neatly among the group members, using a shared repository on Github:

• Filippo Forte (s322788): address space and memory manager, modification to existing files in DUMBVM;

• Michele Cazzola (s323270): segments, page tables, statistics and abstraction for the TLB, with wrappers for existing functions;

• Leone Fabio (s330500): coremap and swapfile management.

Each member of the group managed the implementation of the modules independently, including taking care of the documentation and their own part of the report, after initially agreeing on the interface defined in the header files and the dependencies among them.

Communication mainly took place via weekly video calls lasting 2-3 hours each, during which the work done was discussed and the work to be done was planned.

Project architecture

The project was realised using a kind of layer architecture, with rare exceptions, whereby each module provides abstractions of a specific level, with (almost) unidirectional dependencies. The description of the modules follows their level of abstraction:

• at a high level, they interface with existing modules, including runprogram.c, loadelf.c, main.c, trap.c;

• at lower levels, they provide intermediate services: segment and page table are dependencies of the address space (one directly, the other indirectly), coremap is a dependency of several modules (including page table and higher-level modules), similarly to swapfile;

• others are auxiliary modules: the abstraction for the TLB is used in several modules to access its functionality, statistics are computed only by invoking interface functions.

Source code

Address space

Each process has an address space, which in our case is represented by three different segments: code, data and stack.

Data Structure

typedef struct {
    ps_t *seg_code;
    ps_t *seg_data;
    ps_t *seg_stack;
} addrspace_t ;

Implementation

The functions in addrspace.c are mainly high-level functions that create, manage and destroy address space by relying on lower-level functions implemented in segment.c. The corresponding prototypes are:

addrspace_t *as_create(void);
void as_destroy(addrspace_t *);
int as_copy(addrspace_t *src, addrspace_t **ret);
void as_activate(void);
void as_deactivate(void);
int as_prepare_load(addrspace_t *as);
int as_complete_load(addrspace_t *as);
int as_define_stack(addrspace_t *as, vaddr_t *initstackptr);
int as_define_region(addrspace_t *as,
                                   vaddr_t vaddr, size_t memsize,
                                   size_t file_size,
                                   off_t offset,
                                   struct vnode *v,
                                   int readable,
                                   int writeable,
                                   int executable);
ps_t *as_find_segment(addrspace_t *as, vaddr_t vaddr);
ps_t *as_find_segment_coarse(addrspace_t *as, vaddr_t vaddr);

Creation and destruction

The functions as_create and as_destroy have the task of allocating and freeing the memory space required to accommodate the data structure; as_destroy, in addition to destroying the three corresponding segments by means of seg_destroy, also has the task of closing the program file, which is left open to allow dynamic loading.

Copy and activation

The following functions are used:

• as_copy: it takes care of creating a new address space and copying the one received as a parameter. It is based on seg_copy.
• as_activate: it is called in runprogram immediately after creating and setting the process address space. In particular, its task is to invalidate the TLB entries.

Define

The functions as_define_region and as_define_stack are used to define code segment and data segment (for as_define_region) and stack segment (for as_define_stack). They essentially act as wrappers for the corresponding lower-level functions. What they add is the calculation of the size of the relevant segments, which is necessary for the functions defined in segment.c.

Find

There are two functions that, given an address space and a virtual address, make it possible to trace the relevant segment. They differ in the granularity of the search, they are as_find_segment and as_find_segment_coarse. Both functions have the task of calculating the start and end of the three segments (code, data and stack) and checking to which of these the given address belongs.

Compared to the as_find_segment function, the coarse granularity version, which operates at page level, is used to handle the problem of the virtual base address of a segment not being aligned with pages. However, this solution presents security risks: the page-alignment operation may erroneously consider some virtual addresses, which do not actually belong to any specific segment, as belonging to a segment.

Memory manager (pagevm)

In this module, many of the key functions implemented for this project are collected and utilised. The module is responsible for initialising and terminating the entire virtual memory management, as well as handling any memory faults.

Implementation

The functions implemented in this module are:

void vm_bootstrap(void);
void vm_shutdown(void);
int vm_fault(int faulttype, vaddr_t faultaddress);
void pagevm_can_sleep(void);

Initialisation and Termination

The functions vm_bootstrap and vm_shutdown have the task, respectively, of initialising and destroying all the ancillary structures required for virtual memory management. These structures include the coremap, the swap system, the TLB and the statistics collection system. These functions essentially act as containers that call the initialisation and termination routines of other modules:

• vm_bootstrap: it is called during system start-up to configure the entire virtual memory system. Among its main operations, it resets the victim pointer in the TLB, initialises the coremap, sets up the swap system and prepares the statistics management module.
• vm_shutdown: it is invoked during system shutdown to safely release used resources and print statistics on memory usage. It handles the shutdown of the swap system, the coremap and produces the output of the collected statistics.

Fault Management

The central function of this module is vm_fault, which deals with the handling of TLB misses. It is responsible for managing the creation of a new correspondence between the physical address and the virtual address in the TLB each time a TLB miss occurs. The operation of the function consists of the following steps:

1. Fault Check: the function starts by checking the type of fault (e.g. read-only, read, write) and ensuring that the current process and its address space are valid.
2. Physical Address Recovery: next, it retrieves the physical address corresponding to the virtual address where the fault occurred using the seg_get_paddr function.
3. Page Management: if the fault is caused by a page not yet allocated or a page previously swapped out, a new page is allocated. Depending on the type of fault, the low-level functions seg_add_pt_entry (to add the new page to the page table) or seg_swap_in (to load the page from the swapfile) are then called.
4. Updating the TLB: finally, using a round-robin algorithm, the victim to be replaced in the TLB is chosen and the TLB is updated with the new physical-virtual address match.

Segment

A process has an address space consisting of several segments, which are memory areas with a common semantics; in our case, there are three:

• code: contains the code of the executable, is read-only;
• data: contains global variables, is read-write;
• stack: contains the stack frames of the functions called during process execution, is read-write.

They are not necessarily contiguous in physical memory, so the solution adopted is the creation of a page table for each of them; the number of pages required is calculated downstream of reading the executable, except in the case of the stack, where it is constant.

Data structures

The data structure representing the individual segment is defined in segment.h and is as follows:

typedef struct {
    seg_permissions_t permissions;
    size_t seg_size_bytes;
    off_t file_offset;
    vaddr_t base_vaddr
    size_t num_pages;
    size_t seg_size_words;
    struct vnode *elf_vnode;
    pt_t *page_table;
} ps_t;

The fields have the following meaning:

• permissions: permissions associated with the segment, defined by the following enumerative type:

typedef enum {
    PAGE_RONLY, /* 0: read-only */.
    PAGE_RW, /* 1: read-write */
    PAGE_EXE, /* 2: executable */
    PAGE_STACK /* 3: stack */
} seg_permissions_t;

• seg_size_bytes: effective size of the segment in the executable, in bytes (filesize field in the ELF program header);
• file_offset: offset of the segment within the executable;
• base_vaddr: virtual initial address of the segment;
• num_pages: number of pages occupied by the segment in memory;
• seg_size_words: area of memory actually occupied by the segment and word-aligned, in bytes (memsize field in the ELF program header);
• elf_vnode: pointer to the vnode of the executable file to which the segment belongs;
• page_table: pointer to the page table associated with the segment

with the constraint that seg_size_bytes ≤ seg_size_words; furthermore, if the actual size of the segment is less than the memory it occupies, the residue is completely zeroed out.

Implementation

The functions of this module take care of segment-level operations, possibly acting as simple wrappers for lower-level functions. They are used within the modules addrspace or pagevm; the prototypes are as follows:

ps_t *seg_create(void);
int seg_define(
    ps_t *proc_seg, size_t seg_size_bytes, off_t file_offset,
    vaddr_t base_vaddr, size_t num_pages, size_t seg_size_words,
    struct vnode *elf_vnode, char read, char write, char execute
);
int seg_define_stack(ps_t *proc_seg, vaddr_t base_vaddr, size_t num_pages);
int seg_prepare(ps_t *proc_seg);
int seg_copy(ps_t *src, ps_t **dest);
paddr_t seg_get_paddr(ps_t *proc_seg, vaddr_t vaddr);
void seg_add_pt_entry(ps_t *proc_seg, vaddr_t vaddr, paddr_t paddr);
int seg_load_page(ps_t *proc_seg, vaddr_t vaddr, paddr_t paddr);
void seg_swap_out(ps_t *proc_seg, off_t swapfile_offset, vaddr_t vaddr);
void seg_swap_in(ps_t *proc_seg, vaddr_t vaddr, paddr_t paddr);
void seg_destroy(ps_t *proc_seg);

Creation and destruction

The following functions are used:

• seg_create: creates a new segment, allocating the necessary memory by means of kmalloc and resetting all fields, it is invoked at the creation of an address space;
• seg_destroy: destroys the given segment, also freeing the memory held by its page table, it is invoked upon destruction of the address space to which the segment belongs.

Definition, preparation and copy

The following functions are used:

• seg_define: defines the value of the fields of the given segment, using the parameters passed by the caller (i.e. as_define_region); they do not include information regarding the page table, which is defined later; this function is only used for code and data regions, not for the stack;

• seg_define_stack: like the previous one, but only used for the stack and invoked by as_define_stack:

  • it does not exist within the file, so offset and size in the file are zero fields;
  • the number of pages is defined by the constant PAGEVM_STACKPAGES, equal to 18;
  • the size occupied in memory (whole words) is directly related to the number of pages, according to the constant PAGE_SIZE;
  • the pointer to the vnode is NULL, since there is no need to keep this information: it is used, in the case of the other regions, to load pages into memory from the executable, which is not the case with the stack.

  It also allocates the page table, for consistency with the pattern followed in the DUMBVM configuration, in which the preparation function is not invoked on the stack segment.

• seg_prepare: used to allocate the page table relating to the code and data segments, invoked once for each of the segments, within as_prepare_load;

• seg_copy: performs the deep copy of a given segment into a target segment, invoked in as_copy; makes use of the similar function of the pt module for page table copying.

Address translation operations

The following functions are used:

• seg_get_paddr: obtains the physical address of a memory page, given the virtual address that caused a TLB miss; is invoked by vm_fault, following a TLB miss; directly uses the analogous function of the pt module;
• seg_add_pt_entry: adds the pair (virtual address, physical address), passed as parameters, to the page table using the analogous function of the pt module; it is invoked in vm_fault, following a TLB miss.

Loading (dynamic) of a page from the executable

The seg_load_page function is used, which constitutes a large part of the complexity of this module and allows the dynamic loading of program pages from the executable. Given the associated segment, the goal is to load the page associated with a virtual address (assuming it is neither memory resident nor swapped) into memory, to a physical address already appropriately derived (and passed as a parameter).

The requested page is represented by an index within the executable, calculated from the base_vaddr field of the segment; there are three distinct cases:

• first page: the requested page is the first page of the executable, whose offset within the page itself may not be zero (i.e., the virtual start address of the executable may not be page aligned) and, for simplicity, this offset is also maintained at the physical level, by loading the first page even if it is only partially occupied by the executable; there are two possible sub-cases:

  • the executable terminates in the current page;
  • the executable also occupies other pages,

  by which we determine how many bytes to read from the ELF file.

• last page: the requested page is the last page of the executable, so the loading takes place at a page aligned address, while the offset within the ELF file is calculated from the total number of pages and the offset within the first page; there are two possible sub-cases:

  • the executable terminates in the current page;
  • the executable terminates in a previous page, but the current page is still occupied: this is due to the fact that an executable file has a filesize (represented in ps_t by seg_size_bytes) and a memsize (represented in ps_t by seg_size_words) that may differ, with the former less than or equal to the latter; in this case, the occupied (but not valued) memory area must be reset,

  and, in the second case, no bytes are read from the ELF file.

• intermediate page: the loading is similar to the previous case, at the level of the offset in the ELF file and the physical address, but there are three possible sub-cases, regarding the number of bytes to be read:

  • the executable terminates in a previous page;
  • the executable terminates in the current page;
  • the executable also takes up subsequent pages,

  which are handled similarly to the two previous situations.

After defining the three loading parameters, viz:

• load_paddr: physical address in memory at which to load the page;
• load_len_bytes: number of bytes to be read;
• elf_offset: read start offset within the executable file,

resets the memory region designated to host the page, and then reads, following the pattern given by the operations:

• uio_kinit to set up the uio and iovec data structures;
• VOP_READ to perform the actual read operation.

They are also carried out:

• checks on the result of the read operation, to return any errors to the caller;
• check on the load_len_bytes parameter, for statistical purposes: if it is null, a page fault is recorded concerning a page that has been reset, otherwise it concerns a page to be loaded from the executable (and from disk).

Swapping operations

The following functions are used:

• seg_swap_out: marks as swapped out the page corresponding to the virtual address passed, by means of the analogous function of the pt module; it is invoked by getppage_user within the coremap module, within which the frame is physically swapped out;
• seg_swap_in: swaps in the frame corresponding to the virtual address provided, assuming the page was in a swapped state:
  • obtains the offset in the swapfile from the contents of the page table to the appropriate entry;
  • physically swaps in the frame, using the physical address provided;
  • uses the analogous function of the module pt to insert the correspondence (virtual address, physical address) in the appropriate entry.

Page table

As mentioned above, there are three page tables for each process, one for each of the three constituent segments; for this reason, no form of locking is required, as the page table is not a resource shared between different processes, but is specific to a single process.

Data structures

The data structure used to represent the page table is defined in pt.h and is as follows:

typedef struct {
    unsigned long num_pages;
    vaddr_t base_vaddr;
    paddr_t *page_buffer;
} pt_t;

whose fields have the following meaning:

• num_pages: number of pages within the page table;
• base_vaddr: initial virtual address of the page table, corresponds with the virtual base address of the segment and is used to calculate the page to which a requested virtual address belongs;
• page_buffer: vector of physical addresses of the represented pages, dynamically allocated when creating the page table.

Each page table entry (i.e. each individual page buffer element) can take on the following values:

• PT_EMPTY_ENTRY (0): since 0 is not a valid physical address (it is occupied by the kernel), it is used to indicate an empty entry, i.e. a page not yet loaded into memory;
• PT_SWAPPED_ENTRY (1) + swap offset: since 1 is not a valid physical address (valid physical address are multiple of 4, since CPU has 32-bit parallelism), it is used to indicate a page that has been swapped out; of the remaining 31 bits, the least significant are used to represent the page offset in the swapfile (it is 9 MB in size, so 24 bits would be sufficient);
• other values: in this case there is a valid physical address for the page, i.e. it is present in memory and a page fault has not occurred.

In order to be able to easily derive the index of the entry in the buffer from a virtual address, the buffer was constructed in such a way that each entry occupies an entire page: this occupies more memory, but greatly simplifies the performance of almost all operations carried out on the page table, since deriving the index from a virtual address is necessary in many of them.

Implementation

The page table management functions, as in the case of segments, are divided into different groups according to the task they perform. The prototypes, defined in the pt.h file, are as follows:

pt_t *pt_create(unsigned long num_pages, vaddr_t base_address);
int pt_copy(pt_t *src, pt_t **dest);
paddr_t pt_get_entry(pt_t *pt, vaddr_t vaddr);
void pt_add_entry(pt_t *pt, vaddr_t vaddr, paddr_t paddr);
void pt_clear_content(pt_t *pt);
void pt_swap_out(pt_t *pt, off_t swapfile_offset, vaddr_t vaddr);
void pt_swap_in(pt_t *pt, vaddr_t vaddr, paddr_t paddr);
off_t pt_get_swap_offset(pt_t *pt, vaddr_t vaddr);
void pt_destroy(pt_t *pt);

Creation and copy

The following functions are used:

• pt_create: allocates a new page table, given the number of pages and the virtual starting address, passed as parameters; the buffer used for paging is allocated and cleared, using the constant PT_EMPTY_ENTRY, since initially the page table is (conceptually) empty;
• pt_copy: copies the contents of a page table to a new one, allocated within the function; only used in the context of copying an address space, invoked by seg_copy.

Delete and destruction

The following functions are used:

• pt_clear_content: performs the side effects of deleting page table contents on swapfile and physical memory:

  • if an entry is swapped, it deletes it from the swapfile;
  • if an entry is in memory, it frees physical memory,

  and is used when destroying an address space, invoked by seg_destroy;

• pt_destroy: releases the memory resources held by the page table, including the buffers contained inside; like the previous one, it is used when destroying an address space and it is invoked by seg_destroy.

Address translation operations

The following functions are used:

• pt_get_entry: obtains the physical address of a page from the virtual address; in particular, it returns the constants:
  • PT_EMPTY_ENTRY if the virtual address belongs to a non-stored, non swapped page;
  • PT_SWAPPED_ENTRY if the virtual address belongs to a swapped page;
• pt_add_entry: inserts a physical address in the entry corresponding to the virtual address; both are passed as parameters and, in particular, the physical address is appropriately derived and supplied by the caller.

Swapping operations

The following functions are used:

• pt_swap_out: marks as swapped the entry corresponding to the supplied virtual address; using the constant PT_SWAPPED_MASK, it also stores the offset in the swapfile of the page to which the virtual address belongs;
• pt_swap_in: dual to the previous one, it is in fact only a wrapper for pt_add_entry, as it only requires the writing of a new physical address at the entry for the page to which the given virtual address belongs;
• pt_get_swap_offset: given a virtual address, it obtains the offset in the swapfile of the page to which it belongs, via the 31 most significant bits of the corresponding entry; it is used during the swap in operation, invoked by seg_swap_in.

TLB

The vm_tlb.c module (with its header file) contains an abstraction for managing and interfacing with the TLB: no data structures are added, but only functions that act as wrappers (or little more) to the already existing read/write functions, as well as the management of the replacement policy.

Implementation

The functions implemented in this module have the following prototypes:

void vm_tlb_invalidate_entries(void);
void vm_tlb_reset_current_victim(void);
uint64_t vm_tlb_peek_victim(void);
void vm_tlb_write(vaddr_t vaddr, paddr_t paddr, unsigned char dirty);

and perform the following tasks:

• vm_tlb_invalidate_entries: invalidates all TLB entries, using the appropriate masks defined in mips/tlb.h; it is invoked by as_activate, i.e. at the start of the process and at each context switching;
• vm_tlb_reset_current_victim: resets the position of the victim of the round-robin algorithm, used to manage the replacement, to 0; it is invoked by vm_bootstrap, during the bootstrap of the operating system;
• vm_tlb_peek_victim: performs a read in the TLB (by means of the tlb_read function), of the entry corresponding to the current victim; it is used to check whether the current victim is a valid entry or not, for statistical purposes, following TLB misses;
• vm_tlb_write: writes the pair (vaddr, paddr), within the entry corresponding to the current victim (which in turn may or may not be a valid entry), using the tlb_write function; the position of the victim is obtained through the vm_tlb_get_victim_round_robin function, which increments the victim's index by one unit (in a circular way), and then returns the current one, effectively performing the replacement algorithm; it is invoked following a TLB miss, in the absence of other errors. In addition, if the virtual address belongs to a page with write permission, the dirty bit is set, which (in the TLB of os161) indicates whether the corresponding entry contains the address of a writable page.

The functions tlb_read and tlb_write are implemented directly in assembly language and their prototypes are defined in the file mips/tlb.h.

Statistics

The vmstats.c module (with its header file) contains the data structures and functions for handling the memory manager statistics.

Data structures

Data structures are defined in vmstats.c, in order to be able to implement information hiding, accessing them only with externally exposed functions. They are:

bool vmstats_active = false;
struct spinlock vmstats_lock;

unsigned int vmstats_counts[VMSTATS_NUM];

static const char *vmstats_names[VMSTATS_NUM] = {
    "TLB faults", /* TLB misses */
    "TLB faults with free", /* TLB misses with no replacement */
    "TLB faults with replace", /* TLB misses with replace */
    "TLB invalidations", /* TLB invalidations (number of times) */
    "TLB reloads", /* TLB misses for pages stored in memory */
    "Page faults (zeroed)", /* TLB misses requiring zero-filled page */
    "Page faults (disk)", /* TLB misses requiring load from disk */
    "Page faults from ELF", /* Page faults requiring load from ELF */.
    "Page faults from swapfile", /* Page faults requiring load from swapfile */
    "Swapfile writes" /* Page faults requiring write on swapfile */
};

in order:

• vmstats_active: flag to indicate whether the module is active (i.e. the counters have been appropriately initialised);
• vmstats_lock: spinlock for mutually exclusive access, necessary as this module (with its data structures) is shared by all processes and requires the increments to be independent;
• vmstats_counts: vector of counters, one for each statistic;
• vmstats_names: vector of strings, containing the names of the statistics to be collected, useful when printing.

In the header file (vmstats.h) they are defined:

#define VMSTATS_NUM 10

enum vmstats_counters {
    VMSTAT_TLB_MISS,
    VMSTAT_TLB_MISS_FREE,
    VMSTAT_TLB_MISS_REPLACE,
    VMSTAT_TLB_INVALIDATION,
    VMSTAT_TLB_RELOAD,
    VMSTAT_PAGE_FAULT_ZERO,
    VMSTAT_PAGE_FAULT_DISK,
    VMSTAT_PAGE_FAULT_ELF,
    VMSTAT_PAGE_FAULT_SWAPFILE,
    VMSTAT_SWAPFILE_WRITE
};

where:

• VMSTATS_NUM: the number of statistics to be collected;
• vmstats_counters: the names of the statistics to be collected, used as an index in vmstats_counts and vmstats_names, exposed externally for use in the invocation of the increment function.

Implementation

The functions implemented in this module have the following prototypes:

void vmstats_init(void);    
void vmstats_increment(unsigned int stat_index);
void vmstats_show(void);

They perform the following tasks:

• vmstats_init: initialises the vmstats_active flag, after resetting all counters in vmstats_counts; it is invoked at the bootstrap of the virtual memory manager;
• vmstats_increment: increments the statistics associated with the index provided as a parameter by one unit;
• vmstats_show: prints, for each statistic, the associated count value, displaying any warning messages if the relationships among the statistics are not respected; it is invoked on shutdown of the virtual memory manager.

Each operation carried out within the initialisation and increment functions is protected by spinlocks, as it requires mutually exclusive access, since writes are made to shared data; the print function only performs reads, and therefore does not require the use of any form of locking.

Coremap

The coremap is a fundamental component for managing physical memory within the virtual memory system. This data structure keeps track of the state of each page in physical memory, allowing the system to know which pages are currently in use, which are free and which need to be replaced or retrieved from disk. The coremap manages both the pages used by the kernel and those used by user processes, facilitating dynamic memory management according to the system's needs.

Data structures

The data structure used to manage the coremap is defined in coremap.h and is as follows:

struct coremap_entry {
    coremap_entry_state entry_type; 
    unsigned long allocation_size;
  
    unsigned long previous_allocated;   
    unsigned long next_allocated;

    vaddr_t virtual_address;                
    addrspace_t *address_space;               
};

This structure serves to represent the state and properties of a single page of physical memory. Each field has a specific role:

• entry_type: indicates the current state of the page, using the enumerative type coremap_entry_state. It may take the state:
  • COREMAP_BUSY_KERNEL: the page is allocated for kernel use.
  • COREMAP_BUSY_USER: the page is allocated for user use.
  • COREMAP_UNTRACKED: the page is not yet managed by the coremap.
  • COREMAP_FREED: the page was freed and can be reused.
• allocation_size: specifies the size of the allocation, i.e. the number of contiguous pages allocated. This is particularly relevant for kernel allocations, which may require blocks of contiguous pages.
• previous_allocated and next_allocated: act as pointers to a linked list of allocated pages. They are used to implement a FIFO (First-In-First-Out) strategy for page replacement, facilitating the tracking of pages in order of allocation.
• virtual_address: stores the virtual address associated with the page. It is particularly important for user pages, where the system must map the virtual address of the user to the corresponding physical page.
• address_space: points to the address space to which the page is allocated. It is used to identify which user process is using the page.

Implementation

The coremap implementation is fundamental for memory management within the operating system. The following prototypes are defined to handle coremap initialisation, allocation, deallocation and shutdown:

void coremap_init(void);            
void coremap_shutdown(void);        
vaddr_t alloc_kpages(unsigned npages); 
void free_kpages(vaddr_t addr);     
paddr_t alloc_user_page(vaddr_t vaddr); 
void free_user_page(paddr_t paddr); 

Initialisation and Termination

The following functions are used:

• coremap_init(): it initialises the coremap, allocating the memory required to manage all available physical memory pages. It sets each entry initially as COREMAP_UNTRACKED, indicating that the pages are not yet managed.
• coremap_shutdown(): it is responsible for shutting down and cleaning the coremap, freeing allocated memory and deactivating the coremap when the system no longer needs it.

Page Allocation and Deallocation - Kernel

The following functions are used:

• alloc_kpages(unsigned npages): it handles page allocation for the kernel. It attempts to allocate contiguous npages, returning the virtual address of the first block. If there are not enough free pages, the system attempts to "steal" memory by calling the ram_stealmem() function, provided by default by os161 in ram.c, which returns the physical address of a frame that has not been used yet.
• free_kpages(vaddr_t addr): it frees the pages allocated to the kernel, marking them as COREMAP_FREED in the coremap, making them available for future allocation.

Page Allocation and Deallocation - User Processes

The following functions are used:

• alloc_user_page(vaddr_t vaddr): it manages page allocation for user processes. It first searches for free pages and, if necessary, replaces an existing page using a FIFO replacement strategy. If a page is replaced, the function interacts with the swapfile to manage the transfer of the victim page to disk. Furthermore, it is crucial from an implementation point of view to identify the segment that contains the page selected as the victim. This step is essential to mark as swapped the page table entry corresponding to the virtual address and to save the offset of the swapfile where the page was stored. The segment search is performed using:

  ps_t *as_find_segment_coarse(addrspace_t *as, vaddr_t vaddr)

  defined in addrspace.h.

• free_user_page(paddr_t paddr): it frees pages allocated to user processes, removing the page from the allocation queue and marking it as COREMAP_FREED in the coremap.

Swapfile

The swapfile is an essential component to extend the physical memory capacity of the system, allowing the operating system to handle more processes than can be contained in the available physical memory. When the RAM memory is full, the swapfile allows pages to be temporarily moved to disk, freeing memory for other processes.

Implementation

The swapfile implementation provides various functions for managing swap space and transferring pages between physical memory and disk. The swapfile is limited to 9 MB (as defined in swapfile.h) and if more swap space is requested at runtime, the system panics indicating the violation. The prototypes of the main functions are:

int swap_init(void);
int swap_out(paddr_t page_paddr, off_t *ret_offset);
int swap_in(paddr_t page_paddr, off_t swap_offset);
void swap_free(off_t swap_offset);
void swap_shutdown(void);

Initialisation

Function swap_init() is used: it initialises the swapfile and the bitmap useful to track the utilisation status of pages in the swap file.

Swapping operations

The following functions are used:

• swap_out(paddr_t page_paddr, off_t *ret_offset): it writes a page from physical memory to the swap file. The parameter page_paddr indicates the physical address of the page to be moved to disk. The function returns the offset in the swap file where the page was stored, allowing it to be retrieved later.
• swap_in(paddr_t page_paddr, off_t swap_offset): it reads a page from the swap file and restores it to physical memory. The parameter swap_offset indicates the offset in the swap file from which to retrieve the page.

Cleaning and Termination

The following functions are used:

• swap_free(off_t swap_offset): it frees the space in the swap file associated with a page that is no longer needed. The parameter swap_offset specifies the offset of the page in the swap file to be freed.
• swap_shutdown(): it closes and releases the resources associated with the swapfile when the system no longer needs them. It closes the swapfile and releases the memory used by the bitmap.

Modifications to other files

Below are the (minor, but necessary) changes made to other os161 kernel files, which already existed in the source version.

trap.c

Within the kill_curthread function, in the case of:

• TLB misses in read/write;
• TLB hit in case of write request (memory store) on read-only memory segment,

an error printout is executed, followed by an invocation to the system call sys__exit, to perform the graceful termination of the process, freeing the allocated resources; this usually occurs following the return of a non-zero value by the vm_fault function.

In this way, it is possible to avoid an operating system panic, in case of error, allowing either the execution of further tests (or the repetition of the same one); furthermore, this allows the operating system to be terminated correctly (with the q command), tracking statistics for the faulter test.

This change is only valid when the conditional option OPT_PAGING is enabled.

runprogram.c

In this implementation, a modification with a conditional flag (using #if !OPT_PAGING) was added to determine whether the file remains open or is closed immediately after loading the executable. If the paging option (OPT_PAGING) is disabled, the file is closed immediately. Otherwise, the file remains open to be closed later during address space destruction by as_destroy. This change was introduced to support dynamic loading, which requires continuous access to the executable file during program execution.

loadelf.c

In this implementation, the code has been modified to support dynamic loading, which allows pages of the executable to be loaded into memory only when the conditional option OPT_PAGING is enabled. In this case, the function as_define_region is called with additional parameters which include file offset, size in memory, file size and pointer to the file. This allows handling memory regions in a way that supports paging on demand.

The function as_prepare_load is called to prepare the loading of the program into the address space. However, if on-demand paging is active, the actual loading of the segment pages in load_segment is not performed at this stage.

main.c

Within the boot function, the function vm_shutdown is invoked, in order to perform the termination of the virtual memory manager allowing, among other things, the display of statistics on the terminal; this invocation only occurs when the conditional option OPT_PAGING is enabled.

Test

In order to verify the correct functioning of the system, we used the tests already present within os161, choosing those suitable for what was developed:

• palin: performs a simple check on a string of 8000 characters, without stressing the VM; it does not cause neither TLB replacements nor page swaps;
• matmult: performs a matrix product (checking the result against the expected one), taking up a lot of memory space and putting more stress on the VM than the previous one;
• sort: sorts a large array using the quick sort algorithm;
• zero: checks that the memory areas to be zeroed in the allocation are correctly zeroed (the check performed on the syscall sbrk is ignored);
• faulter: verifies that illegal access to a memory area causes the program to be interrupted;
• ctest: performs the traversal of a linked list;
• huge: allocates and manipulates a large array.

To ensure that the basic functions of the kernel were already correctly implemented, we run the following kernel tests:

• at: arrays handling;
• at2: like the previous one, but with a larger array;
• bt: bitmap management;
• km1: verification of kmalloc;
• km2: as the previous one, but under stress conditions.

Below are the statistics recorded for each test: each was run only once, and then the system was shut down to collect its statistics.

Name test	TLB faults	TLB faults (free)	TLB faults (replace)	TLB invalidations	TLB reloads	Page faults (zeroed)	Page faults (disk)	Page faults (ELF)	Page faults (swapfile)	Swapfile writes
palin	13889	13889	0	7789	13884	1	4	4	0	0
matmult	4342	4323	19	1222	3534	380	428	3	425	733
sort	7052	7014	38	3144	5316	289	1447	4	1443	1661
zero	143	143	0	139	137	3	3	3	0	0
faulter	61	61	0	132	58	2	1	1	0	0
ctest	248591	248579	12	249633	123627	257	124707	3	124704	124889
huge	7459	7441	18	6752	3880	512	3067	3	3064	3506