导读

参考:

在应用程序的视角中,动态内存分配中的内存,其实就是操作系统管理的“堆 (Heap)”。但现在要实现操作系统,那么就需要操作系统自身能提供动态内存分配的能力。如果要实现动态内存分配的能力,需要操作系统需要有如下功能:

  • 初始时能提供一块大内存空间作为初始的“堆” 。在没有分页机制情况下,这块空间是物理内存空间,否则就是虚拟内存空间。
  • 提供在堆上分配一块内存的函数接口。这样函数调用方就能够得到一块地址连续的空闲内存块进行读写。
  • 提供释放内存的函数接口。能够回收内存,以备后续的内存分配请求。
  • 提供空闲空间管理的连续内存分配算法。能够有效地管理空闲快,这样就能够动态地维护一系列空闲和已分配的内存块。
  • (可选)提供建立在堆上的数据结构和操作。有了上述基本的内存分配与释放函数接口,就可以实现类似动态数组,动态字典等空间灵活可变的堆数据结构,提高编程的灵活性。

操作系统给应用程序提供统一的访问接口,即应用程序不需要了解虚拟内存和物理内存的区别的,操作系统提出了 地址空间 Address Space 抽象,并在内核中建立虚实地址空间的映射机制,给应用程序提供一个虚拟的内存环境。

到目前为止仍被操作系统内核广泛使用的抽象被称为 地址空间 (Address Space) 。某种程度上讲,可以将它看成一块 巨大但并不一定真实存在的内存。在每个应用程序的视角里,操作系统分配给应用程序一个范围有限(但其实很大),独占的连续地址空间(其中有些地方被操作系统限制不能访问,如内核本身占用的虚地址空间等),因此应用程序可以在划分给它的地址空间中随意规划内存布局,它的 各个段也就可以分别放置在地址空间中它希望的位置(当然是操作系统允许应用访问的地址)。应用同样可以使用一个地址作为索引来读写自己地址空间的数据,就像用物理地址 作为索引来读写物理内存上的数据一样。这种地址被称为 虚拟地址 (Virtual Address) 。当然,操作系统要达到 地址空间 抽象的设计目标,需要有计算机硬件的支持,这就是计算机组成原理课上讲到的 MMUTLB 等硬件机制。

分段管理:尽管内碎片被消除了,但内存浪费问题并没有完全解决。这是因为每个段的大小都是不同的(它们可能来自不同的应用,功能 也不同),内核就需要使用更加通用、也更加复杂的连续内存分配算法来进行内存管理,而不能像之前的插槽那样以一个比特 为单位。顾名思义,连续内存分配算法就是每次需要分配一块连续内存来存放一个段的数据。 随着一段时间的分配和回收,物理内存还剩下一些相互不连续的较小的可用连续块,其中有一些只是两个已分配内存块之间的很小的间隙,它们自己可能由于空间较小,已经无法被 用于分配,被称为 外碎片 (External Fragment) 。

image-20240621164912284

分页管理:

就需要内核始终以一个同样大小的单位来在物理内存上放置应用地址空间中的数据,这样内核就可以 使用简单的插槽式内存管理,使得内存分配算法比较简单且不会产生外碎片;同时,这个单位的大小要足够小,从而其内部没有 被用到的内碎片的大小也足够小,尽可能提高内存利用率。这便是我们将要介绍的分页内存管理。

image-20240621165010141

为了方便实现虚拟页面到物理页帧的地址转换,我们给每个虚拟页面和物理页帧一个编号,分别称为 虚拟页号 (VPN, Virtual Page Number) 和 物理页号 (PPN, Physical Page Number) 。每个应用都有一个不同的 页表 (Page Table) ,里面记录了该应用地址空间中的每个虚拟页面映射到物理内存中的哪个物理页帧,即数据实际 被内核放在哪里。我们可以用页号来代表二者,因此如果将页表看成一个键值对,其键的类型为虚拟页号,值的类型则为物理 页号。

