MIT 6s081 blog 1.xv6内存管理

发布时间:2024年01月15日

xv6内存管理部分

xv6内存布局

内核地址空间

如xv6指导书中图3.3:从0x80000000开始的地址为内核地址空间,CLINT、PLIC、uart0、virtio disk等为I/O设备(内存映射I/O),可以看到xv6虚拟地址到物理地址的映射,大部分是相等的关系。
在这里插入图片描述

在kernel/memlayout.h中对内存分布进行了宏定义

// kernel/memlayout.h
// the kernel expects there to be RAM
// for use by the kernel and user pages
// from physical address 0x80000000 to PHYSTOP.
#define KERNBASE 0x80000000L
#define PHYSTOP (KERNBASE + 128*1024*1024)

// map the trampoline page to the highest address,
// in both user and kernel space.
#define TRAMPOLINE (MAXVA - PGSIZE)

// map kernel stacks beneath the trampoline,
// each surrounded by invalid guard pages.
#define KSTACK(p) (TRAMPOLINE - ((p)+1)* 2*PGSIZE)

进程地址空间

在这里插入图片描述

在kernel/memlayout.h中对内存分布进行了宏定义

// User memory layout.
// Address zero first:
//   text
//   original data and bss
//   fixed-size stack
//   expandable heap
//   ...
//   TRAPFRAME (p->trapframe, used by the trampoline)
//   TRAMPOLINE (the same page as in the kernel)
#define TRAPFRAME (TRAMPOLINE - PGSIZE)

物理内存分配

xv6对于物理内存的管理使用的是空闲链表,以页为单位进行管理,每次分配/释放都是一页。代码如下:

空闲链表

// kernel/kalloc.c

struct run {
  struct run *next;
};

struct {
  struct spinlock lock;
  struct run *freelist;
} kmem;

使用两个结构体维护一个单向链表,kmem作为全局变量,freelist为空闲链表的头节点,每个链表节点为struct run,包含指向下一个链表节点的结构体指针,并为全局变量kmem维护一把锁用于race condition(竞态条件)

申请物理内存

// 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); // fill with junk
  return (void*)r;
}

首先获取kmem的锁,r = freelist,将freelist移到freelist->next,此时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);
}

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);
}

将传入的要释放的物理地址pa强转为链表节点,将该节点的next节点指向空闲链表头结点,然后将该节点作为空闲链表头节点(也就是链表的头插法)

freerange为封装的kfree函数,用于释放pa_start到pa_end的物理空间

内核页表

三级页表遍历过程

xv6使用三级页表来节约因为存储页表而耗费的大量内存页

在这里插入图片描述

物理内存地址是56bit,其中44bit是物理page号(PPN,Physical Page Number),剩下12bit是offset完全继承自虚拟内存地址。

每个页表项:63-54为预留位,53-10为物理页号,9-0为标志位

xv6使用的是三级页表,首先从satp寄存器中获取最高级页目录的地址,从L2(38:30位)得到索引,根据索引在最高级页目录中找到物理页号(也就是中间级页目录的地址),根据L1(29:21位)得到索引,根据索引在中间级页目录中找到物理页号(也就是最低级页目录的地址),根据L0(20:12位)得到索引,根据索引在最低级页目录中找到物理页号,将最低级的物理页号和offset(11:0位)合并得到最终的56位物理地址。(三级页表的查询方式和每个页表项的结构如上图所示)。

初始化

在kernel/vm.c中声明了内核页表,每个pagetable_t(通过kalloc分配一页空间)包含512个页表项(4096 * 8 / 64 = 512)

typedef uint64 pte_t;
typedef uint64 *pagetable_t; // 512 PTEs
pagetable_t kernel_pagetable; // 内核页表

在main.c中调用kvminit函数创建内核页表,kvminit调用了kvmmake函数,在kvmmake函数中为一些启动必备的区域添加映射到内核页表中,如UART0、VIRTIO0、PLIC、etext、TRAMPOLINE等,

