NEMU-PART III

PA3：存储管理

实现高速缓存

经过实践，高速缓存的一级和二级结构最好同时实现，否则会在分页控制中出现难以预料的bug！

定义高速缓存结构

新建文件/nemu/include/memory/cache.h，填写以下内容：

宏定义缓存块：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


#ifndef __CACHE_H__
#define __CACHE_H__

#include "common.h"

// 定义高速缓存参数
#define CACHE_E_L1 8
#define CACHE_E_L2 16
#define CACHE_BLOCK 64
#define CACHE_SIZE_L1 64*1024
#define CACHE_SIZE_L2 4*1024*1024

...

#endif

缓存块的结构体定义：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


// 定义一级缓存
struct cache_l1 {
    bool valid;
    int tag;
    uint8_t byte[CACHE_BLOCK];
} cache_L1[CACHE_SIZE_L1 / CACHE_BLOCK];

// 定义二级缓存
struct cache_l2 {
    bool valid;
    bool dirty;
    int tag;
    uint8_t byte[CACHE_BLOCK];
} cache_L2[CACHE_SIZE_L2 / CACHE_BLOCK];

// 定义高速缓存函数
void init_cache();
uint32_t cache_read_L1(hwaddr_t addr);
uint32_t cache_read_L2(hwaddr_t addr);
void cache_write_L1(hwaddr_t addr, size_t len, uint32_t data);
void cache_write_L2(hwaddr_t addr, size_t len, uint32_t data);

高速缓存的读写函数

新建文件/nemu/src/memory/cache.c

缓存的初始化

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


void init_cache(){
    int i;
    for(i = 0; i < CACHE_SIZE_L1 / CACHE_BLOCK; i++) {
        cache_L1[i].valid = false;
        cache_L1[i].tag = 0;
        memset(cache_L1[i].byte, 0, CACHE_BLOCK);
    }
    for(i = 0; i < CACHE_SIZE_L2 / CACHE_BLOCK; i++) {
        cache_L2[i].dirty = false;
        cache_L2[i].valid = false;
        cache_L2[i].tag = 0;
        memset(cache_L2[i].byte, 0, CACHE_BLOCK);
    }
}

读取缓存块中的内容

 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


uint32_t cache_read_L1(hwaddr_t addr) {
    // 取出地址中set的部分（右移block位并 & 1111111）
    // set = 7 byte (set = 2^s = 128)
    // offset = 6 byte (block = 2^e = 64)
    uint32_t set = (addr >> 6) & 0x7f; 
    bool hit = false;
    int i;
    // 一级缓存中找到相应set
    for(i = set * CACHE_E_L1; i < (set + 1) * CACHE_E_L1; i++) { 
        if(cache_L1[i].tag == (addr >> 13) && cache_L1[i].valid) { // 如果tag和地址相符合并且valid == true
            hit = true; 
            return i;
        }
    }
     
    // 一级缓存中找空内存块
    for(i = set * CACHE_E_L1; i < (set + 1) * CACHE_E_L1; i++) {
        // 找到空的地方退出
        if (!cache_L1[i].valid) {
            break; 
        }  
    }
    // 到最后仍然没有找到空的地方，执行随机替换算法
    if(i == (set + 1) * CACHE_E_L1) { 
        srand(0);
        i = set * CACHE_E_L1 + rand() % CACHE_E_L1;
    }
    cache_L1[i].valid = true;
    cache_L1[i].tag = addr >> 13;
    int j = cache_read_L2(addr);;
    memcpy(cache_L1[i].byte, cache_L2[j].byte, CACHE_BLOCK);
    
    return i;
}

uint32_t cache_read_L2(hwaddr_t addr){
    uint32_t s = (addr >> 6) & ((1 << 12) - 1);
    uint32_t block = (addr >> 6) << 6;
    int i;
    bool hit = false;
    for (i = s * CACHE_E_L2; i < (s + 1) * CACHE_E_L2; i++) {
        if (cache_L2[i].tag == (addr >> 18) && cache_L2[i].valid) {
            hit = true;
            break;
        }
    }
    if (!hit) {
        int j;
        for (i = s * CACHE_E_L2; i < (s + 1) * CACHE_E_L2; i++) {
            if (!cache_L2[i].valid)
                break;
        }
        if (i == (s + 1) * CACHE_E_L2) {
            srand(0);
            i = s * CACHE_E_L2 + rand() % CACHE_E_L2;
            if (cache_L2[i].dirty) {
                uint8_t mask[BURST_LEN * 2];
                memset(mask, 1, BURST_LEN * 2);
                for (j = 0; j < CACHE_BLOCK / BURST_LEN; j++) {
                    call_ddr3_write(block + j * BURST_LEN, cache_L2[i].byte + j * BURST_LEN, mask);
                }	
            }
        }
        cache_L2[i].valid = true;
        cache_L2[i].tag = addr >> 18;
        cache_L2[i].dirty = false;
        for (j = 0; j < BURST_LEN; j++){
            call_ddr3_read(block + j * BURST_LEN, cache_L2[i].byte + j * BURST_LEN);
        }
    }
    return i;
}

