Skip to content

PA3-3 note

截至目前，我们没有区分线性地址和物理地址，即 laddr = paddr。在 80386之后，我们引入分页机制，让每一个进程都拥有独立的存储空间，且具有相同的地址划分方式

此时为了实现分页机制，我们需要在 laddr --> paddr 这一步进行进一步的转换，而不是直接映射

（分页机制和 PA3.2 实现的段机制有相似之处，可以结合着看）

Intro

程序层采用虚拟地址，虚拟地址与主存地址存在对应关系

在引入分页式虚拟存储后，主存地址和虚拟地址空间都被划分成大小相等的页面，在虚拟地址空间中的页面称为虚拟页，而对应的在主存空间中的页面称为物理页。在 x86 系统中，规定每个页面的大小为 $2^{12} = 4\text{ KB}$。于是一个进程的整个虚拟地址空间就被划分成 $1\text{ M} = 2^{20} = 1024*1024$ 个虚拟页。

无论是哪一个进程，虚拟页和物理页都是一一对应的（不考虑多对一、一对多等复杂的情况）。就像之前引入段表一样，我们相应的引入页表，页表是由若干个页表项构成的数组，每个页表项是一个 32bit 的结构体，包含各种标志位以及存放位置（某一个虚拟页映射到主存中的哪一个物理页 这一信息）

以下是 x86 页表项的位布局，其中固定为 0 的位不可修改：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
31                                  12 11                      0
+--------------------------------------+-------+---+-+-+---+-+-+-+
|                                      |       |   | | |   |U|R| |
|     PAGE FRAME ADDRESS 31..12        | AVAIL |0 0|D|A|0 0|/|/|P|
|                                      |       |   | | |   |S|W| |
+--------------------------------------+-------+---+-+-+---+-+-+-+
P - PRESENT
R/W - READ/WRITE
U/S - USER/SUPERVISOR
D - DIRTY
AVAIL - AVAILABLE FOR SYSTEMS PROGRAMMER USE
NOTE: 0 INDICATES INTEL RESERVED. DO NOT DEFINE.

与段描述符中的段基地址不同，32位系统中，页表项中的物理页存放位置指向的是主存中对应的20位物理页号（或称页框号）。若物理页号为0，则表示该页没有调入主存。这里体现出分页机制和分段机制一个很大的区别：在分页机制下，所寻址的物理页不一定在主存中，而可能位于磁盘上。这种允许用磁盘来扩展存储主存中数据的方式大大提高了系统的处理能力。

每个进程都有自己独立的页表来描述该进程的虚拟地址空间和物理地址空间之间的映射关系。从较为直观的角度来说，一个 32 位的线性地址可以分为两个部分：高 20 位指出该线性地址属于哪一个虚拟页，而低 12 位则指出该地址具体指向的字节在该虚拟页内的偏移量是多少。若参照段表的组织方式，将所有 $2^{20}$ 个页表项都按顺序存放在一个数组中。那么地址转换的过程就可以简单地表达为：使用线性地址中的高 20 位作为索引，查找页表；提取对应页表项中的物理页号，加上线性地址中低 12 位指出的页内偏移量；便能够获取对应的物理地址了。

很快我们发现 “将所有 $2^{20}$ 个页表项都按顺序存放在一个数组中” 不现实，因此我们把页表拆成二级索引结构：线性地址地高 20 位拆成两部分：高 10 位作为页目录，低 10 位 作为页表索引

可以理解词典添加了 A~Z 字母的一级索引，然后在一级索引下定位具体地点

实现

对 config.h 和 Makefile 的修改简单来说就是建立虚拟内存地址空间的布局，将内核的虚拟地址从 0x30000 修改为 0xc0030000，对应的物理地址不变，同时将用户程序的虚拟地址统一为 0x8048000（物理地址依旧是分散的），这是为了还原真实的 Linux 内存机制

Kernel 的行为改变参照 PA 手册，这里只介绍如何完善 NEMU 的代码层：

首先完成对 CR3 寄存器的实现，其存储了页表的根目录物理地址

1
2
3
4
5
6
7
typedef union {
    struct {
        uint32_t reserved : 12;
        uint32_t pdbr : 20;
    };
    uint32_t val;
}CR3;

