MIT6.828操作系统实验二之内存管理

主要学习内核各种地址的管理，以及二级页表的各种操作

前言

花了两个晚上终于完成了实验二，相比于实验一花的时间要少(可能还是敲代码比较适合我)。

实验二主要完成操作系统的内存管理代码，分为两部分，物理内存分配器和虚拟内存。

物理内存分配器主要是在页面级别的操作，而虚拟内存就是二级页表的管理。

下面是实验二的报告。

实验准备

按照指导更新了lab2的代码后，多了这几个文件：

inc/memlayout.h
kern/pmap.c
kern/pmap.h
kern/kclock.h
kern/kclock.c

memlayout.h描述了必须通过修改pmap.c来实现的虚拟地址空间的布局。
memlayout.h和pmap.h定义了PageInfo用于跟踪哪些物理内存页面是空闲的结构。
kclock.c和kclock.h操纵PC的电池供电时钟和CMOS RAM硬件，其中BIOS记录PC包含的物理内存量等。
pmap.c中的代码需要读取此设备硬件以确定有多少物理内存，但代码的这一部分是需要完成的，但不需要知道CMOS硬件如何工作的细节。特别注意memlayout.h和pmap.h，因为本实验要求使用并理解它们包含的许多定义。inc/mmu.h也有用。

第一部分：物理页面管理

操作系统必须跟踪物理RAM的哪些部分是空闲的以及哪些是当前正在使用的。

JOS以页面粒度管理PC的物理内存，以便它可以使用MMU映射和保护每个分配的内存。

需要编写物理页面分配器。它通过链接的struct PageInfo对象列表跟踪哪些页面是空闲的（与xv6不同，它们不嵌入在空闲页面中），每个对应于一个物理页面。

在编写剩余的虚拟内存实现之前，需要编写物理页面分配器，因为页表管理代码需要分配用于存储页表的物理内存。

练习1. 在文件`kern/pmap.c`中，必须为以下函数实现代码（可能按给定的顺序）。

boot_alloc()
mem_init()
page_init()
page_alloc()
page_free()

check_page_free_list()和check_page_alloc()是用于测试的物理页面分配器。

启动JOS并查看check_page_alloc()报告是否成功。修复代码，使其通过。添加自己的assert()有助于验证假设是否正确。

Part1：理解一些宏函数

typeof是GNU C标准中的一个扩展特性，类似于C++11中的decltype，就是自动推导表达式的数据类型

ROUNDUP的作用就是计算传进来的字节数所需要的页面数

// Rounding operations (efficient when n is a power of 2)
// Round down to the nearest multiple of n
#define ROUNDDOWN(a, n)						\
({								\
	uint32_t __a = (uint32_t) (a);				\
	(typeof(a)) (__a - __a % (n));				\
})
// Round up to the nearest multiple of n
#define ROUNDUP(a, n)						\
({								\
	uint32_t __n = (uint32_t) (n);				\
	(typeof(a)) (ROUNDDOWN((uint32_t) (a) + __n - 1, __n));	\
})

PADDR作用是将内核虚拟地址转化为物理地址，实际就是减了一个 F0000000

/* This macro takes a kernel virtual address -- an address that points above
 * KERNBASE, where the machine's maximum 256MB of physical memory is mapped --
 * and returns the corresponding physical address.  It panics if you pass it a
 * non-kernel virtual address.
 */
#define PADDR(kva) _paddr(__FILE__, __LINE__, kva)

static inline physaddr_t
_paddr(const char *file, int line, void *kva)
{
	if ((uint32_t)kva < KERNBASE)
		_panic(file, line, "PADDR called with invalid kva %08lx", kva);
	return (physaddr_t)kva - KERNBASE;
}

Part2：理解函数的作用，并补充完整

