lab 4：内存管理

Overview

在本实验中，我们将编写操作系统的内存管理代码。 内存管理有两个组成部分。

第一个部分是内核的物理内存分配器，以致于内核可以分配和释放内存。 分配器将以4096字节为操作单位，称为一个页面。 我们的任务是维护一个数据结构，去记录哪些物理页面是空闲的，哪些是已分配的，以及共享每个已分配页面的进程数。 我们还要编写例程来分配和释放内存页面。

内存管理的第二个组件是虚拟内存，它将内核和用户软件使用的虚拟地址映射到物理内存中的地址。 当指令使用内存时，x86硬件的内存管理单元（MMU）执行映射，查询一组页表。 我们根据任务提供的规范修改JOS以设置MMU的页面表。

Part Ⅰ：Physical Page Management

物理内存页管理

操作系统必须跟踪物理RAM（Random Access Memory,一般是主存）的哪些部分是空闲的，哪些部分正在使用，而这部分的实现是通过物理页面分配器来进行的，它通过struct PageInfo的链表来查询，每个PageInfo对应着一个物理内存页面

Exercise 1

boot_alloc()函数

该函数维护一个static的指针nextfree，初始值是end，end是定义在/kern/kernel.ld中定义的符号，位于bss段的末尾。也就是说从内核的末尾开始分配物理内存。需要添加如下代码

// 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 = nextfree;
	nextfree = ROUNDUP((char *)result + n, PGSIZE);
	cprintf("boot memory at %x, next memory allocate at %x\n",result, nextfree);
	return result;

之后来看mem_init()函数

mem_init()函数

1-1

可以看到是将boot_alloc()返回的result的值（当前的页）给了kern_pgdir，kern_pgdir保存的是内核页目录的物理地址

之后根据注释完成代码

// 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:
pages = (struct PageInfo *)boot_alloc(sizeof(struct PageInfo) * npages);
memset(pages, 0, sizeof(struct PageInfo) * npages);

这段代码分配足够的空间来保存pages数组，数组的每一项PageInfo对应一个物理页的信息

1-2

page_init()函数

这个函数的主要作用是初始化之前分配的pages数组，并且构建一个PageInfo链表，保存空闲的物理页，表头是全局变量page_free_list。

// 1）第一个物理页是IDT所在，需要标识为已用
// 2）[IOPHYSMEM, EXTPHYSMEM)称为IO hole的区域，需要标识为已用。
// 3）EXTPHYSMEM是内核加载的起始位置，终止位置可以由boot_alloc(0)给出（理由是boot_alloc()分配的内存是内核的最尾部），这块区域也要标识
size_t i;
size_t io_hole_start_page = (size_t)IOPHYSMEM / PGSIZE;
size_t kernel_end_page = PADDR(boot_alloc(0)) / PGSIZE;
for ( i = 0; i < npages; i++)
{
	if (i == 0)
	{
		pages[i].pp_ref = 1;
		pages[i].pp_link = NULL;
	}
	else if (i >= io_hole_start_page && i < kernel_end_page)
	{
		pages[i].pp_ref = 1;
		pages[i].pp_link = NULL;
	}
	else
	{
		pages[i].pp_ref = 0;
		pages[i].pp_link = page_free_list;
		page_free_list = &pages[i];
	}
	
}

page_alloc()函数

函数具体作用：

从page_free_list指向的链表中取出一个PageInfo结构，之后根据形参决定是否将对应的内存初始化为0

具体实现：

// Be sure to set the pp_link field of the allocated page to NULL so
// page_free can check for double-free bugs.
//
// Returns NULL if out of free memory.
//
// Hint: use page2kva and memset
struct PageInfo *
page_alloc(int alloc_flags)
{
	struct PageInfo *ret = page_free_list;
	if (ret = NULL)
	{
		cprintf("page_alloc:out of free memory now\n");
		return NULL;
	}
	page_free_list = ret->pp_link;
	ret->pp_link = NULL;
	if (alloc_flags && ALLOC_ZERO)
	{
		memset(page2kva(ret), 0, PGSIZE);
	}
	
	// Fill this function in
	return ret;
}

page_free()函数

这个函数就是将对应的物理页设置为空闲状态并且将对应的PageInfo连接到空闲链表中