接下来就是对 laddr 的修改，这是没有分页机制下的代码

PA3 的每一个子阶段都在逐步完善内存机制，paddr vaddr laddr 在引入了三种机制后分别得到了完善

1
2
3
4
5
6
7
8
9
uint32_t laddr_read(laddr_t laddr, size_t len)
{
    return paddr_read(laddr, len);
}

void laddr_write(laddr_t laddr, size_t len, uint32_t data)
{
    paddr_write(laddr, len, data);
}

引入 paddr 后是这样的：

 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
uint32_t laddr_read(laddr_t laddr, size_t len)
{
#ifdef IA32_PAGE
    if (cpu.cr0.pg) {
        paddr_t paddr = page_translate(laddr);
        return paddr_read(paddr, len);
    }
    return paddr_read(laddr, len);
#else
    return paddr_read(laddr, len);
#endif
}

void laddr_write(laddr_t laddr, size_t len, uint32_t data)
{
#ifdef IA32_PAGE
    if (cpu.cr0.pg) {
        paddr_t paddr = page_translate(laddr);
        paddr_write(paddr, len, data);
        return;
    }
    paddr_write(laddr, len, data);
#else
    paddr_write(laddr, len, data);
#endif
}

接下来是 page_translate() 函数的实现：

1
2
3
4
5
6
7
8
9
// translate from linear address to physical address
paddr_t page_translate(laddr_t laddr)
{
#ifndef TLB_ENABLED
    // need implementation
#else
    return tlb_read(laddr) | (laddr & PAGE_MASK);
#endif
}

其中 tlb_read 是快表的实现（对页表的 cache 实现），我们需要实现的是基础情况下的页表翻译工作（下图为 Laddr -> Paddr 的转换过程）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
                                                              PAGE FRAME
     LINEAR   +-----------+-----------+----------+         +---------------+
     ADDRESS  |    DIR    |   PAGE    |  OFFSET  |         |               |
              +-----+-----+-----+-----+-----+----+         |               |
                    |           |           |              |               |
      +-------------+           |           +------------->|    PHYSICAL   |
      |                         |                          |    ADDRESS    |
      |   PAGE DIRECTORY        |      PAGE TABLE          |               |
      |  +---------------+      |   +---------------+      |               |
      |  |               |      |   |               |      +---------------+
      |  |               |      |   |---------------|              ^
      |  |               |      +-->| PG TBL ENTRY  |--------------+
      |  |---------------|          |---------------|
      +->|   DIR ENTRY   |--+       |               |
         |---------------|  |       |               |
         |               |  |       |               |
         +---------------+  |       +---------------+
                 ^          |               ^
+-------+        |          +---------------+
|  CR3  |--------+
+-------+

接下来是代码实现：

在NEMU中，我们不会发生缺页的情况，因此，在进行page_translate()时，建议添加对页目录项和页表项中present==1的检查，若出现present为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
paddr_t page_translate(laddr_t laddr)
{
#ifndef TLB_ENABLED
    // 首先我们提取出三个部分
    uint32_t dir = (laddr >> 22) & 0x3ff;
    uint32_t page = (laddr >> 12) & 0x3ff;
    uint32_t offset = laddr & 0xfff;

    // 然后经过上图中的两步索引得到地址
    // 首先查找页目录项
    uint32_t pde = (cpu.cr3.pdbr << 12) + (dir << 2);
    PDE pde;
    pde.val = paddr_read(pde, 4);
    // 然后查找页表项
    uint32_t pte = (pde.page_frame << 12) + (page << 2);
    PTE pte;
    pte.val = paddr_read(pte, 4);

    // 这里是手册的建议
    assert(pde.present == 1);
    assert(pte.present == 1);

    // 返回值加上页内偏移
    // 这就是物理地址的布局（如果之前没提到的话）
    return (pte.page_frame << 12) | offset;
#else    
    return tlb_read(laddr) | (laddr & PAGE_MASK);
#endif
}

最后我们需要修改内核代码，借助已实现的函数 mm_malloc 完成对用户进程空间的分配：

 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