static void *boot_alloc(uint32_t n)
- 这个简单的物理内存分配器只有在JOS在设置它的虚拟内存系统时才被调用，即只会在初始化时、在page_free_list被设置前调用
- page_alloc()才是真正的分配函数 ```c static void * boot_alloc(uint32_t n) { static char *nextfree; // virtual address of next byte of free memory char *result;

// Initialize nextfree if this is the first time. // ‘end’ is a magic symbol automatically generated by the linker, // which points to the end of the kernel’s bss segment: // the first virtual address that the linker did not assign // to any kernel code or global variables. if (!nextfree) { extern char end[]; nextfree = ROUNDUP((char *) end, PGSIZE); }

// Allocate a chunk large enough to hold ‘n’ bytes, then update // nextfree. Make sure nextfree is kept aligned // to a multiple of PGSIZE. // // LAB 2: Your code here. // result = KADDR(PADDR(nextfree)); if(n == 0) { return nextfree; } result = nextfree; nextfree += ROUNDUP(n, PGSIZE); return result; }

+ `void mem_init(void)`
    + 设置两层页表，这个函数只设置内核部分的地址空间(>= UTOP)，用户部分的地址空间将在之后设置
    + `UTOP`到`ULIM`：用户只能读不能写；`ULIM`之上用户不能读或写
这个初始化内存的函数只需要补充三行，之后是设置虚拟内存的事。
```c
//////////////////////////////////////////////////////////////////////
// Allocate an array of npages 'struct PageInfo's and store it in 'pages'.
// The kernel uses this array to keep track of physical pages: for
// each physical page, there is a corresponding struct PageInfo in this
// array.  'npages' is the number of physical pages in memory.  Use memset
// to initialize all fields of each struct PageInfo to 0.
// Your code goes here:
// 分配 npages 个 struct PageInfo 的页面到 pages
n = npages * sizeof(struct PageInfo);
pages = (struct PageInfo *)boot_alloc(n);
memset(pages, 0, n);

