MIT_6.S081_xv6.Information 3:Memory&Page Table

MIT_6.S081_xv6.Information 3:Memory&Page Table

于2022年3月18日2022年3月18日由Sukuna发布

内存管理

分页的硬件

RISC-V的指令(包括用户态下的或者内核态下的)里面的地址操作数其实代表了虚拟地址.但是对应地,RAM或者叫做物理内存,自然也有物理地址,物理地址真实唯一地标记实际内存空间,可能RAM的第10006个区块地址就是0x10006.所以说就有页表这个东西,把指令提供的逻辑地址转化到实际内存的物理地址.

xv6会运行RISC-V支持的Sv39架构,页表是一个连接虚拟地址和实际的物理地址的一个桥梁,CPU给页表一个虚拟地址,页表会返回一个物理地址.

其中虚拟地址分成两部分,低12位就是offset,代表一个页有​大,中间的27位是index值,负责寻找到对应的表项位置,比如说如果index=5就代表要找到第五个表项.后面的25位不需要.页表的每一项对应44位的PPN和10位的flags.其中flags标记这一项的一些控制信息,PPN则和offset一块组成物理地址.虚拟地址是​的空间,而物理地址是​.

总的来说是分三步走.

• 虚拟地址分成index和Offset两部分.
• 找到页表中的第index项.获取其中的PPN和flags
• PPN和虚拟地址的Offset组成物理地址.

页表给OS给操作系统提供了va和pa互换的途径,其中内存被划分成4KB的块,我们称之为页.

实际的操作可能更加复杂,SV39维护的是一个多级页表.虚拟地址转化为物理地址需要分三步走.

首先我们发现页表是三级结构,第一层页表的首地址保存在satp寄存器中,有512个表项,其中表项存储着下一级页表(第二层)的首地址.第二级页表也是由512个表项组成,其中每一个表项存着下一级页表(第三层)的首地址.第三级页表里面存储的就是对应的物理地址的PPN.

所以说va分成L2,L1,L0和Offset分成四部分.

• 首先在第一级页表中找到第L2个表项,这样就找到第二级页表的首地址.
• 然后在第二级页表中找到第L1个表项,这样就找到第三级页表的首地址.
• 最后在第三级页表中找到第L0个表项,这样就能获取到PPN,然后拿PPN和offset组合在一起就可以了.
• 如果在任何一次寻找的时候Flags显示这个页表项不可用,那么就引发缺页中断.

三级页表非常好用而别比较高效,因为一开始的时候我们不需要要那么大的空间存放页表,我们可以边运行程序遍扩充页表的大小.

但是CPU这样去访问页表需要3次访存指令.这样子访问就很慢,所以说CPU设计了一个类似于cache的东西来保存页表信息,这个表叫做TLB.CPU首先会在TLB中查找页表元素.如果TLB miss了才会调用访存操作来获取页表元素.

每一个页表都都存储了flag位,其中PTE_V存着这个页表项究竟是不是可用的.PTE_W表示指令是否可以往这个页是否可写,PTE_X表示这个页是否可执行,PTE_U表示在用户态下是否可以访问这一页.

在硬件层面上我们必须指定第一级页表的首地址,这个页表首地址存放在satp寄存器中,由于这个是CPU,所以说不同CPU的satp寄存器的值都是不一样的.我们还知道每个进程的第一级页表的首地址也是不一样的(每个进程都有不同的页表记录地址).这为每个CPU运行不同的进程提供了一句.

我们的用户程序在虚拟内存上进行读写,提供的地址也是虚拟地址,虚拟内存其实就是由许多的实际的DRAM(存储器件)组成的虚拟化而已.

内核地址空间

xv6对每个进程都维护了一份页表(每个进程都有一个页表),来表示不同进程的虚拟地址空间.当然xv6也会给内核态地址空间维护一个页表,也就是说xv6的地址空间=若干个用户态进程的地址空间+内核地址空间.

QEMU会模拟一个RAM(物理存储器),这个存储器的地址空间是0x80000000~0x86400000.在xv6系统中称为PHYSTOP.QEMU还把各种I/O设备,比如说磁盘等的地址映射到0x80000000的地址之下,xv6操作系统可以通过直接访问这些物理地址来操控这些设备(比如说访问0x10001000来访问VIRTIO disk),而不是通过访问RAM来间接地访问设备.

