xv6 的内存管理

该文章作为本人学习 MIT 6.S081 课程与 xv6 book 的学习笔记，如有错误或疑问，欢迎联系我。

分页硬件

xv6 使用 RISC-V 指令集，其分页硬件使用的是三级页表形式，其中虚拟地址的低 27+12=39 位地址用于分页过程，L2、L1、L0 每 9 位作为一级页表的索引，例如 L2 会在第一级页表（一共 2^9=512 个 PTE 项）中索引到某一项，得到对应 44 位 PPN，然后在 PPN 后补齐 12 位 0，得到第二级页表在物理内存中的地址，然后 L1 在第二级页表中索引，如此重复，一直到第三级页表使用 L0 索引得到 PPN 此时与虚拟地址中的 Offset 拼接得到真正的物理地址。

在 xv6 中虚拟地址只使用 64 位中的低 39 位，物理地址只使用 64 位中的低 56 位。在每一个 PTE（页表项）中也只使用 64 位中的低 54 位，其中 Flags 中包含了该 PTE 项是否有效等信息。

需要注意的是，在 xv6 中，使用 satp 寄存器保存第一级页表的起始地址，因此当切换进程或者在内核与用户之间跳转的时候需要切换 satp 寄存器的值进行切换。

内核内存空间

在 xv6 中，内核地址空间如下所示。可以看到，对于内核地址空间，从 0x0 到 KERNBASE（0x80000000）之间是一些 IO 设备，而且是直接映射到真实的物理地址。从 KERNBASE 到 PHYSTOP（0x86400000，但是在 xv6 2022 版的源码中貌似等于 0x88000000）是内核的代码和数据，也是直接映射到物理地址，然后就是 PHYSTOP 到 MAXVA，从上往下看，首先是 Trampoline（跳板）代码页面，然后是一个 Guard page（防止栈溢出的页面），然后就是 Kstack（分配给每一个用户进程的内核栈），如此重复，需要注意的是，在 PHYSTOP 上的内容不再直接映射，而是映射到物理内存的 RAM 中。

用户内存空间

在 xv6 中，用户地址空间如下所示。用户地址空间较为简单，从下往上看，就是代码、数据、堆、栈以及用于防止栈溢出的保证页，需要注意的是从 MAXVA 向下第一个页面跟内核一样也是 trampoline（跳板），下一个页面叫做 trapframe 页面，这两个页面主要用于系统调用跳转以及保存现场，具体请参见 xv6系统调用与第一个进程。

代码

main

首先看到我们 kernel 的 main 函数（在 QEMU 的准备工作做好之后就会跳转到这里）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// start() jumps here in supervisor mode on all CPUs.

void main() {
    if (cpuid() == 0) {
        .....
        kinit();             // physical page allocator
        kvminit();           // create kernel page table
        kvminithart();       // turn on paging
        procinit();          // process table
        trapinit();          // trap vectors
        trapinithart();      // install kernel trap vector
        ...
    } else {
        ...
    }

    scheduler();
}

kinit

首先调用 kinit 函数，这里的过程比较复杂，比较重要的是调用了 freerange 函数，将 end 到 PHYSTOP 的所有物理内存清空，其中 end 这个地址是有 kernel.ld 提供的（具体就是内核代码和数据放完之后，free memory 最低地址）。而且 kfree 的过程其实是一个链表头插的过程，把现在所有的 free memory （内核内存地址空间示意图中的 free memory）组织成一个链表，从最高地址作为头，一直到最低地址。

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
void kinit() {
    initlock(&kmem.lock, "kmem");
    initlock(&ref.lock, "pgref");
    freerange(end, (void *)PHYSTOP);
}

void freerange(void *pa_start, void *pa_end) {
    char *p;
    p = (char *)PGROUNDUP((uint64)pa_start);
    for (; p + PGSIZE <= (char *)pa_end; p += PGSIZE) {
        kfree(p);
    }
}

// Free the page of physical memory pointed at by pa,
// which normally should have been returned by a
// call to kalloc().  (The exception is when
// initializing the allocator; see kinit above.)
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.
    // pa will be memset multiple times if race-condition occurred.
	memset(pa, 1, PGSIZE);
    r = (struct run *)pa;
	acquire(&kmem.lock);
	r->next = kmem.freelist;
	kmem.freelist = r;
	release(&kmem.lock);

}

kvminit

然后就是 kvminit 函数，创建内核的页表，调用 kvmake 函数，这个函数首先调用 kalloc 函数，kalloc 函数其实就是拿到刚刚 freerange 函数组织的链表中的头部，表示这个头部已经被分配了，不再是 free memory 了。然后使用 kvmmap 函数将内核地址空间中的那些 IO 设备等等创建一个直接映射的 PTE，映射了 trampoline 页面，最后调用 proc_mapstacks，为每一个用户进程分配一个内核栈。

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
55
56
57
58
59
60
61
62
63
64
65
66
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);

    // allocate and map a kernel stack for each process.
    proc_mapstacks(kpgtbl);

    return kpgtbl;
}

// Allocate one 4096-byte page of physical memory.
// Returns a pointer that the kernel can use.
// Returns 0 if the memory cannot be allocated.
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);
    }

    return (void *)r;
}

// 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、mappages、walk

具体解析一下 kvmmap 函数，其主要用于创建一个 PTE，它调用 mappages 函数，它拿到 va 在页表中的那个 PTE 的位置，然后把 pa 和一些 perm（也就是分页硬件中的 flag 位）写到这个 PTE 中。具体怎么找到 PTE 靠的是 walk 函数，这个函数模拟出三级页表的过程，首先拿前 9 位拿到当前第一级页表的 PTE，得到第二级页表的位置（事实上内核页表此时只有第一级页表），发现 PTE_V（有效位）无效，因此再分配第二级页表，以此类推得到第三级页表 PTE 的位置。

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
55
56
57
58
59
60
61
// 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");
}

// 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)
        // continue;
        // panic("mappages: remap");
        *pte = PA2PTE(pa) | perm | PTE_V;
        if (a == last) break;
        a += PGSIZE;
        pa += PGSIZE;
    }
    return 0;
}

// Return the address of the PTE in page table pagetable
// that corresponds to virtual address va.  If alloc!=0,
// create any required page-table pages.
//
// The risc-v Sv39 scheme has three levels of page-table
// pages. A page-table page contains 512 64-bit PTEs.
// A 64-bit virtual address is split into five fields:
//   39..63 -- must be zero.
//   30..38 -- 9 bits of level-2 index.
//   21..29 -- 9 bits of level-1 index.
//   12..20 -- 9 bits of level-0 index.
//    0..11 -- 12 bits of byte offset within the page.
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)];
}

最后在 main 函数中再调用 kvminithart 函数启用分页，事实上它就只是写入了内核第一级页表的位置到 satp 寄存器。

1
2
3
4
5
6
7
8
9
10
11
// Switch h/w page table register to the kernel's page table,
// and enable paging.
void kvminithart() {
    // wait for any previous writes to the page table memory to finish.
    sfence_vma();

    w_satp(MAKE_SATP(kernel_pagetable));

    // flush stale entries from the TLB.
    sfence_vma();
}

至此对于内核的内存管理就已经结束了，我们已经创建了一个三级页表，并且把一些 IO 设备、trampoline 页面、内核代码数据映射到了相应的 PTE，并且现在的 satp 寄存器就存储着内核第一级页表的位置。对于用户态的内存管理，到下一篇文章再讨论。