计算机系统基础综合实践 PA3

高速缓存及MMU

PA3主要实现高速缓存、分段、分页机制。

前言

此次PA是为了理解高速缓存的机制以及从逻辑地址到线性地址（分段）、线性地址到物理地址（分页）之间的关系。

实验内容

  • 阶段 1: 实现 cache（必做）和二级 cache（选做）
  • 阶段 2: 实现 IA-32 分段机制
  • 阶段 3：实现 IA-32 分页机制

开始实验

高速缓存

在计算机系统中，其实内存的速度相对于cpu来说是非常慢的，这时候就需要有一个cache来弥补这种差异上的速度，而内存又可以分成两种，分别为SRAM和DRAM。

DRAM和SRAM的电路图

image-20240901125152512

DRAM中的一个电容用来存储一个bit，而晶体管则充当一个开关。当电容的电量大于50%，就被认为为1，否则为0。由于电容是会漏电的，所以我们还要不断地为电容充电，让DRAM定时刷新，以确保正确性。而CPU的寄存器采用SRAM，是通过一个触发器来存储1个bit，只要不断电，SRAM中存储的数据就不会丢失。可以看到SRAM相比DRAM的电路来得相对更复杂，所以SRAM的成本远远超过DRAM。

存储器金字塔层次结构

image.png

为了解决CPU和存储器之间速度的差距，又由于SRAM的成本远远高于DRAM，所以引进了高速缓存的概念。CPU在最上层，速度就是最快的。SRAM在第二层次，其中又可分为L1、L2、L3等高速缓存。第三层对应着主存DRAM，第四层就是我们说的SSD，第五层便是HDD了。这里的金字塔层次结构由上至下的形式也表示了存储器的从小到大。

高速缓存的原理就是利用时间局部性和空间局部性来达到加速的效果。例如当程序访问了一个内存区间，那么这个内存区间很有可能在不久的将来再次被访问，而这个内存区间周围的邻近区间也很有可能会被访问，前后者分别对应着时间局部性和空间局部性。我们把cache向内存进行读写的基本单位称为block。所以只要CPU访问cache的时候命中所需要的内存区间，就不需要浪费很多时间去访存了。但是这也带来了一系列的问题。例如一个内存区域可以分为几个block？由于cache是有限的，当一个block持续地被写cache、出cache时，如何解决这样的冲突？冲突的时候，需要替换哪个block？这就涉及到了替换算法。当写cache的时候需不需要每次都写回内存里？等等一系列问题，所以cache又可以表示成多种形式。

  • 直接映射（Direct-Mapped Caches）
  • 组相连映射（ Set Associative Caches）
  • 全相连映射（ Fully Associative Caches）

这些问题太多太多，懒惰写了，可参考：多图详解CPU Cache Memory - 云+社区 - 腾讯云 (tencent.com)

高速缓存结构

image.png

这个便是高速缓存的结构。高速缓存被组织成S = 2^s 个set，每个set包含E个line。每个line由一个B = 2^b bit的block、一个valid以及一个tag组成。当高速缓存命中的时候，就是tag和valid被校验成功，这时候就可以取出cache中的存储单位（block），这个存储单位通常以1个字节为单位。当高速缓存不命中的时候，这时候CPU才要去内存中取，之后便会根据时间局部性和空间局部性相关的算法以及策略放进cache里。

必做任务 1：实现一级 Cache

需要实现一个64KB的cache，block为64B，八路组相联映射高速缓存，并且其中的替换算法为随机替换算法，写直通策略。

nemu/include/memory/cache.h

#ifndef __CACHE_H__
#define __CACHE_H__

#include "common.h"

#define E 8
#define CACHE_BLOCK 64
#define CACHE_SIZE 64*1024

struct cache_l1 {
    bool valid;
    int tag;
    uint8_t byte[CACHE_BLOCK];
} cache[CACHE_SIZE / CACHE_BLOCK];

uint64_t cnt;

