lab3 — 虚拟内存管理

前置知识

虚拟存储、页面置换算法、中断机制。

改动点

相比于 lab2 源代码，lab3 主要是添加部分代码以实现虚拟存储功能，仅见的改动点在于页描述结构 page 和 alloc_pages 函数的具体实现，两者源码如下：

struct Page {
    int ref;                        
    uint32_t flags;                 
    unsigned int property;          
    list_entry_t page_link;         
    list_entry_t pra_page_link;     // 链接属于同一程序的物理页面
    uintptr_t pra_vaddr;            // 指明此物理页面对应的虚拟地址
};


struct Page * alloc_pages(size_t n) {
    struct Page *page=NULL;
    bool intr_flag;
    
    while (1)
    {
         local_intr_save(intr_flag);
         {
              page = pmm_manager->alloc_pages(n);
         }
         local_intr_restore(intr_flag);

         // 如果因空闲页不够而导致的内存分配失败，且此时已经开启 swap，则其会基于相关替换算法而自动换出某些页面，以满足分配要求(此处要求 n > 1，表明只要请求页面大于 1，分配失败时不会尝试进行页面替换)。
         if (page != NULL || n > 1 || swap_init_ok == 0) break;
         
         extern struct mm_struct *check_mm_struct;
         
         swap_out(check_mm_struct, n, 0);
    }
    return page;
}

练习一

此练习用于了解页面替换算法 FIFO 的具体实现。

对于虚拟内存管理而言，另外涉及两大数据结构：

struct vma_struct {
    struct mm_struct *vm_mm; // 指向管理此 vma 的 mm
    uintptr_t vm_start;      // vma 的起始虚拟地址(包含)      
    uintptr_t vm_end;        // vma 的终止虚拟地址(不包含)
    uint32_t vm_flags;       // vma 权限标志信息(可读、可写、可执行)
    list_entry_t list_link;  // 用于将属于同一程序的 vma 链接起来
};

struct mm_struct {
    list_entry_t mmap_list;        // 指向某程序的 vma 集
    struct vma_struct *mmap_cache; // 当前访问的 vma
    pde_t *pgdir;                  // 该程序对应的页目录表
    int map_count;                 // 指明某程序的 vma 总数
    void *sm_priv;                 // swap manager(主要指代页面替换算法的具体实现) 的隐私信息。ucore 之中，使用 pra_list_head 进行填充
};

为实现 FIFO，我们需要使用 list_entry_t pra_list_head 所指链表来有序 (对于 FIFO 而言，指代页面被分配的时间) 保存某程序所分配的物理页面集 (集内页面使用 Page.pra_page_link 进行链接)。

当分配某程序物理页面后，需要将刚分配的页面放置于链首以显式更新 pra_list_head 链表；当需要选择待替换物理页面时，直接选择链尾页面即可。

被替换的物理页面会被存放至 swap 分区内部 (此称为交换技术)。因为此时 PTE 表项无效，因此 ucore 使用此存放该页面所在位置的起始扇区编号。

因为 ucore 将物理页面线性映射至 swap 对应扇区，因此其交换技术的实现十分简单。而实际系统之中，这种映射实现是比较复杂的。

基于 FIFO 实现思想及上述数据结构，很容易写出相关代码，故不再赘述。

练习二

此练习用于了解并实现缺页中断的异常处理程序。

缺页中断的异常处理程序的具体调用流程如下：__alltraps –> trap –> trap_dispatch –> pgfault_handler –>do_pgfault。这里直接基于 do_pgfault 的实现，说明如何处理缺页中断。

// mm 指代当前运行程序的虚拟内存管理结构，error_code 指代硬件设置的异常码，addr 指代引发缺页中断的虚拟地址。
int do_pgfault(struct mm_struct *mm, uint32_t error_code, uintptr_t addr) {
    int ret = -E_INVAL;
    // 判断 addr 是否属于当前运行程序的合法地址。
    struct vma_struct *vma = find_vma(mm, addr);

    pgfault_num++;
    // 如果该地址不合法，则直接返回即可。
    if (vma == NULL || vma->vm_start > addr) {
        goto failed;
    }
    
    // 详细判断硬件设置的 error_code (其第 0 位指代中断是否由页面不存在而引起，第 1 位指代中断是否由写操作引起，第 2 位指代当前是否处于用户模式)，对于因权限不满足的情况，直接返回。
    switch (error_code & 3) {
    default:
            
    case 2: 
        if (!(vma->vm_flags & VM_WRITE)) {
            goto failed;
        }
        break;
    case 1: 
        goto failed;
    case 0: 
        if (!(vma->vm_flags & (VM_READ | VM_EXEC))) {
            goto failed;
        }
    }

    // 以下情形才能继续运行：1. 写某已存在的地址；2. 写未存在的地址，并且此地址可写；3. 读未存在的地址，并且此地址可读。
    // 对于情形 1，基本没有涉及，主要关注后两种情形。
    
    // 获取 vma 对应的访问权限
    uint32_t perm = PTE_U;
    if (vma->vm_flags & VM_WRITE) {
        perm |= PTE_W;
    }
    addr = ROUNDDOWN(addr, PGSIZE);

    ret = -E_NO_MEM;

    pte_t *ptep=NULL;
    // 获取该虚拟地址对应的 pte 表项，若获取失败(可能因为空间不足，而分配页表失败)，则直接返回。
    ptep = get_pte(mm->pgdir, addr, 1);
    if (ptep == NULL)
    {
        goto failed;
    }
    
    // 如果其值为空，则只能直接分配页面(对于实际系统而言，直接分配肯定是不行的，因为当前页面可能存在数据)。
    if (*ptep == 0) {
        // 同样可能因为分配页面而失败，
        if (pgdir_alloc_page(mm->pgdir, addr, perm) == NULL) {
            goto failed;
        }
    }
    
    // 表明其存在于 swap 分区内部，需要进行获取(如果 swap manager 尚未初始化成功，则直接返回)。
    else {
        if(swap_init_ok) {
            // 获取 swap 内容至所分配的 page。
            struct Page *page=NULL;
            if ((ret = swap_in(mm, addr, &page)) != 0)
            {
                goto failed;
            }
            
            // 构建页表映射，触发 FIFO 更新，设置 page 对应的 pra_vaddr。
            page_insert(mm->pgdir, page, addr, perm);                        
            swap_map_swappable(mm, addr, page, 1);
            page->pra_vaddr = addr;
        }
        else {
            goto failed;
        }
    }
    
    ret = 0;
failed:
    return ret;
}

扩展练习一

该练习用于了解并实现 extended clock 页面替换算法。

基于硬件实现以及现有数据结构，该算法比较容易实现。

当分配某程序物理页面后，需要将其放置于 list_entry_t pra_list_head 所示链表的尾部；程序访问过程中，硬件会自动设置 PTE 表项中的相关标志位 (所示页面是否发生修改，所示页面是否访问)；当需要选择待替换物理页面时，遍历链表，并动态更新 pra_list_head 指针以及相应页面对应页表项的标志位，如果某页面对应的标志位为 00 (即，自上次至此，尚未被访问，也尚未被修改)，则选择此页面进行替换。

扩展练习二

该练习用于了解并实现 LRU 页面替换算法。

当某页面被访问后，似乎无法更新 LRU 所维护的页面链表。