//
// Return a page to the free list.
// (This function should only be called when pp->pp_ref reaches 0.)
//
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->pp_link != NULL && pp->pp_ref != 0)
	{
		panic("page_free:pp->pp_link is not NULL or pp->pp_ref is nonzero");
	}
	pp->pp_link = page_free_list;
	page_free_list = pp;
}

Exercise复盘

就是进行了对于内存物理页面的管理，将4096个字节分割成为一个页，然后通过数据结构PageInfo来进行管理，存储对应的数组，并且初始化一些和物理页面相关的操作，比如page_alloc和page_free，完成Part Ⅰ之后的内存情况如下

1-3

Part Ⅱ：Virtual Memory

Exercise 4

2-1

pagedir_walk()函数

这个函数是给定pdir参数，来指向一个页目录，返回指针指向虚拟地址va对应的页表条目

pte_t *
pgdir_walk(pde_t *pgdir, const void *va, int create)
{
	// Fill this function in
	pde_t *pde_ptr = pgdir + PDX(va);
	if (!(*pde_ptr && PTE_P))
	{
		if (create)
		{
			//分配一个页来作为页表
			struct PageInfo *pp = page_alloc(1);
			if (pp == NULL)
			{
				return NULL;
			}
			pp->pp_ref++;
			*pde_ptr = (page2pa(pp)) | PTE_P | PTE_U | PTE_W;
		}
		else
		{
			return NULL;
		}
		
	}
	
	return (pte_t *)KADDR(PTE_ADDR(*pde_ptr)) + PTX(va);;
}

boot_map_region()函数

该函数的作用是通过修改pgdir指向的树结构，将va，va+size对应的虚拟地址映射到pa，pa+size对应的物理地址空间

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 pgs = size / PGSIZE;
	if (size % PGSIZE != 0 )
	{
		pgs++;     //计算有多少页
	}
	for (int i = 0; i < pgs; i++)
	{
		pte_t *pte = pgdir_walk(pgdir, (void *)va, 1);
		if (pte == NULL)
		{
			panic("boot_map_region:out of physical memory");
		}
		*pte = pa | PTE_P | perm;
		pa = pa + PGSIZE;
		va = va + PGSIZE;
	}
	
}

page_lookup()函数

查找pgdir指向的树结构，返回va对应的PTE对应的物理地址对应的PageInfo结构

struct PageInfo *
page_lookup(pde_t *pgdir, void *va, pte_t **pte_store)
{
	// Fill this function in
	struct PageInfo *pp;
	pte_t *pte =  pgdir_walk(pgdir, va, 0);		
	if (pte == NULL) 
	{
		return NULL;
	}
	if (!(*pte) & PTE_P) 
	{
		return NULL;
	}
	physaddr_t pa = PTE_ADDR(*pte);		//va对应的物理
	pp = pa2page(pa);
	if (pte_store != NULL) 
	{
		*pte_store = pte;
	}
	return pp;
}

page_remove()函数

修改pgdir对用的树结构，解除映射关系

void
page_remove(pde_t *pgdir, void *va)
{
	// Fill this function in
	pte_t *pte_store;
	struct PageInfo *pp = page_lookup(pgdir, va, &pte_store); //获取va对应的PTE的地址以及pp结构
	if (pp == NULL) 
	{    //va可能还没有映射，什么都不用做
		return;
	}
	page_decref(pp);    //将pp->pp_ref减1，如果pp->pp_ref为0，需要释放该PageInfo结构（将其放入page_free_list链表中）
	*pte_store = 0;    //将PTE清空
	tlb_invalidate(pgdir, va); //失效化TLB缓存
}

page_insert()函数

修改pgdir对应的树结构，建立va与pp对应的内存物理页之间的链接

int
page_insert(pde_t *pgdir, struct PageInfo *pp, void *va, int perm)
{
	// Fill this function in
	// Fill this function in
	pte_t *pte = pgdir_walk(pgdir, va, 1);    //拿到va对应的PTE地址，如果va对应的页表还没有分配，则分配一个物理页作为页表
	if (pte == NULL) {
		return -E_NO_MEM;
	}
	pp->pp_ref++;	
	if ((*pte) & PTE_P) 
	{	//当前虚拟地址va已经被映射过，需要先释放
		page_remove(pgdir, va); 
	}
	physaddr_t pa = page2pa(pp); //将PageInfo结构转换为对应物理页的首地址
	*pte = pa | perm | PTE_P;    //修改PTE
	pgdir[PDX(va)] |= perm;
	
	return 0;
}

