操作系统

xv6 虚拟空间实现不连续分配

源码地址:https://github.com/professordeng/xv6-paging

  1. 实现 myallocuvm 函数 (vm.c

    实现物理内存分配和虚拟地址到物理地址的映射。

    // 入参:申请内存的进程页表目录首地址 *pgdir,虚拟空间起始地址 start,虚拟空间结束地址 end
    // 返回值:成功返回分配大小,失败返回 0
    int
    myallocuvm(pde_t *pgdir, uint start, uint end) {
        char* mem;
        uint a;
        a = PGROUNDUP(start);
        for(; a < end; a += PGSIZE) {
            mem = kalloc();
        	if(mem == 0){
            	// 物理内存不足处理
        	}
        	memset(mem, 0, PGSIZE);
        	if(mappages(pgdir, (char*)a, PGSIZE, V2P(mem), PTE_W|PTE_U) < 0){
            	// 页表影射失败处理
        	}
        }
        return (end-start);
    }
    
  2. 实现 mydeallocuvm 函数(vm.c

    实现物理内存释放和更新页表。

    // 入参:申请内存的进程页表目录首地址 *pgdir,虚拟空间起始地址 start,虚拟空间结束地址 end
    // 返回值:默认返回 1
    int        
    mydeallocuvm(pde_t *pgdir, uint start, uint end) {
        pte_t *pte;
        uint a, pa;
         
        a = PGROUNDUP(start);
        for(; a < end; a += PGSIZE) {
            pte = walkpgdir(pgdir, (char*)a, 0);
            if(!pte)
                a += (NPTENTRIES - 1) * PGSIZE;
            else if((*pte & PTE_P) != 0){
                pa = PTE_ADDR(*pte);
                if(pa == 0)
                    panic("kfree");
                char *v = P2V(pa);
                kfree(v);
                *pte = 0;
            }
        }
        return 1;
    }
    
  3. 给进程控制块添加结构存储不连续内存块的信息。

    proc.h 中添加结构信息。

    struct vma{
    	int next;     // -1 表示未分配,否则表示下一个内存索引
    	int address;  // 内存块首地址  
    	int length;   // 内存块大小
    };
       
    // 在 struct proc 结构体中添加
    struct vma vm[10];  // 可分配 9 个不连续内存块,第一个为指针头
    

    proc.callocproc 中初始化

    for(i = 0; i < 10; i++) {
    	p->vm[i].next = -1;
        p->vm[i].length = 0;
    }
    p->vm[0].next = 0;
    
  4. 实现 mygrowproc 函数

    给当前进程分配内存。

    // 入参:需要内存的大小
    // 返回值:新内存起始地址,失败返回 0
    int 
    mygrowproc(int n){                 // 实现首次最佳适应算法
      	struct vma *vm = proc->vm;     // 遍历寻找合适的空间
        int start = proc->sz;          // 寻找合适的分配起点
        int index;
        int prev = 0;
        int i;
       
        for(index = vm[0].next; index != 0; index = vm[index].next){
     	  	if(start + n < vm[index].address)
    			break;
    	 	start = vm[index].address + vm[index].length;
    	        prev = index;
    	}
           
        for(i = 1; i < 10; i++) {            // 寻找一块没有用的 vma 记录新的内存块
           	if(vm[i].next == -1){
            	vm[i].next = index;                     
                vm[i].address = start;
                vm[i].length = n;
       
                vm[prev].next = i;
                              
    			myallocuvm(proc->pgdir, start, start + n);
    	        switchuvm(proc);
                return start;   // 返回分配的地址
    	    }
    	}
        switchuvm(proc);
        return 0;
    }
    
  5. 实现 myreduceproc 函数

    释放当前进程的内存。

    // 入参:需要释放的内存地址
    // 返回值:默认返回 0
    int
    myreduceproc(int address){  // 释放 address 开头的内存块
       	int prev = 0;
        int index;
        for(index = proc->vm[0].next; index != 0; index = proc->vm[index].next) {
           	if(proc->vm[index].address == address && proc->vm[index].length > 0) {
            	mydeallocuvm(proc->pgdir, proc->vm[index].address, proc->vm[index].address + proc->vm[index].length);                   
        		proc->vm[prev].next = proc->vm[index].next;
                proc->vm[index].next = -1;
                proc->vm[index].length = 0;
                break;
            }
            prev = index;
        }
        switchuvm(proc);
        return 0;
    }
    
  6. 添加系统调用 myalloc 供用户程序申请新内存

    // syscall.h
    #define SYS_myalloc 23
       
    // usys.S
    SYSCALL(myalloc)
       
    // syscall.c
    extern int sys_myalloc(void);
       
    [SYS_myalloc]  sys_myalloc,
       
    // user.h
    char* myalloc(int);
       
    // sysproc.c
    int
    sys_myalloc(void)
    {
      	int n;   // 分配 n 个字节
        if(argint(0, &n) < 0)
          	return 0;
        if(n <= 0)
            return 0;
        cprintf("myalloc 申请 %d 个字节 \n", n);
        return mygrowproc(n);
    }
    
  7. 添加系统调用 myfree 供用户程序释放申请的内存

    // syscall.h
    #define SYS_myfree 24
       
    // syscall.c
    extern int sys_myfree(void);
    [SYS_myfree] sys_myfree;
       
    // usys.S
    SYSCALL(myfree)
       
    // user.h
    int myfree(void*);
       
    // sysproc.c
       
    int 
    sys_myfree(void) {
       	int addr;
        if(argint(0, &addr) < 0)
      	   return -1;
        return myreduceproc(addr);
    }
    
  8. 添加系统调用 map 观察用户程序虚拟空间布局

    // 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;
    	int index = 0;
    	// Enable interrupts on this processor
    	sti();
    	acquire(&ptable.lock);
    	for(p = ptable.proc; p < &ptable.proc[NPROC]; p++) {
    		if(p->pid != pid) continue;
    		cprintf("pid \t size \t state \t ppid \t name \n");
    		cprintf(" %d \t %d \t %d \t %d \t %s \n", p->pid, p->sz, p->state, p->parent->pid, p->name);
    		printMap(p->pgdir);
    		for(index = p->vm[0].next; index != 0; index = p->vm[index].next) {
    			cprintf("编号为 %d 的内存起始地址为 %d,大小为 %d,下一块内存编号为 %d\n", index, p->vm[index].address, p->vm[index].length, p->vm[index].next);
    		}
    		break;
    	}
    	release(&ptable.lock);
    	if(p == &ptable.proc[NPROC])
    		return -1;
    	return 22;
    }
    

    添加用户指令程序 map pid

    // 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();
    }
    
  9. 添加用户测试程序 myalloc 进行测试功能测试。

    首先连续生成 5 块大小不一的内存,然后释放 2、4 块,查看进程空间是否出现空洞。

    // Makefile
    _myalloc\
       
    // myalloc.c
    #include "types.h"
    #include "stat.h"
    #include "user.h"
       
       
    int
    main(int argc, char *argv[]) {
      int pid = getpid();   
      map(pid);
         
      char* m1 = (char*)myalloc(2 * 4096);
      char* m2 = (char*)myalloc(3 * 4096);
      char* m3 = (char*)myalloc(1 * 4096);
      char* m4 = (char*)myalloc(7 * 4096);
      char* m5 = (char*)myalloc(9 * 4096);
       
      myfree(m2);
      myfree(m4);
         
      map(pid);
       
      myfree(m1);
      myfree(m3);
     myfree(m5);
       
      exit();
    }
    
  10. map 调用系统验证截图

    首先测试一下 map pid ,一开始 xv6 已经有 initshell 进程在执行了,因此我们直接查看其中的信息。如下图,我们先查看 init 进程的信息,这里显示了进程号、非动态分配大小(使用 myalloc 生成的内存块不计入内),以及状态(2 表示 SLEEP),父进程号和名字。

    接下来就是虚拟空间以及对应的物理页帧。

    例如 dir 0 table 0 的换算公式为 addr = 4M*dir + 4KB*table

    1559788338667

  11. 用户程序 myalloc 的执行效果,代码查看 9 。

    直接在 qemu 环境输入 myalloc ,直接结果如下

    一开始先调用 map 查看虚拟空间,可以看到是连续的,而且只使用了一张页表的前三项。

    接下来执行分配过程(代码查看 9),可以看到页表项,4~8 中空缺了三页,也就是释放 2 引起的空洞。

    然后 8~16 空缺了 7 页,也就是释放 4 引起的虚拟空间的空洞。

    最后输出的是内存块链表,这里利用了数组的方式(代码查看 3)

    1559788669703

  12. 访问分配后又释放的内存会陷入中断

    修改 myalloc.c 的代码,如下。按上面的方式执行,当输出 m1 内存中的字符串时是正常的,但是对 释放后的 m2 进行写操作,就发生了异常。

    #include "types.h"
    #include "stat.h"
    #include "user.h"
        
        
    int
    main(int argc, char *argv[]) {
      int pid = getpid();   
      map(pid);
          
      char* m1 = (char*)myalloc(2 * 4096);
      char* m2 = (char*)myalloc(3 * 4096);
      char* m3 = (char*)myalloc(1 * 4096);
      char* m4 = (char*)myalloc(7 * 4096);
      char* m5 = (char*)myalloc(9 * 4096);
        
      m1[0] = 'h';
      m1[1] = '\0';
      printf(1, "m1: %s\n", m1);
        
      myfree(m2);
          
      m2[0] = 'h';
      m2[1] = '\0';
      printf(1, "m1: %s\n", m2);
        
        
          
      myfree(m4);
          
      map(pid);
        
      myfree(m1);
      myfree(m3);
      myfree(m5);
        
      exit();
    }
    

    执行过程如下:

    1559789319864