6.828笔记 Lab 2: Memory Management

发表于 分类于

Lab2分为三个部分，第一个部分是Physical Page Management，第二个部分是Virtual Memory，第三部分是Kernel Address Space。

Physical Page Management

物理页管理，需要写一个physical memory allocator，即物理内存分配器，用来管理内存。在内存管理里面，是以4096字节的page（页）为单位的。
需要按顺序完成kern/pmap.c中的下列函数：

  • boot_alloc()
  • mem_init() (只需要完成在check_page_free_list(1)之前的)
  • page_init()
  • page_alloc()
  • page_free()

在kern/init.c里面，有i386_init()函数，调用了kern/pmap.c中的mem_init()函数。mem_init()又调用了i386_detect_memory()函数，用来探测有多少实际内存的。就先打断点看内存数量。得到输出：

1
Physical memory: 131072K available, base = 640K, extended = 130432K

不需要关注是怎么算出来的，只需要看下面几行（单位是kilobytes）：

1
2
3
4
5
npages = totalmem / (PGSIZE / 1024);
npages_basemem = basemem / (PGSIZE / 1024);

cprintf("Physical memory: %uK available, base = %uK, extended = %uK\n",
    totalmem, basemem, totalmem - basemem);

物理地址131072K等于128M，131072K=640K+130432K。也就是模拟器整个物理空间大小为128M，其中base部分（图中的Low Memory部分）为640K，其他的都是extended部分。PGSIZE为4096，即一页有4096个字节。共131072KB内存，每4KB为一页，则npages就是整个物理空间可以划分出的页码数量，为32768页。npages_basemem为base部分可以划分出的页码数量，为160页。

初始页目录

然后就是下面两行：

1
2
kern_pgdir = (pde_t *) boot_alloc(PGSIZE);
memset(kern_pgdir, 0, PGSIZE);

pde_t其实就是一个uint32_t，也就是unsigned int类型的指针，指向内存空间内的一个地址。memset是把从kern_pgdir开始的PGSIZE个字节设置为0，相当于初始化。关键是补充boot_alloc()函数。
boot_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
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 = nextfree;

    if(n>0) {
        nextfree = ROUNDUP(nextfree + n, PGSIZE);
    }

    return result;
}

分配了初始页目录，大小为一页。有一个static变量*nextfree，用来指向下一个可用的地址。ROUNDUP((char *) end, PGSIZE)是把end的地址往上对齐到PGSIZE个字节（向上取整）。如果n>0，把nextfree + n个字节的地址往上对齐，然后赋值给nextfree。最后返回此次调用分配的地址的首地址result。如果超出了物理地址，则报错。但是报错的那里像下面这样写有问题，所以就先删了。

1
2
if (nextfree-KERNBASE > npages*PGSIZE)
    panic("Out of memory!\n");

第一次调用返回的结果给kern_pgdir：

1
kern_pgdir:f0117000

可以看出，返回的是一个虚拟地址。上一次lab说把内核从0x100000开始放，然后地址映射，在这里f0117000会映射到00117000，转换成十进制除以4096，得到279。即内核从0x100000开始放，到0x117000结束。kern_pgdir的地址为0x117000。

PageInfo分配

下面是让分配npages个struct PageInfo，保存在pages中，pages是一个PageInfo *结构。先看PageInfo结构体：

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;
};

其实就是链表，pp_link指向下一个PageInfo结构，pp_ref为0表示此PageInfo对应的一页物理地址未使用，为1表示在使用。
那么代码就比较简单了：

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

直接调用boot_alloc分配npages*sizeof(struct PageInfo)个字节的空间，转换成struct PageInfo*并把初始地址赋给pages，然后把这些地方全部赋值为0。
打印下面几个内容：

