xv6(3) 内存管理部分
*************
内存管理部分
内存管理这部分我没有集中在一起叙述，本节只是讲述物理内存如何组织管理，页表的内核部分如何创建的，与地址转换的在启动理论那一块儿说了，虚拟地址空间的用户部分在进程那儿叙述，堆内存管理也在进程那一块儿讲述。废话不多说来看本节内容：
我之前看了另外一个小型操作系统，我觉得那里面对内存管理层次抽象分的很清楚，每个操作系统都有相通性，这里拿出来说说：
- 物理内存管理，主要就是物理页的分配与回收
- 虚拟内存管理，主要就是虚拟页的分配与回收
- 物理内存与虚拟内存建立映射，那就是页表了
xv6 因其功能少，物理内存与虚拟内存的特殊关系，虚拟内存管理这一块很弱，可能水平还是不够，我想了半天都没能把这一块儿很好地抽象出来，不过物理内存管理和建立映射这一块儿还是很明显的，主要也就是从这几个方面来看
物理内存管理
对于物理内存和虚拟内存我们都是以页为单位进行管理，像要管理这种一页一页的，一块一块的对象，最常用的就是两种方法：
- 空闲链表法，将空闲页/块给串起来，分配就是删除一个结点，回收就是插入一个结点
- 位图，额外拿出一页/块当作位图，一位表示一页/块的使用情况，通常 1 表示使用中，0 表示空闲。分配某页/块就是将相应的位置 1，回收就是将相应的位置 0
空闲链表法
xv6 对于物理内存的组织管理使用的是空闲链表法。相关代码在 kalloc.c 文件中，我们来具体分析一下：
首先定义了两个结构体：
struct run {
struct run *next; //指向下一个空闲物理页
};
struct {
struct spinlock lock; //自旋锁
int use_lock; //现下是否使用锁？
struct run *freelist; //空闲链表头
} kmem;
这两个结构体什么意思，有什么用？看个图就明白了：
所以 kmem 就像个物理内存分配器，这个 freelist 就是这片空闲页链表的链头，分配内存的时候就将它先分配出去，然后每页里面有一个指针，指向下一个空闲页。有了这个了解之后来看分配回收物理页的代码
分配回收
char* kalloc(void)
{
struct run *r; //声明run结构体指针
if(kmem.use_lock) //如果使用了锁，取锁
acquire(&kmem.lock);
r = kmem.freelist; //第一个空闲页地址赋给r
if(r)
kmem.freelist = r->next; //链头移动到下一页，相当于把链头给分配出去了
if(kmem.use_lock) //如果使用了锁，解锁
release(&kmem.lock);
return (char*)r; //返回第一个空闲页的地址
}
代码很简单，就是加锁，取链头地址，链头移到下一个空闲页，释放锁，返回取到的链头地址。
void kfree(char *v) //释放页v
{
struct run *r;
//这个页应该在这些范围内且边界为4K的倍数
if((uint)v % PGSIZE || v < end || V2P(v) >= PHYSTOP)
panic("kfree");
// Fill with junk to catch dangling refs.
memset(v, 1, PGSIZE); //将这个页填充无用信息，全置为1
if(kmem.use_lock) //如果使用了锁，取锁
acquire(&kmem.lock);
r = (struct run*)v; //头插法将这个页放在链头
r->next = kmem.freelist; //当前页指向链头
kmem.freelist = r; //链头移到当前页
if(kmem.use_lock) //如果使用了锁，解锁
release(&kmem.lock);
}
基本上是 kalloc 的逆操作，先检查要释放的页合理与否，然后填充无效信息，再取锁，使用头插法将这个页放在链首，释放锁。
回收多个连续页
void freerange(void *vstart, void *vend) //连续释放vstart到vend之间的页
{
char *p;
p = (char*)PGROUNDUP((uint)vstart);
for(; p + PGSIZE <= (char*)vend; p += PGSIZE)
kfree(p);
}
这个函数就是连续调用 kfree 来回收多个页，还有两个函数 kinit1，kinit2 是上述 freerange 函数的封装：
void kinit1(void *vstart, void *vend) //kinit1(end, P2V(4*1024*1024));
{
initlock(&kmem.lock, "kmem");
kmem.use_lock = 0;
freerange(vstart, vend);
}
void kinit2(void *vstart, void *vend) //kinit2(P2V(4*1024*1024), P2V(PHYSTOP));
{
freerange(vstart, vend);
kmem.use_lock = 1;
}
它俩是在 main.c 的 main 函数中被调用，调用的参数也已经注释在后边。调用这两个函数就是初始化内存，将内存一页一页的回收，使用头插法链在一起组成一个空闲链表，是为初始化。
另外这里使用初始化内存的时候 kmem.use_lock = 0 表示不使用锁，这里应是为了加快初始化内存的速度，不然每次初始化(回收)一页物理内存都上锁解锁的话还是很费时的。因为正处于启动初始化的环境，不会有多处理器，中断，多进程等竞争条件，不使用锁完全没得问题。
关于物理内存的管理还要注意一点，这些所有函数都是使用的虚拟地址，管理物理内存不是说就要使用物理地址，自从分页机制开启之后，使用的一直就是线性地址或者说虚拟地址。自由页表和 MMU 单元将其转化为物理地址。
但前面也说了，在启动 开启分页机制的时候使用的是临时页表，有临时当然就有正式，下面来看正式页表的创建。
页表内核部分
映射关系
要了解其他几个参数还需要先来了解 xv6 的虚拟地址空间和实际的物理地址空间的映射关系，这也有相应的结构体表示：
#define EXTMEM 0x100000 // Start of extended memory
#define PHYSTOP 0xE000000 // Top physical memory
#define DEVSPACE 0xFE000000 // 一些设备的地址，比如apic的一些寄存器
// Key addresses for address space layout (see kmap in vm.c for layout)
#define KERNBASE 0x80000000 // 内核的起始虚拟地址
#define KERNLINK (KERNBASE+EXTMEM) // 内核文件的链接地址
#define V2P(a) (((uint) (a)) - KERNBASE) //内核虚拟地址转物理地址
#define P2V(a) ((void *)(((char *) (a)) + KERNBASE)) //物理地址转内核虚拟地址
static struct kmap {
void *virt;
uint phys_start;
uint phys_end;
int perm;
} kmap[] = {
{ (void*)KERNBASE, 0, EXTMEM, PTE_W}, // I/O space
{ (void*)KERNLINK, V2P(KERNLINK), V2P(data), 0}, // kern text+rodata
{ (void*)data, V2P(data), PHYSTOP, PTE_W}, // kern data+memory
{ (void*)DEVSPACE, DEVSPACE, 0, PTE_W}, // more devices
};
上面那一坨就是说明虚拟地址空间内核部分到物理内存的映射关系，看起来可能很麻杂，做了一张表格和图：
从这张图可以看出，内核部分的虚拟地址空间和物理地址空间就是一一对应的，只是相差了 0x8000 0000，所以这就是为什么简单的宏 V2P，P2V 就可以实现虚拟地址物理地址之间的转换，当然这只是内核部分才行。用户态部分的我们还没有涉及，用户态下的虚拟地址到物理地址之间没有什么特定的关系，转换就必须要使用页表了，相关部分在进程我们再详述，这里只关注内核部分。
再者也可以看出 xv6 并没有使用全部的 4G 地址空间，有很大一部分都没有使用，内核的为映射部分和物理地址空间的未映射部分两者大小是不一样的，可能图画得有些迷惑，拿出来说一下。另外关于设备部分是直接映射的，是真的一一对应，虚拟地址和物理地址一样，这部分地址空间是分配给一些设别的，比如 APIC 的一些寄存器
映射函数
页表就是物理内存和虚拟内存的纽带，所以映射函数实际上就是创建页表项，来看相关代码：
#define PDX(va) (((uint)(va) >> PDXSHIFT) & 0x3FF) //高10位
#define PTX(va) (((uint)(va) >> PTXSHIFT) & 0x3FF) //中10位
#define PGADDR(d, t, o) ((uint)((d) << PDXSHIFT | (t) << PTXSHIFT | (o))) //d为高10位，t为中10位，o为低12位，将他们组合成虚拟地址
static pte_t * walkpgdir(pde_t *pgdir, const void *va, int alloc) //根据虚拟地址 va 返回相应的页表项地址
{
pde_t *pde; //页目录项地址
pte_t *pgtab; //一级页表地址
pde = &pgdir[PDX(va)]; //va取高12位->页目录项
if(*pde & PTE_P){ //若一级页表存在
pgtab = (pte_t*)P2V(PTE_ADDR(*pde)); //取一级页表的物理地址，转化成虚拟地址
} else {
if(!alloc || (pgtab = (pte_t*)kalloc()) == 0) //否则分配一页出来做页表
return 0;
// Make sure all those PTE_P bits are zero.
memset(pgtab, 0, PGSIZE); //初始化置0
*pde = V2P(pgtab) | PTE_P | PTE_W | PTE_U; //将新分配出来的以及页表记录在页目录中，标识存在，可读可写，用户可访问
}
return &pgtab[PTX(va)]; //va取中10位->页表项
}
xv6 使用的是二级页表，后面我称之为页目录和页表，每页对应着一个页表项，每个页表对应着一个页目录项。walkpgdir 函数就是根据页目录页表获取虚拟地址 va 所在页对应的页表项地址。如果对应的页表不存在，参数 alloc 可控制是否创建一个新页表，然后返回页表项地址。如果对页表很熟悉这个函数应该很简单的，我就不详细解释了，有什么疑惑可以看看前面关于页表的理论部分
static int mappages(pde_t *pgdir, void *va, uint size, uint pa, int perm)
{
char *a, *last;
pte_t *pte;
a = (char*)PGROUNDDOWN((uint)va); //虚拟地址va以4K为单位的下边界
last = (char*)PGROUNDDOWN(((uint)va) + size - 1); //偏移量，所以减1
for(;;){
if((pte = walkpgdir(pgdir, a, 1)) == 0) //获取地址a的页表项地址
return -1;
if(*pte & PTE_P) //如果该页本来就存在
panic("remap");
*pte = pa | perm | PTE_P; //填写地址a相应的页表项
if(a == last) //映射完了退出循环
break;
a += PGSIZE;
pa += PGSIZE;
}
return 0;
}
mappages 映射虚拟地址 va 到物理地址 pa，映射大小为 size，已页为单位，实现方式将相应的页表项填进 pgdir 指向的页表中去。总的来说分为两步，调用 walkpgdir 获取虚拟地址相应的页表项，然后将物理地址属性位填进这个页表项。这就是映射一页的操作，重复这个操作映射从 va 开始的 size 大小区域。
建立页表内核部分
现在有了内核映射的要求和实现方法，可以建立内核正式的页表了：
#define NELEM(x) (sizeof(x)/sizeof((x)[0])) //x有多少项
pde_t* setupkvm(void) //建立内核页表
{
pde_t *pgdir;
struct kmap *k;
if((pgdir = (pde_t*)kalloc()) == 0) //分配一页作为页目录表
return 0;
memset(pgdir, 0, PGSIZE); //页目录表置0
if (P2V(PHYSTOP) > (void*)DEVSPACE) //PHYSTOP的地址不能高于DEVSPACE
panic("PHYSTOP too high");
for(k = kmap; k < &kmap[NELEM(kmap)]; k++) //映射4项，循环4次
if(mappages(pgdir, k->virt, k->phys_end - k->phys_start, (uint)k->phys_start, k->perm) < 0) {
freevm(pgdir);
return 0;
}
return pgdir;
}
setupkvm 相当于 mappages 的封装，它循环四次，将 kmap 给出的信息当作参数传给 mappages，映射相应的地址空间。
注意 kmap 最后一项的 phys_end 为0，kmap 结构体中声明的物理地址都是无符号数，所以最后一项k->phys_end - k->phys_start，如此计算也是没有问题的，对于数值问题有疑惑的请看数值问题
切换页表
建好页表就可以切换到这个正式页表了，切换页表就是将页目录地址写进 CR3，看下面对 setupkvm 封装的函数：
pde_t *kpgdir; //全局变量kpgdir表示内核页表
void kvmalloc(void)
{
kpgdir = setupkvm(); //建立页表
switchkvm(); //切换页表
}
void switchkvm(void)
{
lcr3(V2P(kpgdir)); //加载内核页表到cr3寄存器，cr3存放的是页目录物理地址
}
kpgdir 是个全局变量，为内核页表的地址，kvmalloc() 调用 setupkvm() 建立页表，返回的页表地址赋给 kpgdir，然后调用 switchkvm() 切换成内核页表，也就是将 kpgdir 的物理地址加载到 CR3 寄存器。
这里要注意在切换内核页表之前使用的临时页表映射了虚拟地址空间的 映射到物理地址
，
映射到
，在开启分页机制后仍然有些机制使用的低 4M 虚拟地址，比如说 GDTR 中的线性地址(虚拟地址)，所以这也是必须要映射低 4M 的一个原因。
在切换到正式页表前，因为虚拟地址空间的低地址和高地址都有内核的映射，我们可以说内核处于低地址，也可以说内核处于高地址，没得问题。现在，切换到正式页表，不映射低 4M 的虚拟地址空间，低地址是用户用的。所以相应的内核数据结构 GDT 必须挪到高地址去，GDTR 也必须存放高地址。
所以有了如下的 seginit：
void seginit(void) //设置内核用户的代码段和数据段
{
struct cpu *c;
c = &cpus[cpuid()]; //获取当前CPU
//建立段描述符，内核态用户态的代码段和数据段
c->gdt[SEG_KCODE] = SEG(STA_X|STA_R, 0, 0xffffffff, 0);
c->gdt[SEG_KDATA] = SEG(STA_W, 0, 0xffffffff, 0);
c->gdt[SEG_UCODE] = SEG(STA_X|STA_R, 0, 0xffffffff, DPL_USER);
c->gdt[SEG_UDATA] = SEG(STA_W, 0, 0xffffffff, DPL_USER);
lgdt(c->gdt, sizeof(c->gdt)); //加载到GDTR
}
每个 CPU 有自己的结构，cpus 这个全局结构体数组本身高地址，这是链接的时候就顶下的，GDT 放在 CPU 结构体中，那么也就相当于位于高地址上。
设置好段描述符，建立好 GDT 之后，便将 GDT 的新地址和界限写进 GDTR 寄存器中去。这里可以看出 GDT 里面有 4 个段，内核代码段，内核数据段，用户代码段，用户数据段。段基址都是 0，段界限拉满，“所有” 段共用这几个选择子，这就是平坦模式。
遗留问题
上述讲述了内核页表的过程，有了这全局的认识之后，来解决前面遗留的一些问题：
- 为什么要分两次初始化内存：kinit1 和 kinit2
- 为什么 kinit2 必须在 startothers 之后
解决这两个问题，我们要来看看 xv6 的设计思路，当然只是看和内存相关比较紧密的部分：
最开始内核加载到物理地址 0x10 0000 处，xv6 内核很小，整个内核只有 200 多 K。内核一开始就先运行 entry.S 的代码，开启分页机制，分页当然得有页表，为简单方便将页面大小扩展到了 4M，制作了一个启动时用的临时页表，映射了低 4M 的内存。entry.S 代码运行完之后跳到 main() 中去。
int main(void)
{
kinit1(end, P2V(4*1024*1024)); // phys page allocator
kvmalloc(); // kernel page table
/*********/
seginit(); // segment descriptors
/*********/
startothers(); // start other processors
kinit2(P2V(4*1024*1024), P2V(PHYSTOP)); // must come after startothers()
/*********/
}
首先就是初始化内核结束点到 4M 之间的内存，kinit1 使用的地址是虚拟地址，此时的页表只映射了低 4M，所以传的参数为 end 到 P2V(4*1024*1024)。
初始化了 end 到 4M 之间的内存区域之后就可以构建正式的内核页表映射更多的地址空间，所以紧接着调用了 kvmalloc 建立内核部分的页表。
原本内核在低地址，由于分页机制的开启，内核跑到高地址上面去了，需要改变一些寄存器中记录的值，比如记录 GDT 地址和界限的 GDTR 寄存器，所以有了 seginit 重新初始化 GDT，然后将 GDT 的虚拟地址和界限写到 GDTR 中去。
现在已经建立了正式的内核页表，映射了整个内核部分，有更多的虚拟地址空间可用，所以可以初始化更多的内存了，因此有了 kinit2，初始化的区域是 4M 到 PHYSTOP，这个宏定义可以在一定范围内改变，从这个宏定义可以看出，xv6 实际并没有用到 32 位全部的 4G 空间。
那为什么 kinit2 必须在 startothers 后面呢？原因就在于其他 CPU 启动的时候也是用的那张临时页表，只映射了物理地址的低 4M， kinit2 的初始化内存是用头插法依次链接在头部的，如果先执行 kinit2 的话，那么在执行 startothers 时候给 APs 分配内存的时候就会先分配高处的内存，而这些内存的地址临时页表是没有映射的，就会引发错误，所以 kinit2 必须在 startothers 之后。
至于其他 APs 的启动，大都重复 BSP 的过程，只不过 APs 的启动代码放在了 0x7000 处，其他的基本一样就不再赘述了。
到此内存管理的内核部分结束，其他部分在前面的启动理论处有讲页表，用户部分的内存管理待到进程再详述。
好了本节就这样吧，有什么问题还请批评指正，也欢迎大家来同我讨论交流学习进步。
*************
查看3道真题和解析
中兴通讯工作强度 87人发布
投递中兴通讯等公司10个岗位