当 MMU 进行地址转换的时候: 当然对三级页表 映射关系更加复杂,但总体上逻辑差不多

  1. 它首先找到给定的虚拟地址所在的虚拟页面的页号
  2. 然后查当前应用的页表根据虚拟页号 找到物理页号
  3. 最后按照虚拟地址在它所在的虚拟页面中的相对位置相应给物理页号对应的物理页帧的起始地址加上一个偏移量, 这就得到了实际访问的物理地址。

1.riscv的分页机制

riscv支持三种分页转换机制:

  • Sv32:仅支持32位riscv处理器,是一个二级页表结构,支持32位虚拟地址转换
  • Sv39:支持64位riscv处理器,是一个三级页表结构,支持39位虚拟地址转换
  • Sv48:支持64位riscv处理器,是一个四级页表结构,支持48位虚拟地址转换

我们采用sv39的机制进行分页管理,即使用三级页表结构

参考:

  1. RISC-V 虚拟存储系统(文档阅读学习)_satp寄存器-CSDN博客
  2. 实现 SV39 多级页表机制(上) — rCore-Tutorial-Book-v3 0.1 文档 (gitcode.host)

介绍如下:

SATP寄存器

SATP(Supervisor Address Translation and Protection Register):控制supervisor模式下的地址转换和保护

image-20240620164636731

  • MODE 控制 CPU 使用哪种页表实现;当 MODE 设置为 0 的时候,代表所有访存都被视为物理地址;而设置为 8 的时候,SV39 分页机制被启用,所有 S/U 特权级的访存被视为一个 39 位的虚拟地址,它们需要先经过 MMU(memory menage unit内存管理单元) 的地址转换流程,如果顺利的话,则会变成一个 56 位的物理地址来访问物理内存;否则则会触发异常。
  • ASID 表示地址空间标识符,这里还没有涉及到进程的概念,我们不需要管这个地方;其实就是表示当前进程的ASID
  • PPN 存的是根页表所在的物理页号。这样,给定一个虚拟页号,CPU 就可以从三级页表的根页表开始一步步的将其映射到一个物理页号。

Sv39

  • 39位虚拟地址空间
  • 支持大小4KB,2MB,1GB的页;
  • 三级页表结构,每个页有512个表项,每个表项8B,故每个页表项地址8B对齐;
  • 每一级的PTE都可能是叶子PTE(page table entry)页表条目,即包含最终物理地址的PTE。
  • 物理地址构成:
    • - 4KB:{PPN[2] , PPN[1] , PPN[0] , VA.pageoffset}
    • - 2MB:{PPN[2] , PPN[1] , VPN[0] , VA.pageoffset}
    • - 1GB:{PPN[2] , VPN[1] , VPN[0] , VA.pageoffset}

image-20240620170056663

  • 取指、load、store的地址是64位,地址的63:39位必须与第38位相同,否则会导致page fault异常;

PTE

PTE的结构中定义了如何将虚拟地址映射到物理地址:

  • **V (Valid)**:有效位,表示该页表条目是否有效。
  • **R (Read)**:读位,表示该页是否可读。
  • **W (Write)**:写位,表示该页是否可写。
  • **X (Execute)**:执行位,表示该页是否可执行。
  • **U (User)**:用户位,表示该页是否在用户模式下可访问。
  • **G (Global)**:全局位,表示该页是否对所有地址空间可见。
  • **A (Accessed)**:访问位,表示该页是否被访问过。
  • **D (Dirty)**:脏位,表示该页是否被写入过。
  • **RSW (Reserved for Software)**:保留给软件使用的位。
  • **PPN (Physical Page Number)**:物理页号,表示该页的物理地址。
  • Reserved:保留位

三级页表虚拟地址转换物理地址过程

image-20240620172006572
  • MMU通过satp寄存器得到PGD的物理地址,结合PGD index(即VPN[2])找到PMD;找到PMD后,再结合PMD index(即VPN[1])找到PTE,然后结合PTE index(即VPN[0])得到VAPTE索引中的值,从而得到物理地址。

