Pwn进你的心
0%

Ucore-Lab3

Posted on Edited on In 19k 17 mins.

vma简析

用户进程的虚拟地址空间包含了若干区域，这些区域的分布方式是特定于体系结构的，不过所有的方式都包含下列成分：

  • 可执行文件的二进制代码，也就是程序的代码段
  • 存储全局变量的数据段
  • 用于保存局部变量和实现函数调用的栈
  • 环境变量和命令行参数
  • 程序使用的动态库的代码
  • 用于映射文件内容的区域

由此可以看到进程的虚拟内存空间会被分成不同的若干区域，每个区域都有其相关的属性和用途，一个合法的地址总是落在某个区域当中的，这些区域也不会重叠

在linux内核中，这样的区域被称之为虚拟内存区域（virtual memory areas，vma），每一个虚拟内存区域都由一个相关的 struct vma_struct 结构来描述，而一个进程往往由许多不同功能的 vma 组成，它们则统一归于 struct mm_struct 结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct vma_struct {
    struct mm_struct *vm_mm; /* 所属的内存描述符 */
    uintptr_t vm_start;      /* vma的起始地址 */      
    uintptr_t vm_end;        /* vma的结束地址 */  
    uint32_t vm_flags;       /* 标识集 */
    list_entry_t list_link;  /* 按vma的起始地址排序的线性列表链接 */
    /* 后续实验还会增加: */
    // mm_count(共享mm的进程数)
    // mm_lock(关于锁的标记) 
};

struct mm_struct {
    list_entry_t mmap_list;          /* vma链表的起始地址 */
    struct vma_struct *mmap_cache;   /* 当前访问的vma，用于速度目的 */
    pde_t *pgdir;                    /* 这些vma的PDT(页目录表) */
    int map_count;                   /* 这些vma的计数 */
    void *sm_priv;                   /* 用于指向swap manager的某个链表 */
    /* 在FIFO算法中,该双向链表用于将可交换的已分配物理页串起来 */
};
  • 每一个进程都有一个 mm_struct 来管理虚拟内存和物理内存
  • 内核会把这一整片内存给划分为不同功能的 vma，每个 vma 用一个 vma_struct 来管理
  • 按 vma 的起始地址排序，可以把一个进程中所有的 vma 组成一个链表
  • 而 mm_struct->mmap_list 指向该 vma 链表的起始地址

下面是与 vma 有关的函数：

  • find_vma：找寻合适的 vma 地址（vma->vm_start <= addr <= vma_vm_end）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
struct vma_struct {
    struct mm_struct *vm_mm; /* 所属的内存描述符 */
    uintptr_t vm_start;      /* vma的起始地址 */      
    uintptr_t vm_end;        /* vma的结束地址 */  
    uint32_t vm_flags;       /* 标识集 */
    list_entry_t list_link;  /* 按vma的起始地址排序的线性列表链接 */
};

struct vma_struct * 
find_vma(struct mm_struct *mm, uintptr_t addr) { /* 我没有看出来这个addr有什么用 */
    struct vma_struct *vma = NULL;
    if (mm != NULL) {
        vma = mm->mmap_cache; /* 尝试直接获取当前访问的vma,若没有找到才遍历链表 */
        if (!(vma != NULL && vma->vm_start <= addr && vma->vm_end > addr)) {
                bool found = 0; /* 标记未找到 */
                list_entry_t *list = &(mm->mmap_list), *le = list;
                while ((le = list_next(le)) != list) { /* 遍历vma链表 */
                    vma = le2vma(le, list_link); /* 通过链表信息获取vma首地址 */
                    if (vma->vm_start<=addr && addr < vma->vm_end) {
                        found = 1; /* 标记找到 */
                        break;
                    }
                }
                if (!found) {
                    vma = NULL; /* 若没有找到,返回NULL */
                }
        }
        if (vma != NULL) {
            mm->mmap_cache = vma; /* 若找到,更新mmap_cache条目(方便下次找到) */
        }
    }
    return vma;
}
  • vma_create：新建vma，并进行初始化
1
2
3
4
5
6
7
8
9
10
11
struct vma_struct *
vma_create(uintptr_t vm_start, uintptr_t vm_end, uint32_t vm_flags) {
    struct vma_struct *vma = kmalloc(sizeof(struct vma_struct)); /* 分配一片空间用于存储vma */

    if (vma != NULL) { /* 初始化各个条目 */
        vma->vm_start = vm_start;
        vma->vm_end = vm_end;
        vma->vm_flags = vm_flags;
    }
    return vma;
}
  • insert_vma_struct：把新申请的vma插入vma链表（mmap_list为该链表的起始地址）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