void init_cache();
uint32_t cache_read(hwaddr_t addr);
void cache_write(hwaddr_t addr,size_t len,uint32_t data);

#endif

定义cache的结构，并且声明了三个函数，分别为初始化cache以及要实现的读写函数。

nemu/src/memory/cache.c

#include "common.h"
#include "memory/cache.h"
#include "burst.h"
#include "stdlib.h"

uint32_t dram_read(hwaddr_t addr, size_t len);
void call_ddr3_read(hwaddr_t, void *);
void call_ddr3_write(hwaddr_t, void *, uint8_t *);

void init_cache(){
    int i;
    for (i = 0; i < CACHE_SIZE / CACHE_BLOCK; i++){
        cache[i].valid = false;
        cache[i].tag = 0;
        memset(cache[i].byte, 0, CACHE_BLOCK);
    }
    cnt = 0;
}

uint32_t cache_read(hwaddr_t addr) {
    uint32_t set = (addr >> 6) & 0x7f; //取出地址中set的部分（右移block位并 & 1111111），set = 7 byte (set = 2^s = 128), offset = 6 byte (block = 2^e = 64)
    bool hit = false;
    int i;
    for (i = set * E; i < (set + 1) * E; i++) { //找到相应set所在
        if (cache[i].tag == (addr >> 13) && cache[i].valid) { //如果tag和地址相符合并且alid == true
            hit = true; 
            cnt += 2;
            break;
        }
    }
    if (!hit) { //找不到
        for (i = set * E; i < (set + 1) * E; i++) { //去到相应set所在
            if (!cache[i].valid) //找到空的地方退出
            break; 
        }
        if (i == (set + 1) * E) { // 到最后仍然没有找到空的地方，执行随机替换算法
            srand(0);
            i = set * E + rand() % E;
        }
        cache[i].valid = true;
        cache[i].tag = addr >> 13;
       int j;
       uint32_t block = (addr >> 6) << 6; // 取出block
         for (j = 0; j < BURST_LEN; j++) {
            call_ddr3_read(block + j * BURST_LEN, cache[i].byte + j * BURST_LEN); 
         }
        cnt += 200;
    }
    return i;
}

void cache_write(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 * E; i < (set + 1) * E; i++) {
        if (cache[i].tag == (addr >> 13) && cache[i].valid) {
            hit = true;
            break;
        }
    }
    if (hit) { // 写直通
        memcpy(cache[i].byte + offset, &data, len);
    }     
    else {
        i = cache_read(addr);
         memcpy(cache[i].byte + offset, &data, len);
    }
}

理解了cache的原理就很好实现了。这里有一个变量cnt用来观察成功实现了cache后，运行用户程序所需要的时间。

nemu/src/memory/dram.c

// ...
void call_ddr3_read(hwaddr_t addr, void *data){
	ddr3_read(addr,data);
}

void call_ddr3_write(hwaddr_t addr, void *data, uint8_t *mask){
	ddr3_write(addr,data,mask);
}

这两个函数实际上就是调用ddr3里的函数，作为一个接口。

nemu/src/monitor/monitor.c

void restart() {
// ...
	/* Initialize cache */
	init_cache();
// ...
}

然后需要在restart中对cache进行一个初始化操作。

nemu/src/monitor/memory/memory.c

uint32_t hwaddr_read(hwaddr_t addr, size_t len) {
	uint32_t offset = addr & (CACHE_BLOCK - 1);
	uint32_t block = cache_read(addr);
	uint8_t temp[4];
	memset(temp, 0, sizeof(temp));
	if (offset + len >= CACHE_BLOCK) {
		uint32_t second_block = cache_read(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));
	//printf("time: %ld\n", cnt);
	return result;
}

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

最后要在修改两个函数，就不是直接读写DRAM了，需要先调用cache，当cache缺失的时候才读写DRAM。

选做任务 1：实现二级 Cache