1
2
3
4
5
6
7
8
9
cprintf("pages:%#x\n", pages);
cprintf("sizeof PageInfo:%d\n", sizeof(struct PageInfo));
pde_t *afterPageInfo;
afterPageInfo = (pde_t *) boot_alloc(0); //分配0个空间，用于观察此时的nextfree
cprintf("afterPageInfo:%#x\n", afterPageInfo);
//结果
pages:f0118000
sizeof PageInfo:8
afterPageInfo:f0158000

pages的f0118000和刚才的f0117000相差0x1000，也就是分给初始页目录的4KB。每一个PageInfo的大小为8字节，内存大小共131072K，每4K对应于一个PageInfo，所以共131072/4=32768个PageInfo，占用32768*8/4096=64页。
此时的内存空间：

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
35
36

+------------------+  <- 0xFFFFFFFF (4GB)
|      32-bit      |
|  memory mapped   |
|     devices      |
|                  |
/\/\/\/\/\/\/\/\/\/\

/\/\/\/\/\/\/\/\/\/\
|                  |
|      Unused      |
|                  |
+------------------+  <- depends on amount of RAM
|                  |
|                  |
|                  |
| Extended Memory  |
|                  |
|                  |  <- 0x00158000 (32768*8字节的PageInfo结束，新的nextfree)
|                  |
|                  |
|                  |  <- 0x00118000 (pages=0xf0118000，下面的4KB为初始页目录，从这往上是PageInfo)
|                  |  <- 0x00117000 (kern_pgdir=0xf0117000，下面到1MB的地方都是内核代码)
|                  |
+------------------+  <- 0x00100000 (1MB)
|     BIOS ROM     |
+------------------+  <- 0x000F0000 (960KB)
|  16-bit devices, |
|  expansion ROMs  |
+------------------+  <- 0x000C0000 (768KB)
|   VGA Display    |
+------------------+  <- 0x000A0000 (640KB)
|                  |
|    Low Memory    |
|                  |
+------------------+  <- 0x00000000

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
void
page_init(void)
{
    // 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...)
    //  2) The rest of base memory, [PGSIZE, npages_basemem * PGSIZE)
    //     is free.
    //  3) Then comes the IO hole [IOPHYSMEM, EXTPHYSMEM), which must
    //     never be allocated.
    //  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?
    //
    // Change the code to reflect this.
    // NB: DO NOT actually touch the physical memory corresponding to
    // free pages!
    pages[0].pp_ref = 1; //物理页0是使用的
    
    size_t i;
    for (i = 1; i < npages_basemem; i++) {
        //从1开始到npages_basemem的159页（截止640KB）未使用，标记为0
        pages[i].pp_ref = 0;
        pages[i].pp_link = &pages[i+1];
        page_free_list = &pages[i];
    }

    /*
    IOPHYSMEM为0x0A0000
    EXTPHYSMEM为0x100000 （可参考上图
    PGNUM(IOPHYSMEM)是把IOPHYSMEM右移12位，结果为0xA0，即十进制的160
    一直到EXTPHYSMEM为之前的那些。从EXTPHYSMEM开始是内核代码、初始页目录、一串PageInfo
    所以我直接计算出PADDR(pages)+npages*sizeof(struct PageInfo)的物理地址，然后转换成PGNUM
    这个物理地址其实也就是0x00158000
    */
    for (i = PGNUM(IOPHYSMEM); i < PGNUM(PADDR(pages)+npages*sizeof(struct PageInfo)); i++) {
        pages[i].pp_ref = 1;
    }


    //这里的PGNUM(PADDR(pages)+npages*sizeof(struct PageInfo))也可以用PGNUM(PADDR(boot_alloc(0)))替代
    //注：在Lab3中，由于还要在pages后面继续分配内容，所以这两处还是直接用PGNUM(PADDR(boot_alloc(0)))好
    //从这后面的地址都是空的了
    for (i = PGNUM(PADDR(pages)+npages*sizeof(struct PageInfo)); i < npages; i++) {
        pages[i].pp_ref = 0;
        page_free_list->pp_link = &pages[i];
        page_free_list = &pages[i];
    }

    page_free_list = &pages[1];
}

