operating system

内存管理的代码从功能上分为两部分,一部分是内存系统的初始化,剩下一部分才是 xv6 操作系统正常运行时的内存管理功能。另外根据物理页帧和虚拟存储空间的不同,又分成物理页帧的分配、回收管理和虚存空间分配、回收以及映射管理。其中虚存空间又根据保护级的不同,分成内核空间和用户空间两部分。(初始化分两次解决自举问题)

下面将物理空间的页称为页帧,虚拟空间的页成为虚页。

1. 空闲物理内存

物理内存的初始化分两步

  1. 早期布局,先分配 0~4MB ,然后启动分页机制映射到整个物理空间。其中 0x100000~PHYSTOP 为扩展内存区。
  2. 启动分页后的空闲物理页帧初始化。也就是将扩展内存区中的空闲页帧串成一个链表,一开始 end~PHYSTOP 都是空闲页帧。

1.1 早期布局

main 函数一开始执行,首先进行物理页帧分配,此时调用了 kinit1 函数:内核代码存在于物理地址的 0x100000 处,而虚存空间的 0 和 0x80000000 地址开始的两段 4 MB 都影射了内核代码。此时的早期页表为 main.c 文件中的 entrypgdir 数组,其中只有两项有效。

  1. 虚拟地址低 [0,4MB] 映射到物理地址 低[0,4MB]。
  2. 虚拟地址[KERNBASE, KERNBASE+4MB] 映射到物理地址[0,4MB]。

1.2 完整的初始化

  1. 调用 kinit1end~4MB 中的空闲页帧插入 freelist ,此时还是使用 entrypgdir 页表。
  2. 调用 kinit2end~PHYSTOP 的所有空闲页帧都插入 freelist 中。

2. 内核页表

当使用 entrypgdir 作为页表建立起一些空闲内存的时候,主函数立即调用了 kvmalloc 函数为内核页表重新设置完整的页表目录 kpgdir 。大致分为下面几个步骤

  1. 申请一个页帧存储页表目录,利用 kalloc 函数。

  2. 利用 kmap 的布局构建页表目录布局。这里使用了 mappages 函数。

    static int mappages(pde_t *pgdir, void *va, uint size, uint pa, int perm)
    

    我们查看 kmap 的第三项如下, (void*)data 就是空间的起始地址,V2P(data) 是物理空间的起始地址,PHYSTOP 是物理空间的结束地址,所以 sizePHYSTOP-V2P(data) ,最后一个是权限,PTE_W 表示可写。

    { (void*)data,     V2P(data),     PHYSTOP,   PTE_W}, // kern data+memory
    
  3. 为布局好的页表目录的每一项映射一个页表,这里调用了 walkpgdir 函数。

    给你一个逻辑地址(一般是页表下边界),然后查看 pgdir 是否有相关的页表,如果 alloc 为 1,那么就给页表目录项分配相应的页表。内核页表目录全部页表项都要分配相应的页表,因为内核要映射整个物理空间,这样才可以进行内存管理。

    static pte_t * walkpgdir(pde_t *pgdir, const void *va, int alloc)
    

手动编程

xv6 添加 alloc()free() 系统调用,替代原有 sbrk() 系统调用,从而使得进程空间不必是一个连续的空间。

sbrk 分配过程

查看 sys_sbrksysproc.c)系统调用。调用了 growproc 函数。

// 调用成功返回分配内存的首地址,可以发现首地址是 proc->sz。也就是说,用户空间的内存居然是连续的
int
sys_sbrk(void) {
  int addr;
  int n;

  if(argint(0, &n) < 0)
    return -1;
  addr = proc->sz;
  if(growproc(n) < 0)
    return -1;
  return addr;
}

查看 growprocproc.c)函数,扩容调用 allocuvm 函数,缩容调用 deallocuvm 函数。