void
insert_vma_struct(struct mm_struct *mm, struct vma_struct *vma) {
    assert(vma->vm_start < vma->vm_end);
    list_entry_t *list = &(mm->mmap_list); /* 目标进程的获取vma链表首地址 */
    list_entry_t *le_prev = list, *le_next;

        list_entry_t *le = list;
        while ((le = list_next(le)) != list) { /* 遍历vma链表 */
            struct vma_struct *mmap_prev = le2vma(le, list_link);
            if (mmap_prev->vm_start > vma->vm_start) {
                /* 注意:vma链表是按vma起始地址的排序进行链接的 */
                break;
            }
            le_prev = le;
        }

    le_next = list_next(le_prev);

    /* 检查是否覆盖 */
    if (le_prev != list) {
        check_vma_overlap(le2vma(le_prev, list_link), vma);
    }
    if (le_next != list) {
        check_vma_overlap(vma, le2vma(le_next, list_link));
    }

    vma->vm_mm = mm; /* 更新vm_mm条目(用于记录该vma所属的mm_struct内存描述符) */
    list_add_after(le_prev, &(vma->list_link)); /* 插链 */

    mm->map_count ++; /* vma的计数增加 */
}

static inline void
check_vma_overlap(struct vma_struct *prev, struct vma_struct *next) {
    assert(prev->vm_start < prev->vm_end);
    assert(prev->vm_end <= next->vm_start);
    assert(next->vm_start < next->vm_end);
}
  • mm_map：构建新的vma（包含find_vma，vma_create，insert_vma_struct，并形成逻辑）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#define USERBASE            0x00200000
#define USERTOP             0xB0000000
#define USER_ACCESS(start, end) \ /* 检查该start和end是否符合条件 */
(USERBASE <= (start) && (start) < (end) && (end) <= USERTOP)

int
mm_map(struct mm_struct *mm, uintptr_t addr, size_t len, uint32_t vm_flags,
       struct vma_struct **vma_store) {
    // mm:当前进程的mm_struct结构体
    // addr(ph->p_va):映射段的虚拟地址
    // len(ph->p_memsz):该段在内存中的大小
    // vm_flags:标志位
    // vma_store:NULL
    
    uintptr_t start = ROUNDDOWN(addr, PGSIZE), end = ROUNDUP(addr + len, PGSIZE);
    /* 实现内存页对齐,建立合法的start(目标段起始地址),end地址(目标段结束地址) */
    if (!USER_ACCESS(start, end)) { /* 确保该start和end在一定的范围内 */
        return -E_INVAL;
    }

    assert(mm != NULL); /* 断言mm不为空 */

    int ret = -E_INVAL; /* 标记异常返回 */

    struct vma_struct *vma;
    if ((vma = find_vma(mm, start)) != NULL && end > vma->vm_start) {
        /* 找寻合适的vma地址(通过mmap_cache获取vma链表) */
     // insert_vma_struct(mm, vma); 
     // ret = 0;
        goto out; /* 找寻成功则立刻返回 */
    }
    
    /*
    这里我感觉有点BUG:
    如果find_vma找到了vma(vma就不为空),应该把它送入insert_vma_struct才对
    按照程序的逻辑,不管"end>vma->vm_star"t是否成立,找寻到的vma都无法再利用
    条件成立:执行"goto out"返回一个错误代码
    条件不成立:后续的vma_create会覆盖原来的vma,就相当于白找了
    */
    
    ret = -E_NO_MEM; /* 标记异常返回 */

    if ((vma = vma_create(start, end, vm_flags)) == NULL) {
        /* 新建vma,并进行初始化 */
        goto out; /* 新建失败则立刻返回(NULL) */
    }
    insert_vma_struct(mm, vma); /* 使新分配的vma插入vma链表 */
    if (vma_store != NULL) {
        *vma_store = vma;
    }
    ret = 0; /* 标记正常返回 */

out:
    return ret;
}

与 mm 有关的函数只有两个：（因为涉及到锁和共享内存，所以在后续的实验中进行分析）

  • mm_create：创建一片虚拟内存，完成各个条目的初始化
  • mm_destroy：遍历并释放 vma 链表中的所有 vma，最后释放 mm

