pollux's Dairy

mineucore-虚拟内存管理学习笔记

OS
字数统计: 3.5k阅读时长: 21 min
2019/10/06 Share

概述

虚拟页式存储技术，在页式存储管理的基础上，增加请求调页和页面置换

有了页式内存管理技术，CPU使用的地址已经不是实际的物理地址了，而是虚拟地址，进而可以通过设置段界限或页表项来设定程序运行时的访问空间，确保程序运行不越界，完成内存访问保护的功能。

但是想最大化利用物理内存，根据程序的局部性原理，即程序在执行过程中的一个较短的时期内，所执行的指令地址和指令操作数地址，分别局限于一定区域。可使程序在没有访问某个虚拟地址时，不分配物理内存，当程序访问某个虚拟地址时，操作系统在动态的分配内存，在页表中建立虚拟地址到物理地址的映射关系，这就是按需分页。

但是物理内存总会使用殆尽，操作系统可以将程序内存空间中不经常访问的数据放入外存中，并在页表项中标记，当发生缺页异常时，就把外存中的数据重新加载进内存中，这是页换入换出（page swap in/out）技术。如何选择物理页放入外存中，这就是页面置换算法的工作了。

当两个虚拟页的数据内容相同时，可只分配一个物理页框，这样如果对两个虚拟页的访问方式是只读方式，这两个虚拟页可共享页框，节省内存空间；如果CPU对其中之一的虚拟页进行写操作，则这两个虚拟页的数据内容会不同，需要分配一个新的物理页框，并将物理页框标记为可写，这样两个虚拟页面将映射到不同的物理页帧，确保整个内存空间的正确访问。这种技术称为写时复制（Copy On Write，简称COW）。

下面主要在物理内存管理和中断异常的基础上完成上面的三个内容。

按需分页与FIFO页面置换算法

在物理内存方面，使用Page结构体管理所有物理内存，每一个物理帧，都对应一个Page结构体。Page结构体保存在ucore系统的物理内存上方。为了实现页面置换算法，在Page结构体末尾，添加了两个新的成员。

1
2
3
4
5
6
7
8
struct Page {
    int ref; //该物理帧被线性地址引用的次数
    uint32_t flags; //描述页面属性的标志位
    unsigned int property; //描述连续空闲块的数量
    list_entry_t page_link; //用于串联空闲块双向链表的链接结构
    list_entry_t pra_page_link; //用来构造按页的第一次访问时间进行排序的一个链表，表头时间最近，表尾时间最远
    uintptr_t pra_vaddr; //用来记录此物理页对应的虚拟页起始地址
};

pra_page_link这个双向链表也是有头结点的

1
2
//swap_info.c
list_entry_t pra_list_head;//做为头结点，用双向链表各用到的页框Page结构体，按照时间顺序，使用时当成队列数据结构使用

但是对于用户态的程序来说，需要有相关的数据结构和操作来体现一般应用程序对虚拟内存的“需求”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct mm_struct {
    list_entry_t mmap_list; //连接vma_struct的双向链表的头结点
    struct vma_struct *mmap_cache; //指向当前正在使用的vma结构，用于提速
    pde_t *pgdir; //指向当前mm数据结构所维护的页目录表
    int map_count; //其链接的vma_struct的数量
    void *sm_priv; //指向用来链接记录页访问情况的链表头
};

struct vma_struct {
    struct mm_struct *vm_mm; //指向头mm结构
    uintptr_t vm_start; //虚拟地址的起始地址
    uintptr_t vm_end; //虚拟地址的结束地址
    uint32_t vm_flags; //虚拟空间的标志位
    list_entry_t list_link; //双向链表的连接结构（按照地址排序）
};

mm_struct维护一个页表的可用空闲空间，具体来说是一个mm_struct下链接多个vma_struct，vma_struct标记了这个4M空间中可以使用的虚拟空间，各个vma_struct间通过list_link双向链表链接，而mm_struct就是这个双向链表的表头。

当页表映射到物理内存时，页表内容为页帧的地址还有一些标志位，但是当虚拟内存映射到外存时，其页表内容如何设计？即如何区分物理内存的映射和swap区的映射。

一个页大小为4kb，当映射到硬盘中时，需要占用8个扇区（0.5kb/扇区）。可将PTE（页表项）的高24位表示对换到硬盘上的页的起始扇区号，并将bit 0置为0，即当PTE高24位不为0，且bit 0为0，则说明该物理页被映射到了swap区。