Exercise 4复盘

实现的是对于虚拟内存和物理页面之间的建立联系/树结构的过程，并且实现了一些相关操作

Part Ⅲ：kernel address space

Exercise 5

//////////////////////////////////////////////////////////////////////
// Map 'pages' read-only by the user at linear address UPAGES
// Permissions:
//    - the new image at UPAGES -- kernel R, user R
//      (ie. perm = PTE_U | PTE_P)
//    - pages itself -- kernel RW, user NONE
// Your code goes here:
//将虚拟地址的UPAGES映射到物理地址pags起始位置
boot_map_region(kern_pgdir, UPAGES, PTSIZE, PADDR(pages), PTE_U);
//////////////////////////////////////////////////////////////////////
// Use the physical memory that 'bootstack' refers to as the kernel
// stack.  The kernel stack grows down from virtual address KSTACKTOP.
// We consider the entire range from [KSTACKTOP-PTSIZE, KSTACKTOP)
// to be the kernel stack, but break this into two pieces:
//     * [KSTACKTOP-KSTKSIZE, KSTACKTOP) -- backed by physical memory
//     * [KSTACKTOP-PTSIZE, KSTACKTOP-KSTKSIZE) -- not backed; so if
//       the kernel overflows its stack, it will fault rather than
//       overwrite memory.  Known as a "guard page".
//     Permissions: kernel RW, user NONE
// Your code goes here:
boot_map_region(kern_pgdir, KSTACKTOP-KSTKSIZE, KSTKSIZE, PADDR(bootstack), PTE_W);
//////////////////////////////////////////////////////////////////////
// Map all of physical memory at KERNBASE.
// Ie.  the VA range [KERNBASE, 2^32) should map to
//      the PA range [0, 2^32 - KERNBASE)
// We might not have 2^32 - KERNBASE bytes of physical memory, but
// we just set up the mapping anyway.
// Permissions: kernel RW, user NONE
// Your code goes here:
boot_map_region(kern_pgdir, KERNBASE, 0xffffffff - KERNBASE, 0, PTE_W);

make grade结果

2-2

展示地址

首先是需要声明函数并且在command结构里面加入对应的命令

2-4

2-3

之后就是对应的hanshudaima

int
mon_showva2pa(int argc, char **argv, struct Trapframe *tf)
{
	if (argc != 3 && argc != 2)
	{
		cprintf("mon_showva2pa:Command error!!!");
	}
	else if(argc == 3)
	{
		char *str;
		uint32_t start = (uint32_t)strtol(argv[1], &str, 16);
		uint32_t end = (uint32_t)strtol(argv[2], &str, 16);
		uint16_t ref;
		uint32_t pa;
		int u, w;
		pde_t *pte;
		struct PageInfo *po;
		for ( ; start <= end; start += PGSIZE)
		{
			po = page_lookup(kern_pgdir, (void *)start, &pte);
			pte = pgdir_walk(kern_pgdir, (void *)start, 0);
			if (pte == NULL)
			{
				cprintf("the va does not have a corresponding physical page");
				break;
			}
			ref = po->pp_ref;
			u = ((* pte&PTE_U) == PTE_U);
			w = ((* pte & PTE_W) == PTE_W);
			pa = PTE_ADDR(* pte) | (start & 0xff);
			cprintf("VA = %x, PA = %x, pp_ref = %d, PTE_U = %d, PTE_W = %d\n",start, pa, ref, u, w);
		}
	}
	else if (argc == 2)
	{
		char *str;
		uint32_t va = (uint32_t)strtol(argv[1], &str, 16);
		uint16_t ref;
		uint32_t pa;
		int u, w;
		pde_t *pte;
		struct PageInfo *po;
		po = page_lookup(kern_pgdir, (void *)va, &pte);
		pte = pgdir_walk(kern_pgdir, (void *)va, 0);
		if (pte == NULL)
		{
			cprintf("the va does not have a corresponding physical page");
			return 0;
		}
		ref = po->pp_ref;
		u = ((* pte&PTE_U) == PTE_U);
		w = ((* pte & PTE_W) == PTE_W);
		pa = PTE_ADDR(* pte) | (va & 0xff);
		cprintf("VA = %x, PA = %x, pp_ref = %d, PTE_U = %d, PTE_W = %d\n",va, pa, ref, u, w);
	}
	return 0;
}