这里其实和实现L1的cache很类似，L2相比L2需要加上一个dirty位。当L1如果不命中，需要到L2里去找，最后当L2缺失的时候，才去DRAM里找。相关代码就不再贴出了。

分段机制

在16位的时代，所有寄存器都是16位，所以访存最大的范围也只是在2^16 = 64KB，所以这时候引进了一个伟大的概念，叫做分段。分段其实就是把内存分成一段一段，并且增加了一些16位的寄存器来协助寻址，这些寄存器称为段寄存器，里面存储着段基地址。段基地址* 16 + 偏移量 = 物理地址，利用段寄存器就可以访问到2^20 = 1MB的内存了。当程序需要执行的时候，就要确定程序相应的区域各自要放在哪里，这时候这四个段寄存器就会分别指向这些起始位置，这是约定俗成，现在也是如此。

  • 代码段寄存器CS：存放当前执行的程序的段地址。
  • 数据段寄存器DS：存放当前执行的程序所用操作数的段地址。
  • 堆栈段寄存器SS：存放当前执行的程序所用堆栈的段地址。
  • 附加段寄存器ES：存放当前执行程序中一个辅助数据段的段地址。

到了32位的时代，由于历史和兼容性原因，段寄存器必须保留，但是所有的寄存器都已经是32位了，一个段寄存器只有16位，是无法放下一个32位的基地址的。所以intel想了一个牛逼的办法，把一个段的各种属性放在一起，形成一个新的概念，叫做段描述符。这个段描述符是64位的，intel把所有的段描述符放在一个数组当中，称作全局描述符表GDT（Global Descriptor Table），段寄存器则用来充当这个数组的索引，这时候段寄存器就被称作段选择符。除了全局描述符表，还有中断描述符表IDT（Interrupt Descriptor Table）以及局部描述符表LDT（Local Descriptor Table）。

段选择符结构

img

段描述符结构

img

这时候必须要有一个指向全局唯一的GDT的寄存器，intel把它称作GDTR。这个GDTR里存的必然是线性地址，因为分段机制就是把逻辑地址转为线性地址的过程，如果这个GDTR里存放的是逻辑地址，那也没有其他机制能把GDTR里的地址从逻辑地址转为线性地址了。

逻辑地址转线性地址的过程

img

所以寻址的过程就变成：

  1. 首先要有通用寄存器的32位有效地址，也可以称作段内偏移。
  2. 根据段选择符中的TI决定在哪个描述符表中取值。
  3. 找到相应的描述符表后，利用描述符表寄存器里的值找到描述符表的首地址，并且加上段描述符中的索引 * 8 （段描述符占8字节）。
  4. 比较RPL和DPL和当前进程的CPL，这是x86的保护机制（必须满足DPL >= RPL && DPL >=CPL）。
  5. 最后将段描述符中的32位地址和有效地址相加，得到32位线性地址。

必做任务2：在 NEMU 中实现分段机制

在寄存器结构体中添加段寄存器后，需要编写一个lgdt指令，这个指令是用来加载全局描述符表的。之后要完善未实现的一些指令，运行NEMU的时候会指示出来。mov指令中要设置cr0，进入分段机制。修改两个函数swaddr_read()和 swaddr_write()，使其实现分段机制的转换。在有使用到段寄存器的指令中设置对应的段寄存器，有些函数也要进行设置，例如instr_fetch()和read_ModR_M()，并且之前实现的有些打印操作也要设置相应的段寄存器。实现Opcode为8E的mov指令后需要设置段寄存器，在里面调用sreg_load()用来拼接属性。切到保护模式后取址操作要用到CS寄存器，要先在restart()函数中初始化CS寄存器。设置CS寄存器则要实现ljmp指令。下面会贴出一些比较关键的代码。

nemu/include/cpu/reg.h

enum { R_ES, R_CS, R_SS, R_DS, R_FS, R_GS};
typedef struct {
  uint16_t selector;
  uint16_t attribute; // type (is read or write or excutive)
  uint32_t limit; //length (base + limit = segment size)
  uint32_t base; // base address
} Segment_Reg;