1
2
3
4
5
* swap_entry_t
* --------------------------------------------
* |         offset        |   reserved   | 0 |
* --------------------------------------------
*           24 bits            7 bits    1 bit

缺页中断的处理函数主要是do_pgfault这个函数，主要包括两个分支：1）当发生缺页中断时，如果页表项的内容为0，则表示发生缺页异常，接下来会请求一个新的物理页，然后更新页表内容，完成映射过程。2）如果不为0，则为是一个映射到swap区的缺页异常。当然不会直接到这两个分支，还需要根据错误号，做进一步判断。

下面完整的do_pgfault函数

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
//vmm.c
/* do_pgfault - 处理页中断异常的主要函数
 * @mm         : 管理可用虚拟内存空间的结构体
 * @error_code : 处理器抛出的异常码
 * @addr       : CR2寄存器保存的发生页访问错误的线性地址
 */
int
do_pgfault(struct mm_struct *mm, uint32_t error_code, uintptr_t addr) {
    int ret = -E_INVAL;
    //查找包含缺页异常addr的vma
    struct vma_struct *vma = find_vma(mm, addr);//在测试中 addr = 100h

    pgfault_num++;
    //若查找不到，说明该地址无效，不合法
    if (vma == NULL || vma->vm_start > addr) {
        cprintf("not valid addr %x, and  can not find it in vma\n", addr);
        goto failed;
    }
    //判断异常类型，与3，即&11b，取后两位
    switch (error_code & 3) {
    default:
    case 2: //缺页，存在写异常，下面判断物理页是否可写，若可写，通过下面流程将该物理页映射，若不可写，则报错
        if (!(vma->vm_flags & VM_WRITE)) {
            cprintf("do_pgfault failed: error code flag = write AND not present, but the addr's vma cannot write\n");
            goto failed;
        }
        break;
    case 1: //对应物理页存在，但是读异常，应该是权限问题，直接报错
        cprintf("do_pgfault failed: error code flag = read AND present\n");
        goto failed;
    case 0: //缺页，读异常，下面判断物理页是否可读，若可读，通过下面流程将该物理页映射，若不可写，则报错
        if (!(vma->vm_flags & (VM_READ | VM_EXEC))) {
            cprintf("do_pgfault failed: error code flag = read AND not present, but the addr's vma cannot read or exec\n");
            goto failed;
        }
    }
    /* 剩下两种情况：
     * 1. 写一个不存在的可写物理地址
     * 2. 读一个不存在的可读物理地址
     */
    uint32_t perm = PTE_U;//perm为PDE（页目录项）/PTE（页项）的权限位
    if (vma->vm_flags & VM_WRITE) {
        perm |= PTE_W;
    }
    addr = ROUNDDOWN(addr, PGSIZE);

    ret = -E_NO_MEM;

    pte_t *ptep=NULL;
    
    if ((ptep = get_pte(mm->pgdir, addr, 1)) == NULL) {
        cprintf("get_pte in do_pgfault failed\n");
        goto failed;
    }
    
    //如果该页表内容为0，说明未建立映射，
    if (*ptep == 0) { // pgdir_alloc_page申请一个物理页，并建立映射
        if (pgdir_alloc_page(mm->pgdir, addr, perm) == NULL) {
            cprintf("pgdir_alloc_page in do_pgfault failed\n");
            goto failed;
        }
    }
    else { // 否则就是映射到swap区，需要将磁盘中的数据加载到物理页
           // 调用 page_insert 重新建立映射
        if(swap_init_ok) {
            struct Page *page=NULL;
            if ((ret = swap_in(mm, addr, &page)) != 0) {
                cprintf("swap_in in do_pgfault failed\n");
                goto failed;
            }    
            page_insert(mm->pgdir, page, addr, perm);
            swap_map_swappable(mm, addr, page, 1);
            page->pra_vaddr = addr;
        }
        else {
            cprintf("no swap_init_ok but ptep is %x, failed\n",*ptep);
            goto failed;
        }
   }
   ret = 0;
failed:
    return ret;
}

下面是实现FIFO页面置换算法的_fifo_map_swappable函数

1
2
3
4
5
6
7
8
9
10
static int
_fifo_map_swappable(struct mm_struct *mm, uintptr_t addr, struct Page *page, int swap_in)
{
    list_entry_t *head=(list_entry_t*) mm->sm_priv;//获取队列的表头
    list_entry_t *entry=&(page->pra_page_link);//获取当前使用的维护物理页的Page结构体的地址
 
    assert(entry != NULL && head != NULL);
    list_add(head, entry);//所以实现链接效果，只要添加这一句就可以了
    return 0;
}