// kernel/vm.c
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);
...

以及为每个进程的内核栈建立映射(在每一个进程的生命周期中,必然会通过到系统调用陷入内核。在执行系统调用陷入内核之后,这些内核代码所使用的栈并不是原先进程用户空间中的栈,而是一个单独内核空间的栈,这个称作进程内核栈。)

// 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,将添加va->pa、长度为sz、标志位为perm的映射(PTE)

kvmmap->mappages->walk

// kvmmap调用了mappages
void kvmmap(pagetable_t kpgtbl, uint64 va, uint64 pa, uint64 sz, int perm)
{
  if(mappages(kpgtbl, va, sz, pa, perm) != 0)
    panic("kvmmap");
}

// 向pagetable页表中添加长度为sz,va->pa,标志为perm的映射
int mappages(pagetable_t pagetable, uint64 va, uint64 size, uint64 pa, int perm)
{
  uint64 a, last;
  pte_t *pte;

  a = PGROUNDDOWN(va);
  last = PGROUNDDOWN(va + size - 1);
  for(;;){
    if((pte = walk(pagetable, a, 1)) == 0) //  mappages使用walk找到最低一级的pte,alloc = 1
      return -1;
    if(*pte & PTE_V)
      panic("remap");
    *pte = PA2PTE(pa) | perm | PTE_V; // 修改pte
    if(a == last)
      break;
    a += PGSIZE;
    pa += PGSIZE;
  }
  return 0;
}

// 根据va返回最低一级的页表项,alloc选项用于当pte无效时,是否创建pte,本质上是软件模拟硬件MMU的过程
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)];
}

设置/切换页表

  • 内核初始化时/进入内核态时切换为内核页表
  • 进入用户态/进程调度后,切换为对应进程的页表

kvminithart函数,这个函数首先设置了SATP寄存器,kernel_pagetable变量来自于kvminit第一行。所以这里实际上是内核告诉MMU来使用刚刚设置好的page table(在此之前,内核在kernel/start.c中使用w_satp(0);来关闭分页机制)。

// Switch h/w page table register to the kernel's page table,
// and enable paging.
void
kvminithart()
{
  w_satp(MAKE_SATP(kernel_pagetable)); // 设置satp寄存器,将对应位进行设置
  sfence_vma(); // 刷新快表
}

进程页表

在进程的结构体中有一个字段为pagetable_t pagetable(User page table),为进程的页表,在用户态时,使用的页表是独立的,符合了操作系统的隔离性,不同进程的虚拟地址所指向的物理地址空间是不同的,进程A无法访问到进程B的内存空间。

// Per-process state
struct proc {
  struct spinlock lock;

  // p->lock must be held when using these:
  enum procstate state;        // Process state
  struct proc *parent;         // Parent process
  void *chan;                  // If non-zero, sleeping on chan
  int killed;                  // If non-zero, have been killed
  int xstate;                  // Exit status to be returned to parent's wait
  int pid;                     // Process ID

  // these are private to the process, so p->lock need not be held.
  uint64 kstack;               // Virtual address of kernel stack
  uint64 sz;                   // Size of process memory (bytes)
  pagetable_t pagetable;       // User page table
  struct trapframe *trapframe; // data page for trampoline.S
  struct context context;      // swtch() here to run process
  struct file *ofile[NOFILE];  // Open files
  struct inode *cwd;           // Current directory
  char name[16];               // Process name (debugging)
};

riscv.h一些声明

这些宏定义在页表操作中被使用到,如PA2PTE将物理地址转换为页表项,PGROUNDUP表示对sz / PGSIZE的结果进行上取整。

#define PGSIZE 4096 // bytes per page
#define PGSHIFT 12  // bits of offset within a page

#define PGROUNDUP(sz)  (((sz)+PGSIZE-1) & ~(PGSIZE-1))
#define PGROUNDDOWN(a) (((a)) & ~(PGSIZE-1))