内核通过直接访问映射来访问RAM和上文提到的设备,也就是说程序提到的虚拟地址=物理地址.(也就是说,xv6访问内存和设备是bare linking的,物理地址就是虚拟地址,同样地,在页表中,对应的虚拟地址=物理地址).

当然内核用户状态下也有不是直接链接的比如说trampoline页(看syscall&trap一章)和内核态栈(若干个内核态栈之间有一个Guard页)不是直接连的.

如何创建一个地址空间?

所有的xv6关于地址的处理全部放在vm.c这个文件中.

最关键的就是数据结构就是pagetable_t这个数据结构,这个数据结构本质上就是一个uint64*类型的一个指针,这个代表了第一级页表的首地址.可以是用户进程页表的首地址,也可以是内核页表的首地址.

最重要的函数有walk,这个函数负责给定一个va,然后找到对应的PTE.

pte_t *
walk(pagetable_t pagetable, uint64 va, int alloc)
{
 if(va >= MAXVA)
   panic("walk");
​
 for(int level = 2; level > 0; level--) {
   pte_t *pte = &pagetable[PX(level, va)];
   if(*pte & PTE_V) {
     pagetable = (pagetable_t)PTE2PA(*pte);
  } else {
     if(!alloc || (pagetable = (pde_t*)kalloc()) == 0)
       return 0;
     memset(pagetable, 0, PGSIZE);
     *pte = PA2PTE(pagetable) | PTE_V;
  }
}
 return &pagetable[PX(0, va)];
}

int
mappages(pagetable_t pagetable, uint64 va, uint64 size, uint64 pa, int perm)
{
 uint64 a, last;
 pte_t *pte;
​
 if(size == 0)
   panic("mappages: size");
 
 a = PGROUNDDOWN(va);
 last = PGROUNDDOWN(va + size - 1);
 for(;;){
   if((pte = walk(pagetable, a, 1)) == 0)
     return -1;
   if(*pte & PTE_V)
     panic("mappages: remap");
   *pte = PA2PTE(pa) | perm | PTE_V;
   if(a == last)
     break;
   a += PGSIZE;
   pa += PGSIZE;
}
 return 0;
}

void
kvmmap(pagetable_t kpgtbl, uint64 va, uint64 pa, uint64 sz, int perm)
{
 if(mappages(kpgtbl, va, sz, pa, perm) != 0)
   panic("kvmmap");
}
​
pagetable_t
kvmmake(void)
{
 pagetable_t kpgtbl;
​
 kpgtbl = (pagetable_t) kalloc();
 memset(kpgtbl, 0, PGSIZE);
​
 // uart registers
 kvmmap(kpgtbl, UART0, UART0, PGSIZE, PTE_R | PTE_W);
​
 // virtio mmio disk interface
 kvmmap(kpgtbl, VIRTIO0, VIRTIO0, PGSIZE, PTE_R | PTE_W);
​
 // PLIC
 kvmmap(kpgtbl, PLIC, PLIC, 0x400000, PTE_R | PTE_W);
​
 // map kernel text executable and read-only.
 kvmmap(kpgtbl, KERNBASE, KERNBASE, (uint64)etext-KERNBASE, PTE_R | PTE_X);
​
 // map kernel data and the physical RAM we'll make use of.
 kvmmap(kpgtbl, (uint64)etext, (uint64)etext, PHYSTOP-(uint64)etext, PTE_R | PTE_W);
​
 // map the trampoline for trap entry/exit to
 // the highest virtual address in the kernel.
 kvmmap(kpgtbl, TRAMPOLINE, (uint64)trampoline, PGSIZE, PTE_R | PTE_X);
​
 // map kernel stacks
 proc_mapstacks(kpgtbl);
 
 return kpgtbl;
}

void
kvminithart()
{
 w_satp(MAKE_SATP(kernel_pagetable));
 sfence_vma();
}

void
kinit()
{
 initlock(&kmem.lock, "kmem");
 freerange(end, (void*)PHYSTOP);
}
​
void *
kalloc(void)
{
 struct run *r;
​
 acquire(&kmem.lock);
 r = kmem.freelist;
 if(r)
   kmem.freelist = r->next;
 release(&kmem.lock);
​
 if(r)
   memset((char*)r, 5, PGSIZE); // fill with junk
 return (void*)r;
}