使用一个双向链表维护一个队列，用来保存物理页的使用情况。每次不论重新分配物理页建立映射，还是将磁盘中的数据装入物理内存建立映射，即每次物理页被使用，都会更新Page数据结构的pra_page_link链表，上面说了，这个链表按时间先后连接被使用的物理页，用以FIFO的页面置换算法，每次新使用的物理页都会链接在链表的末尾。

下面是实现的FIFO页面置换算法的_fifo_swap_out_victim函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static int
_fifo_swap_out_victim(struct mm_struct *mm, struct Page ** ptr_page, int in_tick)
{
     list_entry_t *head=(list_entry_t*) mm->sm_priv;//获取队列的表头
     assert(head != NULL);
     assert(in_tick==0);
     list_entry_t *le = head->next;
     assert(head!=le);
     struct Page *p = le2page(le, pra_page_link);//通过Page的成员pra_page_link获取Page的指针
     list_del(le);
     assert(p !=NULL);
     *ptr_page = p;
     return 0;
}

上面的队列保存的是正在使用的物理页，如果物理内存满了，就需要将正在使用的物理页置换到外存中，该函数_fifo_swap_out_victim就是删除队列中对首的最早使用的物理页，并用ptr_page保存。

分析测试数据

在测试中，只提供了4个物理页进行分配，首先建立了4个物理页的映射

1
2
3
4
5
6
7
//swap.c
//CHECK_VALID_PHY_PAGE_NUM = 4
     for (i=0;i<CHECK_VALID_PHY_PAGE_NUM;i++) {
          check_rp[i] = alloc_page();
          assert(check_rp[i] != NULL );
          assert(!PageProperty(check_rp[i]));
     }

然后通过直接写内存数据触发缺页中断，总共发生12次内存写

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
//swap_fifo.c
static int
_fifo_check_swap(void) {
    cprintf("write Virt Page c in fifo_check_swap\n");
    *(unsigned char *)0x3000 = 0x0c;_
    assert(pgfault_num==4);
    cprintf("write Virt Page a in fifo_check_swap\n");
    *(unsigned char *)0x1000 = 0x0a;
    assert(pgfault_num==4);
    cprintf("write Virt Page d in fifo_check_swap\n");
    *(unsigned char *)0x4000 = 0x0d;
    assert(pgfault_num==4);
    cprintf("write Virt Page b in fifo_check_swap\n");
    *(unsigned char *)0x2000 = 0x0b;
    assert(pgfault_num==4);
    cprintf("write Virt Page e in fifo_check_swap\n");//页面置换开始
    *(unsigned char *)0x5000 = 0x0e;//页面置换开始
    assert(pgfault_num==5);
    cprintf("write Virt Page b in fifo_check_swap\n");
    *(unsigned char *)0x2000 = 0x0b;
    assert(pgfault_num==5);
    cprintf("write Virt Page a in fifo_check_swap\n");
    *(unsigned char *)0x1000 = 0x0a;
    assert(pgfault_num==6);
    cprintf("write Virt Page b in fifo_check_swap\n");
    *(unsigned char *)0x2000 = 0x0b;
    assert(pgfault_num==7);
    cprintf("write Virt Page c in fifo_check_swap\n");
    *(unsigned char *)0x3000 = 0x0c;
    assert(pgfault_num==8);
    cprintf("write Virt Page d in fifo_check_swap\n");
    *(unsigned char *)0x4000 = 0x0d;
    assert(pgfault_num==9);
    cprintf("write Virt Page e in fifo_check_swap\n");
    *(unsigned char *)0x5000 = 0x0e;
    assert(pgfault_num==10);
    cprintf("write Virt Page a in fifo_check_swap\n");
    assert(*(unsigned char *)0x1000 == 0x0a);
    *(unsigned char *)0x1000 = 0x0a;
    assert(pgfault_num==11);
    return 0;
}

