lab2_report

lab2_report

Charles Lv7
  2023-03-13 13:22 2023-03-13 13:22 Created   2023-11-05 21:36:18 2023-11-05 21:36:18 Updated      5.3k Words  19 Mins  

lab2_report

advance

实现物理内存和虚拟内存的管理方式

在lab2实验中物理内存采用链表法进行管理，而虚拟内存采用二级页表进行管理。本实验相关的映射与寻址规则（内存布局）如下

  • 若虚拟地址处于 0x80000000~0x9fffffff (kseg0)，则将虚拟地址的最高位置 0 得到物理地址，通过 cache 访存。这一部分用于存放内核代码与数据结构。

  • 若虚拟地址处于 0xa0000000~0xbfffffff (kseg1)，则将虚拟地址的最高 3 位置 0 得到物理地址，不通过 cache 访存。这一部分可以用于映射外设。

  • 若虚拟地址处于 0x00000000~0x7fffffff (kuseg)，则需要通过 TLB 来获取物理地址，通过 cache 访存。

在R3000 中，使用 MMU 来完成上述地址映射，MMU 中是采用硬件 TLB 来完成地址映射。在 R3000 中，需要通过软件填写 TLB 。所有低 2GB 空间的内存访问操作都需要经过 TLB。

image-20230313131725622

对于本次实验而言，主要在代码中利用PADDR和KADDR两个宏实现了kseg0虚拟地址和物理地址之间的转化。

lab_thinkings

Thinking 2.1

question

请根据上述说明，回答问题：在编写的 C程序中，指针变量中存储的地址是虚拟地址，还是物理地址？MIPS 汇编程序中 lw 和 sw 使用的是虚拟地址，还是物理地址？

answer

正如教程中所说的那样——MIPS R3000 发出的地址均为虚拟地址，因此如果程序想访问某个物理地址，需要通过映射到该物理地址的虚拟地址来访问。CPU只会发出经过产生处理后的虚拟地址，因此在编写的 C程序中指针变量中储存的是虚拟地址。MIPS汇编程序中lw、sw中使用的也是虚拟地址。

Thinking 2.2

question

  • 从可重用性的角度，阐述用宏来实现链表的好处。

  • 查看实验环境中的 /usr/include/sys/queue.h，了解其中单向链表与循环链表的实现，比较它们与本实验中使用的双向链表，分析三者在插入与删除操作上的性能差异。

answer

使用宏定义对链表操作进行封装，可以实现代码的复用，既减少了工作量，也提高了程序的可读性，而且从健壮性的角度而言，这样的改变很好的使指针的编写错误可能性大大降低。

对于单向链表、循环链表和双向链表而言，这三者的操作性能有以下的差异——

  • 对于单向链表，由于它只能获得每一项的后面一项，因此在删除时需要遍历整个链表；同样，如果是在某一项的前面插入，也需要从head开始遍历这个链表。但是如果是“在某一项之后插入”，单项链表可以直接进行该操作。

  • 对于循环链表，因为它仍然是单向的，所以在“删除”、“某一项之前插入”、“某一项之后插入”三个操作的性能和单项链表相同。但是，由于循环链表首尾相连，同时维护了一个指向尾项的指针，因此它可以直接在尾部插入。

  • 对于双向链表，因为它可以直接获得某一项的前后两项，所以无论是“删除”还是“在某一项前或后插入”都可以以O(1)的开销实现。但是，双向链表没有维护指向尾部的指针，因此无法直接将某一项插入链表尾部，如要实现该操作还需要遍历整个链表。

综上所述，循环链表和双向链表可以说是在单向链表的基础上完成的两种优化方式，分别完成了尾部插入和逆向插入的难题，但均依旧存在一些缺点。

Thinking 2.3

question

请阅读 include/queue.h 以及 include/pmap.h, 将 Page_list 的结构梳理清楚，选择正确的展开结构。

