MIT 6.828 Lab:Memory Management

Posted on

实验2：内存管理

MIT 6.828 Operating System Engineering

该实验原始指南

简介

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

  • 内核的物理内存分配器：因此内核可以分配内存，释放内存。分配器将以4096字节为单位运行，即页。这次lab的任务是维护数据结构，记录哪些物理页面是空闲的，哪些是已分配的，以及共享每个已分配页面的进程数。除此之外，还要编写例程来分配和释放内存页面
  • 虚拟内存：将内核和用户程序使用的虚拟地址映射到物理内存中的地址。当指令使用内存时，x86硬件的内存管理单元（MMU）执行映射，查询一组页表

实验2包含以下新的源文件

  • memlayout.h：描述了虚拟地址空间的布局
  • pmap.c：读取此设备硬件以便计算出有多少物理内存
  • pmap.h：定义了相关数据结构

重点阅读memlayout.h 以及 pmap.h，还需参考 inc/mmu.h

第1部分：物理页面管理

操作系统需要追踪那部分物理内存是空闲的，那部分是正在使用的。JOS以页粒度（page granularity）管理PC的物理内存，以便可以使用MMU映射和保护每个分配的内存。

现在要编写物理页分配器（physical page allocator）。它通过以struct PageInfo组成的链表跟踪哪些页面是空闲的（与xv6不同，它们没有嵌入到自由页面本身中？？？），每个对应于一个物理页面。在编写剩余的虚拟内存实现之前，您需要编写物理页分配器，因为页表管理代码需要分配用于存储页表的物理内存。

In the file kern/pmap.c, you must implement code for the following functions (probably in the order given).

  • boot_alloc()
  • mem_init() (only up to the call to check_page_free_list(1))
  • page_init()
  • page_alloc()
  • page_free()

check_page_free_list() and check_page_alloc() test your physical page allocator. You should boot JOS and see whether check_page_alloc() reports success. Fix your code so that it passes. You may find it helpful to add your own assert()s to verify that your assumptions are correct.

先看看相关的函数理理思路：
mem_init()：在内核刚开始运行时就会调用这个子函数，对整个操作系统的内存管理系统进行一些初始化的设置，比如设定页表等等操作。该函数里面又会调用以下子函数。
static void i386_detect_memory(void)：在MIT 6.828 Lab:Booting a PC的图中我们看到物理内存被默认分为三个部分。该函数会去探测basemem和extmem两部分的大小，并计算出对应的物理页的数量。

  • 0x00000~0xA0000，这部分也叫basemem，是可用的
  • 0xA0000~0x100000，这部分叫做IO hole，是不可用的，主要被用来分配给外部设备、BIOS ROM
  • 0x100000~0x...，这部分叫做extmem，是可用的，这是最重要的内存区域

kern_pgdir = (pde_t *) boot_alloc(PGSIZE); memset(kern_pgdir, 0, PGSIZE);：kern_pgdir是一个指针，它是指向操作系统的页目录表的指针，操作系统之后工作在虚拟内存模式下时，就需要这个页目录表进行地址转换。我们为这个页目录表分配的内存大小空间为PGSIZE，即一个页的大小。并且把这部分内存清0。

boot_alloc

这个函数是实验要完成的函数：它只是被用来暂时当做页分配器，之后我们使用的真实页分配器是page_alloc()。注释中对该函数要实现什么功能已经说得很明白。

1
2
3
4
5
6
7
8
9
10
11
// 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(nextfree + n,PGSIZE);
if((uint32_t)nextfree - KERNBASE > (npages*PGSIZE))
        panic("out of memory\n");
 cprintf("boot_alloc %d bytes memory success\n",n);
 return result;

kern_pgdir[PDX(UVPT)] = PADDR(kern_pgdir) | PTE_U | PTE_P;这一条语句就是为页目录表添加第一个页目录表项。通过查看memlayout.h文件，我们可以看到，UVPT的定义是一段虚拟地址的起始地址0xef400000，从这个虚拟地址开始，存放的就是这个操作系统的页表kern_pgdir，所以我们必须把它和页表kern_pgdir的物理地址映射起来，PADDR(kern_pgdir)就是在计算kern_pgdir所对应的真实物理地址。

1
2
3
4
5
6
7
8
9
10
11
struct PageInfo {
        // Next page on the free list.
        struct PageInfo *pp_link;

        // pp_ref is the count of pointers (usually in page table entries)
        // to this page, for pages allocated using page_alloc.
        // Pages allocated at boot time using pmap.c's
        // boot_alloc do not have valid reference count fields.