typedef struct {
    // ...
struct GDTR {
    uint32_t base;
    uint16_t limit;
  } gdtr;

  CR0 cr0;

  union {
    struct {
      Segment_Reg sreg[6];
    };
    struct {
      Segment_Reg es, cs, ss, ds, fs, gs;
    };
  };

  CR3 cr3;
} CPU_state;

typedef struct{
  union{
    struct{
      uint16_t limit1;
      uint16_t base1;
    };
    uint32_t part1;
  };
  union{
    struct{
      uint32_t base2:		8; //base address
      uint32_t a:			1; //is access
      uint32_t type:		3; //type
      uint32_t s:			1; //is data OR code segment
      uint32_t dpl:		2; //privilage
      uint32_t p:			1;  // is exist
      uint32_t limit2:	4;  //limit (segment length - 1)
      uint32_t avl:		1; //user
      uint32_t :			1; //32bit
      uint32_t x:			1; //16bit
      uint32_t g:			1; // page unit or byte unit (0 == 1 byte, 1 == 4kb)
      uint32_t base3:		8; //base address
    };
    uint32_t part2;
  };
} Sreg_Descriptor;

Sreg_Descriptor *sreg_desc;
void sreg_load(uint8_t);
uint8_t current_sreg;

Sreg_Descriptor则结构体是段描述符。Segment_Reg是参照着Sreg_Descriptor定义的结构体。sreg_load()这个函数要自己实现。这里我声明了一个变量current_sreg用来判断当前要使用哪个段寄存器，也可以依照实验指导书中的指示修改MEM_W() 和 MEM_R()这两个宏。

nemu/src/cpu/reg.c

void sreg_load(uint8_t sreg_num) {
  Assert(cpu.cr0.protect_enable, "Not In Protect Mode!");

  uint16_t idx = cpu.sreg[sreg_num].selector >> 3;

  Assert((idx << 3) <= cpu.gdtr.limit, "Segement Selector Is Out Of The Limit!");

  lnaddr_t chart_addr = cpu.gdtr.base + (idx << 3);
  sreg_desc -> part1 = lnaddr_read(chart_addr, 4);
  sreg_desc -> part2 = lnaddr_read(chart_addr + 4, 4);

  Assert(sreg_desc -> p == 1, "Segement Not Exist!");
  uint32_t bases = 0;

  bases += ((uint32_t)sreg_desc -> base1);

  bases += ((uint32_t)sreg_desc -> base2) << 16;

  bases += ((uint32_t)sreg_desc -> base3) << 24;
  cpu.sreg[sreg_num].base = bases;

  uint32_t limits = 0;
  limits += ((uint32_t)sreg_desc -> limit1);
  limits += ((uint32_t)sreg_desc -> limit2) << 16;
  limits += ((uint32_t)0xfff) << 24;
  cpu.sreg[sreg_num].limit = limits;
  if (sreg_desc -> g == 1) {
      cpu.sreg[sreg_num].limit <<= 12;//G = 0, unit = 1B;G = 1, unit = 4KB
  }
  return ;
}

这个函数的作用是来拼接一些属性的，在Opcode为8E的mov指令中调用。

nemu/src/memory/memory.c

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;
  }
}

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

void swaddr_write(swaddr_t addr, size_t len, uint32_t data) {
#ifdef DEBUG
  assert(len == 1 || len == 2 || len == 4);
#endif
  lnaddr_t lnaddr = seg_translate(addr, len, current_sreg);
  lnaddr_write(lnaddr, len, data);
}

seg_translate()中判断是否在保护模式，如果是的话，返回描述符表基地址+索引+有效地址。然后对swaddr_read()和swaddr_write()这两个函数进行修改，实现分段地址的转换。

nemu/src/monitor/monitor.c

static void init_CS(){
	cpu.cs.base = 0;
  	cpu.cs.limit = 0xffffffff;
}