1
2
3
4
5
6
7
8
9
10
A:
struct Page_list{
	struct {
		struct {
			struct Page *le_next;
			struct Page **le_prev;
		}* pp_link;
		u_short pp_ref;
	}* lh_first;
}
1
2
3
4
5
6
7
8
9
10
B:
struct Page_list{
	struct {
		struct {
			struct Page *le_next;
			struct Page **le_prev;
		} pp_link;
		u_short pp_ref;
	} lh_first;
}
1
2
3
4
5
6
7
8
9
10
C:
struct Page_list{
	struct {
		struct {
			struct Page *le_next;
			struct Page **le_prev;
		} pp_link;
		u_short pp_ref;
	}* lh_first;
}
answer

选项C正确，理由如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#define LIST_HEAD(name, type)                                                                      \
	struct name {                                                                              \
		struct type *lh_first;                                         \
	}
LIST_HEAD(Page_list, Page);
#define LIST_ENTRY(type)                                                                           \
	struct {                                                                                   \
		struct type *le_next;  /* next element */                                          \
		struct type **le_prev; /* address of previous next element */                      \
	}
typedef LIST_ENTRY(Page) Page_LIST_entry_t;
struct Page {
	Page_LIST_entry_t pp_link; 
	u_short pp_ref;
};

将上面各部分分别带入即可。

Thinking 2.4

question

请思考下面两个问题：

  • 请阅读上面有关 R3000-TLB 的描述，从虚拟内存的实现角度，阐述 ASID 的必要性。

  • 请阅读《IDT R30xx Family Software Reference Manual》的 Chapter 6，结合 ASID段的位数，说明 R3000 中可容纳不同的地址空间的最大数量。

answer

ASID(Address Space IDentifier)用于区分不同的地址空间。查找 TLB 表项时，除了需要提供 VPN，还需要提供**ASID。具体而言，操作系统会给每一个进程分配一个页表，每个页表都有自己的虚拟地址空间，而同一虚拟地址在不同地址空间中通常映射到不同的物理地址。如果没有ASID来区分当前虚拟地址是在哪个进程中使用**，则可能会将该虚拟地址映射到错误的物理地址。

image-20230314075709706

ASID在EntryHi寄存器中占6位，可以被设置为64个不同的值，因此R3000中可最多容纳64个不同的地址空间。

Thinking 2.5

question

请回答下述三个问题：

  • tlb_invalidate 和 tlb_out 的调用关系？

  • 请用一句话概括 tlb_invalidate 的作用。

  • 逐行解释 tlb_out 中的汇编代码。

answer

我们通过 tlb_invalidate 实现删除特定虚拟地址在 TLB 中的旧表项，函数的主要逻辑位于 kern/tlb_asm.S 中的 tlb_out 中。即tlb_invalidata函数中调用了tlb_out函数。

在页表内容改变后及时更新TLB,从而实现删除特定虚拟地址在 TLB 中的旧表项。

tlb_out作用实际上就是使得某一虚拟地址对应的tlb表项失效，基本思路是——先将要查找的虚拟地址存入EntryHi寄存器，然后调用tlbp指令在TLB中查找（此时Index寄存器中保存了找到的对应表项的索引）。如果没有找到（索引小于0），则直接跳到最后；如果找到了，将索引对应的tlb项清空（需要将EntryHi和EntryLo寄存器清零后使用tlbwi指令）。注意在函数最后需要将“调用该函数前EntryHi寄存器中的值恢复”。具体过程见下方注释：

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
LEAF(tlb_out)
.set noreorder
       mfc0    t0, CP0_ENTRYHI		#将EntryHi寄存器的值存入t0寄存器
       mtc0    a0, CP0_ENTRYHI		#将a0中的值存入EntryHi寄存器
       nop
       /* Step 1: Use 'tlbp' to probe TLB entry */
       /* Exercise 2.8: Your code here. (1/2) */
       tlbp 						#根据EntryHi在TLB中查找与之对应的表项，并把表项的索引存入Index寄存器
	nop
       nop
       /* Step 2: Fetch the probe result from CP0.Index */
       mfc0    t1, CP0_INDEX		#将Index寄存器的值存入t1寄存器