下面分析测试结果

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
set up init env for check_swap begin!
page fault at 0x00001000: K/W [no page found].
page fault at 0x00002000: K/W [no page found].
page fault at 0x00003000: K/W [no page found].
page fault at 0x00004000: K/W [no page found].
set up init env for check_swap over!
write Virt Page c in fifo_check_swap
write Virt Page a in fifo_check_swap
write Virt Page d in fifo_check_swap
write Virt Page b in fifo_check_swap
write Virt Page e in fifo_check_swap
page fault at 0x00005000: K/W [no page found].
swap_out: i 0, store page in vaddr 0x1000 to disk swap entry 2
write Virt Page b in fifo_check_swap
write Virt Page a in fifo_check_swap
page fault at 0x00001000: K/W [no page found].
*ptep!=0
swap_out: i 0, store page in vaddr 0x2000 to disk swap entry 3
swap_in: load disk swap entry 2 with swap_page in vadr 0x1000
write Virt Page b in fifo_check_swap
page fault at 0x00002000: K/W [no page found].
*ptep!=0
swap_out: i 0, store page in vaddr 0x3000 to disk swap entry 4
swap_in: load disk swap entry 3 with swap_page in vadr 0x2000
write Virt Page c in fifo_check_swap
page fault at 0x00003000: K/W [no page found].
*ptep!=0
swap_out: i 0, store page in vaddr 0x4000 to disk swap entry 5
swap_in: load disk swap entry 4 with swap_page in vadr 0x3000
write Virt Page d in fifo_check_swap
page fault at 0x00004000: K/W [no page found].
*ptep!=0
swap_out: i 0, store page in vaddr 0x5000 to disk swap entry 6
swap_in: load disk swap entry 5 with swap_page in vadr 0x4000
write Virt Page e in fifo_check_swap
page fault at 0x00005000: K/W [no page found].
*ptep!=0
swap_out: i 0, store page in vaddr 0x1000 to disk swap entry 2
swap_in: load disk swap entry 6 with swap_page in vadr 0x5000
write Virt Page a in fifo_check_swap
page fault at 0x00001000: K/R [no page found].
swap_out: i 0, store page in vaddr 0x2000 to disk swap entry 3
swap_in: load disk swap entry 2 with swap_page in vadr 0x1000
count is 0, total is 7

可以看出程序要对0x00005000进行写时出现缺页中断，但是物理页已经满了，就把0x00001000对应的物理页置换到swap区……

最后12次写中，发生了7次缺页异常。

其他

使用gdb查看mm_struct 和 vma_struct 结构体的内容

查看 mm_struct 和 vma_struct 结构体的内容。可以看到初始时，只有一个页目录表项，维护了一个页表，该页表维护了0~4M的虚拟内存空间

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
gef➤  p check_mm_struct
$3 = (struct mm_struct *) 0xc0303000
  
gef➤  p *((struct mm_struct *) 0xc0303000)
$12 = {
  mmap_list = {
    prev = 0xc0304010, 
    next = 0xc0304010
  }, 
  mmap_cache = 0xc0304000, 
  pgdir = 0xc0120000, 
  map_count = 0x1, 
  sm_priv = 0x0
}

gef➤  p *((struct vma_struct *) (0xc0304010-0x10))
$13 = {
  vm_mm = 0xc0303000, 
  vm_start = 0x0, 
  vm_end = 0x400000, 
  vm_flags = 0x2, 
  list_link = {
    prev = 0xc0303000, 
    next = 0xc0303000
  }
}
查看页表内容，可以看到页表中没有任何映射
gef➤  x/4xw 0xc0120000
0xc0120000:	0x00000000	0x00000000	0x00000000	0x00000000

页面置换算法分类

局部页面置换算法：1.最优算法 2.FIFO算法 3.最近最久未使用算法 4.时钟置换算法 5.最不常用算法

全局页面置换算法：1.工作集置换算法 2.缺页率置换算法

局部性原理

程序在执行过程中的一个较短的时期内，所执行的指令地址和指令操作数地址，分别局限于一定区域，包括时间局部性、空间局部性、分支局部性

原文作者：Po1lux

原文链接：http://yoursite.com/2019/10/06/mineucore-虚拟内存管理学习笔记/

发表日期：October 6th 2019, 6:51:21 pm

更新日期：October 9th 2019, 3:28:08 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 概述
  2. 2. 按需分页与FIFO页面置换算法
  3. 3. 分析测试数据
  4. 4. 其他
    1. 4.1. 使用gdb查看mm_struct 和 vma_struct 结构体的内容
    2. 4.2. 页面置换算法分类
    3. 4.3. 局部性原理
Total : 56
2020
2019
2018
unlink fastbin attack House of spirit House of Force UAF DynELF PIE format string off by one x64 64bit 格式化字符串漏洞 栈溢出 Canary tcache libc-2.29 chunk overlapping chunk extend shellcode，系统调用 libc2.29 stack overflow fmt rop 2016，CTFs，fsb CTF stack pivoting OS pwnable fsb
heap stack android-reverse learning-note android-system Operating-System pwnable conclusion