// 入参 n 可正可负,正表示逻辑地址向上扩增,负表示逻辑地址向下缩减,不会出现内存空洞。
int
growproc(int n) {
  uint sz;
  
  sz = proc->sz;    // 当前内存大小
  if(n > 0){        // n > 0 调用 allocuvm 函数扩增内存
    if((sz = allocuvm(proc->pgdir, sz, sz + n)) == 0)
      return -1;
  } else if(n < 0){ // n < 0 调用 deallocuvm 函数缩减内存
    if((sz = deallocuvm(proc->pgdir, sz, sz + n)) == 0)
      return -1;
  }
  proc->sz = sz;
  switchuvm(proc);
  return 0;
}

查看 allocuvmvm.c)函数,里面利用 kalloc 函数申请物理页帧,kfree 函数释放物理页帧,mappages 函数用于建立虚拟地址和物理页帧之间的页表影射。一旦 kalloc 分配失败,整个过程就分配失败,并利用 deallocuvm 释放之前申请的内存。

// 分配页帧并建立页表映射
int allocuvm(pde_t *pgdir, uint oldsz, uint newsz) {
  char *mem;
  uint a;

  if(newsz >= KERNBASE)  // 用户空间的逻辑地址小于 KERNBASE,也就是不超过 2G 内存
    return 0;
  if(newsz < oldsz)      // 分配操作而不是缩小内存
    return oldsz;

  a = PGROUNDUP(oldsz);             // 虚页下边界
  for(; a < newsz; a += PGSIZE){    // 逐个页帧进行分配
    mem = kalloc();                 // 申请一个空闲页帧并返回一个逻辑地址 
    if(mem == 0){
      cprintf("allocuvm out of memory\n");
      deallocuvm(pgdir, newsz, oldsz);
      return 0;
    }
    memset(mem, 0, PGSIZE);         // 对新页帧清 0,这里也能说明 mem 是程序地址
    // 接下来建立虚拟地址到物理地址的映射,权限是可写或者用户才有资格分配,负责失败
    if(mappages(pgdir, (char*)a, PGSIZE, V2P(mem), PTE_W|PTE_U) < 0){ // 映射
      cprintf("allocuvm out of memory (2)\n");
      deallocuvm(pgdir, newsz, oldsz);
      kfree(mem);
      return 0;
    }
  }
  return newsz;
}

查看 deallocuvmvm.c)函数,删除物理页帧的同时,需要更新页表。这里调用了 walkpgdir 函数。

// 释放物理内存,将大小从 oldsz 降到 newsz
int
deallocuvm(pde_t *pgdir, uint oldsz, uint newsz)
{
  pte_t *pte;
  uint a, pa;

  if(newsz >= oldsz)         
    return oldsz;

  a = PGROUNDUP(newsz);                   // 页面上边界
  for(; a  < oldsz; a += PGSIZE){         // 逐页处理
    pte = walkpgdir(pgdir, (char*)a, 0);  // 找到对应的 PTE
    if(!pte)                              // 如果未映射
      a += (NPTENTRIES - 1) * PGSIZE;     // 无需处理,跳过,一个页表记录 4MB
    else if((*pte & PTE_P) != 0){         // 如果有映射
      pa = PTE_ADDR(*pte);                // 取 PTE 高20位,PTE存储的是物理地址高20位
      if(pa == 0)
        panic("kfree");
      char *v = P2V(pa);                   // 物理地址转虚拟地址
      kfree(v);                            // 释放页帧
      *pte = 0;                            // 释放后页表项清零,主要是 PTE_P 清零
    }
  }
  return newsz;
}

物理内存分配过程

sbrk 内存分配过程中,调用了一些函数分配物理内存给(用户进程、内核栈、页表以及管道缓存),这些函数都在 kalloc.c 文件中,物理页帧为 4096 字节。

查看 kalloc 函数,注意:虽然是管理物理页帧,但是在函数中的地址都是逻辑地址。

