BUAA-OS

「BUAA OS Lab2」难点梳理与理解总结

Posted by saltyfishyjk on 2022-05-06
Words 3.6k and Reading Time 13 Minutes
Viewed Times

「BUAA OS Lab2」 难点梳理与理解总结

内存访问

内存访问的流程：

  1. TLB根据虚拟地址查找
  2. 若存在，在cache中查找；若不存在，按照页表查询，再查cache，更新TLB
  3. 若cache命中则完成，若未命中，进行页面替换

值得一提的是，这里有一个思考方式：我认为应当将虚拟地址如何划分和管理与如何进行物理内存管理这两件事分开考虑。也就是说，我们在虚拟空间中，按照我们的规则将不同的内容井井有条地摆放好，这是一项工作；在根据一个虚拟地址访问物理内存，得到正确的内容，这是另一项工作。如果我们可以保证将两件工作分开做好，那么我们也就将内存访问与管理做好了。

更进一步拓展，这是一种分而治之和面向约定的思想。尽管我们在实验中长久地和底层的、琐碎的细节（我有时候想称呼其为dirty details）打交道，但是尽可能在较为宏观的地方划一些线区分他们是一个不错的思维方式，这样避免了那你无限递归去考虑一个问题。举例而言，当你的操作系统获得一个虚拟地址的时候，你不应当考虑CPU如何计算这个虚拟地址；当你的CPU计算一个虚拟地址的时候，你不应当考虑寄存器的工作原理；当你观察一个logisim CPU的时候，你不应当考虑二极管或者更底层的内容。这样，可以尽可能保证你头脑的清晰。最后的时候，你应当得到的图景是各个部分都做好了他们的工作，并且接口约定一致、行为约定一致，而不应当在一个部分中考虑另一个部分如何实现。一句话概括，考虑你应该考虑的，对不是你职责内的事情放弃考虑。

内存布局与初始化

涉及的内存布局

  • kuseg：用户态可用地址，低 $ 2GB $ 空间，需要MMU进行地址转换
  • kseg0：内核地址，转换不需要MMU，只需要最高位清 $ 0 $

64MB的物理内存的16进制为 $ 0x400,0000 $

初始化内存管理相关变量

mips_detect_memory

1
2
3
4
5
6
7
8
9
10
11
12
13
void mips_detect_memory()
{
	/* Step 1: Initialize basemem.
	 * (When use real computer, CMOS tells us how many kilobytes there are). */
	maxpa = 0x4000000;
	basemem = 0x4000000;
	extmem = 0x0;
	// Step 2: Calculate corresponding npage value.
	npage = basemem >> PGSHIFT;
	printf("Physical memory: %dK available, ", (int)(maxpa / 1024));
	printf("base = %dK, extended = %dK\n", (int)(basemem / 1024),
			(int)(extmem / 1024));
}

初始化一些相关变量，具体的变量含义等可以查询文章Lab 2 名词解释

初始化mips虚拟空间

mips_vm_init

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
void mips_vm_init()
{
	extern char end[];
	extern int mCONTEXT;
	extern struct Env *envs;

	Pde *pgdir;
	u_int n;

	/* Step 1: Allocate a page for page directory(first level page table). */
	pgdir = alloc(BY2PG, BY2PG, 1);
	printf("to memory %x for struct page directory.\n", freemem);
	mCONTEXT = (int)pgdir;

	boot_pgdir = pgdir;

	/* Step 2: Allocate proper size of physical memory for global array `pages`,
	 * for physical memory management. Then, map virtual address `UPAGES` to
	 * physical address `pages` allocated before. In consideration of alignment,
	 * you should round up the memory size before map. */
	pages = (struct Page *)alloc(npage * sizeof(struct Page), BY2PG, 1);
	printf("to memory %x for struct Pages.\n", freemem);
	n = ROUND(npage * sizeof(struct Page), BY2PG);
	boot_map_segment(pgdir, UPAGES, n, PADDR(pages), PTE_R);

	/* Step 3, Allocate proper size of physical memory for global array `envs`,
	 * for process management. Then map the physical address to `UENVS`. */
	envs = (struct Env *)alloc(NENV * sizeof(struct Env), BY2PG, 1);
	n = ROUND(NENV * sizeof(struct Env), BY2PG);
	boot_map_segment(pgdir, UENVS, n, PADDR(envs), PTE_R);

	printf("pmap.c:\t mips vm init success\n");
}

这个函数进行了初始化工作，它调用了一些其他函数，我们在下面逐一讲解：