运行截图

  • 范围查询

2-5

  • 单页查询

2-6

问题与回答

Q1

程序中的地址从什么时候开始都是虚拟地址了，请找到那几行代码。

A1

  • 分段机制：是 boot.S 中加载 GDT 并启用 cr0 保护模式后启用的
    # Switch from real to protected mode, using a bootstrap GDT
# and segment translation that makes virtual addresses 
# identical to their physical addresses, so that the 
# effective memory map does not change during the switch.
lgdt    gdtdesc
movl    %cr0, %eax
orl     $CR0_PE_ON, %eax
movl    %eax, %cr0
  • 分页机制：是 entry.S 中加载了 entry_pgdir 后启用的
    # Load the physical address of entry_pgdir into cr3.  entry_pgdir
# is defined in entrypgdir.c.
movl  $(RELOC(entry_pgdir)), %eax
movl  %eax, %cr3
# Turn on paging.
movl  %cr0, %eax
orl $(CR0_PE|CR0_PG|CR0_WP), %eax
movl  %eax, %cr0
  • 分页分段都启用后，CPU 便能处理虚拟地址

Q2

mem_init()函数中 kern_pgdir 的虚拟地址是多少？物理地址呢？在我们还未完成本 次 lab 之前，为什么我们已经可以使用虚拟地址了？

A2

cprintf("%x\n", kern_pgdir);得到结果 0xf011b000，对应物理地址 0x0011b000

因为在程序中已经完成了内核部分 4MB 大小的虚拟地址到物理地址的简单映射，在 kern/entry.S 与 kern/entrypgdir.c 中。

Q3

哪一行代码使得本次 lab 所构建的虚拟内存系统真正被使用？请指出它的位置。

A3

mem_init() 中的lcr3(PADDR(kern_pgdir));

Q4

此操作系统可支持的最大物理内存是多少？为什么？

A4

2GB的最大物理内存，所有空闲的物理页面最开始都放在了pages数组中，数组中每个struct大小为8B，UPAGES大小为PTSIZE，所以最多可存储512K个pageInfo，而每个结构对应页面大小4KB，所以最多可以管理2^19 *2^12 = 2^31 = 2GB

Q5

请详细描述在 JOS 中虚拟地址到物理地址的转换过程。

A5

  • 在 inc/mmu.h 中的 PDX、PTX、PGOFF 三个宏将虚拟地址分为 31 - 22 位、21 - 12 位、11 - 0位的三段。
  • 首先通过 cr3 寄存器找到页表目录的物理地址 kern_pgdir，以虚拟地址的高10位 PDX(va) 作为索引在页表目录中找对应的页表项，该表项储存次级页表的起始地址和标志位。
  • 然后通过 PTE_ADDR() 取出将页表项的高 20 位得到次级页表的物理地址，以虚拟地址的中间 10 位 PTX(va) 为索引找到对应的页表项，该表项储存对应物理页框的地址。
  • 最后将线性地址的低 12 位 PGOFF(va) 与物理页框起始地址相加就得到了虚拟地址 va 对应的物理地址 pa。

Q6

在函数 pgdir_walk() 的上下文中，请说明以下地址的含义，并指出他们是虚拟地址还是物理地址：

A6

  1. pgdir 页目录地址，是虚拟地址。
  2. pgtab = PTE_ADDR(pgdir[PDX(va)]) pgdir[PDX(va)] 是页表目录中以 PDX(va)为索引找到的页表项, 页表项中储存的都是物理地址。而宏 PTE_ADDR 则是去除这个地址的高 20 位，因此也是物理地址。
  3. pg = PTE_ADDR(KADDR(pgtab)[PTX(va)]) pg 就是二级页表中对应这个地址的页表项，因此也是物理地址。

Q7

画出本次 Lab 结束后虚拟地址空间与物理地址空间的映射关系，地址空间表示图中应至 少包含 kern_pgdir 与 pages，展示越多的细节越好。（提示：地址空间的表示方式可以 参考 Lab 1-“The PC’s Physical Address Space”小节）

A7

2-7

Operating System

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！

RBAC访问控制 上一篇
DNS Rebinding Attack lab 下一篇