2.使用栈管理物理页帧

栈数据结构以及相关函数的实现

c语言下需要自己实现栈的数据结构,分别新建stack.c和.h文件

OS/lib/stack.h

  • stack结构体中 data维护的是物理页号,所以物理页号是u64类型的
  • 然后声明了相关的函数
  • 栈顶需要定义成int类型,不能定义成无符号类型,因为对栈初始化时,top的值被设置为-1,但是后面会让top和0进行大小比较,如果设置成无符号会导致结果出错。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#ifndef SOS_STACK_H__
#define SOS_STACK_H__

#include "sifanos/os.h"

#define MAX_SIZE 10000

typedef struct {
u64 data[MAX_SIZE];
int top; // 不能定义成无符号类型,不然会导致 -1 > 0
} Stack;

bool isEmpty(Stack *stack);
bool isFull(Stack *stack);
void push(Stack *stack, u64 value);
u64 pop(Stack *stack);
u64 top(Stack *stack);

#endif

OS/lib/stack.c

实现了相关的函数

注意 bool 类型还需要在types.h中进行定义

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
#include <sifanos/stack.h>

// 初始化栈
void initStack(Stack *stack) {
stack->top = -1;
}

// 判断栈是否为空
bool isEmpty(Stack *stack) {
return stack->top == -1;
}

// 判断栈是否已满
bool isFull(Stack *stack) {
return stack->top == MAX_SIZE - 1;
}

// 入栈操作
void push(Stack *stack, u64 value) {
if (isFull(stack)) {
printk("Stack overflow\n");
return;
}
stack->data[++stack->top] = value;
}

// 出栈操作
u64 pop(Stack *stack) {
if (isEmpty(stack)) {
printk("Stack underflow\n");
return -1; // 表示栈为空或操作失败
}
return stack->data[stack->top--];
}

// 获取栈顶元素
u64 top(Stack *stack) {
if (isEmpty(stack)) {
printk("Stack is empty\n");
return -1; // 表示栈为空
}
return stack->data[stack->top];
}

OS/include/types.h

1
2
3
4
5
#ifndef __cplusplus
#define bool _Bool
#define true 1
#define false 0
#endif

内存管理相关函数的实现

分别新建address.caddress.h

include/address.h

定义了PA,VA,PPN,VPN 以及对相应的位进行操作 注意还需要实现 string.h文件和 assert.h文件 断言

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
#ifndef SOS_ADDRESS_H
#define SOS_ADDRESS_H

#include <sifanos/os.h>
#include <sifanos/stack.h>
#include <sifanos/string.h>
#include <sifanos/assert.h>

#define PAGE_SIZE 0x1000 // 4kb 一页的大小
#define PAGE_SIZE_BITS 0xc // 12 页内偏移地址长度

#define PA_WIDTH_SV39 56 //物理地址长度 0 - 55
#define VA_WIDTH_SV39 39 //虚拟地址长度 Sv39
#define PPN_WIDTH_SV39 (PA_WIDTH_SV39 - PAGE_SIZE_BITS) // 物理页号 44位 [55:12]
#define VPN_WIDTH_SV39 (VA_WIDTH_SV39 - PAGE_SIZE_BITS) // 虚拟页号 27位 [38:12]

#define MEMORY_END 0x80800000 // 0x80200000 ~ 0x80800000
#define MEMORY_START 0x80400000

/* 物理地址 */
typedef struct {
uint64_t value;
} PhysAddr;

/* 虚拟地址 */
typedef struct {
uint64_t value;
} VirtAddr;

/* 物理页号 */
typedef struct {
uint64_t value;
} PhysPageNum;

/* 虚拟页号 */
typedef struct {
uint64_t value;
} VirtPageNum;


