ucore lab3

practice 1： Map physical pages to unmapped addresses （ You need to program ）

This experiment is required to be completed do_pgfault function , To map physical pages to unmapped addresses .
To be specific , When the paging mechanism is started , If the physical page frame corresponding to the virtual address of an instruction or data is not in memory or the access type is wrong （ For example, write a read-only page or user mode program to access kernel mode data, etc ）, It will happen
Page error exception . The main reasons for page exceptions are :

1. The target page does not exist （ Page table entries are all 0, That is, the mapping between the linear address and the physical address has not been established or has been revoked ）;
2. The corresponding physical page is not in memory （ Page table entry is not empty , but Present Sign a =0, For example swap Partition or disk file ）;
3. Access permissions do not match （ At this time, the page table item P sign =1, For example, trying to write a read-only page ）.

When one of the above occurs , Then there will be a page page fault(#PF) abnormal . The linear address generating the exception is stored in
CR2 in , And will page fault The generation type of is saved in error code So our do_pgfault The idea of function is obvious .do_pgfault() Function from CR2 Register to get the virtual address of the page error exception , according to error code To find out whether the virtual address is in a certain VMA Within the address range of , Then assign it a physical page .

stay kern/init/init.c The initialization of several parts is added in ：

vmm_init();                 // init virtual memory management
ide_init();                 // init ide devices
swap_init();                // init swap

The first function vmm_init Is to check our practice 1 Whether the correct implementation of .

ide_init and swap_init Is for practice 2 To prepare the . Due to the implementation of page replacement algorithm, there is a problem of reading and writing hard disk data blocks , therefore ide_init Is to complete the hard disk for page in and out （ abbreviation swap Hard disk ） Initialization work . complete ide_init After the function ,ucore You can do this swap The hard disk has been read and written .swap_init The function first establishes swap_manager,swap_manager It is the main function module to complete the page replacement process , It includes the implementation of page replacement algorithm .

page_fault The function doesn't know what is “ legal ” The virtual page of , as a result of ucore There is also a lack of data structure to describe this kind of data that is not in physical memory “ legal ” Virtual page .** So ucore Through establishment mm_struct and vma_struct data structure , It describes ucore Simulate the legal memory space required by the application to run .** When accessing memory, a page fault When abnormal , How to get access to memory （ Read or write ） And the specific virtual memory address , such ucore You can query this address , See if it belongs to vma_struct The legal address range described in the data structure , If in , You can request page adjustment according to specific conditions / Page in / out processing （ This is practice 2 The part involved ）; If not , False report .

there vma It describes the application's response to virtual memory “ demand ” The variable of , as follows ：

// the virtual continuous memory area(vma)
//  Virtual contiguous memory area , Describes the application's impact on virtual memory “ demand ” Data structure of 
struct vma_struct {
    
    struct mm_struct *vm_mm; // the set of vma using the same PDT
  
    // vm_start and vm_end Describes the starting and ending positions of a virtual memory space with consecutive addresses ,vma There is no intersection between the address spaces 
    uintptr_t vm_start;      // start addr of vma 
    uintptr_t vm_end;        // end addr of vma
  
    uint32_t vm_flags;       // flags of vma  Properties of virtual memory space , Include ： read-only 、 read-write 、 Executable 
    list_entry_t list_link;  // linear list link which sorted by start addr of vma  List nodes sorted by starting address 
};

mm_struct The structure is as follows ：

// the control struct for a set of vma using the same PDT
//  For all “ Belong to the same page table of contents ” Virtual memory space of 
struct mm_struct {
    
    list_entry_t mmap_list;        // linear list link which sorted by start addr of vma  All virtual memory spaces belonging to the same page directory table are linked 
    struct vma_struct *mmap_cache; // current accessed vma, used for speed purpose  Virtual memory space currently used , Due to the principle of program locality , Can speed up access 
    pde_t *pgdir;                  // the PDT of these vma  Maintained page tables 
    int map_count;                 // the count of these vma
    void *sm_priv;                   // the private data for swap manager
};

The resulting do_pgfault Function as follows ：

/* do_pgfault - interrupt handler to process the page fault execption  An interrupt handler that handles page missing interrupt exceptions  * @mm : the control struct for a set of vma using the same PDT  For those with the same page table of contents vma Control structure of  * @error_code : the error code recorded in trapframe->tf_err which is set by x86 hardware  Recorded in the trapframe->tf_err Error code in , Set by hardware  * @addr : the addr which causes a memory access exception, (the contents of the CR2 register)  The address that caused the memory access exception （CR2 The contents of the register ） * * CALL GRAPH: trap--> trap_dispatch-->pgfault_handler-->do_pgfault * The processor provides ucore's do_pgfault function with two items of information to aid in diagnosing * the exception and recovering from it.  The processor provides two messages to do_fault Function handling exception  * (1) The contents of the CR2 register. The processor loads the CR2 register with the * 32-bit linear address that generated the exception. The do_pgfault fun can * use this address to locate the corresponding page directory and page-table * entries. * CR2 The contents of the register . The processor will cause an interrupt 32 Bit linear address is loaded into CR2 In the register , Function can use this address to locate the corresponding page directory 、 Page table item  * (2) An error code on the kernel stack. The error code for a page fault has a format different from * that for other exceptions. The error code tells the exception handler three things: *  There is an error code in the kernel stack . The error codes of page missing exceptions are different from those of other exceptions , It tells the processor three things ： * -- The P flag (bit 0) indicates whether the exception was due to a not-present page (0) * or to either an access rights violation or the use of a reserved bit (1). * P position , Indicates whether the page is not in memory or access rights have been violated / Reserved bit is 1 * -- The W/R flag (bit 1) indicates whether the memory access that caused the exception * was a read (0) or write (1). * W/R position , Indicate whether the exception is caused by reading or writing  * -- The U/S flag (bit 2) indicates whether the processor was executing at user mode (1) * or supervisor mode (0) at the time of the exception. * U/S position , Indicate whether the machine is in kernel state or user state when an exception occurs  */
int
do_pgfault(struct mm_struct *mm, uint32_t error_code, uintptr_t addr) {
    
    int ret = -E_INVAL;
    //try to find a vma which include addr
    struct vma_struct *vma = find_vma(mm, addr);    // find a vma (vma->vm_start <= addr <= vma_vm_end)

    pgfault_num++;
    //If the addr is in the range of a mm's vma?
    if (vma == NULL || vma->vm_start > addr) {
      // vma Does not correspond to the address 
        cprintf("not valid addr %x, and can not find it in vma\n", addr);
        goto failed;
    }
    //check the error_code
    switch (error_code & 3) {
       // error code The lower two bits are read and write bits respectively / Existential bit , Here are some exceptions 
    default:
            /* error code flag : default is 3 ( W/R=1, P=1): write, present */
            //  Write exception , Pages exist in memory 
    case 2: /* error code flag : (W/R=1, P=0): write, not present */    //  Write , Page is not in memory 
        if (!(vma->vm_flags & VM_WRITE)) {
     //  The page is set to be non writable 
            cprintf("do_pgfault failed: error code flag = write AND not present, but the addr's vma cannot write\n");
            goto failed;
        }
        break;
    case 1: /* error code flag : (W/R=0, P=1): read, present */ //  read , Page in memory 
        cprintf("do_pgfault failed: error code flag = read AND present\n");
        goto failed;
    case 0: /* error code flag : (W/R=0, P=0): read, not present */ //  read , Page is not in memory 
        if (!(vma->vm_flags & (VM_READ | VM_EXEC))) {
       //  Pages cannot be read / perform 
            cprintf("do_pgfault failed: error code flag = read AND not present, but the addr's vma cannot read or exec\n");
            goto failed;
        }
    }
    /* IF (write an existed addr ) OR * (write an non_existed addr && addr is writable) OR * (read an non_existed addr && addr is readable) *  If it is   Write an existing address / Write a nonexistent address, but the address can be written / Read a non-existent address and the address is readable   Continued to  * THEN * continue process */
    uint32_t perm = PTE_U;
    if (vma->vm_flags & VM_WRITE) {
     //  If vma Page writable is marked in 
        perm |= PTE_W;  //  Set permissions to writable 
    }
    addr = ROUNDDOWN(addr, PGSIZE); // Round down to page boundary 

    ret = -E_NO_MEM;

    pte_t *ptep=NULL;   // page table entry pointer
    /*LAB3 EXERCISE 1: YOUR CODE * Maybe you want help comment, BELOW comments can help you finish the code * * Some Useful MACROs and DEFINEs, you can use them in below implementation. * MACROs or Functions: * get_pte : get an pte and return the kernel virtual address of this pte for la * if the PT containing this pte doesn't exist, alloc a page for PT (notice the 3th parameter '1') *  Get a linear address la The address of the page entry of , If the page table containing the page does not exist , Assign a physical page to the page table  * pgdir_alloc_page : call alloc_page & page_insert functions to allocate a page size memory & setup * an addr map pa<--->la with linear address la and the PDT pgdir *  Allocate one  * DEFINES: * VM_WRITE : If vma->vm_flags & VM_WRITE == 1/0, then the vma is writable/non writable * PTE_W 0x002 // page table/directory entry flags bit : Writeable * PTE_U 0x004 // page table/directory entry flags bit : User can access * VARIABLES: * mm->pgdir : the PDT of these vma * */
    /*LAB3 EXERCISE 1: YOUR CODE*/
    //(1) try to find a pte, if pte's PT(Page Table) isn't existed, then create a PT.
    if ((ptep = get_pte(mm->pgdir, addr, 1)) == NULL) {
     //  Get address addr Page entry for failed 
        cprintf("get_pte in do_pgfault failed\n");
        goto failed;
    }
    if (*ptep == 0) {
       // Logical address addr The corresponding physical page does not exist 
        //(2) if the phy addr doesn't exist, then alloc a page & map the phy addr with logical addr
        //  If the physical address does not exist , Assign a page , Map logical addresses to physical addresses 
        if (pgdir_alloc_page(mm->pgdir, addr, perm) == NULL) {
    
            cprintf("pgdir_alloc_page in do_pgfault failed\n");
            goto failed;
        }
    }
    else {
      //  Page table entry is not empty , You can try to switch to a page 
    /*LAB3 EXERCISE 2: YOUR CODE * Now we think this pte is a swap entry, we should load data from disk to a page with phy addr, * and map the phy addr with logical addr, trigger swap manager to record the access situation of this page. *  Page table entry is not empty , Is one that should be carried out swap The item , You should read a page from your hard disk  * Some Useful MACROs and DEFINEs, you can use them in below implementation. * MACROs or Functions: * swap_in(mm, addr, &page) : alloc a memory page, then according to the swap entry in PTE for addr, * find the addr of disk page, read the content of disk page into this memroy page *  Allocate a storage page , according to swap Item to find the page on the hard disk , read out  * page_insert ： build the map of phy addr of an Page with the linear addr la  Map logical addresses to physical addresses  * swap_map_swappable ： set the page swappable  Set the page to be swap Of  */
        if(swap_init_ok) {
    
            struct Page *page=NULL;
            //(1）According to the mm AND addr, try to load the content of right disk page into the memory which page managed.
            //  According to the given mm_struct And address addr, Read the corresponding physical page into memory 
            if ((ret = swap_in(mm, addr, &page)) != 0) {
    
                cprintf("swap_in in do_pgfault failed\n");
                goto failed;
            }
            page_insert(mm->pgdir, page, addr, perm);   //  Establish the correspondence between the virtual address and the physical address 
            swap_map_swappable(mm, addr, page, 1);  //  Make this page exchangeable 
            page->pra_vaddr = addr; //  Set the virtual address of the page 
        }
        else {
    
            cprintf("no swap_init_ok but ptep is %x, failed\n",*ptep);
            goto failed;
        }
   }
    // try to find a pte, if pte's PT(Page Table) doesn't existed, then create a PT.
    // (notice the 3th parameter '1')
    if ((ptep = get_pte(mm->pgdir, addr, 1)) == NULL) {
    
        cprintf("get_pte in do_pgfault failed\n");
        goto failed;
    }
    
    if (*ptep == 0) {
     // if the phy addr isn't exist, then alloc a page & map the phy addr with logical addr
        if (pgdir_alloc_page(mm->pgdir, addr, perm) == NULL) {
    
            cprintf("pgdir_alloc_page in do_pgfault failed\n");
            goto failed;
        }
    }
    else {
     // if this pte is a swap entry, then load data from disk to a page with phy addr
           // and call page_insert to map the phy addr with logical addr
        if(swap_init_ok) {
    
            struct Page *page=NULL;
            if ((ret = swap_in(mm, addr, &page)) != 0) {
    
                cprintf("swap_in in do_pgfault failed\n");
                goto failed;
            }
            page_insert(mm->pgdir, page, addr, perm);
            swap_map_swappable(mm, addr, page, 1);
            page->pra_vaddr = addr;
        }
        else {
    
            cprintf("no swap_init_ok but ptep is %x, failed\n",*ptep);
            goto failed;
        }
   }
   ret = 0;
failed:
    return ret;
}

practice 2： Supplementary completion is based on FIFO Page replacement algorithm （ You need to program ）

Page replacement algorithm and principle

The simplest page replacement algorithm is fifo, But it is not efficient , And there are belady The phenomenon （ Increasing the number of pages to a process increases the number of page misses ）; The most commonly used are improved clock Algorithm , It doesn't just consider whether the page is accessed , And consider whether the page has been modified .

A basic principle of page changing is ： Not all physical pages can be exchanged , Only pages mapped to user space and directly accessed by user programs can be exchanged , The pages of kernel space directly used by the kernel cannot be swapped out .

The correspondence between virtual memory pages and hard disk sectors

When one PTE When used to describe a physical page in a general sense , Obviously it should maintain various permissions and mapping relationships , And there should be PTE_P Mark ; But when it is used to describe a replaced physical page , It is used to maintain the physical page and swap The mapping relationship of sectors on the disk , And it's time to PTE It should not be done by MMU Interpret it as a physical page map ( That is, no PTE_P Mark ), At the same time, the corresponding authority is entrusted to mm_struct To maintain the , When accessing the memory address located on the page , Inevitably lead to page fault, then ucore Can be based on PTE Description of the swap Item to rebuild the corresponding physical page , And reset according to the permissions described by the virtual memory PTE Enable memory access to continue normally .

The timing of swap in and swap out

check_mm_struct The data structure variable represents the current ucore A collection of all virtual memory spaces considered legitimate , and mm Each of the vma It represents a legal virtual space with continuous addresses . When ucore Or when the page where the application access address is located is not in memory , It will produce page fault abnormal , Cause a call do_pgfault function , This function will judge that the address generating the access exception belongs to check_mm_struct Some vma Represents the legal virtual address space , And stored on the hard disk swap In file （ That is, the corresponding PTE The height of 24 Not for 0, And the lowest bit is 0）, Is the time to perform page swapping , Will call swap_in Function to complete page switch in .

The timing of changing pages is relatively complicated , There are different opportunities for different strategies .ucore At present, there are roughly two strategies , namely Active swap out strategy and Negative swap out strategy . An active swap out strategy means that the operating system periodically （ Or when the system is not busy ） Take the initiative to think that “ Not commonly used ” Page out to the hard disk , To ensure that there are always a certain number of free pages in the system , So when you need a free page , Basically, it can meet the demand in time ; A negative swap out strategy is , Just when trying to get free pages , It is found that there are currently no free physical pages available for allocation , Only then did I begin to search “ Not commonly used ” page , And swap one or more of these pages out to the hard disk .

Relevant data structure

Add two members to the data structure that represents the physical page ：

struct Page {
      
……   
list_entry_t pra_page_link;   // It is used to construct a linked list sorted by the first access time of the page 
uintptr_t pra_vaddr;   // Used to record the starting address of the virtual page corresponding to this physical page 
};

Class framework of page replacement algorithm swap_manager:

struct swap_manager
{
    
     const char *name;
     /* Global initialization for the swap manager */
     int (*init)            (void);
     /* Initialize the priv data inside mm_struct */
     int (*init_mm)         (struct mm_struct *mm);
     /* Called when tick interrupt occured */
     int (*tick_event)      (struct mm_struct *mm);
     /* Called when map a swappable page into the mm_struct */
     int (*map_swappable)   (struct mm_struct *mm, uintptr_t addr, struct Page *page, int swap_in);
     /* When a page is marked as shared, this routine is called to * delete the addr entry from the swap manager */
     int (*set_unswappable) (struct mm_struct *mm, uintptr_t addr);
     /* Try to swap out a page, return then victim */
     int (*swap_out_victim) (struct mm_struct *mm, struct Page **ptr_page, int in_tick);
     /* check the page relpacement algorithm */
     int (*check_swap)(void);     
};

The two key function pointers here are map_swappable and swap_out_vistim, The previous function is used for Record page access related properties , The latter function is used for Pick the pages that need to be swapped out . Obviously, the second function depends on the page access recorded by the first function .tick_event Function pointers are also important , Interrupt generated in combination with timing , Can achieve a positive page change strategy .

The implementation of these two functions is as follows ：

/* * (3)_fifo_map_swappable: According FIFO PRA, we should link the most recent arrival page at the back of pra_list_head queue *  Add the most recently used pages to the order queue maintained by the algorithm  */
static int
_fifo_map_swappable(struct mm_struct *mm, uintptr_t addr, struct Page *page, int swap_in)
{
    
    list_entry_t *head=(list_entry_t*) mm->sm_priv;
    list_entry_t *entry=&(page->pra_page_link);
 
    assert(entry != NULL && head != NULL);
    //record the page access situlation
    /*LAB3 EXERCISE 2: YOUR CODE*/ 
    //(1)link the most recent arrival page at the back of the pra_list_head qeueue.
    list_add(head, entry);  // Add the most recently used pages to the end of the sequence 
    return 0;
}

/* * (4)_fifo_swap_out_victim: According FIFO PRA, we should unlink the earliest arrival page in front of pra_list_head qeueue, * then assign the value of *ptr_page to the addr of this page. *  Query which page needs to be swapped out  */
static int
_fifo_swap_out_victim(struct mm_struct *mm, struct Page ** ptr_page, int in_tick)
{
    
     list_entry_t *head=(list_entry_t*) mm->sm_priv;
         assert(head != NULL);
     assert(in_tick==0);
     /* Select the victim */
     /*LAB3 EXERCISE 2: YOUR CODE*/ 
     //(1) unlink the earliest arrival page in front of pra_list_head qeueue
     //(2) assign the value of *ptr_page to the addr of this page
     /* Select the tail */
     list_entry_t *le = head->prev; // use le Indicates the page that needs to be swapped out 
     assert(head!=le);
     struct Page *p = le2page(le, pra_page_link);   //le2page The macro can obtain the corresponding... According to the linked list elements Page The pointer p
     list_del(le);  // Remove the oldest page from the queue 
     assert(p !=NULL);
     *ptr_page = p; // Store the address of this page in ptr_page in 
     return 0;
}