        uint16_t pp_ref;
};

接下来的注释提醒我们要去分配一块内存，来存放一个struct PageInfo的数组，上面就是结构在memlayout.h中的定义，数组中的每一个PageInfo代表内存当中的一个物理页。操作系统内核就是通过这个数组来追踪所有内存页的使用情况。

1
2
pages = (struct PageInfo *)boot_alloc(npages * sizeof(PageInfo));
memset(pages,0,npages * sizeof(PageInfo));

page_init()

之后就会调用page_init()，也就是这个练习的重头戏。通过上面的页表的分配，目前的物理内存状态如下所示

如注释所说，该函数要初始化pages数组和page_free_list链表，上图给出了此时物理内存的使用情况，因此需要根据该图来初始化数组和链表。

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
size_t i;

// IOPHYSMEM:the start address of IO hole 
// io_hole:the index of IO hole in pages
size_t io_hole = (size_t)IOPHYSMEM / PGSIZE;

// boot_alloc(0):return the end address of kernel
// kernel_end:including [IOPHYSMEM,EXTPHYSMEM] and [EXTPHYSMEM,...]
size_t kernel_end = PADDR(boot_alloc(0)) / PGSIZE;

page_free_list = NULL;
for(i = 0;i < npages ;i++){
        // mark physical page 0 as in use
        if(i == 0){
                pages[0].pp_ref = 1;
                pages[0].pp_link = NULL;
                continue;
        }
        // mark physical page [PGSIZE,npages_basemem * PGSIZE] as free
        else if(i >= io_hole && i < kernel_end){
                pages[i].pp_ref = 0;
                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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct PageInfo *result;

      // out of memory
      if(page_free_list == NULL)
              return NULL;

      result = page_free_list;
      page_free_list = result->pp_link;

      result->pp_link = NULL;

      // page2kva:get virtual address by physical address(result)
      if(alloc_flags & ALLOC_ZERO)
              memset(page2kva(result),0,PGSIZE);
      return result;

page_free

1
2
3
4
5
6
7
// 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 still in used\n");
       pp->pp_link = page_free_list;
       page_free_list = pp;

重新回到mem_init函数，会调用check_page_free_list(1)和check_page_alloc()。这两个函数通过一系列断言，判断我们的实现是否符合预期。至此第一部分就算完成。

第2部分：虚拟内存

在做其他任何事情之前，请熟悉x86的保护模式内存管理架构：即分段和页面转换。

80386分两步将逻辑地址（即程序员查看的地址）转换为物理地址（即物理内存中的实际地址）

  • 段转换，其中逻辑地址（由段选择器和段偏移组成）被转换为线性地址。
  • 页面转换，其中线性地址转换为物理地址。此步骤是可选的，由系统软件设计人员决定。此阶段的地址转换实现了面向页面的虚拟内存系统和页面级保护所需的基本功能。

段翻译

处理器将逻辑地址转换为线性地址，需要使用以下数据结构：描述符、描述符表，选择器、段寄存器。

描述符由编译器，链接器，加载器或操作系统创建，而不是由应用程序员创建

段描述符存储于两种描述符表中的一种：全局描述符表（GDT）和本地描述符表（LDT）。处理器通过GDTR和LDTR寄存器将GDT和当前LDT定位在存储器中。这些寄存器将表的基址存储在线性地址空间中，并存储段限制

逻辑地址的选择器部分通过指定描述符表并索引该表内的描述符来标识描述符。应用程序可以将选择器看作指针变量中的字段，但选择器的值通常由链接器或链接加载器分配（固定）。

80386在段寄存器中存储来自的描述符的信息，从而避免在每次访问存储器时查询描述符表。

每个段寄存器都有一个“可见”部分和一个“不可见”部分。这些段地址寄存器的可见部分由程序操作，就好像它们只是16位寄存器一样。不可见部分由处理器操纵。

加载这些寄存器的操作是正常的程序指令（之前在第3章中描述 ）。这些说明分为两类：

使用正常的程序指令，程序使用16位选择器加载段寄存器的可见部分。处理器自动从描述符表中提取基址，限制，类型和其他信息，并将它们加载到段寄存器的不可见部分。

因为大多数指令指的是其选择器已经被加载到段寄存器中的段中的数据，所以处理器可以将指令提供的段相对偏移添加到段基地址而没有额外的开销。

页面翻译

虚拟，线性和物理地址

引用计数

页表管理

第3部分：内核地址空间

参考

参考
参考
参考