虚拟内存

虚拟内存是CPU可以看到的“内存”

  • 虚拟内存所对应的实际物理内存单元可能不存在
  • 虚拟内存的地址和对应物理内存的地址可能不一致
  • 通过操作系统所实现的某种内存映射机制，可以达到访问的虚拟内存地址转换为物理内存地址的目的

虚拟内存的异常：

  • 写入一个存在物理页的虚拟页 —- 写时复制
  • 读写一个不存在物理页的虚拟页 —- 缺页
  • 不满足访问权限

虚拟页结构

lab3 的虚拟页结构和 lab2 有所不同：

1
2
3
4
5
6
7
8
struct Page {
    int ref;                    // 当前页被引用的次数,与内存共享有关
    uint32_t flags;             // 标志位的集合,与eflags寄存器类似
    unsigned int property;      // 空闲的连续page数量,这个成员只会用在连续空闲page中的第一个page
    list_entry_t page_link;     // 两个分别指向上一个和下一个非连续空闲页的两个指针
    list_entry_t pra_page_link; // 用于连接上一个和下一个"可交换已分配"的物理页
    uintptr_t pra_vaddr;        // 用于保存该物理页所对应的虚拟地址
};

新增了 pra_page_link 和 pra_vaddr ，它们将在页面替换算法（page replace algorithm，pra）中起作用（ pra_page_link 类似于 page_link ，用于链接执行“页面替换算法”的链表）

uCore页面置换&物理页控制

swap_manager 与 pmm_manager 类似，都设置了一个用于管理某个功能的模块

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct swap_manager
{
     const char *name;
     int (*init)            (void); 
    /* 交换管理器的全局初始化 */
     int (*init_mm)         (struct mm_struct *mm); 
    /* 初始化mm_结构中的priv数据 */
     int (*tick_event)      (struct mm_struct *mm); 
    /* 发生时钟中断时调用 */
     int (*map_swappable)   (struct mm_struct *mm, uintptr_t addr, struct Page *page, int swap_in); 
    /* 将可交换页面映射到mm_结构时调用 */
     int (*set_unswappable) (struct mm_struct *mm, uintptr_t addr);
    /* 当页面被标记为共享时，调用此例程(从交换管理器中删除addr条目) */
     int (*swap_out_victim) (struct mm_struct *mm, struct Page **ptr_page, int in_tick);
    /* 试着换掉一页，然后返回victim */
     int (*check_swap)(void);     
    /* 检查页面重新定距算法 */
}; 
/* 结构体swap_manager中:定义了一大堆的函数指针 */

pgdir_alloc_page：分配一块物理页（作为页表），设置页表项（对应物理地址la），插入页表目录（pgdir）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct Page *
pgdir_alloc_page(pde_t *pgdir, uintptr_t la, uint32_t perm) {
    struct Page *page = alloc_page(); /* 分配一张物理页 */
    if (page != NULL) {
        if (page_insert(pgdir, page, la, perm) != 0) {
            /* 将该物理页与对应的虚拟地址关联,同时设置页表 */
            free_page(page); /* 释放页 */
            return NULL;
        }
        if (swap_init_ok){
            swap_map_swappable(check_mm_struct, la, page, 0);
            /* 设置当前页为可swap */
            page->pra_vaddr=la;
            assert(page_ref(page) == 1); 
        }
    }
    return page;
}

page_insert：将该物理页与对应的虚拟地址关联，同时设置页表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
int
page_insert(pde_t *pgdir, struct Page *page, uintptr_t la, uint32_t perm) {
    // pgdir:页目录表PDT的内核虚拟基址
    // page:需要映射的物理页
    // la:需要映射的线性地址
    // perm:在相关pte中设置的该页面的权限
    
    pte_t *ptep = get_pte(pgdir, la, 1); /* 获取线性地址la对应二级页表项的虚拟地址 */
    if (ptep == NULL) {
        return -E_NO_MEM;
    }
    page_ref_inc(page); /* 引用次数+1 */
    if (*ptep & PTE_P) { /* 表示物理内存页存在 */
        struct Page *p = pte2page(*ptep); /* 获取该物理页 */
        if (p == page) {
            page_ref_dec(page); /* 引用次数-1 */
        }
        else {
            page_remove_pte(pgdir, la, ptep); /* 释放某虚地址所在的物理页并取消对应的二级页表项映射 */
        }
    }
    *ptep = page2pa(page) | PTE_P | perm; /* 获取物理页page的物理地址后进行设置 */
    /* ptep为对应二级页表项的虚拟地址,页表项里面也应该装物理地址 */
    tlb_invalidate(pgdir, la); /* 用于使虚拟地址la对应的tlb表项失效 */
    return 0;
}