// 定义位掩码常量
#define PTE_V (1 << 0) //有效位
#define PTE_R (1 << 1) //可读属性
#define PTE_W (1 << 2) //可写属性
#define PTE_X (1 << 3) //可执行属性
#define PTE_U (1 << 4) //用户访问模式
#define PTE_G (1 << 5) //全局映射
#define PTE_A (1 << 6) //访问标志位
#define PTE_D (1 << 7) //脏位

#endif

string.h

1
2
3
4
5
6
7
8
9
#ifndef SOS_STRING_H__
#define SOS_STRING_H__

#include <sifanos/os.h>
size_t strlen(const char *str);
void* memcpy(void *dest, const void *src, size_t count);
void* memset(void *dest, int ch, size_t count);

#endif

assert.h

这里实现了断言,注意预定义的宏

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#ifndef SOS_ASSERT_H
#define SOS_ASSERT_H

void assertion_failure(char *exp, char *file, char *base, int line);


/*
__FILE__是一个预定义的宏,在C语言中表示当前源文件的文件名。
在预处理阶段,编译器会将所有的__FILE__宏替换为当前源文件的文件名字符串。
__BASE_FILE__是一个预定义的宏,在某些编译器中用于表示当前编译单元的顶层源文件的文件名,
即当前源文件所属的工程或者库的主文件名。
__LINE__是一个预定义的宏,在C语言中表示当前代码所在的行号。
在预处理阶段,编译器会将所有的__LINE__宏替换为当前代码所在的行号。
*/