.set reorder
       bltz    t1, NO_SUCH_ENTRY	#如果t1值小于零，即没有在TLB中找到EntryHi对应的表项，则跳转到NO_SUCH_ENTRY标签处
		nop
.set noreorder
       mtc0    zero, CP0_ENTRYHI	#将EntryHi寄存器赋值为0
       mtc0    zero, CP0_ENTRYLO0 	#将EntryLo0寄存器赋值为0
		nop
       nop
       /* Step 3: Use 'tlbwi' to write CP0.EntryHi/Lo into TLB at CP0.Index      */
       /* Exercise 2.8: Your code here. (2/2) */
       tlbwi						#将EntryHi和EntryLo0寄存器中的值存取Index对应的TLB表项中
NOFOUND:
.set reorder

NO_SUCH_ENTRY:
        mtc0    t0, CP0_ENTRYHI		#将t0寄存器中的值存入EntryHi寄存器(恢复到调用该函数之前的状态)
        j       ra					#函数返回
	nop
END(tlb_out)

Thinking 2.6

question

任选下述二者之一回答：

  • 简单了解并叙述 X86 体系结构中的内存管理机制，比较 X86 和 MIPS 在内存管理上的区别。

  • 简单了解并叙述 RISC-V 中的内存管理机制，比较 RISC-V 与 MIPS 在内存管理上的区别。

answer

X86 和 MIPS 在内存管理上的区别有以下三点主要区别——

  • 首先是内存管理机制上，MIPS主要采用的是页式管理系统，X86主要采用的是段页式

  • 其次，在对 TLB 不命中时的处理上，MIPS 会触发TLB Refill 异常，内核的 tlb_refill_handler 会以 pgd_current 为当前进程的 PGD 基址，索引获得转换失败的虚址对应的 PTE，并将其填入TLB，然后CPU再用刚刚转换失败的虚拟地址重新访问以下TLB。

    而X86在TLB不命中时，是由硬件MMU以CR3为当前进程的PGD基址，索引获得PFN后，直接输出PA。同时MMU会填充TLB以加快下次转换的速度。

  • 另外转换失败的虚址，MIPS使用BadVAddr寄存器存放，X86使用CR2存放

lab_difficulties

image-20230421220223399

内核程序启动

在lab2中内核启动部分总共需要做以下三件事，主要难点在于page_init()部分。

函数 功能
mips_detect_memory() 探测硬件可用内存，并对一些和内存管理相关的变量进行初始化。
mips_vm_init() 为内存管理机制作准备，建立一些用于管理的数据结构。
page_init() 实现位于 kern/pmap.c 中，作用是初始化 Pages 结构体以及空闲链表。

值得一提的是，内核启动阶段还没有建立内存管理机制，所以实际上是通过 kseg0 段地址直接操作物理内存的，虽然实验一直在操作如0x80xxxxxx 的虚拟地址，由于 kseg0 段的性质，操作系统可以通过这一段地址来直接操作物理内存，从而逐步建立内存管理机制。

物理内存管理

页式内存管理

MOS 中的内存管理使用页式内存管理，采用链表法管理空闲物理页框,MOS 中维护了 npage 个页控制块，也就是 Page 结构体。npage 个 Page 和 npage 个物理页面一一顺序对应，具体来说，npage 个 Page的起始地址为 pages，则 pages[i] 对应从 0 开始计数的第 i 个物理页面。两者的转换可以使用 page2pa 和 pa2page 这两个函数。

这里简单解说一下page2pa函数，具体实现如下：

1
2
3
4
5
6
static inline u_long page2ppn(struct Page *pp) {
	return pp - pages;
}
static inline u_long page2pa(struct Page *pp) {
	return page2ppn(pp) << PGSHIFT;
}