他给出的代码里面page_free_list好像是反着链接的，我写的时候改了一下，正着链接。pages相当于一个数组，放着32768个PageInfo，page_free_list把其中pp_ref = 0的结构体串起来，形成了一个空闲页链表。
page_alloc()和page_free()就很简单了，照着提示，对空闲页链表操作就可以了。最后注释一行panic，运行，出现

1
2
check_page_free_list() succeeded!
check_page_alloc() succeeded!

说明前面的成功完成了。

Virtual Memory

1
2
3
4
5
6
7
8
9
10

           Selector  +--------------+         +-----------+
          ---------->|              |         |           |
                     | Segmentation |         |  Paging   |
Software             |              |-------->|           |---------->  RAM
            Offset   |  Mechanism   |         | Mechanism |
          ---------->|              |         |           |
                     +--------------+         +-----------+
            Virtual                   Linear                Physical

C语言中使用的地址是虚拟地址，经过段式分页得到线性地址，再通过分页得到物理地址，用于访存。重点在从线性地址变换为物理地址的过程。
操作：

  • 使用make qemu进入后，输入ctrl+a，再按c，进入QEMU monitor界面
  • 在QEMU monitor界面中，输入info pg或info mem，官网有介绍
    下面要用到的函数、宏定义主要在kern/pmap.h、inc/memlayour.h和inc/mmu.h中，建议仔细看这几个文件

分页机制

先记录一下分页机制。下图是xv6 book Chapter 2的一张图。
6.828 lab2 page table.JPG

分页是对于虚拟地址的分页，虚拟地址一共有从0到0xffffffff共4GB的空间，而实际上物理上只有128MB的空间。下面要实现的函数中，输入进来的地址就是上图中的虚拟地址，被分为了三个部分，Dir、Table和Offset。文档中说，当前使用的Page Direction的地址存放在CR3寄存器，所以可以直接访问到Page Direction。Dir10位，当作索引，从Page Direction的1024项中得到相关的一项，如果该项存在（PTE_P=1），则此项的高20位是对应的Page Table的物理地址，在C代码中使用时要转换为虚拟地址（加上KERNBASE），得到Page Table的地址。类似地，Table10位，得到对应的项，检测是否存在，若存在，则高20位为对应的物理地址，加上Offset得到实际物理地址。
注意：

  • 每个Page Direction和Page Table都是1024项，每一项都是32位，即占用内存4byte*1k=4KB。所以在代码中，kern_pgdir是4KB的。如果某一项Page Table不存在，要分配空间时，使用的是page_alloc()函数，即分配了一页4KB。
  • Page Table中的每一项的高20位为地址，低12位为权限，所以对应的地址是4KB对齐的，意思就是只能记录0，4KB，8KB这样的地址，也就是Page Table中的每一项对应实际物理地址中的4KB。每一个Page Table有1024个这样的项，则对应4MB。Page Direction有1024个这样的Page Table，则共可以映射4GB的空间，和之前的是对应的。
  • 刚才初始化的kern_pgdir是一个Page Direction，占4KB。之前的代码初始化了kern_pgdir，即全部设置为0。然后通过kern_pgdir[PDX(UVPT)] = PADDR(kern_pgdir) | PTE_U | PTE_P;设置了kern_pgdir的映射，后面的设置需要自己在代码中完成。至于之后每个进程是否需要拥有自己的Page Direction和Page Table，需要在后面的Lab中了解。

pgdir_walk

根据上面的解释和代码中的提示，现在就比较好理解了。

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
pte_t *
pgdir_walk(pde_t *pgdir, const void *va, int create)
{
    // Fill this function in
    pde_t *pde = &pgdir[PDX(va)];
    pte_t *pte;

    //检测Present位是否存在
    if(*pde & PTE_P) {
        pte = KADDR(PTE_ADDR(*pde));
    }
    else {
        if(!create) {
            return NULL;
        }
        struct PageInfo *p = page_alloc(ALLOC_ZERO);
        if(p == NULL) {
            return NULL;
        }
        p->pp_ref++;
        pte = (pte_t *)page2kva(p);
        *pde = PADDR(pte) | PTE_P | PTE_W | PTE_U;
    }
    return &pte[PTX(va)];
}