#define assert(exp) \
if (exp) \
; \
else \
assertion_failure(#exp, __FILE__, __BASE_FILE__, __LINE__)

#endif

src/assert.c

出现错误后会调用printk函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <sifanos/assert.h>
#include <sifanos/types.h>

// 强制阻塞
static void spin(char *name)
{
printk("spinning in %s ...\n", name);
while (true)
;
}


//提示报错信息
void assertion_failure(char *exp, char *file, char *base, int line)
{
printk(
"\n--> assert(%s) failed!!!\n"
"--> file: %s \n"
"--> base: %s \n"
"--> line: %d \n",
exp, file, base, line);

spin("assertion_failure()");
}

src/address.c

首先将uint_64,转换为虚拟地址 物理地址 ppn vpn等

  • **phys_addr_from_size_t**:将一个 uint64_t 类型的值转换为物理地址 PhysAddr

    • 通过与掩码 (1ULL << PA_WIDTH_SV39) - 1 相与,确保结果在物理地址的有效范围内。
  • **phys_page_num_from_size_t**:将一个 uint64_t 类型的值转换为物理页号 PhysPageNum

    • 同样通过与掩码 (1ULL << PPN_WIDTH_SV39) - 1 相与,确保结果在物理页号的有效范围内。

    **size_t_from_phys_addr**:将物理地址 PhysAddr 转换为 uint64_t

    • 直接返回物理地址的 value 字段。

    **size_t_from_phys_page_num**:将物理页号 PhysPageNum 转换为 uint64_t

    • 直接返回物理页号的 value 字段。

    **phys_addr_from_phys_page_num**:将物理页号 PhysPageNum 转换为物理地址 PhysAddr

    • 通过左移 PAGE_SIZE_BITS 位,将页号转换为地址。

    **virt_addr_from_size_t**:将一个 uint64_t 类型的值转换为虚拟地址 VirtAddr

    • 通过与掩码 (1ULL << VA_WIDTH_SV39) - 1 相与,确保结果在虚拟地址的有效范围内。

    **virt_page_num_from_size_t**:将一个 uint64_t 类型的值转换为虚拟页号 VirtPageNum

    • 通过与掩码 (1ULL << VPN_WIDTH_SV39) - 1 相与,确保结果在虚拟页号的有效范围内。
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
/* 给定一个u64 转换为PhysAddr */
PhysAddr phys_addr_from_size_t(uint64_t v) {
PhysAddr addr;
addr.value = v & ((1ULL << PA_WIDTH_SV39) - 1);
return addr;
}

/*给定一个u64 转换为PhysPageNum */
PhysPageNum phys_page_num_from_size_t(uint64_t v) {
PhysPageNum pageNum;
pageNum.value = v & ((1ULL << PPN_WIDTH_SV39) - 1);
return pageNum;
}
/* 给定一个PhysAddr转换为u64 */
uint64_t size_t_from_phys_addr(PhysAddr v) {
return v.value;
}

/* 给定一个PhysPageNum 转换为u64 */
uint64_t size_t_from_phys_page_num(PhysPageNum v) {
return v.value;
}


/* 从物理页号转换为实际物理地址 */
PhysAddr phys_addr_from_phys_page_num(PhysPageNum ppn)
{
PhysAddr addr;
addr.value = ppn.value << PAGE_SIZE_BITS ;
return addr;
}

/* 给定一个u64 转换为VirtAddr */
VirtAddr virt_addr_from_size_t(uint64_t v) {
VirtAddr addr;
addr.value = v & ((1ULL << VA_WIDTH_SV39) - 1);
return addr;
}

/* 给定一个u64 转换为VirtPageNum */
VirtPageNum virt_page_num_from_size_t(uint64_t v) {
VirtPageNum pageNum;
pageNum.value = v & ((1ULL << VPN_WIDTH_SV39) - 1);
return pageNum;
}

/*给定一个VirtAddr 转换为一个u64 */
uint64_t size_t_from_virt_addr(VirtAddr v) {
if (v.value >= (1ULL << (VA_WIDTH_SV39 - 1))) {
return v.value | ~((1ULL << VA_WIDTH_SV39) - 1);
} else {
return v.value;
}
}

/* 给定一个VirtPageNum 转换为 u64*/
uint64_t size_t_from_virt_page_num(VirtPageNum v) {
return v.value;
}

/* 物理地址向下取整 */
PhysPageNum floor_phys(PhysAddr phys_addr) {
PhysPageNum phys_page_num;
phys_page_num.value = phys_addr.value / PAGE_SIZE;
return phys_page_num;
}

/* 物理地址向上取整 */
PhysPageNum ceil_phys(PhysAddr phys_addr) {
PhysPageNum phys_page_num;
phys_page_num.value = (phys_addr.value + PAGE_SIZE - 1) / PAGE_SIZE;
return phys_page_num;
}

/* 把虚拟地址转换为虚拟页号 */
VirtPageNum virt_page_num_from_virt_addr(VirtAddr virt_addr)
{
VirtPageNum vpn;
vpn.value = virt_addr.value / PAGE_SIZE;
return vpn;
}

页帧分配器

  • 实现了new:用于创建实例
  • alloc:分配
  • 在分配 alloc 的时候,首先会检查栈 recycled 内有没有之前回收的物理页号,如果有的话直接弹出栈顶并返回;否则的话我们只能从之前从未分配过的物理页号区间 [ current , end ) 上进行分配,我们分配它的左端点 current ,同时将管理器内部维护的 current1 代表 current 已被分配了。然后清空此页内存,全部初始化为0,最后返回分配的页的物理页号。
  • dealloc:删除与回收
    • 需要检测合法性
      • 页面之前一定是被分配过,因此他的物理页号一定是 < current
      • 该页面没有正处在回收状态,即它的物理页号不能在栈 recycled 中找到。
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
/* StackFrameAllocator*/
typedef struct
{
uint64_t current; //空闲内存的起始物理页号
uint64_t end; //空闲内存的结束物理页号
Stack recycled; // 回收页
}StackFrameAllocator;

void StackFrameAllocator_new(StackFrameAllocator* allocator) {
allocator->current = 0;
allocator->end = 0;
initStack(&allocator->recycled);
}
void StackFrameAllocator_init(StackFrameAllocator *allocator, PhysPageNum l, PhysPageNum r) {
allocator->current = l.value;
allocator->end = r.value;
}

PhysPageNum StackFrameAllocator_alloc(StackFrameAllocator *allocator) {
PhysPageNum ppn;
if (allocator->recycled.top >= 0) {
ppn.value = pop(&(allocator->recycled));
} else {
if (allocator->current == allocator->end) {
ppn.value = 0; // Return 0 as None
} else {
ppn.value = allocator->current++;
}
}
/* 清空此页内存 : 注意不能覆盖内核代码区,分配的内存只能是未使用部分*/
PhysAddr addr = phys_addr_from_phys_page_num(ppn);
memset(addr.value,0,PAGE_SIZE);
return ppn;
}

void StackFrameAllocator_dealloc(StackFrameAllocator *allocator, PhysPageNum ppn) {
uint64_t ppnValue = ppn.value;
// 检查回收的页面之前一定被分配出去过
if (ppnValue >= allocator->current) {
printk("Frame ppn=%lx has not been allocated!\n", ppnValue);
return;
}
// 检查未在回收列表中
if(allocator->recycled.top>=0)
{
for (size_t i = 0; i <= allocator->recycled.top; i++)
{
if(ppnValue ==allocator->recycled.data[i] )
return;
}
}
// 回收物理内存页号
push(&(allocator->recycled), ppnValue);
}

测试程序:

测试函数一次调用了new,init ,然后尝试分配五页内存,并打印五页内存的物理页号,然后将分配的五页内存释放掉,此时这五页内存应该会全部被压入recycled栈中,然后再次分配五页内存,此时分配的话就是从recycledpop的内存了。强调一下在StackFrameAllocator_init函数中传入的起始物理内存的地址必须在内核代码段之上,在头文件中进行了定义

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
static StackFrameAllocator FrameAllocatorImpl;
void frame_allocator_test()
{
StackFrameAllocator_new(&FrameAllocatorImpl);
StackFrameAllocator_init(&FrameAllocatorImpl, \
floor_phys(phys_addr_from_size_t(MEMORY_START)), \
ceil_phys(phys_addr_from_size_t(MEMORY_END)));
printk("Memoery start:%d\n",floor_phys(phys_addr_from_size_t(MEMORY_START)));
printk("Memoery end:%d\n",ceil_phys(phys_addr_from_size_t(MEMORY_END)));
// 第一次分配
PhysPageNum frame[10];
for (size_t i = 0; i < 5; i++)
{
frame[i] = StackFrameAllocator_alloc(&FrameAllocatorImpl);
printk("frame id:%d\n",frame[i].value);
}

// 回收
for (size_t i = 0; i < 5; i++)
{
StackFrameAllocator_dealloc(&FrameAllocatorImpl,frame[i]);
printk("allocator->recycled.data.value:%d\n",FrameAllocatorImpl.recycled.data[i]);
printk("frame id:%d\n",frame[i].value);
}
// 再分配
PhysPageNum frame_test[10];
for (size_t i = 0; i < 5; i++)
{
frame[i] = StackFrameAllocator_alloc(&FrameAllocatorImpl);
printk("frame id:%d\n",frame[i].value);
}
}

3.测试

mian.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include "sifanos/os.h"

extern void frame_allocator_test();

void os_main()
{
printk("hello!!!\n");
frame_allocator_test();
while(1) {

}
//trap_init();
//task_init();
//timer_init(); // 时钟初始化
//run_first_task();

}

image-20240621154445235

总结

image-20240621160558362

本节新增了以上的文件

  • stack中实现了栈这个数据结构,因为后续的内存管理需要用到栈。
    • 实现了栈的常用接口pushpoptop
  • assert中,实现了断言
  • address中,实现了Sv39的三级页表内存管理
    • 实现了将uint_64转换位物理地址,虚拟地址等 PPN,VPN
    • 实现了页表条目的管理
    • 实现了栈帧的管理,newallocdealloc等内存分配回收函数
    • 对物理页分配进行了测试,测试了new allocdealloc