首先我们需要熟悉一下指针运算的效果，这里传入的参数*pp可以等价理解为page[i]，所以pp-pages类似于a[i]-a得到的是数组的下标i，之后<<PGSHIFT部分是将得到的页号i和每一页的page大小相乘从而得到了对应的物理页面。

Page存储结构

之后就是一个很重要也是难点的部分——Page存储结构。Page是我们用于管理物理内存块的结构体，该结构体包含两部分——一个是"数据域"（pp_ref）,另一个是"指针域"（pp_link）。通过上面的思考题我们知道最终page结构可以简化到以下这种形式

1
2
3
4
5
6
7
struct Page{
	struct {
		struct Page *le_next;
		struct Page **le_prev;
	} pp_link;
    u_short pp_ref;
};

其中，pp_ref代表着该物理内存块被引用的次数，即有多少个虚拟地址映射到该物理内存块。pp_link中包含两个指针变量——le_next和le_prev，前者是指向后一个Page结构体的指针，后者是指向前一个Page的le_next的指针。

为了便于对空闲物理内存块的管理，我们将所有空闲物理内存块对应的Page结构体用一个链表链接了起来，为了便于链表的增删改查，我们就需要上述le_next和le_prev发挥作用了。链表示意图如下所示

image-20230314090217222

用结构体表示就是这样一个结构：

1
2
3
4
5
6
7
8
9
struct Page_list{
	struct {
		struct {
			struct Page *le_next;
			struct Page **le_prev;
		} pp_link;
		u_short pp_ref;
	}* lh_first;
}

这里在实际操作时对你的指针能力是一个极大的挑战，需要我们对链表的增删改查十分熟悉，值得一提的是该链表实际上是一个双向链表，但和我们常见的双向链表又有区别。该双向链表可以直接通过le_next来访问下一个链表项，但却无法直接访问上一个链表项。因为le_prev仅仅是指向了前一个Page的le_next，换句话说，就是一个指向了"指向自己的指针"的指针。虽然le_prev无法帮助我们直接访问上一个链表项，但是，它却可以帮助我们以O(1)的开销实现链表的增删操作。在此奉上一文gg亲手画的链表前插入的解析图，供大家理解一下与正常链表插入的差异。

将空闲物理页对应的 Page 结构体全部插入一个链表中，该链表被称为空闲链表，就是page_free_list,用于存储指向链表首项的指针。

1
2
3
struct Page_list {
	struct Page *lh_first;
} page_free_list;

至此Page存储结构介绍完毕。

相关函数
函数 作用
page_init() 物理页面管理
初始化空闲页面链表，用于存储“没有被使用”的页控制块,并完成页对齐。
page_alloc(struct Page **pp) 分配物理页面
将 page_free_list 空闲链表头部页控制块对应的物理页面分配出去，将其从空闲链表中移除，并清空对应的物理页面，最后将 pp指向的空间赋值为这个页控制块的地址。
page_decref(struct Page *pp) 减少物理页面引用
令 pp 对应页控制块的引用次数减少 1，如果引用次数为 0 则会调用下面的 page_free 函数将对应物理页面重新设置为空闲页面。
page_free(struct Page *pp) 回收物理页面到空闲页面链表
是判断 pp 指向页控制块对应的物理页面引用次数是否为 0，若为 0 则该物理页面为空闲页面，将其对应的页控制块重新插入到 page_free_list

当一个进程需要分配内存时，将空闲链表头部的页控制块对应的那一页物理内存分配出去，同时将该页控制块从空闲链表的头部删去。当一页物理内存被使用完毕 (准确来说，引用次数为 0 时)，将其对应的页控制块重新插入到空闲链表的头部。

虚拟内存管理

MOS 中采用 PADDR 与KADDR 这两个宏就可以对位于 kseg0 的虚拟地址和对应的物理地址进行转换。但是，对于位于 kuseg 的虚拟地址，MOS 中采用两级页表结构对其进行地址转换。

二级页表查询机制