数据写入缓存块

 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


void cache_write_L1(hwaddr_t addr, size_t len, uint32_t data) {
    uint32_t set = (addr >> 6) & 0x7f;
    uint32_t offset = addr & (CACHE_BLOCK - 1); 
    int i;
    bool hit = false;
    for (i = set * CACHE_E_L1; i < (set + 1) * CACHE_E_L1; i++) {
        if (cache_L1[i].tag == (addr >> 13) && cache_L1[i].valid) {
            hit = true;
            break;
        }
    }
    // 写直通
    if (hit) { 
        memcpy(cache_L1[i].byte + offset, &data, len);
    }
    cache_write_L2(addr, len, data);
}

void cache_write_L2(swaddr_t addr, size_t len, uint32_t data) {
    uint32_t set = (addr >> 6) & ((1 << 12) - 1); 
    uint32_t offset = addr & 0x3f;	
    int i;
    bool hit = false;
    for (i = set * CACHE_E_L2; i < (set + 1) * CACHE_E_L2; i++) {
        if (cache_L2[i].tag == (addr >> 13) && cache_L2[i].valid) {
            hit = true;
            break;
        }
    }
    if (!hit){
        i = cache_read_L2(addr);
    }
    cache_L2[i].dirty = true;
    memcpy(cache_L2[i].byte + offset, &data, len);
}

修改内存读写逻辑

在/nemu/src/memory/memory.c中，修改hwaddr_read和hwaddr_write两个函数：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


uint32_t hwaddr_read(hwaddr_t addr, size_t len) {
    uint32_t offset = addr & (CACHE_BLOCK - 1);
    uint32_t block = cache_read_L1(addr);
    uint8_t temp[4];
    memset(temp, 0, sizeof(temp));
    if (offset + len >= CACHE_BLOCK) {
        uint32_t second_block = cache_read_L1(addr + len);
        memcpy(temp, cache[block].byte + offset, CACHE_BLOCK - offset);
        memcpy(temp + CACHE_BLOCK - offset, cache[second_block].byte, len - (CACHE_BLOCK - offset));
    } else {
        memcpy(temp, cache[block].byte + offset, len);
    }
    int zero = 0;
    uint32_t result = unalign_rw(temp + zero, 4) & (~0u >> ((4 - len) << 3));
    return result;
}

void hwaddr_write(hwaddr_t addr, size_t len, uint32_t data) {
    cache_write_L1(addr, len, data);
}

实现分段机制

修改kernel

首先需要在kernel中加入切换到保护模式的代码：在kernel/include/common.h中定义宏IA32_SEG，然后重新编译kernel。

1
2


- //#define IA32_SEG
+ #define IA32_SEG

这一步必须完成！如果你是CV大佬，很容易漏掉这个步骤！

定义段寄存器

在CPU_state结构中添加GDTR，CR0和各种段寄存器，包括CS, DS, ES, SS, 其具体结构参考i386手册。

在libcommon/x86-inc目录下的头文件中定义了一些和x86相关的宏和结构体，你可以在NEMU中包含这些头文件来使用它们。

 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


// 段寄存器
enum {R_ES, R_CS, R_SS, R_DS};

// 定义段寄存器结构体
typedef struct {
    uint16_t selector;
    uint16_t attribute;
    uint32_t limit;
    uint32_t base;
} Segment_Reg;

...

typedef struct {
    ...

    // GDTR寄存器
    struct GDTR {
        uint32_t base;
        uint16_t limit;
    } gdtr;

    // CR0和CR3寄存器由 /lib-common/x86-inc/cpu.h 定义
    CR0 cr0;
    CR3 cr3;

    // 设置段寄存器
    union {
        struct {
            Segment_Reg sreg[4];	
        };
        struct {
            Segment_Reg es, cs, ss, ds;
        };
    };

} CPU_state;

完善指令集

添加lgdt指令。
添加opcode为0F 20和0F 22的mov指令，使得我们可以设置/读出CR0。
添加opcode为8E的mov指令，使得我们可以设置段寄存器。
为了设置CS寄存器, 你需要实现ljmp指令

实现段寄存器的捆绑规则

在Operand结构体中添加成员sreg，位置：/nemu/include/cpu/decode/operand.h

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


typedef struct {
    uint32_t type;
    size_t size;
    union {
        uint32_t reg;
-       swaddr_t addr;
+		struct {
+			swaddr_t addr;
+			uint8_t sreg;
+		};
        uint32_t imm;
        int32_t simm;
    };
    uint32_t val;
    char str[OP_STR_SIZE];
} Operand;