/* page->ref:当前页被引用的次数,与内存共享有关 */

static inline int
page_ref_inc(struct Page *page) { 
    page->ref += 1; /* 引用次数+1 */
    return page->ref;
}

static inline int
page_ref_dec(struct Page *page) {
    page->ref -= 1; /* 引用次数-1 */
    return page->ref;
}

page_remove_pte：释放某虚地址所在的物理页并取消对应的二级页表项映射（已经实现）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static inline void
page_remove_pte(pde_t *pgdir, uintptr_t la, pte_t *ptep) {
    // pgdir:页目录表PDT的内核虚拟基址
    // la:需要映射的线性地址
    // ptep:二级页表项的虚拟地址

#if 0 /* 模板 */
    if (0) {                     
        struct Page *page = NULL; 
    }
#endif /* 实现 */
    if (*ptep & PTE_P) {
        struct Page *page = pte2page(*ptep); /* 获取对应的物理页 */
        if (page_ref_dec(page) == 0) { /* "引用次数-1"后,确保该页没有被引用 */
            free_page(page); /* 释放目标页 */
        }
        *ptep = 0;
        tlb_invalidate(pgdir, la); /* 用于使虚拟地址la对应的tlb表项失效 */
    }
}

swap_in：只会将目标物理页加载进内存中，而不会修改页表条目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int
swap_in(struct mm_struct *mm, uintptr_t addr, struct Page **ptr_result)
{
    // mm:指定地址对应的"所属的内存描述符"
    // addr:指定的虚拟地址
    // ptr_result:最终需要返回的物理页(利用alloc_page进行分配)
    
     struct Page *result = alloc_page(); /* 分配一张物理页 */
     assert(result!=NULL); /* assert断言分配成功 */

     pte_t *ptep = get_pte(mm->pgdir, addr, 0);
     /* 找到一个虚地址对应的二级页表项的虚拟地址,如果此二级页表项不存在,则分配一个包含此项的二级页表 */
    
     int r;
     if ((r = swapfs_read((*ptep), result)) != 0)
         /* 尝试将硬盘中的内容换入到新的page中 */
     {
        assert(r!=0);
     }
     cprintf("swap_in: load disk swap entry %d with swap_page in vadr 0x%x\n", (*ptep)>>8, addr);
     *ptr_result=result;
     return 0;
}

swapfs_read：尝试将硬盘中的内容换入到新的 page 中 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int
swapfs_read(swap_entry_t entry, struct Page *page) {
    return ide_read_secs(SWAP_DEV_NO, swap_offset(entry) * PAGE_NSECT, page2kva(page), PAGE_NSECT);
}

int
ide_read_secs(unsigned short ideno, uint32_t secno, void *dst, size_t nsecs) {
    assert(nsecs <= MAX_NSECS && VALID_IDE(ideno));
    assert(secno < MAX_DISK_NSECS && secno + nsecs <= MAX_DISK_NSECS);
    unsigned short iobase = IO_BASE(ideno), ioctrl = IO_CTRL(ideno);

    ide_wait_ready(iobase, 0);

    // generate interrupt
    outb(ioctrl + ISA_CTRL, 0);
    outb(iobase + ISA_SECCNT, nsecs);
    outb(iobase + ISA_SECTOR, secno & 0xFF);
    outb(iobase + ISA_CYL_LO, (secno >> 8) & 0xFF);
    outb(iobase + ISA_CYL_HI, (secno >> 16) & 0xFF);
    outb(iobase + ISA_SDH, 0xE0 | ((ideno & 1) << 4) | ((secno >> 24) & 0xF));
    outb(iobase + ISA_COMMAND, IDE_CMD_READ);

    int ret = 0;
    for (; nsecs > 0; nsecs --, dst += SECTSIZE) {
        if ((ret = ide_wait_ready(iobase, 1)) != 0) {
            goto out;
        }
        insl(iobase, dst, SECTSIZE / sizeof(uint32_t));
    }
out:
    return ret;
}