void page_init(void)
- 跟踪物理页面
- 初始化页面结构和内存空闲链表
- 这个函数完成后，boot_alloc不能再被调用跟着注释就能很好的完成了。 c void page_init(void) { // Change the code to reflect this. // NB: DO NOT actually touch the physical memory corresponding to // free pages! // The example code here marks all physical pages as free. // However this is not truly the case. What memory is free? // 1) Mark physical page 0 as in use. // This way we preserve the real-mode IDT and BIOS structures // in case we ever need them. (Currently we don't, but...) pages[0].pp_ref = 1; // 2) The rest of base memory, [PGSIZE, npages_basemem * PGSIZE) // is free. size_t i; for (i = 1; i < npages_basemem; i++) { // 把页面设为空闲，并插入链表头 pages[i].pp_ref = 0; pages[i].pp_link = page_free_list; page_free_list = &pages[i]; } // 3) Then comes the IO hole [IOPHYSMEM, EXTPHYSMEM), which must // never be allocated. for(i = IOPHYSMEM/PGSIZE; i < EXTPHYSMEM/PGSIZE; i++) pages[i].pp_ref = 1; // 4) Then extended memory [EXTPHYSMEM, ...). // Some of it is in use, some is free. Where is the kernel // in physical memory? Which pages are already in use for // page tables and other data structures? // 找到第一个能分配到的页面地址，尤其需要注意的是， // 由于 boot_alloc 返回的是内核虚拟地址 (kernel virtual address)， // 一定要利用 PADDR 转为物理地址。 size_t first_free_address = PADDR(boot_alloc(0)); for(i = EXTPHYSMEM/PGSIZE; i < first_free_address/PGSIZE; i++) pages[i].pp_ref = 1; for(i = first_free_address/PGSIZE; i < npages; i++) { // 把页面设为空闲，并插入链表头 pages[i].pp_ref = 0; pages[i].pp_link = page_free_list; page_free_list = &pages[i]; } }
struct PageInfo *page_alloc(int alloc_flags)
- 分配一个物理页面 c struct PageInfo * page_alloc(int alloc_flags) { // Fill this function in struct PageInfo *page = NULL; if (page_free_list != NULL) { // 从空闲页面链表取走一页 page = page_free_list; page_free_list = page_free_list->pp_link; page->pp_link = NULL; if (alloc_flags & ALLOC_ZERO) { // page2kva的作用是通过物理页面获取其内核虚拟地址 memset(page2kva(page), '\0', PGSIZE); } } return page; }
void page_free(struct PageInfo *pp)
- 释放一个页面到空闲链表 ```c void page_free(struct PageInfo *pp) { // Fill this function in // Hint: You may want to panic if pp->pp_ref is nonzero or // pp->pp_link is not NULL. if(pp == NULL || pp->pp_ref != 0 || pp->pp_link != NULL) { panic(“wrong pp\n”); return; } // 释放后要加入空闲页链表中 pp->pp_link = page_free_list; page_free_list = pp; }


#### Part3：测试
测试前要删除或注释掉`mem_init`函数中的一行。
```c
// Remove this line when you're ready to test this function.
// panic("mem_init: This function is not finished\n");

现在能通过第一测试了。

$ ./grade-lab2
running JOS: (0.4s)
  Physical page allocator: OK

第二部分：虚拟内存

练习4. 在文件kern / pmap.c中，您必须实现以下函数的代码。

pgdir_walk（）
boot_map_region（）
page_lookup（）
page_remove（）
page_insert（）

check_page()，来自mem_init()是测试页表管理的例程。

Part1：理解什么是两级页表

内存分页管理的基本原理是将整个主内存区域划分成4096字节为一页的内存页面。
程序申请使用内存时，就以内存页为单位进行分配。上面提到了线性地址经过分页机制的转换变成物理地址，但是没有提到如何转换。
其实是通过两个表，一个是页目录表PDE，也叫一级目录，另一个是二级页表PTE。进程的虚拟地址需要首先通过其局部段描述符变换为CPU整个线性地址空间中的地址，然后再使用页目录表PDE（一级页表）和页表PTE（二级页表）映射到实际物理地址页上。
页表中，每项的大小是32b，其中20b用来存放页面的物理地址，12b用于存放属性信息。页表含有1M个表项，每项4B。第一级表是页目录，存放在1页4k页面中，含有1K个表项。第二级是页表，也是1K个表项。如下图所示：

![]()

Part2：理解函数的作用，并补充完整

void page_decref(struct PageInfo* pp)
- 减少对页面的引用，如果没有别的引用则释放页面
pte_t *pgdir_walk(pde_t *pgdir, const void *va, int create)
- 返回页表项地址 ```c pte_t * pgdir_walk(pde_t *pgdir, const void *va, int create) { // Fill this function in size_t pdx = PDX(va); size_t ptx = PTX(va);

// 如果对应的页面不存在 if(!pgdir[pdx]) { if(create == false) return NULL;

struct PageInfo *page = page_alloc(ALLOC_ZERO); if(page == NULL) return NULL; page->pp_ref++;

// 将页面的地址和属性信息存入页表 pgdir[pdx] = page2pa(page) | PTE_P | PTE_U | PTE_W; }

// 页目录表 pte_t *pgtbl = (pte_t *)KADDR(PTE_ADDR(pgdir[pdx])); // 返回页表项的地址 return &pgtbl[ptx]; }

+ `static void boot_map_region(pde_t *pgdir, uintptr_t va, size_t size, physaddr_t pa, int perm)`
    + 映射[va, va+size]的虚拟地址空间到物理地址空间[pa, pa+size]
```c
static void
boot_map_region(pde_t *pgdir, uintptr_t va, size_t size, physaddr_t pa, int perm)
{
	// Fill this function in
	size_t i = 0;
	for(; i < size; i += PGSIZE)
	{
		pte_t *pte = pgdir_walk(pgdir, (void *)(va + i), 1);
		*pte = (pa + i) | perm | PTE_P;
	}
}

int page_insert(pde_t *pgdir, struct PageInfo *pp, void *va, int perm)
- 映射物理页面pp到虚拟地址va ```c int page_insert(pde_t *pgdir, struct PageInfo *pp, void *va, int perm) { // Fill this function in pte_t *pte = pgdir_walk(pgdir, va, 1); if(pte == NULL) return -E_NO_MEM; // 空间不足

// 这里要提前增加引用计数，原因如下 // 如果该物理页ref = 1，经过page_remove后会被加入空闲页链表。 // 然而，在函数最后还需要增加其引用计数，导致page_free_list中出现了非空闲页。 pp->pp_ref++; if(*pte & PTE_P) page_remove(pgdir, va);

*pte = page2pa(pp) | perm | PTE_P;

return 0; }

+ `struct PageInfo *page_lookup(pde_t *pgdir, void *va, pte_t **pte_store)`
    + 作用是查找虚拟地址对应的物理页描述
    + 返回映射到虚拟内存`va`的页面
```c
struct PageInfo *
page_lookup(pde_t *pgdir, void *va, pte_t **pte_store)
{
	// Fill this function in
	pte_t *pte = pgdir_walk(pgdir, va, 1);

	if(pte == NULL)
		return NULL;

	if(pte_store)
		*pte_store = pte;  // 附加保存一个指向找到的页表的指针
	
	// PTE_ADDR这个宏的作用是将页表指针指向的内容转为物理地址
	return pa2page(PTE_ADDR(*pte));
}

void page_remove(pde_t *pgdir, void *va)
- 解除在虚拟地址va页面的映射 ```c void page_remove(pde_t *pgdir, void *va) { // Fill this function in pte_t *pte = NULL; struct PageInfo *page = page_lookup(pgdir, va, &pte); if(page == NULL) return;

*pte = (pte_t)0; tlb_invalidate(pgdir, va); page_decref(page); }


#### Part3：测试
现在能通过第二个测试`Page management`
```shell
$ ./grade-lab2
running JOS: (0.4s)
  Physical page allocator: OK
  Page management: OK

第三部分：内核地址空间

练习5.在mem_init()调用之后填写缺少的代码check_page()

该练习中主要映射了三段虚拟地址到物理页上。 1. UPAGES(0xef000000 ~ 0xef400000)最多4MB

n = ROUNDUP(n, PGSIZE);
boot_map_region(kern_pgdir, UPAGES, n, PADDR(pages), PTE_U | PTE_P);

内核栈(0xefff8000 ~ 0xf0000000)32kB

// bootstack表示的是栈地最低地址，由于栈向低地址生长，实际是栈顶
boot_map_region(kern_pgdir, KSTACKTOP - KSTKSIZE, KSTKSIZE, PADDR(bootstack), PTE_W | PTE_P);

内核 ( 0xf0000000 ~ 0xffffffff ) 256MB

n = (uint32_t)(-1) - KERNBASE + 1;
boot_map_region(kern_pgdir, KERNBASE, n, 0, PTE_W | PTE_P);

测试

$ ./grade-lab2
running JOS: (1.0s)
  Physical page allocator: OK
  Page management: OK
  Kernel page directory: OK
  Page management 2: OK
Score: 70/70

总结

完成第一个练习后有一个很无语的错误浪费了我很多时间，就是要注释的那行程序，导致我以为是我的程序有错误，一直在找bug。后来发现是由于没有注释那行程序，导致程序没有执行下去，也就不会成功，检查了许多遍才发现这个问题，看来我还是太菜了。

MIT6.828操作系统实验二之内存管理

前言

实验准备

第一部分：物理页面管理

练习1. 在文件kern/pmap.c中，必须为以下函数实现代码（可能按给定的顺序）。

Part1：理解一些宏函数

Part2：理解函数的作用，并补充完整

第二部分：虚拟内存

练习4. 在文件kern / pmap.c中，您必须实现以下函数的代码。

Part1：理解什么是两级页表

Part2：理解函数的作用，并补充完整

第三部分：内核地址空间

练习5.在mem_init()调用之后填写缺少的代码check_page()

测试

总结

liu jianhao

Raft详解

Linux内核网络源码解析3

Linux内核网络源码解析2——sk_buff操作

Paxos、Multi-Paxos详解

Linux内核网络源码解析1——sk_buff结构

LevelDB源码解析4——compaction

LevelDB源码解析3——get

LevelDB源码解析2——put

LevelDB源码解析1——open

LevelDB源码解析0.5——使用

练习1. 在文件`kern/pmap.c`中，必须为以下函数实现代码（可能按给定的顺序）。