MIT 6.828-jos-xv6-lab2: memory management

先把内存整体的分布图放上来，目前还不能完全看懂

在LAB1之后，形成的物理内存的状态是下面这样的

然后手动开启了映射机制之后，将从0XF0100000开始的内存映射到了0x0100000的位置上

Part1：物理内存分配器

首先是要写一个物理内存分配器，就是分配物理内存的，需要跟踪内存中有哪些物理内存是可用的，哪些是不可用的。

XV6中空闲物理内存的链表项是存储在空闲页中的，因为里面本来就没有内容。但是JOS是进行了单独的存储管理的。

JOS使用了两个物理内存分配器，boot_alloc和page_alloc

Boot_alloc只在系统加载的时候运行一次，在page_init之后就不再调用了，此后的物理内存分配全部由page_alloc来完成

之所以采用了两个内存分配器的设计，在XV6 book中给出的理由是：在加载之后，还没有分配器的情况下，大部分代码没办法使用锁及4MB以上的内存，而第一个分配器在4MB空间内进行了不需要锁的内存分配，而第二个可以使用锁，使得更多的内存可以用于分配

但是JOS里好像是不一样的。因为在开启了内存映射之后，内核继续运行，此时需要开启页机制，建立页表等。但是在还没有建立页表的时候，对内存的分配也是需要按照页来进行的，这样在开启了页机制之后能平滑过渡，所以采用了boot_alloc这样一个函数，然后建立物理页内存表，进行物理页的管理

这是调用关系图，可以看到只有两个地方调用了boot_alloc

回顾一下上次实验的内容，首先是bootloader加载内核，内核的第一条指令从0x010000c开始，实际上，JOS系统加载的地址是从0X0100000开始的，并向高地址扩展，在没有开启手动开启内存映射之前，虚拟地址就是物理地址，所以内核加载在了这个地方，之后开启了映射，虚地址0xf0100000就会映射到0x0100000的位置

但是这个简单的映射是不够的，需要建立页机制，那么首先需要完成的就是物理内存分配器

1. Boot_alloc函数

Boot_alloc函数接收一个参数n，假如说该参数为0，返回当前可用的空闲页的地址，大于0的话，那么就分配足够装下n个字节的页出来

但是，当boot_alloc第一次运行的时候，还需要将第一个可用的空闲地址进行初始化，JOS里这一段代码写的相当简洁，使用了static局部变量

这样在第一次运行的时候是空的，接下来就不会了

关于end，一张图就能看清楚了

elf格式可执行文件，bss是未进行初始化的全局变量，是载入内存中的最后一部分，随后是end标记

所以第一次运行的时候，实际上将nextfree指向了.bss后面

然后就是要进行分配了

ROUNDUP就是寻找离nextfree+n最近的且地址高于nextfree的可以整除PGSIZE的地址，更新nextfree，然后返回结果就可以了

在mem_init中有下面一句

这个调用boot_alloc生成了一个4KB大小的空间，是用来存在页表目录的

也就是说，现在内存中的实际状态应该是下面这样的

1. mem_init函数

该函数就是要建立内核地址空间，而用户空间则不在此实现

主要功能是探测当前可用内存有多少页，建立页表目录，并初始化处于最高地址处的1024*4096字节（也就是一张页表能映射的最大地址范围）所对应的也表目录项，该部分指向页表目录所在位置，也就是说，页表目录存储在用户可访问的最高虚拟地址，就是下面这句话

接下来就是要建立物理内存页的管理机制，使用一个PageInfo的数组来管理每个物理内存页

我一开始居然用了new方法，且不说new方法C标准支不支持，这个方法本身就不能用在这，因为new是在堆内存中寻找一块可用的区域，但是现在我们需要做的显然不是讲页表目录放在堆中啊，而是申请空间来做这件事

看一下PageInfo的设计，这里需要注意的是使用了引用计数

在分配完pages之后，得到的内存状态应该是下面这样的

而实际中的内核是运行在低地址的，所以如下所示

所以就是将上面两块空白的地方加到链表中就可以了，包括前面的一小块和后pagedir和pages后面的部分

1. Page_init函数

这个函数就是根据上面那个已使用内存图来进行物理内存页的初始化。我一开始看这部分的时候有点懵，被陷在实现细节中，越来越晕，但是后来发现，我忘记了当前在做什么事，为什么要做这件事。

当前就是要将所有物理内存分页，然后确定哪些页当前已经被占用，哪些页是空闲的，将空闲的页连接成一个表就可以了

这里的注释写的很明白了，可用的位置就是上面图中的白色区域，中间的部分必须都标记为已经使用了的

1. Page_alloc函数

这个函数就是返回一个当前空闲的物理页，进行相应的处理

这里需要注意的是，需要将对应页的PageInfo的pp_link置为NULL，这样可以探测出double free的问题

1. Page_free函数

回收一个物理页，但是回收的时候需要注意，需要引用数为0而且pp_link域一定为空，如果引用数不为零，说明目前还有进程在使用该页，如果pp_link不为空，说明已经在空闲列表中了，再次释放是发生了double free

PART2：virtual memory

C指针实际上对应的是虚拟地址中的offset项

非常不幸的是，JOS也抛弃了段。。。。

所有的段全部都是开始地址为0，大小限制为0XFFFFFFFF

一旦在启动加载内核的时候启动了保护模式，所有的地址都是通过MMU进行转换的了，根本没有办法直接使用一个线性地址或者物理地址，所以的地址引用都被解析为虚拟地址，然后送入MMU进行解析

比如说指针，都是虚地址，所以*pointer操作中的pointer必须是虚地址

JOS中是做了虚地址和物理地址的区分的

JOS操作系统内有时是需要知道物理内存的，比如说映射页表