// /kernel/src/elf/elf.c
uint32_t loader()
{
    Elf32_Ehdr *elf;
    Elf32_Phdr *ph, *eph;

#ifdef HAS_DEVICE_IDE
    uint8_t buf[4096];
    ide_read(buf, ELF_OFFSET_IN_DISK, 4096);
    elf = (void *)buf;
    Log("ELF loading from hard disk.");
#else
    elf = (void *)0x0;
    Log("ELF loading from ram disk.");
#endif

    /* Load each program segment */
    ph = (void *)elf + elf->e_phoff;
    eph = ph + elf->e_phnum;
    for (; ph < eph; ph++)
    {
        if (ph->p_type == PT_LOAD)
        {
            // 你在 PA2-2 的时候对这里进行了初步的实现
            uint8_t *src = (uint8_t *)elf + ph->p_offset;
            uint32_t file_sz = ph->p_filesz;
            uint32_t mem_sz = ph->p_memsz;

// 针对分页机制的改动在这里
#ifdef IA32_PAGE
            uint8_t *dst = (uint8_t *)mm_malloc(ph->p_vaddr, ph->p_memsz);
#else
            uint8_t *dst = (uint8_t *)ph->p_vaddr;
#endif  
// 改动结束
            memcpy(dst, src, file_sz);

            if (mem_sz > file_sz) {
                memset(dst + file_sz, 0, mem_sz - file_sz);
            }

#ifdef IA32_PAGE
            /* Record the program break for future use */
            extern uint32_t brk;
            uint32_t new_brk = ph->p_vaddr + ph->p_memsz - 1;
            if (brk < new_brk)
            {
                brk = new_brk;
            }
#endif
        }
    }

    volatile uint32_t entry = elf->e_entry;

#ifdef IA32_PAGE
    mm_malloc(KOFFSET - STACK_SIZE, STACK_SIZE);
#ifdef HAS_DEVICE_VGA
    create_video_mapping();
#endif
    write_cr3(get_ucr3());
#endif
    return entry;
}

数据跨页的处理

以防你不知道，不处理这个也可以 PASS，因为数据跨页的概率远比数据跨 cache 槽的概率小，在 testcase 中并没有出现这种情况

正如之前处理 cache 数据跨块一样，我们需要处理地址访问跨越页边界的情形，这部分处理就和 cache 数据跨块处理非常相似了

 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
uint32_t laddr_read(laddr_t laddr, size_t len)
{  
    assert(len == 1 || len == 2 || len == 4);
#ifdef IA32_PAGE
    if (cpu.cr0.pg) {
        // page_limit 为下一页的首地址
        uint32_t page_limit = (laddr | 0xFFF) + 1;

        if (laddr + len > page_limit) {
            uint32_t low_len = page_limit - laddr;
            uint32_t high_len = len - low_len;

            paddr_t low_paddr = page_translate(laddr);
            paddr_t high_paddr = page_translate(laddr + low_len);

            uint32_t low_data = paddr_read(low_paddr, low_len);
            uint32_t high_data = paddr_read(high_paddr, high_len);

            return low_data | (high_data << (low_len << 3));
        } else {
            paddr_t paddr = page_translate(laddr);
            return paddr_read(paddr, len);
        }
    }
#endif
    return paddr_read(laddr, len);
}

附上之前 cache 读的代码，两者很像：

 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
uint32_t cache_read(paddr_t paddr, size_t len) {
    uint32_t offset = get_offset(paddr);

    // if cross the line, divided to two parts
    if (offset + len > BLOCK_SIZE) {
        uint32_t low_part = BLOCK_SIZE - offset;
        uint32_t low_data = cache_read(paddr, low_part);
        uint32_t high_part = len - low_part;
        uint32_t high_data = cache_read(paddr + low_part, high_part);

        return low_data | (high_data << (low_part << 3));
    }

    uint32_t set = get_set(paddr);
    uint32_t tag = get_tag(paddr);


    int way = find_way(set, tag);

    if (way == -1) {
        way = rand() % WAY_CNT;
        transfer(paddr, set, way);
    }
    uint32_t data = 0;
    memcpy(&data, cache[set][way].data + offset, len);
    return data;
}

写操作同理可得

My problems during the debugging

完成整个分页机制后一直出现段错误，两天查了五个小时才意识到是 mov_r2c_l 指令在 PA3-2 写错了

啊啊啊啊啊啊啊啊啊啊啊啊

😭😭😭😭😭😭😭😭😭😭😭