页表读书笔记
pagetable_t may be either the kernel page table, or one of the per-process page tables.
walk: which finds the PTE for a virtual address, and mappages, which install PTEs for new mappings.
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)];
}
// Create PTEs for virtual addresses starting at va that refer to
// physical addresses starting at pa. va and size might not
// be page-aligned. Returns 0 on success, -1 if walk() couldn't
// allocate a needed page-table page.
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;
}
copyout and copyin copy data to and from user virtual addresses provided as system call arguments; they are in the vm.c because they need to explicitly translate those addresses in order to find the corresponding physical memory.
// Copy from kernel to user.
// Copy len bytes from src to virtual address dstva in a given page table.
// Return 0 on success, -1 on error.
int
copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)
{
uint64 n, va0, pa0;
while(len > 0){
va0 = PGROUNDDOWN(dstva);
pa0 = walkaddr(pagetable, va0);
if(pa0 == 0)
return -1;
n = PGSIZE - (dstva - va0);
if(n > len)
n = len;
memmove((void *)(pa0 + (dstva - va0)), src, n);
len -= n;
src += n;
dstva = va0 + PGSIZE;
}
return 0;
}
// Copy from user to kernel.
// Copy len bytes to dst from virtual address srcva in a given page table.
// Return 0 on success, -1 on error.
int
copyin(pagetable_t pagetable, char *dst, uint64 srcva, uint64 len)
{
uint64 n, va0, pa0;
while(len > 0){
va0 = PGROUNDDOWN(srcva);
pa0 = walkaddr(pagetable, va0);
if(pa0 == 0)
return -1;
n = PGSIZE - (srcva - va0);
if(n > len)
n = len;
memmove(dst, (void *)(pa0 + (srcva - va0)), n);
len -= n;
dst += n;
srcva = va0 + PGSIZE;
}
return 0;
}
In the boot sequence, main calls kvminit to create the kernel’s page table using kvmmake. This call occurs before xv6 has enabled paging on the RISC-V, so addresses refer directly to physical memory.
// Initialize the one kernel_pagetable
void
kvminit(void)
{
kernel_pagetable = kvmmake();
}
// Make a direct-map page table for the kernel.
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;
}
kvmmake first allocates a page of physical memory to hold the root page-table page. Then it calls kvmmap to install the translations that kernel needs. The translations include the kernel’s instructions and data, physical memory up to PHYSTOP, and memory ranges which are actually devices. Proc_mapstacks allocates a kernel stack for each process. It calls kvmmap to map each stack at the virtual address generated by KSTACK, which leaves root for the invalid stack-guard pages.
// Allocate a page for each process's kernel stack.
// Map it high in memory, followed by an invalid
// guard page.
void
proc_mapstacks(pagetable_t kpgtbl) {
struct proc *p;
for(p = proc; p < &proc[NPROC]; p++) {
char *pa = kalloc();
if(pa == 0)
panic("kalloc");
uint64 va = KSTACK((int) (p - proc));
kvmmap(kpgtbl, va, (uint64)pa, PGSIZE, PTE_R | PTE_W);
}
}
kvmmap calls mappages, which installs mappings into a page table for a range of virtual address in the range, at page intervals For each virtual address to be mapped, mappages calls walk to find the address of the PTE for that address. It then initializes the PTE to hold the relevant physical page number.
// add a mapping to the kernel page table.
// only used when booting.
// does not flush TLB or enable paging.
void
kvmmap(pagetable_t kpgtbl, uint64 va, uint64 pa, uint64 sz, int perm)
{
if(mappages(kpgtbl, va, sz, pa, perm) != 0)
panic("kvmmap");
}
walk mimics the RISC-V paging hardware as it looks up the PTE for a virtual address. walk descends the 3-level page table 9 bits at a time. It uses each level’s 9 bits of virtual address to find the PTE of either the next-level page table of the final page. If the PTE isn’t valid, then the required page hasn’t been allocated; if the alloc argument is set. walk allocates a new-page table and puts its physical address in the PTE. It returns the address of the PTE in the lowest layer in the tree.
The above code depends on physical memory being direct-mapped into the kernel. For example, as walk descends levels of the page table, it pulls the address of the next-level-down page table from a PTE, and then uses that address as a virtual address to fetch the PTE at he next level down.
main calls kvminithart to install the kernel page table. It writes the physical address of the root page-table page into the register satp. After this the CPU will translate addresses using the kernel page table. Since the kernel uses an identity mapping, the now virtual address of the next instruction will map to the right physical memory address.
Each RISC-V caches page table entries in a Translation Look-aside Buffer(TLB), and when xv6 changes a page table, it must tell the CPU to invalidate corresponding cached TLB entries. If it didn’t then at some point lager the TLB might use an old cached mapping, pointing to a physical page that in the meantime has been allocated to another process, and as a result, a process might be able to scribble on some other process’s memory. The RISC-V has an instruction sfence.vma that flushes the current CPU’s TLB. Xv6 executes sfence.vma in kvminithart after reloading the satp register, and in the trampoline code that switches to a user page table before returning to user space.
Physical memory allocation
The kernel must allocate and free physical memory at run-time for page tables, user memory, kernel stacks, and pipe buffers. xv6 uses the physical memory between the end of the kernel and PHYSTOP for run-time allocation. It allocates and frees whole 4096-byte pages at a time. It keeps track of which pages are free by threading a linked list through the pages themselves. Allocation consists of removing a page from the linked list; freeing consists of adding the freed page to the list.
Code: Physical memory allocator
The allocator resides kalloc.c. The allocator’s data structure is a free list of physical memory pages that are available for allocation. Each free page’s list element is a struct run. Where does the allocator get the memory to hold that data structure? It stores each free page’s run structure in the free page itself,
原文这里引用的是本机 Typora 截图，图片文件没有随仓库保存。
Figure 3.4 shows the layout of the user memory of an executing process in xv6 in more detail. The stack is a single page, and is shown with the initial contents as created by exec. Strings containing the command-line arguments , as well as an array of pointers to them, are at the very top of the stack. Just under that are values that allow a program to start at main as if the function main(argc, argv) has just been called.
To detect a user stack overflowing the allocated memory.
Code: sbrk
sbrk is the system call for a process to shrink or grow its memory. The system call is implemented by the function growproc. growproc calls uvmalloc or uvmdealloc, depending on whether n is positive or negative. uvmalloc allocates physical memory with kalloc, and adds PTEs to the user page table with mappages. vumdealloc calls uvmunmap, which uses walk to find PTEs and kfree to free the physical memory they refer to.
Now exec allocates and initializes the user stack. It allocates just one stack page. Exec copies the argument strings to the top of the stack one at a time, recording the pointers to them in ustack. It places a null pointer at the end of that will be the argv list passed to main. The first three entries in ustack are the fake return program counter, argc, and argv pointer.
For example if (ph.vaddr + ph.memsz < ph.vaddr) checks for whether the sum overflows to 0x1000, which will look like a valid value. In an older version of xv6 in which the user address space also contained the kernel, the user could choose an address that correspond to kernel memory and would thus copy data from the ELF binary into the kernel. In the RISC-V version xv6 this cannot happen, because the kernel has its own separate page table;loadseg loads into the process’s page table, not in the kernel’s page table.
Real world
Real hardware places RAM and devices at unpredictable physical addresses, so that there might be no RAM at 0x80000000, where xv6 expect to be able to store the kernel.