alloc

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
static void *alloc(u_int n, u_int align, int clear)
{
	extern char end[];
	u_long alloced_mem;

	/* Initialize `freemem` if this is the first time. The first virtual address that the
	 * linker did *not* assign to any kernel code or global variables. */
	if (freemem == 0) {
		freemem = (u_long)end;
	}

	/* Step 1: Round up `freemem` up to be aligned properly */
	freemem = ROUND(freemem, align);

	/* Step 2: Save current value of `freemem` as allocated chunk. */
	alloced_mem = freemem;

	/* Step 3: Increase `freemem` to record allocation. */
	freemem = freemem + n;

	/* Check if we're out of memory. If we are, PANIC !! */
	if (PADDR(freemem) >= maxpa) {
		panic("out of memory\n");
		return (void *)-E_NO_MEM;
	}

	/* Step 4: Clear allocated chunk if parameter `clear` is set. */
	if (clear) {
		bzero((void *)alloced_mem, n);
	}

	/* Step 5: return allocated chunk. */
	return (void *)alloced_mem;
}

值得注意的是，我们的maxpa是 $ 0x400,0000 $ ， 查阅mmu.h可以知道 $ 0x8400,0000 $ 直接对应maxpa，这也就是图中的Physical Memory Max(PMM)。

alloc函数中我们可以看到，其本质上维护freemem，而 $ [PADDR(freemem), maxpa - 1] $​是我们还可以接着分配的物理内存。但是由于我们统一使用虚拟地址，因此，freemem仍然是虚拟地址。由于这种一一映射的关系，将物理内存 $ [0x400000 , 0x4000000] $ 表述为

$ [0x80400000,0x84000000] $ 也是可以理解的。

在alloc维护freemem的时候，其具体操作为上移freemem，以代表剩余可分配空间的底线。

初始化Pages结构体和空闲链表

page_init

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
void page_init(void)
{
    /* Step 1: Initialize page_free_list. */
    /* Hint: Use macro `LIST_INIT` defined in include/queue.h. */
    LIST_INIT(&page_free_list);

    /* Step 2: Align `freemem` up to multiple of BY2PG. */
    freemem = ROUND(freemem, BY2PG);

    /* Step 3: Mark all memory blow `freemem` as used(set `pp_ref`
     * filed to 1) */
    int size = PADDR(freemem) / BY2PG;
    int i;
    for (i = 0; i < size; ++i)
    {
        pages[i].pp_ref = 1;
    }
    /* Step 4: Mark the other memory as free. */
    for (i = size; i < npage; ++i)
    {
        pages[i].pp_ref = 0;
        LIST_INSERT_HEAD(&page_free_list, pages + i, pp_link);
    }
    LIST_REMOVE(pa2page(PADDR(TIMESTACK - BY2PG)), pp_link);
}
  • 初始化头结点page_free_list
  • 圆整freemem使其对齐
  • 将freemem下面的空间标记为用过，上面的空间标记为没用过并插入空闲链表
  • 将TIMESTACK对应的页从空闲链表中移出

关于链表宏的具体写法，可以查看源码，这里记录一下直观感受：

链表可以是一个抽象的概念，本实验中使用的双向链表不依赖链表结点的具体内容和结构，更进一步说，只要链表结点都拥有双向指针（链表项LIST_ENTRY(type)），就应当可以根据链表项完成增删改查的功能。

因此，根据上述分析，只要设计好了field链表项（其实为一个结构体，通过LIST_ENTRY(type)类工厂模式构造）

在页表管理这个例子中，通过LIST_ENTRY工厂，传入参数Page构造了类型Page_LIST_entry_t，并将其置入Page结构体中，这样我们就可以得到了链表结点Page，因此也就可以依靠其构造链表了。

虚拟内存管理

在MOS中，对于kseg0的虚拟地址及其对应的物理地址的转换，我们通过PADDR和KADDR进行转换。对于kuseg的虚拟地址，我们采用两级页表结构管理。

虚拟地址和物理地址

在这个部分，我遇到了巨大的理解层面的挑战。

在理论课程和理论题目中，我们对于给定一个虚拟地址及其结构，给定页表项结构，给定一些特定的物理页及其内容后按需访存是比较熟悉的，但这和实验是脱钩的，或者也可以反过来说，实验和理论访存流程是脱钩的。以下举例说明。

这是一个比较典型的二级页表类题目。我们知道，给定一个虚拟地址，我们按照格式划分得到页目录号，二级页表号和页内偏移量，这在我们的实验中有PDE(va)和PTE(va)两个宏函数分别对应获得前两者。然后，我们根据页目录号左移4位，加上我们的页目录物理基地址，得到了页目录项的物理地址，这时候，由于题图中有物理页及其内容，我们很自然地得到了页目录项内容。但是在实验中，问题来了，你凭什么根据物理地址访问物理内存？更进一步说，当我们的规则统一设定为给定虚拟地址后按照虚拟地址所属的节（比如kseg0,kseg1,kseg2,kuseg等）来获取物理地址，即使是像kseg0的地址只需要抹掉最高位就可以得到物理地址，也不影响你必须提供一个虚拟地址供我们转换，这是一个统一的、完善的流程。因此，即便我们在这里获得了物理地址，我们事实上也将在这个物理地址访存，但是我们仍需要将其通过宏函数KADDR转换为（kseg0中的）虚拟地址来提供给CPU。因此，我们拼上了理论到实验的最后一块积木：得到物理地址后如何访问。