修改所有调用swaddr_read()和swaddr_write()的代码，为它们添加段寄存器的参数。具体要求如下：

指令	实现要求
`opcode`为`A0`, `A1`, `A2`, `A3` 的`mov`指令	使用`DS`寄存器
一些堆栈操作指令	隐式使用`SS`寄存器
`instr_fetch()`	总是使用`CS`寄存器
`monitor`中，`x`和`p`命令读出内存时	使用`DS`寄存器
`bt`命令打印栈帧链	使用`SS`寄存器
字符串操作指令使用的段寄存器	请查阅 i386 手册

修改内存读写函数

设置CR0后，如果发现CR0的PE位为 1，则进入IA-32保护模式，从此所有虚拟地址的访问（包括swaddr_read()和 swaddr_write()）都需要经过段级地址转换。

为了实现段级地址转换，需要对/nemu/src/memory/memory.c中的swaddr_read()和swaddr_write()函数作少量修改：

1
2
3
4
5
6
7
8
9


uint32_t swaddr_read(swaddr_t addr, size_t len) {
#ifdef DEBUG
    assert(len == 1 || len == 2 || len == 4);
#endif
    lnaddr_t lnaddr = seg_translate(addr, len, current_sreg);
    return lnaddr_read(lnaddr, len);
}

// swaddr_write()函数采取类似操作

其中sreg记录了当前段级地址转换所用到的段寄存器的编码。关于段寄存器的编码，请查阅i386手册。

然后实现seg_translate()函数。再次提醒，在 NEMU 中，只有进入保护模式之后才会进行段级地址转换。

1
2
3
4
5
6
7
8


lnaddr_t seg_translate(swaddr_t addr, size_t len, uint8_t sreg_id) {
    if (cpu.cr0.protect_enable == 0) {
        return addr;
    }
    else {
        return cpu.sreg[sreg_id].base + addr;
    }
}

实现分页机制

思考题

GDT能有多大

段选择符的结构中，INDEX有13位，故GDT最大能容纳2^13个段描述符

为什么是线性地址？

不可以。虚拟地址需要经GDT中的段表翻译才能得出地址，而如果GDTR中存放虚拟地址则找不到GDT在哪里了。

如何提高寻找段描述符的效率

可以按照高速缓存的思想，建立类似cache 和 TLB 的结构来提高寻找效率。

段式存储管理的缺点

分段管理要求分配一大段连续的存储空间，难以实现并且容易造成大量的外部碎片出现。

页式存储管理的优点

没有外部碎片，并且不再需要大段连续的存储空间，提高了内存的利用率。

一些问题

Q：为什么页表表项中的基地址信息只有20位而不是32位

A：分页基地址有20位是8086的传统，在8086的分段机制中，每个段的基地址由seg_reg（即段寄存器的值）«4得到，而段寄存器是16位的，左移4位得到20位的基地址。

Q：表项和CR3中的基地址都是物理地址，这是必须的吗？能否采用虚拟地址或者线性地址？

A：是必须的，如果cr3中的基地址是虚拟地址，则无从寻找页表翻译成物理地址，进入鸡生蛋蛋生鸡的死循环。至于其他表项的虚拟地址与线性地址问题同理。

Q：为什么不采用一级页表？采用一级页表会有什么缺点？

A：多级页表可以有效地节约内存空间，如果仅采用一级页表，将可能导致较大的页表长期驻留在内存中。

空指针是“空”的吗？

空指针只是未分配或者未指向内存任何位置的指针，并不是“NULL”的。

在扁平模式下如何进行保护

对于数据有不同的访问权限，未达到需要的权限时不能进行写操作

地址映射
分页机制

因为这里定义的ｘ生成的地址是虚拟地址，超过了物理地址的界限，报错0xc014a000 outside of the physical memory。而kvm.c中的虚拟地址都经过了va_to_pa的转换，在物理地址范围之内。

进行反汇编后，其地址如下：

c01003d6: e8 65 09 00 00 call c0100d40

该call指令的opcode为e8，实现的是跳转到：该条指令的下一条指令的首地址+偏移量的位置。由于未进行寻址，故不需要进行虚实地址转化。

分页的环境下，在没有初始化页表时，0～128M的虚拟地址到物理地址的映射相当于一个简易的页表，使得高位的地址可以通过该虚拟地址（即经过va_to_pa）访问到物理地址，从而进行初始化页表的操作。

init_mm()函数执行退出时。该函数将nemu映射到了高位地址并且将之前的PDE全部置为无效，此时返回main.c时，栈中保存的返回地址需要经过虚实转换，可由于页面被置为了无效，所以报错。查看汇编代码，直接调用此函数时，nemu运行在物理地址上，由于在init_mm中将之前的PDE都置为无效，所以在loader()函数寻址时页面无效，导致报错。