swap_map_swappable：将该物理页加入到 mm_struct->sm_priv 指针所指向的双向链表中，换入和换出操作都会操作该链表（插入/移除 可交换的已分配 物理页） 

1
2
3
4
5
int
swap_map_swappable(struct mm_struct *mm, uintptr_t addr, struct Page *page, int swap_in)
{
     return sm->map_swappable(mm, addr, page, swap_in); /* 发生时钟中断时调用 */
}

uCore缺页异常处理

页缺失（Page fault，又名硬错误、硬中断、分页错误、寻页缺失、缺页中断、页故障等），是指当软件试图访问已映射在虚拟地址空间中， 但是并未被加载在物理内存中的一个分页时 ，由中央处理器的内存管理单元所发出的中断（读写一个不存在物理页的虚拟页）

通常情况下，用于处理此中断的程序是操作系统的一部分

  • 如果操作系统判断此次访问是有效的，那么操作系统会尝试将相关的分页从硬盘上的虚拟内存文件中调入内存
  • 而如果访问是不被允许的，那么操作系统通常会结束相关的进程

产生页访问异常的原因主要有：

  • 目标页帧不存在（页表项全为 0，即该线性地址与物理地址尚未建立映射或者已经撤销）
  • 相应的物理页帧不在内存中（页表项非空，但 Present 标志位=0，比如在 swap 分区或磁盘文件上)
  • 不满足访问权限（此时页表项 P 标志=1，但低权限的程序试图访问高权限的地址空间，或者有程序试图写只读页面）

异常处理的过程：

产生页访问异常后，CPU 硬件和软件都会做一些事情来应对此事

  • 首先页访问异常也是一种异常，所以针对一般异常的硬件处理操作是必须要做的，即 CPU 在当前内核栈保存当前被打断的程序现场，即依次压入当前被打断程序使用的 EFLAGS，CS，EIP，errorCode
  • 由于页访问异常的中断号是 0xE，CPU 把异常中断号 0xE 对应的中断服务例程的地址加载到 CS 和 EIP 寄存器中，开始执行中断服务例程
  • 这时 ucore 开始处理异常中断，首先需要保存硬件没有保存的寄存器，在 vectors.S 中的标号 vector14 处先把中断号压入内核栈，然后再在 trapentry.S 中的标号__alltraps 处把 DS、ES 和其他通用寄存器都压栈
  • 自此，被打断的程序执行现场（context）被保存在内核栈中
  • 接下来，在 trap.c 的 trap 函数开始了中断服务例程的处理流程，大致调用关系为：
1
trap-->trap_dispatch-->pgfault_handler-->do_pgfault

其中的 do_pgfault 就是该异常处理的核心部分

练习0-把 lab2 的内容复制粘贴到 lab3

练习1-给未被映射的地址映射上物理页