static void init_cr0(){
	cpu.cr0.protect_enable = 0; //real mode turn to protect mode
	//cpu.cr0.paging = 0; //page mode
}

void restart() {
    // ...
 	/* Initialize CR0. */
	init_cr0();
	
	/* Initialize CS. */
	init_CS();   
}

根据实验指导书中的指示初始化CS寄存器和cr0，分段机制也就实现了。

分页机制

由于分段机制中段的大小不固定，在段的换入换出中会产生很多内存碎片，从而导致浪费很多内存空间，所以又迎来了分页机制。页的大小是固定且是系统决定的，并且产生的碎片很少，可以说分页模式是为了解决分段模式的缺点而产生的。

线性地址转物理地址的过程

img

分页机制采用两级页表的形式，并且也有一个寄存器CR3存储着页目录基地址。由分段机制得到的线性地址可以分成三个部分，分别为页目录表索引、页表索引、页内偏移量。Linux中的页目录中的页目录项一共有1K个，而每个页目录项又拥有1K个页项，每个页项大小为4KB。

页目录项和页表项的格式

img

所以分页机制的寻址过程就是：

  1. 由页目录基地址 + 页目录表索引 * 4（每个表项占4个字节）得到页目录表中对应的页目录项。
  2. 页目录项 + 页表索引 * 4得到第二级页表中的页项。
  3. 页项 + 页内偏移量得到相应的物理地址。

必做任务 3：在 NEMU 中实现分页机制

首先要添加CR3寄存器，并且也要初始化CR0寄存器中的paging。修改 lnaddr_read()和 lnaddr_write()函数，实现分页机制。之后根据实验指导书中指示的部分把需要修改的部分修改，最后要在nemu/kerne/src/elf/elf.c中调用内存分配的接口函数mm_malloc()。

nemu/src/memory/memory.c

hwaddr_t page_translate(lnaddr_t addr) {
  if (cpu.cr0.protect_enable == 1 && cpu.cr0.paging == 1) {
    uint32_t dir = addr >> 22;
    uint32_t page = (addr >> 12) & 0x3ff;
    uint32_t offset = addr & 0xfff;

    int i = read_tlb(addr);
    if (i != -1) {
      return (tlb[i].page_num << 12) + offset;
    }
    uint32_t dir_start = cpu.cr3.page_directory_base;
    uint32_t dir_position = (dir_start << 12) + (dir << 2);
    Page_Descriptor first_content;
    first_content.val = hwaddr_read(dir_position, 4);
    Assert(first_content.p, "pagevalue = %x eip = %x", first_content.val,cpu.eip);
    uint32_t page_start = first_content.addr;
    uint32_t page_pos = (page_start << 12) + (page << 2);
    Page_Descriptor second_content;
    second_content.val =  hwaddr_read(page_pos, 4);
    Assert(second_content.p == 1, "Page Cannot Be Used!, %x", cpu.eip);
    uint32_t addr_start = second_content.addr;
    hwaddr_t hwaddr = (addr_start << 12) + offset;
    write_tlb(addr, hwaddr);
    return hwaddr;
  } else {
    return addr;
  }
}

uint32_t lnaddr_read(lnaddr_t addr, size_t len) {
  assert(len == 1 || len == 2 || len == 4);
  uint32_t now_offset = addr & 0xfff;
  if (now_offset + len - 1 > 0xfff) {
    size_t len1 = 0xfff - now_offset + 1;
    size_t len2 = len - len1;
    uint32_t addr_len1 = lnaddr_read(addr, len1);
    uint32_t addr_len2 = lnaddr_read(addr + len1, len2);
    uint32_t value = (addr_len2 << (len1 << 3)) | addr_len1;
    return value;

  } else {
    hwaddr_t hwaddr = page_translate(addr);
    return hwaddr_read(hwaddr, len);
  }
}