// 分配一个 4096 字节的物理页帧
char*
kalloc(void) {
  struct run *r;   
  
  if(kmem.use_lock)     
    acquire(&kmem.lock);       
  r = kmem.freelist;           // 指向空闲页帧链表
  if(r)                        // 有空闲页帧
    kmem.freelist = r->next;   // 将页帧移出空闲链表给 r
  if(kmem.use_lock)            
    release(&kmem.lock);
  return (char*)r;             // 返回申请到的页帧的首地址
}

查看 kfree 函数

// 释放被 v 影射的物理页,也就是说 v 是逻辑地址
void
kfree(char *v) {
  struct run *r;  
  
  // v 要页面对齐,v >= end 且 v < KERNBASE+PHYSTOP
  if((uint)v % PGSIZE || v < end || V2P(v) >= PHYSTOP)
    panic("kfree");

  // 给每一个字节置 1
  // 使得访问已被释放内存的代码所读到的不是原有数据,而是垃圾数据。 
  // 这样做的目的是让这种错误的代码尽早崩溃。
  memset(v, 1, PGSIZE);

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

虚拟地址和物理页帧之间的页表影射

查看 mappagesvm.c)函数,里面调用了 walkpgdir 函数。

// 建立逻辑地址到物理地址的二级页表映射
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);                 // 按页边界对齐的起始地址
  last = (char*)PGROUNDDOWN(((uint)va) + size - 1); // 按页边界对齐的结束地址
  for(;;){                                          // 逐个页帧建立页表映射
    if((pte = walkpgdir(pgdir, a, 1)) == 0)         // 找到对应的 PTE 项
      return -1;
    if(*pte & PTE_P)                                // 已存在
      panic("remap");
    *pte = pa | perm | PTE_P;              // 物理地址 + 权限 + 占用标志
    if(a == last)
      break;
    a += PGSIZE;                         // 下一个虚页的起始地址
    pa += PGSIZE;                        // 下一个页帧的起始物理地址
  }
  return 0;
}

查看 walkpgdirvm.c)函数。

// 查找逻辑地址 va 所对应的物理地址,如果没有且 alloc = 1,分配一个页帧
static pte_t *
walkpgdir(pde_t *pgdir, const void *va, int alloc)
{
  pde_t *pde;
  pte_t *pgtab;

  pde = &pgdir[PDX(va)];  // 利用 dir 查找页表
  if(*pde & PTE_P){       // 二级页表存在
    pgtab = (pte_t*)P2V(PTE_ADDR(*pde));   // 二级页表逻辑首地址
  } else {
    if(!alloc || (pgtab = (pte_t*)kalloc()) == 0)  // alloc 为 1 则分配页帧
      return 0;
      
    // 保证所有 PTE_P 位为 0(页帧可用)
    memset(pgtab, 0, PGSIZE);
      
    // 页表目录的权限过于宽松,但是如果需要,可以通过二级页表的权限进一步限制页帧权限。 
    *pde = V2P(pgtab) | PTE_P | PTE_W | PTE_U;   // 更新页表目录
  }
  return &pgtab[PTX(va)];     // 这里返回的是 va 的物理页帧首地址
}