两级页表机制相比单级页表机制，将虚拟页号进一步分为了两部分。具体来说，对于一个 32 位的虚存地址，从低到高从 0 开始编号，其 31-22 位表示的是一级页表项的偏移量，21-12 位表示的是二级页表项的偏移量，11-0 位表示的是页内偏移量。具体可以通过PDX和PTX两个宏快速获得相关量。

访问虚拟地址时，先通过一级页表基地址和一级页表项的偏移量，找到对应的一级页表项，得到对应的二级页表的物理页号，再根据二级页表项的偏移量找到所需的二级页表项，进而得到该虚拟地址对应的物理页号。具体情况如图所示——

image-20230314095743231

MIPS R3000发出的地址均为虚拟地址，因此如果程序想访问某个物理地址，需要通过映射到该物理地址的虚拟地址来访问。在 MOS中，无论是一级页表还是二级页表，它们的结构都一样，只不过每个页表项记录的物理页号含义有所不同。

与页表相关的函数
函数 作用
pgdir_walk(Pde *pgdir, u_long va, int create, Pte **ppte) 二级页表检索函数
该函数将一级页表基地址 pgdir 对应的两级页表结构中 va 虚拟地址所在的二级页表项的指针存储在 ppte 指向的空间上。如果 create 不为 0 且对应的二级页表不存在，则会使用 page_alloc 函数分配一页物理内存用于存放二级页表，如果分配失败则返回错误码。
int page_insert(Pde *pgdir, u_int asid, struct Page *pp, u_long va, u_int perm) 增加地址映射函数
将一级页表基地址 pgdir 对应的两级页表结构中虚拟地址 va 映射到页控制块 pp 对应的物理页面，并将页表项权限为设置为 perm。
page_lookup(Pde *pgdir, u_long va, Pte **ppte) 寻找映射的物理地址函数
作用是返回一级页表基地址 pgdir对应的两级页表结构中虚拟地址 va 映射的物理页面的页控制块，同时将ppte 指向的空间设为对应的二级页表项地址。
page_remove(Pde *pgdir, u_int asid, u_long va) 取消地址映射函数
作用是删除一级页表基地址pgdir 对应的两级页表结构中虚拟地址 va 对物理地址的映射。如果存在这样的映射，那么对应物理页面的引用次数会减少一次。

可以辅助这张图加强理解——

image-20230314100557280

页表项常见权限位
1
2
3
4
5
#define PTE_V 0x0200
#define PTE_D 0x0400
#define PTE_G 0x0100
#define PTE_COW 0x0001
#define PTE_LIBRARY 0x0004
权限位 功能
PTE_V 有效位，若某页表项的有效位为 1，则该页表项中高 20 位就是对应的物理页号。
PTE_D 可写位，若某页表项的可写位为 1，则可经由该页表项对物理页进行写操作。
PTE_G 全局位，若某页表项的全局位为 1，则 TLB 仅通过虚页号匹配表项，而不匹配ASID，将在 Lab3 中用于映射 pages 和 envs 到用户空间。本 Lab 中可以忽略。
PTE_COW 写时复制位，将在 Lab4 中用到，通过该权限位实现了 fork 的写时复制机制。本 Lab 中可以忽略。
PTE_LIBRARY 共享页面位，将在 Lab6 中用到，用于实现管道机制，本 Lab 中可以忽略。

TLB 重填

TLB 组成

每一个 TLB 表项都有 64 位，其中高 32 位是 Key，低 32 位是 Data。EntryHi、EntryLo 都是 CP0 中的寄存器，他们只是分别对应到 TLB 的 Key 与 Data，并不是 TLB 本身。

image-20230314102146758