void
kfree(void *pa)
{
 struct run *r;
​
 if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
   panic("kfree");
​
 // Fill with junk to catch dangling refs.
 memset(pa, 1, PGSIZE);
​
 r = (struct run*)pa;
​
 acquire(&kmem.lock);
 r->next = kmem.freelist;
 kmem.freelist = r;
 release(&kmem.lock);
}

int
growproc(int n)
{
 uint sz;
 struct proc *p = myproc();
​
 sz = p->sz;
 if(n > 0){
   if((sz = uvmalloc(p->pagetable, sz, sz + n)) == 0) {
     return -1;
  }
} else if(n < 0){
   sz = uvmdealloc(p->pagetable, sz, sz + n);
}
 p->sz = sz;
 return 0;
}

sbrk是一个系统调用,这个调用帮助我们实现进程内存空间的增长和消亡.

sbrk系统调用?

同样,为了防止栈溢出,我们有一个guard page来保护.

stack页是一个页,然后里面的参数是由exec程序创建的,有各种参数以及参数的地址.还有main执行完PC的返回值.

其中trapframe这个页是映射到可用物理空间的,在kernel态是直接映射的,所以说不用担心kernel态访问不了用户态的kernel.

第一:一个用户进程只使用一张页表,不同的用户进程的物理地址是相互隔离的不会被打扰的.第二,用户看见的虚拟地址是连续的但其实物理地址不是连续的,这样加大了分配的灵活性.第三,trampoline页是所有用户通用的,也就是说每个用户的页表一定有一个MAXVA-PGSIZE->trampoline的映射.

用户地址空间是从0~MAXVA的.然后当用户程序需要更多的内存的时候,xv6就会使用kalloc来获取新的页,然后接着建立pa和va的关系(和内核是一样的).对于虚拟地址,如果用户进程暂时不需要使用,就可以把页表的PTE_V置0表示不需要使用.

用户进程地址空间.

同样,在释放的时候,也是获得这个释放的物理块地址,把它放到freelist的队首中.

在kalloc.c中我们知道,每次申请都会调用一次kalloc函数.kalloc函数每一次从freelist中取出一块来进行返回.这个freelist已经在kinit函数中初始化好了,就是从end(内核态空间的占用的最后一个地址)到PHYSTOP这个区域内.

如何申请物理块?

我们知道TLB会存储一些页表信息,CPU同样也会切换进程,切换进程的时候我们不想让下一个进程知道我们的页表信息,这个时候就会调用sfence_vma()函数来对TLB的内容进行一次部分刷新.

这个时候这个函数会把kernel_pagetable写进satp寄存器中,这个时候页表正式进入工作,之后的地址就是需要页表一级的转化,并且当前页表的第一级首地址就是kernel_pagetable.

在S态的main函数执行了kvminithart函数来初始化了内核态页表.

上面的所有函数实现的基础就是在bare linking上面的,也就是说执行的情况中虚拟地址=物理地址,我们才可以方便地访问和处理.

进行了若干次的虚拟地址和物理地址的映射,这个时候最后一步就是调用proc_mapstacks.对每一个进程都分配了一个内核栈.然后也调用了kvmmap来进行地址的映射.最后返回一个内核态页表.

在操作系统初始化的时候,就调用kvminit函数对内存空间进行初始化,kvminit调用了kvmmake函数.kvmmake又调用了若干个kvmmap函数.在调用这一段函数的时候,xv6还没有开启份页功能,所以说在这一部分执行的指令可以直接访问物理内存.kvmmake函数首先申请物理内存的一页作为内核态页表的一页.然后接着调用kvmmap函数在kernel态的页表中添加对于若干个虚拟地址的映射.

然后又copyout和copyin,这个函数可以从用户态的虚拟地址中获取信息传递给内核态.

给定va和pa,然后添加va和pa的连接,放入页表中,这个时候va和pa正式有了联系.

还有一个就是mappages.这个函数负责添加页表项,就是给页表添加一项,让一段虚拟地址和一段物理地址进行匹配.

这个函数是不是跟我们之前说的读法是一样的,三层的页表就需要我们去读三次,有哪一次发现Valid位(PTE_V不对)就返回为0,然后申请一个新页即可.image-20220317203331257