lagrange's blog

what's dead may never die

0%

Lab3 实验报告

发表于 更新于 分类于

Lab3

do_pgfault 之前

当程序访问内存遇上特殊情况时，CPU 会执行第十四号中断处理程序——缺页处理程序来处理。

特殊情况如下

  1. 写入一个存在物理页的虚拟页——写时复制。
  2. 读写一个不存在物理页的虚拟页——缺页。
  3. 不满足访问权限。

当程序触发缺页中断时，CPU 会把产生异常的线性地址存储在 CR2 寄存器中，并且把页访问异常错误码保存在中断栈中。

其中，页访问异常错误码的位 0 为 1 表示对应物理页不存在；位 1 为 1 表示写异常；位 2 为 1 表示访问权限异常。

中断处理机制

一直到do_pgfault的函数调用链为

trap–> trap_dispatch–>pgfault_handler–>do_pgfault

首先是在 trap.c 中中断向量表初始化的时候，将 vectors.S 中的所有跳转到__alltraps 的函数作为中断处理程序填写到 idt 表中，并设置中断寄存器 IDT。

完成该操作后，所有的中断会带着中断的描述向量值跳转到 __alltraps 中，这段汇编会进行中断现场的保存和恢复，并建立一个中断栈帧，最后带着栈帧跳转到 trap.c 中的 trap 函数，trap 函数直接调用 trap_dispatch（并传递该栈帧），trap_dispatch 函数包含了一个 case 语句，根据中断号调用 os 中不同的函数进行处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector254:
  pushl $0
  pushl $254
  jmp __alltraps

static struct gatedesc idt[256] = {{0}};

static struct pseudodesc idt_pd = {
    sizeof(idt) - 1, (uintptr_t)idt
};

void
idt_init(void) {
    extern uintptr_t __vectors[];
    int i;
    for (i = 0; i < sizeof(idt) / sizeof(struct gatedesc); i ++) {
        SETGATE(idt[i], 0, GD_KTEXT, __vectors[i], DPL_KERNEL);
    }
    lidt(&idt_pd);
}

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
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) {
    int ret = -E_INVAL;
    // 获取触发pgfault的虚拟地址所在虚拟页
    struct vma_struct *vma = find_vma(mm, addr);

    pgfault_num++;
    // 如果当前访问的虚拟地址不在已经分配的虚拟页中
    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:
        // 写，同时存在物理页，则写时复制
        // 需要注意的是，default会执行case2的代码，也就是判断是否有写权限。
    case 2:
        // 读，同时不存在物理页
        // 同时如果当前操作是写入，但所在虚拟页不允许写入
        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 */
        // 读，同时存在物理页。那就不可能会调用page fault，肯定哪里有问题，直接failed
        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);
    ret = -E_NO_MEM;
    pte_t *ptep=NULL;

    /* LAB3 EXERCISE 1: YOUR CODE */
    // 查找当前虚拟地址所对应的页表项
    // create 是 1，查找对应的页表项，页目录下找不到该页表则新建一个页表
    // 返回该页表的地址，地址为空说明找不到页表地址，直接返回failed
    if ((ptep = get_pte(mm->pgdir, addr, 1)) == NULL) {
        cprintf("get_pte in do_pgfault failed\n");
        goto failed;
    }
    // 如果这个页表项（用了*说明取了页表项中的内容）为0（啥没有）说明所对应的物理页不存在，则新建一个页对应页表
    if (*ptep == 0) {
        // 分配一块物理页，并设置页表项
        if (pgdir_alloc_page(mm->pgdir, addr, perm) == NULL) {
            cprintf("pgdir_alloc_page in do_pgfault failed\n");
            goto failed;
        }
    }
    else {
        /* LAB3 EXERCISE 2: YOUR CODE */
        // 如果这个页表项所对应的物理页存在，但不在内存中
        // 如果swap已经初始化完成
        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。
            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;
}

所以只要在 vma 里面设置的地址都是被 os 认定为有效的，找不到该地址会新建一个页，该页判断被换出会进行换入操作。

swap_in 函数首先向 OS 申请一个空闲页面，然后调用 swapfs_read 尝试将其从 swap 分区中读出。