void lnaddr_write(lnaddr_t addr, size_t len, uint32_t data) {
  assert(len == 1 || len == 2 || len == 4);
  uint32_t now_offset = addr & 0xfff;
  if (now_offset + len - 1 > 0xfff) {
    size_t len1 = 0xfff - now_offset + 1;
    size_t len2 = len - len1;
    lnaddr_write(addr, len1, data & ((1 << (len1 << 3)) - 1));
    lnaddr_write(addr + len1, len2, data >> (len1 << 3));
  } else {
    hwaddr_t hwaddr = page_translate(addr);
    hwaddr_write(hwaddr, len, data);
  }
}

page_translate()要判断是否已经开启了分段和分页的机制，之后就可以实现分页机制的转换。tlb是类似cache的一种，调用这两个函数read_tlb()和write_tlb()前需要实现先tlb，之后会说到。

kernel/src/elf/elf.c

// ...	
	for(i = 0; i < elf->e_phnum; i++) {
		/* Scan the program header table, load each segment into memory */
		if(ph->p_type == PT_LOAD) {
			
			ph->p_vaddr = mm_malloc(ph->p_vaddr,ph->p_memsz);
			uint32_t pa = ph->p_vaddr;

			/* TODO: read the content of the segment from the ELF file 
			 * to the memory region [VirtAddr, VirtAddr + FileSiz)
			 */
			ramdisk_read((void *)pa,ph->p_offset,ph->p_filesz);
			 
			/* TODO: zero the memory region 
			 * [VirtAddr + FileSiz, VirtAddr + MemSiz)
			 */
			memset((void*)pa+ph->p_filesz,0,ph->p_memsz-ph->p_filesz);
			
			ph ++;

// ...

调用内存分配的mm_malloc()函数，至此开启了分页机制。

选做任务 2：简易调试器

只是需要在nemu/src/memory/memory.c增加一个和page_translate类似的函数，实现方式差不多是相同的，之后在nemu/src/monitor/debug/ui.c**添加相应的指令即可，代码就不贴出来了。

选做任务 3：为用户进程创建 video memory 映射

没做。

必做任务 4：实现 TLB

和之前实现高速缓存的概念是差不多的，利用TLB和局部性原理存储一些地址。如果tlb命中，已经转换过的地址不再需要经过分段和分页机制进行转换，从而改善转换速度。

kernel/include/memory/tlb.h

#ifndef __TLB_H__
#define __TLB_H__

#include "common.h"

#define TLB_SIZE 64

typedef struct{
    bool valid_value;
    uint32_t tag, page_num;
} TLB;

TLB tlb[TLB_SIZE];

void init_tlb();
int read_tlb(uint32_t addr);
void write_tlb(uint32_t lnaddr, uint32_t hwaddr);

#endif

定义tlb的结构。

kernel/src/memory/tlb.c

#include "common.h"
#include "memory/tlb.h"
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include "burst.h"

void init_tlb() {
  int i;
  for (i = 0; i < TLB_SIZE; i++) {
    tlb[i].valid_value = false;
  }
  return ;
}

int read_tlb(uint32_t addr) {
  int dir = addr >> 12;
  int i;
  for (i = 0; i < TLB_SIZE; i++) {
    if (tlb[i].tag == dir && tlb[i].valid_value) {
      return i;
    }
  }
  return -1;
}

void write_tlb(uint32_t lnaddr, uint32_t hwaddr_t) {
  int dir = lnaddr >> 12, page_num = hwaddr_t >> 12;
  int i;
  for (i = 0; i < TLB_SIZE; i++) {
    if (!tlb[i].valid_value) {
      tlb[i].valid_value = true;
      tlb[i].tag = dir;
      tlb[i].page_num = page_num;
      return ;
    }
  }
  srand(time(0));
  i = rand() % TLB_SIZE;
  tlb[i].valid_value = true;
  tlb[i].tag = dir;
  tlb[i].page_num = page_num;
  return ;
}

实现tlb后，最后在nemu/src/memory/memory.c中的page_translate()调用即可。