boot_map_segment

当我们在前面的初始化过程中分别为boot_pgdir申请了空间，为pages和envs申请了空间（虚拟地址）之后，我们还需要将其虚拟地址与物理地址建立关系，这便是boot_map_segment的功能。

在boot_map_segment中，通过函数boot_pgdir_walk找到一个二级页表项地址pgtable_entry，然后将其中内容储存为物理地址和权限位的结合。值得注意的是，PTE的结构事实上是高20位为页框号，低12位为权限控制。但是得益于一页大小正好是4KB即12位，我们可以直接将物理地址和权限位或在一起即可。

boot_pgdir_walk

找到二级页表项地址。

在这个函数中，采用了二级页表寻址，我们在上面的OS理论题的例子中已经阐述过物理地址和虚拟地址在实验中的区别和关系，相信读者以及该完全理解了这一点，因此不再赘述。

值得一提的是，该函数不仅进行寻址，还在没有找到且create满足时申请新的页面，这里采用了alloc函数。

物理内存内容

经过上述初始化过程，我们现在忽略掉实现细节，站在更高的抽象角度观察和考虑我们都在物理内存中存放了什么。

从低地址向高地址，我们依次存放了pgdir，pages，envs以及后续alloc的页。

操作进程页表

上述介绍中，我们在系统启动初期进行了虚拟内存管理的初始化，接下来我们介绍操作进程的页表。一个显著的区分是，初始化过程中使用的函数带有boot前缀，在进程生命周期中使用的函数不带有boot前缀。

在在这个阶段，我们已经建立好了内存管理机制，因此可以放心使用page_alloc函数。

运行时二级页表检索

pgdir_walk实现该功能，并且其支持申请失败，会返回一个错误码。

pgdir_walk能够获取va对应的二级页表项，其实这里就对应我们在理论作业中，根据pgdir和PDX得到二级页表项的物理地址然后到页框中寻找对应的物理内存的内容的步骤一样。值得注意的是，我们在理论中可以直接根据物理地址看到具体的页框，而我们的实验中则还需要转为虚拟地址；另外，我们的理论题目在页目录项无效（权限为不满足）时就结束了，但在我们的实验中还支持为这个页目录项申请一个物理页作为其映射的二级页表。

如果这个函数正常结束，就能赋给其相应参数指向二级页表项的指针（pgtable + PTX(va)）。

页面插入、删除与置换

在这里我们重申访存过程：一次合法的访存，对给定的va，根据PDX和pgdir访问页目录项，得到二级页表项的指针（当pgdir_walk运行结束的时候正好完成这一步）；得到二级页表项的指针，读取得到va对应的物理页框号；将物理页框号加上va的offset得到具体的存储单元，读取即可。

page_insert

增加地址映射，将va这一虚拟地址映射到内存控制块pp对应的物理页面。

首先使用pgdir_walk获得二级页表项。值得注意的是，此时我们不应当再去考虑pgdir_walk的实现细节，我们只需要可以通过其获得二级页表基地址即可，应当时刻注意抽象、封装和接口。

然后分情况讨论：

  • 当该二级页表项有效时
    • 若当前映射的物理页面不是我们需要其映射的pp，则执行page_remove取消地址映射。
    • 否则，更新权限位，并调用tlb_invalidate以使得下一次访问该va时会触发缺页异常并直接返回。
  • 当二级页表项无效或进行了page_remove，调用tlb_invalidate使得下一次访问该va时触发缺页异常。调用pgdir_walk得到二级页表项，将其内容设置为pp对应的物理地址并或上权限位。还需要注意要使pp->pp_ref++

page_lookup

根据给定的va和对应的pgdir寻找映射的物理地址函数。

首先调用pgdir_walk获得pte，分情况讨论（值得注意的是，调用pgdir_walk的时候create置为0，即，如果页目录项非法，不新生成有效的二级页目录项）：

  • pte为0（无效）或pte判断PTE_V无效，直接返回0表示没找到
  • pte有效，根据pte得到物理页框的指针作为返回值，同时将参数Pte **ppte赋值使得ppte指向的pte的值更新为本函数中调用pgdir_walk得到的页目录项指针，一个小细节是要判断ppte!=0即ppte不是空指针

page_remove

取消地址映射函数，删除pgdir对应的两级页表结构中va这一虚拟地址对物理地址的映射，如果存在这样的映射，相应的物理页面引用次数会减少。

利用上面的page_lookup函数找到va再pgdir下对应的物理页面，如果不为0（说明确实va映射到了物理地址）则使其pp_ref减1，如果减完之后为0，则说明不再有va映射到该物理页面，调用page_free将其插回page_free_list。将二级页表项内容设置为0，并调用tlb_invalidate使得再次访问该va时会引发缺页异常。

page_decref

减小物理页框的引用次数1次。

This is copyright.

FEATURED TAGS
BUAA-OS
FRIENDS