TLB相关指令
指令 作用
tlbr 以 Index 寄存器中的值为索引，读出 TLB 中对应的表项到 EntryHi 与 EntryLo
tlbwi 以 Index 寄存器中的值为索引，将此时 EntryHi 与 EntryLo 的值写到索引指定的 TLB 表项中。
tlbwr 将 EntryHi 与 EntryLo 的数据随机写到一个 TLB 表项中（此处使用 Random 寄存器来“随机”指定表项，Random 寄存器本质上是一个不停运行的循环计数器）
tlbp 根据 EntryHi 中的 Key（包含 VPN 与 ASID），查找 TLB 中与之对应的表项，并将表项的索引存入 Index 寄存器（若未找到匹配项，则 Index 最高位被置 1）
TLB相关函数
函数 作用
tlb_invalidate(u_int asid, u_long va) 实现删除特定虚拟地址的映射，每当页表被修改，就需要调
_do_tlb_refill(u_long va, u_int asid) TLB 重填

lab_summary

整体回顾

image-20230403174759500

一个小知识点

在这部分先插入一个我对于c语言的新发现，就是lab2中PADDR宏是这样实现的

1
2
3
4
5
6
7
#define PADDR(kva)                                                                                 \
	({                                                                                         \
		u_long a = (u_long)(kva);                                                          \
		if (a < ULIM)                                                                      \
			panic("PADDR called with invalid kva %08lx", a);                           \
		a - ULIM;                                                                          \
	})

而我对其中的a-ULIM这个非赋值语句产生了好奇，于是通过查资料、问助教发现了这样一种神奇的用法，在此记录一下。

image-20230314110630659

Lab2中地址相关的常量宏

宏 作用
PDX(va) 页目录偏移量（查找遍历页表时常用）
PTX(va) 页表偏移量（查找遍历页表时常用）
PTE_ADDR(pte) 获取页表项中的物理地址（读取 pte 时常用）
PADDR(kva) kseg0 处虚地址 → 物理地址
KADDR(pa) 物理地址 → kseg0 处虚地址（读取 pte 后可进行转换）
va2pa(Pde *pgdir, u_long va) 查页表，虚地址 → 物理地址（测试时常用）
pa2page(u_long pa) 物理地址 → 页控制块（读取 pte 后可进行转换）
page2pa(struct Page *pp) 页控制块 → 物理地址（填充 pte 时常用）

总结

Lab2主要是实现MOS中的内存管理机制，包括物理内存管理、虚拟内存管理和TLB重填机制。和Lab1相比，本次Lab代码量剧增，而且链表操作部分使用了指向指针的指针，对代码的理解和补全也造成一定困难（有的时候甚至怀疑自己是不是真的学会了指针）。虽然一路艰辛，但还是收获满满，希望继续加油！！！

  • Title: lab2_report
  • Author: Charles
  • Created at : 2023-03-13 13:00:22
  • Updated at : 2023-11-05 21:36:18
  • Link: https://charles2530.github.io/2023/03/13/lab2-report/
  • License: This work is licensed under CC BY-NC-SA 4.0.
recommend_articles
datastruct_6 datastruct_6 shortest-path-algorithm shortest-path-algorithm optimisation theory optimisation theory
recommend_articles
datastruct_6 datastruct_6 shortest-path-algorithm shortest-path-algorithm
Comments
On this page
lab2_report
  1. lab2_report
    1. advance
      1. 实现物理内存和虚拟内存的管理方式
    2. lab_thinkings
      1. Thinking 2.1
        1. question
        2. answer
      2. Thinking 2.2
        1. question
        2. answer
      3. Thinking 2.3
        1. question
        2. answer
      4. Thinking 2.4
        1. question
        2. answer
      5. Thinking 2.5
        1. question
        2. answer
      6. Thinking 2.6
        1. question
        2. answer
    3. lab_difficulties
      1. 内核程序启动
      2. 物理内存管理
        1. 页式内存管理
        2. Page存储结构
        3. 相关函数
      3. 虚拟内存管理
        1. 二级页表查询机制
        2. 与页表相关的函数
        3. 页表项常见权限位
      4. TLB 重填
        1. TLB 组成
        2. TLB相关指令
        3. TLB相关函数
    4. lab_summary
      1. 整体回顾
      2. 一个小知识点
      3. Lab2中地址相关的常量宏
      4. 总结