#define PTE_V (1L << 0) // valid
#define PTE_R (1L << 1)
#define PTE_W (1L << 2)
#define PTE_X (1L << 3)
#define PTE_U (1L << 4) // 1 -> user can access

// shift a physical address to the right place for a PTE.
#define PA2PTE(pa) ((((uint64)pa) >> 12) << 10)

#define PTE2PA(pte) (((pte) >> 10) << 12)

#define PTE_FLAGS(pte) ((pte) & 0x3FF)

// extract the three 9-bit page table indices from a virtual address.
#define PXMASK          0x1FF // 9 bits
#define PXSHIFT(level)  (PGSHIFT+(9*(level)))
#define PX(level, va) ((((uint64) (va)) >> PXSHIFT(level)) & PXMASK)

// one beyond the highest possible virtual address.
// MAXVA is actually one bit less than the max allowed by
// Sv39, to avoid having to sign-extend virtual addresses
// that have the high bit set.
#define MAXVA (1L << (9 + 9 + 9 + 12 - 1))

typedef uint64 pte_t;
typedef uint64 *pagetable_t; // 512 PTEs

vm.c主要函数

ptb:pagetable; va : 虚拟地址; pa:物理地址; pte:页表项

与内核页表相关:

  • kvminit:创建内核页表的一些固定映射

  • kvminithart:使用内核页表

  • kvmmap:向内核页表中添加va->pa,flag为perm|PTE_V的映射

  • kvmpa:根据内核页表将va转换成pa

与进程页表相关:

  • uvmunmap:在ptb中移除va开始的npages个页的叶子级别映射(最低一级页表的映射),并根据do_free参数选择是否释放对应的物理空间(与freewalk配合使用来释放页表)
  • uvmcreate:创建一个空的页表
  • uvminit:用于加载第一个进程的initcode到va = 0处
  • uvmalloc:在进程页表中创建新的PTE和分配对应的物理内存,用于将进程空间从oldsz增大到newsz
  • uvmdealloc:在进程页表中修改进程空间,从oldsz到newsz(用于回收用户页表中的页面)
  • uvmfree:把进程页表空间释放,把最低一级PTE的条目清空,并删除对应的物理页(uvmunmap)。并将最高级和中间级的PTE条目也清空,并清空物理页(freewalk)
  • uvmcopy:将old ptb的sz个页空间拷贝到new ptb(用于fork系统调用,将父进程的页表映射复制到子进程的页表映射,虚拟地址对应的物理地址不同,但内容相同)
  • uvmclear:将用户页表的最低一级PTE条目的PTE_U标志去除,用于exec函数设置守护页

kvm开头和uvm开头的函数都在内核态中运行,使用的都是内核页表,但操作的对象不同

工具方法:

  • walk:根据ptb和va,返回对应的最低一级PTE

  • walkaddr:根据ptb和va,找到对应的pte,并使用PTE2PA,返回pa

  • freewalk:递归释放指定页表的所有项,叶子节点在调用之前必须已经被清空,否则会陷入freewalk leaf

  • mappages:根据给定的ptb, va, pa, size, perm在三级页表中创建映射

  • copyout:将内核空间的n个字节拷贝至用户空间

  • copyin:将用户空间的n个字节拷贝至内核空间

  • copyinstr:将用户空间的max个字符串(必须以‘\0’结尾)拷贝至内核空间

copyin

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;
}

从给定进程页表的虚拟地址srcva中拷贝len字节到内核地址dst中,由于此时运行在内核态中,因此char* dst会通过硬件MMU自动翻译成对应的物理地址(使用内核页表),而scrva对应的物理地址要使用walkaddr(软件模拟MMU的方法)从进程页表中找到对应的物理地址进行拷贝

copyout

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;
}

与copyin类似,只不过拷贝方向相反。

文章来源:https://blog.csdn.net/weixin_45988024/article/details/135602913
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。