导读
参考:
在应用程序的视角中,动态内存分配中的内存,其实就是操作系统管理的“堆 (Heap)”。但现在要实现操作系统,那么就需要操作系统自身能提供动态内存分配的能力。如果要实现动态内存分配的能力,需要操作系统需要有如下功能:
初始时能提供一块大内存空间作为初始的“堆” 。 在没有分页机制情况下,这块空间是物理内存空间,否则就是虚拟内存空间。
提供在堆上分配一块内存的函数接口。 这样函数调用方就能够得到一块地址连续的空闲内存块进行读写。
提供释放内存的函数接口 。能够回收内存,以备后续的内存分配请求。
提供空闲空间管理的连续内存分配算法 。能够有效地管理空闲快,这样就能够动态地维护一系列空闲和已分配的内存块。
(可选)提供建立在堆上的数据结构和操作 。有了上述基本的内存分配与释放函数接口,就可以实现类似动态数组,动态字典等空间灵活可变的堆数据结构,提高编程的灵活性。
操作系统给应用程序提供统一的访问接口,即应用程序不需要了解虚拟内存和物理内存的区别的, 操作系统提出了 地址空间 Address Space
抽象,并在内核中建立虚实地址空间的映射机制,给应用程序提供一个虚拟的内存环境。
到目前为止仍被操作系统内核广泛使用的抽象被称为 地址空间 (Address Space) 。某种程度上讲,可以将它看成一块 巨大但并不一定真实存在的内存。在每个应用程序的视角里,操作系统分配给应用程序一个范围有限(但其实很大),独占的连续地址空间(其中有些地方被操作系统限制不能访问,如内核本身占用的虚地址空间等),因此应用程序可以在划分给它的地址空间中随意规划内存布局,它的 各个段也就可以分别放置在地址空间中它希望的位置(当然是操作系统允许应用访问的地址)。应用同样可以使用一个地址作为索引来读写自己地址空间的数据,就像用物理地址 作为索引来读写物理内存上的数据一样。这种地址被称为 虚拟地址 (Virtual Address) 。当然,操作系统要达到 地址空间 抽象的设计目标,需要有计算机硬件的支持,这就是计算机组成原理课上讲到的 MMU
和 TLB
等硬件机制。
分段管理: 尽管内碎片被消除了,但内存浪费问题并没有完全解决。这是因为每个段的大小都是不同的(它们可能来自不同的应用,功能 也不同),内核就需要使用更加通用、也更加复杂的连续内存分配算法来进行内存管理,而不能像之前的插槽那样以一个比特 为单位。顾名思义,连续内存分配算法就是每次需要分配一块连续内存来存放一个段的数据。 随着一段时间的分配和回收,物理内存还剩下一些相互不连续的较小的可用连续块,其中有一些只是两个已分配内存块之间的很小的间隙,它们自己可能由于空间较小,已经无法被 用于分配,被称为 外碎片 (External Fragment) 。
分页管理:
就需要内核始终以一个同样大小的单位来在物理内存上放置应用地址空间中的数据,这样内核就可以 使用简单的插槽式内存管理,使得内存分配算法比较简单且不会产生外碎片;同时,这个单位的大小要足够小,从而其内部没有 被用到的内碎片的大小也足够小,尽可能提高内存利用率。这便是我们将要介绍的分页内存管理。
为了方便实现虚拟页面到物理页帧的地址转换,我们给每个虚拟页面和物理页帧一个编号,分别称为 虚拟页号 (VPN, Virtual Page Number) 和 物理页号 (PPN, Physical Page Number) 。每个应用都有一个不同的 页表 (Page Table) ,里面记录了该应用地址空间中的每个虚拟页面映射到物理内存中的哪个物理页帧,即数据实际 被内核放在哪里。我们可以用页号来代表二者,因此如果将页表看成一个键值对,其键的类型为虚拟页号,值的类型则为物理 页号。
当 MMU 进行地址转换的时候: 当然对三级页表 映射关系更加复杂,但总体上逻辑差不多
它首先找到给定的虚拟地址所在的虚拟页面的页号
然后查当前应用的页表根据虚拟页号 找到物理页号
最后按照虚拟地址在它所在的虚拟页面中的相对位置相应给物理页号对应的物理页帧的起始地址加上一个偏移量, 这就得到了实际访问的物理地址。
1.riscv的分页机制 riscv支持三种分页转换机制:
Sv32 :仅支持32位riscv处理器,是一个二级页表结构,支持32位虚拟地址转换
Sv39 :支持64位riscv处理器,是一个三级页表结构,支持39位虚拟地址转换
Sv48 :支持64位riscv处理器,是一个四级页表结构,支持48位虚拟地址转换
我们采用sv39
的机制进行分页管理,即使用三级页表结构
参考:
RISC-V 虚拟存储系统(文档阅读学习)_satp寄存器-CSDN博客
实现 SV39 多级页表机制(上) — rCore-Tutorial-Book-v3 0.1 文档 (gitcode.host)
介绍如下:
SATP寄存器 SATP(Supervisor Address Translation and Protection Register):控制supervisor
模式下的地址转换和保护
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}
取指、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 :保留位
三级页表虚拟地址转换物理地址过程
MMU
通过satp
寄存器得到PGD
的物理地址,结合PGD index
(即VPN[2]
)找到PMD
;找到PMD
后,再结合PMD index
(即VPN[1]
)找到PTE
,然后结合PTE index
(即VPN[0]
)得到VA
在PTE
索引中的值,从而得到物理地址。
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; } 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.c
和 address.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 #define PAGE_SIZE_BITS 0xc #define PA_WIDTH_SV39 56 #define VA_WIDTH_SV39 39 #define PPN_WIDTH_SV39 (PA_WIDTH_SV39 - PAGE_SIZE_BITS) #define VPN_WIDTH_SV39 (VA_WIDTH_SV39 - PAGE_SIZE_BITS) #define MEMORY_END 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) ;#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
。
**size_t_from_phys_page_num
**:将物理页号 PhysPageNum
转换为 uint64_t
。
**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 PhysAddr phys_addr_from_size_t (uint64_t v) { PhysAddr addr; addr.value = v & ((1ULL << PA_WIDTH_SV39) - 1 ); return addr; } PhysPageNum phys_page_num_from_size_t (uint64_t v) { PhysPageNum pageNum; pageNum.value = v & ((1ULL << PPN_WIDTH_SV39) - 1 ); return pageNum; } uint64_t size_t_from_phys_addr (PhysAddr v) { return v.value; } 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; } VirtAddr virt_addr_from_size_t (uint64_t v) { VirtAddr addr; addr.value = v & ((1ULL << VA_WIDTH_SV39) - 1 ); return addr; } VirtPageNum virt_page_num_from_size_t (uint64_t v) { VirtPageNum pageNum; pageNum.value = v & ((1ULL << VPN_WIDTH_SV39) - 1 ); return pageNum; } 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; } } 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
,同时将管理器内部维护的 current
加 1
代表 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 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 ; } 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
栈中,然后再次分配五页内存,此时分配的话就是从recycled
中pop
的内存了。强调一下在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 ) { } }
总结
本节新增了以上的文件 :
在stack
中实现了栈这个数据结构,因为后续的内存管理需要用到栈。
在assert
中,实现了断言
在address
中,实现了Sv39的三级页表内存管理
实现了将uint_64
转换位物理地址,虚拟地址等 PPN
,VPN
实现了页表条目的管理
实现了栈帧的管理,new
,alloc
,dealloc
等内存分配回收函数
对物理页分配进行了测试,测试了new
alloc
,dealloc