完成 do_pgfault 函数（mm/vmm.c），给未被映射的地址映射上物理页，设置访问权限的时候需要参考页面所在 VMA 的权限，同时需要注意映射物理页时需要操作内存控制 结构所指定的页表，而不是内核的页表

  • 触发 do_pgfault 有两种情况：
    • 如果操作系统判断此次访问是有效的，那么操作系统会尝试将相关的分页从硬盘上的虚拟内存文件中调入内存
    • 如果访问是不被允许的，那么操作系统通常会结束相关的进程
  • 第二种情况程序已经替我们实现了，所以我们需要“将相关的分页从硬盘上的虚拟内存文件中调入内存”
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
int
do_pgfault(struct mm_struct *mm, uint32_t error_code, uintptr_t addr) {
    // mm:指定地址对应的"所属的内存描述符"
    // error_code:错误代码
    // addr:发生Page Fault的虚拟地址
    
    int ret = -E_INVAL;
    /* 根据mm找到一个vma(virtual memory areas) */
    struct vma_struct *vma = find_vma(mm, addr);

    pgfault_num++;
    /* vma未找到 || 如果addr(虚拟地址)不在mm的vma范围内 */
    if (vma == NULL || vma->vm_start > addr) {
        cprintf("not valid addr %x, and  can not find it in vma\n", addr);
        goto failed;
    }
    /* 检测到错误代码,根据错误代码输出错误信息 */
    switch (error_code & 3) {
    default:
            /* error code flag : default is 3 ( W/R=1, P=1): write, present */
    case 2: /* error code flag : (W/R=1, P=0): write, not present */
        if (!(vma->vm_flags & VM_WRITE)) {
            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 */
        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 */
        if (!(vma->vm_flags & (VM_READ | VM_EXEC))) {
            cprintf("do_pgfault failed: error code flag = read AND not present, but the addr's vma cannot read or exec\n");
            goto failed;
        }
    }
    uint32_t perm = PTE_U; /* 设置页表条目所对应的权限:可以读取对应物理页的内容 */
    if (vma->vm_flags & VM_WRITE) {
        perm |= PTE_W;
    }
    addr = ROUNDDOWN(addr, PGSIZE); /* 将addr与PGSIZE对齐 */
    ret = -E_NO_MEM;
    pte_t *ptep=NULL;
#if 0 /* 需要在这里实现:将相关的分页从硬盘上的虚拟内存文件中调入内存 */
    ptep = ???        
    if (*ptep == 0) {
    }
    else {
        if(swap_init_ok) {
            struct Page *page=NULL;               
        }
        else {
            cprintf("no swap_init_ok but ptep is %x, failed\n",*ptep);
            goto failed;
        }
   }
#endif
   ret = 0;
failed:
    return ret;
}

要求：

  • 尝试查找 pte，如果 pte 的PT（页面表）不存在，则创建一个PT
  • 如果 phy addr 不存在，则分配一个页面并将 phy addr 映射为逻辑 addr
  • 根据 mm 和 addr，尝试加载右磁盘页面的内容
  • 根据 mm、addr 和 page，设置 phy addr 的映射
  • 使页面可交换

具体实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
int
do_pgfault(struct mm_struct *mm, uint32_t error_code, uintptr_t addr) {
    // mm:指定地址对应的"所属的内存描述符"
    // error_code:错误代码
    // addr:发生Page Fault的虚拟地址
    
    int ret = -E_INVAL;
    /* 根据mm找到一个vma(virtual memory areas) */
    struct vma_struct *vma = find_vma(mm, addr);

    pgfault_num++;
    /* vma未找到 || 如果addr(虚拟地址)不在mm的vma范围内 */
    if (vma == NULL || vma->vm_start > addr) {
        cprintf("not valid addr %x, and  can not find it in vma\n", addr);
        goto failed;
    }
    /* 检测错误代码,这里的检测不涉及特权判断 */
    switch (error_code & 3) {
    default:
            /* error code flag : default is 3 ( W/R=1, P=1): write, present */
    case 2: /* error code flag : (W/R=1, P=0): write, not present */
        if (!(vma->vm_flags & VM_WRITE)) {
            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 */
        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 */
        if (!(vma->vm_flags & (VM_READ | VM_EXEC))) {
            cprintf("do_pgfault failed: error code flag = read AND not present, but the addr's vma cannot read or exec\n");
            goto failed;
        }
    }
    uint32_t perm = PTE_U; /* 设置页表条目所对应的权限:可以读取对应物理页的内容 */
    if (vma->vm_flags & VM_WRITE) {
        perm |= PTE_W;
    }
    addr = ROUNDDOWN(addr, PGSIZE); /* 将addr与PGSIZE对齐 */
    ret = -E_NO_MEM;
    pte_t *ptep=NULL;
#if 0 /* 模板 */
    ptep = ???         
    if (*ptep == 0) {
    }
    else {
        if(swap_init_ok) {
            struct Page *page=NULL;
        }
        else {
            cprintf("no swap_init_ok but ptep is %x, failed\n",*ptep);
            goto failed;
        }
   }
#endif
    ptep = get_pte(mm->pgdir, addr, 1); /* 获取当前虚拟地址所对应的页表项 */
    if (*ptep == 0) { /* 该页表项对应的物理页不存在 */
        if (pgdir_alloc_page(mm->pgdir, addr, perm) == NULL) {
            /* 分配一块物理页，并设置页表项 */
            cprintf("pgdir_alloc_page in do_pgfault failed\n");
            goto failed;
        }
    }
    else { /* 该页表项对应的物理页存在 */
        if(swap_init_ok) { /* 如果swap已经初始化完成 */
            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);
            /* 设置当前页为可swap */
            page->pra_vaddr = addr;
            /* page->pra_vaddr:用于保存该物理页所对应的虚拟地址 */
        }
        else {
            cprintf("no swap_init_ok but ptep is %x, failed\n",*ptep);
            goto failed;
        }
   }
   ret = 0;
failed:
    return ret;
}

练习2-补充完成基于FIFO的页面替换算法

FIFO 中，当新加入一个物理页时，我们只需将该物理页加入至链表首部即可，当需要换出某个物理页时，选择链表末尾的物理页即可

先看看 FIFO 初始化函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
list_entry_t pra_list_head; /* swap manager中:"可交换已分配"链表的链表头 */

static int
_fifo_init_mm(struct mm_struct *mm)
{     
     list_init(&pra_list_head);
     mm->sm_priv = &pra_list_head;
     return 0;
}

static inline void
list_init(list_entry_t *elm) {
    elm->prev = elm->next = elm;
}
  • 让 mm->sm_priv 指向 pra_list_head 的地址
  • 现在，我们可以从内存控制结构体 mm_struct 访问 FIFO PRA（FIFO页面替换算法）

接下来就是需要我们进行完善的函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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; /* 获取pra_list_head */
    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.
    return 0;
}