boot_map_region

boot_map_region()是把从va开始的size个虚拟地址映射到pa开始的size个物理地址。如果在Page Direction对应的项不存在，则会分配空闲的一页，把这一页的地址记录在Page Direction中，在分配的这一页中的对应的4KB对齐的位置，写入对应的物理地址和权限，但是并没有对该物理地址进行读写操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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;
    for(i=0; i<size/PGSIZE; i++)
    {
        pte_t *pte = pgdir_walk(pgdir, (void *)va, 1);
        if(pte == NULL) {
            panic("boot_map_region(): out of memory!");
        }
        *pte = pa | perm | PTE_P;
        va += PGSIZE;
        pa += PGSIZE;   
    }
    
}

其他的就比较简单了，在page_insert()中有一点要注意，先pp->pp_ref++;，参考的那个博客里面也都讲了。

Kernel Address Space

在这一部分设置内核的映射。在inc/memlayout.h中有虚拟的4GB的分配。从UTOP往下是用户可用的；从UTOP到ULIM，用户和内核都是只读的；从ULIM往上到KERNBASE有一段，放的是栈之类的；从KERNBASE到4GB都是内核的，内核可以读写，用户无法访问。KERNBASE为0xf0000000，到0xffffffff有256MB。
根据博客的提示，在mem_init()对应位置加上：

1
2
3
boot_map_region(kern_pgdir, UPAGES, npages*sizeof(struct PageInfo), PADDR(pages), PTE_U);
boot_map_region(kern_pgdir, KSTACKTOP-KSTKSIZE, KSTKSIZE, PADDR(bootstack), PTE_W);
boot_map_region(kern_pgdir, KERNBASE, 0xffffffff-KERNBASE+1, 0, PTE_W);

分别是把npages个PageInfo映射到UPAGES的虚拟地址，用户可读；把KSTACKTOP-KSTKSIZE开始的KSTKSIZE个字节映射到bootstack的位置；把从KERNBASE，即0xf0000000开始的256MB映射到物理0的位置，此时，访问虚拟地址0xf0001000就会转到物理地址0x00001000。
最后make grade，满分。

总结

下面这幅图总结了这次Lab的大部分内容，其中，kern_pgdir的位置和之前的不一样，应该是因为要完成Lab，在之前的基础上对内核里面添加了代码，所以内核部分占用地多了，所以kern_pgdir地址靠后了。
6.828 lab2 总结.jpg

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
(qemu) info pg
VPN range     Entry         Flags        Physical page
[ef000-ef3ff]  PDE[3bc]     -------UWP
  [ef000-ef03f]  PTE[000-03f] -------U-P 0011b-0015a
[ef400-ef7ff]  PDE[3bd]     -------U-P
  [ef7bc-ef7bc]  PTE[3bc]     -------UWP 00003
  [ef7bd-ef7bd]  PTE[3bd]     -------U-P 0011a
  [ef7bf-ef7bf]  PTE[3bf]     -------UWP 00002
  [ef7c0-ef7df]  PTE[3c0-3df] ----A--UWP 00001 00004-00022
  [ef7e0-ef7ff]  PTE[3e0-3ff] -------UWP 00023-00042
[efc00-effff]  PDE[3bf]     -------UWP
  [efff8-effff]  PTE[3f8-3ff] --------WP 0010e-00115