但是上面说了，我们不知道实际的物理地址是多少，所以JOS选择将0xf0000000地址全部映射到0地址处，就是为了帮助JOS读写物理内存区域，为了读写某一物理区域，需要将目前已知的物理地址ADDR，需要将ADDR加上0xf0000000，经过地址映射之后就又变成了addr

同样的，知道虚拟地址求解物理地址，直接减就可以了

Reference counting

由于各种原因，同一个物理页框是可能被多个虚拟页映射的，这种情况下需要pp_ref值，当这个值变成0的时候，说明没有程序需要这块内存了，因此可以释放掉了

但是这个引用计数一般情况下是等于该物理页框在所有页表中出现的次数，也就是使用该页的进程数，但是一般只对低于UTOP的页进行引用计数

不包括UTOP之上的页表，是因为那上面的页表是boot_alloc建立的，是属于内核的，任何时候都不应该被释放，所以也没有

Page table management

TLB失效的问题

TLB是为了高速的地址翻译而设计的，一个进程的页表在内存和TLB中都存在(部分存在)，这样如果程序员修改了页表，那么在TLB中的页表与实际的页表就会出现不一致的情况，这样会导致地址的翻译错误。

所以为了防止这种现象的出现，页表发生修改之后，需要重载CR3，使整个TLB中的数据都失效，然后重新载入，或者使用INVLPG命令

逻辑地址-线性地址-物理地址注意区分

在开启页映射机制之前，系统还是采用段式地址变换的，逻辑地址+base=线性地址(这里base是负的0xf0000000)，而这个线性地址直接就等于物理地址了

而页映射机制处理的是线性地址到物理地址的转换，也就是逻辑地址进行变换之后得到的地址，不能弄混

Pgdir_walk()函数

这个函数我写了很久，都觉得写的别别扭扭的，回头翻了一下文档，才发现自己理解的不深

上面这张图中，页表目录和和表的格式都是一样的

前面20位是物理地址的高20位，如果是页目录，那么包含的内容就是对应页表的地址的高20位，而如果是页表，那么对应的就是实际页的高20位地址

另外，在内核中世纪处理的都是虚拟地址，所以需要转来转去的

这个函数的主要功能就是给定一个页表目录和虚拟地址，要你返回二级页表中对应的页表项的指针

有几个需要注意的地方

1. 页表目录和页表中存的都是物理地址，而实际的代码操作都是虚拟地址，这个一定要转换，比如说上面代码中的memset函数，已经二级页表的指针中，都必须使用虚拟地址
2. 在获取页表目录之后，一定要检查是否已经存在了，没有存在的话，根据create的值决定是否穿件一个新的页表
3. 如果新建了一个页表，插入到页表目录中的时候，需要注意给足权限，是因为页表目录中的一个表项对应的1024个物理页，这些物理页的控制权限可能都各不相同，所以当前能做的就是不对其读写权限做任何限制，而是在页表中去限制

Boot_map_region函数

这个函数的作用以及实现如下

对于给定的虚拟地址，利用上面实现的pgdir_walk函数，找到对应虚拟页所在的表项，然后填充表项内容就可以了

Page_lookup函数

该函数就是给定一个虚拟地址，返回一个描述该虚拟地址指向的物理地址的结构体

Page_remove函数

这个函数就是将一个给定的虚拟地址与对应的物理页之间解除映射

解除映射的时候需要考虑的问题有：引用计数需要维护，引用计数为0，那么就可以释放这个物理页了

一开始我以为只有物理页的引用计数为0的时候，TLB失效的函数才需要调用，但是后来一想显然不对，因为物理页是否需要，与一个进程空间中对应的某虚拟地址是否有映射并不完全对应的，只要这个进程的页表中的内容发生了变化，TLB就会失效

Page_insert函数

将一个虚拟地址映射到一个实际的物理页面中去

这个函数的实现要非常小心才行，因为这个函数的调用可能有多种情况，如果同一个结构体，同一个虚拟地址多次调用怎么办，这个时候显然是不能反复处理的，尤其是引用计数；另外，假如说已经改地址已经映射到了一个物理页上，那么需要将其remove掉

上面的几个函数对应的是页面映射中经常需要用到的，诸如给定虚拟地址返回页表项，解除映射，增加映射等等，不得不说，这里几个函数的设计非常高超，不但功能很完善，而且各部分功能清晰，分离合理

Part3: kernel address space

JOS将内存分为了两部分，一部分是用户空间，运行在虚拟的低地址，另一部分是内核空间，运行在了高虚拟地址空间

分割线是ULIM

为了保护内核的代码和数据，需要在页中增加权限限制，使得用户空间的代码只能访问用户空间的内存，这样用户的代码产生的bug不会伤害到内核空间

在[UTOP, ULIM)的范围内，用户代码和内核代码都是可以访问的，但是都不可以写。这部分空间的设立主要是为了能让用户读取一些内核中的数据结构

注意下图中权限的变化

这部分是要完成在mem_init函数内的代码，实际上就是利用前面实现的boot_map_region将给定的虚拟地址映射到物理地址上去

首先是物理页表数组的映射，这部分是用户无权限操作，内核可读写的

这部分的实际地址是内核代码和数据区以及页表目录区之后的部分，希望从虚拟地址PAGES处映射过来

接下来是内核栈的映射

内核栈的虚拟地址是[KSTACKTOP-KSTKSIZE, KSTACKTOP)，映射到的物理内存地址是bootstack处

这里面采用了保护页的做法，就是在规定的栈大小的后面，防止的是invalid的内存部分，这样当栈溢出的时候会出发错误，而不是毁掉更低地址的内存

最后是将内核的基地址映射到0地址处

在设置完上面的内容之后，就可以开启页机制了

最后的映射关系如下

写这个实验累死我了。。。。