实现 map 系统调用查看进程的虚拟空间

  1. 添加系统调用

    // syscall.h
    #define SYS_map 22	
       
    // syscall.c
    extern int sys_map(void);
    [SYS_map]  sys_map,
       
    // defs.h
    int map(int);
       
    // usys.S
    SYSCALL(map)
           
    // user.h
    int map(int);
       
    // sysproc.c
    int sys_map(void) {
        int pid;
        if (argint(0, &pid) < 0)
            return -1;
        return map(pid);
    }
       
    // proc.c
    static void printTable(pde_t pde, int i){
        pte_t* table = (pte_t*)P2V(PTE_ADDR(pde));
        int j;
        for(j = 0; j < 1024; j++)
            if(table[j] & PTE_P)
                cprintf("dir %d table %d 对应的物理页帧:%x\n", i, j, table[j]);  
    }
       
    static void printMap(pde_t* pgdir){
        int i;
        for(i=0; i < 512; i++)
            if(pgdir[i] & PTE_P)
                printTable(pgdir[i], i);
    }
       
    int
    map(int pid) {
        struct proc *p;
        // Enable interrupts on this processor
        sti();
        acquire(&ptable.lock);
        for(p = ptable.proc; p < &ptable.proc[NPROC]; p++) {
            if(p->pid != pid) continue;
            cprintf("proc name \t pid \t size \t state \t parent \n");
            cprintf(" %s \t %d \t %d \t %d \t %d \n", p->name, p->pid, p->sz, p->state, p->parent->pid);
            printMap(p->pgdir);
            break;
        }
        release(&ptable.lock);
        if(p == &ptable.proc[NPROC])
            return -1;
        return 22;
    }
    
  2. 测试

    // Makefile
    _map\
       
    // map.c
    #include "types.h"
    #include "stat.h"
    #include "user.h"
       
    int main(int argc, char *argv[]) {
      if(argc <= 1) {
        printf(1, "need a pid.\n");
        exit();
      }
       
      int result = map(atoi(argv[1]));
      if(result == -1) {
    	printf(1, "pid invalid\n");
      }
      exit();
    }
    

运行 qemu ,然后执行 map 2 查看 shell 进程的信息。

观察 sbrk 分配过程

// Makefile
_sbrk\

// sbrk.c
#include "types.h"
#include "stat.h"
#include "user.h"

int
main(int argc, char *argv[])
{
  int pid = getpid();
  map(pid);

  char* m1 = sbrk(4*1024*1024);
  printf(1, "分配 4MB,逻辑起始地址为:%p\n", m1);
  map(pid);
  
  char* m2 = sbrk(4*1024);
  printf(1, "分配 4KB,逻辑起始地址为:%p\n", m2);
  map(pid);

  char* m3 = sbrk(-4096);
  printf(1, "释放 4KB,逻辑起始地址为:%p\n", m3);
  map(pid);

  char* m4 = sbrk(-4096);
  printf(1, "分配 4KB,逻辑起始地址为:%p\n", m4);
  map(pid);

  exit();
}

运行 qemu ,发现分配 m1 之前,用户空间只有一个二级页表,说明该程序很小,接着我们分配了 4MB,这时候一张页表不够了,用户会分配多一个页表,因此可以看到两张页表。

在虚拟空间中,我们发现用户空间的所有使用到的内存都是连续的,这个和 linux 算法有些不同,为了加深理解,观察内核代码,实现首次适应算法。

首次适应算法

实现内存分配算法首先得清楚逻辑地址和物理地址是如何对接上的。这里的调试信息我已经封装成 map 调用,知道进程号直接执行 map pid 即可。

利用 map 2 发现 shell 申请了 3 个物理页帧,如下

dir 0 table 0 对应的物理页帧:df32027
dir 0 table 1 对应的物理页帧:df30067
dir 0 table 2 对应的物理页帧:df2f003
dir 0 table 3 对应的物理页帧:df2e067

我们只关注最后三位,PTE_P 为 1 默认可读可取。

027 表示可读可写、已存在、用户程序可用。

067 表示脏页,可读可写、已经存在且用户可用 。

003 表示已存在可写。

1. 思路

  1. 系统已经实现了 kalloc 分配物理页帧和 kfree 释放物理页帧(这也是为什么动态内存需要经过操作系统同意),因此我们可以直接调用该接口分配物理页帧。
  2. 在 PCB 中添加记录虚拟空间段的结构体(可以用数组也可以用链表)
  3. 实现 mallocfree 系统调用,使得虚拟空间分配不一定要像 sbrk 函数一样,我们可以实现虚拟空间的空洞。