[f0000-f03ff]  PDE[3c0]     ----A--UWP
  [f0000-f0042]  PTE[000-042] --------WP 00000-00042
  [f0043-f009f]  PTE[043-09f] ---DA---WP 00043-0009f
  [f00a0-f00b7]  PTE[0a0-0b7] --------WP 000a0-000b7
  [f00b8-f00b8]  PTE[0b8]     ---DA---WP 000b8
  [f00b9-f00ff]  PTE[0b9-0ff] --------WP 000b9-000ff
  [f0100-f0105]  PTE[100-105] ----A---WP 00100-00105
  [f0106-f0114]  PTE[106-114] --------WP 00106-00114
  [f0115-f0115]  PTE[115]     ---DA---WP 00115
  [f0116-f0118]  PTE[116-118] --------WP 00116-00118
  [f0119-f011b]  PTE[119-11b] ---DA---WP 00119-0011b
  [f011c-f015a]  PTE[11c-15a] ----A---WP 0011c-0015a
  [f015b-f03ff]  PTE[15b-3ff] ---DA---WP 0015b-003ff
[f0400-f7fff]  PDE[3c1-3df] ----A--UWP
  [f0400-f7fff]  PTE[000-3ff] ---DA---WP 00400-07fff
[f8000-fffff]  PDE[3e0-3ff] -------UWP
  [f8000-fffff]  PTE[000-3ff] --------WP 08000-0ffff

一个一个来分析。

  • 0x3bc=956，里面的PTE是从000-03f，0x3f=63。和上图分析的一样，只使用了前64项
  • 0x3bd=957，上面说这是Page Direction。仔细观察，会发现这里面的PTE和info pg显示出的PDE相同，即在这个地方放的是kern_pgdir，里面的页表项即整个Page Dicection映射的项
  • 0x3bf=959，0x3f8-0x3ff即1016到1023，和之前的分析一致
  • 0x3c0=960，从0到0x3ff，即1023都有项，只不过有些是dirty和accessed了的
  • PDE从0x3c1到0x3ff，即961到1023，都是有项的

观察0x3bd项的Physical page，这个的意思就是Page Direction中分配了的Page Table对应的物理地址。有一个是0011a，其他的是从1到0x42，即66，和之前的分析一致。至于第一个PTE是3而不是1，经过测试发现，按顺序的话，本来应该是PageInfo[1]，即0x1000，但是有check程序，估计释放的时候把顺序改变了，所以前三个PageInfo的顺序反了。

1
2
3
4
5
(qemu) info mem
00000000ef000000-00000000ef040000 0000000000040000 ur-
00000000ef7bc000-00000000ef7be000 0000000000002000 ur-
00000000ef7bf000-00000000ef800000 0000000000041000 ur-
00000000efff8000-0000000100000000 0000000010008000 -rw

和上面的结果类似，只是更简略了，意思是一样的，就不展开讲了。

最后，再来一个测试。比较明显地，PageInfo被映射了两次，分别是在956项和960项。kern_pgdir[956]的第0项对应PageInfo的前4KB。PageInfo的物理地址为0x11b000，在kern_pgdir[960]项中对应11b项，即283项。在mem_init()后面加上：

1
2
3
4
5
6
7
8
9
cprintf("956[0](pages's pa):\n");
pde_t pde = kern_pgdir[956];
pte_t *pte = KADDR(PTE_ADDR(pde));
cprintf("%#08x\n", pte[0]);

cprintf("960[283](pages's pa):\n");
pde = kern_pgdir[960];
pte = KADDR(PTE_ADDR(pde));
cprintf("%#08x", pte[283]);

得到结果：

1
2
3
4
956[0](pages's pa):
0011b005
960[283](pages's pa):
0011b063

可见，前20位都是0011b，都做出了正确的映射。前一个的权限是005,也就是U-P。第二的权限是063，DA—WP，用户无法访问。
Lab2做得很艰难，直接看人家的博客看不懂，然后就开始看课程给的资料，看一次看不懂，各种资料换着看，加上抄抄代码，调试输出，最后终于搞懂了。最后的Challenge做了一个，就是显示虚拟地址对应的物理地址，大致怎么做还是很清楚的，但是一些代码上的具体的细节还是不太行，最后在网上抄了一个，能看懂。像修改权限位那些，就先没做，如果后面的Lab需要了就再弄。