static int /* 执行换出队列的操作(把链表尾部的page脱链即可) */
_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; /* 获取pra_list_head */
         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
     return 0;
}

具体实现特别简单：（参考 CSapp 中的 malloc lab）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
static int /* 执行目标页加入队列的操作(插入目标页头部即可) */
_fifo_map_swappable(struct mm_struct *mm, uintptr_t addr, struct Page *page, int swap_in) 
{
    // mm:指定地址对应的"所属的内存描述符"
    // addr:发生目标虚拟地址
    // page:将要被插入的物理页
    // swap_in:swap_manager中的函数指针(将可交换页面映射到mm_结构时调用)
    
    list_entry_t *head=(list_entry_t*) mm->sm_priv; /* 获取pra_list_head */
    list_entry_t *entry=&(page->pra_page_link); /* page->pra_page_link==NULL */
    assert(entry != NULL && head != NULL); 
    
    /* 结点->prev  <--1-->  结点(pra_list_head)  <--2-->  结点->next */
    
    list_add(head, entry); /* 直接插入头部("2"号位置) */
    return 0;
}

static int /* 执行换出队列的操作(把链表尾部的page脱链即可) */ 
_fifo_swap_out_victim(struct mm_struct *mm, struct Page ** ptr_page, int in_tick)
{ 
    // mm:指定地址对应的"所属的内存描述符"
    // ptr_page:将要被换出的物理页(会被返回出来)
    // in_tick:信息表示位
    
     list_entry_t *head=(list_entry_t*) mm->sm_priv; /* 获取pra_list_head */
         assert(head != NULL);
     assert(in_tick==0);
     list_entry_t *le = head->prev; /* 获取pra_list_head->prev(链表尾) */
     assert(head!=le);
     struct Page *p = le2page(le, pra_page_link); /* 根据链表信息获取该page的位置 */
     list_del(le); /* 脱链操作 */
     assert(p !=NULL);
     *ptr_page = p;

     return 0;
}

结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
➜  lab3 make grade
Check SWAP:              (1.2s)
  -check pmm:                                OK
  -check page table:                         OK
  -check vmm:                                WRONG
   -e !! error: missing 'page fault at 0x00000100: K/W [no page found].'
   !! error: missing 'check_pgfault() succeeded!'
   !! error: missing 'check_vmm() succeeded.'

  -check swap page fault:                    WRONG
   -e !! error: missing 'page fault at 0x00001000: K/W [no page found].'
   !! error: missing 'page fault at 0x00002000: K/W [no page found].'
   !! error: missing 'page fault at 0x00003000: K/W [no page found].'
   !! error: missing 'page fault at 0x00004000: K/W [no page found].'
   !! error: missing 'write Virt Page e in fifo_check_swap'
   !! error: missing 'page fault at 0x00005000: K/W [no page found].'
   !! error: missing 'page fault at 0x00001000: K/W [no page found]'
   !! error: missing 'page fault at 0x00002000: K/W [no page found].'
   !! error: missing 'page fault at 0x00003000: K/W [no page found].'
   !! error: missing 'page fault at 0x00004000: K/W [no page found].'
   !! error: missing 'check_swap() succeeded!'

  -check ticks:                              WRONG
   -e !! error: missing '++ setup timer interrupts'
   !! error: missing '100 ticks'
   !! error: missing 'End of Test.'

Total Score: 10/45
make: *** [Makefile:260：grade] 错误 1