1
2
3
4
5
6
7
8
9
10
11
12
13
int
swap_in(struct mm_struct *mm, uintptr_t addr, struct Page **ptr_result)
{
     struct Page *result = alloc_page();
     pte_t *ptep = get_pte(mm->pgdir, addr, 0);
     int r;
     //*ptep = pa | PTE_P | perm;
     //这时候PTE_P无效，pa与磁盘扇区有映射关系
     if ((r = swapfs_read((*ptep), result)) != 0)
        assert(r!=0);
     *ptr_result=result;
     return 0;
}

SWAP

虚存中的页与硬盘上的扇区之间的映射关系

如果一个页被置换到了硬盘上，那操作系统如何能简捷来表示这种情况呢？在 ucore 的设计上，充分利用了页表中的 PTE 来表示这种情况：当一个 PTE 用来描述一般意义上的物理页时，显然它应该维护各种权限和映射关系，以及应该有 PTE_P 标记；但当它用来描述一个被置换出去的物理页时，它被用来维护该物理页与 swap 磁盘上扇区的映射关系，并且该 PTE 不应该由 MMU 将它解释成物理页映射(即没有 PTE_P 标记)，与此同时对应的权限则交由 mm_struct 来维护，当对位于该页的内存地址进行访问的时候，必然导致 page fault，然后 ucore 能够根据 PTE 描述的 swap 项将相应的物理页重新建立起来，并根据虚存所描述的权限重新设置好 PTE 使得内存访问能够继续正常进行。

如果一个页（4KB/页）被置换到了硬盘某 8 个扇区（0.5KB/扇区），该 PTE 的最低位–present 位应该为 0 （即 PTE_P 标记为空，表示虚实地址映射关系不存在），接下来的 7 位暂时保留，可以用作各种扩展；而包括原来高 20 位页帧号的高 24 位数据，恰好可以用来表示此页在硬盘上的起始扇区的位置（其从第几个扇区开始）。为了在页表项中区别 0 和 swap 分区的映射，将 swap 分区的一个 page 空出来不用，也就是说一个高 24 位不为 0，而最低位为 0 的 PTE 表示了一个放在硬盘上的页的起始扇区号（见 swap.h 中对 swap_entry_t 的描述）：

1
2
3
4
5
swap_entry_t
-------------------------
| offset | reserved | 0 |
-------------------------
24 bits    7 bits   1 bit

考虑到硬盘的最小访问单位是一个扇区，而一个扇区的大小为 512（$2^8$）字节，所以需要 8 个连续扇区才能放置一个 4KB 的页。在 ucore 中，用了第二个 IDE 硬盘来保存被换出的扇区，根据实验三的输出信息

实验三还创建了一个 swap.img

1
2
3
4
5
6
SWAPIMG		:= $(call totarget,swap.img)

$(SWAPIMG):
	$(V)dd if=/dev/zero of=$@ bs=1024k count=128

$(call create_target,swap.img)

“ide 1: 262144(sectors), ‘QEMU HARDDISK’.”

我们可以知道实验三可以保存 262144/8=32768 个页，即 128MB 的内存空间。swap 分区的大小是 swapfs_init 里面根据磁盘驱动的接口计算出来的，目前 ucore 里面要求 swap 磁盘至少包含 1000 个 page，并且至多能使用 1<<24 个 page。

FIFO

Page 的数据结构里面又多了几个链接域，用于下面换入换出的时候来管理这些个 Page。因为 FIFO 需要维护现在正在使用的页，所以用来管理的结构是 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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// the control struct for a set of vma using the same PDT
struct mm_struct {
    list_entry_t mmap_list;        // 按照虚拟地址顺序双向连接的虚拟页链表
    struct vma_struct *mmap_cache; // 当前使用的虚拟页地址，该成员加速页索引速度。
    pde_t *pgdir;                  // 虚拟页对应的PDT
    int map_count;                 // 虚拟页个数
    void *sm_priv;                 // 用于指向swap manager的某个链表,在FIFO算法中，该双向链表用于将可交换的已分配物理页串起来
};

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;            // 用于保存该物理页所对应的虚拟地址。
};

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);
    return 0;
}

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
     list_entry_t *le = head->prev;
     assert(head!=le);
     struct Page *p = le2page(le, pra_page_link);
     list_del(le);
     assert(p !=NULL);
     *ptr_page = p;

     return 0;
}